Add analysis to eliminate dead resume point operands, bug 814997. r=dvander
authorBrian Hackett <bhackett1024@gmail.com>
Fri, 30 Nov 2012 15:59:52 -0700
changeset 114659 0952f7c80055460d608473728eff78a827a92b70
parent 114658 6e8ee650b33c1d2d1a3b6d81263e4ccecbfe7188
child 114660 cd51ab1d33f59cd8a2961291c62a200c25dcf3fe
push id18906
push userbhackett@mozilla.com
push dateFri, 30 Nov 2012 22:59:59 +0000
treeherdermozilla-inbound@0952f7c80055 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdvander
bugs814997
milestone20.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
Add analysis to eliminate dead resume point operands, bug 814997. r=dvander
js/src/ion/Ion.cpp
js/src/ion/IonAnalysis.cpp
js/src/ion/IonAnalysis.h
js/src/ion/IonBuilder.cpp
js/src/ion/MIR.cpp
js/src/ion/MIR.h
js/src/jsinfer.cpp
js/src/jsinterp.cpp
--- a/js/src/ion/Ion.cpp
+++ b/js/src/ion/Ion.cpp
@@ -844,16 +844,25 @@ CompileBackEnd(MIRGenerator *mir)
         AliasAnalysis analysis(mir, graph);
         if (!analysis.analyze())
             return NULL;
         IonSpewPass("Alias analysis");
         AssertGraphCoherency(graph);
 
         if (mir->shouldCancel("Alias analysis"))
             return NULL;
+
+        // Eliminating dead resume point operands requires basic block
+        // instructions to be numbered. Reuse the numbering computed during
+        // alias analysis.
+        if (!EliminateDeadResumePointOperands(mir, graph))
+            return NULL;
+
+        if (mir->shouldCancel("Eliminate dead resume point operands"))
+            return NULL;
     }
 
     if (js_IonOptions.edgeCaseAnalysis) {
         EdgeCaseAnalysis edgeCaseAnalysis(mir, graph);
         if (!edgeCaseAnalysis.analyzeEarly())
             return NULL;
         IonSpewPass("Edge Case Analysis (Early)");
         AssertGraphCoherency(graph);
--- a/js/src/ion/IonAnalysis.cpp
+++ b/js/src/ion/IonAnalysis.cpp
@@ -35,16 +35,105 @@ ion::SplitCriticalEdges(MIRGraph &graph)
 
             block->replaceSuccessor(i, split);
             target->replacePredecessor(*block, split);
         }
     }
     return true;
 }
 
+// Operands to a resume point which are dead at the point of the resume can be
+// replaced with undefined values. This analysis supports limited detection of
+// dead operands, pruning those which are defined in the resume point's basic
+// block and have no uses outside the block or at points later than the resume
+// point.
+//
+// This is intended to ensure that extra resume points within a basic block
+// will not artificially extend the lifetimes of any SSA values. This could
+// otherwise occur if the new resume point captured a value which is created
+// between the old and new resume point and is dead at the new resume point.
+bool
+ion::EliminateDeadResumePointOperands(MIRGenerator *mir, MIRGraph &graph)
+{
+    for (PostorderIterator block = graph.poBegin(); block != graph.poEnd(); block++) {
+        if (mir->shouldCancel("Eliminate Dead Resume Point Operands (main loop)"))
+            return false;
+
+        // The logic below can get confused on infinite loops.
+        if (block->isLoopHeader() && block->backedge() == *block)
+            continue;
+
+        for (MInstructionIterator ins = block->begin(); ins != block->end(); ins++) {
+            // No benefit to replacing constant operands with other constants.
+            if (ins->isConstant())
+                continue;
+
+            // Scanning uses does not give us sufficient information to tell
+            // where instructions that are involved in box/unbox operations or
+            // parameter passing might be live. Rewriting uses of these terms
+            // in resume points may affect the interpreter's behavior. Rather
+            // than doing a more sophisticated analysis, just ignore these.
+            if (ins->isUnbox() || ins->isParameter())
+                continue;
+
+            // Check if this instruction's result is only used within the
+            // current block, and keep track of its last use in a definition
+            // (not resume point). This requires the instructions in the block
+            // to be numbered, ensured by running this immediately after alias
+            // analysis.
+            uint32 maxDefinition = 0;
+            for (MUseDefIterator uses(*ins); uses; uses++) {
+                if (uses.def()->block() != *block || uses.def()->isBox() || uses.def()->isPassArg()) {
+                    maxDefinition = UINT32_MAX;
+                    break;
+                }
+                maxDefinition = Max(maxDefinition, uses.def()->id());
+            }
+            if (maxDefinition == UINT32_MAX)
+                continue;
+
+            // Walk the uses a second time, removing any in resume points after
+            // the last use in a definition.
+            for (MUseIterator uses(ins->usesBegin()); uses != ins->usesEnd(); ) {
+                if (uses->node()->isDefinition()) {
+                    uses++;
+                    continue;
+                }
+                MResumePoint *mrp = uses->node()->toResumePoint();
+                if (mrp->block() != *block ||
+                    !mrp->instruction() ||
+                    mrp->instruction() == *ins ||
+                    mrp->instruction()->id() <= maxDefinition)
+                {
+                    uses++;
+                    continue;
+                }
+
+                // Store an undefined value in place of all dead resume point
+                // operands. Making any such substitution can in general alter
+                // the interpreter's behavior, even though the code is dead, as
+                // the interpreter will still execute opcodes whose effects
+                // cannot be observed. If the undefined value were to flow to,
+                // say, a dead property access the interpreter could throw an
+                // exception; we avoid this problem by removing dead operands
+                // before removing dead code.
+                MConstant *constant = MConstant::New(UndefinedValue());
+                block->insertBefore(*(block->begin()), constant);
+                uses = mrp->replaceOperand(uses, constant);
+            }
+
+            MResumePoint *mrp = ins->resumePoint();
+            if (!mrp)
+                continue;
+        }
+    }
+
+    return true;
+}
+
 // Instructions are useless if they are unused and have no side effects.
 // This pass eliminates useless instructions.
 // The graph itself is unchanged.
 bool
 ion::EliminateDeadCode(MIRGenerator *mir, MIRGraph &graph)
 {
     // Traverse in postorder so that we hit uses before definitions.
     // Traverse instruction list backwards for the same reason.
--- a/js/src/ion/IonAnalysis.h
+++ b/js/src/ion/IonAnalysis.h
@@ -21,16 +21,19 @@ class MIRGraph;
 
 bool
 SplitCriticalEdges(MIRGraph &graph);
 
 bool
 EliminatePhis(MIRGenerator *mir, MIRGraph &graph);
 
 bool
+EliminateDeadResumePointOperands(MIRGenerator *mir, MIRGraph &graph);
+
+bool
 EliminateDeadCode(MIRGenerator *mir, MIRGraph &graph);
 
 bool
 ApplyTypeInformation(MIRGenerator *mir, MIRGraph &graph);
 
 bool
 RenumberBlocks(MIRGraph &graph);
 
--- a/js/src/ion/IonBuilder.cpp
+++ b/js/src/ion/IonBuilder.cpp
@@ -4287,16 +4287,17 @@ bool
 IonBuilder::resume(MInstruction *ins, jsbytecode *pc, MResumePoint::Mode mode)
 {
     JS_ASSERT(ins->isEffectful());
 
     MResumePoint *resumePoint = MResumePoint::New(ins->block(), pc, callerResumePoint_, mode);
     if (!resumePoint)
         return false;
     ins->setResumePoint(resumePoint);
+    resumePoint->setInstruction(ins);
     return true;
 }
 
 bool
 IonBuilder::resumeAt(MInstruction *ins, jsbytecode *pc)
 {
     return resume(ins, pc, MResumePoint::ResumeAt);
 }
--- a/js/src/ion/MIR.cpp
+++ b/js/src/ion/MIR.cpp
@@ -1240,16 +1240,17 @@ MResumePoint::New(MBasicBlock *block, js
 }
 
 MResumePoint::MResumePoint(MBasicBlock *block, jsbytecode *pc, MResumePoint *caller,
                            Mode mode)
   : MNode(block),
     stackDepth_(block->stackDepth()),
     pc_(pc),
     caller_(caller),
+    instruction_(NULL),
     mode_(mode)
 {
 }
 
 bool
 MResumePoint::init(MBasicBlock *block)
 {
     operands_ = block->graph().allocate<MDefinition *>(stackDepth());
--- a/js/src/ion/MIR.h
+++ b/js/src/ion/MIR.h
@@ -5634,16 +5634,17 @@ class MResumePoint : public MNode
 
   private:
     friend class MBasicBlock;
 
     MDefinition **operands_;
     uint32 stackDepth_;
     jsbytecode *pc_;
     MResumePoint *caller_;
+    MInstruction *instruction_;
     Mode mode_;
 
     MResumePoint(MBasicBlock *block, jsbytecode *pc, MResumePoint *parent, Mode mode);
     bool init(MBasicBlock *state);
     void inherit(MBasicBlock *state);
 
   protected:
     // Overwrites an operand without updating its Uses.
@@ -5678,16 +5679,22 @@ class MResumePoint : public MNode
         caller_ = caller;
     }
     uint32 frameCount() const {
         uint32 count = 1;
         for (MResumePoint *it = caller_; it; it = it->caller_)
             count++;
         return count;
     }
+    MInstruction *instruction() {
+        return instruction_;
+    }
+    void setInstruction(MInstruction *ins) {
+        instruction_ = ins;
+    }
     Mode mode() const {
         return mode_;
     }
 };
 
 /*
  * Facade for a chain of MResumePoints that cross frame boundaries (due to
  * function inlining). Operands are ordered from oldest frame to newest.
--- a/js/src/jsinfer.cpp
+++ b/js/src/jsinfer.cpp
@@ -5603,16 +5603,23 @@ TypeScript::CheckBytecode(JSContext *cx,
     int defCount = GetDefCount(script, pc - script->code);
 
     for (int i = 0; i < defCount; i++) {
         const js::Value &val = sp[-defCount + i];
         TypeSet *types = analysis->pushedTypes(pc, i);
         if (IgnorePushed(pc, i))
             continue;
 
+        /*
+         * Ignore undefined values, these may have been inserted by Ion to
+         * substitute for dead values.
+         */
+        if (val.isUndefined())
+            continue;
+
         Type type = GetValueType(cx, val);
 
         if (!types->hasType(type)) {
             /* Display fine-grained debug information first */
             fprintf(stderr, "Missing type at #%u:%05u pushed %u: %s\n",
                     script->id(), unsigned(pc - script->code), i, TypeString(type));
             TypeFailure(cx, "Missing type pushed %u: %s", i, TypeString(type));
         }
--- a/js/src/jsinterp.cpp
+++ b/js/src/jsinterp.cpp
@@ -3018,17 +3018,17 @@ BEGIN_CASE(JSOP_NEWOBJECT)
     TypeScript::Monitor(cx, script, regs.pc, regs.sp[-1]);
 }
 END_CASE(JSOP_NEWOBJECT)
 
 BEGIN_CASE(JSOP_ENDINIT)
 {
     /* FIXME remove JSOP_ENDINIT bug 588522 */
     JS_ASSERT(regs.stackDepth() >= 1);
-    JS_ASSERT(regs.sp[-1].isObject());
+    JS_ASSERT(regs.sp[-1].isObject() || regs.sp[-1].isUndefined());
 }
 END_CASE(JSOP_ENDINIT)
 
 BEGIN_CASE(JSOP_INITPROP)
 {
     /* Load the property's initial value into rval. */
     JS_ASSERT(regs.stackDepth() >= 2);
     RootedValue &rval = rootValue0;