243 lines · 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-exception6//7//===----------------------------------------------------------------------===//8//9// Stable hashing for MachineInstr and MachineOperand. Useful or getting a10// 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 38using namespace llvm;39 40STATISTIC(StableHashBailingMachineBasicBlock,41 "Number of encountered unsupported MachineOperands that were "42 "MachineBasicBlocks while computing stable hashes");43STATISTIC(StableHashBailingConstantPoolIndex,44 "Number of encountered unsupported MachineOperands that were "45 "ConstantPoolIndex while computing stable hashes");46STATISTIC(StableHashBailingTargetIndexNoName,47 "Number of encountered unsupported MachineOperands that were "48 "TargetIndex with no name");49STATISTIC(StableHashBailingGlobalAddress,50 "Number of encountered unsupported MachineOperands that were "51 "GlobalAddress while computing stable hashes");52STATISTIC(StableHashBailingBlockAddress,53 "Number of encountered unsupported MachineOperands that were "54 "BlockAddress while computing stable hashes");55STATISTIC(StableHashBailingMetadataUnsupported,56 "Number of encountered unsupported MachineOperands that were "57 "Metadata of an unsupported kind while computing stable hashes");58 59stable_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().id(), 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 =140 MO.isRegMask() ? MO.getRegMask() : MO.getRegLiveOut();141 std::vector<llvm::stable_hash> RegMaskHashes(RegMask,142 RegMask + RegMaskSize);143 return stable_hash_combine(MO.getType(), MO.getTargetFlags(),144 stable_hash_combine(RegMaskHashes));145 }146 }147 }148 149 assert(0 && "MachineOperand not associated with any MachineFunction");150 return stable_hash_combine(MO.getType(), MO.getTargetFlags());151 }152 153 case MachineOperand::MO_ShuffleMask: {154 std::vector<llvm::stable_hash> ShuffleMaskHashes;155 156 llvm::transform(157 MO.getShuffleMask(), std::back_inserter(ShuffleMaskHashes),158 [](int S) -> llvm::stable_hash { return llvm::stable_hash(S); });159 160 return stable_hash_combine(MO.getType(), MO.getTargetFlags(),161 stable_hash_combine(ShuffleMaskHashes));162 }163 case MachineOperand::MO_MCSymbol: {164 auto SymbolName = MO.getMCSymbol()->getName();165 return stable_hash_combine(MO.getType(), MO.getTargetFlags(),166 stable_hash_name(SymbolName));167 }168 case MachineOperand::MO_CFIIndex:169 return stable_hash_combine(MO.getType(), MO.getTargetFlags(),170 MO.getCFIIndex());171 case MachineOperand::MO_IntrinsicID:172 return stable_hash_combine(MO.getType(), MO.getTargetFlags(),173 MO.getIntrinsicID());174 case MachineOperand::MO_Predicate:175 return stable_hash_combine(MO.getType(), MO.getTargetFlags(),176 MO.getPredicate());177 case MachineOperand::MO_DbgInstrRef:178 return stable_hash_combine(MO.getType(), MO.getInstrRefInstrIndex(),179 MO.getInstrRefOpIndex());180 }181 llvm_unreachable("Invalid machine operand type");182}183 184/// A stable hash value for machine instructions.185/// Returns 0 if no stable hash could be computed.186/// The hashing and equality testing functions ignore definitions so this is187/// useful for CSE, etc.188stable_hash llvm::stableHashValue(const MachineInstr &MI, bool HashVRegs,189 bool HashConstantPoolIndices,190 bool HashMemOperands) {191 // Build up a buffer of hash code components.192 SmallVector<stable_hash, 16> HashComponents;193 HashComponents.reserve(MI.getNumOperands() + MI.getNumMemOperands() + 2);194 HashComponents.push_back(MI.getOpcode());195 HashComponents.push_back(MI.getFlags());196 for (const MachineOperand &MO : MI.operands()) {197 if (!HashVRegs && MO.isReg() && MO.isDef() && MO.getReg().isVirtual())198 continue; // Skip virtual register defs.199 200 if (MO.isCPI()) {201 HashComponents.push_back(stable_hash_combine(202 MO.getType(), MO.getTargetFlags(), MO.getIndex()));203 continue;204 }205 206 stable_hash StableHash = stableHashValue(MO);207 if (!StableHash)208 return 0;209 HashComponents.push_back(StableHash);210 }211 212 for (const auto *Op : MI.memoperands()) {213 if (!HashMemOperands)214 break;215 HashComponents.push_back(static_cast<unsigned>(Op->getSize().getValue()));216 HashComponents.push_back(static_cast<unsigned>(Op->getFlags()));217 HashComponents.push_back(static_cast<unsigned>(Op->getOffset()));218 HashComponents.push_back(static_cast<unsigned>(Op->getSuccessOrdering()));219 HashComponents.push_back(static_cast<unsigned>(Op->getAddrSpace()));220 HashComponents.push_back(static_cast<unsigned>(Op->getSyncScopeID()));221 HashComponents.push_back(static_cast<unsigned>(Op->getBaseAlign().value()));222 HashComponents.push_back(static_cast<unsigned>(Op->getFailureOrdering()));223 }224 225 return stable_hash_combine(HashComponents);226}227 228stable_hash llvm::stableHashValue(const MachineBasicBlock &MBB) {229 SmallVector<stable_hash> HashComponents;230 // TODO: Hash more stuff like block alignment and branch probabilities.231 for (const auto &MI : MBB)232 HashComponents.push_back(stableHashValue(MI));233 return stable_hash_combine(HashComponents);234}235 236stable_hash llvm::stableHashValue(const MachineFunction &MF) {237 SmallVector<stable_hash> HashComponents;238 // TODO: Hash lots more stuff like function alignment and stack objects.239 for (const auto &MBB : MF)240 HashComponents.push_back(stableHashValue(MBB));241 return stable_hash_combine(HashComponents);242}243