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