don't generate unecessary phi instructions (Bug 676151, r=dvander)
authorRyan Pearl <rpearl@mozilla.com>
Tue, 02 Aug 2011 17:49:22 -0700
changeset 74702 a459db11a653415c72368a2117227fb51aa0f3b1
parent 74701 2605bce381ef88f760862a72d7cecc18450496a7
child 74772 7c85629e7f73afa21cfc47df3de2ef476c42028a
push id64
push userrpearl@mozilla.com
push dateThu, 04 Aug 2011 19:21:22 +0000
reviewersdvander
bugs676151
milestone8.0a1
don't generate unecessary phi instructions (Bug 676151, r=dvander)
js/src/ion/IonAnalysis.cpp
js/src/ion/MIRGraph.cpp
--- a/js/src/ion/IonAnalysis.cpp
+++ b/js/src/ion/IonAnalysis.cpp
@@ -96,16 +96,17 @@ class TypeAnalyzer
 
     bool buildWorklist();
     bool reflow(MDefinition *def);
     bool despecializePhi(MPhi *phi);
     bool specializePhi(MPhi *phi);
     bool specializePhis();
     bool specializeInstructions();
     bool determineSpecializations();
+    void replaceRedundantPhi(MPhi *phi);
     bool insertConversions();
     bool adjustPhiInputs(MPhi *phi);
     bool adjustInputs(MDefinition *def);
     bool adjustOutput(MDefinition *def);
 
   public:
     TypeAnalyzer(MIRGraph &graph)
       : graph(graph)
@@ -115,23 +116,23 @@ class TypeAnalyzer
 };
 
 bool
 TypeAnalyzer::buildWorklist()
 {
     // The worklist is LIFO. We add items in postorder to get reverse-postorder
     // removal.
     for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); block++) {
-        MDefinitionIterator iter(*block);
-        while (iter) {
+        MInstructionIterator iter = block->begin();
+        while (iter != block->end()) {
             if (iter->isCopy()) {
                 // Remove copies here.
                 MCopy *copy = iter->toCopy();
                 copy->replaceAllUsesWith(copy->getOperand(0));
-                iter = block->removeDefAt(iter);
+                iter = block->removeAt(iter);
                 continue;
             }
             if (!push(*iter))
                 return false;
             iter++;
         }
     }
     return true;
@@ -341,28 +342,45 @@ TypeAnalyzer::adjustInputs(MDefinition *
     // The adjustOutput pass of our inputs' defs may not have have been
     // satisfactory, so double check now, inserting conversions as necessary.
     TypePolicy *policy = def->typePolicy();
     if (policy && !policy->adjustInputs(def->toInstruction()))
         return false;
     return true;
 }
 
+void
+TypeAnalyzer::replaceRedundantPhi(MPhi *phi)
+{
+    MBasicBlock *block = phi->block();
+    js::Value v = (phi->type() == MIRType_Undefined) ? UndefinedValue() : NullValue();
+    MConstant *c = MConstant::New(v);
+    // The instruction pass will insert the box
+    block->insertBefore(*(block->begin()), c);
+    phi->replaceAllUsesWith(c);
+}
+
 bool
 TypeAnalyzer::insertConversions()
 {
     // Instructions are processed in reverse postorder: all uses are defs are
     // seen before uses. This ensures that output adjustment (which may rewrite
     // inputs of uses) does not conflict with input adjustment.
     for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); block++) {
-        for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd(); phi++) {
-            if (!adjustPhiInputs(*phi))
-                return false;
-            if (phi->type() == MIRType_Value && !adjustOutput(*phi))
-                return false;
+        for (MPhiIterator phi(block->phisBegin()); phi != block->phisEnd();) {
+            if (phi->type() <= MIRType_Null) {
+                replaceRedundantPhi(*phi);
+                phi = block->removePhiAt(phi);
+            } else {
+                if (!adjustPhiInputs(*phi))
+                    return false;
+                if (phi->type() == MIRType_Value && !adjustOutput(*phi))
+                    return false;
+                phi++;
+            }
         }
         for (MInstructionIterator iter(block->begin()); iter != block->end(); iter++) {
             if (!adjustInputs(*iter))
                 return false;
             if (iter->type() == MIRType_Value && !adjustOutput(*iter))
                 return false;
         }
     }
--- a/js/src/ion/MIRGraph.cpp
+++ b/js/src/ion/MIRGraph.cpp
@@ -497,16 +497,24 @@ MBasicBlock::assertUsesAreNotWithin(MUse
 #ifdef DEBUG
     for (; use != end; use++) {
         JS_ASSERT_IF(use->node()->isDefinition(),
                      use->node()->toDefinition()->block()->id() < id());
     }
 #endif
 }
 
+static inline MDefinition *
+FollowCopy(MDefinition *def)
+{
+    MDefinition *ret = def->isCopy() ? def->getOperand(0) : def;
+    JS_ASSERT(!ret->isCopy());
+    return ret;
+}
+
 bool
 MBasicBlock::setBackedge(MBasicBlock *pred, MBasicBlock *successor)
 {
     // Predecessors must be finished, and at the correct stack depth.
     JS_ASSERT(lastIns_);
     JS_ASSERT(pred->lastIns_);
     JS_ASSERT(pred->stackPosition_ == stackPosition_);
     JS_ASSERT(entrySnapshot()->stackDepth() == stackPosition_);
@@ -520,19 +528,57 @@ MBasicBlock::setBackedge(MBasicBlock *pr
     //
     // This algorithm would break in the face of copies, so we take care to
     // give every assignment its own unique SSA name. See
     // MBasicBlock::setVariable for more information.
     for (uint32 i = 0; i < stackPosition_; i++) {
         MDefinition *entryDef = entrySnapshot()->getOperand(i);
         MDefinition *exitDef = pred->slots_[i].def;
 
+        // So long as we make sure that local variables are distinct SSA names,
+        // and generate a unique copy for each assignment until copy
+        // propagation occurs after SSA building is complete, then we need not
+        // insert phis if the entry definition is just a copy of the exit
+        // definition.
+        //
+        // If at any point, we perform an operation on a local variable that is
+        // NOT just a copy (say, we perform an add), then the exit definition
+        // will differ and we will insert the phi as necessary.
+        //
+        // Essentially, we are capturing the fact that copy propagation WILL
+        // occur, so that there will be no modifying operations in the loop,
+        // and we will not need to insert a phi to merge a back edge. So,
+        // inserting a phi is not necessary.
+        //
+        // Consider:
+        //   i = 1          ||   0: const(#1)    ||   0: const(#1)
+        //                  ||   1: copy(0)      ||   1: copy(0)
+        //   t = i          \|   do {            \|   do {
+        //   do {            ->    3: copy(0)     ->    2: phi(0, 3)
+        //      i = t       /|   } ...           /|     3: copy(2)
+        //   } ...          ||                   ||   } ...
+        //                  ||                   ||
+        //
+        // Note that the inserted phi is unecessary. After copy propagation
+        // occurs, we will have:
+        // 0: const(#1)     ||   0: const(#1)
+        // 1: copy(0)       ||   [eliminated copy]
+        // do {             \|   do {
+        //   2: phi(0, 3)    ->     2: phi(0, 2)
+        //   3: copy(2)     /|   }
+        // } ...            ||   4 : op(2, ...)
+        // 4 : op(3, ...)   ||
+        //
+        // So, the phi joins two definitions which are actually the same, and
+        // there was no reason to insert it to begin with.
+
+
         // If the entry definition and exit definition do not differ, then
         // no phi placement is necessary.
-        if (entryDef == exitDef)
+        if (FollowCopy(entryDef) == FollowCopy(exitDef))
             continue;
 
         // Create a new phi. Do not add inputs yet, as we don't want to
         // accidentally rewrite the phi's operands.
         MPhi *phi = MPhi::New(i);
         addPhi(phi);
 
         for (MUseIterator use(entryDef->usesBegin()); use != entryDef->usesEnd(); ) {