llvm/lib/CodeGen/MachineStableHash.cpp

   1 //===- lib/CodeGen/MachineStableHash.cpp ----------------------------------===//
   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 // Stable hashing for MachineInstr and MachineOperand. Useful or getting a
  10 // hash across runs, modules, etc.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/CodeGen/MachineStableHash.h"
  15 #include "llvm/ADT/APFloat.h"
  16 #include "llvm/ADT/APInt.h"
  17 #include "llvm/ADT/Hashing.h"
  18 #include "llvm/ADT/STLExtras.h"
  19 #include "llvm/ADT/SmallVector.h"
  20 #include "llvm/ADT/StableHashing.h"
  21 #include "llvm/ADT/Statistic.h"
  22 #include "llvm/ADT/ilist_iterator.h"
  23 #include "llvm/CodeGen/MachineBasicBlock.h"
  24 #include "llvm/CodeGen/MachineFunction.h"
  25 #include "llvm/CodeGen/MachineInstr.h"
  26 #include "llvm/CodeGen/MachineInstrBundleIterator.h"
  27 #include "llvm/CodeGen/MachineMemOperand.h"
  28 #include "llvm/CodeGen/MachineOperand.h"
  29 #include "llvm/CodeGen/MachineRegisterInfo.h"
  30 #include "llvm/CodeGen/Register.h"
  31 #include "llvm/Config/llvm-config.h"
  32 #include "llvm/IR/Constants.h"
  33 #include "llvm/MC/MCSymbol.h"
  34 #include "llvm/Support/Alignment.h"
  35 #include "llvm/Support/ErrorHandling.h"
  36
  37 #define DEBUG_TYPE "machine-stable-hash"
  38
  39 using namespace llvm;
  40
  41 STATISTIC(StableHashBailingMachineBasicBlock,
  42           "Number of encountered unsupported MachineOperands that were "
  43           "MachineBasicBlocks while computing stable hashes");
  44 STATISTIC(StableHashBailingConstantPoolIndex,
  45           "Number of encountered unsupported MachineOperands that were "
  46           "ConstantPoolIndex while computing stable hashes");
  47 STATISTIC(StableHashBailingTargetIndexNoName,
  48           "Number of encountered unsupported MachineOperands that were "
  49           "TargetIndex with no name");
  50 STATISTIC(StableHashBailingGlobalAddress,
  51           "Number of encountered unsupported MachineOperands that were "
  52           "GlobalAddress while computing stable hashes");
  53 STATISTIC(StableHashBailingBlockAddress,
  54           "Number of encountered unsupported MachineOperands that were "
  55           "BlockAddress while computing stable hashes");
  56 STATISTIC(StableHashBailingMetadataUnsupported,
  57           "Number of encountered unsupported MachineOperands that were "
  58           "Metadata of an unsupported kind while computing stable hashes");
  59
  60 stable_hash llvm::stableHashValue(const MachineOperand &MO) {
  61   switch (MO.getType()) {
  62   case MachineOperand::MO_Register:
  63     if (MO.getReg().isVirtual()) {
  64       const MachineRegisterInfo &MRI = MO.getParent()->getMF()->getRegInfo();
  65       SmallVector<unsigned> DefOpcodes;
  66       for (auto &Def : MRI.def_instructions(MO.getReg()))
  67         DefOpcodes.push_back(Def.getOpcode());
  68       return hash_combine_range(DefOpcodes.begin(), DefOpcodes.end());
  69     }
  70
  71     // Register operands don't have target flags.
  72     return stable_hash_combine(MO.getType(), MO.getReg(), MO.getSubReg(),
  73                                MO.isDef());
  74   case MachineOperand::MO_Immediate:
  75     return stable_hash_combine(MO.getType(), MO.getTargetFlags(), MO.getImm());
  76   case MachineOperand::MO_CImmediate:
  77   case MachineOperand::MO_FPImmediate: {
  78     auto Val = MO.isCImm() ? MO.getCImm()->getValue()
  79                            : MO.getFPImm()->getValueAPF().bitcastToAPInt();
  80     auto ValHash =
  81         stable_hash_combine_array(Val.getRawData(), Val.getNumWords());
  82     return hash_combine(MO.getType(), MO.getTargetFlags(), ValHash);
  83   }
  84
  85   case MachineOperand::MO_MachineBasicBlock:
  86     StableHashBailingMachineBasicBlock++;
  87     return 0;
  88   case MachineOperand::MO_ConstantPoolIndex:
  89     StableHashBailingConstantPoolIndex++;
  90     return 0;
  91   case MachineOperand::MO_BlockAddress:
  92     StableHashBailingBlockAddress++;
  93     return 0;
  94   case MachineOperand::MO_Metadata:
  95     StableHashBailingMetadataUnsupported++;
  96     return 0;
  97   case MachineOperand::MO_GlobalAddress:
  98     StableHashBailingGlobalAddress++;
  99     return 0;
 100   case MachineOperand::MO_TargetIndex: {
 101     if (const char *Name = MO.getTargetIndexName())
 102       return stable_hash_combine(MO.getType(), MO.getTargetFlags(),
 103                                  stable_hash_combine_string(Name),
 104                                  MO.getOffset());
 105     StableHashBailingTargetIndexNoName++;
 106     return 0;
 107   }
 108
 109   case MachineOperand::MO_FrameIndex:
 110   case MachineOperand::MO_JumpTableIndex:
 111     return stable_hash_combine(MO.getType(), MO.getTargetFlags(),
 112                                MO.getIndex());
 113
 114   case MachineOperand::MO_ExternalSymbol:
 115     return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getOffset(),
 116                         stable_hash_combine_string(MO.getSymbolName()));
 117
 118   case MachineOperand::MO_RegisterMask:
 119   case MachineOperand::MO_RegisterLiveOut: {
 120     if (const MachineInstr *MI = MO.getParent()) {
 121       if (const MachineBasicBlock *MBB = MI->getParent()) {
 122         if (const MachineFunction *MF = MBB->getParent()) {
 123           const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
 124           unsigned RegMaskSize =
 125               MachineOperand::getRegMaskSize(TRI->getNumRegs());
 126           const uint32_t *RegMask = MO.getRegMask();
 127           std::vector<llvm::stable_hash> RegMaskHashes(RegMask,
 128                                                        RegMask + RegMaskSize);
 129           return hash_combine(MO.getType(), MO.getTargetFlags(),
 130                               stable_hash_combine_array(RegMaskHashes.data(),
 131                                                         RegMaskHashes.size()));
 132         }
 133       }
 134     }
 135
 136     assert(0 && "MachineOperand not associated with any MachineFunction");
 137     return hash_combine(MO.getType(), MO.getTargetFlags());
 138   }
 139
 140   case MachineOperand::MO_ShuffleMask: {
 141     std::vector<llvm::stable_hash> ShuffleMaskHashes;
 142
 143     llvm::transform(
 144         MO.getShuffleMask(), std::back_inserter(ShuffleMaskHashes),
 145         [](int S) -> llvm::stable_hash { return llvm::stable_hash(S); });
 146
 147     return hash_combine(MO.getType(), MO.getTargetFlags(),
 148                         stable_hash_combine_array(ShuffleMaskHashes.data(),
 149                                                   ShuffleMaskHashes.size()));
 150   }
 151   case MachineOperand::MO_MCSymbol: {
 152     auto SymbolName = MO.getMCSymbol()->getName();
 153     return hash_combine(MO.getType(), MO.getTargetFlags(),
 154                         stable_hash_combine_string(SymbolName));
 155   }
 156   case MachineOperand::MO_CFIIndex:
 157     return stable_hash_combine(MO.getType(), MO.getTargetFlags(),
 158                                MO.getCFIIndex());
 159   case MachineOperand::MO_IntrinsicID:
 160     return stable_hash_combine(MO.getType(), MO.getTargetFlags(),
 161                                MO.getIntrinsicID());
 162   case MachineOperand::MO_Predicate:
 163     return stable_hash_combine(MO.getType(), MO.getTargetFlags(),
 164                                MO.getPredicate());
 165   case MachineOperand::MO_DbgInstrRef:
 166     return stable_hash_combine(MO.getType(), MO.getInstrRefInstrIndex(),
 167                                MO.getInstrRefOpIndex());
 168   }
 169   llvm_unreachable("Invalid machine operand type");
 170 }
 171
 172 /// A stable hash value for machine instructions.
 173 /// Returns 0 if no stable hash could be computed.
 174 /// The hashing and equality testing functions ignore definitions so this is
 175 /// useful for CSE, etc.
 176 stable_hash llvm::stableHashValue(const MachineInstr &MI, bool HashVRegs,
 177                                   bool HashConstantPoolIndices,
 178                                   bool HashMemOperands) {
 179   // Build up a buffer of hash code components.
 180   SmallVector<stable_hash, 16> HashComponents;
 181   HashComponents.reserve(MI.getNumOperands() + MI.getNumMemOperands() + 2);
 182   HashComponents.push_back(MI.getOpcode());
 183   HashComponents.push_back(MI.getFlags());
 184   for (const MachineOperand &MO : MI.operands()) {
 185     if (!HashVRegs && MO.isReg() && MO.isDef() && MO.getReg().isVirtual())
 186       continue; // Skip virtual register defs.
 187
 188     if (MO.isCPI()) {
 189       HashComponents.push_back(stable_hash_combine(
 190           MO.getType(), MO.getTargetFlags(), MO.getIndex()));
 191       continue;
 192     }
 193
 194     stable_hash StableHash = stableHashValue(MO);
 195     if (!StableHash)
 196       return 0;
 197     HashComponents.push_back(StableHash);
 198   }
 199
 200   for (const auto *Op : MI.memoperands()) {
 201     if (!HashMemOperands)
 202       break;
 203     HashComponents.push_back(static_cast<unsigned>(Op->getSize()));
 204     HashComponents.push_back(static_cast<unsigned>(Op->getFlags()));
 205     HashComponents.push_back(static_cast<unsigned>(Op->getOffset()));
 206     HashComponents.push_back(static_cast<unsigned>(Op->getSuccessOrdering()));
 207     HashComponents.push_back(static_cast<unsigned>(Op->getAddrSpace()));
 208     HashComponents.push_back(static_cast<unsigned>(Op->getSyncScopeID()));
 209     HashComponents.push_back(static_cast<unsigned>(Op->getBaseAlign().value()));
 210     HashComponents.push_back(static_cast<unsigned>(Op->getFailureOrdering()));
 211   }
 212
 213   return stable_hash_combine_range(HashComponents.begin(),
 214                                    HashComponents.end());
 215 }
 216
 217 stable_hash llvm::stableHashValue(const MachineBasicBlock &MBB) {
 218   SmallVector<stable_hash> HashComponents;
 219   // TODO: Hash more stuff like block alignment and branch probabilities.
 220   for (const auto &MI : MBB)
 221     HashComponents.push_back(stableHashValue(MI));
 222   return stable_hash_combine_range(HashComponents.begin(),
 223                                    HashComponents.end());
 224 }
 225
 226 stable_hash llvm::stableHashValue(const MachineFunction &MF) {
 227   SmallVector<stable_hash> HashComponents;
 228   // TODO: Hash lots more stuff like function alignment and stack objects.
 229   for (const auto &MBB : MF)
 230     HashComponents.push_back(stableHashValue(MBB));
 231   return stable_hash_combine_range(HashComponents.begin(),
 232                                    HashComponents.end());
 233 }