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
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 bool SourceQualifyLocalGlobals) {
61 switch (MO.getType()) {
62 case MachineOperand::MO_Register:
63 if (MO.getReg().isVirtual()) {
64 const MachineRegisterInfo &MRI = MO.getParent()->getMF()->getRegInfo();
65 SmallVector<stable_hash> DefOpcodes;
66 for (auto &Def : MRI.def_instructions(Reg: MO.getReg()))
67 DefOpcodes.push_back(Elt: Def.getOpcode());
68 return stable_hash_combine(Buffer: DefOpcodes);
69 }
70
71 // Register operands don't have target flags.
72 return stable_hash_combine(A: MO.getType(), B: MO.getReg().id(), C: MO.getSubReg(),
73 D: MO.isDef());
74 case MachineOperand::MO_Immediate:
75 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(), C: MO.getImm());
76 case MachineOperand::MO_CImmediate:
77 case MachineOperand::MO_FPImmediate: {
78 auto Val = MO.isCImm() ? MO.getCImm()->getValue()
79 : MO.getFPImm()->getValueAPF().bitcastToAPInt();
80 auto ValHash = stable_hash_combine(
81 Buffer: ArrayRef<stable_hash>(Val.getRawData(), Val.getNumWords()));
82 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(), C: ValHash);
83 }
84
85 case MachineOperand::MO_MachineBasicBlock:
86 ++StableHashBailingMachineBasicBlock;
87 return 0;
88 case MachineOperand::MO_ConstantPoolIndex:
89 ++StableHashBailingConstantPoolIndex;
90 return 0;
91 case MachineOperand::MO_BlockAddress:
92 ++StableHashBailingBlockAddress;
93 return 0;
94 case MachineOperand::MO_Metadata:
95 ++StableHashBailingMetadataUnsupported;
96 return 0;
97 case MachineOperand::MO_GlobalAddress: {
98 const GlobalValue *GV = MO.getGlobal();
99 stable_hash GVHash = 0;
100 if (auto *GVar = dyn_cast<GlobalVariable>(Val: GV))
101 GVHash = StructuralHash(G: *GVar, SourceQualifyLocalGlobals);
102 if (!GVHash) {
103 if (!GV->hasName()) {
104 ++StableHashBailingGlobalAddress;
105 return 0;
106 }
107 GVHash = stable_hash_name(Name: GV->getName());
108 }
109
110 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(), C: GVHash,
111 D: MO.getOffset());
112 }
113
114 case MachineOperand::MO_TargetIndex: {
115 if (const char *Name = MO.getTargetIndexName())
116 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(),
117 C: stable_hash_name(Name), D: MO.getOffset());
118 ++StableHashBailingTargetIndexNoName;
119 return 0;
120 }
121
122 case MachineOperand::MO_FrameIndex:
123 case MachineOperand::MO_JumpTableIndex:
124 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(),
125 C: MO.getIndex());
126
127 case MachineOperand::MO_ExternalSymbol:
128 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(),
129 C: MO.getOffset(),
130 D: stable_hash_name(Name: MO.getSymbolName()));
131
132 case MachineOperand::MO_RegisterMask:
133 case MachineOperand::MO_RegisterLiveOut: {
134 if (const MachineInstr *MI = MO.getParent()) {
135 if (const MachineBasicBlock *MBB = MI->getParent()) {
136 if (const MachineFunction *MF = MBB->getParent()) {
137 const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
138 unsigned RegMaskSize =
139 MachineOperand::getRegMaskSize(NumRegs: TRI->getNumRegs());
140 const uint32_t *RegMask =
141 MO.isRegMask() ? MO.getRegMask() : MO.getRegLiveOut();
142 std::vector<llvm::stable_hash> RegMaskHashes(RegMask,
143 RegMask + RegMaskSize);
144 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(),
145 C: stable_hash_combine(Buffer: RegMaskHashes));
146 }
147 }
148 }
149
150 assert(0 && "MachineOperand not associated with any MachineFunction");
151 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags());
152 }
153
154 case MachineOperand::MO_ShuffleMask: {
155 std::vector<llvm::stable_hash> ShuffleMaskHashes;
156
157 llvm::transform(
158 Range: MO.getShuffleMask(), d_first: std::back_inserter(x&: ShuffleMaskHashes),
159 F: [](int S) -> llvm::stable_hash { return llvm::stable_hash(S); });
160
161 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(),
162 C: stable_hash_combine(Buffer: ShuffleMaskHashes));
163 }
164 case MachineOperand::MO_MCSymbol: {
165 auto SymbolName = MO.getMCSymbol()->getName();
166 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(),
167 C: stable_hash_name(Name: SymbolName));
168 }
169 case MachineOperand::MO_LaneMask: {
170 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(),
171 C: MO.getLaneMask().getAsInteger());
172 }
173 case MachineOperand::MO_CFIIndex:
174 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(),
175 C: MO.getCFIIndex());
176 case MachineOperand::MO_IntrinsicID:
177 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(),
178 C: MO.getIntrinsicID());
179 case MachineOperand::MO_Predicate:
180 return stable_hash_combine(A: MO.getType(), B: MO.getTargetFlags(),
181 C: MO.getPredicate());
182 case MachineOperand::MO_DbgInstrRef:
183 return stable_hash_combine(A: MO.getType(), B: MO.getInstrRefInstrIndex(),
184 C: MO.getInstrRefOpIndex());
185 }
186 llvm_unreachable("Invalid machine operand type");
187}
188
189/// A stable hash value for machine instructions.
190/// Returns 0 if no stable hash could be computed.
191/// The hashing and equality testing functions ignore definitions so this is
192/// useful for CSE, etc.
193stable_hash llvm::stableHashValue(const MachineInstr &MI, bool HashVRegs,
194 bool HashConstantPoolIndices,
195 bool HashMemOperands,
196 bool SourceQualifyLocalGlobals) {
197 // Build up a buffer of hash code components.
198 SmallVector<stable_hash, 16> HashComponents;
199 HashComponents.reserve(N: MI.getNumOperands() + MI.getNumMemOperands() + 2);
200 HashComponents.push_back(Elt: MI.getOpcode());
201 HashComponents.push_back(Elt: MI.getFlags());
202 for (const MachineOperand &MO : MI.operands()) {
203 if (!HashVRegs && MO.isReg() && MO.isDef() && MO.getReg().isVirtual())
204 continue; // Skip virtual register defs.
205
206 if (MO.isCPI()) {
207 HashComponents.push_back(Elt: stable_hash_combine(
208 A: MO.getType(), B: MO.getTargetFlags(), C: MO.getIndex()));
209 continue;
210 }
211
212 stable_hash StableHash = stableHashValue(MO, SourceQualifyLocalGlobals);
213 if (!StableHash)
214 return 0;
215 HashComponents.push_back(Elt: StableHash);
216 }
217
218 for (const auto *Op : MI.memoperands()) {
219 if (!HashMemOperands)
220 break;
221 HashComponents.push_back(Elt: static_cast<unsigned>(Op->getSize().getValue()));
222 HashComponents.push_back(Elt: static_cast<unsigned>(Op->getFlags()));
223 HashComponents.push_back(Elt: static_cast<unsigned>(Op->getOffset()));
224 HashComponents.push_back(Elt: static_cast<unsigned>(Op->getSuccessOrdering()));
225 HashComponents.push_back(Elt: static_cast<unsigned>(Op->getAddrSpace()));
226 HashComponents.push_back(Elt: static_cast<unsigned>(Op->getSyncScopeID()));
227 HashComponents.push_back(Elt: static_cast<unsigned>(Op->getBaseAlign().value()));
228 HashComponents.push_back(Elt: static_cast<unsigned>(Op->getFailureOrdering()));
229 }
230
231 return stable_hash_combine(Buffer: HashComponents);
232}
233
234stable_hash llvm::stableHashValue(const MachineBasicBlock &MBB) {
235 SmallVector<stable_hash> HashComponents;
236 // TODO: Hash more stuff like block alignment and branch probabilities.
237 for (const auto &MI : MBB)
238 HashComponents.push_back(Elt: stableHashValue(MI));
239 return stable_hash_combine(Buffer: HashComponents);
240}
241
242stable_hash llvm::stableHashValue(const MachineFunction &MF) {
243 SmallVector<stable_hash> HashComponents;
244 // TODO: Hash lots more stuff like function alignment and stack objects.
245 for (const auto &MBB : MF)
246 HashComponents.push_back(Elt: stableHashValue(MBB));
247 return stable_hash_combine(Buffer: HashComponents);
248}
249