LLVM  6.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  // Used by a non-instruction, or not the callee of a function, do not
66  // transform.
67  if (!isa<CallInst>(UR) && !isa<InvokeInst>(UR))
68  return false;
69 
70  CallSite CS(cast<Instruction>(UR));
71  if (!CS.isCallee(&U))
72  return false;
73 
74  // Check out all of the potentially constant arguments. Note that we don't
75  // inspect varargs here.
78  for (unsigned i = 0, e = ArgumentConstants.size(); i != e;
79  ++i, ++AI, ++Arg) {
80 
81  // If this argument is known non-constant, ignore it.
82  if (ArgumentConstants[i].second)
83  continue;
84 
85  Constant *C = dyn_cast<Constant>(*AI);
86  if (C && ArgumentConstants[i].first == nullptr) {
87  ArgumentConstants[i].first = C; // First constant seen.
88  } else if (C && ArgumentConstants[i].first == C) {
89  // Still the constant value we think it is.
90  } else if (*AI == &*Arg) {
91  // Ignore recursive calls passing argument down.
92  } else {
93  // Argument became non-constant. If all arguments are non-constant now,
94  // give up on this function.
95  if (++NumNonconstant == ArgumentConstants.size())
96  return false;
97  ArgumentConstants[i].second = true;
98  }
99  }
100  }
101 
102  // If we got to this point, there is a constant argument!
103  assert(NumNonconstant != ArgumentConstants.size());
104  bool MadeChange = false;
106  for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI) {
107  // Do we have a constant argument?
108  if (ArgumentConstants[i].second || AI->use_empty() ||
109  AI->hasInAllocaAttr() || (AI->hasByValAttr() && !F.onlyReadsMemory()))
110  continue;
111 
112  Value *V = ArgumentConstants[i].first;
113  if (!V) V = UndefValue::get(AI->getType());
114  AI->replaceAllUsesWith(V);
115  ++NumArgumentsProped;
116  MadeChange = true;
117  }
118  return MadeChange;
119 }
120 
121 
122 // Check to see if this function returns one or more constants. If so, replace
123 // all callers that use those return values with the constant value. This will
124 // leave in the actual return values and instructions, but deadargelim will
125 // clean that up.
126 //
127 // Additionally if a function always returns one of its arguments directly,
128 // callers will be updated to use the value they pass in directly instead of
129 // using the return value.
131  if (F.getReturnType()->isVoidTy())
132  return false; // No return value.
133 
134  // We can infer and propagate the return value only when we know that the
135  // definition we'll get at link time is *exactly* the definition we see now.
136  // For more details, see GlobalValue::mayBeDerefined.
137  if (!F.isDefinitionExact())
138  return false;
139 
140  // Don't touch naked functions. The may contain asm returning
141  // value we don't see, so we may end up interprocedurally propagating
142  // the return value incorrectly.
143  if (F.hasFnAttribute(Attribute::Naked))
144  return false;
145 
146  // Check to see if this function returns a constant.
147  SmallVector<Value *,4> RetVals;
149  if (STy)
150  for (unsigned i = 0, e = STy->getNumElements(); i < e; ++i)
151  RetVals.push_back(UndefValue::get(STy->getElementType(i)));
152  else
154 
155  unsigned NumNonConstant = 0;
156  for (BasicBlock &BB : F)
157  if (ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator())) {
158  for (unsigned i = 0, e = RetVals.size(); i != e; ++i) {
159  // Already found conflicting return values?
160  Value *RV = RetVals[i];
161  if (!RV)
162  continue;
163 
164  // Find the returned value
165  Value *V;
166  if (!STy)
167  V = RI->getOperand(0);
168  else
169  V = FindInsertedValue(RI->getOperand(0), i);
170 
171  if (V) {
172  // Ignore undefs, we can change them into anything
173  if (isa<UndefValue>(V))
174  continue;
175 
176  // Try to see if all the rets return the same constant or argument.
177  if (isa<Constant>(V) || isa<Argument>(V)) {
178  if (isa<UndefValue>(RV)) {
179  // No value found yet? Try the current one.
180  RetVals[i] = V;
181  continue;
182  }
183  // Returning the same value? Good.
184  if (RV == V)
185  continue;
186  }
187  }
188  // Different or no known return value? Don't propagate this return
189  // value.
190  RetVals[i] = nullptr;
191  // All values non-constant? Stop looking.
192  if (++NumNonConstant == RetVals.size())
193  return false;
194  }
195  }
196 
197  // If we got here, the function returns at least one constant value. Loop
198  // over all users, replacing any uses of the return value with the returned
199  // constant.
200  bool MadeChange = false;
201  for (Use &U : F.uses()) {
202  CallSite CS(U.getUser());
203  Instruction* Call = CS.getInstruction();
204 
205  // Not a call instruction or a call instruction that's not calling F
206  // directly?
207  if (!Call || !CS.isCallee(&U))
208  continue;
209 
210  // Call result not used?
211  if (Call->use_empty())
212  continue;
213 
214  MadeChange = true;
215 
216  if (!STy) {
217  Value* New = RetVals[0];
218  if (Argument *A = dyn_cast<Argument>(New))
219  // Was an argument returned? Then find the corresponding argument in
220  // the call instruction and use that.
221  New = CS.getArgument(A->getArgNo());
222  Call->replaceAllUsesWith(New);
223  continue;
224  }
225 
226  for (auto I = Call->user_begin(), E = Call->user_end(); I != E;) {
227  Instruction *Ins = cast<Instruction>(*I);
228 
229  // Increment now, so we can remove the use
230  ++I;
231 
232  // Find the index of the retval to replace with
233  int index = -1;
234  if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Ins))
235  if (EV->hasIndices())
236  index = *EV->idx_begin();
237 
238  // If this use uses a specific return value, and we have a replacement,
239  // replace it.
240  if (index != -1) {
241  Value *New = RetVals[index];
242  if (New) {
243  if (Argument *A = dyn_cast<Argument>(New))
244  // Was an argument returned? Then find the corresponding argument in
245  // the call instruction and use that.
246  New = CS.getArgument(A->getArgNo());
247  Ins->replaceAllUsesWith(New);
248  Ins->eraseFromParent();
249  }
250  }
251  }
252  }
253 
254  if (MadeChange) ++NumReturnValProped;
255  return MadeChange;
256 }
257 
258 char IPCP::ID = 0;
259 INITIALIZE_PASS(IPCP, "ipconstprop",
260  "Interprocedural constant propagation", false, false)
261 
262 ModulePass *llvm::createIPConstantPropagationPass() { return new IPCP(); }
263 
264 bool IPCP::runOnModule(Module &M) {
265  if (skipModule(M))
266  return false;
267 
268  bool Changed = false;
269  bool LocalChange = true;
270 
271  // FIXME: instead of using smart algorithms, we just iterate until we stop
272  // making changes.
273  while (LocalChange) {
274  LocalChange = false;
275  for (Function &F : M)
276  if (!F.isDeclaration()) {
277  // Delete any klingons.
278  F.removeDeadConstantUsers();
279  if (F.hasLocalLinkage())
280  LocalChange |= PropagateConstantsIntoArguments(F);
281  Changed |= PropagateConstantReturn(F);
282  }
283  Changed |= LocalChange;
284  }
285  return Changed;
286 }
bool onlyReadsMemory() const
Determine if the function does not access or only reads memory.
Definition: Function.h:395
uint64_t CallInst * C
Return a value (possibly void), from a function.
void initializeIPCPPass(PassRegistry &)
User::op_iterator arg_iterator
The type of iterator to use when looping over actual arguments at this call site. ...
Definition: CallSite.h:210
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:69
ModulePass * createIPConstantPropagationPass()
createIPConstantPropagationPass - This pass propagates constants from call sites into the bodies of f...
iterator_range< use_iterator > uses()
Definition: Value.h:350
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.
Compute iterated dominance frontiers using a linear time algorithm.
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:63
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
unsigned getNumElements() const
Random access to the elements.
Definition: DerivedTypes.h:313
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:254
unsigned second
STATISTIC(NumFunctions, "Total number of functions")
bool hasByValAttr() const
Return true if this argument has the byval attribute.
Definition: Function.cpp:88
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
#define F(x, y, z)
Definition: MD5.cpp: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:623
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:428
bool isVoidTy() const
Return true if this is &#39;void&#39;.
Definition: Type.h:141
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:142
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
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...
#define A
Definition: LargeTest.cpp:12
size_t arg_size() const
Definition: Function.h:622
arg_iterator arg_begin()
Definition: Function.h:595
bool hasInAllocaAttr() const
Return true if this argument has the inalloca attribute.
Definition: Function.cpp:101
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1320
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:382
#define E
Definition: LargeTest.cpp:27
IterTy arg_begin() const
Definition: CallSite.h:545
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
Module.h This file contains the declarations for the Module class.
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:235
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())
LLVM Value Representation.
Definition: Value.h:73
bool use_empty() const
Definition: Value.h:322
void resize(size_type N)
Definition: SmallVector.h:355
bool isCallee(Value::const_user_iterator UI) const
Determine whether the passed iterator points to the callee operand&#39;s Use.
Definition: CallSite.h:140