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