1048 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the FunctionComparator and GlobalNumberState classes10// 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 48using namespace llvm;49 50#define DEBUG_TYPE "functioncomparator"51 52int 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 60int 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 68int 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 76int 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 86int 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 93int 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 112int 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 when118 // strings are equal in size.119 return std::clamp(L.compare(R), -1, 1);120}121 122int 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 is148 // 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 188int FunctionComparator::cmpMetadata(const Metadata *L,189 const Metadata *R) const {190 // TODO: the following routine coerce the metadata contents into constants191 // or MDStrings before comparison.192 // It ignores any other cases, so that the metadata nodes are considered193 // 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 219int 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 merge227 // this data when considering functions to merge. Thus this comparison would228 // return 0 (i.e. equivalent), but merging would become more complicated229 // because the ranges would need to be unioned. It is not likely that230 // functions differ ONLY in this metadata if they are actually the same231 // 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 240int FunctionComparator::cmpInstMetadata(Instruction const *L,241 Instruction const *R) const {242 /// These metadata affects the other optimization passes by making assertions243 /// 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 263int 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 R287/// type.288/// 2. Compare constant contents.289/// For more details see declaration comments.290int 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-factored296 // 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 result305 // of comparing the types306 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 types315 // 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 to343 // 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 we369 // compare the two raw data arrays, which might differ depending on the host370 // endianness. This isn't a problem though, because the endiness of a module371 // will affect the order of the constants, but this order is the same372 // 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 the485 // 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't504 // literally the same pointer, they must respectively be the left and505 // right functions.506 assert(LBA->getFunction() == FnL && RBA->getFunction() == FnR);507 // cmpValues will tell us if these are equivalent BasicBlocks, in the508 // 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 the515 // function was referenced directly rather than through a516 // 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 528int 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.537int 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-A634// and pointer-to-B are equivalent. This should be kept in sync with635// Instruction::isSameOperationAs.636// Read method declaration comments for more details.637int 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 see671 // if all operands are the same type672 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 identical799 // (checked by the caller of this function), the incoming blocks800 // 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.812int 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 bytes821 // 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 843int FunctionComparator::cmpInlineAsm(const InlineAsm *L,844 const InlineAsm *R) const {845 // InlineAsm's are uniqued. If they are the same pointer, obviously they are846 // 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. If866/// this is the first time the values are seen, they're added to the mapping so867/// that we will detect mismatches on next use.868/// See comments in declaration for more details.869int 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.927int 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 960int 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 this984 // 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're995 // 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.1007int 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 the1014 // linked list is immaterial. Our walk starts at the entry block for both1015 // functions, then takes each block from each terminator in order. As an1016 // 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