1 //===---- ReachingDefAnalysis.cpp - 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 #include "llvm/CodeGen/LivePhysRegs.h" 10 #include "llvm/CodeGen/ReachingDefAnalysis.h" 11 #include "llvm/CodeGen/TargetRegisterInfo.h" 12 #include "llvm/CodeGen/TargetSubtargetInfo.h" 13 #include "llvm/Support/Debug.h" 14 15 using namespace llvm; 16 17 #define DEBUG_TYPE "reaching-deps-analysis" 18 19 char ReachingDefAnalysis::ID = 0; 20 INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false, 21 true) 22 23 void ReachingDefAnalysis::enterBasicBlock( 24 const LoopTraversal::TraversedMBBInfo &TraversedMBB) { 25 26 MachineBasicBlock *MBB = TraversedMBB.MBB; 27 unsigned MBBNumber = MBB->getNumber(); 28 assert(MBBNumber < MBBReachingDefs.size() && 29 "Unexpected basic block number."); 30 MBBReachingDefs[MBBNumber].resize(NumRegUnits); 31 32 // Reset instruction counter in each basic block. 33 CurInstr = 0; 34 35 // Set up LiveRegs to represent registers entering MBB. 36 // Default values are 'nothing happened a long time ago'. 37 if (LiveRegs.empty()) 38 LiveRegs.assign(NumRegUnits, ReachingDefDefaultVal); 39 40 // This is the entry block. 41 if (MBB->pred_empty()) { 42 for (const auto &LI : MBB->liveins()) { 43 for (MCRegUnitIterator Unit(LI.PhysReg, TRI); Unit.isValid(); ++Unit) { 44 // Treat function live-ins as if they were defined just before the first 45 // instruction. Usually, function arguments are set up immediately 46 // before the call. 47 LiveRegs[*Unit] = -1; 48 MBBReachingDefs[MBBNumber][*Unit].push_back(LiveRegs[*Unit]); 49 } 50 } 51 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n"); 52 return; 53 } 54 55 // Try to coalesce live-out registers from predecessors. 56 for (MachineBasicBlock *pred : MBB->predecessors()) { 57 assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() && 58 "Should have pre-allocated MBBInfos for all MBBs"); 59 const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()]; 60 // Incoming is null if this is a backedge from a BB 61 // we haven't processed yet 62 if (Incoming.empty()) 63 continue; 64 65 for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) { 66 // Use the most recent predecessor def for each register. 67 LiveRegs[Unit] = std::max(LiveRegs[Unit], Incoming[Unit]); 68 if ((LiveRegs[Unit] != ReachingDefDefaultVal)) 69 MBBReachingDefs[MBBNumber][Unit].push_back(LiveRegs[Unit]); 70 } 71 } 72 73 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) 74 << (!TraversedMBB.IsDone ? ": incomplete\n" 75 : ": all preds known\n")); 76 } 77 78 void ReachingDefAnalysis::leaveBasicBlock( 79 const LoopTraversal::TraversedMBBInfo &TraversedMBB) { 80 assert(!LiveRegs.empty() && "Must enter basic block first."); 81 unsigned MBBNumber = TraversedMBB.MBB->getNumber(); 82 assert(MBBNumber < MBBOutRegsInfos.size() && 83 "Unexpected basic block number."); 84 // Save register clearances at end of MBB - used by enterBasicBlock(). 85 MBBOutRegsInfos[MBBNumber] = LiveRegs; 86 87 // While processing the basic block, we kept `Def` relative to the start 88 // of the basic block for convenience. However, future use of this information 89 // only cares about the clearance from the end of the block, so adjust 90 // everything to be relative to the end of the basic block. 91 for (int &OutLiveReg : MBBOutRegsInfos[MBBNumber]) 92 OutLiveReg -= CurInstr; 93 LiveRegs.clear(); 94 } 95 96 void ReachingDefAnalysis::processDefs(MachineInstr *MI) { 97 assert(!MI->isDebugInstr() && "Won't process debug instructions"); 98 99 unsigned MBBNumber = MI->getParent()->getNumber(); 100 assert(MBBNumber < MBBReachingDefs.size() && 101 "Unexpected basic block number."); 102 const MCInstrDesc &MCID = MI->getDesc(); 103 for (unsigned i = 0, 104 e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs(); 105 i != e; ++i) { 106 MachineOperand &MO = MI->getOperand(i); 107 if (!MO.isReg() || !MO.getReg()) 108 continue; 109 if (MO.isUse()) 110 continue; 111 for (MCRegUnitIterator Unit(MO.getReg(), TRI); Unit.isValid(); ++Unit) { 112 // This instruction explicitly defines the current reg unit. 113 LLVM_DEBUG(dbgs() << printReg(MO.getReg(), TRI) << ":\t" << CurInstr 114 << '\t' << *MI); 115 116 // How many instructions since this reg unit was last written? 117 LiveRegs[*Unit] = CurInstr; 118 MBBReachingDefs[MBBNumber][*Unit].push_back(CurInstr); 119 } 120 } 121 InstIds[MI] = CurInstr; 122 ++CurInstr; 123 } 124 125 void ReachingDefAnalysis::processBasicBlock( 126 const LoopTraversal::TraversedMBBInfo &TraversedMBB) { 127 enterBasicBlock(TraversedMBB); 128 for (MachineInstr &MI : *TraversedMBB.MBB) { 129 if (!MI.isDebugInstr()) 130 processDefs(&MI); 131 } 132 leaveBasicBlock(TraversedMBB); 133 } 134 135 bool ReachingDefAnalysis::runOnMachineFunction(MachineFunction &mf) { 136 MF = &mf; 137 TRI = MF->getSubtarget().getRegisterInfo(); 138 139 LiveRegs.clear(); 140 NumRegUnits = TRI->getNumRegUnits(); 141 142 MBBReachingDefs.resize(mf.getNumBlockIDs()); 143 144 LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n"); 145 146 // Initialize the MBBOutRegsInfos 147 MBBOutRegsInfos.resize(mf.getNumBlockIDs()); 148 149 // Traverse the basic blocks. 150 LoopTraversal Traversal; 151 LoopTraversal::TraversalOrder TraversedMBBOrder = Traversal.traverse(mf); 152 for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) { 153 processBasicBlock(TraversedMBB); 154 } 155 156 // Sorting all reaching defs found for a ceartin reg unit in a given BB. 157 for (MBBDefsInfo &MBBDefs : MBBReachingDefs) { 158 for (MBBRegUnitDefs &RegUnitDefs : MBBDefs) 159 llvm::sort(RegUnitDefs); 160 } 161 162 return false; 163 } 164 165 void ReachingDefAnalysis::releaseMemory() { 166 // Clear the internal vectors. 167 MBBOutRegsInfos.clear(); 168 MBBReachingDefs.clear(); 169 InstIds.clear(); 170 } 171 172 int ReachingDefAnalysis::getReachingDef(MachineInstr *MI, int PhysReg) { 173 assert(InstIds.count(MI) && "Unexpected machine instuction."); 174 int InstId = InstIds[MI]; 175 int DefRes = ReachingDefDefaultVal; 176 unsigned MBBNumber = MI->getParent()->getNumber(); 177 assert(MBBNumber < MBBReachingDefs.size() && 178 "Unexpected basic block number."); 179 int LatestDef = ReachingDefDefaultVal; 180 for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) { 181 for (int Def : MBBReachingDefs[MBBNumber][*Unit]) { 182 if (Def >= InstId) 183 break; 184 DefRes = Def; 185 } 186 LatestDef = std::max(LatestDef, DefRes); 187 } 188 return LatestDef; 189 } 190 191 MachineInstr* ReachingDefAnalysis::getReachingMIDef(MachineInstr *MI, int PhysReg) { 192 return getInstFromId(MI->getParent(), getReachingDef(MI, PhysReg)); 193 } 194 195 bool ReachingDefAnalysis::hasSameReachingDef(MachineInstr *A, MachineInstr *B, 196 int PhysReg) { 197 MachineBasicBlock *ParentA = A->getParent(); 198 MachineBasicBlock *ParentB = B->getParent(); 199 if (ParentA != ParentB) 200 return false; 201 202 return getReachingDef(A, PhysReg) == getReachingDef(B, PhysReg); 203 } 204 205 MachineInstr *ReachingDefAnalysis::getInstFromId(MachineBasicBlock *MBB, 206 int InstId) { 207 assert(static_cast<size_t>(MBB->getNumber()) < MBBReachingDefs.size() && 208 "Unexpected basic block number."); 209 assert(InstId < static_cast<int>(MBB->size()) && 210 "Unexpected instruction id."); 211 212 if (InstId < 0) 213 return nullptr; 214 215 for (auto &MI : *MBB) { 216 if (InstIds.count(&MI) && InstIds[&MI] == InstId) 217 return &MI; 218 } 219 return nullptr; 220 } 221 222 int ReachingDefAnalysis::getClearance(MachineInstr *MI, MCPhysReg PhysReg) { 223 assert(InstIds.count(MI) && "Unexpected machine instuction."); 224 return InstIds[MI] - getReachingDef(MI, PhysReg); 225 } 226 227 void ReachingDefAnalysis::getReachingLocalUses(MachineInstr *Def, int PhysReg, 228 SmallVectorImpl<MachineInstr*> &Uses) { 229 MachineBasicBlock *MBB = Def->getParent(); 230 MachineBasicBlock::iterator MI = MachineBasicBlock::iterator(Def); 231 while (++MI != MBB->end()) { 232 // If/when we find a new reaching def, we know that there's no more uses 233 // of 'Def'. 234 if (getReachingMIDef(&*MI, PhysReg) != Def) 235 return; 236 237 for (auto &MO : MI->operands()) { 238 if (!MO.isReg() || !MO.isUse() || MO.getReg() != PhysReg) 239 continue; 240 241 Uses.push_back(&*MI); 242 if (MO.isKill()) 243 return; 244 } 245 } 246 } 247 248 unsigned ReachingDefAnalysis::getNumUses(MachineInstr *Def, int PhysReg) { 249 SmallVector<MachineInstr*, 4> Uses; 250 getReachingLocalUses(Def, PhysReg, Uses); 251 return Uses.size(); 252 } 253 254 bool ReachingDefAnalysis::isRegUsedAfter(MachineInstr *MI, int PhysReg) { 255 MachineBasicBlock *MBB = MI->getParent(); 256 LivePhysRegs LiveRegs(*TRI); 257 LiveRegs.addLiveOuts(*MBB); 258 259 // Yes if the register is live out of the basic block. 260 if (LiveRegs.contains(PhysReg)) 261 return true; 262 263 // Walk backwards through the block to see if the register is live at some 264 // point. 265 for (auto Last = MBB->rbegin(), End = MBB->rend(); Last != End; ++Last) { 266 LiveRegs.stepBackward(*Last); 267 if (LiveRegs.contains(PhysReg)) 268 return InstIds[&*Last] > InstIds[MI]; 269 } 270 return false; 271 } 272 273 bool ReachingDefAnalysis::isReachingDefLiveOut(MachineInstr *MI, int PhysReg) { 274 MachineBasicBlock *MBB = MI->getParent(); 275 LivePhysRegs LiveRegs(*TRI); 276 LiveRegs.addLiveOuts(*MBB); 277 if (!LiveRegs.contains(PhysReg)) 278 return false; 279 280 MachineInstr *Last = &MBB->back(); 281 int Def = getReachingDef(MI, PhysReg); 282 if (getReachingDef(Last, PhysReg) != Def) 283 return false; 284 285 // Finally check that the last instruction doesn't redefine the register. 286 for (auto &MO : Last->operands()) 287 if (MO.isReg() && MO.isDef() && MO.getReg() == PhysReg) 288 return false; 289 290 return true; 291 } 292 293 MachineInstr* ReachingDefAnalysis::getLocalLiveOutMIDef(MachineBasicBlock *MBB, 294 int PhysReg) { 295 LivePhysRegs LiveRegs(*TRI); 296 LiveRegs.addLiveOuts(*MBB); 297 if (!LiveRegs.contains(PhysReg)) 298 return nullptr; 299 300 MachineInstr *Last = &MBB->back(); 301 int Def = getReachingDef(Last, PhysReg); 302 for (auto &MO : Last->operands()) 303 if (MO.isReg() && MO.isDef() && MO.getReg() == PhysReg) 304 return Last; 305 306 return Def < 0 ? nullptr : getInstFromId(MBB, Def); 307 } 308 309 MachineInstr *ReachingDefAnalysis::getInstWithUseBefore(MachineInstr *MI, 310 int PhysReg) { 311 auto I = MachineBasicBlock::reverse_iterator(MI); 312 auto E = MI->getParent()->rend(); 313 I++; 314 315 for ( ; I != E; I++) 316 for (auto &MO : I->operands()) 317 if (MO.isReg() && MO.isUse() && MO.getReg() == PhysReg) 318 return &*I; 319 320 return nullptr; 321 } 322 323 void ReachingDefAnalysis::getAllInstWithUseBefore(MachineInstr *MI, 324 int PhysReg, SmallVectorImpl<MachineInstr*> &Uses) { 325 MachineInstr *Use = nullptr; 326 MachineInstr *Pos = MI; 327 328 while ((Use = getInstWithUseBefore(Pos, PhysReg))) { 329 Uses.push_back(Use); 330 Pos = Use; 331 } 332 } 333