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/SmallSet.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     DEBUG(doSanityCheck(Worklist));
 411
 412     DEBUG(dbgs() << "size of module: " << M.size() << '\n');
 413     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     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   DEBUG(dbgs() << " Erasing instructions (in reverse order of appearance in "
 502                   "entry block) unrelated to parameter debug info from entry "
 503                   "block: {\n");
 504   while (!PDIUnrelatedWL.empty()) {
 505     Instruction *I = PDIUnrelatedWL.back();
 506     DEBUG(dbgs() << "  Deleting Instruction: ");
 507     DEBUG(I->print(dbgs()));
 508     DEBUG(dbgs() << "\n");
 509     I->eraseFromParent();
 510     PDIUnrelatedWL.pop_back();
 511   }
 512   DEBUG(dbgs() << " } // Done erasing instructions unrelated to parameter "
 513                   "debug info from entry block. \n");
 514 }
 515
 516 // Reduce G to its entry block.
 517 void MergeFunctions::eraseTail(Function *G) {
 518   std::vector<BasicBlock *> WorklistBB;
 519   for (Function::iterator BBI = std::next(G->begin()), BBE = G->end();
 520        BBI != BBE; ++BBI) {
 521     BBI->dropAllReferences();
 522     WorklistBB.push_back(&*BBI);
 523   }
 524   while (!WorklistBB.empty()) {
 525     BasicBlock *BB = WorklistBB.back();
 526     BB->eraseFromParent();
 527     WorklistBB.pop_back();
 528   }
 529 }
 530
 531 // We are interested in the following instructions from the entry block as being
 532 // related to parameter debug info:
 533 // - @llvm.dbg.declare
 534 // - stores from the incoming parameters to locations on the stack-frame
 535 // - allocas that create these locations on the stack-frame
 536 // - @llvm.dbg.value
 537 // - the entry block's terminator
 538 // The rest are unrelated to debug info for the parameters; fill up
 539 // PDIUnrelatedWL with such instructions.
 540 void MergeFunctions::filterInstsUnrelatedToPDI(
 541     BasicBlock *GEntryBlock, std::vector<Instruction *> &PDIUnrelatedWL) {
 542   std::set<Instruction *> PDIRelated;
 543   for (BasicBlock::iterator BI = GEntryBlock->begin(), BIE = GEntryBlock->end();
 544        BI != BIE; ++BI) {
 545     if (auto *DVI = dyn_cast<DbgValueInst>(&*BI)) {
 546       DEBUG(dbgs() << " Deciding: ");
 547       DEBUG(BI->print(dbgs()));
 548       DEBUG(dbgs() << "\n");
 549       DILocalVariable *DILocVar = DVI->getVariable();
 550       if (DILocVar->isParameter()) {
 551         DEBUG(dbgs() << "  Include (parameter): ");
 552         DEBUG(BI->print(dbgs()));
 553         DEBUG(dbgs() << "\n");
 554         PDIRelated.insert(&*BI);
 555       } else {
 556         DEBUG(dbgs() << "  Delete (!parameter): ");
 557         DEBUG(BI->print(dbgs()));
 558         DEBUG(dbgs() << "\n");
 559       }
 560     } else if (auto *DDI = dyn_cast<DbgDeclareInst>(&*BI)) {
 561       DEBUG(dbgs() << " Deciding: ");
 562       DEBUG(BI->print(dbgs()));
 563       DEBUG(dbgs() << "\n");
 564       DILocalVariable *DILocVar = DDI->getVariable();
 565       if (DILocVar->isParameter()) {
 566         DEBUG(dbgs() << "  Parameter: ");
 567         DEBUG(DILocVar->print(dbgs()));
 568         AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress());
 569         if (AI) {
 570           DEBUG(dbgs() << "  Processing alloca users: ");
 571           DEBUG(dbgs() << "\n");
 572           for (User *U : AI->users()) {
 573             if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
 574               if (Value *Arg = SI->getValueOperand()) {
 575                 if (dyn_cast<Argument>(Arg)) {
 576                   DEBUG(dbgs() << "  Include: ");
 577                   DEBUG(AI->print(dbgs()));
 578                   DEBUG(dbgs() << "\n");
 579                   PDIRelated.insert(AI);
 580                   DEBUG(dbgs() << "   Include (parameter): ");
 581                   DEBUG(SI->print(dbgs()));
 582                   DEBUG(dbgs() << "\n");
 583                   PDIRelated.insert(SI);
 584                   DEBUG(dbgs() << "  Include: ");
 585                   DEBUG(BI->print(dbgs()));
 586                   DEBUG(dbgs() << "\n");
 587                   PDIRelated.insert(&*BI);
 588                 } else {
 589                   DEBUG(dbgs() << "   Delete (!parameter): ");
 590                   DEBUG(SI->print(dbgs()));
 591                   DEBUG(dbgs() << "\n");
 592                 }
 593               }
 594             } else {
 595               DEBUG(dbgs() << "   Defer: ");
 596               DEBUG(U->print(dbgs()));
 597               DEBUG(dbgs() << "\n");
 598             }
 599           }
 600         } else {
 601           DEBUG(dbgs() << "  Delete (alloca NULL): ");
 602           DEBUG(BI->print(dbgs()));
 603           DEBUG(dbgs() << "\n");
 604         }
 605       } else {
 606         DEBUG(dbgs() << "  Delete (!parameter): ");
 607         DEBUG(BI->print(dbgs()));
 608         DEBUG(dbgs() << "\n");
 609       }
 610     } else if (dyn_cast<TerminatorInst>(BI) == GEntryBlock->getTerminator()) {
 611       DEBUG(dbgs() << " Will Include Terminator: ");
 612       DEBUG(BI->print(dbgs()));
 613       DEBUG(dbgs() << "\n");
 614       PDIRelated.insert(&*BI);
 615     } else {
 616       DEBUG(dbgs() << " Defer: ");
 617       DEBUG(BI->print(dbgs()));
 618       DEBUG(dbgs() << "\n");
 619     }
 620   }
 621   DEBUG(dbgs()
 622         << " Report parameter debug info related/related instructions: {\n");
 623   for (BasicBlock::iterator BI = GEntryBlock->begin(), BE = GEntryBlock->end();
 624        BI != BE; ++BI) {
 625
 626     Instruction *I = &*BI;
 627     if (PDIRelated.find(I) == PDIRelated.end()) {
 628       DEBUG(dbgs() << "  !PDIRelated: ");
 629       DEBUG(I->print(dbgs()));
 630       DEBUG(dbgs() << "\n");
 631       PDIUnrelatedWL.push_back(I);
 632     } else {
 633       DEBUG(dbgs() << "   PDIRelated: ");
 634       DEBUG(I->print(dbgs()));
 635       DEBUG(dbgs() << "\n");
 636     }
 637   }
 638   DEBUG(dbgs() << " }\n");
 639 }
 640
 641 // Replace G with a simple tail call to bitcast(F). Also (unless
 642 // MergeFunctionsPDI holds) replace direct uses of G with bitcast(F),
 643 // delete G. Under MergeFunctionsPDI, we use G itself for creating
 644 // the thunk as we preserve the debug info (and associated instructions)
 645 // from G's entry block pertaining to G's incoming arguments which are
 646 // passed on as corresponding arguments in the call that G makes to F.
 647 // For better debugability, under MergeFunctionsPDI, we do not modify G's
 648 // call sites to point to F even when within the same translation unit.
 649 void MergeFunctions::writeThunk(Function *F, Function *G) {
 650   if (!G->isInterposable() && !MergeFunctionsPDI) {
 651     if (G->hasGlobalUnnamedAddr()) {
 652       // G might have been a key in our GlobalNumberState, and it's illegal
 653       // to replace a key in ValueMap<GlobalValue *> with a non-global.
 654       GlobalNumbers.erase(G);
 655       // If G's address is not significant, replace it entirely.
 656       Constant *BitcastF = ConstantExpr::getBitCast(F, G->getType());
 657       G->replaceAllUsesWith(BitcastF);
 658     } else {
 659       // Redirect direct callers of G to F. (See note on MergeFunctionsPDI
 660       // above).
 661       replaceDirectCallers(G, F);
 662     }
 663   }
 664
 665   // If G was internal then we may have replaced all uses of G with F. If so,
 666   // stop here and delete G. There's no need for a thunk. (See note on
 667   // MergeFunctionsPDI above).
 668   if (G->hasLocalLinkage() && G->use_empty() && !MergeFunctionsPDI) {
 669     G->eraseFromParent();
 670     return;
 671   }
 672
 673   // Don't merge tiny functions using a thunk, since it can just end up
 674   // making the function larger.
 675   if (F->size() == 1) {
 676     if (F->front().size() <= 2) {
 677       DEBUG(dbgs() << "writeThunk: " << F->getName()
 678                    << " is too small to bother creating a thunk for\n");
 679       return;
 680     }
 681   }
 682
 683   BasicBlock *GEntryBlock = nullptr;
 684   std::vector<Instruction *> PDIUnrelatedWL;
 685   BasicBlock *BB = nullptr;
 686   Function *NewG = nullptr;
 687   if (MergeFunctionsPDI) {
 688     DEBUG(dbgs() << "writeThunk: (MergeFunctionsPDI) Do not create a new "
 689                     "function as thunk; retain original: "
 690                  << G->getName() << "()\n");
 691     GEntryBlock = &G->getEntryBlock();
 692     DEBUG(dbgs() << "writeThunk: (MergeFunctionsPDI) filter parameter related "
 693                     "debug info for "
 694                  << G->getName() << "() {\n");
 695     filterInstsUnrelatedToPDI(GEntryBlock, PDIUnrelatedWL);
 696     GEntryBlock->getTerminator()->eraseFromParent();
 697     BB = GEntryBlock;
 698   } else {
 699     NewG = Function::Create(G->getFunctionType(), G->getLinkage(), "",
 700                             G->getParent());
 701     BB = BasicBlock::Create(F->getContext(), "", NewG);
 702   }
 703
 704   IRBuilder<> Builder(BB);
 705   Function *H = MergeFunctionsPDI ? G : NewG;
 706   SmallVector<Value *, 16> Args;
 707   unsigned i = 0;
 708   FunctionType *FFTy = F->getFunctionType();
 709   for (Argument &AI : H->args()) {
 710     Args.push_back(createCast(Builder, &AI, FFTy->getParamType(i)));
 711     ++i;
 712   }
 713
 714   CallInst *CI = Builder.CreateCall(F, Args);
 715   ReturnInst *RI = nullptr;
 716   CI->setTailCall();
 717   CI->setCallingConv(F->getCallingConv());
 718   CI->setAttributes(F->getAttributes());
 719   if (H->getReturnType()->isVoidTy()) {
 720     RI = Builder.CreateRetVoid();
 721   } else {
 722     RI = Builder.CreateRet(createCast(Builder, CI, H->getReturnType()));
 723   }
 724
 725   if (MergeFunctionsPDI) {
 726     DISubprogram *DIS = G->getSubprogram();
 727     if (DIS) {
 728       DebugLoc CIDbgLoc = DebugLoc::get(DIS->getScopeLine(), 0, DIS);
 729       DebugLoc RIDbgLoc = DebugLoc::get(DIS->getScopeLine(), 0, DIS);
 730       CI->setDebugLoc(CIDbgLoc);
 731       RI->setDebugLoc(RIDbgLoc);
 732     } else {
 733       DEBUG(dbgs() << "writeThunk: (MergeFunctionsPDI) No DISubprogram for "
 734                    << G->getName() << "()\n");
 735     }
 736     eraseTail(G);
 737     eraseInstsUnrelatedToPDI(PDIUnrelatedWL);
 738     DEBUG(dbgs() << "} // End of parameter related debug info filtering for: "
 739                  << G->getName() << "()\n");
 740   } else {
 741     NewG->copyAttributesFrom(G);
 742     NewG->takeName(G);
 743     removeUsers(G);
 744     G->replaceAllUsesWith(NewG);
 745     G->eraseFromParent();
 746   }
 747
 748   DEBUG(dbgs() << "writeThunk: " << H->getName() << '\n');
 749   ++NumThunksWritten;
 750 }
 751
 752 // Merge two equivalent functions. Upon completion, Function G is deleted.
 753 void MergeFunctions::mergeTwoFunctions(Function *F, Function *G) {
 754   if (F->isInterposable()) {
 755     assert(G->isInterposable());
 756
 757     // Make them both thunks to the same internal function.
 758     Function *H = Function::Create(F->getFunctionType(), F->getLinkage(), "",
 759                                    F->getParent());
 760     H->copyAttributesFrom(F);
 761     H->takeName(F);
 762     removeUsers(F);
 763     F->replaceAllUsesWith(H);
 764
 765     unsigned MaxAlignment = std::max(G->getAlignment(), H->getAlignment());
 766
 767     writeThunk(F, G);
 768     writeThunk(F, H);
 769
 770     F->setAlignment(MaxAlignment);
 771     F->setLinkage(GlobalValue::PrivateLinkage);
 772     ++NumDoubleWeak;
 773   } else {
 774     writeThunk(F, G);
 775   }
 776
 777   ++NumFunctionsMerged;
 778 }
 779
 780 /// Replace function F by function G.
 781 void MergeFunctions::replaceFunctionInTree(const FunctionNode &FN,
 782                                            Function *G) {
 783   Function *F = FN.getFunc();
 784   assert(FunctionComparator(F, G, &GlobalNumbers).compare() == 0 &&
 785          "The two functions must be equal");
 786
 787   auto I = FNodesInTree.find(F);
 788   assert(I != FNodesInTree.end() && "F should be in FNodesInTree");
 789   assert(FNodesInTree.count(G) == 0 && "FNodesInTree should not contain G");
 790
 791   FnTreeType::iterator IterToFNInFnTree = I->second;
 792   assert(&(*IterToFNInFnTree) == &FN && "F should map to FN in FNodesInTree.");
 793   // Remove F -> FN and insert G -> FN
 794   FNodesInTree.erase(I);
 795   FNodesInTree.insert({G, IterToFNInFnTree});
 796   // Replace F with G in FN, which is stored inside the FnTree.
 797   FN.replaceBy(G);
 798 }
 799
 800 // Insert a ComparableFunction into the FnTree, or merge it away if equal to one
 801 // that was already inserted.
 802 bool MergeFunctions::insert(Function *NewFunction) {
 803   std::pair<FnTreeType::iterator, bool> Result =
 804       FnTree.insert(FunctionNode(NewFunction));
 805
 806   if (Result.second) {
 807     assert(FNodesInTree.count(NewFunction) == 0);
 808     FNodesInTree.insert({NewFunction, Result.first});
 809     DEBUG(dbgs() << "Inserting as unique: " << NewFunction->getName() << '\n');
 810     return false;
 811   }
 812
 813   const FunctionNode &OldF = *Result.first;
 814
 815   // Impose a total order (by name) on the replacement of functions. This is
 816   // important when operating on more than one module independently to prevent
 817   // cycles of thunks calling each other when the modules are linked together.
 818   //
 819   // First of all, we process strong functions before weak functions.
 820   if ((OldF.getFunc()->isInterposable() && !NewFunction->isInterposable()) ||
 821      (OldF.getFunc()->isInterposable() == NewFunction->isInterposable() &&
 822        OldF.getFunc()->getName() > NewFunction->getName())) {
 823     // Swap the two functions.
 824     Function *F = OldF.getFunc();
 825     replaceFunctionInTree(*Result.first, NewFunction);
 826     NewFunction = F;
 827     assert(OldF.getFunc() != F && "Must have swapped the functions.");
 828   }
 829
 830   DEBUG(dbgs() << "  " << OldF.getFunc()->getName()
 831                << " == " << NewFunction->getName() << '\n');
 832
 833   Function *DeleteF = NewFunction;
 834   mergeTwoFunctions(OldF.getFunc(), DeleteF);
 835   return true;
 836 }
 837
 838 // Remove a function from FnTree. If it was already in FnTree, add
 839 // it to Deferred so that we'll look at it in the next round.
 840 void MergeFunctions::remove(Function *F) {
 841   auto I = FNodesInTree.find(F);
 842   if (I != FNodesInTree.end()) {
 843     DEBUG(dbgs() << "Deferred " << F->getName()<< ".\n");
 844     FnTree.erase(I->second);
 845     // I->second has been invalidated, remove it from the FNodesInTree map to
 846     // preserve the invariant.
 847     FNodesInTree.erase(I);
 848     Deferred.emplace_back(F);
 849   }
 850 }
 851
 852 // For each instruction used by the value, remove() the function that contains
 853 // the instruction. This should happen right before a call to RAUW.
 854 void MergeFunctions::removeUsers(Value *V) {
 855   std::vector<Value *> Worklist;
 856   Worklist.push_back(V);
 857   SmallSet<Value*, 8> Visited;
 858   Visited.insert(V);
 859   while (!Worklist.empty()) {
 860     Value *V = Worklist.back();
 861     Worklist.pop_back();
 862
 863     for (User *U : V->users()) {
 864       if (Instruction *I = dyn_cast<Instruction>(U)) {
 865         remove(I->getParent()->getParent());
 866       } else if (isa<GlobalValue>(U)) {
 867         // do nothing
 868       } else if (Constant *C = dyn_cast<Constant>(U)) {
 869         for (User *UU : C->users()) {
 870           if (!Visited.insert(UU).second)
 871             Worklist.push_back(UU);
 872         }
 873       }
 874     }
 875   }
 876 }