contrib/llvm-project/llvm/lib/CodeGen/MIRCanonicalizerPass.cpp

   1 //===-------------- MIRCanonicalizer.cpp - MIR Canonicalizer --------------===//
   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 // The purpose of this pass is to employ a canonical code transformation so
  10 // that code compiled with slightly different IR passes can be diffed more
  11 // effectively than otherwise. This is done by renaming vregs in a given
  12 // LiveRange in a canonical way. This pass also does a pseudo-scheduling to
  13 // move defs closer to their use inorder to reduce diffs caused by slightly
  14 // different schedules.
  15 //
  16 // Basic Usage:
  17 //
  18 // llc -o - -run-pass mir-canonicalizer example.mir
  19 //
  20 // Reorders instructions canonically.
  21 // Renames virtual register operands canonically.
  22 // Strips certain MIR artifacts (optionally).
  23 //
  24 //===----------------------------------------------------------------------===//
  25
  26 #include "llvm/ADT/PostOrderIterator.h"
  27 #include "llvm/ADT/STLExtras.h"
  28 #include "llvm/CodeGen/MachineFunctionPass.h"
  29 #include "llvm/CodeGen/MachineInstrBuilder.h"
  30 #include "llvm/CodeGen/MachineRegisterInfo.h"
  31 #include "llvm/CodeGen/Passes.h"
  32 #include "llvm/Support/raw_ostream.h"
  33
  34 #include <queue>
  35
  36 using namespace llvm;
  37
  38 namespace llvm {
  39 extern char &MIRCanonicalizerID;
  40 } // namespace llvm
  41
  42 #define DEBUG_TYPE "mir-canonicalizer"
  43
  44 static cl::opt<unsigned>
  45     CanonicalizeFunctionNumber("canon-nth-function", cl::Hidden, cl::init(~0u),
  46                                cl::value_desc("N"),
  47                                cl::desc("Function number to canonicalize."));
  48
  49 static cl::opt<unsigned> CanonicalizeBasicBlockNumber(
  50     "canon-nth-basicblock", cl::Hidden, cl::init(~0u), cl::value_desc("N"),
  51     cl::desc("BasicBlock number to canonicalize."));
  52
  53 namespace {
  54
  55 class MIRCanonicalizer : public MachineFunctionPass {
  56 public:
  57   static char ID;
  58   MIRCanonicalizer() : MachineFunctionPass(ID) {}
  59
  60   StringRef getPassName() const override {
  61     return "Rename register operands in a canonical ordering.";
  62   }
  63
  64   void getAnalysisUsage(AnalysisUsage &AU) const override {
  65     AU.setPreservesCFG();
  66     MachineFunctionPass::getAnalysisUsage(AU);
  67   }
  68
  69   bool runOnMachineFunction(MachineFunction &MF) override;
  70 };
  71
  72 } // end anonymous namespace
  73
  74 enum VRType { RSE_Reg = 0, RSE_FrameIndex, RSE_NewCandidate };
  75 class TypedVReg {
  76   VRType type;
  77   unsigned reg;
  78
  79 public:
  80   TypedVReg(unsigned reg) : type(RSE_Reg), reg(reg) {}
  81   TypedVReg(VRType type) : type(type), reg(~0U) {
  82     assert(type != RSE_Reg && "Expected a non-register type.");
  83   }
  84
  85   bool isReg() const { return type == RSE_Reg; }
  86   bool isFrameIndex() const { return type == RSE_FrameIndex; }
  87   bool isCandidate() const { return type == RSE_NewCandidate; }
  88
  89   VRType getType() const { return type; }
  90   unsigned getReg() const {
  91     assert(this->isReg() && "Expected a virtual or physical register.");
  92     return reg;
  93   }
  94 };
  95
  96 char MIRCanonicalizer::ID;
  97
  98 char &llvm::MIRCanonicalizerID = MIRCanonicalizer::ID;
  99
 100 INITIALIZE_PASS_BEGIN(MIRCanonicalizer, "mir-canonicalizer",
 101                       "Rename Register Operands Canonically", false, false)
 102
 103 INITIALIZE_PASS_END(MIRCanonicalizer, "mir-canonicalizer",
 104                     "Rename Register Operands Canonically", false, false)
 105
 106 static std::vector<MachineBasicBlock *> GetRPOList(MachineFunction &MF) {
 107   if (MF.empty())
 108     return {};
 109   ReversePostOrderTraversal<MachineBasicBlock *> RPOT(&*MF.begin());
 110   std::vector<MachineBasicBlock *> RPOList;
 111   for (auto MBB : RPOT) {
 112     RPOList.push_back(MBB);
 113   }
 114
 115   return RPOList;
 116 }
 117
 118 static bool
 119 rescheduleLexographically(std::vector<MachineInstr *> instructions,
 120                           MachineBasicBlock *MBB,
 121                           std::function<MachineBasicBlock::iterator()> getPos) {
 122
 123   bool Changed = false;
 124   using StringInstrPair = std::pair<std::string, MachineInstr *>;
 125   std::vector<StringInstrPair> StringInstrMap;
 126
 127   for (auto *II : instructions) {
 128     std::string S;
 129     raw_string_ostream OS(S);
 130     II->print(OS);
 131     OS.flush();
 132
 133     // Trim the assignment, or start from the begining in the case of a store.
 134     const size_t i = S.find("=");
 135     StringInstrMap.push_back({(i == std::string::npos) ? S : S.substr(i), II});
 136   }
 137
 138   llvm::sort(StringInstrMap,
 139              [](const StringInstrPair &a, const StringInstrPair &b) -> bool {
 140                return (a.first < b.first);
 141              });
 142
 143   for (auto &II : StringInstrMap) {
 144
 145     LLVM_DEBUG({
 146       dbgs() << "Splicing ";
 147       II.second->dump();
 148       dbgs() << " right before: ";
 149       getPos()->dump();
 150     });
 151
 152     Changed = true;
 153     MBB->splice(getPos(), MBB, II.second);
 154   }
 155
 156   return Changed;
 157 }
 158
 159 static bool rescheduleCanonically(unsigned &PseudoIdempotentInstCount,
 160                                   MachineBasicBlock *MBB) {
 161
 162   bool Changed = false;
 163
 164   // Calculates the distance of MI from the begining of its parent BB.
 165   auto getInstrIdx = [](const MachineInstr &MI) {
 166     unsigned i = 0;
 167     for (auto &CurMI : *MI.getParent()) {
 168       if (&CurMI == &MI)
 169         return i;
 170       i++;
 171     }
 172     return ~0U;
 173   };
 174
 175   // Pre-Populate vector of instructions to reschedule so that we don't
 176   // clobber the iterator.
 177   std::vector<MachineInstr *> Instructions;
 178   for (auto &MI : *MBB) {
 179     Instructions.push_back(&MI);
 180   }
 181
 182   std::map<MachineInstr *, std::vector<MachineInstr *>> MultiUsers;
 183   std::map<unsigned, MachineInstr *> MultiUserLookup;
 184   unsigned UseToBringDefCloserToCount = 0;
 185   std::vector<MachineInstr *> PseudoIdempotentInstructions;
 186   std::vector<unsigned> PhysRegDefs;
 187   for (auto *II : Instructions) {
 188     for (unsigned i = 1; i < II->getNumOperands(); i++) {
 189       MachineOperand &MO = II->getOperand(i);
 190       if (!MO.isReg())
 191         continue;
 192
 193       if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
 194         continue;
 195
 196       if (!MO.isDef())
 197         continue;
 198
 199       PhysRegDefs.push_back(MO.getReg());
 200     }
 201   }
 202
 203   for (auto *II : Instructions) {
 204     if (II->getNumOperands() == 0)
 205       continue;
 206     if (II->mayLoadOrStore())
 207       continue;
 208
 209     MachineOperand &MO = II->getOperand(0);
 210     if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
 211       continue;
 212     if (!MO.isDef())
 213       continue;
 214
 215     bool IsPseudoIdempotent = true;
 216     for (unsigned i = 1; i < II->getNumOperands(); i++) {
 217
 218       if (II->getOperand(i).isImm()) {
 219         continue;
 220       }
 221
 222       if (II->getOperand(i).isReg()) {
 223         if (!TargetRegisterInfo::isVirtualRegister(II->getOperand(i).getReg()))
 224           if (llvm::find(PhysRegDefs, II->getOperand(i).getReg()) ==
 225               PhysRegDefs.end()) {
 226             continue;
 227           }
 228       }
 229
 230       IsPseudoIdempotent = false;
 231       break;
 232     }
 233
 234     if (IsPseudoIdempotent) {
 235       PseudoIdempotentInstructions.push_back(II);
 236       continue;
 237     }
 238
 239     LLVM_DEBUG(dbgs() << "Operand " << 0 << " of "; II->dump(); MO.dump(););
 240
 241     MachineInstr *Def = II;
 242     unsigned Distance = ~0U;
 243     MachineInstr *UseToBringDefCloserTo = nullptr;
 244     MachineRegisterInfo *MRI = &MBB->getParent()->getRegInfo();
 245     for (auto &UO : MRI->use_nodbg_operands(MO.getReg())) {
 246       MachineInstr *UseInst = UO.getParent();
 247
 248       const unsigned DefLoc = getInstrIdx(*Def);
 249       const unsigned UseLoc = getInstrIdx(*UseInst);
 250       const unsigned Delta = (UseLoc - DefLoc);
 251
 252       if (UseInst->getParent() != Def->getParent())
 253         continue;
 254       if (DefLoc >= UseLoc)
 255         continue;
 256
 257       if (Delta < Distance) {
 258         Distance = Delta;
 259         UseToBringDefCloserTo = UseInst;
 260         MultiUserLookup[UseToBringDefCloserToCount++] = UseToBringDefCloserTo;
 261       }
 262     }
 263
 264     const auto BBE = MBB->instr_end();
 265     MachineBasicBlock::iterator DefI = BBE;
 266     MachineBasicBlock::iterator UseI = BBE;
 267
 268     for (auto BBI = MBB->instr_begin(); BBI != BBE; ++BBI) {
 269
 270       if (DefI != BBE && UseI != BBE)
 271         break;
 272
 273       if (&*BBI == Def) {
 274         DefI = BBI;
 275         continue;
 276       }
 277
 278       if (&*BBI == UseToBringDefCloserTo) {
 279         UseI = BBI;
 280         continue;
 281       }
 282     }
 283
 284     if (DefI == BBE || UseI == BBE)
 285       continue;
 286
 287     LLVM_DEBUG({
 288       dbgs() << "Splicing ";
 289       DefI->dump();
 290       dbgs() << " right before: ";
 291       UseI->dump();
 292     });
 293
 294     MultiUsers[UseToBringDefCloserTo].push_back(Def);
 295     Changed = true;
 296     MBB->splice(UseI, MBB, DefI);
 297   }
 298
 299   // Sort the defs for users of multiple defs lexographically.
 300   for (const auto &E : MultiUserLookup) {
 301
 302     auto UseI =
 303         std::find_if(MBB->instr_begin(), MBB->instr_end(),
 304                      [&](MachineInstr &MI) -> bool { return &MI == E.second; });
 305
 306     if (UseI == MBB->instr_end())
 307       continue;
 308
 309     LLVM_DEBUG(
 310         dbgs() << "Rescheduling Multi-Use Instructions Lexographically.";);
 311     Changed |= rescheduleLexographically(
 312         MultiUsers[E.second], MBB,
 313         [&]() -> MachineBasicBlock::iterator { return UseI; });
 314   }
 315
 316   PseudoIdempotentInstCount = PseudoIdempotentInstructions.size();
 317   LLVM_DEBUG(
 318       dbgs() << "Rescheduling Idempotent Instructions Lexographically.";);
 319   Changed |= rescheduleLexographically(
 320       PseudoIdempotentInstructions, MBB,
 321       [&]() -> MachineBasicBlock::iterator { return MBB->begin(); });
 322
 323   return Changed;
 324 }
 325
 326 static bool propagateLocalCopies(MachineBasicBlock *MBB) {
 327   bool Changed = false;
 328   MachineRegisterInfo &MRI = MBB->getParent()->getRegInfo();
 329
 330   std::vector<MachineInstr *> Copies;
 331   for (MachineInstr &MI : MBB->instrs()) {
 332     if (MI.isCopy())
 333       Copies.push_back(&MI);
 334   }
 335
 336   for (MachineInstr *MI : Copies) {
 337
 338     if (!MI->getOperand(0).isReg())
 339       continue;
 340     if (!MI->getOperand(1).isReg())
 341       continue;
 342
 343     const unsigned Dst = MI->getOperand(0).getReg();
 344     const unsigned Src = MI->getOperand(1).getReg();
 345
 346     if (!TargetRegisterInfo::isVirtualRegister(Dst))
 347       continue;
 348     if (!TargetRegisterInfo::isVirtualRegister(Src))
 349       continue;
 350     // Not folding COPY instructions if regbankselect has not set the RCs.
 351     // Why are we only considering Register Classes? Because the verifier
 352     // sometimes gets upset if the register classes don't match even if the
 353     // types do. A future patch might add COPY folding for matching types in
 354     // pre-registerbankselect code.
 355     if (!MRI.getRegClassOrNull(Dst))
 356       continue;
 357     if (MRI.getRegClass(Dst) != MRI.getRegClass(Src))
 358       continue;
 359
 360     std::vector<MachineOperand *> Uses;
 361     for (auto UI = MRI.use_begin(Dst); UI != MRI.use_end(); ++UI)
 362       Uses.push_back(&*UI);
 363     for (auto *MO : Uses)
 364       MO->setReg(Src);
 365
 366     Changed = true;
 367     MI->eraseFromParent();
 368   }
 369
 370   return Changed;
 371 }
 372
 373 /// Here we find our candidates. What makes an interesting candidate?
 374 /// An candidate for a canonicalization tree root is normally any kind of
 375 /// instruction that causes side effects such as a store to memory or a copy to
 376 /// a physical register or a return instruction. We use these as an expression
 377 /// tree root that we walk inorder to build a canonical walk which should result
 378 /// in canoncal vreg renaming.
 379 static std::vector<MachineInstr *> populateCandidates(MachineBasicBlock *MBB) {
 380   std::vector<MachineInstr *> Candidates;
 381   MachineRegisterInfo &MRI = MBB->getParent()->getRegInfo();
 382
 383   for (auto II = MBB->begin(), IE = MBB->end(); II != IE; ++II) {
 384     MachineInstr *MI = &*II;
 385
 386     bool DoesMISideEffect = false;
 387
 388     if (MI->getNumOperands() > 0 && MI->getOperand(0).isReg()) {
 389       const unsigned Dst = MI->getOperand(0).getReg();
 390       DoesMISideEffect |= !TargetRegisterInfo::isVirtualRegister(Dst);
 391
 392       for (auto UI = MRI.use_begin(Dst); UI != MRI.use_end(); ++UI) {
 393         if (DoesMISideEffect)
 394           break;
 395         DoesMISideEffect |= (UI->getParent()->getParent() != MI->getParent());
 396       }
 397     }
 398
 399     if (!MI->mayStore() && !MI->isBranch() && !DoesMISideEffect)
 400       continue;
 401
 402     LLVM_DEBUG(dbgs() << "Found Candidate:  "; MI->dump(););
 403     Candidates.push_back(MI);
 404   }
 405
 406   return Candidates;
 407 }
 408
 409 static void doCandidateWalk(std::vector<TypedVReg> &VRegs,
 410                             std::queue<TypedVReg> &RegQueue,
 411                             std::vector<MachineInstr *> &VisitedMIs,
 412                             const MachineBasicBlock *MBB) {
 413
 414   const MachineFunction &MF = *MBB->getParent();
 415   const MachineRegisterInfo &MRI = MF.getRegInfo();
 416
 417   while (!RegQueue.empty()) {
 418
 419     auto TReg = RegQueue.front();
 420     RegQueue.pop();
 421
 422     if (TReg.isFrameIndex()) {
 423       LLVM_DEBUG(dbgs() << "Popping frame index.\n";);
 424       VRegs.push_back(TypedVReg(RSE_FrameIndex));
 425       continue;
 426     }
 427
 428     assert(TReg.isReg() && "Expected vreg or physreg.");
 429     unsigned Reg = TReg.getReg();
 430
 431     if (TargetRegisterInfo::isVirtualRegister(Reg)) {
 432       LLVM_DEBUG({
 433         dbgs() << "Popping vreg ";
 434         MRI.def_begin(Reg)->dump();
 435         dbgs() << "\n";
 436       });
 437
 438       if (!llvm::any_of(VRegs, [&](const TypedVReg &TR) {
 439             return TR.isReg() && TR.getReg() == Reg;
 440           })) {
 441         VRegs.push_back(TypedVReg(Reg));
 442       }
 443     } else {
 444       LLVM_DEBUG(dbgs() << "Popping physreg.\n";);
 445       VRegs.push_back(TypedVReg(Reg));
 446       continue;
 447     }
 448
 449     for (auto RI = MRI.def_begin(Reg), RE = MRI.def_end(); RI != RE; ++RI) {
 450       MachineInstr *Def = RI->getParent();
 451
 452       if (Def->getParent() != MBB)
 453         continue;
 454
 455       if (llvm::any_of(VisitedMIs,
 456                        [&](const MachineInstr *VMI) { return Def == VMI; })) {
 457         break;
 458       }
 459
 460       LLVM_DEBUG({
 461         dbgs() << "\n========================\n";
 462         dbgs() << "Visited MI: ";
 463         Def->dump();
 464         dbgs() << "BB Name: " << Def->getParent()->getName() << "\n";
 465         dbgs() << "\n========================\n";
 466       });
 467       VisitedMIs.push_back(Def);
 468       for (unsigned I = 1, E = Def->getNumOperands(); I != E; ++I) {
 469
 470         MachineOperand &MO = Def->getOperand(I);
 471         if (MO.isFI()) {
 472           LLVM_DEBUG(dbgs() << "Pushing frame index.\n";);
 473           RegQueue.push(TypedVReg(RSE_FrameIndex));
 474         }
 475
 476         if (!MO.isReg())
 477           continue;
 478         RegQueue.push(TypedVReg(MO.getReg()));
 479       }
 480     }
 481   }
 482 }
 483
 484 namespace {
 485 class NamedVRegCursor {
 486   MachineRegisterInfo &MRI;
 487   unsigned virtualVRegNumber;
 488
 489 public:
 490   NamedVRegCursor(MachineRegisterInfo &MRI) : MRI(MRI), virtualVRegNumber(0) {}
 491
 492   void SkipVRegs() {
 493     unsigned VRegGapIndex = 1;
 494     if (!virtualVRegNumber) {
 495       VRegGapIndex = 0;
 496       virtualVRegNumber = MRI.createIncompleteVirtualRegister();
 497     }
 498     const unsigned VR_GAP = (++VRegGapIndex * 1000);
 499
 500     unsigned I = virtualVRegNumber;
 501     const unsigned E = (((I + VR_GAP) / VR_GAP) + 1) * VR_GAP;
 502
 503     virtualVRegNumber = E;
 504   }
 505
 506   unsigned getVirtualVReg() const { return virtualVRegNumber; }
 507
 508   unsigned incrementVirtualVReg(unsigned incr = 1) {
 509     virtualVRegNumber += incr;
 510     return virtualVRegNumber;
 511   }
 512
 513   unsigned createVirtualRegister(unsigned VReg) {
 514     if (!virtualVRegNumber)
 515       SkipVRegs();
 516     std::string S;
 517     raw_string_ostream OS(S);
 518     OS << "namedVReg" << (virtualVRegNumber & ~0x80000000);
 519     OS.flush();
 520     virtualVRegNumber++;
 521     if (auto RC = MRI.getRegClassOrNull(VReg))
 522       return MRI.createVirtualRegister(RC, OS.str());
 523     return MRI.createGenericVirtualRegister(MRI.getType(VReg), OS.str());
 524   }
 525 };
 526 } // namespace
 527
 528 static std::map<unsigned, unsigned>
 529 GetVRegRenameMap(const std::vector<TypedVReg> &VRegs,
 530                  const std::vector<unsigned> &renamedInOtherBB,
 531                  MachineRegisterInfo &MRI, NamedVRegCursor &NVC) {
 532   std::map<unsigned, unsigned> VRegRenameMap;
 533   bool FirstCandidate = true;
 534
 535   for (auto &vreg : VRegs) {
 536     if (vreg.isFrameIndex()) {
 537       // We skip one vreg for any frame index because there is a good chance
 538       // (especially when comparing SelectionDAG to GlobalISel generated MIR)
 539       // that in the other file we are just getting an incoming vreg that comes
 540       // from a copy from a frame index. So it's safe to skip by one.
 541       unsigned LastRenameReg = NVC.incrementVirtualVReg();
 542       (void)LastRenameReg;
 543       LLVM_DEBUG(dbgs() << "Skipping rename for FI " << LastRenameReg << "\n";);
 544       continue;
 545     } else if (vreg.isCandidate()) {
 546
 547       // After the first candidate, for every subsequent candidate, we skip mod
 548       // 10 registers so that the candidates are more likely to start at the
 549       // same vreg number making it more likely that the canonical walk from the
 550       // candidate insruction. We don't need to skip from the first candidate of
 551       // the BasicBlock because we already skip ahead several vregs for each BB.
 552       unsigned LastRenameReg = NVC.getVirtualVReg();
 553       if (FirstCandidate)
 554         NVC.incrementVirtualVReg(LastRenameReg % 10);
 555       FirstCandidate = false;
 556       continue;
 557     } else if (!TargetRegisterInfo::isVirtualRegister(vreg.getReg())) {
 558       unsigned LastRenameReg = NVC.incrementVirtualVReg();
 559       (void)LastRenameReg;
 560       LLVM_DEBUG({
 561         dbgs() << "Skipping rename for Phys Reg " << LastRenameReg << "\n";
 562       });
 563       continue;
 564     }
 565
 566     auto Reg = vreg.getReg();
 567     if (llvm::find(renamedInOtherBB, Reg) != renamedInOtherBB.end()) {
 568       LLVM_DEBUG(dbgs() << "Vreg " << Reg
 569                         << " already renamed in other BB.\n";);
 570       continue;
 571     }
 572
 573     auto Rename = NVC.createVirtualRegister(Reg);
 574
 575     if (VRegRenameMap.find(Reg) == VRegRenameMap.end()) {
 576       LLVM_DEBUG(dbgs() << "Mapping vreg ";);
 577       if (MRI.reg_begin(Reg) != MRI.reg_end()) {
 578         LLVM_DEBUG(auto foo = &*MRI.reg_begin(Reg); foo->dump(););
 579       } else {
 580         LLVM_DEBUG(dbgs() << Reg;);
 581       }
 582       LLVM_DEBUG(dbgs() << " to ";);
 583       if (MRI.reg_begin(Rename) != MRI.reg_end()) {
 584         LLVM_DEBUG(auto foo = &*MRI.reg_begin(Rename); foo->dump(););
 585       } else {
 586         LLVM_DEBUG(dbgs() << Rename;);
 587       }
 588       LLVM_DEBUG(dbgs() << "\n";);
 589
 590       VRegRenameMap.insert(std::pair<unsigned, unsigned>(Reg, Rename));
 591     }
 592   }
 593
 594   return VRegRenameMap;
 595 }
 596
 597 static bool doVRegRenaming(std::vector<unsigned> &RenamedInOtherBB,
 598                            const std::map<unsigned, unsigned> &VRegRenameMap,
 599                            MachineRegisterInfo &MRI) {
 600   bool Changed = false;
 601   for (auto I = VRegRenameMap.begin(), E = VRegRenameMap.end(); I != E; ++I) {
 602
 603     auto VReg = I->first;
 604     auto Rename = I->second;
 605
 606     RenamedInOtherBB.push_back(Rename);
 607
 608     std::vector<MachineOperand *> RenameMOs;
 609     for (auto &MO : MRI.reg_operands(VReg)) {
 610       RenameMOs.push_back(&MO);
 611     }
 612
 613     for (auto *MO : RenameMOs) {
 614       Changed = true;
 615       MO->setReg(Rename);
 616
 617       if (!MO->isDef())
 618         MO->setIsKill(false);
 619     }
 620   }
 621
 622   return Changed;
 623 }
 624
 625 static bool doDefKillClear(MachineBasicBlock *MBB) {
 626   bool Changed = false;
 627
 628   for (auto &MI : *MBB) {
 629     for (auto &MO : MI.operands()) {
 630       if (!MO.isReg())
 631         continue;
 632       if (!MO.isDef() && MO.isKill()) {
 633         Changed = true;
 634         MO.setIsKill(false);
 635       }
 636
 637       if (MO.isDef() && MO.isDead()) {
 638         Changed = true;
 639         MO.setIsDead(false);
 640       }
 641     }
 642   }
 643
 644   return Changed;
 645 }
 646
 647 static bool runOnBasicBlock(MachineBasicBlock *MBB,
 648                             std::vector<StringRef> &bbNames,
 649                             std::vector<unsigned> &renamedInOtherBB,
 650                             unsigned &basicBlockNum, unsigned &VRegGapIndex,
 651                             NamedVRegCursor &NVC) {
 652
 653   if (CanonicalizeBasicBlockNumber != ~0U) {
 654     if (CanonicalizeBasicBlockNumber != basicBlockNum++)
 655       return false;
 656     LLVM_DEBUG(dbgs() << "\n Canonicalizing BasicBlock " << MBB->getName()
 657                       << "\n";);
 658   }
 659
 660   if (llvm::find(bbNames, MBB->getName()) != bbNames.end()) {
 661     LLVM_DEBUG({
 662       dbgs() << "Found potentially duplicate BasicBlocks: " << MBB->getName()
 663              << "\n";
 664     });
 665     return false;
 666   }
 667
 668   LLVM_DEBUG({
 669     dbgs() << "\n\n  NEW BASIC BLOCK: " << MBB->getName() << "  \n\n";
 670     dbgs() << "\n\n================================================\n\n";
 671   });
 672
 673   bool Changed = false;
 674   MachineFunction &MF = *MBB->getParent();
 675   MachineRegisterInfo &MRI = MF.getRegInfo();
 676
 677   bbNames.push_back(MBB->getName());
 678   LLVM_DEBUG(dbgs() << "\n\n NEW BASIC BLOCK: " << MBB->getName() << "\n\n";);
 679
 680   LLVM_DEBUG(dbgs() << "MBB Before Canonical Copy Propagation:\n";
 681              MBB->dump(););
 682   Changed |= propagateLocalCopies(MBB);
 683   LLVM_DEBUG(dbgs() << "MBB After Canonical Copy Propagation:\n"; MBB->dump(););
 684
 685   LLVM_DEBUG(dbgs() << "MBB Before Scheduling:\n"; MBB->dump(););
 686   unsigned IdempotentInstCount = 0;
 687   Changed |= rescheduleCanonically(IdempotentInstCount, MBB);
 688   LLVM_DEBUG(dbgs() << "MBB After Scheduling:\n"; MBB->dump(););
 689
 690   std::vector<MachineInstr *> Candidates = populateCandidates(MBB);
 691   std::vector<MachineInstr *> VisitedMIs;
 692   llvm::copy(Candidates, std::back_inserter(VisitedMIs));
 693
 694   std::vector<TypedVReg> VRegs;
 695   for (auto candidate : Candidates) {
 696     VRegs.push_back(TypedVReg(RSE_NewCandidate));
 697
 698     std::queue<TypedVReg> RegQueue;
 699
 700     // Here we walk the vreg operands of a non-root node along our walk.
 701     // The root nodes are the original candidates (stores normally).
 702     // These are normally not the root nodes (except for the case of copies to
 703     // physical registers).
 704     for (unsigned i = 1; i < candidate->getNumOperands(); i++) {
 705       if (candidate->mayStore() || candidate->isBranch())
 706         break;
 707
 708       MachineOperand &MO = candidate->getOperand(i);
 709       if (!(MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg())))
 710         continue;
 711
 712       LLVM_DEBUG(dbgs() << "Enqueue register"; MO.dump(); dbgs() << "\n";);
 713       RegQueue.push(TypedVReg(MO.getReg()));
 714     }
 715
 716     // Here we walk the root candidates. We start from the 0th operand because
 717     // the root is normally a store to a vreg.
 718     for (unsigned i = 0; i < candidate->getNumOperands(); i++) {
 719
 720       if (!candidate->mayStore() && !candidate->isBranch())
 721         break;
 722
 723       MachineOperand &MO = candidate->getOperand(i);
 724
 725       // TODO: Do we want to only add vregs here?
 726       if (!MO.isReg() && !MO.isFI())
 727         continue;
 728
 729       LLVM_DEBUG(dbgs() << "Enqueue Reg/FI"; MO.dump(); dbgs() << "\n";);
 730
 731       RegQueue.push(MO.isReg() ? TypedVReg(MO.getReg())
 732                                : TypedVReg(RSE_FrameIndex));
 733     }
 734
 735     doCandidateWalk(VRegs, RegQueue, VisitedMIs, MBB);
 736   }
 737
 738   // If we have populated no vregs to rename then bail.
 739   // The rest of this function does the vreg remaping.
 740   if (VRegs.size() == 0)
 741     return Changed;
 742
 743   auto VRegRenameMap = GetVRegRenameMap(VRegs, renamedInOtherBB, MRI, NVC);
 744   Changed |= doVRegRenaming(renamedInOtherBB, VRegRenameMap, MRI);
 745
 746   // Here we renumber the def vregs for the idempotent instructions from the top
 747   // of the MachineBasicBlock so that they are named in the order that we sorted
 748   // them alphabetically. Eventually we wont need SkipVRegs because we will use
 749   // named vregs instead.
 750   if (IdempotentInstCount)
 751     NVC.SkipVRegs();
 752
 753   auto MII = MBB->begin();
 754   for (unsigned i = 0; i < IdempotentInstCount && MII != MBB->end(); ++i) {
 755     MachineInstr &MI = *MII++;
 756     Changed = true;
 757     unsigned vRegToRename = MI.getOperand(0).getReg();
 758     auto Rename = NVC.createVirtualRegister(vRegToRename);
 759
 760     std::vector<MachineOperand *> RenameMOs;
 761     for (auto &MO : MRI.reg_operands(vRegToRename)) {
 762       RenameMOs.push_back(&MO);
 763     }
 764
 765     for (auto *MO : RenameMOs) {
 766       MO->setReg(Rename);
 767     }
 768   }
 769
 770   Changed |= doDefKillClear(MBB);
 771
 772   LLVM_DEBUG(dbgs() << "Updated MachineBasicBlock:\n"; MBB->dump();
 773              dbgs() << "\n";);
 774   LLVM_DEBUG(
 775       dbgs() << "\n\n================================================\n\n");
 776   return Changed;
 777 }
 778
 779 bool MIRCanonicalizer::runOnMachineFunction(MachineFunction &MF) {
 780
 781   static unsigned functionNum = 0;
 782   if (CanonicalizeFunctionNumber != ~0U) {
 783     if (CanonicalizeFunctionNumber != functionNum++)
 784       return false;
 785     LLVM_DEBUG(dbgs() << "\n Canonicalizing Function " << MF.getName()
 786                       << "\n";);
 787   }
 788
 789   // we need a valid vreg to create a vreg type for skipping all those
 790   // stray vreg numbers so reach alignment/canonical vreg values.
 791   std::vector<MachineBasicBlock *> RPOList = GetRPOList(MF);
 792
 793   LLVM_DEBUG(
 794       dbgs() << "\n\n  NEW MACHINE FUNCTION: " << MF.getName() << "  \n\n";
 795       dbgs() << "\n\n================================================\n\n";
 796       dbgs() << "Total Basic Blocks: " << RPOList.size() << "\n";
 797       for (auto MBB
 798            : RPOList) { dbgs() << MBB->getName() << "\n"; } dbgs()
 799       << "\n\n================================================\n\n";);
 800
 801   std::vector<StringRef> BBNames;
 802   std::vector<unsigned> RenamedInOtherBB;
 803
 804   unsigned GapIdx = 0;
 805   unsigned BBNum = 0;
 806
 807   bool Changed = false;
 808
 809   MachineRegisterInfo &MRI = MF.getRegInfo();
 810   NamedVRegCursor NVC(MRI);
 811   for (auto MBB : RPOList)
 812     Changed |=
 813         runOnBasicBlock(MBB, BBNames, RenamedInOtherBB, BBNum, GapIdx, NVC);
 814
 815   return Changed;
 816 }