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