• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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.
FunctionNode(Function * F)176   FunctionNode(Function *F)
177     : F(F), Hash(FunctionComparator::functionHash(*F))  {}
178 
getFunc() const179   Function *getFunc() const { return F; }
getHash() const180   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.
replaceBy(Function * G) const184   void replaceBy(Function *G) const {
185     F = G;
186   }
187 
release()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 
MergeFunctions()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:
FunctionNodeCmp(GlobalNumberState * GN)213     FunctionNodeCmp(GlobalNumberState* GN) : GlobalNumbers(GN) {}
214 
operator ()(const FunctionNode & LHS,const FunctionNode & RHS) const215     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 
createMergeFunctionsPass()296 ModulePass *llvm::createMergeFunctionsPass() {
297   return new MergeFunctions();
298 }
299 
300 #ifndef NDEBUG
doSanityCheck(std::vector<WeakTrackingVH> & Worklist)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 
runOnModule(Module & M)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.
replaceDirectCallers(Function * Old,Function * 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.
createCast(IRBuilder<> & Builder,Value * V,Type * DestTy)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.
eraseInstsUnrelatedToPDI(std::vector<Instruction * > & PDIUnrelatedWL)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.
eraseTail(Function * G)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.
filterInstsUnrelatedToPDI(BasicBlock * GEntryBlock,std::vector<Instruction * > & PDIUnrelatedWL)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.
isThunkProfitable(Function * F)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.
writeThunk(Function * F,Function * G)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.
mergeTwoFunctions(Function * F,Function * G)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.
replaceFunctionInTree(const FunctionNode & FN,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.
insert(Function * NewFunction)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.
remove(Function * F)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.
removeUsers(Value * V)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 }
897