[INFER] LICM and bounds check hoisting for x.length, bug 649693.
authorBrian Hackett <bhackett1024@gmail.com>
Sat, 16 Apr 2011 06:54:01 -0700
changeset 74950 244446b156b75d135113161e0ec4d0b8bf2d447e
parent 74949 50d7a9b2ecc5b373bf9bc25db6e8d3993b2d0302
child 74951 f01b61fd6f49a216a0a748f25fa5a16f321b9b8d
push id2
push userbsmedberg@mozilla.com
push dateFri, 19 Aug 2011 14:38:13 +0000
bugs649693
milestone6.0a1
[INFER] LICM and bounds check hoisting for x.length, bug 649693.
js/src/jit-test/tests/jaeger/loops/hoist-08.js
js/src/jit-test/tests/jaeger/loops/hoist-09.js
js/src/jsanalyze.cpp
js/src/jsanalyze.h
js/src/jsinfer.h
js/src/jsobjinlines.h
js/src/methodjit/Compiler.cpp
js/src/methodjit/FrameEntry.h
js/src/methodjit/FrameState-inl.h
js/src/methodjit/FrameState.cpp
js/src/methodjit/FrameState.h
js/src/methodjit/LoopState.cpp
js/src/methodjit/LoopState.h
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/jaeger/loops/hoist-08.js
@@ -0,0 +1,7 @@
+
+function foo(x,n) {
+  for (var i = -5; i < n; i++) {
+    x[i] = 10;
+  }
+}
+foo([1,2,3,4,5],5);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/jaeger/loops/hoist-09.js
@@ -0,0 +1,11 @@
+
+function foo(x, y) {
+  for (var i = 0; i < x.length; i++) {
+    x[i];
+    if (i < 20)
+      y[i + 1] = 0;
+  }
+}
+
+var q = Array(1,2,3,4,5);
+foo(q, []);
--- a/js/src/jsanalyze.cpp
+++ b/js/src/jsanalyze.cpp
@@ -715,16 +715,88 @@ Script::analyze(JSContext *cx, JSScript 
         }
     }
 
     JS_ASSERT(!failed());
     JS_ASSERT(forwardJump == 0 && forwardCatch == 0);
 }
 
 /////////////////////////////////////////////////////////////////////
+// Stack Analysis
+/////////////////////////////////////////////////////////////////////
+
+bool
+StackAnalysis::analyze(JSArenaPool &pool, JSScript *script,
+                       uint32 start, uint32 length, Script *analysis)
+{
+    this->script = script;
+    this->start = start;
+    this->length = length;
+
+    poppedArray = ArenaArray<PoppedValue*>(pool, length);
+    if (!poppedArray)
+        return false;
+    PodZero(poppedArray, length);
+
+    PoppedValue *stack = ArenaArray<PoppedValue>(pool, script->nslots - script->nfixed);
+    if (!stack)
+        return false;
+
+    unsigned depth = analysis->getCode(start).stackDepth;
+    for (unsigned i = 0; i < depth; i++)
+        stack[i].reset();
+
+    unsigned offset = start;
+    while (offset < start + length) {
+        jsbytecode *pc = script->code + offset;
+        uint32 successorOffset = offset + GetBytecodeLength(pc);
+
+        Bytecode *code = analysis->maybeCode(pc);
+        if (!code) {
+            offset = successorOffset;
+            continue;
+        }
+
+        for (unsigned i = depth; i < code->stackDepth; i++)
+            stack[i].reset();
+        depth = code->stackDepth;
+
+        if (code->jumpTarget) {
+            for (unsigned i = 0; i < depth; i++)
+                stack[i].reset();
+        }
+
+        unsigned nuses = GetUseCount(script, offset);
+        unsigned ndefs = GetDefCount(script, offset);
+
+        if (nuses) {
+            PoppedValue *popped = ArenaArray<PoppedValue>(pool, nuses);
+            if (!popped)
+                return false;
+            for (unsigned i = 0; i < nuses; i++)
+                popped[i] = stack[depth - 1 - i];
+            poppedArray[offset - start] = popped;
+        }
+
+        for (unsigned i = 0; i < ndefs; i++) {
+            PoppedValue &value = stack[depth - nuses + i];
+            value.offset = offset;
+            value.which = i;
+        }
+
+        depth -= nuses;
+        depth += ndefs;
+
+        offset = successorOffset;
+    }
+
+    return true;
+}
+
+/////////////////////////////////////////////////////////////////////
 // Live Range Analysis
 /////////////////////////////////////////////////////////////////////
 
 LifetimeScript::LifetimeScript()
 {
     PodZero(this);
 }
 
@@ -1120,372 +1192,10 @@ LifetimeScript::extendVariable(JSContext
         return false;
     tail->start = segment->end;
     tail->loopTail = true;
     segment->next = tail;
 
     return true;
 }
 
-/* Whether pc is a loop test operand accessing a variable modified by the loop. */
-bool
-LifetimeScript::loopVariableAccess(LifetimeLoop *loop, jsbytecode *pc)
-{
-    unsigned nargs = script->fun ? script->fun->nargs : 0;
-    switch (JSOp(*pc)) {
-      case JSOP_GETLOCAL:
-      case JSOP_INCLOCAL:
-      case JSOP_DECLOCAL:
-      case JSOP_LOCALINC:
-      case JSOP_LOCALDEC:
-        if (analysis->localEscapes(GET_SLOTNO(pc)))
-            return false;
-        return firstWrite(2 + nargs + GET_SLOTNO(pc), loop) != uint32(-1);
-      case JSOP_GETARG:
-      case JSOP_INCARG:
-      case JSOP_DECARG:
-      case JSOP_ARGINC:
-      case JSOP_ARGDEC:
-        if (analysis->argEscapes(GET_SLOTNO(pc)))
-            return false;
-        return firstWrite(2 + GET_SLOTNO(pc), loop) != uint32(-1);
-      default:
-        return false;
-    }
-}
-
-/*
- * Get any slot/constant accessed by a loop test operand, in terms of its value
- * at the start of the next loop iteration.
- */
-bool
-LifetimeScript::getLoopTestAccess(jsbytecode *pc, uint32 *slotp, int32 *constantp)
-{
-    *slotp = LifetimeLoop::UNASSIGNED;
-    *constantp = 0;
-
-    /*
-     * If the pc is modifying a variable and the value tested is its earlier value
-     * (e.g. 'x++ < n'), we need to account for the modification --- at the start
-     * of the next iteration, the value compared will have been 'x - 1'.
-     * Note that we don't need to worry about other accesses to the variable
-     * in the condition like 'x++ < x', as loop tests where both operands are
-     * modified by the loop are rejected.
-     */
-
-    JSOp op = JSOp(*pc);
-    switch (op) {
-
-      case JSOP_GETLOCAL:
-      case JSOP_INCLOCAL:
-      case JSOP_DECLOCAL:
-      case JSOP_LOCALINC:
-      case JSOP_LOCALDEC: {
-        uint32 local = GET_SLOTNO(pc);
-        if (analysis->localEscapes(local))
-            return false;
-        *slotp = 2 + (script->fun ? script->fun->nargs : 0) + local;  /* :XXX: factor out */
-        if (op == JSOP_LOCALINC)
-            *constantp = -1;
-        else if (op == JSOP_LOCALDEC)
-            *constantp = 1;
-        return true;
-      }
-
-      case JSOP_GETARG:
-      case JSOP_INCARG:
-      case JSOP_DECARG:
-      case JSOP_ARGINC:
-      case JSOP_ARGDEC: {
-        uint32 arg = GET_SLOTNO(pc);
-        if (analysis->argEscapes(GET_SLOTNO(pc)))
-            return false;
-        *slotp = 2 + arg;  /* :XXX: factor out */
-        if (op == JSOP_ARGINC)
-            *constantp = -1;
-        else if (op == JSOP_ARGDEC)
-            *constantp = 1;
-        return true;
-      }
-
-      case JSOP_ZERO:
-        *constantp = 0;
-        return true;
-
-      case JSOP_ONE:
-        *constantp = 1;
-        return true;
-
-      case JSOP_UINT16:
-        *constantp = (int32_t) GET_UINT16(pc);
-        return true;
-
-      case JSOP_UINT24:
-        *constantp = (int32_t) GET_UINT24(pc);
-        return true;
-
-      case JSOP_INT8:
-        *constantp = GET_INT8(pc);
-        return true;
-
-      case JSOP_INT32:
-        /*
-         * Don't allow big constants out of the range of an object's max
-         * nslots, to avoid integer overflow.
-         */
-        *constantp = GET_INT32(pc);
-        if (*constantp >= JSObject::NSLOTS_LIMIT || *constantp <= -JSObject::NSLOTS_LIMIT)
-            return false;
-        return true;
-
-      default:
-        return false;
-    }
-}
-
-void
-LifetimeScript::analyzeLoopTest(LifetimeLoop *loop)
-{
-    /*
-     * Try to pick out loop tests like 'A cmp B', where A and B are locals/args
-     * or constants, and at most one is modified in the body of the loop.
-     * :TODO: bug 618692 once more general loop invariant code motion is in
-     * place, this needs to be more robust. Also, LoopState::checkHoistedBounds
-     * depends on the test not storing anything between the entry and backedge,
-     * and also needs to be more robust.
-     */
-
-    /* Don't handle do-while loops. */
-    if (loop->entry == loop->head)
-        return;
-
-    /* Don't handle loops with branching inside their condition. */
-    if (loop->entry < loop->lastBlock)
-        return;
-
-    /*
-     * Only handle loops with four opcodes between the entry and backedge:
-     * get/inc/dec lhs, get/inc/dec rhs, compare, jump to head
-     */
-    jsbytecode *backedge = script->code + loop->backedge;
-
-    jsbytecode *one = script->code + loop->entry;
-    if (one == backedge)
-        return;
-    jsbytecode *two = one + GetBytecodeLength(one);
-    if (two == backedge)
-        return;
-    jsbytecode *three = two + GetBytecodeLength(two);
-    if (three == backedge)
-        return;
-    if (three + GetBytecodeLength(three) != backedge || JSOp(*backedge) != JSOP_IFNE)
-        return;
-
-    /* Only handle inequalities in the compare condition. */
-    JSOp cmpop = JSOp(*three);
-    switch (cmpop) {
-      case JSOP_GT:
-      case JSOP_GE:
-      case JSOP_LT:
-      case JSOP_LE:
-        break;
-      default:
-        return;
-    }
-
-    /* Reverse the condition if the LHS is not modified by the loop. */
-    if (!loopVariableAccess(loop, one)) {
-        jsbytecode *tmp = one;
-        one = two;
-        two = tmp;
-        cmpop = ReverseCompareOp(cmpop);
-    }
-
-    /* Only handle comparisons where the RHS is not modified by the loop. */
-    if (loopVariableAccess(loop, two))
-        return;
-
-    uint32 lhs;
-    int32 lhsConstant;
-    if (!getLoopTestAccess(one, &lhs, &lhsConstant))
-        return;
-
-    uint32 rhs;
-    int32 rhsConstant;
-    if (!getLoopTestAccess(two, &rhs, &rhsConstant))
-        return;
-
-    if (lhs == LifetimeLoop::UNASSIGNED)
-        return;
-
-    /* Passed all filters, this is a loop test we can capture. */
-
-    loop->testLHS = lhs;
-    loop->testRHS = rhs;
-    loop->testConstant = rhsConstant - lhsConstant;
-
-    switch (cmpop) {
-      case JSOP_GT:
-        loop->testConstant++;  /* x > y ==> x >= y + 1 */
-        /* FALLTHROUGH */
-      case JSOP_GE:
-        loop->testLessEqual = false;
-        break;
-
-      case JSOP_LT:
-        loop->testConstant--;  /* x < y ==> x <= y - 1 */
-      case JSOP_LE:
-        loop->testLessEqual = true;
-        break;
-
-      default:
-        JS_NOT_REACHED("Bad op");
-        return;
-    }
-}
-
-bool
-LifetimeScript::analyzeLoopIncrements(JSContext *cx, LifetimeLoop *loop)
-{
-    /*
-     * Find locals and arguments which are used in exactly one inc/dec operation in every
-     * iteration of the loop (we only match against the last basic block, but could
-     * also handle the first basic block).
-     */
-
-    Vector<LifetimeLoop::Increment> increments(cx);
-
-    unsigned nargs = script->fun ? script->fun->nargs : 0;
-    for (unsigned i = 0; i < nargs; i++) {
-        if (analysis->argEscapes(i))
-            continue;
-
-        uint32 offset = onlyWrite(2 + i, loop);
-        if (offset == uint32(-1) || offset < loop->lastBlock)
-            continue;
-
-        JSOp op = JSOp(script->code[offset]);
-        if (op == JSOP_SETARG)
-            continue;
-
-        LifetimeLoop::Increment inc;
-        inc.slot = 2 + i;  /* :XXX: factor out */
-        inc.offset = offset;
-        if (!increments.append(inc))
-            return false;
-    }
-
-    for (unsigned i = 0; i < script->nfixed; i++) {
-        if (analysis->localEscapes(i))
-            continue;
-
-        uint32 offset = onlyWrite(2 + nargs + i, loop);
-        if (offset == uint32(-1) || offset < loop->lastBlock)
-            continue;
-
-        JSOp op = JSOp(script->code[offset]);
-        if (op == JSOP_SETLOCAL || op == JSOP_SETLOCALPOP)
-            continue;
-
-        LifetimeLoop::Increment inc;
-        inc.slot = 2 + (script->fun ? script->fun->nargs : 0) + i;  /* :XXX: factor out */
-        inc.offset = offset;
-        if (!increments.append(inc))
-            return false;
-    }
-
-    loop->increments = ArenaArray<LifetimeLoop::Increment>(pool, increments.length());
-    if (!loop->increments)
-        return false;
-    loop->nIncrements = increments.length();
-
-    for (unsigned i = 0; i < increments.length(); i++)
-        loop->increments[i] = increments[i];
-
-    return true;
-}
-
-bool
-LifetimeScript::analyzeLoopModset(JSContext *cx, LifetimeLoop *loop)
-{
-    Vector<types::TypeObject *> growArrays(cx);
-
-    /*
-     * To figure out modsets, we need to know the type sets on the stack at
-     * each point. These were generated when running inference on the script,
-     * but are no longer retained and we need to reconstruct them here.
-     */
-
-    types::TypeSet **stack = ArenaArray<types::TypeSet*>(pool, script->nslots);
-    if (!stack)
-        return false;
-
-    unsigned offset = loop->head;
-    unsigned stackDepth = 0;
-
-    while (offset < loop->backedge) {
-        jsbytecode *pc = script->code + offset;
-        unsigned successorOffset = offset + GetBytecodeLength(pc);
-
-        analyze::Bytecode *opinfo = analysis->maybeCode(offset);
-        if (!opinfo) {
-            offset = successorOffset;
-            continue;
-        }
-
-        if (opinfo->stackDepth > stackDepth) {
-            unsigned ndefs = opinfo->stackDepth - stackDepth;
-            memset(&stack[stackDepth], 0, ndefs * sizeof(types::TypeSet*));
-        }
-        stackDepth = opinfo->stackDepth;
-
-        switch (JSOp(*pc)) {
-
-          case JSOP_SETHOLE: {
-            types::TypeSet *types = stack[opinfo->stackDepth - 3];
-            if (types && !types->unknown()) {
-                unsigned count = types->getObjectCount();
-                for (unsigned i = 0; i < count; i++) {
-                    types::TypeObject *object = types->getObject(i);
-                    if (object) {
-                        bool found = false;
-                        for (unsigned i = 0; !found && i < growArrays.length(); i++) {
-                            if (growArrays[i] == object)
-                                found = true;
-                        }
-                        if (!found && !growArrays.append(object))
-                            return false;
-                    }
-                }
-            } else {
-                loop->unknownModset = true;
-            }
-            break;
-          }
-
-          default:
-            break;
-        }
-
-        unsigned nuses = analyze::GetUseCount(script, offset);
-        unsigned ndefs = analyze::GetDefCount(script, offset);
-        memset(&stack[stackDepth - nuses], 0, ndefs * sizeof(types::TypeSet*));
-        stackDepth = stackDepth - nuses + ndefs;
-
-        for (unsigned i = 0; i < ndefs; i++)
-            stack[stackDepth - ndefs + i] = script->types->pushed(offset, i);
-
-        offset = successorOffset;
-    }
-
-    loop->growArrays = ArenaArray<types::TypeObject*>(pool, growArrays.length());
-    if (!loop->growArrays)
-        return false;
-    loop->nGrowArrays = growArrays.length();
-
-    for (unsigned i = 0; i < growArrays.length(); i++)
-        loop->growArrays[i] = growArrays[i];
-
-    return true;
-}
-
 } /* namespace analyze */
 } /* namespace js */
--- a/js/src/jsanalyze.h
+++ b/js/src/jsanalyze.h
@@ -322,16 +322,48 @@ struct UntrapOpcode
     ~UntrapOpcode()
     {
         if (trap)
             *pc = JSOP_TRAP;
     }
 };
 
 /*
+ * Analysis over a range of bytecode to determine where each popped value was
+ * originally pushed.
+ */
+struct StackAnalysis
+{
+    /* For values whose pushed location is not known. */
+    static const uint32 UNKNOWN_PUSHED = uint32(-1);
+
+    struct PoppedValue {
+        uint32 offset;
+        uint32 which;
+        void reset() { offset = UNKNOWN_PUSHED; which = 0; }
+    };
+
+    PoppedValue **poppedArray;
+    uint32 start;
+    uint32 length;
+
+    JSScript *script;
+
+    bool analyze(JSArenaPool &pool, JSScript *script, uint32 start, uint32 length,
+                 Script *analysis);
+
+    const PoppedValue &popped(uint32 offset, uint32 which) {
+        return poppedArray[offset - start][which];
+    }
+    const PoppedValue &popped(jsbytecode *pc, uint32 which) {
+        return popped(pc - script->code, which);
+    }
+};
+
+/*
  * Lifetime analysis. The goal of this analysis is to make a single backwards pass
  * over a script to approximate the regions where each variable is live, without
  * doing a full fixpointing live-variables pass. This is based on the algorithm
  * described in:
  *
  * "Quality and Speed in Linear-scan Register Allocation"
  * Traub et. al.
  * PLDI, 1998
@@ -396,58 +428,23 @@ struct LifetimeLoop
      * Start of the last basic block in the loop, excluding the initial jump to
      * entry. All code between lastBlock and the backedge runs in every
      * iteration, and if entry >= lastBlock all code between entry and the
      * backedge runs when the loop is initially entered.
      */
     uint32 lastBlock;
 
     /*
-     * Any inequality known to hold at the head of the loop. This has the
-     * form 'lhs <= rhs + constant' or 'lhs >= rhs + constant', depending on
-     * lessEqual. The lhs may be modified within the loop body (the test is
-     * invalid afterwards), and the rhs is invariant. This information is only
-     * valid if the LHS/RHS are known integers.
-     */
-    enum { UNASSIGNED = uint32(-1) };
-    uint32 testLHS;
-    uint32 testRHS;
-    int32 testConstant;
-    bool testLessEqual;
-
-    /*
-     * A variable which will be incremented or decremented exactly once in each
-     * iteration of the loop. The offset of the operation is indicated, which
-     * may or may not run after the initial entry into the loop.
-     */
-    struct Increment {
-        uint32 slot;
-        uint32 offset;
-    };
-    Increment *increments;
-    uint32 nIncrements;
-
-    /* It is unknown which arrays grow or which objects are modified in this loop. */
-    bool unknownModset;
-
-    /*
      * This loop contains safe points in its body which the interpreter might
      * join at directly.
      */
     bool hasSafePoints;
 
     /* This loop has calls or inner loops. */
     bool hasCallsLoops;
-
-    /*
-     * Arrays which might grow during this loop. This is a guess, and may
-     * underapproximate the actual set of such arrays.
-     */
-    types::TypeObject **growArrays;
-    uint32 nGrowArrays;
 };
 
 /* Lifetime and register information for a bytecode. */
 struct LifetimeBytecode
 {
     /* If this is a loop head, information about the loop. */
     LifetimeLoop *loop;
 
@@ -585,30 +582,19 @@ class LifetimeScript
         return lifetimes[slot].nonDecreasing(script, loop);
     }
 
     uint32 onlyWrite(uint32 slot, LifetimeLoop *loop) {
         JS_ASSERT(slot < nLifetimes);
         return lifetimes[slot].onlyWrite(loop);
     }
 
-    /*
-     * Note: loop analysis depends on the function not having had indirect
-     * modification of its arguments. Clients must watch for this.
-     */
-    void analyzeLoopTest(LifetimeLoop *loop);
-    bool analyzeLoopIncrements(JSContext *cx, LifetimeLoop *loop);
-    bool analyzeLoopModset(JSContext *cx, LifetimeLoop *loop);
-
   private:
 
     inline bool addVariable(JSContext *cx, LifetimeVariable &var, unsigned offset);
     inline bool killVariable(JSContext *cx, LifetimeVariable &var, unsigned offset);
     inline bool extendVariable(JSContext *cx, LifetimeVariable &var, unsigned start, unsigned end);
-
-    bool loopVariableAccess(LifetimeLoop *loop, jsbytecode *pc);
-    bool getLoopTestAccess(jsbytecode *pc, uint32 *slotp, int32 *constantp);
 };
 
 } /* namespace analyze */
 } /* namespace js */
 
 #endif // jsanalyze_h___
--- a/js/src/jsinfer.h
+++ b/js/src/jsinfer.h
@@ -455,17 +455,20 @@ enum {
      * Whether all the properties of this object are unknown. When this object
      * appears in a type set, nothing can be assumed about its contents,
      * including whether the .proto field is correct. This is needed to handle
      * mutable __proto__, which requires us to unify all type objects with
      * unknown properties in type sets (see SetProto).
      */
     OBJECT_FLAG_UNKNOWN_MASK = uint32(-1),
 
-    /* Whether any objects this represents are not dense arrays. */
+    /*
+     * Whether any objects this represents are not dense arrays. This also
+     * includes dense arrays whose length property does not fit in an int32.
+     */
     OBJECT_FLAG_NON_DENSE_ARRAY = 1 << 0,
 
     /* Whether any objects this represents are not packed arrays. */
     OBJECT_FLAG_NON_PACKED_ARRAY = 1 << 1,
 
     /* Whether any objects this represents have had their .arguments accessed. */
     OBJECT_FLAG_UNINLINEABLE = 1 << 2,
 
--- a/js/src/jsobjinlines.h
+++ b/js/src/jsobjinlines.h
@@ -423,20 +423,26 @@ JSObject::getArrayLength() const
     return (uint32)(size_t) getPrivate();
 }
 
 inline bool
 JSObject::setArrayLength(JSContext *cx, uint32 length)
 {
     JS_ASSERT(isArray());
 
-    if (length > INT32_MAX &&
-        !cx->addTypePropertyId(getType(), ATOM_TO_JSID(cx->runtime->atomState.lengthAtom),
-                               js::types::TYPE_DOUBLE)) {
-        return false;
+    if (length > INT32_MAX) {
+        /*
+         * Mark the type of this object as possibly not a dense array, per the
+         * requirements of OBJECT_FLAG_NON_DENSE_ARRAY.
+         */
+        if (!cx->markTypeArrayNotPacked(getType(), true))
+            return false;
+        jsid lengthId = ATOM_TO_JSID(cx->runtime->atomState.lengthAtom);
+        if (!cx->addTypePropertyId(getType(), lengthId, js::types::TYPE_DOUBLE))
+            return false;
     }
 
     setPrivate((void*) length);
     return true;
 }
 
 inline void
 JSObject::setDenseArrayLength(uint32 length)
--- a/js/src/methodjit/Compiler.cpp
+++ b/js/src/methodjit/Compiler.cpp
@@ -4354,23 +4354,36 @@ mjit::Compiler::jsop_length()
             masm.urshift32(Imm32(JSString::LENGTH_SHIFT), str);
             frame.pop();
             frame.pushTypedPayload(JSVAL_TYPE_INT32, str);
         }
         return true;
     }
 
     /*
-     * Check if we are accessing the 'length' property of a known dense array
-     * which must fit in an int32.
+     * Check if this is an array we can make a loop invariant entry for.
+     * This will fail for objects which are not definitely dense arrays.
+     */
+    if (loop && loop->generatingInvariants()) {
+        FrameEntry *fe = loop->invariantLength(top);
+        if (fe) {
+            frame.pop();
+            frame.pushTemporary(fe);
+            return true;
+        }
+    }
+
+    /*
+     * Check if we are accessing the 'length' property of a known dense array.
+     * Note that if the types are known to indicate dense arrays, their lengths
+     * must fit in an int32.
      */
     types::TypeSet *types = frame.extra(top).types;
     types::ObjectKind kind = types ? types->getKnownObjectKind(cx) : types::OBJECT_UNKNOWN;
-    if ((kind == types::OBJECT_DENSE_ARRAY || kind == types::OBJECT_PACKED_ARRAY) &&
-        knownPushedType(0) == JSVAL_TYPE_INT32) {
+    if ((kind == types::OBJECT_DENSE_ARRAY || kind == types::OBJECT_PACKED_ARRAY)) {
         bool isObject = top->isTypeKnown();
         if (!isObject) {
             Jump notObject = frame.testObject(Assembler::NotEqual, top);
             stubcc.linkExit(notObject, Uses(1));
             stubcc.leave();
             OOL_STUBCALL(stubs::Length);
         }
         RegisterID reg = frame.tempRegForData(top);
@@ -5407,17 +5420,17 @@ mjit::Compiler::jsop_this()
                 stubcc.linkExit(notObj, Uses(1));
                 stubcc.leave();
                 OOL_STUBCALL(stubs::This);
                 stubcc.rejoin(Changes(1));
             }
 
             // Now we know that |this| is an object.
             frame.pop();
-            frame.learnThisIsObject();
+            frame.learnThisIsObject(type != JSVAL_TYPE_OBJECT);
             frame.pushThis();
         }
 
         JS_ASSERT(thisFe->isType(JSVAL_TYPE_OBJECT));
     }
 }
 
 bool
@@ -6578,38 +6591,43 @@ mjit::Compiler::finishLoop(jsbytecode *h
         RegisterAllocation *alloc = a->liveness.getCode(head).allocation;
         JaegerSpew(JSpew_Regalloc, "loop allocation at %u:", head - script->code);
         frame.dumpAllocation(alloc);
     }
 #endif
 
     loop->entryJump().linkTo(masm.label(), &masm);
 
+    jsbytecode *oldPC = PC;
+
+    PC = entryTarget;
     {
         REJOIN_SITE(stubs::MissedBoundsCheckEntry);
         OOL_STUBCALL(stubs::MissedBoundsCheckEntry);
 
         if (loop->generatingInvariants()) {
             /*
              * To do the initial load of the invariants, jump to the invariant
              * restore point after the call just emitted. :XXX: fix hackiness.
              */
             if (oomInVector)
                 return false;
             Label label = callSites[callSites.length() - 1].loopJumpLabel;
             stubcc.linkExitDirect(masm.jump(), label);
         }
         stubcc.crossJump(stubcc.masm.jump(), masm.label());
     }
+    PC = oldPC;
 
     frame.prepareForJump(entryTarget, masm, true);
 
     if (!jumpInScript(masm.jump(), entryTarget))
         return false;
 
+    PC = head;
     if (!a->analysis.getCode(head).safePoint) {
         /*
          * Emit a stub into the OOL path which loads registers from a synced state
          * and jumps to the loop head, for rejoining from the interpreter.
          */
         LoopEntry entry;
         entry.pcOffset = head - script->code;
 
@@ -6626,16 +6644,17 @@ mjit::Compiler::finishLoop(jsbytecode *h
 
         autoRejoinHead.oolRejoin(stubcc.masm.label());
         frame.prepareForJump(head, stubcc.masm, true);
         if (!stubcc.jumpInScript(stubcc.masm.jump(), head))
             return false;
 
         loopEntries.append(entry);
     }
+    PC = oldPC;
 
     /* Write out loads and tests of loop invariants at all calls in the loop body. */
     loop->flushLoop(stubcc);
 
     LoopState *nloop = loop->outer;
     cx->delete_(loop);
     loop = nloop;
     frame.setLoop(loop);
--- a/js/src/methodjit/FrameEntry.h
+++ b/js/src/methodjit/FrameEntry.h
@@ -55,17 +55,17 @@ class FrameEntry
     friend class FrameState;
     friend class ImmutableSync;
 
   public:
 
     /* Accessors for entries which are known constants. */
 
     bool isConstant() const {
-        if (isCopy() || isInvariant())
+        if (isCopy())
             return false;
         return data.isConstant();
     }
 
     const jsval_layout &getConstant() const {
         JS_ASSERT(isConstant());
         return v_;
     }
@@ -151,32 +151,19 @@ class FrameEntry
     const FrameEntry *backing() const {
         return isCopy() ? copyOf() : this;
     }
 
     bool hasSameBacking(const FrameEntry *other) const {
         return backing() == other->backing();
     }
 
-    /*
-     * Accessors for entries which are copies of analysis temporaries. All
-     * temporaries are invariant, so these behave more like constants than like
-     * copies of mutable entries.
-     */
-
-    bool isInvariant() const { return !!invariant_; }
-
-    FrameEntry *invariant() {
-        JS_ASSERT(isInvariant());
-        return invariant_;
-    }
-
   private:
     void setType(JSValueType type_) {
-        JS_ASSERT(!isCopy() && !isInvariant());
+        JS_ASSERT(!isCopy());
         type.setConstant();
 #if defined JS_NUNBOX32
         v_.s.tag = JSVAL_TYPE_TO_TAG(type_);
 #elif defined JS_PUNBOX64
         v_.asBits &= JSVAL_PAYLOAD_MASK;
         v_.asBits |= JSVAL_TYPE_TO_SHIFTED_TAG(type_);
 #endif
         knownType = type_;
@@ -186,17 +173,16 @@ class FrameEntry
         clear();
         index_ = index;
         tracked = true;
     }
 
     void clear() {
         copied = false;
         copy = NULL;
-        invariant_ = NULL;
     }
 
     uint32 trackerIndex() {
         return index_;
     }
 
     /*
      * Marks the FE as unsynced & invalid.
@@ -237,76 +223,71 @@ class FrameEntry
 
     void setCopied() {
         JS_ASSERT(!isCopy());
         copied = true;
     }
 
     FrameEntry *copyOf() const {
         JS_ASSERT(isCopy());
-        JS_ASSERT(copy < this);
+        JS_ASSERT_IF(!copy->temporary, copy < this);
         return copy;
     }
 
     void setNotCopied() {
         copied = false;
     }
 
     /*
      * Set copy index.
      */
     void setCopyOf(FrameEntry *fe) {
         JS_ASSERT(!isCopied());
         copy = fe;
-        invariant_ = NULL;
         if (fe) {
             type.invalidate();
             data.invalidate();
         }
     }
 
-    void setInvariant(FrameEntry *fe) {
-        JS_ASSERT(!isCopied());
-        copy = NULL;
-        invariant_ = fe;
-        type.invalidate();
-        data.invalidate();
-    }
-
     inline bool isTracked() const {
         return tracked;
     }
 
     inline void untrack() {
         tracked = false;
     }
 
     inline bool dataInRegister(AnyRegisterID reg) const {
-        JS_ASSERT(!copy && !invariant_);
+        JS_ASSERT(!copy);
         return reg.isReg()
             ? (data.inRegister() && data.reg() == reg.reg())
             : (data.inFPRegister() && data.fpreg() == reg.fpreg());
     }
 
   private:
     JSValueType knownType;
     jsval_layout v_;
     RematInfo  type;
     RematInfo  data;
     uint32     index_;
-    FrameEntry *invariant_;
     FrameEntry *copy;
     bool       copied;
     bool       tracked;
     bool       inlined;
+    bool       temporary;
 
     /*
      * Offset of the last loop in which this entry was written or had a loop
      * register assigned.
      */
     uint32     lastLoop;
+
+#if JS_BITS_PER_WORD == 32
+    void *padding;
+#endif
 };
 
 } /* namespace mjit */
 } /* namespace js */
 
 #endif /* jsjaeger_valueinfo_h__ */
 
--- a/js/src/methodjit/FrameState-inl.h
+++ b/js/src/methodjit/FrameState-inl.h
@@ -613,23 +613,23 @@ FrameState::tempRegForData(FrameEntry *f
         masm.loadPayload(addressOf(fe), reg);
         return reg;
     }
 }
 
 inline bool
 FrameState::shouldAvoidTypeRemat(FrameEntry *fe)
 {
-    return !fe->isCopy() && !fe->isInvariant() && fe->type.inMemory();
+    return !fe->isCopy() && fe->type.inMemory();
 }
 
 inline bool
 FrameState::shouldAvoidDataRemat(FrameEntry *fe)
 {
-    return !fe->isCopy() && !fe->isInvariant() && fe->data.inMemory();
+    return !fe->isCopy() && fe->data.inMemory();
 }
 
 inline void
 FrameState::ensureFeSynced(const FrameEntry *fe, Assembler &masm) const
 {
     Address to = addressOf(fe);
     const FrameEntry *backing = fe;
     if (fe->isCopy())
@@ -1111,17 +1111,17 @@ FrameState::unpinKilledReg(RegisterID re
 {
     regstate(reg).unpinUnsafe();
     a->freeRegs.putReg(reg);
 }
 
 inline void
 FrameState::forgetAllRegs(FrameEntry *fe)
 {
-    if (fe->isCopy() || fe->isInvariant())
+    if (fe->isCopy())
         return;
     if (fe->type.inRegister())
         forgetReg(fe->type.reg());
     if (fe->data.inRegister())
         forgetReg(fe->data.reg());
     if (fe->data.inFPRegister())
         forgetReg(fe->data.fpreg());
 }
@@ -1218,23 +1218,30 @@ FrameState::pushCallee()
 
 inline void
 FrameState::pushThis()
 {
     FrameEntry *fe = getThis();
     pushCopyOf(indexOfFe(fe));
 }
 
+inline void
+FrameState::pushTemporary(FrameEntry *fe)
+{
+    JS_ASSERT(isTemporary(fe));
+    pushCopyOf(indexOfFe(fe));
+}
+
 void
-FrameState::learnThisIsObject()
+FrameState::learnThisIsObject(bool unsync)
 {
     // This is safe, albeit hacky. This is only called from the compiler,
     // and only on the first use of |this| inside a basic block. Thus,
     // there are no copies of |this| anywhere.
-    learnType(this_, JSVAL_TYPE_OBJECT);
+    learnType(this_, JSVAL_TYPE_OBJECT, unsync);
 }
 
 inline void
 FrameState::leaveBlock(uint32 n)
 {
     popn(n);
 }
 
@@ -1302,18 +1309,17 @@ FrameState::loadDouble(RegisterID t, Reg
     loadDouble(fe, fpreg, masm);
 #endif
 }
 
 inline bool
 FrameState::tryFastDoubleLoad(FrameEntry *fe, FPRegisterID fpReg, Assembler &masm) const
 {
 #ifdef JS_CPU_X86
-    if (!fe->isCopy() && !fe->isInvariant() &&
-        fe->type.inRegister() && fe->data.inRegister()) {
+    if (!fe->isCopy() && fe->type.inRegister() && fe->data.inRegister()) {
         masm.fastLoadDouble(fe->data.reg(), fe->type.reg(), fpReg);
         return true;
     }
 #endif
     return false;
 }
 
 inline void
--- a/js/src/methodjit/FrameState.cpp
+++ b/js/src/methodjit/FrameState.cpp
@@ -1328,26 +1328,23 @@ FrameState::assertValidRegisterState() c
     for (uint32 i = 0; i < a->tracker.nentries; i++) {
         FrameEntry *fe = a->tracker[i];
         if (deadEntry(fe))
             continue;
 
         JS_ASSERT(i == fe->trackerIndex());
 
         if (fe->isCopy()) {
+            JS_ASSERT_IF(!fe->copyOf()->temporary, fe > fe->copyOf());
             JS_ASSERT(fe->trackerIndex() > fe->copyOf()->trackerIndex());
-            JS_ASSERT(fe > fe->copyOf());
             JS_ASSERT(!deadEntry(fe->copyOf()));
             JS_ASSERT(fe->copyOf()->isCopied());
             continue;
         }
 
-        if (fe->isInvariant())
-            continue;
-
         if (fe->type.inRegister()) {
             checkedFreeRegs.takeReg(fe->type.reg());
             JS_ASSERT(regstate(fe->type.reg()).fe() == fe);
         }
         if (fe->data.inRegister()) {
             checkedFreeRegs.takeReg(fe->data.reg());
             JS_ASSERT(regstate(fe->data.reg()).fe() == fe);
         }
@@ -1531,17 +1528,17 @@ FrameState::sync(Assembler &masm, Uses u
             if ((!fe->type.synced() && backing->type.inMemory()) ||
                 (!fe->data.synced() && backing->data.inMemory())) {
                 syncFancy(masm, avail, fe, bottom);
                 return;
             }
 #endif
         }
 
-        bool copy = fe->isCopy() || fe->isInvariant();
+        bool copy = fe->isCopy();
 
         /* If a part still needs syncing, it is either a copy or constant. */
 #if defined JS_PUNBOX64
         /* All register-backed FEs have been entirely synced up-front. */
         if (copy || (!fe->type.inRegister() && !fe->data.inRegister()))
             ensureFeSynced(fe, masm);
 #elif defined JS_NUNBOX32
         /* All components held in registers have been already synced. */
@@ -1621,17 +1618,17 @@ FrameState::syncAndKill(Registers kill, 
 
         maxvisits--;
 
         if (deadEntry(fe, ignore.nuses))
             continue;
 
         syncFe(fe);
 
-        if (fe->isCopy() || fe->isInvariant())
+        if (fe->isCopy())
             continue;
 
         /* Forget registers. */
         if (fe->data.inRegister() && !regstate(fe->data.reg()).isPinned()) {
             forgetReg(fe->data.reg());
             fe->data.setMemory();
         }
         if (fe->data.inFPRegister() && !regstate(fe->data.fpreg()).isPinned()) {
@@ -2066,35 +2063,32 @@ FrameState::ensureDouble(FrameEntry *fe)
 
 void
 FrameState::ensureInMemoryDoubles(Assembler &masm)
 {
     JS_ASSERT(!a->parent);
     for (uint32 i = 0; i < a->tracker.nentries; i++) {
         FrameEntry *fe = a->tracker[i];
         if (!deadEntry(fe) && fe->isType(JSVAL_TYPE_DOUBLE) &&
-            !fe->isCopy() && !fe->isInvariant() && !fe->isConstant()) {
+            !fe->isCopy() && !fe->isConstant()) {
             masm.ensureInMemoryDouble(addressOf(fe));
         }
     }
 }
 
 void
 FrameState::pushCopyOf(uint32 index)
 {
     FrameEntry *backing = entryFor(index);
     FrameEntry *fe = rawPush();
     fe->resetUnsynced();
     if (backing->isConstant()) {
         fe->setConstant(Jsvalify(backing->getValue()));
     } else {
-        if (backing->isTypeKnown())
-            fe->setType(backing->getKnownType());
-        else
-            fe->type.invalidate();
+        fe->type.invalidate();
         fe->data.invalidate();
         if (backing->isCopy()) {
             backing = backing->copyOf();
             fe->setCopyOf(backing);
         } else {
             fe->setCopyOf(backing);
             backing->setCopied();
         }
@@ -2104,16 +2098,19 @@ FrameState::pushCopyOf(uint32 index)
         if (fe->trackerIndex() < backing->trackerIndex())
             swapInTracker(fe, backing);
     }
 }
 
 FrameEntry *
 FrameState::walkTrackerForUncopy(FrameEntry *original)
 {
+    /* Temporary entries are immutable and should never be uncopied. */
+    JS_ASSERT(!isTemporary(original));
+
     uint32 firstCopy = InvalidIndex;
     FrameEntry *bestFe = NULL;
     uint32 ncopies = 0;
     for (uint32 i = original->trackerIndex() + 1; i < a->tracker.nentries; i++) {
         FrameEntry *fe = a->tracker[i];
         if (deadEntry(fe))
             continue;
         if (fe->isCopy() && fe->copyOf() == original) {
@@ -2377,16 +2374,18 @@ FrameState::forgetEntry(FrameEntry *fe)
 
     if (fe >= spBase && fe < sp)
         a->extraArray[fe - spBase].reset();
 }
 
 void
 FrameState::storeTop(FrameEntry *target, JSValueType type, bool popGuaranteed)
 {
+    JS_ASSERT(!isTemporary(target));
+
     /* Detect something like (x = x) which is a no-op. */
     FrameEntry *top = peek(-1);
     if (top->isCopy() && top->copyOf() == target) {
         JS_ASSERT(target->isCopied());
         return;
     }
 
     /* Completely invalidate the local variable. */
@@ -3040,16 +3039,17 @@ FrameState::maybeUnpinReg(MaybeRegisterI
 
 uint32
 FrameState::allocTemporary()
 {
     if (temporariesTop == temporaries + TEMPORARY_LIMIT)
         return uint32(-1);
     FrameEntry *fe = temporariesTop++;
     fe->lastLoop = 0;
+    fe->temporary = true;
     return fe - temporaries;
 }
 
 void
 FrameState::clearTemporaries()
 {
     for (FrameEntry *fe = temporaries; fe < temporariesTop; fe++) {
         if (!fe->isTracked())
--- a/js/src/methodjit/FrameState.h
+++ b/js/src/methodjit/FrameState.h
@@ -361,22 +361,25 @@ class FrameState
     inline void leaveBlock(uint32 n);
 
     // Pushes a copy of a slot (formal argument, local variable, or stack slot)
     // onto the operation stack.
     void pushLocal(uint32 n, JSValueType knownType);
     void pushArg(uint32 n, JSValueType knownType);
     void pushCallee();
     void pushThis();
-    inline void learnThisIsObject();
+    void pushTemporary(FrameEntry *fe);
+    inline void learnThisIsObject(bool unsync = true);
 
     inline FrameEntry *getStack(uint32 slot);
     inline FrameEntry *getLocal(uint32 slot);
     inline FrameEntry *getArg(uint32 slot);
 
+    inline FrameEntry *getOrTrack(uint32 index);
+
     /*
      * Allocates a temporary register for a FrameEntry's type. The register
      * can be spilled or clobbered by the frame. The compiler may only operate
      * on it temporarily, and must take care not to clobber it.
      */
     inline RegisterID tempRegForType(FrameEntry *fe);
 
     /*
@@ -910,17 +913,16 @@ class FrameState
     inline void ensureDataSynced(const FrameEntry *fe, Assembler &masm) const;
 
     /* Guarantee sync, even if register allocation is required, and set sync. */
     inline void syncFe(FrameEntry *fe);
     inline void syncType(FrameEntry *fe);
     inline void syncData(FrameEntry *fe);
     inline void syncAndForgetFe(FrameEntry *fe);
 
-    inline FrameEntry *getOrTrack(uint32 index);
     inline FrameEntry *getCallee();
     inline FrameEntry *getThis();
     inline void forgetAllRegs(FrameEntry *fe);
     inline void swapInTracker(FrameEntry *lhs, FrameEntry *rhs);
     void pushCopyOf(uint32 index);
 #if defined JS_NUNBOX32
     void syncFancy(Assembler &masm, Registers avail, FrameEntry *resumeAt,
                    FrameEntry *bottom) const;
--- a/js/src/methodjit/LoopState.cpp
+++ b/js/src/methodjit/LoopState.cpp
@@ -48,58 +48,70 @@ using namespace js::analyze;
 LoopState::LoopState(JSContext *cx, JSScript *script,
                      mjit::Compiler *cc, FrameState *frame,
                      Script *analysis, LifetimeScript *liveness)
     : cx(cx), script(script), cc(*cc), frame(*frame), analysis(analysis), liveness(liveness),
       lifetime(NULL), alloc(NULL), loopRegs(0), skipAnalysis(false),
       loopJoins(CompilerAllocPolicy(cx, *cc)),
       loopPatches(CompilerAllocPolicy(cx, *cc)),
       restoreInvariantCalls(CompilerAllocPolicy(cx, *cc)),
-      hoistedBoundsChecks(CompilerAllocPolicy(cx, *cc)),
-      invariantArraySlots(CompilerAllocPolicy(cx, *cc)),
-      outer(NULL), PC(NULL)
+      invariantEntries(CompilerAllocPolicy(cx, *cc)),
+      outer(NULL), PC(NULL),
+      testLHS(UNASSIGNED), testRHS(UNASSIGNED),
+      testConstant(0), testLessEqual(false), testLength(false),
+      increments(CompilerAllocPolicy(cx, *cc)), unknownModset(false),
+      growArrays(CompilerAllocPolicy(cx, *cc)),
+      modifiedProperties(CompilerAllocPolicy(cx, *cc))
 {
     JS_ASSERT(cx->typeInferenceEnabled());
 }
 
 bool
 LoopState::init(jsbytecode *head, Jump entry, jsbytecode *entryTarget)
 {
     this->lifetime = liveness->getCode(head).loop;
     JS_ASSERT(lifetime &&
               lifetime->head == uint32(head - script->code) &&
               lifetime->entry == uint32(entryTarget - script->code));
 
     this->entry = entry;
 
-    liveness->analyzeLoopTest(lifetime);
-    if (!liveness->analyzeLoopIncrements(cx, lifetime))
-        return false;
-    if (!liveness->analyzeLoopModset(cx, lifetime))
+    if (!stack.analyze(liveness->pool, script, lifetime->head,
+                       lifetime->backedge - lifetime->head + 1, analysis)) {
         return false;
-
-    if (lifetime->testLHS != LifetimeLoop::UNASSIGNED) {
-        JaegerSpew(JSpew_Analysis, "loop test at %u: %s %s %s + %d\n", lifetime->head,
-                   frame.entryName(lifetime->testLHS),
-                   lifetime->testLessEqual ? "<=" : ">=",
-                   (lifetime->testRHS == LifetimeLoop::UNASSIGNED)
-                       ? ""
-                       : frame.entryName(lifetime->testRHS),
-                   lifetime->testConstant);
     }
 
-    for (unsigned i = 0; i < lifetime->nIncrements; i++) {
-        JaegerSpew(JSpew_Analysis, "loop increment at %u for %s: %u\n", lifetime->head,
-                   frame.entryName(lifetime->increments[i].slot),
-                   lifetime->increments[i].offset);
+    analyzeLoopTest();
+    analyzeLoopIncrements();
+    analyzeModset();
+
+    if (testLHS != UNASSIGNED) {
+        JaegerSpew(JSpew_Analysis, "loop test at %u: %s %s%s %s + %d\n", lifetime->head,
+                   frame.entryName(testLHS),
+                   testLessEqual ? "<=" : ">=",
+                   testLength ? " length" : "",
+                   (testRHS == UNASSIGNED) ? "" : frame.entryName(testRHS),
+                   testConstant);
     }
 
-    for (unsigned i = 0; i < lifetime->nGrowArrays; i++) {
+    for (unsigned i = 0; i < increments.length(); i++) {
+        JaegerSpew(JSpew_Analysis, "loop increment at %u for %s: %u\n", lifetime->head,
+                   frame.entryName(increments[i].slot),
+                   increments[i].offset);
+    }
+
+    for (unsigned i = 0; i < growArrays.length(); i++) {
         JaegerSpew(JSpew_Analysis, "loop grow array at %u: %s\n", lifetime->head,
-                   lifetime->growArrays[i]->name());
+                   growArrays[i]->name());
+    }
+
+    for (unsigned i = 0; i < modifiedProperties.length(); i++) {
+        JaegerSpew(JSpew_Analysis, "loop modified property at %u: %s %s\n", lifetime->head,
+                   modifiedProperties[i].object->name(),
+                   types::TypeIdString(modifiedProperties[i].id));
     }
 
     RegisterAllocation *&alloc = liveness->getCode(head).allocation;
     JS_ASSERT(!alloc);
 
     alloc = ArenaNew<RegisterAllocation>(liveness->pool, true);
     if (!alloc)
         return false;
@@ -254,61 +266,92 @@ LoopState::loopInvariantEntry(const Fram
 
 bool
 LoopState::addHoistedCheck(uint32 arraySlot, uint32 valueSlot, int32 constant)
 {
     /*
      * Check to see if this bounds check either implies or is implied by an
      * existing hoisted check.
      */
-    for (unsigned i = 0; i < hoistedBoundsChecks.length(); i++) {
-        HoistedBoundsCheck &check = hoistedBoundsChecks[i];
-        if (check.arraySlot == arraySlot && check.valueSlot == valueSlot) {
-            if (check.constant < constant)
-                check.constant = constant;
+    for (unsigned i = 0; i < invariantEntries.length(); i++) {
+        InvariantEntry &entry = invariantEntries[i];
+        if (entry.kind == InvariantEntry::BOUNDS_CHECK &&
+            entry.u.check.arraySlot == arraySlot &&
+            entry.u.check.valueSlot == valueSlot) {
+            if (entry.u.check.constant < constant)
+                entry.u.check.constant = constant;
             return true;
         }
     }
 
     /*
      * Maintain an invariant that for any array with a hoisted bounds check,
      * we also have a loop invariant slot to hold the array's slots pointer.
      * The compiler gets invariant array slots only for accesses with a hoisted
      * bounds check, so this makes invariantSlots infallible.
      */
     bool hasInvariantSlots = false;
-    for (unsigned i = 0; !hasInvariantSlots && i < invariantArraySlots.length(); i++) {
-        if (invariantArraySlots[i].arraySlot == arraySlot)
+    for (unsigned i = 0; !hasInvariantSlots && i < invariantEntries.length(); i++) {
+        InvariantEntry &entry = invariantEntries[i];
+        if (entry.kind == InvariantEntry::INVARIANT_SLOTS &&
+            entry.u.array.arraySlot == arraySlot) {
             hasInvariantSlots = true;
+        }
     }
     if (!hasInvariantSlots) {
         uint32 which = frame.allocTemporary();
         if (which == uint32(-1))
             return false;
         FrameEntry *fe = frame.getTemporary(which);
 
         JaegerSpew(JSpew_Analysis, "Using %s for loop invariant slots of %s\n",
                    frame.entryName(fe), frame.entryName(arraySlot));
 
-        InvariantArraySlots slots;
-        slots.arraySlot = arraySlot;
-        slots.temporary = which;
-        invariantArraySlots.append(slots);
+        InvariantEntry entry;
+        entry.kind = InvariantEntry::INVARIANT_SLOTS;
+        entry.u.array.arraySlot = arraySlot;
+        entry.u.array.temporary = which;
+        invariantEntries.append(entry);
     }
 
-    HoistedBoundsCheck check;
-    check.arraySlot = arraySlot;
-    check.valueSlot = valueSlot;
-    check.constant = constant;
-    hoistedBoundsChecks.append(check);
+    InvariantEntry entry;
+    entry.kind = InvariantEntry::BOUNDS_CHECK;
+    entry.u.check.arraySlot = arraySlot;
+    entry.u.check.valueSlot = valueSlot;
+    entry.u.check.constant = constant;
+    invariantEntries.append(entry);
 
     return true;
 }
 
 void
+LoopState::addNegativeCheck(uint32 valueSlot, int32 constant)
+{
+    /*
+     * Check to see if this check either implies or is implied by an
+     * existing negative check.
+     */
+    for (unsigned i = 0; i < invariantEntries.length(); i++) {
+        InvariantEntry &entry = invariantEntries[i];
+        if (entry.kind == InvariantEntry::NEGATIVE_CHECK &&
+            entry.u.check.valueSlot == valueSlot) {
+            if (entry.u.check.constant > constant)
+                entry.u.check.constant = constant;
+            return;
+        }
+    }
+
+    InvariantEntry entry;
+    entry.kind = InvariantEntry::NEGATIVE_CHECK;
+    entry.u.check.valueSlot = valueSlot;
+    entry.u.check.constant = constant;
+    invariantEntries.append(entry);
+}
+
+void
 LoopState::setLoopReg(AnyRegisterID reg, FrameEntry *fe)
 {
     JS_ASSERT(alloc->loop(reg));
     loopRegs.takeReg(reg);
 
     uint32 slot = frame.indexOfFe(fe);
     JaegerSpew(JSpew_Regalloc, "allocating loop register %s for %s\n",
                reg.name(), frame.entryName(fe));
@@ -372,23 +415,22 @@ LoopState::hoistArrayLengthCheck(const F
     }
 
     /*
      * Check for an overlap with the arrays we think might grow in this loop.
      * This information is only a guess; if we don't think the array can grow
      * but it actually can, we will probably recompile after the hoisted
      * bounds check fails.
      */
-    if (lifetime->nGrowArrays) {
-        types::TypeObject **growArrays = lifetime->growArrays;
+    if (!growArrays.empty()) {
         unsigned count = objTypes->getObjectCount();
         for (unsigned i = 0; i < count; i++) {
             types::TypeObject *object = objTypes->getObject(i);
             if (object) {
-                for (unsigned j = 0; j < lifetime->nGrowArrays; j++) {
+                for (unsigned j = 0; j < growArrays.length(); j++) {
                     if (object == growArrays[j]) {
                         JaegerSpew(JSpew_Analysis, "Object might grow inside loop\n");
                         return false;
                     }
                 }
             }
         }
     }
@@ -403,127 +445,667 @@ LoopState::hoistArrayLengthCheck(const F
 
     if (loopInvariantEntry(index)) {
         /* Hoist checks on x[y] accesses when y is loop invariant. */
         JaegerSpew(JSpew_Analysis, "Hoisted as initlen > %s\n", frame.entryName(index));
 
         return addHoistedCheck(frame.indexOfFe(obj), frame.indexOfFe(index), 0);
     }
 
-    if (frame.indexOfFe(index) == lifetime->testLHS && lifetime->testLessEqual) {
+    if (frame.indexOfFe(index) == testLHS && testLessEqual) {
         /*
          * If the access is of the form x[y] where we know that y <= z + n at
          * the head of the loop, hoist the check as initlen < z + n provided
          * that y has not been modified since the head of the loop.
          */
-        uint32 rhs = lifetime->testRHS;
-        int32 constant = lifetime->testConstant;
+        uint32 rhs = testRHS;
 
         /*
          * If the LHS can decrease in the loop, it could become negative and
          * underflow the array.
          */
-        if (!liveness->nonDecreasing(lifetime->testLHS, lifetime)) {
+        if (!liveness->nonDecreasing(testLHS, lifetime)) {
             JaegerSpew(JSpew_Analysis, "Index may decrease in future iterations\n");
             return false;
         }
 
-        uint32 write = liveness->firstWrite(lifetime->testLHS, lifetime);
-        JS_ASSERT(write != LifetimeLoop::UNASSIGNED);
+        uint32 write = liveness->firstWrite(testLHS, lifetime);
+        JS_ASSERT(write != UNASSIGNED);
         if (write < uint32(PC - script->code)) {
             JaegerSpew(JSpew_Analysis, "Index previously modified in loop\n");
             return false;
         }
 
-        if (rhs != LifetimeLoop::UNASSIGNED) {
-            /*
-             * The index will be a known int or will have been guarded as an int,
-             * but the branch test substitution is only valid if it is comparing
-             * integers.
-             */
+        if (rhs != UNASSIGNED) {
             types::TypeSet *types = cc.getTypeSet(rhs);
-            if (types->getKnownTypeTag(cx) != JSVAL_TYPE_INT32) {
-                JaegerSpew(JSpew_Analysis, "Branch test may not be on integer\n");
+            if (!types) {
+                JaegerSpew(JSpew_Analysis, "Unknown type of branch test\n");
                 return false;
             }
+            if (testLength) {
+                FrameEntry *rhsFE = frame.getOrTrack(rhs);
+                FrameEntry *lengthEntry = invariantLength(rhsFE);
+                if (!lengthEntry) {
+                    JaegerSpew(JSpew_Analysis, "Could not get invariant entry for length\n");
+                    return false;
+                }
+                rhs = frame.indexOfFe(lengthEntry);
+            } else {
+                /*
+                 * The index will be a known int or will have been guarded as an int,
+                 * but the branch test substitution is only valid if it is comparing
+                 * integers.
+                 */
+                if (types->getKnownTypeTag(cx) != JSVAL_TYPE_INT32) {
+                    JaegerSpew(JSpew_Analysis, "Branch test may not be on integer\n");
+                    return false;
+                }
+            }
         }
 
+        /*
+         * Check that the LHS is nonnegative every time we rejoin the loop.
+         * This is only really necessary on initial loop entry. Note that this
+         * test is not sensitive to changes to the LHS between when we make
+         * the test and the start of the next iteration, as we've ensured the
+         * LHS is nondecreasing within the body of the loop.
+         */
+
+        JaegerSpew(JSpew_Analysis, "Nonnegative check %s + %d >= 0\n",
+                   frame.entryName(testLHS), 0);
+
+        addNegativeCheck(testLHS, 0);
+
         JaegerSpew(JSpew_Analysis, "Hoisted as initlen > %s + %d\n",
-                   (rhs == LifetimeLoop::UNASSIGNED) ? "" : frame.entryName(rhs),
-                   constant);
+                   (rhs == UNASSIGNED) ? "" : frame.entryName(rhs),
+                   testConstant);
 
-        return addHoistedCheck(frame.indexOfFe(obj), rhs, constant);
+        return addHoistedCheck(frame.indexOfFe(obj), rhs, testConstant);
     }
 
     JaegerSpew(JSpew_Analysis, "No match found\n");
     return false;
 }
 
 FrameEntry *
 LoopState::invariantSlots(const FrameEntry *obj)
 {
     obj = obj->backing();
     uint32 slot = frame.indexOfFe(obj);
 
-    for (unsigned i = 0; i < invariantArraySlots.length(); i++) {
-        if (invariantArraySlots[i].arraySlot == slot)
-            return frame.getTemporary(invariantArraySlots[i].temporary);
+    for (unsigned i = 0; i < invariantEntries.length(); i++) {
+        InvariantEntry &entry = invariantEntries[i];
+        if (entry.kind == InvariantEntry::INVARIANT_SLOTS &&
+            entry.u.array.arraySlot == slot) {
+            return frame.getTemporary(entry.u.array.temporary);
+        }
     }
 
     /* addHoistedCheck should have ensured there is an entry for the slots. */
     JS_NOT_REACHED("Missing invariant slots");
     return NULL;
 }
 
+FrameEntry *
+LoopState::invariantLength(const FrameEntry *obj)
+{
+    obj = obj->backing();
+    uint32 slot = frame.indexOfFe(obj);
+
+    for (unsigned i = 0; i < invariantEntries.length(); i++) {
+        InvariantEntry &entry = invariantEntries[i];
+        if (entry.kind == InvariantEntry::INVARIANT_LENGTH &&
+            entry.u.array.arraySlot == slot) {
+            FrameEntry *fe = frame.getTemporary(entry.u.array.temporary);
+            frame.learnType(fe, JSVAL_TYPE_INT32, false);
+            return fe;
+        }
+    }
+
+    if (!loopInvariantEntry(obj))
+        return NULL;
+
+    /* Make sure this is a dense array whose length fits in an int32. */
+    types::TypeSet *types = cc.getTypeSet(slot);
+    types::ObjectKind kind = types ? types->getKnownObjectKind(cx) : types::OBJECT_UNKNOWN;
+    if (kind != types::OBJECT_DENSE_ARRAY && kind != types::OBJECT_PACKED_ARRAY)
+        return NULL;
+
+    /*
+     * Don't make 'length' loop invariant if the loop might directly write
+     * to the elements of any of the accessed arrays. This could invoke an
+     * inline path which updates the length.
+     */
+    for (unsigned i = 0; i < types->getObjectCount(); i++) {
+        types::TypeObject *object = types->getObject(i);
+        if (!object)
+            continue;
+        if (object->unknownProperties() || hasModifiedProperty(object, JSID_VOID))
+            return NULL;
+    }
+    types->addFreeze(cx);
+
+    uint32 which = frame.allocTemporary();
+    if (which == uint32(-1))
+        return NULL;
+    FrameEntry *fe = frame.getTemporary(which);
+    frame.learnType(fe, JSVAL_TYPE_INT32, false);
+
+    JaegerSpew(JSpew_Analysis, "Using %s for loop invariant length of %s\n",
+               frame.entryName(fe), frame.entryName(slot));
+
+    InvariantEntry entry;
+    entry.kind = InvariantEntry::INVARIANT_LENGTH;
+    entry.u.array.arraySlot = slot;
+    entry.u.array.temporary = which;
+    invariantEntries.append(entry);
+
+    return fe;
+}
+
 void
 LoopState::restoreInvariants(Assembler &masm, Vector<Jump> *jumps)
 {
     /*
      * Restore all invariants in memory when entering the loop or after any
      * scripted or C++ call, and check that all hoisted conditions. Care should
      * be taken not to clobber the return register or callee-saved registers,
      * which may still be live after some calls.
      */
 
     Registers regs(Registers::TempRegs);
     regs.takeReg(Registers::ReturnReg);
 
-    for (unsigned i = 0; i < invariantArraySlots.length(); i++) {
-        const InvariantArraySlots &entry = invariantArraySlots[i];
-        FrameEntry *fe = frame.getTemporary(entry.temporary);
+    RegisterID T0 = regs.takeAnyReg().reg();
+    RegisterID T1 = regs.takeAnyReg().reg();
+
+    for (unsigned i = 0; i < invariantEntries.length(); i++) {
+        const InvariantEntry &entry = invariantEntries[i];
+        switch (entry.kind) {
+
+          case InvariantEntry::BOUNDS_CHECK: {
+            /*
+             * Hoisted bounds checks always have preceding invariant slots
+             * in the invariant list, so don't recheck this is an object.
+             */
+            masm.loadPayload(frame.addressOf(entry.u.check.arraySlot), T0);
+            masm.load32(Address(T0, offsetof(JSObject, initializedLength)), T0);
+
+            if (entry.u.check.valueSlot != uint32(-1)) {
+                masm.loadPayload(frame.addressOf(entry.u.check.valueSlot), T1);
+                if (entry.u.check.constant != 0) {
+                    Jump overflow = masm.branchAdd32(Assembler::Overflow,
+                                                     Imm32(entry.u.check.constant), T1);
+                    jumps->append(overflow);
+                }
+                Jump j = masm.branch32(Assembler::BelowOrEqual, T0, T1);
+                jumps->append(j);
+            } else {
+                Jump j = masm.branch32(Assembler::BelowOrEqual, T0,
+                                       Imm32(entry.u.check.constant));
+                jumps->append(j);
+            }
+            break;
+          }
+
+          case InvariantEntry::NEGATIVE_CHECK: {
+            masm.loadPayload(frame.addressOf(entry.u.check.valueSlot), T0);
+            if (entry.u.check.constant != 0) {
+                Jump overflow = masm.branchAdd32(Assembler::Overflow,
+                                                 Imm32(entry.u.check.constant), T0);
+                jumps->append(overflow);
+            }
+            Jump j = masm.branch32(Assembler::LessThan, T0, Imm32(0));
+            jumps->append(j);
+            break;
+          }
+
+          case InvariantEntry::INVARIANT_SLOTS:
+          case InvariantEntry::INVARIANT_LENGTH: {
+            /* Make sure this is an object before trying to access its slots or length. */
+            uint32 array = entry.u.array.arraySlot;
+            if (cc.getTypeSet(array)->getKnownTypeTag(cx) != JSVAL_TYPE_OBJECT) {
+                Jump notObject = masm.testObject(Assembler::NotEqual, frame.addressOf(array));
+                jumps->append(notObject);
+            }
+            masm.loadPayload(frame.addressOf(array), T0);
+
+            uint32 offset = (entry.kind == InvariantEntry::INVARIANT_SLOTS)
+                ? JSObject::offsetOfSlots()
+                : offsetof(JSObject, privateData);
+
+            masm.loadPtr(Address(T0, offset), T0);
+            masm.storePtr(T0, frame.addressOf(frame.getTemporary(entry.u.array.temporary)));
+            break;
+          }
+
+          default:
+            JS_NOT_REACHED("Bad invariant kind");
+        }
+    }
+}
+
+/* Loop analysis methods. */
+
+/* :XXX: factor out into more common code. */
+static inline uint32 localSlot(JSScript *script, uint32 local) {
+    return 2 + (script->fun ? script->fun->nargs : 0) + local;
+}
+static inline uint32 argSlot(uint32 arg) {
+    return 2 + arg;
+}
+static inline uint32 thisSlot() {
+    return 1;
+}
+
+/* Whether pc is a loop test operand accessing a variable modified by the loop. */
+bool
+LoopState::loopVariableAccess(jsbytecode *pc)
+{
+    switch (JSOp(*pc)) {
+      case JSOP_GETLOCAL:
+      case JSOP_INCLOCAL:
+      case JSOP_DECLOCAL:
+      case JSOP_LOCALINC:
+      case JSOP_LOCALDEC:
+        if (analysis->localEscapes(GET_SLOTNO(pc)))
+            return false;
+        return liveness->firstWrite(localSlot(script, GET_SLOTNO(pc)), lifetime) != uint32(-1);
+      case JSOP_GETARG:
+      case JSOP_INCARG:
+      case JSOP_DECARG:
+      case JSOP_ARGINC:
+      case JSOP_ARGDEC:
+        if (analysis->argEscapes(GET_SLOTNO(pc)))
+            return false;
+        return liveness->firstWrite(argSlot(GET_SLOTNO(pc)), lifetime) != uint32(-1);
+      default:
+        return false;
+    }
+}
+
+/*
+ * Get any slot/constant accessed by a loop test operand, in terms of its value
+ * at the start of the next loop iteration.
+ */
+bool
+LoopState::getLoopTestAccess(jsbytecode *pc, uint32 *slotp, int32 *constantp)
+{
+    *slotp = UNASSIGNED;
+    *constantp = 0;
 
-        Address array = frame.addressOf(entry.arraySlot);
-        Address address = frame.addressOf(fe);
+    /*
+     * If the pc is modifying a variable and the value tested is its earlier value
+     * (e.g. 'x++ < n'), we need to account for the modification --- at the start
+     * of the next iteration, the value compared will have been 'x - 1'.
+     * Note that we don't need to worry about other accesses to the variable
+     * in the condition like 'x++ < x', as loop tests where both operands are
+     * modified by the loop are rejected.
+     */
+
+    JSOp op = JSOp(*pc);
+    switch (op) {
+
+      case JSOP_GETLOCAL:
+      case JSOP_INCLOCAL:
+      case JSOP_DECLOCAL:
+      case JSOP_LOCALINC:
+      case JSOP_LOCALDEC: {
+        uint32 local = GET_SLOTNO(pc);
+        if (analysis->localEscapes(local))
+            return false;
+        *slotp = localSlot(script, local);
+        if (op == JSOP_LOCALINC)
+            *constantp = -1;
+        else if (op == JSOP_LOCALDEC)
+            *constantp = 1;
+        return true;
+      }
+
+      case JSOP_GETARG:
+      case JSOP_INCARG:
+      case JSOP_DECARG:
+      case JSOP_ARGINC:
+      case JSOP_ARGDEC: {
+        uint32 arg = GET_SLOTNO(pc);
+        if (analysis->argEscapes(arg))
+            return false;
+        *slotp = argSlot(arg);
+        if (op == JSOP_ARGINC)
+            *constantp = -1;
+        else if (op == JSOP_ARGDEC)
+            *constantp = 1;
+        return true;
+      }
+
+      case JSOP_ZERO:
+        *constantp = 0;
+        return true;
+
+      case JSOP_ONE:
+        *constantp = 1;
+        return true;
+
+      case JSOP_UINT16:
+        *constantp = (int32_t) GET_UINT16(pc);
+        return true;
+
+      case JSOP_UINT24:
+        *constantp = (int32_t) GET_UINT24(pc);
+        return true;
 
-        RegisterID reg = regs.takeAnyReg().reg();
-        masm.loadPayload(array, reg);
-        masm.loadPtr(Address(reg, JSObject::offsetOfSlots()), reg);
-        masm.storePtr(reg, address);
-        regs.putReg(reg);
+      case JSOP_INT8:
+        *constantp = GET_INT8(pc);
+        return true;
+
+      case JSOP_INT32:
+        /*
+         * Don't allow big constants out of the range of an object's max
+         * nslots, to avoid integer overflow.
+         */
+        *constantp = GET_INT32(pc);
+        if (*constantp >= JSObject::NSLOTS_LIMIT || *constantp <= -JSObject::NSLOTS_LIMIT)
+            return false;
+        return true;
+
+      default:
+        return false;
+    }
+}
+
+void
+LoopState::analyzeLoopTest()
+{
+    /* Don't handle do-while loops. */
+    if (lifetime->entry == lifetime->head)
+        return;
+
+    /* Don't handle loops with branching inside their condition. */
+    if (lifetime->entry < lifetime->lastBlock)
+        return;
+
+    /* Get the test performed before branching. */
+    jsbytecode *backedge = script->code + lifetime->backedge;
+    if (JSOp(*backedge) != JSOP_IFNE)
+        return;
+    StackAnalysis::PoppedValue test = stack.popped(backedge, 0);
+    if (test.offset == StackAnalysis::UNKNOWN_PUSHED)
+        return;
+    JSOp cmpop = JSOp(script->code[test.offset]);
+    switch (cmpop) {
+      case JSOP_GT:
+      case JSOP_GE:
+      case JSOP_LT:
+      case JSOP_LE:
+        break;
+      default:
+        return;
+    }
+
+    StackAnalysis::PoppedValue poppedOne = stack.popped(test.offset, 1);
+    StackAnalysis::PoppedValue poppedTwo = stack.popped(test.offset, 0);
+
+    if (poppedOne.offset == StackAnalysis::UNKNOWN_PUSHED ||
+        poppedTwo.offset == StackAnalysis::UNKNOWN_PUSHED) {
+        return;
+    }
+
+    jsbytecode *one = script->code + poppedOne.offset;
+    jsbytecode *two = script->code + poppedTwo.offset;
+
+    /* Reverse the condition if the RHS is modified by the loop. */
+    if (loopVariableAccess(two)) {
+        jsbytecode *tmp = one;
+        one = two;
+        two = tmp;
+        cmpop = ReverseCompareOp(cmpop);
     }
 
-    for (unsigned i = 0; i < hoistedBoundsChecks.length(); i++) {
-        /* Testing: initializedLength(array) > value + constant; */
-        const HoistedBoundsCheck &check = hoistedBoundsChecks[i];
+    /* Don't handle comparisons where both the LHS and RHS are modified in the loop. */
+    if (loopVariableAccess(two))
+        return;
+
+    uint32 lhs;
+    int32 lhsConstant;
+    if (!getLoopTestAccess(one, &lhs, &lhsConstant))
+        return;
+
+    uint32 rhs = UNASSIGNED;
+    int32 rhsConstant = 0;
+    bool rhsLength = false;
 
-        RegisterID initlen = regs.takeAnyReg().reg();
-        masm.loadPayload(frame.addressOf(check.arraySlot), initlen);
-        masm.load32(Address(initlen, offsetof(JSObject, initializedLength)), initlen);
+    if (JSOp(*two) == JSOP_LENGTH) {
+        /* Handle 'this.length' or 'x.length' for loop invariant 'x'. */
+        StackAnalysis::PoppedValue array = stack.popped(two, 0);
+        if (array.offset == StackAnalysis::UNKNOWN_PUSHED)
+            return;
+        jsbytecode *arraypc = script->code + array.offset;
+        if (loopVariableAccess(arraypc))
+            return;
+        switch (JSOp(*arraypc)) {
+          case JSOP_GETLOCAL: {
+            uint32 local = GET_SLOTNO(arraypc);
+            if (analysis->localEscapes(local))
+                return;
+            rhs = localSlot(script, local);
+            break;
+          }
+          case JSOP_GETARG: {
+            uint32 arg = GET_SLOTNO(arraypc);
+            if (analysis->argEscapes(arg))
+                return;
+            rhs = argSlot(arg);
+            break;
+          }
+          case JSOP_THIS:
+            rhs = thisSlot();
+            break;
+          default:
+            return;
+        }
+        rhsLength = true;
+    } else {
+        if (!getLoopTestAccess(two, &rhs, &rhsConstant))
+            return;
+    }
+
+    if (lhs == UNASSIGNED)
+        return;
+
+    /* Passed all filters, this is a loop test we can capture. */
+
+    this->testLHS = lhs;
+    this->testRHS = rhs;
+    this->testConstant = rhsConstant - lhsConstant;
+    this->testLength = rhsLength;
+
+    switch (cmpop) {
+      case JSOP_GT:
+        this->testConstant++;  /* x > y ==> x >= y + 1 */
+        /* FALLTHROUGH */
+      case JSOP_GE:
+        this->testLessEqual = false;
+        break;
 
-        if (check.valueSlot != uint32(-1)) {
-            RegisterID value = regs.takeAnyReg().reg();
-            masm.loadPayload(frame.addressOf(check.valueSlot), value);
-            if (check.constant != 0) {
-                Jump overflow = masm.branchAdd32(Assembler::Overflow,
-                                                 Imm32(check.constant), value);
-                jumps->append(overflow);
-            }
-            Jump j = masm.branch32(Assembler::BelowOrEqual, initlen, value);
-            jumps->append(j);
-            regs.putReg(value);
-        } else {
-            Jump j = masm.branch32(Assembler::BelowOrEqual, initlen, Imm32(check.constant));
-            jumps->append(j);
+      case JSOP_LT:
+        this->testConstant--;  /* x < y ==> x <= y - 1 */
+      case JSOP_LE:
+        this->testLessEqual = true;
+        break;
+
+      default:
+        JS_NOT_REACHED("Bad op");
+        return;
+    }
+}
+
+void
+LoopState::analyzeLoopIncrements()
+{
+    /*
+     * Find locals and arguments which are used in exactly one inc/dec operation in every
+     * iteration of the loop (we only match against the last basic block, but could
+     * also handle the first basic block).
+     */
+
+    unsigned nargs = script->fun ? script->fun->nargs : 0;
+    for (unsigned i = 0; i < nargs; i++) {
+        if (analysis->argEscapes(i))
+            continue;
+
+        uint32 offset = liveness->onlyWrite(argSlot(i), lifetime);
+        if (offset == uint32(-1) || offset < lifetime->lastBlock)
+            continue;
+
+        JSOp op = JSOp(script->code[offset]);
+        if (op == JSOP_SETARG)
+            continue;
+
+        Increment inc;
+        inc.slot = argSlot(i);
+        inc.offset = offset;
+        increments.append(inc);
+    }
+
+    for (unsigned i = 0; i < script->nfixed; i++) {
+        if (analysis->localEscapes(i))
+            continue;
+
+        uint32 offset = liveness->onlyWrite(localSlot(script, i), lifetime);
+        if (offset == uint32(-1) || offset < lifetime->lastBlock)
+            continue;
+
+        JSOp op = JSOp(script->code[offset]);
+        if (op == JSOP_SETLOCAL || op == JSOP_SETLOCALPOP)
+            continue;
+
+        Increment inc;
+        inc.slot = localSlot(script, i);
+        inc.offset = offset;
+        increments.append(inc);
+    }
+}
+
+void
+LoopState::analyzeModset()
+{
+    /* :XXX: Currently only doing this for arrays modified in the loop. */
+
+    unsigned offset = lifetime->head;
+    while (offset < lifetime->backedge) {
+        jsbytecode *pc = script->code + offset;
+        uint32 successorOffset = offset + GetBytecodeLength(pc);
+
+        analyze::Bytecode *opinfo = analysis->maybeCode(offset);
+        if (!opinfo) {
+            offset = successorOffset;
+            continue;
         }
 
-        regs.putReg(initlen);
+        JSOp op = JSOp(*pc);
+        switch (op) {
+
+          case JSOP_SETHOLE:
+          case JSOP_SETELEM: {
+            types::TypeSet *objTypes = poppedTypes(pc, 2);
+            types::TypeSet *elemTypes = poppedTypes(pc, 1);
+
+            /*
+             * Mark the modset as unknown if the index might be non-integer,
+             * we don't want to consider the SETELEM PIC here.
+             */
+            if (!objTypes || objTypes->unknown() || !elemTypes ||
+                elemTypes->getKnownTypeTag(cx) != JSVAL_TYPE_INT32) {
+                unknownModset = true;
+                return;
+            }
+
+            objTypes->addFreeze(cx);
+            for (unsigned i = 0; i < objTypes->getObjectCount(); i++) {
+                types::TypeObject *object = objTypes->getObject(i);
+                if (!object)
+                    continue;
+                if (!addModifiedProperty(object, JSID_VOID))
+                    return;
+                if (op == JSOP_SETHOLE && !addGrowArray(object))
+                    return;
+            }
+            break;
+          }
+
+          default:
+            break;
+        }
+
+        offset = successorOffset;
     }
 }
+
+bool
+LoopState::addGrowArray(types::TypeObject *object)
+{
+    static const uint32 MAX_SIZE = 10;
+    for (unsigned i = 0; i < growArrays.length(); i++) {
+        if (growArrays[i] == object)
+            return true;
+    }
+    if (growArrays.length() >= MAX_SIZE) {
+        unknownModset = true;
+        return false;
+    }
+    growArrays.append(object);
+
+    return true;
+}
+
+bool
+LoopState::addModifiedProperty(types::TypeObject *object, jsid id)
+{
+    static const uint32 MAX_SIZE = 20;
+    for (unsigned i = 0; i < modifiedProperties.length(); i++) {
+        if (modifiedProperties[i].object == object && modifiedProperties[i].id == id)
+            return true;
+    }
+    if (modifiedProperties.length() >= MAX_SIZE) {
+        unknownModset = true;
+        return false;
+    }
+
+    ModifiedProperty property;
+    property.object = object;
+    property.id = id;
+    modifiedProperties.append(property);
+
+    return true;
+}
+
+bool
+LoopState::hasGrowArray(types::TypeObject *object)
+{
+    if (unknownModset)
+        return true;
+    for (unsigned i = 0; i < growArrays.length(); i++) {
+        if (growArrays[i] == object)
+            return true;
+    }
+    return false;
+}
+
+bool
+LoopState::hasModifiedProperty(types::TypeObject *object, jsid id)
+{
+    if (unknownModset)
+        return true;
+    for (unsigned i = 0; i < modifiedProperties.length(); i++) {
+        if (modifiedProperties[i].object == object && modifiedProperties[i].id == id)
+            return true;
+    }
+    return false;
+}
+
+inline types::TypeSet *
+LoopState::poppedTypes(jsbytecode *pc, unsigned which)
+{
+    StackAnalysis::PoppedValue value = stack.popped(pc, which);
+    if (value.offset == StackAnalysis::UNKNOWN_PUSHED)
+        return NULL;
+    return script->types->pushed(value.offset, value.which);
+}
--- a/js/src/methodjit/LoopState.h
+++ b/js/src/methodjit/LoopState.h
@@ -139,43 +139,54 @@ class LoopState : public MacroAssemblerT
 
         /* Index into Compiler's callSites or rejoinSites */
         unsigned patchIndex;
         bool patchCall;
     };
     Vector<RestoreInvariantCall> restoreInvariantCalls;
 
     /*
-     * Array bounds check hoisted out of the loop. This is a check that needs
-     * to be performed, expressed in terms of the state at the loop head.
+     * Aggregate structure for all loop invariant code and hoisted checks we
+     * can perform. These are all stored in the same vector as they may depend
+     * on each other and we need to emit code restoring them in order.
      */
-    struct HoistedBoundsCheck
-    {
-        /* initializedLength(array) > value + constant */
-        uint32 arraySlot;
-        uint32 valueSlot;
-        int32 constant;
+    struct InvariantEntry {
+        enum {
+            /*
+             * initializedLength(array) > value + constant.
+             * Unsigned comparison, so will fail if value + constant < 0
+             */
+            BOUNDS_CHECK,
+
+            /* value + constant >= 0 */
+            NEGATIVE_CHECK,
+
+            INVARIANT_SLOTS,
+            INVARIANT_LENGTH
+        } kind;
+        union {
+            struct {
+                uint32 arraySlot;
+                uint32 valueSlot;
+                int32 constant;
+            } check;
+            struct {
+                uint32 arraySlot;
+                uint32 temporary;
+            } array;
+        } u;
+        InvariantEntry() { PodZero(this); }
     };
-    Vector<HoistedBoundsCheck, 4, CompilerAllocPolicy> hoistedBoundsChecks;
+    Vector<InvariantEntry, 4, CompilerAllocPolicy> invariantEntries;
 
     bool loopInvariantEntry(const FrameEntry *fe);
     bool addHoistedCheck(uint32 arraySlot, uint32 valueSlot, int32 constant);
+    void addNegativeCheck(uint32 valueSlot, int32 constant);
 
-    /*
-     * Track analysis temporaries in the frame state which hold slots pointers
-     * for arrays throughout the loop.
-     */
-    struct InvariantArraySlots
-    {
-        uint32 arraySlot;
-        uint32 temporary;
-    };
-    Vector<InvariantArraySlots, 4, CompilerAllocPolicy> invariantArraySlots;
-
-    bool hasInvariants() { return !hoistedBoundsChecks.empty() || !invariantArraySlots.empty(); }
+    bool hasInvariants() { return !invariantEntries.empty(); }
     void restoreInvariants(Assembler &masm, Vector<Jump> *jumps);
 
   public:
 
     /* Outer loop to this one, in case of loop nesting. */
     LoopState *outer;
 
     /* Current bytecode for compilation. */
@@ -219,14 +230,82 @@ class LoopState : public MacroAssemblerT
 
     void addJoin(unsigned index, bool script);
     void clearLoopRegisters();
 
     void flushLoop(StubCompiler &stubcc);
 
     bool hoistArrayLengthCheck(const FrameEntry *obj, const FrameEntry *id);
     FrameEntry *invariantSlots(const FrameEntry *obj);
+    FrameEntry *invariantLength(const FrameEntry *obj);
+
+  private:
+    /* Analysis information for the loop. */
+
+    /* Stack information at points within this loop. */
+    analyze::StackAnalysis stack;
+
+    /*
+     * Any inequality known to hold at the head of the loop. This has the
+     * form 'lhs <= rhs + constant' or 'lhs >= rhs + constant', depending on
+     * lessEqual. The lhs may be modified within the loop body (the test is
+     * invalid afterwards), and the rhs is invariant. This information is only
+     * valid if the LHS/RHS are known integers.
+     */
+    enum { UNASSIGNED = uint32(-1) };
+    uint32 testLHS;
+    uint32 testRHS;
+    int32 testConstant;
+    bool testLessEqual;
+
+    /*
+     * The rhs in the test is testRHS.length; for the test to be valid, the
+     * length must not be directly modified within the loop.
+     */
+    bool testLength;
+
+    /*
+     * A variable which will be incremented or decremented exactly once in each
+     * iteration of the loop. The offset of the operation is indicated, which
+     * may or may not run after the initial entry into the loop.
+     */
+    struct Increment {
+        uint32 slot;
+        uint32 offset;
+    };
+    Vector<Increment, 4, CompilerAllocPolicy> increments;
+
+    /* It is unknown which arrays grow or which objects are modified in this loop. */
+    bool unknownModset;
+
+    /*
+     * Arrays which might grow during this loop. This is a guess, and may
+     * underapproximate the actual set of such arrays.
+     */
+    Vector<types::TypeObject *, 4, CompilerAllocPolicy> growArrays;
+
+    /* Properties which might be modified during this loop. */
+    struct ModifiedProperty {
+        types::TypeObject *object;
+        jsid id;
+    };
+    Vector<ModifiedProperty, 4, CompilerAllocPolicy> modifiedProperties;
+
+    void analyzeLoopTest();
+    void analyzeLoopIncrements();
+    void analyzeModset();
+
+    bool loopVariableAccess(jsbytecode *pc);
+    bool getLoopTestAccess(jsbytecode *pc, uint32 *slotp, int32 *constantp);
+
+    bool addGrowArray(types::TypeObject *object);
+    bool addModifiedProperty(types::TypeObject *object, jsid id);
+
+    bool hasGrowArray(types::TypeObject *object);
+    bool hasModifiedProperty(types::TypeObject *object, jsid id);
+
+    inline types::TypeSet *poppedTypes(jsbytecode *pc, unsigned which);
 };
 
 } /* namespace mjit */
 } /* namespace js */
 
 #endif /* jsjaeger_loopstate_h__ */