[MIR-Renamer][WIP] opcode-chain based Canonical MIR VReg renaming.

[plotfi]

Summary

This patch is a first stab at renaming vregs not by an index increment but by the chain of encountered instruction opcodes in the defuse. Ideally something like:

%36:fpr64 = LDRDroX killed %30, %35, 0, 0
%38:gpr32common = ADDWri %32, 20, 0
%39:gpr64common = SMADDLrrr killed %38, %24, killed %37
STRDroX killed %36, killed %39, %35, 0, 0

Can be renamed to:

%STRDroXSBFMXr35:gpr64 = SBFMXri %STRDroXINSERT_SUBRE39, 61, 31
%STRDroXLDRDro33:fpr64 = LDRDroX %STRDroXLDRXu36, %STRDroXSBFMXr35, 0, 0
%STRDroXSMADDLrr34:gpr64common = SMADDLrrr %STRDroXADDWr37, %STURDiMOVi32im30, %STRDroXLDRXu38
STRDroX %STRDroXLDRDro33, %STRDroXSMADDLrr34, %BSTRDroXSBFMXr35, 0, 0

This is a rough work in progress. Only posting something this early without tests so that others can mess with it.

llvm/lib/CodeGen/MIRNamerPass.cpp

public:
   bool runOnMachineFunction(MachineFunction &MF) override {
     bool Changed = false;
 
     if (MF.empty())
       return Changed;
 
     NamedVRegCursor NVC(MF.getRegInfo());
 
+    unsigned BBNumber = 0;
     ReversePostOrderTraversal<MachineBasicBlock *> RPOT(&*MF.begin());
     for (auto &MBB : RPOT)
-      Changed |= NVC.renameVRegs(MBB);
+      Changed |= NVC.renameVRegs(MBB, BBNumber++);
 
     return Changed;
   }
 };
 
 } // end anonymous namespace
 
 char MIRNamer::ID;
 
 char &llvm::MIRNamerID = MIRNamer::ID;
 
 INITIALIZE_PASS_BEGIN(MIRNamer, "mir-namer", "Rename Register Operands", false,
                       false)
 
 INITIALIZE_PASS_END(MIRNamer, "mir-namer", "Rename Register Operands", false,
                     false)

llvm/lib/CodeGen/MIRVRegNamerUtils.h

class NamedVRegCursor {
   /// 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;
 
   /// RenamedInOtherBB - VRegs that we already renamed: ie breadcrumbs.
   std::vector<Register> RenamedInOtherBB;
 
+  unsigned CurrentBBNumber = 0;
+
 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) {}
 
   /// SkipGapSize - Skips modulo a gap value of indices. Indices are used to
   /// produce the next vreg name.
   void skipVRegs();
 
   unsigned getVirtualVReg() const { return virtualVRegNumber; }
 
   /// 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;
   }
 
   /// createVirtualRegister - Given an existing vreg, create a named vreg to
   /// take its place.
   unsigned createVirtualRegister(unsigned VReg);
 
+  unsigned createVirtualRegisterWithName(unsigned VReg,
+                                         const std::string &Name);
+
   /// 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);
+  bool renameVRegs(MachineBasicBlock *MBB, unsigned BBNum = 0);
+
+  unsigned getCurrentBBNumber() const { return CurrentBBNumber; }
 };
 
 } // namespace llvm
 
 #endif

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"
 #include "llvm/Support/Debug.h"
+#include <sstream>
 
 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;
+  std::string Token;
 
 public:
-  TypedVReg(Register Reg) : Type(RSE_Reg), Reg(Reg) {}
-  TypedVReg(VRType Type) : Type(Type), Reg(~0U) {
+  TypedVReg(Register Reg, std::string Token = "")
+      : Type(RSE_Reg), Reg(Reg), Token(Token) {}
+  TypedVReg(VRType Type, std::string Token = "")
+      : Type(Type), Reg(~0U), Token(Token) {
     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; }
+  const std::string &getToken() const { return Token; }
 
   VRType getType() const { return Type; }
   Register getReg() const {
     assert(this->isReg() && "Expected a virtual or physical Register.");
     return Reg;
   }
 };
 
for (auto II = MBB->begin(), IE = MBB->end(); II != IE; ++II) {
 
     LLVM_DEBUG(dbgs() << "Found Candidate:  "; MI->dump(););
     Candidates.push_back(MI);
   }
 
   return Candidates;
 }
 
+std::string getInstructionOpcodeStr(MachineInstr &I) {
+  std::string S;
+  raw_string_ostream OS(S);
+  I.print(OS);
+  OS.flush();
+
+  // Trim the assignment, or start from the begining in the case of a store.
+  size_t i = S.find("=");
+  if (i == std::string::npos) {
+    i = S.find(" ");
+    S = S.substr(0, i);
+    return S;
+  }
+  S = (i == std::string::npos) ? S : S.substr(i);
+  i = S.find(" ");
+  S = S.substr(i + 1);
+  i = S.find(" ");
+  S = S.substr(0, i - 1);
+  return S;
+}
+
 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));
+      VRegs.push_back(TypedVReg(RSE_FrameIndex, TReg.getToken()));
       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));
+
+        MachineInstr *Def = nullptr;
+        for (auto RI = MRI.def_begin(Reg), RE = MRI.def_end(); RI != RE; ++RI) {
+          Def = RI->getParent();
+          break;
+        }
+
+        VRegs.push_back(
+            TypedVReg(Reg, TReg.getToken() + getInstructionOpcodeStr(*Def)));
       }
     } else {
       LLVM_DEBUG(dbgs() << "Popping physreg.\n";);
-      VRegs.push_back(TypedVReg(Reg));
+      std::string S;
+      raw_string_ostream OS(S);
+      printReg(Reg, MRI.getTargetRegisterInfo()).Print(OS);
+      OS.flush();
+      llvm::errs() << "WTF2: " << OS.str() << "\n";
+      VRegs.push_back(TypedVReg(Reg, TReg.getToken() + S));
       continue;
     }
 
     for (auto RI = MRI.def_begin(Reg), RE = MRI.def_end(); RI != RE; ++RI) {
       MachineInstr *Def = RI->getParent();
 
       if (Def->getParent() != MBB)
         continue;
for (auto RI = MRI.def_begin(Reg), RE = MRI.def_end(); RI != RE; ++RI) {
         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));
+          RegQueue.push(TypedVReg(RSE_FrameIndex, TReg.getToken()));
         }
 
         if (!MO.isReg())
           continue;
-        RegQueue.push(TypedVReg(MO.getReg()));
+        RegQueue.push(TypedVReg(MO.getReg(), TReg.getToken()));
       }
     }
   }
 }
 
 std::map<unsigned, unsigned>
 getVRegRenameMap(const std::vector<TypedVReg> &VRegs,
                  const std::vector<Register> &renamedInOtherBB,
for (auto &vreg : VRegs) {
 
     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);
+    auto Rename = NVC.createVirtualRegisterWithName(Reg, vreg.getToken());
+    // 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;);
       }
bool renameVRegs(MachineBasicBlock *MBB,
   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::stringstream sstr;
+    sstr << "BB";
+    sstr << NVC.getCurrentBBNumber();
+    sstr << "_";
+    sstr << getInstructionOpcodeStr(*candidate);
+    std::string TokenPrefix = sstr.str();
+    VRegs.push_back(TypedVReg(RSE_NewCandidate, TokenPrefix));
 
     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;
 
       MachineOperand &MO = candidate->getOperand(i);
       if (!(MO.isReg() && Register::isVirtualRegister(MO.getReg())))
         continue;
 
       LLVM_DEBUG(dbgs() << "Enqueue register"; MO.dump(); dbgs() << "\n";);
-      RegQueue.push(TypedVReg(MO.getReg()));
+      RegQueue.push(TypedVReg(MO.getReg(), TokenPrefix));
     }
 
     // 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));
+      RegQueue.push(MO.isReg() ? TypedVReg(MO.getReg(), TokenPrefix)
+                               : TypedVReg(RSE_FrameIndex, TokenPrefix));
     }
 
     doCandidateWalk(VRegs, RegQueue, VisitedMIs, MBB);
   }
 
   // If we have populated no vregs to rename then bail.
   // The rest of this function does the vreg remaping.
   if (VRegs.size() == 0)
unsigned NamedVRegCursor::createVirtualRegister(unsigned VReg) {
   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());
 }
 
-bool NamedVRegCursor::renameVRegs(MachineBasicBlock *MBB) {
+unsigned
+NamedVRegCursor::createVirtualRegisterWithName(unsigned VReg,
+                                               const std::string &Name) {
+  static unsigned i = 0;
+  std::stringstream sstr;
+  sstr << tolower(Name.c_str());
+  sstr << i++;
+  llvm::errs() << "[" << sstr.str() << "]\n";
+  if (auto RC = MRI.getRegClassOrNull(VReg))
+    return MRI.createVirtualRegister(RC, sstr.str());
+  return MRI.createGenericVirtualRegister(MRI.getType(VReg), sstr.str());
+}
+
+bool NamedVRegCursor::renameVRegs(MachineBasicBlock *MBB, unsigned BBNum) {
+  CurrentBBNumber = BBNum;
   return ::renameVRegs(MBB, RenamedInOtherBB, *this);
 }