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