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