lib/Transforms/IPO/MergeFunctions.cpp

   1 //===- MergeFunctions.cpp - Merge identical functions ---------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass looks for equivalent functions that are mergable and folds them.
  11 //
  12 // A hash is computed from the function, based on its type and number of
  13 // basic blocks.
  14 //
  15 // Once all hashes are computed, we perform an expensive equality comparison
  16 // on each function pair. This takes n^2/2 comparisons per bucket, so it's
  17 // important that the hash function be high quality. The equality comparison
  18 // iterates through each instruction in each basic block.
  19 //
  20 // When a match is found the functions are folded. If both functions are
  21 // overridable, we move the functionality into a new internal function and
  22 // leave two overridable thunks to it.
  23 //
  24 //===----------------------------------------------------------------------===//
  25 //
  26 // Future work:
  27 //
  28 // * virtual functions.
  29 //
  30 // Many functions have their address taken by the virtual function table for
  31 // the object they belong to. However, as long as it's only used for a lookup
  32 // and call, this is irrelevant, and we'd like to fold such implementations.
  33 //
  34 // * use SCC to cut down on pair-wise comparisons and solve larger cycles.
  35 //
  36 // The current implementation loops over a pair-wise comparison of all
  37 // functions in the program where the two functions in the pair are treated as
  38 // assumed to be equal until proven otherwise. We could both use fewer
  39 // comparisons and optimize more complex cases if we used strongly connected
  40 // components of the call graph.
  41 //
  42 // * be smarter about bitcast.
  43 //
  44 // In order to fold functions, we will sometimes add either bitcast instructions
  45 // or bitcast constant expressions. Unfortunately, this can confound further
  46 // analysis since the two functions differ where one has a bitcast and the
  47 // other doesn't. We should learn to peer through bitcasts without imposing bad
  48 // performance properties.
  49 //
  50 // * don't emit aliases for Mach-O.
  51 //
  52 // Mach-O doesn't support aliases which means that we must avoid introducing
  53 // them in the bitcode on architectures which don't support them, such as
  54 // Mac OSX. There's a few approaches to this problem;
  55 //   a) teach codegen to lower global aliases to thunks on platforms which don't
  56 //      support them.
  57 //   b) always emit thunks, and create a separate thunk-to-alias pass which
  58 //      runs on ELF systems. This has the added benefit of transforming other
  59 //      thunks such as those produced by a C++ frontend into aliases when legal
  60 //      to do so.
  61 //
  62 //===----------------------------------------------------------------------===//
  63
  64 #define DEBUG_TYPE "mergefunc"
  65 #include "llvm/Transforms/IPO.h"
  66 #include "llvm/ADT/DenseMap.h"
  67 #include "llvm/ADT/FoldingSet.h"
  68 #include "llvm/ADT/SmallSet.h"
  69 #include "llvm/ADT/Statistic.h"
  70 #include "llvm/Constants.h"
  71 #include "llvm/InlineAsm.h"
  72 #include "llvm/Instructions.h"
  73 #include "llvm/LLVMContext.h"
  74 #include "llvm/Module.h"
  75 #include "llvm/Pass.h"
  76 #include "llvm/Support/CallSite.h"
  77 #include "llvm/Support/Debug.h"
  78 #include "llvm/Support/ErrorHandling.h"
  79 #include "llvm/Support/raw_ostream.h"
  80 #include "llvm/Target/TargetData.h"
  81 #include <map>
  82 #include <vector>
  83 using namespace llvm;
  84
  85 STATISTIC(NumFunctionsMerged, "Number of functions merged");
  86
  87 namespace {
  88   class MergeFunctions : public ModulePass {
  89   public:
  90     static char ID; // Pass identification, replacement for typeid
  91     MergeFunctions() : ModulePass(&ID) {}
  92
  93     bool runOnModule(Module &M);
  94
  95   private:
  96     bool isEquivalentGEP(const GetElementPtrInst *GEP1,
  97                          const GetElementPtrInst *GEP2);
  98
  99     bool equals(const BasicBlock *BB1, const BasicBlock *BB2);
 100     bool equals(const Function *F, const Function *G);
 101
 102     bool compare(const Value *V1, const Value *V2);
 103
 104     const Function *LHS, *RHS;
 105     typedef DenseMap<const Value *, unsigned long> IDMap;
 106     IDMap Map;
 107     DenseMap<const Function *, IDMap> Domains;
 108     DenseMap<const Function *, unsigned long> DomainCount;
 109     TargetData *TD;
 110   };
 111 }
 112
 113 char MergeFunctions::ID = 0;
 114 static RegisterPass<MergeFunctions> X("mergefunc", "Merge Functions");
 115
 116 ModulePass *llvm::createMergeFunctionsPass() {
 117   return new MergeFunctions();
 118 }
 119
 120 // ===----------------------------------------------------------------------===
 121 // Comparison of functions
 122 // ===----------------------------------------------------------------------===
 123
 124 static unsigned long hash(const Function *F) {
 125   const FunctionType *FTy = F->getFunctionType();
 126
 127   FoldingSetNodeID ID;
 128   ID.AddInteger(F->size());
 129   ID.AddInteger(F->getCallingConv());
 130   ID.AddBoolean(F->hasGC());
 131   ID.AddBoolean(FTy->isVarArg());
 132   ID.AddInteger(FTy->getReturnType()->getTypeID());
 133   for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
 134     ID.AddInteger(FTy->getParamType(i)->getTypeID());
 135   return ID.ComputeHash();
 136 }
 137
 138 /// isEquivalentType - any two pointers are equivalent. Otherwise, standard
 139 /// type equivalence rules apply.
 140 static bool isEquivalentType(const Type *Ty1, const Type *Ty2) {
 141   if (Ty1 == Ty2)
 142     return true;
 143   if (Ty1->getTypeID() != Ty2->getTypeID())
 144     return false;
 145
 146   switch(Ty1->getTypeID()) {
 147   default:
 148     llvm_unreachable("Unknown type!");
 149     // Fall through in Release mode.
 150   case Type::IntegerTyID:
 151   case Type::OpaqueTyID:
 152     // Ty1 == Ty2 would have returned true earlier.
 153     return false;
 154
 155   case Type::VoidTyID:
 156   case Type::FloatTyID:
 157   case Type::DoubleTyID:
 158   case Type::X86_FP80TyID:
 159   case Type::FP128TyID:
 160   case Type::PPC_FP128TyID:
 161   case Type::LabelTyID:
 162   case Type::MetadataTyID:
 163     return true;
 164
 165   case Type::PointerTyID: {
 166     const PointerType *PTy1 = cast<PointerType>(Ty1);
 167     const PointerType *PTy2 = cast<PointerType>(Ty2);
 168     return PTy1->getAddressSpace() == PTy2->getAddressSpace();
 169   }
 170
 171   case Type::StructTyID: {
 172     const StructType *STy1 = cast<StructType>(Ty1);
 173     const StructType *STy2 = cast<StructType>(Ty2);
 174     if (STy1->getNumElements() != STy2->getNumElements())
 175       return false;
 176
 177     if (STy1->isPacked() != STy2->isPacked())
 178       return false;
 179
 180     for (unsigned i = 0, e = STy1->getNumElements(); i != e; ++i) {
 181       if (!isEquivalentType(STy1->getElementType(i), STy2->getElementType(i)))
 182         return false;
 183     }
 184     return true;
 185   }
 186
 187   case Type::UnionTyID: {
 188     const UnionType *UTy1 = cast<UnionType>(Ty1);
 189     const UnionType *UTy2 = cast<UnionType>(Ty2);
 190
 191     // TODO: we could be fancy with union(A, union(A, B)) === union(A, B), etc.
 192     if (UTy1->getNumElements() != UTy2->getNumElements())
 193       return false;
 194
 195     for (unsigned i = 0, e = UTy1->getNumElements(); i != e; ++i) {
 196       if (!isEquivalentType(UTy1->getElementType(i), UTy2->getElementType(i)))
 197         return false;
 198     }
 199     return true;
 200   }
 201
 202   case Type::FunctionTyID: {
 203     const FunctionType *FTy1 = cast<FunctionType>(Ty1);
 204     const FunctionType *FTy2 = cast<FunctionType>(Ty2);
 205     if (FTy1->getNumParams() != FTy2->getNumParams() ||
 206         FTy1->isVarArg() != FTy2->isVarArg())
 207       return false;
 208
 209     if (!isEquivalentType(FTy1->getReturnType(), FTy2->getReturnType()))
 210       return false;
 211
 212     for (unsigned i = 0, e = FTy1->getNumParams(); i != e; ++i) {
 213       if (!isEquivalentType(FTy1->getParamType(i), FTy2->getParamType(i)))
 214         return false;
 215     }
 216     return true;
 217   }
 218
 219   case Type::ArrayTyID: {
 220     const ArrayType *ATy1 = cast<ArrayType>(Ty1);
 221     const ArrayType *ATy2 = cast<ArrayType>(Ty2);
 222     return ATy1->getNumElements() == ATy2->getNumElements() &&
 223            isEquivalentType(ATy1->getElementType(), ATy2->getElementType());
 224   }
 225   case Type::VectorTyID: {
 226     const VectorType *VTy1 = cast<VectorType>(Ty1);
 227     const VectorType *VTy2 = cast<VectorType>(Ty2);
 228     return VTy1->getNumElements() == VTy2->getNumElements() &&
 229            isEquivalentType(VTy1->getElementType(), VTy2->getElementType());
 230   }
 231   }
 232 }
 233
 234 /// isEquivalentOperation - determine whether the two operations are the same
 235 /// except that pointer-to-A and pointer-to-B are equivalent. This should be
 236 /// kept in sync with Instruction::isSameOperationAs.
 237 static bool
 238 isEquivalentOperation(const Instruction *I1, const Instruction *I2) {
 239   if (I1->getOpcode() != I2->getOpcode() ||
 240       I1->getNumOperands() != I2->getNumOperands() ||
 241       !isEquivalentType(I1->getType(), I2->getType()) ||
 242       !I1->hasSameSubclassOptionalData(I2))
 243     return false;
 244
 245   // We have two instructions of identical opcode and #operands.  Check to see
 246   // if all operands are the same type
 247   for (unsigned i = 0, e = I1->getNumOperands(); i != e; ++i)
 248     if (!isEquivalentType(I1->getOperand(i)->getType(),
 249                           I2->getOperand(i)->getType()))
 250       return false;
 251
 252   // Check special state that is a part of some instructions.
 253   if (const LoadInst *LI = dyn_cast<LoadInst>(I1))
 254     return LI->isVolatile() == cast<LoadInst>(I2)->isVolatile() &&
 255            LI->getAlignment() == cast<LoadInst>(I2)->getAlignment();
 256   if (const StoreInst *SI = dyn_cast<StoreInst>(I1))
 257     return SI->isVolatile() == cast<StoreInst>(I2)->isVolatile() &&
 258            SI->getAlignment() == cast<StoreInst>(I2)->getAlignment();
 259   if (const CmpInst *CI = dyn_cast<CmpInst>(I1))
 260     return CI->getPredicate() == cast<CmpInst>(I2)->getPredicate();
 261   if (const CallInst *CI = dyn_cast<CallInst>(I1))
 262     return CI->isTailCall() == cast<CallInst>(I2)->isTailCall() &&
 263            CI->getCallingConv() == cast<CallInst>(I2)->getCallingConv() &&
 264            CI->getAttributes().getRawPointer() ==
 265              cast<CallInst>(I2)->getAttributes().getRawPointer();
 266   if (const InvokeInst *CI = dyn_cast<InvokeInst>(I1))
 267     return CI->getCallingConv() == cast<InvokeInst>(I2)->getCallingConv() &&
 268            CI->getAttributes().getRawPointer() ==
 269              cast<InvokeInst>(I2)->getAttributes().getRawPointer();
 270   if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(I1)) {
 271     if (IVI->getNumIndices() != cast<InsertValueInst>(I2)->getNumIndices())
 272       return false;
 273     for (unsigned i = 0, e = IVI->getNumIndices(); i != e; ++i)
 274       if (IVI->idx_begin()[i] != cast<InsertValueInst>(I2)->idx_begin()[i])
 275         return false;
 276     return true;
 277   }
 278   if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(I1)) {
 279     if (EVI->getNumIndices() != cast<ExtractValueInst>(I2)->getNumIndices())
 280       return false;
 281     for (unsigned i = 0, e = EVI->getNumIndices(); i != e; ++i)
 282       if (EVI->idx_begin()[i] != cast<ExtractValueInst>(I2)->idx_begin()[i])
 283         return false;
 284     return true;
 285   }
 286
 287   return true;
 288 }
 289
 290 bool MergeFunctions::isEquivalentGEP(const GetElementPtrInst *GEP1,
 291                                      const GetElementPtrInst *GEP2) {
 292   if (TD && GEP1->hasAllConstantIndices() && GEP2->hasAllConstantIndices()) {
 293     SmallVector<Value *, 8> Indices1, Indices2;
 294     for (GetElementPtrInst::const_op_iterator I = GEP1->idx_begin(),
 295            E = GEP1->idx_end(); I != E; ++I) {
 296       Indices1.push_back(*I);
 297     }
 298     for (GetElementPtrInst::const_op_iterator I = GEP2->idx_begin(),
 299            E = GEP2->idx_end(); I != E; ++I) {
 300       Indices2.push_back(*I);
 301     }
 302     uint64_t Offset1 = TD->getIndexedOffset(GEP1->getPointerOperandType(),
 303                                             Indices1.data(), Indices1.size());
 304     uint64_t Offset2 = TD->getIndexedOffset(GEP2->getPointerOperandType(),
 305                                             Indices2.data(), Indices2.size());
 306     return Offset1 == Offset2;
 307   }
 308
 309   // Equivalent types aren't enough.
 310   if (GEP1->getPointerOperand()->getType() !=
 311       GEP2->getPointerOperand()->getType())
 312     return false;
 313
 314   if (GEP1->getNumOperands() != GEP2->getNumOperands())
 315     return false;
 316
 317   for (unsigned i = 0, e = GEP1->getNumOperands(); i != e; ++i) {
 318     if (!compare(GEP1->getOperand(i), GEP2->getOperand(i)))
 319       return false;
 320   }
 321
 322   return true;
 323 }
 324
 325 bool MergeFunctions::compare(const Value *V1, const Value *V2) {
 326   if (V1 == LHS || V1 == RHS)
 327     if (V2 == LHS || V2 == RHS)
 328       return true;
 329
 330   // TODO: constant expressions in terms of LHS and RHS
 331   if (isa<Constant>(V1))
 332     return V1 == V2;
 333
 334   if (isa<InlineAsm>(V1) && isa<InlineAsm>(V2)) {
 335     const InlineAsm *IA1 = cast<InlineAsm>(V1);
 336     const InlineAsm *IA2 = cast<InlineAsm>(V2);
 337     return IA1->getAsmString() == IA2->getAsmString() &&
 338            IA1->getConstraintString() == IA2->getConstraintString();
 339   }
 340
 341   // We enumerate constants globally and arguments, basic blocks or
 342   // instructions within the function they belong to.
 343   const Function *Domain1 = NULL;
 344   if (const Argument *A = dyn_cast<Argument>(V1)) {
 345     Domain1 = A->getParent();
 346   } else if (const BasicBlock *BB = dyn_cast<BasicBlock>(V1)) {
 347     Domain1 = BB->getParent();
 348   } else if (const Instruction *I = dyn_cast<Instruction>(V1)) {
 349     Domain1 = I->getParent()->getParent();
 350   }
 351
 352   const Function *Domain2 = NULL;
 353   if (const Argument *A = dyn_cast<Argument>(V2)) {
 354     Domain2 = A->getParent();
 355   } else if (const BasicBlock *BB = dyn_cast<BasicBlock>(V2)) {
 356     Domain2 = BB->getParent();
 357   } else if (const Instruction *I = dyn_cast<Instruction>(V2)) {
 358     Domain2 = I->getParent()->getParent();
 359   }
 360
 361   if (Domain1 != Domain2)
 362     if (Domain1 != LHS && Domain1 != RHS)
 363       if (Domain2 != LHS && Domain2 != RHS)
 364         return false;
 365
 366   IDMap &Map1 = Domains[Domain1];
 367   unsigned long &ID1 = Map1[V1];
 368   if (!ID1)
 369     ID1 = ++DomainCount[Domain1];
 370
 371   IDMap &Map2 = Domains[Domain2];
 372   unsigned long &ID2 = Map2[V2];
 373   if (!ID2)
 374     ID2 = ++DomainCount[Domain2];
 375
 376   return ID1 == ID2;
 377 }
 378
 379 bool MergeFunctions::equals(const BasicBlock *BB1, const BasicBlock *BB2) {
 380   BasicBlock::const_iterator FI = BB1->begin(), FE = BB1->end();
 381   BasicBlock::const_iterator GI = BB2->begin(), GE = BB2->end();
 382
 383   do {
 384     if (!compare(FI, GI))
 385       return false;
 386
 387     if (isa<GetElementPtrInst>(FI) && isa<GetElementPtrInst>(GI)) {
 388       const GetElementPtrInst *GEP1 = cast<GetElementPtrInst>(FI);
 389       const GetElementPtrInst *GEP2 = cast<GetElementPtrInst>(GI);
 390
 391       if (!compare(GEP1->getPointerOperand(), GEP2->getPointerOperand()))
 392         return false;
 393
 394       if (!isEquivalentGEP(GEP1, GEP2))
 395         return false;
 396     } else {
 397       if (!isEquivalentOperation(FI, GI))
 398         return false;
 399
 400       for (unsigned i = 0, e = FI->getNumOperands(); i != e; ++i) {
 401         Value *OpF = FI->getOperand(i);
 402         Value *OpG = GI->getOperand(i);
 403
 404         if (!compare(OpF, OpG))
 405           return false;
 406
 407         if (OpF->getValueID() != OpG->getValueID() ||
 408             !isEquivalentType(OpF->getType(), OpG->getType()))
 409           return false;
 410       }
 411     }
 412
 413     ++FI, ++GI;
 414   } while (FI != FE && GI != GE);
 415
 416   return FI == FE && GI == GE;
 417 }
 418
 419 bool MergeFunctions::equals(const Function *F, const Function *G) {
 420   // We need to recheck everything, but check the things that weren't included
 421   // in the hash first.
 422
 423   if (F->getAttributes() != G->getAttributes())
 424     return false;
 425
 426   if (F->hasGC() != G->hasGC())
 427     return false;
 428
 429   if (F->hasGC() && F->getGC() != G->getGC())
 430     return false;
 431
 432   if (F->hasSection() != G->hasSection())
 433     return false;
 434
 435   if (F->hasSection() && F->getSection() != G->getSection())
 436     return false;
 437
 438   if (F->isVarArg() != G->isVarArg())
 439     return false;
 440
 441   // TODO: if it's internal and only used in direct calls, we could handle this
 442   // case too.
 443   if (F->getCallingConv() != G->getCallingConv())
 444     return false;
 445
 446   if (!isEquivalentType(F->getFunctionType(), G->getFunctionType()))
 447     return false;
 448
 449   assert(F->arg_size() == G->arg_size() &&
 450          "Identical functions have a different number of args.");
 451
 452   LHS = F;
 453   RHS = G;
 454
 455   // Visit the arguments so that they get enumerated in the order they're
 456   // passed in.
 457   for (Function::const_arg_iterator fi = F->arg_begin(), gi = G->arg_begin(),
 458          fe = F->arg_end(); fi != fe; ++fi, ++gi) {
 459     if (!compare(fi, gi))
 460       llvm_unreachable("Arguments repeat");
 461   }
 462
 463   SmallVector<const BasicBlock *, 8> FBBs, GBBs;
 464   SmallSet<const BasicBlock *, 128> VisitedBBs; // in terms of F.
 465   FBBs.push_back(&F->getEntryBlock());
 466   GBBs.push_back(&G->getEntryBlock());
 467   VisitedBBs.insert(FBBs[0]);
 468   while (!FBBs.empty()) {
 469     const BasicBlock *FBB = FBBs.pop_back_val();
 470     const BasicBlock *GBB = GBBs.pop_back_val();
 471     if (!compare(FBB, GBB) || !equals(FBB, GBB)) {
 472       Domains.clear();
 473       DomainCount.clear();
 474       return false;
 475     }
 476     const TerminatorInst *FTI = FBB->getTerminator();
 477     const TerminatorInst *GTI = GBB->getTerminator();
 478     assert(FTI->getNumSuccessors() == GTI->getNumSuccessors());
 479     for (unsigned i = 0, e = FTI->getNumSuccessors(); i != e; ++i) {
 480       if (!VisitedBBs.insert(FTI->getSuccessor(i)))
 481         continue;
 482       FBBs.push_back(FTI->getSuccessor(i));
 483       GBBs.push_back(GTI->getSuccessor(i));
 484     }
 485   }
 486
 487   Domains.clear();
 488   DomainCount.clear();
 489   return true;
 490 }
 491
 492 // ===----------------------------------------------------------------------===
 493 // Folding of functions
 494 // ===----------------------------------------------------------------------===
 495
 496 // Cases:
 497 // * F is external strong, G is external strong:
 498 //   turn G into a thunk to F    (1)
 499 // * F is external strong, G is external weak:
 500 //   turn G into a thunk to F    (1)
 501 // * F is external weak, G is external weak:
 502 //   unfoldable
 503 // * F is external strong, G is internal:
 504 //   address of G taken:
 505 //     turn G into a thunk to F  (1)
 506 //   address of G not taken:
 507 //     make G an alias to F      (2)
 508 // * F is internal, G is external weak
 509 //   address of F is taken:
 510 //     turn G into a thunk to F  (1)
 511 //   address of F is not taken:
 512 //     make G an alias of F      (2)
 513 // * F is internal, G is internal:
 514 //   address of F and G are taken:
 515 //     turn G into a thunk to F  (1)
 516 //   address of G is not taken:
 517 //     make G an alias to F      (2)
 518 //
 519 // alias requires linkage == (external,local,weak) fallback to creating a thunk
 520 // external means 'externally visible' linkage != (internal,private)
 521 // internal means linkage == (internal,private)
 522 // weak means linkage mayBeOverridable
 523 // being external implies that the address is taken
 524 //
 525 // 1. turn G into a thunk to F
 526 // 2. make G an alias to F
 527
 528 enum LinkageCategory {
 529   ExternalStrong,
 530   ExternalWeak,
 531   Internal
 532 };
 533
 534 static LinkageCategory categorize(const Function *F) {
 535   switch (F->getLinkage()) {
 536   case GlobalValue::InternalLinkage:
 537   case GlobalValue::PrivateLinkage:
 538   case GlobalValue::LinkerPrivateLinkage:
 539     return Internal;
 540
 541   case GlobalValue::WeakAnyLinkage:
 542   case GlobalValue::WeakODRLinkage:
 543   case GlobalValue::ExternalWeakLinkage:
 544   case GlobalValue::LinkerPrivateWeakLinkage:
 545     return ExternalWeak;
 546
 547   case GlobalValue::ExternalLinkage:
 548   case GlobalValue::AvailableExternallyLinkage:
 549   case GlobalValue::LinkOnceAnyLinkage:
 550   case GlobalValue::LinkOnceODRLinkage:
 551   case GlobalValue::AppendingLinkage:
 552   case GlobalValue::DLLImportLinkage:
 553   case GlobalValue::DLLExportLinkage:
 554   case GlobalValue::CommonLinkage:
 555     return ExternalStrong;
 556   }
 557
 558   llvm_unreachable("Unknown LinkageType.");
 559   return ExternalWeak;
 560 }
 561
 562 static void ThunkGToF(Function *F, Function *G) {
 563   if (!G->mayBeOverridden()) {
 564     // Redirect direct callers of G to F.
 565     Constant *BitcastF = ConstantExpr::getBitCast(F, G->getType());
 566     for (Value::use_iterator UI = G->use_begin(), UE = G->use_end();
 567          UI != UE;) {
 568       Value::use_iterator TheIter = UI;
 569       ++UI;
 570       CallSite CS(*TheIter);
 571       if (CS && CS.isCallee(TheIter))
 572         TheIter.getUse().set(BitcastF);
 573     }
 574   }
 575
 576   Function *NewG = Function::Create(G->getFunctionType(), G->getLinkage(), "",
 577                                     G->getParent());
 578   BasicBlock *BB = BasicBlock::Create(F->getContext(), "", NewG);
 579
 580   SmallVector<Value *, 16> Args;
 581   unsigned i = 0;
 582   const FunctionType *FFTy = F->getFunctionType();
 583   for (Function::arg_iterator AI = NewG->arg_begin(), AE = NewG->arg_end();
 584        AI != AE; ++AI) {
 585     if (FFTy->getParamType(i) == AI->getType()) {
 586       Args.push_back(AI);
 587     } else {
 588       Args.push_back(new BitCastInst(AI, FFTy->getParamType(i), "", BB));
 589     }
 590     ++i;
 591   }
 592
 593   CallInst *CI = CallInst::Create(F, Args.begin(), Args.end(), "", BB);
 594   CI->setTailCall();
 595   CI->setCallingConv(F->getCallingConv());
 596   if (NewG->getReturnType()->isVoidTy()) {
 597     ReturnInst::Create(F->getContext(), BB);
 598   } else if (CI->getType() != NewG->getReturnType()) {
 599     Value *BCI = new BitCastInst(CI, NewG->getReturnType(), "", BB);
 600     ReturnInst::Create(F->getContext(), BCI, BB);
 601   } else {
 602     ReturnInst::Create(F->getContext(), CI, BB);
 603   }
 604
 605   NewG->copyAttributesFrom(G);
 606   NewG->takeName(G);
 607   G->replaceAllUsesWith(NewG);
 608   G->eraseFromParent();
 609 }
 610
 611 static void AliasGToF(Function *F, Function *G) {
 612   // Darwin will trigger llvm_unreachable if asked to codegen an alias.
 613   return ThunkGToF(F, G);
 614
 615 #if 0
 616   if (!G->hasExternalLinkage() && !G->hasLocalLinkage() && !G->hasWeakLinkage())
 617     return ThunkGToF(F, G);
 618
 619   GlobalAlias *GA = new GlobalAlias(
 620     G->getType(), G->getLinkage(), "",
 621     ConstantExpr::getBitCast(F, G->getType()), G->getParent());
 622   F->setAlignment(std::max(F->getAlignment(), G->getAlignment()));
 623   GA->takeName(G);
 624   GA->setVisibility(G->getVisibility());
 625   G->replaceAllUsesWith(GA);
 626   G->eraseFromParent();
 627 #endif
 628 }
 629
 630 static bool fold(std::vector<Function *> &FnVec, unsigned i, unsigned j) {
 631   Function *F = FnVec[i];
 632   Function *G = FnVec[j];
 633
 634   LinkageCategory catF = categorize(F);
 635   LinkageCategory catG = categorize(G);
 636
 637   if (catF == ExternalWeak || (catF == Internal && catG == ExternalStrong)) {
 638     std::swap(FnVec[i], FnVec[j]);
 639     std::swap(F, G);
 640     std::swap(catF, catG);
 641   }
 642
 643   switch (catF) {
 644   case ExternalStrong:
 645     switch (catG) {
 646     case ExternalStrong:
 647     case ExternalWeak:
 648       ThunkGToF(F, G);
 649       break;
 650     case Internal:
 651       if (G->hasAddressTaken())
 652         ThunkGToF(F, G);
 653       else
 654         AliasGToF(F, G);
 655       break;
 656     }
 657     break;
 658
 659   case ExternalWeak: {
 660     assert(catG == ExternalWeak);
 661
 662     // Make them both thunks to the same internal function.
 663     F->setAlignment(std::max(F->getAlignment(), G->getAlignment()));
 664     Function *H = Function::Create(F->getFunctionType(), F->getLinkage(), "",
 665                                    F->getParent());
 666     H->copyAttributesFrom(F);
 667     H->takeName(F);
 668     F->replaceAllUsesWith(H);
 669
 670     ThunkGToF(F, G);
 671     ThunkGToF(F, H);
 672
 673     F->setLinkage(GlobalValue::InternalLinkage);
 674   } break;
 675
 676   case Internal:
 677     switch (catG) {
 678     case ExternalStrong:
 679       llvm_unreachable(0);
 680       // fall-through
 681     case ExternalWeak:
 682       if (F->hasAddressTaken())
 683         ThunkGToF(F, G);
 684       else
 685         AliasGToF(F, G);
 686       break;
 687     case Internal: {
 688       bool addrTakenF = F->hasAddressTaken();
 689       bool addrTakenG = G->hasAddressTaken();
 690       if (!addrTakenF && addrTakenG) {
 691         std::swap(FnVec[i], FnVec[j]);
 692         std::swap(F, G);
 693         std::swap(addrTakenF, addrTakenG);
 694       }
 695
 696       if (addrTakenF && addrTakenG) {
 697         ThunkGToF(F, G);
 698       } else {
 699         assert(!addrTakenG);
 700         AliasGToF(F, G);
 701       }
 702     } break;
 703   } break;
 704   }
 705
 706   ++NumFunctionsMerged;
 707   return true;
 708 }
 709
 710 // ===----------------------------------------------------------------------===
 711 // Pass definition
 712 // ===----------------------------------------------------------------------===
 713
 714 bool MergeFunctions::runOnModule(Module &M) {
 715   bool Changed = false;
 716
 717   std::map<unsigned long, std::vector<Function *> > FnMap;
 718
 719   for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
 720     if (F->isDeclaration())
 721       continue;
 722
 723     FnMap[hash(F)].push_back(F);
 724   }
 725
 726   TD = getAnalysisIfAvailable<TargetData>();
 727
 728   bool LocalChanged;
 729   do {
 730     LocalChanged = false;
 731     DEBUG(dbgs() << "size: " << FnMap.size() << "\n");
 732     for (std::map<unsigned long, std::vector<Function *> >::iterator
 733            I = FnMap.begin(), E = FnMap.end(); I != E; ++I) {
 734       std::vector<Function *> &FnVec = I->second;
 735       DEBUG(dbgs() << "hash (" << I->first << "): " << FnVec.size() << "\n");
 736
 737       for (int i = 0, e = FnVec.size(); i != e; ++i) {
 738         for (int j = i + 1; j != e; ++j) {
 739           bool isEqual = equals(FnVec[i], FnVec[j]);
 740
 741           DEBUG(dbgs() << "  " << FnVec[i]->getName()
 742                 << (isEqual ? " == " : " != ")
 743                 << FnVec[j]->getName() << "\n");
 744
 745           if (isEqual) {
 746             if (fold(FnVec, i, j)) {
 747               LocalChanged = true;
 748               FnVec.erase(FnVec.begin() + j);
 749               --j, --e;
 750             }
 751           }
 752         }
 753       }
 754
 755     }
 756     Changed |= LocalChanged;
 757   } while (LocalChanged);
 758
 759   return Changed;
 760 }