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 108988 2520fd9f388380f2bd057c19ed3f4b694371d61e
parent 108987 bca9d7ef2727f1dff6ad72ac739fecb38595d7f7
child 108989 7895a56d434da2e97879ad4ae62395a0312ac809
push id82
push usershu@rfrn.org
push dateFri, 05 Oct 2012 13:20:22 +0000
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__