X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FStrongPHIElimination.cpp;h=0fabd8e6eef9e4c606a05171aa583ee818894114;hb=fd9c4f76f4a1ec06891a3405198fc907f8253958;hp=f84fdbe5bc2c45990319825903d7f6018eb76e4e;hpb=92f0fcb6df128ab99a63986b5be00e80fc9f98c6;p=oota-llvm.git

diff --git a/lib/CodeGen/StrongPHIElimination.cpp b/lib/CodeGen/StrongPHIElimination.cpp
index f84fdbe5bc2..0fabd8e6eef 100644
--- a/lib/CodeGen/StrongPHIElimination.cpp
+++ b/lib/CodeGen/StrongPHIElimination.cpp
@@ -47,6 +47,8 @@
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/Statistic.h"
 #include "llvm/Support/Debug.h"
 using namespace llvm;
 
@@ -79,7 +81,7 @@ namespace {
       };
       Node(unsigned v) : value(v), rank(0) { parent.setPointer(this); }
 
-      Node* getLeader();
+      Node *getLeader();
 
       PointerIntPair<Node*, 2> parent;
       unsigned value;
@@ -89,7 +91,15 @@ namespace {
     /// Add a register in a new congruence class containing only itself.
     void addReg(unsigned);
 
-    /// Join the congruence classes of two registers.
+    /// Join the congruence classes of two registers. This function is biased
+    /// towards the left argument, i.e. after
+    ///
+    /// addReg(r2);
+    /// unionRegs(r1, r2);
+    ///
+    /// the leader of the unioned congruence class is the same as the leader of
+    /// r1's congruence class prior to the union. This is actually relied upon
+    /// in the copy insertion code.
     void unionRegs(unsigned, unsigned);
 
     /// Get the color of a register. The color is 0 if the register has been
@@ -107,8 +117,6 @@ namespace {
     /// Isolate a PHI.
     void isolatePHI(MachineInstr*);
 
-    void PartitionRegisters(MachineFunction& MF);
-
     /// Traverses a basic block, splitting any interferences found between
     /// registers in the same congruence class. It takes two DenseMaps as
     /// arguments that it also updates: CurrentDominatingParent, which maps
@@ -121,8 +129,8 @@ namespace {
     /// of the dominator tree.
     void SplitInterferencesForBasicBlock(
       MachineBasicBlock&,
-      DenseMap<unsigned, unsigned>& CurrentDominatingParent,
-      DenseMap<unsigned, unsigned>& ImmediateDominatingParent);
+      DenseMap<unsigned, unsigned> &CurrentDominatingParent,
+      DenseMap<unsigned, unsigned> &ImmediateDominatingParent);
 
     // Lowers a PHI instruction, inserting copies of the source and destination
     // registers as necessary.
@@ -133,15 +141,23 @@ namespace {
     // overlapping lifetimes.
     void MergeLIsAndRename(unsigned Reg, unsigned NewReg);
 
-    MachineRegisterInfo* MRI;
-    const TargetInstrInfo* TII;
-    MachineDominatorTree* DT;
-    LiveIntervals* LI;
+    MachineRegisterInfo *MRI;
+    const TargetInstrInfo *TII;
+    MachineDominatorTree *DT;
+    LiveIntervals *LI;
 
     BumpPtrAllocator Allocator;
 
     DenseMap<unsigned, Node*> RegNodeMap;
 
+    // Maps a basic block to a list of its defs of registers that appear as PHI
+    // sources.
+    DenseMap<MachineBasicBlock*, std::vector<MachineInstr*> > PHISrcDefs;
+
+    // Maps a color to a pair of a MachineInstr* and a virtual register, which
+    // is the operand of that PHI corresponding to the current basic block.
+    DenseMap<unsigned, std::pair<MachineInstr*, unsigned> > CurrentPHIForColor;
+
     // FIXME: Can these two data structures be combined? Would a std::multimap
     // be any better?
 
@@ -161,8 +177,22 @@ namespace {
     typedef DenseMap<unsigned, MachineInstr*> DestCopyMap;
     DestCopyMap InsertedDestCopies;
   };
+
+  struct MIIndexCompare {
+    MIIndexCompare(LiveIntervals *LiveIntervals) : LI(LiveIntervals) { }
+
+    bool operator()(const MachineInstr *LHS, const MachineInstr *RHS) const {
+      return LI->getInstructionIndex(LHS) < LI->getInstructionIndex(RHS);
+    }
+
+    LiveIntervals *LI;
+  };
 } // namespace
 
+STATISTIC(NumPHIsLowered, "Number of PHIs lowered");
+STATISTIC(NumDestCopiesInserted, "Number of destination copies inserted");
+STATISTIC(NumSrcCopiesInserted, "Number of source copies inserted");
+
 char StrongPHIElimination::ID = 0;
 INITIALIZE_PASS_BEGIN(StrongPHIElimination, "strong-phi-node-elimination",
   "Eliminate PHI nodes for register allocation, intelligently", false, false)
@@ -174,7 +204,7 @@ INITIALIZE_PASS_END(StrongPHIElimination, "strong-phi-node-elimination",
 
 char &llvm::StrongPHIEliminationID = StrongPHIElimination::ID;
 
-void StrongPHIElimination::getAnalysisUsage(AnalysisUsage& AU) const {
+void StrongPHIElimination::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesCFG();
   AU.addRequired<MachineDominatorTree>();
   AU.addRequired<SlotIndexes>();
@@ -184,16 +214,16 @@ void StrongPHIElimination::getAnalysisUsage(AnalysisUsage& AU) const {
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
-static MachineOperand* findLastUse(MachineBasicBlock* MBB, unsigned Reg) {
+static MachineOperand *findLastUse(MachineBasicBlock *MBB, unsigned Reg) {
   // FIXME: This only needs to check from the first terminator, as only the
   // first terminator can use a virtual register.
   for (MachineBasicBlock::reverse_iterator RI = MBB->rbegin(); ; ++RI) {
     assert (RI != MBB->rend());
-    MachineInstr* MI = &*RI;
+    MachineInstr *MI = &*RI;
 
     for (MachineInstr::mop_iterator OI = MI->operands_begin(),
          OE = MI->operands_end(); OI != OE; ++OI) {
-      MachineOperand& MO = *OI;
+      MachineOperand &MO = *OI;
       if (MO.isReg() && MO.isUse() && MO.getReg() == Reg)
         return &MO;
     }
@@ -201,13 +231,32 @@ static MachineOperand* findLastUse(MachineBasicBlock* MBB, unsigned Reg) {
   return NULL;
 }
 
-bool StrongPHIElimination::runOnMachineFunction(MachineFunction& MF) {
+bool StrongPHIElimination::runOnMachineFunction(MachineFunction &MF) {
   MRI = &MF.getRegInfo();
   TII = MF.getTarget().getInstrInfo();
   DT = &getAnalysis<MachineDominatorTree>();
   LI = &getAnalysis<LiveIntervals>();
 
-  PartitionRegisters(MF);
+  for (MachineFunction::iterator I = MF.begin(), E = MF.end();
+       I != E; ++I) {
+    for (MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
+         BBI != BBE && BBI->isPHI(); ++BBI) {
+      unsigned DestReg = BBI->getOperand(0).getReg();
+      addReg(DestReg);
+      PHISrcDefs[I].push_back(BBI);
+
+      for (unsigned i = 1; i < BBI->getNumOperands(); i += 2) {
+        MachineOperand &SrcMO = BBI->getOperand(i);
+        unsigned SrcReg = SrcMO.getReg();
+        addReg(SrcReg);
+        unionRegs(DestReg, SrcReg);
+
+        MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
+        if (DefMI)
+          PHISrcDefs[DefMI->getParent()].push_back(DefMI);
+      }
+    }
+  }
 
   // Perform a depth-first traversal of the dominator tree, splitting
   // interferences amongst PHI-congruence classes.
@@ -232,7 +281,20 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction& MF) {
   // FIXME: Preserve the equivalence classes during copy insertion and use
   // the preversed equivalence classes instead of recomputing them.
   RegNodeMap.clear();
-  PartitionRegisters(MF);
+  for (MachineFunction::iterator I = MF.begin(), E = MF.end();
+       I != E; ++I) {
+    for (MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
+         BBI != BBE && BBI->isPHI(); ++BBI) {
+      unsigned DestReg = BBI->getOperand(0).getReg();
+      addReg(DestReg);
+
+      for (unsigned i = 1; i < BBI->getNumOperands(); i += 2) {
+        unsigned SrcReg = BBI->getOperand(i).getReg();
+        addReg(SrcReg);
+        unionRegs(DestReg, SrcReg);
+      }
+    }
+  }
 
   DenseMap<unsigned, unsigned> RegRenamingMap;
   bool Changed = false;
@@ -240,7 +302,7 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction& MF) {
        I != E; ++I) {
     MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
     while (BBI != BBE && BBI->isPHI()) {
-      MachineInstr* PHI = BBI;
+      MachineInstr *PHI = BBI;
 
       assert(PHI->getNumOperands() > 0);
 
@@ -280,15 +342,17 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction& MF) {
     unsigned DestColor = getRegColor(DestReg);
     unsigned NewReg = RegRenamingMap[DestColor];
 
-    LiveInterval& DestLI = LI->getInterval(DestReg);
-    LiveInterval& NewLI = LI->getInterval(NewReg);
+    LiveInterval &DestLI = LI->getInterval(DestReg);
+    LiveInterval &NewLI = LI->getInterval(NewReg);
 
-    assert(DestLI.ranges.size() == 1);
-    LiveRange* DestLR = DestLI.begin();
-    VNInfo* NewVNI = NewLI.getVNInfoAt(DestLR->start);
+    assert(DestLI.ranges.size() == 1
+           && "PHI destination copy's live interval should be a single live "
+               "range from the beginning of the BB to the copy instruction.");
+    LiveRange *DestLR = DestLI.begin();
+    VNInfo *NewVNI = NewLI.getVNInfoAt(DestLR->start);
     if (!NewVNI) {
       NewVNI = NewLI.createValueCopy(DestLR->valno, LI->getVNInfoAllocator());
-      MachineInstr* CopyInstr = I->second;
+      MachineInstr *CopyInstr = I->second;
       CopyInstr->getOperand(1).setIsKill(true);
     }
 
@@ -304,12 +368,12 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction& MF) {
   // register.
   for (SrcCopySet::iterator I = InsertedSrcCopySet.begin(),
        E = InsertedSrcCopySet.end(); I != E; ++I) {
-    MachineBasicBlock* MBB = I->first;
+    MachineBasicBlock *MBB = I->first;
     unsigned SrcReg = I->second;
     if (unsigned RenamedRegister = RegRenamingMap[getRegColor(SrcReg)])
       SrcReg = RenamedRegister;
 
-    LiveInterval& SrcLI = LI->getInterval(SrcReg);
+    LiveInterval &SrcLI = LI->getInterval(SrcReg);
 
     bool isLiveOut = false;
     for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
@@ -323,7 +387,7 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction& MF) {
     if (isLiveOut)
       continue;
 
-    MachineOperand* LastUse = findLastUse(MBB, SrcReg);
+    MachineOperand *LastUse = findLastUse(MBB, SrcReg);
     assert(LastUse);
     SlotIndex LastUseIndex = LI->getInstructionIndex(LastUse->getParent());
     SrcLI.removeRange(LastUseIndex.getDefIndex(), LI->getMBBEndIdx(MBB));
@@ -334,6 +398,7 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction& MF) {
 
   Allocator.Reset();
   RegNodeMap.clear();
+  PHISrcDefs.clear();
   InsertedSrcCopySet.clear();
   InsertedSrcCopyMap.clear();
   InsertedDestCopies.clear();
@@ -349,27 +414,33 @@ void StrongPHIElimination::addReg(unsigned Reg) {
 
 StrongPHIElimination::Node*
 StrongPHIElimination::Node::getLeader() {
-  Node* parentPointer = parent.getPointer();
-  if (parentPointer == this)
-    return this;
-  Node* newParent = parentPointer->getLeader();
-  parent.setPointer(newParent);
-  return newParent;
+  Node *N = this;
+  Node *Parent = parent.getPointer();
+  Node *Grandparent = Parent->parent.getPointer();
+
+  while (Parent != Grandparent) {
+    N->parent.setPointer(Grandparent);
+    N = Grandparent;
+    Parent = Parent->parent.getPointer();
+    Grandparent = Parent->parent.getPointer();
+  }
+
+  return Parent;
 }
 
 unsigned StrongPHIElimination::getRegColor(unsigned Reg) {
   DenseMap<unsigned, Node*>::iterator RI = RegNodeMap.find(Reg);
   if (RI == RegNodeMap.end())
     return 0;
-  Node* Node = RI->second;
+  Node *Node = RI->second;
   if (Node->parent.getInt() & Node::kRegisterIsolatedFlag)
     return 0;
   return Node->getLeader()->value;
 }
 
 void StrongPHIElimination::unionRegs(unsigned Reg1, unsigned Reg2) {
-  Node* Node1 = RegNodeMap[Reg1]->getLeader();
-  Node* Node2 = RegNodeMap[Reg2]->getLeader();
+  Node *Node1 = RegNodeMap[Reg1]->getLeader();
+  Node *Node2 = RegNodeMap[Reg2]->getLeader();
 
   if (Node1->rank > Node2->rank) {
     Node2->parent.setPointer(Node1->getLeader());
@@ -382,15 +453,15 @@ void StrongPHIElimination::unionRegs(unsigned Reg1, unsigned Reg2) {
 }
 
 void StrongPHIElimination::isolateReg(unsigned Reg) {
-  Node* Node = RegNodeMap[Reg];
+  Node *Node = RegNodeMap[Reg];
   Node->parent.setInt(Node->parent.getInt() | Node::kRegisterIsolatedFlag);
 }
 
-unsigned StrongPHIElimination::getPHIColor(MachineInstr* PHI) {
+unsigned StrongPHIElimination::getPHIColor(MachineInstr *PHI) {
   assert(PHI->isPHI());
 
   unsigned DestReg = PHI->getOperand(0).getReg();
-  Node* DestNode = RegNodeMap[DestReg];
+  Node *DestNode = RegNodeMap[DestReg];
   if (DestNode->parent.getInt() & Node::kPHIIsolatedFlag)
     return 0;
 
@@ -402,29 +473,12 @@ unsigned StrongPHIElimination::getPHIColor(MachineInstr* PHI) {
   return 0;
 }
 
-void StrongPHIElimination::isolatePHI(MachineInstr* PHI) {
+void StrongPHIElimination::isolatePHI(MachineInstr *PHI) {
   assert(PHI->isPHI());
-  Node* Node = RegNodeMap[PHI->getOperand(0).getReg()];
+  Node *Node = RegNodeMap[PHI->getOperand(0).getReg()];
   Node->parent.setInt(Node->parent.getInt() | Node::kPHIIsolatedFlag);
 }
 
-void StrongPHIElimination::PartitionRegisters(MachineFunction& MF) {
-  for (MachineFunction::iterator I = MF.begin(), E = MF.end();
-       I != E; ++I) {
-    for (MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
-         BBI != BBE && BBI->isPHI(); ++BBI) {
-      unsigned DestReg = BBI->getOperand(0).getReg();
-      addReg(DestReg);
-
-      for (unsigned i = 1; i < BBI->getNumOperands(); i += 2) {
-        unsigned SrcReg = BBI->getOperand(i).getReg();
-        addReg(SrcReg);
-        unionRegs(DestReg, SrcReg);
-      }
-    }
-  }
-}
-
 /// SplitInterferencesForBasicBlock - traverses a basic block, splitting any
 /// interferences found between registers in the same congruence class. It
 /// takes two DenseMaps as arguments that it also updates:
@@ -466,14 +520,26 @@ void StrongPHIElimination::PartitionRegisters(MachineFunction& MF) {
 /// interference in multiple distinct sets at once.
 void
 StrongPHIElimination::SplitInterferencesForBasicBlock(
-    MachineBasicBlock& MBB,
-    DenseMap<unsigned, unsigned>& CurrentDominatingParent,
-    DenseMap<unsigned, unsigned>& ImmediateDominatingParent) {
-  for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end();
-  BBI != BBE; ++BBI) {
-    for (MachineInstr::const_mop_iterator I = BBI->operands_begin(),
-         E = BBI->operands_end(); I != E && I->isReg() && I->isDef(); ++I) {
-      const MachineOperand& MO = *I;
+    MachineBasicBlock &MBB,
+    DenseMap<unsigned, unsigned> &CurrentDominatingParent,
+    DenseMap<unsigned, unsigned> &ImmediateDominatingParent) {
+  // Sort defs by their order in the original basic block, as the code below
+  // assumes that it is processing definitions in dominance order.
+  std::vector<MachineInstr*> &DefInstrs = PHISrcDefs[&MBB];
+  std::sort(DefInstrs.begin(), DefInstrs.end(), MIIndexCompare(LI));
+
+  for (std::vector<MachineInstr*>::const_iterator BBI = DefInstrs.begin(),
+       BBE = DefInstrs.end(); BBI != BBE; ++BBI) {
+    for (MachineInstr::const_mop_iterator I = (*BBI)->operands_begin(),
+         E = (*BBI)->operands_end(); I != E; ++I) {
+      const MachineOperand &MO = *I;
+
+      // FIXME: This would be faster if it were possible to bail out of checking
+      // an instruction's operands after the explicit defs, but this is incorrect
+      // for variadic instructions, which may appear before register allocation
+      // in the future.
+      if (!MO.isReg() || !MO.isDef())
+        continue;
 
       unsigned DestReg = MO.getReg();
       if (!DestReg || !TargetRegisterInfo::isVirtualRegister(DestReg))
@@ -491,13 +557,14 @@ StrongPHIElimination::SplitInterferencesForBasicBlock(
       // handle it here by tracking defining machine instructions rather than
       // virtual registers. For now, we just handle the situation conservatively
       // in a way that will possibly lead to false interferences.
-      unsigned NewParent = CurrentDominatingParent[DestColor];
+      unsigned &CurrentParent = CurrentDominatingParent[DestColor];
+      unsigned NewParent = CurrentParent;
       if (NewParent == DestReg)
         continue;
 
       // Pop registers from the stack represented by ImmediateDominatingParent
       // until we find a parent that dominates the current instruction.
-      while (NewParent && (!DT->dominates(MRI->getVRegDef(NewParent), BBI)
+      while (NewParent && (!DT->dominates(MRI->getVRegDef(NewParent), *BBI)
                            || !getRegColor(NewParent)))
         NewParent = ImmediateDominatingParent[NewParent];
 
@@ -505,38 +572,33 @@ StrongPHIElimination::SplitInterferencesForBasicBlock(
       // instruction, so it is only necessary to check for the liveness of
       // NewParent in order to check for an interference.
       if (NewParent
-          && LI->getInterval(NewParent).liveAt(LI->getInstructionIndex(BBI))) {
+          && LI->getInterval(NewParent).liveAt(LI->getInstructionIndex(*BBI))) {
         // If there is an interference, always isolate the new register. This
         // could be improved by using a heuristic that decides which of the two
         // registers to isolate.
         isolateReg(DestReg);
-        CurrentDominatingParent[DestColor] = NewParent;
+        CurrentParent = NewParent;
       } else {
         // If there is no interference, update ImmediateDominatingParent and set
         // the CurrentDominatingParent for this color to the current register.
         ImmediateDominatingParent[DestReg] = NewParent;
-        CurrentDominatingParent[DestColor] = DestReg;
+        CurrentParent = DestReg;
       }
     }
   }
 
   // We now walk the PHIs in successor blocks and check for interferences. This
-  // is necesary because the use of a PHI's operands are logically contained in
+  // is necessary because the use of a PHI's operands are logically contained in
   // the predecessor block. The def of a PHI's destination register is processed
   // along with the other defs in a basic block.
 
-  // The map CurrentPHIForColor maps a color to a pair of a MachineInstr* and a
-  // virtual register, which is the operand of that PHI corresponding to the
-  // current basic block.
-  // FIXME: This should use a container that doesn't always perform heap
-  // allocation.
-  DenseMap<unsigned, std::pair<MachineInstr*, unsigned> > CurrentPHIForColor;
+  CurrentPHIForColor.clear();
 
   for (MachineBasicBlock::succ_iterator SI = MBB.succ_begin(),
        SE = MBB.succ_end(); SI != SE; ++SI) {
     for (MachineBasicBlock::iterator BBI = (*SI)->begin(), BBE = (*SI)->end();
          BBI != BBE && BBI->isPHI(); ++BBI) {
-      MachineInstr* PHI = BBI;
+      MachineInstr *PHI = BBI;
 
       // If a PHI is already isolated, either by being isolated directly or
       // having all of its operands isolated, ignore it.
@@ -555,12 +617,13 @@ StrongPHIElimination::SplitInterferencesForBasicBlock(
 
       // Pop registers from the stack represented by ImmediateDominatingParent
       // until we find a parent that dominates the current instruction.
-      unsigned NewParent = CurrentDominatingParent[Color];
+      unsigned &CurrentParent = CurrentDominatingParent[Color];
+      unsigned NewParent = CurrentParent;
       while (NewParent
              && (!DT->dominates(MRI->getVRegDef(NewParent)->getParent(), &MBB)
                  || !getRegColor(NewParent)))
         NewParent = ImmediateDominatingParent[NewParent];
-      CurrentDominatingParent[Color] = NewParent;
+      CurrentParent = NewParent;
 
       // If there is an interference with a register, always isolate the
       // register rather than the PHI. It is also possible to isolate the
@@ -570,7 +633,8 @@ StrongPHIElimination::SplitInterferencesForBasicBlock(
                     && NewParent != PredOperandReg)
         isolateReg(NewParent);
 
-      std::pair<MachineInstr*, unsigned> CurrentPHI = CurrentPHIForColor[Color];
+      std::pair<MachineInstr*, unsigned>
+        &CurrentPHI = CurrentPHIForColor[Color];
 
       // If two PHIs have the same operand from every shared predecessor, then
       // they don't actually interfere. Otherwise, isolate the current PHI. This
@@ -579,18 +643,19 @@ StrongPHIElimination::SplitInterferencesForBasicBlock(
       if (CurrentPHI.first && CurrentPHI.second != PredOperandReg)
         isolatePHI(PHI);
       else
-        CurrentPHIForColor[Color] = std::make_pair(PHI, PredOperandReg);
+        CurrentPHI = std::make_pair(PHI, PredOperandReg);
     }
   }
 }
 
-void StrongPHIElimination::InsertCopiesForPHI(MachineInstr* PHI,
-                                              MachineBasicBlock* MBB) {
+void StrongPHIElimination::InsertCopiesForPHI(MachineInstr *PHI,
+                                              MachineBasicBlock *MBB) {
   assert(PHI->isPHI());
+  ++NumPHIsLowered;
   unsigned PHIColor = getPHIColor(PHI);
 
   for (unsigned i = 1; i < PHI->getNumOperands(); i += 2) {
-    MachineOperand& SrcMO = PHI->getOperand(i);
+    MachineOperand &SrcMO = PHI->getOperand(i);
 
     // If a source is defined by an implicit def, there is no need to insert a
     // copy in the predecessor.
@@ -601,15 +666,15 @@ void StrongPHIElimination::InsertCopiesForPHI(MachineInstr* PHI,
     assert(TargetRegisterInfo::isVirtualRegister(SrcReg) &&
            "Machine PHI Operands must all be virtual registers!");
 
-    MachineBasicBlock* PredBB = PHI->getOperand(i + 1).getMBB();
+    MachineBasicBlock *PredBB = PHI->getOperand(i + 1).getMBB();
     unsigned SrcColor = getRegColor(SrcReg);
 
     // If neither the PHI nor the operand were isolated, then we only need to
     // set the phi-kill flag on the VNInfo at this PHI.
     if (PHIColor && SrcColor == PHIColor) {
-      LiveInterval& SrcInterval = LI->getInterval(SrcReg);
+      LiveInterval &SrcInterval = LI->getInterval(SrcReg);
       SlotIndex PredIndex = LI->getMBBEndIdx(PredBB);
-      VNInfo* SrcVNI = SrcInterval.getVNInfoAt(PredIndex.getPrevIndex());
+      VNInfo *SrcVNI = SrcInterval.getVNInfoAt(PredIndex.getPrevIndex());
       assert(SrcVNI);
       SrcVNI->setHasPHIKill(true);
       continue;
@@ -624,18 +689,19 @@ void StrongPHIElimination::InsertCopiesForPHI(MachineInstr* PHI,
     }
 
     if (!CopyReg) {
-      const TargetRegisterClass* RC = MRI->getRegClass(SrcReg);
+      const TargetRegisterClass *RC = MRI->getRegClass(SrcReg);
       CopyReg = MRI->createVirtualRegister(RC);
 
       MachineBasicBlock::iterator
         CopyInsertPoint = findPHICopyInsertPoint(PredBB, MBB, SrcReg);
       unsigned SrcSubReg = SrcMO.getSubReg();
-      MachineInstr* CopyInstr = BuildMI(*PredBB,
+      MachineInstr *CopyInstr = BuildMI(*PredBB,
                                         CopyInsertPoint,
                                         PHI->getDebugLoc(),
                                         TII->get(TargetOpcode::COPY),
                                         CopyReg).addReg(SrcReg, 0, SrcSubReg);
       LI->InsertMachineInstrInMaps(CopyInstr);
+      ++NumSrcCopiesInserted;
 
       // addLiveRangeToEndOfBlock() also adds the phikill flag to the VNInfo for
       // the newly added range.
@@ -663,7 +729,7 @@ void StrongPHIElimination::InsertCopiesForPHI(MachineInstr* PHI,
     // never rely on LiveIntervals being correct while inserting copies.
     // FIXME: Should this just count uses at PHIs like the normal PHIElimination
     // pass does?
-    LiveInterval& SrcLI = LI->getInterval(SrcReg);
+    LiveInterval &SrcLI = LI->getInterval(SrcReg);
     SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
     SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
     SlotIndex NextInstrIndex = PHIIndex.getNextIndex();
@@ -675,11 +741,11 @@ void StrongPHIElimination::InsertCopiesForPHI(MachineInstr* PHI,
   unsigned DestColor = getRegColor(DestReg);
 
   if (PHIColor && DestColor == PHIColor) {
-    LiveInterval& DestLI = LI->getInterval(DestReg);
+    LiveInterval &DestLI = LI->getInterval(DestReg);
 
     // Set the phi-def flag for the VN at this PHI.
     SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
-    VNInfo* DestVNI = DestLI.getVNInfoAt(PHIIndex.getDefIndex());
+    VNInfo *DestVNI = DestLI.getVNInfoAt(PHIIndex.getDefIndex());
     assert(DestVNI);
     DestVNI->setIsPHIDef(true);
   
@@ -695,23 +761,24 @@ void StrongPHIElimination::InsertCopiesForPHI(MachineInstr* PHI,
     return;
   }
 
-  const TargetRegisterClass* RC = MRI->getRegClass(DestReg);
+  const TargetRegisterClass *RC = MRI->getRegClass(DestReg);
   unsigned CopyReg = MRI->createVirtualRegister(RC);
 
-  MachineInstr* CopyInstr = BuildMI(*MBB,
+  MachineInstr *CopyInstr = BuildMI(*MBB,
                                     MBB->SkipPHIsAndLabels(MBB->begin()),
                                     PHI->getDebugLoc(),
                                     TII->get(TargetOpcode::COPY),
                                     DestReg).addReg(CopyReg);
   LI->InsertMachineInstrInMaps(CopyInstr);
   PHI->getOperand(0).setReg(CopyReg);
+  ++NumDestCopiesInserted;
 
   // Add the region from the beginning of MBB to the copy instruction to
   // CopyReg's live interval, and give the VNInfo the phidef flag.
-  LiveInterval& CopyLI = LI->getOrCreateInterval(CopyReg);
+  LiveInterval &CopyLI = LI->getOrCreateInterval(CopyReg);
   SlotIndex MBBStartIndex = LI->getMBBStartIdx(MBB);
   SlotIndex DestCopyIndex = LI->getInstructionIndex(CopyInstr);
-  VNInfo* CopyVNI = CopyLI.getNextValue(MBBStartIndex,
+  VNInfo *CopyVNI = CopyLI.getNextValue(MBBStartIndex,
                                         CopyInstr,
                                         LI->getVNInfoAllocator());
   CopyVNI->setIsPHIDef(true);
@@ -721,11 +788,11 @@ void StrongPHIElimination::InsertCopiesForPHI(MachineInstr* PHI,
 
   // Adjust DestReg's live interval to adjust for its new definition at
   // CopyInstr.
-  LiveInterval& DestLI = LI->getOrCreateInterval(DestReg);
+  LiveInterval &DestLI = LI->getOrCreateInterval(DestReg);
   SlotIndex PHIIndex = LI->getInstructionIndex(PHI);
   DestLI.removeRange(PHIIndex.getDefIndex(), DestCopyIndex.getDefIndex());
 
-  VNInfo* DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getDefIndex());
+  VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getDefIndex());
   assert(DestVNI);
   DestVNI->def = DestCopyIndex.getDefIndex();
 
@@ -736,17 +803,17 @@ void StrongPHIElimination::MergeLIsAndRename(unsigned Reg, unsigned NewReg) {
   if (Reg == NewReg)
     return;
 
-  LiveInterval& OldLI = LI->getInterval(Reg);
-  LiveInterval& NewLI = LI->getInterval(NewReg);
+  LiveInterval &OldLI = LI->getInterval(Reg);
+  LiveInterval &NewLI = LI->getInterval(NewReg);
 
   // Merge the live ranges of the two registers.
   DenseMap<VNInfo*, VNInfo*> VNMap;
   for (LiveInterval::iterator LRI = OldLI.begin(), LRE = OldLI.end();
        LRI != LRE; ++LRI) {
     LiveRange OldLR = *LRI;
-    VNInfo* OldVN = OldLR.valno;
+    VNInfo *OldVN = OldLR.valno;
 
-    VNInfo*& NewVN = VNMap[OldVN];
+    VNInfo *&NewVN = VNMap[OldVN];
     if (!NewVN) {
       NewVN = NewLI.createValueCopy(OldVN, LI->getVNInfoAllocator());
       VNMap[OldVN] = NewVN;