blob: 023e642e648c716236f88c6d6fe258b442b6240b [file] [log] [blame]
Chris Lattnerd358e6f2003-10-23 16:52:27 +00001//===-- IPConstantPropagation.cpp - Propagate constants through calls -----===//
Misha Brukmanfd939082005-04-21 23:48:37 +00002//
Chris Lattnerd358e6f2003-10-23 16:52:27 +00003// The LLVM Compiler Infrastructure
4//
Chris Lattner4ee451d2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Misha Brukmanfd939082005-04-21 23:48:37 +00007//
Chris Lattnerd358e6f2003-10-23 16:52:27 +00008//===----------------------------------------------------------------------===//
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
Chris Lattner86453c52006-12-19 22:09:18 +000018#define DEBUG_TYPE "ipconstprop"
Chris Lattnerd358e6f2003-10-23 16:52:27 +000019#include "llvm/Transforms/IPO.h"
Chris Lattnera990d942004-11-14 06:10:11 +000020#include "llvm/Constants.h"
21#include "llvm/Instructions.h"
Owen Anderson14ce9ef2009-07-06 01:34:54 +000022#include "llvm/LLVMContext.h"
Chris Lattnerd358e6f2003-10-23 16:52:27 +000023#include "llvm/Module.h"
24#include "llvm/Pass.h"
Matthijs Kooijman8b0fcf32008-06-18 08:09:27 +000025#include "llvm/Analysis/ValueTracking.h"
Chris Lattnerd358e6f2003-10-23 16:52:27 +000026#include "llvm/Support/CallSite.h"
Reid Spencer551ccae2004-09-01 22:55:40 +000027#include "llvm/ADT/Statistic.h"
Devang Patel7db30ba2008-03-11 22:24:29 +000028#include "llvm/ADT/SmallVector.h"
Chris Lattner1e2385b2003-11-21 21:54:22 +000029using namespace llvm;
Brian Gaeked0fde302003-11-11 22:41:34 +000030
Chris Lattner86453c52006-12-19 22:09:18 +000031STATISTIC(NumArgumentsProped, "Number of args turned into constants");
32STATISTIC(NumReturnValProped, "Number of return values turned into constants");
Chris Lattnerd358e6f2003-10-23 16:52:27 +000033
Chris Lattner86453c52006-12-19 22:09:18 +000034namespace {
Chris Lattnerd358e6f2003-10-23 16:52:27 +000035 /// IPCP - The interprocedural constant propagation pass
36 ///
Nick Lewycky6726b6d2009-10-25 06:33:48 +000037 struct IPCP : public ModulePass {
Nick Lewyckyecd94c82007-05-06 13:37:16 +000038 static char ID; // Pass identification, replacement for typeid
Dan Gohmanae73dc12008-09-04 17:05:41 +000039 IPCP() : ModulePass(&ID) {}
Devang Patel794fd752007-05-01 21:15:47 +000040
Chris Lattnerb12914b2004-09-20 04:48:05 +000041 bool runOnModule(Module &M);
Chris Lattnerd358e6f2003-10-23 16:52:27 +000042 private:
Chris Lattnera990d942004-11-14 06:10:11 +000043 bool PropagateConstantsIntoArguments(Function &F);
44 bool PropagateConstantReturn(Function &F);
Chris Lattnerd358e6f2003-10-23 16:52:27 +000045 };
Chris Lattnerd358e6f2003-10-23 16:52:27 +000046}
47
Dan Gohman844731a2008-05-13 00:00:25 +000048char IPCP::ID = 0;
49static RegisterPass<IPCP>
50X("ipconstprop", "Interprocedural constant propagation");
51
Chris Lattnerb12914b2004-09-20 04:48:05 +000052ModulePass *llvm::createIPConstantPropagationPass() { return new IPCP(); }
Chris Lattnerd358e6f2003-10-23 16:52:27 +000053
Chris Lattnerb12914b2004-09-20 04:48:05 +000054bool IPCP::runOnModule(Module &M) {
Chris Lattnerd358e6f2003-10-23 16:52:27 +000055 bool Changed = false;
Chris Lattner2e8dfb82003-10-27 21:09:00 +000056 bool LocalChange = true;
57
58 // FIXME: instead of using smart algorithms, we just iterate until we stop
59 // making changes.
60 while (LocalChange) {
61 LocalChange = false;
62 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
Reid Spencer5cbf9852007-01-30 20:08:39 +000063 if (!I->isDeclaration()) {
Chris Lattnera990d942004-11-14 06:10:11 +000064 // Delete any klingons.
65 I->removeDeadConstantUsers();
Rafael Espindolabb46f522009-01-15 20:18:42 +000066 if (I->hasLocalLinkage())
Chris Lattnera990d942004-11-14 06:10:11 +000067 LocalChange |= PropagateConstantsIntoArguments(*I);
68 Changed |= PropagateConstantReturn(*I);
69 }
Chris Lattner2e8dfb82003-10-27 21:09:00 +000070 Changed |= LocalChange;
71 }
Chris Lattnerd358e6f2003-10-23 16:52:27 +000072 return Changed;
73}
74
Chris Lattnera990d942004-11-14 06:10:11 +000075/// PropagateConstantsIntoArguments - Look at all uses of the specified
76/// function. If all uses are direct call sites, and all pass a particular
77/// constant in for an argument, propagate that constant in as the argument.
Chris Lattnerd358e6f2003-10-23 16:52:27 +000078///
Chris Lattnera990d942004-11-14 06:10:11 +000079bool IPCP::PropagateConstantsIntoArguments(Function &F) {
Chris Lattner7f8897f2006-08-27 22:42:52 +000080 if (F.arg_empty() || F.use_empty()) return false; // No arguments? Early exit.
Chris Lattnerd358e6f2003-10-23 16:52:27 +000081
Chris Lattner4af6ad32008-04-23 06:16:27 +000082 // For each argument, keep track of its constant value and whether it is a
83 // constant or not. The bool is driven to true when found to be non-constant.
84 SmallVector<std::pair<Constant*, bool>, 16> ArgumentConstants;
Chris Lattnere4d5c442005-03-15 04:54:21 +000085 ArgumentConstants.resize(F.arg_size());
Chris Lattnerd358e6f2003-10-23 16:52:27 +000086
87 unsigned NumNonconstant = 0;
Chris Lattner4af6ad32008-04-23 06:16:27 +000088 for (Value::use_iterator UI = F.use_begin(), E = F.use_end(); UI != E; ++UI) {
Chris Lattnerb2710042009-11-01 06:11:53 +000089 // Ignore blockaddress uses.
90 if (isa<BlockAddress>(*UI)) continue;
91
Chris Lattner4af6ad32008-04-23 06:16:27 +000092 // Used by a non-instruction, or not the callee of a function, do not
93 // transform.
Gabor Greifedc4d692009-01-22 21:35:57 +000094 if (!isa<CallInst>(*UI) && !isa<InvokeInst>(*UI))
Chris Lattner4af6ad32008-04-23 06:16:27 +000095 return false;
96
97 CallSite CS = CallSite::get(cast<Instruction>(*UI));
Gabor Greifedc4d692009-01-22 21:35:57 +000098 if (!CS.isCallee(UI))
99 return false;
Chris Lattnerd358e6f2003-10-23 16:52:27 +0000100
Chris Lattner4af6ad32008-04-23 06:16:27 +0000101 // Check out all of the potentially constant arguments. Note that we don't
102 // inspect varargs here.
103 CallSite::arg_iterator AI = CS.arg_begin();
104 Function::arg_iterator Arg = F.arg_begin();
105 for (unsigned i = 0, e = ArgumentConstants.size(); i != e;
106 ++i, ++AI, ++Arg) {
107
108 // If this argument is known non-constant, ignore it.
109 if (ArgumentConstants[i].second)
110 continue;
111
112 Constant *C = dyn_cast<Constant>(*AI);
113 if (C && ArgumentConstants[i].first == 0) {
114 ArgumentConstants[i].first = C; // First constant seen.
115 } else if (C && ArgumentConstants[i].first == C) {
116 // Still the constant value we think it is.
117 } else if (*AI == &*Arg) {
118 // Ignore recursive calls passing argument down.
119 } else {
120 // Argument became non-constant. If all arguments are non-constant now,
121 // give up on this function.
122 if (++NumNonconstant == ArgumentConstants.size())
123 return false;
124 ArgumentConstants[i].second = true;
Chris Lattnerd358e6f2003-10-23 16:52:27 +0000125 }
126 }
Chris Lattner4af6ad32008-04-23 06:16:27 +0000127 }
Chris Lattnerd358e6f2003-10-23 16:52:27 +0000128
129 // If we got to this point, there is a constant argument!
130 assert(NumNonconstant != ArgumentConstants.size());
Chris Lattner2e8dfb82003-10-27 21:09:00 +0000131 bool MadeChange = false;
Chris Lattner4af6ad32008-04-23 06:16:27 +0000132 Function::arg_iterator AI = F.arg_begin();
133 for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI) {
134 // Do we have a constant argument?
Torok Edwinc3384992009-09-24 18:33:42 +0000135 if (ArgumentConstants[i].second || AI->use_empty() ||
136 (AI->hasByValAttr() && !F.onlyReadsMemory()))
Chris Lattner4af6ad32008-04-23 06:16:27 +0000137 continue;
138
139 Value *V = ArgumentConstants[i].first;
Owen Anderson9e9a0d52009-07-30 23:03:37 +0000140 if (V == 0) V = UndefValue::get(AI->getType());
Chris Lattner4af6ad32008-04-23 06:16:27 +0000141 AI->replaceAllUsesWith(V);
142 ++NumArgumentsProped;
143 MadeChange = true;
144 }
Chris Lattner2e8dfb82003-10-27 21:09:00 +0000145 return MadeChange;
Chris Lattnerd358e6f2003-10-23 16:52:27 +0000146}
Brian Gaeked0fde302003-11-11 22:41:34 +0000147
Chris Lattnera990d942004-11-14 06:10:11 +0000148
Matthijs Kooijman8b0fcf32008-06-18 08:09:27 +0000149// Check to see if this function returns one or more constants. If so, replace
150// all callers that use those return values with the constant value. This will
151// leave in the actual return values and instructions, but deadargelim will
152// clean that up.
Matthijs Kooijmanc2afe892008-06-18 08:30:37 +0000153//
154// Additionally if a function always returns one of its arguments directly,
155// callers will be updated to use the value they pass in directly instead of
156// using the return value.
Chris Lattnera990d942004-11-14 06:10:11 +0000157bool IPCP::PropagateConstantReturn(Function &F) {
Owen Anderson1d0be152009-08-13 21:58:54 +0000158 if (F.getReturnType() == Type::getVoidTy(F.getContext()))
Chris Lattnera990d942004-11-14 06:10:11 +0000159 return false; // No return value.
160
Chris Lattner18d73c22008-06-09 07:58:07 +0000161 // If this function could be overridden later in the link stage, we can't
162 // propagate information about its results into callers.
Nuno Lopes5ed3b892008-09-29 14:40:32 +0000163 if (F.mayBeOverridden())
Chris Lattner18d73c22008-06-09 07:58:07 +0000164 return false;
Owen Andersone922c022009-07-22 00:24:57 +0000165
166 LLVMContext &Context = F.getContext();
Chris Lattner18d73c22008-06-09 07:58:07 +0000167
Chris Lattnera990d942004-11-14 06:10:11 +0000168 // Check to see if this function returns a constant.
Devang Patel7db30ba2008-03-11 22:24:29 +0000169 SmallVector<Value *,4> RetVals;
Devang Patel7db30ba2008-03-11 22:24:29 +0000170 const StructType *STy = dyn_cast<StructType>(F.getReturnType());
171 if (STy)
Matthijs Kooijman8b0fcf32008-06-18 08:09:27 +0000172 for (unsigned i = 0, e = STy->getNumElements(); i < e; ++i)
Owen Anderson9e9a0d52009-07-30 23:03:37 +0000173 RetVals.push_back(UndefValue::get(STy->getElementType(i)));
Devang Patel7db30ba2008-03-11 22:24:29 +0000174 else
Owen Anderson9e9a0d52009-07-30 23:03:37 +0000175 RetVals.push_back(UndefValue::get(F.getReturnType()));
Devang Patel7db30ba2008-03-11 22:24:29 +0000176
Matthijs Kooijman8b0fcf32008-06-18 08:09:27 +0000177 unsigned NumNonConstant = 0;
Chris Lattnera990d942004-11-14 06:10:11 +0000178 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
Anton Korobeynikov07e6e562008-02-20 11:26:25 +0000179 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
Chris Lattnere9625c62008-04-23 05:59:23 +0000180 for (unsigned i = 0, e = RetVals.size(); i != e; ++i) {
Matthijs Kooijman8b0fcf32008-06-18 08:09:27 +0000181 // Already found conflicting return values?
Chris Lattnere9625c62008-04-23 05:59:23 +0000182 Value *RV = RetVals[i];
Matthijs Kooijman8b0fcf32008-06-18 08:09:27 +0000183 if (!RV)
184 continue;
185
186 // Find the returned value
187 Value *V;
Dan Gohman792e1e92008-10-03 22:21:24 +0000188 if (!STy)
Matthijs Kooijman8b0fcf32008-06-18 08:09:27 +0000189 V = RI->getOperand(i);
190 else
Owen Anderson76f600b2009-07-06 22:37:39 +0000191 V = FindInsertedValue(RI->getOperand(0), i, Context);
Matthijs Kooijman8b0fcf32008-06-18 08:09:27 +0000192
193 if (V) {
194 // Ignore undefs, we can change them into anything
195 if (isa<UndefValue>(V))
196 continue;
197
Matthijs Kooijmanc2afe892008-06-18 08:30:37 +0000198 // Try to see if all the rets return the same constant or argument.
199 if (isa<Constant>(V) || isa<Argument>(V)) {
Matthijs Kooijman8b0fcf32008-06-18 08:09:27 +0000200 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;
Chris Lattnera990d942004-11-14 06:10:11 +0000216 }
Anton Korobeynikov07e6e562008-02-20 11:26:25 +0000217 }
Chris Lattnera990d942004-11-14 06:10:11 +0000218
Matthijs Kooijman8b0fcf32008-06-18 08:09:27 +0000219 // 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.
Chris Lattnera990d942004-11-14 06:10:11 +0000222 bool MadeChange = false;
Chris Lattnere9625c62008-04-23 05:59:23 +0000223 for (Value::use_iterator UI = F.use_begin(), E = F.use_end(); UI != E; ++UI) {
Matthijs Kooijmanf0da2032008-06-19 08:53:24 +0000224 CallSite CS = CallSite::get(*UI);
225 Instruction* Call = CS.getInstruction();
226
227 // Not a call instruction or a call instruction that's not calling F
228 // directly?
Gabor Greifedc4d692009-01-22 21:35:57 +0000229 if (!Call || !CS.isCallee(UI))
Chris Lattnere9625c62008-04-23 05:59:23 +0000230 continue;
Chris Lattnere9625c62008-04-23 05:59:23 +0000231
Matthijs Kooijmanf0da2032008-06-19 08:53:24 +0000232 // Call result not used?
Chris Lattnere9625c62008-04-23 05:59:23 +0000233 if (Call->use_empty())
234 continue;
Chris Lattnera990d942004-11-14 06:10:11 +0000235
Chris Lattnere9625c62008-04-23 05:59:23 +0000236 MadeChange = true;
237
238 if (STy == 0) {
Matthijs Kooijmanc2afe892008-06-18 08:30:37 +0000239 Value* New = RetVals[0];
240 if (Argument *A = dyn_cast<Argument>(New))
241 // Was an argument returned? Then find the corresponding argument in
Matthijs Kooijmanf0da2032008-06-19 08:53:24 +0000242 // the call instruction and use that.
243 New = CS.getArgument(A->getArgNo());
Matthijs Kooijmanc2afe892008-06-18 08:30:37 +0000244 Call->replaceAllUsesWith(New);
Chris Lattnere9625c62008-04-23 05:59:23 +0000245 continue;
246 }
247
Matthijs Kooijman8b0fcf32008-06-18 08:09:27 +0000248 for (Value::use_iterator I = Call->use_begin(), E = Call->use_end();
249 I != E;) {
Jay Foad0906b1b2009-06-06 17:49:35 +0000250 Instruction *Ins = cast<Instruction>(*I);
Matthijs Kooijman8b0fcf32008-06-18 08:09:27 +0000251
252 // Increment now, so we can remove the use
253 ++I;
254
Matthijs Kooijman8b0fcf32008-06-18 08:09:27 +0000255 // Find the index of the retval to replace with
256 int index = -1;
Dan Gohmanfc74abf2008-07-23 00:34:11 +0000257 if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Ins))
Matthijs Kooijman8b0fcf32008-06-18 08:09:27 +0000258 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) {
Matthijs Kooijmanc2afe892008-06-18 08:30:37 +0000266 if (Argument *A = dyn_cast<Argument>(New))
267 // Was an argument returned? Then find the corresponding argument in
Matthijs Kooijmanf0da2032008-06-19 08:53:24 +0000268 // the call instruction and use that.
269 New = CS.getArgument(A->getArgNo());
Matthijs Kooijman8b0fcf32008-06-18 08:09:27 +0000270 Ins->replaceAllUsesWith(New);
271 Ins->eraseFromParent();
Chris Lattner2ffa47b2004-12-11 17:00:14 +0000272 }
Devang Patel488b6782008-03-20 18:30:32 +0000273 }
Devang Patel7db30ba2008-03-11 22:24:29 +0000274 }
Chris Lattnera990d942004-11-14 06:10:11 +0000275 }
276
277 if (MadeChange) ++NumReturnValProped;
Chris Lattnera990d942004-11-14 06:10:11 +0000278 return MadeChange;
279}