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/CodeGen/MachineRegisterInfo.h"
11 #include "llvm/CodeGen/MachineStableHash.h"
12 #include "llvm/IR/Constants.h"
13 
14 using namespace llvm;
15 
16 #define DEBUG_TYPE "mir-vregnamer-utils"
17 
18 static cl::opt<bool>
19     UseStableNamerHash("mir-vreg-namer-use-stable-hash", cl::init(false),
20                        cl::Hidden,
21                        cl::desc("Use Stable Hashing for MIR VReg Renaming"));
22 
23 using VRegRenameMap = std::map<unsigned, unsigned>;
24 
doVRegRenaming(const VRegRenameMap & VRM)25 bool VRegRenamer::doVRegRenaming(const VRegRenameMap &VRM) {
26   bool Changed = false;
27 
28   for (const auto &E : VRM) {
29     Changed = Changed || !MRI.reg_empty(E.first);
30     MRI.replaceRegWith(E.first, E.second);
31   }
32 
33   return Changed;
34 }
35 
36 VRegRenameMap
getVRegRenameMap(const std::vector<NamedVReg> & VRegs)37 VRegRenamer::getVRegRenameMap(const std::vector<NamedVReg> &VRegs) {
38 
39   StringMap<unsigned> VRegNameCollisionMap;
40 
41   auto GetUniqueVRegName = [&VRegNameCollisionMap](const NamedVReg &Reg) {
42     if (!VRegNameCollisionMap.contains(Reg.getName()))
43       VRegNameCollisionMap[Reg.getName()] = 0;
44     const unsigned Counter = ++VRegNameCollisionMap[Reg.getName()];
45     return Reg.getName() + "__" + std::to_string(Counter);
46   };
47 
48   VRegRenameMap VRM;
49   for (const auto &VReg : VRegs) {
50     const unsigned Reg = VReg.getReg();
51     VRM[Reg] = createVirtualRegisterWithLowerName(Reg, GetUniqueVRegName(VReg));
52   }
53   return VRM;
54 }
55 
getInstructionOpcodeHash(MachineInstr & MI)56 std::string VRegRenamer::getInstructionOpcodeHash(MachineInstr &MI) {
57   std::string S;
58   raw_string_ostream OS(S);
59 
60   if (UseStableNamerHash) {
61     auto Hash = stableHashValue(MI, /* HashVRegs */ true,
62                                 /* HashConstantPoolIndices */ true,
63                                 /* HashMemOperands */ true);
64     assert(Hash && "Expected non-zero Hash");
65     OS << format_hex_no_prefix(Hash, 16, true);
66     return OS.str();
67   }
68 
69   // Gets a hashable artifact from a given MachineOperand (ie an unsigned).
70   auto GetHashableMO = [this](const MachineOperand &MO) -> unsigned {
71     switch (MO.getType()) {
72     case MachineOperand::MO_CImmediate:
73       return hash_combine(MO.getType(), MO.getTargetFlags(),
74                           MO.getCImm()->getZExtValue());
75     case MachineOperand::MO_FPImmediate:
76       return hash_combine(
77           MO.getType(), MO.getTargetFlags(),
78           MO.getFPImm()->getValueAPF().bitcastToAPInt().getZExtValue());
79     case MachineOperand::MO_Register:
80       if (MO.getReg().isVirtual())
81         return MRI.getVRegDef(MO.getReg())->getOpcode();
82       return MO.getReg();
83     case MachineOperand::MO_Immediate:
84       return MO.getImm();
85     case MachineOperand::MO_TargetIndex:
86       return MO.getOffset() | (MO.getTargetFlags() << 16);
87     case MachineOperand::MO_FrameIndex:
88     case MachineOperand::MO_ConstantPoolIndex:
89     case MachineOperand::MO_JumpTableIndex:
90       return llvm::hash_value(MO);
91 
92     // We could explicitly handle all the types of the MachineOperand,
93     // here but we can just return a common number until we find a
94     // compelling test case where this is bad. The only side effect here
95     // is contributing to a hash collision but there's enough information
96     // (Opcodes,other registers etc) that this will likely not be a problem.
97 
98     // TODO: Handle the following Index/ID/Predicate cases. They can
99     // be hashed on in a stable manner.
100     case MachineOperand::MO_CFIIndex:
101     case MachineOperand::MO_IntrinsicID:
102     case MachineOperand::MO_Predicate:
103 
104     // In the cases below we havn't found a way to produce an artifact that will
105     // result in a stable hash, in most cases because they are pointers. We want
106     // stable hashes because we want the hash to be the same run to run.
107     case MachineOperand::MO_MachineBasicBlock:
108     case MachineOperand::MO_ExternalSymbol:
109     case MachineOperand::MO_GlobalAddress:
110     case MachineOperand::MO_BlockAddress:
111     case MachineOperand::MO_RegisterMask:
112     case MachineOperand::MO_RegisterLiveOut:
113     case MachineOperand::MO_Metadata:
114     case MachineOperand::MO_MCSymbol:
115     case MachineOperand::MO_ShuffleMask:
116     case MachineOperand::MO_DbgInstrRef:
117       return 0;
118     }
119     llvm_unreachable("Unexpected MachineOperandType.");
120   };
121 
122   SmallVector<unsigned, 16> MIOperands = {MI.getOpcode(), MI.getFlags()};
123   llvm::transform(MI.uses(), std::back_inserter(MIOperands), GetHashableMO);
124 
125   for (const auto *Op : MI.memoperands()) {
126     MIOperands.push_back((unsigned)Op->getSize());
127     MIOperands.push_back((unsigned)Op->getFlags());
128     MIOperands.push_back((unsigned)Op->getOffset());
129     MIOperands.push_back((unsigned)Op->getSuccessOrdering());
130     MIOperands.push_back((unsigned)Op->getAddrSpace());
131     MIOperands.push_back((unsigned)Op->getSyncScopeID());
132     MIOperands.push_back((unsigned)Op->getBaseAlign().value());
133     MIOperands.push_back((unsigned)Op->getFailureOrdering());
134   }
135 
136   auto HashMI = hash_combine_range(MIOperands.begin(), MIOperands.end());
137   OS << format_hex_no_prefix(HashMI, 16, true);
138   return OS.str();
139 }
140 
createVirtualRegister(unsigned VReg)141 unsigned VRegRenamer::createVirtualRegister(unsigned VReg) {
142   assert(Register::isVirtualRegister(VReg) && "Expected Virtual Registers");
143   std::string Name = getInstructionOpcodeHash(*MRI.getVRegDef(VReg));
144   return createVirtualRegisterWithLowerName(VReg, Name);
145 }
146 
renameInstsInMBB(MachineBasicBlock * MBB)147 bool VRegRenamer::renameInstsInMBB(MachineBasicBlock *MBB) {
148   std::vector<NamedVReg> VRegs;
149   std::string Prefix = "bb" + std::to_string(CurrentBBNumber) + "_";
150   for (MachineInstr &Candidate : *MBB) {
151     // Don't rename stores/branches.
152     if (Candidate.mayStore() || Candidate.isBranch())
153       continue;
154     if (!Candidate.getNumOperands())
155       continue;
156     // Look for instructions that define VRegs in operand 0.
157     MachineOperand &MO = Candidate.getOperand(0);
158     // Avoid non regs, instructions defining physical regs.
159     if (!MO.isReg() || !MO.getReg().isVirtual())
160       continue;
161     VRegs.push_back(
162         NamedVReg(MO.getReg(), Prefix + getInstructionOpcodeHash(Candidate)));
163   }
164 
165   return VRegs.size() ? doVRegRenaming(getVRegRenameMap(VRegs)) : false;
166 }
167 
createVirtualRegisterWithLowerName(unsigned VReg,StringRef Name)168 unsigned VRegRenamer::createVirtualRegisterWithLowerName(unsigned VReg,
169                                                          StringRef Name) {
170   std::string LowerName = Name.lower();
171   const TargetRegisterClass *RC = MRI.getRegClassOrNull(VReg);
172   return RC ? MRI.createVirtualRegister(RC, LowerName)
173             : MRI.createGenericVirtualRegister(MRI.getType(VReg), LowerName);
174 }
175