1 //===- LiveRangeCalc.h - Calculate 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 // The LiveRangeCalc class can be used to implement the computation of 10 // live ranges from scratch. 11 // It caches information about values in the CFG to speed up repeated 12 // operations on the same live range. The cache can be shared by 13 // non-overlapping live ranges. SplitKit uses that when computing the live 14 // range of split products. 15 // 16 // A low-level interface is available to clients that know where a variable is 17 // live, but don't know which value it has as every point. LiveRangeCalc will 18 // propagate values down the dominator tree, and even insert PHI-defs where 19 // needed. SplitKit uses this faster interface when possible. 20 // 21 //===----------------------------------------------------------------------===// 22 23 #ifndef LLVM_LIB_CODEGEN_LIVERANGECALC_H 24 #define LLVM_LIB_CODEGEN_LIVERANGECALC_H 25 26 #include "llvm/ADT/ArrayRef.h" 27 #include "llvm/ADT/BitVector.h" 28 #include "llvm/ADT/DenseMap.h" 29 #include "llvm/ADT/IndexedMap.h" 30 #include "llvm/ADT/SmallVector.h" 31 #include "llvm/CodeGen/LiveInterval.h" 32 #include "llvm/CodeGen/MachineBasicBlock.h" 33 #include "llvm/CodeGen/SlotIndexes.h" 34 #include "llvm/MC/LaneBitmask.h" 35 #include <utility> 36 37 namespace llvm { 38 39 template <class NodeT> class DomTreeNodeBase; 40 class MachineDominatorTree; 41 class MachineFunction; 42 class MachineRegisterInfo; 43 44 using MachineDomTreeNode = DomTreeNodeBase<MachineBasicBlock>; 45 46 class LiveRangeCalc { 47 const MachineFunction *MF = nullptr; 48 const MachineRegisterInfo *MRI = nullptr; 49 SlotIndexes *Indexes = nullptr; 50 MachineDominatorTree *DomTree = nullptr; 51 VNInfo::Allocator *Alloc = nullptr; 52 53 /// LiveOutPair - A value and the block that defined it. The domtree node is 54 /// redundant, it can be computed as: MDT[Indexes.getMBBFromIndex(VNI->def)]. 55 using LiveOutPair = std::pair<VNInfo *, MachineDomTreeNode *>; 56 57 /// LiveOutMap - Map basic blocks to the value leaving the block. 58 using LiveOutMap = IndexedMap<LiveOutPair, MBB2NumberFunctor>; 59 60 /// Bit vector of active entries in LiveOut, also used as a visited set by 61 /// findReachingDefs. One entry per basic block, indexed by block number. 62 /// This is kept as a separate bit vector because it can be cleared quickly 63 /// when switching live ranges. 64 BitVector Seen; 65 66 /// Map LiveRange to sets of blocks (represented by bit vectors) that 67 /// in the live range are defined on entry and undefined on entry. 68 /// A block is defined on entry if there is a path from at least one of 69 /// the defs in the live range to the entry of the block, and conversely, 70 /// a block is undefined on entry, if there is no such path (i.e. no 71 /// definition reaches the entry of the block). A single LiveRangeCalc 72 /// object is used to track live-out information for multiple registers 73 /// in live range splitting (which is ok, since the live ranges of these 74 /// registers do not overlap), but the defined/undefined information must 75 /// be kept separate for each individual range. 76 /// By convention, EntryInfoMap[&LR] = { Defined, Undefined }. 77 using EntryInfoMap = DenseMap<LiveRange *, std::pair<BitVector, BitVector>>; 78 EntryInfoMap EntryInfos; 79 80 /// Map each basic block where a live range is live out to the live-out value 81 /// and its defining block. 82 /// 83 /// For every basic block, MBB, one of these conditions shall be true: 84 /// 85 /// 1. !Seen.count(MBB->getNumber()) 86 /// Blocks without a Seen bit are ignored. 87 /// 2. LiveOut[MBB].second.getNode() == MBB 88 /// The live-out value is defined in MBB. 89 /// 3. forall P in preds(MBB): LiveOut[P] == LiveOut[MBB] 90 /// The live-out value passses through MBB. All predecessors must carry 91 /// the same value. 92 /// 93 /// The domtree node may be null, it can be computed. 94 /// 95 /// The map can be shared by multiple live ranges as long as no two are 96 /// live-out of the same block. 97 LiveOutMap Map; 98 99 /// LiveInBlock - Information about a basic block where a live range is known 100 /// to be live-in, but the value has not yet been determined. 101 struct LiveInBlock { 102 // The live range set that is live-in to this block. The algorithms can 103 // handle multiple non-overlapping live ranges simultaneously. 104 LiveRange &LR; 105 106 // DomNode - Dominator tree node for the block. 107 // Cleared when the final value has been determined and LI has been updated. 108 MachineDomTreeNode *DomNode; 109 110 // Position in block where the live-in range ends, or SlotIndex() if the 111 // range passes through the block. When the final value has been 112 // determined, the range from the block start to Kill will be added to LI. 113 SlotIndex Kill; 114 115 // Live-in value filled in by updateSSA once it is known. 116 VNInfo *Value = nullptr; 117 118 LiveInBlock(LiveRange &LR, MachineDomTreeNode *node, SlotIndex kill) 119 : LR(LR), DomNode(node), Kill(kill) {} 120 }; 121 122 /// LiveIn - Work list of blocks where the live-in value has yet to be 123 /// determined. This list is typically computed by findReachingDefs() and 124 /// used as a work list by updateSSA(). The low-level interface may also be 125 /// used to add entries directly. 126 SmallVector<LiveInBlock, 16> LiveIn; 127 128 /// Check if the entry to block @p MBB can be reached by any of the defs 129 /// in @p LR. Return true if none of the defs reach the entry to @p MBB. 130 bool isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs, 131 MachineBasicBlock &MBB, BitVector &DefOnEntry, 132 BitVector &UndefOnEntry); 133 134 /// Find the set of defs that can reach @p Kill. @p Kill must belong to 135 /// @p UseMBB. 136 /// 137 /// If exactly one def can reach @p UseMBB, and the def dominates @p Kill, 138 /// all paths from the def to @p UseMBB are added to @p LR, and the function 139 /// returns true. 140 /// 141 /// If multiple values can reach @p UseMBB, the blocks that need @p LR to be 142 /// live in are added to the LiveIn array, and the function returns false. 143 /// 144 /// The array @p Undef provides the locations where the range @p LR becomes 145 /// undefined by <def,read-undef> operands on other subranges. If @p Undef 146 /// is non-empty and @p Kill is jointly dominated only by the entries of 147 /// @p Undef, the function returns false. 148 /// 149 /// PhysReg, when set, is used to verify live-in lists on basic blocks. 150 bool findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB, SlotIndex Use, 151 unsigned PhysReg, ArrayRef<SlotIndex> Undefs); 152 153 /// updateSSA - Compute the values that will be live in to all requested 154 /// blocks in LiveIn. Create PHI-def values as required to preserve SSA form. 155 /// 156 /// Every live-in block must be jointly dominated by the added live-out 157 /// blocks. No values are read from the live ranges. 158 void updateSSA(); 159 160 /// Transfer information from the LiveIn vector to the live ranges and update 161 /// the given @p LiveOuts. 162 void updateFromLiveIns(); 163 164 protected: 165 /// Some getters to expose in a read-only way some private fields to 166 /// subclasses. 167 const MachineFunction *getMachineFunction() { return MF; } 168 const MachineRegisterInfo *getRegInfo() const { return MRI; } 169 SlotIndexes *getIndexes() { return Indexes; } 170 MachineDominatorTree *getDomTree() { return DomTree; } 171 VNInfo::Allocator *getVNAlloc() { return Alloc; } 172 173 /// Reset Map and Seen fields. 174 void resetLiveOutMap(); 175 176 public: 177 LiveRangeCalc() = default; 178 179 //===--------------------------------------------------------------------===// 180 // High-level interface. 181 //===--------------------------------------------------------------------===// 182 // 183 // Calculate live ranges from scratch. 184 // 185 186 /// reset - Prepare caches for a new set of non-overlapping live ranges. The 187 /// caches must be reset before attempting calculations with a live range 188 /// that may overlap a previously computed live range, and before the first 189 /// live range in a function. If live ranges are not known to be 190 /// non-overlapping, call reset before each. 191 void reset(const MachineFunction *mf, SlotIndexes *SI, 192 MachineDominatorTree *MDT, VNInfo::Allocator *VNIA); 193 194 //===--------------------------------------------------------------------===// 195 // Mid-level interface. 196 //===--------------------------------------------------------------------===// 197 // 198 // Modify existing live ranges. 199 // 200 201 /// Extend the live range of @p LR to reach @p Use. 202 /// 203 /// The existing values in @p LR must be live so they jointly dominate @p Use. 204 /// If @p Use is not dominated by a single existing value, PHI-defs are 205 /// inserted as required to preserve SSA form. 206 /// 207 /// PhysReg, when set, is used to verify live-in lists on basic blocks. 208 void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg, 209 ArrayRef<SlotIndex> Undefs); 210 211 //===--------------------------------------------------------------------===// 212 // Low-level interface. 213 //===--------------------------------------------------------------------===// 214 // 215 // These functions can be used to compute live ranges where the live-in and 216 // live-out blocks are already known, but the SSA value in each block is 217 // unknown. 218 // 219 // After calling reset(), add known live-out values and known live-in blocks. 220 // Then call calculateValues() to compute the actual value that is 221 // live-in to each block, and add liveness to the live ranges. 222 // 223 224 /// setLiveOutValue - Indicate that VNI is live out from MBB. The 225 /// calculateValues() function will not add liveness for MBB, the caller 226 /// should take care of that. 227 /// 228 /// VNI may be null only if MBB is a live-through block also passed to 229 /// addLiveInBlock(). 230 void setLiveOutValue(MachineBasicBlock *MBB, VNInfo *VNI) { 231 Seen.set(MBB->getNumber()); 232 Map[MBB] = LiveOutPair(VNI, nullptr); 233 } 234 235 /// addLiveInBlock - Add a block with an unknown live-in value. This 236 /// function can only be called once per basic block. Once the live-in value 237 /// has been determined, calculateValues() will add liveness to LI. 238 /// 239 /// @param LR The live range that is live-in to the block. 240 /// @param DomNode The domtree node for the block. 241 /// @param Kill Index in block where LI is killed. If the value is 242 /// live-through, set Kill = SLotIndex() and also call 243 /// setLiveOutValue(MBB, 0). 244 void addLiveInBlock(LiveRange &LR, MachineDomTreeNode *DomNode, 245 SlotIndex Kill = SlotIndex()) { 246 LiveIn.push_back(LiveInBlock(LR, DomNode, Kill)); 247 } 248 249 /// calculateValues - Calculate the value that will be live-in to each block 250 /// added with addLiveInBlock. Add PHI-def values as needed to preserve SSA 251 /// form. Add liveness to all live-in blocks up to the Kill point, or the 252 /// whole block for live-through blocks. 253 /// 254 /// Every predecessor of a live-in block must have been given a value with 255 /// setLiveOutValue, the value may be null for live-trough blocks. 256 void calculateValues(); 257 258 /// A diagnostic function to check if the end of the block @p MBB is 259 /// jointly dominated by the blocks corresponding to the slot indices 260 /// in @p Defs. This function is mainly for use in self-verification 261 /// checks. 262 LLVM_ATTRIBUTE_UNUSED 263 static bool isJointlyDominated(const MachineBasicBlock *MBB, 264 ArrayRef<SlotIndex> Defs, 265 const SlotIndexes &Indexes); 266 }; 267 268 } // end namespace llvm 269 270 #endif // LLVM_LIB_CODEGEN_LIVERANGECALC_H 271