Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 : * vim: set ts=8 sts=4 et sw=4 tw=99:
3 : * This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : #ifndef jit_IonControlFlow_h
8 : #define jit_IonControlFlow_h
9 :
10 : #include "mozilla/Array.h"
11 :
12 : #include "jsbytecode.h"
13 :
14 : #include "jit/BytecodeAnalysis.h"
15 : #include "jit/FixedList.h"
16 : #include "jit/JitAllocPolicy.h"
17 : #include "js/TypeDecls.h"
18 :
19 : namespace js {
20 : namespace jit {
21 :
22 : class CFGControlInstruction;
23 :
24 : // Adds MFoo::New functions which are mirroring the arguments of the
25 : // constructors. Opcodes which are using this macro can be called with a
26 : // TempAllocator, or the fallible version of the TempAllocator.
27 : #define TRIVIAL_CFG_NEW_WRAPPERS \
28 : template <typename... Args> \
29 : static CFGThisOpcode* New(TempAllocator& alloc, Args&&... args) { \
30 : return new(alloc) CFGThisOpcode(mozilla::Forward<Args>(args)...); \
31 : } \
32 : template <typename... Args> \
33 : static CFGThisOpcode* New(TempAllocator::Fallible alloc, Args&&... args) \
34 : { \
35 : return new(alloc) CFGThisOpcode(mozilla::Forward<Args>(args)...); \
36 : }
37 :
38 0 : class CFGSpace
39 : {
40 : static const size_t DEFAULT_CHUNK_SIZE = 4096;
41 :
42 : protected:
43 : LifoAlloc allocator_;
44 : public:
45 :
46 13 : explicit CFGSpace()
47 13 : : allocator_(DEFAULT_CHUNK_SIZE)
48 13 : {}
49 :
50 19 : LifoAlloc& lifoAlloc() {
51 19 : return allocator_;
52 : }
53 :
54 0 : size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
55 0 : return allocator_.sizeOfExcludingThis(mallocSizeOf);
56 : }
57 : };
58 :
59 : class CFGBlock : public TempObject
60 : {
61 : size_t id_;
62 : jsbytecode* start;
63 : jsbytecode* stop;
64 : CFGControlInstruction* end;
65 : bool inWorkList;
66 :
67 : public:
68 4656 : explicit CFGBlock(jsbytecode* start)
69 4656 : : id_(-1),
70 : start(start),
71 : stop(nullptr),
72 : end(nullptr),
73 4656 : inWorkList(false)
74 4656 : {}
75 :
76 2328 : static CFGBlock* New(TempAllocator& alloc, jsbytecode* start) {
77 2328 : return new(alloc) CFGBlock(start);
78 : }
79 :
80 : void operator=(const CFGBlock&) = delete;
81 :
82 15406 : jsbytecode* startPc() const {
83 15406 : return start;
84 : }
85 0 : void setStartPc(jsbytecode* startPc) {
86 0 : start = startPc;
87 0 : }
88 24483 : jsbytecode* stopPc() const {
89 24483 : MOZ_ASSERT(stop);
90 24483 : return stop;
91 : }
92 4656 : void setStopPc(jsbytecode* stopPc) {
93 4656 : stop = stopPc;
94 4656 : }
95 5314 : CFGControlInstruction* stopIns() const {
96 5314 : MOZ_ASSERT(end);
97 5314 : return end;
98 : }
99 4656 : void setStopIns(CFGControlInstruction* stopIns) {
100 4656 : end = stopIns;
101 4656 : }
102 : bool isInWorkList() const {
103 : return inWorkList;
104 : }
105 : void setInWorklist() {
106 : MOZ_ASSERT(!inWorkList);
107 : inWorkList = true;
108 : }
109 : void clearInWorkList() {
110 : MOZ_ASSERT(inWorkList);
111 : inWorkList = false;
112 : }
113 8890 : size_t id() const {
114 8890 : return id_;
115 : }
116 4656 : void setId(size_t id) {
117 4656 : id_ = id;
118 4656 : }
119 : };
120 :
121 : #define CFG_CONTROL_OPCODE_LIST(_) \
122 : _(Test) \
123 : _(Compare) \
124 : _(Goto) \
125 : _(Return) \
126 : _(RetRVal) \
127 : _(LoopEntry) \
128 : _(BackEdge) \
129 : _(TableSwitch) \
130 : _(Try) \
131 : _(Throw)
132 :
133 : // Forward declarations of MIR types.
134 : #define FORWARD_DECLARE(type) class CFG##type;
135 : CFG_CONTROL_OPCODE_LIST(FORWARD_DECLARE)
136 : #undef FORWARD_DECLARE
137 :
138 : #define CFG_CONTROL_HEADER(type_name) \
139 : static const Type classOpcode = CFGControlInstruction::Type_##type_name; \
140 : using CFGThisOpcode = CFG##type_name; \
141 : Type type() const override { \
142 : return classOpcode; \
143 : } \
144 : const char* Name() const override { \
145 : return #type_name; \
146 : } \
147 :
148 :
149 4656 : class CFGControlInstruction : public TempObject
150 : {
151 : public:
152 : enum Type {
153 : # define DEFINE_TYPES(type) Type_##type,
154 : CFG_CONTROL_OPCODE_LIST(DEFINE_TYPES)
155 : # undef DEFINE_TYPES
156 : };
157 :
158 : virtual size_t numSuccessors() const = 0;
159 : virtual CFGBlock* getSuccessor(size_t i) const = 0;
160 : virtual void replaceSuccessor(size_t i, CFGBlock* successor) = 0;
161 : virtual Type type() const = 0;
162 : virtual const char* Name() const = 0;
163 :
164 4252 : template<typename CFGType> bool is() const {
165 4252 : return type() == CFGType::classOpcode;
166 : }
167 4211 : template<typename CFGType> CFGType* to() {
168 4211 : MOZ_ASSERT(this->is<CFGType>());
169 4211 : return static_cast<CFGType*>(this);
170 : }
171 : template<typename CFGType> const CFGType* to() const {
172 : MOZ_ASSERT(this->is<CFGType>());
173 : return static_cast<const CFGType*>(this);
174 : }
175 : # define TYPE_CASTS(type) \
176 : bool is##type() const { \
177 : return this->is<CFG##type>(); \
178 : } \
179 : CFG##type* to##type() { \
180 : return this->to<CFG##type>(); \
181 : } \
182 : const CFG##type* to##type() const { \
183 : return this->to<CFG##type>(); \
184 : }
185 4252 : CFG_CONTROL_OPCODE_LIST(TYPE_CASTS)
186 : # undef TYPE_CASTS
187 : };
188 :
189 : template <size_t Successors>
190 4558 : class CFGAryControlInstruction : public CFGControlInstruction
191 : {
192 : mozilla::Array<CFGBlock*, Successors> successors_;
193 :
194 : public:
195 0 : size_t numSuccessors() const final override {
196 0 : return Successors;
197 : }
198 9235 : CFGBlock* getSuccessor(size_t i) const final override {
199 9235 : return successors_[i];
200 : }
201 5076 : void replaceSuccessor(size_t i, CFGBlock* succ) final override {
202 5076 : successors_[i] = succ;
203 5076 : }
204 : };
205 :
206 : class CFGTry : public CFGControlInstruction
207 : {
208 : CFGBlock* tryBlock_;
209 : jsbytecode* catchStartPc_;
210 : CFGBlock* mergePoint_;
211 :
212 10 : CFGTry(CFGBlock* successor, jsbytecode* catchStartPc, CFGBlock* mergePoint = nullptr)
213 10 : : tryBlock_(successor),
214 : catchStartPc_(catchStartPc),
215 10 : mergePoint_(mergePoint)
216 10 : { }
217 :
218 : public:
219 20 : CFG_CONTROL_HEADER(Try)
220 5 : TRIVIAL_CFG_NEW_WRAPPERS
221 :
222 5 : static CFGTry* CopyWithNewTargets(TempAllocator& alloc, CFGTry* old,
223 : CFGBlock* tryBlock, CFGBlock* merge)
224 : {
225 5 : return new(alloc) CFGTry(tryBlock, old->catchStartPc(), merge);
226 : }
227 :
228 23 : size_t numSuccessors() const final override {
229 23 : return mergePoint_ ? 2 : 1;
230 : }
231 18 : CFGBlock* getSuccessor(size_t i) const final override {
232 18 : MOZ_ASSERT(i < numSuccessors());
233 18 : return (i == 0) ? tryBlock_ : mergePoint_;
234 : }
235 0 : void replaceSuccessor(size_t i, CFGBlock* succ) final override {
236 0 : MOZ_ASSERT(i < numSuccessors());
237 0 : if (i == 0)
238 0 : tryBlock_ = succ;
239 : else
240 0 : mergePoint_ = succ;
241 0 : }
242 :
243 9 : CFGBlock* tryBlock() const {
244 9 : return getSuccessor(0);
245 : }
246 :
247 7 : jsbytecode* catchStartPc() const {
248 7 : return catchStartPc_;
249 : }
250 :
251 7 : CFGBlock* afterTryCatchBlock() const {
252 7 : return getSuccessor(1);
253 : }
254 :
255 2 : bool codeAfterTryCatchReachable() const {
256 2 : return !!mergePoint_;
257 : }
258 : };
259 :
260 : class CFGTableSwitch : public CFGControlInstruction
261 : {
262 : Vector<CFGBlock*, 4, JitAllocPolicy> successors_;
263 : size_t low_;
264 : size_t high_;
265 :
266 88 : CFGTableSwitch(TempAllocator& alloc, size_t low, size_t high)
267 88 : : successors_(alloc),
268 : low_(low),
269 88 : high_(high)
270 88 : {}
271 :
272 : public:
273 176 : CFG_CONTROL_HEADER(TableSwitch);
274 :
275 88 : static CFGTableSwitch* New(TempAllocator& alloc, size_t low, size_t high) {
276 88 : return new(alloc) CFGTableSwitch(alloc, low, high);
277 : }
278 :
279 2904 : size_t numSuccessors() const final override {
280 2904 : return successors_.length();
281 : }
282 1540 : CFGBlock* getSuccessor(size_t i) const final override {
283 1540 : MOZ_ASSERT(i < numSuccessors());
284 1540 : return successors_[i];
285 : }
286 0 : void replaceSuccessor(size_t i, CFGBlock* succ) final override {
287 0 : MOZ_ASSERT(i < numSuccessors());
288 0 : successors_[i] = succ;
289 0 : }
290 :
291 88 : bool addDefault(CFGBlock* defaultCase) {
292 88 : MOZ_ASSERT(successors_.length() == 0);
293 88 : return successors_.append(defaultCase);
294 : }
295 :
296 528 : bool addCase(CFGBlock* caseBlock) {
297 528 : MOZ_ASSERT(successors_.length() > 0);
298 528 : return successors_.append(caseBlock);
299 : }
300 :
301 88 : CFGBlock* defaultCase() const {
302 88 : return getSuccessor(0);
303 : }
304 :
305 528 : CFGBlock* getCase(size_t i) const {
306 528 : return getSuccessor(i + 1);
307 : }
308 :
309 88 : size_t high() const {
310 88 : return high_;
311 : }
312 :
313 88 : size_t low() const {
314 88 : return low_;
315 : }
316 : };
317 :
318 : /**
319 : * CFGCompare
320 : *
321 : * PEEK
322 : * PEEK
323 : * STRICTEQ
324 : * POP truePopAmount
325 : * JUMP succ1
326 : * STRICTNEQ
327 : * POP falsePopAmount
328 : * JUMP succ2
329 : */
330 : class CFGCompare : public CFGAryControlInstruction<2>
331 : {
332 : const size_t truePopAmount_;
333 : const size_t falsePopAmount_;
334 :
335 0 : CFGCompare(CFGBlock* succ1, size_t truePopAmount, CFGBlock* succ2, size_t falsePopAmount)
336 0 : : truePopAmount_(truePopAmount),
337 0 : falsePopAmount_(falsePopAmount)
338 : {
339 0 : replaceSuccessor(0, succ1);
340 0 : replaceSuccessor(1, succ2);
341 0 : }
342 :
343 : public:
344 0 : CFG_CONTROL_HEADER(Compare);
345 :
346 0 : static CFGCompare* NewFalseBranchIsDefault(TempAllocator& alloc, CFGBlock* case_,
347 : CFGBlock* default_)
348 : {
349 : // True and false branch both go to a body and don't need the lhs and
350 : // rhs to the compare. Pop them.
351 0 : return new(alloc) CFGCompare(case_, 2, default_, 2);
352 : }
353 :
354 0 : static CFGCompare* NewFalseBranchIsNextCompare(TempAllocator& alloc, CFGBlock* case_,
355 : CFGBlock* nextCompare)
356 : {
357 : // True branch goes to the body and don't need the lhs and
358 : // rhs to the compare anymore. Pop them. The next compare still
359 : // needs the lhs.
360 0 : return new(alloc) CFGCompare(case_, 2, nextCompare, 1);
361 : }
362 :
363 0 : static CFGCompare* CopyWithNewTargets(TempAllocator& alloc, CFGCompare* old,
364 : CFGBlock* succ1, CFGBlock* succ2)
365 : {
366 0 : return new(alloc) CFGCompare(succ1, old->truePopAmount(), succ2, old->falsePopAmount());
367 : }
368 :
369 0 : CFGBlock* trueBranch() const {
370 0 : return getSuccessor(0);
371 : }
372 0 : CFGBlock* falseBranch() const {
373 0 : return getSuccessor(1);
374 : }
375 0 : size_t truePopAmount() const {
376 0 : return truePopAmount_;
377 : }
378 0 : size_t falsePopAmount() const {
379 0 : return falsePopAmount_;
380 : }
381 : };
382 :
383 : /**
384 : * CFGTest
385 : *
386 : * POP / PEEK (depending on keepCondition_)
387 : * IFEQ JUMP succ1
388 : * IFNEQ JUMP succ2
389 : *
390 : */
391 : class CFGTest : public CFGAryControlInstruction<2>
392 : {
393 : // By default the condition gets popped. This variable
394 : // keeps track if we want to keep the condition.
395 : bool keepCondition_;
396 :
397 760 : CFGTest(CFGBlock* succ1, CFGBlock* succ2)
398 760 : : keepCondition_(false)
399 : {
400 760 : replaceSuccessor(0, succ1);
401 760 : replaceSuccessor(1, succ2);
402 760 : }
403 760 : CFGTest(CFGBlock* succ1, CFGBlock* succ2, bool keepCondition)
404 760 : : keepCondition_(keepCondition)
405 : {
406 760 : replaceSuccessor(0, succ1);
407 760 : replaceSuccessor(1, succ2);
408 760 : }
409 :
410 : public:
411 3344 : CFG_CONTROL_HEADER(Test);
412 760 : TRIVIAL_CFG_NEW_WRAPPERS
413 :
414 760 : static CFGTest* CopyWithNewTargets(TempAllocator& alloc, CFGTest* old,
415 : CFGBlock* succ1, CFGBlock* succ2)
416 : {
417 760 : return new(alloc) CFGTest(succ1, succ2, old->mustKeepCondition());
418 : }
419 :
420 2584 : CFGBlock* trueBranch() const {
421 2584 : return getSuccessor(0);
422 : }
423 3496 : CFGBlock* falseBranch() const {
424 3496 : return getSuccessor(1);
425 : }
426 46 : void keepCondition() {
427 46 : keepCondition_ = true;
428 46 : }
429 1672 : bool mustKeepCondition() const {
430 1672 : return keepCondition_;
431 : }
432 : };
433 :
434 : /**
435 : * CFGReturn
436 : *
437 : * POP
438 : * RETURN popped value
439 : *
440 : */
441 956 : class CFGReturn : public CFGAryControlInstruction<0>
442 : {
443 : public:
444 1554 : CFG_CONTROL_HEADER(Return);
445 956 : TRIVIAL_CFG_NEW_WRAPPERS
446 : };
447 :
448 : /**
449 : * CFGRetRVal
450 : *
451 : * RETURN the value in the return value slot
452 : *
453 : */
454 44 : class CFGRetRVal : public CFGAryControlInstruction<0>
455 : {
456 : public:
457 68 : CFG_CONTROL_HEADER(RetRVal);
458 44 : TRIVIAL_CFG_NEW_WRAPPERS
459 : };
460 :
461 : /**
462 : * CFGThrow
463 : *
464 : * POP
465 : * THROW popped value
466 : *
467 : */
468 2 : class CFGThrow : public CFGAryControlInstruction<0>
469 : {
470 : public:
471 3 : CFG_CONTROL_HEADER(Throw);
472 2 : TRIVIAL_CFG_NEW_WRAPPERS
473 : };
474 :
475 : class CFGUnaryControlInstruction : public CFGAryControlInstruction<1>
476 : {
477 : public:
478 2036 : explicit CFGUnaryControlInstruction(CFGBlock* block) {
479 2036 : MOZ_ASSERT(block);
480 2036 : replaceSuccessor(0, block);
481 2036 : }
482 :
483 235 : CFGBlock* successor() const {
484 235 : return getSuccessor(0);
485 : }
486 : };
487 :
488 : /**
489 : * CFGGOTO
490 : *
491 : * POP (x popAmount)
492 : * JMP block
493 : *
494 : */
495 : class CFGGoto : public CFGUnaryControlInstruction
496 : {
497 : const size_t popAmount_;
498 :
499 784 : explicit CFGGoto(CFGBlock* block)
500 784 : : CFGUnaryControlInstruction(block),
501 784 : popAmount_(0)
502 784 : {}
503 :
504 784 : CFGGoto(CFGBlock* block, size_t popAmount_)
505 784 : : CFGUnaryControlInstruction(block),
506 784 : popAmount_(popAmount_)
507 784 : {}
508 :
509 : public:
510 3512 : CFG_CONTROL_HEADER(Goto);
511 784 : TRIVIAL_CFG_NEW_WRAPPERS
512 :
513 784 : static CFGGoto* CopyWithNewTargets(TempAllocator& alloc, CFGGoto* old, CFGBlock* block)
514 : {
515 784 : return new(alloc) CFGGoto(block, old->popAmount());
516 : }
517 :
518 1736 : size_t popAmount() const {
519 1736 : return popAmount_;
520 : }
521 : };
522 :
523 : /**
524 : * CFGBackEdge
525 : *
526 : * Jumps back to the start of the loop.
527 : *
528 : * JMP block
529 : *
530 : */
531 : class CFGBackEdge : public CFGUnaryControlInstruction
532 : {
533 234 : explicit CFGBackEdge(CFGBlock* block)
534 234 : : CFGUnaryControlInstruction(block)
535 234 : {}
536 :
537 : public:
538 469 : CFG_CONTROL_HEADER(BackEdge);
539 117 : TRIVIAL_CFG_NEW_WRAPPERS
540 :
541 117 : static CFGBackEdge* CopyWithNewTargets(TempAllocator& alloc, CFGBackEdge* old, CFGBlock* block)
542 : {
543 117 : return new(alloc) CFGBackEdge(block);
544 : }
545 : };
546 :
547 : /**
548 : * CFGLOOPENTRY
549 : *
550 : * Indicates the jumping block is the start of a loop.
551 : * That block is the only block allowed to have a backedge.
552 : *
553 : * JMP block
554 : *
555 : */
556 : class CFGLoopEntry : public CFGUnaryControlInstruction
557 : {
558 : bool canOsr_;
559 : size_t stackPhiCount_;
560 : jsbytecode* loopStopPc_;
561 :
562 117 : CFGLoopEntry(CFGBlock* block, size_t stackPhiCount)
563 117 : : CFGUnaryControlInstruction(block),
564 : canOsr_(false),
565 : stackPhiCount_(stackPhiCount),
566 117 : loopStopPc_(nullptr)
567 117 : {}
568 :
569 117 : CFGLoopEntry(CFGBlock* block, bool canOsr, size_t stackPhiCount, jsbytecode* loopStopPc)
570 117 : : CFGUnaryControlInstruction(block),
571 : canOsr_(canOsr),
572 : stackPhiCount_(stackPhiCount),
573 117 : loopStopPc_(loopStopPc)
574 117 : {}
575 :
576 : public:
577 705 : CFG_CONTROL_HEADER(LoopEntry);
578 117 : TRIVIAL_CFG_NEW_WRAPPERS
579 :
580 117 : static CFGLoopEntry* CopyWithNewTargets(TempAllocator& alloc, CFGLoopEntry* old,
581 : CFGBlock* loopEntry)
582 : {
583 117 : return new(alloc) CFGLoopEntry(loopEntry, old->canOsr(), old->stackPhiCount(),
584 117 : old->loopStopPc());
585 : }
586 :
587 117 : void setCanOsr() {
588 117 : canOsr_ = true;
589 117 : }
590 :
591 239 : bool canOsr() const {
592 239 : return canOsr_;
593 : }
594 :
595 235 : size_t stackPhiCount() const {
596 235 : return stackPhiCount_;
597 : }
598 :
599 235 : jsbytecode* loopStopPc() const {
600 235 : MOZ_ASSERT(loopStopPc_);
601 235 : return loopStopPc_;
602 : }
603 :
604 117 : void setLoopStopPc(jsbytecode* loopStopPc) {
605 117 : loopStopPc_ = loopStopPc;
606 117 : }
607 : };
608 :
609 : typedef Vector<CFGBlock*, 4, JitAllocPolicy> CFGBlockVector;
610 :
611 : class ControlFlowGraph : public TempObject
612 : {
613 : // A list of blocks in RPO, containing per block a pc-range and
614 : // a control instruction.
615 : Vector<CFGBlock, 4, JitAllocPolicy> blocks_;
616 :
617 150 : explicit ControlFlowGraph(TempAllocator& alloc)
618 150 : : blocks_(alloc)
619 150 : {}
620 :
621 : public:
622 150 : static ControlFlowGraph* New(TempAllocator& alloc) {
623 150 : return new(alloc) ControlFlowGraph(alloc);
624 : }
625 :
626 : ControlFlowGraph(const ControlFlowGraph&) = delete;
627 : void operator=(const ControlFlowGraph&) = delete;
628 :
629 : void dump(GenericPrinter& print, JSScript* script);
630 : bool init(TempAllocator& alloc, const CFGBlockVector& blocks);
631 :
632 2713 : const CFGBlock* block(size_t i) const {
633 2713 : return &blocks_[i];
634 : }
635 :
636 5883 : size_t numBlocks() const {
637 5883 : return blocks_.length();
638 : }
639 : };
640 :
641 150 : class ControlFlowGenerator
642 : {
643 : static int CmpSuccessors(const void* a, const void* b);
644 :
645 : JSScript* script;
646 : CFGBlock* current;
647 : jsbytecode* pc;
648 : GSNCache gsn;
649 : TempAllocator& alloc_;
650 : CFGBlockVector blocks_;
651 :
652 : public:
653 : ControlFlowGenerator(const ControlFlowGenerator&) = delete;
654 : void operator=(const ControlFlowGenerator&) = delete;
655 :
656 24603 : TempAllocator& alloc() {
657 24603 : return alloc_;
658 : }
659 :
660 : enum class ControlStatus {
661 : Error,
662 : Abort,
663 : Ended, // There is no continuation/join point.
664 : Joined, // Created a join node.
665 : Jumped, // Parsing another branch at the same level.
666 : None // No control flow.
667 : };
668 :
669 : struct DeferredEdge : public TempObject
670 : {
671 : CFGBlock* block;
672 : DeferredEdge* next;
673 :
674 29 : DeferredEdge(CFGBlock* block, DeferredEdge* next)
675 29 : : block(block), next(next)
676 29 : { }
677 : };
678 :
679 : struct ControlFlowInfo {
680 : // Entry in the cfgStack.
681 : uint32_t cfgEntry;
682 :
683 : // Label that continues go to.
684 : jsbytecode* continuepc;
685 :
686 161 : ControlFlowInfo(uint32_t cfgEntry, jsbytecode* continuepc)
687 161 : : cfgEntry(cfgEntry),
688 161 : continuepc(continuepc)
689 161 : { }
690 : };
691 :
692 :
693 : // To avoid recursion, the bytecode analyzer uses a stack where each entry
694 : // is a small state machine. As we encounter branches or jumps in the
695 : // bytecode, we push information about the edges on the stack so that the
696 : // CFG can be built in a tree-like fashion.
697 : struct CFGState {
698 : enum State {
699 : IF_TRUE, // if() { }, no else.
700 : IF_TRUE_EMPTY_ELSE, // if() { }, empty else
701 : IF_ELSE_TRUE, // if() { X } else { }
702 : IF_ELSE_FALSE, // if() { } else { X }
703 : DO_WHILE_LOOP_BODY, // do { x } while ()
704 : DO_WHILE_LOOP_COND, // do { } while (x)
705 : WHILE_LOOP_COND, // while (x) { }
706 : WHILE_LOOP_BODY, // while () { x }
707 : FOR_LOOP_COND, // for (; x;) { }
708 : FOR_LOOP_BODY, // for (; ;) { x }
709 : FOR_LOOP_UPDATE, // for (; ; x) { }
710 : TABLE_SWITCH, // switch() { x }
711 : COND_SWITCH_CASE, // switch() { case X: ... }
712 : COND_SWITCH_BODY, // switch() { case ...: X }
713 : AND_OR, // && x, || x
714 : LABEL, // label: x
715 : TRY // try { x } catch(e) { }
716 : };
717 :
718 : State state; // Current state of this control structure.
719 : jsbytecode* stopAt; // Bytecode at which to stop the processing loop.
720 :
721 : // For if structures, this contains branch information.
722 : union {
723 : struct {
724 : CFGBlock* ifFalse;
725 : jsbytecode* falseEnd;
726 : CFGBlock* ifTrue; // Set when the end of the true path is reached.
727 : CFGTest* test;
728 : } branch;
729 : struct {
730 : // Common entry point.
731 : CFGBlock* entry;
732 :
733 : // Position of where the loop body starts and ends.
734 : jsbytecode* bodyStart;
735 : jsbytecode* bodyEnd;
736 :
737 : // pc immediately after the loop exits.
738 : jsbytecode* exitpc;
739 :
740 : // Common exit point. Created lazily, so it may be nullptr.
741 : CFGBlock* successor;
742 :
743 : // Deferred break and continue targets.
744 : DeferredEdge* breaks;
745 : DeferredEdge* continues;
746 :
747 : // Initial state, in case loop processing is restarted.
748 : State initialState;
749 : jsbytecode* initialPc;
750 : jsbytecode* initialStopAt;
751 : jsbytecode* loopHead;
752 :
753 : // For-loops only.
754 : jsbytecode* condpc;
755 : jsbytecode* updatepc;
756 : jsbytecode* updateEnd;
757 : } loop;
758 : struct {
759 : // Vector of body blocks to process after the cases.
760 : FixedList<CFGBlock*>* bodies;
761 :
762 : // When processing case statements, this counter points at the
763 : // last uninitialized body. When processing bodies, this
764 : // counter targets the next body to process.
765 : uint32_t currentIdx;
766 :
767 : // Remember the block index of the default case.
768 : jsbytecode* defaultTarget;
769 : uint32_t defaultIdx;
770 :
771 : // Block immediately after the switch.
772 : jsbytecode* exitpc;
773 : DeferredEdge* breaks;
774 : } switch_;
775 : struct {
776 : DeferredEdge* breaks;
777 : } label;
778 : struct {
779 : CFGBlock* successor;
780 : } try_;
781 : };
782 :
783 827 : inline bool isLoop() const {
784 827 : switch (state) {
785 : case DO_WHILE_LOOP_COND:
786 : case DO_WHILE_LOOP_BODY:
787 : case WHILE_LOOP_COND:
788 : case WHILE_LOOP_BODY:
789 : case FOR_LOOP_COND:
790 : case FOR_LOOP_BODY:
791 : case FOR_LOOP_UPDATE:
792 135 : return true;
793 : default:
794 692 : return false;
795 : }
796 : }
797 :
798 : static CFGState If(jsbytecode* join, CFGTest* test);
799 : static CFGState IfElse(jsbytecode* trueEnd, jsbytecode* falseEnd, CFGTest* test);
800 : static CFGState AndOr(jsbytecode* join, CFGBlock* lhs);
801 : static CFGState TableSwitch(TempAllocator& alloc, jsbytecode* exitpc);
802 : static CFGState CondSwitch(TempAllocator& alloc, jsbytecode* exitpc,
803 : jsbytecode* defaultTarget);
804 : static CFGState Label(jsbytecode* exitpc);
805 : static CFGState Try(jsbytecode* exitpc, CFGBlock* successor);
806 : };
807 :
808 : Vector<CFGState, 8, JitAllocPolicy> cfgStack_;
809 : Vector<ControlFlowInfo, 4, JitAllocPolicy> loops_;
810 : Vector<ControlFlowInfo, 0, JitAllocPolicy> switches_;
811 : Vector<ControlFlowInfo, 2, JitAllocPolicy> labels_;
812 : BytecodeAnalysis analysis_;
813 : bool aborted_;
814 :
815 : public:
816 : ControlFlowGenerator(TempAllocator& alloc, JSScript* script);
817 :
818 : MOZ_MUST_USE bool init();
819 :
820 : MOZ_MUST_USE bool traverseBytecode();
821 : MOZ_MUST_USE bool addBlock(CFGBlock* block);
822 150 : ControlFlowGraph* getGraph(TempAllocator& alloc) {
823 150 : ControlFlowGraph* cfg = ControlFlowGraph::New(alloc);
824 150 : if (!cfg)
825 0 : return nullptr;
826 150 : if (!cfg->init(alloc, blocks_))
827 0 : return nullptr;
828 150 : return cfg;
829 : }
830 :
831 0 : bool aborted() const {
832 0 : return aborted_;
833 : }
834 :
835 : private:
836 : void popCfgStack();
837 : MOZ_MUST_USE bool processDeferredContinues(CFGState& state);
838 : ControlStatus processControlEnd();
839 : ControlStatus processCfgStack();
840 : ControlStatus processCfgEntry(CFGState& state);
841 : ControlStatus processIfStart(JSOp op);
842 : ControlStatus processIfEnd(CFGState& state);
843 : ControlStatus processIfElseTrueEnd(CFGState& state);
844 : ControlStatus processIfElseFalseEnd(CFGState& state);
845 : ControlStatus processDoWhileLoop(JSOp op, jssrcnote* sn);
846 : ControlStatus processDoWhileBodyEnd(CFGState& state);
847 : ControlStatus processDoWhileCondEnd(CFGState& state);
848 : ControlStatus processWhileCondEnd(CFGState& state);
849 : ControlStatus processWhileBodyEnd(CFGState& state);
850 : ControlStatus processForLoop(JSOp op, jssrcnote* sn);
851 : ControlStatus processForCondEnd(CFGState& state);
852 : ControlStatus processForBodyEnd(CFGState& state);
853 : ControlStatus processForUpdateEnd(CFGState& state);
854 : ControlStatus processWhileOrForInLoop(jssrcnote* sn);
855 : ControlStatus processNextTableSwitchCase(CFGState& state);
856 : ControlStatus processCondSwitch();
857 : ControlStatus processCondSwitchCase(CFGState& state);
858 : ControlStatus processCondSwitchDefault(CFGState& state);
859 : ControlStatus processCondSwitchBody(CFGState& state);
860 : ControlStatus processSwitchBreak(JSOp op);
861 : ControlStatus processSwitchEnd(DeferredEdge* breaks, jsbytecode* exitpc);
862 : ControlStatus processTry();
863 : ControlStatus processTryEnd(CFGState& state);
864 : ControlStatus processThrow();
865 : ControlStatus processTableSwitch(JSOp op, jssrcnote* sn);
866 : ControlStatus processContinue(JSOp op);
867 : ControlStatus processBreak(JSOp op, jssrcnote* sn);
868 : ControlStatus processReturn(JSOp op);
869 : ControlStatus maybeLoop(JSOp op, jssrcnote* sn);
870 : ControlStatus snoopControlFlow(JSOp op);
871 : ControlStatus processBrokenLoop(CFGState& state);
872 : ControlStatus finishLoop(CFGState& state, CFGBlock* successor);
873 : ControlStatus processAndOr(JSOp op);
874 : ControlStatus processAndOrEnd(CFGState& state);
875 : ControlStatus processLabel();
876 : ControlStatus processLabelEnd(CFGState& state);
877 :
878 : MOZ_MUST_USE bool pushLoop(CFGState::State state, jsbytecode* stopAt, CFGBlock* entry,
879 : jsbytecode* loopHead, jsbytecode* initialPc,
880 : jsbytecode* bodyStart, jsbytecode* bodyEnd,
881 : jsbytecode* exitpc, jsbytecode* continuepc);
882 : void endCurrentBlock(CFGControlInstruction* ins);
883 : CFGBlock* createBreakCatchBlock(DeferredEdge* edge, jsbytecode* pc);
884 : };
885 :
886 : } // namespace jit
887 : } // namespace js
888 :
889 : #endif /* jit_IonControlFlow_h */
|
