1 //===---------- SplitKit.cpp - Toolkit for splitting live ranges ----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file contains the SplitAnalysis class as well as mutator functions for
11 // live range splitting.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "splitter"
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"
27 //===----------------------------------------------------------------------===//
29 //===----------------------------------------------------------------------===//
31 SplitAnalysis::SplitAnalysis(const MachineFunction *mf,
32 const LiveIntervals *lis,
33 const MachineLoopInfo *mli)
39 void SplitAnalysis::clear() {
45 /// analyseUses - Count instructions, basic blocks, and loops using curli.
46 void SplitAnalysis::analyseUses() {
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))
52 MachineBasicBlock *MBB = MI->getParent();
53 if (usingBlocks_[MBB]++)
55 if (MachineLoop *Loop = loops_.getLoopFor(MBB))
56 usingLoops_.insert(Loop);
58 DEBUG(dbgs() << "Counted "
59 << usingInstrs_.size() << " instrs, "
60 << usingBlocks_.size() << " blocks, "
61 << usingLoops_.size() << " loops in "
65 SplitAnalysis::LoopPeripheralUse
66 SplitAnalysis::analyzeLoopPeripheralUse(const MachineLoop *Loop) {
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());
75 LoopPeripheralUse use = ContainedInLoop;
76 for (BlockCountMap::iterator I = usingBlocks_.begin(), E = usingBlocks_.end();
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;
86 // Is it a loop block?
87 if (Loop->contains(MBB))
89 // It must be an unrelated block.
95 void SplitAnalysis::analyze(const LiveInterval *li) {
101 const MachineLoop *SplitAnalysis::getBestSplitLoop() {
102 LoopPtrSet Loops, SecondLoops;
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)) {
112 case MultiPeripheral:
113 SecondLoops.insert(*I);
119 // If there are no first class loops available, look at second class loops.
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;
132 for (LoopPtrSet::const_iterator I = Loops.begin(), E = Loops.end(); I != E;
134 SlotIndex Idx = lis_.getMBBStartIdx((*I)->getHeader());
135 if (!Best || Idx < BestIdx)
136 Best = *I, BestIdx = Idx;
141 //===----------------------------------------------------------------------===//
143 //===----------------------------------------------------------------------===//
145 bool llvm::splitAroundLoop(SplitAnalysis &sa, const MachineLoop *loop) {