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