LLVM  15.0.0git
MachineStableHash.cpp
Go to the documentation of this file.
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 
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"
32 #include "llvm/CodeGen/Register.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"
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 
64  switch (MO.getType()) {
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());
78  return stable_hash_combine(MO.getType(), MO.getTargetFlags(), MO.getImm());
81  auto Val = MO.isCImm() ? MO.getCImm()->getValue()
83  auto ValHash =
84  stable_hash_combine_array(Val.getRawData(), Val.getNumWords());
85  return hash_combine(MO.getType(), MO.getTargetFlags(), ValHash);
86  }
87 
89  StableHashBailingMachineBasicBlock++;
90  return 0;
92  StableHashBailingConstantPoolIndex++;
93  return 0;
95  StableHashBailingBlockAddress++;
96  return 0;
98  StableHashBailingMetadataUnsupported++;
99  return 0;
101  StableHashBailingGlobalAddress++;
102  return 0;
104  if (const char *Name = MO.getTargetIndexName())
105  return stable_hash_combine(MO.getType(), MO.getTargetFlags(),
107  MO.getOffset());
108  StableHashBailingTargetIndexNoName++;
109  return 0;
110  }
111 
114  return stable_hash_combine(MO.getType(), MO.getTargetFlags(),
115  MO.getIndex());
116 
118  return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getOffset(),
120 
123  return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getRegMask());
124 
126  std::vector<llvm::stable_hash> ShuffleMaskHashes;
127 
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  }
137  auto SymbolName = MO.getMCSymbol()->getName();
138  return hash_combine(MO.getType(), MO.getTargetFlags(),
140  }
142  return stable_hash_combine(MO.getType(), MO.getTargetFlags(),
143  MO.getCFIIndex());
145  return stable_hash_combine(MO.getType(), MO.getTargetFlags(),
146  MO.getIntrinsicID());
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.
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 
201  SmallVector<stable_hash> HashComponents;
202  // TODO: Hash more stuff like block alignment and branch probabilities.
203  for (auto &MI : MBB)
204  HashComponents.push_back(stableHashValue(MI));
205  return stable_hash_combine_range(HashComponents.begin(),
206  HashComponents.end());
207 }
208 
210  SmallVector<stable_hash> HashComponents;
211  // TODO: Hash lots more stuff like function alignment and stack objects.
212  for (auto &MBB : MF)
213  HashComponents.push_back(stableHashValue(MBB));
214  return stable_hash_combine_range(HashComponents.begin(),
215  HashComponents.end());
216 }
llvm::MachineOperand::MO_BlockAddress
@ MO_BlockAddress
Address of a basic block.
Definition: MachineOperand.h:62
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
llvm::stable_hash_combine_string
stable_hash stable_hash_combine_string(const StringRef &S)
Definition: StableHashing.h:99
MachineInstr.h
llvm::MachineOperand::MO_Immediate
@ MO_Immediate
Immediate operand.
Definition: MachineOperand.h:52
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::stable_hash_combine_range
stable_hash stable_hash_combine_range(InputIteratorT First, InputIteratorT Last)
Compute a stable_hash for a sequence of values.
Definition: StableHashing.h:84
llvm::stable_hash_combine
stable_hash stable_hash_combine(stable_hash A, stable_hash B)
Definition: StableHashing.h:51
llvm::MachineOperand::MO_ShuffleMask
@ MO_ShuffleMask
Other IR Constant for ISel (shuffle masks)
Definition: MachineOperand.h:70
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
llvm::MachineOperand::MO_RegisterLiveOut
@ MO_RegisterLiveOut
Mask of live-out registers.
Definition: MachineOperand.h:64
llvm::stable_hash_combine_array
stable_hash stable_hash_combine_array(const stable_hash *P, size_t C)
Definition: StableHashing.h:92
llvm::MachineOperand::getIntrinsicID
Intrinsic::ID getIntrinsicID() const
Definition: MachineOperand.h:592
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:133
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
Statistic.h
ErrorHandling.h
MachineBasicBlock.h
APInt.h
llvm::MachineOperand::MO_CFIIndex
@ MO_CFIIndex
MCCFIInstruction index.
Definition: MachineOperand.h:67
llvm::MachineOperand::getTargetIndexName
const char * getTargetIndexName() const
getTargetIndexName - If this MachineOperand is a TargetIndex that has a name, attempt to get the name...
Definition: MachineOperand.cpp:426
llvm::MachineOperand::isCImm
bool isCImm() const
isCImm - Test if this is a MO_CImmediate operand.
Definition: MachineOperand.h:324
llvm::MachineInstr::getMF
const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
Definition: MachineInstr.cpp:636
llvm::ConstantFP::getValueAPF
const APFloat & getValueAPF() const
Definition: Constants.h:297
Hashing.h
STLExtras.h
llvm::MachineOperand::getOffset
int64_t getOffset() const
Return the offset from the symbol in this operand.
Definition: MachineOperand.h:609
llvm::MachineOperand::getMCSymbol
MCSymbol * getMCSymbol() const
Definition: MachineOperand.h:582
llvm::MachineOperand::MO_Register
@ MO_Register
Register operand.
Definition: MachineOperand.h:51
MachineRegisterInfo.h
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:650
StableHashing.h
Constants.h
llvm::MachineOperand::MO_GlobalAddress
@ MO_GlobalAddress
Address of a global value.
Definition: MachineOperand.h:61
llvm::MachineOperand::getImm
int64_t getImm() const
Definition: MachineOperand.h:546
llvm::MachineOperand::getRegMask
const uint32_t * getRegMask() const
getRegMask - Returns a bit mask of registers preserved by this RegMask operand.
Definition: MachineOperand.h:639
llvm::MachineOperand::MO_FrameIndex
@ MO_FrameIndex
Abstract Stack Frame Index.
Definition: MachineOperand.h:56
MCSymbol.h
llvm::stableHashValue
stable_hash stableHashValue(const MachineOperand &MO)
Definition: MachineStableHash.cpp:63
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
APFloat.h
llvm::MCSymbol::getName
StringRef getName() const
getName - Get the symbol name.
Definition: MCSymbol.h:198
MachineStableHash.h
llvm::APFloat::bitcastToAPInt
APInt bitcastToAPInt() const
Definition: APFloat.h:1129
llvm::MachineOperand::getParent
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
Definition: MachineOperand.h:237
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::MachineOperand::MO_Metadata
@ MO_Metadata
Metadata reference (for debug info)
Definition: MachineOperand.h:65
llvm::MachineOperand::getTargetFlags
unsigned getTargetFlags() const
Definition: MachineOperand.h:220
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::MachineOperand::getCImm
const ConstantInt * getCImm() const
Definition: MachineOperand.h:551
uint64_t
llvm::MachineRegisterInfo::def_instructions
iterator_range< def_instr_iterator > def_instructions(Register Reg) const
Definition: MachineRegisterInfo.h:413
llvm::MachineOperand::MO_Predicate
@ MO_Predicate
Generic predicate for ISel.
Definition: MachineOperand.h:69
llvm::MachineOperand::MO_MCSymbol
@ MO_MCSymbol
MCSymbol reference (for debug/eh info)
Definition: MachineOperand.h:66
ArrayRef.h
llvm::MachineOperand::getType
MachineOperandType getType() const
getType - Returns the MachineOperandType for this operand.
Definition: MachineOperand.h:218
llvm::MachineOperand::getFPImm
const ConstantFP * getFPImm() const
Definition: MachineOperand.h:556
llvm::Register::isVirtualRegister
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:71
llvm::MachineOperand::getPredicate
unsigned getPredicate() const
Definition: MachineOperand.h:597
llvm::MachineOperand::getShuffleMask
ArrayRef< int > getShuffleMask() const
Definition: MachineOperand.h:602
llvm::MachineOperand::MO_TargetIndex
@ MO_TargetIndex
Target-dependent index+offset operand.
Definition: MachineOperand.h:58
iterator_range.h
llvm::MachineOperand::MO_FPImmediate
@ MO_FPImmediate
Floating-point immediate operand.
Definition: MachineOperand.h:54
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:359
llvm::MachineFunction
Definition: MachineFunction.h:241
llvm::MachineOperand::MO_JumpTableIndex
@ MO_JumpTableIndex
Address of indexed Jump Table for switch.
Definition: MachineOperand.h:59
llvm::MachineOperand::MO_CImmediate
@ MO_CImmediate
Immediate >64bit operand.
Definition: MachineOperand.h:53
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::transform
OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F)
Wrapper function around std::transform to apply a function to a range and store the result elsewhere.
Definition: STLExtras.h:1711
MachineInstrBundleIterator.h
llvm::MachineOperand::MO_MachineBasicBlock
@ MO_MachineBasicBlock
MachineBasicBlock reference.
Definition: MachineOperand.h:55
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:374
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::MachineOperand::MO_IntrinsicID
@ MO_IntrinsicID
Intrinsic ID for ISel.
Definition: MachineOperand.h:68
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::MachineOperand::getSubReg
unsigned getSubReg() const
Definition: MachineOperand.h:364
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::AMDGPU::HSAMD::Kernel::Key::SymbolName
constexpr char SymbolName[]
Key for Kernel::Metadata::mSymbolName.
Definition: AMDGPUMetadata.h:386
Alignment.h
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:50
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:341
llvm::MachineOperand::MO_ExternalSymbol
@ MO_ExternalSymbol
Name of external global symbol.
Definition: MachineOperand.h:60
llvm::MachineOperand::getIndex
int getIndex() const
Definition: MachineOperand.h:566
llvm::MachineOperand::getCFIIndex
unsigned getCFIIndex() const
Definition: MachineOperand.h:587
SmallVector.h
llvm::hash_combine
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:605
llvm::MachineOperand::getSymbolName
const char * getSymbolName() const
Definition: MachineOperand.h:617
llvm::hash_combine_range
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:483
MachineMemOperand.h
MachineOperand.h
DenseMapInfo.h
Register.h
llvm::MachineOperand::MO_RegisterMask
@ MO_RegisterMask
Mask of preserved registers.
Definition: MachineOperand.h:63
MachineFunction.h
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:644
ilist_iterator.h
llvm::MachineOperand::MO_ConstantPoolIndex
@ MO_ConstantPoolIndex
Address of indexed Constant in Constant Pool.
Definition: MachineOperand.h:57