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 : #include "jit/IonControlFlow.h"
8 :
9 : #include "mozilla/DebugOnly.h"
10 : #include "mozilla/SizePrintfMacros.h"
11 :
12 : using namespace js;
13 : using namespace js::jit;
14 : using mozilla::DebugOnly;
15 :
16 150 : ControlFlowGenerator::ControlFlowGenerator(TempAllocator& temp, JSScript* script)
17 : : script(script),
18 : current(nullptr),
19 : alloc_(temp),
20 : blocks_(temp),
21 : cfgStack_(temp),
22 : loops_(temp),
23 : switches_(temp),
24 : labels_(temp),
25 : analysis_(temp, script),
26 150 : aborted_(false)
27 150 : { }
28 :
29 : bool
30 150 : ControlFlowGenerator::init()
31 : {
32 150 : return analysis_.init(alloc(), gsn);
33 : }
34 :
35 : static inline int32_t
36 1098 : GetJumpOffset(jsbytecode* pc)
37 : {
38 1098 : MOZ_ASSERT(CodeSpec[JSOp(*pc)].type() == JOF_JUMP);
39 1098 : return GET_JUMP_OFFSET(pc);
40 : }
41 :
42 : void
43 0 : ControlFlowGraph::dump(GenericPrinter& print, JSScript* script)
44 : {
45 0 : if (blocks_.length() == 0) {
46 0 : print.printf("Didn't run yet.\n");
47 0 : return;
48 : }
49 :
50 0 : fprintf(stderr, "Dumping cfg:\n\n");
51 0 : for (size_t i = 0; i < blocks_.length(); i++) {
52 0 : print.printf(" Block %" PRIuSIZE ", %" PRIuSIZE ":%" PRIuSIZE "\n",
53 0 : blocks_[i].id(),
54 0 : script->pcToOffset(blocks_[i].startPc()),
55 0 : script->pcToOffset(blocks_[i].stopPc()));
56 :
57 0 : jsbytecode* pc = blocks_[i].startPc();
58 0 : for ( ; pc < blocks_[i].stopPc(); pc += CodeSpec[JSOp(*pc)].length) {
59 0 : MOZ_ASSERT(pc < script->codeEnd());
60 0 : print.printf(" %" PRIuSIZE ": %s\n", script->pcToOffset(pc),
61 0 : CodeName[JSOp(*pc)]);
62 : }
63 :
64 0 : if (blocks_[i].stopIns()->isGoto()) {
65 0 : print.printf(" %s (popping:%" PRIuSIZE ") [",
66 0 : blocks_[i].stopIns()->Name(),
67 0 : blocks_[i].stopIns()->toGoto()->popAmount());
68 : } else {
69 0 : print.printf(" %s [", blocks_[i].stopIns()->Name());
70 : }
71 0 : for (size_t j=0; j<blocks_[i].stopIns()->numSuccessors(); j++) {
72 0 : if (j!=0)
73 0 : print.printf(", ");
74 0 : print.printf("%" PRIuSIZE, blocks_[i].stopIns()->getSuccessor(j)->id());
75 : }
76 0 : print.printf("]\n\n");
77 : }
78 : }
79 :
80 : bool
81 150 : ControlFlowGraph::init(TempAllocator& alloc, const CFGBlockVector& blocks)
82 : {
83 150 : if (!blocks_.reserve(blocks.length()))
84 0 : return false;
85 :
86 2478 : for (size_t i = 0; i < blocks.length(); i++) {
87 2328 : MOZ_ASSERT(blocks[i]->id() == i);
88 2328 : CFGBlock block(blocks[i]->startPc());
89 :
90 2328 : block.setStopPc(blocks[i]->stopPc());
91 2328 : block.setId(i);
92 2328 : blocks_.infallibleAppend(mozilla::Move(block));
93 : }
94 :
95 2478 : for (size_t i = 0; i < blocks.length(); i++) {
96 2328 : if (!alloc.ensureBallast())
97 0 : return false;
98 :
99 2328 : CFGControlInstruction* copy = nullptr;
100 2328 : CFGControlInstruction* ins = blocks[i]->stopIns();
101 2328 : switch (ins->type()) {
102 : case CFGControlInstruction::Type_Goto: {
103 784 : CFGBlock* successor = &blocks_[ins->getSuccessor(0)->id()];
104 784 : copy = CFGGoto::CopyWithNewTargets(alloc, ins->toGoto(), successor);
105 784 : break;
106 : }
107 : case CFGControlInstruction::Type_BackEdge: {
108 117 : CFGBlock* successor = &blocks_[ins->getSuccessor(0)->id()];
109 117 : copy = CFGBackEdge::CopyWithNewTargets(alloc, ins->toBackEdge(), successor);
110 117 : break;
111 : }
112 : case CFGControlInstruction::Type_LoopEntry: {
113 117 : CFGLoopEntry* old = ins->toLoopEntry();
114 117 : CFGBlock* successor = &blocks_[ins->getSuccessor(0)->id()];
115 117 : copy = CFGLoopEntry::CopyWithNewTargets(alloc, old, successor);
116 117 : break;
117 : }
118 : case CFGControlInstruction::Type_Throw: {
119 1 : copy = CFGThrow::New(alloc);
120 1 : break;
121 : }
122 : case CFGControlInstruction::Type_Test: {
123 760 : CFGTest* old = ins->toTest();
124 760 : CFGBlock* trueBranch = &blocks_[old->trueBranch()->id()];
125 760 : CFGBlock* falseBranch = &blocks_[old->falseBranch()->id()];
126 760 : copy = CFGTest::CopyWithNewTargets(alloc, old, trueBranch, falseBranch);
127 760 : break;
128 : }
129 : case CFGControlInstruction::Type_Compare: {
130 0 : CFGCompare* old = ins->toCompare();
131 0 : CFGBlock* trueBranch = &blocks_[old->trueBranch()->id()];
132 0 : CFGBlock* falseBranch = &blocks_[old->falseBranch()->id()];
133 0 : copy = CFGCompare::CopyWithNewTargets(alloc, old, trueBranch, falseBranch);
134 0 : break;
135 : }
136 : case CFGControlInstruction::Type_Return: {
137 478 : copy = CFGReturn::New(alloc);
138 478 : break;
139 : }
140 : case CFGControlInstruction::Type_RetRVal: {
141 22 : copy = CFGRetRVal::New(alloc);
142 22 : break;
143 : }
144 : case CFGControlInstruction::Type_Try: {
145 5 : CFGTry* old = ins->toTry();
146 5 : CFGBlock* tryBlock = &blocks_[old->tryBlock()->id()];
147 5 : CFGBlock* merge = nullptr;
148 5 : if (old->numSuccessors() == 2)
149 5 : merge = &blocks_[old->afterTryCatchBlock()->id()];
150 5 : copy = CFGTry::CopyWithNewTargets(alloc, old, tryBlock, merge);
151 5 : break;
152 : }
153 : case CFGControlInstruction::Type_TableSwitch: {
154 44 : CFGTableSwitch* old = ins->toTableSwitch();
155 : CFGTableSwitch* tableSwitch =
156 44 : CFGTableSwitch::New(alloc, old->low(), old->high());
157 44 : if (!tableSwitch->addDefault(&blocks_[old->defaultCase()->id()]))
158 0 : return false;
159 308 : for (size_t i = 0; i < ins->numSuccessors() - 1; i++) {
160 264 : if (!tableSwitch->addCase(&blocks_[old->getCase(i)->id()]))
161 0 : return false;
162 : }
163 44 : copy = tableSwitch;
164 44 : break;
165 : }
166 : }
167 2328 : MOZ_ASSERT(copy);
168 2328 : blocks_[i].setStopIns(copy);
169 : }
170 150 : return true;
171 : }
172 :
173 : bool
174 2328 : ControlFlowGenerator::addBlock(CFGBlock* block)
175 : {
176 2328 : block->setId(blocks_.length());
177 2328 : return blocks_.append(block);
178 : }
179 :
180 : // We try to build a control-flow graph in the order that it would be built as
181 : // if traversing the AST. This leads to a nice ordering and lets us build SSA
182 : // in one pass, since the bytecode is structured.
183 : //
184 : // Things get interesting when we encounter a control structure. This can be
185 : // either an IFEQ, downward GOTO, or a decompiler hint stashed away in source
186 : // notes. Once we encounter such an opcode, we recover the structure of the
187 : // control flow (its branches and bounds), and push it on a stack.
188 : //
189 : // As we continue traversing the bytecode, we look for points that would
190 : // terminate the topmost control flow path pushed on the stack. These are:
191 : // (1) The bounds of the current structure (end of a loop or join/edge of a
192 : // branch).
193 : // (2) A "return", "break", or "continue" statement.
194 : //
195 : // For (1), we expect that there is a current block in the progress of being
196 : // built, and we complete the necessary edges in the CFG. For (2), we expect
197 : // that there is no active block.
198 : bool
199 150 : ControlFlowGenerator::traverseBytecode()
200 : {
201 150 : blocks_.clear();
202 :
203 150 : current = CFGBlock::New(alloc(), script->code());
204 150 : pc = current->startPc();
205 :
206 150 : if (!addBlock(current))
207 0 : return false;
208 :
209 : for (;;) {
210 17167 : MOZ_ASSERT(pc < script->codeEnd());
211 :
212 : for (;;) {
213 19387 : if (!alloc().ensureBallast())
214 0 : return false;
215 :
216 : // Check if we've hit an expected join point or edge in the bytecode.
217 : // Leaving one control structure could place us at the edge of another,
218 : // thus |while| instead of |if| so we don't skip any opcodes.
219 19387 : MOZ_ASSERT_IF(!cfgStack_.empty(), cfgStack_.back().stopAt >= pc);
220 19387 : if (!cfgStack_.empty() && cfgStack_.back().stopAt == pc) {
221 1031 : ControlStatus status = processCfgStack();
222 1031 : if (status == ControlStatus::Error)
223 0 : return false;
224 1031 : if (status == ControlStatus::Abort) {
225 0 : aborted_ = true;
226 0 : return false;
227 : }
228 1031 : if (!current)
229 0 : return true;
230 1031 : continue;
231 : }
232 :
233 : // Some opcodes need to be handled early because they affect control
234 : // flow, terminating the current basic block and/or instructing the
235 : // traversal algorithm to continue from a new pc.
236 : //
237 : // (1) If the opcode does not affect control flow, then the opcode
238 : // is inspected and transformed to IR. This is the process_opcode
239 : // label.
240 : // (2) A loop could be detected via a forward GOTO. In this case,
241 : // we don't want to process the GOTO, but the following
242 : // instruction.
243 : // (3) A RETURN, STOP, BREAK, or CONTINUE may require processing the
244 : // CFG stack to terminate open branches.
245 : //
246 : // Similar to above, snooping control flow could land us at another
247 : // control flow point, so we iterate until it's time to inspect a real
248 : // opcode.
249 : ControlStatus status;
250 18356 : if ((status = snoopControlFlow(JSOp(*pc))) == ControlStatus::None)
251 17017 : break;
252 1339 : if (status == ControlStatus::Error)
253 0 : return false;
254 1339 : if (status == ControlStatus::Abort) {
255 0 : aborted_ = true;
256 0 : return false;
257 : }
258 1339 : if (!current)
259 150 : return true;
260 2220 : }
261 :
262 17017 : JSOp op = JSOp(*pc);
263 17017 : pc += CodeSpec[op].length;
264 17017 : }
265 :
266 : return true;
267 : }
268 :
269 : ControlFlowGenerator::ControlStatus
270 18356 : ControlFlowGenerator::snoopControlFlow(JSOp op)
271 : {
272 18356 : switch (op) {
273 : case JSOP_POP:
274 : case JSOP_NOP: {
275 1825 : jssrcnote* sn = GetSrcNote(gsn, script, pc);
276 1825 : return maybeLoop(op, sn);
277 : }
278 :
279 : case JSOP_RETURN:
280 : case JSOP_RETRVAL:
281 500 : return processReturn(op);
282 :
283 : case JSOP_THROW:
284 1 : return processThrow();
285 :
286 : case JSOP_GOTO:
287 : {
288 41 : jssrcnote* sn = GetSrcNote(gsn, script, pc);
289 41 : switch (sn ? SN_TYPE(sn) : SRC_NULL) {
290 : case SRC_BREAK:
291 : case SRC_BREAK2LABEL:
292 18 : return processBreak(op, sn);
293 :
294 : case SRC_CONTINUE:
295 11 : return processContinue(op);
296 :
297 : case SRC_SWITCHBREAK:
298 0 : return processSwitchBreak(op);
299 :
300 : case SRC_WHILE:
301 : case SRC_FOR_IN:
302 : case SRC_FOR_OF:
303 : // while (cond) { }
304 12 : return processWhileOrForInLoop(sn);
305 :
306 : default:
307 : // Hard assert for now - make an error later.
308 0 : MOZ_CRASH("unknown goto case");
309 : }
310 : break;
311 : }
312 :
313 : case JSOP_TABLESWITCH: {
314 44 : jssrcnote* sn = GetSrcNote(gsn, script, pc);
315 44 : return processTableSwitch(op, sn);
316 : }
317 :
318 : case JSOP_CONDSWITCH:
319 0 : return processCondSwitch();
320 :
321 : case JSOP_IFNE:
322 : // We should never reach an IFNE, it's a stopAt point, which will
323 : // trigger closing the loop.
324 0 : MOZ_CRASH("we should never reach an ifne!");
325 :
326 : case JSOP_IFEQ:
327 597 : return processIfStart(JSOP_IFEQ);
328 :
329 : case JSOP_AND:
330 : case JSOP_OR:
331 46 : return processAndOr(op);
332 :
333 : case JSOP_LABEL:
334 0 : return processLabel();
335 :
336 : case JSOP_TRY:
337 5 : return processTry();
338 :
339 : case JSOP_THROWMSG:
340 : // Not implemented yet.
341 0 : return ControlStatus::Abort;
342 :
343 : default:
344 15297 : break;
345 : }
346 15297 : return ControlStatus::None;
347 : }
348 :
349 : ControlFlowGenerator::ControlStatus
350 500 : ControlFlowGenerator::processReturn(JSOp op)
351 : {
352 500 : MOZ_ASSERT(op == JSOP_RETURN || op == JSOP_RETRVAL);
353 :
354 : CFGControlInstruction* ins;
355 500 : if (op == JSOP_RETURN)
356 478 : ins = CFGReturn::New(alloc());
357 : else
358 22 : ins = CFGRetRVal::New(alloc());
359 500 : endCurrentBlock(ins);
360 :
361 500 : return processControlEnd();
362 : }
363 :
364 : ControlFlowGenerator::ControlStatus
365 1 : ControlFlowGenerator::processThrow()
366 : {
367 1 : CFGThrow* ins = CFGThrow::New(alloc());
368 1 : endCurrentBlock(ins);
369 :
370 1 : return processControlEnd();
371 : }
372 :
373 : void
374 501 : ControlFlowGenerator::endCurrentBlock(CFGControlInstruction* ins)
375 : {
376 501 : current->setStopPc(pc);
377 501 : current->setStopIns(ins);
378 :
379 : // Make sure no one tries to use this block now.
380 501 : current = nullptr;
381 501 : }
382 :
383 : // Processes the top of the CFG stack. This is used from two places:
384 : // (1) processControlEnd(), whereby a break, continue, or return may interrupt
385 : // an in-progress CFG structure before reaching its actual termination
386 : // point in the bytecode.
387 : // (2) traverseBytecode(), whereby we reach the last instruction in a CFG
388 : // structure.
389 : ControlFlowGenerator::ControlStatus
390 1429 : ControlFlowGenerator::processCfgStack()
391 : {
392 1429 : ControlStatus status = processCfgEntry(cfgStack_.back());
393 :
394 : // If this terminated a CFG structure, act like processControlEnd() and
395 : // keep propagating upward.
396 1501 : while (status == ControlStatus::Ended) {
397 54 : popCfgStack();
398 54 : if (cfgStack_.empty())
399 18 : return status;
400 36 : status = processCfgEntry(cfgStack_.back());
401 : }
402 :
403 : // If some join took place, the current structure is finished.
404 1411 : if (status == ControlStatus::Joined)
405 755 : popCfgStack();
406 :
407 1411 : return status;
408 : }
409 :
410 : // Given that the current control flow structure has ended forcefully,
411 : // via a return, break, or continue (rather than joining), propagate the
412 : // termination up. For example, a return nested 5 loops deep may terminate
413 : // every outer loop at once, if there are no intervening conditionals:
414 : //
415 : // for (...) {
416 : // for (...) {
417 : // return x;
418 : // }
419 : // }
420 : //
421 : // If |current| is nullptr when this function returns, then there is no more
422 : // control flow to be processed.
423 : ControlFlowGenerator::ControlStatus
424 530 : ControlFlowGenerator::processControlEnd()
425 : {
426 530 : MOZ_ASSERT(!current);
427 :
428 530 : if (cfgStack_.empty()) {
429 : // If there is no more control flow to process, then this is the
430 : // last return in the function.
431 132 : return ControlStatus::Ended;
432 : }
433 :
434 398 : return processCfgStack();
435 : }
436 :
437 : ControlFlowGenerator::ControlStatus
438 1465 : ControlFlowGenerator::processCfgEntry(CFGState& state)
439 : {
440 1465 : switch (state.state) {
441 : case CFGState::IF_TRUE:
442 : case CFGState::IF_TRUE_EMPTY_ELSE:
443 427 : return processIfEnd(state);
444 :
445 : case CFGState::IF_ELSE_TRUE:
446 170 : return processIfElseTrueEnd(state);
447 :
448 : case CFGState::IF_ELSE_FALSE:
449 170 : return processIfElseFalseEnd(state);
450 :
451 : case CFGState::DO_WHILE_LOOP_BODY:
452 0 : return processDoWhileBodyEnd(state);
453 :
454 : case CFGState::DO_WHILE_LOOP_COND:
455 0 : return processDoWhileCondEnd(state);
456 :
457 : case CFGState::WHILE_LOOP_COND:
458 12 : return processWhileCondEnd(state);
459 :
460 : case CFGState::WHILE_LOOP_BODY:
461 12 : return processWhileBodyEnd(state);
462 :
463 : case CFGState::FOR_LOOP_COND:
464 105 : return processForCondEnd(state);
465 :
466 : case CFGState::FOR_LOOP_BODY:
467 105 : return processForBodyEnd(state);
468 :
469 : case CFGState::FOR_LOOP_UPDATE:
470 105 : return processForUpdateEnd(state);
471 :
472 : case CFGState::TABLE_SWITCH:
473 308 : return processNextTableSwitchCase(state);
474 :
475 : case CFGState::COND_SWITCH_CASE:
476 0 : return processCondSwitchCase(state);
477 :
478 : case CFGState::COND_SWITCH_BODY:
479 0 : return processCondSwitchBody(state);
480 :
481 : case CFGState::AND_OR:
482 46 : return processAndOrEnd(state);
483 :
484 : case CFGState::LABEL:
485 0 : return processLabelEnd(state);
486 :
487 : case CFGState::TRY:
488 5 : return processTryEnd(state);
489 :
490 : default:
491 0 : MOZ_CRASH("unknown cfgstate");
492 : }
493 : }
494 :
495 : void
496 809 : ControlFlowGenerator::popCfgStack()
497 : {
498 809 : if (cfgStack_.back().isLoop())
499 117 : loops_.popBack();
500 809 : if (cfgStack_.back().state == CFGState::LABEL)
501 0 : labels_.popBack();
502 809 : cfgStack_.popBack();
503 809 : }
504 :
505 : ControlFlowGenerator::ControlStatus
506 0 : ControlFlowGenerator::processLabelEnd(CFGState& state)
507 : {
508 0 : MOZ_ASSERT(state.state == CFGState::LABEL);
509 :
510 : // If there are no breaks and no current, controlflow is terminated.
511 0 : if (!state.label.breaks && !current)
512 0 : return ControlStatus::Ended;
513 :
514 : // If there are no breaks to this label, there's nothing to do.
515 0 : if (!state.label.breaks)
516 0 : return ControlStatus::Joined;
517 :
518 0 : CFGBlock* successor = createBreakCatchBlock(state.label.breaks, state.stopAt);
519 0 : if (!successor)
520 0 : return ControlStatus::Error;
521 :
522 0 : if (current) {
523 0 : current->setStopIns(CFGGoto::New(alloc(), successor));
524 0 : current->setStopPc(pc);
525 : }
526 :
527 0 : current = successor;
528 0 : pc = successor->startPc();
529 :
530 0 : if (!addBlock(successor))
531 0 : return ControlStatus::Error;
532 :
533 0 : return ControlStatus::Joined;
534 : }
535 :
536 : ControlFlowGenerator::ControlStatus
537 5 : ControlFlowGenerator::processTry()
538 : {
539 5 : MOZ_ASSERT(JSOp(*pc) == JSOP_TRY);
540 :
541 : // Try-finally is not yet supported.
542 5 : if (analysis_.hasTryFinally())
543 0 : return ControlStatus::Abort;
544 :
545 5 : jssrcnote* sn = GetSrcNote(gsn, script, pc);
546 5 : MOZ_ASSERT(SN_TYPE(sn) == SRC_TRY);
547 :
548 : // Get the pc of the last instruction in the try block. It's a JSOP_GOTO to
549 : // jump over the catch block.
550 5 : jsbytecode* endpc = pc + GetSrcNoteOffset(sn, 0);
551 5 : MOZ_ASSERT(JSOp(*endpc) == JSOP_GOTO);
552 5 : MOZ_ASSERT(GetJumpOffset(endpc) > 0);
553 :
554 5 : jsbytecode* afterTry = endpc + GetJumpOffset(endpc);
555 :
556 : // If controlflow in the try body is terminated (by a return or throw
557 : // statement), the code after the try-statement may still be reachable
558 : // via the catch block (which we don't compile) and OSR can enter it.
559 : // For example:
560 : //
561 : // try {
562 : // throw 3;
563 : // } catch(e) { }
564 : //
565 : // for (var i=0; i<1000; i++) {}
566 : //
567 : // To handle this, we create two blocks: one for the try block and one
568 : // for the code following the try-catch statement.
569 : //
570 : // If the code after the try block is unreachable (control flow in both the
571 : // try and catch blocks is terminated), only create the try block, to avoid
572 : // parsing unreachable code.
573 :
574 5 : CFGBlock* tryBlock = CFGBlock::New(alloc(), GetNextPc(pc));
575 :
576 : CFGBlock* successor;
577 5 : if (analysis_.maybeInfo(afterTry)) {
578 5 : successor = CFGBlock::New(alloc(), afterTry);
579 5 : current->setStopIns(CFGTry::New(alloc(), tryBlock, endpc, successor));
580 : } else {
581 0 : successor = nullptr;
582 0 : current->setStopIns(CFGTry::New(alloc(), tryBlock, endpc));
583 : }
584 5 : current->setStopPc(pc);
585 :
586 5 : if (!cfgStack_.append(CFGState::Try(endpc, successor)))
587 0 : return ControlStatus::Error;
588 :
589 5 : current = tryBlock;
590 5 : pc = current->startPc();
591 :
592 5 : if (!addBlock(current))
593 0 : return ControlStatus::Error;
594 :
595 5 : return ControlStatus::Jumped;
596 : }
597 :
598 : ControlFlowGenerator::ControlStatus
599 5 : ControlFlowGenerator::processTryEnd(CFGState& state)
600 : {
601 5 : MOZ_ASSERT(state.state == CFGState::TRY);
602 :
603 5 : if (!state.try_.successor) {
604 0 : MOZ_ASSERT(!current);
605 0 : return ControlStatus::Ended;
606 : }
607 :
608 5 : if (current) {
609 5 : current->setStopIns(CFGGoto::New(alloc(), state.try_.successor));
610 5 : current->setStopPc(pc);
611 : }
612 :
613 : // Start parsing the code after this try-catch statement.
614 5 : current = state.try_.successor;
615 5 : pc = current->startPc();
616 :
617 5 : if (!addBlock(current))
618 0 : return ControlStatus::Error;
619 :
620 5 : return ControlStatus::Joined;
621 : }
622 :
623 : ControlFlowGenerator::ControlStatus
624 427 : ControlFlowGenerator::processIfEnd(CFGState& state)
625 : {
626 427 : if (current) {
627 : // Here, the false block is the join point. Create an edge from the
628 : // current block to the false block. Note that a RETURN opcode
629 : // could have already ended the block.
630 329 : current->setStopIns(CFGGoto::New(alloc(), state.branch.ifFalse));
631 329 : current->setStopPc(pc);
632 : }
633 :
634 427 : current = state.branch.ifFalse;
635 427 : pc = current->startPc();
636 :
637 427 : if (!addBlock(current))
638 0 : return ControlStatus::Error;
639 :
640 427 : return ControlStatus::Joined;
641 : }
642 :
643 : ControlFlowGenerator::ControlStatus
644 170 : ControlFlowGenerator::processIfElseTrueEnd(CFGState& state)
645 : {
646 : // We've reached the end of the true branch of an if-else. Don't
647 : // create an edge yet, just transition to parsing the false branch.
648 170 : state.state = CFGState::IF_ELSE_FALSE;
649 170 : state.branch.ifTrue = current;
650 170 : state.stopAt = state.branch.falseEnd;
651 :
652 170 : if (current)
653 152 : current->setStopPc(pc);
654 :
655 170 : current = state.branch.ifFalse;
656 170 : pc = current->startPc();
657 :
658 170 : if (!addBlock(current))
659 0 : return ControlStatus::Error;
660 :
661 170 : return ControlStatus::Jumped;
662 : }
663 :
664 : ControlFlowGenerator::ControlStatus
665 170 : ControlFlowGenerator::processIfElseFalseEnd(CFGState& state)
666 : {
667 : // Update the state to have the latest block from the false path.
668 170 : state.branch.ifFalse = current;
669 170 : if (current)
670 152 : current->setStopPc(pc);
671 :
672 : // To create the join node, we need an incoming edge that has not been
673 : // terminated yet.
674 170 : CFGBlock* pred = state.branch.ifTrue
675 170 : ? state.branch.ifTrue
676 170 : : state.branch.ifFalse;
677 170 : CFGBlock* other = (pred == state.branch.ifTrue)
678 170 : ? state.branch.ifFalse
679 170 : : state.branch.ifTrue;
680 :
681 170 : if (!pred)
682 18 : return ControlStatus::Ended;
683 :
684 : // Create a new block to represent the join.
685 152 : CFGBlock* join = CFGBlock::New(alloc(), state.branch.falseEnd);
686 :
687 : // Create edges from the true and false blocks as needed.
688 152 : pred->setStopIns(CFGGoto::New(alloc(), join));
689 :
690 152 : if (other)
691 152 : other->setStopIns(CFGGoto::New(alloc(), join));
692 :
693 : // Ignore unreachable remainder of false block if existent.
694 152 : current = join;
695 152 : pc = current->startPc();
696 :
697 152 : if (!addBlock(current))
698 0 : return ControlStatus::Error;
699 :
700 152 : return ControlStatus::Joined;
701 : }
702 :
703 : CFGBlock*
704 16 : ControlFlowGenerator::createBreakCatchBlock(DeferredEdge* edge, jsbytecode* pc)
705 : {
706 : // Create block, using the first break statement as predecessor
707 16 : CFGBlock* successor = CFGBlock::New(alloc(), pc);
708 :
709 : // Finish up remaining breaks.
710 52 : while (edge) {
711 18 : if (!alloc().ensureBallast())
712 0 : return nullptr;
713 :
714 18 : CFGGoto* brk = CFGGoto::New(alloc(), successor);
715 18 : edge->block->setStopIns(brk);
716 18 : edge = edge->next;
717 : }
718 :
719 16 : return successor;
720 : }
721 :
722 : ControlFlowGenerator::ControlStatus
723 0 : ControlFlowGenerator::processDoWhileBodyEnd(CFGState& state)
724 : {
725 0 : if (!processDeferredContinues(state))
726 0 : return ControlStatus::Error;
727 :
728 : // No current means control flow cannot reach the condition, so this will
729 : // never loop.
730 0 : if (!current)
731 0 : return processBrokenLoop(state);
732 :
733 0 : CFGBlock* header = CFGBlock::New(alloc(), state.loop.updatepc);
734 0 : current->setStopIns(CFGGoto::New(alloc(), header));
735 0 : current->setStopPc(pc);
736 :
737 0 : state.state = CFGState::DO_WHILE_LOOP_COND;
738 0 : state.stopAt = state.loop.updateEnd;
739 :
740 0 : current = header;
741 0 : pc = header->startPc();
742 :
743 0 : if (!addBlock(current))
744 0 : return ControlStatus::Error;
745 :
746 0 : return ControlStatus::Jumped;
747 : }
748 :
749 : ControlFlowGenerator::ControlStatus
750 0 : ControlFlowGenerator::processDoWhileCondEnd(CFGState& state)
751 : {
752 0 : MOZ_ASSERT(JSOp(*pc) == JSOP_IFNE);
753 :
754 : // We're guaranteed a |current|, it's impossible to break or return from
755 : // inside the conditional expression.
756 0 : MOZ_ASSERT(current);
757 :
758 : // Create the successor block.
759 0 : CFGBlock* successor = CFGBlock::New(alloc(), GetNextPc(pc));
760 :
761 0 : CFGLoopEntry* entry = state.loop.entry->stopIns()->toLoopEntry();
762 0 : entry->setLoopStopPc(pc);
763 :
764 : // Create backedge with pc at start of loop to make sure we capture the
765 : // right stack.
766 0 : CFGBlock* backEdge = CFGBlock::New(alloc(), entry->successor()->startPc());
767 0 : backEdge->setStopIns(CFGBackEdge::New(alloc(), entry->successor()));
768 0 : backEdge->setStopPc(entry->successor()->startPc());
769 :
770 0 : if (!addBlock(backEdge))
771 0 : return ControlStatus::Error;
772 :
773 : // Create the test instruction and end the current block.
774 0 : CFGTest* test = CFGTest::New(alloc(), backEdge, successor);
775 0 : current->setStopIns(test);
776 0 : current->setStopPc(pc);
777 0 : return finishLoop(state, successor);
778 : }
779 :
780 : ControlFlowGenerator::ControlStatus
781 12 : ControlFlowGenerator::processWhileCondEnd(CFGState& state)
782 : {
783 12 : MOZ_ASSERT(JSOp(*pc) == JSOP_IFNE || JSOp(*pc) == JSOP_IFEQ);
784 :
785 : // Create the body and successor blocks.
786 12 : CFGBlock* body = CFGBlock::New(alloc(), state.loop.bodyStart);
787 12 : state.loop.successor = CFGBlock::New(alloc(), state.loop.exitpc);
788 12 : if (!body || !state.loop.successor)
789 0 : return ControlStatus::Error;
790 :
791 : CFGTest* test;
792 12 : if (JSOp(*pc) == JSOP_IFNE)
793 9 : test = CFGTest::New(alloc(), body, state.loop.successor);
794 : else
795 3 : test = CFGTest::New(alloc(), state.loop.successor, body);
796 12 : current->setStopIns(test);
797 12 : current->setStopPc(pc);
798 :
799 12 : state.state = CFGState::WHILE_LOOP_BODY;
800 12 : state.stopAt = state.loop.bodyEnd;
801 :
802 12 : current = body;
803 12 : pc = body->startPc();
804 :
805 12 : if (!addBlock(current))
806 0 : return ControlStatus::Error;
807 :
808 12 : return ControlStatus::Jumped;
809 : }
810 :
811 : ControlFlowGenerator::ControlStatus
812 12 : ControlFlowGenerator::processWhileBodyEnd(CFGState& state)
813 : {
814 12 : if (!processDeferredContinues(state))
815 0 : return ControlStatus::Error;
816 :
817 12 : if (!current)
818 0 : return processBrokenLoop(state);
819 :
820 12 : CFGLoopEntry* entry = state.loop.entry->stopIns()->toLoopEntry();
821 12 : entry->setLoopStopPc(pc);
822 :
823 12 : current->setStopIns(CFGBackEdge::New(alloc(), entry->successor()));
824 12 : if (pc != current->startPc()) {
825 12 : current->setStopPc(pc);
826 : } else {
827 : // If the block is empty update the pc to the start of loop to make
828 : // sure we capture the right stack.
829 0 : current->setStartPc(entry->successor()->startPc());
830 0 : current->setStopPc(entry->successor()->startPc());
831 : }
832 12 : return finishLoop(state, state.loop.successor);
833 : }
834 :
835 : ControlFlowGenerator::ControlStatus
836 105 : ControlFlowGenerator::processForCondEnd(CFGState& state)
837 : {
838 105 : MOZ_ASSERT(JSOp(*pc) == JSOP_IFNE);
839 :
840 : // Create the body and successor blocks.
841 105 : CFGBlock* body = CFGBlock::New(alloc(), state.loop.bodyStart);
842 105 : state.loop.successor = CFGBlock::New(alloc(), state.loop.exitpc);
843 :
844 105 : CFGTest* test = CFGTest::New(alloc(), body, state.loop.successor);
845 105 : current->setStopIns(test);
846 105 : current->setStopPc(pc);
847 :
848 105 : state.state = CFGState::FOR_LOOP_BODY;
849 105 : state.stopAt = state.loop.bodyEnd;
850 :
851 105 : current = body;
852 105 : pc = body->startPc();
853 :
854 105 : if (!addBlock(current))
855 0 : return ControlStatus::Error;
856 :
857 105 : return ControlStatus::Jumped;
858 : }
859 :
860 : ControlFlowGenerator::ControlStatus
861 105 : ControlFlowGenerator::processForBodyEnd(CFGState& state)
862 : {
863 105 : if (!processDeferredContinues(state))
864 0 : return ControlStatus::Error;
865 :
866 : // If there is no updatepc, just go right to processing what would be the
867 : // end of the update clause. Otherwise, |current| might be nullptr; if this is
868 : // the case, the update is unreachable anyway.
869 105 : if (!state.loop.updatepc || !current)
870 0 : return processForUpdateEnd(state);
871 :
872 : //MOZ_ASSERT(pc == state.loop.updatepc);
873 :
874 105 : if (state.loop.updatepc != pc) {
875 0 : CFGBlock* next = CFGBlock::New(alloc(), state.loop.updatepc);
876 0 : current->setStopIns(CFGGoto::New(alloc(), next));
877 0 : current->setStopPc(pc);
878 0 : current = next;
879 :
880 0 : if (!addBlock(current))
881 0 : return ControlStatus::Error;
882 : }
883 :
884 105 : pc = state.loop.updatepc;
885 :
886 105 : state.state = CFGState::FOR_LOOP_UPDATE;
887 105 : state.stopAt = state.loop.updateEnd;
888 105 : return ControlStatus::Jumped;
889 : }
890 :
891 : ControlFlowGenerator::ControlStatus
892 105 : ControlFlowGenerator::processForUpdateEnd(CFGState& state)
893 : {
894 : // If there is no current, we couldn't reach the loop edge and there was no
895 : // update clause.
896 105 : if (!current)
897 0 : return processBrokenLoop(state);
898 :
899 105 : CFGLoopEntry* entry = state.loop.entry->stopIns()->toLoopEntry();
900 105 : entry->setLoopStopPc(pc);
901 :
902 105 : current->setStopIns(CFGBackEdge::New(alloc(), entry->successor()));
903 105 : if (pc != current->startPc()) {
904 105 : current->setStopPc(pc);
905 : } else {
906 : // If the block is empty update the pc to the start of loop to make
907 : // sure we capture the right stack.
908 0 : current->setStartPc(entry->successor()->startPc());
909 0 : current->setStopPc(entry->successor()->startPc());
910 : }
911 105 : return finishLoop(state, state.loop.successor);
912 : }
913 :
914 : ControlFlowGenerator::ControlStatus
915 12 : ControlFlowGenerator::processWhileOrForInLoop(jssrcnote* sn)
916 : {
917 : // while (cond) { } loops have the following structure:
918 : // GOTO cond ; SRC_WHILE (offset to IFNE)
919 : // LOOPHEAD
920 : // ...
921 : // cond:
922 : // LOOPENTRY
923 : // ...
924 : // IFNE ; goes to LOOPHEAD
925 : // for (x in y) { } loops are similar; the cond will be a MOREITER.
926 12 : MOZ_ASSERT(SN_TYPE(sn) == SRC_FOR_OF || SN_TYPE(sn) == SRC_FOR_IN || SN_TYPE(sn) == SRC_WHILE);
927 12 : int ifneOffset = GetSrcNoteOffset(sn, 0);
928 12 : jsbytecode* ifne = pc + ifneOffset;
929 12 : MOZ_ASSERT(ifne > pc);
930 :
931 : // Verify that the IFNE goes back to a loophead op.
932 12 : MOZ_ASSERT(JSOp(*GetNextPc(pc)) == JSOP_LOOPHEAD);
933 12 : MOZ_ASSERT(GetNextPc(pc) == ifne + GetJumpOffset(ifne));
934 :
935 12 : jsbytecode* loopEntry = pc + GetJumpOffset(pc);
936 :
937 : size_t stackPhiCount;
938 12 : if (SN_TYPE(sn) == SRC_FOR_OF)
939 3 : stackPhiCount = 2;
940 9 : else if (SN_TYPE(sn) == SRC_FOR_IN)
941 0 : stackPhiCount = 1;
942 : else
943 9 : stackPhiCount = 0;
944 :
945 : // Skip past the JSOP_LOOPHEAD for the body start.
946 12 : jsbytecode* loopHead = GetNextPc(pc);
947 12 : jsbytecode* bodyStart = GetNextPc(loopHead);
948 12 : jsbytecode* bodyEnd = pc + GetJumpOffset(pc);
949 12 : jsbytecode* exitpc = GetNextPc(ifne);
950 12 : jsbytecode* continuepc = pc;
951 :
952 12 : CFGBlock* header = CFGBlock::New(alloc(), GetNextPc(loopEntry));
953 :
954 12 : CFGLoopEntry* ins = CFGLoopEntry::New(alloc(), header, stackPhiCount);
955 12 : if (LoopEntryCanIonOsr(loopEntry))
956 12 : ins->setCanOsr();
957 :
958 12 : current->setStopIns(ins);
959 12 : current->setStopPc(pc);
960 :
961 12 : if (!pushLoop(CFGState::WHILE_LOOP_COND, ifne, current,
962 : loopHead, bodyEnd, bodyStart, bodyEnd, exitpc, continuepc))
963 : {
964 0 : return ControlStatus::Error;
965 : }
966 :
967 : // Parse the condition first.
968 12 : current = header;
969 12 : pc = header->startPc();
970 :
971 12 : if (!addBlock(current))
972 0 : return ControlStatus::Error;
973 :
974 12 : return ControlStatus::Jumped;
975 : }
976 :
977 : ControlFlowGenerator::ControlStatus
978 0 : ControlFlowGenerator::processBrokenLoop(CFGState& state)
979 : {
980 0 : MOZ_ASSERT(!current);
981 :
982 : {
983 0 : state.loop.entry->setStopIns(
984 0 : CFGGoto::New(alloc(), state.loop.entry->stopIns()->toLoopEntry()->successor()));
985 : }
986 :
987 : // If the loop started with a condition (while/for) then even if the
988 : // structure never actually loops, the condition itself can still fail and
989 : // thus we must resume at the successor, if one exists.
990 0 : current = state.loop.successor;
991 0 : if (current) {
992 0 : if (!addBlock(current))
993 0 : return ControlStatus::Error;
994 : }
995 :
996 : // Join the breaks together and continue parsing.
997 0 : if (state.loop.breaks) {
998 0 : CFGBlock* block = createBreakCatchBlock(state.loop.breaks, state.loop.exitpc);
999 0 : if (!block)
1000 0 : return ControlStatus::Error;
1001 :
1002 0 : if (current) {
1003 0 : current->setStopIns(CFGGoto::New(alloc(), block));
1004 0 : current->setStopPc(current->startPc());
1005 : }
1006 :
1007 0 : current = block;
1008 :
1009 0 : if (!addBlock(current))
1010 0 : return ControlStatus::Error;
1011 : }
1012 :
1013 : // If the loop is not gated on a condition, and has only returns, we'll
1014 : // reach this case. For example:
1015 : // do { ... return; } while ();
1016 0 : if (!current)
1017 0 : return ControlStatus::Ended;
1018 :
1019 : // Otherwise, the loop is gated on a condition and/or has breaks so keep
1020 : // parsing at the successor.
1021 0 : pc = current->startPc();
1022 0 : return ControlStatus::Joined;
1023 : }
1024 :
1025 : ControlFlowGenerator::ControlStatus
1026 117 : ControlFlowGenerator::finishLoop(CFGState& state, CFGBlock* successor)
1027 : {
1028 117 : MOZ_ASSERT(current);
1029 :
1030 117 : if (state.loop.breaks) {
1031 16 : if (successor) {
1032 16 : if (!addBlock(successor))
1033 0 : return ControlStatus::Error;
1034 : }
1035 :
1036 : // Create a catch block to join all break exits.
1037 16 : CFGBlock* block = createBreakCatchBlock(state.loop.breaks, state.loop.exitpc);
1038 16 : if (!block)
1039 0 : return ControlStatus::Error;
1040 :
1041 16 : if (successor) {
1042 : // Finally, create an unconditional edge from the successor to the
1043 : // catch block.
1044 16 : successor->setStopIns(CFGGoto::New(alloc(), block));
1045 16 : successor->setStopPc(successor->startPc());
1046 : }
1047 16 : successor = block;
1048 : }
1049 :
1050 : // An infinite loop (for (;;) { }) will not have a successor.
1051 117 : if (!successor) {
1052 0 : current = nullptr;
1053 0 : return ControlStatus::Ended;
1054 : }
1055 :
1056 117 : current = successor;
1057 117 : pc = current->startPc();
1058 :
1059 117 : if (!addBlock(current))
1060 0 : return ControlStatus::Error;
1061 :
1062 117 : return ControlStatus::Joined;
1063 : }
1064 :
1065 : bool
1066 117 : ControlFlowGenerator::processDeferredContinues(CFGState& state)
1067 : {
1068 : // If there are any continues for this loop, and there is an update block,
1069 : // then we need to create a new basic block to house the update.
1070 117 : if (state.loop.continues) {
1071 1 : DeferredEdge* edge = state.loop.continues;
1072 :
1073 1 : CFGBlock* update = CFGBlock::New(alloc(), pc);
1074 :
1075 1 : if (current) {
1076 1 : current->setStopIns(CFGGoto::New(alloc(), update));
1077 1 : current->setStopPc(pc);
1078 : }
1079 :
1080 : // Remaining edges
1081 23 : while (edge) {
1082 11 : if (!alloc().ensureBallast())
1083 0 : return false;
1084 11 : edge->block->setStopIns(CFGGoto::New(alloc(), update));
1085 11 : edge = edge->next;
1086 : }
1087 1 : state.loop.continues = nullptr;
1088 :
1089 1 : current = update;
1090 1 : if (!addBlock(current))
1091 0 : return false;
1092 : }
1093 :
1094 117 : return true;
1095 : }
1096 :
1097 : ControlFlowGenerator::ControlStatus
1098 0 : ControlFlowGenerator::processCondSwitch()
1099 : {
1100 : // CondSwitch op looks as follows:
1101 : // condswitch [length +exit_pc; first case offset +next-case ]
1102 : // {
1103 : // {
1104 : // ... any code ...
1105 : // case (+jump) [pcdelta offset +next-case]
1106 : // }+
1107 : // default (+jump)
1108 : // ... jump targets ...
1109 : // }
1110 : //
1111 : // The default case is always emitted even if there is no default case in
1112 : // the source. The last case statement pcdelta source note might have a 0
1113 : // offset on the last case (not all the time).
1114 : //
1115 : // A conditional evaluate the condition of each case and compare it to the
1116 : // switch value with a strict equality. Cases conditions are iterated
1117 : // linearly until one is matching. If one case succeeds, the flow jumps into
1118 : // the corresponding body block. The body block might alias others and
1119 : // might continue in the next body block if the body is not terminated with
1120 : // a break.
1121 : //
1122 : // Algorithm:
1123 : // 1/ Loop over the case chain to reach the default target
1124 : // & Estimate the number of uniq bodies.
1125 : // 2/ Generate code for all cases (see processCondSwitchCase).
1126 : // 3/ Generate code for all bodies (see processCondSwitchBody).
1127 :
1128 0 : MOZ_ASSERT(JSOp(*pc) == JSOP_CONDSWITCH);
1129 0 : jssrcnote* sn = GetSrcNote(gsn, script, pc);
1130 0 : MOZ_ASSERT(SN_TYPE(sn) == SRC_CONDSWITCH);
1131 :
1132 : // Get the exit pc
1133 0 : jsbytecode* exitpc = pc + GetSrcNoteOffset(sn, 0);
1134 0 : jsbytecode* firstCase = pc + GetSrcNoteOffset(sn, 1);
1135 :
1136 : // Iterate all cases in the conditional switch.
1137 : // - Stop at the default case. (always emitted after the last case)
1138 : // - Estimate the number of uniq bodies. This estimation might be off by 1
1139 : // if the default body alias a case body.
1140 0 : jsbytecode* curCase = firstCase;
1141 0 : jsbytecode* lastTarget = GetJumpOffset(curCase) + curCase;
1142 0 : size_t nbBodies = 1; // default target and the first body.
1143 :
1144 0 : MOZ_ASSERT(pc < curCase && curCase <= exitpc);
1145 0 : while (JSOp(*curCase) == JSOP_CASE) {
1146 : // Fetch the next case.
1147 0 : jssrcnote* caseSn = GetSrcNote(gsn, script, curCase);
1148 0 : MOZ_ASSERT(caseSn && SN_TYPE(caseSn) == SRC_NEXTCASE);
1149 0 : ptrdiff_t off = GetSrcNoteOffset(caseSn, 0);
1150 0 : MOZ_ASSERT_IF(off == 0, JSOp(*GetNextPc(curCase)) == JSOP_JUMPTARGET);
1151 0 : curCase = off ? curCase + off : GetNextPc(GetNextPc(curCase));
1152 0 : MOZ_ASSERT(pc < curCase && curCase <= exitpc);
1153 :
1154 : // Count non-aliased cases.
1155 0 : jsbytecode* curTarget = GetJumpOffset(curCase) + curCase;
1156 0 : if (lastTarget < curTarget)
1157 0 : nbBodies++;
1158 0 : lastTarget = curTarget;
1159 : }
1160 :
1161 : // The current case now be the default case which jump to the body of the
1162 : // default case, which might be behind the last target.
1163 0 : MOZ_ASSERT(JSOp(*curCase) == JSOP_DEFAULT);
1164 0 : jsbytecode* defaultTarget = GetJumpOffset(curCase) + curCase;
1165 0 : MOZ_ASSERT(curCase < defaultTarget && defaultTarget <= exitpc);
1166 :
1167 : // Iterate over all cases again to find the position of the default block.
1168 0 : curCase = firstCase;
1169 0 : lastTarget = nullptr;
1170 0 : size_t defaultIdx = 0;
1171 0 : while (JSOp(*curCase) == JSOP_CASE) {
1172 0 : jsbytecode* curTarget = GetJumpOffset(curCase) + curCase;
1173 0 : if (lastTarget < defaultTarget && defaultTarget <= curTarget) {
1174 0 : if (defaultTarget < curTarget)
1175 0 : nbBodies++;
1176 0 : break;
1177 : }
1178 0 : if (lastTarget < curTarget)
1179 0 : defaultIdx++;
1180 :
1181 0 : jssrcnote* caseSn = GetSrcNote(gsn, script, curCase);
1182 0 : ptrdiff_t off = GetSrcNoteOffset(caseSn, 0);
1183 0 : curCase = off ? curCase + off : GetNextPc(GetNextPc(curCase));
1184 0 : lastTarget = curTarget;
1185 : }
1186 :
1187 : // Allocate the current graph state.
1188 0 : CFGState state = CFGState::CondSwitch(alloc(), exitpc, defaultTarget);
1189 0 : if (!state.switch_.bodies || !state.switch_.bodies->init(alloc(), nbBodies))
1190 0 : return ControlStatus::Error;
1191 0 : state.switch_.defaultIdx = defaultIdx;
1192 :
1193 : // Create the default case already.
1194 0 : FixedList<CFGBlock*>& bodies = *state.switch_.bodies;
1195 0 : bodies[state.switch_.defaultIdx] = CFGBlock::New(alloc(), defaultTarget);
1196 :
1197 : // Skip default case.
1198 0 : if (state.switch_.defaultIdx == 0)
1199 0 : state.switch_.currentIdx++;
1200 :
1201 : // We loop on case conditions with processCondSwitchCase.
1202 0 : MOZ_ASSERT(JSOp(*firstCase) == JSOP_CASE);
1203 0 : state.stopAt = firstCase;
1204 0 : state.state = CFGState::COND_SWITCH_CASE;
1205 :
1206 0 : if (!cfgStack_.append(state))
1207 0 : return ControlStatus::Error;
1208 :
1209 0 : jsbytecode* nextPc = GetNextPc(pc);
1210 0 : CFGBlock* next = CFGBlock::New(alloc(), nextPc);
1211 :
1212 0 : current->setStopIns(CFGGoto::New(alloc(), next));
1213 0 : current->setStopPc(pc);
1214 :
1215 0 : current = next;
1216 0 : pc = current->startPc();
1217 :
1218 0 : if (!addBlock(current))
1219 0 : return ControlStatus::Error;
1220 :
1221 0 : return ControlStatus::Jumped;
1222 : }
1223 :
1224 : ControlFlowGenerator::ControlStatus
1225 0 : ControlFlowGenerator::processCondSwitchCase(CFGState& state)
1226 : {
1227 0 : MOZ_ASSERT(state.state == CFGState::COND_SWITCH_CASE);
1228 0 : MOZ_ASSERT(!state.switch_.breaks);
1229 0 : MOZ_ASSERT(current);
1230 0 : MOZ_ASSERT(JSOp(*pc) == JSOP_CASE);
1231 0 : FixedList<CFGBlock*>& bodies = *state.switch_.bodies;
1232 0 : uint32_t& currentIdx = state.switch_.currentIdx;
1233 :
1234 0 : jsbytecode* lastTarget = currentIdx ? bodies[currentIdx - 1]->startPc() : nullptr;
1235 :
1236 : // Fetch the following case in which we will continue.
1237 0 : jssrcnote* sn = GetSrcNote(gsn, script, pc);
1238 0 : ptrdiff_t off = GetSrcNoteOffset(sn, 0);
1239 0 : MOZ_ASSERT_IF(off == 0, JSOp(*GetNextPc(pc)) == JSOP_JUMPTARGET);
1240 0 : jsbytecode* casePc = off ? pc + off : GetNextPc(GetNextPc(pc));
1241 0 : bool nextIsDefault = JSOp(*casePc) == JSOP_DEFAULT;
1242 0 : MOZ_ASSERT(JSOp(*casePc) == JSOP_CASE || nextIsDefault);
1243 :
1244 : // Allocate the block of the matching case.
1245 0 : jsbytecode* bodyTarget = pc + GetJumpOffset(pc);
1246 0 : CFGBlock* bodyBlock = nullptr;
1247 0 : if (lastTarget < bodyTarget) {
1248 :
1249 : // Skip default case.
1250 0 : if (currentIdx == state.switch_.defaultIdx) {
1251 0 : currentIdx++;
1252 0 : lastTarget = bodies[currentIdx - 1]->startPc();
1253 0 : if (lastTarget < bodyTarget) {
1254 0 : bodyBlock = CFGBlock::New(alloc(), bodyTarget);
1255 0 : bodies[currentIdx++] = bodyBlock;
1256 : } else {
1257 : // This body alias the previous one.
1258 0 : MOZ_ASSERT(lastTarget == bodyTarget);
1259 0 : MOZ_ASSERT(currentIdx > 0);
1260 0 : bodyBlock = bodies[currentIdx - 1];
1261 : }
1262 : } else {
1263 0 : bodyBlock = CFGBlock::New(alloc(), bodyTarget);
1264 0 : bodies[currentIdx++] = bodyBlock;
1265 : }
1266 :
1267 : } else {
1268 : // This body alias the previous one.
1269 0 : MOZ_ASSERT(lastTarget == bodyTarget);
1270 0 : MOZ_ASSERT(currentIdx > 0);
1271 0 : bodyBlock = bodies[currentIdx - 1];
1272 : }
1273 :
1274 0 : CFGBlock* emptyBlock = CFGBlock::New(alloc(), bodyBlock->startPc());
1275 0 : emptyBlock->setStopIns(CFGGoto::New(alloc(), bodyBlock));
1276 0 : emptyBlock->setStopPc(bodyBlock->startPc());
1277 0 : if (!addBlock(emptyBlock))
1278 0 : return ControlStatus::Error;
1279 :
1280 0 : if (nextIsDefault) {
1281 0 : CFGBlock* defaultBlock = bodies[state.switch_.defaultIdx];
1282 :
1283 0 : CFGBlock* emptyBlock2 = CFGBlock::New(alloc(), defaultBlock->startPc());
1284 0 : emptyBlock2->setStopIns(CFGGoto::New(alloc(), defaultBlock));
1285 0 : emptyBlock2->setStopPc(defaultBlock->startPc());
1286 0 : if (!addBlock(emptyBlock2))
1287 0 : return ControlStatus::Error;
1288 :
1289 0 : current->setStopIns(CFGCompare::NewFalseBranchIsDefault(alloc(), emptyBlock, emptyBlock2));
1290 0 : current->setStopPc(pc);
1291 :
1292 0 : return processCondSwitchDefault(state);
1293 : }
1294 :
1295 0 : CFGBlock* nextBlock = CFGBlock::New(alloc(), GetNextPc(pc));
1296 0 : current->setStopIns(CFGCompare::NewFalseBranchIsNextCompare(alloc(), emptyBlock, nextBlock));
1297 0 : current->setStopPc(pc);
1298 :
1299 : // Continue until the case condition.
1300 0 : current = nextBlock;
1301 0 : pc = current->startPc();
1302 0 : state.stopAt = casePc;
1303 :
1304 0 : if (!addBlock(current))
1305 0 : return ControlStatus::Error;
1306 :
1307 0 : return ControlStatus::Jumped;
1308 : }
1309 :
1310 : ControlFlowGenerator::ControlStatus
1311 0 : ControlFlowGenerator::processCondSwitchDefault(CFGState& state)
1312 : {
1313 0 : uint32_t& currentIdx = state.switch_.currentIdx;
1314 :
1315 : // The last case condition is finished. Loop in processCondSwitchBody,
1316 : // with potential stops in processSwitchBreak.
1317 :
1318 : #ifdef DEBUG
1319 : // Test that we calculated the number of bodies correctly.
1320 0 : FixedList<CFGBlock*>& bodies = *state.switch_.bodies;
1321 0 : MOZ_ASSERT(state.switch_.currentIdx == bodies.length() ||
1322 : state.switch_.defaultIdx + 1 == bodies.length());
1323 : #endif
1324 :
1325 : // Handle break statements in processSwitchBreak while processing
1326 : // bodies.
1327 0 : ControlFlowInfo breakInfo(cfgStack_.length() - 1, state.switch_.exitpc);
1328 0 : if (!switches_.append(breakInfo))
1329 0 : return ControlStatus::Error;
1330 :
1331 : // Jump into the first body.
1332 0 : currentIdx = 0;
1333 0 : current = nullptr;
1334 0 : state.state = CFGState::COND_SWITCH_BODY;
1335 :
1336 0 : return processCondSwitchBody(state);
1337 : }
1338 :
1339 : ControlFlowGenerator::ControlStatus
1340 0 : ControlFlowGenerator::processCondSwitchBody(CFGState& state)
1341 : {
1342 0 : MOZ_ASSERT(state.state == CFGState::COND_SWITCH_BODY);
1343 0 : MOZ_ASSERT(pc <= state.switch_.exitpc);
1344 0 : FixedList<CFGBlock*>& bodies = *state.switch_.bodies;
1345 0 : uint32_t& currentIdx = state.switch_.currentIdx;
1346 :
1347 0 : MOZ_ASSERT(currentIdx <= bodies.length());
1348 0 : if (currentIdx == bodies.length()) {
1349 0 : MOZ_ASSERT_IF(current, pc == state.switch_.exitpc);
1350 0 : return processSwitchEnd(state.switch_.breaks, state.switch_.exitpc);
1351 : }
1352 :
1353 : // Get the next body
1354 0 : CFGBlock* nextBody = bodies[currentIdx++];
1355 0 : MOZ_ASSERT_IF(current, pc == nextBody->startPc());
1356 :
1357 : // The last body continue into the new one.
1358 0 : if (current) {
1359 0 : current->setStopIns(CFGGoto::New(alloc(), nextBody));
1360 0 : current->setStopPc(pc);
1361 : }
1362 :
1363 : // Continue in the next body.
1364 0 : current = nextBody;
1365 0 : pc = current->startPc();
1366 :
1367 0 : if (!addBlock(current))
1368 0 : return ControlStatus::Error;
1369 :
1370 0 : if (currentIdx < bodies.length())
1371 0 : state.stopAt = bodies[currentIdx]->startPc();
1372 : else
1373 0 : state.stopAt = state.switch_.exitpc;
1374 0 : return ControlStatus::Jumped;
1375 : }
1376 :
1377 : ControlFlowGenerator::ControlStatus
1378 46 : ControlFlowGenerator::processAndOrEnd(CFGState& state)
1379 : {
1380 46 : MOZ_ASSERT(current);
1381 46 : CFGBlock* lhs = state.branch.ifFalse;
1382 :
1383 : // Create a new block to represent the join.
1384 46 : CFGBlock* join = CFGBlock::New(alloc(), state.stopAt);
1385 :
1386 : // End the rhs.
1387 46 : current->setStopIns(CFGGoto::New(alloc(), join));
1388 46 : current->setStopPc(pc);
1389 :
1390 : // End the lhs.
1391 46 : lhs->setStopIns(CFGGoto::New(alloc(), join));
1392 46 : lhs->setStopPc(pc);
1393 :
1394 : // Set the join path as current path.
1395 46 : current = join;
1396 46 : pc = current->startPc();
1397 :
1398 46 : if (!addBlock(current))
1399 0 : return ControlStatus::Error;
1400 :
1401 46 : return ControlStatus::Joined;
1402 : }
1403 :
1404 : ControlFlowGenerator::ControlStatus
1405 1825 : ControlFlowGenerator::maybeLoop(JSOp op, jssrcnote* sn)
1406 : {
1407 : // This function looks at the opcode and source note and tries to
1408 : // determine the structure of the loop. For some opcodes, like
1409 : // POP/NOP which are not explicitly control flow, this source note is
1410 : // optional. For opcodes with control flow, like GOTO, an unrecognized
1411 : // or not-present source note is a compilation failure.
1412 1825 : switch (op) {
1413 : case JSOP_POP:
1414 : // for (init; ; update?) ...
1415 1720 : if (sn && SN_TYPE(sn) == SRC_FOR) {
1416 0 : MOZ_CRASH("Not supported anymore?");
1417 : return processForLoop(op, sn);
1418 : }
1419 1720 : break;
1420 :
1421 : case JSOP_NOP:
1422 105 : if (sn) {
1423 : // do { } while (cond)
1424 105 : if (SN_TYPE(sn) == SRC_WHILE)
1425 0 : return processDoWhileLoop(op, sn);
1426 : // Build a mapping such that given a basic block, whose successor
1427 : // has a phi
1428 :
1429 : // for (; ; update?)
1430 105 : if (SN_TYPE(sn) == SRC_FOR)
1431 105 : return processForLoop(op, sn);
1432 : }
1433 0 : break;
1434 :
1435 : default:
1436 0 : MOZ_CRASH("unexpected opcode");
1437 : }
1438 :
1439 1720 : return ControlStatus::None;
1440 : }
1441 :
1442 : ControlFlowGenerator::ControlStatus
1443 105 : ControlFlowGenerator::processForLoop(JSOp op, jssrcnote* sn)
1444 : {
1445 : // Skip the NOP.
1446 105 : MOZ_ASSERT(op == JSOP_NOP);
1447 105 : pc = GetNextPc(pc);
1448 :
1449 105 : jsbytecode* condpc = pc + GetSrcNoteOffset(sn, 0);
1450 105 : jsbytecode* updatepc = pc + GetSrcNoteOffset(sn, 1);
1451 105 : jsbytecode* ifne = pc + GetSrcNoteOffset(sn, 2);
1452 105 : jsbytecode* exitpc = GetNextPc(ifne);
1453 :
1454 : // for loops have the following structures:
1455 : //
1456 : // NOP or POP
1457 : // [GOTO cond | NOP]
1458 : // LOOPHEAD
1459 : // body:
1460 : // ; [body]
1461 : // [increment:]
1462 : // [FRESHENBLOCKSCOPE, if needed by a cloned block]
1463 : // ; [increment]
1464 : // [cond:]
1465 : // LOOPENTRY
1466 : // GOTO body
1467 : //
1468 : // If there is a condition (condpc != ifne), this acts similar to a while
1469 : // loop otherwise, it acts like a do-while loop.
1470 : //
1471 : // Note that currently Ion does not compile pushblockscope/popblockscope as
1472 : // necessary prerequisites to freshenblockscope. So the code below doesn't
1473 : // and needn't consider the implications of freshenblockscope.
1474 105 : jsbytecode* bodyStart = pc;
1475 105 : jsbytecode* bodyEnd = updatepc;
1476 105 : jsbytecode* loopEntry = condpc;
1477 105 : if (condpc != ifne) {
1478 105 : MOZ_ASSERT(JSOp(*bodyStart) == JSOP_GOTO);
1479 105 : MOZ_ASSERT(bodyStart + GetJumpOffset(bodyStart) == condpc);
1480 105 : bodyStart = GetNextPc(bodyStart);
1481 : } else {
1482 : // No loop condition, such as for(j = 0; ; j++)
1483 0 : if (op != JSOP_NOP) {
1484 : // If the loop starts with POP, we have to skip a NOP.
1485 0 : MOZ_ASSERT(JSOp(*bodyStart) == JSOP_NOP);
1486 0 : bodyStart = GetNextPc(bodyStart);
1487 : }
1488 0 : loopEntry = GetNextPc(bodyStart);
1489 : }
1490 105 : jsbytecode* loopHead = bodyStart;
1491 105 : MOZ_ASSERT(JSOp(*bodyStart) == JSOP_LOOPHEAD);
1492 105 : MOZ_ASSERT(ifne + GetJumpOffset(ifne) == bodyStart);
1493 105 : bodyStart = GetNextPc(bodyStart);
1494 :
1495 105 : MOZ_ASSERT(JSOp(*loopEntry) == JSOP_LOOPENTRY);
1496 :
1497 105 : CFGBlock* header = CFGBlock::New(alloc(), GetNextPc(loopEntry));
1498 :
1499 105 : CFGLoopEntry* ins = CFGLoopEntry::New(alloc(), header, 0);
1500 105 : if (LoopEntryCanIonOsr(loopEntry))
1501 105 : ins->setCanOsr();
1502 :
1503 105 : current->setStopIns(ins);
1504 105 : current->setStopPc(pc);
1505 :
1506 : // If there is no condition, we immediately parse the body. Otherwise, we
1507 : // parse the condition.
1508 : jsbytecode* stopAt;
1509 : CFGState::State initial;
1510 105 : if (condpc != ifne) {
1511 105 : pc = condpc;
1512 105 : stopAt = ifne;
1513 105 : initial = CFGState::FOR_LOOP_COND;
1514 : } else {
1515 0 : pc = bodyStart;
1516 0 : stopAt = bodyEnd;
1517 0 : initial = CFGState::FOR_LOOP_BODY;
1518 : }
1519 :
1520 105 : if (!pushLoop(initial, stopAt, current,
1521 : loopHead, pc, bodyStart, bodyEnd, exitpc, updatepc))
1522 : {
1523 0 : return ControlStatus::Error;
1524 : }
1525 :
1526 105 : CFGState& state = cfgStack_.back();
1527 105 : state.loop.condpc = (condpc != ifne) ? condpc : nullptr;
1528 105 : state.loop.updatepc = (updatepc != condpc) ? updatepc : nullptr;
1529 105 : if (state.loop.updatepc)
1530 105 : state.loop.updateEnd = condpc;
1531 :
1532 105 : current = header;
1533 105 : if (!addBlock(current))
1534 0 : return ControlStatus::Error;
1535 105 : return ControlStatus::Jumped;
1536 : }
1537 :
1538 : ControlFlowGenerator::ControlStatus
1539 0 : ControlFlowGenerator::processDoWhileLoop(JSOp op, jssrcnote* sn)
1540 : {
1541 : // do { } while() loops have the following structure:
1542 : // NOP ; SRC_WHILE (offset to COND)
1543 : // LOOPHEAD ; SRC_WHILE (offset to IFNE)
1544 : // LOOPENTRY
1545 : // ... ; body
1546 : // ...
1547 : // COND ; start of condition
1548 : // ...
1549 : // IFNE -> ; goes to LOOPHEAD
1550 0 : int condition_offset = GetSrcNoteOffset(sn, 0);
1551 0 : jsbytecode* conditionpc = pc + condition_offset;
1552 :
1553 0 : jssrcnote* sn2 = GetSrcNote(gsn, script, pc + 1);
1554 0 : int offset = GetSrcNoteOffset(sn2, 0);
1555 0 : jsbytecode* ifne = pc + offset + 1;
1556 0 : MOZ_ASSERT(ifne > pc);
1557 :
1558 : // Verify that the IFNE goes back to a loophead op.
1559 0 : jsbytecode* loopHead = GetNextPc(pc);
1560 0 : MOZ_ASSERT(JSOp(*loopHead) == JSOP_LOOPHEAD);
1561 0 : MOZ_ASSERT(loopHead == ifne + GetJumpOffset(ifne));
1562 :
1563 0 : jsbytecode* loopEntry = GetNextPc(loopHead);
1564 :
1565 0 : CFGBlock* header = CFGBlock::New(alloc(), GetNextPc(loopEntry));
1566 :
1567 0 : CFGLoopEntry* ins = CFGLoopEntry::New(alloc(), header, 0);
1568 0 : if (LoopEntryCanIonOsr(loopEntry))
1569 0 : ins->setCanOsr();
1570 :
1571 0 : current->setStopIns(ins);
1572 0 : current->setStopPc(pc);
1573 :
1574 0 : jsbytecode* bodyEnd = conditionpc;
1575 0 : jsbytecode* exitpc = GetNextPc(ifne);
1576 0 : if (!pushLoop(CFGState::DO_WHILE_LOOP_BODY, conditionpc, current,
1577 : loopHead, loopEntry, loopEntry, bodyEnd, exitpc, conditionpc))
1578 : {
1579 0 : return ControlStatus::Error;
1580 : }
1581 :
1582 0 : CFGState& state = cfgStack_.back();
1583 0 : state.loop.updatepc = conditionpc;
1584 0 : state.loop.updateEnd = ifne;
1585 :
1586 0 : current = header;
1587 0 : pc = loopEntry;
1588 :
1589 0 : if (!addBlock(current))
1590 0 : return ControlStatus::Error;
1591 :
1592 0 : return ControlStatus::Jumped;
1593 : }
1594 :
1595 : bool
1596 117 : ControlFlowGenerator::pushLoop(CFGState::State initial, jsbytecode* stopAt, CFGBlock* entry,
1597 : jsbytecode* loopHead, jsbytecode* initialPc,
1598 : jsbytecode* bodyStart, jsbytecode* bodyEnd,
1599 : jsbytecode* exitpc, jsbytecode* continuepc)
1600 : {
1601 117 : ControlFlowInfo loop(cfgStack_.length(), continuepc);
1602 117 : if (!loops_.append(loop))
1603 0 : return false;
1604 :
1605 : CFGState state;
1606 117 : state.state = initial;
1607 117 : state.stopAt = stopAt;
1608 117 : state.loop.bodyStart = bodyStart;
1609 117 : state.loop.bodyEnd = bodyEnd;
1610 117 : state.loop.exitpc = exitpc;
1611 117 : state.loop.entry = entry;
1612 117 : state.loop.successor = nullptr;
1613 117 : state.loop.breaks = nullptr;
1614 117 : state.loop.continues = nullptr;
1615 117 : state.loop.initialState = initial;
1616 117 : state.loop.initialPc = initialPc;
1617 117 : state.loop.initialStopAt = stopAt;
1618 117 : state.loop.loopHead = loopHead;
1619 117 : return cfgStack_.append(state);
1620 : }
1621 :
1622 : ControlFlowGenerator::ControlStatus
1623 18 : ControlFlowGenerator::processBreak(JSOp op, jssrcnote* sn)
1624 : {
1625 18 : MOZ_ASSERT(op == JSOP_GOTO);
1626 :
1627 18 : MOZ_ASSERT(SN_TYPE(sn) == SRC_BREAK ||
1628 : SN_TYPE(sn) == SRC_BREAK2LABEL);
1629 :
1630 : // Find the break target.
1631 18 : jsbytecode* target = pc + GetJumpOffset(pc);
1632 36 : DebugOnly<bool> found = false;
1633 :
1634 18 : if (SN_TYPE(sn) == SRC_BREAK2LABEL) {
1635 0 : for (size_t i = labels_.length() - 1; i < labels_.length(); i--) {
1636 0 : CFGState& cfg = cfgStack_[labels_[i].cfgEntry];
1637 0 : MOZ_ASSERT(cfg.state == CFGState::LABEL);
1638 0 : if (cfg.stopAt == target) {
1639 0 : cfg.label.breaks = new(alloc()) DeferredEdge(current, cfg.label.breaks);
1640 0 : found = true;
1641 0 : break;
1642 : }
1643 : }
1644 : } else {
1645 18 : for (size_t i = loops_.length() - 1; i < loops_.length(); i--) {
1646 18 : CFGState& cfg = cfgStack_[loops_[i].cfgEntry];
1647 18 : MOZ_ASSERT(cfg.isLoop());
1648 18 : if (cfg.loop.exitpc == target) {
1649 18 : cfg.loop.breaks = new(alloc()) DeferredEdge(current, cfg.loop.breaks);
1650 18 : found = true;
1651 18 : break;
1652 : }
1653 : }
1654 : }
1655 :
1656 18 : current->setStopPc(pc);
1657 :
1658 18 : MOZ_ASSERT(found);
1659 :
1660 18 : current = nullptr;
1661 18 : pc += CodeSpec[op].length;
1662 36 : return processControlEnd();
1663 : }
1664 :
1665 : static inline jsbytecode*
1666 11 : EffectiveContinue(jsbytecode* pc)
1667 : {
1668 11 : if (JSOp(*pc) == JSOP_GOTO)
1669 0 : return pc + GetJumpOffset(pc);
1670 11 : return pc;
1671 : }
1672 :
1673 : ControlFlowGenerator::ControlStatus
1674 11 : ControlFlowGenerator::processContinue(JSOp op)
1675 : {
1676 11 : MOZ_ASSERT(op == JSOP_GOTO);
1677 :
1678 : // Find the target loop.
1679 11 : CFGState* found = nullptr;
1680 11 : jsbytecode* target = pc + GetJumpOffset(pc);
1681 11 : for (size_t i = loops_.length() - 1; i < loops_.length(); i--) {
1682 : // +1 to skip JSOP_JUMPTARGET.
1683 22 : if (loops_[i].continuepc == target + 1 ||
1684 11 : EffectiveContinue(loops_[i].continuepc) == target)
1685 : {
1686 11 : found = &cfgStack_[loops_[i].cfgEntry];
1687 11 : break;
1688 : }
1689 : }
1690 :
1691 : // There must always be a valid target loop structure. If not, there's
1692 : // probably an off-by-something error in which pc we track.
1693 11 : MOZ_ASSERT(found);
1694 11 : CFGState& state = *found;
1695 :
1696 11 : state.loop.continues = new(alloc()) DeferredEdge(current, state.loop.continues);
1697 11 : if (!state.loop.continues)
1698 0 : return ControlStatus::Error;
1699 11 : current->setStopPc(pc);
1700 :
1701 11 : current = nullptr;
1702 11 : pc += CodeSpec[op].length;
1703 11 : return processControlEnd();
1704 : }
1705 :
1706 : ControlFlowGenerator::ControlStatus
1707 0 : ControlFlowGenerator::processSwitchBreak(JSOp op)
1708 : {
1709 0 : MOZ_ASSERT(op == JSOP_GOTO);
1710 :
1711 : // Find the target switch.
1712 0 : CFGState* found = nullptr;
1713 0 : jsbytecode* target = pc + GetJumpOffset(pc);
1714 0 : for (size_t i = switches_.length() - 1; i < switches_.length(); i--) {
1715 0 : if (switches_[i].continuepc == target) {
1716 0 : found = &cfgStack_[switches_[i].cfgEntry];
1717 0 : break;
1718 : }
1719 : }
1720 :
1721 : // There must always be a valid target loop structure. If not, there's
1722 : // probably an off-by-something error in which pc we track.
1723 0 : MOZ_ASSERT(found);
1724 0 : CFGState& state = *found;
1725 :
1726 0 : DeferredEdge** breaks = nullptr;
1727 0 : switch (state.state) {
1728 : case CFGState::TABLE_SWITCH:
1729 0 : breaks = &state.switch_.breaks;
1730 0 : break;
1731 : case CFGState::COND_SWITCH_BODY:
1732 0 : breaks = &state.switch_.breaks;
1733 0 : break;
1734 : default:
1735 0 : MOZ_CRASH("Unexpected switch state.");
1736 : }
1737 :
1738 0 : *breaks = new(alloc()) DeferredEdge(current, *breaks);
1739 :
1740 0 : current->setStopPc(pc);
1741 :
1742 0 : current = nullptr;
1743 0 : pc += CodeSpec[op].length;
1744 0 : return processControlEnd();
1745 : }
1746 :
1747 : ControlFlowGenerator::ControlStatus
1748 597 : ControlFlowGenerator::processIfStart(JSOp op)
1749 : {
1750 : // IFEQ always has a forward offset.
1751 597 : jsbytecode* trueStart = pc + CodeSpec[op].length;
1752 597 : jsbytecode* falseStart = pc + GetJumpOffset(pc);
1753 597 : MOZ_ASSERT(falseStart > pc);
1754 :
1755 : // We only handle cases that emit source notes.
1756 597 : jssrcnote* sn = GetSrcNote(gsn, script, pc);
1757 597 : if (!sn)
1758 0 : return ControlStatus::Error;
1759 :
1760 : // Create true and false branches.
1761 597 : CFGBlock* ifTrue = CFGBlock::New(alloc(), trueStart);
1762 597 : CFGBlock* ifFalse = CFGBlock::New(alloc(), falseStart);
1763 :
1764 597 : CFGTest* test = CFGTest::New(alloc(), ifTrue, ifFalse);
1765 597 : current->setStopIns(test);
1766 597 : current->setStopPc(pc);
1767 :
1768 : // The bytecode for if/ternary gets emitted either like this:
1769 : //
1770 : // IFEQ X ; src note (IF_ELSE, COND) points to the GOTO
1771 : // ...
1772 : // GOTO Z
1773 : // X: ... ; else/else if
1774 : // ...
1775 : // Z: ; join
1776 : //
1777 : // Or like this:
1778 : //
1779 : // IFEQ X ; src note (IF) has no offset
1780 : // ...
1781 : // Z: ... ; join
1782 : //
1783 : // We want to parse the bytecode as if we were parsing the AST, so for the
1784 : // IF_ELSE/COND cases, we use the source note and follow the GOTO. For the
1785 : // IF case, the IFEQ offset is the join point.
1786 597 : switch (SN_TYPE(sn)) {
1787 : case SRC_IF:
1788 427 : if (!cfgStack_.append(CFGState::If(falseStart, test)))
1789 0 : return ControlStatus::Error;
1790 427 : break;
1791 :
1792 : case SRC_IF_ELSE:
1793 : case SRC_COND:
1794 : {
1795 : // Infer the join point from the JSOP_GOTO[X] sitting here, then
1796 : // assert as we much we can that this is the right GOTO.
1797 170 : jsbytecode* trueEnd = pc + GetSrcNoteOffset(sn, 0);
1798 170 : MOZ_ASSERT(trueEnd > pc);
1799 170 : MOZ_ASSERT(trueEnd < falseStart);
1800 170 : MOZ_ASSERT(JSOp(*trueEnd) == JSOP_GOTO);
1801 170 : MOZ_ASSERT(!GetSrcNote(gsn, script, trueEnd));
1802 :
1803 170 : jsbytecode* falseEnd = trueEnd + GetJumpOffset(trueEnd);
1804 170 : MOZ_ASSERT(falseEnd > trueEnd);
1805 170 : MOZ_ASSERT(falseEnd >= falseStart);
1806 :
1807 170 : if (!cfgStack_.append(CFGState::IfElse(trueEnd, falseEnd, test)))
1808 0 : return ControlStatus::Error;
1809 170 : break;
1810 : }
1811 :
1812 : default:
1813 0 : MOZ_CRASH("unexpected source note type");
1814 : }
1815 :
1816 : // Switch to parsing the true branch. Note that no PC update is needed,
1817 : // it's the next instruction.
1818 597 : current = ifTrue;
1819 597 : pc = ifTrue->startPc();
1820 :
1821 597 : if (!addBlock(current))
1822 0 : return ControlStatus::Error;
1823 :
1824 597 : return ControlStatus::Jumped;
1825 : }
1826 :
1827 : int
1828 572 : ControlFlowGenerator::CmpSuccessors(const void* a, const void* b)
1829 : {
1830 572 : const CFGBlock* a0 = * (CFGBlock * const*)a;
1831 572 : const CFGBlock* b0 = * (CFGBlock * const*)b;
1832 572 : if (a0->startPc() == b0->startPc())
1833 0 : return 0;
1834 :
1835 572 : return (a0->startPc() > b0->startPc()) ? 1 : -1;
1836 : }
1837 :
1838 : ControlFlowGenerator::ControlStatus
1839 44 : ControlFlowGenerator::processTableSwitch(JSOp op, jssrcnote* sn)
1840 : {
1841 : // TableSwitch op contains the following data
1842 : // (length between data is JUMP_OFFSET_LEN)
1843 : //
1844 : // 0: Offset of default case
1845 : // 1: Lowest number in tableswitch
1846 : // 2: Highest number in tableswitch
1847 : // 3: Offset of case low
1848 : // 4: Offset of case low+1
1849 : // .: ...
1850 : // .: Offset of case high
1851 :
1852 44 : MOZ_ASSERT(op == JSOP_TABLESWITCH);
1853 44 : MOZ_ASSERT(SN_TYPE(sn) == SRC_TABLESWITCH);
1854 :
1855 : // Get the default and exit pc
1856 44 : jsbytecode* exitpc = pc + GetSrcNoteOffset(sn, 0);
1857 44 : jsbytecode* defaultpc = pc + GET_JUMP_OFFSET(pc);
1858 :
1859 44 : MOZ_ASSERT(defaultpc > pc && defaultpc <= exitpc);
1860 :
1861 : // Get the low and high from the tableswitch
1862 44 : jsbytecode* pc2 = pc;
1863 44 : pc2 += JUMP_OFFSET_LEN;
1864 44 : int low = GET_JUMP_OFFSET(pc2);
1865 44 : pc2 += JUMP_OFFSET_LEN;
1866 44 : int high = GET_JUMP_OFFSET(pc2);
1867 44 : pc2 += JUMP_OFFSET_LEN;
1868 :
1869 : // Create MIR instruction
1870 44 : CFGTableSwitch* tableswitch = CFGTableSwitch::New(alloc(), low, high);
1871 :
1872 : // Create default case
1873 44 : CFGBlock* defaultcase = CFGBlock::New(alloc(), defaultpc);
1874 :
1875 44 : if (!tableswitch->addDefault(defaultcase))
1876 0 : return ControlStatus::Error;
1877 :
1878 : // Create cases
1879 44 : jsbytecode* casepc = nullptr;
1880 308 : for (int i = 0; i < high-low+1; i++) {
1881 264 : if (!alloc().ensureBallast())
1882 0 : return ControlStatus::Error;
1883 264 : casepc = pc + GET_JUMP_OFFSET(pc2);
1884 :
1885 264 : MOZ_ASSERT(casepc >= pc && casepc <= exitpc);
1886 : CFGBlock* caseBlock;
1887 :
1888 264 : if (casepc == pc) {
1889 : // If the casepc equals the current pc, it is not a written case,
1890 : // but a filled gap. That way we can use a tableswitch instead of
1891 : // condswitch, even if not all numbers are consecutive.
1892 : // In that case this block goes to the default case
1893 0 : caseBlock = CFGBlock::New(alloc(), defaultpc);
1894 0 : caseBlock->setStopIns(CFGGoto::New(alloc(), defaultcase));
1895 : } else {
1896 : // If this is an actual case (not filled gap),
1897 : // add this block to the list that still needs to get processed.
1898 264 : caseBlock = CFGBlock::New(alloc(), casepc);
1899 : }
1900 :
1901 264 : if (!tableswitch->addCase(caseBlock))
1902 0 : return ControlStatus::Error;
1903 :
1904 264 : pc2 += JUMP_OFFSET_LEN;
1905 : }
1906 :
1907 : // Create info
1908 44 : ControlFlowInfo switchinfo(cfgStack_.length(), exitpc);
1909 44 : if (!switches_.append(switchinfo))
1910 0 : return ControlStatus::Error;
1911 :
1912 : // Use a state to retrieve some information
1913 44 : CFGState state = CFGState::TableSwitch(alloc(), exitpc);
1914 88 : if (!state.switch_.bodies ||
1915 44 : !state.switch_.bodies->init(alloc(), tableswitch->numSuccessors()))
1916 : {
1917 0 : return ControlStatus::Error;
1918 : }
1919 :
1920 44 : FixedList<CFGBlock*>& bodies = *state.switch_.bodies;
1921 352 : for (size_t i = 0; i < tableswitch->numSuccessors(); i++)
1922 308 : bodies[i] = tableswitch->getSuccessor(i);
1923 :
1924 44 : qsort(bodies.begin(), state.switch_.bodies->length(),
1925 44 : sizeof(CFGBlock*), CmpSuccessors);
1926 :
1927 : // Save the MIR instruction as last instruction of this block.
1928 44 : current->setStopIns(tableswitch);
1929 44 : current->setStopPc(pc);
1930 :
1931 : // If there is only one successor the block should stop at the end of the switch
1932 : // Else it should stop at the start of the next successor
1933 44 : if (bodies.length() > 1)
1934 44 : state.stopAt = bodies[1]->startPc();
1935 : else
1936 0 : state.stopAt = exitpc;
1937 :
1938 44 : if (!cfgStack_.append(state))
1939 0 : return ControlStatus::Error;
1940 :
1941 44 : current = bodies[0];
1942 44 : pc = current->startPc();
1943 :
1944 44 : if (!addBlock(current))
1945 0 : return ControlStatus::Error;
1946 :
1947 44 : return ControlStatus::Jumped;
1948 : }
1949 :
1950 : ControlFlowGenerator::ControlStatus
1951 308 : ControlFlowGenerator::processNextTableSwitchCase(CFGState& state)
1952 : {
1953 308 : MOZ_ASSERT(state.state == CFGState::TABLE_SWITCH);
1954 308 : FixedList<CFGBlock*>& bodies = *state.switch_.bodies;
1955 :
1956 308 : state.switch_.currentIdx++;
1957 :
1958 : // Test if there are still unprocessed successors (cases/default)
1959 308 : if (state.switch_.currentIdx >= bodies.length())
1960 44 : return processSwitchEnd(state.switch_.breaks, state.switch_.exitpc);
1961 :
1962 : // Get the next successor
1963 264 : CFGBlock* successor = bodies[state.switch_.currentIdx];
1964 :
1965 : // Add current block as predecessor if available.
1966 : // This means the previous case didn't have a break statement.
1967 : // So flow will continue in this block.
1968 264 : if (current) {
1969 0 : current->setStopIns(CFGGoto::New(alloc(), successor));
1970 0 : current->setStopPc(pc);
1971 : }
1972 :
1973 : // If this is the last successor the block should stop at the end of the tableswitch
1974 : // Else it should stop at the start of the next successor
1975 264 : if (state.switch_.currentIdx + 1 < bodies.length())
1976 220 : state.stopAt = bodies[state.switch_.currentIdx + 1]->startPc();
1977 : else
1978 44 : state.stopAt = state.switch_.exitpc;
1979 :
1980 264 : current = bodies[state.switch_.currentIdx];
1981 264 : pc = current->startPc();
1982 :
1983 264 : if (!addBlock(current))
1984 0 : return ControlStatus::Error;
1985 :
1986 264 : return ControlStatus::Jumped;
1987 : }
1988 :
1989 : ControlFlowGenerator::ControlStatus
1990 44 : ControlFlowGenerator::processSwitchEnd(DeferredEdge* breaks, jsbytecode* exitpc)
1991 : {
1992 : // No break statements, no current.
1993 : // This means that control flow is cut-off from this point
1994 : // (e.g. all cases have return statements).
1995 44 : if (!breaks && !current)
1996 36 : return ControlStatus::Ended;
1997 :
1998 : // Create successor block.
1999 : // If there are breaks, create block with breaks as predecessor
2000 : // Else create a block with current as predecessor
2001 8 : CFGBlock* successor = nullptr;
2002 8 : if (breaks) {
2003 0 : successor = createBreakCatchBlock(breaks, exitpc);
2004 0 : if (!successor)
2005 0 : return ControlStatus::Error;
2006 : } else {
2007 8 : successor = CFGBlock::New(alloc(), exitpc);
2008 : }
2009 :
2010 : // If there is current, the current block flows into this one.
2011 : // So current is also a predecessor to this block
2012 8 : if (current) {
2013 8 : current->setStopIns(CFGGoto::New(alloc(), successor));
2014 8 : current->setStopPc(pc);
2015 : }
2016 :
2017 8 : current = successor;
2018 8 : pc = successor->startPc();
2019 :
2020 8 : if (!addBlock(successor))
2021 0 : return ControlStatus::Error;
2022 :
2023 8 : return ControlStatus::Joined;
2024 : }
2025 :
2026 : ControlFlowGenerator::CFGState
2027 427 : ControlFlowGenerator::CFGState::If(jsbytecode* join, CFGTest* test)
2028 : {
2029 : CFGState state;
2030 427 : state.state = IF_TRUE;
2031 427 : state.stopAt = join;
2032 427 : state.branch.ifFalse = test->getSuccessor(1);
2033 427 : state.branch.test = test;
2034 427 : return state;
2035 : }
2036 :
2037 : ControlFlowGenerator::CFGState
2038 170 : ControlFlowGenerator::CFGState::IfElse(jsbytecode* trueEnd, jsbytecode* falseEnd,
2039 : CFGTest* test)
2040 : {
2041 170 : CFGBlock* ifFalse = test->getSuccessor(1);
2042 :
2043 : CFGState state;
2044 : // If the end of the false path is the same as the start of the
2045 : // false path, then the "else" block is empty and we can devolve
2046 : // this to the IF_TRUE case. We handle this here because there is
2047 : // still an extra GOTO on the true path and we want stopAt to point
2048 : // there, whereas the IF_TRUE case does not have the GOTO.
2049 340 : state.state = (falseEnd == ifFalse->startPc())
2050 170 : ? IF_TRUE_EMPTY_ELSE
2051 : : IF_ELSE_TRUE;
2052 170 : state.stopAt = trueEnd;
2053 170 : state.branch.falseEnd = falseEnd;
2054 170 : state.branch.ifFalse = ifFalse;
2055 170 : state.branch.test = test;
2056 170 : return state;
2057 : }
2058 :
2059 : ControlFlowGenerator::CFGState
2060 46 : ControlFlowGenerator::CFGState::AndOr(jsbytecode* join, CFGBlock* lhs)
2061 : {
2062 : CFGState state;
2063 46 : state.state = AND_OR;
2064 46 : state.stopAt = join;
2065 46 : state.branch.ifFalse = lhs;
2066 46 : state.branch.test = nullptr;
2067 46 : return state;
2068 : }
2069 :
2070 : ControlFlowGenerator::CFGState
2071 44 : ControlFlowGenerator::CFGState::TableSwitch(TempAllocator& alloc, jsbytecode* exitpc)
2072 : {
2073 : CFGState state;
2074 44 : state.state = TABLE_SWITCH;
2075 44 : state.stopAt = exitpc;
2076 44 : state.switch_.bodies = (FixedList<CFGBlock*>*)alloc.allocate(sizeof(FixedList<CFGBlock*>));
2077 44 : state.switch_.currentIdx = 0;
2078 44 : state.switch_.exitpc = exitpc;
2079 44 : state.switch_.breaks = nullptr;
2080 44 : return state;
2081 : }
2082 :
2083 : ControlFlowGenerator::CFGState
2084 0 : ControlFlowGenerator::CFGState::CondSwitch(TempAllocator& alloc, jsbytecode* exitpc,
2085 : jsbytecode* defaultTarget)
2086 : {
2087 : CFGState state;
2088 0 : state.state = COND_SWITCH_CASE;
2089 0 : state.stopAt = nullptr;
2090 0 : state.switch_.bodies = (FixedList<CFGBlock*>*)alloc.allocate(sizeof(FixedList<CFGBlock*>));
2091 0 : state.switch_.currentIdx = 0;
2092 0 : state.switch_.defaultTarget = defaultTarget;
2093 0 : state.switch_.defaultIdx = uint32_t(-1);
2094 0 : state.switch_.exitpc = exitpc;
2095 0 : state.switch_.breaks = nullptr;
2096 0 : return state;
2097 : }
2098 : ControlFlowGenerator::CFGState
2099 0 : ControlFlowGenerator::CFGState::Label(jsbytecode* exitpc)
2100 : {
2101 : CFGState state;
2102 0 : state.state = LABEL;
2103 0 : state.stopAt = exitpc;
2104 0 : state.label.breaks = nullptr;
2105 0 : return state;
2106 : }
2107 :
2108 : ControlFlowGenerator::CFGState
2109 5 : ControlFlowGenerator::CFGState::Try(jsbytecode* exitpc, CFGBlock* successor)
2110 : {
2111 : CFGState state;
2112 5 : state.state = TRY;
2113 5 : state.stopAt = exitpc;
2114 5 : state.try_.successor = successor;
2115 5 : return state;
2116 : }
2117 :
2118 : ControlFlowGenerator::ControlStatus
2119 46 : ControlFlowGenerator::processAndOr(JSOp op)
2120 : {
2121 46 : MOZ_ASSERT(op == JSOP_AND || op == JSOP_OR);
2122 :
2123 46 : jsbytecode* rhsStart = pc + CodeSpec[op].length;
2124 46 : jsbytecode* joinStart = pc + GetJumpOffset(pc);
2125 46 : MOZ_ASSERT(joinStart > pc);
2126 :
2127 46 : CFGBlock* evalLhs = CFGBlock::New(alloc(), joinStart);
2128 46 : CFGBlock* evalRhs = CFGBlock::New(alloc(), rhsStart);
2129 :
2130 : CFGTest* test = (op == JSOP_AND)
2131 63 : ? CFGTest::New(alloc(), evalRhs, evalLhs)
2132 63 : : CFGTest::New(alloc(), evalLhs, evalRhs);
2133 46 : test->keepCondition();
2134 46 : current->setStopIns(test);
2135 46 : current->setStopPc(pc);
2136 :
2137 : // Create the rhs block.
2138 46 : if (!cfgStack_.append(CFGState::AndOr(joinStart, evalLhs)))
2139 0 : return ControlStatus::Error;
2140 :
2141 46 : if (!addBlock(evalLhs))
2142 0 : return ControlStatus::Error;
2143 :
2144 46 : current = evalRhs;
2145 46 : pc = current->startPc();
2146 :
2147 46 : if (!addBlock(current))
2148 0 : return ControlStatus::Error;
2149 :
2150 46 : return ControlStatus::Jumped;
2151 : }
2152 :
2153 : ControlFlowGenerator::ControlStatus
2154 0 : ControlFlowGenerator::processLabel()
2155 : {
2156 0 : MOZ_ASSERT(JSOp(*pc) == JSOP_LABEL);
2157 :
2158 0 : jsbytecode* endpc = pc + GET_JUMP_OFFSET(pc);
2159 0 : MOZ_ASSERT(endpc > pc);
2160 :
2161 0 : ControlFlowInfo label(cfgStack_.length(), endpc);
2162 0 : if (!labels_.append(label))
2163 0 : return ControlStatus::Error;
2164 :
2165 0 : if (!cfgStack_.append(CFGState::Label(endpc)))
2166 0 : return ControlStatus::Error;
2167 :
2168 0 : return ControlStatus::None;
2169 : }
|
