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