Add narrowing into range analysis, greatly speeding up some testcases (bug 765119, jandem)
authorMarty Rosenberg <mrosenberg@mozilla.com>
Tue, 02 Oct 2012 04:34:28 -0400
changeset 115359 43a250bfe33ded565eb8c1b9ec12dccaed4d427e
parent 115358 43e4a8a3788b361897d1bb48fd52265d5cdeb166
child 115360 ec67e229cc9b43c7fdd948da131acc92342a5a0e
push idunknown
push userunknown
push dateunknown
bugs765119
milestone18.0a1
Add narrowing into range analysis, greatly speeding up some testcases (bug 765119, jandem)
js/src/ion/MIR.cpp
js/src/ion/MIR.h
js/src/ion/RangeAnalysis.cpp
js/src/ion/RangeAnalysis.h
--- a/js/src/ion/MIR.cpp
+++ b/js/src/ion/MIR.cpp
@@ -5,16 +5,17 @@
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "IonBuilder.h"
 #include "LICM.h" // For LinearSum
 #include "MIR.h"
 #include "MIRGraph.h"
 #include "EdgeCaseAnalysis.h"
+#include "IonSpewer.h"
 #include "jsnum.h"
 #include "jsstr.h"
 #include "jsatominlines.h"
 #include "jstypedarrayinlines.h" // For ClampIntForUint8Array
 
 using namespace js;
 using namespace js::ion;
 
@@ -453,16 +454,49 @@ MPhi::congruentTo(MDefinition *const &in
 
 bool
 MPhi::addInput(MDefinition *ins)
 {
     ins->addUse(this, inputs_.length());
     return inputs_.append(ins);
 }
 
+bool
+MPhi::recomputeRange()
+{
+    if (type() != MIRType_Int32)
+        return false;
+
+    Range r;
+    JS_ASSERT(getOperand(0)->op() != MDefinition::Op_OsrValue);
+    bool updated = false;
+    for (size_t i = 0; i < numOperands(); i++) {
+#if 0
+        if (getOperand(i)->block()->earlyAbort()) {
+            IonSpew(IonSpew_Range, "Ignoring unreachable input %d", getOperand(i)->id());
+            continue;
+        }
+#endif
+        if (!isOSRLikeValue(getOperand(i))) {
+            if (block()->isLoopHeader())
+                changeCounts_[i].updateRange(getOperand(i)->range());
+            if (updated) {
+                if (block()->isLoopHeader())
+                    r.unionWith(&changeCounts_[i]);
+                else
+                    r.unionWith(getOperand(i)->range());
+            } else {
+                r.update(getOperand(0)->range());
+                updated = true;
+            }
+        }
+    }
+     return range()->update(&r);
+}
+
 uint32
 MPrepareCall::argc() const
 {
     JS_ASSERT(useCount() == 1);
     MCall *call = usesBegin()->node()->toDefinition()->toCall();
     return call->numStackArgs();
 }
 
--- a/js/src/ion/MIR.h
+++ b/js/src/ion/MIR.h
@@ -2679,17 +2679,19 @@ class MFromCharCode
 
 class MPhi : public MDefinition, public InlineForwardListNode<MPhi>
 {
     js::Vector<MDefinition *, 2, IonAllocPolicy> inputs_;
     uint32 slot_;
     bool triedToSpecialize_;
     bool hasBytecodeUses_;
     bool isIterator_;
-
+    // For every input to the phi, track how many times it has changed
+    // Only used in loop headers, so it defaults to 0 elements to conserve space
+    js::Vector<RangeChangeCount, 0, IonAllocPolicy> changeCounts_;
     MPhi(uint32 slot)
       : slot_(slot),
         triedToSpecialize_(false),
         hasBytecodeUses_(false),
         isIterator_(false)
     {
         setResultType(MIRType_Value);
     }
@@ -2736,29 +2738,19 @@ class MPhi : public MDefinition, public 
     }
     void setIterator() {
         isIterator_ = true;
     }
 
     AliasSet getAliasSet() const {
         return AliasSet::None();
     }
-    bool recomputeRange() {
-        if (type() != MIRType_Int32)
-            return false;
-
-        Range r;
-        r.update(getOperand(0)->range());
-        JS_ASSERT(getOperand(0)->op() != MDefinition::Op_OsrValue);
-        for (size_t i = 0; i < numOperands(); i++) {
-            if (!isOSRLikeValue(getOperand(i)))
-                r.unionWith(getOperand(i)->range(), true);
-        }
-
-        return range()->update(&r);
+    bool recomputeRange();
+    bool initCounts() {
+        return changeCounts_.resize(inputs_.length());
     }
 };
 
 // The goal of a Beta node is to split a def at a conditionally taken
 // branch, so that uses dominated by it have a different name.
 class MBeta : public MUnaryInstruction
 {
   private:
--- a/js/src/ion/RangeAnalysis.cpp
+++ b/js/src/ion/RangeAnalysis.cpp
@@ -273,22 +273,39 @@ Range::intersect(const Range *lhs, const
     // Instead, we should use it to eliminate the dead block.
     // (Bug 765127)
     if (r.upper_ < r.lower_)
         r.makeRangeInfinite();
     return r;
 }
 
 void
-Range::unionWith(const Range *other, bool useNarrowing)
+Range::unionWith(const Range *other)
+{
+   setLower(Min(lower_, other->lower_));
+   lower_infinite_ |= other->lower_infinite_;
+   setUpper(Max(upper_, other->upper_));
+   upper_infinite_ |= other->upper_infinite_;
+}
+
+void
+Range::unionWith(RangeChangeCount *other)
 {
-    setLower(Min(lower_, other->lower_));
-    lower_infinite_ |= other->lower_infinite_;
-    setUpper(Max(upper_, other->upper_));
-    upper_infinite_ |= other->upper_infinite_;
+    if (other->lowerCount_ <= 2) {
+        setLower(Min(lower_, other->oldRange.lower_));
+        lower_infinite_ |= other->oldRange.lower_infinite_;
+    } else {
+        other->lowerCount_ = 0;
+    }
+    if (other->upperCount_ <= 2) {
+        setUpper(Max(upper_, other->oldRange.upper_));
+        upper_infinite_ |= other->oldRange.upper_infinite_;
+    } else {
+        other->upperCount_ = 0;
+    }
 }
 
 Range
 Range::add(const Range *lhs, const Range *rhs)
 {
     Range ret(
         (int64_t)lhs->lower_ + (int64_t)rhs->lower_,
         (int64_t)lhs->upper_ + (int64_t)rhs->upper_);
@@ -386,16 +403,25 @@ PopFromWorklist(MDefinitionVector &workl
     def->setNotInWorklist();
     return def;
 }
 
 
 bool
 RangeAnalysis::analyze()
 {
+    for (PostorderIterator i(graph_.poBegin()); i != graph_.poEnd(); i++) {
+        MBasicBlock *curBlock = *i;
+        if (!curBlock->isLoopHeader())
+            continue;
+        for (MPhiIterator pi(curBlock->phisBegin()); pi != curBlock->phisEnd(); pi++)
+            if (!pi->initCounts())
+                return false;
+    }
+
     IonSpew(IonSpew_Range, "Doing range propagation");
     MDefinitionVector worklist;
 
     for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
         for (MDefinitionIterator iter(*block); iter; iter++) {
             MDefinition *def = *iter;
 
             AddToWorklist(worklist, def);
--- a/js/src/ion/RangeAnalysis.h
+++ b/js/src/ion/RangeAnalysis.h
@@ -30,16 +30,17 @@ class RangeAnalysis
 
   public:
     RangeAnalysis(MIRGraph &graph);
     bool addBetaNobes();
     bool analyze();
     bool removeBetaNobes();
 };
 
+struct RangeChangeCount;
 class Range {
     private:
         // :TODO: we should do symbolic range evaluation, where we have
         // information of the form v1 < v2 for arbitrary defs v1 and v2, not
         // just constants of type int32.
         // (Bug 766592)
 
         // We represent ranges where the endpoints can be in the set:
@@ -101,17 +102,18 @@ class Range {
         bool update(const Range &other) {
             return update(&other);
         }
 
         // Unlike the other operations, unionWith is an in-place
         // modification. This is to avoid a bunch of useless extra
         // copying when chaining together unions when handling Phi
         // nodes.
-    void unionWith(const Range *other, bool useNarrowing = false);
+    void unionWith(const Range *other);
+    void unionWith(RangeChangeCount *other);
 
         static Range intersect(const Range *lhs, const Range *rhs);
         static Range add(const Range *lhs, const Range *rhs);
         static Range sub(const Range *lhs, const Range *rhs);
         static Range mul(const Range *lhs, const Range *rhs);
         static Range and_(const Range *lhs, const Range *rhs);
         static Range shl(const Range *lhs, int32 c);
         static Range shr(const Range *lhs, int32 c);
@@ -169,13 +171,29 @@ class Range {
             }
         }
         void set(int64_t l, int64_t h) {
             setLower(l);
             setUpper(h);
         }
 };
 
+struct RangeChangeCount {
+    Range oldRange;
+    unsigned char lowerCount_ : 4;
+    unsigned char upperCount_ : 4;
+
+    void updateRange(Range *newRange) {
+        JS_ASSERT(newRange->lower() >= oldRange.lower());
+        if (newRange->lower() != oldRange.lower())
+            lowerCount_ = lowerCount_ < 15 ? lowerCount_ + 1 : lowerCount_;
+        JS_ASSERT(newRange->upper() <= oldRange.upper());
+        if (newRange->upper() != oldRange.upper())
+            upperCount_ = upperCount_ < 15 ? upperCount_ + 1 : upperCount_;
+        oldRange = *newRange;
+    }
+};
+
 } // namespace ion
 } // namespace js
 
 #endif // jsion_range_analysis_h__