LLVM: lib/IR/StructuralHash.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
16
17using namespace llvm;
18
19namespace {
20
21
22
23
24
25class StructuralHashImpl {
27
28 bool DetailedHash;
29
30
31
32 static constexpr stable_hash BlockHeaderHash = 45798;
33 static constexpr stable_hash FunctionHeaderHash = 0x62642d6b6b2d6b72;
34 static constexpr stable_hash GlobalHeaderHash = 23456;
35
36
38
39
40
41 std::unique_ptr IndexInstruction = nullptr;
42
43
44 std::unique_ptr IndexOperandHashMap = nullptr;
45
46
47 DenseMap<const Value *, int> ValueToId;
48
50 SmallVector<stable_hash> Hashes;
55 }
56
57public:
58 StructuralHashImpl() = delete;
59 explicit StructuralHashImpl(bool DetailedHash,
61 : DetailedHash(DetailedHash), IgnoreOp(IgnoreOp) {
62 if (IgnoreOp) {
63 IndexInstruction = std::make_unique();
64 IndexOperandHashMap = std::make_unique();
65 }
66 }
67
68 static stable_hash hashAPInt(const APInt &I) {
69 SmallVector<stable_hash> Hashes;
71 auto RawVals = ArrayRef<uint64_t>(I.getRawData(), I.getNumWords());
72 Hashes.append(RawVals.begin(), RawVals.end());
74 }
75
76 static stable_hash hashAPFloat(const APFloat &F) {
77 return hashAPInt(F.bitcastToAPInt());
78 }
79
80 static stable_hash hashGlobalVariable(const GlobalVariable &GVar) {
82 return hashGlobalValue(&GVar);
83
84
88 if (Seq->isString())
90 }
91
92
93
94 static constexpr const char *SectionNames[] = {
95 "__cfstring", "__cstring", "__objc_classrefs",
96 "__objc_methname", "__objc_selrefs",
97 };
103 }
104
105 return hashGlobalValue(&GVar);
106 }
107
108 static stable_hash hashGlobalValue(const GlobalValue *GV) {
110 return 0;
112 }
113
114
115
116
117
118 static stable_hash hashConstant(const Constant *C) {
119 SmallVector<stable_hash> Hashes;
120
123
124 if (C->isNullValue()) {
127 }
128
130 Hashes.emplace_back(hashGlobalVariable(*GVar));
132 }
133
137 }
138
140 if (Seq->isString()) {
143 }
144 }
145
146 switch (C->getValueID()) {
147 case Value::ConstantIntVal: {
151 }
152 case Value::ConstantFPVal: {
156 }
157 case Value::ConstantArrayVal:
158 case Value::ConstantStructVal:
159 case Value::ConstantVectorVal:
160 case Value::ConstantExprVal: {
161 for (const auto &Op : C->operands()) {
164 }
166 }
167 case Value::BlockAddressVal: {
172 }
173 case Value::DSOLocalEquivalentVal: {
175 auto H = hashGlobalValue(Equiv->getGlobalValue());
178 }
179 default:
180
182 }
183 }
184
186
188 if (C)
189 return hashConstant(C);
190
191
192 SmallVector<stable_hash> Hashes;
195
196
197 auto [It, WasInserted] = ValueToId.try_emplace(V, ValueToId.size());
199
201 }
202
204 SmallVector<stable_hash> Hashes;
208 }
209
210 stable_hash hashInstruction(const Instruction &Inst) {
211 SmallVector<stable_hash> Hashes;
213
214 if (!DetailedHash)
216
218
219
220
221 if (const auto *ComparisonInstruction = dyn_cast(&Inst))
222 Hashes.emplace_back(ComparisonInstruction->getPredicate());
223
224 unsigned InstIdx = 0;
225 if (IndexInstruction) {
226 InstIdx = IndexInstruction->size();
227 IndexInstruction->try_emplace(InstIdx, const_cast<Instruction *>(&Inst));
228 }
229
231 auto OpndHash = hashOperand(Op);
232 if (IgnoreOp && IgnoreOp(&Inst, OpndIdx)) {
233 assert(IndexOperandHashMap);
234 IndexOperandHashMap->try_emplace({InstIdx, OpndIdx}, OpndHash);
235 } else
237 }
238
240 }
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258 void update(const Function &F) {
259
260 if (F.isDeclaration())
261 return;
262
263 SmallVector<stable_hash> Hashes;
266
269
270 SmallVector<const BasicBlock *, 8> BBs;
271 SmallPtrSet<const BasicBlock *, 16> VisitedBBs;
272
273
274
275
277 VisitedBBs.insert(BBs[0]);
278 while (!BBs.empty()) {
280
282 for (auto &Inst : *BB)
284
285 for (const BasicBlock *Succ : successors(BB))
286 if (VisitedBBs.insert(Succ).second)
288 }
289
290
292 }
293
294 void update(const GlobalVariable &GV) {
295
296
297
299 return;
300 SmallVector<stable_hash> Hashes;
304
305
307 }
308
309 void update(const Module &M) {
310 for (const GlobalVariable &GV : M.globals())
311 update(GV);
312 for (const Function &F : M)
313 update(F);
314 }
315
316 uint64_t getHash() const { return Hash; }
317
318 std::unique_ptr getIndexInstrMap() {
319 return std::move(IndexInstruction);
320 }
321
322 std::unique_ptr getIndexPairOpndHashMap() {
323 return std::move(IndexOperandHashMap);
324 }
325};
326
327}
328
330 StructuralHashImpl H(DetailedHash);
332 return H.getHash();
333}
334
336 return StructuralHashImpl::hashGlobalVariable(GVar);
337}
338
340 StructuralHashImpl H(DetailedHash);
341 H.update(M);
342 return H.getHash();
343}
344
348 StructuralHashImpl H(true, IgnoreOp);
351 H.getIndexPairOpndHashMap());
352}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
Module.h This file contains the declarations for the Module class.
Machine Check Debug Module
Function * getFunction() const
StringRef getSection() const
Get the custom section of this global if it has one.
bool hasSection() const
Check if this global has a custom object file section.
LLVM_ABI bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Type * getValueType() const
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
bool hasInitializer() const
Definitions have initializers, declarations don't.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
A Module instance is used to store all the information related to an LLVM module.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
reference emplace_back(ArgTypes &&... Args)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
bool starts_with(StringRef Prefix) const
Check if this string starts with the given Prefix.
TypeID getTypeID() const
Return the type id for the type.
Type * getType() const
All values are typed, get the type of this value.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
@ C
The default llvm calling convention, compatible with C.
@ BasicBlock
Various leaf nodes.
static constexpr StringLiteral SectionNames[SectionKindsNum]
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
std::function< bool(const Instruction *, unsigned)> IgnoreOperandFunc
A function that takes an instruction and an operand index and returns true if the operand should be i...
FunctionAddr VTableAddr Value
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are tuples (A, B,...
decltype(auto) dyn_cast(const From &Val)
dyn_cast - Return the argument parameter cast to the specified type.
LLVM_ABI FunctionHashInfo StructuralHashWithDifferences(const Function &F, IgnoreOperandFunc IgnoreOp)
Computes a structural hash of a given function, considering the structure and content of the function...
Definition StructuralHash.cpp:346
auto successors(const MachineBasicBlock *BB)
uint64_t stable_hash
An opaque object representing a stable hash code.
stable_hash stable_hash_name(StringRef Name)
DWARFExpression::Operation Op
decltype(auto) cast(const From &Val)
cast - Return the argument parameter cast to the specified type.
PointerUnion< const Value *, const PseudoSourceValue * > ValueType
stable_hash stable_hash_combine(ArrayRef< stable_hash > Buffer)
LLVM_ABI stable_hash StructuralHash(const Function &F, bool DetailedHash=false)
Returns a hash of the function F.
Definition StructuralHash.cpp:329