LLVM  14.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 (Use &U : llvm::make_early_inc_range(Old->uses())) {
467  CallBase *CB = dyn_cast<CallBase>(U.getUser());
468  if (CB && CB->isCallee(&U)) {
469  // Do not copy attributes from the called function to the call-site.
470  // Function comparison ensures that the attributes are the same up to
471  // type congruences in byval(), in which case we need to keep the byval
472  // type of the call-site, not the callee function.
473  remove(CB->getFunction());
474  U.set(BitcastNew);
475  }
476  }
477 }
478 
479 // Helper for writeThunk,
480 // Selects proper bitcast operation,
481 // but a bit simpler then CastInst::getCastOpcode.
482 static Value *createCast(IRBuilder<> &Builder, Value *V, Type *DestTy) {
483  Type *SrcTy = V->getType();
484  if (SrcTy->isStructTy()) {
485  assert(DestTy->isStructTy());
486  assert(SrcTy->getStructNumElements() == DestTy->getStructNumElements());
487  Value *Result = UndefValue::get(DestTy);
488  for (unsigned int I = 0, E = SrcTy->getStructNumElements(); I < E; ++I) {
489  Value *Element = createCast(
490  Builder, Builder.CreateExtractValue(V, makeArrayRef(I)),
491  DestTy->getStructElementType(I));
492 
493  Result =
494  Builder.CreateInsertValue(Result, Element, makeArrayRef(I));
495  }
496  return Result;
497  }
498  assert(!DestTy->isStructTy());
499  if (SrcTy->isIntegerTy() && DestTy->isPointerTy())
500  return Builder.CreateIntToPtr(V, DestTy);
501  else if (SrcTy->isPointerTy() && DestTy->isIntegerTy())
502  return Builder.CreatePtrToInt(V, DestTy);
503  else
504  return Builder.CreateBitCast(V, DestTy);
505 }
506 
507 // Erase the instructions in PDIUnrelatedWL as they are unrelated to the
508 // parameter debug info, from the entry block.
509 void MergeFunctions::eraseInstsUnrelatedToPDI(
510  std::vector<Instruction *> &PDIUnrelatedWL) {
511  LLVM_DEBUG(
512  dbgs() << " Erasing instructions (in reverse order of appearance in "
513  "entry block) unrelated to parameter debug info from entry "
514  "block: {\n");
515  while (!PDIUnrelatedWL.empty()) {
516  Instruction *I = PDIUnrelatedWL.back();
517  LLVM_DEBUG(dbgs() << " Deleting Instruction: ");
518  LLVM_DEBUG(I->print(dbgs()));
519  LLVM_DEBUG(dbgs() << "\n");
520  I->eraseFromParent();
521  PDIUnrelatedWL.pop_back();
522  }
523  LLVM_DEBUG(dbgs() << " } // Done erasing instructions unrelated to parameter "
524  "debug info from entry block. \n");
525 }
526 
527 // Reduce G to its entry block.
528 void MergeFunctions::eraseTail(Function *G) {
529  std::vector<BasicBlock *> WorklistBB;
530  for (BasicBlock &BB : drop_begin(*G)) {
531  BB.dropAllReferences();
532  WorklistBB.push_back(&BB);
533  }
534  while (!WorklistBB.empty()) {
535  BasicBlock *BB = WorklistBB.back();
536  BB->eraseFromParent();
537  WorklistBB.pop_back();
538  }
539 }
540 
541 // We are interested in the following instructions from the entry block as being
542 // related to parameter debug info:
543 // - @llvm.dbg.declare
544 // - stores from the incoming parameters to locations on the stack-frame
545 // - allocas that create these locations on the stack-frame
546 // - @llvm.dbg.value
547 // - the entry block's terminator
548 // The rest are unrelated to debug info for the parameters; fill up
549 // PDIUnrelatedWL with such instructions.
550 void MergeFunctions::filterInstsUnrelatedToPDI(
551  BasicBlock *GEntryBlock, std::vector<Instruction *> &PDIUnrelatedWL) {
552  std::set<Instruction *> PDIRelated;
553  for (BasicBlock::iterator BI = GEntryBlock->begin(), BIE = GEntryBlock->end();
554  BI != BIE; ++BI) {
555  if (auto *DVI = dyn_cast<DbgValueInst>(&*BI)) {
556  LLVM_DEBUG(dbgs() << " Deciding: ");
557  LLVM_DEBUG(BI->print(dbgs()));
558  LLVM_DEBUG(dbgs() << "\n");
559  DILocalVariable *DILocVar = DVI->getVariable();
560  if (DILocVar->isParameter()) {
561  LLVM_DEBUG(dbgs() << " Include (parameter): ");
562  LLVM_DEBUG(BI->print(dbgs()));
563  LLVM_DEBUG(dbgs() << "\n");
564  PDIRelated.insert(&*BI);
565  } else {
566  LLVM_DEBUG(dbgs() << " Delete (!parameter): ");
567  LLVM_DEBUG(BI->print(dbgs()));
568  LLVM_DEBUG(dbgs() << "\n");
569  }
570  } else if (auto *DDI = dyn_cast<DbgDeclareInst>(&*BI)) {
571  LLVM_DEBUG(dbgs() << " Deciding: ");
572  LLVM_DEBUG(BI->print(dbgs()));
573  LLVM_DEBUG(dbgs() << "\n");
574  DILocalVariable *DILocVar = DDI->getVariable();
575  if (DILocVar->isParameter()) {
576  LLVM_DEBUG(dbgs() << " Parameter: ");
577  LLVM_DEBUG(DILocVar->print(dbgs()));
578  AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress());
579  if (AI) {
580  LLVM_DEBUG(dbgs() << " Processing alloca users: ");
581  LLVM_DEBUG(dbgs() << "\n");
582  for (User *U : AI->users()) {
583  if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
584  if (Value *Arg = SI->getValueOperand()) {
585  if (isa<Argument>(Arg)) {
586  LLVM_DEBUG(dbgs() << " Include: ");
587  LLVM_DEBUG(AI->print(dbgs()));
588  LLVM_DEBUG(dbgs() << "\n");
589  PDIRelated.insert(AI);
590  LLVM_DEBUG(dbgs() << " Include (parameter): ");
591  LLVM_DEBUG(SI->print(dbgs()));
592  LLVM_DEBUG(dbgs() << "\n");
593  PDIRelated.insert(SI);
594  LLVM_DEBUG(dbgs() << " Include: ");
595  LLVM_DEBUG(BI->print(dbgs()));
596  LLVM_DEBUG(dbgs() << "\n");
597  PDIRelated.insert(&*BI);
598  } else {
599  LLVM_DEBUG(dbgs() << " Delete (!parameter): ");
600  LLVM_DEBUG(SI->print(dbgs()));
601  LLVM_DEBUG(dbgs() << "\n");
602  }
603  }
604  } else {
605  LLVM_DEBUG(dbgs() << " Defer: ");
606  LLVM_DEBUG(U->print(dbgs()));
607  LLVM_DEBUG(dbgs() << "\n");
608  }
609  }
610  } else {
611  LLVM_DEBUG(dbgs() << " Delete (alloca NULL): ");
612  LLVM_DEBUG(BI->print(dbgs()));
613  LLVM_DEBUG(dbgs() << "\n");
614  }
615  } else {
616  LLVM_DEBUG(dbgs() << " Delete (!parameter): ");
617  LLVM_DEBUG(BI->print(dbgs()));
618  LLVM_DEBUG(dbgs() << "\n");
619  }
620  } else if (BI->isTerminator() && &*BI == GEntryBlock->getTerminator()) {
621  LLVM_DEBUG(dbgs() << " Will Include Terminator: ");
622  LLVM_DEBUG(BI->print(dbgs()));
623  LLVM_DEBUG(dbgs() << "\n");
624  PDIRelated.insert(&*BI);
625  } else {
626  LLVM_DEBUG(dbgs() << " Defer: ");
627  LLVM_DEBUG(BI->print(dbgs()));
628  LLVM_DEBUG(dbgs() << "\n");
629  }
630  }
631  LLVM_DEBUG(
632  dbgs()
633  << " Report parameter debug info related/related instructions: {\n");
634  for (Instruction &I : *GEntryBlock) {
635  if (PDIRelated.find(&I) == PDIRelated.end()) {
636  LLVM_DEBUG(dbgs() << " !PDIRelated: ");
637  LLVM_DEBUG(I.print(dbgs()));
638  LLVM_DEBUG(dbgs() << "\n");
639  PDIUnrelatedWL.push_back(&I);
640  } else {
641  LLVM_DEBUG(dbgs() << " PDIRelated: ");
642  LLVM_DEBUG(I.print(dbgs()));
643  LLVM_DEBUG(dbgs() << "\n");
644  }
645  }
646  LLVM_DEBUG(dbgs() << " }\n");
647 }
648 
649 /// Whether this function may be replaced by a forwarding thunk.
650 static bool canCreateThunkFor(Function *F) {
651  if (F->isVarArg())
652  return false;
653 
654  // Don't merge tiny functions using a thunk, since it can just end up
655  // making the function larger.
656  if (F->size() == 1) {
657  if (F->front().size() <= 2) {
658  LLVM_DEBUG(dbgs() << "canCreateThunkFor: " << F->getName()
659  << " is too small to bother creating a thunk for\n");
660  return false;
661  }
662  }
663  return true;
664 }
665 
666 // Replace G with a simple tail call to bitcast(F). Also (unless
667 // MergeFunctionsPDI holds) replace direct uses of G with bitcast(F),
668 // delete G. Under MergeFunctionsPDI, we use G itself for creating
669 // the thunk as we preserve the debug info (and associated instructions)
670 // from G's entry block pertaining to G's incoming arguments which are
671 // passed on as corresponding arguments in the call that G makes to F.
672 // For better debugability, under MergeFunctionsPDI, we do not modify G's
673 // call sites to point to F even when within the same translation unit.
674 void MergeFunctions::writeThunk(Function *F, Function *G) {
675  BasicBlock *GEntryBlock = nullptr;
676  std::vector<Instruction *> PDIUnrelatedWL;
677  BasicBlock *BB = nullptr;
678  Function *NewG = nullptr;
679  if (MergeFunctionsPDI) {
680  LLVM_DEBUG(dbgs() << "writeThunk: (MergeFunctionsPDI) Do not create a new "
681  "function as thunk; retain original: "
682  << G->getName() << "()\n");
683  GEntryBlock = &G->getEntryBlock();
684  LLVM_DEBUG(
685  dbgs() << "writeThunk: (MergeFunctionsPDI) filter parameter related "
686  "debug info for "
687  << G->getName() << "() {\n");
688  filterInstsUnrelatedToPDI(GEntryBlock, PDIUnrelatedWL);
689  GEntryBlock->getTerminator()->eraseFromParent();
690  BB = GEntryBlock;
691  } else {
692  NewG = Function::Create(G->getFunctionType(), G->getLinkage(),
693  G->getAddressSpace(), "", G->getParent());
694  NewG->setComdat(G->getComdat());
695  BB = BasicBlock::Create(F->getContext(), "", NewG);
696  }
697 
699  Function *H = MergeFunctionsPDI ? G : NewG;
701  unsigned i = 0;
702  FunctionType *FFTy = F->getFunctionType();
703  for (Argument &AI : H->args()) {
704  Args.push_back(createCast(Builder, &AI, FFTy->getParamType(i)));
705  ++i;
706  }
707 
708  CallInst *CI = Builder.CreateCall(F, Args);
709  ReturnInst *RI = nullptr;
710  bool isSwiftTailCall = F->getCallingConv() == CallingConv::SwiftTail &&
711  G->getCallingConv() == CallingConv::SwiftTail;
712  CI->setTailCallKind(isSwiftTailCall ? llvm::CallInst::TCK_MustTail
714  CI->setCallingConv(F->getCallingConv());
715  CI->setAttributes(F->getAttributes());
716  if (H->getReturnType()->isVoidTy()) {
717  RI = Builder.CreateRetVoid();
718  } else {
719  RI = Builder.CreateRet(createCast(Builder, CI, H->getReturnType()));
720  }
721 
722  if (MergeFunctionsPDI) {
723  DISubprogram *DIS = G->getSubprogram();
724  if (DIS) {
725  DebugLoc CIDbgLoc =
726  DILocation::get(DIS->getContext(), DIS->getScopeLine(), 0, DIS);
727  DebugLoc RIDbgLoc =
728  DILocation::get(DIS->getContext(), DIS->getScopeLine(), 0, DIS);
729  CI->setDebugLoc(CIDbgLoc);
730  RI->setDebugLoc(RIDbgLoc);
731  } else {
732  LLVM_DEBUG(
733  dbgs() << "writeThunk: (MergeFunctionsPDI) No DISubprogram for "
734  << G->getName() << "()\n");
735  }
736  eraseTail(G);
737  eraseInstsUnrelatedToPDI(PDIUnrelatedWL);
738  LLVM_DEBUG(
739  dbgs() << "} // End of parameter related debug info filtering for: "
740  << G->getName() << "()\n");
741  } else {
742  NewG->copyAttributesFrom(G);
743  NewG->takeName(G);
744  removeUsers(G);
745  G->replaceAllUsesWith(NewG);
746  G->eraseFromParent();
747  }
748 
749  LLVM_DEBUG(dbgs() << "writeThunk: " << H->getName() << '\n');
750  ++NumThunksWritten;
751 }
752 
753 // Whether this function may be replaced by an alias
754 static bool canCreateAliasFor(Function *F) {
755  if (!MergeFunctionsAliases || !F->hasGlobalUnnamedAddr())
756  return false;
757 
758  // We should only see linkages supported by aliases here
759  assert(F->hasLocalLinkage() || F->hasExternalLinkage()
760  || F->hasWeakLinkage() || F->hasLinkOnceLinkage());
761  return true;
762 }
763 
764 // Replace G with an alias to F (deleting function G)
765 void MergeFunctions::writeAlias(Function *F, Function *G) {
766  Constant *BitcastF = ConstantExpr::getBitCast(F, G->getType());
767  PointerType *PtrType = G->getType();
768  auto *GA = GlobalAlias::create(G->getValueType(), 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:482
llvm::GlobalObject::setComdat
void setComdat(Comdat *C)
Definition: Globals.cpp:192
llvm
This is an optimization pass for GlobalISel generic memory operations.
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:321
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:3010
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:217
DebugInfoMetadata.h
llvm::Function
Definition: Function.h:62
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:1177
Statistic.h
llvm::CallInst::setTailCallKind
void setTailCallKind(TailCallKind TCK)
Definition: Instructions.h:1681
llvm::CallingConv::SwiftTail
@ SwiftTail
SwiftTail - This follows the Swift calling convention in how arguments are passed but guarantees tail...
Definition: CallingConv.h:92
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:687
llvm::ConstantExpr::getBitCast
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2282
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:45
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:1406
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:3166
RHS
Value * RHS
Definition: X86PartialReduction.cpp:74
llvm::CallInst::TCK_MustTail
@ TCK_MustTail
Definition: Instructions.h:1658
Use.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1233
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::FunctionComparator::functionHash
static FunctionHash functionHash(Function &)
Definition: FunctionComparator.cpp:954
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:185
Instruction.h
CommandLine.h
LHS
Value * LHS
Definition: X86PartialReduction.cpp:73
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:3104
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:1376
InstrTypes.h
canCreateAliasFor
static bool canCreateAliasFor(Function *F)
Definition: MergeFunctions.cpp:754
llvm::CallBase::setAttributes
void setAttributes(AttributeList A)
Set the parameter attributes for this call.
Definition: InstrTypes.h:1477
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:376
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:712
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1804
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:348
llvm::Type::isIntegerTy
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:190
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:1432
llvm::FunctionComparator::compare
int compare()
Test whether the two functions have equivalent behaviour.
Definition: FunctionComparator.cpp:878
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:309
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
uint64_t
IPO.h
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::FunctionType::getParamType
Type * getParamType(unsigned i) const
Parameter type accessors.
Definition: DerivedTypes.h:135
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:441
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:642
llvm::PointerType
Class to represent pointers.
Definition: DerivedTypes.h:632
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:4571
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:139
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
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:650
llvm::Metadata::print
void print(raw_ostream &OS, const Module *M=nullptr, bool IsForDebug=false) const
Print.
Definition: AsmWriter.cpp:4771
llvm::CallInst::TCK_Tail
@ TCK_Tail
Definition: Instructions.h:1657
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:352
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
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
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:650
llvm::ifs::IFSSymbolType::Func
@ Func
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
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:152
llvm::GlobalObject::getAlignment
uint64_t getAlignment() const
FIXME: Remove this function once transition to Align is over.
Definition: GlobalObject.h:71
ValueMap.h
Argument.h
llvm::MDNode::getContext
LLVMContext & getContext() const
Definition: Metadata.h:967
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:1784
H
#define H(x, y, z)
Definition: MD5.cpp:57
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:482
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:474
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:211
SmallVector.h
User.h
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:1826
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1176
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:382
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:62
llvm::cl::desc
Definition: CommandLine.h:412
raw_ostream.h
Value.h
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
llvm::CallBase::setCallingConv
void setCallingConv(CallingConv::ID CC)
Definition: InstrTypes.h:1458
llvm::FunctionType
Class to represent function types.
Definition: DerivedTypes.h:103
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