llvm/lib/CodeGen/MIRVRegNamerUtils.cpp

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