The Tor Browser / file comparison

comparison: js/src/jit/MIRGraph.cpp

js/src/jit/MIRGraph.cpp

branch
TOR_BUG_3246
changeset 7
129ffea94266
equal deleted inserted replaced
-1:000000000000 0:f61d69114f50
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/MIRGraph.h"
8
9 #include "jit/AsmJS.h"
10 #include "jit/BytecodeAnalysis.h"
11 #include "jit/Ion.h"
12 #include "jit/IonSpewer.h"
13 #include "jit/MIR.h"
14 #include "jit/MIRGenerator.h"
15
16 using namespace js;
17 using namespace js::jit;
18
19 MIRGenerator::MIRGenerator(CompileCompartment *compartment, const JitCompileOptions &options,
20 TempAllocator *alloc, MIRGraph *graph, CompileInfo *info,
21 const OptimizationInfo *optimizationInfo)
22 : compartment(compartment),
23 info_(info),
24 optimizationInfo_(optimizationInfo),
25 alloc_(alloc),
26 graph_(graph),
27 error_(false),
28 cancelBuild_(false),
29 maxAsmJSStackArgBytes_(0),
30 performsCall_(false),
31 performsAsmJSCall_(false),
32 minAsmJSHeapLength_(AsmJSAllocationGranularity),
33 modifiesFrameArguments_(false),
34 options(options)
35 { }
36
37 bool
38 MIRGenerator::abortFmt(const char *message, va_list ap)
39 {
40 IonSpewVA(IonSpew_Abort, message, ap);
41 error_ = true;
42 return false;
43 }
44
45 bool
46 MIRGenerator::abort(const char *message, ...)
47 {
48 va_list ap;
49 va_start(ap, message);
50 abortFmt(message, ap);
51 va_end(ap);
52 return false;
53 }
54
55 void
56 MIRGraph::addBlock(MBasicBlock *block)
57 {
58 JS_ASSERT(block);
59 block->setId(blockIdGen_++);
60 blocks_.pushBack(block);
61 numBlocks_++;
62 }
63
64 void
65 MIRGraph::insertBlockAfter(MBasicBlock *at, MBasicBlock *block)
66 {
67 block->setId(blockIdGen_++);
68 blocks_.insertAfter(at, block);
69 numBlocks_++;
70 }
71
72 void
73 MIRGraph::removeBlocksAfter(MBasicBlock *start)
74 {
75 MBasicBlockIterator iter(begin());
76 iter++;
77 while (iter != end()) {
78 MBasicBlock *block = *iter;
79 iter++;
80
81 if (block->id() <= start->id())
82 continue;
83
84 // removeBlock will not remove the resumepoints, since
85 // it can be shared with outer blocks. So remove them now.
86 block->discardAllResumePoints();
87 removeBlock(block);
88 }
89 }
90
91 void
92 MIRGraph::removeBlock(MBasicBlock *block)
93 {
94 // Remove a block from the graph. It will also cleanup the block,
95 // except for removing the resumepoints, since multiple blocks can
96 // share the same resumepoints and we cannot distinguish between them.
97
98 if (block == osrBlock_)
99 osrBlock_ = nullptr;
100
101 if (returnAccumulator_) {
102 size_t i = 0;
103 while (i < returnAccumulator_->length()) {
104 if ((*returnAccumulator_)[i] == block)
105 returnAccumulator_->erase(returnAccumulator_->begin() + i);
106 else
107 i++;
108 }
109 }
110
111 block->discardAllInstructions();
112
113 // Note: phis are disconnected from the rest of the graph, but are not
114 // removed entirely. If the block being removed is a loop header then
115 // IonBuilder may need to access these phis to more quickly converge on the
116 // possible types in the graph. See IonBuilder::analyzeNewLoopTypes.
117 block->discardAllPhiOperands();
118
119 block->markAsDead();
120 blocks_.remove(block);
121 numBlocks_--;
122 }
123
124 void
125 MIRGraph::unmarkBlocks()
126 {
127 for (MBasicBlockIterator i(blocks_.begin()); i != blocks_.end(); i++)
128 i->unmark();
129 }
130
131 MDefinition *
132 MIRGraph::forkJoinContext()
133 {
134 // Search the entry block to find a ForkJoinContext instruction. If we do
135 // not find one, add one after the Start instruction.
136 //
137 // Note: the original design used a field in MIRGraph to cache the
138 // forkJoinContext rather than searching for it again. However, this
139 // could become out of date due to DCE. Given that we do not generally
140 // have to search very far to find the ForkJoinContext instruction if it
141 // exists, and that we don't look for it that often, I opted to simply
142 // eliminate the cache and search anew each time, so that it is that much
143 // easier to keep the IR coherent. - nmatsakis
144
145 MBasicBlock *entry = entryBlock();
146 JS_ASSERT(entry->info().executionMode() == ParallelExecution);
147
148 MInstruction *start = nullptr;
149 for (MInstructionIterator ins(entry->begin()); ins != entry->end(); ins++) {
150 if (ins->isForkJoinContext())
151 return *ins;
152 else if (ins->isStart())
153 start = *ins;
154 }
155 JS_ASSERT(start);
156
157 MForkJoinContext *cx = MForkJoinContext::New(alloc());
158 entry->insertAfter(start, cx);
159 return cx;
160 }
161
162 MBasicBlock *
163 MBasicBlock::New(MIRGraph &graph, BytecodeAnalysis *analysis, CompileInfo &info,
164 MBasicBlock *pred, jsbytecode *entryPc, Kind kind)
165 {
166 JS_ASSERT(entryPc != nullptr);
167
168 MBasicBlock *block = new(graph.alloc()) MBasicBlock(graph, info, entryPc, kind);
169 if (!block->init())
170 return nullptr;
171
172 if (!block->inherit(graph.alloc(), analysis, pred, 0))
173 return nullptr;
174
175 return block;
176 }
177
178 MBasicBlock *
179 MBasicBlock::NewPopN(MIRGraph &graph, CompileInfo &info,
180 MBasicBlock *pred, jsbytecode *entryPc, Kind kind, uint32_t popped)
181 {
182 MBasicBlock *block = new(graph.alloc()) MBasicBlock(graph, info, entryPc, kind);
183 if (!block->init())
184 return nullptr;
185
186 if (!block->inherit(graph.alloc(), nullptr, pred, popped))
187 return nullptr;
188
189 return block;
190 }
191
192 MBasicBlock *
193 MBasicBlock::NewWithResumePoint(MIRGraph &graph, CompileInfo &info,
194 MBasicBlock *pred, jsbytecode *entryPc,
195 MResumePoint *resumePoint)
196 {
197 MBasicBlock *block = new(graph.alloc()) MBasicBlock(graph, info, entryPc, NORMAL);
198
199 resumePoint->block_ = block;
200 block->entryResumePoint_ = resumePoint;
201
202 if (!block->init())
203 return nullptr;
204
205 if (!block->inheritResumePoint(pred))
206 return nullptr;
207
208 return block;
209 }
210
211 MBasicBlock *
212 MBasicBlock::NewPendingLoopHeader(MIRGraph &graph, CompileInfo &info,
213 MBasicBlock *pred, jsbytecode *entryPc,
214 unsigned stackPhiCount)
215 {
216 JS_ASSERT(entryPc != nullptr);
217
218 MBasicBlock *block = new(graph.alloc()) MBasicBlock(graph, info, entryPc, PENDING_LOOP_HEADER);
219 if (!block->init())
220 return nullptr;
221
222 if (!block->inherit(graph.alloc(), nullptr, pred, 0, stackPhiCount))
223 return nullptr;
224
225 return block;
226 }
227
228 MBasicBlock *
229 MBasicBlock::NewSplitEdge(MIRGraph &graph, CompileInfo &info, MBasicBlock *pred)
230 {
231 return pred->pc()
232 ? MBasicBlock::New(graph, nullptr, info, pred, pred->pc(), SPLIT_EDGE)
233 : MBasicBlock::NewAsmJS(graph, info, pred, SPLIT_EDGE);
234 }
235
236 MBasicBlock *
237 MBasicBlock::NewAbortPar(MIRGraph &graph, CompileInfo &info,
238 MBasicBlock *pred, jsbytecode *entryPc,
239 MResumePoint *resumePoint)
240 {
241 MBasicBlock *block = new(graph.alloc()) MBasicBlock(graph, info, entryPc, NORMAL);
242
243 resumePoint->block_ = block;
244 block->entryResumePoint_ = resumePoint;
245
246 if (!block->init())
247 return nullptr;
248
249 if (!block->addPredecessorWithoutPhis(pred))
250 return nullptr;
251
252 block->end(MAbortPar::New(graph.alloc()));
253 return block;
254 }
255
256 MBasicBlock *
257 MBasicBlock::NewAsmJS(MIRGraph &graph, CompileInfo &info, MBasicBlock *pred, Kind kind)
258 {
259 MBasicBlock *block = new(graph.alloc()) MBasicBlock(graph, info, /* entryPC = */ nullptr, kind);
260 if (!block->init())
261 return nullptr;
262
263 if (pred) {
264 block->stackPosition_ = pred->stackPosition_;
265
266 if (block->kind_ == PENDING_LOOP_HEADER) {
267 size_t nphis = block->stackPosition_;
268
269 TempAllocator &alloc = graph.alloc();
270 MPhi *phis = (MPhi*)alloc.allocateArray<sizeof(MPhi)>(nphis);
271 if (!phis)
272 return nullptr;
273
274 for (size_t i = 0; i < nphis; i++) {
275 MDefinition *predSlot = pred->getSlot(i);
276
277 JS_ASSERT(predSlot->type() != MIRType_Value);
278 MPhi *phi = new(phis + i) MPhi(alloc, i, predSlot->type());
279
280 JS_ALWAYS_TRUE(phi->reserveLength(2));
281 phi->addInput(predSlot);
282
283 block->addPhi(phi);
284 block->setSlot(i, phi);
285 }
286 } else {
287 block->copySlots(pred);
288 }
289
290 if (!block->predecessors_.append(pred))
291 return nullptr;
292 }
293
294 return block;
295 }
296
297 MBasicBlock::MBasicBlock(MIRGraph &graph, CompileInfo &info, jsbytecode *pc, Kind kind)
298 : unreachable_(false),
299 graph_(graph),
300 info_(info),
301 predecessors_(graph.alloc()),
302 stackPosition_(info_.firstStackSlot()),
303 lastIns_(nullptr),
304 pc_(pc),
305 lir_(nullptr),
306 start_(nullptr),
307 entryResumePoint_(nullptr),
308 successorWithPhis_(nullptr),
309 positionInPhiSuccessor_(0),
310 kind_(kind),
311 loopDepth_(0),
312 mark_(false),
313 immediatelyDominated_(graph.alloc()),
314 immediateDominator_(nullptr),
315 numDominated_(0),
316 trackedPc_(pc)
317 #if defined (JS_ION_PERF)
318 , lineno_(0u),
319 columnIndex_(0u)
320 #endif
321 {
322 }
323
324 bool
325 MBasicBlock::init()
326 {
327 return slots_.init(graph_.alloc(), info_.nslots());
328 }
329
330 bool
331 MBasicBlock::increaseSlots(size_t num)
332 {
333 return slots_.growBy(graph_.alloc(), num);
334 }
335
336 bool
337 MBasicBlock::ensureHasSlots(size_t num)
338 {
339 size_t depth = stackDepth() + num;
340 if (depth > nslots()) {
341 if (!increaseSlots(depth - nslots()))
342 return false;
343 }
344 return true;
345 }
346
347 void
348 MBasicBlock::copySlots(MBasicBlock *from)
349 {
350 JS_ASSERT(stackPosition_ <= from->stackPosition_);
351
352 for (uint32_t i = 0; i < stackPosition_; i++)
353 slots_[i] = from->slots_[i];
354 }
355
356 bool
357 MBasicBlock::inherit(TempAllocator &alloc, BytecodeAnalysis *analysis, MBasicBlock *pred,
358 uint32_t popped, unsigned stackPhiCount)
359 {
360 if (pred) {
361 stackPosition_ = pred->stackPosition_;
362 JS_ASSERT(stackPosition_ >= popped);
363 stackPosition_ -= popped;
364 if (kind_ != PENDING_LOOP_HEADER)
365 copySlots(pred);
366 } else {
367 uint32_t stackDepth = analysis->info(pc()).stackDepth;
368 stackPosition_ = info().firstStackSlot() + stackDepth;
369 JS_ASSERT(stackPosition_ >= popped);
370 stackPosition_ -= popped;
371 }
372
373 JS_ASSERT(info_.nslots() >= stackPosition_);
374 JS_ASSERT(!entryResumePoint_);
375
376 // Propagate the caller resume point from the inherited block.
377 MResumePoint *callerResumePoint = pred ? pred->callerResumePoint() : nullptr;
378
379 // Create a resume point using our initial stack state.
380 entryResumePoint_ = new(alloc) MResumePoint(this, pc(), callerResumePoint, MResumePoint::ResumeAt);
381 if (!entryResumePoint_->init(alloc))
382 return false;
383
384 if (pred) {
385 if (!predecessors_.append(pred))
386 return false;
387
388 if (kind_ == PENDING_LOOP_HEADER) {
389 size_t i = 0;
390 for (i = 0; i < info().firstStackSlot(); i++) {
391 MPhi *phi = MPhi::New(alloc, i);
392 if (!phi->addInputSlow(pred->getSlot(i)))
393 return false;
394 addPhi(phi);
395 setSlot(i, phi);
396 entryResumePoint()->setOperand(i, phi);
397 }
398
399 JS_ASSERT(stackPhiCount <= stackDepth());
400 JS_ASSERT(info().firstStackSlot() <= stackDepth() - stackPhiCount);
401
402 // Avoid creating new phis for stack values that aren't part of the
403 // loop. Note that for loop headers that can OSR, all values on the
404 // stack are part of the loop.
405 for (; i < stackDepth() - stackPhiCount; i++) {
406 MDefinition *val = pred->getSlot(i);
407 setSlot(i, val);
408 entryResumePoint()->setOperand(i, val);
409 }
410
411 for (; i < stackDepth(); i++) {
412 MPhi *phi = MPhi::New(alloc, i);
413 if (!phi->addInputSlow(pred->getSlot(i)))
414 return false;
415 addPhi(phi);
416 setSlot(i, phi);
417 entryResumePoint()->setOperand(i, phi);
418 }
419 } else {
420 for (size_t i = 0; i < stackDepth(); i++)
421 entryResumePoint()->setOperand(i, getSlot(i));
422 }
423 } else {
424 /*
425 * Don't leave the operands uninitialized for the caller, as it may not
426 * initialize them later on.
427 */
428 for (size_t i = 0; i < stackDepth(); i++)
429 entryResumePoint()->clearOperand(i);
430 }
431
432 return true;
433 }
434
435 bool
436 MBasicBlock::inheritResumePoint(MBasicBlock *pred)
437 {
438 // Copy slots from the resume point.
439 stackPosition_ = entryResumePoint_->numOperands();
440 for (uint32_t i = 0; i < stackPosition_; i++)
441 slots_[i] = entryResumePoint_->getOperand(i);
442
443 JS_ASSERT(info_.nslots() >= stackPosition_);
444 JS_ASSERT(kind_ != PENDING_LOOP_HEADER);
445 JS_ASSERT(pred != nullptr);
446
447 if (!predecessors_.append(pred))
448 return false;
449
450 return true;
451 }
452
453 void
454 MBasicBlock::inheritSlots(MBasicBlock *parent)
455 {
456 stackPosition_ = parent->stackPosition_;
457 copySlots(parent);
458 }
459
460 bool
461 MBasicBlock::initEntrySlots(TempAllocator &alloc)
462 {
463 // Create a resume point using our initial stack state.
464 entryResumePoint_ = MResumePoint::New(alloc, this, pc(), callerResumePoint(),
465 MResumePoint::ResumeAt);
466 if (!entryResumePoint_)
467 return false;
468 return true;
469 }
470
471 MDefinition *
472 MBasicBlock::getSlot(uint32_t index)
473 {
474 JS_ASSERT(index < stackPosition_);
475 return slots_[index];
476 }
477
478 void
479 MBasicBlock::initSlot(uint32_t slot, MDefinition *ins)
480 {
481 slots_[slot] = ins;
482 if (entryResumePoint())
483 entryResumePoint()->setOperand(slot, ins);
484 }
485
486 void
487 MBasicBlock::shimmySlots(int discardDepth)
488 {
489 // Move all slots above the given depth down by one,
490 // overwriting the MDefinition at discardDepth.
491
492 JS_ASSERT(discardDepth < 0);
493 JS_ASSERT(stackPosition_ + discardDepth >= info_.firstStackSlot());
494
495 for (int i = discardDepth; i < -1; i++)
496 slots_[stackPosition_ + i] = slots_[stackPosition_ + i + 1];
497
498 --stackPosition_;
499 }
500
501 void
502 MBasicBlock::linkOsrValues(MStart *start)
503 {
504 JS_ASSERT(start->startType() == MStart::StartType_Osr);
505
506 MResumePoint *res = start->resumePoint();
507
508 for (uint32_t i = 0; i < stackDepth(); i++) {
509 MDefinition *def = slots_[i];
510 if (i == info().scopeChainSlot()) {
511 if (def->isOsrScopeChain())
512 def->toOsrScopeChain()->setResumePoint(res);
513 } else if (i == info().returnValueSlot()) {
514 if (def->isOsrReturnValue())
515 def->toOsrReturnValue()->setResumePoint(res);
516 } else if (info().hasArguments() && i == info().argsObjSlot()) {
517 JS_ASSERT(def->isConstant() || def->isOsrArgumentsObject());
518 JS_ASSERT_IF(def->isConstant(), def->toConstant()->value() == UndefinedValue());
519 if (def->isOsrArgumentsObject())
520 def->toOsrArgumentsObject()->setResumePoint(res);
521 } else {
522 JS_ASSERT(def->isOsrValue() || def->isGetArgumentsObjectArg() || def->isConstant() ||
523 def->isParameter());
524
525 // A constant Undefined can show up here for an argument slot when the function uses
526 // a heavyweight argsobj, but the argument in question is stored on the scope chain.
527 JS_ASSERT_IF(def->isConstant(), def->toConstant()->value() == UndefinedValue());
528
529 if (def->isOsrValue())
530 def->toOsrValue()->setResumePoint(res);
531 else if (def->isGetArgumentsObjectArg())
532 def->toGetArgumentsObjectArg()->setResumePoint(res);
533 else if (def->isParameter())
534 def->toParameter()->setResumePoint(res);
535 }
536 }
537 }
538
539 void
540 MBasicBlock::setSlot(uint32_t slot, MDefinition *ins)
541 {
542 slots_[slot] = ins;
543 }
544
545 void
546 MBasicBlock::setVariable(uint32_t index)
547 {
548 JS_ASSERT(stackPosition_ > info_.firstStackSlot());
549 setSlot(index, slots_[stackPosition_ - 1]);
550 }
551
552 void
553 MBasicBlock::setArg(uint32_t arg)
554 {
555 setVariable(info_.argSlot(arg));
556 }
557
558 void
559 MBasicBlock::setLocal(uint32_t local)
560 {
561 setVariable(info_.localSlot(local));
562 }
563
564 void
565 MBasicBlock::setSlot(uint32_t slot)
566 {
567 setVariable(slot);
568 }
569
570 void
571 MBasicBlock::rewriteSlot(uint32_t slot, MDefinition *ins)
572 {
573 setSlot(slot, ins);
574 }
575
576 void
577 MBasicBlock::rewriteAtDepth(int32_t depth, MDefinition *ins)
578 {
579 JS_ASSERT(depth < 0);
580 JS_ASSERT(stackPosition_ + depth >= info_.firstStackSlot());
581 rewriteSlot(stackPosition_ + depth, ins);
582 }
583
584 void
585 MBasicBlock::push(MDefinition *ins)
586 {
587 JS_ASSERT(stackPosition_ < nslots());
588 slots_[stackPosition_++] = ins;
589 }
590
591 void
592 MBasicBlock::pushVariable(uint32_t slot)
593 {
594 push(slots_[slot]);
595 }
596
597 void
598 MBasicBlock::pushArg(uint32_t arg)
599 {
600 pushVariable(info_.argSlot(arg));
601 }
602
603 void
604 MBasicBlock::pushLocal(uint32_t local)
605 {
606 pushVariable(info_.localSlot(local));
607 }
608
609 void
610 MBasicBlock::pushSlot(uint32_t slot)
611 {
612 pushVariable(slot);
613 }
614
615 MDefinition *
616 MBasicBlock::pop()
617 {
618 JS_ASSERT(stackPosition_ > info_.firstStackSlot());
619 return slots_[--stackPosition_];
620 }
621
622 void
623 MBasicBlock::popn(uint32_t n)
624 {
625 JS_ASSERT(stackPosition_ - n >= info_.firstStackSlot());
626 JS_ASSERT(stackPosition_ >= stackPosition_ - n);
627 stackPosition_ -= n;
628 }
629
630 MDefinition *
631 MBasicBlock::scopeChain()
632 {
633 return getSlot(info().scopeChainSlot());
634 }
635
636 MDefinition *
637 MBasicBlock::argumentsObject()
638 {
639 return getSlot(info().argsObjSlot());
640 }
641
642 void
643 MBasicBlock::setScopeChain(MDefinition *scopeObj)
644 {
645 setSlot(info().scopeChainSlot(), scopeObj);
646 }
647
648 void
649 MBasicBlock::setArgumentsObject(MDefinition *argsObj)
650 {
651 setSlot(info().argsObjSlot(), argsObj);
652 }
653
654 void
655 MBasicBlock::pick(int32_t depth)
656 {
657 // pick take an element and move it to the top.
658 // pick(-2):
659 // A B C D E
660 // A B D C E [ swapAt(-2) ]
661 // A B D E C [ swapAt(-1) ]
662 for (; depth < 0; depth++)
663 swapAt(depth);
664 }
665
666 void
667 MBasicBlock::swapAt(int32_t depth)
668 {
669 uint32_t lhsDepth = stackPosition_ + depth - 1;
670 uint32_t rhsDepth = stackPosition_ + depth;
671
672 MDefinition *temp = slots_[lhsDepth];
673 slots_[lhsDepth] = slots_[rhsDepth];
674 slots_[rhsDepth] = temp;
675 }
676
677 MDefinition *
678 MBasicBlock::peek(int32_t depth)
679 {
680 JS_ASSERT(depth < 0);
681 JS_ASSERT(stackPosition_ + depth >= info_.firstStackSlot());
682 return getSlot(stackPosition_ + depth);
683 }
684
685 void
686 MBasicBlock::discardLastIns()
687 {
688 JS_ASSERT(lastIns_);
689 discard(lastIns_);
690 lastIns_ = nullptr;
691 }
692
693 void
694 MBasicBlock::addFromElsewhere(MInstruction *ins)
695 {
696 JS_ASSERT(ins->block() != this);
697
698 // Remove |ins| from its containing block.
699 ins->block()->instructions_.remove(ins);
700
701 // Add it to this block.
702 add(ins);
703 }
704
705 void
706 MBasicBlock::moveBefore(MInstruction *at, MInstruction *ins)
707 {
708 // Remove |ins| from the current block.
709 JS_ASSERT(ins->block() == this);
710 instructions_.remove(ins);
711
712 // Insert into new block, which may be distinct.
713 // Uses and operands are untouched.
714 at->block()->insertBefore(at, ins);
715 }
716
717 static inline void
718 AssertSafelyDiscardable(MDefinition *def)
719 {
720 #ifdef DEBUG
721 // Instructions captured by resume points cannot be safely discarded, since
722 // they are necessary for interpreter frame reconstruction in case of bailout.
723 JS_ASSERT(!def->hasUses());
724 #endif
725 }
726
727 void
728 MBasicBlock::discard(MInstruction *ins)
729 {
730 AssertSafelyDiscardable(ins);
731 for (size_t i = 0, e = ins->numOperands(); i < e; i++)
732 ins->discardOperand(i);
733
734 instructions_.remove(ins);
735 }
736
737 MInstructionIterator
738 MBasicBlock::discardAt(MInstructionIterator &iter)
739 {
740 AssertSafelyDiscardable(*iter);
741 for (size_t i = 0, e = iter->numOperands(); i < e; i++)
742 iter->discardOperand(i);
743
744 return instructions_.removeAt(iter);
745 }
746
747 MInstructionReverseIterator
748 MBasicBlock::discardAt(MInstructionReverseIterator &iter)
749 {
750 AssertSafelyDiscardable(*iter);
751 for (size_t i = 0, e = iter->numOperands(); i < e; i++)
752 iter->discardOperand(i);
753
754 return instructions_.removeAt(iter);
755 }
756
757 MDefinitionIterator
758 MBasicBlock::discardDefAt(MDefinitionIterator &old)
759 {
760 MDefinitionIterator iter(old);
761
762 if (iter.atPhi())
763 iter.phiIter_ = iter.block_->discardPhiAt(iter.phiIter_);
764 else
765 iter.iter_ = iter.block_->discardAt(iter.iter_);
766
767 return iter;
768 }
769
770 void
771 MBasicBlock::discardAllInstructions()
772 {
773 for (MInstructionIterator iter = begin(); iter != end(); ) {
774 for (size_t i = 0, e = iter->numOperands(); i < e; i++)
775 iter->discardOperand(i);
776 iter = instructions_.removeAt(iter);
777 }
778 lastIns_ = nullptr;
779 }
780
781 void
782 MBasicBlock::discardAllPhiOperands()
783 {
784 for (MPhiIterator iter = phisBegin(); iter != phisEnd(); iter++) {
785 MPhi *phi = *iter;
786 for (size_t i = 0, e = phi->numOperands(); i < e; i++)
787 phi->discardOperand(i);
788 }
789
790 for (MBasicBlock **pred = predecessors_.begin(); pred != predecessors_.end(); pred++)
791 (*pred)->setSuccessorWithPhis(nullptr, 0);
792 }
793
794 void
795 MBasicBlock::discardAllPhis()
796 {
797 discardAllPhiOperands();
798 phis_.clear();
799 }
800
801 void
802 MBasicBlock::discardAllResumePoints(bool discardEntry)
803 {
804 for (MResumePointIterator iter = resumePointsBegin(); iter != resumePointsEnd(); ) {
805 MResumePoint *rp = *iter;
806 if (rp == entryResumePoint() && !discardEntry) {
807 iter++;
808 } else {
809 rp->discardUses();
810 iter = resumePoints_.removeAt(iter);
811 }
812 }
813 }
814
815 void
816 MBasicBlock::insertBefore(MInstruction *at, MInstruction *ins)
817 {
818 JS_ASSERT(at->block() == this);
819 ins->setBlock(this);
820 graph().allocDefinitionId(ins);
821 instructions_.insertBefore(at, ins);
822 ins->setTrackedPc(at->trackedPc());
823 }
824
825 void
826 MBasicBlock::insertAfter(MInstruction *at, MInstruction *ins)
827 {
828 JS_ASSERT(at->block() == this);
829 ins->setBlock(this);
830 graph().allocDefinitionId(ins);
831 instructions_.insertAfter(at, ins);
832 ins->setTrackedPc(at->trackedPc());
833 }
834
835 void
836 MBasicBlock::add(MInstruction *ins)
837 {
838 JS_ASSERT(!lastIns_);
839 ins->setBlock(this);
840 graph().allocDefinitionId(ins);
841 instructions_.pushBack(ins);
842 ins->setTrackedPc(trackedPc_);
843 }
844
845 void
846 MBasicBlock::end(MControlInstruction *ins)
847 {
848 JS_ASSERT(!lastIns_); // Existing control instructions should be removed first.
849 JS_ASSERT(ins);
850 add(ins);
851 lastIns_ = ins;
852 }
853
854 void
855 MBasicBlock::addPhi(MPhi *phi)
856 {
857 phis_.pushBack(phi);
858 phi->setBlock(this);
859 graph().allocDefinitionId(phi);
860 }
861
862 MPhiIterator
863 MBasicBlock::discardPhiAt(MPhiIterator &at)
864 {
865 JS_ASSERT(!phis_.empty());
866
867 for (size_t i = 0, e = at->numOperands(); i < e; i++)
868 at->discardOperand(i);
869
870 MPhiIterator result = phis_.removeAt(at);
871
872 if (phis_.empty()) {
873 for (MBasicBlock **pred = predecessors_.begin(); pred != predecessors_.end(); pred++)
874 (*pred)->setSuccessorWithPhis(nullptr, 0);
875 }
876 return result;
877 }
878
879 bool
880 MBasicBlock::addPredecessor(TempAllocator &alloc, MBasicBlock *pred)
881 {
882 return addPredecessorPopN(alloc, pred, 0);
883 }
884
885 bool
886 MBasicBlock::addPredecessorPopN(TempAllocator &alloc, MBasicBlock *pred, uint32_t popped)
887 {
888 JS_ASSERT(pred);
889 JS_ASSERT(predecessors_.length() > 0);
890
891 // Predecessors must be finished, and at the correct stack depth.
892 JS_ASSERT(pred->lastIns_);
893 JS_ASSERT(pred->stackPosition_ == stackPosition_ + popped);
894
895 for (uint32_t i = 0; i < stackPosition_; i++) {
896 MDefinition *mine = getSlot(i);
897 MDefinition *other = pred->getSlot(i);
898
899 if (mine != other) {
900 // If the current instruction is a phi, and it was created in this
901 // basic block, then we have already placed this phi and should
902 // instead append to its operands.
903 if (mine->isPhi() && mine->block() == this) {
904 JS_ASSERT(predecessors_.length());
905 if (!mine->toPhi()->addInputSlow(other))
906 return false;
907 } else {
908 // Otherwise, create a new phi node.
909 MPhi *phi;
910 if (mine->type() == other->type())
911 phi = MPhi::New(alloc, i, mine->type());
912 else
913 phi = MPhi::New(alloc, i);
914 addPhi(phi);
915
916 // Prime the phi for each predecessor, so input(x) comes from
917 // predecessor(x).
918 if (!phi->reserveLength(predecessors_.length() + 1))
919 return false;
920
921 for (size_t j = 0; j < predecessors_.length(); j++) {
922 JS_ASSERT(predecessors_[j]->getSlot(i) == mine);
923 phi->addInput(mine);
924 }
925 phi->addInput(other);
926
927 setSlot(i, phi);
928 if (entryResumePoint())
929 entryResumePoint()->replaceOperand(i, phi);
930 }
931 }
932 }
933
934 return predecessors_.append(pred);
935 }
936
937 bool
938 MBasicBlock::addPredecessorWithoutPhis(MBasicBlock *pred)
939 {
940 // Predecessors must be finished.
941 JS_ASSERT(pred && pred->lastIns_);
942 return predecessors_.append(pred);
943 }
944
945 bool
946 MBasicBlock::addImmediatelyDominatedBlock(MBasicBlock *child)
947 {
948 return immediatelyDominated_.append(child);
949 }
950
951 void
952 MBasicBlock::assertUsesAreNotWithin(MUseIterator use, MUseIterator end)
953 {
954 #ifdef DEBUG
955 for (; use != end; use++) {
956 JS_ASSERT_IF(use->consumer()->isDefinition(),
957 use->consumer()->toDefinition()->block()->id() < id());
958 }
959 #endif
960 }
961
962 bool
963 MBasicBlock::dominates(const MBasicBlock *other) const
964 {
965 uint32_t high = domIndex() + numDominated();
966 uint32_t low = domIndex();
967 return other->domIndex() >= low && other->domIndex() <= high;
968 }
969
970 void
971 MBasicBlock::setUnreachable()
972 {
973 unreachable_ = true;
974 size_t numDom = numImmediatelyDominatedBlocks();
975 for (size_t d = 0; d < numDom; d++)
976 getImmediatelyDominatedBlock(d)->unreachable_ = true;
977 }
978
979 AbortReason
980 MBasicBlock::setBackedge(MBasicBlock *pred)
981 {
982 // Predecessors must be finished, and at the correct stack depth.
983 JS_ASSERT(lastIns_);
984 JS_ASSERT(pred->lastIns_);
985 JS_ASSERT(pred->stackDepth() == entryResumePoint()->stackDepth());
986
987 // We must be a pending loop header
988 JS_ASSERT(kind_ == PENDING_LOOP_HEADER);
989
990 bool hadTypeChange = false;
991
992 // Add exit definitions to each corresponding phi at the entry.
993 for (MPhiIterator phi = phisBegin(); phi != phisEnd(); phi++) {
994 MPhi *entryDef = *phi;
995 MDefinition *exitDef = pred->slots_[entryDef->slot()];
996
997 // Assert that we already placed phis for each slot.
998 JS_ASSERT(entryDef->block() == this);
999
1000 if (entryDef == exitDef) {
1001 // If the exit def is the same as the entry def, make a redundant
1002 // phi. Since loop headers have exactly two incoming edges, we
1003 // know that that's just the first input.
1004 //
1005 // Note that we eliminate later rather than now, to avoid any
1006 // weirdness around pending continue edges which might still hold
1007 // onto phis.
1008 exitDef = entryDef->getOperand(0);
1009 }
1010
1011 bool typeChange = false;
1012
1013 if (!entryDef->addInputSlow(exitDef, &typeChange))
1014 return AbortReason_Alloc;
1015
1016 hadTypeChange |= typeChange;
1017
1018 JS_ASSERT(entryDef->slot() < pred->stackDepth());
1019 setSlot(entryDef->slot(), entryDef);
1020 }
1021
1022 if (hadTypeChange) {
1023 for (MPhiIterator phi = phisBegin(); phi != phisEnd(); phi++)
1024 phi->removeOperand(phi->numOperands() - 1);
1025 return AbortReason_Disable;
1026 }
1027
1028 // We are now a loop header proper
1029 kind_ = LOOP_HEADER;
1030
1031 if (!predecessors_.append(pred))
1032 return AbortReason_Alloc;
1033
1034 return AbortReason_NoAbort;
1035 }
1036
1037 bool
1038 MBasicBlock::setBackedgeAsmJS(MBasicBlock *pred)
1039 {
1040 // Predecessors must be finished, and at the correct stack depth.
1041 JS_ASSERT(lastIns_);
1042 JS_ASSERT(pred->lastIns_);
1043 JS_ASSERT(stackDepth() == pred->stackDepth());
1044
1045 // We must be a pending loop header
1046 JS_ASSERT(kind_ == PENDING_LOOP_HEADER);
1047
1048 // Add exit definitions to each corresponding phi at the entry.
1049 for (MPhiIterator phi = phisBegin(); phi != phisEnd(); phi++) {
1050 MPhi *entryDef = *phi;
1051 MDefinition *exitDef = pred->getSlot(entryDef->slot());
1052
1053 // Assert that we already placed phis for each slot.
1054 JS_ASSERT(entryDef->block() == this);
1055
1056 // Assert that the phi already has the correct type.
1057 JS_ASSERT(entryDef->type() == exitDef->type());
1058 JS_ASSERT(entryDef->type() != MIRType_Value);
1059
1060 if (entryDef == exitDef) {
1061 // If the exit def is the same as the entry def, make a redundant
1062 // phi. Since loop headers have exactly two incoming edges, we
1063 // know that that's just the first input.
1064 //
1065 // Note that we eliminate later rather than now, to avoid any
1066 // weirdness around pending continue edges which might still hold
1067 // onto phis.
1068 exitDef = entryDef->getOperand(0);
1069 }
1070
1071 // MBasicBlock::NewAsmJS calls reserveLength(2) for loop header phis.
1072 entryDef->addInput(exitDef);
1073
1074 JS_ASSERT(entryDef->slot() < pred->stackDepth());
1075 setSlot(entryDef->slot(), entryDef);
1076 }
1077
1078 // We are now a loop header proper
1079 kind_ = LOOP_HEADER;
1080
1081 return predecessors_.append(pred);
1082 }
1083
1084 void
1085 MBasicBlock::clearLoopHeader()
1086 {
1087 JS_ASSERT(isLoopHeader());
1088 kind_ = NORMAL;
1089 }
1090
1091 size_t
1092 MBasicBlock::numSuccessors() const
1093 {
1094 JS_ASSERT(lastIns());
1095 return lastIns()->numSuccessors();
1096 }
1097
1098 MBasicBlock *
1099 MBasicBlock::getSuccessor(size_t index) const
1100 {
1101 JS_ASSERT(lastIns());
1102 return lastIns()->getSuccessor(index);
1103 }
1104
1105 size_t
1106 MBasicBlock::getSuccessorIndex(MBasicBlock *block) const
1107 {
1108 JS_ASSERT(lastIns());
1109 for (size_t i = 0; i < numSuccessors(); i++) {
1110 if (getSuccessor(i) == block)
1111 return i;
1112 }
1113 MOZ_ASSUME_UNREACHABLE("Invalid successor");
1114 }
1115
1116 void
1117 MBasicBlock::replaceSuccessor(size_t pos, MBasicBlock *split)
1118 {
1119 JS_ASSERT(lastIns());
1120
1121 // Note, during split-critical-edges, successors-with-phis is not yet set.
1122 // During PAA, this case is handled before we enter.
1123 JS_ASSERT_IF(successorWithPhis_, successorWithPhis_ != getSuccessor(pos));
1124
1125 lastIns()->replaceSuccessor(pos, split);
1126 }
1127
1128 void
1129 MBasicBlock::replacePredecessor(MBasicBlock *old, MBasicBlock *split)
1130 {
1131 for (size_t i = 0; i < numPredecessors(); i++) {
1132 if (getPredecessor(i) == old) {
1133 predecessors_[i] = split;
1134
1135 #ifdef DEBUG
1136 // The same block should not appear twice in the predecessor list.
1137 for (size_t j = i; j < numPredecessors(); j++)
1138 JS_ASSERT(predecessors_[j] != old);
1139 #endif
1140
1141 return;
1142 }
1143 }
1144
1145 MOZ_ASSUME_UNREACHABLE("predecessor was not found");
1146 }
1147
1148 void
1149 MBasicBlock::clearDominatorInfo()
1150 {
1151 setImmediateDominator(nullptr);
1152 immediatelyDominated_.clear();
1153 numDominated_ = 0;
1154 }
1155
1156 void
1157 MBasicBlock::removePredecessor(MBasicBlock *pred)
1158 {
1159 JS_ASSERT(numPredecessors() >= 2);
1160
1161 for (size_t i = 0; i < numPredecessors(); i++) {
1162 if (getPredecessor(i) != pred)
1163 continue;
1164
1165 // Adjust phis. Note that this can leave redundant phis
1166 // behind.
1167 if (!phisEmpty()) {
1168 JS_ASSERT(pred->successorWithPhis());
1169 JS_ASSERT(pred->positionInPhiSuccessor() == i);
1170 for (MPhiIterator iter = phisBegin(); iter != phisEnd(); iter++)
1171 iter->removeOperand(i);
1172 for (size_t j = i+1; j < numPredecessors(); j++)
1173 getPredecessor(j)->setSuccessorWithPhis(this, j - 1);
1174 }
1175
1176 // Remove from pred list.
1177 MBasicBlock **ptr = predecessors_.begin() + i;
1178 predecessors_.erase(ptr);
1179 return;
1180 }
1181
1182 MOZ_ASSUME_UNREACHABLE("predecessor was not found");
1183 }
1184
1185 void
1186 MBasicBlock::inheritPhis(MBasicBlock *header)
1187 {
1188 for (MPhiIterator iter = header->phisBegin(); iter != header->phisEnd(); iter++) {
1189 MPhi *phi = *iter;
1190 JS_ASSERT(phi->numOperands() == 2);
1191
1192 // The entry definition is always the leftmost input to the phi.
1193 MDefinition *entryDef = phi->getOperand(0);
1194 MDefinition *exitDef = getSlot(phi->slot());
1195
1196 if (entryDef != exitDef)
1197 continue;
1198
1199 // If the entryDef is the same as exitDef, then we must propagate the
1200 // phi down to this successor. This chance was missed as part of
1201 // setBackedge() because exits are not captured in resume points.
1202 setSlot(phi->slot(), phi);
1203 }
1204 }
1205
1206 bool
1207 MBasicBlock::specializePhis()
1208 {
1209 for (MPhiIterator iter = phisBegin(); iter != phisEnd(); iter++) {
1210 MPhi *phi = *iter;
1211 if (!phi->specializeType())
1212 return false;
1213 }
1214 return true;
1215 }
1216
1217 void
1218 MBasicBlock::dumpStack(FILE *fp)
1219 {
1220 #ifdef DEBUG
1221 fprintf(fp, " %-3s %-16s %-6s %-10s\n", "#", "name", "copyOf", "first/next");
1222 fprintf(fp, "-------------------------------------------\n");
1223 for (uint32_t i = 0; i < stackPosition_; i++) {
1224 fprintf(fp, " %-3d", i);
1225 fprintf(fp, " %-16p\n", (void *)slots_[i]);
1226 }
1227 #endif
1228 }
1229
1230 MTest *
1231 MBasicBlock::immediateDominatorBranch(BranchDirection *pdirection)
1232 {
1233 *pdirection = FALSE_BRANCH;
1234
1235 if (numPredecessors() != 1)
1236 return nullptr;
1237
1238 MBasicBlock *dom = immediateDominator();
1239 if (dom != getPredecessor(0))
1240 return nullptr;
1241
1242 // Look for a trailing MTest branching to this block.
1243 MInstruction *ins = dom->lastIns();
1244 if (ins->isTest()) {
1245 MTest *test = ins->toTest();
1246
1247 JS_ASSERT(test->ifTrue() == this || test->ifFalse() == this);
1248 if (test->ifTrue() == this && test->ifFalse() == this)
1249 return nullptr;
1250
1251 *pdirection = (test->ifTrue() == this) ? TRUE_BRANCH : FALSE_BRANCH;
1252 return test;
1253 }
1254
1255 return nullptr;
1256 }
1257
1258 void
1259 MIRGraph::dump(FILE *fp)
1260 {
1261 #ifdef DEBUG
1262 for (MBasicBlockIterator iter(begin()); iter != end(); iter++) {
1263 fprintf(fp, "block%d:\n", iter->id());
1264 iter->dump(fp);
1265 fprintf(fp, "\n");
1266 }
1267 #endif
1268 }
1269
1270 void
1271 MIRGraph::dump()
1272 {
1273 dump(stderr);
1274 }
1275
1276 void
1277 MBasicBlock::dump(FILE *fp)
1278 {
1279 #ifdef DEBUG
1280 for (MPhiIterator iter(phisBegin()); iter != phisEnd(); iter++) {
1281 iter->dump(fp);
1282 }
1283 for (MInstructionIterator iter(begin()); iter != end(); iter++) {
1284 iter->dump(fp);
1285 }
1286 #endif
1287 }
1288
1289 void
1290 MBasicBlock::dump()
1291 {
1292 dump(stderr);
1293 }

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial