LLVM  12.0.0git
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"
21 #include "llvm/IR/Constants.h"
22 #include "llvm/IR/Instructions.h"
23 #include "llvm/IR/Module.h"
24 #include "llvm/InitializePasses.h"
25 #include "llvm/Pass.h"
26 #include "llvm/Transforms/IPO.h"
27 using namespace llvm;
28 
29 #define DEBUG_TYPE "ipconstprop"
30 
31 STATISTIC(NumArgumentsProped, "Number of args turned into constants");
32 STATISTIC(NumReturnValProped, "Number of return values turned into constants");
33 
34 namespace {
35  /// IPCP - The interprocedural constant propagation pass
36  ///
37  struct IPCP : public ModulePass {
38  static char ID; // Pass identification, replacement for typeid
39  IPCP() : ModulePass(ID) {
41  }
42 
43  bool runOnModule(Module &M) override;
44  };
45 }
46 
47 /// PropagateConstantsIntoArguments - Look at all uses of the specified
48 /// function. If all uses are direct call sites, and all pass a particular
49 /// constant in for an argument, propagate that constant in as the argument.
50 ///
52  if (F.arg_empty() || F.use_empty()) return false; // No arguments? Early exit.
53 
54  // For each argument, keep track of its constant value and whether it is a
55  // constant or not. The bool is driven to true when found to be non-constant.
57  ArgumentConstants.resize(F.arg_size());
58 
59  unsigned NumNonconstant = 0;
60  for (Use &U : F.uses()) {
61  User *UR = U.getUser();
62  // Ignore blockaddress uses.
63  if (isa<BlockAddress>(UR)) continue;
64 
65  // If no abstract call site was created we did not understand the use, bail.
66  AbstractCallSite ACS(&U);
67  if (!ACS)
68  return false;
69 
70  // Mismatched argument count is undefined behavior. Simply bail out to avoid
71  // handling of such situations below (avoiding asserts/crashes).
72  unsigned NumActualArgs = ACS.getNumArgOperands();
73  if (F.isVarArg() ? ArgumentConstants.size() > NumActualArgs
74  : ArgumentConstants.size() != NumActualArgs)
75  return false;
76 
77  // Check out all of the potentially constant arguments. Note that we don't
78  // inspect varargs here.
80  for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++Arg) {
81 
82  // If this argument is known non-constant, ignore it.
83  if (ArgumentConstants[i].getInt())
84  continue;
85 
86  Value *V = ACS.getCallArgOperand(i);
87  Constant *C = dyn_cast_or_null<Constant>(V);
88 
89  // Mismatched argument type is undefined behavior. Simply bail out to avoid
90  // handling of such situations below (avoiding asserts/crashes).
91  if (C && Arg->getType() != C->getType())
92  return false;
93 
94  // We can only propagate thread independent values through callbacks.
95  // This is different to direct/indirect call sites because for them we
96  // know the thread executing the caller and callee is the same. For
97  // callbacks this is not guaranteed, thus a thread dependent value could
98  // be different for the caller and callee, making it invalid to propagate.
99  if (C && ACS.isCallbackCall() && C->isThreadDependent()) {
100  // Argument became non-constant. If all arguments are non-constant now,
101  // give up on this function.
102  if (++NumNonconstant == ArgumentConstants.size())
103  return false;
104 
105  ArgumentConstants[i].setInt(true);
106  continue;
107  }
108 
109  if (C && ArgumentConstants[i].getPointer() == nullptr) {
110  ArgumentConstants[i].setPointer(C); // First constant seen.
111  } else if (C && ArgumentConstants[i].getPointer() == C) {
112  // Still the constant value we think it is.
113  } else if (V == &*Arg) {
114  // Ignore recursive calls passing argument down.
115  } else {
116  // Argument became non-constant. If all arguments are non-constant now,
117  // give up on this function.
118  if (++NumNonconstant == ArgumentConstants.size())
119  return false;
120  ArgumentConstants[i].setInt(true);
121  }
122  }
123  }
124 
125  // If we got to this point, there is a constant argument!
126  assert(NumNonconstant != ArgumentConstants.size());
127  bool MadeChange = false;
129  for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI) {
130  // Do we have a constant argument?
131  if (ArgumentConstants[i].getInt() || AI->use_empty() ||
132  (AI->hasByValAttr() && !F.onlyReadsMemory()))
133  continue;
134 
135  Value *V = ArgumentConstants[i].getPointer();
136  if (!V) V = UndefValue::get(AI->getType());
137  AI->replaceAllUsesWith(V);
138  ++NumArgumentsProped;
139  MadeChange = true;
140  }
141  return MadeChange;
142 }
143 
144 
145 // Check to see if this function returns one or more constants. If so, replace
146 // all callers that use those return values with the constant value. This will
147 // leave in the actual return values and instructions, but deadargelim will
148 // clean that up.
149 //
150 // Additionally if a function always returns one of its arguments directly,
151 // callers will be updated to use the value they pass in directly instead of
152 // using the return value.
154  if (F.getReturnType()->isVoidTy())
155  return false; // No return value.
156 
157  // We can infer and propagate the return value only when we know that the
158  // definition we'll get at link time is *exactly* the definition we see now.
159  // For more details, see GlobalValue::mayBeDerefined.
160  if (!F.isDefinitionExact())
161  return false;
162 
163  // Don't touch naked functions. The may contain asm returning
164  // value we don't see, so we may end up interprocedurally propagating
165  // the return value incorrectly.
166  if (F.hasFnAttribute(Attribute::Naked))
167  return false;
168 
169  // Check to see if this function returns a constant.
170  SmallVector<Value *,4> RetVals;
172  if (STy)
173  for (unsigned i = 0, e = STy->getNumElements(); i < e; ++i)
174  RetVals.push_back(UndefValue::get(STy->getElementType(i)));
175  else
177 
178  unsigned NumNonConstant = 0;
179  for (BasicBlock &BB : F)
180  if (ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator())) {
181  for (unsigned i = 0, e = RetVals.size(); i != e; ++i) {
182  // Already found conflicting return values?
183  Value *RV = RetVals[i];
184  if (!RV)
185  continue;
186 
187  // Find the returned value
188  Value *V;
189  if (!STy)
190  V = RI->getOperand(0);
191  else
192  V = FindInsertedValue(RI->getOperand(0), i);
193 
194  if (V) {
195  // Ignore undefs, we can change them into anything
196  if (isa<UndefValue>(V))
197  continue;
198 
199  // Try to see if all the rets return the same constant or argument.
200  if (isa<Constant>(V) || isa<Argument>(V)) {
201  if (isa<UndefValue>(RV)) {
202  // No value found yet? Try the current one.
203  RetVals[i] = V;
204  continue;
205  }
206  // Returning the same value? Good.
207  if (RV == V)
208  continue;
209  }
210  }
211  // Different or no known return value? Don't propagate this return
212  // value.
213  RetVals[i] = nullptr;
214  // All values non-constant? Stop looking.
215  if (++NumNonConstant == RetVals.size())
216  return false;
217  }
218  }
219 
220  // If we got here, the function returns at least one constant value. Loop
221  // over all users, replacing any uses of the return value with the returned
222  // constant.
223  bool MadeChange = false;
224  for (Use &U : F.uses()) {
225  CallBase *CB = dyn_cast<CallBase>(U.getUser());
226 
227  // Not a call instruction or a call instruction that's not calling F
228  // directly?
229  if (!CB || !CB->isCallee(&U))
230  continue;
231 
232  // Call result not used?
233  if (CB->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 = CB->getArgOperand(A->getArgNo());
244  CB->replaceAllUsesWith(New);
245  continue;
246  }
247 
248  for (auto I = CB->user_begin(), E = CB->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->getNumIndices() == 1)
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 = CB->getArgOperand(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:178
bool onlyReadsMemory() const
Determine if the function does not access or only reads memory.
Definition: Function.h:506
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:80
ModulePass * createIPConstantPropagationPass()
createIPConstantPropagationPass - This pass propagates constants from call sites into the bodies of f...
iterator_range< use_iterator > uses()
Definition: Value.h:373
LLVM_NODISCARD std::enable_if_t< !is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > dyn_cast(const Y &Val)
Definition: Casting.h:334
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:329
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:67
unsigned getNumElements() const
Random access to the elements.
Definition: DerivedTypes.h:328
void push_back(const T &Elt)
Definition: SmallVector.h:246
Value * getCallArgOperand(Argument &Arg) const
Return the operand of the underlying instruction associated with Arg.
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:330
STATISTIC(NumFunctions, "Total number of functions")
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1100
F(f)
bool hasByValAttr() const
Return true if this argument has the byval attribute.
Definition: Function.cpp:100
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1259
static unsigned getInt(StringRef R)
Get an unsigned integer, including error checks.
Definition: DataLayout.cpp:211
Class to represent struct types.
Definition: DerivedTypes.h:218
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
bool arg_empty() const
Definition: Function.h:754
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:486
bool isVoidTy() const
Return true if this is &#39;void&#39;.
Definition: Type.h:138
bool isThreadDependent() const
Return true if the value can vary between threads.
Definition: Constants.cpp:597
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:170
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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...
constexpr double e
Definition: MathExtras.h:58
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
size_t arg_size() const
Definition: Function.h:753
arg_iterator arg_begin()
Definition: Function.h:720
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1665
unsigned getNumArgOperands() const
Return the number of parameters of the callee.
Value * FindInsertedValue(Value *V, ArrayRef< unsigned > idx_range, Instruction *InsertBefore=nullptr)
Given an aggregate and an sequence of indices, see if the scalar value indexed is already around as a...
bool isDefinitionExact() const
Return true if the currently visible definition of this global (if any) is exactly the definition we ...
Definition: GlobalValue.h:410
bool isCallee(Value::const_user_iterator UI) const
Determine whether the passed iterator points to the callee operand&#39;s Use.
Definition: InstrTypes.h:1322
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:883
Module.h This file contains the declarations for the Module class.
bool isCallbackCall() const
Return true if this ACS represents a callback call.
static bool PropagateConstantReturn(Function &F)
#define I(x, y, z)
Definition: MD5.cpp:59
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:224
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:394
AbstractCallSite.
LLVM Value Representation.
Definition: Value.h:74
bool use_empty() const
Definition: Value.h:341
void resize(size_type N)
Definition: SmallVector.h:390
user_iterator user_end()
Definition: Value.h:402