X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FStrongPHIElimination.cpp;h=bd7cb7520c985d341630a23e0c08760959a3e894;hb=31acb89c6545847435518f42825102aa30af9fd4;hp=399e61541843c7490790283c54b8130e732f64ea;hpb=a279a896ecd1601060adcc6563488f27b12319ef;p=oota-llvm.git

diff --git a/lib/CodeGen/StrongPHIElimination.cpp b/lib/CodeGen/StrongPHIElimination.cpp
index 399e6154184..bd7cb7520c9 100644
--- a/lib/CodeGen/StrongPHIElimination.cpp
+++ b/lib/CodeGen/StrongPHIElimination.cpp
@@ -32,18 +32,18 @@
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/Statistic.h"
-#include "llvm/Support/Compiler.h"
+#include "llvm/Support/Debug.h"
 using namespace llvm;
 
 namespace {
-  struct VISIBILITY_HIDDEN StrongPHIElimination : public MachineFunctionPass {
+  struct StrongPHIElimination : public MachineFunctionPass {
     static char ID; // Pass identification, replacement for typeid
-    StrongPHIElimination() : MachineFunctionPass((intptr_t)&ID) {}
+    StrongPHIElimination() : MachineFunctionPass(&ID) {}
 
     // Waiting stores, for each MBB, the set of copies that need to
     // be inserted into that MBB
     DenseMap<MachineBasicBlock*,
-             std::map<unsigned, unsigned> > Waiting;
+             std::multimap<unsigned, unsigned> > Waiting;
     
     // Stacks holds the renaming stack for each register
     std::map<unsigned, std::vector<unsigned> > Stacks;
@@ -70,7 +70,10 @@ namespace {
     bool runOnMachineFunction(MachineFunction &Fn);
     
     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+      AU.setPreservesCFG();
       AU.addRequired<MachineDominatorTree>();
+      AU.addRequired<SlotIndexes>();
+      AU.addPreserved<SlotIndexes>();
       AU.addRequired<LiveIntervals>();
       
       // TODO: Actually make this true.
@@ -139,10 +142,9 @@ namespace {
                          std::vector<StrongPHIElimination::DomForestNode*>& DF,
                          std::vector<std::pair<unsigned, unsigned> >& locals);
     void ScheduleCopies(MachineBasicBlock* MBB, std::set<unsigned>& pushed);
-    void InsertCopies(MachineBasicBlock* MBB,
+    void InsertCopies(MachineDomTreeNode* MBB,
                       SmallPtrSet<MachineBasicBlock*, 16>& v);
-    void mergeLiveIntervals(unsigned primary, unsigned secondary, 
-                            MachineBasicBlock* pred);
+    bool mergeLiveIntervals(unsigned primary, unsigned secondary);
   };
 }
 
@@ -294,8 +296,8 @@ StrongPHIElimination::computeDomForest(
 static bool isLiveIn(unsigned r, MachineBasicBlock* MBB,
                      LiveIntervals& LI) {
   LiveInterval& I = LI.getOrCreateInterval(r);
-  unsigned idx = LI.getMBBStartIdx(MBB);
-  return I.liveBeforeAndAt(idx);
+  SlotIndex idx = LI.getMBBStartIdx(MBB);
+  return I.liveAt(idx);
 }
 
 /// isLiveOut - help method that determines, from a regno, if a register is
@@ -303,10 +305,9 @@ static bool isLiveIn(unsigned r, MachineBasicBlock* MBB,
 static bool isLiveOut(unsigned r, MachineBasicBlock* MBB,
                       LiveIntervals& LI) {
   for (MachineBasicBlock::succ_iterator PI = MBB->succ_begin(),
-       E = MBB->succ_end(); PI != E; ++PI) {
+       E = MBB->succ_end(); PI != E; ++PI)
     if (isLiveIn(r, *PI, LI))
       return true;
-  }
   
   return false;
 }
@@ -420,7 +421,7 @@ void StrongPHIElimination::processBlock(MachineBasicBlock* MBB) {
   MachineBasicBlock::iterator P = MBB->begin();
   while (P != MBB->end() && P->getOpcode() == TargetInstrInfo::PHI) {
     unsigned DestReg = P->getOperand(0).getReg();
-
+    
     // Don't both doing PHI elimination for dead PHI's.
     if (P->registerDefIsDead(DestReg)) {
       ++P;
@@ -428,7 +429,7 @@ void StrongPHIElimination::processBlock(MachineBasicBlock* MBB) {
     }
 
     LiveInterval& PI = LI.getOrCreateInterval(DestReg);
-    unsigned pIdx = LI.getDefIndex(LI.getInstructionIndex(P));
+    SlotIndex pIdx = LI.getInstructionIndex(P).getDefIndex();
     VNInfo* PVN = PI.getLiveRangeContaining(pIdx)->valno;
     PhiValueNumber.insert(std::make_pair(DestReg, PVN->id));
 
@@ -442,6 +443,17 @@ void StrongPHIElimination::processBlock(MachineBasicBlock* MBB) {
     // Iterate over the operands of the PHI node
     for (int i = P->getNumOperands() - 1; i >= 2; i-=2) {
       unsigned SrcReg = P->getOperand(i-1).getReg();
+      
+      // Don't need to try to coalesce a register with itself.
+      if (SrcReg == DestReg) {
+        ProcessedNames.insert(SrcReg);
+        continue;
+      }
+      
+      // We don't need to insert copies for implicit_defs.
+      MachineInstr* DefMI = MRI.getVRegDef(SrcReg);
+      if (DefMI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF)
+        ProcessedNames.insert(SrcReg);
     
       // Check for trivial interferences via liveness information, allowing us
       // to avoid extra work later.  Any registers that interfere cannot both
@@ -541,6 +553,12 @@ void StrongPHIElimination::processBlock(MachineBasicBlock* MBB) {
     }
     
     // Add the renaming set for this PHI node to our overall renaming information
+    for (std::map<unsigned, MachineBasicBlock*>::iterator QI = PHIUnion.begin(),
+         QE = PHIUnion.end(); QI != QE; ++QI) {
+      DEBUG(dbgs() << "Adding Renaming: " << QI->first << " -> "
+                   << P->getOperand(0).getReg() << "\n");
+    }
+    
     RenameSets.insert(std::make_pair(P->getOperand(0).getReg(), PHIUnion));
     
     // Remember which registers are already renamed, so that we don't try to 
@@ -631,13 +649,13 @@ void StrongPHIElimination::processPHIUnion(MachineInstr* Inst,
 void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB,
                                           std::set<unsigned>& pushed) {
   // FIXME: This function needs to update LiveIntervals
-  std::map<unsigned, unsigned>& copy_set= Waiting[MBB];
+  std::multimap<unsigned, unsigned>& copy_set= Waiting[MBB];
   
-  std::map<unsigned, unsigned> worklist;
+  std::multimap<unsigned, unsigned> worklist;
   std::map<unsigned, unsigned> map;
   
   // Setup worklist of initial copies
-  for (std::map<unsigned, unsigned>::iterator I = copy_set.begin(),
+  for (std::multimap<unsigned, unsigned>::iterator I = copy_set.begin(),
        E = copy_set.end(); I != E; ) {
     map.insert(std::make_pair(I->first, I->first));
     map.insert(std::make_pair(I->second, I->second));
@@ -646,9 +664,9 @@ void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB,
       worklist.insert(*I);
       
       // Avoid iterator invalidation
-      unsigned first = I->first;
+      std::multimap<unsigned, unsigned>::iterator OI = I;
       ++I;
-      copy_set.erase(first);
+      copy_set.erase(OI);
     } else {
       ++I;
     }
@@ -664,8 +682,9 @@ void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB,
   // Iterate over the worklist, inserting copies
   while (!worklist.empty() || !copy_set.empty()) {
     while (!worklist.empty()) {
-      std::pair<unsigned, unsigned> curr = *worklist.begin();
-      worklist.erase(curr.first);
+      std::multimap<unsigned, unsigned>::iterator WI = worklist.begin();
+      std::pair<unsigned, unsigned> curr = *WI;
+      worklist.erase(WI);
       
       const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(curr.first);
       
@@ -679,17 +698,25 @@ void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB,
         TII->copyRegToReg(*PI->getParent(), PI, t,
                           curr.second, RC, RC);
         
+        DEBUG(dbgs() << "Inserted copy from " << curr.second << " to " << t
+                     << "\n");
+        
         // Push temporary on Stacks
         Stacks[curr.second].push_back(t);
         
         // Insert curr.second in pushed
         pushed.insert(curr.second);
+        
+        // Create a live interval for this temporary
+        InsertedPHIDests.push_back(std::make_pair(t, --PI));
       }
       
       // Insert copy from map[curr.first] to curr.second
       TII->copyRegToReg(*MBB, MBB->getFirstTerminator(), curr.second,
                         map[curr.first], RC, RC);
       map[curr.first] = curr.second;
+      DEBUG(dbgs() << "Inserted copy from " << curr.first << " to "
+                   << curr.second << "\n");
       
       // Push this copy onto InsertedPHICopies so we can
       // update LiveIntervals with it.
@@ -697,15 +724,16 @@ void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB,
       InsertedPHIDests.push_back(std::make_pair(curr.second, --MI));
       
       // If curr.first is a destination in copy_set...
-      for (std::map<unsigned, unsigned>::iterator I = copy_set.begin(),
+      for (std::multimap<unsigned, unsigned>::iterator I = copy_set.begin(),
            E = copy_set.end(); I != E; )
         if (curr.first == I->second) {
           std::pair<unsigned, unsigned> temp = *I;
+          worklist.insert(temp);
           
           // Avoid iterator invalidation
+          std::multimap<unsigned, unsigned>::iterator OI = I;
           ++I;
-          copy_set.erase(temp.first);
-          worklist.insert(temp);
+          copy_set.erase(OI);
           
           break;
         } else {
@@ -714,24 +742,38 @@ void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB,
     }
     
     if (!copy_set.empty()) {
-      std::pair<unsigned, unsigned> curr = *copy_set.begin();
-      copy_set.erase(curr.first);
-      
-      const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(curr.first);
+      std::multimap<unsigned, unsigned>::iterator CI = copy_set.begin();
+      std::pair<unsigned, unsigned> curr = *CI;
+      worklist.insert(curr);
+      copy_set.erase(CI);
       
-      // Insert a copy from dest to a new temporary t at the end of b
-      unsigned t = MF->getRegInfo().createVirtualRegister(RC);
-      TII->copyRegToReg(*MBB, MBB->getFirstTerminator(), t,
-                        curr.second, RC, RC);
-      map[curr.second] = t;
+      LiveInterval& I = LI.getInterval(curr.second);
+      MachineBasicBlock::iterator term = MBB->getFirstTerminator();
+      SlotIndex endIdx = SlotIndex();
+      if (term != MBB->end())
+        endIdx = LI.getInstructionIndex(term);
+      else
+        endIdx = LI.getMBBEndIdx(MBB);
       
-      worklist.insert(curr);
+      if (I.liveAt(endIdx)) {
+        const TargetRegisterClass *RC =
+                                       MF->getRegInfo().getRegClass(curr.first);
+        
+        // Insert a copy from dest to a new temporary t at the end of b
+        unsigned t = MF->getRegInfo().createVirtualRegister(RC);
+        TII->copyRegToReg(*MBB, MBB->getFirstTerminator(), t,
+                          curr.second, RC, RC);
+        map[curr.second] = t;
+        
+        MachineBasicBlock::iterator TI = MBB->getFirstTerminator();
+        InsertedPHIDests.push_back(std::make_pair(t, --TI));
+      }
     }
   }
   
   // Renumber the instructions so that we can perform the index computations
   // needed to create new live intervals.
-  LI.computeNumbering();
+  LI.renumber();
   
   // For copies that we inserted at the ends of predecessors, we construct
   // live intervals.  This is pretty easy, since we know that the destination
@@ -740,35 +782,72 @@ void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB,
   // PHI, we don't create multiple overlapping live intervals.
   std::set<unsigned> RegHandled;
   for (SmallVector<std::pair<unsigned, MachineInstr*>, 4>::iterator I =
-       InsertedPHIDests.begin(), E = InsertedPHIDests.end(); I != E; ++I)
-    if (RegHandled.insert(I->first).second)
-      LI.addLiveRangeToEndOfBlock(I->first, I->second);
+       InsertedPHIDests.begin(), E = InsertedPHIDests.end(); I != E; ++I) {
+    if (RegHandled.insert(I->first).second) {
+      LiveInterval& Int = LI.getOrCreateInterval(I->first);
+      SlotIndex instrIdx = LI.getInstructionIndex(I->second);
+      if (Int.liveAt(instrIdx.getDefIndex()))
+        Int.removeRange(instrIdx.getDefIndex(),
+                        LI.getMBBEndIdx(I->second->getParent()).getNextSlot(),
+                        true);
+      
+      LiveRange R = LI.addLiveRangeToEndOfBlock(I->first, I->second);
+      R.valno->setCopy(I->second);
+      R.valno->def = LI.getInstructionIndex(I->second).getDefIndex();
+    }
+  }
 }
 
 /// InsertCopies - insert copies into MBB and all of its successors
-void StrongPHIElimination::InsertCopies(MachineBasicBlock* MBB,
+void StrongPHIElimination::InsertCopies(MachineDomTreeNode* MDTN,
                                  SmallPtrSet<MachineBasicBlock*, 16>& visited) {
+  MachineBasicBlock* MBB = MDTN->getBlock();
   visited.insert(MBB);
   
   std::set<unsigned> pushed;
   
+  LiveIntervals& LI = getAnalysis<LiveIntervals>();
   // Rewrite register uses from Stacks
   for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
-      I != E; ++I)
+      I != E; ++I) {
+    if (I->getOpcode() == TargetInstrInfo::PHI)
+      continue;
+    
     for (unsigned i = 0; i < I->getNumOperands(); ++i)
-      if (I->getOperand(i).isRegister() &&
+      if (I->getOperand(i).isReg() &&
           Stacks[I->getOperand(i).getReg()].size()) {
+        // Remove the live range for the old vreg.
+        LiveInterval& OldInt = LI.getInterval(I->getOperand(i).getReg());
+        LiveInterval::iterator OldLR =
+          OldInt.FindLiveRangeContaining(LI.getInstructionIndex(I).getUseIndex());
+        if (OldLR != OldInt.end())
+          OldInt.removeRange(*OldLR, true);
+        
+        // Change the register
         I->getOperand(i).setReg(Stacks[I->getOperand(i).getReg()].back());
+        
+        // Add a live range for the new vreg
+        LiveInterval& Int = LI.getInterval(I->getOperand(i).getReg());
+        VNInfo* FirstVN = *Int.vni_begin();
+        FirstVN->setHasPHIKill(false);
+        if (I->getOperand(i).isKill())
+          FirstVN->addKill(LI.getInstructionIndex(I).getUseIndex());
+        
+        LiveRange LR (LI.getMBBStartIdx(I->getParent()),
+                      LI.getInstructionIndex(I).getUseIndex().getNextSlot(),
+                      FirstVN);
+        
+        Int.addRange(LR);
       }
+  }    
   
   // Schedule the copies for this block
   ScheduleCopies(MBB, pushed);
   
-  // Recur to our successors
-  for (GraphTraits<MachineBasicBlock*>::ChildIteratorType I = 
-       GraphTraits<MachineBasicBlock*>::child_begin(MBB), E =
-       GraphTraits<MachineBasicBlock*>::child_end(MBB); I != E; ++I)
-    if (!visited.count(*I))
+  // Recur down the dominator tree.
+  for (MachineDomTreeNode::iterator I = MDTN->begin(),
+       E = MDTN->end(); I != E; ++I)
+    if (!visited.count((*I)->getBlock()))
       InsertCopies(*I, visited);
   
   // As we exit this block, pop the names we pushed while processing it
@@ -777,30 +856,47 @@ void StrongPHIElimination::InsertCopies(MachineBasicBlock* MBB,
     Stacks[*I].pop_back();
 }
 
-void StrongPHIElimination::mergeLiveIntervals(unsigned primary,
-                                              unsigned secondary,
-                                              MachineBasicBlock* pred) {
+bool StrongPHIElimination::mergeLiveIntervals(unsigned primary,
+                                              unsigned secondary) {
   
   LiveIntervals& LI = getAnalysis<LiveIntervals>();
   LiveInterval& LHS = LI.getOrCreateInterval(primary);
   LiveInterval& RHS = LI.getOrCreateInterval(secondary);
   
-  LI.computeNumbering();
+  LI.renumber();
+  
+  DenseMap<VNInfo*, VNInfo*> VNMap;
+  for (LiveInterval::iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) {
+    LiveRange R = *I;
+ 
+    SlotIndex Start = R.start;
+    SlotIndex End = R.end;
+    if (LHS.getLiveRangeContaining(Start))
+      return false;
+    
+    if (LHS.getLiveRangeContaining(End))
+      return false;
+    
+    LiveInterval::iterator RI = std::upper_bound(LHS.begin(), LHS.end(), R);
+    if (RI != LHS.end() && RI->start < End)
+      return false;
+  }
   
-  const LiveRange* RangeMergingIn =
-                   RHS.getLiveRangeContaining(LI.getMBBEndIdx(pred));
-  VNInfo* NewVN = LHS.getNextValue(RangeMergingIn->valno->def,
-                                   RangeMergingIn->valno->copy,
-                                   LI.getVNInfoAllocator());
-  NewVN->hasPHIKill = true;
-  LiveRange NewRange(RangeMergingIn->start, RangeMergingIn->end, NewVN);
+  for (LiveInterval::iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) {
+    LiveRange R = *I;
+    VNInfo* OldVN = R.valno;
+    VNInfo*& NewVN = VNMap[OldVN];
+    if (!NewVN) {
+      NewVN = LHS.createValueCopy(OldVN, LI.getVNInfoAllocator());
+    }
+    
+    LiveRange LR (R.start, R.end, NewVN);
+    LHS.addRange(LR);
+  }
   
-  if (RHS.containsOneValue())
-    LI.removeInterval(RHS.reg);
-  else
-    RHS.removeRange(RangeMergingIn->start, RangeMergingIn->end, true);
+  LI.removeInterval(RHS.reg);
   
-  LHS.addRange(NewRange);
+  return true;
 }
 
 bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) {
@@ -815,24 +911,86 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) {
         I->begin()->getOpcode() == TargetInstrInfo::PHI)
       processBlock(I);
   
+  // Break interferences where two different phis want to coalesce
+  // in the same register.
+  std::set<unsigned> seen;
+  typedef std::map<unsigned, std::map<unsigned, MachineBasicBlock*> >
+          RenameSetType;
+  for (RenameSetType::iterator I = RenameSets.begin(), E = RenameSets.end();
+       I != E; ++I) {
+    for (std::map<unsigned, MachineBasicBlock*>::iterator
+         OI = I->second.begin(), OE = I->second.end(); OI != OE; ) {
+      if (!seen.count(OI->first)) {
+        seen.insert(OI->first);
+        ++OI;
+      } else {
+        Waiting[OI->second].insert(std::make_pair(OI->first, I->first));
+        unsigned reg = OI->first;
+        ++OI;
+        I->second.erase(reg);
+        DEBUG(dbgs() << "Removing Renaming: " << reg << " -> " << I->first
+                     << "\n");
+      }
+    }
+  }
+  
   // Insert copies
   // FIXME: This process should probably preserve LiveIntervals
   SmallPtrSet<MachineBasicBlock*, 16> visited;
-  InsertCopies(Fn.begin(), visited);
+  MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>();
+  InsertCopies(MDT.getRootNode(), visited);
   
   // Perform renaming
-  typedef std::map<unsigned, std::map<unsigned, MachineBasicBlock*> >
-          RenameSetType;
   for (RenameSetType::iterator I = RenameSets.begin(), E = RenameSets.end();
        I != E; ++I)
-    for (std::map<unsigned, MachineBasicBlock*>::iterator SI = 
-         I->second.begin(), SE = I->second.end(); SI != SE; ++SI) {
-      mergeLiveIntervals(I->first, SI->first, SI->second);
-      Fn.getRegInfo().replaceRegWith(SI->first, I->first);
+    while (I->second.size()) {
+      std::map<unsigned, MachineBasicBlock*>::iterator SI = I->second.begin();
+      
+      DEBUG(dbgs() << "Renaming: " << SI->first << " -> " << I->first << "\n");
+      
+      if (SI->first != I->first) {
+        if (mergeLiveIntervals(I->first, SI->first)) {
+          Fn.getRegInfo().replaceRegWith(SI->first, I->first);
+      
+          if (RenameSets.count(SI->first)) {
+            I->second.insert(RenameSets[SI->first].begin(),
+                             RenameSets[SI->first].end());
+            RenameSets.erase(SI->first);
+          }
+        } else {
+          // Insert a last-minute copy if a conflict was detected.
+          const TargetInstrInfo *TII = Fn.getTarget().getInstrInfo();
+          const TargetRegisterClass *RC = Fn.getRegInfo().getRegClass(I->first);
+          TII->copyRegToReg(*SI->second, SI->second->getFirstTerminator(),
+                            I->first, SI->first, RC, RC);
+          
+          LI.renumber();
+          
+          LiveInterval& Int = LI.getOrCreateInterval(I->first);
+          SlotIndex instrIdx =
+                     LI.getInstructionIndex(--SI->second->getFirstTerminator());
+          if (Int.liveAt(instrIdx.getDefIndex()))
+            Int.removeRange(instrIdx.getDefIndex(),
+                            LI.getMBBEndIdx(SI->second).getNextSlot(), true);
+
+          LiveRange R = LI.addLiveRangeToEndOfBlock(I->first,
+                                            --SI->second->getFirstTerminator());
+          R.valno->setCopy(--SI->second->getFirstTerminator());
+          R.valno->def = instrIdx.getDefIndex();
+          
+          DEBUG(dbgs() << "Renaming failed: " << SI->first << " -> "
+                       << I->first << "\n");
+        }
+      }
+      
+      LiveInterval& Int = LI.getOrCreateInterval(I->first);
+      const LiveRange* LR =
+                       Int.getLiveRangeContaining(LI.getMBBEndIdx(SI->second));
+      LR->valno->setHasPHIKill(true);
+      
+      I->second.erase(SI->first);
     }
   
-  // FIXME: Insert last-minute copies
-  
   // Remove PHIs
   std::vector<MachineInstr*> phis;
   for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) {
@@ -846,19 +1004,6 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) {
        I != E; ) {
     MachineInstr* PInstr = *(I++);
     
-    // Trim live intervals of input registers.  They are no longer live into
-    // this block.
-    for (unsigned i = 1; i < PInstr->getNumOperands(); i += 2) {
-      unsigned reg = PInstr->getOperand(i).getReg();
-      MachineBasicBlock* MBB = PInstr->getOperand(i+1).getMBB();
-      LiveInterval& InputI = LI.getInterval(reg);
-      if (MBB != PInstr->getParent() &&
-          InputI.liveAt(LI.getMBBStartIdx(PInstr->getParent())))
-        InputI.removeRange(LI.getMBBStartIdx(PInstr->getParent()),
-                           LI.getInstructionIndex(PInstr),
-                           true);
-    }
-    
     // If this is a dead PHI node, then remove it from LiveIntervals.
     unsigned DestReg = PInstr->getOperand(0).getReg();
     LiveInterval& PI = LI.getInterval(DestReg);
@@ -866,15 +1011,31 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) {
       if (PI.containsOneValue()) {
         LI.removeInterval(DestReg);
       } else {
-        unsigned idx = LI.getDefIndex(LI.getInstructionIndex(PInstr));
+        SlotIndex idx = LI.getInstructionIndex(PInstr).getDefIndex();
         PI.removeRange(*PI.getLiveRangeContaining(idx), true);
       }
     } else {
+      // Trim live intervals of input registers.  They are no longer live into
+      // this block if they died after the PHI.  If they lived after it, don't
+      // trim them because they might have other legitimate uses.
+      for (unsigned i = 1; i < PInstr->getNumOperands(); i += 2) {
+        unsigned reg = PInstr->getOperand(i).getReg();
+        
+        MachineBasicBlock* MBB = PInstr->getOperand(i+1).getMBB();
+        LiveInterval& InputI = LI.getInterval(reg);
+        if (MBB != PInstr->getParent() &&
+            InputI.liveAt(LI.getMBBStartIdx(PInstr->getParent())) &&
+            InputI.expiredAt(LI.getInstructionIndex(PInstr).getNextIndex()))
+          InputI.removeRange(LI.getMBBStartIdx(PInstr->getParent()),
+                             LI.getInstructionIndex(PInstr),
+                             true);
+      }
+      
       // If the PHI is not dead, then the valno defined by the PHI
       // now has an unknown def.
-      unsigned idx = LI.getDefIndex(LI.getInstructionIndex(PInstr));
+      SlotIndex idx = LI.getInstructionIndex(PInstr).getDefIndex();
       const LiveRange* PLR = PI.getLiveRangeContaining(idx);
-      PLR->valno->def = ~0U;
+      PLR->valno->setIsPHIDef(true);
       LiveRange R (LI.getMBBStartIdx(PInstr->getParent()),
                    PLR->start, PLR->valno);
       PI.addRange(R);
@@ -884,7 +1045,7 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) {
     PInstr->eraseFromParent();
   }
   
-  LI.computeNumbering();
+  LI.renumber();
   
   return true;
 }