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