/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Scalar/SCCP.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- SCCP.cpp - Sparse Conditional Constant Propagation -----------------===// |
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 file implements sparse conditional constant propagation and merging: |
10 | | // |
11 | | // Specifically, this: |
12 | | // * Assumes values are constant unless proven otherwise |
13 | | // * Assumes BasicBlocks are dead unless proven otherwise |
14 | | // * Proves values to be constant, and replaces them with constants |
15 | | // * Proves conditional branches to be unconditional |
16 | | // |
17 | | //===----------------------------------------------------------------------===// |
18 | | |
19 | | #include "llvm/Transforms/Scalar/SCCP.h" |
20 | | #include "llvm/ADT/ArrayRef.h" |
21 | | #include "llvm/ADT/DenseMap.h" |
22 | | #include "llvm/ADT/DenseSet.h" |
23 | | #include "llvm/ADT/MapVector.h" |
24 | | #include "llvm/ADT/PointerIntPair.h" |
25 | | #include "llvm/ADT/STLExtras.h" |
26 | | #include "llvm/ADT/SmallPtrSet.h" |
27 | | #include "llvm/ADT/SmallVector.h" |
28 | | #include "llvm/ADT/Statistic.h" |
29 | | #include "llvm/Analysis/ConstantFolding.h" |
30 | | #include "llvm/Analysis/GlobalsModRef.h" |
31 | | #include "llvm/Analysis/TargetLibraryInfo.h" |
32 | | #include "llvm/Transforms/Utils/Local.h" |
33 | | #include "llvm/Analysis/ValueLattice.h" |
34 | | #include "llvm/Analysis/ValueLatticeUtils.h" |
35 | | #include "llvm/IR/BasicBlock.h" |
36 | | #include "llvm/IR/CallSite.h" |
37 | | #include "llvm/IR/Constant.h" |
38 | | #include "llvm/IR/Constants.h" |
39 | | #include "llvm/IR/DataLayout.h" |
40 | | #include "llvm/IR/DerivedTypes.h" |
41 | | #include "llvm/IR/Function.h" |
42 | | #include "llvm/IR/GlobalVariable.h" |
43 | | #include "llvm/IR/InstVisitor.h" |
44 | | #include "llvm/IR/InstrTypes.h" |
45 | | #include "llvm/IR/Instruction.h" |
46 | | #include "llvm/IR/Instructions.h" |
47 | | #include "llvm/IR/Module.h" |
48 | | #include "llvm/IR/PassManager.h" |
49 | | #include "llvm/IR/Type.h" |
50 | | #include "llvm/IR/User.h" |
51 | | #include "llvm/IR/Value.h" |
52 | | #include "llvm/Pass.h" |
53 | | #include "llvm/Support/Casting.h" |
54 | | #include "llvm/Support/Debug.h" |
55 | | #include "llvm/Support/ErrorHandling.h" |
56 | | #include "llvm/Support/raw_ostream.h" |
57 | | #include "llvm/Transforms/Scalar.h" |
58 | | #include "llvm/Transforms/Utils/PredicateInfo.h" |
59 | | #include <cassert> |
60 | | #include <utility> |
61 | | #include <vector> |
62 | | |
63 | | using namespace llvm; |
64 | | |
65 | | #define DEBUG_TYPE "sccp" |
66 | | |
67 | | STATISTIC(NumInstRemoved, "Number of instructions removed"); |
68 | | STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable"); |
69 | | |
70 | | STATISTIC(IPNumInstRemoved, "Number of instructions removed by IPSCCP"); |
71 | | STATISTIC(IPNumArgsElimed ,"Number of arguments constant propagated by IPSCCP"); |
72 | | STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP"); |
73 | | |
74 | | namespace { |
75 | | |
76 | | /// LatticeVal class - This class represents the different lattice values that |
77 | | /// an LLVM value may occupy. It is a simple class with value semantics. |
78 | | /// |
79 | | class LatticeVal { |
80 | | enum LatticeValueTy { |
81 | | /// unknown - This LLVM Value has no known value yet. |
82 | | unknown, |
83 | | |
84 | | /// constant - This LLVM Value has a specific constant value. |
85 | | constant, |
86 | | |
87 | | /// forcedconstant - This LLVM Value was thought to be undef until |
88 | | /// ResolvedUndefsIn. This is treated just like 'constant', but if merged |
89 | | /// with another (different) constant, it goes to overdefined, instead of |
90 | | /// asserting. |
91 | | forcedconstant, |
92 | | |
93 | | /// overdefined - This instruction is not known to be constant, and we know |
94 | | /// it has a value. |
95 | | overdefined |
96 | | }; |
97 | | |
98 | | /// Val: This stores the current lattice value along with the Constant* for |
99 | | /// the constant if this is a 'constant' or 'forcedconstant' value. |
100 | | PointerIntPair<Constant *, 2, LatticeValueTy> Val; |
101 | | |
102 | 203M | LatticeValueTy getLatticeValue() const { |
103 | 203M | return Val.getInt(); |
104 | 203M | } |
105 | | |
106 | | public: |
107 | 92.6M | LatticeVal() : Val(nullptr, unknown) {} |
108 | | |
109 | 47.7M | bool isUnknown() const { return getLatticeValue() == unknown; } |
110 | | |
111 | 14.4M | bool isConstant() const { |
112 | 14.4M | return getLatticeValue() == constant || getLatticeValue() == forcedconstant10.4M ; |
113 | 14.4M | } |
114 | | |
115 | 128M | bool isOverdefined() const { return getLatticeValue() == overdefined; } |
116 | | |
117 | 6.17M | Constant *getConstant() const { |
118 | 6.17M | assert(isConstant() && "Cannot get the constant of a non-constant!"); |
119 | 6.17M | return Val.getPointer(); |
120 | 6.17M | } |
121 | | |
122 | | /// markOverdefined - Return true if this is a change in status. |
123 | 27.7M | bool markOverdefined() { |
124 | 27.7M | if (isOverdefined()) |
125 | 5.91M | return false; |
126 | 21.7M | |
127 | 21.7M | Val.setInt(overdefined); |
128 | 21.7M | return true; |
129 | 21.7M | } |
130 | | |
131 | | /// markConstant - Return true if this is a change in status. |
132 | 2.84M | bool markConstant(Constant *V) { |
133 | 2.84M | if (getLatticeValue() == constant) { // Constant but not forcedconstant. |
134 | 123k | assert(getConstant() == V && "Marking constant with different value"); |
135 | 123k | return false; |
136 | 123k | } |
137 | 2.71M | |
138 | 2.71M | if (2.71M isUnknown()2.71M ) { |
139 | 2.71M | Val.setInt(constant); |
140 | 2.71M | assert(V && "Marking constant with NULL"); |
141 | 2.71M | Val.setPointer(V); |
142 | 18.4E | } else { |
143 | 18.4E | assert(getLatticeValue() == forcedconstant && |
144 | 18.4E | "Cannot move from overdefined to constant!"); |
145 | 18.4E | // Stay at forcedconstant if the constant is the same. |
146 | 18.4E | if (V == getConstant()) return false0 ; |
147 | 18.4E | |
148 | 18.4E | // Otherwise, we go to overdefined. Assumptions made based on the |
149 | 18.4E | // forced value are possibly wrong. Assuming this is another constant |
150 | 18.4E | // could expose a contradiction. |
151 | 18.4E | Val.setInt(overdefined); |
152 | 18.4E | } |
153 | 2.71M | return true; |
154 | 2.71M | } |
155 | | |
156 | | /// getConstantInt - If this is a constant with a ConstantInt value, return it |
157 | | /// otherwise return null. |
158 | 5.00M | ConstantInt *getConstantInt() const { |
159 | 5.00M | if (isConstant()) |
160 | 177k | return dyn_cast<ConstantInt>(getConstant()); |
161 | 4.82M | return nullptr; |
162 | 4.82M | } |
163 | | |
164 | | /// getBlockAddress - If this is a constant with a BlockAddress value, return |
165 | | /// it, otherwise return null. |
166 | 18 | BlockAddress *getBlockAddress() const { |
167 | 18 | if (isConstant()) |
168 | 4 | return dyn_cast<BlockAddress>(getConstant()); |
169 | 14 | return nullptr; |
170 | 14 | } |
171 | | |
172 | 18 | void markForcedConstant(Constant *V) { |
173 | 18 | assert(isUnknown() && "Can't force a defined value!"); |
174 | 18 | Val.setInt(forcedconstant); |
175 | 18 | Val.setPointer(V); |
176 | 18 | } |
177 | | |
178 | 5.98M | ValueLatticeElement toValueLattice() const { |
179 | 5.98M | if (isOverdefined()) |
180 | 3.45M | return ValueLatticeElement::getOverdefined(); |
181 | 2.53M | if (isConstant()) |
182 | 2.36M | return ValueLatticeElement::get(getConstant()); |
183 | 162k | return ValueLatticeElement(); |
184 | 162k | } |
185 | | }; |
186 | | |
187 | | //===----------------------------------------------------------------------===// |
188 | | // |
189 | | /// SCCPSolver - This class is a general purpose solver for Sparse Conditional |
190 | | /// Constant Propagation. |
191 | | /// |
192 | | class SCCPSolver : public InstVisitor<SCCPSolver> { |
193 | | const DataLayout &DL; |
194 | | const TargetLibraryInfo *TLI; |
195 | | SmallPtrSet<BasicBlock *, 8> BBExecutable; // The BBs that are executable. |
196 | | DenseMap<Value *, LatticeVal> ValueState; // The state each value is in. |
197 | | // The state each parameter is in. |
198 | | DenseMap<Value *, ValueLatticeElement> ParamState; |
199 | | |
200 | | /// StructValueState - This maintains ValueState for values that have |
201 | | /// StructType, for example for formal arguments, calls, insertelement, etc. |
202 | | DenseMap<std::pair<Value *, unsigned>, LatticeVal> StructValueState; |
203 | | |
204 | | /// GlobalValue - If we are tracking any values for the contents of a global |
205 | | /// variable, we keep a mapping from the constant accessor to the element of |
206 | | /// the global, to the currently known value. If the value becomes |
207 | | /// overdefined, it's entry is simply removed from this map. |
208 | | DenseMap<GlobalVariable *, LatticeVal> TrackedGlobals; |
209 | | |
210 | | /// TrackedRetVals - If we are tracking arguments into and the return |
211 | | /// value out of a function, it will have an entry in this map, indicating |
212 | | /// what the known return value for the function is. |
213 | | MapVector<Function *, LatticeVal> TrackedRetVals; |
214 | | |
215 | | /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions |
216 | | /// that return multiple values. |
217 | | MapVector<std::pair<Function *, unsigned>, LatticeVal> TrackedMultipleRetVals; |
218 | | |
219 | | /// MRVFunctionsTracked - Each function in TrackedMultipleRetVals is |
220 | | /// represented here for efficient lookup. |
221 | | SmallPtrSet<Function *, 16> MRVFunctionsTracked; |
222 | | |
223 | | /// MustTailFunctions - Each function here is a callee of non-removable |
224 | | /// musttail call site. |
225 | | SmallPtrSet<Function *, 16> MustTailCallees; |
226 | | |
227 | | /// TrackingIncomingArguments - This is the set of functions for whose |
228 | | /// arguments we make optimistic assumptions about and try to prove as |
229 | | /// constants. |
230 | | SmallPtrSet<Function *, 16> TrackingIncomingArguments; |
231 | | |
232 | | /// The reason for two worklists is that overdefined is the lowest state |
233 | | /// on the lattice, and moving things to overdefined as fast as possible |
234 | | /// makes SCCP converge much faster. |
235 | | /// |
236 | | /// By having a separate worklist, we accomplish this because everything |
237 | | /// possibly overdefined will become overdefined at the soonest possible |
238 | | /// point. |
239 | | SmallVector<Value *, 64> OverdefinedInstWorkList; |
240 | | SmallVector<Value *, 64> InstWorkList; |
241 | | |
242 | | // The BasicBlock work list |
243 | | SmallVector<BasicBlock *, 64> BBWorkList; |
244 | | |
245 | | /// KnownFeasibleEdges - Entries in this set are edges which have already had |
246 | | /// PHI nodes retriggered. |
247 | | using Edge = std::pair<BasicBlock *, BasicBlock *>; |
248 | | DenseSet<Edge> KnownFeasibleEdges; |
249 | | |
250 | | DenseMap<Function *, AnalysisResultsForFn> AnalysisResults; |
251 | | DenseMap<Value *, SmallPtrSet<User *, 2>> AdditionalUsers; |
252 | | |
253 | | public: |
254 | 590k | void addAnalysis(Function &F, AnalysisResultsForFn A) { |
255 | 590k | AnalysisResults.insert({&F, std::move(A)}); |
256 | 590k | } |
257 | | |
258 | 14.1M | const PredicateBase *getPredicateInfoFor(Instruction *I) { |
259 | 14.1M | auto A = AnalysisResults.find(I->getParent()->getParent()); |
260 | 14.1M | if (A == AnalysisResults.end()) |
261 | 0 | return nullptr; |
262 | 14.1M | return A->second.PredInfo->getPredicateInfoFor(I); |
263 | 14.1M | } |
264 | | |
265 | 590k | DomTreeUpdater getDTU(Function &F) { |
266 | 590k | auto A = AnalysisResults.find(&F); |
267 | 590k | assert(A != AnalysisResults.end() && "Need analysis results for function."); |
268 | 590k | return {A->second.DT, A->second.PDT, DomTreeUpdater::UpdateStrategy::Lazy}; |
269 | 590k | } |
270 | | |
271 | | SCCPSolver(const DataLayout &DL, const TargetLibraryInfo *tli) |
272 | 480k | : DL(DL), TLI(tli) {} |
273 | | |
274 | | /// MarkBlockExecutable - This method can be used by clients to mark all of |
275 | | /// the blocks that are known to be intrinsically live in the processed unit. |
276 | | /// |
277 | | /// This returns true if the block was not considered live before. |
278 | 7.83M | bool MarkBlockExecutable(BasicBlock *BB) { |
279 | 7.83M | if (!BBExecutable.insert(BB).second) |
280 | 2.52M | return false; |
281 | 5.31M | LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n'); |
282 | 5.31M | BBWorkList.push_back(BB); // Add the block to the work list! |
283 | 5.31M | return true; |
284 | 5.31M | } |
285 | | |
286 | | /// TrackValueOfGlobalVariable - Clients can use this method to |
287 | | /// inform the SCCPSolver that it should track loads and stores to the |
288 | | /// specified global variable if it can. This is only legal to call if |
289 | | /// performing Interprocedural SCCP. |
290 | 4.79k | void TrackValueOfGlobalVariable(GlobalVariable *GV) { |
291 | 4.79k | // We only track the contents of scalar globals. |
292 | 4.79k | if (GV->getValueType()->isSingleValueType()) { |
293 | 4.77k | LatticeVal &IV = TrackedGlobals[GV]; |
294 | 4.77k | if (!isa<UndefValue>(GV->getInitializer())) |
295 | 4.77k | IV.markConstant(GV->getInitializer()); |
296 | 4.77k | } |
297 | 4.79k | } |
298 | | |
299 | | /// AddTrackedFunction - If the SCCP solver is supposed to track calls into |
300 | | /// and out of the specified function (which cannot have its address taken), |
301 | | /// this method must be called. |
302 | 98.5k | void AddTrackedFunction(Function *F) { |
303 | 98.5k | // Add an entry, F -> undef. |
304 | 98.5k | if (auto *STy = dyn_cast<StructType>(F->getReturnType())) { |
305 | 866 | MRVFunctionsTracked.insert(F); |
306 | 2.49k | for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i1.62k ) |
307 | 1.62k | TrackedMultipleRetVals.insert(std::make_pair(std::make_pair(F, i), |
308 | 1.62k | LatticeVal())); |
309 | 866 | } else |
310 | 97.7k | TrackedRetVals.insert(std::make_pair(F, LatticeVal())); |
311 | 98.5k | } |
312 | | |
313 | | /// AddMustTailCallee - If the SCCP solver finds that this function is called |
314 | | /// from non-removable musttail call site. |
315 | 5 | void AddMustTailCallee(Function *F) { |
316 | 5 | MustTailCallees.insert(F); |
317 | 5 | } |
318 | | |
319 | | /// Returns true if the given function is called from non-removable musttail |
320 | | /// call site. |
321 | 759 | bool isMustTailCallee(Function *F) { |
322 | 759 | return MustTailCallees.count(F); |
323 | 759 | } |
324 | | |
325 | 25.3k | void AddArgumentTrackedFunction(Function *F) { |
326 | 25.3k | TrackingIncomingArguments.insert(F); |
327 | 25.3k | } |
328 | | |
329 | | /// Returns true if the given function is in the solver's set of |
330 | | /// argument-tracked functions. |
331 | 7.65k | bool isArgumentTrackedFunction(Function *F) { |
332 | 7.65k | return TrackingIncomingArguments.count(F); |
333 | 7.65k | } |
334 | | |
335 | | /// Solve - Solve for constants and executable blocks. |
336 | | void Solve(); |
337 | | |
338 | | /// ResolvedUndefsIn - While solving the dataflow for a function, we assume |
339 | | /// that branches on undef values cannot reach any of their successors. |
340 | | /// However, this is not a safe assumption. After we solve dataflow, this |
341 | | /// method should be use to handle this. If this returns true, the solver |
342 | | /// should be rerun. |
343 | | bool ResolvedUndefsIn(Function &F); |
344 | | |
345 | 6.52M | bool isBlockExecutable(BasicBlock *BB) const { |
346 | 6.52M | return BBExecutable.count(BB); |
347 | 6.52M | } |
348 | | |
349 | | // isEdgeFeasible - Return true if the control flow edge from the 'From' basic |
350 | | // block to the 'To' basic block is currently feasible. |
351 | | bool isEdgeFeasible(BasicBlock *From, BasicBlock *To); |
352 | | |
353 | 76.3k | std::vector<LatticeVal> getStructLatticeValueFor(Value *V) const { |
354 | 76.3k | std::vector<LatticeVal> StructValues; |
355 | 76.3k | auto *STy = dyn_cast<StructType>(V->getType()); |
356 | 76.3k | assert(STy && "getStructLatticeValueFor() can be called only on structs"); |
357 | 222k | for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i146k ) { |
358 | 146k | auto I = StructValueState.find(std::make_pair(V, i)); |
359 | 146k | assert(I != StructValueState.end() && "Value not in valuemap!"); |
360 | 146k | StructValues.push_back(I->second); |
361 | 146k | } |
362 | 76.3k | return StructValues; |
363 | 76.3k | } |
364 | | |
365 | 20.5M | const LatticeVal &getLatticeValueFor(Value *V) const { |
366 | 20.5M | assert(!V->getType()->isStructTy() && |
367 | 20.5M | "Should use getStructLatticeValueFor"); |
368 | 20.5M | DenseMap<Value *, LatticeVal>::const_iterator I = ValueState.find(V); |
369 | 20.5M | assert(I != ValueState.end() && |
370 | 20.5M | "V not found in ValueState nor Paramstate map!"); |
371 | 20.5M | return I->second; |
372 | 20.5M | } |
373 | | |
374 | | /// getTrackedRetVals - Get the inferred return value map. |
375 | 13.6k | const MapVector<Function*, LatticeVal> &getTrackedRetVals() { |
376 | 13.6k | return TrackedRetVals; |
377 | 13.6k | } |
378 | | |
379 | | /// getTrackedGlobals - Get and return the set of inferred initializers for |
380 | | /// global variables. |
381 | 13.6k | const DenseMap<GlobalVariable*, LatticeVal> &getTrackedGlobals() { |
382 | 13.6k | return TrackedGlobals; |
383 | 13.6k | } |
384 | | |
385 | | /// getMRVFunctionsTracked - Get the set of functions which return multiple |
386 | | /// values tracked by the pass. |
387 | 13.6k | const SmallPtrSet<Function *, 16> getMRVFunctionsTracked() { |
388 | 13.6k | return MRVFunctionsTracked; |
389 | 13.6k | } |
390 | | |
391 | | /// getMustTailCallees - Get the set of functions which are called |
392 | | /// from non-removable musttail call sites. |
393 | 0 | const SmallPtrSet<Function *, 16> getMustTailCallees() { |
394 | 0 | return MustTailCallees; |
395 | 0 | } |
396 | | |
397 | | /// markOverdefined - Mark the specified value overdefined. This |
398 | | /// works with both scalars and structs. |
399 | 23.7M | void markOverdefined(Value *V) { |
400 | 23.7M | if (auto *STy = dyn_cast<StructType>(V->getType())) |
401 | 374k | for (unsigned i = 0, e = STy->getNumElements(); 131k i != e; ++i243k ) |
402 | 243k | markOverdefined(getStructValueState(V, i), V); |
403 | 23.5M | else |
404 | 23.5M | markOverdefined(ValueState[V], V); |
405 | 23.7M | } |
406 | | |
407 | | // isStructLatticeConstant - Return true if all the lattice values |
408 | | // corresponding to elements of the structure are not overdefined, |
409 | | // false otherwise. |
410 | 866 | bool isStructLatticeConstant(Function *F, StructType *STy) { |
411 | 915 | for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i49 ) { |
412 | 889 | const auto &It = TrackedMultipleRetVals.find(std::make_pair(F, i)); |
413 | 889 | assert(It != TrackedMultipleRetVals.end()); |
414 | 889 | LatticeVal LV = It->second; |
415 | 889 | if (LV.isOverdefined()) |
416 | 840 | return false; |
417 | 889 | } |
418 | 866 | return true26 ; |
419 | 866 | } |
420 | | |
421 | | private: |
422 | | // pushToWorkList - Helper for markConstant/markForcedConstant/markOverdefined |
423 | 22.8M | void pushToWorkList(LatticeVal &IV, Value *V) { |
424 | 22.8M | if (IV.isOverdefined()) |
425 | 21.7M | return OverdefinedInstWorkList.push_back(V); |
426 | 1.07M | InstWorkList.push_back(V); |
427 | 1.07M | } |
428 | | |
429 | | // markConstant - Make a value be marked as "constant". If the value |
430 | | // is not already a constant, add it to the instruction work list so that |
431 | | // the users of the instruction are updated later. |
432 | 1.19M | bool markConstant(LatticeVal &IV, Value *V, Constant *C) { |
433 | 1.19M | if (!IV.markConstant(C)) return false123k ; |
434 | 1.07M | LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n'); |
435 | 1.07M | pushToWorkList(IV, V); |
436 | 1.07M | return true; |
437 | 1.07M | } |
438 | | |
439 | 649k | bool markConstant(Value *V, Constant *C) { |
440 | 649k | assert(!V->getType()->isStructTy() && "structs should use mergeInValue"); |
441 | 649k | return markConstant(ValueState[V], V, C); |
442 | 649k | } |
443 | | |
444 | 18 | void markForcedConstant(Value *V, Constant *C) { |
445 | 18 | assert(!V->getType()->isStructTy() && "structs should use mergeInValue"); |
446 | 18 | LatticeVal &IV = ValueState[V]; |
447 | 18 | IV.markForcedConstant(C); |
448 | 18 | LLVM_DEBUG(dbgs() << "markForcedConstant: " << *C << ": " << *V << '\n'); |
449 | 18 | pushToWorkList(IV, V); |
450 | 18 | } |
451 | | |
452 | | // markOverdefined - Make a value be marked as "overdefined". If the |
453 | | // value is not already overdefined, add it to the overdefined instruction |
454 | | // work list so that the users of the instruction are updated later. |
455 | 27.7M | bool markOverdefined(LatticeVal &IV, Value *V) { |
456 | 27.7M | if (!IV.markOverdefined()) return false5.91M ; |
457 | 21.7M | |
458 | 21.7M | LLVM_DEBUG(dbgs() << "markOverdefined: "; |
459 | 21.7M | if (auto *F = dyn_cast<Function>(V)) dbgs() |
460 | 21.7M | << "Function '" << F->getName() << "'\n"; |
461 | 21.7M | else dbgs() << *V << '\n'); |
462 | 21.7M | // Only instructions go on the work list |
463 | 21.7M | pushToWorkList(IV, V); |
464 | 21.7M | return true; |
465 | 21.7M | } |
466 | | |
467 | 2.18M | bool mergeInValue(LatticeVal &IV, Value *V, LatticeVal MergeWithV) { |
468 | 2.18M | if (IV.isOverdefined() || MergeWithV.isUnknown()1.34M ) |
469 | 1.08M | return false; // Noop. |
470 | 1.10M | if (MergeWithV.isOverdefined()) |
471 | 808k | return markOverdefined(IV, V); |
472 | 299k | if (IV.isUnknown()) |
473 | 249k | return markConstant(IV, V, MergeWithV.getConstant()); |
474 | 50.0k | if (IV.getConstant() != MergeWithV.getConstant()) |
475 | 4.17k | return markOverdefined(IV, V); |
476 | 45.8k | return false; |
477 | 45.8k | } |
478 | | |
479 | 1.14M | bool mergeInValue(Value *V, LatticeVal MergeWithV) { |
480 | 1.14M | assert(!V->getType()->isStructTy() && |
481 | 1.14M | "non-structs should use markConstant"); |
482 | 1.14M | return mergeInValue(ValueState[V], V, MergeWithV); |
483 | 1.14M | } |
484 | | |
485 | | /// getValueState - Return the LatticeVal object that corresponds to the |
486 | | /// value. This function handles the case when the value hasn't been seen yet |
487 | | /// by properly seeding constants etc. |
488 | 72.2M | LatticeVal &getValueState(Value *V) { |
489 | 72.2M | assert(!V->getType()->isStructTy() && "Should use getStructValueState"); |
490 | 72.2M | |
491 | 72.2M | std::pair<DenseMap<Value*, LatticeVal>::iterator, bool> I = |
492 | 72.2M | ValueState.insert(std::make_pair(V, LatticeVal())); |
493 | 72.2M | LatticeVal &LV = I.first->second; |
494 | 72.2M | |
495 | 72.2M | if (!I.second) |
496 | 68.5M | return LV; // Common case, already in the map. |
497 | 3.79M | |
498 | 3.79M | if (auto *C = dyn_cast<Constant>(V)) { |
499 | 1.53M | // Undef values remain unknown. |
500 | 1.53M | if (!isa<UndefValue>(V)) |
501 | 1.53M | LV.markConstant(C); // Constants are constant |
502 | 1.53M | } |
503 | 3.79M | |
504 | 3.79M | // All others are underdefined by default. |
505 | 3.79M | return LV; |
506 | 3.79M | } |
507 | | |
508 | 546k | ValueLatticeElement &getParamState(Value *V) { |
509 | 546k | assert(!V->getType()->isStructTy() && "Should use getStructValueState"); |
510 | 546k | |
511 | 546k | std::pair<DenseMap<Value*, ValueLatticeElement>::iterator, bool> |
512 | 546k | PI = ParamState.insert(std::make_pair(V, ValueLatticeElement())); |
513 | 546k | ValueLatticeElement &LV = PI.first->second; |
514 | 546k | if (PI.second) |
515 | 49.8k | LV = getValueState(V).toValueLattice(); |
516 | 546k | |
517 | 546k | return LV; |
518 | 546k | } |
519 | | |
520 | | /// getStructValueState - Return the LatticeVal object that corresponds to the |
521 | | /// value/field pair. This function handles the case when the value hasn't |
522 | | /// been seen yet by properly seeding constants etc. |
523 | 700k | LatticeVal &getStructValueState(Value *V, unsigned i) { |
524 | 700k | assert(V->getType()->isStructTy() && "Should use getValueState"); |
525 | 700k | assert(i < cast<StructType>(V->getType())->getNumElements() && |
526 | 700k | "Invalid element #"); |
527 | 700k | |
528 | 700k | std::pair<DenseMap<std::pair<Value*, unsigned>, LatticeVal>::iterator, |
529 | 700k | bool> I = StructValueState.insert( |
530 | 700k | std::make_pair(std::make_pair(V, i), LatticeVal())); |
531 | 700k | LatticeVal &LV = I.first->second; |
532 | 700k | |
533 | 700k | if (!I.second) |
534 | 551k | return LV; // Common case, already in the map. |
535 | 149k | |
536 | 149k | if (auto *C = dyn_cast<Constant>(V)) { |
537 | 2.98k | Constant *Elt = C->getAggregateElement(i); |
538 | 2.98k | |
539 | 2.98k | if (!Elt) |
540 | 0 | LV.markOverdefined(); // Unknown sort of constant. |
541 | 2.98k | else if (isa<UndefValue>(Elt)) |
542 | 2.94k | ; // Undef values remain unknown. |
543 | 36 | else |
544 | 36 | LV.markConstant(Elt); // Constants are constant. |
545 | 2.98k | } |
546 | 149k | |
547 | 149k | // All others are underdefined by default. |
548 | 149k | return LV; |
549 | 149k | } |
550 | | |
551 | | /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB |
552 | | /// work list if it is not already executable. |
553 | 11.1M | bool markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) { |
554 | 11.1M | if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second) |
555 | 4.57M | return false; // This edge is already known to be executable! |
556 | 6.53M | |
557 | 6.53M | if (!MarkBlockExecutable(Dest)) { |
558 | 2.27M | // If the destination is already executable, we just made an *edge* |
559 | 2.27M | // feasible that wasn't before. Revisit the PHI nodes in the block |
560 | 2.27M | // because they have potentially new operands. |
561 | 2.27M | LLVM_DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName() |
562 | 2.27M | << " -> " << Dest->getName() << '\n'); |
563 | 2.27M | |
564 | 2.27M | for (PHINode &PN : Dest->phis()) |
565 | 1.78M | visitPHINode(PN); |
566 | 2.27M | } |
567 | 6.53M | return true; |
568 | 6.53M | } |
569 | | |
570 | | // getFeasibleSuccessors - Return a vector of booleans to indicate which |
571 | | // successors are reachable from a given terminator instruction. |
572 | | void getFeasibleSuccessors(Instruction &TI, SmallVectorImpl<bool> &Succs); |
573 | | |
574 | | // OperandChangedState - This method is invoked on all of the users of an |
575 | | // instruction that was just changed state somehow. Based on this |
576 | | // information, we need to update the specified user of this instruction. |
577 | 31.9M | void OperandChangedState(Instruction *I) { |
578 | 31.9M | if (BBExecutable.count(I->getParent())) // Inst is executable? |
579 | 29.0M | visit(*I); |
580 | 31.9M | } |
581 | | |
582 | | // Add U as additional user of V. |
583 | 35.4k | void addAdditionalUser(Value *V, User *U) { |
584 | 35.4k | auto Iter = AdditionalUsers.insert({V, {}}); |
585 | 35.4k | Iter.first->second.insert(U); |
586 | 35.4k | } |
587 | | |
588 | | // Mark I's users as changed, including AdditionalUsers. |
589 | 21.9M | void markUsersAsChanged(Value *I) { |
590 | 21.9M | for (User *U : I->users()) |
591 | 31.9M | if (auto *UI = dyn_cast<Instruction>(U)) |
592 | 31.9M | OperandChangedState(UI); |
593 | 21.9M | |
594 | 21.9M | auto Iter = AdditionalUsers.find(I); |
595 | 21.9M | if (Iter != AdditionalUsers.end()) { |
596 | 21.6k | for (User *U : Iter->second) |
597 | 21.6k | if (auto *UI = dyn_cast<Instruction>(U)) |
598 | 21.6k | OperandChangedState(UI); |
599 | 21.6k | } |
600 | 21.9M | } |
601 | | |
602 | | private: |
603 | | friend class InstVisitor<SCCPSolver>; |
604 | | |
605 | | // visit implementations - Something changed in this instruction. Either an |
606 | | // operand made a transition, or the instruction is newly executable. Change |
607 | | // the value type of I to reflect these changes if appropriate. |
608 | | void visitPHINode(PHINode &I); |
609 | | |
610 | | // Terminators |
611 | | |
612 | | void visitReturnInst(ReturnInst &I); |
613 | | void visitTerminator(Instruction &TI); |
614 | | |
615 | | void visitCastInst(CastInst &I); |
616 | | void visitSelectInst(SelectInst &I); |
617 | | void visitUnaryOperator(Instruction &I); |
618 | | void visitBinaryOperator(Instruction &I); |
619 | | void visitCmpInst(CmpInst &I); |
620 | | void visitExtractValueInst(ExtractValueInst &EVI); |
621 | | void visitInsertValueInst(InsertValueInst &IVI); |
622 | | |
623 | 4 | void visitCatchSwitchInst(CatchSwitchInst &CPI) { |
624 | 4 | markOverdefined(&CPI); |
625 | 4 | visitTerminator(CPI); |
626 | 4 | } |
627 | | |
628 | | // Instructions that cannot be folded away. |
629 | | |
630 | | void visitStoreInst (StoreInst &I); |
631 | | void visitLoadInst (LoadInst &I); |
632 | | void visitGetElementPtrInst(GetElementPtrInst &I); |
633 | | |
634 | 10.1M | void visitCallInst (CallInst &I) { |
635 | 10.1M | visitCallSite(&I); |
636 | 10.1M | } |
637 | | |
638 | 149k | void visitInvokeInst (InvokeInst &II) { |
639 | 149k | visitCallSite(&II); |
640 | 149k | visitTerminator(II); |
641 | 149k | } |
642 | | |
643 | 0 | void visitCallBrInst (CallBrInst &CBI) { |
644 | 0 | visitCallSite(&CBI); |
645 | 0 | visitTerminator(CBI); |
646 | 0 | } |
647 | | |
648 | | void visitCallSite (CallSite CS); |
649 | 29.4k | void visitResumeInst (ResumeInst &I) { /*returns void*/ } |
650 | 76.4k | void visitUnreachableInst(UnreachableInst &I) { /*returns void*/ } |
651 | 12.2k | void visitFenceInst (FenceInst &I) { /*returns void*/ } |
652 | | |
653 | 494k | void visitInstruction(Instruction &I) { |
654 | 494k | // All the instructions we don't do any special handling for just |
655 | 494k | // go to overdefined. |
656 | 494k | LLVM_DEBUG(dbgs() << "SCCP: Don't know how to handle: " << I << '\n'); |
657 | 494k | markOverdefined(&I); |
658 | 494k | } |
659 | | }; |
660 | | |
661 | | } // end anonymous namespace |
662 | | |
663 | | // getFeasibleSuccessors - Return a vector of booleans to indicate which |
664 | | // successors are reachable from a given terminator instruction. |
665 | | void SCCPSolver::getFeasibleSuccessors(Instruction &TI, |
666 | 6.49M | SmallVectorImpl<bool> &Succs) { |
667 | 6.49M | Succs.resize(TI.getNumSuccessors()); |
668 | 6.49M | if (auto *BI = dyn_cast<BranchInst>(&TI)) { |
669 | 6.27M | if (BI->isUnconditional()) { |
670 | 1.82M | Succs[0] = true; |
671 | 1.82M | return; |
672 | 1.82M | } |
673 | 4.44M | |
674 | 4.44M | LatticeVal BCValue = getValueState(BI->getCondition()); |
675 | 4.44M | ConstantInt *CI = BCValue.getConstantInt(); |
676 | 4.44M | if (!CI) { |
677 | 4.30M | // Overdefined condition variables, and branches on unfoldable constant |
678 | 4.30M | // conditions, mean the branch could go either way. |
679 | 4.30M | if (!BCValue.isUnknown()) |
680 | 4.28M | Succs[0] = Succs[1] = true; |
681 | 4.30M | return; |
682 | 4.30M | } |
683 | 138k | |
684 | 138k | // Constant condition variables mean the branch can only go a single way. |
685 | 138k | Succs[CI->isZero()] = true; |
686 | 138k | return; |
687 | 138k | } |
688 | 216k | |
689 | 216k | // Unwinding instructions successors are always executable. |
690 | 216k | if (TI.isExceptionalTerminator()) { |
691 | 149k | Succs.assign(TI.getNumSuccessors(), true); |
692 | 149k | return; |
693 | 149k | } |
694 | 66.2k | |
695 | 66.2k | if (auto *SI = dyn_cast<SwitchInst>(&TI)) { |
696 | 66.2k | if (!SI->getNumCases()) { |
697 | 1 | Succs[0] = true; |
698 | 1 | return; |
699 | 1 | } |
700 | 66.2k | LatticeVal SCValue = getValueState(SI->getCondition()); |
701 | 66.2k | ConstantInt *CI = SCValue.getConstantInt(); |
702 | 66.2k | |
703 | 66.2k | if (!CI) { // Overdefined or unknown condition? |
704 | 61.9k | // All destinations are executable! |
705 | 61.9k | if (!SCValue.isUnknown()) |
706 | 61.8k | Succs.assign(TI.getNumSuccessors(), true); |
707 | 61.9k | return; |
708 | 61.9k | } |
709 | 4.23k | |
710 | 4.23k | Succs[SI->findCaseValue(CI)->getSuccessorIndex()] = true; |
711 | 4.23k | return; |
712 | 4.23k | } |
713 | 18 | |
714 | 18 | // In case of indirect branch and its address is a blockaddress, we mark |
715 | 18 | // the target as executable. |
716 | 18 | if (auto *IBR = dyn_cast<IndirectBrInst>(&TI)) { |
717 | 18 | // Casts are folded by visitCastInst. |
718 | 18 | LatticeVal IBRValue = getValueState(IBR->getAddress()); |
719 | 18 | BlockAddress *Addr = IBRValue.getBlockAddress(); |
720 | 18 | if (!Addr) { // Overdefined or unknown condition? |
721 | 14 | // All destinations are executable! |
722 | 14 | if (!IBRValue.isUnknown()) |
723 | 13 | Succs.assign(TI.getNumSuccessors(), true); |
724 | 14 | return; |
725 | 14 | } |
726 | 4 | |
727 | 4 | BasicBlock* T = Addr->getBasicBlock(); |
728 | 4 | assert(Addr->getFunction() == T->getParent() && |
729 | 4 | "Block address of a different function ?"); |
730 | 7 | for (unsigned i = 0; i < IBR->getNumSuccessors(); ++i3 ) { |
731 | 7 | // This is the target. |
732 | 7 | if (IBR->getDestination(i) == T) { |
733 | 4 | Succs[i] = true; |
734 | 4 | return; |
735 | 4 | } |
736 | 7 | } |
737 | 4 | |
738 | 4 | // If we didn't find our destination in the IBR successor list, then we |
739 | 4 | // have undefined behavior. Its ok to assume no successor is executable. |
740 | 4 | return0 ; |
741 | 0 | } |
742 | 0 | |
743 | 0 | // In case of callbr, we pessimistically assume that all successors are |
744 | 0 | // feasible. |
745 | 0 | if (isa<CallBrInst>(&TI)) { |
746 | 0 | Succs.assign(TI.getNumSuccessors(), true); |
747 | 0 | return; |
748 | 0 | } |
749 | 0 | |
750 | 0 | LLVM_DEBUG(dbgs() << "Unknown terminator instruction: " << TI << '\n'); |
751 | 0 | llvm_unreachable("SCCP: Don't know how to handle this terminator!"); |
752 | 0 | } |
753 | | |
754 | | // isEdgeFeasible - Return true if the control flow edge from the 'From' basic |
755 | | // block to the 'To' basic block is currently feasible. |
756 | 2.87M | bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) { |
757 | 2.87M | // Check if we've called markEdgeExecutable on the edge yet. (We could |
758 | 2.87M | // be more aggressive and try to consider edges which haven't been marked |
759 | 2.87M | // yet, but there isn't any need.) |
760 | 2.87M | return KnownFeasibleEdges.count(Edge(From, To)); |
761 | 2.87M | } |
762 | | |
763 | | // visit Implementations - Something changed in this instruction, either an |
764 | | // operand made a transition, or the instruction is newly executable. Change |
765 | | // the value type of I to reflect these changes if appropriate. This method |
766 | | // makes sure to do the following actions: |
767 | | // |
768 | | // 1. If a phi node merges two constants in, and has conflicting value coming |
769 | | // from different branches, or if the PHI node merges in an overdefined |
770 | | // value, then the PHI node becomes overdefined. |
771 | | // 2. If a phi node merges only constants in, and they all agree on value, the |
772 | | // PHI node becomes a constant value equal to that. |
773 | | // 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant |
774 | | // 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined |
775 | | // 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined |
776 | | // 6. If a conditional branch has a value that is constant, make the selected |
777 | | // destination executable |
778 | | // 7. If a conditional branch has a value that is overdefined, make all |
779 | | // successors executable. |
780 | 5.00M | void SCCPSolver::visitPHINode(PHINode &PN) { |
781 | 5.00M | // If this PN returns a struct, just mark the result overdefined. |
782 | 5.00M | // TODO: We could do a lot better than this if code actually uses this. |
783 | 5.00M | if (PN.getType()->isStructTy()) |
784 | 11.5k | return (void)markOverdefined(&PN); |
785 | 4.99M | |
786 | 4.99M | if (getValueState(&PN).isOverdefined()) |
787 | 3.31M | return; // Quick exit |
788 | 1.68M | |
789 | 1.68M | // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant, |
790 | 1.68M | // and slow us down a lot. Just mark them overdefined. |
791 | 1.68M | if (PN.getNumIncomingValues() > 64) |
792 | 78 | return (void)markOverdefined(&PN); |
793 | 1.68M | |
794 | 1.68M | // Look at all of the executable operands of the PHI node. If any of them |
795 | 1.68M | // are overdefined, the PHI becomes overdefined as well. If they are all |
796 | 1.68M | // constant, and they agree with each other, the PHI becomes the identical |
797 | 1.68M | // constant. If they are constant and don't agree, the PHI is overdefined. |
798 | 1.68M | // If there are no executable operands, the PHI remains unknown. |
799 | 1.68M | Constant *OperandVal = nullptr; |
800 | 4.34M | for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i2.66M ) { |
801 | 3.80M | LatticeVal IV = getValueState(PN.getIncomingValue(i)); |
802 | 3.80M | if (IV.isUnknown()) continue928k ; // Doesn't influence PHI node. |
803 | 2.87M | |
804 | 2.87M | if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) |
805 | 578k | continue; |
806 | 2.29M | |
807 | 2.29M | if (IV.isOverdefined()) // PHI node becomes overdefined! |
808 | 828k | return (void)markOverdefined(&PN); |
809 | 1.46M | |
810 | 1.46M | if (!OperandVal) { // Grab the first value. |
811 | 894k | OperandVal = IV.getConstant(); |
812 | 894k | continue; |
813 | 894k | } |
814 | 573k | |
815 | 573k | // There is already a reachable operand. If we conflict with it, |
816 | 573k | // then the PHI node becomes overdefined. If we agree with it, we |
817 | 573k | // can continue on. |
818 | 573k | |
819 | 573k | // Check to see if there are two different constants merging, if so, the PHI |
820 | 573k | // node is overdefined. |
821 | 573k | if (IV.getConstant() != OperandVal) |
822 | 306k | return (void)markOverdefined(&PN); |
823 | 573k | } |
824 | 1.68M | |
825 | 1.68M | // If we exited the loop, this means that the PHI node only has constant |
826 | 1.68M | // arguments that agree with each other(and OperandVal is the constant) or |
827 | 1.68M | // OperandVal is null because there are no defined incoming arguments. If |
828 | 1.68M | // this is the case, the PHI remains unknown. |
829 | 1.68M | if (546k OperandVal546k ) |
830 | 510k | markConstant(&PN, OperandVal); // Acquire operand value |
831 | 546k | } |
832 | | |
833 | 1.69M | void SCCPSolver::visitReturnInst(ReturnInst &I) { |
834 | 1.69M | if (I.getNumOperands() == 0) return316k ; // ret void |
835 | 1.37M | |
836 | 1.37M | Function *F = I.getParent()->getParent(); |
837 | 1.37M | Value *ResultOp = I.getOperand(0); |
838 | 1.37M | |
839 | 1.37M | // If we are tracking the return value of this function, merge it in. |
840 | 1.37M | if (!TrackedRetVals.empty() && !ResultOp->getType()->isStructTy()353k ) { |
841 | 349k | MapVector<Function*, LatticeVal>::iterator TFRVI = |
842 | 349k | TrackedRetVals.find(F); |
843 | 349k | if (TFRVI != TrackedRetVals.end()) { |
844 | 115k | mergeInValue(TFRVI->second, F, getValueState(ResultOp)); |
845 | 115k | return; |
846 | 115k | } |
847 | 1.25M | } |
848 | 1.25M | |
849 | 1.25M | // Handle functions that return multiple values. |
850 | 1.25M | if (!TrackedMultipleRetVals.empty()) { |
851 | 10.1k | if (auto *STy = dyn_cast<StructType>(ResultOp->getType())) |
852 | 3.16k | if (MRVFunctionsTracked.count(F)) |
853 | 7.22k | for (unsigned i = 0, e = STy->getNumElements(); 2.46k i != e; ++i4.76k ) |
854 | 4.76k | mergeInValue(TrackedMultipleRetVals[std::make_pair(F, i)], F, |
855 | 4.76k | getStructValueState(ResultOp, i)); |
856 | 10.1k | } |
857 | 1.25M | } |
858 | | |
859 | 6.49M | void SCCPSolver::visitTerminator(Instruction &TI) { |
860 | 6.49M | SmallVector<bool, 16> SuccFeasible; |
861 | 6.49M | getFeasibleSuccessors(TI, SuccFeasible); |
862 | 6.49M | |
863 | 6.49M | BasicBlock *BB = TI.getParent(); |
864 | 6.49M | |
865 | 6.49M | // Mark all feasible successors executable. |
866 | 17.8M | for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i11.3M ) |
867 | 11.3M | if (SuccFeasible[i]) |
868 | 11.1M | markEdgeExecutable(BB, TI.getSuccessor(i)); |
869 | 6.49M | } |
870 | | |
871 | 4.85M | void SCCPSolver::visitCastInst(CastInst &I) { |
872 | 4.85M | LatticeVal OpSt = getValueState(I.getOperand(0)); |
873 | 4.85M | if (OpSt.isOverdefined()) // Inherit overdefinedness of operand |
874 | 4.64M | markOverdefined(&I); |
875 | 211k | else if (OpSt.isConstant()) { |
876 | 103k | // Fold the constant as we build. |
877 | 103k | Constant *C = ConstantFoldCastOperand(I.getOpcode(), OpSt.getConstant(), |
878 | 103k | I.getType(), DL); |
879 | 103k | if (isa<UndefValue>(C)) |
880 | 4 | return; |
881 | 103k | // Propagate constant value |
882 | 103k | markConstant(&I, C); |
883 | 103k | } |
884 | 4.85M | } |
885 | | |
886 | 289k | void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) { |
887 | 289k | // If this returns a struct, mark all elements over defined, we don't track |
888 | 289k | // structs in structs. |
889 | 289k | if (EVI.getType()->isStructTy()) |
890 | 193 | return (void)markOverdefined(&EVI); |
891 | 288k | |
892 | 288k | // If this is extracting from more than one level of struct, we don't know. |
893 | 288k | if (EVI.getNumIndices() != 1) |
894 | 625 | return (void)markOverdefined(&EVI); |
895 | 288k | |
896 | 288k | Value *AggVal = EVI.getAggregateOperand(); |
897 | 288k | if (AggVal->getType()->isStructTy()) { |
898 | 252k | unsigned i = *EVI.idx_begin(); |
899 | 252k | LatticeVal EltVal = getStructValueState(AggVal, i); |
900 | 252k | mergeInValue(getValueState(&EVI), &EVI, EltVal); |
901 | 252k | } else { |
902 | 36.0k | // Otherwise, must be extracting from an array. |
903 | 36.0k | return (void)markOverdefined(&EVI); |
904 | 36.0k | } |
905 | 288k | } |
906 | | |
907 | 55.8k | void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) { |
908 | 55.8k | auto *STy = dyn_cast<StructType>(IVI.getType()); |
909 | 55.8k | if (!STy) |
910 | 18.0k | return (void)markOverdefined(&IVI); |
911 | 37.8k | |
912 | 37.8k | // If this has more than one index, we can't handle it, drive all results to |
913 | 37.8k | // undef. |
914 | 37.8k | if (IVI.getNumIndices() != 1) |
915 | 13.6k | return (void)markOverdefined(&IVI); |
916 | 24.1k | |
917 | 24.1k | Value *Aggr = IVI.getAggregateOperand(); |
918 | 24.1k | unsigned Idx = *IVI.idx_begin(); |
919 | 24.1k | |
920 | 24.1k | // Compute the result based on what we're inserting. |
921 | 73.0k | for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i48.8k ) { |
922 | 48.8k | // This passes through all values that aren't the inserted element. |
923 | 48.8k | if (i != Idx) { |
924 | 24.6k | LatticeVal EltVal = getStructValueState(Aggr, i); |
925 | 24.6k | mergeInValue(getStructValueState(&IVI, i), &IVI, EltVal); |
926 | 24.6k | continue; |
927 | 24.6k | } |
928 | 24.1k | |
929 | 24.1k | Value *Val = IVI.getInsertedValueOperand(); |
930 | 24.1k | if (Val->getType()->isStructTy()) |
931 | 0 | // We don't track structs in structs. |
932 | 0 | markOverdefined(getStructValueState(&IVI, i), &IVI); |
933 | 24.1k | else { |
934 | 24.1k | LatticeVal InVal = getValueState(Val); |
935 | 24.1k | mergeInValue(getStructValueState(&IVI, i), &IVI, InVal); |
936 | 24.1k | } |
937 | 24.1k | } |
938 | 24.1k | } |
939 | | |
940 | 517k | void SCCPSolver::visitSelectInst(SelectInst &I) { |
941 | 517k | // If this select returns a struct, just mark the result overdefined. |
942 | 517k | // TODO: We could do a lot better than this if code actually uses this. |
943 | 517k | if (I.getType()->isStructTy()) |
944 | 0 | return (void)markOverdefined(&I); |
945 | 517k | |
946 | 517k | LatticeVal CondValue = getValueState(I.getCondition()); |
947 | 517k | if (CondValue.isUnknown()) |
948 | 57.7k | return; |
949 | 460k | |
950 | 460k | if (ConstantInt *CondCB = CondValue.getConstantInt()) { |
951 | 5.87k | Value *OpVal = CondCB->isZero() ? I.getFalseValue()3.00k : I.getTrueValue()2.87k ; |
952 | 5.87k | mergeInValue(&I, getValueState(OpVal)); |
953 | 5.87k | return; |
954 | 5.87k | } |
955 | 454k | |
956 | 454k | // Otherwise, the condition is overdefined or a constant we can't evaluate. |
957 | 454k | // See if we can produce something better than overdefined based on the T/F |
958 | 454k | // value. |
959 | 454k | LatticeVal TVal = getValueState(I.getTrueValue()); |
960 | 454k | LatticeVal FVal = getValueState(I.getFalseValue()); |
961 | 454k | |
962 | 454k | // select ?, C, C -> C. |
963 | 454k | if (TVal.isConstant() && FVal.isConstant()148k && |
964 | 454k | TVal.getConstant() == FVal.getConstant()65.8k ) |
965 | 483 | return (void)markConstant(&I, FVal.getConstant()); |
966 | 453k | |
967 | 453k | if (TVal.isUnknown()) // select ?, undef, X -> X. |
968 | 4.37k | return (void)mergeInValue(&I, FVal); |
969 | 449k | if (FVal.isUnknown()) // select ?, X, undef -> X. |
970 | 1.42k | return (void)mergeInValue(&I, TVal); |
971 | 447k | markOverdefined(&I); |
972 | 447k | } |
973 | | |
974 | | // Handle Unary Operators. |
975 | 4 | void SCCPSolver::visitUnaryOperator(Instruction &I) { |
976 | 4 | LatticeVal V0State = getValueState(I.getOperand(0)); |
977 | 4 | |
978 | 4 | LatticeVal &IV = ValueState[&I]; |
979 | 4 | if (IV.isOverdefined()) return0 ; |
980 | 4 | |
981 | 4 | if (V0State.isConstant()) { |
982 | 3 | Constant *C = ConstantExpr::get(I.getOpcode(), V0State.getConstant()); |
983 | 3 | |
984 | 3 | // op Y -> undef. |
985 | 3 | if (isa<UndefValue>(C)) |
986 | 0 | return; |
987 | 3 | return (void)markConstant(IV, &I, C); |
988 | 3 | } |
989 | 1 | |
990 | 1 | // If something is undef, wait for it to resolve. |
991 | 1 | if (!V0State.isOverdefined()) |
992 | 1 | return; |
993 | 0 | |
994 | 0 | markOverdefined(&I); |
995 | 0 | } |
996 | | |
997 | | // Handle Binary Operators. |
998 | 5.06M | void SCCPSolver::visitBinaryOperator(Instruction &I) { |
999 | 5.06M | LatticeVal V1State = getValueState(I.getOperand(0)); |
1000 | 5.06M | LatticeVal V2State = getValueState(I.getOperand(1)); |
1001 | 5.06M | |
1002 | 5.06M | LatticeVal &IV = ValueState[&I]; |
1003 | 5.06M | if (IV.isOverdefined()) return2.51M ; |
1004 | 2.54M | |
1005 | 2.54M | if (V1State.isConstant() && V2State.isConstant()439k ) { |
1006 | 284k | Constant *C = ConstantExpr::get(I.getOpcode(), V1State.getConstant(), |
1007 | 284k | V2State.getConstant()); |
1008 | 284k | // X op Y -> undef. |
1009 | 284k | if (isa<UndefValue>(C)) |
1010 | 92 | return; |
1011 | 284k | return (void)markConstant(IV, &I, C); |
1012 | 284k | } |
1013 | 2.25M | |
1014 | 2.25M | // If something is undef, wait for it to resolve. |
1015 | 2.25M | if (!V1State.isOverdefined() && !V2State.isOverdefined()285k ) |
1016 | 25.7k | return; |
1017 | 2.23M | |
1018 | 2.23M | // Otherwise, one of our operands is overdefined. Try to produce something |
1019 | 2.23M | // better than overdefined with some tricks. |
1020 | 2.23M | // If this is 0 / Y, it doesn't matter that the second operand is |
1021 | 2.23M | // overdefined, and we can replace it with zero. |
1022 | 2.23M | if (I.getOpcode() == Instruction::UDiv || I.getOpcode() == Instruction::SDiv2.21M ) |
1023 | 41.8k | if (V1State.isConstant() && V1State.getConstant()->isNullValue()4.21k ) |
1024 | 126 | return (void)markConstant(IV, &I, V1State.getConstant()); |
1025 | 2.23M | |
1026 | 2.23M | // If this is: |
1027 | 2.23M | // -> AND/MUL with 0 |
1028 | 2.23M | // -> OR with -1 |
1029 | 2.23M | // it doesn't matter that the other operand is overdefined. |
1030 | 2.23M | if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Mul1.93M || |
1031 | 2.23M | I.getOpcode() == Instruction::Or1.74M ) { |
1032 | 622k | LatticeVal *NonOverdefVal = nullptr; |
1033 | 622k | if (!V1State.isOverdefined()) |
1034 | 66.8k | NonOverdefVal = &V1State; |
1035 | 555k | else if (!V2State.isOverdefined()) |
1036 | 252k | NonOverdefVal = &V2State; |
1037 | 622k | |
1038 | 622k | if (NonOverdefVal) { |
1039 | 319k | if (NonOverdefVal->isUnknown()) |
1040 | 69.1k | return; |
1041 | 250k | |
1042 | 250k | if (I.getOpcode() == Instruction::And || |
1043 | 250k | I.getOpcode() == Instruction::Mul93.0k ) { |
1044 | 221k | // X and 0 = 0 |
1045 | 221k | // X * 0 = 0 |
1046 | 221k | if (NonOverdefVal->getConstant()->isNullValue()) |
1047 | 7.23k | return (void)markConstant(IV, &I, NonOverdefVal->getConstant()); |
1048 | 28.8k | } else { |
1049 | 28.8k | // X or -1 = -1 |
1050 | 28.8k | if (ConstantInt *CI = NonOverdefVal->getConstantInt()) |
1051 | 28.7k | if (CI->isMinusOne()) |
1052 | 551 | return (void)markConstant(IV, &I, NonOverdefVal->getConstant()); |
1053 | 2.15M | } |
1054 | 250k | } |
1055 | 622k | } |
1056 | 2.15M | |
1057 | 2.15M | markOverdefined(&I); |
1058 | 2.15M | } |
1059 | | |
1060 | | // Handle ICmpInst instruction. |
1061 | 5.29M | void SCCPSolver::visitCmpInst(CmpInst &I) { |
1062 | 5.29M | // Do not cache this lookup, getValueState calls later in the function might |
1063 | 5.29M | // invalidate the reference. |
1064 | 5.29M | if (ValueState[&I].isOverdefined()) return2.59M ; |
1065 | 2.69M | |
1066 | 2.69M | Value *Op1 = I.getOperand(0); |
1067 | 2.69M | Value *Op2 = I.getOperand(1); |
1068 | 2.69M | |
1069 | 2.69M | // For parameters, use ParamState which includes constant range info if |
1070 | 2.69M | // available. |
1071 | 2.69M | auto V1Param = ParamState.find(Op1); |
1072 | 2.69M | ValueLatticeElement V1State = (V1Param != ParamState.end()) |
1073 | 2.69M | ? V1Param->second5.73k |
1074 | 2.69M | : getValueState(Op1).toValueLattice()2.69M ; |
1075 | 2.69M | |
1076 | 2.69M | auto V2Param = ParamState.find(Op2); |
1077 | 2.69M | ValueLatticeElement V2State = V2Param != ParamState.end() |
1078 | 2.69M | ? V2Param->second3.23k |
1079 | 2.69M | : getValueState(Op2).toValueLattice()2.69M ; |
1080 | 2.69M | |
1081 | 2.69M | Constant *C = V1State.getCompare(I.getPredicate(), I.getType(), V2State); |
1082 | 2.69M | if (C) { |
1083 | 203k | if (isa<UndefValue>(C)) |
1084 | 94.9k | return; |
1085 | 108k | LatticeVal CV; |
1086 | 108k | CV.markConstant(C); |
1087 | 108k | mergeInValue(&I, CV); |
1088 | 108k | return; |
1089 | 108k | } |
1090 | 2.49M | |
1091 | 2.49M | // If operands are still unknown, wait for it to resolve. |
1092 | 2.49M | if (!V1State.isOverdefined() && !V2State.isOverdefined()166k && |
1093 | 2.49M | !ValueState[&I].isConstant()294 ) |
1094 | 188 | return; |
1095 | 2.49M | |
1096 | 2.49M | markOverdefined(&I); |
1097 | 2.49M | } |
1098 | | |
1099 | | // Handle getelementptr instructions. If all operands are constants then we |
1100 | | // can turn this into a getelementptr ConstantExpr. |
1101 | 9.01M | void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) { |
1102 | 9.01M | if (ValueState[&I].isOverdefined()) return3.93M ; |
1103 | 5.07M | |
1104 | 5.07M | SmallVector<Constant*, 8> Operands; |
1105 | 5.07M | Operands.reserve(I.getNumOperands()); |
1106 | 5.07M | |
1107 | 5.37M | for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i296k ) { |
1108 | 5.33M | LatticeVal State = getValueState(I.getOperand(i)); |
1109 | 5.33M | if (State.isUnknown()) |
1110 | 415k | return; // Operands are not resolved yet. |
1111 | 4.91M | |
1112 | 4.91M | if (State.isOverdefined()) |
1113 | 4.62M | return (void)markOverdefined(&I); |
1114 | 296k | |
1115 | 296k | assert(State.isConstant() && "Unknown state!"); |
1116 | 296k | Operands.push_back(State.getConstant()); |
1117 | 296k | } |
1118 | 5.07M | |
1119 | 5.07M | Constant *Ptr = Operands[0]; |
1120 | 35.0k | auto Indices = makeArrayRef(Operands.begin() + 1, Operands.end()); |
1121 | 35.0k | Constant *C = |
1122 | 35.0k | ConstantExpr::getGetElementPtr(I.getSourceElementType(), Ptr, Indices); |
1123 | 35.0k | if (isa<UndefValue>(C)) |
1124 | 0 | return; |
1125 | 35.0k | markConstant(&I, C); |
1126 | 35.0k | } |
1127 | | |
1128 | 4.81M | void SCCPSolver::visitStoreInst(StoreInst &SI) { |
1129 | 4.81M | // If this store is of a struct, ignore it. |
1130 | 4.81M | if (SI.getOperand(0)->getType()->isStructTy()) |
1131 | 24 | return; |
1132 | 4.81M | |
1133 | 4.81M | if (TrackedGlobals.empty() || !isa<GlobalVariable>(SI.getOperand(1))493k ) |
1134 | 4.77M | return; |
1135 | 41.8k | |
1136 | 41.8k | GlobalVariable *GV = cast<GlobalVariable>(SI.getOperand(1)); |
1137 | 41.8k | DenseMap<GlobalVariable*, LatticeVal>::iterator I = TrackedGlobals.find(GV); |
1138 | 41.8k | if (I == TrackedGlobals.end() || I->second.isOverdefined()5.10k ) return36.7k ; |
1139 | 5.10k | |
1140 | 5.10k | // Get the value we are storing into the global, then merge it. |
1141 | 5.10k | mergeInValue(I->second, GV, getValueState(SI.getOperand(0))); |
1142 | 5.10k | if (I->second.isOverdefined()) |
1143 | 4.42k | TrackedGlobals.erase(I); // No need to keep tracking this! |
1144 | 5.10k | } |
1145 | | |
1146 | | // Handle load instructions. If the operand is a constant pointer to a constant |
1147 | | // global, we can replace the load with the loaded constant value! |
1148 | 5.52M | void SCCPSolver::visitLoadInst(LoadInst &I) { |
1149 | 5.52M | // If this load is of a struct, just mark the result overdefined. |
1150 | 5.52M | if (I.getType()->isStructTy()) |
1151 | 14 | return (void)markOverdefined(&I); |
1152 | 5.52M | |
1153 | 5.52M | LatticeVal PtrVal = getValueState(I.getOperand(0)); |
1154 | 5.52M | if (PtrVal.isUnknown()) return43.6k ; // The pointer is not resolved yet! |
1155 | 5.48M | |
1156 | 5.48M | LatticeVal &IV = ValueState[&I]; |
1157 | 5.48M | if (IV.isOverdefined()) return2.42M ; |
1158 | 3.05M | |
1159 | 3.05M | if (!PtrVal.isConstant() || I.isVolatile()450k ) |
1160 | 2.62M | return (void)markOverdefined(IV, &I); |
1161 | 431k | |
1162 | 431k | Constant *Ptr = PtrVal.getConstant(); |
1163 | 431k | |
1164 | 431k | // load null is undefined. |
1165 | 431k | if (isa<ConstantPointerNull>(Ptr)) { |
1166 | 611 | if (NullPointerIsDefined(I.getFunction(), I.getPointerAddressSpace())) |
1167 | 2 | return (void)markOverdefined(IV, &I); |
1168 | 609 | else |
1169 | 609 | return; |
1170 | 431k | } |
1171 | 431k | |
1172 | 431k | // Transform load (constant global) into the value loaded. |
1173 | 431k | if (auto *GV = dyn_cast<GlobalVariable>(Ptr)) { |
1174 | 291k | if (!TrackedGlobals.empty()) { |
1175 | 50.3k | // If we are tracking this global, merge in the known value for it. |
1176 | 50.3k | DenseMap<GlobalVariable*, LatticeVal>::iterator It = |
1177 | 50.3k | TrackedGlobals.find(GV); |
1178 | 50.3k | if (It != TrackedGlobals.end()) { |
1179 | 7.10k | mergeInValue(IV, &I, It->second); |
1180 | 7.10k | return; |
1181 | 7.10k | } |
1182 | 424k | } |
1183 | 291k | } |
1184 | 424k | |
1185 | 424k | // Transform load from a constant into a constant if possible. |
1186 | 424k | if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, I.getType(), DL)) { |
1187 | 1.58k | if (isa<UndefValue>(C)) |
1188 | 3 | return; |
1189 | 1.57k | return (void)markConstant(IV, &I, C); |
1190 | 1.57k | } |
1191 | 422k | |
1192 | 422k | // Otherwise we cannot say for certain what value this load will produce. |
1193 | 422k | // Bail out. |
1194 | 422k | markOverdefined(IV, &I); |
1195 | 422k | } |
1196 | | |
1197 | 10.3M | void SCCPSolver::visitCallSite(CallSite CS) { |
1198 | 10.3M | Function *F = CS.getCalledFunction(); |
1199 | 10.3M | Instruction *I = CS.getInstruction(); |
1200 | 10.3M | |
1201 | 10.3M | if (auto *II = dyn_cast<IntrinsicInst>(I)) { |
1202 | 2.33M | if (II->getIntrinsicID() == Intrinsic::ssa_copy) { |
1203 | 969k | if (ValueState[I].isOverdefined()) |
1204 | 358k | return; |
1205 | 611k | |
1206 | 611k | auto *PI = getPredicateInfoFor(I); |
1207 | 611k | if (!PI) |
1208 | 0 | return; |
1209 | 611k | |
1210 | 611k | Value *CopyOf = I->getOperand(0); |
1211 | 611k | auto *PBranch = dyn_cast<PredicateBranch>(PI); |
1212 | 611k | if (!PBranch) { |
1213 | 203 | mergeInValue(ValueState[I], I, getValueState(CopyOf)); |
1214 | 203 | return; |
1215 | 203 | } |
1216 | 611k | |
1217 | 611k | Value *Cond = PBranch->Condition; |
1218 | 611k | |
1219 | 611k | // Everything below relies on the condition being a comparison. |
1220 | 611k | auto *Cmp = dyn_cast<CmpInst>(Cond); |
1221 | 611k | if (!Cmp) { |
1222 | 0 | mergeInValue(ValueState[I], I, getValueState(CopyOf)); |
1223 | 0 | return; |
1224 | 0 | } |
1225 | 611k | |
1226 | 611k | Value *CmpOp0 = Cmp->getOperand(0); |
1227 | 611k | Value *CmpOp1 = Cmp->getOperand(1); |
1228 | 611k | if (CopyOf != CmpOp0 && CopyOf != CmpOp189.5k ) { |
1229 | 6.10k | mergeInValue(ValueState[I], I, getValueState(CopyOf)); |
1230 | 6.10k | return; |
1231 | 6.10k | } |
1232 | 604k | |
1233 | 604k | if (CmpOp0 != CopyOf) |
1234 | 83.4k | std::swap(CmpOp0, CmpOp1); |
1235 | 604k | |
1236 | 604k | LatticeVal OriginalVal = getValueState(CopyOf); |
1237 | 604k | LatticeVal EqVal = getValueState(CmpOp1); |
1238 | 604k | LatticeVal &IV = ValueState[I]; |
1239 | 604k | if (PBranch->TrueEdge && Cmp->getPredicate() == CmpInst::ICMP_EQ346k ) { |
1240 | 31.9k | addAdditionalUser(CmpOp1, I); |
1241 | 31.9k | if (OriginalVal.isConstant()) |
1242 | 506 | mergeInValue(IV, I, OriginalVal); |
1243 | 31.4k | else |
1244 | 31.4k | mergeInValue(IV, I, EqVal); |
1245 | 31.9k | return; |
1246 | 31.9k | } |
1247 | 572k | if (!PBranch->TrueEdge && Cmp->getPredicate() == CmpInst::ICMP_NE258k ) { |
1248 | 3.49k | addAdditionalUser(CmpOp1, I); |
1249 | 3.49k | if (OriginalVal.isConstant()) |
1250 | 475 | mergeInValue(IV, I, OriginalVal); |
1251 | 3.01k | else |
1252 | 3.01k | mergeInValue(IV, I, EqVal); |
1253 | 3.49k | return; |
1254 | 3.49k | } |
1255 | 569k | |
1256 | 569k | return (void)mergeInValue(IV, I, getValueState(CopyOf)); |
1257 | 569k | } |
1258 | 2.33M | } |
1259 | 9.37M | |
1260 | 9.37M | // The common case is that we aren't tracking the callee, either because we |
1261 | 9.37M | // are not doing interprocedural analysis or the callee is indirect, or is |
1262 | 9.37M | // external. Handle these cases first. |
1263 | 9.37M | if (!F || F->isDeclaration()8.92M ) { |
1264 | 8.90M | CallOverdefined: |
1265 | 8.90M | // Void return and not tracking callee, just bail. |
1266 | 8.90M | if (I->getType()->isVoidTy()) return3.25M ; |
1267 | 5.64M | |
1268 | 5.64M | // Otherwise, if we have a single return value case, and if the function is |
1269 | 5.64M | // a declaration, maybe we can constant fold it. |
1270 | 5.64M | if (F && F->isDeclaration()5.39M && !I->getType()->isStructTy()1.73M && |
1271 | 5.64M | canConstantFoldCallTo(cast<CallBase>(CS.getInstruction()), F)1.71M ) { |
1272 | 167k | SmallVector<Constant*, 8> Operands; |
1273 | 167k | for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end(); |
1274 | 170k | AI != E; ++AI3.23k ) { |
1275 | 169k | if (AI->get()->getType()->isStructTy()) |
1276 | 8 | return markOverdefined(I); // Can't handle struct args. |
1277 | 169k | LatticeVal State = getValueState(*AI); |
1278 | 169k | |
1279 | 169k | if (State.isUnknown()) |
1280 | 443 | return; // Operands are not resolved yet. |
1281 | 169k | if (State.isOverdefined()) |
1282 | 166k | return (void)markOverdefined(I); |
1283 | 3.23k | assert(State.isConstant() && "Unknown state!"); |
1284 | 3.23k | Operands.push_back(State.getConstant()); |
1285 | 3.23k | } |
1286 | 167k | |
1287 | 167k | if (711 getValueState(I).isOverdefined()711 ) |
1288 | 1 | return; |
1289 | 710 | |
1290 | 710 | // If we can constant fold this, mark the result of the call as a |
1291 | 710 | // constant. |
1292 | 710 | if (Constant *C = ConstantFoldCall(cast<CallBase>(CS.getInstruction()), F, |
1293 | 678 | Operands, TLI)) { |
1294 | 678 | // call -> undef. |
1295 | 678 | if (isa<UndefValue>(C)) |
1296 | 0 | return; |
1297 | 678 | return (void)markConstant(I, C); |
1298 | 678 | } |
1299 | 710 | } |
1300 | 5.47M | |
1301 | 5.47M | // Otherwise, we don't know anything about this call, mark it overdefined. |
1302 | 5.47M | return (void)markOverdefined(I); |
1303 | 5.47M | } |
1304 | 5.37M | |
1305 | 5.37M | // If this is a local function that doesn't have its address taken, mark its |
1306 | 5.37M | // entry block executable and merge in the actual arguments to the call into |
1307 | 5.37M | // the formal arguments of the function. |
1308 | 5.37M | if (!TrackingIncomingArguments.empty() && TrackingIncomingArguments.count(F)1.07M ){ |
1309 | 266k | MarkBlockExecutable(&F->front()); |
1310 | 266k | |
1311 | 266k | // Propagate information from this call site into the callee. |
1312 | 266k | CallSite::arg_iterator CAI = CS.arg_begin(); |
1313 | 266k | for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); |
1314 | 814k | AI != E; ++AI, ++CAI547k ) { |
1315 | 547k | // If this argument is byval, and if the function is not readonly, there |
1316 | 547k | // will be an implicit copy formed of the input aggregate. |
1317 | 547k | if (AI->hasByValAttr() && !F->onlyReadsMemory()995 ) { |
1318 | 993 | markOverdefined(&*AI); |
1319 | 993 | continue; |
1320 | 993 | } |
1321 | 546k | |
1322 | 546k | if (auto *STy = dyn_cast<StructType>(AI->getType())) { |
1323 | 24 | for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i16 ) { |
1324 | 16 | LatticeVal CallArg = getStructValueState(*CAI, i); |
1325 | 16 | mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg); |
1326 | 16 | } |
1327 | 546k | } else { |
1328 | 546k | // Most other parts of the Solver still only use the simpler value |
1329 | 546k | // lattice, so we propagate changes for parameters to both lattices. |
1330 | 546k | LatticeVal ConcreteArgument = getValueState(*CAI); |
1331 | 546k | bool ParamChanged = |
1332 | 546k | getParamState(&*AI).mergeIn(ConcreteArgument.toValueLattice(), DL); |
1333 | 546k | bool ValueChanged = mergeInValue(&*AI, ConcreteArgument); |
1334 | 546k | // Add argument to work list, if the state of a parameter changes but |
1335 | 546k | // ValueState does not change (because it is already overdefined there), |
1336 | 546k | // We have to take changes in ParamState into account, as it is used |
1337 | 546k | // when evaluating Cmp instructions. |
1338 | 546k | if (!ValueChanged && ParamChanged492k ) |
1339 | 971 | pushToWorkList(ValueState[&*AI], &*AI); |
1340 | 546k | } |
1341 | 546k | } |
1342 | 266k | } |
1343 | 5.37M | |
1344 | 5.37M | // If this is a single/zero retval case, see if we're tracking the function. |
1345 | 5.37M | if (auto *STy = dyn_cast<StructType>(F->getReturnType())) { |
1346 | 11.3k | if (!MRVFunctionsTracked.count(F)) |
1347 | 9.39k | goto CallOverdefined; // Not tracking this callee. |
1348 | 1.96k | |
1349 | 1.96k | // If we are tracking this callee, propagate the result of the function |
1350 | 1.96k | // into this call site. |
1351 | 5.61k | for (unsigned i = 0, e = STy->getNumElements(); 1.96k i != e; ++i3.65k ) |
1352 | 3.65k | mergeInValue(getStructValueState(I, i), I, |
1353 | 3.65k | TrackedMultipleRetVals[std::make_pair(F, i)]); |
1354 | 5.36M | } else { |
1355 | 5.36M | MapVector<Function*, LatticeVal>::iterator TFRVI = TrackedRetVals.find(F); |
1356 | 5.36M | if (TFRVI == TrackedRetVals.end()) |
1357 | 4.89M | goto CallOverdefined; // Not tracking this callee. |
1358 | 473k | |
1359 | 473k | // If so, propagate the return value of the callee into this call result. |
1360 | 473k | mergeInValue(I, TFRVI->second); |
1361 | 473k | } |
1362 | 5.37M | } |
1363 | | |
1364 | 480k | void SCCPSolver::Solve() { |
1365 | 480k | // Process the work lists until they are empty! |
1366 | 1.21M | while (!BBWorkList.empty() || !InstWorkList.empty()738k || |
1367 | 1.21M | !OverdefinedInstWorkList.empty()658k ) { |
1368 | 737k | // Process the overdefined instruction's work list first, which drives other |
1369 | 737k | // things to overdefined more quickly. |
1370 | 22.5M | while (!OverdefinedInstWorkList.empty()) { |
1371 | 21.7M | Value *I = OverdefinedInstWorkList.pop_back_val(); |
1372 | 21.7M | |
1373 | 21.7M | LLVM_DEBUG(dbgs() << "\nPopped off OI-WL: " << *I << '\n'); |
1374 | 21.7M | |
1375 | 21.7M | // "I" got into the work list because it either made the transition from |
1376 | 21.7M | // bottom to constant, or to overdefined. |
1377 | 21.7M | // |
1378 | 21.7M | // Anything on this worklist that is overdefined need not be visited |
1379 | 21.7M | // since all of its users will have already been marked as overdefined |
1380 | 21.7M | // Update all of the users of this instruction's value. |
1381 | 21.7M | // |
1382 | 21.7M | markUsersAsChanged(I); |
1383 | 21.7M | } |
1384 | 737k | |
1385 | 737k | // Process the instruction work list. |
1386 | 1.80M | while (!InstWorkList.empty()) { |
1387 | 1.07M | Value *I = InstWorkList.pop_back_val(); |
1388 | 1.07M | |
1389 | 1.07M | LLVM_DEBUG(dbgs() << "\nPopped off I-WL: " << *I << '\n'); |
1390 | 1.07M | |
1391 | 1.07M | // "I" got into the work list because it made the transition from undef to |
1392 | 1.07M | // constant. |
1393 | 1.07M | // |
1394 | 1.07M | // Anything on this worklist that is overdefined need not be visited |
1395 | 1.07M | // since all of its users will have already been marked as overdefined. |
1396 | 1.07M | // Update all of the users of this instruction's value. |
1397 | 1.07M | // |
1398 | 1.07M | if (I->getType()->isStructTy() || !getValueState(I).isOverdefined()1.07M ) |
1399 | 132k | markUsersAsChanged(I); |
1400 | 1.07M | } |
1401 | 737k | |
1402 | 737k | // Process the basic block work list. |
1403 | 6.04M | while (!BBWorkList.empty()) { |
1404 | 5.31M | BasicBlock *BB = BBWorkList.back(); |
1405 | 5.31M | BBWorkList.pop_back(); |
1406 | 5.31M | |
1407 | 5.31M | LLVM_DEBUG(dbgs() << "\nPopped off BBWL: " << *BB << '\n'); |
1408 | 5.31M | |
1409 | 5.31M | // Notify all instructions in this basic block that they are newly |
1410 | 5.31M | // executable. |
1411 | 5.31M | visit(BB); |
1412 | 5.31M | } |
1413 | 737k | } |
1414 | 480k | } |
1415 | | |
1416 | | /// ResolvedUndefsIn - While solving the dataflow for a function, we assume |
1417 | | /// that branches on undef values cannot reach any of their successors. |
1418 | | /// However, this is not a safe assumption. After we solve dataflow, this |
1419 | | /// method should be use to handle this. If this returns true, the solver |
1420 | | /// should be rerun. |
1421 | | /// |
1422 | | /// This method handles this by finding an unresolved branch and marking it one |
1423 | | /// of the edges from the block as being feasible, even though the condition |
1424 | | /// doesn't say it would otherwise be. This allows SCCP to find the rest of the |
1425 | | /// CFG and only slightly pessimizes the analysis results (by marking one, |
1426 | | /// potentially infeasible, edge feasible). This cannot usefully modify the |
1427 | | /// constraints on the condition of the branch, as that would impact other users |
1428 | | /// of the value. |
1429 | | /// |
1430 | | /// This scan also checks for values that use undefs, whose results are actually |
1431 | | /// defined. For example, 'zext i8 undef to i32' should produce all zeros |
1432 | | /// conservatively, as "(zext i8 X -> i32) & 0xFF00" must always return zero, |
1433 | | /// even if X isn't defined. |
1434 | 1.99M | bool SCCPSolver::ResolvedUndefsIn(Function &F) { |
1435 | 5.45M | for (BasicBlock &BB : F) { |
1436 | 5.45M | if (!BBExecutable.count(&BB)) |
1437 | 23.8k | continue; |
1438 | 5.43M | |
1439 | 29.1M | for (Instruction &I : BB)5.43M { |
1440 | 29.1M | // Look for instructions which produce undef values. |
1441 | 29.1M | if (I.getType()->isVoidTy()) continue9.12M ; |
1442 | 20.0M | |
1443 | 20.0M | if (auto *STy = dyn_cast<StructType>(I.getType())) { |
1444 | 77.5k | // Only a few things that can be structs matter for undef. |
1445 | 77.5k | |
1446 | 77.5k | // Tracked calls must never be marked overdefined in ResolvedUndefsIn. |
1447 | 77.5k | if (CallSite CS = CallSite(&I)) |
1448 | 10.4k | if (Function *F = CS.getCalledFunction()) |
1449 | 10.1k | if (MRVFunctionsTracked.count(F)) |
1450 | 393 | continue; |
1451 | 77.1k | |
1452 | 77.1k | // extractvalue and insertvalue don't need to be marked; they are |
1453 | 77.1k | // tracked as precisely as their operands. |
1454 | 77.1k | if (isa<ExtractValueInst>(I) || isa<InsertValueInst>(I)77.1k ) |
1455 | 15.1k | continue; |
1456 | 62.0k | |
1457 | 62.0k | // Send the results of everything else to overdefined. We could be |
1458 | 62.0k | // more precise than this but it isn't worth bothering. |
1459 | 184k | for (unsigned i = 0, e = STy->getNumElements(); 62.0k i != e; ++i122k ) { |
1460 | 122k | LatticeVal &LV = getStructValueState(&I, i); |
1461 | 122k | if (LV.isUnknown()) |
1462 | 0 | markOverdefined(LV, &I); |
1463 | 122k | } |
1464 | 62.0k | continue; |
1465 | 62.0k | } |
1466 | 19.9M | |
1467 | 19.9M | LatticeVal &LV = getValueState(&I); |
1468 | 19.9M | if (!LV.isUnknown()) continue19.9M ; |
1469 | 871 | |
1470 | 871 | // extractvalue is safe; check here because the argument is a struct. |
1471 | 871 | if (isa<ExtractValueInst>(I)) |
1472 | 1 | continue; |
1473 | 870 | |
1474 | 870 | // Compute the operand LatticeVals, for convenience below. |
1475 | 870 | // Anything taking a struct is conservatively assumed to require |
1476 | 870 | // overdefined markings. |
1477 | 870 | if (I.getOperand(0)->getType()->isStructTy()) { |
1478 | 0 | markOverdefined(&I); |
1479 | 0 | return true; |
1480 | 0 | } |
1481 | 870 | LatticeVal Op0LV = getValueState(I.getOperand(0)); |
1482 | 870 | LatticeVal Op1LV; |
1483 | 870 | if (I.getNumOperands() == 2) { |
1484 | 271 | if (I.getOperand(1)->getType()->isStructTy()) { |
1485 | 0 | markOverdefined(&I); |
1486 | 0 | return true; |
1487 | 0 | } |
1488 | 271 | |
1489 | 271 | Op1LV = getValueState(I.getOperand(1)); |
1490 | 271 | } |
1491 | 870 | // If this is an instructions whose result is defined even if the input is |
1492 | 870 | // not fully defined, propagate the information. |
1493 | 870 | Type *ITy = I.getType(); |
1494 | 870 | switch (I.getOpcode()) { |
1495 | 870 | case Instruction::Add: |
1496 | 16 | case Instruction::Sub: |
1497 | 16 | case Instruction::Trunc: |
1498 | 16 | case Instruction::FPTrunc: |
1499 | 16 | case Instruction::BitCast: |
1500 | 16 | break; // Any undef -> undef |
1501 | 16 | case Instruction::FSub: |
1502 | 0 | case Instruction::FAdd: |
1503 | 0 | case Instruction::FMul: |
1504 | 0 | case Instruction::FDiv: |
1505 | 0 | case Instruction::FRem: |
1506 | 0 | // Floating-point binary operation: be conservative. |
1507 | 0 | if (Op0LV.isUnknown() && Op1LV.isUnknown()) |
1508 | 0 | markForcedConstant(&I, Constant::getNullValue(ITy)); |
1509 | 0 | else |
1510 | 0 | markOverdefined(&I); |
1511 | 0 | return true; |
1512 | 1 | case Instruction::FNeg: |
1513 | 1 | break; // fneg undef -> undef |
1514 | 3 | case Instruction::ZExt: |
1515 | 3 | case Instruction::SExt: |
1516 | 3 | case Instruction::FPToUI: |
1517 | 3 | case Instruction::FPToSI: |
1518 | 3 | case Instruction::FPExt: |
1519 | 3 | case Instruction::PtrToInt: |
1520 | 3 | case Instruction::IntToPtr: |
1521 | 3 | case Instruction::SIToFP: |
1522 | 3 | case Instruction::UIToFP: |
1523 | 3 | // undef -> 0; some outputs are impossible |
1524 | 3 | markForcedConstant(&I, Constant::getNullValue(ITy)); |
1525 | 3 | return true; |
1526 | 7 | case Instruction::Mul: |
1527 | 7 | case Instruction::And: |
1528 | 7 | // Both operands undef -> undef |
1529 | 7 | if (Op0LV.isUnknown() && Op1LV.isUnknown()5 ) |
1530 | 0 | break; |
1531 | 7 | // undef * X -> 0. X could be zero. |
1532 | 7 | // undef & X -> 0. X could be zero. |
1533 | 7 | markForcedConstant(&I, Constant::getNullValue(ITy)); |
1534 | 7 | return true; |
1535 | 7 | case Instruction::Or: |
1536 | 1 | // Both operands undef -> undef |
1537 | 1 | if (Op0LV.isUnknown() && Op1LV.isUnknown()0 ) |
1538 | 0 | break; |
1539 | 1 | // undef | X -> -1. X could be -1. |
1540 | 1 | markForcedConstant(&I, Constant::getAllOnesValue(ITy)); |
1541 | 1 | return true; |
1542 | 3 | case Instruction::Xor: |
1543 | 3 | // undef ^ undef -> 0; strictly speaking, this is not strictly |
1544 | 3 | // necessary, but we try to be nice to people who expect this |
1545 | 3 | // behavior in simple cases |
1546 | 3 | if (Op0LV.isUnknown() && Op1LV.isUnknown()) { |
1547 | 3 | markForcedConstant(&I, Constant::getNullValue(ITy)); |
1548 | 3 | return true; |
1549 | 3 | } |
1550 | 0 | // undef ^ X -> undef |
1551 | 0 | break; |
1552 | 1 | case Instruction::SDiv: |
1553 | 1 | case Instruction::UDiv: |
1554 | 1 | case Instruction::SRem: |
1555 | 1 | case Instruction::URem: |
1556 | 1 | // X / undef -> undef. No change. |
1557 | 1 | // X % undef -> undef. No change. |
1558 | 1 | if (Op1LV.isUnknown()) break0 ; |
1559 | 1 | |
1560 | 1 | // X / 0 -> undef. No change. |
1561 | 1 | // X % 0 -> undef. No change. |
1562 | 1 | if (Op1LV.isConstant() && Op1LV.getConstant()->isZeroValue()) |
1563 | 1 | break; |
1564 | 0 | |
1565 | 0 | // undef / X -> 0. X could be maxint. |
1566 | 0 | // undef % X -> 0. X could be 1. |
1567 | 0 | markForcedConstant(&I, Constant::getNullValue(ITy)); |
1568 | 0 | return true; |
1569 | 6 | case Instruction::AShr: |
1570 | 6 | // X >>a undef -> undef. |
1571 | 6 | if (Op1LV.isUnknown()) break0 ; |
1572 | 6 | |
1573 | 6 | // Shifting by the bitwidth or more is undefined. |
1574 | 6 | if (Op1LV.isConstant()) { |
1575 | 6 | if (auto *ShiftAmt = Op1LV.getConstantInt()) |
1576 | 5 | if (ShiftAmt->getLimitedValue() >= |
1577 | 5 | ShiftAmt->getType()->getScalarSizeInBits()) |
1578 | 4 | break; |
1579 | 2 | } |
1580 | 2 | |
1581 | 2 | // undef >>a X -> 0 |
1582 | 2 | markForcedConstant(&I, Constant::getNullValue(ITy)); |
1583 | 2 | return true; |
1584 | 17 | case Instruction::LShr: |
1585 | 17 | case Instruction::Shl: |
1586 | 17 | // X << undef -> undef. |
1587 | 17 | // X >> undef -> undef. |
1588 | 17 | if (Op1LV.isUnknown()) break7 ; |
1589 | 10 | |
1590 | 10 | // Shifting by the bitwidth or more is undefined. |
1591 | 10 | if (Op1LV.isConstant()) { |
1592 | 10 | if (auto *ShiftAmt = Op1LV.getConstantInt()) |
1593 | 10 | if (ShiftAmt->getLimitedValue() >= |
1594 | 10 | ShiftAmt->getType()->getScalarSizeInBits()) |
1595 | 9 | break; |
1596 | 1 | } |
1597 | 1 | |
1598 | 1 | // undef << X -> 0 |
1599 | 1 | // undef >> X -> 0 |
1600 | 1 | markForcedConstant(&I, Constant::getNullValue(ITy)); |
1601 | 1 | return true; |
1602 | 4 | case Instruction::Select: |
1603 | 4 | Op1LV = getValueState(I.getOperand(1)); |
1604 | 4 | // undef ? X : Y -> X or Y. There could be commonality between X/Y. |
1605 | 4 | if (Op0LV.isUnknown()) { |
1606 | 4 | if (!Op1LV.isConstant()) // Pick the constant one if there is any. |
1607 | 3 | Op1LV = getValueState(I.getOperand(2)); |
1608 | 4 | } else if (0 Op1LV.isUnknown()0 ) { |
1609 | 0 | // c ? undef : undef -> undef. No change. |
1610 | 0 | Op1LV = getValueState(I.getOperand(2)); |
1611 | 0 | if (Op1LV.isUnknown()) |
1612 | 0 | break; |
1613 | 0 | // Otherwise, c ? undef : x -> x. |
1614 | 0 | } else { |
1615 | 0 | // Leave Op1LV as Operand(1)'s LatticeValue. |
1616 | 0 | } |
1617 | 4 | |
1618 | 4 | if (Op1LV.isConstant()) |
1619 | 1 | markForcedConstant(&I, Op1LV.getConstant()); |
1620 | 3 | else |
1621 | 3 | markOverdefined(&I); |
1622 | 4 | return true; |
1623 | 28 | case Instruction::Load: |
1624 | 28 | // A load here means one of two things: a load of undef from a global, |
1625 | 28 | // a load from an unknown pointer. Either way, having it return undef |
1626 | 28 | // is okay. |
1627 | 28 | break; |
1628 | 131 | case Instruction::ICmp: |
1629 | 131 | // X == undef -> undef. Other comparisons get more complicated. |
1630 | 131 | Op0LV = getValueState(I.getOperand(0)); |
1631 | 131 | Op1LV = getValueState(I.getOperand(1)); |
1632 | 131 | |
1633 | 131 | if ((Op0LV.isUnknown() || Op1LV.isUnknown()106 ) && |
1634 | 131 | cast<ICmpInst>(&I)->isEquality()33 ) |
1635 | 28 | break; |
1636 | 103 | markOverdefined(&I); |
1637 | 103 | return true; |
1638 | 599 | case Instruction::Call: |
1639 | 599 | case Instruction::Invoke: |
1640 | 599 | case Instruction::CallBr: |
1641 | 599 | // There are two reasons a call can have an undef result |
1642 | 599 | // 1. It could be tracked. |
1643 | 599 | // 2. It could be constant-foldable. |
1644 | 599 | // Because of the way we solve return values, tracked calls must |
1645 | 599 | // never be marked overdefined in ResolvedUndefsIn. |
1646 | 599 | if (Function *F = CallSite(&I).getCalledFunction()) |
1647 | 599 | if (TrackedRetVals.count(F)) |
1648 | 597 | break; |
1649 | 2 | |
1650 | 2 | // If the call is constant-foldable, we mark it overdefined because |
1651 | 2 | // we do not know what return values are valid. |
1652 | 2 | markOverdefined(&I); |
1653 | 2 | return true; |
1654 | 54 | default: |
1655 | 54 | // If we don't know what should happen here, conservatively mark it |
1656 | 54 | // overdefined. |
1657 | 54 | markOverdefined(&I); |
1658 | 54 | return true; |
1659 | 870 | } |
1660 | 870 | } |
1661 | 5.43M | |
1662 | 5.43M | // Check to see if we have a branch or switch on an undefined value. If so |
1663 | 5.43M | // we force the branch to go one way or the other to make the successor |
1664 | 5.43M | // values live. It doesn't really matter which way we force it. |
1665 | 5.43M | Instruction *TI = BB.getTerminator(); |
1666 | 5.43M | if (auto *BI = dyn_cast<BranchInst>(TI)) { |
1667 | 4.17M | if (!BI->isConditional()) continue1.87M ; |
1668 | 2.29M | if (!getValueState(BI->getCondition()).isUnknown()) |
1669 | 2.29M | continue; |
1670 | 33 | |
1671 | 33 | // If the input to SCCP is actually branch on undef, fix the undef to |
1672 | 33 | // false. |
1673 | 33 | if (isa<UndefValue>(BI->getCondition())) { |
1674 | 14 | BI->setCondition(ConstantInt::getFalse(BI->getContext())); |
1675 | 14 | markEdgeExecutable(&BB, TI->getSuccessor(1)); |
1676 | 14 | return true; |
1677 | 14 | } |
1678 | 19 | |
1679 | 19 | // Otherwise, it is a branch on a symbolic value which is currently |
1680 | 19 | // considered to be undef. Make sure some edge is executable, so a |
1681 | 19 | // branch on "undef" always flows somewhere. |
1682 | 19 | // FIXME: Distinguish between dead code and an LLVM "undef" value. |
1683 | 19 | BasicBlock *DefaultSuccessor = TI->getSuccessor(1); |
1684 | 19 | if (markEdgeExecutable(&BB, DefaultSuccessor)) |
1685 | 11 | return true; |
1686 | 8 | |
1687 | 8 | continue; |
1688 | 8 | } |
1689 | 1.25M | |
1690 | 1.25M | if (auto *IBR = dyn_cast<IndirectBrInst>(TI)) { |
1691 | 11 | // Indirect branch with no successor ?. Its ok to assume it branches |
1692 | 11 | // to no target. |
1693 | 11 | if (IBR->getNumSuccessors() < 1) |
1694 | 0 | continue; |
1695 | 11 | |
1696 | 11 | if (!getValueState(IBR->getAddress()).isUnknown()) |
1697 | 10 | continue; |
1698 | 1 | |
1699 | 1 | // If the input to SCCP is actually branch on undef, fix the undef to |
1700 | 1 | // the first successor of the indirect branch. |
1701 | 1 | if (isa<UndefValue>(IBR->getAddress())) { |
1702 | 1 | IBR->setAddress(BlockAddress::get(IBR->getSuccessor(0))); |
1703 | 1 | markEdgeExecutable(&BB, IBR->getSuccessor(0)); |
1704 | 1 | return true; |
1705 | 1 | } |
1706 | 0 | |
1707 | 0 | // Otherwise, it is a branch on a symbolic value which is currently |
1708 | 0 | // considered to be undef. Make sure some edge is executable, so a |
1709 | 0 | // branch on "undef" always flows somewhere. |
1710 | 0 | // FIXME: IndirectBr on "undef" doesn't actually need to go anywhere: |
1711 | 0 | // we can assume the branch has undefined behavior instead. |
1712 | 0 | BasicBlock *DefaultSuccessor = IBR->getSuccessor(0); |
1713 | 0 | if (markEdgeExecutable(&BB, DefaultSuccessor)) |
1714 | 0 | return true; |
1715 | 0 | |
1716 | 0 | continue; |
1717 | 0 | } |
1718 | 1.25M | |
1719 | 1.25M | if (auto *SI = dyn_cast<SwitchInst>(TI)) { |
1720 | 34.3k | if (!SI->getNumCases() || !getValueState(SI->getCondition()).isUnknown()34.3k ) |
1721 | 34.3k | continue; |
1722 | 6 | |
1723 | 6 | // If the input to SCCP is actually switch on undef, fix the undef to |
1724 | 6 | // the first constant. |
1725 | 6 | if (isa<UndefValue>(SI->getCondition())) { |
1726 | 2 | SI->setCondition(SI->case_begin()->getCaseValue()); |
1727 | 2 | markEdgeExecutable(&BB, SI->case_begin()->getCaseSuccessor()); |
1728 | 2 | return true; |
1729 | 2 | } |
1730 | 4 | |
1731 | 4 | // Otherwise, it is a branch on a symbolic value which is currently |
1732 | 4 | // considered to be undef. Make sure some edge is executable, so a |
1733 | 4 | // branch on "undef" always flows somewhere. |
1734 | 4 | // FIXME: Distinguish between dead code and an LLVM "undef" value. |
1735 | 4 | BasicBlock *DefaultSuccessor = SI->case_begin()->getCaseSuccessor(); |
1736 | 4 | if (markEdgeExecutable(&BB, DefaultSuccessor)) |
1737 | 2 | return true; |
1738 | 2 | |
1739 | 2 | continue; |
1740 | 2 | } |
1741 | 1.25M | } |
1742 | 1.99M | |
1743 | 1.99M | return false1.99M ; |
1744 | 1.99M | } |
1745 | | |
1746 | 20.6M | static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) { |
1747 | 20.6M | Constant *Const = nullptr; |
1748 | 20.6M | if (V->getType()->isStructTy()) { |
1749 | 76.3k | std::vector<LatticeVal> IVs = Solver.getStructLatticeValueFor(V); |
1750 | 76.3k | if (llvm::any_of(IVs, |
1751 | 76.4k | [](const LatticeVal &LV) { return LV.isOverdefined(); })) |
1752 | 76.3k | return false; |
1753 | 36 | std::vector<Constant *> ConstVals; |
1754 | 36 | auto *ST = dyn_cast<StructType>(V->getType()); |
1755 | 93 | for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i57 ) { |
1756 | 57 | LatticeVal V = IVs[i]; |
1757 | 57 | ConstVals.push_back(V.isConstant() |
1758 | 57 | ? V.getConstant()46 |
1759 | 57 | : UndefValue::get(ST->getElementType(i))11 ); |
1760 | 57 | } |
1761 | 36 | Const = ConstantStruct::get(ST, ConstVals); |
1762 | 20.5M | } else { |
1763 | 20.5M | const LatticeVal &IV = Solver.getLatticeValueFor(V); |
1764 | 20.5M | if (IV.isOverdefined()) |
1765 | 20.5M | return false; |
1766 | 37.4k | |
1767 | 37.4k | Const = IV.isConstant() ? IV.getConstant()37.2k : UndefValue::get(V->getType())178 ; |
1768 | 37.4k | } |
1769 | 20.6M | assert(Const && "Constant is nullptr here!"); |
1770 | 37.5k | |
1771 | 37.5k | // Replacing `musttail` instructions with constant breaks `musttail` invariant |
1772 | 37.5k | // unless the call itself can be removed |
1773 | 37.5k | CallInst *CI = dyn_cast<CallInst>(V); |
1774 | 37.5k | if (CI && CI->isMustTailCall()22.1k && !CI->isSafeToRemove()7 ) { |
1775 | 5 | CallSite CS(CI); |
1776 | 5 | Function *F = CS.getCalledFunction(); |
1777 | 5 | |
1778 | 5 | // Don't zap returns of the callee |
1779 | 5 | if (F) |
1780 | 5 | Solver.AddMustTailCallee(F); |
1781 | 5 | |
1782 | 5 | LLVM_DEBUG(dbgs() << " Can\'t treat the result of musttail call : " << *CI |
1783 | 5 | << " as a constant\n"); |
1784 | 5 | return false; |
1785 | 5 | } |
1786 | 37.5k | |
1787 | 37.5k | LLVM_DEBUG(dbgs() << " Constant: " << *Const << " = " << *V << '\n'); |
1788 | 37.5k | |
1789 | 37.5k | // Replaces all of the uses of a variable with uses of the constant. |
1790 | 37.5k | V->replaceAllUsesWith(Const); |
1791 | 37.5k | return true; |
1792 | 37.5k | } |
1793 | | |
1794 | | // runSCCP() - Run the Sparse Conditional Constant Propagation algorithm, |
1795 | | // and return true if the function was modified. |
1796 | | static bool runSCCP(Function &F, const DataLayout &DL, |
1797 | 467k | const TargetLibraryInfo *TLI) { |
1798 | 467k | LLVM_DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n"); |
1799 | 467k | SCCPSolver Solver(DL, TLI); |
1800 | 467k | |
1801 | 467k | // Mark the first block of the function as being executable. |
1802 | 467k | Solver.MarkBlockExecutable(&F.front()); |
1803 | 467k | |
1804 | 467k | // Mark all arguments to the function as being overdefined. |
1805 | 467k | for (Argument &AI : F.args()) |
1806 | 954k | Solver.markOverdefined(&AI); |
1807 | 467k | |
1808 | 467k | // Solve for constants. |
1809 | 467k | bool ResolvedUndefs = true; |
1810 | 934k | while (ResolvedUndefs) { |
1811 | 467k | Solver.Solve(); |
1812 | 467k | LLVM_DEBUG(dbgs() << "RESOLVING UNDEFs\n"); |
1813 | 467k | ResolvedUndefs = Solver.ResolvedUndefsIn(F); |
1814 | 467k | } |
1815 | 467k | |
1816 | 467k | bool MadeChanges = false; |
1817 | 467k | |
1818 | 467k | // If we decided that there are basic blocks that are dead in this function, |
1819 | 467k | // delete their contents now. Note that we cannot actually delete the blocks, |
1820 | 467k | // as we cannot modify the CFG of the function. |
1821 | 467k | |
1822 | 2.91M | for (BasicBlock &BB : F) { |
1823 | 2.91M | if (!Solver.isBlockExecutable(&BB)) { |
1824 | 8.05k | LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB); |
1825 | 8.05k | |
1826 | 8.05k | ++NumDeadBlocks; |
1827 | 8.05k | NumInstRemoved += removeAllNonTerminatorAndEHPadInstructions(&BB); |
1828 | 8.05k | |
1829 | 8.05k | MadeChanges = true; |
1830 | 8.05k | continue; |
1831 | 8.05k | } |
1832 | 2.90M | |
1833 | 2.90M | // Iterate over all of the instructions in a function, replacing them with |
1834 | 2.90M | // constants if we have found them to be of constant values. |
1835 | 17.9M | for (BasicBlock::iterator BI = BB.begin(), E = BB.end(); 2.90M BI != E;) { |
1836 | 15.0M | Instruction *Inst = &*BI++; |
1837 | 15.0M | if (Inst->getType()->isVoidTy() || Inst->isTerminator()10.0M ) |
1838 | 4.98M | continue; |
1839 | 10.0M | |
1840 | 10.0M | if (tryToReplaceWithConstant(Solver, Inst)) { |
1841 | 849 | if (isInstructionTriviallyDead(Inst)) |
1842 | 848 | Inst->eraseFromParent(); |
1843 | 849 | // Hey, we just changed something! |
1844 | 849 | MadeChanges = true; |
1845 | 849 | ++NumInstRemoved; |
1846 | 849 | } |
1847 | 10.0M | } |
1848 | 2.90M | } |
1849 | 467k | |
1850 | 467k | return MadeChanges; |
1851 | 467k | } |
1852 | | |
1853 | 1.17k | PreservedAnalyses SCCPPass::run(Function &F, FunctionAnalysisManager &AM) { |
1854 | 1.17k | const DataLayout &DL = F.getParent()->getDataLayout(); |
1855 | 1.17k | auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); |
1856 | 1.17k | if (!runSCCP(F, DL, &TLI)) |
1857 | 1.17k | return PreservedAnalyses::all(); |
1858 | 3 | |
1859 | 3 | auto PA = PreservedAnalyses(); |
1860 | 3 | PA.preserve<GlobalsAA>(); |
1861 | 3 | PA.preserveSet<CFGAnalyses>(); |
1862 | 3 | return PA; |
1863 | 3 | } |
1864 | | |
1865 | | namespace { |
1866 | | |
1867 | | //===--------------------------------------------------------------------===// |
1868 | | // |
1869 | | /// SCCP Class - This class uses the SCCPSolver to implement a per-function |
1870 | | /// Sparse Conditional Constant Propagator. |
1871 | | /// |
1872 | | class SCCPLegacyPass : public FunctionPass { |
1873 | | public: |
1874 | | // Pass identification, replacement for typeid |
1875 | | static char ID; |
1876 | | |
1877 | 13.5k | SCCPLegacyPass() : FunctionPass(ID) { |
1878 | 13.5k | initializeSCCPLegacyPassPass(*PassRegistry::getPassRegistry()); |
1879 | 13.5k | } |
1880 | | |
1881 | 13.5k | void getAnalysisUsage(AnalysisUsage &AU) const override { |
1882 | 13.5k | AU.addRequired<TargetLibraryInfoWrapperPass>(); |
1883 | 13.5k | AU.addPreserved<GlobalsAAWrapperPass>(); |
1884 | 13.5k | AU.setPreservesCFG(); |
1885 | 13.5k | } |
1886 | | |
1887 | | // runOnFunction - Run the Sparse Conditional Constant Propagation |
1888 | | // algorithm, and return true if the function was modified. |
1889 | 465k | bool runOnFunction(Function &F) override { |
1890 | 465k | if (skipFunction(F)) |
1891 | 48 | return false; |
1892 | 465k | const DataLayout &DL = F.getParent()->getDataLayout(); |
1893 | 465k | const TargetLibraryInfo *TLI = |
1894 | 465k | &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); |
1895 | 465k | return runSCCP(F, DL, TLI); |
1896 | 465k | } |
1897 | | }; |
1898 | | |
1899 | | } // end anonymous namespace |
1900 | | |
1901 | | char SCCPLegacyPass::ID = 0; |
1902 | | |
1903 | 48.9k | INITIALIZE_PASS_BEGIN(SCCPLegacyPass, "sccp", |
1904 | 48.9k | "Sparse Conditional Constant Propagation", false, false) |
1905 | 48.9k | INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) |
1906 | 48.9k | INITIALIZE_PASS_END(SCCPLegacyPass, "sccp", |
1907 | | "Sparse Conditional Constant Propagation", false, false) |
1908 | | |
1909 | | // createSCCPPass - This is the public interface to this file. |
1910 | 13.5k | FunctionPass *llvm::createSCCPPass() { return new SCCPLegacyPass(); } |
1911 | | |
1912 | | static void findReturnsToZap(Function &F, |
1913 | | SmallVector<ReturnInst *, 8> &ReturnsToZap, |
1914 | 7.65k | SCCPSolver &Solver) { |
1915 | 7.65k | // We can only do this if we know that nothing else can call the function. |
1916 | 7.65k | if (!Solver.isArgumentTrackedFunction(&F)) |
1917 | 6.89k | return; |
1918 | 759 | |
1919 | 759 | // There is a non-removable musttail call site of this function. Zapping |
1920 | 759 | // returns is not allowed. |
1921 | 759 | if (Solver.isMustTailCallee(&F)) { |
1922 | 2 | LLVM_DEBUG(dbgs() << "Can't zap returns of the function : " << F.getName() |
1923 | 2 | << " due to present musttail call of it\n"); |
1924 | 2 | return; |
1925 | 2 | } |
1926 | 757 | |
1927 | 2.64k | for (BasicBlock &BB : F)757 { |
1928 | 2.64k | if (CallInst *CI = BB.getTerminatingMustTailCall()) { |
1929 | 0 | LLVM_DEBUG(dbgs() << "Can't zap return of the block due to present " |
1930 | 0 | << "musttail call : " << *CI << "\n"); |
1931 | 0 | (void)CI; |
1932 | 0 | return; |
1933 | 0 | } |
1934 | 2.64k | |
1935 | 2.64k | if (auto *RI = dyn_cast<ReturnInst>(BB.getTerminator())) |
1936 | 731 | if (!isa<UndefValue>(RI->getOperand(0))) |
1937 | 730 | ReturnsToZap.push_back(RI); |
1938 | 2.64k | } |
1939 | 757 | } |
1940 | | |
1941 | | // Update the condition for terminators that are branching on indeterminate |
1942 | | // values, forcing them to use a specific edge. |
1943 | 12.2k | static void forceIndeterminateEdge(Instruction* I, SCCPSolver &Solver) { |
1944 | 12.2k | BasicBlock *Dest = nullptr; |
1945 | 12.2k | Constant *C = nullptr; |
1946 | 12.2k | if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) { |
1947 | 37 | if (!isa<ConstantInt>(SI->getCondition())) { |
1948 | 2 | // Indeterminate switch; use first case value. |
1949 | 2 | Dest = SI->case_begin()->getCaseSuccessor(); |
1950 | 2 | C = SI->case_begin()->getCaseValue(); |
1951 | 2 | } |
1952 | 12.2k | } else if (BranchInst *BI = dyn_cast<BranchInst>(I)) { |
1953 | 12.2k | if (!isa<ConstantInt>(BI->getCondition())) { |
1954 | 1 | // Indeterminate branch; use false. |
1955 | 1 | Dest = BI->getSuccessor(1); |
1956 | 1 | C = ConstantInt::getFalse(BI->getContext()); |
1957 | 1 | } |
1958 | 12.2k | } else if (IndirectBrInst *0 IBR0 = dyn_cast<IndirectBrInst>(I)) { |
1959 | 0 | if (!isa<BlockAddress>(IBR->getAddress()->stripPointerCasts())) { |
1960 | 0 | // Indeterminate indirectbr; use successor 0. |
1961 | 0 | Dest = IBR->getSuccessor(0); |
1962 | 0 | C = BlockAddress::get(IBR->getSuccessor(0)); |
1963 | 0 | } |
1964 | 0 | } else { |
1965 | 0 | llvm_unreachable("Unexpected terminator instruction"); |
1966 | 0 | } |
1967 | 12.2k | if (C) { |
1968 | 3 | assert(Solver.isEdgeFeasible(I->getParent(), Dest) && |
1969 | 3 | "Didn't find feasible edge?"); |
1970 | 3 | (void)Dest; |
1971 | 3 | |
1972 | 3 | I->setOperand(0, C); |
1973 | 3 | } |
1974 | 12.2k | } |
1975 | | |
1976 | | bool llvm::runIPSCCP( |
1977 | | Module &M, const DataLayout &DL, const TargetLibraryInfo *TLI, |
1978 | 13.6k | function_ref<AnalysisResultsForFn(Function &)> getAnalysis) { |
1979 | 13.6k | SCCPSolver Solver(DL, TLI); |
1980 | 13.6k | |
1981 | 13.6k | // Loop over all functions, marking arguments to those with their addresses |
1982 | 13.6k | // taken or that are external as overdefined. |
1983 | 1.51M | for (Function &F : M) { |
1984 | 1.51M | if (F.isDeclaration()) |
1985 | 919k | continue; |
1986 | 590k | |
1987 | 590k | Solver.addAnalysis(F, getAnalysis(F)); |
1988 | 590k | |
1989 | 590k | // Determine if we can track the function's return values. If so, add the |
1990 | 590k | // function to the solver's set of return-tracked functions. |
1991 | 590k | if (canTrackReturnsInterprocedurally(&F)) |
1992 | 98.5k | Solver.AddTrackedFunction(&F); |
1993 | 590k | |
1994 | 590k | // Determine if we can track the function's arguments. If so, add the |
1995 | 590k | // function to the solver's set of argument-tracked functions. |
1996 | 590k | if (canTrackArgumentsInterprocedurally(&F)) { |
1997 | 25.3k | Solver.AddArgumentTrackedFunction(&F); |
1998 | 25.3k | continue; |
1999 | 25.3k | } |
2000 | 565k | |
2001 | 565k | // Assume the function is called. |
2002 | 565k | Solver.MarkBlockExecutable(&F.front()); |
2003 | 565k | |
2004 | 565k | // Assume nothing about the incoming arguments. |
2005 | 565k | for (Argument &AI : F.args()) |
2006 | 1.05M | Solver.markOverdefined(&AI); |
2007 | 565k | } |
2008 | 13.6k | |
2009 | 13.6k | // Determine if we can track any of the module's global variables. If so, add |
2010 | 13.6k | // the global variables we can track to the solver's set of tracked global |
2011 | 13.6k | // variables. |
2012 | 453k | for (GlobalVariable &G : M.globals()) { |
2013 | 453k | G.removeDeadConstantUsers(); |
2014 | 453k | if (canTrackGlobalVariableInterprocedurally(&G)) |
2015 | 4.79k | Solver.TrackValueOfGlobalVariable(&G); |
2016 | 453k | } |
2017 | 13.6k | |
2018 | 13.6k | // Solve for constants. |
2019 | 13.6k | bool ResolvedUndefs = true; |
2020 | 13.6k | Solver.Solve(); |
2021 | 27.3k | while (ResolvedUndefs) { |
2022 | 13.7k | LLVM_DEBUG(dbgs() << "RESOLVING UNDEFS\n"); |
2023 | 13.7k | ResolvedUndefs = false; |
2024 | 13.7k | for (Function &F : M) |
2025 | 1.52M | if (Solver.ResolvedUndefsIn(F)) { |
2026 | 158 | // We run Solve() after we resolved an undef in a function, because |
2027 | 158 | // we might deduce a fact that eliminates an undef in another function. |
2028 | 158 | Solver.Solve(); |
2029 | 158 | ResolvedUndefs = true; |
2030 | 158 | } |
2031 | 13.7k | } |
2032 | 13.6k | |
2033 | 13.6k | bool MadeChanges = false; |
2034 | 13.6k | |
2035 | 13.6k | // Iterate over all of the instructions in the module, replacing them with |
2036 | 13.6k | // constants if we have found them to be of constant values. |
2037 | 13.6k | |
2038 | 1.51M | for (Function &F : M) { |
2039 | 1.51M | if (F.isDeclaration()) |
2040 | 919k | continue; |
2041 | 590k | |
2042 | 590k | SmallVector<BasicBlock *, 512> BlocksToErase; |
2043 | 590k | |
2044 | 590k | if (Solver.isBlockExecutable(&F.front())) |
2045 | 1.69M | for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); 590k AI != E; |
2046 | 1.10M | ++AI) { |
2047 | 1.10M | if (!AI->use_empty() && tryToReplaceWithConstant(Solver, &*AI)1.05M ) { |
2048 | 2.38k | ++IPNumArgsElimed; |
2049 | 2.38k | continue; |
2050 | 2.38k | } |
2051 | 1.10M | } |
2052 | 590k | |
2053 | 3.01M | for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB2.42M ) { |
2054 | 2.42M | if (!Solver.isBlockExecutable(&*BB)) { |
2055 | 13.2k | LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << *BB); |
2056 | 13.2k | ++NumDeadBlocks; |
2057 | 13.2k | |
2058 | 13.2k | MadeChanges = true; |
2059 | 13.2k | |
2060 | 13.2k | if (&*BB != &F.front()) |
2061 | 13.2k | BlocksToErase.push_back(&*BB); |
2062 | 13.2k | continue; |
2063 | 13.2k | } |
2064 | 2.40M | |
2065 | 15.9M | for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); 2.40M BI != E; ) { |
2066 | 13.5M | Instruction *Inst = &*BI++; |
2067 | 13.5M | if (Inst->getType()->isVoidTy()) |
2068 | 3.98M | continue; |
2069 | 9.56M | if (tryToReplaceWithConstant(Solver, Inst)) { |
2070 | 34.2k | if (Inst->isSafeToRemove()) |
2071 | 14.7k | Inst->eraseFromParent(); |
2072 | 34.2k | // Hey, we just changed something! |
2073 | 34.2k | MadeChanges = true; |
2074 | 34.2k | ++IPNumInstRemoved; |
2075 | 34.2k | } |
2076 | 9.56M | } |
2077 | 2.40M | } |
2078 | 590k | |
2079 | 590k | DomTreeUpdater DTU = Solver.getDTU(F); |
2080 | 590k | // Change dead blocks to unreachable. We do it after replacing constants |
2081 | 590k | // in all executable blocks, because changeToUnreachable may remove PHI |
2082 | 590k | // nodes in executable blocks we found values for. The function's entry |
2083 | 590k | // block is not part of BlocksToErase, so we have to handle it separately. |
2084 | 590k | for (BasicBlock *BB : BlocksToErase) { |
2085 | 13.2k | NumInstRemoved += |
2086 | 13.2k | changeToUnreachable(BB->getFirstNonPHI(), /*UseLLVMTrap=*/false, |
2087 | 13.2k | /*PreserveLCSSA=*/false, &DTU); |
2088 | 13.2k | } |
2089 | 590k | if (!Solver.isBlockExecutable(&F.front())) |
2090 | 40 | NumInstRemoved += changeToUnreachable(F.front().getFirstNonPHI(), |
2091 | 40 | /*UseLLVMTrap=*/false, |
2092 | 40 | /*PreserveLCSSA=*/false, &DTU); |
2093 | 590k | |
2094 | 590k | // Now that all instructions in the function are constant folded, |
2095 | 590k | // use ConstantFoldTerminator to get rid of in-edges, record DT updates and |
2096 | 590k | // delete dead BBs. |
2097 | 590k | for (BasicBlock *DeadBB : BlocksToErase) { |
2098 | 13.2k | // If there are any PHI nodes in this successor, drop entries for BB now. |
2099 | 13.2k | for (Value::user_iterator UI = DeadBB->user_begin(), |
2100 | 13.2k | UE = DeadBB->user_end(); |
2101 | 25.5k | UI != UE;) { |
2102 | 12.2k | // Grab the user and then increment the iterator early, as the user |
2103 | 12.2k | // will be deleted. Step past all adjacent uses from the same user. |
2104 | 12.2k | auto *I = dyn_cast<Instruction>(*UI); |
2105 | 12.2k | do { ++UI; } while (UI != UE && *UI == I59 ); |
2106 | 12.2k | |
2107 | 12.2k | // Ignore blockaddress users; BasicBlock's dtor will handle them. |
2108 | 12.2k | if (!I) continue2 ; |
2109 | 12.2k | |
2110 | 12.2k | // If we have forced an edge for an indeterminate value, then force the |
2111 | 12.2k | // terminator to fold to that edge. |
2112 | 12.2k | forceIndeterminateEdge(I, Solver); |
2113 | 12.2k | BasicBlock *InstBB = I->getParent(); |
2114 | 12.2k | bool Folded = ConstantFoldTerminator(InstBB, |
2115 | 12.2k | /*DeleteDeadConditions=*/false, |
2116 | 12.2k | /*TLI=*/nullptr, &DTU); |
2117 | 12.2k | assert(Folded && |
2118 | 12.2k | "Expect TermInst on constantint or blockaddress to be folded"); |
2119 | 12.2k | (void) Folded; |
2120 | 12.2k | // If we folded the terminator to an unconditional branch to another |
2121 | 12.2k | // dead block, replace it with Unreachable, to avoid trying to fold that |
2122 | 12.2k | // branch again. |
2123 | 12.2k | BranchInst *BI = cast<BranchInst>(InstBB->getTerminator()); |
2124 | 12.2k | if (BI && BI->isUnconditional() && |
2125 | 12.2k | !Solver.isBlockExecutable(BI->getSuccessor(0))) { |
2126 | 4 | InstBB->getTerminator()->eraseFromParent(); |
2127 | 4 | new UnreachableInst(InstBB->getContext(), InstBB); |
2128 | 4 | } |
2129 | 12.2k | } |
2130 | 13.2k | // Mark dead BB for deletion. |
2131 | 13.2k | DTU.deleteBB(DeadBB); |
2132 | 13.2k | } |
2133 | 590k | |
2134 | 2.42M | for (BasicBlock &BB : F) { |
2135 | 15.9M | for (BasicBlock::iterator BI = BB.begin(), E = BB.end(); BI != E;) { |
2136 | 13.5M | Instruction *Inst = &*BI++; |
2137 | 13.5M | if (Solver.getPredicateInfoFor(Inst)) { |
2138 | 512k | if (auto *II = dyn_cast<IntrinsicInst>(Inst)) { |
2139 | 512k | if (II->getIntrinsicID() == Intrinsic::ssa_copy) { |
2140 | 512k | Value *Op = II->getOperand(0); |
2141 | 512k | Inst->replaceAllUsesWith(Op); |
2142 | 512k | Inst->eraseFromParent(); |
2143 | 512k | } |
2144 | 512k | } |
2145 | 512k | } |
2146 | 13.5M | } |
2147 | 2.42M | } |
2148 | 590k | } |
2149 | 13.6k | |
2150 | 13.6k | // If we inferred constant or undef return values for a function, we replaced |
2151 | 13.6k | // all call uses with the inferred value. This means we don't need to bother |
2152 | 13.6k | // actually returning anything from the function. Replace all return |
2153 | 13.6k | // instructions with return undef. |
2154 | 13.6k | // |
2155 | 13.6k | // Do this in two stages: first identify the functions we should process, then |
2156 | 13.6k | // actually zap their returns. This is important because we can only do this |
2157 | 13.6k | // if the address of the function isn't taken. In cases where a return is the |
2158 | 13.6k | // last use of a function, the order of processing functions would affect |
2159 | 13.6k | // whether other functions are optimizable. |
2160 | 13.6k | SmallVector<ReturnInst*, 8> ReturnsToZap; |
2161 | 13.6k | |
2162 | 13.6k | const MapVector<Function*, LatticeVal> &RV = Solver.getTrackedRetVals(); |
2163 | 97.7k | for (const auto &I : RV) { |
2164 | 97.7k | Function *F = I.first; |
2165 | 97.7k | if (I.second.isOverdefined() || F->getReturnType()->isVoidTy()44.4k ) |
2166 | 90.0k | continue; |
2167 | 7.62k | findReturnsToZap(*F, ReturnsToZap, Solver); |
2168 | 7.62k | } |
2169 | 13.6k | |
2170 | 13.6k | for (const auto &F : Solver.getMRVFunctionsTracked()) { |
2171 | 866 | assert(F->getReturnType()->isStructTy() && |
2172 | 866 | "The return type should be a struct"); |
2173 | 866 | StructType *STy = cast<StructType>(F->getReturnType()); |
2174 | 866 | if (Solver.isStructLatticeConstant(F, STy)) |
2175 | 26 | findReturnsToZap(*F, ReturnsToZap, Solver); |
2176 | 866 | } |
2177 | 13.6k | |
2178 | 13.6k | // Zap all returns which we've identified as zap to change. |
2179 | 14.3k | for (unsigned i = 0, e = ReturnsToZap.size(); i != e; ++i730 ) { |
2180 | 730 | Function *F = ReturnsToZap[i]->getParent()->getParent(); |
2181 | 730 | ReturnsToZap[i]->setOperand(0, UndefValue::get(F->getReturnType())); |
2182 | 730 | } |
2183 | 13.6k | |
2184 | 13.6k | // If we inferred constant or undef values for globals variables, we can |
2185 | 13.6k | // delete the global and any stores that remain to it. |
2186 | 13.6k | const DenseMap<GlobalVariable*, LatticeVal> &TG = Solver.getTrackedGlobals(); |
2187 | 13.6k | for (DenseMap<GlobalVariable*, LatticeVal>::const_iterator I = TG.begin(), |
2188 | 13.9k | E = TG.end(); I != E; ++I351 ) { |
2189 | 351 | GlobalVariable *GV = I->first; |
2190 | 351 | assert(!I->second.isOverdefined() && |
2191 | 351 | "Overdefined values should have been taken out of the map!"); |
2192 | 351 | LLVM_DEBUG(dbgs() << "Found that GV '" << GV->getName() |
2193 | 351 | << "' is constant!\n"); |
2194 | 405 | while (!GV->use_empty()) { |
2195 | 54 | StoreInst *SI = cast<StoreInst>(GV->user_back()); |
2196 | 54 | SI->eraseFromParent(); |
2197 | 54 | } |
2198 | 351 | M.getGlobalList().erase(GV); |
2199 | 351 | ++IPNumGlobalConst; |
2200 | 351 | } |
2201 | 13.6k | |
2202 | 13.6k | return MadeChanges; |
2203 | 13.6k | } |