Add a bunch of features to range analysis to make it optimize more. (bug 765119, r=jandem)
authorMarty Rosenberg <mrosenberg@mozilla.com>
Tue, 02 Oct 2012 04:34:28 -0400
changeset 109619 af9e58e861024e230bc10cdd109ac2af159bfa9f
parent 109618 ddcda23710f428704d5e455abe86947154458829
child 109620 94734724e155c9f80c1f837b9e15dae582f24431
push id23636
push usergsharp@mozilla.com
push dateMon, 08 Oct 2012 08:08:19 +0000
treeherdermozilla-central@24cf40690042 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjandem
bugs765119
milestone18.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
Add a bunch of features to range analysis to make it optimize more. (bug 765119, r=jandem)
js/src/ion/JSONSpewer.cpp
js/src/ion/MIR.h
js/src/ion/RangeAnalysis.cpp
js/src/ion/RangeAnalysis.h
js/src/ion/arm/CodeGenerator-arm.cpp
--- a/js/src/ion/JSONSpewer.cpp
+++ b/js/src/ion/JSONSpewer.cpp
@@ -250,17 +250,18 @@ JSONSpewer::spewMDef(MDefinition *def)
         integerValue(def->getOperand(i)->id());
     endList();
 
     beginListProperty("uses");
     for (MUseDefIterator use(def); use; use++)
         integerValue(use.def()->id());
     endList();
 
-    stringProperty("type", StringFromMIRType(def->type()));
+    stringProperty("type", "%s : [%d, %d]", StringFromMIRType(def->type()),
+                   def->range()->lower(), def->range()->upper());
 
     if (def->isInstruction()) {
         if (MResumePoint *rp = def->toInstruction()->resumePoint())
             spewMResumePoint(rp);
     }
 
     endObject();
 }
--- a/js/src/ion/MIR.h
+++ b/js/src/ion/MIR.h
@@ -56,16 +56,18 @@ MIRType MIRTypeFromValue(const js::Value
 class MDefinition;
 class MInstruction;
 class MBasicBlock;
 class MNode;
 class MUse;
 class MIRGraph;
 class MResumePoint;
 
+static inline bool isOSRLikeValue (MDefinition *def);
+
 // Represents a use of a node.
 class MUse : public TempObject, public InlineForwardListNode<MUse>
 {
     friend class MDefinition;
 
     MNode *node_;           // The node that is using this operand.
     uint32 index_;          // The index of this operand in its owner.
 
@@ -1914,16 +1916,22 @@ class MBitAnd : public MBinaryBitwiseIns
         return getOperand(operand); // 0 & x => 0;
     }
     MDefinition *foldIfNegOne(size_t operand) {
         return getOperand(1 - operand); // x & -1 => x
     }
     MDefinition *foldIfEqual() {
         return getOperand(0); // x & x => x;
     }
+    bool recomputeRange() {
+        Range *left = getOperand(0)->range();
+        Range *right = getOperand(1)->range();
+        return range()->update(Range::and_(left, right));
+    }
+
 };
 
 class MBitOr : public MBinaryBitwiseInstruction
 {
     MBitOr(MDefinition *left, MDefinition *right)
       : MBinaryBitwiseInstruction(left, right)
     { }
 
@@ -2747,26 +2755,27 @@ 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());
-
-        for (size_t i = 0; i < numOperands(); i++)
-            r.unionWith(getOperand(i)->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);
     }
 };
 
 // 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
@@ -5619,16 +5628,26 @@ MInstruction *MDefinition::toInstruction
     return (MInstruction *)this;
 }
 
 void MNode::initOperand(size_t index, MDefinition *ins)
 {
     setOperand(index, ins);
     ins->addUse(this, index);
 }
+static inline bool isOSRLikeValue (MDefinition *def) {
+    if (def->isOsrValue())
+        return true;
+
+    if (def->isUnbox())
+        if (def->getOperand(0)->isOsrValue())
+            return true;
+
+    return false;
+}
 
 typedef Vector<MDefinition *, 8, IonAllocPolicy> MDefinitionVector;
 
 } // namespace ion
 } // namespace js
 
 #endif // jsion_mir_h__
 
--- a/js/src/ion/RangeAnalysis.cpp
+++ b/js/src/ion/RangeAnalysis.cpp
@@ -273,21 +273,21 @@ 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)
+Range::unionWith(const Range *other, bool useNarrowing)
 {
     setLower(Min(lower_, other->lower_));
+    lower_infinite_ |= other->lower_infinite_;
     setUpper(Max(upper_, other->upper_));
-    lower_infinite_ |= other->lower_infinite_;
     upper_infinite_ |= other->upper_infinite_;
 }
 
 Range
 Range::add(const Range *lhs, const Range *rhs)
 {
     Range ret(
         (int64_t)lhs->lower_ + (int64_t)rhs->lower_,
@@ -299,17 +299,30 @@ Range
 Range::sub(const Range *lhs, const Range *rhs)
 {
     Range ret(
         (int64_t)lhs->lower_ - (int64_t)rhs->upper_,
         (int64_t)lhs->upper_ - (int64_t)rhs->lower_);
     return ret;
 
 }
+Range
+Range::and_(const Range *lhs, const Range *rhs)
+{
+    uint64_t lower = 0;
+    // If both numbers can be negative, issues can be had.
+    if (lhs->lower_ < 0 && rhs->lower_ < 0)
+        lower = INT_MIN;
+    uint64_t upper = lhs->upper_;
+    if (rhs->upper_ < lhs->upper_)
+        upper = rhs->upper_;
+    Range ret(lower, upper);
+    return ret;
 
+}
 Range
 Range::mul(const Range *lhs, const Range *rhs)
 {
     int64_t a = (int64_t)lhs->lower_ * (int64_t)rhs->lower_;
     int64_t b = (int64_t)lhs->lower_ * (int64_t)rhs->upper_;
     int64_t c = (int64_t)lhs->upper_ * (int64_t)rhs->lower_;
     int64_t d = (int64_t)lhs->upper_ * (int64_t)rhs->upper_;
     Range ret(
@@ -341,17 +354,16 @@ Range::shr(const Range *lhs, int32 c)
 bool
 Range::update(const Range *other)
 {
     bool changed =
         lower_ != other->lower_ ||
         lower_infinite_ != other->lower_infinite_ ||
         upper_ != other->upper_ ||
         upper_infinite_ != other->upper_infinite_;
-
     if (changed) {
         lower_ = other->lower_;
         lower_infinite_ = other->lower_infinite_;
         upper_ = other->upper_;
         upper_infinite_ = other->upper_infinite_;
     }
 
     return changed;
@@ -381,30 +393,23 @@ RangeAnalysis::analyze()
 {
     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;
 
-            if (!def->isPhi() && !def->isBeta())
-                continue;
             AddToWorklist(worklist, def);
 
         }
     }
     size_t iters = 0;
-#define MAX_ITERS 4096
-    // XXX: hack: range analysis iloops on jit-test/tests/basic/fannkuch.js
-    // To circumvent this and land the pass, we just run for a fixed number of
-    // iterations.
-    //
-    // (Bug 765119)
-    while (!worklist.empty() /* && iters < MAX_ITERS*/) {
+
+    while (!worklist.empty()) {
         MDefinition *def = PopFromWorklist(worklist);
         IonSpew(IonSpew_Range, "recomputing range on %d", def->id());
         SpewRange(def);
         if (def->recomputeRange()) {
             JS_ASSERT(def->range()->lower() <= def->range()->upper());
             IonSpew(IonSpew_Range, "Range changed; adding consumers");
             for (MUseDefIterator use(def); use; use++) {
                 if(!AddToWorklist(worklist, use.def()))
@@ -412,17 +417,16 @@ RangeAnalysis::analyze()
             }
         }
         iters++;
     }
     // Cleanup (in case we stopped due to MAX_ITERS)
     for(size_t i = 0; i < worklist.length(); i++)
         worklist[i]->setNotInWorklist();
 
-#undef MAX_ITERS
 
 #ifdef DEBUG
     for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
         for (MDefinitionIterator iter(*block); iter; iter++) {
             MDefinition *def = *iter;
             SpewRange(def);
             JS_ASSERT(def->range()->lower() <= def->range()->upper());
             JS_ASSERT(!def->isInWorklist());
--- a/js/src/ion/RangeAnalysis.h
+++ b/js/src/ion/RangeAnalysis.h
@@ -101,23 +101,23 @@ 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);
+    void unionWith(const Range *other, bool useNarrowing = false);
 
         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);
 
         inline void makeLowerInfinite() {
             lower_infinite_ = true;
             lower_ = JSVAL_INT_MIN;
         }
         inline void makeUpperInfinite() {
--- a/js/src/ion/arm/CodeGenerator-arm.cpp
+++ b/js/src/ion/arm/CodeGenerator-arm.cpp
@@ -462,22 +462,20 @@ CodeGeneratorARM::visitMulI(LMulI *ins)
         }
         // Bailout on overflow
         if (mul->canOverflow() && !bailoutIf(c, ins->snapshot()))
             return false;
     } else {
         Assembler::Condition c = Assembler::Overflow;
 
         //masm.imull(ToOperand(rhs), ToRegister(lhs));
-        if (mul->canOverflow()) {
+        if (mul->canOverflow())
             c = masm.ma_check_mul(ToRegister(lhs), ToRegister(rhs), ToRegister(dest), c);
-        } else {
+        else
             masm.ma_mul(ToRegister(lhs), ToRegister(rhs), ToRegister(dest));
-        }
-
 
         // Bailout on overflow
         if (mul->canOverflow() && !bailoutIf(c, ins->snapshot()))
             return false;
 
         if (mul->canBeNegativeZero()) {
             Label done;
             masm.ma_cmp(ToRegister(dest), Imm32(0));