Bug 1029830 - IonMonkey: GVN: Say "discard" instead of "delete" r=nbp
authorDan Gohman <sunfish@mozilla.com>
Wed, 17 Sep 2014 10:27:24 -0700
changeset 205738 f212bee81c3ce73390ec63c0e6ee02ef9e41f522
parent 205737 2079c454f90817279f650f251512638c1c28dfc1
child 205739 f7f1732c82097f169fc862bb6979527c9ae0ad36
push id49264
push userdgohman@mozilla.com
push dateWed, 17 Sep 2014 17:27:46 +0000
treeherdermozilla-inbound@ce0a75f9481b [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersnbp
bugs1029830
milestone35.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1029830 - IonMonkey: GVN: Say "discard" instead of "delete" r=nbp
js/src/jit/ValueNumbering.cpp
js/src/jit/ValueNumbering.h
--- a/js/src/jit/ValueNumbering.cpp
+++ b/js/src/jit/ValueNumbering.cpp
@@ -100,17 +100,17 @@ ValueNumberer::VisibleValues::add(AddPtr
 
 // Insert a value onto the set overwriting any existing entry.
 void
 ValueNumberer::VisibleValues::overwrite(AddPtr p, MDefinition *def)
 {
     set_.rekeyInPlace(p, def);
 }
 
-// The given def will be deleted, so remove it from any sets.
+// The given def will be discarded, so remove it from any sets.
 void
 ValueNumberer::VisibleValues::forget(const MDefinition *def)
 {
     Ptr p = set_.lookup(def);
     if (p && *p == def)
         set_.remove(p);
 }
 
@@ -210,26 +210,26 @@ IsDominatorRefined(MBasicBlock *block)
     for (MBasicBlock *i = now; i != old; i = i->immediateDominator()) {
         if (!i->phisEmpty() || *i->begin() != i->lastIns())
             return true;
     }
 
     return false;
 }
 
-// Delete the given instruction and anything in its use-def subtree which is no
+// Discard the given instruction and anything in its use-def subtree which is no
 // longer needed.
 bool
-ValueNumberer::deleteDefsRecursively(MDefinition *def)
+ValueNumberer::discardDefsRecursively(MDefinition *def)
 {
-    return deleteDef(def) && processDeadDefs();
+    return discardDef(def) && processDeadDefs();
 }
 
 // Assuming phi is dead, release its operands. If an operand which is not
-// dominated by the phi becomes dead, push it to the delete worklist.
+// dominated by the phi becomes dead, push it to the discard worklist.
 bool
 ValueNumberer::releasePhiOperands(MPhi *phi, const MBasicBlock *phiBlock,
                                   UseRemovedOption useRemovedOption)
 {
     // MPhi saves operands in a vector so we iterate in reverse.
     for (int o = phi->numOperands() - 1; o >= 0; --o) {
         MDefinition *op = phi->getOperand(o);
         phi->removeOperand(o);
@@ -240,17 +240,17 @@ ValueNumberer::releasePhiOperands(MPhi *
             if (useRemovedOption == SetUseRemoved)
                 op->setUseRemovedUnchecked();
         }
     }
     return true;
 }
 
 // Assuming ins is dead, release its operands. If an operand becomes dead, push
-// it to the delete worklist.
+// it to the discard worklist.
 bool
 ValueNumberer::releaseInsOperands(MInstruction *ins,
                                   UseRemovedOption useRemovedOption)
 {
     for (size_t o = 0, e = ins->numOperands(); o != e; ++o) {
         MDefinition *op = ins->getOperand(o);
         ins->releaseOperand(o);
         if (IsDead(op)) {
@@ -260,22 +260,22 @@ ValueNumberer::releaseInsOperands(MInstr
             if (useRemovedOption == SetUseRemoved)
                 op->setUseRemovedUnchecked();
         }
     }
     return true;
 }
 
 bool
-ValueNumberer::deleteDef(MDefinition *def,
+ValueNumberer::discardDef(MDefinition *def,
                          UseRemovedOption useRemovedOption)
 {
-    JitSpew(JitSpew_GVN, "    Deleting %s%u", def->opName(), def->id());
-    MOZ_ASSERT(IsDead(def), "Deleting non-dead definition");
-    MOZ_ASSERT(!values_.has(def), "Deleting an instruction still in the set");
+    JitSpew(JitSpew_GVN, "    Discarding %s%u", def->opName(), def->id());
+    MOZ_ASSERT(IsDead(def), "Discarding non-dead definition");
+    MOZ_ASSERT(!values_.has(def), "Discarding an instruction still in the set");
 
     if (def->isPhi()) {
         MPhi *phi = def->toPhi();
         MBasicBlock *phiBlock = phi->block();
         if (!releasePhiOperands(phi, phiBlock, useRemovedOption))
              return false;
         MPhiIterator at(phiBlock->phisBegin(phi));
         phiBlock->discardPhiAt(at);
@@ -283,56 +283,56 @@ ValueNumberer::deleteDef(MDefinition *de
         MInstruction *ins = def->toInstruction();
         if (!releaseInsOperands(ins, useRemovedOption))
              return false;
         ins->block()->discardIgnoreOperands(ins);
     }
     return true;
 }
 
-// Recursively delete all the defs on the deadDefs_ worklist.
+// Recursively discard all the defs on the deadDefs_ worklist.
 bool
 ValueNumberer::processDeadDefs()
 {
     while (!deadDefs_.empty()) {
         MDefinition *def = deadDefs_.popCopy();
 
         values_.forget(def);
-        if (!deleteDef(def))
+        if (!discardDef(def))
             return false;
     }
     return true;
 }
 
-// Delete an edge from the CFG. Return true if the block becomes unreachable.
+// Remove an edge from the CFG. Return true if the block becomes unreachable.
 bool
 ValueNumberer::removePredecessor(MBasicBlock *block, MBasicBlock *pred)
 {
     bool isUnreachableLoop = false;
     if (block->isLoopHeader()) {
         if (block->loopPredecessor() == pred) {
-            // Deleting the entry into the loop makes the loop unreachable.
+            // Discarding the entry into the loop makes the loop unreachable.
             isUnreachableLoop = true;
             JitSpew(JitSpew_GVN, "    Loop with header block%u is no longer reachable", block->id());
 #ifdef DEBUG
         } else if (block->hasUniqueBackedge() && block->backedge() == pred) {
             JitSpew(JitSpew_GVN, "    Loop with header block%u is no longer a loop", block->id());
 #endif
         }
     }
 
     // TODO: Removing a predecessor removes operands from phis, and these
-    // operands may become dead. We should detect this and delete them.
+    // operands may become dead. We should detect this and discard them.
     // In practice though, when this happens, we often end up re-running GVN
     // for other reasons anyway.
     block->removePredecessor(pred);
     return block->numPredecessors() == 0 || isUnreachableLoop;
 }
 
-// Delete the given block and any block in its dominator subtree.
+// Discard the given block and any block in its dominator subtree.
 bool
 ValueNumberer::removeBlocksRecursively(MBasicBlock *start, const MBasicBlock *dominatorRoot)
 {
     MOZ_ASSERT(start != graph_.entryBlock(), "Removing normal entry block");
     MOZ_ASSERT(start != graph_.osrBlock(), "Removing OSR entry block");
 
     // Remove this block from its dominator parent's subtree. This is the only
     // immediately-dominated-block information we need to manually update,
@@ -358,35 +358,35 @@ ValueNumberer::removeBlocksRecursively(M
                 } else if (!rerun_) {
                     if (!remainingBlocks_.append(succ))
                         return false;
                 }
             }
         }
 
 #ifdef DEBUG
-        JitSpew(JitSpew_GVN, "    Deleting block%u%s%s%s", block->id(),
+        JitSpew(JitSpew_GVN, "    Discarding block%u%s%s%s", block->id(),
                 block->isLoopHeader() ? " (loop header)" : "",
                 block->isSplitEdge() ? " (split edge)" : "",
                 block->immediateDominator() == block ? " (dominator root)" : "");
         for (MDefinitionIterator iter(block); iter; iter++) {
             MDefinition *def = *iter;
-            JitSpew(JitSpew_GVN, "      Deleting %s%u", def->opName(), def->id());
+            JitSpew(JitSpew_GVN, "      Discarding %s%u", def->opName(), def->id());
         }
         MControlInstruction *control = block->lastIns();
-        JitSpew(JitSpew_GVN, "      Deleting %s%u", control->opName(), control->id());
+        JitSpew(JitSpew_GVN, "      Discarding %s%u", control->opName(), control->id());
 #endif
 
-        // Keep track of how many blocks within dominatorRoot's tree have been deleted.
+        // Keep track of how many blocks within dominatorRoot's tree have been discarded.
         if (dominatorRoot->dominates(block))
-            ++numBlocksDeleted_;
+            ++numBlocksDiscarded_;
 
-        // TODO: Removing a block deletes the phis, instructions, and resume
+        // TODO: Removing a block discards the phis, instructions, and resume
         // points in the block, and their operands may become dead. We should
-        // detect this and delete them. In practice though, when this happens,
+        // detect this and discard them. In practice though, when this happens,
         // we often end up re-running GVN for other reasons anyway (bug 1031412).
         graph_.removeBlockIncludingPhis(block);
         blocksRemoved_ = true;
     } while (!unreachableBlocks_.empty());
 
     return true;
 }
 
@@ -438,17 +438,17 @@ ValueNumberer::hasLeader(const MPhi *phi
         return rep != phi && rep->block()->dominates(phiBlock);
     }
     return false;
 }
 
 // Test whether there are any phis in the backedge's loop header which are
 // newly optimizable, as a result of optimizations done inside the loop. This
 // is not a sparse approach, but restarting is rare enough in practice.
-// Termination is ensured by deleting the phi triggering the iteration.
+// Termination is ensured by discarding the phi triggering the iteration.
 bool
 ValueNumberer::loopHasOptimizablePhi(MBasicBlock *backedge) const
 {
     // Rescan the phis for any that can be simplified, since they may be reading
     // values from backedges.
     MBasicBlock *header = backedge->loopHeaderOfBackedge();
     for (MPhiIterator iter(header->phisBegin()), end(header->phisEnd()); iter != end; ++iter) {
         MPhi *phi = *iter;
@@ -475,21 +475,21 @@ ValueNumberer::visitDefinition(MDefiniti
             def->block()->insertAfter(def->toInstruction(), sim->toInstruction());
 
         JitSpew(JitSpew_GVN, "    Folded %s%u to %s%u",
                 def->opName(), def->id(), sim->opName(), sim->id());
         ReplaceAllUsesWith(def, sim);
 
         // The node's foldsTo said |def| can be replaced by |rep|. If |def| is a
         // guard, then either |rep| is also a guard, or a guard isn't actually
-        // needed, so we can clear |def|'s guard flag and let it be deleted.
+        // needed, so we can clear |def|'s guard flag and let it be discarded.
         def->setNotGuardUnchecked();
 
         if (DeadIfUnused(def)) {
-            if (!deleteDefsRecursively(def))
+            if (!discardDefsRecursively(def))
                 return false;
         }
         def = sim;
     }
 
     // Look for a dominating def which makes this def redundant.
     MDefinition *rep = leader(def);
     if (rep != def) {
@@ -498,27 +498,27 @@ ValueNumberer::visitDefinition(MDefiniti
         if (rep->updateForReplacement(def)) {
             JitSpew(JitSpew_GVN,
                     "    Replacing %s%u with %s%u",
                     def->opName(), def->id(), rep->opName(), rep->id());
             ReplaceAllUsesWith(def, rep);
 
             // The node's congruentTo said |def| is congruent to |rep|, and it's
             // dominated by |rep|. If |def| is a guard, it's covered by |rep|,
-            // so we can clear |def|'s guard flag and let it be deleted.
+            // so we can clear |def|'s guard flag and let it be discarded.
             def->setNotGuardUnchecked();
 
             if (DeadIfUnused(def)) {
-                // deleteDef should not add anything to the deadDefs, as the
+                // discardDef should not add anything to the deadDefs, as the
                 // redundant operation should have the same input operands.
-                mozilla::DebugOnly<bool> r = deleteDef(def, DontSetUseRemoved);
-                MOZ_ASSERT(r, "deleteDef shouldn't have tried to add anything to the worklist, "
+                mozilla::DebugOnly<bool> r = discardDef(def, DontSetUseRemoved);
+                MOZ_ASSERT(r, "discardDef shouldn't have tried to add anything to the worklist, "
                               "so it shouldn't have failed");
                 MOZ_ASSERT(deadDefs_.empty(),
-                           "deleteDef shouldn't have added anything to the worklist");
+                           "discardDef shouldn't have added anything to the worklist");
             }
             def = rep;
         }
     }
 
     // If this instruction has a dependency() into an unreachable block, we'll
     // need to update AliasAnalysis.
     if (updateAliasAnalysis_ && !dependenciesBroken_) {
@@ -584,19 +584,19 @@ ValueNumberer::visitBlock(MBasicBlock *b
 {
     MOZ_ASSERT(!block->unreachable(), "Blocks marked unreachable during GVN");
     MOZ_ASSERT(!block->isDead(), "Block to visit is already dead");
 
     // Visit the definitions in the block top-down.
     for (MDefinitionIterator iter(block); iter; ) {
         MDefinition *def = *iter++;
 
-        // If the definition is dead, delete it.
+        // If the definition is dead, discard it.
         if (IsDead(def)) {
-            if (!deleteDefsRecursively(def))
+            if (!discardDefsRecursively(def))
                 return false;
             continue;
         }
 
         if (!visitDefinition(def))
             return false;
     }
 
@@ -607,17 +607,17 @@ ValueNumberer::visitBlock(MBasicBlock *b
 bool
 ValueNumberer::visitDominatorTree(MBasicBlock *dominatorRoot, size_t *totalNumVisited)
 {
     JitSpew(JitSpew_GVN, "  Visiting dominator tree (with %llu blocks) rooted at block%u%s",
             uint64_t(dominatorRoot->numDominated()), dominatorRoot->id(),
             dominatorRoot == graph_.entryBlock() ? " (normal entry block)" :
             dominatorRoot == graph_.osrBlock() ? " (OSR entry block)" :
             " (normal entry and OSR entry merge point)");
-    MOZ_ASSERT(numBlocksDeleted_ == 0, "numBlocksDeleted_ wasn't reset");
+    MOZ_ASSERT(numBlocksDiscarded_ == 0, "numBlocksDiscarded_ wasn't reset");
     MOZ_ASSERT(dominatorRoot->immediateDominator() == dominatorRoot,
             "root is not a dominator tree root");
 
     // Visit all blocks dominated by dominatorRoot, in RPO. This has the nice property
     // that we'll always visit a block before any block it dominates, so we can
     // make a single pass through the list and see every full redundance.
     size_t numVisited = 0;
     for (ReversePostorderIterator iter(graph_.rpoBegin(dominatorRoot)); ; ++iter) {
@@ -632,25 +632,25 @@ ValueNumberer::visitDominatorTree(MBasic
         // If this was the end of a loop, check for optimization in the header.
         if (!rerun_ && block->isLoopBackedge() && loopHasOptimizablePhi(block)) {
             JitSpew(JitSpew_GVN, "    Loop phi in block%u can now be optimized; will re-run GVN!",
                     block->id());
             rerun_ = true;
             remainingBlocks_.clear();
         }
         ++numVisited;
-        MOZ_ASSERT(numVisited <= dominatorRoot->numDominated() - numBlocksDeleted_,
+        MOZ_ASSERT(numVisited <= dominatorRoot->numDominated() - numBlocksDiscarded_,
                    "Visited blocks too many times");
-        if (numVisited >= dominatorRoot->numDominated() - numBlocksDeleted_)
+        if (numVisited >= dominatorRoot->numDominated() - numBlocksDiscarded_)
             break;
     }
 
     *totalNumVisited += numVisited;
     values_.clear();
-    numBlocksDeleted_ = 0;
+    numBlocksDiscarded_ = 0;
     return true;
 }
 
 // Visit all the blocks in the graph.
 bool
 ValueNumberer::visitGraph()
 {
     // Due to OSR blocks, the set of blocks dominated by a blocks may not be
@@ -674,17 +674,17 @@ ValueNumberer::visitGraph()
 }
 
 ValueNumberer::ValueNumberer(MIRGenerator *mir, MIRGraph &graph)
   : mir_(mir), graph_(graph),
     values_(graph.alloc()),
     deadDefs_(graph.alloc()),
     unreachableBlocks_(graph.alloc()),
     remainingBlocks_(graph.alloc()),
-    numBlocksDeleted_(0),
+    numBlocksDiscarded_(0),
     rerun_(false),
     blocksRemoved_(false),
     updateAliasAnalysis_(false),
     dependenciesBroken_(false)
 {}
 
 bool
 ValueNumberer::run(UpdateAliasAnalysisFlag updateAliasAnalysis)
@@ -699,18 +699,19 @@ ValueNumberer::run(UpdateAliasAnalysisFl
     // as needed on its own seems to work pretty well.
     if (!values_.init())
         return false;
 
     JitSpew(JitSpew_GVN, "Running GVN on graph (with %llu blocks)",
             uint64_t(graph_.numBlocks()));
 
     // Top level non-sparse iteration loop. If an iteration performs a
-    // significant change, such as deleting a block which changes the dominator
-    // tree and may enable more optimization, this loop takes another iteration.
+    // significant change, such as discarding a block which changes the
+    // dominator tree and may enable more optimization, this loop takes another
+    // iteration.
     int runs = 0;
     for (;;) {
         if (!visitGraph())
             return false;
 
         // Test whether any block which was not removed but which had at least
         // one predecessor removed will have a new dominator parent.
         while (!remainingBlocks_.empty()) {
@@ -741,17 +742,17 @@ ValueNumberer::run(UpdateAliasAnalysisFl
 
         JitSpew(JitSpew_GVN, "Re-running GVN on graph (run %d, now with %llu blocks)",
                 runs, uint64_t(graph_.numBlocks()));
         rerun_ = false;
 
         // Enforce an arbitrary iteration limit. This is rarely reached, and
         // isn't even strictly necessary, as the algorithm is guaranteed to
         // terminate on its own in a finite amount of time (since every time we
-        // re-run we delete the construct which triggered the re-run), but it
+        // re-run we discard the construct which triggered the re-run), but it
         // does help avoid slow compile times on pathlogical code.
         ++runs;
         if (runs == 6) {
             JitSpew(JitSpew_GVN, "Re-run cutoff reached. Terminating GVN!");
             break;
         }
     }
 
--- a/js/src/jit/ValueNumbering.h
+++ b/js/src/jit/ValueNumbering.h
@@ -61,34 +61,34 @@ class ValueNumberer
     typedef Vector<MDefinition *, 4, IonAllocPolicy> DefWorklist;
 
     MIRGenerator *const mir_;
     MIRGraph &graph_;
     VisibleValues values_;            // Numbered values
     DefWorklist deadDefs_;            // Worklist for deleting values
     BlockWorklist unreachableBlocks_; // Worklist for unreachable blocks
     BlockWorklist remainingBlocks_;   // Blocks remaining with fewer preds
-    size_t numBlocksDeleted_;         // Num deleted blocks in current tree
+    size_t numBlocksDiscarded_;       // Num discarded blocks in current tree
     bool rerun_;                      // Should we run another GVN iteration?
     bool blocksRemoved_;              // Have any blocks been removed?
     bool updateAliasAnalysis_;        // Do we care about AliasAnalysis?
     bool dependenciesBroken_;         // Have we broken AliasAnalysis?
 
     enum UseRemovedOption {
         DontSetUseRemoved,
         SetUseRemoved
     };
 
-    bool deleteDefsRecursively(MDefinition *def);
+    bool discardDefsRecursively(MDefinition *def);
     bool releasePhiOperands(MPhi *phi, const MBasicBlock *phiBlock,
                             UseRemovedOption useRemovedOption = SetUseRemoved);
     bool releaseInsOperands(MInstruction *ins,
                             UseRemovedOption useRemovedOption = SetUseRemoved);
-    bool deleteDef(MDefinition *def,
-                   UseRemovedOption useRemovedOption = SetUseRemoved);
+    bool discardDef(MDefinition *def,
+                    UseRemovedOption useRemovedOption = SetUseRemoved);
     bool processDeadDefs();
 
     bool removePredecessor(MBasicBlock *block, MBasicBlock *pred);
     bool removeBlocksRecursively(MBasicBlock *block, const MBasicBlock *root);
 
     MDefinition *simplified(MDefinition *def) const;
     MDefinition *leader(MDefinition *def);
     bool hasLeader(const MPhi *phi, const MBasicBlock *phiBlock) const;