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 
279