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
14using namespace llvm;
15
16#define DEBUG_TYPE "mir-vregnamer-utils"
17
18using VRegRenameMap = std::map<unsigned, unsigned>;
19
20bool 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
31VRegRenameMap
32VRegRenamer::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
51std::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
125unsigned 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
131bool 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
152unsigned 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