LLVM  13.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  /// DidRepairRange - analyze was forced to shrinkToUses().
164  bool DidRepairRange;
165 
166  // Sumarize statistics by counting instructions using CurLI.
167  void analyzeUses();
168 
169  /// calcLiveBlockInfo - Compute per-block information about CurLI.
170  bool calcLiveBlockInfo();
171 
172 public:
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  /// didRepairRange() - Returns true if CurLI was invalid and has been repaired
181  /// by analyze(). This really shouldn't happen, but sometimes the coalescer
182  /// can create live ranges that end in mid-air.
183  bool didRepairRange() const { return DidRepairRange; }
184 
185  /// clear - clear all data structures so SplitAnalysis is ready to analyze a
186  /// new interval.
187  void clear();
188 
189  /// getParent - Return the last analyzed interval.
190  const LiveInterval &getParent() const { return *CurLI; }
191 
192  /// isOriginalEndpoint - Return true if the original live range was killed or
193  /// (re-)defined at Idx. Idx should be the 'def' slot for a normal kill/def,
194  /// and 'use' for an early-clobber def.
195  /// This can be used to recognize code inserted by earlier live range
196  /// splitting.
197  bool isOriginalEndpoint(SlotIndex Idx) const;
198 
199  /// getUseSlots - Return an array of SlotIndexes of instructions using CurLI.
200  /// This include both use and def operands, at most one entry per instruction.
201  ArrayRef<SlotIndex> getUseSlots() const { return UseSlots; }
202 
203  /// getUseBlocks - Return an array of BlockInfo objects for the basic blocks
204  /// where CurLI has uses.
205  ArrayRef<BlockInfo> getUseBlocks() const { return UseBlocks; }
206 
207  /// getNumThroughBlocks - Return the number of through blocks.
208  unsigned getNumThroughBlocks() const { return NumThroughBlocks; }
209 
210  /// isThroughBlock - Return true if CurLI is live through MBB without uses.
211  bool isThroughBlock(unsigned MBB) const { return ThroughBlocks.test(MBB); }
212 
213  /// getThroughBlocks - Return the set of through blocks.
214  const BitVector &getThroughBlocks() const { return ThroughBlocks; }
215 
216  /// getNumLiveBlocks - Return the number of blocks where CurLI is live.
217  unsigned getNumLiveBlocks() const {
218  return getUseBlocks().size() - NumGapBlocks + getNumThroughBlocks();
219  }
220 
221  /// countLiveBlocks - Return the number of blocks where li is live. This is
222  /// guaranteed to return the same number as getNumLiveBlocks() after calling
223  /// analyze(li).
224  unsigned countLiveBlocks(const LiveInterval *li) const;
225 
227 
228  /// shouldSplitSingleBlock - Returns true if it would help to create a local
229  /// live range for the instructions in BI. There is normally no benefit to
230  /// creating a live range for a single instruction, but it does enable
231  /// register class inflation if the instruction has a restricted register
232  /// class.
233  ///
234  /// @param BI The block to be isolated.
235  /// @param SingleInstrs True when single instructions should be isolated.
236  bool shouldSplitSingleBlock(const BlockInfo &BI, bool SingleInstrs) const;
237 
238  SlotIndex getLastSplitPoint(unsigned Num) {
239  return IPA.getLastInsertPoint(*CurLI, *MF.getBlockNumbered(Num));
240  }
241 
243  return IPA.getLastInsertPoint(*CurLI, *BB);
244  }
245 
247  return IPA.getLastInsertPointIter(*CurLI, *BB);
248  }
249 
251  return IPA.getFirstInsertPoint(*MF.getBlockNumbered(Num));
252  }
253 };
254 
255 /// SplitEditor - Edit machine code and LiveIntervals for live range
256 /// splitting.
257 ///
258 /// - Create a SplitEditor from a SplitAnalysis.
259 /// - Start a new live interval with openIntv.
260 /// - Mark the places where the new interval is entered using enterIntv*
261 /// - Mark the ranges where the new interval is used with useIntv*
262 /// - Mark the places where the interval is exited with exitIntv*.
263 /// - Finish the current interval with closeIntv and repeat from 2.
264 /// - Rewrite instructions with finish().
265 ///
267  SplitAnalysis &SA;
268  AAResults &AA;
269  LiveIntervals &LIS;
270  VirtRegMap &VRM;
273  const TargetInstrInfo &TII;
274  const TargetRegisterInfo &TRI;
275  const MachineBlockFrequencyInfo &MBFI;
276  VirtRegAuxInfo &VRAI;
277 
278 public:
279  /// ComplementSpillMode - Select how the complement live range should be
280  /// created. SplitEditor automatically creates interval 0 to contain
281  /// anything that isn't added to another interval. This complement interval
282  /// can get quite complicated, and it can sometimes be an advantage to allow
283  /// it to overlap the other intervals. If it is going to spill anyway, no
284  /// registers are wasted by keeping a value in two places at the same time.
286  /// SM_Partition(Default) - Try to create the complement interval so it
287  /// doesn't overlap any other intervals, and the original interval is
288  /// partitioned. This may require a large number of back copies and extra
289  /// PHI-defs. Only segments marked with overlapIntv will be overlapping.
291 
292  /// SM_Size - Overlap intervals to minimize the number of inserted COPY
293  /// instructions. Copies to the complement interval are hoisted to their
294  /// common dominator, so only one COPY is required per value in the
295  /// complement interval. This also means that no extra PHI-defs need to be
296  /// inserted in the complement interval.
298 
299  /// SM_Speed - Overlap intervals to minimize the expected execution
300  /// frequency of the inserted copies. This is very similar to SM_Size, but
301  /// the complement interval may get some extra PHI-defs.
302  SM_Speed
303  };
304 
305 private:
306  /// Edit - The current parent register and new intervals created.
307  LiveRangeEdit *Edit = nullptr;
308 
309  /// Index into Edit of the currently open interval.
310  /// The index 0 is used for the complement, so the first interval started by
311  /// openIntv will be 1.
312  unsigned OpenIdx = 0;
313 
314  /// The current spill mode, selected by reset().
315  ComplementSpillMode SpillMode = SM_Partition;
316 
317  using RegAssignMap = IntervalMap<SlotIndex, unsigned>;
318 
319  /// Allocator for the interval map. This will eventually be shared with
320  /// SlotIndexes and LiveIntervals.
322 
323  /// RegAssign - Map of the assigned register indexes.
324  /// Edit.get(RegAssign.lookup(Idx)) is the register that should be live at
325  /// Idx.
326  RegAssignMap RegAssign;
327 
328  using ValueForcePair = PointerIntPair<VNInfo *, 1>;
329  using ValueMap = DenseMap<std::pair<unsigned, unsigned>, ValueForcePair>;
330 
331  /// Values - keep track of the mapping from parent values to values in the new
332  /// intervals. Given a pair (RegIdx, ParentVNI->id), Values contains:
333  ///
334  /// 1. No entry - the value is not mapped to Edit.get(RegIdx).
335  /// 2. (Null, false) - the value is mapped to multiple values in
336  /// Edit.get(RegIdx). Each value is represented by a minimal live range at
337  /// its def. The full live range can be inferred exactly from the range
338  /// of RegIdx in RegAssign.
339  /// 3. (Null, true). As above, but the ranges in RegAssign are too large, and
340  /// the live range must be recomputed using ::extend().
341  /// 4. (VNI, false) The value is mapped to a single new value.
342  /// The new value has no live ranges anywhere.
343  ValueMap Values;
344 
345  /// LICalc - Cache for computing live ranges and SSA update. Each instance
346  /// can only handle non-overlapping live ranges, so use a separate
347  /// LiveIntervalCalc instance for the complement interval when in spill mode.
348  LiveIntervalCalc LICalc[2];
349 
350  /// getLICalc - Return the LICalc to use for RegIdx. In spill mode, the
351  /// complement interval can overlap the other intervals, so it gets its own
352  /// LICalc instance. When not in spill mode, all intervals can share one.
353  LiveIntervalCalc &getLICalc(unsigned RegIdx) {
354  return LICalc[SpillMode != SM_Partition && RegIdx != 0];
355  }
356 
357  /// Find a subrange corresponding to the exact lane mask @p LM in the live
358  /// interval @p LI. The interval @p LI is assumed to contain such a subrange.
359  /// This function is used to find corresponding subranges between the
360  /// original interval and the new intervals.
361  LiveInterval::SubRange &getSubRangeForMaskExact(LaneBitmask LM,
362  LiveInterval &LI);
363 
364  /// Find a subrange corresponding to the lane mask @p LM, or a superset of it,
365  /// in the live interval @p LI. The interval @p LI is assumed to contain such
366  /// a subrange. This function is used to find corresponding subranges between
367  /// the original interval and the new intervals.
368  LiveInterval::SubRange &getSubRangeForMask(LaneBitmask LM, LiveInterval &LI);
369 
370  /// Add a segment to the interval LI for the value number VNI. If LI has
371  /// subranges, corresponding segments will be added to them as well, but
372  /// with newly created value numbers. If Original is true, dead def will
373  /// only be added a subrange of LI if the corresponding subrange of the
374  /// original interval has a def at this index. Otherwise, all subranges
375  /// of LI will be updated.
376  void addDeadDef(LiveInterval &LI, VNInfo *VNI, bool Original);
377 
378  /// defValue - define a value in RegIdx from ParentVNI at Idx.
379  /// Idx does not have to be ParentVNI->def, but it must be contained within
380  /// ParentVNI's live range in ParentLI. The new value is added to the value
381  /// map. The value being defined may either come from rematerialization
382  /// (or an inserted copy), or it may be coming from the original interval.
383  /// The parameter Original should be true in the latter case, otherwise
384  /// it should be false.
385  /// Return the new LI value.
386  VNInfo *defValue(unsigned RegIdx, const VNInfo *ParentVNI, SlotIndex Idx,
387  bool Original);
388 
389  /// forceRecompute - Force the live range of ParentVNI in RegIdx to be
390  /// recomputed by LiveRangeCalc::extend regardless of the number of defs.
391  /// This is used for values whose live range doesn't match RegAssign exactly.
392  /// They could have rematerialized, or back-copies may have been moved.
393  void forceRecompute(unsigned RegIdx, const VNInfo &ParentVNI);
394 
395  /// Calls forceRecompute() on any affected regidx and on ParentVNI
396  /// predecessors in case of a phi definition.
397  void forceRecomputeVNI(const VNInfo &ParentVNI);
398 
399  /// defFromParent - Define Reg from ParentVNI at UseIdx using either
400  /// rematerialization or a COPY from parent. Return the new value.
401  VNInfo *defFromParent(unsigned RegIdx,
402  VNInfo *ParentVNI,
403  SlotIndex UseIdx,
404  MachineBasicBlock &MBB,
406 
407  /// removeBackCopies - Remove the copy instructions that defines the values
408  /// in the vector in the complement interval.
409  void removeBackCopies(SmallVectorImpl<VNInfo*> &Copies);
410 
411  /// getShallowDominator - Returns the least busy dominator of MBB that is
412  /// also dominated by DefMBB. Busy is measured by loop depth.
413  MachineBasicBlock *findShallowDominator(MachineBasicBlock *MBB,
414  MachineBasicBlock *DefMBB);
415 
416  /// Find out all the backCopies dominated by others.
417  void computeRedundantBackCopies(DenseSet<unsigned> &NotToHoistSet,
418  SmallVectorImpl<VNInfo *> &BackCopies);
419 
420  /// Hoist back-copies to the complement interval. It tries to hoist all
421  /// the back-copies to one BB if it is beneficial, or else simply remove
422  /// redundant backcopies dominated by others.
423  void hoistCopies();
424 
425  /// transferValues - Transfer values to the new ranges.
426  /// Return true if any ranges were skipped.
427  bool transferValues();
428 
429  /// Live range @p LR corresponding to the lane Mask @p LM has a live
430  /// PHI def at the beginning of block @p B. Extend the range @p LR of
431  /// all predecessor values that reach this def. If @p LR is a subrange,
432  /// the array @p Undefs is the set of all locations where it is undefined
433  /// via <def,read-undef> in other subranges for the same register.
434  void extendPHIRange(MachineBasicBlock &B, LiveIntervalCalc &LIC,
435  LiveRange &LR, LaneBitmask LM,
436  ArrayRef<SlotIndex> Undefs);
437 
438  /// extendPHIKillRanges - Extend the ranges of all values killed by original
439  /// parent PHIDefs.
440  void extendPHIKillRanges();
441 
442  /// rewriteAssigned - Rewrite all uses of Edit.getReg() to assigned registers.
443  void rewriteAssigned(bool ExtendRanges);
444 
445  /// deleteRematVictims - Delete defs that are dead after rematerializing.
446  void deleteRematVictims();
447 
448  /// Add a copy instruction copying \p FromReg to \p ToReg before
449  /// \p InsertBefore. This can be invoked with a \p LaneMask which may make it
450  /// necessary to construct a sequence of copies to cover it exactly.
451  SlotIndex buildCopy(Register FromReg, Register ToReg, LaneBitmask LaneMask,
452  MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
453  bool Late, unsigned RegIdx);
454 
455  SlotIndex buildSingleSubRegCopy(Register FromReg, Register ToReg,
456  MachineBasicBlock &MB, MachineBasicBlock::iterator InsertBefore,
457  unsigned SubIdx, LiveInterval &DestLI, bool Late, SlotIndex Def);
458 
459 public:
460  /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
461  /// Newly created intervals will be appended to newIntervals.
462  SplitEditor(SplitAnalysis &SA, AAResults &AA, LiveIntervals &LIS,
463  VirtRegMap &VRM, MachineDominatorTree &MDT,
464  MachineBlockFrequencyInfo &MBFI, VirtRegAuxInfo &VRAI);
465 
466  /// reset - Prepare for a new split.
467  void reset(LiveRangeEdit&, ComplementSpillMode = SM_Partition);
468 
469  /// Create a new virtual register and live interval.
470  /// Return the interval index, starting from 1. Interval index 0 is the
471  /// implicit complement interval.
472  unsigned openIntv();
473 
474  /// currentIntv - Return the current interval index.
475  unsigned currentIntv() const { return OpenIdx; }
476 
477  /// selectIntv - Select a previously opened interval index.
478  void selectIntv(unsigned Idx);
479 
480  /// enterIntvBefore - Enter the open interval before the instruction at Idx.
481  /// If the parent interval is not live before Idx, a COPY is not inserted.
482  /// Return the beginning of the new live range.
483  SlotIndex enterIntvBefore(SlotIndex Idx);
484 
485  /// enterIntvAfter - Enter the open interval after the instruction at Idx.
486  /// Return the beginning of the new live range.
487  SlotIndex enterIntvAfter(SlotIndex Idx);
488 
489  /// enterIntvAtEnd - Enter the open interval at the end of MBB.
490  /// Use the open interval from the inserted copy to the MBB end.
491  /// Return the beginning of the new live range.
492  SlotIndex enterIntvAtEnd(MachineBasicBlock &MBB);
493 
494  /// useIntv - indicate that all instructions in MBB should use OpenLI.
495  void useIntv(const MachineBasicBlock &MBB);
496 
497  /// useIntv - indicate that all instructions in range should use OpenLI.
498  void useIntv(SlotIndex Start, SlotIndex End);
499 
500  /// leaveIntvAfter - Leave the open interval after the instruction at Idx.
501  /// Return the end of the live range.
502  SlotIndex leaveIntvAfter(SlotIndex Idx);
503 
504  /// leaveIntvBefore - Leave the open interval before the instruction at Idx.
505  /// Return the end of the live range.
506  SlotIndex leaveIntvBefore(SlotIndex Idx);
507 
508  /// leaveIntvAtTop - Leave the interval at the top of MBB.
509  /// Add liveness from the MBB top to the copy.
510  /// Return the end of the live range.
511  SlotIndex leaveIntvAtTop(MachineBasicBlock &MBB);
512 
513  /// overlapIntv - Indicate that all instructions in range should use the open
514  /// interval if End does not have tied-def usage of the register and in this
515  /// case compliment interval is used. Let the complement interval be live.
516  ///
517  /// This doubles the register pressure, but is sometimes required to deal with
518  /// register uses after the last valid split point.
519  ///
520  /// The Start index should be a return value from a leaveIntv* call, and End
521  /// should be in the same basic block. The parent interval must have the same
522  /// value across the range.
523  ///
524  void overlapIntv(SlotIndex Start, SlotIndex End);
525 
526  /// finish - after all the new live ranges have been created, compute the
527  /// remaining live range, and rewrite instructions to use the new registers.
528  /// @param LRMap When not null, this vector will map each live range in Edit
529  /// back to the indices returned by openIntv.
530  /// There may be extra indices created by dead code elimination.
531  void finish(SmallVectorImpl<unsigned> *LRMap = nullptr);
532 
533  /// dump - print the current interval mapping to dbgs().
534  void dump() const;
535 
536  // ===--- High level methods ---===
537 
538  /// splitSingleBlock - Split CurLI into a separate live interval around the
539  /// uses in a single block. This is intended to be used as part of a larger
540  /// split, and doesn't call finish().
541  void splitSingleBlock(const SplitAnalysis::BlockInfo &BI);
542 
543  /// splitLiveThroughBlock - Split CurLI in the given block such that it
544  /// enters the block in IntvIn and leaves it in IntvOut. There may be uses in
545  /// the block, but they will be ignored when placing split points.
546  ///
547  /// @param MBBNum Block number.
548  /// @param IntvIn Interval index entering the block.
549  /// @param LeaveBefore When set, leave IntvIn before this point.
550  /// @param IntvOut Interval index leaving the block.
551  /// @param EnterAfter When set, enter IntvOut after this point.
552  void splitLiveThroughBlock(unsigned MBBNum,
553  unsigned IntvIn, SlotIndex LeaveBefore,
554  unsigned IntvOut, SlotIndex EnterAfter);
555 
556  /// splitRegInBlock - Split CurLI in the given block such that it enters the
557  /// block in IntvIn and leaves it on the stack (or not at all). Split points
558  /// are placed in a way that avoids putting uses in the stack interval. This
559  /// may require creating a local interval when there is interference.
560  ///
561  /// @param BI Block descriptor.
562  /// @param IntvIn Interval index entering the block. Not 0.
563  /// @param LeaveBefore When set, leave IntvIn before this point.
564  void splitRegInBlock(const SplitAnalysis::BlockInfo &BI,
565  unsigned IntvIn, SlotIndex LeaveBefore);
566 
567  /// splitRegOutBlock - Split CurLI in the given block such that it enters the
568  /// block on the stack (or isn't live-in at all) and leaves it in IntvOut.
569  /// Split points are placed to avoid interference and such that the uses are
570  /// not in the stack interval. This may require creating a local interval
571  /// when there is interference.
572  ///
573  /// @param BI Block descriptor.
574  /// @param IntvOut Interval index leaving the block.
575  /// @param EnterAfter When set, enter IntvOut after this point.
576  void splitRegOutBlock(const SplitAnalysis::BlockInfo &BI,
577  unsigned IntvOut, SlotIndex EnterAfter);
578 };
579 
580 } // end namespace llvm
581 
582 #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:217
llvm::SplitAnalysis::BlockInfo::LiveIn
bool LiveIn
Current reg is live in.
Definition: SplitKit.h:127
llvm
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:250
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:231
llvm::SplitAnalysis::getUseSlots
ArrayRef< SlotIndex > getUseSlots() const
getUseSlots - Return an array of SlotIndexes of instructions using CurLI.
Definition: SplitKit.h:201
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:266
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:1567
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:233
llvm::SplitEditor::SM_Size
@ SM_Size
SM_Size - Overlap intervals to minimize the number of inserted COPY instructions.
Definition: SplitKit.h:297
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:456
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:290
llvm::SplitAnalysis::didRepairRange
bool didRepairRange() const
didRepairRange() - Returns true if CurLI was invalid and has been repaired by analyze().
Definition: SplitKit.h:183
llvm::SplitAnalysis::getLastSplitPointIter
MachineBasicBlock::iterator getLastSplitPointIter(MachineBasicBlock *BB)
Definition: SplitKit.h:246
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:50
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:214
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:205
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:190
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
llvm::SplitAnalysis::MF
const MachineFunction & MF
Definition: SplitKit.h:99
llvm::MachineFunction
Definition: MachineFunction.h:230
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:675
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:285
llvm::SplitAnalysis::getNumThroughBlocks
unsigned getNumThroughBlocks() const
getNumThroughBlocks - Return the number of through blocks.
Definition: SplitKit.h:208
llvm::SplitAnalysis::isThroughBlock
bool isThroughBlock(unsigned MBB) const
isThroughBlock - Return true if CurLI is live through MBB without uses.
Definition: SplitKit.h:211
llvm::LiveIntervals
Definition: LiveIntervals.h:54
llvm::SplitEditor::currentIntv
unsigned currentIntv() const
currentIntv - Return the current interval index.
Definition: SplitKit.h:475
LiveInterval.h
llvm::SplitAnalysis::getLastSplitPoint
SlotIndex getLastSplitPoint(unsigned Num)
Definition: SplitKit.h:238
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:45
MachineFunction.h
llvm::MachineInstrBundleIterator< MachineInstr >
llvm::SplitAnalysis::getLastSplitPoint
SlotIndex getLastSplitPoint(MachineBasicBlock *BB)
Definition: SplitKit.h:242
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:141
llvm::SplitAnalysis
SplitAnalysis - Analyze a LiveInterval, looking for live range splitting opportunities.
Definition: SplitKit.h:97