Home | History | Annotate | Line # | Download | only in CodeGen 
      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 #include "llvm/Support/Debug.h"
     14 
     15 using namespace llvm;
     16 
     17 #define DEBUG_TYPE "mir-vregnamer-utils"
     18 
     19 static cl::opt<bool>
     20     UseStableNamerHash("mir-vreg-namer-use-stable-hash", cl::init(false),
     21                        cl::Hidden,
     22                        cl::desc("Use Stable Hashing for MIR VReg Renaming"));
     23 
     24 using VRegRenameMap = std::map<unsigned, unsigned>;
     25 
     26 bool VRegRenamer::doVRegRenaming(const VRegRenameMap &VRM) {
     27   bool Changed = false;
     28 
     29   for (const auto &E : VRM) {
     30     Changed = Changed || !MRI.reg_empty(E.first);
     31     MRI.replaceRegWith(E.first, E.second);
     32   }
     33 
     34   return Changed;
     35 }
     36 
     37 VRegRenameMap
     38 VRegRenamer::getVRegRenameMap(const std::vector<NamedVReg> &VRegs) {
     39 
     40   StringMap<unsigned> VRegNameCollisionMap;
     41 
     42   auto GetUniqueVRegName = [&VRegNameCollisionMap](const NamedVReg &Reg) {
     43     if (VRegNameCollisionMap.find(Reg.getName()) == VRegNameCollisionMap.end())
     44       VRegNameCollisionMap[Reg.getName()] = 0;
     45     const unsigned Counter = ++VRegNameCollisionMap[Reg.getName()];
     46     return Reg.getName() + "__" + std::to_string(Counter);
     47   };
     48 
     49   VRegRenameMap VRM;
     50   for (const auto &VReg : VRegs) {
     51     const unsigned Reg = VReg.getReg();
     52     VRM[Reg] = createVirtualRegisterWithLowerName(Reg, GetUniqueVRegName(VReg));
     53   }
     54   return VRM;
     55 }
     56 
     57 std::string VRegRenamer::getInstructionOpcodeHash(MachineInstr &MI) {
     58   std::string S;
     59   raw_string_ostream OS(S);
     60 
     61   if (UseStableNamerHash) {
     62     auto Hash = stableHashValue(MI, /* HashVRegs */ true,
     63                                 /* HashConstantPoolIndices */ true,
     64                                 /* HashMemOperands */ true);
     65     assert(Hash && "Expected non-zero Hash");
     66     return std::to_string(Hash).substr(0, 5);
     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 (Register::isVirtualRegister(MO.getReg()))
     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       return 0;
    117     }
    118     llvm_unreachable("Unexpected MachineOperandType.");
    119   };
    120 
    121   SmallVector<unsigned, 16> MIOperands = {MI.getOpcode(), MI.getFlags()};
    122   llvm::transform(MI.uses(), std::back_inserter(MIOperands), GetHashableMO);
    123 
    124   for (const auto *Op : MI.memoperands()) {
    125     MIOperands.push_back((unsigned)Op->getSize());
    126     MIOperands.push_back((unsigned)Op->getFlags());
    127     MIOperands.push_back((unsigned)Op->getOffset());
    128     MIOperands.push_back((unsigned)Op->getOrdering());
    129     MIOperands.push_back((unsigned)Op->getAddrSpace());
    130     MIOperands.push_back((unsigned)Op->getSyncScopeID());
    131     MIOperands.push_back((unsigned)Op->getBaseAlign().value());
    132     MIOperands.push_back((unsigned)Op->getFailureOrdering());
    133   }
    134 
    135   auto HashMI = hash_combine_range(MIOperands.begin(), MIOperands.end());
    136   return std::to_string(HashMI).substr(0, 5);
    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() || !Register::isVirtualRegister(MO.getReg()))
    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 }
    173