Teach PHIElimination to split critical edges when -split-phi-edges is enabled.

Critical edges leading to a PHI node are split when the PHI source variable is
live out from the predecessor block. This help the coalescer eliminate more
PHI joins.

llvm-svn: 86725

1 files changed, 40 insertions, 0 deletions

diff --git a/llvm/lib/CodeGen/LiveVariables.cpp b/llvm/lib/CodeGen/LiveVariables.cpp
index 96c655c1a9b..1580667222f 100644
--- a/llvm/lib/CodeGen/LiveVariables.cpp
+++ b/llvm/lib/CodeGen/LiveVariables.cpp
@@ -50,6 +50,14 @@ void LiveVariables::getAnalysisUsage(AnalysisUsage &AU) const {
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
+MachineInstr *
+LiveVariables::VarInfo::findKill(const MachineBasicBlock *MBB) const {
+  for (unsigned i = 0, e = Kills.size(); i != e; ++i)
+    if (Kills[i]->getParent() == MBB)
+      return Kills[i];
+  return NULL;
+}
+
 void LiveVariables::VarInfo::dump() const {
   errs() << "  Alive in blocks: ";
   for (SparseBitVector<>::iterator I = AliveBlocks.begin(),
@@ -641,3 +649,35 @@ void LiveVariables::analyzePHINodes(const MachineFunction& Fn) {
         PHIVarInfo[BBI->getOperand(i + 1).getMBB()->getNumber()]
           .push_back(BBI->getOperand(i).getReg());
 }
+
+void LiveVariables::addNewBlock(MachineBasicBlock *A, MachineBasicBlock *B) {
+  unsigned NumA = A->getNumber();
+  unsigned NumB = B->getNumber();
+
+  // Update info for all live variables
+  for (unsigned i = 0, e = VirtRegInfo.size(); i != e; ++i) {
+    VarInfo &VI = VirtRegInfo[i];
+
+    // Anything live through B is also live through A.
+    if (VI.AliveBlocks.test(NumB)) {
+      VI.AliveBlocks.set(NumA);
+      continue;
+    }
+
+    // If we're not killed in B, we are not live in
+    if (!VI.findKill(B))
+      continue;
+
+    unsigned Reg = i+TargetRegisterInfo::FirstVirtualRegister;
+
+    // Find a def outside B
+    for (MachineRegisterInfo::def_iterator di = MRI->def_begin(Reg),
+           de=MRI->def_end(); di != de; ++di) {
+      if (di->getParent() != B) {
+        // Reg was defined outside B and killed in B - it must be live in.
+        VI.AliveBlocks.set(NumA);
+        break;
+      }
+    }
+  }
+}