[mir-canon][NFC] Move MIR Vreg renaming code to separate file for better reuse.

[plotfi]

Summary

This change is actually NFC. I will post a pass that uses the virtual register naming code from MIRCanonicalizatioPass to only rename vregs for the purposes of making MIR tests more readable.

[paquette]

This is just code movement, but still a couple of nits/questions.

Only thing I think that I'd really like to see here is some documentation in the header file for functions, classes, etc. If this is going to be shared between some passes, I think it makes sense to document what each thing does, and how these things fit together.

And, since we're moving it all anyway, I guess it'd be worth making function/variable names fit the standard style while we're here.

llvm/lib/CodeGen/MIRVRegNamerUtils.cpp

15–20

• Move Doxygen comment to the header?
• s/An/A/

21

Now that this isn't fully tied to the canonicalizer, I think it would make sense to give it a more descriptive name?

E.g. findInstructionsWithSideEffects or something?

51

Same thing here? Basically, anything with "candidate" makes less sense outside the context of a specific pass.

(Maybe it would make sense to pack all of this into a Renamer struct/class or something. I don't have any strong opinions there though.)

llvm/lib/CodeGen/MIRVRegNamerUtils.h

29

I guess from the name, in concept it's obvious what this class *is*, but it would be nice to have a Doxygen comment documenting what its purpose is etc.

30

While we're here, might as well rename things to fit the style guide?

e.g. Type, Reg, etc.

31

Use Register instead of unsigned? Or is this your own thing? (We started using Register instead of unsigned for registers recently.)

50

This class could use a Doxygen comment as well. It's a little less obvious what it does.

57

skipVRegs

63

Why 1000?

100

getVRegRenameMap

[plotfi]

llvm/lib/CodeGen/MIRVRegNamerUtils.h

29

Actually at second glance, I dont think these need to be exposed outside of the .cpp file.

[plotfi]

Moving the guts of the candidate walk loop into the reusable MIRVRegNamer.cpp library

[plotfi]

llvm/lib/CodeGen/MIRVRegNamerUtils.cpp

21

I've decided to isolate these from the header file. So for now the names can remain without confusion.

51

Agreed. I can consider changing everything named "candidate" to something else, but I'd rather do it in another commit. I've wrapped most of the functions into an anonymous namespace in the cpp file at this point.

[plotfi]

addressing @paquette's suggestions.

[plotfi]

llvm/lib/CodeGen/MIRVRegNamerUtils.h

63

It's used as a default value for skipping indices between BBs and side-effect tree roots. I've made it an optional parameter of the NamedVRegCursor.

[paquette]

LGTM with some nits on comments.

llvm/lib/CodeGen/MIRVRegNamerUtils.h

36

Judging by the SkipGapSize comment below, I think you wanted to document this?

I guess it's probably a good idea anyway, considering you can initialize it etc?

46–47

s/SkipGapSize/skipVRegs/

[plotfi]

More comments.

llvm/lib/CodeGen/CMakeLists.txt

add_llvm_library(LLVMCodeGen
   RegAllocFast.cpp
   RegAllocGreedy.cpp
   RegAllocPBQP.cpp
   RegisterClassInfo.cpp
   RegisterCoalescer.cpp
   RegisterPressure.cpp
   RegisterScavenging.cpp
   RenameIndependentSubregs.cpp
+  MIRVRegNamerUtils.cpp
   MIRCanonicalizerPass.cpp
   RegisterUsageInfo.cpp
   RegUsageInfoCollector.cpp
   RegUsageInfoPropagate.cpp
   ResetMachineFunctionPass.cpp
   SafeStack.cpp
   SafeStackColoring.cpp
   SafeStackLayout.cpp

llvm/lib/CodeGen/MIRCanonicalizerPass.cpp

 
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/Support/raw_ostream.h"
+#include "MIRVRegNamerUtils.h"
 
 #include <queue>
 
 using namespace llvm;
 
 namespace llvm {
 extern char &MIRCanonicalizerID;
 } // namespace llvm
void getAnalysisUsage(AnalysisUsage &AU) const override {
     MachineFunctionPass::getAnalysisUsage(AU);
   }
 
   bool runOnMachineFunction(MachineFunction &MF) override;
 };
 
 } // end anonymous namespace
 
-enum VRType { RSE_Reg = 0, RSE_FrameIndex, RSE_NewCandidate };
-class TypedVReg {
-  VRType type;
-  unsigned reg;
-
-public:
-  TypedVReg(unsigned reg) : type(RSE_Reg), reg(reg) {}
-  TypedVReg(VRType type) : type(type), reg(~0U) {
-    assert(type != RSE_Reg && "Expected a non-register type.");
-  }
-
-  bool isReg() const { return type == RSE_Reg; }
-  bool isFrameIndex() const { return type == RSE_FrameIndex; }
-  bool isCandidate() const { return type == RSE_NewCandidate; }
-
-  VRType getType() const { return type; }
-  unsigned getReg() const {
-    assert(this->isReg() && "Expected a virtual or physical register.");
-    return reg;
-  }
-};
-
 char MIRCanonicalizer::ID;
 
 char &llvm::MIRCanonicalizerID = MIRCanonicalizer::ID;
 
 INITIALIZE_PASS_BEGIN(MIRCanonicalizer, "mir-canonicalizer",
                       "Rename Register Operands Canonically", false, false)
 
 INITIALIZE_PASS_END(MIRCanonicalizer, "mir-canonicalizer",
for (MachineInstr *MI : Copies) {
 
     Changed = true;
     MI->eraseFromParent();
   }
 
   return Changed;
 }
 
-/// Here we find our candidates. What makes an interesting candidate?
-/// An candidate for a canonicalization tree root is normally any kind of
-/// instruction that causes side effects such as a store to memory or a copy to
-/// a physical register or a return instruction. We use these as an expression
-/// tree root that we walk inorder to build a canonical walk which should result
-/// in canoncal vreg renaming.
-static std::vector<MachineInstr *> populateCandidates(MachineBasicBlock *MBB) {
-  std::vector<MachineInstr *> Candidates;
-  MachineRegisterInfo &MRI = MBB->getParent()->getRegInfo();
-
-  for (auto II = MBB->begin(), IE = MBB->end(); II != IE; ++II) {
-    MachineInstr *MI = &*II;
-
-    bool DoesMISideEffect = false;
-
-    if (MI->getNumOperands() > 0 && MI->getOperand(0).isReg()) {
-      const Register Dst = MI->getOperand(0).getReg();
-      DoesMISideEffect |= !Register::isVirtualRegister(Dst);
-
-      for (auto UI = MRI.use_begin(Dst); UI != MRI.use_end(); ++UI) {
-        if (DoesMISideEffect)
-          break;
-        DoesMISideEffect |= (UI->getParent()->getParent() != MI->getParent());
-      }
-    }
-
-    if (!MI->mayStore() && !MI->isBranch() && !DoesMISideEffect)
-      continue;
-
-    LLVM_DEBUG(dbgs() << "Found Candidate:  "; MI->dump(););
-    Candidates.push_back(MI);
-  }
-
-  return Candidates;
-}
-
-static void doCandidateWalk(std::vector<TypedVReg> &VRegs,
-                            std::queue<TypedVReg> &RegQueue,
-                            std::vector<MachineInstr *> &VisitedMIs,
-                            const MachineBasicBlock *MBB) {
-
-  const MachineFunction &MF = *MBB->getParent();
-  const MachineRegisterInfo &MRI = MF.getRegInfo();
-
-  while (!RegQueue.empty()) {
-
-    auto TReg = RegQueue.front();
-    RegQueue.pop();
-
-    if (TReg.isFrameIndex()) {
-      LLVM_DEBUG(dbgs() << "Popping frame index.\n";);
-      VRegs.push_back(TypedVReg(RSE_FrameIndex));
-      continue;
-    }
-
-    assert(TReg.isReg() && "Expected vreg or physreg.");
-    unsigned Reg = TReg.getReg();
-
-    if (Register::isVirtualRegister(Reg)) {
-      LLVM_DEBUG({
-        dbgs() << "Popping vreg ";
-        MRI.def_begin(Reg)->dump();
-        dbgs() << "\n";
-      });
-
-      if (!llvm::any_of(VRegs, [&](const TypedVReg &TR) {
-            return TR.isReg() && TR.getReg() == Reg;
-          })) {
-        VRegs.push_back(TypedVReg(Reg));
-      }
-    } else {
-      LLVM_DEBUG(dbgs() << "Popping physreg.\n";);
-      VRegs.push_back(TypedVReg(Reg));
-      continue;
-    }
-
-    for (auto RI = MRI.def_begin(Reg), RE = MRI.def_end(); RI != RE; ++RI) {
-      MachineInstr *Def = RI->getParent();
-
-      if (Def->getParent() != MBB)
-        continue;
-
-      if (llvm::any_of(VisitedMIs,
-                       [&](const MachineInstr *VMI) { return Def == VMI; })) {
-        break;
-      }
-
-      LLVM_DEBUG({
-        dbgs() << "\n========================\n";
-        dbgs() << "Visited MI: ";
-        Def->dump();
-        dbgs() << "BB Name: " << Def->getParent()->getName() << "\n";
-        dbgs() << "\n========================\n";
-      });
-      VisitedMIs.push_back(Def);
-      for (unsigned I = 1, E = Def->getNumOperands(); I != E; ++I) {
-
-        MachineOperand &MO = Def->getOperand(I);
-        if (MO.isFI()) {
-          LLVM_DEBUG(dbgs() << "Pushing frame index.\n";);
-          RegQueue.push(TypedVReg(RSE_FrameIndex));
-        }
-
-        if (!MO.isReg())
-          continue;
-        RegQueue.push(TypedVReg(MO.getReg()));
-      }
-    }
-  }
-}
-
-namespace {
-class NamedVRegCursor {
-  MachineRegisterInfo &MRI;
-  unsigned virtualVRegNumber;
-
-public:
-  NamedVRegCursor(MachineRegisterInfo &MRI) : MRI(MRI), virtualVRegNumber(0) {}
-
-  void SkipVRegs() {
-    unsigned VRegGapIndex = 1;
-    if (!virtualVRegNumber) {
-      VRegGapIndex = 0;
-      virtualVRegNumber = MRI.createIncompleteVirtualRegister();
-    }
-    const unsigned VR_GAP = (++VRegGapIndex * 1000);
-
-    unsigned I = virtualVRegNumber;
-    const unsigned E = (((I + VR_GAP) / VR_GAP) + 1) * VR_GAP;
-
-    virtualVRegNumber = E;
-  }
-
-  unsigned getVirtualVReg() const { return virtualVRegNumber; }
-
-  unsigned incrementVirtualVReg(unsigned incr = 1) {
-    virtualVRegNumber += incr;
-    return virtualVRegNumber;
-  }
-
-  unsigned createVirtualRegister(unsigned VReg) {
-    if (!virtualVRegNumber)
-      SkipVRegs();
-    std::string S;
-    raw_string_ostream OS(S);
-    OS << "namedVReg" << (virtualVRegNumber & ~0x80000000);
-    OS.flush();
-    virtualVRegNumber++;
-    if (auto RC = MRI.getRegClassOrNull(VReg))
-      return MRI.createVirtualRegister(RC, OS.str());
-    return MRI.createGenericVirtualRegister(MRI.getType(VReg), OS.str());
-  }
-};
-} // namespace
-
-static std::map<unsigned, unsigned>
-GetVRegRenameMap(const std::vector<TypedVReg> &VRegs,
-                 const std::vector<unsigned> &renamedInOtherBB,
-                 MachineRegisterInfo &MRI, NamedVRegCursor &NVC) {
-  std::map<unsigned, unsigned> VRegRenameMap;
-  bool FirstCandidate = true;
-
-  for (auto &vreg : VRegs) {
-    if (vreg.isFrameIndex()) {
-      // We skip one vreg for any frame index because there is a good chance
-      // (especially when comparing SelectionDAG to GlobalISel generated MIR)
-      // that in the other file we are just getting an incoming vreg that comes
-      // from a copy from a frame index. So it's safe to skip by one.
-      unsigned LastRenameReg = NVC.incrementVirtualVReg();
-      (void)LastRenameReg;
-      LLVM_DEBUG(dbgs() << "Skipping rename for FI " << LastRenameReg << "\n";);
-      continue;
-    } else if (vreg.isCandidate()) {
-
-      // After the first candidate, for every subsequent candidate, we skip mod
-      // 10 registers so that the candidates are more likely to start at the
-      // same vreg number making it more likely that the canonical walk from the
-      // candidate insruction. We don't need to skip from the first candidate of
-      // the BasicBlock because we already skip ahead several vregs for each BB.
-      unsigned LastRenameReg = NVC.getVirtualVReg();
-      if (FirstCandidate)
-        NVC.incrementVirtualVReg(LastRenameReg % 10);
-      FirstCandidate = false;
-      continue;
-    } else if (!Register::isVirtualRegister(vreg.getReg())) {
-      unsigned LastRenameReg = NVC.incrementVirtualVReg();
-      (void)LastRenameReg;
-      LLVM_DEBUG({
-        dbgs() << "Skipping rename for Phys Reg " << LastRenameReg << "\n";
-      });
-      continue;
-    }
-
-    auto Reg = vreg.getReg();
-    if (llvm::find(renamedInOtherBB, Reg) != renamedInOtherBB.end()) {
-      LLVM_DEBUG(dbgs() << "Vreg " << Reg
-                        << " already renamed in other BB.\n";);
-      continue;
-    }
-
-    auto Rename = NVC.createVirtualRegister(Reg);
-
-    if (VRegRenameMap.find(Reg) == VRegRenameMap.end()) {
-      LLVM_DEBUG(dbgs() << "Mapping vreg ";);
-      if (MRI.reg_begin(Reg) != MRI.reg_end()) {
-        LLVM_DEBUG(auto foo = &*MRI.reg_begin(Reg); foo->dump(););
-      } else {
-        LLVM_DEBUG(dbgs() << Reg;);
-      }
-      LLVM_DEBUG(dbgs() << " to ";);
-      if (MRI.reg_begin(Rename) != MRI.reg_end()) {
-        LLVM_DEBUG(auto foo = &*MRI.reg_begin(Rename); foo->dump(););
-      } else {
-        LLVM_DEBUG(dbgs() << Rename;);
-      }
-      LLVM_DEBUG(dbgs() << "\n";);
-
-      VRegRenameMap.insert(std::pair<unsigned, unsigned>(Reg, Rename));
-    }
-  }
-
-  return VRegRenameMap;
-}
-
-static bool doVRegRenaming(std::vector<unsigned> &RenamedInOtherBB,
-                           const std::map<unsigned, unsigned> &VRegRenameMap,
-                           MachineRegisterInfo &MRI) {
-  bool Changed = false;
-  for (auto I = VRegRenameMap.begin(), E = VRegRenameMap.end(); I != E; ++I) {
-
-    auto VReg = I->first;
-    auto Rename = I->second;
-
-    RenamedInOtherBB.push_back(Rename);
-
-    std::vector<MachineOperand *> RenameMOs;
-    for (auto &MO : MRI.reg_operands(VReg)) {
-      RenameMOs.push_back(&MO);
-    }
-
-    for (auto *MO : RenameMOs) {
-      Changed = true;
-      MO->setReg(Rename);
-
-      if (!MO->isDef())
-        MO->setIsKill(false);
-    }
-  }
-
-  return Changed;
-}
-
 static bool doDefKillClear(MachineBasicBlock *MBB) {
   bool Changed = false;
 
   for (auto &MI : *MBB) {
     for (auto &MO : MI.operands()) {
       if (!MO.isReg())
         continue;
       if (!MO.isDef() && MO.isKill()) {

llvm/lib/CodeGen/MIRVRegNamerUtils.h

+//===------------ MIRVRegNamerUtils.h - MIR VReg Renaming Utilities -------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// The purpose of these utilities is to abstract out parts of the MIRCanon pass
+// that are responsible for renaming virtual registers with the purpose of
+// sharing code with a MIRVRegNamer pass that could be the analog of the
+// opt -instnamer pass.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include <queue>
+
+using namespace llvm;
+
+enum VRType { RSE_Reg = 0, RSE_FrameIndex, RSE_NewCandidate };
+class TypedVReg {
+  VRType type;
+  unsigned reg;
+
+public:
+  TypedVReg(unsigned reg) : type(RSE_Reg), reg(reg) {}
+  TypedVReg(VRType type) : type(type), reg(~0U) {
+    assert(type != RSE_Reg && "Expected a non-register type.");
+  }
+
+  bool isReg() const { return type == RSE_Reg; }
+  bool isFrameIndex() const { return type == RSE_FrameIndex; }
+  bool isCandidate() const { return type == RSE_NewCandidate; }
+
+  VRType getType() const { return type; }
+  unsigned getReg() const {
+    assert(this->isReg() && "Expected a virtual or physical register.");
+    return reg;
+  }
+};
+
+class NamedVRegCursor {
+  MachineRegisterInfo &MRI;
+  unsigned virtualVRegNumber;
+
+public:
+  NamedVRegCursor(MachineRegisterInfo &MRI) : MRI(MRI), virtualVRegNumber(0) {}
+
+  void SkipVRegs() {
+    unsigned VRegGapIndex = 1;
+    if (!virtualVRegNumber) {
+      VRegGapIndex = 0;
+      virtualVRegNumber = MRI.createIncompleteVirtualRegister();
+    }
+    const unsigned VR_GAP = (++VRegGapIndex * 1000);
+
+    unsigned I = virtualVRegNumber;
+    const unsigned E = (((I + VR_GAP) / VR_GAP) + 1) * VR_GAP;
+
+    virtualVRegNumber = E;
+  }
+
+  unsigned getVirtualVReg() const { return virtualVRegNumber; }
+
+  unsigned incrementVirtualVReg(unsigned incr = 1) {
+    virtualVRegNumber += incr;
+    return virtualVRegNumber;
+  }
+
+  unsigned createVirtualRegister(unsigned VReg) {
+    if (!virtualVRegNumber)
+      SkipVRegs();
+    std::string S;
+    raw_string_ostream OS(S);
+    OS << "namedVReg" << (virtualVRegNumber & ~0x80000000);
+    OS.flush();
+    virtualVRegNumber++;
+    if (auto RC = MRI.getRegClassOrNull(VReg))
+      return MRI.createVirtualRegister(RC, OS.str());
+    return MRI.createGenericVirtualRegister(MRI.getType(VReg), OS.str());
+  }
+};
+
+std::vector<MachineInstr *> populateCandidates(MachineBasicBlock *MBB);
+
+void doCandidateWalk(std::vector<TypedVReg> &VRegs,
+                     std::queue<TypedVReg> &RegQueue,
+                     std::vector<MachineInstr *> &VisitedMIs,
+                     const MachineBasicBlock *MBB);
+
+std::map<unsigned, unsigned>
+GetVRegRenameMap(const std::vector<TypedVReg> &VRegs,
+                 const std::vector<unsigned> &renamedInOtherBB,
+                 MachineRegisterInfo &MRI, NamedVRegCursor &NVC);
+
+bool doVRegRenaming(std::vector<unsigned> &RenamedInOtherBB,
+                    const std::map<unsigned, unsigned> &VRegRenameMap,
+                    MachineRegisterInfo &MRI);

llvm/lib/CodeGen/MIRVRegNamerUtils.cpp

+//===---------- MIRVRegNamerUtils.cpp - MIR VReg Renaming Utilities -------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "MIRVRegNamerUtils.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "mir-vregnamer-utils"
+
+/// Here we find our candidates. What makes an interesting candidate?
+/// An candidate for a canonicalization tree root is normally any kind of
+/// instruction that causes side effects such as a store to memory or a copy to
+/// a physical register or a return instruction. We use these as an expression
+/// tree root that we walk inorder to build a canonical walk which should result
+/// in canoncal vreg renaming.
+std::vector<MachineInstr *> populateCandidates(MachineBasicBlock *MBB) {
+  std::vector<MachineInstr *> Candidates;
+  MachineRegisterInfo &MRI = MBB->getParent()->getRegInfo();
+
+  for (auto II = MBB->begin(), IE = MBB->end(); II != IE; ++II) {
+    MachineInstr *MI = &*II;
+
+    bool DoesMISideEffect = false;
+
+    if (MI->getNumOperands() > 0 && MI->getOperand(0).isReg()) {
+      const Register Dst = MI->getOperand(0).getReg();
+      DoesMISideEffect |= !Register::isVirtualRegister(Dst);
+
+      for (auto UI = MRI.use_begin(Dst); UI != MRI.use_end(); ++UI) {
+        if (DoesMISideEffect)
+          break;
+        DoesMISideEffect |= (UI->getParent()->getParent() != MI->getParent());
+      }
+    }
+
+    if (!MI->mayStore() && !MI->isBranch() && !DoesMISideEffect)
+      continue;
+
+    LLVM_DEBUG(dbgs() << "Found Candidate:  "; MI->dump(););
+    Candidates.push_back(MI);
+  }
+
+  return Candidates;
+}
+
+void doCandidateWalk(std::vector<TypedVReg> &VRegs,
+                     std::queue<TypedVReg> &RegQueue,
+                     std::vector<MachineInstr *> &VisitedMIs,
+                     const MachineBasicBlock *MBB) {
+
+  const MachineFunction &MF = *MBB->getParent();
+  const MachineRegisterInfo &MRI = MF.getRegInfo();
+
+  while (!RegQueue.empty()) {
+
+    auto TReg = RegQueue.front();
+    RegQueue.pop();
+
+    if (TReg.isFrameIndex()) {
+      LLVM_DEBUG(dbgs() << "Popping frame index.\n";);
+      VRegs.push_back(TypedVReg(RSE_FrameIndex));
+      continue;
+    }
+
+    assert(TReg.isReg() && "Expected vreg or physreg.");
+    unsigned Reg = TReg.getReg();
+
+    if (Register::isVirtualRegister(Reg)) {
+      LLVM_DEBUG({
+        dbgs() << "Popping vreg ";
+        MRI.def_begin(Reg)->dump();
+        dbgs() << "\n";
+      });
+
+      if (!llvm::any_of(VRegs, [&](const TypedVReg &TR) {
+            return TR.isReg() && TR.getReg() == Reg;
+          })) {
+        VRegs.push_back(TypedVReg(Reg));
+      }
+    } else {
+      LLVM_DEBUG(dbgs() << "Popping physreg.\n";);
+      VRegs.push_back(TypedVReg(Reg));
+      continue;
+    }
+
+    for (auto RI = MRI.def_begin(Reg), RE = MRI.def_end(); RI != RE; ++RI) {
+      MachineInstr *Def = RI->getParent();
+
+      if (Def->getParent() != MBB)
+        continue;
+
+      if (llvm::any_of(VisitedMIs,
+                       [&](const MachineInstr *VMI) { return Def == VMI; })) {
+        break;
+      }
+
+      LLVM_DEBUG({
+        dbgs() << "\n========================\n";
+        dbgs() << "Visited MI: ";
+        Def->dump();
+        dbgs() << "BB Name: " << Def->getParent()->getName() << "\n";
+        dbgs() << "\n========================\n";
+      });
+      VisitedMIs.push_back(Def);
+      for (unsigned I = 1, E = Def->getNumOperands(); I != E; ++I) {
+
+        MachineOperand &MO = Def->getOperand(I);
+        if (MO.isFI()) {
+          LLVM_DEBUG(dbgs() << "Pushing frame index.\n";);
+          RegQueue.push(TypedVReg(RSE_FrameIndex));
+        }
+
+        if (!MO.isReg())
+          continue;
+        RegQueue.push(TypedVReg(MO.getReg()));
+      }
+    }
+  }
+}
+
+std::map<unsigned, unsigned>
+GetVRegRenameMap(const std::vector<TypedVReg> &VRegs,
+                 const std::vector<unsigned> &renamedInOtherBB,
+                 MachineRegisterInfo &MRI, NamedVRegCursor &NVC) {
+  std::map<unsigned, unsigned> VRegRenameMap;
+  bool FirstCandidate = true;
+
+  for (auto &vreg : VRegs) {
+    if (vreg.isFrameIndex()) {
+      // We skip one vreg for any frame index because there is a good chance
+      // (especially when comparing SelectionDAG to GlobalISel generated MIR)
+      // that in the other file we are just getting an incoming vreg that comes
+      // from a copy from a frame index. So it's safe to skip by one.
+      unsigned LastRenameReg = NVC.incrementVirtualVReg();
+      (void)LastRenameReg;
+      LLVM_DEBUG(dbgs() << "Skipping rename for FI " << LastRenameReg << "\n";);
+      continue;
+    } else if (vreg.isCandidate()) {
+
+      // After the first candidate, for every subsequent candidate, we skip mod
+      // 10 registers so that the candidates are more likely to start at the
+      // same vreg number making it more likely that the canonical walk from the
+      // candidate insruction. We don't need to skip from the first candidate of
+      // the BasicBlock because we already skip ahead several vregs for each BB.
+      unsigned LastRenameReg = NVC.getVirtualVReg();
+      if (FirstCandidate)
+        NVC.incrementVirtualVReg(LastRenameReg % 10);
+      FirstCandidate = false;
+      continue;
+    } else if (!Register::isVirtualRegister(vreg.getReg())) {
+      unsigned LastRenameReg = NVC.incrementVirtualVReg();
+      (void)LastRenameReg;
+      LLVM_DEBUG({
+        dbgs() << "Skipping rename for Phys Reg " << LastRenameReg << "\n";
+      });
+      continue;
+    }
+
+    auto Reg = vreg.getReg();
+    if (llvm::find(renamedInOtherBB, Reg) != renamedInOtherBB.end()) {
+      LLVM_DEBUG(dbgs() << "Vreg " << Reg
+                        << " already renamed in other BB.\n";);
+      continue;
+    }
+
+    auto Rename = NVC.createVirtualRegister(Reg);
+
+    if (VRegRenameMap.find(Reg) == VRegRenameMap.end()) {
+      LLVM_DEBUG(dbgs() << "Mapping vreg ";);
+      if (MRI.reg_begin(Reg) != MRI.reg_end()) {
+        LLVM_DEBUG(auto foo = &*MRI.reg_begin(Reg); foo->dump(););
+      } else {
+        LLVM_DEBUG(dbgs() << Reg;);
+      }
+      LLVM_DEBUG(dbgs() << " to ";);
+      if (MRI.reg_begin(Rename) != MRI.reg_end()) {
+        LLVM_DEBUG(auto foo = &*MRI.reg_begin(Rename); foo->dump(););
+      } else {
+        LLVM_DEBUG(dbgs() << Rename;);
+      }
+      LLVM_DEBUG(dbgs() << "\n";);
+
+      VRegRenameMap.insert(std::pair<unsigned, unsigned>(Reg, Rename));
+    }
+  }
+
+  return VRegRenameMap;
+}
+
+bool doVRegRenaming(std::vector<unsigned> &RenamedInOtherBB,
+                    const std::map<unsigned, unsigned> &VRegRenameMap,
+                    MachineRegisterInfo &MRI) {
+  bool Changed = false;
+  for (auto I = VRegRenameMap.begin(), E = VRegRenameMap.end(); I != E; ++I) {
+
+    auto VReg = I->first;
+    auto Rename = I->second;
+
+    RenamedInOtherBB.push_back(Rename);
+
+    std::vector<MachineOperand *> RenameMOs;
+    for (auto &MO : MRI.reg_operands(VReg)) {
+      RenameMOs.push_back(&MO);
+    }
+
+    for (auto *MO : RenameMOs) {
+      Changed = true;
+      MO->setReg(Rename);
+
+      if (!MO->isDef())
+        MO->setIsKill(false);
+    }
+  }
+
+  return Changed;
+}