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 #include "llvm/ADT/SmallPtrSet.h"
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/CodeGen/SlotIndexes.h"
25 class MachineLoopInfo;
26 class MachineRegisterInfo;
27 class TargetInstrInfo;
31 /// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting
35 const MachineFunction &mf_;
36 const LiveIntervals &lis_;
37 const MachineLoopInfo &loops_;
38 const TargetInstrInfo &tii_;
40 // Instructions using the the current register.
41 typedef SmallPtrSet<const MachineInstr*, 16> InstrPtrSet;
42 InstrPtrSet usingInstrs_;
44 // The number of instructions using curli in each basic block.
45 typedef DenseMap<const MachineBasicBlock*, unsigned> BlockCountMap;
46 BlockCountMap usingBlocks_;
48 // The number of basic block using curli in each loop.
49 typedef DenseMap<const MachineLoop*, unsigned> LoopCountMap;
50 LoopCountMap usingLoops_;
53 // Current live interval.
54 const LiveInterval *curli_;
56 // Sumarize statistics by counting instructions using curli_.
59 /// canAnalyzeBranch - Return true if MBB ends in a branch that can be
61 bool canAnalyzeBranch(const MachineBasicBlock *MBB);
64 SplitAnalysis(const MachineFunction &mf, const LiveIntervals &lis,
65 const MachineLoopInfo &mli);
67 /// analyze - set curli to the specified interval, and analyze how it may be
69 void analyze(const LiveInterval *li);
71 /// removeUse - Update statistics by noting that mi no longer uses curli.
72 void removeUse(const MachineInstr *mi);
74 const LiveInterval *getCurLI() { return curli_; }
76 /// clear - clear all data structures so SplitAnalysis is ready to analyze a
80 typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet;
81 typedef SmallPtrSet<const MachineLoop*, 16> LoopPtrSet;
83 // Sets of basic blocks surrounding a machine loop.
85 BlockPtrSet Loop; // Blocks in the loop.
86 BlockPtrSet Preds; // Loop predecessor blocks.
87 BlockPtrSet Exits; // Loop exit blocks.
96 // Calculate the block sets surrounding the loop.
97 void getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks);
99 /// LoopPeripheralUse - how is a variable used in and around a loop?
100 /// Peripheral blocks are the loop predecessors and exit blocks.
101 enum LoopPeripheralUse {
102 ContainedInLoop, // All uses are inside the loop.
103 SinglePeripheral, // At most one instruction per peripheral block.
104 MultiPeripheral, // Multiple instructions in some peripheral blocks.
105 OutsideLoop // Uses outside loop periphery.
108 /// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in
109 /// and around the Loop.
110 LoopPeripheralUse analyzeLoopPeripheralUse(const LoopBlocks&);
112 /// getCriticalExits - It may be necessary to partially break critical edges
113 /// leaving the loop if an exit block has phi uses of curli. Collect the exit
114 /// blocks that need special treatment into CriticalExits.
115 void getCriticalExits(const LoopBlocks &Blocks, BlockPtrSet &CriticalExits);
117 /// canSplitCriticalExits - Return true if it is possible to insert new exit
118 /// blocks before the blocks in CriticalExits.
119 bool canSplitCriticalExits(const LoopBlocks &Blocks,
120 BlockPtrSet &CriticalExits);
122 /// getBestSplitLoop - Return the loop where curli may best be split to a
123 /// separate register, or NULL.
124 const MachineLoop *getBestSplitLoop();
126 /// getMultiUseBlocks - Add basic blocks to Blocks that may benefit from
127 /// having curli split to a new live interval. Return true if Blocks can be
128 /// passed to SplitEditor::splitSingleBlocks.
129 bool getMultiUseBlocks(BlockPtrSet &Blocks);
131 /// getBlockForInsideSplit - If curli is contained inside a single basic block,
132 /// and it wou pay to subdivide the interval inside that block, return it.
133 /// Otherwise return NULL. The returned block can be passed to
134 /// SplitEditor::splitInsideBlock.
135 const MachineBasicBlock *getBlockForInsideSplit();
139 /// LiveIntervalMap - Map values from a large LiveInterval into a small
140 /// interval that is a subset. Insert phi-def values as needed. This class is
141 /// used by SplitEditor to create new smaller LiveIntervals.
143 /// parentli_ is the larger interval, li_ is the subset interval. Every value
144 /// in li_ corresponds to exactly one value in parentli_, and the live range
145 /// of the value is contained within the live range of the parentli_ value.
146 /// Values in parentli_ may map to any number of openli_ values, including 0.
147 class LiveIntervalMap {
150 // The parent interval is never changed.
151 const LiveInterval &parentli_;
153 // The child interval's values are fully contained inside parentli_ values.
156 typedef DenseMap<const VNInfo*, VNInfo*> ValueMap;
158 // Map parentli_ values to simple values in li_ that are defined at the same
159 // SlotIndex, or NULL for parentli_ values that have complex li_ defs.
160 // Note there is a difference between values mapping to NULL (complex), and
161 // values not present (unknown/unmapped).
164 // extendTo - Find the last li_ value defined in MBB at or before Idx. The
165 // parentli_ is assumed to be live at Idx. Extend the live range to Idx.
166 // Return the found VNInfo, or NULL.
167 VNInfo *extendTo(MachineBasicBlock *MBB, SlotIndex Idx);
169 // addSimpleRange - Add a simple range from parentli_ to li_.
170 // ParentVNI must be live in the [Start;End) interval.
171 void addSimpleRange(SlotIndex Start, SlotIndex End, const VNInfo *ParentVNI);
174 LiveIntervalMap(LiveIntervals &lis,
175 const LiveInterval &parentli)
176 : lis_(lis), parentli_(parentli), li_(0) {}
178 /// reset - clear all data structures and start a new live interval.
179 void reset(LiveInterval *);
181 /// getLI - return the current live interval.
182 LiveInterval *getLI() const { return li_; }
184 /// defValue - define a value in li_ from the parentli_ value VNI and Idx.
185 /// Idx does not have to be ParentVNI->def, but it must be contained within
186 /// ParentVNI's live range in parentli_.
187 /// Return the new li_ value.
188 VNInfo *defValue(const VNInfo *ParentVNI, SlotIndex Idx);
190 /// mapValue - map ParentVNI to the corresponding li_ value at Idx. It is
191 /// assumed that ParentVNI is live at Idx.
192 /// If ParentVNI has not been defined by defValue, it is assumed that
193 /// ParentVNI->def dominates Idx.
194 /// If ParentVNI has been defined by defValue one or more times, a value that
195 /// dominates Idx will be returned. This may require creating extra phi-def
196 /// values and adding live ranges to li_.
197 VNInfo *mapValue(const VNInfo *ParentVNI, SlotIndex Idx);
199 /// addRange - Add live ranges to li_ where [Start;End) intersects parentli_.
200 /// All needed values whose def is not inside [Start;End) must be defined
201 /// beforehand so mapValue will work.
202 void addRange(SlotIndex Start, SlotIndex End);
206 /// SplitEditor - Edit machine code and LiveIntervals for live range
209 /// - Create a SplitEditor from a SplitAnalysis.
210 /// - Start a new live interval with openIntv.
211 /// - Mark the places where the new interval is entered using enterIntv*
212 /// - Mark the ranges where the new interval is used with useIntv*
213 /// - Mark the places where the interval is exited with exitIntv*.
214 /// - Finish the current interval with closeIntv and repeat from 2.
215 /// - Rewrite instructions with rewrite().
221 MachineRegisterInfo &mri_;
222 const TargetInstrInfo &tii_;
224 /// curli_ - The immutable interval we are currently splitting.
225 const LiveInterval *const curli_;
227 /// dupli_ - Created as a copy of curli_, ranges are carved out as new
228 /// intervals get added through openIntv / closeIntv. This is used to avoid
230 LiveIntervalMap dupli_;
232 /// Currently open LiveInterval.
233 LiveIntervalMap openli_;
235 /// createInterval - Create a new virtual register and LiveInterval with same
236 /// register class and spill slot as curli.
237 LiveInterval *createInterval();
239 /// getDupLI - Ensure dupli is created and return it.
240 LiveInterval *getDupLI();
242 /// valueMap_ - Map values in cupli to values in openli. These are direct 1-1
243 /// mappings, and do not include values created by inserted copies.
244 DenseMap<const VNInfo*, VNInfo*> valueMap_;
246 /// mapValue - Return the openIntv value that corresponds to the given curli
248 VNInfo *mapValue(const VNInfo *curliVNI);
250 /// A dupli value is live through openIntv.
253 /// All the new intervals created for this split are added to intervals_.
254 SmallVectorImpl<LiveInterval*> &intervals_;
256 /// The index into intervals_ of the first interval we added. There may be
257 /// others from before we got it.
258 unsigned firstInterval;
260 /// Insert a COPY instruction curli -> li. Allocate a new value from li
261 /// defined by the COPY
262 VNInfo *insertCopy(LiveInterval &LI,
263 MachineBasicBlock &MBB,
264 MachineBasicBlock::iterator I);
267 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
268 /// Newly created intervals will be appended to newIntervals.
269 SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&,
270 SmallVectorImpl<LiveInterval*> &newIntervals);
272 /// getAnalysis - Get the corresponding analysis.
273 SplitAnalysis &getAnalysis() { return sa_; }
275 /// Create a new virtual register and live interval.
278 /// enterIntvBefore - Enter openli before the instruction at Idx. If curli is
279 /// not live before Idx, a COPY is not inserted.
280 void enterIntvBefore(SlotIndex Idx);
282 /// enterIntvAtEnd - Enter openli at the end of MBB.
283 /// PhiMBB is a successor inside openli where a PHI value is created.
284 /// Currently, all entries must share the same PhiMBB.
285 void enterIntvAtEnd(MachineBasicBlock &MBB, MachineBasicBlock &PhiMBB);
287 /// useIntv - indicate that all instructions in MBB should use openli.
288 void useIntv(const MachineBasicBlock &MBB);
290 /// useIntv - indicate that all instructions in range should use openli.
291 void useIntv(SlotIndex Start, SlotIndex End);
293 /// leaveIntvAfter - Leave openli after the instruction at Idx.
294 void leaveIntvAfter(SlotIndex Idx);
296 /// leaveIntvAtTop - Leave the interval at the top of MBB.
297 /// Currently, only one value can leave the interval.
298 void leaveIntvAtTop(MachineBasicBlock &MBB);
300 /// closeIntv - Indicate that we are done editing the currently open
301 /// LiveInterval, and ranges can be trimmed.
304 /// rewrite - after all the new live ranges have been created, rewrite
305 /// instructions using curli to use the new intervals.
306 /// Return true if curli has been completely replaced, false if curli is still
307 /// intact, and needs to be spilled or split further.
310 // ===--- High level methods ---===
312 /// splitAroundLoop - Split curli into a separate live interval inside
313 /// the loop. Return true if curli has been completely replaced, false if
314 /// curli is still intact, and needs to be spilled or split further.
315 bool splitAroundLoop(const MachineLoop*);
317 /// splitSingleBlocks - Split curli into a separate live interval inside each
318 /// basic block in Blocks. Return true if curli has been completely replaced,
319 /// false if curli is still intact, and needs to be spilled or split further.
320 bool splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks);
322 /// splitInsideBlock - Split curli into multiple intervals inside MBB. Return
323 /// true if curli has been completely replaced, false if curli is still
324 /// intact, and needs to be spilled or split further.
325 bool splitInsideBlock(const MachineBasicBlock *);