SplitKit.h revision b38f02435b58eaba878d7a1894b610c4679fbd41 
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#include "llvm/ADT/SmallPtrSet.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/CodeGen/SlotIndexes.h"
18
19namespace llvm {
20
21class LiveInterval;
22class LiveIntervals;
23class MachineInstr;
24class MachineLoop;
25class MachineLoopInfo;
26class MachineRegisterInfo;
27class TargetInstrInfo;
28class VirtRegMap;
29class VNInfo;
30
31/// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting
32/// opportunities.
33class SplitAnalysis {
34public:
35  const MachineFunction &mf_;
36  const LiveIntervals &lis_;
37  const MachineLoopInfo &loops_;
38  const TargetInstrInfo &tii_;
39
40private:
41  // Current live interval.
42  const LiveInterval *curli_;
43
44  // Instructions using the the current register.
45  typedef SmallPtrSet<const MachineInstr*, 16> InstrPtrSet;
46  InstrPtrSet usingInstrs_;
47
48  // The number of instructions using curli in each basic block.
49  typedef DenseMap<const MachineBasicBlock*, unsigned> BlockCountMap;
50  BlockCountMap usingBlocks_;
51
52  // Loops where the curent interval is used.
53  typedef SmallPtrSet<const MachineLoop*, 16> LoopPtrSet;
54  LoopPtrSet usingLoops_;
55
56  // Sumarize statistics by counting instructions using curli_.
57  void analyzeUses();
58
59  /// canAnalyzeBranch - Return true if MBB ends in a branch that can be
60  /// analyzed.
61  bool canAnalyzeBranch(const MachineBasicBlock *MBB);
62
63public:
64  SplitAnalysis(const MachineFunction &mf, const LiveIntervals &lis,
65                const MachineLoopInfo &mli);
66
67  /// analyze - set curli to the specified interval, and analyze how it may be
68  /// split.
69  void analyze(const LiveInterval *li);
70
71  const LiveInterval *getCurLI() { return curli_; }
72
73  /// clear - clear all data structures so SplitAnalysis is ready to analyze a
74  /// new interval.
75  void clear();
76
77  typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet;
78
79  // Sets of basic blocks surrounding a machine loop.
80  struct LoopBlocks {
81    BlockPtrSet Loop;  // Blocks in the loop.
82    BlockPtrSet Preds; // Loop predecessor blocks.
83    BlockPtrSet Exits; // Loop exit blocks.
84
85    void clear() {
86      Loop.clear();
87      Preds.clear();
88      Exits.clear();
89    }
90  };
91
92  // Calculate the block sets surrounding the loop.
93  void getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks);
94
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.
102  };
103
104  /// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in
105  /// and around the Loop.
106  LoopPeripheralUse analyzeLoopPeripheralUse(const LoopBlocks&);
107
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);
112
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);
117
118  /// getBestSplitLoop - Return the loop where curli may best be split to a
119  /// separate register, or NULL.
120  const MachineLoop *getBestSplitLoop();
121};
122
123/// SplitEditor - Edit machine code and LiveIntervals for live range
124/// splitting.
125///
126/// - Create a SplitEditor from a SplitAnalysis.
127/// - Start a new live interval with openIntv.
128/// - Mark the places where the new interval is entered using enterIntv*
129/// - Mark the ranges where the new interval is used with useIntv*
130/// - Mark the places where the interval is exited with exitIntv*.
131/// - Finish the current interval with closeIntv and repeat from 2.
132/// - Rewrite instructions with rewrite().
133///
134class SplitEditor {
135  SplitAnalysis &sa_;
136  LiveIntervals &lis_;
137  VirtRegMap &vrm_;
138  MachineRegisterInfo &mri_;
139  const TargetInstrInfo &tii_;
140
141  /// curli_ - The immutable interval we are currently splitting.
142  const LiveInterval *const curli_;
143
144  /// dupli_ - Created as a copy of curli_, ranges are carved out as new
145  /// intervals get added through openIntv / closeIntv. This is used to avoid
146  /// editing curli_.
147  LiveInterval *dupli_;
148
149  /// Currently open LiveInterval.
150  LiveInterval *openli_;
151
152  /// createInterval - Create a new virtual register and LiveInterval with same
153  /// register class and spill slot as curli.
154  LiveInterval *createInterval();
155
156  /// getDupLI - Ensure dupli is created and return it.
157  LiveInterval *getDupLI();
158
159  /// valueMap_ - Map values in dupli to values in openIntv. These are direct 1-1
160  /// mappings, and do not include values created by inserted copies.
161  DenseMap<const VNInfo*, VNInfo*> valueMap_;
162
163  /// mapValue - Return the openIntv value that corresponds to the given curli
164  /// value.
165  VNInfo *mapValue(const VNInfo *curliVNI);
166
167  /// A dupli value is live through openIntv.
168  bool liveThrough_;
169
170  /// All the new intervals created for this split are added to intervals_.
171  std::vector<LiveInterval*> &intervals_;
172
173  /// The index into intervals_ of the first interval we added. There may be
174  /// others from before we got it.
175  unsigned firstInterval;
176
177  /// Insert a COPY instruction curli -> li. Allocate a new value from li
178  /// defined by the COPY
179  VNInfo *insertCopy(LiveInterval &LI,
180                     MachineBasicBlock &MBB,
181                     MachineBasicBlock::iterator I);
182
183public:
184  /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
185  /// Newly created intervals will be appended to newIntervals.
186  SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&,
187              std::vector<LiveInterval*> &newIntervals);
188
189  /// getAnalysis - Get the corresponding analysis.
190  SplitAnalysis &getAnalysis() { return sa_; }
191
192  /// Create a new virtual register and live interval.
193  void openIntv();
194
195  /// enterIntvAtEnd - Enter openli at the end of MBB.
196  /// PhiMBB is a successor inside openli where a PHI value is created.
197  /// Currently, all entries must share the same PhiMBB.
198  void enterIntvAtEnd(MachineBasicBlock &MBB, MachineBasicBlock &PhiMBB);
199
200  /// useIntv - indicate that all instructions in MBB should use openli.
201  void useIntv(const MachineBasicBlock &MBB);
202
203  /// useIntv - indicate that all instructions in range should use openli.
204  void useIntv(SlotIndex Start, SlotIndex End);
205
206  /// leaveIntvAtTop - Leave the interval at the top of MBB.
207  /// Currently, only one value can leave the interval.
208  void leaveIntvAtTop(MachineBasicBlock &MBB);
209
210  /// closeIntv - Indicate that we are done editing the currently open
211  /// LiveInterval, and ranges can be trimmed.
212  void closeIntv();
213
214  /// rewrite - after all the new live ranges have been created, rewrite
215  /// instructions using curli to use the new intervals.
216  void rewrite();
217
218  // ===--- High level methods ---===
219
220  /// splitAroundLoop - Split curli into a separate live interval inside
221  /// the loop. Return true if curli has been completely replaced, false if
222  /// curli is still intact, and needs to be spilled or split further.
223  bool splitAroundLoop(const MachineLoop*);
224
225};
226
227
228}
229