Bug 944930 - Remove block index from aliasedvar ops, use a binary search to find the block chain for a given pc, r=luke.
authorBrian Hackett <bhackett1024@gmail.com>
Sat, 07 Dec 2013 11:03:07 -0800
changeset 175066 5bb192fc539e3a2935f7addcc3a9ce79742ebec3
parent 175065 8dcaf0cd8b895c1bbdcc1b5a63f192c3d714344f
child 175067 edac8cba9f78c0160edf79ff56041831ef44c2fa
push id445
push userffxbld
push dateMon, 10 Mar 2014 22:05:19 +0000
treeherdermozilla-release@dc38b741b04e [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersluke
bugs944930
milestone28.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 944930 - Remove block index from aliasedvar ops, use a binary search to find the block chain for a given pc, r=luke.
js/src/configure.in
js/src/frontend/BytecodeEmitter.cpp
js/src/frontend/BytecodeEmitter.h
js/src/jit-test/tests/jaeger/bug563000/trap-from-add-ool.js
js/src/jsopcode.cpp
js/src/jsopcode.h
js/src/jsopcode.tbl
js/src/jsscript.cpp
js/src/jsscript.h
js/src/vm/ScopeObject.cpp
js/src/vm/Xdr.h
--- a/js/src/configure.in
+++ b/js/src/configure.in
@@ -1130,17 +1130,16 @@ if test "$GNU_CC"; then
     # -Wdeclaration-after-statement - MSVC doesn't like these
     # -Werror=return-type - catches missing returns, zero false positives
     # -Wtype-limits - catches overflow bugs, few false positives
     # -Wempty-body - catches bugs, e.g. "if (c); foo();", few false positives
     # -Wsign-compare - catches comparison of signed and unsigned types
     #
     _WARNINGS_CFLAGS="${_WARNINGS_CFLAGS} -Wall -Wpointer-arith -Wdeclaration-after-statement"
     MOZ_C_SUPPORTS_WARNING(-W, error=return-type, ac_c_has_werror_return_type)
-    MOZ_C_SUPPORTS_WARNING(-W, type-limits, ac_c_has_wtype_limits)
     MOZ_C_SUPPORTS_WARNING(-W, empty-body, ac_c_has_wempty_body)
     MOZ_C_SUPPORTS_WARNING(-W, sign-compare, ac_c_has_sign_compare)
 
     # Turn off the following warnings that -Wall turns on:
     # -Wno-unused - lots of violations in third-party code
     #
     _WARNINGS_CFLAGS="${_WARNINGS_CFLAGS} -Wno-unused"
 
--- a/js/src/frontend/BytecodeEmitter.cpp
+++ b/js/src/frontend/BytecodeEmitter.cpp
@@ -673,23 +673,30 @@ EnclosingStaticScope(BytecodeEmitter *bc
     return bce->sc->asFunctionBox()->function();
 }
 
 // Push a block scope statement and link blockObj into bce->blockChain.
 static bool
 PushBlockScopeBCE(BytecodeEmitter *bce, StmtInfoBCE *stmt, ObjectBox *objbox,
                   ptrdiff_t top)
 {
+    uint32_t parent = UINT32_MAX;
+    if (bce->blockChain) {
+        StmtInfoBCE *stmt = bce->topScopeStmt;
+        for (; stmt->blockObj != bce->blockChain; stmt = stmt->down) {}
+        parent = stmt->blockScopeIndex;
+    }
+
     StaticBlockObject &blockObj = objbox->object->as<StaticBlockObject>();
 
     PushStatementBCE(bce, stmt, STMT_BLOCK, top);
 
     unsigned scopeObjectIndex = bce->objectList.add(objbox);
     stmt->blockScopeIndex = bce->blockScopeList.length();
-    if (!bce->blockScopeList.append(scopeObjectIndex, bce->offset()))
+    if (!bce->blockScopeList.append(scopeObjectIndex, bce->offset(), parent))
         return false;
 
     blockObj.initEnclosingStaticScope(EnclosingStaticScope(bce));
     FinishPushBlockScope(bce, stmt, blockObj);
 
     return true;
 }
 
@@ -809,33 +816,28 @@ EmitUnaliasedVarOp(ExclusiveContext *cx,
     return true;
 }
 
 static bool
 EmitAliasedVarOp(ExclusiveContext *cx, JSOp op, ScopeCoordinate sc, BytecodeEmitter *bce)
 {
     JS_ASSERT(JOF_OPTYPE(op) == JOF_SCOPECOORD);
 
-    uint32_t maybeBlockIndex = UINT32_MAX;
-    if (bce->blockChain)
-        maybeBlockIndex = bce->objectList.indexOf(bce->blockChain);
-
-    unsigned n = 2 * sizeof(uint16_t) + sizeof(uint32_t);
+    unsigned n = 2 * sizeof(uint16_t);
     JS_ASSERT(int(n) + 1 /* op */ == js_CodeSpec[op].length);
 
     ptrdiff_t off = EmitN(cx, bce, op, n);
     if (off < 0)
         return false;
 
     jsbytecode *pc = bce->code(off);
     SET_UINT16(pc, sc.hops);
     pc += sizeof(uint16_t);
     SET_UINT16(pc, sc.slot);
     pc += sizeof(uint16_t);
-    SET_UINT32_INDEX(pc, maybeBlockIndex);
     CheckTypeSet(cx, bce, op);
     return true;
 }
 
 static unsigned
 ClonedBlockDepth(BytecodeEmitter *bce)
 {
     unsigned clonedBlockDepth = 0;
@@ -6874,23 +6876,24 @@ CGTryNoteList::finish(TryNoteArray *arra
 {
     JS_ASSERT(length() == array->length);
 
     for (unsigned i = 0; i < length(); i++)
         array->vector[i] = list[i];
 }
 
 bool
-CGBlockScopeList::append(uint32_t scopeObject, uint32_t offset)
+CGBlockScopeList::append(uint32_t scopeObject, uint32_t offset, uint32_t parent)
 {
     BlockScopeNote note;
     mozilla::PodZero(&note);
 
     note.index = scopeObject;
     note.start = offset;
+    note.parent = parent;
 
     return list.append(note);
 }
 
 void
 CGBlockScopeList::recordEnd(uint32_t index, uint32_t offset)
 {
     JS_ASSERT(index < length());
--- a/js/src/frontend/BytecodeEmitter.h
+++ b/js/src/frontend/BytecodeEmitter.h
@@ -56,17 +56,17 @@ struct CGTryNoteList {
     size_t length() const { return list.length(); }
     void finish(TryNoteArray *array);
 };
 
 struct CGBlockScopeList {
     Vector<BlockScopeNote> list;
     CGBlockScopeList(ExclusiveContext *cx) : list(cx) {}
 
-    bool append(uint32_t scopeObject, uint32_t offset);
+    bool append(uint32_t scopeObject, uint32_t offset, uint32_t parent);
     void recordEnd(uint32_t index, uint32_t offset);
     size_t length() const { return list.length(); }
     void finish(BlockScopeArray *array);
 };
 
 struct StmtInfoBCE;
 
 // Use zero inline elements because these go on the stack and affect how many
--- a/js/src/jit-test/tests/jaeger/bug563000/trap-from-add-ool.js
+++ b/js/src/jit-test/tests/jaeger/bug563000/trap-from-add-ool.js
@@ -1,14 +1,14 @@
 // |jit-test| debug
 setDebug(true);
 x = "notset";
 function main() {
   /* The JSOP_STOP in main. */
-  a = { valueOf: function () { trap(main, 95, "success()"); } };
+  a = { valueOf: function () { trap(main, 91, "success()"); } };
   b = "";
   eval();
   a + b;
   x = "failure";
 }
 function success() { x = "success"; }
 
 main();
--- a/js/src/jsopcode.cpp
+++ b/js/src/jsopcode.cpp
@@ -1427,35 +1427,62 @@ js_QuoteString(ExclusiveContext *cx, JSS
     char *bytes = QuoteString(&sprinter, str, quote);
     if (!bytes)
         return nullptr;
     return js_NewStringCopyZ<CanGC>(cx, bytes);
 }
 
 /************************************************************************/
 
-static JSObject *
-GetBlockChainAtPC(JSContext *cx, JSScript *script, jsbytecode *pc)
+StaticBlockObject *
+js::GetBlockChainAtPC(JSScript *script, jsbytecode *pc)
 {
     JS_ASSERT(script->containsPC(pc));
-    JS_ASSERT(pc >= script->main());
-
-    ptrdiff_t offset = pc - script->main();
 
     if (!script->hasBlockScopes())
         return nullptr;
 
+    if (pc < script->main())
+        return nullptr;
+    ptrdiff_t offset = pc - script->main();
+
     BlockScopeArray *blockScopes = script->blockScopes();
-    JSObject *blockChain = nullptr;
-    for (uint32_t n = 0; n < blockScopes->length; n++) {
-        const BlockScopeNote *note = &blockScopes->vector[n];
-        if (note->start > offset)
-            break;
-        if (offset <= note->start + note->length)
-            blockChain = script->getObject(note->index);
+    StaticBlockObject *blockChain = nullptr;
+
+    // Find the innermost block chain using a binary search.
+    size_t bottom = 0;
+    size_t top = blockScopes->length;
+
+    while (bottom < top) {
+        size_t mid = bottom + (top - bottom) / 2;
+        const BlockScopeNote *note = &blockScopes->vector[mid];
+        if (note->start <= offset) {
+            // Block scopes are ordered in the list by their starting offset, and since
+            // blocks form a tree ones earlier in the list may cover the pc even if
+            // later blocks end before the pc. This only happens when the earlier block
+            // is a parent of the later block, so we need to check parents of |mid| in
+            // the searched range for coverage.
+            size_t check = mid;
+            while (check >= bottom) {
+                const BlockScopeNote *checkNote = &blockScopes->vector[check];
+                JS_ASSERT(checkNote->start <= offset);
+                if (offset <= checkNote->start + checkNote->length) {
+                    // We found a matching block chain but there may be inner ones
+                    // at a higher block chain index than mid. Continue the binary search.
+                    blockChain = &script->getObject(checkNote->index)->as<StaticBlockObject>();
+                    break;
+                }
+                if (checkNote->parent == UINT32_MAX)
+                    break;
+                check = checkNote->parent;
+            }
+            bottom = mid + 1;
+        } else {
+            top = mid;
+        }
     }
 
     return blockChain;
 }
 
 namespace {
 /*
  * The expression decompiler is invoked by error handling code to produce a
@@ -1711,17 +1738,17 @@ ExpressionDecompiler::loadAtom(jsbytecod
 {
     return script->getAtom(GET_UINT32_INDEX(pc));
 }
 
 JSAtom *
 ExpressionDecompiler::findLetVar(jsbytecode *pc, unsigned depth)
 {
     if (script->hasObjects()) {
-        JSObject *chain = GetBlockChainAtPC(cx, script, pc);
+        JSObject *chain = GetBlockChainAtPC(script, pc);
         if (!chain)
             return nullptr;
         JS_ASSERT(chain->is<BlockObject>());
         do {
             BlockObject &block = chain->as<BlockObject>();
             uint32_t blockDepth = block.stackDepth();
             uint32_t blockCount = block.slotCount();
             if (uint32_t(depth - blockDepth) < uint32_t(blockCount)) {
--- a/js/src/jsopcode.h
+++ b/js/src/jsopcode.h
@@ -772,16 +772,21 @@ class PCCounts
 JS_STATIC_ASSERT(sizeof(PCCounts) % sizeof(Value) == 0);
 
 static inline jsbytecode *
 GetNextPc(jsbytecode *pc)
 {
     return pc + GetBytecodeLength(pc);
 }
 
+class StaticBlockObject;
+
+StaticBlockObject *
+GetBlockChainAtPC(JSScript *script, jsbytecode *pc);
+
 } /* namespace js */
 
 #if defined(DEBUG)
 /*
  * Disassemblers, for debugging only.
  */
 bool
 js_Disassemble(JSContext *cx, JS::Handle<JSScript*> script, bool lines, js::Sprinter *sp);
--- a/js/src/jsopcode.tbl
+++ b/js/src/jsopcode.tbl
@@ -313,22 +313,20 @@ OPDEF(JSOP_FINALLY,     135,"finally",  
  * 'with', and 'arguments'. All of these cases require creating a CallObject to
  * own the aliased variable.
  *
  * An ALIASEDVAR opcode contains the following immediates:
  *  uint16 hops:  the number of scope objects to skip to find the ScopeObject
  *                containing the variable being accessed
  *  uint16 slot:  the slot containing the variable in the ScopeObject (this
  *                'slot' does not include RESERVED_SLOTS).
- *  uint32 block: the index (into the script object table) of the block chain
- *                at the point of the variable access.
  */
-OPDEF(JSOP_GETALIASEDVAR, 136,"getaliasedvar",NULL,   9,  0,  1, JOF_SCOPECOORD|JOF_NAME|JOF_TYPESET)
-OPDEF(JSOP_CALLALIASEDVAR,137,"callaliasedvar",NULL,  9,  0,  1, JOF_SCOPECOORD|JOF_NAME|JOF_TYPESET)
-OPDEF(JSOP_SETALIASEDVAR, 138,"setaliasedvar",NULL,   9,  1,  1, JOF_SCOPECOORD|JOF_NAME|JOF_SET|JOF_DETECTING)
+OPDEF(JSOP_GETALIASEDVAR, 136,"getaliasedvar",NULL,   5,  0,  1, JOF_SCOPECOORD|JOF_NAME|JOF_TYPESET)
+OPDEF(JSOP_CALLALIASEDVAR,137,"callaliasedvar",NULL,  5,  0,  1, JOF_SCOPECOORD|JOF_NAME|JOF_TYPESET)
+OPDEF(JSOP_SETALIASEDVAR, 138,"setaliasedvar",NULL,   5,  1,  1, JOF_SCOPECOORD|JOF_NAME|JOF_SET|JOF_DETECTING)
 
 OPDEF(JSOP_UNUSED139,  139, "unused139",   NULL,         1,  0,  0,  JOF_BYTE)
 OPDEF(JSOP_UNUSED140,  140, "unused140",   NULL,         1,  0,  0,  JOF_BYTE)
 OPDEF(JSOP_UNUSED141,  141, "unused141",   NULL,         1,  0,  0,  JOF_BYTE)
 OPDEF(JSOP_UNUSED142,  142, "unused142",   NULL,         1,  0,  0,  JOF_BYTE)
 
 /*
  * Intrinsic names are emitted instead of JSOP_*NAME ops when the
--- a/js/src/jsscript.cpp
+++ b/js/src/jsscript.cpp
@@ -802,17 +802,18 @@ js::XDRScript(XDRState<mode> *xdr, Handl
             }
         } while (tn != tnfirst);
     }
 
     for (i = 0; i < nblockscopes; ++i) {
         BlockScopeNote *note = &script->blockScopes()->vector[i];
         if (!xdr->codeUint32(&note->index) ||
             !xdr->codeUint32(&note->start) ||
-            !xdr->codeUint32(&note->length))
+            !xdr->codeUint32(&note->length) ||
+            !xdr->codeUint32(&note->parent))
         {
             return false;
         }
     }
 
     if (mode == XDR_DECODE)
         scriptp.set(script);
 
--- a/js/src/jsscript.h
+++ b/js/src/jsscript.h
@@ -80,17 +80,17 @@ struct JSTryNote {
 };
 
 namespace js {
 
 struct BlockScopeNote {
     uint32_t        index;      // Index of StaticScopeObject in the object array.
     uint32_t        start;      // Bytecode offset at which this scope starts.
     uint32_t        length;     // Bytecode length of scope.
-    uint32_t        padding;    // Pad to 64-bit boundary.
+    uint32_t        parent;     // Index of parent block scope in notes, or UINT32_MAX.
 };
 
 struct ConstArray {
     js::HeapValue   *vector;    /* array of indexed constant values */
     uint32_t        length;
 };
 
 struct ObjectArray {
--- a/js/src/vm/ScopeObject.cpp
+++ b/js/src/vm/ScopeObject.cpp
@@ -33,21 +33,20 @@ typedef Rooted<ArgumentsObject *> Rooted
 /*****************************************************************************/
 
 static JSObject *
 InnermostStaticScope(JSScript *script, jsbytecode *pc)
 {
     JS_ASSERT(script->containsPC(pc));
     JS_ASSERT(JOF_OPTYPE(*pc) == JOF_SCOPECOORD);
 
-    uint32_t blockIndex = GET_UINT32_INDEX(pc + 2 * sizeof(uint16_t));
-
-    if (blockIndex == UINT32_MAX)
-        return script->function();
-    return &script->getObject(blockIndex)->as<StaticBlockObject>();
+    StaticBlockObject *block = GetBlockChainAtPC(script, pc);
+    if (block)
+        return block;
+    return script->function();
 }
 
 Shape *
 js::ScopeCoordinateToStaticScopeShape(JSScript *script, jsbytecode *pc)
 {
     StaticScopeIter<NoGC> ssi(InnermostStaticScope(script, pc));
     ScopeCoordinate sc(pc);
     while (true) {
--- a/js/src/vm/Xdr.h
+++ b/js/src/vm/Xdr.h
@@ -17,17 +17,17 @@ namespace js {
  * Bytecode version number. Increment the subtrahend whenever JS bytecode
  * changes incompatibly.
  *
  * This version number is XDR'd near the front of xdr bytecode and
  * aborts deserialization if there is a mismatch between the current
  * and saved versions. If deserialization fails, the data should be
  * invalidated if possible.
  */
-static const uint32_t XDR_BYTECODE_VERSION = uint32_t(0xb973c0de - 155);
+static const uint32_t XDR_BYTECODE_VERSION = uint32_t(0xb973c0de - 156);
 
 class XDRBuffer {
   public:
     XDRBuffer(JSContext *cx)
       : context(cx), base(nullptr), cursor(nullptr), limit(nullptr) { }
 
     JSContext *cx() const {
         return context;