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 108987 bca9d7ef2727f1dff6ad72ac739fecb38595d7f7
parent 108986 ba4e134b13fdb90c5eda8ef714c119bf1b503a13
child 108988 2520fd9f388380f2bd057c19ed3f4b694371d61e
push id82
push usershu@rfrn.org
push dateFri, 05 Oct 2012 13:20:22 +0000
reviewersjandem
bugs765119
milestone18.0a1
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)
     { }
 
@@ -2728,26 +2736,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
@@ -5529,16 +5538,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));