1//===-- StructuralHash.cpp - IR Hashing -------------------------*- C++ -*-===//
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#include "llvm/IR/StructuralHash.h"
10#include "llvm/IR/Function.h"
11#include "llvm/IR/GlobalVariable.h"
12#include "llvm/IR/InstrTypes.h"
13#include "llvm/IR/Instructions.h"
14#include "llvm/IR/IntrinsicInst.h"
15#include "llvm/IR/Module.h"
16
17using namespace llvm;
18
19namespace {
20
21// Basic hashing mechanism to detect structural change to the IR, used to verify
22// pass return status consistency with actual change. In addition to being used
23// by the MergeFunctions pass.
24
25class StructuralHashImpl {
26 stable_hash Hash = 4;
27
28 bool DetailedHash;
29
30 // This random value acts as a block header, as otherwise the partition of
31 // opcodes into BBs wouldn't affect the hash, only the order of the opcodes.
32 static constexpr stable_hash BlockHeaderHash = 45798;
33 static constexpr stable_hash FunctionHeaderHash = 0x62642d6b6b2d6b72;
34 static constexpr stable_hash GlobalHeaderHash = 23456;
35
36 /// IgnoreOp is a function that returns true if the operand should be ignored.
37 IgnoreOperandFunc IgnoreOp = nullptr;
38 /// Whether name-based hashes of globals with local linkage are qualified
39 /// with the source file name of their module.
40 bool SourceQualifyLocalGlobals;
41 /// Lazily computed hash of the source file name. An instance only hashes
42 /// values from a single module, so one cached value suffices; 0 means the
43 /// source file name is empty and hashes are left unqualified.
44 std::optional<stable_hash> SourceNameHash;
45 /// A mapping from instruction indices to instruction pointers.
46 /// The index represents the position of an instruction based on the order in
47 /// which it is first encountered.
48 std::unique_ptr<IndexInstrMap> IndexInstruction = nullptr;
49 /// A mapping from pairs of instruction indices and operand indices
50 /// to the hashes of the operands.
51 std::unique_ptr<IndexOperandHashMapType> IndexOperandHashMap = nullptr;
52
53 /// Assign a unique ID to each Value in the order they are first seen.
54 DenseMap<const Value *, int> ValueToId;
55
56 static stable_hash hashType(Type *ValueType) {
57 SmallVector<stable_hash> Hashes;
58 Hashes.emplace_back(Args: ValueType->getTypeID());
59 if (ValueType->isIntegerTy())
60 Hashes.emplace_back(Args: ValueType->getIntegerBitWidth());
61 return stable_hash_combine(Buffer: Hashes);
62 }
63
64public:
65 StructuralHashImpl() = delete;
66 explicit StructuralHashImpl(bool DetailedHash,
67 IgnoreOperandFunc IgnoreOp = nullptr,
68 bool SourceQualifyLocalGlobals = false)
69 : DetailedHash(DetailedHash), IgnoreOp(IgnoreOp),
70 SourceQualifyLocalGlobals(SourceQualifyLocalGlobals) {
71 if (IgnoreOp) {
72 IndexInstruction = std::make_unique<IndexInstrMap>();
73 IndexOperandHashMap = std::make_unique<IndexOperandHashMapType>();
74 }
75 }
76
77 static stable_hash hashAPInt(const APInt &I) {
78 SmallVector<stable_hash> Hashes;
79 Hashes.emplace_back(Args: I.getBitWidth());
80 auto RawVals = ArrayRef<uint64_t>(I.getRawData(), I.getNumWords());
81 Hashes.append(in_start: RawVals.begin(), in_end: RawVals.end());
82 return stable_hash_combine(Buffer: Hashes);
83 }
84
85 static stable_hash hashAPFloat(const APFloat &F) {
86 return hashAPInt(I: F.bitcastToAPInt());
87 }
88
89 stable_hash hashGlobalName(const GlobalVariable &GVar) {
90 stable_hash GlobalHash = hashGlobalValue(GV: &GVar);
91 if (!GlobalHash || !SourceQualifyLocalGlobals || !GVar.hasLocalLinkage())
92 return GlobalHash;
93 if (!SourceNameHash) {
94 StringRef SourceName = GVar.getParent()->getSourceFileName();
95 SourceNameHash =
96 SourceName.empty() ? stable_hash(0) : stable_hash_name(Name: SourceName);
97 }
98 if (!*SourceNameHash)
99 return GlobalHash;
100 return stable_hash_combine(A: *SourceNameHash, B: GlobalHash);
101 }
102
103 stable_hash hashGlobalVariable(const GlobalVariable &GVar) {
104 if (!GVar.hasInitializer())
105 return hashGlobalName(GVar);
106
107 // Hash the contents of a string.
108 if (GVar.getName().starts_with(Prefix: ".str")) {
109 auto *C = GVar.getInitializer();
110 if (const auto *Seq = dyn_cast<ConstantDataSequential>(Val: C))
111 if (Seq->isString())
112 return stable_hash_name(Name: Seq->getAsString());
113 }
114
115 // Hash structural contents of Objective-C metadata in specific sections.
116 // This can be extended to other metadata if needed.
117 static constexpr const char *SectionNames[] = {
118 "__cfstring", "__cstring", "__objc_classrefs",
119 "__objc_methname", "__objc_selrefs",
120 };
121 if (GVar.hasSection()) {
122 StringRef SectionName = GVar.getSection();
123 for (const char *Name : SectionNames)
124 if (SectionName.contains(Other: Name))
125 return hashConstant(C: GVar.getInitializer());
126 }
127
128 return hashGlobalName(GVar);
129 }
130
131 static stable_hash hashGlobalValue(const GlobalValue *GV) {
132 if (!GV->hasName())
133 return 0;
134 return stable_hash_name(Name: GV->getName());
135 }
136
137 // Compute a hash for a Constant. This function is logically similar to
138 // FunctionComparator::cmpConstants() in FunctionComparator.cpp, but here
139 // we're interested in computing a hash rather than comparing two Constants.
140 // Some of the logic is simplified, e.g, we don't expand GEPOperator.
141 stable_hash hashConstant(const Constant *C) {
142 SmallVector<stable_hash> Hashes;
143
144 Type *Ty = C->getType();
145 Hashes.emplace_back(Args: hashType(ValueType: Ty));
146
147 if (C->isNullValue()) {
148 Hashes.emplace_back(Args: static_cast<stable_hash>('N'));
149 return stable_hash_combine(Buffer: Hashes);
150 }
151
152 if (auto *GVar = dyn_cast<GlobalVariable>(Val: C)) {
153 Hashes.emplace_back(Args: hashGlobalVariable(GVar: *GVar));
154 return stable_hash_combine(Buffer: Hashes);
155 }
156
157 if (auto *G = dyn_cast<GlobalValue>(Val: C)) {
158 Hashes.emplace_back(Args: hashGlobalValue(GV: G));
159 return stable_hash_combine(Buffer: Hashes);
160 }
161
162 if (const auto *Seq = dyn_cast<ConstantDataSequential>(Val: C)) {
163 if (Seq->isString()) {
164 Hashes.emplace_back(Args: stable_hash_name(Name: Seq->getAsString()));
165 return stable_hash_combine(Buffer: Hashes);
166 }
167 }
168
169 switch (C->getValueID()) {
170 case Value::ConstantIntVal: {
171 const APInt &Int = cast<ConstantInt>(Val: C)->getValue();
172 Hashes.emplace_back(Args: hashAPInt(I: Int));
173 return stable_hash_combine(Buffer: Hashes);
174 }
175 case Value::ConstantFPVal: {
176 const APFloat &APF = cast<ConstantFP>(Val: C)->getValueAPF();
177 Hashes.emplace_back(Args: hashAPFloat(F: APF));
178 return stable_hash_combine(Buffer: Hashes);
179 }
180 case Value::ConstantArrayVal:
181 case Value::ConstantStructVal:
182 case Value::ConstantVectorVal:
183 case Value::ConstantExprVal: {
184 for (const auto &Op : C->operands()) {
185 auto H = hashConstant(C: cast<Constant>(Val: Op));
186 Hashes.emplace_back(Args&: H);
187 }
188 return stable_hash_combine(Buffer: Hashes);
189 }
190 case Value::BlockAddressVal: {
191 const BlockAddress *BA = cast<BlockAddress>(Val: C);
192 auto H = hashGlobalValue(GV: BA->getFunction());
193 Hashes.emplace_back(Args&: H);
194 return stable_hash_combine(Buffer: Hashes);
195 }
196 case Value::DSOLocalEquivalentVal: {
197 const auto *Equiv = cast<DSOLocalEquivalent>(Val: C);
198 auto H = hashGlobalValue(GV: Equiv->getGlobalValue());
199 Hashes.emplace_back(Args&: H);
200 return stable_hash_combine(Buffer: Hashes);
201 }
202 default:
203 // Skip other types of constants for simplicity.
204 return stable_hash_combine(Buffer: Hashes);
205 }
206 }
207
208 stable_hash hashValue(Value *V) {
209 // Check constant and return its hash.
210 Constant *C = dyn_cast<Constant>(Val: V);
211 if (C)
212 return hashConstant(C);
213
214 // Hash argument number.
215 SmallVector<stable_hash> Hashes;
216 if (Argument *Arg = dyn_cast<Argument>(Val: V))
217 Hashes.emplace_back(Args: Arg->getArgNo());
218
219 // Get an index (an insertion order) for the non-constant value.
220 auto [It, WasInserted] = ValueToId.try_emplace(Key: V, Args: ValueToId.size());
221 Hashes.emplace_back(Args&: It->second);
222
223 return stable_hash_combine(Buffer: Hashes);
224 }
225
226 stable_hash hashOperand(Value *Operand) {
227 SmallVector<stable_hash> Hashes;
228 Hashes.emplace_back(Args: hashType(ValueType: Operand->getType()));
229 Hashes.emplace_back(Args: hashValue(V: Operand));
230 return stable_hash_combine(Buffer: Hashes);
231 }
232
233 stable_hash hashInstruction(const Instruction &Inst) {
234 SmallVector<stable_hash> Hashes;
235 Hashes.emplace_back(Args: Inst.getOpcode());
236
237 if (!DetailedHash)
238 return stable_hash_combine(Buffer: Hashes);
239
240 Hashes.emplace_back(Args: hashType(ValueType: Inst.getType()));
241
242 // Handle additional properties of specific instructions that cause
243 // semantic differences in the IR.
244 if (const auto *ComparisonInstruction = dyn_cast<CmpInst>(Val: &Inst))
245 Hashes.emplace_back(Args: ComparisonInstruction->getPredicate());
246
247 unsigned InstIdx = 0;
248 if (IndexInstruction) {
249 InstIdx = IndexInstruction->size();
250 IndexInstruction->try_emplace(Key: InstIdx, Args: const_cast<Instruction *>(&Inst));
251 }
252
253 for (const auto [OpndIdx, Op] : enumerate(First: Inst.operands())) {
254 auto OpndHash = hashOperand(Operand: Op);
255 if (IgnoreOp && IgnoreOp(&Inst, OpndIdx)) {
256 assert(IndexOperandHashMap);
257 IndexOperandHashMap->try_emplace(Key: {InstIdx, OpndIdx}, Args&: OpndHash);
258 } else
259 Hashes.emplace_back(Args&: OpndHash);
260 }
261
262 return stable_hash_combine(Buffer: Hashes);
263 }
264
265 // A function hash is calculated by considering only the number of arguments
266 // and whether a function is varargs, the order of basic blocks (given by the
267 // successors of each basic block in depth first order), and the order of
268 // opcodes of each instruction within each of these basic blocks. This mirrors
269 // the strategy FunctionComparator::compare() uses to compare functions by
270 // walking the BBs in depth first order and comparing each instruction in
271 // sequence. Because this hash currently does not look at the operands, it is
272 // insensitive to things such as the target of calls and the constants used in
273 // the function, which makes it useful when possibly merging functions which
274 // are the same modulo constants and call targets.
275 //
276 // Note that different users of StructuralHash will want different behavior
277 // out of it (i.e., MergeFunctions will want something different from PM
278 // expensive checks for pass modification status). When modifying this
279 // function, most changes should be gated behind an option and enabled
280 // selectively.
281 void update(const Function &F) {
282 // Declarations don't affect analyses.
283 if (F.isDeclaration())
284 return;
285
286 SmallVector<stable_hash> Hashes;
287 Hashes.emplace_back(Args&: Hash);
288 Hashes.emplace_back(Args: FunctionHeaderHash);
289
290 Hashes.emplace_back(Args: F.isVarArg());
291 Hashes.emplace_back(Args: F.arg_size());
292
293 SmallVector<const BasicBlock *, 8> BBs;
294 SmallPtrSet<const BasicBlock *, 16> VisitedBBs;
295
296 // Walk the blocks in the same order as
297 // FunctionComparator::cmpBasicBlocks(), accumulating the hash of the
298 // function "structure." (BB and opcode sequence)
299 BBs.push_back(Elt: &F.getEntryBlock());
300 VisitedBBs.insert(Ptr: BBs[0]);
301 while (!BBs.empty()) {
302 const BasicBlock *BB = BBs.pop_back_val();
303
304 Hashes.emplace_back(Args: BlockHeaderHash);
305 for (auto &Inst : *BB)
306 Hashes.emplace_back(Args: hashInstruction(Inst));
307
308 for (const BasicBlock *Succ : successors(BB))
309 if (VisitedBBs.insert(Ptr: Succ).second)
310 BBs.push_back(Elt: Succ);
311 }
312
313 // Update the combined hash in place.
314 Hash = stable_hash_combine(Buffer: Hashes);
315 }
316
317 void update(const GlobalVariable &GV) {
318 // Declarations and used/compiler.used don't affect analyses.
319 // Since there are several `llvm.*` metadata, like `llvm.embedded.object`,
320 // we ignore anything with the `.llvm` prefix
321 if (GV.isDeclaration() || GV.getName().starts_with(Prefix: "llvm."))
322 return;
323 SmallVector<stable_hash> Hashes;
324 Hashes.emplace_back(Args&: Hash);
325 Hashes.emplace_back(Args: GlobalHeaderHash);
326 Hashes.emplace_back(Args: GV.getValueType()->getTypeID());
327
328 // Update the combined hash in place.
329 Hash = stable_hash_combine(Buffer: Hashes);
330 }
331
332 void update(const Module &M) {
333 for (const GlobalVariable &GV : M.globals())
334 update(GV);
335 for (const Function &F : M)
336 update(F);
337 }
338
339 uint64_t getHash() const { return Hash; }
340
341 std::unique_ptr<IndexInstrMap> getIndexInstrMap() {
342 return std::move(IndexInstruction);
343 }
344
345 std::unique_ptr<IndexOperandHashMapType> getIndexPairOpndHashMap() {
346 return std::move(IndexOperandHashMap);
347 }
348};
349
350} // namespace
351
352stable_hash llvm::StructuralHash(const Function &F, bool DetailedHash) {
353 StructuralHashImpl H(DetailedHash);
354 H.update(F);
355 return H.getHash();
356}
357
358stable_hash llvm::StructuralHash(const GlobalVariable &GVar,
359 bool SourceQualifyLocalGlobals) {
360 StructuralHashImpl H(/*DetailedHash=*/false, /*IgnoreOp=*/nullptr,
361 SourceQualifyLocalGlobals);
362 return H.hashGlobalVariable(GVar);
363}
364
365stable_hash llvm::StructuralHash(const Module &M, bool DetailedHash) {
366 StructuralHashImpl H(DetailedHash);
367 H.update(M);
368 return H.getHash();
369}
370
371FunctionHashInfo
372llvm::StructuralHashWithDifferences(const Function &F,
373 IgnoreOperandFunc IgnoreOp,
374 bool SourceQualifyLocalGlobals) {
375 StructuralHashImpl H(/*DetailedHash=*/true, IgnoreOp,
376 SourceQualifyLocalGlobals);
377 H.update(F);
378 return FunctionHashInfo(H.getHash(), H.getIndexInstrMap(),
379 H.getIndexPairOpndHashMap());
380}
381