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