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