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 isByValOrInAlloca,
570  AAResults &AAR, 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  //
593  // This optimization is also safe for InAlloca parameters, because it verifies
594  // that the address isn't captured.
595  GEPIndicesSet SafeToUnconditionallyLoad;
596 
597  // This set contains all the sets of indices that we are planning to promote.
598  // This makes it possible to limit the number of arguments added.
599  GEPIndicesSet ToPromote;
600 
601  // If the pointer is always valid, any load with first index 0 is valid.
602  if (isByValOrInAlloca || allCallersPassInValidPointerForArgument(Arg))
603  SafeToUnconditionallyLoad.insert(IndicesVector(1, 0));
604 
605  // First, iterate the entry block and mark loads of (geps of) arguments as
606  // safe.
607  BasicBlock &EntryBlock = Arg->getParent()->front();
608  // Declare this here so we can reuse it
609  IndicesVector Indices;
610  for (Instruction &I : EntryBlock)
611  if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
612  Value *V = LI->getPointerOperand();
613  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V)) {
614  V = GEP->getPointerOperand();
615  if (V == Arg) {
616  // This load actually loads (part of) Arg? Check the indices then.
617  Indices.reserve(GEP->getNumIndices());
618  for (User::op_iterator II = GEP->idx_begin(), IE = GEP->idx_end();
619  II != IE; ++II)
620  if (ConstantInt *CI = dyn_cast<ConstantInt>(*II))
621  Indices.push_back(CI->getSExtValue());
622  else
623  // We found a non-constant GEP index for this argument? Bail out
624  // right away, can't promote this argument at all.
625  return false;
626 
627  // Indices checked out, mark them as safe
628  markIndicesSafe(Indices, SafeToUnconditionallyLoad);
629  Indices.clear();
630  }
631  } else if (V == Arg) {
632  // Direct loads are equivalent to a GEP with a single 0 index.
633  markIndicesSafe(IndicesVector(1, 0), SafeToUnconditionallyLoad);
634  }
635  }
636 
637  // Now, iterate all uses of the argument to see if there are any uses that are
638  // not (GEP+)loads, or any (GEP+)loads that are not safe to promote.
640  IndicesVector Operands;
641  for (Use &U : Arg->uses()) {
642  User *UR = U.getUser();
643  Operands.clear();
644  if (LoadInst *LI = dyn_cast<LoadInst>(UR)) {
645  // Don't hack volatile/atomic loads
646  if (!LI->isSimple())
647  return false;
648  Loads.push_back(LI);
649  // Direct loads are equivalent to a GEP with a zero index and then a load.
650  Operands.push_back(0);
651  } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(UR)) {
652  if (GEP->use_empty()) {
653  // Dead GEP's cause trouble later. Just remove them if we run into
654  // them.
655  GEP->eraseFromParent();
656  // TODO: This runs the above loop over and over again for dead GEPs
657  // Couldn't we just do increment the UI iterator earlier and erase the
658  // use?
659  return isSafeToPromoteArgument(Arg, isByValOrInAlloca, AAR,
660  MaxElements);
661  }
662 
663  // Ensure that all of the indices are constants.
664  for (User::op_iterator i = GEP->idx_begin(), e = GEP->idx_end(); i != e;
665  ++i)
666  if (ConstantInt *C = dyn_cast<ConstantInt>(*i))
667  Operands.push_back(C->getSExtValue());
668  else
669  return false; // Not a constant operand GEP!
670 
671  // Ensure that the only users of the GEP are load instructions.
672  for (User *GEPU : GEP->users())
673  if (LoadInst *LI = dyn_cast<LoadInst>(GEPU)) {
674  // Don't hack volatile/atomic loads
675  if (!LI->isSimple())
676  return false;
677  Loads.push_back(LI);
678  } else {
679  // Other uses than load?
680  return false;
681  }
682  } else {
683  return false; // Not a load or a GEP.
684  }
685 
686  // Now, see if it is safe to promote this load / loads of this GEP. Loading
687  // is safe if Operands, or a prefix of Operands, is marked as safe.
688  if (!prefixIn(Operands, SafeToUnconditionallyLoad))
689  return false;
690 
691  // See if we are already promoting a load with these indices. If not, check
692  // to make sure that we aren't promoting too many elements. If so, nothing
693  // to do.
694  if (ToPromote.find(Operands) == ToPromote.end()) {
695  if (MaxElements > 0 && ToPromote.size() == MaxElements) {
696  LLVM_DEBUG(dbgs() << "argpromotion not promoting argument '"
697  << Arg->getName()
698  << "' because it would require adding more "
699  << "than " << MaxElements
700  << " arguments to the function.\n");
701  // We limit aggregate promotion to only promoting up to a fixed number
702  // of elements of the aggregate.
703  return false;
704  }
705  ToPromote.insert(std::move(Operands));
706  }
707  }
708 
709  if (Loads.empty())
710  return true; // No users, this is a dead argument.
711 
712  // Okay, now we know that the argument is only used by load instructions and
713  // it is safe to unconditionally perform all of them. Use alias analysis to
714  // check to see if the pointer is guaranteed to not be modified from entry of
715  // the function to each of the load instructions.
716 
717  // Because there could be several/many load instructions, remember which
718  // blocks we know to be transparent to the load.
720 
721  for (LoadInst *Load : Loads) {
722  // Check to see if the load is invalidated from the start of the block to
723  // the load itself.
724  BasicBlock *BB = Load->getParent();
725 
727  if (AAR.canInstructionRangeModRef(BB->front(), *Load, Loc, ModRefInfo::Mod))
728  return false; // Pointer is invalidated!
729 
730  // Now check every path from the entry block to the load for transparency.
731  // To do this, we perform a depth first search on the inverse CFG from the
732  // loading block.
733  for (BasicBlock *P : predecessors(BB)) {
734  for (BasicBlock *TranspBB : inverse_depth_first_ext(P, TranspBlocks))
735  if (AAR.canBasicBlockModify(*TranspBB, Loc))
736  return false;
737  }
738  }
739 
740  // If the path from the entry of the function to each load is free of
741  // instructions that potentially invalidate the load, we can make the
742  // transformation!
743  return true;
744 }
745 
746 /// Checks if a type could have padding bytes.
747 static bool isDenselyPacked(Type *type, const DataLayout &DL) {
748  // There is no size information, so be conservative.
749  if (!type->isSized())
750  return false;
751 
752  // If the alloc size is not equal to the storage size, then there are padding
753  // bytes. For x86_fp80 on x86-64, size: 80 alloc size: 128.
754  if (DL.getTypeSizeInBits(type) != DL.getTypeAllocSizeInBits(type))
755  return false;
756 
757  if (!isa<CompositeType>(type))
758  return true;
759 
760  // For homogenous sequential types, check for padding within members.
761  if (SequentialType *seqTy = dyn_cast<SequentialType>(type))
762  return isDenselyPacked(seqTy->getElementType(), DL);
763 
764  // Check for padding within and between elements of a struct.
765  StructType *StructTy = cast<StructType>(type);
766  const StructLayout *Layout = DL.getStructLayout(StructTy);
767  uint64_t StartPos = 0;
768  for (unsigned i = 0, E = StructTy->getNumElements(); i < E; ++i) {
769  Type *ElTy = StructTy->getElementType(i);
770  if (!isDenselyPacked(ElTy, DL))
771  return false;
772  if (StartPos != Layout->getElementOffsetInBits(i))
773  return false;
774  StartPos += DL.getTypeAllocSizeInBits(ElTy);
775  }
776 
777  return true;
778 }
779 
780 /// Checks if the padding bytes of an argument could be accessed.
781 static bool canPaddingBeAccessed(Argument *arg) {
782  assert(arg->hasByValAttr());
783 
784  // Track all the pointers to the argument to make sure they are not captured.
785  SmallPtrSet<Value *, 16> PtrValues;
786  PtrValues.insert(arg);
787 
788  // Track all of the stores.
790 
791  // Scan through the uses recursively to make sure the pointer is always used
792  // sanely.
793  SmallVector<Value *, 16> WorkList;
794  WorkList.insert(WorkList.end(), arg->user_begin(), arg->user_end());
795  while (!WorkList.empty()) {
796  Value *V = WorkList.back();
797  WorkList.pop_back();
798  if (isa<GetElementPtrInst>(V) || isa<PHINode>(V)) {
799  if (PtrValues.insert(V).second)
800  WorkList.insert(WorkList.end(), V->user_begin(), V->user_end());
801  } else if (StoreInst *Store = dyn_cast<StoreInst>(V)) {
802  Stores.push_back(Store);
803  } else if (!isa<LoadInst>(V)) {
804  return true;
805  }
806  }
807 
808  // Check to make sure the pointers aren't captured
809  for (StoreInst *Store : Stores)
810  if (PtrValues.count(Store->getValueOperand()))
811  return true;
812 
813  return false;
814 }
815 
817  const Function &F, const TargetTransformInfo &TTI,
818  SmallPtrSetImpl<Argument *> &ArgsToPromote,
819  SmallPtrSetImpl<Argument *> &ByValArgsToTransform) {
820  for (const Use &U : F.uses()) {
821  CallSite CS(U.getUser());
822  const Function *Caller = CS.getCaller();
823  const Function *Callee = CS.getCalledFunction();
824  if (!TTI.areFunctionArgsABICompatible(Caller, Callee, ArgsToPromote) ||
825  !TTI.areFunctionArgsABICompatible(Caller, Callee, ByValArgsToTransform))
826  return false;
827  }
828  return true;
829 }
830 
831 /// PromoteArguments - This method checks the specified function to see if there
832 /// are any promotable arguments and if it is safe to promote the function (for
833 /// example, all callers are direct). If safe to promote some arguments, it
834 /// calls the DoPromotion method.
835 static Function *
837  unsigned MaxElements,
838  Optional<function_ref<void(CallSite OldCS, CallSite NewCS)>>
839  ReplaceCallSite,
840  const TargetTransformInfo &TTI) {
841  // Don't perform argument promotion for naked functions; otherwise we can end
842  // up removing parameters that are seemingly 'not used' as they are referred
843  // to in the assembly.
844  if(F->hasFnAttribute(Attribute::Naked))
845  return nullptr;
846 
847  // Make sure that it is local to this module.
848  if (!F->hasLocalLinkage())
849  return nullptr;
850 
851  // Don't promote arguments for variadic functions. Adding, removing, or
852  // changing non-pack parameters can change the classification of pack
853  // parameters. Frontends encode that classification at the call site in the
854  // IR, while in the callee the classification is determined dynamically based
855  // on the number of registers consumed so far.
856  if (F->isVarArg())
857  return nullptr;
858 
859  // First check: see if there are any pointer arguments! If not, quick exit.
860  SmallVector<Argument *, 16> PointerArgs;
861  for (Argument &I : F->args())
862  if (I.getType()->isPointerTy())
863  PointerArgs.push_back(&I);
864  if (PointerArgs.empty())
865  return nullptr;
866 
867  // Second check: make sure that all callers are direct callers. We can't
868  // transform functions that have indirect callers. Also see if the function
869  // is self-recursive and check that target features are compatible.
870  bool isSelfRecursive = false;
871  for (Use &U : F->uses()) {
872  CallSite CS(U.getUser());
873  // Must be a direct call.
874  if (CS.getInstruction() == nullptr || !CS.isCallee(&U))
875  return nullptr;
876 
877  // Can't change signature of musttail callee
878  if (CS.isMustTailCall())
879  return nullptr;
880 
881  if (CS.getInstruction()->getParent()->getParent() == F)
882  isSelfRecursive = true;
883  }
884 
885  // Can't change signature of musttail caller
886  // FIXME: Support promoting whole chain of musttail functions
887  for (BasicBlock &BB : *F)
888  if (BB.getTerminatingMustTailCall())
889  return nullptr;
890 
891  const DataLayout &DL = F->getParent()->getDataLayout();
892 
893  AAResults &AAR = AARGetter(*F);
894 
895  // Check to see which arguments are promotable. If an argument is promotable,
896  // add it to ArgsToPromote.
897  SmallPtrSet<Argument *, 8> ArgsToPromote;
898  SmallPtrSet<Argument *, 8> ByValArgsToTransform;
899  for (Argument *PtrArg : PointerArgs) {
900  Type *AgTy = cast<PointerType>(PtrArg->getType())->getElementType();
901 
902  // Replace sret attribute with noalias. This reduces register pressure by
903  // avoiding a register copy.
904  if (PtrArg->hasStructRetAttr()) {
905  unsigned ArgNo = PtrArg->getArgNo();
906  F->removeParamAttr(ArgNo, Attribute::StructRet);
907  F->addParamAttr(ArgNo, Attribute::NoAlias);
908  for (Use &U : F->uses()) {
909  CallSite CS(U.getUser());
910  CS.removeParamAttr(ArgNo, Attribute::StructRet);
911  CS.addParamAttr(ArgNo, Attribute::NoAlias);
912  }
913  }
914 
915  // If this is a byval argument, and if the aggregate type is small, just
916  // pass the elements, which is always safe, if the passed value is densely
917  // packed or if we can prove the padding bytes are never accessed. This does
918  // not apply to inalloca.
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->hasByValOrInAllocaAttr(), 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:435
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Type * getElementType(unsigned N) const
Definition: DerivedTypes.h:345
void setAttributes(AttributeList PAL)
Set the parameter attributes of the call.
Definition: CallSite.h:341
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:1392
bool isSized(SmallPtrSetImpl< Type *> *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:264
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
unsigned getNumElements() const
Random access to the elements.
Definition: DerivedTypes.h:344
const StructLayout * getStructLayout(StructType *Ty) const
Returns a StructLayout object, indicating the alignment of the struct, its size, and the offsets of i...
Definition: DataLayout.cpp:607
Implements a lazy call graph analysis and related passes for the new pass manager.
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value *> IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:899
This class represents a function call, abstracting a target machine&#39;s calling convention.
This file contains the declarations for metadata subclasses.
An immutable pass that tracks lazily created AssumptionCache objects.
virtual bool doInitialization(CallGraph &CG)
doInitialization - This method is called before the SCC&#39;s of the program has been processed...
The two locations do not alias at all.
Definition: AliasAnalysis.h: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:320
arg_iterator arg_end()
Definition: Function.h:682
iterator_range< idf_ext_iterator< T, SetTy > > inverse_depth_first_ext(const T &G, SetTy &S)
STATISTIC(NumFunctions, "Total number of functions")
F(f)
An instruction for reading from memory.
Definition: Instructions.h:167
static IntegerType * getInt64Ty(LLVMContext &C)
Definition: Type.cpp:176
Hexagon Common GEP
This defines the Use class.
bool hasByValAttr() const
Return true if this argument has the byval attribute.
Definition: Function.cpp:86
A proxy from a FunctionAnalysisManager to an SCC.
A node in the call graph for a module.
Definition: CallGraph.h:164
void getAnalysisUsage(AnalysisUsage &Info) const override
getAnalysisUsage - For this class, we declare that we require and preserve the call graph...
op_iterator op_begin()
Definition: User.h:229
Support structure for SCC passes to communicate updates the call graph back to the CGSCC pass manager...
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
static bool prefixIn(const IndicesVector &Indices, std::set< IndicesVector > &Set)
Checks if Indices, or a prefix of Indices, is in Set.
unsigned getAllocaAddrSpace() const
Definition: DataLayout.h:269
static bool areFunctionArgsABICompatible(const Function &F, const TargetTransformInfo &TTI, SmallPtrSetImpl< Argument *> &ArgsToPromote, SmallPtrSetImpl< Argument *> &ByValArgsToTransform)
AnalysisUsage & addRequired()
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
Definition: DataLayout.h:554
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
Promote by reference arguments to scalars
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
Class to represent struct types.
Definition: DerivedTypes.h:232
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:102
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
static bool isSafeToPromoteArgument(Argument *Arg, bool isByValOrInAlloca, AAResults &AAR, unsigned MaxElements)
isSafeToPromoteArgument - As you might guess from the name of this method, it checks to see if it is ...
AttributeSet getParamAttributes(unsigned ArgNo) const
The attributes for the argument or parameter at the given index are returned.
bool isVarArg() const
Definition: DerivedTypes.h:122
A lazily constructed view of the call graph of a module.
op_iterator idx_begin()
Definition: Instructions.h:998
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:223
An instruction for storing to memory.
Definition: Instructions.h:320
LinkageTypes getLinkage() const
Definition: GlobalValue.h:450
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:291
virtual bool doInitialization(Module &)
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
Definition: Pass.h:105
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:156
AttributeSet getAttributes(unsigned Index) const
The attributes for the specified index are returned.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:873
void getAAMetadata(AAMDNodes &N, bool Merge=false) const
Fills the AAMDNodes structure with AA metadata from this instruction.
#define P(N)
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
void setSubprogram(DISubprogram *SP)
Set the attached subprogram.
Definition: Metadata.cpp:1503
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:135
Wrapper pass for TargetTransformInfo.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
The ModulePass which wraps up a CallGraph and the logic to build it.
Definition: CallGraph.h:324
void setAAMetadata(const AAMDNodes &N)
Sets the metadata on this instruction from the AAMDNodes structure.
Definition: Metadata.cpp:1264
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
const FunctionListType & getFunctionList() const
Get the Module&#39;s list of functions (constant).
Definition: Module.h:533
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1507
bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, const MemoryLocation &Loc, const ModRefInfo Mode)
Check if it is possible for the execution of the specified instructions to mod(according to the mode)...
void stealCalledFunctionsFrom(CallGraphNode *N)
Moves all the callee information from N to this node.
Definition: CallGraph.h:225
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
void copyAttributesFrom(const Function *Src)
copyAttributesFrom - copy all additional attributes (those not needed to create a Function) from the ...
Definition: Function.cpp:483
void removeParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
Definition: CallSite.h:365
This file contains the declarations for the subclasses of Constant, which represent the different fla...
const Instruction & front() const
Definition: BasicBlock.h:280
A manager for alias analyses.
ValTy * getArgument(unsigned ArgNo) const
Definition: CallSite.h:193
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
element_iterator element_end() const
Definition: DerivedTypes.h:335
INITIALIZE_PASS_BEGIN(ArgPromotion, "argpromotion", "Promote 'by reference' arguments to scalars", false, false) INITIALIZE_PASS_END(ArgPromotion
static Function * doPromotion(Function *F, SmallPtrSetImpl< Argument *> &ArgsToPromote, SmallPtrSetImpl< Argument *> &ByValArgsToTransform, Optional< function_ref< void(CallSite OldCS, CallSite NewCS)>> ReplaceCallSite)
DoPromotion - This method actually performs the promotion of the specified arguments, and returns the new function.
Represent the analysis usage information of a pass.
op_iterator op_end()
Definition: User.h:231
static bool canPaddingBeAccessed(Argument *arg)
Checks if the padding bytes of an argument could be accessed.
unsigned getAddressSpace() const
Definition: Globals.cpp:110
StringRef getName() const
Return the name for this struct type if it has an identity.
Definition: Type.cpp:499
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
static bool allCallersPassInValidPointerForArgument(Argument *Arg)
AllCallersPassInValidPointerForArgument - Return true if we can prove that all callees pass in a vali...
static FunctionType * get(Type *Result, ArrayRef< Type *> Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
Definition: Type.cpp:296
A node in the call graph.
arg_iterator arg_begin()
Definition: Function.h:673
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
self_iterator getIterator()
Definition: ilist_node.h:81
void setAlignment(unsigned Align)
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:192
void setTailCall(bool isTC=true)
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1424
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
bool areFunctionArgsABICompatible(const Function *Caller, const Function *Callee, SmallPtrSetImpl< Argument *> &Args) const
void getAAResultsAnalysisUsage(AnalysisUsage &AU)
A helper for the legacy pass manager to populate AU to add uses to make sure the analyses required by...
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Value * CreateGEP(Value *Ptr, ArrayRef< Value *> IdxList, const Twine &Name="")
Definition: IRBuilder.h:1493
Representation for a specific memory location.
This is the superclass of the array and vector type classes.
Definition: DerivedTypes.h:374
unsigned getNumOperands() const
Definition: User.h:191
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
std::vector< uint64_t > IndicesVector
A vector used to hold the indices of a single GEP instruction.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
Module.h This file contains the declarations for the Module class.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
Definition: Instruction.h:63
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:643
Type * getReturnType() const
Definition: DerivedTypes.h:123
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:631
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:124
std::string utostr(uint64_t X, bool isNeg=false)
Definition: StringExtras.h:223
User::op_iterator arg_iterator
The type of iterator to use when looping over actual arguments at this call site. ...
Definition: CallSite.h:220
static bool isPrefix(const IndicesVector &Prefix, const IndicesVector &Longer)
Returns true if Prefix is a prefix of longer.
void setLinkage(LinkageTypes LT)
Definition: GlobalValue.h:444
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
The access may modify the value stored in memory.
FunctionType * getFunctionType() const
Returns the FunctionType for me.
Definition: Function.h:163
amdgpu Simplify well known AMD library false FunctionCallee Callee
unsigned getArgNo() const
Return the index of this formal argument in its containing function.
Definition: Argument.h:47
iterator_range< user_iterator > users()
Definition: Value.h:399
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:471
element_iterator element_begin() const
Definition: DerivedTypes.h:334
uint64_t getTypeSizeInBits(Type *Ty) const
Size examples:
Definition: DataLayout.h:593
bool isDereferenceablePointer(const Value *V, const DataLayout &DL, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr)
Return true if this is always a dereferenceable pointer.
Definition: Loads.cpp:152
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:73
iterator insert(iterator where, pointer New)
Definition: ilist.h:226
const Function * getParent() const
Definition: Argument.h:41
unsigned getAlignment() const
Return the alignment of the access that is being performed.
Definition: Instructions.h:240
static Type * getIndexedType(Type *Ty, ArrayRef< Value *> IdxList)
Returns the type of the element that would be loaded with a load instruction with the specified param...
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:175
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
static InvokeInst * Create(FunctionType *Ty, Value *Func, BasicBlock *IfNormal, BasicBlock *IfException, ArrayRef< Value *> Args, const Twine &NameStr, Instruction *InsertBefore=nullptr)
This file provides utility analysis objects describing memory locations.
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:635
PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG, CGSCCUpdateResult &UR)
void eraseFromParent()
eraseFromParent - This method unlinks &#39;this&#39; from the containing module and deletes it...
Definition: Function.cpp:213
This header provides classes for managing passes over SCCs of the call graph.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:375
const BasicBlock & front() const
Definition: Function.h:665
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:565
LLVM Value Representation.
Definition: Value.h:72
An SCC of the call graph.
CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on.
CallGraphNode * getOrInsertFunction(const Function *F)
Similar to operator[], but this will insert a new CallGraphNode for F if one does not already exist...
Definition: CallGraph.cpp: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:471
This is the interface for LLVM&#39;s primary stateless and local alias analysis.
A container for analyses that lazily runs them and caches their results.
This pass exposes codegen information to IR-level passes.
This header defines various interfaces for pass management in LLVM.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc)
Check if it is possible for execution of the specified basic block to modify the location Loc...
bool use_empty() const
Definition: Value.h:322
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
static AttributeList get(LLVMContext &C, ArrayRef< std::pair< unsigned, Attribute >> Attrs)
Create an AttributeList with the specified parameters in it.
Definition: Attributes.cpp:874
iterator_range< arg_iterator > args()
Definition: Function.h:691
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