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