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 const ConstantRange &LCR = LA.getRange();
152 const 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 (auto *GEPL = dyn_cast<GEPOperator>(Val: LE)) {
432 auto *GEPR = cast<GEPOperator>(Val: RE);
433 if (int Res = cmpTypes(TyL: GEPL->getSourceElementType(),
434 TyR: GEPR->getSourceElementType()))
435 return Res;
436 if (int Res = cmpNumbers(L: GEPL->getNoWrapFlags().getRaw(),
437 R: GEPR->getNoWrapFlags().getRaw()))
438 return Res;
439
440 std::optional<ConstantRange> InRangeL = GEPL->getInRange();
441 std::optional<ConstantRange> InRangeR = GEPR->getInRange();
442 if (InRangeL) {
443 if (!InRangeR)
444 return 1;
445 if (int Res = cmpAPInts(L: InRangeL->getLower(), R: InRangeR->getLower()))
446 return Res;
447 if (int Res = cmpAPInts(L: InRangeL->getUpper(), R: InRangeR->getUpper()))
448 return Res;
449 } else if (InRangeR) {
450 return -1;
451 }
452 }
453 if (auto *OBOL = dyn_cast<OverflowingBinaryOperator>(Val: LE)) {
454 auto *OBOR = cast<OverflowingBinaryOperator>(Val: RE);
455 if (int Res =
456 cmpNumbers(L: OBOL->hasNoUnsignedWrap(), R: OBOR->hasNoUnsignedWrap()))
457 return Res;
458 if (int Res =
459 cmpNumbers(L: OBOL->hasNoSignedWrap(), R: OBOR->hasNoSignedWrap()))
460 return Res;
461 }
462 return 0;
463 }
464 case Value::BlockAddressVal: {
465 const BlockAddress *LBA = cast<BlockAddress>(Val: L);
466 const BlockAddress *RBA = cast<BlockAddress>(Val: R);
467 if (int Res = cmpValues(L: LBA->getFunction(), R: RBA->getFunction()))
468 return Res;
469 if (LBA->getFunction() == RBA->getFunction()) {
470 // They are BBs in the same function. Order by which comes first in the
471 // BB order of the function. This order is deterministic.
472 Function *F = LBA->getFunction();
473 BasicBlock *LBB = LBA->getBasicBlock();
474 BasicBlock *RBB = RBA->getBasicBlock();
475 if (LBB == RBB)
476 return 0;
477 for (BasicBlock &BB : *F) {
478 if (&BB == LBB) {
479 assert(&BB != RBB);
480 return -1;
481 }
482 if (&BB == RBB)
483 return 1;
484 }
485 llvm_unreachable("Basic Block Address does not point to a basic block in "
486 "its function.");
487 return -1;
488 } else {
489 // cmpValues said the functions are the same. So because they aren't
490 // literally the same pointer, they must respectively be the left and
491 // right functions.
492 assert(LBA->getFunction() == FnL && RBA->getFunction() == FnR);
493 // cmpValues will tell us if these are equivalent BasicBlocks, in the
494 // context of their respective functions.
495 return cmpValues(L: LBA->getBasicBlock(), R: RBA->getBasicBlock());
496 }
497 }
498 case Value::DSOLocalEquivalentVal: {
499 // dso_local_equivalent is functionally equivalent to whatever it points to.
500 // This means the behavior of the IR should be the exact same as if the
501 // function was referenced directly rather than through a
502 // dso_local_equivalent.
503 const auto *LEquiv = cast<DSOLocalEquivalent>(Val: L);
504 const auto *REquiv = cast<DSOLocalEquivalent>(Val: R);
505 return cmpGlobalValues(L: LEquiv->getGlobalValue(), R: REquiv->getGlobalValue());
506 }
507 default: // Unknown constant, abort.
508 LLVM_DEBUG(dbgs() << "Looking at valueID " << L->getValueID() << "\n");
509 llvm_unreachable("Constant ValueID not recognized.");
510 return -1;
511 }
512}
513
514int FunctionComparator::cmpGlobalValues(GlobalValue *L, GlobalValue *R) const {
515 uint64_t LNumber = GlobalNumbers->getNumber(Global: L);
516 uint64_t RNumber = GlobalNumbers->getNumber(Global: R);
517 return cmpNumbers(L: LNumber, R: RNumber);
518}
519
520/// cmpType - compares two types,
521/// defines total ordering among the types set.
522/// See method declaration comments for more details.
523int FunctionComparator::cmpTypes(Type *TyL, Type *TyR) const {
524 PointerType *PTyL = dyn_cast<PointerType>(Val: TyL);
525 PointerType *PTyR = dyn_cast<PointerType>(Val: TyR);
526
527 const DataLayout &DL = FnL->getDataLayout();
528 if (PTyL && PTyL->getAddressSpace() == 0)
529 TyL = DL.getIntPtrType(TyL);
530 if (PTyR && PTyR->getAddressSpace() == 0)
531 TyR = DL.getIntPtrType(TyR);
532
533 if (TyL == TyR)
534 return 0;
535
536 if (int Res = cmpNumbers(L: TyL->getTypeID(), R: TyR->getTypeID()))
537 return Res;
538
539 switch (TyL->getTypeID()) {
540 default:
541 llvm_unreachable("Unknown type!");
542 case Type::IntegerTyID:
543 return cmpNumbers(L: cast<IntegerType>(Val: TyL)->getBitWidth(),
544 R: cast<IntegerType>(Val: TyR)->getBitWidth());
545 // TyL == TyR would have returned true earlier, because types are uniqued.
546 case Type::VoidTyID:
547 case Type::FloatTyID:
548 case Type::DoubleTyID:
549 case Type::X86_FP80TyID:
550 case Type::FP128TyID:
551 case Type::PPC_FP128TyID:
552 case Type::LabelTyID:
553 case Type::MetadataTyID:
554 case Type::TokenTyID:
555 return 0;
556
557 case Type::PointerTyID:
558 assert(PTyL && PTyR && "Both types must be pointers here.");
559 return cmpNumbers(L: PTyL->getAddressSpace(), R: PTyR->getAddressSpace());
560
561 case Type::StructTyID: {
562 StructType *STyL = cast<StructType>(Val: TyL);
563 StructType *STyR = cast<StructType>(Val: TyR);
564 if (STyL->getNumElements() != STyR->getNumElements())
565 return cmpNumbers(L: STyL->getNumElements(), R: STyR->getNumElements());
566
567 if (STyL->isPacked() != STyR->isPacked())
568 return cmpNumbers(L: STyL->isPacked(), R: STyR->isPacked());
569
570 for (unsigned i = 0, e = STyL->getNumElements(); i != e; ++i) {
571 if (int Res = cmpTypes(TyL: STyL->getElementType(N: i), TyR: STyR->getElementType(N: i)))
572 return Res;
573 }
574 return 0;
575 }
576
577 case Type::FunctionTyID: {
578 FunctionType *FTyL = cast<FunctionType>(Val: TyL);
579 FunctionType *FTyR = cast<FunctionType>(Val: TyR);
580 if (FTyL->getNumParams() != FTyR->getNumParams())
581 return cmpNumbers(L: FTyL->getNumParams(), R: FTyR->getNumParams());
582
583 if (FTyL->isVarArg() != FTyR->isVarArg())
584 return cmpNumbers(L: FTyL->isVarArg(), R: FTyR->isVarArg());
585
586 if (int Res = cmpTypes(TyL: FTyL->getReturnType(), TyR: FTyR->getReturnType()))
587 return Res;
588
589 for (unsigned i = 0, e = FTyL->getNumParams(); i != e; ++i) {
590 if (int Res = cmpTypes(TyL: FTyL->getParamType(i), TyR: FTyR->getParamType(i)))
591 return Res;
592 }
593 return 0;
594 }
595
596 case Type::ArrayTyID: {
597 auto *STyL = cast<ArrayType>(Val: TyL);
598 auto *STyR = cast<ArrayType>(Val: TyR);
599 if (STyL->getNumElements() != STyR->getNumElements())
600 return cmpNumbers(L: STyL->getNumElements(), R: STyR->getNumElements());
601 return cmpTypes(TyL: STyL->getElementType(), TyR: STyR->getElementType());
602 }
603 case Type::FixedVectorTyID:
604 case Type::ScalableVectorTyID: {
605 auto *STyL = cast<VectorType>(Val: TyL);
606 auto *STyR = cast<VectorType>(Val: TyR);
607 if (STyL->getElementCount().isScalable() !=
608 STyR->getElementCount().isScalable())
609 return cmpNumbers(L: STyL->getElementCount().isScalable(),
610 R: STyR->getElementCount().isScalable());
611 if (STyL->getElementCount() != STyR->getElementCount())
612 return cmpNumbers(L: STyL->getElementCount().getKnownMinValue(),
613 R: STyR->getElementCount().getKnownMinValue());
614 return cmpTypes(TyL: STyL->getElementType(), TyR: STyR->getElementType());
615 }
616 }
617}
618
619// Determine whether the two operations are the same except that pointer-to-A
620// and pointer-to-B are equivalent. This should be kept in sync with
621// Instruction::isSameOperationAs.
622// Read method declaration comments for more details.
623int FunctionComparator::cmpOperations(const Instruction *L,
624 const Instruction *R,
625 bool &needToCmpOperands) const {
626 needToCmpOperands = true;
627 if (int Res = cmpValues(L, R))
628 return Res;
629
630 // Differences from Instruction::isSameOperationAs:
631 // * replace type comparison with calls to cmpTypes.
632 // * we test for I->getRawSubclassOptionalData (nuw/nsw/tail) at the top.
633 // * because of the above, we don't test for the tail bit on calls later on.
634 if (int Res = cmpNumbers(L: L->getOpcode(), R: R->getOpcode()))
635 return Res;
636
637 if (const GetElementPtrInst *GEPL = dyn_cast<GetElementPtrInst>(Val: L)) {
638 needToCmpOperands = false;
639 const GetElementPtrInst *GEPR = cast<GetElementPtrInst>(Val: R);
640 if (int Res =
641 cmpValues(L: GEPL->getPointerOperand(), R: GEPR->getPointerOperand()))
642 return Res;
643 return cmpGEPs(GEPL, GEPR);
644 }
645
646 if (int Res = cmpNumbers(L: L->getNumOperands(), R: R->getNumOperands()))
647 return Res;
648
649 if (int Res = cmpTypes(TyL: L->getType(), TyR: R->getType()))
650 return Res;
651
652 if (int Res = cmpNumbers(L: L->getRawSubclassOptionalData(),
653 R: R->getRawSubclassOptionalData()))
654 return Res;
655
656 // We have two instructions of identical opcode and #operands. Check to see
657 // if all operands are the same type
658 for (unsigned i = 0, e = L->getNumOperands(); i != e; ++i) {
659 if (int Res =
660 cmpTypes(TyL: L->getOperand(i)->getType(), TyR: R->getOperand(i)->getType()))
661 return Res;
662 }
663
664 // Check special state that is a part of some instructions.
665 if (const AllocaInst *AI = dyn_cast<AllocaInst>(Val: L)) {
666 if (int Res = cmpTypes(TyL: AI->getAllocatedType(),
667 TyR: cast<AllocaInst>(Val: R)->getAllocatedType()))
668 return Res;
669 return cmpAligns(L: AI->getAlign(), R: cast<AllocaInst>(Val: R)->getAlign());
670 }
671 if (const LoadInst *LI = dyn_cast<LoadInst>(Val: L)) {
672 if (int Res = cmpNumbers(L: LI->isVolatile(), R: cast<LoadInst>(Val: R)->isVolatile()))
673 return Res;
674 if (int Res = cmpAligns(L: LI->getAlign(), R: cast<LoadInst>(Val: R)->getAlign()))
675 return Res;
676 if (int Res =
677 cmpOrderings(L: LI->getOrdering(), R: cast<LoadInst>(Val: R)->getOrdering()))
678 return Res;
679 if (int Res = cmpNumbers(L: LI->getSyncScopeID(),
680 R: cast<LoadInst>(Val: R)->getSyncScopeID()))
681 return Res;
682 return cmpInstMetadata(L, R);
683 }
684 if (const StoreInst *SI = dyn_cast<StoreInst>(Val: L)) {
685 if (int Res =
686 cmpNumbers(L: SI->isVolatile(), R: cast<StoreInst>(Val: R)->isVolatile()))
687 return Res;
688 if (int Res = cmpAligns(L: SI->getAlign(), R: cast<StoreInst>(Val: R)->getAlign()))
689 return Res;
690 if (int Res =
691 cmpOrderings(L: SI->getOrdering(), R: cast<StoreInst>(Val: R)->getOrdering()))
692 return Res;
693 return cmpNumbers(L: SI->getSyncScopeID(),
694 R: cast<StoreInst>(Val: R)->getSyncScopeID());
695 }
696 if (const CmpInst *CI = dyn_cast<CmpInst>(Val: L))
697 return cmpNumbers(L: CI->getPredicate(), R: cast<CmpInst>(Val: R)->getPredicate());
698 if (auto *CBL = dyn_cast<CallBase>(Val: L)) {
699 auto *CBR = cast<CallBase>(Val: R);
700 if (int Res = cmpNumbers(L: CBL->getCallingConv(), R: CBR->getCallingConv()))
701 return Res;
702 if (int Res = cmpAttrs(L: CBL->getAttributes(), R: CBR->getAttributes()))
703 return Res;
704 if (int Res = cmpOperandBundlesSchema(LCS: *CBL, RCS: *CBR))
705 return Res;
706 if (const CallInst *CI = dyn_cast<CallInst>(Val: L))
707 if (int Res = cmpNumbers(L: CI->getTailCallKind(),
708 R: cast<CallInst>(Val: R)->getTailCallKind()))
709 return Res;
710 return cmpMDNode(L: L->getMetadata(KindID: LLVMContext::MD_range),
711 R: R->getMetadata(KindID: LLVMContext::MD_range));
712 }
713 if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Val: L)) {
714 ArrayRef<unsigned> LIndices = IVI->getIndices();
715 ArrayRef<unsigned> RIndices = cast<InsertValueInst>(Val: R)->getIndices();
716 if (int Res = cmpNumbers(L: LIndices.size(), R: RIndices.size()))
717 return Res;
718 for (size_t i = 0, e = LIndices.size(); i != e; ++i) {
719 if (int Res = cmpNumbers(L: LIndices[i], R: RIndices[i]))
720 return Res;
721 }
722 return 0;
723 }
724 if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Val: L)) {
725 ArrayRef<unsigned> LIndices = EVI->getIndices();
726 ArrayRef<unsigned> RIndices = cast<ExtractValueInst>(Val: R)->getIndices();
727 if (int Res = cmpNumbers(L: LIndices.size(), R: RIndices.size()))
728 return Res;
729 for (size_t i = 0, e = LIndices.size(); i != e; ++i) {
730 if (int Res = cmpNumbers(L: LIndices[i], R: RIndices[i]))
731 return Res;
732 }
733 }
734 if (const FenceInst *FI = dyn_cast<FenceInst>(Val: L)) {
735 if (int Res =
736 cmpOrderings(L: FI->getOrdering(), R: cast<FenceInst>(Val: R)->getOrdering()))
737 return Res;
738 return cmpNumbers(L: FI->getSyncScopeID(),
739 R: cast<FenceInst>(Val: R)->getSyncScopeID());
740 }
741 if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(Val: L)) {
742 if (int Res = cmpNumbers(L: CXI->isVolatile(),
743 R: cast<AtomicCmpXchgInst>(Val: R)->isVolatile()))
744 return Res;
745 if (int Res =
746 cmpNumbers(L: CXI->isWeak(), R: cast<AtomicCmpXchgInst>(Val: R)->isWeak()))
747 return Res;
748 if (int Res =
749 cmpOrderings(L: CXI->getSuccessOrdering(),
750 R: cast<AtomicCmpXchgInst>(Val: R)->getSuccessOrdering()))
751 return Res;
752 if (int Res =
753 cmpOrderings(L: CXI->getFailureOrdering(),
754 R: cast<AtomicCmpXchgInst>(Val: R)->getFailureOrdering()))
755 return Res;
756 return cmpNumbers(L: CXI->getSyncScopeID(),
757 R: cast<AtomicCmpXchgInst>(Val: R)->getSyncScopeID());
758 }
759 if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(Val: L)) {
760 if (int Res = cmpNumbers(L: RMWI->getOperation(),
761 R: cast<AtomicRMWInst>(Val: R)->getOperation()))
762 return Res;
763 if (int Res = cmpNumbers(L: RMWI->isVolatile(),
764 R: cast<AtomicRMWInst>(Val: R)->isVolatile()))
765 return Res;
766 if (int Res = cmpOrderings(L: RMWI->getOrdering(),
767 R: cast<AtomicRMWInst>(Val: R)->getOrdering()))
768 return Res;
769 return cmpNumbers(L: RMWI->getSyncScopeID(),
770 R: cast<AtomicRMWInst>(Val: R)->getSyncScopeID());
771 }
772 if (const ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(Val: L)) {
773 ArrayRef<int> LMask = SVI->getShuffleMask();
774 ArrayRef<int> RMask = cast<ShuffleVectorInst>(Val: R)->getShuffleMask();
775 if (int Res = cmpNumbers(L: LMask.size(), R: RMask.size()))
776 return Res;
777 for (size_t i = 0, e = LMask.size(); i != e; ++i) {
778 if (int Res = cmpNumbers(L: LMask[i], R: RMask[i]))
779 return Res;
780 }
781 }
782 if (const PHINode *PNL = dyn_cast<PHINode>(Val: L)) {
783 const PHINode *PNR = cast<PHINode>(Val: R);
784 // Ensure that in addition to the incoming values being identical
785 // (checked by the caller of this function), the incoming blocks
786 // are also identical.
787 for (unsigned i = 0, e = PNL->getNumIncomingValues(); i != e; ++i) {
788 if (int Res =
789 cmpValues(L: PNL->getIncomingBlock(i), R: PNR->getIncomingBlock(i)))
790 return Res;
791 }
792 }
793 return 0;
794}
795
796// Determine whether two GEP operations perform the same underlying arithmetic.
797// Read method declaration comments for more details.
798int FunctionComparator::cmpGEPs(const GEPOperator *GEPL,
799 const GEPOperator *GEPR) const {
800 unsigned int ASL = GEPL->getPointerAddressSpace();
801 unsigned int ASR = GEPR->getPointerAddressSpace();
802
803 if (int Res = cmpNumbers(L: ASL, R: ASR))
804 return Res;
805
806 // When we have target data, we can reduce the GEP down to the value in bytes
807 // added to the address.
808 const DataLayout &DL = FnL->getDataLayout();
809 unsigned OffsetBitWidth = DL.getIndexSizeInBits(AS: ASL);
810 APInt OffsetL(OffsetBitWidth, 0), OffsetR(OffsetBitWidth, 0);
811 if (GEPL->accumulateConstantOffset(DL, Offset&: OffsetL) &&
812 GEPR->accumulateConstantOffset(DL, Offset&: OffsetR))
813 return cmpAPInts(L: OffsetL, R: OffsetR);
814 if (int Res =
815 cmpTypes(TyL: GEPL->getSourceElementType(), TyR: GEPR->getSourceElementType()))
816 return Res;
817
818 if (int Res = cmpNumbers(L: GEPL->getNumOperands(), R: GEPR->getNumOperands()))
819 return Res;
820
821 for (unsigned i = 0, e = GEPL->getNumOperands(); i != e; ++i) {
822 if (int Res = cmpValues(L: GEPL->getOperand(i_nocapture: i), R: GEPR->getOperand(i_nocapture: i)))
823 return Res;
824 }
825
826 return 0;
827}
828
829int FunctionComparator::cmpInlineAsm(const InlineAsm *L,
830 const InlineAsm *R) const {
831 // InlineAsm's are uniqued. If they are the same pointer, obviously they are
832 // the same, otherwise compare the fields.
833 if (L == R)
834 return 0;
835 if (int Res = cmpTypes(TyL: L->getFunctionType(), TyR: R->getFunctionType()))
836 return Res;
837 if (int Res = cmpMem(L: L->getAsmString(), R: R->getAsmString()))
838 return Res;
839 if (int Res = cmpMem(L: L->getConstraintString(), R: R->getConstraintString()))
840 return Res;
841 if (int Res = cmpNumbers(L: L->hasSideEffects(), R: R->hasSideEffects()))
842 return Res;
843 if (int Res = cmpNumbers(L: L->isAlignStack(), R: R->isAlignStack()))
844 return Res;
845 if (int Res = cmpNumbers(L: L->getDialect(), R: R->getDialect()))
846 return Res;
847 assert(L->getFunctionType() != R->getFunctionType());
848 return 0;
849}
850
851/// Compare two values used by the two functions under pair-wise comparison. If
852/// this is the first time the values are seen, they're added to the mapping so
853/// that we will detect mismatches on next use.
854/// See comments in declaration for more details.
855int FunctionComparator::cmpValues(const Value *L, const Value *R) const {
856 // Catch self-reference case.
857 if (L == FnL) {
858 if (R == FnR)
859 return 0;
860 return -1;
861 }
862 if (R == FnR) {
863 if (L == FnL)
864 return 0;
865 return 1;
866 }
867
868 const Constant *ConstL = dyn_cast<Constant>(Val: L);
869 const Constant *ConstR = dyn_cast<Constant>(Val: R);
870 if (ConstL && ConstR) {
871 if (L == R)
872 return 0;
873 return cmpConstants(L: ConstL, R: ConstR);
874 }
875
876 if (ConstL)
877 return 1;
878 if (ConstR)
879 return -1;
880
881 const MetadataAsValue *MetadataValueL = dyn_cast<MetadataAsValue>(Val: L);
882 const MetadataAsValue *MetadataValueR = dyn_cast<MetadataAsValue>(Val: R);
883 if (MetadataValueL && MetadataValueR) {
884 if (MetadataValueL == MetadataValueR)
885 return 0;
886
887 return cmpMetadata(L: MetadataValueL->getMetadata(),
888 R: MetadataValueR->getMetadata());
889 }
890
891 if (MetadataValueL)
892 return 1;
893 if (MetadataValueR)
894 return -1;
895
896 const InlineAsm *InlineAsmL = dyn_cast<InlineAsm>(Val: L);
897 const InlineAsm *InlineAsmR = dyn_cast<InlineAsm>(Val: R);
898
899 if (InlineAsmL && InlineAsmR)
900 return cmpInlineAsm(L: InlineAsmL, R: InlineAsmR);
901 if (InlineAsmL)
902 return 1;
903 if (InlineAsmR)
904 return -1;
905
906 auto LeftSN = sn_mapL.insert(KV: std::make_pair(x&: L, y: sn_mapL.size())),
907 RightSN = sn_mapR.insert(KV: std::make_pair(x&: R, y: sn_mapR.size()));
908
909 return cmpNumbers(L: LeftSN.first->second, R: RightSN.first->second);
910}
911
912// Test whether two basic blocks have equivalent behaviour.
913int FunctionComparator::cmpBasicBlocks(const BasicBlock *BBL,
914 const BasicBlock *BBR) const {
915 BasicBlock::const_iterator InstL = BBL->begin(), InstLE = BBL->end();
916 BasicBlock::const_iterator InstR = BBR->begin(), InstRE = BBR->end();
917
918 do {
919 bool needToCmpOperands = true;
920 if (int Res = cmpOperations(L: &*InstL, R: &*InstR, needToCmpOperands))
921 return Res;
922 if (needToCmpOperands) {
923 assert(InstL->getNumOperands() == InstR->getNumOperands());
924
925 for (unsigned i = 0, e = InstL->getNumOperands(); i != e; ++i) {
926 Value *OpL = InstL->getOperand(i);
927 Value *OpR = InstR->getOperand(i);
928 if (int Res = cmpValues(L: OpL, R: OpR))
929 return Res;
930 // cmpValues should ensure this is true.
931 assert(cmpTypes(OpL->getType(), OpR->getType()) == 0);
932 }
933 }
934
935 ++InstL;
936 ++InstR;
937 } while (InstL != InstLE && InstR != InstRE);
938
939 if (InstL != InstLE && InstR == InstRE)
940 return 1;
941 if (InstL == InstLE && InstR != InstRE)
942 return -1;
943 return 0;
944}
945
946int FunctionComparator::compareSignature() const {
947 if (int Res = cmpAttrs(L: FnL->getAttributes(), R: FnR->getAttributes()))
948 return Res;
949
950 if (int Res = cmpNumbers(L: FnL->hasGC(), R: FnR->hasGC()))
951 return Res;
952
953 if (FnL->hasGC()) {
954 if (int Res = cmpMem(L: FnL->getGC(), R: FnR->getGC()))
955 return Res;
956 }
957
958 if (int Res = cmpNumbers(L: FnL->hasSection(), R: FnR->hasSection()))
959 return Res;
960
961 if (FnL->hasSection()) {
962 if (int Res = cmpMem(L: FnL->getSection(), R: FnR->getSection()))
963 return Res;
964 }
965
966 if (int Res = cmpNumbers(L: FnL->isVarArg(), R: FnR->isVarArg()))
967 return Res;
968
969 // TODO: if it's internal and only used in direct calls, we could handle this
970 // case too.
971 if (int Res = cmpNumbers(L: FnL->getCallingConv(), R: FnR->getCallingConv()))
972 return Res;
973
974 if (int Res = cmpTypes(TyL: FnL->getFunctionType(), TyR: FnR->getFunctionType()))
975 return Res;
976
977 assert(FnL->arg_size() == FnR->arg_size() &&
978 "Identically typed functions have different numbers of args!");
979
980 // Visit the arguments so that they get enumerated in the order they're
981 // passed in.
982 for (Function::const_arg_iterator ArgLI = FnL->arg_begin(),
983 ArgRI = FnR->arg_begin(),
984 ArgLE = FnL->arg_end();
985 ArgLI != ArgLE; ++ArgLI, ++ArgRI) {
986 if (cmpValues(L: &*ArgLI, R: &*ArgRI) != 0)
987 llvm_unreachable("Arguments repeat!");
988 }
989 return 0;
990}
991
992// Test whether the two functions have equivalent behaviour.
993int FunctionComparator::compare() {
994 beginCompare();
995
996 if (int Res = compareSignature())
997 return Res;
998
999 // We do a CFG-ordered walk since the actual ordering of the blocks in the
1000 // linked list is immaterial. Our walk starts at the entry block for both
1001 // functions, then takes each block from each terminator in order. As an
1002 // artifact, this also means that unreachable blocks are ignored.
1003 SmallVector<const BasicBlock *, 8> FnLBBs, FnRBBs;
1004 SmallPtrSet<const BasicBlock *, 32> VisitedBBs; // in terms of F1.
1005
1006 FnLBBs.push_back(Elt: &FnL->getEntryBlock());
1007 FnRBBs.push_back(Elt: &FnR->getEntryBlock());
1008
1009 VisitedBBs.insert(Ptr: FnLBBs[0]);
1010 while (!FnLBBs.empty()) {
1011 const BasicBlock *BBL = FnLBBs.pop_back_val();
1012 const BasicBlock *BBR = FnRBBs.pop_back_val();
1013
1014 if (int Res = cmpValues(L: BBL, R: BBR))
1015 return Res;
1016
1017 if (int Res = cmpBasicBlocks(BBL, BBR))
1018 return Res;
1019
1020 const Instruction *TermL = BBL->getTerminator();
1021 const Instruction *TermR = BBR->getTerminator();
1022
1023 assert(TermL->getNumSuccessors() == TermR->getNumSuccessors());
1024 for (unsigned i = 0, e = TermL->getNumSuccessors(); i != e; ++i) {
1025 if (!VisitedBBs.insert(Ptr: TermL->getSuccessor(Idx: i)).second)
1026 continue;
1027
1028 FnLBBs.push_back(Elt: TermL->getSuccessor(Idx: i));
1029 FnRBBs.push_back(Elt: TermR->getSuccessor(Idx: i));
1030 }
1031 }
1032 return 0;
1033}
1034