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
49using namespace llvm;
50
51#define DEBUG_TYPE "functioncomparator"
52
53int 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
61int 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
69int 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
77int 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
87int 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
106int 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
116int 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
172int 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
203int 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
224int 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
247int 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.
274int 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
516int 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.
525int 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.
625int 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.
800int 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
831int 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.
857int 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.
915int 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
948int 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.
995int 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

source code of llvm/lib/Transforms/Utils/FunctionComparator.cpp