1 //===---------- MIRVRegNamerUtils.cpp - MIR VReg Renaming Utilities -------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "MIRVRegNamerUtils.h"
10 #include "llvm/Support/Debug.h"
11 
12 using namespace llvm;
13 
14 #define DEBUG_TYPE "mir-vregnamer-utils"
15 
16 using VRegRenameMap = std::map<unsigned, unsigned>;
17 
18 bool VRegRenamer::doVRegRenaming(const VRegRenameMap &VRM) {
19   bool Changed = false;
20 
21   for (const auto &E : VRM) {
22     Changed = Changed || !MRI.reg_empty(E.first);
23     MRI.replaceRegWith(E.first, E.second);
24   }
25 
26   return Changed;
27 }
28 
29 VRegRenameMap
30 VRegRenamer::getVRegRenameMap(const std::vector<NamedVReg> &VRegs) {
31 
32   StringMap<unsigned> VRegNameCollisionMap;
33 
34   auto GetUniqueVRegName = [&VRegNameCollisionMap](const NamedVReg &Reg) {
35     if (VRegNameCollisionMap.find(Reg.getName()) == VRegNameCollisionMap.end())
36       VRegNameCollisionMap[Reg.getName()] = 0;
37     const unsigned Counter = ++VRegNameCollisionMap[Reg.getName()];
38     return Reg.getName() + "__" + std::to_string(Counter);
39   };
40 
41   VRegRenameMap VRM;
42   for (const auto &VReg : VRegs) {
43     const unsigned Reg = VReg.getReg();
44     VRM[Reg] = createVirtualRegisterWithLowerName(Reg, GetUniqueVRegName(VReg));
45   }
46   return VRM;
47 }
48 
49 std::string VRegRenamer::getInstructionOpcodeHash(MachineInstr &MI) {
50   std::string S;
51   raw_string_ostream OS(S);
52 
53   // Gets a hashable artifact from a given MachineOperand (ie an unsigned).
54   auto GetHashableMO = [this](const MachineOperand &MO) -> unsigned {
55     switch (MO.getType()) {
56     case MachineOperand::MO_Immediate:
57       return MO.getImm();
58     case MachineOperand::MO_TargetIndex:
59       return MO.getOffset() | (MO.getTargetFlags() << 16);
60     case MachineOperand::MO_Register:
61       if (Register::isVirtualRegister(MO.getReg()))
62         return MRI.getVRegDef(MO.getReg())->getOpcode();
63       return MO.getReg();
64 
65     // We could explicitly handle all the types of the MachineOperand,
66     // here but we can just return a common number until we find a
67     // compelling test case where this is bad. The only side effect here
68     // is contributing to a hash collision but there's enough information
69     // (Opcodes,other registers etc) that this will likely not be a problem.
70 
71     // TODO: Handle the following Immediate/Index/ID/Predicate cases. They can
72     // be hashed on in a stable manner.
73     case MachineOperand::MO_CImmediate:
74     case MachineOperand::MO_FPImmediate:
75     case MachineOperand::MO_FrameIndex:
76     case MachineOperand::MO_ConstantPoolIndex:
77     case MachineOperand::MO_JumpTableIndex:
78     case MachineOperand::MO_CFIIndex:
79     case MachineOperand::MO_IntrinsicID:
80     case MachineOperand::MO_Predicate:
81 
82     // In the cases below we havn't found a way to produce an artifact that will
83     // result in a stable hash, in most cases because they are pointers. We want
84     // stable hashes because we want the hash to be the same run to run.
85     case MachineOperand::MO_MachineBasicBlock:
86     case MachineOperand::MO_ExternalSymbol:
87     case MachineOperand::MO_GlobalAddress:
88     case MachineOperand::MO_BlockAddress:
89     case MachineOperand::MO_RegisterMask:
90     case MachineOperand::MO_RegisterLiveOut:
91     case MachineOperand::MO_Metadata:
92     case MachineOperand::MO_MCSymbol:
93     case MachineOperand::MO_ShuffleMask:
94       return 0;
95     }
96     llvm_unreachable("Unexpected MachineOperandType.");
97   };
98 
99   SmallVector<unsigned, 16> MIOperands = {MI.getOpcode(), MI.getFlags()};
100   llvm::transform(MI.uses(), std::back_inserter(MIOperands), GetHashableMO);
101 
102   for (const auto *Op : MI.memoperands()) {
103     MIOperands.push_back((unsigned)Op->getSize());
104     MIOperands.push_back((unsigned)Op->getFlags());
105     MIOperands.push_back((unsigned)Op->getOffset());
106     MIOperands.push_back((unsigned)Op->getOrdering());
107     MIOperands.push_back((unsigned)Op->getAddrSpace());
108     MIOperands.push_back((unsigned)Op->getSyncScopeID());
109     MIOperands.push_back((unsigned)Op->getBaseAlignment());
110     MIOperands.push_back((unsigned)Op->getFailureOrdering());
111   }
112 
113   auto HashMI = hash_combine_range(MIOperands.begin(), MIOperands.end());
114   return std::to_string(HashMI).substr(0, 5);
115 }
116 
117 unsigned VRegRenamer::createVirtualRegister(unsigned VReg) {
118   assert(Register::isVirtualRegister(VReg) && "Expected Virtual Registers");
119   std::string Name = getInstructionOpcodeHash(*MRI.getVRegDef(VReg));
120   return createVirtualRegisterWithLowerName(VReg, Name);
121 }
122 
123 bool VRegRenamer::renameInstsInMBB(MachineBasicBlock *MBB) {
124   std::vector<NamedVReg> VRegs;
125   std::string Prefix = "bb" + std::to_string(CurrentBBNumber) + "_";
126   for (MachineInstr &Candidate : *MBB) {
127     // Don't rename stores/branches.
128     if (Candidate.mayStore() || Candidate.isBranch())
129       continue;
130     if (!Candidate.getNumOperands())
131       continue;
132     // Look for instructions that define VRegs in operand 0.
133     MachineOperand &MO = Candidate.getOperand(0);
134     // Avoid non regs, instructions defining physical regs.
135     if (!MO.isReg() || !Register::isVirtualRegister(MO.getReg()))
136       continue;
137     VRegs.push_back(
138         NamedVReg(MO.getReg(), Prefix + getInstructionOpcodeHash(Candidate)));
139   }
140 
141   return VRegs.size() ? doVRegRenaming(getVRegRenameMap(VRegs)) : false;
142 }
143 
144 unsigned VRegRenamer::createVirtualRegisterWithLowerName(unsigned VReg,
145                                                          StringRef Name) {
146   std::string LowerName = Name.lower();
147   const TargetRegisterClass *RC = MRI.getRegClassOrNull(VReg);
148   return RC ? MRI.createVirtualRegister(RC, LowerName)
149             : MRI.createGenericVirtualRegister(MRI.getType(VReg), LowerName);
150 }
151