Use direct object shape instead of identity as key for deep property cache hits (497789, r=jorendorff).
authorBrendan Eich <brendan@mozilla.org>
Mon, 22 Mar 2010 11:11:44 -0700
changeset 40327 ff6b54ac276de71f3d73801431a001657af421e3
parent 40326 d52333800c73dbef8b0fefab4c41eeec06f63828
child 40328 806dfb7f713db7ec264caa2d616382e86cc5cdcd
push id1
push userroot
push dateTue, 26 Apr 2011 22:38:44 +0000
treeherdermozilla-beta@bfdb6e623a36 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjorendorff
bugs497789
milestone1.9.3a3pre
Use direct object shape instead of identity as key for deep property cache hits (497789, r=jorendorff).
js/src/Makefile.in
js/src/jsapi.cpp
js/src/jscntxt.h
js/src/jsgc.cpp
js/src/jsgc.h
js/src/jsinterp.cpp
js/src/jsinterp.h
js/src/jsinterpinlines.h
js/src/jsiter.h
js/src/jslibmath.h
js/src/jsobj.cpp
js/src/jsops.cpp
js/src/jsparse.cpp
js/src/jspropertytree.cpp
js/src/jspropertytree.h
js/src/jsscope.cpp
js/src/jsscope.h
js/src/jsscopeinlines.h
js/src/jstracer.cpp
js/src/jstracer.h
js/src/tests/js1_5/Regress/jstests.list
--- a/js/src/Makefile.in
+++ b/js/src/Makefile.in
@@ -142,16 +142,17 @@ CPPSRCS		= \
 		jslog2.cpp \
 		jsmath.cpp \
 		jsnum.cpp \
 		jsobj.cpp \
 		json.cpp \
 		jsopcode.cpp \
 		jsparse.cpp \
 		jsprf.cpp \
+		jspropertytree.cpp \
 		jsregexp.cpp \
 		jsscan.cpp \
 		jsscope.cpp \
 		jsscript.cpp \
 		jsstr.cpp \
 		jstask.cpp \
 		jstypedarray.cpp \
 		jsutil.cpp \
@@ -196,16 +197,17 @@ INSTALLED_HEADERS = \
 		jsobj.h \
 		jsobjinlines.h \
 		json.h \
 		jsopcode.tbl \
 		jsopcode.h \
 		jsotypes.h \
 		jsparse.h \
 		jsprf.h \
+		jspropertytree.h \
 		jsproto.tbl \
 		jsprvtd.h \
 		jspubtd.h \
 		jsregexp.h \
 		jsscan.h \
 		jsscope.h \
 		jsscript.h \
 		jsscriptinlines.h \
--- a/js/src/jsapi.cpp
+++ b/js/src/jsapi.cpp
@@ -598,17 +598,17 @@ JSRuntime::init(uint32 maxbytes)
     titleSharingTodo = NO_TITLE_SHARING_TODO;
     debuggerLock = JS_NEW_LOCK();
     if (!debuggerLock)
         return false;
     deallocatorThread = new JSBackgroundThread();
     if (!deallocatorThread || !deallocatorThread->init())
         return false;
 #endif
-    return js_InitPropertyTree(this) && js_InitThreads(this);
+    return propertyTree.init() && js_InitThreads(this);
 }
 
 JSRuntime::~JSRuntime()
 {
 #ifdef DEBUG
     /* Don't hurt everyone in leaky ol' Mozilla with a fatal JS_ASSERT! */
     if (!JS_CLIST_IS_EMPTY(&contextList)) {
         JSContext *cx, *iter = NULL;
@@ -650,17 +650,17 @@ JSRuntime::~JSRuntime()
         JS_DESTROY_CONDVAR(titleSharingDone);
     if (debuggerLock)
         JS_DESTROY_LOCK(debuggerLock);
     if (deallocatorThread) {
         deallocatorThread->cancel();
         delete deallocatorThread;
     }
 #endif
-    js_FinishPropertyTree(this);
+    propertyTree.finish();
 }
 
 
 JS_PUBLIC_API(JSRuntime *)
 JS_NewRuntime(uint32 maxbytes)
 {
 #ifdef DEBUG
     if (!js_NewRuntimeWasCalled) {
@@ -2803,20 +2803,18 @@ JS_SealObject(JSContext *cx, JSObject *o
     ida = JS_Enumerate(cx, obj);
     if (!ida)
         return JS_FALSE;
     JS_DestroyIdArray(cx, ida);
 
     /* Ensure that obj has its own, mutable scope, and seal that scope. */
     JS_LOCK_OBJ(cx, obj);
     scope = js_GetMutableScope(cx, obj);
-    if (scope) {
-        scope->sealingShapeChange(cx);
-        scope->setSealed();
-    }
+    if (scope)
+        scope->seal(cx);
     JS_UNLOCK_OBJ(cx, obj);
     if (!scope)
         return JS_FALSE;
 
     /* If we are not sealing an entire object graph, we're done. */
     if (!deep)
         return JS_TRUE;
 
--- a/js/src/jscntxt.h
+++ b/js/src/jscntxt.h
@@ -44,29 +44,29 @@
  * JS execution context.
  */
 #include <string.h>
 
 #include "jsarena.h" /* Added by JSIFY */
 #include "jsclist.h"
 #include "jslong.h"
 #include "jsatom.h"
-#include "jsversion.h"
 #include "jsdhash.h"
 #include "jsgc.h"
+#include "jshashtable.h"
 #include "jsinterp.h"
 #include "jsobj.h"
+#include "jspropertytree.h"
 #include "jsprvtd.h"
 #include "jspubtd.h"
 #include "jsregexp.h"
 #include "jsutil.h"
 #include "jsarray.h"
 #include "jstask.h"
 #include "jsvector.h"
-#include "jshashtable.h"
 
 #ifdef _MSC_VER
 #pragma warning(push)
 #pragma warning(disable:4100) /* Silence unreferenced formal parameter warnings */
 #pragma warning(push)
 #pragma warning(disable:4355) /* Silence warning about "this" used in base member initializer list */
 #endif
 
@@ -905,23 +905,28 @@ struct JSRuntime {
     /*
      * Security callbacks set on the runtime are used by each context unless
      * an override is set on the context.
      */
     JSSecurityCallbacks *securityCallbacks;
 
     /*
      * Shared scope property tree, and arena-pool for allocating its nodes.
+     * This really should be free of all locking overhead and allocated in
+     * thread-local storage, hence the JS_PROPERTY_TREE(cx) macro.
+     */
+    js::PropertyTree    propertyTree;
+
+#define JS_PROPERTY_TREE(cx) ((cx)->runtime->propertyTree)
+
+    /*
      * The propertyRemovals counter is incremented for every JSScope::clear,
      * and for each JSScope::remove method call that frees a slot in an object.
-     * See js_NativeGet and js_NativeSet in jsobj.c.
+     * See js_NativeGet and js_NativeSet in jsobj.cpp.
      */
-    JSDHashTable        propertyTreeHash;
-    JSScopeProperty     *propertyFreeList;
-    JSArenaPool         propertyArenaPool;
     int32               propertyRemovals;
 
     /* Script filename table. */
     struct JSHashTable  *scriptFilenameTable;
     JSCList             scriptFilenamePrefixes;
 #ifdef JS_THREADSAFE
     PRLock              *scriptFilenameTableLock;
 #endif
--- a/js/src/jsgc.cpp
+++ b/js/src/jsgc.cpp
@@ -3231,17 +3231,17 @@ js_GC(JSContext *cx, JSGCInvocationKind 
     METER(UpdateArenaStats(&rt->gcStats.doubleArenaStats,
                            nlivearenas, nkilledarenas, nthings));
     rt->gcDoubleArenaList.cursor = rt->gcDoubleArenaList.head;
 
     /*
      * Sweep the runtime's property tree after finalizing objects, in case any
      * had watchpoints referencing tree nodes.
      */
-    js_SweepScopeProperties(cx);
+    js::SweepScopeProperties(cx);
 
     /*
      * Sweep script filenames after sweeping functions in the generic loop
      * above. In this way when a scripted function's finalizer destroys the
      * script and calls rt->destroyScriptHook, the hook can still access the
      * script's filename. See bug 323267.
      */
     js_SweepScriptFilenames(rt);
--- a/js/src/jsgc.h
+++ b/js/src/jsgc.h
@@ -43,16 +43,17 @@
  * JS Garbage Collector.
  */
 #include "jsprvtd.h"
 #include "jspubtd.h"
 #include "jsdhash.h"
 #include "jsbit.h"
 #include "jsutil.h"
 #include "jstask.h"
+#include "jsversion.h"
 
 JS_BEGIN_EXTERN_C
 
 #define JSTRACE_XML         3
 
 /*
  * One past the maximum trace kind.
  */
--- a/js/src/jsinterp.cpp
+++ b/js/src/jsinterp.cpp
@@ -99,22 +99,20 @@ using namespace js;
 JS_REQUIRES_STACK JSPropCacheEntry *
 js_FillPropertyCache(JSContext *cx, JSObject *obj,
                      uintN scopeIndex, uintN protoIndex, JSObject *pobj,
                      JSScopeProperty *sprop, JSBool adding)
 {
     JSPropertyCache *cache;
     jsbytecode *pc;
     JSScope *scope;
-    jsuword kshape, vshape, khash;
+    jsuword kshape, vshape;
     JSOp op;
     const JSCodeSpec *cs;
     jsuword vword;
-    ptrdiff_t pcoff;
-    JSAtom *atom;
     JSPropCacheEntry *entry;
 
     JS_ASSERT(!cx->runtime->gcRunning);
     cache = &JS_PROPERTY_CACHE(cx);
 
     /* FIXME bug 489098: consider enabling the property cache for eval. */
     if (js_IsPropertyCacheDisabled(cx) || (cx->fp->flags & JSFRAME_EVAL)) {
         PCMETER(cache->disfills++);
@@ -230,20 +228,18 @@ js_FillPropertyCache(JSContext *cx, JSOb
 #ifdef DEBUG_notme
                         fprintf(stderr,
                                 "branding %p (%s) for funobj %p (%s), shape %lu\n",
                                 pobj, pobj->getClass()->name,
                                 JSVAL_TO_OBJECT(v),
                                 JS_GetFunctionName(GET_FUNCTION_PRIVATE(cx, JSVAL_TO_OBJECT(v))),
                                 OBJ_SHAPE(obj));
 #endif
-                        scope->brandingShapeChange(cx, sprop->slot, v);
-                        if (js_IsPropertyCacheDisabled(cx))  /* check for rt->shapeGen overflow */
+                        if (!scope->brand(cx, sprop->slot, v))
                             return JS_NO_PROP_CACHE_FILL;
-                        scope->setBranded();
                     }
                     vword = JSVAL_OBJECT_TO_PCVAL(v);
                     break;
                 }
             }
         }
 
         /* If getting a value via a stub getter, we can cache the slot. */
@@ -316,57 +312,43 @@ js_FillPropertyCache(JSContext *cx, JSOb
     } while (0);
 
     if (kshape == 0) {
         kshape = OBJ_SHAPE(obj);
         vshape = scope->shape;
     }
     JS_ASSERT(kshape < SHAPE_OVERFLOW_BIT);
 
-    khash = PROPERTY_CACHE_HASH_PC(pc, kshape);
     if (obj == pobj) {
         JS_ASSERT(scopeIndex == 0 && protoIndex == 0);
     } else {
-        if (op == JSOP_LENGTH) {
-            atom = cx->runtime->atomState.lengthAtom;
-        } else {
-            pcoff = (JOF_TYPE(cs->format) == JOF_SLOTATOM) ? SLOTNO_LEN : 0;
-            GET_ATOM_FROM_BYTECODE(cx->fp->script, pc, pcoff, atom);
-        }
-
 #ifdef DEBUG
         if (scopeIndex == 0) {
             JS_ASSERT(protoIndex != 0);
             JS_ASSERT((protoIndex == 1) == (obj->getProto() == pobj));
         }
 #endif
 
         if (scopeIndex != 0 || protoIndex != 1) {
-            khash = PROPERTY_CACHE_HASH_ATOM(atom, obj);
-            PCMETER(if (PCVCAP_TAG(cache->table[khash].vcap) <= 1)
-                        cache->pcrecycles++);
-            pc = (jsbytecode *) atom;
-            kshape = (jsuword) obj;
-
             /*
              * Make sure that a later shadowing assignment will enter
              * PurgeProtoChain and invalidate this entry, bug 479198.
              *
              * This is thread-safe even though obj is not locked. Only the
              * DELEGATE bit of obj->classword can change at runtime, given that
              * obj is native; and the bit is only set, never cleared. And on
              * platforms where another CPU can fail to see this write, it's OK
              * because the property cache and JIT cache are thread-local.
              */
             obj->setDelegate();
         }
     }
     JS_ASSERT(vshape < SHAPE_OVERFLOW_BIT);
 
-    entry = &cache->table[khash];
+    entry = &cache->table[PROPERTY_CACHE_HASH(pc, kshape)];
     PCMETER(PCVAL_IS_NULL(entry->vword) || cache->recycles++);
     entry->kpc = pc;
     entry->kshape = kshape;
     entry->vcap = PCVCAP_MAKE(vshape, scopeIndex, protoIndex);
     entry->vword = vword;
 
     cache->empty = JS_FALSE;
     PCMETER(cache->fills++);
@@ -375,52 +357,51 @@ js_FillPropertyCache(JSContext *cx, JSOb
      * The modfills counter is not exact. It increases if a getter or setter
      * recurse into the interpreter.
      */
     PCMETER(entry == cache->pctestentry || cache->modfills++);
     PCMETER(cache->pctestentry = NULL);
     return entry;
 }
 
+static inline JSAtom *
+GetAtomFromBytecode(JSContext *cx, jsbytecode *pc, JSOp op, const JSCodeSpec &cs)
+{
+    if (op == JSOP_LENGTH)
+        return cx->runtime->atomState.lengthAtom;
+
+    ptrdiff_t pcoff = (JOF_TYPE(cs.format) == JOF_SLOTATOM) ? SLOTNO_LEN : 0;
+    JSAtom *atom;
+    GET_ATOM_FROM_BYTECODE(cx->fp->script, pc, pcoff, atom);
+    return atom;
+}
+
 JS_REQUIRES_STACK JSAtom *
 js_FullTestPropertyCache(JSContext *cx, jsbytecode *pc,
                          JSObject **objp, JSObject **pobjp,
-                         JSPropCacheEntry **entryp)
+                         JSPropCacheEntry *entry)
 {
-    JSOp op;
-    const JSCodeSpec *cs;
-    ptrdiff_t pcoff;
-    JSAtom *atom;
     JSObject *obj, *pobj, *tmp;
-    JSPropCacheEntry *entry;
     uint32 vcap;
 
     JS_ASSERT(uintN((cx->fp->imacpc ? cx->fp->imacpc : pc) - cx->fp->script->code)
               < cx->fp->script->length);
 
-    op = js_GetOpcode(cx, cx->fp->script, pc);
-    cs = &js_CodeSpec[op];
-    if (op == JSOP_LENGTH) {
-        atom = cx->runtime->atomState.lengthAtom;
-    } else {
-        pcoff = (JOF_TYPE(cs->format) == JOF_SLOTATOM) ? SLOTNO_LEN : 0;
-        GET_ATOM_FROM_BYTECODE(cx->fp->script, pc, pcoff, atom);
-    }
+    JSOp op = js_GetOpcode(cx, cx->fp->script, pc);
+    const JSCodeSpec &cs = js_CodeSpec[op];
 
     obj = *objp;
     JS_ASSERT(OBJ_IS_NATIVE(obj));
-    entry = &JS_PROPERTY_CACHE(cx).table[PROPERTY_CACHE_HASH_ATOM(atom, obj)];
-    *entryp = entry;
     vcap = entry->vcap;
 
-    if (entry->kpc != (jsbytecode *) atom) {
-        PCMETER(JS_PROPERTY_CACHE(cx).idmisses++);
-
+    if (entry->kpc != pc) {
+        PCMETER(JS_PROPERTY_CACHE(cx).kpcmisses++);
+
+        JSAtom *atom = GetAtomFromBytecode(cx, pc, op, cs);
 #ifdef DEBUG_notme
-        entry = &JS_PROPERTY_CACHE(cx).table[PROPERTY_CACHE_HASH_PC(pc, OBJ_SHAPE(obj))];
         fprintf(stderr,
                 "id miss for %s from %s:%u"
                 " (pc %u, kpc %u, kshape %u, shape %u)\n",
                 js_AtomToPrintableString(cx, atom),
                 cx->fp->script->filename,
                 js_PCToLineNumber(cx, cx->fp->script, pc),
                 pc - cx->fp->script->code,
                 entry->kpc - cx->fp->script->code,
@@ -429,24 +410,29 @@ js_FullTestPropertyCache(JSContext *cx, 
                 js_Disassemble1(cx, cx->fp->script, pc,
                                 pc - cx->fp->script->code,
                                 JS_FALSE, stderr);
 #endif
 
         return atom;
     }
 
-    if (entry->kshape != (jsuword) obj) {
-        PCMETER(JS_PROPERTY_CACHE(cx).komisses++);
-        return atom;
+    if (entry->kshape != OBJ_SHAPE(obj)) {
+        PCMETER(JS_PROPERTY_CACHE(cx).kshapemisses++);
+        return GetAtomFromBytecode(cx, pc, op, cs);
     }
 
+    /*
+     * PROPERTY_CACHE_TEST handles only the direct and immediate-prototype hit
+     * cases, all others go here. We could embed the target object in the cache
+     * entry but then entry size would be 5 words. Instead we traverse chains.
+     */
     pobj = obj;
 
-    if (JOF_MODE(cs->format) == JOF_NAME) {
+    if (JOF_MODE(cs.format) == JOF_NAME) {
         while (vcap & (PCVCAP_SCOPEMASK << PCVCAP_PROTOBITS)) {
             tmp = pobj->getParent();
             if (!tmp || !OBJ_IS_NATIVE(tmp))
                 break;
             pobj = tmp;
             vcap -= PCVCAP_PROTOSIZE;
         }
 
@@ -456,30 +442,31 @@ js_FullTestPropertyCache(JSContext *cx, 
     while (vcap & PCVCAP_PROTOMASK) {
         tmp = pobj->getProto();
         if (!tmp || !OBJ_IS_NATIVE(tmp))
             break;
         pobj = tmp;
         --vcap;
     }
 
-    if (js_MatchPropertyCacheShape(cx, pobj, PCVCAP_SHAPE(vcap))) {
+    if (JSPropCacheEntry::matchShape(cx, pobj, PCVCAP_SHAPE(vcap))) {
 #ifdef DEBUG
+        JSAtom *atom = GetAtomFromBytecode(cx, pc, op, cs);
         jsid id = ATOM_TO_JSID(atom);
 
         id = js_CheckForStringIndex(id);
         JS_ASSERT(OBJ_SCOPE(pobj)->lookup(id));
         JS_ASSERT_IF(OBJ_SCOPE(pobj)->object, OBJ_SCOPE(pobj)->object == pobj);
 #endif
         *pobjp = pobj;
         return NULL;
     }
 
-    PCMETER(JS_PROPERTY_CACHE(cx).vcmisses++);
-    return atom;
+    PCMETER(JS_PROPERTY_CACHE(cx).vcapmisses++);
+    return GetAtomFromBytecode(cx, pc, op, cs);
 }
 
 #ifdef DEBUG
 #define ASSERT_CACHE_IS_EMPTY(cache)                                          \
     JS_BEGIN_MACRO                                                            \
         JSPropertyCache *cache_ = (cache);                                    \
         uintN i_;                                                             \
         JS_ASSERT(cache_->empty);                                             \
@@ -524,31 +511,30 @@ js_PurgePropertyCache(JSContext *cx, JSP
         P(rofills);
         P(disfills);
         P(oddfills);
         P(modfills);
         P(brandfills);
         P(noprotos);
         P(longchains);
         P(recycles);
-        P(pcrecycles);
         P(tests);
         P(pchits);
         P(protopchits);
         P(initests);
         P(inipchits);
         P(inipcmisses);
         P(settests);
         P(addpchits);
         P(setpchits);
         P(setpcmisses);
         P(setmisses);
-        P(idmisses);
-        P(komisses);
-        P(vcmisses);
+        P(kpcmisses);
+        P(kshapemisses);
+        P(vcapmisses);
         P(misses);
         P(flushes);
         P(pcpurges);
 # undef P
 
         fprintf(fp, "hit rates: pc %g%% (proto %g%%), set %g%%, ini %g%%, full %g%%\n",
                 (100. * cache->pchits) / cache->tests,
                 (100. * cache->protopchits) / cache->tests,
@@ -562,27 +548,25 @@ js_PurgePropertyCache(JSContext *cx, JSP
 #endif
 
     PCMETER(cache->flushes++);
 }
 
 void
 js_PurgePropertyCacheForScript(JSContext *cx, JSScript *script)
 {
-    JSPropertyCache *cache;
-    JSPropCacheEntry *entry;
-
-    cache = &JS_PROPERTY_CACHE(cx);
-    for (entry = cache->table; entry < cache->table + PROPERTY_CACHE_SIZE;
+    JSPropertyCache *cache = &JS_PROPERTY_CACHE(cx);
+
+    for (JSPropCacheEntry *entry = cache->table;
+         entry < cache->table + PROPERTY_CACHE_SIZE;
          entry++) {
         if (JS_UPTRDIFF(entry->kpc, script->code) < script->length) {
             entry->kpc = NULL;
-            entry->kshape = 0;
 #ifdef DEBUG
-            entry->vcap = entry->vword = 0;
+            entry->kshape = entry->vcap = entry->vword = 0;
 #endif
         }
     }
 }
 
 /*
  * Check if the current arena has enough space to fit nslots after sp and, if
  * so, reserve the necessary space.
--- a/js/src/jsinterp.h
+++ b/js/src/jsinterp.h
@@ -239,22 +239,16 @@ typedef struct JSInlineFrame {
  * Add kshape rather than xor it to avoid collisions between nearby bytecode
  * that are evolving an object by setting successive properties, incrementing
  * the object's scope->shape on each set.
  */
 #define PROPERTY_CACHE_HASH(pc,kshape)                                        \
     (((((jsuword)(pc) >> PROPERTY_CACHE_LOG2) ^ (jsuword)(pc)) + (kshape)) &  \
      PROPERTY_CACHE_MASK)
 
-#define PROPERTY_CACHE_HASH_PC(pc,kshape)                                     \
-    PROPERTY_CACHE_HASH(pc, kshape)
-
-#define PROPERTY_CACHE_HASH_ATOM(atom,obj)                                    \
-    PROPERTY_CACHE_HASH((jsuword)(atom) >> 2, OBJ_SHAPE(obj))
-
 /*
  * Property cache value capability macros.
  */
 #define PCVCAP_PROTOBITS        4
 #define PCVCAP_PROTOSIZE        JS_BIT(PCVCAP_PROTOBITS)
 #define PCVCAP_PROTOMASK        JS_BITMASK(PCVCAP_PROTOBITS)
 
 #define PCVCAP_SCOPEBITS        4
@@ -268,28 +262,30 @@ typedef struct JSInlineFrame {
 #define PCVCAP_MAKE(t,s,p)      ((uint32(t) << PCVCAP_TAGBITS) |              \
                                  ((s) << PCVCAP_PROTOBITS) |                  \
                                  (p))
 #define PCVCAP_SHAPE(t)         ((t) >> PCVCAP_TAGBITS)
 
 #define SHAPE_OVERFLOW_BIT      JS_BIT(32 - PCVCAP_TAGBITS)
 
 struct JSPropCacheEntry {
-    jsbytecode          *kpc;           /* pc if vcap tag is <= 1, else atom */
-    jsuword             kshape;         /* key shape if pc, else obj for atom */
+    jsbytecode          *kpc;           /* pc of cache-testing bytecode */
+    jsuword             kshape;         /* shape of direct (key) object */
     jsuword             vcap;           /* value capability, see above */
     jsuword             vword;          /* value word, see PCVAL_* below */
 
     bool adding() const {
         return PCVCAP_TAG(vcap) == 0 && kshape != PCVCAP_SHAPE(vcap);
     }
 
     bool directHit() const {
         return PCVCAP_TAG(vcap) == 0 && kshape == PCVCAP_SHAPE(vcap);
     }
+
+    static inline bool matchShape(JSContext *cx, JSObject *obj, uint32 shape);
 };
 
 /*
  * Special value for functions returning JSPropCacheEntry * to distinguish
  * between failure and no no-cache-fill cases.
  */
 #define JS_NO_PROP_CACHE_FILL ((JSPropCacheEntry *) NULL + 1)
 
@@ -308,32 +304,30 @@ typedef struct JSPropertyCache {
     uint32              disfills;       /* fill attempts on disabled cache */
     uint32              oddfills;       /* fill attempt after setter deleted */
     uint32              modfills;       /* fill that rehashed to a new entry */
     uint32              brandfills;     /* scope brandings to type structural
                                            method fills */
     uint32              noprotos;       /* resolve-returned non-proto pobj */
     uint32              longchains;     /* overlong scope and/or proto chain */
     uint32              recycles;       /* cache entries recycled by fills */
-    uint32              pcrecycles;     /* pc-keyed entries recycled by atom-
-                                           keyed fills */
     uint32              tests;          /* cache probes */
     uint32              pchits;         /* fast-path polymorphic op hits */
     uint32              protopchits;    /* pchits hitting immediate prototype */
     uint32              initests;       /* cache probes from JSOP_INITPROP */
     uint32              inipchits;      /* init'ing next property pchit case */
     uint32              inipcmisses;    /* init'ing next property pc misses */
     uint32              settests;       /* cache probes from JOF_SET opcodes */
     uint32              addpchits;      /* adding next property pchit case */
     uint32              setpchits;      /* setting existing property pchit */
     uint32              setpcmisses;    /* setting/adding property pc misses */
     uint32              setmisses;      /* JSOP_SET{NAME,PROP} total misses */
-    uint32              idmisses;       /* slow-path key id == atom misses */
-    uint32              komisses;       /* slow-path key object misses */
-    uint32              vcmisses;       /* value capability misses */
+    uint32              kpcmisses;      /* slow-path key id == atom misses */
+    uint32              kshapemisses;   /* slow-path key object misses */
+    uint32              vcapmisses;     /* value capability misses */
     uint32              misses;         /* cache misses */
     uint32              flushes;        /* cache flushes */
     uint32              pcpurges;       /* shadowing purges on proto chain */
 # define PCMETER(x)     x
 #else
 # define PCMETER(x)     ((void)0)
 #endif
 } JSPropertyCache;
@@ -364,31 +358,28 @@ typedef struct JSPropertyCache {
 #define PCVAL_IS_SLOT(v)        ((v) & PCVAL_SLOT)
 #define PCVAL_TO_SLOT(v)        ((jsuint)(v) >> 1)
 #define SLOT_TO_PCVAL(i)        (((jsuword)(i) << 1) | PCVAL_SLOT)
 
 #define PCVAL_IS_SPROP(v)       (PCVAL_TAG(v) == PCVAL_SPROP)
 #define PCVAL_TO_SPROP(v)       ((JSScopeProperty *) PCVAL_CLRTAG(v))
 #define SPROP_TO_PCVAL(sprop)   PCVAL_SETTAG(sprop, PCVAL_SPROP)
 
-inline bool
-js_MatchPropertyCacheShape(JSContext *cx, JSObject *obj, uint32 shape);
-
 /*
  * Fill property cache entry for key cx->fp->pc, optimized value word computed
  * from obj and sprop, and entry capability forged from 24-bit OBJ_SHAPE(obj),
  * 4-bit scopeIndex, and 4-bit protoIndex.
  *
  * Return the filled cache entry or JS_NO_PROP_CACHE_FILL if caching was not
  * possible.
  */
 extern JS_REQUIRES_STACK JSPropCacheEntry *
 js_FillPropertyCache(JSContext *cx, JSObject *obj,
                      uintN scopeIndex, uintN protoIndex, JSObject *pobj,
-                     JSScopeProperty *sprop, JSBool adding);
+                     JSScopeProperty *sprop, JSBool adding = false);
 
 /*
  * Property cache lookup macros. PROPERTY_CACHE_TEST is designed to inline the
  * fast path in js_Interpret, so it makes "just-so" restrictions on parameters,
  * e.g. pobj and obj should not be the same variable, since for JOF_PROP-mode
  * opcodes, obj must not be changed because of a cache miss.
  *
  * On return from PROPERTY_CACHE_TEST, if atom is null then obj points to the
@@ -400,45 +391,45 @@ js_FillPropertyCache(JSContext *cx, JSOb
  * We must lock pobj on a hit in order to close races with threads that might
  * be deleting a property from its scope, or otherwise invalidating property
  * caches (on all threads) by re-generating scope->shape.
  */
 #define PROPERTY_CACHE_TEST(cx, pc, obj, pobj, entry, atom)                   \
     do {                                                                      \
         JSPropertyCache *cache_ = &JS_PROPERTY_CACHE(cx);                     \
         uint32 kshape_ = (JS_ASSERT(OBJ_IS_NATIVE(obj)), OBJ_SHAPE(obj));     \
-        entry = &cache_->table[PROPERTY_CACHE_HASH_PC(pc, kshape_)];          \
+        entry = &cache_->table[PROPERTY_CACHE_HASH(pc, kshape_)];             \
         PCMETER(cache_->pctestentry = entry);                                 \
         PCMETER(cache_->tests++);                                             \
         JS_ASSERT(&obj != &pobj);                                             \
         if (entry->kpc == pc && entry->kshape == kshape_) {                   \
             JSObject *tmp_;                                                   \
             pobj = obj;                                                       \
-            JS_ASSERT(PCVCAP_TAG(entry->vcap) <= 1);                          \
             if (PCVCAP_TAG(entry->vcap) == 1 &&                               \
                 (tmp_ = pobj->getProto()) != NULL) {                          \
                 pobj = tmp_;                                                  \
             }                                                                 \
                                                                               \
-            if (js_MatchPropertyCacheShape(cx,pobj,PCVCAP_SHAPE(entry->vcap))){\
+            if (JSPropCacheEntry::matchShape(cx, pobj,                        \
+                                             PCVCAP_SHAPE(entry->vcap))) {    \
                 PCMETER(cache_->pchits++);                                    \
                 PCMETER(!PCVCAP_TAG(entry->vcap) || cache_->protopchits++);   \
                 atom = NULL;                                                  \
                 break;                                                        \
             }                                                                 \
         }                                                                     \
-        atom = js_FullTestPropertyCache(cx, pc, &obj, &pobj, &entry);         \
+        atom = js_FullTestPropertyCache(cx, pc, &obj, &pobj, entry);          \
         if (atom)                                                             \
             PCMETER(cache_->misses++);                                        \
     } while (0)
 
 extern JS_REQUIRES_STACK JSAtom *
 js_FullTestPropertyCache(JSContext *cx, jsbytecode *pc,
                          JSObject **objp, JSObject **pobjp,
-                         JSPropCacheEntry **entryp);
+                         JSPropCacheEntry *entry);
 
 /* The property cache does not need a destructor. */
 #define js_FinishPropertyCache(cache) ((void) 0)
 
 extern void
 js_PurgePropertyCache(JSContext *cx, JSPropertyCache *cache);
 
 extern void
--- a/js/src/jsinterpinlines.h
+++ b/js/src/jsinterpinlines.h
@@ -41,16 +41,15 @@
 
 #ifndef jsinterpinlines_h___
 #define jsinterpinlines_h___
 
 #include "jsinterp.h"
 #include "jslock.h"
 #include "jsscope.h"
 
-inline bool
-js_MatchPropertyCacheShape(JSContext *cx, JSObject *obj, uint32 shape)
+/* static */ inline bool
+JSPropCacheEntry::matchShape(JSContext *cx, JSObject *obj, uint32 shape)
 {
     return CX_OWNS_OBJECT_TITLE(cx, obj) && OBJ_SHAPE(obj) == shape;
 }
 
-
 #endif /* jsinterpinlines_h___ */
--- a/js/src/jsiter.h
+++ b/js/src/jsiter.h
@@ -40,16 +40,17 @@
 #ifndef jsiter_h___
 #define jsiter_h___
 
 /*
  * JavaScript iterators.
  */
 #include "jsprvtd.h"
 #include "jspubtd.h"
+#include "jsversion.h"
 
 JS_BEGIN_EXTERN_C
 
 /*
  * NB: these flag bits are encoded into the bytecode stream in the immediate
  * operand of JSOP_ITER, so don't change them without advancing jsxdrapi.h's
  * JSXDR_BYTECODE_VERSION.
  */
--- a/js/src/jslibmath.h
+++ b/js/src/jslibmath.h
@@ -37,17 +37,16 @@
  * the terms of any one of the MPL, the GPL or the LGPL.
  *
  * ***** END LICENSE BLOCK ***** */
 
 #ifndef _LIBMATH_H
 #define _LIBMATH_H
 
 #include <math.h>
-#include "jsversion.h"
 
 /*
  * Use system provided math routines.
  */
 
 /* The right copysign function is not always named the same thing. */
 #if __GNUC__ >= 4 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 #define js_copysign __builtin_copysign
--- a/js/src/jsobj.cpp
+++ b/js/src/jsobj.cpp
@@ -1640,34 +1640,35 @@ js_HasOwnPropertyHelper(JSContext *cx, J
     return JS_TRUE;
 }
 
 JSBool
 js_HasOwnProperty(JSContext *cx, JSLookupPropOp lookup, JSObject *obj, jsid id,
                   JSObject **objp, JSProperty **propp)
 {
     if (!lookup(cx, obj, id, objp, propp))
-        return JS_FALSE;
+        return false;
     if (!*propp)
-        return JS_TRUE;
+        return true;
 
     if (*objp == obj)
-        return JS_TRUE;
+        return true;
 
     JSExtendedClass *xclasp;
     JSObject *outer;
     JSClass *clasp = (*objp)->getClass();
     if (!(clasp->flags & JSCLASS_IS_EXTENDED) ||
         !(xclasp = (JSExtendedClass *) clasp)->outerObject) {
         outer = NULL;
     } else {
         outer = xclasp->outerObject(cx, *objp);
         if (!outer)
-            return JS_FALSE;
-    }
+            return false;
+    }
+
     if (outer != *objp) {
         if (OBJ_IS_NATIVE(*objp) && obj->getClass() == clasp) {
             /*
              * The combination of JSPROP_SHARED and JSPROP_PERMANENT in a
              * delegated property makes that property appear to be direct in
              * all delegating instances of the same native class.  This hack
              * avoids bloating every function instance with its own 'length'
              * (AKA 'arity') property.  But it must not extend across class
@@ -1676,26 +1677,24 @@ js_HasOwnProperty(JSContext *cx, JSLooku
              * It's not really a hack, of course: a permanent property can't
              * be deleted, and JSPROP_SHARED means "don't allocate a slot in
              * any instance, prototype or delegating".  Without a slot, and
              * without the ability to remove and recreate (with differences)
              * the property, there is no way to tell whether it is directly
              * owned, or indirectly delegated.
              */
             JSScopeProperty *sprop = reinterpret_cast<JSScopeProperty *>(*propp);
-            if (!SPROP_IS_SHARED_PERMANENT(sprop)) {
-                (*objp)->dropProperty(cx, *propp);
-                *propp = NULL;
-            }
-        } else {
-            (*objp)->dropProperty(cx, *propp);
-            *propp = NULL;
+            if (sprop->isSharedPermanent())
+                return true;
         }
-    }
-    return JS_TRUE;
+
+        (*objp)->dropProperty(cx, *propp);
+        *propp = NULL;
+    }
+    return true;
 }
 
 #ifdef JS_TRACER
 static JSBool FASTCALL
 Object_p_hasOwnProperty(JSContext* cx, JSObject* obj, JSString *str)
 {
     jsid id;
 
@@ -1782,17 +1781,17 @@ js_PropertyIsEnumerable(JSContext *cx, J
      *
      * We check here for shared permanent prototype properties, which should
      * be treated as if they are local to obj.  They are an implementation
      * technique used to satisfy ECMA requirements; users should not be able
      * to distinguish a shared permanent proto-property from a local one.
      */
     if (pobj != obj &&
         !(OBJ_IS_NATIVE(pobj) &&
-          SPROP_IS_SHARED_PERMANENT((JSScopeProperty *)prop))) {
+          ((JSScopeProperty *)prop)->isSharedPermanent())) {
         pobj->dropProperty(cx, prop);
         *vp = JSVAL_FALSE;
         return JS_TRUE;
     }
 
     ok = pobj->getAttributes(cx, id, prop, &attrs);
     pobj->dropProperty(cx, prop);
     if (ok)
@@ -4755,17 +4754,17 @@ js_FindPropertyHelper(JSContext *cx, jsi
                     JS_ASSERT(!obj->getProto());
                     JS_ASSERT(protoIndex == 0);
                 }
             }
 #endif
             if (cacheResult) {
                 entry = js_FillPropertyCache(cx, scopeChain,
                                              scopeIndex, protoIndex, pobj,
-                                             (JSScopeProperty *) prop, false);
+                                             (JSScopeProperty *) prop);
             }
             SCOPE_DEPTH_ACCUM(&cx->runtime->scopeSearchDepthStats, scopeIndex);
             goto out;
         }
 
         if (!parent) {
             pobj = NULL;
             goto out;
@@ -4838,17 +4837,17 @@ js_FindIdentifierBase(JSContext *cx, JSO
         if (prop) {
             JS_ASSERT(OBJ_IS_NATIVE(pobj));
             JS_ASSERT(OBJ_GET_CLASS(cx, pobj) == OBJ_GET_CLASS(cx, obj));
 #ifdef DEBUG
             JSPropCacheEntry *entry =
 #endif
             js_FillPropertyCache(cx, scopeChain,
                                  scopeIndex, protoIndex, pobj,
-                                 (JSScopeProperty *) prop, false);
+                                 (JSScopeProperty *) prop);
             JS_ASSERT(entry);
             JS_UNLOCK_OBJ(cx, pobj);
             return obj;
         }
 
         /* Call and other cacheable objects always have a parent. */
         obj = obj->getParent();
         if (!obj->getParent())
@@ -5074,17 +5073,17 @@ js_GetPropertyHelper(JSContext *cx, JSOb
         obj2->dropProperty(cx, prop);
         return obj2->getProperty(cx, id, vp);
     }
 
     sprop = (JSScopeProperty *) prop;
 
     if (getHow & JSGET_CACHE_RESULT) {
         JS_ASSERT_NOT_ON_TRACE(cx);
-        js_FillPropertyCache(cx, aobj, 0, protoIndex, obj2, sprop, false);
+        js_FillPropertyCache(cx, aobj, 0, protoIndex, obj2, sprop);
     }
 
     if (!js_NativeGet(cx, obj, obj2, sprop, getHow, vp))
         return JS_FALSE;
 
     JS_UNLOCK_OBJ(cx, obj2);
     return JS_TRUE;
 }
@@ -5263,18 +5262,18 @@ js_SetPropertyHelper(JSContext *cx, JSOb
              * sprop going away behind our back after we've unlocked scope.
              */
             JS_UNLOCK_SCOPE(cx, scope);
 
             /* Don't clone a prototype property that doesn't have a slot. */
             if (!sprop->hasSlot()) {
                 if (defineHow & JSDNP_CACHE_RESULT) {
                     JS_ASSERT_NOT_ON_TRACE(cx);
-                    JSPropCacheEntry *entry;
-                    entry = js_FillPropertyCache(cx, obj, 0, protoIndex, pobj, sprop, false);
+                    JSPropCacheEntry *entry =
+                        js_FillPropertyCache(cx, obj, 0, protoIndex, pobj, sprop);
                     TRACE_2(SetPropHit, entry, sprop);
                 }
 
                 if (sprop->hasDefaultSetter() && !sprop->hasGetterValue())
                     return JS_TRUE;
 
                 return sprop->set(cx, obj, vp);
             }
@@ -5468,17 +5467,17 @@ js_DeleteProperty(JSContext *cx, JSObjec
          * If the property was found in a native prototype, check whether it's
          * shared and permanent.  Such a property stands for direct properties
          * in all delegating objects, matching ECMA semantics without bloating
          * each delegating object.
          */
         if (prop) {
             if (OBJ_IS_NATIVE(proto)) {
                 sprop = (JSScopeProperty *)prop;
-                if (SPROP_IS_SHARED_PERMANENT(sprop))
+                if (sprop->isSharedPermanent())
                     *rval = JSVAL_FALSE;
             }
             proto->dropProperty(cx, prop);
             if (*rval == JSVAL_FALSE)
                 return JS_TRUE;
         }
 
         /*
--- a/js/src/jsops.cpp
+++ b/js/src/jsops.cpp
@@ -1701,152 +1701,154 @@ BEGIN_CASE(JSOP_SETMETHOD)
              * additions. And second:
              *
              *   o.p = x;
              *
              * in a frequently executed method or loop body, where p will
              * (possibly after the first iteration) always exist in native
              * object o.
              */
-            entry = &cache->table[PROPERTY_CACHE_HASH_PC(regs.pc, kshape)];
+            entry = &cache->table[PROPERTY_CACHE_HASH(regs.pc, kshape)];
             PCMETER(cache->pctestentry = entry);
             PCMETER(cache->tests++);
             PCMETER(cache->settests++);
-            if (entry->kpc == regs.pc && entry->kshape == kshape) {
-                JS_ASSERT(PCVCAP_TAG(entry->vcap) <= 1);
-                if (js_MatchPropertyCacheShape(cx, obj, kshape)) {
-                    JS_ASSERT(PCVAL_IS_SPROP(entry->vword));
-                    sprop = PCVAL_TO_SPROP(entry->vword);
-                    JS_ASSERT(sprop->writable());
-                    JS_ASSERT_IF(sprop->hasSlot(), PCVCAP_TAG(entry->vcap) == 0);
-
-                    JSScope *scope = OBJ_SCOPE(obj);
-                    JS_ASSERT(!scope->sealed());
+            if (entry->kpc == regs.pc && entry->kshape == kshape &&
+                JSPropCacheEntry::matchShape(cx, obj, kshape)) {
+                /*
+                 * Property cache hit: either predicting a new property to be
+                 * added directly to obj by this set, or on an existing "own"
+                 * property, or on a prototype property that has a setter.
+                 */
+                JS_ASSERT(PCVAL_IS_SPROP(entry->vword));
+                sprop = PCVAL_TO_SPROP(entry->vword);
+                JS_ASSERT(sprop->writable());
+                JS_ASSERT_IF(sprop->hasSlot(), PCVCAP_TAG(entry->vcap) == 0);
+
+                JSScope *scope = OBJ_SCOPE(obj);
+                JS_ASSERT(!scope->sealed());
+
+                /*
+                 * Fastest path: check whether the cached sprop is already
+                 * in scope and call NATIVE_SET and break to get out of the
+                 * do-while(0). But we can call NATIVE_SET only if obj owns
+                 * scope or sprop is shared.
+                 */
+                bool checkForAdd;
+                if (!sprop->hasSlot()) {
+                    if (PCVCAP_TAG(entry->vcap) == 0 ||
+                        ((obj2 = obj->getProto()) &&
+                         OBJ_IS_NATIVE(obj2) &&
+                         OBJ_SHAPE(obj2) == PCVCAP_SHAPE(entry->vcap))) {
+                        goto fast_set_propcache_hit;
+                    }
+
+                    /* The cache entry doesn't apply. vshape mismatch. */
+                    checkForAdd = false;
+                } else if (!scope->isSharedEmpty()) {
+                    if (sprop == scope->lastProperty() || scope->hasProperty(sprop)) {
+                      fast_set_propcache_hit:
+                        PCMETER(cache->pchits++);
+                        PCMETER(cache->setpchits++);
+                        NATIVE_SET(cx, obj, sprop, entry, &rval);
+                        break;
+                    }
+                    checkForAdd = sprop->hasSlot() && sprop->parent == scope->lastProperty();
+                } else {
+                    /*
+                     * We check that cx own obj here and will continue to
+                     * own it after js_GetMutableScope returns so we can
+                     * continue to skip JS_UNLOCK_OBJ calls.
+                     */
+                    JS_ASSERT(CX_OWNS_OBJECT_TITLE(cx, obj));
+                    scope = js_GetMutableScope(cx, obj);
+                    JS_ASSERT(CX_OWNS_OBJECT_TITLE(cx, obj));
+                    if (!scope)
+                        goto error;
+                    checkForAdd = !sprop->parent;
+                }
+
+                if (checkForAdd &&
+                    PCVCAP_SHAPE(entry->vcap) == rt->protoHazardShape &&
+                    sprop->hasDefaultSetter() &&
+                    (slot = sprop->slot) == scope->freeslot) {
+                    /*
+                     * Fast path: adding a plain old property that was once
+                     * at the frontier of the property tree, whose slot is
+                     * next to claim among the allocated slots in obj,
+                     * where scope->table has not been created yet.
+                     *
+                     * We may want to remove hazard conditions above and
+                     * inline compensation code here, depending on
+                     * real-world workloads.
+                     */
+                    JS_ASSERT(!(obj->getClass()->flags &
+                                JSCLASS_SHARE_ALL_PROPERTIES));
+
+                    PCMETER(cache->pchits++);
+                    PCMETER(cache->addpchits++);
 
                     /*
-                     * Fastest path: check whether the cached sprop is already
-                     * in scope and call NATIVE_SET and break to get out of the
-                     * do-while(0). But we can call NATIVE_SET only if obj owns
-                     * scope or sprop is shared.
+                     * Beware classes such as Function that use the
+                     * reserveSlots hook to allocate a number of reserved
+                     * slots that may vary with obj.
                      */
-                    bool checkForAdd;
-                    if (!sprop->hasSlot()) {
-                        if (PCVCAP_TAG(entry->vcap) == 0 ||
-                            ((obj2 = obj->getProto()) &&
-                             OBJ_IS_NATIVE(obj2) &&
-                             OBJ_SHAPE(obj2) == PCVCAP_SHAPE(entry->vcap))) {
-                            goto fast_set_propcache_hit;
-                        }
-
-                        /* The cache entry doesn't apply. vshape mismatch. */
-                        checkForAdd = false;
-                    } else if (!scope->isSharedEmpty()) {
-                        if (sprop == scope->lastProperty() || scope->hasProperty(sprop)) {
-                          fast_set_propcache_hit:
-                            PCMETER(cache->pchits++);
-                            PCMETER(cache->setpchits++);
-                            NATIVE_SET(cx, obj, sprop, entry, &rval);
-                            break;
-                        }
-                        checkForAdd = sprop->hasSlot() && sprop->parent == scope->lastProperty();
+                    if (slot < STOBJ_NSLOTS(obj) &&
+                        !OBJ_GET_CLASS(cx, obj)->reserveSlots) {
+                        ++scope->freeslot;
                     } else {
-                        /*
-                         * We check that cx own obj here and will continue to
-                         * own it after js_GetMutableScope returns so we can
-                         * continue to skip JS_UNLOCK_OBJ calls.
-                         */
-                        JS_ASSERT(CX_OWNS_OBJECT_TITLE(cx, obj));
-                        scope = js_GetMutableScope(cx, obj);
-                        JS_ASSERT(CX_OWNS_OBJECT_TITLE(cx, obj));
-                        if (!scope)
+                        if (!js_AllocSlot(cx, obj, &slot))
                             goto error;
-                        checkForAdd = !sprop->parent;
                     }
 
-                    if (checkForAdd &&
-                        PCVCAP_SHAPE(entry->vcap) == rt->protoHazardShape &&
-                        sprop->hasDefaultSetter() &&
-                        (slot = sprop->slot) == scope->freeslot) {
-                        /*
-                         * Fast path: adding a plain old property that was once
-                         * at the frontier of the property tree, whose slot is
-                         * next to claim among the allocated slots in obj,
-                         * where scope->table has not been created yet.
-                         *
-                         * We may want to remove hazard conditions above and
-                         * inline compensation code here, depending on
-                         * real-world workloads.
-                         */
-                        JS_ASSERT(!(obj->getClass()->flags &
-                                    JSCLASS_SHARE_ALL_PROPERTIES));
-
-                        PCMETER(cache->pchits++);
-                        PCMETER(cache->addpchits++);
-
-                        /*
-                         * Beware classes such as Function that use the
-                         * reserveSlots hook to allocate a number of reserved
-                         * slots that may vary with obj.
-                         */
-                        if (slot < STOBJ_NSLOTS(obj) &&
-                            !OBJ_GET_CLASS(cx, obj)->reserveSlots) {
-                            ++scope->freeslot;
-                        } else {
-                            if (!js_AllocSlot(cx, obj, &slot))
-                                goto error;
+                    /*
+                     * If this obj's number of reserved slots differed, or
+                     * if something created a hash table for scope, we must
+                     * pay the price of JSScope::putProperty.
+                     *
+                     * (A reserveSlots hook can cause scopes of the same
+                     * shape to have different freeslot values. This is
+                     * what causes the slot != sprop->slot case. See
+                     * js_GetMutableScope.)
+                     */
+                    if (slot != sprop->slot || scope->table) {
+                        JSScopeProperty *sprop2 =
+                            scope->putProperty(cx, sprop->id,
+                                               sprop->getter(), sprop->setter(),
+                                               slot, sprop->attributes(),
+                                               sprop->getFlags(), sprop->shortid);
+                        if (!sprop2) {
+                            js_FreeSlot(cx, obj, slot);
+                            goto error;
                         }
-
-                        /*
-                         * If this obj's number of reserved slots differed, or
-                         * if something created a hash table for scope, we must
-                         * pay the price of JSScope::putProperty.
-                         *
-                         * (A reserveSlots hook can cause scopes of the same
-                         * shape to have different freeslot values. This is
-                         * what causes the slot != sprop->slot case. See
-                         * js_GetMutableScope.)
-                         */
-                        if (slot != sprop->slot || scope->table) {
-                            JSScopeProperty *sprop2 =
-                                scope->putProperty(cx, sprop->id,
-                                                   sprop->getter(), sprop->setter(),
-                                                   slot, sprop->attributes(),
-                                                   sprop->getFlags(), sprop->shortid);
-                            if (!sprop2) {
-                                js_FreeSlot(cx, obj, slot);
-                                goto error;
-                            }
-                            sprop = sprop2;
-                        } else {
-                            scope->extend(cx, sprop);
-                        }
-
-                        /*
-                         * No method change check here because here we are
-                         * adding a new property, not updating an existing
-                         * slot's value that might contain a method of a
-                         * branded scope.
-                         */
-                        TRACE_2(SetPropHit, entry, sprop);
-                        LOCKED_OBJ_SET_SLOT(obj, slot, rval);
-
-                        /*
-                         * Purge the property cache of the id we may have just
-                         * shadowed in obj's scope and proto chains. We do this
-                         * after unlocking obj's scope to avoid lock nesting.
-                         */
-                        js_PurgeScopeChain(cx, obj, sprop->id);
-                        break;
+                        sprop = sprop2;
+                    } else {
+                        scope->extend(cx, sprop);
                     }
-                    PCMETER(cache->setpcmisses++);
+
+                    /*
+                     * No method change check here because here we are
+                     * adding a new property, not updating an existing
+                     * slot's value that might contain a method of a
+                     * branded scope.
+                     */
+                    TRACE_2(SetPropHit, entry, sprop);
+                    LOCKED_OBJ_SET_SLOT(obj, slot, rval);
+
+                    /*
+                     * Purge the property cache of the id we may have just
+                     * shadowed in obj's scope and proto chains. We do this
+                     * after unlocking obj's scope to avoid lock nesting.
+                     */
+                    js_PurgeScopeChain(cx, obj, sprop->id);
+                    break;
                 }
+                PCMETER(cache->setpcmisses++);
             }
 
-            atom = js_FullTestPropertyCache(cx, regs.pc, &obj, &obj2,
-                                            &entry);
+            atom = js_FullTestPropertyCache(cx, regs.pc, &obj, &obj2, entry);
             if (atom) {
                 PCMETER(cache->misses++);
                 PCMETER(cache->setmisses++);
             } else {
                 ASSERT_VALID_PROPERTY_CACHE_HIT(0, obj, obj2, entry);
                 sprop = NULL;
                 if (obj == obj2) {
                     JS_ASSERT(PCVAL_IS_SPROP(entry->vword));
@@ -3388,17 +3390,17 @@ BEGIN_CASE(JSOP_INITMETHOD)
         if (!CX_OWNS_OBJECT_TITLE(cx, obj))
             goto do_initprop_miss;
 
         scope = OBJ_SCOPE(obj);
         JS_ASSERT(scope->object == obj);
         JS_ASSERT(!scope->sealed());
         kshape = scope->shape;
         cache = &JS_PROPERTY_CACHE(cx);
-        entry = &cache->table[PROPERTY_CACHE_HASH_PC(regs.pc, kshape)];
+        entry = &cache->table[PROPERTY_CACHE_HASH(regs.pc, kshape)];
         PCMETER(cache->pctestentry = entry);
         PCMETER(cache->tests++);
         PCMETER(cache->initests++);
 
         if (entry->kpc == regs.pc &&
             entry->kshape == kshape &&
             PCVCAP_SHAPE(entry->vcap) == rt->protoHazardShape) {
             JS_ASSERT(PCVCAP_TAG(entry->vcap) == 0);
--- a/js/src/jsparse.cpp
+++ b/js/src/jsparse.cpp
@@ -6043,16 +6043,17 @@ JSCompiler::condExpr()
     uintN oldflags;
 
     pn = orExpr();
     if (pn && MatchToken(context, &tokenStream, TOK_HOOK)) {
         pn1 = pn;
         pn = TernaryNode::create(tc);
         if (!pn)
             return NULL;
+
         /*
          * Always accept the 'in' operator in the middle clause of a ternary,
          * where it's unambiguous, even if we might be parsing the init of a
          * for statement.
          */
         oldflags = tc->flags;
         tc->flags &= ~TCF_IN_FOR_INIT;
         pn2 = assignExpr();
new file mode 100644
--- /dev/null
+++ b/js/src/jspropertytree.cpp
@@ -0,0 +1,1051 @@
+/* -*- Mode: c++; c-basic-offset: 4; tab-width: 40; indent-tabs-mode: nil -*- */
+/* vim: set ts=40 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 the Mozilla SpiderMonkey property tree implementation
+ *
+ * The Initial Developer of the Original Code is
+ *   Mozilla Foundation
+ * Portions created by the Initial Developer are Copyright (C) 2002-2010
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *   Brendan Eich <brendan@mozilla.org>
+ *
+ * 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 "jstypes.h"
+#include "jsarena.h"
+#include "jsdhash.h"
+#include "jsprf.h"
+#include "jsapi.h"
+#include "jscntxt.h"
+#include "jsgc.h"
+#include "jspropertytree.h"
+#include "jsscope.h"
+
+#include "jsscopeinlines.h"
+
+using namespace js;
+
+struct PropertyRootKey
+{
+    const JSScopeProperty *firstProp;
+    uint32                emptyShape;
+
+    PropertyRootKey(const JSScopeProperty *child, uint32 shape)
+      : firstProp(child), emptyShape(shape) {}
+
+    static JSDHashNumber hash(JSDHashTable *table, const void *key) {
+        const PropertyRootKey *rkey = (const PropertyRootKey *)key;
+
+        return rkey->firstProp->hash() ^ rkey->emptyShape;
+    }
+};
+
+struct PropertyRootEntry : public JSDHashEntryHdr
+{
+    JSScopeProperty *firstProp;
+    uint32          emptyShape;
+    uint32          newEmptyShape;
+
+    static JSBool match(JSDHashTable *table, const JSDHashEntryHdr *hdr, const void *key) {
+        const PropertyRootEntry *rent = (const PropertyRootEntry *)hdr;
+        const PropertyRootKey *rkey = (const PropertyRootKey *)key;
+
+        return rent->firstProp->matches(rkey->firstProp) &&
+               rent->emptyShape == rkey->emptyShape;
+    }
+};
+
+static const JSDHashTableOps PropertyRootHashOps = {
+    JS_DHashAllocTable,
+    JS_DHashFreeTable,
+    PropertyRootKey::hash,
+    PropertyRootEntry::match,
+    JS_DHashMoveEntryStub,
+    JS_DHashClearEntryStub,
+    JS_DHashFinalizeStub,
+    NULL
+};
+
+static JSDHashNumber
+HashScopeProperty(JSDHashTable *table, const void *key)
+{
+    const JSScopeProperty *sprop = (const JSScopeProperty *)key;
+    return sprop->hash();
+}
+
+static JSBool
+MatchScopeProperty(JSDHashTable *table,
+                   const JSDHashEntryHdr *hdr,
+                   const void *key)
+{
+    const JSPropertyTreeEntry *entry = (const JSPropertyTreeEntry *)hdr;
+    const JSScopeProperty *sprop = entry->child;
+    const JSScopeProperty *kprop = (const JSScopeProperty *)key;
+
+    return sprop->matches(kprop);
+}
+
+static const JSDHashTableOps PropertyTreeHashOps = {
+    JS_DHashAllocTable,
+    JS_DHashFreeTable,
+    HashScopeProperty,
+    MatchScopeProperty,
+    JS_DHashMoveEntryStub,
+    JS_DHashClearEntryStub,
+    JS_DHashFinalizeStub,
+    NULL
+};
+
+bool
+PropertyTree::init()
+{
+    if (!JS_DHashTableInit(&hash, &PropertyRootHashOps, NULL,
+                           sizeof(PropertyRootEntry), JS_DHASH_MIN_SIZE)) {
+        hash.ops = NULL;
+        return false;
+    }
+    JS_InitArenaPool(&arenaPool, "properties",
+                     256 * sizeof(JSScopeProperty), sizeof(void *), NULL);
+    emptyShapeChanges = 0;
+    return true;
+}
+
+void
+PropertyTree::finish()
+{
+    if (hash.ops) {
+        JS_DHashTableFinish(&hash);
+        hash.ops = NULL;
+    }
+    JS_FinishArenaPool(&arenaPool);
+}
+
+/*
+ * A property tree node on PropertyTree::freeList overlays the following prefix
+ * struct on JSScopeProperty.
+ */
+typedef struct FreeNode {
+    jsid        id;
+    FreeNode    *next;
+    FreeNode    **prevp;
+
+    void insert(FreeNode *&list) {
+        next = list;
+        prevp = &list;
+        if (list)
+            list->prevp = &next;
+        list = this;
+    }
+
+    void remove() {
+        *prevp = next;
+        if (next)
+            next->prevp = prevp;
+    }
+} FreeNode;
+
+#define FREENODE(sprop) ((FreeNode *) (sprop))
+
+#define FREENODE_INSERT(list, sprop)                                          \
+    JS_BEGIN_MACRO                                                            \
+        union { FreeNode *fn; JSScopeProperty *sp; } u;                       \
+        u.fn = (FreeNode *)(list);                                            \
+        FREENODE(sprop)->insert(u.fn);                                        \
+    JS_END_MACRO
+
+#define FREENODE_REMOVE(sprop)                                                \
+    (FREENODE(sprop)->remove())
+
+/*
+ * NB: Called with cx->runtime->gcLock held if gcLocked is true.
+ * On failure, return null after unlocking the GC and reporting out of memory.
+ */
+JSScopeProperty *
+PropertyTree::newScopeProperty(JSContext *cx, bool gcLocked)
+{
+    JSScopeProperty *sprop;
+
+    if (!gcLocked)
+        JS_LOCK_GC(cx->runtime);
+    sprop = freeList;
+    if (sprop) {
+        FREENODE_REMOVE(sprop);
+    } else {
+        JS_ARENA_ALLOCATE_CAST(sprop, JSScopeProperty *, &arenaPool,
+                               sizeof(JSScopeProperty));
+        if (!sprop) {
+            JS_UNLOCK_GC(cx->runtime);
+            JS_ReportOutOfMemory(cx);
+            return NULL;
+        }
+    }
+    if (!gcLocked)
+        JS_UNLOCK_GC(cx->runtime);
+
+    JS_RUNTIME_METER(cx->runtime, livePropTreeNodes);
+    JS_RUNTIME_METER(cx->runtime, totalPropTreeNodes);
+    return sprop;
+}
+
+#define CHUNKY_KIDS_TAG         ((jsuword)1)
+#define KIDS_IS_CHUNKY(kids)    ((jsuword)(kids) & CHUNKY_KIDS_TAG)
+#define KIDS_TO_CHUNK(kids)     ((PropTreeKidsChunk *)                        \
+                                 ((jsuword)(kids) & ~CHUNKY_KIDS_TAG))
+#define CHUNK_TO_KIDS(chunk)    ((JSScopeProperty *)                          \
+                                 ((jsuword)(chunk) | CHUNKY_KIDS_TAG))
+#define MAX_KIDS_PER_CHUNK      10
+#define CHUNK_HASH_THRESHOLD    30
+
+struct PropTreeKidsChunk {
+    JSScopeProperty     *kids[MAX_KIDS_PER_CHUNK];
+    JSDHashTable        *table;
+    PropTreeKidsChunk   *next;
+};
+
+/*
+ * NB: Called with cx->runtime->gcLock held, always.
+ * On failure, return null after unlocking the GC and reporting out of memory.
+ */
+static PropTreeKidsChunk *
+NewPropTreeKidsChunk(JSContext *cx)
+{
+    PropTreeKidsChunk *chunk;
+
+    chunk = (PropTreeKidsChunk *) js_calloc(sizeof *chunk);
+    if (!chunk) {
+        JS_UNLOCK_GC(cx->runtime);
+        JS_ReportOutOfMemory(cx);
+        return NULL;
+    }
+    JS_ASSERT(((jsuword)chunk & CHUNKY_KIDS_TAG) == 0);
+    JS_RUNTIME_METER(cx->runtime, propTreeKidsChunks);
+    return chunk;
+}
+
+static PropTreeKidsChunk *
+DestroyPropTreeKidsChunk(JSContext *cx, PropTreeKidsChunk *chunk)
+{
+    JS_RUNTIME_UNMETER(cx->runtime, propTreeKidsChunks);
+    if (chunk->table)
+        JS_DHashTableDestroy(chunk->table);
+
+    PropTreeKidsChunk *nextChunk = chunk->next;
+    js_free(chunk);
+    return nextChunk;
+}
+
+/*
+ * NB: Called with cx->runtime->gcLock held, always.
+ * On failure, return null after unlocking the GC and reporting out of memory.
+ */
+bool
+PropertyTree::insertChild(JSContext *cx, JSScopeProperty *parent,
+                          JSScopeProperty *child)
+{
+    JS_ASSERT(parent);
+    JS_ASSERT(!child->parent);
+    JS_ASSERT(!JSVAL_IS_NULL(parent->id));
+    JS_ASSERT(!JSVAL_IS_NULL(child->id));
+
+    JSScopeProperty **childp = &parent->kids;
+    if (JSScopeProperty *kids = *childp) {
+        JSScopeProperty *sprop;
+        PropTreeKidsChunk *chunk;
+
+        if (!KIDS_IS_CHUNKY(kids)) {
+            sprop = kids;
+            JS_ASSERT(sprop != child);
+            if (sprop->matches(child)) {
+                /*
+                 * Duplicate child created while racing to getChild on the same
+                 * node label. See PropertyTree::getChild, further below.
+                 */
+                JS_RUNTIME_METER(cx->runtime, duplicatePropTreeNodes);
+            }
+            chunk = NewPropTreeKidsChunk(cx);
+            if (!chunk)
+                return false;
+            parent->kids = CHUNK_TO_KIDS(chunk);
+            chunk->kids[0] = sprop;
+            childp = &chunk->kids[1];
+        } else {
+            PropTreeKidsChunk **chunkp;
+
+            chunk = KIDS_TO_CHUNK(kids);
+            if (JSDHashTable *table = chunk->table) {
+                JSPropertyTreeEntry *entry = (JSPropertyTreeEntry *)
+                    JS_DHashTableOperate(table, child, JS_DHASH_ADD);
+                if (!entry) {
+                    JS_UNLOCK_GC(cx->runtime);
+                    JS_ReportOutOfMemory(cx);
+                    return false;
+                }
+                if (!entry->child) {
+                    entry->child = child;
+                    while (chunk->next)
+                        chunk = chunk->next;
+                    for (uintN i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
+                        childp = &chunk->kids[i];
+                        sprop = *childp;
+                        if (!sprop)
+                            goto insert;
+                    }
+                    chunkp = &chunk->next;
+                    goto new_chunk;
+                }
+            }
+
+            do {
+                for (uintN i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
+                    childp = &chunk->kids[i];
+                    sprop = *childp;
+                    if (!sprop)
+                        goto insert;
+
+                    JS_ASSERT(sprop != child);
+                    if (sprop->matches(child)) {
+                        /*
+                         * Duplicate child, see comment above.  In this
+                         * case, we must let the duplicate be inserted at
+                         * this level in the tree, so we keep iterating,
+                         * looking for an empty slot in which to insert.
+                         */
+                        JS_ASSERT(sprop != child);
+                        JS_RUNTIME_METER(cx->runtime, duplicatePropTreeNodes);
+                    }
+                }
+                chunkp = &chunk->next;
+            } while ((chunk = *chunkp) != NULL);
+
+          new_chunk:
+            chunk = NewPropTreeKidsChunk(cx);
+            if (!chunk)
+                return false;
+            *chunkp = chunk;
+            childp = &chunk->kids[0];
+        }
+    }
+
+  insert:
+    *childp = child;
+    child->parent = parent;
+    return true;
+}
+
+/* NB: Called with cx->runtime->gcLock held. */
+void
+PropertyTree::removeChild(JSContext *cx, JSScopeProperty *child)
+{
+    uintN i, j;
+    JSPropertyTreeEntry *entry;
+
+    JSScopeProperty *parent = child->parent;
+    JS_ASSERT(parent);
+    JS_ASSERT(!JSVAL_IS_NULL(parent->id));
+
+    JSScopeProperty *kids = parent->kids;
+    if (!KIDS_IS_CHUNKY(kids)) {
+        JSScopeProperty *kid = kids;
+        if (kid == child)
+            parent->kids = NULL;
+        return;
+    }
+
+    PropTreeKidsChunk *list = KIDS_TO_CHUNK(kids);
+    PropTreeKidsChunk *chunk = list;
+    PropTreeKidsChunk **chunkp = &list;
+
+    JSDHashTable *table = chunk->table;
+    PropTreeKidsChunk *freeChunk = NULL;
+
+    do {
+        for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
+            if (chunk->kids[i] == child) {
+                PropTreeKidsChunk *lastChunk = chunk;
+                if (!lastChunk->next) {
+                    j = i + 1;
+                } else {
+                    j = 0;
+                    do {
+                        chunkp = &lastChunk->next;
+                        lastChunk = *chunkp;
+                    } while (lastChunk->next);
+                }
+                for (; j < MAX_KIDS_PER_CHUNK; j++) {
+                    if (!lastChunk->kids[j])
+                        break;
+                }
+                --j;
+                if (chunk != lastChunk || j > i)
+                    chunk->kids[i] = lastChunk->kids[j];
+                lastChunk->kids[j] = NULL;
+                if (j == 0) {
+                    *chunkp = NULL;
+                    if (!list)
+                        parent->kids = NULL;
+                    freeChunk = lastChunk;
+                }
+                goto out;
+            }
+        }
+
+        chunkp = &chunk->next;
+    } while ((chunk = *chunkp) != NULL);
+
+  out:
+    if (table) {
+        entry = (JSPropertyTreeEntry *)
+                JS_DHashTableOperate(table, child, JS_DHASH_LOOKUP);
+
+        if (entry->child == child)
+            JS_DHashTableRawRemove(table, &entry->hdr);
+    }
+    if (freeChunk)
+        DestroyPropTreeKidsChunk(cx, freeChunk);
+}
+
+void
+PropertyTree::emptyShapeChange(uint32 oldEmptyShape, uint32 newEmptyShape)
+{
+    if (oldEmptyShape == newEmptyShape)
+        return;
+
+    PropertyRootEntry *rent = (PropertyRootEntry *) hash.entryStore;
+    PropertyRootEntry *rend = rent + JS_DHASH_TABLE_SIZE(&hash);
+
+    while (rent < rend) {
+        if (rent->emptyShape == oldEmptyShape)
+            rent->newEmptyShape = newEmptyShape;
+        rent++;
+    }
+
+    ++emptyShapeChanges;
+}
+
+static JSDHashTable *
+HashChunks(PropTreeKidsChunk *chunk, uintN n)
+{
+    JSDHashTable *table;
+    uintN i;
+    JSScopeProperty *sprop;
+    JSPropertyTreeEntry *entry;
+
+    table = JS_NewDHashTable(&PropertyTreeHashOps, NULL,
+                             sizeof(JSPropertyTreeEntry),
+                             JS_DHASH_DEFAULT_CAPACITY(n + 1));
+    if (!table)
+        return NULL;
+    do {
+        for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
+            sprop = chunk->kids[i];
+            if (!sprop)
+                break;
+            entry = (JSPropertyTreeEntry *)
+                    JS_DHashTableOperate(table, sprop, JS_DHASH_ADD);
+            entry->child = sprop;
+        }
+    } while ((chunk = chunk->next) != NULL);
+    return table;
+}
+
+/*
+ * Called without cx->runtime->gcLock held. This function acquires that lock
+ * only when inserting a new child.  Thus there may be races to find or add a
+ * node that result in duplicates.  We expect such races to be rare!
+ *
+ * We use cx->runtime->gcLock, not ...->rtLock, to avoid nesting the former
+ * inside the latter in js_GenerateShape below.
+ */
+JSScopeProperty *
+PropertyTree::getChild(JSContext *cx, JSScopeProperty *parent, uint32 shape,
+                       const JSScopeProperty &child)
+{
+    PropertyRootEntry *rent;
+    JSScopeProperty *sprop;
+
+    if (!parent) {
+        PropertyRootKey rkey(&child, shape);
+
+        JS_LOCK_GC(cx->runtime);
+        rent = (PropertyRootEntry *) JS_DHashTableOperate(&hash, &rkey, JS_DHASH_ADD);
+        if (!rent) {
+            JS_UNLOCK_GC(cx->runtime);
+            JS_ReportOutOfMemory(cx);
+            return NULL;
+        }
+
+        sprop = rent->firstProp;
+        if (sprop)
+            goto out;
+    } else {
+        JS_ASSERT(!JSVAL_IS_NULL(parent->id));
+
+        /*
+         * Because chunks are appended at the end and never deleted except by
+         * the GC, we can search without taking the runtime's GC lock.  We may
+         * miss a matching sprop added by another thread, and make a duplicate
+         * one, but that is an unlikely, therefore small, cost.  The property
+         * tree has extremely low fan-out below its root in popular embeddings
+         * with real-world workloads.
+         *
+         * Patterns such as defining closures that capture a constructor's
+         * environment as getters or setters on the new object that is passed
+         * in as |this| can significantly increase fan-out below the property
+         * tree root -- see bug 335700 for details.
+         */
+        rent = NULL;
+        sprop = parent->kids;
+        if (sprop) {
+            if (!KIDS_IS_CHUNKY(sprop)) {
+                if (sprop->matches(&child))
+                    return sprop;
+            } else {
+                PropTreeKidsChunk *chunk = KIDS_TO_CHUNK(sprop);
+
+                if (JSDHashTable *table = chunk->table) {
+                    JS_LOCK_GC(cx->runtime);
+                    JSPropertyTreeEntry *entry = (JSPropertyTreeEntry *)
+                        JS_DHashTableOperate(table, &child, JS_DHASH_LOOKUP);
+                    sprop = entry->child;
+                    if (sprop)
+                        goto out;
+                    goto locked_not_found;
+                }
+
+                uintN n = 0;
+                do {
+                    for (uintN i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
+                        sprop = chunk->kids[i];
+                        if (!sprop) {
+                            n += i;
+                            if (n >= CHUNK_HASH_THRESHOLD) {
+                                chunk = KIDS_TO_CHUNK(parent->kids);
+                                if (!chunk->table) {
+                                    JSDHashTable *table = HashChunks(chunk, n);
+                                    if (!table) {
+                                        JS_ReportOutOfMemory(cx);
+                                        return NULL;
+                                    }
+
+                                    JS_LOCK_GC(cx->runtime);
+                                    if (chunk->table)
+                                        JS_DHashTableDestroy(table);
+                                    else
+                                        chunk->table = table;
+                                    goto locked_not_found;
+                                }
+                            }
+                            goto not_found;
+                        }
+
+                        if (sprop->matches(&child))
+                            return sprop;
+                    }
+                    n += MAX_KIDS_PER_CHUNK;
+                } while ((chunk = chunk->next) != NULL);
+            }
+        }
+
+      not_found:
+        JS_LOCK_GC(cx->runtime);
+    }
+
+  locked_not_found:
+    sprop = newScopeProperty(cx, true);
+    if (!sprop)
+        return NULL;
+
+    new (sprop) JSScopeProperty(child.id, child.rawGetter, child.rawSetter, child.slot,
+                                child.attrs, child.flags, child.shortid);
+    sprop->parent = sprop->kids = NULL;
+    sprop->shape = js_GenerateShape(cx, true);
+
+    if (!parent) {
+        rent->firstProp = sprop;
+        rent->emptyShape = shape;
+        rent->newEmptyShape = 0;
+    } else {
+        if (!PropertyTree::insertChild(cx, parent, sprop))
+            return NULL;
+    }
+
+  out:
+    JS_UNLOCK_GC(cx->runtime);
+    return sprop;
+}
+
+#ifdef DEBUG
+
+static void
+MeterKidCount(JSBasicStats *bs, uintN nkids)
+{
+    JS_BASIC_STATS_ACCUM(bs, nkids);
+    bs->hist[JS_MIN(nkids, 10)]++;
+}
+
+static void
+MeterPropertyTree(JSBasicStats *bs, JSScopeProperty *node)
+{
+    uintN i, nkids;
+    JSScopeProperty *kids, *kid;
+    PropTreeKidsChunk *chunk;
+
+    nkids = 0;
+    kids = node->kids;
+    if (kids) {
+        if (KIDS_IS_CHUNKY(kids)) {
+            for (chunk = KIDS_TO_CHUNK(kids); chunk; chunk = chunk->next) {
+                for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
+                    kid = chunk->kids[i];
+                    if (!kid)
+                        break;
+                    MeterPropertyTree(bs, kid);
+                    nkids++;
+                }
+            }
+        } else {
+            MeterPropertyTree(bs, kids);
+            nkids = 1;
+        }
+    }
+
+    MeterKidCount(bs, nkids);
+}
+
+static JSDHashOperator
+js_MeterPropertyTree(JSDHashTable *table, JSDHashEntryHdr *hdr, uint32 number,
+                     void *arg)
+{
+    PropertyRootEntry *rent = (PropertyRootEntry *)hdr;
+    JSBasicStats *bs = (JSBasicStats *)arg;
+
+    MeterPropertyTree(bs, rent->firstProp);
+    return JS_DHASH_NEXT;
+}
+
+void
+JSScopeProperty::dump(JSContext *cx, FILE *fp)
+{
+    JS_ASSERT(!JSVAL_IS_NULL(id));
+
+    jsval idval = ID_TO_VALUE(id);
+    if (JSVAL_IS_INT(idval)) {
+        fprintf(fp, "[%ld]", (long) JSVAL_TO_INT(idval));
+    } else {
+        JSString *str;
+        if (JSVAL_IS_STRING(idval)) {
+            str = JSVAL_TO_STRING(idval);
+        } else {
+            JS_ASSERT(JSVAL_IS_OBJECT(idval));
+            str = js_ValueToString(cx, idval);
+            fputs("object ", fp);
+        }
+        if (!str)
+            fputs("<error>", fp);
+        else
+            js_FileEscapedString(fp, str, '"');
+    }
+
+    fprintf(fp, " g/s %p/%p slot %u attrs %x ",
+            JS_FUNC_TO_DATA_PTR(void *, rawGetter),
+            JS_FUNC_TO_DATA_PTR(void *, rawSetter),
+            slot, attrs);
+    if (attrs) {
+        int first = 1;
+        fputs("(", fp);
+#define DUMP_ATTR(name, display) if (attrs & JSPROP_##name) fputs(" " #display + first, fp), first = 0
+        DUMP_ATTR(ENUMERATE, enumerate);
+        DUMP_ATTR(READONLY, readonly);
+        DUMP_ATTR(PERMANENT, permanent);
+        DUMP_ATTR(GETTER, getter);
+        DUMP_ATTR(SETTER, setter);
+        DUMP_ATTR(SHARED, shared);
+#undef  DUMP_ATTR
+        fputs(") ", fp);
+    }
+
+    fprintf(fp, "flags %x ", flags);
+    if (flags) {
+        int first = 1;
+        fputs("(", fp);
+#define DUMP_FLAG(name, display) if (flags & name) fputs(" " #display + first, fp), first = 0
+        DUMP_FLAG(ALIAS, alias);
+        DUMP_FLAG(HAS_SHORTID, has_shortid);
+        DUMP_FLAG(METHOD, method);
+        DUMP_FLAG(MARK, mark);
+        DUMP_FLAG(SHAPE_REGEN, shape_regen);
+        DUMP_FLAG(IN_DICTIONARY, in_dictionary);
+#undef  DUMP_FLAG
+        fputs(") ", fp);
+    }
+
+    fprintf(fp, "shortid %d\n", shortid);
+}
+
+void
+JSScopeProperty::dumpSubtree(JSContext *cx, int level, FILE *fp)
+{
+    fprintf(fp, "%*sid ", level, "");
+    dump(cx, fp);
+
+    if (kids) {
+        ++level;
+        if (KIDS_IS_CHUNKY(kids)) {
+            PropTreeKidsChunk *chunk = KIDS_TO_CHUNK(kids);
+            do {
+                for (uintN i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
+                    JSScopeProperty *kid = chunk->kids[i];
+                    if (!kid)
+                        break;
+                    JS_ASSERT(kid->parent == this);
+                    kid->dumpSubtree(cx, level, fp);
+                }
+            } while ((chunk = chunk->next) != NULL);
+        } else {
+            JSScopeProperty *kid = kids;
+            JS_ASSERT(kid->parent == this);
+            kid->dumpSubtree(cx, level, fp);
+        }
+    }
+}
+
+#endif /* DEBUG */
+
+static void
+OrphanNodeKids(JSContext *cx, JSScopeProperty *sprop)
+{
+    JSScopeProperty *kids = sprop->kids;
+
+    JS_ASSERT(kids);
+    sprop->kids = NULL;
+
+    /*
+     * The grandparent must have either no kids or (still, after the
+     * removeChild call above) chunky kids.
+     */
+    JS_ASSERT(!sprop->parent || !sprop->parent->kids ||
+              KIDS_IS_CHUNKY(sprop->parent->kids));
+
+    if (KIDS_IS_CHUNKY(kids)) {
+        PropTreeKidsChunk *chunk = KIDS_TO_CHUNK(kids);
+
+        do {
+            for (uintN i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
+                JSScopeProperty *kid = chunk->kids[i];
+                if (!kid)
+                    break;
+
+                if (!JSVAL_IS_NULL(kid->id)) {
+                    JS_ASSERT(kid->parent == sprop);
+                    kid->parent = NULL;
+                }
+            }
+        } while ((chunk = DestroyPropTreeKidsChunk(cx, chunk)) != NULL);
+    } else {
+        JSScopeProperty *kid = kids;
+
+        if (!JSVAL_IS_NULL(kid->id)) {
+            JS_ASSERT(kid->parent == sprop);
+            kid->parent = NULL;
+        }
+    }
+}
+
+JSDHashOperator
+js::RemoveNodeIfDead(JSDHashTable *table, JSDHashEntryHdr *hdr, uint32 number, void *arg)
+{
+    PropertyRootEntry *rent = (PropertyRootEntry *)hdr;
+    JSScopeProperty *sprop = rent->firstProp;
+
+    JS_ASSERT(!sprop->parent);
+    if (!sprop->marked()) {
+        if (sprop->kids)
+            OrphanNodeKids((JSContext *)arg, sprop);
+        return JS_DHASH_REMOVE;
+    }
+    return JS_DHASH_NEXT;
+}
+
+void
+js::SweepScopeProperties(JSContext *cx)
+{
+    JS_STATIC_ASSERT(offsetof(FreeNode, id) == offsetof(JSScopeProperty, id));
+    JS_STATIC_ASSERT(sizeof(FreeNode) >= offsetof(JSScopeProperty, slot));
+
+#ifdef DEBUG
+    JSBasicStats bs;
+    uint32 livePropCapacity = 0, totalLiveCount = 0;
+    static FILE *logfp;
+    if (!logfp) {
+        if (const char *filename = getenv("JS_PROPTREE_STATFILE"))
+            logfp = fopen(filename, "w");
+    }
+
+    if (logfp) {
+        JS_BASIC_STATS_INIT(&bs);
+        MeterKidCount(&bs, JS_PROPERTY_TREE(cx).hash.entryCount);
+        JS_DHashTableEnumerate(&JS_PROPERTY_TREE(cx).hash, js_MeterPropertyTree, &bs);
+
+        double props, nodes, mean, sigma;
+
+        props = cx->runtime->liveScopePropsPreSweep;
+        nodes = cx->runtime->livePropTreeNodes;
+        JS_ASSERT(nodes == bs.sum);
+        mean = JS_MeanAndStdDevBS(&bs, &sigma);
+
+        fprintf(logfp,
+                "props %g nodes %g beta %g meankids %g sigma %g max %u\n",
+                props, nodes, nodes / props, mean, sigma, bs.max);
+
+        JS_DumpHistogram(&bs, logfp);
+    }
+#endif
+
+    /*
+     * First, remove unmarked nodes from JS_PROPERTY_TREE(cx).hash. This table
+     * requires special handling up front, rather than removal during regular
+     * heap sweeping, because we cannot find an entry in it from the firstProp
+     * node pointer alone -- we would need the emptyShape too.
+     *
+     * Rather than encode emptyShape in firstProp somehow (a tagged overlay on
+     * parent, perhaps, but that would slow down JSScope::search and other hot
+     * paths), we simply orphan kids of garbage nodes in the property tree's
+     * root-ply before sweeping the node heap.
+     */
+    JS_DHashTableEnumerate(&JS_PROPERTY_TREE(cx).hash, RemoveNodeIfDead, cx);
+
+    /*
+     * Second, if any empty scopes have been reshaped, rehash the root ply of
+     * this tree using the new empty shape numbers as key-halves. If we run out
+     * of memory trying to allocate the new hash, disable the property cache by
+     * setting SHAPE_OVERFLOW_BIT in rt->shapeGen. The next GC will therefore
+     * renumber shapes as well as (we hope, eventually) free sufficient memory
+     * for a successful re-run through this code.
+     */
+    if (JS_PROPERTY_TREE(cx).emptyShapeChanges) {
+        JSDHashTable &oldHash = JS_PROPERTY_TREE(cx).hash;
+        uint32 tableSize = JS_DHASH_TABLE_SIZE(&oldHash);
+        JSDHashTable newHash;
+
+        if (!JS_DHashTableInit(&newHash, &PropertyRootHashOps, NULL,
+                               sizeof(PropertyRootEntry), tableSize)) {
+            cx->runtime->shapeGen |= SHAPE_OVERFLOW_BIT;
+        } else {
+            PropertyRootEntry *rent = (PropertyRootEntry *) oldHash.entryStore;
+            PropertyRootEntry *rend = rent + tableSize;
+
+            while (rent < rend) {
+                if (rent->firstProp) {
+                    uint32 emptyShape = rent->newEmptyShape;
+                    if (emptyShape == 0)
+                        emptyShape = rent->emptyShape;
+
+                    PropertyRootKey rkey(rent->firstProp, emptyShape);
+                    PropertyRootEntry *newRent =
+                        (PropertyRootEntry *) JS_DHashTableOperate(&newHash, &rkey, JS_DHASH_ADD);
+
+                    newRent->firstProp = rent->firstProp;
+                    newRent->emptyShape = emptyShape;
+                    newRent->newEmptyShape = 0;
+                }
+                rent++;
+            }
+
+            JS_ASSERT(newHash.generation == 0);
+            JS_DHashTableFinish(&oldHash);
+            JS_PROPERTY_TREE(cx).hash = newHash;
+            JS_PROPERTY_TREE(cx).emptyShapeChanges = 0;
+        }
+    }
+
+    /*
+     * Third, sweep the heap clean of all unmarked nodes. Here we will find
+     * nodes already GC'ed from the root ply, but we will avoid re-orphaning
+     * their kids, because the kids member will already be null.
+     */
+    JSArena **ap = &JS_PROPERTY_TREE(cx).arenaPool.first.next;
+    while (JSArena *a = *ap) {
+        JSScopeProperty *limit = (JSScopeProperty *) a->avail;
+        uintN liveCount = 0;
+
+        for (JSScopeProperty *sprop = (JSScopeProperty *) a->base; sprop < limit; sprop++) {
+            /* If the id is null, sprop is already on the freelist. */
+            if (JSVAL_IS_NULL(sprop->id))
+                continue;
+
+            /*
+             * If the mark bit is set, sprop is alive, so clear the mark bit
+             * and continue the while loop.
+             *
+             * Regenerate sprop->shape if it hasn't already been refreshed
+             * during the mark phase, when live scopes' lastProp members are
+             * followed to update both scope->shape and lastProp->shape.
+             */
+            if (sprop->marked()) {
+                sprop->clearMark();
+                if (cx->runtime->gcRegenShapes) {
+                    if (sprop->hasRegenFlag())
+                        sprop->clearRegenFlag();
+                    else
+                        sprop->shape = js_RegenerateShapeForGC(cx);
+                }
+                liveCount++;
+                continue;
+            }
+
+            if (!sprop->inDictionary()) {
+                /*
+                 * Here, sprop is garbage to collect, but its parent might not
+                 * be, so we may have to remove it from its parent's kids chunk
+                 * list or kid singleton pointer set.
+                 *
+                 * Without a separate mark-clearing pass, we can't tell whether
+                 * sprop->parent is live at this point, so we must remove sprop
+                 * if its parent member is non-null. A saving grace: if sprop's
+                 * parent is dead and swept by this point, sprop->parent will
+                 * be null -- in the next paragraph, we null all of a property
+                 * tree node's kids' parent links when sweeping that node.
+                 */
+                if (sprop->parent)
+                    JS_PROPERTY_TREE(cx).removeChild(cx, sprop);
+
+                if (sprop->kids)
+                    OrphanNodeKids(cx, sprop);
+            }
+
+            /* Clear id so we know (above) that sprop is on the freelist. */
+            sprop->id = JSVAL_NULL;
+            FREENODE_INSERT(JS_PROPERTY_TREE(cx).freeList, sprop);
+            JS_RUNTIME_UNMETER(cx->runtime, livePropTreeNodes);
+        }
+
+        /* If a contains no live properties, return it to the malloc heap. */
+        if (liveCount == 0) {
+            for (JSScopeProperty *sprop = (JSScopeProperty *) a->base; sprop < limit; sprop++)
+                FREENODE_REMOVE(sprop);
+            JS_ARENA_DESTROY(&JS_PROPERTY_TREE(cx).arenaPool, a, ap);
+        } else {
+#ifdef DEBUG
+            livePropCapacity += limit - (JSScopeProperty *) a->base;
+            totalLiveCount += liveCount;
+#endif
+            ap = &a->next;
+        }
+    }
+
+#ifdef DEBUG
+    if (logfp) {
+        fprintf(logfp,
+                "\nProperty tree stats for gcNumber %lu\n",
+                (unsigned long) cx->runtime->gcNumber);
+
+        fprintf(logfp, "arenautil %g%%\n",
+                (totalLiveCount && livePropCapacity)
+                ? (totalLiveCount * 100.0) / livePropCapacity
+                : 0.0);
+
+#define RATE(f1, f2) (((double)js_scope_stats.f1 / js_scope_stats.f2) * 100.0)
+
+        fprintf(logfp,
+                "Scope search stats:\n"
+                "  searches:       %6u\n"
+                "  hits:           %6u %5.2f%% of searches\n"
+                "  misses:         %6u %5.2f%%\n"
+                "  hashes:         %6u %5.2f%%\n"
+                "  steps:          %6u %5.2f%% %5.2f%% of hashes\n"
+                "  stepHits:       %6u %5.2f%% %5.2f%%\n"
+                "  stepMisses:     %6u %5.2f%% %5.2f%%\n"
+                "  tableAllocFails %6u\n"
+                "  toDictFails     %6u\n"
+                "  wrapWatchFails  %6u\n"
+                "  adds:           %6u\n"
+                "  addFails:       %6u\n"
+                "  puts:           %6u\n"
+                "  redundantPuts:  %6u\n"
+                "  putFails:       %6u\n"
+                "  changes:        %6u\n"
+                "  changeFails:    %6u\n"
+                "  compresses:     %6u\n"
+                "  grows:          %6u\n"
+                "  removes:        %6u\n"
+                "  removeFrees:    %6u\n"
+                "  uselessRemoves: %6u\n"
+                "  shrinks:        %6u\n",
+                js_scope_stats.searches,
+                js_scope_stats.hits, RATE(hits, searches),
+                js_scope_stats.misses, RATE(misses, searches),
+                js_scope_stats.hashes, RATE(hashes, searches),
+                js_scope_stats.steps, RATE(steps, searches), RATE(steps, hashes),
+                js_scope_stats.stepHits,
+                RATE(stepHits, searches), RATE(stepHits, hashes),
+                js_scope_stats.stepMisses,
+                RATE(stepMisses, searches), RATE(stepMisses, hashes),
+                js_scope_stats.tableAllocFails,
+                js_scope_stats.toDictFails,
+                js_scope_stats.wrapWatchFails,
+                js_scope_stats.adds,
+                js_scope_stats.addFails,
+                js_scope_stats.puts,
+                js_scope_stats.redundantPuts,
+                js_scope_stats.putFails,
+                js_scope_stats.changes,
+                js_scope_stats.changeFails,
+                js_scope_stats.compresses,
+                js_scope_stats.grows,
+                js_scope_stats.removes,
+                js_scope_stats.removeFrees,
+                js_scope_stats.uselessRemoves,
+                js_scope_stats.shrinks);
+
+#undef RATE
+
+        fflush(logfp);
+    }
+
+    if (const char *filename = getenv("JS_PROPTREE_DUMPFILE")) {
+        char pathname[1024];
+        JS_snprintf(pathname, sizeof pathname, "%s.%lu",
+                    filename, (unsigned long)cx->runtime->gcNumber);
+        FILE *dumpfp = fopen(pathname, "w");
+        if (dumpfp) {
+            PropertyRootEntry *rent = (PropertyRootEntry *) JS_PROPERTY_TREE(cx).hash.entryStore;
+            PropertyRootEntry *rend = rent + JS_DHASH_TABLE_SIZE(&JS_PROPERTY_TREE(cx).hash);
+
+            while (rent < rend) {
+                if (rent->firstProp) {
+                    fprintf(dumpfp, "emptyShape %u ", rent->emptyShape);
+                    rent->firstProp->dumpSubtree(cx, 0, dumpfp);
+                }
+                rent++;
+            }
+            fclose(dumpfp);
+        }
+    }
+#endif /* DEBUG */
+}
new file mode 100644
--- /dev/null
+++ b/js/src/jspropertytree.h
@@ -0,0 +1,82 @@
+/* -*- Mode: c++; c-basic-offset: 4; tab-width: 40; indent-tabs-mode: nil -*- */
+/* vim: set ts=40 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 the Mozilla SpiderMonkey property tree implementation
+ *
+ * The Initial Developer of the Original Code is
+ *   Mozilla Foundation
+ * Portions created by the Initial Developer are Copyright (C) 2002-2010
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *   Brendan Eich <brendan@mozilla.org>
+ *
+ * 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 ***** */
+
+#ifndef jspropertytree_h___
+#define jspropertytree_h___
+
+#include "jsarena.h"
+#include "jsdhash.h"
+#include "jsprvtd.h"
+
+struct JSScope;
+
+namespace js {
+
+JSDHashOperator RemoveNodeIfDead(JSDHashTable *table, JSDHashEntryHdr *hdr,
+                                 uint32 number, void *arg);
+
+void SweepScopeProperties(JSContext *cx);
+
+class PropertyTree
+{
+    friend struct ::JSScope;
+    friend void js::SweepScopeProperties(JSContext *cx);
+
+    JSDHashTable        hash;
+    JSScopeProperty     *freeList;
+    JSArenaPool         arenaPool;
+    uint32              emptyShapeChanges;
+
+    bool insertChild(JSContext *cx, JSScopeProperty *parent, JSScopeProperty *child);
+    void removeChild(JSContext *cx, JSScopeProperty *child);
+    void emptyShapeChange(uint32 oldEmptyShape, uint32 newEmptyShape);
+
+  public:
+    bool init();
+    void finish();
+
+    JSScopeProperty *newScopeProperty(JSContext *cx, bool gcLocked = false);
+
+    JSScopeProperty *getChild(JSContext *cx, JSScopeProperty *parent, uint32 shape,
+                              const JSScopeProperty &child);
+};
+
+} /* namespace js */
+
+#endif /* jspropertytree_h___ */
--- a/js/src/jsscope.cpp
+++ b/js/src/jsscope.cpp
@@ -447,508 +447,16 @@ JSScope::changeTable(JSContext *cx, int 
         oldsize--;
     }
 
     /* Finally, free the old table storage. */
     cx->free(oldtable);
     return true;
 }
 
-static JSDHashNumber
-js_HashScopeProperty(JSDHashTable *table, const void *key)
-{
-    const JSScopeProperty *sprop = (const JSScopeProperty *)key;
-    return sprop->hash();
-}
-
-static JSBool
-js_MatchScopeProperty(JSDHashTable *table,
-                      const JSDHashEntryHdr *hdr,
-                      const void *key)
-{
-    const JSPropertyTreeEntry *entry = (const JSPropertyTreeEntry *)hdr;
-    const JSScopeProperty *sprop = entry->child;
-    const JSScopeProperty *kprop = (const JSScopeProperty *)key;
-
-    return sprop->matches(kprop);
-}
-
-static const JSDHashTableOps PropertyTreeHashOps = {
-    JS_DHashAllocTable,
-    JS_DHashFreeTable,
-    js_HashScopeProperty,
-    js_MatchScopeProperty,
-    JS_DHashMoveEntryStub,
-    JS_DHashClearEntryStub,
-    JS_DHashFinalizeStub,
-    NULL
-};
-
-/*
- * A property tree node on rt->propertyFreeList overlays the following prefix
- * struct on JSScopeProperty.
- */
-typedef struct FreeNode {
-    jsid                id;
-    JSScopeProperty     *next;
-    JSScopeProperty     **prevp;
-} FreeNode;
-
-#define FREENODE(sprop) ((FreeNode *) (sprop))
-
-#define FREENODE_INSERT(list, sprop)                                          \
-    JS_BEGIN_MACRO                                                            \
-        FREENODE(sprop)->next = (list);                                       \
-        FREENODE(sprop)->prevp = &(list);                                     \
-        if (list)                                                             \
-            FREENODE(list)->prevp = &FREENODE(sprop)->next;                   \
-        (list) = (sprop);                                                     \
-    JS_END_MACRO
-
-#define FREENODE_REMOVE(sprop)                                                \
-    JS_BEGIN_MACRO                                                            \
-        *FREENODE(sprop)->prevp = FREENODE(sprop)->next;                      \
-        if (FREENODE(sprop)->next)                                            \
-            FREENODE(FREENODE(sprop)->next)->prevp = FREENODE(sprop)->prevp;  \
-    JS_END_MACRO
-
-/* NB: Called with rt->gcLock held. */
-static JSScopeProperty *
-NewScopeProperty(JSRuntime *rt)
-{
-    JSScopeProperty *sprop;
-
-    sprop = rt->propertyFreeList;
-    if (sprop) {
-        FREENODE_REMOVE(sprop);
-    } else {
-        JS_ARENA_ALLOCATE_CAST(sprop, JSScopeProperty *,
-                               &rt->propertyArenaPool,
-                               sizeof(JSScopeProperty));
-        if (!sprop)
-            return NULL;
-    }
-
-    JS_RUNTIME_METER(rt, livePropTreeNodes);
-    JS_RUNTIME_METER(rt, totalPropTreeNodes);
-    return sprop;
-}
-
-#define CHUNKY_KIDS_TAG         ((jsuword)1)
-#define KIDS_IS_CHUNKY(kids)    ((jsuword)(kids) & CHUNKY_KIDS_TAG)
-#define KIDS_TO_CHUNK(kids)     ((PropTreeKidsChunk *)                        \
-                                 ((jsuword)(kids) & ~CHUNKY_KIDS_TAG))
-#define CHUNK_TO_KIDS(chunk)    ((JSScopeProperty *)                          \
-                                 ((jsuword)(chunk) | CHUNKY_KIDS_TAG))
-#define MAX_KIDS_PER_CHUNK      10
-#define CHUNK_HASH_THRESHOLD    30
-
-typedef struct PropTreeKidsChunk PropTreeKidsChunk;
-
-struct PropTreeKidsChunk {
-    JSScopeProperty     *kids[MAX_KIDS_PER_CHUNK];
-    JSDHashTable        *table;
-    PropTreeKidsChunk   *next;
-};
-
-static PropTreeKidsChunk *
-NewPropTreeKidsChunk(JSRuntime *rt)
-{
-    PropTreeKidsChunk *chunk;
-
-    chunk = (PropTreeKidsChunk *) js_calloc(sizeof *chunk);
-    if (!chunk)
-        return NULL;
-    JS_ASSERT(((jsuword)chunk & CHUNKY_KIDS_TAG) == 0);
-    JS_RUNTIME_METER(rt, propTreeKidsChunks);
-    return chunk;
-}
-
-static void
-DestroyPropTreeKidsChunk(JSRuntime *rt, PropTreeKidsChunk *chunk)
-{
-    JS_RUNTIME_UNMETER(rt, propTreeKidsChunks);
-    if (chunk->table)
-        JS_DHashTableDestroy(chunk->table);
-    js_free(chunk);
-}
-
-/* NB: Called with rt->gcLock held. */
-static bool
-InsertPropertyTreeChild(JSRuntime *rt, JSScopeProperty *parent,
-                        JSScopeProperty *child, PropTreeKidsChunk *sweptChunk)
-{
-    JSDHashTable *table;
-    JSPropertyTreeEntry *entry;
-    JSScopeProperty **childp, *kids, *sprop;
-    PropTreeKidsChunk *chunk, **chunkp;
-    uintN i;
-
-    JS_ASSERT(!parent || child->parent != parent);
-    JS_ASSERT(!JSVAL_IS_NULL(child->id));
-
-    if (!parent) {
-        table = &rt->propertyTreeHash;
-        entry = (JSPropertyTreeEntry *)
-                JS_DHashTableOperate(table, child, JS_DHASH_ADD);
-        if (!entry)
-            return false;
-        childp = &entry->child;
-        sprop = *childp;
-        if (!sprop) {
-            *childp = child;
-        } else {
-            /*
-             * A "Duplicate child" case.
-             *
-             * We can't do away with child, as at least one live scope entry
-             * still points at it.  What's more, that scope's lastProp chains
-             * through an ancestor line to reach child, and js_Enumerate and
-             * others count on this linkage.  We must leave child out of the
-             * hash table, and not require it to be there when we eventually
-             * GC it (see RemovePropertyTreeChild, below).
-             *
-             * It is necessary to leave the duplicate child out of the hash
-             * table to preserve entry uniqueness.  It is safe to leave the
-             * child out of the hash table (unlike the duplicate child cases
-             * below), because the child's parent link will be null, which
-             * can't dangle.
-             */
-            JS_ASSERT(sprop != child && sprop->matches(child));
-            JS_RUNTIME_METER(rt, duplicatePropTreeNodes);
-        }
-    } else {
-        JS_ASSERT(!JSVAL_IS_NULL(parent->id));
-        childp = &parent->kids;
-        kids = *childp;
-        if (kids) {
-            if (KIDS_IS_CHUNKY(kids)) {
-                chunk = KIDS_TO_CHUNK(kids);
-
-                table = chunk->table;
-                if (table) {
-                    entry = (JSPropertyTreeEntry *)
-                            JS_DHashTableOperate(table, child, JS_DHASH_ADD);
-                    if (!entry)
-                        return false;
-                    if (!entry->child) {
-                        entry->child = child;
-                        while (chunk->next)
-                            chunk = chunk->next;
-                        for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
-                            childp = &chunk->kids[i];
-                            sprop = *childp;
-                            if (!sprop)
-                                goto insert;
-                        }
-                        chunkp = &chunk->next;
-                        goto new_chunk;
-                    }
-                }
-
-                do {
-                    for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
-                        childp = &chunk->kids[i];
-                        sprop = *childp;
-                        if (!sprop)
-                            goto insert;
-
-                        JS_ASSERT(sprop != child);
-                        if (sprop->matches(child)) {
-                            /*
-                             * Duplicate child, see comment above.  In this
-                             * case, we must let the duplicate be inserted at
-                             * this level in the tree, so we keep iterating,
-                             * looking for an empty slot in which to insert.
-                             */
-                            JS_ASSERT(sprop != child);
-                            JS_RUNTIME_METER(rt, duplicatePropTreeNodes);
-                        }
-                    }
-                    chunkp = &chunk->next;
-                } while ((chunk = *chunkp) != NULL);
-
-            new_chunk:
-                if (sweptChunk) {
-                    chunk = sweptChunk;
-                } else {
-                    chunk = NewPropTreeKidsChunk(rt);
-                    if (!chunk)
-                        return false;
-                }
-                *chunkp = chunk;
-                childp = &chunk->kids[0];
-            } else {
-                sprop = kids;
-                JS_ASSERT(sprop != child);
-                if (sprop->matches(child)) {
-                    /*
-                     * Duplicate child, see comment above.  Once again, we
-                     * must let duplicates created by deletion pile up in a
-                     * kids-chunk-list, in order to find them when sweeping
-                     * and thereby avoid dangling parent pointers.
-                     */
-                    JS_RUNTIME_METER(rt, duplicatePropTreeNodes);
-                }
-                if (sweptChunk) {
-                    chunk = sweptChunk;
-                } else {
-                    chunk = NewPropTreeKidsChunk(rt);
-                    if (!chunk)
-                        return false;
-                }
-                parent->kids = CHUNK_TO_KIDS(chunk);
-                chunk->kids[0] = sprop;
-                childp = &chunk->kids[1];
-            }
-        }
-    insert:
-        *childp = child;
-    }
-
-    child->parent = parent;
-    return true;
-}
-
-/* NB: Called with rt->gcLock held. */
-static PropTreeKidsChunk *
-RemovePropertyTreeChild(JSRuntime *rt, JSScopeProperty *child)
-{
-    PropTreeKidsChunk *freeChunk;
-    JSScopeProperty *parent, *kids, *kid;
-    JSDHashTable *table;
-    PropTreeKidsChunk *list, *chunk, **chunkp, *lastChunk;
-    uintN i, j;
-    JSPropertyTreeEntry *entry;
-
-    freeChunk = NULL;
-    parent = child->parent;
-    if (!parent) {
-        /*
-         * Don't remove child if it is not in rt->propertyTreeHash, but only
-         * matches a root child in the table that has compatible members. See
-         * the "Duplicate child" comments in InsertPropertyTreeChild, above.
-         */
-        table = &rt->propertyTreeHash;
-    } else {
-        JS_ASSERT(!JSVAL_IS_NULL(parent->id));
-        kids = parent->kids;
-        if (KIDS_IS_CHUNKY(kids)) {
-            list = chunk = KIDS_TO_CHUNK(kids);
-            chunkp = &list;
-            table = chunk->table;
-
-            do {
-                for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
-                    if (chunk->kids[i] == child) {
-                        lastChunk = chunk;
-                        if (!lastChunk->next) {
-                            j = i + 1;
-                        } else {
-                            j = 0;
-                            do {
-                                chunkp = &lastChunk->next;
-                                lastChunk = *chunkp;
-                            } while (lastChunk->next);
-                        }
-                        for (; j < MAX_KIDS_PER_CHUNK; j++) {
-                            if (!lastChunk->kids[j])
-                                break;
-                        }
-                        --j;
-                        if (chunk != lastChunk || j > i)
-                            chunk->kids[i] = lastChunk->kids[j];
-                        lastChunk->kids[j] = NULL;
-                        if (j == 0) {
-                            *chunkp = NULL;
-                            if (!list)
-                                parent->kids = NULL;
-                            freeChunk = lastChunk;
-                        }
-                        goto out;
-                    }
-                }
-
-                chunkp = &chunk->next;
-            } while ((chunk = *chunkp) != NULL);
-        } else {
-            table = NULL;
-            kid = kids;
-            if (kid == child)
-                parent->kids = NULL;
-        }
-    }
-
-out:
-    if (table) {
-        entry = (JSPropertyTreeEntry *)
-                JS_DHashTableOperate(table, child, JS_DHASH_LOOKUP);
-
-        if (entry->child == child)
-            JS_DHashTableRawRemove(table, &entry->hdr);
-    }
-    return freeChunk;
-}
-
-static JSDHashTable *
-HashChunks(PropTreeKidsChunk *chunk, uintN n)
-{
-    JSDHashTable *table;
-    uintN i;
-    JSScopeProperty *sprop;
-    JSPropertyTreeEntry *entry;
-
-    table = JS_NewDHashTable(&PropertyTreeHashOps, NULL,
-                             sizeof(JSPropertyTreeEntry),
-                             JS_DHASH_DEFAULT_CAPACITY(n + 1));
-    if (!table)
-        return NULL;
-    do {
-        for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
-            sprop = chunk->kids[i];
-            if (!sprop)
-                break;
-            entry = (JSPropertyTreeEntry *)
-                    JS_DHashTableOperate(table, sprop, JS_DHASH_ADD);
-            entry->child = sprop;
-        }
-    } while ((chunk = chunk->next) != NULL);
-    return table;
-}
-
-/*
- * Called without cx->runtime->gcLock held. This function acquires that lock
- * only when inserting a new child.  Thus there may be races to find or add a
- * node that result in duplicates.  We expect such races to be rare!
- *
- * We use rt->gcLock, not rt->rtLock, to avoid nesting the former inside the
- * latter in js_GenerateShape below.
- */
-JSScopeProperty *
-js_GetPropertyTreeChild(JSContext *cx, JSScopeProperty *parent,
-                        const JSScopeProperty &child)
-{
-    JSRuntime *rt;
-    JSDHashTable *table;
-    JSPropertyTreeEntry *entry;
-    JSScopeProperty *sprop;
-    PropTreeKidsChunk *chunk;
-    uintN i, n;
-
-    rt = cx->runtime;
-    if (!parent) {
-        JS_LOCK_GC(rt);
-
-        table = &rt->propertyTreeHash;
-        entry = (JSPropertyTreeEntry *)
-                JS_DHashTableOperate(table, &child, JS_DHASH_ADD);
-        if (!entry)
-            goto out_of_memory;
-
-        sprop = entry->child;
-        if (sprop)
-            goto out;
-    } else {
-        JS_ASSERT(!JSVAL_IS_NULL(parent->id));
-
-        /*
-         * Because chunks are appended at the end and never deleted except by
-         * the GC, we can search without taking the runtime's GC lock.  We may
-         * miss a matching sprop added by another thread, and make a duplicate
-         * one, but that is an unlikely, therefore small, cost.  The property
-         * tree has extremely low fan-out below its root in popular embeddings
-         * with real-world workloads.
-         *
-         * Patterns such as defining closures that capture a constructor's
-         * environment as getters or setters on the new object that is passed
-         * in as |this| can significantly increase fan-out below the property
-         * tree root -- see bug 335700 for details.
-         */
-        entry = NULL;
-        sprop = parent->kids;
-        if (sprop) {
-            if (KIDS_IS_CHUNKY(sprop)) {
-                chunk = KIDS_TO_CHUNK(sprop);
-
-                table = chunk->table;
-                if (table) {
-                    JS_LOCK_GC(rt);
-                    entry = (JSPropertyTreeEntry *)
-                            JS_DHashTableOperate(table, &child, JS_DHASH_LOOKUP);
-                    sprop = entry->child;
-                    if (sprop)
-                        goto out;
-                    goto locked_not_found;
-                }
-
-                n = 0;
-                do {
-                    for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
-                        sprop = chunk->kids[i];
-                        if (!sprop) {
-                            n += i;
-                            if (n >= CHUNK_HASH_THRESHOLD) {
-                                chunk = KIDS_TO_CHUNK(parent->kids);
-                                if (!chunk->table) {
-                                    table = HashChunks(chunk, n);
-                                    JS_LOCK_GC(rt);
-                                    if (!table)
-                                        goto out_of_memory;
-                                    if (chunk->table)
-                                        JS_DHashTableDestroy(table);
-                                    else
-                                        chunk->table = table;
-                                    goto locked_not_found;
-                                }
-                            }
-                            goto not_found;
-                        }
-
-                        if (sprop->matches(&child))
-                            return sprop;
-                    }
-                    n += MAX_KIDS_PER_CHUNK;
-                } while ((chunk = chunk->next) != NULL);
-            } else {
-                if (sprop->matches(&child))
-                    return sprop;
-            }
-        }
-
-    not_found:
-        JS_LOCK_GC(rt);
-    }
-
-locked_not_found:
-    sprop = NewScopeProperty(rt);
-    if (!sprop)
-        goto out_of_memory;
-
-    new(sprop) JSScopeProperty(child.id, child.rawGetter, child.rawSetter, child.slot,
-                               child.attrs, child.flags, child.shortid);
-    sprop->parent = sprop->kids = NULL;
-    sprop->shape = js_GenerateShape(cx, true);
-
-    if (!parent) {
-        entry->child = sprop;
-    } else {
-        if (!InsertPropertyTreeChild(rt, parent, sprop, NULL))
-            goto out_of_memory;
-    }
-
-  out:
-    JS_UNLOCK_GC(rt);
-    return sprop;
-
-  out_of_memory:
-    JS_UNLOCK_GC(rt);
-    JS_ReportOutOfMemory(cx);
-    return NULL;
-}
-
 /*
  * Get or create a property-tree or dictionary child property of parent, which
  * must be lastProp if inDictionaryMode(), else parent must be one of lastProp
  * or lastProp->parent.
  */
 JSScopeProperty *
 JSScope::getChildProperty(JSContext *cx, JSScopeProperty *parent,
                           JSScopeProperty &child)
@@ -983,17 +491,17 @@ JSScope::getChildProperty(JSContext *cx,
         JS_ASSERT(parent == lastProp);
         if (newDictionaryProperty(cx, child, &lastProp)) {
             updateShape(cx);
             return lastProp;
         }
         return NULL;
     }
 
-    JSScopeProperty *sprop = js_GetPropertyTreeChild(cx, parent, child);
+    JSScopeProperty *sprop = JS_PROPERTY_TREE(cx).getChild(cx, parent, shape, child);
     if (sprop) {
         JS_ASSERT(sprop->parent == parent);
         if (parent == lastProp) {
             extend(cx, sprop);
         } else {
             JS_ASSERT(parent == lastProp->parent);
             setLastProperty(sprop);
             updateShape(cx);
@@ -1087,23 +595,19 @@ JSScope::generateOwnShape(JSContext *cx)
     shape = js_GenerateShape(cx, false);
     setOwnShape();
 }
 
 JSScopeProperty *
 JSScope::newDictionaryProperty(JSContext *cx, const JSScopeProperty &child,
                                JSScopeProperty **childp)
 {
-    JS_LOCK_GC(cx->runtime);
-    JSScopeProperty *dprop = NewScopeProperty(cx->runtime);
-    JS_UNLOCK_GC(cx->runtime);
-    if (!dprop) {
-        JS_ReportOutOfMemory(cx);
+    JSScopeProperty *dprop = JS_PROPERTY_TREE(cx).newScopeProperty(cx);
+    if (!dprop)
         return NULL;
-    }
 
     new (dprop) JSScopeProperty(child.id, child.rawGetter, child.rawSetter, child.slot,
                                 child.attrs, child.flags | JSScopeProperty::IN_DICTIONARY,
                                 child.shortid);
     dprop->shape = js_GenerateShape(cx, false);
 
     dprop->childp = NULL;
     insertDictionaryProperty(dprop, childp);
@@ -1608,22 +1112,16 @@ JSScope::clear(JSContext *cx)
         newShape = js_GenerateShape(cx, false);
     }
     initMinimal(cx, newShape);
 
     JS_ATOMIC_INCREMENT(&cx->runtime->propertyRemovals);
 }
 
 void
-JSScope::brandingShapeChange(JSContext *cx, uint32 slot, jsval v)
-{
-    generateOwnShape(cx);
-}
-
-void
 JSScope::deletingShapeChange(JSContext *cx, JSScopeProperty *sprop)
 {
     JS_ASSERT(!JSVAL_IS_NULL(sprop->id));
     generateOwnShape(cx);
 }
 
 bool
 JSScope::methodShapeChange(JSContext *cx, JSScopeProperty *sprop, jsval toval)
@@ -1673,22 +1171,16 @@ JSScope::methodShapeChange(JSContext *cx
 
 void
 JSScope::protoShapeChange(JSContext *cx)
 {
     generateOwnShape(cx);
 }
 
 void
-JSScope::sealingShapeChange(JSContext *cx)
-{
-    generateOwnShape(cx);
-}
-
-void
 JSScope::shadowingShapeChange(JSContext *cx, JSScopeProperty *sprop)
 {
     JS_ASSERT(!JSVAL_IS_NULL(sprop->id));
     generateOwnShape(cx);
 }
 
 void
 js_TraceId(JSTracer *trc, jsid id)
@@ -1765,433 +1257,8 @@ JSScopeProperty::trace(JSTracer *trc)
     }
 #endif /* JS_HAS_GETTER_SETTER */
 
     if (isMethod()) {
         JS_SET_TRACING_DETAILS(trc, PrintPropertyMethod, this, 0);
         js_CallGCMarker(trc, methodObject(), JSTRACE_OBJECT);
     }
 }
-
-#ifdef DEBUG
-
-static void
-MeterKidCount(JSBasicStats *bs, uintN nkids)
-{
-    JS_BASIC_STATS_ACCUM(bs, nkids);
-    bs->hist[JS_MIN(nkids, 10)]++;
-}
-
-static void
-MeterPropertyTree(JSBasicStats *bs, JSScopeProperty *node)
-{
-    uintN i, nkids;
-    JSScopeProperty *kids, *kid;
-    PropTreeKidsChunk *chunk;
-
-    nkids = 0;
-    kids = node->kids;
-    if (kids) {
-        if (KIDS_IS_CHUNKY(kids)) {
-            for (chunk = KIDS_TO_CHUNK(kids); chunk; chunk = chunk->next) {
-                for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
-                    kid = chunk->kids[i];
-                    if (!kid)
-                        break;
-                    MeterPropertyTree(bs, kid);
-                    nkids++;
-                }
-            }
-        } else {
-            MeterPropertyTree(bs, kids);
-            nkids = 1;
-        }
-    }
-
-    MeterKidCount(bs, nkids);
-}
-
-static JSDHashOperator
-js_MeterPropertyTree(JSDHashTable *table, JSDHashEntryHdr *hdr, uint32 number,
-                     void *arg)
-{
-    JSPropertyTreeEntry *entry = (JSPropertyTreeEntry *)hdr;
-    JSBasicStats *bs = (JSBasicStats *)arg;
-
-    MeterPropertyTree(bs, entry->child);
-    return JS_DHASH_NEXT;
-}
-
-void
-JSScopeProperty::dump(JSContext *cx, FILE *fp)
-{
-    JS_ASSERT(!JSVAL_IS_NULL(id));
-
-    jsval idval = ID_TO_VALUE(id);
-    if (JSVAL_IS_INT(idval)) {
-        fprintf(fp, "[%ld]", (long) JSVAL_TO_INT(idval));
-    } else {
-        JSString *str;
-        if (JSVAL_IS_STRING(idval)) {
-            str = JSVAL_TO_STRING(idval);
-        } else {
-            JS_ASSERT(JSVAL_IS_OBJECT(idval));
-            str = js_ValueToString(cx, idval);
-            fputs("object ", fp);
-        }
-        if (!str)
-            fputs("<error>", fp);
-        else
-            js_FileEscapedString(fp, str, '"');
-    }
-
-    fprintf(fp, " g/s %p/%p slot %u attrs %x ",
-            JS_FUNC_TO_DATA_PTR(void *, rawGetter),
-            JS_FUNC_TO_DATA_PTR(void *, rawSetter),
-            slot, attrs);
-    if (attrs) {
-        int first = 1;
-        fputs("(", fp);
-#define DUMP_ATTR(name, display) if (attrs & JSPROP_##name) fputs(" " #display + first, fp), first = 0
-        DUMP_ATTR(ENUMERATE, enumerate);
-        DUMP_ATTR(READONLY, readonly);
-        DUMP_ATTR(PERMANENT, permanent);
-        DUMP_ATTR(GETTER, getter);
-        DUMP_ATTR(SETTER, setter);
-        DUMP_ATTR(SHARED, shared);
-#undef  DUMP_ATTR
-        fputs(") ", fp);
-    }
-
-    fprintf(fp, "flags %x ", flags);
-    if (flags) {
-        int first = 1;
-        fputs("(", fp);
-#define DUMP_FLAG(name, display) if (flags & name) fputs(" " #display + first, fp), first = 0
-        DUMP_FLAG(ALIAS, alias);
-        DUMP_FLAG(HAS_SHORTID, has_shortid);
-        DUMP_FLAG(METHOD, method);
-        DUMP_FLAG(MARK, mark);
-        DUMP_FLAG(SHAPE_REGEN, shape_regen);
-        DUMP_FLAG(IN_DICTIONARY, in_dictionary);
-#undef  DUMP_FLAG
-        fputs(") ", fp);
-    }
-
-    fprintf(fp, "shortid %d\n", shortid);
-}
-
-void
-JSScopeProperty::dumpSubtree(JSContext *cx, int level, FILE *fp)
-{
-    fprintf(fp, "%*sid ", level, "");
-    dump(cx, fp);
-
-    if (kids) {
-        ++level;
-        if (KIDS_IS_CHUNKY(kids)) {
-            PropTreeKidsChunk *chunk = KIDS_TO_CHUNK(kids);
-            do {
-                for (uintN i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
-                    JSScopeProperty *kid = chunk->kids[i];
-                    if (!kid)
-                        break;
-                    JS_ASSERT(kid->parent == this);
-                    kid->dumpSubtree(cx, level, fp);
-                }
-            } while ((chunk = chunk->next) != NULL);
-        } else {
-            JSScopeProperty *kid = kids;
-            JS_ASSERT(kid->parent == this);
-            kid->dumpSubtree(cx, level, fp);
-        }
-    }
-}
-
-#endif /* DEBUG */
-
-void
-js_SweepScopeProperties(JSContext *cx)
-{
-    JSRuntime *rt = cx->runtime;
-    JSArena **ap, *a;
-    JSScopeProperty *limit, *sprop, *parent, *kids, *kid;
-    uintN liveCount;
-    PropTreeKidsChunk *chunk, *nextChunk, *freeChunk;
-    uintN i;
-
-#ifdef DEBUG
-    JSBasicStats bs;
-    uint32 livePropCapacity = 0, totalLiveCount = 0;
-    static FILE *logfp;
-    if (!logfp) {
-        if (const char *filename = getenv("JS_PROPTREE_STATFILE"))
-            logfp = fopen(filename, "w");
-    }
-
-    if (logfp) {
-        JS_BASIC_STATS_INIT(&bs);
-        MeterKidCount(&bs, rt->propertyTreeHash.entryCount);
-        JS_DHashTableEnumerate(&rt->propertyTreeHash, js_MeterPropertyTree, &bs);
-
-        double props, nodes, mean, sigma;
-
-        props = rt->liveScopePropsPreSweep;
-        nodes = rt->livePropTreeNodes;
-        JS_ASSERT(nodes == bs.sum);
-        mean = JS_MeanAndStdDevBS(&bs, &sigma);
-
-        fprintf(logfp,
-                "props %g nodes %g beta %g meankids %g sigma %g max %u\n",
-                props, nodes, nodes / props, mean, sigma, bs.max);
-
-        JS_DumpHistogram(&bs, logfp);
-    }
-#endif
-
-    ap = &rt->propertyArenaPool.first.next;
-    while ((a = *ap) != NULL) {
-        limit = (JSScopeProperty *) a->avail;
-        liveCount = 0;
-        for (sprop = (JSScopeProperty *) a->base; sprop < limit; sprop++) {
-            /* If the id is null, sprop is already on the freelist. */
-            if (sprop->id == JSVAL_NULL)
-                continue;
-
-            /*
-             * If the mark bit is set, sprop is alive, so clear the mark bit
-             * and continue the while loop.
-             *
-             * Regenerate sprop->shape if it hasn't already been refreshed
-             * during the mark phase, when live scopes' lastProp members are
-             * followed to update both scope->shape and lastProp->shape.
-             */
-            if (sprop->marked()) {
-                sprop->clearMark();
-                if (rt->gcRegenShapes) {
-                    if (sprop->hasRegenFlag())
-                        sprop->clearRegenFlag();
-                    else
-                        sprop->shape = js_RegenerateShapeForGC(cx);
-                }
-                liveCount++;
-                continue;
-            }
-
-            if (!sprop->inDictionary()) {
-                /* Ok, sprop is garbage to collect: unlink it from its parent. */
-                freeChunk = RemovePropertyTreeChild(rt, sprop);
-
-                /*
-                 * Take care to reparent all sprop's kids to their grandparent.
-                 * InsertPropertyTreeChild can potentially fail for two reasons:
-                 *
-                 * 1. If parent is null, insertion into the root property hash
-                 *    table may fail. We are forced to leave the kid out of the
-                 *    table (as can already happen with duplicates) but ensure
-                 *    that the kid's parent pointer is set to null.
-                 *
-                 * 2. If parent is non-null, allocation of a new KidsChunk can
-                 *    fail. To prevent this from happening, we allow sprops's own
-                 *    chunks to be reused by the grandparent, which removes the
-                 *    need for InsertPropertyTreeChild to malloc a new KidsChunk.
-                 *
-                 *    If sprop does not have chunky kids, then we rely on the
-                 *    RemovePropertyTreeChild call above (which removed sprop from
-                 *    its parent) either leaving one free entry, or else returning
-                 *    the now-unused chunk to us so we can reuse it.
-                 *
-                 * We also require the grandparent to have either no kids or else
-                 * chunky kids. A single non-chunky kid would force a new chunk to
-                 * be malloced in some cases (if sprop had a single non-chunky
-                 * kid, or a multiple of MAX_KIDS_PER_CHUNK kids). Note that
-                 * RemovePropertyTreeChild never converts a single-entry chunky
-                 * kid back to a non-chunky kid, so we are assured of correct
-                 * behaviour.
-                 */
-                kids = sprop->kids;
-                if (kids) {
-                    sprop->kids = NULL;
-                    parent = sprop->parent;
-
-                    /* The grandparent must have either no kids or chunky kids. */
-                    JS_ASSERT(!parent || !parent->kids ||
-                              KIDS_IS_CHUNKY(parent->kids));
-                    if (KIDS_IS_CHUNKY(kids)) {
-                        chunk = KIDS_TO_CHUNK(kids);
-                        do {
-                            nextChunk = chunk->next;
-                            chunk->next = NULL;
-                            for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
-                                kid = chunk->kids[i];
-                                if (!kid)
-                                    break;
-                                JS_ASSERT(kid->parent == sprop);
-
-                                /*
-                                 * Clear a space in the kids array for possible
-                                 * re-use by InsertPropertyTreeChild.
-                                 */
-                                chunk->kids[i] = NULL;
-                                if (!InsertPropertyTreeChild(rt, parent, kid, chunk)) {
-                                    /*
-                                     * This can happen only if we failed to add an
-                                     * entry to the root property hash table.
-                                     */
-                                    JS_ASSERT(!parent);
-                                    kid->parent = NULL;
-                                }
-                            }
-                            if (!chunk->kids[0]) {
-                                /* The chunk wasn't reused, so we must free it. */
-                                DestroyPropTreeKidsChunk(rt, chunk);
-                            }
-                        } while ((chunk = nextChunk) != NULL);
-                    } else {
-                        kid = kids;
-                        if (!InsertPropertyTreeChild(rt, parent, kid, freeChunk)) {
-                            /*
-                             * This can happen only if we failed to add an entry
-                             * to the root property hash table.
-                             */
-                            JS_ASSERT(!parent);
-                            kid->parent = NULL;
-                        }
-                    }
-                }
-
-                if (freeChunk && !freeChunk->kids[0]) {
-                    /* The chunk wasn't reused, so we must free it. */
-                    DestroyPropTreeKidsChunk(rt, freeChunk);
-                }
-            }
-
-            /* Clear id so we know (above) that sprop is on the freelist. */
-            sprop->id = JSVAL_NULL;
-            FREENODE_INSERT(rt->propertyFreeList, sprop);
-            JS_RUNTIME_UNMETER(rt, livePropTreeNodes);
-        }
-
-        /* If a contains no live properties, return it to the malloc heap. */
-        if (liveCount == 0) {
-            for (sprop = (JSScopeProperty *) a->base; sprop < limit; sprop++)
-                FREENODE_REMOVE(sprop);
-            JS_ARENA_DESTROY(&rt->propertyArenaPool, a, ap);
-        } else {
-#ifdef DEBUG
-            livePropCapacity += limit - (JSScopeProperty *) a->base;
-            totalLiveCount += liveCount;
-#endif
-            ap = &a->next;
-        }
-    }
-
-#ifdef DEBUG
-    if (logfp) {
-        fprintf(logfp,
-                "\nProperty tree stats for gcNumber %lu\n",
-                (unsigned long) rt->gcNumber);
-
-        fprintf(logfp, "arenautil %g%%\n",
-                (totalLiveCount && livePropCapacity)
-                ? (totalLiveCount * 100.0) / livePropCapacity
-                : 0.0);
-
-#define RATE(f1, f2) (((double)js_scope_stats.f1 / js_scope_stats.f2) * 100.0)
-
-        fprintf(logfp,
-                "Scope search stats:\n"
-                "  searches:       %6u\n"
-                "  hits:           %6u %5.2f%% of searches\n"
-                "  misses:         %6u %5.2f%%\n"
-                "  hashes:         %6u %5.2f%%\n"
-                "  steps:          %6u %5.2f%% %5.2f%% of hashes\n"
-                "  stepHits:       %6u %5.2f%% %5.2f%%\n"
-                "  stepMisses:     %6u %5.2f%% %5.2f%%\n"
-                "  tableAllocFails %6u\n"
-                "  toDictFails     %6u\n"
-                "  wrapWatchFails  %6u\n"
-                "  adds:           %6u\n"
-                "  addFails:       %6u\n"
-                "  puts:           %6u\n"
-                "  redundantPuts:  %6u\n"
-                "  putFails:       %6u\n"
-                "  changes:        %6u\n"
-                "  changeFails:    %6u\n"
-                "  compresses:     %6u\n"
-                "  grows:          %6u\n"
-                "  removes:        %6u\n"
-                "  removeFrees:    %6u\n"
-                "  uselessRemoves: %6u\n"
-                "  shrinks:        %6u\n",
-                js_scope_stats.searches,
-                js_scope_stats.hits, RATE(hits, searches),
-                js_scope_stats.misses, RATE(misses, searches),
-                js_scope_stats.hashes, RATE(hashes, searches),
-                js_scope_stats.steps, RATE(steps, searches), RATE(steps, hashes),
-                js_scope_stats.stepHits,
-                RATE(stepHits, searches), RATE(stepHits, hashes),
-                js_scope_stats.stepMisses,
-                RATE(stepMisses, searches), RATE(stepMisses, hashes),
-                js_scope_stats.tableAllocFails,
-                js_scope_stats.toDictFails,
-                js_scope_stats.wrapWatchFails,
-                js_scope_stats.adds,
-                js_scope_stats.addFails,
-                js_scope_stats.puts,
-                js_scope_stats.redundantPuts,
-                js_scope_stats.putFails,
-                js_scope_stats.changes,
-                js_scope_stats.changeFails,
-                js_scope_stats.compresses,
-                js_scope_stats.grows,
-                js_scope_stats.removes,
-                js_scope_stats.removeFrees,
-                js_scope_stats.uselessRemoves,
-                js_scope_stats.shrinks);
-
-#undef RATE
-
-        fflush(logfp);
-    }
-
-    if (const char *filename = getenv("JS_PROPTREE_DUMPFILE")) {
-        char pathname[1024];
-        JS_snprintf(pathname, sizeof pathname, "%s.%lu", filename, (unsigned long)rt->gcNumber);
-        FILE *dumpfp = fopen(pathname, "w");
-        if (dumpfp) {
-            JSPropertyTreeEntry *pte, *end;
-
-            pte = (JSPropertyTreeEntry *) rt->propertyTreeHash.entryStore;
-            end = pte + JS_DHASH_TABLE_SIZE(&rt->propertyTreeHash);
-            while (pte < end) {
-                if (pte->child)
-                    pte->child->dumpSubtree(cx, 0, dumpfp);
-                pte++;
-            }
-            fclose(dumpfp);
-        }
-    }
-#endif /* DEBUG */
-}
-
-bool
-js_InitPropertyTree(JSRuntime *rt)
-{
-    if (!JS_DHashTableInit(&rt->propertyTreeHash, &PropertyTreeHashOps, NULL,
-                           sizeof(JSPropertyTreeEntry), JS_DHASH_MIN_SIZE)) {
-        rt->propertyTreeHash.ops = NULL;
-        return false;
-    }
-    JS_InitArenaPool(&rt->propertyArenaPool, "properties",
-                     256 * sizeof(JSScopeProperty), sizeof(void *), NULL);
-    return true;
-}
-
-void
-js_FinishPropertyTree(JSRuntime *rt)
-{
-    if (rt->propertyTreeHash.ops) {
-        JS_DHashTableFinish(&rt->propertyTreeHash);
-        rt->propertyTreeHash.ops = NULL;
-    }
-    JS_FinishArenaPool(&rt->propertyArenaPool);
-}
--- a/js/src/jsscope.h
+++ b/js/src/jsscope.h
@@ -199,16 +199,20 @@ JS_BEGIN_EXTERN_C
  *
  * One final twist (can you stand it?): the mean number of entries per scope
  * in Mozilla is < 5, with a large standard deviation (~8).  Instead of always
  * allocating scope->table, we leave it null while initializing all the other
  * scope members as if it were non-null and minimal-length.  Until a property
  * is added that crosses the threshold of 6 or more entries for hashing, we use
  * linear search from scope->lastProp to find a given id, and save on the space
  * overhead of a hash table.
+ *
+ * See jspropertytree.{h,cpp} for the actual PropertyTree implementation. This
+ * file contains object property map (historical misnomer: "scope" AKA JSScope)
+ * and property tree node ("sprop", JSScopeProperty) declarations.
  */
 
 struct JSEmptyScope;
 
 #define SPROP_INVALID_SLOT              0xffffffff
 
 struct JSScope : public JSObjectMap
 {
@@ -356,22 +360,20 @@ struct JSScope : public JSObjectMap
      * flags show this is necessary. The methodShapeChange overload (directly
      * below) parallels this.
      */
     bool methodWriteBarrier(JSContext *cx, JSScopeProperty *sprop, jsval v);
     bool methodWriteBarrier(JSContext *cx, uint32 slot, jsval v);
 
     void trace(JSTracer *trc);
 
-    void brandingShapeChange(JSContext *cx, uint32 slot, jsval v);
     void deletingShapeChange(JSContext *cx, JSScopeProperty *sprop);
     bool methodShapeChange(JSContext *cx, JSScopeProperty *sprop, jsval toval);
     bool methodShapeChange(JSContext *cx, uint32 slot, jsval toval);
     void protoShapeChange(JSContext *cx);
-    void sealingShapeChange(JSContext *cx);
     void shadowingShapeChange(JSContext *cx, JSScopeProperty *sprop);
 
 /* By definition, hashShift = JS_DHASH_BITS - log2(capacity). */
 #define SCOPE_CAPACITY(scope)   JS_BIT(JS_DHASH_BITS-(scope)->hashShift)
 
     enum {
         DICTIONARY_MODE         = 0x0001,
         SEALED                  = 0x0002,
@@ -395,28 +397,39 @@ struct JSScope : public JSObjectMap
     void clearDictionaryMode()  { flags &= ~DICTIONARY_MODE; }
 
     /*
      * Don't define clearSealed, as it can't be done safely because JS_LOCK_OBJ
      * will avoid taking the lock if the object owns its scope and the scope is
      * sealed.
      */
     bool sealed()               { return flags & SEALED; }
-    void setSealed()            {
+
+    void seal(JSContext *cx) {
         JS_ASSERT(!isSharedEmpty());
+        JS_ASSERT(!sealed());
+        generateOwnShape(cx);
         flags |= SEALED;
     }
 
     /*
      * A branded scope's object contains plain old methods (function-valued
      * properties without magic getters and setters), and its scope->shape
      * evolves whenever a function value changes.
      */
     bool branded()              { JS_ASSERT(!generic()); return flags & BRANDED; }
-    void setBranded()           { flags |= BRANDED; }
+
+    bool brand(JSContext *cx, uint32 slot, jsval v) {
+        JS_ASSERT(!branded());
+        generateOwnShape(cx);
+        if (js_IsPropertyCacheDisabled(cx))  // check for rt->shapeGen overflow
+            return false;
+        flags |= BRANDED;
+        return true;
+    }
 
     bool generic()              { return flags & GENERIC; }
     void setGeneric()           { flags |= GENERIC; }
 
     bool hadIndexedProperties() { return flags & INDEXED_PROPERTIES; }
     void setIndexedProperties() { flags |= INDEXED_PROPERTIES; }
 
     bool hasOwnShape()          { return flags & OWN_SHAPE; }
@@ -549,60 +562,69 @@ js_CastAsObject(JSPropertyOp op)
 }
 
 inline jsval
 js_CastAsObjectJSVal(JSPropertyOp op)
 {
     return OBJECT_TO_JSVAL(JS_FUNC_TO_DATA_PTR(JSObject *, op));
 }
 
+namespace js {
+class PropertyTree;
+}
+
 struct JSScopeProperty {
     friend struct JSScope;
-    friend void js_SweepScopeProperties(JSContext *cx);
-    friend JSScopeProperty * js_GetPropertyTreeChild(JSContext *cx, JSScopeProperty *parent,
-                                                     const JSScopeProperty &child);
+    friend class js::PropertyTree;
+    friend JSDHashOperator js::RemoveNodeIfDead(JSDHashTable *table, JSDHashEntryHdr *hdr,
+                                                uint32 number, void *arg);
+    friend void js::SweepScopeProperties(JSContext *cx);
 
     jsid            id;                 /* int-tagged jsval/untagged JSAtom* */
-private:
+  private:
     JSPropertyOp    rawGetter;          /* getter and setter hooks or objects */
     JSPropertyOp    rawSetter;          /* getter is JSObject* and setter is 0
                                            if sprop->isMethod() */
-public:
+  public:
     uint32          slot;               /* abstract index in object slots */
-private:
+  private:
     uint8           attrs;              /* attributes, see jsapi.h JSPROP_* */
     uint8           flags;              /* flags, see below for defines */
-public:
+  public:
     int16           shortid;            /* tinyid, or local arg/var index */
     JSScopeProperty *parent;            /* parent node, reverse for..in order */
     union {
         JSScopeProperty *kids;          /* null, single child, or a tagged ptr
                                            to many-kids data structure */
         JSScopeProperty **childp;       /* dictionary list starting at lastProp
                                            has a double-indirect back pointer,
                                            either to sprop->parent if not last,
                                            else to scope->lastProp */
     };
     uint32          shape;              /* property cache shape identifier */
 
-private:
-    /* Implementation-private bits stored in sprop->flags. */
+  private:
+    /*
+     * Implementation-private bits stored in sprop->flags. See public: enum {}
+     * flags further below, which were allocated FCFS over time, so interleave
+     * with these bits.
+     */
     enum {
         /* GC mark flag. */
-        MARK =          0x01,
+        MARK            = 0x01,
 
         /*
          * Set during a shape-regenerating GC if the shape has already been
          * regenerated. Unlike JSScope::SHAPE_REGEN, this does not toggle with
-         * each GC. js_SweepScopeProperties clears it.
+         * each GC. js::SweepScopeProperties clears it.
          */
-        SHAPE_REGEN =   0x08,
+        SHAPE_REGEN     = 0x08,
 
         /* Property stored in per-object dictionary, not shared property tree. */
-        IN_DICTIONARY = 0x20
+        IN_DICTIONARY   = 0x20
     };
 
     JSScopeProperty(jsid id, JSPropertyOp getter, JSPropertyOp setter, uint32 slot,
                     uintN attrs, uintN flags, intN shortid)
         : id(id), rawGetter(getter), rawSetter(setter), slot(slot), attrs(uint8(attrs)),
           flags(uint8(flags)), shortid(int16(shortid))
     {
         JS_ASSERT_IF(getter && (attrs & JSPROP_GETTER),
@@ -616,23 +638,23 @@ private:
     void clearMark() { flags &= ~MARK; }
 
     bool hasRegenFlag() const { return (flags & SHAPE_REGEN) != 0; }
     void setRegenFlag() { flags |= SHAPE_REGEN; }
     void clearRegenFlag() { flags &= ~SHAPE_REGEN; }
 
     bool inDictionary() const { return (flags & IN_DICTIONARY) != 0; }
 
-public:
+  public:
     /* Public bits stored in sprop->flags. */
     enum {
-        ALIAS =         0x02,
-        HAS_SHORTID =   0x04,
-        METHOD =        0x10,
-        PUBLIC_FLAGS = ALIAS | HAS_SHORTID | METHOD
+        ALIAS           = 0x02,
+        HAS_SHORTID     = 0x04,
+        METHOD          = 0x10,
+        PUBLIC_FLAGS    = ALIAS | HAS_SHORTID | METHOD
     };
 
     uintN getFlags() const { return flags & PUBLIC_FLAGS; }
     bool isAlias() const { return (flags & ALIAS) != 0; }
     bool hasShortID() const { return (flags & HAS_SHORTID) != 0; }
     bool isMethod() const { return (flags & METHOD) != 0; }
 
     JSObject *methodObject() const {
@@ -677,16 +699,18 @@ public:
     inline JSDHashNumber hash() const;
     inline bool matches(const JSScopeProperty *p) const;
     inline bool matchesParamsAfterId(JSPropertyOp agetter, JSPropertyOp asetter, uint32 aslot,
                                      uintN aattrs, uintN aflags, intN ashortid) const;
 
     bool get(JSContext* cx, JSObject* obj, JSObject *pobj, jsval* vp);
     bool set(JSContext* cx, JSObject* obj, jsval* vp);
 
+    inline bool isSharedPermanent() const;
+
     void trace(JSTracer *trc);
 
     bool hasSlot() const { return (attrs & JSPROP_SHARED) == 0; }
 
     uint8 attributes() const { return attrs; }
     bool configurable() const { return (attrs & JSPROP_PERMANENT) == 0; }
     bool enumerable() const { return (attrs & JSPROP_ENUMERATE) != 0; }
     bool writable() const {
@@ -891,16 +915,22 @@ JSScope::search(jsid id, bool adding)
     return searchTable(id, adding);
 }
 
 #undef METER
 
 inline bool
 JSScope::canProvideEmptyScope(JSObjectOps *ops, JSClass *clasp)
 {
+    /*
+     * An empty scope cannot provide another empty scope, or wrongful two-level
+     * prototype shape sharing ensues -- see bug 497789.
+     */
+    if (!object)
+        return false;
     return this->ops == ops && (!emptyScope || emptyScope->clasp == clasp);
 }
 
 inline bool
 JSScopeProperty::get(JSContext* cx, JSObject* obj, JSObject *pobj, jsval* vp)
 {
     JS_ASSERT(!JSVAL_IS_NULL(this->id));
     JS_ASSERT(!hasDefaultGetter());
@@ -944,38 +974,28 @@ JSScopeProperty::set(JSContext* cx, JSOb
         return !!js_ReportGetterOnlyAssignment(cx);
 
     /* See the comment in JSScopeProperty::get as to why we can check for With. */
     if (STOBJ_GET_CLASS(obj) == &js_WithClass)
         obj = obj->map->ops->thisObject(cx, obj);
     return setterOp()(cx, obj, SPROP_USERID(this), vp);
 }
 
-/* Macro for common expression to test for shared permanent attributes. */
 inline bool
-SPROP_IS_SHARED_PERMANENT(JSScopeProperty *sprop)
+JSScopeProperty::isSharedPermanent() const
 {
-    return !sprop->hasSlot() && !sprop->configurable();
+    return (~attrs & (JSPROP_SHARED | JSPROP_PERMANENT)) == 0;
 }
 
 extern JSScope *
 js_GetMutableScope(JSContext *cx, JSObject *obj);
 
 extern void
 js_TraceId(JSTracer *trc, jsid id);
 
-extern void
-js_SweepScopeProperties(JSContext *cx);
-
-extern bool
-js_InitPropertyTree(JSRuntime *rt);
-
-extern void
-js_FinishPropertyTree(JSRuntime *rt);
-
 JS_END_EXTERN_C
 
 #ifdef _MSC_VER
 #pragma warning(pop)
 #pragma warning(pop)
 #endif
 
 #endif /* jsscope_h___ */
--- a/js/src/jsscopeinlines.h
+++ b/js/src/jsscopeinlines.h
@@ -158,16 +158,17 @@ JSScope::methodWriteBarrier(JSContext *c
 }
 
 inline void
 JSScope::trace(JSTracer *trc)
 {
     JSContext *cx = trc->context;
     JSScopeProperty *sprop = lastProp;
     uint8 regenFlag = cx->runtime->gcRegenShapesScopeFlag;
+
     if (IS_GC_MARKING_TRACER(trc) && cx->runtime->gcRegenShapes && !hasRegenFlag(regenFlag)) {
         /*
          * Either this scope has its own shape, which must be regenerated, or
          * it must have the same shape as lastProp.
          */
         uint32 newShape;
 
         if (sprop) {
@@ -179,24 +180,30 @@ JSScope::trace(JSTracer *trc)
         }
         if (!sprop || hasOwnShape()) {
             newShape = js_RegenerateShapeForGC(cx);
             JS_ASSERT_IF(sprop, newShape != sprop->shape);
         }
         shape = newShape;
         flags ^= JSScope::SHAPE_REGEN;
 
-        /* Also regenerate the shapes of empty scopes, in case they are not shared. */
-        for (JSScope *empty = emptyScope;
-             empty && !empty->hasRegenFlag(regenFlag);
-             empty = empty->emptyScope) {
-            empty->shape = js_RegenerateShapeForGC(cx);
-            empty->flags ^= JSScope::SHAPE_REGEN;
+        /* Also regenerate the shapes of this scope's empty scope, if there is one. */
+        JSScope *empty = emptyScope;
+        if (empty) {
+            JS_ASSERT(!empty->emptyScope);
+            if (!empty->hasRegenFlag(regenFlag)) {
+                uint32 newEmptyShape = js_RegenerateShapeForGC(cx);
+
+                JS_PROPERTY_TREE(cx).emptyShapeChange(empty->shape, newEmptyShape);
+                empty->shape = newEmptyShape;
+                empty->flags ^= JSScope::SHAPE_REGEN;
+            }
         }
     }
+
     if (sprop) {
         JS_ASSERT(hasProperty(sprop));
 
         /* Trace scope's property tree ancestor line. */
         do {
             sprop->trace(trc);
         } while ((sprop = sprop->parent) != NULL);
     }
--- a/js/src/jstracer.cpp
+++ b/js/src/jstracer.cpp
@@ -5188,55 +5188,60 @@ TraceRecorder::checkTraceEnd(jsbytecode 
             return ars;
         } else {
             return endLoop();
         }
     }
     return ARECORD_CONTINUE;
 }
 
-bool
-TraceRecorder::hasMethod(JSObject* obj, jsid id)
-{
+RecordingStatus
+TraceRecorder::hasMethod(JSObject* obj, jsid id, bool& found)
+{
+    found = false;
+    RecordingStatus status = RECORD_CONTINUE;
     if (!obj)
-        return false;
+        return status;
 
     JSObject* pobj;
     JSProperty* prop;
     int protoIndex = obj->lookupProperty(cx, id, &pobj, &prop);
-    if (protoIndex < 0 || !prop)
-        return false;
-
-    bool found = false;
-    if (OBJ_IS_NATIVE(pobj)) {
+    if (protoIndex < 0)
+        return RECORD_ERROR;
+    if (!prop)
+        return status;
+
+    if (!OBJ_IS_NATIVE(pobj)) {
+        // We can't rely on __iterator__ being present on trace just because
+        // it's there now, if found in a non-native object.
+        status = RECORD_STOP;
+    } else {
         JSScope* scope = OBJ_SCOPE(pobj);
         JSScopeProperty* sprop = (JSScopeProperty*) prop;
 
         if (sprop->hasDefaultGetterOrIsMethod() && SPROP_HAS_VALID_SLOT(sprop, scope)) {
             jsval v = LOCKED_OBJ_GET_SLOT(pobj, sprop->slot);
             if (VALUE_IS_FUNCTION(cx, v)) {
                 found = true;
-                if (!scope->generic() && !scope->branded()) {
-                    scope->brandingShapeChange(cx, sprop->slot, v);
-                    scope->setBranded();
-                }
+                if (!scope->generic() && !scope->branded() && !scope->brand(cx, sprop->slot, v))
+                    status = RECORD_STOP;
             }
         }
     }
 
     pobj->dropProperty(cx, prop);
-    return found;
-}
-
-JS_REQUIRES_STACK bool
-TraceRecorder::hasIteratorMethod(JSObject* obj)
+    return status;
+}
+
+JS_REQUIRES_STACK RecordingStatus
+TraceRecorder::hasIteratorMethod(JSObject* obj, bool& found)
 {
     JS_ASSERT(cx->fp->regs->sp + 2 <= cx->fp->slots + cx->fp->script->nslots);
 
-    return hasMethod(obj, ATOM_TO_JSID(cx->runtime->atomState.iteratorAtom));
+    return hasMethod(obj, ATOM_TO_JSID(cx->runtime->atomState.iteratorAtom), found);
 }
 
 /*
  * Check whether the shape of the global object has changed. The return value
  * indicates whether the recorder is still active.  If 'false', any active
  * recording has been aborted and the JIT may have been reset.
  */
 static JS_REQUIRES_STACK bool
@@ -9162,17 +9167,17 @@ TraceRecorder::test_property_cache(JSObj
                 RETURN_ERROR_A("error in js_LookupPropertyWithFlags");
 
             if (prop) {
                 if (!OBJ_IS_NATIVE(obj2)) {
                     obj2->dropProperty(cx, prop);
                     RETURN_STOP_A("property found on non-native object");
                 }
                 entry = js_FillPropertyCache(cx, aobj, 0, protoIndex, obj2,
-                                             (JSScopeProperty*) prop, false);
+                                             (JSScopeProperty*) prop);
                 JS_ASSERT(entry);
                 if (entry == JS_NO_PROP_CACHE_FILL)
                     entry = NULL;
             }
 
         }
 
         if (!prop) {
@@ -9209,70 +9214,46 @@ TraceRecorder::guardPropertyCacheHit(LIn
                                      JSObject* obj2,
                                      JSPropCacheEntry* entry,
                                      jsuword& pcval)
 {
     VMSideExit* exit = snapshot(BRANCH_EXIT);
 
     uint32 vshape = PCVCAP_SHAPE(entry->vcap);
 
-    // Check for first-level cache hit and guard on kshape if possible.
-    // Otherwise guard on key object exact match.
-    if (PCVCAP_TAG(entry->vcap) <= 1) {
-        // Special case for the global object, which may be aliased to get a property value.
-        // To catch cross-global property accesses we must check against globalObj identity.
-        // But a JOF_NAME mode opcode needs no guard, as we ensure the global object's shape
-        // never changes, and name ops can't reach across a global object ('with' aborts).
-        if (aobj == globalObj) {
-            if (entry->adding())
-                RETURN_STOP("adding a property to the global object");
-
-            JSOp op = js_GetOpcode(cx, cx->fp->script, cx->fp->regs->pc);
-            if (JOF_OPMODE(op) != JOF_NAME) {
-                guard(true,
-                      addName(lir->ins2(LIR_peq, obj_ins, INS_CONSTOBJ(globalObj)), "guard_global"),
-                      exit);
-            }
-        } else {
-            CHECK_STATUS(guardShape(obj_ins, aobj, entry->kshape, "guard_kshape", map_ins, exit));
-        }
-
-        if (entry->adding()) {
-            LIns *vshape_ins = addName(
-                lir->insLoad(LIR_ld,
-                             addName(lir->insLoad(LIR_ldp, cx_ins,
-                                                  offsetof(JSContext, runtime), ACC_READONLY),
-                                     "runtime"),
-                             offsetof(JSRuntime, protoHazardShape)),
-                "protoHazardShape");
+    // Special case for the global object, which may be aliased to get a property value.
+    // To catch cross-global property accesses we must check against globalObj identity.
+    // But a JOF_NAME mode opcode needs no guard, as we ensure the global object's shape
+    // never changes, and name ops can't reach across a global object ('with' aborts).
+    if (aobj == globalObj) {
+        if (entry->adding())
+            RETURN_STOP("adding a property to the global object");
+
+        JSOp op = js_GetOpcode(cx, cx->fp->script, cx->fp->regs->pc);
+        if (JOF_OPMODE(op) != JOF_NAME) {
             guard(true,
-                  addName(lir->ins2i(LIR_eq, vshape_ins, vshape), "guard_protoHazardShape"),
-                  MISMATCH_EXIT);
+                  addName(lir->ins2(LIR_peq, obj_ins, INS_CONSTOBJ(globalObj)), "guard_global"),
+                  exit);
         }
     } else {
-        JSOp op = js_GetOpcode(cx, cx->fp->script, cx->fp->regs->pc);
-
-#ifdef DEBUG
-        JSAtom *pcatom;
-        if (op == JSOP_LENGTH) {
-            pcatom = cx->runtime->atomState.lengthAtom;
-        } else {
-            ptrdiff_t pcoff = (JOF_TYPE(js_CodeSpec[op].format) == JOF_SLOTATOM) ? SLOTNO_LEN : 0;
-            GET_ATOM_FROM_BYTECODE(cx->fp->script, cx->fp->regs->pc, pcoff, pcatom);
-        }
-        JS_ASSERT(entry->kpc == (jsbytecode *) pcatom);
-        JS_ASSERT(entry->kshape == jsuword(aobj));
-#endif
-
-        // See above comment about globalObj and JOF_NAME.
-        if (!obj_ins->isconstp() && (aobj != globalObj || JOF_OPMODE(op) != JOF_NAME)) {
-            guard(true,
-                  addName(lir->ins2(LIR_peq, obj_ins, INS_CONSTOBJ(aobj)), "guard_kobj"),
-                  exit);
-        }
+        CHECK_STATUS(guardShape(obj_ins, aobj, entry->kshape, "guard_kshape", map_ins, exit));
+    }
+
+    if (entry->adding()) {
+        LIns *vshape_ins = addName(
+            lir->insLoad(LIR_ld,
+                         addName(lir->insLoad(LIR_ldp, cx_ins, offsetof(JSContext, runtime),
+                                              ACC_READONLY),
+                                 "runtime"),
+                         offsetof(JSRuntime, protoHazardShape)),
+            "protoHazardShape");
+
+        guard(true,
+              addName(lir->ins2i(LIR_eq, vshape_ins, vshape), "guard_protoHazardShape"),
+              MISMATCH_EXIT);
     }
 
     // For any hit that goes up the scope and/or proto chains, we will need to
     // guard on the shape of the object containing the property.
     if (PCVCAP_TAG(entry->vcap) >= 1) {
         JS_ASSERT(OBJ_SHAPE(obj2) == vshape);
         if (obj2 == globalObj)
             RETURN_STOP("hitting the global object via a prototype chain");
@@ -13447,17 +13428,21 @@ TraceRecorder::record_JSOP_ITER()
 {
     jsval& v = stackval(-1);
     if (JSVAL_IS_PRIMITIVE(v))
         RETURN_STOP_A("for-in on a primitive value");
     RETURN_IF_XML_A(v);
 
     jsuint flags = cx->fp->regs->pc[1];
 
-    if (hasIteratorMethod(JSVAL_TO_OBJECT(v))) {
+    bool found;
+    RecordingStatus status = hasIteratorMethod(JSVAL_TO_OBJECT(v), found);
+    if (status != RECORD_CONTINUE)
+        return InjectStatus(status);
+    if (found) {
         if (flags == JSITER_ENUMERATE)
             return InjectStatus(call_imacro(iter_imacros.for_in));
         if (flags == (JSITER_ENUMERATE | JSITER_FOREACH))
             return InjectStatus(call_imacro(iter_imacros.for_each));
     } else {
         if (flags == JSITER_ENUMERATE)
             return InjectStatus(call_imacro(iter_imacros.for_in_native));
         if (flags == (JSITER_ENUMERATE | JSITER_FOREACH))
--- a/js/src/jstracer.h
+++ b/js/src/jstracer.h
@@ -1348,18 +1348,18 @@ class TraceRecorder
     JS_REQUIRES_STACK RecordingStatus callNative(uintN argc, JSOp mode);
     JS_REQUIRES_STACK RecordingStatus functionCall(uintN argc, JSOp mode);
 
     JS_REQUIRES_STACK void trackCfgMerges(jsbytecode* pc);
     JS_REQUIRES_STACK void emitIf(jsbytecode* pc, bool cond, nanojit::LIns* x);
     JS_REQUIRES_STACK void fuseIf(jsbytecode* pc, bool cond, nanojit::LIns* x);
     JS_REQUIRES_STACK AbortableRecordingStatus checkTraceEnd(jsbytecode* pc);
 
-    bool hasMethod(JSObject* obj, jsid id);
-    JS_REQUIRES_STACK bool hasIteratorMethod(JSObject* obj);
+    RecordingStatus hasMethod(JSObject* obj, jsid id, bool& found);
+    JS_REQUIRES_STACK RecordingStatus hasIteratorMethod(JSObject* obj, bool& found);
 
     JS_REQUIRES_STACK jsatomid getFullIndex(ptrdiff_t pcoff = 0);
 
     JS_REQUIRES_STACK TraceType determineSlotType(jsval* vp);
 
     JS_REQUIRES_STACK AbortableRecordingStatus compile();
     JS_REQUIRES_STACK AbortableRecordingStatus closeLoop();
     JS_REQUIRES_STACK AbortableRecordingStatus closeLoop(VMSideExit* exit);
--- a/js/src/tests/js1_5/Regress/jstests.list
+++ b/js/src/tests/js1_5/Regress/jstests.list
@@ -342,17 +342,17 @@ script regress-478314.js
 script regress-479353.js
 script regress-480147.js
 script regress-480244.js
 script regress-481436.js
 script regress-482421.js
 script regress-482783.js
 script regress-483103.js
 script regress-501124.js
-skip script regress-503860.js # waiting for bug 497789 to be fixed
+script regress-503860.js
 script regress-504078.js
 script regress-506567.js
 script regress-511859.js
 script regress-57043.js
 script regress-58116.js
 script regress-68498-001.js
 script regress-68498-002.js
 script regress-68498-003.js