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