LLVM  13.0.0git
MergeFunctions.cpp
Go to the documentation of this file.
1 //===- MergeFunctions.cpp - Merge identical functions ---------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This pass looks for equivalent functions that are mergable and folds them.
10 //
11 // Order relation is defined on set of functions. It was made through
12 // special function comparison procedure that returns
13 // 0 when functions are equal,
14 // -1 when Left function is less than right function, and
15 // 1 for opposite case. We need total-ordering, so we need to maintain
16 // four properties on the functions set:
17 // a <= a (reflexivity)
18 // if a <= b and b <= a then a = b (antisymmetry)
19 // if a <= b and b <= c then a <= c (transitivity).
20 // for all a and b: a <= b or b <= a (totality).
21 //
22 // Comparison iterates through each instruction in each basic block.
23 // Functions are kept on binary tree. For each new function F we perform
24 // lookup in binary tree.
25 // In practice it works the following way:
26 // -- We define Function* container class with custom "operator<" (FunctionPtr).
27 // -- "FunctionPtr" instances are stored in std::set collection, so every
28 // std::set::insert operation will give you result in log(N) time.
29 //
30 // As an optimization, a hash of the function structure is calculated first, and
31 // two functions are only compared if they have the same hash. This hash is
32 // cheap to compute, and has the property that if function F == G according to
33 // the comparison function, then hash(F) == hash(G). This consistency property
34 // is critical to ensuring all possible merging opportunities are exploited.
35 // Collisions in the hash affect the speed of the pass but not the correctness
36 // or determinism of the resulting transformation.
37 //
38 // When a match is found the functions are folded. If both functions are
39 // overridable, we move the functionality into a new internal function and
40 // leave two overridable thunks to it.
41 //
42 //===----------------------------------------------------------------------===//
43 //
44 // Future work:
45 //
46 // * virtual functions.
47 //
48 // Many functions have their address taken by the virtual function table for
49 // the object they belong to. However, as long as it's only used for a lookup
50 // and call, this is irrelevant, and we'd like to fold such functions.
51 //
52 // * be smarter about bitcasts.
53 //
54 // In order to fold functions, we will sometimes add either bitcast instructions
55 // or bitcast constant expressions. Unfortunately, this can confound further
56 // analysis since the two functions differ where one has a bitcast and the
57 // other doesn't. We should learn to look through bitcasts.
58 //
59 // * Compare complex types with pointer types inside.
60 // * Compare cross-reference cases.
61 // * Compare complex expressions.
62 //
63 // All the three issues above could be described as ability to prove that
64 // fA == fB == fC == fE == fF == fG in example below:
65 //
66 // void fA() {
67 // fB();
68 // }
69 // void fB() {
70 // fA();
71 // }
72 //
73 // void fE() {
74 // fF();
75 // }
76 // void fF() {
77 // fG();
78 // }
79 // void fG() {
80 // fE();
81 // }
82 //
83 // Simplest cross-reference case (fA <--> fB) was implemented in previous
84 // versions of MergeFunctions, though it presented only in two function pairs
85 // in test-suite (that counts >50k functions)
86 // Though possibility to detect complex cross-referencing (e.g.: A->B->C->D->A)
87 // could cover much more cases.
88 //
89 //===----------------------------------------------------------------------===//
90 
91 #include "llvm/ADT/ArrayRef.h"
92 #include "llvm/ADT/SmallPtrSet.h"
93 #include "llvm/ADT/SmallVector.h"
94 #include "llvm/ADT/Statistic.h"
95 #include "llvm/IR/Argument.h"
96 #include "llvm/IR/Attributes.h"
97 #include "llvm/IR/BasicBlock.h"
98 #include "llvm/IR/Constant.h"
99 #include "llvm/IR/Constants.h"
101 #include "llvm/IR/DebugLoc.h"
102 #include "llvm/IR/DerivedTypes.h"
103 #include "llvm/IR/Function.h"
104 #include "llvm/IR/GlobalValue.h"
105 #include "llvm/IR/IRBuilder.h"
106 #include "llvm/IR/InstrTypes.h"
107 #include "llvm/IR/Instruction.h"
108 #include "llvm/IR/Instructions.h"
109 #include "llvm/IR/IntrinsicInst.h"
110 #include "llvm/IR/Module.h"
111 #include "llvm/IR/Type.h"
112 #include "llvm/IR/Use.h"
113 #include "llvm/IR/User.h"
114 #include "llvm/IR/Value.h"
115 #include "llvm/IR/ValueHandle.h"
116 #include "llvm/IR/ValueMap.h"
117 #include "llvm/InitializePasses.h"
118 #include "llvm/Pass.h"
119 #include "llvm/Support/Casting.h"
121 #include "llvm/Support/Debug.h"
123 #include "llvm/Transforms/IPO.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 
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;
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 
195 /// MergeFunctions finds functions which will generate identical machine code,
196 /// by considering all pointer types to be equivalent. Once identified,
197 /// MergeFunctions will fold them by replacing a call to one to a call to a
198 /// bitcast of the other.
199 class MergeFunctions {
200 public:
201  MergeFunctions() : FnTree(FunctionNodeCmp(&GlobalNumbers)) {
202  }
203 
204  bool runOnModule(Module &M);
205 
206 private:
207  // The function comparison operator is provided here so that FunctionNodes do
208  // not need to become larger with another pointer.
209  class FunctionNodeCmp {
210  GlobalNumberState* GlobalNumbers;
211 
212  public:
213  FunctionNodeCmp(GlobalNumberState* GN) : GlobalNumbers(GN) {}
214 
215  bool operator()(const FunctionNode &LHS, const FunctionNode &RHS) const {
216  // Order first by hashes, then full function comparison.
217  if (LHS.getHash() != RHS.getHash())
218  return LHS.getHash() < RHS.getHash();
219  FunctionComparator FCmp(LHS.getFunc(), RHS.getFunc(), GlobalNumbers);
220  return FCmp.compare() == -1;
221  }
222  };
223  using FnTreeType = std::set<FunctionNode, FunctionNodeCmp>;
224 
225  GlobalNumberState GlobalNumbers;
226 
227  /// A work queue of functions that may have been modified and should be
228  /// analyzed again.
229  std::vector<WeakTrackingVH> Deferred;
230 
231 #ifndef NDEBUG
232  /// Checks the rules of order relation introduced among functions set.
233  /// Returns true, if sanity check has been passed, and false if failed.
234  bool doSanityCheck(std::vector<WeakTrackingVH> &Worklist);
235 #endif
236 
237  /// Insert a ComparableFunction into the FnTree, or merge it away if it's
238  /// equal to one that's already present.
239  bool insert(Function *NewFunction);
240 
241  /// Remove a Function from the FnTree and queue it up for a second sweep of
242  /// analysis.
243  void remove(Function *F);
244 
245  /// Find the functions that use this Value and remove them from FnTree and
246  /// queue the functions.
247  void removeUsers(Value *V);
248 
249  /// Replace all direct calls of Old with calls of New. Will bitcast New if
250  /// necessary to make types match.
251  void replaceDirectCallers(Function *Old, Function *New);
252 
253  /// Merge two equivalent functions. Upon completion, G may be deleted, or may
254  /// be converted into a thunk. In either case, it should never be visited
255  /// again.
256  void mergeTwoFunctions(Function *F, Function *G);
257 
258  /// Fill PDIUnrelatedWL with instructions from the entry block that are
259  /// unrelated to parameter related debug info.
260  void filterInstsUnrelatedToPDI(BasicBlock *GEntryBlock,
261  std::vector<Instruction *> &PDIUnrelatedWL);
262 
263  /// Erase the rest of the CFG (i.e. barring the entry block).
264  void eraseTail(Function *G);
265 
266  /// Erase the instructions in PDIUnrelatedWL as they are unrelated to the
267  /// parameter debug info, from the entry block.
268  void eraseInstsUnrelatedToPDI(std::vector<Instruction *> &PDIUnrelatedWL);
269 
270  /// Replace G with a simple tail call to bitcast(F). Also (unless
271  /// MergeFunctionsPDI holds) replace direct uses of G with bitcast(F),
272  /// delete G.
273  void writeThunk(Function *F, Function *G);
274 
275  // Replace G with an alias to F (deleting function G)
276  void writeAlias(Function *F, Function *G);
277 
278  // Replace G with an alias to F if possible, or a thunk to F if possible.
279  // Returns false if neither is the case.
280  bool writeThunkOrAlias(Function *F, Function *G);
281 
282  /// Replace function F with function G in the function tree.
283  void replaceFunctionInTree(const FunctionNode &FN, Function *G);
284 
285  /// The set of all distinct functions. Use the insert() and remove() methods
286  /// to modify it. The map allows efficient lookup and deferring of Functions.
287  FnTreeType FnTree;
288 
289  // Map functions to the iterators of the FunctionNode which contains them
290  // in the FnTree. This must be updated carefully whenever the FnTree is
291  // modified, i.e. in insert(), remove(), and replaceFunctionInTree(), to avoid
292  // dangling iterators into FnTree. The invariant that preserves this is that
293  // there is exactly one mapping F -> FN for each FunctionNode FN in FnTree.
294  DenseMap<AssertingVH<Function>, FnTreeType::iterator> FNodesInTree;
295 };
296 
297 class MergeFunctionsLegacyPass : public ModulePass {
298 public:
299  static char ID;
300 
301  MergeFunctionsLegacyPass(): ModulePass(ID) {
303  }
304 
305  bool runOnModule(Module &M) override {
306  if (skipModule(M))
307  return false;
308 
309  MergeFunctions MF;
310  return MF.runOnModule(M);
311  }
312 };
313 
314 } // end anonymous namespace
315 
317 INITIALIZE_PASS(MergeFunctionsLegacyPass, "mergefunc",
318  "Merge Functions", false, false)
319 
321  return new MergeFunctionsLegacyPass();
322 }
323 
325  ModuleAnalysisManager &AM) {
326  MergeFunctions MF;
327  if (!MF.runOnModule(M))
328  return PreservedAnalyses::all();
329  return PreservedAnalyses::none();
330 }
331 
332 #ifndef NDEBUG
333 bool MergeFunctions::doSanityCheck(std::vector<WeakTrackingVH> &Worklist) {
334  if (const unsigned Max = NumFunctionsForSanityCheck) {
335  unsigned TripleNumber = 0;
336  bool Valid = true;
337 
338  dbgs() << "MERGEFUNC-SANITY: Started for first " << Max << " functions.\n";
339 
340  unsigned i = 0;
341  for (std::vector<WeakTrackingVH>::iterator I = Worklist.begin(),
342  E = Worklist.end();
343  I != E && i < Max; ++I, ++i) {
344  unsigned j = i;
345  for (std::vector<WeakTrackingVH>::iterator J = I; J != E && j < Max;
346  ++J, ++j) {
347  Function *F1 = cast<Function>(*I);
348  Function *F2 = cast<Function>(*J);
349  int Res1 = FunctionComparator(F1, F2, &GlobalNumbers).compare();
350  int Res2 = FunctionComparator(F2, F1, &GlobalNumbers).compare();
351 
352  // If F1 <= F2, then F2 >= F1, otherwise report failure.
353  if (Res1 != -Res2) {
354  dbgs() << "MERGEFUNC-SANITY: Non-symmetric; triple: " << TripleNumber
355  << "\n";
356  dbgs() << *F1 << '\n' << *F2 << '\n';
357  Valid = false;
358  }
359 
360  if (Res1 == 0)
361  continue;
362 
363  unsigned k = j;
364  for (std::vector<WeakTrackingVH>::iterator K = J; K != E && k < Max;
365  ++k, ++K, ++TripleNumber) {
366  if (K == J)
367  continue;
368 
369  Function *F3 = cast<Function>(*K);
370  int Res3 = FunctionComparator(F1, F3, &GlobalNumbers).compare();
371  int Res4 = FunctionComparator(F2, F3, &GlobalNumbers).compare();
372 
373  bool Transitive = true;
374 
375  if (Res1 != 0 && Res1 == Res4) {
376  // F1 > F2, F2 > F3 => F1 > F3
377  Transitive = Res3 == Res1;
378  } else if (Res3 != 0 && Res3 == -Res4) {
379  // F1 > F3, F3 > F2 => F1 > F2
380  Transitive = Res3 == Res1;
381  } else if (Res4 != 0 && -Res3 == Res4) {
382  // F2 > F3, F3 > F1 => F2 > F1
383  Transitive = Res4 == -Res1;
384  }
385 
386  if (!Transitive) {
387  dbgs() << "MERGEFUNC-SANITY: Non-transitive; triple: "
388  << TripleNumber << "\n";
389  dbgs() << "Res1, Res3, Res4: " << Res1 << ", " << Res3 << ", "
390  << Res4 << "\n";
391  dbgs() << *F1 << '\n' << *F2 << '\n' << *F3 << '\n';
392  Valid = false;
393  }
394  }
395  }
396  }
397 
398  dbgs() << "MERGEFUNC-SANITY: " << (Valid ? "Passed." : "Failed.") << "\n";
399  return Valid;
400  }
401  return true;
402 }
403 #endif
404 
405 /// Check whether \p F is eligible for function merging.
407  return !F.isDeclaration() && !F.hasAvailableExternallyLinkage();
408 }
409 
410 bool MergeFunctions::runOnModule(Module &M) {
411  bool Changed = false;
412 
413  // All functions in the module, ordered by hash. Functions with a unique
414  // hash value are easily eliminated.
415  std::vector<std::pair<FunctionComparator::FunctionHash, Function *>>
416  HashedFuncs;
417  for (Function &Func : M) {
418  if (isEligibleForMerging(Func)) {
419  HashedFuncs.push_back({FunctionComparator::functionHash(Func), &Func});
420  }
421  }
422 
423  llvm::stable_sort(HashedFuncs, less_first());
424 
425  auto S = HashedFuncs.begin();
426  for (auto I = HashedFuncs.begin(), IE = HashedFuncs.end(); I != IE; ++I) {
427  // If the hash value matches the previous value or the next one, we must
428  // consider merging it. Otherwise it is dropped and never considered again.
429  if ((I != S && std::prev(I)->first == I->first) ||
430  (std::next(I) != IE && std::next(I)->first == I->first) ) {
431  Deferred.push_back(WeakTrackingVH(I->second));
432  }
433  }
434 
435  do {
436  std::vector<WeakTrackingVH> Worklist;
437  Deferred.swap(Worklist);
438 
439  LLVM_DEBUG(doSanityCheck(Worklist));
440 
441  LLVM_DEBUG(dbgs() << "size of module: " << M.size() << '\n');
442  LLVM_DEBUG(dbgs() << "size of worklist: " << Worklist.size() << '\n');
443 
444  // Insert functions and merge them.
445  for (WeakTrackingVH &I : Worklist) {
446  if (!I)
447  continue;
448  Function *F = cast<Function>(I);
449  if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage()) {
450  Changed |= insert(F);
451  }
452  }
453  LLVM_DEBUG(dbgs() << "size of FnTree: " << FnTree.size() << '\n');
454  } while (!Deferred.empty());
455 
456  FnTree.clear();
457  FNodesInTree.clear();
458  GlobalNumbers.clear();
459 
460  return Changed;
461 }
462 
463 // Replace direct callers of Old with New.
464 void MergeFunctions::replaceDirectCallers(Function *Old, Function *New) {
465  Constant *BitcastNew = ConstantExpr::getBitCast(New, Old->getType());
466  for (auto UI = Old->use_begin(), UE = Old->use_end(); UI != UE;) {
467  Use *U = &*UI;
468  ++UI;
469  CallBase *CB = dyn_cast<CallBase>(U->getUser());
470  if (CB && CB->isCallee(U)) {
471  // Do not copy attributes from the called function to the call-site.
472  // Function comparison ensures that the attributes are the same up to
473  // type congruences in byval(), in which case we need to keep the byval
474  // type of the call-site, not the callee function.
475  remove(CB->getFunction());
476  U->set(BitcastNew);
477  }
478  }
479 }
480 
481 // Helper for writeThunk,
482 // Selects proper bitcast operation,
483 // but a bit simpler then CastInst::getCastOpcode.
484 static Value *createCast(IRBuilder<> &Builder, Value *V, Type *DestTy) {
485  Type *SrcTy = V->getType();
486  if (SrcTy->isStructTy()) {
487  assert(DestTy->isStructTy());
488  assert(SrcTy->getStructNumElements() == DestTy->getStructNumElements());
489  Value *Result = UndefValue::get(DestTy);
490  for (unsigned int I = 0, E = SrcTy->getStructNumElements(); I < E; ++I) {
491  Value *Element = createCast(
492  Builder, Builder.CreateExtractValue(V, makeArrayRef(I)),
493  DestTy->getStructElementType(I));
494 
495  Result =
496  Builder.CreateInsertValue(Result, Element, makeArrayRef(I));
497  }
498  return Result;
499  }
500  assert(!DestTy->isStructTy());
501  if (SrcTy->isIntegerTy() && DestTy->isPointerTy())
502  return Builder.CreateIntToPtr(V, DestTy);
503  else if (SrcTy->isPointerTy() && DestTy->isIntegerTy())
504  return Builder.CreatePtrToInt(V, DestTy);
505  else
506  return Builder.CreateBitCast(V, DestTy);
507 }
508 
509 // Erase the instructions in PDIUnrelatedWL as they are unrelated to the
510 // parameter debug info, from the entry block.
511 void MergeFunctions::eraseInstsUnrelatedToPDI(
512  std::vector<Instruction *> &PDIUnrelatedWL) {
513  LLVM_DEBUG(
514  dbgs() << " Erasing instructions (in reverse order of appearance in "
515  "entry block) unrelated to parameter debug info from entry "
516  "block: {\n");
517  while (!PDIUnrelatedWL.empty()) {
518  Instruction *I = PDIUnrelatedWL.back();
519  LLVM_DEBUG(dbgs() << " Deleting Instruction: ");
520  LLVM_DEBUG(I->print(dbgs()));
521  LLVM_DEBUG(dbgs() << "\n");
522  I->eraseFromParent();
523  PDIUnrelatedWL.pop_back();
524  }
525  LLVM_DEBUG(dbgs() << " } // Done erasing instructions unrelated to parameter "
526  "debug info from entry block. \n");
527 }
528 
529 // Reduce G to its entry block.
530 void MergeFunctions::eraseTail(Function *G) {
531  std::vector<BasicBlock *> WorklistBB;
532  for (BasicBlock &BB : drop_begin(*G)) {
533  BB.dropAllReferences();
534  WorklistBB.push_back(&BB);
535  }
536  while (!WorklistBB.empty()) {
537  BasicBlock *BB = WorklistBB.back();
538  BB->eraseFromParent();
539  WorklistBB.pop_back();
540  }
541 }
542 
543 // We are interested in the following instructions from the entry block as being
544 // related to parameter debug info:
545 // - @llvm.dbg.declare
546 // - stores from the incoming parameters to locations on the stack-frame
547 // - allocas that create these locations on the stack-frame
548 // - @llvm.dbg.value
549 // - the entry block's terminator
550 // The rest are unrelated to debug info for the parameters; fill up
551 // PDIUnrelatedWL with such instructions.
552 void MergeFunctions::filterInstsUnrelatedToPDI(
553  BasicBlock *GEntryBlock, std::vector<Instruction *> &PDIUnrelatedWL) {
554  std::set<Instruction *> PDIRelated;
555  for (BasicBlock::iterator BI = GEntryBlock->begin(), BIE = GEntryBlock->end();
556  BI != BIE; ++BI) {
557  if (auto *DVI = dyn_cast<DbgValueInst>(&*BI)) {
558  LLVM_DEBUG(dbgs() << " Deciding: ");
559  LLVM_DEBUG(BI->print(dbgs()));
560  LLVM_DEBUG(dbgs() << "\n");
561  DILocalVariable *DILocVar = DVI->getVariable();
562  if (DILocVar->isParameter()) {
563  LLVM_DEBUG(dbgs() << " Include (parameter): ");
564  LLVM_DEBUG(BI->print(dbgs()));
565  LLVM_DEBUG(dbgs() << "\n");
566  PDIRelated.insert(&*BI);
567  } else {
568  LLVM_DEBUG(dbgs() << " Delete (!parameter): ");
569  LLVM_DEBUG(BI->print(dbgs()));
570  LLVM_DEBUG(dbgs() << "\n");
571  }
572  } else if (auto *DDI = dyn_cast<DbgDeclareInst>(&*BI)) {
573  LLVM_DEBUG(dbgs() << " Deciding: ");
574  LLVM_DEBUG(BI->print(dbgs()));
575  LLVM_DEBUG(dbgs() << "\n");
576  DILocalVariable *DILocVar = DDI->getVariable();
577  if (DILocVar->isParameter()) {
578  LLVM_DEBUG(dbgs() << " Parameter: ");
579  LLVM_DEBUG(DILocVar->print(dbgs()));
580  AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress());
581  if (AI) {
582  LLVM_DEBUG(dbgs() << " Processing alloca users: ");
583  LLVM_DEBUG(dbgs() << "\n");
584  for (User *U : AI->users()) {
585  if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
586  if (Value *Arg = SI->getValueOperand()) {
587  if (isa<Argument>(Arg)) {
588  LLVM_DEBUG(dbgs() << " Include: ");
589  LLVM_DEBUG(AI->print(dbgs()));
590  LLVM_DEBUG(dbgs() << "\n");
591  PDIRelated.insert(AI);
592  LLVM_DEBUG(dbgs() << " Include (parameter): ");
593  LLVM_DEBUG(SI->print(dbgs()));
594  LLVM_DEBUG(dbgs() << "\n");
595  PDIRelated.insert(SI);
596  LLVM_DEBUG(dbgs() << " Include: ");
597  LLVM_DEBUG(BI->print(dbgs()));
598  LLVM_DEBUG(dbgs() << "\n");
599  PDIRelated.insert(&*BI);
600  } else {
601  LLVM_DEBUG(dbgs() << " Delete (!parameter): ");
602  LLVM_DEBUG(SI->print(dbgs()));
603  LLVM_DEBUG(dbgs() << "\n");
604  }
605  }
606  } else {
607  LLVM_DEBUG(dbgs() << " Defer: ");
608  LLVM_DEBUG(U->print(dbgs()));
609  LLVM_DEBUG(dbgs() << "\n");
610  }
611  }
612  } else {
613  LLVM_DEBUG(dbgs() << " Delete (alloca NULL): ");
614  LLVM_DEBUG(BI->print(dbgs()));
615  LLVM_DEBUG(dbgs() << "\n");
616  }
617  } else {
618  LLVM_DEBUG(dbgs() << " Delete (!parameter): ");
619  LLVM_DEBUG(BI->print(dbgs()));
620  LLVM_DEBUG(dbgs() << "\n");
621  }
622  } else if (BI->isTerminator() && &*BI == GEntryBlock->getTerminator()) {
623  LLVM_DEBUG(dbgs() << " Will Include Terminator: ");
624  LLVM_DEBUG(BI->print(dbgs()));
625  LLVM_DEBUG(dbgs() << "\n");
626  PDIRelated.insert(&*BI);
627  } else {
628  LLVM_DEBUG(dbgs() << " Defer: ");
629  LLVM_DEBUG(BI->print(dbgs()));
630  LLVM_DEBUG(dbgs() << "\n");
631  }
632  }
633  LLVM_DEBUG(
634  dbgs()
635  << " Report parameter debug info related/related instructions: {\n");
636  for (Instruction &I : *GEntryBlock) {
637  if (PDIRelated.find(&I) == PDIRelated.end()) {
638  LLVM_DEBUG(dbgs() << " !PDIRelated: ");
639  LLVM_DEBUG(I.print(dbgs()));
640  LLVM_DEBUG(dbgs() << "\n");
641  PDIUnrelatedWL.push_back(&I);
642  } else {
643  LLVM_DEBUG(dbgs() << " PDIRelated: ");
644  LLVM_DEBUG(I.print(dbgs()));
645  LLVM_DEBUG(dbgs() << "\n");
646  }
647  }
648  LLVM_DEBUG(dbgs() << " }\n");
649 }
650 
651 /// Whether this function may be replaced by a forwarding thunk.
652 static bool canCreateThunkFor(Function *F) {
653  if (F->isVarArg())
654  return false;
655 
656  // Don't merge tiny functions using a thunk, since it can just end up
657  // making the function larger.
658  if (F->size() == 1) {
659  if (F->front().size() <= 2) {
660  LLVM_DEBUG(dbgs() << "canCreateThunkFor: " << F->getName()
661  << " is too small to bother creating a thunk for\n");
662  return false;
663  }
664  }
665  return true;
666 }
667 
668 // Replace G with a simple tail call to bitcast(F). Also (unless
669 // MergeFunctionsPDI holds) replace direct uses of G with bitcast(F),
670 // delete G. Under MergeFunctionsPDI, we use G itself for creating
671 // the thunk as we preserve the debug info (and associated instructions)
672 // from G's entry block pertaining to G's incoming arguments which are
673 // passed on as corresponding arguments in the call that G makes to F.
674 // For better debugability, under MergeFunctionsPDI, we do not modify G's
675 // call sites to point to F even when within the same translation unit.
676 void MergeFunctions::writeThunk(Function *F, Function *G) {
677  BasicBlock *GEntryBlock = nullptr;
678  std::vector<Instruction *> PDIUnrelatedWL;
679  BasicBlock *BB = nullptr;
680  Function *NewG = nullptr;
681  if (MergeFunctionsPDI) {
682  LLVM_DEBUG(dbgs() << "writeThunk: (MergeFunctionsPDI) Do not create a new "
683  "function as thunk; retain original: "
684  << G->getName() << "()\n");
685  GEntryBlock = &G->getEntryBlock();
686  LLVM_DEBUG(
687  dbgs() << "writeThunk: (MergeFunctionsPDI) filter parameter related "
688  "debug info for "
689  << G->getName() << "() {\n");
690  filterInstsUnrelatedToPDI(GEntryBlock, PDIUnrelatedWL);
691  GEntryBlock->getTerminator()->eraseFromParent();
692  BB = GEntryBlock;
693  } else {
694  NewG = Function::Create(G->getFunctionType(), G->getLinkage(),
695  G->getAddressSpace(), "", G->getParent());
696  NewG->setComdat(G->getComdat());
697  BB = BasicBlock::Create(F->getContext(), "", NewG);
698  }
699 
701  Function *H = MergeFunctionsPDI ? G : NewG;
703  unsigned i = 0;
704  FunctionType *FFTy = F->getFunctionType();
705  for (Argument &AI : H->args()) {
706  Args.push_back(createCast(Builder, &AI, FFTy->getParamType(i)));
707  ++i;
708  }
709 
710  CallInst *CI = Builder.CreateCall(F, Args);
711  ReturnInst *RI = nullptr;
712  CI->setTailCall();
713  CI->setCallingConv(F->getCallingConv());
714  CI->setAttributes(F->getAttributes());
715  if (H->getReturnType()->isVoidTy()) {
716  RI = Builder.CreateRetVoid();
717  } else {
718  RI = Builder.CreateRet(createCast(Builder, CI, H->getReturnType()));
719  }
720 
721  if (MergeFunctionsPDI) {
722  DISubprogram *DIS = G->getSubprogram();
723  if (DIS) {
724  DebugLoc CIDbgLoc =
725  DILocation::get(DIS->getContext(), DIS->getScopeLine(), 0, DIS);
726  DebugLoc RIDbgLoc =
727  DILocation::get(DIS->getContext(), DIS->getScopeLine(), 0, DIS);
728  CI->setDebugLoc(CIDbgLoc);
729  RI->setDebugLoc(RIDbgLoc);
730  } else {
731  LLVM_DEBUG(
732  dbgs() << "writeThunk: (MergeFunctionsPDI) No DISubprogram for "
733  << G->getName() << "()\n");
734  }
735  eraseTail(G);
736  eraseInstsUnrelatedToPDI(PDIUnrelatedWL);
737  LLVM_DEBUG(
738  dbgs() << "} // End of parameter related debug info filtering for: "
739  << G->getName() << "()\n");
740  } else {
741  NewG->copyAttributesFrom(G);
742  NewG->takeName(G);
743  removeUsers(G);
744  G->replaceAllUsesWith(NewG);
745  G->eraseFromParent();
746  }
747 
748  LLVM_DEBUG(dbgs() << "writeThunk: " << H->getName() << '\n');
749  ++NumThunksWritten;
750 }
751 
752 // Whether this function may be replaced by an alias
753 static bool canCreateAliasFor(Function *F) {
754  if (!MergeFunctionsAliases || !F->hasGlobalUnnamedAddr())
755  return false;
756 
757  // We should only see linkages supported by aliases here
758  assert(F->hasLocalLinkage() || F->hasExternalLinkage()
759  || F->hasWeakLinkage() || F->hasLinkOnceLinkage());
760  return true;
761 }
762 
763 // Replace G with an alias to F (deleting function G)
764 void MergeFunctions::writeAlias(Function *F, Function *G) {
765  Constant *BitcastF = ConstantExpr::getBitCast(F, G->getType());
766  PointerType *PtrType = G->getType();
767  auto *GA = GlobalAlias::create(
768  PtrType->getElementType(), PtrType->getAddressSpace(),
769  G->getLinkage(), "", BitcastF, G->getParent());
770 
771  F->setAlignment(MaybeAlign(std::max(F->getAlignment(), G->getAlignment())));
772  GA->takeName(G);
773  GA->setVisibility(G->getVisibility());
774  GA->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
775 
776  removeUsers(G);
777  G->replaceAllUsesWith(GA);
778  G->eraseFromParent();
779 
780  LLVM_DEBUG(dbgs() << "writeAlias: " << GA->getName() << '\n');
781  ++NumAliasesWritten;
782 }
783 
784 // Replace G with an alias to F if possible, or a thunk to F if
785 // profitable. Returns false if neither is the case.
786 bool MergeFunctions::writeThunkOrAlias(Function *F, Function *G) {
787  if (canCreateAliasFor(G)) {
788  writeAlias(F, G);
789  return true;
790  }
791  if (canCreateThunkFor(F)) {
792  writeThunk(F, G);
793  return true;
794  }
795  return false;
796 }
797 
798 // Merge two equivalent functions. Upon completion, Function G is deleted.
799 void MergeFunctions::mergeTwoFunctions(Function *F, Function *G) {
800  if (F->isInterposable()) {
801  assert(G->isInterposable());
802 
803  // Both writeThunkOrAlias() calls below must succeed, either because we can
804  // create aliases for G and NewF, or because a thunk for F is profitable.
805  // F here has the same signature as NewF below, so that's what we check.
806  if (!canCreateThunkFor(F) &&
808  return;
809 
810  // Make them both thunks to the same internal function.
811  Function *NewF = Function::Create(F->getFunctionType(), F->getLinkage(),
812  F->getAddressSpace(), "", F->getParent());
813  NewF->copyAttributesFrom(F);
814  NewF->takeName(F);
815  removeUsers(F);
816  F->replaceAllUsesWith(NewF);
817 
818  MaybeAlign MaxAlignment(std::max(G->getAlignment(), NewF->getAlignment()));
819 
820  writeThunkOrAlias(F, G);
821  writeThunkOrAlias(F, NewF);
822 
823  F->setAlignment(MaxAlignment);
824  F->setLinkage(GlobalValue::PrivateLinkage);
825  ++NumDoubleWeak;
826  ++NumFunctionsMerged;
827  } else {
828  // For better debugability, under MergeFunctionsPDI, we do not modify G's
829  // call sites to point to F even when within the same translation unit.
830  if (!G->isInterposable() && !MergeFunctionsPDI) {
831  if (G->hasGlobalUnnamedAddr()) {
832  // G might have been a key in our GlobalNumberState, and it's illegal
833  // to replace a key in ValueMap<GlobalValue *> with a non-global.
834  GlobalNumbers.erase(G);
835  // If G's address is not significant, replace it entirely.
836  Constant *BitcastF = ConstantExpr::getBitCast(F, G->getType());
837  removeUsers(G);
838  G->replaceAllUsesWith(BitcastF);
839  } else {
840  // Redirect direct callers of G to F. (See note on MergeFunctionsPDI
841  // above).
842  replaceDirectCallers(G, F);
843  }
844  }
845 
846  // If G was internal then we may have replaced all uses of G with F. If so,
847  // stop here and delete G. There's no need for a thunk. (See note on
848  // MergeFunctionsPDI above).
849  if (G->isDiscardableIfUnused() && G->use_empty() && !MergeFunctionsPDI) {
850  G->eraseFromParent();
851  ++NumFunctionsMerged;
852  return;
853  }
854 
855  if (writeThunkOrAlias(F, G)) {
856  ++NumFunctionsMerged;
857  }
858  }
859 }
860 
861 /// Replace function F by function G.
862 void MergeFunctions::replaceFunctionInTree(const FunctionNode &FN,
863  Function *G) {
864  Function *F = FN.getFunc();
865  assert(FunctionComparator(F, G, &GlobalNumbers).compare() == 0 &&
866  "The two functions must be equal");
867 
868  auto I = FNodesInTree.find(F);
869  assert(I != FNodesInTree.end() && "F should be in FNodesInTree");
870  assert(FNodesInTree.count(G) == 0 && "FNodesInTree should not contain G");
871 
872  FnTreeType::iterator IterToFNInFnTree = I->second;
873  assert(&(*IterToFNInFnTree) == &FN && "F should map to FN in FNodesInTree.");
874  // Remove F -> FN and insert G -> FN
875  FNodesInTree.erase(I);
876  FNodesInTree.insert({G, IterToFNInFnTree});
877  // Replace F with G in FN, which is stored inside the FnTree.
878  FN.replaceBy(G);
879 }
880 
881 // Ordering for functions that are equal under FunctionComparator
882 static bool isFuncOrderCorrect(const Function *F, const Function *G) {
883  if (F->isInterposable() != G->isInterposable()) {
884  // Strong before weak, because the weak function may call the strong
885  // one, but not the other way around.
886  return !F->isInterposable();
887  }
888  if (F->hasLocalLinkage() != G->hasLocalLinkage()) {
889  // External before local, because we definitely have to keep the external
890  // function, but may be able to drop the local one.
891  return !F->hasLocalLinkage();
892  }
893  // Impose a total order (by name) on the replacement of functions. This is
894  // important when operating on more than one module independently to prevent
895  // cycles of thunks calling each other when the modules are linked together.
896  return F->getName() <= G->getName();
897 }
898 
899 // Insert a ComparableFunction into the FnTree, or merge it away if equal to one
900 // that was already inserted.
901 bool MergeFunctions::insert(Function *NewFunction) {
902  std::pair<FnTreeType::iterator, bool> Result =
903  FnTree.insert(FunctionNode(NewFunction));
904 
905  if (Result.second) {
906  assert(FNodesInTree.count(NewFunction) == 0);
907  FNodesInTree.insert({NewFunction, Result.first});
908  LLVM_DEBUG(dbgs() << "Inserting as unique: " << NewFunction->getName()
909  << '\n');
910  return false;
911  }
912 
913  const FunctionNode &OldF = *Result.first;
914 
915  if (!isFuncOrderCorrect(OldF.getFunc(), NewFunction)) {
916  // Swap the two functions.
917  Function *F = OldF.getFunc();
918  replaceFunctionInTree(*Result.first, NewFunction);
919  NewFunction = F;
920  assert(OldF.getFunc() != F && "Must have swapped the functions.");
921  }
922 
923  LLVM_DEBUG(dbgs() << " " << OldF.getFunc()->getName()
924  << " == " << NewFunction->getName() << '\n');
925 
926  Function *DeleteF = NewFunction;
927  mergeTwoFunctions(OldF.getFunc(), DeleteF);
928  return true;
929 }
930 
931 // Remove a function from FnTree. If it was already in FnTree, add
932 // it to Deferred so that we'll look at it in the next round.
934  auto I = FNodesInTree.find(F);
935  if (I != FNodesInTree.end()) {
936  LLVM_DEBUG(dbgs() << "Deferred " << F->getName() << ".\n");
937  FnTree.erase(I->second);
938  // I->second has been invalidated, remove it from the FNodesInTree map to
939  // preserve the invariant.
940  FNodesInTree.erase(I);
941  Deferred.emplace_back(F);
942  }
943 }
944 
945 // For each instruction used by the value, remove() the function that contains
946 // the instruction. This should happen right before a call to RAUW.
947 void MergeFunctions::removeUsers(Value *V) {
948  for (User *U : V->users())
949  if (auto *I = dyn_cast<Instruction>(U))
950  remove(I->getFunction());
951 }
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
llvm::BasicBlock::end
iterator end()
Definition: BasicBlock.h:298
llvm::GlobalNumberState
GlobalNumberState assigns an integer to each global value in the program, which is used by the compar...
Definition: FunctionComparator.h:54
createCast
static Value * createCast(IRBuilder<> &Builder, Value *V, Type *DestTy)
Definition: MergeFunctions.cpp:484
llvm
Definition: AllocatorList.h:23
llvm::MergeFunctionsPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: MergeFunctions.cpp:324
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::drop_begin
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:266
llvm::CallInst::setTailCall
void setTailCall(bool IsTc=true)
Definition: Instructions.h:1685
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:2953
llvm::WeakTrackingVH
Value handle that is nullable, but tries to track the Value.
Definition: ValueHandle.h:204
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
llvm::ModulePass
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:238
IntrinsicInst.h
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:229
DebugInfoMetadata.h
llvm::PointerType::getElementType
Type * getElementType() const
Definition: DerivedTypes.h:675
llvm::Function
Definition: Function.h:61
Pass.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1167
Statistic.h
isEligibleForMerging
static bool isEligibleForMerging(Function &F)
Check whether F is eligible for function merging.
Definition: MergeFunctions.cpp:406
llvm::IRBuilder<>
llvm::PointerType::getAddressSpace
unsigned getAddressSpace() const
Return the address space of the Pointer type.
Definition: DerivedTypes.h:689
llvm::ConstantExpr::getBitCast
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2220
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
MergeFunctions.h
FunctionComparator.h
llvm::PreservedAnalyses::none
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:158
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
Module.h
llvm::CallBase::isCallee
bool isCallee(Value::const_user_iterator UI) const
Determine whether the passed iterator points to the callee operand's Use.
Definition: InstrTypes.h:1404
llvm::GlobalValue::UnnamedAddr::Global
@ Global
llvm::createMergeFunctionsPass
ModulePass * createMergeFunctionsPass()
createMergeFunctionsPass - This pass discovers identical functions and collapses them.
llvm::DILocalVariable::isParameter
bool isParameter() const
Definition: DebugInfoMetadata.h:3107
Use.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1198
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::FunctionComparator::functionHash
static FunctionHash functionHash(Function &)
Definition: FunctionComparator.cpp:948
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:206
Instruction.h
CommandLine.h
GlobalValue.h
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
Constants.h
llvm::DILocalVariable
Local variable.
Definition: DebugInfoMetadata.h:3050
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::User
Definition: User.h:44
isFuncOrderCorrect
static bool isFuncOrderCorrect(const Function *F, const Function *G)
Definition: MergeFunctions.cpp:882
llvm::less_first
Function object to check whether the first component of a std::pair compares less than the first comp...
Definition: STLExtras.h:1261
InstrTypes.h
canCreateAliasFor
static bool canCreateAliasFor(Function *F)
Definition: MergeFunctions.cpp:753
llvm::CallBase::setAttributes
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
Definition: InstrTypes.h:1475
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::MaybeAlign
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
Definition: Alignment.h:109
llvm::Instruction
Definition: Instruction.h:45
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::Function::copyAttributesFrom
void copyAttributesFrom(const Function *Src)
copyAttributesFrom - copy all additional attributes (those not needed to create a Function) from the ...
Definition: Function.cpp:681
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1783
DebugLoc.h
MergeFunctionsPDI
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."))
SmallPtrSet.h
Type.h
llvm::ARM_PROC::IE
@ IE
Definition: ARMBaseInfo.h:27
llvm::Type::getStructNumElements
unsigned getStructNumElements() const
Definition: DerivedTypes.h:350
llvm::Type::isIntegerTy
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:202
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
llvm::GlobalNumberState::clear
void clear()
Definition: FunctionComparator.h:84
BasicBlock.h
llvm::cl::opt
Definition: CommandLine.h:1422
llvm::FunctionComparator::compare
int compare()
Test whether the two functions have equivalent behaviour.
Definition: FunctionComparator.cpp:872
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:303
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
IPO.h
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::FunctionType::getParamType
Type * getParamType(unsigned i) const
Parameter type accessors.
Definition: DerivedTypes.h:134
llvm::GlobalObject::setComdat
void setComdat(Comdat *C)
Definition: GlobalObject.h:125
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
llvm::PointerType
Class to represent pointers.
Definition: DerivedTypes.h:634
ArrayRef.h
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:367
llvm::Value::print
void print(raw_ostream &O, bool IsForDebug=false) const
Implement operator<< on Value.
Definition: AsmWriter.cpp:4623
NumFunctionsForSanityCheck
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)
llvm::Function::Create
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:137
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::elfabi::ELFSymbolType::Func
@ Func
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::ScaledNumbers::compare
int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Compare two scaled numbers.
Definition: ScaledNumber.h:251
llvm::Value::use_begin
use_iterator use_begin()
Definition: Value.h:361
llvm::GlobalObject::getAlignment
unsigned getAlignment() const
FIXME: Remove this function once transition to Align is over.
Definition: GlobalObject.h:71
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
MergeFunctionsAliases
static cl::opt< bool > MergeFunctionsAliases("mergefunc-use-aliases", cl::Hidden, cl::init(false), cl::desc("Allow mergefunc to create aliases"))
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::Metadata::print
void print(raw_ostream &OS, const Module *M=nullptr, bool IsForDebug=false) const
Print.
Definition: AsmWriter.cpp:4752
llvm::sys::fs::remove
std::error_code remove(const Twine &path, bool IgnoreNonExisting=true)
Remove path.
llvm::Type::getStructElementType
Type * getStructElementType(unsigned N) const
Definition: DerivedTypes.h:354
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::Instruction::getFunction
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:70
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
llvm::Value::use_end
use_iterator use_end()
Definition: Value.h:369
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
INITIALIZE_PASS
INITIALIZE_PASS(MergeFunctionsLegacyPass, "mergefunc", "Merge Functions", false, false) ModulePass *llvm
Definition: MergeFunctions.cpp:317
canCreateThunkFor
static bool canCreateThunkFor(Function *F)
Whether this function may be replaced by a forwarding thunk.
Definition: MergeFunctions.cpp:652
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:294
ValueHandle.h
llvm::BasicBlock::getTerminator
const Instruction * 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:148
ValueMap.h
Argument.h
llvm::MDNode::getContext
LLVMContext & getContext() const
Definition: Metadata.h:957
llvm::initializeMergeFunctionsLegacyPassPass
void initializeMergeFunctionsLegacyPassPass(PassRegistry &)
Attributes.h
j
return j(j<< 16)
Constant.h
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1617
H
#define H(x, y, z)
Definition: MD5.cpp:58
llvm::GlobalAlias::create
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:485
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
Casting.h
llvm::GlobalNumberState::erase
void erase(GlobalValue *Global)
Definition: FunctionComparator.h:80
Function.h
llvm::makeArrayRef
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:476
llvm::GlobalValue::PrivateLinkage
@ PrivateLinkage
Like Internal, but omit from symbol table.
Definition: GlobalValue.h:56
Instructions.h
llvm::Type::isStructTy
bool isStructTy() const
True if this is an instance of StructType.
Definition: Type.h:223
SmallVector.h
User.h
llvm::FunctionComparator::FunctionHash
uint64_t FunctionHash
Hash a function.
Definition: FunctionComparator.h:104
llvm::AssertingVH
Value handle that asserts if the Value is deleted.
Definition: ValueHandle.h:260
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::FunctionComparator
FunctionComparator - Compares two functions to determine whether or not they will generate machine co...
Definition: FunctionComparator.h:93
llvm::DISubprogram
Subprogram description.
Definition: DebugInfoMetadata.h:1800
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1164
llvm::GlobalValue::getType
PointerType * getType() const
Global values are always pointers.
Definition: GlobalValue.h:271
DerivedTypes.h
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1478
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::Value::takeName
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:367
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:389
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:61
llvm::cl::desc
Definition: CommandLine.h:414
raw_ostream.h
Value.h
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:422
llvm::CallBase::setCallingConv
void setCallingConv(CallingConv::ID CC)
Definition: InstrTypes.h:1456
llvm::FunctionType
Class to represent function types.
Definition: DerivedTypes.h:102
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38