Backed out changeset 0a197ef0840c (bug 766592) for talos crashes.
authorRyan VanderMeulen <ryanvm@gmail.com>
Fri, 23 Nov 2012 10:04:14 -0500
changeset 114072 5493ee135368050c2a80ff4a262a0b1f0aebaf65
parent 114071 0a197ef0840cae2f5f493b56362a1ce7af859605
child 114073 85c1a0de5374a3a60526275d09baaf2d6861f89a
push id23901
push userryanvm@gmail.com
push dateFri, 23 Nov 2012 21:11:03 +0000
treeherdermozilla-central@0d373cf880fd [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
bugs766592
milestone20.0a1
backs out0a197ef0840cae2f5f493b56362a1ce7af859605
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
Backed out changeset 0a197ef0840c (bug 766592) for talos crashes.
js/src/ion/Ion.cpp
js/src/ion/IonAnalysis.cpp
js/src/ion/IonAnalysis.h
js/src/ion/JSONSpewer.cpp
js/src/ion/LICM.cpp
js/src/ion/LICM.h
js/src/ion/Lowering.cpp
js/src/ion/MIR.cpp
js/src/ion/MIR.h
js/src/ion/MIRGraph.h
js/src/ion/RangeAnalysis.cpp
js/src/ion/RangeAnalysis.h
--- a/js/src/ion/Ion.cpp
+++ b/js/src/ion/Ion.cpp
@@ -863,27 +863,16 @@ CompileBackEnd(MIRGenerator *mir)
             return NULL;
         IonSpewPass("GVN");
         AssertGraphCoherency(graph);
 
         if (mir->shouldCancel("GVN"))
             return NULL;
     }
 
-    if (js_IonOptions.licm) {
-        LICM licm(mir, graph);
-        if (!licm.analyze())
-            return NULL;
-        IonSpewPass("LICM");
-        AssertGraphCoherency(graph);
-
-        if (mir->shouldCancel("LICM"))
-            return NULL;
-    }
-
     if (js_IonOptions.rangeAnalysis) {
         RangeAnalysis r(graph);
         if (!r.addBetaNobes())
             return NULL;
         IonSpewPass("Beta");
         AssertGraphCoherency(graph);
 
         if (mir->shouldCancel("RA Beta"))
@@ -909,16 +898,27 @@ CompileBackEnd(MIRGenerator *mir)
     if (!EliminateDeadCode(mir, graph))
         return NULL;
     IonSpewPass("DCE");
     AssertGraphCoherency(graph);
 
     if (mir->shouldCancel("DCE"))
         return NULL;
 
+    if (js_IonOptions.licm) {
+        LICM licm(mir, graph);
+        if (!licm.analyze())
+            return NULL;
+        IonSpewPass("LICM");
+        AssertGraphCoherency(graph);
+
+        if (mir->shouldCancel("LICM"))
+            return NULL;
+    }
+
     if (js_IonOptions.edgeCaseAnalysis) {
         EdgeCaseAnalysis edgeCaseAnalysis(mir, graph);
         if (!edgeCaseAnalysis.analyzeLate())
             return NULL;
         IonSpewPass("Edge Case Analysis (Late)");
         AssertGraphCoherency(graph);
 
         if (mir->shouldCancel("Edge Case Analysis (Late)"))
--- a/js/src/ion/IonAnalysis.cpp
+++ b/js/src/ion/IonAnalysis.cpp
@@ -807,17 +807,17 @@ typedef HashMap<uint32,
                 BoundsCheckInfo,
                 DefaultHasher<uint32>,
                 IonAllocPolicy> BoundsCheckMap;
 
 // Compute a hash for bounds checks which ignores constant offsets in the index.
 static HashNumber
 BoundsCheckHashIgnoreOffset(MBoundsCheck *check)
 {
-    SimpleLinearSum indexSum = ExtractLinearSum(check->index());
+    LinearSum indexSum = ExtractLinearSum(check->index());
     uintptr_t index = indexSum.term ? uintptr_t(indexSum.term) : 0;
     uintptr_t length = uintptr_t(check->length());
     return index ^ length;
 }
 
 static MBoundsCheck *
 FindDominatingBoundsCheck(BoundsCheckMap &checks, MBoundsCheck *check, size_t index)
 {
@@ -835,130 +835,67 @@ FindDominatingBoundsCheck(BoundsCheckMap
 
         return check;
     }
 
     return p->value.check;
 }
 
 // Extract a linear sum from ins, if possible (otherwise giving the sum 'ins + 0').
-SimpleLinearSum
+LinearSum
 ion::ExtractLinearSum(MDefinition *ins)
 {
-    if (ins->isBeta())
-        ins = ins->getOperand(0);
-
     if (ins->type() != MIRType_Int32)
-        return SimpleLinearSum(ins, 0);
+        return LinearSum(ins, 0);
 
     if (ins->isConstant()) {
         const Value &v = ins->toConstant()->value();
         JS_ASSERT(v.isInt32());
-        return SimpleLinearSum(NULL, v.toInt32());
+        return LinearSum(NULL, v.toInt32());
     } else if (ins->isAdd() || ins->isSub()) {
         MDefinition *lhs = ins->getOperand(0);
         MDefinition *rhs = ins->getOperand(1);
         if (lhs->type() == MIRType_Int32 && rhs->type() == MIRType_Int32) {
-            SimpleLinearSum lsum = ExtractLinearSum(lhs);
-            SimpleLinearSum rsum = ExtractLinearSum(rhs);
+            LinearSum lsum = ExtractLinearSum(lhs);
+            LinearSum rsum = ExtractLinearSum(rhs);
 
             JS_ASSERT(lsum.term || rsum.term);
             if (lsum.term && rsum.term)
-                return SimpleLinearSum(ins, 0);
+                return LinearSum(ins, 0);
 
             // Check if this is of the form <SUM> + n, n + <SUM> or <SUM> - n.
             if (ins->isAdd()) {
                 int32 constant;
                 if (!SafeAdd(lsum.constant, rsum.constant, &constant))
-                    return SimpleLinearSum(ins, 0);
-                return SimpleLinearSum(lsum.term ? lsum.term : rsum.term, constant);
+                    return LinearSum(ins, 0);
+                return LinearSum(lsum.term ? lsum.term : rsum.term, constant);
             } else if (lsum.term) {
                 int32 constant;
                 if (!SafeSub(lsum.constant, rsum.constant, &constant))
-                    return SimpleLinearSum(ins, 0);
-                return SimpleLinearSum(lsum.term, constant);
+                    return LinearSum(ins, 0);
+                return LinearSum(lsum.term, constant);
             }
         }
     }
 
-    return SimpleLinearSum(ins, 0);
-}
-
-// Extract a linear inequality holding when a boolean test goes in the
-// specified direction, of the form 'lhs + lhsN <= rhs' (or >=).
-bool
-ion::ExtractLinearInequality(MTest *test, BranchDirection direction,
-                             SimpleLinearSum *plhs, MDefinition **prhs, bool *plessEqual)
-{
-    if (!test->getOperand(0)->isCompare())
-        return false;
-
-    MCompare *compare = test->getOperand(0)->toCompare();
-
-    MDefinition *lhs = compare->getOperand(0);
-    MDefinition *rhs = compare->getOperand(1);
-
-    if (compare->specialization() != MIRType_Int32)
-        return false;
-
-    JS_ASSERT(lhs->type() == MIRType_Int32);
-    JS_ASSERT(rhs->type() == MIRType_Int32);
-
-    JSOp jsop = compare->jsop();
-    if (direction == FALSE_BRANCH)
-        jsop = analyze::NegateCompareOp(jsop);
-
-    SimpleLinearSum lsum = ExtractLinearSum(lhs);
-    SimpleLinearSum rsum = ExtractLinearSum(rhs);
-
-    if (!SafeSub(lsum.constant, rsum.constant, &lsum.constant))
-        return false;
-
-    // Normalize operations to use <= or >=.
-    switch (jsop) {
-      case JSOP_LE:
-        *plessEqual = true;
-        break;
-      case JSOP_LT:
-        /* x < y ==> x + 1 <= y */
-        if (!SafeAdd(lsum.constant, 1, &lsum.constant))
-            return false;
-        *plessEqual = true;
-        break;
-      case JSOP_GE:
-        *plessEqual = false;
-        break;
-      case JSOP_GT:
-        /* x > y ==> x - 1 >= y */
-        if (!SafeSub(lsum.constant, 1, &lsum.constant))
-            return false;
-        *plessEqual = false;
-        break;
-      default:
-        return false;
-    }
-
-    *plhs = lsum;
-    *prhs = rsum.term;
-
-    return true;
+    return LinearSum(ins, 0);
 }
 
 static bool
 TryEliminateBoundsCheck(MBoundsCheck *dominating, MBoundsCheck *dominated, bool *eliminated)
 {
     JS_ASSERT(!*eliminated);
 
     // We found two bounds checks with the same hash number, but we still have
     // to make sure the lengths and index terms are equal.
     if (dominating->length() != dominated->length())
         return true;
 
-    SimpleLinearSum sumA = ExtractLinearSum(dominating->index());
-    SimpleLinearSum sumB = ExtractLinearSum(dominated->index());
+    LinearSum sumA = ExtractLinearSum(dominating->index());
+    LinearSum sumB = ExtractLinearSum(dominated->index());
 
     // Both terms should be NULL or the same definition.
     if (sumA.term != sumB.term)
         return true;
 
     // This bounds check is redundant.
     *eliminated = true;
 
@@ -1068,84 +1005,8 @@ ion::EliminateRedundantBoundsChecks(MIRG
                 iter++;
         }
         index++;
     }
 
     JS_ASSERT(index == graph.numBlocks());
     return true;
 }
-
-bool
-LinearSum::multiply(int32 scale)
-{
-    for (size_t i = 0; i < terms_.length(); i++) {
-        if (!SafeMul(scale, terms_[i].scale, &terms_[i].scale))
-            return false;
-    }
-    return SafeMul(scale, constant_, &constant_);
-}
-
-bool
-LinearSum::add(const LinearSum &other)
-{
-    for (size_t i = 0; i < other.terms_.length(); i++) {
-        if (!add(other.terms_[i].term, other.terms_[i].scale))
-            return false;
-    }
-    return add(other.constant_);
-}
-
-bool
-LinearSum::add(MDefinition *term, int32 scale)
-{
-    JS_ASSERT(term);
-
-    if (scale == 0)
-        return true;
-
-    for (size_t i = 0; i < terms_.length(); i++) {
-        if (term == terms_[i].term) {
-            if (!SafeAdd(scale, terms_[i].scale, &terms_[i].scale))
-                return false;
-            if (terms_[i].scale == 0) {
-                terms_[i] = terms_.back();
-                terms_.popBack();
-            }
-            return true;
-        }
-    }
-
-    terms_.append(LinearTerm(term, scale));
-    return true;
-}
-
-bool
-LinearSum::add(int32 constant)
-{
-    return SafeAdd(constant, constant_, &constant_);
-}
-
-void
-LinearSum::print(Sprinter &sp) const
-{
-    for (size_t i = 0; i < terms_.length(); i++) {
-        int32 scale = terms_[i].scale;
-        int32 id = terms_[i].term->id();
-        JS_ASSERT(scale);
-        if (scale > 0) {
-            if (i)
-                sp.printf("+");
-            if (scale == 1)
-                sp.printf("#%d", id);
-            else
-                sp.printf("%d*#%d", scale, id);
-        } else if (scale == -1) {
-            sp.printf("-#%d", id);
-        } else {
-            sp.printf("%d*#%d", scale, id);
-        }
-    }
-    if (constant_ > 0)
-        sp.printf("+%d", constant_);
-    else if (constant_ < 0)
-        sp.printf("%d", constant_);
-}
--- a/js/src/ion/IonAnalysis.h
+++ b/js/src/ion/IonAnalysis.h
@@ -6,17 +6,16 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #ifndef jsion_ion_analysis_h__
 #define jsion_ion_analysis_h__
 
 // This file declares various analysis passes that operate on MIR.
 
 #include "IonAllocPolicy.h"
-#include "MIR.h"
 
 namespace js {
 namespace ion {
 
 class MIRGenerator;
 class MIRGraph;
 
 bool
@@ -41,76 +40,30 @@ bool
 BuildPhiReverseMapping(MIRGraph &graph);
 
 void
 AssertGraphCoherency(MIRGraph &graph);
 
 bool
 EliminateRedundantBoundsChecks(MIRGraph &graph);
 
+// Linear sum of term(s). For now the only linear sums which can be represented
+// are 'n' or 'x + n' (for any computation x).
 class MDefinition;
 
-// Simple linear sum of the form 'n' or 'x + n'.
-struct SimpleLinearSum
+struct LinearSum
 {
     MDefinition *term;
     int32 constant;
 
-    SimpleLinearSum(MDefinition *term, int32 constant)
+    LinearSum(MDefinition *term, int32 constant)
         : term(term), constant(constant)
     {}
 };
 
-SimpleLinearSum
+LinearSum
 ExtractLinearSum(MDefinition *ins);
 
-bool
-ExtractLinearInequality(MTest *test, BranchDirection direction,
-                        SimpleLinearSum *plhs, MDefinition **prhs, bool *plessEqual);
-
-struct LinearTerm
-{
-    MDefinition *term;
-    int32 scale;
-
-    LinearTerm(MDefinition *term, int32 scale)
-      : term(term), scale(scale)
-    {
-    }
-};
-
-// General linear sum of the form 'x1*n1 + x2*n2 + ... + n'
-class LinearSum
-{
-  public:
-    LinearSum()
-      : constant_(0)
-    {
-    }
-
-    LinearSum(const LinearSum &other)
-      : constant_(other.constant_)
-    {
-        for (size_t i = 0; i < other.terms_.length(); i++)
-            terms_.append(other.terms_[i]);
-    }
-
-    bool multiply(int32 scale);
-    bool add(const LinearSum &other);
-    bool add(MDefinition *term, int32 scale);
-    bool add(int32 constant);
-
-    int32 constant() const { return constant_; }
-    size_t numTerms() const { return terms_.length(); }
-    LinearTerm term(size_t i) const { return terms_[i]; }
-
-    void print(Sprinter &sp) const;
-
-  private:
-    Vector<LinearTerm, 2, IonAllocPolicy> terms_;
-    int32 constant_;
-};
-
 } // namespace ion
 } // namespace js
 
 #endif // jsion_ion_analysis_h__
 
--- a/js/src/ion/JSONSpewer.cpp
+++ b/js/src/ion/JSONSpewer.cpp
@@ -8,17 +8,16 @@
 #include <stdarg.h>
 
 #include "JSONSpewer.h"
 #include "LIR.h"
 #include "TypeOracle.h"
 #include "MIR.h"
 #include "MIRGraph.h"
 #include "LinearScan.h"
-#include "RangeAnalysis.h"
 using namespace js;
 using namespace js::ion;
 
 JSONSpewer::~JSONSpewer()
 {
     if (fp_)
         fclose(fp_);
 }
@@ -251,24 +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();
 
-    if (def->range()) {
-        Sprinter sp(GetIonContext()->cx);
-        sp.init();
-        def->range()->print(sp);
-        stringProperty("type", "%s : %s", sp.string());
-    } else {
-        stringProperty("type", "%s", 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/LICM.cpp
+++ b/js/src/ion/LICM.cpp
@@ -12,16 +12,74 @@
 #include "IonSpewer.h"
 #include "LICM.h"
 #include "MIR.h"
 #include "MIRGraph.h"
 
 using namespace js;
 using namespace js::ion;
 
+bool
+ion::ExtractLinearInequality(MTest *test, BranchDirection direction,
+                             LinearSum *plhs, MDefinition **prhs, bool *plessEqual)
+{
+    if (!test->getOperand(0)->isCompare())
+        return false;
+
+    MCompare *compare = test->getOperand(0)->toCompare();
+
+    MDefinition *lhs = compare->getOperand(0);
+    MDefinition *rhs = compare->getOperand(1);
+
+    if (compare->specialization() != MIRType_Int32)
+        return false;
+
+    JS_ASSERT(lhs->type() == MIRType_Int32);
+    JS_ASSERT(rhs->type() == MIRType_Int32);
+
+    JSOp jsop = compare->jsop();
+    if (direction == FALSE_BRANCH)
+        jsop = analyze::NegateCompareOp(jsop);
+
+    LinearSum lsum = ExtractLinearSum(lhs);
+    LinearSum rsum = ExtractLinearSum(rhs);
+
+    if (!SafeSub(lsum.constant, rsum.constant, &lsum.constant))
+        return false;
+
+    // Normalize operations to use <= or >=.
+    switch (jsop) {
+      case JSOP_LE:
+        *plessEqual = true;
+        break;
+      case JSOP_LT:
+        /* x < y ==> x + 1 <= y */
+        if (!SafeAdd(lsum.constant, 1, &lsum.constant))
+            return false;
+        *plessEqual = true;
+        break;
+      case JSOP_GE:
+        *plessEqual = false;
+        break;
+      case JSOP_GT:
+        /* x > y ==> x - 1 >= y */
+        if (!SafeSub(lsum.constant, 1, &lsum.constant))
+            return false;
+        *plessEqual = false;
+        break;
+      default:
+        return false;
+    }
+
+    *plhs = lsum;
+    *prhs = rsum.term;
+
+    return true;
+}
+
 LICM::LICM(MIRGenerator *mir, MIRGraph &graph)
   : mir(mir), graph(graph)
 {
 }
 
 bool
 LICM::analyze()
 {
@@ -115,16 +173,17 @@ Loop::iterateLoopBlocks(MBasicBlock *cur
     }
     return LoopReturn_Success;
 }
 
 bool
 Loop::optimize()
 {
     InstructionQueue invariantInstructions;
+    InstructionQueue boundsChecks;
 
     IonSpew(IonSpew_LICM, "These instructions are in the loop: ");
 
     while (!worklist_.empty()) {
         if (mir->shouldCancel("LICM (worklist)"))
             return false;
 
         MInstruction *ins = popFromWorklist();
@@ -156,43 +215,93 @@ Loop::optimize()
                 if (isInLoop(consumer) && isHoistable(consumer)) {
                     if (!insertInWorklist(consumer->toInstruction()))
                         return false;
                 }
             }
 
             if (IonSpewEnabled(IonSpew_LICM))
                 fprintf(IonSpewFile, " Loop Invariant!\n");
+        } else if (ins->isBoundsCheck()) {
+            if (!boundsChecks.append(ins))
+                return false;
         }
     }
 
-    if (!hoistInstructions(invariantInstructions))
+    if (!hoistInstructions(invariantInstructions, boundsChecks))
         return false;
     return true;
 }
 
 bool
-Loop::hoistInstructions(InstructionQueue &toHoist)
+Loop::hoistInstructions(InstructionQueue &toHoist, InstructionQueue &boundsChecks)
 {
+    // Hoist bounds checks first, so that hoistBoundsCheck can test for
+    // invariant instructions, but delay actual insertion until the end to
+    // handle dependencies on loop invariant instructions.
+    InstructionQueue hoistedChecks;
+    for (size_t i = 0; i < boundsChecks.length(); i++) {
+        MBoundsCheck *ins = boundsChecks[i]->toBoundsCheck();
+        if (isLoopInvariant(ins) || !isInLoop(ins))
+            continue;
+
+        // Try to find a test dominating the bounds check which can be
+        // transformed into a hoistable check. Stop after the first such check
+        // which could be transformed (the one which will be the closest to the
+        // access in the source).
+        MBasicBlock *block = ins->block();
+        while (true) {
+            BranchDirection direction;
+            MTest *branch = block->immediateDominatorBranch(&direction);
+            if (branch) {
+                MInstruction *upper, *lower;
+                tryHoistBoundsCheck(ins, branch, direction, &upper, &lower);
+                if (upper && !hoistedChecks.append(upper))
+                    return false;
+                if (lower && !hoistedChecks.append(lower))
+                    return false;
+                if (upper || lower) {
+                    // Note: replace all uses of the original bounds check with the
+                    // actual index. This is usually done during bounds check elimination,
+                    // but in this case it's safe to do it here since the load/store is
+                    // definitely not loop-invariant, so we will never move it before
+                    // one of the bounds checks we just added.
+                    ins->replaceAllUsesWith(ins->index());
+                    ins->block()->discard(ins);
+                    break;
+                }
+            }
+            MBasicBlock *dom = block->immediateDominator();
+            if (dom == block)
+                break;
+            block = dom;
+        }
+    }
+
     // Move all instructions to the preLoop_ block just before the control instruction.
     for (size_t i = 0; i < toHoist.length(); i++) {
         MInstruction *ins = toHoist[i];
 
         // Loads may have an implicit dependency on either stores (effectful instructions) or
         // control instructions so we should never move these.
         JS_ASSERT(!ins->isControlInstruction());
         JS_ASSERT(!ins->isEffectful());
         JS_ASSERT(ins->isMovable());
 
         if (checkHotness(ins->block())) {
             ins->block()->moveBefore(preLoop_->lastIns(), ins);
             ins->setNotLoopInvariant();
         }
     }
 
+    for (size_t i = 0; i < hoistedChecks.length(); i++) {
+        MInstruction *ins = hoistedChecks[i];
+        preLoop_->insertBefore(preLoop_->lastIns(), ins);
+    }
+
     return true;
 }
 
 bool
 Loop::isInLoop(MDefinition *ins)
 {
     return ins->block()->id() >= header_->id();
 }
@@ -256,8 +365,191 @@ Loop::insertInWorklist(MInstruction *ins
 
 MInstruction*
 Loop::popFromWorklist()
 {
     MInstruction* toReturn = worklist_.popCopy();
     toReturn->setNotInWorklist();
     return toReturn;
 }
+
+// Try to compute hoistable checks for the upper and lower bound on ins,
+// according to a test in the loop which dominates ins.
+//
+// Given a bounds check within a loop which is not loop invariant, we would
+// like to compute loop invariant bounds checks which imply that the inner
+// check will succeed.  These invariant checks can then be added to the
+// preheader, and the inner check eliminated.
+//
+// Example:
+//
+// for (i = v; i < n; i++)
+//   x[i] = 0;
+//
+// There are two constraints captured by the bounds check here: i >= 0, and
+// i < length(x).  'i' is not loop invariant, but we can still hoist these
+// checks:
+//
+// - At the point of the check, it is known that i < n.  Given this,
+//   if n <= length(x) then i < length(x), and since n and length(x) are loop
+//   invariant the former condition can be hoisted and the i < length(x) check
+//   removed.
+//
+// - i is only incremented within the loop, so if its initial value is >= 0
+//   then all its values within the loop will also be >= 0.  The lower bounds
+//   check can be hoisted as v >= 0.
+//
+// tryHoistBoundsCheck encodes this logic.  Given a bounds check B and a test T
+// in the loop dominating that bounds check, where B and T share a non-invariant
+// term lhs, a new check C is computed such that T && C imply B.
+void
+Loop::tryHoistBoundsCheck(MBoundsCheck *ins, MTest *test, BranchDirection direction,
+                          MInstruction **pupper, MInstruction **plower)
+{
+    *pupper = NULL;
+    *plower = NULL;
+
+    if (!isLoopInvariant(ins->length()))
+        return;
+
+    LinearSum lhs(NULL, 0);
+    MDefinition *rhs;
+    bool lessEqual;
+    if (!ExtractLinearInequality(test, direction, &lhs, &rhs, &lessEqual))
+        return;
+
+    // Ensure the rhs is a loop invariant term.
+    if (rhs && !isLoopInvariant(rhs)) {
+        if (lhs.term && !isLoopInvariant(lhs.term))
+            return;
+        MDefinition *temp = lhs.term;
+        lhs.term = rhs;
+        rhs = temp;
+        if (!SafeSub(0, lhs.constant, &lhs.constant))
+            return;
+        lessEqual = !lessEqual;
+    }
+
+    JS_ASSERT_IF(rhs, isLoopInvariant(rhs));
+
+    // Ensure the lhs is a phi node from the start of the loop body.
+    if (!lhs.term || !lhs.term->isPhi() || lhs.term->block() != header_)
+        return;
+
+    // Check if the lhs in the conditional matches the bounds check index.
+    LinearSum index = ExtractLinearSum(ins->index());
+    if (index.term != lhs.term)
+        return;
+
+    if (!lessEqual)
+        return;
+
+    // At the point of the access, it is known that lhs + lhsN <= rhs, and the
+    // bounds check is that lhs + indexN + maximum < length. To ensure the
+    // bounds check holds then, we need to ensure that:
+    //
+    // rhs - lhsN + indexN + maximum < length
+
+    int32 adjustment;
+    if (!SafeSub(index.constant, lhs.constant, &adjustment))
+        return;
+    if (!SafeAdd(adjustment, ins->maximum(), &adjustment))
+        return;
+
+    // For the lower bound, check that lhs + indexN + minimum >= 0, e.g.
+    //
+    // lhs >= -indexN - minimum
+    //
+    // lhs is not loop invariant, but if this condition holds of the backing
+    // variable at loop entry and the variable's value never decreases in the
+    // loop body, it will hold throughout the loop.
+
+    uint32 position = preLoop_->positionInPhiSuccessor();
+    MDefinition *initialIndex = lhs.term->toPhi()->getOperand(position);
+    if (!nonDecreasing(initialIndex, lhs.term))
+        return;
+
+    int32 lowerBound;
+    if (!SafeSub(0, index.constant, &lowerBound))
+        return;
+    if (!SafeSub(lowerBound, ins->minimum(), &lowerBound))
+        return;
+
+    // XXX limit on how much can be hoisted, to ensure ballast works?
+
+    if (!rhs) {
+        rhs = MConstant::New(Int32Value(adjustment));
+        adjustment = 0;
+        preLoop_->insertBefore(preLoop_->lastIns(), rhs->toInstruction());
+    }
+
+    MBoundsCheck *upper = MBoundsCheck::New(rhs, ins->length());
+    upper->setMinimum(adjustment);
+    upper->setMaximum(adjustment);
+
+    MBoundsCheckLower *lower = MBoundsCheckLower::New(initialIndex);
+    lower->setMinimum(lowerBound);
+
+    *pupper = upper;
+    *plower = lower;
+}
+
+// Determine whether the possible value of start (a phi node within the loop)
+// can become smaller than an initial value at loop entry.
+bool
+Loop::nonDecreasing(MDefinition *initial, MDefinition *start)
+{
+    MDefinitionVector worklist;
+    MDefinitionVector seen;
+
+    if (!worklist.append(start))
+        return false;
+
+    while (!worklist.empty()) {
+        MDefinition *def = worklist.popCopy();
+        bool duplicate = false;
+        for (size_t i = 0; i < seen.length() && !duplicate; i++) {
+            if (seen[i] == def)
+                duplicate = true;
+        }
+        if (duplicate)
+            continue;
+        if (!seen.append(def))
+            return false;
+
+        if (def->type() != MIRType_Int32)
+            return false;
+
+        if (!isInLoop(def)) {
+            if (def != initial)
+                return false;
+            continue;
+        }
+
+        if (def->isPhi()) {
+            MPhi *phi = def->toPhi();
+            for (size_t i = 0; i < phi->numOperands(); i++) {
+                if (!worklist.append(phi->getOperand(i)))
+                    return false;
+            }
+            continue;
+        }
+
+        if (def->isAdd()) {
+            if (def->toAdd()->specialization() != MIRType_Int32)
+                return false;
+            MDefinition *lhs = def->toAdd()->getOperand(0);
+            MDefinition *rhs = def->toAdd()->getOperand(1);
+            if (!rhs->isConstant())
+                return false;
+            Value v = rhs->toConstant()->value();
+            if (!v.isInt32() || v.toInt32() < 0)
+                return false;
+            if (!worklist.append(lhs))
+                return false;
+            continue;
+        }
+
+        return false;
+    }
+
+    return true;
+}
--- a/js/src/ion/LICM.h
+++ b/js/src/ion/LICM.h
@@ -28,16 +28,22 @@ class LICM
     MIRGenerator *mir;
     MIRGraph &graph;
 
   public:
     LICM(MIRGenerator *mir, MIRGraph &graph);
     bool analyze();
 };
 
+// Extract a linear inequality holding when a boolean test goes in the
+// specified direction, of the form 'lhs + lhsN <= rhs' (or >=).
+bool
+ExtractLinearInequality(MTest *test, BranchDirection direction,
+                        LinearSum *plhs, MDefinition **prhs, bool *plessEqual);
+
 class Loop
 {
     MIRGenerator *mir;
     MIRGraph &graph;
 
   public:
     // Loop code may return three values:
     enum LoopReturn {
@@ -66,17 +72,17 @@ class Loop
     // the loop is first entered and where hoisted instructions will be placed.
     MBasicBlock* preLoop_;
 
     // This method recursively traverses the graph from the loop footer back through
     // predecessor edges and stops when it reaches the loop header.
     // Along the way it adds instructions to the worklist for invariance testing.
     LoopReturn iterateLoopBlocks(MBasicBlock *current);
 
-    bool hoistInstructions(InstructionQueue &toHoist);
+    bool hoistInstructions(InstructionQueue &toHoist, InstructionQueue &boundsChecks);
 
     // Utility methods for invariance testing and instruction hoisting.
     bool isInLoop(MDefinition *ins);
     bool isLoopInvariant(MInstruction *ins);
     bool isLoopInvariant(MDefinition *ins);
 
     // This method determines if this block hot within a loop.  That is, if it's
     // always or usually run when the loop executes
@@ -85,14 +91,23 @@ class Loop
     // Worklist and worklist usage methods
     InstructionQueue worklist_;
     bool insertInWorklist(MInstruction *ins);
     MInstruction* popFromWorklist();
 
     inline bool isHoistable(const MDefinition *ins) const {
         return ins->isMovable() && !ins->isEffectful();
     }
+
+    // State for hoisting bounds checks. Even if the terms involved in a bounds
+    // check are not loop invariant, we analyze the tests and increments done
+    // in the loop to try to find a stronger condition which can be hoisted.
+
+    void tryHoistBoundsCheck(MBoundsCheck *ins, MTest *test, BranchDirection direction,
+                             MInstruction **pupper, MInstruction **plower);
+
+    bool nonDecreasing(MDefinition *initial, MDefinition *start);
 };
 
 } // namespace ion
 } // namespace js
 
 #endif // jsion_licm_h__
--- a/js/src/ion/Lowering.cpp
+++ b/js/src/ion/Lowering.cpp
@@ -5,17 +5,16 @@
  * 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 "LIR.h"
 #include "Lowering.h"
 #include "MIR.h"
 #include "MIRGraph.h"
 #include "IonSpewer.h"
-#include "RangeAnalysis.h"
 #include "jsanalyze.h"
 #include "jsbool.h"
 #include "jsnum.h"
 #include "jsobjinlines.h"
 #include "shared/Lowering-shared-inl.h"
 
 using namespace js;
 using namespace ion;
--- a/js/src/ion/MIR.cpp
+++ b/js/src/ion/MIR.cpp
@@ -5,17 +5,16 @@
  * 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 "RangeAnalysis.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;
@@ -280,16 +279,21 @@ MConstant::New(const Value &v)
     return new MConstant(v);
 }
 
 MConstant::MConstant(const js::Value &vp)
   : value_(vp)
 {
     setResultType(MIRTypeFromValue(vp));
     setMovable();
+
+    if (type() == MIRType_Int32) {
+        range()->setLower(value().toInt32());
+        range()->setUpper(value().toInt32());
+    }
 }
 
 HashNumber
 MConstant::valueHash() const
 {
     // This disregards some state, since values are 64 bits. But for a hash,
     // it's completely acceptable.
     return (HashNumber)JSVAL_TO_IMPL(value_).asBits;
@@ -467,16 +471,63 @@ 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;
+
+    // Use RangeUpdater rather than Range because it needs to
+    // track if it has been updated yet.
+    RangeUpdater r;
+    JS_ASSERT(getOperand(0)->op() != MDefinition::Op_OsrValue);
+    bool updated = false;
+    for (size_t i = 0; i < numOperands(); i++) {
+        if (getOperand(i)->block()->earlyAbort()) {
+            IonSpew(IonSpew_Range, "Ignoring unreachable input %d", getOperand(i)->id());
+            continue;
+        }
+
+        if (!isOSRLikeValue(getOperand(i))) {
+            if (block()->isLoopHeader()) {
+                IonSpew(IonSpew_Range, "    Updating input #%d (inst %d)", i, getOperand(i)->id());
+                changeCounts_[i].updateRange(getOperand(i)->range());
+                r.unionWith(&changeCounts_[i]);
+            } else {
+                r.unionWith(getOperand(i)->range());
+            }
+
+#ifdef DEBUG
+            if (IonSpewEnabled(IonSpew_Range)) {
+                fprintf(IonSpewFile, "    %d:", getOperand(i)->id());
+                getOperand(i)->range()->printRange(IonSpewFile);
+                fprintf(IonSpewFile, " => ");
+                r.printRange(IonSpewFile);
+                fprintf(IonSpewFile, "\n");
+            }
+#endif
+
+
+        }
+     }
+     if (!updated) {
+         IonSpew(IonSpew_Range, "My block is unreachable %d", id());
+         block()->setEarlyAbort();
+         return false;
+     }
+     return range()->update(r.getRange());
+}
+
 uint32
 MPrepareCall::argc() const
 {
     JS_ASSERT(useCount() == 1);
     MCall *call = usesBegin()->node()->toDefinition()->toCall();
     return call->numStackArgs();
 }
 
@@ -838,22 +889,16 @@ MAdd::updateForReplacement(MDefinition *
 {
     JS_ASSERT(ins_->isAdd());
     MAdd *ins = ins_->toAdd();
     if (isTruncated())
         setTruncated(ins->isTruncated());
     return true;
 }
 
-bool
-MAdd::fallible()
-{
-    return !isTruncated() && (!range() || !range()->isFinite());
-}
-
 void
 MSub::analyzeTruncateBackward()
 {
     if (!isTruncated())
         setTruncated(js::ion::EdgeCaseAnalysis::AllUsesTruncate(this));
 }
 
 bool
@@ -861,22 +906,16 @@ MSub::updateForReplacement(MDefinition *
 {
     JS_ASSERT(ins_->isSub());
     MSub *ins = ins_->toSub();
     if (isTruncated())
         setTruncated(ins->isTruncated());
     return true;
 }
 
-bool
-MSub::fallible()
-{
-    return !isTruncated() && (!range() || !range()->isFinite());
-}
-
 MDefinition *
 MMul::foldsTo(bool useValueNumbers)
 {
     MDefinition *out = MBinaryArithInstruction::foldsTo(useValueNumbers);
     if (out != this)
         return out;
 
     if (specialization() != MIRType_Int32)
@@ -931,34 +970,16 @@ MMul::updateForReplacement(MDefinition *
 {
     JS_ASSERT(ins_->isMul());
     MMul *ins = ins_->toMul();
     if (isPossibleTruncated())
         setPossibleTruncated(ins->isPossibleTruncated());
     return true;
 }
 
-bool
-MMul::canOverflow()
-{
-    if (implicitTruncate_)
-        return false;
-    return !range() || !range()->isFinite();
-}
-
-bool
-MMul::canBeNegativeZero()
-{
-    if (!range())
-        return canBeNegativeZero_;
-    if (range()->lower() > 0 || range()->upper() < 0)
-        return false;
-    return canBeNegativeZero_;
-}
-
 void
 MBinaryArithInstruction::infer(JSContext *cx, const TypeOracle::BinaryTypes &b)
 {
     // Retrieve type information of lhs and rhs
     // Rhs is defaulted to int32 first, 
     // because in some cases there is no rhs type information
     MIRType lhs = MIRTypeFromValueType(b.lhsTypes->getKnownTypeTag());
     MIRType rhs = MIRType_Int32;
@@ -1504,41 +1525,29 @@ MNot::foldsTo(bool useValueNumbers)
 
     // NOT of an undefined or null value is always true
     if (operand()->type() == MIRType_Undefined || operand()->type() == MIRType_Null)
         return MConstant::New(BooleanValue(true));
 
     return this;
 }
 
-bool
-MBoundsCheckLower::fallible()
-{
-    return !range() || range()->lower() < minimum_;
-}
-
 void
 MBeta::printOpcode(FILE *fp)
 {
     PrintOpcodeName(fp, op());
     fprintf(fp, " ");
     getOperand(0)->printName(fp);
     fprintf(fp, " ");
-
-    Sprinter sp(GetIonContext()->cx);
-    sp.init();
-    comparison_->print(sp);
-    fprintf(fp, "%s", sp.string());
+    comparison_.printRange(fp);
 }
 
-void
-MBeta::computeRange()
+bool
+MBeta::recomputeRange()
 {
-    bool emptyRange = false;
-
-    Range *range = Range::intersect(val_->range(), comparison_, &emptyRange);
-    if (emptyRange) {
-        IonSpew(IonSpew_Range, "Marking block for inst %d unexitable", id());
-        block()->setEarlyAbort();
-    } else {
-        setRange(range);
+    bool nullRange = false;
+    bool ret = range()->update(Range::intersect(val_->range(), &comparison_, &nullRange));
+    if (nullRange) {
+            IonSpew(IonSpew_Range, "Marking block for inst %d unexitable", id());
+            block()->setEarlyAbort();
     }
+    return ret;
 }
--- a/js/src/ion/MIR.h
+++ b/js/src/ion/MIR.h
@@ -19,24 +19,22 @@
 #include "TypePolicy.h"
 #include "IonAllocPolicy.h"
 #include "InlineList.h"
 #include "MOpcodes.h"
 #include "FixedArityList.h"
 #include "IonMacroAssembler.h"
 #include "Bailouts.h"
 #include "FixedList.h"
+#include "RangeAnalysis.h"
 #include "CompilerRoot.h"
 
 namespace js {
 namespace ion {
-
 class ValueNumberData;
-class Range;
-
 static const inline
 MIRType MIRTypeFromValue(const js::Value &vp)
 {
     if (vp.isDouble())
         return MIRType_Double;
     return MIRTypeFromValueType(vp.extractNonDoubleType());
 }
 
@@ -225,17 +223,21 @@ class MDefinition : public MNode
         Op_Invalid
     };
 
   private:
     InlineForwardList<MUse> uses_; // Use chain.
     uint32 id_;                    // Instruction ID, which after block re-ordering
                                    // is sorted within a basic block.
     ValueNumberData *valueNumber_; // The instruction's value number (see GVN for details in use)
-    Range *range_;                 // Any computed range for this def.
+
+    // Bug 765126: This should be a pointer. The range should only be allocated if range analysis is
+    // enabled.
+    Range range_;                  // The most specific known range for this def.
+
     MIRType resultType_;           // Representation of result type.
     uint32 flags_;                 // Bit flags.
     union {
         MDefinition *dependency_;  // Implicit dependency (store, call, etc.) of this instruction.
                                    // Used by alias analysis, GVN and LICM.
         uint32 virtualRegister_;   // Used by lowering to map definitions to virtual registers.
     };
 
@@ -285,37 +287,33 @@ class MDefinition : public MNode
     void setTrackedPc(jsbytecode *pc) {
         trackedPc_ = pc;
     }
 
     jsbytecode *trackedPc() {
         return trackedPc_;
     }
 
-    Range *range() const {
-        return range_;
-    }
-    void setRange(Range *range) {
-        range_ = range;
+    Range *range() {
+        return &range_;
     }
 
     virtual HashNumber valueHash() const;
     virtual bool congruentTo(MDefinition* const &ins) const {
         return false;
     }
     bool congruentIfOperandsEqual(MDefinition * const &ins) const;
     virtual MDefinition *foldsTo(bool useValueNumbers);
     virtual void analyzeEdgeCasesForward();
     virtual void analyzeEdgeCasesBackward();
     virtual void analyzeTruncateBackward();
     bool earlyAbortCheck();
-
-    // Compute an absolute or symbolic range for the value of this node.
-    // Ranges are only computed for definitions whose type is int32.
-    virtual void computeRange() {
+    // Propagate a range. Return true if the range changed.
+    virtual bool recomputeRange() {
+        return false;
     }
 
     MNode::Kind kind() const {
         return MNode::Definition;
     }
 
     uint32 id() const {
         JS_ASSERT(block_);
@@ -620,18 +618,16 @@ class MConstant : public MNullaryInstruc
     void printOpcode(FILE *fp);
 
     HashNumber valueHash() const;
     bool congruentTo(MDefinition * const &ins) const;
 
     AliasSet getAliasSet() const {
         return AliasSet::None();
     }
-
-    void computeRange();
 };
 
 class MParameter : public MNullaryInstruction
 {
     int32 index_;
     types::StackTypeSet *typeSet_;
 
   public:
@@ -851,27 +847,16 @@ class MGoto : public MAryControlInstruct
     MBasicBlock *target() {
         return getSuccessor(0);
     }
     AliasSet getAliasSet() const {
         return AliasSet::None();
     }
 };
 
-enum BranchDirection {
-    FALSE_BRANCH,
-    TRUE_BRANCH
-};
-
-static inline BranchDirection
-NegateBranchDirection(BranchDirection dir)
-{
-    return (dir == FALSE_BRANCH) ? TRUE_BRANCH : FALSE_BRANCH;
-}
-
 // Tests if the input instruction evaluates to true or false, and jumps to the
 // start of a corresponding basic block.
 class MTest
   : public MAryControlInstruction<1, 2>,
     public TestPolicy
 {
     MTest(MDefinition *ins, MBasicBlock *if_true, MBasicBlock *if_false) {
         initOperand(0, ins);
@@ -885,19 +870,16 @@ class MTest
                       MBasicBlock *ifTrue, MBasicBlock *ifFalse);
 
     MBasicBlock *ifTrue() const {
         return getSuccessor(0);
     }
     MBasicBlock *ifFalse() const {
         return getSuccessor(1);
     }
-    MBasicBlock *branchSuccessor(BranchDirection dir) const {
-        return (dir == TRUE_BRANCH) ? ifTrue() : ifFalse();
-    }
     TypePolicy *typePolicy() {
         return this;
     }
 
     AliasSet getAliasSet() const {
         return AliasSet::None();
     }
     MDefinition *foldsTo(bool useValueNumbers);
@@ -1714,16 +1696,17 @@ class MToInt32 : public MUnaryInstructio
     bool canBeNegativeZero_;
 
     MToInt32(MDefinition *def)
       : MUnaryInstruction(def),
         canBeNegativeZero_(true)
     {
         setResultType(MIRType_Int32);
         setMovable();
+        range()->set(JSVAL_INT_MIN, JSVAL_INT_MAX);
     }
 
   public:
     INSTRUCTION_HEADER(ToInt32);
     static MToInt32 *New(MDefinition *def)
     {
         return new MToInt32(def);
     }
@@ -1754,16 +1737,17 @@ class MToInt32 : public MUnaryInstructio
 // operations. This is an infallible ValueToECMAInt32.
 class MTruncateToInt32 : public MUnaryInstruction
 {
     MTruncateToInt32(MDefinition *def)
       : MUnaryInstruction(def)
     {
         setResultType(MIRType_Int32);
         setMovable();
+        range()->set(JSVAL_INT_MIN, JSVAL_INT_MAX);
     }
 
   public:
     INSTRUCTION_HEADER(TruncateToInt32);
     static MTruncateToInt32 *New(MDefinition *def)
     {
         return new MTruncateToInt32(def);
     }
@@ -1819,16 +1803,17 @@ class MBitNot
     public BitwisePolicy
 {
   protected:
     MBitNot(MDefinition *input)
       : MUnaryInstruction(input)
     {
         setResultType(MIRType_Int32);
         setMovable();
+        range()->set(JSVAL_INT_MIN, JSVAL_INT_MAX);
     }
 
   public:
     INSTRUCTION_HEADER(BitNot);
     static MBitNot *New(MDefinition *input);
 
     TypePolicy *typePolicy() {
         return this;
@@ -1914,16 +1899,17 @@ class MBinaryBitwiseInstruction
     public BitwisePolicy
 {
   protected:
     MBinaryBitwiseInstruction(MDefinition *left, MDefinition *right)
       : MBinaryInstruction(left, right)
     {
         setResultType(MIRType_Int32);
         setMovable();
+        range()->set(JSVAL_INT_MIN, JSVAL_INT_MAX);
     }
 
   public:
     TypePolicy *typePolicy() {
         return this;
     }
 
     MDefinition *foldsTo(bool useValueNumbers);
@@ -1956,17 +1942,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;
     }
-    void computeRange();
+    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)
     { }
 
@@ -2035,17 +2026,25 @@ class MLsh : public MShiftInstruction
     static MLsh *New(MDefinition *left, MDefinition *right);
 
     MDefinition *foldIfZero(size_t operand) {
         // 0 << x => 0
         // x << 0 => x
         return getOperand(0);
     }
 
-    void computeRange();
+    bool recomputeRange() {
+        MDefinition *right = getOperand(1);
+        if (!right->isConstant())
+            return false;
+
+        int32 c = right->toConstant()->value().toInt32();
+        const Range *other = getOperand(0)->range();
+        return range()->update(Range::shl(other, c));
+    }
 };
 
 class MRsh : public MShiftInstruction
 {
     MRsh(MDefinition *left, MDefinition *right)
       : MShiftInstruction(left, right)
     { }
 
@@ -2053,17 +2052,25 @@ class MRsh : public MShiftInstruction
     INSTRUCTION_HEADER(Rsh);
     static MRsh *New(MDefinition *left, MDefinition *right);
 
     MDefinition *foldIfZero(size_t operand) {
         // 0 >> x => 0
         // x >> 0 => x
         return getOperand(0);
     }
-    void computeRange();
+    bool recomputeRange() {
+        MDefinition *right = getOperand(1);
+        if (!right->isConstant())
+            return false;
+
+        int32 c = right->toConstant()->value().toInt32();
+        Range *other = getOperand(0)->range();
+        return range()->update(Range::shr(other, c));
+    }
 };
 
 class MUrsh : public MShiftInstruction
 {
     bool canOverflow_;
 
     MUrsh(MDefinition *left, MDefinition *right)
       : MShiftInstruction(left, right),
@@ -2128,21 +2135,16 @@ class MBinaryArithInstruction
     }
 
     MDefinition *foldsTo(bool useValueNumbers);
 
     virtual double getIdentity() = 0;
 
     void infer(JSContext *cx, const TypeOracle::BinaryTypes &b);
 
-    void setInt32() {
-        specialization_ = MIRType_Int32;
-        setResultType(MIRType_Int32);
-    }
-
     bool congruentTo(MDefinition *const &ins) const {
         return MBinaryInstruction::congruentTo(ins);
     }
     AliasSet getAliasSet() const {
         if (specialization_ >= MIRType_Object)
             return AliasSet::Store(AliasSet::Any);
         return AliasSet::None();
     }
@@ -2219,17 +2221,27 @@ class MAbs
     }
     bool congruentTo(MDefinition *const &ins) const {
         return congruentIfOperandsEqual(ins);
     }
 
     AliasSet getAliasSet() const {
         return AliasSet::None();
     }
-    void computeRange();
+    bool recomputeRange() {
+        if (specialization_ != MIRType_Int32)
+            return false;
+
+        Range *other = getOperand(0)->range();
+        Range r(0,
+                Max(Range::abs64((int64_t)other->lower()),
+                    Range::abs64((int64_t)other->upper())));
+
+        return range()->update(r);
+    }
 };
 
 // Inline implementation of Math.sqrt().
 class MSqrt
   : public MUnaryInstruction,
     public DoublePolicy<0>
 {
     MSqrt(MDefinition *num)
@@ -2422,18 +2434,28 @@ class MAdd : public MBinaryArithInstruct
     void setTruncated(bool val) {
         implicitTruncate_ = val;
     }
     bool updateForReplacement(MDefinition *ins);
     double getIdentity() {
         return 0;
     }
 
-    bool fallible();
-    void computeRange();
+    bool fallible() {
+        return !isTruncated() && !range()->isFinite();
+    }
+
+    bool recomputeRange() {
+        if (specialization() != MIRType_Int32)
+            return false;
+        Range *left = getOperand(0)->range();
+        Range *right = getOperand(1)->range();
+        Range next = isTruncated() ? Range::addTruncate(left,right) : Range::add(left, right);
+        return range()->update(next);
+    }
 };
 
 class MSub : public MBinaryArithInstruction
 {
     bool implicitTruncate_;
     MSub(MDefinition *left, MDefinition *right)
       : MBinaryArithInstruction(left, right),
         implicitTruncate_(false)
@@ -2455,18 +2477,28 @@ class MSub : public MBinaryArithInstruct
         implicitTruncate_ = val;
     }
     bool updateForReplacement(MDefinition *ins);
 
     double getIdentity() {
         return 0;
     }
 
-    bool fallible();
-    void computeRange();
+    bool fallible() {
+        return !isTruncated() && !range()->isFinite();
+    }
+
+    bool recomputeRange() {
+        if (specialization() != MIRType_Int32)
+            return false;
+        Range *left = getOperand(0)->range();
+        Range *right = getOperand(1)->range();
+        Range next = isTruncated() ? Range::subTruncate(left,right) : Range::sub(left, right);
+        return range()->update(next);
+    }
 };
 
 class MMul : public MBinaryArithInstruction
 {
     // Annotation the result could be a negative zero
     // and we need to guard this during execution.
     bool canBeNegativeZero_;
 
@@ -2503,26 +2535,40 @@ class MMul : public MBinaryArithInstruct
     void analyzeEdgeCasesForward();
     void analyzeEdgeCasesBackward();
     void analyzeTruncateBackward();
 
     double getIdentity() {
         return 1;
     }
 
-    bool canOverflow();
-    bool canBeNegativeZero();
-
+    bool canOverflow() {
+        return !implicitTruncate_ && !range()->isFinite();
+    }
+
+    bool canBeNegativeZero() {
+        if (range()->lower() > 0 || range()->upper() < 0)
+            return false;
+        return canBeNegativeZero_;
+    }
     bool updateForReplacement(MDefinition *ins);
 
     bool fallible() {
         return canBeNegativeZero_ || canOverflow();
     }
 
-    void computeRange();
+    bool recomputeRange() {
+        if (specialization() != MIRType_Int32)
+            return false;
+        Range *left = getOperand(0)->range();
+        Range *right = getOperand(1)->range();
+        if (isPossibleTruncated())
+            implicitTruncate_ = !Range::precisionLossMul(left, right);
+        return range()->update(Range::mul(left, right));
+    }
 
     bool isPossibleTruncated() const {
         return possibleTruncate_;
     }
 
     void setPossibleTruncated(bool truncate) {
         possibleTruncate_ = truncate;
     }
@@ -2604,17 +2650,31 @@ class MMod : public MBinaryArithInstruct
     }
 
     MDefinition *foldsTo(bool useValueNumbers);
     double getIdentity() {
         JS_NOT_REACHED("not used");
         return 1;
     }
 
-    void computeRange();
+    bool recomputeRange() {
+        if (specialization() != MIRType_Int32)
+            return false;
+        Range *rhs = getOperand(1)->range();
+        int64_t a = Range::abs64((int64_t)rhs->lower());
+        int64_t b = Range::abs64((int64_t)rhs->upper());
+        if (a ==0 && b == 0) {
+            // We should never take something % 0.
+            Range r(INT_MIN, INT_MAX);
+            return range()->update(r);
+        }
+        int64_t bound = Max(1-a, b-1);
+        Range r(-bound, bound);
+        return range()->update(r);
+    }
 };
 
 class MConcat
   : public MBinaryInstruction,
     public BinaryStringPolicy
 {
     MConcat(MDefinition *left, MDefinition *right)
       : MBinaryInstruction(left, right)
@@ -2644,16 +2704,18 @@ class MCharCodeAt
   : public MBinaryInstruction,
     public MixPolicy<StringPolicy, IntPolicy<1> >
 {
     MCharCodeAt(MDefinition *str, MDefinition *index)
         : MBinaryInstruction(str, index)
     {
         setMovable();
         setResultType(MIRType_Int32);
+        range()->set(0, 65535); //ECMA 262 says that the integer will be
+                                //non-negative and less than 65535.
     }
 
   public:
     INSTRUCTION_HEADER(CharCodeAt);
 
     static MCharCodeAt *New(MDefinition *str, MDefinition *index) {
         return new MCharCodeAt(str, index);
     }
@@ -2661,18 +2723,16 @@ class MCharCodeAt
     TypePolicy *typePolicy() {
         return this;
     }
 
     virtual AliasSet getAliasSet() const {
         // Strings are immutable, so there is no implicit dependency.
         return AliasSet::None();
     }
-
-    void computeRange();
 };
 
 class MFromCharCode
   : public MUnaryInstruction,
     public IntPolicy<0>
 {
     MFromCharCode(MDefinition *code)
       : MUnaryInstruction(code)
@@ -2695,16 +2755,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);
     }
@@ -2751,47 +2814,49 @@ class MPhi : public MDefinition, public 
     }
     void setIterator() {
         isIterator_ = true;
     }
 
     AliasSet getAliasSet() const {
         return AliasSet::None();
     }
-    void computeRange();
+    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:
-    const Range *comparison_;
+    Range comparison_;
     MDefinition *val_;
-    MBeta(MDefinition *val, const Range *comp)
+    MBeta(MDefinition *val, const Range &comp)
         : MUnaryInstruction(val),
           comparison_(comp),
           val_(val)
     {
-        setResultType(val->type());
     }
 
   public:
     INSTRUCTION_HEADER(Beta);
     void printOpcode(FILE *fp);
-    static MBeta *New(MDefinition *val, const Range *comp)
+    static MBeta *New(MDefinition *val, const Range &comp)
     {
         return new MBeta(val, comp);
     }
 
     AliasSet getAliasSet() const {
         return AliasSet::None();
     }
 
-    void computeRange();
+    bool recomputeRange();
 };
 
 // MIR representation of a Value on the OSR StackFrame.
 // The Value is indexed off of OsrFrameReg.
 class MOsrValue : public MUnaryInstruction
 {
   private:
     ptrdiff_t frameOffset_;
@@ -3439,17 +3504,19 @@ class MBoundsCheckLower
         return minimum_;
     }
     void setMinimum(int32 n) {
         minimum_ = n;
     }
     AliasSet getAliasSet() const {
         return AliasSet::None();
     }
-    bool fallible();
+    bool fallible() {
+        return range()->lower() < minimum_;
+    }
 };
 
 // Load a value from a dense array's element vector and does a hole check if the
 // array is not known to be packed.
 class MLoadElement
   : public MBinaryInstruction,
     public SingleObjectPolicy
 {
@@ -3915,16 +3982,17 @@ class MClampToUint8
   : public MUnaryInstruction,
     public ClampPolicy
 {
     MClampToUint8(MDefinition *input)
       : MUnaryInstruction(input)
     {
         setResultType(MIRType_Int32);
         setMovable();
+        range()->set(0, 255);
     }
 
   public:
     INSTRUCTION_HEADER(ClampToUint8);
 
     static MClampToUint8 *New(MDefinition *input) {
         return new MClampToUint8(input);
     }
@@ -3938,17 +4006,16 @@ class MClampToUint8
         return this;
     }
     bool congruentTo(MDefinition *const &ins) const {
         return congruentIfOperandsEqual(ins);
     }
     AliasSet getAliasSet() const {
         return AliasSet::None();
     }
-    void computeRange();
 };
 
 class MLoadFixedSlot
   : public MUnaryInstruction,
     public SingleObjectPolicy
 {
     size_t slot_;
 
--- a/js/src/ion/MIRGraph.h
+++ b/js/src/ion/MIRGraph.h
@@ -25,16 +25,21 @@ class MStart;
 class MDefinitionIterator;
 
 typedef InlineListIterator<MInstruction> MInstructionIterator;
 typedef InlineListReverseIterator<MInstruction> MInstructionReverseIterator;
 typedef InlineForwardListIterator<MPhi> MPhiIterator;
 
 class LBlock;
 
+enum BranchDirection {
+    FALSE_BRANCH,
+    TRUE_BRANCH
+};
+
 class MBasicBlock : public TempObject, public InlineListNode<MBasicBlock>
 {
   public:
     enum Kind {
         NORMAL,
         PENDING_LOOP_HEADER,
         LOOP_HEADER,
         SPLIT_EDGE
--- a/js/src/ion/RangeAnalysis.cpp
+++ b/js/src/ion/RangeAnalysis.cpp
@@ -3,17 +3,16 @@
  *
  * This Source Code Form is subject to the terms of the Mozilla Public
  * 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 <stdio.h>
 
 #include "Ion.h"
-#include "IonAnalysis.h"
 #include "MIR.h"
 #include "MIRGraph.h"
 #include "RangeAnalysis.h"
 #include "IonSpewer.h"
 
 using namespace js;
 using namespace js::ion;
 
@@ -91,21 +90,21 @@ IsDominatedUse(MBasicBlock *block, MUse 
 
     return block->dominates(n->block());
 }
 
 static inline void
 SpewRange(MDefinition *def)
 {
 #ifdef DEBUG
-    if (IonSpewEnabled(IonSpew_Range) && def->range()) {
-        Sprinter sp(GetIonContext()->cx);
-        sp.init();
-        def->range()->print(sp);
-        IonSpew(IonSpew_Range, "%d has range %s", def->id(), sp.string());
+    if (IonSpewEnabled(IonSpew_Range)) {
+        IonSpewHeader(IonSpew_Range);
+        fprintf(IonSpewFile, "%d has range ", def->id());
+        def->range()->printRange(IonSpewFile);
+        fprintf(IonSpewFile, "\n");
     }
 #endif
 }
 
 void
 RangeAnalysis::replaceDominatedUsesWith(MDefinition *orig, MDefinition *dom,
                                             MBasicBlock *block)
 {
@@ -158,20 +157,20 @@ RangeAnalysis::addBetaNobes()
                 smaller = left;
                 greater = right;
             } else if (jsop == JSOP_GT) {
                 smaller = right;
                 greater = left;
             }
             if (smaller && greater) {
                 MBeta *beta;
-                beta = MBeta::New(smaller, new Range(JSVAL_INT_MIN, JSVAL_INT_MAX-1));
+                beta = MBeta::New(smaller, Range(JSVAL_INT_MIN, JSVAL_INT_MAX-1));
                 block->insertBefore(*block->begin(), beta);
                 replaceDominatedUsesWith(smaller, beta, block);
-                beta = MBeta::New(greater, new Range(JSVAL_INT_MIN+1, JSVAL_INT_MAX));
+                beta = MBeta::New(greater, Range(JSVAL_INT_MIN+1, JSVAL_INT_MAX));
                 block->insertBefore(*block->begin(), beta);
                 replaceDominatedUsesWith(greater, beta, block);
             }
             continue;
         }
 
         JS_ASSERT(val);
 
@@ -198,17 +197,17 @@ RangeAnalysis::addBetaNobes()
             comp.setLower(bound);
             comp.setUpper(bound);
           default:
             break; // well, for neq we could have
                    // [-\inf, bound-1] U [bound+1, \inf] but we only use contiguous ranges.
         }
 
         IonSpew(IonSpew_Range, "Adding beta node for %d", val->id());
-        MBeta *beta = MBeta::New(val, new Range(comp));
+        MBeta *beta = MBeta::New(val, comp);
         block->insertBefore(*block->begin(), beta);
         replaceDominatedUsesWith(val, beta, block);
     }
 
     return true;
 }
 
 bool
@@ -233,237 +232,219 @@ RangeAnalysis::removeBetaNobes()
                 break;
             }
         }
     }
     return true;
 }
 
 void
-SymbolicBound::print(Sprinter &sp) const
-{
-    if (loop)
-        sp.printf("[loop] ");
-    sum.print(sp);
-}
-
-void
-Range::print(Sprinter &sp) const
+Range::printRange(FILE *fp)
 {
     JS_ASSERT_IF(lower_infinite_, lower_ == JSVAL_INT_MIN);
     JS_ASSERT_IF(upper_infinite_, upper_ == JSVAL_INT_MAX);
-
-    sp.printf("[");
-
-    if (lower_infinite_)
-        sp.printf("-inf");
-    else
-        sp.printf("%d", lower_);
-    if (symbolicLower_) {
-        sp.printf(" {");
-        symbolicLower_->print(sp);
-        sp.printf("}");
-    }
-
-    sp.printf(", ");
-
-    if (upper_infinite_)
-        sp.printf("inf");
-    else
-        sp.printf("%d", upper_);
-    if (symbolicUpper_) {
-        sp.printf(" {");
-        symbolicUpper_->print(sp);
-        sp.printf("}");
-    }
-
-    sp.printf("]");
+    fprintf(fp, "[");
+    if (lower_infinite_) { fprintf(fp, "-inf"); } else { fprintf(fp, "%d", lower_); }
+    fprintf(fp, ", ");
+    if (upper_infinite_) { fprintf(fp, "inf"); } else { fprintf(fp, "%d", upper_); }
+    fprintf(fp, "]");
 }
 
-Range *
-Range::intersect(const Range *lhs, const Range *rhs, bool *emptyRange)
+Range
+Range::intersect(const Range *lhs, const Range *rhs, bool *nullRange)
 {
-    *emptyRange = false;
-
-    if (!lhs && !rhs)
-        return NULL;
-
-    if (!lhs)
-        return new Range(*rhs);
-    if (!rhs)
-        return new Range(*lhs);
-
-    Range *r = new Range(
+    Range r(
         Max(lhs->lower_, rhs->lower_),
         Min(lhs->upper_, rhs->upper_));
 
-    r->lower_infinite_ = lhs->lower_infinite_ && rhs->lower_infinite_;
-    r->upper_infinite_ = lhs->upper_infinite_ && rhs->upper_infinite_;
+    r.lower_infinite_ = lhs->lower_infinite_ && rhs->lower_infinite_;
+    r.upper_infinite_ = lhs->upper_infinite_ && rhs->upper_infinite_;
 
     // :TODO: This information could be used better. If upper < lower, then we
     // have conflicting constraints. Consider:
     //
     // if (x < 0) {
     //   if (x > 0) {
     //     [Some code.]
     //   }
     // }
     //
     // In this case, the block is dead. Right now, we just disregard this fact
     // and make the range infinite, rather than empty.
     //
     // Instead, we should use it to eliminate the dead block.
     // (Bug 765127)
-    if (r->upper_ < r->lower_) {
-        *emptyRange = true;
-        r->makeRangeInfinite();
+    if (r.upper_ < r.lower_) {
+        *nullRange = true;
+        r.makeRangeInfinite();
     }
-
     return r;
 }
 
 void
 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_;
 }
 
-static const Range emptyRange;
-
-static inline void
-EnsureRange(const Range **prange)
+void
+RangeUpdater::updateLower(const Range *other)
 {
-    if (!*prange)
-        *prange = &emptyRange;
+    if (lowerSet_) {
+        r_.setLower(Min(r_.lower(), other->lower()));
+    } else {
+        r_.setLower(other->lower());
+        lowerSet_ = true;
+    }
+    if (other->isLowerInfinite())
+        r_.makeLowerInfinite();
 }
-
-Range *
-Range::add(const Range *lhs, const Range *rhs)
+void
+RangeUpdater::updateUpper(const Range *other)
 {
-    EnsureRange(&lhs);
-    EnsureRange(&rhs);
-    return new Range(
-        (int64_t)lhs->lower_ + (int64_t)rhs->lower_,
-        (int64_t)lhs->upper_ + (int64_t)rhs->upper_);
+    if (upperSet_) {
+        r_.setUpper(Min(r_.upper(), other->upper()));
+    } else {
+        r_.setUpper(other->upper());
+        upperSet_ = true;
+    }
+    if (other->isUpperInfinite())
+        r_.makeUpperInfinite();
 }
 
-Range *
-Range::sub(const Range *lhs, const Range *rhs)
+void
+RangeUpdater::unionWith(const Range *other)
 {
-    EnsureRange(&lhs);
-    EnsureRange(&rhs);
-    return new Range(
-        (int64_t)lhs->lower_ - (int64_t)rhs->upper_,
-        (int64_t)lhs->upper_ - (int64_t)rhs->lower_);
+    updateLower(other);
+    updateUpper(other);
 }
 
-/* static */ Range *
-Range::Truncate(int64_t l, int64_t h)
+void
+RangeUpdater::unionWith(RangeChangeCount *other)
 {
-    Range *ret = new Range(l, h);
-    if (!ret->isFinite()) {
-        ret->makeLowerInfinite();
-        ret->makeUpperInfinite();
+    if (other->lowerCount_ <= 2) {
+        // If this->lower has been initialized, then update it
+        // otherwise, initialize it.
+        updateLower(&other->oldRange);
+    } else {
+        other->lowerCount_ = 0;
     }
+
+    if (other->upperCount_ <= 2) {
+        updateUpper(&other->oldRange);
+    } 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_);
     return ret;
 }
 
-Range *
+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::addTruncate(const Range *lhs, const Range *rhs)
 {
-    EnsureRange(&lhs);
-    EnsureRange(&rhs);
-    return Truncate((int64_t)lhs->lower_ + (int64_t)rhs->lower_,
-                    (int64_t)lhs->upper_ + (int64_t)rhs->upper_);
+    Range ret = Truncate((int64_t)lhs->lower_ + (int64_t)rhs->lower_,
+                         (int64_t)lhs->upper_ + (int64_t)rhs->upper_);
+    return ret;
 }
 
-Range *
+Range
 Range::subTruncate(const Range *lhs, const Range *rhs)
 {
-    EnsureRange(&lhs);
-    EnsureRange(&rhs);
-    return Truncate((int64_t)lhs->lower_ - (int64_t)rhs->upper_,
-                    (int64_t)lhs->upper_ - (int64_t)rhs->lower_);
+    Range ret = Truncate((int64_t)lhs->lower_ - (int64_t)rhs->upper_,
+                         (int64_t)lhs->upper_ - (int64_t)rhs->lower_);
+    return ret;
 }
 
-Range *
+Range
 Range::and_(const Range *lhs, const Range *rhs)
 {
-    EnsureRange(&lhs);
-    EnsureRange(&rhs);
-
     int64_t lower;
     int64_t upper;
 
     // If both numbers can be negative, result can be negative in the whole range
     if (lhs->lower_ < 0 && rhs->lower_ < 0) {
         lower = INT_MIN;
         upper = Max(lhs->upper_, rhs->upper_);
-        return new Range(lower, upper);
+        Range ret(lower, upper);
+        return ret;
     }
 
     // Only one of both numbers can be negative.
     // - result can't be negative
     // - Upper bound is minimum of both upper range,
     lower = 0;
     upper = Min(lhs->upper_, rhs->upper_);
 
     // EXCEPT when upper bound of non negative number is max value,
     // because negative value can return the whole max value.
     // -1 & 5 = 5
     if (lhs->lower_ < 0)
        upper = rhs->upper_;
     if (rhs->lower_ < 0)
         upper = lhs->upper_;
 
-    return new Range(lower, upper);
+    Range ret(lower, upper);
+    return ret;
+
 }
-
-Range *
+Range
 Range::mul(const Range *lhs, const Range *rhs)
 {
-    EnsureRange(&lhs);
-    EnsureRange(&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_;
-    return new Range(
+    Range ret(
         Min( Min(a, b), Min(c, d) ),
         Max( Max(a, b), Max(c, d) ));
+    return ret;
 }
 
-Range *
+Range
 Range::shl(const Range *lhs, int32 c)
 {
-    EnsureRange(&lhs);
     int32 shift = c & 0x1f;
-    return new Range(
+    Range ret(
         (int64_t)lhs->lower_ << shift,
         (int64_t)lhs->upper_ << shift);
+    return ret;
 }
 
-Range *
+Range
 Range::shr(const Range *lhs, int32 c)
 {
-    EnsureRange(&lhs);
     int32 shift = c & 0x1f;
-    return new Range(
+    Range ret(
         (int64_t)lhs->lower_ >> shift,
         (int64_t)lhs->upper_ >> shift);
+    return ret;
 }
 
 bool
 Range::precisionLossMul(const Range *lhs, const Range *rhs)
 {
-    EnsureRange(&lhs);
-    EnsureRange(&rhs);
     int64_t loss  = 1LL<<53; // result must be lower than 2^53
     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_;
     int64_t lower = Min( Min(a, b), Min(c, d) );
     int64_t upper = Max( Max(a, b), Max(c, d) );
     if (lower < 0)
@@ -487,606 +468,88 @@ Range::update(const Range *other)
         lower_infinite_ = other->lower_infinite_;
         upper_ = other->upper_;
         upper_infinite_ = other->upper_infinite_;
     }
 
     return changed;
 }
 
-///////////////////////////////////////////////////////////////////////////////
-// Range Computation for MIR Nodes
-///////////////////////////////////////////////////////////////////////////////
-
-void
-MPhi::computeRange()
-{
-    if (type() != MIRType_Int32)
-        return;
-
-    Range *range = NULL;
-    JS_ASSERT(getOperand(0)->op() != MDefinition::Op_OsrValue);
-    for (size_t i = 0; i < numOperands(); i++) {
-        if (getOperand(i)->block()->earlyAbort()) {
-            IonSpew(IonSpew_Range, "Ignoring unreachable input %d", getOperand(i)->id());
-            continue;
-        }
-
-        if (isOSRLikeValue(getOperand(i)))
-            continue;
-
-        Range *input = getOperand(i)->range();
-
-        if (!input) {
-            range = NULL;
-            break;
-        }
-
-        if (range)
-            range->unionWith(input);
-        else
-            range = new Range(*input);
-    }
-
-    setRange(range);
-
-    if (block()->isLoopHeader()) {
-    }
-}
-
-void
-MConstant::computeRange()
-{
-    if (type() == MIRType_Int32)
-        setRange(new Range(value().toInt32(), value().toInt32()));
-}
-
-void
-MCharCodeAt::computeRange()
-{
-    setRange(new Range(0, 65535)); //ECMA 262 says that the integer will be
-                                   //non-negative and at most 65535.
-}
-
-void
-MClampToUint8::computeRange()
-{
-    setRange(new Range(0, 255));
-}
-
-void
-MBitAnd::computeRange()
-{
-    Range *left = getOperand(0)->range();
-    Range *right = getOperand(1)->range();
-    setRange(Range::and_(left, right));
-}
-
-void
-MLsh::computeRange()
-{
-    MDefinition *right = getOperand(1);
-    if (!right->isConstant())
-        return;
-
-    int32 c = right->toConstant()->value().toInt32();
-    const Range *other = getOperand(0)->range();
-    setRange(Range::shl(other, c));
-}
-
-void
-MRsh::computeRange()
+static inline bool
+AddToWorklist(MDefinitionVector &worklist, MDefinition *def)
 {
-    MDefinition *right = getOperand(1);
-    if (!right->isConstant())
-        return;
-
-    int32 c = right->toConstant()->value().toInt32();
-    Range *other = getOperand(0)->range();
-    setRange(Range::shr(other, c));
-}
-
-void
-MAbs::computeRange()
-{
-    if (specialization_ != MIRType_Int32)
-        return;
-
-    const Range *other = getOperand(0)->range();
-    EnsureRange(&other);
-
-    Range *range = new Range(0,
-                             Max(Range::abs64((int64_t)other->lower()),
-                                 Range::abs64((int64_t)other->upper())));
-    setRange(range);
-}
-
-void
-MAdd::computeRange()
-{
-    if (specialization() != MIRType_Int32)
-        return;
-    Range *left = getOperand(0)->range();
-    Range *right = getOperand(1)->range();
-    Range *next = isTruncated() ? Range::addTruncate(left,right) : Range::add(left, right);
-    setRange(next);
-}
-
-void
-MSub::computeRange()
-{
-    if (specialization() != MIRType_Int32)
-        return;
-    Range *left = getOperand(0)->range();
-    Range *right = getOperand(1)->range();
-    Range *next = isTruncated() ? Range::subTruncate(left,right) : Range::sub(left, right);
-    setRange(next);
-}
-
-void
-MMul::computeRange()
-{
-    if (specialization() != MIRType_Int32)
-        return;
-    Range *left = getOperand(0)->range();
-    Range *right = getOperand(1)->range();
-    if (isPossibleTruncated())
-        implicitTruncate_ = !Range::precisionLossMul(left, right);
-    setRange(Range::mul(left, right));
-}
-
-void
-MMod::computeRange()
-{
-    if (specialization() != MIRType_Int32)
-        return;
-    const Range *rhs = getOperand(1)->range();
-    EnsureRange(&rhs);
-    int64_t a = Range::abs64((int64_t)rhs->lower());
-    int64_t b = Range::abs64((int64_t)rhs->upper());
-    if (a == 0 && b == 0)
-        return;
-    int64_t bound = Max(1-a, b-1);
-    setRange(new Range(-bound, bound));
-}
-
-///////////////////////////////////////////////////////////////////////////////
-// Range Analysis
-///////////////////////////////////////////////////////////////////////////////
-
-void
-RangeAnalysis::markBlocksInLoopBody(MBasicBlock *header, MBasicBlock *current)
-{
-    // Visited.
-    current->mark();
-
-    // If we haven't reached the loop header yet, recursively explore predecessors
-    // if we haven't seen them already.
-    if (current != header) {
-        for (size_t i = 0; i < current->numPredecessors(); i++) {
-            if (current->getPredecessor(i)->isMarked())
-                continue;
-            markBlocksInLoopBody(header, current->getPredecessor(i));
-        }
-    }
+    if (def->isInWorklist())
+        return true;
+    def->setInWorklist();
+    return worklist.append(def);
 }
 
-void
-RangeAnalysis::analyzeLoop(MBasicBlock *header)
-{
-    // Try to compute an upper bound on the number of times the loop backedge
-    // will be taken. Look for tests that dominate the backedge and which have
-    // an edge leaving the loop body.
-    MBasicBlock *backedge = header->backedge();
-
-    // Ignore trivial infinite loops.
-    if (backedge == header)
-        return;
-
-    markBlocksInLoopBody(header, backedge);
-
-    LoopIterationBound *iterationBound = NULL;
-
-    MBasicBlock *block = backedge;
-    do {
-        BranchDirection direction;
-        MTest *branch = block->immediateDominatorBranch(&direction);
-
-        if (block == block->immediateDominator())
-            break;
-
-        block = block->immediateDominator();
-
-        if (branch) {
-            direction = NegateBranchDirection(direction);
-            MBasicBlock *otherBlock = branch->branchSuccessor(direction);
-            if (!otherBlock->isMarked()) {
-                iterationBound =
-                    analyzeLoopIterationCount(header, branch, direction);
-                if (iterationBound)
-                    break;
-            }
-        }
-    } while (block != header);
-
-    if (!iterationBound) {
-        graph_.unmarkBlocks();
-        return;
-    }
-
-#ifdef DEBUG
-    if (IonSpewEnabled(IonSpew_Range)) {
-        Sprinter sp(GetIonContext()->cx);
-        sp.init();
-        iterationBound->sum.print(sp);
-        IonSpew(IonSpew_Range, "computed symbolic bound on backedges: %s",
-                sp.string());
-    }
-#endif
-
-    // Try to compute symbolic bounds for the phi nodes at the head of this
-    // loop, expressed in terms of the iteration bound just computed.
-
-    for (MDefinitionIterator iter(header); iter; iter++) {
-        MDefinition *def = *iter;
-        if (def->isPhi())
-            analyzeLoopPhi(header, iterationBound, def->toPhi());
-    }
-
-    // Try to hoist any bounds checks from the loop using symbolic bounds.
-
-    Vector<MBoundsCheck *, 0, IonAllocPolicy> hoistedChecks;
-
-    for (ReversePostorderIterator iter(graph_.rpoBegin()); iter != graph_.rpoEnd(); iter++) {
-        MBasicBlock *block = *iter;
-        if (!block->isMarked())
-            continue;
-
-        for (MDefinitionIterator iter(block); iter; iter++) {
-            MDefinition *def = *iter;
-            if (def->isBoundsCheck() && def->isMovable()) {
-                if (tryHoistBoundsCheck(header, def->toBoundsCheck()))
-                    hoistedChecks.append(def->toBoundsCheck());
-            }
-        }
-    }
-
-    // Note: replace all uses of the original bounds check with the
-    // actual index. This is usually done during bounds check elimination,
-    // but in this case it's safe to do it here since the load/store is
-    // definitely not loop-invariant, so we will never move it before
-    // one of the bounds checks we just added.
-    for (size_t i = 0; i < hoistedChecks.length(); i++) {
-        MBoundsCheck *ins = hoistedChecks[i];
-        ins->replaceAllUsesWith(ins->index());
-        ins->block()->discard(ins);
-    }
-
-    graph_.unmarkBlocks();
-}
-
-LoopIterationBound *
-RangeAnalysis::analyzeLoopIterationCount(MBasicBlock *header,
-                                         MTest *test, BranchDirection direction)
+static inline MDefinition *
+PopFromWorklist(MDefinitionVector &worklist)
 {
-    SimpleLinearSum lhs(NULL, 0);
-    MDefinition *rhs;
-    bool lessEqual;
-    if (!ExtractLinearInequality(test, direction, &lhs, &rhs, &lessEqual))
-        return NULL;
-
-    // Ensure the rhs is a loop invariant term.
-    if (rhs && rhs->block()->isMarked()) {
-        if (lhs.term && lhs.term->block()->isMarked())
-            return NULL;
-        MDefinition *temp = lhs.term;
-        lhs.term = rhs;
-        rhs = temp;
-        if (!SafeSub(0, lhs.constant, &lhs.constant))
-            return NULL;
-        lessEqual = !lessEqual;
-    }
-
-    JS_ASSERT_IF(rhs, !rhs->block()->isMarked());
-
-    // Ensure the lhs is a phi node from the start of the loop body.
-    if (!lhs.term || !lhs.term->isPhi() || lhs.term->block() != header)
-        return NULL;
-
-    // Check that the value of the lhs changes by a constant amount with each
-    // loop iteration. This requires that the lhs be written in every loop
-    // iteration with a value that is a constant difference from its value at
-    // the start of the iteration.
-
-    if (lhs.term->toPhi()->numOperands() != 2)
-        return NULL;
-
-    // The first operand of the phi should be the lhs' value at the start of
-    // the first executed iteration, and not a value written which could
-    // replace the second operand below during the middle of execution.
-    MDefinition *lhsInitial = lhs.term->toPhi()->getOperand(0);
-    if (lhsInitial->block()->isMarked())
-        return NULL;
-
-    // The second operand of the phi should be a value written by an add/sub
-    // in every loop iteration, i.e. in a block which dominates the backedge.
-    MDefinition *lhsWrite = lhs.term->toPhi()->getOperand(1);
-    if (lhsWrite->isBeta())
-        lhsWrite = lhsWrite->getOperand(0);
-    if (!lhsWrite->isAdd() && !lhsWrite->isSub())
-        return NULL;
-    if (!lhsWrite->block()->isMarked())
-        return NULL;
-    MBasicBlock *bb = header->backedge();
-    for (; bb != lhsWrite->block() && bb != header; bb = bb->immediateDominator()) {}
-    if (bb != lhsWrite->block())
-        return NULL;
-
-    SimpleLinearSum lhsModified = ExtractLinearSum(lhsWrite);
-
-    // Check that the value of the lhs at the backedge is of the form
-    // 'old(lhs) + N'. We can be sure that old(lhs) is the value at the start
-    // of the iteration, and not that written to lhs in a previous iteration,
-    // as such a previous value could not appear directly in the addition:
-    // it could not be stored in lhs as the lhs add/sub executes in every
-    // iteration, and if it were stored in another variable its use here would
-    // be as an operand to a phi node for that variable.
-    if (lhsModified.term != lhs.term)
-        return NULL;
-
-    LinearSum bound;
-
-    if (lhsModified.constant == 1 && !lessEqual) {
-        // The value of lhs is 'initial(lhs) + iterCount' and this will end
-        // execution of the loop if 'lhs + lhsN >= rhs'. Thus, an upper bound
-        // on the number of backedges executed is:
-        //
-        // initial(lhs) + iterCount + lhsN == rhs
-        // iterCount == rhsN - initial(lhs) - lhsN
-
-        if (rhs)
-            bound.add(rhs, 1);
-        bound.add(lhsInitial, -1);
-
-        int32 lhsConstant;
-        if (!SafeSub(0, lhs.constant, &lhsConstant))
-            return NULL;
-        bound.add(lhsConstant);
-    } else if (lhsModified.constant == -1 && lessEqual) {
-        // The value of lhs is 'initial(lhs) - iterCount'. Similar to the above
-        // case, an upper bound on the number of backedges executed is:
-        //
-        // initial(lhs) - iterCount + lhsN == rhs
-        // iterCount == initial(lhs) - rhs + lhsN
-
-        bound.add(lhsInitial, 1);
-        if (rhs)
-            bound.add(rhs, -1);
-        bound.add(lhs.constant);
-    } else {
-        return NULL;
-    }
-
-    return new LoopIterationBound(header, test, bound);
-}
-
-void
-RangeAnalysis::analyzeLoopPhi(MBasicBlock *header, LoopIterationBound *loopBound, MPhi *phi)
-{
-    // Given a bound on the number of backedges taken, compute an upper and
-    // lower bound for a phi node that may change by a constant amount each
-    // iteration. Unlike for the case when computing the iteration bound
-    // itself, the phi does not need to change the same amount every iteration,
-    // but is required to change at most N and be either nondecreasing or
-    // nonincreasing.
-
-    if (phi->numOperands() != 2)
-        return;
-
-    MBasicBlock *preLoop = header->loopPredecessor();
-    JS_ASSERT(!preLoop->isMarked() && preLoop->successorWithPhis() == header);
-
-    MBasicBlock *backedge = header->backedge();
-    JS_ASSERT(backedge->isMarked() && backedge->successorWithPhis() == header);
-
-    MDefinition *initial = phi->getOperand(preLoop->positionInPhiSuccessor());
-    if (initial->block()->isMarked())
-        return;
-
-    SimpleLinearSum modified = ExtractLinearSum(phi->getOperand(backedge->positionInPhiSuccessor()));
-
-    if (modified.term != phi || modified.constant == 0)
-        return;
-
-    if (!phi->range())
-        phi->setRange(new Range());
-
-    LinearSum initialSum;
-    initialSum.add(initial, 1);
-
-    // The phi may change by N each iteration, and is either nondecreasing or
-    // nonincreasing. initial(phi) is either a lower or upper bound for the
-    // phi, and initial(phi) + loopBound * N is either an upper or lower bound,
-    // at all points within the loop, provided that loopBound >= 0.
-    //
-    // We are more interested, however, in the bound for phi at points
-    // dominated by the loop bound's test; if the test dominates e.g. a bounds
-    // check we want to hoist from the loop, using the value of the phi at the
-    // head of the loop for this will usually be too imprecise to hoist the
-    // check. These points will execute only if the backedge executes at least
-    // one more time (as the test passed and the test dominates the backedge),
-    // so we know both that loopBound >= 1 and that the phi's value has changed
-    // at most loopBound - 1 times. Thus, another upper or lower bound for the
-    // phi is initial(phi) + (loopBound - 1) * N, without requiring us to
-    // ensure that loopBound >= 0.
-
-    LinearSum limitSum(loopBound->sum);
-    if (!limitSum.multiply(modified.constant) || !limitSum.add(initialSum))
-        return;
-
-    int32 negativeConstant;
-    if (!SafeSub(0, modified.constant, &negativeConstant) || !limitSum.add(negativeConstant))
-        return;
-
-    if (modified.constant > 0) {
-        phi->range()->setSymbolicLower(new SymbolicBound(NULL, initialSum));
-        phi->range()->setSymbolicUpper(new SymbolicBound(loopBound, limitSum));
-    } else {
-        phi->range()->setSymbolicUpper(new SymbolicBound(NULL, initialSum));
-        phi->range()->setSymbolicLower(new SymbolicBound(loopBound, limitSum));
-    }
-
-    IonSpew(IonSpew_Range, "added symbolic range on %d", phi->id());
-    SpewRange(phi);
-}
-
-// Whether bound is valid at the specified bounds check instruction in a loop,
-// and may be used to hoist ins.
-static inline bool
-SymbolicBoundIsValid(MBasicBlock *header, MBoundsCheck *ins, const SymbolicBound *bound)
-{
-    if (!bound->loop)
-        return true;
-    if (ins->block() == header)
-        return false;
-    MBasicBlock *bb = ins->block()->immediateDominator();
-    while (bb != header && bb != bound->loop->test->block())
-        bb = bb->immediateDominator();
-    return bb == bound->loop->test->block();
-}
-
-// Convert all components of a linear sum *except* its constant to a definition,
-// adding any necessary instructions to the end of block.
-static inline MDefinition *
-ConvertLinearSum(MBasicBlock *block, const LinearSum &sum)
-{
-    MDefinition *def = NULL;
-
-    for (size_t i = 0; i < sum.numTerms(); i++) {
-        LinearTerm term = sum.term(i);
-        if (term.scale == 1) {
-            if (def) {
-                def = MAdd::New(def, term.term);
-                def->toAdd()->setInt32();
-                block->insertBefore(block->lastIns(), def->toInstruction());
-            } else {
-                def = term.term;
-            }
-        } else {
-            if (!def) {
-                def = MConstant::New(Int32Value(0));
-                block->insertBefore(block->lastIns(), def->toInstruction());
-            }
-            if (term.scale == -1) {
-                def = MSub::New(def, term.term);
-                def->toSub()->setInt32();
-                block->insertBefore(block->lastIns(), def->toInstruction());
-            } else {
-                MConstant *factor = MConstant::New(Int32Value(term.scale));
-                block->insertBefore(block->lastIns(), factor);
-                MMul *mul = MMul::New(term.term, factor);
-                mul->setInt32();
-                block->insertBefore(block->lastIns(), mul);
-                def = MAdd::New(def, mul);
-                block->insertBefore(block->lastIns(), def->toInstruction());
-            }
-        }
-    }
-
-    if (!def) {
-        def = MConstant::New(Int32Value(0));
-        block->insertBefore(block->lastIns(), def->toInstruction());
-    }
-
+    JS_ASSERT(!worklist.empty());
+    MDefinition *def = worklist.popCopy();
+    def->setNotInWorklist();
     return def;
 }
 
-bool
-RangeAnalysis::tryHoistBoundsCheck(MBasicBlock *header, MBoundsCheck *ins)
-{
-    // The bounds check's length must be loop invariant.
-    if (ins->length()->block()->isMarked())
-        return false;
-
-    // The bounds check's index should not be loop invariant (else we would
-    // already have hoisted it during LICM).
-    SimpleLinearSum index = ExtractLinearSum(ins->index());
-    if (!index.term || !index.term->block()->isMarked())
-        return false;
-
-    // Check for a symbolic lower and upper bound on the index. If either
-    // condition depends on an iteration bound for the loop, only hoist if
-    // the bounds check is dominated by the iteration bound's test.
-    if (!index.term->range())
-        return false;
-    const SymbolicBound *lower = index.term->range()->symbolicLower();
-    if (!lower || !SymbolicBoundIsValid(header, ins, lower))
-        return false;
-    const SymbolicBound *upper = index.term->range()->symbolicUpper();
-    if (!upper || !SymbolicBoundIsValid(header, ins, upper))
-        return false;
-
-    MBasicBlock *preLoop = header->loopPredecessor();
-    JS_ASSERT(!preLoop->isMarked());
-
-    MDefinition *lowerTerm = ConvertLinearSum(preLoop, lower->sum);
-    if (!lowerTerm)
-        return false;
-
-    MDefinition *upperTerm = ConvertLinearSum(preLoop, upper->sum);
-    if (!upperTerm)
-        return false;
-
-    // We are checking that index + indexConstant >= 0, and know that
-    // index >= lowerTerm + lowerConstant. Thus, check that:
-    //
-    // lowerTerm + lowerConstant + indexConstant >= 0
-    // lowerTerm >= -lowerConstant - indexConstant
-
-    int32 lowerConstant = 0;
-    if (!SafeSub(lowerConstant, index.constant, &lowerConstant))
-        return false;
-    if (!SafeSub(lowerConstant, lower->sum.constant(), &lowerConstant))
-        return false;
-    MBoundsCheckLower *lowerCheck = MBoundsCheckLower::New(lowerTerm);
-    lowerCheck->setMinimum(lowerConstant);
-
-    // We are checking that index < boundsLength, and know that
-    // index <= upperTerm + upperConstant. Thus, check that:
-    //
-    // upperTerm + upperConstant < boundsLength
-
-    int32 upperConstant = index.constant;
-    if (!SafeAdd(upper->sum.constant(), upperConstant, &upperConstant))
-        return false;
-    MBoundsCheck *upperCheck = MBoundsCheck::New(upperTerm, ins->length());
-    upperCheck->setMinimum(upperConstant);
-    upperCheck->setMaximum(upperConstant);
-
-    // Hoist the loop invariant upper and lower bounds checks.
-    preLoop->insertBefore(preLoop->lastIns(), lowerCheck);
-    preLoop->insertBefore(preLoop->lastIns(), upperCheck);
-
-    return true;
-}
 
 bool
 RangeAnalysis::analyze()
 {
-    IonSpew(IonSpew_Range, "Doing range propagation");
+    int numBlocks = 0;
+    for (PostorderIterator i(graph_.poBegin()); i != graph_.poEnd(); i++) {
+        numBlocks++;
+        MBasicBlock *curBlock = *i;
+        if (!curBlock->isLoopHeader())
+            continue;
+        for (MPhiIterator pi(curBlock->phisBegin()); pi != curBlock->phisEnd(); pi++)
+            if (!pi->initCounts())
+                return false;
+    }
 
-    for (ReversePostorderIterator iter(graph_.rpoBegin()); iter != graph_.rpoEnd(); iter++) {
-        MBasicBlock *block = *iter;
+    IonSpew(IonSpew_Range, "Doing range propagation");
+    MDefinitionVector worklist;
 
-        for (MDefinitionIterator iter(block); iter; iter++) {
+    for (ReversePostorderIterator block(graph_.rpoBegin()); block != graph_.rpoEnd(); block++) {
+        for (MDefinitionIterator iter(*block); iter; iter++) {
             MDefinition *def = *iter;
 
-            def->computeRange();
-            IonSpew(IonSpew_Range, "computing range on %d", def->id());
-            SpewRange(def);
+            AddToWorklist(worklist, def);
+
         }
+    }
+    size_t iters = 0;
 
-        if (block->isLoopHeader())
-            analyzeLoop(block);
+    while (!worklist.empty()) {
+        MDefinition *def = PopFromWorklist(worklist);
+        IonSpew(IonSpew_Range, "recomputing range on %d", def->id());
+        SpewRange(def);
+        if (!def->earlyAbortCheck() && def->recomputeRange()) {
+            JS_ASSERT(def->range()->lower() <= def->range()->upper());
+            IonSpew(IonSpew_Range, "Range changed; adding consumers");
+            IonSpew(IonSpew_Range, "New range for %d is: (%d, %d)", def->id(), def->range()->lower(), def->range()->upper());
+            for (MUseDefIterator use(def); use; use++) {
+                if(!AddToWorklist(worklist, use.def()))
+                    return false;
+            }
+        }
+        iters++;
+        if (iters >= numBlocks * 100)
+            return false;
     }
+    // Cleanup (in case we stopped due to MAX_ITERS)
+    for(size_t i = 0; i < worklist.length(); i++)
+        worklist[i]->setNotInWorklist();
 
+
+#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());
+        }
+    }
+#endif
     return true;
 }
--- a/js/src/ion/RangeAnalysis.h
+++ b/js/src/ion/RangeAnalysis.h
@@ -6,99 +6,48 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #ifndef jsion_range_analysis_h__
 #define jsion_range_analysis_h__
 
 #include "wtf/Platform.h"
 #include "MIR.h"
 #include "CompileInfo.h"
-#include "IonAnalysis.h"
 
 namespace js {
 namespace ion {
 
 class MBasicBlock;
 class MIRGraph;
 
-// An upper bound computed on the number of backedges a loop will take.
-// This count only includes backedges taken while running Ion code: for OSR
-// loops, this will exclude iterations that executed in the interpreter or in
-// baseline compiled code.
-struct LoopIterationBound : public TempObject
-{
-    // Loop for which this bound applies.
-    MBasicBlock *header;
-
-    // Test from which this bound was derived. Code in the loop body which this
-    // test dominates (will include the backedge) will execute at most 'bound'
-    // times. Other code in the loop will execute at most '1 + Max(bound, 0)'
-    // times.
-    MTest *test;
-
-    // Symbolic bound computed for the number of backedge executions.
-    LinearSum sum;
-
-    LoopIterationBound(MBasicBlock *header, MTest *test, LinearSum sum)
-      : header(header), test(test), sum(sum)
-    {
-    }
-};
-
-// A symbolic upper or lower bound computed for a term.
-struct SymbolicBound : public TempObject
-{
-    // Any loop iteration bound from which this was derived.
-    //
-    // If non-NULL, then 'sum' is only valid within the loop body, at points
-    // dominated by the loop bound's test (see LoopIterationBound).
-    //
-    // If NULL, then 'sum' is always valid.
-    LoopIterationBound *loop;
-
-    // Computed symbolic bound, see above.
-    LinearSum sum;
-
-    SymbolicBound(LoopIterationBound *loop, LinearSum sum)
-      : loop(loop), sum(sum)
-    {
-    }
-
-    void print(Sprinter &sp) const;
-};
-
 class RangeAnalysis
 {
   protected:
     bool blockDominates(MBasicBlock *b, MBasicBlock *b2);
     void replaceDominatedUsesWith(MDefinition *orig, MDefinition *dom,
                                   MBasicBlock *block);
 
   protected:
     MIRGraph &graph_;
 
   public:
     RangeAnalysis(MIRGraph &graph);
     bool addBetaNobes();
     bool analyze();
     bool removeBetaNobes();
-
-  private:
-    void analyzeLoop(MBasicBlock *header);
-    LoopIterationBound *analyzeLoopIterationCount(MBasicBlock *header,
-                                                  MTest *test, BranchDirection direction);
-    void analyzeLoopPhi(MBasicBlock *header, LoopIterationBound *loopBound, MPhi *phi);
-    bool tryHoistBoundsCheck(MBasicBlock *header, MBoundsCheck *ins);
-    void markBlocksInLoopBody(MBasicBlock *header, MBasicBlock *current);
 };
 
-class Range : public TempObject {
+struct RangeChangeCount;
+class Range {
   private:
-    // Absolute ranges.
-    //
+    // :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:
     // {-infty} U [INT_MIN, INT_MAX] U {infty}.  A bound of +/-
     // infty means that the value may have overflowed in that
     // direction. When computing the range of an integer
     // instruction, the ranges of the operands can be clamped to
     // [INT_MIN, INT_MAX], since if they had overflowed they would
     // no longer be integers. This is important for optimizations
     // and somewhat subtle.
@@ -115,77 +64,72 @@ class Range : public TempObject {
     // To facilitate this trick, we maintain the invariants that:
     // 1) lower_infinite == true implies lower_ == JSVAL_INT_MIN
     // 2) upper_infinite == true implies upper_ == JSVAL_INT_MAX
     int32 lower_;
     bool lower_infinite_;
     int32 upper_;
     bool upper_infinite_;
 
-    // Any symbolic lower or upper bound computed for this term.
-    const SymbolicBound *symbolicLower_;
-    const SymbolicBound *symbolicUpper_;
-
   public:
     Range()
         : lower_(JSVAL_INT_MIN),
           lower_infinite_(true),
           upper_(JSVAL_INT_MAX),
-          upper_infinite_(true),
-          symbolicLower_(NULL),
-          symbolicUpper_(NULL)
+          upper_infinite_(true)
     {}
 
-    Range(int64_t l, int64_t h)
-        : symbolicLower_(NULL),
-          symbolicUpper_(NULL)
-    {
+    Range(int64_t l, int64_t h) {
         setLower(l);
         setUpper(h);
     }
 
     Range(const Range &other)
-        : lower_(other.lower_),
-          lower_infinite_(other.lower_infinite_),
-          upper_(other.upper_),
-          upper_infinite_(other.upper_infinite_),
-          symbolicLower_(NULL),
-          symbolicUpper_(NULL)
+    : lower_(other.lower_),
+      lower_infinite_(other.lower_infinite_),
+      upper_(other.upper_),
+      upper_infinite_(other.upper_infinite_)
     {}
-
-    static Range *Truncate(int64_t l, int64_t h);
+    static Range Truncate(int64_t l, int64_t h) {
+        Range ret(l,h);
+        if (!ret.isFinite()) {
+            ret.makeLowerInfinite();
+            ret.makeUpperInfinite();
+        }
+        return ret;
+    }
 
     static int64_t abs64(int64_t x) {
 #ifdef WTF_OS_WINDOWS
         return _abs64(x);
 #else
         return llabs(x);
 #endif
     }
 
-    void print(Sprinter &sp) const;
+    void printRange(FILE *fp);
     bool update(const Range *other);
     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);
-    static Range * intersect(const Range *lhs, const Range *rhs, bool *emptyRange);
-    static Range * addTruncate(const Range *lhs, const Range *rhs);
-    static Range * subTruncate(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);
+    static Range intersect(const Range *lhs, const Range *rhs, bool *nullRange);
+    static Range addTruncate(const Range *lhs, const Range *rhs);
+    static Range subTruncate(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);
 
     static bool precisionLossMul(const Range *lhs, const Range *rhs);
 
     inline void makeLowerInfinite() {
         lower_infinite_ = true;
         lower_ = JSVAL_INT_MIN;
     }
     inline void makeUpperInfinite() {
@@ -235,29 +179,44 @@ class Range : public TempObject {
             upper_ = (int32)x;
             upper_infinite_ = false;
         }
     }
     void set(int64_t l, int64_t h) {
         setLower(l);
         setUpper(h);
     }
+};
 
-    const SymbolicBound *symbolicLower() const {
-        return symbolicLower_;
-    }
-    const SymbolicBound *symbolicUpper() const {
-        return symbolicUpper_;
+struct RangeChangeCount {
+    Range oldRange;
+    unsigned char lowerCount_ : 4;
+    unsigned char upperCount_ : 4;
+    RangeChangeCount() : oldRange(), lowerCount_(0), upperCount_(0) {};
+    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;
     }
-
-    void setSymbolicLower(SymbolicBound *bound) {
-        symbolicLower_ = bound;
-    }
-    void setSymbolicUpper(SymbolicBound *bound) {
-        symbolicUpper_ = bound;
-    }
+};
+class RangeUpdater {
+    Range r_;
+    bool lowerSet_;
+    bool upperSet_;
+  public:
+    RangeUpdater() : r_(), lowerSet_(false), upperSet_(false) {}
+    void unionWith(const Range *other);
+    void unionWith(RangeChangeCount *other);
+    void updateLower(const Range * other);
+    void updateUpper(const Range * other);
+    Range *getRange() { JS_ASSERT(lowerSet_ && upperSet_); return &r_; }
+    void printRange(FILE *fp) { r_.printRange(fp); }
 };
 
 } // namespace ion
 } // namespace js
 
 #endif // jsion_range_analysis_h__