LLVM API Documentation

MergeFunctions.cpp

Go to the documentation of this file.
00001 //===- MergeFunctions.cpp - Merge identical functions ---------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass looks for equivalent functions that are mergable and folds them.
00011 //
00012 // A hash is computed from the function, based on its type and number of
00013 // basic blocks.
00014 //
00015 // Once all hashes are computed, we perform an expensive equality comparison
00016 // on each function pair. This takes n^2/2 comparisons per bucket, so it's
00017 // important that the hash function be high quality. The equality comparison
00018 // iterates through each instruction in each basic block.
00019 //
00020 // When a match is found, the functions are folded. We can only fold two
00021 // functions when we know that the definition of one of them is not
00022 // overridable.
00023 //
00024 //===----------------------------------------------------------------------===//
00025 //
00026 // Future work:
00027 //
00028 // * fold vector<T*>::push_back and vector<S*>::push_back.
00029 //
00030 // These two functions have different types, but in a way that doesn't matter
00031 // to us. As long as we never see an S or T itself, using S* and S** is the
00032 // same as using a T* and T**.
00033 //
00034 // * virtual functions.
00035 //
00036 // Many functions have their address taken by the virtual function table for
00037 // the object they belong to. However, as long as it's only used for a lookup
00038 // and call, this is irrelevant, and we'd like to fold such implementations.
00039 //
00040 //===----------------------------------------------------------------------===//
00041 
00042 #define DEBUG_TYPE "mergefunc"
00043 #include "llvm/Transforms/IPO.h"
00044 #include "llvm/ADT/DenseMap.h"
00045 #include "llvm/ADT/FoldingSet.h"
00046 #include "llvm/ADT/Statistic.h"
00047 #include "llvm/Constants.h"
00048 #include "llvm/InlineAsm.h"
00049 #include "llvm/Instructions.h"
00050 #include "llvm/LLVMContext.h"
00051 #include "llvm/Module.h"
00052 #include "llvm/Pass.h"
00053 #include "llvm/Support/CallSite.h"
00054 #include "llvm/Support/Compiler.h"
00055 #include "llvm/Support/Debug.h"
00056 #include "llvm/Support/ErrorHandling.h"
00057 #include "llvm/Support/raw_ostream.h"
00058 #include <map>
00059 #include <vector>
00060 using namespace llvm;
00061 
00062 STATISTIC(NumFunctionsMerged, "Number of functions merged");
00063 
00064 namespace {
00065   struct VISIBILITY_HIDDEN MergeFunctions : public ModulePass {
00066     static char ID; // Pass identification, replacement for typeid
00067     MergeFunctions() : ModulePass(&ID) {}
00068 
00069     bool runOnModule(Module &M);
00070   };
00071 }
00072 
00073 char MergeFunctions::ID = 0;
00074 static RegisterPass<MergeFunctions>
00075 X("mergefunc", "Merge Functions");
00076 
00077 ModulePass *llvm::createMergeFunctionsPass() {
00078   return new MergeFunctions();
00079 }
00080 
00081 // ===----------------------------------------------------------------------===
00082 // Comparison of functions
00083 // ===----------------------------------------------------------------------===
00084 
00085 static unsigned long hash(const Function *F) {
00086   const FunctionType *FTy = F->getFunctionType();
00087 
00088   FoldingSetNodeID ID;
00089   ID.AddInteger(F->size());
00090   ID.AddInteger(F->getCallingConv());
00091   ID.AddBoolean(F->hasGC());
00092   ID.AddBoolean(FTy->isVarArg());
00093   ID.AddInteger(FTy->getReturnType()->getTypeID());
00094   for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
00095     ID.AddInteger(FTy->getParamType(i)->getTypeID());
00096   return ID.ComputeHash();
00097 }
00098 
00099 /// IgnoreBitcasts - given a bitcast, returns the first non-bitcast found by
00100 /// walking the chain of cast operands. Otherwise, returns the argument.
00101 static Value* IgnoreBitcasts(Value *V) {
00102   while (BitCastInst *BC = dyn_cast<BitCastInst>(V))
00103     V = BC->getOperand(0);
00104 
00105   return V;
00106 }
00107 
00108 /// isEquivalentType - any two pointers are equivalent. Otherwise, standard
00109 /// type equivalence rules apply.
00110 static bool isEquivalentType(const Type *Ty1, const Type *Ty2) {
00111   if (Ty1 == Ty2)
00112     return true;
00113   if (Ty1->getTypeID() != Ty2->getTypeID())
00114     return false;
00115 
00116   switch(Ty1->getTypeID()) {
00117   case Type::VoidTyID:
00118   case Type::FloatTyID:
00119   case Type::DoubleTyID:
00120   case Type::X86_FP80TyID:
00121   case Type::FP128TyID:
00122   case Type::PPC_FP128TyID:
00123   case Type::LabelTyID:
00124   case Type::MetadataTyID:
00125     return true;
00126 
00127   case Type::IntegerTyID:
00128   case Type::OpaqueTyID:
00129     // Ty1 == Ty2 would have returned true earlier.
00130     return false;
00131 
00132   default:
00133     llvm_unreachable("Unknown type!");
00134     return false;
00135 
00136   case Type::PointerTyID: {
00137     const PointerType *PTy1 = cast<PointerType>(Ty1);
00138     const PointerType *PTy2 = cast<PointerType>(Ty2);
00139     return PTy1->getAddressSpace() == PTy2->getAddressSpace();
00140   }
00141 
00142   case Type::StructTyID: {
00143     const StructType *STy1 = cast<StructType>(Ty1);
00144     const StructType *STy2 = cast<StructType>(Ty2);
00145     if (STy1->getNumElements() != STy2->getNumElements())
00146       return false;
00147 
00148     if (STy1->isPacked() != STy2->isPacked())
00149       return false;
00150 
00151     for (unsigned i = 0, e = STy1->getNumElements(); i != e; ++i) {
00152       if (!isEquivalentType(STy1->getElementType(i), STy2->getElementType(i)))
00153         return false;
00154     }
00155     return true;
00156   }
00157 
00158   case Type::FunctionTyID: {
00159     const FunctionType *FTy1 = cast<FunctionType>(Ty1);
00160     const FunctionType *FTy2 = cast<FunctionType>(Ty2);
00161     if (FTy1->getNumParams() != FTy2->getNumParams() ||
00162         FTy1->isVarArg() != FTy2->isVarArg())
00163       return false;
00164 
00165     if (!isEquivalentType(FTy1->getReturnType(), FTy2->getReturnType()))
00166       return false;
00167 
00168     for (unsigned i = 0, e = FTy1->getNumParams(); i != e; ++i) {
00169       if (!isEquivalentType(FTy1->getParamType(i), FTy2->getParamType(i)))
00170         return false;
00171     }
00172     return true;
00173   }
00174 
00175   case Type::ArrayTyID:
00176   case Type::VectorTyID: {
00177     const SequentialType *STy1 = cast<SequentialType>(Ty1);
00178     const SequentialType *STy2 = cast<SequentialType>(Ty2);
00179     return isEquivalentType(STy1->getElementType(), STy2->getElementType());
00180   }
00181   }
00182 }
00183 
00184 /// isEquivalentOperation - determine whether the two operations are the same
00185 /// except that pointer-to-A and pointer-to-B are equivalent. This should be
00186 /// kept in sync with Instruction::isSameOperationAs.
00187 static bool
00188 isEquivalentOperation(const Instruction *I1, const Instruction *I2) {
00189   if (I1->getOpcode() != I2->getOpcode() ||
00190       I1->getNumOperands() != I2->getNumOperands() ||
00191       !isEquivalentType(I1->getType(), I2->getType()) ||
00192       !I1->hasSameSubclassOptionalData(I2))
00193     return false;
00194 
00195   // We have two instructions of identical opcode and #operands.  Check to see
00196   // if all operands are the same type
00197   for (unsigned i = 0, e = I1->getNumOperands(); i != e; ++i)
00198     if (!isEquivalentType(I1->getOperand(i)->getType(),
00199                           I2->getOperand(i)->getType()))
00200       return false;
00201 
00202   // Check special state that is a part of some instructions.
00203   if (const LoadInst *LI = dyn_cast<LoadInst>(I1))
00204     return LI->isVolatile() == cast<LoadInst>(I2)->isVolatile() &&
00205            LI->getAlignment() == cast<LoadInst>(I2)->getAlignment();
00206   if (const StoreInst *SI = dyn_cast<StoreInst>(I1))
00207     return SI->isVolatile() == cast<StoreInst>(I2)->isVolatile() &&
00208            SI->getAlignment() == cast<StoreInst>(I2)->getAlignment();
00209   if (const CmpInst *CI = dyn_cast<CmpInst>(I1))
00210     return CI->getPredicate() == cast<CmpInst>(I2)->getPredicate();
00211   if (const CallInst *CI = dyn_cast<CallInst>(I1))
00212     return CI->isTailCall() == cast<CallInst>(I2)->isTailCall() &&
00213            CI->getCallingConv() == cast<CallInst>(I2)->getCallingConv() &&
00214            CI->getAttributes().getRawPointer() ==
00215              cast<CallInst>(I2)->getAttributes().getRawPointer();
00216   if (const InvokeInst *CI = dyn_cast<InvokeInst>(I1))
00217     return CI->getCallingConv() == cast<InvokeInst>(I2)->getCallingConv() &&
00218            CI->getAttributes().getRawPointer() ==
00219              cast<InvokeInst>(I2)->getAttributes().getRawPointer();
00220   if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(I1)) {
00221     if (IVI->getNumIndices() != cast<InsertValueInst>(I2)->getNumIndices())
00222       return false;
00223     for (unsigned i = 0, e = IVI->getNumIndices(); i != e; ++i)
00224       if (IVI->idx_begin()[i] != cast<InsertValueInst>(I2)->idx_begin()[i])
00225         return false;
00226     return true;
00227   }
00228   if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(I1)) {
00229     if (EVI->getNumIndices() != cast<ExtractValueInst>(I2)->getNumIndices())
00230       return false;
00231     for (unsigned i = 0, e = EVI->getNumIndices(); i != e; ++i)
00232       if (EVI->idx_begin()[i] != cast<ExtractValueInst>(I2)->idx_begin()[i])
00233         return false;
00234     return true;
00235   }
00236 
00237   return true;
00238 }
00239 
00240 static bool compare(const Value *V, const Value *U) {
00241   assert(!isa<BasicBlock>(V) && !isa<BasicBlock>(U) &&
00242          "Must not compare basic blocks.");
00243 
00244   assert(isEquivalentType(V->getType(), U->getType()) &&
00245         "Two of the same operation have operands of different type.");
00246 
00247   // TODO: If the constant is an expression of F, we should accept that it's
00248   // equal to the same expression in terms of G.
00249   if (isa<Constant>(V))
00250     return V == U;
00251 
00252   // The caller has ensured that ValueMap[V] != U. Since Arguments are
00253   // pre-loaded into the ValueMap, and Instructions are added as we go, we know
00254   // that this can only be a mis-match.
00255   if (isa<Instruction>(V) || isa<Argument>(V))
00256     return false;
00257 
00258   if (isa<InlineAsm>(V) && isa<InlineAsm>(U)) {
00259     const InlineAsm *IAF = cast<InlineAsm>(V);
00260     const InlineAsm *IAG = cast<InlineAsm>(U);
00261     return IAF->getAsmString() == IAG->getAsmString() &&
00262            IAF->getConstraintString() == IAG->getConstraintString();
00263   }
00264 
00265   return false;
00266 }
00267 
00268 static bool equals(const BasicBlock *BB1, const BasicBlock *BB2,
00269                    DenseMap<const Value *, const Value *> &ValueMap,
00270                    DenseMap<const Value *, const Value *> &SpeculationMap) {
00271   // Speculatively add it anyways. If it's false, we'll notice a difference
00272   // later, and this won't matter.
00273   ValueMap[BB1] = BB2;
00274 
00275   BasicBlock::const_iterator FI = BB1->begin(), FE = BB1->end();
00276   BasicBlock::const_iterator GI = BB2->begin(), GE = BB2->end();
00277 
00278   do {
00279     if (isa<BitCastInst>(FI)) {
00280       ++FI;
00281       continue;
00282     }
00283     if (isa<BitCastInst>(GI)) {
00284       ++GI;
00285       continue;
00286     }
00287 
00288     if (!isEquivalentOperation(FI, GI))
00289       return false;
00290 
00291     if (isa<GetElementPtrInst>(FI)) {
00292       const GetElementPtrInst *GEPF = cast<GetElementPtrInst>(FI);
00293       const GetElementPtrInst *GEPG = cast<GetElementPtrInst>(GI);
00294       if (GEPF->hasAllZeroIndices() && GEPG->hasAllZeroIndices()) {
00295         // It's effectively a bitcast.
00296         ++FI, ++GI;
00297         continue;
00298       }
00299 
00300       // TODO: we only really care about the elements before the index
00301       if (FI->getOperand(0)->getType() != GI->getOperand(0)->getType())
00302         return false;
00303     }
00304 
00305     if (ValueMap[FI] == GI) {
00306       ++FI, ++GI;
00307       continue;
00308     }
00309 
00310     if (ValueMap[FI] != NULL)
00311       return false;
00312 
00313     for (unsigned i = 0, e = FI->getNumOperands(); i != e; ++i) {
00314       Value *OpF = IgnoreBitcasts(FI->getOperand(i));
00315       Value *OpG = IgnoreBitcasts(GI->getOperand(i));
00316 
00317       if (ValueMap[OpF] == OpG)
00318         continue;
00319 
00320       if (ValueMap[OpF] != NULL)
00321         return false;
00322 
00323       if (OpF->getValueID() != OpG->getValueID() ||
00324           !isEquivalentType(OpF->getType(), OpG->getType()))
00325         return false;
00326 
00327       if (isa<PHINode>(FI)) {
00328         if (SpeculationMap[OpF] == NULL)
00329           SpeculationMap[OpF] = OpG;
00330         else if (SpeculationMap[OpF] != OpG)
00331           return false;
00332         continue;
00333       } else if (isa<BasicBlock>(OpF)) {
00334         assert(isa<TerminatorInst>(FI) &&
00335                "BasicBlock referenced by non-Terminator non-PHI");
00336         // This call changes the ValueMap, hence we can't use
00337         // Value *& = ValueMap[...]
00338         if (!equals(cast<BasicBlock>(OpF), cast<BasicBlock>(OpG), ValueMap,
00339                     SpeculationMap))
00340           return false;
00341       } else {
00342         if (!compare(OpF, OpG))
00343           return false;
00344       }
00345 
00346       ValueMap[OpF] = OpG;
00347     }
00348 
00349     ValueMap[FI] = GI;
00350     ++FI, ++GI;
00351   } while (FI != FE && GI != GE);
00352 
00353   return FI == FE && GI == GE;
00354 }
00355 
00356 static bool equals(const Function *F, const Function *G) {
00357   // We need to recheck everything, but check the things that weren't included
00358   // in the hash first.
00359 
00360   if (F->getAttributes() != G->getAttributes())
00361     return false;
00362 
00363   if (F->hasGC() != G->hasGC())
00364     return false;
00365 
00366   if (F->hasGC() && F->getGC() != G->getGC())
00367     return false;
00368 
00369   if (F->hasSection() != G->hasSection())
00370     return false;
00371 
00372   if (F->hasSection() && F->getSection() != G->getSection())
00373     return false;
00374 
00375   if (F->isVarArg() != G->isVarArg())
00376     return false;
00377 
00378   // TODO: if it's internal and only used in direct calls, we could handle this
00379   // case too.
00380   if (F->getCallingConv() != G->getCallingConv())
00381     return false;
00382 
00383   if (!isEquivalentType(F->getFunctionType(), G->getFunctionType()))
00384     return false;
00385 
00386   DenseMap<const Value *, const Value *> ValueMap;
00387   DenseMap<const Value *, const Value *> SpeculationMap;
00388   ValueMap[F] = G;
00389 
00390   assert(F->arg_size() == G->arg_size() &&
00391          "Identical functions have a different number of args.");
00392 
00393   for (Function::const_arg_iterator fi = F->arg_begin(), gi = G->arg_begin(),
00394          fe = F->arg_end(); fi != fe; ++fi, ++gi)
00395     ValueMap[fi] = gi;
00396 
00397   if (!equals(&F->getEntryBlock(), &G->getEntryBlock(), ValueMap,
00398               SpeculationMap))
00399     return false;
00400 
00401   for (DenseMap<const Value *, const Value *>::iterator
00402          I = SpeculationMap.begin(), E = SpeculationMap.end(); I != E; ++I) {
00403     if (ValueMap[I->first] != I->second)
00404       return false;
00405   }
00406 
00407   return true;
00408 }
00409 
00410 // ===----------------------------------------------------------------------===
00411 // Folding of functions
00412 // ===----------------------------------------------------------------------===
00413 
00414 // Cases:
00415 // * F is external strong, G is external strong:
00416 //   turn G into a thunk to F    (1)
00417 // * F is external strong, G is external weak:
00418 //   turn G into a thunk to F    (1)
00419 // * F is external weak, G is external weak:
00420 //   unfoldable
00421 // * F is external strong, G is internal:
00422 //   address of G taken:
00423 //     turn G into a thunk to F  (1)
00424 //   address of G not taken:
00425 //     make G an alias to F      (2)
00426 // * F is internal, G is external weak
00427 //   address of F is taken:
00428 //     turn G into a thunk to F  (1)
00429 //   address of F is not taken:
00430 //     make G an alias of F      (2)
00431 // * F is internal, G is internal:
00432 //   address of F and G are taken:
00433 //     turn G into a thunk to F  (1)
00434 //   address of G is not taken:
00435 //     make G an alias to F      (2)
00436 //
00437 // alias requires linkage == (external,local,weak) fallback to creating a thunk
00438 // external means 'externally visible' linkage != (internal,private)
00439 // internal means linkage == (internal,private)
00440 // weak means linkage mayBeOverridable
00441 // being external implies that the address is taken
00442 //
00443 // 1. turn G into a thunk to F
00444 // 2. make G an alias to F
00445 
00446 enum LinkageCategory {
00447   ExternalStrong,
00448   ExternalWeak,
00449   Internal
00450 };
00451 
00452 static LinkageCategory categorize(const Function *F) {
00453   switch (F->getLinkage()) {
00454   case GlobalValue::InternalLinkage:
00455   case GlobalValue::PrivateLinkage:
00456   case GlobalValue::LinkerPrivateLinkage:
00457     return Internal;
00458 
00459   case GlobalValue::WeakAnyLinkage:
00460   case GlobalValue::WeakODRLinkage:
00461   case GlobalValue::ExternalWeakLinkage:
00462     return ExternalWeak;
00463 
00464   case GlobalValue::ExternalLinkage:
00465   case GlobalValue::AvailableExternallyLinkage:
00466   case GlobalValue::LinkOnceAnyLinkage:
00467   case GlobalValue::LinkOnceODRLinkage:
00468   case GlobalValue::AppendingLinkage:
00469   case GlobalValue::DLLImportLinkage:
00470   case GlobalValue::DLLExportLinkage:
00471   case GlobalValue::GhostLinkage:
00472   case GlobalValue::CommonLinkage:
00473     return ExternalStrong;
00474   }
00475 
00476   llvm_unreachable("Unknown LinkageType.");
00477   return ExternalWeak;
00478 }
00479 
00480 static void ThunkGToF(Function *F, Function *G) {
00481   Function *NewG = Function::Create(G->getFunctionType(), G->getLinkage(), "",
00482                                     G->getParent());
00483   BasicBlock *BB = BasicBlock::Create(F->getContext(), "", NewG);
00484 
00485   std::vector<Value *> Args;
00486   unsigned i = 0;
00487   const FunctionType *FFTy = F->getFunctionType();
00488   for (Function::arg_iterator AI = NewG->arg_begin(), AE = NewG->arg_end();
00489        AI != AE; ++AI) {
00490     if (FFTy->getParamType(i) == AI->getType())
00491       Args.push_back(AI);
00492     else {
00493       Value *BCI = new BitCastInst(AI, FFTy->getParamType(i), "", BB);
00494       Args.push_back(BCI);
00495     }
00496     ++i;
00497   }
00498 
00499   CallInst *CI = CallInst::Create(F, Args.begin(), Args.end(), "", BB);
00500   CI->setTailCall();
00501   CI->setCallingConv(F->getCallingConv());
00502   if (NewG->getReturnType() == Type::getVoidTy(F->getContext())) {
00503     ReturnInst::Create(F->getContext(), BB);
00504   } else if (CI->getType() != NewG->getReturnType()) {
00505     Value *BCI = new BitCastInst(CI, NewG->getReturnType(), "", BB);
00506     ReturnInst::Create(F->getContext(), BCI, BB);
00507   } else {
00508     ReturnInst::Create(F->getContext(), CI, BB);
00509   }
00510 
00511   NewG->copyAttributesFrom(G);
00512   NewG->takeName(G);
00513   G->replaceAllUsesWith(NewG);
00514   G->eraseFromParent();
00515 
00516   // TODO: look at direct callers to G and make them all direct callers to F.
00517 }
00518 
00519 static void AliasGToF(Function *F, Function *G) {
00520   if (!G->hasExternalLinkage() && !G->hasLocalLinkage() && !G->hasWeakLinkage())
00521     return ThunkGToF(F, G);
00522 
00523   GlobalAlias *GA = new GlobalAlias(
00524     G->getType(), G->getLinkage(), "",
00525     ConstantExpr::getBitCast(F, G->getType()), G->getParent());
00526   F->setAlignment(std::max(F->getAlignment(), G->getAlignment()));
00527   GA->takeName(G);
00528   GA->setVisibility(G->getVisibility());
00529   G->replaceAllUsesWith(GA);
00530   G->eraseFromParent();
00531 }
00532 
00533 static bool fold(std::vector<Function *> &FnVec, unsigned i, unsigned j) {
00534   Function *F = FnVec[i];
00535   Function *G = FnVec[j];
00536 
00537   LinkageCategory catF = categorize(F);
00538   LinkageCategory catG = categorize(G);
00539 
00540   if (catF == ExternalWeak || (catF == Internal && catG == ExternalStrong)) {
00541     std::swap(FnVec[i], FnVec[j]);
00542     std::swap(F, G);
00543     std::swap(catF, catG);
00544   }
00545 
00546   switch (catF) {
00547     case ExternalStrong:
00548       switch (catG) {
00549         case ExternalStrong:
00550         case ExternalWeak:
00551           ThunkGToF(F, G);
00552           break;
00553         case Internal:
00554           if (G->hasAddressTaken())
00555             ThunkGToF(F, G);
00556           else
00557             AliasGToF(F, G);
00558           break;
00559       }
00560       break;
00561 
00562     case ExternalWeak: {
00563       assert(catG == ExternalWeak);
00564 
00565       // Make them both thunks to the same internal function.
00566       F->setAlignment(std::max(F->getAlignment(), G->getAlignment()));
00567       Function *H = Function::Create(F->getFunctionType(), F->getLinkage(), "",
00568                                      F->getParent());
00569       H->copyAttributesFrom(F);
00570       H->takeName(F);
00571       F->replaceAllUsesWith(H);
00572 
00573       ThunkGToF(F, G);
00574       ThunkGToF(F, H);
00575 
00576       F->setLinkage(GlobalValue::InternalLinkage);
00577     } break;
00578 
00579     case Internal:
00580       switch (catG) {
00581         case ExternalStrong:
00582           llvm_unreachable(0);
00583           // fall-through
00584         case ExternalWeak:
00585     if (F->hasAddressTaken())
00586             ThunkGToF(F, G);
00587           else
00588             AliasGToF(F, G);
00589     break;
00590         case Internal: {
00591           bool addrTakenF = F->hasAddressTaken();
00592           bool addrTakenG = G->hasAddressTaken();
00593           if (!addrTakenF && addrTakenG) {
00594             std::swap(FnVec[i], FnVec[j]);
00595             std::swap(F, G);
00596       std::swap(addrTakenF, addrTakenG);
00597     }
00598 
00599           if (addrTakenF && addrTakenG) {
00600             ThunkGToF(F, G);
00601           } else {
00602             assert(!addrTakenG);
00603             AliasGToF(F, G);
00604           }
00605   } break;
00606       }
00607       break;
00608   }
00609 
00610   ++NumFunctionsMerged;
00611   return true;
00612 }
00613 
00614 // ===----------------------------------------------------------------------===
00615 // Pass definition
00616 // ===----------------------------------------------------------------------===
00617 
00618 bool MergeFunctions::runOnModule(Module &M) {
00619   bool Changed = false;
00620 
00621   std::map<unsigned long, std::vector<Function *> > FnMap;
00622 
00623   for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
00624     if (F->isDeclaration() || F->isIntrinsic())
00625       continue;
00626 
00627     FnMap[hash(F)].push_back(F);
00628   }
00629 
00630   // TODO: instead of running in a loop, we could also fold functions in
00631   // callgraph order. Constructing the CFG probably isn't cheaper than just
00632   // running in a loop, unless it happened to already be available.
00633 
00634   bool LocalChanged;
00635   do {
00636     LocalChanged = false;
00637     DOUT << "size: " << FnMap.size() << "\n";
00638     for (std::map<unsigned long, std::vector<Function *> >::iterator
00639          I = FnMap.begin(), E = FnMap.end(); I != E; ++I) {
00640       std::vector<Function *> &FnVec = I->second;
00641       DOUT << "hash (" << I->first << "): " << FnVec.size() << "\n";
00642 
00643       for (int i = 0, e = FnVec.size(); i != e; ++i) {
00644         for (int j = i + 1; j != e; ++j) {
00645           bool isEqual = equals(FnVec[i], FnVec[j]);
00646 
00647           DEBUG(errs() << "  " << FnVec[i]->getName()
00648                 << (isEqual ? " == " : " != ")
00649                 << FnVec[j]->getName() << "\n");
00650 
00651           if (isEqual) {
00652             if (fold(FnVec, i, j)) {
00653               LocalChanged = true;
00654               FnVec.erase(FnVec.begin() + j);
00655               --j, --e;
00656             }
00657           }
00658         }
00659       }
00660 
00661     }
00662     Changed |= LocalChanged;
00663   } while (LocalChanged);
00664 
00665   return Changed;
00666 }