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.back();
 401       ToVisit.pop_back();
 402       if (Visited.count(MBB) || !MBB->isLiveIn(PhysReg))
 403         continue;
 404       if (getLiveInUses(MBB, PhysReg, Uses))
 405         llvm::append_range(ToVisit, MBB->successors());
 406       Visited.insert(MBB);
 407     }
 408   }
 409 }
 410
 411 void ReachingDefAnalysis::getGlobalReachingDefs(MachineInstr *MI,
 412                                                 MCRegister PhysReg,
 413                                                 InstSet &Defs) const {
 414   if (auto *Def = getUniqueReachingMIDef(MI, PhysReg)) {
 415     Defs.insert(Def);
 416     return;
 417   }
 418
 419   for (auto *MBB : MI->getParent()->predecessors())
 420     getLiveOuts(MBB, PhysReg, Defs);
 421 }
 422
 423 void ReachingDefAnalysis::getLiveOuts(MachineBasicBlock *MBB,
 424                                       MCRegister PhysReg, InstSet &Defs) const {
 425   SmallPtrSet<MachineBasicBlock*, 2> VisitedBBs;
 426   getLiveOuts(MBB, PhysReg, Defs, VisitedBBs);
 427 }
 428
 429 void ReachingDefAnalysis::getLiveOuts(MachineBasicBlock *MBB,
 430                                       MCRegister PhysReg, InstSet &Defs,
 431                                       BlockSet &VisitedBBs) const {
 432   if (VisitedBBs.count(MBB))
 433     return;
 434
 435   VisitedBBs.insert(MBB);
 436   LivePhysRegs LiveRegs(*TRI);
 437   LiveRegs.addLiveOuts(*MBB);
 438   if (LiveRegs.available(MBB->getParent()->getRegInfo(), PhysReg))
 439     return;
 440
 441   if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg))
 442     Defs.insert(Def);
 443   else
 444     for (auto *Pred : MBB->predecessors())
 445       getLiveOuts(Pred, PhysReg, Defs, VisitedBBs);
 446 }
 447
 448 MachineInstr *
 449 ReachingDefAnalysis::getUniqueReachingMIDef(MachineInstr *MI,
 450                                             MCRegister PhysReg) const {
 451   // If there's a local def before MI, return it.
 452   MachineInstr *LocalDef = getReachingLocalMIDef(MI, PhysReg);
 453   if (LocalDef && InstIds.lookup(LocalDef) < InstIds.lookup(MI))
 454     return LocalDef;
 455
 456   SmallPtrSet<MachineInstr*, 2> Incoming;
 457   MachineBasicBlock *Parent = MI->getParent();
 458   for (auto *Pred : Parent->predecessors())
 459     getLiveOuts(Pred, PhysReg, Incoming);
 460
 461   // Check that we have a single incoming value and that it does not
 462   // come from the same block as MI - since it would mean that the def
 463   // is executed after MI.
 464   if (Incoming.size() == 1 && (*Incoming.begin())->getParent() != Parent)
 465     return *Incoming.begin();
 466   return nullptr;
 467 }
 468
 469 MachineInstr *ReachingDefAnalysis::getMIOperand(MachineInstr *MI,
 470                                                 unsigned Idx) const {
 471   assert(MI->getOperand(Idx).isReg() && "Expected register operand");
 472   return getUniqueReachingMIDef(MI, MI->getOperand(Idx).getReg());
 473 }
 474
 475 MachineInstr *ReachingDefAnalysis::getMIOperand(MachineInstr *MI,
 476                                                 MachineOperand &MO) const {
 477   assert(MO.isReg() && "Expected register operand");
 478   return getUniqueReachingMIDef(MI, MO.getReg());
 479 }
 480
 481 bool ReachingDefAnalysis::isRegUsedAfter(MachineInstr *MI,
 482                                          MCRegister PhysReg) const {
 483   MachineBasicBlock *MBB = MI->getParent();
 484   LivePhysRegs LiveRegs(*TRI);
 485   LiveRegs.addLiveOuts(*MBB);
 486
 487   // Yes if the register is live out of the basic block.
 488   if (!LiveRegs.available(MBB->getParent()->getRegInfo(), PhysReg))
 489     return true;
 490
 491   // Walk backwards through the block to see if the register is live at some
 492   // point.
 493   for (MachineInstr &Last :
 494        instructionsWithoutDebug(MBB->instr_rbegin(), MBB->instr_rend())) {
 495     LiveRegs.stepBackward(Last);
 496     if (!LiveRegs.available(MBB->getParent()->getRegInfo(), PhysReg))
 497       return InstIds.lookup(&Last) > InstIds.lookup(MI);
 498   }
 499   return false;
 500 }
 501
 502 bool ReachingDefAnalysis::isRegDefinedAfter(MachineInstr *MI,
 503                                             MCRegister PhysReg) const {
 504   MachineBasicBlock *MBB = MI->getParent();
 505   auto Last = MBB->getLastNonDebugInstr();
 506   if (Last != MBB->end() &&
 507       getReachingDef(MI, PhysReg) != getReachingDef(&*Last, PhysReg))
 508     return true;
 509
 510   if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg))
 511     return Def == getReachingLocalMIDef(MI, PhysReg);
 512
 513   return false;
 514 }
 515
 516 bool ReachingDefAnalysis::isReachingDefLiveOut(MachineInstr *MI,
 517                                                MCRegister PhysReg) const {
 518   MachineBasicBlock *MBB = MI->getParent();
 519   LivePhysRegs LiveRegs(*TRI);
 520   LiveRegs.addLiveOuts(*MBB);
 521   if (LiveRegs.available(MBB->getParent()->getRegInfo(), PhysReg))
 522     return false;
 523
 524   auto Last = MBB->getLastNonDebugInstr();
 525   int Def = getReachingDef(MI, PhysReg);
 526   if (Last != MBB->end() && getReachingDef(&*Last, PhysReg) != Def)
 527     return false;
 528
 529   // Finally check that the last instruction doesn't redefine the register.
 530   for (auto &MO : Last->operands())
 531     if (isValidRegDefOf(MO, PhysReg, TRI))
 532       return false;
 533
 534   return true;
 535 }
 536
 537 MachineInstr *
 538 ReachingDefAnalysis::getLocalLiveOutMIDef(MachineBasicBlock *MBB,
 539                                           MCRegister PhysReg) const {
 540   LivePhysRegs LiveRegs(*TRI);
 541   LiveRegs.addLiveOuts(*MBB);
 542   if (LiveRegs.available(MBB->getParent()->getRegInfo(), PhysReg))
 543     return nullptr;
 544
 545   auto Last = MBB->getLastNonDebugInstr();
 546   if (Last == MBB->end())
 547     return nullptr;
 548
 549   int Def = getReachingDef(&*Last, PhysReg);
 550   for (auto &MO : Last->operands())
 551     if (isValidRegDefOf(MO, PhysReg, TRI))
 552       return &*Last;
 553
 554   return Def < 0 ? nullptr : getInstFromId(MBB, Def);
 555 }
 556
 557 static bool mayHaveSideEffects(MachineInstr &MI) {
 558   return MI.mayLoadOrStore() || MI.mayRaiseFPException() ||
 559          MI.hasUnmodeledSideEffects() || MI.isTerminator() ||
 560          MI.isCall() || MI.isBarrier() || MI.isBranch() || MI.isReturn();
 561 }
 562
 563 // Can we safely move 'From' to just before 'To'? To satisfy this, 'From' must
 564 // not define a register that is used by any instructions, after and including,
 565 // 'To'. These instructions also must not redefine any of Froms operands.
 566 template<typename Iterator>
 567 bool ReachingDefAnalysis::isSafeToMove(MachineInstr *From,
 568                                        MachineInstr *To) const {
 569   if (From->getParent() != To->getParent() || From == To)
 570     return false;
 571
 572   SmallSet<int, 2> Defs;
 573   // First check that From would compute the same value if moved.
 574   for (auto &MO : From->operands()) {
 575     if (!isValidReg(MO))
 576       continue;
 577     if (MO.isDef())
 578       Defs.insert(MO.getReg());
 579     else if (!hasSameReachingDef(From, To, MO.getReg()))
 580       return false;
 581   }
 582
 583   // Now walk checking that the rest of the instructions will compute the same
 584   // value and that we're not overwriting anything. Don't move the instruction
 585   // past any memory, control-flow or other ambiguous instructions.
 586   for (auto I = ++Iterator(From), E = Iterator(To); I != E; ++I) {
 587     if (mayHaveSideEffects(*I))
 588       return false;
 589     for (auto &MO : I->operands())
 590       if (MO.isReg() && MO.getReg() && Defs.count(MO.getReg()))
 591         return false;
 592   }
 593   return true;
 594 }
 595
 596 bool ReachingDefAnalysis::isSafeToMoveForwards(MachineInstr *From,
 597                                                MachineInstr *To) const {
 598   using Iterator = MachineBasicBlock::iterator;
 599   // Walk forwards until we find the instruction.
 600   for (auto I = Iterator(From), E = From->getParent()->end(); I != E; ++I)
 601     if (&*I == To)
 602       return isSafeToMove<Iterator>(From, To);
 603   return false;
 604 }
 605
 606 bool ReachingDefAnalysis::isSafeToMoveBackwards(MachineInstr *From,
 607                                                 MachineInstr *To) const {
 608   using Iterator = MachineBasicBlock::reverse_iterator;
 609   // Walk backwards until we find the instruction.
 610   for (auto I = Iterator(From), E = From->getParent()->rend(); I != E; ++I)
 611     if (&*I == To)
 612       return isSafeToMove<Iterator>(From, To);
 613   return false;
 614 }
 615
 616 bool ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI,
 617                                          InstSet &ToRemove) const {
 618   SmallPtrSet<MachineInstr*, 1> Ignore;
 619   SmallPtrSet<MachineInstr*, 2> Visited;
 620   return isSafeToRemove(MI, Visited, ToRemove, Ignore);
 621 }
 622
 623 bool
 624 ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI, InstSet &ToRemove,
 625                                     InstSet &Ignore) const {
 626   SmallPtrSet<MachineInstr*, 2> Visited;
 627   return isSafeToRemove(MI, Visited, ToRemove, Ignore);
 628 }
 629
 630 bool
 631 ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI, InstSet &Visited,
 632                                     InstSet &ToRemove, InstSet &Ignore) const {
 633   if (Visited.count(MI) || Ignore.count(MI))
 634     return true;
 635   else if (mayHaveSideEffects(*MI)) {
 636     // Unless told to ignore the instruction, don't remove anything which has
 637     // side effects.
 638     return false;
 639   }
 640
 641   Visited.insert(MI);
 642   for (auto &MO : MI->operands()) {
 643     if (!isValidRegDef(MO))
 644       continue;
 645
 646     SmallPtrSet<MachineInstr*, 4> Uses;
 647     getGlobalUses(MI, MO.getReg(), Uses);
 648
 649     for (auto I : Uses) {
 650       if (Ignore.count(I) || ToRemove.count(I))
 651         continue;
 652       if (!isSafeToRemove(I, Visited, ToRemove, Ignore))
 653         return false;
 654     }
 655   }
 656   ToRemove.insert(MI);
 657   return true;
 658 }
 659
 660 void ReachingDefAnalysis::collectKilledOperands(MachineInstr *MI,
 661                                                 InstSet &Dead) const {
 662   Dead.insert(MI);
 663   auto IsDead = [this, &Dead](MachineInstr *Def, MCRegister PhysReg) {
 664     if (mayHaveSideEffects(*Def))
 665       return false;
 666
 667     unsigned LiveDefs = 0;
 668     for (auto &MO : Def->operands()) {
 669       if (!isValidRegDef(MO))
 670         continue;
 671       if (!MO.isDead())
 672         ++LiveDefs;
 673     }
 674
 675     if (LiveDefs > 1)
 676       return false;
 677
 678     SmallPtrSet<MachineInstr*, 4> Uses;
 679     getGlobalUses(Def, PhysReg, Uses);
 680     return llvm::set_is_subset(Uses, Dead);
 681   };
 682
 683   for (auto &MO : MI->operands()) {
 684     if (!isValidRegUse(MO))
 685       continue;
 686     if (MachineInstr *Def = getMIOperand(MI, MO))
 687       if (IsDead(Def, MO.getReg()))
 688         collectKilledOperands(Def, Dead);
 689   }
 690 }
 691
 692 bool ReachingDefAnalysis::isSafeToDefRegAt(MachineInstr *MI,
 693                                            MCRegister PhysReg) const {
 694   SmallPtrSet<MachineInstr*, 1> Ignore;
 695   return isSafeToDefRegAt(MI, PhysReg, Ignore);
 696 }
 697
 698 bool ReachingDefAnalysis::isSafeToDefRegAt(MachineInstr *MI, MCRegister PhysReg,
 699                                            InstSet &Ignore) const {
 700   // Check for any uses of the register after MI.
 701   if (isRegUsedAfter(MI, PhysReg)) {
 702     if (auto *Def = getReachingLocalMIDef(MI, PhysReg)) {
 703       SmallPtrSet<MachineInstr*, 2> Uses;
 704       getGlobalUses(Def, PhysReg, Uses);
 705       if (!llvm::set_is_subset(Uses, Ignore))
 706         return false;
 707     } else
 708       return false;
 709   }
 710
 711   MachineBasicBlock *MBB = MI->getParent();
 712   // Check for any defs after MI.
 713   if (isRegDefinedAfter(MI, PhysReg)) {
 714     auto I = MachineBasicBlock::iterator(MI);
 715     for (auto E = MBB->end(); I != E; ++I) {
 716       if (Ignore.count(&*I))
 717         continue;
 718       for (auto &MO : I->operands())
 719         if (isValidRegDefOf(MO, PhysReg, TRI))
 720           return false;
 721     }
 722   }
 723   return true;
 724 }