/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/SplitKit.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- SplitKit.h - Toolkit for splitting live ranges -----------*- C++ -*-===// |
2 | | // |
3 | | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | | // See https://llvm.org/LICENSE.txt for license information. |
5 | | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | | // |
7 | | //===----------------------------------------------------------------------===// |
8 | | // |
9 | | // This file contains the SplitAnalysis class as well as mutator functions for |
10 | | // live range splitting. |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #ifndef LLVM_LIB_CODEGEN_SPLITKIT_H |
15 | | #define LLVM_LIB_CODEGEN_SPLITKIT_H |
16 | | |
17 | | #include "LiveRangeCalc.h" |
18 | | #include "llvm/ADT/ArrayRef.h" |
19 | | #include "llvm/ADT/BitVector.h" |
20 | | #include "llvm/ADT/DenseMap.h" |
21 | | #include "llvm/ADT/DenseSet.h" |
22 | | #include "llvm/ADT/IntervalMap.h" |
23 | | #include "llvm/ADT/PointerIntPair.h" |
24 | | #include "llvm/ADT/SmallPtrSet.h" |
25 | | #include "llvm/ADT/SmallVector.h" |
26 | | #include "llvm/CodeGen/LiveInterval.h" |
27 | | #include "llvm/CodeGen/LiveIntervals.h" |
28 | | #include "llvm/CodeGen/MachineBasicBlock.h" |
29 | | #include "llvm/CodeGen/MachineFunction.h" |
30 | | #include "llvm/CodeGen/SlotIndexes.h" |
31 | | #include "llvm/MC/LaneBitmask.h" |
32 | | #include "llvm/Support/Compiler.h" |
33 | | #include <utility> |
34 | | |
35 | | namespace llvm { |
36 | | |
37 | | class LiveIntervals; |
38 | | class LiveRangeEdit; |
39 | | class MachineBlockFrequencyInfo; |
40 | | class MachineDominatorTree; |
41 | | class MachineLoopInfo; |
42 | | class MachineRegisterInfo; |
43 | | class TargetInstrInfo; |
44 | | class TargetRegisterInfo; |
45 | | class VirtRegMap; |
46 | | |
47 | | /// Determines the latest safe point in a block in which we can insert a split, |
48 | | /// spill or other instruction related with CurLI. |
49 | | class LLVM_LIBRARY_VISIBILITY InsertPointAnalysis { |
50 | | private: |
51 | | const LiveIntervals &LIS; |
52 | | |
53 | | /// Last legal insert point in each basic block in the current function. |
54 | | /// The first entry is the first terminator, the second entry is the |
55 | | /// last valid point to insert a split or spill for a variable that is |
56 | | /// live into a landing pad successor. |
57 | | SmallVector<std::pair<SlotIndex, SlotIndex>, 8> LastInsertPoint; |
58 | | |
59 | | SlotIndex computeLastInsertPoint(const LiveInterval &CurLI, |
60 | | const MachineBasicBlock &MBB); |
61 | | |
62 | | public: |
63 | | InsertPointAnalysis(const LiveIntervals &lis, unsigned BBNum); |
64 | | |
65 | | /// Return the base index of the last valid insert point for \pCurLI in \pMBB. |
66 | | SlotIndex getLastInsertPoint(const LiveInterval &CurLI, |
67 | 35.5M | const MachineBasicBlock &MBB) { |
68 | 35.5M | unsigned Num = MBB.getNumber(); |
69 | 35.5M | // Inline the common simple case. |
70 | 35.5M | if (LastInsertPoint[Num].first.isValid() && |
71 | 35.5M | !LastInsertPoint[Num].second.isValid()34.7M ) |
72 | 33.8M | return LastInsertPoint[Num].first; |
73 | 1.70M | return computeLastInsertPoint(CurLI, MBB); |
74 | 1.70M | } |
75 | | |
76 | | /// Returns the last insert point as an iterator for \pCurLI in \pMBB. |
77 | | MachineBasicBlock::iterator getLastInsertPointIter(const LiveInterval &CurLI, |
78 | | MachineBasicBlock &MBB); |
79 | | |
80 | | /// Return the base index of the first insert point in \pMBB. |
81 | 27.6M | SlotIndex getFirstInsertPoint(MachineBasicBlock &MBB) { |
82 | 27.6M | SlotIndex Res = LIS.getMBBStartIdx(&MBB); |
83 | 27.6M | if (!MBB.empty()) { |
84 | 27.6M | MachineBasicBlock::iterator MII = MBB.SkipPHIsLabelsAndDebug(MBB.begin()); |
85 | 27.6M | if (MII != MBB.end()) |
86 | 27.6M | Res = LIS.getInstructionIndex(*MII); |
87 | 27.6M | } |
88 | 27.6M | return Res; |
89 | 27.6M | } |
90 | | |
91 | | }; |
92 | | |
93 | | /// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting |
94 | | /// opportunities. |
95 | | class LLVM_LIBRARY_VISIBILITY SplitAnalysis { |
96 | | public: |
97 | | const MachineFunction &MF; |
98 | | const VirtRegMap &VRM; |
99 | | const LiveIntervals &LIS; |
100 | | const MachineLoopInfo &Loops; |
101 | | const TargetInstrInfo &TII; |
102 | | |
103 | | /// Additional information about basic blocks where the current variable is |
104 | | /// live. Such a block will look like one of these templates: |
105 | | /// |
106 | | /// 1. | o---x | Internal to block. Variable is only live in this block. |
107 | | /// 2. |---x | Live-in, kill. |
108 | | /// 3. | o---| Def, live-out. |
109 | | /// 4. |---x o---| Live-in, kill, def, live-out. Counted by NumGapBlocks. |
110 | | /// 5. |---o---o---| Live-through with uses or defs. |
111 | | /// 6. |-----------| Live-through without uses. Counted by NumThroughBlocks. |
112 | | /// |
113 | | /// Two BlockInfo entries are created for template 4. One for the live-in |
114 | | /// segment, and one for the live-out segment. These entries look as if the |
115 | | /// block were split in the middle where the live range isn't live. |
116 | | /// |
117 | | /// Live-through blocks without any uses don't get BlockInfo entries. They |
118 | | /// are simply listed in ThroughBlocks instead. |
119 | | /// |
120 | | struct BlockInfo { |
121 | | MachineBasicBlock *MBB; |
122 | | SlotIndex FirstInstr; ///< First instr accessing current reg. |
123 | | SlotIndex LastInstr; ///< Last instr accessing current reg. |
124 | | SlotIndex FirstDef; ///< First non-phi valno->def, or SlotIndex(). |
125 | | bool LiveIn; ///< Current reg is live in. |
126 | | bool LiveOut; ///< Current reg is live out. |
127 | | |
128 | | /// isOneInstr - Returns true when this BlockInfo describes a single |
129 | | /// instruction. |
130 | 444k | bool isOneInstr() const { |
131 | 444k | return SlotIndex::isSameInstr(FirstInstr, LastInstr); |
132 | 444k | } |
133 | | }; |
134 | | |
135 | | private: |
136 | | // Current live interval. |
137 | | const LiveInterval *CurLI = nullptr; |
138 | | |
139 | | /// Insert Point Analysis. |
140 | | InsertPointAnalysis IPA; |
141 | | |
142 | | // Sorted slot indexes of using instructions. |
143 | | SmallVector<SlotIndex, 8> UseSlots; |
144 | | |
145 | | /// UseBlocks - Blocks where CurLI has uses. |
146 | | SmallVector<BlockInfo, 8> UseBlocks; |
147 | | |
148 | | /// NumGapBlocks - Number of duplicate entries in UseBlocks for blocks where |
149 | | /// the live range has a gap. |
150 | | unsigned NumGapBlocks; |
151 | | |
152 | | /// ThroughBlocks - Block numbers where CurLI is live through without uses. |
153 | | BitVector ThroughBlocks; |
154 | | |
155 | | /// NumThroughBlocks - Number of live-through blocks. |
156 | | unsigned NumThroughBlocks; |
157 | | |
158 | | /// DidRepairRange - analyze was forced to shrinkToUses(). |
159 | | bool DidRepairRange; |
160 | | |
161 | | // Sumarize statistics by counting instructions using CurLI. |
162 | | void analyzeUses(); |
163 | | |
164 | | /// calcLiveBlockInfo - Compute per-block information about CurLI. |
165 | | bool calcLiveBlockInfo(); |
166 | | |
167 | | public: |
168 | | SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis, |
169 | | const MachineLoopInfo &mli); |
170 | | |
171 | | /// analyze - set CurLI to the specified interval, and analyze how it may be |
172 | | /// split. |
173 | | void analyze(const LiveInterval *li); |
174 | | |
175 | | /// didRepairRange() - Returns true if CurLI was invalid and has been repaired |
176 | | /// by analyze(). This really shouldn't happen, but sometimes the coalescer |
177 | | /// can create live ranges that end in mid-air. |
178 | 247k | bool didRepairRange() const { return DidRepairRange; } |
179 | | |
180 | | /// clear - clear all data structures so SplitAnalysis is ready to analyze a |
181 | | /// new interval. |
182 | | void clear(); |
183 | | |
184 | | /// getParent - Return the last analyzed interval. |
185 | 4.36M | const LiveInterval &getParent() const { return *CurLI; } |
186 | | |
187 | | /// isOriginalEndpoint - Return true if the original live range was killed or |
188 | | /// (re-)defined at Idx. Idx should be the 'def' slot for a normal kill/def, |
189 | | /// and 'use' for an early-clobber def. |
190 | | /// This can be used to recognize code inserted by earlier live range |
191 | | /// splitting. |
192 | | bool isOriginalEndpoint(SlotIndex Idx) const; |
193 | | |
194 | | /// getUseSlots - Return an array of SlotIndexes of instructions using CurLI. |
195 | | /// This include both use and def operands, at most one entry per instruction. |
196 | 1.01M | ArrayRef<SlotIndex> getUseSlots() const { return UseSlots; } |
197 | | |
198 | | /// getUseBlocks - Return an array of BlockInfo objects for the basic blocks |
199 | | /// where CurLI has uses. |
200 | 12.8M | ArrayRef<BlockInfo> getUseBlocks() const { return UseBlocks; } |
201 | | |
202 | | /// getNumThroughBlocks - Return the number of through blocks. |
203 | 361k | unsigned getNumThroughBlocks() const { return NumThroughBlocks; } |
204 | | |
205 | | /// isThroughBlock - Return true if CurLI is live through MBB without uses. |
206 | 0 | bool isThroughBlock(unsigned MBB) const { return ThroughBlocks.test(MBB); } |
207 | | |
208 | | /// getThroughBlocks - Return the set of through blocks. |
209 | 4.39M | const BitVector &getThroughBlocks() const { return ThroughBlocks; } |
210 | | |
211 | | /// getNumLiveBlocks - Return the number of blocks where CurLI is live. |
212 | 115k | unsigned getNumLiveBlocks() const { |
213 | 115k | return getUseBlocks().size() - NumGapBlocks + getNumThroughBlocks(); |
214 | 115k | } |
215 | | |
216 | | /// countLiveBlocks - Return the number of blocks where li is live. This is |
217 | | /// guaranteed to return the same number as getNumLiveBlocks() after calling |
218 | | /// analyze(li). |
219 | | unsigned countLiveBlocks(const LiveInterval *li) const; |
220 | | |
221 | | using BlockPtrSet = SmallPtrSet<const MachineBasicBlock *, 16>; |
222 | | |
223 | | /// shouldSplitSingleBlock - Returns true if it would help to create a local |
224 | | /// live range for the instructions in BI. There is normally no benefit to |
225 | | /// creating a live range for a single instruction, but it does enable |
226 | | /// register class inflation if the instruction has a restricted register |
227 | | /// class. |
228 | | /// |
229 | | /// @param BI The block to be isolated. |
230 | | /// @param SingleInstrs True when single instructions should be isolated. |
231 | | bool shouldSplitSingleBlock(const BlockInfo &BI, bool SingleInstrs) const; |
232 | | |
233 | 35.3M | SlotIndex getLastSplitPoint(unsigned Num) { |
234 | 35.3M | return IPA.getLastInsertPoint(*CurLI, *MF.getBlockNumbered(Num)); |
235 | 35.3M | } |
236 | | |
237 | 146k | MachineBasicBlock::iterator getLastSplitPointIter(MachineBasicBlock *BB) { |
238 | 146k | return IPA.getLastInsertPointIter(*CurLI, *BB); |
239 | 146k | } |
240 | | |
241 | 27.6M | SlotIndex getFirstSplitPoint(unsigned Num) { |
242 | 27.6M | return IPA.getFirstInsertPoint(*MF.getBlockNumbered(Num)); |
243 | 27.6M | } |
244 | | }; |
245 | | |
246 | | /// SplitEditor - Edit machine code and LiveIntervals for live range |
247 | | /// splitting. |
248 | | /// |
249 | | /// - Create a SplitEditor from a SplitAnalysis. |
250 | | /// - Start a new live interval with openIntv. |
251 | | /// - Mark the places where the new interval is entered using enterIntv* |
252 | | /// - Mark the ranges where the new interval is used with useIntv* |
253 | | /// - Mark the places where the interval is exited with exitIntv*. |
254 | | /// - Finish the current interval with closeIntv and repeat from 2. |
255 | | /// - Rewrite instructions with finish(). |
256 | | /// |
257 | | class LLVM_LIBRARY_VISIBILITY SplitEditor { |
258 | | SplitAnalysis &SA; |
259 | | AliasAnalysis &AA; |
260 | | LiveIntervals &LIS; |
261 | | VirtRegMap &VRM; |
262 | | MachineRegisterInfo &MRI; |
263 | | MachineDominatorTree &MDT; |
264 | | const TargetInstrInfo &TII; |
265 | | const TargetRegisterInfo &TRI; |
266 | | const MachineBlockFrequencyInfo &MBFI; |
267 | | |
268 | | public: |
269 | | /// ComplementSpillMode - Select how the complement live range should be |
270 | | /// created. SplitEditor automatically creates interval 0 to contain |
271 | | /// anything that isn't added to another interval. This complement interval |
272 | | /// can get quite complicated, and it can sometimes be an advantage to allow |
273 | | /// it to overlap the other intervals. If it is going to spill anyway, no |
274 | | /// registers are wasted by keeping a value in two places at the same time. |
275 | | enum ComplementSpillMode { |
276 | | /// SM_Partition(Default) - Try to create the complement interval so it |
277 | | /// doesn't overlap any other intervals, and the original interval is |
278 | | /// partitioned. This may require a large number of back copies and extra |
279 | | /// PHI-defs. Only segments marked with overlapIntv will be overlapping. |
280 | | SM_Partition, |
281 | | |
282 | | /// SM_Size - Overlap intervals to minimize the number of inserted COPY |
283 | | /// instructions. Copies to the complement interval are hoisted to their |
284 | | /// common dominator, so only one COPY is required per value in the |
285 | | /// complement interval. This also means that no extra PHI-defs need to be |
286 | | /// inserted in the complement interval. |
287 | | SM_Size, |
288 | | |
289 | | /// SM_Speed - Overlap intervals to minimize the expected execution |
290 | | /// frequency of the inserted copies. This is very similar to SM_Size, but |
291 | | /// the complement interval may get some extra PHI-defs. |
292 | | SM_Speed |
293 | | }; |
294 | | |
295 | | private: |
296 | | /// Edit - The current parent register and new intervals created. |
297 | | LiveRangeEdit *Edit = nullptr; |
298 | | |
299 | | /// Index into Edit of the currently open interval. |
300 | | /// The index 0 is used for the complement, so the first interval started by |
301 | | /// openIntv will be 1. |
302 | | unsigned OpenIdx = 0; |
303 | | |
304 | | /// The current spill mode, selected by reset(). |
305 | | ComplementSpillMode SpillMode = SM_Partition; |
306 | | |
307 | | using RegAssignMap = IntervalMap<SlotIndex, unsigned>; |
308 | | |
309 | | /// Allocator for the interval map. This will eventually be shared with |
310 | | /// SlotIndexes and LiveIntervals. |
311 | | RegAssignMap::Allocator Allocator; |
312 | | |
313 | | /// RegAssign - Map of the assigned register indexes. |
314 | | /// Edit.get(RegAssign.lookup(Idx)) is the register that should be live at |
315 | | /// Idx. |
316 | | RegAssignMap RegAssign; |
317 | | |
318 | | using ValueForcePair = PointerIntPair<VNInfo *, 1>; |
319 | | using ValueMap = DenseMap<std::pair<unsigned, unsigned>, ValueForcePair>; |
320 | | |
321 | | /// Values - keep track of the mapping from parent values to values in the new |
322 | | /// intervals. Given a pair (RegIdx, ParentVNI->id), Values contains: |
323 | | /// |
324 | | /// 1. No entry - the value is not mapped to Edit.get(RegIdx). |
325 | | /// 2. (Null, false) - the value is mapped to multiple values in |
326 | | /// Edit.get(RegIdx). Each value is represented by a minimal live range at |
327 | | /// its def. The full live range can be inferred exactly from the range |
328 | | /// of RegIdx in RegAssign. |
329 | | /// 3. (Null, true). As above, but the ranges in RegAssign are too large, and |
330 | | /// the live range must be recomputed using LiveRangeCalc::extend(). |
331 | | /// 4. (VNI, false) The value is mapped to a single new value. |
332 | | /// The new value has no live ranges anywhere. |
333 | | ValueMap Values; |
334 | | |
335 | | /// LRCalc - Cache for computing live ranges and SSA update. Each instance |
336 | | /// can only handle non-overlapping live ranges, so use a separate |
337 | | /// LiveRangeCalc instance for the complement interval when in spill mode. |
338 | | LiveRangeCalc LRCalc[2]; |
339 | | |
340 | | /// getLRCalc - Return the LRCalc to use for RegIdx. In spill mode, the |
341 | | /// complement interval can overlap the other intervals, so it gets its own |
342 | | /// LRCalc instance. When not in spill mode, all intervals can share one. |
343 | 769k | LiveRangeCalc &getLRCalc(unsigned RegIdx) { |
344 | 769k | return LRCalc[SpillMode != SM_Partition && RegIdx != 0758k ]; |
345 | 769k | } |
346 | | |
347 | | /// Find a subrange corresponding to the lane mask @p LM in the live |
348 | | /// interval @p LI. The interval @p LI is assumed to contain such a subrange. |
349 | | /// This function is used to find corresponding subranges between the |
350 | | /// original interval and the new intervals. |
351 | | LiveInterval::SubRange &getSubRangeForMask(LaneBitmask LM, LiveInterval &LI); |
352 | | |
353 | | /// Add a segment to the interval LI for the value number VNI. If LI has |
354 | | /// subranges, corresponding segments will be added to them as well, but |
355 | | /// with newly created value numbers. If Original is true, dead def will |
356 | | /// only be added a subrange of LI if the corresponding subrange of the |
357 | | /// original interval has a def at this index. Otherwise, all subranges |
358 | | /// of LI will be updated. |
359 | | void addDeadDef(LiveInterval &LI, VNInfo *VNI, bool Original); |
360 | | |
361 | | /// defValue - define a value in RegIdx from ParentVNI at Idx. |
362 | | /// Idx does not have to be ParentVNI->def, but it must be contained within |
363 | | /// ParentVNI's live range in ParentLI. The new value is added to the value |
364 | | /// map. The value being defined may either come from rematerialization |
365 | | /// (or an inserted copy), or it may be coming from the original interval. |
366 | | /// The parameter Original should be true in the latter case, otherwise |
367 | | /// it should be false. |
368 | | /// Return the new LI value. |
369 | | VNInfo *defValue(unsigned RegIdx, const VNInfo *ParentVNI, SlotIndex Idx, |
370 | | bool Original); |
371 | | |
372 | | /// forceRecompute - Force the live range of ParentVNI in RegIdx to be |
373 | | /// recomputed by LiveRangeCalc::extend regardless of the number of defs. |
374 | | /// This is used for values whose live range doesn't match RegAssign exactly. |
375 | | /// They could have rematerialized, or back-copies may have been moved. |
376 | | void forceRecompute(unsigned RegIdx, const VNInfo &ParentVNI); |
377 | | |
378 | | /// Calls forceRecompute() on any affected regidx and on ParentVNI |
379 | | /// predecessors in case of a phi definition. |
380 | | void forceRecomputeVNI(const VNInfo &ParentVNI); |
381 | | |
382 | | /// defFromParent - Define Reg from ParentVNI at UseIdx using either |
383 | | /// rematerialization or a COPY from parent. Return the new value. |
384 | | VNInfo *defFromParent(unsigned RegIdx, |
385 | | VNInfo *ParentVNI, |
386 | | SlotIndex UseIdx, |
387 | | MachineBasicBlock &MBB, |
388 | | MachineBasicBlock::iterator I); |
389 | | |
390 | | /// removeBackCopies - Remove the copy instructions that defines the values |
391 | | /// in the vector in the complement interval. |
392 | | void removeBackCopies(SmallVectorImpl<VNInfo*> &Copies); |
393 | | |
394 | | /// getShallowDominator - Returns the least busy dominator of MBB that is |
395 | | /// also dominated by DefMBB. Busy is measured by loop depth. |
396 | | MachineBasicBlock *findShallowDominator(MachineBasicBlock *MBB, |
397 | | MachineBasicBlock *DefMBB); |
398 | | |
399 | | /// Find out all the backCopies dominated by others. |
400 | | void computeRedundantBackCopies(DenseSet<unsigned> &NotToHoistSet, |
401 | | SmallVectorImpl<VNInfo *> &BackCopies); |
402 | | |
403 | | /// Hoist back-copies to the complement interval. It tries to hoist all |
404 | | /// the back-copies to one BB if it is beneficial, or else simply remove |
405 | | /// redundant backcopies dominated by others. |
406 | | void hoistCopies(); |
407 | | |
408 | | /// transferValues - Transfer values to the new ranges. |
409 | | /// Return true if any ranges were skipped. |
410 | | bool transferValues(); |
411 | | |
412 | | /// Live range @p LR corresponding to the lane Mask @p LM has a live |
413 | | /// PHI def at the beginning of block @p B. Extend the range @p LR of |
414 | | /// all predecessor values that reach this def. If @p LR is a subrange, |
415 | | /// the array @p Undefs is the set of all locations where it is undefined |
416 | | /// via <def,read-undef> in other subranges for the same register. |
417 | | void extendPHIRange(MachineBasicBlock &B, LiveRangeCalc &LRC, |
418 | | LiveRange &LR, LaneBitmask LM, |
419 | | ArrayRef<SlotIndex> Undefs); |
420 | | |
421 | | /// extendPHIKillRanges - Extend the ranges of all values killed by original |
422 | | /// parent PHIDefs. |
423 | | void extendPHIKillRanges(); |
424 | | |
425 | | /// rewriteAssigned - Rewrite all uses of Edit.getReg() to assigned registers. |
426 | | void rewriteAssigned(bool ExtendRanges); |
427 | | |
428 | | /// deleteRematVictims - Delete defs that are dead after rematerializing. |
429 | | void deleteRematVictims(); |
430 | | |
431 | | /// Add a copy instruction copying \p FromReg to \p ToReg before |
432 | | /// \p InsertBefore. This can be invoked with a \p LaneMask which may make it |
433 | | /// necessary to construct a sequence of copies to cover it exactly. |
434 | | SlotIndex buildCopy(unsigned FromReg, unsigned ToReg, LaneBitmask LaneMask, |
435 | | MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore, |
436 | | bool Late, unsigned RegIdx); |
437 | | |
438 | | SlotIndex buildSingleSubRegCopy(unsigned FromReg, unsigned ToReg, |
439 | | MachineBasicBlock &MB, MachineBasicBlock::iterator InsertBefore, |
440 | | unsigned SubIdx, LiveInterval &DestLI, bool Late, SlotIndex Def); |
441 | | |
442 | | public: |
443 | | /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. |
444 | | /// Newly created intervals will be appended to newIntervals. |
445 | | SplitEditor(SplitAnalysis &sa, AliasAnalysis &aa, LiveIntervals &lis, |
446 | | VirtRegMap &vrm, MachineDominatorTree &mdt, |
447 | | MachineBlockFrequencyInfo &mbfi); |
448 | | |
449 | | /// reset - Prepare for a new split. |
450 | | void reset(LiveRangeEdit&, ComplementSpillMode = SM_Partition); |
451 | | |
452 | | /// Create a new virtual register and live interval. |
453 | | /// Return the interval index, starting from 1. Interval index 0 is the |
454 | | /// implicit complement interval. |
455 | | unsigned openIntv(); |
456 | | |
457 | | /// currentIntv - Return the current interval index. |
458 | 0 | unsigned currentIntv() const { return OpenIdx; } |
459 | | |
460 | | /// selectIntv - Select a previously opened interval index. |
461 | | void selectIntv(unsigned Idx); |
462 | | |
463 | | /// enterIntvBefore - Enter the open interval before the instruction at Idx. |
464 | | /// If the parent interval is not live before Idx, a COPY is not inserted. |
465 | | /// Return the beginning of the new live range. |
466 | | SlotIndex enterIntvBefore(SlotIndex Idx); |
467 | | |
468 | | /// enterIntvAfter - Enter the open interval after the instruction at Idx. |
469 | | /// Return the beginning of the new live range. |
470 | | SlotIndex enterIntvAfter(SlotIndex Idx); |
471 | | |
472 | | /// enterIntvAtEnd - Enter the open interval at the end of MBB. |
473 | | /// Use the open interval from the inserted copy to the MBB end. |
474 | | /// Return the beginning of the new live range. |
475 | | SlotIndex enterIntvAtEnd(MachineBasicBlock &MBB); |
476 | | |
477 | | /// useIntv - indicate that all instructions in MBB should use OpenLI. |
478 | | void useIntv(const MachineBasicBlock &MBB); |
479 | | |
480 | | /// useIntv - indicate that all instructions in range should use OpenLI. |
481 | | void useIntv(SlotIndex Start, SlotIndex End); |
482 | | |
483 | | /// leaveIntvAfter - Leave the open interval after the instruction at Idx. |
484 | | /// Return the end of the live range. |
485 | | SlotIndex leaveIntvAfter(SlotIndex Idx); |
486 | | |
487 | | /// leaveIntvBefore - Leave the open interval before the instruction at Idx. |
488 | | /// Return the end of the live range. |
489 | | SlotIndex leaveIntvBefore(SlotIndex Idx); |
490 | | |
491 | | /// leaveIntvAtTop - Leave the interval at the top of MBB. |
492 | | /// Add liveness from the MBB top to the copy. |
493 | | /// Return the end of the live range. |
494 | | SlotIndex leaveIntvAtTop(MachineBasicBlock &MBB); |
495 | | |
496 | | /// overlapIntv - Indicate that all instructions in range should use the open |
497 | | /// interval, but also let the complement interval be live. |
498 | | /// |
499 | | /// This doubles the register pressure, but is sometimes required to deal with |
500 | | /// register uses after the last valid split point. |
501 | | /// |
502 | | /// The Start index should be a return value from a leaveIntv* call, and End |
503 | | /// should be in the same basic block. The parent interval must have the same |
504 | | /// value across the range. |
505 | | /// |
506 | | void overlapIntv(SlotIndex Start, SlotIndex End); |
507 | | |
508 | | /// finish - after all the new live ranges have been created, compute the |
509 | | /// remaining live range, and rewrite instructions to use the new registers. |
510 | | /// @param LRMap When not null, this vector will map each live range in Edit |
511 | | /// back to the indices returned by openIntv. |
512 | | /// There may be extra indices created by dead code elimination. |
513 | | void finish(SmallVectorImpl<unsigned> *LRMap = nullptr); |
514 | | |
515 | | /// dump - print the current interval mapping to dbgs(). |
516 | | void dump() const; |
517 | | |
518 | | // ===--- High level methods ---=== |
519 | | |
520 | | /// splitSingleBlock - Split CurLI into a separate live interval around the |
521 | | /// uses in a single block. This is intended to be used as part of a larger |
522 | | /// split, and doesn't call finish(). |
523 | | void splitSingleBlock(const SplitAnalysis::BlockInfo &BI); |
524 | | |
525 | | /// splitLiveThroughBlock - Split CurLI in the given block such that it |
526 | | /// enters the block in IntvIn and leaves it in IntvOut. There may be uses in |
527 | | /// the block, but they will be ignored when placing split points. |
528 | | /// |
529 | | /// @param MBBNum Block number. |
530 | | /// @param IntvIn Interval index entering the block. |
531 | | /// @param LeaveBefore When set, leave IntvIn before this point. |
532 | | /// @param IntvOut Interval index leaving the block. |
533 | | /// @param EnterAfter When set, enter IntvOut after this point. |
534 | | void splitLiveThroughBlock(unsigned MBBNum, |
535 | | unsigned IntvIn, SlotIndex LeaveBefore, |
536 | | unsigned IntvOut, SlotIndex EnterAfter); |
537 | | |
538 | | /// splitRegInBlock - Split CurLI in the given block such that it enters the |
539 | | /// block in IntvIn and leaves it on the stack (or not at all). Split points |
540 | | /// are placed in a way that avoids putting uses in the stack interval. This |
541 | | /// may require creating a local interval when there is interference. |
542 | | /// |
543 | | /// @param BI Block descriptor. |
544 | | /// @param IntvIn Interval index entering the block. Not 0. |
545 | | /// @param LeaveBefore When set, leave IntvIn before this point. |
546 | | void splitRegInBlock(const SplitAnalysis::BlockInfo &BI, |
547 | | unsigned IntvIn, SlotIndex LeaveBefore); |
548 | | |
549 | | /// splitRegOutBlock - Split CurLI in the given block such that it enters the |
550 | | /// block on the stack (or isn't live-in at all) and leaves it in IntvOut. |
551 | | /// Split points are placed to avoid interference and such that the uses are |
552 | | /// not in the stack interval. This may require creating a local interval |
553 | | /// when there is interference. |
554 | | /// |
555 | | /// @param BI Block descriptor. |
556 | | /// @param IntvOut Interval index leaving the block. |
557 | | /// @param EnterAfter When set, enter IntvOut after this point. |
558 | | void splitRegOutBlock(const SplitAnalysis::BlockInfo &BI, |
559 | | unsigned IntvOut, SlotIndex EnterAfter); |
560 | | }; |
561 | | |
562 | | } // end namespace llvm |
563 | | |
564 | | #endif // LLVM_LIB_CODEGEN_SPLITKIT_H |