From 35e2dba67215045b1be2b890699788adfa939d05 Mon Sep 17 00:00:00 2001
From: Owen Anderson <resistor@mac.com>
Date: Mon, 12 Nov 2007 17:27:27 +0000
Subject: [PATCH] Break critical edges coming into blocks with PHI nodes.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@44019 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/CodeGen/StrongPHIElimination.cpp | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)

diff --git a/lib/CodeGen/StrongPHIElimination.cpp b/lib/CodeGen/StrongPHIElimination.cpp
index f64186e8e8c..3d5ee9fb3ce 100644
--- a/lib/CodeGen/StrongPHIElimination.cpp
+++ b/lib/CodeGen/StrongPHIElimination.cpp
@@ -93,6 +93,7 @@ namespace {
     void processBlock(MachineBasicBlock* MBB);
     
     std::vector<DomForestNode*> computeDomForest(std::set<unsigned>& instrs);
+    void breakCriticalEdges(MachineFunction &Fn);
     
   };
 
@@ -295,7 +296,32 @@ void StrongPHIElimination::processBlock(MachineBasicBlock* MBB) {
   }
 }
 
+void StrongPHIElimination::breakCriticalEdges(MachineFunction &Fn) {
+  typedef std::pair<MachineBasicBlock*, MachineBasicBlock*> MBB_pair;
+  
+  MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>();
+  //LiveVariables& LV = getAnalysis<LiveVariables>();
+  
+  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) {
+    SplitCriticalMachineEdge(I->first, I->second);
+    
+    MDT.splitBlock(I->first);
+  }
+}
+
 bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) {
+  breakCriticalEdges(Fn);
   computeDFS(Fn);
   
   for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
-- 
2.34.1