Fixed breakage of type stability guarantees between linked trees, and fixed using the wrong global typemap in LeaveTree (bug 476653, r=gal).
authorDavid Anderson <danderson@mozilla.com>
Tue, 24 Feb 2009 22:52:09 -0500
changeset 25491 0d0489b3e4b7f60abd6c2d6131c037ebfcdf6c1d
parent 25490 5178de16806170cd77e5c421556d05d5b2b8ea78
child 25492 00d554e3db2949a577674b033247c5f280eb8d4d
push id5575
push userrsayre@mozilla.com
push dateWed, 25 Feb 2009 09:05:38 +0000
treeherdermozilla-central@8eba35e62d92 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersgal
bugs476653
milestone1.9.2a1pre
Fixed breakage of type stability guarantees between linked trees, and fixed using the wrong global typemap in LeaveTree (bug 476653, r=gal).
js/src/jstracer.cpp
js/src/jstracer.h
--- a/js/src/jstracer.cpp
+++ b/js/src/jstracer.cpp
@@ -1173,16 +1173,38 @@ mergeTypeMaps(uint8** partial, unsigned*
     unsigned l = *plength;
     JS_ASSERT(l < clength);
     memcpy(mem, *partial, l * sizeof(uint8));
     memcpy(mem + l, complete + l, (clength - l) * sizeof(uint8));
     *partial = mem;
     *plength = clength;
 }
 
+/* Specializes a tree to any missing globals, including any dependent trees. */
+static void
+specializeTreesToMissingGlobals(JSContext* cx, TreeInfo* root)
+{
+    TreeInfo* ti = root;
+
+    ti->typeMap.captureMissingGlobalTypes(cx, *ti->globalSlots, ti->nStackTypes);
+    JS_ASSERT(ti->globalSlots->length() == ti->typeMap.length() - ti->nStackTypes);
+   
+    for (unsigned i = 0; i < root->dependentTrees.length(); i++) {
+        ti = (TreeInfo*)root->dependentTrees.data()[i]->vmprivate;
+        /* ti can be NULL if we hit the recording tree in emitTreeCall; this is harmless. */
+        if (ti && ti->nGlobalTypes() < ti->globalSlots->length())
+            specializeTreesToMissingGlobals(cx, ti);
+    }
+    for (unsigned i = 0; i < root->linkedTrees.length(); i++) {
+        ti = (TreeInfo*)root->linkedTrees.data()[i]->vmprivate;
+        if (ti && ti->nGlobalTypes() < ti->globalSlots->length())
+            specializeTreesToMissingGlobals(cx, ti);
+    }
+}
+
 static void
 js_TrashTree(JSContext* cx, Fragment* f);
 
 JS_REQUIRES_STACK
 TraceRecorder::TraceRecorder(JSContext* cx, VMSideExit* _anchor, Fragment* _fragment,
         TreeInfo* ti, unsigned stackSlots, unsigned ngslots, uint8* typeMap,
         VMSideExit* innermostNestedGuard, Fragment* outerToBlacklist)
 {
@@ -1227,21 +1249,18 @@ TraceRecorder::TraceRecorder(JSContext* 
     lirbuf->rp = addName(lir->insLoad(LIR_ldp, lirbuf->state, offsetof(InterpState, rp)), "rp");
     cx_ins = addName(lir->insLoad(LIR_ldp, lirbuf->state, offsetof(InterpState, cx)), "cx");
     gp_ins = addName(lir->insLoad(LIR_ldp, lirbuf->state, offsetof(InterpState, global)), "gp");
     eos_ins = addName(lir->insLoad(LIR_ldp, lirbuf->state, offsetof(InterpState, eos)), "eos");
     eor_ins = addName(lir->insLoad(LIR_ldp, lirbuf->state, offsetof(InterpState, eor)), "eor");
     globalObj_ins = addName(lir->insLoad(LIR_ldp, lirbuf->state, offsetof(InterpState, globalObj)), "globalObj");
 
     /* If we came from exit, we might not have enough global types. */
-    if (ti->globalSlots->length() > ti->nGlobalTypes()) {
-        ti->typeMap.captureMissingGlobalTypes(cx,
-                                              *(ti->globalSlots),
-                                              ti->nStackTypes);
-    }
+    if (ti->globalSlots->length() > ti->nGlobalTypes())
+        specializeTreesToMissingGlobals(cx, ti);
 
     /* read into registers all values on the stack and all globals we know so far */
     import(treeInfo, lirbuf->sp, stackSlots, ngslots, callDepth, typeMap);
 
     if (fragment == fragment->root) {
         /*
          * We poll the operation callback request flag. It is updated asynchronously whenever 
          * the callback is to be invoked.
@@ -1643,16 +1662,17 @@ BuildNativeStackFrame(JSContext* cx, uns
 }
 
 /* Box the given native frame into a JS frame. This is infallible. */
 static JS_REQUIRES_STACK int
 FlushNativeGlobalFrame(JSContext* cx, unsigned ngslots, uint16* gslots, uint8* mp, double* np)
 {
     uint8* mp_base = mp;
     FORALL_GLOBAL_SLOTS(cx, ngslots, gslots,
+        debug_only_v(printf("%s%u=", vpname, vpnum);)
         NativeToValue(cx, *vp, *mp, np + gslots[n]);
         ++mp;
     );
     debug_only_v(printf("\n");)
     return mp - mp_base;
 }
 
 /**
@@ -1823,22 +1843,24 @@ TraceRecorder::lazilyImportGlobalSlot(un
 {
     if (slot != uint16(slot)) /* we use a table of 16-bit ints, bail out if that's not enough */
         return false;
     jsval* vp = &STOBJ_GET_SLOT(globalObj, slot);
     if (known(vp))
         return true; /* we already have it */
     unsigned index = treeInfo->globalSlots->length();
     /* Add the slot to the list of interned global slots. */
+    JS_ASSERT(treeInfo->nGlobalTypes() == treeInfo->globalSlots->length());
     treeInfo->globalSlots->add(slot);
     uint8 type = getCoercedType(*vp);
     if ((type == JSVAL_INT) && oracle.isGlobalSlotUndemotable(cx, slot))
         type = JSVAL_DOUBLE;
     treeInfo->typeMap.add(type);
     import(gp_ins, slot*sizeof(double), vp, type, "global", index, NULL);
+    specializeTreesToMissingGlobals(cx, treeInfo);
     return true;
 }
 
 /* Write back a value onto the stack or global frames. */
 LIns*
 TraceRecorder::writeBack(LIns* i, LIns* base, ptrdiff_t offset)
 {
     /* Sink all type casts targeting the stack into the side exit by simply storing the original
@@ -2511,16 +2533,17 @@ js_JoinPeersIfCompatible(Fragmento* frag
         memcmp(getFullTypeMap(exit), stableTree->typeMap.data(), stableTree->typeMap.length())) {
        return false;
     }
 
     exit->target = stableFrag;
     frago->assm()->patch(exit);
 
     stableTree->dependentTrees.addUnique(exit->from->root);
+    ((TreeInfo*)exit->from->root->vmprivate)->linkedTrees.addUnique(stableFrag);
 
     return true;
 }
 
 /* Complete and compile a trace and link it to the existing tree if appropriate. */
 JS_REQUIRES_STACK bool
 TraceRecorder::closeLoop(JSTraceMonitor* tm, bool& demote)
 {
@@ -2592,30 +2615,35 @@ TraceRecorder::closeLoop(JSTraceMonitor*
                 exit->imacpc = terminate_imacpc;
             }
         } else {
             JS_ASSERT(peer->code());
             exit->target = peer;
             debug_only_v(printf("Joining type-unstable trace to target fragment %p.\n", (void*)peer);)
             stable = true;
             ((TreeInfo*)peer->vmprivate)->dependentTrees.addUnique(fragment->root);
+            treeInfo->linkedTrees.addUnique(peer);
         }
 
         compile(tm);
     } else {
         exit->target = fragment->root;
         fragment->lastIns = lir->insGuard(LIR_loop, lir->insImm(1), exitIns);
         compile(tm);
     }
 
     if (fragmento->assm()->error() != nanojit::None)
         return false;
 
     joinEdgesToEntry(fragmento, peer_root);
 
+    debug_only_v(printf("updating specializations on dependent and linked trees\n"))
+    if (fragment->root->vmprivate)
+        specializeTreesToMissingGlobals(cx, (TreeInfo*)fragment->root->vmprivate);
+
     debug_only_v(printf("recording completed at %s:%u@%u via closeLoop\n",
                         cx->fp->script->filename,
                         js_FramePCToLineNumber(cx, cx->fp),
                         FramePCOffset(cx->fp));)
     return true;
 }
 
 JS_REQUIRES_STACK void
@@ -2713,16 +2741,22 @@ TraceRecorder::endLoop(JSTraceMonitor* t
     fragment->lastIns = lir->insGuard(LIR_x, lir->insImm(1), exitIns);
     compile(tm);
 
     if (tm->fragmento->assm()->error() != nanojit::None)
         return;
 
     joinEdgesToEntry(tm->fragmento, getLoop(tm, fragment->root->ip, treeInfo->globalShape));
 
+    /* Note: this must always be done, in case we added new globals on trace and haven't yet 
+       propagated those to linked and dependent trees. */
+    debug_only_v(printf("updating specializations on dependent and linked trees\n"))
+    if (fragment->root->vmprivate)
+        specializeTreesToMissingGlobals(cx, (TreeInfo*)fragment->root->vmprivate);
+
     debug_only_v(printf("recording completed at %s:%u@%u via endLoop\n",
                         cx->fp->script->filename,
                         js_FramePCToLineNumber(cx, cx->fp),
                         FramePCOffset(cx->fp));)
 }
 
 /* Emit code to adjust the stack to match the inner tree's stack expectations. */
 JS_REQUIRES_STACK void
@@ -2780,16 +2814,17 @@ TraceRecorder::emitTreeCall(Fragment* in
         lir->insStorei(lirbuf->sp, lirbuf->state, offsetof(InterpState, sp));
         lir->insStorei(lirbuf->rp, lirbuf->state, offsetof(InterpState, rp));
     }
     /* Guard that we come out of the inner tree along the same side exit we came out when
        we called the inner tree at recording time. */
     guard(true, lir->ins2(LIR_eq, ret, INS_CONSTPTR(exit)), NESTED_EXIT);
     /* Register us as a dependent tree of the inner tree. */
     ((TreeInfo*)inner->vmprivate)->dependentTrees.addUnique(fragment->root);
+    treeInfo->linkedTrees.addUnique(inner);
 }
 
 /* Add a if/if-else control-flow merge point to the list of known merge points. */
 JS_REQUIRES_STACK void
 TraceRecorder::trackCfgMerges(jsbytecode* pc)
 {
     /* If we hit the beginning of an if/if-else, then keep track of the merge point after it. */
     JS_ASSERT((*pc == JSOP_IFEQ) || (*pc == JSOP_IFEQX));
@@ -3386,19 +3421,20 @@ js_AttemptToStabilizeTree(JSContext* cx,
             }
         }
         if (matched) {
             JS_ASSERT(from_ti->globalSlots == ti->globalSlots);
             JS_ASSERT(from_ti->nStackTypes == ti->nStackTypes);
             /* Capture missing globals on both trees and link the fragments together. */
             if (from != f) {
                 ti->dependentTrees.addUnique(from);
-                ti->typeMap.captureMissingGlobalTypes(cx, *ti->globalSlots, ti->nStackTypes);
+                from_ti->linkedTrees.addUnique(f);
             }
-            from_ti->typeMap.captureMissingGlobalTypes(cx, *from_ti->globalSlots, from_ti->nStackTypes);
+            if (ti->nGlobalTypes() < ti->globalSlots->length())
+                specializeTreesToMissingGlobals(cx, ti);
             exit->target = f;
             tm->fragmento->assm()->patch(exit);
             /* Now erase this exit from the unstable exit list. */
             UnstableExit** tail = &from_ti->unstableExits;
             for (UnstableExit* uexit = from_ti->unstableExits; uexit != NULL; uexit = uexit->next) {
                 if (uexit->exit == exit) {
                     *tail = uexit->next;
                     delete uexit;
@@ -3717,17 +3753,17 @@ TraceRecorder::findNestedCompatiblePeer(
         }
 
         unsigned demotes = 0;
         ti = (TreeInfo*)f->vmprivate;
 
         debug_only_v(printf("checking nested types %p: ", (void*)f);)
 
         if (ngslots > ti->nGlobalTypes())
-            ti->typeMap.captureMissingGlobalTypes(cx, *ti->globalSlots, ti->nStackTypes);
+            specializeTreesToMissingGlobals(cx, ti);
 
         uint8* m = ti->typeMap.data();
 
         FORALL_SLOTS(cx, ngslots, gslots, 0,
             debug_only_v(printf("%s%d=", vpname, vpnum);)
             if (!js_IsEntryTypeCompatible(vp, m))
                 goto check_fail;
             if (*m == JSVAL_STRING && *vp == JSVAL_VOID)
@@ -3772,17 +3808,17 @@ static JS_REQUIRES_STACK bool
 js_CheckEntryTypes(JSContext* cx, TreeInfo* ti)
 {
     unsigned int ngslots = ti->globalSlots->length();
     uint16* gslots = ti->globalSlots->data();
 
     JS_ASSERT(ti->nStackTypes == js_NativeStackSlots(cx, 0));
 
     if (ngslots > ti->nGlobalTypes())
-        ti->typeMap.captureMissingGlobalTypes(cx, *ti->globalSlots, ti->nStackTypes);
+        specializeTreesToMissingGlobals(cx, ti);
 
     uint8* m = ti->typeMap.data();
 
     JS_ASSERT(ti->typeMap.length() == js_NativeStackSlots(cx, 0) + ngslots);
     JS_ASSERT(ti->typeMap.length() == ti->nStackTypes + ngslots);
     JS_ASSERT(ti->nGlobalTypes() == ngslots);
     FORALL_SLOTS(cx, ngslots, gslots, 0,
         debug_only_v(printf("%s%d=", vpname, vpnum);)
@@ -4104,26 +4140,38 @@ LeaveTree(InterpState& state, VMSideExit
     /* If this trace is part of a tree, later branches might have added additional globals for
        which we don't have any type information available in the side exit. We merge in this
        information from the entry type-map. See also comment in the constructor of TraceRecorder
        why this is always safe to do. */
     TreeInfo* outermostTree = state.outermostTree;
     uint16* gslots = outermostTree->globalSlots->data();
     unsigned ngslots = outermostTree->globalSlots->length();
     JS_ASSERT(ngslots == outermostTree->nGlobalTypes());
-    unsigned exit_gslots = innermost->numGlobalSlots;
-    JS_ASSERT(exit_gslots <= ngslots);
-    uint8* globalTypeMap = getGlobalTypeMap(innermost);
-    if (exit_gslots < ngslots)
-        mergeTypeMaps(&globalTypeMap, &exit_gslots, outermostTree->globalTypeMap(), ngslots,
-                      (uint8*)alloca(sizeof(uint8) * ngslots));
-    JS_ASSERT(exit_gslots == outermostTree->globalSlots->length());
+    uint8* globalTypeMap;
+
+    /* Are there enough globals? This is the ideal fast path. */
+    if (innermost->numGlobalSlots == ngslots) {
+        globalTypeMap = getGlobalTypeMap(innermost);
+    /* Otherwise, merge the typemap of the innermost entry and exit together.  This should always
+       work because it is invalid for nested trees or linked trees to have incompatible types.
+       Thus, whenever a new global type is lazily added into a tree, all dependent and linked
+       trees are immediately specialized (see bug 476653). */
+    } else {
+        TreeInfo* ti = (TreeInfo*)innermost->from->root->vmprivate;
+        JS_ASSERT(ti->nGlobalTypes() == ngslots);
+        JS_ASSERT(ti->nGlobalTypes() > innermost->numGlobalSlots);
+        globalTypeMap = (uint8*)alloca(ngslots * sizeof(uint8));
+        memcpy(globalTypeMap, getGlobalTypeMap(innermost), innermost->numGlobalSlots);
+        memcpy(globalTypeMap + innermost->numGlobalSlots,
+               ti->globalTypeMap() + innermost->numGlobalSlots,
+               ti->nGlobalTypes() - innermost->numGlobalSlots);
+    }
 
     /* write back interned globals */
-    FlushNativeGlobalFrame(cx, exit_gslots, gslots, globalTypeMap, state.global);
+    FlushNativeGlobalFrame(cx, ngslots, gslots, globalTypeMap, state.global);
     JS_ASSERT(*(uint64*)&state.global[STOBJ_NSLOTS(state.globalObj)] == 0xdeadbeefdeadbeefLL);
 
     /* write back native stack frame */
 #ifdef DEBUG
     int slots =
 #endif
         FlushNativeStackFrame(cx, innermost->calldepth,
                               getStackTypeMap(innermost),
--- a/js/src/jstracer.h
+++ b/js/src/jstracer.h
@@ -303,17 +303,20 @@ public:
     JSScript*               script;
     unsigned                maxNativeStackSlots;
     ptrdiff_t               nativeStackBase;
     unsigned                maxCallDepth;
     TypeMap                 typeMap;
     unsigned                nStackTypes;
     uint32                  globalShape;
     SlotList*               globalSlots;
+    /* Dependent trees must be trashed if this tree dies, and updated on missing global types */
     Queue<nanojit::Fragment*> dependentTrees;
+    /* Linked trees must be updated on missing global types, but are not dependent */
+    Queue<nanojit::Fragment*> linkedTrees;
     unsigned                branchCount;
     Queue<VMSideExit*>      sideExits;
     UnstableExit*           unstableExits;
 
     TreeInfo(nanojit::Fragment* _fragment,
              uint32 _globalShape,
              SlotList* _globalSlots)
       : fragment(_fragment),