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(NumAliasesWritten, "Number of aliases generated");
 140 STATISTIC(NumDoubleWeak, "Number of new functions created");
 141
 142 static cl::opt<unsigned> NumFunctionsForSanityCheck(
 143     "mergefunc-sanity",
 144     cl::desc("How many functions in module could be used for "
 145              "MergeFunctions pass sanity check. "
 146              "'0' disables this check. Works only with '-debug' key."),
 147     cl::init(0), cl::Hidden);
 148
 149 // Under option -mergefunc-preserve-debug-info we:
 150 // - Do not create a new function for a thunk.
 151 // - Retain the debug info for a thunk's parameters (and associated
 152 //   instructions for the debug info) from the entry block.
 153 //   Note: -debug will display the algorithm at work.
 154 // - Create debug-info for the call (to the shared implementation) made by
 155 //   a thunk and its return value.
 156 // - Erase the rest of the function, retaining the (minimally sized) entry
 157 //   block to create a thunk.
 158 // - Preserve a thunk's call site to point to the thunk even when both occur
 159 //   within the same translation unit, to aid debugability. Note that this
 160 //   behaviour differs from the underlying -mergefunc implementation which
 161 //   modifies the thunk's call site to point to the shared implementation
 162 //   when both occur within the same translation unit.
 163 static cl::opt<bool>
 164     MergeFunctionsPDI("mergefunc-preserve-debug-info", cl::Hidden,
 165                       cl::init(false),
 166                       cl::desc("Preserve debug info in thunk when mergefunc "
 167                                "transformations are made."));
 168
 169 static cl::opt<bool>
 170     MergeFunctionsAliases("mergefunc-use-aliases", cl::Hidden,
 171                           cl::init(false),
 172                           cl::desc("Allow mergefunc to create aliases"));
 173
 174 namespace {
 175
 176 class FunctionNode {
 177   mutable AssertingVH<Function> F;
 178   FunctionComparator::FunctionHash Hash;
 179
 180 public:
 181   // Note the hash is recalculated potentially multiple times, but it is cheap.
 182   FunctionNode(Function *F)
 183     : F(F), Hash(FunctionComparator::functionHash(*F))  {}
 184
 185   Function *getFunc() const { return F; }
 186   FunctionComparator::FunctionHash getHash() const { return Hash; }
 187
 188   /// Replace the reference to the function F by the function G, assuming their
 189   /// implementations are equal.
 190   void replaceBy(Function *G) const {
 191     F = G;
 192   }
 193
 194   void release() { F = nullptr; }
 195 };
 196
 197 /// MergeFunctions finds functions which will generate identical machine code,
 198 /// by considering all pointer types to be equivalent. Once identified,
 199 /// MergeFunctions will fold them by replacing a call to one to a call to a
 200 /// bitcast of the other.
 201 class MergeFunctions : public ModulePass {
 202 public:
 203   static char ID;
 204
 205   MergeFunctions()
 206     : ModulePass(ID), FnTree(FunctionNodeCmp(&GlobalNumbers)) {
 207     initializeMergeFunctionsPass(*PassRegistry::getPassRegistry());
 208   }
 209
 210   bool runOnModule(Module &M) override;
 211
 212 private:
 213   // The function comparison operator is provided here so that FunctionNodes do
 214   // not need to become larger with another pointer.
 215   class FunctionNodeCmp {
 216     GlobalNumberState* GlobalNumbers;
 217
 218   public:
 219     FunctionNodeCmp(GlobalNumberState* GN) : GlobalNumbers(GN) {}
 220
 221     bool operator()(const FunctionNode &LHS, const FunctionNode &RHS) const {
 222       // Order first by hashes, then full function comparison.
 223       if (LHS.getHash() != RHS.getHash())
 224         return LHS.getHash() < RHS.getHash();
 225       FunctionComparator FCmp(LHS.getFunc(), RHS.getFunc(), GlobalNumbers);
 226       return FCmp.compare() == -1;
 227     }
 228   };
 229   using FnTreeType = std::set<FunctionNode, FunctionNodeCmp>;
 230
 231   GlobalNumberState GlobalNumbers;
 232
 233   /// A work queue of functions that may have been modified and should be
 234   /// analyzed again.
 235   std::vector<WeakTrackingVH> Deferred;
 236
 237 #ifndef NDEBUG
 238   /// Checks the rules of order relation introduced among functions set.
 239   /// Returns true, if sanity check has been passed, and false if failed.
 240   bool doSanityCheck(std::vector<WeakTrackingVH> &Worklist);
 241 #endif
 242
 243   /// Insert a ComparableFunction into the FnTree, or merge it away if it's
 244   /// equal to one that's already present.
 245   bool insert(Function *NewFunction);
 246
 247   /// Remove a Function from the FnTree and queue it up for a second sweep of
 248   /// analysis.
 249   void remove(Function *F);
 250
 251   /// Find the functions that use this Value and remove them from FnTree and
 252   /// queue the functions.
 253   void removeUsers(Value *V);
 254
 255   /// Replace all direct calls of Old with calls of New. Will bitcast New if
 256   /// necessary to make types match.
 257   void replaceDirectCallers(Function *Old, Function *New);
 258
 259   /// Merge two equivalent functions. Upon completion, G may be deleted, or may
 260   /// be converted into a thunk. In either case, it should never be visited
 261   /// again.
 262   void mergeTwoFunctions(Function *F, Function *G);
 263
 264   /// Fill PDIUnrelatedWL with instructions from the entry block that are
 265   /// unrelated to parameter related debug info.
 266   void filterInstsUnrelatedToPDI(BasicBlock *GEntryBlock,
 267                                  std::vector<Instruction *> &PDIUnrelatedWL);
 268
 269   /// Erase the rest of the CFG (i.e. barring the entry block).
 270   void eraseTail(Function *G);
 271
 272   /// Erase the instructions in PDIUnrelatedWL as they are unrelated to the
 273   /// parameter debug info, from the entry block.
 274   void eraseInstsUnrelatedToPDI(std::vector<Instruction *> &PDIUnrelatedWL);
 275
 276   /// Replace G with a simple tail call to bitcast(F). Also (unless
 277   /// MergeFunctionsPDI holds) replace direct uses of G with bitcast(F),
 278   /// delete G.
 279   void writeThunk(Function *F, Function *G);
 280
 281   // Replace G with an alias to F (deleting function G)
 282   void writeAlias(Function *F, Function *G);
 283
 284   // Replace G with an alias to F if possible, or a thunk to F if
 285   // profitable. Returns false if neither is the case.
 286   bool writeThunkOrAlias(Function *F, Function *G);
 287
 288   /// Replace function F with function G in the function tree.
 289   void replaceFunctionInTree(const FunctionNode &FN, Function *G);
 290
 291   /// The set of all distinct functions. Use the insert() and remove() methods
 292   /// to modify it. The map allows efficient lookup and deferring of Functions.
 293   FnTreeType FnTree;
 294
 295   // Map functions to the iterators of the FunctionNode which contains them
 296   // in the FnTree. This must be updated carefully whenever the FnTree is
 297   // modified, i.e. in insert(), remove(), and replaceFunctionInTree(), to avoid
 298   // dangling iterators into FnTree. The invariant that preserves this is that
 299   // there is exactly one mapping F -> FN for each FunctionNode FN in FnTree.
 300   DenseMap<AssertingVH<Function>, FnTreeType::iterator> FNodesInTree;
 301 };
 302
 303 } // end anonymous namespace
 304
 305 char MergeFunctions::ID = 0;
 306
 307 INITIALIZE_PASS(MergeFunctions, "mergefunc", "Merge Functions", false, false)
 308
 309 ModulePass *llvm::createMergeFunctionsPass() {
 310   return new MergeFunctions();
 311 }
 312
 313 #ifndef NDEBUG
 314 bool MergeFunctions::doSanityCheck(std::vector<WeakTrackingVH> &Worklist) {
 315   if (const unsigned Max = NumFunctionsForSanityCheck) {
 316     unsigned TripleNumber = 0;
 317     bool Valid = true;
 318
 319     dbgs() << "MERGEFUNC-SANITY: Started for first " << Max << " functions.\n";
 320
 321     unsigned i = 0;
 322     for (std::vector<WeakTrackingVH>::iterator I = Worklist.begin(),
 323                                                E = Worklist.end();
 324          I != E && i < Max; ++I, ++i) {
 325       unsigned j = i;
 326       for (std::vector<WeakTrackingVH>::iterator J = I; J != E && j < Max;
 327            ++J, ++j) {
 328         Function *F1 = cast<Function>(*I);
 329         Function *F2 = cast<Function>(*J);
 330         int Res1 = FunctionComparator(F1, F2, &GlobalNumbers).compare();
 331         int Res2 = FunctionComparator(F2, F1, &GlobalNumbers).compare();
 332
 333         // If F1 <= F2, then F2 >= F1, otherwise report failure.
 334         if (Res1 != -Res2) {
 335           dbgs() << "MERGEFUNC-SANITY: Non-symmetric; triple: " << TripleNumber
 336                  << "\n";
 337           dbgs() << *F1 << '\n' << *F2 << '\n';
 338           Valid = false;
 339         }
 340
 341         if (Res1 == 0)
 342           continue;
 343
 344         unsigned k = j;
 345         for (std::vector<WeakTrackingVH>::iterator K = J; K != E && k < Max;
 346              ++k, ++K, ++TripleNumber) {
 347           if (K == J)
 348             continue;
 349
 350           Function *F3 = cast<Function>(*K);
 351           int Res3 = FunctionComparator(F1, F3, &GlobalNumbers).compare();
 352           int Res4 = FunctionComparator(F2, F3, &GlobalNumbers).compare();
 353
 354           bool Transitive = true;
 355
 356           if (Res1 != 0 && Res1 == Res4) {
 357             // F1 > F2, F2 > F3 => F1 > F3
 358             Transitive = Res3 == Res1;
 359           } else if (Res3 != 0 && Res3 == -Res4) {
 360             // F1 > F3, F3 > F2 => F1 > F2
 361             Transitive = Res3 == Res1;
 362           } else if (Res4 != 0 && -Res3 == Res4) {
 363             // F2 > F3, F3 > F1 => F2 > F1
 364             Transitive = Res4 == -Res1;
 365           }
 366
 367           if (!Transitive) {
 368             dbgs() << "MERGEFUNC-SANITY: Non-transitive; triple: "
 369                    << TripleNumber << "\n";
 370             dbgs() << "Res1, Res3, Res4: " << Res1 << ", " << Res3 << ", "
 371                    << Res4 << "\n";
 372             dbgs() << *F1 << '\n' << *F2 << '\n' << *F3 << '\n';
 373             Valid = false;
 374           }
 375         }
 376       }
 377     }
 378
 379     dbgs() << "MERGEFUNC-SANITY: " << (Valid ? "Passed." : "Failed.") << "\n";
 380     return Valid;
 381   }
 382   return true;
 383 }
 384 #endif
 385
 386 bool MergeFunctions::runOnModule(Module &M) {
 387   if (skipModule(M))
 388     return false;
 389
 390   bool Changed = false;
 391
 392   // All functions in the module, ordered by hash. Functions with a unique
 393   // hash value are easily eliminated.
 394   std::vector<std::pair<FunctionComparator::FunctionHash, Function *>>
 395     HashedFuncs;
 396   for (Function &Func : M) {
 397     if (!Func.isDeclaration() && !Func.hasAvailableExternallyLinkage()) {
 398       HashedFuncs.push_back({FunctionComparator::functionHash(Func), &Func});
 399     }
 400   }
 401
 402   std::stable_sort(
 403       HashedFuncs.begin(), HashedFuncs.end(),
 404       [](const std::pair<FunctionComparator::FunctionHash, Function *> &a,
 405          const std::pair<FunctionComparator::FunctionHash, Function *> &b) {
 406         return a.first < b.first;
 407       });
 408
 409   auto S = HashedFuncs.begin();
 410   for (auto I = HashedFuncs.begin(), IE = HashedFuncs.end(); I != IE; ++I) {
 411     // If the hash value matches the previous value or the next one, we must
 412     // consider merging it. Otherwise it is dropped and never considered again.
 413     if ((I != S && std::prev(I)->first == I->first) ||
 414         (std::next(I) != IE && std::next(I)->first == I->first) ) {
 415       Deferred.push_back(WeakTrackingVH(I->second));
 416     }
 417   }
 418
 419   do {
 420     std::vector<WeakTrackingVH> Worklist;
 421     Deferred.swap(Worklist);
 422
 423     LLVM_DEBUG(doSanityCheck(Worklist));
 424
 425     LLVM_DEBUG(dbgs() << "size of module: " << M.size() << '\n');
 426     LLVM_DEBUG(dbgs() << "size of worklist: " << Worklist.size() << '\n');
 427
 428     // Insert functions and merge them.
 429     for (WeakTrackingVH &I : Worklist) {
 430       if (!I)
 431         continue;
 432       Function *F = cast<Function>(I);
 433       if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage()) {
 434         Changed |= insert(F);
 435       }
 436     }
 437     LLVM_DEBUG(dbgs() << "size of FnTree: " << FnTree.size() << '\n');
 438   } while (!Deferred.empty());
 439
 440   FnTree.clear();
 441   FNodesInTree.clear();
 442   GlobalNumbers.clear();
 443
 444   return Changed;
 445 }
 446
 447 // Replace direct callers of Old with New.
 448 void MergeFunctions::replaceDirectCallers(Function *Old, Function *New) {
 449   Constant *BitcastNew = ConstantExpr::getBitCast(New, Old->getType());
 450   for (auto UI = Old->use_begin(), UE = Old->use_end(); UI != UE;) {
 451     Use *U = &*UI;
 452     ++UI;
 453     CallSite CS(U->getUser());
 454     if (CS && CS.isCallee(U)) {
 455       // Transfer the called function's attributes to the call site. Due to the
 456       // bitcast we will 'lose' ABI changing attributes because the 'called
 457       // function' is no longer a Function* but the bitcast. Code that looks up
 458       // the attributes from the called function will fail.
 459
 460       // FIXME: This is not actually true, at least not anymore. The callsite
 461       // will always have the same ABI affecting attributes as the callee,
 462       // because otherwise the original input has UB. Note that Old and New
 463       // always have matching ABI, so no attributes need to be changed.
 464       // Transferring other attributes may help other optimizations, but that
 465       // should be done uniformly and not in this ad-hoc way.
 466       auto &Context = New->getContext();
 467       auto NewPAL = New->getAttributes();
 468       SmallVector<AttributeSet, 4> NewArgAttrs;
 469       for (unsigned argIdx = 0; argIdx < CS.arg_size(); argIdx++)
 470         NewArgAttrs.push_back(NewPAL.getParamAttributes(argIdx));
 471       // Don't transfer attributes from the function to the callee. Function
 472       // attributes typically aren't relevant to the calling convention or ABI.
 473       CS.setAttributes(AttributeList::get(Context, /*FnAttrs=*/AttributeSet(),
 474                                           NewPAL.getRetAttributes(),
 475                                           NewArgAttrs));
 476
 477       remove(CS.getInstruction()->getFunction());
 478       U->set(BitcastNew);
 479     }
 480   }
 481 }
 482
 483 // Helper for writeThunk,
 484 // Selects proper bitcast operation,
 485 // but a bit simpler then CastInst::getCastOpcode.
 486 static Value *createCast(IRBuilder<> &Builder, Value *V, Type *DestTy) {
 487   Type *SrcTy = V->getType();
 488   if (SrcTy->isStructTy()) {
 489     assert(DestTy->isStructTy());
 490     assert(SrcTy->getStructNumElements() == DestTy->getStructNumElements());
 491     Value *Result = UndefValue::get(DestTy);
 492     for (unsigned int I = 0, E = SrcTy->getStructNumElements(); I < E; ++I) {
 493       Value *Element = createCast(
 494           Builder, Builder.CreateExtractValue(V, makeArrayRef(I)),
 495           DestTy->getStructElementType(I));
 496
 497       Result =
 498           Builder.CreateInsertValue(Result, Element, makeArrayRef(I));
 499     }
 500     return Result;
 501   }
 502   assert(!DestTy->isStructTy());
 503   if (SrcTy->isIntegerTy() && DestTy->isPointerTy())
 504     return Builder.CreateIntToPtr(V, DestTy);
 505   else if (SrcTy->isPointerTy() && DestTy->isIntegerTy())
 506     return Builder.CreatePtrToInt(V, DestTy);
 507   else
 508     return Builder.CreateBitCast(V, DestTy);
 509 }
 510
 511 // Erase the instructions in PDIUnrelatedWL as they are unrelated to the
 512 // parameter debug info, from the entry block.
 513 void MergeFunctions::eraseInstsUnrelatedToPDI(
 514     std::vector<Instruction *> &PDIUnrelatedWL) {
 515   LLVM_DEBUG(
 516       dbgs() << " Erasing instructions (in reverse order of appearance in "
 517                 "entry block) unrelated to parameter debug info from entry "
 518                 "block: {\n");
 519   while (!PDIUnrelatedWL.empty()) {
 520     Instruction *I = PDIUnrelatedWL.back();
 521     LLVM_DEBUG(dbgs() << "  Deleting Instruction: ");
 522     LLVM_DEBUG(I->print(dbgs()));
 523     LLVM_DEBUG(dbgs() << "\n");
 524     I->eraseFromParent();
 525     PDIUnrelatedWL.pop_back();
 526   }
 527   LLVM_DEBUG(dbgs() << " } // Done erasing instructions unrelated to parameter "
 528                        "debug info from entry block. \n");
 529 }
 530
 531 // Reduce G to its entry block.
 532 void MergeFunctions::eraseTail(Function *G) {
 533   std::vector<BasicBlock *> WorklistBB;
 534   for (Function::iterator BBI = std::next(G->begin()), BBE = G->end();
 535        BBI != BBE; ++BBI) {
 536     BBI->dropAllReferences();
 537     WorklistBB.push_back(&*BBI);
 538   }
 539   while (!WorklistBB.empty()) {
 540     BasicBlock *BB = WorklistBB.back();
 541     BB->eraseFromParent();
 542     WorklistBB.pop_back();
 543   }
 544 }
 545
 546 // We are interested in the following instructions from the entry block as being
 547 // related to parameter debug info:
 548 // - @llvm.dbg.declare
 549 // - stores from the incoming parameters to locations on the stack-frame
 550 // - allocas that create these locations on the stack-frame
 551 // - @llvm.dbg.value
 552 // - the entry block's terminator
 553 // The rest are unrelated to debug info for the parameters; fill up
 554 // PDIUnrelatedWL with such instructions.
 555 void MergeFunctions::filterInstsUnrelatedToPDI(
 556     BasicBlock *GEntryBlock, std::vector<Instruction *> &PDIUnrelatedWL) {
 557   std::set<Instruction *> PDIRelated;
 558   for (BasicBlock::iterator BI = GEntryBlock->begin(), BIE = GEntryBlock->end();
 559        BI != BIE; ++BI) {
 560     if (auto *DVI = dyn_cast<DbgValueInst>(&*BI)) {
 561       LLVM_DEBUG(dbgs() << " Deciding: ");
 562       LLVM_DEBUG(BI->print(dbgs()));
 563       LLVM_DEBUG(dbgs() << "\n");
 564       DILocalVariable *DILocVar = DVI->getVariable();
 565       if (DILocVar->isParameter()) {
 566         LLVM_DEBUG(dbgs() << "  Include (parameter): ");
 567         LLVM_DEBUG(BI->print(dbgs()));
 568         LLVM_DEBUG(dbgs() << "\n");
 569         PDIRelated.insert(&*BI);
 570       } else {
 571         LLVM_DEBUG(dbgs() << "  Delete (!parameter): ");
 572         LLVM_DEBUG(BI->print(dbgs()));
 573         LLVM_DEBUG(dbgs() << "\n");
 574       }
 575     } else if (auto *DDI = dyn_cast<DbgDeclareInst>(&*BI)) {
 576       LLVM_DEBUG(dbgs() << " Deciding: ");
 577       LLVM_DEBUG(BI->print(dbgs()));
 578       LLVM_DEBUG(dbgs() << "\n");
 579       DILocalVariable *DILocVar = DDI->getVariable();
 580       if (DILocVar->isParameter()) {
 581         LLVM_DEBUG(dbgs() << "  Parameter: ");
 582         LLVM_DEBUG(DILocVar->print(dbgs()));
 583         AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress());
 584         if (AI) {
 585           LLVM_DEBUG(dbgs() << "  Processing alloca users: ");
 586           LLVM_DEBUG(dbgs() << "\n");
 587           for (User *U : AI->users()) {
 588             if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
 589               if (Value *Arg = SI->getValueOperand()) {
 590                 if (dyn_cast<Argument>(Arg)) {
 591                   LLVM_DEBUG(dbgs() << "  Include: ");
 592                   LLVM_DEBUG(AI->print(dbgs()));
 593                   LLVM_DEBUG(dbgs() << "\n");
 594                   PDIRelated.insert(AI);
 595                   LLVM_DEBUG(dbgs() << "   Include (parameter): ");
 596                   LLVM_DEBUG(SI->print(dbgs()));
 597                   LLVM_DEBUG(dbgs() << "\n");
 598                   PDIRelated.insert(SI);
 599                   LLVM_DEBUG(dbgs() << "  Include: ");
 600                   LLVM_DEBUG(BI->print(dbgs()));
 601                   LLVM_DEBUG(dbgs() << "\n");
 602                   PDIRelated.insert(&*BI);
 603                 } else {
 604                   LLVM_DEBUG(dbgs() << "   Delete (!parameter): ");
 605                   LLVM_DEBUG(SI->print(dbgs()));
 606                   LLVM_DEBUG(dbgs() << "\n");
 607                 }
 608               }
 609             } else {
 610               LLVM_DEBUG(dbgs() << "   Defer: ");
 611               LLVM_DEBUG(U->print(dbgs()));
 612               LLVM_DEBUG(dbgs() << "\n");
 613             }
 614           }
 615         } else {
 616           LLVM_DEBUG(dbgs() << "  Delete (alloca NULL): ");
 617           LLVM_DEBUG(BI->print(dbgs()));
 618           LLVM_DEBUG(dbgs() << "\n");
 619         }
 620       } else {
 621         LLVM_DEBUG(dbgs() << "  Delete (!parameter): ");
 622         LLVM_DEBUG(BI->print(dbgs()));
 623         LLVM_DEBUG(dbgs() << "\n");
 624       }
 625     } else if (BI->isTerminator() && &*BI == GEntryBlock->getTerminator()) {
 626       LLVM_DEBUG(dbgs() << " Will Include Terminator: ");
 627       LLVM_DEBUG(BI->print(dbgs()));
 628       LLVM_DEBUG(dbgs() << "\n");
 629       PDIRelated.insert(&*BI);
 630     } else {
 631       LLVM_DEBUG(dbgs() << " Defer: ");
 632       LLVM_DEBUG(BI->print(dbgs()));
 633       LLVM_DEBUG(dbgs() << "\n");
 634     }
 635   }
 636   LLVM_DEBUG(
 637       dbgs()
 638       << " Report parameter debug info related/related instructions: {\n");
 639   for (BasicBlock::iterator BI = GEntryBlock->begin(), BE = GEntryBlock->end();
 640        BI != BE; ++BI) {
 641
 642     Instruction *I = &*BI;
 643     if (PDIRelated.find(I) == PDIRelated.end()) {
 644       LLVM_DEBUG(dbgs() << "  !PDIRelated: ");
 645       LLVM_DEBUG(I->print(dbgs()));
 646       LLVM_DEBUG(dbgs() << "\n");
 647       PDIUnrelatedWL.push_back(I);
 648     } else {
 649       LLVM_DEBUG(dbgs() << "   PDIRelated: ");
 650       LLVM_DEBUG(I->print(dbgs()));
 651       LLVM_DEBUG(dbgs() << "\n");
 652     }
 653   }
 654   LLVM_DEBUG(dbgs() << " }\n");
 655 }
 656
 657 // Don't merge tiny functions using a thunk, since it can just end up
 658 // making the function larger.
 659 static bool isThunkProfitable(Function * F) {
 660   if (F->size() == 1) {
 661     if (F->front().size() <= 2) {
 662       LLVM_DEBUG(dbgs() << "isThunkProfitable: " << F->getName()
 663                         << " is too small to bother creating a thunk for\n");
 664       return false;
 665     }
 666   }
 667   return true;
 668 }
 669
 670 // Replace G with a simple tail call to bitcast(F). Also (unless
 671 // MergeFunctionsPDI holds) replace direct uses of G with bitcast(F),
 672 // delete G. Under MergeFunctionsPDI, we use G itself for creating
 673 // the thunk as we preserve the debug info (and associated instructions)
 674 // from G's entry block pertaining to G's incoming arguments which are
 675 // passed on as corresponding arguments in the call that G makes to F.
 676 // For better debugability, under MergeFunctionsPDI, we do not modify G's
 677 // call sites to point to F even when within the same translation unit.
 678 void MergeFunctions::writeThunk(Function *F, Function *G) {
 679   BasicBlock *GEntryBlock = nullptr;
 680   std::vector<Instruction *> PDIUnrelatedWL;
 681   BasicBlock *BB = nullptr;
 682   Function *NewG = nullptr;
 683   if (MergeFunctionsPDI) {
 684     LLVM_DEBUG(dbgs() << "writeThunk: (MergeFunctionsPDI) Do not create a new "
 685                          "function as thunk; retain original: "
 686                       << G->getName() << "()\n");
 687     GEntryBlock = &G->getEntryBlock();
 688     LLVM_DEBUG(
 689         dbgs() << "writeThunk: (MergeFunctionsPDI) filter parameter related "
 690                   "debug info for "
 691                << G->getName() << "() {\n");
 692     filterInstsUnrelatedToPDI(GEntryBlock, PDIUnrelatedWL);
 693     GEntryBlock->getTerminator()->eraseFromParent();
 694     BB = GEntryBlock;
 695   } else {
 696     NewG = Function::Create(G->getFunctionType(), G->getLinkage(),
 697                             G->getAddressSpace(), "", G->getParent());
 698     BB = BasicBlock::Create(F->getContext(), "", NewG);
 699   }
 700
 701   IRBuilder<> Builder(BB);
 702   Function *H = MergeFunctionsPDI ? G : NewG;
 703   SmallVector<Value *, 16> Args;
 704   unsigned i = 0;
 705   FunctionType *FFTy = F->getFunctionType();
 706   for (Argument &AI : H->args()) {
 707     Args.push_back(createCast(Builder, &AI, FFTy->getParamType(i)));
 708     ++i;
 709   }
 710
 711   CallInst *CI = Builder.CreateCall(F, Args);
 712   ReturnInst *RI = nullptr;
 713   CI->setTailCall();
 714   CI->setCallingConv(F->getCallingConv());
 715   CI->setAttributes(F->getAttributes());
 716   if (H->getReturnType()->isVoidTy()) {
 717     RI = Builder.CreateRetVoid();
 718   } else {
 719     RI = Builder.CreateRet(createCast(Builder, CI, H->getReturnType()));
 720   }
 721
 722   if (MergeFunctionsPDI) {
 723     DISubprogram *DIS = G->getSubprogram();
 724     if (DIS) {
 725       DebugLoc CIDbgLoc = DebugLoc::get(DIS->getScopeLine(), 0, DIS);
 726       DebugLoc RIDbgLoc = DebugLoc::get(DIS->getScopeLine(), 0, DIS);
 727       CI->setDebugLoc(CIDbgLoc);
 728       RI->setDebugLoc(RIDbgLoc);
 729     } else {
 730       LLVM_DEBUG(
 731           dbgs() << "writeThunk: (MergeFunctionsPDI) No DISubprogram for "
 732                  << G->getName() << "()\n");
 733     }
 734     eraseTail(G);
 735     eraseInstsUnrelatedToPDI(PDIUnrelatedWL);
 736     LLVM_DEBUG(
 737         dbgs() << "} // End of parameter related debug info filtering for: "
 738                << G->getName() << "()\n");
 739   } else {
 740     NewG->copyAttributesFrom(G);
 741     NewG->takeName(G);
 742     removeUsers(G);
 743     G->replaceAllUsesWith(NewG);
 744     G->eraseFromParent();
 745   }
 746
 747   LLVM_DEBUG(dbgs() << "writeThunk: " << H->getName() << '\n');
 748   ++NumThunksWritten;
 749 }
 750
 751 // Whether this function may be replaced by an alias
 752 static bool canCreateAliasFor(Function *F) {
 753   if (!MergeFunctionsAliases || !F->hasGlobalUnnamedAddr())
 754     return false;
 755
 756   // We should only see linkages supported by aliases here
 757   assert(F->hasLocalLinkage() || F->hasExternalLinkage()
 758       || F->hasWeakLinkage() || F->hasLinkOnceLinkage());
 759   return true;
 760 }
 761
 762 // Replace G with an alias to F (deleting function G)
 763 void MergeFunctions::writeAlias(Function *F, Function *G) {
 764   Constant *BitcastF = ConstantExpr::getBitCast(F, G->getType());
 765   PointerType *PtrType = G->getType();
 766   auto *GA = GlobalAlias::create(
 767       PtrType->getElementType(), PtrType->getAddressSpace(),
 768       G->getLinkage(), "", BitcastF, G->getParent());
 769
 770   F->setAlignment(std::max(F->getAlignment(), G->getAlignment()));
 771   GA->takeName(G);
 772   GA->setVisibility(G->getVisibility());
 773   GA->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
 774
 775   removeUsers(G);
 776   G->replaceAllUsesWith(GA);
 777   G->eraseFromParent();
 778
 779   LLVM_DEBUG(dbgs() << "writeAlias: " << GA->getName() << '\n');
 780   ++NumAliasesWritten;
 781 }
 782
 783 // Replace G with an alias to F if possible, or a thunk to F if
 784 // profitable. Returns false if neither is the case.
 785 bool MergeFunctions::writeThunkOrAlias(Function *F, Function *G) {
 786   if (canCreateAliasFor(G)) {
 787     writeAlias(F, G);
 788     return true;
 789   }
 790   if (isThunkProfitable(F)) {
 791     writeThunk(F, G);
 792     return true;
 793   }
 794   return false;
 795 }
 796
 797 // Merge two equivalent functions. Upon completion, Function G is deleted.
 798 void MergeFunctions::mergeTwoFunctions(Function *F, Function *G) {
 799   if (F->isInterposable()) {
 800     assert(G->isInterposable());
 801
 802     // Both writeThunkOrAlias() calls below must succeed, either because we can
 803     // create aliases for G and NewF, or because a thunk for F is profitable.
 804     // F here has the same signature as NewF below, so that's what we check.
 805     if (!isThunkProfitable(F) && (!canCreateAliasFor(F) || !canCreateAliasFor(G))) {
 806       return;
 807     }
 808
 809     // Make them both thunks to the same internal function.
 810     Function *NewF = Function::Create(F->getFunctionType(), F->getLinkage(),
 811                                       F->getAddressSpace(), "", F->getParent());
 812     NewF->copyAttributesFrom(F);
 813     NewF->takeName(F);
 814     removeUsers(F);
 815     F->replaceAllUsesWith(NewF);
 816
 817     unsigned MaxAlignment = std::max(G->getAlignment(), NewF->getAlignment());
 818
 819     writeThunkOrAlias(F, G);
 820     writeThunkOrAlias(F, NewF);
 821
 822     F->setAlignment(MaxAlignment);
 823     F->setLinkage(GlobalValue::PrivateLinkage);
 824     ++NumDoubleWeak;
 825     ++NumFunctionsMerged;
 826   } else {
 827     // For better debugability, under MergeFunctionsPDI, we do not modify G's
 828     // call sites to point to F even when within the same translation unit.
 829     if (!G->isInterposable() && !MergeFunctionsPDI) {
 830       if (G->hasGlobalUnnamedAddr()) {
 831         // G might have been a key in our GlobalNumberState, and it's illegal
 832         // to replace a key in ValueMap<GlobalValue *> with a non-global.
 833         GlobalNumbers.erase(G);
 834         // If G's address is not significant, replace it entirely.
 835         Constant *BitcastF = ConstantExpr::getBitCast(F, G->getType());
 836         removeUsers(G);
 837         G->replaceAllUsesWith(BitcastF);
 838       } else {
 839         // Redirect direct callers of G to F. (See note on MergeFunctionsPDI
 840         // above).
 841         replaceDirectCallers(G, F);
 842       }
 843     }
 844
 845     // If G was internal then we may have replaced all uses of G with F. If so,
 846     // stop here and delete G. There's no need for a thunk. (See note on
 847     // MergeFunctionsPDI above).
 848     if (G->isDiscardableIfUnused() && G->use_empty() && !MergeFunctionsPDI) {
 849       G->eraseFromParent();
 850       ++NumFunctionsMerged;
 851       return;
 852     }
 853
 854     if (writeThunkOrAlias(F, G)) {
 855       ++NumFunctionsMerged;
 856     }
 857   }
 858 }
 859
 860 /// Replace function F by function G.
 861 void MergeFunctions::replaceFunctionInTree(const FunctionNode &FN,
 862                                            Function *G) {
 863   Function *F = FN.getFunc();
 864   assert(FunctionComparator(F, G, &GlobalNumbers).compare() == 0 &&
 865          "The two functions must be equal");
 866
 867   auto I = FNodesInTree.find(F);
 868   assert(I != FNodesInTree.end() && "F should be in FNodesInTree");
 869   assert(FNodesInTree.count(G) == 0 && "FNodesInTree should not contain G");
 870
 871   FnTreeType::iterator IterToFNInFnTree = I->second;
 872   assert(&(*IterToFNInFnTree) == &FN && "F should map to FN in FNodesInTree.");
 873   // Remove F -> FN and insert G -> FN
 874   FNodesInTree.erase(I);
 875   FNodesInTree.insert({G, IterToFNInFnTree});
 876   // Replace F with G in FN, which is stored inside the FnTree.
 877   FN.replaceBy(G);
 878 }
 879
 880 // Ordering for functions that are equal under FunctionComparator
 881 static bool isFuncOrderCorrect(const Function *F, const Function *G) {
 882   if (F->isInterposable() != G->isInterposable()) {
 883     // Strong before weak, because the weak function may call the strong
 884     // one, but not the other way around.
 885     return !F->isInterposable();
 886   }
 887   if (F->hasLocalLinkage() != G->hasLocalLinkage()) {
 888     // External before local, because we definitely have to keep the external
 889     // function, but may be able to drop the local one.
 890     return !F->hasLocalLinkage();
 891   }
 892   // Impose a total order (by name) on the replacement of functions. This is
 893   // important when operating on more than one module independently to prevent
 894   // cycles of thunks calling each other when the modules are linked together.
 895   return F->getName() <= G->getName();
 896 }
 897
 898 // Insert a ComparableFunction into the FnTree, or merge it away if equal to one
 899 // that was already inserted.
 900 bool MergeFunctions::insert(Function *NewFunction) {
 901   std::pair<FnTreeType::iterator, bool> Result =
 902       FnTree.insert(FunctionNode(NewFunction));
 903
 904   if (Result.second) {
 905     assert(FNodesInTree.count(NewFunction) == 0);
 906     FNodesInTree.insert({NewFunction, Result.first});
 907     LLVM_DEBUG(dbgs() << "Inserting as unique: " << NewFunction->getName()
 908                       << '\n');
 909     return false;
 910   }
 911
 912   const FunctionNode &OldF = *Result.first;
 913
 914   if (!isFuncOrderCorrect(OldF.getFunc(), NewFunction)) {
 915     // Swap the two functions.
 916     Function *F = OldF.getFunc();
 917     replaceFunctionInTree(*Result.first, NewFunction);
 918     NewFunction = F;
 919     assert(OldF.getFunc() != F && "Must have swapped the functions.");
 920   }
 921
 922   LLVM_DEBUG(dbgs() << "  " << OldF.getFunc()->getName()
 923                     << " == " << NewFunction->getName() << '\n');
 924
 925   Function *DeleteF = NewFunction;
 926   mergeTwoFunctions(OldF.getFunc(), DeleteF);
 927   return true;
 928 }
 929
 930 // Remove a function from FnTree. If it was already in FnTree, add
 931 // it to Deferred so that we'll look at it in the next round.
 932 void MergeFunctions::remove(Function *F) {
 933   auto I = FNodesInTree.find(F);
 934   if (I != FNodesInTree.end()) {
 935     LLVM_DEBUG(dbgs() << "Deferred " << F->getName() << ".\n");
 936     FnTree.erase(I->second);
 937     // I->second has been invalidated, remove it from the FNodesInTree map to
 938     // preserve the invariant.
 939     FNodesInTree.erase(I);
 940     Deferred.emplace_back(F);
 941   }
 942 }
 943
 944 // For each instruction used by the value, remove() the function that contains
 945 // the instruction. This should happen right before a call to RAUW.
 946 void MergeFunctions::removeUsers(Value *V) {
 947   std::vector<Value *> Worklist;
 948   Worklist.push_back(V);
 949   SmallPtrSet<Value*, 8> Visited;
 950   Visited.insert(V);
 951   while (!Worklist.empty()) {
 952     Value *V = Worklist.back();
 953     Worklist.pop_back();
 954
 955     for (User *U : V->users()) {
 956       if (Instruction *I = dyn_cast<Instruction>(U)) {
 957         remove(I->getFunction());
 958       } else if (isa<GlobalValue>(U)) {
 959         // do nothing
 960       } else if (Constant *C = dyn_cast<Constant>(U)) {
 961         for (User *UU : C->users()) {
 962           if (!Visited.insert(UU).second)
 963             Worklist.push_back(UU);
 964         }
 965       }
 966     }
 967   }
 968 }