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