Index: lib/Transforms/IPO/MergeFunctions.cpp =================================================================== --- lib/Transforms/IPO/MergeFunctions.cpp +++ lib/Transforms/IPO/MergeFunctions.cpp @@ -119,7 +119,7 @@ STATISTIC(NumFunctionsMerged, "Number of functions merged"); STATISTIC(NumThunksWritten, "Number of thunks generated"); -STATISTIC(NumAliasesWritten, "Number of aliases generated"); +STATISTIC(NumThunksSkipped, "Number of thunks skipped"); STATISTIC(NumDoubleWeak, "Number of new functions created"); static cl::opt NumFunctionsForSanityCheck( @@ -144,19 +144,19 @@ /// compare those, but this would not work for stripped bitcodes or for those /// few symbols without a name. class GlobalNumberState { - struct Config : ValueMapConfig { + struct Config : ValueMapConfig { enum { FollowRAUW = false }; }; // Each GlobalValue is mapped to an identifier. The Config ensures when RAUW // occurs, the mapping does not change. Tracking changes is unnecessary, and // also problematic for weak symbols (which may be overwritten). - typedef ValueMap ValueNumberMap; + typedef ValueMap ValueNumberMap; ValueNumberMap GlobalNumbers; // The next unused serial number to assign to a global. uint64_t NextNumber; public: GlobalNumberState() : GlobalNumbers(), NextNumber(0) {} - uint64_t getNumber(GlobalValue* Global) { + uint64_t getNumber(Constant *Global) { ValueNumberMap::iterator MapIter; bool Inserted; std::tie(MapIter, Inserted) = GlobalNumbers.insert({Global, NextNumber}); @@ -178,6 +178,12 @@ /// Test whether the two functions have equivalent behaviour. int compare(); + /// Test whether the two functions are equivalent modulo callsites. + int compareStructure(); + /// Compares the callsites of the two functions. Must be called after + /// compareStructure(). + int compareDeferredCallsites(); + /// Hash a function. Equivalent functions will have the same hash, and unequal /// functions will have different hashes with high probability. typedef uint64_t FunctionHash; @@ -441,6 +447,7 @@ /// could be operands from further BBs we didn't scan yet. /// So it's impossible to use dominance properties in general. DenseMap sn_mapL, sn_mapR; + SmallVector DeferredL, DeferredR; // The global state we will use GlobalNumberState* GlobalNumbers; @@ -1119,21 +1126,31 @@ do { if (int Res = cmpValues(InstL, InstR)) return Res; + // First, order by opcode. This means that we can dispatch only on InstL. + if (int Res = cmpNumbers(InstL->getOpcode(), InstR->getOpcode())) + return Res; - const GetElementPtrInst *GEPL = dyn_cast(InstL); - const GetElementPtrInst *GEPR = dyn_cast(InstR); - - if (GEPL && !GEPR) - return 1; - if (GEPR && !GEPL) - return -1; - - if (GEPL && GEPR) { + // GEPs need special logic because the number of operands can vary in the + // case of a equivalent GEPs which lower to a constant constant offset. + // cmpOperations requires the same number of operands, so can't be used. + if (const GetElementPtrInst *GEPL = dyn_cast(InstL)) { + const GetElementPtrInst *GEPR = cast(InstR); if (int Res = cmpValues(GEPL->getPointerOperand(), GEPR->getPointerOperand())) return Res; if (int Res = cmpGEPs(GEPL, GEPR)) return Res; + } else if (const CallInst * CL = dyn_cast(InstL)) { + const CallInst * CR = cast(InstR); + if (int Res = cmpOperations(InstL, InstR)) + return Res; + assert(CL->getNumArgOperands() == CR->getNumArgOperands()); + for (unsigned i = 0, e = CL->getNumArgOperands(); i != e; ++i) { + if (int Res = cmpValues(CL->getArgOperand(i), CR->getArgOperand(i))) + return Res; + } + DeferredL.push_back(CL); + DeferredR.push_back(CR); } else { if (int Res = cmpOperations(InstL, InstR)) return Res; @@ -1160,7 +1177,7 @@ } // Test whether the two functions have equivalent behaviour. -int FunctionComparator::compare() { +int FunctionComparator::compareStructure() { sn_mapL.clear(); sn_mapR.clear(); @@ -1244,6 +1261,24 @@ return 0; } +int FunctionComparator::compareDeferredCallsites() { + assert(DeferredL.size() == DeferredR.size()); + for(size_t I = 0, E = DeferredL.size(); I < E; ++I) { + if (int Res = cmpValues(DeferredL[I]->getCalledValue(), + DeferredR[I]->getCalledValue())) + return Res; + } + return 0; +} + +int FunctionComparator::compare() { + if (int Res = compareStructure()) + return Res; + if (int Res = compareDeferredCallsites()) + return Res; + return 0; +} + // Accumulate the hash of a sequence of 64-bit integers. This is similar to a // hash of a sequence of 64bit ints, but the entire input does not need to be // available at once. This interface is necessary for functionHash because it @@ -1315,8 +1350,7 @@ public: static char ID; MergeFunctions() - : ModulePass(ID), FnTree(FunctionNodeCmp(&GlobalNumbers)), FNodesInTree(), - HasGlobalAliases(false) { + : ModulePass(ID), FnTree(FunctionNodeCmp(&GlobalNumbers)), FNodesInTree() { initializeMergeFunctionsPass(*PassRegistry::getPassRegistry()); } @@ -1365,16 +1399,20 @@ /// necessary to make types match. void replaceDirectCallers(Function *Old, Function *New); + /// Replace references to Old in bitcasts with New. + void replaceUseInConstants(Constant *Old, Constant *New); + /// Merge two equivalent functions. Upon completion, G may be deleted, or may /// be converted into a thunk. In either case, it should never be visited /// again. - void mergeTwoFunctions(Function *F, Function *G); + bool mergeTwoFunctions(const FunctionNode &FN, Function *G); - /// Replace G with a thunk or an alias to F. Deletes G. - void writeThunkOrAlias(Function *F, Function *G); + /// Merge two equivalent functions. Upon completion, G may be deleted, or may + /// be converted into a thunk. In either case, it should never be visited + /// again. + bool mergeTwoWeakFunctions(Function *F, Function *G); - /// Replace G with a simple tail call to bitcast(F). Also replace direct uses - /// of G with bitcast(F). Deletes G. + /// Replace G with a simple tail call to bitcast(F). void writeThunk(Function *F, Function *G); /// Replace G with an alias to F. Deletes G. @@ -1392,9 +1430,6 @@ // dangling iterators into FnTree. The invariant that preserves this is that // there is exactly one mapping F -> FN for each FunctionNode FN in FnTree. ValueMap FNodesInTree; - - /// Whether or not the target supports global aliases. - bool HasGlobalAliases; }; } // end anonymous namespace @@ -1517,31 +1552,13 @@ DEBUG(dbgs() << "size of module: " << M.size() << '\n'); DEBUG(dbgs() << "size of worklist: " << Worklist.size() << '\n'); - // Insert only strong functions and merge them. Strong function merging - // always deletes one of them. for (std::vector::iterator I = Worklist.begin(), E = Worklist.end(); I != E; ++I) { if (!*I) continue; Function *F = cast(*I); - if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() && - !F->mayBeOverridden()) { - Changed |= insert(F); - } + Changed |= insert(F); } - // Insert only weak functions and merge them. By doing these second we - // create thunks to the strong function when possible. When two weak - // functions are identical, we create a new strong function with two weak - // weak thunks to it which are identical but not mergable. - for (std::vector::iterator I = Worklist.begin(), - E = Worklist.end(); I != E; ++I) { - if (!*I) continue; - Function *F = cast(*I); - if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() && - F->mayBeOverridden()) { - Changed |= insert(F); - } - } DEBUG(dbgs() << "size of FnTree: " << FnTree.size() << '\n'); } while (!Deferred.empty()); @@ -1590,17 +1607,25 @@ } } -// Replace G with an alias to F if possible, or else a thunk to F. Deletes G. -void MergeFunctions::writeThunkOrAlias(Function *F, Function *G) { - if (HasGlobalAliases && G->hasUnnamedAddr()) { - if (G->hasExternalLinkage() || G->hasLocalLinkage() || - G->hasWeakLinkage()) { - writeAlias(F, G); - return; +void MergeFunctions::replaceUseInConstants(Constant *Old, Constant *New) { + for (auto UI = Old->use_begin(), UE = Old->use_end(); UI != UE;) { + Use *U = &*UI; + ++UI; + if (Constant* C = dyn_cast(U->getUser())) { + if (!isa(C)) { + removeUsers(C); + C->handleOperandChange(Old, New, U); + } else if (GlobalAlias* Alias = dyn_cast(C)) { + if (Alias->hasLocalLinkage() && !Alias->mayBeOverridden()) { + DEBUG(dbgs() << "Replacing alias " << Alias->getName() << "\n"); + Constant *BitcastNew = ConstantExpr::getBitCast(New, Old->getType()); + removeUsers(Alias); + Alias->replaceAllUsesWith(BitcastNew); + Alias->eraseFromParent(); + } + } } } - - writeThunk(F, G); } // Helper for writeThunk, @@ -1631,21 +1656,8 @@ return Builder.CreateBitCast(V, DestTy); } -// Replace G with a simple tail call to bitcast(F). Also replace direct uses -// of G with bitcast(F). Deletes G. +// Replace G with a simple tail call to F. Deletes the former body of G. void MergeFunctions::writeThunk(Function *F, Function *G) { - if (!G->mayBeOverridden()) { - // Redirect direct callers of G to F. - replaceDirectCallers(G, F); - } - - // If G was internal then we may have replaced all uses of G with F. If so, - // stop here and delete G. There's no need for a thunk. - if (G->hasLocalLinkage() && G->use_empty()) { - G->eraseFromParent(); - return; - } - Function *NewG = Function::Create(G->getFunctionType(), G->getLinkage(), "", G->getParent()); BasicBlock *BB = BasicBlock::Create(F->getContext(), "", NewG); @@ -1680,52 +1692,103 @@ ++NumThunksWritten; } -// Replace G with an alias to F and delete G. -void MergeFunctions::writeAlias(Function *F, Function *G) { - PointerType *PTy = G->getType(); - auto *GA = GlobalAlias::create(PTy, G->getLinkage(), "", F); - F->setAlignment(std::max(F->getAlignment(), G->getAlignment())); - GA->takeName(G); - GA->setVisibility(G->getVisibility()); - removeUsers(G); - G->replaceAllUsesWith(GA); - G->eraseFromParent(); +enum FuncMergeKind { + Weak = 0, + Internal = 1, + Named = 2, + External = 3 +}; - DEBUG(dbgs() << "writeAlias: " << GA->getName() << '\n'); - ++NumAliasesWritten; +FuncMergeKind functionMergeKind(Function *F) { + if (F->mayBeOverridden()) + return Weak; + if (F->hasLocalLinkage()) { + if (F->hasUnnamedAddr()) + return Internal; + return Named; + } + return External; } -// Merge two equivalent functions. Upon completion, Function G is deleted. -void MergeFunctions::mergeTwoFunctions(Function *F, Function *G) { - if (F->mayBeOverridden()) { - assert(G->mayBeOverridden()); - - // Make them both thunks to the same internal function. - Function *H = Function::Create(F->getFunctionType(), F->getLinkage(), "", - F->getParent()); - H->copyAttributesFrom(F); - H->takeName(F); - removeUsers(F); - F->replaceAllUsesWith(H); - - unsigned MaxAlignment = std::max(G->getAlignment(), H->getAlignment()); - - if (HasGlobalAliases) { - writeAlias(F, G); - writeAlias(F, H); - } else { - writeThunk(F, G); - writeThunk(F, H); +bool MergeFunctions::mergeTwoWeakFunctions(Function* F, Function* G) { + // Make them both thunks to the same internal function. + Function *H = Function::Create(F->getFunctionType(), F->getLinkage(), "", + F->getParent()); + H->copyAttributesFrom(F); + H->takeName(F); + F->replaceAllUsesWith(H); + + unsigned MaxAlignment = std::max(G->getAlignment(), H->getAlignment()); + + writeThunk(F, G); + writeThunk(F, H); + + F->setAlignment(MaxAlignment); + F->setLinkage(GlobalValue::PrivateLinkage); + return true; +} + +bool isFunctionThunkSized(Function& F) { + if (F.size() == 1) { + if (F.front().size() <= 2) { + return true; } + } + return false; +} - F->setAlignment(MaxAlignment); - F->setLinkage(GlobalValue::PrivateLinkage); +// Merge two equivalent functions. Upon completion, Function G is deleted. +bool MergeFunctions::mergeTwoFunctions(const FunctionNode &FN, Function *G) { + + auto FMK = functionMergeKind(FN.getFunc()), GMK = functionMergeKind(G); + // If the functions are to small, skip merging. But if one is internal, then + // we can replace it without generating a thunk. + if (isFunctionThunkSized(*G) && !(FMK == Internal || GMK == Internal)) + return false; + // Impose a total order (by name) on the replacement of functions. This is + // important when operating on more than one module independently to prevent + // cycles of thunks calling each other when the modules are linked together. + // When one function is weak and the other is strong there is an order imposed + // already. + bool Swap = (FMK == GMK && (FMK == Weak || FMK == External) + && FN.getFunc()->getName() > G->getName()); + // Ensure the "weaker" function is merged into the "stronger" one. + Swap = Swap || (GMK > FMK); + + if (Swap) { + Function *F = FN.getFunc(); + replaceFunctionInTree(FN, G); + G = F; + std::swap(FMK, GMK); + } + Function* F = FN.getFunc(); + // First, check if it's two weak functions. In this case, we need to modify + // both. + if (FMK == Weak && GMK == Weak) { + mergeTwoWeakFunctions(F, G); ++NumDoubleWeak; + ++NumFunctionsMerged; + return true; + } + // Otherwise, eliminate G in one of several ways depending on its type. + if (GMK != Weak) + replaceDirectCallers(G, F); + if (GMK == Internal) { + removeUsers(G); + replaceUseInConstants(G, F); + } + if (GMK != External && GMK != Weak && G->use_empty()) { + G->eraseFromParent(); + ++NumFunctionsMerged; } else { - writeThunkOrAlias(F, G); + if(!isFunctionThunkSized(*G)) { + writeThunk(F, G); + ++NumFunctionsMerged; + } else { + ++NumThunksSkipped; + } } - - ++NumFunctionsMerged; + return true; } /// Replace function F by function G. @@ -1761,45 +1824,12 @@ return false; } - const FunctionNode &OldF = *Result.first; - - // Don't merge tiny functions, since it can just end up making the function - // larger. - // FIXME: Should still merge them if they are unnamed_addr and produce an - // alias. - if (NewFunction->size() == 1) { - if (NewFunction->front().size() <= 2) { - DEBUG(dbgs() << NewFunction->getName() - << " is to small to bother merging\n"); - return false; - } - } + const FunctionNode &OldFuncNode = *Result.first; - // Impose a total order (by name) on the replacement of functions. This is - // important when operating on more than one module independently to prevent - // cycles of thunks calling each other when the modules are linked together. - // - // When one function is weak and the other is strong there is an order imposed - // already. We process strong functions before weak functions. - if ((OldF.getFunc()->mayBeOverridden() && NewFunction->mayBeOverridden()) || - (!OldF.getFunc()->mayBeOverridden() && !NewFunction->mayBeOverridden())) - if (OldF.getFunc()->getName() > NewFunction->getName()) { - // Swap the two functions. - Function *F = OldF.getFunc(); - replaceFunctionInTree(*Result.first, NewFunction); - NewFunction = F; - assert(OldF.getFunc() != F && "Must have swapped the functions."); - } - - // Never thunk a strong function to a weak function. - assert(!OldF.getFunc()->mayBeOverridden() || NewFunction->mayBeOverridden()); - - DEBUG(dbgs() << " " << OldF.getFunc()->getName() + DEBUG(dbgs() << " " << OldFuncNode.getFunc()->getName() << " == " << NewFunction->getName() << '\n'); - Function *DeleteF = NewFunction; - mergeTwoFunctions(OldF.getFunc(), DeleteF); - return true; + return mergeTwoFunctions(OldFuncNode, NewFunction); } // Remove a function from FnTree. If it was already in FnTree, add Index: test/Transforms/MergeFunc/constant-entire-value.ll =================================================================== --- test/Transforms/MergeFunc/constant-entire-value.ll +++ test/Transforms/MergeFunc/constant-entire-value.ll @@ -22,8 +22,8 @@ ret i32 %sum3 } -define internal i32 @plus(i32 %x, i32 %y) { -; NOPLUS-NOT: @plus +define internal i32 @next(i32 %x, i32 %y) { +; CHECK-LABEL: @next %sum = add i32 %x, %y %1 = extractvalue [3 x i32] [ i32 3, i32 0, i32 5 ], 2 %sum2 = add i32 %sum, %1 @@ -31,8 +31,8 @@ ret i32 %sum3 } -define internal i32 @next(i32 %x, i32 %y) { -; CHECK-LABEL: @next +define internal i32 @plus(i32 %x, i32 %y) { +; NOPLUS-NOT: @plus %sum = add i32 %x, %y %1 = extractvalue [3 x i32] [ i32 3, i32 0, i32 5 ], 2 %sum2 = add i32 %sum, %1