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