X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FStrongPHIElimination.cpp;h=5d7bc23694bf9100f033c606e0b892690ba79bf6;hb=a29c13086a3add78a3a79f744573fe09eaa9dc88;hp=9f59417b5dc0e05dec1315204806c02baed4b40b;hpb=a8c763b3071ae1a58ee8baeb282331245527e004;p=oota-llvm.git

diff --git a/lib/CodeGen/StrongPHIElimination.cpp b/lib/CodeGen/StrongPHIElimination.cpp
index 9f59417b5dc..5d7bc23694b 100644
--- a/lib/CodeGen/StrongPHIElimination.cpp
+++ b/lib/CodeGen/StrongPHIElimination.cpp
@@ -33,17 +33,18 @@
 #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 {
     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;
@@ -141,7 +142,7 @@ namespace {
     void ScheduleCopies(MachineBasicBlock* MBB, std::set<unsigned>& pushed);
     void InsertCopies(MachineDomTreeNode* MBB,
                       SmallPtrSet<MachineBasicBlock*, 16>& v);
-    void mergeLiveIntervals(unsigned primary, unsigned secondary);
+    bool mergeLiveIntervals(unsigned primary, unsigned secondary);
   };
 }
 
@@ -294,7 +295,7 @@ static bool isLiveIn(unsigned r, MachineBasicBlock* MBB,
                      LiveIntervals& LI) {
   LiveInterval& I = LI.getOrCreateInterval(r);
   unsigned idx = LI.getMBBStartIdx(MBB);
-  return I.liveBeforeAndAt(idx);
+  return I.liveAt(idx);
 }
 
 /// isLiveOut - help method that determines, from a regno, if a register is
@@ -418,7 +419,6 @@ 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)) {
@@ -447,6 +447,11 @@ void StrongPHIElimination::processBlock(MachineBasicBlock* MBB) {
         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
@@ -546,6 +551,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) {
+      DOUT << "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 
@@ -636,13 +647,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));
@@ -651,9 +662,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;
     }
@@ -669,8 +680,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);
       
@@ -684,6 +696,8 @@ void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB,
         TII->copyRegToReg(*PI->getParent(), PI, t,
                           curr.second, RC, RC);
         
+        DOUT << "Inserted copy from " << curr.second << " to " << t << "\n";
+        
         // Push temporary on Stacks
         Stacks[curr.second].push_back(t);
         
@@ -698,6 +712,8 @@ void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB,
       TII->copyRegToReg(*MBB, MBB->getFirstTerminator(), curr.second,
                         map[curr.first], RC, RC);
       map[curr.first] = curr.second;
+      DOUT << "Inserted copy from " << curr.first << " to "
+           << curr.second << "\n";
       
       // Push this copy onto InsertedPHICopies so we can
       // update LiveIntervals with it.
@@ -705,15 +721,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 {
@@ -722,9 +739,10 @@ void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB,
     }
     
     if (!copy_set.empty()) {
-      std::pair<unsigned, unsigned> curr = *copy_set.begin();
-      copy_set.erase(curr.first);
+      std::multimap<unsigned, unsigned>::iterator CI = copy_set.begin();
+      std::pair<unsigned, unsigned> curr = *CI;
       worklist.insert(curr);
+      copy_set.erase(CI);
       
       LiveInterval& I = LI.getInterval(curr.second);
       MachineBasicBlock::iterator term = MBB->getFirstTerminator();
@@ -762,10 +780,19 @@ void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB,
   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.getOrCreateInterval(I->first).liveAt(
-                                      LI.getMBBEndIdx(I->second->getParent())))
-      LI.addLiveRangeToEndOfBlock(I->first, I->second);
+    if (RegHandled.insert(I->first).second) {
+      LiveInterval& Int = LI.getOrCreateInterval(I->first);
+      unsigned instrIdx = LI.getInstructionIndex(I->second);
+      if (Int.liveAt(LiveIntervals::getDefIndex(instrIdx)))
+        Int.removeRange(LiveIntervals::getDefIndex(instrIdx),
+                        LI.getMBBEndIdx(I->second->getParent())+1,
+                        true);
+      
+      LiveRange R = LI.addLiveRangeToEndOfBlock(I->first, I->second);
+      R.valno->copy = I->second;
+      R.valno->def =
+                  LiveIntervals::getDefIndex(LI.getInstructionIndex(I->second));
+    }
   }
 }
 
@@ -785,7 +812,7 @@ void StrongPHIElimination::InsertCopies(MachineDomTreeNode* MDTN,
       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());
@@ -806,7 +833,7 @@ void StrongPHIElimination::InsertCopies(MachineDomTreeNode* MDTN,
                          LiveIntervals::getUseIndex(LI.getInstructionIndex(I)));
         
         LiveRange LR (LI.getMBBStartIdx(I->getParent()),
-                      LiveIntervals::getUseIndex(LI.getInstructionIndex(I)),
+                      LiveIntervals::getUseIndex(LI.getInstructionIndex(I))+1,
                       FirstVN);
         
         Int.addRange(LR);
@@ -828,7 +855,7 @@ void StrongPHIElimination::InsertCopies(MachineDomTreeNode* MDTN,
     Stacks[*I].pop_back();
 }
 
-void StrongPHIElimination::mergeLiveIntervals(unsigned primary,
+bool StrongPHIElimination::mergeLiveIntervals(unsigned primary,
                                               unsigned secondary) {
   
   LiveIntervals& LI = getAnalysis<LiveIntervals>();
@@ -836,20 +863,42 @@ void StrongPHIElimination::mergeLiveIntervals(unsigned primary,
   LiveInterval& RHS = LI.getOrCreateInterval(secondary);
   
   LI.computeNumbering();
-                     
-  SmallVector<VNInfo*, 4> VNSet (RHS.vni_begin(), RHS.vni_end());
+  
   DenseMap<VNInfo*, VNInfo*> VNMap;
-  for (SmallVector<VNInfo*, 4>::iterator VI = VNSet.begin(),
-       VE = VNSet.end(); VI != VE; ++VI) {
-    VNInfo* NewVN = LHS.getNextValue((*VI)->def,
-                                     (*VI)->copy,
-                                     LI.getVNInfoAllocator());
-    LHS.MergeValueInAsValue(RHS, *VI, NewVN);
-    RHS.removeValNo(*VI);
+  for (LiveInterval::iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) {
+    LiveRange R = *I;
+ 
+    unsigned Start = R.start;
+    unsigned 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;
   }
   
-  if (RHS.empty())
-    LI.removeInterval(RHS.reg);
+  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.getNextValue(OldVN->def,
+                               OldVN->copy,
+                               LI.getVNInfoAllocator());
+      NewVN->kills = OldVN->kills;
+    }
+    
+    LiveRange LR (R.start, R.end, NewVN);
+    LHS.addRange(LR);
+  }
+  
+  LI.removeInterval(RHS.reg);
+  
+  return true;
 }
 
 bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) {
@@ -881,6 +930,7 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) {
         unsigned reg = OI->first;
         ++OI;
         I->second.erase(reg);
+        DOUT << "Removing Renaming: " << reg << " -> " << I->first << "\n";
       }
     }
   }
@@ -897,22 +947,51 @@ bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) {
     while (I->second.size()) {
       std::map<unsigned, MachineBasicBlock*>::iterator SI = I->second.begin();
       
+      DOUT << "Renaming: " << SI->first << " -> " << I->first << "\n";
+      
       if (SI->first != I->first) {
-        mergeLiveIntervals(I->first, SI->first);
-        Fn.getRegInfo().replaceRegWith(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);
+          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.computeNumbering();
+          
+          LiveInterval& Int = LI.getOrCreateInterval(I->first);
+          unsigned instrIdx =
+                     LI.getInstructionIndex(--SI->second->getFirstTerminator());
+          if (Int.liveAt(LiveIntervals::getDefIndex(instrIdx)))
+            Int.removeRange(LiveIntervals::getDefIndex(instrIdx),
+                            LI.getMBBEndIdx(SI->second)+1, true);
+
+          LiveRange R = LI.addLiveRangeToEndOfBlock(I->first,
+                                            --SI->second->getFirstTerminator());
+          R.valno->copy = --SI->second->getFirstTerminator();
+          R.valno->def = LiveIntervals::getDefIndex(instrIdx);
+          
+          DOUT << "Renaming failed: " << SI->first << " -> "
+               << I->first << "\n";
         }
       }
       
+      LiveInterval& Int = LI.getOrCreateInterval(I->first);
+      const LiveRange* LR =
+                       Int.getLiveRangeContaining(LI.getMBBEndIdx(SI->second));
+      LR->valno->hasPHIKill = 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) {