[MirNamer][Canonicalizer]: Perform instruction semantic based renaming

https://reviews.llvm.org/D70210

Previously:

Due to sensitivity of the algorithm with gaps, and extra instructions,
when diffing, often we see naming being off by a few. Makes the diff
unreadable even for tests with 7 and 8 instructions respectively.
Naming can change depending on candidates (and order of picking
candidates). Suddenly if there's one extra instruction somewhere, the
entire subtree would be named completely differently.
No consistent naming of similar instructions which occur in different
functions. If we try to do something like count the frequency
distribution of various differences across suite, then the above
sensitivity issues are going to result in poor results.
Instead:

Name instruction based on semantics of the instruction (hash of the
opcode and operands). Essentially for a given instruction that occurs in
any module/function it'll be named similarly (ie semantic). This has
some nice properties
Can easily look at many instructions and just check the hash and if
they're named similarly, then it's the same instruction. Makes it very
easy to spot the same instruction both multiple times, as well as across
many functions (useful for frequency distribution).
Independent of traversal/candidates/depth of graph. No need to keep
track of last index/gaps/skip count etc.
No off by few issues with diffs. I've tried the old vs new
implementation in files ranging from 30 to 700 instructions. In both
cases with the old algorithm, diffs are a sea of red, where as for the
semantic version, in both cases, the diffs line up beautifully.
Simplified implementation of the main loop (simple iteration) , no keep
track of what's visited and not.
Handle collision just by incrementing a counter. Roughly
bb[N]_hash_[CollisionCount].
Additionally with the new implementation, we can probably avoid doing
the hoisting of instructions to various places, as they'll likely be
named the same resulting in differences only based on collision (ie
regardless of whether the instruction is hoisted or not/close to use or
not, it'll be named the same hash which should result in use of the
instruction be identical with the only change being the collision count)
which is very easy to spot visually.

4 files changed, 143 insertions, 369 deletions

diff --git a/llvm/lib/CodeGen/MIRCanonicalizerPass.cpp b/llvm/lib/CodeGen/MIRCanonicalizerPass.cpp
index c99959ce3ea..7a57cd6890d 100644
--- a/llvm/lib/CodeGen/MIRCanonicalizerPass.cpp
+++ b/llvm/lib/CodeGen/MIRCanonicalizerPass.cpp
@@ -375,7 +375,7 @@ static bool doDefKillClear(MachineBasicBlock *MBB) {
 
 static bool runOnBasicBlock(MachineBasicBlock *MBB,
                             std::vector<StringRef> &bbNames,
-                            unsigned &basicBlockNum, NamedVRegCursor &NVC) {
+                            unsigned &basicBlockNum, VRegRenamer &Renamer) {
 
   if (CanonicalizeBasicBlockNumber != ~0U) {
     if (CanonicalizeBasicBlockNumber != basicBlockNum++)
@@ -398,8 +398,6 @@ static bool runOnBasicBlock(MachineBasicBlock *MBB,
   });
 
   bool Changed = false;
-  MachineFunction &MF = *MBB->getParent();
-  MachineRegisterInfo &MRI = MF.getRegInfo();
 
   bbNames.push_back(MBB->getName());
   LLVM_DEBUG(dbgs() << "\n\n NEW BASIC BLOCK: " << MBB->getName() << "\n\n";);
@@ -414,31 +412,7 @@ static bool runOnBasicBlock(MachineBasicBlock *MBB,
   Changed |= rescheduleCanonically(IdempotentInstCount, MBB);
   LLVM_DEBUG(dbgs() << "MBB After Scheduling:\n"; MBB->dump(););
 
-  Changed |= NVC.renameVRegs(MBB);
-
-  // Here we renumber the def vregs for the idempotent instructions from the top
-  // of the MachineBasicBlock so that they are named in the order that we sorted
-  // them alphabetically. Eventually we wont need SkipVRegs because we will use
-  // named vregs instead.
-  if (IdempotentInstCount)
-    NVC.skipVRegs();
-
-  auto MII = MBB->begin();
-  for (unsigned i = 0; i < IdempotentInstCount && MII != MBB->end(); ++i) {
-    MachineInstr &MI = *MII++;
-    Changed = true;
-    Register vRegToRename = MI.getOperand(0).getReg();
-    auto Rename = NVC.createVirtualRegister(vRegToRename);
-
-    std::vector<MachineOperand *> RenameMOs;
-    for (auto &MO : MRI.reg_operands(vRegToRename)) {
-      RenameMOs.push_back(&MO);
-    }
-
-    for (auto *MO : RenameMOs) {
-      MO->setReg(Rename);
-    }
-  }
+  Changed |= Renamer.renameVRegs(MBB);
 
   Changed |= doDefKillClear(MBB);
 
@@ -478,9 +452,9 @@ bool MIRCanonicalizer::runOnMachineFunction(MachineFunction &MF) {
   bool Changed = false;
 
   MachineRegisterInfo &MRI = MF.getRegInfo();
-  NamedVRegCursor NVC(MRI);
+  VRegRenamer Renamer(MRI);
   for (auto MBB : RPOList)
-    Changed |= runOnBasicBlock(MBB, BBNames, BBNum, NVC);
+    Changed |= runOnBasicBlock(MBB, BBNames, BBNum, Renamer);
 
   return Changed;
 }
diff --git a/llvm/lib/CodeGen/MIRNamerPass.cpp b/llvm/lib/CodeGen/MIRNamerPass.cpp
index a3fda5c8762..62d0f2e52c7 100644
--- a/llvm/lib/CodeGen/MIRNamerPass.cpp
+++ b/llvm/lib/CodeGen/MIRNamerPass.cpp
@@ -55,11 +55,11 @@ public:
     if (MF.empty())
       return Changed;
 
-    NamedVRegCursor NVC(MF.getRegInfo());
+    VRegRenamer Renamer(MF.getRegInfo());
 
     ReversePostOrderTraversal<MachineBasicBlock *> RPOT(&*MF.begin());
     for (auto &MBB : RPOT)
-      Changed |= NVC.renameVRegs(MBB);
+      Changed |= Renamer.renameVRegs(MBB);
 
     return Changed;
   }
diff --git a/llvm/lib/CodeGen/MIRVRegNamerUtils.cpp b/llvm/lib/CodeGen/MIRVRegNamerUtils.cpp
index 6629000f468..0596234986c 100644
--- a/llvm/lib/CodeGen/MIRVRegNamerUtils.cpp
+++ b/llvm/lib/CodeGen/MIRVRegNamerUtils.cpp
@@ -13,226 +13,14 @@ using namespace llvm;
 
 #define DEBUG_TYPE "mir-vregnamer-utils"
 
-namespace {
-
-// TypedVReg and VRType are used to tell the renamer what to do at points in a
-// sequence of values to be renamed. A TypedVReg can either contain
-// an actual VReg, a FrameIndex, or it could just be a barrier for the next
-// candidate (side-effecting instruction). This tells the renamer to increment
-// to the next vreg name, or to skip modulo some skip-gap value.
-enum VRType { RSE_Reg = 0, RSE_FrameIndex, RSE_NewCandidate };
-class TypedVReg {
-  VRType Type;
-  Register Reg;
-
-public:
-  TypedVReg(Register 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; }
-  Register getReg() const {
-    assert(this->isReg() && "Expected a virtual or physical Register.");
-    return Reg;
-  }
-};
-
-/// Here we find our candidates. What makes an interesting candidate?
-/// A 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 in order to build a canonical walk which should
-/// result in canonical 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.");
-    Register 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<Register> &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<Register> &renamedInOtherBB,
-                    const std::map<unsigned, unsigned> &VRegRenameMap,
-                    MachineRegisterInfo &MRI) {
+bool VRegRenamer::doVRegRenaming(
+    const std::map<unsigned, unsigned> &VRegRenameMap) {
   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);
@@ -250,99 +38,108 @@ bool doVRegRenaming(std::vector<Register> &renamedInOtherBB,
   return Changed;
 }
 
-bool renameVRegs(MachineBasicBlock *MBB,
-                 std::vector<Register> &renamedInOtherBB,
-                 NamedVRegCursor &NVC) {
-  bool Changed = false;
-  MachineFunction &MF = *MBB->getParent();
-  MachineRegisterInfo &MRI = MF.getRegInfo();
-
-  std::vector<MachineInstr *> Candidates = populateCandidates(MBB);
-  std::vector<MachineInstr *> VisitedMIs;
-  llvm::copy(Candidates, std::back_inserter(VisitedMIs));
-
-  std::vector<TypedVReg> VRegs;
-  for (auto candidate : Candidates) {
-    VRegs.push_back(TypedVReg(RSE_NewCandidate));
-
-    std::queue<TypedVReg> RegQueue;
-
-    // Here we walk the vreg operands of a non-root node along our walk.
-    // The root nodes are the original candidates (stores normally).
-    // These are normally not the root nodes (except for the case of copies to
-    // physical registers).
-    for (unsigned i = 1; i < candidate->getNumOperands(); i++) {
-      if (candidate->mayStore() || candidate->isBranch())
-        break;
+std::map<unsigned, unsigned>
+VRegRenamer::getVRegRenameMap(const std::vector<NamedVReg> &VRegs) {
+  std::map<unsigned, unsigned> VRegRenameMap;
 
-      MachineOperand &MO = candidate->getOperand(i);
-      if (!(MO.isReg() && Register::isVirtualRegister(MO.getReg())))
-        continue;
+  std::map<std::string, unsigned> VRegNameCollisionMap;
 
-      LLVM_DEBUG(dbgs() << "Enqueue register"; MO.dump(); dbgs() << "\n";);
-      RegQueue.push(TypedVReg(MO.getReg()));
+  auto GetUniqueVRegName =
+      [&VRegNameCollisionMap](const NamedVReg &Reg) -> std::string {
+    auto It = VRegNameCollisionMap.find(Reg.getName());
+    unsigned Counter = 0;
+    if (It != VRegNameCollisionMap.end()) {
+      Counter = It->second;
     }
+    ++Counter;
+    VRegNameCollisionMap[Reg.getName()] = Counter;
+    return Reg.getName() + "__" + std::to_string(Counter);
+  };
+
+  for (auto &Vreg : VRegs) {
+    auto Reg = Vreg.getReg();
+    assert(Register::isVirtualRegister(Reg) &&
+           "Expecting Virtual Registers Only");
+    auto NewNameForReg = GetUniqueVRegName(Vreg);
+    auto Rename = createVirtualRegisterWithName(Reg, NewNameForReg);
+
+    VRegRenameMap.insert(std::pair<unsigned, unsigned>(Reg, Rename));
+  }
+  return VRegRenameMap;
+}
 
-    // Here we walk the root candidates. We start from the 0th operand because
-    // the root is normally a store to a vreg.
-    for (unsigned i = 0; i < candidate->getNumOperands(); i++) {
-
-      if (!candidate->mayStore() && !candidate->isBranch())
-        break;
-
-      MachineOperand &MO = candidate->getOperand(i);
-
-      // TODO: Do we want to only add vregs here?
-      if (!MO.isReg() && !MO.isFI())
-        continue;
-
-      LLVM_DEBUG(dbgs() << "Enqueue Reg/FI"; MO.dump(); dbgs() << "\n";);
-
-      RegQueue.push(MO.isReg() ? TypedVReg(MO.getReg())
-                               : TypedVReg(RSE_FrameIndex));
+std::string VRegRenamer::getInstructionOpcodeHash(MachineInstr &MI) {
+  std::string S;
+  raw_string_ostream OS(S);
+  auto HashOperand = [this](const MachineOperand &MO) -> unsigned {
+    if (MO.isImm())
+      return MO.getImm();
+    if (MO.isTargetIndex())
+      return MO.getOffset() | (MO.getTargetFlags() << 16);
+    if (MO.isReg()) {
+      return Register::isVirtualRegister(MO.getReg())
+                 ? MRI.getVRegDef(MO.getReg())->getOpcode()
+                 : (unsigned)MO.getReg();
     }
+    // We could explicitly handle all the types of the MachineOperand,
+    // here but we can just return a common number until we find a
+    // compelling test case where this is bad. The only side effect here
+    // is contributing to a hash collission but there's enough information
+    // (Opcodes,other registers etc) that this will likely not be a problem.
+    return 0;
+  };
+  SmallVector<unsigned, 16> MIOperands;
+  MIOperands.push_back(MI.getOpcode());
+  for (auto &Op : MI.uses()) {
+    MIOperands.push_back(HashOperand(Op));
+  }
+  auto HashMI = hash_combine_range(MIOperands.begin(), MIOperands.end());
+  return std::to_string(HashMI).substr(0, 5);
+}
+
+unsigned VRegRenamer::createVirtualRegister(unsigned VReg) {
+  return createVirtualRegisterWithName(
+      VReg, getInstructionOpcodeHash(*MRI.getVRegDef(VReg)));
+}
 
-    doCandidateWalk(VRegs, RegQueue, VisitedMIs, MBB);
+bool VRegRenamer::renameInstsInMBB(MachineBasicBlock *MBB) {
+  std::vector<NamedVReg> VRegs;
+  std::string Prefix = "bb" + std::to_string(getCurrentBBNumber()) + "_";
+  for (auto &MII : *MBB) {
+    MachineInstr &Candidate = MII;
+    // Don't rename stores/branches.
+    if (Candidate.mayStore() || Candidate.isBranch())
+      continue;
+    if (!Candidate.getNumOperands())
+      continue;
+    // Look for instructions that define VRegs in operand 0.
+    MachineOperand &MO = Candidate.getOperand(0);
+    // Avoid non regs, instructions defining physical regs.
+    if (!MO.isReg() || !Register::isVirtualRegister(MO.getReg()))
+      continue;
+    VRegs.push_back(
+        NamedVReg(MO.getReg(), Prefix + getInstructionOpcodeHash(Candidate)));
   }
 
   // If we have populated no vregs to rename then bail.
   // The rest of this function does the vreg remaping.
   if (VRegs.size() == 0)
-    return Changed;
+    return false;
 
-  auto VRegRenameMap = getVRegRenameMap(VRegs, renamedInOtherBB, MRI, NVC);
-  Changed |= doVRegRenaming(renamedInOtherBB, VRegRenameMap, MRI);
-  return Changed;
+  auto VRegRenameMap = getVRegRenameMap(VRegs);
+  return doVRegRenaming(VRegRenameMap);
 }
-} // anonymous namespace
-
-void NamedVRegCursor::skipVRegs() {
-  unsigned VRegGapIndex = 1;
-  if (!virtualVRegNumber) {
-    VRegGapIndex = 0;
-    virtualVRegNumber = MRI.createIncompleteVirtualRegister();
-  }
-  const unsigned VR_GAP = (++VRegGapIndex * SkipGapSize);
 
-  unsigned I = virtualVRegNumber;
-  const unsigned E = (((I + VR_GAP) / VR_GAP) + 1) * VR_GAP;
-
-  virtualVRegNumber = E;
+bool VRegRenamer::renameVRegs(MachineBasicBlock *MBB, unsigned BBNum) {
+  CurrentBBNumber = BBNum;
+  return renameInstsInMBB(MBB);
 }
 
-unsigned NamedVRegCursor::createVirtualRegister(unsigned VReg) {
-  if (!virtualVRegNumber)
-    skipVRegs();
-  std::string S;
-  raw_string_ostream OS(S);
-  OS << "namedVReg" << (virtualVRegNumber & ~0x80000000);
-  OS.flush();
-  virtualVRegNumber++;
+unsigned VRegRenamer::createVirtualRegisterWithName(unsigned VReg,
+                                                    const std::string &Name) {
+  std::string Temp(Name);
+  std::transform(Temp.begin(), Temp.end(), Temp.begin(), ::tolower);
   if (auto RC = MRI.getRegClassOrNull(VReg))
-    return MRI.createVirtualRegister(RC, OS.str());
-  return MRI.createGenericVirtualRegister(MRI.getType(VReg), OS.str());
-}
-
-bool NamedVRegCursor::renameVRegs(MachineBasicBlock *MBB) {
-  return ::renameVRegs(MBB, RenamedInOtherBB, *this);
+    return MRI.createVirtualRegister(RC, Temp);
+  return MRI.createGenericVirtualRegister(MRI.getType(VReg), Name);
 }
diff --git a/llvm/lib/CodeGen/MIRVRegNamerUtils.h b/llvm/lib/CodeGen/MIRVRegNamerUtils.h
index c5b52a96853..ebe309757f2 100644
--- a/llvm/lib/CodeGen/MIRVRegNamerUtils.h
+++ b/llvm/lib/CodeGen/MIRVRegNamerUtils.h
@@ -25,65 +25,68 @@
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/Support/raw_ostream.h"
 
-#include <queue>
 
 namespace llvm {
+/// VRegRenamer - This class is used for renaming vregs in a machine basic
+/// block according to semantics of the instruction.
+class VRegRenamer {
+  class NamedVReg {
+    Register Reg;
+    std::string Name;
 
-/// NamedVRegCursor - The cursor is an object that keeps track of what the next
-/// vreg name should be. It does book keeping to determine when to skip the
-/// index value and by how much, or if the next vreg name should be an increment
-/// from the previous.
-class NamedVRegCursor {
-  MachineRegisterInfo &MRI;
+  public:
+    NamedVReg(Register Reg, std::string Name = "") : Reg(Reg), Name(Name) {}
+    NamedVReg(std::string Name = "") : Reg(~0U), Name(Name) {}
 
-  /// virtualVRegNumber - Book keeping of the last vreg position.
-  unsigned virtualVRegNumber;
+    const std::string &getName() const { return Name; }
 
-  /// SkipGapSize - Used to calculate a modulo amount to skip by after every
-  /// sequence of instructions starting from a given side-effecting
-  /// MachineInstruction for a given MachineBasicBlock. The general idea is that
-  /// for a given program compiled with two different opt pipelines, there
-  /// shouldn't be greater than SkipGapSize difference in how many vregs are in
-  /// play between the two and for every def-use graph of vregs we rename we
-  /// will round up to the next SkipGapSize'th number so that we have a high
-  /// change of landing on the same name for two given matching side-effects
-  /// for the two compilation outcomes.
-  const unsigned SkipGapSize;
+    Register getReg() const { return Reg; }
+  };
 
-  /// RenamedInOtherBB - VRegs that we already renamed: ie breadcrumbs.
-  std::vector<Register> RenamedInOtherBB;
+  MachineRegisterInfo &MRI;
 
-public:
-  NamedVRegCursor() = delete;
-  /// 1000 for the SkipGapSize was a good heuristic at the time of the writing
-  /// of the MIRCanonicalizerPass. Adjust as needed.
-  NamedVRegCursor(MachineRegisterInfo &MRI, unsigned SkipGapSize = 1000)
-      : MRI(MRI), virtualVRegNumber(0), SkipGapSize(SkipGapSize) {}
+  unsigned CurrentBBNumber = 0;
 
-  /// SkipGapSize - Skips modulo a gap value of indices. Indices are used to
-  /// produce the next vreg name.
-  void skipVRegs();
+  /// Given an Instruction, construct a hash of the operands
+  /// of the instructions along with the opcode.
+  /// When dealing with virtual registers, just hash the opcode of
+  /// the instruction defining that vreg.
+  /// Handle immediates, registers (physical and virtual) explicitly,
+  /// and return a common value for the other cases.
+  /// Instruction will be named in the following scheme
+  /// bb<block_no>_hash_<collission_count>.
+  std::string getInstructionOpcodeHash(MachineInstr &MI);
 
-  unsigned getVirtualVReg() const { return virtualVRegNumber; }
+  /// For all the VRegs that are candidates for renaming,
+  /// return a mapping from old vregs to new vregs with names.
+  std::map<unsigned, unsigned>
+  getVRegRenameMap(const std::vector<NamedVReg> &VRegs);
 
-  /// incrementVirtualVReg - This increments an index value that us used to
-  /// create a new vreg name. This is not a Register.
-  unsigned incrementVirtualVReg(unsigned incr = 1) {
-    virtualVRegNumber += incr;
-    return virtualVRegNumber;
-  }
+  /// Perform replacing of registers based on the <old,new> vreg map.
+  bool doVRegRenaming(const std::map<unsigned, unsigned> &VRegRenameMap);
+
+public:
+  VRegRenamer() = delete;
+  VRegRenamer(MachineRegisterInfo &MRI) : MRI(MRI) {}
 
   /// createVirtualRegister - Given an existing vreg, create a named vreg to
-  /// take its place.
+  /// take its place. The name is determined by calling
+  /// getInstructionOpcodeHash.
   unsigned createVirtualRegister(unsigned VReg);
 
-  /// renameVRegs - For a given MachineBasicBlock, scan for side-effecting
-  /// instructions, walk the def-use from each side-effecting root (in sorted
-  /// root order) and rename the encountered vregs in the def-use graph in a
-  /// canonical ordering. This method maintains book keeping for which vregs
-  /// were already renamed in RenamedInOtherBB.
-  // @return changed
-  bool renameVRegs(MachineBasicBlock *MBB);
+  /// Create a vreg with name and return it.
+  unsigned createVirtualRegisterWithName(unsigned VReg,
+                                         const std::string &Name);
+  /// Linearly traverse the MachineBasicBlock and rename each instruction's
+  /// vreg definition based on the semantics of the instruction.
+  /// Names are as follows bb<BBNum>_hash_[0-9]+
+  bool renameInstsInMBB(MachineBasicBlock *MBB);
+
+  /// Same as the above, but sets a BBNum depending on BB traversal that
+  /// will be used as prefix for the vreg names.
+  bool renameVRegs(MachineBasicBlock *MBB, unsigned BBNum = 0);
+
+  unsigned getCurrentBBNumber() const { return CurrentBBNumber; }
 };
 
 } // namespace llvm