1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 * vim: set ts=8 sts=2 et sw=2 tw=80:
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/ValueNumbering.h"
8
9 #include "jit/AliasAnalysis.h"
10 #include "jit/IonAnalysis.h"
11 #include "jit/JitSpewer.h"
12 #include "jit/MIRGenerator.h"
13
14 using namespace js;
15 using namespace js::jit;
16
17 /*
18 * [SMDOC] IonMonkey Value Numbering
19 *
20 * Some notes on the main algorithm here:
21 * - The SSA identifier id() is the value number. We do replaceAllUsesWith as
22 * we go, so there's always at most one visible value with a given number.
23 *
24 * - Consequently, the GVN algorithm is effectively pessimistic. This means it
25 * is not as powerful as an optimistic GVN would be, but it is simpler and
26 * faster.
27 *
28 * - We iterate in RPO, so that when visiting a block, we've already optimized
29 * and hashed all values in dominating blocks. With occasional exceptions,
30 * this allows us to do everything in a single pass.
31 *
32 * - When we do use multiple passes, we just re-run the algorithm on the whole
33 * graph instead of doing sparse propagation. This is a tradeoff to keep the
34 * algorithm simpler and lighter on inputs that don't have a lot of
35 * interesting unreachable blocks or degenerate loop induction variables, at
36 * the expense of being slower on inputs that do. The loop for this always
37 * terminates, because it only iterates when code is or will be removed, so
38 * eventually it must stop iterating.
39 *
40 * - Values are not immediately removed from the hash set when they go out of
41 * scope. Instead, we check for dominance after a lookup. If the dominance
42 * check fails, the value is removed.
43 */
44
hash(Lookup ins)45 HashNumber ValueNumberer::VisibleValues::ValueHasher::hash(Lookup ins) {
46 return ins->valueHash();
47 }
48
49 // Test whether two MDefinitions are congruent.
match(Key k,Lookup l)50 bool ValueNumberer::VisibleValues::ValueHasher::match(Key k, Lookup l) {
51 // If one of the instructions depends on a store, and the other instruction
52 // does not depend on the same store, the instructions are not congruent.
53 if (k->dependency() != l->dependency()) {
54 return false;
55 }
56
57 bool congruent =
58 k->congruentTo(l); // Ask the values themselves what they think.
59 #ifdef JS_JITSPEW
60 if (congruent != l->congruentTo(k)) {
61 JitSpew(
62 JitSpew_GVN,
63 " congruentTo relation is not symmetric between %s%u and %s%u!!",
64 k->opName(), k->id(), l->opName(), l->id());
65 }
66 #endif
67 return congruent;
68 }
69
rekey(Key & k,Key newKey)70 void ValueNumberer::VisibleValues::ValueHasher::rekey(Key& k, Key newKey) {
71 k = newKey;
72 }
73
VisibleValues(TempAllocator & alloc)74 ValueNumberer::VisibleValues::VisibleValues(TempAllocator& alloc)
75 : set_(alloc) {}
76
77 // Look up the first entry for |def|.
findLeader(const MDefinition * def) const78 ValueNumberer::VisibleValues::Ptr ValueNumberer::VisibleValues::findLeader(
79 const MDefinition* def) const {
80 return set_.lookup(def);
81 }
82
83 // Look up the first entry for |def|.
84 ValueNumberer::VisibleValues::AddPtr
findLeaderForAdd(MDefinition * def)85 ValueNumberer::VisibleValues::findLeaderForAdd(MDefinition* def) {
86 return set_.lookupForAdd(def);
87 }
88
89 // Insert a value into the set.
add(AddPtr p,MDefinition * def)90 bool ValueNumberer::VisibleValues::add(AddPtr p, MDefinition* def) {
91 return set_.add(p, def);
92 }
93
94 // Insert a value onto the set overwriting any existing entry.
overwrite(AddPtr p,MDefinition * def)95 void ValueNumberer::VisibleValues::overwrite(AddPtr p, MDefinition* def) {
96 set_.replaceKey(p, def);
97 }
98
99 // |def| will be discarded, so remove it from any sets.
forget(const MDefinition * def)100 void ValueNumberer::VisibleValues::forget(const MDefinition* def) {
101 Ptr p = set_.lookup(def);
102 if (p && *p == def) {
103 set_.remove(p);
104 }
105 }
106
107 // Clear all state.
clear()108 void ValueNumberer::VisibleValues::clear() { set_.clear(); }
109
110 #ifdef DEBUG
111 // Test whether |def| is in the set.
has(const MDefinition * def) const112 bool ValueNumberer::VisibleValues::has(const MDefinition* def) const {
113 Ptr p = set_.lookup(def);
114 return p && *p == def;
115 }
116 #endif
117
118 // Call MDefinition::justReplaceAllUsesWith, and add some GVN-specific asserts.
ReplaceAllUsesWith(MDefinition * from,MDefinition * to)119 static void ReplaceAllUsesWith(MDefinition* from, MDefinition* to) {
120 MOZ_ASSERT(from != to, "GVN shouldn't try to replace a value with itself");
121 MOZ_ASSERT(from->type() == to->type(), "Def replacement has different type");
122 MOZ_ASSERT(!to->isDiscarded(),
123 "GVN replaces an instruction by a removed instruction");
124
125 // We don't need the extra setting of ImplicitlyUsed flags that the regular
126 // replaceAllUsesWith does because we do it ourselves.
127 from->justReplaceAllUsesWith(to);
128 }
129
130 // Test whether |succ| is a successor of |block|.
HasSuccessor(const MControlInstruction * block,const MBasicBlock * succ)131 static bool HasSuccessor(const MControlInstruction* block,
132 const MBasicBlock* succ) {
133 for (size_t i = 0, e = block->numSuccessors(); i != e; ++i) {
134 if (block->getSuccessor(i) == succ) {
135 return true;
136 }
137 }
138 return false;
139 }
140
141 // Given a block which has had predecessors removed but is still reachable, test
142 // whether the block's new dominator will be closer than its old one and whether
143 // it will expose potential optimization opportunities.
ComputeNewDominator(MBasicBlock * block,MBasicBlock * old)144 static MBasicBlock* ComputeNewDominator(MBasicBlock* block, MBasicBlock* old) {
145 MBasicBlock* now = block->getPredecessor(0);
146 for (size_t i = 1, e = block->numPredecessors(); i < e; ++i) {
147 MBasicBlock* pred = block->getPredecessor(i);
148 // Note that dominators haven't been recomputed yet, so we have to check
149 // whether now dominates pred, not block.
150 while (!now->dominates(pred)) {
151 MBasicBlock* next = now->immediateDominator();
152 if (next == old) {
153 return old;
154 }
155 if (next == now) {
156 MOZ_ASSERT(block == old,
157 "Non-self-dominating block became self-dominating");
158 return block;
159 }
160 now = next;
161 }
162 }
163 MOZ_ASSERT(old != block || old != now,
164 "Missed self-dominating block staying self-dominating");
165 return now;
166 }
167
168 // Test for any defs which look potentially interesting to GVN.
BlockHasInterestingDefs(MBasicBlock * block)169 static bool BlockHasInterestingDefs(MBasicBlock* block) {
170 return !block->phisEmpty() || *block->begin() != block->lastIns();
171 }
172
173 // Walk up the dominator tree from |block| to the root and test for any defs
174 // which look potentially interesting to GVN.
ScanDominatorsForDefs(MBasicBlock * block)175 static bool ScanDominatorsForDefs(MBasicBlock* block) {
176 for (MBasicBlock* i = block;;) {
177 if (BlockHasInterestingDefs(block)) {
178 return true;
179 }
180
181 MBasicBlock* immediateDominator = i->immediateDominator();
182 if (immediateDominator == i) {
183 break;
184 }
185 i = immediateDominator;
186 }
187 return false;
188 }
189
190 // Walk up the dominator tree from |now| to |old| and test for any defs which
191 // look potentially interesting to GVN.
ScanDominatorsForDefs(MBasicBlock * now,MBasicBlock * old)192 static bool ScanDominatorsForDefs(MBasicBlock* now, MBasicBlock* old) {
193 MOZ_ASSERT(old->dominates(now),
194 "Refined dominator not dominated by old dominator");
195
196 for (MBasicBlock* i = now; i != old; i = i->immediateDominator()) {
197 if (BlockHasInterestingDefs(i)) {
198 return true;
199 }
200 }
201 return false;
202 }
203
204 // Given a block which has had predecessors removed but is still reachable, test
205 // whether the block's new dominator will be closer than its old one and whether
206 // it will expose potential optimization opportunities.
IsDominatorRefined(MBasicBlock * block)207 static bool IsDominatorRefined(MBasicBlock* block) {
208 MBasicBlock* old = block->immediateDominator();
209 MBasicBlock* now = ComputeNewDominator(block, old);
210
211 // If this block is just a goto and it doesn't dominate its destination,
212 // removing its predecessors won't refine the dominators of anything
213 // interesting.
214 MControlInstruction* control = block->lastIns();
215 if (*block->begin() == control && block->phisEmpty() && control->isGoto() &&
216 !block->dominates(control->toGoto()->target())) {
217 return false;
218 }
219
220 // We've computed block's new dominator. Test whether there are any
221 // newly-dominating definitions which look interesting.
222 if (block == old) {
223 return block != now && ScanDominatorsForDefs(now);
224 }
225 MOZ_ASSERT(block != now, "Non-self-dominating block became self-dominating");
226 return ScanDominatorsForDefs(now, old);
227 }
228
229 // |def| has just had one of its users release it. If it's now dead, enqueue it
230 // for discarding, otherwise just make note of it.
handleUseReleased(MDefinition * def,ImplicitUseOption implicitUseOption)231 bool ValueNumberer::handleUseReleased(MDefinition* def,
232 ImplicitUseOption implicitUseOption) {
233 if (IsDiscardable(def)) {
234 values_.forget(def);
235 if (!deadDefs_.append(def)) {
236 return false;
237 }
238 } else {
239 if (implicitUseOption == SetImplicitUse) {
240 def->setImplicitlyUsedUnchecked();
241 }
242 }
243 return true;
244 }
245
246 // Discard |def| and anything in its use-def subtree which is no longer needed.
discardDefsRecursively(MDefinition * def)247 bool ValueNumberer::discardDefsRecursively(MDefinition* def) {
248 MOZ_ASSERT(deadDefs_.empty(), "deadDefs_ not cleared");
249
250 return discardDef(def) && processDeadDefs();
251 }
252
253 // Assuming |resume| is unreachable, release its operands.
254 // It might be nice to integrate this code with prepareForDiscard, however GVN
255 // needs it to call handleUseReleased so that it can observe when a definition
256 // becomes unused, so it isn't trivial to do.
releaseResumePointOperands(MResumePoint * resume)257 bool ValueNumberer::releaseResumePointOperands(MResumePoint* resume) {
258 for (size_t i = 0, e = resume->numOperands(); i < e; ++i) {
259 if (!resume->hasOperand(i)) {
260 continue;
261 }
262 MDefinition* op = resume->getOperand(i);
263 resume->releaseOperand(i);
264
265 // We set the ImplicitlyUsed flag when removing resume point operands,
266 // because even though we may think we're certain that a particular
267 // branch might not be taken, the type information might be incomplete.
268 if (!handleUseReleased(op, SetImplicitUse)) {
269 return false;
270 }
271 }
272 return true;
273 }
274
275 // Assuming |phi| is dead, release and remove its operands. If an operand
276 // becomes dead, push it to the discard worklist.
releaseAndRemovePhiOperands(MPhi * phi)277 bool ValueNumberer::releaseAndRemovePhiOperands(MPhi* phi) {
278 // MPhi saves operands in a vector so we iterate in reverse.
279 for (int o = phi->numOperands() - 1; o >= 0; --o) {
280 MDefinition* op = phi->getOperand(o);
281 phi->removeOperand(o);
282 if (!handleUseReleased(op, DontSetImplicitUse)) {
283 return false;
284 }
285 }
286 return true;
287 }
288
289 // Assuming |def| is dead, release its operands. If an operand becomes dead,
290 // push it to the discard worklist.
releaseOperands(MDefinition * def)291 bool ValueNumberer::releaseOperands(MDefinition* def) {
292 for (size_t o = 0, e = def->numOperands(); o < e; ++o) {
293 MDefinition* op = def->getOperand(o);
294 def->releaseOperand(o);
295 if (!handleUseReleased(op, DontSetImplicitUse)) {
296 return false;
297 }
298 }
299 return true;
300 }
301
302 // Discard |def| and mine its operands for any subsequently dead defs.
discardDef(MDefinition * def)303 bool ValueNumberer::discardDef(MDefinition* def) {
304 #ifdef JS_JITSPEW
305 JitSpew(JitSpew_GVN, " Discarding %s %s%u",
306 def->block()->isMarked() ? "unreachable" : "dead", def->opName(),
307 def->id());
308 #endif
309 #ifdef DEBUG
310 MOZ_ASSERT(def != nextDef_, "Invalidating the MDefinition iterator");
311 if (def->block()->isMarked()) {
312 MOZ_ASSERT(!def->hasUses(), "Discarding def that still has uses");
313 } else {
314 MOZ_ASSERT(IsDiscardable(def), "Discarding non-discardable definition");
315 MOZ_ASSERT(!values_.has(def), "Discarding a definition still in the set");
316 }
317 #endif
318
319 MBasicBlock* block = def->block();
320 if (def->isPhi()) {
321 MPhi* phi = def->toPhi();
322 if (!releaseAndRemovePhiOperands(phi)) {
323 return false;
324 }
325 block->discardPhi(phi);
326 } else {
327 MInstruction* ins = def->toInstruction();
328 if (MResumePoint* resume = ins->resumePoint()) {
329 if (!releaseResumePointOperands(resume)) {
330 return false;
331 }
332 }
333 if (!releaseOperands(ins)) {
334 return false;
335 }
336 block->discardIgnoreOperands(ins);
337 }
338
339 // If that was the last definition in the block, it can be safely removed
340 // from the graph.
341 if (block->phisEmpty() && block->begin() == block->end()) {
342 MOZ_ASSERT(block->isMarked(),
343 "Reachable block lacks at least a control instruction");
344
345 // As a special case, don't remove a block which is a dominator tree
346 // root so that we don't invalidate the iterator in visitGraph. We'll
347 // check for this and remove it later.
348 if (block->immediateDominator() != block) {
349 JitSpew(JitSpew_GVN, " Block block%u is now empty; discarding",
350 block->id());
351 graph_.removeBlock(block);
352 blocksRemoved_ = true;
353 } else {
354 JitSpew(JitSpew_GVN,
355 " Dominator root block%u is now empty; will discard later",
356 block->id());
357 }
358 }
359
360 return true;
361 }
362
363 // Recursively discard all the defs on the deadDefs_ worklist.
processDeadDefs()364 bool ValueNumberer::processDeadDefs() {
365 MDefinition* nextDef = nextDef_;
366 while (!deadDefs_.empty()) {
367 MDefinition* def = deadDefs_.popCopy();
368
369 // Don't invalidate the MDefinition iterator. This is what we're going
370 // to visit next, so we won't miss anything.
371 if (def == nextDef) {
372 continue;
373 }
374
375 if (!discardDef(def)) {
376 return false;
377 }
378 }
379 return true;
380 }
381
382 // Test whether |block|, which is a loop header, has any predecessors other than
383 // |loopPred|, the loop predecessor, which it doesn't dominate.
hasNonDominatingPredecessor(MBasicBlock * block,MBasicBlock * loopPred)384 static bool hasNonDominatingPredecessor(MBasicBlock* block,
385 MBasicBlock* loopPred) {
386 MOZ_ASSERT(block->isLoopHeader());
387 MOZ_ASSERT(block->loopPredecessor() == loopPred);
388
389 for (uint32_t i = 0, e = block->numPredecessors(); i < e; ++i) {
390 MBasicBlock* pred = block->getPredecessor(i);
391 if (pred != loopPred && !block->dominates(pred)) {
392 return true;
393 }
394 }
395 return false;
396 }
397
398 // A loop is about to be made reachable only through an OSR entry into one of
399 // its nested loops. Fix everything up.
fixupOSROnlyLoop(MBasicBlock * block)400 bool ValueNumberer::fixupOSROnlyLoop(MBasicBlock* block) {
401 // Create an empty and unreachable(!) block which jumps to |block|. This
402 // allows |block| to remain marked as a loop header, so we don't have to
403 // worry about moving a different block into place as the new loop header,
404 // which is hard, especially if the OSR is into a nested loop. Doing all
405 // that would produce slightly more optimal code, but this is so
406 // extraordinarily rare that it isn't worth the complexity.
407 MBasicBlock* fake = MBasicBlock::NewFakeLoopPredecessor(graph_, block);
408 if (!fake) {
409 return false;
410 }
411 fake->setImmediateDominator(fake);
412 fake->addNumDominated(1);
413 fake->setDomIndex(fake->id());
414
415 JitSpew(JitSpew_GVN, " Created fake block%u", fake->id());
416 hasOSRFixups_ = true;
417 return true;
418 }
419
420 // Remove the CFG edge between |pred| and |block|, after releasing the phi
421 // operands on that edge and discarding any definitions consequently made dead.
removePredecessorAndDoDCE(MBasicBlock * block,MBasicBlock * pred,size_t predIndex)422 bool ValueNumberer::removePredecessorAndDoDCE(MBasicBlock* block,
423 MBasicBlock* pred,
424 size_t predIndex) {
425 MOZ_ASSERT(
426 !block->isMarked(),
427 "Block marked unreachable should have predecessors removed already");
428
429 // Before removing the predecessor edge, scan the phi operands for that edge
430 // for dead code before they get removed.
431 MOZ_ASSERT(nextDef_ == nullptr);
432 for (MPhiIterator iter(block->phisBegin()), end(block->phisEnd());
433 iter != end;) {
434 MPhi* phi = *iter++;
435 MOZ_ASSERT(!values_.has(phi),
436 "Visited phi in block having predecessor removed");
437 MOZ_ASSERT(!phi->isGuard());
438
439 MDefinition* op = phi->getOperand(predIndex);
440 phi->removeOperand(predIndex);
441
442 nextDef_ = iter != end ? *iter : nullptr;
443 if (!handleUseReleased(op, DontSetImplicitUse) || !processDeadDefs()) {
444 return false;
445 }
446
447 // If |nextDef_| became dead while we had it pinned, advance the
448 // iterator and discard it now.
449 while (nextDef_ && !nextDef_->hasUses() &&
450 !nextDef_->isGuardRangeBailouts()) {
451 phi = nextDef_->toPhi();
452 iter++;
453 nextDef_ = iter != end ? *iter : nullptr;
454 if (!discardDefsRecursively(phi)) {
455 return false;
456 }
457 }
458 }
459 nextDef_ = nullptr;
460
461 block->removePredecessorWithoutPhiOperands(pred, predIndex);
462 return true;
463 }
464
465 // Remove the CFG edge between |pred| and |block|, and if this makes |block|
466 // unreachable, mark it so, and remove the rest of its incoming edges too. And
467 // discard any instructions made dead by the entailed release of any phi
468 // operands.
removePredecessorAndCleanUp(MBasicBlock * block,MBasicBlock * pred)469 bool ValueNumberer::removePredecessorAndCleanUp(MBasicBlock* block,
470 MBasicBlock* pred) {
471 MOZ_ASSERT(!block->isMarked(),
472 "Removing predecessor on block already marked unreachable");
473
474 // We'll be removing a predecessor, so anything we know about phis in this
475 // block will be wrong.
476 for (MPhiIterator iter(block->phisBegin()), end(block->phisEnd());
477 iter != end; ++iter) {
478 values_.forget(*iter);
479 }
480
481 // If this is a loop header, test whether it will become an unreachable
482 // loop, or whether it needs special OSR-related fixups.
483 bool isUnreachableLoop = false;
484 if (block->isLoopHeader()) {
485 if (block->loopPredecessor() == pred) {
486 if (MOZ_UNLIKELY(hasNonDominatingPredecessor(block, pred))) {
487 JitSpew(JitSpew_GVN,
488 " "
489 "Loop with header block%u is now only reachable through an "
490 "OSR entry into the middle of the loop!!",
491 block->id());
492 } else {
493 // Deleting the entry into the loop makes the loop unreachable.
494 isUnreachableLoop = true;
495 JitSpew(JitSpew_GVN,
496 " "
497 "Loop with header block%u is no longer reachable",
498 block->id());
499 }
500 #ifdef JS_JITSPEW
501 } else if (block->hasUniqueBackedge() && block->backedge() == pred) {
502 JitSpew(JitSpew_GVN, " Loop with header block%u is no longer a loop",
503 block->id());
504 #endif
505 }
506 }
507
508 // Actually remove the CFG edge.
509 if (!removePredecessorAndDoDCE(block, pred,
510 block->getPredecessorIndex(pred))) {
511 return false;
512 }
513
514 // We've now edited the CFG; check to see if |block| became unreachable.
515 if (block->numPredecessors() == 0 || isUnreachableLoop) {
516 JitSpew(JitSpew_GVN, " Disconnecting block%u", block->id());
517
518 // Remove |block| from its dominator parent's subtree. This is the only
519 // immediately-dominated-block information we need to update, because
520 // everything dominated by this block is about to be swept away.
521 MBasicBlock* parent = block->immediateDominator();
522 if (parent != block) {
523 parent->removeImmediatelyDominatedBlock(block);
524 }
525
526 // Completely disconnect it from the CFG. We do this now rather than
527 // just doing it later when we arrive there in visitUnreachableBlock
528 // so that we don't leave a partially broken loop sitting around. This
529 // also lets visitUnreachableBlock assert that numPredecessors() == 0,
530 // which is a nice invariant.
531 if (block->isLoopHeader()) {
532 block->clearLoopHeader();
533 }
534 for (size_t i = 0, e = block->numPredecessors(); i < e; ++i) {
535 if (!removePredecessorAndDoDCE(block, block->getPredecessor(i), i)) {
536 return false;
537 }
538 }
539
540 // Clear out the resume point operands, as they can hold things that
541 // don't appear to dominate them live.
542 if (MResumePoint* resume = block->entryResumePoint()) {
543 if (!releaseResumePointOperands(resume) || !processDeadDefs()) {
544 return false;
545 }
546 if (MResumePoint* outer = block->outerResumePoint()) {
547 if (!releaseResumePointOperands(outer) || !processDeadDefs()) {
548 return false;
549 }
550 }
551 MOZ_ASSERT(nextDef_ == nullptr);
552 for (MInstructionIterator iter(block->begin()), end(block->end());
553 iter != end;) {
554 MInstruction* ins = *iter++;
555 nextDef_ = iter != end ? *iter : nullptr;
556 if (MResumePoint* resume = ins->resumePoint()) {
557 if (!releaseResumePointOperands(resume) || !processDeadDefs()) {
558 return false;
559 }
560 }
561 }
562 nextDef_ = nullptr;
563 } else {
564 #ifdef DEBUG
565 MOZ_ASSERT(block->outerResumePoint() == nullptr,
566 "Outer resume point in block without an entry resume point");
567 for (MInstructionIterator iter(block->begin()), end(block->end());
568 iter != end; ++iter) {
569 MOZ_ASSERT(iter->resumePoint() == nullptr,
570 "Instruction with resume point in block without entry "
571 "resume point");
572 }
573 #endif
574 }
575
576 // Use the mark to note that we've already removed all its predecessors,
577 // and we know it's unreachable.
578 block->mark();
579 }
580
581 return true;
582 }
583
584 // Return a simplified form of |def|, if we can.
simplified(MDefinition * def) const585 MDefinition* ValueNumberer::simplified(MDefinition* def) const {
586 return def->foldsTo(graph_.alloc());
587 }
588
589 // If an equivalent and dominating value already exists in the set, return it.
590 // Otherwise insert |def| into the set and return it.
leader(MDefinition * def)591 MDefinition* ValueNumberer::leader(MDefinition* def) {
592 // If the value isn't suitable for eliminating, don't bother hashing it. The
593 // convention is that congruentTo returns false for node kinds that wish to
594 // opt out of redundance elimination.
595 // TODO: It'd be nice to clean up that convention (bug 1031406).
596 if (!def->isEffectful() && def->congruentTo(def)) {
597 // Look for a match.
598 VisibleValues::AddPtr p = values_.findLeaderForAdd(def);
599 if (p) {
600 MDefinition* rep = *p;
601 if (!rep->isDiscarded() && rep->block()->dominates(def->block())) {
602 // We found a dominating congruent value.
603 return rep;
604 }
605
606 // The congruent value doesn't dominate. It never will again in this
607 // dominator tree, so overwrite it.
608 values_.overwrite(p, def);
609 } else {
610 // No match. Add a new entry.
611 if (!values_.add(p, def)) {
612 return nullptr;
613 }
614 }
615
616 #ifdef JS_JITSPEW
617 JitSpew(JitSpew_GVN, " Recording %s%u", def->opName(), def->id());
618 #endif
619 }
620
621 return def;
622 }
623
624 // Test whether |phi| is dominated by a congruent phi.
hasLeader(const MPhi * phi,const MBasicBlock * phiBlock) const625 bool ValueNumberer::hasLeader(const MPhi* phi,
626 const MBasicBlock* phiBlock) const {
627 if (VisibleValues::Ptr p = values_.findLeader(phi)) {
628 const MDefinition* rep = *p;
629 return rep != phi && rep->block()->dominates(phiBlock);
630 }
631 return false;
632 }
633
634 // Test whether there are any phis in |header| which are newly optimizable, as a
635 // result of optimizations done inside the loop. This is not a sparse approach,
636 // but restarting is rare enough in practice. Termination is ensured by
637 // discarding the phi triggering the iteration.
loopHasOptimizablePhi(MBasicBlock * header) const638 bool ValueNumberer::loopHasOptimizablePhi(MBasicBlock* header) const {
639 // If the header is unreachable, don't bother re-optimizing it.
640 if (header->isMarked()) {
641 return false;
642 }
643
644 // Rescan the phis for any that can be simplified, since they may be reading
645 // values from backedges.
646 for (MPhiIterator iter(header->phisBegin()), end(header->phisEnd());
647 iter != end; ++iter) {
648 MPhi* phi = *iter;
649 MOZ_ASSERT_IF(!phi->hasUses(), !DeadIfUnused(phi));
650
651 if (phi->operandIfRedundant() || hasLeader(phi, header)) {
652 return true; // Phi can be simplified.
653 }
654 }
655 return false;
656 }
657
658 // Visit |def|.
visitDefinition(MDefinition * def)659 bool ValueNumberer::visitDefinition(MDefinition* def) {
660 // Nop does not fit in any of the previous optimization, as its only purpose
661 // is to reduce the register pressure by keeping additional resume
662 // point. Still, there is no need consecutive list of MNop instructions, and
663 // this will slow down every other iteration on the Graph.
664 if (def->isNop()) {
665 MNop* nop = def->toNop();
666 MBasicBlock* block = nop->block();
667
668 // We look backward to know if we can remove the previous Nop, we do not
669 // look forward as we would not benefit from the folding made by GVN.
670 MInstructionReverseIterator iter = ++block->rbegin(nop);
671
672 // This nop is at the beginning of the basic block, just replace the
673 // resume point of the basic block by the one from the resume point.
674 if (iter == block->rend()) {
675 JitSpew(JitSpew_GVN, " Removing Nop%u", nop->id());
676 nop->moveResumePointAsEntry();
677 block->discard(nop);
678 return true;
679 }
680
681 // The previous instruction is also a Nop, no need to keep it anymore.
682 MInstruction* prev = *iter;
683 if (prev->isNop()) {
684 JitSpew(JitSpew_GVN, " Removing Nop%u", prev->id());
685 block->discard(prev);
686 return true;
687 }
688
689 // The Nop is introduced to capture the result and make sure the operands
690 // are not live anymore when there are no further uses. Though when
691 // all operands are still needed the Nop doesn't decrease the liveness
692 // and can get removed.
693 MResumePoint* rp = nop->resumePoint();
694 if (rp && rp->numOperands() > 0 &&
695 rp->getOperand(rp->numOperands() - 1) == prev &&
696 !nop->block()->lastIns()->isThrow() &&
697 !prev->isAssertRecoveredOnBailout()) {
698 size_t numOperandsLive = 0;
699 for (size_t j = 0; j < prev->numOperands(); j++) {
700 for (size_t i = 0; i < rp->numOperands(); i++) {
701 if (prev->getOperand(j) == rp->getOperand(i)) {
702 numOperandsLive++;
703 break;
704 }
705 }
706 }
707
708 if (numOperandsLive == prev->numOperands()) {
709 JitSpew(JitSpew_GVN, " Removing Nop%u", nop->id());
710 block->discard(nop);
711 }
712 }
713
714 return true;
715 }
716
717 // Skip optimizations on instructions which are recovered on bailout, to
718 // avoid mixing instructions which are recovered on bailouts with
719 // instructions which are not.
720 if (def->isRecoveredOnBailout()) {
721 return true;
722 }
723
724 // If this instruction has a dependency() into an unreachable block, we'll
725 // need to update AliasAnalysis.
726 MDefinition* dep = def->dependency();
727 if (dep != nullptr && (dep->isDiscarded() || dep->block()->isDead())) {
728 JitSpew(JitSpew_GVN, " AliasAnalysis invalidated");
729 if (updateAliasAnalysis_ && !dependenciesBroken_) {
730 // TODO: Recomputing alias-analysis could theoretically expose more
731 // GVN opportunities.
732 JitSpew(JitSpew_GVN, " Will recompute!");
733 dependenciesBroken_ = true;
734 }
735 // Temporarily clear its dependency, to protect foldsTo, which may
736 // wish to use the dependency to do store-to-load forwarding.
737 def->setDependency(def->toInstruction());
738 } else {
739 dep = nullptr;
740 }
741
742 // Look for a simplified form of |def|.
743 MDefinition* sim = simplified(def);
744 if (sim != def) {
745 if (sim == nullptr) {
746 return false;
747 }
748
749 bool isNewInstruction = sim->block() == nullptr;
750
751 // If |sim| doesn't belong to a block, insert it next to |def|.
752 if (isNewInstruction) {
753 def->block()->insertAfter(def->toInstruction(), sim->toInstruction());
754 }
755
756 #ifdef JS_JITSPEW
757 JitSpew(JitSpew_GVN, " Folded %s%u to %s%u", def->opName(), def->id(),
758 sim->opName(), sim->id());
759 #endif
760 MOZ_ASSERT(!sim->isDiscarded());
761 ReplaceAllUsesWith(def, sim);
762
763 // The node's foldsTo said |def| can be replaced by |rep|. If |def| is a
764 // guard, then either |rep| is also a guard, or a guard isn't actually
765 // needed, so we can clear |def|'s guard flag and let it be discarded.
766 def->setNotGuardUnchecked();
767
768 if (def->isGuardRangeBailouts()) {
769 sim->setGuardRangeBailoutsUnchecked();
770 }
771
772 if (sim->bailoutKind() == BailoutKind::Unknown) {
773 sim->setBailoutKind(def->bailoutKind());
774 }
775
776 if (DeadIfUnused(def)) {
777 if (!discardDefsRecursively(def)) {
778 return false;
779 }
780
781 // If that ended up discarding |sim|, then we're done here.
782 if (sim->isDiscarded()) {
783 return true;
784 }
785 }
786
787 if (!rerun_ && def->isPhi() && !sim->isPhi()) {
788 rerun_ = true;
789 JitSpew(JitSpew_GVN,
790 " Replacing phi%u may have enabled cascading optimisations; "
791 "will re-run",
792 def->id());
793 }
794
795 // Otherwise, procede to optimize with |sim| in place of |def|.
796 def = sim;
797
798 // If the simplified instruction was already part of the graph, then we
799 // probably already visited and optimized this instruction.
800 if (!isNewInstruction) {
801 return true;
802 }
803 }
804
805 // Now that foldsTo is done, re-enable the original dependency. Even though
806 // it may be pointing into a discarded block, it's still valid for the
807 // purposes of detecting congruent loads.
808 if (dep != nullptr) {
809 def->setDependency(dep);
810 }
811
812 // Look for a dominating def which makes |def| redundant.
813 MDefinition* rep = leader(def);
814 if (rep != def) {
815 if (rep == nullptr) {
816 return false;
817 }
818 if (rep->updateForReplacement(def)) {
819 #ifdef JS_JITSPEW
820 JitSpew(JitSpew_GVN, " Replacing %s%u with %s%u", def->opName(),
821 def->id(), rep->opName(), rep->id());
822 #endif
823 ReplaceAllUsesWith(def, rep);
824
825 // The node's congruentTo said |def| is congruent to |rep|, and it's
826 // dominated by |rep|. If |def| is a guard, it's covered by |rep|,
827 // so we can clear |def|'s guard flag and let it be discarded.
828 def->setNotGuardUnchecked();
829
830 if (DeadIfUnused(def)) {
831 // discardDef should not add anything to the deadDefs, as the
832 // redundant operation should have the same input operands.
833 mozilla::DebugOnly<bool> r = discardDef(def);
834 MOZ_ASSERT(
835 r,
836 "discardDef shouldn't have tried to add anything to the worklist, "
837 "so it shouldn't have failed");
838 MOZ_ASSERT(deadDefs_.empty(),
839 "discardDef shouldn't have added anything to the worklist");
840 }
841 def = rep;
842 }
843 }
844
845 return true;
846 }
847
848 // Visit the control instruction at the end of |block|.
visitControlInstruction(MBasicBlock * block)849 bool ValueNumberer::visitControlInstruction(MBasicBlock* block) {
850 // Look for a simplified form of the control instruction.
851 MControlInstruction* control = block->lastIns();
852 MDefinition* rep = simplified(control);
853 if (rep == control) {
854 return true;
855 }
856
857 if (rep == nullptr) {
858 return false;
859 }
860
861 MControlInstruction* newControl = rep->toControlInstruction();
862 MOZ_ASSERT(!newControl->block(),
863 "Control instruction replacement shouldn't already be in a block");
864 #ifdef JS_JITSPEW
865 JitSpew(JitSpew_GVN, " Folded control instruction %s%u to %s%u",
866 control->opName(), control->id(), newControl->opName(),
867 graph_.getNumInstructionIds());
868 #endif
869
870 // If the simplification removes any CFG edges, update the CFG and remove
871 // any blocks that become dead.
872 size_t oldNumSuccs = control->numSuccessors();
873 size_t newNumSuccs = newControl->numSuccessors();
874 if (newNumSuccs != oldNumSuccs) {
875 MOZ_ASSERT(newNumSuccs < oldNumSuccs,
876 "New control instruction has too many successors");
877 for (size_t i = 0; i != oldNumSuccs; ++i) {
878 MBasicBlock* succ = control->getSuccessor(i);
879 if (HasSuccessor(newControl, succ)) {
880 continue;
881 }
882 if (succ->isMarked()) {
883 continue;
884 }
885 if (!removePredecessorAndCleanUp(succ, block)) {
886 return false;
887 }
888 if (succ->isMarked()) {
889 continue;
890 }
891 if (!rerun_) {
892 if (!remainingBlocks_.append(succ)) {
893 return false;
894 }
895 }
896 }
897 }
898
899 if (!releaseOperands(control)) {
900 return false;
901 }
902 block->discardIgnoreOperands(control);
903 block->end(newControl);
904 if (block->entryResumePoint() && newNumSuccs != oldNumSuccs) {
905 block->flagOperandsOfPrunedBranches(newControl);
906 }
907 return processDeadDefs();
908 }
909
910 // |block| is unreachable. Mine it for opportunities to delete more dead
911 // code, and then discard it.
visitUnreachableBlock(MBasicBlock * block)912 bool ValueNumberer::visitUnreachableBlock(MBasicBlock* block) {
913 JitSpew(JitSpew_GVN, " Visiting unreachable block%u%s%s%s", block->id(),
914 block->isLoopHeader() ? " (loop header)" : "",
915 block->isSplitEdge() ? " (split edge)" : "",
916 block->immediateDominator() == block ? " (dominator root)" : "");
917
918 MOZ_ASSERT(block->isMarked(),
919 "Visiting unmarked (and therefore reachable?) block");
920 MOZ_ASSERT(block->numPredecessors() == 0,
921 "Block marked unreachable still has predecessors");
922 MOZ_ASSERT(block != graph_.entryBlock(), "Removing normal entry block");
923 MOZ_ASSERT(block != graph_.osrBlock(), "Removing OSR entry block");
924 MOZ_ASSERT(deadDefs_.empty(), "deadDefs_ not cleared");
925
926 // Disconnect all outgoing CFG edges.
927 for (size_t i = 0, e = block->numSuccessors(); i < e; ++i) {
928 MBasicBlock* succ = block->getSuccessor(i);
929 if (succ->isDead() || succ->isMarked()) {
930 continue;
931 }
932 if (!removePredecessorAndCleanUp(succ, block)) {
933 return false;
934 }
935 if (succ->isMarked()) {
936 continue;
937 }
938 // |succ| is still reachable. Make a note of it so that we can scan
939 // it for interesting dominator tree changes later.
940 if (!rerun_) {
941 if (!remainingBlocks_.append(succ)) {
942 return false;
943 }
944 }
945 }
946
947 // Discard any instructions with no uses. The remaining instructions will be
948 // discarded when their last use is discarded.
949 MOZ_ASSERT(nextDef_ == nullptr);
950 for (MDefinitionIterator iter(block); iter;) {
951 MDefinition* def = *iter++;
952 if (def->hasUses()) {
953 continue;
954 }
955 nextDef_ = iter ? *iter : nullptr;
956 if (!discardDefsRecursively(def)) {
957 return false;
958 }
959 }
960
961 nextDef_ = nullptr;
962 MControlInstruction* control = block->lastIns();
963 return discardDefsRecursively(control);
964 }
965
966 // Visit all the phis and instructions |block|.
visitBlock(MBasicBlock * block)967 bool ValueNumberer::visitBlock(MBasicBlock* block) {
968 MOZ_ASSERT(!block->isMarked(), "Blocks marked unreachable during GVN");
969 MOZ_ASSERT(!block->isDead(), "Block to visit is already dead");
970
971 JitSpew(JitSpew_GVN, " Visiting block%u", block->id());
972
973 // Visit the definitions in the block top-down.
974 MOZ_ASSERT(nextDef_ == nullptr);
975 for (MDefinitionIterator iter(block); iter;) {
976 if (!graph_.alloc().ensureBallast()) {
977 return false;
978 }
979 MDefinition* def = *iter++;
980
981 // Remember where our iterator is so that we don't invalidate it.
982 nextDef_ = iter ? *iter : nullptr;
983
984 // If the definition is dead, discard it.
985 if (IsDiscardable(def)) {
986 if (!discardDefsRecursively(def)) {
987 return false;
988 }
989 continue;
990 }
991
992 if (!visitDefinition(def)) {
993 return false;
994 }
995 }
996 nextDef_ = nullptr;
997
998 if (!graph_.alloc().ensureBallast()) {
999 return false;
1000 }
1001
1002 return visitControlInstruction(block);
1003 }
1004
1005 // Visit all the blocks dominated by dominatorRoot.
visitDominatorTree(MBasicBlock * dominatorRoot)1006 bool ValueNumberer::visitDominatorTree(MBasicBlock* dominatorRoot) {
1007 JitSpew(JitSpew_GVN,
1008 " Visiting dominator tree (with %" PRIu64
1009 " blocks) rooted at block%u%s",
1010 uint64_t(dominatorRoot->numDominated()), dominatorRoot->id(),
1011 dominatorRoot == graph_.entryBlock() ? " (normal entry block)"
1012 : dominatorRoot == graph_.osrBlock() ? " (OSR entry block)"
1013 : dominatorRoot->numPredecessors() == 0
1014 ? " (odd unreachable block)"
1015 : " (merge point from normal entry and OSR entry)");
1016 MOZ_ASSERT(dominatorRoot->immediateDominator() == dominatorRoot,
1017 "root is not a dominator tree root");
1018
1019 // Visit all blocks dominated by dominatorRoot, in RPO. This has the nice
1020 // property that we'll always visit a block before any block it dominates,
1021 // so we can make a single pass through the list and see every full
1022 // redundance.
1023 size_t numVisited = 0;
1024 size_t numDiscarded = 0;
1025 for (ReversePostorderIterator iter(graph_.rpoBegin(dominatorRoot));;) {
1026 MOZ_ASSERT(iter != graph_.rpoEnd(), "Inconsistent dominator information");
1027 MBasicBlock* block = *iter++;
1028 // We're only visiting blocks in dominatorRoot's tree right now.
1029 if (!dominatorRoot->dominates(block)) {
1030 continue;
1031 }
1032
1033 // If this is a loop backedge, remember the header, as we may not be able
1034 // to find it after we simplify the block.
1035 MBasicBlock* header =
1036 block->isLoopBackedge() ? block->loopHeaderOfBackedge() : nullptr;
1037
1038 if (block->isMarked()) {
1039 // This block has become unreachable; handle it specially.
1040 if (!visitUnreachableBlock(block)) {
1041 return false;
1042 }
1043 ++numDiscarded;
1044 } else {
1045 // Visit the block!
1046 if (!visitBlock(block)) {
1047 return false;
1048 }
1049 ++numVisited;
1050 }
1051
1052 // If the block is/was a loop backedge, check to see if the block that
1053 // is/was its header has optimizable phis, which would want a re-run.
1054 if (!rerun_ && header && loopHasOptimizablePhi(header)) {
1055 JitSpew(JitSpew_GVN,
1056 " Loop phi in block%u can now be optimized; will re-run GVN!",
1057 header->id());
1058 rerun_ = true;
1059 remainingBlocks_.clear();
1060 }
1061
1062 MOZ_ASSERT(numVisited <= dominatorRoot->numDominated() - numDiscarded,
1063 "Visited blocks too many times");
1064 if (numVisited >= dominatorRoot->numDominated() - numDiscarded) {
1065 break;
1066 }
1067 }
1068
1069 totalNumVisited_ += numVisited;
1070 values_.clear();
1071 return true;
1072 }
1073
1074 // Visit all the blocks in the graph.
visitGraph()1075 bool ValueNumberer::visitGraph() {
1076 // Due to OSR blocks, the set of blocks dominated by a blocks may not be
1077 // contiguous in the RPO. Do a separate traversal for each dominator tree
1078 // root. There's always the main entry, and sometimes there's an OSR entry,
1079 // and then there are the roots formed where the OSR paths merge with the
1080 // main entry paths.
1081 for (ReversePostorderIterator iter(graph_.rpoBegin());;) {
1082 MOZ_ASSERT(iter != graph_.rpoEnd(), "Inconsistent dominator information");
1083 MBasicBlock* block = *iter;
1084 if (block->immediateDominator() == block) {
1085 if (!visitDominatorTree(block)) {
1086 return false;
1087 }
1088
1089 // Normally unreachable blocks would be removed by now, but if this
1090 // block is a dominator tree root, it has been special-cased and left
1091 // in place in order to avoid invalidating our iterator. Now that
1092 // we've finished the tree, increment the iterator, and then if it's
1093 // marked for removal, remove it.
1094 ++iter;
1095 if (block->isMarked()) {
1096 JitSpew(JitSpew_GVN, " Discarding dominator root block%u",
1097 block->id());
1098 MOZ_ASSERT(
1099 block->begin() == block->end(),
1100 "Unreachable dominator tree root has instructions after tree walk");
1101 MOZ_ASSERT(block->phisEmpty(),
1102 "Unreachable dominator tree root has phis after tree walk");
1103 graph_.removeBlock(block);
1104 blocksRemoved_ = true;
1105 }
1106
1107 MOZ_ASSERT(totalNumVisited_ <= graph_.numBlocks(),
1108 "Visited blocks too many times");
1109 if (totalNumVisited_ >= graph_.numBlocks()) {
1110 break;
1111 }
1112 } else {
1113 // This block a dominator tree root. Proceed to the next one.
1114 ++iter;
1115 }
1116 }
1117 totalNumVisited_ = 0;
1118 return true;
1119 }
1120
insertOSRFixups()1121 bool ValueNumberer::insertOSRFixups() {
1122 ReversePostorderIterator end(graph_.end());
1123 for (ReversePostorderIterator iter(graph_.begin()); iter != end;) {
1124 MBasicBlock* block = *iter++;
1125
1126 // Only add fixup block above for loops which can be reached from OSR.
1127 if (!block->isLoopHeader()) {
1128 continue;
1129 }
1130
1131 // If the loop header is not self-dominated, then this loop does not
1132 // have to deal with a second entry point, so there is no need to add a
1133 // second entry point with a fixup block.
1134 if (block->immediateDominator() != block) {
1135 continue;
1136 }
1137
1138 if (!fixupOSROnlyLoop(block)) {
1139 return false;
1140 }
1141 }
1142
1143 return true;
1144 }
1145
1146 // OSR fixups serve the purpose of representing the non-OSR entry into a loop
1147 // when the only real entry is an OSR entry into the middle. However, if the
1148 // entry into the middle is subsequently folded away, the loop may actually
1149 // have become unreachable. Mark-and-sweep all blocks to remove all such code.
cleanupOSRFixups()1150 bool ValueNumberer::cleanupOSRFixups() {
1151 // Mark.
1152 Vector<MBasicBlock*, 0, JitAllocPolicy> worklist(graph_.alloc());
1153 unsigned numMarked = 2;
1154 graph_.entryBlock()->mark();
1155 graph_.osrBlock()->mark();
1156 if (!worklist.append(graph_.entryBlock()) ||
1157 !worklist.append(graph_.osrBlock())) {
1158 return false;
1159 }
1160 while (!worklist.empty()) {
1161 MBasicBlock* block = worklist.popCopy();
1162 for (size_t i = 0, e = block->numSuccessors(); i != e; ++i) {
1163 MBasicBlock* succ = block->getSuccessor(i);
1164 if (!succ->isMarked()) {
1165 ++numMarked;
1166 succ->mark();
1167 if (!worklist.append(succ)) {
1168 return false;
1169 }
1170 } else if (succ->isLoopHeader() && succ->loopPredecessor() == block &&
1171 succ->numPredecessors() == 3) {
1172 // Unmark fixup blocks if the loop predecessor is marked after
1173 // the loop header.
1174 succ->getPredecessor(1)->unmarkUnchecked();
1175 }
1176 }
1177
1178 // OSR fixup blocks are needed if and only if the loop header is
1179 // reachable from its backedge (via the OSR block) and not from its
1180 // original loop predecessor.
1181 //
1182 // Thus OSR fixup blocks are removed if the loop header is not
1183 // reachable, or if the loop header is reachable from both its backedge
1184 // and its original loop predecessor.
1185 if (block->isLoopHeader()) {
1186 MBasicBlock* maybeFixupBlock = nullptr;
1187 if (block->numPredecessors() == 2) {
1188 maybeFixupBlock = block->getPredecessor(0);
1189 } else {
1190 MOZ_ASSERT(block->numPredecessors() == 3);
1191 if (!block->loopPredecessor()->isMarked()) {
1192 maybeFixupBlock = block->getPredecessor(1);
1193 }
1194 }
1195
1196 if (maybeFixupBlock && !maybeFixupBlock->isMarked() &&
1197 maybeFixupBlock->numPredecessors() == 0) {
1198 MOZ_ASSERT(maybeFixupBlock->numSuccessors() == 1,
1199 "OSR fixup block should have exactly one successor");
1200 MOZ_ASSERT(maybeFixupBlock != graph_.entryBlock(),
1201 "OSR fixup block shouldn't be the entry block");
1202 MOZ_ASSERT(maybeFixupBlock != graph_.osrBlock(),
1203 "OSR fixup block shouldn't be the OSR entry block");
1204 maybeFixupBlock->mark();
1205 }
1206 }
1207 }
1208
1209 // And sweep.
1210 return RemoveUnmarkedBlocks(mir_, graph_, numMarked);
1211 }
1212
ValueNumberer(MIRGenerator * mir,MIRGraph & graph)1213 ValueNumberer::ValueNumberer(MIRGenerator* mir, MIRGraph& graph)
1214 : mir_(mir),
1215 graph_(graph),
1216 // Initialize the value set. It's tempting to pass in a length that is a
1217 // function of graph_.getNumInstructionIds(). But if we start out with a
1218 // large capacity, it will be far larger than the actual element count for
1219 // most of the pass, so when we remove elements, it would often think it
1220 // needs to compact itself. Empirically, just letting the HashTable grow
1221 // as needed on its own seems to work pretty well.
1222 values_(graph.alloc()),
1223 deadDefs_(graph.alloc()),
1224 remainingBlocks_(graph.alloc()),
1225 nextDef_(nullptr),
1226 totalNumVisited_(0),
1227 rerun_(false),
1228 blocksRemoved_(false),
1229 updateAliasAnalysis_(false),
1230 dependenciesBroken_(false),
1231 hasOSRFixups_(false) {}
1232
run(UpdateAliasAnalysisFlag updateAliasAnalysis)1233 bool ValueNumberer::run(UpdateAliasAnalysisFlag updateAliasAnalysis) {
1234 updateAliasAnalysis_ = updateAliasAnalysis == UpdateAliasAnalysis;
1235
1236 JitSpew(JitSpew_GVN, "Running GVN on graph (with %" PRIu64 " blocks)",
1237 uint64_t(graph_.numBlocks()));
1238
1239 // Adding fixup blocks only make sense iff we have a second entry point into
1240 // the graph which cannot be reached any more from the entry point.
1241 if (graph_.osrBlock()) {
1242 if (!insertOSRFixups()) {
1243 return false;
1244 }
1245 }
1246
1247 // Top level non-sparse iteration loop. If an iteration performs a
1248 // significant change, such as discarding a block which changes the
1249 // dominator tree and may enable more optimization, this loop takes another
1250 // iteration.
1251 int runs = 0;
1252 for (;;) {
1253 if (!visitGraph()) {
1254 return false;
1255 }
1256
1257 // Test whether any block which was not removed but which had at least
1258 // one predecessor removed will have a new dominator parent.
1259 while (!remainingBlocks_.empty()) {
1260 MBasicBlock* block = remainingBlocks_.popCopy();
1261 if (!block->isDead() && IsDominatorRefined(block)) {
1262 JitSpew(JitSpew_GVN,
1263 " Dominator for block%u can now be refined; will re-run GVN!",
1264 block->id());
1265 rerun_ = true;
1266 remainingBlocks_.clear();
1267 break;
1268 }
1269 }
1270
1271 if (blocksRemoved_) {
1272 if (!AccountForCFGChanges(mir_, graph_, dependenciesBroken_,
1273 /* underValueNumberer = */ true)) {
1274 return false;
1275 }
1276
1277 blocksRemoved_ = false;
1278 dependenciesBroken_ = false;
1279 }
1280
1281 if (mir_->shouldCancel("GVN (outer loop)")) {
1282 return false;
1283 }
1284
1285 // If no further opportunities have been discovered, we're done.
1286 if (!rerun_) {
1287 break;
1288 }
1289
1290 rerun_ = false;
1291
1292 // Enforce an arbitrary iteration limit. This is rarely reached, and
1293 // isn't even strictly necessary, as the algorithm is guaranteed to
1294 // terminate on its own in a finite amount of time (since every time we
1295 // re-run we discard the construct which triggered the re-run), but it
1296 // does help avoid slow compile times on pathological code.
1297 ++runs;
1298 if (runs == 6) {
1299 JitSpew(JitSpew_GVN, "Re-run cutoff of %d reached. Terminating GVN!",
1300 runs);
1301 break;
1302 }
1303
1304 JitSpew(JitSpew_GVN,
1305 "Re-running GVN on graph (run %d, now with %" PRIu64 " blocks)",
1306 runs, uint64_t(graph_.numBlocks()));
1307 }
1308
1309 if (MOZ_UNLIKELY(hasOSRFixups_)) {
1310 if (!cleanupOSRFixups()) {
1311 return false;
1312 }
1313 hasOSRFixups_ = false;
1314 }
1315
1316 return true;
1317 }
1318