Implement loop splitting analysis.

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

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

3 files changed, 189 insertions, 19 deletions

diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h
index b101f32..5dfdc25 100644
--- a/include/llvm/Analysis/LoopInfo.h
+++ b/include/llvm/Analysis/LoopInfo.h
@@ -509,6 +509,12 @@ protected:
   }
 };
 
+template<class BlockT, class LoopT>
+raw_ostream& operator<<(raw_ostream &OS, const LoopBase<BlockT, LoopT> &Loop) {
+  Loop.print(OS);
+  return OS;
+}
+
 class Loop : public LoopBase<BasicBlock, Loop> {
 public:
   Loop() {}
diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp
index b62fabc..897b2a4 100644
--- a/lib/CodeGen/SplitKit.cpp
+++ b/lib/CodeGen/SplitKit.cpp
@@ -18,11 +18,17 @@
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetMachine.h"
 
 using namespace llvm;
 
+static cl::opt<bool>
+AllowSplit("spiller-splits-edges",
+           cl::desc("Allow critical edge splitting during spilling"));
 
 //===----------------------------------------------------------------------===//
 //                                 Split Analysis
@@ -34,6 +40,7 @@ SplitAnalysis::SplitAnalysis(const MachineFunction *mf,
   : mf_(*mf),
     lis_(*lis),
     loops_(*mli),
+    tii_(*mf->getTarget().getInstrInfo()),
     curli_(0) {}
 
 void SplitAnalysis::clear() {
@@ -42,6 +49,12 @@ void SplitAnalysis::clear() {
   usingLoops_.clear();
 }
 
+bool SplitAnalysis::canAnalyzeBranch(const MachineBasicBlock *MBB) {
+  MachineBasicBlock *T, *F;
+  SmallVector<MachineOperand, 4> Cond;
+  return !tii_.AnalyzeBranch(const_cast<MachineBasicBlock&>(*MBB), T, F, Cond);
+}
+
 /// analyzeUses - Count instructions, basic blocks, and loops using curli.
 void SplitAnalysis::analyzeUses() {
   const MachineRegisterInfo &MRI = mf_.getRegInfo();
@@ -62,29 +75,49 @@ void SplitAnalysis::analyzeUses() {
                << *curli_ << "\n");
 }
 
-SplitAnalysis::LoopPeripheralUse
-SplitAnalysis::analyzeLoopPeripheralUse(const MachineLoop *Loop) {
-  // Peripheral blocks.
-  SmallVector<MachineBasicBlock*, 16> Peri;
-  Loop->getExitBlocks(Peri);
-  if (MachineBasicBlock *PredBB = Loop->getLoopPredecessor())
-    Peri.push_back(PredBB);
-  array_pod_sort(Peri.begin(), Peri.end());
-  Peri.erase(std::unique(Peri.begin(), Peri.end()), Peri.end());
+// Get three sets of basic blocks surrounding a loop: Blocks inside the loop,
+// predecessor blocks, and exit blocks.
+void SplitAnalysis::getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks) {
+  Blocks.clear();
+
+  // Blocks in the loop.
+  Blocks.Loop.insert(Loop->block_begin(), Loop->block_end());
+
+  // Predecessor blocks.
+  const MachineBasicBlock *Header = Loop->getHeader();
+  for (MachineBasicBlock::const_pred_iterator I = Header->pred_begin(),
+       E = Header->pred_end(); I != E; ++I)
+    if (!Blocks.Loop.count(*I))
+      Blocks.Preds.insert(*I);
 
+  // Exit blocks.
+  for (MachineLoop::block_iterator I = Loop->block_begin(),
+       E = Loop->block_end(); I != E; ++I) {
+    const MachineBasicBlock *MBB = *I;
+    for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(),
+       SE = MBB->succ_end(); SI != SE; ++SI)
+      if (!Blocks.Loop.count(*SI))
+        Blocks.Exits.insert(*SI);
+  }
+}
+
+/// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in
+/// and around the Loop.
+SplitAnalysis::LoopPeripheralUse SplitAnalysis::
+analyzeLoopPeripheralUse(const SplitAnalysis::LoopBlocks &Blocks) {
   LoopPeripheralUse use = ContainedInLoop;
   for (BlockCountMap::iterator I = usingBlocks_.begin(), E = usingBlocks_.end();
        I != E; ++I) {
     const MachineBasicBlock *MBB = I->first;
     // Is this a peripheral block?
     if (use < MultiPeripheral &&
-        std::binary_search(Peri.begin(), Peri.end(), MBB)) {
+        (Blocks.Preds.count(MBB) || Blocks.Exits.count(MBB))) {
       if (I->second > 1) use = MultiPeripheral;
       else               use = SinglePeripheral;
       continue;
     }
     // Is it a loop block?
-    if (Loop->contains(MBB))
+    if (Blocks.Loop.count(MBB))
       continue;
     // It must be an unrelated block.
     return OutsideLoop;
@@ -92,6 +125,80 @@ SplitAnalysis::analyzeLoopPeripheralUse(const MachineLoop *Loop) {
   return use;
 }
 
+/// 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 SplitAnalysis::getCriticalExits(const SplitAnalysis::LoopBlocks &Blocks,
+                                     BlockPtrSet &CriticalExits) {
+  CriticalExits.clear();
+
+  // A critical exit block contains a phi def of curli, 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();
+       I != E; ++I) {
+    const MachineBasicBlock *Succ = *I;
+    SlotIndex SuccIdx = lis_.getMBBStartIdx(Succ);
+    VNInfo *SuccVNI = curli_->getVNInfoAt(SuccIdx);
+    // This exit may not have curli live in at all. No need to split.
+    if (!SuccVNI)
+      continue;
+    // If this is not a PHI def, it is either using a value from before the
+    // loop, or a value defined inside the loop. Both are safe.
+    if (!SuccVNI->isPHIDef() || SuccVNI->def.getBaseIndex() != SuccIdx)
+      continue;
+    // This exit block does have a PHI. Does it also have a predecessor that is
+    // not a loop block or loop predecessor?
+    for (MachineBasicBlock::const_pred_iterator PI = Succ->pred_begin(),
+         PE = Succ->pred_end(); PI != PE; ++PI) {
+      const MachineBasicBlock *Pred = *PI;
+      if (Blocks.Loop.count(Pred) || Blocks.Preds.count(Pred))
+        continue;
+      // This is a critical exit block, and we need to split the exit edge.
+      CriticalExits.insert(Succ);
+      break;
+    }
+  }
+}
+
+/// canSplitCriticalExits - Return true if it is possible to insert new exit
+/// blocks before the blocks in CriticalExits.
+bool
+SplitAnalysis::canSplitCriticalExits(const SplitAnalysis::LoopBlocks &Blocks,
+                                     BlockPtrSet &CriticalExits) {
+  // If we don't allow critical edge splitting, require no critical exits.
+  if (!AllowSplit)
+    return CriticalExits.empty();
+
+  for (BlockPtrSet::iterator I = CriticalExits.begin(), E = CriticalExits.end();
+       I != E; ++I) {
+    const MachineBasicBlock *Succ = *I;
+    // We want to insert a new pre-exit MBB before Succ, and change all the
+    // in-loop blocks to branch to the pre-exit instead of Succ.
+    // Check that all the in-loop predecessors can be changed.
+    for (MachineBasicBlock::const_pred_iterator PI = Succ->pred_begin(),
+         PE = Succ->pred_end(); PI != PE; ++PI) {
+      const MachineBasicBlock *Pred = *PI;
+      // The external predecessors won't be altered.
+      if (!Blocks.Loop.count(Pred) && !Blocks.Preds.count(Pred))
+        continue;
+      if (!canAnalyzeBranch(Pred))
+        return false;
+    }
+
+    // If Succ's layout predecessor falls through, that too must be analyzable.
+    // We need to insert the pre-exit block in the gap.
+    MachineFunction::const_iterator MFI = Succ;
+    if (MFI == mf_.begin())
+      continue;
+    if (!canAnalyzeBranch(--MFI))
+      return false;
+  }
+  // No problems found.
+  return true;
+}
+
 void SplitAnalysis::analyze(const LiveInterval *li) {
   clear();
   curli_ = li;
@@ -99,22 +206,46 @@ void SplitAnalysis::analyze(const LiveInterval *li) {
 }
 
 const MachineLoop *SplitAnalysis::getBestSplitLoop() {
+  assert(curli_ && "Call analyze() before getBestSplitLoop");
+  if (usingLoops_.empty())
+    return 0;
+
   LoopPtrSet Loops, SecondLoops;
+  LoopBlocks Blocks;
+  BlockPtrSet CriticalExits;
 
   // Find first-class and second class candidate loops.
   // We prefer to split around loops where curli is used outside the periphery.
   for (LoopPtrSet::const_iterator I = usingLoops_.begin(),
-       E = usingLoops_.end(); I != E; ++I)
-    switch(analyzeLoopPeripheralUse(*I)) {
+       E = usingLoops_.end(); I != E; ++I) {
+    getLoopBlocks(*I, Blocks);
+    LoopPtrSet *LPS = 0;
+    switch(analyzeLoopPeripheralUse(Blocks)) {
     case OutsideLoop:
-      Loops.insert(*I);
+      LPS = &Loops;
       break;
     case MultiPeripheral:
-      SecondLoops.insert(*I);
+      LPS = &SecondLoops;
       break;
-    default:
+    case ContainedInLoop:
+      DEBUG(dbgs() << "ContainedInLoop: " << **I);
+      continue;
+    case SinglePeripheral:
+      DEBUG(dbgs() << "SinglePeripheral: " << **I);
       continue;
     }
+    // Will it be possible to split around this loop?
+    getCriticalExits(Blocks, CriticalExits);
+    DEBUG(dbgs() << CriticalExits.size() << " critical exits: " << **I);
+    if (!canSplitCriticalExits(Blocks, CriticalExits))
+      continue;
+    // This is a possible split.
+    assert(LPS);
+    LPS->insert(*I);
+  }
+
+  DEBUG(dbgs() << "Got " << Loops.size() << " + " << SecondLoops.size()
+               << " candidate loops\n");
 
   // If there are no first class loops available, look at second class loops.
   if (Loops.empty())
@@ -125,8 +256,6 @@ const MachineLoop *SplitAnalysis::getBestSplitLoop() {
 
   // Pick the earliest loop.
   // FIXME: Are there other heuristics to consider?
-  // - avoid breaking critical edges.
-  // - avoid impossible loops.
   const MachineLoop *Best = 0;
   SlotIndex BestIdx;
   for (LoopPtrSet::const_iterator I = Loops.begin(), E = Loops.end(); I != E;
@@ -135,6 +264,7 @@ const MachineLoop *SplitAnalysis::getBestSplitLoop() {
     if (!Best || Idx < BestIdx)
       Best = *I, BestIdx = Idx;
   }
+  DEBUG(dbgs() << "Best: " << *Best);
   return Best;
 }
 
diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h
index 3d76772..d567c04 100644
--- a/lib/CodeGen/SplitKit.h
+++ b/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.