Generate SSA information for scripts containing switch and try blocks, bug 704387. r=dvander
authorBrian Hackett <bhackett1024@gmail.com>
Sat, 24 Dec 2011 06:21:52 -0800
changeset 84568 eaac85c4c05f32affdc377a0ebe373379541325f
parent 84567 4b2c62d75deadce231799f9f77dd5cf5aa93b476
child 84569 c93d8c55f67d07b17be78bfefaf77641d0b95d6b
push id805
push userakeybl@mozilla.com
push dateWed, 01 Feb 2012 18:17:35 +0000
treeherdermozilla-aurora@6fb3bf232436 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdvander
bugs704387
milestone12.0a1
Generate SSA information for scripts containing switch and try blocks, bug 704387. r=dvander
js/src/jsanalyze.cpp
js/src/jsanalyze.h
--- a/js/src/jsanalyze.cpp
+++ b/js/src/jsanalyze.cpp
@@ -404,17 +404,17 @@ ScriptAnalysis::analyzeBytecode(JSContex
           case JSOP_CALL:
           case JSOP_NEW:
             /* Only consider potentially inlineable calls here. */
             hasFunctionCalls_ = true;
             break;
 
           case JSOP_TABLESWITCH:
           case JSOP_TABLESWITCHX: {
-            isInlineable = canTrackVars = false;
+            isInlineable = false;
             jsbytecode *pc2 = pc;
             unsigned jmplen = (op == JSOP_TABLESWITCH) ? JUMP_OFFSET_LEN : JUMPX_OFFSET_LEN;
             unsigned defaultOffset = offset + GetJumpOffset(pc, pc2);
             pc2 += jmplen;
             jsint low = GET_JUMP_OFFSET(pc2);
             pc2 += JUMP_OFFSET_LEN;
             jsint high = GET_JUMP_OFFSET(pc2);
             pc2 += JUMP_OFFSET_LEN;
@@ -434,17 +434,17 @@ ScriptAnalysis::analyzeBytecode(JSContex
                 getCode(targetOffset).safePoint = true;
                 pc2 += jmplen;
             }
             break;
           }
 
           case JSOP_LOOKUPSWITCH:
           case JSOP_LOOKUPSWITCHX: {
-            isInlineable = canTrackVars = false;
+            isInlineable = false;
             jsbytecode *pc2 = pc;
             unsigned jmplen = (op == JSOP_LOOKUPSWITCH) ? JUMP_OFFSET_LEN : JUMPX_OFFSET_LEN;
             unsigned defaultOffset = offset + GetJumpOffset(pc, pc2);
             pc2 += jmplen;
             unsigned npairs = GET_UINT16(pc2);
             pc2 += UINT16_LEN;
 
             if (!addJump(cx, defaultOffset, &nextOffset, &forwardJump, stackDepth))
@@ -467,17 +467,17 @@ ScriptAnalysis::analyzeBytecode(JSContex
 
           case JSOP_TRY: {
             /*
              * Everything between a try and corresponding catch or finally is conditional.
              * Note that there is no problem with code which is skipped by a thrown
              * exception but is not caught by a later handler in the same function:
              * no more code will execute, and it does not matter what is defined.
              */
-            isInlineable = canTrackVars = false;
+            isInlineable = false;
             JSTryNote *tn = script->trynotes()->vector;
             JSTryNote *tnlimit = tn + script->trynotes()->length;
             for (; tn < tnlimit; tn++) {
                 unsigned startOffset = script->mainOffset + tn->start;
                 if (startOffset == offset + 1) {
                     unsigned catchOffset = startOffset + tn->length;
 
                     /* This will overestimate try block code, for multiple catch/finally. */
@@ -1143,16 +1143,23 @@ ScriptAnalysis::analyzeSSA(JSContext *cx
 
     /*
      * All target offsets for forward jumps we in the middle of. We lazily add
      * pending entries at these targets for the original value of variables
      * modified before the branch rejoins.
      */
     Vector<uint32_t> branchTargets(cx);
 
+    /*
+     * Subset of branchTargets which are also exception handlers. Any value of
+     * a variable modified before the target is reached is a potential value
+     * at that target, along with the lazily added original value.
+     */
+    Vector<uint32_t> exceptionTargets(cx);
+
     uint32_t offset = 0;
     while (offset < script->length) {
         jsbytecode *pc = script->code + offset;
         JSOp op = (JSOp)*pc;
 
         uint32_t successorOffset = offset + GetBytecodeLength(pc);
 
         Bytecode *code = maybeCode(pc);
@@ -1178,17 +1185,17 @@ ScriptAnalysis::analyzeSSA(JSContext *cx
              * up when we *do* get to the back edge. This could be made lazier.
              *
              * We don't make phi nodes for values on the stack at the head of
              * the loop. These may be popped during the loop (i.e. for ITER
              * loops), but in such cases the original value is pushed back.
              */
             Vector<SlotValue> *&pending = code->pendingValues;
             if (pending) {
-                removeBranchTarget(branchTargets, offset);
+                removeBranchTarget(branchTargets, exceptionTargets, offset);
             } else {
                 pending = cx->new_< Vector<SlotValue> >(cx);
                 if (!pending) {
                     setOOM(cx);
                     return;
                 }
             }
 
@@ -1243,23 +1250,29 @@ ScriptAnalysis::analyzeSSA(JSContext *cx
                 }
             }
         } else if (code->pendingValues) {
             /*
              * New values at this point from a previous jump to this bytecode.
              * If there is fallthrough from the previous instruction, merge
              * with the current state and create phi nodes where necessary,
              * otherwise replace current values with the new values.
+             *
+             * Catch blocks are artifically treated as having fallthrough, so
+             * that values written inside the block but not subsequently
+             * overwritten are picked up.
              */
-            removeBranchTarget(branchTargets, offset);
+            bool exception = removeBranchTarget(branchTargets, exceptionTargets, offset);
             Vector<SlotValue> *pending = code->pendingValues;
             for (unsigned i = 0; i < pending->length(); i++) {
                 SlotValue &v = (*pending)[i];
-                if (code->fallthrough || code->jumpFallthrough)
+                if (code->fallthrough || code->jumpFallthrough ||
+                    (exception && values[v.slot].kind() != SSAValue::EMPTY)) {
                     mergeValue(cx, offset, values[v.slot], &v);
+                }
                 mergeBranchTarget(cx, values[v.slot], v.slot, branchTargets);
                 values[v.slot] = v.value;
             }
             freezeNewValues(cx, offset);
         }
 
         if (js_CodeSpec[op].format & JOF_DECOMPOSE) {
             offset = successorOffset;
@@ -1345,16 +1358,17 @@ ScriptAnalysis::analyzeSSA(JSContext *cx
           case JSOP_ARGDEC:
           case JSOP_INCLOCAL:
           case JSOP_DECLOCAL:
           case JSOP_LOCALINC:
           case JSOP_LOCALDEC: {
             uint32_t slot = GetBytecodeSlot(script, pc);
             if (trackSlot(slot)) {
                 mergeBranchTarget(cx, values[slot], slot, branchTargets);
+                mergeExceptionTarget(cx, values[slot], slot, exceptionTargets);
                 values[slot].initWritten(slot, offset);
             }
             break;
           }
 
           case JSOP_GETARG:
           case JSOP_GETLOCAL: {
             uint32_t slot = GetBytecodeSlot(script, pc);
@@ -1407,21 +1421,17 @@ ScriptAnalysis::analyzeSSA(JSContext *cx
             stack[stackDepth - 1] = code->poppedValues[pickedDepth];
             for (unsigned i = 0; i < pickedDepth; i++)
                 stack[stackDepth - 2 - i] = code->poppedValues[i];
             break;
           }
 
           /*
            * Switch and try blocks preserve the stack between the original op
-           * and all case statements or exception/finally handlers. Even though
-           * we don't track the values of variables in scripts containing such
-           * switch and try blocks, propagate the stack now to all targets as
-           * the values on the stack may be popped by intervening cleanup ops
-           * (e.g. LEAVEBLOCK, ENDITER).
+           * and all case statements or exception/finally handlers.
            */
 
           case JSOP_TABLESWITCH:
           case JSOP_TABLESWITCHX: {
             jsbytecode *pc2 = pc;
             unsigned jmplen = (op == JSOP_TABLESWITCH) ? JUMP_OFFSET_LEN : JUMPX_OFFSET_LEN;
             unsigned defaultOffset = offset + GetJumpOffset(pc, pc2);
             pc2 += jmplen;
@@ -1465,18 +1475,20 @@ ScriptAnalysis::analyzeSSA(JSContext *cx
           case JSOP_TRY: { 
             JSTryNote *tn = script->trynotes()->vector;
             JSTryNote *tnlimit = tn + script->trynotes()->length;
             for (; tn < tnlimit; tn++) {
                 unsigned startOffset = script->mainOffset + tn->start;
                 if (startOffset == offset + 1) {
                     unsigned catchOffset = startOffset + tn->length;
 
-                    if (tn->kind != JSTRY_ITER)
+                    if (tn->kind != JSTRY_ITER) {
                         checkBranchTarget(cx, catchOffset, branchTargets, values, stackDepth);
+                        checkExceptionTarget(cx, catchOffset, exceptionTargets);
+                    }
                 }
             }
             break;
           }
 
           default:;
         }
 
@@ -1649,16 +1661,32 @@ ScriptAnalysis::checkBranchTarget(JSCont
      */
     for (unsigned i = 0; i < targetDepth; i++) {
         uint32_t slot = StackSlot(script, i);
         checkPendingValue(cx, values[slot], slot, pending);
     }
 }
 
 void
+ScriptAnalysis::checkExceptionTarget(JSContext *cx, uint32_t catchOffset,
+                                     Vector<uint32_t> &exceptionTargets)
+{
+    /*
+     * The catch offset will already be in the branch targets, just check
+     * whether this is already a known exception target.
+     */
+    for (unsigned i = 0; i < exceptionTargets.length(); i++) {
+        if (exceptionTargets[i] == catchOffset)
+            return;
+    }
+    if (!exceptionTargets.append(catchOffset))
+        setOOM(cx);
+}
+
+void
 ScriptAnalysis::mergeBranchTarget(JSContext *cx, const SSAValue &value, uint32_t slot,
                                   const Vector<uint32_t> &branchTargets)
 {
     if (slot >= numSlots) {
         /*
          * There is no need to lazily check that there are pending values at
          * branch targets for slots on the stack, these are added to pending
          * eagerly.
@@ -1674,26 +1702,66 @@ ScriptAnalysis::mergeBranchTarget(JSCont
      */
     for (unsigned i = 0; i < branchTargets.length(); i++) {
         Vector<SlotValue> *pending = getCode(branchTargets[i]).pendingValues;
         checkPendingValue(cx, value, slot, pending);
     }
 }
 
 void
-ScriptAnalysis::removeBranchTarget(Vector<uint32_t> &branchTargets, uint32_t offset)
+ScriptAnalysis::mergeExceptionTarget(JSContext *cx, const SSAValue &value, uint32_t slot,
+                                     const Vector<uint32_t> &exceptionTargets)
 {
+    JS_ASSERT(trackSlot(slot));
+
+    /*
+     * Update the value at exception targets with the value of a variable
+     * before it is overwritten. Unlike mergeBranchTarget, this is done whether
+     * or not the overwritten value is the value of the variable at the
+     * original branch. Values for a variable which are written after the
+     * try block starts and overwritten before it is finished can still be
+     * seen at exception handlers via exception paths.
+     */
+    for (unsigned i = 0; i < exceptionTargets.length(); i++) {
+        Vector<SlotValue> *pending = getCode(exceptionTargets[i]).pendingValues;
+
+        bool duplicate = false;
+        for (unsigned i = 0; i < pending->length(); i++) {
+            if ((*pending)[i].slot == slot && (*pending)[i].value.equals(value))
+                duplicate = true;
+        }
+
+        if (!duplicate && !pending->append(SlotValue(slot, value)))
+            setOOM(cx);
+    }
+}
+
+bool
+ScriptAnalysis::removeBranchTarget(Vector<uint32_t> &branchTargets,
+                                   Vector<uint32_t> &exceptionTargets,
+                                   uint32_t offset)
+{
+    bool exception = false;
+    for (unsigned i = 0; i < exceptionTargets.length(); i++) {
+        if (exceptionTargets[i] == offset) {
+            exceptionTargets[i] = branchTargets.back();
+            exceptionTargets.popBack();
+            exception = true;
+            break;
+        }
+    }
     for (unsigned i = 0; i < branchTargets.length(); i++) {
         if (branchTargets[i] == offset) {
             branchTargets[i] = branchTargets.back();
             branchTargets.popBack();
-            return;
+            return exception;
         }
     }
     JS_ASSERT(OOM());
+    return exception;
 }
 
 void
 ScriptAnalysis::freezeNewValues(JSContext *cx, uint32_t offset)
 {
     Bytecode &code = getCode(offset);
 
     Vector<SlotValue> *pending = code.pendingValues;
--- a/js/src/jsanalyze.h
+++ b/js/src/jsanalyze.h
@@ -1087,18 +1087,18 @@ class ScriptAnalysis
         if (slot >= numSlots)
             return true;
         return escapedSlots[slot];
     }
 
     /*
      * Whether we distinguish different writes of this variable while doing
      * SSA analysis. Escaping locals can be written in other scripts, and the
-     * presence of NAME opcodes, switch or try blocks keeps us from tracking
-     * variable values at each point.
+     * presence of NAME opcodes which could alias local variables or arguments
+     * keeps us from tracking variable values at each point.
      */
     bool trackSlot(uint32_t slot) { return !slotEscapes(slot) && canTrackVars; }
 
     const LifetimeVariable & liveness(uint32_t slot) {
         JS_ASSERT(script->compartment()->activeAnalysis);
         JS_ASSERT(!slotEscapes(slot));
         return lifetimes[slot];
     }
@@ -1148,19 +1148,25 @@ class ScriptAnalysis
     /* SSA helpers */
     bool makePhi(JSContext *cx, uint32_t slot, uint32_t offset, SSAValue *pv);
     void insertPhi(JSContext *cx, SSAValue &phi, const SSAValue &v);
     void mergeValue(JSContext *cx, uint32_t offset, const SSAValue &v, SlotValue *pv);
     void checkPendingValue(JSContext *cx, const SSAValue &v, uint32_t slot,
                            Vector<SlotValue> *pending);
     void checkBranchTarget(JSContext *cx, uint32_t targetOffset, Vector<uint32_t> &branchTargets,
                            SSAValue *values, uint32_t stackDepth);
+    void checkExceptionTarget(JSContext *cx, uint32_t catchOffset,
+                              Vector<uint32_t> &exceptionTargets);
     void mergeBranchTarget(JSContext *cx, const SSAValue &value, uint32_t slot,
                            const Vector<uint32_t> &branchTargets);
-    void removeBranchTarget(Vector<uint32_t> &branchTargets, uint32_t offset);
+    void mergeExceptionTarget(JSContext *cx, const SSAValue &value, uint32_t slot,
+                              const Vector<uint32_t> &exceptionTargets);
+    bool removeBranchTarget(Vector<uint32_t> &branchTargets,
+                            Vector<uint32_t> &exceptionTargets,
+                            uint32_t offset);
     void freezeNewValues(JSContext *cx, uint32_t offset);
 
     struct TypeInferenceState {
         Vector<SSAPhiNode *> phiNodes;
         bool hasGetSet;
         bool hasHole;
         types::TypeSet *forTypes;
         TypeInferenceState(JSContext *cx)