Compute critical loop predecessors in the same way as critical loop exits.

Critical edges going into a loop are not as bad as critical exits. We can handle
them by splitting the critical edge, or by having both inside and outside
registers live out of the predecessor.

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

2 files changed, 38 insertions, 1 deletions

diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp
index 9307286..cf29756 100644
--- a/lib/CodeGen/SplitKit.cpp
+++ b/lib/CodeGen/SplitKit.cpp
@@ -155,7 +155,7 @@ void SplitAnalysis::getCriticalExits(const SplitAnalysis::LoopBlocks &Blocks,
                                      BlockPtrSet &CriticalExits) {
   CriticalExits.clear();
 
-  // A critical exit block has curli line-in, and has a predecessor that is not
+  // A critical exit block has curli live-in, and has a predecessor that is not
   // in the loop nor a loop predecessor. For such an exit block, the edges
   // carrying the new variable must be moved to a new pre-exit block.
   for (BlockPtrSet::iterator I = Blocks.Exits.begin(), E = Blocks.Exits.end();
@@ -181,6 +181,38 @@ void SplitAnalysis::getCriticalExits(const SplitAnalysis::LoopBlocks &Blocks,
   }
 }
 
+void SplitAnalysis::getCriticalPreds(const SplitAnalysis::LoopBlocks &Blocks,
+                                     BlockPtrSet &CriticalPreds) {
+  CriticalPreds.clear();
+
+  // A critical predecessor block has curli live-out, and has a successor that
+  // has curli live-in and is not in the loop nor a loop exit block. For such a
+  // predecessor block, we must carry the value in both the 'inside' and
+  // 'outside' registers.
+  for (BlockPtrSet::iterator I = Blocks.Preds.begin(), E = Blocks.Preds.end();
+       I != E; ++I) {
+    const MachineBasicBlock *Pred = *I;
+    // Definitely not a critical edge.
+    if (Pred->succ_size() == 1)
+      continue;
+    // This block may not have curli live out at all if there is a PHI.
+    if (!lis_.isLiveOutOfMBB(*curli_, Pred))
+      continue;
+    // Does this block have a successor outside the loop?
+    for (MachineBasicBlock::const_pred_iterator SI = Pred->succ_begin(),
+         SE = Pred->succ_end(); SI != SE; ++SI) {
+      const MachineBasicBlock *Succ = *SI;
+      if (Blocks.Loop.count(Succ) || Blocks.Exits.count(Succ))
+        continue;
+      if (!lis_.isLiveInToMBB(*curli_, Succ))
+        continue;
+      // This is a critical predecessor block.
+      CriticalPreds.insert(Pred);
+      break;
+    }
+  }
+}
+
 /// canSplitCriticalExits - Return true if it is possible to insert new exit
 /// blocks before the blocks in CriticalExits.
 bool
diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h
index d9f16dc..08fac7f 100644
--- a/lib/CodeGen/SplitKit.h
+++ b/lib/CodeGen/SplitKit.h
@@ -122,6 +122,11 @@ public:
   bool canSplitCriticalExits(const LoopBlocks &Blocks,
                              BlockPtrSet &CriticalExits);
 
+  /// getCriticalPreds - Get the set of loop predecessors with critical edges to
+  /// blocks outside the loop that have curli live in. We don't have to break
+  /// these edges, but they do require special treatment.
+  void getCriticalPreds(const LoopBlocks &Blocks, BlockPtrSet &CriticalPreds);
+
   /// getBestSplitLoop - Return the loop where curli may best be split to a
   /// separate register, or NULL.
   const MachineLoop *getBestSplitLoop();