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