LLVM  9.0.0svn
IPConstantPropagation.cpp
Go to the documentation of this file.
1 //===-- IPConstantPropagation.cpp - Propagate constants through calls -----===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass implements an _extremely_ simple interprocedural constant
11 // propagation pass. It could certainly be improved in many different ways,
12 // like using a worklist. This pass makes arguments dead, but does not remove
13 // them. The existing dead argument elimination pass should be run after this
14 // to clean up the mess.
15 //
16 //===----------------------------------------------------------------------===//
17 
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Statistic.h"
21 #include "llvm/IR/CallSite.h"
22 #include "llvm/IR/Constants.h"
23 #include "llvm/IR/Instructions.h"
24 #include "llvm/IR/Module.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.
56  SmallVector<std::pair<Constant*, bool>, 16> ArgumentConstants;
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  // Check out all of the potentially constant arguments. Note that we don't
71  // inspect varargs here.
73  for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++Arg) {
74 
75  // If this argument is known non-constant, ignore it.
76  if (ArgumentConstants[i].second)
77  continue;
78 
79  Value *V = ACS.getCallArgOperand(i);
80  Constant *C = dyn_cast_or_null<Constant>(V);
81 
82  // We can only propagate thread independent values through callbacks.
83  // This is different to direct/indirect call sites because for them we
84  // know the thread executing the caller and callee is the same. For
85  // callbacks this is not guaranteed, thus a thread dependent value could
86  // be different for the caller and callee, making it invalid to propagate.
87  if (C && ACS.isCallbackCall() && C->isThreadDependent()) {
88  // Argument became non-constant. If all arguments are non-constant now,
89  // give up on this function.
90  if (++NumNonconstant == ArgumentConstants.size())
91  return false;
92 
93  ArgumentConstants[i].second = true;
94  continue;
95  }
96 
97  if (C && ArgumentConstants[i].first == nullptr) {
98  ArgumentConstants[i].first = C; // First constant seen.
99  } else if (C && ArgumentConstants[i].first == C) {
100  // Still the constant value we think it is.
101  } else if (V == &*Arg) {
102  // Ignore recursive calls passing argument down.
103  } else {
104  // Argument became non-constant. If all arguments are non-constant now,
105  // give up on this function.
106  if (++NumNonconstant == ArgumentConstants.size())
107  return false;
108  ArgumentConstants[i].second = true;
109  }
110  }
111  }
112 
113  // If we got to this point, there is a constant argument!
114  assert(NumNonconstant != ArgumentConstants.size());
115  bool MadeChange = false;
117  for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI) {
118  // Do we have a constant argument?
119  if (ArgumentConstants[i].second || AI->use_empty() ||
120  AI->hasInAllocaAttr() || (AI->hasByValAttr() && !F.onlyReadsMemory()))
121  continue;
122 
123  Value *V = ArgumentConstants[i].first;
124  if (!V) V = UndefValue::get(AI->getType());
125  AI->replaceAllUsesWith(V);
126  ++NumArgumentsProped;
127  MadeChange = true;
128  }
129  return MadeChange;
130 }
131 
132 
133 // Check to see if this function returns one or more constants. If so, replace
134 // all callers that use those return values with the constant value. This will
135 // leave in the actual return values and instructions, but deadargelim will
136 // clean that up.
137 //
138 // Additionally if a function always returns one of its arguments directly,
139 // callers will be updated to use the value they pass in directly instead of
140 // using the return value.
142  if (F.getReturnType()->isVoidTy())
143  return false; // No return value.
144 
145  // We can infer and propagate the return value only when we know that the
146  // definition we'll get at link time is *exactly* the definition we see now.
147  // For more details, see GlobalValue::mayBeDerefined.
148  if (!F.isDefinitionExact())
149  return false;
150 
151  // Don't touch naked functions. The may contain asm returning
152  // value we don't see, so we may end up interprocedurally propagating
153  // the return value incorrectly.
154  if (F.hasFnAttribute(Attribute::Naked))
155  return false;
156 
157  // Check to see if this function returns a constant.
158  SmallVector<Value *,4> RetVals;
160  if (STy)
161  for (unsigned i = 0, e = STy->getNumElements(); i < e; ++i)
162  RetVals.push_back(UndefValue::get(STy->getElementType(i)));
163  else
165 
166  unsigned NumNonConstant = 0;
167  for (BasicBlock &BB : F)
168  if (ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator())) {
169  for (unsigned i = 0, e = RetVals.size(); i != e; ++i) {
170  // Already found conflicting return values?
171  Value *RV = RetVals[i];
172  if (!RV)
173  continue;
174 
175  // Find the returned value
176  Value *V;
177  if (!STy)
178  V = RI->getOperand(0);
179  else
180  V = FindInsertedValue(RI->getOperand(0), i);
181 
182  if (V) {
183  // Ignore undefs, we can change them into anything
184  if (isa<UndefValue>(V))
185  continue;
186 
187  // Try to see if all the rets return the same constant or argument.
188  if (isa<Constant>(V) || isa<Argument>(V)) {
189  if (isa<UndefValue>(RV)) {
190  // No value found yet? Try the current one.
191  RetVals[i] = V;
192  continue;
193  }
194  // Returning the same value? Good.
195  if (RV == V)
196  continue;
197  }
198  }
199  // Different or no known return value? Don't propagate this return
200  // value.
201  RetVals[i] = nullptr;
202  // All values non-constant? Stop looking.
203  if (++NumNonConstant == RetVals.size())
204  return false;
205  }
206  }
207 
208  // If we got here, the function returns at least one constant value. Loop
209  // over all users, replacing any uses of the return value with the returned
210  // constant.
211  bool MadeChange = false;
212  for (Use &U : F.uses()) {
213  CallSite CS(U.getUser());
214  Instruction* Call = CS.getInstruction();
215 
216  // Not a call instruction or a call instruction that's not calling F
217  // directly?
218  if (!Call || !CS.isCallee(&U))
219  continue;
220 
221  // Call result not used?
222  if (Call->use_empty())
223  continue;
224 
225  MadeChange = true;
226 
227  if (!STy) {
228  Value* New = RetVals[0];
229  if (Argument *A = dyn_cast<Argument>(New))
230  // Was an argument returned? Then find the corresponding argument in
231  // the call instruction and use that.
232  New = CS.getArgument(A->getArgNo());
233  Call->replaceAllUsesWith(New);
234  continue;
235  }
236 
237  for (auto I = Call->user_begin(), E = Call->user_end(); I != E;) {
238  Instruction *Ins = cast<Instruction>(*I);
239 
240  // Increment now, so we can remove the use
241  ++I;
242 
243  // Find the index of the retval to replace with
244  int index = -1;
245  if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Ins))
246  if (EV->hasIndices())
247  index = *EV->idx_begin();
248 
249  // If this use uses a specific return value, and we have a replacement,
250  // replace it.
251  if (index != -1) {
252  Value *New = RetVals[index];
253  if (New) {
254  if (Argument *A = dyn_cast<Argument>(New))
255  // Was an argument returned? Then find the corresponding argument in
256  // the call instruction and use that.
257  New = CS.getArgument(A->getArgNo());
258  Ins->replaceAllUsesWith(New);
259  Ins->eraseFromParent();
260  }
261  }
262  }
263  }
264 
265  if (MadeChange) ++NumReturnValProped;
266  return MadeChange;
267 }
268 
269 char IPCP::ID = 0;
270 INITIALIZE_PASS(IPCP, "ipconstprop",
271  "Interprocedural constant propagation", false, false)
272 
273 ModulePass *llvm::createIPConstantPropagationPass() { return new IPCP(); }
274 
275 bool IPCP::runOnModule(Module &M) {
276  if (skipModule(M))
277  return false;
278 
279  bool Changed = false;
280  bool LocalChange = true;
281 
282  // FIXME: instead of using smart algorithms, we just iterate until we stop
283  // making changes.
284  while (LocalChange) {
285  LocalChange = false;
286  for (Function &F : M)
287  if (!F.isDeclaration()) {
288  // Delete any klingons.
289  F.removeDeadConstantUsers();
290  if (F.hasLocalLinkage())
291  LocalChange |= PropagateConstantsIntoArguments(F);
292  Changed |= PropagateConstantReturn(F);
293  }
294  Changed |= LocalChange;
295  }
296  return Changed;
297 }
bool onlyReadsMemory() const
Determine if the function does not access or only reads memory.
Definition: Function.h:468
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:68
ModulePass * createIPConstantPropagationPass()
createIPConstantPropagationPass - This pass propagates constants from call sites into the bodies of f...
iterator_range< use_iterator > uses()
Definition: Value.h:355
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:30
static bool PropagateConstantsIntoArguments(Function &F)
PropagateConstantsIntoArguments - Look at all uses of the specified function.
This class represents lattice values for constants.
Definition: AllocatorList.h:24
Type * getElementType(unsigned N) const
Definition: DerivedTypes.h:314
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:313
Value * getCallArgOperand(Argument &Arg) const
Return the operand of the underlying instruction associated with Arg.
Definition: CallSite.h:824
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:321
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:87
Class to represent struct types.
Definition: DerivedTypes.h:201
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
bool arg_empty() const
Definition: Function.h:699
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:141
bool isThreadDependent() const
Return true if the value can vary between threads.
Definition: Constants.cpp:463
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:169
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:42
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...
size_t arg_size() const
Definition: Function.h:698
arg_iterator arg_begin()
Definition: Function.h:671
bool hasInAllocaAttr() const
Return true if this argument has the inalloca attribute.
Definition: Function.cpp:100
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1415
size_t size() const
Definition: SmallVector.h:53
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:402
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
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:778
amdgpu Simplify well known AMD library false Value Value * Arg
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:225
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:323
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
AbstractCallSite.
Definition: CallSite.h:708
LLVM Value Representation.
Definition: Value.h:73
bool use_empty() const
Definition: Value.h:323
void resize(size_type N)
Definition: SmallVector.h:351