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