From 0885a28635557e4154aad0f8ebf3be571736a962 Mon Sep 17 00:00:00 2001 From: Stepan Dyatkovskiy Date: Fri, 16 May 2014 11:02:22 +0000 Subject: MergeFunctions Pass, introduced total ordering among operations. Patch replaces old isEquivalentOperation implementation, and changes type of comparison result from bool (equal or not) to {-1, 0, 1} (less, equal, greater). This patch belongs to patch series that improves MergeFunctions performance time from O(N*N) to O(N*log(N)). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@208973 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/IPO/MergeFunctions.cpp | 185 +++++++++++++++++++++++++--------- 1 file changed, 135 insertions(+), 50 deletions(-) (limited to 'lib/Transforms/IPO/MergeFunctions.cpp') diff --git a/lib/Transforms/IPO/MergeFunctions.cpp b/lib/Transforms/IPO/MergeFunctions.cpp index 55d199ee7b..60ef2b6267 100644 --- a/lib/Transforms/IPO/MergeFunctions.cpp +++ b/lib/Transforms/IPO/MergeFunctions.cpp @@ -307,8 +307,32 @@ private: /// Compare two Instructions for equivalence, similar to /// Instruction::isSameOperationAs but with modifications to the type /// comparison. + /// Stages are listed in "most significant stage first" order: + /// On each stage below, we do comparison between some left and right + /// operation parts. If parts are non-equal, we assign parts comparison + /// result to the operation comparison result and exit from method. + /// Otherwise we proceed to the next stage. + /// Stages: + /// 1. Operations opcodes. Compared as numbers. + /// 2. Number of operands. + /// 3. Operation types. Compared with cmpType method. + /// 4. Compare operation subclass optional data as stream of bytes: + /// just convert it to integers and call cmpNumbers. + /// 5. Compare in operation operand types with cmpType in + /// most significant operand first order. + /// 6. Last stage. Check operations for some specific attributes. + /// For example, for Load it would be: + /// 6.1.Load: volatile (as boolean flag) + /// 6.2.Load: alignment (as integer numbers) + /// 6.3.Load: synch-scope (as integer numbers) + /// On this stage its better to see the code, since its not more than 10-15 + /// strings for particular instruction, and could change sometimes. + int cmpOperation(const Instruction *L, const Instruction *R) const; + bool isEquivalentOperation(const Instruction *I1, - const Instruction *I2) const; + const Instruction *I2) const { + return cmpOperation(I1, I2) == 0; + } /// Compare two GEPs for equivalent pointer arithmetic. bool isEquivalentGEP(const GEPOperator *GEP1, const GEPOperator *GEP2); @@ -711,65 +735,126 @@ int FunctionComparator::cmpType(Type *TyL, Type *TyR) const { // Determine whether the two operations are the same except that pointer-to-A // and pointer-to-B are equivalent. This should be kept in sync with // Instruction::isSameOperationAs. -bool FunctionComparator::isEquivalentOperation(const Instruction *I1, - const Instruction *I2) const { +// Read method declaration comments for more details. +int FunctionComparator::cmpOperation(const Instruction *L, + const Instruction *R) const { // Differences from Instruction::isSameOperationAs: // * replace type comparison with calls to isEquivalentType. // * we test for I->hasSameSubclassOptionalData (nuw/nsw/tail) at the top // * because of the above, we don't test for the tail bit on calls later on - if (I1->getOpcode() != I2->getOpcode() || - I1->getNumOperands() != I2->getNumOperands() || - !isEquivalentType(I1->getType(), I2->getType()) || - !I1->hasSameSubclassOptionalData(I2)) - return false; + if (int Res = cmpNumbers(L->getOpcode(), R->getOpcode())) + return Res; + + if (int Res = cmpNumbers(L->getNumOperands(), R->getNumOperands())) + return Res; + + if (int Res = cmpType(L->getType(), R->getType())) + return Res; + + if (int Res = cmpNumbers(L->getRawSubclassOptionalData(), + R->getRawSubclassOptionalData())) + return Res; // We have two instructions of identical opcode and #operands. Check to see // if all operands are the same type - for (unsigned i = 0, e = I1->getNumOperands(); i != e; ++i) - if (!isEquivalentType(I1->getOperand(i)->getType(), - I2->getOperand(i)->getType())) - return false; + for (unsigned i = 0, e = L->getNumOperands(); i != e; ++i) { + if (int Res = + cmpType(L->getOperand(i)->getType(), R->getOperand(i)->getType())) + return Res; + } // Check special state that is a part of some instructions. - if (const LoadInst *LI = dyn_cast(I1)) - return LI->isVolatile() == cast(I2)->isVolatile() && - LI->getAlignment() == cast(I2)->getAlignment() && - LI->getOrdering() == cast(I2)->getOrdering() && - LI->getSynchScope() == cast(I2)->getSynchScope(); - if (const StoreInst *SI = dyn_cast(I1)) - return SI->isVolatile() == cast(I2)->isVolatile() && - SI->getAlignment() == cast(I2)->getAlignment() && - SI->getOrdering() == cast(I2)->getOrdering() && - SI->getSynchScope() == cast(I2)->getSynchScope(); - if (const CmpInst *CI = dyn_cast(I1)) - return CI->getPredicate() == cast(I2)->getPredicate(); - if (const CallInst *CI = dyn_cast(I1)) - return CI->getCallingConv() == cast(I2)->getCallingConv() && - CI->getAttributes() == cast(I2)->getAttributes(); - if (const InvokeInst *CI = dyn_cast(I1)) - return CI->getCallingConv() == cast(I2)->getCallingConv() && - CI->getAttributes() == cast(I2)->getAttributes(); - if (const InsertValueInst *IVI = dyn_cast(I1)) - return IVI->getIndices() == cast(I2)->getIndices(); - if (const ExtractValueInst *EVI = dyn_cast(I1)) - return EVI->getIndices() == cast(I2)->getIndices(); - if (const FenceInst *FI = dyn_cast(I1)) - return FI->getOrdering() == cast(I2)->getOrdering() && - FI->getSynchScope() == cast(I2)->getSynchScope(); - if (const AtomicCmpXchgInst *CXI = dyn_cast(I1)) - return CXI->isVolatile() == cast(I2)->isVolatile() && - CXI->getSuccessOrdering() == - cast(I2)->getSuccessOrdering() && - CXI->getFailureOrdering() == - cast(I2)->getFailureOrdering() && - CXI->getSynchScope() == cast(I2)->getSynchScope(); - if (const AtomicRMWInst *RMWI = dyn_cast(I1)) - return RMWI->getOperation() == cast(I2)->getOperation() && - RMWI->isVolatile() == cast(I2)->isVolatile() && - RMWI->getOrdering() == cast(I2)->getOrdering() && - RMWI->getSynchScope() == cast(I2)->getSynchScope(); + if (const LoadInst *LI = dyn_cast(L)) { + if (int Res = cmpNumbers(LI->isVolatile(), cast(R)->isVolatile())) + return Res; + if (int Res = + cmpNumbers(LI->getAlignment(), cast(R)->getAlignment())) + return Res; + if (int Res = + cmpNumbers(LI->getOrdering(), cast(R)->getOrdering())) + return Res; + return cmpNumbers(LI->getSynchScope(), cast(R)->getSynchScope()); + } + if (const StoreInst *SI = dyn_cast(L)) { + if (int Res = + cmpNumbers(SI->isVolatile(), cast(R)->isVolatile())) + return Res; + if (int Res = + cmpNumbers(SI->getAlignment(), cast(R)->getAlignment())) + return Res; + if (int Res = + cmpNumbers(SI->getOrdering(), cast(R)->getOrdering())) + return Res; + return cmpNumbers(SI->getSynchScope(), cast(R)->getSynchScope()); + } + if (const CmpInst *CI = dyn_cast(L)) + return cmpNumbers(CI->getPredicate(), cast(R)->getPredicate()); + if (const CallInst *CI = dyn_cast(L)) { + if (int Res = cmpNumbers(CI->getCallingConv(), + cast(R)->getCallingConv())) + return Res; + return cmpAttrs(CI->getAttributes(), cast(R)->getAttributes()); + } + if (const InvokeInst *CI = dyn_cast(L)) { + if (int Res = cmpNumbers(CI->getCallingConv(), + cast(R)->getCallingConv())) + return Res; + return cmpAttrs(CI->getAttributes(), cast(R)->getAttributes()); + } + if (const InsertValueInst *IVI = dyn_cast(L)) { + ArrayRef LIndices = IVI->getIndices(); + ArrayRef RIndices = cast(R)->getIndices(); + if (int Res = cmpNumbers(LIndices.size(), RIndices.size())) + return Res; + for (size_t i = 0, e = LIndices.size(); i != e; ++i) { + if (int Res = cmpNumbers(LIndices[i], RIndices[i])) + return Res; + } + } + if (const ExtractValueInst *EVI = dyn_cast(L)) { + ArrayRef LIndices = EVI->getIndices(); + ArrayRef RIndices = cast(R)->getIndices(); + if (int Res = cmpNumbers(LIndices.size(), RIndices.size())) + return Res; + for (size_t i = 0, e = LIndices.size(); i != e; ++i) { + if (int Res = cmpNumbers(LIndices[i], RIndices[i])) + return Res; + } + } + if (const FenceInst *FI = dyn_cast(L)) { + if (int Res = + cmpNumbers(FI->getOrdering(), cast(R)->getOrdering())) + return Res; + return cmpNumbers(FI->getSynchScope(), cast(R)->getSynchScope()); + } - return true; + if (const AtomicCmpXchgInst *CXI = dyn_cast(L)) { + if (int Res = cmpNumbers(CXI->isVolatile(), + cast(R)->isVolatile())) + return Res; + if (int Res = cmpNumbers(CXI->getSuccessOrdering(), + cast(R)->getSuccessOrdering())) + return Res; + if (int Res = cmpNumbers(CXI->getFailureOrdering(), + cast(R)->getFailureOrdering())) + return Res; + return cmpNumbers(CXI->getSynchScope(), + cast(R)->getSynchScope()); + } + if (const AtomicRMWInst *RMWI = dyn_cast(L)) { + if (int Res = cmpNumbers(RMWI->getOperation(), + cast(R)->getOperation())) + return Res; + if (int Res = cmpNumbers(RMWI->isVolatile(), + cast(R)->isVolatile())) + return Res; + if (int Res = cmpNumbers(RMWI->getOrdering(), + cast(R)->getOrdering())) + return Res; + return cmpNumbers(RMWI->getSynchScope(), + cast(R)->getSynchScope()); + } + return 0; } // Determine whether two GEP operations perform the same underlying arithmetic. -- cgit v1.2.3