LLVM 20.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/Hashing.h"
18#include "llvm/ADT/STLExtras.h"
21#include "llvm/ADT/Statistic.h"
31#include "llvm/Config/llvm-config.h"
32#include "llvm/IR/Constants.h"
33#include "llvm/MC/MCSymbol.h"
36#include "llvm/Support/xxhash.h"
37
38#define DEBUG_TYPE "machine-stable-hash"
39
40using namespace llvm;
41
42STATISTIC(StableHashBailingMachineBasicBlock,
43 "Number of encountered unsupported MachineOperands that were "
44 "MachineBasicBlocks while computing stable hashes");
45STATISTIC(StableHashBailingConstantPoolIndex,
46 "Number of encountered unsupported MachineOperands that were "
47 "ConstantPoolIndex while computing stable hashes");
48STATISTIC(StableHashBailingTargetIndexNoName,
49 "Number of encountered unsupported MachineOperands that were "
50 "TargetIndex with no name");
51STATISTIC(StableHashBailingGlobalAddress,
52 "Number of encountered unsupported MachineOperands that were "
53 "GlobalAddress while computing stable hashes");
54STATISTIC(StableHashBailingBlockAddress,
55 "Number of encountered unsupported MachineOperands that were "
56 "BlockAddress while computing stable hashes");
57STATISTIC(StableHashBailingMetadataUnsupported,
58 "Number of encountered unsupported MachineOperands that were "
59 "Metadata of an unsupported kind while computing stable hashes");
60
62 switch (MO.getType()) {
64 if (MO.getReg().isVirtual()) {
66 SmallVector<unsigned> DefOpcodes;
67 for (auto &Def : MRI.def_instructions(MO.getReg()))
68 DefOpcodes.push_back(Def.getOpcode());
69 return hash_combine_range(DefOpcodes.begin(), DefOpcodes.end());
70 }
71
72 // Register operands don't have target flags.
73 return stable_hash_combine(MO.getType(), MO.getReg(), MO.getSubReg(),
74 MO.isDef());
76 return stable_hash_combine(MO.getType(), MO.getTargetFlags(), MO.getImm());
79 auto Val = MO.isCImm() ? MO.getCImm()->getValue()
81 auto ValHash =
82 stable_hash_combine_array(Val.getRawData(), Val.getNumWords());
83 return hash_combine(MO.getType(), MO.getTargetFlags(), ValHash);
84 }
85
87 StableHashBailingMachineBasicBlock++;
88 return 0;
90 StableHashBailingConstantPoolIndex++;
91 return 0;
93 StableHashBailingBlockAddress++;
94 return 0;
96 StableHashBailingMetadataUnsupported++;
97 return 0;
99 StableHashBailingGlobalAddress++;
100 return 0;
102 if (const char *Name = MO.getTargetIndexName())
104 xxh3_64bits(Name), MO.getOffset());
105 StableHashBailingTargetIndexNoName++;
106 return 0;
107 }
108
112 MO.getIndex());
113
115 return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getOffset(),
117
120 if (const MachineInstr *MI = MO.getParent()) {
121 if (const MachineBasicBlock *MBB = MI->getParent()) {
122 if (const MachineFunction *MF = MBB->getParent()) {
123 const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
124 unsigned RegMaskSize =
125 MachineOperand::getRegMaskSize(TRI->getNumRegs());
126 const uint32_t *RegMask = MO.getRegMask();
127 std::vector<llvm::stable_hash> RegMaskHashes(RegMask,
128 RegMask + RegMaskSize);
129 return hash_combine(MO.getType(), MO.getTargetFlags(),
130 stable_hash_combine_array(RegMaskHashes.data(),
131 RegMaskHashes.size()));
132 }
133 }
134 }
135
136 assert(0 && "MachineOperand not associated with any MachineFunction");
137 return hash_combine(MO.getType(), MO.getTargetFlags());
138 }
139
141 std::vector<llvm::stable_hash> ShuffleMaskHashes;
142
144 MO.getShuffleMask(), std::back_inserter(ShuffleMaskHashes),
145 [](int S) -> llvm::stable_hash { return llvm::stable_hash(S); });
146
147 return hash_combine(MO.getType(), MO.getTargetFlags(),
148 stable_hash_combine_array(ShuffleMaskHashes.data(),
149 ShuffleMaskHashes.size()));
150 }
152 auto SymbolName = MO.getMCSymbol()->getName();
153 return hash_combine(MO.getType(), MO.getTargetFlags(),
154 xxh3_64bits(SymbolName));
155 }
158 MO.getCFIIndex());
161 MO.getIntrinsicID());
164 MO.getPredicate());
167 MO.getInstrRefOpIndex());
168 }
169 llvm_unreachable("Invalid machine operand type");
170}
171
172/// A stable hash value for machine instructions.
173/// Returns 0 if no stable hash could be computed.
174/// The hashing and equality testing functions ignore definitions so this is
175/// useful for CSE, etc.
177 bool HashConstantPoolIndices,
178 bool HashMemOperands) {
179 // Build up a buffer of hash code components.
180 SmallVector<stable_hash, 16> HashComponents;
181 HashComponents.reserve(MI.getNumOperands() + MI.getNumMemOperands() + 2);
182 HashComponents.push_back(MI.getOpcode());
183 HashComponents.push_back(MI.getFlags());
184 for (const MachineOperand &MO : MI.operands()) {
185 if (!HashVRegs && MO.isReg() && MO.isDef() && MO.getReg().isVirtual())
186 continue; // Skip virtual register defs.
187
188 if (MO.isCPI()) {
189 HashComponents.push_back(stable_hash_combine(
190 MO.getType(), MO.getTargetFlags(), MO.getIndex()));
191 continue;
192 }
193
194 stable_hash StableHash = stableHashValue(MO);
195 if (!StableHash)
196 return 0;
197 HashComponents.push_back(StableHash);
198 }
199
200 for (const auto *Op : MI.memoperands()) {
201 if (!HashMemOperands)
202 break;
203 HashComponents.push_back(static_cast<unsigned>(Op->getSize().getValue()));
204 HashComponents.push_back(static_cast<unsigned>(Op->getFlags()));
205 HashComponents.push_back(static_cast<unsigned>(Op->getOffset()));
206 HashComponents.push_back(static_cast<unsigned>(Op->getSuccessOrdering()));
207 HashComponents.push_back(static_cast<unsigned>(Op->getAddrSpace()));
208 HashComponents.push_back(static_cast<unsigned>(Op->getSyncScopeID()));
209 HashComponents.push_back(static_cast<unsigned>(Op->getBaseAlign().value()));
210 HashComponents.push_back(static_cast<unsigned>(Op->getFailureOrdering()));
211 }
212
213 return stable_hash_combine_range(HashComponents.begin(),
214 HashComponents.end());
215}
216
218 SmallVector<stable_hash> HashComponents;
219 // TODO: Hash more stuff like block alignment and branch probabilities.
220 for (const auto &MI : MBB)
221 HashComponents.push_back(stableHashValue(MI));
222 return stable_hash_combine_range(HashComponents.begin(),
223 HashComponents.end());
224}
225
227 SmallVector<stable_hash> HashComponents;
228 // TODO: Hash lots more stuff like function alignment and stack objects.
229 for (const auto &MBB : MF)
230 HashComponents.push_back(stableHashValue(MBB));
231 return stable_hash_combine_range(HashComponents.begin(),
232 HashComponents.end());
233}
unsigned const MachineRegisterInfo * MRI
This file declares a class to represent arbitrary precision floating point values and provide a varie...
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock & MBB
This file contains the declarations for the subclasses of Constant, which represent the different fla...
std::string Name
IRTranslator LLVM IR MI
unsigned const TargetRegisterInfo * TRI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
APInt bitcastToAPInt() const
Definition: APFloat.h:1266
const APFloat & getValueAPF() const
Definition: Constants.h:312
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:146
This class represents an Operation in the Expression.
StringRef getName() const
getName - Get the symbol name.
Definition: MCSymbol.h:205
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Representation of each machine instruction.
Definition: MachineInstr.h:69
const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
MachineOperand class - Representation of each machine instruction operand.
unsigned getSubReg() const
unsigned getInstrRefOpIndex() const
const ConstantInt * getCImm() const
const char * getTargetIndexName() const
getTargetIndexName - If this MachineOperand is a TargetIndex that has a name, attempt to get the name...
bool isCImm() const
isCImm - Test if this is a MO_CImmediate operand.
int64_t getImm() const
unsigned getInstrRefInstrIndex() const
ArrayRef< int > getShuffleMask() const
unsigned getCFIIndex() const
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
static unsigned getRegMaskSize(unsigned NumRegs)
Returns number of elements needed for a regmask array.
unsigned getTargetFlags() const
MachineOperandType getType() const
getType - Returns the MachineOperandType for this operand.
const char * getSymbolName() const
Register getReg() const
getReg - Returns the register number.
Intrinsic::ID getIntrinsicID() const
const uint32_t * getRegMask() const
getRegMask - Returns a bit mask of registers preserved by this RegMask operand.
const ConstantFP * getFPImm() const
unsigned getPredicate() const
MCSymbol * getMCSymbol() const
@ MO_CFIIndex
MCCFIInstruction index.
@ MO_Immediate
Immediate operand.
@ MO_ConstantPoolIndex
Address of indexed Constant in Constant Pool.
@ MO_MCSymbol
MCSymbol reference (for debug/eh info)
@ MO_Predicate
Generic predicate for ISel.
@ MO_GlobalAddress
Address of a global value.
@ MO_RegisterMask
Mask of preserved registers.
@ MO_ShuffleMask
Other IR Constant for ISel (shuffle masks)
@ MO_CImmediate
Immediate >64bit operand.
@ MO_BlockAddress
Address of a basic block.
@ MO_DbgInstrRef
Integer indices referring to an instruction+operand.
@ MO_MachineBasicBlock
MachineBasicBlock reference.
@ MO_FrameIndex
Abstract Stack Frame Index.
@ MO_Register
Register operand.
@ MO_ExternalSymbol
Name of external global symbol.
@ MO_IntrinsicID
Intrinsic ID for ISel.
@ MO_JumpTableIndex
Address of indexed Jump Table for switch.
@ MO_TargetIndex
Target-dependent index+offset operand.
@ MO_Metadata
Metadata reference (for debug info)
@ MO_FPImmediate
Floating-point immediate operand.
@ MO_RegisterLiveOut
Mask of live-out registers.
int64_t getOffset() const
Return the offset from the symbol in this operand.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:91
void reserve(size_type N)
Definition: SmallVector.h:677
void push_back(const T &Elt)
Definition: SmallVector.h:427
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1210
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
uint64_t xxh3_64bits(ArrayRef< uint8_t > data)
Definition: xxhash.cpp:553
stable_hash stable_hash_combine_range(InputIteratorT First, InputIteratorT Last)
Compute a stable_hash for a sequence of values.
Definition: StableHashing.h:84
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:1928
stable_hash stable_hash_combine_array(const stable_hash *P, size_t C)
Definition: StableHashing.h:92
stable_hash stableHashValue(const MachineOperand &MO)
stable_hash stable_hash_combine(stable_hash A, stable_hash B)
Definition: StableHashing.h:51
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:593
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:471