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