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/ADT/SmallSet.h" 10 #include "llvm/ADT/SetOperations.h" 11 #include "llvm/CodeGen/LivePhysRegs.h" 12 #include "llvm/CodeGen/ReachingDefAnalysis.h" 13 #include "llvm/CodeGen/TargetRegisterInfo.h" 14 #include "llvm/CodeGen/TargetSubtargetInfo.h" 15 #include "llvm/Support/Debug.h" 16 17 using namespace llvm; 18 19 #define DEBUG_TYPE "reaching-deps-analysis" 20 21 char ReachingDefAnalysis::ID = 0; 22 INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false, 23 true) 24 25 static bool isValidReg(const MachineOperand &MO) { 26 return MO.isReg() && MO.getReg(); 27 } 28 29 static bool isValidRegUse(const MachineOperand &MO) { 30 return isValidReg(MO) && MO.isUse(); 31 } 32 33 static bool isValidRegUseOf(const MachineOperand &MO, MCRegister PhysReg, 34 const TargetRegisterInfo *TRI) { 35 if (!isValidRegUse(MO)) 36 return false; 37 if (MO.getReg() == PhysReg) 38 return true; 39 for (MCRegAliasIterator R(PhysReg, TRI, false); R.isValid(); ++R) 40 if (MO.getReg() == *R) 41 return true; 42 return false; 43 } 44 45 static bool isValidRegDef(const MachineOperand &MO) { 46 return isValidReg(MO) && MO.isDef(); 47 } 48 49 static bool isValidRegDefOf(const MachineOperand &MO, MCRegister PhysReg, 50 const TargetRegisterInfo *TRI) { 51 if (!isValidRegDef(MO)) 52 return false; 53 if (MO.getReg() == PhysReg) 54 return true; 55 for (MCRegAliasIterator R(PhysReg, TRI, false); R.isValid(); ++R) 56 if (MO.getReg() == *R) 57 return true; 58 return false; 59 } 60 61 void ReachingDefAnalysis::enterBasicBlock(MachineBasicBlock *MBB) { 62 unsigned MBBNumber = MBB->getNumber(); 63 assert(MBBNumber < MBBReachingDefs.size() && 64 "Unexpected basic block number."); 65 MBBReachingDefs[MBBNumber].resize(NumRegUnits); 66 67 // Reset instruction counter in each basic block. 68 CurInstr = 0; 69 70 // Set up LiveRegs to represent registers entering MBB. 71 // Default values are 'nothing happened a long time ago'. 72 if (LiveRegs.empty()) 73 LiveRegs.assign(NumRegUnits, ReachingDefDefaultVal); 74 75 // This is the entry block. 76 if (MBB->pred_empty()) { 77 for (const auto &LI : MBB->liveins()) { 78 for (MCRegUnitIterator Unit(LI.PhysReg, TRI); Unit.isValid(); ++Unit) { 79 // Treat function live-ins as if they were defined just before the first 80 // instruction. Usually, function arguments are set up immediately 81 // before the call. 82 if (LiveRegs[*Unit] != -1) { 83 LiveRegs[*Unit] = -1; 84 MBBReachingDefs[MBBNumber][*Unit].push_back(-1); 85 } 86 } 87 } 88 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n"); 89 return; 90 } 91 92 // Try to coalesce live-out registers from predecessors. 93 for (MachineBasicBlock *pred : MBB->predecessors()) { 94 assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() && 95 "Should have pre-allocated MBBInfos for all MBBs"); 96 const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()]; 97 // Incoming is null if this is a backedge from a BB 98 // we haven't processed yet 99 if (Incoming.empty()) 100 continue; 101 102 // Find the most recent reaching definition from a predecessor. 103 for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) 104 LiveRegs[Unit] = std::max(LiveRegs[Unit], Incoming[Unit]); 105 } 106 107 // Insert the most recent reaching definition we found. 108 for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) 109 if (LiveRegs[Unit] != ReachingDefDefaultVal) 110 MBBReachingDefs[MBBNumber][Unit].push_back(LiveRegs[Unit]); 111 } 112 113 void ReachingDefAnalysis::leaveBasicBlock(MachineBasicBlock *MBB) { 114 assert(!LiveRegs.empty() && "Must enter basic block first."); 115 unsigned MBBNumber = MBB->getNumber(); 116 assert(MBBNumber < MBBOutRegsInfos.size() && 117 "Unexpected basic block number."); 118 // Save register clearances at end of MBB - used by enterBasicBlock(). 119 MBBOutRegsInfos[MBBNumber] = LiveRegs; 120 121 // While processing the basic block, we kept `Def` relative to the start 122 // of the basic block for convenience. However, future use of this information 123 // only cares about the clearance from the end of the block, so adjust 124 // everything to be relative to the end of the basic block. 125 for (int &OutLiveReg : MBBOutRegsInfos[MBBNumber]) 126 if (OutLiveReg != ReachingDefDefaultVal) 127 OutLiveReg -= CurInstr; 128 LiveRegs.clear(); 129 } 130 131 void ReachingDefAnalysis::processDefs(MachineInstr *MI) { 132 assert(!MI->isDebugInstr() && "Won't process debug instructions"); 133 134 unsigned MBBNumber = MI->getParent()->getNumber(); 135 assert(MBBNumber < MBBReachingDefs.size() && 136 "Unexpected basic block number."); 137 138 for (auto &MO : MI->operands()) { 139 if (!isValidRegDef(MO)) 140 continue; 141 for (MCRegUnitIterator Unit(MO.getReg().asMCReg(), TRI); Unit.isValid(); 142 ++Unit) { 143 // This instruction explicitly defines the current reg unit. 144 LLVM_DEBUG(dbgs() << printRegUnit(*Unit, TRI) << ":\t" << CurInstr 145 << '\t' << *MI); 146 147 // How many instructions since this reg unit was last written? 148 if (LiveRegs[*Unit] != CurInstr) { 149 LiveRegs[*Unit] = CurInstr; 150 MBBReachingDefs[MBBNumber][*Unit].push_back(CurInstr); 151 } 152 } 153 } 154 InstIds[MI] = CurInstr; 155 ++CurInstr; 156 } 157 158 void ReachingDefAnalysis::reprocessBasicBlock(MachineBasicBlock *MBB) { 159 unsigned MBBNumber = MBB->getNumber(); 160 assert(MBBNumber < MBBReachingDefs.size() && 161 "Unexpected basic block number."); 162 163 // Count number of non-debug instructions for end of block adjustment. 164 auto NonDbgInsts = 165 instructionsWithoutDebug(MBB->instr_begin(), MBB->instr_end()); 166 int NumInsts = std::distance(NonDbgInsts.begin(), NonDbgInsts.end()); 167 168 // When reprocessing a block, the only thing we need to do is check whether 169 // there is now a more recent incoming reaching definition from a predecessor. 170 for (MachineBasicBlock *pred : MBB->predecessors()) { 171 assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() && 172 "Should have pre-allocated MBBInfos for all MBBs"); 173 const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()]; 174 // Incoming may be empty for dead predecessors. 175 if (Incoming.empty()) 176 continue; 177 178 for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) { 179 int Def = Incoming[Unit]; 180 if (Def == ReachingDefDefaultVal) 181 continue; 182 183 auto Start = MBBReachingDefs[MBBNumber][Unit].begin(); 184 if (Start != MBBReachingDefs[MBBNumber][Unit].end() && *Start < 0) { 185 if (*Start >= Def) 186 continue; 187 188 // Update existing reaching def from predecessor to a more recent one. 189 *Start = Def; 190 } else { 191 // Insert new reaching def from predecessor. 192 MBBReachingDefs[MBBNumber][Unit].insert(Start, Def); 193 } 194 195 // Update reaching def at end of of BB. Keep in mind that these are 196 // adjusted relative to the end of the basic block. 197 if (MBBOutRegsInfos[MBBNumber][Unit] < Def - NumInsts) 198 MBBOutRegsInfos[MBBNumber][Unit] = Def - NumInsts; 199 } 200 } 201 } 202 203 void ReachingDefAnalysis::processBasicBlock( 204 const LoopTraversal::TraversedMBBInfo &TraversedMBB) { 205 MachineBasicBlock *MBB = TraversedMBB.MBB; 206 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) 207 << (!TraversedMBB.IsDone ? ": incomplete\n" 208 : ": all preds known\n")); 209 210 if (!TraversedMBB.PrimaryPass) { 211 // Reprocess MBB that is part of a loop. 212 reprocessBasicBlock(MBB); 213 return; 214 } 215 216 enterBasicBlock(MBB); 217 for (MachineInstr &MI : 218 instructionsWithoutDebug(MBB->instr_begin(), MBB->instr_end())) 219 processDefs(&MI); 220 leaveBasicBlock(MBB); 221 } 222 223 bool ReachingDefAnalysis::runOnMachineFunction(MachineFunction &mf) { 224 MF = &mf; 225 TRI = MF->getSubtarget().getRegisterInfo(); 226 LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n"); 227 init(); 228 traverse(); 229 return false; 230 } 231 232 void ReachingDefAnalysis::releaseMemory() { 233 // Clear the internal vectors. 234 MBBOutRegsInfos.clear(); 235 MBBReachingDefs.clear(); 236 InstIds.clear(); 237 LiveRegs.clear(); 238 } 239 240 void ReachingDefAnalysis::reset() { 241 releaseMemory(); 242 init(); 243 traverse(); 244 } 245 246 void ReachingDefAnalysis::init() { 247 NumRegUnits = TRI->getNumRegUnits(); 248 MBBReachingDefs.resize(MF->getNumBlockIDs()); 249 // Initialize the MBBOutRegsInfos 250 MBBOutRegsInfos.resize(MF->getNumBlockIDs()); 251 LoopTraversal Traversal; 252 TraversedMBBOrder = Traversal.traverse(*MF); 253 } 254 255 void ReachingDefAnalysis::traverse() { 256 // Traverse the basic blocks. 257 for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) 258 processBasicBlock(TraversedMBB); 259 #ifndef NDEBUG 260 // Make sure reaching defs are sorted and unique. 261 for (MBBDefsInfo &MBBDefs : MBBReachingDefs) { 262 for (MBBRegUnitDefs &RegUnitDefs : MBBDefs) { 263 int LastDef = ReachingDefDefaultVal; 264 for (int Def : RegUnitDefs) { 265 assert(Def > LastDef && "Defs must be sorted and unique"); 266 LastDef = Def; 267 } 268 } 269 } 270 #endif 271 } 272 273 int ReachingDefAnalysis::getReachingDef(MachineInstr *MI, 274 MCRegister PhysReg) const { 275 assert(InstIds.count(MI) && "Unexpected machine instuction."); 276 int InstId = InstIds.lookup(MI); 277 int DefRes = ReachingDefDefaultVal; 278 unsigned MBBNumber = MI->getParent()->getNumber(); 279 assert(MBBNumber < MBBReachingDefs.size() && 280 "Unexpected basic block number."); 281 int LatestDef = ReachingDefDefaultVal; 282 for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) { 283 for (int Def : MBBReachingDefs[MBBNumber][*Unit]) { 284 if (Def >= InstId) 285 break; 286 DefRes = Def; 287 } 288 LatestDef = std::max(LatestDef, DefRes); 289 } 290 return LatestDef; 291 } 292 293 MachineInstr * 294 ReachingDefAnalysis::getReachingLocalMIDef(MachineInstr *MI, 295 MCRegister PhysReg) const { 296 return hasLocalDefBefore(MI, PhysReg) 297 ? getInstFromId(MI->getParent(), getReachingDef(MI, PhysReg)) 298 : nullptr; 299 } 300 301 bool ReachingDefAnalysis::hasSameReachingDef(MachineInstr *A, MachineInstr *B, 302 MCRegister PhysReg) const { 303 MachineBasicBlock *ParentA = A->getParent(); 304 MachineBasicBlock *ParentB = B->getParent(); 305 if (ParentA != ParentB) 306 return false; 307 308 return getReachingDef(A, PhysReg) == getReachingDef(B, PhysReg); 309 } 310 311 MachineInstr *ReachingDefAnalysis::getInstFromId(MachineBasicBlock *MBB, 312 int InstId) const { 313 assert(static_cast<size_t>(MBB->getNumber()) < MBBReachingDefs.size() && 314 "Unexpected basic block number."); 315 assert(InstId < static_cast<int>(MBB->size()) && 316 "Unexpected instruction id."); 317 318 if (InstId < 0) 319 return nullptr; 320 321 for (auto &MI : *MBB) { 322 auto F = InstIds.find(&MI); 323 if (F != InstIds.end() && F->second == InstId) 324 return &MI; 325 } 326 327 return nullptr; 328 } 329 330 int ReachingDefAnalysis::getClearance(MachineInstr *MI, 331 MCRegister PhysReg) const { 332 assert(InstIds.count(MI) && "Unexpected machine instuction."); 333 return InstIds.lookup(MI) - getReachingDef(MI, PhysReg); 334 } 335 336 bool ReachingDefAnalysis::hasLocalDefBefore(MachineInstr *MI, 337 MCRegister PhysReg) const { 338 return getReachingDef(MI, PhysReg) >= 0; 339 } 340 341 void ReachingDefAnalysis::getReachingLocalUses(MachineInstr *Def, 342 MCRegister PhysReg, 343 InstSet &Uses) const { 344 MachineBasicBlock *MBB = Def->getParent(); 345 MachineBasicBlock::iterator MI = MachineBasicBlock::iterator(Def); 346 while (++MI != MBB->end()) { 347 if (MI->isDebugInstr()) 348 continue; 349 350 // If/when we find a new reaching def, we know that there's no more uses 351 // of 'Def'. 352 if (getReachingLocalMIDef(&*MI, PhysReg) != Def) 353 return; 354 355 for (auto &MO : MI->operands()) { 356 if (!isValidRegUseOf(MO, PhysReg, TRI)) 357 continue; 358 359 Uses.insert(&*MI); 360 if (MO.isKill()) 361 return; 362 } 363 } 364 } 365 366 bool ReachingDefAnalysis::getLiveInUses(MachineBasicBlock *MBB, 367 MCRegister PhysReg, 368 InstSet &Uses) const { 369 for (MachineInstr &MI : 370 instructionsWithoutDebug(MBB->instr_begin(), MBB->instr_end())) { 371 for (auto &MO : MI.operands()) { 372 if (!isValidRegUseOf(MO, PhysReg, TRI)) 373 continue; 374 if (getReachingDef(&MI, PhysReg) >= 0) 375 return false; 376 Uses.insert(&MI); 377 } 378 } 379 auto Last = MBB->getLastNonDebugInstr(); 380 if (Last == MBB->end()) 381 return true; 382 return isReachingDefLiveOut(&*Last, PhysReg); 383 } 384 385 void ReachingDefAnalysis::getGlobalUses(MachineInstr *MI, MCRegister PhysReg, 386 InstSet &Uses) const { 387 MachineBasicBlock *MBB = MI->getParent(); 388 389 // Collect the uses that each def touches within the block. 390 getReachingLocalUses(MI, PhysReg, Uses); 391 392 // Handle live-out values. 393 if (auto *LiveOut = getLocalLiveOutMIDef(MI->getParent(), PhysReg)) { 394 if (LiveOut != MI) 395 return; 396 397 SmallVector<MachineBasicBlock *, 4> ToVisit(MBB->successors()); 398 SmallPtrSet<MachineBasicBlock*, 4>Visited; 399 while (!ToVisit.empty()) { 400 MachineBasicBlock *MBB = ToVisit.pop_back_val(); 401 if (Visited.count(MBB) || !MBB->isLiveIn(PhysReg)) 402 continue; 403 if (getLiveInUses(MBB, PhysReg, Uses)) 404 llvm::append_range(ToVisit, MBB->successors()); 405 Visited.insert(MBB); 406 } 407 } 408 } 409 410 void ReachingDefAnalysis::getGlobalReachingDefs(MachineInstr *MI, 411 MCRegister PhysReg, 412 InstSet &Defs) const { 413 if (auto *Def = getUniqueReachingMIDef(MI, PhysReg)) { 414 Defs.insert(Def); 415 return; 416 } 417 418 for (auto *MBB : MI->getParent()->predecessors()) 419 getLiveOuts(MBB, PhysReg, Defs); 420 } 421 422 void ReachingDefAnalysis::getLiveOuts(MachineBasicBlock *MBB, 423 MCRegister PhysReg, InstSet &Defs) const { 424 SmallPtrSet<MachineBasicBlock*, 2> VisitedBBs; 425 getLiveOuts(MBB, PhysReg, Defs, VisitedBBs); 426 } 427 428 void ReachingDefAnalysis::getLiveOuts(MachineBasicBlock *MBB, 429 MCRegister PhysReg, InstSet &Defs, 430 BlockSet &VisitedBBs) const { 431 if (VisitedBBs.count(MBB)) 432 return; 433 434 VisitedBBs.insert(MBB); 435 LivePhysRegs LiveRegs(*TRI); 436 LiveRegs.addLiveOuts(*MBB); 437 if (LiveRegs.available(MBB->getParent()->getRegInfo(), PhysReg)) 438 return; 439 440 if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg)) 441 Defs.insert(Def); 442 else 443 for (auto *Pred : MBB->predecessors()) 444 getLiveOuts(Pred, PhysReg, Defs, VisitedBBs); 445 } 446 447 MachineInstr * 448 ReachingDefAnalysis::getUniqueReachingMIDef(MachineInstr *MI, 449 MCRegister PhysReg) const { 450 // If there's a local def before MI, return it. 451 MachineInstr *LocalDef = getReachingLocalMIDef(MI, PhysReg); 452 if (LocalDef && InstIds.lookup(LocalDef) < InstIds.lookup(MI)) 453 return LocalDef; 454 455 SmallPtrSet<MachineInstr*, 2> Incoming; 456 MachineBasicBlock *Parent = MI->getParent(); 457 for (auto *Pred : Parent->predecessors()) 458 getLiveOuts(Pred, PhysReg, Incoming); 459 460 // Check that we have a single incoming value and that it does not 461 // come from the same block as MI - since it would mean that the def 462 // is executed after MI. 463 if (Incoming.size() == 1 && (*Incoming.begin())->getParent() != Parent) 464 return *Incoming.begin(); 465 return nullptr; 466 } 467 468 MachineInstr *ReachingDefAnalysis::getMIOperand(MachineInstr *MI, 469 unsigned Idx) const { 470 assert(MI->getOperand(Idx).isReg() && "Expected register operand"); 471 return getUniqueReachingMIDef(MI, MI->getOperand(Idx).getReg()); 472 } 473 474 MachineInstr *ReachingDefAnalysis::getMIOperand(MachineInstr *MI, 475 MachineOperand &MO) const { 476 assert(MO.isReg() && "Expected register operand"); 477 return getUniqueReachingMIDef(MI, MO.getReg()); 478 } 479 480 bool ReachingDefAnalysis::isRegUsedAfter(MachineInstr *MI, 481 MCRegister PhysReg) const { 482 MachineBasicBlock *MBB = MI->getParent(); 483 LivePhysRegs LiveRegs(*TRI); 484 LiveRegs.addLiveOuts(*MBB); 485 486 // Yes if the register is live out of the basic block. 487 if (!LiveRegs.available(MBB->getParent()->getRegInfo(), PhysReg)) 488 return true; 489 490 // Walk backwards through the block to see if the register is live at some 491 // point. 492 for (MachineInstr &Last : 493 instructionsWithoutDebug(MBB->instr_rbegin(), MBB->instr_rend())) { 494 LiveRegs.stepBackward(Last); 495 if (!LiveRegs.available(MBB->getParent()->getRegInfo(), PhysReg)) 496 return InstIds.lookup(&Last) > InstIds.lookup(MI); 497 } 498 return false; 499 } 500 501 bool ReachingDefAnalysis::isRegDefinedAfter(MachineInstr *MI, 502 MCRegister PhysReg) const { 503 MachineBasicBlock *MBB = MI->getParent(); 504 auto Last = MBB->getLastNonDebugInstr(); 505 if (Last != MBB->end() && 506 getReachingDef(MI, PhysReg) != getReachingDef(&*Last, PhysReg)) 507 return true; 508 509 if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg)) 510 return Def == getReachingLocalMIDef(MI, PhysReg); 511 512 return false; 513 } 514 515 bool ReachingDefAnalysis::isReachingDefLiveOut(MachineInstr *MI, 516 MCRegister PhysReg) const { 517 MachineBasicBlock *MBB = MI->getParent(); 518 LivePhysRegs LiveRegs(*TRI); 519 LiveRegs.addLiveOuts(*MBB); 520 if (LiveRegs.available(MBB->getParent()->getRegInfo(), PhysReg)) 521 return false; 522 523 auto Last = MBB->getLastNonDebugInstr(); 524 int Def = getReachingDef(MI, PhysReg); 525 if (Last != MBB->end() && getReachingDef(&*Last, PhysReg) != Def) 526 return false; 527 528 // Finally check that the last instruction doesn't redefine the register. 529 for (auto &MO : Last->operands()) 530 if (isValidRegDefOf(MO, PhysReg, TRI)) 531 return false; 532 533 return true; 534 } 535 536 MachineInstr * 537 ReachingDefAnalysis::getLocalLiveOutMIDef(MachineBasicBlock *MBB, 538 MCRegister PhysReg) const { 539 LivePhysRegs LiveRegs(*TRI); 540 LiveRegs.addLiveOuts(*MBB); 541 if (LiveRegs.available(MBB->getParent()->getRegInfo(), PhysReg)) 542 return nullptr; 543 544 auto Last = MBB->getLastNonDebugInstr(); 545 if (Last == MBB->end()) 546 return nullptr; 547 548 int Def = getReachingDef(&*Last, PhysReg); 549 for (auto &MO : Last->operands()) 550 if (isValidRegDefOf(MO, PhysReg, TRI)) 551 return &*Last; 552 553 return Def < 0 ? nullptr : getInstFromId(MBB, Def); 554 } 555 556 static bool mayHaveSideEffects(MachineInstr &MI) { 557 return MI.mayLoadOrStore() || MI.mayRaiseFPException() || 558 MI.hasUnmodeledSideEffects() || MI.isTerminator() || 559 MI.isCall() || MI.isBarrier() || MI.isBranch() || MI.isReturn(); 560 } 561 562 // Can we safely move 'From' to just before 'To'? To satisfy this, 'From' must 563 // not define a register that is used by any instructions, after and including, 564 // 'To'. These instructions also must not redefine any of Froms operands. 565 template<typename Iterator> 566 bool ReachingDefAnalysis::isSafeToMove(MachineInstr *From, 567 MachineInstr *To) const { 568 if (From->getParent() != To->getParent() || From == To) 569 return false; 570 571 SmallSet<int, 2> Defs; 572 // First check that From would compute the same value if moved. 573 for (auto &MO : From->operands()) { 574 if (!isValidReg(MO)) 575 continue; 576 if (MO.isDef()) 577 Defs.insert(MO.getReg()); 578 else if (!hasSameReachingDef(From, To, MO.getReg())) 579 return false; 580 } 581 582 // Now walk checking that the rest of the instructions will compute the same 583 // value and that we're not overwriting anything. Don't move the instruction 584 // past any memory, control-flow or other ambiguous instructions. 585 for (auto I = ++Iterator(From), E = Iterator(To); I != E; ++I) { 586 if (mayHaveSideEffects(*I)) 587 return false; 588 for (auto &MO : I->operands()) 589 if (MO.isReg() && MO.getReg() && Defs.count(MO.getReg())) 590 return false; 591 } 592 return true; 593 } 594 595 bool ReachingDefAnalysis::isSafeToMoveForwards(MachineInstr *From, 596 MachineInstr *To) const { 597 using Iterator = MachineBasicBlock::iterator; 598 // Walk forwards until we find the instruction. 599 for (auto I = Iterator(From), E = From->getParent()->end(); I != E; ++I) 600 if (&*I == To) 601 return isSafeToMove<Iterator>(From, To); 602 return false; 603 } 604 605 bool ReachingDefAnalysis::isSafeToMoveBackwards(MachineInstr *From, 606 MachineInstr *To) const { 607 using Iterator = MachineBasicBlock::reverse_iterator; 608 // Walk backwards until we find the instruction. 609 for (auto I = Iterator(From), E = From->getParent()->rend(); I != E; ++I) 610 if (&*I == To) 611 return isSafeToMove<Iterator>(From, To); 612 return false; 613 } 614 615 bool ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI, 616 InstSet &ToRemove) const { 617 SmallPtrSet<MachineInstr*, 1> Ignore; 618 SmallPtrSet<MachineInstr*, 2> Visited; 619 return isSafeToRemove(MI, Visited, ToRemove, Ignore); 620 } 621 622 bool 623 ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI, InstSet &ToRemove, 624 InstSet &Ignore) const { 625 SmallPtrSet<MachineInstr*, 2> Visited; 626 return isSafeToRemove(MI, Visited, ToRemove, Ignore); 627 } 628 629 bool 630 ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI, InstSet &Visited, 631 InstSet &ToRemove, InstSet &Ignore) const { 632 if (Visited.count(MI) || Ignore.count(MI)) 633 return true; 634 else if (mayHaveSideEffects(*MI)) { 635 // Unless told to ignore the instruction, don't remove anything which has 636 // side effects. 637 return false; 638 } 639 640 Visited.insert(MI); 641 for (auto &MO : MI->operands()) { 642 if (!isValidRegDef(MO)) 643 continue; 644 645 SmallPtrSet<MachineInstr*, 4> Uses; 646 getGlobalUses(MI, MO.getReg(), Uses); 647 648 for (auto I : Uses) { 649 if (Ignore.count(I) || ToRemove.count(I)) 650 continue; 651 if (!isSafeToRemove(I, Visited, ToRemove, Ignore)) 652 return false; 653 } 654 } 655 ToRemove.insert(MI); 656 return true; 657 } 658 659 void ReachingDefAnalysis::collectKilledOperands(MachineInstr *MI, 660 InstSet &Dead) const { 661 Dead.insert(MI); 662 auto IsDead = [this, &Dead](MachineInstr *Def, MCRegister PhysReg) { 663 if (mayHaveSideEffects(*Def)) 664 return false; 665 666 unsigned LiveDefs = 0; 667 for (auto &MO : Def->operands()) { 668 if (!isValidRegDef(MO)) 669 continue; 670 if (!MO.isDead()) 671 ++LiveDefs; 672 } 673 674 if (LiveDefs > 1) 675 return false; 676 677 SmallPtrSet<MachineInstr*, 4> Uses; 678 getGlobalUses(Def, PhysReg, Uses); 679 return llvm::set_is_subset(Uses, Dead); 680 }; 681 682 for (auto &MO : MI->operands()) { 683 if (!isValidRegUse(MO)) 684 continue; 685 if (MachineInstr *Def = getMIOperand(MI, MO)) 686 if (IsDead(Def, MO.getReg())) 687 collectKilledOperands(Def, Dead); 688 } 689 } 690 691 bool ReachingDefAnalysis::isSafeToDefRegAt(MachineInstr *MI, 692 MCRegister PhysReg) const { 693 SmallPtrSet<MachineInstr*, 1> Ignore; 694 return isSafeToDefRegAt(MI, PhysReg, Ignore); 695 } 696 697 bool ReachingDefAnalysis::isSafeToDefRegAt(MachineInstr *MI, MCRegister PhysReg, 698 InstSet &Ignore) const { 699 // Check for any uses of the register after MI. 700 if (isRegUsedAfter(MI, PhysReg)) { 701 if (auto *Def = getReachingLocalMIDef(MI, PhysReg)) { 702 SmallPtrSet<MachineInstr*, 2> Uses; 703 getGlobalUses(Def, PhysReg, Uses); 704 if (!llvm::set_is_subset(Uses, Ignore)) 705 return false; 706 } else 707 return false; 708 } 709 710 MachineBasicBlock *MBB = MI->getParent(); 711 // Check for any defs after MI. 712 if (isRegDefinedAfter(MI, PhysReg)) { 713 auto I = MachineBasicBlock::iterator(MI); 714 for (auto E = MBB->end(); I != E; ++I) { 715 if (Ignore.count(&*I)) 716 continue; 717 for (auto &MO : I->operands()) 718 if (isValidRegDefOf(MO, PhysReg, TRI)) 719 return false; 720 } 721 } 722 return true; 723 } 724