Optimize integer performance with nested trees. r=gal
authorDavid Anderson <dvander@alliedmods.net>
Mon, 09 Nov 2009 11:02:56 -0500
changeset 26560 cad82a9d57c7b64d7f45a5540e0c584ed29b390c
parent 26559 290980a8887eb4ab55cd6d8b495e556fc97d0af5
child 26561 8415bc81a9d30a184bae9521976669ec0dc69179
push id2105
push userrsayre@mozilla.com
push dateMon, 09 Nov 2009 16:03:16 +0000
reviewersgal
milestone1.9.1.6pre
Optimize integer performance with nested trees. r=gal
js/src/jstracer.cpp
js/src/jstracer.h
--- a/js/src/jstracer.cpp
+++ b/js/src/jstracer.cpp
@@ -3289,16 +3289,36 @@ TraceRecorder::prepareTreeCall(Fragment*
                 + sp_adj /* adjust for stack in outer frame inner tree can't see */
                 + ti->nativeStackBase), /* plus the inner tree's stack base */
                 lirbuf->state, offsetof(InterpState, sp));
         lir->insStorei(lir->ins2i(LIR_piadd, lirbuf->rp, rp_adj),
                 lirbuf->state, offsetof(InterpState, rp));
     }
 }
 
+static unsigned
+BuildGlobalTypeMapFromInnerTree(Queue<uint8>& typeMap, VMSideExit* inner)
+{
+#if defined DEBUG
+    unsigned initialSlots = typeMap.length();
+#endif
+    /* First, use the innermost exit's global typemap. */
+    typeMap.add(getGlobalTypeMap(inner), inner->numGlobalSlots);
+
+    /* Add missing global types from the innermost exit's tree. */
+    TreeInfo* innerTree = (TreeInfo*)inner->from->root->vmprivate;
+    unsigned slots = inner->numGlobalSlots;
+    if (slots < innerTree->nGlobalTypes()) {
+        typeMap.add(innerTree->globalTypeMap() + slots, innerTree->nGlobalTypes() - slots);
+        slots = innerTree->nGlobalTypes();
+    }
+    JS_ASSERT(typeMap.length() - initialSlots == slots);
+    return slots;
+}
+
 /* Record a call to an inner tree. */
 JS_REQUIRES_STACK void
 TraceRecorder::emitTreeCall(Fragment* inner, VMSideExit* exit)
 {
     TreeInfo* ti = (TreeInfo*)inner->vmprivate;
 
     /* Invoke the inner tree. */
     LIns* args[] = { INS_CONSTPTR(inner), lirbuf->state }; /* reverse order */
@@ -3307,22 +3327,17 @@ TraceRecorder::emitTreeCall(Fragment* in
     /* Read back all registers, in case the called tree changed any of them. */
     JS_ASSERT(!memchr(getGlobalTypeMap(exit), JSVAL_BOXED, exit->numGlobalSlots) &&
               !memchr(getStackTypeMap(exit), JSVAL_BOXED, exit->numStackSlots));
     /* bug 502604 - It is illegal to extend from the outer typemap without first extending from the
      * inner. Make a new typemap here.
      */
     TypeMap fullMap;
     fullMap.add(getStackTypeMap(exit), exit->numStackSlots);
-    fullMap.add(getGlobalTypeMap(exit), exit->numGlobalSlots);
-    TreeInfo* innerTree = (TreeInfo*)exit->from->root->vmprivate;
-    if (exit->numGlobalSlots < innerTree->nGlobalTypes()) {
-        fullMap.add(innerTree->globalTypeMap() + exit->numGlobalSlots,
-                    innerTree->nGlobalTypes() - exit->numGlobalSlots);
-    }
+    BuildGlobalTypeMapFromInnerTree(fullMap, exit);
     import(ti, inner_sp_ins, exit->numStackSlots, fullMap.length() - exit->numStackSlots,
            exit->calldepth, fullMap.data());
 
     /* Restore sp and rp to their original values (we still have them in a register). */
     if (callDepth > 0) {
         lir->insStorei(lirbuf->sp, lirbuf->state, offsetof(InterpState, sp));
         lir->insStorei(lirbuf->rp, lirbuf->state, offsetof(InterpState, rp));
     }
@@ -4118,44 +4133,19 @@ js_AttemptToExtendTree(JSContext* cx, VM
                guard (anchor) has the type information for everything below the current scope,
                and the actual guard we exited from has the types for everything in the current
                scope (and whatever it inlined). We have to merge those maps here. */
             VMSideExit* e1 = anchor;
             VMSideExit* e2 = exitedFrom;
             fullMap.add(getStackTypeMap(e1), e1->numStackSlotsBelowCurrentFrame);
             fullMap.add(getStackTypeMap(e2), e2->numStackSlots);
             stackSlots = fullMap.length();
-            fullMap.add(getGlobalTypeMap(e2), e2->numGlobalSlots);
-            if (e2->numGlobalSlots < e1->numGlobalSlots) {
-                /* Watch out for an extremely rare case (bug 502714). The sequence of events is:
-                 * 
-                 * 1) Inner tree compiles not knowing about global X (which has type A).
-                 * 2) Inner tree learns about global X and specializes it to a different type
-                 *    (type B).
-                 * 3) Outer tree records inner tree with global X as type A, exiting as B.
-                 * 4) Outer tree now has a nesting guard with typeof(X)=B.
-                 * 5) Inner tree takes its original exit that does not know about X.
-                 * 
-                 * In this case, the nesting guard fails, and now it is illegal to use the nested
-                 * typemap entry for X. The correct entry is in the inner guard's TreeInfo,
-                 * analogous to the solution for bug 476653.
-                 */
-                TreeInfo* innerTree = (TreeInfo*)e2->from->root->vmprivate;
-                unsigned slots = e2->numGlobalSlots;
-                if (innerTree->nGlobalTypes() > slots) {
-                    unsigned addSlots = JS_MIN(innerTree->nGlobalTypes() - slots,
-                                               e1->numGlobalSlots - slots);
-                    fullMap.add(innerTree->globalTypeMap() + e2->numGlobalSlots, addSlots);
-                    slots += addSlots;
-                }
-                if (slots < e1->numGlobalSlots)
-                    fullMap.add(getGlobalTypeMap(e1) + slots, e1->numGlobalSlots - slots);
-                JS_ASSERT(slots == e1->numGlobalSlots);
-            }
-            ngslots = e1->numGlobalSlots;
+            ngslots = BuildGlobalTypeMapFromInnerTree(fullMap, e2);
+            JS_ASSERT(ngslots >= e1->numGlobalSlots); // inner tree must have all globals
+            JS_ASSERT(ngslots == fullMap.length() - stackSlots);
             typeMap = fullMap.data();
         }
         JS_ASSERT(ngslots >= anchor->numGlobalSlots);
         return js_StartRecorder(cx, anchor, c, (TreeInfo*)f->vmprivate, stackSlots,
                                 ngslots, typeMap, exitedFrom, outer, cx->fp->argc);
     }
     return false;
 }
@@ -4789,31 +4779,34 @@ LeaveTree(InterpState& state, VMSideExit
        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());
     uint8* globalTypeMap;
 
     /* Are there enough globals? This is the ideal fast path. */
+    Queue<uint8> typeMap(0);
     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);
+        JS_ASSERT(((TreeInfo*)innermost->from->root->vmprivate)->nGlobalTypes() == ngslots);
+        JS_ASSERT(((TreeInfo*)innermost->from->root->vmprivate)->nGlobalTypes() >
+                  innermost->numGlobalSlots);
+        typeMap.ensure(ngslots);
+#ifdef DEBUG
+        unsigned check_ngslots =
+#endif
+        BuildGlobalTypeMapFromInnerTree(typeMap, innermost);
+        JS_ASSERT(check_ngslots == ngslots);
+        globalTypeMap = typeMap.data();
     }
 
     /* 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
@@ -57,29 +57,35 @@
 #endif
 
 template <typename T>
 class Queue : public avmplus::GCObject {
     T* _data;
     unsigned _len;
     unsigned _max;
 
+public:
     void ensure(unsigned size) {
+        if (!_max)
+            _max = 16;
         while (_max < size)
             _max <<= 1;
         _data = (T*)realloc(_data, _max * sizeof(T));
 #if defined(DEBUG)
         memset(&_data[_len], 0xcd, _max - _len);
 #endif
     }
-public:
+
     Queue(unsigned max = 16) {
         this->_max = max;
         this->_len = 0;
-        this->_data = (T*)malloc(max * sizeof(T));
+        if (max)
+            this->_data = (T*)malloc(max * sizeof(T));
+        else
+            this->_data = NULL;
     }
 
     ~Queue() {
         free(_data);
     }
 
     bool contains(T a) {
         for (unsigned n = 0; n < _len; ++n) {