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