SplitKit.h revision f1b05f2b0ef48cb80b064e2f792b38c626822fc0 
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
40  // Instructions using the the current register.
41  typedef SmallPtrSet<const MachineInstr*, 16> InstrPtrSet;
42  InstrPtrSet usingInstrs_;
43
44  // The number of instructions using curli in each basic block.
45  typedef DenseMap<const MachineBasicBlock*, unsigned> BlockCountMap;
46  BlockCountMap usingBlocks_;
47
48  // Loops where the curent interval is used.
49  typedef SmallPtrSet<const MachineLoop*, 16> LoopPtrSet;
50  LoopPtrSet usingLoops_;
51
52private:
53  // Current live interval.
54  const LiveInterval *curli_;
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  /// 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);
126};
127
128/// SplitEditor - Edit machine code and LiveIntervals for live range
129/// splitting.
130///
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().
138///
139class SplitEditor {
140  SplitAnalysis &sa_;
141  LiveIntervals &lis_;
142  VirtRegMap &vrm_;
143  MachineRegisterInfo &mri_;
144  const TargetInstrInfo &tii_;
145
146  /// curli_ - The immutable interval we are currently splitting.
147  const LiveInterval *const curli_;
148
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
151  /// editing curli_.
152  LiveInterval *dupli_;
153
154  /// Currently open LiveInterval.
155  LiveInterval *openli_;
156
157  /// createInterval - Create a new virtual register and LiveInterval with same
158  /// register class and spill slot as curli.
159  LiveInterval *createInterval();
160
161  /// getDupLI - Ensure dupli is created and return it.
162  LiveInterval *getDupLI();
163
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_;
167
168  /// mapValue - Return the openIntv value that corresponds to the given curli
169  /// value.
170  VNInfo *mapValue(const VNInfo *curliVNI);
171
172  /// A dupli value is live through openIntv.
173  bool liveThrough_;
174
175  /// All the new intervals created for this split are added to intervals_.
176  std::vector<LiveInterval*> &intervals_;
177
178  /// The index into intervals_ of the first interval we added. There may be
179  /// others from before we got it.
180  unsigned firstInterval;
181
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);
187
188public:
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);
193
194  /// getAnalysis - Get the corresponding analysis.
195  SplitAnalysis &getAnalysis() { return sa_; }
196
197  /// Create a new virtual register and live interval.
198  void openIntv();
199
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);
203
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);
208
209  /// useIntv - indicate that all instructions in MBB should use openli.
210  void useIntv(const MachineBasicBlock &MBB);
211
212  /// useIntv - indicate that all instructions in range should use openli.
213  void useIntv(SlotIndex Start, SlotIndex End);
214
215  /// leaveIntvAfter - Leave openli after the instruction at Idx.
216  void leaveIntvAfter(SlotIndex Idx);
217
218  /// leaveIntvAtTop - Leave the interval at the top of MBB.
219  /// Currently, only one value can leave the interval.
220  void leaveIntvAtTop(MachineBasicBlock &MBB);
221
222  /// closeIntv - Indicate that we are done editing the currently open
223  /// LiveInterval, and ranges can be trimmed.
224  void closeIntv();
225
226  /// rewrite - after all the new live ranges have been created, rewrite
227  /// instructions using curli to use the new intervals.
228  void rewrite();
229
230  // ===--- High level methods ---===
231
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*);
236
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);
241};
242
243
244}
245