LLVM  6.0.0svn
MergeFunctions.cpp
Go to the documentation of this file.
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/Hashing.h"
93 #include "llvm/ADT/STLExtras.h"
94 #include "llvm/ADT/SmallSet.h"
95 #include "llvm/ADT/Statistic.h"
96 #include "llvm/IR/CallSite.h"
97 #include "llvm/IR/Constants.h"
98 #include "llvm/IR/DataLayout.h"
99 #include "llvm/IR/DebugInfo.h"
100 #include "llvm/IR/IRBuilder.h"
101 #include "llvm/IR/Instructions.h"
102 #include "llvm/IR/IntrinsicInst.h"
103 #include "llvm/IR/LLVMContext.h"
104 #include "llvm/IR/Module.h"
105 #include "llvm/IR/ValueHandle.h"
106 #include "llvm/IR/ValueMap.h"
107 #include "llvm/Pass.h"
109 #include "llvm/Support/Debug.h"
112 #include "llvm/Transforms/IPO.h"
114 #include <vector>
115 
116 using namespace llvm;
117 
118 #define DEBUG_TYPE "mergefunc"
119 
120 STATISTIC(NumFunctionsMerged, "Number of functions merged");
121 STATISTIC(NumThunksWritten, "Number of thunks generated");
122 STATISTIC(NumAliasesWritten, "Number of aliases generated");
123 STATISTIC(NumDoubleWeak, "Number of new functions created");
124 
126  "mergefunc-sanity",
127  cl::desc("How many functions in module could be used for "
128  "MergeFunctions pass sanity check. "
129  "'0' disables this check. Works only with '-debug' key."),
130  cl::init(0), cl::Hidden);
131 
132 // Under option -mergefunc-preserve-debug-info we:
133 // - Do not create a new function for a thunk.
134 // - Retain the debug info for a thunk's parameters (and associated
135 // instructions for the debug info) from the entry block.
136 // Note: -debug will display the algorithm at work.
137 // - Create debug-info for the call (to the shared implementation) made by
138 // a thunk and its return value.
139 // - Erase the rest of the function, retaining the (minimally sized) entry
140 // block to create a thunk.
141 // - Preserve a thunk's call site to point to the thunk even when both occur
142 // within the same translation unit, to aid debugability. Note that this
143 // behaviour differs from the underlying -mergefunc implementation which
144 // modifies the thunk's call site to point to the shared implementation
145 // when both occur within the same translation unit.
146 static cl::opt<bool>
147  MergeFunctionsPDI("mergefunc-preserve-debug-info", cl::Hidden,
148  cl::init(false),
149  cl::desc("Preserve debug info in thunk when mergefunc "
150  "transformations are made."));
151 
152 namespace {
153 
154 class FunctionNode {
155  mutable AssertingVH<Function> F;
157 public:
158  // Note the hash is recalculated potentially multiple times, but it is cheap.
159  FunctionNode(Function *F)
160  : F(F), Hash(FunctionComparator::functionHash(*F)) {}
161  Function *getFunc() const { return F; }
162  FunctionComparator::FunctionHash getHash() const { return Hash; }
163 
164  /// Replace the reference to the function F by the function G, assuming their
165  /// implementations are equal.
166  void replaceBy(Function *G) const {
167  F = G;
168  }
169 
170  void release() { F = nullptr; }
171 };
172 
173 /// MergeFunctions finds functions which will generate identical machine code,
174 /// by considering all pointer types to be equivalent. Once identified,
175 /// MergeFunctions will fold them by replacing a call to one to a call to a
176 /// bitcast of the other.
177 ///
178 class MergeFunctions : public ModulePass {
179 public:
180  static char ID;
181  MergeFunctions()
182  : ModulePass(ID), FnTree(FunctionNodeCmp(&GlobalNumbers)), FNodesInTree(),
183  HasGlobalAliases(false) {
185  }
186 
187  bool runOnModule(Module &M) override;
188 
189 private:
190  // The function comparison operator is provided here so that FunctionNodes do
191  // not need to become larger with another pointer.
192  class FunctionNodeCmp {
193  GlobalNumberState* GlobalNumbers;
194  public:
195  FunctionNodeCmp(GlobalNumberState* GN) : GlobalNumbers(GN) {}
196  bool operator()(const FunctionNode &LHS, const FunctionNode &RHS) const {
197  // Order first by hashes, then full function comparison.
198  if (LHS.getHash() != RHS.getHash())
199  return LHS.getHash() < RHS.getHash();
200  FunctionComparator FCmp(LHS.getFunc(), RHS.getFunc(), GlobalNumbers);
201  return FCmp.compare() == -1;
202  }
203  };
204  typedef std::set<FunctionNode, FunctionNodeCmp> FnTreeType;
205 
206  GlobalNumberState GlobalNumbers;
207 
208  /// A work queue of functions that may have been modified and should be
209  /// analyzed again.
210  std::vector<WeakTrackingVH> Deferred;
211 
212  /// Checks the rules of order relation introduced among functions set.
213  /// Returns true, if sanity check has been passed, and false if failed.
214 #ifndef NDEBUG
215  bool doSanityCheck(std::vector<WeakTrackingVH> &Worklist);
216 #endif
217 
218  /// Insert a ComparableFunction into the FnTree, or merge it away if it's
219  /// equal to one that's already present.
220  bool insert(Function *NewFunction);
221 
222  /// Remove a Function from the FnTree and queue it up for a second sweep of
223  /// analysis.
224  void remove(Function *F);
225 
226  /// Find the functions that use this Value and remove them from FnTree and
227  /// queue the functions.
228  void removeUsers(Value *V);
229 
230  /// Replace all direct calls of Old with calls of New. Will bitcast New if
231  /// necessary to make types match.
232  void replaceDirectCallers(Function *Old, Function *New);
233 
234  /// Merge two equivalent functions. Upon completion, G may be deleted, or may
235  /// be converted into a thunk. In either case, it should never be visited
236  /// again.
237  void mergeTwoFunctions(Function *F, Function *G);
238 
239  /// Replace G with a thunk or an alias to F. Deletes G.
240  void writeThunkOrAlias(Function *F, Function *G);
241 
242  /// Fill PDIUnrelatedWL with instructions from the entry block that are
243  /// unrelated to parameter related debug info.
244  void filterInstsUnrelatedToPDI(BasicBlock *GEntryBlock,
245  std::vector<Instruction *> &PDIUnrelatedWL);
246 
247  /// Erase the rest of the CFG (i.e. barring the entry block).
248  void eraseTail(Function *G);
249 
250  /// Erase the instructions in PDIUnrelatedWL as they are unrelated to the
251  /// parameter debug info, from the entry block.
252  void eraseInstsUnrelatedToPDI(std::vector<Instruction *> &PDIUnrelatedWL);
253 
254  /// Replace G with a simple tail call to bitcast(F). Also (unless
255  /// MergeFunctionsPDI holds) replace direct uses of G with bitcast(F),
256  /// delete G.
257  void writeThunk(Function *F, Function *G);
258 
259  /// Replace G with an alias to F. Deletes G.
260  void writeAlias(Function *F, Function *G);
261 
262  /// Replace function F with function G in the function tree.
263  void replaceFunctionInTree(const FunctionNode &FN, Function *G);
264 
265  /// The set of all distinct functions. Use the insert() and remove() methods
266  /// to modify it. The map allows efficient lookup and deferring of Functions.
267  FnTreeType FnTree;
268  // Map functions to the iterators of the FunctionNode which contains them
269  // in the FnTree. This must be updated carefully whenever the FnTree is
270  // modified, i.e. in insert(), remove(), and replaceFunctionInTree(), to avoid
271  // dangling iterators into FnTree. The invariant that preserves this is that
272  // there is exactly one mapping F -> FN for each FunctionNode FN in FnTree.
274 
275  /// Whether or not the target supports global aliases.
276  bool HasGlobalAliases;
277 };
278 
279 } // end anonymous namespace
280 
281 char MergeFunctions::ID = 0;
282 INITIALIZE_PASS(MergeFunctions, "mergefunc", "Merge Functions", false, false)
283 
285  return new MergeFunctions();
286 }
287 
288 #ifndef NDEBUG
289 bool MergeFunctions::doSanityCheck(std::vector<WeakTrackingVH> &Worklist) {
290  if (const unsigned Max = NumFunctionsForSanityCheck) {
291  unsigned TripleNumber = 0;
292  bool Valid = true;
293 
294  dbgs() << "MERGEFUNC-SANITY: Started for first " << Max << " functions.\n";
295 
296  unsigned i = 0;
297  for (std::vector<WeakTrackingVH>::iterator I = Worklist.begin(),
298  E = Worklist.end();
299  I != E && i < Max; ++I, ++i) {
300  unsigned j = i;
301  for (std::vector<WeakTrackingVH>::iterator J = I; J != E && j < Max;
302  ++J, ++j) {
303  Function *F1 = cast<Function>(*I);
304  Function *F2 = cast<Function>(*J);
305  int Res1 = FunctionComparator(F1, F2, &GlobalNumbers).compare();
306  int Res2 = FunctionComparator(F2, F1, &GlobalNumbers).compare();
307 
308  // If F1 <= F2, then F2 >= F1, otherwise report failure.
309  if (Res1 != -Res2) {
310  dbgs() << "MERGEFUNC-SANITY: Non-symmetric; triple: " << TripleNumber
311  << "\n";
312  dbgs() << *F1 << '\n' << *F2 << '\n';
313  Valid = false;
314  }
315 
316  if (Res1 == 0)
317  continue;
318 
319  unsigned k = j;
320  for (std::vector<WeakTrackingVH>::iterator K = J; K != E && k < Max;
321  ++k, ++K, ++TripleNumber) {
322  if (K == J)
323  continue;
324 
325  Function *F3 = cast<Function>(*K);
326  int Res3 = FunctionComparator(F1, F3, &GlobalNumbers).compare();
327  int Res4 = FunctionComparator(F2, F3, &GlobalNumbers).compare();
328 
329  bool Transitive = true;
330 
331  if (Res1 != 0 && Res1 == Res4) {
332  // F1 > F2, F2 > F3 => F1 > F3
333  Transitive = Res3 == Res1;
334  } else if (Res3 != 0 && Res3 == -Res4) {
335  // F1 > F3, F3 > F2 => F1 > F2
336  Transitive = Res3 == Res1;
337  } else if (Res4 != 0 && -Res3 == Res4) {
338  // F2 > F3, F3 > F1 => F2 > F1
339  Transitive = Res4 == -Res1;
340  }
341 
342  if (!Transitive) {
343  dbgs() << "MERGEFUNC-SANITY: Non-transitive; triple: "
344  << TripleNumber << "\n";
345  dbgs() << "Res1, Res3, Res4: " << Res1 << ", " << Res3 << ", "
346  << Res4 << "\n";
347  dbgs() << *F1 << '\n' << *F2 << '\n' << *F3 << '\n';
348  Valid = false;
349  }
350  }
351  }
352  }
353 
354  dbgs() << "MERGEFUNC-SANITY: " << (Valid ? "Passed." : "Failed.") << "\n";
355  return Valid;
356  }
357  return true;
358 }
359 #endif
360 
361 bool MergeFunctions::runOnModule(Module &M) {
362  if (skipModule(M))
363  return false;
364 
365  bool Changed = false;
366 
367  // All functions in the module, ordered by hash. Functions with a unique
368  // hash value are easily eliminated.
369  std::vector<std::pair<FunctionComparator::FunctionHash, Function *>>
370  HashedFuncs;
371  for (Function &Func : M) {
372  if (!Func.isDeclaration() && !Func.hasAvailableExternallyLinkage()) {
373  HashedFuncs.push_back({FunctionComparator::functionHash(Func), &Func});
374  }
375  }
376 
377  std::stable_sort(
378  HashedFuncs.begin(), HashedFuncs.end(),
379  [](const std::pair<FunctionComparator::FunctionHash, Function *> &a,
380  const std::pair<FunctionComparator::FunctionHash, Function *> &b) {
381  return a.first < b.first;
382  });
383 
384  auto S = HashedFuncs.begin();
385  for (auto I = HashedFuncs.begin(), IE = HashedFuncs.end(); I != IE; ++I) {
386  // If the hash value matches the previous value or the next one, we must
387  // consider merging it. Otherwise it is dropped and never considered again.
388  if ((I != S && std::prev(I)->first == I->first) ||
389  (std::next(I) != IE && std::next(I)->first == I->first) ) {
390  Deferred.push_back(WeakTrackingVH(I->second));
391  }
392  }
393 
394  do {
395  std::vector<WeakTrackingVH> Worklist;
396  Deferred.swap(Worklist);
397 
398  DEBUG(doSanityCheck(Worklist));
399 
400  DEBUG(dbgs() << "size of module: " << M.size() << '\n');
401  DEBUG(dbgs() << "size of worklist: " << Worklist.size() << '\n');
402 
403  // Insert functions and merge them.
404  for (WeakTrackingVH &I : Worklist) {
405  if (!I)
406  continue;
407  Function *F = cast<Function>(I);
408  if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage()) {
409  Changed |= insert(F);
410  }
411  }
412  DEBUG(dbgs() << "size of FnTree: " << FnTree.size() << '\n');
413  } while (!Deferred.empty());
414 
415  FnTree.clear();
416  GlobalNumbers.clear();
417 
418  return Changed;
419 }
420 
421 // Replace direct callers of Old with New.
422 void MergeFunctions::replaceDirectCallers(Function *Old, Function *New) {
423  Constant *BitcastNew = ConstantExpr::getBitCast(New, Old->getType());
424  for (auto UI = Old->use_begin(), UE = Old->use_end(); UI != UE;) {
425  Use *U = &*UI;
426  ++UI;
427  CallSite CS(U->getUser());
428  if (CS && CS.isCallee(U)) {
429  // Transfer the called function's attributes to the call site. Due to the
430  // bitcast we will 'lose' ABI changing attributes because the 'called
431  // function' is no longer a Function* but the bitcast. Code that looks up
432  // the attributes from the called function will fail.
433 
434  // FIXME: This is not actually true, at least not anymore. The callsite
435  // will always have the same ABI affecting attributes as the callee,
436  // because otherwise the original input has UB. Note that Old and New
437  // always have matching ABI, so no attributes need to be changed.
438  // Transferring other attributes may help other optimizations, but that
439  // should be done uniformly and not in this ad-hoc way.
440  auto &Context = New->getContext();
441  auto NewPAL = New->getAttributes();
442  SmallVector<AttributeSet, 4> NewArgAttrs;
443  for (unsigned argIdx = 0; argIdx < CS.arg_size(); argIdx++)
444  NewArgAttrs.push_back(NewPAL.getParamAttributes(argIdx));
445  // Don't transfer attributes from the function to the callee. Function
446  // attributes typically aren't relevant to the calling convention or ABI.
447  CS.setAttributes(AttributeList::get(Context, /*FnAttrs=*/AttributeSet(),
448  NewPAL.getRetAttributes(),
449  NewArgAttrs));
450 
451  remove(CS.getInstruction()->getParent()->getParent());
452  U->set(BitcastNew);
453  }
454  }
455 }
456 
457 // Replace G with an alias to F if possible, or else a thunk to F. Deletes G.
458 void MergeFunctions::writeThunkOrAlias(Function *F, Function *G) {
459  if (HasGlobalAliases && G->hasGlobalUnnamedAddr()) {
460  if (G->hasExternalLinkage() || G->hasLocalLinkage() ||
461  G->hasWeakLinkage()) {
462  writeAlias(F, G);
463  return;
464  }
465  }
466 
467  writeThunk(F, G);
468 }
469 
470 // Helper for writeThunk,
471 // Selects proper bitcast operation,
472 // but a bit simpler then CastInst::getCastOpcode.
473 static Value *createCast(IRBuilder<> &Builder, Value *V, Type *DestTy) {
474  Type *SrcTy = V->getType();
475  if (SrcTy->isStructTy()) {
476  assert(DestTy->isStructTy());
477  assert(SrcTy->getStructNumElements() == DestTy->getStructNumElements());
478  Value *Result = UndefValue::get(DestTy);
479  for (unsigned int I = 0, E = SrcTy->getStructNumElements(); I < E; ++I) {
480  Value *Element = createCast(
481  Builder, Builder.CreateExtractValue(V, makeArrayRef(I)),
482  DestTy->getStructElementType(I));
483 
484  Result =
485  Builder.CreateInsertValue(Result, Element, makeArrayRef(I));
486  }
487  return Result;
488  }
489  assert(!DestTy->isStructTy());
490  if (SrcTy->isIntegerTy() && DestTy->isPointerTy())
491  return Builder.CreateIntToPtr(V, DestTy);
492  else if (SrcTy->isPointerTy() && DestTy->isIntegerTy())
493  return Builder.CreatePtrToInt(V, DestTy);
494  else
495  return Builder.CreateBitCast(V, DestTy);
496 }
497 
498 // Erase the instructions in PDIUnrelatedWL as they are unrelated to the
499 // parameter debug info, from the entry block.
500 void MergeFunctions::eraseInstsUnrelatedToPDI(
501  std::vector<Instruction *> &PDIUnrelatedWL) {
502 
503  DEBUG(dbgs() << " Erasing instructions (in reverse order of appearance in "
504  "entry block) unrelated to parameter debug info from entry "
505  "block: {\n");
506  while (!PDIUnrelatedWL.empty()) {
507  Instruction *I = PDIUnrelatedWL.back();
508  DEBUG(dbgs() << " Deleting Instruction: ");
509  DEBUG(I->print(dbgs()));
510  DEBUG(dbgs() << "\n");
511  I->eraseFromParent();
512  PDIUnrelatedWL.pop_back();
513  }
514  DEBUG(dbgs() << " } // Done erasing instructions unrelated to parameter "
515  "debug info from entry block. \n");
516 }
517 
518 // Reduce G to its entry block.
519 void MergeFunctions::eraseTail(Function *G) {
520 
521  std::vector<BasicBlock *> WorklistBB;
522  for (Function::iterator BBI = std::next(G->begin()), BBE = G->end();
523  BBI != BBE; ++BBI) {
524  BBI->dropAllReferences();
525  WorklistBB.push_back(&*BBI);
526  }
527  while (!WorklistBB.empty()) {
528  BasicBlock *BB = WorklistBB.back();
529  BB->eraseFromParent();
530  WorklistBB.pop_back();
531  }
532 }
533 
534 // We are interested in the following instructions from the entry block as being
535 // related to parameter debug info:
536 // - @llvm.dbg.declare
537 // - stores from the incoming parameters to locations on the stack-frame
538 // - allocas that create these locations on the stack-frame
539 // - @llvm.dbg.value
540 // - the entry block's terminator
541 // The rest are unrelated to debug info for the parameters; fill up
542 // PDIUnrelatedWL with such instructions.
543 void MergeFunctions::filterInstsUnrelatedToPDI(
544  BasicBlock *GEntryBlock, std::vector<Instruction *> &PDIUnrelatedWL) {
545 
546  std::set<Instruction *> PDIRelated;
547  for (BasicBlock::iterator BI = GEntryBlock->begin(), BIE = GEntryBlock->end();
548  BI != BIE; ++BI) {
549  if (auto *DVI = dyn_cast<DbgValueInst>(&*BI)) {
550  DEBUG(dbgs() << " Deciding: ");
551  DEBUG(BI->print(dbgs()));
552  DEBUG(dbgs() << "\n");
553  DILocalVariable *DILocVar = DVI->getVariable();
554  if (DILocVar->isParameter()) {
555  DEBUG(dbgs() << " Include (parameter): ");
556  DEBUG(BI->print(dbgs()));
557  DEBUG(dbgs() << "\n");
558  PDIRelated.insert(&*BI);
559  } else {
560  DEBUG(dbgs() << " Delete (!parameter): ");
561  DEBUG(BI->print(dbgs()));
562  DEBUG(dbgs() << "\n");
563  }
564  } else if (auto *DDI = dyn_cast<DbgDeclareInst>(&*BI)) {
565  DEBUG(dbgs() << " Deciding: ");
566  DEBUG(BI->print(dbgs()));
567  DEBUG(dbgs() << "\n");
568  DILocalVariable *DILocVar = DDI->getVariable();
569  if (DILocVar->isParameter()) {
570  DEBUG(dbgs() << " Parameter: ");
571  DEBUG(DILocVar->print(dbgs()));
572  AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress());
573  if (AI) {
574  DEBUG(dbgs() << " Processing alloca users: ");
575  DEBUG(dbgs() << "\n");
576  for (User *U : AI->users()) {
577  if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
578  if (Value *Arg = SI->getValueOperand()) {
579  if (dyn_cast<Argument>(Arg)) {
580  DEBUG(dbgs() << " Include: ");
581  DEBUG(AI->print(dbgs()));
582  DEBUG(dbgs() << "\n");
583  PDIRelated.insert(AI);
584  DEBUG(dbgs() << " Include (parameter): ");
585  DEBUG(SI->print(dbgs()));
586  DEBUG(dbgs() << "\n");
587  PDIRelated.insert(SI);
588  DEBUG(dbgs() << " Include: ");
589  DEBUG(BI->print(dbgs()));
590  DEBUG(dbgs() << "\n");
591  PDIRelated.insert(&*BI);
592  } else {
593  DEBUG(dbgs() << " Delete (!parameter): ");
594  DEBUG(SI->print(dbgs()));
595  DEBUG(dbgs() << "\n");
596  }
597  }
598  } else {
599  DEBUG(dbgs() << " Defer: ");
600  DEBUG(U->print(dbgs()));
601  DEBUG(dbgs() << "\n");
602  }
603  }
604  } else {
605  DEBUG(dbgs() << " Delete (alloca NULL): ");
606  DEBUG(BI->print(dbgs()));
607  DEBUG(dbgs() << "\n");
608  }
609  } else {
610  DEBUG(dbgs() << " Delete (!parameter): ");
611  DEBUG(BI->print(dbgs()));
612  DEBUG(dbgs() << "\n");
613  }
614  } else if (dyn_cast<TerminatorInst>(BI) == GEntryBlock->getTerminator()) {
615  DEBUG(dbgs() << " Will Include Terminator: ");
616  DEBUG(BI->print(dbgs()));
617  DEBUG(dbgs() << "\n");
618  PDIRelated.insert(&*BI);
619  } else {
620  DEBUG(dbgs() << " Defer: ");
621  DEBUG(BI->print(dbgs()));
622  DEBUG(dbgs() << "\n");
623  }
624  }
625  DEBUG(dbgs()
626  << " Report parameter debug info related/related instructions: {\n");
627  for (BasicBlock::iterator BI = GEntryBlock->begin(), BE = GEntryBlock->end();
628  BI != BE; ++BI) {
629 
630  Instruction *I = &*BI;
631  if (PDIRelated.find(I) == PDIRelated.end()) {
632  DEBUG(dbgs() << " !PDIRelated: ");
633  DEBUG(I->print(dbgs()));
634  DEBUG(dbgs() << "\n");
635  PDIUnrelatedWL.push_back(I);
636  } else {
637  DEBUG(dbgs() << " PDIRelated: ");
638  DEBUG(I->print(dbgs()));
639  DEBUG(dbgs() << "\n");
640  }
641  }
642  DEBUG(dbgs() << " }\n");
643 }
644 
645 // Replace G with a simple tail call to bitcast(F). Also (unless
646 // MergeFunctionsPDI holds) replace direct uses of G with bitcast(F),
647 // delete G. Under MergeFunctionsPDI, we use G itself for creating
648 // the thunk as we preserve the debug info (and associated instructions)
649 // from G's entry block pertaining to G's incoming arguments which are
650 // passed on as corresponding arguments in the call that G makes to F.
651 // For better debugability, under MergeFunctionsPDI, we do not modify G's
652 // call sites to point to F even when within the same translation unit.
653 void MergeFunctions::writeThunk(Function *F, Function *G) {
654  if (!G->isInterposable() && !MergeFunctionsPDI) {
655  // Redirect direct callers of G to F. (See note on MergeFunctionsPDI
656  // above).
657  replaceDirectCallers(G, F);
658  }
659 
660  // If G was internal then we may have replaced all uses of G with F. If so,
661  // stop here and delete G. There's no need for a thunk. (See note on
662  // MergeFunctionsPDI above).
663  if (G->hasLocalLinkage() && G->use_empty() && !MergeFunctionsPDI) {
664  G->eraseFromParent();
665  return;
666  }
667 
668  BasicBlock *GEntryBlock = nullptr;
669  std::vector<Instruction *> PDIUnrelatedWL;
670  BasicBlock *BB = nullptr;
671  Function *NewG = nullptr;
672  if (MergeFunctionsPDI) {
673  DEBUG(dbgs() << "writeThunk: (MergeFunctionsPDI) Do not create a new "
674  "function as thunk; retain original: "
675  << G->getName() << "()\n");
676  GEntryBlock = &G->getEntryBlock();
677  DEBUG(dbgs() << "writeThunk: (MergeFunctionsPDI) filter parameter related "
678  "debug info for "
679  << G->getName() << "() {\n");
680  filterInstsUnrelatedToPDI(GEntryBlock, PDIUnrelatedWL);
681  GEntryBlock->getTerminator()->eraseFromParent();
682  BB = GEntryBlock;
683  } else {
684  NewG = Function::Create(G->getFunctionType(), G->getLinkage(), "",
685  G->getParent());
686  BB = BasicBlock::Create(F->getContext(), "", NewG);
687  }
688 
689  IRBuilder<> Builder(BB);
690  Function *H = MergeFunctionsPDI ? G : NewG;
692  unsigned i = 0;
693  FunctionType *FFTy = F->getFunctionType();
694  for (Argument & AI : H->args()) {
695  Args.push_back(createCast(Builder, &AI, FFTy->getParamType(i)));
696  ++i;
697  }
698 
699  CallInst *CI = Builder.CreateCall(F, Args);
700  ReturnInst *RI = nullptr;
701  CI->setTailCall();
702  CI->setCallingConv(F->getCallingConv());
703  CI->setAttributes(F->getAttributes());
704  if (H->getReturnType()->isVoidTy()) {
705  RI = Builder.CreateRetVoid();
706  } else {
707  RI = Builder.CreateRet(createCast(Builder, CI, H->getReturnType()));
708  }
709 
710  if (MergeFunctionsPDI) {
711  DISubprogram *DIS = G->getSubprogram();
712  if (DIS) {
713  DebugLoc CIDbgLoc = DebugLoc::get(DIS->getScopeLine(), 0, DIS);
714  DebugLoc RIDbgLoc = DebugLoc::get(DIS->getScopeLine(), 0, DIS);
715  CI->setDebugLoc(CIDbgLoc);
716  RI->setDebugLoc(RIDbgLoc);
717  } else {
718  DEBUG(dbgs() << "writeThunk: (MergeFunctionsPDI) No DISubprogram for "
719  << G->getName() << "()\n");
720  }
721  eraseTail(G);
722  eraseInstsUnrelatedToPDI(PDIUnrelatedWL);
723  DEBUG(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  DEBUG(dbgs() << "writeThunk: " << H->getName() << '\n');
734  ++NumThunksWritten;
735 }
736 
737 // Replace G with an alias to F and delete G.
738 void MergeFunctions::writeAlias(Function *F, Function *G) {
739  auto *GA = GlobalAlias::create(G->getLinkage(), "", F);
741  GA->takeName(G);
742  GA->setVisibility(G->getVisibility());
743  removeUsers(G);
744  G->replaceAllUsesWith(GA);
745  G->eraseFromParent();
746 
747  DEBUG(dbgs() << "writeAlias: " << GA->getName() << '\n');
748  ++NumAliasesWritten;
749 }
750 
751 // Merge two equivalent functions. Upon completion, Function G is deleted.
752 void MergeFunctions::mergeTwoFunctions(Function *F, Function *G) {
753  if (F->isInterposable()) {
754  assert(G->isInterposable());
755 
756  // Make them both thunks to the same internal function.
758  F->getParent());
759  H->copyAttributesFrom(F);
760  H->takeName(F);
761  removeUsers(F);
762  F->replaceAllUsesWith(H);
763 
764  unsigned MaxAlignment = std::max(G->getAlignment(), H->getAlignment());
765 
766  if (HasGlobalAliases) {
767  writeAlias(F, G);
768  writeAlias(F, H);
769  } else {
770  writeThunk(F, G);
771  writeThunk(F, H);
772  }
773 
774  F->setAlignment(MaxAlignment);
776  ++NumDoubleWeak;
777  } else {
778  writeThunkOrAlias(F, G);
779  }
780 
781  ++NumFunctionsMerged;
782 }
783 
784 /// Replace function F by function G.
785 void MergeFunctions::replaceFunctionInTree(const FunctionNode &FN,
786  Function *G) {
787  Function *F = FN.getFunc();
788  assert(FunctionComparator(F, G, &GlobalNumbers).compare() == 0 &&
789  "The two functions must be equal");
790 
791  auto I = FNodesInTree.find(F);
792  assert(I != FNodesInTree.end() && "F should be in FNodesInTree");
793  assert(FNodesInTree.count(G) == 0 && "FNodesInTree should not contain G");
794 
795  FnTreeType::iterator IterToFNInFnTree = I->second;
796  assert(&(*IterToFNInFnTree) == &FN && "F should map to FN in FNodesInTree.");
797  // Remove F -> FN and insert G -> FN
798  FNodesInTree.erase(I);
799  FNodesInTree.insert({G, IterToFNInFnTree});
800  // Replace F with G in FN, which is stored inside the FnTree.
801  FN.replaceBy(G);
802 }
803 
804 // Insert a ComparableFunction into the FnTree, or merge it away if equal to one
805 // that was already inserted.
806 bool MergeFunctions::insert(Function *NewFunction) {
807  std::pair<FnTreeType::iterator, bool> Result =
808  FnTree.insert(FunctionNode(NewFunction));
809 
810  if (Result.second) {
811  assert(FNodesInTree.count(NewFunction) == 0);
812  FNodesInTree.insert({NewFunction, Result.first});
813  DEBUG(dbgs() << "Inserting as unique: " << NewFunction->getName() << '\n');
814  return false;
815  }
816 
817  const FunctionNode &OldF = *Result.first;
818 
819  // Don't merge tiny functions, since it can just end up making the function
820  // larger.
821  // FIXME: Should still merge them if they are unnamed_addr and produce an
822  // alias.
823  if (NewFunction->size() == 1) {
824  if (NewFunction->front().size() <= 2) {
825  DEBUG(dbgs() << NewFunction->getName()
826  << " is to small to bother merging\n");
827  return false;
828  }
829  }
830 
831  // Impose a total order (by name) on the replacement of functions. This is
832  // important when operating on more than one module independently to prevent
833  // cycles of thunks calling each other when the modules are linked together.
834  //
835  // First of all, we process strong functions before weak functions.
836  if ((OldF.getFunc()->isInterposable() && !NewFunction->isInterposable()) ||
837  (OldF.getFunc()->isInterposable() == NewFunction->isInterposable() &&
838  OldF.getFunc()->getName() > NewFunction->getName())) {
839  // Swap the two functions.
840  Function *F = OldF.getFunc();
841  replaceFunctionInTree(*Result.first, NewFunction);
842  NewFunction = F;
843  assert(OldF.getFunc() != F && "Must have swapped the functions.");
844  }
845 
846  DEBUG(dbgs() << " " << OldF.getFunc()->getName()
847  << " == " << NewFunction->getName() << '\n');
848 
849  Function *DeleteF = NewFunction;
850  mergeTwoFunctions(OldF.getFunc(), DeleteF);
851  return true;
852 }
853 
854 // Remove a function from FnTree. If it was already in FnTree, add
855 // it to Deferred so that we'll look at it in the next round.
857  auto I = FNodesInTree.find(F);
858  if (I != FNodesInTree.end()) {
859  DEBUG(dbgs() << "Deferred " << F->getName()<< ".\n");
860  FnTree.erase(I->second);
861  // I->second has been invalidated, remove it from the FNodesInTree map to
862  // preserve the invariant.
863  FNodesInTree.erase(I);
864  Deferred.emplace_back(F);
865  }
866 }
867 
868 // For each instruction used by the value, remove() the function that contains
869 // the instruction. This should happen right before a call to RAUW.
870 void MergeFunctions::removeUsers(Value *V) {
871  std::vector<Value *> Worklist;
872  Worklist.push_back(V);
873  SmallSet<Value*, 8> Visited;
874  Visited.insert(V);
875  while (!Worklist.empty()) {
876  Value *V = Worklist.back();
877  Worklist.pop_back();
878 
879  for (User *U : V->users()) {
880  if (Instruction *I = dyn_cast<Instruction>(U)) {
881  remove(I->getParent()->getParent());
882  } else if (isa<GlobalValue>(U)) {
883  // do nothing
884  } else if (Constant *C = dyn_cast<Constant>(U)) {
885  for (User *UU : C->users()) {
886  if (!Visited.insert(UU).second)
887  Worklist.push_back(UU);
888  }
889  }
890  }
891  }
892 }
size_t size() const
Definition: Function.h:585
uint64_t CallInst * C
Return a value (possibly void), from a function.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:69
unsigned getAlignment() const
Definition: GlobalObject.h:59
use_iterator use_end()
Definition: Value.h:342
bool hasLocalLinkage() const
Definition: GlobalValue.h:416
DILocation * get() const
Get the underlying DILocation.
Definition: DebugLoc.cpp:22
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
This class represents an incoming formal argument to a Function.
Definition: Argument.h:30
LLVMContext & Context
static Value * createCast(IRBuilder<> &Builder, Value *V, Type *DestTy)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Type * getParamType(unsigned i) const
Parameter type accessors.
Definition: DerivedTypes.h:135
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
iterator end()
Definition: Function.h:582
std::error_code remove(const Twine &path, bool IgnoreNonExisting=true)
Remove path.
ModulePass * createMergeFunctionsPass()
createMergeFunctionsPass - This pass discovers identical functions and collapses them.
This class represents a function call, abstracting a target machine&#39;s calling convention.
bool hasAvailableExternallyLinkage() const
Definition: GlobalValue.h:403
Like Internal, but omit from symbol table.
Definition: GlobalValue.h:57
bool isInterposable() const
Return true if this global&#39;s definition can be substituted with an arbitrary definition at link time...
Definition: GlobalValue.h:400
STATISTIC(NumFunctions, "Total number of functions")
A debug info location.
Definition: DebugLoc.h:34
Type * getStructElementType(unsigned N) const
Definition: DerivedTypes.h:333
void setAlignment(unsigned Align)
Definition: Globals.cpp:110
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
void setCallingConv(CallingConv::ID CC)
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:451
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:197
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:664
Value * CreateIntToPtr(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1440
bool hasExternalLinkage() const
Definition: GlobalValue.h:402
Subprogram description.
Class to represent function types.
Definition: DerivedTypes.h:103
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1444
#define F(x, y, z)
Definition: MD5.cpp:55
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
Value handle that is nullable, but tries to track the Value.
Definition: ValueHandle.h:182
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:197
An instruction for storing to memory.
Definition: Instructions.h:306
LinkageTypes getLinkage() const
Definition: GlobalValue.h:430
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:428
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:290
iterator begin()
Definition: Function.h:580
void initializeMergeFunctionsPass(PassRegistry &)
static cl::opt< unsigned > NumFunctionsForSanityCheck("mergefunc-sanity", cl::desc("How many functions in module could be used for " "MergeFunctions pass sanity check. " "'0' disables this check. Works only with '-debug' key."), cl::init(0), cl::Hidden)
static FunctionHash functionHash(Function &)
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1678
bool isVoidTy() const
Return true if this is &#39;void&#39;.
Definition: Type.h:141
const BasicBlock & getEntryBlock() const
Definition: Function.h:564
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:404
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:142
FunctionComparator - Compares two functions to determine whether or not they will generate machine co...
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:277
VisibilityTypes getVisibility() const
Definition: GlobalValue.h:220
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1498
This is an important base class in LLVM.
Definition: Constant.h:42
void copyAttributesFrom(const Function *Src)
copyAttributesFrom - copy all additional attributes (those not needed to create a Function) from the ...
Definition: Function.cpp:463
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:36
This file contains the declarations for the subclasses of Constant, which represent the different fla...
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:221
#define H(x, y, z)
Definition: MD5.cpp:57
size_t size() const
Definition: BasicBlock.h:262
const Instruction & back() const
Definition: BasicBlock.h:266
void print(raw_ostream &O, bool IsForDebug=false) const
Implement operator<< on Value.
Definition: AsmWriter.cpp:3459
unsigned getStructNumElements() const
Definition: DerivedTypes.h:329
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:101
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:81
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:194
void setTailCall(bool isTC=true)
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1320
Value * CreateExtractValue(Value *Agg, ArrayRef< unsigned > Idxs, const Twine &Name="")
Definition: IRBuilder.h:1751
uint64_t FunctionHash
Hash a function.
unsigned first
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:34
bool hasWeakLinkage() const
Definition: GlobalValue.h:410
void print(raw_ostream &OS, const Module *M=nullptr, bool IsForDebug=false) const
Print.
Definition: AsmWriter.cpp:3592
static cl::opt< bool > MergeFunctionsPDI("mergefunc-preserve-debug-info", cl::Hidden, cl::init(false), cl::desc("Preserve debug info in thunk when mergefunc " "transformations are made."))
Iterator for intrusive lists based on ilist_node.
See the file comment.
Definition: ValueMap.h:86
#define E
Definition: LargeTest.cpp:27
iterator end()
Definition: BasicBlock.h:254
CallingConv::ID getCallingConv() const
getCallingConv()/setCallingConv(CC) - These method get and set the calling convention of this functio...
Definition: Function.h:186
GlobalNumberState assigns an integer to each global value in the program, which is used by the compar...
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
Module.h This file contains the declarations for the Module class.
const DataFlowGraph & G
Definition: RDFGraph.cpp:206
bool hasGlobalUnnamedAddr() const
Definition: GlobalValue.h:187
Value handle that asserts if the Value is deleted.
Definition: ValueHandle.h:238
void setLinkage(LinkageTypes LT)
Definition: GlobalValue.h:425
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
FunctionType * getFunctionType() const
Returns the FunctionType for me.
Definition: Function.h:137
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
int compare()
Test whether the two functions have equivalent behaviour.
iterator_range< user_iterator > users()
Definition: Value.h:395
use_iterator use_begin()
Definition: Value.h:334
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:218
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink &#39;this&#39; from the containing function and delete it.
Definition: BasicBlock.cpp:97
#define I(x, y, z)
Definition: MD5.cpp:58
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:235
void eraseFromParent()
eraseFromParent - This method unlinks &#39;this&#39; from the containing module and deletes it...
Definition: Function.cpp:202
Value * CreatePtrToInt(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1436
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:200
int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Compare two scaled numbers.
Definition: ScaledNumber.h:252
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
const BasicBlock & front() const
Definition: Function.h:587
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:545
LLVM Value Representation.
Definition: Value.h:73
#define DEBUG(X)
Definition: Debug.h:118
std::string Hash(const Unit &U)
Definition: FuzzerSHA1.cpp:216
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, const Twine &N="", Module *M=nullptr)
Definition: Function.h:128
const TerminatorInst * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:120
Value * CreateInsertValue(Value *Agg, Value *Val, ArrayRef< unsigned > Idxs, const Twine &Name="")
Definition: IRBuilder.h:1759
void pop_back()
Definition: ilist.h:331
bool use_empty() const
Definition: Value.h:322
static GlobalAlias * create(Type *Ty, unsigned AddressSpace, LinkageTypes Linkage, const Twine &Name, Constant *Aliasee, Module *Parent)
If a parent module is specified, the alias is automatically inserted into the end of the specified mo...
Definition: Globals.cpp:399
PointerType * getType() const
Global values are always pointers.
Definition: GlobalValue.h:260
static AttributeList get(LLVMContext &C, ArrayRef< std::pair< unsigned, Attribute >> Attrs)
Create an AttributeList with the specified parameters in it.
Definition: Attributes.cpp:868
iterator_range< arg_iterator > args()
Definition: Function.h:613
bool isStructTy() const
True if this is an instance of StructType.
Definition: Type.h:215
an instruction to allocate memory on the stack
Definition: Instructions.h:60