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