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
34 const MachineFunction &mf_;
35 const LiveIntervals &lis_;
36 const MachineLoopInfo &loops_;
37 const TargetInstrInfo &tii_;
39 // Current live interval.
40 const LiveInterval *curli_;
42 // Instructions using the the current register.
43 typedef SmallPtrSet<const MachineInstr*, 16> InstrPtrSet;
44 InstrPtrSet usingInstrs_;
46 // The number of instructions using curli in each basic block.
47 typedef DenseMap<const MachineBasicBlock*, unsigned> BlockCountMap;
48 BlockCountMap usingBlocks_;
50 // Loops where the curent interval is used.
51 typedef SmallPtrSet<const MachineLoop*, 16> LoopPtrSet;
52 LoopPtrSet usingLoops_;
54 // Sumarize statistics by counting instructions using curli_.
57 /// canAnalyzeBranch - Return true if MBB ends in a branch that can be
59 bool canAnalyzeBranch(const MachineBasicBlock *MBB);
62 SplitAnalysis(const MachineFunction &mf, const LiveIntervals &lis,
63 const MachineLoopInfo &mli);
65 /// analyze - set curli to the specified interval, and analyze how it may be
67 void analyze(const LiveInterval *li);
69 const LiveInterval *getCurLI() { return curli_; }
71 /// clear - clear all data structures so SplitAnalysis is ready to analyze a
75 typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet;
77 // Sets of basic blocks surrounding a machine loop.
79 BlockPtrSet Loop; // Blocks in the loop.
80 BlockPtrSet Preds; // Loop predecessor blocks.
81 BlockPtrSet Exits; // Loop exit blocks.
90 // Calculate the block sets surrounding the loop.
91 void getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks);
93 /// LoopPeripheralUse - how is a variable used in and around a loop?
94 /// Peripheral blocks are the loop predecessors and exit blocks.
95 enum LoopPeripheralUse {
96 ContainedInLoop, // All uses are inside the loop.
97 SinglePeripheral, // At most one instruction per peripheral block.
98 MultiPeripheral, // Multiple instructions in some peripheral blocks.
99 OutsideLoop // Uses outside loop periphery.
102 /// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in
103 /// and around the Loop.
104 LoopPeripheralUse analyzeLoopPeripheralUse(const LoopBlocks&);
106 /// getCriticalExits - It may be necessary to partially break critical edges
107 /// leaving the loop if an exit block has phi uses of curli. Collect the exit
108 /// blocks that need special treatment into CriticalExits.
109 void getCriticalExits(const LoopBlocks &Blocks, BlockPtrSet &CriticalExits);
111 /// canSplitCriticalExits - Return true if it is possible to insert new exit
112 /// blocks before the blocks in CriticalExits.
113 bool canSplitCriticalExits(const LoopBlocks &Blocks,
114 BlockPtrSet &CriticalExits);
116 /// getBestSplitLoop - Return the loop where curli may best be split to a
117 /// separate register, or NULL.
118 const MachineLoop *getBestSplitLoop();
121 /// SplitEditor - Edit machine code and LiveIntervals for live range
124 /// - Create a SplitEditor from a SplitAnalysis. This will create a new
125 /// LiveInterval, dupli, that is identical to SA.curli.
126 /// - Start a new live interval with openIntv.
127 /// - Mark the places where the new interval is entered using enterIntv*
128 /// - Mark the ranges where the new interval is used with useIntv*
129 /// - Mark the places where the interval is exited with exitIntv*.
130 /// - Finish the current interval with closeIntv and repeat from 2.
131 /// - Rewrite instructions with rewrite().
137 MachineRegisterInfo &mri_;
138 const TargetInstrInfo &tii_;
140 /// dupli_ - Created as a copy of sa_.curli_, ranges are carved out as new
141 /// intervals get added through openIntv / closeIntv.
142 LiveInterval *dupli_;
144 /// Currently open LiveInterval.
145 LiveInterval *openli_;
147 /// createInterval - Create a new virtual register and LiveInterval with same
148 /// register class and spill slot as curli.
149 LiveInterval *createInterval();
151 /// valueMap_ - Map values in dupli to values in openIntv. These are direct 1-1
152 /// mappings, and do not include values created by inserted copies.
153 DenseMap<VNInfo*,VNInfo*> valueMap_;
155 /// mapValue - Return the openIntv value that corresponds to the given dupli
157 VNInfo *mapValue(VNInfo *dupliVNI);
159 /// A dupli value is live through openIntv.
162 /// All the new intervals created for this split are added to intervals_.
163 std::vector<LiveInterval*> &intervals_;
165 /// The index into intervals_ of the first interval we added. There may be
166 /// others from before we got it.
167 unsigned firstInterval;
169 /// Insert a COPY instruction curli -> li. Allocate a new value from li
170 /// defined by the COPY
171 VNInfo *insertCopy(LiveInterval &LI,
172 MachineBasicBlock &MBB,
173 MachineBasicBlock::iterator I);
176 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
177 /// Newly created intervals will be appended to newIntervals.
178 SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&,
179 std::vector<LiveInterval*> &newIntervals);
181 /// getAnalysis - Get the corresponding analysis.
182 SplitAnalysis &getAnalysis() { return sa_; }
184 /// Create a new virtual register and live interval.
187 /// enterIntvAtEnd - Enter openli at the end of MBB.
188 /// PhiMBB is a successor inside openli where a PHI value is created.
189 /// Currently, all entries must share the same PhiMBB.
190 void enterIntvAtEnd(MachineBasicBlock &MBB, MachineBasicBlock &PhiMBB);
192 /// useIntv - indicate that all instructions in MBB should use openli.
193 void useIntv(const MachineBasicBlock &MBB);
195 /// useIntv - indicate that all instructions in range should use openli.
196 void useIntv(SlotIndex Start, SlotIndex End);
198 /// leaveIntvAtTop - Leave the interval at the top of MBB.
199 /// Currently, only one value can leave the interval.
200 void leaveIntvAtTop(MachineBasicBlock &MBB);
202 /// closeIntv - Indicate that we are done editing the currently open
203 /// LiveInterval, and ranges can be trimmed.
206 /// rewrite - after all the new live ranges have been created, rewrite
207 /// instructions using curli to use the new intervals.
210 // ===--- High level methods ---===
212 /// splitAroundLoop - Split curli into a separate live interval inside
214 void splitAroundLoop(const MachineLoop*);