--- 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__