Fix liveness calculation when splitting critical edges during PHI elimination.

- Edges are split before any phis are eliminated, so the code is SSA.

- Create a proper IR BasicBlock for the split edges.

- LiveVariables::addNewBlock now has same syntax as
  MachineDominatorTree::addNewBlock. Algorithm calculates predecessor live-out
  set rather than successor live-in set.

This feature still causes some miscompilations.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86867 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 78 insertions, 52 deletions

diff --git a/lib/CodeGen/LiveVariables.cpp b/lib/CodeGen/LiveVariables.cpp
index 1580667222..cba0371f25 100644
--- a/lib/CodeGen/LiveVariables.cpp
+++ b/lib/CodeGen/LiveVariables.cpp
@@ -650,34 +650,35 @@ void LiveVariables::analyzePHINodes(const MachineFunction& Fn) {
           .push_back(BBI->getOperand(i).getReg());
 }
 
-void LiveVariables::addNewBlock(MachineBasicBlock *A, MachineBasicBlock *B) {
-  unsigned NumA = A->getNumber();
-  unsigned NumB = B->getNumber();
+/// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All
+/// variables that are live out of DomBB will be marked as passing live through
+/// BB.
+void LiveVariables::addNewBlock(MachineBasicBlock *BB,
+                                MachineBasicBlock *DomBB) {
+  const unsigned NumNew = BB->getNumber();
+  const unsigned NumDom = DomBB->getNumber();
 
   // Update info for all live variables
-  for (unsigned i = 0, e = VirtRegInfo.size(); i != e; ++i) {
-    VarInfo &VI = VirtRegInfo[i];
+  for (unsigned Reg = TargetRegisterInfo::FirstVirtualRegister,
+         E = MRI->getLastVirtReg()+1; Reg != E; ++Reg) {
+    VarInfo &VI = getVarInfo(Reg);
 
-    // Anything live through B is also live through A.
-    if (VI.AliveBlocks.test(NumB)) {
-      VI.AliveBlocks.set(NumA);
+    // Anything live through DomBB is also live through BB.
+    if (VI.AliveBlocks.test(NumDom)) {
+      VI.AliveBlocks.set(NumNew);
       continue;
     }
 
-    // If we're not killed in B, we are not live in
-    if (!VI.findKill(B))
+    // Variables not defined in DomBB cannot be live out.
+    const MachineInstr *Def = MRI->getVRegDef(Reg);
+    if (!Def || Def->getParent() != DomBB)
       continue;
 
-    unsigned Reg = i+TargetRegisterInfo::FirstVirtualRegister;
+    // Killed by DomBB?
+    if (VI.findKill(DomBB))
+      continue;
 
-    // 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;
-      }
-    }
+    // This register is defined in DomBB and live out
+    VI.AliveBlocks.set(NumNew);
   }
 }
diff --git a/lib/CodeGen/PHIElimination.cpp b/lib/CodeGen/PHIElimination.cpp
index 7c9c18c1cb..53a7ea2188 100644
--- a/lib/CodeGen/PHIElimination.cpp
+++ b/lib/CodeGen/PHIElimination.cpp
@@ -23,6 +23,7 @@
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/Function.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/STLExtras.h"
@@ -65,10 +66,17 @@ bool llvm::PHIElimination::runOnMachineFunction(MachineFunction &Fn) {
 
   PHIDefs.clear();
   PHIKills.clear();
-  analyzePHINodes(Fn);
 
   bool Changed = false;
 
+  // Split critical edges to help the coalescer
+  if (SplitEdges)
+    for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
+      Changed |= SplitPHIEdges(Fn, *I);
+
+  // Populate VRegPHIUseCount
+  analyzePHINodes(Fn);
+
   // Eliminate PHI instructions by inserting copies into predecessor blocks.
   for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
     Changed |= EliminatePHINodes(Fn, *I);
@@ -87,7 +95,6 @@ bool llvm::PHIElimination::runOnMachineFunction(MachineFunction &Fn) {
   return Changed;
 }
 
-
 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
 /// predecessor basic blocks.
 ///
@@ -96,9 +103,6 @@ bool llvm::PHIElimination::EliminatePHINodes(MachineFunction &MF,
   if (MBB.empty() || MBB.front().getOpcode() != TargetInstrInfo::PHI)
     return false;   // Quick exit for basic blocks without PHIs.
 
-  if (SplitEdges)
-    SplitPHIEdges(MF, MBB);
-
   // Get an iterator to the first instruction after the last PHI node (this may
   // also be the end of the basic block).
   MachineBasicBlock::iterator AfterPHIsIt = SkipPHIsAndLabels(MBB, MBB.begin());
@@ -293,7 +297,7 @@ void llvm::PHIElimination::LowerAtomicPHINode(
     // Okay, if we now know that the value is not live out of the block, we can
     // add a kill marker in this block saying that it kills the incoming value!
     // When SplitEdges is enabled, the value is never live out.
-    if (!ValueIsUsed && (SplitEdges || !isLiveOut(SrcReg, opBlock, *LV))) {
+    if (!ValueIsUsed && !isLiveOut(SrcReg, opBlock, *LV)) {
       // In our final twist, we have to decide which instruction kills the
       // register.  In most cases this is the copy, however, the first
       // terminator instruction at the end of the block may also use the value.
@@ -345,8 +349,10 @@ void llvm::PHIElimination::analyzePHINodes(const MachineFunction& Fn) {
                                      BBI->getOperand(i).getReg())];
 }
 
-void llvm::PHIElimination::SplitPHIEdges(MachineFunction &MF,
+bool llvm::PHIElimination::SplitPHIEdges(MachineFunction &MF,
                                          MachineBasicBlock &MBB) {
+  if (MBB.empty() || MBB.front().getOpcode() != TargetInstrInfo::PHI)
+    return false;   // Quick exit for basic blocks without PHIs.
   LiveVariables &LV = getAnalysis<LiveVariables>();
   for (MachineBasicBlock::const_iterator BBI = MBB.begin(), BBE = MBB.end();
        BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) {
@@ -354,29 +360,29 @@ void llvm::PHIElimination::SplitPHIEdges(MachineFunction &MF,
       unsigned Reg = BBI->getOperand(i).getReg();
       MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB();
       // We break edges when registers are live out from the predecessor block
-      // (not considering PHI nodes).
-      if (isLiveOut(Reg, *PreMBB, LV))
+      // (not considering PHI nodes). If the register is live in to this block
+      // anyway, we would gain nothing from splitting.
+      if (isLiveOut(Reg, *PreMBB, LV) && !isLiveIn(Reg, MBB, LV))
         SplitCriticalEdge(PreMBB, &MBB);
     }
   }
+  return true;
 }
 
 bool llvm::PHIElimination::isLiveOut(unsigned Reg, const MachineBasicBlock &MBB,
                                      LiveVariables &LV) {
-  LiveVariables::VarInfo &InRegVI = LV.getVarInfo(Reg);
+  LiveVariables::VarInfo &VI = LV.getVarInfo(Reg);
 
   // Loop over all of the successors of the basic block, checking to see if
   // the value is either live in the block, or if it is killed in the block.
   std::vector<MachineBasicBlock*> OpSuccBlocks;
-
-  // Otherwise, scan successors, including the BB the PHI node lives in.
   for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(),
          E = MBB.succ_end(); SI != E; ++SI) {
     MachineBasicBlock *SuccMBB = *SI;
 
     // Is it alive in this successor?
     unsigned SuccIdx = SuccMBB->getNumber();
-    if (InRegVI.AliveBlocks.test(SuccIdx))
+    if (VI.AliveBlocks.test(SuccIdx))
       return true;
     OpSuccBlocks.push_back(SuccMBB);
   }
@@ -386,36 +392,56 @@ bool llvm::PHIElimination::isLiveOut(unsigned Reg, const MachineBasicBlock &MBB,
   switch (OpSuccBlocks.size()) {
   case 1: {
     MachineBasicBlock *SuccMBB = OpSuccBlocks[0];
-    for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i)
-      if (InRegVI.Kills[i]->getParent() == SuccMBB)
+    for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i)
+      if (VI.Kills[i]->getParent() == SuccMBB)
         return true;
     break;
   }
   case 2: {
     MachineBasicBlock *SuccMBB1 = OpSuccBlocks[0], *SuccMBB2 = OpSuccBlocks[1];
-    for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i)
-      if (InRegVI.Kills[i]->getParent() == SuccMBB1 ||
-          InRegVI.Kills[i]->getParent() == SuccMBB2)
+    for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i)
+      if (VI.Kills[i]->getParent() == SuccMBB1 ||
+          VI.Kills[i]->getParent() == SuccMBB2)
         return true;
     break;
   }
   default:
     std::sort(OpSuccBlocks.begin(), OpSuccBlocks.end());
-    for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i)
+    for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i)
       if (std::binary_search(OpSuccBlocks.begin(), OpSuccBlocks.end(),
-                             InRegVI.Kills[i]->getParent()))
+                             VI.Kills[i]->getParent()))
         return true;
   }
   return false;
 }
 
+bool llvm::PHIElimination::isLiveIn(unsigned Reg, const MachineBasicBlock &MBB,
+                                    LiveVariables &LV) {
+  LiveVariables::VarInfo &VI = LV.getVarInfo(Reg);
+
+  return VI.AliveBlocks.test(MBB.getNumber()) || VI.findKill(&MBB);
+}
+
 MachineBasicBlock *PHIElimination::SplitCriticalEdge(MachineBasicBlock *A,
                                                      MachineBasicBlock *B) {
   assert(A && B && "Missing MBB end point");
   ++NumSplits;
 
+  BasicBlock *ABB = const_cast<BasicBlock*>(A->getBasicBlock());
+  BasicBlock *BBB = const_cast<BasicBlock*>(B->getBasicBlock());
+  assert(ABB && BBB && "End points must have a basic block");
+  BasicBlock *BB = BasicBlock::Create(BBB->getContext(),
+                                      ABB->getName() + "." + BBB->getName() +
+                                      "_phi_edge");
+  Function *F = ABB->getParent();
+  F->getBasicBlockList().insert(F->end(), BB);
+
+  BranchInst::Create(BBB, BB);
+  // We could do more here to produce correct IR, compare
+  // llvm::SplitCriticalEdge
+
   MachineFunction *MF = A->getParent();
-  MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock(B->getBasicBlock());
+  MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock(BB);
   MF->push_back(NMBB);
   const unsigned NewNum = NMBB->getNumber();
   DEBUG(errs() << "PHIElimination splitting critical edge:"
@@ -430,21 +456,14 @@ MachineBasicBlock *PHIElimination::SplitCriticalEdge(MachineBasicBlock *A,
   SmallVector<MachineOperand, 4> Cond;
   MF->getTarget().getInstrInfo()->InsertBranch(*NMBB, B, NULL, Cond);
 
-  LiveVariables *LV = getAnalysisIfAvailable<LiveVariables>();
-  if (LV)
-    LV->addNewBlock(NMBB, B);
+  if (LiveVariables *LV = getAnalysisIfAvailable<LiveVariables>())
+    LV->addNewBlock(NMBB, A);
 
   // Fix PHI nodes in B so they refer to NMBB instead of A
   for (MachineBasicBlock::iterator i = B->begin(), e = B->end();
        i != e && i->getOpcode() == TargetInstrInfo::PHI; ++i)
     for (unsigned ni = 1, ne = i->getNumOperands(); ni != ne; ni += 2)
-      if (i->getOperand(ni+1).getMBB() == A) {
+      if (i->getOperand(ni+1).getMBB() == A)
         i->getOperand(ni+1).setMBB(NMBB);
-        // Mark PHI sources as passing live through NMBB
-        if (LV)
-          LV->getVarInfo(i->getOperand(ni).getReg()).AliveBlocks.set(NewNum);
-      }
   return NMBB;
 }
-
-
diff --git a/lib/CodeGen/PHIElimination.h b/lib/CodeGen/PHIElimination.h
index 8188440c89..edc2d36670 100644
--- a/lib/CodeGen/PHIElimination.h
+++ b/lib/CodeGen/PHIElimination.h
@@ -90,7 +90,7 @@ namespace llvm {
     void analyzePHINodes(const MachineFunction& Fn);
 
     /// Split critical edges where necessary for good coalescer performance.
-    void SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB);
+    bool SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB);
 
     /// isLiveOut - Determine if Reg is live out from MBB, when not
     /// considering PHI nodes. This means that Reg is either killed by
@@ -98,6 +98,12 @@ namespace llvm {
     bool isLiveOut(unsigned Reg, const MachineBasicBlock &MBB,
                    LiveVariables &LV);
 
+    /// isLiveIn - Determine if Reg is live in to MBB, not considering PHI
+    /// source registers. This means that Reg is either killed by MBB or passes
+    /// through it.
+    bool isLiveIn(unsigned Reg, const MachineBasicBlock &MBB,
+                  LiveVariables &LV);
+
     /// SplitCriticalEdge - Split a critical edge from A to B by
     /// inserting a new MBB. Update branches in A and PHI instructions
     /// in B. Return the new block.