LLVM  10.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 /// Return true if we can prove that all callees pass in a valid pointer for the
483 /// 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), Ty, 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, Type *ByValTy, 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 
600  if (ByValTy)
601  SafeToUnconditionallyLoad.insert(IndicesVector(1, 0));
602 
603  // Whenever a new underlying type for the operand is found, make sure it's
604  // consistent with the GEPs and loads we've already seen and, if necessary,
605  // use it to see if all incoming pointers are valid (which implies the 0-index
606  // is safe).
607  Type *BaseTy = ByValTy;
608  auto UpdateBaseTy = [&](Type *NewBaseTy) {
609  if (BaseTy)
610  return BaseTy == NewBaseTy;
611 
612  BaseTy = NewBaseTy;
613  if (allCallersPassValidPointerForArgument(Arg, BaseTy)) {
614  assert(SafeToUnconditionallyLoad.empty());
615  SafeToUnconditionallyLoad.insert(IndicesVector(1, 0));
616  }
617 
618  return true;
619  };
620 
621  // First, iterate the entry block and mark loads of (geps of) arguments as
622  // safe.
623  BasicBlock &EntryBlock = Arg->getParent()->front();
624  // Declare this here so we can reuse it
625  IndicesVector Indices;
626  for (Instruction &I : EntryBlock)
627  if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
628  Value *V = LI->getPointerOperand();
629  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V)) {
630  V = GEP->getPointerOperand();
631  if (V == Arg) {
632  // This load actually loads (part of) Arg? Check the indices then.
633  Indices.reserve(GEP->getNumIndices());
634  for (User::op_iterator II = GEP->idx_begin(), IE = GEP->idx_end();
635  II != IE; ++II)
636  if (ConstantInt *CI = dyn_cast<ConstantInt>(*II))
637  Indices.push_back(CI->getSExtValue());
638  else
639  // We found a non-constant GEP index for this argument? Bail out
640  // right away, can't promote this argument at all.
641  return false;
642 
643  if (!UpdateBaseTy(GEP->getSourceElementType()))
644  return false;
645 
646  // Indices checked out, mark them as safe
647  markIndicesSafe(Indices, SafeToUnconditionallyLoad);
648  Indices.clear();
649  }
650  } else if (V == Arg) {
651  // Direct loads are equivalent to a GEP with a single 0 index.
652  markIndicesSafe(IndicesVector(1, 0), SafeToUnconditionallyLoad);
653 
654  if (BaseTy && LI->getType() != BaseTy)
655  return false;
656 
657  BaseTy = LI->getType();
658  }
659  }
660 
661  // Now, iterate all uses of the argument to see if there are any uses that are
662  // not (GEP+)loads, or any (GEP+)loads that are not safe to promote.
664  IndicesVector Operands;
665  for (Use &U : Arg->uses()) {
666  User *UR = U.getUser();
667  Operands.clear();
668  if (LoadInst *LI = dyn_cast<LoadInst>(UR)) {
669  // Don't hack volatile/atomic loads
670  if (!LI->isSimple())
671  return false;
672  Loads.push_back(LI);
673  // Direct loads are equivalent to a GEP with a zero index and then a load.
674  Operands.push_back(0);
675 
676  if (!UpdateBaseTy(LI->getType()))
677  return false;
678  } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(UR)) {
679  if (GEP->use_empty()) {
680  // Dead GEP's cause trouble later. Just remove them if we run into
681  // them.
682  GEP->eraseFromParent();
683  // TODO: This runs the above loop over and over again for dead GEPs
684  // Couldn't we just do increment the UI iterator earlier and erase the
685  // use?
686  return isSafeToPromoteArgument(Arg, ByValTy, AAR, MaxElements);
687  }
688 
689  if (!UpdateBaseTy(GEP->getSourceElementType()))
690  return false;
691 
692  // Ensure that all of the indices are constants.
693  for (User::op_iterator i = GEP->idx_begin(), e = GEP->idx_end(); i != e;
694  ++i)
695  if (ConstantInt *C = dyn_cast<ConstantInt>(*i))
696  Operands.push_back(C->getSExtValue());
697  else
698  return false; // Not a constant operand GEP!
699 
700  // Ensure that the only users of the GEP are load instructions.
701  for (User *GEPU : GEP->users())
702  if (LoadInst *LI = dyn_cast<LoadInst>(GEPU)) {
703  // Don't hack volatile/atomic loads
704  if (!LI->isSimple())
705  return false;
706  Loads.push_back(LI);
707  } else {
708  // Other uses than load?
709  return false;
710  }
711  } else {
712  return false; // Not a load or a GEP.
713  }
714 
715  // Now, see if it is safe to promote this load / loads of this GEP. Loading
716  // is safe if Operands, or a prefix of Operands, is marked as safe.
717  if (!prefixIn(Operands, SafeToUnconditionallyLoad))
718  return false;
719 
720  // See if we are already promoting a load with these indices. If not, check
721  // to make sure that we aren't promoting too many elements. If so, nothing
722  // to do.
723  if (ToPromote.find(Operands) == ToPromote.end()) {
724  if (MaxElements > 0 && ToPromote.size() == MaxElements) {
725  LLVM_DEBUG(dbgs() << "argpromotion not promoting argument '"
726  << Arg->getName()
727  << "' because it would require adding more "
728  << "than " << MaxElements
729  << " arguments to the function.\n");
730  // We limit aggregate promotion to only promoting up to a fixed number
731  // of elements of the aggregate.
732  return false;
733  }
734  ToPromote.insert(std::move(Operands));
735  }
736  }
737 
738  if (Loads.empty())
739  return true; // No users, this is a dead argument.
740 
741  // Okay, now we know that the argument is only used by load instructions and
742  // it is safe to unconditionally perform all of them. Use alias analysis to
743  // check to see if the pointer is guaranteed to not be modified from entry of
744  // the function to each of the load instructions.
745 
746  // Because there could be several/many load instructions, remember which
747  // blocks we know to be transparent to the load.
749 
750  for (LoadInst *Load : Loads) {
751  // Check to see if the load is invalidated from the start of the block to
752  // the load itself.
753  BasicBlock *BB = Load->getParent();
754 
756  if (AAR.canInstructionRangeModRef(BB->front(), *Load, Loc, ModRefInfo::Mod))
757  return false; // Pointer is invalidated!
758 
759  // Now check every path from the entry block to the load for transparency.
760  // To do this, we perform a depth first search on the inverse CFG from the
761  // loading block.
762  for (BasicBlock *P : predecessors(BB)) {
763  for (BasicBlock *TranspBB : inverse_depth_first_ext(P, TranspBlocks))
764  if (AAR.canBasicBlockModify(*TranspBB, Loc))
765  return false;
766  }
767  }
768 
769  // If the path from the entry of the function to each load is free of
770  // instructions that potentially invalidate the load, we can make the
771  // transformation!
772  return true;
773 }
774 
775 /// Checks if a type could have padding bytes.
776 static bool isDenselyPacked(Type *type, const DataLayout &DL) {
777  // There is no size information, so be conservative.
778  if (!type->isSized())
779  return false;
780 
781  // If the alloc size is not equal to the storage size, then there are padding
782  // bytes. For x86_fp80 on x86-64, size: 80 alloc size: 128.
783  if (DL.getTypeSizeInBits(type) != DL.getTypeAllocSizeInBits(type))
784  return false;
785 
786  if (!isa<CompositeType>(type))
787  return true;
788 
789  // For homogenous sequential types, check for padding within members.
790  if (SequentialType *seqTy = dyn_cast<SequentialType>(type))
791  return isDenselyPacked(seqTy->getElementType(), DL);
792 
793  // Check for padding within and between elements of a struct.
794  StructType *StructTy = cast<StructType>(type);
795  const StructLayout *Layout = DL.getStructLayout(StructTy);
796  uint64_t StartPos = 0;
797  for (unsigned i = 0, E = StructTy->getNumElements(); i < E; ++i) {
798  Type *ElTy = StructTy->getElementType(i);
799  if (!isDenselyPacked(ElTy, DL))
800  return false;
801  if (StartPos != Layout->getElementOffsetInBits(i))
802  return false;
803  StartPos += DL.getTypeAllocSizeInBits(ElTy);
804  }
805 
806  return true;
807 }
808 
809 /// Checks if the padding bytes of an argument could be accessed.
810 static bool canPaddingBeAccessed(Argument *arg) {
811  assert(arg->hasByValAttr());
812 
813  // Track all the pointers to the argument to make sure they are not captured.
814  SmallPtrSet<Value *, 16> PtrValues;
815  PtrValues.insert(arg);
816 
817  // Track all of the stores.
819 
820  // Scan through the uses recursively to make sure the pointer is always used
821  // sanely.
822  SmallVector<Value *, 16> WorkList;
823  WorkList.insert(WorkList.end(), arg->user_begin(), arg->user_end());
824  while (!WorkList.empty()) {
825  Value *V = WorkList.back();
826  WorkList.pop_back();
827  if (isa<GetElementPtrInst>(V) || isa<PHINode>(V)) {
828  if (PtrValues.insert(V).second)
829  WorkList.insert(WorkList.end(), V->user_begin(), V->user_end());
830  } else if (StoreInst *Store = dyn_cast<StoreInst>(V)) {
831  Stores.push_back(Store);
832  } else if (!isa<LoadInst>(V)) {
833  return true;
834  }
835  }
836 
837  // Check to make sure the pointers aren't captured
838  for (StoreInst *Store : Stores)
839  if (PtrValues.count(Store->getValueOperand()))
840  return true;
841 
842  return false;
843 }
844 
846  const Function &F, const TargetTransformInfo &TTI,
847  SmallPtrSetImpl<Argument *> &ArgsToPromote,
848  SmallPtrSetImpl<Argument *> &ByValArgsToTransform) {
849  for (const Use &U : F.uses()) {
850  CallSite CS(U.getUser());
851  const Function *Caller = CS.getCaller();
852  const Function *Callee = CS.getCalledFunction();
853  if (!TTI.areFunctionArgsABICompatible(Caller, Callee, ArgsToPromote) ||
854  !TTI.areFunctionArgsABICompatible(Caller, Callee, ByValArgsToTransform))
855  return false;
856  }
857  return true;
858 }
859 
860 /// PromoteArguments - This method checks the specified function to see if there
861 /// are any promotable arguments and if it is safe to promote the function (for
862 /// example, all callers are direct). If safe to promote some arguments, it
863 /// calls the DoPromotion method.
864 static Function *
866  unsigned MaxElements,
867  Optional<function_ref<void(CallSite OldCS, CallSite NewCS)>>
868  ReplaceCallSite,
869  const TargetTransformInfo &TTI) {
870  // Don't perform argument promotion for naked functions; otherwise we can end
871  // up removing parameters that are seemingly 'not used' as they are referred
872  // to in the assembly.
873  if(F->hasFnAttribute(Attribute::Naked))
874  return nullptr;
875 
876  // Make sure that it is local to this module.
877  if (!F->hasLocalLinkage())
878  return nullptr;
879 
880  // Don't promote arguments for variadic functions. Adding, removing, or
881  // changing non-pack parameters can change the classification of pack
882  // parameters. Frontends encode that classification at the call site in the
883  // IR, while in the callee the classification is determined dynamically based
884  // on the number of registers consumed so far.
885  if (F->isVarArg())
886  return nullptr;
887 
888  // Don't transform functions that receive inallocas, as the transformation may
889  // not be safe depending on calling convention.
890  if (F->getAttributes().hasAttrSomewhere(Attribute::InAlloca))
891  return nullptr;
892 
893  // First check: see if there are any pointer arguments! If not, quick exit.
894  SmallVector<Argument *, 16> PointerArgs;
895  for (Argument &I : F->args())
896  if (I.getType()->isPointerTy())
897  PointerArgs.push_back(&I);
898  if (PointerArgs.empty())
899  return nullptr;
900 
901  // Second check: make sure that all callers are direct callers. We can't
902  // transform functions that have indirect callers. Also see if the function
903  // is self-recursive and check that target features are compatible.
904  bool isSelfRecursive = false;
905  for (Use &U : F->uses()) {
906  CallSite CS(U.getUser());
907  // Must be a direct call.
908  if (CS.getInstruction() == nullptr || !CS.isCallee(&U))
909  return nullptr;
910 
911  // Can't change signature of musttail callee
912  if (CS.isMustTailCall())
913  return nullptr;
914 
915  if (CS.getInstruction()->getParent()->getParent() == F)
916  isSelfRecursive = true;
917  }
918 
919  // Can't change signature of musttail caller
920  // FIXME: Support promoting whole chain of musttail functions
921  for (BasicBlock &BB : *F)
922  if (BB.getTerminatingMustTailCall())
923  return nullptr;
924 
925  const DataLayout &DL = F->getParent()->getDataLayout();
926 
927  AAResults &AAR = AARGetter(*F);
928 
929  // Check to see which arguments are promotable. If an argument is promotable,
930  // add it to ArgsToPromote.
931  SmallPtrSet<Argument *, 8> ArgsToPromote;
932  SmallPtrSet<Argument *, 8> ByValArgsToTransform;
933  for (Argument *PtrArg : PointerArgs) {
934  Type *AgTy = cast<PointerType>(PtrArg->getType())->getElementType();
935 
936  // Replace sret attribute with noalias. This reduces register pressure by
937  // avoiding a register copy.
938  if (PtrArg->hasStructRetAttr()) {
939  unsigned ArgNo = PtrArg->getArgNo();
940  F->removeParamAttr(ArgNo, Attribute::StructRet);
941  F->addParamAttr(ArgNo, Attribute::NoAlias);
942  for (Use &U : F->uses()) {
943  CallSite CS(U.getUser());
944  CS.removeParamAttr(ArgNo, Attribute::StructRet);
945  CS.addParamAttr(ArgNo, Attribute::NoAlias);
946  }
947  }
948 
949  // If this is a byval argument, and if the aggregate type is small, just
950  // pass the elements, which is always safe, if the passed value is densely
951  // packed or if we can prove the padding bytes are never accessed.
952  bool isSafeToPromote =
953  PtrArg->hasByValAttr() &&
954  (isDenselyPacked(AgTy, DL) || !canPaddingBeAccessed(PtrArg));
955  if (isSafeToPromote) {
956  if (StructType *STy = dyn_cast<StructType>(AgTy)) {
957  if (MaxElements > 0 && STy->getNumElements() > MaxElements) {
958  LLVM_DEBUG(dbgs() << "argpromotion disable promoting argument '"
959  << PtrArg->getName()
960  << "' because it would require adding more"
961  << " than " << MaxElements
962  << " arguments to the function.\n");
963  continue;
964  }
965 
966  // If all the elements are single-value types, we can promote it.
967  bool AllSimple = true;
968  for (const auto *EltTy : STy->elements()) {
969  if (!EltTy->isSingleValueType()) {
970  AllSimple = false;
971  break;
972  }
973  }
974 
975  // Safe to transform, don't even bother trying to "promote" it.
976  // Passing the elements as a scalar will allow sroa to hack on
977  // the new alloca we introduce.
978  if (AllSimple) {
979  ByValArgsToTransform.insert(PtrArg);
980  continue;
981  }
982  }
983  }
984 
985  // If the argument is a recursive type and we're in a recursive
986  // function, we could end up infinitely peeling the function argument.
987  if (isSelfRecursive) {
988  if (StructType *STy = dyn_cast<StructType>(AgTy)) {
989  bool RecursiveType = false;
990  for (const auto *EltTy : STy->elements()) {
991  if (EltTy == PtrArg->getType()) {
992  RecursiveType = true;
993  break;
994  }
995  }
996  if (RecursiveType)
997  continue;
998  }
999  }
1000 
1001  // Otherwise, see if we can promote the pointer to its value.
1002  Type *ByValTy =
1003  PtrArg->hasByValAttr() ? PtrArg->getParamByValType() : nullptr;
1004  if (isSafeToPromoteArgument(PtrArg, ByValTy, AAR, MaxElements))
1005  ArgsToPromote.insert(PtrArg);
1006  }
1007 
1008  // No promotable pointer arguments.
1009  if (ArgsToPromote.empty() && ByValArgsToTransform.empty())
1010  return nullptr;
1011 
1012  if (!areFunctionArgsABICompatible(*F, TTI, ArgsToPromote,
1013  ByValArgsToTransform))
1014  return nullptr;
1015 
1016  return doPromotion(F, ArgsToPromote, ByValArgsToTransform, ReplaceCallSite);
1017 }
1018 
1021  LazyCallGraph &CG,
1022  CGSCCUpdateResult &UR) {
1023  bool Changed = false, LocalChange;
1024 
1025  // Iterate until we stop promoting from this SCC.
1026  do {
1027  LocalChange = false;
1028 
1029  for (LazyCallGraph::Node &N : C) {
1030  Function &OldF = N.getFunction();
1031 
1033  AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
1034  // FIXME: This lambda must only be used with this function. We should
1035  // skip the lambda and just get the AA results directly.
1036  auto AARGetter = [&](Function &F) -> AAResults & {
1037  assert(&F == &OldF && "Called with an unexpected function!");
1038  return FAM.getResult<AAManager>(F);
1039  };
1040 
1041  const TargetTransformInfo &TTI = FAM.getResult<TargetIRAnalysis>(OldF);
1042  Function *NewF =
1043  promoteArguments(&OldF, AARGetter, MaxElements, None, TTI);
1044  if (!NewF)
1045  continue;
1046  LocalChange = true;
1047 
1048  // Directly substitute the functions in the call graph. Note that this
1049  // requires the old function to be completely dead and completely
1050  // replaced by the new function. It does no call graph updates, it merely
1051  // swaps out the particular function mapped to a particular node in the
1052  // graph.
1053  C.getOuterRefSCC().replaceNodeFunction(N, *NewF);
1054  OldF.eraseFromParent();
1055  }
1056 
1057  Changed |= LocalChange;
1058  } while (LocalChange);
1059 
1060  if (!Changed)
1061  return PreservedAnalyses::all();
1062 
1063  return PreservedAnalyses::none();
1064 }
1065 
1066 namespace {
1067 
1068 /// ArgPromotion - The 'by reference' to 'by value' argument promotion pass.
1069 struct ArgPromotion : public CallGraphSCCPass {
1070  // Pass identification, replacement for typeid
1071  static char ID;
1072 
1073  explicit ArgPromotion(unsigned MaxElements = 3)
1074  : CallGraphSCCPass(ID), MaxElements(MaxElements) {
1076  }
1077 
1078  void getAnalysisUsage(AnalysisUsage &AU) const override {
1084  }
1085 
1086  bool runOnSCC(CallGraphSCC &SCC) override;
1087 
1088 private:
1090 
1091  bool doInitialization(CallGraph &CG) override;
1092 
1093  /// The maximum number of elements to expand, or 0 for unlimited.
1094  unsigned MaxElements;
1095 };
1096 
1097 } // end anonymous namespace
1098 
1099 char ArgPromotion::ID = 0;
1100 
1101 INITIALIZE_PASS_BEGIN(ArgPromotion, "argpromotion",
1102  "Promote 'by reference' arguments to scalars", false,
1103  false)
1109  "Promote 'by reference' arguments to scalars", false, false)
1110 
1111 Pass *llvm::createArgumentPromotionPass(unsigned MaxElements) {
1112  return new ArgPromotion(MaxElements);
1113 }
1114 
1115 bool ArgPromotion::runOnSCC(CallGraphSCC &SCC) {
1116  if (skipSCC(SCC))
1117  return false;
1118 
1119  // Get the callgraph information that we need to update to reflect our
1120  // changes.
1121  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
1122 
1123  LegacyAARGetter AARGetter(*this);
1124 
1125  bool Changed = false, LocalChange;
1126 
1127  // Iterate until we stop promoting from this SCC.
1128  do {
1129  LocalChange = false;
1130  // Attempt to promote arguments from all functions in this SCC.
1131  for (CallGraphNode *OldNode : SCC) {
1132  Function *OldF = OldNode->getFunction();
1133  if (!OldF)
1134  continue;
1135 
1136  auto ReplaceCallSite = [&](CallSite OldCS, CallSite NewCS) {
1137  Function *Caller = OldCS.getInstruction()->getParent()->getParent();
1138  CallGraphNode *NewCalleeNode =
1139  CG.getOrInsertFunction(NewCS.getCalledFunction());
1140  CallGraphNode *CallerNode = CG[Caller];
1141  CallerNode->replaceCallEdge(*cast<CallBase>(OldCS.getInstruction()),
1142  *cast<CallBase>(NewCS.getInstruction()),
1143  NewCalleeNode);
1144  };
1145 
1146  const TargetTransformInfo &TTI =
1147  getAnalysis<TargetTransformInfoWrapperPass>().getTTI(*OldF);
1148  if (Function *NewF = promoteArguments(OldF, AARGetter, MaxElements,
1149  {ReplaceCallSite}, TTI)) {
1150  LocalChange = true;
1151 
1152  // Update the call graph for the newly promoted function.
1153  CallGraphNode *NewNode = CG.getOrInsertFunction(NewF);
1154  NewNode->stealCalledFunctionsFrom(OldNode);
1155  if (OldNode->getNumReferences() == 0)
1156  delete CG.removeFunctionFromModule(OldNode);
1157  else
1159 
1160  // And updat ethe SCC we're iterating as well.
1161  SCC.ReplaceNode(OldNode, NewNode);
1162  }
1163  }
1164  // Remember that we changed something.
1165  Changed |= LocalChange;
1166  } while (LocalChange);
1167 
1168  return Changed;
1169 }
1170 
1171 bool ArgPromotion::doInitialization(CallGraph &CG) {
1173 }
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:1576
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:704
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:779
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 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:695
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:1436
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:1677
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.
bool isDereferenceablePointer(const Value *V, Type *Ty, const DataLayout &DL, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr)
Return true if this is always a dereferenceable pointer.
Definition: Loads.cpp:152
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:643
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
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:657
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.
static bool isSafeToPromoteArgument(Argument *Arg, Type *ByValTy, AAResults &AAR, unsigned MaxElements)
isSafeToPromoteArgument - As you might guess from the name of this method, it checks to see if it is ...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:375
const BasicBlock & front() const
Definition: Function.h:687
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.
static bool allCallersPassValidPointerForArgument(Argument *Arg, Type *Ty)
Return true if we can prove that all callees pass in a valid pointer for the specified function argum...
#define LLVM_DEBUG(X)
Definition: Debug.h:122
bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc)
Check if it is possible for execution of the specified basic block to modify the location Loc...
bool use_empty() const
Definition: Value.h: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:973
iterator_range< arg_iterator > args()
Definition: Function.h:713
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