/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/IPO/IPConstantPropagation.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===-- IPConstantPropagation.cpp - Propagate constants through calls -----===// |
2 | | // |
3 | | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | | // See https://llvm.org/LICENSE.txt for license information. |
5 | | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | | // |
7 | | //===----------------------------------------------------------------------===// |
8 | | // |
9 | | // This pass implements an _extremely_ simple interprocedural constant |
10 | | // propagation pass. It could certainly be improved in many different ways, |
11 | | // like using a worklist. This pass makes arguments dead, but does not remove |
12 | | // them. The existing dead argument elimination pass should be run after this |
13 | | // to clean up the mess. |
14 | | // |
15 | | //===----------------------------------------------------------------------===// |
16 | | |
17 | | #include "llvm/ADT/SmallVector.h" |
18 | | #include "llvm/ADT/Statistic.h" |
19 | | #include "llvm/Analysis/ValueTracking.h" |
20 | | #include "llvm/IR/CallSite.h" |
21 | | #include "llvm/IR/Constants.h" |
22 | | #include "llvm/IR/Instructions.h" |
23 | | #include "llvm/IR/Module.h" |
24 | | #include "llvm/Pass.h" |
25 | | #include "llvm/Transforms/IPO.h" |
26 | | using namespace llvm; |
27 | | |
28 | | #define DEBUG_TYPE "ipconstprop" |
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 | 17 | IPCP() : ModulePass(ID) { |
39 | 17 | initializeIPCPPass(*PassRegistry::getPassRegistry()); |
40 | 17 | } |
41 | | |
42 | | bool runOnModule(Module &M) override; |
43 | | }; |
44 | | } |
45 | | |
46 | | /// PropagateConstantsIntoArguments - Look at all uses of the specified |
47 | | /// function. If all uses are direct call sites, and all pass a particular |
48 | | /// constant in for an argument, propagate that constant in as the argument. |
49 | | /// |
50 | 50 | static bool PropagateConstantsIntoArguments(Function &F) { |
51 | 50 | if (F.arg_empty() || F.use_empty()48 ) return false2 ; // No arguments? Early exit. |
52 | 48 | |
53 | 48 | // For each argument, keep track of its constant value and whether it is a |
54 | 48 | // constant or not. The bool is driven to true when found to be non-constant. |
55 | 48 | SmallVector<std::pair<Constant*, bool>, 16> ArgumentConstants; |
56 | 48 | ArgumentConstants.resize(F.arg_size()); |
57 | 48 | |
58 | 48 | unsigned NumNonconstant = 0; |
59 | 73 | for (Use &U : F.uses()) { |
60 | 73 | User *UR = U.getUser(); |
61 | 73 | // Ignore blockaddress uses. |
62 | 73 | if (isa<BlockAddress>(UR)) continue0 ; |
63 | 73 | |
64 | 73 | // If no abstract call site was created we did not understand the use, bail. |
65 | 73 | AbstractCallSite ACS(&U); |
66 | 73 | if (!ACS) |
67 | 0 | return false; |
68 | 73 | |
69 | 73 | // Mismatched argument count is undefined behavior. Simply bail out to avoid |
70 | 73 | // handling of such situations below (avoiding asserts/crashes). |
71 | 73 | unsigned NumActualArgs = ACS.getNumArgOperands(); |
72 | 73 | if (F.isVarArg() ? ArgumentConstants.size() > NumActualArgs4 |
73 | 73 | : ArgumentConstants.size() != NumActualArgs69 ) |
74 | 4 | return false; |
75 | 69 | |
76 | 69 | // Check out all of the potentially constant arguments. Note that we don't |
77 | 69 | // inspect varargs here. |
78 | 69 | Function::arg_iterator Arg = F.arg_begin(); |
79 | 166 | for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++Arg97 ) { |
80 | 111 | |
81 | 111 | // If this argument is known non-constant, ignore it. |
82 | 111 | if (ArgumentConstants[i].second) |
83 | 4 | continue; |
84 | 107 | |
85 | 107 | Value *V = ACS.getCallArgOperand(i); |
86 | 107 | Constant *C = dyn_cast_or_null<Constant>(V); |
87 | 107 | |
88 | 107 | // Mismatched argument type is undefined behavior. Simply bail out to avoid |
89 | 107 | // handling of such situations below (avoiding asserts/crashes). |
90 | 107 | if (C && Arg->getType() != C->getType()71 ) |
91 | 1 | return false; |
92 | 106 | |
93 | 106 | // We can only propagate thread independent values through callbacks. |
94 | 106 | // This is different to direct/indirect call sites because for them we |
95 | 106 | // know the thread executing the caller and callee is the same. For |
96 | 106 | // callbacks this is not guaranteed, thus a thread dependent value could |
97 | 106 | // be different for the caller and callee, making it invalid to propagate. |
98 | 106 | if (C && ACS.isCallbackCall()70 && C->isThreadDependent()54 ) { |
99 | 2 | // Argument became non-constant. If all arguments are non-constant now, |
100 | 2 | // give up on this function. |
101 | 2 | if (++NumNonconstant == ArgumentConstants.size()) |
102 | 0 | return false; |
103 | 2 | |
104 | 2 | ArgumentConstants[i].second = true; |
105 | 2 | continue; |
106 | 2 | } |
107 | 104 | |
108 | 104 | if (C && ArgumentConstants[i].first == nullptr68 ) { |
109 | 43 | ArgumentConstants[i].first = C; // First constant seen. |
110 | 61 | } else if (C && ArgumentConstants[i].first == C25 ) { |
111 | 15 | // Still the constant value we think it is. |
112 | 46 | } else if (V == &*Arg) { |
113 | 2 | // Ignore recursive calls passing argument down. |
114 | 44 | } else { |
115 | 44 | // Argument became non-constant. If all arguments are non-constant now, |
116 | 44 | // give up on this function. |
117 | 44 | if (++NumNonconstant == ArgumentConstants.size()) |
118 | 13 | return false; |
119 | 31 | ArgumentConstants[i].second = true; |
120 | 31 | } |
121 | 104 | } |
122 | 69 | } |
123 | 48 | |
124 | 48 | // If we got to this point, there is a constant argument! |
125 | 48 | assert(NumNonconstant != ArgumentConstants.size()); |
126 | 30 | bool MadeChange = false; |
127 | 30 | Function::arg_iterator AI = F.arg_begin(); |
128 | 90 | for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI60 ) { |
129 | 60 | // Do we have a constant argument? |
130 | 60 | if (ArgumentConstants[i].second || AI->use_empty()30 || |
131 | 60 | AI->hasInAllocaAttr()15 || (15 AI->hasByValAttr()15 && !F.onlyReadsMemory()0 )) |
132 | 45 | continue; |
133 | 15 | |
134 | 15 | Value *V = ArgumentConstants[i].first; |
135 | 15 | if (!V) V = UndefValue::get(AI->getType())1 ; |
136 | 15 | AI->replaceAllUsesWith(V); |
137 | 15 | ++NumArgumentsProped; |
138 | 15 | MadeChange = true; |
139 | 15 | } |
140 | 30 | return MadeChange; |
141 | 48 | } |
142 | | |
143 | | |
144 | | // Check to see if this function returns one or more constants. If so, replace |
145 | | // all callers that use those return values with the constant value. This will |
146 | | // leave in the actual return values and instructions, but deadargelim will |
147 | | // clean that up. |
148 | | // |
149 | | // Additionally if a function always returns one of its arguments directly, |
150 | | // callers will be updated to use the value they pass in directly instead of |
151 | | // using the return value. |
152 | 87 | static bool PropagateConstantReturn(Function &F) { |
153 | 87 | if (F.getReturnType()->isVoidTy()) |
154 | 34 | return false; // No return value. |
155 | 53 | |
156 | 53 | // We can infer and propagate the return value only when we know that the |
157 | 53 | // definition we'll get at link time is *exactly* the definition we see now. |
158 | 53 | // For more details, see GlobalValue::mayBeDerefined. |
159 | 53 | if (!F.isDefinitionExact()) |
160 | 2 | return false; |
161 | 51 | |
162 | 51 | // Don't touch naked functions. The may contain asm returning |
163 | 51 | // value we don't see, so we may end up interprocedurally propagating |
164 | 51 | // the return value incorrectly. |
165 | 51 | if (F.hasFnAttribute(Attribute::Naked)) |
166 | 1 | return false; |
167 | 50 | |
168 | 50 | // Check to see if this function returns a constant. |
169 | 50 | SmallVector<Value *,4> RetVals; |
170 | 50 | StructType *STy = dyn_cast<StructType>(F.getReturnType()); |
171 | 50 | if (STy) |
172 | 12 | for (unsigned i = 0, e = STy->getNumElements(); 4 i < e; ++i8 ) |
173 | 8 | RetVals.push_back(UndefValue::get(STy->getElementType(i))); |
174 | 46 | else |
175 | 46 | RetVals.push_back(UndefValue::get(F.getReturnType())); |
176 | 50 | |
177 | 50 | unsigned NumNonConstant = 0; |
178 | 50 | for (BasicBlock &BB : F) |
179 | 59 | if (ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator())) { |
180 | 99 | for (unsigned i = 0, e = RetVals.size(); i != e; ++i45 ) { |
181 | 60 | // Already found conflicting return values? |
182 | 60 | Value *RV = RetVals[i]; |
183 | 60 | if (!RV) |
184 | 0 | continue; |
185 | 60 | |
186 | 60 | // Find the returned value |
187 | 60 | Value *V; |
188 | 60 | if (!STy) |
189 | 48 | V = RI->getOperand(0); |
190 | 12 | else |
191 | 12 | V = FindInsertedValue(RI->getOperand(0), i); |
192 | 60 | |
193 | 60 | if (V) { |
194 | 58 | // Ignore undefs, we can change them into anything |
195 | 58 | if (isa<UndefValue>(V)) |
196 | 0 | continue; |
197 | 58 | |
198 | 58 | // Try to see if all the rets return the same constant or argument. |
199 | 58 | if (isa<Constant>(V) || isa<Argument>(V)29 ) { |
200 | 43 | if (isa<UndefValue>(RV)) { |
201 | 37 | // No value found yet? Try the current one. |
202 | 37 | RetVals[i] = V; |
203 | 37 | continue; |
204 | 37 | } |
205 | 6 | // Returning the same value? Good. |
206 | 6 | if (RV == V) |
207 | 4 | continue; |
208 | 19 | } |
209 | 58 | } |
210 | 19 | // Different or no known return value? Don't propagate this return |
211 | 19 | // value. |
212 | 19 | RetVals[i] = nullptr; |
213 | 19 | // All values non-constant? Stop looking. |
214 | 19 | if (++NumNonConstant == RetVals.size()) |
215 | 15 | return false; |
216 | 19 | } |
217 | 54 | } |
218 | 50 | |
219 | 50 | // If we got here, the function returns at least one constant value. Loop |
220 | 50 | // over all users, replacing any uses of the return value with the returned |
221 | 50 | // constant. |
222 | 50 | bool MadeChange = false; |
223 | 57 | for (Use &U : F.uses()) { |
224 | 57 | CallSite CS(U.getUser()); |
225 | 57 | Instruction* Call = CS.getInstruction(); |
226 | 57 | |
227 | 57 | // Not a call instruction or a call instruction that's not calling F |
228 | 57 | // directly? |
229 | 57 | if (!Call || !CS.isCallee(&U)52 ) |
230 | 41 | continue; |
231 | 16 | |
232 | 16 | // Call result not used? |
233 | 16 | if (Call->use_empty()) |
234 | 8 | continue; |
235 | 8 | |
236 | 8 | MadeChange = true; |
237 | 8 | |
238 | 8 | if (!STy) { |
239 | 4 | Value* New = RetVals[0]; |
240 | 4 | if (Argument *A = dyn_cast<Argument>(New)) |
241 | 1 | // Was an argument returned? Then find the corresponding argument in |
242 | 1 | // the call instruction and use that. |
243 | 1 | New = CS.getArgument(A->getArgNo()); |
244 | 4 | Call->replaceAllUsesWith(New); |
245 | 4 | continue; |
246 | 4 | } |
247 | 4 | |
248 | 11 | for (auto I = Call->user_begin(), E = Call->user_end(); 4 I != E;) { |
249 | 7 | Instruction *Ins = cast<Instruction>(*I); |
250 | 7 | |
251 | 7 | // Increment now, so we can remove the use |
252 | 7 | ++I; |
253 | 7 | |
254 | 7 | // Find the index of the retval to replace with |
255 | 7 | int index = -1; |
256 | 7 | if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Ins)) |
257 | 6 | if (EV->hasIndices()) |
258 | 6 | index = *EV->idx_begin(); |
259 | 7 | |
260 | 7 | // If this use uses a specific return value, and we have a replacement, |
261 | 7 | // replace it. |
262 | 7 | if (index != -1) { |
263 | 6 | Value *New = RetVals[index]; |
264 | 6 | if (New) { |
265 | 4 | if (Argument *A = dyn_cast<Argument>(New)) |
266 | 2 | // Was an argument returned? Then find the corresponding argument in |
267 | 2 | // the call instruction and use that. |
268 | 2 | New = CS.getArgument(A->getArgNo()); |
269 | 4 | Ins->replaceAllUsesWith(New); |
270 | 4 | Ins->eraseFromParent(); |
271 | 4 | } |
272 | 6 | } |
273 | 7 | } |
274 | 4 | } |
275 | 35 | |
276 | 35 | if (MadeChange) ++NumReturnValProped6 ; |
277 | 35 | return MadeChange; |
278 | 50 | } |
279 | | |
280 | | char IPCP::ID = 0; |
281 | | INITIALIZE_PASS(IPCP, "ipconstprop", |
282 | | "Interprocedural constant propagation", false, false) |
283 | | |
284 | 0 | ModulePass *llvm::createIPConstantPropagationPass() { return new IPCP(); } |
285 | | |
286 | 17 | bool IPCP::runOnModule(Module &M) { |
287 | 17 | if (skipModule(M)) |
288 | 0 | return false; |
289 | 17 | |
290 | 17 | bool Changed = false; |
291 | 17 | bool LocalChange = true; |
292 | 17 | |
293 | 17 | // FIXME: instead of using smart algorithms, we just iterate until we stop |
294 | 17 | // making changes. |
295 | 44 | while (LocalChange) { |
296 | 27 | LocalChange = false; |
297 | 27 | for (Function &F : M) |
298 | 135 | if (!F.isDeclaration()) { |
299 | 87 | // Delete any klingons. |
300 | 87 | F.removeDeadConstantUsers(); |
301 | 87 | if (F.hasLocalLinkage()) |
302 | 50 | LocalChange |= PropagateConstantsIntoArguments(F); |
303 | 87 | Changed |= PropagateConstantReturn(F); |
304 | 87 | } |
305 | 27 | Changed |= LocalChange; |
306 | 27 | } |
307 | 17 | return Changed; |
308 | 17 | } |