LLVM API Documentation

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 #define DEBUG_TYPE "ipconstprop"
19 #include "llvm/Transforms/IPO.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/Statistic.h"
23 #include "llvm/IR/Constants.h"
24 #include "llvm/IR/Instructions.h"
25 #include "llvm/IR/Module.h"
26 #include "llvm/Pass.h"
27 #include "llvm/Support/CallSite.h"
28 using namespace llvm;
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);
43  private:
44  bool PropagateConstantsIntoArguments(Function &F);
45  bool PropagateConstantReturn(Function &F);
46  };
47 }
48 
49 char IPCP::ID = 0;
50 INITIALIZE_PASS(IPCP, "ipconstprop",
51  "Interprocedural constant propagation", false, false)
52 
53 ModulePass *llvm::createIPConstantPropagationPass() { return new IPCP(); }
54 
55 bool IPCP::runOnModule(Module &M) {
56  bool Changed = false;
57  bool LocalChange = true;
58 
59  // FIXME: instead of using smart algorithms, we just iterate until we stop
60  // making changes.
61  while (LocalChange) {
62  LocalChange = false;
63  for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
64  if (!I->isDeclaration()) {
65  // Delete any klingons.
66  I->removeDeadConstantUsers();
67  if (I->hasLocalLinkage())
68  LocalChange |= PropagateConstantsIntoArguments(*I);
69  Changed |= PropagateConstantReturn(*I);
70  }
71  Changed |= LocalChange;
72  }
73  return Changed;
74 }
75 
76 /// PropagateConstantsIntoArguments - Look at all uses of the specified
77 /// function. If all uses are direct call sites, and all pass a particular
78 /// constant in for an argument, propagate that constant in as the argument.
79 ///
80 bool IPCP::PropagateConstantsIntoArguments(Function &F) {
81  if (F.arg_empty() || F.use_empty()) return false; // No arguments? Early exit.
82 
83  // For each argument, keep track of its constant value and whether it is a
84  // constant or not. The bool is driven to true when found to be non-constant.
85  SmallVector<std::pair<Constant*, bool>, 16> ArgumentConstants;
86  ArgumentConstants.resize(F.arg_size());
87 
88  unsigned NumNonconstant = 0;
89  for (Value::use_iterator UI = F.use_begin(), E = F.use_end(); UI != E; ++UI) {
90  User *U = *UI;
91  // Ignore blockaddress uses.
92  if (isa<BlockAddress>(U)) continue;
93 
94  // Used by a non-instruction, or not the callee of a function, do not
95  // transform.
96  if (!isa<CallInst>(U) && !isa<InvokeInst>(U))
97  return false;
98 
99  CallSite CS(cast<Instruction>(U));
100  if (!CS.isCallee(UI))
101  return false;
102 
103  // Check out all of the potentially constant arguments. Note that we don't
104  // inspect varargs here.
105  CallSite::arg_iterator AI = CS.arg_begin();
107  for (unsigned i = 0, e = ArgumentConstants.size(); i != e;
108  ++i, ++AI, ++Arg) {
109 
110  // If this argument is known non-constant, ignore it.
111  if (ArgumentConstants[i].second)
112  continue;
113 
114  Constant *C = dyn_cast<Constant>(*AI);
115  if (C && ArgumentConstants[i].first == 0) {
116  ArgumentConstants[i].first = C; // First constant seen.
117  } else if (C && ArgumentConstants[i].first == C) {
118  // Still the constant value we think it is.
119  } else if (*AI == &*Arg) {
120  // Ignore recursive calls passing argument down.
121  } else {
122  // Argument became non-constant. If all arguments are non-constant now,
123  // give up on this function.
124  if (++NumNonconstant == ArgumentConstants.size())
125  return false;
126  ArgumentConstants[i].second = true;
127  }
128  }
129  }
130 
131  // If we got to this point, there is a constant argument!
132  assert(NumNonconstant != ArgumentConstants.size());
133  bool MadeChange = false;
135  for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI) {
136  // Do we have a constant argument?
137  if (ArgumentConstants[i].second || AI->use_empty() ||
138  (AI->hasByValAttr() && !F.onlyReadsMemory()))
139  continue;
140 
141  Value *V = ArgumentConstants[i].first;
142  if (V == 0) V = UndefValue::get(AI->getType());
143  AI->replaceAllUsesWith(V);
144  ++NumArgumentsProped;
145  MadeChange = true;
146  }
147  return MadeChange;
148 }
149 
150 
151 // Check to see if this function returns one or more constants. If so, replace
152 // all callers that use those return values with the constant value. This will
153 // leave in the actual return values and instructions, but deadargelim will
154 // clean that up.
155 //
156 // Additionally if a function always returns one of its arguments directly,
157 // callers will be updated to use the value they pass in directly instead of
158 // using the return value.
159 bool IPCP::PropagateConstantReturn(Function &F) {
160  if (F.getReturnType()->isVoidTy())
161  return false; // No return value.
162 
163  // If this function could be overridden later in the link stage, we can't
164  // propagate information about its results into callers.
165  if (F.mayBeOverridden())
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 (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
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] = 0;
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 (Value::use_iterator UI = F.use_begin(), E = F.use_end(); UI != E; ++UI) {
224  CallSite CS(*UI);
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(UI))
230  continue;
231 
232  // Call result not used?
233  if (Call->use_empty())
234  continue;
235 
236  MadeChange = true;
237 
238  if (STy == 0) {
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 (Value::use_iterator I = Call->use_begin(), E = Call->use_end();
249  I != E;) {
250  Instruction *Ins = cast<Instruction>(*I);
251 
252  // Increment now, so we can remove the use
253  ++I;
254 
255  // Find the index of the retval to replace with
256  int index = -1;
257  if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Ins))
258  if (EV->hasIndices())
259  index = *EV->idx_begin();
260 
261  // If this use uses a specific return value, and we have a replacement,
262  // replace it.
263  if (index != -1) {
264  Value *New = RetVals[index];
265  if (New) {
266  if (Argument *A = dyn_cast<Argument>(New))
267  // Was an argument returned? Then find the corresponding argument in
268  // the call instruction and use that.
269  New = CS.getArgument(A->getArgNo());
270  Ins->replaceAllUsesWith(New);
271  Ins->eraseFromParent();
272  }
273  }
274  }
275  }
276 
277  if (MadeChange) ++NumReturnValProped;
278  return MadeChange;
279 }
void initializeIPCPPass(PassRegistry &)
use_iterator use_end()
Definition: Value.h:152
ModulePass * createIPConstantPropagationPass()
static PassRegistry * getPassRegistry()
LLVM Argument representation.
Definition: Argument.h:35
bool onlyReadsMemory() const
Determine if the function does not access or only reads memory.
Definition: Function.h:246
INITIALIZE_PASS(IPCP,"ipconstprop","Interprocedural constant propagation", false, false) ModulePass *llvm
The main container class for the LLVM Intermediate Representation.
Definition: Module.h:112
iterator end()
Definition: Function.h:397
enable_if_c<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:266
Type * getReturnType() const
Definition: Function.cpp:179
F(f)
size_t arg_size() const
Definition: Function.cpp:248
Value * FindInsertedValue(Value *V, ArrayRef< unsigned > idx_range, Instruction *InsertBefore=0)
ID
LLVM Calling Convention Representation.
Definition: CallingConv.h:26
void replaceAllUsesWith(Value *V)
Definition: Value.cpp:303
iterator begin()
Definition: Function.h:395
STATISTIC(NumArgumentsProped,"Number of args turned into constants")
static bool mayBeOverridden(LinkageTypes Linkage)
Definition: GlobalValue.h:171
Type * getElementType(unsigned N) const
Definition: DerivedTypes.h:287
LLVM Constant Representation.
Definition: Constant.h:41
arg_iterator arg_begin()
Definition: Function.h:410
static UndefValue * get(Type *T)
Definition: Constants.cpp:1334
bool arg_empty() const
Definition: Function.cpp:251
use_iterator use_begin()
Definition: Value.h:150
iterator end()
Definition: Module.h:533
#define I(x, y, z)
Definition: MD5.cpp:54
iterator begin()
Definition: Module.h:531
void resize(unsigned N)
Definition: SmallVector.h:401
bool use_empty() const
Definition: Value.h:149
LLVM Value Representation.
Definition: Value.h:66
unsigned getNumElements() const
Random access to the elements.
Definition: DerivedTypes.h:286
bool isVoidTy() const
isVoidTy - Return true if this is 'void'.
Definition: Type.h:140