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