Compute critical loop predecessors in the same way as critical loop exits.
authorJakob Stoklund Olesen <stoklund@2pi.dk>
Wed, 27 Oct 2010 00:39:05 +0000 (00:39 +0000)
committerJakob Stoklund Olesen <stoklund@2pi.dk>
Wed, 27 Oct 2010 00:39:05 +0000 (00:39 +0000)
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

lib/CodeGen/SplitKit.cpp
lib/CodeGen/SplitKit.h

index 9307286a610f4f7b5d3a95f04087ab1742865ff0..cf297568f6d1431dd9fed34164b8d9dbfa978833 100644 (file)
@@ -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
index d9f16dc9155beef7448807b1d06afb5ec0e31e98..08fac7f451de436276c08ab47bd82ccdc93d19ec 100644 (file)
@@ -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();