1 //===- lib/CodeGen/MachineStableHash.cpp ----------------------------------===//
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
7 //===----------------------------------------------------------------------===//
9 // Stable hashing for MachineInstr and MachineOperand. Useful or getting a
10 // hash across runs, modules, etc.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/MachineStableHash.h"
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/StableHashing.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/ADT/ilist_iterator.h"
25 #include "llvm/CodeGen/MachineBasicBlock.h"
26 #include "llvm/CodeGen/MachineFunction.h"
27 #include "llvm/CodeGen/MachineInstr.h"
28 #include "llvm/CodeGen/MachineInstrBundleIterator.h"
29 #include "llvm/CodeGen/MachineMemOperand.h"
30 #include "llvm/CodeGen/MachineOperand.h"
31 #include "llvm/CodeGen/MachineRegisterInfo.h"
32 #include "llvm/CodeGen/Register.h"
33 #include "llvm/Config/llvm-config.h"
34 #include "llvm/IR/Constants.h"
35 #include "llvm/MC/MCSymbol.h"
36 #include "llvm/Support/Alignment.h"
37 #include "llvm/Support/ErrorHandling.h"
39 #define DEBUG_TYPE "machine-stable-hash"
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");
62 stable_hash
llvm::stableHashValue(const MachineOperand
&MO
) {
63 switch (MO
.getType()) {
64 case MachineOperand::MO_Register
:
65 if (MO
.getReg().isVirtual()) {
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());
73 // Register operands don't have target flags.
74 return stable_hash_combine(MO
.getType(), MO
.getReg(), MO
.getSubReg(),
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();
83 stable_hash_combine_array(Val
.getRawData(), Val
.getNumWords());
84 return hash_combine(MO
.getType(), MO
.getTargetFlags(), ValHash
);
87 case MachineOperand::MO_MachineBasicBlock
:
88 StableHashBailingMachineBasicBlock
++;
90 case MachineOperand::MO_ConstantPoolIndex
:
91 StableHashBailingConstantPoolIndex
++;
93 case MachineOperand::MO_BlockAddress
:
94 StableHashBailingBlockAddress
++;
96 case MachineOperand::MO_Metadata
:
97 StableHashBailingMetadataUnsupported
++;
99 case MachineOperand::MO_GlobalAddress
:
100 StableHashBailingGlobalAddress
++;
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
),
107 StableHashBailingTargetIndexNoName
++;
111 case MachineOperand::MO_FrameIndex
:
112 case MachineOperand::MO_JumpTableIndex
:
113 return stable_hash_combine(MO
.getType(), MO
.getTargetFlags(),
116 case MachineOperand::MO_ExternalSymbol
:
117 return hash_combine(MO
.getType(), MO
.getTargetFlags(), MO
.getOffset(),
118 stable_hash_combine_string(MO
.getSymbolName()));
120 case MachineOperand::MO_RegisterMask
:
121 case MachineOperand::MO_RegisterLiveOut
: {
122 if (const MachineInstr
*MI
= MO
.getParent()) {
123 if (const MachineBasicBlock
*MBB
= MI
->getParent()) {
124 if (const MachineFunction
*MF
= MBB
->getParent()) {
125 const TargetRegisterInfo
*TRI
= MF
->getSubtarget().getRegisterInfo();
126 unsigned RegMaskSize
=
127 MachineOperand::getRegMaskSize(TRI
->getNumRegs());
128 const uint32_t *RegMask
= MO
.getRegMask();
129 std::vector
<llvm::stable_hash
> RegMaskHashes(RegMask
,
130 RegMask
+ RegMaskSize
);
131 return hash_combine(MO
.getType(), MO
.getTargetFlags(),
132 stable_hash_combine_array(RegMaskHashes
.data(),
133 RegMaskHashes
.size()));
138 assert(0 && "MachineOperand not associated with any MachineFunction");
139 return hash_combine(MO
.getType(), MO
.getTargetFlags());
142 case MachineOperand::MO_ShuffleMask
: {
143 std::vector
<llvm::stable_hash
> ShuffleMaskHashes
;
146 MO
.getShuffleMask(), std::back_inserter(ShuffleMaskHashes
),
147 [](int S
) -> llvm::stable_hash
{ return llvm::stable_hash(S
); });
149 return hash_combine(MO
.getType(), MO
.getTargetFlags(),
150 stable_hash_combine_array(ShuffleMaskHashes
.data(),
151 ShuffleMaskHashes
.size()));
153 case MachineOperand::MO_MCSymbol
: {
154 auto SymbolName
= MO
.getMCSymbol()->getName();
155 return hash_combine(MO
.getType(), MO
.getTargetFlags(),
156 stable_hash_combine_string(SymbolName
));
158 case MachineOperand::MO_CFIIndex
:
159 return stable_hash_combine(MO
.getType(), MO
.getTargetFlags(),
161 case MachineOperand::MO_IntrinsicID
:
162 return stable_hash_combine(MO
.getType(), MO
.getTargetFlags(),
163 MO
.getIntrinsicID());
164 case MachineOperand::MO_Predicate
:
165 return stable_hash_combine(MO
.getType(), MO
.getTargetFlags(),
167 case MachineOperand::MO_DbgInstrRef
:
168 return stable_hash_combine(MO
.getType(), MO
.getInstrRefInstrIndex(),
169 MO
.getInstrRefOpIndex());
171 llvm_unreachable("Invalid machine operand type");
174 /// A stable hash value for machine instructions.
175 /// Returns 0 if no stable hash could be computed.
176 /// The hashing and equality testing functions ignore definitions so this is
177 /// useful for CSE, etc.
178 stable_hash
llvm::stableHashValue(const MachineInstr
&MI
, bool HashVRegs
,
179 bool HashConstantPoolIndices
,
180 bool HashMemOperands
) {
181 // Build up a buffer of hash code components.
182 SmallVector
<stable_hash
, 16> HashComponents
;
183 HashComponents
.reserve(MI
.getNumOperands() + MI
.getNumMemOperands() + 2);
184 HashComponents
.push_back(MI
.getOpcode());
185 HashComponents
.push_back(MI
.getFlags());
186 for (const MachineOperand
&MO
: MI
.operands()) {
187 if (!HashVRegs
&& MO
.isReg() && MO
.isDef() && MO
.getReg().isVirtual())
188 continue; // Skip virtual register defs.
191 HashComponents
.push_back(stable_hash_combine(
192 MO
.getType(), MO
.getTargetFlags(), MO
.getIndex()));
196 stable_hash StableHash
= stableHashValue(MO
);
199 HashComponents
.push_back(StableHash
);
202 for (const auto *Op
: MI
.memoperands()) {
203 if (!HashMemOperands
)
205 HashComponents
.push_back(static_cast<unsigned>(Op
->getSize()));
206 HashComponents
.push_back(static_cast<unsigned>(Op
->getFlags()));
207 HashComponents
.push_back(static_cast<unsigned>(Op
->getOffset()));
208 HashComponents
.push_back(static_cast<unsigned>(Op
->getSuccessOrdering()));
209 HashComponents
.push_back(static_cast<unsigned>(Op
->getAddrSpace()));
210 HashComponents
.push_back(static_cast<unsigned>(Op
->getSyncScopeID()));
211 HashComponents
.push_back(static_cast<unsigned>(Op
->getBaseAlign().value()));
212 HashComponents
.push_back(static_cast<unsigned>(Op
->getFailureOrdering()));
215 return stable_hash_combine_range(HashComponents
.begin(),
216 HashComponents
.end());
219 stable_hash
llvm::stableHashValue(const MachineBasicBlock
&MBB
) {
220 SmallVector
<stable_hash
> HashComponents
;
221 // TODO: Hash more stuff like block alignment and branch probabilities.
222 for (const auto &MI
: MBB
)
223 HashComponents
.push_back(stableHashValue(MI
));
224 return stable_hash_combine_range(HashComponents
.begin(),
225 HashComponents
.end());
228 stable_hash
llvm::stableHashValue(const MachineFunction
&MF
) {
229 SmallVector
<stable_hash
> HashComponents
;
230 // TODO: Hash lots more stuff like function alignment and stack objects.
231 for (const auto &MBB
: MF
)
232 HashComponents
.push_back(stableHashValue(MBB
));
233 return stable_hash_combine_range(HashComponents
.begin(),
234 HashComponents
.end());