lib/CodeGen/SplitKit.cpp

   1 //===---------- SplitKit.cpp - Toolkit for splitting live ranges ----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file contains the SplitAnalysis class as well as mutator functions for
  11 // live range splitting.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "splitter"
  16 #include "SplitKit.h"
  17 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  18 #include "llvm/CodeGen/MachineFunctionPass.h"
  19 #include "llvm/CodeGen/MachineLoopInfo.h"
  20 #include "llvm/CodeGen/MachineRegisterInfo.h"
  21 #include "llvm/Support/CommandLine.h"
  22 #include "llvm/Support/Debug.h"
  23 #include "llvm/Support/raw_ostream.h"
  24 #include "llvm/Target/TargetInstrInfo.h"
  25 #include "llvm/Target/TargetMachine.h"
  26
  27 using namespace llvm;
  28
  29 static cl::opt<bool>
  30 AllowSplit("spiller-splits-edges",
  31            cl::desc("Allow critical edge splitting during spilling"));
  32
  33 //===----------------------------------------------------------------------===//
  34 //                                 Split Analysis
  35 //===----------------------------------------------------------------------===//
  36
  37 SplitAnalysis::SplitAnalysis(const MachineFunction &mf,
  38                              const LiveIntervals &lis,
  39                              const MachineLoopInfo &mli)
  40   : mf_(mf),
  41     lis_(lis),
  42     loops_(mli),
  43     tii_(*mf.getTarget().getInstrInfo()),
  44     curli_(0) {}
  45
  46 void SplitAnalysis::clear() {
  47   usingInstrs_.clear();
  48   usingBlocks_.clear();
  49   usingLoops_.clear();
  50 }
  51
  52 bool SplitAnalysis::canAnalyzeBranch(const MachineBasicBlock *MBB) {
  53   MachineBasicBlock *T, *F;
  54   SmallVector<MachineOperand, 4> Cond;
  55   return !tii_.AnalyzeBranch(const_cast<MachineBasicBlock&>(*MBB), T, F, Cond);
  56 }
  57
  58 /// analyzeUses - Count instructions, basic blocks, and loops using curli.
  59 void SplitAnalysis::analyzeUses() {
  60   const MachineRegisterInfo &MRI = mf_.getRegInfo();
  61   for (MachineRegisterInfo::reg_iterator I = MRI.reg_begin(curli_->reg);
  62        MachineInstr *MI = I.skipInstruction();) {
  63     if (MI->isDebugValue() || !usingInstrs_.insert(MI))
  64       continue;
  65     MachineBasicBlock *MBB = MI->getParent();
  66     if (usingBlocks_[MBB]++)
  67       continue;
  68     if (MachineLoop *Loop = loops_.getLoopFor(MBB))
  69       usingLoops_.insert(Loop);
  70   }
  71   DEBUG(dbgs() << "Counted "
  72                << usingInstrs_.size() << " instrs, "
  73                << usingBlocks_.size() << " blocks, "
  74                << usingLoops_.size()  << " loops in "
  75                << *curli_ << "\n");
  76 }
  77
  78 // Get three sets of basic blocks surrounding a loop: Blocks inside the loop,
  79 // predecessor blocks, and exit blocks.
  80 void SplitAnalysis::getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks) {
  81   Blocks.clear();
  82
  83   // Blocks in the loop.
  84   Blocks.Loop.insert(Loop->block_begin(), Loop->block_end());
  85
  86   // Predecessor blocks.
  87   const MachineBasicBlock *Header = Loop->getHeader();
  88   for (MachineBasicBlock::const_pred_iterator I = Header->pred_begin(),
  89        E = Header->pred_end(); I != E; ++I)
  90     if (!Blocks.Loop.count(*I))
  91       Blocks.Preds.insert(*I);
  92
  93   // Exit blocks.
  94   for (MachineLoop::block_iterator I = Loop->block_begin(),
  95        E = Loop->block_end(); I != E; ++I) {
  96     const MachineBasicBlock *MBB = *I;
  97     for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(),
  98        SE = MBB->succ_end(); SI != SE; ++SI)
  99       if (!Blocks.Loop.count(*SI))
 100         Blocks.Exits.insert(*SI);
 101   }
 102 }
 103
 104 /// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in
 105 /// and around the Loop.
 106 SplitAnalysis::LoopPeripheralUse SplitAnalysis::
 107 analyzeLoopPeripheralUse(const SplitAnalysis::LoopBlocks &Blocks) {
 108   LoopPeripheralUse use = ContainedInLoop;
 109   for (BlockCountMap::iterator I = usingBlocks_.begin(), E = usingBlocks_.end();
 110        I != E; ++I) {
 111     const MachineBasicBlock *MBB = I->first;
 112     // Is this a peripheral block?
 113     if (use < MultiPeripheral &&
 114         (Blocks.Preds.count(MBB) || Blocks.Exits.count(MBB))) {
 115       if (I->second > 1) use = MultiPeripheral;
 116       else               use = SinglePeripheral;
 117       continue;
 118     }
 119     // Is it a loop block?
 120     if (Blocks.Loop.count(MBB))
 121       continue;
 122     // It must be an unrelated block.
 123     return OutsideLoop;
 124   }
 125   return use;
 126 }
 127
 128 /// getCriticalExits - It may be necessary to partially break critical edges
 129 /// leaving the loop if an exit block has phi uses of curli. Collect the exit
 130 /// blocks that need special treatment into CriticalExits.
 131 void SplitAnalysis::getCriticalExits(const SplitAnalysis::LoopBlocks &Blocks,
 132                                      BlockPtrSet &CriticalExits) {
 133   CriticalExits.clear();
 134
 135   // A critical exit block contains a phi def of curli, and has a predecessor
 136   // that is not in the loop nor a loop predecessor.
 137   // For such an exit block, the edges carrying the new variable must be moved
 138   // to a new pre-exit block.
 139   for (BlockPtrSet::iterator I = Blocks.Exits.begin(), E = Blocks.Exits.end();
 140        I != E; ++I) {
 141     const MachineBasicBlock *Succ = *I;
 142     SlotIndex SuccIdx = lis_.getMBBStartIdx(Succ);
 143     VNInfo *SuccVNI = curli_->getVNInfoAt(SuccIdx);
 144     // This exit may not have curli live in at all. No need to split.
 145     if (!SuccVNI)
 146       continue;
 147     // If this is not a PHI def, it is either using a value from before the
 148     // loop, or a value defined inside the loop. Both are safe.
 149     if (!SuccVNI->isPHIDef() || SuccVNI->def.getBaseIndex() != SuccIdx)
 150       continue;
 151     // This exit block does have a PHI. Does it also have a predecessor that is
 152     // not a loop block or loop predecessor?
 153     for (MachineBasicBlock::const_pred_iterator PI = Succ->pred_begin(),
 154          PE = Succ->pred_end(); PI != PE; ++PI) {
 155       const MachineBasicBlock *Pred = *PI;
 156       if (Blocks.Loop.count(Pred) || Blocks.Preds.count(Pred))
 157         continue;
 158       // This is a critical exit block, and we need to split the exit edge.
 159       CriticalExits.insert(Succ);
 160       break;
 161     }
 162   }
 163 }
 164
 165 /// canSplitCriticalExits - Return true if it is possible to insert new exit
 166 /// blocks before the blocks in CriticalExits.
 167 bool
 168 SplitAnalysis::canSplitCriticalExits(const SplitAnalysis::LoopBlocks &Blocks,
 169                                      BlockPtrSet &CriticalExits) {
 170   // If we don't allow critical edge splitting, require no critical exits.
 171   if (!AllowSplit)
 172     return CriticalExits.empty();
 173
 174   for (BlockPtrSet::iterator I = CriticalExits.begin(), E = CriticalExits.end();
 175        I != E; ++I) {
 176     const MachineBasicBlock *Succ = *I;
 177     // We want to insert a new pre-exit MBB before Succ, and change all the
 178     // in-loop blocks to branch to the pre-exit instead of Succ.
 179     // Check that all the in-loop predecessors can be changed.
 180     for (MachineBasicBlock::const_pred_iterator PI = Succ->pred_begin(),
 181          PE = Succ->pred_end(); PI != PE; ++PI) {
 182       const MachineBasicBlock *Pred = *PI;
 183       // The external predecessors won't be altered.
 184       if (!Blocks.Loop.count(Pred) && !Blocks.Preds.count(Pred))
 185         continue;
 186       if (!canAnalyzeBranch(Pred))
 187         return false;
 188     }
 189
 190     // If Succ's layout predecessor falls through, that too must be analyzable.
 191     // We need to insert the pre-exit block in the gap.
 192     MachineFunction::const_iterator MFI = Succ;
 193     if (MFI == mf_.begin())
 194       continue;
 195     if (!canAnalyzeBranch(--MFI))
 196       return false;
 197   }
 198   // No problems found.
 199   return true;
 200 }
 201
 202 void SplitAnalysis::analyze(const LiveInterval *li) {
 203   clear();
 204   curli_ = li;
 205   analyzeUses();
 206 }
 207
 208 const MachineLoop *SplitAnalysis::getBestSplitLoop() {
 209   assert(curli_ && "Call analyze() before getBestSplitLoop");
 210   if (usingLoops_.empty())
 211     return 0;
 212
 213   LoopPtrSet Loops, SecondLoops;
 214   LoopBlocks Blocks;
 215   BlockPtrSet CriticalExits;
 216
 217   // Find first-class and second class candidate loops.
 218   // We prefer to split around loops where curli is used outside the periphery.
 219   for (LoopPtrSet::const_iterator I = usingLoops_.begin(),
 220        E = usingLoops_.end(); I != E; ++I) {
 221     getLoopBlocks(*I, Blocks);
 222     LoopPtrSet *LPS = 0;
 223     switch(analyzeLoopPeripheralUse(Blocks)) {
 224     case OutsideLoop:
 225       LPS = &Loops;
 226       break;
 227     case MultiPeripheral:
 228       LPS = &SecondLoops;
 229       break;
 230     case ContainedInLoop:
 231       DEBUG(dbgs() << "ContainedInLoop: " << **I);
 232       continue;
 233     case SinglePeripheral:
 234       DEBUG(dbgs() << "SinglePeripheral: " << **I);
 235       continue;
 236     }
 237     // Will it be possible to split around this loop?
 238     getCriticalExits(Blocks, CriticalExits);
 239     DEBUG(dbgs() << CriticalExits.size() << " critical exits: " << **I);
 240     if (!canSplitCriticalExits(Blocks, CriticalExits))
 241       continue;
 242     // This is a possible split.
 243     assert(LPS);
 244     LPS->insert(*I);
 245   }
 246
 247   DEBUG(dbgs() << "Got " << Loops.size() << " + " << SecondLoops.size()
 248                << " candidate loops\n");
 249
 250   // If there are no first class loops available, look at second class loops.
 251   if (Loops.empty())
 252     Loops = SecondLoops;
 253
 254   if (Loops.empty())
 255     return 0;
 256
 257   // Pick the earliest loop.
 258   // FIXME: Are there other heuristics to consider?
 259   const MachineLoop *Best = 0;
 260   SlotIndex BestIdx;
 261   for (LoopPtrSet::const_iterator I = Loops.begin(), E = Loops.end(); I != E;
 262        ++I) {
 263     SlotIndex Idx = lis_.getMBBStartIdx((*I)->getHeader());
 264     if (!Best || Idx < BestIdx)
 265       Best = *I, BestIdx = Idx;
 266   }
 267   DEBUG(dbgs() << "Best: " << *Best);
 268   return Best;
 269 }
 270
 271 //===----------------------------------------------------------------------===//
 272 //                               Loop Splitting
 273 //===----------------------------------------------------------------------===//
 274
 275 bool llvm::splitAroundLoop(SplitAnalysis &sa, const MachineLoop *loop) {
 276   return false;
 277 }
 278