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