LLVM  6.0.0svn
ArgumentPromotion.cpp
Go to the documentation of this file.
1 //===- ArgumentPromotion.cpp - Promote by-reference arguments -------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass promotes "by reference" arguments to be "by value" arguments. In
11 // practice, this means looking for internal functions that have pointer
12 // arguments. If it can prove, through the use of alias analysis, that an
13 // argument is *only* loaded, then it can pass the value into the function
14 // instead of the address of the value. This can cause recursive simplification
15 // of code and lead to the elimination of allocas (especially in C++ template
16 // code like the STL).
17 //
18 // This pass also handles aggregate arguments that are passed into a function,
19 // scalarizing them if the elements of the aggregate are only loaded. Note that
20 // by default it refuses to scalarize aggregates which would require passing in
21 // more than three operands to the function, because passing thousands of
22 // operands for a large array or structure is unprofitable! This limit can be
23 // configured or disabled, however.
24 //
25 // Note that this transformation could also be done for arguments that are only
26 // stored to (returning the value instead), but does not currently. This case
27 // would be best handled when and if LLVM begins supporting multiple return
28 // values from functions.
29 //
30 //===----------------------------------------------------------------------===//
31 
34 #include "llvm/ADT/None.h"
35 #include "llvm/ADT/Optional.h"
36 #include "llvm/ADT/STLExtras.h"
37 #include "llvm/ADT/SmallPtrSet.h"
38 #include "llvm/ADT/SmallVector.h"
39 #include "llvm/ADT/Statistic.h"
40 #include "llvm/ADT/StringExtras.h"
41 #include "llvm/ADT/Twine.h"
49 #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->getName());
217  NF->copyAttributesFrom(F);
218 
219  // Patch the pointer to LLVM function in debug info descriptor.
220  NF->setSubprogram(F->getSubprogram());
221  F->setSubprogram(nullptr);
222 
223  DEBUG(dbgs() << "ARG PROMOTION: Promoting to:" << *NF << "\n"
224  << "From: " << *F);
225 
226  // Recompute the parameter attributes list based on the new arguments for
227  // the function.
228  NF->setAttributes(AttributeList::get(F->getContext(), PAL.getFnAttributes(),
229  PAL.getRetAttributes(), ArgAttrVec));
230  ArgAttrVec.clear();
231 
232  F->getParent()->getFunctionList().insert(F->getIterator(), NF);
233  NF->takeName(F);
234 
235  // Loop over all of the callers of the function, transforming the call sites
236  // to pass in the loaded pointers.
237  //
239  while (!F->use_empty()) {
240  CallSite CS(F->user_back());
241  assert(CS.getCalledFunction() == F);
242  Instruction *Call = CS.getInstruction();
243  const AttributeList &CallPAL = CS.getAttributes();
244 
245  // Loop over the operands, inserting GEP and loads in the caller as
246  // appropriate.
247  CallSite::arg_iterator AI = CS.arg_begin();
248  ArgNo = 0;
249  for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E;
250  ++I, ++AI, ++ArgNo)
251  if (!ArgsToPromote.count(&*I) && !ByValArgsToTransform.count(&*I)) {
252  Args.push_back(*AI); // Unmodified argument
253  ArgAttrVec.push_back(CallPAL.getParamAttributes(ArgNo));
254  } else if (ByValArgsToTransform.count(&*I)) {
255  // Emit a GEP and load for each element of the struct.
256  Type *AgTy = cast<PointerType>(I->getType())->getElementType();
257  StructType *STy = cast<StructType>(AgTy);
258  Value *Idxs[2] = {
259  ConstantInt::get(Type::getInt32Ty(F->getContext()), 0), nullptr};
260  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
261  Idxs[1] = ConstantInt::get(Type::getInt32Ty(F->getContext()), i);
263  STy, *AI, Idxs, (*AI)->getName() + "." + Twine(i), Call);
264  // TODO: Tell AA about the new values?
265  Args.push_back(new LoadInst(Idx, 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 = new LoadInst(V, V->getName() + ".val", Call);
302  newLoad->setAlignment(OrigLoad->getAlignment());
303  // Transfer the AA info too.
304  AAMDNodes AAInfo;
305  OrigLoad->getAAMetadata(AAInfo);
306  newLoad->setAAMetadata(AAInfo);
307 
308  Args.push_back(newLoad);
309  ArgAttrVec.push_back(AttributeSet());
310  }
311  }
312 
313  // Push any varargs arguments on the list.
314  for (; AI != CS.arg_end(); ++AI, ++ArgNo) {
315  Args.push_back(*AI);
316  ArgAttrVec.push_back(CallPAL.getParamAttributes(ArgNo));
317  }
318 
320  CS.getOperandBundlesAsDefs(OpBundles);
321 
322  CallSite NewCS;
323  if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
324  NewCS = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(),
325  Args, OpBundles, "", Call);
326  } else {
327  auto *NewCall = CallInst::Create(NF, Args, OpBundles, "", Call);
328  NewCall->setTailCallKind(cast<CallInst>(Call)->getTailCallKind());
329  NewCS = NewCall;
330  }
331  NewCS.setCallingConv(CS.getCallingConv());
332  NewCS.setAttributes(
334  CallPAL.getRetAttributes(), ArgAttrVec));
335  NewCS->setDebugLoc(Call->getDebugLoc());
336  uint64_t W;
337  if (Call->extractProfTotalWeight(W))
338  NewCS->setProfWeight(W);
339  Args.clear();
340  ArgAttrVec.clear();
341 
342  // Update the callgraph to know that the callsite has been transformed.
343  if (ReplaceCallSite)
344  (*ReplaceCallSite)(CS, NewCS);
345 
346  if (!Call->use_empty()) {
347  Call->replaceAllUsesWith(NewCS.getInstruction());
348  NewCS->takeName(Call);
349  }
350 
351  // Finally, remove the old call from the program, reducing the use-count of
352  // F.
353  Call->eraseFromParent();
354  }
355 
356  const DataLayout &DL = F->getParent()->getDataLayout();
357 
358  // Since we have now created the new function, splice the body of the old
359  // function right into the new function, leaving the old rotting hulk of the
360  // function empty.
361  NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList());
362 
363  // Loop over the argument list, transferring uses of the old arguments over to
364  // the new arguments, also transferring over the names as well.
365  for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(),
366  I2 = NF->arg_begin();
367  I != E; ++I) {
368  if (!ArgsToPromote.count(&*I) && !ByValArgsToTransform.count(&*I)) {
369  // If this is an unmodified argument, move the name and users over to the
370  // new version.
371  I->replaceAllUsesWith(&*I2);
372  I2->takeName(&*I);
373  ++I2;
374  continue;
375  }
376 
377  if (ByValArgsToTransform.count(&*I)) {
378  // In the callee, we create an alloca, and store each of the new incoming
379  // arguments into the alloca.
380  Instruction *InsertPt = &NF->begin()->front();
381 
382  // Just add all the struct element types.
383  Type *AgTy = cast<PointerType>(I->getType())->getElementType();
384  Value *TheAlloca = new AllocaInst(AgTy, DL.getAllocaAddrSpace(), nullptr,
385  I->getParamAlignment(), "", InsertPt);
386  StructType *STy = cast<StructType>(AgTy);
387  Value *Idxs[2] = {ConstantInt::get(Type::getInt32Ty(F->getContext()), 0),
388  nullptr};
389 
390  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
391  Idxs[1] = ConstantInt::get(Type::getInt32Ty(F->getContext()), i);
393  AgTy, TheAlloca, Idxs, TheAlloca->getName() + "." + Twine(i),
394  InsertPt);
395  I2->setName(I->getName() + "." + Twine(i));
396  new StoreInst(&*I2++, Idx, InsertPt);
397  }
398 
399  // Anything that used the arg should now use the alloca.
400  I->replaceAllUsesWith(TheAlloca);
401  TheAlloca->takeName(&*I);
402 
403  // If the alloca is used in a call, we must clear the tail flag since
404  // the callee now uses an alloca from the caller.
405  for (User *U : TheAlloca->users()) {
406  CallInst *Call = dyn_cast<CallInst>(U);
407  if (!Call)
408  continue;
409  Call->setTailCall(false);
410  }
411  continue;
412  }
413 
414  if (I->use_empty())
415  continue;
416 
417  // Otherwise, if we promoted this argument, then all users are load
418  // instructions (or GEPs with only load users), and all loads should be
419  // using the new argument that we added.
420  ScalarizeTable &ArgIndices = ScalarizedElements[&*I];
421 
422  while (!I->use_empty()) {
423  if (LoadInst *LI = dyn_cast<LoadInst>(I->user_back())) {
424  assert(ArgIndices.begin()->second.empty() &&
425  "Load element should sort to front!");
426  I2->setName(I->getName() + ".val");
427  LI->replaceAllUsesWith(&*I2);
428  LI->eraseFromParent();
429  DEBUG(dbgs() << "*** Promoted load of argument '" << I->getName()
430  << "' in function '" << F->getName() << "'\n");
431  } else {
432  GetElementPtrInst *GEP = cast<GetElementPtrInst>(I->user_back());
433  IndicesVector Operands;
434  Operands.reserve(GEP->getNumIndices());
435  for (User::op_iterator II = GEP->idx_begin(), IE = GEP->idx_end();
436  II != IE; ++II)
437  Operands.push_back(cast<ConstantInt>(*II)->getSExtValue());
438 
439  // GEPs with a single 0 index can be merged with direct loads
440  if (Operands.size() == 1 && Operands.front() == 0)
441  Operands.clear();
442 
443  Function::arg_iterator TheArg = I2;
444  for (ScalarizeTable::iterator It = ArgIndices.begin();
445  It->second != Operands; ++It, ++TheArg) {
446  assert(It != ArgIndices.end() && "GEP not handled??");
447  }
448 
449  std::string NewName = I->getName();
450  for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
451  NewName += "." + utostr(Operands[i]);
452  }
453  NewName += ".val";
454  TheArg->setName(NewName);
455 
456  DEBUG(dbgs() << "*** Promoted agg argument '" << TheArg->getName()
457  << "' of function '" << NF->getName() << "'\n");
458 
459  // All of the uses must be load instructions. Replace them all with
460  // the argument specified by ArgNo.
461  while (!GEP->use_empty()) {
462  LoadInst *L = cast<LoadInst>(GEP->user_back());
463  L->replaceAllUsesWith(&*TheArg);
464  L->eraseFromParent();
465  }
466  GEP->eraseFromParent();
467  }
468  }
469 
470  // Increment I2 past all of the arguments added for this promoted pointer.
471  std::advance(I2, ArgIndices.size());
472  }
473 
474  return NF;
475 }
476 
477 /// AllCallersPassInValidPointerForArgument - Return true if we can prove that
478 /// all callees pass in a valid pointer for the specified function argument.
480  Function *Callee = Arg->getParent();
481  const DataLayout &DL = Callee->getParent()->getDataLayout();
482 
483  unsigned ArgNo = Arg->getArgNo();
484 
485  // Look at all call sites of the function. At this point we know we only have
486  // direct callees.
487  for (User *U : Callee->users()) {
488  CallSite CS(U);
489  assert(CS && "Should only have direct calls!");
490 
491  if (!isDereferenceablePointer(CS.getArgument(ArgNo), DL))
492  return false;
493  }
494  return true;
495 }
496 
497 /// Returns true if Prefix is a prefix of longer. That means, Longer has a size
498 /// that is greater than or equal to the size of prefix, and each of the
499 /// elements in Prefix is the same as the corresponding elements in Longer.
500 ///
501 /// This means it also returns true when Prefix and Longer are equal!
502 static bool isPrefix(const IndicesVector &Prefix, const IndicesVector &Longer) {
503  if (Prefix.size() > Longer.size())
504  return false;
505  return std::equal(Prefix.begin(), Prefix.end(), Longer.begin());
506 }
507 
508 /// Checks if Indices, or a prefix of Indices, is in Set.
509 static bool prefixIn(const IndicesVector &Indices,
510  std::set<IndicesVector> &Set) {
511  std::set<IndicesVector>::iterator Low;
512  Low = Set.upper_bound(Indices);
513  if (Low != Set.begin())
514  Low--;
515  // Low is now the last element smaller than or equal to Indices. This means
516  // it points to a prefix of Indices (possibly Indices itself), if such
517  // prefix exists.
518  //
519  // This load is safe if any prefix of its operands is safe to load.
520  return Low != Set.end() && isPrefix(*Low, Indices);
521 }
522 
523 /// Mark the given indices (ToMark) as safe in the given set of indices
524 /// (Safe). Marking safe usually means adding ToMark to Safe. However, if there
525 /// is already a prefix of Indices in Safe, Indices are implicitely marked safe
526 /// already. Furthermore, any indices that Indices is itself a prefix of, are
527 /// removed from Safe (since they are implicitely safe because of Indices now).
528 static void markIndicesSafe(const IndicesVector &ToMark,
529  std::set<IndicesVector> &Safe) {
530  std::set<IndicesVector>::iterator Low;
531  Low = Safe.upper_bound(ToMark);
532  // Guard against the case where Safe is empty
533  if (Low != Safe.begin())
534  Low--;
535  // Low is now the last element smaller than or equal to Indices. This
536  // means it points to a prefix of Indices (possibly Indices itself), if
537  // such prefix exists.
538  if (Low != Safe.end()) {
539  if (isPrefix(*Low, ToMark))
540  // If there is already a prefix of these indices (or exactly these
541  // indices) marked a safe, don't bother adding these indices
542  return;
543 
544  // Increment Low, so we can use it as a "insert before" hint
545  ++Low;
546  }
547  // Insert
548  Low = Safe.insert(Low, ToMark);
549  ++Low;
550  // If there we're a prefix of longer index list(s), remove those
551  std::set<IndicesVector>::iterator End = Safe.end();
552  while (Low != End && isPrefix(ToMark, *Low)) {
553  std::set<IndicesVector>::iterator Remove = Low;
554  ++Low;
555  Safe.erase(Remove);
556  }
557 }
558 
559 /// isSafeToPromoteArgument - As you might guess from the name of this method,
560 /// it checks to see if it is both safe and useful to promote the argument.
561 /// This method limits promotion of aggregates to only promote up to three
562 /// elements of the aggregate in order to avoid exploding the number of
563 /// arguments passed in.
564 static bool isSafeToPromoteArgument(Argument *Arg, bool isByValOrInAlloca,
565  AAResults &AAR, unsigned MaxElements) {
566  using GEPIndicesSet = std::set<IndicesVector>;
567 
568  // Quick exit for unused arguments
569  if (Arg->use_empty())
570  return true;
571 
572  // We can only promote this argument if all of the uses are loads, or are GEP
573  // instructions (with constant indices) that are subsequently loaded.
574  //
575  // Promoting the argument causes it to be loaded in the caller
576  // unconditionally. This is only safe if we can prove that either the load
577  // would have happened in the callee anyway (ie, there is a load in the entry
578  // block) or the pointer passed in at every call site is guaranteed to be
579  // valid.
580  // In the former case, invalid loads can happen, but would have happened
581  // anyway, in the latter case, invalid loads won't happen. This prevents us
582  // from introducing an invalid load that wouldn't have happened in the
583  // original code.
584  //
585  // This set will contain all sets of indices that are loaded in the entry
586  // block, and thus are safe to unconditionally load in the caller.
587  //
588  // This optimization is also safe for InAlloca parameters, because it verifies
589  // that the address isn't captured.
590  GEPIndicesSet SafeToUnconditionallyLoad;
591 
592  // This set contains all the sets of indices that we are planning to promote.
593  // This makes it possible to limit the number of arguments added.
594  GEPIndicesSet ToPromote;
595 
596  // If the pointer is always valid, any load with first index 0 is valid.
597  if (isByValOrInAlloca || allCallersPassInValidPointerForArgument(Arg))
598  SafeToUnconditionallyLoad.insert(IndicesVector(1, 0));
599 
600  // First, iterate the entry block and mark loads of (geps of) arguments as
601  // safe.
602  BasicBlock &EntryBlock = Arg->getParent()->front();
603  // Declare this here so we can reuse it
604  IndicesVector Indices;
605  for (Instruction &I : EntryBlock)
606  if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
607  Value *V = LI->getPointerOperand();
608  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V)) {
609  V = GEP->getPointerOperand();
610  if (V == Arg) {
611  // This load actually loads (part of) Arg? Check the indices then.
612  Indices.reserve(GEP->getNumIndices());
613  for (User::op_iterator II = GEP->idx_begin(), IE = GEP->idx_end();
614  II != IE; ++II)
615  if (ConstantInt *CI = dyn_cast<ConstantInt>(*II))
616  Indices.push_back(CI->getSExtValue());
617  else
618  // We found a non-constant GEP index for this argument? Bail out
619  // right away, can't promote this argument at all.
620  return false;
621 
622  // Indices checked out, mark them as safe
623  markIndicesSafe(Indices, SafeToUnconditionallyLoad);
624  Indices.clear();
625  }
626  } else if (V == Arg) {
627  // Direct loads are equivalent to a GEP with a single 0 index.
628  markIndicesSafe(IndicesVector(1, 0), SafeToUnconditionallyLoad);
629  }
630  }
631 
632  // Now, iterate all uses of the argument to see if there are any uses that are
633  // not (GEP+)loads, or any (GEP+)loads that are not safe to promote.
635  IndicesVector Operands;
636  for (Use &U : Arg->uses()) {
637  User *UR = U.getUser();
638  Operands.clear();
639  if (LoadInst *LI = dyn_cast<LoadInst>(UR)) {
640  // Don't hack volatile/atomic loads
641  if (!LI->isSimple())
642  return false;
643  Loads.push_back(LI);
644  // Direct loads are equivalent to a GEP with a zero index and then a load.
645  Operands.push_back(0);
646  } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(UR)) {
647  if (GEP->use_empty()) {
648  // Dead GEP's cause trouble later. Just remove them if we run into
649  // them.
650  GEP->eraseFromParent();
651  // TODO: This runs the above loop over and over again for dead GEPs
652  // Couldn't we just do increment the UI iterator earlier and erase the
653  // use?
654  return isSafeToPromoteArgument(Arg, isByValOrInAlloca, AAR,
655  MaxElements);
656  }
657 
658  // Ensure that all of the indices are constants.
659  for (User::op_iterator i = GEP->idx_begin(), e = GEP->idx_end(); i != e;
660  ++i)
661  if (ConstantInt *C = dyn_cast<ConstantInt>(*i))
662  Operands.push_back(C->getSExtValue());
663  else
664  return false; // Not a constant operand GEP!
665 
666  // Ensure that the only users of the GEP are load instructions.
667  for (User *GEPU : GEP->users())
668  if (LoadInst *LI = dyn_cast<LoadInst>(GEPU)) {
669  // Don't hack volatile/atomic loads
670  if (!LI->isSimple())
671  return false;
672  Loads.push_back(LI);
673  } else {
674  // Other uses than load?
675  return false;
676  }
677  } else {
678  return false; // Not a load or a GEP.
679  }
680 
681  // Now, see if it is safe to promote this load / loads of this GEP. Loading
682  // is safe if Operands, or a prefix of Operands, is marked as safe.
683  if (!prefixIn(Operands, SafeToUnconditionallyLoad))
684  return false;
685 
686  // See if we are already promoting a load with these indices. If not, check
687  // to make sure that we aren't promoting too many elements. If so, nothing
688  // to do.
689  if (ToPromote.find(Operands) == ToPromote.end()) {
690  if (MaxElements > 0 && ToPromote.size() == MaxElements) {
691  DEBUG(dbgs() << "argpromotion not promoting argument '"
692  << Arg->getName()
693  << "' because it would require adding more "
694  << "than " << MaxElements
695  << " arguments to the function.\n");
696  // We limit aggregate promotion to only promoting up to a fixed number
697  // of elements of the aggregate.
698  return false;
699  }
700  ToPromote.insert(std::move(Operands));
701  }
702  }
703 
704  if (Loads.empty())
705  return true; // No users, this is a dead argument.
706 
707  // Okay, now we know that the argument is only used by load instructions and
708  // it is safe to unconditionally perform all of them. Use alias analysis to
709  // check to see if the pointer is guaranteed to not be modified from entry of
710  // the function to each of the load instructions.
711 
712  // Because there could be several/many load instructions, remember which
713  // blocks we know to be transparent to the load.
715 
716  for (LoadInst *Load : Loads) {
717  // Check to see if the load is invalidated from the start of the block to
718  // the load itself.
719  BasicBlock *BB = Load->getParent();
720 
722  if (AAR.canInstructionRangeModRef(BB->front(), *Load, Loc, MRI_Mod))
723  return false; // Pointer is invalidated!
724 
725  // Now check every path from the entry block to the load for transparency.
726  // To do this, we perform a depth first search on the inverse CFG from the
727  // loading block.
728  for (BasicBlock *P : predecessors(BB)) {
729  for (BasicBlock *TranspBB : inverse_depth_first_ext(P, TranspBlocks))
730  if (AAR.canBasicBlockModify(*TranspBB, Loc))
731  return false;
732  }
733  }
734 
735  // If the path from the entry of the function to each load is free of
736  // instructions that potentially invalidate the load, we can make the
737  // transformation!
738  return true;
739 }
740 
741 /// \brief Checks if a type could have padding bytes.
742 static bool isDenselyPacked(Type *type, const DataLayout &DL) {
743  // There is no size information, so be conservative.
744  if (!type->isSized())
745  return false;
746 
747  // If the alloc size is not equal to the storage size, then there are padding
748  // bytes. For x86_fp80 on x86-64, size: 80 alloc size: 128.
749  if (DL.getTypeSizeInBits(type) != DL.getTypeAllocSizeInBits(type))
750  return false;
751 
752  if (!isa<CompositeType>(type))
753  return true;
754 
755  // For homogenous sequential types, check for padding within members.
756  if (SequentialType *seqTy = dyn_cast<SequentialType>(type))
757  return isDenselyPacked(seqTy->getElementType(), DL);
758 
759  // Check for padding within and between elements of a struct.
760  StructType *StructTy = cast<StructType>(type);
761  const StructLayout *Layout = DL.getStructLayout(StructTy);
762  uint64_t StartPos = 0;
763  for (unsigned i = 0, E = StructTy->getNumElements(); i < E; ++i) {
764  Type *ElTy = StructTy->getElementType(i);
765  if (!isDenselyPacked(ElTy, DL))
766  return false;
767  if (StartPos != Layout->getElementOffsetInBits(i))
768  return false;
769  StartPos += DL.getTypeAllocSizeInBits(ElTy);
770  }
771 
772  return true;
773 }
774 
775 /// \brief Checks if the padding bytes of an argument could be accessed.
776 static bool canPaddingBeAccessed(Argument *arg) {
777  assert(arg->hasByValAttr());
778 
779  // Track all the pointers to the argument to make sure they are not captured.
780  SmallPtrSet<Value *, 16> PtrValues;
781  PtrValues.insert(arg);
782 
783  // Track all of the stores.
785 
786  // Scan through the uses recursively to make sure the pointer is always used
787  // sanely.
788  SmallVector<Value *, 16> WorkList;
789  WorkList.insert(WorkList.end(), arg->user_begin(), arg->user_end());
790  while (!WorkList.empty()) {
791  Value *V = WorkList.back();
792  WorkList.pop_back();
793  if (isa<GetElementPtrInst>(V) || isa<PHINode>(V)) {
794  if (PtrValues.insert(V).second)
795  WorkList.insert(WorkList.end(), V->user_begin(), V->user_end());
796  } else if (StoreInst *Store = dyn_cast<StoreInst>(V)) {
797  Stores.push_back(Store);
798  } else if (!isa<LoadInst>(V)) {
799  return true;
800  }
801  }
802 
803  // Check to make sure the pointers aren't captured
804  for (StoreInst *Store : Stores)
805  if (PtrValues.count(Store->getValueOperand()))
806  return true;
807 
808  return false;
809 }
810 
811 /// PromoteArguments - This method checks the specified function to see if there
812 /// are any promotable arguments and if it is safe to promote the function (for
813 /// example, all callers are direct). If safe to promote some arguments, it
814 /// calls the DoPromotion method.
815 static Function *
817  unsigned MaxElements,
818  Optional<function_ref<void(CallSite OldCS, CallSite NewCS)>>
819  ReplaceCallSite) {
820  // Make sure that it is local to this module.
821  if (!F->hasLocalLinkage())
822  return nullptr;
823 
824  // Don't promote arguments for variadic functions. Adding, removing, or
825  // changing non-pack parameters can change the classification of pack
826  // parameters. Frontends encode that classification at the call site in the
827  // IR, while in the callee the classification is determined dynamically based
828  // on the number of registers consumed so far.
829  if (F->isVarArg())
830  return nullptr;
831 
832  // First check: see if there are any pointer arguments! If not, quick exit.
833  SmallVector<Argument *, 16> PointerArgs;
834  for (Argument &I : F->args())
835  if (I.getType()->isPointerTy())
836  PointerArgs.push_back(&I);
837  if (PointerArgs.empty())
838  return nullptr;
839 
840  // Second check: make sure that all callers are direct callers. We can't
841  // transform functions that have indirect callers. Also see if the function
842  // is self-recursive.
843  bool isSelfRecursive = false;
844  for (Use &U : F->uses()) {
845  CallSite CS(U.getUser());
846  // Must be a direct call.
847  if (CS.getInstruction() == nullptr || !CS.isCallee(&U))
848  return nullptr;
849 
850  if (CS.getInstruction()->getParent()->getParent() == F)
851  isSelfRecursive = true;
852  }
853 
854  const DataLayout &DL = F->getParent()->getDataLayout();
855 
856  AAResults &AAR = AARGetter(*F);
857 
858  // Check to see which arguments are promotable. If an argument is promotable,
859  // add it to ArgsToPromote.
860  SmallPtrSet<Argument *, 8> ArgsToPromote;
861  SmallPtrSet<Argument *, 8> ByValArgsToTransform;
862  for (Argument *PtrArg : PointerArgs) {
863  Type *AgTy = cast<PointerType>(PtrArg->getType())->getElementType();
864 
865  // Replace sret attribute with noalias. This reduces register pressure by
866  // avoiding a register copy.
867  if (PtrArg->hasStructRetAttr()) {
868  unsigned ArgNo = PtrArg->getArgNo();
869  F->removeParamAttr(ArgNo, Attribute::StructRet);
870  F->addParamAttr(ArgNo, Attribute::NoAlias);
871  for (Use &U : F->uses()) {
872  CallSite CS(U.getUser());
873  CS.removeParamAttr(ArgNo, Attribute::StructRet);
874  CS.addParamAttr(ArgNo, Attribute::NoAlias);
875  }
876  }
877 
878  // If this is a byval argument, and if the aggregate type is small, just
879  // pass the elements, which is always safe, if the passed value is densely
880  // packed or if we can prove the padding bytes are never accessed. This does
881  // not apply to inalloca.
882  bool isSafeToPromote =
883  PtrArg->hasByValAttr() &&
884  (isDenselyPacked(AgTy, DL) || !canPaddingBeAccessed(PtrArg));
885  if (isSafeToPromote) {
886  if (StructType *STy = dyn_cast<StructType>(AgTy)) {
887  if (MaxElements > 0 && STy->getNumElements() > MaxElements) {
888  DEBUG(dbgs() << "argpromotion disable promoting argument '"
889  << PtrArg->getName()
890  << "' because it would require adding more"
891  << " than " << MaxElements
892  << " arguments to the function.\n");
893  continue;
894  }
895 
896  // If all the elements are single-value types, we can promote it.
897  bool AllSimple = true;
898  for (const auto *EltTy : STy->elements()) {
899  if (!EltTy->isSingleValueType()) {
900  AllSimple = false;
901  break;
902  }
903  }
904 
905  // Safe to transform, don't even bother trying to "promote" it.
906  // Passing the elements as a scalar will allow sroa to hack on
907  // the new alloca we introduce.
908  if (AllSimple) {
909  ByValArgsToTransform.insert(PtrArg);
910  continue;
911  }
912  }
913  }
914 
915  // If the argument is a recursive type and we're in a recursive
916  // function, we could end up infinitely peeling the function argument.
917  if (isSelfRecursive) {
918  if (StructType *STy = dyn_cast<StructType>(AgTy)) {
919  bool RecursiveType = false;
920  for (const auto *EltTy : STy->elements()) {
921  if (EltTy == PtrArg->getType()) {
922  RecursiveType = true;
923  break;
924  }
925  }
926  if (RecursiveType)
927  continue;
928  }
929  }
930 
931  // Otherwise, see if we can promote the pointer to its value.
932  if (isSafeToPromoteArgument(PtrArg, PtrArg->hasByValOrInAllocaAttr(), AAR,
933  MaxElements))
934  ArgsToPromote.insert(PtrArg);
935  }
936 
937  // No promotable pointer arguments.
938  if (ArgsToPromote.empty() && ByValArgsToTransform.empty())
939  return nullptr;
940 
941  return doPromotion(F, ArgsToPromote, ByValArgsToTransform, ReplaceCallSite);
942 }
943 
946  LazyCallGraph &CG,
947  CGSCCUpdateResult &UR) {
948  bool Changed = false, LocalChange;
949 
950  // Iterate until we stop promoting from this SCC.
951  do {
952  LocalChange = false;
953 
954  for (LazyCallGraph::Node &N : C) {
955  Function &OldF = N.getFunction();
956 
958  AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
959  // FIXME: This lambda must only be used with this function. We should
960  // skip the lambda and just get the AA results directly.
961  auto AARGetter = [&](Function &F) -> AAResults & {
962  assert(&F == &OldF && "Called with an unexpected function!");
963  return FAM.getResult<AAManager>(F);
964  };
965 
966  Function *NewF = promoteArguments(&OldF, AARGetter, 3u, None);
967  if (!NewF)
968  continue;
969  LocalChange = true;
970 
971  // Directly substitute the functions in the call graph. Note that this
972  // requires the old function to be completely dead and completely
973  // replaced by the new function. It does no call graph updates, it merely
974  // swaps out the particular function mapped to a particular node in the
975  // graph.
976  C.getOuterRefSCC().replaceNodeFunction(N, *NewF);
977  OldF.eraseFromParent();
978  }
979 
980  Changed |= LocalChange;
981  } while (LocalChange);
982 
983  if (!Changed)
984  return PreservedAnalyses::all();
985 
986  return PreservedAnalyses::none();
987 }
988 
989 namespace {
990 
991 /// ArgPromotion - The 'by reference' to 'by value' argument promotion pass.
992 struct ArgPromotion : public CallGraphSCCPass {
993  // Pass identification, replacement for typeid
994  static char ID;
995 
996  explicit ArgPromotion(unsigned MaxElements = 3)
997  : CallGraphSCCPass(ID), MaxElements(MaxElements) {
999  }
1000 
1001  void getAnalysisUsage(AnalysisUsage &AU) const override {
1006  }
1007 
1008  bool runOnSCC(CallGraphSCC &SCC) override;
1009 
1010 private:
1012 
1013  bool doInitialization(CallGraph &CG) override;
1014 
1015  /// The maximum number of elements to expand, or 0 for unlimited.
1016  unsigned MaxElements;
1017 };
1018 
1019 } // end anonymous namespace
1020 
1021 char ArgPromotion::ID = 0;
1022 
1023 INITIALIZE_PASS_BEGIN(ArgPromotion, "argpromotion",
1024  "Promote 'by reference' arguments to scalars", false,
1025  false)
1030  "Promote 'by reference' arguments to scalars", false, false)
1031 
1032 Pass *llvm::createArgumentPromotionPass(unsigned MaxElements) {
1033  return new ArgPromotion(MaxElements);
1034 }
1035 
1036 bool ArgPromotion::runOnSCC(CallGraphSCC &SCC) {
1037  if (skipSCC(SCC))
1038  return false;
1039 
1040  // Get the callgraph information that we need to update to reflect our
1041  // changes.
1042  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
1043 
1044  LegacyAARGetter AARGetter(*this);
1045 
1046  bool Changed = false, LocalChange;
1047 
1048  // Iterate until we stop promoting from this SCC.
1049  do {
1050  LocalChange = false;
1051  // Attempt to promote arguments from all functions in this SCC.
1052  for (CallGraphNode *OldNode : SCC) {
1053  Function *OldF = OldNode->getFunction();
1054  if (!OldF)
1055  continue;
1056 
1057  auto ReplaceCallSite = [&](CallSite OldCS, CallSite NewCS) {
1058  Function *Caller = OldCS.getInstruction()->getParent()->getParent();
1059  CallGraphNode *NewCalleeNode =
1060  CG.getOrInsertFunction(NewCS.getCalledFunction());
1061  CallGraphNode *CallerNode = CG[Caller];
1062  CallerNode->replaceCallEdge(OldCS, NewCS, NewCalleeNode);
1063  };
1064 
1065  if (Function *NewF = promoteArguments(OldF, AARGetter, MaxElements,
1066  {ReplaceCallSite})) {
1067  LocalChange = true;
1068 
1069  // Update the call graph for the newly promoted function.
1070  CallGraphNode *NewNode = CG.getOrInsertFunction(NewF);
1071  NewNode->stealCalledFunctionsFrom(OldNode);
1072  if (OldNode->getNumReferences() == 0)
1073  delete CG.removeFunctionFromModule(OldNode);
1074  else
1076 
1077  // And updat ethe SCC we're iterating as well.
1078  SCC.ReplaceNode(OldNode, NewNode);
1079  }
1080  }
1081  // Remember that we changed something.
1082  Changed |= LocalChange;
1083  } while (LocalChange);
1084 
1085  return Changed;
1086 }
1087 
1088 bool ArgPromotion::doInitialization(CallGraph &CG) {
1090 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
bool isVarArg() const
isVarArg - Return true if this function takes a variable number of arguments.
Definition: Function.h:158
uint64_t CallInst * C
User::op_iterator arg_iterator
The type of iterator to use when looping over actual arguments at this call site. ...
Definition: CallSite.h:213
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:69
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
iterator_range< use_iterator > uses()
Definition: Value.h:356
void removeParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
removes the attribute from the list of attributes.
Definition: Function.cpp:401
bool hasLocalLinkage() const
Definition: GlobalValue.h:427
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:30
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Type * getElementType(unsigned N) const
Definition: DerivedTypes.h:314
void addParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
adds the attribute to the list of attributes for the given arg.
Definition: Function.cpp:365
bool isSized(SmallPtrSetImpl< Type *> *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:262
unsigned getNumElements() const
Random access to the elements.
Definition: DerivedTypes.h:313
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:562
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:863
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...
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:89
static bool isDenselyPacked(Type *type, const DataLayout &DL)
Checks if a type could have padding bytes.
Externally visible function.
Definition: GlobalValue.h:49
arg_iterator arg_end()
Definition: Function.h:612
iterator_range< idf_ext_iterator< T, SetTy > > inverse_depth_first_ext(const T &G, SetTy &S)
STATISTIC(NumFunctions, "Total number of functions")
The two locations do not alias at all.
Definition: AliasAnalysis.h:85
F(f)
static CallInst * Create(Value *Func, ArrayRef< Value *> Args, ArrayRef< OperandBundleDef > Bundles=None, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
An instruction for reading from memory.
Definition: Instructions.h:164
static IntegerType * getInt64Ty(LLVMContext &C)
Definition: Type.cpp:177
Hexagon Common GEP
This defines the Use class.
bool hasByValAttr() const
Return true if this argument has the byval attribute.
Definition: Function.cpp:88
A proxy from a FunctionAnalysisManager to an SCC.
A node in the call graph for a module.
Definition: CallGraph.h:165
void getAnalysisUsage(AnalysisUsage &Info) const override
getAnalysisUsage - For this class, we declare that we require and preserve the call graph...
The access modifies the value stored in memory.
op_iterator op_begin()
Definition: User.h:214
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:344
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:253
AnalysisUsage & addRequired()
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
Definition: DataLayout.h:491
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
Promote by reference arguments to scalars
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
Class to represent struct types.
Definition: DerivedTypes.h:201
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:231
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
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:122
AttributeSet getRetAttributes() const
The attributes for the ret value are returned.
InstrTy * getInstruction() const
Definition: CallSite.h:92
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:286
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:103
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
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:123
A lazily constructed view of the call graph of a module.
op_iterator idx_begin()
Definition: Instructions.h:962
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:205
An instruction for storing to memory.
Definition: Instructions.h:306
LinkageTypes getLinkage() const
Definition: GlobalValue.h:441
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:430
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:292
amdgpu Simplify well known AMD library false Value * Callee
virtual bool doInitialization(Module &)
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
Definition: Pass.h:106
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:837
void getAAMetadata(AAMDNodes &N, bool Merge=false) const
Fills the AAMDNodes structure with AA metadata from this instruction.
void setAttributes(AttributeList PAL)
Set the parameter attributes of the call.
Definition: CallSite.h:333
#define P(N)
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
void setSubprogram(DISubprogram *SP)
Set the attached subprogram.
Definition: Metadata.cpp:1493
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:324
void setAAMetadata(const AAMDNodes &N)
Sets the metadata on this instruction from the AAMDNodes structure.
Definition: Metadata.cpp:1253
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
const FunctionListType & getFunctionList() const
Get the Module&#39;s list of functions (constant).
Definition: Module.h:507
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1497
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:226
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:92
void copyAttributesFrom(const Function *Src)
copyAttributesFrom - copy all additional attributes (those not needed to create a Function) from the ...
Definition: Function.cpp:463
This file contains the declarations for the subclasses of Constant, which represent the different fla...
const Instruction & front() const
Definition: BasicBlock.h:264
A manager for alias analyses.
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:371
void removeParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
Definition: CallSite.h:357
element_iterator element_end() const
Definition: DerivedTypes.h:304
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:216
static bool canPaddingBeAccessed(Argument *arg)
Checks if the padding bytes of an argument could be accessed.
StringRef getName() const
Return the name for this struct type if it has an identity.
Definition: Type.cpp:487
static const unsigned End
void setCallingConv(CallingConv::ID CC)
Set the calling convention of the call.
Definition: CallSite.h:316
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:297
A node in the call graph.
arg_iterator arg_begin()
Definition: Function.h:603
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
self_iterator getIterator()
Definition: ilist_node.h:82
void setAlignment(unsigned Align)
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:194
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:1320
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
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
static InvokeInst * Create(Value *Func, BasicBlock *IfNormal, BasicBlock *IfException, ArrayRef< Value *> Args, const Twine &NameStr, Instruction *InsertBefore=nullptr)
Representation for a specific memory location.
This is the superclass of the array and vector type classes.
Definition: DerivedTypes.h:343
unsigned getNumOperands() const
Definition: User.h:176
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
std::vector< uint64_t > IndicesVector
A vector used to hold the indices of a single GEP instruction.
ValTy * getArgument(unsigned ArgNo) const
Definition: CallSite.h:186
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
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:642
Type * getReturnType() const
Definition: DerivedTypes.h:124
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:560
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:110
std::string utostr(uint64_t X, bool isNeg=false)
Definition: StringExtras.h:174
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:436
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
FunctionType * getFunctionType() const
Returns the FunctionType for me.
Definition: Function.h:145
unsigned getArgNo() const
Return the index of this formal argument in its containing function.
Definition: Argument.h:48
iterator_range< user_iterator > users()
Definition: Value.h:401
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:482
element_iterator element_begin() const
Definition: DerivedTypes.h:303
amdgpu Simplify well known AMD library false Value Value * Arg
uint64_t getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:530
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:153
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:74
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
iterator insert(iterator where, pointer New)
Definition: ilist.h:241
const Function * getParent() const
Definition: Argument.h:42
unsigned getAlignment() const
Return the alignment of the access that is being performed.
Definition: Instructions.h:226
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:176
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
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:220
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
#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:323
const BasicBlockListType & getBasicBlockList() const
Get the underlying elements of the Function...
Definition: Function.h:565
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:202
This header provides classes for managing passes over SCCs of the call graph.
const Function * getFunction() const
Definition: Function.h:134
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:377
const BasicBlock & front() const
Definition: Function.h:595
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:556
LLVM Value Representation.
Definition: Value.h:73
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:149
AttributeSet getFnAttributes() const
The function attributes are returned.
Invoke instruction.
#define DEBUG(X)
Definition: Debug.h:118
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:413
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.
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, const Twine &N="", Module *M=nullptr)
Definition: Function.h:136
This header defines various interfaces for pass management in LLVM.
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:328
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:868
iterator_range< arg_iterator > args()
Definition: Function.h:621
bool isStructTy() const
True if this is an instance of StructType.
Definition: Type.h:215
User * user_back()
Definition: Value.h:387
static Function * promoteArguments(Function *F, function_ref< AAResults &(Function &F)> AARGetter, unsigned MaxElements, Optional< function_ref< void(CallSite OldCS, CallSite NewCS)>> ReplaceCallSite)
PromoteArguments - This method checks the specified function to see if there are any promotable argum...
const BasicBlock * getParent() const
Definition: Instruction.h:66
an instruction to allocate memory on the stack
Definition: Instructions.h:60
user_iterator user_end()
Definition: Value.h:385