MergeFunctions.cpp revision 9c1858cf4a91d0f373d2315ccf834adedd197e6e
1579a0246616d76bc536de0e41edf069d091604beNick Lewycky//===- MergeFunctions.cpp - Merge identical functions ---------------------===// 2579a0246616d76bc536de0e41edf069d091604beNick Lewycky// 3579a0246616d76bc536de0e41edf069d091604beNick Lewycky// The LLVM Compiler Infrastructure 4579a0246616d76bc536de0e41edf069d091604beNick Lewycky// 5579a0246616d76bc536de0e41edf069d091604beNick Lewycky// This file is distributed under the University of Illinois Open Source 6579a0246616d76bc536de0e41edf069d091604beNick Lewycky// License. See LICENSE.TXT for details. 7579a0246616d76bc536de0e41edf069d091604beNick Lewycky// 8579a0246616d76bc536de0e41edf069d091604beNick Lewycky//===----------------------------------------------------------------------===// 9579a0246616d76bc536de0e41edf069d091604beNick Lewycky// 10579a0246616d76bc536de0e41edf069d091604beNick Lewycky// This pass looks for equivalent functions that are mergable and folds them. 11579a0246616d76bc536de0e41edf069d091604beNick Lewycky// 12579a0246616d76bc536de0e41edf069d091604beNick Lewycky// A hash is computed from the function, based on its type and number of 13579a0246616d76bc536de0e41edf069d091604beNick Lewycky// basic blocks. 14579a0246616d76bc536de0e41edf069d091604beNick Lewycky// 15579a0246616d76bc536de0e41edf069d091604beNick Lewycky// Once all hashes are computed, we perform an expensive equality comparison 16579a0246616d76bc536de0e41edf069d091604beNick Lewycky// on each function pair. This takes n^2/2 comparisons per bucket, so it's 17579a0246616d76bc536de0e41edf069d091604beNick Lewycky// important that the hash function be high quality. The equality comparison 18579a0246616d76bc536de0e41edf069d091604beNick Lewycky// iterates through each instruction in each basic block. 19579a0246616d76bc536de0e41edf069d091604beNick Lewycky// 2033ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky// When a match is found the functions are folded. If both functions are 2133ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky// overridable, we move the functionality into a new internal function and 2233ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky// leave two overridable thunks to it. 23579a0246616d76bc536de0e41edf069d091604beNick Lewycky// 24579a0246616d76bc536de0e41edf069d091604beNick Lewycky//===----------------------------------------------------------------------===// 25579a0246616d76bc536de0e41edf069d091604beNick Lewycky// 26579a0246616d76bc536de0e41edf069d091604beNick Lewycky// Future work: 27579a0246616d76bc536de0e41edf069d091604beNick Lewycky// 28579a0246616d76bc536de0e41edf069d091604beNick Lewycky// * virtual functions. 29579a0246616d76bc536de0e41edf069d091604beNick Lewycky// 30579a0246616d76bc536de0e41edf069d091604beNick Lewycky// Many functions have their address taken by the virtual function table for 31579a0246616d76bc536de0e41edf069d091604beNick Lewycky// the object they belong to. However, as long as it's only used for a lookup 32be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky// and call, this is irrelevant, and we'd like to fold such functions. 33579a0246616d76bc536de0e41edf069d091604beNick Lewycky// 3478d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky// * switch from n^2 pair-wise comparisons to an n-way comparison for each 3578d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky// bucket. 3633ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky// 37be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky// * be smarter about bitcasts. 3833ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky// 3933ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky// In order to fold functions, we will sometimes add either bitcast instructions 4033ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky// or bitcast constant expressions. Unfortunately, this can confound further 4133ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky// analysis since the two functions differ where one has a bitcast and the 42be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky// other doesn't. We should learn to look through bitcasts. 4333ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky// 44579a0246616d76bc536de0e41edf069d091604beNick Lewycky//===----------------------------------------------------------------------===// 45579a0246616d76bc536de0e41edf069d091604beNick Lewycky 46579a0246616d76bc536de0e41edf069d091604beNick Lewycky#define DEBUG_TYPE "mergefunc" 47579a0246616d76bc536de0e41edf069d091604beNick Lewycky#include "llvm/Transforms/IPO.h" 48f53de86cba33b63ecd54e16dcea735939c5b0e4aNick Lewycky#include "llvm/ADT/DenseSet.h" 49287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky#include "llvm/ADT/FoldingSet.h" 5033ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky#include "llvm/ADT/SmallSet.h" 51579a0246616d76bc536de0e41edf069d091604beNick Lewycky#include "llvm/ADT/Statistic.h" 52f53de86cba33b63ecd54e16dcea735939c5b0e4aNick Lewycky#include "llvm/ADT/STLExtras.h" 53579a0246616d76bc536de0e41edf069d091604beNick Lewycky#include "llvm/Constants.h" 54579a0246616d76bc536de0e41edf069d091604beNick Lewycky#include "llvm/InlineAsm.h" 55579a0246616d76bc536de0e41edf069d091604beNick Lewycky#include "llvm/Instructions.h" 5614ce9ef2e9013ba56e1daafebd91fe3ee1e8647eOwen Anderson#include "llvm/LLVMContext.h" 57579a0246616d76bc536de0e41edf069d091604beNick Lewycky#include "llvm/Module.h" 58579a0246616d76bc536de0e41edf069d091604beNick Lewycky#include "llvm/Pass.h" 596feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky#include "llvm/Support/CallSite.h" 60579a0246616d76bc536de0e41edf069d091604beNick Lewycky#include "llvm/Support/Debug.h" 61c25e7581b9b8088910da31702d4ca21c4734c6d7Torok Edwin#include "llvm/Support/ErrorHandling.h" 62be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky#include "llvm/Support/IRBuilder.h" 63f53de86cba33b63ecd54e16dcea735939c5b0e4aNick Lewycky#include "llvm/Support/ValueHandle.h" 64ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar#include "llvm/Support/raw_ostream.h" 6533ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky#include "llvm/Target/TargetData.h" 6665a0af3855c7003fa57d41eeb6586b20eefa8cfdNick Lewycky#include <vector> 67579a0246616d76bc536de0e41edf069d091604beNick Lewyckyusing namespace llvm; 68579a0246616d76bc536de0e41edf069d091604beNick Lewycky 69579a0246616d76bc536de0e41edf069d091604beNick LewyckySTATISTIC(NumFunctionsMerged, "Number of functions merged"); 702b6c01b40b75e363e46b3ad7c598113eb98f34fbNick LewyckySTATISTIC(NumThunksWritten, "Number of thunks generated"); 71b38824f866447ccf8dd0c76656755b05bcede1b1Nick LewyckySTATISTIC(NumAliasesWritten, "Number of aliases generated"); 722b6c01b40b75e363e46b3ad7c598113eb98f34fbNick LewyckySTATISTIC(NumDoubleWeak, "Number of new functions created"); 73579a0246616d76bc536de0e41edf069d091604beNick Lewycky 742b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky/// ProfileFunction - Creates a hash-code for the function which is the same 752b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky/// for any two functions that will compare equal, without looking at the 762b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky/// instructions inside the function. 77b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewyckystatic unsigned ProfileFunction(const Function *F) { 78b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky const FunctionType *FTy = F->getFunctionType(); 79b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 80b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky FoldingSetNodeID ID; 81b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky ID.AddInteger(F->size()); 82b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky ID.AddInteger(F->getCallingConv()); 83b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky ID.AddBoolean(F->hasGC()); 84b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky ID.AddBoolean(FTy->isVarArg()); 85b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky ID.AddInteger(FTy->getReturnType()->getTypeID()); 86b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i) 87b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky ID.AddInteger(FTy->getParamType(i)->getTypeID()); 88b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky return ID.ComputeHash(); 89579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 90579a0246616d76bc536de0e41edf069d091604beNick Lewycky 912b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewyckynamespace { 922b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky 93b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewyckyclass ComparableFunction { 94b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewyckypublic: 95b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky static const ComparableFunction EmptyKey; 96b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky static const ComparableFunction TombstoneKey; 97b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky 98b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky ComparableFunction(Function *Func, TargetData *TD) 99b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky : Func(Func), Hash(ProfileFunction(Func)), TD(TD) {} 100b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 101b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky Function *getFunc() const { return Func; } 102b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky unsigned getHash() const { return Hash; } 103b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky TargetData *getTD() const { return TD; } 104b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 105b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky // Drops AssertingVH reference to the function. Outside of debug mode, this 106b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky // does nothing. 107b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky void release() { 108b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky assert(Func && 109b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky "Attempted to release function twice, or release empty/tombstone!"); 110b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky Func = NULL; 111b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky } 112b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky 113e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky bool &getOrInsertCachedComparison(const ComparableFunction &Other, 114e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky bool &inserted) const { 115e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky typedef DenseMap<Function *, bool>::iterator iterator; 116e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky std::pair<iterator, bool> p = 117e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky CompareResultCache.insert(std::make_pair(Other.getFunc(), false)); 118e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky inserted = p.second; 119e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky return p.first->second; 120e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky } 121e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky 122b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewyckyprivate: 123b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky explicit ComparableFunction(unsigned Hash) 124b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky : Func(NULL), Hash(Hash), TD(NULL) {} 125b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky 126e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky // DenseMap::grow() triggers a recomparison of all keys in the map, which is 127e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky // wildly expensive. This cache tries to preserve known results. 128e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky mutable DenseMap<Function *, bool> CompareResultCache; 129e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky 130b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky AssertingVH<Function> Func; 131b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky unsigned Hash; 132b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky TargetData *TD; 133b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky}; 134b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 135b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewyckyconst ComparableFunction ComparableFunction::EmptyKey = ComparableFunction(0); 136b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewyckyconst ComparableFunction ComparableFunction::TombstoneKey = 137b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky ComparableFunction(1); 138b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky 1392b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky} 140b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky 141b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewyckynamespace llvm { 142b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky template <> 143b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky struct DenseMapInfo<ComparableFunction> { 144b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky static ComparableFunction getEmptyKey() { 145b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky return ComparableFunction::EmptyKey; 146b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky } 147b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky static ComparableFunction getTombstoneKey() { 148b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky return ComparableFunction::TombstoneKey; 149b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky } 150b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky static unsigned getHashValue(const ComparableFunction &CF) { 151b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky return CF.getHash(); 152b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky } 153b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky static bool isEqual(const ComparableFunction &LHS, 154b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky const ComparableFunction &RHS); 155b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky }; 156b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky} 157b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky 158b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewyckynamespace { 159b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky 160b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky/// MergeFunctions finds functions which will generate identical machine code, 161b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky/// by considering all pointer types to be equivalent. Once identified, 162b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky/// MergeFunctions will fold them by replacing a call to one to a call to a 163b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky/// bitcast of the other. 164b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky/// 165b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewyckyclass MergeFunctions : public ModulePass { 166b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewyckypublic: 167b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky static char ID; 168b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky MergeFunctions() 169b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky : ModulePass(ID), HasGlobalAliases(false) { 170081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeMergeFunctionsPass(*PassRegistry::getPassRegistry()); 171081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 172b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 173b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky bool runOnModule(Module &M); 174b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 175b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewyckyprivate: 176b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky typedef DenseSet<ComparableFunction> FnSetType; 177b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 178abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky /// A work queue of functions that may have been modified and should be 179abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky /// analyzed again. 180abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky std::vector<WeakVH> Deferred; 181b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 182b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky /// Insert a ComparableFunction into the FnSet, or merge it away if it's 183b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky /// equal to one that's already present. 184abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky bool Insert(ComparableFunction &NewF); 185abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky 186abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky /// Remove a Function from the FnSet and queue it up for a second sweep of 187abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky /// analysis. 188abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky void Remove(Function *F); 189abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky 190abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky /// Find the functions that use this Value and remove them from FnSet and 191abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky /// queue the functions. 192abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky void RemoveUsers(Value *V); 193b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 194b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky /// Replace all direct calls of Old with calls of New. Will bitcast New if 195b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky /// necessary to make types match. 196b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky void replaceDirectCallers(Function *Old, Function *New); 197b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky 198b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky /// MergeTwoFunctions - Merge two equivalent functions. Upon completion, G 199b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky /// may be deleted, or may be converted into a thunk. In either case, it 200b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky /// should never be visited again. 201abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky void MergeTwoFunctions(Function *F, Function *G); 202b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 203b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky /// WriteThunkOrAlias - Replace G with a thunk or an alias to F. Deletes G. 204b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky void WriteThunkOrAlias(Function *F, Function *G); 205b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky 206b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky /// WriteThunk - Replace G with a simple tail call to bitcast(F). Also 207b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky /// replace direct uses of G with bitcast(F). Deletes G. 208abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky void WriteThunk(Function *F, Function *G); 209b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 210b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky /// WriteAlias - Replace G with an alias to F. Deletes G. 211b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky void WriteAlias(Function *F, Function *G); 212b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky 213abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky /// The set of all distinct functions. Use the Insert and Remove methods to 214abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky /// modify it. 215abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky FnSetType FnSet; 216abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky 217abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky /// TargetData for more accurate GEP comparisons. May be NULL. 218b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky TargetData *TD; 219b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky 220b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky /// Whether or not the target supports global aliases. 221b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky bool HasGlobalAliases; 222b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky}; 223b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 224b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky} // end anonymous namespace 225b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 226579a0246616d76bc536de0e41edf069d091604beNick Lewyckychar MergeFunctions::ID = 0; 227ce665bd2e2b581ab0858d1afe359192bac96b868Owen AndersonINITIALIZE_PASS(MergeFunctions, "mergefunc", "Merge Functions", false, false) 228579a0246616d76bc536de0e41edf069d091604beNick Lewycky 229579a0246616d76bc536de0e41edf069d091604beNick LewyckyModulePass *llvm::createMergeFunctionsPass() { 230579a0246616d76bc536de0e41edf069d091604beNick Lewycky return new MergeFunctions(); 231579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 232579a0246616d76bc536de0e41edf069d091604beNick Lewycky 23378d4330fd83a94707b345e19f5277e7a46892689Nick Lewyckynamespace { 234be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky/// FunctionComparator - Compares two functions to determine whether or not 235be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky/// they will generate machine code with the same behaviour. TargetData is 236be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky/// used if available. The comparator always fails conservatively (erring on the 237be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky/// side of claiming that two functions are different). 23878d4330fd83a94707b345e19f5277e7a46892689Nick Lewyckyclass FunctionComparator { 23978d4330fd83a94707b345e19f5277e7a46892689Nick Lewyckypublic: 240f53de86cba33b63ecd54e16dcea735939c5b0e4aNick Lewycky FunctionComparator(const TargetData *TD, const Function *F1, 241f53de86cba33b63ecd54e16dcea735939c5b0e4aNick Lewycky const Function *F2) 242c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky : F1(F1), F2(F2), TD(TD), IDMap1Count(0), IDMap2Count(0) {} 24378d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky 244be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky /// Compare - test whether the two functions have equivalent behaviour. 24578d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky bool Compare(); 24678d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky 24778d4330fd83a94707b345e19f5277e7a46892689Nick Lewyckyprivate: 248be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky /// Compare - test whether two basic blocks have equivalent behaviour. 24978d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky bool Compare(const BasicBlock *BB1, const BasicBlock *BB2); 25078d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky 251be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky /// Enumerate - Assign or look up previously assigned numbers for the two 252be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky /// values, and return whether the numbers are equal. Numbers are assigned in 253be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky /// the order visited. 25478d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky bool Enumerate(const Value *V1, const Value *V2); 25578d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky 256be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky /// isEquivalentOperation - Compare two Instructions for equivalence, similar 257be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky /// to Instruction::isSameOperationAs but with modifications to the type 258be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky /// comparison. 25978d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky bool isEquivalentOperation(const Instruction *I1, 26078d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky const Instruction *I2) const; 26178d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky 262be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky /// isEquivalentGEP - Compare two GEPs for equivalent pointer arithmetic. 26378d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky bool isEquivalentGEP(const GEPOperator *GEP1, const GEPOperator *GEP2); 26478d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky bool isEquivalentGEP(const GetElementPtrInst *GEP1, 265be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky const GetElementPtrInst *GEP2) { 26678d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky return isEquivalentGEP(cast<GEPOperator>(GEP1), cast<GEPOperator>(GEP2)); 26778d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky } 268287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 269be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky /// isEquivalentType - Compare two Types, treating all pointer types as equal. 27078d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky bool isEquivalentType(const Type *Ty1, const Type *Ty2) const; 27178d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky 27278d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky // The two functions undergoing comparison. 273f53de86cba33b63ecd54e16dcea735939c5b0e4aNick Lewycky const Function *F1, *F2; 27478d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky 275f53de86cba33b63ecd54e16dcea735939c5b0e4aNick Lewycky const TargetData *TD; 27678d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky 27778d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky typedef DenseMap<const Value *, unsigned long> IDMap; 278c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky IDMap Map1, Map2; 279c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky unsigned long IDMap1Count, IDMap2Count; 28078d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky}; 28178d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky} 28278d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky 283c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky/// isEquivalentType - any two pointers in the same address space are 284c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky/// equivalent. Otherwise, standard type equivalence rules apply. 28578d4330fd83a94707b345e19f5277e7a46892689Nick Lewyckybool FunctionComparator::isEquivalentType(const Type *Ty1, 28678d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky const Type *Ty2) const { 287287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (Ty1 == Ty2) 288287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return true; 289207c193e7e9cc177115101333079e952a7676689Nick Lewycky if (Ty1->getTypeID() != Ty2->getTypeID()) { 290207c193e7e9cc177115101333079e952a7676689Nick Lewycky if (TD) { 291207c193e7e9cc177115101333079e952a7676689Nick Lewycky LLVMContext &Ctx = Ty1->getContext(); 292207c193e7e9cc177115101333079e952a7676689Nick Lewycky if (isa<PointerType>(Ty1) && Ty2 == TD->getIntPtrType(Ctx)) return true; 293207c193e7e9cc177115101333079e952a7676689Nick Lewycky if (isa<PointerType>(Ty2) && Ty1 == TD->getIntPtrType(Ctx)) return true; 294207c193e7e9cc177115101333079e952a7676689Nick Lewycky } 295287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 296207c193e7e9cc177115101333079e952a7676689Nick Lewycky } 297287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 298287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky switch(Ty1->getTypeID()) { 29933ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky default: 30033ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky llvm_unreachable("Unknown type!"); 3018246adc1f0e2d28374da3aeab864aee5ff03f3ffDuncan Sands // Fall through in Release mode. 30233ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky case Type::IntegerTyID: 30333ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky case Type::OpaqueTyID: 304388f4918fbd8349a6c5b8403e31f65aa3408add6Nick Lewycky case Type::VectorTyID: 30533ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky // Ty1 == Ty2 would have returned true earlier. 30633ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky return false; 30733ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky 308287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky case Type::VoidTyID: 309287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky case Type::FloatTyID: 310287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky case Type::DoubleTyID: 311287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky case Type::X86_FP80TyID: 312287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky case Type::FP128TyID: 313287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky case Type::PPC_FP128TyID: 314287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky case Type::LabelTyID: 315287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky case Type::MetadataTyID: 316287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return true; 317287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 318287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky case Type::PointerTyID: { 319287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky const PointerType *PTy1 = cast<PointerType>(Ty1); 320287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky const PointerType *PTy2 = cast<PointerType>(Ty2); 321287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return PTy1->getAddressSpace() == PTy2->getAddressSpace(); 322287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky } 323287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 324287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky case Type::StructTyID: { 325287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky const StructType *STy1 = cast<StructType>(Ty1); 326287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky const StructType *STy2 = cast<StructType>(Ty2); 327287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (STy1->getNumElements() != STy2->getNumElements()) 328287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 329287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 330287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (STy1->isPacked() != STy2->isPacked()) 331287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 332287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 333287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky for (unsigned i = 0, e = STy1->getNumElements(); i != e; ++i) { 334287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (!isEquivalentType(STy1->getElementType(i), STy2->getElementType(i))) 335287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 336287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky } 337287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return true; 338287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky } 339287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 340287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky case Type::FunctionTyID: { 341287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky const FunctionType *FTy1 = cast<FunctionType>(Ty1); 342287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky const FunctionType *FTy2 = cast<FunctionType>(Ty2); 343287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (FTy1->getNumParams() != FTy2->getNumParams() || 344287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky FTy1->isVarArg() != FTy2->isVarArg()) 345287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 346287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 347287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (!isEquivalentType(FTy1->getReturnType(), FTy2->getReturnType())) 348287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 349287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 350287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky for (unsigned i = 0, e = FTy1->getNumParams(); i != e; ++i) { 351287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (!isEquivalentType(FTy1->getParamType(i), FTy2->getParamType(i))) 352287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 353287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky } 354287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return true; 355287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky } 356287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 357394ce41b7fcb64a35d5cd1c1fefc0e2225ebfc01Nick Lewycky case Type::ArrayTyID: { 358394ce41b7fcb64a35d5cd1c1fefc0e2225ebfc01Nick Lewycky const ArrayType *ATy1 = cast<ArrayType>(Ty1); 359394ce41b7fcb64a35d5cd1c1fefc0e2225ebfc01Nick Lewycky const ArrayType *ATy2 = cast<ArrayType>(Ty2); 360394ce41b7fcb64a35d5cd1c1fefc0e2225ebfc01Nick Lewycky return ATy1->getNumElements() == ATy2->getNumElements() && 361394ce41b7fcb64a35d5cd1c1fefc0e2225ebfc01Nick Lewycky isEquivalentType(ATy1->getElementType(), ATy2->getElementType()); 362287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky } 363287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky } 364287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky} 365287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 366287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky/// isEquivalentOperation - determine whether the two operations are the same 367287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky/// except that pointer-to-A and pointer-to-B are equivalent. This should be 368194ae785e1f94619cbdcdcf2921caa6997277d32Dan Gohman/// kept in sync with Instruction::isSameOperationAs. 36978d4330fd83a94707b345e19f5277e7a46892689Nick Lewyckybool FunctionComparator::isEquivalentOperation(const Instruction *I1, 37078d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky const Instruction *I2) const { 371287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (I1->getOpcode() != I2->getOpcode() || 372287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky I1->getNumOperands() != I2->getNumOperands() || 37358cfa3b13752579c86cf85270d49f9ced0942f2fDan Gohman !isEquivalentType(I1->getType(), I2->getType()) || 37458cfa3b13752579c86cf85270d49f9ced0942f2fDan Gohman !I1->hasSameSubclassOptionalData(I2)) 375287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 376287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 377287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky // We have two instructions of identical opcode and #operands. Check to see 378287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky // if all operands are the same type 379287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky for (unsigned i = 0, e = I1->getNumOperands(); i != e; ++i) 380287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (!isEquivalentType(I1->getOperand(i)->getType(), 381287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky I2->getOperand(i)->getType())) 382287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 383287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 384287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky // Check special state that is a part of some instructions. 385287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (const LoadInst *LI = dyn_cast<LoadInst>(I1)) 386287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return LI->isVolatile() == cast<LoadInst>(I2)->isVolatile() && 387287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky LI->getAlignment() == cast<LoadInst>(I2)->getAlignment(); 388287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (const StoreInst *SI = dyn_cast<StoreInst>(I1)) 389287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return SI->isVolatile() == cast<StoreInst>(I2)->isVolatile() && 390287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky SI->getAlignment() == cast<StoreInst>(I2)->getAlignment(); 391287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (const CmpInst *CI = dyn_cast<CmpInst>(I1)) 392287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return CI->getPredicate() == cast<CmpInst>(I2)->getPredicate(); 393287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (const CallInst *CI = dyn_cast<CallInst>(I1)) 394287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return CI->isTailCall() == cast<CallInst>(I2)->isTailCall() && 395287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky CI->getCallingConv() == cast<CallInst>(I2)->getCallingConv() && 396f6c63c23203ca4c4aa89efa2bff722bb479cfe3cNick Lewycky CI->getAttributes() == cast<CallInst>(I2)->getAttributes(); 397287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (const InvokeInst *CI = dyn_cast<InvokeInst>(I1)) 398287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return CI->getCallingConv() == cast<InvokeInst>(I2)->getCallingConv() && 399f6c63c23203ca4c4aa89efa2bff722bb479cfe3cNick Lewycky CI->getAttributes() == cast<InvokeInst>(I2)->getAttributes(); 400287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(I1)) { 401287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (IVI->getNumIndices() != cast<InsertValueInst>(I2)->getNumIndices()) 402287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 403287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky for (unsigned i = 0, e = IVI->getNumIndices(); i != e; ++i) 404287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (IVI->idx_begin()[i] != cast<InsertValueInst>(I2)->idx_begin()[i]) 405287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 406287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return true; 407287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky } 408287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(I1)) { 409287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (EVI->getNumIndices() != cast<ExtractValueInst>(I2)->getNumIndices()) 410287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 411287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky for (unsigned i = 0, e = EVI->getNumIndices(); i != e; ++i) 412287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (EVI->idx_begin()[i] != cast<ExtractValueInst>(I2)->idx_begin()[i]) 413287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 414287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return true; 415287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky } 416287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 417287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return true; 418579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 419579a0246616d76bc536de0e41edf069d091604beNick Lewycky 42078d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky/// isEquivalentGEP - determine whether two GEP operations perform the same 42178d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky/// underlying arithmetic. 42278d4330fd83a94707b345e19f5277e7a46892689Nick Lewyckybool FunctionComparator::isEquivalentGEP(const GEPOperator *GEP1, 42378d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky const GEPOperator *GEP2) { 42478d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky // When we have target data, we can reduce the GEP down to the value in bytes 42578d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky // added to the address. 42633ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky if (TD && GEP1->hasAllConstantIndices() && GEP2->hasAllConstantIndices()) { 42778d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky SmallVector<Value *, 8> Indices1(GEP1->idx_begin(), GEP1->idx_end()); 42878d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky SmallVector<Value *, 8> Indices2(GEP2->idx_begin(), GEP2->idx_end()); 42933ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky uint64_t Offset1 = TD->getIndexedOffset(GEP1->getPointerOperandType(), 43033ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky Indices1.data(), Indices1.size()); 43133ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky uint64_t Offset2 = TD->getIndexedOffset(GEP2->getPointerOperandType(), 43233ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky Indices2.data(), Indices2.size()); 43333ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky return Offset1 == Offset2; 43433ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky } 435579a0246616d76bc536de0e41edf069d091604beNick Lewycky 43633ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky if (GEP1->getPointerOperand()->getType() != 43733ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky GEP2->getPointerOperand()->getType()) 43833ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky return false; 439579a0246616d76bc536de0e41edf069d091604beNick Lewycky 44033ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky if (GEP1->getNumOperands() != GEP2->getNumOperands()) 441579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 442579a0246616d76bc536de0e41edf069d091604beNick Lewycky 44333ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky for (unsigned i = 0, e = GEP1->getNumOperands(); i != e; ++i) { 44478d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (!Enumerate(GEP1->getOperand(i), GEP2->getOperand(i))) 44533ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky return false; 446579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 447579a0246616d76bc536de0e41edf069d091604beNick Lewycky 44833ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky return true; 449579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 450579a0246616d76bc536de0e41edf069d091604beNick Lewycky 45178d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky/// Enumerate - Compare two values used by the two functions under pair-wise 45278d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky/// comparison. If this is the first time the values are seen, they're added to 45378d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky/// the mapping so that we will detect mismatches on next use. 45478d4330fd83a94707b345e19f5277e7a46892689Nick Lewyckybool FunctionComparator::Enumerate(const Value *V1, const Value *V2) { 45578d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky // Check for function @f1 referring to itself and function @f2 referring to 45678d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky // itself, or referring to each other, or both referring to either of them. 45778d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky // They're all equivalent if the two functions are otherwise equivalent. 458c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky if (V1 == F1 && V2 == F2) 459c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky return true; 460c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky if (V1 == F2 && V2 == F1) 461c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky return true; 462579a0246616d76bc536de0e41edf069d091604beNick Lewycky 4639c1858cf4a91d0f373d2315ccf834adedd197e6eBenjamin Kramer if (const Constant *C1 = dyn_cast<Constant>(V1)) { 46425296e25fd30806b4a1f2348cbf73f227962be86Nick Lewycky if (V1 == V2) return true; 46525296e25fd30806b4a1f2348cbf73f227962be86Nick Lewycky const Constant *C2 = dyn_cast<Constant>(V2); 46625296e25fd30806b4a1f2348cbf73f227962be86Nick Lewycky if (!C2) return false; 46725296e25fd30806b4a1f2348cbf73f227962be86Nick Lewycky // TODO: constant expressions with GEP or references to F1 or F2. 46825296e25fd30806b4a1f2348cbf73f227962be86Nick Lewycky if (C1->isNullValue() && C2->isNullValue() && 46925296e25fd30806b4a1f2348cbf73f227962be86Nick Lewycky isEquivalentType(C1->getType(), C2->getType())) 47025296e25fd30806b4a1f2348cbf73f227962be86Nick Lewycky return true; 471c9d69489ebe12f265828c48defb0278f6bd9121fNick Lewycky // Try bitcasting C2 to C1's type. If the bitcast is legal and returns C1 472c9d69489ebe12f265828c48defb0278f6bd9121fNick Lewycky // then they must have equal bit patterns. 47325296e25fd30806b4a1f2348cbf73f227962be86Nick Lewycky return C1->getType()->canLosslesslyBitCastTo(C2->getType()) && 47425296e25fd30806b4a1f2348cbf73f227962be86Nick Lewycky C1 == ConstantExpr::getBitCast(const_cast<Constant*>(C2), C1->getType()); 47525296e25fd30806b4a1f2348cbf73f227962be86Nick Lewycky } 476579a0246616d76bc536de0e41edf069d091604beNick Lewycky 47733ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky if (isa<InlineAsm>(V1) && isa<InlineAsm>(V2)) { 47833ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky const InlineAsm *IA1 = cast<InlineAsm>(V1); 47933ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky const InlineAsm *IA2 = cast<InlineAsm>(V2); 48033ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky return IA1->getAsmString() == IA2->getAsmString() && 48133ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky IA1->getConstraintString() == IA2->getConstraintString(); 48233ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky } 483579a0246616d76bc536de0e41edf069d091604beNick Lewycky 48433ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky unsigned long &ID1 = Map1[V1]; 48533ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky if (!ID1) 486c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky ID1 = ++IDMap1Count; 48733ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky 48833ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky unsigned long &ID2 = Map2[V2]; 48933ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky if (!ID2) 490c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky ID2 = ++IDMap2Count; 49133ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky 49233ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky return ID1 == ID2; 49333ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky} 49433ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky 495be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky/// Compare - test whether two basic blocks have equivalent behaviour. 49678d4330fd83a94707b345e19f5277e7a46892689Nick Lewyckybool FunctionComparator::Compare(const BasicBlock *BB1, const BasicBlock *BB2) { 49778d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky BasicBlock::const_iterator F1I = BB1->begin(), F1E = BB1->end(); 49878d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky BasicBlock::const_iterator F2I = BB2->begin(), F2E = BB2->end(); 499579a0246616d76bc536de0e41edf069d091604beNick Lewycky 50033ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky do { 50178d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (!Enumerate(F1I, F2I)) 502579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 503579a0246616d76bc536de0e41edf069d091604beNick Lewycky 50478d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (const GetElementPtrInst *GEP1 = dyn_cast<GetElementPtrInst>(F1I)) { 50578d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky const GetElementPtrInst *GEP2 = dyn_cast<GetElementPtrInst>(F2I); 50678d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (!GEP2) 50778d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky return false; 508579a0246616d76bc536de0e41edf069d091604beNick Lewycky 50978d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (!Enumerate(GEP1->getPointerOperand(), GEP2->getPointerOperand())) 510911ae391e85ead1bb11895562a6bbdb2c0f8ebd2Nick Lewycky return false; 511579a0246616d76bc536de0e41edf069d091604beNick Lewycky 51233ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky if (!isEquivalentGEP(GEP1, GEP2)) 513911ae391e85ead1bb11895562a6bbdb2c0f8ebd2Nick Lewycky return false; 51433ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky } else { 51578d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (!isEquivalentOperation(F1I, F2I)) 516579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 517579a0246616d76bc536de0e41edf069d091604beNick Lewycky 51878d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky assert(F1I->getNumOperands() == F2I->getNumOperands()); 51978d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky for (unsigned i = 0, e = F1I->getNumOperands(); i != e; ++i) { 52078d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky Value *OpF1 = F1I->getOperand(i); 52178d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky Value *OpF2 = F2I->getOperand(i); 522579a0246616d76bc536de0e41edf069d091604beNick Lewycky 52378d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (!Enumerate(OpF1, OpF2)) 524911ae391e85ead1bb11895562a6bbdb2c0f8ebd2Nick Lewycky return false; 52533ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky 52678d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (OpF1->getValueID() != OpF2->getValueID() || 52778d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky !isEquivalentType(OpF1->getType(), OpF2->getType())) 528579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 529579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 530579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 531579a0246616d76bc536de0e41edf069d091604beNick Lewycky 53278d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky ++F1I, ++F2I; 53378d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky } while (F1I != F1E && F2I != F2E); 534579a0246616d76bc536de0e41edf069d091604beNick Lewycky 53578d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky return F1I == F1E && F2I == F2E; 536579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 537579a0246616d76bc536de0e41edf069d091604beNick Lewycky 538be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky/// Compare - test whether the two functions have equivalent behaviour. 53978d4330fd83a94707b345e19f5277e7a46892689Nick Lewyckybool FunctionComparator::Compare() { 540579a0246616d76bc536de0e41edf069d091604beNick Lewycky // We need to recheck everything, but check the things that weren't included 541579a0246616d76bc536de0e41edf069d091604beNick Lewycky // in the hash first. 542579a0246616d76bc536de0e41edf069d091604beNick Lewycky 54378d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (F1->getAttributes() != F2->getAttributes()) 544579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 545579a0246616d76bc536de0e41edf069d091604beNick Lewycky 54678d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (F1->hasGC() != F2->hasGC()) 547579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 548579a0246616d76bc536de0e41edf069d091604beNick Lewycky 54978d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (F1->hasGC() && F1->getGC() != F2->getGC()) 550579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 551579a0246616d76bc536de0e41edf069d091604beNick Lewycky 55278d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (F1->hasSection() != F2->hasSection()) 553579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 554579a0246616d76bc536de0e41edf069d091604beNick Lewycky 55578d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (F1->hasSection() && F1->getSection() != F2->getSection()) 556579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 557579a0246616d76bc536de0e41edf069d091604beNick Lewycky 55878d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (F1->isVarArg() != F2->isVarArg()) 559287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 560287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 561579a0246616d76bc536de0e41edf069d091604beNick Lewycky // TODO: if it's internal and only used in direct calls, we could handle this 562579a0246616d76bc536de0e41edf069d091604beNick Lewycky // case too. 56378d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (F1->getCallingConv() != F2->getCallingConv()) 564579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 565579a0246616d76bc536de0e41edf069d091604beNick Lewycky 56678d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (!isEquivalentType(F1->getFunctionType(), F2->getFunctionType())) 567579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 568579a0246616d76bc536de0e41edf069d091604beNick Lewycky 56978d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky assert(F1->arg_size() == F2->arg_size() && 5702b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky "Identically typed functions have different numbers of args!"); 571579a0246616d76bc536de0e41edf069d091604beNick Lewycky 57233ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky // Visit the arguments so that they get enumerated in the order they're 57333ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky // passed in. 57478d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky for (Function::const_arg_iterator f1i = F1->arg_begin(), 57578d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky f2i = F2->arg_begin(), f1e = F1->arg_end(); f1i != f1e; ++f1i, ++f2i) { 57678d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (!Enumerate(f1i, f2i)) 5772b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky llvm_unreachable("Arguments repeat!"); 57833ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky } 579579a0246616d76bc536de0e41edf069d091604beNick Lewycky 580be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky // We do a CFG-ordered walk since the actual ordering of the blocks in the 581be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky // linked list is immaterial. Our walk starts at the entry block for both 58278d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky // functions, then takes each block from each terminator in order. As an 58378d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky // artifact, this also means that unreachable blocks are ignored. 58478d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky SmallVector<const BasicBlock *, 8> F1BBs, F2BBs; 58578d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky SmallSet<const BasicBlock *, 128> VisitedBBs; // in terms of F1. 586c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky 58778d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky F1BBs.push_back(&F1->getEntryBlock()); 58878d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky F2BBs.push_back(&F2->getEntryBlock()); 589c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky 59078d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky VisitedBBs.insert(F1BBs[0]); 59178d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky while (!F1BBs.empty()) { 59278d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky const BasicBlock *F1BB = F1BBs.pop_back_val(); 59378d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky const BasicBlock *F2BB = F2BBs.pop_back_val(); 594c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky 59578d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (!Enumerate(F1BB, F2BB) || !Compare(F1BB, F2BB)) 596579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 597c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky 59878d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky const TerminatorInst *F1TI = F1BB->getTerminator(); 59978d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky const TerminatorInst *F2TI = F2BB->getTerminator(); 600c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky 60178d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky assert(F1TI->getNumSuccessors() == F2TI->getNumSuccessors()); 60278d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky for (unsigned i = 0, e = F1TI->getNumSuccessors(); i != e; ++i) { 60378d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (!VisitedBBs.insert(F1TI->getSuccessor(i))) 604911ae391e85ead1bb11895562a6bbdb2c0f8ebd2Nick Lewycky continue; 605c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky 60678d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky F1BBs.push_back(F1TI->getSuccessor(i)); 60778d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky F2BBs.push_back(F2TI->getSuccessor(i)); 60833ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky } 609579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 610579a0246616d76bc536de0e41edf069d091604beNick Lewycky return true; 611579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 612579a0246616d76bc536de0e41edf069d091604beNick Lewycky 613b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky/// Replace direct callers of Old with New. 614b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewyckyvoid MergeFunctions::replaceDirectCallers(Function *Old, Function *New) { 615b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky Constant *BitcastNew = ConstantExpr::getBitCast(New, Old->getType()); 616b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky for (Value::use_iterator UI = Old->use_begin(), UE = Old->use_end(); 617b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky UI != UE;) { 618b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky Value::use_iterator TheIter = UI; 619b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky ++UI; 620b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky CallSite CS(*TheIter); 621b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky if (CS && CS.isCallee(TheIter)) { 622b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky Remove(CS.getInstruction()->getParent()->getParent()); 623b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky TheIter.getUse().set(BitcastNew); 624b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky } 625b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky } 626b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky} 627b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky 628b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewyckyvoid MergeFunctions::WriteThunkOrAlias(Function *F, Function *G) { 629b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky if (HasGlobalAliases && G->hasUnnamedAddr()) { 630b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky if (G->hasExternalLinkage() || G->hasLocalLinkage() || 631b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky G->hasWeakLinkage()) { 632b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky WriteAlias(F, G); 633b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky return; 634b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky } 635b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky } 636b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky 637b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky WriteThunk(F, G); 638b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky} 639b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky 640be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky/// WriteThunk - Replace G with a simple tail call to bitcast(F). Also replace 641b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky/// direct uses of G with bitcast(F). Deletes G. 642abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewyckyvoid MergeFunctions::WriteThunk(Function *F, Function *G) { 64333ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky if (!G->mayBeOverridden()) { 64433ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky // Redirect direct callers of G to F. 645b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky replaceDirectCallers(G, F); 64633ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky } 64733ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky 6482b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky // If G was internal then we may have replaced all uses of G with F. If so, 649c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky // stop here and delete G. There's no need for a thunk. 650c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky if (G->hasLocalLinkage() && G->use_empty()) { 651c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky G->eraseFromParent(); 652c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky return; 653c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky } 654c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky 6558728d7a3ea7cad3297f9ab0984358007238ae83aNick Lewycky Function *NewG = Function::Create(G->getFunctionType(), G->getLinkage(), "", 6568728d7a3ea7cad3297f9ab0984358007238ae83aNick Lewycky G->getParent()); 6571d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *BB = BasicBlock::Create(F->getContext(), "", NewG); 658be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky IRBuilder<false> Builder(BB); 659287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 66033ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky SmallVector<Value *, 16> Args; 661287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky unsigned i = 0; 662287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky const FunctionType *FFTy = F->getFunctionType(); 663287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky for (Function::arg_iterator AI = NewG->arg_begin(), AE = NewG->arg_end(); 664287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky AI != AE; ++AI) { 665be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky Args.push_back(Builder.CreateBitCast(AI, FFTy->getParamType(i))); 666287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky ++i; 667579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 668579a0246616d76bc536de0e41edf069d091604beNick Lewycky 669be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky CallInst *CI = Builder.CreateCall(F, Args.begin(), Args.end()); 670287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky CI->setTailCall(); 671b3c36c9c9aba3fce8ae35b52eda4192531a9d3dfNick Lewycky CI->setCallingConv(F->getCallingConv()); 672f012705c7e4ca8cf90b6b734ce1d5355daca5ba5Benjamin Kramer if (NewG->getReturnType()->isVoidTy()) { 673be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky Builder.CreateRetVoid(); 674287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky } else { 675be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky Builder.CreateRet(Builder.CreateBitCast(CI, NewG->getReturnType())); 6766feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky } 6776feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky 678287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky NewG->copyAttributesFrom(G); 679287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky NewG->takeName(G); 680abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky RemoveUsers(G); 681287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky G->replaceAllUsesWith(NewG); 682287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky G->eraseFromParent(); 6832b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky 6842b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky DEBUG(dbgs() << "WriteThunk: " << NewG->getName() << '\n'); 6852b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky ++NumThunksWritten; 686579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 687579a0246616d76bc536de0e41edf069d091604beNick Lewycky 688b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky/// WriteAlias - Replace G with an alias to F and delete G. 689b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewyckyvoid MergeFunctions::WriteAlias(Function *F, Function *G) { 690b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky Constant *BitcastF = ConstantExpr::getBitCast(F, G->getType()); 691b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky GlobalAlias *GA = new GlobalAlias(G->getType(), G->getLinkage(), "", 692b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky BitcastF, G->getParent()); 693b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky F->setAlignment(std::max(F->getAlignment(), G->getAlignment())); 694b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky GA->takeName(G); 695b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky GA->setVisibility(G->getVisibility()); 696b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky RemoveUsers(G); 697b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky G->replaceAllUsesWith(GA); 698b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky G->eraseFromParent(); 699b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky 700b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky DEBUG(dbgs() << "WriteAlias: " << GA->getName() << '\n'); 701b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky ++NumAliasesWritten; 702b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky} 703b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky 704be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky/// MergeTwoFunctions - Merge two equivalent functions. Upon completion, 705f53de86cba33b63ecd54e16dcea735939c5b0e4aNick Lewycky/// Function G is deleted. 706abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewyckyvoid MergeFunctions::MergeTwoFunctions(Function *F, Function *G) { 7072b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky if (F->mayBeOverridden()) { 7082b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky assert(G->mayBeOverridden()); 7098728d7a3ea7cad3297f9ab0984358007238ae83aNick Lewycky 710b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky if (HasGlobalAliases) { 711b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky // Make them both thunks to the same internal function. 712b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky Function *H = Function::Create(F->getFunctionType(), F->getLinkage(), "", 713b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky F->getParent()); 714b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky H->copyAttributesFrom(F); 715b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky H->takeName(F); 716b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky RemoveUsers(F); 717b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky F->replaceAllUsesWith(H); 7188728d7a3ea7cad3297f9ab0984358007238ae83aNick Lewycky 719b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky unsigned MaxAlignment = std::max(G->getAlignment(), H->getAlignment()); 7203221834f8a6216d01a7e1d1201bd14eafd79cff3Nick Lewycky 721b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky WriteAlias(F, G); 722b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky WriteAlias(F, H); 7238728d7a3ea7cad3297f9ab0984358007238ae83aNick Lewycky 724b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky F->setAlignment(MaxAlignment); 725b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky F->setLinkage(GlobalValue::PrivateLinkage); 726b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky } else { 727b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky // We can't merge them. Instead, pick one and update all direct callers 728b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky // to call it and hope that we improve the instruction cache hit rate. 729b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky replaceDirectCallers(G, F); 730b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky } 7312b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky 7322b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky ++NumDoubleWeak; 733c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky } else { 734b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky WriteThunkOrAlias(F, G); 735579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 736579a0246616d76bc536de0e41edf069d091604beNick Lewycky 737287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky ++NumFunctionsMerged; 738579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 739579a0246616d76bc536de0e41edf069d091604beNick Lewycky 740b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky// Insert - Insert a ComparableFunction into the FnSet, or merge it away if 741b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky// equal to one that's already inserted. 742abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewyckybool MergeFunctions::Insert(ComparableFunction &NewF) { 743b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky std::pair<FnSetType::iterator, bool> Result = FnSet.insert(NewF); 744b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky if (Result.second) 745b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky return false; 746f53de86cba33b63ecd54e16dcea735939c5b0e4aNick Lewycky 747b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky const ComparableFunction &OldF = *Result.first; 748b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 749b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky // Never thunk a strong function to a weak function. 7502b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky assert(!OldF.getFunc()->mayBeOverridden() || 7512b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky NewF.getFunc()->mayBeOverridden()); 752b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 753b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky DEBUG(dbgs() << " " << OldF.getFunc()->getName() << " == " 754b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky << NewF.getFunc()->getName() << '\n'); 755b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 756b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky Function *DeleteF = NewF.getFunc(); 757b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky NewF.release(); 758b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky MergeTwoFunctions(OldF.getFunc(), DeleteF); 759b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky return true; 760be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky} 761287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 762abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky// Remove - Remove a function from FnSet. If it was already in FnSet, add it to 763abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky// Deferred so that we'll look at it in the next round. 764abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewyckyvoid MergeFunctions::Remove(Function *F) { 765abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky ComparableFunction CF = ComparableFunction(F, TD); 766abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky if (FnSet.erase(CF)) { 767abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky Deferred.push_back(F); 768f53de86cba33b63ecd54e16dcea735939c5b0e4aNick Lewycky } 769abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky} 770b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 771abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky// RemoveUsers - For each instruction used by the value, Remove() the function 772abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky// that contains the instruction. This should happen right before a call to RAUW. 773abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewyckyvoid MergeFunctions::RemoveUsers(Value *V) { 774d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky std::vector<Value *> Worklist; 775d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky Worklist.push_back(V); 776d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky while (!Worklist.empty()) { 777d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky Value *V = Worklist.back(); 778d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky Worklist.pop_back(); 779d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky 780d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); 781d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky UI != UE; ++UI) { 782d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky Use &U = UI.getUse(); 783d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky if (Instruction *I = dyn_cast<Instruction>(U.getUser())) { 784d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky Remove(I->getParent()->getParent()); 785d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky } else if (isa<GlobalValue>(U.getUser())) { 786e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky // do nothing 787d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky } else if (Constant *C = dyn_cast<Constant>(U.getUser())) { 788e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky for (Value::use_iterator CUI = C->use_begin(), CUE = C->use_end(); 789e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky CUI != CUE; ++CUI) 790d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky Worklist.push_back(*CUI); 791d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky } 792b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky } 793f53de86cba33b63ecd54e16dcea735939c5b0e4aNick Lewycky } 794b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky} 795f53de86cba33b63ecd54e16dcea735939c5b0e4aNick Lewycky 796579a0246616d76bc536de0e41edf069d091604beNick Lewyckybool MergeFunctions::runOnModule(Module &M) { 79765a0af3855c7003fa57d41eeb6586b20eefa8cfdNick Lewycky bool Changed = false; 79865a0af3855c7003fa57d41eeb6586b20eefa8cfdNick Lewycky TD = getAnalysisIfAvailable<TargetData>(); 799f53de86cba33b63ecd54e16dcea735939c5b0e4aNick Lewycky 800abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) { 801abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky Deferred.push_back(WeakVH(I)); 802abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky } 803abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky 80465a0af3855c7003fa57d41eeb6586b20eefa8cfdNick Lewycky do { 805abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky std::vector<WeakVH> Worklist; 806abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky Deferred.swap(Worklist); 807abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky 8082b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky DEBUG(dbgs() << "size of module: " << M.size() << '\n'); 809abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky DEBUG(dbgs() << "size of worklist: " << Worklist.size() << '\n'); 810b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 811b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky // Insert only strong functions and merge them. Strong function merging 812b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky // always deletes one of them. 813abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky for (std::vector<WeakVH>::iterator I = Worklist.begin(), 814abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky E = Worklist.end(); I != E; ++I) { 815abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky if (!*I) continue; 816abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky Function *F = cast<Function>(*I); 817b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() && 818abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky !F->mayBeOverridden()) { 819b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky ComparableFunction CF = ComparableFunction(F, TD); 820abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky Changed |= Insert(CF); 821b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky } 822b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky } 823b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 824b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky // Insert only weak functions and merge them. By doing these second we 825b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky // create thunks to the strong function when possible. When two weak 826b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky // functions are identical, we create a new strong function with two weak 827b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky // weak thunks to it which are identical but not mergable. 828abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky for (std::vector<WeakVH>::iterator I = Worklist.begin(), 829abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky E = Worklist.end(); I != E; ++I) { 830abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky if (!*I) continue; 831abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky Function *F = cast<Function>(*I); 832b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() && 833abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky F->mayBeOverridden()) { 834b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky ComparableFunction CF = ComparableFunction(F, TD); 835abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky Changed |= Insert(CF); 83665a0af3855c7003fa57d41eeb6586b20eefa8cfdNick Lewycky } 837579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 8382b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky DEBUG(dbgs() << "size of FnSet: " << FnSet.size() << '\n'); 839abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky } while (!Deferred.empty()); 840abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky 841abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky FnSet.clear(); 842579a0246616d76bc536de0e41edf069d091604beNick Lewycky 843579a0246616d76bc536de0e41edf069d091604beNick Lewycky return Changed; 844579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 845b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 846b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewyckybool DenseMapInfo<ComparableFunction>::isEqual(const ComparableFunction &LHS, 847b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky const ComparableFunction &RHS) { 848b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky if (LHS.getFunc() == RHS.getFunc() && 849b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky LHS.getHash() == RHS.getHash()) 850b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky return true; 851b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky if (!LHS.getFunc() || !RHS.getFunc()) 852b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky return false; 853b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky assert(LHS.getTD() == RHS.getTD() && 854b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky "Comparing functions for different targets"); 855e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky 856e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky bool inserted; 857e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky bool &result1 = LHS.getOrInsertCachedComparison(RHS, inserted); 858e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky if (!inserted) 859e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky return result1; 860e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky bool &result2 = RHS.getOrInsertCachedComparison(LHS, inserted); 861e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky if (!inserted) 862e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky return result1 = result2; 863e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky 864e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky return result1 = result2 = FunctionComparator(LHS.getTD(), LHS.getFunc(), 865e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky RHS.getFunc()).Compare(); 866b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky} 867