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 // Loops where the curent interval is used.
49 typedef SmallPtrSet<const MachineLoop*, 16> LoopPtrSet;
50 LoopPtrSet 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 const LiveInterval *getCurLI() { return curli_; }
73 /// clear - clear all data structures so SplitAnalysis is ready to analyze a
77 typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet;
79 // Sets of basic blocks surrounding a machine loop.
81 BlockPtrSet Loop; // Blocks in the loop.
82 BlockPtrSet Preds; // Loop predecessor blocks.
83 BlockPtrSet Exits; // Loop exit blocks.
92 // Calculate the block sets surrounding the loop.
93 void getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks);
95 /// LoopPeripheralUse - how is a variable used in and around a loop?
96 /// Peripheral blocks are the loop predecessors and exit blocks.
97 enum LoopPeripheralUse {
98 ContainedInLoop, // All uses are inside the loop.
99 SinglePeripheral, // At most one instruction per peripheral block.
100 MultiPeripheral, // Multiple instructions in some peripheral blocks.
101 OutsideLoop // Uses outside loop periphery.
104 /// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in
105 /// and around the Loop.
106 LoopPeripheralUse analyzeLoopPeripheralUse(const LoopBlocks&);
108 /// getCriticalExits - It may be necessary to partially break critical edges
109 /// leaving the loop if an exit block has phi uses of curli. Collect the exit
110 /// blocks that need special treatment into CriticalExits.
111 void getCriticalExits(const LoopBlocks &Blocks, BlockPtrSet &CriticalExits);
113 /// canSplitCriticalExits - Return true if it is possible to insert new exit
114 /// blocks before the blocks in CriticalExits.
115 bool canSplitCriticalExits(const LoopBlocks &Blocks,
116 BlockPtrSet &CriticalExits);
118 /// getBestSplitLoop - Return the loop where curli may best be split to a
119 /// separate register, or NULL.
120 const MachineLoop *getBestSplitLoop();
122 /// getMultiUseBlocks - Add basic blocks to Blocks that may benefit from
123 /// having curli split to a new live interval. Return true if Blocks can be
124 /// passed to SplitEditor::splitSingleBlocks.
125 bool getMultiUseBlocks(BlockPtrSet &Blocks);
128 /// SplitEditor - Edit machine code and LiveIntervals for live range
131 /// - Create a SplitEditor from a SplitAnalysis.
132 /// - Start a new live interval with openIntv.
133 /// - Mark the places where the new interval is entered using enterIntv*
134 /// - Mark the ranges where the new interval is used with useIntv*
135 /// - Mark the places where the interval is exited with exitIntv*.
136 /// - Finish the current interval with closeIntv and repeat from 2.
137 /// - Rewrite instructions with rewrite().
143 MachineRegisterInfo &mri_;
144 const TargetInstrInfo &tii_;
146 /// curli_ - The immutable interval we are currently splitting.
147 const LiveInterval *const curli_;
149 /// dupli_ - Created as a copy of curli_, ranges are carved out as new
150 /// intervals get added through openIntv / closeIntv. This is used to avoid
152 LiveInterval *dupli_;
154 /// Currently open LiveInterval.
155 LiveInterval *openli_;
157 /// createInterval - Create a new virtual register and LiveInterval with same
158 /// register class and spill slot as curli.
159 LiveInterval *createInterval();
161 /// getDupLI - Ensure dupli is created and return it.
162 LiveInterval *getDupLI();
164 /// valueMap_ - Map values in cupli to values in openli. These are direct 1-1
165 /// mappings, and do not include values created by inserted copies.
166 DenseMap<const VNInfo*, VNInfo*> valueMap_;
168 /// mapValue - Return the openIntv value that corresponds to the given curli
170 VNInfo *mapValue(const VNInfo *curliVNI);
172 /// A dupli value is live through openIntv.
175 /// All the new intervals created for this split are added to intervals_.
176 std::vector<LiveInterval*> &intervals_;
178 /// The index into intervals_ of the first interval we added. There may be
179 /// others from before we got it.
180 unsigned firstInterval;
182 /// Insert a COPY instruction curli -> li. Allocate a new value from li
183 /// defined by the COPY
184 VNInfo *insertCopy(LiveInterval &LI,
185 MachineBasicBlock &MBB,
186 MachineBasicBlock::iterator I);
189 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
190 /// Newly created intervals will be appended to newIntervals.
191 SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&,
192 std::vector<LiveInterval*> &newIntervals);
194 /// getAnalysis - Get the corresponding analysis.
195 SplitAnalysis &getAnalysis() { return sa_; }
197 /// Create a new virtual register and live interval.
200 /// enterIntvBefore - Enter openli before the instruction at Idx. If curli is
201 /// not live before Idx, a COPY is not inserted.
202 void enterIntvBefore(SlotIndex Idx);
204 /// enterIntvAtEnd - Enter openli at the end of MBB.
205 /// PhiMBB is a successor inside openli where a PHI value is created.
206 /// Currently, all entries must share the same PhiMBB.
207 void enterIntvAtEnd(MachineBasicBlock &MBB, MachineBasicBlock &PhiMBB);
209 /// useIntv - indicate that all instructions in MBB should use openli.
210 void useIntv(const MachineBasicBlock &MBB);
212 /// useIntv - indicate that all instructions in range should use openli.
213 void useIntv(SlotIndex Start, SlotIndex End);
215 /// leaveIntvAfter - Leave openli after the instruction at Idx.
216 void leaveIntvAfter(SlotIndex Idx);
218 /// leaveIntvAtTop - Leave the interval at the top of MBB.
219 /// Currently, only one value can leave the interval.
220 void leaveIntvAtTop(MachineBasicBlock &MBB);
222 /// closeIntv - Indicate that we are done editing the currently open
223 /// LiveInterval, and ranges can be trimmed.
226 /// rewrite - after all the new live ranges have been created, rewrite
227 /// instructions using curli to use the new intervals.
230 // ===--- High level methods ---===
232 /// splitAroundLoop - Split curli into a separate live interval inside
233 /// the loop. Return true if curli has been completely replaced, false if
234 /// curli is still intact, and needs to be spilled or split further.
235 bool splitAroundLoop(const MachineLoop*);
237 /// splitSingleBlocks - Split curli into a separate live interval inside each
238 /// basic block in Blocks. Return true if curli has been completely replaced,
239 /// false if curli is still intact, and needs to be spilled or split further.
240 bool splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks);