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/Debug.h"
  22 #include "llvm/Support/raw_ostream.h"
  23
  24 using namespace llvm;
  25
  26
  27 //===----------------------------------------------------------------------===//
  28 //                                 Split Analysis
  29 //===----------------------------------------------------------------------===//
  30
  31 SplitAnalysis::SplitAnalysis(const MachineFunction *mf,
  32                              const LiveIntervals *lis,
  33                              const MachineLoopInfo *mli)
  34   : mf_(*mf),
  35     lis_(*lis),
  36     loops_(*mli),
  37     curli_(0) {}
  38
  39 void SplitAnalysis::clear() {
  40   usingInstrs_.clear();
  41   usingBlocks_.clear();
  42   usingLoops_.clear();
  43 }
  44
  45 /// analyzeUses - Count instructions, basic blocks, and loops using curli.
  46 void SplitAnalysis::analyzeUses() {
  47   const MachineRegisterInfo &MRI = mf_.getRegInfo();
  48   for (MachineRegisterInfo::reg_iterator I = MRI.reg_begin(curli_->reg);
  49        MachineInstr *MI = I.skipInstruction();) {
  50     if (MI->isDebugValue() || !usingInstrs_.insert(MI))
  51       continue;
  52     MachineBasicBlock *MBB = MI->getParent();
  53     if (usingBlocks_[MBB]++)
  54       continue;
  55     if (MachineLoop *Loop = loops_.getLoopFor(MBB))
  56       usingLoops_.insert(Loop);
  57   }
  58   DEBUG(dbgs() << "Counted "
  59                << usingInstrs_.size() << " instrs, "
  60                << usingBlocks_.size() << " blocks, "
  61                << usingLoops_.size()  << " loops in "
  62                << *curli_ << "\n");
  63 }
  64
  65 SplitAnalysis::LoopPeripheralUse
  66 SplitAnalysis::analyzeLoopPeripheralUse(const MachineLoop *Loop) {
  67   // Peripheral blocks.
  68   SmallVector<MachineBasicBlock*, 16> Peri;
  69   Loop->getExitBlocks(Peri);
  70   if (MachineBasicBlock *PredBB = Loop->getLoopPredecessor())
  71     Peri.push_back(PredBB);
  72   array_pod_sort(Peri.begin(), Peri.end());
  73   Peri.erase(std::unique(Peri.begin(), Peri.end()), Peri.end());
  74
  75   LoopPeripheralUse use = ContainedInLoop;
  76   for (BlockCountMap::iterator I = usingBlocks_.begin(), E = usingBlocks_.end();
  77        I != E; ++I) {
  78     const MachineBasicBlock *MBB = I->first;
  79     // Is this a peripheral block?
  80     if (use < MultiPeripheral &&
  81         std::binary_search(Peri.begin(), Peri.end(), MBB)) {
  82       if (I->second > 1) use = MultiPeripheral;
  83       else               use = SinglePeripheral;
  84       continue;
  85     }
  86     // Is it a loop block?
  87     if (Loop->contains(MBB))
  88       continue;
  89     // It must be an unrelated block.
  90     return OutsideLoop;
  91   }
  92   return use;
  93 }
  94
  95 void SplitAnalysis::analyze(const LiveInterval *li) {
  96   clear();
  97   curli_ = li;
  98   analyzeUses();
  99 }
 100
 101 const MachineLoop *SplitAnalysis::getBestSplitLoop() {
 102   LoopPtrSet Loops, SecondLoops;
 103
 104   // Find first-class and second class candidate loops.
 105   // We prefer to split around loops where curli is used outside the periphery.
 106   for (LoopPtrSet::const_iterator I = usingLoops_.begin(),
 107        E = usingLoops_.end(); I != E; ++I)
 108     switch(analyzeLoopPeripheralUse(*I)) {
 109     case OutsideLoop:
 110       Loops.insert(*I);
 111       break;
 112     case MultiPeripheral:
 113       SecondLoops.insert(*I);
 114       break;
 115     default:
 116       continue;
 117     }
 118
 119   // If there are no first class loops available, look at second class loops.
 120   if (Loops.empty())
 121     Loops = SecondLoops;
 122
 123   if (Loops.empty())
 124     return 0;
 125
 126   // Pick the earliest loop.
 127   // FIXME: Are there other heuristics to consider?
 128   // - avoid breaking critical edges.
 129   // - avoid impossible loops.
 130   const MachineLoop *Best = 0;
 131   SlotIndex BestIdx;
 132   for (LoopPtrSet::const_iterator I = Loops.begin(), E = Loops.end(); I != E;
 133        ++I) {
 134     SlotIndex Idx = lis_.getMBBStartIdx((*I)->getHeader());
 135     if (!Best || Idx < BestIdx)
 136       Best = *I, BestIdx = Idx;
 137   }
 138   return Best;
 139 }
 140
 141 //===----------------------------------------------------------------------===//
 142 //                               Loop Splitting
 143 //===----------------------------------------------------------------------===//
 144
 145 bool llvm::splitAroundLoop(SplitAnalysis &sa, const MachineLoop *loop) {
 146   return false;
 147 }
 148