Bug 1004363 - IonMonkey: Make a block's numDominated() include itself. r=nbp
authorDan Gohman <sunfish@mozilla.com>
Wed, 04 Jun 2014 07:44:46 -0700
changeset 205856 07ab6ede1eff8b32bf070da17529972bb5d7b356
parent 205855 41f1efb029203e6f72a97b87773ac64d99b1654e
child 205857 51b269a9c5c9ada5291547ce405457ee23b3a87e
push id3741
push userasasaki@mozilla.com
push dateMon, 21 Jul 2014 20:25:18 +0000
treeherdermozilla-beta@4d6f46f5af68 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersnbp
bugs1004363
milestone32.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 1004363 - IonMonkey: Make a block's numDominated() include itself. r=nbp
js/src/jit/IonAnalysis.cpp
js/src/jit/MIRGraph.cpp
js/src/jit/MIRGraph.h
js/src/jit/ValueNumbering.cpp
js/src/jit/ValueNumbering.h
--- a/js/src/jit/IonAnalysis.cpp
+++ b/js/src/jit/IonAnalysis.cpp
@@ -1196,32 +1196,34 @@ jit::BuildDominatorTree(MIRGraph &graph)
     // of a definition is visited before the def itself. Since a def
     // dominates its uses, by the time we reach a particular
     // block, we have processed all of its dominated children, so
     // block->numDominated() is accurate.
     for (PostorderIterator i(graph.poBegin()); i != graph.poEnd(); i++) {
         MBasicBlock *child = *i;
         MBasicBlock *parent = child->immediateDominator();
 
+        // Domininace is defined such that blocks always dominate themselves.
+        child->addNumDominated(1);
+
         // If the block only self-dominates, it has no definite parent.
         if (child == parent)
             continue;
 
         if (!parent->addImmediatelyDominatedBlock(child))
             return false;
 
-        // An additional +1 for the child block.
-        parent->addNumDominated(child->numDominated() + 1);
+        parent->addNumDominated(child->numDominated());
     }
 
 #ifdef DEBUG
     // If compiling with OSR, many blocks will self-dominate.
     // Without OSR, there is only one root block which dominates all.
     if (!graph.osrBlock())
-        JS_ASSERT(graph.entryBlock()->numDominated() == graph.numBlocks() - 1);
+        JS_ASSERT(graph.entryBlock()->numDominated() == graph.numBlocks());
 #endif
     // Now, iterate through the dominator tree and annotate every
     // block with its index in the pre-order traversal of the
     // dominator tree.
     Vector<MBasicBlock *, 1, IonAllocPolicy> worklist(graph.alloc());
 
     // The index of the current block in the CFG traversal.
     size_t index = 0;
@@ -1426,45 +1428,47 @@ AssertReversePostOrder(MIRGraph &graph)
 #ifdef DEBUG
 static void
 AssertDominatorTree(MIRGraph &graph)
 {
     // Check dominators.
     size_t i = graph.numBlocks();
     size_t totalNumDominated = 0;
     for (MBasicBlockIterator block(graph.begin()); block != graph.end(); block++) {
+        JS_ASSERT(block->dominates(*block));
+
         MBasicBlock *idom = block->immediateDominator();
         JS_ASSERT(idom->dominates(*block));
         JS_ASSERT(idom == *block || idom->id() < block->id());
 
         if (idom == *block) {
-            totalNumDominated += block->numDominated() + 1;
+            totalNumDominated += block->numDominated();
         } else {
             bool foundInParent = false;
             for (size_t j = 0; j < idom->numImmediatelyDominatedBlocks(); j++) {
                 if (idom->getImmediatelyDominatedBlock(j) == *block) {
                     foundInParent = true;
                     break;
                 }
             }
             JS_ASSERT(foundInParent);
         }
 
-        size_t numDominated = 0;
+        size_t numDominated = 1;
         for (size_t j = 0; j < block->numImmediatelyDominatedBlocks(); j++) {
             MBasicBlock *dom = block->getImmediatelyDominatedBlock(j);
             JS_ASSERT(block->dominates(dom));
             JS_ASSERT(dom->id() > block->id());
             JS_ASSERT(dom->immediateDominator() == *block);
 
-            numDominated += dom->numDominated() + 1;
+            numDominated += dom->numDominated();
         }
         JS_ASSERT(block->numDominated() == numDominated);
-        JS_ASSERT(block->numDominated() + 1 <= i);
-        JS_ASSERT(block->numSuccessors() != 0 || block->numDominated() == 0);
+        JS_ASSERT(block->numDominated() <= i);
+        JS_ASSERT(block->numSuccessors() != 0 || block->numDominated() == 1);
         i--;
     }
     JS_ASSERT(i == 0);
     JS_ASSERT(totalNumDominated == graph.numBlocks());
 }
 #endif
 
 void
@@ -1527,17 +1531,17 @@ jit::AssertExtendedGraphCoherency(MIRGra
     AssertDominatorTree(graph);
 #endif
 }
 
 
 struct BoundsCheckInfo
 {
     MBoundsCheck *check;
-    uint32_t validUntil;
+    uint32_t validEnd;
 };
 
 typedef HashMap<uint32_t,
                 BoundsCheckInfo,
                 DefaultHasher<uint32_t>,
                 IonAllocPolicy> BoundsCheckMap;
 
 // Compute a hash for bounds checks which ignores constant offsets in the index.
@@ -1551,21 +1555,21 @@ BoundsCheckHashIgnoreOffset(MBoundsCheck
 }
 
 static MBoundsCheck *
 FindDominatingBoundsCheck(BoundsCheckMap &checks, MBoundsCheck *check, size_t index)
 {
     // See the comment in ValueNumberer::findDominatingDef.
     HashNumber hash = BoundsCheckHashIgnoreOffset(check);
     BoundsCheckMap::Ptr p = checks.lookup(hash);
-    if (!p || index > p->value().validUntil) {
+    if (!p || index >= p->value().validEnd) {
         // We didn't find a dominating bounds check.
         BoundsCheckInfo info;
         info.check = check;
-        info.validUntil = index + check->block()->numDominated();
+        info.validEnd = index + check->block()->numDominated();
 
         if(!checks.put(hash, info))
             return nullptr;
 
         return check;
     }
 
     return p->value().check;
--- a/js/src/jit/MIRGraph.cpp
+++ b/js/src/jit/MIRGraph.cpp
@@ -937,17 +937,17 @@ MBasicBlock::assertUsesAreNotWithin(MUse
 #endif
 }
 
 bool
 MBasicBlock::dominates(const MBasicBlock *other) const
 {
     uint32_t high = domIndex() + numDominated();
     uint32_t low  = domIndex();
-    return other->domIndex() >= low && other->domIndex() <= high;
+    return other->domIndex() >= low && other->domIndex() < high;
 }
 
 void
 MBasicBlock::setUnreachable()
 {
     unreachable_ = true;
     size_t numDom = numImmediatelyDominatedBlocks();
     for (size_t d = 0; d < numDom; d++)
--- a/js/src/jit/MIRGraph.h
+++ b/js/src/jit/MIRGraph.h
@@ -392,17 +392,20 @@ class MBasicBlock : public TempObject, p
     MBasicBlock **immediatelyDominatedBlocksBegin() {
         return immediatelyDominated_.begin();
     }
 
     MBasicBlock **immediatelyDominatedBlocksEnd() {
         return immediatelyDominated_.end();
     }
 
+    // Return the number of blocks dominated by this block. All blocks
+    // dominate at least themselves, so this will always be non-zero.
     size_t numDominated() const {
+        JS_ASSERT(numDominated_ != 0);
         return numDominated_;
     }
 
     void addNumDominated(size_t n) {
         numDominated_ += n;
     }
 
     bool addImmediatelyDominatedBlock(MBasicBlock *child);
--- a/js/src/jit/ValueNumbering.cpp
+++ b/js/src/jit/ValueNumbering.cpp
@@ -303,27 +303,27 @@ ValueNumberer::computeValueNumbers()
 }
 
 MDefinition *
 ValueNumberer::findDominatingDef(InstructionMap &defs, MDefinition *ins, size_t index)
 {
     JS_ASSERT(ins->valueNumber() != 0);
     InstructionMap::Ptr p = defs.lookup(ins->valueNumber());
     MDefinition *dom;
-    if (!p || index > p->value().validUntil) {
+    if (!p || index >= p->value().validEnd) {
         DominatingValue value;
         value.def = ins;
         // Since we are traversing the dominator tree in pre-order, when we
         // are looking at the |index|-th block, the next numDominated() blocks
         // we traverse are precisely the set of blocks that are dominated.
         //
         // So, this value is visible in all blocks if:
-        // index <= index + ins->block->numDominated()
+        // index < index + ins->block->numDominated()
         // and becomes invalid after that.
-        value.validUntil = index + ins->block()->numDominated();
+        value.validEnd = index + ins->block()->numDominated();
 
         if(!defs.put(ins->valueNumber(), value))
             return nullptr;
 
         dom = ins;
     } else {
         dom = p->value().def;
     }
--- a/js/src/jit/ValueNumbering.h
+++ b/js/src/jit/ValueNumbering.h
@@ -36,17 +36,17 @@ class ValueNumberer
     typedef HashMap<MDefinition *,
                     uint32_t,
                     ValueHasher,
                     IonAllocPolicy> ValueMap;
 
     struct DominatingValue
     {
         MDefinition *def;
-        uint32_t validUntil;
+        uint32_t validEnd;
     };
 
     typedef HashMap<uint32_t,
                     DominatingValue,
                     DefaultHasher<uint32_t>,
                     IonAllocPolicy> InstructionMap;
 
   protected: