Implement loop splitting analysis.

Determine which loop exit blocks need a 'pre-exit' block inserted.
Recognize when this would be impossible.

llvm-svn: 108941

1 files changed, 35 insertions, 1 deletions

diff --git a/llvm/lib/CodeGen/SplitKit.h b/llvm/lib/CodeGen/SplitKit.h
index 3d767720df0..d567c0420d9 100644
--- a/llvm/lib/CodeGen/SplitKit.h
+++ b/llvm/lib/CodeGen/SplitKit.h
@@ -25,11 +25,13 @@ class MachineFunction;
 class MachineFunctionPass;
 class MachineLoop;
 class MachineLoopInfo;
+class TargetInstrInfo;
 
 class SplitAnalysis {
   const MachineFunction &mf_;
   const LiveIntervals &lis_;
   const MachineLoopInfo &loops_;
+  const TargetInstrInfo &tii_;
 
   // Current live interval.
   const LiveInterval *curli_;
@@ -49,6 +51,10 @@ class SplitAnalysis {
   // Sumarize statistics by counting instructions using curli_.
   void analyzeUses();
 
+  /// canAnalyzeBranch - Return true if MBB ends in a branch that can be
+  /// analyzed.
+  bool canAnalyzeBranch(const MachineBasicBlock *MBB);
+
 public:
   SplitAnalysis(const MachineFunction *mf, const LiveIntervals *lis,
                 const MachineLoopInfo *mli);
@@ -61,6 +67,24 @@ public:
   /// new interval.
   void clear();
 
+  typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet;
+
+  // Sets of basic blocks surrounding a machine loop.
+  struct LoopBlocks {
+    BlockPtrSet Loop;  // Blocks in the loop.
+    BlockPtrSet Preds; // Loop predecessor blocks.
+    BlockPtrSet Exits; // Loop exit blocks.
+
+    void clear() {
+      Loop.clear();
+      Preds.clear();
+      Exits.clear();
+    }
+  };
+
+  // Calculate the block sets surrounding the loop.
+  void getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks);
+
   /// LoopPeripheralUse - how is a variable used in and around a loop?
   /// Peripheral blocks are the loop predecessors and exit blocks.
   enum LoopPeripheralUse {
@@ -72,7 +96,17 @@ public:
 
   /// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in
   /// and around the Loop.
-  LoopPeripheralUse analyzeLoopPeripheralUse(const MachineLoop*);
+  LoopPeripheralUse analyzeLoopPeripheralUse(const LoopBlocks&);
+
+  /// getCriticalExits - It may be necessary to partially break critical edges
+  /// leaving the loop if an exit block has phi uses of curli. Collect the exit
+  /// blocks that need special treatment into CriticalExits.
+  void getCriticalExits(const LoopBlocks &Blocks, BlockPtrSet &CriticalExits);
+
+  /// canSplitCriticalExits - Return true if it is possible to insert new exit
+  /// blocks before the blocks in CriticalExits.
+  bool canSplitCriticalExits(const LoopBlocks &Blocks,
+                             BlockPtrSet &CriticalExits);
 
   /// getBestSplitLoop - Return the loop where curli may best be split to a
   /// separate register, or NULL.