LLVM  9.0.0svn
ArgumentPromotion.cpp
Go to the documentation of this file.
1 //===- ArgumentPromotion.cpp - Promote by-reference arguments -------------===//
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 promotes "by reference" arguments to be "by value" arguments. In
10 // practice, this means looking for internal functions that have pointer
11 // arguments. If it can prove, through the use of alias analysis, that an
12 // argument is *only* loaded, then it can pass the value into the function
13 // instead of the address of the value. This can cause recursive simplification
14 // of code and lead to the elimination of allocas (especially in C++ template
15 // code like the STL).
16 //
17 // This pass also handles aggregate arguments that are passed into a function,
18 // scalarizing them if the elements of the aggregate are only loaded. Note that
19 // by default it refuses to scalarize aggregates which would require passing in
20 // more than three operands to the function, because passing thousands of
21 // operands for a large array or structure is unprofitable! This limit can be
22 // configured or disabled, however.
23 //
24 // Note that this transformation could also be done for arguments that are only
25 // stored to (returning the value instead), but does not currently. This case
26 // would be best handled when and if LLVM begins supporting multiple return
27 // values from functions.
28 //
29 //===----------------------------------------------------------------------===//
30 
33 #include "llvm/ADT/None.h"
34 #include "llvm/ADT/Optional.h"
35 #include "llvm/ADT/STLExtras.h"
36 #include "llvm/ADT/SmallPtrSet.h"
37 #include "llvm/ADT/SmallVector.h"
38 #include "llvm/ADT/Statistic.h"
39 #include "llvm/ADT/StringExtras.h"
40 #include "llvm/ADT/Twine.h"
48 #include "llvm/Analysis/Loads.h"
52 #include "llvm/IR/Argument.h"
53 #include "llvm/IR/Attributes.h"
54 #include "llvm/IR/BasicBlock.h"
55 #include "llvm/IR/CFG.h"
56 #include "llvm/IR/CallSite.h"
57 #include "llvm/IR/Constants.h"
58 #include "llvm/IR/DataLayout.h"
59 #include "llvm/IR/DerivedTypes.h"
60 #include "llvm/IR/Function.h"
61 #include "llvm/IR/InstrTypes.h"
62 #include "llvm/IR/Instruction.h"
63 #include "llvm/IR/Instructions.h"
64 #include "llvm/IR/Metadata.h"
65 #include "llvm/IR/Module.h"
66 #include "llvm/IR/PassManager.h"
67 #include "llvm/IR/Type.h"
68 #include "llvm/IR/Use.h"
69 #include "llvm/IR/User.h"
70 #include "llvm/IR/Value.h"
71 #include "llvm/Pass.h"
72 #include "llvm/Support/Casting.h"
73 #include "llvm/Support/Debug.h"
75 #include "llvm/Transforms/IPO.h"
76 #include <algorithm>
77 #include <cassert>
78 #include <cstdint>
79 #include <functional>
80 #include <iterator>
81 #include <map>
82 #include <set>
83 #include <string>
84 #include <utility>
85 #include <vector>
86 
87 using namespace llvm;
88 
89 #define DEBUG_TYPE "argpromotion"
90 
91 STATISTIC(NumArgumentsPromoted, "Number of pointer arguments promoted");
92 STATISTIC(NumAggregatesPromoted, "Number of aggregate arguments promoted");
93 STATISTIC(NumByValArgsPromoted, "Number of byval arguments promoted");
94 STATISTIC(NumArgumentsDead, "Number of dead pointer args eliminated");
95 
96 /// A vector used to hold the indices of a single GEP instruction
97 using IndicesVector = std::vector<uint64_t>;
98 
99 /// DoPromotion - This method actually performs the promotion of the specified
100 /// arguments, and returns the new function. At this point, we know that it's
101 /// safe to do so.
102 static Function *
104  SmallPtrSetImpl<Argument *> &ByValArgsToTransform,
105  Optional<function_ref<void(CallSite OldCS, CallSite NewCS)>>
106  ReplaceCallSite) {
107  // Start by computing a new prototype for the function, which is the same as
108  // the old function, but has modified arguments.
109  FunctionType *FTy = F->getFunctionType();
110  std::vector<Type *> Params;
111 
112  using ScalarizeTable = std::set<std::pair<Type *, IndicesVector>>;
113 
114  // ScalarizedElements - If we are promoting a pointer that has elements
115  // accessed out of it, keep track of which elements are accessed so that we
116  // can add one argument for each.
117  //
118  // Arguments that are directly loaded will have a zero element value here, to
119  // handle cases where there are both a direct load and GEP accesses.
120  std::map<Argument *, ScalarizeTable> ScalarizedElements;
121 
122  // OriginalLoads - Keep track of a representative load instruction from the
123  // original function so that we can tell the alias analysis implementation
124  // what the new GEP/Load instructions we are inserting look like.
125  // We need to keep the original loads for each argument and the elements
126  // of the argument that are accessed.
127  std::map<std::pair<Argument *, IndicesVector>, LoadInst *> OriginalLoads;
128 
129  // Attribute - Keep track of the parameter attributes for the arguments
130  // that we are *not* promoting. For the ones that we do promote, the parameter
131  // attributes are lost
132  SmallVector<AttributeSet, 8> ArgAttrVec;
133  AttributeList PAL = F->getAttributes();
134 
135  // First, determine the new argument list
136  unsigned ArgNo = 0;
137  for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E;
138  ++I, ++ArgNo) {
139  if (ByValArgsToTransform.count(&*I)) {
140  // Simple byval argument? Just add all the struct element types.
141  Type *AgTy = cast<PointerType>(I->getType())->getElementType();
142  StructType *STy = cast<StructType>(AgTy);
143  Params.insert(Params.end(), STy->element_begin(), STy->element_end());
144  ArgAttrVec.insert(ArgAttrVec.end(), STy->getNumElements(),
145  AttributeSet());
146  ++NumByValArgsPromoted;
147  } else if (!ArgsToPromote.count(&*I)) {
148  // Unchanged argument
149  Params.push_back(I->getType());
150  ArgAttrVec.push_back(PAL.getParamAttributes(ArgNo));
151  } else if (I->use_empty()) {
152  // Dead argument (which are always marked as promotable)
153  ++NumArgumentsDead;
154 
155  // There may be remaining metadata uses of the argument for things like
156  // llvm.dbg.value. Replace them with undef.
157  I->replaceAllUsesWith(UndefValue::get(I->getType()));
158  } else {
159  // Okay, this is being promoted. This means that the only uses are loads
160  // or GEPs which are only used by loads
161 
162  // In this table, we will track which indices are loaded from the argument
163  // (where direct loads are tracked as no indices).
164  ScalarizeTable &ArgIndices = ScalarizedElements[&*I];
165  for (User *U : I->users()) {
166  Instruction *UI = cast<Instruction>(U);
167  Type *SrcTy;
168  if (LoadInst *L = dyn_cast<LoadInst>(UI))
169  SrcTy = L->getType();
170  else
171  SrcTy = cast<GetElementPtrInst>(UI)->getSourceElementType();
172  IndicesVector Indices;
173  Indices.reserve(UI->getNumOperands() - 1);
174  // Since loads will only have a single operand, and GEPs only a single
175  // non-index operand, this will record direct loads without any indices,
176  // and gep+loads with the GEP indices.
177  for (User::op_iterator II = UI->op_begin() + 1, IE = UI->op_end();
178  II != IE; ++II)
179  Indices.push_back(cast<ConstantInt>(*II)->getSExtValue());
180  // GEPs with a single 0 index can be merged with direct loads
181  if (Indices.size() == 1 && Indices.front() == 0)
182  Indices.clear();
183  ArgIndices.insert(std::make_pair(SrcTy, Indices));
184  LoadInst *OrigLoad;
185  if (LoadInst *L = dyn_cast<LoadInst>(UI))
186  OrigLoad = L;
187  else
188  // Take any load, we will use it only to update Alias Analysis
189  OrigLoad = cast<LoadInst>(UI->user_back());
190  OriginalLoads[std::make_pair(&*I, Indices)] = OrigLoad;
191  }
192 
193  // Add a parameter to the function for each element passed in.
194  for (const auto &ArgIndex : ArgIndices) {
195  // not allowed to dereference ->begin() if size() is 0
196  Params.push_back(GetElementPtrInst::getIndexedType(
197  cast<PointerType>(I->getType()->getScalarType())->getElementType(),
198  ArgIndex.second));
199  ArgAttrVec.push_back(AttributeSet());
200  assert(Params.back());
201  }
202 
203  if (ArgIndices.size() == 1 && ArgIndices.begin()->second.empty())
204  ++NumArgumentsPromoted;
205  else
206  ++NumAggregatesPromoted;
207  }
208  }
209 
210  Type *RetTy = FTy->getReturnType();
211 
212  // Construct the new function type using the new arguments.
213  FunctionType *NFTy = FunctionType::get(RetTy, Params, FTy->isVarArg());
214 
215  // Create the new function body and insert it into the module.
216  Function *NF = Function::Create(NFTy, F->getLinkage(), F->getAddressSpace(),
217  F->getName());
218  NF->copyAttributesFrom(F);
219  NF->copyMetadata(F, 0);
220  F->clearMetadata();
221 
222  LLVM_DEBUG(dbgs() << "ARG PROMOTION: Promoting to:" << *NF << "\n"
223  << "From: " << *F);
224 
225  // Recompute the parameter attributes list based on the new arguments for
226  // the function.
227  NF->setAttributes(AttributeList::get(F->getContext(), PAL.getFnAttributes(),
228  PAL.getRetAttributes(), ArgAttrVec));
229  ArgAttrVec.clear();
230 
231  F->getParent()->getFunctionList().insert(F->getIterator(), NF);
232  NF->takeName(F);
233 
234  // Loop over all of the callers of the function, transforming the call sites
235  // to pass in the loaded pointers.
236  //
238  while (!F->use_empty()) {
239  CallSite CS(F->user_back());
240  assert(CS.getCalledFunction() == F);
241  Instruction *Call = CS.getInstruction();
242  const AttributeList &CallPAL = CS.getAttributes();
243 
244  // Loop over the operands, inserting GEP and loads in the caller as
245  // appropriate.
246  CallSite::arg_iterator AI = CS.arg_begin();
247  ArgNo = 0;
248  for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E;
249  ++I, ++AI, ++ArgNo)
250  if (!ArgsToPromote.count(&*I) && !ByValArgsToTransform.count(&*I)) {
251  Args.push_back(*AI); // Unmodified argument
252  ArgAttrVec.push_back(CallPAL.getParamAttributes(ArgNo));
253  } else if (ByValArgsToTransform.count(&*I)) {
254  // Emit a GEP and load for each element of the struct.
255  Type *AgTy = cast<PointerType>(I->getType())->getElementType();
256  StructType *STy = cast<StructType>(AgTy);
257  Value *Idxs[2] = {
258  ConstantInt::get(Type::getInt32Ty(F->getContext()), 0), nullptr};
259  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
260  Idxs[1] = ConstantInt::get(Type::getInt32Ty(F->getContext()), i);
262  STy, *AI, Idxs, (*AI)->getName() + "." + Twine(i), Call);
263  // TODO: Tell AA about the new values?
264  Args.push_back(new LoadInst(STy->getElementType(i), Idx,
265  Idx->getName() + ".val", Call));
266  ArgAttrVec.push_back(AttributeSet());
267  }
268  } else if (!I->use_empty()) {
269  // Non-dead argument: insert GEPs and loads as appropriate.
270  ScalarizeTable &ArgIndices = ScalarizedElements[&*I];
271  // Store the Value* version of the indices in here, but declare it now
272  // for reuse.
273  std::vector<Value *> Ops;
274  for (const auto &ArgIndex : ArgIndices) {
275  Value *V = *AI;
276  LoadInst *OrigLoad =
277  OriginalLoads[std::make_pair(&*I, ArgIndex.second)];
278  if (!ArgIndex.second.empty()) {
279  Ops.reserve(ArgIndex.second.size());
280  Type *ElTy = V->getType();
281  for (auto II : ArgIndex.second) {
282  // Use i32 to index structs, and i64 for others (pointers/arrays).
283  // This satisfies GEP constraints.
284  Type *IdxTy =
285  (ElTy->isStructTy() ? Type::getInt32Ty(F->getContext())
286  : Type::getInt64Ty(F->getContext()));
287  Ops.push_back(ConstantInt::get(IdxTy, II));
288  // Keep track of the type we're currently indexing.
289  if (auto *ElPTy = dyn_cast<PointerType>(ElTy))
290  ElTy = ElPTy->getElementType();
291  else
292  ElTy = cast<CompositeType>(ElTy)->getTypeAtIndex(II);
293  }
294  // And create a GEP to extract those indices.
295  V = GetElementPtrInst::Create(ArgIndex.first, V, Ops,
296  V->getName() + ".idx", Call);
297  Ops.clear();
298  }
299  // Since we're replacing a load make sure we take the alignment
300  // of the previous load.
301  LoadInst *newLoad =
302  new LoadInst(OrigLoad->getType(), V, V->getName() + ".val", Call);
303  newLoad->setAlignment(OrigLoad->getAlignment());
304  // Transfer the AA info too.
305  AAMDNodes AAInfo;
306  OrigLoad->getAAMetadata(AAInfo);
307  newLoad->setAAMetadata(AAInfo);
308 
309  Args.push_back(newLoad);
310  ArgAttrVec.push_back(AttributeSet());
311  }
312  }
313 
314  // Push any varargs arguments on the list.
315  for (; AI != CS.arg_end(); ++AI, ++ArgNo) {
316  Args.push_back(*AI);
317  ArgAttrVec.push_back(CallPAL.getParamAttributes(ArgNo));
318  }
319 
321  CS.getOperandBundlesAsDefs(OpBundles);
322 
323  CallSite NewCS;
324  if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
325  NewCS = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(),
326  Args, OpBundles, "", Call);
327  } else {
328  auto *NewCall = CallInst::Create(NF, Args, OpBundles, "", Call);
329  NewCall->setTailCallKind(cast<CallInst>(Call)->getTailCallKind());
330  NewCS = NewCall;
331  }
332  NewCS.setCallingConv(CS.getCallingConv());
333  NewCS.setAttributes(
335  CallPAL.getRetAttributes(), ArgAttrVec));
336  NewCS->setDebugLoc(Call->getDebugLoc());
337  uint64_t W;
338  if (Call->extractProfTotalWeight(W))
339  NewCS->setProfWeight(W);
340  Args.clear();
341  ArgAttrVec.clear();
342 
343  // Update the callgraph to know that the callsite has been transformed.
344  if (ReplaceCallSite)
345  (*ReplaceCallSite)(CS, NewCS);
346 
347  if (!Call->use_empty()) {
348  Call->replaceAllUsesWith(NewCS.getInstruction());
349  NewCS->takeName(Call);
350  }
351 
352  // Finally, remove the old call from the program, reducing the use-count of
353  // F.
354  Call->eraseFromParent();
355  }
356 
357  const DataLayout &DL = F->getParent()->getDataLayout();
358 
359  // Since we have now created the new function, splice the body of the old
360  // function right into the new function, leaving the old rotting hulk of the
361  // function empty.
362  NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList());
363 
364  // Loop over the argument list, transferring uses of the old arguments over to
365  // the new arguments, also transferring over the names as well.
366  for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(),
367  I2 = NF->arg_begin();
368  I != E; ++I) {
369  if (!ArgsToPromote.count(&*I) && !ByValArgsToTransform.count(&*I)) {
370  // If this is an unmodified argument, move the name and users over to the
371  // new version.
372  I->replaceAllUsesWith(&*I2);
373  I2->takeName(&*I);
374  ++I2;
375  continue;
376  }
377 
378  if (ByValArgsToTransform.count(&*I)) {
379  // In the callee, we create an alloca, and store each of the new incoming
380  // arguments into the alloca.
381  Instruction *InsertPt = &NF->begin()->front();
382 
383  // Just add all the struct element types.
384  Type *AgTy = cast<PointerType>(I->getType())->getElementType();
385  Value *TheAlloca = new AllocaInst(AgTy, DL.getAllocaAddrSpace(), nullptr,
386  I->getParamAlignment(), "", InsertPt);
387  StructType *STy = cast<StructType>(AgTy);
388  Value *Idxs[2] = {ConstantInt::get(Type::getInt32Ty(F->getContext()), 0),
389  nullptr};
390 
391  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
392  Idxs[1] = ConstantInt::get(Type::getInt32Ty(F->getContext()), i);
394  AgTy, TheAlloca, Idxs, TheAlloca->getName() + "." + Twine(i),
395  InsertPt);
396  I2->setName(I->getName() + "." + Twine(i));
397  new StoreInst(&*I2++, Idx, InsertPt);
398  }
399 
400  // Anything that used the arg should now use the alloca.
401  I->replaceAllUsesWith(TheAlloca);
402  TheAlloca->takeName(&*I);
403 
404  // If the alloca is used in a call, we must clear the tail flag since
405  // the callee now uses an alloca from the caller.
406  for (User *U : TheAlloca->users()) {
407  CallInst *Call = dyn_cast<CallInst>(U);
408  if (!Call)
409  continue;
410  Call->setTailCall(false);
411  }
412  continue;
413  }
414 
415  if (I->use_empty())
416  continue;
417 
418  // Otherwise, if we promoted this argument, then all users are load
419  // instructions (or GEPs with only load users), and all loads should be
420  // using the new argument that we added.
421  ScalarizeTable &ArgIndices = ScalarizedElements[&*I];
422 
423  while (!I->use_empty()) {
424  if (LoadInst *LI = dyn_cast<LoadInst>(I->user_back())) {
425  assert(ArgIndices.begin()->second.empty() &&
426  "Load element should sort to front!");
427  I2->setName(I->getName() + ".val");
428  LI->replaceAllUsesWith(&*I2);
429  LI->eraseFromParent();
430  LLVM_DEBUG(dbgs() << "*** Promoted load of argument '" << I->getName()
431  << "' in function '" << F->getName() << "'\n");
432  } else {
433  GetElementPtrInst *GEP = cast<GetElementPtrInst>(I->user_back());
434  IndicesVector Operands;
435  Operands.reserve(GEP->getNumIndices());
436  for (User::op_iterator II = GEP->idx_begin(), IE = GEP->idx_end();
437  II != IE; ++II)
438  Operands.push_back(cast<ConstantInt>(*II)->getSExtValue());
439 
440  // GEPs with a single 0 index can be merged with direct loads
441  if (Operands.size() == 1 && Operands.front() == 0)
442  Operands.clear();
443 
444  Function::arg_iterator TheArg = I2;
445  for (ScalarizeTable::iterator It = ArgIndices.begin();
446  It->second != Operands; ++It, ++TheArg) {
447  assert(It != ArgIndices.end() && "GEP not handled??");
448  }
449 
450  std::string NewName = I->getName();
451  for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
452  NewName += "." + utostr(Operands[i]);
453  }
454  NewName += ".val";
455  TheArg->setName(NewName);
456 
457  LLVM_DEBUG(dbgs() << "*** Promoted agg argument '" << TheArg->getName()
458  << "' of function '" << NF->getName() << "'\n");
459 
460  // All of the uses must be load instructions. Replace them all with
461  // the argument specified by ArgNo.
462  while (!GEP->use_empty()) {
463  LoadInst *L = cast<LoadInst>(GEP->user_back());
464  L->replaceAllUsesWith(&*TheArg);
465  L->eraseFromParent();
466  }
467  GEP->eraseFromParent();
468  }
469  }
470 
471  // Increment I2 past all of the arguments added for this promoted pointer.
472  std::advance(I2, ArgIndices.size());
473  }
474 
475  assert(F->isDeclaration());
476  return NF;
477 }
478 
479 /// AllCallersPassInValidPointerForArgument - Return true if we can prove that
480 /// all callees pass in a valid pointer for the specified function argument.
482  Function *Callee = Arg->getParent();
483  const DataLayout &DL = Callee->getParent()->getDataLayout();
484 
485  unsigned ArgNo = Arg->getArgNo();
486 
487  // Look at all call sites of the function. At this point we know we only have
488  // direct callees.
489  for (User *U : Callee->users()) {
490  CallSite CS(U);
491  assert(CS && "Should only have direct calls!");
492 
493  if (!isDereferenceablePointer(CS.getArgument(ArgNo), DL))
494  return false;
495  }
496  return true;
497 }
498 
499 /// Returns true if Prefix is a prefix of longer. That means, Longer has a size
500 /// that is greater than or equal to the size of prefix, and each of the
501 /// elements in Prefix is the same as the corresponding elements in Longer.
502 ///
503 /// This means it also returns true when Prefix and Longer are equal!
504 static bool isPrefix(const IndicesVector &Prefix, const IndicesVector &Longer) {
505  if (Prefix.size() > Longer.size())
506  return false;
507  return std::equal(Prefix.begin(), Prefix.end(), Longer.begin());
508 }
509 
510 /// Checks if Indices, or a prefix of Indices, is in Set.
511 static bool prefixIn(const IndicesVector &Indices,
512  std::set<IndicesVector> &Set) {
513  std::set<IndicesVector>::iterator Low;
514  Low = Set.upper_bound(Indices);
515  if (Low != Set.begin())
516  Low--;
517  // Low is now the last element smaller than or equal to Indices. This means
518  // it points to a prefix of Indices (possibly Indices itself), if such
519  // prefix exists.
520  //
521  // This load is safe if any prefix of its operands is safe to load.
522  return Low != Set.end() && isPrefix(*Low, Indices);
523 }
524 
525 /// Mark the given indices (ToMark) as safe in the given set of indices
526 /// (Safe). Marking safe usually means adding ToMark to Safe. However, if there
527 /// is already a prefix of Indices in Safe, Indices are implicitely marked safe
528 /// already. Furthermore, any indices that Indices is itself a prefix of, are
529 /// removed from Safe (since they are implicitely safe because of Indices now).
530 static void markIndicesSafe(const IndicesVector &ToMark,
531  std::set<IndicesVector> &Safe) {
532  std::set<IndicesVector>::iterator Low;
533  Low = Safe.upper_bound(ToMark);
534  // Guard against the case where Safe is empty
535  if (Low != Safe.begin())
536  Low--;
537  // Low is now the last element smaller than or equal to Indices. This
538  // means it points to a prefix of Indices (possibly Indices itself), if
539  // such prefix exists.
540  if (Low != Safe.end()) {
541  if (isPrefix(*Low, ToMark))
542  // If there is already a prefix of these indices (or exactly these
543  // indices) marked a safe, don't bother adding these indices
544  return;
545 
546  // Increment Low, so we can use it as a "insert before" hint
547  ++Low;
548  }
549  // Insert
550  Low = Safe.insert(Low, ToMark);
551  ++Low;
552  // If there we're a prefix of longer index list(s), remove those
553  std::set<IndicesVector>::iterator End = Safe.end();
554  while (Low != End && isPrefix(ToMark, *Low)) {
555  std::set<IndicesVector>::iterator Remove = Low;
556  ++Low;
557  Safe.erase(Remove);
558  }
559 }
560 
561 /// isSafeToPromoteArgument - As you might guess from the name of this method,
562 /// it checks to see if it is both safe and useful to promote the argument.
563 /// This method limits promotion of aggregates to only promote up to three
564 /// elements of the aggregate in order to avoid exploding the number of
565 /// arguments passed in.
566 static bool isSafeToPromoteArgument(Argument *Arg, bool isByValOrInAlloca,
567  AAResults &AAR, unsigned MaxElements) {
568  using GEPIndicesSet = std::set<IndicesVector>;
569 
570  // Quick exit for unused arguments
571  if (Arg->use_empty())
572  return true;
573 
574  // We can only promote this argument if all of the uses are loads, or are GEP
575  // instructions (with constant indices) that are subsequently loaded.
576  //
577  // Promoting the argument causes it to be loaded in the caller
578  // unconditionally. This is only safe if we can prove that either the load
579  // would have happened in the callee anyway (ie, there is a load in the entry
580  // block) or the pointer passed in at every call site is guaranteed to be
581  // valid.
582  // In the former case, invalid loads can happen, but would have happened
583  // anyway, in the latter case, invalid loads won't happen. This prevents us
584  // from introducing an invalid load that wouldn't have happened in the
585  // original code.
586  //
587  // This set will contain all sets of indices that are loaded in the entry
588  // block, and thus are safe to unconditionally load in the caller.
589  //
590  // This optimization is also safe for InAlloca parameters, because it verifies
591  // that the address isn't captured.
592  GEPIndicesSet SafeToUnconditionallyLoad;
593 
594  // This set contains all the sets of indices that we are planning to promote.
595  // This makes it possible to limit the number of arguments added.
596  GEPIndicesSet ToPromote;
597 
598  // If the pointer is always valid, any load with first index 0 is valid.
599  if (isByValOrInAlloca || allCallersPassInValidPointerForArgument(Arg))
600  SafeToUnconditionallyLoad.insert(IndicesVector(1, 0));
601 
602  // First, iterate the entry block and mark loads of (geps of) arguments as
603  // safe.
604  BasicBlock &EntryBlock = Arg->getParent()->front();
605  // Declare this here so we can reuse it
606  IndicesVector Indices;
607  for (Instruction &I : EntryBlock)
608  if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
609  Value *V = LI->getPointerOperand();
610  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V)) {
611  V = GEP->getPointerOperand();
612  if (V == Arg) {
613  // This load actually loads (part of) Arg? Check the indices then.
614  Indices.reserve(GEP->getNumIndices());
615  for (User::op_iterator II = GEP->idx_begin(), IE = GEP->idx_end();
616  II != IE; ++II)
617  if (ConstantInt *CI = dyn_cast<ConstantInt>(*II))
618  Indices.push_back(CI->getSExtValue());
619  else
620  // We found a non-constant GEP index for this argument? Bail out
621  // right away, can't promote this argument at all.
622  return false;
623 
624  // Indices checked out, mark them as safe
625  markIndicesSafe(Indices, SafeToUnconditionallyLoad);
626  Indices.clear();
627  }
628  } else if (V == Arg) {
629  // Direct loads are equivalent to a GEP with a single 0 index.
630  markIndicesSafe(IndicesVector(1, 0), SafeToUnconditionallyLoad);
631  }
632  }
633 
634  // Now, iterate all uses of the argument to see if there are any uses that are
635  // not (GEP+)loads, or any (GEP+)loads that are not safe to promote.
637  IndicesVector Operands;
638  for (Use &U : Arg->uses()) {
639  User *UR = U.getUser();
640  Operands.clear();
641  if (LoadInst *LI = dyn_cast<LoadInst>(UR)) {
642  // Don't hack volatile/atomic loads
643  if (!LI->isSimple())
644  return false;
645  Loads.push_back(LI);
646  // Direct loads are equivalent to a GEP with a zero index and then a load.
647  Operands.push_back(0);
648  } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(UR)) {
649  if (GEP->use_empty()) {
650  // Dead GEP's cause trouble later. Just remove them if we run into
651  // them.
652  GEP->eraseFromParent();
653  // TODO: This runs the above loop over and over again for dead GEPs
654  // Couldn't we just do increment the UI iterator earlier and erase the
655  // use?
656  return isSafeToPromoteArgument(Arg, isByValOrInAlloca, AAR,
657  MaxElements);
658  }
659 
660  // Ensure that all of the indices are constants.
661  for (User::op_iterator i = GEP->idx_begin(), e = GEP->idx_end(); i != e;
662  ++i)
663  if (ConstantInt *C = dyn_cast<ConstantInt>(*i))
664  Operands.push_back(C->getSExtValue());
665  else
666  return false; // Not a constant operand GEP!
667 
668  // Ensure that the only users of the GEP are load instructions.
669  for (User *GEPU : GEP->users())
670  if (LoadInst *LI = dyn_cast<LoadInst>(GEPU)) {
671  // Don't hack volatile/atomic loads
672  if (!LI->isSimple())
673  return false;
674  Loads.push_back(LI);
675  } else {
676  // Other uses than load?
677  return false;
678  }
679  } else {
680  return false; // Not a load or a GEP.
681  }
682 
683  // Now, see if it is safe to promote this load / loads of this GEP. Loading
684  // is safe if Operands, or a prefix of Operands, is marked as safe.
685  if (!prefixIn(Operands, SafeToUnconditionallyLoad))
686  return false;
687 
688  // See if we are already promoting a load with these indices. If not, check
689  // to make sure that we aren't promoting too many elements. If so, nothing
690  // to do.
691  if (ToPromote.find(Operands) == ToPromote.end()) {
692  if (MaxElements > 0 && ToPromote.size() == MaxElements) {
693  LLVM_DEBUG(dbgs() << "argpromotion not promoting argument '"
694  << Arg->getName()
695  << "' because it would require adding more "
696  << "than " << MaxElements
697  << " arguments to the function.\n");
698  // We limit aggregate promotion to only promoting up to a fixed number
699  // of elements of the aggregate.
700  return false;
701  }
702  ToPromote.insert(std::move(Operands));
703  }
704  }
705 
706  if (Loads.empty())
707  return true; // No users, this is a dead argument.
708 
709  // Okay, now we know that the argument is only used by load instructions and
710  // it is safe to unconditionally perform all of them. Use alias analysis to
711  // check to see if the pointer is guaranteed to not be modified from entry of
712  // the function to each of the load instructions.
713 
714  // Because there could be several/many load instructions, remember which
715  // blocks we know to be transparent to the load.
717 
718  for (LoadInst *Load : Loads) {
719  // Check to see if the load is invalidated from the start of the block to
720  // the load itself.
721  BasicBlock *BB = Load->getParent();
722 
724  if (AAR.canInstructionRangeModRef(BB->front(), *Load, Loc, ModRefInfo::Mod))
725  return false; // Pointer is invalidated!
726 
727  // Now check every path from the entry block to the load for transparency.
728  // To do this, we perform a depth first search on the inverse CFG from the
729  // loading block.
730  for (BasicBlock *P : predecessors(BB)) {
731  for (BasicBlock *TranspBB : inverse_depth_first_ext(P, TranspBlocks))
732  if (AAR.canBasicBlockModify(*TranspBB, Loc))
733  return false;
734  }
735  }
736 
737  // If the path from the entry of the function to each load is free of
738  // instructions that potentially invalidate the load, we can make the
739  // transformation!
740  return true;
741 }
742 
743 /// Checks if a type could have padding bytes.
744 static bool isDenselyPacked(Type *type, const DataLayout &DL) {
745  // There is no size information, so be conservative.
746  if (!type->isSized())
747  return false;
748 
749  // If the alloc size is not equal to the storage size, then there are padding
750  // bytes. For x86_fp80 on x86-64, size: 80 alloc size: 128.
751  if (DL.getTypeSizeInBits(type) != DL.getTypeAllocSizeInBits(type))
752  return false;
753 
754  if (!isa<CompositeType>(type))
755  return true;
756 
757  // For homogenous sequential types, check for padding within members.
758  if (SequentialType *seqTy = dyn_cast<SequentialType>(type))
759  return isDenselyPacked(seqTy->getElementType(), DL);
760 
761  // Check for padding within and between elements of a struct.
762  StructType *StructTy = cast<StructType>(type);
763  const StructLayout *Layout = DL.getStructLayout(StructTy);
764  uint64_t StartPos = 0;
765  for (unsigned i = 0, E = StructTy->getNumElements(); i < E; ++i) {
766  Type *ElTy = StructTy->getElementType(i);
767  if (!isDenselyPacked(ElTy, DL))
768  return false;
769  if (StartPos != Layout->getElementOffsetInBits(i))
770  return false;
771  StartPos += DL.getTypeAllocSizeInBits(ElTy);
772  }
773 
774  return true;
775 }
776 
777 /// Checks if the padding bytes of an argument could be accessed.
778 static bool canPaddingBeAccessed(Argument *arg) {
779  assert(arg->hasByValAttr());
780 
781  // Track all the pointers to the argument to make sure they are not captured.
782  SmallPtrSet<Value *, 16> PtrValues;
783  PtrValues.insert(arg);
784 
785  // Track all of the stores.
787 
788  // Scan through the uses recursively to make sure the pointer is always used
789  // sanely.
790  SmallVector<Value *, 16> WorkList;
791  WorkList.insert(WorkList.end(), arg->user_begin(), arg->user_end());
792  while (!WorkList.empty()) {
793  Value *V = WorkList.back();
794  WorkList.pop_back();
795  if (isa<GetElementPtrInst>(V) || isa<PHINode>(V)) {
796  if (PtrValues.insert(V).second)
797  WorkList.insert(WorkList.end(), V->user_begin(), V->user_end());
798  } else if (StoreInst *Store = dyn_cast<StoreInst>(V)) {
799  Stores.push_back(Store);
800  } else if (!isa<LoadInst>(V)) {
801  return true;
802  }
803  }
804 
805  // Check to make sure the pointers aren't captured
806  for (StoreInst *Store : Stores)
807  if (PtrValues.count(Store->getValueOperand()))
808  return true;
809 
810  return false;
811 }
812 
814  const Function &F, const TargetTransformInfo &TTI,
815  SmallPtrSetImpl<Argument *> &ArgsToPromote,
816  SmallPtrSetImpl<Argument *> &ByValArgsToTransform) {
817  for (const Use &U : F.uses()) {
818  CallSite CS(U.getUser());
819  const Function *Caller = CS.getCaller();
820  const Function *Callee = CS.getCalledFunction();
821  if (!TTI.areFunctionArgsABICompatible(Caller, Callee, ArgsToPromote) ||
822  !TTI.areFunctionArgsABICompatible(Caller, Callee, ByValArgsToTransform))
823  return false;
824  }
825  return true;
826 }
827 
828 /// PromoteArguments - This method checks the specified function to see if there
829 /// are any promotable arguments and if it is safe to promote the function (for
830 /// example, all callers are direct). If safe to promote some arguments, it
831 /// calls the DoPromotion method.
832 static Function *
834  unsigned MaxElements,
835  Optional<function_ref<void(CallSite OldCS, CallSite NewCS)>>
836  ReplaceCallSite,
837  const TargetTransformInfo &TTI) {
838  // Don't perform argument promotion for naked functions; otherwise we can end
839  // up removing parameters that are seemingly 'not used' as they are referred
840  // to in the assembly.
841  if(F->hasFnAttribute(Attribute::Naked))
842  return nullptr;
843 
844  // Make sure that it is local to this module.
845  if (!F->hasLocalLinkage())
846  return nullptr;
847 
848  // Don't promote arguments for variadic functions. Adding, removing, or
849  // changing non-pack parameters can change the classification of pack
850  // parameters. Frontends encode that classification at the call site in the
851  // IR, while in the callee the classification is determined dynamically based
852  // on the number of registers consumed so far.
853  if (F->isVarArg())
854  return nullptr;
855 
856  // First check: see if there are any pointer arguments! If not, quick exit.
857  SmallVector<Argument *, 16> PointerArgs;
858  for (Argument &I : F->args())
859  if (I.getType()->isPointerTy())
860  PointerArgs.push_back(&I);
861  if (PointerArgs.empty())
862  return nullptr;
863 
864  // Second check: make sure that all callers are direct callers. We can't
865  // transform functions that have indirect callers. Also see if the function
866  // is self-recursive and check that target features are compatible.
867  bool isSelfRecursive = false;
868  for (Use &U : F->uses()) {
869  CallSite CS(U.getUser());
870  // Must be a direct call.
871  if (CS.getInstruction() == nullptr || !CS.isCallee(&U))
872  return nullptr;
873 
874  // Can't change signature of musttail callee
875  if (CS.isMustTailCall())
876  return nullptr;
877 
878  if (CS.getInstruction()->getParent()->getParent() == F)
879  isSelfRecursive = true;
880  }
881 
882  // Can't change signature of musttail caller
883  // FIXME: Support promoting whole chain of musttail functions
884  for (BasicBlock &BB : *F)
885  if (BB.getTerminatingMustTailCall())
886  return nullptr;
887 
888  const DataLayout &DL = F->getParent()->getDataLayout();
889 
890  AAResults &AAR = AARGetter(*F);
891 
892  // Check to see which arguments are promotable. If an argument is promotable,
893  // add it to ArgsToPromote.
894  SmallPtrSet<Argument *, 8> ArgsToPromote;
895  SmallPtrSet<Argument *, 8> ByValArgsToTransform;
896  for (Argument *PtrArg : PointerArgs) {
897  Type *AgTy = cast<PointerType>(PtrArg->getType())->getElementType();
898 
899  // Replace sret attribute with noalias. This reduces register pressure by
900  // avoiding a register copy.
901  if (PtrArg->hasStructRetAttr()) {
902  unsigned ArgNo = PtrArg->getArgNo();
903  F->removeParamAttr(ArgNo, Attribute::StructRet);
904  F->addParamAttr(ArgNo, Attribute::NoAlias);
905  for (Use &U : F->uses()) {
906  CallSite CS(U.getUser());
907  CS.removeParamAttr(ArgNo, Attribute::StructRet);
908  CS.addParamAttr(ArgNo, Attribute::NoAlias);
909  }
910  }
911 
912  // If this is a byval argument, and if the aggregate type is small, just
913  // pass the elements, which is always safe, if the passed value is densely
914  // packed or if we can prove the padding bytes are never accessed. This does
915  // not apply to inalloca.
916  bool isSafeToPromote =
917  PtrArg->hasByValAttr() &&
918  (isDenselyPacked(AgTy, DL) || !canPaddingBeAccessed(PtrArg));
919  if (isSafeToPromote) {
920  if (StructType *STy = dyn_cast<StructType>(AgTy)) {
921  if (MaxElements > 0 && STy->getNumElements() > MaxElements) {
922  LLVM_DEBUG(dbgs() << "argpromotion disable promoting argument '"
923  << PtrArg->getName()
924  << "' because it would require adding more"
925  << " than " << MaxElements
926  << " arguments to the function.\n");
927  continue;
928  }
929 
930  // If all the elements are single-value types, we can promote it.
931  bool AllSimple = true;
932  for (const auto *EltTy : STy->elements()) {
933  if (!EltTy->isSingleValueType()) {
934  AllSimple = false;
935  break;
936  }
937  }
938 
939  // Safe to transform, don't even bother trying to "promote" it.
940  // Passing the elements as a scalar will allow sroa to hack on
941  // the new alloca we introduce.
942  if (AllSimple) {
943  ByValArgsToTransform.insert(PtrArg);
944  continue;
945  }
946  }
947  }
948 
949  // If the argument is a recursive type and we're in a recursive
950  // function, we could end up infinitely peeling the function argument.
951  if (isSelfRecursive) {
952  if (StructType *STy = dyn_cast<StructType>(AgTy)) {
953  bool RecursiveType = false;
954  for (const auto *EltTy : STy->elements()) {
955  if (EltTy == PtrArg->getType()) {
956  RecursiveType = true;
957  break;
958  }
959  }
960  if (RecursiveType)
961  continue;
962  }
963  }
964 
965  // Otherwise, see if we can promote the pointer to its value.
966  if (isSafeToPromoteArgument(PtrArg, PtrArg->hasByValOrInAllocaAttr(), AAR,
967  MaxElements))
968  ArgsToPromote.insert(PtrArg);
969  }
970 
971  // No promotable pointer arguments.
972  if (ArgsToPromote.empty() && ByValArgsToTransform.empty())
973  return nullptr;
974 
975  if (!areFunctionArgsABICompatible(*F, TTI, ArgsToPromote,
976  ByValArgsToTransform))
977  return nullptr;
978 
979  return doPromotion(F, ArgsToPromote, ByValArgsToTransform, ReplaceCallSite);
980 }
981 
984  LazyCallGraph &CG,
985  CGSCCUpdateResult &UR) {
986  bool Changed = false, LocalChange;
987 
988  // Iterate until we stop promoting from this SCC.
989  do {
990  LocalChange = false;
991 
992  for (LazyCallGraph::Node &N : C) {
993  Function &OldF = N.getFunction();
994 
996  AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
997  // FIXME: This lambda must only be used with this function. We should
998  // skip the lambda and just get the AA results directly.
999  auto AARGetter = [&](Function &F) -> AAResults & {
1000  assert(&F == &OldF && "Called with an unexpected function!");
1001  return FAM.getResult<AAManager>(F);
1002  };
1003 
1004  const TargetTransformInfo &TTI = FAM.getResult<TargetIRAnalysis>(OldF);
1005  Function *NewF =
1006  promoteArguments(&OldF, AARGetter, MaxElements, None, TTI);
1007  if (!NewF)
1008  continue;
1009  LocalChange = true;
1010 
1011  // Directly substitute the functions in the call graph. Note that this
1012  // requires the old function to be completely dead and completely
1013  // replaced by the new function. It does no call graph updates, it merely
1014  // swaps out the particular function mapped to a particular node in the
1015  // graph.
1016  C.getOuterRefSCC().replaceNodeFunction(N, *NewF);
1017  OldF.eraseFromParent();
1018  }
1019 
1020  Changed |= LocalChange;
1021  } while (LocalChange);
1022 
1023  if (!Changed)
1024  return PreservedAnalyses::all();
1025 
1026  return PreservedAnalyses::none();
1027 }
1028 
1029 namespace {
1030 
1031 /// ArgPromotion - The 'by reference' to 'by value' argument promotion pass.
1032 struct ArgPromotion : public CallGraphSCCPass {
1033  // Pass identification, replacement for typeid
1034  static char ID;
1035 
1036  explicit ArgPromotion(unsigned MaxElements = 3)
1037  : CallGraphSCCPass(ID), MaxElements(MaxElements) {
1039  }
1040 
1041  void getAnalysisUsage(AnalysisUsage &AU) const override {
1047  }
1048 
1049  bool runOnSCC(CallGraphSCC &SCC) override;
1050 
1051 private:
1053 
1054  bool doInitialization(CallGraph &CG) override;
1055 
1056  /// The maximum number of elements to expand, or 0 for unlimited.
1057  unsigned MaxElements;
1058 };
1059 
1060 } // end anonymous namespace
1061 
1062 char ArgPromotion::ID = 0;
1063 
1064 INITIALIZE_PASS_BEGIN(ArgPromotion, "argpromotion",
1065  "Promote 'by reference' arguments to scalars", false,
1066  false)
1072  "Promote 'by reference' arguments to scalars", false, false)
1073 
1074 Pass *llvm::createArgumentPromotionPass(unsigned MaxElements) {
1075  return new ArgPromotion(MaxElements);
1076 }
1077 
1078 bool ArgPromotion::runOnSCC(CallGraphSCC &SCC) {
1079  if (skipSCC(SCC))
1080  return false;
1081 
1082  // Get the callgraph information that we need to update to reflect our
1083  // changes.
1084  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
1085 
1086  LegacyAARGetter AARGetter(*this);
1087 
1088  bool Changed = false, LocalChange;
1089 
1090  // Iterate until we stop promoting from this SCC.
1091  do {
1092  LocalChange = false;
1093  // Attempt to promote arguments from all functions in this SCC.
1094  for (CallGraphNode *OldNode : SCC) {
1095  Function *OldF = OldNode->getFunction();
1096  if (!OldF)
1097  continue;
1098 
1099  auto ReplaceCallSite = [&](CallSite OldCS, CallSite NewCS) {
1100  Function *Caller = OldCS.getInstruction()->getParent()->getParent();
1101  CallGraphNode *NewCalleeNode =
1102  CG.getOrInsertFunction(NewCS.getCalledFunction());
1103  CallGraphNode *CallerNode = CG[Caller];
1104  CallerNode->replaceCallEdge(OldCS, NewCS, NewCalleeNode);
1105  };
1106 
1107  const TargetTransformInfo &TTI =
1108  getAnalysis<TargetTransformInfoWrapperPass>().getTTI(*OldF);
1109  if (Function *NewF = promoteArguments(OldF, AARGetter, MaxElements,
1110  {ReplaceCallSite}, TTI)) {
1111  LocalChange = true;
1112 
1113  // Update the call graph for the newly promoted function.
1114  CallGraphNode *NewNode = CG.getOrInsertFunction(NewF);
1115  NewNode->stealCalledFunctionsFrom(OldNode);
1116  if (OldNode->getNumReferences() == 0)
1117  delete CG.removeFunctionFromModule(OldNode);
1118  else
1120 
1121  // And updat ethe SCC we're iterating as well.
1122  SCC.ReplaceNode(OldNode, NewNode);
1123  }
1124  }
1125  // Remember that we changed something.
1126  Changed |= LocalChange;
1127  } while (LocalChange);
1128 
1129  return Changed;
1130 }
1131 
1132 bool ArgPromotion::doInitialization(CallGraph &CG) {
1134 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
const Function & getFunction() const
Definition: Function.h:133
bool isVarArg() const
isVarArg - Return true if this function takes a variable number of arguments.
Definition: Function.h:176
uint64_t CallInst * C
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:110
iterator_range< use_iterator > uses()
Definition: Value.h:354
bool hasLocalLinkage() const
Definition: GlobalValue.h:435
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Type * getElementType(unsigned N) const
Definition: DerivedTypes.h:345
void setAttributes(AttributeList PAL)
Set the parameter attributes of the call.
Definition: CallSite.h:341
bool isSized(SmallPtrSetImpl< Type *> *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:264
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
unsigned getNumElements() const
Random access to the elements.
Definition: DerivedTypes.h:344
const StructLayout * getStructLayout(StructType *Ty) const
Returns a StructLayout object, indicating the alignment of the struct, its size, and the offsets of i...
Definition: DataLayout.cpp:587
Implements a lazy call graph analysis and related passes for the new pass manager.
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value *> IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:899
This class represents a function call, abstracting a target machine&#39;s calling convention.
This file contains the declarations for metadata subclasses.
An immutable pass that tracks lazily created AssumptionCache objects.
virtual bool doInitialization(CallGraph &CG)
doInitialization - This method is called before the SCC&#39;s of the program has been processed...
The two locations do not alias at all.
Definition: AliasAnalysis.h:83
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:116
static bool isDenselyPacked(Type *type, const DataLayout &DL)
Checks if a type could have padding bytes.
Analysis pass providing the TargetTransformInfo.
void setCallingConv(CallingConv::ID CC)
Set the calling convention of the call.
Definition: CallSite.h:324
Externally visible function.
Definition: GlobalValue.h:48
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:320
arg_iterator arg_end()
Definition: Function.h:679
iterator_range< idf_ext_iterator< T, SetTy > > inverse_depth_first_ext(const T &G, SetTy &S)
STATISTIC(NumFunctions, "Total number of functions")
F(f)
An instruction for reading from memory.
Definition: Instructions.h:167
static IntegerType * getInt64Ty(LLVMContext &C)
Definition: Type.cpp:176
Hexagon Common GEP
This defines the Use class.
bool hasByValAttr() const
Return true if this argument has the byval attribute.
Definition: Function.cpp:86
A proxy from a FunctionAnalysisManager to an SCC.
A node in the call graph for a module.
Definition: CallGraph.h:164
void getAnalysisUsage(AnalysisUsage &Info) const override
getAnalysisUsage - For this class, we declare that we require and preserve the call graph...
op_iterator op_begin()
Definition: User.h:229
Support structure for SCC passes to communicate updates the call graph back to the CGSCC pass manager...
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
static bool prefixIn(const IndicesVector &Indices, std::set< IndicesVector > &Set)
Checks if Indices, or a prefix of Indices, is in Set.
unsigned getAllocaAddrSpace() const
Definition: DataLayout.h:257
static bool areFunctionArgsABICompatible(const Function &F, const TargetTransformInfo &TTI, SmallPtrSetImpl< Argument *> &ArgsToPromote, SmallPtrSetImpl< Argument *> &ByValArgsToTransform)
AnalysisUsage & addRequired()
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
Definition: DataLayout.h:531
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
Promote by reference arguments to scalars
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
Class to represent struct types.
Definition: DerivedTypes.h:232
void replaceCallEdge(CallSite CS, CallSite NewCS, CallGraphNode *NewNode)
Replaces the edge in the node for the specified call site with a new one.
Definition: CallGraph.cpp:230
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
void initializeArgPromotionPass(PassRegistry &)
This class is a functor to be used in legacy module or SCC passes for computing AA results for a func...
This file contains the simple types necessary to represent the attributes associated with functions a...
Pass * createArgumentPromotionPass(unsigned maxElements=3)
createArgumentPromotionPass - This pass promotes "by reference" arguments to be passed by value if th...
Function * removeFunctionFromModule(CallGraphNode *CGN)
Unlink the function from this module, returning it.
Definition: CallGraph.cpp:121
AttributeSet getRetAttributes() const
The attributes for the ret value are returned.
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:285
InstrTy * getInstruction() const
Definition: CallSite.h:96
unsigned getNumIndices() const
This file provides interfaces used to build and manipulate a call graph, which is a very useful tool ...
Class to represent function types.
Definition: DerivedTypes.h:102
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
static bool isSafeToPromoteArgument(Argument *Arg, bool isByValOrInAlloca, AAResults &AAR, unsigned MaxElements)
isSafeToPromoteArgument - As you might guess from the name of this method, it checks to see if it is ...
AttributeSet getParamAttributes(unsigned ArgNo) const
The attributes for the argument or parameter at the given index are returned.
bool isVarArg() const
Definition: DerivedTypes.h:122
A lazily constructed view of the call graph of a module.
op_iterator idx_begin()
Definition: Instructions.h:998
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:223
An instruction for storing to memory.
Definition: Instructions.h:320
LinkageTypes getLinkage() const
Definition: GlobalValue.h:450
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:291
virtual bool doInitialization(Module &)
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
Definition: Pass.h:105
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:156
AttributeSet getAttributes(unsigned Index) const
The attributes for the specified index are returned.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:873
void getAAMetadata(AAMDNodes &N, bool Merge=false) const
Fills the AAMDNodes structure with AA metadata from this instruction.
#define P(N)
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:135
Wrapper pass for TargetTransformInfo.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
The ModulePass which wraps up a CallGraph and the logic to build it.
Definition: CallGraph.h:323
void setAAMetadata(const AAMDNodes &N)
Sets the metadata on this instruction from the AAMDNodes structure.
Definition: Metadata.cpp:1264
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
const FunctionListType & getFunctionList() const
Get the Module&#39;s list of functions (constant).
Definition: Module.h:532
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, const MemoryLocation &Loc, const ModRefInfo Mode)
Check if it is possible for the execution of the specified instructions to mod(according to the mode)...
void stealCalledFunctionsFrom(CallGraphNode *N)
Moves all the callee information from N to this node.
Definition: CallGraph.h:225
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
void copyAttributesFrom(const Function *Src)
copyAttributesFrom - copy all additional attributes (those not needed to create a Function) from the ...
Definition: Function.cpp:483
void removeParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
Definition: CallSite.h:365
This file contains the declarations for the subclasses of Constant, which represent the different fla...
const Instruction & front() const
Definition: BasicBlock.h:280
A manager for alias analyses.
ValTy * getArgument(unsigned ArgNo) const
Definition: CallSite.h:193
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
element_iterator element_end() const
Definition: DerivedTypes.h:335
INITIALIZE_PASS_BEGIN(ArgPromotion, "argpromotion", "Promote 'by reference' arguments to scalars", false, false) INITIALIZE_PASS_END(ArgPromotion
static Function * doPromotion(Function *F, SmallPtrSetImpl< Argument *> &ArgsToPromote, SmallPtrSetImpl< Argument *> &ByValArgsToTransform, Optional< function_ref< void(CallSite OldCS, CallSite NewCS)>> ReplaceCallSite)
DoPromotion - This method actually performs the promotion of the specified arguments, and returns the new function.
Represent the analysis usage information of a pass.
op_iterator op_end()
Definition: User.h:231
static bool canPaddingBeAccessed(Argument *arg)
Checks if the padding bytes of an argument could be accessed.
unsigned getAddressSpace() const
Definition: Globals.cpp:110
StringRef getName() const
Return the name for this struct type if it has an identity.
Definition: Type.cpp:499
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
static bool allCallersPassInValidPointerForArgument(Argument *Arg)
AllCallersPassInValidPointerForArgument - Return true if we can prove that all callees pass in a vali...
static FunctionType * get(Type *Result, ArrayRef< Type *> Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
Definition: Type.cpp:296
A node in the call graph.
arg_iterator arg_begin()
Definition: Function.h:670
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
self_iterator getIterator()
Definition: ilist_node.h:81
void setAlignment(unsigned Align)
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:192
void setTailCall(bool isTC=true)
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1414
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
bool areFunctionArgsABICompatible(const Function *Caller, const Function *Callee, SmallPtrSetImpl< Argument *> &Args) const
void getAAResultsAnalysisUsage(AnalysisUsage &AU)
A helper for the legacy pass manager to populate AU to add uses to make sure the analyses required by...
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Representation for a specific memory location.
This is the superclass of the array and vector type classes.
Definition: DerivedTypes.h:374
unsigned getNumOperands() const
Definition: User.h:191
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
std::vector< uint64_t > IndicesVector
A vector used to hold the indices of a single GEP instruction.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:839
Module.h This file contains the declarations for the Module class.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
Definition: Instruction.h:63
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:643
Type * getReturnType() const
Definition: DerivedTypes.h:123
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:621
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:124
std::string utostr(uint64_t X, bool isNeg=false)
Definition: StringExtras.h:223
User::op_iterator arg_iterator
The type of iterator to use when looping over actual arguments at this call site. ...
Definition: CallSite.h:220
static bool isPrefix(const IndicesVector &Prefix, const IndicesVector &Longer)
Returns true if Prefix is a prefix of longer.
void setLinkage(LinkageTypes LT)
Definition: GlobalValue.h:444
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
The access may modify the value stored in memory.
FunctionType * getFunctionType() const
Returns the FunctionType for me.
Definition: Function.h:163
amdgpu Simplify well known AMD library false FunctionCallee Callee
unsigned getArgNo() const
Return the index of this formal argument in its containing function.
Definition: Argument.h:47
iterator_range< user_iterator > users()
Definition: Value.h:399
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:470
element_iterator element_begin() const
Definition: DerivedTypes.h:334
uint64_t getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:570
bool isDereferenceablePointer(const Value *V, const DataLayout &DL, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr)
Return true if this is always a dereferenceable pointer.
Definition: Loads.cpp:152
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:73
iterator insert(iterator where, pointer New)
Definition: ilist.h:226
const Function * getParent() const
Definition: Argument.h:41
unsigned getAlignment() const
Return the alignment of the access that is being performed.
Definition: Instructions.h:240
static Type * getIndexedType(Type *Ty, ArrayRef< Value *> IdxList)
Returns the type of the element that would be loaded with a load instruction with the specified param...
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:175
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
static InvokeInst * Create(FunctionType *Ty, Value *Func, BasicBlock *IfNormal, BasicBlock *IfException, ArrayRef< Value *> Args, const Twine &NameStr, Instruction *InsertBefore=nullptr)
This file provides utility analysis objects describing memory locations.
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:322
const BasicBlockListType & getBasicBlockList() const
Get the underlying elements of the Function...
Definition: Function.h:632
PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG, CGSCCUpdateResult &UR)
void eraseFromParent()
eraseFromParent - This method unlinks &#39;this&#39; from the containing module and deletes it...
Definition: Function.cpp:213
This header provides classes for managing passes over SCCs of the call graph.
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:205
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:375
const BasicBlock & front() const
Definition: Function.h:662
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:565
LLVM Value Representation.
Definition: Value.h:72
An SCC of the call graph.
CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on.
CallGraphNode * getOrInsertFunction(const Function *F)
Similar to operator[], but this will insert a new CallGraphNode for F if one does not already exist...
Definition: CallGraph.cpp:148
AttributeSet getFnAttributes() const
The function attributes are returned.
Invoke instruction.
static Function * promoteArguments(Function *F, function_ref< AAResults &(Function &F)> AARGetter, unsigned MaxElements, Optional< function_ref< void(CallSite OldCS, CallSite NewCS)>> ReplaceCallSite, const TargetTransformInfo &TTI)
PromoteArguments - This method checks the specified function to see if there are any promotable argum...
static void markIndicesSafe(const IndicesVector &ToMark, std::set< IndicesVector > &Safe)
Mark the given indices (ToMark) as safe in the given set of indices (Safe).
uint64_t getTypeAllocSizeInBits(Type *Ty) const
Returns the offset in bits between successive objects of the specified type, including alignment padd...
Definition: DataLayout.h:448
This is the interface for LLVM&#39;s primary stateless and local alias analysis.
A container for analyses that lazily runs them and caches their results.
This pass exposes codegen information to IR-level passes.
This header defines various interfaces for pass management in LLVM.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc)
Check if it is possible for execution of the specified basic block to modify the location Loc...
bool use_empty() const
Definition: Value.h:322
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
static AttributeList get(LLVMContext &C, ArrayRef< std::pair< unsigned, Attribute >> Attrs)
Create an AttributeList with the specified parameters in it.
Definition: Attributes.cpp:872
iterator_range< arg_iterator > args()
Definition: Function.h:688
bool isStructTy() const
True if this is an instance of StructType.
Definition: Type.h:217
User * user_back()
Definition: Value.h:385
const BasicBlock * getParent() const
Definition: Instruction.h:66
an instruction to allocate memory on the stack
Definition: Instructions.h:59
user_iterator user_end()
Definition: Value.h:383