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