LLVM 17.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"
19#include "llvm/ADT/Hashing.h"
20#include "llvm/ADT/STLExtras.h"
22#include "llvm/ADT/Statistic.h"
34#include "llvm/Config/llvm-config.h"
35#include "llvm/IR/Constants.h"
36#include "llvm/MC/MCSymbol.h"
39
40#define DEBUG_TYPE "machine-stable-hash"
41
42using namespace llvm;
43
44STATISTIC(StableHashBailingMachineBasicBlock,
45 "Number of encountered unsupported MachineOperands that were "
46 "MachineBasicBlocks while computing stable hashes");
47STATISTIC(StableHashBailingConstantPoolIndex,
48 "Number of encountered unsupported MachineOperands that were "
49 "ConstantPoolIndex while computing stable hashes");
50STATISTIC(StableHashBailingTargetIndexNoName,
51 "Number of encountered unsupported MachineOperands that were "
52 "TargetIndex with no name");
53STATISTIC(StableHashBailingGlobalAddress,
54 "Number of encountered unsupported MachineOperands that were "
55 "GlobalAddress while computing stable hashes");
56STATISTIC(StableHashBailingBlockAddress,
57 "Number of encountered unsupported MachineOperands that were "
58 "BlockAddress while computing stable hashes");
59STATISTIC(StableHashBailingMetadataUnsupported,
60 "Number of encountered unsupported MachineOperands that were "
61 "Metadata of an unsupported kind while computing stable hashes");
62
64 switch (MO.getType()) {
66 if (MO.getReg().isVirtual()) {
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())
107 MO.getOffset());
108 StableHashBailingTargetIndexNoName++;
109 return 0;
110 }
111
115 MO.getIndex());
116
118 return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getOffset(),
120
123 if (const MachineInstr *MI = MO.getParent()) {
124 if (const MachineBasicBlock *MBB = MI->getParent()) {
125 if (const MachineFunction *MF = MBB->getParent()) {
126 const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
127 unsigned RegMaskSize =
128 MachineOperand::getRegMaskSize(TRI->getNumRegs());
129 const uint32_t *RegMask = MO.getRegMask();
130 std::vector<llvm::stable_hash> RegMaskHashes(RegMask,
131 RegMask + RegMaskSize);
132 return hash_combine(MO.getType(), MO.getTargetFlags(),
133 stable_hash_combine_array(RegMaskHashes.data(),
134 RegMaskHashes.size()));
135 }
136 }
137 }
138
139 assert(0 && "MachineOperand not associated with any MachineFunction");
140 return hash_combine(MO.getType(), MO.getTargetFlags());
141 }
142
144 std::vector<llvm::stable_hash> ShuffleMaskHashes;
145
147 MO.getShuffleMask(), std::back_inserter(ShuffleMaskHashes),
148 [](int S) -> llvm::stable_hash { return llvm::stable_hash(S); });
149
150 return hash_combine(MO.getType(), MO.getTargetFlags(),
151 stable_hash_combine_array(ShuffleMaskHashes.data(),
152 ShuffleMaskHashes.size()));
153 }
155 auto SymbolName = MO.getMCSymbol()->getName();
156 return hash_combine(MO.getType(), MO.getTargetFlags(),
157 stable_hash_combine_string(SymbolName));
158 }
161 MO.getCFIIndex());
164 MO.getIntrinsicID());
167 MO.getPredicate());
170 MO.getInstrRefOpIndex());
171 }
172 llvm_unreachable("Invalid machine operand type");
173}
174
175/// A stable hash value for machine instructions.
176/// Returns 0 if no stable hash could be computed.
177/// The hashing and equality testing functions ignore definitions so this is
178/// useful for CSE, etc.
180 bool HashConstantPoolIndices,
181 bool HashMemOperands) {
182 // Build up a buffer of hash code components.
183 SmallVector<stable_hash, 16> HashComponents;
184 HashComponents.reserve(MI.getNumOperands() + MI.getNumMemOperands() + 2);
185 HashComponents.push_back(MI.getOpcode());
186 HashComponents.push_back(MI.getFlags());
187 for (const MachineOperand &MO : MI.operands()) {
188 if (!HashVRegs && MO.isReg() && MO.isDef() && MO.getReg().isVirtual())
189 continue; // Skip virtual register defs.
190
191 if (MO.isCPI()) {
192 HashComponents.push_back(stable_hash_combine(
193 MO.getType(), MO.getTargetFlags(), MO.getIndex()));
194 continue;
195 }
196
197 stable_hash StableHash = stableHashValue(MO);
198 if (!StableHash)
199 return 0;
200 HashComponents.push_back(StableHash);
201 }
202
203 for (const auto *Op : MI.memoperands()) {
204 if (!HashMemOperands)
205 break;
206 HashComponents.push_back(static_cast<unsigned>(Op->getSize()));
207 HashComponents.push_back(static_cast<unsigned>(Op->getFlags()));
208 HashComponents.push_back(static_cast<unsigned>(Op->getOffset()));
209 HashComponents.push_back(static_cast<unsigned>(Op->getSuccessOrdering()));
210 HashComponents.push_back(static_cast<unsigned>(Op->getAddrSpace()));
211 HashComponents.push_back(static_cast<unsigned>(Op->getSyncScopeID()));
212 HashComponents.push_back(static_cast<unsigned>(Op->getBaseAlign().value()));
213 HashComponents.push_back(static_cast<unsigned>(Op->getFailureOrdering()));
214 }
215
216 return stable_hash_combine_range(HashComponents.begin(),
217 HashComponents.end());
218}
219
221 SmallVector<stable_hash> HashComponents;
222 // TODO: Hash more stuff like block alignment and branch probabilities.
223 for (const auto &MI : MBB)
224 HashComponents.push_back(stableHashValue(MI));
225 return stable_hash_combine_range(HashComponents.begin(),
226 HashComponents.end());
227}
228
230 SmallVector<stable_hash> HashComponents;
231 // TODO: Hash lots more stuff like function alignment and stack objects.
232 for (const auto &MBB : MF)
233 HashComponents.push_back(stableHashValue(MBB));
234 return stable_hash_combine_range(HashComponents.begin(),
235 HashComponents.end());
236}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
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...
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file defines DenseMapInfo traits for DenseMap.
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:1184
const APFloat & getValueAPF() const
Definition: Constants.h:296
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:136
StringRef getName() const
getName - Get the symbol name.
Definition: MCSymbol.h:206
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:68
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:667
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
#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
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:2025
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
stable_hash stable_hash_combine_string(const StringRef &S)
Definition: StableHashing.h:99
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:613
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:491