contrib/llvm/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 // Order relation is defined on set of functions. It was made through
  13 // special function comparison procedure that returns
  14 // 0 when functions are equal,
  15 // -1 when Left function is less than right function, and
  16 // 1 for opposite case. We need total-ordering, so we need to maintain
  17 // four properties on the functions set:
  18 // a <= a (reflexivity)
  19 // if a <= b and b <= a then a = b (antisymmetry)
  20 // if a <= b and b <= c then a <= c (transitivity).
  21 // for all a and b: a <= b or b <= a (totality).
  22 //
  23 // Comparison iterates through each instruction in each basic block.
  24 // Functions are kept on binary tree. For each new function F we perform
  25 // lookup in binary tree.
  26 // In practice it works the following way:
  27 // -- We define Function* container class with custom "operator<" (FunctionPtr).
  28 // -- "FunctionPtr" instances are stored in std::set collection, so every
  29 //    std::set::insert operation will give you result in log(N) time.
  30 //
  31 // As an optimization, a hash of the function structure is calculated first, and
  32 // two functions are only compared if they have the same hash. This hash is
  33 // cheap to compute, and has the property that if function F == G according to
  34 // the comparison function, then hash(F) == hash(G). This consistency property
  35 // is critical to ensuring all possible merging opportunities are exploited.
  36 // Collisions in the hash affect the speed of the pass but not the correctness
  37 // or determinism of the resulting transformation.
  38 //
  39 // When a match is found the functions are folded. If both functions are
  40 // overridable, we move the functionality into a new internal function and
  41 // leave two overridable thunks to it.
  42 //
  43 //===----------------------------------------------------------------------===//
  44 //
  45 // Future work:
  46 //
  47 // * virtual functions.
  48 //
  49 // Many functions have their address taken by the virtual function table for
  50 // the object they belong to. However, as long as it's only used for a lookup
  51 // and call, this is irrelevant, and we'd like to fold such functions.
  52 //
  53 // * be smarter about bitcasts.
  54 //
  55 // In order to fold functions, we will sometimes add either bitcast instructions
  56 // or bitcast constant expressions. Unfortunately, this can confound further
  57 // analysis since the two functions differ where one has a bitcast and the
  58 // other doesn't. We should learn to look through bitcasts.
  59 //
  60 // * Compare complex types with pointer types inside.
  61 // * Compare cross-reference cases.
  62 // * Compare complex expressions.
  63 //
  64 // All the three issues above could be described as ability to prove that
  65 // fA == fB == fC == fE == fF == fG in example below:
  66 //
  67 //  void fA() {
  68 //    fB();
  69 //  }
  70 //  void fB() {
  71 //    fA();
  72 //  }
  73 //
  74 //  void fE() {
  75 //    fF();
  76 //  }
  77 //  void fF() {
  78 //    fG();
  79 //  }
  80 //  void fG() {
  81 //    fE();
  82 //  }
  83 //
  84 // Simplest cross-reference case (fA <--> fB) was implemented in previous
  85 // versions of MergeFunctions, though it presented only in two function pairs
  86 // in test-suite (that counts >50k functions)
  87 // Though possibility to detect complex cross-referencing (e.g.: A->B->C->D->A)
  88 // could cover much more cases.
  89 //
  90 //===----------------------------------------------------------------------===//
  91
  92 #include "llvm/ADT/ArrayRef.h"
  93 #include "llvm/ADT/SmallPtrSet.h"
  94 #include "llvm/ADT/SmallVector.h"
  95 #include "llvm/ADT/Statistic.h"
  96 #include "llvm/IR/Argument.h"
  97 #include "llvm/IR/Attributes.h"
  98 #include "llvm/IR/BasicBlock.h"
  99 #include "llvm/IR/CallSite.h"
 100 #include "llvm/IR/Constant.h"
 101 #include "llvm/IR/Constants.h"
 102 #include "llvm/IR/DebugInfoMetadata.h"
 103 #include "llvm/IR/DebugLoc.h"
 104 #include "llvm/IR/DerivedTypes.h"
 105 #include "llvm/IR/Function.h"
 106 #include "llvm/IR/GlobalValue.h"
 107 #include "llvm/IR/IRBuilder.h"
 108 #include "llvm/IR/InstrTypes.h"
 109 #include "llvm/IR/Instruction.h"
 110 #include "llvm/IR/Instructions.h"
 111 #include "llvm/IR/IntrinsicInst.h"
 112 #include "llvm/IR/Module.h"
 113 #include "llvm/IR/Type.h"
 114 #include "llvm/IR/Use.h"
 115 #include "llvm/IR/User.h"
 116 #include "llvm/IR/Value.h"
 117 #include "llvm/IR/ValueHandle.h"
 118 #include "llvm/IR/ValueMap.h"
 119 #include "llvm/Pass.h"
 120 #include "llvm/Support/Casting.h"
 121 #include "llvm/Support/CommandLine.h"
 122 #include "llvm/Support/Debug.h"
 123 #include "llvm/Support/raw_ostream.h"
 124 #include "llvm/Transforms/IPO.h"
 125 #include "llvm/Transforms/Utils/FunctionComparator.h"
 126 #include <algorithm>
 127 #include <cassert>
 128 #include <iterator>
 129 #include <set>
 130 #include <utility>
 131 #include <vector>
 132
 133 using namespace llvm;
 134
 135 #define DEBUG_TYPE "mergefunc"
 136
 137 STATISTIC(NumFunctionsMerged, "Number of functions merged");
 138 STATISTIC(NumThunksWritten, "Number of thunks generated");
 139 STATISTIC(NumDoubleWeak, "Number of new functions created");
 140
 141 static cl::opt<unsigned> NumFunctionsForSanityCheck(
 142     "mergefunc-sanity",
 143     cl::desc("How many functions in module could be used for "
 144              "MergeFunctions pass sanity check. "
 145              "'0' disables this check. Works only with '-debug' key."),
 146     cl::init(0), cl::Hidden);
 147
 148 // Under option -mergefunc-preserve-debug-info we:
 149 // - Do not create a new function for a thunk.
 150 // - Retain the debug info for a thunk's parameters (and associated
 151 //   instructions for the debug info) from the entry block.
 152 //   Note: -debug will display the algorithm at work.
 153 // - Create debug-info for the call (to the shared implementation) made by
 154 //   a thunk and its return value.
 155 // - Erase the rest of the function, retaining the (minimally sized) entry
 156 //   block to create a thunk.
 157 // - Preserve a thunk's call site to point to the thunk even when both occur
 158 //   within the same translation unit, to aid debugability. Note that this
 159 //   behaviour differs from the underlying -mergefunc implementation which
 160 //   modifies the thunk's call site to point to the shared implementation
 161 //   when both occur within the same translation unit.
 162 static cl::opt<bool>
 163     MergeFunctionsPDI("mergefunc-preserve-debug-info", cl::Hidden,
 164                       cl::init(false),
 165                       cl::desc("Preserve debug info in thunk when mergefunc "
 166                                "transformations are made."));
 167
 168 namespace {
 169
 170 class FunctionNode {
 171   mutable AssertingVH<Function> F;
 172   FunctionComparator::FunctionHash Hash;
 173
 174 public:
 175   // Note the hash is recalculated potentially multiple times, but it is cheap.
 176   FunctionNode(Function *F)
 177     : F(F), Hash(FunctionComparator::functionHash(*F))  {}
 178
 179   Function *getFunc() const { return F; }
 180   FunctionComparator::FunctionHash getHash() const { return Hash; }
 181
 182   /// Replace the reference to the function F by the function G, assuming their
 183   /// implementations are equal.
 184   void replaceBy(Function *G) const {
 185     F = G;
 186   }
 187
 188   void release() { F = nullptr; }
 189 };
 190
 191 /// MergeFunctions finds functions which will generate identical machine code,
 192 /// by considering all pointer types to be equivalent. Once identified,
 193 /// MergeFunctions will fold them by replacing a call to one to a call to a
 194 /// bitcast of the other.
 195 class MergeFunctions : public ModulePass {
 196 public:
 197   static char ID;
 198
 199   MergeFunctions()
 200     : ModulePass(ID), FnTree(FunctionNodeCmp(&GlobalNumbers)) {
 201     initializeMergeFunctionsPass(*PassRegistry::getPassRegistry());
 202   }
 203
 204   bool runOnModule(Module &M) override;
 205
 206 private:
 207   // The function comparison operator is provided here so that FunctionNodes do
 208   // not need to become larger with another pointer.
 209   class FunctionNodeCmp {
 210     GlobalNumberState* GlobalNumbers;
 211
 212   public:
 213     FunctionNodeCmp(GlobalNumberState* GN) : GlobalNumbers(GN) {}
 214
 215     bool operator()(const FunctionNode &LHS, const FunctionNode &RHS) const {
 216       // Order first by hashes, then full function comparison.
 217       if (LHS.getHash() != RHS.getHash())
 218         return LHS.getHash() < RHS.getHash();
 219       FunctionComparator FCmp(LHS.getFunc(), RHS.getFunc(), GlobalNumbers);
 220       return FCmp.compare() == -1;
 221     }
 222   };
 223   using FnTreeType = std::set<FunctionNode, FunctionNodeCmp>;
 224
 225   GlobalNumberState GlobalNumbers;
 226
 227   /// A work queue of functions that may have been modified and should be
 228   /// analyzed again.
 229   std::vector<WeakTrackingVH> Deferred;
 230
 231 #ifndef NDEBUG
 232   /// Checks the rules of order relation introduced among functions set.
 233   /// Returns true, if sanity check has been passed, and false if failed.
 234   bool doSanityCheck(std::vector<WeakTrackingVH> &Worklist);
 235 #endif
 236
 237   /// Insert a ComparableFunction into the FnTree, or merge it away if it's
 238   /// equal to one that's already present.
 239   bool insert(Function *NewFunction);
 240
 241   /// Remove a Function from the FnTree and queue it up for a second sweep of
 242   /// analysis.
 243   void remove(Function *F);
 244
 245   /// Find the functions that use this Value and remove them from FnTree and
 246   /// queue the functions.
 247   void removeUsers(Value *V);
 248
 249   /// Replace all direct calls of Old with calls of New. Will bitcast New if
 250   /// necessary to make types match.
 251   void replaceDirectCallers(Function *Old, Function *New);
 252
 253   /// Merge two equivalent functions. Upon completion, G may be deleted, or may
 254   /// be converted into a thunk. In either case, it should never be visited
 255   /// again.
 256   void mergeTwoFunctions(Function *F, Function *G);
 257
 258   /// Fill PDIUnrelatedWL with instructions from the entry block that are
 259   /// unrelated to parameter related debug info.
 260   void filterInstsUnrelatedToPDI(BasicBlock *GEntryBlock,
 261                                  std::vector<Instruction *> &PDIUnrelatedWL);
 262
 263   /// Erase the rest of the CFG (i.e. barring the entry block).
 264   void eraseTail(Function *G);
 265
 266   /// Erase the instructions in PDIUnrelatedWL as they are unrelated to the
 267   /// parameter debug info, from the entry block.
 268   void eraseInstsUnrelatedToPDI(std::vector<Instruction *> &PDIUnrelatedWL);
 269
 270   /// Replace G with a simple tail call to bitcast(F). Also (unless
 271   /// MergeFunctionsPDI holds) replace direct uses of G with bitcast(F),
 272   /// delete G.
 273   void writeThunk(Function *F, Function *G);
 274
 275   /// Replace function F with function G in the function tree.
 276   void replaceFunctionInTree(const FunctionNode &FN, Function *G);
 277
 278   /// The set of all distinct functions. Use the insert() and remove() methods
 279   /// to modify it. The map allows efficient lookup and deferring of Functions.
 280   FnTreeType FnTree;
 281
 282   // Map functions to the iterators of the FunctionNode which contains them
 283   // in the FnTree. This must be updated carefully whenever the FnTree is
 284   // modified, i.e. in insert(), remove(), and replaceFunctionInTree(), to avoid
 285   // dangling iterators into FnTree. The invariant that preserves this is that
 286   // there is exactly one mapping F -> FN for each FunctionNode FN in FnTree.
 287   ValueMap<Function*, FnTreeType::iterator> FNodesInTree;
 288 };
 289
 290 } // end anonymous namespace
 291
 292 char MergeFunctions::ID = 0;
 293
 294 INITIALIZE_PASS(MergeFunctions, "mergefunc", "Merge Functions", false, false)
 295
 296 ModulePass *llvm::createMergeFunctionsPass() {
 297   return new MergeFunctions();
 298 }
 299
 300 #ifndef NDEBUG
 301 bool MergeFunctions::doSanityCheck(std::vector<WeakTrackingVH> &Worklist) {
 302   if (const unsigned Max = NumFunctionsForSanityCheck) {
 303     unsigned TripleNumber = 0;
 304     bool Valid = true;
 305
 306     dbgs() << "MERGEFUNC-SANITY: Started for first " << Max << " functions.\n";
 307
 308     unsigned i = 0;
 309     for (std::vector<WeakTrackingVH>::iterator I = Worklist.begin(),
 310                                                E = Worklist.end();
 311          I != E && i < Max; ++I, ++i) {
 312       unsigned j = i;
 313       for (std::vector<WeakTrackingVH>::iterator J = I; J != E && j < Max;
 314            ++J, ++j) {
 315         Function *F1 = cast<Function>(*I);
 316         Function *F2 = cast<Function>(*J);
 317         int Res1 = FunctionComparator(F1, F2, &GlobalNumbers).compare();
 318         int Res2 = FunctionComparator(F2, F1, &GlobalNumbers).compare();
 319
 320         // If F1 <= F2, then F2 >= F1, otherwise report failure.
 321         if (Res1 != -Res2) {
 322           dbgs() << "MERGEFUNC-SANITY: Non-symmetric; triple: " << TripleNumber
 323                  << "\n";
 324           dbgs() << *F1 << '\n' << *F2 << '\n';
 325           Valid = false;
 326         }
 327
 328         if (Res1 == 0)
 329           continue;
 330
 331         unsigned k = j;
 332         for (std::vector<WeakTrackingVH>::iterator K = J; K != E && k < Max;
 333              ++k, ++K, ++TripleNumber) {
 334           if (K == J)
 335             continue;
 336
 337           Function *F3 = cast<Function>(*K);
 338           int Res3 = FunctionComparator(F1, F3, &GlobalNumbers).compare();
 339           int Res4 = FunctionComparator(F2, F3, &GlobalNumbers).compare();
 340
 341           bool Transitive = true;
 342
 343           if (Res1 != 0 && Res1 == Res4) {
 344             // F1 > F2, F2 > F3 => F1 > F3
 345             Transitive = Res3 == Res1;
 346           } else if (Res3 != 0 && Res3 == -Res4) {
 347             // F1 > F3, F3 > F2 => F1 > F2
 348             Transitive = Res3 == Res1;
 349           } else if (Res4 != 0 && -Res3 == Res4) {
 350             // F2 > F3, F3 > F1 => F2 > F1
 351             Transitive = Res4 == -Res1;
 352           }
 353
 354           if (!Transitive) {
 355             dbgs() << "MERGEFUNC-SANITY: Non-transitive; triple: "
 356                    << TripleNumber << "\n";
 357             dbgs() << "Res1, Res3, Res4: " << Res1 << ", " << Res3 << ", "
 358                    << Res4 << "\n";
 359             dbgs() << *F1 << '\n' << *F2 << '\n' << *F3 << '\n';
 360             Valid = false;
 361           }
 362         }
 363       }
 364     }
 365
 366     dbgs() << "MERGEFUNC-SANITY: " << (Valid ? "Passed." : "Failed.") << "\n";
 367     return Valid;
 368   }
 369   return true;
 370 }
 371 #endif
 372
 373 bool MergeFunctions::runOnModule(Module &M) {
 374   if (skipModule(M))
 375     return false;
 376
 377   bool Changed = false;
 378
 379   // All functions in the module, ordered by hash. Functions with a unique
 380   // hash value are easily eliminated.
 381   std::vector<std::pair<FunctionComparator::FunctionHash, Function *>>
 382     HashedFuncs;
 383   for (Function &Func : M) {
 384     if (!Func.isDeclaration() && !Func.hasAvailableExternallyLinkage()) {
 385       HashedFuncs.push_back({FunctionComparator::functionHash(Func), &Func});
 386     }
 387   }
 388
 389   std::stable_sort(
 390       HashedFuncs.begin(), HashedFuncs.end(),
 391       [](const std::pair<FunctionComparator::FunctionHash, Function *> &a,
 392          const std::pair<FunctionComparator::FunctionHash, Function *> &b) {
 393         return a.first < b.first;
 394       });
 395
 396   auto S = HashedFuncs.begin();
 397   for (auto I = HashedFuncs.begin(), IE = HashedFuncs.end(); I != IE; ++I) {
 398     // If the hash value matches the previous value or the next one, we must
 399     // consider merging it. Otherwise it is dropped and never considered again.
 400     if ((I != S && std::prev(I)->first == I->first) ||
 401         (std::next(I) != IE && std::next(I)->first == I->first) ) {
 402       Deferred.push_back(WeakTrackingVH(I->second));
 403     }
 404   }
 405
 406   do {
 407     std::vector<WeakTrackingVH> Worklist;
 408     Deferred.swap(Worklist);
 409
 410     LLVM_DEBUG(doSanityCheck(Worklist));
 411
 412     LLVM_DEBUG(dbgs() << "size of module: " << M.size() << '\n');
 413     LLVM_DEBUG(dbgs() << "size of worklist: " << Worklist.size() << '\n');
 414
 415     // Insert functions and merge them.
 416     for (WeakTrackingVH &I : Worklist) {
 417       if (!I)
 418         continue;
 419       Function *F = cast<Function>(I);
 420       if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage()) {
 421         Changed |= insert(F);
 422       }
 423     }
 424     LLVM_DEBUG(dbgs() << "size of FnTree: " << FnTree.size() << '\n');
 425   } while (!Deferred.empty());
 426
 427   FnTree.clear();
 428   GlobalNumbers.clear();
 429
 430   return Changed;
 431 }
 432
 433 // Replace direct callers of Old with New.
 434 void MergeFunctions::replaceDirectCallers(Function *Old, Function *New) {
 435   Constant *BitcastNew = ConstantExpr::getBitCast(New, Old->getType());
 436   for (auto UI = Old->use_begin(), UE = Old->use_end(); UI != UE;) {
 437     Use *U = &*UI;
 438     ++UI;
 439     CallSite CS(U->getUser());
 440     if (CS && CS.isCallee(U)) {
 441       // Transfer the called function's attributes to the call site. Due to the
 442       // bitcast we will 'lose' ABI changing attributes because the 'called
 443       // function' is no longer a Function* but the bitcast. Code that looks up
 444       // the attributes from the called function will fail.
 445
 446       // FIXME: This is not actually true, at least not anymore. The callsite
 447       // will always have the same ABI affecting attributes as the callee,
 448       // because otherwise the original input has UB. Note that Old and New
 449       // always have matching ABI, so no attributes need to be changed.
 450       // Transferring other attributes may help other optimizations, but that
 451       // should be done uniformly and not in this ad-hoc way.
 452       auto &Context = New->getContext();
 453       auto NewPAL = New->getAttributes();
 454       SmallVector<AttributeSet, 4> NewArgAttrs;
 455       for (unsigned argIdx = 0; argIdx < CS.arg_size(); argIdx++)
 456         NewArgAttrs.push_back(NewPAL.getParamAttributes(argIdx));
 457       // Don't transfer attributes from the function to the callee. Function
 458       // attributes typically aren't relevant to the calling convention or ABI.
 459       CS.setAttributes(AttributeList::get(Context, /*FnAttrs=*/AttributeSet(),
 460                                           NewPAL.getRetAttributes(),
 461                                           NewArgAttrs));
 462
 463       remove(CS.getInstruction()->getParent()->getParent());
 464       U->set(BitcastNew);
 465     }
 466   }
 467 }
 468
 469 // Helper for writeThunk,
 470 // Selects proper bitcast operation,
 471 // but a bit simpler then CastInst::getCastOpcode.
 472 static Value *createCast(IRBuilder<> &Builder, Value *V, Type *DestTy) {
 473   Type *SrcTy = V->getType();
 474   if (SrcTy->isStructTy()) {
 475     assert(DestTy->isStructTy());
 476     assert(SrcTy->getStructNumElements() == DestTy->getStructNumElements());
 477     Value *Result = UndefValue::get(DestTy);
 478     for (unsigned int I = 0, E = SrcTy->getStructNumElements(); I < E; ++I) {
 479       Value *Element = createCast(
 480           Builder, Builder.CreateExtractValue(V, makeArrayRef(I)),
 481           DestTy->getStructElementType(I));
 482
 483       Result =
 484           Builder.CreateInsertValue(Result, Element, makeArrayRef(I));
 485     }
 486     return Result;
 487   }
 488   assert(!DestTy->isStructTy());
 489   if (SrcTy->isIntegerTy() && DestTy->isPointerTy())
 490     return Builder.CreateIntToPtr(V, DestTy);
 491   else if (SrcTy->isPointerTy() && DestTy->isIntegerTy())
 492     return Builder.CreatePtrToInt(V, DestTy);
 493   else
 494     return Builder.CreateBitCast(V, DestTy);
 495 }
 496
 497 // Erase the instructions in PDIUnrelatedWL as they are unrelated to the
 498 // parameter debug info, from the entry block.
 499 void MergeFunctions::eraseInstsUnrelatedToPDI(
 500     std::vector<Instruction *> &PDIUnrelatedWL) {
 501   LLVM_DEBUG(
 502       dbgs() << " Erasing instructions (in reverse order of appearance in "
 503                 "entry block) unrelated to parameter debug info from entry "
 504                 "block: {\n");
 505   while (!PDIUnrelatedWL.empty()) {
 506     Instruction *I = PDIUnrelatedWL.back();
 507     LLVM_DEBUG(dbgs() << "  Deleting Instruction: ");
 508     LLVM_DEBUG(I->print(dbgs()));
 509     LLVM_DEBUG(dbgs() << "\n");
 510     I->eraseFromParent();
 511     PDIUnrelatedWL.pop_back();
 512   }
 513   LLVM_DEBUG(dbgs() << " } // Done erasing instructions unrelated to parameter "
 514                        "debug info from entry block. \n");
 515 }
 516
 517 // Reduce G to its entry block.
 518 void MergeFunctions::eraseTail(Function *G) {
 519   std::vector<BasicBlock *> WorklistBB;
 520   for (Function::iterator BBI = std::next(G->begin()), BBE = G->end();
 521        BBI != BBE; ++BBI) {
 522     BBI->dropAllReferences();
 523     WorklistBB.push_back(&*BBI);
 524   }
 525   while (!WorklistBB.empty()) {
 526     BasicBlock *BB = WorklistBB.back();
 527     BB->eraseFromParent();
 528     WorklistBB.pop_back();
 529   }
 530 }
 531
 532 // We are interested in the following instructions from the entry block as being
 533 // related to parameter debug info:
 534 // - @llvm.dbg.declare
 535 // - stores from the incoming parameters to locations on the stack-frame
 536 // - allocas that create these locations on the stack-frame
 537 // - @llvm.dbg.value
 538 // - the entry block's terminator
 539 // The rest are unrelated to debug info for the parameters; fill up
 540 // PDIUnrelatedWL with such instructions.
 541 void MergeFunctions::filterInstsUnrelatedToPDI(
 542     BasicBlock *GEntryBlock, std::vector<Instruction *> &PDIUnrelatedWL) {
 543   std::set<Instruction *> PDIRelated;
 544   for (BasicBlock::iterator BI = GEntryBlock->begin(), BIE = GEntryBlock->end();
 545        BI != BIE; ++BI) {
 546     if (auto *DVI = dyn_cast<DbgValueInst>(&*BI)) {
 547       LLVM_DEBUG(dbgs() << " Deciding: ");
 548       LLVM_DEBUG(BI->print(dbgs()));
 549       LLVM_DEBUG(dbgs() << "\n");
 550       DILocalVariable *DILocVar = DVI->getVariable();
 551       if (DILocVar->isParameter()) {
 552         LLVM_DEBUG(dbgs() << "  Include (parameter): ");
 553         LLVM_DEBUG(BI->print(dbgs()));
 554         LLVM_DEBUG(dbgs() << "\n");
 555         PDIRelated.insert(&*BI);
 556       } else {
 557         LLVM_DEBUG(dbgs() << "  Delete (!parameter): ");
 558         LLVM_DEBUG(BI->print(dbgs()));
 559         LLVM_DEBUG(dbgs() << "\n");
 560       }
 561     } else if (auto *DDI = dyn_cast<DbgDeclareInst>(&*BI)) {
 562       LLVM_DEBUG(dbgs() << " Deciding: ");
 563       LLVM_DEBUG(BI->print(dbgs()));
 564       LLVM_DEBUG(dbgs() << "\n");
 565       DILocalVariable *DILocVar = DDI->getVariable();
 566       if (DILocVar->isParameter()) {
 567         LLVM_DEBUG(dbgs() << "  Parameter: ");
 568         LLVM_DEBUG(DILocVar->print(dbgs()));
 569         AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress());
 570         if (AI) {
 571           LLVM_DEBUG(dbgs() << "  Processing alloca users: ");
 572           LLVM_DEBUG(dbgs() << "\n");
 573           for (User *U : AI->users()) {
 574             if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
 575               if (Value *Arg = SI->getValueOperand()) {
 576                 if (dyn_cast<Argument>(Arg)) {
 577                   LLVM_DEBUG(dbgs() << "  Include: ");
 578                   LLVM_DEBUG(AI->print(dbgs()));
 579                   LLVM_DEBUG(dbgs() << "\n");
 580                   PDIRelated.insert(AI);
 581                   LLVM_DEBUG(dbgs() << "   Include (parameter): ");
 582                   LLVM_DEBUG(SI->print(dbgs()));
 583                   LLVM_DEBUG(dbgs() << "\n");
 584                   PDIRelated.insert(SI);
 585                   LLVM_DEBUG(dbgs() << "  Include: ");
 586                   LLVM_DEBUG(BI->print(dbgs()));
 587                   LLVM_DEBUG(dbgs() << "\n");
 588                   PDIRelated.insert(&*BI);
 589                 } else {
 590                   LLVM_DEBUG(dbgs() << "   Delete (!parameter): ");
 591                   LLVM_DEBUG(SI->print(dbgs()));
 592                   LLVM_DEBUG(dbgs() << "\n");
 593                 }
 594               }
 595             } else {
 596               LLVM_DEBUG(dbgs() << "   Defer: ");
 597               LLVM_DEBUG(U->print(dbgs()));
 598               LLVM_DEBUG(dbgs() << "\n");
 599             }
 600           }
 601         } else {
 602           LLVM_DEBUG(dbgs() << "  Delete (alloca NULL): ");
 603           LLVM_DEBUG(BI->print(dbgs()));
 604           LLVM_DEBUG(dbgs() << "\n");
 605         }
 606       } else {
 607         LLVM_DEBUG(dbgs() << "  Delete (!parameter): ");
 608         LLVM_DEBUG(BI->print(dbgs()));
 609         LLVM_DEBUG(dbgs() << "\n");
 610       }
 611     } else if (dyn_cast<TerminatorInst>(BI) == GEntryBlock->getTerminator()) {
 612       LLVM_DEBUG(dbgs() << " Will Include Terminator: ");
 613       LLVM_DEBUG(BI->print(dbgs()));
 614       LLVM_DEBUG(dbgs() << "\n");
 615       PDIRelated.insert(&*BI);
 616     } else {
 617       LLVM_DEBUG(dbgs() << " Defer: ");
 618       LLVM_DEBUG(BI->print(dbgs()));
 619       LLVM_DEBUG(dbgs() << "\n");
 620     }
 621   }
 622   LLVM_DEBUG(
 623       dbgs()
 624       << " Report parameter debug info related/related instructions: {\n");
 625   for (BasicBlock::iterator BI = GEntryBlock->begin(), BE = GEntryBlock->end();
 626        BI != BE; ++BI) {
 627
 628     Instruction *I = &*BI;
 629     if (PDIRelated.find(I) == PDIRelated.end()) {
 630       LLVM_DEBUG(dbgs() << "  !PDIRelated: ");
 631       LLVM_DEBUG(I->print(dbgs()));
 632       LLVM_DEBUG(dbgs() << "\n");
 633       PDIUnrelatedWL.push_back(I);
 634     } else {
 635       LLVM_DEBUG(dbgs() << "   PDIRelated: ");
 636       LLVM_DEBUG(I->print(dbgs()));
 637       LLVM_DEBUG(dbgs() << "\n");
 638     }
 639   }
 640   LLVM_DEBUG(dbgs() << " }\n");
 641 }
 642
 643 // Don't merge tiny functions using a thunk, since it can just end up
 644 // making the function larger.
 645 static bool isThunkProfitable(Function * F) {
 646   if (F->size() == 1) {
 647     if (F->front().size() <= 2) {
 648       LLVM_DEBUG(dbgs() << "isThunkProfitable: " << F->getName()
 649                         << " is too small to bother creating a thunk for\n");
 650       return false;
 651     }
 652   }
 653   return true;
 654 }
 655
 656 // Replace G with a simple tail call to bitcast(F). Also (unless
 657 // MergeFunctionsPDI holds) replace direct uses of G with bitcast(F),
 658 // delete G. Under MergeFunctionsPDI, we use G itself for creating
 659 // the thunk as we preserve the debug info (and associated instructions)
 660 // from G's entry block pertaining to G's incoming arguments which are
 661 // passed on as corresponding arguments in the call that G makes to F.
 662 // For better debugability, under MergeFunctionsPDI, we do not modify G's
 663 // call sites to point to F even when within the same translation unit.
 664 void MergeFunctions::writeThunk(Function *F, Function *G) {
 665   BasicBlock *GEntryBlock = nullptr;
 666   std::vector<Instruction *> PDIUnrelatedWL;
 667   BasicBlock *BB = nullptr;
 668   Function *NewG = nullptr;
 669   if (MergeFunctionsPDI) {
 670     LLVM_DEBUG(dbgs() << "writeThunk: (MergeFunctionsPDI) Do not create a new "
 671                          "function as thunk; retain original: "
 672                       << G->getName() << "()\n");
 673     GEntryBlock = &G->getEntryBlock();
 674     LLVM_DEBUG(
 675         dbgs() << "writeThunk: (MergeFunctionsPDI) filter parameter related "
 676                   "debug info for "
 677                << G->getName() << "() {\n");
 678     filterInstsUnrelatedToPDI(GEntryBlock, PDIUnrelatedWL);
 679     GEntryBlock->getTerminator()->eraseFromParent();
 680     BB = GEntryBlock;
 681   } else {
 682     NewG = Function::Create(G->getFunctionType(), G->getLinkage(), "",
 683                             G->getParent());
 684     BB = BasicBlock::Create(F->getContext(), "", NewG);
 685   }
 686
 687   IRBuilder<> Builder(BB);
 688   Function *H = MergeFunctionsPDI ? G : NewG;
 689   SmallVector<Value *, 16> Args;
 690   unsigned i = 0;
 691   FunctionType *FFTy = F->getFunctionType();
 692   for (Argument &AI : H->args()) {
 693     Args.push_back(createCast(Builder, &AI, FFTy->getParamType(i)));
 694     ++i;
 695   }
 696
 697   CallInst *CI = Builder.CreateCall(F, Args);
 698   ReturnInst *RI = nullptr;
 699   CI->setTailCall();
 700   CI->setCallingConv(F->getCallingConv());
 701   CI->setAttributes(F->getAttributes());
 702   if (H->getReturnType()->isVoidTy()) {
 703     RI = Builder.CreateRetVoid();
 704   } else {
 705     RI = Builder.CreateRet(createCast(Builder, CI, H->getReturnType()));
 706   }
 707
 708   if (MergeFunctionsPDI) {
 709     DISubprogram *DIS = G->getSubprogram();
 710     if (DIS) {
 711       DebugLoc CIDbgLoc = DebugLoc::get(DIS->getScopeLine(), 0, DIS);
 712       DebugLoc RIDbgLoc = DebugLoc::get(DIS->getScopeLine(), 0, DIS);
 713       CI->setDebugLoc(CIDbgLoc);
 714       RI->setDebugLoc(RIDbgLoc);
 715     } else {
 716       LLVM_DEBUG(
 717           dbgs() << "writeThunk: (MergeFunctionsPDI) No DISubprogram for "
 718                  << G->getName() << "()\n");
 719     }
 720     eraseTail(G);
 721     eraseInstsUnrelatedToPDI(PDIUnrelatedWL);
 722     LLVM_DEBUG(
 723         dbgs() << "} // End of parameter related debug info filtering for: "
 724                << G->getName() << "()\n");
 725   } else {
 726     NewG->copyAttributesFrom(G);
 727     NewG->takeName(G);
 728     removeUsers(G);
 729     G->replaceAllUsesWith(NewG);
 730     G->eraseFromParent();
 731   }
 732
 733   LLVM_DEBUG(dbgs() << "writeThunk: " << H->getName() << '\n');
 734   ++NumThunksWritten;
 735 }
 736
 737 // Merge two equivalent functions. Upon completion, Function G is deleted.
 738 void MergeFunctions::mergeTwoFunctions(Function *F, Function *G) {
 739   if (F->isInterposable()) {
 740     assert(G->isInterposable());
 741
 742     if (!isThunkProfitable(F)) {
 743       return;
 744     }
 745
 746     // Make them both thunks to the same internal function.
 747     Function *H = Function::Create(F->getFunctionType(), F->getLinkage(), "",
 748                                    F->getParent());
 749     H->copyAttributesFrom(F);
 750     H->takeName(F);
 751     removeUsers(F);
 752     F->replaceAllUsesWith(H);
 753
 754     unsigned MaxAlignment = std::max(G->getAlignment(), H->getAlignment());
 755
 756     writeThunk(F, G);
 757     writeThunk(F, H);
 758
 759     F->setAlignment(MaxAlignment);
 760     F->setLinkage(GlobalValue::PrivateLinkage);
 761     ++NumDoubleWeak;
 762     ++NumFunctionsMerged;
 763   } else {
 764     // For better debugability, under MergeFunctionsPDI, we do not modify G's
 765     // call sites to point to F even when within the same translation unit.
 766     if (!G->isInterposable() && !MergeFunctionsPDI) {
 767       if (G->hasGlobalUnnamedAddr()) {
 768         // G might have been a key in our GlobalNumberState, and it's illegal
 769         // to replace a key in ValueMap<GlobalValue *> with a non-global.
 770         GlobalNumbers.erase(G);
 771         // If G's address is not significant, replace it entirely.
 772         Constant *BitcastF = ConstantExpr::getBitCast(F, G->getType());
 773         G->replaceAllUsesWith(BitcastF);
 774       } else {
 775         // Redirect direct callers of G to F. (See note on MergeFunctionsPDI
 776         // above).
 777         replaceDirectCallers(G, F);
 778       }
 779     }
 780
 781     // If G was internal then we may have replaced all uses of G with F. If so,
 782     // stop here and delete G. There's no need for a thunk. (See note on
 783     // MergeFunctionsPDI above).
 784     if (G->hasLocalLinkage() && G->use_empty() && !MergeFunctionsPDI) {
 785       G->eraseFromParent();
 786       ++NumFunctionsMerged;
 787       return;
 788     }
 789
 790     if (!isThunkProfitable(F)) {
 791       return;
 792     }
 793
 794     writeThunk(F, G);
 795     ++NumFunctionsMerged;
 796   }
 797 }
 798
 799 /// Replace function F by function G.
 800 void MergeFunctions::replaceFunctionInTree(const FunctionNode &FN,
 801                                            Function *G) {
 802   Function *F = FN.getFunc();
 803   assert(FunctionComparator(F, G, &GlobalNumbers).compare() == 0 &&
 804          "The two functions must be equal");
 805
 806   auto I = FNodesInTree.find(F);
 807   assert(I != FNodesInTree.end() && "F should be in FNodesInTree");
 808   assert(FNodesInTree.count(G) == 0 && "FNodesInTree should not contain G");
 809
 810   FnTreeType::iterator IterToFNInFnTree = I->second;
 811   assert(&(*IterToFNInFnTree) == &FN && "F should map to FN in FNodesInTree.");
 812   // Remove F -> FN and insert G -> FN
 813   FNodesInTree.erase(I);
 814   FNodesInTree.insert({G, IterToFNInFnTree});
 815   // Replace F with G in FN, which is stored inside the FnTree.
 816   FN.replaceBy(G);
 817 }
 818
 819 // Insert a ComparableFunction into the FnTree, or merge it away if equal to one
 820 // that was already inserted.
 821 bool MergeFunctions::insert(Function *NewFunction) {
 822   std::pair<FnTreeType::iterator, bool> Result =
 823       FnTree.insert(FunctionNode(NewFunction));
 824
 825   if (Result.second) {
 826     assert(FNodesInTree.count(NewFunction) == 0);
 827     FNodesInTree.insert({NewFunction, Result.first});
 828     LLVM_DEBUG(dbgs() << "Inserting as unique: " << NewFunction->getName()
 829                       << '\n');
 830     return false;
 831   }
 832
 833   const FunctionNode &OldF = *Result.first;
 834
 835   // Impose a total order (by name) on the replacement of functions. This is
 836   // important when operating on more than one module independently to prevent
 837   // cycles of thunks calling each other when the modules are linked together.
 838   //
 839   // First of all, we process strong functions before weak functions.
 840   if ((OldF.getFunc()->isInterposable() && !NewFunction->isInterposable()) ||
 841      (OldF.getFunc()->isInterposable() == NewFunction->isInterposable() &&
 842        OldF.getFunc()->getName() > NewFunction->getName())) {
 843     // Swap the two functions.
 844     Function *F = OldF.getFunc();
 845     replaceFunctionInTree(*Result.first, NewFunction);
 846     NewFunction = F;
 847     assert(OldF.getFunc() != F && "Must have swapped the functions.");
 848   }
 849
 850   LLVM_DEBUG(dbgs() << "  " << OldF.getFunc()->getName()
 851                     << " == " << NewFunction->getName() << '\n');
 852
 853   Function *DeleteF = NewFunction;
 854   mergeTwoFunctions(OldF.getFunc(), DeleteF);
 855   return true;
 856 }
 857
 858 // Remove a function from FnTree. If it was already in FnTree, add
 859 // it to Deferred so that we'll look at it in the next round.
 860 void MergeFunctions::remove(Function *F) {
 861   auto I = FNodesInTree.find(F);
 862   if (I != FNodesInTree.end()) {
 863     LLVM_DEBUG(dbgs() << "Deferred " << F->getName() << ".\n");
 864     FnTree.erase(I->second);
 865     // I->second has been invalidated, remove it from the FNodesInTree map to
 866     // preserve the invariant.
 867     FNodesInTree.erase(I);
 868     Deferred.emplace_back(F);
 869   }
 870 }
 871
 872 // For each instruction used by the value, remove() the function that contains
 873 // the instruction. This should happen right before a call to RAUW.
 874 void MergeFunctions::removeUsers(Value *V) {
 875   std::vector<Value *> Worklist;
 876   Worklist.push_back(V);
 877   SmallPtrSet<Value*, 8> Visited;
 878   Visited.insert(V);
 879   while (!Worklist.empty()) {
 880     Value *V = Worklist.back();
 881     Worklist.pop_back();
 882
 883     for (User *U : V->users()) {
 884       if (Instruction *I = dyn_cast<Instruction>(U)) {
 885         remove(I->getParent()->getParent());
 886       } else if (isa<GlobalValue>(U)) {
 887         // do nothing
 888       } else if (Constant *C = dyn_cast<Constant>(U)) {
 889         for (User *UU : C->users()) {
 890           if (!Visited.insert(UU).second)
 891             Worklist.push_back(UU);
 892         }
 893       }
 894     }
 895   }
 896 }