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