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