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