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