LLVM 19.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 /// LooksLikeLoopIV - The variable defines what looks like it could be a loop
163 /// IV, where it defs a variable in the latch.
164 bool LooksLikeLoopIV = false;
165
166 // Sumarize statistics by counting instructions using CurLI.
167 void analyzeUses();
168
169 /// calcLiveBlockInfo - Compute per-block information about CurLI.
170 void calcLiveBlockInfo();
171
172public:
173 SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis,
174 const MachineLoopInfo &mli);
175
176 /// analyze - set CurLI to the specified interval, and analyze how it may be
177 /// split.
178 void analyze(const LiveInterval *li);
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 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 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 ArrayRef<BlockInfo> getUseBlocks() const { return UseBlocks; }
201
202 /// getNumThroughBlocks - Return the number of through blocks.
203 unsigned getNumThroughBlocks() const { return NumThroughBlocks; }
204
205 /// isThroughBlock - Return true if CurLI is live through MBB without uses.
206 bool isThroughBlock(unsigned MBB) const { return ThroughBlocks.test(MBB); }
207
208 /// getThroughBlocks - Return the set of through blocks.
209 const BitVector &getThroughBlocks() const { return ThroughBlocks; }
210
211 /// getNumLiveBlocks - Return the number of blocks where CurLI is live.
212 unsigned getNumLiveBlocks() const {
213 return getUseBlocks().size() - NumGapBlocks + getNumThroughBlocks();
214 }
215
216 bool looksLikeLoopIV() const { return LooksLikeLoopIV; }
217
218 /// countLiveBlocks - Return the number of blocks where li is live. This is
219 /// guaranteed to return the same number as getNumLiveBlocks() after calling
220 /// analyze(li).
221 unsigned countLiveBlocks(const LiveInterval *li) const;
222
224
225 /// shouldSplitSingleBlock - Returns true if it would help to create a local
226 /// live range for the instructions in BI. There is normally no benefit to
227 /// creating a live range for a single instruction, but it does enable
228 /// register class inflation if the instruction has a restricted register
229 /// class.
230 ///
231 /// @param BI The block to be isolated.
232 /// @param SingleInstrs True when single instructions should be isolated.
233 bool shouldSplitSingleBlock(const BlockInfo &BI, bool SingleInstrs) const;
234
236 return IPA.getLastInsertPoint(*CurLI, *MF.getBlockNumbered(Num));
237 }
238
240 return IPA.getLastInsertPoint(*CurLI, *BB);
241 }
242
244 return IPA.getLastInsertPointIter(*CurLI, *BB);
245 }
246
248 return IPA.getFirstInsertPoint(*MF.getBlockNumbered(Num));
249 }
250};
251
252/// SplitEditor - Edit machine code and LiveIntervals for live range
253/// splitting.
254///
255/// - Create a SplitEditor from a SplitAnalysis.
256/// - Start a new live interval with openIntv.
257/// - Mark the places where the new interval is entered using enterIntv*
258/// - Mark the ranges where the new interval is used with useIntv*
259/// - Mark the places where the interval is exited with exitIntv*.
260/// - Finish the current interval with closeIntv and repeat from 2.
261/// - Rewrite instructions with finish().
262///
264 SplitAnalysis &SA;
265 LiveIntervals &LIS;
266 VirtRegMap &VRM;
269 const TargetInstrInfo &TII;
270 const TargetRegisterInfo &TRI;
271 const MachineBlockFrequencyInfo &MBFI;
272 VirtRegAuxInfo &VRAI;
273
274public:
275 /// ComplementSpillMode - Select how the complement live range should be
276 /// created. SplitEditor automatically creates interval 0 to contain
277 /// anything that isn't added to another interval. This complement interval
278 /// can get quite complicated, and it can sometimes be an advantage to allow
279 /// it to overlap the other intervals. If it is going to spill anyway, no
280 /// registers are wasted by keeping a value in two places at the same time.
282 /// SM_Partition(Default) - Try to create the complement interval so it
283 /// doesn't overlap any other intervals, and the original interval is
284 /// partitioned. This may require a large number of back copies and extra
285 /// PHI-defs. Only segments marked with overlapIntv will be overlapping.
287
288 /// SM_Size - Overlap intervals to minimize the number of inserted COPY
289 /// instructions. Copies to the complement interval are hoisted to their
290 /// common dominator, so only one COPY is required per value in the
291 /// complement interval. This also means that no extra PHI-defs need to be
292 /// inserted in the complement interval.
294
295 /// SM_Speed - Overlap intervals to minimize the expected execution
296 /// frequency of the inserted copies. This is very similar to SM_Size, but
297 /// the complement interval may get some extra PHI-defs.
298 SM_Speed
299 };
300
301private:
302 /// Edit - The current parent register and new intervals created.
303 LiveRangeEdit *Edit = nullptr;
304
305 /// Index into Edit of the currently open interval.
306 /// The index 0 is used for the complement, so the first interval started by
307 /// openIntv will be 1.
308 unsigned OpenIdx = 0;
309
310 /// The current spill mode, selected by reset().
311 ComplementSpillMode SpillMode = SM_Partition;
312
313 using RegAssignMap = IntervalMap<SlotIndex, unsigned>;
314
315 /// Allocator for the interval map. This will eventually be shared with
316 /// SlotIndexes and LiveIntervals.
317 RegAssignMap::Allocator Allocator;
318
319 /// RegAssign - Map of the assigned register indexes.
320 /// Edit.get(RegAssign.lookup(Idx)) is the register that should be live at
321 /// Idx.
322 RegAssignMap RegAssign;
323
324 using ValueForcePair = PointerIntPair<VNInfo *, 1>;
325 using ValueMap = DenseMap<std::pair<unsigned, unsigned>, ValueForcePair>;
326
327 /// Values - keep track of the mapping from parent values to values in the new
328 /// intervals. Given a pair (RegIdx, ParentVNI->id), Values contains:
329 ///
330 /// 1. No entry - the value is not mapped to Edit.get(RegIdx).
331 /// 2. (Null, false) - the value is mapped to multiple values in
332 /// Edit.get(RegIdx). Each value is represented by a minimal live range at
333 /// its def. The full live range can be inferred exactly from the range
334 /// of RegIdx in RegAssign.
335 /// 3. (Null, true). As above, but the ranges in RegAssign are too large, and
336 /// the live range must be recomputed using ::extend().
337 /// 4. (VNI, false) The value is mapped to a single new value.
338 /// The new value has no live ranges anywhere.
339 ValueMap Values;
340
341 /// LICalc - Cache for computing live ranges and SSA update. Each instance
342 /// can only handle non-overlapping live ranges, so use a separate
343 /// LiveIntervalCalc instance for the complement interval when in spill mode.
344 LiveIntervalCalc LICalc[2];
345
346 /// getLICalc - Return the LICalc to use for RegIdx. In spill mode, the
347 /// complement interval can overlap the other intervals, so it gets its own
348 /// LICalc instance. When not in spill mode, all intervals can share one.
349 LiveIntervalCalc &getLICalc(unsigned RegIdx) {
350 return LICalc[SpillMode != SM_Partition && RegIdx != 0];
351 }
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, const VNInfo *ParentVNI,
385 SlotIndex UseIdx, MachineBasicBlock &MBB,
386 MachineBasicBlock::iterator I);
387
388 /// removeBackCopies - Remove the copy instructions that defines the values
389 /// in the vector in the complement interval.
390 void removeBackCopies(SmallVectorImpl<VNInfo*> &Copies);
391
392 /// getShallowDominator - Returns the least busy dominator of MBB that is
393 /// also dominated by DefMBB. Busy is measured by loop depth.
394 MachineBasicBlock *findShallowDominator(MachineBasicBlock *MBB,
395 MachineBasicBlock *DefMBB);
396
397 /// Find out all the backCopies dominated by others.
398 void computeRedundantBackCopies(DenseSet<unsigned> &NotToHoistSet,
399 SmallVectorImpl<VNInfo *> &BackCopies);
400
401 /// Hoist back-copies to the complement interval. It tries to hoist all
402 /// the back-copies to one BB if it is beneficial, or else simply remove
403 /// redundant backcopies dominated by others.
404 void hoistCopies();
405
406 /// transferValues - Transfer values to the new ranges.
407 /// Return true if any ranges were skipped.
408 bool transferValues();
409
410 /// Live range @p LR corresponding to the lane Mask @p LM has a live
411 /// PHI def at the beginning of block @p B. Extend the range @p LR of
412 /// all predecessor values that reach this def. If @p LR is a subrange,
413 /// the array @p Undefs is the set of all locations where it is undefined
414 /// via <def,read-undef> in other subranges for the same register.
415 void extendPHIRange(MachineBasicBlock &B, LiveIntervalCalc &LIC,
416 LiveRange &LR, LaneBitmask LM,
417 ArrayRef<SlotIndex> Undefs);
418
419 /// extendPHIKillRanges - Extend the ranges of all values killed by original
420 /// parent PHIDefs.
421 void extendPHIKillRanges();
422
423 /// rewriteAssigned - Rewrite all uses of Edit.getReg() to assigned registers.
424 void rewriteAssigned(bool ExtendRanges);
425
426 /// deleteRematVictims - Delete defs that are dead after rematerializing.
427 void deleteRematVictims();
428
429 /// Add a copy instruction copying \p FromReg to \p ToReg before
430 /// \p InsertBefore. This can be invoked with a \p LaneMask which may make it
431 /// necessary to construct a sequence of copies to cover it exactly.
432 SlotIndex buildCopy(Register FromReg, Register ToReg, LaneBitmask LaneMask,
433 MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
434 bool Late, unsigned RegIdx);
435
436 SlotIndex buildSingleSubRegCopy(Register FromReg, Register ToReg,
437 MachineBasicBlock &MB,
438 MachineBasicBlock::iterator InsertBefore,
439 unsigned SubIdx, LiveInterval &DestLI,
440 bool Late, SlotIndex Def,
441 const MCInstrDesc &Desc);
442
443public:
444 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
445 /// Newly created intervals will be appended to newIntervals.
446 SplitEditor(SplitAnalysis &SA, LiveIntervals &LIS, VirtRegMap &VRM,
447 MachineDominatorTree &MDT, MachineBlockFrequencyInfo &MBFI,
448 VirtRegAuxInfo &VRAI);
449
450 /// reset - Prepare for a new split.
451 void reset(LiveRangeEdit&, ComplementSpillMode = SM_Partition);
452
453 /// Create a new virtual register and live interval.
454 /// Return the interval index, starting from 1. Interval index 0 is the
455 /// implicit complement interval.
456 unsigned openIntv();
457
458 /// currentIntv - Return the current interval index.
459 unsigned currentIntv() const { return OpenIdx; }
460
461 /// selectIntv - Select a previously opened interval index.
462 void selectIntv(unsigned Idx);
463
464 /// enterIntvBefore - Enter the open interval before the instruction at Idx.
465 /// If the parent interval is not live before Idx, a COPY is not inserted.
466 /// Return the beginning of the new live range.
467 SlotIndex enterIntvBefore(SlotIndex Idx);
468
469 /// enterIntvAfter - Enter the open interval after the instruction at Idx.
470 /// Return the beginning of the new live range.
471 SlotIndex enterIntvAfter(SlotIndex Idx);
472
473 /// enterIntvAtEnd - Enter the open interval at the end of MBB.
474 /// Use the open interval from the inserted copy to the MBB end.
475 /// Return the beginning of the new live range.
476 SlotIndex enterIntvAtEnd(MachineBasicBlock &MBB);
477
478 /// useIntv - indicate that all instructions in MBB should use OpenLI.
479 void useIntv(const MachineBasicBlock &MBB);
480
481 /// useIntv - indicate that all instructions in range should use OpenLI.
482 void useIntv(SlotIndex Start, SlotIndex End);
483
484 /// leaveIntvAfter - Leave the open interval after the instruction at Idx.
485 /// Return the end of the live range.
486 SlotIndex leaveIntvAfter(SlotIndex Idx);
487
488 /// leaveIntvBefore - Leave the open interval before the instruction at Idx.
489 /// Return the end of the live range.
490 SlotIndex leaveIntvBefore(SlotIndex Idx);
491
492 /// leaveIntvAtTop - Leave the interval at the top of MBB.
493 /// Add liveness from the MBB top to the copy.
494 /// Return the end of the live range.
495 SlotIndex leaveIntvAtTop(MachineBasicBlock &MBB);
496
497 /// overlapIntv - Indicate that all instructions in range should use the open
498 /// interval if End does not have tied-def usage of the register and in this
499 /// case complement interval is used. Let the complement interval be live.
500 ///
501 /// This doubles the register pressure, but is sometimes required to deal with
502 /// register uses after the last valid split point.
503 ///
504 /// The Start index should be a return value from a leaveIntv* call, and End
505 /// should be in the same basic block. The parent interval must have the same
506 /// value across the range.
507 ///
508 void overlapIntv(SlotIndex Start, SlotIndex End);
509
510 /// finish - after all the new live ranges have been created, compute the
511 /// remaining live range, and rewrite instructions to use the new registers.
512 /// @param LRMap When not null, this vector will map each live range in Edit
513 /// back to the indices returned by openIntv.
514 /// There may be extra indices created by dead code elimination.
515 void finish(SmallVectorImpl<unsigned> *LRMap = nullptr);
516
517 /// dump - print the current interval mapping to dbgs().
518 void dump() const;
519
520 // ===--- High level methods ---===
521
522 /// splitSingleBlock - Split CurLI into a separate live interval around the
523 /// uses in a single block. This is intended to be used as part of a larger
524 /// split, and doesn't call finish().
525 void splitSingleBlock(const SplitAnalysis::BlockInfo &BI);
526
527 /// splitLiveThroughBlock - Split CurLI in the given block such that it
528 /// enters the block in IntvIn and leaves it in IntvOut. There may be uses in
529 /// the block, but they will be ignored when placing split points.
530 ///
531 /// @param MBBNum Block number.
532 /// @param IntvIn Interval index entering the block.
533 /// @param LeaveBefore When set, leave IntvIn before this point.
534 /// @param IntvOut Interval index leaving the block.
535 /// @param EnterAfter When set, enter IntvOut after this point.
536 void splitLiveThroughBlock(unsigned MBBNum,
537 unsigned IntvIn, SlotIndex LeaveBefore,
538 unsigned IntvOut, SlotIndex EnterAfter);
539
540 /// splitRegInBlock - Split CurLI in the given block such that it enters the
541 /// block in IntvIn and leaves it on the stack (or not at all). Split points
542 /// are placed in a way that avoids putting uses in the stack interval. This
543 /// may require creating a local interval when there is interference.
544 ///
545 /// @param BI Block descriptor.
546 /// @param IntvIn Interval index entering the block. Not 0.
547 /// @param LeaveBefore When set, leave IntvIn before this point.
548 void splitRegInBlock(const SplitAnalysis::BlockInfo &BI,
549 unsigned IntvIn, SlotIndex LeaveBefore);
550
551 /// splitRegOutBlock - Split CurLI in the given block such that it enters the
552 /// block on the stack (or isn't live-in at all) and leaves it in IntvOut.
553 /// Split points are placed to avoid interference and such that the uses are
554 /// not in the stack interval. This may require creating a local interval
555 /// when there is interference.
556 ///
557 /// @param BI Block descriptor.
558 /// @param IntvOut Interval index leaving the block.
559 /// @param EnterAfter When set, enter IntvOut after this point.
560 void splitRegOutBlock(const SplitAnalysis::BlockInfo &BI,
561 unsigned IntvOut, SlotIndex EnterAfter);
562};
563
564} // end namespace llvm
565
566#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:148
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:480
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:110
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:143
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:687
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:65
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:479
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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:243
ArrayRef< BlockInfo > getUseBlocks() const
getUseBlocks - Return an array of BlockInfo objects for the basic blocks where CurLI has uses.
Definition: SplitKit.h:200
ArrayRef< SlotIndex > getUseSlots() const
getUseSlots - Return an array of SlotIndexes of instructions using CurLI.
Definition: SplitKit.h:196
unsigned getNumThroughBlocks() const
getNumThroughBlocks - Return the number of through blocks.
Definition: SplitKit.h:203
SlotIndex getLastSplitPoint(unsigned Num)
Definition: SplitKit.h:235
const LiveInterval & getParent() const
getParent - Return the last analyzed interval.
Definition: SplitKit.h:185
bool looksLikeLoopIV() const
Definition: SplitKit.h:216
const LiveIntervals & LIS
Definition: SplitKit.h:100
const BitVector & getThroughBlocks() const
getThroughBlocks - Return the set of through blocks.
Definition: SplitKit.h:209
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:212
SlotIndex getLastSplitPoint(MachineBasicBlock *BB)
Definition: SplitKit.h:239
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:206
SlotIndex getFirstSplitPoint(unsigned Num)
Definition: SplitKit.h:247
SplitEditor - Edit machine code and LiveIntervals for live range splitting.
Definition: SplitKit.h:263
unsigned currentIntv() const
currentIntv - Return the current interval index.
Definition: SplitKit.h:459
ComplementSpillMode
ComplementSpillMode - Select how the complement live range should be created.
Definition: SplitKit.h:281
@ SM_Partition
SM_Partition(Default) - Try to create the complement interval so it doesn't overlap any other interva...
Definition: SplitKit.h:286
@ SM_Size
SM_Size - Overlap intervals to minimize the number of inserted COPY instructions.
Definition: SplitKit.h:293
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