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