Fix comment for consistency sake.
[llvm/avr.git] / lib / Transforms / IPO / IPConstantPropagation.cpp
blobbb2448610f2855dcb86275394c9c9429adb0ff0f
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.
16 //===----------------------------------------------------------------------===//
18 #define DEBUG_TYPE "ipconstprop"
19 #include "llvm/Transforms/IPO.h"
20 #include "llvm/Constants.h"
21 #include "llvm/Instructions.h"
22 #include "llvm/LLVMContext.h"
23 #include "llvm/Module.h"
24 #include "llvm/Pass.h"
25 #include "llvm/Analysis/ValueTracking.h"
26 #include "llvm/Support/CallSite.h"
27 #include "llvm/Support/Compiler.h"
28 #include "llvm/ADT/Statistic.h"
29 #include "llvm/ADT/SmallVector.h"
30 using namespace llvm;
32 STATISTIC(NumArgumentsProped, "Number of args turned into constants");
33 STATISTIC(NumReturnValProped, "Number of return values turned into constants");
35 namespace {
36 /// IPCP - The interprocedural constant propagation pass
37 ///
38 struct VISIBILITY_HIDDEN IPCP : public ModulePass {
39 static char ID; // Pass identification, replacement for typeid
40 IPCP() : ModulePass(&ID) {}
42 bool runOnModule(Module &M);
43 private:
44 bool PropagateConstantsIntoArguments(Function &F);
45 bool PropagateConstantReturn(Function &F);
49 char IPCP::ID = 0;
50 static RegisterPass<IPCP>
51 X("ipconstprop", "Interprocedural constant propagation");
53 ModulePass *llvm::createIPConstantPropagationPass() { return new IPCP(); }
55 bool IPCP::runOnModule(Module &M) {
56 bool Changed = false;
57 bool LocalChange = true;
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);
71 Changed |= LocalChange;
73 return Changed;
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.
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());
88 unsigned NumNonconstant = 0;
89 for (Value::use_iterator UI = F.use_begin(), E = F.use_end(); UI != E; ++UI) {
90 // Used by a non-instruction, or not the callee of a function, do not
91 // transform.
92 if (!isa<CallInst>(*UI) && !isa<InvokeInst>(*UI))
93 return false;
95 CallSite CS = CallSite::get(cast<Instruction>(*UI));
96 if (!CS.isCallee(UI))
97 return false;
99 // Check out all of the potentially constant arguments. Note that we don't
100 // inspect varargs here.
101 CallSite::arg_iterator AI = CS.arg_begin();
102 Function::arg_iterator Arg = F.arg_begin();
103 for (unsigned i = 0, e = ArgumentConstants.size(); i != e;
104 ++i, ++AI, ++Arg) {
106 // If this argument is known non-constant, ignore it.
107 if (ArgumentConstants[i].second)
108 continue;
110 Constant *C = dyn_cast<Constant>(*AI);
111 if (C && ArgumentConstants[i].first == 0) {
112 ArgumentConstants[i].first = C; // First constant seen.
113 } else if (C && ArgumentConstants[i].first == C) {
114 // Still the constant value we think it is.
115 } else if (*AI == &*Arg) {
116 // Ignore recursive calls passing argument down.
117 } else {
118 // Argument became non-constant. If all arguments are non-constant now,
119 // give up on this function.
120 if (++NumNonconstant == ArgumentConstants.size())
121 return false;
122 ArgumentConstants[i].second = true;
127 // If we got to this point, there is a constant argument!
128 assert(NumNonconstant != ArgumentConstants.size());
129 bool MadeChange = false;
130 Function::arg_iterator AI = F.arg_begin();
131 for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI) {
132 // Do we have a constant argument?
133 if (ArgumentConstants[i].second || AI->use_empty())
134 continue;
136 Value *V = ArgumentConstants[i].first;
137 if (V == 0) V = UndefValue::get(AI->getType());
138 AI->replaceAllUsesWith(V);
139 ++NumArgumentsProped;
140 MadeChange = true;
142 return MadeChange;
146 // Check to see if this function returns one or more constants. If so, replace
147 // all callers that use those return values with the constant value. This will
148 // leave in the actual return values and instructions, but deadargelim will
149 // clean that up.
151 // Additionally if a function always returns one of its arguments directly,
152 // callers will be updated to use the value they pass in directly instead of
153 // using the return value.
154 bool IPCP::PropagateConstantReturn(Function &F) {
155 if (F.getReturnType() == Type::getVoidTy(F.getContext()))
156 return false; // No return value.
158 // If this function could be overridden later in the link stage, we can't
159 // propagate information about its results into callers.
160 if (F.mayBeOverridden())
161 return false;
163 LLVMContext &Context = F.getContext();
165 // Check to see if this function returns a constant.
166 SmallVector<Value *,4> RetVals;
167 const StructType *STy = dyn_cast<StructType>(F.getReturnType());
168 if (STy)
169 for (unsigned i = 0, e = STy->getNumElements(); i < e; ++i)
170 RetVals.push_back(UndefValue::get(STy->getElementType(i)));
171 else
172 RetVals.push_back(UndefValue::get(F.getReturnType()));
174 unsigned NumNonConstant = 0;
175 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
176 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
177 for (unsigned i = 0, e = RetVals.size(); i != e; ++i) {
178 // Already found conflicting return values?
179 Value *RV = RetVals[i];
180 if (!RV)
181 continue;
183 // Find the returned value
184 Value *V;
185 if (!STy)
186 V = RI->getOperand(i);
187 else
188 V = FindInsertedValue(RI->getOperand(0), i, Context);
190 if (V) {
191 // Ignore undefs, we can change them into anything
192 if (isa<UndefValue>(V))
193 continue;
195 // Try to see if all the rets return the same constant or argument.
196 if (isa<Constant>(V) || isa<Argument>(V)) {
197 if (isa<UndefValue>(RV)) {
198 // No value found yet? Try the current one.
199 RetVals[i] = V;
200 continue;
202 // Returning the same value? Good.
203 if (RV == V)
204 continue;
207 // Different or no known return value? Don't propagate this return
208 // value.
209 RetVals[i] = 0;
210 // All values non constant? Stop looking.
211 if (++NumNonConstant == RetVals.size())
212 return false;
216 // If we got here, the function returns at least one constant value. Loop
217 // over all users, replacing any uses of the return value with the returned
218 // constant.
219 bool MadeChange = false;
220 for (Value::use_iterator UI = F.use_begin(), E = F.use_end(); UI != E; ++UI) {
221 CallSite CS = CallSite::get(*UI);
222 Instruction* Call = CS.getInstruction();
224 // Not a call instruction or a call instruction that's not calling F
225 // directly?
226 if (!Call || !CS.isCallee(UI))
227 continue;
229 // Call result not used?
230 if (Call->use_empty())
231 continue;
233 MadeChange = true;
235 if (STy == 0) {
236 Value* New = RetVals[0];
237 if (Argument *A = dyn_cast<Argument>(New))
238 // Was an argument returned? Then find the corresponding argument in
239 // the call instruction and use that.
240 New = CS.getArgument(A->getArgNo());
241 Call->replaceAllUsesWith(New);
242 continue;
245 for (Value::use_iterator I = Call->use_begin(), E = Call->use_end();
246 I != E;) {
247 Instruction *Ins = cast<Instruction>(*I);
249 // Increment now, so we can remove the use
250 ++I;
252 // Find the index of the retval to replace with
253 int index = -1;
254 if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Ins))
255 if (EV->hasIndices())
256 index = *EV->idx_begin();
258 // If this use uses a specific return value, and we have a replacement,
259 // replace it.
260 if (index != -1) {
261 Value *New = RetVals[index];
262 if (New) {
263 if (Argument *A = dyn_cast<Argument>(New))
264 // Was an argument returned? Then find the corresponding argument in
265 // the call instruction and use that.
266 New = CS.getArgument(A->getArgNo());
267 Ins->replaceAllUsesWith(New);
268 Ins->eraseFromParent();
274 if (MadeChange) ++NumReturnValProped;
275 return MadeChange;