109467b48Spatrick //===- SplitKit.h - Toolkit for splitting live ranges -----------*- C++ -*-===// 209467b48Spatrick // 309467b48Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 409467b48Spatrick // See https://llvm.org/LICENSE.txt for license information. 509467b48Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 609467b48Spatrick // 709467b48Spatrick //===----------------------------------------------------------------------===// 809467b48Spatrick // 909467b48Spatrick // This file contains the SplitAnalysis class as well as mutator functions for 1009467b48Spatrick // live range splitting. 1109467b48Spatrick // 1209467b48Spatrick //===----------------------------------------------------------------------===// 1309467b48Spatrick 1409467b48Spatrick #ifndef LLVM_LIB_CODEGEN_SPLITKIT_H 1509467b48Spatrick #define LLVM_LIB_CODEGEN_SPLITKIT_H 1609467b48Spatrick 1709467b48Spatrick #include "llvm/ADT/ArrayRef.h" 1809467b48Spatrick #include "llvm/ADT/BitVector.h" 1909467b48Spatrick #include "llvm/ADT/DenseMap.h" 2009467b48Spatrick #include "llvm/ADT/DenseSet.h" 2109467b48Spatrick #include "llvm/ADT/IntervalMap.h" 2209467b48Spatrick #include "llvm/ADT/PointerIntPair.h" 2309467b48Spatrick #include "llvm/ADT/SmallPtrSet.h" 2409467b48Spatrick #include "llvm/ADT/SmallVector.h" 25097a140dSpatrick #include "llvm/CodeGen/LiveIntervalCalc.h" 2609467b48Spatrick #include "llvm/CodeGen/LiveIntervals.h" 2709467b48Spatrick #include "llvm/CodeGen/MachineBasicBlock.h" 2809467b48Spatrick #include "llvm/CodeGen/MachineFunction.h" 2909467b48Spatrick #include "llvm/CodeGen/SlotIndexes.h" 3009467b48Spatrick #include "llvm/Support/Compiler.h" 3109467b48Spatrick #include <utility> 3209467b48Spatrick 3309467b48Spatrick namespace llvm { 3409467b48Spatrick 35*d415bd75Srobert class LiveInterval; 36*d415bd75Srobert class LiveRange; 3709467b48Spatrick class LiveIntervals; 3809467b48Spatrick class LiveRangeEdit; 3909467b48Spatrick class MachineBlockFrequencyInfo; 4009467b48Spatrick class MachineDominatorTree; 4109467b48Spatrick class MachineLoopInfo; 4209467b48Spatrick class MachineRegisterInfo; 4309467b48Spatrick class TargetInstrInfo; 4409467b48Spatrick class TargetRegisterInfo; 4509467b48Spatrick class VirtRegMap; 4673471bf0Spatrick class VirtRegAuxInfo; 4709467b48Spatrick 4809467b48Spatrick /// Determines the latest safe point in a block in which we can insert a split, 4909467b48Spatrick /// spill or other instruction related with CurLI. 5009467b48Spatrick class LLVM_LIBRARY_VISIBILITY InsertPointAnalysis { 5109467b48Spatrick private: 5209467b48Spatrick const LiveIntervals &LIS; 5309467b48Spatrick 5409467b48Spatrick /// Last legal insert point in each basic block in the current function. 5509467b48Spatrick /// The first entry is the first terminator, the second entry is the 5609467b48Spatrick /// last valid point to insert a split or spill for a variable that is 57097a140dSpatrick /// live into a landing pad or inlineasm_br successor. 5809467b48Spatrick SmallVector<std::pair<SlotIndex, SlotIndex>, 8> LastInsertPoint; 5909467b48Spatrick 6009467b48Spatrick SlotIndex computeLastInsertPoint(const LiveInterval &CurLI, 6109467b48Spatrick const MachineBasicBlock &MBB); 6209467b48Spatrick 6309467b48Spatrick public: 6409467b48Spatrick InsertPointAnalysis(const LiveIntervals &lis, unsigned BBNum); 6509467b48Spatrick 6609467b48Spatrick /// Return the base index of the last valid insert point for \pCurLI in \pMBB. getLastInsertPoint(const LiveInterval & CurLI,const MachineBasicBlock & MBB)6709467b48Spatrick SlotIndex getLastInsertPoint(const LiveInterval &CurLI, 6809467b48Spatrick const MachineBasicBlock &MBB) { 6909467b48Spatrick unsigned Num = MBB.getNumber(); 7009467b48Spatrick // Inline the common simple case. 7109467b48Spatrick if (LastInsertPoint[Num].first.isValid() && 7209467b48Spatrick !LastInsertPoint[Num].second.isValid()) 7309467b48Spatrick return LastInsertPoint[Num].first; 7409467b48Spatrick return computeLastInsertPoint(CurLI, MBB); 7509467b48Spatrick } 7609467b48Spatrick 7709467b48Spatrick /// Returns the last insert point as an iterator for \pCurLI in \pMBB. 7809467b48Spatrick MachineBasicBlock::iterator getLastInsertPointIter(const LiveInterval &CurLI, 7909467b48Spatrick MachineBasicBlock &MBB); 8009467b48Spatrick 8109467b48Spatrick /// Return the base index of the first insert point in \pMBB. getFirstInsertPoint(MachineBasicBlock & MBB)8209467b48Spatrick SlotIndex getFirstInsertPoint(MachineBasicBlock &MBB) { 8309467b48Spatrick SlotIndex Res = LIS.getMBBStartIdx(&MBB); 8409467b48Spatrick if (!MBB.empty()) { 8509467b48Spatrick MachineBasicBlock::iterator MII = MBB.SkipPHIsLabelsAndDebug(MBB.begin()); 8609467b48Spatrick if (MII != MBB.end()) 8709467b48Spatrick Res = LIS.getInstructionIndex(*MII); 8809467b48Spatrick } 8909467b48Spatrick return Res; 9009467b48Spatrick } 9109467b48Spatrick 9209467b48Spatrick }; 9309467b48Spatrick 9409467b48Spatrick /// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting 9509467b48Spatrick /// opportunities. 9609467b48Spatrick class LLVM_LIBRARY_VISIBILITY SplitAnalysis { 9709467b48Spatrick public: 9809467b48Spatrick const MachineFunction &MF; 9909467b48Spatrick const VirtRegMap &VRM; 10009467b48Spatrick const LiveIntervals &LIS; 10109467b48Spatrick const MachineLoopInfo &Loops; 10209467b48Spatrick const TargetInstrInfo &TII; 10309467b48Spatrick 10409467b48Spatrick /// Additional information about basic blocks where the current variable is 10509467b48Spatrick /// live. Such a block will look like one of these templates: 10609467b48Spatrick /// 10709467b48Spatrick /// 1. | o---x | Internal to block. Variable is only live in this block. 10809467b48Spatrick /// 2. |---x | Live-in, kill. 10909467b48Spatrick /// 3. | o---| Def, live-out. 11009467b48Spatrick /// 4. |---x o---| Live-in, kill, def, live-out. Counted by NumGapBlocks. 11109467b48Spatrick /// 5. |---o---o---| Live-through with uses or defs. 11209467b48Spatrick /// 6. |-----------| Live-through without uses. Counted by NumThroughBlocks. 11309467b48Spatrick /// 11409467b48Spatrick /// Two BlockInfo entries are created for template 4. One for the live-in 11509467b48Spatrick /// segment, and one for the live-out segment. These entries look as if the 11609467b48Spatrick /// block were split in the middle where the live range isn't live. 11709467b48Spatrick /// 11809467b48Spatrick /// Live-through blocks without any uses don't get BlockInfo entries. They 11909467b48Spatrick /// are simply listed in ThroughBlocks instead. 12009467b48Spatrick /// 12109467b48Spatrick struct BlockInfo { 12209467b48Spatrick MachineBasicBlock *MBB; 12309467b48Spatrick SlotIndex FirstInstr; ///< First instr accessing current reg. 12409467b48Spatrick SlotIndex LastInstr; ///< Last instr accessing current reg. 12509467b48Spatrick SlotIndex FirstDef; ///< First non-phi valno->def, or SlotIndex(). 12609467b48Spatrick bool LiveIn; ///< Current reg is live in. 12709467b48Spatrick bool LiveOut; ///< Current reg is live out. 12809467b48Spatrick 12909467b48Spatrick /// isOneInstr - Returns true when this BlockInfo describes a single 13009467b48Spatrick /// instruction. isOneInstrBlockInfo13109467b48Spatrick bool isOneInstr() const { 13209467b48Spatrick return SlotIndex::isSameInstr(FirstInstr, LastInstr); 13309467b48Spatrick } 13473471bf0Spatrick 13573471bf0Spatrick void print(raw_ostream &OS) const; 13673471bf0Spatrick void dump() const; 13709467b48Spatrick }; 13809467b48Spatrick 13909467b48Spatrick private: 14009467b48Spatrick // Current live interval. 14109467b48Spatrick const LiveInterval *CurLI = nullptr; 14209467b48Spatrick 14309467b48Spatrick /// Insert Point Analysis. 14409467b48Spatrick InsertPointAnalysis IPA; 14509467b48Spatrick 14609467b48Spatrick // Sorted slot indexes of using instructions. 14709467b48Spatrick SmallVector<SlotIndex, 8> UseSlots; 14809467b48Spatrick 14909467b48Spatrick /// UseBlocks - Blocks where CurLI has uses. 15009467b48Spatrick SmallVector<BlockInfo, 8> UseBlocks; 15109467b48Spatrick 15209467b48Spatrick /// NumGapBlocks - Number of duplicate entries in UseBlocks for blocks where 15309467b48Spatrick /// the live range has a gap. 15409467b48Spatrick unsigned NumGapBlocks; 15509467b48Spatrick 15609467b48Spatrick /// ThroughBlocks - Block numbers where CurLI is live through without uses. 15709467b48Spatrick BitVector ThroughBlocks; 15809467b48Spatrick 15909467b48Spatrick /// NumThroughBlocks - Number of live-through blocks. 16009467b48Spatrick unsigned NumThroughBlocks; 16109467b48Spatrick 16209467b48Spatrick // Sumarize statistics by counting instructions using CurLI. 16309467b48Spatrick void analyzeUses(); 16409467b48Spatrick 16509467b48Spatrick /// calcLiveBlockInfo - Compute per-block information about CurLI. 166*d415bd75Srobert void calcLiveBlockInfo(); 16709467b48Spatrick 16809467b48Spatrick public: 16909467b48Spatrick SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis, 17009467b48Spatrick const MachineLoopInfo &mli); 17109467b48Spatrick 17209467b48Spatrick /// analyze - set CurLI to the specified interval, and analyze how it may be 17309467b48Spatrick /// split. 17409467b48Spatrick void analyze(const LiveInterval *li); 17509467b48Spatrick 17609467b48Spatrick /// clear - clear all data structures so SplitAnalysis is ready to analyze a 17709467b48Spatrick /// new interval. 17809467b48Spatrick void clear(); 17909467b48Spatrick 18009467b48Spatrick /// getParent - Return the last analyzed interval. getParent()18109467b48Spatrick const LiveInterval &getParent() const { return *CurLI; } 18209467b48Spatrick 18309467b48Spatrick /// isOriginalEndpoint - Return true if the original live range was killed or 18409467b48Spatrick /// (re-)defined at Idx. Idx should be the 'def' slot for a normal kill/def, 18509467b48Spatrick /// and 'use' for an early-clobber def. 18609467b48Spatrick /// This can be used to recognize code inserted by earlier live range 18709467b48Spatrick /// splitting. 18809467b48Spatrick bool isOriginalEndpoint(SlotIndex Idx) const; 18909467b48Spatrick 19009467b48Spatrick /// getUseSlots - Return an array of SlotIndexes of instructions using CurLI. 19109467b48Spatrick /// This include both use and def operands, at most one entry per instruction. getUseSlots()19209467b48Spatrick ArrayRef<SlotIndex> getUseSlots() const { return UseSlots; } 19309467b48Spatrick 19409467b48Spatrick /// getUseBlocks - Return an array of BlockInfo objects for the basic blocks 19509467b48Spatrick /// where CurLI has uses. getUseBlocks()19609467b48Spatrick ArrayRef<BlockInfo> getUseBlocks() const { return UseBlocks; } 19709467b48Spatrick 19809467b48Spatrick /// getNumThroughBlocks - Return the number of through blocks. getNumThroughBlocks()19909467b48Spatrick unsigned getNumThroughBlocks() const { return NumThroughBlocks; } 20009467b48Spatrick 20109467b48Spatrick /// isThroughBlock - Return true if CurLI is live through MBB without uses. isThroughBlock(unsigned MBB)20209467b48Spatrick bool isThroughBlock(unsigned MBB) const { return ThroughBlocks.test(MBB); } 20309467b48Spatrick 20409467b48Spatrick /// getThroughBlocks - Return the set of through blocks. getThroughBlocks()20509467b48Spatrick const BitVector &getThroughBlocks() const { return ThroughBlocks; } 20609467b48Spatrick 20709467b48Spatrick /// getNumLiveBlocks - Return the number of blocks where CurLI is live. getNumLiveBlocks()20809467b48Spatrick unsigned getNumLiveBlocks() const { 20909467b48Spatrick return getUseBlocks().size() - NumGapBlocks + getNumThroughBlocks(); 21009467b48Spatrick } 21109467b48Spatrick 21209467b48Spatrick /// countLiveBlocks - Return the number of blocks where li is live. This is 21309467b48Spatrick /// guaranteed to return the same number as getNumLiveBlocks() after calling 21409467b48Spatrick /// analyze(li). 21509467b48Spatrick unsigned countLiveBlocks(const LiveInterval *li) const; 21609467b48Spatrick 21709467b48Spatrick using BlockPtrSet = SmallPtrSet<const MachineBasicBlock *, 16>; 21809467b48Spatrick 21909467b48Spatrick /// shouldSplitSingleBlock - Returns true if it would help to create a local 22009467b48Spatrick /// live range for the instructions in BI. There is normally no benefit to 22109467b48Spatrick /// creating a live range for a single instruction, but it does enable 22209467b48Spatrick /// register class inflation if the instruction has a restricted register 22309467b48Spatrick /// class. 22409467b48Spatrick /// 22509467b48Spatrick /// @param BI The block to be isolated. 22609467b48Spatrick /// @param SingleInstrs True when single instructions should be isolated. 22709467b48Spatrick bool shouldSplitSingleBlock(const BlockInfo &BI, bool SingleInstrs) const; 22809467b48Spatrick getLastSplitPoint(unsigned Num)22909467b48Spatrick SlotIndex getLastSplitPoint(unsigned Num) { 23009467b48Spatrick return IPA.getLastInsertPoint(*CurLI, *MF.getBlockNumbered(Num)); 23109467b48Spatrick } 23209467b48Spatrick getLastSplitPoint(MachineBasicBlock * BB)23373471bf0Spatrick SlotIndex getLastSplitPoint(MachineBasicBlock *BB) { 23473471bf0Spatrick return IPA.getLastInsertPoint(*CurLI, *BB); 23573471bf0Spatrick } 23673471bf0Spatrick getLastSplitPointIter(MachineBasicBlock * BB)23709467b48Spatrick MachineBasicBlock::iterator getLastSplitPointIter(MachineBasicBlock *BB) { 23809467b48Spatrick return IPA.getLastInsertPointIter(*CurLI, *BB); 23909467b48Spatrick } 24009467b48Spatrick getFirstSplitPoint(unsigned Num)24109467b48Spatrick SlotIndex getFirstSplitPoint(unsigned Num) { 24209467b48Spatrick return IPA.getFirstInsertPoint(*MF.getBlockNumbered(Num)); 24309467b48Spatrick } 24409467b48Spatrick }; 24509467b48Spatrick 24609467b48Spatrick /// SplitEditor - Edit machine code and LiveIntervals for live range 24709467b48Spatrick /// splitting. 24809467b48Spatrick /// 24909467b48Spatrick /// - Create a SplitEditor from a SplitAnalysis. 25009467b48Spatrick /// - Start a new live interval with openIntv. 25109467b48Spatrick /// - Mark the places where the new interval is entered using enterIntv* 25209467b48Spatrick /// - Mark the ranges where the new interval is used with useIntv* 25309467b48Spatrick /// - Mark the places where the interval is exited with exitIntv*. 25409467b48Spatrick /// - Finish the current interval with closeIntv and repeat from 2. 25509467b48Spatrick /// - Rewrite instructions with finish(). 25609467b48Spatrick /// 25709467b48Spatrick class LLVM_LIBRARY_VISIBILITY SplitEditor { 25809467b48Spatrick SplitAnalysis &SA; 25909467b48Spatrick LiveIntervals &LIS; 26009467b48Spatrick VirtRegMap &VRM; 26109467b48Spatrick MachineRegisterInfo &MRI; 26209467b48Spatrick MachineDominatorTree &MDT; 26309467b48Spatrick const TargetInstrInfo &TII; 26409467b48Spatrick const TargetRegisterInfo &TRI; 26509467b48Spatrick const MachineBlockFrequencyInfo &MBFI; 26673471bf0Spatrick VirtRegAuxInfo &VRAI; 26709467b48Spatrick 26809467b48Spatrick public: 26909467b48Spatrick /// ComplementSpillMode - Select how the complement live range should be 27009467b48Spatrick /// created. SplitEditor automatically creates interval 0 to contain 27109467b48Spatrick /// anything that isn't added to another interval. This complement interval 27209467b48Spatrick /// can get quite complicated, and it can sometimes be an advantage to allow 27309467b48Spatrick /// it to overlap the other intervals. If it is going to spill anyway, no 27409467b48Spatrick /// registers are wasted by keeping a value in two places at the same time. 27509467b48Spatrick enum ComplementSpillMode { 27609467b48Spatrick /// SM_Partition(Default) - Try to create the complement interval so it 27709467b48Spatrick /// doesn't overlap any other intervals, and the original interval is 27809467b48Spatrick /// partitioned. This may require a large number of back copies and extra 27909467b48Spatrick /// PHI-defs. Only segments marked with overlapIntv will be overlapping. 28009467b48Spatrick SM_Partition, 28109467b48Spatrick 28209467b48Spatrick /// SM_Size - Overlap intervals to minimize the number of inserted COPY 28309467b48Spatrick /// instructions. Copies to the complement interval are hoisted to their 28409467b48Spatrick /// common dominator, so only one COPY is required per value in the 28509467b48Spatrick /// complement interval. This also means that no extra PHI-defs need to be 28609467b48Spatrick /// inserted in the complement interval. 28709467b48Spatrick SM_Size, 28809467b48Spatrick 28909467b48Spatrick /// SM_Speed - Overlap intervals to minimize the expected execution 29009467b48Spatrick /// frequency of the inserted copies. This is very similar to SM_Size, but 29109467b48Spatrick /// the complement interval may get some extra PHI-defs. 29209467b48Spatrick SM_Speed 29309467b48Spatrick }; 29409467b48Spatrick 29509467b48Spatrick private: 29609467b48Spatrick /// Edit - The current parent register and new intervals created. 29709467b48Spatrick LiveRangeEdit *Edit = nullptr; 29809467b48Spatrick 29909467b48Spatrick /// Index into Edit of the currently open interval. 30009467b48Spatrick /// The index 0 is used for the complement, so the first interval started by 30109467b48Spatrick /// openIntv will be 1. 30209467b48Spatrick unsigned OpenIdx = 0; 30309467b48Spatrick 30409467b48Spatrick /// The current spill mode, selected by reset(). 30509467b48Spatrick ComplementSpillMode SpillMode = SM_Partition; 30609467b48Spatrick 30709467b48Spatrick using RegAssignMap = IntervalMap<SlotIndex, unsigned>; 30809467b48Spatrick 30909467b48Spatrick /// Allocator for the interval map. This will eventually be shared with 31009467b48Spatrick /// SlotIndexes and LiveIntervals. 31109467b48Spatrick RegAssignMap::Allocator Allocator; 31209467b48Spatrick 31309467b48Spatrick /// RegAssign - Map of the assigned register indexes. 31409467b48Spatrick /// Edit.get(RegAssign.lookup(Idx)) is the register that should be live at 31509467b48Spatrick /// Idx. 31609467b48Spatrick RegAssignMap RegAssign; 31709467b48Spatrick 31809467b48Spatrick using ValueForcePair = PointerIntPair<VNInfo *, 1>; 31909467b48Spatrick using ValueMap = DenseMap<std::pair<unsigned, unsigned>, ValueForcePair>; 32009467b48Spatrick 32109467b48Spatrick /// Values - keep track of the mapping from parent values to values in the new 32209467b48Spatrick /// intervals. Given a pair (RegIdx, ParentVNI->id), Values contains: 32309467b48Spatrick /// 32409467b48Spatrick /// 1. No entry - the value is not mapped to Edit.get(RegIdx). 32509467b48Spatrick /// 2. (Null, false) - the value is mapped to multiple values in 32609467b48Spatrick /// Edit.get(RegIdx). Each value is represented by a minimal live range at 32709467b48Spatrick /// its def. The full live range can be inferred exactly from the range 32809467b48Spatrick /// of RegIdx in RegAssign. 32909467b48Spatrick /// 3. (Null, true). As above, but the ranges in RegAssign are too large, and 330097a140dSpatrick /// the live range must be recomputed using ::extend(). 33109467b48Spatrick /// 4. (VNI, false) The value is mapped to a single new value. 33209467b48Spatrick /// The new value has no live ranges anywhere. 33309467b48Spatrick ValueMap Values; 33409467b48Spatrick 335097a140dSpatrick /// LICalc - Cache for computing live ranges and SSA update. Each instance 33609467b48Spatrick /// can only handle non-overlapping live ranges, so use a separate 337097a140dSpatrick /// LiveIntervalCalc instance for the complement interval when in spill mode. 338097a140dSpatrick LiveIntervalCalc LICalc[2]; 33909467b48Spatrick 340097a140dSpatrick /// getLICalc - Return the LICalc to use for RegIdx. In spill mode, the 34109467b48Spatrick /// complement interval can overlap the other intervals, so it gets its own 342097a140dSpatrick /// LICalc instance. When not in spill mode, all intervals can share one. getLICalc(unsigned RegIdx)343097a140dSpatrick LiveIntervalCalc &getLICalc(unsigned RegIdx) { 344097a140dSpatrick return LICalc[SpillMode != SM_Partition && RegIdx != 0]; 34509467b48Spatrick } 34609467b48Spatrick 34709467b48Spatrick /// Add a segment to the interval LI for the value number VNI. If LI has 34809467b48Spatrick /// subranges, corresponding segments will be added to them as well, but 34909467b48Spatrick /// with newly created value numbers. If Original is true, dead def will 35009467b48Spatrick /// only be added a subrange of LI if the corresponding subrange of the 35109467b48Spatrick /// original interval has a def at this index. Otherwise, all subranges 35209467b48Spatrick /// of LI will be updated. 35309467b48Spatrick void addDeadDef(LiveInterval &LI, VNInfo *VNI, bool Original); 35409467b48Spatrick 35509467b48Spatrick /// defValue - define a value in RegIdx from ParentVNI at Idx. 35609467b48Spatrick /// Idx does not have to be ParentVNI->def, but it must be contained within 35709467b48Spatrick /// ParentVNI's live range in ParentLI. The new value is added to the value 35809467b48Spatrick /// map. The value being defined may either come from rematerialization 35909467b48Spatrick /// (or an inserted copy), or it may be coming from the original interval. 36009467b48Spatrick /// The parameter Original should be true in the latter case, otherwise 36109467b48Spatrick /// it should be false. 36209467b48Spatrick /// Return the new LI value. 36309467b48Spatrick VNInfo *defValue(unsigned RegIdx, const VNInfo *ParentVNI, SlotIndex Idx, 36409467b48Spatrick bool Original); 36509467b48Spatrick 36609467b48Spatrick /// forceRecompute - Force the live range of ParentVNI in RegIdx to be 36709467b48Spatrick /// recomputed by LiveRangeCalc::extend regardless of the number of defs. 36809467b48Spatrick /// This is used for values whose live range doesn't match RegAssign exactly. 36909467b48Spatrick /// They could have rematerialized, or back-copies may have been moved. 37009467b48Spatrick void forceRecompute(unsigned RegIdx, const VNInfo &ParentVNI); 37109467b48Spatrick 37209467b48Spatrick /// Calls forceRecompute() on any affected regidx and on ParentVNI 37309467b48Spatrick /// predecessors in case of a phi definition. 37409467b48Spatrick void forceRecomputeVNI(const VNInfo &ParentVNI); 37509467b48Spatrick 37609467b48Spatrick /// defFromParent - Define Reg from ParentVNI at UseIdx using either 37709467b48Spatrick /// rematerialization or a COPY from parent. Return the new value. 378*d415bd75Srobert VNInfo *defFromParent(unsigned RegIdx, const VNInfo *ParentVNI, 379*d415bd75Srobert SlotIndex UseIdx, MachineBasicBlock &MBB, 38009467b48Spatrick MachineBasicBlock::iterator I); 38109467b48Spatrick 38209467b48Spatrick /// removeBackCopies - Remove the copy instructions that defines the values 38309467b48Spatrick /// in the vector in the complement interval. 38409467b48Spatrick void removeBackCopies(SmallVectorImpl<VNInfo*> &Copies); 38509467b48Spatrick 38609467b48Spatrick /// getShallowDominator - Returns the least busy dominator of MBB that is 38709467b48Spatrick /// also dominated by DefMBB. Busy is measured by loop depth. 38809467b48Spatrick MachineBasicBlock *findShallowDominator(MachineBasicBlock *MBB, 38909467b48Spatrick MachineBasicBlock *DefMBB); 39009467b48Spatrick 39109467b48Spatrick /// Find out all the backCopies dominated by others. 39209467b48Spatrick void computeRedundantBackCopies(DenseSet<unsigned> &NotToHoistSet, 39309467b48Spatrick SmallVectorImpl<VNInfo *> &BackCopies); 39409467b48Spatrick 39509467b48Spatrick /// Hoist back-copies to the complement interval. It tries to hoist all 39609467b48Spatrick /// the back-copies to one BB if it is beneficial, or else simply remove 39709467b48Spatrick /// redundant backcopies dominated by others. 39809467b48Spatrick void hoistCopies(); 39909467b48Spatrick 40009467b48Spatrick /// transferValues - Transfer values to the new ranges. 40109467b48Spatrick /// Return true if any ranges were skipped. 40209467b48Spatrick bool transferValues(); 40309467b48Spatrick 40409467b48Spatrick /// Live range @p LR corresponding to the lane Mask @p LM has a live 40509467b48Spatrick /// PHI def at the beginning of block @p B. Extend the range @p LR of 40609467b48Spatrick /// all predecessor values that reach this def. If @p LR is a subrange, 40709467b48Spatrick /// the array @p Undefs is the set of all locations where it is undefined 40809467b48Spatrick /// via <def,read-undef> in other subranges for the same register. 409097a140dSpatrick void extendPHIRange(MachineBasicBlock &B, LiveIntervalCalc &LIC, 41009467b48Spatrick LiveRange &LR, LaneBitmask LM, 41109467b48Spatrick ArrayRef<SlotIndex> Undefs); 41209467b48Spatrick 41309467b48Spatrick /// extendPHIKillRanges - Extend the ranges of all values killed by original 41409467b48Spatrick /// parent PHIDefs. 41509467b48Spatrick void extendPHIKillRanges(); 41609467b48Spatrick 41709467b48Spatrick /// rewriteAssigned - Rewrite all uses of Edit.getReg() to assigned registers. 41809467b48Spatrick void rewriteAssigned(bool ExtendRanges); 41909467b48Spatrick 42009467b48Spatrick /// deleteRematVictims - Delete defs that are dead after rematerializing. 42109467b48Spatrick void deleteRematVictims(); 42209467b48Spatrick 42309467b48Spatrick /// Add a copy instruction copying \p FromReg to \p ToReg before 42409467b48Spatrick /// \p InsertBefore. This can be invoked with a \p LaneMask which may make it 42509467b48Spatrick /// necessary to construct a sequence of copies to cover it exactly. 42673471bf0Spatrick SlotIndex buildCopy(Register FromReg, Register ToReg, LaneBitmask LaneMask, 42709467b48Spatrick MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore, 42809467b48Spatrick bool Late, unsigned RegIdx); 42909467b48Spatrick 43073471bf0Spatrick SlotIndex buildSingleSubRegCopy(Register FromReg, Register ToReg, 43109467b48Spatrick MachineBasicBlock &MB, MachineBasicBlock::iterator InsertBefore, 43209467b48Spatrick unsigned SubIdx, LiveInterval &DestLI, bool Late, SlotIndex Def); 43309467b48Spatrick 43409467b48Spatrick public: 43509467b48Spatrick /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. 43609467b48Spatrick /// Newly created intervals will be appended to newIntervals. 437*d415bd75Srobert SplitEditor(SplitAnalysis &SA, LiveIntervals &LIS, VirtRegMap &VRM, 438*d415bd75Srobert MachineDominatorTree &MDT, MachineBlockFrequencyInfo &MBFI, 439*d415bd75Srobert VirtRegAuxInfo &VRAI); 44009467b48Spatrick 44109467b48Spatrick /// reset - Prepare for a new split. 44209467b48Spatrick void reset(LiveRangeEdit&, ComplementSpillMode = SM_Partition); 44309467b48Spatrick 44409467b48Spatrick /// Create a new virtual register and live interval. 44509467b48Spatrick /// Return the interval index, starting from 1. Interval index 0 is the 44609467b48Spatrick /// implicit complement interval. 44709467b48Spatrick unsigned openIntv(); 44809467b48Spatrick 44909467b48Spatrick /// currentIntv - Return the current interval index. currentIntv()45009467b48Spatrick unsigned currentIntv() const { return OpenIdx; } 45109467b48Spatrick 45209467b48Spatrick /// selectIntv - Select a previously opened interval index. 45309467b48Spatrick void selectIntv(unsigned Idx); 45409467b48Spatrick 45509467b48Spatrick /// enterIntvBefore - Enter the open interval before the instruction at Idx. 45609467b48Spatrick /// If the parent interval is not live before Idx, a COPY is not inserted. 45709467b48Spatrick /// Return the beginning of the new live range. 45809467b48Spatrick SlotIndex enterIntvBefore(SlotIndex Idx); 45909467b48Spatrick 46009467b48Spatrick /// enterIntvAfter - Enter the open interval after the instruction at Idx. 46109467b48Spatrick /// Return the beginning of the new live range. 46209467b48Spatrick SlotIndex enterIntvAfter(SlotIndex Idx); 46309467b48Spatrick 46409467b48Spatrick /// enterIntvAtEnd - Enter the open interval at the end of MBB. 46509467b48Spatrick /// Use the open interval from the inserted copy to the MBB end. 46609467b48Spatrick /// Return the beginning of the new live range. 46709467b48Spatrick SlotIndex enterIntvAtEnd(MachineBasicBlock &MBB); 46809467b48Spatrick 46909467b48Spatrick /// useIntv - indicate that all instructions in MBB should use OpenLI. 47009467b48Spatrick void useIntv(const MachineBasicBlock &MBB); 47109467b48Spatrick 47209467b48Spatrick /// useIntv - indicate that all instructions in range should use OpenLI. 47309467b48Spatrick void useIntv(SlotIndex Start, SlotIndex End); 47409467b48Spatrick 47509467b48Spatrick /// leaveIntvAfter - Leave the open interval after the instruction at Idx. 47609467b48Spatrick /// Return the end of the live range. 47709467b48Spatrick SlotIndex leaveIntvAfter(SlotIndex Idx); 47809467b48Spatrick 47909467b48Spatrick /// leaveIntvBefore - Leave the open interval before the instruction at Idx. 48009467b48Spatrick /// Return the end of the live range. 48109467b48Spatrick SlotIndex leaveIntvBefore(SlotIndex Idx); 48209467b48Spatrick 48309467b48Spatrick /// leaveIntvAtTop - Leave the interval at the top of MBB. 48409467b48Spatrick /// Add liveness from the MBB top to the copy. 48509467b48Spatrick /// Return the end of the live range. 48609467b48Spatrick SlotIndex leaveIntvAtTop(MachineBasicBlock &MBB); 48709467b48Spatrick 48809467b48Spatrick /// overlapIntv - Indicate that all instructions in range should use the open 48973471bf0Spatrick /// interval if End does not have tied-def usage of the register and in this 490*d415bd75Srobert /// case complement interval is used. Let the complement interval be live. 49109467b48Spatrick /// 49209467b48Spatrick /// This doubles the register pressure, but is sometimes required to deal with 49309467b48Spatrick /// register uses after the last valid split point. 49409467b48Spatrick /// 49509467b48Spatrick /// The Start index should be a return value from a leaveIntv* call, and End 49609467b48Spatrick /// should be in the same basic block. The parent interval must have the same 49709467b48Spatrick /// value across the range. 49809467b48Spatrick /// 49909467b48Spatrick void overlapIntv(SlotIndex Start, SlotIndex End); 50009467b48Spatrick 50109467b48Spatrick /// finish - after all the new live ranges have been created, compute the 50209467b48Spatrick /// remaining live range, and rewrite instructions to use the new registers. 50309467b48Spatrick /// @param LRMap When not null, this vector will map each live range in Edit 50409467b48Spatrick /// back to the indices returned by openIntv. 50509467b48Spatrick /// There may be extra indices created by dead code elimination. 50609467b48Spatrick void finish(SmallVectorImpl<unsigned> *LRMap = nullptr); 50709467b48Spatrick 50809467b48Spatrick /// dump - print the current interval mapping to dbgs(). 50909467b48Spatrick void dump() const; 51009467b48Spatrick 51109467b48Spatrick // ===--- High level methods ---=== 51209467b48Spatrick 51309467b48Spatrick /// splitSingleBlock - Split CurLI into a separate live interval around the 51409467b48Spatrick /// uses in a single block. This is intended to be used as part of a larger 51509467b48Spatrick /// split, and doesn't call finish(). 51609467b48Spatrick void splitSingleBlock(const SplitAnalysis::BlockInfo &BI); 51709467b48Spatrick 51809467b48Spatrick /// splitLiveThroughBlock - Split CurLI in the given block such that it 51909467b48Spatrick /// enters the block in IntvIn and leaves it in IntvOut. There may be uses in 52009467b48Spatrick /// the block, but they will be ignored when placing split points. 52109467b48Spatrick /// 52209467b48Spatrick /// @param MBBNum Block number. 52309467b48Spatrick /// @param IntvIn Interval index entering the block. 52409467b48Spatrick /// @param LeaveBefore When set, leave IntvIn before this point. 52509467b48Spatrick /// @param IntvOut Interval index leaving the block. 52609467b48Spatrick /// @param EnterAfter When set, enter IntvOut after this point. 52709467b48Spatrick void splitLiveThroughBlock(unsigned MBBNum, 52809467b48Spatrick unsigned IntvIn, SlotIndex LeaveBefore, 52909467b48Spatrick unsigned IntvOut, SlotIndex EnterAfter); 53009467b48Spatrick 53109467b48Spatrick /// splitRegInBlock - Split CurLI in the given block such that it enters the 53209467b48Spatrick /// block in IntvIn and leaves it on the stack (or not at all). Split points 53309467b48Spatrick /// are placed in a way that avoids putting uses in the stack interval. This 53409467b48Spatrick /// may require creating a local interval when there is interference. 53509467b48Spatrick /// 53609467b48Spatrick /// @param BI Block descriptor. 53709467b48Spatrick /// @param IntvIn Interval index entering the block. Not 0. 53809467b48Spatrick /// @param LeaveBefore When set, leave IntvIn before this point. 53909467b48Spatrick void splitRegInBlock(const SplitAnalysis::BlockInfo &BI, 54009467b48Spatrick unsigned IntvIn, SlotIndex LeaveBefore); 54109467b48Spatrick 54209467b48Spatrick /// splitRegOutBlock - Split CurLI in the given block such that it enters the 54309467b48Spatrick /// block on the stack (or isn't live-in at all) and leaves it in IntvOut. 54409467b48Spatrick /// Split points are placed to avoid interference and such that the uses are 54509467b48Spatrick /// not in the stack interval. This may require creating a local interval 54609467b48Spatrick /// when there is interference. 54709467b48Spatrick /// 54809467b48Spatrick /// @param BI Block descriptor. 54909467b48Spatrick /// @param IntvOut Interval index leaving the block. 55009467b48Spatrick /// @param EnterAfter When set, enter IntvOut after this point. 55109467b48Spatrick void splitRegOutBlock(const SplitAnalysis::BlockInfo &BI, 55209467b48Spatrick unsigned IntvOut, SlotIndex EnterAfter); 55309467b48Spatrick }; 55409467b48Spatrick 55509467b48Spatrick } // end namespace llvm 55609467b48Spatrick 55709467b48Spatrick #endif // LLVM_LIB_CODEGEN_SPLITKIT_H 558