lib/CodeGen/MIRCanonicalizerPass.cpp

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