Remove lazy phi placement (bug 732862, r=sstangl).
authorDavid Anderson <danderson@mozilla.com>
Fri, 09 Mar 2012 13:44:51 -0800
changeset 89817 74080c02eedcf90b2820c3284c6b9a1103fd5179
parent 89816 3ab9cb07980d077b9c0e4c4f0425314dec431d1d
child 89818 d09133d1bdaeacd8b2fd86c59cc2bb83144d7ab7
push id703
push userdanderson@mozilla.com
push dateFri, 09 Mar 2012 21:48:08 +0000
reviewerssstangl
bugs732862
milestone13.0a1
Remove lazy phi placement (bug 732862, r=sstangl).
js/src/ion/Ion.cpp
js/src/ion/IonAnalysis.cpp
js/src/ion/IonAnalysis.h
js/src/ion/IonBuilder.cpp
js/src/ion/IonBuilder.h
js/src/ion/Lowering.cpp
js/src/ion/Lowering.h
js/src/ion/MIR.cpp
js/src/ion/MIR.h
js/src/ion/MIRGraph.cpp
js/src/ion/MIRGraph.h
js/src/ion/MOpcodes.h
js/src/jit-test/tests/ion/bug732862.js
--- a/js/src/ion/Ion.cpp
+++ b/js/src/ion/Ion.cpp
@@ -660,29 +660,25 @@ TestCompiler(IonBuilder &builder, MIRGra
     IonSpewPass("Reorder Blocks");
     AssertGraphCoherency(graph);
 
     if (!BuildDominatorTree(graph))
         return false;
     // No spew: graph not changed.
 
     // This must occur before any code elimination.
-    if (!EliminateDeadPhis(graph))
+    if (!EliminatePhis(graph))
         return false;
-    IonSpewPass("Eliminate dead phis");
+    IonSpewPass("Eliminate phis");
     AssertGraphCoherency(graph);
 
     if (!BuildPhiReverseMapping(graph))
         return false;
     // No spew: graph not changed.
 
-    EliminateCopies(graph);
-    IonSpewPass("Eliminate copies");
-    AssertGraphCoherency(graph);
-
     // This pass also removes copies.
     if (!ApplyTypeInformation(graph))
         return false;
     IonSpewPass("Apply types");
     AssertGraphCoherency(graph);
 
     // Alias analysis is required for LICM and GVN so that we don't move
     // loads across stores.
--- a/js/src/ion/IonAnalysis.cpp
+++ b/js/src/ion/IonAnalysis.cpp
@@ -106,30 +106,51 @@ IsPhiObservable(MPhi *phi)
     // points, then the SSA name is never consumed by the program.
     for (MUseDefIterator iter(phi); iter; iter++) {
         if (!iter.def()->isPhi())
             return true;
     }
     return false;
 }
 
+static inline MDefinition *
+IsPhiRedundant(MPhi *phi)
+{
+    MDefinition *first = phi->getOperand(0);
+
+    for (size_t i = 1; i < phi->numOperands(); i++) {
+        if (first != phi->getOperand(i))
+            return NULL;
+    }
+
+    return first;
+}
+
 bool
-ion::EliminateDeadPhis(MIRGraph &graph)
+ion::EliminatePhis(MIRGraph &graph)
 {
     Vector<MPhi *, 16, SystemAllocPolicy> worklist;
 
     // Add all observable phis to a worklist. We use the "in worklist" bit to
     // mean "this phi is live".
     for (PostorderIterator block = graph.poBegin(); block != graph.poEnd(); block++) {
-        for (MPhiIterator iter = block->phisBegin(); iter != block->phisEnd(); iter++) {
+        MPhiIterator iter = block->phisBegin();
+        while (iter != block->phisEnd()) {
+            // If the phi is redundant, remove it here.
+            if (MDefinition *redundant = IsPhiRedundant(*iter)) {
+                iter->replaceAllUsesWith(redundant);
+                iter = block->discardPhiAt(iter);
+                continue;
+            }
             if (IsPhiObservable(*iter)) {
                 iter->setInWorklist();
                 if (!worklist.append(*iter))
                     return false;
             }
+            iter++;
         }
     }
 
     // Iteratively mark all phis reacahble from live phis.
     while (!worklist.empty()) {
         MPhi *phi = worklist.popCopy();
 
         for (size_t i = 0; i < phi->numOperands(); i++) {
@@ -154,36 +175,16 @@ ion::EliminateDeadPhis(MIRGraph &graph)
                 iter = block->discardPhiAt(iter);
             }
         }
     }
 
     return true;
 }
 
-void
-ion::EliminateCopies(MIRGraph &graph)
-{
-    // The worklist is LIFO. We add items in postorder to get reverse-postorder
-    // removal.
-    for (ReversePostorderIterator block(graph.rpoBegin()); block != graph.rpoEnd(); block++) {
-        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->discardAt(iter);
-            } else {
-                iter++;
-            }
-        }
-    }
-}
-
 // The type analysis algorithm inserts conversions and box/unbox instructions
 // to make the IR graph well-typed for future passes.
 //
 // Phi adjustment: If a phi's inputs are all the same type, the phi is
 // specialized to return that type.
 //
 // Input adjustment: Each input is asked to apply conversion operations to its
 // inputs. This may include Box, Unbox, or other instruction-specific type
--- a/js/src/ion/IonAnalysis.h
+++ b/js/src/ion/IonAnalysis.h
@@ -51,20 +51,17 @@ namespace ion {
 
 class MIRGenerator;
 class MIRGraph;
 
 bool
 SplitCriticalEdges(MIRGenerator *gen, MIRGraph &graph);
 
 bool
-EliminateDeadPhis(MIRGraph &graph);
-
-void
-EliminateCopies(MIRGraph &graph);
+EliminatePhis(MIRGraph &graph);
 
 bool
 EliminateDeadCode(MIRGraph &graph);
 
 bool
 ApplyTypeInformation(MIRGraph &graph);
 
 bool
--- a/js/src/ion/IonBuilder.cpp
+++ b/js/src/ion/IonBuilder.cpp
@@ -1094,18 +1094,16 @@ IonBuilder::finishLoop(CFGState &state, 
 
     // Compute phis in the loop header and propagate them throughout the loop,
     // including the successor.
     if (!state.loop.entry->setBackedge(current))
         return ControlStatus_Error;
     if (successor)
         successor->inheritPhis(state.loop.entry);
 
-    fixPendingContinues(state.loop.entry);
-
     if (state.loop.breaks) {
         // Propagate phis placed in the header to individual break exit points.
         DeferredEdge *edge = state.loop.breaks;
         while (edge) {
             edge->block->inheritPhis(state.loop.entry);
             edge = edge->next;
         }
 
@@ -1129,70 +1127,16 @@ IonBuilder::finishLoop(CFGState &state, 
     // An infinite loop (for (;;) { }) will not have a successor.
     if (!current)
         return ControlStatus_Ended;
 
     pc = current->pc();
     return ControlStatus_Joined;
 }
 
-void
-IonBuilder::fixPendingContinues(MBasicBlock *header)
-{
-    // An edge case (bug 729902). We leave |continue| edges "dangling" in the
-    // control-flow graph. When we finish parsing a loop, all continues
-    // targeting that loop are linked to a catch-all join block, which becomes
-    // that loop's backedge.
-    //
-    // If a continue edge crosses a loop boundary, this mechanism is delayed.
-    // Consider:
-    //   
-    //   outer: for (;;) {
-    //      inner: for (;;) {
-    //         continue outer;
-    //      }
-    //   }
-    //
-    // In this case, the innermost loop will have a dangling edge. When we
-    // finish parsing the outer loop, we will insert an MGoto from edge->outer.
-    //
-    // The inner loop, via setBackEdge, could place a phi at its header, and
-    // replace all contained uses of its original value with that phi. This
-    // will even include resume points, meaning the dangling |continue| edge's
-    // entry state will correctly use that phi. However, this will *not* update
-    // the *stack state* of that edge. Thus, when we go to create the catch-all
-    // join block, we'll inherit the wrong value from that edge! The value will
-    // be stale, instead of the phi.
-    //
-    // As a fix for this, we iterate over slots in continue blocks and make
-    // sure to update them. Note that we are only concerned about |continue|
-    // edges eminating from this loop, targeting outer loops, so we skip
-    // continues targeting the current loop.
-
-    for (size_t i = 0; i < loops_.length() - 1; i++) {
-        CFGState &cfg = cfgStack_[loops_[i].cfgEntry];
-        for (DeferredEdge *edge = cfg.loop.continues; edge; edge = edge->next) {
-            // Edges are added to the head of the list as we parse control-flow,
-            // so if we see an id outside this loop body, we can shortcut out.
-            // We haven't yet parsed anything beyond this loop, so any blocks
-            // created after the header are part of this loop.
-            if (edge->block->id() < header->id())
-                break;
-
-            MBasicBlock *block = edge->block;
-            for (MPhiIterator iter = header->phisBegin(); iter != header->phisEnd(); iter++) {
-                // We should have replaced the initial mapping of this slot.
-                JS_ASSERT(block->getEntrySlot(iter->slot()) == *iter);
-
-                block->rewriteSlot(iter->slot(), *iter);
-            }
-        }
-    }
-}
-
 IonBuilder::ControlStatus
 IonBuilder::processDoWhileBodyEnd(CFGState &state)
 {
     if (!processDeferredContinues(state))
         return ControlStatus_Error;
 
     // No current means control flow cannot reach the condition, so this will
     // never loop.
--- a/js/src/ion/IonBuilder.h
+++ b/js/src/ion/IonBuilder.h
@@ -253,17 +253,16 @@ class IonBuilder : public MIRGenerator
 
     // Finishes loops that do not actually loop, containing only breaks or
     // returns.
     ControlStatus processBrokenLoop(CFGState &state);
 
     // Computes loop phis, places them in all successors of a loop, then
     // handles any pending breaks.
     ControlStatus finishLoop(CFGState &state, MBasicBlock *successor);
-    void fixPendingContinues(MBasicBlock *header);
 
     void assertValidLoopHeadOp(jsbytecode *pc);
 
     ControlStatus forLoop(JSOp op, jssrcnote *sn);
     ControlStatus whileOrForInLoop(JSOp op, jssrcnote *sn);
     ControlStatus doWhileLoop(JSOp op, jssrcnote *sn);
     ControlStatus tableSwitch(JSOp op, jssrcnote *sn);
 
--- a/js/src/ion/Lowering.cpp
+++ b/js/src/ion/Lowering.cpp
@@ -854,23 +854,16 @@ LIRGenerator::visitToString(MToString *i
         // Objects might be effectful. (see ToPrimitive)
         JS_NOT_REACHED("unexpected type");
         break;
     }
     return false;
 }
 
 bool
-LIRGenerator::visitCopy(MCopy *ins)
-{
-    JS_NOT_REACHED("unexpected copy");
-    return false;
-}
-
-bool
 LIRGenerator::visitRegExp(MRegExp *ins)
 {
     LRegExp *lir = new LRegExp();
     return defineVMReturn(lir, ins) && assignSafepoint(lir, ins);
 }
 
 bool
 LIRGenerator::visitLambda(MLambda *ins)
--- a/js/src/ion/Lowering.h
+++ b/js/src/ion/Lowering.h
@@ -142,17 +142,16 @@ class LIRGenerator : public LIRGenerator
     bool visitStart(MStart *start);
     bool visitOsrEntry(MOsrEntry *entry);
     bool visitOsrValue(MOsrValue *value);
     bool visitOsrScopeChain(MOsrScopeChain *object);
     bool visitToDouble(MToDouble *convert);
     bool visitToInt32(MToInt32 *convert);
     bool visitTruncateToInt32(MTruncateToInt32 *truncate);
     bool visitToString(MToString *convert);
-    bool visitCopy(MCopy *ins);
     bool visitRegExp(MRegExp *ins);
     bool visitLambda(MLambda *ins);
     bool visitLambdaJoinableForCall(MLambdaJoinableForCall *ins);
     bool visitLambdaJoinableForSet(MLambdaJoinableForSet *ins);
     bool visitImplicitThis(MImplicitThis *ins);
     bool visitSlots(MSlots *ins);
     bool visitElements(MElements *ins);
     bool visitFlatClosureUpvars(MFlatClosureUpvars *ins);
--- a/js/src/ion/MIR.cpp
+++ b/js/src/ion/MIR.cpp
@@ -357,41 +357,16 @@ MCall *
 MCall::New(size_t argc, bool construct)
 {
     MCall *ins = new MCall(construct);
     if (!ins->init(argc + NumNonArgumentOperands))
         return NULL;
     return ins;
 }
 
-MCopy *
-MCopy::New(MDefinition *ins)
-{
-    // Don't create nested copies.
-    if (ins->isCopy())
-        ins = ins->toCopy()->getOperand(0);
-
-    return new MCopy(ins);
-}
-
-HashNumber
-MCopy::valueHash() const
-{
-    return getOperand(0)->valueHash();
-}
-
-bool
-MCopy::congruentTo(MDefinition * const &ins) const
-{
-    if (!ins->isCopy())
-        return false;
-
-    return ins->toCopy()->getOperand(0) == getOperand(0);
-}
-
 MTest *
 MTest::New(MDefinition *ins, MBasicBlock *ifTrue, MBasicBlock *ifFalse)
 {
     return new MTest(ins, ifTrue, ifFalse);
 }
 
 MCompare *
 MCompare::New(MDefinition *left, MDefinition *right, JSOp op)
--- a/js/src/ion/MIR.h
+++ b/js/src/ion/MIR.h
@@ -1270,39 +1270,16 @@ class MCompare
   protected:
     bool congruentTo(MDefinition *const &ins) const {
         if (!MBinaryInstruction::congruentTo(ins))
             return false;
         return jsop() == ins->toCompare()->jsop();
     }
 };
 
-// Wraps an SSA name in a new SSA name. This is used for correctness while
-// constructing SSA, and is removed immediately after the initial SSA is built.
-class MCopy : public MUnaryInstruction
-{
-    MCopy(MDefinition *ins)
-      : MUnaryInstruction(ins)
-    {
-        setResultType(ins->type());
-    }
-
-  public:
-    INSTRUCTION_HEADER(Copy);
-    static MCopy *New(MDefinition *ins);
-
-    HashNumber valueHash() const;
-    bool congruentTo(MDefinition * const &ins) const;
-
-    AliasSet getAliasSet() const {
-        JS_NOT_REACHED("Unexpected MCopy after building SSA");
-        return AliasSet::None();
-    }
-};
-
 // Takes a typed value and returns an untyped value.
 class MBox : public MUnaryInstruction
 {
     MBox(MDefinition *ins)
       : MUnaryInstruction(ins)
     {
         setResultType(MIRType_Value);
         setMovable();
--- a/js/src/ion/MIRGraph.cpp
+++ b/js/src/ion/MIRGraph.cpp
@@ -159,17 +159,18 @@ MBasicBlock::copySlots(MBasicBlock *from
         slots_[i] = from->slots_[i];
 }
 
 bool
 MBasicBlock::inherit(MBasicBlock *pred)
 {
     if (pred) {
         stackPosition_ = pred->stackPosition_;
-        copySlots(pred);
+        if (kind_ != PENDING_LOOP_HEADER)
+            copySlots(pred);
     } else {
         uint32_t stackDepth = info().script()->analysis()->getCode(pc()).stackDepth;
         stackPosition_ = info().firstStackSlot() + stackDepth;
     }
 
     JS_ASSERT(info_.nslots() >= stackPosition_);
 
     // Propagate the caller resume point from the inherited block.
@@ -179,18 +180,29 @@ MBasicBlock::inherit(MBasicBlock *pred)
     entryResumePoint_ = new MResumePoint(this, pc(), callerResumePoint, MResumePoint::ResumeAt);
     if (!entryResumePoint_->init(this))
         return false;
 
     if (pred) {
         if (!predecessors_.append(pred))
             return false;
 
-        for (size_t i = 0; i < stackDepth(); i++)
-            entryResumePoint()->initOperand(i, getSlot(i));
+        if (kind_ == PENDING_LOOP_HEADER) {
+            for (size_t i = 0; i < stackDepth(); i++) {
+                MPhi *phi = MPhi::New(i);
+                if (!phi->addInput(pred->getSlot(i)))
+                    return NULL;
+                addPhi(phi);
+                setSlot(i, phi);
+                entryResumePoint()->initOperand(i, phi);
+            }
+        } else {
+            for (size_t i = 0; i < stackDepth(); i++)
+                entryResumePoint()->initOperand(i, getSlot(i));
+        }
     }
 
     return true;
 }
 
 bool
 MBasicBlock::inheritNonPredecessor(MBasicBlock *parent)
 {
@@ -202,161 +214,53 @@ MBasicBlock::inheritNonPredecessor(MBasi
         return false;
     return true;
 }
 
 MDefinition *
 MBasicBlock::getSlot(uint32 index)
 {
     JS_ASSERT(index < stackPosition_);
-    return slots_[index].def;
+    return slots_[index];
 }
 
 void
 MBasicBlock::initSlot(uint32 slot, MDefinition *ins)
 {
-    slots_[slot].set(ins);
+    slots_[slot] = ins;
     entryResumePoint()->initOperand(slot, ins);
 }
 
 void
 MBasicBlock::linkOsrValues(MStart *start)
 {
     JS_ASSERT(start->startType() == MStart::StartType_Osr);
 
     MResumePoint *res = start->resumePoint();
 
     for (uint32 i = 0; i < stackDepth(); i++) {
-        StackSlot &var = slots_[i];
-        if (!var.isCopy()) {
-            if (i == info().scopeChainSlot())
-                var.def->toOsrScopeChain()->setResumePoint(res);
-            else
-                var.def->toOsrValue()->setResumePoint(res);
-        }
+        MDefinition *def = slots_[i];
+        if (i == info().scopeChainSlot())
+            def->toOsrScopeChain()->setResumePoint(res);
+        else
+            def->toOsrValue()->setResumePoint(res);
     }
 }
 
 void
 MBasicBlock::setSlot(uint32 slot, MDefinition *ins)
 {
-    StackSlot &var = slots_[slot];
-
-    // If |var| is copied, we must fix any of its copies so that they point to
-    // a usable value.
-    if (var.isCopied()) {
-        // Find the lowest copy on the stack, to preserve the invariant that
-        // the copy list starts near the top of the stack and proceeds
-        // toward the bottom.
-        uint32 lowest = var.firstCopy;
-        uint32 prev = NotACopy;
-        do {
-            uint32 next = slots_[lowest].nextCopy;
-            if (next == NotACopy)
-                break;
-            JS_ASSERT(next < lowest);
-            prev = lowest;
-            lowest = next;
-        } while (true);
-
-        // Rewrite every copy.
-        for (uint32 copy = var.firstCopy; copy != lowest;) {
-            slots_[copy].copyOf = lowest;
-
-            uint32 next = slots_[copy].nextCopy;
-
-            // The node whose "nextCopy" field is |lowest| is now the
-            // terminator of the list.
-            if (slots_[copy].nextCopy == lowest)
-                slots_[copy].nextCopy = NotACopy;
-
-            copy = next;
-        }
-
-        // Make the lowest the new store.
-        slots_[lowest].copyOf = NotACopy;
-        slots_[lowest].firstCopy = prev;
-    } else if (var.isCopy()) {
-        uint32 prev = var.copyOf;
-        if (slots_[prev].firstCopy != slot) {
-            // Find the first entry in the list pointing to this entry.
-            prev = slots_[prev].firstCopy;
-            while (slots_[prev].nextCopy != slot) {
-                prev = slots_[prev].nextCopy;
-                JS_ASSERT(prev != NotACopy);
-            }
-            slots_[prev].nextCopy = var.nextCopy;
-        } else {
-            slots_[prev].firstCopy = var.nextCopy;
-        }
-    }
-
-    var.set(ins);
+    slots_[slot] = ins;
 }
 
-// We must avoid losing copies when inserting phis. For example, the code
-// on the left must not be naively rewritten as shown.
-//   t = 1           ||   0: const(#1)   ||   0: const(#1)
-//   i = t           \|   do {           \|   do {
-//   do {             ->    2: add(0, 0)  ->   1: phi(0, 1)
-//      i = i + t    /|                  /|    2: add(1, 1)
-//   } ...           ||   } ...          ||   } ...
-//
-// Which is not correct. To solve this, we create a new SSA name at the point
-// where |t| is assigned to |i|, like so:
-//   t = 1          ||   0: const(#1)    ||   0: const(#1)
-//   t' = copy(t)   ||   1: copy(0)      ||   1: copy(0)
-//   i = t'         \|   do {            \|   do {
-//   do {            ->    3: add(0, 1)   ->    2: phi(1, 3)
-//      i = i + t   /|   } ...           /|     3: add(0, 2)
-//   } ...          ||                   ||   } ...
-//                  ||                   ||
-//
-// We assume that the only way such copies can be created is via simple
-// assignment, like (x = y), which will be reflected in the bytecode via
-// a GET[LOCAL,ARG] that inherits into a SET[LOCAL,ARG]. Normal calls
-// to push() will be compiler-created temporaries. So to minimize creation of
-// new SSA names, we lazily create them when applying a setVariable() whose
-// stack top was pushed by a pushVariable(). That also means we do not create
-// "copies" for calls to push().
 void
 MBasicBlock::setVariable(uint32 index)
 {
     JS_ASSERT(stackPosition_ > info_.firstStackSlot());
-    StackSlot &top = slots_[stackPosition_ - 1];
-
-    MDefinition *def = top.def;
-    if (top.isCopy()) {
-        // Set the local variable to be a copy of |def|. Note that unlike
-        // JaegerMonkey, no complicated logic is needed to figure out how to
-        // make |top| a copy of |var|. There is no need, because we only care
-        // about (1) popping being fast, thus the backwarding ordering of
-        // copies, and (2) knowing when a GET flows into a SET.
-        MInstruction *ins = MCopy::New(def);
-        add(ins);
-        def = ins;
-    }
-
-    setSlot(index, def);
-
-    if (!top.isCopy()) {
-        // If the top is not a copy, we make it one anyway, in case the
-        // bytecode ever emits something like:
-        //    GETELEM
-        //    SETLOCAL 0
-        //    SETLOCAL 1
-        //
-        // In this case, we want the second assignment to act as though there
-        // was an intervening POP; GETLOCAL. Note that |def| is already
-        // correct, because we only created a new instruction if |top.isCopy()|
-        // was true.
-        top.copyOf = index;
-        top.nextCopy = slots_[index].firstCopy;
-        slots_[index].firstCopy = stackPosition_ - 1;
-    }
+    setSlot(index, slots_[stackPosition_ - 1]);
 }
 
 void
 MBasicBlock::setArg(uint32 arg)
 {
     // :TODO:  assert not closed
     setVariable(info_.argSlot(arg));
 }
@@ -379,37 +283,23 @@ MBasicBlock::rewriteSlot(uint32 slot, MD
 {
     setSlot(slot, ins);
 }
 
 void
 MBasicBlock::push(MDefinition *ins)
 {
     JS_ASSERT(stackPosition_ < info_.nslots());
-    slots_[stackPosition_].set(ins);
-    stackPosition_++;
+    slots_[stackPosition_++] = ins;
 }
 
 void
 MBasicBlock::pushVariable(uint32 slot)
 {
-    JS_ASSERT(slot < stackPosition_);
-    if (slots_[slot].isCopy())
-        slot = slots_[slot].copyOf;
-
-    JS_ASSERT(stackPosition_ < info_.nslots());
-    StackSlot &to = slots_[stackPosition_];
-    StackSlot &from = slots_[slot];
-
-    to.def = from.def;
-    to.copyOf = slot;
-    to.nextCopy = from.firstCopy;
-    from.firstCopy = stackPosition_;
-
-    stackPosition_++;
+    push(slots_[slot]);
 }
 
 void
 MBasicBlock::pushArg(uint32 arg)
 {
     // :TODO:  assert not closed
     pushVariable(info_.argSlot(arg));
 }
@@ -426,32 +316,17 @@ MBasicBlock::pushSlot(uint32 slot)
 {
     pushVariable(slot);
 }
 
 MDefinition *
 MBasicBlock::pop()
 {
     JS_ASSERT(stackPosition_ > info_.firstStackSlot());
-
-    StackSlot &slot = slots_[--stackPosition_];
-    if (slot.isCopy()) {
-        // The latest copy is at the top of the stack, and is the first copy
-        // in the linked list. We only remove copies from the head of the list.
-        StackSlot &backing = slots_[slot.copyOf];
-        JS_ASSERT(backing.isCopied());
-        JS_ASSERT(backing.firstCopy == stackPosition_);
-
-        backing.firstCopy = slot.nextCopy;
-    }
-
-    // The slot cannot have live copies if it is being removed.
-    JS_ASSERT(!slot.isCopied());
-
-    return slot.def;
+    return slots_[--stackPosition_];
 }
 
 void
 MBasicBlock::pick(int32 depth)
 {
     // pick take an element and move it to the top.
     // pick(-2):
     //   A B C D E
@@ -462,74 +337,19 @@ MBasicBlock::pick(int32 depth)
 }
 
 void
 MBasicBlock::swapAt(int32 depth)
 {
     uint32 lhsDepth = stackPosition_ + depth - 1;
     uint32 rhsDepth = stackPosition_ + depth;
 
-    JS_ASSERT(depth < 0);
-    JS_ASSERT(lhsDepth >= info_.firstStackSlot());
-
-    StackSlot &lhs = slots_[lhsDepth];
-    StackSlot &rhs = slots_[rhsDepth];
-
-    // Exit if the swap is a no-op.
-    if (rhs.isCopy()) {
-        if (rhs.copyOf == lhsDepth)
-            return;
-        if (lhs.isCopy() && rhs.copyOf == lhs.copyOf)
-            return;
-    }
-
-    // Update linked lists to new locations.
-    updateIndexes(lhs, lhsDepth, rhsDepth);
-    updateIndexes(rhs, rhsDepth, lhsDepth);
-
-    // Swap values.
-    StackSlot tmp = lhs;
-    lhs = rhs;
-    rhs = tmp;
-}
-
-void
-MBasicBlock::updateIndexes(StackSlot &elem, uint32 oldIdx, uint32 newIdx)
-{
-    // This implementation does not handle the case where the element need to
-    // change location in the chained list.
-    JS_ASSERT(oldIdx == newIdx + 1 || oldIdx == newIdx - 1);
-    JS_ASSERT(&elem == &slots_[oldIdx] || &elem == &slots_[newIdx]);
-    JS_ASSERT_IF(slots_[oldIdx].isCopy() || slots_[newIdx].isCopy(),
-                 slots_[oldIdx].copyOf != newIdx &&
-                 slots_[oldIdx].copyOf != slots_[newIdx].copyOf &&
-                 oldIdx != slots_[newIdx].copyOf);
-
-    if (elem.isCopy()) {
-        // We iterate since the beginning to find and update the element
-        // pointing to this one.
-        JS_ASSERT(slots_[elem.copyOf].isCopied());
-        if (slots_[elem.copyOf].firstCopy == oldIdx) {
-            slots_[elem.copyOf].firstCopy = newIdx;
-        } else {
-            uint32 copyIndex = slots_[elem.copyOf].firstCopy;
-            while (slots_[copyIndex].nextCopy != oldIdx)
-                copyIndex = slots_[copyIndex].nextCopy;
-            slots_[copyIndex].nextCopy = newIdx;
-        }
-    } else if (elem.isCopied()) {
-        // This element is copied, so we iterate over all copies to update the
-        // copyOf index.
-        uint32 copyIndex = elem.firstCopy;
-        while (copyIndex != NotACopy) {
-            JS_ASSERT(slots_[copyIndex].copyOf == oldIdx);
-            slots_[copyIndex].copyOf = newIdx;
-            copyIndex = slots_[copyIndex].nextCopy;
-        }
-    }
+    MDefinition *temp = slots_[lhsDepth];
+    slots_[lhsDepth] = slots_[rhsDepth];
+    slots_[rhsDepth] = temp;
 }
 
 MDefinition *
 MBasicBlock::peek(int32 depth)
 {
     JS_ASSERT(depth < 0);
     JS_ASSERT(stackPosition_ + depth >= info_.firstStackSlot());
     return getSlot(stackPosition_ + depth);
@@ -731,132 +551,50 @@ 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)
 {
     // Predecessors must be finished, and at the correct stack depth.
     JS_ASSERT(lastIns_);
     JS_ASSERT(pred->lastIns_);
     JS_ASSERT(pred->stackDepth() == entryResumePoint()->stackDepth());
 
     // We must be a pending loop header
     JS_ASSERT(kind_ == PENDING_LOOP_HEADER);
 
-    // Place minimal phi nodes by comparing the set of defintions at loop entry
-    // with the loop exit. For each mismatching slot, we create a phi node, and
-    // rewrite all uses of the entry definition to use the phi node instead.
-    //
-    // 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.
+    // Add exit definitions to each corresponding phi at the entry.
     for (uint32 i = 0; i < pred->stackDepth(); i++) {
-        MDefinition *entryDef = entryResumePoint()->getOperand(i);
-        MDefinition *exitDef = pred->slots_[i].def;
+        MPhi *entryDef = entryResumePoint()->getOperand(i)->toPhi();
+        MDefinition *exitDef = pred->slots_[i];
 
-        // If the entry def is a phi, it must not be a phi owned by this block,
-        // since a loop header can only have two entry points, and one already
-        // exists. This assert would trigger if we accidentally copy propagated,
-        // and two locals had the same def.
-        JS_ASSERT_IF(entryDef->isPhi(), entryDef->block() != this);
+        // Assert that we already placed phis for each slot.
+        JS_ASSERT(entryDef->block() == this);
 
-        // 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 (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(); ) {
-            JS_ASSERT(use->node()->getOperand(use->index()) == entryDef);
-
-            // Uses are initially sorted, with the head of the list being the
-            // most recently inserted. This ordering is maintained while
-            // placing phis.
-            if (use->node()->block()->id() < id()) {
-                assertUsesAreNotWithin(use, entryDef->usesEnd());
-                break;
-            }
-
-            // Replace the instruction's use with the phi. Note that |prev|
-            // does not change, and is really NULL since we always remove
-            // from the head of the list,
-            use = use->node()->replaceOperand(use, phi);
+        if (entryDef == exitDef) {
+            // If the exit def is the same as the entry def, make a redundant
+            // phi. Since loop headers have exactly two incoming edges, we
+            // know that that's just the first input.
+            //
+            // Note that we eliminate later rather than now, to avoid any
+            // weirdness around pending continue edges which might still hold
+            // onto phis.
+            exitDef = entryDef->getOperand(0);
         }
 
-#ifdef DEBUG
-        // Assert that no slot after this one has the same entryDef. This would
-        // imply that the SSA building process has accidentally allowed the
-        // same SSA name to occupy two slots. Note, this is actually allowed
-        // when the expression stack is non-empty, for example, (a + a) will
-        // push two stack slots with the same SSA name as |a|. However, at loop
-        // edges, the expression stack is empty, and thus we expect there to be
-        // no copies.
-        for (uint32 j = i + 1; j < pred->stackDepth(); j++)
-            JS_ASSERT(slots_[j].def != entryDef);
-#endif
-
-        if (!phi->addInput(entryDef) || !phi->addInput(exitDef))
+        if (!entryDef->addInput(exitDef))
             return false;
 
-        setSlot(i, phi);
+        setSlot(i, entryDef);
     }
 
     // We are now a loop header proper
     kind_ = LOOP_HEADER;
 
     return predecessors_.append(pred);
 }
 
@@ -927,17 +665,17 @@ MBasicBlock::inheritPhis(MBasicBlock *he
 void
 MBasicBlock::dumpStack(FILE *fp)
 {
 #ifdef DEBUG
     fprintf(fp, " %-3s %-16s %-6s %-10s\n", "#", "name", "copyOf", "first/next");
     fprintf(fp, "-------------------------------------------\n");
     for (uint32 i = 0; i < stackPosition_; i++) {
         fprintf(fp, " %-3d", i);
-        fprintf(fp, " %-16p %-6d %-10d\n", (void *)slots_[i].def, slots_[i].copyOf, slots_[i].firstCopy);
+        fprintf(fp, " %-16p\n", (void *)slots_[i]);
     }
 #endif
 }
 
 MTest *
 MBasicBlock::immediateDominatorBranch(BranchDirection *pdirection)
 {
     *pdirection = FALSE_BRANCH;
--- a/js/src/ion/MIRGraph.h
+++ b/js/src/ion/MIRGraph.h
@@ -65,41 +65,16 @@ class LBlock;
 
 enum BranchDirection {
     FALSE_BRANCH,
     TRUE_BRANCH
 };
 
 class MBasicBlock : public TempObject, public InlineListNode<MBasicBlock>
 {
-    static const uint32 NotACopy = uint32(-1);
-
-    struct StackSlot {
-        MDefinition *def;
-        uint32 copyOf;
-        union {
-            uint32 firstCopy; // copyOf == NotACopy: first copy in the linked list
-            uint32 nextCopy;  // copyOf != NotACopy: next copy in the linked list
-        };
-
-        void set(MDefinition *def) {
-            this->def = def;
-            copyOf = NotACopy;
-            firstCopy = NotACopy;
-        }
-        bool isCopy() const {
-            return copyOf != NotACopy;
-        }
-        bool isCopied() const {
-            if (isCopy())
-                return false;
-            return firstCopy != NotACopy;
-        }
-    };
-
   public:
     enum Kind {
         NORMAL,
         PENDING_LOOP_HEADER,
         LOOP_HEADER,
         SPLIT_EDGE
     };
 
@@ -115,21 +90,16 @@ class MBasicBlock : public TempObject, p
 
     // Pushes a copy of a local variable or argument.
     void pushVariable(uint32 slot);
 
     // Sets a variable slot to the top of the stack, correctly creating copies
     // as needed.
     void setVariable(uint32 slot);
 
-    // Update the index of the linked list of stack slot during swapAt
-    // operations.  The value must have been copied from the source to the
-    // destination before calling this function.
-    void updateIndexes(StackSlot &elem, uint32 oldIdx, uint32 newIdx);
-
   public:
     ///////////////////////////////////////////////////////
     ////////// BEGIN GRAPH BUILDING INSTRUCTIONS //////////
     ///////////////////////////////////////////////////////
 
     // Creates a new basic block for a MIR generator. If |pred| is not NULL,
     // its slots and stack depth are initialized from |pred|.
     static MBasicBlock *New(MIRGraph &graph, CompileInfo &info,
@@ -446,17 +416,17 @@ class MBasicBlock : public TempObject, p
 #endif
 
   private:
     MIRGraph &graph_;
     CompileInfo &info_; // Each block originates from a particular script.
     InlineList<MInstruction> instructions_;
     Vector<MBasicBlock *, 1, IonAllocPolicy> predecessors_;
     InlineForwardList<MPhi> phis_;
-    FixedList<StackSlot> slots_;
+    FixedList<MDefinition *> slots_;
     uint32 stackPosition_;
     MControlInstruction *lastIns_;
     jsbytecode *pc_;
     uint32 id_;
     LBlock *lir_;
     MStart *start_;
     MResumePoint *entryResumePoint_;
     MBasicBlock *successorWithPhis_;
--- a/js/src/ion/MOpcodes.h
+++ b/js/src/ion/MOpcodes.h
@@ -78,17 +78,16 @@ namespace ion {
     _(Mul)                                                                  \
     _(Div)                                                                  \
     _(Mod)                                                                  \
     _(Concat)                                                               \
     _(CharCodeAt)                                                           \
     _(FromCharCode)                                                         \
     _(Return)                                                               \
     _(Throw)                                                                \
-    _(Copy)                                                                 \
     _(Box)                                                                  \
     _(Unbox)                                                                \
     _(GuardObject)                                                          \
     _(ToDouble)                                                             \
     _(ToInt32)                                                              \
     _(TruncateToInt32)                                                      \
     _(ToString)                                                             \
     _(NewArray)                                                             \
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/ion/bug732862.js
@@ -0,0 +1,7 @@
+function testReallyDeepNestedExit() {
+    for (var i = 0; i < 5*4; i++) {}
+    for (var o = schedule = i = 9 ; i < 5; i++) {}
+}
+dis(testReallyDeepNestedExit);
+assertEq(testReallyDeepNestedExit(), undefined);
+