LLVM 18.0.0git
SplitKit.h
Go to the documentation of this file.
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 "llvm/ADT/ArrayRef.h"
18#include "llvm/ADT/BitVector.h"
19#include "llvm/ADT/DenseMap.h"
20#include "llvm/ADT/DenseSet.h"
31#include <utility>
32
33namespace llvm {
34
35class LiveInterval;
36class LiveRange;
37class LiveIntervals;
38class LiveRangeEdit;
39class MachineBlockFrequencyInfo;
40class MachineDominatorTree;
41class MachineLoopInfo;
42class MachineRegisterInfo;
43class TargetInstrInfo;
44class TargetRegisterInfo;
45class VirtRegMap;
46class VirtRegAuxInfo;
47
48/// Determines the latest safe point in a block in which we can insert a split,
49/// spill or other instruction related with CurLI.
51private:
52 const LiveIntervals &LIS;
53
54 /// Last legal insert point in each basic block in the current function.
55 /// The first entry is the first terminator, the second entry is the
56 /// last valid point to insert a split or spill for a variable that is
57 /// live into a landing pad or inlineasm_br successor.
59
60 SlotIndex computeLastInsertPoint(const LiveInterval &CurLI,
61 const MachineBasicBlock &MBB);
62
63public:
64 InsertPointAnalysis(const LiveIntervals &lis, unsigned BBNum);
65
66 /// Return the base index of the last valid insert point for \pCurLI in \pMBB.
68 const MachineBasicBlock &MBB) {
69 unsigned Num = MBB.getNumber();
70 // Inline the common simple case.
71 if (LastInsertPoint[Num].first.isValid() &&
72 !LastInsertPoint[Num].second.isValid())
73 return LastInsertPoint[Num].first;
74 return computeLastInsertPoint(CurLI, MBB);
75 }
76
77 /// Returns the last insert point as an iterator for \pCurLI in \pMBB.
78 MachineBasicBlock::iterator getLastInsertPointIter(const LiveInterval &CurLI,
80
81 /// Return the base index of the first insert point in \pMBB.
83 SlotIndex Res = LIS.getMBBStartIdx(&MBB);
84 if (!MBB.empty()) {
85 MachineBasicBlock::iterator MII = MBB.SkipPHIsLabelsAndDebug(MBB.begin());
86 if (MII != MBB.end())
87 Res = LIS.getInstructionIndex(*MII);
88 }
89 return Res;
90 }
91
92};
93
94/// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting
95/// opportunities.
97public:
103
104 /// Additional information about basic blocks where the current variable is
105 /// live. Such a block will look like one of these templates:
106 ///
107 /// 1. | o---x | Internal to block. Variable is only live in this block.
108 /// 2. |---x | Live-in, kill.
109 /// 3. | o---| Def, live-out.
110 /// 4. |---x o---| Live-in, kill, def, live-out. Counted by NumGapBlocks.
111 /// 5. |---o---o---| Live-through with uses or defs.
112 /// 6. |-----------| Live-through without uses. Counted by NumThroughBlocks.
113 ///
114 /// Two BlockInfo entries are created for template 4. One for the live-in
115 /// segment, and one for the live-out segment. These entries look as if the
116 /// block were split in the middle where the live range isn't live.
117 ///
118 /// Live-through blocks without any uses don't get BlockInfo entries. They
119 /// are simply listed in ThroughBlocks instead.
120 ///
121 struct BlockInfo {
123 SlotIndex FirstInstr; ///< First instr accessing current reg.
124 SlotIndex LastInstr; ///< Last instr accessing current reg.
125 SlotIndex FirstDef; ///< First non-phi valno->def, or SlotIndex().
126 bool LiveIn; ///< Current reg is live in.
127 bool LiveOut; ///< Current reg is live out.
128
129 /// isOneInstr - Returns true when this BlockInfo describes a single
130 /// instruction.
131 bool isOneInstr() const {
132 return SlotIndex::isSameInstr(FirstInstr, LastInstr);
133 }
134
135 void print(raw_ostream &OS) const;
136 void dump() const;
137 };
138
139private:
140 // Current live interval.
141 const LiveInterval *CurLI = nullptr;
142
143 /// Insert Point Analysis.
145
146 // Sorted slot indexes of using instructions.
148
149 /// UseBlocks - Blocks where CurLI has uses.
151
152 /// NumGapBlocks - Number of duplicate entries in UseBlocks for blocks where
153 /// the live range has a gap.
154 unsigned NumGapBlocks = 0u;
155
156 /// ThroughBlocks - Block numbers where CurLI is live through without uses.
157 BitVector ThroughBlocks;
158
159 /// NumThroughBlocks - Number of live-through blocks.
160 unsigned NumThroughBlocks = 0u;
161
162 // Sumarize statistics by counting instructions using CurLI.
163 void analyzeUses();
164
165 /// calcLiveBlockInfo - Compute per-block information about CurLI.
166 void calcLiveBlockInfo();
167
168public:
169 SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis,
170 const MachineLoopInfo &mli);
171
172 /// analyze - set CurLI to the specified interval, and analyze how it may be
173 /// split.
174 void analyze(const LiveInterval *li);
175
176 /// clear - clear all data structures so SplitAnalysis is ready to analyze a
177 /// new interval.
178 void clear();
179
180 /// getParent - Return the last analyzed interval.
181 const LiveInterval &getParent() const { return *CurLI; }
182
183 /// isOriginalEndpoint - Return true if the original live range was killed or
184 /// (re-)defined at Idx. Idx should be the 'def' slot for a normal kill/def,
185 /// and 'use' for an early-clobber def.
186 /// This can be used to recognize code inserted by earlier live range
187 /// splitting.
188 bool isOriginalEndpoint(SlotIndex Idx) const;
189
190 /// getUseSlots - Return an array of SlotIndexes of instructions using CurLI.
191 /// This include both use and def operands, at most one entry per instruction.
192 ArrayRef<SlotIndex> getUseSlots() const { return UseSlots; }
193
194 /// getUseBlocks - Return an array of BlockInfo objects for the basic blocks
195 /// where CurLI has uses.
196 ArrayRef<BlockInfo> getUseBlocks() const { return UseBlocks; }
197
198 /// getNumThroughBlocks - Return the number of through blocks.
199 unsigned getNumThroughBlocks() const { return NumThroughBlocks; }
200
201 /// isThroughBlock - Return true if CurLI is live through MBB without uses.
202 bool isThroughBlock(unsigned MBB) const { return ThroughBlocks.test(MBB); }
203
204 /// getThroughBlocks - Return the set of through blocks.
205 const BitVector &getThroughBlocks() const { return ThroughBlocks; }
206
207 /// getNumLiveBlocks - Return the number of blocks where CurLI is live.
208 unsigned getNumLiveBlocks() const {
209 return getUseBlocks().size() - NumGapBlocks + getNumThroughBlocks();
210 }
211
212 /// countLiveBlocks - Return the number of blocks where li is live. This is
213 /// guaranteed to return the same number as getNumLiveBlocks() after calling
214 /// analyze(li).
215 unsigned countLiveBlocks(const LiveInterval *li) const;
216
218
219 /// shouldSplitSingleBlock - Returns true if it would help to create a local
220 /// live range for the instructions in BI. There is normally no benefit to
221 /// creating a live range for a single instruction, but it does enable
222 /// register class inflation if the instruction has a restricted register
223 /// class.
224 ///
225 /// @param BI The block to be isolated.
226 /// @param SingleInstrs True when single instructions should be isolated.
227 bool shouldSplitSingleBlock(const BlockInfo &BI, bool SingleInstrs) const;
228
230 return IPA.getLastInsertPoint(*CurLI, *MF.getBlockNumbered(Num));
231 }
232
234 return IPA.getLastInsertPoint(*CurLI, *BB);
235 }
236
238 return IPA.getLastInsertPointIter(*CurLI, *BB);
239 }
240
242 return IPA.getFirstInsertPoint(*MF.getBlockNumbered(Num));
243 }
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///
258 SplitAnalysis &SA;
259 LiveIntervals &LIS;
260 VirtRegMap &VRM;
263 const TargetInstrInfo &TII;
264 const TargetRegisterInfo &TRI;
265 const MachineBlockFrequencyInfo &MBFI;
266 VirtRegAuxInfo &VRAI;
267
268public:
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.
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.
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.
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
295private:
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 ::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 /// LICalc - Cache for computing live ranges and SSA update. Each instance
336 /// can only handle non-overlapping live ranges, so use a separate
337 /// LiveIntervalCalc instance for the complement interval when in spill mode.
338 LiveIntervalCalc LICalc[2];
339
340 /// getLICalc - Return the LICalc to use for RegIdx. In spill mode, the
341 /// complement interval can overlap the other intervals, so it gets its own
342 /// LICalc instance. When not in spill mode, all intervals can share one.
343 LiveIntervalCalc &getLICalc(unsigned RegIdx) {
344 return LICalc[SpillMode != SM_Partition && RegIdx != 0];
345 }
346
347 /// Add a segment to the interval LI for the value number VNI. If LI has
348 /// subranges, corresponding segments will be added to them as well, but
349 /// with newly created value numbers. If Original is true, dead def will
350 /// only be added a subrange of LI if the corresponding subrange of the
351 /// original interval has a def at this index. Otherwise, all subranges
352 /// of LI will be updated.
353 void addDeadDef(LiveInterval &LI, VNInfo *VNI, bool Original);
354
355 /// defValue - define a value in RegIdx from ParentVNI at Idx.
356 /// Idx does not have to be ParentVNI->def, but it must be contained within
357 /// ParentVNI's live range in ParentLI. The new value is added to the value
358 /// map. The value being defined may either come from rematerialization
359 /// (or an inserted copy), or it may be coming from the original interval.
360 /// The parameter Original should be true in the latter case, otherwise
361 /// it should be false.
362 /// Return the new LI value.
363 VNInfo *defValue(unsigned RegIdx, const VNInfo *ParentVNI, SlotIndex Idx,
364 bool Original);
365
366 /// forceRecompute - Force the live range of ParentVNI in RegIdx to be
367 /// recomputed by LiveRangeCalc::extend regardless of the number of defs.
368 /// This is used for values whose live range doesn't match RegAssign exactly.
369 /// They could have rematerialized, or back-copies may have been moved.
370 void forceRecompute(unsigned RegIdx, const VNInfo &ParentVNI);
371
372 /// Calls forceRecompute() on any affected regidx and on ParentVNI
373 /// predecessors in case of a phi definition.
374 void forceRecomputeVNI(const VNInfo &ParentVNI);
375
376 /// defFromParent - Define Reg from ParentVNI at UseIdx using either
377 /// rematerialization or a COPY from parent. Return the new value.
378 VNInfo *defFromParent(unsigned RegIdx, const VNInfo *ParentVNI,
379 SlotIndex UseIdx, MachineBasicBlock &MBB,
380 MachineBasicBlock::iterator I);
381
382 /// removeBackCopies - Remove the copy instructions that defines the values
383 /// in the vector in the complement interval.
384 void removeBackCopies(SmallVectorImpl<VNInfo*> &Copies);
385
386 /// getShallowDominator - Returns the least busy dominator of MBB that is
387 /// also dominated by DefMBB. Busy is measured by loop depth.
388 MachineBasicBlock *findShallowDominator(MachineBasicBlock *MBB,
389 MachineBasicBlock *DefMBB);
390
391 /// Find out all the backCopies dominated by others.
392 void computeRedundantBackCopies(DenseSet<unsigned> &NotToHoistSet,
393 SmallVectorImpl<VNInfo *> &BackCopies);
394
395 /// Hoist back-copies to the complement interval. It tries to hoist all
396 /// the back-copies to one BB if it is beneficial, or else simply remove
397 /// redundant backcopies dominated by others.
398 void hoistCopies();
399
400 /// transferValues - Transfer values to the new ranges.
401 /// Return true if any ranges were skipped.
402 bool transferValues();
403
404 /// Live range @p LR corresponding to the lane Mask @p LM has a live
405 /// PHI def at the beginning of block @p B. Extend the range @p LR of
406 /// all predecessor values that reach this def. If @p LR is a subrange,
407 /// the array @p Undefs is the set of all locations where it is undefined
408 /// via <def,read-undef> in other subranges for the same register.
409 void extendPHIRange(MachineBasicBlock &B, LiveIntervalCalc &LIC,
410 LiveRange &LR, LaneBitmask LM,
411 ArrayRef<SlotIndex> Undefs);
412
413 /// extendPHIKillRanges - Extend the ranges of all values killed by original
414 /// parent PHIDefs.
415 void extendPHIKillRanges();
416
417 /// rewriteAssigned - Rewrite all uses of Edit.getReg() to assigned registers.
418 void rewriteAssigned(bool ExtendRanges);
419
420 /// deleteRematVictims - Delete defs that are dead after rematerializing.
421 void deleteRematVictims();
422
423 /// Add a copy instruction copying \p FromReg to \p ToReg before
424 /// \p InsertBefore. This can be invoked with a \p LaneMask which may make it
425 /// necessary to construct a sequence of copies to cover it exactly.
426 SlotIndex buildCopy(Register FromReg, Register ToReg, LaneBitmask LaneMask,
427 MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
428 bool Late, unsigned RegIdx);
429
430 SlotIndex buildSingleSubRegCopy(Register FromReg, Register ToReg,
431 MachineBasicBlock &MB,
432 MachineBasicBlock::iterator InsertBefore,
433 unsigned SubIdx, LiveInterval &DestLI,
434 bool Late, SlotIndex Def,
435 const MCInstrDesc &Desc);
436
437public:
438 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
439 /// Newly created intervals will be appended to newIntervals.
440 SplitEditor(SplitAnalysis &SA, LiveIntervals &LIS, VirtRegMap &VRM,
441 MachineDominatorTree &MDT, MachineBlockFrequencyInfo &MBFI,
442 VirtRegAuxInfo &VRAI);
443
444 /// reset - Prepare for a new split.
445 void reset(LiveRangeEdit&, ComplementSpillMode = SM_Partition);
446
447 /// Create a new virtual register and live interval.
448 /// Return the interval index, starting from 1. Interval index 0 is the
449 /// implicit complement interval.
450 unsigned openIntv();
451
452 /// currentIntv - Return the current interval index.
453 unsigned currentIntv() const { return OpenIdx; }
454
455 /// selectIntv - Select a previously opened interval index.
456 void selectIntv(unsigned Idx);
457
458 /// enterIntvBefore - Enter the open interval before the instruction at Idx.
459 /// If the parent interval is not live before Idx, a COPY is not inserted.
460 /// Return the beginning of the new live range.
461 SlotIndex enterIntvBefore(SlotIndex Idx);
462
463 /// enterIntvAfter - Enter the open interval after the instruction at Idx.
464 /// Return the beginning of the new live range.
465 SlotIndex enterIntvAfter(SlotIndex Idx);
466
467 /// enterIntvAtEnd - Enter the open interval at the end of MBB.
468 /// Use the open interval from the inserted copy to the MBB end.
469 /// Return the beginning of the new live range.
470 SlotIndex enterIntvAtEnd(MachineBasicBlock &MBB);
471
472 /// useIntv - indicate that all instructions in MBB should use OpenLI.
473 void useIntv(const MachineBasicBlock &MBB);
474
475 /// useIntv - indicate that all instructions in range should use OpenLI.
476 void useIntv(SlotIndex Start, SlotIndex End);
477
478 /// leaveIntvAfter - Leave the open interval after the instruction at Idx.
479 /// Return the end of the live range.
480 SlotIndex leaveIntvAfter(SlotIndex Idx);
481
482 /// leaveIntvBefore - Leave the open interval before the instruction at Idx.
483 /// Return the end of the live range.
484 SlotIndex leaveIntvBefore(SlotIndex Idx);
485
486 /// leaveIntvAtTop - Leave the interval at the top of MBB.
487 /// Add liveness from the MBB top to the copy.
488 /// Return the end of the live range.
489 SlotIndex leaveIntvAtTop(MachineBasicBlock &MBB);
490
491 /// overlapIntv - Indicate that all instructions in range should use the open
492 /// interval if End does not have tied-def usage of the register and in this
493 /// case complement interval is used. Let the complement interval be live.
494 ///
495 /// This doubles the register pressure, but is sometimes required to deal with
496 /// register uses after the last valid split point.
497 ///
498 /// The Start index should be a return value from a leaveIntv* call, and End
499 /// should be in the same basic block. The parent interval must have the same
500 /// value across the range.
501 ///
502 void overlapIntv(SlotIndex Start, SlotIndex End);
503
504 /// finish - after all the new live ranges have been created, compute the
505 /// remaining live range, and rewrite instructions to use the new registers.
506 /// @param LRMap When not null, this vector will map each live range in Edit
507 /// back to the indices returned by openIntv.
508 /// There may be extra indices created by dead code elimination.
509 void finish(SmallVectorImpl<unsigned> *LRMap = nullptr);
510
511 /// dump - print the current interval mapping to dbgs().
512 void dump() const;
513
514 // ===--- High level methods ---===
515
516 /// splitSingleBlock - Split CurLI into a separate live interval around the
517 /// uses in a single block. This is intended to be used as part of a larger
518 /// split, and doesn't call finish().
519 void splitSingleBlock(const SplitAnalysis::BlockInfo &BI);
520
521 /// splitLiveThroughBlock - Split CurLI in the given block such that it
522 /// enters the block in IntvIn and leaves it in IntvOut. There may be uses in
523 /// the block, but they will be ignored when placing split points.
524 ///
525 /// @param MBBNum Block number.
526 /// @param IntvIn Interval index entering the block.
527 /// @param LeaveBefore When set, leave IntvIn before this point.
528 /// @param IntvOut Interval index leaving the block.
529 /// @param EnterAfter When set, enter IntvOut after this point.
530 void splitLiveThroughBlock(unsigned MBBNum,
531 unsigned IntvIn, SlotIndex LeaveBefore,
532 unsigned IntvOut, SlotIndex EnterAfter);
533
534 /// splitRegInBlock - Split CurLI in the given block such that it enters the
535 /// block in IntvIn and leaves it on the stack (or not at all). Split points
536 /// are placed in a way that avoids putting uses in the stack interval. This
537 /// may require creating a local interval when there is interference.
538 ///
539 /// @param BI Block descriptor.
540 /// @param IntvIn Interval index entering the block. Not 0.
541 /// @param LeaveBefore When set, leave IntvIn before this point.
542 void splitRegInBlock(const SplitAnalysis::BlockInfo &BI,
543 unsigned IntvIn, SlotIndex LeaveBefore);
544
545 /// splitRegOutBlock - Split CurLI in the given block such that it enters the
546 /// block on the stack (or isn't live-in at all) and leaves it in IntvOut.
547 /// Split points are placed to avoid interference and such that the uses are
548 /// not in the stack interval. This may require creating a local interval
549 /// when there is interference.
550 ///
551 /// @param BI Block descriptor.
552 /// @param IntvOut Interval index leaving the block.
553 /// @param EnterAfter When set, enter IntvOut after this point.
554 void splitRegOutBlock(const SplitAnalysis::BlockInfo &BI,
555 unsigned IntvOut, SlotIndex EnterAfter);
556};
557
558} // end namespace llvm
559
560#endif // LLVM_LIB_CODEGEN_SPLITKIT_H
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
This file implements the BitVector class.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_LIBRARY_VISIBILITY
Definition: Compiler.h:131
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:150
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
bool End
Definition: ELF_riscv.cpp:469
const HexagonInstrInfo * TII
This file implements a coalescing interval map for small objects.
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
Promote Memory to Register
Definition: Mem2Reg.cpp:114
This file defines the PointerIntPair class.
Basic Register Allocator
SI Lower i1 Copies
SI Optimize VGPR LiveRange
raw_pwrite_stream & OS
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
bool test(unsigned Idx) const
Definition: BitVector.h:461
Determines the latest safe point in a block in which we can insert a split, spill or other instructio...
Definition: SplitKit.h:50
MachineBasicBlock::iterator getLastInsertPointIter(const LiveInterval &CurLI, MachineBasicBlock &MBB)
Returns the last insert point as an iterator for \pCurLI in \pMBB.
Definition: SplitKit.cpp:138
SlotIndex getLastInsertPoint(const LiveInterval &CurLI, const MachineBasicBlock &MBB)
Return the base index of the last valid insert point for \pCurLI in \pMBB.
Definition: SplitKit.h:67
SlotIndex getFirstInsertPoint(MachineBasicBlock &MBB)
Return the base index of the first insert point in \pMBB.
Definition: SplitKit.h:82
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:686
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const
Return the first index in the given basic block.
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
PointerIntPair - This class implements a pair of a pointer and small integer.
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:68
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
SplitAnalysis - Analyze a LiveInterval, looking for live range splitting opportunities.
Definition: SplitKit.h:96
const MachineFunction & MF
Definition: SplitKit.h:98
MachineBasicBlock::iterator getLastSplitPointIter(MachineBasicBlock *BB)
Definition: SplitKit.h:237
ArrayRef< BlockInfo > getUseBlocks() const
getUseBlocks - Return an array of BlockInfo objects for the basic blocks where CurLI has uses.
Definition: SplitKit.h:196
ArrayRef< SlotIndex > getUseSlots() const
getUseSlots - Return an array of SlotIndexes of instructions using CurLI.
Definition: SplitKit.h:192
unsigned getNumThroughBlocks() const
getNumThroughBlocks - Return the number of through blocks.
Definition: SplitKit.h:199
SlotIndex getLastSplitPoint(unsigned Num)
Definition: SplitKit.h:229
const LiveInterval & getParent() const
getParent - Return the last analyzed interval.
Definition: SplitKit.h:181
const LiveIntervals & LIS
Definition: SplitKit.h:100
const BitVector & getThroughBlocks() const
getThroughBlocks - Return the set of through blocks.
Definition: SplitKit.h:205
const MachineLoopInfo & Loops
Definition: SplitKit.h:101
const TargetInstrInfo & TII
Definition: SplitKit.h:102
unsigned getNumLiveBlocks() const
getNumLiveBlocks - Return the number of blocks where CurLI is live.
Definition: SplitKit.h:208
SlotIndex getLastSplitPoint(MachineBasicBlock *BB)
Definition: SplitKit.h:233
const VirtRegMap & VRM
Definition: SplitKit.h:99
bool isThroughBlock(unsigned MBB) const
isThroughBlock - Return true if CurLI is live through MBB without uses.
Definition: SplitKit.h:202
SlotIndex getFirstSplitPoint(unsigned Num)
Definition: SplitKit.h:241
SplitEditor - Edit machine code and LiveIntervals for live range splitting.
Definition: SplitKit.h:257
unsigned currentIntv() const
currentIntv - Return the current interval index.
Definition: SplitKit.h:453
ComplementSpillMode
ComplementSpillMode - Select how the complement live range should be created.
Definition: SplitKit.h:275
@ SM_Partition
SM_Partition(Default) - Try to create the complement interval so it doesn't overlap any other interva...
Definition: SplitKit.h:280
@ SM_Size
SM_Size - Overlap intervals to minimize the number of inserted COPY instructions.
Definition: SplitKit.h:287
TargetInstrInfo - Interface to description of machine instruction set.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
See the file comment.
Definition: ValueMap.h:84
Calculate auxiliary information for a virtual register such as its spill weight and allocation hint.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Additional information about basic blocks where the current variable is live.
Definition: SplitKit.h:121
SlotIndex FirstDef
First non-phi valno->def, or SlotIndex().
Definition: SplitKit.h:125
bool LiveOut
Current reg is live out.
Definition: SplitKit.h:127
bool LiveIn
Current reg is live in.
Definition: SplitKit.h:126
bool isOneInstr() const
isOneInstr - Returns true when this BlockInfo describes a single instruction.
Definition: SplitKit.h:131
MachineBasicBlock * MBB
Definition: SplitKit.h:122
SlotIndex LastInstr
Last instr accessing current reg.
Definition: SplitKit.h:124
SlotIndex FirstInstr
First instr accessing current reg.
Definition: SplitKit.h:123