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/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"
30 AllowSplit("spiller-splits-edges",
31 cl::desc("Allow critical edge splitting during spilling"));
33 //===----------------------------------------------------------------------===//
35 //===----------------------------------------------------------------------===//
37 SplitAnalysis::SplitAnalysis(const MachineFunction *mf,
38 const LiveIntervals *lis,
39 const MachineLoopInfo *mli)
43 tii_(*mf->getTarget().getInstrInfo()),
46 void SplitAnalysis::clear() {
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);
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))
65 MachineBasicBlock *MBB = MI->getParent();
66 if (usingBlocks_[MBB]++)
68 if (MachineLoop *Loop = loops_.getLoopFor(MBB))
69 usingLoops_.insert(Loop);
71 DEBUG(dbgs() << "Counted "
72 << usingInstrs_.size() << " instrs, "
73 << usingBlocks_.size() << " blocks, "
74 << usingLoops_.size() << " loops in "
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) {
83 // Blocks in the loop.
84 Blocks.Loop.insert(Loop->block_begin(), Loop->block_end());
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);
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);
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();
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;
119 // Is it a loop block?
120 if (Blocks.Loop.count(MBB))
122 // It must be an unrelated block.
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();
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();
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.
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)
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))
158 // This is a critical exit block, and we need to split the exit edge.
159 CriticalExits.insert(Succ);
165 /// canSplitCriticalExits - Return true if it is possible to insert new exit
166 /// blocks before the blocks in CriticalExits.
168 SplitAnalysis::canSplitCriticalExits(const SplitAnalysis::LoopBlocks &Blocks,
169 BlockPtrSet &CriticalExits) {
170 // If we don't allow critical edge splitting, require no critical exits.
172 return CriticalExits.empty();
174 for (BlockPtrSet::iterator I = CriticalExits.begin(), E = CriticalExits.end();
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))
186 if (!canAnalyzeBranch(Pred))
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())
195 if (!canAnalyzeBranch(--MFI))
198 // No problems found.
202 void SplitAnalysis::analyze(const LiveInterval *li) {
208 const MachineLoop *SplitAnalysis::getBestSplitLoop() {
209 assert(curli_ && "Call analyze() before getBestSplitLoop");
210 if (usingLoops_.empty())
213 LoopPtrSet Loops, SecondLoops;
215 BlockPtrSet CriticalExits;
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);
223 switch(analyzeLoopPeripheralUse(Blocks)) {
227 case MultiPeripheral:
230 case ContainedInLoop:
231 DEBUG(dbgs() << "ContainedInLoop: " << **I);
233 case SinglePeripheral:
234 DEBUG(dbgs() << "SinglePeripheral: " << **I);
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))
242 // This is a possible split.
247 DEBUG(dbgs() << "Got " << Loops.size() << " + " << SecondLoops.size()
248 << " candidate loops\n");
250 // If there are no first class loops available, look at second class loops.
257 // Pick the earliest loop.
258 // FIXME: Are there other heuristics to consider?
259 const MachineLoop *Best = 0;
261 for (LoopPtrSet::const_iterator I = Loops.begin(), E = Loops.end(); I != E;
263 SlotIndex Idx = lis_.getMBBStartIdx((*I)->getHeader());
264 if (!Best || Idx < BestIdx)
265 Best = *I, BestIdx = Idx;
267 DEBUG(dbgs() << "Best: " << *Best);
271 //===----------------------------------------------------------------------===//
273 //===----------------------------------------------------------------------===//
275 bool llvm::splitAroundLoop(SplitAnalysis &sa, const MachineLoop *loop) {