LLVM  10.0.0svn
IPConstantPropagation.cpp
Go to the documentation of this file.
1 //===-- IPConstantPropagation.cpp - Propagate constants through calls -----===//
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 implements an _extremely_ simple interprocedural constant
10 // propagation pass. It could certainly be improved in many different ways,
11 // like using a worklist. This pass makes arguments dead, but does not remove
12 // them. The existing dead argument elimination pass should be run after this
13 // to clean up the mess.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/Statistic.h"
20 #include "llvm/IR/CallSite.h"
21 #include "llvm/IR/Constants.h"
22 #include "llvm/IR/Instructions.h"
23 #include "llvm/IR/Module.h"
24 #include "llvm/Pass.h"
25 #include "llvm/Transforms/IPO.h"
26 using namespace llvm;
27 
28 #define DEBUG_TYPE "ipconstprop"
29 
30 STATISTIC(NumArgumentsProped, "Number of args turned into constants");
31 STATISTIC(NumReturnValProped, "Number of return values turned into constants");
32 
33 namespace {
34  /// IPCP - The interprocedural constant propagation pass
35  ///
36  struct IPCP : public ModulePass {
37  static char ID; // Pass identification, replacement for typeid
38  IPCP() : ModulePass(ID) {
40  }
41 
42  bool runOnModule(Module &M) override;
43  };
44 }
45 
46 /// PropagateConstantsIntoArguments - Look at all uses of the specified
47 /// function. If all uses are direct call sites, and all pass a particular
48 /// constant in for an argument, propagate that constant in as the argument.
49 ///
51  if (F.arg_empty() || F.use_empty()) return false; // No arguments? Early exit.
52 
53  // For each argument, keep track of its constant value and whether it is a
54  // constant or not. The bool is driven to true when found to be non-constant.
55  SmallVector<std::pair<Constant*, bool>, 16> ArgumentConstants;
56  ArgumentConstants.resize(F.arg_size());
57 
58  unsigned NumNonconstant = 0;
59  for (Use &U : F.uses()) {
60  User *UR = U.getUser();
61  // Ignore blockaddress uses.
62  if (isa<BlockAddress>(UR)) continue;
63 
64  // If no abstract call site was created we did not understand the use, bail.
65  AbstractCallSite ACS(&U);
66  if (!ACS)
67  return false;
68 
69  // Mismatched argument count is undefined behavior. Simply bail out to avoid
70  // handling of such situations below (avoiding asserts/crashes).
71  unsigned NumActualArgs = ACS.getNumArgOperands();
72  if (F.isVarArg() ? ArgumentConstants.size() > NumActualArgs
73  : ArgumentConstants.size() != NumActualArgs)
74  return false;
75 
76  // Check out all of the potentially constant arguments. Note that we don't
77  // inspect varargs here.
79  for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++Arg) {
80 
81  // If this argument is known non-constant, ignore it.
82  if (ArgumentConstants[i].second)
83  continue;
84 
85  Value *V = ACS.getCallArgOperand(i);
86  Constant *C = dyn_cast_or_null<Constant>(V);
87 
88  // Mismatched argument type is undefined behavior. Simply bail out to avoid
89  // handling of such situations below (avoiding asserts/crashes).
90  if (C && Arg->getType() != C->getType())
91  return false;
92 
93  // We can only propagate thread independent values through callbacks.
94  // This is different to direct/indirect call sites because for them we
95  // know the thread executing the caller and callee is the same. For
96  // callbacks this is not guaranteed, thus a thread dependent value could
97  // be different for the caller and callee, making it invalid to propagate.
98  if (C && ACS.isCallbackCall() && C->isThreadDependent()) {
99  // Argument became non-constant. If all arguments are non-constant now,
100  // give up on this function.
101  if (++NumNonconstant == ArgumentConstants.size())
102  return false;
103 
104  ArgumentConstants[i].second = true;
105  continue;
106  }
107 
108  if (C && ArgumentConstants[i].first == nullptr) {
109  ArgumentConstants[i].first = C; // First constant seen.
110  } else if (C && ArgumentConstants[i].first == C) {
111  // Still the constant value we think it is.
112  } else if (V == &*Arg) {
113  // Ignore recursive calls passing argument down.
114  } else {
115  // Argument became non-constant. If all arguments are non-constant now,
116  // give up on this function.
117  if (++NumNonconstant == ArgumentConstants.size())
118  return false;
119  ArgumentConstants[i].second = true;
120  }
121  }
122  }
123 
124  // If we got to this point, there is a constant argument!
125  assert(NumNonconstant != ArgumentConstants.size());
126  bool MadeChange = false;
128  for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI) {
129  // Do we have a constant argument?
130  if (ArgumentConstants[i].second || AI->use_empty() ||
131  AI->hasInAllocaAttr() || (AI->hasByValAttr() && !F.onlyReadsMemory()))
132  continue;
133 
134  Value *V = ArgumentConstants[i].first;
135  if (!V) V = UndefValue::get(AI->getType());
136  AI->replaceAllUsesWith(V);
137  ++NumArgumentsProped;
138  MadeChange = true;
139  }
140  return MadeChange;
141 }
142 
143 
144 // Check to see if this function returns one or more constants. If so, replace
145 // all callers that use those return values with the constant value. This will
146 // leave in the actual return values and instructions, but deadargelim will
147 // clean that up.
148 //
149 // Additionally if a function always returns one of its arguments directly,
150 // callers will be updated to use the value they pass in directly instead of
151 // using the return value.
153  if (F.getReturnType()->isVoidTy())
154  return false; // No return value.
155 
156  // We can infer and propagate the return value only when we know that the
157  // definition we'll get at link time is *exactly* the definition we see now.
158  // For more details, see GlobalValue::mayBeDerefined.
159  if (!F.isDefinitionExact())
160  return false;
161 
162  // Don't touch naked functions. The may contain asm returning
163  // value we don't see, so we may end up interprocedurally propagating
164  // the return value incorrectly.
165  if (F.hasFnAttribute(Attribute::Naked))
166  return false;
167 
168  // Check to see if this function returns a constant.
169  SmallVector<Value *,4> RetVals;
171  if (STy)
172  for (unsigned i = 0, e = STy->getNumElements(); i < e; ++i)
173  RetVals.push_back(UndefValue::get(STy->getElementType(i)));
174  else
176 
177  unsigned NumNonConstant = 0;
178  for (BasicBlock &BB : F)
179  if (ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator())) {
180  for (unsigned i = 0, e = RetVals.size(); i != e; ++i) {
181  // Already found conflicting return values?
182  Value *RV = RetVals[i];
183  if (!RV)
184  continue;
185 
186  // Find the returned value
187  Value *V;
188  if (!STy)
189  V = RI->getOperand(0);
190  else
191  V = FindInsertedValue(RI->getOperand(0), i);
192 
193  if (V) {
194  // Ignore undefs, we can change them into anything
195  if (isa<UndefValue>(V))
196  continue;
197 
198  // Try to see if all the rets return the same constant or argument.
199  if (isa<Constant>(V) || isa<Argument>(V)) {
200  if (isa<UndefValue>(RV)) {
201  // No value found yet? Try the current one.
202  RetVals[i] = V;
203  continue;
204  }
205  // Returning the same value? Good.
206  if (RV == V)
207  continue;
208  }
209  }
210  // Different or no known return value? Don't propagate this return
211  // value.
212  RetVals[i] = nullptr;
213  // All values non-constant? Stop looking.
214  if (++NumNonConstant == RetVals.size())
215  return false;
216  }
217  }
218 
219  // If we got here, the function returns at least one constant value. Loop
220  // over all users, replacing any uses of the return value with the returned
221  // constant.
222  bool MadeChange = false;
223  for (Use &U : F.uses()) {
224  CallSite CS(U.getUser());
225  Instruction* Call = CS.getInstruction();
226 
227  // Not a call instruction or a call instruction that's not calling F
228  // directly?
229  if (!Call || !CS.isCallee(&U))
230  continue;
231 
232  // Call result not used?
233  if (Call->use_empty())
234  continue;
235 
236  MadeChange = true;
237 
238  if (!STy) {
239  Value* New = RetVals[0];
240  if (Argument *A = dyn_cast<Argument>(New))
241  // Was an argument returned? Then find the corresponding argument in
242  // the call instruction and use that.
243  New = CS.getArgument(A->getArgNo());
244  Call->replaceAllUsesWith(New);
245  continue;
246  }
247 
248  for (auto I = Call->user_begin(), E = Call->user_end(); I != E;) {
249  Instruction *Ins = cast<Instruction>(*I);
250 
251  // Increment now, so we can remove the use
252  ++I;
253 
254  // Find the index of the retval to replace with
255  int index = -1;
256  if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Ins))
257  if (EV->hasIndices())
258  index = *EV->idx_begin();
259 
260  // If this use uses a specific return value, and we have a replacement,
261  // replace it.
262  if (index != -1) {
263  Value *New = RetVals[index];
264  if (New) {
265  if (Argument *A = dyn_cast<Argument>(New))
266  // Was an argument returned? Then find the corresponding argument in
267  // the call instruction and use that.
268  New = CS.getArgument(A->getArgNo());
269  Ins->replaceAllUsesWith(New);
270  Ins->eraseFromParent();
271  }
272  }
273  }
274  }
275 
276  if (MadeChange) ++NumReturnValProped;
277  return MadeChange;
278 }
279 
280 char IPCP::ID = 0;
281 INITIALIZE_PASS(IPCP, "ipconstprop",
282  "Interprocedural constant propagation", false, false)
283 
284 ModulePass *llvm::createIPConstantPropagationPass() { return new IPCP(); }
285 
286 bool IPCP::runOnModule(Module &M) {
287  if (skipModule(M))
288  return false;
289 
290  bool Changed = false;
291  bool LocalChange = true;
292 
293  // FIXME: instead of using smart algorithms, we just iterate until we stop
294  // making changes.
295  while (LocalChange) {
296  LocalChange = false;
297  for (Function &F : M)
298  if (!F.isDeclaration()) {
299  // Delete any klingons.
300  F.removeDeadConstantUsers();
301  if (F.hasLocalLinkage())
302  LocalChange |= PropagateConstantsIntoArguments(F);
303  Changed |= PropagateConstantReturn(F);
304  }
305  Changed |= LocalChange;
306  }
307  return Changed;
308 }
bool isVarArg() const
isVarArg - Return true if this function takes a variable number of arguments.
Definition: Function.h:176
bool onlyReadsMemory() const
Determine if the function does not access or only reads memory.
Definition: Function.h:481
uint64_t CallInst * C
Return a value (possibly void), from a function.
void initializeIPCPPass(PassRegistry &)
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
ModulePass * createIPConstantPropagationPass()
createIPConstantPropagationPass - This pass propagates constants from call sites into the bodies of f...
iterator_range< use_iterator > uses()
Definition: Value.h:374
This instruction extracts a struct member or array element value from an aggregate value...
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
static bool PropagateConstantsIntoArguments(Function &F)
PropagateConstantsIntoArguments - Look at all uses of the specified function.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Type * getElementType(unsigned N) const
Definition: DerivedTypes.h:346
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
unsigned getNumElements() const
Random access to the elements.
Definition: DerivedTypes.h:345
Value * getCallArgOperand(Argument &Arg) const
Return the operand of the underlying instruction associated with Arg.
Definition: CallSite.h:834
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:323
unsigned second
STATISTIC(NumFunctions, "Total number of functions")
F(f)
bool hasByValAttr() const
Return true if this argument has the byval attribute.
Definition: Function.cpp:86
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
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
bool arg_empty() const
Definition: Function.h:729
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
bool isVoidTy() const
Return true if this is &#39;void&#39;.
Definition: Type.h:140
bool isThreadDependent() const
Return true if the value can vary between threads.
Definition: Constants.cpp:487
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:168
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:41
INITIALIZE_PASS(IPCP, "ipconstprop", "Interprocedural constant propagation", false, false) ModulePass *llvm
This file contains the declarations for the subclasses of Constant, which represent the different fla...
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
size_t arg_size() const
Definition: Function.h:728
arg_iterator arg_begin()
Definition: Function.h:695
bool hasInAllocaAttr() const
Return true if this argument has the inalloca attribute.
Definition: Function.cpp:99
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1446
size_t size() const
Definition: SmallVector.h:52
unsigned getNumArgOperands() const
Return the number of parameters of the callee.
Definition: CallSite.h:811
unsigned first
Value * FindInsertedValue(Value *V, ArrayRef< unsigned > idx_range, Instruction *InsertBefore=nullptr)
Given an aggregrate and an sequence of indices, see if the scalar value indexed is already around as ...
bool isDefinitionExact() const
Return true if the currently visible definition of this global (if any) is exactly the definition we ...
Definition: GlobalValue.h:411
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.
bool isCallbackCall() const
Return true if this ACS represents a callback call.
Definition: CallSite.h:788
static bool PropagateConstantReturn(Function &F)
#define I(x, y, z)
Definition: MD5.cpp:58
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:224
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
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
AbstractCallSite.
Definition: CallSite.h:718
LLVM Value Representation.
Definition: Value.h:73
bool use_empty() const
Definition: Value.h:342
void resize(size_type N)
Definition: SmallVector.h:344