MergeFunctions.cpp revision 6feb333695f913cd7b525f9a2d5b887f4b0fca1f
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 Function will not be analyzed if: 13579a0246616d76bc536de0e41edf069d091604beNick Lewycky// * it is overridable at runtime (except for weak linkage), or 14579a0246616d76bc536de0e41edf069d091604beNick Lewycky// * it is used by anything other than the callee parameter of a call/invoke 15579a0246616d76bc536de0e41edf069d091604beNick Lewycky// 16579a0246616d76bc536de0e41edf069d091604beNick Lewycky// A hash is computed from the function, based on its type and number of 17579a0246616d76bc536de0e41edf069d091604beNick Lewycky// basic blocks. 18579a0246616d76bc536de0e41edf069d091604beNick Lewycky// 19579a0246616d76bc536de0e41edf069d091604beNick Lewycky// Once all hashes are computed, we perform an expensive equality comparison 20579a0246616d76bc536de0e41edf069d091604beNick Lewycky// on each function pair. This takes n^2/2 comparisons per bucket, so it's 21579a0246616d76bc536de0e41edf069d091604beNick Lewycky// important that the hash function be high quality. The equality comparison 22579a0246616d76bc536de0e41edf069d091604beNick Lewycky// iterates through each instruction in each basic block. 23579a0246616d76bc536de0e41edf069d091604beNick Lewycky// 24579a0246616d76bc536de0e41edf069d091604beNick Lewycky// When a match is found, the functions are folded. We can only fold two 25579a0246616d76bc536de0e41edf069d091604beNick Lewycky// functions when we know that the definition of one of them is not 26579a0246616d76bc536de0e41edf069d091604beNick Lewycky// overridable. 27579a0246616d76bc536de0e41edf069d091604beNick Lewycky// * fold a function marked internal by replacing all of its users. 28579a0246616d76bc536de0e41edf069d091604beNick Lewycky// * fold extern or weak functions by replacing them with a global alias 29579a0246616d76bc536de0e41edf069d091604beNick Lewycky// 30579a0246616d76bc536de0e41edf069d091604beNick Lewycky//===----------------------------------------------------------------------===// 31579a0246616d76bc536de0e41edf069d091604beNick Lewycky// 32579a0246616d76bc536de0e41edf069d091604beNick Lewycky// Future work: 33579a0246616d76bc536de0e41edf069d091604beNick Lewycky// 34579a0246616d76bc536de0e41edf069d091604beNick Lewycky// * fold vector<T*>::push_back and vector<S*>::push_back. 35579a0246616d76bc536de0e41edf069d091604beNick Lewycky// 36579a0246616d76bc536de0e41edf069d091604beNick Lewycky// These two functions have different types, but in a way that doesn't matter 37579a0246616d76bc536de0e41edf069d091604beNick Lewycky// to us. As long as we never see an S or T itself, using S* and S** is the 38579a0246616d76bc536de0e41edf069d091604beNick Lewycky// same as using a T* and T**. 39579a0246616d76bc536de0e41edf069d091604beNick Lewycky// 40579a0246616d76bc536de0e41edf069d091604beNick Lewycky// * virtual functions. 41579a0246616d76bc536de0e41edf069d091604beNick Lewycky// 42579a0246616d76bc536de0e41edf069d091604beNick Lewycky// Many functions have their address taken by the virtual function table for 43579a0246616d76bc536de0e41edf069d091604beNick Lewycky// the object they belong to. However, as long as it's only used for a lookup 44579a0246616d76bc536de0e41edf069d091604beNick Lewycky// and call, this is irrelevant, and we'd like to fold such implementations. 45579a0246616d76bc536de0e41edf069d091604beNick Lewycky// 46579a0246616d76bc536de0e41edf069d091604beNick Lewycky//===----------------------------------------------------------------------===// 47579a0246616d76bc536de0e41edf069d091604beNick Lewycky 48579a0246616d76bc536de0e41edf069d091604beNick Lewycky#define DEBUG_TYPE "mergefunc" 49579a0246616d76bc536de0e41edf069d091604beNick Lewycky#include "llvm/Transforms/IPO.h" 50579a0246616d76bc536de0e41edf069d091604beNick Lewycky#include "llvm/ADT/DenseMap.h" 51579a0246616d76bc536de0e41edf069d091604beNick Lewycky#include "llvm/ADT/Statistic.h" 52579a0246616d76bc536de0e41edf069d091604beNick Lewycky#include "llvm/Constants.h" 53579a0246616d76bc536de0e41edf069d091604beNick Lewycky#include "llvm/InlineAsm.h" 54579a0246616d76bc536de0e41edf069d091604beNick Lewycky#include "llvm/Instructions.h" 55579a0246616d76bc536de0e41edf069d091604beNick Lewycky#include "llvm/Module.h" 56579a0246616d76bc536de0e41edf069d091604beNick Lewycky#include "llvm/Pass.h" 576feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky#include "llvm/Support/CallSite.h" 58579a0246616d76bc536de0e41edf069d091604beNick Lewycky#include "llvm/Support/Compiler.h" 59579a0246616d76bc536de0e41edf069d091604beNick Lewycky#include "llvm/Support/Debug.h" 60579a0246616d76bc536de0e41edf069d091604beNick Lewycky#include <map> 61579a0246616d76bc536de0e41edf069d091604beNick Lewycky#include <vector> 62579a0246616d76bc536de0e41edf069d091604beNick Lewyckyusing namespace llvm; 63579a0246616d76bc536de0e41edf069d091604beNick Lewycky 64579a0246616d76bc536de0e41edf069d091604beNick LewyckySTATISTIC(NumFunctionsMerged, "Number of functions merged"); 65579a0246616d76bc536de0e41edf069d091604beNick LewyckySTATISTIC(NumMergeFails, "Number of identical function pairings not merged"); 66579a0246616d76bc536de0e41edf069d091604beNick Lewycky 67579a0246616d76bc536de0e41edf069d091604beNick Lewyckynamespace { 68579a0246616d76bc536de0e41edf069d091604beNick Lewycky struct VISIBILITY_HIDDEN MergeFunctions : public ModulePass { 69579a0246616d76bc536de0e41edf069d091604beNick Lewycky static char ID; // Pass identification, replacement for typeid 70579a0246616d76bc536de0e41edf069d091604beNick Lewycky MergeFunctions() : ModulePass((intptr_t)&ID) {} 71579a0246616d76bc536de0e41edf069d091604beNick Lewycky 72579a0246616d76bc536de0e41edf069d091604beNick Lewycky bool runOnModule(Module &M); 73579a0246616d76bc536de0e41edf069d091604beNick Lewycky }; 74579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 75579a0246616d76bc536de0e41edf069d091604beNick Lewycky 76579a0246616d76bc536de0e41edf069d091604beNick Lewyckychar MergeFunctions::ID = 0; 77579a0246616d76bc536de0e41edf069d091604beNick Lewyckystatic RegisterPass<MergeFunctions> 78579a0246616d76bc536de0e41edf069d091604beNick LewyckyX("mergefunc", "Merge Functions"); 79579a0246616d76bc536de0e41edf069d091604beNick Lewycky 80579a0246616d76bc536de0e41edf069d091604beNick LewyckyModulePass *llvm::createMergeFunctionsPass() { 81579a0246616d76bc536de0e41edf069d091604beNick Lewycky return new MergeFunctions(); 82579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 83579a0246616d76bc536de0e41edf069d091604beNick Lewycky 845baf8ece830b7a14ac466d09d6a113205296f6eeDuncan Sandsstatic unsigned long hash(const Function *F) { 855baf8ece830b7a14ac466d09d6a113205296f6eeDuncan Sands return F->size() ^ reinterpret_cast<unsigned long>(F->getType()); 86579a0246616d76bc536de0e41edf069d091604beNick Lewycky //return F->size() ^ F->arg_size() ^ F->getReturnType(); 87579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 88579a0246616d76bc536de0e41edf069d091604beNick Lewycky 89579a0246616d76bc536de0e41edf069d091604beNick Lewyckystatic bool compare(const Value *V, const Value *U) { 90579a0246616d76bc536de0e41edf069d091604beNick Lewycky assert(!isa<BasicBlock>(V) && !isa<BasicBlock>(U) && 91579a0246616d76bc536de0e41edf069d091604beNick Lewycky "Must not compare basic blocks."); 92579a0246616d76bc536de0e41edf069d091604beNick Lewycky 93579a0246616d76bc536de0e41edf069d091604beNick Lewycky assert(V->getType() == U->getType() && 94579a0246616d76bc536de0e41edf069d091604beNick Lewycky "Two of the same operation have operands of different type."); 95579a0246616d76bc536de0e41edf069d091604beNick Lewycky 96579a0246616d76bc536de0e41edf069d091604beNick Lewycky // TODO: If the constant is an expression of F, we should accept that it's 97579a0246616d76bc536de0e41edf069d091604beNick Lewycky // equal to the same expression in terms of G. 98579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (isa<Constant>(V)) 99579a0246616d76bc536de0e41edf069d091604beNick Lewycky return V == U; 100579a0246616d76bc536de0e41edf069d091604beNick Lewycky 101579a0246616d76bc536de0e41edf069d091604beNick Lewycky // The caller has ensured that ValueMap[V] != U. Since Arguments are 102579a0246616d76bc536de0e41edf069d091604beNick Lewycky // pre-loaded into the ValueMap, and Instructions are added as we go, we know 103579a0246616d76bc536de0e41edf069d091604beNick Lewycky // that this can only be a mis-match. 104579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (isa<Instruction>(V) || isa<Argument>(V)) 105579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 106579a0246616d76bc536de0e41edf069d091604beNick Lewycky 107579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (isa<InlineAsm>(V) && isa<InlineAsm>(U)) { 108579a0246616d76bc536de0e41edf069d091604beNick Lewycky const InlineAsm *IAF = cast<InlineAsm>(V); 109579a0246616d76bc536de0e41edf069d091604beNick Lewycky const InlineAsm *IAG = cast<InlineAsm>(U); 110579a0246616d76bc536de0e41edf069d091604beNick Lewycky return IAF->getAsmString() == IAG->getAsmString() && 111579a0246616d76bc536de0e41edf069d091604beNick Lewycky IAF->getConstraintString() == IAG->getConstraintString(); 112579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 113579a0246616d76bc536de0e41edf069d091604beNick Lewycky 114579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 115579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 116579a0246616d76bc536de0e41edf069d091604beNick Lewycky 117579a0246616d76bc536de0e41edf069d091604beNick Lewyckystatic bool equals(const BasicBlock *BB1, const BasicBlock *BB2, 118579a0246616d76bc536de0e41edf069d091604beNick Lewycky DenseMap<const Value *, const Value *> &ValueMap, 119579a0246616d76bc536de0e41edf069d091604beNick Lewycky DenseMap<const Value *, const Value *> &SpeculationMap) { 120579a0246616d76bc536de0e41edf069d091604beNick Lewycky // Specutively add it anyways. If it's false, we'll notice a difference later, and 121579a0246616d76bc536de0e41edf069d091604beNick Lewycky // this won't matter. 122579a0246616d76bc536de0e41edf069d091604beNick Lewycky ValueMap[BB1] = BB2; 123579a0246616d76bc536de0e41edf069d091604beNick Lewycky 124579a0246616d76bc536de0e41edf069d091604beNick Lewycky BasicBlock::const_iterator FI = BB1->begin(), FE = BB1->end(); 125579a0246616d76bc536de0e41edf069d091604beNick Lewycky BasicBlock::const_iterator GI = BB2->begin(), GE = BB2->end(); 126579a0246616d76bc536de0e41edf069d091604beNick Lewycky 127579a0246616d76bc536de0e41edf069d091604beNick Lewycky do { 128579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (!FI->isSameOperationAs(const_cast<Instruction *>(&*GI))) 129579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 130579a0246616d76bc536de0e41edf069d091604beNick Lewycky 131579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (FI->getNumOperands() != GI->getNumOperands()) 132579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 133579a0246616d76bc536de0e41edf069d091604beNick Lewycky 134579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (ValueMap[FI] == GI) { 135579a0246616d76bc536de0e41edf069d091604beNick Lewycky ++FI, ++GI; 136579a0246616d76bc536de0e41edf069d091604beNick Lewycky continue; 137579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 138579a0246616d76bc536de0e41edf069d091604beNick Lewycky 139579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (ValueMap[FI] != NULL) 140579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 141579a0246616d76bc536de0e41edf069d091604beNick Lewycky 142579a0246616d76bc536de0e41edf069d091604beNick Lewycky for (unsigned i = 0, e = FI->getNumOperands(); i != e; ++i) { 143579a0246616d76bc536de0e41edf069d091604beNick Lewycky Value *OpF = FI->getOperand(i); 144579a0246616d76bc536de0e41edf069d091604beNick Lewycky Value *OpG = GI->getOperand(i); 145579a0246616d76bc536de0e41edf069d091604beNick Lewycky 146579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (ValueMap[OpF] == OpG) 147579a0246616d76bc536de0e41edf069d091604beNick Lewycky continue; 148579a0246616d76bc536de0e41edf069d091604beNick Lewycky 149579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (ValueMap[OpF] != NULL) 150579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 151579a0246616d76bc536de0e41edf069d091604beNick Lewycky 152579a0246616d76bc536de0e41edf069d091604beNick Lewycky assert(OpF->getType() == OpG->getType() && 153579a0246616d76bc536de0e41edf069d091604beNick Lewycky "Two of the same operation has operands of different type."); 154579a0246616d76bc536de0e41edf069d091604beNick Lewycky 155579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (OpF->getValueID() != OpG->getValueID()) 156579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 157579a0246616d76bc536de0e41edf069d091604beNick Lewycky 158579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (isa<PHINode>(FI)) { 159579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (SpeculationMap[OpF] == NULL) 160579a0246616d76bc536de0e41edf069d091604beNick Lewycky SpeculationMap[OpF] = OpG; 161579a0246616d76bc536de0e41edf069d091604beNick Lewycky else if (SpeculationMap[OpF] != OpG) 162579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 163579a0246616d76bc536de0e41edf069d091604beNick Lewycky continue; 164579a0246616d76bc536de0e41edf069d091604beNick Lewycky } else if (isa<BasicBlock>(OpF)) { 165579a0246616d76bc536de0e41edf069d091604beNick Lewycky assert(isa<TerminatorInst>(FI) && 166579a0246616d76bc536de0e41edf069d091604beNick Lewycky "BasicBlock referenced by non-Terminator non-PHI"); 167579a0246616d76bc536de0e41edf069d091604beNick Lewycky // This call changes the ValueMap, hence we can't use 168579a0246616d76bc536de0e41edf069d091604beNick Lewycky // Value *& = ValueMap[...] 169579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (!equals(cast<BasicBlock>(OpF), cast<BasicBlock>(OpG), ValueMap, 170579a0246616d76bc536de0e41edf069d091604beNick Lewycky SpeculationMap)) 171579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 172579a0246616d76bc536de0e41edf069d091604beNick Lewycky } else { 173579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (!compare(OpF, OpG)) 174579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 175579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 176579a0246616d76bc536de0e41edf069d091604beNick Lewycky 177579a0246616d76bc536de0e41edf069d091604beNick Lewycky ValueMap[OpF] = OpG; 178579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 179579a0246616d76bc536de0e41edf069d091604beNick Lewycky 180579a0246616d76bc536de0e41edf069d091604beNick Lewycky ValueMap[FI] = GI; 181579a0246616d76bc536de0e41edf069d091604beNick Lewycky ++FI, ++GI; 182579a0246616d76bc536de0e41edf069d091604beNick Lewycky } while (FI != FE && GI != GE); 183579a0246616d76bc536de0e41edf069d091604beNick Lewycky 184579a0246616d76bc536de0e41edf069d091604beNick Lewycky return FI == FE && GI == GE; 185579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 186579a0246616d76bc536de0e41edf069d091604beNick Lewycky 187579a0246616d76bc536de0e41edf069d091604beNick Lewyckystatic bool equals(const Function *F, const Function *G) { 188579a0246616d76bc536de0e41edf069d091604beNick Lewycky // We need to recheck everything, but check the things that weren't included 189579a0246616d76bc536de0e41edf069d091604beNick Lewycky // in the hash first. 190579a0246616d76bc536de0e41edf069d091604beNick Lewycky 191579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (F->getAttributes() != G->getAttributes()) 192579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 193579a0246616d76bc536de0e41edf069d091604beNick Lewycky 194579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (F->hasGC() != G->hasGC()) 195579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 196579a0246616d76bc536de0e41edf069d091604beNick Lewycky 197579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (F->hasGC() && F->getGC() != G->getGC()) 198579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 199579a0246616d76bc536de0e41edf069d091604beNick Lewycky 200579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (F->hasSection() != G->hasSection()) 201579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 202579a0246616d76bc536de0e41edf069d091604beNick Lewycky 203579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (F->hasSection() && F->getSection() != G->getSection()) 204579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 205579a0246616d76bc536de0e41edf069d091604beNick Lewycky 206579a0246616d76bc536de0e41edf069d091604beNick Lewycky // TODO: if it's internal and only used in direct calls, we could handle this 207579a0246616d76bc536de0e41edf069d091604beNick Lewycky // case too. 208579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (F->getCallingConv() != G->getCallingConv()) 209579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 210579a0246616d76bc536de0e41edf069d091604beNick Lewycky 211579a0246616d76bc536de0e41edf069d091604beNick Lewycky // TODO: We want to permit cases where two functions take T* and S* but 212579a0246616d76bc536de0e41edf069d091604beNick Lewycky // only load or store them into T** and S**. 213579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (F->getType() != G->getType()) 214579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 215579a0246616d76bc536de0e41edf069d091604beNick Lewycky 216579a0246616d76bc536de0e41edf069d091604beNick Lewycky DenseMap<const Value *, const Value *> ValueMap; 217579a0246616d76bc536de0e41edf069d091604beNick Lewycky DenseMap<const Value *, const Value *> SpeculationMap; 218579a0246616d76bc536de0e41edf069d091604beNick Lewycky ValueMap[F] = G; 219579a0246616d76bc536de0e41edf069d091604beNick Lewycky 220579a0246616d76bc536de0e41edf069d091604beNick Lewycky assert(F->arg_size() == G->arg_size() && 221579a0246616d76bc536de0e41edf069d091604beNick Lewycky "Identical functions have a different number of args."); 222579a0246616d76bc536de0e41edf069d091604beNick Lewycky 223579a0246616d76bc536de0e41edf069d091604beNick Lewycky for (Function::const_arg_iterator fi = F->arg_begin(), gi = G->arg_begin(), 224579a0246616d76bc536de0e41edf069d091604beNick Lewycky fe = F->arg_end(); fi != fe; ++fi, ++gi) 225579a0246616d76bc536de0e41edf069d091604beNick Lewycky ValueMap[fi] = gi; 226579a0246616d76bc536de0e41edf069d091604beNick Lewycky 227579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (!equals(&F->getEntryBlock(), &G->getEntryBlock(), ValueMap, 228579a0246616d76bc536de0e41edf069d091604beNick Lewycky SpeculationMap)) 229579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 230579a0246616d76bc536de0e41edf069d091604beNick Lewycky 231579a0246616d76bc536de0e41edf069d091604beNick Lewycky for (DenseMap<const Value *, const Value *>::iterator 232579a0246616d76bc536de0e41edf069d091604beNick Lewycky I = SpeculationMap.begin(), E = SpeculationMap.end(); I != E; ++I) { 233579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (ValueMap[I->first] != I->second) 234579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 235579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 236579a0246616d76bc536de0e41edf069d091604beNick Lewycky 237579a0246616d76bc536de0e41edf069d091604beNick Lewycky return true; 238579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 239579a0246616d76bc536de0e41edf069d091604beNick Lewycky 240579a0246616d76bc536de0e41edf069d091604beNick Lewyckystatic bool fold(std::vector<Function *> &FnVec, unsigned i, unsigned j) { 241579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (FnVec[i]->mayBeOverridden() && !FnVec[j]->mayBeOverridden()) 242579a0246616d76bc536de0e41edf069d091604beNick Lewycky std::swap(FnVec[i], FnVec[j]); 243579a0246616d76bc536de0e41edf069d091604beNick Lewycky 244579a0246616d76bc536de0e41edf069d091604beNick Lewycky Function *F = FnVec[i]; 245579a0246616d76bc536de0e41edf069d091604beNick Lewycky Function *G = FnVec[j]; 246579a0246616d76bc536de0e41edf069d091604beNick Lewycky 247579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (!F->mayBeOverridden()) { 248579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (G->hasInternalLinkage()) { 249579a0246616d76bc536de0e41edf069d091604beNick Lewycky F->setAlignment(std::max(F->getAlignment(), G->getAlignment())); 250579a0246616d76bc536de0e41edf069d091604beNick Lewycky G->replaceAllUsesWith(F); 251579a0246616d76bc536de0e41edf069d091604beNick Lewycky G->eraseFromParent(); 252579a0246616d76bc536de0e41edf069d091604beNick Lewycky ++NumFunctionsMerged; 253579a0246616d76bc536de0e41edf069d091604beNick Lewycky return true; 254579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 255579a0246616d76bc536de0e41edf069d091604beNick Lewycky 256579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (G->hasExternalLinkage() || G->hasWeakLinkage()) { 257579a0246616d76bc536de0e41edf069d091604beNick Lewycky GlobalAlias *GA = new GlobalAlias(G->getType(), G->getLinkage(), "", 258579a0246616d76bc536de0e41edf069d091604beNick Lewycky F, G->getParent()); 259579a0246616d76bc536de0e41edf069d091604beNick Lewycky F->setAlignment(std::max(F->getAlignment(), G->getAlignment())); 260579a0246616d76bc536de0e41edf069d091604beNick Lewycky GA->takeName(G); 261579a0246616d76bc536de0e41edf069d091604beNick Lewycky GA->setVisibility(G->getVisibility()); 262579a0246616d76bc536de0e41edf069d091604beNick Lewycky G->replaceAllUsesWith(GA); 263579a0246616d76bc536de0e41edf069d091604beNick Lewycky G->eraseFromParent(); 264579a0246616d76bc536de0e41edf069d091604beNick Lewycky ++NumFunctionsMerged; 265579a0246616d76bc536de0e41edf069d091604beNick Lewycky return true; 266579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 267579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 268579a0246616d76bc536de0e41edf069d091604beNick Lewycky 2696feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky if (F->hasWeakLinkage() && G->hasWeakLinkage()) { 2706feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky GlobalAlias *GA_F = new GlobalAlias(F->getType(), F->getLinkage(), "", 2716feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky 0, F->getParent()); 2726feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky GA_F->takeName(F); 2736feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky GA_F->setVisibility(F->getVisibility()); 2746feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky F->setAlignment(std::max(F->getAlignment(), G->getAlignment())); 2756feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky F->replaceAllUsesWith(GA_F); 2766feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky F->setName("folded." + GA_F->getName()); 2776feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky F->setLinkage(GlobalValue::ExternalLinkage); 2786feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky GA_F->setAliasee(F); 2796feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky 2806feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky GlobalAlias *GA_G = new GlobalAlias(G->getType(), G->getLinkage(), "", 2816feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky F, G->getParent()); 2826feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky GA_G->takeName(G); 2836feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky GA_G->setVisibility(G->getVisibility()); 2846feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky G->replaceAllUsesWith(GA_G); 2856feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky G->eraseFromParent(); 2866feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky 2876feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky ++NumFunctionsMerged; 2886feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky return true; 2896feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky } 2906feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky 291579a0246616d76bc536de0e41edf069d091604beNick Lewycky DOUT << "Failed on " << F->getName() << " and " << G->getName() << "\n"; 292579a0246616d76bc536de0e41edf069d091604beNick Lewycky 293579a0246616d76bc536de0e41edf069d091604beNick Lewycky ++NumMergeFails; 294579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 295579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 296579a0246616d76bc536de0e41edf069d091604beNick Lewycky 297579a0246616d76bc536de0e41edf069d091604beNick Lewyckystatic bool hasAddressTaken(User *U) { 298579a0246616d76bc536de0e41edf069d091604beNick Lewycky for (User::use_iterator I = U->use_begin(), E = U->use_end(); I != E; ++I) { 299579a0246616d76bc536de0e41edf069d091604beNick Lewycky User *Use = *I; 300579a0246616d76bc536de0e41edf069d091604beNick Lewycky 301579a0246616d76bc536de0e41edf069d091604beNick Lewycky // 'call (bitcast @F to ...)' happens a lot. 302579a0246616d76bc536de0e41edf069d091604beNick Lewycky while (isa<ConstantExpr>(Use) && Use->hasOneUse()) { 303579a0246616d76bc536de0e41edf069d091604beNick Lewycky Use = *Use->use_begin(); 304579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 305579a0246616d76bc536de0e41edf069d091604beNick Lewycky 306579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (isa<ConstantExpr>(Use)) { 307579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (hasAddressTaken(Use)) 308579a0246616d76bc536de0e41edf069d091604beNick Lewycky return true; 309579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 310579a0246616d76bc536de0e41edf069d091604beNick Lewycky 311579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (!isa<CallInst>(Use) && !isa<InvokeInst>(Use)) 312579a0246616d76bc536de0e41edf069d091604beNick Lewycky return true; 313579a0246616d76bc536de0e41edf069d091604beNick Lewycky 314579a0246616d76bc536de0e41edf069d091604beNick Lewycky // Make sure we aren't passing U as a parameter to call instead of the 3156feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky // callee. 3166feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky if (CallSite(cast<Instruction>(Use)).hasArgument(U)) 3176feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky return true; 318579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 319579a0246616d76bc536de0e41edf069d091604beNick Lewycky 320579a0246616d76bc536de0e41edf069d091604beNick Lewycky return false; 321579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 322579a0246616d76bc536de0e41edf069d091604beNick Lewycky 323579a0246616d76bc536de0e41edf069d091604beNick Lewyckybool MergeFunctions::runOnModule(Module &M) { 324579a0246616d76bc536de0e41edf069d091604beNick Lewycky bool Changed = false; 325579a0246616d76bc536de0e41edf069d091604beNick Lewycky 3265baf8ece830b7a14ac466d09d6a113205296f6eeDuncan Sands std::map<unsigned long, std::vector<Function *> > FnMap; 327579a0246616d76bc536de0e41edf069d091604beNick Lewycky 328579a0246616d76bc536de0e41edf069d091604beNick Lewycky for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { 329579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (F->isDeclaration() || F->isIntrinsic()) 330579a0246616d76bc536de0e41edf069d091604beNick Lewycky continue; 331579a0246616d76bc536de0e41edf069d091604beNick Lewycky 3326feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky if (!F->hasInternalLinkage() && !F->hasExternalLinkage() && 3336feb333695f913cd7b525f9a2d5b887f4b0fca1fNick Lewycky !F->hasWeakLinkage()) 334579a0246616d76bc536de0e41edf069d091604beNick Lewycky continue; 335579a0246616d76bc536de0e41edf069d091604beNick Lewycky 336579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (hasAddressTaken(F)) 337579a0246616d76bc536de0e41edf069d091604beNick Lewycky continue; 338579a0246616d76bc536de0e41edf069d091604beNick Lewycky 339579a0246616d76bc536de0e41edf069d091604beNick Lewycky FnMap[hash(F)].push_back(F); 340579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 341579a0246616d76bc536de0e41edf069d091604beNick Lewycky 342579a0246616d76bc536de0e41edf069d091604beNick Lewycky // TODO: instead of running in a loop, we could also fold functions in callgraph 343579a0246616d76bc536de0e41edf069d091604beNick Lewycky // order. Constructing the CFG probably isn't cheaper than just running in a loop. 344579a0246616d76bc536de0e41edf069d091604beNick Lewycky 345579a0246616d76bc536de0e41edf069d091604beNick Lewycky bool LocalChanged; 346579a0246616d76bc536de0e41edf069d091604beNick Lewycky do { 347579a0246616d76bc536de0e41edf069d091604beNick Lewycky LocalChanged = false; 3485baf8ece830b7a14ac466d09d6a113205296f6eeDuncan Sands for (std::map<unsigned long, std::vector<Function *> >::iterator 3495baf8ece830b7a14ac466d09d6a113205296f6eeDuncan Sands I = FnMap.begin(), E = FnMap.end(); I != E; ++I) { 350579a0246616d76bc536de0e41edf069d091604beNick Lewycky DOUT << "size: " << FnMap.size() << "\n"; 351579a0246616d76bc536de0e41edf069d091604beNick Lewycky std::vector<Function *> &FnVec = I->second; 352579a0246616d76bc536de0e41edf069d091604beNick Lewycky DOUT << "hash (" << I->first << "): " << FnVec.size() << "\n"; 353579a0246616d76bc536de0e41edf069d091604beNick Lewycky 354579a0246616d76bc536de0e41edf069d091604beNick Lewycky for (int i = 0, e = FnVec.size(); i != e; ++i) { 355579a0246616d76bc536de0e41edf069d091604beNick Lewycky for (int j = i + 1; j != e; ++j) { 356579a0246616d76bc536de0e41edf069d091604beNick Lewycky bool isEqual = equals(FnVec[i], FnVec[j]); 357579a0246616d76bc536de0e41edf069d091604beNick Lewycky 358579a0246616d76bc536de0e41edf069d091604beNick Lewycky DOUT << " " << FnVec[i]->getName() 359579a0246616d76bc536de0e41edf069d091604beNick Lewycky << (isEqual ? " == " : " != ") 360579a0246616d76bc536de0e41edf069d091604beNick Lewycky << FnVec[j]->getName() << "\n"; 361579a0246616d76bc536de0e41edf069d091604beNick Lewycky 362579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (isEqual) { 363579a0246616d76bc536de0e41edf069d091604beNick Lewycky if (fold(FnVec, i, j)) { 364579a0246616d76bc536de0e41edf069d091604beNick Lewycky LocalChanged = true; 365579a0246616d76bc536de0e41edf069d091604beNick Lewycky FnVec.erase(FnVec.begin() + j); 366579a0246616d76bc536de0e41edf069d091604beNick Lewycky --j, --e; 367579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 368579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 369579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 370579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 371579a0246616d76bc536de0e41edf069d091604beNick Lewycky 372579a0246616d76bc536de0e41edf069d091604beNick Lewycky } 373579a0246616d76bc536de0e41edf069d091604beNick Lewycky Changed |= LocalChanged; 374579a0246616d76bc536de0e41edf069d091604beNick Lewycky } while (LocalChanged); 375579a0246616d76bc536de0e41edf069d091604beNick Lewycky 376579a0246616d76bc536de0e41edf069d091604beNick Lewycky return Changed; 377579a0246616d76bc536de0e41edf069d091604beNick Lewycky} 378