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/Constants.h"
21 #include "llvm/Instructions.h"
22 #include "llvm/Module.h"
23 #include "llvm/Pass.h"
24 #include "llvm/Analysis/ValueTracking.h"
25 #include "llvm/Support/CallSite.h"
26 #include "llvm/ADT/Statistic.h"
27 #include "llvm/ADT/SmallVector.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
IPCP__anon4d8d6af80111::IPCP38 IPCP() : ModulePass(ID) {}
39
40 bool runOnModule(Module &M);
41 private:
42 bool PropagateConstantsIntoArguments(Function &F);
43 bool PropagateConstantReturn(Function &F);
44 };
45 }
46
47 char IPCP::ID = 0;
48 INITIALIZE_PASS(IPCP, "ipconstprop",
49 "Interprocedural constant propagation", false, false);
50
createIPConstantPropagationPass()51 ModulePass *llvm::createIPConstantPropagationPass() { return new IPCP(); }
52
runOnModule(Module & M)53 bool IPCP::runOnModule(Module &M) {
54 bool Changed = false;
55 bool LocalChange = true;
56
57 // FIXME: instead of using smart algorithms, we just iterate until we stop
58 // making changes.
59 while (LocalChange) {
60 LocalChange = false;
61 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
62 if (!I->isDeclaration()) {
63 // Delete any klingons.
64 I->removeDeadConstantUsers();
65 if (I->hasLocalLinkage())
66 LocalChange |= PropagateConstantsIntoArguments(*I);
67 Changed |= PropagateConstantReturn(*I);
68 }
69 Changed |= LocalChange;
70 }
71 return Changed;
72 }
73
74 /// PropagateConstantsIntoArguments - Look at all uses of the specified
75 /// function. If all uses are direct call sites, and all pass a particular
76 /// constant in for an argument, propagate that constant in as the argument.
77 ///
PropagateConstantsIntoArguments(Function & F)78 bool IPCP::PropagateConstantsIntoArguments(Function &F) {
79 if (F.arg_empty() || F.use_empty()) return false; // No arguments? Early exit.
80
81 // For each argument, keep track of its constant value and whether it is a
82 // constant or not. The bool is driven to true when found to be non-constant.
83 SmallVector<std::pair<Constant*, bool>, 16> ArgumentConstants;
84 ArgumentConstants.resize(F.arg_size());
85
86 unsigned NumNonconstant = 0;
87 for (Value::use_iterator UI = F.use_begin(), E = F.use_end(); UI != E; ++UI) {
88 User *U = *UI;
89 // Ignore blockaddress uses.
90 if (isa<BlockAddress>(U)) continue;
91
92 // Used by a non-instruction, or not the callee of a function, do not
93 // transform.
94 if (!isa<CallInst>(U) && !isa<InvokeInst>(U))
95 return false;
96
97 CallSite CS(cast<Instruction>(U));
98 if (!CS.isCallee(UI))
99 return false;
100
101 // 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;
125 }
126 }
127 }
128
129 // If we got to this point, there is a constant argument!
130 assert(NumNonconstant != ArgumentConstants.size());
131 bool MadeChange = false;
132 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?
135 if (ArgumentConstants[i].second || AI->use_empty() ||
136 (AI->hasByValAttr() && !F.onlyReadsMemory()))
137 continue;
138
139 Value *V = ArgumentConstants[i].first;
140 if (V == 0) V = UndefValue::get(AI->getType());
141 AI->replaceAllUsesWith(V);
142 ++NumArgumentsProped;
143 MadeChange = true;
144 }
145 return MadeChange;
146 }
147
148
149 // 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.
153 //
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.
PropagateConstantReturn(Function & F)157 bool IPCP::PropagateConstantReturn(Function &F) {
158 if (F.getReturnType()->isVoidTy())
159 return false; // No return value.
160
161 // If this function could be overridden later in the link stage, we can't
162 // propagate information about its results into callers.
163 if (F.mayBeOverridden())
164 return false;
165
166 // Check to see if this function returns a constant.
167 SmallVector<Value *,4> RetVals;
168 const StructType *STy = dyn_cast<StructType>(F.getReturnType());
169 if (STy)
170 for (unsigned i = 0, e = STy->getNumElements(); i < e; ++i)
171 RetVals.push_back(UndefValue::get(STy->getElementType(i)));
172 else
173 RetVals.push_back(UndefValue::get(F.getReturnType()));
174
175 unsigned NumNonConstant = 0;
176 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
177 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
178 for (unsigned i = 0, e = RetVals.size(); i != e; ++i) {
179 // Already found conflicting return values?
180 Value *RV = RetVals[i];
181 if (!RV)
182 continue;
183
184 // Find the returned value
185 Value *V;
186 if (!STy)
187 V = RI->getOperand(i);
188 else
189 V = FindInsertedValue(RI->getOperand(0), i);
190
191 if (V) {
192 // Ignore undefs, we can change them into anything
193 if (isa<UndefValue>(V))
194 continue;
195
196 // Try to see if all the rets return the same constant or argument.
197 if (isa<Constant>(V) || isa<Argument>(V)) {
198 if (isa<UndefValue>(RV)) {
199 // No value found yet? Try the current one.
200 RetVals[i] = V;
201 continue;
202 }
203 // Returning the same value? Good.
204 if (RV == V)
205 continue;
206 }
207 }
208 // Different or no known return value? Don't propagate this return
209 // value.
210 RetVals[i] = 0;
211 // All values non constant? Stop looking.
212 if (++NumNonConstant == RetVals.size())
213 return false;
214 }
215 }
216
217 // If we got here, the function returns at least one constant value. Loop
218 // over all users, replacing any uses of the return value with the returned
219 // constant.
220 bool MadeChange = false;
221 for (Value::use_iterator UI = F.use_begin(), E = F.use_end(); UI != E; ++UI) {
222 CallSite CS(*UI);
223 Instruction* Call = CS.getInstruction();
224
225 // Not a call instruction or a call instruction that's not calling F
226 // directly?
227 if (!Call || !CS.isCallee(UI))
228 continue;
229
230 // Call result not used?
231 if (Call->use_empty())
232 continue;
233
234 MadeChange = true;
235
236 if (STy == 0) {
237 Value* New = RetVals[0];
238 if (Argument *A = dyn_cast<Argument>(New))
239 // Was an argument returned? Then find the corresponding argument in
240 // the call instruction and use that.
241 New = CS.getArgument(A->getArgNo());
242 Call->replaceAllUsesWith(New);
243 continue;
244 }
245
246 for (Value::use_iterator I = Call->use_begin(), E = Call->use_end();
247 I != E;) {
248 Instruction *Ins = cast<Instruction>(*I);
249
250 // Increment now, so we can remove the use
251 ++I;
252
253 // Find the index of the retval to replace with
254 int index = -1;
255 if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Ins))
256 if (EV->hasIndices())
257 index = *EV->idx_begin();
258
259 // If this use uses a specific return value, and we have a replacement,
260 // replace it.
261 if (index != -1) {
262 Value *New = RetVals[index];
263 if (New) {
264 if (Argument *A = dyn_cast<Argument>(New))
265 // Was an argument returned? Then find the corresponding argument in
266 // the call instruction and use that.
267 New = CS.getArgument(A->getArgNo());
268 Ins->replaceAllUsesWith(New);
269 Ins->eraseFromParent();
270 }
271 }
272 }
273 }
274
275 if (MadeChange) ++NumReturnValProped;
276 return MadeChange;
277 }
278