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