More templatization.

[oota-llvm.git] / lib / CodeGen / StrongPHIElimination.cpp

diff --git a/lib/CodeGen/StrongPHIElimination.cpp b/lib/CodeGen/StrongPHIElimination.cpp
index 200ae8f84e65178963c710af5cfe23fbd2197cf1..d023b59277a7843100b334fc688a0dc2a5a06f70 100644 (file)
--- a/lib/CodeGen/StrongPHIElimination.cpp
+++ b/lib/CodeGen/StrongPHIElimination.cpp
@@ -21,10 +21,12 @@
 
 #define DEBUG_TYPE "strongphielim"
 #include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/BreakCriticalMachineEdge.h"
 #include "llvm/CodeGen/LiveVariables.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/CodeGen/SSARegMap.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/ADT/Statistic.h"
@@ -92,6 +94,7 @@ namespace {
     void processBlock(MachineBasicBlock* MBB);
     
     std::vector<DomForestNode*> computeDomForest(std::set<unsigned>& instrs);
+    void breakCriticalEdges(MachineFunction &Fn);
     
   };
 
@@ -225,10 +228,9 @@ bool isLiveIn(LiveVariables::VarInfo& V, MachineBasicBlock* MBB) {
   if (V.AliveBlocks.test(MBB->getNumber()))
     return true;
   
-  for (std::vector<MachineInstr*>::iterator I = V.Kills.begin(),
-       E = V.Kills.end(); I != E; ++I)
-    if ((*I)->getParent() == MBB)
-      return true;
+  if (V.DefInst->getParent() != MBB &&
+      V.UsedBlocks.test(MBB->getNumber()))
+    return true;
   
   return false;
 }
@@ -236,11 +238,15 @@ bool isLiveIn(LiveVariables::VarInfo& V, MachineBasicBlock* MBB) {
 /// isLiveOut - help method that determines, from a VarInfo, if a register is
 /// live out of a block.
 bool isLiveOut(LiveVariables::VarInfo& V, MachineBasicBlock* MBB) {
-  if (V.AliveBlocks.test(MBB->getNumber()))
-    return true;
-  
-  if (V.DefInst->getParent() == MBB)
+  if (MBB == V.DefInst->getParent() ||
+      V.UsedBlocks.test(MBB->getNumber())) {
+    for (std::vector<MachineInstr*>::iterator I = V.Kills.begin(), 
+         E = V.Kills.end(); I != E; ++I)
+      if ((*I)->getParent() == MBB)
+        return false;
+    
     return true;
+  }
   
   return false;
 }
@@ -279,19 +285,55 @@ void StrongPHIElimination::processBlock(MachineBasicBlock* MBB) {
       } else {
         PHIUnion.insert(SrcReg);
         UnionedBlocks.insert(SrcInfo.DefInst->getParent());
-        
-        // DO STUFF HERE
-        
       }
-      
-      ProcessedNames.insert(PHIUnion.begin(), PHIUnion.end());
     }
     
+    std::vector<StrongPHIElimination::DomForestNode*> DF = 
+                                                     computeDomForest(PHIUnion);
+    
+    // DO STUFF HERE
+    
+    ProcessedNames.insert(PHIUnion.begin(), PHIUnion.end());
     ++P;
   }
 }
 
+/// breakCriticalEdges - Break critical edges coming into blocks with PHI
+/// nodes, preserving dominator and livevariable info.
+void StrongPHIElimination::breakCriticalEdges(MachineFunction &Fn) {
+  typedef std::pair<MachineBasicBlock*, MachineBasicBlock*> MBB_pair;
+  
+  MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>();
+  LiveVariables& LV = getAnalysis<LiveVariables>();
+  
+  // Find critical edges
+  std::vector<MBB_pair> criticals;
+  for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
+    if (!I->empty() &&
+        I->begin()->getOpcode() == TargetInstrInfo::PHI &&
+        I->pred_size() > 1)
+      for (MachineBasicBlock::pred_iterator PI = I->pred_begin(),
+           PE = I->pred_end(); PI != PE; ++PI)
+        if ((*PI)->succ_size() > 1)
+          criticals.push_back(std::make_pair(*PI, I));
+  
+  for (std::vector<MBB_pair>::iterator I = criticals.begin(),
+       E = criticals.end(); I != E; ++I) {
+    // Split the edge
+    MachineBasicBlock* new_bb = SplitCriticalMachineEdge(I->first, I->second);
+    
+    // Update dominators
+    MDT.splitBlock(I->first);
+    
+    // Update livevariables
+    for (unsigned var = 1024; var < Fn.getSSARegMap()->getLastVirtReg(); ++var)
+      if (isLiveOut(LV.getVarInfo(var), I->first))
+        LV.getVarInfo(var).AliveBlocks.set(new_bb->getNumber());
+  }
+}
+
 bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) {
+  breakCriticalEdges(Fn);
   computeDFS(Fn);
   
   for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)