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/Optional.h"
35 #include "llvm/ADT/Statistic.h"
36 #include "llvm/ADT/StringExtras.h"
43 #include "llvm/Analysis/Loads.h"
45 #include "llvm/IR/CFG.h"
46 #include "llvm/IR/CallSite.h"
47 #include "llvm/IR/Constants.h"
48 #include "llvm/IR/DataLayout.h"
49 #include "llvm/IR/DebugInfo.h"
50 #include "llvm/IR/DerivedTypes.h"
51 #include "llvm/IR/Instructions.h"
52 #include "llvm/IR/LLVMContext.h"
53 #include "llvm/IR/Module.h"
54 #include "llvm/Support/Debug.h"
56 #include "llvm/Transforms/IPO.h"
57 #include <set>
58 using namespace llvm;
59 
60 #define DEBUG_TYPE "argpromotion"
61 
62 STATISTIC(NumArgumentsPromoted, "Number of pointer arguments promoted");
63 STATISTIC(NumAggregatesPromoted, "Number of aggregate arguments promoted");
64 STATISTIC(NumByValArgsPromoted, "Number of byval arguments promoted");
65 STATISTIC(NumArgumentsDead, "Number of dead pointer args eliminated");
66 
67 /// A vector used to hold the indices of a single GEP instruction
68 typedef std::vector<uint64_t> IndicesVector;
69 
70 /// DoPromotion - This method actually performs the promotion of the specified
71 /// arguments, and returns the new function. At this point, we know that it's
72 /// safe to do so.
73 static Function *
75  SmallPtrSetImpl<Argument *> &ByValArgsToTransform,
76  Optional<function_ref<void(CallSite OldCS, CallSite NewCS)>>
77  ReplaceCallSite) {
78 
79  // Start by computing a new prototype for the function, which is the same as
80  // the old function, but has modified arguments.
81  FunctionType *FTy = F->getFunctionType();
82  std::vector<Type *> Params;
83 
84  typedef std::set<std::pair<Type *, IndicesVector>> ScalarizeTable;
85 
86  // ScalarizedElements - If we are promoting a pointer that has elements
87  // accessed out of it, keep track of which elements are accessed so that we
88  // can add one argument for each.
89  //
90  // Arguments that are directly loaded will have a zero element value here, to
91  // handle cases where there are both a direct load and GEP accesses.
92  //
93  std::map<Argument *, ScalarizeTable> ScalarizedElements;
94 
95  // OriginalLoads - Keep track of a representative load instruction from the
96  // original function so that we can tell the alias analysis implementation
97  // what the new GEP/Load instructions we are inserting look like.
98  // We need to keep the original loads for each argument and the elements
99  // of the argument that are accessed.
100  std::map<std::pair<Argument *, IndicesVector>, LoadInst *> OriginalLoads;
101 
102  // Attribute - Keep track of the parameter attributes for the arguments
103  // that we are *not* promoting. For the ones that we do promote, the parameter
104  // attributes are lost
105  SmallVector<AttributeSet, 8> ArgAttrVec;
106  AttributeList PAL = F->getAttributes();
107 
108  // First, determine the new argument list
109  unsigned ArgNo = 0;
110  for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E;
111  ++I, ++ArgNo) {
112  if (ByValArgsToTransform.count(&*I)) {
113  // Simple byval argument? Just add all the struct element types.
114  Type *AgTy = cast<PointerType>(I->getType())->getElementType();
115  StructType *STy = cast<StructType>(AgTy);
116  Params.insert(Params.end(), STy->element_begin(), STy->element_end());
117  ArgAttrVec.insert(ArgAttrVec.end(), STy->getNumElements(),
118  AttributeSet());
119  ++NumByValArgsPromoted;
120  } else if (!ArgsToPromote.count(&*I)) {
121  // Unchanged argument
122  Params.push_back(I->getType());
123  ArgAttrVec.push_back(PAL.getParamAttributes(ArgNo));
124  } else if (I->use_empty()) {
125  // Dead argument (which are always marked as promotable)
126  ++NumArgumentsDead;
127 
128  // There may be remaining metadata uses of the argument for things like
129  // llvm.dbg.value. Replace them with undef.
130  I->replaceAllUsesWith(UndefValue::get(I->getType()));
131  } else {
132  // Okay, this is being promoted. This means that the only uses are loads
133  // or GEPs which are only used by loads
134 
135  // In this table, we will track which indices are loaded from the argument
136  // (where direct loads are tracked as no indices).
137  ScalarizeTable &ArgIndices = ScalarizedElements[&*I];
138  for (User *U : I->users()) {
139  Instruction *UI = cast<Instruction>(U);
140  Type *SrcTy;
141  if (LoadInst *L = dyn_cast<LoadInst>(UI))
142  SrcTy = L->getType();
143  else
144  SrcTy = cast<GetElementPtrInst>(UI)->getSourceElementType();
145  IndicesVector Indices;
146  Indices.reserve(UI->getNumOperands() - 1);
147  // Since loads will only have a single operand, and GEPs only a single
148  // non-index operand, this will record direct loads without any indices,
149  // and gep+loads with the GEP indices.
150  for (User::op_iterator II = UI->op_begin() + 1, IE = UI->op_end();
151  II != IE; ++II)
152  Indices.push_back(cast<ConstantInt>(*II)->getSExtValue());
153  // GEPs with a single 0 index can be merged with direct loads
154  if (Indices.size() == 1 && Indices.front() == 0)
155  Indices.clear();
156  ArgIndices.insert(std::make_pair(SrcTy, Indices));
157  LoadInst *OrigLoad;
158  if (LoadInst *L = dyn_cast<LoadInst>(UI))
159  OrigLoad = L;
160  else
161  // Take any load, we will use it only to update Alias Analysis
162  OrigLoad = cast<LoadInst>(UI->user_back());
163  OriginalLoads[std::make_pair(&*I, Indices)] = OrigLoad;
164  }
165 
166  // Add a parameter to the function for each element passed in.
167  for (const auto &ArgIndex : ArgIndices) {
168  // not allowed to dereference ->begin() if size() is 0
169  Params.push_back(GetElementPtrInst::getIndexedType(
170  cast<PointerType>(I->getType()->getScalarType())->getElementType(),
171  ArgIndex.second));
172  ArgAttrVec.push_back(AttributeSet());
173  assert(Params.back());
174  }
175 
176  if (ArgIndices.size() == 1 && ArgIndices.begin()->second.empty())
177  ++NumArgumentsPromoted;
178  else
179  ++NumAggregatesPromoted;
180  }
181  }
182 
183  Type *RetTy = FTy->getReturnType();
184 
185  // Construct the new function type using the new arguments.
186  FunctionType *NFTy = FunctionType::get(RetTy, Params, FTy->isVarArg());
187 
188  // Create the new function body and insert it into the module.
189  Function *NF = Function::Create(NFTy, F->getLinkage(), F->getName());
190  NF->copyAttributesFrom(F);
191 
192  // Patch the pointer to LLVM function in debug info descriptor.
193  NF->setSubprogram(F->getSubprogram());
194  F->setSubprogram(nullptr);
195 
196  DEBUG(dbgs() << "ARG PROMOTION: Promoting to:" << *NF << "\n"
197  << "From: " << *F);
198 
199  // Recompute the parameter attributes list based on the new arguments for
200  // the function.
201  NF->setAttributes(AttributeList::get(F->getContext(), PAL.getFnAttributes(),
202  PAL.getRetAttributes(), ArgAttrVec));
203  ArgAttrVec.clear();
204 
205  F->getParent()->getFunctionList().insert(F->getIterator(), NF);
206  NF->takeName(F);
207 
208  // Loop over all of the callers of the function, transforming the call sites
209  // to pass in the loaded pointers.
210  //
212  while (!F->use_empty()) {
213  CallSite CS(F->user_back());
214  assert(CS.getCalledFunction() == F);
215  Instruction *Call = CS.getInstruction();
216  const AttributeList &CallPAL = CS.getAttributes();
217 
218  // Loop over the operands, inserting GEP and loads in the caller as
219  // appropriate.
220  CallSite::arg_iterator AI = CS.arg_begin();
221  ArgNo = 0;
222  for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E;
223  ++I, ++AI, ++ArgNo)
224  if (!ArgsToPromote.count(&*I) && !ByValArgsToTransform.count(&*I)) {
225  Args.push_back(*AI); // Unmodified argument
226  ArgAttrVec.push_back(CallPAL.getParamAttributes(ArgNo));
227  } else if (ByValArgsToTransform.count(&*I)) {
228  // Emit a GEP and load for each element of the struct.
229  Type *AgTy = cast<PointerType>(I->getType())->getElementType();
230  StructType *STy = cast<StructType>(AgTy);
231  Value *Idxs[2] = {
232  ConstantInt::get(Type::getInt32Ty(F->getContext()), 0), nullptr};
233  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
234  Idxs[1] = ConstantInt::get(Type::getInt32Ty(F->getContext()), i);
236  STy, *AI, Idxs, (*AI)->getName() + "." + Twine(i), Call);
237  // TODO: Tell AA about the new values?
238  Args.push_back(new LoadInst(Idx, Idx->getName() + ".val", Call));
239  ArgAttrVec.push_back(AttributeSet());
240  }
241  } else if (!I->use_empty()) {
242  // Non-dead argument: insert GEPs and loads as appropriate.
243  ScalarizeTable &ArgIndices = ScalarizedElements[&*I];
244  // Store the Value* version of the indices in here, but declare it now
245  // for reuse.
246  std::vector<Value *> Ops;
247  for (const auto &ArgIndex : ArgIndices) {
248  Value *V = *AI;
249  LoadInst *OrigLoad =
250  OriginalLoads[std::make_pair(&*I, ArgIndex.second)];
251  if (!ArgIndex.second.empty()) {
252  Ops.reserve(ArgIndex.second.size());
253  Type *ElTy = V->getType();
254  for (auto II : ArgIndex.second) {
255  // Use i32 to index structs, and i64 for others (pointers/arrays).
256  // This satisfies GEP constraints.
257  Type *IdxTy =
258  (ElTy->isStructTy() ? Type::getInt32Ty(F->getContext())
259  : Type::getInt64Ty(F->getContext()));
260  Ops.push_back(ConstantInt::get(IdxTy, II));
261  // Keep track of the type we're currently indexing.
262  if (auto *ElPTy = dyn_cast<PointerType>(ElTy))
263  ElTy = ElPTy->getElementType();
264  else
265  ElTy = cast<CompositeType>(ElTy)->getTypeAtIndex(II);
266  }
267  // And create a GEP to extract those indices.
268  V = GetElementPtrInst::Create(ArgIndex.first, V, Ops,
269  V->getName() + ".idx", Call);
270  Ops.clear();
271  }
272  // Since we're replacing a load make sure we take the alignment
273  // of the previous load.
274  LoadInst *newLoad = new LoadInst(V, V->getName() + ".val", Call);
275  newLoad->setAlignment(OrigLoad->getAlignment());
276  // Transfer the AA info too.
277  AAMDNodes AAInfo;
278  OrigLoad->getAAMetadata(AAInfo);
279  newLoad->setAAMetadata(AAInfo);
280 
281  Args.push_back(newLoad);
282  ArgAttrVec.push_back(AttributeSet());
283  }
284  }
285 
286  // Push any varargs arguments on the list.
287  for (; AI != CS.arg_end(); ++AI, ++ArgNo) {
288  Args.push_back(*AI);
289  ArgAttrVec.push_back(CallPAL.getParamAttributes(ArgNo));
290  }
291 
293  CS.getOperandBundlesAsDefs(OpBundles);
294 
295  CallSite NewCS;
296  if (InvokeInst *II = dyn_cast<InvokeInst>(Call)) {
297  NewCS = InvokeInst::Create(NF, II->getNormalDest(), II->getUnwindDest(),
298  Args, OpBundles, "", Call);
299  } else {
300  auto *NewCall = CallInst::Create(NF, Args, OpBundles, "", Call);
301  NewCall->setTailCallKind(cast<CallInst>(Call)->getTailCallKind());
302  NewCS = NewCall;
303  }
304  NewCS.setCallingConv(CS.getCallingConv());
305  NewCS.setAttributes(
307  CallPAL.getRetAttributes(), ArgAttrVec));
308  NewCS->setDebugLoc(Call->getDebugLoc());
309  uint64_t W;
310  if (Call->extractProfTotalWeight(W))
311  NewCS->setProfWeight(W);
312  Args.clear();
313  ArgAttrVec.clear();
314 
315  // Update the callgraph to know that the callsite has been transformed.
316  if (ReplaceCallSite)
317  (*ReplaceCallSite)(CS, NewCS);
318 
319  if (!Call->use_empty()) {
320  Call->replaceAllUsesWith(NewCS.getInstruction());
321  NewCS->takeName(Call);
322  }
323 
324  // Finally, remove the old call from the program, reducing the use-count of
325  // F.
326  Call->eraseFromParent();
327  }
328 
329  const DataLayout &DL = F->getParent()->getDataLayout();
330 
331  // Since we have now created the new function, splice the body of the old
332  // function right into the new function, leaving the old rotting hulk of the
333  // function empty.
334  NF->getBasicBlockList().splice(NF->begin(), F->getBasicBlockList());
335 
336  // Loop over the argument list, transferring uses of the old arguments over to
337  // the new arguments, also transferring over the names as well.
338  //
339  for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(),
340  I2 = NF->arg_begin();
341  I != E; ++I) {
342  if (!ArgsToPromote.count(&*I) && !ByValArgsToTransform.count(&*I)) {
343  // If this is an unmodified argument, move the name and users over to the
344  // new version.
345  I->replaceAllUsesWith(&*I2);
346  I2->takeName(&*I);
347  ++I2;
348  continue;
349  }
350 
351  if (ByValArgsToTransform.count(&*I)) {
352  // In the callee, we create an alloca, and store each of the new incoming
353  // arguments into the alloca.
354  Instruction *InsertPt = &NF->begin()->front();
355 
356  // Just add all the struct element types.
357  Type *AgTy = cast<PointerType>(I->getType())->getElementType();
358  Value *TheAlloca = new AllocaInst(AgTy, DL.getAllocaAddrSpace(), nullptr,
359  I->getParamAlignment(), "", InsertPt);
360  StructType *STy = cast<StructType>(AgTy);
361  Value *Idxs[2] = {ConstantInt::get(Type::getInt32Ty(F->getContext()), 0),
362  nullptr};
363 
364  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
365  Idxs[1] = ConstantInt::get(Type::getInt32Ty(F->getContext()), i);
367  AgTy, TheAlloca, Idxs, TheAlloca->getName() + "." + Twine(i),
368  InsertPt);
369  I2->setName(I->getName() + "." + Twine(i));
370  new StoreInst(&*I2++, Idx, InsertPt);
371  }
372 
373  // Anything that used the arg should now use the alloca.
374  I->replaceAllUsesWith(TheAlloca);
375  TheAlloca->takeName(&*I);
376 
377  // If the alloca is used in a call, we must clear the tail flag since
378  // the callee now uses an alloca from the caller.
379  for (User *U : TheAlloca->users()) {
380  CallInst *Call = dyn_cast<CallInst>(U);
381  if (!Call)
382  continue;
383  Call->setTailCall(false);
384  }
385  continue;
386  }
387 
388  if (I->use_empty())
389  continue;
390 
391  // Otherwise, if we promoted this argument, then all users are load
392  // instructions (or GEPs with only load users), and all loads should be
393  // using the new argument that we added.
394  ScalarizeTable &ArgIndices = ScalarizedElements[&*I];
395 
396  while (!I->use_empty()) {
397  if (LoadInst *LI = dyn_cast<LoadInst>(I->user_back())) {
398  assert(ArgIndices.begin()->second.empty() &&
399  "Load element should sort to front!");
400  I2->setName(I->getName() + ".val");
401  LI->replaceAllUsesWith(&*I2);
402  LI->eraseFromParent();
403  DEBUG(dbgs() << "*** Promoted load of argument '" << I->getName()
404  << "' in function '" << F->getName() << "'\n");
405  } else {
406  GetElementPtrInst *GEP = cast<GetElementPtrInst>(I->user_back());
407  IndicesVector Operands;
408  Operands.reserve(GEP->getNumIndices());
409  for (User::op_iterator II = GEP->idx_begin(), IE = GEP->idx_end();
410  II != IE; ++II)
411  Operands.push_back(cast<ConstantInt>(*II)->getSExtValue());
412 
413  // GEPs with a single 0 index can be merged with direct loads
414  if (Operands.size() == 1 && Operands.front() == 0)
415  Operands.clear();
416 
417  Function::arg_iterator TheArg = I2;
418  for (ScalarizeTable::iterator It = ArgIndices.begin();
419  It->second != Operands; ++It, ++TheArg) {
420  assert(It != ArgIndices.end() && "GEP not handled??");
421  }
422 
423  std::string NewName = I->getName();
424  for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
425  NewName += "." + utostr(Operands[i]);
426  }
427  NewName += ".val";
428  TheArg->setName(NewName);
429 
430  DEBUG(dbgs() << "*** Promoted agg argument '" << TheArg->getName()
431  << "' of function '" << NF->getName() << "'\n");
432 
433  // All of the uses must be load instructions. Replace them all with
434  // the argument specified by ArgNo.
435  while (!GEP->use_empty()) {
436  LoadInst *L = cast<LoadInst>(GEP->user_back());
437  L->replaceAllUsesWith(&*TheArg);
438  L->eraseFromParent();
439  }
440  GEP->eraseFromParent();
441  }
442  }
443 
444  // Increment I2 past all of the arguments added for this promoted pointer.
445  std::advance(I2, ArgIndices.size());
446  }
447 
448  return NF;
449 }
450 
451 /// AllCallersPassInValidPointerForArgument - Return true if we can prove that
452 /// all callees pass in a valid pointer for the specified function argument.
454  Function *Callee = Arg->getParent();
455  const DataLayout &DL = Callee->getParent()->getDataLayout();
456 
457  unsigned ArgNo = Arg->getArgNo();
458 
459  // Look at all call sites of the function. At this point we know we only have
460  // direct callees.
461  for (User *U : Callee->users()) {
462  CallSite CS(U);
463  assert(CS && "Should only have direct calls!");
464 
465  if (!isDereferenceablePointer(CS.getArgument(ArgNo), DL))
466  return false;
467  }
468  return true;
469 }
470 
471 /// Returns true if Prefix is a prefix of longer. That means, Longer has a size
472 /// that is greater than or equal to the size of prefix, and each of the
473 /// elements in Prefix is the same as the corresponding elements in Longer.
474 ///
475 /// This means it also returns true when Prefix and Longer are equal!
476 static bool isPrefix(const IndicesVector &Prefix, const IndicesVector &Longer) {
477  if (Prefix.size() > Longer.size())
478  return false;
479  return std::equal(Prefix.begin(), Prefix.end(), Longer.begin());
480 }
481 
482 /// Checks if Indices, or a prefix of Indices, is in Set.
483 static bool prefixIn(const IndicesVector &Indices,
484  std::set<IndicesVector> &Set) {
485  std::set<IndicesVector>::iterator Low;
486  Low = Set.upper_bound(Indices);
487  if (Low != Set.begin())
488  Low--;
489  // Low is now the last element smaller than or equal to Indices. This means
490  // it points to a prefix of Indices (possibly Indices itself), if such
491  // prefix exists.
492  //
493  // This load is safe if any prefix of its operands is safe to load.
494  return Low != Set.end() && isPrefix(*Low, Indices);
495 }
496 
497 /// Mark the given indices (ToMark) as safe in the given set of indices
498 /// (Safe). Marking safe usually means adding ToMark to Safe. However, if there
499 /// is already a prefix of Indices in Safe, Indices are implicitely marked safe
500 /// already. Furthermore, any indices that Indices is itself a prefix of, are
501 /// removed from Safe (since they are implicitely safe because of Indices now).
502 static void markIndicesSafe(const IndicesVector &ToMark,
503  std::set<IndicesVector> &Safe) {
504  std::set<IndicesVector>::iterator Low;
505  Low = Safe.upper_bound(ToMark);
506  // Guard against the case where Safe is empty
507  if (Low != Safe.begin())
508  Low--;
509  // Low is now the last element smaller than or equal to Indices. This
510  // means it points to a prefix of Indices (possibly Indices itself), if
511  // such prefix exists.
512  if (Low != Safe.end()) {
513  if (isPrefix(*Low, ToMark))
514  // If there is already a prefix of these indices (or exactly these
515  // indices) marked a safe, don't bother adding these indices
516  return;
517 
518  // Increment Low, so we can use it as a "insert before" hint
519  ++Low;
520  }
521  // Insert
522  Low = Safe.insert(Low, ToMark);
523  ++Low;
524  // If there we're a prefix of longer index list(s), remove those
525  std::set<IndicesVector>::iterator End = Safe.end();
526  while (Low != End && isPrefix(ToMark, *Low)) {
527  std::set<IndicesVector>::iterator Remove = Low;
528  ++Low;
529  Safe.erase(Remove);
530  }
531 }
532 
533 /// isSafeToPromoteArgument - As you might guess from the name of this method,
534 /// it checks to see if it is both safe and useful to promote the argument.
535 /// This method limits promotion of aggregates to only promote up to three
536 /// elements of the aggregate in order to avoid exploding the number of
537 /// arguments passed in.
538 static bool isSafeToPromoteArgument(Argument *Arg, bool isByValOrInAlloca,
539  AAResults &AAR, unsigned MaxElements) {
540  typedef std::set<IndicesVector> GEPIndicesSet;
541 
542  // Quick exit for unused arguments
543  if (Arg->use_empty())
544  return true;
545 
546  // We can only promote this argument if all of the uses are loads, or are GEP
547  // instructions (with constant indices) that are subsequently loaded.
548  //
549  // Promoting the argument causes it to be loaded in the caller
550  // unconditionally. This is only safe if we can prove that either the load
551  // would have happened in the callee anyway (ie, there is a load in the entry
552  // block) or the pointer passed in at every call site is guaranteed to be
553  // valid.
554  // In the former case, invalid loads can happen, but would have happened
555  // anyway, in the latter case, invalid loads won't happen. This prevents us
556  // from introducing an invalid load that wouldn't have happened in the
557  // original code.
558  //
559  // This set will contain all sets of indices that are loaded in the entry
560  // block, and thus are safe to unconditionally load in the caller.
561  //
562  // This optimization is also safe for InAlloca parameters, because it verifies
563  // that the address isn't captured.
564  GEPIndicesSet SafeToUnconditionallyLoad;
565 
566  // This set contains all the sets of indices that we are planning to promote.
567  // This makes it possible to limit the number of arguments added.
568  GEPIndicesSet ToPromote;
569 
570  // If the pointer is always valid, any load with first index 0 is valid.
571  if (isByValOrInAlloca || allCallersPassInValidPointerForArgument(Arg))
572  SafeToUnconditionallyLoad.insert(IndicesVector(1, 0));
573 
574  // First, iterate the entry block and mark loads of (geps of) arguments as
575  // safe.
576  BasicBlock &EntryBlock = Arg->getParent()->front();
577  // Declare this here so we can reuse it
578  IndicesVector Indices;
579  for (Instruction &I : EntryBlock)
580  if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
581  Value *V = LI->getPointerOperand();
582  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V)) {
583  V = GEP->getPointerOperand();
584  if (V == Arg) {
585  // This load actually loads (part of) Arg? Check the indices then.
586  Indices.reserve(GEP->getNumIndices());
587  for (User::op_iterator II = GEP->idx_begin(), IE = GEP->idx_end();
588  II != IE; ++II)
589  if (ConstantInt *CI = dyn_cast<ConstantInt>(*II))
590  Indices.push_back(CI->getSExtValue());
591  else
592  // We found a non-constant GEP index for this argument? Bail out
593  // right away, can't promote this argument at all.
594  return false;
595 
596  // Indices checked out, mark them as safe
597  markIndicesSafe(Indices, SafeToUnconditionallyLoad);
598  Indices.clear();
599  }
600  } else if (V == Arg) {
601  // Direct loads are equivalent to a GEP with a single 0 index.
602  markIndicesSafe(IndicesVector(1, 0), SafeToUnconditionallyLoad);
603  }
604  }
605 
606  // Now, iterate all uses of the argument to see if there are any uses that are
607  // not (GEP+)loads, or any (GEP+)loads that are not safe to promote.
609  IndicesVector Operands;
610  for (Use &U : Arg->uses()) {
611  User *UR = U.getUser();
612  Operands.clear();
613  if (LoadInst *LI = dyn_cast<LoadInst>(UR)) {
614  // Don't hack volatile/atomic loads
615  if (!LI->isSimple())
616  return false;
617  Loads.push_back(LI);
618  // Direct loads are equivalent to a GEP with a zero index and then a load.
619  Operands.push_back(0);
620  } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(UR)) {
621  if (GEP->use_empty()) {
622  // Dead GEP's cause trouble later. Just remove them if we run into
623  // them.
624  GEP->eraseFromParent();
625  // TODO: This runs the above loop over and over again for dead GEPs
626  // Couldn't we just do increment the UI iterator earlier and erase the
627  // use?
628  return isSafeToPromoteArgument(Arg, isByValOrInAlloca, AAR,
629  MaxElements);
630  }
631 
632  // Ensure that all of the indices are constants.
633  for (User::op_iterator i = GEP->idx_begin(), e = GEP->idx_end(); i != e;
634  ++i)
635  if (ConstantInt *C = dyn_cast<ConstantInt>(*i))
636  Operands.push_back(C->getSExtValue());
637  else
638  return false; // Not a constant operand GEP!
639 
640  // Ensure that the only users of the GEP are load instructions.
641  for (User *GEPU : GEP->users())
642  if (LoadInst *LI = dyn_cast<LoadInst>(GEPU)) {
643  // Don't hack volatile/atomic loads
644  if (!LI->isSimple())
645  return false;
646  Loads.push_back(LI);
647  } else {
648  // Other uses than load?
649  return false;
650  }
651  } else {
652  return false; // Not a load or a GEP.
653  }
654 
655  // Now, see if it is safe to promote this load / loads of this GEP. Loading
656  // is safe if Operands, or a prefix of Operands, is marked as safe.
657  if (!prefixIn(Operands, SafeToUnconditionallyLoad))
658  return false;
659 
660  // See if we are already promoting a load with these indices. If not, check
661  // to make sure that we aren't promoting too many elements. If so, nothing
662  // to do.
663  if (ToPromote.find(Operands) == ToPromote.end()) {
664  if (MaxElements > 0 && ToPromote.size() == MaxElements) {
665  DEBUG(dbgs() << "argpromotion not promoting argument '"
666  << Arg->getName()
667  << "' because it would require adding more "
668  << "than " << MaxElements
669  << " arguments to the function.\n");
670  // We limit aggregate promotion to only promoting up to a fixed number
671  // of elements of the aggregate.
672  return false;
673  }
674  ToPromote.insert(std::move(Operands));
675  }
676  }
677 
678  if (Loads.empty())
679  return true; // No users, this is a dead argument.
680 
681  // Okay, now we know that the argument is only used by load instructions and
682  // it is safe to unconditionally perform all of them. Use alias analysis to
683  // check to see if the pointer is guaranteed to not be modified from entry of
684  // the function to each of the load instructions.
685 
686  // Because there could be several/many load instructions, remember which
687  // blocks we know to be transparent to the load.
689 
690  for (LoadInst *Load : Loads) {
691  // Check to see if the load is invalidated from the start of the block to
692  // the load itself.
693  BasicBlock *BB = Load->getParent();
694 
696  if (AAR.canInstructionRangeModRef(BB->front(), *Load, Loc, MRI_Mod))
697  return false; // Pointer is invalidated!
698 
699  // Now check every path from the entry block to the load for transparency.
700  // To do this, we perform a depth first search on the inverse CFG from the
701  // loading block.
702  for (BasicBlock *P : predecessors(BB)) {
703  for (BasicBlock *TranspBB : inverse_depth_first_ext(P, TranspBlocks))
704  if (AAR.canBasicBlockModify(*TranspBB, Loc))
705  return false;
706  }
707  }
708 
709  // If the path from the entry of the function to each load is free of
710  // instructions that potentially invalidate the load, we can make the
711  // transformation!
712  return true;
713 }
714 
715 /// \brief Checks if a type could have padding bytes.
716 static bool isDenselyPacked(Type *type, const DataLayout &DL) {
717 
718  // There is no size information, so be conservative.
719  if (!type->isSized())
720  return false;
721 
722  // If the alloc size is not equal to the storage size, then there are padding
723  // bytes. For x86_fp80 on x86-64, size: 80 alloc size: 128.
724  if (DL.getTypeSizeInBits(type) != DL.getTypeAllocSizeInBits(type))
725  return false;
726 
727  if (!isa<CompositeType>(type))
728  return true;
729 
730  // For homogenous sequential types, check for padding within members.
731  if (SequentialType *seqTy = dyn_cast<SequentialType>(type))
732  return isDenselyPacked(seqTy->getElementType(), DL);
733 
734  // Check for padding within and between elements of a struct.
735  StructType *StructTy = cast<StructType>(type);
736  const StructLayout *Layout = DL.getStructLayout(StructTy);
737  uint64_t StartPos = 0;
738  for (unsigned i = 0, E = StructTy->getNumElements(); i < E; ++i) {
739  Type *ElTy = StructTy->getElementType(i);
740  if (!isDenselyPacked(ElTy, DL))
741  return false;
742  if (StartPos != Layout->getElementOffsetInBits(i))
743  return false;
744  StartPos += DL.getTypeAllocSizeInBits(ElTy);
745  }
746 
747  return true;
748 }
749 
750 /// \brief Checks if the padding bytes of an argument could be accessed.
751 static bool canPaddingBeAccessed(Argument *arg) {
752 
753  assert(arg->hasByValAttr());
754 
755  // Track all the pointers to the argument to make sure they are not captured.
756  SmallPtrSet<Value *, 16> PtrValues;
757  PtrValues.insert(arg);
758 
759  // Track all of the stores.
761 
762  // Scan through the uses recursively to make sure the pointer is always used
763  // sanely.
764  SmallVector<Value *, 16> WorkList;
765  WorkList.insert(WorkList.end(), arg->user_begin(), arg->user_end());
766  while (!WorkList.empty()) {
767  Value *V = WorkList.back();
768  WorkList.pop_back();
769  if (isa<GetElementPtrInst>(V) || isa<PHINode>(V)) {
770  if (PtrValues.insert(V).second)
771  WorkList.insert(WorkList.end(), V->user_begin(), V->user_end());
772  } else if (StoreInst *Store = dyn_cast<StoreInst>(V)) {
773  Stores.push_back(Store);
774  } else if (!isa<LoadInst>(V)) {
775  return true;
776  }
777  }
778 
779  // Check to make sure the pointers aren't captured
780  for (StoreInst *Store : Stores)
781  if (PtrValues.count(Store->getValueOperand()))
782  return true;
783 
784  return false;
785 }
786 
787 /// PromoteArguments - This method checks the specified function to see if there
788 /// are any promotable arguments and if it is safe to promote the function (for
789 /// example, all callers are direct). If safe to promote some arguments, it
790 /// calls the DoPromotion method.
791 ///
792 static Function *
794  unsigned MaxElements,
795  Optional<function_ref<void(CallSite OldCS, CallSite NewCS)>>
796  ReplaceCallSite) {
797  // Make sure that it is local to this module.
798  if (!F->hasLocalLinkage())
799  return nullptr;
800 
801  // Don't promote arguments for variadic functions. Adding, removing, or
802  // changing non-pack parameters can change the classification of pack
803  // parameters. Frontends encode that classification at the call site in the
804  // IR, while in the callee the classification is determined dynamically based
805  // on the number of registers consumed so far.
806  if (F->isVarArg())
807  return nullptr;
808 
809  // First check: see if there are any pointer arguments! If not, quick exit.
810  SmallVector<Argument *, 16> PointerArgs;
811  for (Argument &I : F->args())
812  if (I.getType()->isPointerTy())
813  PointerArgs.push_back(&I);
814  if (PointerArgs.empty())
815  return nullptr;
816 
817  // Second check: make sure that all callers are direct callers. We can't
818  // transform functions that have indirect callers. Also see if the function
819  // is self-recursive.
820  bool isSelfRecursive = false;
821  for (Use &U : F->uses()) {
822  CallSite CS(U.getUser());
823  // Must be a direct call.
824  if (CS.getInstruction() == nullptr || !CS.isCallee(&U))
825  return nullptr;
826 
827  if (CS.getInstruction()->getParent()->getParent() == F)
828  isSelfRecursive = true;
829  }
830 
831  const DataLayout &DL = F->getParent()->getDataLayout();
832 
833  AAResults &AAR = AARGetter(*F);
834 
835  // Check to see which arguments are promotable. If an argument is promotable,
836  // add it to ArgsToPromote.
837  SmallPtrSet<Argument *, 8> ArgsToPromote;
838  SmallPtrSet<Argument *, 8> ByValArgsToTransform;
839  for (Argument *PtrArg : PointerArgs) {
840  Type *AgTy = cast<PointerType>(PtrArg->getType())->getElementType();
841 
842  // Replace sret attribute with noalias. This reduces register pressure by
843  // avoiding a register copy.
844  if (PtrArg->hasStructRetAttr()) {
845  unsigned ArgNo = PtrArg->getArgNo();
846  F->removeParamAttr(ArgNo, Attribute::StructRet);
847  F->addParamAttr(ArgNo, Attribute::NoAlias);
848  for (Use &U : F->uses()) {
849  CallSite CS(U.getUser());
850  CS.removeParamAttr(ArgNo, Attribute::StructRet);
851  CS.addParamAttr(ArgNo, Attribute::NoAlias);
852  }
853  }
854 
855  // If this is a byval argument, and if the aggregate type is small, just
856  // pass the elements, which is always safe, if the passed value is densely
857  // packed or if we can prove the padding bytes are never accessed. This does
858  // not apply to inalloca.
859  bool isSafeToPromote =
860  PtrArg->hasByValAttr() &&
861  (isDenselyPacked(AgTy, DL) || !canPaddingBeAccessed(PtrArg));
862  if (isSafeToPromote) {
863  if (StructType *STy = dyn_cast<StructType>(AgTy)) {
864  if (MaxElements > 0 && STy->getNumElements() > MaxElements) {
865  DEBUG(dbgs() << "argpromotion disable promoting argument '"
866  << PtrArg->getName()
867  << "' because it would require adding more"
868  << " than " << MaxElements
869  << " arguments to the function.\n");
870  continue;
871  }
872 
873  // If all the elements are single-value types, we can promote it.
874  bool AllSimple = true;
875  for (const auto *EltTy : STy->elements()) {
876  if (!EltTy->isSingleValueType()) {
877  AllSimple = false;
878  break;
879  }
880  }
881 
882  // Safe to transform, don't even bother trying to "promote" it.
883  // Passing the elements as a scalar will allow sroa to hack on
884  // the new alloca we introduce.
885  if (AllSimple) {
886  ByValArgsToTransform.insert(PtrArg);
887  continue;
888  }
889  }
890  }
891 
892  // If the argument is a recursive type and we're in a recursive
893  // function, we could end up infinitely peeling the function argument.
894  if (isSelfRecursive) {
895  if (StructType *STy = dyn_cast<StructType>(AgTy)) {
896  bool RecursiveType = false;
897  for (const auto *EltTy : STy->elements()) {
898  if (EltTy == PtrArg->getType()) {
899  RecursiveType = true;
900  break;
901  }
902  }
903  if (RecursiveType)
904  continue;
905  }
906  }
907 
908  // Otherwise, see if we can promote the pointer to its value.
909  if (isSafeToPromoteArgument(PtrArg, PtrArg->hasByValOrInAllocaAttr(), AAR,
910  MaxElements))
911  ArgsToPromote.insert(PtrArg);
912  }
913 
914  // No promotable pointer arguments.
915  if (ArgsToPromote.empty() && ByValArgsToTransform.empty())
916  return nullptr;
917 
918  return doPromotion(F, ArgsToPromote, ByValArgsToTransform, ReplaceCallSite);
919 }
920 
923  LazyCallGraph &CG,
924  CGSCCUpdateResult &UR) {
925  bool Changed = false, LocalChange;
926 
927  // Iterate until we stop promoting from this SCC.
928  do {
929  LocalChange = false;
930 
931  for (LazyCallGraph::Node &N : C) {
932  Function &OldF = N.getFunction();
933 
935  AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
936  // FIXME: This lambda must only be used with this function. We should
937  // skip the lambda and just get the AA results directly.
938  auto AARGetter = [&](Function &F) -> AAResults & {
939  assert(&F == &OldF && "Called with an unexpected function!");
940  return FAM.getResult<AAManager>(F);
941  };
942 
943  Function *NewF = promoteArguments(&OldF, AARGetter, 3u, None);
944  if (!NewF)
945  continue;
946  LocalChange = true;
947 
948  // Directly substitute the functions in the call graph. Note that this
949  // requires the old function to be completely dead and completely
950  // replaced by the new function. It does no call graph updates, it merely
951  // swaps out the particular function mapped to a particular node in the
952  // graph.
953  C.getOuterRefSCC().replaceNodeFunction(N, *NewF);
954  OldF.eraseFromParent();
955  }
956 
957  Changed |= LocalChange;
958  } while (LocalChange);
959 
960  if (!Changed)
961  return PreservedAnalyses::all();
962 
963  return PreservedAnalyses::none();
964 }
965 
966 namespace {
967 /// ArgPromotion - The 'by reference' to 'by value' argument promotion pass.
968 ///
969 struct ArgPromotion : public CallGraphSCCPass {
970  void getAnalysisUsage(AnalysisUsage &AU) const override {
975  }
976 
977  bool runOnSCC(CallGraphSCC &SCC) override;
978  static char ID; // Pass identification, replacement for typeid
979  explicit ArgPromotion(unsigned MaxElements = 3)
980  : CallGraphSCCPass(ID), MaxElements(MaxElements) {
982  }
983 
984 private:
986  bool doInitialization(CallGraph &CG) override;
987  /// The maximum number of elements to expand, or 0 for unlimited.
988  unsigned MaxElements;
989 };
990 }
991 
992 char ArgPromotion::ID = 0;
993 INITIALIZE_PASS_BEGIN(ArgPromotion, "argpromotion",
994  "Promote 'by reference' arguments to scalars", false,
995  false)
1000  "Promote 'by reference' arguments to scalars", false, false)
1001 
1002 Pass *llvm::createArgumentPromotionPass(unsigned MaxElements) {
1003  return new ArgPromotion(MaxElements);
1004 }
1005 
1006 bool ArgPromotion::runOnSCC(CallGraphSCC &SCC) {
1007  if (skipSCC(SCC))
1008  return false;
1009 
1010  // Get the callgraph information that we need to update to reflect our
1011  // changes.
1012  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
1013 
1014  LegacyAARGetter AARGetter(*this);
1015 
1016  bool Changed = false, LocalChange;
1017 
1018  // Iterate until we stop promoting from this SCC.
1019  do {
1020  LocalChange = false;
1021  // Attempt to promote arguments from all functions in this SCC.
1022  for (CallGraphNode *OldNode : SCC) {
1023  Function *OldF = OldNode->getFunction();
1024  if (!OldF)
1025  continue;
1026 
1027  auto ReplaceCallSite = [&](CallSite OldCS, CallSite NewCS) {
1028  Function *Caller = OldCS.getInstruction()->getParent()->getParent();
1029  CallGraphNode *NewCalleeNode =
1030  CG.getOrInsertFunction(NewCS.getCalledFunction());
1031  CallGraphNode *CallerNode = CG[Caller];
1032  CallerNode->replaceCallEdge(OldCS, NewCS, NewCalleeNode);
1033  };
1034 
1035  if (Function *NewF = promoteArguments(OldF, AARGetter, MaxElements,
1036  {ReplaceCallSite})) {
1037  LocalChange = true;
1038 
1039  // Update the call graph for the newly promoted function.
1040  CallGraphNode *NewNode = CG.getOrInsertFunction(NewF);
1041  NewNode->stealCalledFunctionsFrom(OldNode);
1042  if (OldNode->getNumReferences() == 0)
1043  delete CG.removeFunctionFromModule(OldNode);
1044  else
1046 
1047  // And updat ethe SCC we're iterating as well.
1048  SCC.ReplaceNode(OldNode, NewNode);
1049  }
1050  }
1051  // Remember that we changed something.
1052  Changed |= LocalChange;
1053  } while (LocalChange);
1054 
1055  return Changed;
1056 }
1057 
1058 bool ArgPromotion::doInitialization(CallGraph &CG) {
1060 }
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:350
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:416
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.
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:87
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
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:336
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:493
#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...
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:284
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
static std::string utostr(uint64_t X, bool isNeg=false)
Definition: StringExtras.h:160
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:430
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:428
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:290
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
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:1494
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:1498
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:91
void copyAttributesFrom(const Function *Src)
copyAttributesFrom - copy all additional attributes (those not needed to create a Function) from the ...
Definition: Function.cpp:463
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
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:363
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:374
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
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
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:425
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:395
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:532
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
std::vector< uint64_t > IndicesVector
A vector used to hold the indices of a single GEP instruction.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:218
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
const Function * getFunction() const
Definition: Function.h:134
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:371
const BasicBlock & front() const
Definition: Function.h:595
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:545
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:415
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
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
static AttributeList get(LLVMContext &C, ArrayRef< std::pair< unsigned, Attribute >> Attrs)
Create an AttributeList with the specified parameters in it.
Definition: Attributes.cpp:870
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:381
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:379