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   case Type::VectorTyID: {
 221     const SequentialType *STy1 = cast<SequentialType>(Ty1);
 222     const SequentialType *STy2 = cast<SequentialType>(Ty2);
 223     return isEquivalentType(STy1->getElementType(), STy2->getElementType());
 224   }
 225   }
 226 }
 227
 228 /// isEquivalentOperation - determine whether the two operations are the same
 229 /// except that pointer-to-A and pointer-to-B are equivalent. This should be
 230 /// kept in sync with Instruction::isSameOperationAs.
 231 static bool
 232 isEquivalentOperation(const Instruction *I1, const Instruction *I2) {
 233   if (I1->getOpcode() != I2->getOpcode() ||
 234       I1->getNumOperands() != I2->getNumOperands() ||
 235       !isEquivalentType(I1->getType(), I2->getType()) ||
 236       !I1->hasSameSubclassOptionalData(I2))
 237     return false;
 238
 239   // We have two instructions of identical opcode and #operands.  Check to see
 240   // if all operands are the same type
 241   for (unsigned i = 0, e = I1->getNumOperands(); i != e; ++i)
 242     if (!isEquivalentType(I1->getOperand(i)->getType(),
 243                           I2->getOperand(i)->getType()))
 244       return false;
 245
 246   // Check special state that is a part of some instructions.
 247   if (const LoadInst *LI = dyn_cast<LoadInst>(I1))
 248     return LI->isVolatile() == cast<LoadInst>(I2)->isVolatile() &&
 249            LI->getAlignment() == cast<LoadInst>(I2)->getAlignment();
 250   if (const StoreInst *SI = dyn_cast<StoreInst>(I1))
 251     return SI->isVolatile() == cast<StoreInst>(I2)->isVolatile() &&
 252            SI->getAlignment() == cast<StoreInst>(I2)->getAlignment();
 253   if (const CmpInst *CI = dyn_cast<CmpInst>(I1))
 254     return CI->getPredicate() == cast<CmpInst>(I2)->getPredicate();
 255   if (const CallInst *CI = dyn_cast<CallInst>(I1))
 256     return CI->isTailCall() == cast<CallInst>(I2)->isTailCall() &&
 257            CI->getCallingConv() == cast<CallInst>(I2)->getCallingConv() &&
 258            CI->getAttributes().getRawPointer() ==
 259              cast<CallInst>(I2)->getAttributes().getRawPointer();
 260   if (const InvokeInst *CI = dyn_cast<InvokeInst>(I1))
 261     return CI->getCallingConv() == cast<InvokeInst>(I2)->getCallingConv() &&
 262            CI->getAttributes().getRawPointer() ==
 263              cast<InvokeInst>(I2)->getAttributes().getRawPointer();
 264   if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(I1)) {
 265     if (IVI->getNumIndices() != cast<InsertValueInst>(I2)->getNumIndices())
 266       return false;
 267     for (unsigned i = 0, e = IVI->getNumIndices(); i != e; ++i)
 268       if (IVI->idx_begin()[i] != cast<InsertValueInst>(I2)->idx_begin()[i])
 269         return false;
 270     return true;
 271   }
 272   if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(I1)) {
 273     if (EVI->getNumIndices() != cast<ExtractValueInst>(I2)->getNumIndices())
 274       return false;
 275     for (unsigned i = 0, e = EVI->getNumIndices(); i != e; ++i)
 276       if (EVI->idx_begin()[i] != cast<ExtractValueInst>(I2)->idx_begin()[i])
 277         return false;
 278     return true;
 279   }
 280
 281   return true;
 282 }
 283
 284 bool MergeFunctions::isEquivalentGEP(const GetElementPtrInst *GEP1,
 285                                      const GetElementPtrInst *GEP2) {
 286   if (TD && GEP1->hasAllConstantIndices() && GEP2->hasAllConstantIndices()) {
 287     SmallVector<Value *, 8> Indices1, Indices2;
 288     for (GetElementPtrInst::const_op_iterator I = GEP1->idx_begin(),
 289            E = GEP1->idx_end(); I != E; ++I) {
 290       Indices1.push_back(*I);
 291     }
 292     for (GetElementPtrInst::const_op_iterator I = GEP2->idx_begin(),
 293            E = GEP2->idx_end(); I != E; ++I) {
 294       Indices2.push_back(*I);
 295     }
 296     uint64_t Offset1 = TD->getIndexedOffset(GEP1->getPointerOperandType(),
 297                                             Indices1.data(), Indices1.size());
 298     uint64_t Offset2 = TD->getIndexedOffset(GEP2->getPointerOperandType(),
 299                                             Indices2.data(), Indices2.size());
 300     return Offset1 == Offset2;
 301   }
 302
 303   // Equivalent types aren't enough.
 304   if (GEP1->getPointerOperand()->getType() !=
 305       GEP2->getPointerOperand()->getType())
 306     return false;
 307
 308   if (GEP1->getNumOperands() != GEP2->getNumOperands())
 309     return false;
 310
 311   for (unsigned i = 0, e = GEP1->getNumOperands(); i != e; ++i) {
 312     if (!compare(GEP1->getOperand(i), GEP2->getOperand(i)))
 313       return false;
 314   }
 315
 316   return true;
 317 }
 318
 319 bool MergeFunctions::compare(const Value *V1, const Value *V2) {
 320   if (V1 == LHS || V1 == RHS)
 321     if (V2 == LHS || V2 == RHS)
 322       return true;
 323
 324   // TODO: constant expressions in terms of LHS and RHS
 325   if (isa<Constant>(V1))
 326     return V1 == V2;
 327
 328   if (isa<InlineAsm>(V1) && isa<InlineAsm>(V2)) {
 329     const InlineAsm *IA1 = cast<InlineAsm>(V1);
 330     const InlineAsm *IA2 = cast<InlineAsm>(V2);
 331     return IA1->getAsmString() == IA2->getAsmString() &&
 332            IA1->getConstraintString() == IA2->getConstraintString();
 333   }
 334
 335   // We enumerate constants globally and arguments, basic blocks or
 336   // instructions within the function they belong to.
 337   const Function *Domain1 = NULL;
 338   if (const Argument *A = dyn_cast<Argument>(V1)) {
 339     Domain1 = A->getParent();
 340   } else if (const BasicBlock *BB = dyn_cast<BasicBlock>(V1)) {
 341     Domain1 = BB->getParent();
 342   } else if (const Instruction *I = dyn_cast<Instruction>(V1)) {
 343     Domain1 = I->getParent()->getParent();
 344   }
 345
 346   const Function *Domain2 = NULL;
 347   if (const Argument *A = dyn_cast<Argument>(V2)) {
 348     Domain2 = A->getParent();
 349   } else if (const BasicBlock *BB = dyn_cast<BasicBlock>(V2)) {
 350     Domain2 = BB->getParent();
 351   } else if (const Instruction *I = dyn_cast<Instruction>(V2)) {
 352     Domain2 = I->getParent()->getParent();
 353   }
 354
 355   if (Domain1 != Domain2)
 356     if (Domain1 != LHS && Domain1 != RHS)
 357       if (Domain2 != LHS && Domain2 != RHS)
 358         return false;
 359
 360   IDMap &Map1 = Domains[Domain1];
 361   unsigned long &ID1 = Map1[V1];
 362   if (!ID1)
 363     ID1 = ++DomainCount[Domain1];
 364
 365   IDMap &Map2 = Domains[Domain2];
 366   unsigned long &ID2 = Map2[V2];
 367   if (!ID2)
 368     ID2 = ++DomainCount[Domain2];
 369
 370   return ID1 == ID2;
 371 }
 372
 373 bool MergeFunctions::equals(const BasicBlock *BB1, const BasicBlock *BB2) {
 374   BasicBlock::const_iterator FI = BB1->begin(), FE = BB1->end();
 375   BasicBlock::const_iterator GI = BB2->begin(), GE = BB2->end();
 376
 377   do {
 378     if (!compare(FI, GI))
 379       return false;
 380
 381     if (isa<GetElementPtrInst>(FI) && isa<GetElementPtrInst>(GI)) {
 382       const GetElementPtrInst *GEP1 = cast<GetElementPtrInst>(FI);
 383       const GetElementPtrInst *GEP2 = cast<GetElementPtrInst>(GI);
 384
 385       if (!compare(GEP1->getPointerOperand(), GEP2->getPointerOperand()))
 386         return false;
 387
 388       if (!isEquivalentGEP(GEP1, GEP2))
 389         return false;
 390     } else {
 391       if (!isEquivalentOperation(FI, GI))
 392         return false;
 393
 394       for (unsigned i = 0, e = FI->getNumOperands(); i != e; ++i) {
 395         Value *OpF = FI->getOperand(i);
 396         Value *OpG = GI->getOperand(i);
 397
 398         if (!compare(OpF, OpG))
 399           return false;
 400
 401         if (OpF->getValueID() != OpG->getValueID() ||
 402             !isEquivalentType(OpF->getType(), OpG->getType()))
 403           return false;
 404       }
 405     }
 406
 407     ++FI, ++GI;
 408   } while (FI != FE && GI != GE);
 409
 410   return FI == FE && GI == GE;
 411 }
 412
 413 bool MergeFunctions::equals(const Function *F, const Function *G) {
 414   // We need to recheck everything, but check the things that weren't included
 415   // in the hash first.
 416
 417   if (F->getAttributes() != G->getAttributes())
 418     return false;
 419
 420   if (F->hasGC() != G->hasGC())
 421     return false;
 422
 423   if (F->hasGC() && F->getGC() != G->getGC())
 424     return false;
 425
 426   if (F->hasSection() != G->hasSection())
 427     return false;
 428
 429   if (F->hasSection() && F->getSection() != G->getSection())
 430     return false;
 431
 432   if (F->isVarArg() != G->isVarArg())
 433     return false;
 434
 435   // TODO: if it's internal and only used in direct calls, we could handle this
 436   // case too.
 437   if (F->getCallingConv() != G->getCallingConv())
 438     return false;
 439
 440   if (!isEquivalentType(F->getFunctionType(), G->getFunctionType()))
 441     return false;
 442
 443   assert(F->arg_size() == G->arg_size() &&
 444          "Identical functions have a different number of args.");
 445
 446   LHS = F;
 447   RHS = G;
 448
 449   // Visit the arguments so that they get enumerated in the order they're
 450   // passed in.
 451   for (Function::const_arg_iterator fi = F->arg_begin(), gi = G->arg_begin(),
 452          fe = F->arg_end(); fi != fe; ++fi, ++gi) {
 453     if (!compare(fi, gi))
 454       llvm_unreachable("Arguments repeat");
 455   }
 456
 457   SmallVector<const BasicBlock *, 8> FBBs, GBBs;
 458   SmallSet<const BasicBlock *, 128> VisitedBBs; // in terms of F.
 459   FBBs.push_back(&F->getEntryBlock());
 460   GBBs.push_back(&G->getEntryBlock());
 461   VisitedBBs.insert(FBBs[0]);
 462   while (!FBBs.empty()) {
 463     const BasicBlock *FBB = FBBs.pop_back_val();
 464     const BasicBlock *GBB = GBBs.pop_back_val();
 465     if (!compare(FBB, GBB) || !equals(FBB, GBB)) {
 466       Domains.clear();
 467       DomainCount.clear();
 468       return false;
 469     }
 470     const TerminatorInst *FTI = FBB->getTerminator();
 471     const TerminatorInst *GTI = GBB->getTerminator();
 472     assert(FTI->getNumSuccessors() == GTI->getNumSuccessors());
 473     for (unsigned i = 0, e = FTI->getNumSuccessors(); i != e; ++i) {
 474       if (!VisitedBBs.insert(FTI->getSuccessor(i)))
 475         continue;
 476       FBBs.push_back(FTI->getSuccessor(i));
 477       GBBs.push_back(GTI->getSuccessor(i));
 478     }
 479   }
 480
 481   Domains.clear();
 482   DomainCount.clear();
 483   return true;
 484 }
 485
 486 // ===----------------------------------------------------------------------===
 487 // Folding of functions
 488 // ===----------------------------------------------------------------------===
 489
 490 // Cases:
 491 // * F is external strong, G is external strong:
 492 //   turn G into a thunk to F    (1)
 493 // * F is external strong, G is external weak:
 494 //   turn G into a thunk to F    (1)
 495 // * F is external weak, G is external weak:
 496 //   unfoldable
 497 // * F is external strong, G is internal:
 498 //   address of G taken:
 499 //     turn G into a thunk to F  (1)
 500 //   address of G not taken:
 501 //     make G an alias to F      (2)
 502 // * F is internal, G is external weak
 503 //   address of F is taken:
 504 //     turn G into a thunk to F  (1)
 505 //   address of F is not taken:
 506 //     make G an alias of F      (2)
 507 // * F is internal, G is internal:
 508 //   address of F and G are taken:
 509 //     turn G into a thunk to F  (1)
 510 //   address of G is not taken:
 511 //     make G an alias to F      (2)
 512 //
 513 // alias requires linkage == (external,local,weak) fallback to creating a thunk
 514 // external means 'externally visible' linkage != (internal,private)
 515 // internal means linkage == (internal,private)
 516 // weak means linkage mayBeOverridable
 517 // being external implies that the address is taken
 518 //
 519 // 1. turn G into a thunk to F
 520 // 2. make G an alias to F
 521
 522 enum LinkageCategory {
 523   ExternalStrong,
 524   ExternalWeak,
 525   Internal
 526 };
 527
 528 static LinkageCategory categorize(const Function *F) {
 529   switch (F->getLinkage()) {
 530   case GlobalValue::InternalLinkage:
 531   case GlobalValue::PrivateLinkage:
 532   case GlobalValue::LinkerPrivateLinkage:
 533     return Internal;
 534
 535   case GlobalValue::WeakAnyLinkage:
 536   case GlobalValue::WeakODRLinkage:
 537   case GlobalValue::ExternalWeakLinkage:
 538   case GlobalValue::LinkerPrivateWeakLinkage:
 539     return ExternalWeak;
 540
 541   case GlobalValue::ExternalLinkage:
 542   case GlobalValue::AvailableExternallyLinkage:
 543   case GlobalValue::LinkOnceAnyLinkage:
 544   case GlobalValue::LinkOnceODRLinkage:
 545   case GlobalValue::AppendingLinkage:
 546   case GlobalValue::DLLImportLinkage:
 547   case GlobalValue::DLLExportLinkage:
 548   case GlobalValue::CommonLinkage:
 549     return ExternalStrong;
 550   }
 551
 552   llvm_unreachable("Unknown LinkageType.");
 553   return ExternalWeak;
 554 }
 555
 556 static void ThunkGToF(Function *F, Function *G) {
 557   if (!G->mayBeOverridden()) {
 558     // Redirect direct callers of G to F.
 559     Constant *BitcastF = ConstantExpr::getBitCast(F, G->getType());
 560     for (Value::use_iterator UI = G->use_begin(), UE = G->use_end();
 561          UI != UE;) {
 562       Value::use_iterator TheIter = UI;
 563       ++UI;
 564       CallSite CS(*TheIter);
 565       if (CS && CS.isCallee(TheIter))
 566         TheIter.getUse().set(BitcastF);
 567     }
 568   }
 569
 570   Function *NewG = Function::Create(G->getFunctionType(), G->getLinkage(), "",
 571                                     G->getParent());
 572   BasicBlock *BB = BasicBlock::Create(F->getContext(), "", NewG);
 573
 574   SmallVector<Value *, 16> Args;
 575   unsigned i = 0;
 576   const FunctionType *FFTy = F->getFunctionType();
 577   for (Function::arg_iterator AI = NewG->arg_begin(), AE = NewG->arg_end();
 578        AI != AE; ++AI) {
 579     if (FFTy->getParamType(i) == AI->getType()) {
 580       Args.push_back(AI);
 581     } else {
 582       Args.push_back(new BitCastInst(AI, FFTy->getParamType(i), "", BB));
 583     }
 584     ++i;
 585   }
 586
 587   CallInst *CI = CallInst::Create(F, Args.begin(), Args.end(), "", BB);
 588   CI->setTailCall();
 589   CI->setCallingConv(F->getCallingConv());
 590   if (NewG->getReturnType()->isVoidTy()) {
 591     ReturnInst::Create(F->getContext(), BB);
 592   } else if (CI->getType() != NewG->getReturnType()) {
 593     Value *BCI = new BitCastInst(CI, NewG->getReturnType(), "", BB);
 594     ReturnInst::Create(F->getContext(), BCI, BB);
 595   } else {
 596     ReturnInst::Create(F->getContext(), CI, BB);
 597   }
 598
 599   NewG->copyAttributesFrom(G);
 600   NewG->takeName(G);
 601   G->replaceAllUsesWith(NewG);
 602   G->eraseFromParent();
 603 }
 604
 605 static void AliasGToF(Function *F, Function *G) {
 606   if (!G->hasExternalLinkage() && !G->hasLocalLinkage() && !G->hasWeakLinkage())
 607     return ThunkGToF(F, G);
 608
 609   GlobalAlias *GA = new GlobalAlias(
 610     G->getType(), G->getLinkage(), "",
 611     ConstantExpr::getBitCast(F, G->getType()), G->getParent());
 612   F->setAlignment(std::max(F->getAlignment(), G->getAlignment()));
 613   GA->takeName(G);
 614   GA->setVisibility(G->getVisibility());
 615   G->replaceAllUsesWith(GA);
 616   G->eraseFromParent();
 617 }
 618
 619 static bool fold(std::vector<Function *> &FnVec, unsigned i, unsigned j) {
 620   Function *F = FnVec[i];
 621   Function *G = FnVec[j];
 622
 623   LinkageCategory catF = categorize(F);
 624   LinkageCategory catG = categorize(G);
 625
 626   if (catF == ExternalWeak || (catF == Internal && catG == ExternalStrong)) {
 627     std::swap(FnVec[i], FnVec[j]);
 628     std::swap(F, G);
 629     std::swap(catF, catG);
 630   }
 631
 632   switch (catF) {
 633   case ExternalStrong:
 634     switch (catG) {
 635     case ExternalStrong:
 636     case ExternalWeak:
 637       ThunkGToF(F, G);
 638       break;
 639     case Internal:
 640       if (G->hasAddressTaken())
 641         ThunkGToF(F, G);
 642       else
 643         AliasGToF(F, G);
 644       break;
 645     }
 646     break;
 647
 648   case ExternalWeak: {
 649     assert(catG == ExternalWeak);
 650
 651     // Make them both thunks to the same internal function.
 652     F->setAlignment(std::max(F->getAlignment(), G->getAlignment()));
 653     Function *H = Function::Create(F->getFunctionType(), F->getLinkage(), "",
 654                                    F->getParent());
 655     H->copyAttributesFrom(F);
 656     H->takeName(F);
 657     F->replaceAllUsesWith(H);
 658
 659     ThunkGToF(F, G);
 660     ThunkGToF(F, H);
 661
 662     F->setLinkage(GlobalValue::InternalLinkage);
 663   } break;
 664
 665   case Internal:
 666     switch (catG) {
 667     case ExternalStrong:
 668       llvm_unreachable(0);
 669       // fall-through
 670     case ExternalWeak:
 671       if (F->hasAddressTaken())
 672         ThunkGToF(F, G);
 673       else
 674         AliasGToF(F, G);
 675       break;
 676     case Internal: {
 677       bool addrTakenF = F->hasAddressTaken();
 678       bool addrTakenG = G->hasAddressTaken();
 679       if (!addrTakenF && addrTakenG) {
 680         std::swap(FnVec[i], FnVec[j]);
 681         std::swap(F, G);
 682         std::swap(addrTakenF, addrTakenG);
 683       }
 684
 685       if (addrTakenF && addrTakenG) {
 686         ThunkGToF(F, G);
 687       } else {
 688         assert(!addrTakenG);
 689         AliasGToF(F, G);
 690       }
 691     } break;
 692   } break;
 693   }
 694
 695   ++NumFunctionsMerged;
 696   return true;
 697 }
 698
 699 // ===----------------------------------------------------------------------===
 700 // Pass definition
 701 // ===----------------------------------------------------------------------===
 702
 703 bool MergeFunctions::runOnModule(Module &M) {
 704   bool Changed = false;
 705
 706   std::map<unsigned long, std::vector<Function *> > FnMap;
 707
 708   for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
 709     if (F->isDeclaration())
 710       continue;
 711
 712     FnMap[hash(F)].push_back(F);
 713   }
 714
 715   TD = getAnalysisIfAvailable<TargetData>();
 716
 717   bool LocalChanged;
 718   do {
 719     LocalChanged = false;
 720     DEBUG(dbgs() << "size: " << FnMap.size() << "\n");
 721     for (std::map<unsigned long, std::vector<Function *> >::iterator
 722            I = FnMap.begin(), E = FnMap.end(); I != E; ++I) {
 723       std::vector<Function *> &FnVec = I->second;
 724       DEBUG(dbgs() << "hash (" << I->first << "): " << FnVec.size() << "\n");
 725
 726       for (int i = 0, e = FnVec.size(); i != e; ++i) {
 727         for (int j = i + 1; j != e; ++j) {
 728           bool isEqual = equals(FnVec[i], FnVec[j]);
 729
 730           DEBUG(dbgs() << "  " << FnVec[i]->getName()
 731                 << (isEqual ? " == " : " != ")
 732                 << FnVec[j]->getName() << "\n");
 733
 734           if (isEqual) {
 735             if (fold(FnVec, i, j)) {
 736               LocalChanged = true;
 737               FnVec.erase(FnVec.begin() + j);
 738               --j, --e;
 739             }
 740           }
 741         }
 742       }
 743
 744     }
 745     Changed |= LocalChanged;
 746   } while (LocalChanged);
 747
 748   return Changed;
 749 }