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" 48d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/DenseSet.h" 49d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/FoldingSet.h" 50d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/STLExtras.h" 51d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallSet.h" 52d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 530b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 540b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 550b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IRBuilder.h" 560b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/InlineAsm.h" 570b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 580b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/LLVMContext.h" 590b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 600b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Operator.h" 61579a0246616d76bc536de0e41edf069d091604beNick Lewycky#include "llvm/Pass.h" 626feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky#include "llvm/Support/CallSite.h" 63579a0246616d76bc536de0e41edf069d091604beNick Lewycky#include "llvm/Support/Debug.h" 64c25e7581b9b8088910da31702d4ca21c4734c6d7Torok Edwin#include "llvm/Support/ErrorHandling.h" 65f53de86cba33b63ecd54e16dcea735939c5b0e4aNick Lewycky#include "llvm/Support/ValueHandle.h" 66ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar#include "llvm/Support/raw_ostream.h" 6765a0af3855c7003fa57d41eeb6586b20eefa8cfdNick Lewycky#include <vector> 68579a0246616d76bc536de0e41edf069d091604beNick Lewyckyusing namespace llvm; 69579a0246616d76bc536de0e41edf069d091604beNick Lewycky 70579a0246616d76bc536de0e41edf069d091604beNick LewyckySTATISTIC(NumFunctionsMerged, "Number of functions merged"); 712b6c01b40b75e363e46b3ad7c598113eb98f34fbNick LewyckySTATISTIC(NumThunksWritten, "Number of thunks generated"); 72b38824f866447ccf8dd0c76656755b05bcede1b1Nick LewyckySTATISTIC(NumAliasesWritten, "Number of aliases generated"); 732b6c01b40b75e363e46b3ad7c598113eb98f34fbNick LewyckySTATISTIC(NumDoubleWeak, "Number of new functions created"); 74579a0246616d76bc536de0e41edf069d091604beNick Lewycky 7524a5f30f77fa2890329fa3a9165b54c13bbd51e7Benjamin Kramer/// Returns the type id for a type to be hashed. We turn pointer types into 7624a5f30f77fa2890329fa3a9165b54c13bbd51e7Benjamin Kramer/// integers here because the actual compare logic below considers pointers and 7724a5f30f77fa2890329fa3a9165b54c13bbd51e7Benjamin Kramer/// integers of the same size as equal. 7824a5f30f77fa2890329fa3a9165b54c13bbd51e7Benjamin Kramerstatic Type::TypeID getTypeIDForHash(Type *Ty) { 7924a5f30f77fa2890329fa3a9165b54c13bbd51e7Benjamin Kramer if (Ty->isPointerTy()) 8024a5f30f77fa2890329fa3a9165b54c13bbd51e7Benjamin Kramer return Type::IntegerTyID; 8124a5f30f77fa2890329fa3a9165b54c13bbd51e7Benjamin Kramer return Ty->getTypeID(); 8224a5f30f77fa2890329fa3a9165b54c13bbd51e7Benjamin Kramer} 8324a5f30f77fa2890329fa3a9165b54c13bbd51e7Benjamin Kramer 84468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky/// Creates a hash-code for the function which is the same for any two 85468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky/// functions that will compare equal, without looking at the instructions 86468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky/// inside the function. 87468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewyckystatic unsigned profileFunction(const Function *F) { 88db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner FunctionType *FTy = F->getFunctionType(); 89b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 90b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky FoldingSetNodeID ID; 91b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky ID.AddInteger(F->size()); 92b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky ID.AddInteger(F->getCallingConv()); 93b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky ID.AddBoolean(F->hasGC()); 94b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky ID.AddBoolean(FTy->isVarArg()); 9524a5f30f77fa2890329fa3a9165b54c13bbd51e7Benjamin Kramer ID.AddInteger(getTypeIDForHash(FTy->getReturnType())); 96b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i) 9724a5f30f77fa2890329fa3a9165b54c13bbd51e7Benjamin Kramer ID.AddInteger(getTypeIDForHash(FTy->getParamType(i))); 98b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky return ID.ComputeHash(); 99579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 100579a0246616d76bc536de0e41edf069d091604beNick Lewycky 1012b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewyckynamespace { 1022b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky 1038b5964381ecdba39ff4062085eb26832caa49238Nick Lewycky/// ComparableFunction - A struct that pairs together functions with a 1043574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow/// DataLayout so that we can keep them together as elements in the DenseSet. 105b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewyckyclass ComparableFunction { 106b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewyckypublic: 107b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky static const ComparableFunction EmptyKey; 108b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky static const ComparableFunction TombstoneKey; 1093574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow static DataLayout * const LookupOnly; 110b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky 1113574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow ComparableFunction(Function *Func, DataLayout *TD) 112468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky : Func(Func), Hash(profileFunction(Func)), TD(TD) {} 113b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 114b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky Function *getFunc() const { return Func; } 115b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky unsigned getHash() const { return Hash; } 1163574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow DataLayout *getTD() const { return TD; } 117b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 118b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky // Drops AssertingVH reference to the function. Outside of debug mode, this 119b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky // does nothing. 120b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky void release() { 121b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky assert(Func && 122b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky "Attempted to release function twice, or release empty/tombstone!"); 123b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky Func = NULL; 124b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky } 125b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky 126b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewyckyprivate: 127b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky explicit ComparableFunction(unsigned Hash) 128b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky : Func(NULL), Hash(Hash), TD(NULL) {} 129b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky 130b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky AssertingVH<Function> Func; 131b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky unsigned Hash; 1323574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow DataLayout *TD; 133b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky}; 134b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 135b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewyckyconst ComparableFunction ComparableFunction::EmptyKey = ComparableFunction(0); 136b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewyckyconst ComparableFunction ComparableFunction::TombstoneKey = 137b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky ComparableFunction(1); 1383574eca1b02600bac4e625297f4ecf745f4c4f32Micah VillmowDataLayout *const ComparableFunction::LookupOnly = (DataLayout*)(-1); 139b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky 1402b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky} 141b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky 142b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewyckynamespace llvm { 143b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky template <> 144b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky struct DenseMapInfo<ComparableFunction> { 145b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky static ComparableFunction getEmptyKey() { 146b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky return ComparableFunction::EmptyKey; 147b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky } 148b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky static ComparableFunction getTombstoneKey() { 149b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky return ComparableFunction::TombstoneKey; 150b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky } 151b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky static unsigned getHashValue(const ComparableFunction &CF) { 152b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky return CF.getHash(); 153b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky } 154b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky static bool isEqual(const ComparableFunction &LHS, 155b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky const ComparableFunction &RHS); 156b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky }; 157b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky} 158b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky 159b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewyckynamespace { 160b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky 161be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky/// FunctionComparator - Compares two functions to determine whether or not 1623574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow/// they will generate machine code with the same behaviour. DataLayout is 163be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky/// used if available. The comparator always fails conservatively (erring on the 164be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky/// side of claiming that two functions are different). 16578d4330fd83a94707b345e19f5277e7a46892689Nick Lewyckyclass FunctionComparator { 16678d4330fd83a94707b345e19f5277e7a46892689Nick Lewyckypublic: 1673574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow FunctionComparator(const DataLayout *TD, const Function *F1, 168f53de86cba33b63ecd54e16dcea735939c5b0e4aNick Lewycky const Function *F2) 169eafe863b6dc35f9ba5360685f300d16d0a5e0c3cNick Lewycky : F1(F1), F2(F2), TD(TD) {} 17078d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky 171468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky /// Test whether the two functions have equivalent behaviour. 172468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky bool compare(); 17378d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky 17478d4330fd83a94707b345e19f5277e7a46892689Nick Lewyckyprivate: 175468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky /// Test whether two basic blocks have equivalent behaviour. 176468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky bool compare(const BasicBlock *BB1, const BasicBlock *BB2); 17778d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky 178468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky /// Assign or look up previously assigned numbers for the two values, and 179468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky /// return whether the numbers are equal. Numbers are assigned in the order 180468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky /// visited. 181468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky bool enumerate(const Value *V1, const Value *V2); 18278d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky 183468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky /// Compare two Instructions for equivalence, similar to 184468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky /// Instruction::isSameOperationAs but with modifications to the type 185be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky /// comparison. 18678d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky bool isEquivalentOperation(const Instruction *I1, 18778d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky const Instruction *I2) const; 18878d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky 189468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky /// Compare two GEPs for equivalent pointer arithmetic. 19078d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky bool isEquivalentGEP(const GEPOperator *GEP1, const GEPOperator *GEP2); 19178d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky bool isEquivalentGEP(const GetElementPtrInst *GEP1, 192be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky const GetElementPtrInst *GEP2) { 19378d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky return isEquivalentGEP(cast<GEPOperator>(GEP1), cast<GEPOperator>(GEP2)); 19478d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky } 195287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 196468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky /// Compare two Types, treating all pointer types as equal. 19774d892433d617daa9728f2c52446b2cc2846553fBill Wendling bool isEquivalentType(Type *Ty1, Type *Ty2) const; 19878d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky 19978d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky // The two functions undergoing comparison. 200f53de86cba33b63ecd54e16dcea735939c5b0e4aNick Lewycky const Function *F1, *F2; 20178d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky 2023574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow const DataLayout *TD; 20378d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky 204eafe863b6dc35f9ba5360685f300d16d0a5e0c3cNick Lewycky DenseMap<const Value *, const Value *> id_map; 205eafe863b6dc35f9ba5360685f300d16d0a5e0c3cNick Lewycky DenseSet<const Value *> seen_values; 20678d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky}; 207285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 20878d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky} 20978d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky 210468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky// Any two pointers in the same address space are equivalent, intptr_t and 211468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky// pointers are equivalent. Otherwise, standard type equivalence rules apply. 21274d892433d617daa9728f2c52446b2cc2846553fBill Wendlingbool FunctionComparator::isEquivalentType(Type *Ty1, Type *Ty2) const { 213287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (Ty1 == Ty2) 214287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return true; 215207c193e7e9cc177115101333079e952a7676689Nick Lewycky if (Ty1->getTypeID() != Ty2->getTypeID()) { 21674d892433d617daa9728f2c52446b2cc2846553fBill Wendling if (TD) { 217ece6c6bb6329748b92403c06ac87f45c43485911Chandler Carruth LLVMContext &Ctx = Ty1->getContext(); 218ece6c6bb6329748b92403c06ac87f45c43485911Chandler Carruth if (isa<PointerType>(Ty1) && Ty2 == TD->getIntPtrType(Ctx)) return true; 219ece6c6bb6329748b92403c06ac87f45c43485911Chandler Carruth if (isa<PointerType>(Ty2) && Ty1 == TD->getIntPtrType(Ctx)) return true; 220207c193e7e9cc177115101333079e952a7676689Nick Lewycky } 221287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 222207c193e7e9cc177115101333079e952a7676689Nick Lewycky } 223287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 224628b337561cfb8ae862155fee710b5ca172b7a8eNick Lewycky switch (Ty1->getTypeID()) { 22533ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky default: 22633ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky llvm_unreachable("Unknown type!"); 2278246adc1f0e2d28374da3aeab864aee5ff03f3ffDuncan Sands // Fall through in Release mode. 22833ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky case Type::IntegerTyID: 229388f4918fbd8349a6c5b8403e31f65aa3408add6Nick Lewycky case Type::VectorTyID: 23033ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky // Ty1 == Ty2 would have returned true earlier. 23133ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky return false; 23233ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky 233287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky case Type::VoidTyID: 234287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky case Type::FloatTyID: 235287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky case Type::DoubleTyID: 236287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky case Type::X86_FP80TyID: 237287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky case Type::FP128TyID: 238287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky case Type::PPC_FP128TyID: 239287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky case Type::LabelTyID: 240287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky case Type::MetadataTyID: 241287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return true; 242287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 243287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky case Type::PointerTyID: { 244db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner PointerType *PTy1 = cast<PointerType>(Ty1); 245db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner PointerType *PTy2 = cast<PointerType>(Ty2); 246287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return PTy1->getAddressSpace() == PTy2->getAddressSpace(); 247287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky } 248287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 249287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky case Type::StructTyID: { 250db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner StructType *STy1 = cast<StructType>(Ty1); 251db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner StructType *STy2 = cast<StructType>(Ty2); 252287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (STy1->getNumElements() != STy2->getNumElements()) 253287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 254287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 255287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (STy1->isPacked() != STy2->isPacked()) 256287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 257287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 258287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky for (unsigned i = 0, e = STy1->getNumElements(); i != e; ++i) { 259287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (!isEquivalentType(STy1->getElementType(i), STy2->getElementType(i))) 260287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 261287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky } 262287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return true; 263287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky } 264287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 265287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky case Type::FunctionTyID: { 266db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner FunctionType *FTy1 = cast<FunctionType>(Ty1); 267db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner FunctionType *FTy2 = cast<FunctionType>(Ty2); 268287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (FTy1->getNumParams() != FTy2->getNumParams() || 269287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky FTy1->isVarArg() != FTy2->isVarArg()) 270287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 271287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 27274d892433d617daa9728f2c52446b2cc2846553fBill Wendling if (!isEquivalentType(FTy1->getReturnType(), FTy2->getReturnType())) 273287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 274287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 275287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky for (unsigned i = 0, e = FTy1->getNumParams(); i != e; ++i) { 276287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (!isEquivalentType(FTy1->getParamType(i), FTy2->getParamType(i))) 277287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 278287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky } 279287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return true; 280287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky } 281287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 282394ce41b7fcb64a35d5cd1c1fefc0e2225ebfc01Nick Lewycky case Type::ArrayTyID: { 283db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner ArrayType *ATy1 = cast<ArrayType>(Ty1); 284db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner ArrayType *ATy2 = cast<ArrayType>(Ty2); 285394ce41b7fcb64a35d5cd1c1fefc0e2225ebfc01Nick Lewycky return ATy1->getNumElements() == ATy2->getNumElements() && 286394ce41b7fcb64a35d5cd1c1fefc0e2225ebfc01Nick Lewycky isEquivalentType(ATy1->getElementType(), ATy2->getElementType()); 287287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky } 288287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky } 289287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky} 290287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 291468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky// Determine whether the two operations are the same except that pointer-to-A 292468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky// and pointer-to-B are equivalent. This should be kept in sync with 293468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky// Instruction::isSameOperationAs. 29478d4330fd83a94707b345e19f5277e7a46892689Nick Lewyckybool FunctionComparator::isEquivalentOperation(const Instruction *I1, 29578d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky const Instruction *I2) const { 29639c33e3b6344be1d1cc35ad9fb1b647fd8adfe65Nick Lewycky // Differences from Instruction::isSameOperationAs: 29739c33e3b6344be1d1cc35ad9fb1b647fd8adfe65Nick Lewycky // * replace type comparison with calls to isEquivalentType. 29839c33e3b6344be1d1cc35ad9fb1b647fd8adfe65Nick Lewycky // * we test for I->hasSameSubclassOptionalData (nuw/nsw/tail) at the top 29939c33e3b6344be1d1cc35ad9fb1b647fd8adfe65Nick Lewycky // * because of the above, we don't test for the tail bit on calls later on 300287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (I1->getOpcode() != I2->getOpcode() || 301287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky I1->getNumOperands() != I2->getNumOperands() || 30258cfa3b13752579c86cf85270d49f9ced0942f2fDan Gohman !isEquivalentType(I1->getType(), I2->getType()) || 30358cfa3b13752579c86cf85270d49f9ced0942f2fDan Gohman !I1->hasSameSubclassOptionalData(I2)) 304287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 305287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 306287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky // We have two instructions of identical opcode and #operands. Check to see 307287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky // if all operands are the same type 308287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky for (unsigned i = 0, e = I1->getNumOperands(); i != e; ++i) 309287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (!isEquivalentType(I1->getOperand(i)->getType(), 310287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky I2->getOperand(i)->getType())) 311287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 312287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 313287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky // Check special state that is a part of some instructions. 314287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (const LoadInst *LI = dyn_cast<LoadInst>(I1)) 315287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return LI->isVolatile() == cast<LoadInst>(I2)->isVolatile() && 3163d30b435e2b3d0e7480019577f48472b51133c21Eli Friedman LI->getAlignment() == cast<LoadInst>(I2)->getAlignment() && 3173d30b435e2b3d0e7480019577f48472b51133c21Eli Friedman LI->getOrdering() == cast<LoadInst>(I2)->getOrdering() && 3183d30b435e2b3d0e7480019577f48472b51133c21Eli Friedman LI->getSynchScope() == cast<LoadInst>(I2)->getSynchScope(); 319287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (const StoreInst *SI = dyn_cast<StoreInst>(I1)) 320287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return SI->isVolatile() == cast<StoreInst>(I2)->isVolatile() && 3213d30b435e2b3d0e7480019577f48472b51133c21Eli Friedman SI->getAlignment() == cast<StoreInst>(I2)->getAlignment() && 3223d30b435e2b3d0e7480019577f48472b51133c21Eli Friedman SI->getOrdering() == cast<StoreInst>(I2)->getOrdering() && 3233d30b435e2b3d0e7480019577f48472b51133c21Eli Friedman SI->getSynchScope() == cast<StoreInst>(I2)->getSynchScope(); 324287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (const CmpInst *CI = dyn_cast<CmpInst>(I1)) 325287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return CI->getPredicate() == cast<CmpInst>(I2)->getPredicate(); 326287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (const CallInst *CI = dyn_cast<CallInst>(I1)) 32739c33e3b6344be1d1cc35ad9fb1b647fd8adfe65Nick Lewycky return CI->getCallingConv() == cast<CallInst>(I2)->getCallingConv() && 328f6c63c23203ca4c4aa89efa2bff722bb479cfe3cNick Lewycky CI->getAttributes() == cast<CallInst>(I2)->getAttributes(); 329287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky if (const InvokeInst *CI = dyn_cast<InvokeInst>(I1)) 330287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return CI->getCallingConv() == cast<InvokeInst>(I2)->getCallingConv() && 331f6c63c23203ca4c4aa89efa2bff722bb479cfe3cNick Lewycky CI->getAttributes() == cast<InvokeInst>(I2)->getAttributes(); 33255ba816883842e793cdeb32fcb805c4e011b527fEli Friedman if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(I1)) 33355ba816883842e793cdeb32fcb805c4e011b527fEli Friedman return IVI->getIndices() == cast<InsertValueInst>(I2)->getIndices(); 33455ba816883842e793cdeb32fcb805c4e011b527fEli Friedman if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(I1)) 33555ba816883842e793cdeb32fcb805c4e011b527fEli Friedman return EVI->getIndices() == cast<ExtractValueInst>(I2)->getIndices(); 33655ba816883842e793cdeb32fcb805c4e011b527fEli Friedman if (const FenceInst *FI = dyn_cast<FenceInst>(I1)) 33755ba816883842e793cdeb32fcb805c4e011b527fEli Friedman return FI->getOrdering() == cast<FenceInst>(I2)->getOrdering() && 33855ba816883842e793cdeb32fcb805c4e011b527fEli Friedman FI->getSynchScope() == cast<FenceInst>(I2)->getSynchScope(); 33955ba816883842e793cdeb32fcb805c4e011b527fEli Friedman if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(I1)) 34055ba816883842e793cdeb32fcb805c4e011b527fEli Friedman return CXI->isVolatile() == cast<AtomicCmpXchgInst>(I2)->isVolatile() && 34155ba816883842e793cdeb32fcb805c4e011b527fEli Friedman CXI->getOrdering() == cast<AtomicCmpXchgInst>(I2)->getOrdering() && 34255ba816883842e793cdeb32fcb805c4e011b527fEli Friedman CXI->getSynchScope() == cast<AtomicCmpXchgInst>(I2)->getSynchScope(); 34355ba816883842e793cdeb32fcb805c4e011b527fEli Friedman if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(I1)) 34455ba816883842e793cdeb32fcb805c4e011b527fEli Friedman return RMWI->getOperation() == cast<AtomicRMWInst>(I2)->getOperation() && 34555ba816883842e793cdeb32fcb805c4e011b527fEli Friedman RMWI->isVolatile() == cast<AtomicRMWInst>(I2)->isVolatile() && 34655ba816883842e793cdeb32fcb805c4e011b527fEli Friedman RMWI->getOrdering() == cast<AtomicRMWInst>(I2)->getOrdering() && 34755ba816883842e793cdeb32fcb805c4e011b527fEli Friedman RMWI->getSynchScope() == cast<AtomicRMWInst>(I2)->getSynchScope(); 348287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 349287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return true; 350579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 351579a0246616d76bc536de0e41edf069d091604beNick Lewycky 352468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky// Determine whether two GEP operations perform the same underlying arithmetic. 35378d4330fd83a94707b345e19f5277e7a46892689Nick Lewyckybool FunctionComparator::isEquivalentGEP(const GEPOperator *GEP1, 35478d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky const GEPOperator *GEP2) { 35578d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky // When we have target data, we can reduce the GEP down to the value in bytes 35678d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky // added to the address. 35798281a20503896349bd152e2dfe87435d3a6aadaNuno Lopes unsigned BitWidth = TD ? TD->getPointerSizeInBits() : 1; 35898281a20503896349bd152e2dfe87435d3a6aadaNuno Lopes APInt Offset1(BitWidth, 0), Offset2(BitWidth, 0); 35998281a20503896349bd152e2dfe87435d3a6aadaNuno Lopes if (TD && 36098281a20503896349bd152e2dfe87435d3a6aadaNuno Lopes GEP1->accumulateConstantOffset(*TD, Offset1) && 36198281a20503896349bd152e2dfe87435d3a6aadaNuno Lopes GEP2->accumulateConstantOffset(*TD, Offset2)) { 36233ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky return Offset1 == Offset2; 36333ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky } 364579a0246616d76bc536de0e41edf069d091604beNick Lewycky 36533ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky if (GEP1->getPointerOperand()->getType() != 36633ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky GEP2->getPointerOperand()->getType()) 36733ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky return false; 368579a0246616d76bc536de0e41edf069d091604beNick Lewycky 36933ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky if (GEP1->getNumOperands() != GEP2->getNumOperands()) 370579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 371579a0246616d76bc536de0e41edf069d091604beNick Lewycky 37233ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky for (unsigned i = 0, e = GEP1->getNumOperands(); i != e; ++i) { 373468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky if (!enumerate(GEP1->getOperand(i), GEP2->getOperand(i))) 37433ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky return false; 375579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 376579a0246616d76bc536de0e41edf069d091604beNick Lewycky 37733ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky return true; 378579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 379579a0246616d76bc536de0e41edf069d091604beNick Lewycky 380468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky// Compare two values used by the two functions under pair-wise comparison. If 381468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky// this is the first time the values are seen, they're added to the mapping so 382468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky// that we will detect mismatches on next use. 383468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewyckybool FunctionComparator::enumerate(const Value *V1, const Value *V2) { 38478d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky // Check for function @f1 referring to itself and function @f2 referring to 38578d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky // itself, or referring to each other, or both referring to either of them. 38678d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky // They're all equivalent if the two functions are otherwise equivalent. 387c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky if (V1 == F1 && V2 == F2) 388c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky return true; 389c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky if (V1 == F2 && V2 == F1) 390c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky return true; 391579a0246616d76bc536de0e41edf069d091604beNick Lewycky 3929c1858cf4a91d0f373d2315ccf834adedd197e6eBenjamin Kramer if (const Constant *C1 = dyn_cast<Constant>(V1)) { 39325296e25fd30806b4a1f2348cbf73f227962be86Nick Lewycky if (V1 == V2) return true; 39425296e25fd30806b4a1f2348cbf73f227962be86Nick Lewycky const Constant *C2 = dyn_cast<Constant>(V2); 39525296e25fd30806b4a1f2348cbf73f227962be86Nick Lewycky if (!C2) return false; 39625296e25fd30806b4a1f2348cbf73f227962be86Nick Lewycky // TODO: constant expressions with GEP or references to F1 or F2. 39725296e25fd30806b4a1f2348cbf73f227962be86Nick Lewycky if (C1->isNullValue() && C2->isNullValue() && 39856cb2298663017eb77aa4f4dda8db7ecd1b58173Bill Wendling isEquivalentType(C1->getType(), C2->getType())) 39925296e25fd30806b4a1f2348cbf73f227962be86Nick Lewycky return true; 400c9d69489ebe12f265828c48defb0278f6bd9121fNick Lewycky // Try bitcasting C2 to C1's type. If the bitcast is legal and returns C1 401c9d69489ebe12f265828c48defb0278f6bd9121fNick Lewycky // then they must have equal bit patterns. 40225296e25fd30806b4a1f2348cbf73f227962be86Nick Lewycky return C1->getType()->canLosslesslyBitCastTo(C2->getType()) && 40325296e25fd30806b4a1f2348cbf73f227962be86Nick Lewycky C1 == ConstantExpr::getBitCast(const_cast<Constant*>(C2), C1->getType()); 40425296e25fd30806b4a1f2348cbf73f227962be86Nick Lewycky } 405579a0246616d76bc536de0e41edf069d091604beNick Lewycky 406d489332549f226701825de990a2f5869dad96aceNick Lewycky if (isa<InlineAsm>(V1) || isa<InlineAsm>(V2)) 407d489332549f226701825de990a2f5869dad96aceNick Lewycky return V1 == V2; 408579a0246616d76bc536de0e41edf069d091604beNick Lewycky 409eafe863b6dc35f9ba5360685f300d16d0a5e0c3cNick Lewycky // Check that V1 maps to V2. If we find a value that V1 maps to then we simply 410eafe863b6dc35f9ba5360685f300d16d0a5e0c3cNick Lewycky // check whether it's equal to V2. When there is no mapping then we need to 411eafe863b6dc35f9ba5360685f300d16d0a5e0c3cNick Lewycky // ensure that V2 isn't already equivalent to something else. For this 412eafe863b6dc35f9ba5360685f300d16d0a5e0c3cNick Lewycky // purpose, we track the V2 values in a set. 41333ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky 414eafe863b6dc35f9ba5360685f300d16d0a5e0c3cNick Lewycky const Value *&map_elem = id_map[V1]; 415eafe863b6dc35f9ba5360685f300d16d0a5e0c3cNick Lewycky if (map_elem) 416eafe863b6dc35f9ba5360685f300d16d0a5e0c3cNick Lewycky return map_elem == V2; 417eafe863b6dc35f9ba5360685f300d16d0a5e0c3cNick Lewycky if (!seen_values.insert(V2).second) 418eafe863b6dc35f9ba5360685f300d16d0a5e0c3cNick Lewycky return false; 419eafe863b6dc35f9ba5360685f300d16d0a5e0c3cNick Lewycky map_elem = V2; 420eafe863b6dc35f9ba5360685f300d16d0a5e0c3cNick Lewycky return true; 42133ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky} 42233ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky 423468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky// Test whether two basic blocks have equivalent behaviour. 424468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewyckybool FunctionComparator::compare(const BasicBlock *BB1, const BasicBlock *BB2) { 42578d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky BasicBlock::const_iterator F1I = BB1->begin(), F1E = BB1->end(); 42678d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky BasicBlock::const_iterator F2I = BB2->begin(), F2E = BB2->end(); 427579a0246616d76bc536de0e41edf069d091604beNick Lewycky 42833ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky do { 429468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky if (!enumerate(F1I, F2I)) 430579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 431579a0246616d76bc536de0e41edf069d091604beNick Lewycky 43278d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (const GetElementPtrInst *GEP1 = dyn_cast<GetElementPtrInst>(F1I)) { 43378d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky const GetElementPtrInst *GEP2 = dyn_cast<GetElementPtrInst>(F2I); 43478d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (!GEP2) 43578d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky return false; 436579a0246616d76bc536de0e41edf069d091604beNick Lewycky 437468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky if (!enumerate(GEP1->getPointerOperand(), GEP2->getPointerOperand())) 438911ae391e85ead1bb11895562a6bbdb2c0f8ebd2Nick Lewycky return false; 439579a0246616d76bc536de0e41edf069d091604beNick Lewycky 44033ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky if (!isEquivalentGEP(GEP1, GEP2)) 441911ae391e85ead1bb11895562a6bbdb2c0f8ebd2Nick Lewycky return false; 44233ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky } else { 44378d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (!isEquivalentOperation(F1I, F2I)) 444579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 445579a0246616d76bc536de0e41edf069d091604beNick Lewycky 44678d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky assert(F1I->getNumOperands() == F2I->getNumOperands()); 44778d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky for (unsigned i = 0, e = F1I->getNumOperands(); i != e; ++i) { 44878d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky Value *OpF1 = F1I->getOperand(i); 44978d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky Value *OpF2 = F2I->getOperand(i); 450579a0246616d76bc536de0e41edf069d091604beNick Lewycky 451468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky if (!enumerate(OpF1, OpF2)) 452911ae391e85ead1bb11895562a6bbdb2c0f8ebd2Nick Lewycky return false; 45333ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky 45478d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (OpF1->getValueID() != OpF2->getValueID() || 45578d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky !isEquivalentType(OpF1->getType(), OpF2->getType())) 456579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 457579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 458579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 459579a0246616d76bc536de0e41edf069d091604beNick Lewycky 46078d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky ++F1I, ++F2I; 46178d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky } while (F1I != F1E && F2I != F2E); 462579a0246616d76bc536de0e41edf069d091604beNick Lewycky 46378d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky return F1I == F1E && F2I == F2E; 464579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 465579a0246616d76bc536de0e41edf069d091604beNick Lewycky 466468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky// Test whether the two functions have equivalent behaviour. 467468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewyckybool FunctionComparator::compare() { 468579a0246616d76bc536de0e41edf069d091604beNick Lewycky // We need to recheck everything, but check the things that weren't included 469579a0246616d76bc536de0e41edf069d091604beNick Lewycky // in the hash first. 470579a0246616d76bc536de0e41edf069d091604beNick Lewycky 47178d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (F1->getAttributes() != F2->getAttributes()) 472579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 473579a0246616d76bc536de0e41edf069d091604beNick Lewycky 47478d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (F1->hasGC() != F2->hasGC()) 475579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 476579a0246616d76bc536de0e41edf069d091604beNick Lewycky 47778d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (F1->hasGC() && F1->getGC() != F2->getGC()) 478579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 479579a0246616d76bc536de0e41edf069d091604beNick Lewycky 48078d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (F1->hasSection() != F2->hasSection()) 481579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 482579a0246616d76bc536de0e41edf069d091604beNick Lewycky 48378d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (F1->hasSection() && F1->getSection() != F2->getSection()) 484579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 485579a0246616d76bc536de0e41edf069d091604beNick Lewycky 48678d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (F1->isVarArg() != F2->isVarArg()) 487287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky return false; 488287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 489579a0246616d76bc536de0e41edf069d091604beNick Lewycky // TODO: if it's internal and only used in direct calls, we could handle this 490579a0246616d76bc536de0e41edf069d091604beNick Lewycky // case too. 49178d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (F1->getCallingConv() != F2->getCallingConv()) 492579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 493579a0246616d76bc536de0e41edf069d091604beNick Lewycky 49478d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (!isEquivalentType(F1->getFunctionType(), F2->getFunctionType())) 495579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 496579a0246616d76bc536de0e41edf069d091604beNick Lewycky 49778d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky assert(F1->arg_size() == F2->arg_size() && 4982b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky "Identically typed functions have different numbers of args!"); 499579a0246616d76bc536de0e41edf069d091604beNick Lewycky 50033ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky // Visit the arguments so that they get enumerated in the order they're 50133ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky // passed in. 50278d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky for (Function::const_arg_iterator f1i = F1->arg_begin(), 50378d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky f2i = F2->arg_begin(), f1e = F1->arg_end(); f1i != f1e; ++f1i, ++f2i) { 504468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky if (!enumerate(f1i, f2i)) 5052b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky llvm_unreachable("Arguments repeat!"); 50633ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky } 507579a0246616d76bc536de0e41edf069d091604beNick Lewycky 508be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky // We do a CFG-ordered walk since the actual ordering of the blocks in the 509be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky // linked list is immaterial. Our walk starts at the entry block for both 51078d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky // functions, then takes each block from each terminator in order. As an 51178d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky // artifact, this also means that unreachable blocks are ignored. 51278d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky SmallVector<const BasicBlock *, 8> F1BBs, F2BBs; 51378d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky SmallSet<const BasicBlock *, 128> VisitedBBs; // in terms of F1. 514c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky 51578d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky F1BBs.push_back(&F1->getEntryBlock()); 51678d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky F2BBs.push_back(&F2->getEntryBlock()); 517c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky 51878d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky VisitedBBs.insert(F1BBs[0]); 51978d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky while (!F1BBs.empty()) { 52078d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky const BasicBlock *F1BB = F1BBs.pop_back_val(); 52178d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky const BasicBlock *F2BB = F2BBs.pop_back_val(); 522c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky 523468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky if (!enumerate(F1BB, F2BB) || !compare(F1BB, F2BB)) 524579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 525c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky 52678d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky const TerminatorInst *F1TI = F1BB->getTerminator(); 52778d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky const TerminatorInst *F2TI = F2BB->getTerminator(); 528c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky 52978d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky assert(F1TI->getNumSuccessors() == F2TI->getNumSuccessors()); 53078d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky for (unsigned i = 0, e = F1TI->getNumSuccessors(); i != e; ++i) { 53178d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky if (!VisitedBBs.insert(F1TI->getSuccessor(i))) 532911ae391e85ead1bb11895562a6bbdb2c0f8ebd2Nick Lewycky continue; 533c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky 53478d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky F1BBs.push_back(F1TI->getSuccessor(i)); 53578d4330fd83a94707b345e19f5277e7a46892689Nick Lewycky F2BBs.push_back(F2TI->getSuccessor(i)); 53633ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky } 537579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 538579a0246616d76bc536de0e41edf069d091604beNick Lewycky return true; 539579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 540579a0246616d76bc536de0e41edf069d091604beNick Lewycky 541285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewyckynamespace { 542285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 543285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky/// MergeFunctions finds functions which will generate identical machine code, 544285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky/// by considering all pointer types to be equivalent. Once identified, 545285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky/// MergeFunctions will fold them by replacing a call to one to a call to a 546285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky/// bitcast of the other. 547285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky/// 548285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewyckyclass MergeFunctions : public ModulePass { 549285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewyckypublic: 550285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky static char ID; 551285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky MergeFunctions() 552285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky : ModulePass(ID), HasGlobalAliases(false) { 553285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky initializeMergeFunctionsPass(*PassRegistry::getPassRegistry()); 554285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky } 555285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 556285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky bool runOnModule(Module &M); 557285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 558285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewyckyprivate: 559285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky typedef DenseSet<ComparableFunction> FnSetType; 560285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 561285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky /// A work queue of functions that may have been modified and should be 562285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky /// analyzed again. 563285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky std::vector<WeakVH> Deferred; 564285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 565285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky /// Insert a ComparableFunction into the FnSet, or merge it away if it's 566285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky /// equal to one that's already present. 567468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky bool insert(ComparableFunction &NewF); 568285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 569285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky /// Remove a Function from the FnSet and queue it up for a second sweep of 570285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky /// analysis. 571468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky void remove(Function *F); 572285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 573285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky /// Find the functions that use this Value and remove them from FnSet and 574285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky /// queue the functions. 575468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky void removeUsers(Value *V); 576285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 577285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky /// Replace all direct calls of Old with calls of New. Will bitcast New if 578285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky /// necessary to make types match. 579285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky void replaceDirectCallers(Function *Old, Function *New); 580285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 581468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky /// Merge two equivalent functions. Upon completion, G may be deleted, or may 582468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky /// be converted into a thunk. In either case, it should never be visited 583468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky /// again. 584468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky void mergeTwoFunctions(Function *F, Function *G); 585285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 586468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky /// Replace G with a thunk or an alias to F. Deletes G. 587468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky void writeThunkOrAlias(Function *F, Function *G); 588285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 589468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky /// Replace G with a simple tail call to bitcast(F). Also replace direct uses 590468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky /// of G with bitcast(F). Deletes G. 591468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky void writeThunk(Function *F, Function *G); 592285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 593468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky /// Replace G with an alias to F. Deletes G. 594468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky void writeAlias(Function *F, Function *G); 595285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 596468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky /// The set of all distinct functions. Use the insert() and remove() methods 597468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky /// to modify it. 598285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky FnSetType FnSet; 599285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 6003574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow /// DataLayout for more accurate GEP comparisons. May be NULL. 6013574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow DataLayout *TD; 602285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 603285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky /// Whether or not the target supports global aliases. 604285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky bool HasGlobalAliases; 605285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky}; 606285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 607285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky} // end anonymous namespace 608285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 609285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewyckychar MergeFunctions::ID = 0; 610285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick LewyckyINITIALIZE_PASS(MergeFunctions, "mergefunc", "Merge Functions", false, false) 611285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 612285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick LewyckyModulePass *llvm::createMergeFunctionsPass() { 613285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky return new MergeFunctions(); 614285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky} 615285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 616285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewyckybool MergeFunctions::runOnModule(Module &M) { 617285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky bool Changed = false; 6183574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow TD = getAnalysisIfAvailable<DataLayout>(); 619285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 620285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) { 621285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky if (!I->isDeclaration() && !I->hasAvailableExternallyLinkage()) 622285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky Deferred.push_back(WeakVH(I)); 623285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky } 624285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky FnSet.resize(Deferred.size()); 625285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 626285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky do { 627285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky std::vector<WeakVH> Worklist; 628285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky Deferred.swap(Worklist); 629285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 630285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky DEBUG(dbgs() << "size of module: " << M.size() << '\n'); 631285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky DEBUG(dbgs() << "size of worklist: " << Worklist.size() << '\n'); 632285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 633285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky // Insert only strong functions and merge them. Strong function merging 634285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky // always deletes one of them. 635285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky for (std::vector<WeakVH>::iterator I = Worklist.begin(), 636285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky E = Worklist.end(); I != E; ++I) { 637285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky if (!*I) continue; 638285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky Function *F = cast<Function>(*I); 639285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() && 640285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky !F->mayBeOverridden()) { 641285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky ComparableFunction CF = ComparableFunction(F, TD); 642468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky Changed |= insert(CF); 643285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky } 644285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky } 645285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 646285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky // Insert only weak functions and merge them. By doing these second we 647285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky // create thunks to the strong function when possible. When two weak 648285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky // functions are identical, we create a new strong function with two weak 649285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky // weak thunks to it which are identical but not mergable. 650285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky for (std::vector<WeakVH>::iterator I = Worklist.begin(), 651285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky E = Worklist.end(); I != E; ++I) { 652285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky if (!*I) continue; 653285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky Function *F = cast<Function>(*I); 654285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() && 655285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky F->mayBeOverridden()) { 656285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky ComparableFunction CF = ComparableFunction(F, TD); 657468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky Changed |= insert(CF); 658285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky } 659285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky } 660285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky DEBUG(dbgs() << "size of FnSet: " << FnSet.size() << '\n'); 661285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky } while (!Deferred.empty()); 662285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 663285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky FnSet.clear(); 664285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 665285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky return Changed; 666285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky} 667285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 668285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewyckybool DenseMapInfo<ComparableFunction>::isEqual(const ComparableFunction &LHS, 669285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky const ComparableFunction &RHS) { 670285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky if (LHS.getFunc() == RHS.getFunc() && 671285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky LHS.getHash() == RHS.getHash()) 672285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky return true; 673285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky if (!LHS.getFunc() || !RHS.getFunc()) 674285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky return false; 6753ba974a1c535563bff9a160996ad015a2a56cc05Nick Lewycky 6763ba974a1c535563bff9a160996ad015a2a56cc05Nick Lewycky // One of these is a special "underlying pointer comparison only" object. 6773ba974a1c535563bff9a160996ad015a2a56cc05Nick Lewycky if (LHS.getTD() == ComparableFunction::LookupOnly || 6783ba974a1c535563bff9a160996ad015a2a56cc05Nick Lewycky RHS.getTD() == ComparableFunction::LookupOnly) 6793ba974a1c535563bff9a160996ad015a2a56cc05Nick Lewycky return false; 6803ba974a1c535563bff9a160996ad015a2a56cc05Nick Lewycky 681285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky assert(LHS.getTD() == RHS.getTD() && 682285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky "Comparing functions for different targets"); 683285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 6848eb3e54592ae7d7b43454fcd08d0da7a51ecd4d8Nick Lewycky return FunctionComparator(LHS.getTD(), LHS.getFunc(), 6858eb3e54592ae7d7b43454fcd08d0da7a51ecd4d8Nick Lewycky RHS.getFunc()).compare(); 686285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky} 687285cf8040da6245d5dbc9ebfac8a8caf3647caf4Nick Lewycky 688468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky// Replace direct callers of Old with New. 689b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewyckyvoid MergeFunctions::replaceDirectCallers(Function *Old, Function *New) { 690b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky Constant *BitcastNew = ConstantExpr::getBitCast(New, Old->getType()); 691b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky for (Value::use_iterator UI = Old->use_begin(), UE = Old->use_end(); 692b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky UI != UE;) { 693b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky Value::use_iterator TheIter = UI; 694b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky ++UI; 695b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky CallSite CS(*TheIter); 696b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky if (CS && CS.isCallee(TheIter)) { 697468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky remove(CS.getInstruction()->getParent()->getParent()); 698b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky TheIter.getUse().set(BitcastNew); 699b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky } 700b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky } 701b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky} 702b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky 703468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky// Replace G with an alias to F if possible, or else a thunk to F. Deletes G. 704468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewyckyvoid MergeFunctions::writeThunkOrAlias(Function *F, Function *G) { 705b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky if (HasGlobalAliases && G->hasUnnamedAddr()) { 706b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky if (G->hasExternalLinkage() || G->hasLocalLinkage() || 707b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky G->hasWeakLinkage()) { 708468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky writeAlias(F, G); 709b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky return; 710b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky } 711b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky } 712b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky 713468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky writeThunk(F, G); 714b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky} 715b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky 716468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky// Replace G with a simple tail call to bitcast(F). Also replace direct uses 717468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky// of G with bitcast(F). Deletes G. 718468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewyckyvoid MergeFunctions::writeThunk(Function *F, Function *G) { 71933ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky if (!G->mayBeOverridden()) { 72033ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky // Redirect direct callers of G to F. 721b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky replaceDirectCallers(G, F); 72233ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky } 72333ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky 7242b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky // If G was internal then we may have replaced all uses of G with F. If so, 725c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky // stop here and delete G. There's no need for a thunk. 726c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky if (G->hasLocalLinkage() && G->use_empty()) { 727c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky G->eraseFromParent(); 728c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky return; 729c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky } 730c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky 7318728d7a3ea7cad3297f9ab0984358007238ae83aNick Lewycky Function *NewG = Function::Create(G->getFunctionType(), G->getLinkage(), "", 7328728d7a3ea7cad3297f9ab0984358007238ae83aNick Lewycky G->getParent()); 7331d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *BB = BasicBlock::Create(F->getContext(), "", NewG); 734be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky IRBuilder<false> Builder(BB); 735287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 73633ab0b15689abd32f72a5417cd104bde19f4b4aaNick Lewycky SmallVector<Value *, 16> Args; 737287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky unsigned i = 0; 738db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner FunctionType *FFTy = F->getFunctionType(); 739287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky for (Function::arg_iterator AI = NewG->arg_begin(), AE = NewG->arg_end(); 740287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky AI != AE; ++AI) { 741be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky Args.push_back(Builder.CreateBitCast(AI, FFTy->getParamType(i))); 742287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky ++i; 743579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 744579a0246616d76bc536de0e41edf069d091604beNick Lewycky 745a3efbb15ddd5aa9006564cd79086723640084878Jay Foad CallInst *CI = Builder.CreateCall(F, Args); 746287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky CI->setTailCall(); 747b3c36c9c9aba3fce8ae35b52eda4192531a9d3dfNick Lewycky CI->setCallingConv(F->getCallingConv()); 748f012705c7e4ca8cf90b6b734ce1d5355daca5ba5Benjamin Kramer if (NewG->getReturnType()->isVoidTy()) { 749be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky Builder.CreateRetVoid(); 750287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky } else { 75174d892433d617daa9728f2c52446b2cc2846553fBill Wendling Type *RetTy = NewG->getReturnType(); 75274d892433d617daa9728f2c52446b2cc2846553fBill Wendling if (CI->getType()->isIntegerTy() && RetTy->isPointerTy()) 75374d892433d617daa9728f2c52446b2cc2846553fBill Wendling Builder.CreateRet(Builder.CreateIntToPtr(CI, RetTy)); 75474d892433d617daa9728f2c52446b2cc2846553fBill Wendling else if (CI->getType()->isPointerTy() && RetTy->isIntegerTy()) 75574d892433d617daa9728f2c52446b2cc2846553fBill Wendling Builder.CreateRet(Builder.CreatePtrToInt(CI, RetTy)); 75674d892433d617daa9728f2c52446b2cc2846553fBill Wendling else 75774d892433d617daa9728f2c52446b2cc2846553fBill Wendling Builder.CreateRet(Builder.CreateBitCast(CI, RetTy)); 7586feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky } 7596feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky 760287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky NewG->copyAttributesFrom(G); 761287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky NewG->takeName(G); 762468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky removeUsers(G); 763287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky G->replaceAllUsesWith(NewG); 764287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky G->eraseFromParent(); 7652b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky 766468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky DEBUG(dbgs() << "writeThunk: " << NewG->getName() << '\n'); 7672b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky ++NumThunksWritten; 768579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 769579a0246616d76bc536de0e41edf069d091604beNick Lewycky 770468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky// Replace G with an alias to F and delete G. 771468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewyckyvoid MergeFunctions::writeAlias(Function *F, Function *G) { 772b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky Constant *BitcastF = ConstantExpr::getBitCast(F, G->getType()); 773b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky GlobalAlias *GA = new GlobalAlias(G->getType(), G->getLinkage(), "", 774b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky BitcastF, G->getParent()); 775b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky F->setAlignment(std::max(F->getAlignment(), G->getAlignment())); 776b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky GA->takeName(G); 777b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky GA->setVisibility(G->getVisibility()); 778468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky removeUsers(G); 779b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky G->replaceAllUsesWith(GA); 780b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky G->eraseFromParent(); 781b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky 782468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky DEBUG(dbgs() << "writeAlias: " << GA->getName() << '\n'); 783b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky ++NumAliasesWritten; 784b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky} 785b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky 786468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky// Merge two equivalent functions. Upon completion, Function G is deleted. 787468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewyckyvoid MergeFunctions::mergeTwoFunctions(Function *F, Function *G) { 7882b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky if (F->mayBeOverridden()) { 7892b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky assert(G->mayBeOverridden()); 7908728d7a3ea7cad3297f9ab0984358007238ae83aNick Lewycky 791b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky if (HasGlobalAliases) { 792b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky // Make them both thunks to the same internal function. 793b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky Function *H = Function::Create(F->getFunctionType(), F->getLinkage(), "", 794b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky F->getParent()); 795b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky H->copyAttributesFrom(F); 796b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky H->takeName(F); 797468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky removeUsers(F); 798b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky F->replaceAllUsesWith(H); 7998728d7a3ea7cad3297f9ab0984358007238ae83aNick Lewycky 800b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky unsigned MaxAlignment = std::max(G->getAlignment(), H->getAlignment()); 8013221834f8a6216d01a7e1d1201bd14eafd79cff3Nick Lewycky 802468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky writeAlias(F, G); 803468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky writeAlias(F, H); 8048728d7a3ea7cad3297f9ab0984358007238ae83aNick Lewycky 805b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky F->setAlignment(MaxAlignment); 806b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky F->setLinkage(GlobalValue::PrivateLinkage); 807b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky } else { 808b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky // We can't merge them. Instead, pick one and update all direct callers 809b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky // to call it and hope that we improve the instruction cache hit rate. 810b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky replaceDirectCallers(G, F); 811b38824f866447ccf8dd0c76656755b05bcede1b1Nick Lewycky } 8122b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky 8132b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky ++NumDoubleWeak; 814c9dcbed6a39f3aa2562de070bb15670d81c38650Nick Lewycky } else { 815468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky writeThunkOrAlias(F, G); 816579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 817579a0246616d76bc536de0e41edf069d091604beNick Lewycky 818287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky ++NumFunctionsMerged; 819579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 820579a0246616d76bc536de0e41edf069d091604beNick Lewycky 821468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky// Insert a ComparableFunction into the FnSet, or merge it away if equal to one 822468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky// that was already inserted. 823468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewyckybool MergeFunctions::insert(ComparableFunction &NewF) { 824b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky std::pair<FnSetType::iterator, bool> Result = FnSet.insert(NewF); 8253ba974a1c535563bff9a160996ad015a2a56cc05Nick Lewycky if (Result.second) { 8263ba974a1c535563bff9a160996ad015a2a56cc05Nick Lewycky DEBUG(dbgs() << "Inserting as unique: " << NewF.getFunc()->getName() << '\n'); 827b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky return false; 8283ba974a1c535563bff9a160996ad015a2a56cc05Nick Lewycky } 829f53de86cba33b63ecd54e16dcea735939c5b0e4aNick Lewycky 830b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky const ComparableFunction &OldF = *Result.first; 831b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 832b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky // Never thunk a strong function to a weak function. 8332b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky assert(!OldF.getFunc()->mayBeOverridden() || 8342b6c01b40b75e363e46b3ad7c598113eb98f34fbNick Lewycky NewF.getFunc()->mayBeOverridden()); 835b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 836b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky DEBUG(dbgs() << " " << OldF.getFunc()->getName() << " == " 837b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky << NewF.getFunc()->getName() << '\n'); 838b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 839b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky Function *DeleteF = NewF.getFunc(); 840b0e17779ba401feae32cdd1dd4096d49c1746153Nick Lewycky NewF.release(); 841468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky mergeTwoFunctions(OldF.getFunc(), DeleteF); 842b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky return true; 843be04fdeb6c46e92fdeda7535c5912d072eff008cNick Lewycky} 844287de607dc3e05aa287edf4e3b6aa29e6c4517c9Nick Lewycky 845468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky// Remove a function from FnSet. If it was already in FnSet, add it to Deferred 846468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky// so that we'll look at it in the next round. 847468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewyckyvoid MergeFunctions::remove(Function *F) { 8483ba974a1c535563bff9a160996ad015a2a56cc05Nick Lewycky // We need to make sure we remove F, not a function "equal" to F per the 8493ba974a1c535563bff9a160996ad015a2a56cc05Nick Lewycky // function equality comparator. 8503ba974a1c535563bff9a160996ad015a2a56cc05Nick Lewycky // 8513ba974a1c535563bff9a160996ad015a2a56cc05Nick Lewycky // The special "lookup only" ComparableFunction bypasses the expensive 8523ba974a1c535563bff9a160996ad015a2a56cc05Nick Lewycky // function comparison in favour of a pointer comparison on the underlying 8533ba974a1c535563bff9a160996ad015a2a56cc05Nick Lewycky // Function*'s. 8543ba974a1c535563bff9a160996ad015a2a56cc05Nick Lewycky ComparableFunction CF = ComparableFunction(F, ComparableFunction::LookupOnly); 855abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky if (FnSet.erase(CF)) { 8563ba974a1c535563bff9a160996ad015a2a56cc05Nick Lewycky DEBUG(dbgs() << "Removed " << F->getName() << " from set and deferred it.\n"); 857abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky Deferred.push_back(F); 858f53de86cba33b63ecd54e16dcea735939c5b0e4aNick Lewycky } 859abd6c754090b1ff13b0dee925989bf8676d9cb4cNick Lewycky} 860b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky 861468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky// For each instruction used by the value, remove() the function that contains 862468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky// the instruction. This should happen right before a call to RAUW. 863468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewyckyvoid MergeFunctions::removeUsers(Value *V) { 864d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky std::vector<Value *> Worklist; 865d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky Worklist.push_back(V); 866d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky while (!Worklist.empty()) { 867d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky Value *V = Worklist.back(); 868d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky Worklist.pop_back(); 869d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky 870d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); 871d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky UI != UE; ++UI) { 872d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky Use &U = UI.getUse(); 873d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky if (Instruction *I = dyn_cast<Instruction>(U.getUser())) { 874468ee0a90db9ee7367bd163fcc3cb5b867753385Nick Lewycky remove(I->getParent()->getParent()); 875d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky } else if (isa<GlobalValue>(U.getUser())) { 876e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky // do nothing 877d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky } else if (Constant *C = dyn_cast<Constant>(U.getUser())) { 878e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky for (Value::use_iterator CUI = C->use_begin(), CUE = C->use_end(); 879e8f8139429ffc41ae3a339d4a32e336a74f189c0Nick Lewycky CUI != CUE; ++CUI) 880d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky Worklist.push_back(*CUI); 881d081b04f99de015519357ccaef29868c38c57d87Nick Lewycky } 882b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky } 883f53de86cba33b63ecd54e16dcea735939c5b0e4aNick Lewycky } 884b0104e1bb56cde925d91a5b2432a18f87214484aNick Lewycky} 885