1 | //===- FunctionComparator.h - Function Comparator -------------------------===// |
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 | // This file implements the FunctionComparator and GlobalNumberState classes |
10 | // which are used by the MergeFunctions pass for comparing functions. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #include "llvm/Transforms/Utils/FunctionComparator.h" |
15 | #include "llvm/ADT/APFloat.h" |
16 | #include "llvm/ADT/APInt.h" |
17 | #include "llvm/ADT/ArrayRef.h" |
18 | #include "llvm/ADT/Hashing.h" |
19 | #include "llvm/ADT/SmallPtrSet.h" |
20 | #include "llvm/ADT/SmallVector.h" |
21 | #include "llvm/IR/Attributes.h" |
22 | #include "llvm/IR/BasicBlock.h" |
23 | #include "llvm/IR/Constant.h" |
24 | #include "llvm/IR/Constants.h" |
25 | #include "llvm/IR/DataLayout.h" |
26 | #include "llvm/IR/DerivedTypes.h" |
27 | #include "llvm/IR/Function.h" |
28 | #include "llvm/IR/GlobalValue.h" |
29 | #include "llvm/IR/InlineAsm.h" |
30 | #include "llvm/IR/InstrTypes.h" |
31 | #include "llvm/IR/Instruction.h" |
32 | #include "llvm/IR/Instructions.h" |
33 | #include "llvm/IR/LLVMContext.h" |
34 | #include "llvm/IR/Metadata.h" |
35 | #include "llvm/IR/Module.h" |
36 | #include "llvm/IR/Operator.h" |
37 | #include "llvm/IR/Type.h" |
38 | #include "llvm/IR/Value.h" |
39 | #include "llvm/Support/Casting.h" |
40 | #include "llvm/Support/Compiler.h" |
41 | #include "llvm/Support/Debug.h" |
42 | #include "llvm/Support/ErrorHandling.h" |
43 | #include "llvm/Support/raw_ostream.h" |
44 | #include <cassert> |
45 | #include <cstddef> |
46 | #include <cstdint> |
47 | #include <utility> |
48 | |
49 | using namespace llvm; |
50 | |
51 | #define DEBUG_TYPE "functioncomparator" |
52 | |
53 | int FunctionComparator::cmpNumbers(uint64_t L, uint64_t R) const { |
54 | if (L < R) |
55 | return -1; |
56 | if (L > R) |
57 | return 1; |
58 | return 0; |
59 | } |
60 | |
61 | int FunctionComparator::cmpAligns(Align L, Align R) const { |
62 | if (L.value() < R.value()) |
63 | return -1; |
64 | if (L.value() > R.value()) |
65 | return 1; |
66 | return 0; |
67 | } |
68 | |
69 | int FunctionComparator::cmpOrderings(AtomicOrdering L, AtomicOrdering R) const { |
70 | if ((int)L < (int)R) |
71 | return -1; |
72 | if ((int)L > (int)R) |
73 | return 1; |
74 | return 0; |
75 | } |
76 | |
77 | int FunctionComparator::cmpAPInts(const APInt &L, const APInt &R) const { |
78 | if (int Res = cmpNumbers(L: L.getBitWidth(), R: R.getBitWidth())) |
79 | return Res; |
80 | if (L.ugt(RHS: R)) |
81 | return 1; |
82 | if (R.ugt(RHS: L)) |
83 | return -1; |
84 | return 0; |
85 | } |
86 | |
87 | int FunctionComparator::cmpAPFloats(const APFloat &L, const APFloat &R) const { |
88 | // Floats are ordered first by semantics (i.e. float, double, half, etc.), |
89 | // then by value interpreted as a bitstring (aka APInt). |
90 | const fltSemantics &SL = L.getSemantics(), &SR = R.getSemantics(); |
91 | if (int Res = cmpNumbers(L: APFloat::semanticsPrecision(SL), |
92 | R: APFloat::semanticsPrecision(SR))) |
93 | return Res; |
94 | if (int Res = cmpNumbers(L: APFloat::semanticsMaxExponent(SL), |
95 | R: APFloat::semanticsMaxExponent(SR))) |
96 | return Res; |
97 | if (int Res = cmpNumbers(L: APFloat::semanticsMinExponent(SL), |
98 | R: APFloat::semanticsMinExponent(SR))) |
99 | return Res; |
100 | if (int Res = cmpNumbers(L: APFloat::semanticsSizeInBits(SL), |
101 | R: APFloat::semanticsSizeInBits(SR))) |
102 | return Res; |
103 | return cmpAPInts(L: L.bitcastToAPInt(), R: R.bitcastToAPInt()); |
104 | } |
105 | |
106 | int FunctionComparator::cmpMem(StringRef L, StringRef R) const { |
107 | // Prevent heavy comparison, compare sizes first. |
108 | if (int Res = cmpNumbers(L: L.size(), R: R.size())) |
109 | return Res; |
110 | |
111 | // Compare strings lexicographically only when it is necessary: only when |
112 | // strings are equal in size. |
113 | return std::clamp(val: L.compare(RHS: R), lo: -1, hi: 1); |
114 | } |
115 | |
116 | int FunctionComparator::cmpAttrs(const AttributeList L, |
117 | const AttributeList R) const { |
118 | if (int Res = cmpNumbers(L: L.getNumAttrSets(), R: R.getNumAttrSets())) |
119 | return Res; |
120 | |
121 | for (unsigned i : L.indexes()) { |
122 | AttributeSet LAS = L.getAttributes(Index: i); |
123 | AttributeSet RAS = R.getAttributes(Index: i); |
124 | AttributeSet::iterator LI = LAS.begin(), LE = LAS.end(); |
125 | AttributeSet::iterator RI = RAS.begin(), RE = RAS.end(); |
126 | for (; LI != LE && RI != RE; ++LI, ++RI) { |
127 | Attribute LA = *LI; |
128 | Attribute RA = *RI; |
129 | if (LA.isTypeAttribute() && RA.isTypeAttribute()) { |
130 | if (LA.getKindAsEnum() != RA.getKindAsEnum()) |
131 | return cmpNumbers(L: LA.getKindAsEnum(), R: RA.getKindAsEnum()); |
132 | |
133 | Type *TyL = LA.getValueAsType(); |
134 | Type *TyR = RA.getValueAsType(); |
135 | if (TyL && TyR) { |
136 | if (int Res = cmpTypes(TyL, TyR)) |
137 | return Res; |
138 | continue; |
139 | } |
140 | |
141 | // Two pointers, at least one null, so the comparison result is |
142 | // independent of the value of a real pointer. |
143 | if (int Res = cmpNumbers(L: (uint64_t)TyL, R: (uint64_t)TyR)) |
144 | return Res; |
145 | continue; |
146 | } else if (LA.isConstantRangeAttribute() && |
147 | RA.isConstantRangeAttribute()) { |
148 | if (LA.getKindAsEnum() != RA.getKindAsEnum()) |
149 | return cmpNumbers(L: LA.getKindAsEnum(), R: RA.getKindAsEnum()); |
150 | |
151 | ConstantRange LCR = LA.getRange(); |
152 | ConstantRange RCR = RA.getRange(); |
153 | if (int Res = cmpAPInts(L: LCR.getLower(), R: RCR.getLower())) |
154 | return Res; |
155 | if (int Res = cmpAPInts(L: LCR.getUpper(), R: RCR.getUpper())) |
156 | return Res; |
157 | continue; |
158 | } |
159 | if (LA < RA) |
160 | return -1; |
161 | if (RA < LA) |
162 | return 1; |
163 | } |
164 | if (LI != LE) |
165 | return 1; |
166 | if (RI != RE) |
167 | return -1; |
168 | } |
169 | return 0; |
170 | } |
171 | |
172 | int FunctionComparator::cmpMetadata(const Metadata *L, |
173 | const Metadata *R) const { |
174 | // TODO: the following routine coerce the metadata contents into constants |
175 | // or MDStrings before comparison. |
176 | // It ignores any other cases, so that the metadata nodes are considered |
177 | // equal even though this is not correct. |
178 | // We should structurally compare the metadata nodes to be perfect here. |
179 | |
180 | auto *MDStringL = dyn_cast<MDString>(Val: L); |
181 | auto *MDStringR = dyn_cast<MDString>(Val: R); |
182 | if (MDStringL && MDStringR) { |
183 | if (MDStringL == MDStringR) |
184 | return 0; |
185 | return MDStringL->getString().compare(RHS: MDStringR->getString()); |
186 | } |
187 | if (MDStringR) |
188 | return -1; |
189 | if (MDStringL) |
190 | return 1; |
191 | |
192 | auto *CL = dyn_cast<ConstantAsMetadata>(Val: L); |
193 | auto *CR = dyn_cast<ConstantAsMetadata>(Val: R); |
194 | if (CL == CR) |
195 | return 0; |
196 | if (!CL) |
197 | return -1; |
198 | if (!CR) |
199 | return 1; |
200 | return cmpConstants(L: CL->getValue(), R: CR->getValue()); |
201 | } |
202 | |
203 | int FunctionComparator::cmpMDNode(const MDNode *L, const MDNode *R) const { |
204 | if (L == R) |
205 | return 0; |
206 | if (!L) |
207 | return -1; |
208 | if (!R) |
209 | return 1; |
210 | // TODO: Note that as this is metadata, it is possible to drop and/or merge |
211 | // this data when considering functions to merge. Thus this comparison would |
212 | // return 0 (i.e. equivalent), but merging would become more complicated |
213 | // because the ranges would need to be unioned. It is not likely that |
214 | // functions differ ONLY in this metadata if they are actually the same |
215 | // function semantically. |
216 | if (int Res = cmpNumbers(L: L->getNumOperands(), R: R->getNumOperands())) |
217 | return Res; |
218 | for (size_t I = 0; I < L->getNumOperands(); ++I) |
219 | if (int Res = cmpMetadata(L: L->getOperand(I), R: R->getOperand(I))) |
220 | return Res; |
221 | return 0; |
222 | } |
223 | |
224 | int FunctionComparator::cmpInstMetadata(Instruction const *L, |
225 | Instruction const *R) const { |
226 | /// These metadata affects the other optimization passes by making assertions |
227 | /// or constraints. |
228 | /// Values that carry different expectations should be considered different. |
229 | SmallVector<std::pair<unsigned, MDNode *>> MDL, MDR; |
230 | L->getAllMetadataOtherThanDebugLoc(MDs&: MDL); |
231 | R->getAllMetadataOtherThanDebugLoc(MDs&: MDR); |
232 | if (MDL.size() > MDR.size()) |
233 | return 1; |
234 | else if (MDL.size() < MDR.size()) |
235 | return -1; |
236 | for (size_t I = 0, N = MDL.size(); I < N; ++I) { |
237 | auto const [KeyL, ML] = MDL[I]; |
238 | auto const [KeyR, MR] = MDR[I]; |
239 | if (int Res = cmpNumbers(L: KeyL, R: KeyR)) |
240 | return Res; |
241 | if (int Res = cmpMDNode(L: ML, R: MR)) |
242 | return Res; |
243 | } |
244 | return 0; |
245 | } |
246 | |
247 | int FunctionComparator::cmpOperandBundlesSchema(const CallBase &LCS, |
248 | const CallBase &RCS) const { |
249 | assert(LCS.getOpcode() == RCS.getOpcode() && "Can't compare otherwise!" ); |
250 | |
251 | if (int Res = |
252 | cmpNumbers(L: LCS.getNumOperandBundles(), R: RCS.getNumOperandBundles())) |
253 | return Res; |
254 | |
255 | for (unsigned I = 0, E = LCS.getNumOperandBundles(); I != E; ++I) { |
256 | auto OBL = LCS.getOperandBundleAt(Index: I); |
257 | auto OBR = RCS.getOperandBundleAt(Index: I); |
258 | |
259 | if (int Res = OBL.getTagName().compare(RHS: OBR.getTagName())) |
260 | return Res; |
261 | |
262 | if (int Res = cmpNumbers(L: OBL.Inputs.size(), R: OBR.Inputs.size())) |
263 | return Res; |
264 | } |
265 | |
266 | return 0; |
267 | } |
268 | |
269 | /// Constants comparison: |
270 | /// 1. Check whether type of L constant could be losslessly bitcasted to R |
271 | /// type. |
272 | /// 2. Compare constant contents. |
273 | /// For more details see declaration comments. |
274 | int FunctionComparator::cmpConstants(const Constant *L, |
275 | const Constant *R) const { |
276 | Type *TyL = L->getType(); |
277 | Type *TyR = R->getType(); |
278 | |
279 | // Check whether types are bitcastable. This part is just re-factored |
280 | // Type::canLosslesslyBitCastTo method, but instead of returning true/false, |
281 | // we also pack into result which type is "less" for us. |
282 | int TypesRes = cmpTypes(TyL, TyR); |
283 | if (TypesRes != 0) { |
284 | // Types are different, but check whether we can bitcast them. |
285 | if (!TyL->isFirstClassType()) { |
286 | if (TyR->isFirstClassType()) |
287 | return -1; |
288 | // Neither TyL nor TyR are values of first class type. Return the result |
289 | // of comparing the types |
290 | return TypesRes; |
291 | } |
292 | if (!TyR->isFirstClassType()) { |
293 | if (TyL->isFirstClassType()) |
294 | return 1; |
295 | return TypesRes; |
296 | } |
297 | |
298 | // Vector -> Vector conversions are always lossless if the two vector types |
299 | // have the same size, otherwise not. |
300 | unsigned TyLWidth = 0; |
301 | unsigned TyRWidth = 0; |
302 | |
303 | if (auto *VecTyL = dyn_cast<VectorType>(Val: TyL)) |
304 | TyLWidth = VecTyL->getPrimitiveSizeInBits().getFixedValue(); |
305 | if (auto *VecTyR = dyn_cast<VectorType>(Val: TyR)) |
306 | TyRWidth = VecTyR->getPrimitiveSizeInBits().getFixedValue(); |
307 | |
308 | if (TyLWidth != TyRWidth) |
309 | return cmpNumbers(L: TyLWidth, R: TyRWidth); |
310 | |
311 | // Zero bit-width means neither TyL nor TyR are vectors. |
312 | if (!TyLWidth) { |
313 | PointerType *PTyL = dyn_cast<PointerType>(Val: TyL); |
314 | PointerType *PTyR = dyn_cast<PointerType>(Val: TyR); |
315 | if (PTyL && PTyR) { |
316 | unsigned AddrSpaceL = PTyL->getAddressSpace(); |
317 | unsigned AddrSpaceR = PTyR->getAddressSpace(); |
318 | if (int Res = cmpNumbers(L: AddrSpaceL, R: AddrSpaceR)) |
319 | return Res; |
320 | } |
321 | if (PTyL) |
322 | return 1; |
323 | if (PTyR) |
324 | return -1; |
325 | |
326 | // TyL and TyR aren't vectors, nor pointers. We don't know how to |
327 | // bitcast them. |
328 | return TypesRes; |
329 | } |
330 | } |
331 | |
332 | // OK, types are bitcastable, now check constant contents. |
333 | |
334 | if (L->isNullValue() && R->isNullValue()) |
335 | return TypesRes; |
336 | if (L->isNullValue() && !R->isNullValue()) |
337 | return 1; |
338 | if (!L->isNullValue() && R->isNullValue()) |
339 | return -1; |
340 | |
341 | auto GlobalValueL = const_cast<GlobalValue *>(dyn_cast<GlobalValue>(Val: L)); |
342 | auto GlobalValueR = const_cast<GlobalValue *>(dyn_cast<GlobalValue>(Val: R)); |
343 | if (GlobalValueL && GlobalValueR) { |
344 | return cmpGlobalValues(L: GlobalValueL, R: GlobalValueR); |
345 | } |
346 | |
347 | if (int Res = cmpNumbers(L: L->getValueID(), R: R->getValueID())) |
348 | return Res; |
349 | |
350 | if (const auto *SeqL = dyn_cast<ConstantDataSequential>(Val: L)) { |
351 | const auto *SeqR = cast<ConstantDataSequential>(Val: R); |
352 | // This handles ConstantDataArray and ConstantDataVector. Note that we |
353 | // compare the two raw data arrays, which might differ depending on the host |
354 | // endianness. This isn't a problem though, because the endiness of a module |
355 | // will affect the order of the constants, but this order is the same |
356 | // for a given input module and host platform. |
357 | return cmpMem(L: SeqL->getRawDataValues(), R: SeqR->getRawDataValues()); |
358 | } |
359 | |
360 | switch (L->getValueID()) { |
361 | case Value::UndefValueVal: |
362 | case Value::PoisonValueVal: |
363 | case Value::ConstantTokenNoneVal: |
364 | return TypesRes; |
365 | case Value::ConstantIntVal: { |
366 | const APInt &LInt = cast<ConstantInt>(Val: L)->getValue(); |
367 | const APInt &RInt = cast<ConstantInt>(Val: R)->getValue(); |
368 | return cmpAPInts(L: LInt, R: RInt); |
369 | } |
370 | case Value::ConstantFPVal: { |
371 | const APFloat &LAPF = cast<ConstantFP>(Val: L)->getValueAPF(); |
372 | const APFloat &RAPF = cast<ConstantFP>(Val: R)->getValueAPF(); |
373 | return cmpAPFloats(L: LAPF, R: RAPF); |
374 | } |
375 | case Value::ConstantArrayVal: { |
376 | const ConstantArray *LA = cast<ConstantArray>(Val: L); |
377 | const ConstantArray *RA = cast<ConstantArray>(Val: R); |
378 | uint64_t NumElementsL = cast<ArrayType>(Val: TyL)->getNumElements(); |
379 | uint64_t NumElementsR = cast<ArrayType>(Val: TyR)->getNumElements(); |
380 | if (int Res = cmpNumbers(L: NumElementsL, R: NumElementsR)) |
381 | return Res; |
382 | for (uint64_t i = 0; i < NumElementsL; ++i) { |
383 | if (int Res = cmpConstants(L: cast<Constant>(Val: LA->getOperand(i_nocapture: i)), |
384 | R: cast<Constant>(Val: RA->getOperand(i_nocapture: i)))) |
385 | return Res; |
386 | } |
387 | return 0; |
388 | } |
389 | case Value::ConstantStructVal: { |
390 | const ConstantStruct *LS = cast<ConstantStruct>(Val: L); |
391 | const ConstantStruct *RS = cast<ConstantStruct>(Val: R); |
392 | unsigned NumElementsL = cast<StructType>(Val: TyL)->getNumElements(); |
393 | unsigned NumElementsR = cast<StructType>(Val: TyR)->getNumElements(); |
394 | if (int Res = cmpNumbers(L: NumElementsL, R: NumElementsR)) |
395 | return Res; |
396 | for (unsigned i = 0; i != NumElementsL; ++i) { |
397 | if (int Res = cmpConstants(L: cast<Constant>(Val: LS->getOperand(i_nocapture: i)), |
398 | R: cast<Constant>(Val: RS->getOperand(i_nocapture: i)))) |
399 | return Res; |
400 | } |
401 | return 0; |
402 | } |
403 | case Value::ConstantVectorVal: { |
404 | const ConstantVector *LV = cast<ConstantVector>(Val: L); |
405 | const ConstantVector *RV = cast<ConstantVector>(Val: R); |
406 | unsigned NumElementsL = cast<FixedVectorType>(Val: TyL)->getNumElements(); |
407 | unsigned NumElementsR = cast<FixedVectorType>(Val: TyR)->getNumElements(); |
408 | if (int Res = cmpNumbers(L: NumElementsL, R: NumElementsR)) |
409 | return Res; |
410 | for (uint64_t i = 0; i < NumElementsL; ++i) { |
411 | if (int Res = cmpConstants(L: cast<Constant>(Val: LV->getOperand(i_nocapture: i)), |
412 | R: cast<Constant>(Val: RV->getOperand(i_nocapture: i)))) |
413 | return Res; |
414 | } |
415 | return 0; |
416 | } |
417 | case Value::ConstantExprVal: { |
418 | const ConstantExpr *LE = cast<ConstantExpr>(Val: L); |
419 | const ConstantExpr *RE = cast<ConstantExpr>(Val: R); |
420 | if (int Res = cmpNumbers(L: LE->getOpcode(), R: RE->getOpcode())) |
421 | return Res; |
422 | unsigned NumOperandsL = LE->getNumOperands(); |
423 | unsigned NumOperandsR = RE->getNumOperands(); |
424 | if (int Res = cmpNumbers(L: NumOperandsL, R: NumOperandsR)) |
425 | return Res; |
426 | for (unsigned i = 0; i < NumOperandsL; ++i) { |
427 | if (int Res = cmpConstants(L: cast<Constant>(Val: LE->getOperand(i_nocapture: i)), |
428 | R: cast<Constant>(Val: RE->getOperand(i_nocapture: i)))) |
429 | return Res; |
430 | } |
431 | if (LE->isCompare()) |
432 | if (int Res = cmpNumbers(L: LE->getPredicate(), R: RE->getPredicate())) |
433 | return Res; |
434 | if (auto *GEPL = dyn_cast<GEPOperator>(Val: LE)) { |
435 | auto *GEPR = cast<GEPOperator>(Val: RE); |
436 | if (int Res = cmpTypes(TyL: GEPL->getSourceElementType(), |
437 | TyR: GEPR->getSourceElementType())) |
438 | return Res; |
439 | if (int Res = cmpNumbers(L: GEPL->isInBounds(), R: GEPR->isInBounds())) |
440 | return Res; |
441 | |
442 | std::optional<ConstantRange> InRangeL = GEPL->getInRange(); |
443 | std::optional<ConstantRange> InRangeR = GEPR->getInRange(); |
444 | if (InRangeL) { |
445 | if (!InRangeR) |
446 | return 1; |
447 | if (int Res = cmpAPInts(L: InRangeL->getLower(), R: InRangeR->getLower())) |
448 | return Res; |
449 | if (int Res = cmpAPInts(L: InRangeL->getUpper(), R: InRangeR->getUpper())) |
450 | return Res; |
451 | } else if (InRangeR) { |
452 | return -1; |
453 | } |
454 | } |
455 | if (auto *OBOL = dyn_cast<OverflowingBinaryOperator>(Val: LE)) { |
456 | auto *OBOR = cast<OverflowingBinaryOperator>(Val: RE); |
457 | if (int Res = |
458 | cmpNumbers(L: OBOL->hasNoUnsignedWrap(), R: OBOR->hasNoUnsignedWrap())) |
459 | return Res; |
460 | if (int Res = |
461 | cmpNumbers(L: OBOL->hasNoSignedWrap(), R: OBOR->hasNoSignedWrap())) |
462 | return Res; |
463 | } |
464 | return 0; |
465 | } |
466 | case Value::BlockAddressVal: { |
467 | const BlockAddress *LBA = cast<BlockAddress>(Val: L); |
468 | const BlockAddress *RBA = cast<BlockAddress>(Val: R); |
469 | if (int Res = cmpValues(L: LBA->getFunction(), R: RBA->getFunction())) |
470 | return Res; |
471 | if (LBA->getFunction() == RBA->getFunction()) { |
472 | // They are BBs in the same function. Order by which comes first in the |
473 | // BB order of the function. This order is deterministic. |
474 | Function *F = LBA->getFunction(); |
475 | BasicBlock *LBB = LBA->getBasicBlock(); |
476 | BasicBlock *RBB = RBA->getBasicBlock(); |
477 | if (LBB == RBB) |
478 | return 0; |
479 | for (BasicBlock &BB : *F) { |
480 | if (&BB == LBB) { |
481 | assert(&BB != RBB); |
482 | return -1; |
483 | } |
484 | if (&BB == RBB) |
485 | return 1; |
486 | } |
487 | llvm_unreachable("Basic Block Address does not point to a basic block in " |
488 | "its function." ); |
489 | return -1; |
490 | } else { |
491 | // cmpValues said the functions are the same. So because they aren't |
492 | // literally the same pointer, they must respectively be the left and |
493 | // right functions. |
494 | assert(LBA->getFunction() == FnL && RBA->getFunction() == FnR); |
495 | // cmpValues will tell us if these are equivalent BasicBlocks, in the |
496 | // context of their respective functions. |
497 | return cmpValues(L: LBA->getBasicBlock(), R: RBA->getBasicBlock()); |
498 | } |
499 | } |
500 | case Value::DSOLocalEquivalentVal: { |
501 | // dso_local_equivalent is functionally equivalent to whatever it points to. |
502 | // This means the behavior of the IR should be the exact same as if the |
503 | // function was referenced directly rather than through a |
504 | // dso_local_equivalent. |
505 | const auto *LEquiv = cast<DSOLocalEquivalent>(Val: L); |
506 | const auto *REquiv = cast<DSOLocalEquivalent>(Val: R); |
507 | return cmpGlobalValues(L: LEquiv->getGlobalValue(), R: REquiv->getGlobalValue()); |
508 | } |
509 | default: // Unknown constant, abort. |
510 | LLVM_DEBUG(dbgs() << "Looking at valueID " << L->getValueID() << "\n" ); |
511 | llvm_unreachable("Constant ValueID not recognized." ); |
512 | return -1; |
513 | } |
514 | } |
515 | |
516 | int FunctionComparator::cmpGlobalValues(GlobalValue *L, GlobalValue *R) const { |
517 | uint64_t LNumber = GlobalNumbers->getNumber(Global: L); |
518 | uint64_t RNumber = GlobalNumbers->getNumber(Global: R); |
519 | return cmpNumbers(L: LNumber, R: RNumber); |
520 | } |
521 | |
522 | /// cmpType - compares two types, |
523 | /// defines total ordering among the types set. |
524 | /// See method declaration comments for more details. |
525 | int FunctionComparator::cmpTypes(Type *TyL, Type *TyR) const { |
526 | PointerType *PTyL = dyn_cast<PointerType>(Val: TyL); |
527 | PointerType *PTyR = dyn_cast<PointerType>(Val: TyR); |
528 | |
529 | const DataLayout &DL = FnL->getParent()->getDataLayout(); |
530 | if (PTyL && PTyL->getAddressSpace() == 0) |
531 | TyL = DL.getIntPtrType(TyL); |
532 | if (PTyR && PTyR->getAddressSpace() == 0) |
533 | TyR = DL.getIntPtrType(TyR); |
534 | |
535 | if (TyL == TyR) |
536 | return 0; |
537 | |
538 | if (int Res = cmpNumbers(L: TyL->getTypeID(), R: TyR->getTypeID())) |
539 | return Res; |
540 | |
541 | switch (TyL->getTypeID()) { |
542 | default: |
543 | llvm_unreachable("Unknown type!" ); |
544 | case Type::IntegerTyID: |
545 | return cmpNumbers(L: cast<IntegerType>(Val: TyL)->getBitWidth(), |
546 | R: cast<IntegerType>(Val: TyR)->getBitWidth()); |
547 | // TyL == TyR would have returned true earlier, because types are uniqued. |
548 | case Type::VoidTyID: |
549 | case Type::FloatTyID: |
550 | case Type::DoubleTyID: |
551 | case Type::X86_FP80TyID: |
552 | case Type::FP128TyID: |
553 | case Type::PPC_FP128TyID: |
554 | case Type::LabelTyID: |
555 | case Type::MetadataTyID: |
556 | case Type::TokenTyID: |
557 | return 0; |
558 | |
559 | case Type::PointerTyID: |
560 | assert(PTyL && PTyR && "Both types must be pointers here." ); |
561 | return cmpNumbers(L: PTyL->getAddressSpace(), R: PTyR->getAddressSpace()); |
562 | |
563 | case Type::StructTyID: { |
564 | StructType *STyL = cast<StructType>(Val: TyL); |
565 | StructType *STyR = cast<StructType>(Val: TyR); |
566 | if (STyL->getNumElements() != STyR->getNumElements()) |
567 | return cmpNumbers(L: STyL->getNumElements(), R: STyR->getNumElements()); |
568 | |
569 | if (STyL->isPacked() != STyR->isPacked()) |
570 | return cmpNumbers(L: STyL->isPacked(), R: STyR->isPacked()); |
571 | |
572 | for (unsigned i = 0, e = STyL->getNumElements(); i != e; ++i) { |
573 | if (int Res = cmpTypes(TyL: STyL->getElementType(N: i), TyR: STyR->getElementType(N: i))) |
574 | return Res; |
575 | } |
576 | return 0; |
577 | } |
578 | |
579 | case Type::FunctionTyID: { |
580 | FunctionType *FTyL = cast<FunctionType>(Val: TyL); |
581 | FunctionType *FTyR = cast<FunctionType>(Val: TyR); |
582 | if (FTyL->getNumParams() != FTyR->getNumParams()) |
583 | return cmpNumbers(L: FTyL->getNumParams(), R: FTyR->getNumParams()); |
584 | |
585 | if (FTyL->isVarArg() != FTyR->isVarArg()) |
586 | return cmpNumbers(L: FTyL->isVarArg(), R: FTyR->isVarArg()); |
587 | |
588 | if (int Res = cmpTypes(TyL: FTyL->getReturnType(), TyR: FTyR->getReturnType())) |
589 | return Res; |
590 | |
591 | for (unsigned i = 0, e = FTyL->getNumParams(); i != e; ++i) { |
592 | if (int Res = cmpTypes(TyL: FTyL->getParamType(i), TyR: FTyR->getParamType(i))) |
593 | return Res; |
594 | } |
595 | return 0; |
596 | } |
597 | |
598 | case Type::ArrayTyID: { |
599 | auto *STyL = cast<ArrayType>(Val: TyL); |
600 | auto *STyR = cast<ArrayType>(Val: TyR); |
601 | if (STyL->getNumElements() != STyR->getNumElements()) |
602 | return cmpNumbers(L: STyL->getNumElements(), R: STyR->getNumElements()); |
603 | return cmpTypes(TyL: STyL->getElementType(), TyR: STyR->getElementType()); |
604 | } |
605 | case Type::FixedVectorTyID: |
606 | case Type::ScalableVectorTyID: { |
607 | auto *STyL = cast<VectorType>(Val: TyL); |
608 | auto *STyR = cast<VectorType>(Val: TyR); |
609 | if (STyL->getElementCount().isScalable() != |
610 | STyR->getElementCount().isScalable()) |
611 | return cmpNumbers(L: STyL->getElementCount().isScalable(), |
612 | R: STyR->getElementCount().isScalable()); |
613 | if (STyL->getElementCount() != STyR->getElementCount()) |
614 | return cmpNumbers(L: STyL->getElementCount().getKnownMinValue(), |
615 | R: STyR->getElementCount().getKnownMinValue()); |
616 | return cmpTypes(TyL: STyL->getElementType(), TyR: STyR->getElementType()); |
617 | } |
618 | } |
619 | } |
620 | |
621 | // Determine whether the two operations are the same except that pointer-to-A |
622 | // and pointer-to-B are equivalent. This should be kept in sync with |
623 | // Instruction::isSameOperationAs. |
624 | // Read method declaration comments for more details. |
625 | int FunctionComparator::cmpOperations(const Instruction *L, |
626 | const Instruction *R, |
627 | bool &needToCmpOperands) const { |
628 | needToCmpOperands = true; |
629 | if (int Res = cmpValues(L, R)) |
630 | return Res; |
631 | |
632 | // Differences from Instruction::isSameOperationAs: |
633 | // * replace type comparison with calls to cmpTypes. |
634 | // * we test for I->getRawSubclassOptionalData (nuw/nsw/tail) at the top. |
635 | // * because of the above, we don't test for the tail bit on calls later on. |
636 | if (int Res = cmpNumbers(L: L->getOpcode(), R: R->getOpcode())) |
637 | return Res; |
638 | |
639 | if (const GetElementPtrInst *GEPL = dyn_cast<GetElementPtrInst>(Val: L)) { |
640 | needToCmpOperands = false; |
641 | const GetElementPtrInst *GEPR = cast<GetElementPtrInst>(Val: R); |
642 | if (int Res = |
643 | cmpValues(L: GEPL->getPointerOperand(), R: GEPR->getPointerOperand())) |
644 | return Res; |
645 | return cmpGEPs(GEPL, GEPR); |
646 | } |
647 | |
648 | if (int Res = cmpNumbers(L: L->getNumOperands(), R: R->getNumOperands())) |
649 | return Res; |
650 | |
651 | if (int Res = cmpTypes(TyL: L->getType(), TyR: R->getType())) |
652 | return Res; |
653 | |
654 | if (int Res = cmpNumbers(L: L->getRawSubclassOptionalData(), |
655 | R: R->getRawSubclassOptionalData())) |
656 | return Res; |
657 | |
658 | // We have two instructions of identical opcode and #operands. Check to see |
659 | // if all operands are the same type |
660 | for (unsigned i = 0, e = L->getNumOperands(); i != e; ++i) { |
661 | if (int Res = |
662 | cmpTypes(TyL: L->getOperand(i)->getType(), TyR: R->getOperand(i)->getType())) |
663 | return Res; |
664 | } |
665 | |
666 | // Check special state that is a part of some instructions. |
667 | if (const AllocaInst *AI = dyn_cast<AllocaInst>(Val: L)) { |
668 | if (int Res = cmpTypes(TyL: AI->getAllocatedType(), |
669 | TyR: cast<AllocaInst>(Val: R)->getAllocatedType())) |
670 | return Res; |
671 | return cmpAligns(L: AI->getAlign(), R: cast<AllocaInst>(Val: R)->getAlign()); |
672 | } |
673 | if (const LoadInst *LI = dyn_cast<LoadInst>(Val: L)) { |
674 | if (int Res = cmpNumbers(L: LI->isVolatile(), R: cast<LoadInst>(Val: R)->isVolatile())) |
675 | return Res; |
676 | if (int Res = cmpAligns(L: LI->getAlign(), R: cast<LoadInst>(Val: R)->getAlign())) |
677 | return Res; |
678 | if (int Res = |
679 | cmpOrderings(L: LI->getOrdering(), R: cast<LoadInst>(Val: R)->getOrdering())) |
680 | return Res; |
681 | if (int Res = cmpNumbers(L: LI->getSyncScopeID(), |
682 | R: cast<LoadInst>(Val: R)->getSyncScopeID())) |
683 | return Res; |
684 | return cmpInstMetadata(L, R); |
685 | } |
686 | if (const StoreInst *SI = dyn_cast<StoreInst>(Val: L)) { |
687 | if (int Res = |
688 | cmpNumbers(L: SI->isVolatile(), R: cast<StoreInst>(Val: R)->isVolatile())) |
689 | return Res; |
690 | if (int Res = cmpAligns(L: SI->getAlign(), R: cast<StoreInst>(Val: R)->getAlign())) |
691 | return Res; |
692 | if (int Res = |
693 | cmpOrderings(L: SI->getOrdering(), R: cast<StoreInst>(Val: R)->getOrdering())) |
694 | return Res; |
695 | return cmpNumbers(L: SI->getSyncScopeID(), |
696 | R: cast<StoreInst>(Val: R)->getSyncScopeID()); |
697 | } |
698 | if (const CmpInst *CI = dyn_cast<CmpInst>(Val: L)) |
699 | return cmpNumbers(L: CI->getPredicate(), R: cast<CmpInst>(Val: R)->getPredicate()); |
700 | if (auto *CBL = dyn_cast<CallBase>(Val: L)) { |
701 | auto *CBR = cast<CallBase>(Val: R); |
702 | if (int Res = cmpNumbers(L: CBL->getCallingConv(), R: CBR->getCallingConv())) |
703 | return Res; |
704 | if (int Res = cmpAttrs(L: CBL->getAttributes(), R: CBR->getAttributes())) |
705 | return Res; |
706 | if (int Res = cmpOperandBundlesSchema(LCS: *CBL, RCS: *CBR)) |
707 | return Res; |
708 | if (const CallInst *CI = dyn_cast<CallInst>(Val: L)) |
709 | if (int Res = cmpNumbers(L: CI->getTailCallKind(), |
710 | R: cast<CallInst>(Val: R)->getTailCallKind())) |
711 | return Res; |
712 | return cmpMDNode(L: L->getMetadata(KindID: LLVMContext::MD_range), |
713 | R: R->getMetadata(KindID: LLVMContext::MD_range)); |
714 | } |
715 | if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Val: L)) { |
716 | ArrayRef<unsigned> LIndices = IVI->getIndices(); |
717 | ArrayRef<unsigned> RIndices = cast<InsertValueInst>(Val: R)->getIndices(); |
718 | if (int Res = cmpNumbers(L: LIndices.size(), R: RIndices.size())) |
719 | return Res; |
720 | for (size_t i = 0, e = LIndices.size(); i != e; ++i) { |
721 | if (int Res = cmpNumbers(L: LIndices[i], R: RIndices[i])) |
722 | return Res; |
723 | } |
724 | return 0; |
725 | } |
726 | if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Val: L)) { |
727 | ArrayRef<unsigned> LIndices = EVI->getIndices(); |
728 | ArrayRef<unsigned> RIndices = cast<ExtractValueInst>(Val: R)->getIndices(); |
729 | if (int Res = cmpNumbers(L: LIndices.size(), R: RIndices.size())) |
730 | return Res; |
731 | for (size_t i = 0, e = LIndices.size(); i != e; ++i) { |
732 | if (int Res = cmpNumbers(L: LIndices[i], R: RIndices[i])) |
733 | return Res; |
734 | } |
735 | } |
736 | if (const FenceInst *FI = dyn_cast<FenceInst>(Val: L)) { |
737 | if (int Res = |
738 | cmpOrderings(L: FI->getOrdering(), R: cast<FenceInst>(Val: R)->getOrdering())) |
739 | return Res; |
740 | return cmpNumbers(L: FI->getSyncScopeID(), |
741 | R: cast<FenceInst>(Val: R)->getSyncScopeID()); |
742 | } |
743 | if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(Val: L)) { |
744 | if (int Res = cmpNumbers(L: CXI->isVolatile(), |
745 | R: cast<AtomicCmpXchgInst>(Val: R)->isVolatile())) |
746 | return Res; |
747 | if (int Res = |
748 | cmpNumbers(L: CXI->isWeak(), R: cast<AtomicCmpXchgInst>(Val: R)->isWeak())) |
749 | return Res; |
750 | if (int Res = |
751 | cmpOrderings(L: CXI->getSuccessOrdering(), |
752 | R: cast<AtomicCmpXchgInst>(Val: R)->getSuccessOrdering())) |
753 | return Res; |
754 | if (int Res = |
755 | cmpOrderings(L: CXI->getFailureOrdering(), |
756 | R: cast<AtomicCmpXchgInst>(Val: R)->getFailureOrdering())) |
757 | return Res; |
758 | return cmpNumbers(L: CXI->getSyncScopeID(), |
759 | R: cast<AtomicCmpXchgInst>(Val: R)->getSyncScopeID()); |
760 | } |
761 | if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(Val: L)) { |
762 | if (int Res = cmpNumbers(L: RMWI->getOperation(), |
763 | R: cast<AtomicRMWInst>(Val: R)->getOperation())) |
764 | return Res; |
765 | if (int Res = cmpNumbers(L: RMWI->isVolatile(), |
766 | R: cast<AtomicRMWInst>(Val: R)->isVolatile())) |
767 | return Res; |
768 | if (int Res = cmpOrderings(L: RMWI->getOrdering(), |
769 | R: cast<AtomicRMWInst>(Val: R)->getOrdering())) |
770 | return Res; |
771 | return cmpNumbers(L: RMWI->getSyncScopeID(), |
772 | R: cast<AtomicRMWInst>(Val: R)->getSyncScopeID()); |
773 | } |
774 | if (const ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(Val: L)) { |
775 | ArrayRef<int> LMask = SVI->getShuffleMask(); |
776 | ArrayRef<int> RMask = cast<ShuffleVectorInst>(Val: R)->getShuffleMask(); |
777 | if (int Res = cmpNumbers(L: LMask.size(), R: RMask.size())) |
778 | return Res; |
779 | for (size_t i = 0, e = LMask.size(); i != e; ++i) { |
780 | if (int Res = cmpNumbers(L: LMask[i], R: RMask[i])) |
781 | return Res; |
782 | } |
783 | } |
784 | if (const PHINode *PNL = dyn_cast<PHINode>(Val: L)) { |
785 | const PHINode *PNR = cast<PHINode>(Val: R); |
786 | // Ensure that in addition to the incoming values being identical |
787 | // (checked by the caller of this function), the incoming blocks |
788 | // are also identical. |
789 | for (unsigned i = 0, e = PNL->getNumIncomingValues(); i != e; ++i) { |
790 | if (int Res = |
791 | cmpValues(L: PNL->getIncomingBlock(i), R: PNR->getIncomingBlock(i))) |
792 | return Res; |
793 | } |
794 | } |
795 | return 0; |
796 | } |
797 | |
798 | // Determine whether two GEP operations perform the same underlying arithmetic. |
799 | // Read method declaration comments for more details. |
800 | int FunctionComparator::cmpGEPs(const GEPOperator *GEPL, |
801 | const GEPOperator *GEPR) const { |
802 | unsigned int ASL = GEPL->getPointerAddressSpace(); |
803 | unsigned int ASR = GEPR->getPointerAddressSpace(); |
804 | |
805 | if (int Res = cmpNumbers(L: ASL, R: ASR)) |
806 | return Res; |
807 | |
808 | // When we have target data, we can reduce the GEP down to the value in bytes |
809 | // added to the address. |
810 | const DataLayout &DL = FnL->getParent()->getDataLayout(); |
811 | unsigned OffsetBitWidth = DL.getIndexSizeInBits(AS: ASL); |
812 | APInt OffsetL(OffsetBitWidth, 0), OffsetR(OffsetBitWidth, 0); |
813 | if (GEPL->accumulateConstantOffset(DL, Offset&: OffsetL) && |
814 | GEPR->accumulateConstantOffset(DL, Offset&: OffsetR)) |
815 | return cmpAPInts(L: OffsetL, R: OffsetR); |
816 | if (int Res = |
817 | cmpTypes(TyL: GEPL->getSourceElementType(), TyR: GEPR->getSourceElementType())) |
818 | return Res; |
819 | |
820 | if (int Res = cmpNumbers(L: GEPL->getNumOperands(), R: GEPR->getNumOperands())) |
821 | return Res; |
822 | |
823 | for (unsigned i = 0, e = GEPL->getNumOperands(); i != e; ++i) { |
824 | if (int Res = cmpValues(L: GEPL->getOperand(i_nocapture: i), R: GEPR->getOperand(i_nocapture: i))) |
825 | return Res; |
826 | } |
827 | |
828 | return 0; |
829 | } |
830 | |
831 | int FunctionComparator::cmpInlineAsm(const InlineAsm *L, |
832 | const InlineAsm *R) const { |
833 | // InlineAsm's are uniqued. If they are the same pointer, obviously they are |
834 | // the same, otherwise compare the fields. |
835 | if (L == R) |
836 | return 0; |
837 | if (int Res = cmpTypes(TyL: L->getFunctionType(), TyR: R->getFunctionType())) |
838 | return Res; |
839 | if (int Res = cmpMem(L: L->getAsmString(), R: R->getAsmString())) |
840 | return Res; |
841 | if (int Res = cmpMem(L: L->getConstraintString(), R: R->getConstraintString())) |
842 | return Res; |
843 | if (int Res = cmpNumbers(L: L->hasSideEffects(), R: R->hasSideEffects())) |
844 | return Res; |
845 | if (int Res = cmpNumbers(L: L->isAlignStack(), R: R->isAlignStack())) |
846 | return Res; |
847 | if (int Res = cmpNumbers(L: L->getDialect(), R: R->getDialect())) |
848 | return Res; |
849 | assert(L->getFunctionType() != R->getFunctionType()); |
850 | return 0; |
851 | } |
852 | |
853 | /// Compare two values used by the two functions under pair-wise comparison. If |
854 | /// this is the first time the values are seen, they're added to the mapping so |
855 | /// that we will detect mismatches on next use. |
856 | /// See comments in declaration for more details. |
857 | int FunctionComparator::cmpValues(const Value *L, const Value *R) const { |
858 | // Catch self-reference case. |
859 | if (L == FnL) { |
860 | if (R == FnR) |
861 | return 0; |
862 | return -1; |
863 | } |
864 | if (R == FnR) { |
865 | if (L == FnL) |
866 | return 0; |
867 | return 1; |
868 | } |
869 | |
870 | const Constant *ConstL = dyn_cast<Constant>(Val: L); |
871 | const Constant *ConstR = dyn_cast<Constant>(Val: R); |
872 | if (ConstL && ConstR) { |
873 | if (L == R) |
874 | return 0; |
875 | return cmpConstants(L: ConstL, R: ConstR); |
876 | } |
877 | |
878 | if (ConstL) |
879 | return 1; |
880 | if (ConstR) |
881 | return -1; |
882 | |
883 | const MetadataAsValue *MetadataValueL = dyn_cast<MetadataAsValue>(Val: L); |
884 | const MetadataAsValue *MetadataValueR = dyn_cast<MetadataAsValue>(Val: R); |
885 | if (MetadataValueL && MetadataValueR) { |
886 | if (MetadataValueL == MetadataValueR) |
887 | return 0; |
888 | |
889 | return cmpMetadata(L: MetadataValueL->getMetadata(), |
890 | R: MetadataValueR->getMetadata()); |
891 | } |
892 | |
893 | if (MetadataValueL) |
894 | return 1; |
895 | if (MetadataValueR) |
896 | return -1; |
897 | |
898 | const InlineAsm *InlineAsmL = dyn_cast<InlineAsm>(Val: L); |
899 | const InlineAsm *InlineAsmR = dyn_cast<InlineAsm>(Val: R); |
900 | |
901 | if (InlineAsmL && InlineAsmR) |
902 | return cmpInlineAsm(L: InlineAsmL, R: InlineAsmR); |
903 | if (InlineAsmL) |
904 | return 1; |
905 | if (InlineAsmR) |
906 | return -1; |
907 | |
908 | auto LeftSN = sn_mapL.insert(KV: std::make_pair(x&: L, y: sn_mapL.size())), |
909 | RightSN = sn_mapR.insert(KV: std::make_pair(x&: R, y: sn_mapR.size())); |
910 | |
911 | return cmpNumbers(L: LeftSN.first->second, R: RightSN.first->second); |
912 | } |
913 | |
914 | // Test whether two basic blocks have equivalent behaviour. |
915 | int FunctionComparator::cmpBasicBlocks(const BasicBlock *BBL, |
916 | const BasicBlock *BBR) const { |
917 | BasicBlock::const_iterator InstL = BBL->begin(), InstLE = BBL->end(); |
918 | BasicBlock::const_iterator InstR = BBR->begin(), InstRE = BBR->end(); |
919 | |
920 | do { |
921 | bool needToCmpOperands = true; |
922 | if (int Res = cmpOperations(L: &*InstL, R: &*InstR, needToCmpOperands)) |
923 | return Res; |
924 | if (needToCmpOperands) { |
925 | assert(InstL->getNumOperands() == InstR->getNumOperands()); |
926 | |
927 | for (unsigned i = 0, e = InstL->getNumOperands(); i != e; ++i) { |
928 | Value *OpL = InstL->getOperand(i); |
929 | Value *OpR = InstR->getOperand(i); |
930 | if (int Res = cmpValues(L: OpL, R: OpR)) |
931 | return Res; |
932 | // cmpValues should ensure this is true. |
933 | assert(cmpTypes(OpL->getType(), OpR->getType()) == 0); |
934 | } |
935 | } |
936 | |
937 | ++InstL; |
938 | ++InstR; |
939 | } while (InstL != InstLE && InstR != InstRE); |
940 | |
941 | if (InstL != InstLE && InstR == InstRE) |
942 | return 1; |
943 | if (InstL == InstLE && InstR != InstRE) |
944 | return -1; |
945 | return 0; |
946 | } |
947 | |
948 | int FunctionComparator::compareSignature() const { |
949 | if (int Res = cmpAttrs(L: FnL->getAttributes(), R: FnR->getAttributes())) |
950 | return Res; |
951 | |
952 | if (int Res = cmpNumbers(L: FnL->hasGC(), R: FnR->hasGC())) |
953 | return Res; |
954 | |
955 | if (FnL->hasGC()) { |
956 | if (int Res = cmpMem(L: FnL->getGC(), R: FnR->getGC())) |
957 | return Res; |
958 | } |
959 | |
960 | if (int Res = cmpNumbers(L: FnL->hasSection(), R: FnR->hasSection())) |
961 | return Res; |
962 | |
963 | if (FnL->hasSection()) { |
964 | if (int Res = cmpMem(L: FnL->getSection(), R: FnR->getSection())) |
965 | return Res; |
966 | } |
967 | |
968 | if (int Res = cmpNumbers(L: FnL->isVarArg(), R: FnR->isVarArg())) |
969 | return Res; |
970 | |
971 | // TODO: if it's internal and only used in direct calls, we could handle this |
972 | // case too. |
973 | if (int Res = cmpNumbers(L: FnL->getCallingConv(), R: FnR->getCallingConv())) |
974 | return Res; |
975 | |
976 | if (int Res = cmpTypes(TyL: FnL->getFunctionType(), TyR: FnR->getFunctionType())) |
977 | return Res; |
978 | |
979 | assert(FnL->arg_size() == FnR->arg_size() && |
980 | "Identically typed functions have different numbers of args!" ); |
981 | |
982 | // Visit the arguments so that they get enumerated in the order they're |
983 | // passed in. |
984 | for (Function::const_arg_iterator ArgLI = FnL->arg_begin(), |
985 | ArgRI = FnR->arg_begin(), |
986 | ArgLE = FnL->arg_end(); |
987 | ArgLI != ArgLE; ++ArgLI, ++ArgRI) { |
988 | if (cmpValues(L: &*ArgLI, R: &*ArgRI) != 0) |
989 | llvm_unreachable("Arguments repeat!" ); |
990 | } |
991 | return 0; |
992 | } |
993 | |
994 | // Test whether the two functions have equivalent behaviour. |
995 | int FunctionComparator::compare() { |
996 | beginCompare(); |
997 | |
998 | if (int Res = compareSignature()) |
999 | return Res; |
1000 | |
1001 | // We do a CFG-ordered walk since the actual ordering of the blocks in the |
1002 | // linked list is immaterial. Our walk starts at the entry block for both |
1003 | // functions, then takes each block from each terminator in order. As an |
1004 | // artifact, this also means that unreachable blocks are ignored. |
1005 | SmallVector<const BasicBlock *, 8> FnLBBs, FnRBBs; |
1006 | SmallPtrSet<const BasicBlock *, 32> VisitedBBs; // in terms of F1. |
1007 | |
1008 | FnLBBs.push_back(Elt: &FnL->getEntryBlock()); |
1009 | FnRBBs.push_back(Elt: &FnR->getEntryBlock()); |
1010 | |
1011 | VisitedBBs.insert(Ptr: FnLBBs[0]); |
1012 | while (!FnLBBs.empty()) { |
1013 | const BasicBlock *BBL = FnLBBs.pop_back_val(); |
1014 | const BasicBlock *BBR = FnRBBs.pop_back_val(); |
1015 | |
1016 | if (int Res = cmpValues(L: BBL, R: BBR)) |
1017 | return Res; |
1018 | |
1019 | if (int Res = cmpBasicBlocks(BBL, BBR)) |
1020 | return Res; |
1021 | |
1022 | const Instruction *TermL = BBL->getTerminator(); |
1023 | const Instruction *TermR = BBR->getTerminator(); |
1024 | |
1025 | assert(TermL->getNumSuccessors() == TermR->getNumSuccessors()); |
1026 | for (unsigned i = 0, e = TermL->getNumSuccessors(); i != e; ++i) { |
1027 | if (!VisitedBBs.insert(Ptr: TermL->getSuccessor(Idx: i)).second) |
1028 | continue; |
1029 | |
1030 | FnLBBs.push_back(Elt: TermL->getSuccessor(Idx: i)); |
1031 | FnRBBs.push_back(Elt: TermR->getSuccessor(Idx: i)); |
1032 | } |
1033 | } |
1034 | return 0; |
1035 | } |
1036 | |