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 functions.
  33 //
  34 // * switch from n^2 pair-wise comparisons to an n-way comparison for each
  35 // bucket.
  36 //
  37 // * be smarter about bitcasts.
  38 //
  39 // In order to fold functions, we will sometimes add either bitcast instructions
  40 // or bitcast constant expressions. Unfortunately, this can confound further
  41 // analysis since the two functions differ where one has a bitcast and the
  42 // other doesn't. We should learn to look through bitcasts.
  43 //
  44 //===----------------------------------------------------------------------===//
  45
  46 #define DEBUG_TYPE "mergefunc"
  47 #include "llvm/Transforms/IPO.h"
  48 #include "llvm/ADT/DenseSet.h"
  49 #include "llvm/ADT/FoldingSet.h"
  50 #include "llvm/ADT/SmallSet.h"
  51 #include "llvm/ADT/Statistic.h"
  52 #include "llvm/ADT/STLExtras.h"
  53 #include "llvm/Constants.h"
  54 #include "llvm/InlineAsm.h"
  55 #include "llvm/Instructions.h"
  56 #include "llvm/LLVMContext.h"
  57 #include "llvm/Module.h"
  58 #include "llvm/Pass.h"
  59 #include "llvm/Support/CallSite.h"
  60 #include "llvm/Support/Debug.h"
  61 #include "llvm/Support/ErrorHandling.h"
  62 #include "llvm/Support/IRBuilder.h"
  63 #include "llvm/Support/ValueHandle.h"
  64 #include "llvm/Support/raw_ostream.h"
  65 #include "llvm/Target/TargetData.h"
  66 #include <vector>
  67 using namespace llvm;
  68
  69 STATISTIC(NumFunctionsMerged, "Number of functions merged");
  70
  71 namespace {
  72
  73 static unsigned ProfileFunction(const Function *F) {
  74   const FunctionType *FTy = F->getFunctionType();
  75
  76   FoldingSetNodeID ID;
  77   ID.AddInteger(F->size());
  78   ID.AddInteger(F->getCallingConv());
  79   ID.AddBoolean(F->hasGC());
  80   ID.AddBoolean(FTy->isVarArg());
  81   ID.AddInteger(FTy->getReturnType()->getTypeID());
  82   for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
  83     ID.AddInteger(FTy->getParamType(i)->getTypeID());
  84   return ID.ComputeHash();
  85 }
  86
  87 class ComparableFunction {
  88 public:
  89   static const ComparableFunction EmptyKey;
  90   static const ComparableFunction TombstoneKey;
  91
  92   ComparableFunction(Function *Func, TargetData *TD)
  93     : Func(Func), Hash(ProfileFunction(Func)), TD(TD) {}
  94
  95   Function *getFunc() const { return Func; }
  96   unsigned getHash() const { return Hash; }
  97   TargetData *getTD() const { return TD; }
  98
  99   // Drops AssertingVH reference to the function. Outside of debug mode, this
 100   // does nothing.
 101   void release() {
 102     assert(Func &&
 103            "Attempted to release function twice, or release empty/tombstone!");
 104     Func = NULL;
 105   }
 106
 107 private:
 108   explicit ComparableFunction(unsigned Hash)
 109     : Func(NULL), Hash(Hash), TD(NULL) {}
 110
 111   AssertingVH<Function> Func;
 112   unsigned Hash;
 113   TargetData *TD;
 114 };
 115
 116 const ComparableFunction ComparableFunction::EmptyKey = ComparableFunction(0);
 117 const ComparableFunction ComparableFunction::TombstoneKey =
 118     ComparableFunction(1);
 119
 120 } // anonymous namespace
 121
 122 namespace llvm {
 123   template <>
 124   struct DenseMapInfo<ComparableFunction> {
 125     static ComparableFunction getEmptyKey() {
 126       return ComparableFunction::EmptyKey;
 127     }
 128     static ComparableFunction getTombstoneKey() {
 129       return ComparableFunction::TombstoneKey;
 130     }
 131     static unsigned getHashValue(const ComparableFunction &CF) {
 132       return CF.getHash();
 133     }
 134     static bool isEqual(const ComparableFunction &LHS,
 135                         const ComparableFunction &RHS);
 136   };
 137 }
 138
 139 namespace {
 140
 141 /// MergeFunctions finds functions which will generate identical machine code,
 142 /// by considering all pointer types to be equivalent. Once identified,
 143 /// MergeFunctions will fold them by replacing a call to one to a call to a
 144 /// bitcast of the other.
 145 ///
 146 class MergeFunctions : public ModulePass {
 147 public:
 148   static char ID;
 149   MergeFunctions() : ModulePass(ID) {}
 150
 151   bool runOnModule(Module &M);
 152
 153 private:
 154   typedef DenseSet<ComparableFunction> FnSetType;
 155
 156
 157   /// Insert a ComparableFunction into the FnSet, or merge it away if it's
 158   /// equal to one that's already present.
 159   bool Insert(FnSetType &FnSet, ComparableFunction &NewF);
 160
 161   /// MergeTwoFunctions - Merge two equivalent functions. Upon completion, G
 162   /// may be deleted, or may be converted into a thunk. In either case, it
 163   /// should never be visited again.
 164   void MergeTwoFunctions(Function *F, Function *G) const;
 165
 166   /// WriteThunk - Replace G with a simple tail call to bitcast(F). Also
 167   /// replace direct uses of G with bitcast(F). Deletes G.
 168   void WriteThunk(Function *F, Function *G) const;
 169
 170   TargetData *TD;
 171 };
 172
 173 }  // end anonymous namespace
 174
 175 char MergeFunctions::ID = 0;
 176 INITIALIZE_PASS(MergeFunctions, "mergefunc", "Merge Functions", false, false);
 177
 178 ModulePass *llvm::createMergeFunctionsPass() {
 179   return new MergeFunctions();
 180 }
 181
 182 namespace {
 183 /// FunctionComparator - Compares two functions to determine whether or not
 184 /// they will generate machine code with the same behaviour. TargetData is
 185 /// used if available. The comparator always fails conservatively (erring on the
 186 /// side of claiming that two functions are different).
 187 class FunctionComparator {
 188 public:
 189   FunctionComparator(const TargetData *TD, const Function *F1,
 190                      const Function *F2)
 191     : F1(F1), F2(F2), TD(TD), IDMap1Count(0), IDMap2Count(0) {}
 192
 193   /// Compare - test whether the two functions have equivalent behaviour.
 194   bool Compare();
 195
 196 private:
 197   /// Compare - test whether two basic blocks have equivalent behaviour.
 198   bool Compare(const BasicBlock *BB1, const BasicBlock *BB2);
 199
 200   /// Enumerate - Assign or look up previously assigned numbers for the two
 201   /// values, and return whether the numbers are equal. Numbers are assigned in
 202   /// the order visited.
 203   bool Enumerate(const Value *V1, const Value *V2);
 204
 205   /// isEquivalentOperation - Compare two Instructions for equivalence, similar
 206   /// to Instruction::isSameOperationAs but with modifications to the type
 207   /// comparison.
 208   bool isEquivalentOperation(const Instruction *I1,
 209                              const Instruction *I2) const;
 210
 211   /// isEquivalentGEP - Compare two GEPs for equivalent pointer arithmetic.
 212   bool isEquivalentGEP(const GEPOperator *GEP1, const GEPOperator *GEP2);
 213   bool isEquivalentGEP(const GetElementPtrInst *GEP1,
 214                        const GetElementPtrInst *GEP2) {
 215     return isEquivalentGEP(cast<GEPOperator>(GEP1), cast<GEPOperator>(GEP2));
 216   }
 217
 218   /// isEquivalentType - Compare two Types, treating all pointer types as equal.
 219   bool isEquivalentType(const Type *Ty1, const Type *Ty2) const;
 220
 221   // The two functions undergoing comparison.
 222   const Function *F1, *F2;
 223
 224   const TargetData *TD;
 225
 226   typedef DenseMap<const Value *, unsigned long> IDMap;
 227   IDMap Map1, Map2;
 228   unsigned long IDMap1Count, IDMap2Count;
 229 };
 230 }
 231
 232 /// isEquivalentType - any two pointers in the same address space are
 233 /// equivalent. Otherwise, standard type equivalence rules apply.
 234 bool FunctionComparator::isEquivalentType(const Type *Ty1,
 235                                           const Type *Ty2) const {
 236   if (Ty1 == Ty2)
 237     return true;
 238   if (Ty1->getTypeID() != Ty2->getTypeID())
 239     return false;
 240
 241   switch(Ty1->getTypeID()) {
 242   default:
 243     llvm_unreachable("Unknown type!");
 244     // Fall through in Release mode.
 245   case Type::IntegerTyID:
 246   case Type::OpaqueTyID:
 247     // Ty1 == Ty2 would have returned true earlier.
 248     return false;
 249
 250   case Type::VoidTyID:
 251   case Type::FloatTyID:
 252   case Type::DoubleTyID:
 253   case Type::X86_FP80TyID:
 254   case Type::FP128TyID:
 255   case Type::PPC_FP128TyID:
 256   case Type::LabelTyID:
 257   case Type::MetadataTyID:
 258     return true;
 259
 260   case Type::PointerTyID: {
 261     const PointerType *PTy1 = cast<PointerType>(Ty1);
 262     const PointerType *PTy2 = cast<PointerType>(Ty2);
 263     return PTy1->getAddressSpace() == PTy2->getAddressSpace();
 264   }
 265
 266   case Type::StructTyID: {
 267     const StructType *STy1 = cast<StructType>(Ty1);
 268     const StructType *STy2 = cast<StructType>(Ty2);
 269     if (STy1->getNumElements() != STy2->getNumElements())
 270       return false;
 271
 272     if (STy1->isPacked() != STy2->isPacked())
 273       return false;
 274
 275     for (unsigned i = 0, e = STy1->getNumElements(); i != e; ++i) {
 276       if (!isEquivalentType(STy1->getElementType(i), STy2->getElementType(i)))
 277         return false;
 278     }
 279     return true;
 280   }
 281
 282   case Type::FunctionTyID: {
 283     const FunctionType *FTy1 = cast<FunctionType>(Ty1);
 284     const FunctionType *FTy2 = cast<FunctionType>(Ty2);
 285     if (FTy1->getNumParams() != FTy2->getNumParams() ||
 286         FTy1->isVarArg() != FTy2->isVarArg())
 287       return false;
 288
 289     if (!isEquivalentType(FTy1->getReturnType(), FTy2->getReturnType()))
 290       return false;
 291
 292     for (unsigned i = 0, e = FTy1->getNumParams(); i != e; ++i) {
 293       if (!isEquivalentType(FTy1->getParamType(i), FTy2->getParamType(i)))
 294         return false;
 295     }
 296     return true;
 297   }
 298
 299   case Type::ArrayTyID: {
 300     const ArrayType *ATy1 = cast<ArrayType>(Ty1);
 301     const ArrayType *ATy2 = cast<ArrayType>(Ty2);
 302     return ATy1->getNumElements() == ATy2->getNumElements() &&
 303            isEquivalentType(ATy1->getElementType(), ATy2->getElementType());
 304   }
 305
 306   case Type::VectorTyID: {
 307     const VectorType *VTy1 = cast<VectorType>(Ty1);
 308     const VectorType *VTy2 = cast<VectorType>(Ty2);
 309     return VTy1->getNumElements() == VTy2->getNumElements() &&
 310            isEquivalentType(VTy1->getElementType(), VTy2->getElementType());
 311   }
 312   }
 313 }
 314
 315 /// isEquivalentOperation - determine whether the two operations are the same
 316 /// except that pointer-to-A and pointer-to-B are equivalent. This should be
 317 /// kept in sync with Instruction::isSameOperationAs.
 318 bool FunctionComparator::isEquivalentOperation(const Instruction *I1,
 319                                                const Instruction *I2) const {
 320   if (I1->getOpcode() != I2->getOpcode() ||
 321       I1->getNumOperands() != I2->getNumOperands() ||
 322       !isEquivalentType(I1->getType(), I2->getType()) ||
 323       !I1->hasSameSubclassOptionalData(I2))
 324     return false;
 325
 326   // We have two instructions of identical opcode and #operands.  Check to see
 327   // if all operands are the same type
 328   for (unsigned i = 0, e = I1->getNumOperands(); i != e; ++i)
 329     if (!isEquivalentType(I1->getOperand(i)->getType(),
 330                           I2->getOperand(i)->getType()))
 331       return false;
 332
 333   // Check special state that is a part of some instructions.
 334   if (const LoadInst *LI = dyn_cast<LoadInst>(I1))
 335     return LI->isVolatile() == cast<LoadInst>(I2)->isVolatile() &&
 336            LI->getAlignment() == cast<LoadInst>(I2)->getAlignment();
 337   if (const StoreInst *SI = dyn_cast<StoreInst>(I1))
 338     return SI->isVolatile() == cast<StoreInst>(I2)->isVolatile() &&
 339            SI->getAlignment() == cast<StoreInst>(I2)->getAlignment();
 340   if (const CmpInst *CI = dyn_cast<CmpInst>(I1))
 341     return CI->getPredicate() == cast<CmpInst>(I2)->getPredicate();
 342   if (const CallInst *CI = dyn_cast<CallInst>(I1))
 343     return CI->isTailCall() == cast<CallInst>(I2)->isTailCall() &&
 344            CI->getCallingConv() == cast<CallInst>(I2)->getCallingConv() &&
 345            CI->getAttributes().getRawPointer() ==
 346              cast<CallInst>(I2)->getAttributes().getRawPointer();
 347   if (const InvokeInst *CI = dyn_cast<InvokeInst>(I1))
 348     return CI->getCallingConv() == cast<InvokeInst>(I2)->getCallingConv() &&
 349            CI->getAttributes().getRawPointer() ==
 350              cast<InvokeInst>(I2)->getAttributes().getRawPointer();
 351   if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(I1)) {
 352     if (IVI->getNumIndices() != cast<InsertValueInst>(I2)->getNumIndices())
 353       return false;
 354     for (unsigned i = 0, e = IVI->getNumIndices(); i != e; ++i)
 355       if (IVI->idx_begin()[i] != cast<InsertValueInst>(I2)->idx_begin()[i])
 356         return false;
 357     return true;
 358   }
 359   if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(I1)) {
 360     if (EVI->getNumIndices() != cast<ExtractValueInst>(I2)->getNumIndices())
 361       return false;
 362     for (unsigned i = 0, e = EVI->getNumIndices(); i != e; ++i)
 363       if (EVI->idx_begin()[i] != cast<ExtractValueInst>(I2)->idx_begin()[i])
 364         return false;
 365     return true;
 366   }
 367
 368   return true;
 369 }
 370
 371 /// isEquivalentGEP - determine whether two GEP operations perform the same
 372 /// underlying arithmetic.
 373 bool FunctionComparator::isEquivalentGEP(const GEPOperator *GEP1,
 374                                          const GEPOperator *GEP2) {
 375   // When we have target data, we can reduce the GEP down to the value in bytes
 376   // added to the address.
 377   if (TD && GEP1->hasAllConstantIndices() && GEP2->hasAllConstantIndices()) {
 378     SmallVector<Value *, 8> Indices1(GEP1->idx_begin(), GEP1->idx_end());
 379     SmallVector<Value *, 8> Indices2(GEP2->idx_begin(), GEP2->idx_end());
 380     uint64_t Offset1 = TD->getIndexedOffset(GEP1->getPointerOperandType(),
 381                                             Indices1.data(), Indices1.size());
 382     uint64_t Offset2 = TD->getIndexedOffset(GEP2->getPointerOperandType(),
 383                                             Indices2.data(), Indices2.size());
 384     return Offset1 == Offset2;
 385   }
 386
 387   if (GEP1->getPointerOperand()->getType() !=
 388       GEP2->getPointerOperand()->getType())
 389     return false;
 390
 391   if (GEP1->getNumOperands() != GEP2->getNumOperands())
 392     return false;
 393
 394   for (unsigned i = 0, e = GEP1->getNumOperands(); i != e; ++i) {
 395     if (!Enumerate(GEP1->getOperand(i), GEP2->getOperand(i)))
 396       return false;
 397   }
 398
 399   return true;
 400 }
 401
 402 /// Enumerate - Compare two values used by the two functions under pair-wise
 403 /// comparison. If this is the first time the values are seen, they're added to
 404 /// the mapping so that we will detect mismatches on next use.
 405 bool FunctionComparator::Enumerate(const Value *V1, const Value *V2) {
 406   // Check for function @f1 referring to itself and function @f2 referring to
 407   // itself, or referring to each other, or both referring to either of them.
 408   // They're all equivalent if the two functions are otherwise equivalent.
 409   if (V1 == F1 && V2 == F2)
 410     return true;
 411   if (V1 == F2 && V2 == F1)
 412     return true;
 413
 414   // TODO: constant expressions with GEP or references to F1 or F2.
 415   if (isa<Constant>(V1))
 416     return V1 == V2;
 417
 418   if (isa<InlineAsm>(V1) && isa<InlineAsm>(V2)) {
 419     const InlineAsm *IA1 = cast<InlineAsm>(V1);
 420     const InlineAsm *IA2 = cast<InlineAsm>(V2);
 421     return IA1->getAsmString() == IA2->getAsmString() &&
 422            IA1->getConstraintString() == IA2->getConstraintString();
 423   }
 424
 425   unsigned long &ID1 = Map1[V1];
 426   if (!ID1)
 427     ID1 = ++IDMap1Count;
 428
 429   unsigned long &ID2 = Map2[V2];
 430   if (!ID2)
 431     ID2 = ++IDMap2Count;
 432
 433   return ID1 == ID2;
 434 }
 435
 436 /// Compare - test whether two basic blocks have equivalent behaviour.
 437 bool FunctionComparator::Compare(const BasicBlock *BB1, const BasicBlock *BB2) {
 438   BasicBlock::const_iterator F1I = BB1->begin(), F1E = BB1->end();
 439   BasicBlock::const_iterator F2I = BB2->begin(), F2E = BB2->end();
 440
 441   do {
 442     if (!Enumerate(F1I, F2I))
 443       return false;
 444
 445     if (const GetElementPtrInst *GEP1 = dyn_cast<GetElementPtrInst>(F1I)) {
 446       const GetElementPtrInst *GEP2 = dyn_cast<GetElementPtrInst>(F2I);
 447       if (!GEP2)
 448         return false;
 449
 450       if (!Enumerate(GEP1->getPointerOperand(), GEP2->getPointerOperand()))
 451         return false;
 452
 453       if (!isEquivalentGEP(GEP1, GEP2))
 454         return false;
 455     } else {
 456       if (!isEquivalentOperation(F1I, F2I))
 457         return false;
 458
 459       assert(F1I->getNumOperands() == F2I->getNumOperands());
 460       for (unsigned i = 0, e = F1I->getNumOperands(); i != e; ++i) {
 461         Value *OpF1 = F1I->getOperand(i);
 462         Value *OpF2 = F2I->getOperand(i);
 463
 464         if (!Enumerate(OpF1, OpF2))
 465           return false;
 466
 467         if (OpF1->getValueID() != OpF2->getValueID() ||
 468             !isEquivalentType(OpF1->getType(), OpF2->getType()))
 469           return false;
 470       }
 471     }
 472
 473     ++F1I, ++F2I;
 474   } while (F1I != F1E && F2I != F2E);
 475
 476   return F1I == F1E && F2I == F2E;
 477 }
 478
 479 /// Compare - test whether the two functions have equivalent behaviour.
 480 bool FunctionComparator::Compare() {
 481   // We need to recheck everything, but check the things that weren't included
 482   // in the hash first.
 483
 484   if (F1->getAttributes() != F2->getAttributes())
 485     return false;
 486
 487   if (F1->hasGC() != F2->hasGC())
 488     return false;
 489
 490   if (F1->hasGC() && F1->getGC() != F2->getGC())
 491     return false;
 492
 493   if (F1->hasSection() != F2->hasSection())
 494     return false;
 495
 496   if (F1->hasSection() && F1->getSection() != F2->getSection())
 497     return false;
 498
 499   if (F1->isVarArg() != F2->isVarArg())
 500     return false;
 501
 502   // TODO: if it's internal and only used in direct calls, we could handle this
 503   // case too.
 504   if (F1->getCallingConv() != F2->getCallingConv())
 505     return false;
 506
 507   if (!isEquivalentType(F1->getFunctionType(), F2->getFunctionType()))
 508     return false;
 509
 510   assert(F1->arg_size() == F2->arg_size() &&
 511          "Identical functions have a different number of args.");
 512
 513   // Visit the arguments so that they get enumerated in the order they're
 514   // passed in.
 515   for (Function::const_arg_iterator f1i = F1->arg_begin(),
 516          f2i = F2->arg_begin(), f1e = F1->arg_end(); f1i != f1e; ++f1i, ++f2i) {
 517     if (!Enumerate(f1i, f2i))
 518       llvm_unreachable("Arguments repeat");
 519   }
 520
 521   // We do a CFG-ordered walk since the actual ordering of the blocks in the
 522   // linked list is immaterial. Our walk starts at the entry block for both
 523   // functions, then takes each block from each terminator in order. As an
 524   // artifact, this also means that unreachable blocks are ignored.
 525   SmallVector<const BasicBlock *, 8> F1BBs, F2BBs;
 526   SmallSet<const BasicBlock *, 128> VisitedBBs; // in terms of F1.
 527
 528   F1BBs.push_back(&F1->getEntryBlock());
 529   F2BBs.push_back(&F2->getEntryBlock());
 530
 531   VisitedBBs.insert(F1BBs[0]);
 532   while (!F1BBs.empty()) {
 533     const BasicBlock *F1BB = F1BBs.pop_back_val();
 534     const BasicBlock *F2BB = F2BBs.pop_back_val();
 535
 536     if (!Enumerate(F1BB, F2BB) || !Compare(F1BB, F2BB))
 537       return false;
 538
 539     const TerminatorInst *F1TI = F1BB->getTerminator();
 540     const TerminatorInst *F2TI = F2BB->getTerminator();
 541
 542     assert(F1TI->getNumSuccessors() == F2TI->getNumSuccessors());
 543     for (unsigned i = 0, e = F1TI->getNumSuccessors(); i != e; ++i) {
 544       if (!VisitedBBs.insert(F1TI->getSuccessor(i)))
 545         continue;
 546
 547       F1BBs.push_back(F1TI->getSuccessor(i));
 548       F2BBs.push_back(F2TI->getSuccessor(i));
 549     }
 550   }
 551   return true;
 552 }
 553
 554 /// WriteThunk - Replace G with a simple tail call to bitcast(F). Also replace
 555 /// direct uses of G with bitcast(F). Deletes G.
 556 void MergeFunctions::WriteThunk(Function *F, Function *G) const {
 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   // If G was internal then we may have replaced all uses if G with F. If so,
 571   // stop here and delete G. There's no need for a thunk.
 572   if (G->hasLocalLinkage() && G->use_empty()) {
 573     G->eraseFromParent();
 574     return;
 575   }
 576
 577   Function *NewG = Function::Create(G->getFunctionType(), G->getLinkage(), "",
 578                                     G->getParent());
 579   BasicBlock *BB = BasicBlock::Create(F->getContext(), "", NewG);
 580   IRBuilder<false> Builder(BB);
 581
 582   SmallVector<Value *, 16> Args;
 583   unsigned i = 0;
 584   const FunctionType *FFTy = F->getFunctionType();
 585   for (Function::arg_iterator AI = NewG->arg_begin(), AE = NewG->arg_end();
 586        AI != AE; ++AI) {
 587     Args.push_back(Builder.CreateBitCast(AI, FFTy->getParamType(i)));
 588     ++i;
 589   }
 590
 591   CallInst *CI = Builder.CreateCall(F, Args.begin(), Args.end());
 592   CI->setTailCall();
 593   CI->setCallingConv(F->getCallingConv());
 594   if (NewG->getReturnType()->isVoidTy()) {
 595     Builder.CreateRetVoid();
 596   } else {
 597     Builder.CreateRet(Builder.CreateBitCast(CI, NewG->getReturnType()));
 598   }
 599
 600   NewG->copyAttributesFrom(G);
 601   NewG->takeName(G);
 602   G->replaceAllUsesWith(NewG);
 603   G->eraseFromParent();
 604 }
 605
 606 /// MergeTwoFunctions - Merge two equivalent functions. Upon completion,
 607 /// Function G is deleted.
 608 void MergeFunctions::MergeTwoFunctions(Function *F, Function *G) const {
 609   if (F->isWeakForLinker()) {
 610     assert(G->isWeakForLinker());
 611
 612     // Make them both thunks to the same internal function.
 613     Function *H = Function::Create(F->getFunctionType(), F->getLinkage(), "",
 614                                    F->getParent());
 615     H->copyAttributesFrom(F);
 616     H->takeName(F);
 617     F->replaceAllUsesWith(H);
 618
 619     unsigned MaxAlignment = std::max(G->getAlignment(), H->getAlignment());
 620
 621     WriteThunk(F, G);
 622     WriteThunk(F, H);
 623
 624     F->setAlignment(MaxAlignment);
 625     F->setLinkage(GlobalValue::InternalLinkage);
 626   } else {
 627     WriteThunk(F, G);
 628   }
 629
 630   ++NumFunctionsMerged;
 631 }
 632
 633 // Insert - Insert a ComparableFunction into the FnSet, or merge it away if
 634 // equal to one that's already inserted.
 635 bool MergeFunctions::Insert(FnSetType &FnSet, ComparableFunction &NewF) {
 636   std::pair<FnSetType::iterator, bool> Result = FnSet.insert(NewF);
 637   if (Result.second)
 638     return false;
 639
 640   const ComparableFunction &OldF = *Result.first;
 641
 642   // Never thunk a strong function to a weak function.
 643   assert(!OldF.getFunc()->isWeakForLinker() ||
 644          NewF.getFunc()->isWeakForLinker());
 645
 646   DEBUG(dbgs() << "  " << OldF.getFunc()->getName() << " == "
 647                << NewF.getFunc()->getName() << '\n');
 648
 649   Function *DeleteF = NewF.getFunc();
 650   NewF.release();
 651   MergeTwoFunctions(OldF.getFunc(), DeleteF);
 652   return true;
 653 }
 654
 655 // IsThunk - This method determines whether or not a given Function is a thunk\// like the ones emitted by this pass and therefore not subject to further
 656 // merging.
 657 static bool IsThunk(const Function *F) {
 658   // The safe direction to fail is to return true. In that case, the function
 659   // will be removed from merging analysis. If we failed to including functions
 660   // then we may try to merge unmergable thing (ie., identical weak functions)
 661   // which will push us into an infinite loop.
 662
 663   if (F->size() != 1)
 664     return false;
 665
 666   const BasicBlock *BB = &F->front();
 667   // A thunk is:
 668   //   bitcast-inst*
 669   //   optional-reg tail call @thunkee(args...*)
 670   //   ret void|optional-reg
 671   // where the args are in the same order as the arguments.
 672
 673   // Verify that the sequence of bitcast-inst's are all casts of arguments and
 674   // that there aren't any extras (ie. no repeated casts).
 675   int LastArgNo = -1;
 676   BasicBlock::const_iterator I = BB->begin();
 677   while (const BitCastInst *BCI = dyn_cast<BitCastInst>(I)) {
 678     const Argument *A = dyn_cast<Argument>(BCI->getOperand(0));
 679     if (!A) return false;
 680     if ((int)A->getArgNo() >= LastArgNo) return false;
 681     LastArgNo = A->getArgNo();
 682     ++I;
 683   }
 684
 685   // Verify that the call instruction has the same arguments as this function
 686   // and that they're all either the incoming argument or a cast of the right
 687   // argument.
 688   const CallInst *CI = dyn_cast<CallInst>(I++);
 689   if (!CI || !CI->isTailCall() ||
 690       CI->getNumArgOperands() != F->arg_size()) return false;
 691
 692   for (unsigned i = 0, e = CI->getNumArgOperands(); i != e; ++i) {
 693     const Value *V = CI->getArgOperand(i);
 694     const Argument *A = dyn_cast<Argument>(V);
 695     if (!A) {
 696       const BitCastInst *BCI = dyn_cast<BitCastInst>(V);
 697       if (!BCI) return false;
 698       A = cast<Argument>(BCI->getOperand(0));
 699     }
 700     if (A->getArgNo() != i) return false;
 701   }
 702
 703   // Verify that the terminator is a ret void (if we're void) or a ret of the
 704   // call's return, or a ret of a bitcast of the call's return.
 705   const Value *RetOp = CI;
 706   if (const BitCastInst *BCI = dyn_cast<BitCastInst>(I)) {
 707     ++I;
 708     if (BCI->getOperand(0) != CI) return false;
 709     RetOp = BCI;
 710   }
 711   const ReturnInst *RI = dyn_cast<ReturnInst>(I);
 712   if (!RI) return false;
 713   if (RI->getNumOperands() == 0)
 714     return CI->getType()->isVoidTy();
 715   return RI->getReturnValue() == CI;
 716 }
 717
 718 bool MergeFunctions::runOnModule(Module &M) {
 719   bool Changed = false;
 720   TD = getAnalysisIfAvailable<TargetData>();
 721
 722   bool LocalChanged;
 723   do {
 724     DEBUG(dbgs() << "size: " << M.size() << '\n');
 725     LocalChanged = false;
 726     FnSetType FnSet;
 727
 728     // Insert only strong functions and merge them. Strong function merging
 729     // always deletes one of them.
 730     for (Module::iterator I = M.begin(), E = M.end(); I != E;) {
 731       Function *F = I++;
 732       if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() &&
 733           !F->isWeakForLinker() && !IsThunk(F)) {
 734         ComparableFunction CF = ComparableFunction(F, TD);
 735         LocalChanged |= Insert(FnSet, CF);
 736       }
 737     }
 738
 739     // Insert only weak functions and merge them. By doing these second we
 740     // create thunks to the strong function when possible. When two weak
 741     // functions are identical, we create a new strong function with two weak
 742     // weak thunks to it which are identical but not mergable.
 743     for (Module::iterator I = M.begin(), E = M.end(); I != E;) {
 744       Function *F = I++;
 745       if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() &&
 746           F->isWeakForLinker() && !IsThunk(F)) {
 747         ComparableFunction CF = ComparableFunction(F, TD);
 748         LocalChanged |= Insert(FnSet, CF);
 749       }
 750     }
 751     Changed |= LocalChanged;
 752   } while (LocalChanged);
 753
 754   return Changed;
 755 }
 756
 757 bool DenseMapInfo<ComparableFunction>::isEqual(const ComparableFunction &LHS,
 758                                                const ComparableFunction &RHS) {
 759   if (LHS.getFunc() == RHS.getFunc() &&
 760       LHS.getHash() == RHS.getHash())
 761     return true;
 762   if (!LHS.getFunc() || !RHS.getFunc())
 763     return false;
 764   assert(LHS.getTD() == RHS.getTD() &&
 765          "Comparing functions for different targets");
 766   return FunctionComparator(LHS.getTD(),
 767                             LHS.getFunc(), RHS.getFunc()).Compare();
 768 }