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 /// This class provides the reaching def analysis. 69 class ReachingDefAnalysis : public MachineFunctionPass { 70 private: 71 MachineFunction *MF; 72 const TargetRegisterInfo *TRI; 73 LoopTraversal::TraversalOrder TraversedMBBOrder; 74 unsigned NumRegUnits; 75 /// Instruction that defined each register, relative to the beginning of the 76 /// current basic block. When a LiveRegsDefInfo is used to represent a 77 /// live-out register, this value is relative to the end of the basic block, 78 /// so it will be a negative number. 79 using LiveRegsDefInfo = std::vector<int>; 80 LiveRegsDefInfo LiveRegs; 81 82 /// Keeps clearance information for all registers. Note that this 83 /// is different from the usual definition notion of liveness. The CPU 84 /// doesn't care whether or not we consider a register killed. 85 using OutRegsInfoMap = SmallVector<LiveRegsDefInfo, 4>; 86 OutRegsInfoMap MBBOutRegsInfos; 87 88 /// Current instruction number. 89 /// The first instruction in each basic block is 0. 90 int CurInstr; 91 92 /// Maps instructions to their instruction Ids, relative to the beginning of 93 /// their basic blocks. 94 DenseMap<MachineInstr *, int> InstIds; 95 96 /// All reaching defs of a given RegUnit for a given MBB. 97 using MBBRegUnitDefs = TinyPtrVector<ReachingDef>; 98 /// All reaching defs of all reg units for a given MBB 99 using MBBDefsInfo = std::vector<MBBRegUnitDefs>; 100 /// All reaching defs of all reg units for a all MBBs 101 using MBBReachingDefsInfo = SmallVector<MBBDefsInfo, 4>; 102 MBBReachingDefsInfo MBBReachingDefs; 103 104 /// Default values are 'nothing happened a long time ago'. 105 const int ReachingDefDefaultVal = -(1 << 20); 106 107 using InstSet = SmallPtrSetImpl<MachineInstr*>; 108 using BlockSet = SmallPtrSetImpl<MachineBasicBlock*>; 109 110 public: 111 static char ID; // Pass identification, replacement for typeid 112 113 ReachingDefAnalysis() : MachineFunctionPass(ID) { 114 initializeReachingDefAnalysisPass(*PassRegistry::getPassRegistry()); 115 } 116 void releaseMemory() override; 117 118 void getAnalysisUsage(AnalysisUsage &AU) const override { 119 AU.setPreservesAll(); 120 MachineFunctionPass::getAnalysisUsage(AU); 121 } 122 123 bool runOnMachineFunction(MachineFunction &MF) override; 124 125 MachineFunctionProperties getRequiredProperties() const override { 126 return MachineFunctionProperties().set( 127 MachineFunctionProperties::Property::NoVRegs).set( 128 MachineFunctionProperties::Property::TracksLiveness); 129 } 130 131 /// Re-run the analysis. 132 void reset(); 133 134 /// Initialize data structures. 135 void init(); 136 137 /// Traverse the machine function, mapping definitions. 138 void traverse(); 139 140 /// Provides the instruction id of the closest reaching def instruction of 141 /// PhysReg that reaches MI, relative to the begining of MI's basic block. 142 int getReachingDef(MachineInstr *MI, MCRegister PhysReg) const; 143 144 /// Return whether A and B use the same def of PhysReg. 145 bool hasSameReachingDef(MachineInstr *A, MachineInstr *B, 146 MCRegister PhysReg) const; 147 148 /// Return whether the reaching def for MI also is live out of its parent 149 /// block. 150 bool isReachingDefLiveOut(MachineInstr *MI, MCRegister PhysReg) const; 151 152 /// Return the local MI that produces the live out value for PhysReg, or 153 /// nullptr for a non-live out or non-local def. 154 MachineInstr *getLocalLiveOutMIDef(MachineBasicBlock *MBB, 155 MCRegister PhysReg) const; 156 157 /// If a single MachineInstr creates the reaching definition, then return it. 158 /// Otherwise return null. 159 MachineInstr *getUniqueReachingMIDef(MachineInstr *MI, 160 MCRegister PhysReg) const; 161 162 /// If a single MachineInstr creates the reaching definition, for MIs operand 163 /// at Idx, then return it. Otherwise return null. 164 MachineInstr *getMIOperand(MachineInstr *MI, unsigned Idx) const; 165 166 /// If a single MachineInstr creates the reaching definition, for MIs MO, 167 /// then return it. Otherwise return null. 168 MachineInstr *getMIOperand(MachineInstr *MI, MachineOperand &MO) const; 169 170 /// Provide whether the register has been defined in the same basic block as, 171 /// and before, MI. 172 bool hasLocalDefBefore(MachineInstr *MI, MCRegister PhysReg) const; 173 174 /// Return whether the given register is used after MI, whether it's a local 175 /// use or a live out. 176 bool isRegUsedAfter(MachineInstr *MI, MCRegister PhysReg) const; 177 178 /// Return whether the given register is defined after MI. 179 bool isRegDefinedAfter(MachineInstr *MI, MCRegister PhysReg) const; 180 181 /// Provides the clearance - the number of instructions since the closest 182 /// reaching def instuction of PhysReg that reaches MI. 183 int getClearance(MachineInstr *MI, MCRegister PhysReg) const; 184 185 /// Provides the uses, in the same block as MI, of register that MI defines. 186 /// This does not consider live-outs. 187 void getReachingLocalUses(MachineInstr *MI, MCRegister PhysReg, 188 InstSet &Uses) const; 189 190 /// Search MBB for a definition of PhysReg and insert it into Defs. If no 191 /// definition is found, recursively search the predecessor blocks for them. 192 void getLiveOuts(MachineBasicBlock *MBB, MCRegister PhysReg, InstSet &Defs, 193 BlockSet &VisitedBBs) const; 194 void getLiveOuts(MachineBasicBlock *MBB, MCRegister PhysReg, 195 InstSet &Defs) const; 196 197 /// For the given block, collect the instructions that use the live-in 198 /// value of the provided register. Return whether the value is still 199 /// live on exit. 200 bool getLiveInUses(MachineBasicBlock *MBB, MCRegister PhysReg, 201 InstSet &Uses) const; 202 203 /// Collect the users of the value stored in PhysReg, which is defined 204 /// by MI. 205 void getGlobalUses(MachineInstr *MI, MCRegister PhysReg, InstSet &Uses) const; 206 207 /// Collect all possible definitions of the value stored in PhysReg, which is 208 /// used by MI. 209 void getGlobalReachingDefs(MachineInstr *MI, MCRegister PhysReg, 210 InstSet &Defs) const; 211 212 /// Return whether From can be moved forwards to just before To. 213 bool isSafeToMoveForwards(MachineInstr *From, MachineInstr *To) const; 214 215 /// Return whether From can be moved backwards to just after To. 216 bool isSafeToMoveBackwards(MachineInstr *From, MachineInstr *To) const; 217 218 /// Assuming MI is dead, recursively search the incoming operands which are 219 /// killed by MI and collect those that would become dead. 220 void collectKilledOperands(MachineInstr *MI, InstSet &Dead) const; 221 222 /// Return whether removing this instruction will have no effect on the 223 /// program, returning the redundant use-def chain. 224 bool isSafeToRemove(MachineInstr *MI, InstSet &ToRemove) const; 225 226 /// Return whether removing this instruction will have no effect on the 227 /// program, ignoring the possible effects on some instructions, returning 228 /// the redundant use-def chain. 229 bool isSafeToRemove(MachineInstr *MI, InstSet &ToRemove, 230 InstSet &Ignore) const; 231 232 /// Return whether a MachineInstr could be inserted at MI and safely define 233 /// the given register without affecting the program. 234 bool isSafeToDefRegAt(MachineInstr *MI, MCRegister PhysReg) const; 235 236 /// Return whether a MachineInstr could be inserted at MI and safely define 237 /// the given register without affecting the program, ignoring any effects 238 /// on the provided instructions. 239 bool isSafeToDefRegAt(MachineInstr *MI, MCRegister PhysReg, 240 InstSet &Ignore) const; 241 242 private: 243 /// Set up LiveRegs by merging predecessor live-out values. 244 void enterBasicBlock(MachineBasicBlock *MBB); 245 246 /// Update live-out values. 247 void leaveBasicBlock(MachineBasicBlock *MBB); 248 249 /// Process he given basic block. 250 void processBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB); 251 252 /// Process block that is part of a loop again. 253 void reprocessBasicBlock(MachineBasicBlock *MBB); 254 255 /// Update def-ages for registers defined by MI. 256 /// Also break dependencies on partial defs and undef uses. 257 void processDefs(MachineInstr *); 258 259 /// Utility function for isSafeToMoveForwards/Backwards. 260 template<typename Iterator> 261 bool isSafeToMove(MachineInstr *From, MachineInstr *To) const; 262 263 /// Return whether removing this instruction will have no effect on the 264 /// program, ignoring the possible effects on some instructions, returning 265 /// the redundant use-def chain. 266 bool isSafeToRemove(MachineInstr *MI, InstSet &Visited, 267 InstSet &ToRemove, InstSet &Ignore) const; 268 269 /// Provides the MI, from the given block, corresponding to the Id or a 270 /// nullptr if the id does not refer to the block. 271 MachineInstr *getInstFromId(MachineBasicBlock *MBB, int InstId) const; 272 273 /// Provides the instruction of the closest reaching def instruction of 274 /// PhysReg that reaches MI, relative to the begining of MI's basic block. 275 MachineInstr *getReachingLocalMIDef(MachineInstr *MI, 276 MCRegister PhysReg) const; 277 }; 278 279 } // namespace llvm 280 281 #endif // LLVM_CODEGEN_REACHINGDEFANALYSIS_H 282