llvm/lib/Transforms/Utils/FunctionComparator.cpp

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