LLVM  16.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"
21 #include "llvm/ADT/IntervalMap.h"
23 #include "llvm/ADT/SmallPtrSet.h"
24 #include "llvm/ADT/SmallVector.h"
30 #include "llvm/Support/Compiler.h"
31 #include <utility>
32 
33 namespace llvm {
34 
35 class LiveInterval;
36 class LiveRange;
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 class 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.
51 private:
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 
63 public:
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.
97 public:
99  const VirtRegMap &VRM;
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 
139 private:
140  // Current live interval.
141  const LiveInterval *CurLI = nullptr;
142 
143  /// Insert Point Analysis.
145 
146  // Sorted slot indexes of using instructions.
147  SmallVector<SlotIndex, 8> UseSlots;
148 
149  /// UseBlocks - Blocks where CurLI has uses.
150  SmallVector<BlockInfo, 8> UseBlocks;
151 
152  /// NumGapBlocks - Number of duplicate entries in UseBlocks for blocks where
153  /// the live range has a gap.
154  unsigned NumGapBlocks;
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;
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 
168 public:
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 
229  SlotIndex getLastSplitPoint(unsigned Num) {
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 
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.
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 
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.
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,
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, MachineBasicBlock::iterator InsertBefore,
432  unsigned SubIdx, LiveInterval &DestLI, bool Late, SlotIndex Def);
433 
434 public:
435  /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
436  /// Newly created intervals will be appended to newIntervals.
437  SplitEditor(SplitAnalysis &SA, LiveIntervals &LIS, VirtRegMap &VRM,
438  MachineDominatorTree &MDT, MachineBlockFrequencyInfo &MBFI,
439  VirtRegAuxInfo &VRAI);
440 
441  /// reset - Prepare for a new split.
442  void reset(LiveRangeEdit&, ComplementSpillMode = SM_Partition);
443 
444  /// Create a new virtual register and live interval.
445  /// Return the interval index, starting from 1. Interval index 0 is the
446  /// implicit complement interval.
447  unsigned openIntv();
448 
449  /// currentIntv - Return the current interval index.
450  unsigned currentIntv() const { return OpenIdx; }
451 
452  /// selectIntv - Select a previously opened interval index.
453  void selectIntv(unsigned Idx);
454 
455  /// enterIntvBefore - Enter the open interval before the instruction at Idx.
456  /// If the parent interval is not live before Idx, a COPY is not inserted.
457  /// Return the beginning of the new live range.
458  SlotIndex enterIntvBefore(SlotIndex Idx);
459 
460  /// enterIntvAfter - Enter the open interval after the instruction at Idx.
461  /// Return the beginning of the new live range.
462  SlotIndex enterIntvAfter(SlotIndex Idx);
463 
464  /// enterIntvAtEnd - Enter the open interval at the end of MBB.
465  /// Use the open interval from the inserted copy to the MBB end.
466  /// Return the beginning of the new live range.
467  SlotIndex enterIntvAtEnd(MachineBasicBlock &MBB);
468 
469  /// useIntv - indicate that all instructions in MBB should use OpenLI.
470  void useIntv(const MachineBasicBlock &MBB);
471 
472  /// useIntv - indicate that all instructions in range should use OpenLI.
473  void useIntv(SlotIndex Start, SlotIndex End);
474 
475  /// leaveIntvAfter - Leave the open interval after the instruction at Idx.
476  /// Return the end of the live range.
477  SlotIndex leaveIntvAfter(SlotIndex Idx);
478 
479  /// leaveIntvBefore - Leave the open interval before the instruction at Idx.
480  /// Return the end of the live range.
481  SlotIndex leaveIntvBefore(SlotIndex Idx);
482 
483  /// leaveIntvAtTop - Leave the interval at the top of MBB.
484  /// Add liveness from the MBB top to the copy.
485  /// Return the end of the live range.
486  SlotIndex leaveIntvAtTop(MachineBasicBlock &MBB);
487 
488  /// overlapIntv - Indicate that all instructions in range should use the open
489  /// interval if End does not have tied-def usage of the register and in this
490  /// case compliment interval is used. Let the complement interval be live.
491  ///
492  /// This doubles the register pressure, but is sometimes required to deal with
493  /// register uses after the last valid split point.
494  ///
495  /// The Start index should be a return value from a leaveIntv* call, and End
496  /// should be in the same basic block. The parent interval must have the same
497  /// value across the range.
498  ///
499  void overlapIntv(SlotIndex Start, SlotIndex End);
500 
501  /// finish - after all the new live ranges have been created, compute the
502  /// remaining live range, and rewrite instructions to use the new registers.
503  /// @param LRMap When not null, this vector will map each live range in Edit
504  /// back to the indices returned by openIntv.
505  /// There may be extra indices created by dead code elimination.
506  void finish(SmallVectorImpl<unsigned> *LRMap = nullptr);
507 
508  /// dump - print the current interval mapping to dbgs().
509  void dump() const;
510 
511  // ===--- High level methods ---===
512 
513  /// splitSingleBlock - Split CurLI into a separate live interval around the
514  /// uses in a single block. This is intended to be used as part of a larger
515  /// split, and doesn't call finish().
516  void splitSingleBlock(const SplitAnalysis::BlockInfo &BI);
517 
518  /// splitLiveThroughBlock - Split CurLI in the given block such that it
519  /// enters the block in IntvIn and leaves it in IntvOut. There may be uses in
520  /// the block, but they will be ignored when placing split points.
521  ///
522  /// @param MBBNum Block number.
523  /// @param IntvIn Interval index entering the block.
524  /// @param LeaveBefore When set, leave IntvIn before this point.
525  /// @param IntvOut Interval index leaving the block.
526  /// @param EnterAfter When set, enter IntvOut after this point.
527  void splitLiveThroughBlock(unsigned MBBNum,
528  unsigned IntvIn, SlotIndex LeaveBefore,
529  unsigned IntvOut, SlotIndex EnterAfter);
530 
531  /// splitRegInBlock - Split CurLI in the given block such that it enters the
532  /// block in IntvIn and leaves it on the stack (or not at all). Split points
533  /// are placed in a way that avoids putting uses in the stack interval. This
534  /// may require creating a local interval when there is interference.
535  ///
536  /// @param BI Block descriptor.
537  /// @param IntvIn Interval index entering the block. Not 0.
538  /// @param LeaveBefore When set, leave IntvIn before this point.
539  void splitRegInBlock(const SplitAnalysis::BlockInfo &BI,
540  unsigned IntvIn, SlotIndex LeaveBefore);
541 
542  /// splitRegOutBlock - Split CurLI in the given block such that it enters the
543  /// block on the stack (or isn't live-in at all) and leaves it in IntvOut.
544  /// Split points are placed to avoid interference and such that the uses are
545  /// not in the stack interval. This may require creating a local interval
546  /// when there is interference.
547  ///
548  /// @param BI Block descriptor.
549  /// @param IntvOut Interval index leaving the block.
550  /// @param EnterAfter When set, enter IntvOut after this point.
551  void splitRegOutBlock(const SplitAnalysis::BlockInfo &BI,
552  unsigned IntvOut, SlotIndex EnterAfter);
553 };
554 
555 } // end namespace llvm
556 
557 #endif // LLVM_LIB_CODEGEN_SPLITKIT_H
llvm::SplitAnalysis::getNumLiveBlocks
unsigned getNumLiveBlocks() const
getNumLiveBlocks - Return the number of blocks where CurLI is live.
Definition: SplitKit.h:208
llvm::SplitAnalysis::BlockInfo::LiveIn
bool LiveIn
Current reg is live in.
Definition: SplitKit.h:126
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::SplitAnalysis::BlockInfo::FirstInstr
SlotIndex FirstInstr
First instr accessing current reg.
Definition: SplitKit.h:123
llvm::SplitAnalysis::BlockInfo::isOneInstr
bool isOneInstr() const
isOneInstr - Returns true when this BlockInfo describes a single instruction.
Definition: SplitKit.h:131
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
llvm::SplitAnalysis::getFirstSplitPoint
SlotIndex getFirstSplitPoint(unsigned Num)
Definition: SplitKit.h:241
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
llvm::VirtRegAuxInfo
Calculate auxiliary information for a virtual register such as its spill weight and allocation hint.
Definition: CalcSpillWeights.h:45
llvm::VirtRegMap
Definition: VirtRegMap.h:33
MachineBasicBlock.h
llvm::SplitAnalysis::BlockInfo
Additional information about basic blocks where the current variable is live.
Definition: SplitKit.h:121
llvm::InsertPointAnalysis
Determines the latest safe point in a block in which we can insert a split, spill or other instructio...
Definition: SplitKit.h:50
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:237
llvm::SplitAnalysis::getUseSlots
ArrayRef< SlotIndex > getUseSlots() const
getUseSlots - Return an array of SlotIndexes of instructions using CurLI.
Definition: SplitKit.h:192
DenseMap.h
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:877
llvm::SplitEditor
SplitEditor - Edit machine code and LiveIntervals for live range splitting.
Definition: SplitKit.h:257
llvm::SplitAnalysis::BlockInfo::FirstDef
SlotIndex FirstDef
First non-phi valno->def, or SlotIndex().
Definition: SplitKit.h:125
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
llvm::LiveIntervals::getInstructionIndex
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
Definition: LiveIntervals.h:220
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:89
PointerIntPair.h
clear
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:149
llvm::SplitEditor::SM_Size
@ SM_Size
SM_Size - Overlap intervals to minimize the number of inserted COPY instructions.
Definition: SplitKit.h:287
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:98
llvm::SplitAnalysis::LIS
const LiveIntervals & LIS
Definition: SplitKit.h:100
llvm::SplitAnalysis::Loops
const MachineLoopInfo & Loops
Definition: SplitKit.h:101
llvm::LiveIntervalCalc
Definition: LiveIntervalCalc.h:28
llvm::MachineBlockFrequencyInfo
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
Definition: MachineBlockFrequencyInfo.h:33
llvm::LiveIntervals::getMBBStartIdx
SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const
Return the first index in the given basic block.
Definition: LiveIntervals.h:230
llvm::SplitEditor::SM_Partition
@ SM_Partition
SM_Partition(Default) - Try to create the complement interval so it doesn't overlap any other interva...
Definition: SplitKit.h:280
llvm::SplitAnalysis::getLastSplitPointIter
MachineBasicBlock::iterator getLastSplitPointIter(MachineBasicBlock *BB)
Definition: SplitKit.h:237
DenseSet.h
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::LiveRangeEdit
Definition: LiveRangeEdit.h:43
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
BitVector.h
SmallPtrSet.h
Copies
SI Lower i1 Copies
Definition: SILowerI1Copies.cpp:397
llvm::BitVector
Definition: BitVector.h:75
llvm::LiveInterval
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:686
llvm::SlotIndex
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:82
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
LiveIntervalCalc.h
llvm::SplitAnalysis::BlockInfo::LastInstr
SlotIndex LastInstr
Last instr accessing current reg.
Definition: SplitKit.h:124
llvm::SplitAnalysis::getThroughBlocks
const BitVector & getThroughBlocks() const
getThroughBlocks - Return the set of through blocks.
Definition: SplitKit.h:205
LiveIntervals.h
llvm::SplitAnalysis::BlockInfo::LiveOut
bool LiveOut
Current reg is live out.
Definition: SplitKit.h:127
llvm::SplitAnalysis::VRM
const VirtRegMap & VRM
Definition: SplitKit.h:99
llvm::DenseMap
Definition: DenseMap.h:714
llvm::SplitAnalysis::getUseBlocks
ArrayRef< BlockInfo > getUseBlocks() const
getUseBlocks - Return an array of BlockInfo objects for the basic blocks where CurLI has uses.
Definition: SplitKit.h:196
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::SlotIndex::isSameInstr
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
Definition: SlotIndexes.h:198
ArrayRef.h
llvm::SplitAnalysis::getParent
const LiveInterval & getParent() const
getParent - Return the last analyzed interval.
Definition: SplitKit.h:181
llvm::InsertPointAnalysis::getLastInsertPoint
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
LiveRange
SI Optimize VGPR LiveRange
Definition: SIOptimizeVGPRLiveRange.cpp:616
llvm::SplitAnalysis::MF
const MachineFunction & MF
Definition: SplitKit.h:98
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::print
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
Definition: GCNRegPressure.cpp:138
llvm::MachineBasicBlock::iterator
MachineInstrBundleIterator< MachineInstr > iterator
Definition: MachineBasicBlock.h:269
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
Compiler.h
LLVM_LIBRARY_VISIBILITY
#define LLVM_LIBRARY_VISIBILITY
LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked into a shared library,...
Definition: Compiler.h:126
llvm::SplitAnalysis::BlockInfo::MBB
MachineBasicBlock * MBB
Definition: SplitKit.h:122
llvm::ValueMap
See the file comment.
Definition: ValueMap.h:85
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::SplitAnalysis::TII
const TargetInstrInfo & TII
Definition: SplitKit.h:102
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::MachineFunction::getBlockNumbered
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
Definition: MachineFunction.h:789
llvm::BitVector::test
bool test(unsigned Idx) const
Definition: BitVector.h:454
llvm::SplitEditor::ComplementSpillMode
ComplementSpillMode
ComplementSpillMode - Select how the complement live range should be created.
Definition: SplitKit.h:275
llvm::SplitAnalysis::getNumThroughBlocks
unsigned getNumThroughBlocks() const
getNumThroughBlocks - Return the number of through blocks.
Definition: SplitKit.h:199
llvm::SplitAnalysis::isThroughBlock
bool isThroughBlock(unsigned MBB) const
isThroughBlock - Return true if CurLI is live through MBB without uses.
Definition: SplitKit.h:202
llvm::LiveIntervals
Definition: LiveIntervals.h:53
llvm::SplitEditor::currentIntv
unsigned currentIntv() const
currentIntv - Return the current interval index.
Definition: SplitKit.h:450
llvm::SplitAnalysis::getLastSplitPoint
SlotIndex getLastSplitPoint(unsigned Num)
Definition: SplitKit.h:229
llvm::PointerIntPair
PointerIntPair - This class implements a pair of a pointer and small integer.
Definition: PointerIntPair.h:46
SmallVector.h
IntervalMap.h
Allocator
Basic Register Allocator
Definition: RegAllocBasic.cpp:143
llvm::IntervalMap< SlotIndex, unsigned >
llvm::SmallVectorImpl< unsigned >
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::InsertPointAnalysis::getFirstInsertPoint
SlotIndex getFirstInsertPoint(MachineBasicBlock &MBB)
Return the base index of the first insert point in \pMBB.
Definition: SplitKit.h:82
SlotIndexes.h
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:51
MachineFunction.h
llvm::MachineInstrBundleIterator< MachineInstr >
llvm::SplitAnalysis::getLastSplitPoint
SlotIndex getLastSplitPoint(MachineBasicBlock *BB)
Definition: SplitKit.h:233
llvm::InsertPointAnalysis::getLastInsertPointIter
MachineBasicBlock::iterator getLastInsertPointIter(const LiveInterval &CurLI, MachineBasicBlock &MBB)
Returns the last insert point as an iterator for \pCurLI in \pMBB.
Definition: SplitKit.cpp:140
llvm::SplitAnalysis
SplitAnalysis - Analyze a LiveInterval, looking for live range splitting opportunities.
Definition: SplitKit.h:96