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