1 //==--- llvm/CodeGen/ReachingDefAnalysis.h - Reaching Def Analysis -*- 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 /// \file Reaching Defs Analysis pass. 10 /// 11 /// This pass tracks for each instruction what is the "closest" reaching def of 12 /// a given register. It is used by BreakFalseDeps (for clearance calculation) 13 /// and ExecutionDomainFix (for arbitrating conflicting domains). 14 /// 15 /// Note that this is different from the usual definition notion of liveness. 16 /// The CPU doesn't care whether or not we consider a register killed. 17 /// 18 // 19 //===----------------------------------------------------------------------===// 20 21 #ifndef LLVM_CODEGEN_REACHINGDEFANALYSIS_H 22 #define LLVM_CODEGEN_REACHINGDEFANALYSIS_H 23 24 #include "llvm/ADT/DenseMap.h" 25 #include "llvm/ADT/SmallVector.h" 26 #include "llvm/ADT/TinyPtrVector.h" 27 #include "llvm/CodeGen/LoopTraversal.h" 28 #include "llvm/CodeGen/MachineFunctionPass.h" 29 #include "llvm/InitializePasses.h" 30 31 namespace llvm { 32 33 class MachineBasicBlock; 34 class MachineInstr; 35 36 /// Thin wrapper around "int" used to store reaching definitions, 37 /// using an encoding that makes it compatible with TinyPtrVector. 38 /// The 0th LSB is forced zero (and will be used for pointer union tagging), 39 /// The 1st LSB is forced one (to make sure the value is non-zero). 40 class ReachingDef { 41 uintptr_t Encoded; 42 friend struct PointerLikeTypeTraits<ReachingDef>; 43 explicit ReachingDef(uintptr_t Encoded) : Encoded(Encoded) {} 44 45 public: 46 ReachingDef(std::nullptr_t) : Encoded(0) {} 47 ReachingDef(int Instr) : Encoded(((uintptr_t) Instr << 2) | 2) {} 48 operator int() const { return ((int) Encoded) >> 2; } 49 }; 50 51 template<> 52 struct PointerLikeTypeTraits<ReachingDef> { 53 static constexpr int NumLowBitsAvailable = 1; 54 55 static inline void *getAsVoidPointer(const ReachingDef &RD) { 56 return reinterpret_cast<void *>(RD.Encoded); 57 } 58 59 static inline ReachingDef getFromVoidPointer(void *P) { 60 return ReachingDef(reinterpret_cast<uintptr_t>(P)); 61 } 62 63 static inline ReachingDef getFromVoidPointer(const void *P) { 64 return ReachingDef(reinterpret_cast<uintptr_t>(P)); 65 } 66 }; 67 68 // The storage for all reaching definitions. 69 class MBBReachingDefsInfo { 70 public: 71 void init(unsigned NumBlockIDs) { AllReachingDefs.resize(NumBlockIDs); } 72 73 unsigned numBlockIDs() const { return AllReachingDefs.size(); } 74 75 void startBasicBlock(unsigned MBBNumber, unsigned NumRegUnits) { 76 AllReachingDefs[MBBNumber].resize(NumRegUnits); 77 } 78 79 void append(unsigned MBBNumber, unsigned Unit, int Def) { 80 AllReachingDefs[MBBNumber][Unit].push_back(Def); 81 } 82 83 void prepend(unsigned MBBNumber, unsigned Unit, int Def) { 84 auto &Defs = AllReachingDefs[MBBNumber][Unit]; 85 Defs.insert(Defs.begin(), Def); 86 } 87 88 void replaceFront(unsigned MBBNumber, unsigned Unit, int Def) { 89 assert(!AllReachingDefs[MBBNumber][Unit].empty()); 90 *AllReachingDefs[MBBNumber][Unit].begin() = Def; 91 } 92 93 void clear() { AllReachingDefs.clear(); } 94 95 ArrayRef<ReachingDef> defs(unsigned MBBNumber, unsigned Unit) const { 96 if (AllReachingDefs[MBBNumber].empty()) 97 // Block IDs are not necessarily dense. 98 return ArrayRef<ReachingDef>(); 99 return AllReachingDefs[MBBNumber][Unit]; 100 } 101 102 private: 103 /// All reaching defs of a given RegUnit for a given MBB. 104 using MBBRegUnitDefs = TinyPtrVector<ReachingDef>; 105 /// All reaching defs of all reg units for a given MBB 106 using MBBDefsInfo = std::vector<MBBRegUnitDefs>; 107 108 /// All reaching defs of all reg units for all MBBs 109 SmallVector<MBBDefsInfo, 4> AllReachingDefs; 110 }; 111 112 /// This class provides the reaching def analysis. 113 class ReachingDefAnalysis : public MachineFunctionPass { 114 private: 115 MachineFunction *MF = nullptr; 116 const TargetRegisterInfo *TRI = nullptr; 117 const TargetInstrInfo *TII = nullptr; 118 LoopTraversal::TraversalOrder TraversedMBBOrder; 119 unsigned NumRegUnits = 0; 120 unsigned NumStackObjects = 0; 121 int ObjectIndexBegin = 0; 122 /// Instruction that defined each register, relative to the beginning of the 123 /// current basic block. When a LiveRegsDefInfo is used to represent a 124 /// live-out register, this value is relative to the end of the basic block, 125 /// so it will be a negative number. 126 using LiveRegsDefInfo = std::vector<int>; 127 LiveRegsDefInfo LiveRegs; 128 129 /// Keeps clearance information for all registers. Note that this 130 /// is different from the usual definition notion of liveness. The CPU 131 /// doesn't care whether or not we consider a register killed. 132 using OutRegsInfoMap = SmallVector<LiveRegsDefInfo, 4>; 133 OutRegsInfoMap MBBOutRegsInfos; 134 135 /// Current instruction number. 136 /// The first instruction in each basic block is 0. 137 int CurInstr = -1; 138 139 /// Maps instructions to their instruction Ids, relative to the beginning of 140 /// their basic blocks. 141 DenseMap<MachineInstr *, int> InstIds; 142 143 MBBReachingDefsInfo MBBReachingDefs; 144 using MBBFrameObjsReachingDefsInfo = 145 DenseMap<unsigned, DenseMap<int, SmallVector<int>>>; 146 // MBBFrameObjsReachingDefs[i][j] is a list of instruction indices (relative 147 // to begining of MBB) that define frame index (j + 148 // MF->getFrameInfo().getObjectIndexBegin()) in MBB i. This is used in 149 // answering reaching definition queries. 150 MBBFrameObjsReachingDefsInfo MBBFrameObjsReachingDefs; 151 152 /// Default values are 'nothing happened a long time ago'. 153 const int ReachingDefDefaultVal = -(1 << 21); 154 155 using InstSet = SmallPtrSetImpl<MachineInstr*>; 156 using BlockSet = SmallPtrSetImpl<MachineBasicBlock*>; 157 158 public: 159 static char ID; // Pass identification, replacement for typeid 160 161 ReachingDefAnalysis() : MachineFunctionPass(ID) { 162 initializeReachingDefAnalysisPass(*PassRegistry::getPassRegistry()); 163 } 164 void releaseMemory() override; 165 166 void getAnalysisUsage(AnalysisUsage &AU) const override { 167 AU.setPreservesAll(); 168 MachineFunctionPass::getAnalysisUsage(AU); 169 } 170 171 void printAllReachingDefs(MachineFunction &MF); 172 bool runOnMachineFunction(MachineFunction &MF) override; 173 174 MachineFunctionProperties getRequiredProperties() const override { 175 return MachineFunctionProperties().set( 176 MachineFunctionProperties::Property::NoVRegs).set( 177 MachineFunctionProperties::Property::TracksLiveness); 178 } 179 180 /// Re-run the analysis. 181 void reset(); 182 183 /// Initialize data structures. 184 void init(); 185 186 /// Traverse the machine function, mapping definitions. 187 void traverse(); 188 189 /// Provides the instruction id of the closest reaching def instruction of 190 /// Reg that reaches MI, relative to the begining of MI's basic block. 191 /// Note that Reg may represent a stack slot. 192 int getReachingDef(MachineInstr *MI, Register Reg) const; 193 194 /// Return whether A and B use the same def of Reg. 195 bool hasSameReachingDef(MachineInstr *A, MachineInstr *B, Register Reg) const; 196 197 /// Return whether the reaching def for MI also is live out of its parent 198 /// block. 199 bool isReachingDefLiveOut(MachineInstr *MI, Register Reg) const; 200 201 /// Return the local MI that produces the live out value for Reg, or 202 /// nullptr for a non-live out or non-local def. 203 MachineInstr *getLocalLiveOutMIDef(MachineBasicBlock *MBB, 204 Register Reg) const; 205 206 /// If a single MachineInstr creates the reaching definition, then return it. 207 /// Otherwise return null. 208 MachineInstr *getUniqueReachingMIDef(MachineInstr *MI, Register Reg) const; 209 210 /// If a single MachineInstr creates the reaching definition, for MIs operand 211 /// at Idx, then return it. Otherwise return null. 212 MachineInstr *getMIOperand(MachineInstr *MI, unsigned Idx) const; 213 214 /// If a single MachineInstr creates the reaching definition, for MIs MO, 215 /// then return it. Otherwise return null. 216 MachineInstr *getMIOperand(MachineInstr *MI, MachineOperand &MO) const; 217 218 /// Provide whether the register has been defined in the same basic block as, 219 /// and before, MI. 220 bool hasLocalDefBefore(MachineInstr *MI, Register Reg) const; 221 222 /// Return whether the given register is used after MI, whether it's a local 223 /// use or a live out. 224 bool isRegUsedAfter(MachineInstr *MI, Register Reg) const; 225 226 /// Return whether the given register is defined after MI. 227 bool isRegDefinedAfter(MachineInstr *MI, Register Reg) const; 228 229 /// Provides the clearance - the number of instructions since the closest 230 /// reaching def instuction of Reg that reaches MI. 231 int getClearance(MachineInstr *MI, Register Reg) const; 232 233 /// Provides the uses, in the same block as MI, of register that MI defines. 234 /// This does not consider live-outs. 235 void getReachingLocalUses(MachineInstr *MI, Register Reg, 236 InstSet &Uses) const; 237 238 /// Search MBB for a definition of Reg and insert it into Defs. If no 239 /// definition is found, recursively search the predecessor blocks for them. 240 void getLiveOuts(MachineBasicBlock *MBB, Register Reg, InstSet &Defs, 241 BlockSet &VisitedBBs) const; 242 void getLiveOuts(MachineBasicBlock *MBB, Register Reg, InstSet &Defs) const; 243 244 /// For the given block, collect the instructions that use the live-in 245 /// value of the provided register. Return whether the value is still 246 /// live on exit. 247 bool getLiveInUses(MachineBasicBlock *MBB, Register Reg, InstSet &Uses) const; 248 249 /// Collect the users of the value stored in Reg, which is defined 250 /// by MI. 251 void getGlobalUses(MachineInstr *MI, Register Reg, InstSet &Uses) const; 252 253 /// Collect all possible definitions of the value stored in Reg, which is 254 /// used by MI. 255 void getGlobalReachingDefs(MachineInstr *MI, Register Reg, 256 InstSet &Defs) const; 257 258 /// Return whether From can be moved forwards to just before To. 259 bool isSafeToMoveForwards(MachineInstr *From, MachineInstr *To) const; 260 261 /// Return whether From can be moved backwards to just after To. 262 bool isSafeToMoveBackwards(MachineInstr *From, MachineInstr *To) const; 263 264 /// Assuming MI is dead, recursively search the incoming operands which are 265 /// killed by MI and collect those that would become dead. 266 void collectKilledOperands(MachineInstr *MI, InstSet &Dead) const; 267 268 /// Return whether removing this instruction will have no effect on the 269 /// program, returning the redundant use-def chain. 270 bool isSafeToRemove(MachineInstr *MI, InstSet &ToRemove) const; 271 272 /// Return whether removing this instruction will have no effect on the 273 /// program, ignoring the possible effects on some instructions, returning 274 /// the redundant use-def chain. 275 bool isSafeToRemove(MachineInstr *MI, InstSet &ToRemove, 276 InstSet &Ignore) const; 277 278 /// Return whether a MachineInstr could be inserted at MI and safely define 279 /// the given register without affecting the program. 280 bool isSafeToDefRegAt(MachineInstr *MI, Register Reg) const; 281 282 /// Return whether a MachineInstr could be inserted at MI and safely define 283 /// the given register without affecting the program, ignoring any effects 284 /// on the provided instructions. 285 bool isSafeToDefRegAt(MachineInstr *MI, Register Reg, InstSet &Ignore) const; 286 287 private: 288 /// Set up LiveRegs by merging predecessor live-out values. 289 void enterBasicBlock(MachineBasicBlock *MBB); 290 291 /// Update live-out values. 292 void leaveBasicBlock(MachineBasicBlock *MBB); 293 294 /// Process he given basic block. 295 void processBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB); 296 297 /// Process block that is part of a loop again. 298 void reprocessBasicBlock(MachineBasicBlock *MBB); 299 300 /// Update def-ages for registers defined by MI. 301 /// Also break dependencies on partial defs and undef uses. 302 void processDefs(MachineInstr *); 303 304 /// Utility function for isSafeToMoveForwards/Backwards. 305 template<typename Iterator> 306 bool isSafeToMove(MachineInstr *From, MachineInstr *To) const; 307 308 /// Return whether removing this instruction will have no effect on the 309 /// program, ignoring the possible effects on some instructions, returning 310 /// the redundant use-def chain. 311 bool isSafeToRemove(MachineInstr *MI, InstSet &Visited, 312 InstSet &ToRemove, InstSet &Ignore) const; 313 314 /// Provides the MI, from the given block, corresponding to the Id or a 315 /// nullptr if the id does not refer to the block. 316 MachineInstr *getInstFromId(MachineBasicBlock *MBB, int InstId) const; 317 318 /// Provides the instruction of the closest reaching def instruction of 319 /// Reg that reaches MI, relative to the begining of MI's basic block. 320 /// Note that Reg may represent a stack slot. 321 MachineInstr *getReachingLocalMIDef(MachineInstr *MI, Register Reg) const; 322 }; 323 324 } // namespace llvm 325 326 #endif // LLVM_CODEGEN_REACHINGDEFANALYSIS_H 327