[INFER] Array bounds check hoisting, cleanup, bug 618690.
authorBrian Hackett <bhackett1024@gmail.com>
Tue, 05 Apr 2011 18:12:03 -0700
changeset 74903 7928f2dc3d4def6522514ec90d0aaf7f17c9474e
parent 74902 83c58db6e5902fc9e2ed0ffba4d5b7ab8104ff43
child 74904 98d28777528bfcabf8c06f1a9f705ef1ad50ef78
push id2
push userbsmedberg@mozilla.com
push dateFri, 19 Aug 2011 14:38:13 +0000
bugs618690
milestone2.2a1pre
[INFER] Array bounds check hoisting, cleanup, bug 618690.
js/src/Makefile.in
js/src/jit-test/tests/jaeger/loops/hoist-01.js
js/src/jit-test/tests/jaeger/loops/hoist-02.js
js/src/jit-test/tests/jaeger/loops/hoist-03.js
js/src/jit-test/tests/jaeger/loops/hoist-04.js
js/src/jit-test/tests/jaeger/loops/hoist-05.js
js/src/jsanalyze.cpp
js/src/jsanalyze.h
js/src/jsapi.cpp
js/src/jsarray.cpp
js/src/jscntxt.h
js/src/jsfun.cpp
js/src/jsinfer.cpp
js/src/jsinfer.h
js/src/jsinferinlines.h
js/src/jsinterp.cpp
js/src/jsobjinlines.h
js/src/jsopcode.cpp
js/src/jsopcode.tbl
js/src/jsscript.h
js/src/jstracer.cpp
js/src/methodjit/Compiler.cpp
js/src/methodjit/Compiler.h
js/src/methodjit/FastArithmetic.cpp
js/src/methodjit/FastOps.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/Logging.cpp
js/src/methodjit/Logging.h
js/src/methodjit/LoopState.cpp
js/src/methodjit/LoopState.h
js/src/methodjit/MonoIC.cpp
js/src/methodjit/PolyIC.cpp
js/src/methodjit/StubCalls.cpp
js/src/methodjit/StubCalls.h
js/src/methodjit/StubCompiler.cpp
--- a/js/src/Makefile.in
+++ b/js/src/Makefile.in
@@ -321,16 +321,17 @@ VPATH += 	$(srcdir)/methodjit
 
 CPPSRCS += 	MethodJIT.cpp \
 		StubCalls.cpp \
 		Compiler.cpp \
 		FrameState.cpp \
 		FastArithmetic.cpp \
 		FastBuiltins.cpp \
 		FastOps.cpp \
+		LoopState.cpp \
 		StubCompiler.cpp \
 		MonoIC.cpp \
 		PolyIC.cpp \
 		ImmutableSync.cpp \
 		InvokeHelpers.cpp \
 		Retcon.cpp \
 		TrampolineCompiler.cpp \
 		$(NULL)
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/jaeger/loops/hoist-01.js
@@ -0,0 +1,35 @@
+function foo(x, n) {
+  for (var i = 0; i < n; i++)
+    x[i] = i;
+  var q = 0;
+  for (var i = 0; i < 10; i++) {
+    for (var j = 0; j < n; j++)
+      q += x[j];
+  }
+  return q;
+}
+
+var a = foo([], 100);
+assertEq(a, 49500);
+
+function basic1(x) {
+  var q = 0;
+  for (var i = 0; i < 4; i++)
+    q += x[i];
+  return q;
+}
+
+var b = basic1([1,2,3,4]);
+assertEq(b, 10);
+
+ARRAY = [1,2,3,4];
+
+function basic2() {
+  var q = 0;
+  for (var i = 0; i < 4; i++)
+    q += ARRAY[i];
+  return q;
+}
+
+var c = basic2();
+assertEq(c, 10);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/jaeger/loops/hoist-02.js
@@ -0,0 +1,12 @@
+function foo(x, n) {
+  var a = 0;
+  for (var i = 0; i < n; i++)
+    a += x[3];
+  return a;
+}
+
+var a = foo([1,2,3,4], 100);
+assertEq(a, 400);
+
+var b = foo([1,2], 100);
+assertEq(b, NaN);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/jaeger/loops/hoist-03.js
@@ -0,0 +1,12 @@
+function foo(x, j, n) {
+  var a = 0;
+  for (var i = 0; i < n; i++)
+    a += x[j];
+  return a;
+}
+
+var a = foo([1,2,3,4], 3, 100);
+assertEq(a, 400);
+
+var b = foo([1,2,3,4], 5, 100);
+assertEq(b, NaN);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/jaeger/loops/hoist-04.js
@@ -0,0 +1,18 @@
+function bar(x, i) {
+  if (i == 50)
+    x.length = 0;
+}
+
+function foo(x, j, n) {
+  var a = 0;
+  for (var i = 0; i < n; i++) {
+    var q = x[j];
+    bar(x, i);
+    if (typeof q == 'undefined')
+      a++;
+  }
+  return a;
+}
+
+var a = foo([1,2,3,4], 3, 100);
+assertEq(a, 49);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/jaeger/loops/hoist-05.js
@@ -0,0 +1,19 @@
+function bar(x, i) {
+  if (i == 50)
+    foo.arguments[1] = 20;
+}
+
+function foo(x, j, n) {
+  var a = 0;
+  arguments;
+  for (var i = 0; i < n; i++) {
+    var q = x[j];
+    bar(x, i);
+    if (typeof q == 'undefined')
+      a++;
+  }
+  return a;
+}
+
+var a = foo([1,2,3,4], 3, 100);
+assertEq(a, 49);
--- a/js/src/jsanalyze.cpp
+++ b/js/src/jsanalyze.cpp
@@ -37,16 +37,19 @@
  *
  * ***** END LICENSE BLOCK ***** */
 
 #include "jsanalyze.h"
 #include "jsautooplen.h"
 #include "jscompartment.h"
 #include "jscntxt.h"
 
+#include "jsinferinlines.h"
+#include "jsobjinlines.h"
+
 namespace js {
 namespace analyze {
 
 /////////////////////////////////////////////////////////////////////
 // Script
 /////////////////////////////////////////////////////////////////////
 
 Script::Script()
@@ -741,142 +744,228 @@ LifetimeScript::analyze(JSContext *cx, a
     this->script = script;
 
     codeArray = ArenaArray<LifetimeBytecode>(pool, script->length);
     if (!codeArray)
         return false;
     PodZero(codeArray, script->length);
 
     unsigned nfixed = analysis->localCount();
-    locals = ArenaArray<LifetimeVariable>(pool, nfixed);
-    if (!locals)
-        return false;
-    PodZero(locals, nfixed);
+    unsigned nargs = script->fun ? script->fun->nargs : 0;
 
-    unsigned nargs = script->fun ? script->fun->nargs : 0;
-    args = ArenaArray<LifetimeVariable>(pool, nargs);
-    if (!args)
+    nLifetimes = 2 + nargs + nfixed;
+    lifetimes = ArenaArray<LifetimeVariable>(pool, nLifetimes);
+    if (!lifetimes)
         return false;
-    PodZero(args, nargs);
+    PodZero(lifetimes, nLifetimes);
 
-    PodZero(&thisVar);
+    LifetimeVariable *thisVar = lifetimes + 1;
+    LifetimeVariable *args = lifetimes + 2;
+    LifetimeVariable *locals = lifetimes + 2 + nargs;
 
-    saved = ArenaArray<LifetimeVariable*>(pool, nfixed + nargs + 1);
+    saved = ArenaArray<LifetimeVariable*>(pool, nLifetimes);
     if (!saved)
         return false;
     savedCount = 0;
 
+    LifetimeLoop *loop = NULL;
+
     uint32 offset = script->length - 1;
     while (offset < script->length) {
         Bytecode *code = analysis->maybeCode(offset);
         if (!code) {
             offset--;
             continue;
         }
 
+        if (loop && code->safePoint)
+            loop->hasSafePoints = true;
+
         UntrapOpcode untrap(cx, script, script->code + offset);
 
-        if (codeArray[offset].loopBackedge) {
+        if (codeArray[offset].loop) {
             /*
              * This is the head of a loop, we need to go and make sure that any
              * variables live at the head are live at the backedge and points prior.
              * For each such variable, look for the last lifetime segment in the body
              * and extend it to the end of the loop.
              */
-            unsigned backedge = codeArray[offset].loopBackedge;
+            unsigned backedge = codeArray[offset].loop->backedge;
             for (unsigned i = 0; i < nfixed; i++) {
                 if (locals[i].lifetime && !extendVariable(cx, locals[i], offset, backedge))
                     return false;
             }
             for (unsigned i = 0; i < nargs; i++) {
                 if (args[i].lifetime && !extendVariable(cx, args[i], offset, backedge))
                     return false;
             }
+
+            JS_ASSERT_IF(loop, loop == codeArray[offset].loop);
+            loop = NULL;
         }
 
+        /* Find the last jump target in the loop, other than the initial entry point. */
+        if (loop && code->jumpTarget && offset != loop->entry && offset > loop->lastBlock)
+            loop->lastBlock = offset;
+
         jsbytecode *pc = script->code + offset;
         JSOp op = (JSOp) *pc;
 
         switch (op) {
           case JSOP_GETARG:
           case JSOP_CALLARG:
-          case JSOP_INCARG:
-          case JSOP_DECARG:
-          case JSOP_ARGINC:
-          case JSOP_ARGDEC:
           case JSOP_GETARGPROP: {
             unsigned arg = GET_ARGNO(pc);
             if (!analysis->argEscapes(arg)) {
                 if (!addVariable(cx, args[arg], offset))
                     return false;
             }
             break;
           }
 
           case JSOP_SETARG: {
             unsigned arg = GET_ARGNO(pc);
-            if (!analysis->argEscapes(arg))
-                killVariable(cx, args[arg], offset);
+            if (!analysis->argEscapes(arg)) {
+                if (!killVariable(cx, args[arg], offset))
+                    return false;
+            }
+            break;
+          }
+
+          case JSOP_INCARG:
+          case JSOP_DECARG:
+          case JSOP_ARGINC:
+          case JSOP_ARGDEC: {
+            unsigned arg = GET_ARGNO(pc);
+            if (!analysis->argEscapes(arg)) {
+                if (!killVariable(cx, args[arg], offset))
+                    return false;
+                if (!addVariable(cx, args[arg], offset))
+                    return false;
+            }
             break;
           }
 
           case JSOP_GETLOCAL:
           case JSOP_CALLLOCAL:
-          case JSOP_INCLOCAL:
-          case JSOP_DECLOCAL:
-          case JSOP_LOCALINC:
-          case JSOP_LOCALDEC:
           case JSOP_GETLOCALPROP: {
             unsigned local = GET_SLOTNO(pc);
             if (!analysis->localEscapes(local)) {
                 JS_ASSERT(local < nfixed);
                 if (!addVariable(cx, locals[local], offset))
                     return false;
             }
             break;
           }
 
           case JSOP_SETLOCAL:
           case JSOP_SETLOCALPOP:
           case JSOP_DEFLOCALFUN: {
             unsigned local = GET_SLOTNO(pc);
             if (!analysis->localEscapes(local)) {
                 JS_ASSERT(local < nfixed);
-                killVariable(cx, locals[local], offset);
+                if (!killVariable(cx, locals[local], offset))
+                    return false;
+            }
+            break;
+          }
+
+          case JSOP_INCLOCAL:
+          case JSOP_DECLOCAL:
+          case JSOP_LOCALINC:
+          case JSOP_LOCALDEC: {
+            unsigned local = GET_SLOTNO(pc);
+            if (!analysis->localEscapes(local)) {
+                if (!killVariable(cx, locals[local], offset))
+                    return false;
+                if (!addVariable(cx, locals[local], offset))
+                    return false;
             }
             break;
           }
 
           case JSOP_THIS:
           case JSOP_GETTHISPROP:
-            if (!addVariable(cx, thisVar, offset))
+            if (!addVariable(cx, *thisVar, offset))
                 return false;
             break;
 
           case JSOP_IFEQ:
           case JSOP_IFEQX:
           case JSOP_IFNE:
           case JSOP_IFNEX:
           case JSOP_OR:
           case JSOP_ORX:
           case JSOP_AND:
           case JSOP_ANDX:
           case JSOP_GOTO:
           case JSOP_GOTOX: {
+            /*
+             * Forward jumps need to pull in all variables which are live at
+             * their target offset --- the variables live before the jump are
+             * the union of those live at the fallthrough and at the target.
+             */
             uint32 targetOffset = offset + GetJumpOffset(pc, pc);
             if (targetOffset < offset) {
                 JSOp nop = JSOp(script->code[targetOffset]);
                 if (nop == JSOP_GOTO || nop == JSOP_GOTOX) {
                     /* This is a continue, short circuit the backwards goto. */
                     jsbytecode *target = script->code + targetOffset;
                     targetOffset = targetOffset + GetJumpOffset(target, target);
+
+                    /*
+                     * Unless this is continuing an outer loop, it is a jump to
+                     * the entry offset separate from the initial jump.
+                     * Prune the last block in the loop.
+                     */
+                    JS_ASSERT(loop);
+                    if (loop->entry == targetOffset && loop->entry > loop->lastBlock)
+                        loop->lastBlock = loop->entry;
                 } else {
                     /* This is a loop back edge, no lifetime to pull in yet. */
                     JS_ASSERT(nop == JSOP_TRACE || nop == JSOP_NOTRACE);
-                    codeArray[targetOffset].loopBackedge = offset;
+
+                    /*
+                     * If we already have a loop, it is an outer loop and we
+                     * need to prune the last block in the loop --- we do not
+                     * track 'continue' statements for outer loops.
+                     */
+                    if (loop && loop->entry > loop->lastBlock)
+                        loop->lastBlock = loop->entry;
+
+                    loop = ArenaNew<LifetimeLoop>(pool);
+                    if (!loop)
+                        return false;
+                    PodZero(loop);
+
+                    codeArray[targetOffset].loop = loop;
+                    loop->head = targetOffset;
+                    loop->backedge = offset;
+                    loop->lastBlock = loop->head;
+
+                    /*
+                     * Find the entry jump, which will be a GOTO for 'for' or
+                     * 'while'loops or a fallthrough for 'do while' loops.
+                     */
+                    uint32 entry = targetOffset;
+                    if (entry) {
+                        do {
+                            entry--;
+                        } while (!analysis->maybeCode(entry));
+
+                        jsbytecode *entrypc = script->code + entry;
+                        if (JSOp(*entrypc) == JSOP_GOTO || JSOp(*entrypc) == JSOP_GOTOX)
+                            loop->entry = entry + GetJumpOffset(entrypc, entrypc);
+                        else
+                            loop->entry = targetOffset;
+                    } else {
+                        /* Do-while loop at the start of the script. */
+                        loop->entry = targetOffset;
+                    }
+
                     break;
                 }
             }
             for (unsigned i = 0; i < savedCount; i++) {
                 LifetimeVariable &var = *saved[i];
                 JS_ASSERT(!var.lifetime && var.saved);
                 if (!var.savedEnd) {
                     /*
@@ -961,35 +1050,44 @@ LifetimeScript::addVariable(JSContext *c
         var.lifetime = ArenaNew<Lifetime>(pool, offset, var.saved);
         if (!var.lifetime)
             return false;
         var.saved = NULL;
     }
     return true;
 }
 
-inline void
+inline bool
 LifetimeScript::killVariable(JSContext *cx, LifetimeVariable &var, unsigned offset)
 {
-    if (!var.lifetime)
-        return;
+    if (!var.lifetime) {
+        /* Make a point lifetime indicating the write. */
+        var.saved = ArenaNew<Lifetime>(pool, offset, var.saved);
+        if (!var.saved)
+            return false;
+        var.saved->write = true;
+        return true;
+    }
     JS_ASSERT(offset < var.lifetime->start);
 
     /*
      * The variable is considered to be live at the bytecode which kills it
      * (just not at earlier bytecodes). This behavior is needed by downstream
      * register allocation (see FrameState::bestEvictReg).
      */
     var.lifetime->start = offset;
+    var.lifetime->write = true;
 
     var.saved = var.lifetime;
     var.savedEnd = 0;
     var.lifetime = NULL;
 
     saved[savedCount++] = &var;
+
+    return true;
 }
 
 inline bool
 LifetimeScript::extendVariable(JSContext *cx, LifetimeVariable &var, unsigned start, unsigned end)
 {
     JS_ASSERT(var.lifetime);
     var.lifetime->start = start;
 
@@ -1006,10 +1104,372 @@ 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
@@ -283,16 +283,34 @@ GetDefCount(JSScript *script, unsigned o
         return 1;
       case JSOP_FILTER:
         return 2;
       default:
         return js_CodeSpec[*pc].ndefs;
     }
 }
 
+static inline JSOp
+ReverseCompareOp(JSOp op)
+{
+    switch (op) {
+      case JSOP_GT:
+        return JSOP_LT;
+      case JSOP_GE:
+        return JSOP_LE;
+      case JSOP_LT:
+        return JSOP_GT;
+      case JSOP_LE:
+        return JSOP_GE;
+      default:
+        JS_NOT_REACHED("unrecognized op");
+        return op;
+    }
+}
+
 /* Untrap a single PC, and retrap it at scope exit. */
 struct UntrapOpcode
 {
     jsbytecode *pc;
     bool trap;
 
     UntrapOpcode(JSContext *cx, JSScript *script, jsbytecode *pc)
         : pc(pc), trap(JSOp(*pc) == JSOP_TRAP)
@@ -315,51 +333,122 @@ struct UntrapOpcode
  * described in:
  *
  * "Quality and Speed in Linear-scan Register Allocation"
  * Traub et. al.
  * PLDI, 1998
  */
 
 /*
- * Information about the lifetime of a local or argument. These form a linked list
- * describing successive intervals in the program where the variable's value
- * may be live. At points in the script not in one of these segments (points in
- * a 'lifetime hole'), the variable is dead and registers containing its type/payload
- * can be discarded without needing to be synced.
+ * Information about the lifetime of a local or argument. These form a linked
+ * list describing successive intervals in the program where the variable's
+ * value may be live. At points in the script not in one of these segments
+ * (points in a 'lifetime hole'), the variable is dead and registers containing
+ * its type/payload can be discarded without needing to be synced.
  */
 struct Lifetime
 {
     /*
-     * Start and end offsets of this lifetime. The variable is live at the beginning
-     * of every bytecode in this (inclusive) range.
+     * Start and end offsets of this lifetime. The variable is live at the
+     * beginning of every bytecode in this (inclusive) range.
      */
     uint32 start;
     uint32 end;
 
     /*
-     * This is an artificial segment extending the lifetime of a variable to the
-     * end of a loop, when it is live at the head of the loop. It will not be used
-     * anymore in the loop body until the next iteration.
+     * This is an artificial segment extending the lifetime of a variable to
+     * the end of a loop, when it is live at the head of the loop. It will not
+     * be used anymore in the loop body until the next iteration.
      */
     bool loopTail;
 
+    /*
+     * The start of this lifetime is a bytecode writing the variable. Each
+     * write to a variable is associated with a lifetime.
+     */
+    bool write;
+
     /* Next lifetime. The variable is dead from this->end to next->start. */
     Lifetime *next;
 
     Lifetime(uint32 offset, Lifetime *next)
-        : start(offset), end(offset), loopTail(false), next(next)
+        : start(offset), end(offset), loopTail(false), write(false), next(next)
     {}
 };
 
+/* Lifetime and modset information for a loop. */
+struct LifetimeLoop
+{
+    /* Offset of the head of the loop. */
+    uint32 head;
+
+    /*
+     * Offset of the unique jump going to the head of the loop. The code
+     * between the head and the backedge forms the loop body.
+     */
+    uint32 backedge;
+
+    /* Target offset of the initial jump or fallthrough into the loop. */
+    uint32 entry;
+
+    /*
+     * 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;
+
+    /*
+     * 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, offset of the loop back edge. */
-    uint32 loopBackedge;
+    /* If this is a loop head, information about the loop. */
+    LifetimeLoop *loop;
 
     /* Any allocation computed downstream for this bytecode. */
     mjit::RegisterAllocation *allocation;
 };
 
 /* Current lifetime information for a variable. */
 struct LifetimeVariable
 {
@@ -367,43 +456,75 @@ struct LifetimeVariable
     Lifetime *lifetime;
 
     /* If the variable is currently dead, the next live segment. */
     Lifetime *saved;
 
     /* Jump preceding the basic block which killed this variable. */
     uint32 savedEnd;
 
+    /* Whether this variable is live at offset. */
     Lifetime * live(uint32 offset) {
         if (lifetime && lifetime->end >= offset)
             return lifetime;
         Lifetime *segment = lifetime ? lifetime : saved;
         while (segment && segment->start <= offset) {
             if (segment->end >= offset)
                 return segment;
             segment = segment->next;
         }
         return NULL;
     }
+
+    /*
+     * Get the offset of the first write to the variable in the body of a loop,
+     * -1 if the loop never writes the variable.
+     */
+    uint32 firstWrite(LifetimeLoop *loop) {
+        Lifetime *segment = lifetime ? lifetime : saved;
+        while (segment && segment->start <= loop->backedge) {
+            if (segment->start >= loop->head && segment->write)
+                return segment->start;
+            segment = segment->next;
+        }
+        return uint32(-1);
+    }
+
+    /*
+     * If the variable is only written once in the body of a loop, offset of
+     * that write. -1 otherwise.
+     */
+    uint32 onlyWrite(LifetimeLoop *loop) {
+        uint32 offset = uint32(-1);
+        Lifetime *segment = lifetime ? lifetime : saved;
+        while (segment && segment->start <= loop->backedge) {
+            if (segment->start >= loop->head && segment->write) {
+                if (offset != uint32(-1))
+                    return uint32(-1);
+                offset = segment->start;
+            }
+            segment = segment->next;
+        }
+        return offset;
+    }
 };
 
 /*
  * Analysis approximating variable liveness information at points in a script.
  * This is separate from analyze::Script as it is computed on every compilation
  * and thrown away afterwards.
  */
 class LifetimeScript
 {
     analyze::Script *analysis;
     JSScript *script;
 
     LifetimeBytecode *codeArray;
-    LifetimeVariable *locals;
-    LifetimeVariable *args;
-    LifetimeVariable thisVar;
+    LifetimeVariable *lifetimes;
+    uint32 nLifetimes;
 
     LifetimeVariable **saved;
     unsigned savedCount;
 
   public:
     JSArenaPool pool;
 
     LifetimeScript();
@@ -414,33 +535,51 @@ class LifetimeScript
     LifetimeBytecode &getCode(uint32 offset) {
         JS_ASSERT(analysis->maybeCode(offset));
         return codeArray[offset];
     }
     LifetimeBytecode &getCode(jsbytecode *pc) { return getCode(pc - script->code); }
 
 #ifdef DEBUG
     void dumpVariable(LifetimeVariable &var);
-    void dumpLocal(unsigned i) { dumpVariable(locals[i]); }
-    void dumpArg(unsigned i) { dumpVariable(args[i]); }
+    void dumpSlot(unsigned slot) {
+        JS_ASSERT(slot < nLifetimes);
+        dumpVariable(lifetimes[slot]);
+    }
 #endif
 
-    Lifetime * argLive(uint32 arg, uint32 offset) {
-        JS_ASSERT(script->fun && arg < script->fun->nargs);
-        return args[arg].live(offset);
+    Lifetime * live(uint32 slot, uint32 offset) {
+        JS_ASSERT(slot < nLifetimes);
+        return lifetimes[slot].live(offset);
+    }
+
+    uint32 firstWrite(uint32 slot, LifetimeLoop *loop) {
+        JS_ASSERT(slot < nLifetimes);
+        return lifetimes[slot].firstWrite(loop);
     }
-    Lifetime * localLive(uint32 local, uint32 offset) {
-        JS_ASSERT(local < analysis->localCount());
-        return locals[local].live(offset);
+
+    uint32 onlyWrite(uint32 slot, LifetimeLoop *loop) {
+        JS_ASSERT(slot < nLifetimes);
+        return lifetimes[slot].onlyWrite(loop);
     }
-    Lifetime * thisLive(uint32 offset) { return thisVar.live(offset); }
+
+    /*
+     * 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 void killVariable(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/jsapi.cpp
+++ b/js/src/jsapi.cpp
@@ -3051,18 +3051,18 @@ JS_NewGlobalObject(JSContext *cx, JSClas
     JS_ASSERT(clasp->flags & JSCLASS_IS_GLOBAL);
     JSObject *obj = NewNonFunction<WithProto::Given>(cx, Valueify(clasp), NULL, NULL);
     if (!obj)
         return NULL;
 
     TypeObject *type = cx->newTypeObject("Global", NULL);
     if (!type || !obj->setTypeAndUniqueShape(cx, type))
         return NULL;
-    if (Valueify(clasp)->ext.equality)
-        type->hasSpecialEquality = true;
+    if (Valueify(clasp)->ext.equality && !cx->markTypeObjectHasSpecialEquality(type))
+        return NULL;
 
     obj->syncSpecialEquality();
 
     /* Construct a regexp statics object for this global object. */
     JSObject *res = regexp_statics_construct(cx, obj);
     if (!res ||
         !js_SetReservedSlot(cx, obj, JSRESERVED_GLOBAL_REGEXP_STATICS, ObjectValue(*res)) ||
         !js_SetReservedSlot(cx, obj, JSRESERVED_GLOBAL_FLAGS, Int32Value(0))) {
--- a/js/src/jsarray.cpp
+++ b/js/src/jsarray.cpp
@@ -58,23 +58,24 @@
  * length and the length property are left uninitialized, but are conceptually holes.
  * Arrays with no holes below the initialized length are "packed" arrays.
  *
  * NB: the capacity and length of a dense array are entirely unrelated!  The
  * length may be greater than, less than, or equal to the capacity. The first
  * case may occur when the user writes "new Array(100), in which case the
  * length is 100 while the capacity remains 0 (indices below length and above
  * capacity must be treated as holes). See array_length_setter for another
- * explanation of how the first case may occur. The initialized length is always
- * less than or equal to both the length and capacity.
+ * explanation of how the first case may occur. When type inference is enabled,
+ * the initialized length is always less than or equal to both the length and
+ * capacity. Otherwise, the initialized length always equals the capacity.
  *
  * Arrays are converted to use js_SlowArrayClass when any of these conditions
  * are met:
- *  - there are more than MIN_SPARSE_INDEX slots total
- *  - the load factor (COUNT / capacity) is less than 0.25
+ *  - there are more than MIN_SPARSE_INDEX slots total and the load factor
+ *    (COUNT / capacity) is less than 0.25
  *  - a property is set that is not indexed (and not "length")
  *  - a property is defined that has non-default property attributes.
  *
  * Dense arrays do not track property creation order, so unlike other native
  * objects and slow arrays, enumerating an array does not necessarily visit the
  * properties in the order they were created.  We could instead maintain the
  * scope to track property enumeration order, but still use the fast slot
  * access.  That would have the same memory cost as just using a
@@ -644,16 +645,19 @@ array_length_setter(JSContext *cx, JSObj
 
     if (oldlen == newlen)
         return true;
 
     vp->setNumber(newlen);
     if (oldlen < newlen)
         return obj->setArrayLength(cx, newlen);
 
+    if (!cx->markTypeArrayShrank(obj->getType()))
+        return false;
+
     if (obj->isDenseArray()) {
         /*
          * Don't reallocate if we're not actually shrinking our slots. If we do
          * shrink slots here, shrink the initialized length too.  This permits us
          * us to disregard length when reading from arrays as long we are within
          * the initialized capacity.
          */
         jsuint oldcap = obj->getDenseArrayCapacity();
@@ -1395,17 +1399,17 @@ array_toLocaleString(JSContext *cx, uint
      *  locale-specific version.
      */
     return array_toString_sub(cx, obj, JS_TRUE, NULL, vp);
 }
 
 static inline bool
 InitArrayTypes(JSContext *cx, TypeObject *type, const Value *vector, unsigned count)
 {
-    if (cx->typeInferenceEnabled() && !type->unknownProperties) {
+    if (cx->typeInferenceEnabled() && !type->unknownProperties()) {
         AutoEnterTypeInference enter(cx);
 
         TypeSet *types = type->getProperty(cx, JSID_VOID, true);
         if (!types)
             return JS_FALSE;
 
         for (unsigned i = 0; i < count; i++) {
             if (vector[i].isMagic(JS_ARRAY_HOLE))
@@ -3430,17 +3434,17 @@ array_TypeNew(JSContext *cx, JSTypeFunct
     }
 
     TypeObject *object = site->getInitObject(cx, true);
     if (!object)
         return;
     if (site->returnTypes)
         site->returnTypes->addType(cx, (jstype) object);
 
-    if (object->unknownProperties)
+    if (object->unknownProperties())
         return;
 
     TypeSet *indexTypes = object->getProperty(cx, JSID_VOID, true);
     if (!indexTypes)
         return;
 
     /*
      * Ignore the case where the call is passed a single argument. This is
--- a/js/src/jscntxt.h
+++ b/js/src/jscntxt.h
@@ -2063,17 +2063,17 @@ struct JSContext
     /*
      * The allocation code calls the function to indicate either OOM failure
      * when p is null or that a memory pressure counter has reached some
      * threshold when p is not null. The function takes the pointer and not
      * a boolean flag to minimize the amount of code in its inlined callers.
      */
     JS_FRIEND_API(void) checkMallocGCPressure(void *p);
 
-public:
+  public:
 
     inline bool typeInferenceEnabled();
 
     /* Make a type function or object with the specified name. */
     js::types::TypeFunction *newTypeFunction(const char *name, JSObject *proto);
     js::types::TypeObject   *newTypeObject(const char *name, JSObject *proto);
 
     /* Make a type object whose name is that of base followed by postfix. */
@@ -2115,29 +2115,39 @@ public:
     inline js::types::TypeObject *getTypeEmpty();
 
     /* Alias two properties in the type information for obj. */
     inline bool aliasTypeProperties(js::types::TypeObject *obj, jsid first, jsid second);
 
     /* Mark an array type as being not packed and, possibly, not dense. */
     inline bool markTypeArrayNotPacked(js::types::TypeObject *obj, bool notDense);
 
+    /* Mark an array type as having had its length shrink dynamically. */
+    inline bool markTypeArrayShrank(js::types::TypeObject *obj);
+
     /* Mark a function as being uninlineable (its .arguments property has been accessed). */
     inline bool markTypeFunctionUninlineable(js::types::TypeObject *obj);
 
     /* Monitor all properties of a type object as unknown. */
     inline bool markTypeObjectUnknownProperties(js::types::TypeObject *obj);
 
+    /* Mark a type as possibly having special equality hooks. */
+    inline bool markTypeObjectHasSpecialEquality(js::types::TypeObject *obj);
+
     /*
      * For an array or object which has not yet escaped and been referenced elsewhere,
      * pick a new type based on the object's current contents.
      */
     inline bool fixArrayType(JSObject *obj);
     inline bool fixObjectType(JSObject *obj);
 
+  private:
+
+    inline bool addTypeFlags(js::types::TypeObject *obj, js::types::TypeObjectFlags flags);
+
 }; /* struct JSContext */
 
 #ifdef JS_THREADSAFE
 # define JS_THREAD_ID(cx)       ((cx)->thread ? (cx)->thread->id : 0)
 #endif
 
 #if defined JS_THREADSAFE && defined DEBUG
 
--- a/js/src/jsfun.cpp
+++ b/js/src/jsfun.cpp
@@ -2926,17 +2926,17 @@ js_CloneFunctionObject(JSContext *cx, JS
 #ifdef CHECK_SCRIPT_OWNER
             cfun->script()->owner = NULL;
 #endif
             js_CallNewScriptHook(cx, cfun->script(), cfun);
         } else {
             TypeFunction *type = cx->newTypeFunction("ClonedFunction", clone->getProto());
             if (!type || !clone->setTypeAndUniqueShape(cx, type))
                 return NULL;
-            if (fun->getType()->unknownProperties) {
+            if (fun->getType()->unknownProperties()) {
                 if (!cx->markTypeObjectUnknownProperties(type))
                     return NULL;
             } else {
                 type->handler = fun->getType()->asFunction()->handler;
             }
         }
     }
     return clone;
--- a/js/src/jsinfer.cpp
+++ b/js/src/jsinfer.cpp
@@ -209,44 +209,38 @@ TypeSetMatches(JSContext *cx, TypeSet *t
         return true;
 
     /*
      * If this is a type for an object with unknown properties, match any object
      * in the type set which also has unknown properties. This avoids failure
      * on objects whose prototype (and thus type) changes dynamically, which will
      * mark the old and new type objects as unknown.
      */
-    if (js::types::TypeIsObject(type) && ((js::types::TypeObject*)type)->unknownProperties) {
-        if (types->objectCount >= 2) {
-            unsigned objectCapacity = HashSetCapacity(types->objectCount);
-            for (unsigned i = 0; i < objectCapacity; i++) {
-                TypeObject *object = types->objectSet[i];
-                if (object && object->unknownProperties)
-                    return true;
-            }
-        } else if (types->objectCount == 1) {
-            TypeObject *object = (TypeObject *) types->objectSet;
-            if (object->unknownProperties)
+    if (TypeIsObject(type) && ((TypeObject*)type)->unknownProperties()) {
+        unsigned count = types->getObjectCount();
+        for (unsigned i = 0; i < count; i++) {
+            TypeObject *object = types->getObject(i);
+            if (object && object->unknownProperties())
                 return true;
         }
     }
 
     return false;
 }
 
 bool
 TypeHasProperty(JSContext *cx, TypeObject *obj, jsid id, const Value &value)
 {
     /*
      * Check the correctness of the type information in the object's property
      * against an actual value. Note that we are only checking the .types set,
      * not the .ownTypes set, and could miss cases where a type set is missing
      * entries from its ownTypes set when they are shadowed by a prototype property.
      */
-    if (cx->typeInferenceEnabled() && !obj->unknownProperties && !value.isUndefined()) {
+    if (cx->typeInferenceEnabled() && !obj->unknownProperties() && !value.isUndefined()) {
         id = MakeTypeId(cx, id);
 
         /* Watch for properties which inference does not monitor. */
         if (id == id___proto__(cx) || id == id_constructor(cx) || id == id_caller(cx))
             return true;
 
         /*
          * If we called in here while resolving a type constraint, we may be in the
@@ -415,26 +409,21 @@ TypeSet::add(JSContext *cx, TypeConstrai
         return;
     }
 
     for (jstype type = TYPE_UNDEFINED; type <= TYPE_STRING; type++) {
         if (typeFlags & (1 << type))
             cx->compartment->types.addPending(cx, constraint, this, type);
     }
 
-    if (objectCount >= 2) {
-        unsigned objectCapacity = HashSetCapacity(objectCount);
-        for (unsigned i = 0; i < objectCapacity; i++) {
-            TypeObject *object = objectSet[i];
-            if (object)
-                cx->compartment->types.addPending(cx, constraint, this, (jstype) object);
-        }
-    } else if (objectCount == 1) {
-        TypeObject *object = (TypeObject*) objectSet;
-        cx->compartment->types.addPending(cx, constraint, this, (jstype) object);
+    unsigned count = getObjectCount();
+    for (unsigned i = 0; i < count; i++) {
+        TypeObject *object = getObject(i);
+        if (object)
+            cx->compartment->types.addPending(cx, constraint, this, (jstype) object);
     }
 
     cx->compartment->types.resolvePending(cx);
 }
 
 void
 TypeSet::print(JSContext *cx)
 {
@@ -457,26 +446,21 @@ TypeSet::print(JSContext *cx)
     if (typeFlags & TYPE_FLAG_DOUBLE)
         printf(" float");
     if (typeFlags & TYPE_FLAG_STRING)
         printf(" string");
 
     if (objectCount) {
         printf(" object[%u]", objectCount);
 
-        if (objectCount >= 2) {
-            unsigned objectCapacity = HashSetCapacity(objectCount);
-            for (unsigned i = 0; i < objectCapacity; i++) {
-                TypeObject *object = objectSet[i];
-                if (object)
-                    printf(" %s", object->name());
-            }
-        } else if (objectCount == 1) {
-            TypeObject *object = (TypeObject*) objectSet;
-            printf(" %s", object->name());
+        unsigned count = getObjectCount();
+        for (unsigned i = 0; i < count; i++) {
+            TypeObject *object = getObject(i);
+            if (object)
+                printf(" %s", object->name());
         }
     }
 }
 
 class TypeConstraintInput : public TypeConstraint
 {
 public:
     TypeConstraintInput(JSScript *script)
@@ -841,17 +825,17 @@ PropertyAccess(JSContext *cx, JSScript *
         if (assign)
             cx->compartment->types.monitorBytecode(cx, script, pc - script->code);
         else
             target->addType(cx, TYPE_UNKNOWN);
         return;
     }
 
     /* Reads from objects with unknown properties are unknown, writes to such objects are ignored. */
-    if (object->unknownProperties) {
+    if (object->unknownProperties()) {
         if (!assign)
             target->addType(cx, TYPE_UNKNOWN);
         return;
     }
 
     /* Capture the effects of a standard property access. */
     if (target) {
         TypeSet *types = object->getProperty(cx, id, assign);
@@ -898,17 +882,17 @@ TypeConstraintNewObject::newType(JSConte
 {
     if (type == TYPE_UNKNOWN) {
         target->addType(cx, TYPE_UNKNOWN);
         return;
     }
 
     if (TypeIsObject(type)) {
         TypeObject *object = (TypeObject *) type;
-        if (object->unknownProperties) {
+        if (object->unknownProperties()) {
             target->addType(cx, TYPE_UNKNOWN);
         } else {
             TypeSet *newTypes = object->getProperty(cx, JSID_EMPTY, true);
             if (!newTypes)
                 return;
             newTypes->addMonitorRead(cx, script, target);
         }
     } else if (!fun->script) {
@@ -941,17 +925,17 @@ TypeConstraintCall::newType(JSContext *c
         return;
     }
 
     if (!TypeIsObject(type))
         return;
 
     /* Get the function being invoked. */
     TypeObject *object = (TypeObject*) type;
-    if (object->unknownProperties) {
+    if (object->unknownProperties()) {
         /* Unknown return value for calls on generic objects. */
         cx->compartment->types.monitorBytecode(cx, script, pc - script->code);
         return;
     }
     if (!object->isFunction) {
         /*
          * If a call on a non-function actually occurs, the call's result
          * should be marked as unknown.
@@ -1065,34 +1049,34 @@ TypeConstraintArith::newType(JSContext *
         /*
          * Addition operation, consider these cases:
          *   {int,bool} x {int,bool} -> int
          *   double x {int,bool,double} -> double
          *   string x any -> string
          */
         switch (type) {
           case TYPE_DOUBLE:
-            if (other->typeFlags & (TYPE_FLAG_UNDEFINED | TYPE_FLAG_NULL |
-                                    TYPE_FLAG_INT32 | TYPE_FLAG_DOUBLE | TYPE_FLAG_BOOLEAN) ||
-                other->objectCount != 0) {
+            if (other->hasAnyFlag(TYPE_FLAG_UNDEFINED | TYPE_FLAG_NULL |
+                                  TYPE_FLAG_INT32 | TYPE_FLAG_DOUBLE | TYPE_FLAG_BOOLEAN) ||
+                other->getObjectCount() != 0) {
                 target->addType(cx, TYPE_DOUBLE);
             }
             break;
           case TYPE_STRING:
             target->addType(cx, TYPE_STRING);
             break;
           case TYPE_UNKNOWN:
             target->addType(cx, TYPE_UNKNOWN);
           default:
-            if (other->typeFlags & (TYPE_FLAG_UNDEFINED | TYPE_FLAG_NULL |
-                                    TYPE_FLAG_INT32 | TYPE_FLAG_BOOLEAN) ||
-                other->objectCount != 0) {
+            if (other->hasAnyFlag(TYPE_FLAG_UNDEFINED | TYPE_FLAG_NULL |
+                                  TYPE_FLAG_INT32 | TYPE_FLAG_BOOLEAN) ||
+                other->getObjectCount() != 0) {
                 target->addType(cx, TYPE_INT32);
             }
-            if (other->typeFlags & TYPE_FLAG_DOUBLE)
+            if (other->hasAnyFlag(TYPE_FLAG_DOUBLE))
                 target->addType(cx, TYPE_DOUBLE);
             break;
         }
     } else {
         switch (type) {
           case TYPE_DOUBLE:
             target->addType(cx, TYPE_DOUBLE);
             break;
@@ -1324,17 +1308,17 @@ public:
 
     void newType(JSContext *cx, TypeSet *source, jstype type)
     {
         if (typeUnknown)
             return;
 
         if (type != TYPE_UNKNOWN && TypeIsObject(type)) {
             /* Ignore new objects when the type set already has other objects. */
-            if (source->objectCount >= 2)
+            if (source->getObjectCount() >= 2)
                 return;
         }
 
         typeUnknown = true;
         cx->compartment->types.addPendingRecompile(cx, script);
     }
 };
 
@@ -1389,29 +1373,35 @@ ObjectKindPair(ObjectKind v0, ObjectKind
 static inline ObjectKind
 CombineObjectKind(TypeObject *object, ObjectKind kind)
 {
     /*
      * All type objects with unknown properties are considered interchangeable
      * with one another, as they can be freely exchanged in type sets to handle
      * objects whose __proto__ has been changed.
      */
-    if (object->unknownProperties || object->hasSpecialEquality || kind == OBJECT_UNKNOWN)
+    if (object->unknownProperties() || kind == OBJECT_UNKNOWN ||
+        object->hasFlags(OBJECT_FLAG_SPECIAL_EQUALITY)) {
         return OBJECT_UNKNOWN;
+    }
+
+    bool inlineable = !object->hasFlags(OBJECT_FLAG_UNINLINEABLE);
+    bool packed = !object->hasFlags(OBJECT_FLAG_NON_PACKED_ARRAY);
+    bool dense = !object->hasFlags(OBJECT_FLAG_NON_DENSE_ARRAY);
+
+    JS_ASSERT_IF(packed, dense);
 
     ObjectKind nkind;
-    if (object->isFunction && object->asFunction()->script && !object->isUninlineable)
+    if (object->isFunction && object->asFunction()->script && inlineable)
         nkind = OBJECT_INLINEABLE_FUNCTION;
     else if (object->isFunction && object->asFunction()->script)
         nkind = OBJECT_SCRIPTED_FUNCTION;
-    else if (object->isFunction)
-        nkind = OBJECT_NATIVE_FUNCTION;
-    else if (object->isPackedArray)
+    else if (packed)
         nkind = OBJECT_PACKED_ARRAY;
-    else if (object->isDenseArray)
+    else if (dense)
         nkind = OBJECT_DENSE_ARRAY;
     else
         nkind = OBJECT_NO_SPECIAL_EQUALITY;
 
     if (kind == nkind || kind == OBJECT_NONE)
         return nkind;
 
     if (ObjectKindPair(kind, nkind, OBJECT_INLINEABLE_FUNCTION, OBJECT_SCRIPTED_FUNCTION))
@@ -1429,21 +1419,27 @@ class TypeConstraintFreezeObjectKind : p
 public:
     TypeObject *object;
 
     /*
      * Kind being specialized by the parent FreezeObjectConstraint. This may
      * have already changed since this constraint was created.
      */
     ObjectKind *pkind;
+    ObjectKind localKind;
 
     TypeConstraintFreezeObjectKind(TypeObject *object, ObjectKind *pkind, JSScript *script)
         : TypeConstraint("freezeObjectKind", script), object(object), pkind(pkind)
     {}
 
+    TypeConstraintFreezeObjectKind(TypeObject *object, ObjectKind localKind, JSScript *script)
+        : TypeConstraint("freezeObjectKind", script), object(object), pkind(&this->localKind),
+          localKind(localKind)
+    {}
+
     void newType(JSContext *cx, TypeSet *source, jstype type) {}
 
     void newObjectState(JSContext *cx)
     {
         ObjectKind nkind = CombineObjectKind(object, *pkind);
         if (nkind != *pkind) {
             *pkind = nkind;
             cx->compartment->types.addPendingRecompile(cx, script);
@@ -1505,51 +1501,65 @@ public:
     }
 };
 
 ObjectKind
 TypeSet::getKnownObjectKind(JSContext *cx)
 {
     ObjectKind kind = OBJECT_NONE;
 
-    if (objectCount >= 2) {
-        unsigned objectCapacity = HashSetCapacity(objectCount);
-        for (unsigned i = 0; i < objectCapacity; i++) {
-            TypeObject *object = objectSet[i];
-            if (object)
-                kind = CombineObjectKind(object, kind);
-        }
-    } else if (objectCount == 1) {
-        kind = CombineObjectKind((TypeObject *) objectSet, kind);
-    } else {
-        return OBJECT_UNKNOWN;
+    unsigned count = getObjectCount();
+    for (unsigned i = 0; i < count; i++) {
+        TypeObject *object = getObject(i);
+        if (object)
+            kind = CombineObjectKind(object, kind);
     }
 
+    if (kind == OBJECT_NONE)
+        kind = OBJECT_UNKNOWN;
+
     if (kind != OBJECT_UNKNOWN) {
         /*
          * Watch for new objects of different kind, and re-traverse existing types
          * in this set to add any needed FreezeArray constraints.
          */
         add(cx, ArenaNew<TypeConstraintFreezeObjectKindSet>(cx->compartment->types.pool, kind,
                                                             cx->compartment->types.compiledScript));
     }
 
     return kind;
 }
 
+ObjectKind
+TypeSet::GetObjectKind(JSContext *cx, TypeObject *object)
+{
+    ObjectKind kind = CombineObjectKind(object, OBJECT_NONE);
+
+    if (kind != OBJECT_UNKNOWN) {
+        TypeSet *elementTypes = object->getProperty(cx, JSID_VOID, false);
+        if (!elementTypes)
+            return OBJECT_UNKNOWN;
+        elementTypes->add(cx,
+            ArenaNew<TypeConstraintFreezeObjectKind>(cx->compartment->types.pool,
+                                                     object, kind, cx->compartment->types.compiledScript), false);
+    }
+
+    return kind;
+}
+
 static inline void
 ObjectStateChange(JSContext *cx, TypeObject *object, bool markingUnknown)
 {
     /* All constraints listening to state changes are on the element types. */
     TypeSet *elementTypes = object->getProperty(cx, JSID_VOID, false);
     if (!elementTypes)
         return;
     if (markingUnknown) {
-        /* Mark as unknown after getting the element types, to avoid assert. */
-        object->unknownProperties = true;
+        /* Mark as unknown after getting the element types, to avoid assertion. */
+        object->flags = OBJECT_FLAG_UNKNOWN_MASK;
     }
     TypeConstraint *constraint = elementTypes->constraintList;
     while (constraint) {
         constraint->newObjectState(cx);
         constraint = constraint->next;
     }
 }
 
@@ -1593,29 +1603,27 @@ TypeCompartment::init(JSContext *cx)
     /*
      * Initialize the empty type object. This is not threaded onto the objects list,
      * will never be collected during GC, and does not have a proto or any properties
      * that need to be marked. It *can* have empty shapes, which are weak references.
      */
 #ifdef DEBUG
     typeEmpty.name_ = JSID_VOID;
 #endif
-    typeEmpty.hasSpecialEquality = true;
-    typeEmpty.isUninlineable = true;
-    typeEmpty.unknownProperties = true;
+    typeEmpty.flags = OBJECT_FLAG_UNKNOWN_MASK;
 
     if (cx && cx->getRunOptions() & JSOPTION_TYPE_INFERENCE)
         inferenceEnabled = true;
 
     JS_InitArenaPool(&pool, "typeinfer", 512, 8, NULL);
 }
 
 TypeObject *
 TypeCompartment::newTypeObject(JSContext *cx, JSScript *script, const char *name,
-                               bool isFunction, JSObject *proto)
+                               bool isFunction, bool isArray, JSObject *proto)
 {
 #ifdef DEBUG
 #if 0
     /* Add a unique counter to the name, to distinguish objects from different globals. */
     static unsigned nameCount = 0;
     unsigned len = strlen(name) + 15;
     char *newName = (char *) alloca(len);
     JS_snprintf(newName, len, "%u:%s", ++nameCount, name);
@@ -1635,17 +1643,28 @@ TypeCompartment::newTypeObject(JSContext
     if (!object)
         return NULL;
 
     TypeObject *&objects = script ? script->typeObjects : this->objects;
     object->next = objects;
     objects = object;
 
     if (!cx->typeInferenceEnabled())
-        object->hasSpecialEquality = true;  /* Avoid syncSpecialEquality assert */
+        object->flags = OBJECT_FLAG_UNKNOWN_MASK;
+    else if (!isArray)
+        object->flags = OBJECT_FLAG_NON_DENSE_ARRAY | OBJECT_FLAG_NON_PACKED_ARRAY;
+
+    if (proto) {
+        /* Thread onto the prototype's list of instance type objects. */
+        TypeObject *prototype = proto->getType();
+        if (prototype->unknownProperties())
+            object->flags = OBJECT_FLAG_UNKNOWN_MASK;
+        object->instanceNext = prototype->instanceList;
+        prototype->instanceList = object;
+    }
 
     return object;
 }
 
 TypeObject *
 TypeCompartment::newInitializerTypeObject(JSContext *cx, JSScript *script,
                                           uint32 offset, bool isArray)
 {
@@ -1655,27 +1674,24 @@ TypeCompartment::newInitializerTypeObjec
     JS_snprintf(name, 40, "#%lu:%lu:%s", script->id(), offset, isArray ? "Array" : "Object");
 #endif
 
     JSObject *proto;
     JSProtoKey key = isArray ? JSProto_Array : JSProto_Object;
     if (!js_GetClassPrototype(cx, script->getGlobal(), key, &proto, NULL))
         return NULL;
 
-    TypeObject *res = newTypeObject(cx, script, name, false, proto);
+    TypeObject *res = newTypeObject(cx, script, name, false, isArray, proto);
     if (!res)
         return NULL;
 
-    if (isArray) {
-        if (!res->unknownProperties)
-            res->isDenseArray = res->isPackedArray = true;
+    if (isArray)
         res->initializerArray = true;
-    } else {
+    else
         res->initializerObject = true;
-    }
     res->initializerOffset = offset;
 
     return res;
 }
 
 static inline jsid
 GetAtomId(JSContext *cx, JSScript *script, const jsbytecode *pc, unsigned offset)
 {
@@ -1847,17 +1863,17 @@ TypeCompartment::dynamicPush(JSContext *
     /*
      * If this script was inlined into a parent, we need to make sure the
      * parent has constraints listening to type changes in this one (it won't
      * necessarily, if we have condensed the constraints but not reanalyzed the
      * parent). The parent is listening for isUninlineable changes on the
      * function, so we can treat this as a state change on the function to
      * trigger any necessary reanalysis.
      */
-    if (script->fun && !script->fun->getType()->unknownProperties)
+    if (script->fun && !script->fun->getType()->unknownProperties())
         ObjectStateChange(cx, script->fun->getType(), false);
 
     /*
      * For inc/dec ops, we need to go back and reanalyze the affected opcode
      * taking the overflow into account. We won't see an explicit adjustment
      * of the type of the thing being inc/dec'ed, nor will adding TYPE_DOUBLE to
      * the pushed value affect that type. We only handle inc/dec operations
      * that do not have an object lvalue; INCNAME/INCPROP/INCELEM and friends
@@ -1870,17 +1886,17 @@ TypeCompartment::dynamicPush(JSContext *
 
         switch (op) {
           case JSOP_INCGNAME:
           case JSOP_DECGNAME:
           case JSOP_GNAMEINC:
           case JSOP_GNAMEDEC: {
             jsid id = GetAtomId(cx, script, pc, 0);
             TypeObject *global = script->getGlobalType();
-            if (!global->unknownProperties) {
+            if (!global->unknownProperties()) {
                 TypeSet *types = global->getProperty(cx, id, true);
                 if (!types)
                     break;
                 types->addType(cx, type);
             }
             break;
           }
 
@@ -2005,17 +2021,17 @@ bool
 TypeCompartment::dynamicAssign(JSContext *cx, JSObject *obj, jsid id, const Value &rval)
 {
     if (obj->isWith())
         obj = js_UnwrapWithObject(cx, obj);
 
     jstype rvtype = GetValueType(cx, rval);
     TypeObject *object = obj->getType();
 
-    if (object->unknownProperties)
+    if (object->unknownProperties())
         return true;
 
     id = MakeTypeId(cx, id);
 
     /*
      * Mark as unknown any object which has had dynamic assignments to __proto__,
      * and any object which has had dynamic assignments to string properties through SETELEM.
      * The latter avoids making large numbers of type properties for hashmap-style objects.
@@ -2051,16 +2067,17 @@ TypeCompartment::monitorBytecode(JSConte
      */
     JSOp op = JSOp(script->code[offset]);
     switch (op) {
       case JSOP_SETNAME:
       case JSOP_SETGNAME:
       case JSOP_SETXMLNAME:
       case JSOP_SETCONST:
       case JSOP_SETELEM:
+      case JSOP_SETHOLE:
       case JSOP_SETPROP:
       case JSOP_SETMETHOD:
       case JSOP_INITPROP:
       case JSOP_INITMETHOD:
       case JSOP_FORPROP:
       case JSOP_FORNAME:
       case JSOP_FORGNAME:
       case JSOP_ENUMELEM:
@@ -2224,23 +2241,21 @@ TypeCompartment::fixArrayType(JSContext 
     ArrayTableKey key;
     key.type = type;
     key.proto = obj->getProto();
     ArrayTypeTable::AddPtr p = arrayTypeTable->lookupForAdd(key);
 
     if (p) {
         obj->setType(p->value);
     } else {
-        TypeObject *objType = newTypeObject(cx, NULL, "TableArray", false, obj->getProto());
+        TypeObject *objType = newTypeObject(cx, NULL, "TableArray", false, true, obj->getProto());
         if (!objType) {
             js_ReportOutOfMemory(cx);
             return false;
         }
-        if (!objType->unknownProperties)
-            objType->isDenseArray = objType->isPackedArray = true;
         obj->setType(objType);
 
         if (!cx->addTypePropertyId(objType, JSID_VOID, type))
             return false;
 
         if (!arrayTypeTable->relookupOrAdd(p, key, objType)) {
             js_ReportOutOfMemory(cx);
             return false;
@@ -2351,17 +2366,17 @@ TypeCompartment::fixObjectType(JSContext
         JSObject *xobj = NewBuiltinClassInstance(cx, &js_ObjectClass,
                                                  (gc::FinalizeKind) obj->finalizeKind());
         if (!xobj) {
             js_ReportOutOfMemory(cx);
             return false;
         }
         AutoObjectRooter xvr(cx, xobj);
 
-        TypeObject *objType = newTypeObject(cx, NULL, "TableObject", false, obj->getProto());
+        TypeObject *objType = newTypeObject(cx, NULL, "TableObject", false, false, obj->getProto());
         if (!objType) {
             js_ReportOutOfMemory(cx);
             return false;
         }
         xobj->setType(objType);
 
         jsid *ids = (jsid *) cx->calloc_(obj->slotSpan() * sizeof(jsid));
         if (!ids)
@@ -2466,26 +2481,21 @@ TypeObject::splicePrototype(JSContext *c
 
     AutoEnterTypeInference enter(cx);
 
     /*
      * Note: we require (but do not assert) that any property in the prototype
      * or its own prototypes must not share a name with a property already
      * added to an instance of this object.
      */
-    if (propertyCount >= 2) {
-        unsigned capacity = HashSetCapacity(propertyCount);
-        for (unsigned i = 0; i < capacity; i++) {
-            Property *prop = propertySet[i];
-            if (prop)
-                getFromPrototypes(cx, prop);
-        }
-    } else if (propertyCount == 1) {
-        Property *prop = (Property *) propertySet;
-        getFromPrototypes(cx, prop);
+    unsigned count = getPropertyCount();
+    for (unsigned i = 0; i < count; i++) {
+        Property *prop = getProperty(i);
+        if (prop)
+            getFromPrototypes(cx, prop);
     }
 
     JS_ALWAYS_TRUE(cx->compartment->types.checkPendingRecompiles(cx));
 }
 
 bool
 TypeObject::addProperty(JSContext *cx, jsid id, Property **pprop)
 {
@@ -2511,124 +2521,98 @@ TypeObject::addProperty(JSContext *cx, j
 
     /* Pull in this property from all prototypes up the chain. */
     getFromPrototypes(cx, base);
 
     return true;
 }
 
 void
-TypeObject::markNotPacked(JSContext *cx, bool notDense)
+TypeObject::setFlags(JSContext *cx, TypeObjectFlags flags)
 {
     JS_ASSERT(cx->compartment->types.inferenceDepth);
-
-    if (notDense) {
-        if (!isDenseArray)
-            return;
-        isDenseArray = false;
-    } else if (!isPackedArray) {
-        return;
-    }
-    isPackedArray = false;
-
-    InferSpew(ISpewOps, "%s: %s", notDense ? "NonDenseArray" : "NonPackedArray", name());
-
-    ObjectStateChange(cx, this, false);
-}
-
-void
-TypeObject::markUninlineable(JSContext *cx)
-{
-    JS_ASSERT(cx->compartment->types.inferenceDepth);
-
-    JS_ASSERT(!isUninlineable);
-    isUninlineable = true;
-
-    InferSpew(ISpewOps, "Uninlineable: %s", name());
+    JS_ASSERT((this->flags & flags) != flags);
+
+    this->flags |= flags;
+
+    InferSpew(ISpewOps, "%s: setFlags %u", name(), flags);
 
     ObjectStateChange(cx, this, false);
 }
 
 void
 TypeObject::markUnknown(JSContext *cx)
 {
-    JS_ASSERT(!unknownProperties);
+    JS_ASSERT(cx->compartment->types.inferenceDepth);
+    JS_ASSERT(!unknownProperties());
 
     InferSpew(ISpewOps, "UnknownProperties: %s", name());
 
-    isDenseArray = false;
-    isPackedArray = false;
-    isUninlineable = true;
-    hasSpecialEquality = true;
-
     ObjectStateChange(cx, this, true);
 
     /* Mark existing instances as unknown. */
 
     TypeObject *instance = instanceList;
     while (instance) {
-        if (!instance->unknownProperties)
+        if (!instance->unknownProperties())
             instance->markUnknown(cx);
         instance = instance->instanceNext;
     }
 
     /*
      * Existing constraints may have already been added to this object, which we need
      * to do the right thing for.  We can't ensure that we will mark all unknown
      * objects before they have been accessed, as the __proto__ of a known object
      * could be dynamically set to an unknown object, and we can decide to ignore
      * properties of an object during analysis (i.e. hashmaps). Adding unknown for
      * any properties accessed already accounts for possible values read from them.
      */
 
-    if (propertyCount >= 2) {
-        unsigned capacity = HashSetCapacity(propertyCount);
-        for (unsigned i = 0; i < capacity; i++) {
-            Property *prop = propertySet[i];
-            if (prop)
-                prop->ownTypes.addType(cx, TYPE_UNKNOWN);
-        }
-    } else if (propertyCount == 1) {
-        Property *prop = (Property *) propertySet;
-        prop->ownTypes.addType(cx, TYPE_UNKNOWN);
+    unsigned count = getPropertyCount();
+    for (unsigned i = 0; i < count; i++) {
+        Property *prop = getProperty(i);
+        if (prop)
+            prop->ownTypes.addType(cx, TYPE_UNKNOWN);
     }
 }
 
 void
 TypeObject::print(JSContext *cx)
 {
     printf("%s : %s", name(), proto ? proto->getType()->name() : "(null)");
 
-    if (unknownProperties)
+    if (unknownProperties()) {
         printf(" unknown");
-    else if (isPackedArray)
-        printf(" packed");
-    else if (isDenseArray)
-        printf(" dense");
+    } else {
+        if (!hasFlags(OBJECT_FLAG_NON_PACKED_ARRAY))
+            printf(" packed");
+        if (!hasFlags(OBJECT_FLAG_NON_DENSE_ARRAY))
+            printf(" dense");
+        if (hasFlags(OBJECT_FLAG_ARRAY_SHRANK))
+            printf(" arrayShrank");
+        if (hasFlags(OBJECT_FLAG_UNINLINEABLE))
+            printf(" uninlineable");
+        if (hasFlags(OBJECT_FLAG_SPECIAL_EQUALITY))
+            printf(" specialEquality");
+    }
 
     if (propertyCount == 0) {
         printf(" {}\n");
         return;
     }
 
     printf(" {");
 
-    if (propertyCount >= 2) {
-        unsigned capacity = HashSetCapacity(propertyCount);
-        for (unsigned i = 0; i < capacity; i++) {
-            Property *prop = propertySet[i];
-            if (prop) {
-                printf("\n    %s:", TypeIdString(prop->id));
-                prop->ownTypes.print(cx);
-            }
+    unsigned count = getPropertyCount();
+    for (unsigned i = 0; i < count; i++) {
+        Property *prop = getProperty(i);
+        if (prop) {
+            printf("\n    %s:", TypeIdString(prop->id));
+            prop->ownTypes.print(cx);
         }
-    } else if (propertyCount == 1) {
-        Property *prop = (Property *) propertySet;
-        printf("\n    %s:", TypeIdString(prop->id));
-        prop->ownTypes.print(cx);
     }
 
     printf("\n}\n");
 }
 
 /////////////////////////////////////////////////////////////////////
 // TypeScript
 /////////////////////////////////////////////////////////////////////
@@ -3173,16 +3157,17 @@ AnalyzeBytecode(JSContext *cx, AnalyzeSt
 
         if (op == JSOP_CALLELEM)
             state.popped(1).types->addFilterPrimitives(cx, script, &pushed[1], true);
         if (CheckNextTest(pc))
             pushed[0].addType(cx, TYPE_UNDEFINED);
         break;
 
       case JSOP_SETELEM:
+      case JSOP_SETHOLE:
         state.popped(2).types->addSetProperty(cx, script, pc, state.popped(0).types, JSID_VOID);
         state.popped(0).types->addSubset(cx, script, &pushed[0]);
         break;
 
       case JSOP_INCELEM:
       case JSOP_DECELEM:
       case JSOP_ELEMINC:
       case JSOP_ELEMDEC:
@@ -3292,29 +3277,29 @@ AnalyzeBytecode(JSContext *cx, AnalyzeSt
       case JSOP_ENDINIT:
         break;
 
       case JSOP_INITELEM:
         initializer = state.popped(2).initializer;
         JS_ASSERT((initializer != NULL) == script->compileAndGo);
         if (initializer) {
             pushed[0].addType(cx, (jstype) initializer);
-            if (!initializer->unknownProperties) {
+            if (!initializer->unknownProperties()) {
                 /*
                  * Assume the initialized element is an integer. INITELEM can be used
                  * for doubles which don't map to the JSID_VOID property, which must
                  * be caught with dynamic monitoring.
                  */
                 TypeSet *types = initializer->getProperty(cx, JSID_VOID, true);
                 if (!types)
                     return false;
                 if (state.hasGetSet)
                     types->addType(cx, TYPE_UNKNOWN);
                 else if (state.hasHole)
-                    initializer->markNotPacked(cx, false);
+                    cx->markTypeArrayNotPacked(initializer, false);
                 else
                     state.popped(0).types->addSubset(cx, script, types);
             }
         } else {
             pushed[0].addType(cx, TYPE_UNKNOWN);
         }
         state.hasGetSet = false;
         state.hasHole = false;
@@ -3330,17 +3315,17 @@ AnalyzeBytecode(JSContext *cx, AnalyzeSt
         break;
 
       case JSOP_INITPROP:
       case JSOP_INITMETHOD:
         initializer = state.popped(1).initializer;
         JS_ASSERT((initializer != NULL) == script->compileAndGo);
         if (initializer) {
             pushed[0].addType(cx, (jstype) initializer);
-            if (!initializer->unknownProperties) {
+            if (!initializer->unknownProperties()) {
                 jsid id = GetAtomId(cx, script, pc, 0);
                 TypeSet *types = initializer->getProperty(cx, id, true);
                 if (!types)
                     return false;
                 if (id == id___proto__(cx) || id == id_prototype(cx))
                     cx->compartment->types.monitorBytecode(cx, script, offset);
                 else if (state.hasGetSet)
                     types->addType(cx, TYPE_UNKNOWN);
@@ -3376,17 +3361,17 @@ AnalyzeBytecode(JSContext *cx, AnalyzeSt
       case JSOP_MOREITER:
         state.popped(0).types->addSubset(cx, script, &pushed[0]);
         pushed[1].addType(cx, TYPE_BOOLEAN);
         break;
 
       case JSOP_FORGNAME: {
         jsid id = GetAtomId(cx, script, pc, 0);
         TypeObject *global = script->getGlobalType();
-        if (!global->unknownProperties) {
+        if (!global->unknownProperties()) {
             TypeSet *types = global->getProperty(cx, id, true);
             if (!types)
                 return false;
             SetForTypes(cx, script, state, types);
         }
         break;
       }
 
@@ -3710,17 +3695,17 @@ AnalyzeScriptNew(JSContext *cx, JSScript
 {
     JS_ASSERT(script->calledWithNew && script->fun);
 
     /*
      * Compute the 'this' type when called with 'new'. We do not distinguish regular
      * from 'new' calls to the function.
      */
 
-    if (script->fun->getType()->unknownProperties ||
+    if (script->fun->getType()->unknownProperties() ||
         script->fun->isFunctionPrototype() ||
         !script->compileAndGo) {
         script->thisTypes()->addType(cx, TYPE_UNKNOWN);
         return;
     }
 
     TypeFunction *funType = script->fun->getType()->asFunction();
     TypeSet *prototypeTypes = funType->getProperty(cx, id_prototype(cx), false);
@@ -3855,35 +3840,33 @@ TypeScript::print(JSContext *cx, JSScrip
 
         unsigned defCount = analyze::GetDefCount(script, offset);
         if (!defCount)
             continue;
 
         for (unsigned i = 0; i < defCount; i++) {
             TypeSet *types = &array[i];
 
-            /* TODO: distinguish direct and indirect call sites. */
-            unsigned typeCount = types->objectCount ? 1 : 0;
+            unsigned typeCount = types->getObjectCount() ? 1 : 0;
             for (jstype type = TYPE_UNDEFINED; type <= TYPE_STRING; type++) {
-                if (types->typeFlags & (1 << type))
+                if (types->hasAnyFlag(1 << type))
                     typeCount++;
             }
 
             /*
              * Adjust the type counts for floats: values marked as floats
              * are also marked as ints by the inference, but for counting
              * we don't consider these to be separate types.
              */
-            if (types->typeFlags & TYPE_FLAG_DOUBLE) {
-                JS_ASSERT(types->typeFlags & TYPE_FLAG_INT32);
+            if (types->hasAnyFlag(TYPE_FLAG_DOUBLE)) {
+                JS_ASSERT(types->hasAnyFlag(TYPE_FLAG_INT32));
                 typeCount--;
             }
 
-            if ((types->typeFlags & TYPE_FLAG_UNKNOWN) ||
-                typeCount > TypeCompartment::TYPE_COUNT_LIMIT) {
+            if (types->unknown() || typeCount > TypeCompartment::TYPE_COUNT_LIMIT) {
                 compartment->typeCountOver++;
             } else if (typeCount == 0) {
                 /* Ignore values without types, this may be unreached code. */
             } else {
                 compartment->typeCounts[typeCount-1]++;
             }
         }
     }
@@ -3948,35 +3931,36 @@ TypeScript::print(JSContext *cx, JSScrip
 
 /////////////////////////////////////////////////////////////////////
 // JSContext
 /////////////////////////////////////////////////////////////////////
 
 js::types::TypeFunction *
 JSContext::newTypeFunction(const char *name, JSObject *proto)
 {
-    return (js::types::TypeFunction *) compartment->types.newTypeObject(this, NULL, name, true, proto);
+    return (js::types::TypeFunction *)
+        compartment->types.newTypeObject(this, NULL, name, true, false, proto);
 }
 
 js::types::TypeObject *
 JSContext::newTypeObject(const char *name, JSObject *proto)
 {
-    return compartment->types.newTypeObject(this, NULL, name, false, proto);
+    return compartment->types.newTypeObject(this, NULL, name, false, false, proto);
 }
 
 js::types::TypeObject *
 JSContext::newTypeObject(const char *base, const char *postfix, JSObject *proto, bool isFunction)
 {
     char *name = NULL;
 #ifdef DEBUG
     unsigned len = strlen(base) + strlen(postfix) + 5;
     name = (char *)alloca(len);
     JS_snprintf(name, len, "%s:%s", base, postfix);
 #endif
-    return compartment->types.newTypeObject(this, NULL, name, isFunction, proto);
+    return compartment->types.newTypeObject(this, NULL, name, isFunction, false, proto);
 }
 
 /////////////////////////////////////////////////////////////////////
 // JSScript
 /////////////////////////////////////////////////////////////////////
 
 /*
  * Returns true if we don't expect to compute the correct types for some value
@@ -4120,28 +4104,27 @@ JSScript::typeCheckBytecode(JSContext *c
                                    id(), pc - code, i, js::types::TypeString(type));
         }
 
         if (js::types::TypeIsObject(type)) {
             JS_ASSERT(val.isObject());
             JSObject *obj = &val.toObject();
             js::types::TypeObject *object = (js::types::TypeObject *) type;
 
-            if (object->unknownProperties) {
-                JS_ASSERT(!object->isDenseArray);
+            if (object->unknownProperties())
                 continue;
-            }
 
             /* Make sure information about the array status of this object is right. */
-            JS_ASSERT_IF(object->isPackedArray, object->isDenseArray);
-            if (object->isDenseArray) {
-                if (!obj->isDenseArray() ||
-                    (object->isPackedArray && !obj->isPackedDenseArray())) {
+            bool dense = !object->hasFlags(js::types::OBJECT_FLAG_NON_DENSE_ARRAY);
+            bool packed = !object->hasFlags(js::types::OBJECT_FLAG_NON_PACKED_ARRAY);
+            JS_ASSERT_IF(packed, dense);
+            if (dense) {
+                if (!obj->isDenseArray() || (packed && !obj->isPackedDenseArray())) {
                     js::types::TypeFailure(cx, "Object not %s array at #%u:%05u popped %u: %s",
-                        object->isPackedArray ? "packed" : "dense",
+                        packed ? "packed" : "dense",
                         id(), pc - code, i, object->name());
                 }
             }
         }
     }
 }
 
 #endif
@@ -4154,17 +4137,17 @@ void
 JSObject::makeNewType(JSContext *cx)
 {
     JS_ASSERT(!newType);
 
     js::types::TypeObject *type = cx->newTypeObject(getType()->name(), "new", this);
     if (!type)
         return;
 
-    if (cx->typeInferenceEnabled() && !getType()->unknownProperties) {
+    if (cx->typeInferenceEnabled() && !getType()->unknownProperties()) {
         js::types::AutoEnterTypeInference enter(cx);
 
         /* Update the possible 'new' types for all prototype objects sharing the same type object. */
         js::types::TypeSet *types = getType()->getProperty(cx, JSID_EMPTY, true);
         if (types)
             types->addType(cx, (js::types::jstype) type);
 
         if (!cx->compartment->types.checkPendingRecompiles(cx))
@@ -4193,26 +4176,21 @@ types::TypeObject::trace(JSTracer *trc)
      */
     if (trc->context->runtime->gcMarkAndSweep)
         marked = true;
 
 #ifdef DEBUG
     gc::MarkId(trc, name_, "type_name");
 #endif
 
-    if (propertyCount >= 2) {
-        unsigned capacity = HashSetCapacity(propertyCount);
-        for (unsigned i = 0; i < capacity; i++) {
-            Property *prop = propertySet[i];
-            if (prop)
-                gc::MarkId(trc, prop->id, "type_prop");
-        }
-    } else if (propertyCount == 1) {
-        Property *prop = (Property *) propertySet;
-        gc::MarkId(trc, prop->id, "type_prop");
+    unsigned count = getPropertyCount();
+    for (unsigned i = 0; i < count; i++) {
+        Property *prop = getProperty(i);
+        if (prop)
+            gc::MarkId(trc, prop->id, "type_prop");
     }
 
     if (emptyShapes) {
         int count = gc::FINALIZE_OBJECT_LAST - gc::FINALIZE_OBJECT0 + 1;
         for (int i = 0; i < count; i++) {
             if (emptyShapes[i])
                 MarkShape(trc, emptyShapes[i], "empty_shape");
         }
@@ -4226,18 +4204,18 @@ types::TypeObject::trace(JSTracer *trc)
 }
 
 /*
  * Condense any constraints on a type set which were generated during analysis
  * of a script, and sweep all type objects and references to type objects
  * which no longer exist.
  */
 void
-CondenseSweepTypeSet(JSContext *cx, TypeCompartment *compartment,
-                     HashSet<JSScript*> *pcondensed, TypeSet *types)
+TypeSet::CondenseSweepTypeSet(JSContext *cx, TypeCompartment *compartment,
+                              HashSet<JSScript*> *pcondensed, TypeSet *types)
 {
     /*
      * This function is called from GC, and cannot malloc any data that could
      * trigger a reentrant GC. The only allocation that can happen here is
      * the construction of condensed constraints and tables for hash sets.
      * Both of these use off-the-books malloc rather than cx->malloc, and thus
      * do not contribute towards the runtime's overall malloc bytes.
      */
@@ -4252,17 +4230,17 @@ CondenseSweepTypeSet(JSContext *cx, Type
                 /*
                  * If the object has unknown properties, instead of removing it
                  * replace it with the compartment's empty type object. This is
                  * needed to handle mutable __proto__ --- the type object in
                  * the set may no longer be used but there could be a JSObject
                  * which originally had the type and was changed to a different
                  * type object with unknown properties.
                  */
-                if (object->unknownProperties)
+                if (object->unknownProperties())
                     types->objectSet[i] = &compartment->typeEmpty;
                 else
                     types->objectSet[i] = NULL;
                 removed = true;
             }
         }
         if (removed) {
             /* Reconstruct the type set to re-resolve hash collisions. */
@@ -4278,17 +4256,17 @@ CondenseSweepTypeSet(JSContext *cx, Type
                         *pentry = object;
                 }
             }
             cx->free_(oldArray);
         }
     } else if (types->objectCount == 1) {
         TypeObject *object = (TypeObject*) types->objectSet;
         if (!object->marked) {
-            if (object->unknownProperties) {
+            if (object->unknownProperties()) {
                 types->objectSet = (TypeObject**) &compartment->typeEmpty;
             } else {
                 types->objectSet = NULL;
                 types->objectCount = 0;
             }
         }
     }
 
@@ -4386,29 +4364,23 @@ CondenseTypeObjectList(JSContext *cx, Ty
              */
             object = object->next;
             continue;
         }
 
         PruneInstanceObjects(object);
 
         /* Condense type sets for all properties of the object. */
-        if (object->propertyCount >= 2) {
-            unsigned capacity = HashSetCapacity(object->propertyCount);
-            for (unsigned i = 0; i < capacity; i++) {
-                Property *prop = object->propertySet[i];
-                if (prop) {
-                    CondenseSweepTypeSet(cx, compartment, pcondensed, &prop->types);
-                    CondenseSweepTypeSet(cx, compartment, pcondensed, &prop->ownTypes);
-                }
+        unsigned count = object->getPropertyCount();
+        for (unsigned i = 0; i < count; i++) {
+            Property *prop = object->getProperty(i);
+            if (prop) {
+                TypeSet::CondenseSweepTypeSet(cx, compartment, pcondensed, &prop->types);
+                TypeSet::CondenseSweepTypeSet(cx, compartment, pcondensed, &prop->ownTypes);
             }
-        } else if (object->propertyCount == 1) {
-            Property *prop = (Property *) object->propertySet;
-            CondenseSweepTypeSet(cx, compartment, pcondensed, &prop->types);
-            CondenseSweepTypeSet(cx, compartment, pcondensed, &prop->ownTypes);
         }
 
         object = object->next;
     }
 }
 
 void
 TypeCompartment::condense(JSContext *cx)
@@ -4435,28 +4407,24 @@ SweepTypeObjectList(JSContext *cx, TypeO
         if (object->marked) {
             object->marked = false;
             pobject = &object->next;
         } else {
             if (object->emptyShapes)
                 cx->free_(object->emptyShapes);
             *pobject = object->next;
 
-            if (object->propertyCount >= 2) {
-                unsigned capacity = HashSetCapacity(object->propertyCount);
-                for (unsigned i = 0; i < capacity; i++) {
-                    Property *prop = object->propertySet[i];
-                    if (prop)
-                        DestroyProperty(cx, prop);
-                }
+            unsigned count = object->getPropertyCount();
+            for (unsigned i = 0; i < count; i++) {
+                Property *prop = object->getProperty(i);
+                if (prop)
+                    DestroyProperty(cx, prop);
+            }
+            if (count >= 2)
                 cx->free_(object->propertySet);
-            } else if (object->propertyCount == 1) {
-                Property *prop = (Property *) object->propertySet;
-                DestroyProperty(cx, prop);
-            }
 
             cx->delete_(object);
         }
     }
 }
 
 void
 TypeCompartment::sweep(JSContext *cx)
@@ -4552,27 +4520,27 @@ JSScript::condenseTypes(JSContext *cx)
             (u.object && IsAboutToBeFinalized(cx, u.object)) ||
             (fun && IsAboutToBeFinalized(cx, fun))) {
             for (unsigned i = 0; i < num; i++)
                 varTypes[i].destroy(cx);
             cx->free_(varTypes);
             varTypes = NULL;
         } else {
             for (unsigned i = 0; i < num; i++)
-                js::types::CondenseSweepTypeSet(cx, &compartment->types, pcondensed, &varTypes[i]);
+                js::types::TypeSet::CondenseSweepTypeSet(cx, &compartment->types, pcondensed, &varTypes[i]);
         }
     }
 
     js::types::TypeResult **presult = &typeResults;
     while (*presult) {
         js::types::TypeResult *result = *presult;
         if (js::types::TypeIsObject(result->type)) {
             js::types::TypeObject *object = (js::types::TypeObject *) result->type;
             if (!object->marked) {
-                if (!object->unknownProperties) {
+                if (!object->unknownProperties()) {
                     *presult = result->next;
                     cx->free_(result);
                     continue;
                 } else {
                     result->type = (js::types::jstype) &compartment->types.typeEmpty;
                 }
             }
         }
--- a/js/src/jsinfer.h
+++ b/js/src/jsinfer.h
@@ -170,18 +170,17 @@ public:
 #endif
     }
 
     /* Register a new type for the set this constraint is listening to. */
     virtual void newType(JSContext *cx, TypeSet *source, jstype type) = 0;
 
     /*
      * For constraints attached to the index type set of an object (JSID_VOID),
-     * mark a change in one of the object's dynamic properties (isDenseArray,
-     * isPackedArray, or unknownProperties).
+     * mark a change in one of the object's dynamic property flags.
      */
     virtual void newObjectState(JSContext *cx) {}
 
     /*
      * Whether this is an input type constraint condensed from the original
      * constraints generated during analysis of the associated script.
      * If this type set changes then the script will be reanalyzed/recompiled
      * should the type set change at all in the future.
@@ -194,36 +193,35 @@ public:
      * properties which are independent of the analysis of any script.
      */
     virtual TypeObject * baseSubset() { return NULL; }
 };
 
 /*
  * Coarse kinds of a set of objects.  These form the following lattice:
  *
- *                    NONE
- *       ___________ /  | \______________
- *      /               |                \
- * PACKED_ARRAY  INLINEABLE_FUNCTION  NATIVE_FUNCTION
- *      |               |                 |
- * DENSE_ARRAY    SCRIPTED_FUNCTION       |
- *      \____________   |   _____________/
- *                   \  |  /
- *             NO_SPECIAL_EQUALITY
- *                      |
- *                   UNKNOWN
+ *            NONE
+ *       ____/    \_____
+ *      /               \
+ * PACKED_ARRAY  INLINEABLE_FUNCTION
+ *     |                 |
+ * DENSE_ARRAY    SCRIPTED_FUNCTION
+ *      \____      _____/
+ *           \    /
+ *     NO_SPECIAL_EQUALITY
+ *              |
+ *           UNKNOWN
  */
 enum ObjectKind {
     OBJECT_NONE,
     OBJECT_UNKNOWN,
     OBJECT_PACKED_ARRAY,
-    OBJECT_DENSE_ARRAY,
+    OBJECT_DENSE_ARRAY,         /* Excludes arrays whose length has shrunk. */
     OBJECT_INLINEABLE_FUNCTION,
     OBJECT_SCRIPTED_FUNCTION,
-    OBJECT_NATIVE_FUNCTION,
     OBJECT_NO_SPECIAL_EQUALITY
 };
 
 /* Coarse flags for the contents of a type set. */
 enum {
     TYPE_FLAG_UNDEFINED = 1 << TYPE_UNDEFINED,
     TYPE_FLAG_NULL      = 1 << TYPE_NULL,
     TYPE_FLAG_BOOLEAN   = 1 << TYPE_BOOLEAN,
@@ -236,52 +234,63 @@ enum {
     /* Flag for type sets which are cleared on GC. */
     TYPE_FLAG_INTERMEDIATE_SET = 0x1000
 };
 
 /* Vector of the above flags. */
 typedef uint32 TypeFlags;
 
 /* Information about the set of types associated with an lvalue. */
-struct TypeSet
+class TypeSet
 {
     /* Flags for the possible coarse types in this set. */
     TypeFlags typeFlags;
 
     /* Possible objects this type set can represent. */
     TypeObject **objectSet;
     unsigned objectCount;
 
+  public:
+
     /* Chain of constraints which propagate changes out from this type set. */
     TypeConstraint *constraintList;
 
     TypeSet()
         : typeFlags(0), objectSet(NULL), objectCount(0), constraintList(NULL)
     {}
 
     void print(JSContext *cx);
 
     void setIntermediate() { typeFlags |= TYPE_FLAG_INTERMEDIATE_SET; }
 
     inline void destroy(JSContext *cx);
 
     /* Whether this set contains a specific type. */
     inline bool hasType(jstype type);
 
+    bool hasAnyFlag(TypeFlags flags) { return typeFlags & flags; }
     bool unknown() { return typeFlags & TYPE_FLAG_UNKNOWN; }
 
     /*
      * Add a type to this set, calling any constraint handlers if this is a new
      * possible type.
      */
     inline void addType(JSContext *cx, jstype type);
 
     /* Add all types in a cloned set to this set. */
     void addTypeSet(JSContext *cx, ClonedTypeSet *types);
 
+    /*
+     * Iterate through the objects in this set. getObjectCount overapproximates
+     * in the hash case (see SET_ARRAY_SIZE in jsinferinlines.h), and getObject
+     * may return NULL.
+     */
+    inline unsigned getObjectCount();
+    inline TypeObject *getObject(unsigned i);
+
     /* Add specific kinds of constraints to this set. */
     inline void add(JSContext *cx, TypeConstraint *constraint, bool callExisting = true);
     void addSubset(JSContext *cx, JSScript *script, TypeSet *target);
     void addGetProperty(JSContext *cx, JSScript *script, const jsbytecode *pc,
                         TypeSet *target, jsid id);
     void addSetProperty(JSContext *cx, JSScript *script, const jsbytecode *pc,
                         TypeSet *target, jsid id);
     void addNewObject(JSContext *cx, JSScript *script, TypeFunction *fun, TypeSet *target);
@@ -313,16 +322,19 @@ struct TypeSet
     void addFreeze(JSContext *cx);
 
     /* Get any type tag which all values in this set must have. */
     JSValueType getKnownTypeTag(JSContext *cx);
 
     /* Get information about the kinds of objects in this type set. */
     ObjectKind getKnownObjectKind(JSContext *cx);
 
+    /* Get the fixed kind of a particular object. */
+    static ObjectKind GetObjectKind(JSContext *cx, TypeObject *object);
+
     /* Whether any objects in this type set have unknown properties. */
     bool hasUnknownProperties(JSContext *cx);
 
     /* Get whether this type set is non-empty. */
     bool knownNonEmpty(JSContext *cx);
 
     /* Get the single value which can appear in this type set, otherwise NULL. */
     JSObject *getSingleton(JSContext *cx);
@@ -331,16 +343,20 @@ struct TypeSet
     void pushAllTypes(JSContext *cx, JSScript *script, const jsbytecode *pc);
 
     /*
      * Clone (possibly NULL) source onto target; if any new types are added to
      * source in the future, the script will be recompiled.
      */
     static void Clone(JSContext *cx, TypeSet *source, ClonedTypeSet *target);
 
+    static void
+    CondenseSweepTypeSet(JSContext *cx, TypeCompartment *compartment,
+                         HashSet<JSScript*> *pcondensed, TypeSet *types);
+
   private:
     inline void markUnknown(JSContext *cx);
 };
 
 /* A type set captured for use by JIT compilers. */
 struct ClonedTypeSet
 {
     TypeFlags typeFlags;
@@ -363,30 +379,64 @@ struct Property
     Property(jsid id)
         : id(id)
     {}
 
     static uint32 keyBits(jsid id) { return (uint32) JSID_BITS(id); }
     static jsid getKey(Property *p) { return p->id; }
 };
 
+/* Bitmask for possible dynamic properties of the JSObjects with some type. */
+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. */
+    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 are arrays whose length has shrunk
+     * due to explicit assignments to .length.
+     */
+    OBJECT_FLAG_ARRAY_SHRANK = 1 << 2,
+
+    /* Whether any objects this represents have had their .arguments accessed. */
+    OBJECT_FLAG_UNINLINEABLE = 1 << 3,
+
+    /* Whether any objects this represents have an equality hook. */
+    OBJECT_FLAG_SPECIAL_EQUALITY = 1 << 4
+};
+typedef uint32 TypeObjectFlags;
+
 /* Type information about an object accessed by a script. */
 struct TypeObject
 {
 #ifdef DEBUG
     /* Name of this object. */
     jsid name_;
 #endif
 
     /* Prototype shared by objects using this type. */
     JSObject *proto;
 
     /* Lazily filled array of empty shapes for each size of objects with this type. */
     js::EmptyShape **emptyShapes;
 
+    /* Vector of TypeObjectFlags for the objects this type represents. */
+    TypeObjectFlags flags;
+
     /* Whether this is a function object, and may be cast into TypeFunction. */
     bool isFunction;
 
     /* Mark bit for GC. */
     bool marked;
 
     /*
      * Whether this is an Object or Array keyed to an offset in the script containing
@@ -422,52 +472,34 @@ struct TypeObject
     TypeObject *instanceList;
 
     /* Chain for objects sharing the same prototype. */
     TypeObject *instanceNext;
 
     /* Link in the list of objects associated with a script or global object. */
     TypeObject *next;
 
-    /*
-     * 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).
-     */
-    bool unknownProperties;
-
-    /* Whether all objects this represents are dense arrays. */
-    bool isDenseArray;
-
-    /* Whether all objects this represents are packed arrays (implies isDenseArray). */
-    bool isPackedArray;
-
-    /* Whether any objects this represents have had their .arguments accessed. */
-    bool isUninlineable;
-
-    /* Whether any objects this represents have an equality hook. */
-    bool hasSpecialEquality;
-
     /* If at most one JSObject can have this as its type, that object. */
     JSObject *singleton;
 
     TypeObject() {}
 
     /* Make an object with the specified name. */
     inline TypeObject(jsid id, JSObject *proto);
 
     /* Coerce this object to a function. */
     TypeFunction* asFunction()
     {
         JS_ASSERT(isFunction);
         return (TypeFunction *) this;
     }
 
+    bool unknownProperties() { return flags == OBJECT_FLAG_UNKNOWN_MASK; }
+    bool hasFlags(TypeObjectFlags flags) { return (this->flags & flags) == flags; }
+
     /*
      * Return an immutable, shareable, empty shape with the same clasp as this
      * and the same slotSpan as this had when empty.
      *
      * If |this| is the scope of an object |proto|, the resulting scope can be
      * used as the scope of a new object whose prototype is |proto|.
      */
     inline bool canProvideEmptyShape(js::Class *clasp);
@@ -482,23 +514,25 @@ struct TypeObject
      */
     inline TypeSet *getProperty(JSContext *cx, jsid id, bool assign);
 
     inline const char * name();
 
     /* Mark proto as the prototype of this object and all instances. */
     void splicePrototype(JSContext *cx, JSObject *proto);
 
+    inline unsigned getPropertyCount();
+    inline Property *getProperty(unsigned i);
+
     /* Helpers */
 
     bool addProperty(JSContext *cx, jsid id, Property **pprop);
     void addPrototype(JSContext *cx, TypeObject *proto);
-    void markNotPacked(JSContext *cx, bool notDense);
+    void setFlags(JSContext *cx, TypeObjectFlags flags);
     void markUnknown(JSContext *cx);
-    void markUninlineable(JSContext *cx);
     void storeToInstances(JSContext *cx, Property *base);
     void getFromPrototypes(JSContext *cx, Property *base);
 
     void print(JSContext *cx);
     void trace(JSTracer *trc);
 };
 
 /*
@@ -737,17 +771,17 @@ struct TypeCompartment
     /* Resolve pending type registrations, excluding delayed ones. */
     inline void resolvePending(JSContext *cx);
 
     /* Prints results of this compartment if spew is enabled, checks for warnings. */
     void print(JSContext *cx, JSCompartment *compartment);
 
     /* Make a function or non-function object associated with an optional script. */
     TypeObject *newTypeObject(JSContext *cx, JSScript *script,
-                              const char *name, bool isFunction, JSObject *proto);
+                              const char *name, bool isFunction, bool isArray, JSObject *proto);
 
     /* Make an initializer object. */
     TypeObject *newInitializerTypeObject(JSContext *cx, JSScript *script,
                                          uint32 offset, bool isArray);
 
     /*
      * Add the specified type to the specified set, do any necessary reanalysis
      * stemming from the change and recompile any affected scripts.
--- a/js/src/jsinferinlines.h
+++ b/js/src/jsinferinlines.h
@@ -308,41 +308,41 @@ inline bool
 JSContext::markTypeCallerOverflow()
 {
     return markTypeCallerUnexpected(js::types::TYPE_DOUBLE);
 }
 
 inline bool
 JSContext::addTypeProperty(js::types::TypeObject *obj, const char *name, js::types::jstype type)
 {
-    if (typeInferenceEnabled() && !obj->unknownProperties) {
+    if (typeInferenceEnabled() && !obj->unknownProperties()) {
         jsid id = JSID_VOID;
         if (name) {
             JSAtom *atom = js_Atomize(this, name, strlen(name), 0);
             if (!atom)
                 return false;
             id = ATOM_TO_JSID(atom);
         }
         return addTypePropertyId(obj, id, type);
     }
     return true;
 }
 
 inline bool
 JSContext::addTypeProperty(js::types::TypeObject *obj, const char *name, const js::Value &value)
 {
-    if (typeInferenceEnabled() && !obj->unknownProperties)
+    if (typeInferenceEnabled() && !obj->unknownProperties())
         return addTypeProperty(obj, name, js::types::GetValueType(this, value));
     return true;
 }
 
 inline bool
 JSContext::addTypePropertyId(js::types::TypeObject *obj, jsid id, js::types::jstype type)
 {
-    if (!typeInferenceEnabled() || obj->unknownProperties)
+    if (!typeInferenceEnabled() || obj->unknownProperties())
         return true;
 
     /* Convert string index properties into the common index property. */
     id = js::types::MakeTypeId(this, id);
 
     js::types::AutoEnterTypeInference enter(this);
 
     js::types::TypeSet *types = obj->getProperty(this, id, true);
@@ -355,25 +355,25 @@ JSContext::addTypePropertyId(js::types::
     types->addType(this, type);
 
     return compartment->types.checkPendingRecompiles(this);
 }
 
 inline bool
 JSContext::addTypePropertyId(js::types::TypeObject *obj, jsid id, const js::Value &value)
 {
-    if (typeInferenceEnabled() && !obj->unknownProperties)
+    if (typeInferenceEnabled() && !obj->unknownProperties())
         return addTypePropertyId(obj, id, js::types::GetValueType(this, value));
     return true;
 }
 
 inline bool
 JSContext::addTypePropertyId(js::types::TypeObject *obj, jsid id, js::types::ClonedTypeSet *set)
 {
-    if (obj->unknownProperties)
+    if (obj->unknownProperties())
         return true;
     id = js::types::MakeTypeId(this, id);
 
     js::types::AutoEnterTypeInference enter(this);
 
     js::types::TypeSet *types = obj->getProperty(this, id, true);
     if (!types)
         return compartment->types.checkPendingRecompiles(this);
@@ -389,17 +389,17 @@ inline js::types::TypeObject *
 JSContext::getTypeEmpty()
 {
     return &compartment->types.typeEmpty;
 }
 
 inline bool
 JSContext::aliasTypeProperties(js::types::TypeObject *obj, jsid first, jsid second)
 {
-    if (!typeInferenceEnabled() || obj->unknownProperties)
+    if (!typeInferenceEnabled() || obj->unknownProperties())
         return true;
 
     js::types::AutoEnterTypeInference enter(this);
 
     first = js::types::MakeTypeId(this, first);
     second = js::types::MakeTypeId(this, second);
 
     js::types::TypeSet *firstTypes = obj->getProperty(this, first, true);
@@ -409,43 +409,62 @@ JSContext::aliasTypeProperties(js::types
 
     firstTypes->addBaseSubset(this, obj, secondTypes);
     secondTypes->addBaseSubset(this, obj, firstTypes);
 
     return compartment->types.checkPendingRecompiles(this);
 }
 
 inline bool
+JSContext::addTypeFlags(js::types::TypeObject *obj, js::types::TypeObjectFlags flags)
+{
+    if (!typeInferenceEnabled() || obj->hasFlags(flags))
+        return true;
+
+    js::types::AutoEnterTypeInference enter(this);
+    obj->setFlags(this, flags);
+    return compartment->types.checkPendingRecompiles(this);
+}
+
+inline bool
 JSContext::markTypeArrayNotPacked(js::types::TypeObject *obj, bool notDense)
 {
-    if (!typeInferenceEnabled() || (notDense ? !obj->isDenseArray : !obj->isPackedArray))
-        return true;
-    js::types::AutoEnterTypeInference enter(this);
+    return addTypeFlags(obj, js::types::OBJECT_FLAG_NON_PACKED_ARRAY |
+                        (notDense ? js::types::OBJECT_FLAG_NON_DENSE_ARRAY : 0));
+}
 
-    obj->markNotPacked(this, notDense);
-
-    return compartment->types.checkPendingRecompiles(this);
+inline bool
+JSContext::markTypeArrayShrank(js::types::TypeObject *obj)
+{
+    /*
+     * For simplicity in determining whether to hoist array bounds checks,
+     * we mark types with arrays that have shrunk (a rare operation) as
+     * possibly non-dense.
+     */
+    return addTypeFlags(obj, js::types::OBJECT_FLAG_ARRAY_SHRANK |
+                        js::types::OBJECT_FLAG_NON_PACKED_ARRAY |
+                        js::types::OBJECT_FLAG_NON_DENSE_ARRAY);
 }
 
 inline bool
 JSContext::markTypeFunctionUninlineable(js::types::TypeObject *obj)
 {
-    if (!typeInferenceEnabled() || obj->isUninlineable)
-        return true;
-    js::types::AutoEnterTypeInference enter(this);
+    return addTypeFlags(obj, js::types::OBJECT_FLAG_UNINLINEABLE);
+}
 
-    obj->markUninlineable(this);
-
-    return compartment->types.checkPendingRecompiles(this);
+inline bool
+JSContext::markTypeObjectHasSpecialEquality(js::types::TypeObject *obj)
+{
+    return addTypeFlags(obj, js::types::OBJECT_FLAG_SPECIAL_EQUALITY);
 }
 
 inline bool
 JSContext::markTypeObjectUnknownProperties(js::types::TypeObject *obj)
 {
-    if (!typeInferenceEnabled() || obj->unknownProperties)
+    if (!typeInferenceEnabled() || obj->unknownProperties())
         return true;
 
     js::types::AutoEnterTypeInference enter(this);
     obj->markUnknown(this);
     return compartment->types.checkPendingRecompiles(this);
 }
 
 inline bool
@@ -1116,16 +1135,34 @@ TypeSet::addType(JSContext *cx, jstype t
                      constraint->script->compartment == cx->compartment);
         cx->compartment->types.addPending(cx, constraint, this, type);
         constraint = constraint->next;
     }
 
     cx->compartment->types.resolvePending(cx);
 }
 
+inline unsigned
+TypeSet::getObjectCount()
+{
+    if (objectCount > SET_ARRAY_SIZE)
+        return HashSetCapacity(objectCount);
+    return objectCount;
+}
+
+inline TypeObject *
+TypeSet::getObject(unsigned i)
+{
+    if (objectCount == 1) {
+        JS_ASSERT(i == 0);
+        return (TypeObject *) objectSet;
+    }
+    return objectSet[i];
+}
+
 inline TypeSet *
 TypeSet::make(JSContext *cx, const char *name)
 {
     JS_ASSERT(cx->compartment->types.inferenceDepth);
 
     TypeSet *res = ArenaNew<TypeSet>(cx->compartment->types.pool);
     if (!res) {
         cx->compartment->types.setPendingNukeTypes(cx);
@@ -1183,26 +1220,44 @@ TypeCallsite::compileAndGo()
 /////////////////////////////////////////////////////////////////////
 
 inline TypeSet *
 TypeObject::getProperty(JSContext *cx, jsid id, bool assign)
 {
     JS_ASSERT(cx->compartment->types.inferenceDepth);
     JS_ASSERT(JSID_IS_VOID(id) || JSID_IS_EMPTY(id) || JSID_IS_STRING(id));
     JS_ASSERT_IF(JSID_IS_STRING(id), JSID_TO_STRING(id) != NULL);
-    JS_ASSERT(!unknownProperties);
+    JS_ASSERT(!unknownProperties());
 
     Property **pprop = HashSetInsert<jsid,Property,Property>
                            (cx, propertySet, propertyCount, id, false);
     if (!pprop || (!*pprop && !addProperty(cx, id, pprop)))
         return NULL;
 
     return assign ? &(*pprop)->ownTypes : &(*pprop)->types;
 }
 
+inline unsigned
+TypeObject::getPropertyCount()
+{
+    if (propertyCount > SET_ARRAY_SIZE)
+        return HashSetCapacity(propertyCount);
+    return propertyCount;
+}
+
+inline Property *
+TypeObject::getProperty(unsigned i)
+{
+    if (propertyCount == 1) {
+        JS_ASSERT(i == 0);
+        return (Property *) propertySet;
+    }
+    return propertySet[i];
+}
+
 /////////////////////////////////////////////////////////////////////
 // TypeScript
 /////////////////////////////////////////////////////////////////////
 
 inline bool
 TypeScript::monitored(uint32 offset)
 {
     JS_ASSERT(offset < script->length);
@@ -1245,40 +1300,28 @@ TypeObject::name()
 #ifdef DEBUG
     return TypeIdString(name_);
 #else
     return NULL;
 #endif
 }
 
 inline TypeObject::TypeObject(jsid name, JSObject *proto)
-    : proto(proto), emptyShapes(NULL), isFunction(false), marked(false),
+    : proto(proto), emptyShapes(NULL),
+      flags(0), isFunction(false), marked(false),
       initializerObject(false), initializerArray(false), initializerOffset(0),
       contribution(0), propertySet(NULL), propertyCount(0),
-      instanceList(NULL), instanceNext(NULL), next(NULL), unknownProperties(false),
-      isDenseArray(false), isPackedArray(false),
-      isUninlineable(false), hasSpecialEquality(false),
+      instanceList(NULL), instanceNext(NULL), next(NULL),
       singleton(NULL)
 {
 #ifdef DEBUG
     this->name_ = name;
 #endif
 
     InferSpew(ISpewOps, "newObject: %s", this->name());
-
-    if (proto) {
-        TypeObject *prototype = proto->getType();
-        if (prototype->unknownProperties) {
-            isUninlineable = true;
-            hasSpecialEquality = true;
-            unknownProperties = true;
-        }
-        instanceNext = prototype->instanceList;
-        prototype->instanceList = this;
-    }
 }
 
 inline TypeFunction::TypeFunction(jsid name, JSObject *proto)
     : TypeObject(name, proto), handler(NULL), script(NULL), isGeneric(false)
 {
     isFunction = true;
 }
 
--- a/js/src/jsinterp.cpp
+++ b/js/src/jsinterp.cpp
@@ -4721,16 +4721,17 @@ BEGIN_CASE(JSOP_CALLELEM)
     if ((regs.sp[-2].isUndefined() || !JSID_IS_INT(id)) &&
         !script->typeMonitorUnknown(cx, regs.pc)) {
         goto error;
     }
 }
 END_CASE(JSOP_CALLELEM)
 
 BEGIN_CASE(JSOP_SETELEM)
+BEGIN_CASE(JSOP_SETHOLE)
 {
     JSObject *obj;
     FETCH_OBJECT(cx, -3, obj);
     jsid id;
     FETCH_ELEMENT_ID(obj, -2, id);
     Value rval;
     if (!cx->typeMonitorAssign(obj, id, regs.sp[-1]))
         goto error;
@@ -4739,19 +4740,22 @@ BEGIN_CASE(JSOP_SETELEM)
             jsuint length = obj->getDenseArrayInitializedLength();
             jsint i = JSID_TO_INT(id);
             if ((jsuint)i < length) {
                 if (obj->getDenseArrayElement(i).isMagic(JS_ARRAY_HOLE)) {
                     if (js_PrototypeHasIndexedProperties(cx, obj))
                         break;
                     if ((jsuint)i >= obj->getArrayLength() && !obj->setArrayLength(cx, i + 1))
                         goto error;
+                    *regs.pc = JSOP_SETHOLE;
                 }
                 obj->setDenseArrayElement(i, regs.sp[-1]);
                 goto end_setelem;
+            } else {
+                *regs.pc = JSOP_SETHOLE;
             }
         }
     } while (0);
     rval = regs.sp[-1];
     if (!obj->setProperty(cx, id, &rval, script->strictModeCode))
         goto error;
   end_setelem:;
 }
--- a/js/src/jsobjinlines.h
+++ b/js/src/jsobjinlines.h
@@ -129,17 +129,17 @@ JSObject::deleteProperty(JSContext *cx, 
     return (op ? op : js_DeleteProperty)(cx, this, id, rval, strict);
 }
 
 inline void
 JSObject::syncSpecialEquality()
 {
     if (clasp->ext.equality) {
         flags |= JSObject::HAS_EQUALITY;
-        JS_ASSERT(getType()->hasSpecialEquality);
+        JS_ASSERT(getType()->hasFlags(js::types::OBJECT_FLAG_SPECIAL_EQUALITY));
     }
 }
 
 inline void
 JSObject::finalize(JSContext *cx)
 {
     /* Cope with stillborn objects that have no map. */
     if (!map)
@@ -820,17 +820,17 @@ JSObject::clearType(JSContext *cx)
 inline void
 JSObject::setType(js::types::TypeObject *newType)
 {
 #ifdef DEBUG
     JS_ASSERT(newType);
     for (JSObject *obj = newType->proto; obj; obj = obj->getProto())
         JS_ASSERT(obj != this);
 #endif
-    JS_ASSERT_IF(hasSpecialEquality(), newType->hasSpecialEquality);
+    JS_ASSERT_IF(hasSpecialEquality(), newType->hasFlags(js::types::OBJECT_FLAG_SPECIAL_EQUALITY));
     type = newType;
 }
 
 inline bool
 JSObject::setTypeAndUniqueShape(JSContext *cx, js::types::TypeObject *newType)
 {
     setType(newType);
 
--- a/js/src/jsopcode.cpp
+++ b/js/src/jsopcode.cpp
@@ -3944,16 +3944,17 @@ Decompile(SprintStack *ss, jsbytecode *p
                                   (JOF_OPMODE(lastop) == JOF_XMLNAME)
                                   ? dot_format
                                   : index_format,
                                   lval, xval);
                 }
                 break;
 
               case JSOP_SETELEM:
+              case JSOP_SETHOLE:
                 rval = POP_STR();
                 op = JSOP_NOP;          /* turn off parens */
                 xval = POP_STR();
                 cs = &js_CodeSpec[ss->opcodes[ss->top]];
                 op = JSOP_GETELEM;      /* lval must have high precedence */
                 lval = POP_STR();
                 op = saveop;
                 if (*xval == '\0')
--- a/js/src/jsopcode.tbl
+++ b/js/src/jsopcode.tbl
@@ -611,8 +611,11 @@ OPDEF(JSOP_SHARPINIT,     239,"sharpinit
 /* Static binding for globals. */
 OPDEF(JSOP_GETGLOBAL,     240,"getglobal",     NULL,  3,  0,  1, 19,  JOF_GLOBAL|JOF_NAME)
 OPDEF(JSOP_CALLGLOBAL,    241,"callglobal",    NULL,  3,  0,  2, 19,  JOF_GLOBAL|JOF_NAME|JOF_CALLOP)
 
 /* Like JSOP_FUNAPPLY but for f.call instead of f.apply. */
 OPDEF(JSOP_FUNCALL,       242,"funcall",       NULL,  3, -1,  1, 18,  JOF_UINT16|JOF_INVOKE)
 
 OPDEF(JSOP_FORGNAME,      243,"forgname",      NULL,  3,  1,  1, 19,  JOF_ATOM|JOF_GNAME|JOF_FOR|JOF_TMPSLOT3)
+
+/* Substituted for JSOP_SETELEM to indicate opcodes which have written holes in dense arrays. */
+OPDEF(JSOP_SETHOLE,       244, "sethole",      NULL,  1,  3,  1,  3,  JOF_BYTE |JOF_ELEM|JOF_SET|JOF_DETECTING)
--- a/js/src/jsscript.h
+++ b/js/src/jsscript.h
@@ -459,16 +459,17 @@ struct JSScript {
     bool            isCachedEval:1;   /* script came from eval() */
     bool            isUncachedEval:1; /* script came from EvaluateScript */
     bool            calledWithNew:1;  /* script has been called using 'new' */
     bool            analyzed:1;       /* script has been analyzed by type inference */
 #ifdef JS_METHODJIT
     bool            debugMode:1;      /* script was compiled in debug mode */
     bool            singleStepMode:1; /* compile script in single-step mode */
     bool            inlineParents:1;  /* script may be inlined in other frames */
+    bool            failedBoundsCheck:1; /* script has had hoisted bounds checks fail */
 #endif
 
     jsbytecode      *main;      /* main entry point, after predef'ing prolog */
     JSAtomMap       atomMap;    /* maps immediate index to literal struct */
     JSCompartment   *compartment; /* compartment the script was compiled for */
     const char      *filename;  /* source filename or null */
     uint32          lineno;     /* base line number of script */
     uint16          nslots;     /* vars plus maximum stack depth */
--- a/js/src/jstracer.cpp
+++ b/js/src/jstracer.cpp
@@ -6766,17 +6766,18 @@ LeaveTree(TraceMonitor *tm, TracerState&
             JSFrameRegs* regs = cx->regs;
             JSOp op = (JSOp) *regs->pc;
 
             /*
              * JSOP_SETELEM can be coalesced with a JSOP_POP in the interpeter.
              * Since this doesn't re-enter the recorder, the post-state snapshot
              * is invalid. Fix it up here.
              */
-            if (op == JSOP_SETELEM && JSOp(regs->pc[JSOP_SETELEM_LENGTH]) == JSOP_POP) {
+            if ((op == JSOP_SETELEM || op == JSOP_SETHOLE) &&
+                JSOp(regs->pc[JSOP_SETELEM_LENGTH]) == JSOP_POP) {
                 regs->sp -= js_CodeSpec[JSOP_SETELEM].nuses;
                 regs->sp += js_CodeSpec[JSOP_SETELEM].ndefs;
                 regs->pc += JSOP_SETELEM_LENGTH;
                 op = JSOP_POP;
             }
 
             const JSCodeSpec& cs = js_CodeSpec[op];
             regs->sp -= (cs.format & JOF_INVOKE) ? GET_ARGC(regs->pc) + 2 : cs.nuses;
@@ -13394,28 +13395,34 @@ TraceRecorder::setElem(int lval_spindex,
         }
         w.resumeAddingCSEValues();
 
         // Right, actually set the element.
         box_value_into(v, v_ins, dslotAddr);
     }
 
     jsbytecode* pc = cx->regs->pc;
-    if (*pc == JSOP_SETELEM && pc[JSOP_SETELEM_LENGTH] != JSOP_POP)
+    if ((*pc == JSOP_SETELEM || *pc == JSOP_SETHOLE) && pc[JSOP_SETELEM_LENGTH] != JSOP_POP)
         set(&lval, v_ins);
 
     return ARECORD_CONTINUE;
 }
 
 JS_REQUIRES_STACK AbortableRecordingStatus
 TraceRecorder::record_JSOP_SETELEM()
 {
     return setElem(-3, -2, -1);
 }
 
+JS_REQUIRES_STACK AbortableRecordingStatus
+TraceRecorder::record_JSOP_SETHOLE()
+{
+    return setElem(-3, -2, -1);
+}
+
 static JSBool FASTCALL
 CheckSameGlobal(JSObject *obj, JSObject *globalObj)
 {
     return obj->getGlobal() == globalObj;
 }
 JS_DEFINE_CALLINFO_2(static, BOOL, CheckSameGlobal, OBJECT, OBJECT, 0, ACCSET_STORE_ANY)
 
 JS_REQUIRES_STACK AbortableRecordingStatus
@@ -17123,17 +17130,17 @@ LoopProfile::profileOperation(JSContext*
     }
 
     if (op == JSOP_EVAL)
         increment(OP_EVAL);
 
     if (op == JSOP_NEW)
         increment(OP_NEW);
 
-    if (op == JSOP_GETELEM || op == JSOP_SETELEM) {
+    if (op == JSOP_GETELEM || op == JSOP_SETELEM || op == JSOP_SETHOLE) {
         Value& lval = cx->regs->sp[op == JSOP_GETELEM ? -2 : -3];
         if (lval.isObject() && js_IsTypedArray(&lval.toObject()))
             increment(OP_TYPED_ARRAY);
         else if (lval.isObject() && lval.toObject().isDenseArray() && op == JSOP_GETELEM)
             increment(OP_ARRAY_READ);
     }
 
     if (op == JSOP_GETPROP || op == JSOP_CALLPROP ||
--- a/js/src/methodjit/Compiler.cpp
+++ b/js/src/methodjit/Compiler.cpp
@@ -93,17 +93,17 @@ mjit::Compiler::Compiler(JSContext *cx, 
                          const Vector<PatchableFrame> *patchFrames, bool recompiling)
   : BaseCompiler(cx),
     outerScript(outerScript),
     isConstructing(isConstructing),
     globalObj(outerScript->global),
     patchFrames(patchFrames),
     savedTraps(NULL),
     frame(cx, *this, masm, stubcc),
-    a(NULL), outer(NULL), script(NULL), PC(NULL),
+    a(NULL), outer(NULL), script(NULL), PC(NULL), loop(NULL),
     inlineFrames(CompilerAllocPolicy(cx, *thisFromCtor())),
     branchPatches(CompilerAllocPolicy(cx, *thisFromCtor())),
 #if defined JS_MONOIC
     getGlobalNames(CompilerAllocPolicy(cx, *thisFromCtor())),
     setGlobalNames(CompilerAllocPolicy(cx, *thisFromCtor())),
     callICs(CompilerAllocPolicy(cx, *thisFromCtor())),
     equalityICs(CompilerAllocPolicy(cx, *thisFromCtor())),
     traceICs(CompilerAllocPolicy(cx, *thisFromCtor())),
@@ -205,26 +205,27 @@ mjit::Compiler::pushActiveFrame(JSScript
 
     if (cx->typeInferenceEnabled() && !newa->liveness.analyze(cx, &newa->analysis, script)) {
         js_ReportOutOfMemory(cx);
         return Compile_Error;
     }
 
 #ifdef JS_METHODJIT_SPEW
     if (cx->typeInferenceEnabled() && IsJaegerSpewChannelActive(JSpew_Regalloc)) {
+        unsigned nargs = script->fun ? script->fun->nargs : 0;
+        for (unsigned i = 0; i < nargs; i++) {
+            if (!newa->analysis.argEscapes(i)) {
+                JaegerSpew(JSpew_Regalloc, "Argument %u:", i);
+                newa->liveness.dumpSlot(2 + i);
+            }
+        }
         for (unsigned i = 0; i < script->nfixed; i++) {
             if (!newa->analysis.localEscapes(i)) {
                 JaegerSpew(JSpew_Regalloc, "Local %u:", i);
-                newa->liveness.dumpLocal(i);
-            }
-        }
-        for (unsigned i = 0; script->fun && i < script->fun->nargs; i++) {
-            if (!newa->analysis.argEscapes(i)) {
-                JaegerSpew(JSpew_Regalloc, "Argument %u:", i);
-                newa->liveness.dumpArg(i);
+                newa->liveness.dumpSlot(2 + nargs + i);
             }
         }
     }
 #endif
 
     if (a)
         frame.getUnsyncedEntries(&newa->depth, &newa->unsyncedEntries);
 
@@ -692,17 +693,17 @@ mjit::Compiler::finishThisUp(JITScript *
     JSC::LinkBuffer fullCode(result, totalSize);
     JSC::LinkBuffer stubCode(result + masm.size(), stubcc.size());
 
     size_t nNmapLive = loopEntries.length();
     for (size_t i = 0; i < script->length; i++) {
         analyze::Bytecode *opinfo = a->analysis.maybeCode(i);
         if (opinfo && opinfo->safePoint) {
             /* loopEntries cover any safe points which are at loop heads. */
-            if (!cx->typeInferenceEnabled() || !a->liveness.getCode(i).loopBackedge)
+            if (!cx->typeInferenceEnabled() || !a->liveness.getCode(i).loop)
                 nNmapLive++;
         }
     }
 
     size_t nUnsyncedEntries = 0;
     for (size_t i = 0; i < inlineFrames.length(); i++)
         nUnsyncedEntries += inlineFrames[i]->unsyncedEntries.length();
 
@@ -1263,32 +1264,35 @@ mjit::Compiler::generateMethod()
                 break;
             if (js_CodeSpec[op].length != -1)
                 PC += js_CodeSpec[op].length;
             else
                 PC += js_GetVariableBytecodeLength(PC);
             continue;
         }
 
+        if (loop)
+            loop->PC = PC;
+
         frame.setPC(PC);
         frame.setInTryBlock(opinfo->inTryBlock);
         if (opinfo->jumpTarget || trap) {
             if (fallthrough) {
                 fixDoubleTypes(Uses(0));
 
                 /*
                  * Watch for fallthrough to the head of a 'do while' loop.
                  * We don't know what register state we will be using at the head
                  * of the loop so sync, branch, and fix it up after the loop
                  * has been processed.
                  */
-                if (cx->typeInferenceEnabled() && a->liveness.getCode(PC).loopBackedge) {
+                if (cx->typeInferenceEnabled() && a->liveness.getCode(PC).loop) {
                     frame.syncAndForgetEverything();
                     Jump j = masm.jump();
-                    if (!frame.pushLoop(PC, j, PC))
+                    if (!startLoop(PC, j, PC))
                         return Compile_Error;
                 } else {
                     if (!frame.syncForBranch(PC, Uses(0)))
                         return Compile_Error;
                     JS_ASSERT(frame.consistentRegisters(PC));
                 }
             }
 
@@ -1426,40 +1430,42 @@ mjit::Compiler::generateMethod()
 
           BEGIN_CASE(JSOP_GOTO)
           BEGIN_CASE(JSOP_DEFAULT)
           {
             jsbytecode *target = PC + GET_JUMP_OFFSET(PC);
             fixDoubleTypes(Uses(0));
 
             /*
-             * Watch out for backward jumps emitted to link 'continue' statements
-             * together. These are jumping to another GOTO at the head of the loop,
-             * which should be short circuited so we don't mistake this for an
-             * actual loop back edge. :XXX: what if there is a trap at the target?
+             * Watch out for backward jumps linking 'continue' statements
+             * together. These are jumping to another GOTO at the head of the
+             * loop, which should be short circuited so we don't mistake this
+             * for an actual loop back edge. :XXX: could there be a trap at
+             * the target?
              */
             if (target < PC) {
                 if (JSOp(*target) == JSOP_GOTO) {
                     target = target + GET_JUMP_OFFSET(target);
                     JS_ASSERT(target >= PC);
                 } else if (JSOp(*target) == JSOP_GOTOX) {
                     return Compile_Abort;
                 }
             }
 
             /*
-             * Watch for gotos which are entering a 'for' or 'while' loop. These jump
-             * to the loop condition test and are immediately followed by the head of the loop.
+             * Watch for gotos which are entering a 'for' or 'while' loop.
+             * These jump to the loop condition test and are immediately
+             * followed by the head of the loop.
              */
             jsbytecode *next = PC + JSOP_GOTO_LENGTH;
             if (cx->typeInferenceEnabled() && a->analysis.maybeCode(next) &&
-                a->liveness.getCode(next).loopBackedge) {
+                a->liveness.getCode(next).loop) {
                 frame.syncAndForgetEverything();
                 Jump j = masm.jump();
-                if (!frame.pushLoop(next, j, target))
+                if (!startLoop(next, j, target))
                     return Compile_Error;
             } else {
                 if (!frame.syncForBranch(target, Uses(0)))
                     return Compile_Error;
                 Jump j = masm.jump();
                 if (!jumpAndTrace(j, target))
                     return Compile_Error;
             }
@@ -1904,16 +1910,17 @@ mjit::Compiler::generateMethod()
           END_CASE(JSOP_LENGTH)
 
           BEGIN_CASE(JSOP_GETELEM)
             if (!jsop_getelem(false))
                 return Compile_Error;
           END_CASE(JSOP_GETELEM)
 
           BEGIN_CASE(JSOP_SETELEM)
+          BEGIN_CASE(JSOP_SETHOLE)
           {
             jsbytecode *next = &PC[JSOP_SETELEM_LENGTH];
             bool pop = (JSOp(*next) == JSOP_POP && !a->analysis.jumpTarget(next));
             if (!jsop_setelem(pop))
                 return Compile_Error;
           }
           END_CASE(JSOP_SETELEM);
 
@@ -3727,17 +3734,17 @@ mjit::Compiler::inlineScriptedFunction(u
     /*
      * Make sure no callees have had their .arguments accessed, and trigger
      * recompilation if they ever are accessed.
      */
     types::ObjectKind kind = types->getKnownObjectKind(cx);
     if (kind != types::OBJECT_INLINEABLE_FUNCTION)
         return Compile_InlineAbort;
 
-    if (types->objectCount >= INLINE_SITE_LIMIT)
+    if (types->getObjectCount() >= INLINE_SITE_LIMIT)
         return Compile_InlineAbort;
 
     /*
      * We can't inline frames at this PC if there is a frame on the stack which
      * is in the process of calling a C++ IC or stub call. We do not emit the
      * necessary rejoin code in this situation --- there is no value for ncode
      * we can store in the newly assembled frame once the IC/stub returns.
      */
@@ -3753,23 +3760,20 @@ mjit::Compiler::inlineScriptedFunction(u
      * a call from the deepest inlined frame.
      */
     uint32 stackLimit = outerScript->nslots + StackSpace::STACK_EXTRA - VALUES_PER_STACK_FRAME;
 
     /*
      * Scan each of the possible callees for other conditions precluding
      * inlining. We only inline at a call site if all callees are inlineable.
      */
-    for (unsigned i = 0; i < types->objectCount; i++) {
-        types::TypeObject *object;
-        if (types->objectCount == 1)
-            object = (types::TypeObject *) types->objectSet;
-        else
-            object = types->objectSet[i];  // FIXME hash case not possible here, but still gross.
-        JS_ASSERT(object);
+    unsigned count = types->getObjectCount();
+    for (unsigned i = 0; i < count; i++) {
+        types::TypeObject *object = types->getObject(i);
+        JS_ASSERT(object);  /* Hash case for types->objectSet not possible here. */
 
         if (!object->singleton || !object->singleton->isFunction())
             return Compile_InlineAbort;
 
         JSFunction *fun = object->singleton->getFunctionPrivate();
         if (!fun->isInterpreted())
             return Compile_InlineAbort;
         JSScript *script = fun->script();
@@ -3827,17 +3831,17 @@ mjit::Compiler::inlineScriptedFunction(u
         frame.tryCopyRegister(frame.peek(-(i + 1)), origCallee);
 
     /*
      * If this is a polymorphic callsite, get a register for the callee too.
      * After this, do not touch the register state in the current frame until
      * stubs for all callees have been generated.
      */
     MaybeRegisterID calleeReg;
-    if (types->objectCount > 1) {
+    if (count > 1) {
         frame.forgetConstantData(origCallee);
         calleeReg = frame.tempRegForData(origCallee);
     }
     MaybeJump calleePrevious;
 
     /*
      * Registers for entries which will be popped after the call finishes do
      * not need to be preserved by the inline frames.
@@ -3851,22 +3855,18 @@ mjit::Compiler::inlineScriptedFunction(u
 
     /* Track register state after the call. */
     bool returnSet = false;
     AnyRegisterID returnRegister;
     Registers returnParentRegs = 0;
 
     Vector<Jump, 4, CompilerAllocPolicy> returnJumps(CompilerAllocPolicy(cx, *this));
 
-    for (unsigned i = 0; i < types->objectCount; i++) {
-        types::TypeObject *object;
-        if (types->objectCount == 1)
-            object = (types::TypeObject *) types->objectSet;
-        else
-            object = types->objectSet[i];  // FIXME hash case not possible here, but still gross.
+    for (unsigned i = 0; i < count; i++) {
+        types::TypeObject *object = types->getObject(i);
         JS_ASSERT(object);
 
         JSFunction *fun = object->singleton->getFunctionPrivate();
 
         CompileStatus status;
 
         status = pushActiveFrame(fun->script(), argc);
         if (status != Compile_Okay)
@@ -3875,17 +3875,17 @@ mjit::Compiler::inlineScriptedFunction(u
         JaegerSpew(JSpew_Inlining, "inlining call to script (file \"%s\") (line \"%d\")\n",
                    script->filename, script->lineno);
 
         if (calleePrevious.isSet()) {
             calleePrevious.get().linkTo(masm.label(), &masm);
             calleePrevious = MaybeJump();
         }
 
-        if (i + 1 != types->objectCount) {
+        if (i + 1 != count) {
             /* Guard on the callee, except when this object must be the callee. */
             JS_ASSERT(calleeReg.isSet());
             calleePrevious = masm.branchPtr(Assembler::NotEqual, calleeReg.reg(), ImmPtr(fun));
         }
 
         a->returnJumps = &returnJumps;
         a->needReturnValue = needReturnValue;
         a->syncReturnValue = syncReturnValue;
@@ -3913,17 +3913,17 @@ mjit::Compiler::inlineScriptedFunction(u
             JS_ASSERT(a->returnSet);
             returnSet = true;
             returnRegister = a->returnRegister;
             returnParentRegs = a->returnParentRegs;
         }
 
         popActiveFrame();
 
-        if (i + 1 != types->objectCount)
+        if (i + 1 != count)
             returnJumps.append(masm.jump());
     }
 
     for (unsigned i = 0; i < returnJumps.length(); i++)
         returnJumps[i].linkTo(masm.label(), &masm);
 
     Registers evictedRegisters = Registers(Registers::AvailAnyRegs & ~returnParentRegs.freeMask);
     frame.evictInlineModifiedRegisters(evictedRegisters);
@@ -4631,19 +4631,19 @@ mjit::Compiler::testSingletonPropertyTyp
         break;
 
       case JSVAL_TYPE_BOOLEAN:
         key = JSProto_Boolean;
         break;
 
       case JSVAL_TYPE_OBJECT:
       case JSVAL_TYPE_UNKNOWN:
-        if (types->objectCount == 1 && !top->isNotType(JSVAL_TYPE_OBJECT)) {
+        if (types->getObjectCount() == 1 && !top->isNotType(JSVAL_TYPE_OBJECT)) {
             JS_ASSERT_IF(top->isTypeKnown(), top->isType(JSVAL_TYPE_OBJECT));
-            types::TypeObject *object = (types::TypeObject *) types->objectSet;
+            types::TypeObject *object = types->getObject(0);
             if (object->proto) {
                 if (!testSingletonProperty(object->proto, id))
                     return false;
 
                 /* If we don't know this is an object, we will need a test. */
                 *testObject = (type != JSVAL_TYPE_OBJECT) && !top->isTypeKnown();
                 return true;
             }
@@ -6159,58 +6159,120 @@ mjit::Compiler::jsop_newinit()
 
     frame.extra(frame.peek(-1)).initArray = (*PC == JSOP_NEWARRAY);
     frame.extra(frame.peek(-1)).initObject = baseobj;
 
     return true;
 }
 
 bool
+mjit::Compiler::startLoop(jsbytecode *head, Jump entry, jsbytecode *entryTarget)
+{
+    JS_ASSERT(cx->typeInferenceEnabled() && script == outerScript);
+
+    if (loop) {
+        /*
+         * Convert all loop registers in the outer loop into unassigned registers.
+         * We don't keep track of which registers the inner loop uses, so the only
+         * registers that can be carried in the outer loop must be mentioned before
+         * the inner loop starts.
+         */
+        loop->flushRegisters(stubcc);
+    }
+
+    LoopState *nloop = cx->new_<LoopState>(cx, script, this, &frame, &a->analysis, &a->liveness);
+    if (!nloop || !nloop->init(head, entry, entryTarget))
+        return false;
+
+    nloop->outer = loop;
+    loop = nloop;
+    frame.setLoop(loop);
+
+    return true;
+}
+
+bool
 mjit::Compiler::finishLoop(jsbytecode *head)
 {
     if (!cx->typeInferenceEnabled())
         return true;
 
     /*
      * We're done processing the current loop. Every loop has exactly one backedge
      * at the end ('continue' statements are forward jumps to the loop test),
      * and after jumpAndTrace'ing on that edge we can pop it from the frame.
      */
+    JS_ASSERT(loop && loop->headOffset() == uint32(head - script->code));
+    loop->flushRegisters(stubcc);
+
+    jsbytecode *entryTarget = script->code + loop->entryOffset();
 
     /*
      * Fix up the jump entering the loop. We are doing this after all code has
      * been emitted for the backedge, so that we are now in the loop's fallthrough
      * (where we will emit the entry code).
      */
     Jump fallthrough = masm.jump();
 
-    Jump entry;
-    jsbytecode *entryTarget;
-    frame.popLoop(head, &entry, &entryTarget);
-
-    if (!jumpInScript(entry, entryTarget))
+#ifdef DEBUG
+    if (IsJaegerSpewChannelActive(JSpew_Regalloc)) {
+        RegisterAllocation *alloc = a->liveness.getCode(head).allocation;
+        JaegerSpew(JSpew_Regalloc, "loop allocation at %u:", head - script->code);
+        frame.dumpAllocation(alloc);
+    }
+#endif
+
+    Vector<Jump> hoistJumps(cx);
+
+    loop->entryJump().linkTo(masm.label(), &masm);
+
+    if (!loop->checkHoistedBounds(entryTarget, masm, &hoistJumps))
         return false;
-
-    fallthrough.linkTo(masm.label(), &masm);
+    for (unsigned i = 0; i < hoistJumps.length(); i++)
+        stubcc.linkExitDirect(hoistJumps[i], stubcc.masm.label());
+    OOL_STUBCALL(stubs::MissedBoundsCheckEntry);
+    stubcc.crossJump(stubcc.masm.jump(), masm.label());
+    hoistJumps.clear();
+
+    frame.prepareForJump(entryTarget, masm, true);
+
+    if (!jumpInScript(masm.jump(), entryTarget))
+        return false;
 
     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;
         entry.label = stubcc.masm.label();
         loopEntries.append(entry);
 
+        if (!loop->checkHoistedBounds(head, stubcc.masm, &hoistJumps))
+            return false;
+        Jump skipCall = stubcc.masm.jump();
+        for (unsigned i = 0; i < hoistJumps.length(); i++)
+            hoistJumps[i].linkTo(stubcc.masm.label(), &stubcc.masm);
+        OOL_STUBCALL(stubs::MissedBoundsCheckHead);
+        skipCall.linkTo(stubcc.masm.label(), &stubcc.masm);
+        hoistJumps.clear();
+
         frame.prepareForJump(head, stubcc.masm, true);
         if (!stubcc.jumpInScript(stubcc.masm.jump(), head))
             return false;
     }
 
+    LoopState *nloop = loop->outer;
+    cx->delete_(loop);
+    loop = nloop;
+    frame.setLoop(loop);
+
+    fallthrough.linkTo(masm.label(), &masm);
+
     return true;
 }
 
 /*
  * Note: This function emits tracer hooks into the OOL path. This means if
  * it is used in the middle of an in-progress slow path, the stream will be
  * hopelessly corrupted. Take care to only call this before linkExits() and
  * after rejoin()s.
@@ -6756,16 +6818,40 @@ mjit::Compiler::localTypeSet(uint32 loca
 types::TypeSet *
 mjit::Compiler::pushedTypeSet(uint32 pushed)
 {
     if (!cx->typeInferenceEnabled())
         return NULL;
     return script->types->pushed(PC - script->code, pushed);
 }
 
+types::TypeSet *
+mjit::Compiler::getTypeSet(uint32 slot)
+{
+    if (!cx->typeInferenceEnabled())
+        return NULL;
+
+    if (slot == 0) /* callee */
+        return NULL;
+    if (slot == 1) /* this */
+        return script->thisTypes();
+    slot -= 2;
+
+    unsigned nargs = script->fun ? script->fun->nargs : 0;
+
+    if (slot < nargs)
+        return script->argTypes(slot);
+    slot -= nargs;
+
+    if (slot < script->nfixed)
+        return script->localTypes(slot);
+
+    return frame.extra(2 + nargs + slot).types;
+}
+
 bool
 mjit::Compiler::monitored(jsbytecode *pc)
 {
     return cx->typeInferenceEnabled() && script->types->monitored(pc - script->code);
 }
 
 void
 mjit::Compiler::pushSyncedEntry(uint32 pushed)
--- a/js/src/methodjit/Compiler.h
+++ b/js/src/methodjit/Compiler.h
@@ -402,16 +402,18 @@ class Compiler : public BaseCompiler
         ~ActiveFrame();
     };
     ActiveFrame *a;
     ActiveFrame *outer;
 
     JSScript *script;
     jsbytecode *PC;
 
+    LoopState *loop;
+
     /* State spanning all stack frames. */
 
     js::Vector<ActiveFrame*, 4, CompilerAllocPolicy> inlineFrames;
     js::Vector<BranchPatch, 64, CompilerAllocPolicy> branchPatches;
 #if defined JS_MONOIC
     js::Vector<GetGlobalNameICInfo, 16, CompilerAllocPolicy> getGlobalNames;
     js::Vector<SetGlobalNameICInfo, 16, CompilerAllocPolicy> setGlobalNames;
     js::Vector<CallGenInfo, 64, CompilerAllocPolicy> callICs;
@@ -474,16 +476,19 @@ class Compiler : public BaseCompiler
         while (scan && scan->parent != outer)
             scan = scan->parent;
         return scan->parentPC;
     }
 
     jsbytecode *inlinePC() { return PC; }
     uint32 inlineIndex() { return a->inlineIndex; }
 
+    types::TypeSet *getTypeSet(uint32 slot);
+    types::TypeSet *getTypeSet(const FrameEntry *fe) { return getTypeSet(frame.indexOfFe(fe)); }
+
   private:
     CompileStatus performCompilation(JITScript **jitp);
     CompileStatus generatePrologue();
     CompileStatus generateMethod();
     CompileStatus generateEpilogue();
     CompileStatus finishThisUp(JITScript **jitp);
     CompileStatus pushActiveFrame(JSScript *script, uint32 argc);
     void popActiveFrame();
@@ -534,16 +539,17 @@ class Compiler : public BaseCompiler
      */
     void ensureInteger(FrameEntry *fe, Uses uses);
 
     /* Convert fe from a double to integer (per ValueToECMAInt32) in place. */
     void truncateDoubleToInt32(FrameEntry *fe, Uses uses);
 
     /* Opcode handlers. */
     bool jumpAndTrace(Jump j, jsbytecode *target, Jump *slow = NULL, bool *trampoline = NULL);
+    bool startLoop(jsbytecode *head, Jump entry, jsbytecode *entryTarget);
     bool finishLoop(jsbytecode *head);
     void jsop_bindname(JSAtom *atom, bool usePropCache);
     void jsop_setglobal(uint32 index);
     void jsop_getglobal(uint32 index);
     void jsop_getprop_slow(JSAtom *atom, bool usePropCache = true);
     void jsop_getarg(uint32 slot);
     void jsop_setarg(uint32 slot, bool popped);
     void jsop_this();
--- a/js/src/methodjit/FastArithmetic.cpp
+++ b/js/src/methodjit/FastArithmetic.cpp
@@ -1454,47 +1454,29 @@ mjit::Compiler::jsop_relational_double(J
             frame.freeReg(fpLeft);
         if (allocateRight)
             frame.freeReg(fpRight);
     }
 
     return true;
 }
 
-static inline JSOp
-ReverseCompareOp(JSOp op)
-{
-    switch (op) {
-      case JSOP_GT:
-        return JSOP_LT;
-      case JSOP_GE:
-        return JSOP_LE;
-      case JSOP_LT:
-        return JSOP_GT;
-      case JSOP_LE:
-        return JSOP_GE;
-      default:
-        JS_NOT_REACHED("unrecognized op");
-        return op;
-    }
-}
-
 bool
 mjit::Compiler::jsop_relational_int(JSOp op, jsbytecode *target, JSOp fused)
 {
     FrameEntry *rhs = frame.peek(-1);
     FrameEntry *lhs = frame.peek(-2);
 
     /* Reverse N cmp A comparisons.  The left side must be in a register. */
     if (lhs->isConstant()) {
         JS_ASSERT(!rhs->isConstant());
         FrameEntry *tmp = lhs;
         lhs = rhs;
         rhs = tmp;
-        op = ReverseCompareOp(op);
+        op = analyze::ReverseCompareOp(op);
     }
 
     JS_ASSERT_IF(!target, fused != JSOP_IFEQ);
     Assembler::Condition cond = GetCompareCondition(op, fused);
 
     if (target) {
         fixDoubleTypes(Uses(2));
         if (!frame.syncForBranch(target, Uses(2)))
@@ -1582,17 +1564,17 @@ mjit::Compiler::jsop_relational_full(JSO
         cmpReg = regs.lhsData.reg();
         if (!regs.rhsData.isSet())
             value = rhs->getValue().toInt32();
         else
             reg = regs.rhsData.reg();
     } else {
         cmpReg = regs.rhsData.reg();
         value = lhs->getValue().toInt32();
-        cmpOp = ReverseCompareOp(op);
+        cmpOp = analyze::ReverseCompareOp(op);
     }
 
     /*
      * Emit the actual comparisons. When a fusion is in play, it's faster to
      * combine the comparison with the jump, so these two cases are implemented
      * separately.
      */
 
--- a/js/src/methodjit/FastOps.cpp
+++ b/js/src/methodjit/FastOps.cpp
@@ -1108,29 +1108,35 @@ mjit::Compiler::jsop_setelem_dense()
         masm.move(vr.dataReg(), objReg);
     } else if (frame.haveSameBacking(obj, id)) {
         objReg = frame.allocReg();
         masm.move(key.reg(), objReg);
     } else {
         objReg = frame.copyDataIntoReg(obj);
     }
 
+    // Guard on the array's initialized length.
+    bool hoisted = loop && !a->parent && loop->hoistArrayLengthCheck(obj, id);
+    MaybeJump initlenGuard;
+    if (!hoisted) {
+        initlenGuard = masm.guardArrayExtent(offsetof(JSObject, initializedLength),
+                                             objReg, key, Assembler::BelowOrEqual);
+    }
+
     frame.unpinEntry(vr);
     if (!key.isConstant() && !frame.haveSameBacking(id, value))
         frame.unpinReg(key.reg());
 
     Label syncTarget = stubcc.syncExitAndJump(Uses(3));
 
-    // Check against initialized length.  This always need to be done.
-    Jump initlenGuard = masm.guardArrayExtent(offsetof(JSObject, initializedLength),
-                                              objReg, key, Assembler::BelowOrEqual);
-
-    // Make an OOL path for setting exactly the initialized length.
-    {
-        stubcc.linkExitDirect(initlenGuard, stubcc.masm.label());
+    // Make an OOL path for setting exactly the initialized length. Skip if we
+    // hoisted the initialized length check entirely, in this case we will
+    // recompile if the index could ever be out of range.
+    if (!hoisted) {
+        stubcc.linkExitDirect(initlenGuard.get(), stubcc.masm.label());
 
         // Recheck for an exact initialized length.
         // :TODO: would be nice to reuse the condition bits from the previous test.
         Jump exactlenGuard = stubcc.masm.guardArrayExtent(offsetof(JSObject, initializedLength),
                                                           objReg, key, Assembler::NotEqual);
         exactlenGuard.linkTo(syncTarget, &stubcc.masm);
 
         // Check array capacity.
@@ -1413,45 +1419,50 @@ mjit::Compiler::jsop_getelem_dense(bool 
         Jump guard = frame.testInt32(Assembler::NotEqual, id);
         stubcc.linkExit(guard, Uses(2));
     }
 
     JSValueType type = knownPushedType(0);
 
     // Allocate registers.
 
+    // If we know the result of the GETELEM may be undefined, then misses on the
+    // initialized length or hole checks can just produce an undefined value.
+    // We checked in the caller that prototypes do not have indexed properties.
+    bool allowUndefined = mayPushUndefined(0);
+
     RegisterID objReg = frame.tempRegForData(obj);
     frame.pinReg(objReg);
 
     Int32Key key = id->isConstant()
                  ? Int32Key::FromConstant(id->getValue().toInt32())
                  : Int32Key::FromRegister(frame.tempRegForData(id));
     if (!key.isConstant() && !frame.haveSameBacking(id, obj))
         frame.pinReg(key.reg());
 
     RegisterID dataReg = frame.allocReg();
 
     MaybeRegisterID typeReg;
     if (!isPacked || type == JSVAL_TYPE_UNKNOWN || type == JSVAL_TYPE_DOUBLE)
         typeReg = frame.allocReg();
 
+    // Guard on the array's initialized length.
+    bool hoisted = loop && !a->parent && loop->hoistArrayLengthCheck(obj, id);
+    MaybeJump initlenGuard;
+    if (!hoisted) {
+        initlenGuard = masm.guardArrayExtent(offsetof(JSObject, initializedLength),
+                                             objReg, key, Assembler::BelowOrEqual);
+    }
+
     frame.unpinReg(objReg);
     if (!key.isConstant() && !frame.haveSameBacking(id, obj))
         frame.unpinReg(key.reg());
 
-    // If we know the result of the GETELEM may be undefined, then misses on the
-    // initialized length or hole checks can just produce an undefined value.
-    // We checked in the caller that prototypes do not have indexed properties.
-    bool allowUndefined = mayPushUndefined(0);
-
-    // Guard on the array's initialized length.
-    Jump initlenGuard = masm.guardArrayExtent(offsetof(JSObject, initializedLength),
-                                              objReg, key, Assembler::BelowOrEqual);
-    if (!allowUndefined)
-        stubcc.linkExit(initlenGuard, Uses(2));
+    if (!hoisted && !allowUndefined)
+        stubcc.linkExit(initlenGuard.get(), Uses(2));
 
     masm.loadPtr(Address(objReg, offsetof(JSObject, slots)), dataReg);
 
     // Get the slot, skipping the hole check if the array is known to be packed.
     Jump holeCheck;
     if (key.isConstant()) {
         Address slot(dataReg, key.index() * sizeof(Value));
         holeCheck = masm.fastArrayLoadSlot(slot, !isPacked, typeReg, dataReg);
@@ -1476,17 +1487,18 @@ mjit::Compiler::jsop_getelem_dense(bool 
     if (type == JSVAL_TYPE_UNKNOWN || type == JSVAL_TYPE_DOUBLE)
         frame.pushRegs(typeReg.reg(), dataReg, type);
     else
         frame.pushTypedPayload(type, dataReg);
 
     stubcc.rejoin(Changes(2));
 
     if (allowUndefined) {
-        stubcc.linkExitDirect(initlenGuard, stubcc.masm.label());
+        if (!hoisted)
+            stubcc.linkExitDirect(initlenGuard.get(), stubcc.masm.label());
         if (!isPacked)
             stubcc.linkExitDirect(holeCheck, stubcc.masm.label());
         JS_ASSERT(type == JSVAL_TYPE_UNKNOWN || type == JSVAL_TYPE_UNDEFINED);
         if (type == JSVAL_TYPE_UNDEFINED)
             stubcc.masm.loadValuePayload(UndefinedValue(), dataReg);
         else
             stubcc.masm.loadValueAsComponents(UndefinedValue(), typeReg.reg(), dataReg);
         stubcc.linkRejoin(stubcc.masm.jump());
--- a/js/src/methodjit/FrameEntry.h
+++ b/js/src/methodjit/FrameEntry.h
@@ -133,16 +133,20 @@ class FrameEntry
 
         Value newValue = Int32Value(value);
         setConstant(Jsvalify(newValue));
     }
 
     bool isCopy() const { return !!copy; }
     bool isCopied() const { return copied; }
 
+    const FrameEntry *backing() const {
+        return isCopy() ? copyOf() : this;
+    }
+
   private:
     void setType(JSValueType type_) {
         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_);
@@ -210,20 +214,16 @@ class FrameEntry
     }
 
     FrameEntry *copyOf() const {
         JS_ASSERT(isCopy());
         JS_ASSERT(copy < this);
         return copy;
     }
 
-    const FrameEntry *backing() const {
-        return isCopy() ? copyOf() : this;
-    }
-
     void setNotCopied() {
         copied = false;
     }
 
     /*
      * Set copy index.
      */
     void setCopyOf(FrameEntry *fe) {
@@ -251,18 +251,25 @@ class FrameEntry
     jsval_layout v_;
     RematInfo  type;
     RematInfo  data;
     uint32     index_;
     FrameEntry *copy;
     bool       copied;
     bool       tracked;
     bool       inlined;
-    bool       initArray;
-    JSObject   *initObject;
-    jsbytecode *lastLoop;
+
+    /*
+     * 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
@@ -35,16 +35,18 @@
  * the provisions above, a recipient may use your version of this file under
  * the terms of any one of the MPL, the GPL or the LGPL.
  *
  * ***** END LICENSE BLOCK ***** */
 
 #if !defined jsjaeger_framestate_inl_h__ && defined JS_METHODJIT
 #define jsjaeger_framestate_inl_h__
 
+#include "methodjit/LoopState.h"
+
 namespace js {
 namespace mjit {
 
 inline void
 FrameState::addToTracker(FrameEntry *fe)
 {
     JS_ASSERT(!fe->isTracked());
     fe->track(a->tracker.nentries);
@@ -82,17 +84,16 @@ FrameState::haveSameBacking(FrameEntry *
     return lhs == rhs;
 }
 
 inline AnyRegisterID
 FrameState::allocReg(uint32 mask)
 {
     if (a->freeRegs.hasRegInMask(mask)) {
         AnyRegisterID reg = a->freeRegs.takeAnyReg(mask);
-        clearLoopReg(reg);
         modifyReg(reg);
         return reg;
     }
 
     AnyRegisterID reg = evictSomeReg(mask);
     regstate(reg).forget();
     modifyReg(reg);
     return reg;
@@ -118,27 +119,30 @@ FrameState::allocAndLoadReg(FrameEntry *
 
     /*
      * Decide whether to retroactively mark a register as holding the entry
      * at the start of the current loop. We can do this if (a) the register has
      * not been touched since the start of the loop (it is in loopRegs), and (b)
      * the entry has also not been written to or already had a loop register
      * assigned.
      */
-    if (a->freeRegs.hasRegInMask(loopRegs.freeMask & mask) && type == RematInfo::DATA &&
-        (fe == this_ || isArg(fe) || isLocal(fe)) && fe->lastLoop < activeLoop->head &&
+    if (loop && a->freeRegs.hasRegInMask(loop->getLoopRegs() & mask) &&
+        type == RematInfo::DATA &&
+        (fe == this_ || isArg(fe) || isLocal(fe)) &&
+        fe->lastLoop < loop->headOffset() &&
         !a->parent) {
-        reg = a->freeRegs.takeAnyReg(loopRegs.freeMask & mask);
-        setLoopReg(reg, fe);
+        reg = a->freeRegs.takeAnyReg(loop->getLoopRegs() & mask);
+        regstate(reg).associate(fe, RematInfo::DATA);
+        fe->lastLoop = loop->headOffset();
+        loop->setLoopReg(reg, fe);
         return reg;
     }
 
     if (!a->freeRegs.empty(mask)) {
         reg = a->freeRegs.takeAnyReg(mask);
-        clearLoopReg(reg);
     } else {
         reg = evictSomeReg(mask);
         regstate(reg).forget();
     }
     modifyReg(reg);
 
     if (fp)
         masm.loadDouble(addressOf(fe), reg.fpreg());
@@ -153,27 +157,18 @@ FrameState::allocAndLoadReg(FrameEntry *
 
 inline void
 FrameState::modifyReg(AnyRegisterID reg)
 {
     if (a->parentRegs.hasReg(reg)) {
         a->parentRegs.takeReg(reg);
         syncParentRegister(masm, reg);
     }
-}
-
-inline void
-FrameState::clearLoopReg(AnyRegisterID reg)
-{
-    JS_ASSERT(loopRegs.hasReg(reg) == (activeLoop && activeLoop->alloc->loop(reg)));
-    if (loopRegs.hasReg(reg)) {
-        loopRegs.takeReg(reg);
-        activeLoop->alloc->setUnassigned(reg);
-        JaegerSpew(JSpew_Regalloc, "clearing loop register %s\n", reg.name());
-    }
+    if (loop)
+        loop->clearLoopReg(reg);
 }
 
 inline void
 FrameState::convertInt32ToDouble(Assembler &masm, FrameEntry *fe, FPRegisterID fpreg) const
 {
     JS_ASSERT(!fe->isConstant());
 
     if (fe->isCopy())
--- a/js/src/methodjit/FrameState.cpp
+++ b/js/src/methodjit/FrameState.cpp
@@ -46,24 +46,21 @@ using namespace js::mjit;
 using namespace js::analyze;
 
 /* Because of Value alignment */
 JS_STATIC_ASSERT(sizeof(FrameEntry) % 8 == 0);
 
 FrameState::FrameState(JSContext *cx, mjit::Compiler &cc,
                        Assembler &masm, StubCompiler &stubcc)
   : cx(cx),
-    masm(masm), stubcc(stubcc),
+    masm(masm), cc(cc), stubcc(stubcc),
     a(NULL), script(NULL), entries(NULL),
     callee_(NULL), this_(NULL), args(NULL), locals(NULL),
     spBase(NULL), sp(NULL), PC(NULL),
-    activeLoop(NULL), loopRegs(0),
-    loopJoins(CompilerAllocPolicy(cx, cc)),
-    loopPatches(CompilerAllocPolicy(cx, cc)),
-    inTryBlock(false)
+    loop(NULL), inTryBlock(false)
 {
 }
 
 FrameState::~FrameState()
 {
     while (a) {
         ActiveFrame *parent = a->parent;
 #if defined JS_NUNBOX32
@@ -400,41 +397,44 @@ FrameState::getTemporaryCallRegisters(Fr
 }
 
 void
 FrameState::takeReg(AnyRegisterID reg)
 {
     modifyReg(reg);
     if (a->freeRegs.hasReg(reg)) {
         a->freeRegs.takeReg(reg);
-        clearLoopReg(reg);
         JS_ASSERT(!regstate(reg).usedBy());
     } else {
         JS_ASSERT(regstate(reg).fe());
         evictReg(reg);
         regstate(reg).forget();
     }
 }
 
 #ifdef DEBUG
 const char *
-FrameState::entryName(FrameEntry *fe) const
+FrameState::entryName(const FrameEntry *fe) const
 {
     if (fe == this_)
         return "'this'";
     if (fe == callee_)
         return "callee";
 
-    static char buf[50];
+    static char bufs[4][50];
+    static unsigned which = 0;
+    which = (which + 1) & 3;
+    char *buf = bufs[which];
+
     if (isArg(fe))
-        JS_snprintf(buf, sizeof(buf), "arg %d", fe - args);
+        JS_snprintf(buf, 50, "arg%d", fe - args);
     else if (isLocal(fe))
-        JS_snprintf(buf, sizeof(buf), "local %d", fe - locals);
+        JS_snprintf(buf, 50, "local%d", fe - locals);
     else
-        JS_snprintf(buf, sizeof(buf), "slot %d", fe - spBase);
+        JS_snprintf(buf, 50, "slot%d", fe - spBase);
     return buf;
 }
 #endif
 
 void
 FrameState::evictReg(AnyRegisterID reg)
 {
     FrameEntry *fe = regstate(reg).fe();
@@ -452,32 +452,20 @@ FrameState::evictReg(AnyRegisterID reg)
         fe->data.setMemory();
     }
 }
 
 inline Lifetime *
 FrameState::variableLive(FrameEntry *fe, jsbytecode *pc) const
 {
     JS_ASSERT(cx->typeInferenceEnabled());
+    JS_ASSERT(fe < spBase && fe != callee_);
 
     uint32 offset = pc - script->code;
-    if (fe == this_)
-        return a->liveness->thisLive(offset);
-    if (isArg(fe)) {
-        JS_ASSERT(!a->analysis->argEscapes(fe - args));
-        return a->liveness->argLive(fe - args, offset);
-    }
-    if (isLocal(fe)) {
-        JS_ASSERT(!a->analysis->localEscapes(fe - locals));
-        return a->liveness->localLive(fe - locals, offset);
-    }
-
-    /* Liveness not computed for stack and callee entries. */
-    JS_NOT_REACHED("Stack/callee entry");
-    return NULL;
+    return a->liveness->live(indexOfFe(fe), offset);
 }
 
 bool
 FrameState::isEntryCopied(FrameEntry *fe) const
 {
     /*
      * :TODO: It would be better for fe->isCopied() to mean 'is actually copied'
      * rather than 'might have copies', removing the need for this walk.
@@ -574,18 +562,18 @@ FrameState::bestEvictReg(uint32 mask, bo
             JaegerSpew(JSpew_Regalloc, "result: %s (%s) is dead\n", entryName(fe), reg.name());
             return reg;
         }
 
         /*
          * Evict variables which are only live in future loop iterations, and are
          * not carried around the loop in a register.
          */
-        JS_ASSERT_IF(lifetime->loopTail, activeLoop);
-        if (lifetime->loopTail && !activeLoop->alloc->hasAnyReg(indexOfFe(fe))) {
+        JS_ASSERT_IF(lifetime->loopTail, loop);
+        if (lifetime->loopTail && !loop->carriesLoopReg(fe)) {
             JaegerSpew(JSpew_Regalloc, "result: %s (%s) only live in later iterations\n",
                        entryName(fe), reg.name());
             return reg;
         }
 
         JaegerSpew(JSpew_Regalloc, "    %s (%s): %u\n", entryName(fe), reg.name(), lifetime->end);
 
         /*
@@ -677,137 +665,16 @@ FrameState::forgetEverything()
 #ifdef DEBUG
     for (uint32 i = 0; i < Registers::TotalAnyRegisters; i++) {
         AnyRegisterID reg = AnyRegisterID::fromRaw(i);
         JS_ASSERT(!regstate(reg).usedBy());
     }
 #endif
 }
 
-void
-FrameState::flushLoopJoins()
-{
-    JS_ASSERT(cx->typeInferenceEnabled());
-    for (unsigned i = 0; i < loopPatches.length(); i++) {
-        const StubJoinPatch &p = loopPatches[i];
-        stubcc.patchJoin(p.join.index, p.join.script, p.address, p.reg);
-    }
-    loopJoins.clear();
-    loopPatches.clear();
-}
-
-bool
-FrameState::pushLoop(jsbytecode *head, Jump entry, jsbytecode *entryTarget)
-{
-    JS_ASSERT(cx->typeInferenceEnabled());
-    if (activeLoop) {
-        /*
-         * Convert all loop registers in the outer loop into unassigned registers.
-         * We don't keep track of which registers the inner loop uses, so the only
-         * registers that can be carried in the outer loop must be mentioned before
-         * the inner loop starts.
-         */
-        activeLoop->alloc->clearLoops();
-        flushLoopJoins();
-    }
-
-    LoopState *loop = (LoopState *) cx->calloc_(sizeof(*activeLoop));
-    if (!loop)
-        return false;
-
-    loop->outer = activeLoop;
-    loop->head = head;
-    loop->entry = entry;
-    loop->entryTarget = entryTarget;
-    activeLoop = loop;
-
-    RegisterAllocation *&alloc = a->liveness->getCode(head).allocation;
-    JS_ASSERT(!alloc);
-
-    alloc = ArenaNew<RegisterAllocation>(a->liveness->pool, true);
-    if (!alloc)
-        return false;
-
-    loop->alloc = alloc;
-    loopRegs = Registers::AvailAnyRegs;
-    return true;
-}
-
-void
-FrameState::popLoop(jsbytecode *head, Jump *pjump, jsbytecode **ppc)
-{
-    JS_ASSERT(cx->typeInferenceEnabled());
-    JS_ASSERT(activeLoop && activeLoop->head == head && activeLoop->alloc);
-    activeLoop->alloc->clearLoops();
-
-#ifdef DEBUG
-    if (IsJaegerSpewChannelActive(JSpew_Regalloc)) {
-        JaegerSpew(JSpew_Regalloc, "loop allocation at %u:", head - script->code);
-        dumpAllocation(activeLoop->alloc);
-    }
-#endif
-
-    flushLoopJoins();
-
-    activeLoop->entry.linkTo(masm.label(), &masm);
-    prepareForJump(activeLoop->entryTarget, masm, true);
-
-    *pjump = masm.jump();
-    *ppc = activeLoop->entryTarget;
-
-    LoopState *loop = activeLoop->outer;
-
-    cx->free_(activeLoop);
-    activeLoop = loop;
-
-    loopRegs = 0;
-}
-
-void
-FrameState::setLoopReg(AnyRegisterID reg, FrameEntry *fe)
-{
-    JS_ASSERT(cx->typeInferenceEnabled());
-    JS_ASSERT(activeLoop && activeLoop->alloc->loop(reg));
-    loopRegs.takeReg(reg);
-
-    fe->lastLoop = activeLoop->head;
-
-    uint32 slot = indexOfFe(fe);
-    regstate(reg).associate(fe, RematInfo::DATA);
-
-    JaegerSpew(JSpew_Regalloc, "allocating loop register %s for %s\n", reg.name(), entryName(fe));
-
-    activeLoop->alloc->set(reg, slot, true);
-
-    /*
-     * Mark pending rejoins to patch up with the load. We don't do this now as that would
-     * cause us to emit into the slow path, which may be in progress.
-     */
-    for (unsigned i = 0; i < loopJoins.length(); i++) {
-        StubJoinPatch p;
-        p.join = loopJoins[i];
-        p.address = addressOf(fe);
-        p.reg = reg;
-        loopPatches.append(p);
-    }
-
-    if (activeLoop->entryTarget &&
-        activeLoop->entryTarget != activeLoop->head &&
-        PC >= activeLoop->entryTarget) {
-        /*
-         * We've advanced past the entry point of the loop (we're analyzing the condition),
-         * so need to update the register state at that entry point so that the right
-         * things get loaded when we enter the loop.
-         */
-        RegisterAllocation *entry = a->liveness->getCode(activeLoop->entryTarget).allocation;
-        JS_ASSERT(entry && !entry->assigned(reg));
-        entry->set(reg, slot, true);
-    }
-}
-
 #ifdef DEBUG
 void
 FrameState::dumpAllocation(RegisterAllocation *alloc)
 {
     JS_ASSERT(cx->typeInferenceEnabled());
     for (unsigned i = 0; i < Registers::TotalAnyRegisters; i++) {
         AnyRegisterID reg = AnyRegisterID::fromRaw(i);
         if (alloc->assigned(reg)) {
@@ -1654,23 +1521,22 @@ FrameState::sync(Assembler &masm, Uses u
 }
 
 void
 FrameState::syncAndKill(Registers kill, Uses uses, Uses ignore)
 {
     syncParentRegistersInMask(masm, a->parentRegs.freeMask, true);
     JS_ASSERT(a->parentRegs.empty());
 
-    if (activeLoop) {
+    if (loop) {
         /*
          * Drop any remaining loop registers so we don't do any more after-the-fact
          * allocation of the initial register state.
          */
-        activeLoop->alloc->clearLoops();
-        loopRegs = 0;
+        loop->flushRegisters(stubcc);
     }
 
     FrameEntry *spStop = sp - ignore.nuses;
 
     /* Sync all kill-registers up-front. */
     Registers search(kill.freeMask & ~a->freeRegs.freeMask);
     while (!search.empty()) {
         AnyRegisterID reg = search.takeAnyReg();
@@ -2400,18 +2266,18 @@ FrameState::storeLocal(uint32 n, JSValue
     if (a->analysis->localEscapes(n)) {
         JS_ASSERT(local->data.inMemory());
         storeTo(peek(-1), addressOf(local), popGuaranteed);
         return;
     }
 
     storeTop(local, type, popGuaranteed);
 
-    if (activeLoop)
-        local->lastLoop = activeLoop->head;
+    if (loop)
+        local->lastLoop = loop->headOffset();
 
     if (type != JSVAL_TYPE_UNKNOWN && type != JSVAL_TYPE_DOUBLE &&
         fixedType && !a->parent && !local->type.synced()) {
         /* Except when inlining, known types are always in sync for locals. */
         local->type.sync();
     }
 
     if (inTryBlock)
@@ -2428,18 +2294,18 @@ FrameState::storeArg(uint32 n, JSValueTy
     if (a->analysis->argEscapes(n)) {
         JS_ASSERT(arg->data.inMemory());
         storeTo(peek(-1), addressOf(arg), popGuaranteed);
         return;
     }
 
     storeTop(arg, type, popGuaranteed);
 
-    if (activeLoop)
-        arg->lastLoop = activeLoop->head;
+    if (loop)
+        arg->lastLoop = loop->headOffset();
 
     if (type != JSVAL_TYPE_UNKNOWN && type != JSVAL_TYPE_DOUBLE && !arg->type.synced()) {
         /* Known types are always in sync for args. (Frames which update args are not inlined). */
         arg->type.sync();
     }
 
     syncFe(arg);
 }
--- a/js/src/methodjit/FrameState.h
+++ b/js/src/methodjit/FrameState.h
@@ -61,16 +61,17 @@ struct Uses {
 struct Changes {
     explicit Changes(uint32 nchanges)
       : nchanges(nchanges)
     { }
     uint32 nchanges;
 };
 
 class StubCompiler;
+class LoopState;
 
 /*
  * The FrameState keeps track of values on the frame during compilation.
  * The compiler can query FrameState for information about arguments, locals,
  * and stack slots (all hereby referred to as "slots"). Slot information can
  * be requested in constant time. For each slot there is a FrameEntry *. If
  * this is non-NULL, it contains valid information and can be returned.
  *
@@ -673,20 +674,21 @@ class FrameState
     /* Compiler-owned metadata about stack entries, reset on push/pop/copy. */
     struct StackEntryExtra {
         bool initArray;
         JSObject *initObject;
         types::TypeSet *types;
         JSAtom *name;
         void reset() { PodZero(this); }
     };
-    StackEntryExtra& extra(FrameEntry *fe) {
+    StackEntryExtra& extra(const FrameEntry *fe) {
         JS_ASSERT(fe >= spBase && fe < sp);
         return a->extraArray[fe - spBase];
     }
+    StackEntryExtra& extra(uint32 slot) { return extra(entries + slot); }
 
     /*
      * Helper function. Tests if a slot's type is null. Condition must
      * be Equal or NotEqual.
      */
     inline Jump testNull(Assembler::Condition cond, FrameEntry *fe);
 
     /*
@@ -800,16 +802,17 @@ class FrameState
     void assertValidRegisterState() const;
 #endif
 
     // Return an address, relative to the JSStackFrame, that represents where
     // this FrameEntry is stored in memory. Note that this is its canonical
     // address, not its backing store. There is no guarantee that the memory
     // is coherent.
     Address addressOf(const FrameEntry *fe) const { return addressOf(fe, a); }
+    Address addressOf(uint32 slot) const { return addressOf(entries + slot); }
 
     // Returns an address, relative to the JSStackFrame, that represents where
     // this FrameEntry is backed in memory. This is not necessarily its
     // canonical address, but the address for which the payload has been synced
     // to memory. The caller guarantees that the payload has been synced.
     Address addressForDataRemat(const FrameEntry *fe) const;
 
     // Inside an inline frame, the address for the return value in the caller.
@@ -839,50 +842,47 @@ class FrameState
     void shift(int32 n);
 
     inline void setInTryBlock(bool inTryBlock) {
         this->inTryBlock = inTryBlock;
     }
 
     inline uint32 regsInUse() const { return Registers::AvailRegs & ~a->freeRegs.freeMask; }
 
-    bool pushLoop(jsbytecode *head, Jump entry, jsbytecode *entryTarget);
-    void popLoop(jsbytecode *head, Jump *pentry, jsbytecode **pentryTarget);
-
     void setPC(jsbytecode *PC) { this->PC = PC; }
-
-    struct StubJoin {
-        unsigned index;
-        bool script;
-    };
-
-    void addJoin(unsigned index, bool script) {
-        if (activeLoop) {
-            StubJoin r;
-            r.index = index;
-            r.script = script;
-            loopJoins.append(r);
-        }
-    }
+    void setLoop(LoopState *loop) { this->loop = loop; }
 
     void getUnsyncedEntries(uint32 *pdepth, Vector<UnsyncedEntry> *unsyncedEntries);
 
     bool pushActiveFrame(JSScript *script, uint32 argc,
                          analyze::Script *analysis, analyze::LifetimeScript *liveness);
     void popActiveFrame();
 
     void discardLocalRegisters();
     void evictInlineModifiedRegisters(Registers regs);
     void syncParentRegistersInMask(Assembler &masm, uint32 mask, bool update) const;
     void restoreParentRegistersInMask(Assembler &masm, uint32 mask, bool update) const;
     Registers getParentRegs() const { return a->parentRegs; }
 
     void tryCopyRegister(FrameEntry *fe, FrameEntry *callStart);
     Registers getTemporaryCallRegisters(FrameEntry *callStart) const;
 
+    uint32 indexOfFe(const FrameEntry *fe) const {
+        JS_ASSERT(uint32(fe - entries) < feLimit(script));
+        return uint32(fe - entries);
+    }
+
+#ifdef DEBUG
+    const char * entryName(const FrameEntry *fe) const;
+    void dumpAllocation(RegisterAllocation *alloc);
+#else
+    const char * entryName(const FrameEntry *fe) const { return NULL; }
+#endif
+    const char * entryName(uint32 slot) { return entryName(entries + slot); }
+
   private:
     inline AnyRegisterID allocAndLoadReg(FrameEntry *fe, bool fp, RematInfo::RematType type);
     inline void forgetReg(AnyRegisterID reg);
     AnyRegisterID evictSomeReg(uint32 mask);
     void evictReg(AnyRegisterID reg);
     inline FrameEntry *rawPush();
     inline void addToTracker(FrameEntry *fe);
 
@@ -938,20 +938,16 @@ class FrameState
         JS_ASSERT(entries[index].isTracked());
         return &entries[index];
     }
 
     uint32 indexOf(int32 depth) const {
         JS_ASSERT(uint32((sp + depth) - entries) < feLimit(script));
         return uint32((sp + depth) - entries);
     }
-    uint32 indexOfFe(FrameEntry *fe) const {
-        JS_ASSERT(uint32(fe - entries) < feLimit(script));
-        return uint32(fe - entries);
-    }
 
     static uint32 feLimit(JSScript *script) {
         return script->nslots + 2 + (script->fun ? script->fun->nargs : 0);
     }
 
     RegisterState & regstate(AnyRegisterID reg) {
         JS_ASSERT(reg.reg_ < Registers::TotalAnyRegisters);
         return a->regstate_[reg.reg_];
@@ -964,49 +960,42 @@ class FrameState
 
     AnyRegisterID bestEvictReg(uint32 mask, bool includePinned) const;
 
     inline analyze::Lifetime * variableLive(FrameEntry *fe, jsbytecode *pc) const;
     inline bool binaryEntryLive(FrameEntry *fe) const;
     RegisterAllocation * computeAllocation(jsbytecode *target);
     void relocateReg(AnyRegisterID reg, RegisterAllocation *alloc, Uses uses);
 
-    bool isArg(FrameEntry *fe) const {
+    bool isArg(const FrameEntry *fe) const {
         return script->fun && fe >= args && fe - args < script->fun->nargs;
     }
 
-    bool isLocal(FrameEntry *fe) const {
+    bool isLocal(const FrameEntry *fe) const {
         return fe >= locals && fe - locals < script->nfixed;
     }
 
     int32 frameOffset(const FrameEntry *fe, ActiveFrame *a) const;
     Address addressOf(const FrameEntry *fe, ActiveFrame *a) const;
 
     void updateActiveFrame();
     void syncInlinedEntry(FrameEntry *fe, const FrameEntry *parent);
     void associateReg(FrameEntry *fe, RematInfo::RematType type, AnyRegisterID reg);
 
     inline void modifyReg(AnyRegisterID reg);
-    inline void clearLoopReg(AnyRegisterID reg);
-    void setLoopReg(AnyRegisterID reg, FrameEntry *fe);
-    void flushLoopJoins();
 
-#ifdef DEBUG
-    const char * entryName(FrameEntry *fe) const;
-    void dumpAllocation(RegisterAllocation *alloc);
-#else
-    const char * entryName(FrameEntry *fe) const { return NULL; }
-#endif
+    MaybeJump guardArrayLengthBase(FrameEntry *obj, Int32Key key);
 
     void syncParentRegister(Assembler &masm, AnyRegisterID reg) const;
     void restoreParentRegister(Assembler &masm, AnyRegisterID reg) const;
 
   private:
     JSContext *cx;
     Assembler &masm;
+    Compiler &cc;
     StubCompiler &stubcc;
 
     /* State for the active stack frame. */
 
     struct ActiveFrame {
         ActiveFrame *parent;
         jsbytecode *parentPC;
         FrameEntry *parentSP;
@@ -1076,53 +1065,18 @@ class FrameState
     FrameEntry *spBase;
 
     /* Dynamic stack pointer. */
     FrameEntry *sp;
 
     /* Current PC, for managing register allocation. */
     jsbytecode *PC;
 
-    /*
-     * State for managing registers within loops. Calls to functions which
-     * contain loops are not inlined.
-     */
-
-    struct LoopState
-    {
-        LoopState *outer;
-        jsbytecode *head;
-        RegisterAllocation *alloc;
-
-        /*
-         * Jump which initially enters the loop, and bytecode target of the jump.
-         * The state is synced when this jump occurs, and needs a trampoline
-         * generated to load the right registers before going to entryTarget.
-         */
-        Jump entry;
-        jsbytecode *entryTarget;
-    };
-
     /* Stack of active loops. */
-    LoopState *activeLoop;
-
-    /* Registers available for loop variables. */
-    Registers loopRegs;
-
-    /* Prior stub rejoins to patch when new loop registers are allocated. */
-    Vector<StubJoin,16,CompilerAllocPolicy> loopJoins;
-
-    struct StubJoinPatch {
-        StubJoin join;
-        Address address;
-        AnyRegisterID reg;
-    };
-
-    /* Pending loads to patch for stub rejoins. */
-    Vector<StubJoinPatch,16,CompilerAllocPolicy> loopPatches;
+    LoopState *loop;
 
     bool inTryBlock;
 };
 
 /*
  * Register allocation overview. We want to allocate registers at the same time
  * as we emit code, in a single forward pass over the script. This is good both
  * for compilation speed and for design simplicity; we allocate registers for
--- a/js/src/methodjit/Logging.cpp
+++ b/js/src/methodjit/Logging.cpp
@@ -80,16 +80,17 @@ js::JMCheckLogging()
             "  profile       ???\n"
 #ifdef DEBUG
             "  jsops         JS opcodes\n"
 #endif
             "  insns         JS opcodes and generated insns\n"
             "  vmframe       VMFrame contents\n"
             "  pics          PIC patching activity\n"
             "  slowcalls     Calls to slow path functions\n"
+            "  analysis      LICM and other analysis behavior\n"
             "  regalloc      Register allocation behavior\n"
             "  inlin         Call inlining behavior\n"
             "  recompile     Dynamic recompilations\n"
             "  full          everything\n"
             "  notrace       disable trace hints\n"
             "\n"
         );
         exit(0);
@@ -108,16 +109,18 @@ js::JMCheckLogging()
     if (strstr(env, "insns"))
         LoggingBits |= (1 << uint32(JSpew_Insns) | (1 << uint32(JSpew_JSOps)));
     if (strstr(env, "vmframe"))
         LoggingBits |= (1 << uint32(JSpew_VMFrame));
     if (strstr(env, "pics"))
         LoggingBits |= (1 << uint32(JSpew_PICs));
     if (strstr(env, "slowcalls"))
         LoggingBits |= (1 << uint32(JSpew_SlowCalls));
+    if (strstr(env, "analysis"))
+        LoggingBits |= (1 << uint32(JSpew_Analysis));
     if (strstr(env, "regalloc"))
         LoggingBits |= (1 << uint32(JSpew_Regalloc));
     if (strstr(env, "recompile"))
         LoggingBits |= (1 << uint32(JSpew_Recompile));
     if (strstr(env, "inlin"))
         LoggingBits |= (1 << uint32(JSpew_Inlining));
     if (strstr(env, "full"))
         LoggingBits |= 0xFFFFFFFF;
--- a/js/src/methodjit/Logging.h
+++ b/js/src/methodjit/Logging.h
@@ -52,16 +52,17 @@ namespace js {
     _(Abort)                \
     _(Scripts)              \
     _(Prof)                 \
     _(JSOps)                \
     _(Insns)                \
     _(VMFrame)              \
     _(PICs)                 \
     _(SlowCalls)            \
+    _(Analysis)             \
     _(Regalloc)             \
     _(Inlining)             \
     _(Recompile)
 
 enum JaegerSpewChannel {
 #define _(name) JSpew_##name,
     JSPEW_CHAN_MAP(_)
 #undef  _
new file mode 100644
--- /dev/null
+++ b/js/src/methodjit/LoopState.cpp
@@ -0,0 +1,379 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=4 sw=4 et tw=99:
+ *
+ * ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is Mozilla SpiderMonkey JavaScript 1.9 code, released
+ * May 28, 2008.
+ *
+ * The Initial Developer of the Original Code is
+ *   Brendan Eich <brendan@mozilla.org>
+ *
+ * Contributor(s):
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either of the GNU General Public License Version 2 or later (the "GPL"),
+ * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+#include "methodjit/Compiler.h"
+#include "methodjit/LoopState.h"
+
+using namespace js;
+using namespace js::mjit;
+using namespace js::analyze;
+
+LoopState::LoopState(JSContext *cx, JSScript *script,
+                     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)),
+      hoistedBoundsChecks(CompilerAllocPolicy(cx, *cc)),
+      outer(NULL), PC(NULL)
+{
+    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))
+        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);
+    }
+
+    for (unsigned i = 0; i < lifetime->nGrowArrays; i++) {
+        JaegerSpew(JSpew_Analysis, "loop grow array at %u: %s\n", lifetime->head,
+                   lifetime->growArrays[i]->name());
+    }
+
+    RegisterAllocation *&alloc = liveness->getCode(head).allocation;
+    JS_ASSERT(!alloc);
+
+    alloc = ArenaNew<RegisterAllocation>(liveness->pool, true);
+    if (!alloc)
+        return false;
+
+    this->alloc = alloc;
+    this->loopRegs = Registers::AvailAnyRegs;
+    this->PC = head;
+
+    /*
+     * Don't hoist bounds checks or loop invariant code in scripts that have
+     * had indirect modification of their arguments.
+     */
+    if (script->fun) {
+        types::ObjectKind kind = types::TypeSet::GetObjectKind(cx, script->fun->getType());
+        if (kind != types::OBJECT_INLINEABLE_FUNCTION && kind != types::OBJECT_SCRIPTED_FUNCTION)
+            this->skipAnalysis = true;
+    }
+
+    /*
+     * Don't hoist bounds checks or loop invariant code in loops with safe
+     * points in the middle, which the interpreter can join at directly without
+     * performing hoisted bounds checks or doing initial computation of loop
+     * invariant terms.
+     */
+    if (lifetime->hasSafePoints)
+        this->skipAnalysis = true;
+
+    return true;
+}
+
+void
+LoopState::addJoin(unsigned index, bool script)
+{
+    StubJoin r;
+    r.index = index;
+    r.script = script;
+    loopJoins.append(r);
+}
+
+void
+LoopState::flushRegisters(StubCompiler &stubcc)
+{
+    alloc->clearLoops();
+    loopRegs = 0;
+
+    for (unsigned i = 0; i < loopPatches.length(); i++) {
+        const StubJoinPatch &p = loopPatches[i];
+        stubcc.patchJoin(p.join.index, p.join.script, p.address, p.reg);
+    }
+    loopJoins.clear();
+    loopPatches.clear();
+}
+
+bool
+LoopState::loopInvariantEntry(const FrameEntry *fe)
+{
+    uint32 slot = frame.indexOfFe(fe);
+    unsigned nargs = script->fun ? script->fun->nargs : 0;
+
+    if (slot >= 2 + nargs + script->nfixed)
+        return false;
+
+    if (liveness->firstWrite(slot, lifetime) != uint32(-1))
+        return false;
+
+    if (slot == 0) /* callee */
+        return false;
+    if (slot == 1) /* this */
+        return true;
+    slot -= 2;
+
+    if (slot < nargs && !analysis->argEscapes(slot))
+        return true;
+    if (script->fun)
+        slot -= script->fun->nargs;
+
+    return !analysis->localEscapes(slot);
+}
+
+void
+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;
+            return;
+        }
+    }
+
+    HoistedBoundsCheck check;
+    check.arraySlot = arraySlot;
+    check.valueSlot = valueSlot;
+    check.constant = constant;
+    hoistedBoundsChecks.append(check);
+}
+
+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));
+
+    alloc->set(reg, slot, true);
+
+    /*
+     * Mark pending rejoins to patch up with the load. We don't do this now as that would
+     * cause us to emit into the slow path, which may be in progress.
+     */
+    for (unsigned i = 0; i < loopJoins.length(); i++) {
+        StubJoinPatch p;
+        p.join = loopJoins[i];
+        p.address = frame.addressOf(fe);
+        p.reg = reg;
+        loopPatches.append(p);
+    }
+
+    if (lifetime->entry != lifetime->head && PC >= script->code + lifetime->entry) {
+        /*
+         * We've advanced past the entry point of the loop (we're analyzing the condition),
+         * so need to update the register state at that entry point so that the right
+         * things get loaded when we enter the loop.
+         */
+        RegisterAllocation *entry = liveness->getCode(lifetime->entry).allocation;
+        JS_ASSERT(entry && !entry->assigned(reg));
+        entry->set(reg, slot, true);
+    }
+}
+
+bool
+LoopState::hoistArrayLengthCheck(const FrameEntry *obj, const FrameEntry *index)
+{
+    if (skipAnalysis || script->failedBoundsCheck)
+        return false;
+
+    /*
+     * Note: this should only be used when the object is known to be a dense
+     * array (if it is an object at all) whose length has never shrunk.
+     */
+
+    obj = obj->backing();
+    index = index->backing();
+
+    JaegerSpew(JSpew_Analysis, "Trying to hoist bounds check array %s index %s\n",
+               frame.entryName(obj), frame.entryName(index));
+
+    if (!loopInvariantEntry(obj)) {
+        JaegerSpew(JSpew_Analysis, "Object is not loop invariant\n");
+        return false;
+    }
+
+    /*
+     * 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;
+        types::TypeSet *types = cc.getTypeSet(obj);
+        JS_ASSERT(types && !types->unknown());
+        unsigned count = types->getObjectCount();
+        for (unsigned i = 0; i < count; i++) {
+            types::TypeObject *object = types->getObject(i);
+            if (object) {
+                for (unsigned j = 0; j < lifetime->nGrowArrays; j++) {
+                    if (object == growArrays[j]) {
+                        JaegerSpew(JSpew_Analysis, "Object might grow inside loop\n");
+                        return false;
+                    }
+                }
+            }
+        }
+    }
+
+    if (index->isConstant()) {
+        /* Hoist checks on x[n] accesses for constant n. */
+        int32 value = index->getValue().toInt32();
+        JaegerSpew(JSpew_Analysis, "Hoisted as initlen > %d\n", value);
+
+        addHoistedCheck(frame.indexOfFe(obj), uint32(-1), value);
+        return true;
+    }
+
+    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));
+
+        addHoistedCheck(frame.indexOfFe(obj), frame.indexOfFe(index), 0);
+        return true;
+    }
+
+    if (frame.indexOfFe(index) == lifetime->testLHS && lifetime->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 write = liveness->firstWrite(lifetime->testLHS, lifetime);
+        JS_ASSERT(write != LifetimeLoop::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.
+             */
+            types::TypeSet *types = cc.getTypeSet(rhs);
+            if (types->getKnownTypeTag(cx) != JSVAL_TYPE_INT32) {
+                JaegerSpew(JSpew_Analysis, "Branch test may not be on integer\n");
+                return false;
+            }
+        }
+
+        JaegerSpew(JSpew_Analysis, "Hoisted as initlen > %s + %d\n",
+                   (rhs == LifetimeLoop::UNASSIGNED) ? "" : frame.entryName(rhs),
+                   constant);
+
+        addHoistedCheck(frame.indexOfFe(obj), rhs, constant);
+        return true;
+    }
+
+    JaegerSpew(JSpew_Analysis, "No match found\n");
+
+    return false;
+}
+
+bool
+LoopState::checkHoistedBounds(jsbytecode *PC, Assembler &masm, Vector<Jump> *jumps)
+{
+    /*
+     * Emit code to validate all hoisted bounds checks, filling jumps with all
+     * failure paths. This is done from a fully synced state, and all registers
+     * can be used as temporaries. Note: we assume that no modifications to the
+     * terms in the hoisted checks occur between PC and the head of the loop.
+     */
+
+    for (unsigned i = 0; i < hoistedBoundsChecks.length(); i++) {
+        /* Testing: initializedLength(array) > value + constant; */
+        const HoistedBoundsCheck &check = hoistedBoundsChecks[i];
+
+        RegisterID initlen = Registers::ArgReg0;
+        masm.loadPayload(frame.addressOf(check.arraySlot), initlen);
+        masm.load32(Address(initlen, offsetof(JSObject, initializedLength)), initlen);
+
+        if (check.valueSlot != uint32(-1)) {
+            RegisterID value = Registers::ArgReg1;
+            masm.loadPayload(frame.addressOf(check.valueSlot), value);
+            if (check.constant != 0) {
+                Jump overflow = masm.branchAdd32(Assembler::Overflow, Imm32(check.constant), value);
+                if (!jumps->append(overflow))
+                    return false;
+            }
+            Jump j = masm.branch32(Assembler::BelowOrEqual, initlen, value);
+            if (!jumps->append(j))
+                return false;
+        } else {
+            Jump j = masm.branch32(Assembler::BelowOrEqual, initlen, Imm32(check.constant));
+            if (!jumps->append(j))
+                return false;
+        }
+    }
+
+    return true;
+}
new file mode 100644
--- /dev/null
+++ b/js/src/methodjit/LoopState.h
@@ -0,0 +1,188 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=4 sw=4 et tw=99:
+ *
+ * ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is Mozilla SpiderMonkey JavaScript 1.9 code, released
+ * May 28, 2008.
+ *
+ * The Initial Developer of the Original Code is
+ *   Brendan Eich <brendan@mozilla.org>
+ *
+ * Contributor(s):
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either of the GNU General Public License Version 2 or later (the "GPL"),
+ * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+#if !defined jsjaeger_loopstate_h__ && defined JS_METHODJIT
+#define jsjaeger_loopstate_h__
+
+#include "jsanalyze.h"
+#include "methodjit/BaseCompiler.h"
+
+namespace js {
+namespace mjit {
+
+/*
+ * The LoopState keeps track of register and analysis state within the loop
+ * currently being processed by the Compiler.
+ *
+ * There are several analyses we do that are specific to loops: loop carried
+ * registers, bounds check hoisting, and loop invariant code motion. Brief
+ * descriptions of these analyses:
+ *
+ * Loop carried registers. We allocate registers as we emit code, in a single
+ * forward pass over the script. Normally this would mean we need to pick the
+ * register allocation at the head of the loop before any of the body has been
+ * processed. Instead, while processing the loop body we retroactively mark
+ * registers as holding the payload of certain entries at the head (being
+ * carried around the loop), so that the head's allocation ends up holding
+ * registers that are likely to be used shortly. This can be done provided that
+ * (a) the register has not been touched since the loop head, (b) the slot
+ * has not been modified or separately assigned a different register, and (c)
+ * all prior slow path rejoins in the loop are patched with reloads of the
+ * register. The register allocation at the loop head must have all entries
+ * synced, so that prior slow path syncs do not also need patching.
+ *
+ * Bounds check hoisting. If we can determine a loop invariant test which
+ * implies the bounds check at one or more array accesses, we hoist that and
+ * only check it when initially entering the loop (from JIT code or the
+ * interpreter). This condition never needs to be checked again within the
+ * loop, but can be invalidated if the script's arguments are indirectly
+ * written via the 'arguments' property/local (which loop analysis assumes
+ * does not happen) or if the involved arrays shrink dynamically through
+ * assignments to the length property.
+ *
+ * Loop invariant code motion. TODO!
+ */
+
+class LoopState : public MacroAssemblerTypedefs
+{
+    JSContext *cx;
+    JSScript *script;
+    Compiler &cc;
+    FrameState &frame;
+    analyze::Script *analysis;
+    analyze::LifetimeScript *liveness;
+
+    /* Basic information about this loop. */
+    analyze::LifetimeLoop *lifetime;
+
+    /* Allocation at the head of the loop, has all loop carried variables. */
+    RegisterAllocation *alloc;
+
+    /*
+     * Jump which initially enters the loop. The state is synced when this jump
+     * occurs, and needs a trampoline generated to load the right registers
+     * before going to entryTarget.
+     */
+    Jump entry;
+
+    /* Registers available for loop variables. */
+    Registers loopRegs;
+
+    /* Whether to skip all bounds check hoisting and loop invariant code analysis. */
+    bool skipAnalysis;
+
+    /* Prior stub rejoins to patch when new loop registers are allocated. */
+    struct StubJoin {
+        unsigned index;
+        bool script;
+    };
+    Vector<StubJoin,16,CompilerAllocPolicy> loopJoins;
+
+    /* Pending loads to patch for stub rejoins. */
+    struct StubJoinPatch {
+        StubJoin join;
+        Address address;
+        AnyRegisterID reg;
+    };
+    Vector<StubJoinPatch,16,CompilerAllocPolicy> loopPatches;
+
+    /*
+     * Array bounds check hoisted out of the loop. This is a check that needs
+     * to be performed, in terms of the state at the loop head.
+     */
+    struct HoistedBoundsCheck
+    {
+        /* initializedLength(array) > value + constant */
+        uint32 arraySlot;
+        uint32 valueSlot;
+        int32 constant;
+    };
+    Vector<HoistedBoundsCheck, 4, CompilerAllocPolicy> hoistedBoundsChecks;
+
+    bool loopInvariantEntry(const FrameEntry *fe);
+    void addHoistedCheck(uint32 arraySlot, uint32 valueSlot, int32 constant);
+
+  public:
+
+    /* Outer loop to this one, in case of loop nesting. */
+    LoopState *outer;
+
+    /* Current bytecode for compilation. */
+    jsbytecode *PC;
+
+    LoopState(JSContext *cx, JSScript *script,
+              Compiler *cc, FrameState *frame,
+              analyze::Script *analysis, analyze::LifetimeScript *liveness);
+    bool init(jsbytecode *head, Jump entry, jsbytecode *entryTarget);
+
+    uint32 headOffset() { return lifetime->head; }
+    uint32 getLoopRegs() { return loopRegs.freeMask; }
+
+    Jump entryJump() { return entry; }
+    uint32 entryOffset() { return lifetime->entry; }
+
+    /* Whether the payload of slot is carried around the loop in a register. */
+    bool carriesLoopReg(FrameEntry *fe) { return alloc->hasAnyReg(frame.indexOfFe(fe)); }
+
+    void setLoopReg(AnyRegisterID reg, FrameEntry *fe);
+
+    void clearLoopReg(AnyRegisterID reg)
+    {
+        /*
+         * Mark reg as having been modified since the start of the loop; it
+         * cannot subsequently be marked to carry a register around the loop.
+         */
+        JS_ASSERT(loopRegs.hasReg(reg) == alloc->loop(reg));
+        if (loopRegs.hasReg(reg)) {
+            loopRegs.takeReg(reg);
+            alloc->setUnassigned(reg);
+            JaegerSpew(JSpew_Regalloc, "clearing loop register %s\n", reg.name());
+        }
+    }
+
+    void addJoin(unsigned index, bool script);
+    void flushRegisters(StubCompiler &stubcc);
+
+    bool hoistArrayLengthCheck(const FrameEntry *obj, const FrameEntry *id);
+    bool checkHoistedBounds(jsbytecode *PC, Assembler &masm, Vector<Jump> *jumps);
+};
+
+} /* namespace mjit */
+} /* namespace js */
+
+#endif /* jsjaeger_loopstate_h__ */
--- a/js/src/methodjit/MonoIC.cpp
+++ b/js/src/methodjit/MonoIC.cpp
@@ -1265,38 +1265,32 @@ GenerateTypeCheck(JSContext *cx, Assembl
             return false;
     }
 
     if (types->hasType(types::TYPE_NULL)) {
         if (!matches.append(masm.testNull(Assembler::Equal, address)))
             return false;
     }
 
-    if (types->objectCount != 0) {
+    unsigned count = types->getObjectCount();
+    if (count != 0) {
         if (!mismatches->append(masm.testObject(Assembler::NotEqual, address)))
             return false;
         Registers tempRegs(Registers::AvailRegs);
         RegisterID reg = tempRegs.takeAnyReg().reg();
 
         masm.loadPayload(address, reg);
         masm.loadPtr(Address(reg, offsetof(JSObject, type)), reg);
 
-        if (types->objectCount >= 2) {
-            unsigned objectCapacity = types::HashSetCapacity(types->objectCount);
-            for (unsigned i = 0; i < objectCapacity; i++) {
-                types::TypeObject *object = types->objectSet[i];
-                if (object) {
-                    if (!matches.append(masm.branchPtr(Assembler::Equal, reg, ImmPtr(object))))
-                        return false;
-                }
+        for (unsigned i = 0; i < count; i++) {
+            types::TypeObject *object = types->getObject(i);
+            if (object) {
+                if (!matches.append(masm.branchPtr(Assembler::Equal, reg, ImmPtr(object))))
+                    return false;
             }
-        } else {
-            types::TypeObject *object = (types::TypeObject *) types->objectSet;
-            if (!matches.append(masm.branchPtr(Assembler::Equal, reg, ImmPtr(object))))
-                return false;
         }
     }
 
     if (!mismatches->append(masm.jump()))
         return false;
 
     for (unsigned i = 0; i < matches.length(); i++)
         matches[i].linkTo(masm.label(), &masm);
--- a/js/src/methodjit/PolyIC.cpp
+++ b/js/src/methodjit/PolyIC.cpp
@@ -1553,17 +1553,17 @@ class ScopeNameCompiler : public PICStub
             if (!newscript->ensureVarTypes(cx))
                 return cx->compartment->types.checkPendingRecompiles(cx);
             if (shape->getterOp() == GetCallArg)
                 types = newscript->argTypes(slot);
             else if (shape->getterOp() == GetCallVar)
                 types = newscript->localTypes(slot);
         } else {
             JS_ASSERT(!getprop.obj->getParent());
-            if (getprop.obj->getType()->unknownProperties) {
+            if (getprop.obj->getType()->unknownProperties()) {
                 f.script()->typeMonitorResult(cx, f.pc(), types::TYPE_UNKNOWN);
                 return cx->compartment->types.checkPendingRecompiles(cx);
             }
             types = getprop.obj->getType()->getProperty(cx, shape->id, false);
             if (!types)
                 return cx->compartment->types.checkPendingRecompiles(cx);
         }
 
--- a/js/src/methodjit/StubCalls.cpp
+++ b/js/src/methodjit/StubCalls.cpp
@@ -590,19 +590,22 @@ stubs::SetElem(VMFrame &f)
             jsuint length = obj->getDenseArrayInitializedLength();
             jsint i = JSID_TO_INT(id);
             if ((jsuint)i < length) {
                 if (obj->getDenseArrayElement(i).isMagic(JS_ARRAY_HOLE)) {
                     if (js_PrototypeHasIndexedProperties(cx, obj))
                         break;
                     if ((jsuint)i >= obj->getArrayLength() && !obj->setArrayLength(cx, i + 1))
                         THROW();
+                    *f.pc() = JSOP_SETHOLE;
                 }
                 obj->setDenseArrayElement(i, rval);
                 goto end_setelem;
+            } else {
+                *f.pc() = JSOP_SETHOLE;
             }
         }
     } while (0);
     if (!obj->setProperty(cx, id, &rval, strict))
         THROW();
   end_setelem:
     /* :FIXME: Moving the assigned object into the lowest stack slot
      * is a temporary hack. What we actually want is an implementation
@@ -2841,16 +2844,39 @@ stubs::AssertArgumentTypes(VMFrame &f)
         JS_ASSERT(script->thisTypes()->hasType(types::GetValueType(f.cx, fp->thisValue())));
 
     for (unsigned i = 0; i < fun->nargs; i++)
         JS_ASSERT(script->argTypes(i)->hasType(types::GetValueType(f.cx, fp->formalArg(i))));
 }
 #endif
 
 void JS_FASTCALL
+stubs::MissedBoundsCheckEntry(VMFrame &f)
+{
+    /* Recompile the script, and don't hoist any bounds checks. */
+    JS_ASSERT(!f.script()->failedBoundsCheck);
+    f.script()->failedBoundsCheck = true;
+
+    Recompiler recompiler(f.cx, f.script());
+    if (!recompiler.recompile())
+        THROW();
+}
+
+void JS_FASTCALL
+stubs::MissedBoundsCheckHead(VMFrame &f)
+{
+    /*
+     * This stub is needed as we can emit bounds checks in two places when
+     * finishing a loop (for entry from JIT code, and entry from the
+     * interpreter), and need to rejoin at the right one.
+     */
+    stubs::MissedBoundsCheckEntry(f);
+}
+
+void JS_FASTCALL
 stubs::Exception(VMFrame &f)
 {
     f.regs.sp[0] = f.cx->getPendingException();
     f.cx->clearPendingException();
 }
 
 template <bool Clamped>
 int32 JS_FASTCALL
--- a/js/src/methodjit/StubCalls.h
+++ b/js/src/methodjit/StubCalls.h
@@ -221,16 +221,19 @@ void JS_FASTCALL UndefinedHelper(VMFrame
 void JS_FASTCALL NegZeroHelper(VMFrame &f);
 
 void JS_FASTCALL CheckArgumentTypes(VMFrame &f);
 
 #ifdef DEBUG
 void JS_FASTCALL AssertArgumentTypes(VMFrame &f);
 #endif
 
+void JS_FASTCALL MissedBoundsCheckEntry(VMFrame &f);
+void JS_FASTCALL MissedBoundsCheckHead(VMFrame &f);
+
 template <bool strict> int32 JS_FASTCALL ConvertToTypedInt(JSContext *cx, Value *vp);
 void JS_FASTCALL ConvertToTypedFloat(JSContext *cx, Value *vp);
 
 void JS_FASTCALL Exception(VMFrame &f);
 
 JSObject * JS_FASTCALL
 NewDenseUnallocatedArray(VMFrame &f, uint32 length);
 
--- a/js/src/methodjit/StubCompiler.cpp
+++ b/js/src/methodjit/StubCompiler.cpp
@@ -146,18 +146,19 @@ StubCompiler::leave()
  
 void
 StubCompiler::rejoin(Changes changes)
 {
     JaegerSpew(JSpew_Insns, " ---- BEGIN SLOW RESTORE CODE ---- \n");
 
     frame.merge(masm, changes);
 
-    Jump j = masm.jump();
-    frame.addJoin(crossJump(j, cc.getLabel()), false);
+    unsigned index = crossJump(masm.jump(), cc.getLabel());
+    if (cc.loop)
+        cc.loop->addJoin(index, false);
 
     JaegerSpew(JSpew_Insns, " ---- END SLOW RESTORE CODE ---- \n");
 }
 
 void
 StubCompiler::linkRejoin(Jump j)
 {
     crossJump(j, cc.getLabel());
@@ -218,21 +219,24 @@ StubCompiler::crossJump(Jump j, Label L)
     /* This won't underflow, as joins has space preallocated for some entries. */
     return joins.length() - 1;
 }
 
 bool
 StubCompiler::jumpInScript(Jump j, jsbytecode *target)
 {
     if (cc.knownJump(target)) {
-        frame.addJoin(crossJump(j, cc.labelOf(target, cc.inlineIndex())), false);
+        unsigned index = crossJump(j, cc.labelOf(target, cc.inlineIndex()));
+        if (cc.loop)
+            cc.loop->addJoin(index, false);
     } else {
         if (!scriptJoins.append(CrossJumpInScript(j, target, cc.inlineIndex())))
             return false;
-        frame.addJoin(scriptJoins.length() - 1, true);
+        if (cc.loop)
+            cc.loop->addJoin(scriptJoins.length() - 1, true);
     }
     return true;
 }
 
 void
 StubCompiler::patchJoin(unsigned i, bool script, Assembler::Address address, AnyRegisterID reg)
 {
     Jump &j = script ? scriptJoins[i].from : joins[i].from;