File: | build/source/llvm/include/llvm/Analysis/ValueLattice.h |
Warning: | line 181, column 16 Assigned value is garbage or undefined |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- LazyValueInfo.cpp - Value constraint analysis ------------*- 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 file defines the interface for lazy computation of value constraint | |||
10 | // information. | |||
11 | // | |||
12 | //===----------------------------------------------------------------------===// | |||
13 | ||||
14 | #include "llvm/Analysis/LazyValueInfo.h" | |||
15 | #include "llvm/ADT/DenseSet.h" | |||
16 | #include "llvm/ADT/Optional.h" | |||
17 | #include "llvm/ADT/STLExtras.h" | |||
18 | #include "llvm/Analysis/AssumptionCache.h" | |||
19 | #include "llvm/Analysis/ConstantFolding.h" | |||
20 | #include "llvm/Analysis/InstructionSimplify.h" | |||
21 | #include "llvm/Analysis/TargetLibraryInfo.h" | |||
22 | #include "llvm/Analysis/ValueLattice.h" | |||
23 | #include "llvm/Analysis/ValueTracking.h" | |||
24 | #include "llvm/IR/AssemblyAnnotationWriter.h" | |||
25 | #include "llvm/IR/CFG.h" | |||
26 | #include "llvm/IR/ConstantRange.h" | |||
27 | #include "llvm/IR/Constants.h" | |||
28 | #include "llvm/IR/DataLayout.h" | |||
29 | #include "llvm/IR/Dominators.h" | |||
30 | #include "llvm/IR/Instructions.h" | |||
31 | #include "llvm/IR/IntrinsicInst.h" | |||
32 | #include "llvm/IR/Intrinsics.h" | |||
33 | #include "llvm/IR/LLVMContext.h" | |||
34 | #include "llvm/IR/PatternMatch.h" | |||
35 | #include "llvm/IR/ValueHandle.h" | |||
36 | #include "llvm/InitializePasses.h" | |||
37 | #include "llvm/Support/Debug.h" | |||
38 | #include "llvm/Support/FormattedStream.h" | |||
39 | #include "llvm/Support/KnownBits.h" | |||
40 | #include "llvm/Support/raw_ostream.h" | |||
41 | #include <optional> | |||
42 | using namespace llvm; | |||
43 | using namespace PatternMatch; | |||
44 | ||||
45 | #define DEBUG_TYPE"lazy-value-info" "lazy-value-info" | |||
46 | ||||
47 | // This is the number of worklist items we will process to try to discover an | |||
48 | // answer for a given value. | |||
49 | static const unsigned MaxProcessedPerValue = 500; | |||
50 | ||||
51 | char LazyValueInfoWrapperPass::ID = 0; | |||
52 | LazyValueInfoWrapperPass::LazyValueInfoWrapperPass() : FunctionPass(ID) { | |||
53 | initializeLazyValueInfoWrapperPassPass(*PassRegistry::getPassRegistry()); | |||
54 | } | |||
55 | INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info",static void *initializeLazyValueInfoWrapperPassPassOnce(PassRegistry &Registry) { | |||
56 | "Lazy Value Information Analysis", false, true)static void *initializeLazyValueInfoWrapperPassPassOnce(PassRegistry &Registry) { | |||
57 | INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry); | |||
58 | INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)initializeTargetLibraryInfoWrapperPassPass(Registry); | |||
59 | INITIALIZE_PASS_END(LazyValueInfoWrapperPass, "lazy-value-info",PassInfo *PI = new PassInfo( "Lazy Value Information Analysis" , "lazy-value-info", &LazyValueInfoWrapperPass::ID, PassInfo ::NormalCtor_t(callDefaultCtor<LazyValueInfoWrapperPass> ), false, true); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeLazyValueInfoWrapperPassPassFlag ; void llvm::initializeLazyValueInfoWrapperPassPass(PassRegistry &Registry) { llvm::call_once(InitializeLazyValueInfoWrapperPassPassFlag , initializeLazyValueInfoWrapperPassPassOnce, std::ref(Registry )); } | |||
60 | "Lazy Value Information Analysis", false, true)PassInfo *PI = new PassInfo( "Lazy Value Information Analysis" , "lazy-value-info", &LazyValueInfoWrapperPass::ID, PassInfo ::NormalCtor_t(callDefaultCtor<LazyValueInfoWrapperPass> ), false, true); Registry.registerPass(*PI, true); return PI; } static llvm::once_flag InitializeLazyValueInfoWrapperPassPassFlag ; void llvm::initializeLazyValueInfoWrapperPassPass(PassRegistry &Registry) { llvm::call_once(InitializeLazyValueInfoWrapperPassPassFlag , initializeLazyValueInfoWrapperPassPassOnce, std::ref(Registry )); } | |||
61 | ||||
62 | namespace llvm { | |||
63 | FunctionPass *createLazyValueInfoPass() { return new LazyValueInfoWrapperPass(); } | |||
64 | } | |||
65 | ||||
66 | AnalysisKey LazyValueAnalysis::Key; | |||
67 | ||||
68 | /// Returns true if this lattice value represents at most one possible value. | |||
69 | /// This is as precise as any lattice value can get while still representing | |||
70 | /// reachable code. | |||
71 | static bool hasSingleValue(const ValueLatticeElement &Val) { | |||
72 | if (Val.isConstantRange() && | |||
73 | Val.getConstantRange().isSingleElement()) | |||
74 | // Integer constants are single element ranges | |||
75 | return true; | |||
76 | if (Val.isConstant()) | |||
77 | // Non integer constants | |||
78 | return true; | |||
79 | return false; | |||
80 | } | |||
81 | ||||
82 | /// Combine two sets of facts about the same value into a single set of | |||
83 | /// facts. Note that this method is not suitable for merging facts along | |||
84 | /// different paths in a CFG; that's what the mergeIn function is for. This | |||
85 | /// is for merging facts gathered about the same value at the same location | |||
86 | /// through two independent means. | |||
87 | /// Notes: | |||
88 | /// * This method does not promise to return the most precise possible lattice | |||
89 | /// value implied by A and B. It is allowed to return any lattice element | |||
90 | /// which is at least as strong as *either* A or B (unless our facts | |||
91 | /// conflict, see below). | |||
92 | /// * Due to unreachable code, the intersection of two lattice values could be | |||
93 | /// contradictory. If this happens, we return some valid lattice value so as | |||
94 | /// not confuse the rest of LVI. Ideally, we'd always return Undefined, but | |||
95 | /// we do not make this guarantee. TODO: This would be a useful enhancement. | |||
96 | static ValueLatticeElement intersect(const ValueLatticeElement &A, | |||
97 | const ValueLatticeElement &B) { | |||
98 | // Undefined is the strongest state. It means the value is known to be along | |||
99 | // an unreachable path. | |||
100 | if (A.isUnknown()) | |||
101 | return A; | |||
102 | if (B.isUnknown()) | |||
103 | return B; | |||
104 | ||||
105 | // If we gave up for one, but got a useable fact from the other, use it. | |||
106 | if (A.isOverdefined()) | |||
107 | return B; | |||
108 | if (B.isOverdefined()) | |||
109 | return A; | |||
110 | ||||
111 | // Can't get any more precise than constants. | |||
112 | if (hasSingleValue(A)) | |||
113 | return A; | |||
114 | if (hasSingleValue(B)) | |||
115 | return B; | |||
116 | ||||
117 | // Could be either constant range or not constant here. | |||
118 | if (!A.isConstantRange() || !B.isConstantRange()) { | |||
119 | // TODO: Arbitrary choice, could be improved | |||
120 | return A; | |||
121 | } | |||
122 | ||||
123 | // Intersect two constant ranges | |||
124 | ConstantRange Range = | |||
125 | A.getConstantRange().intersectWith(B.getConstantRange()); | |||
126 | // Note: An empty range is implicitly converted to unknown or undef depending | |||
127 | // on MayIncludeUndef internally. | |||
128 | return ValueLatticeElement::getRange( | |||
129 | std::move(Range), /*MayIncludeUndef=*/A.isConstantRangeIncludingUndef() || | |||
130 | B.isConstantRangeIncludingUndef()); | |||
131 | } | |||
132 | ||||
133 | //===----------------------------------------------------------------------===// | |||
134 | // LazyValueInfoCache Decl | |||
135 | //===----------------------------------------------------------------------===// | |||
136 | ||||
137 | namespace { | |||
138 | /// A callback value handle updates the cache when values are erased. | |||
139 | class LazyValueInfoCache; | |||
140 | struct LVIValueHandle final : public CallbackVH { | |||
141 | LazyValueInfoCache *Parent; | |||
142 | ||||
143 | LVIValueHandle(Value *V, LazyValueInfoCache *P = nullptr) | |||
144 | : CallbackVH(V), Parent(P) { } | |||
145 | ||||
146 | void deleted() override; | |||
147 | void allUsesReplacedWith(Value *V) override { | |||
148 | deleted(); | |||
149 | } | |||
150 | }; | |||
151 | } // end anonymous namespace | |||
152 | ||||
153 | namespace { | |||
154 | using NonNullPointerSet = SmallDenseSet<AssertingVH<Value>, 2>; | |||
155 | ||||
156 | /// This is the cache kept by LazyValueInfo which | |||
157 | /// maintains information about queries across the clients' queries. | |||
158 | class LazyValueInfoCache { | |||
159 | /// This is all of the cached information for one basic block. It contains | |||
160 | /// the per-value lattice elements, as well as a separate set for | |||
161 | /// overdefined values to reduce memory usage. Additionally pointers | |||
162 | /// dereferenced in the block are cached for nullability queries. | |||
163 | struct BlockCacheEntry { | |||
164 | SmallDenseMap<AssertingVH<Value>, ValueLatticeElement, 4> LatticeElements; | |||
165 | SmallDenseSet<AssertingVH<Value>, 4> OverDefined; | |||
166 | // None indicates that the nonnull pointers for this basic block | |||
167 | // block have not been computed yet. | |||
168 | std::optional<NonNullPointerSet> NonNullPointers; | |||
169 | }; | |||
170 | ||||
171 | /// Cached information per basic block. | |||
172 | DenseMap<PoisoningVH<BasicBlock>, std::unique_ptr<BlockCacheEntry>> | |||
173 | BlockCache; | |||
174 | /// Set of value handles used to erase values from the cache on deletion. | |||
175 | DenseSet<LVIValueHandle, DenseMapInfo<Value *>> ValueHandles; | |||
176 | ||||
177 | const BlockCacheEntry *getBlockEntry(BasicBlock *BB) const { | |||
178 | auto It = BlockCache.find_as(BB); | |||
179 | if (It == BlockCache.end()) | |||
180 | return nullptr; | |||
181 | return It->second.get(); | |||
182 | } | |||
183 | ||||
184 | BlockCacheEntry *getOrCreateBlockEntry(BasicBlock *BB) { | |||
185 | auto It = BlockCache.find_as(BB); | |||
186 | if (It == BlockCache.end()) | |||
187 | It = BlockCache.insert({ BB, std::make_unique<BlockCacheEntry>() }) | |||
188 | .first; | |||
189 | ||||
190 | return It->second.get(); | |||
191 | } | |||
192 | ||||
193 | void addValueHandle(Value *Val) { | |||
194 | auto HandleIt = ValueHandles.find_as(Val); | |||
195 | if (HandleIt == ValueHandles.end()) | |||
196 | ValueHandles.insert({ Val, this }); | |||
197 | } | |||
198 | ||||
199 | public: | |||
200 | void insertResult(Value *Val, BasicBlock *BB, | |||
201 | const ValueLatticeElement &Result) { | |||
202 | BlockCacheEntry *Entry = getOrCreateBlockEntry(BB); | |||
203 | ||||
204 | // Insert over-defined values into their own cache to reduce memory | |||
205 | // overhead. | |||
206 | if (Result.isOverdefined()) | |||
207 | Entry->OverDefined.insert(Val); | |||
208 | else | |||
209 | Entry->LatticeElements.insert({ Val, Result }); | |||
210 | ||||
211 | addValueHandle(Val); | |||
212 | } | |||
213 | ||||
214 | Optional<ValueLatticeElement> getCachedValueInfo(Value *V, | |||
215 | BasicBlock *BB) const { | |||
216 | const BlockCacheEntry *Entry = getBlockEntry(BB); | |||
217 | if (!Entry) | |||
218 | return std::nullopt; | |||
219 | ||||
220 | if (Entry->OverDefined.count(V)) | |||
221 | return ValueLatticeElement::getOverdefined(); | |||
222 | ||||
223 | auto LatticeIt = Entry->LatticeElements.find_as(V); | |||
224 | if (LatticeIt == Entry->LatticeElements.end()) | |||
225 | return std::nullopt; | |||
226 | ||||
227 | return LatticeIt->second; | |||
228 | } | |||
229 | ||||
230 | bool isNonNullAtEndOfBlock( | |||
231 | Value *V, BasicBlock *BB, | |||
232 | function_ref<NonNullPointerSet(BasicBlock *)> InitFn) { | |||
233 | BlockCacheEntry *Entry = getOrCreateBlockEntry(BB); | |||
234 | if (!Entry->NonNullPointers) { | |||
235 | Entry->NonNullPointers = InitFn(BB); | |||
236 | for (Value *V : *Entry->NonNullPointers) | |||
237 | addValueHandle(V); | |||
238 | } | |||
239 | ||||
240 | return Entry->NonNullPointers->count(V); | |||
241 | } | |||
242 | ||||
243 | /// clear - Empty the cache. | |||
244 | void clear() { | |||
245 | BlockCache.clear(); | |||
246 | ValueHandles.clear(); | |||
247 | } | |||
248 | ||||
249 | /// Inform the cache that a given value has been deleted. | |||
250 | void eraseValue(Value *V); | |||
251 | ||||
252 | /// This is part of the update interface to inform the cache | |||
253 | /// that a block has been deleted. | |||
254 | void eraseBlock(BasicBlock *BB); | |||
255 | ||||
256 | /// Updates the cache to remove any influence an overdefined value in | |||
257 | /// OldSucc might have (unless also overdefined in NewSucc). This just | |||
258 | /// flushes elements from the cache and does not add any. | |||
259 | void threadEdgeImpl(BasicBlock *OldSucc,BasicBlock *NewSucc); | |||
260 | }; | |||
261 | } | |||
262 | ||||
263 | void LazyValueInfoCache::eraseValue(Value *V) { | |||
264 | for (auto &Pair : BlockCache) { | |||
265 | Pair.second->LatticeElements.erase(V); | |||
266 | Pair.second->OverDefined.erase(V); | |||
267 | if (Pair.second->NonNullPointers) | |||
268 | Pair.second->NonNullPointers->erase(V); | |||
269 | } | |||
270 | ||||
271 | auto HandleIt = ValueHandles.find_as(V); | |||
272 | if (HandleIt != ValueHandles.end()) | |||
273 | ValueHandles.erase(HandleIt); | |||
274 | } | |||
275 | ||||
276 | void LVIValueHandle::deleted() { | |||
277 | // This erasure deallocates *this, so it MUST happen after we're done | |||
278 | // using any and all members of *this. | |||
279 | Parent->eraseValue(*this); | |||
280 | } | |||
281 | ||||
282 | void LazyValueInfoCache::eraseBlock(BasicBlock *BB) { | |||
283 | BlockCache.erase(BB); | |||
284 | } | |||
285 | ||||
286 | void LazyValueInfoCache::threadEdgeImpl(BasicBlock *OldSucc, | |||
287 | BasicBlock *NewSucc) { | |||
288 | // When an edge in the graph has been threaded, values that we could not | |||
289 | // determine a value for before (i.e. were marked overdefined) may be | |||
290 | // possible to solve now. We do NOT try to proactively update these values. | |||
291 | // Instead, we clear their entries from the cache, and allow lazy updating to | |||
292 | // recompute them when needed. | |||
293 | ||||
294 | // The updating process is fairly simple: we need to drop cached info | |||
295 | // for all values that were marked overdefined in OldSucc, and for those same | |||
296 | // values in any successor of OldSucc (except NewSucc) in which they were | |||
297 | // also marked overdefined. | |||
298 | std::vector<BasicBlock*> worklist; | |||
299 | worklist.push_back(OldSucc); | |||
300 | ||||
301 | const BlockCacheEntry *Entry = getBlockEntry(OldSucc); | |||
302 | if (!Entry || Entry->OverDefined.empty()) | |||
303 | return; // Nothing to process here. | |||
304 | SmallVector<Value *, 4> ValsToClear(Entry->OverDefined.begin(), | |||
305 | Entry->OverDefined.end()); | |||
306 | ||||
307 | // Use a worklist to perform a depth-first search of OldSucc's successors. | |||
308 | // NOTE: We do not need a visited list since any blocks we have already | |||
309 | // visited will have had their overdefined markers cleared already, and we | |||
310 | // thus won't loop to their successors. | |||
311 | while (!worklist.empty()) { | |||
312 | BasicBlock *ToUpdate = worklist.back(); | |||
313 | worklist.pop_back(); | |||
314 | ||||
315 | // Skip blocks only accessible through NewSucc. | |||
316 | if (ToUpdate == NewSucc) continue; | |||
317 | ||||
318 | // If a value was marked overdefined in OldSucc, and is here too... | |||
319 | auto OI = BlockCache.find_as(ToUpdate); | |||
320 | if (OI == BlockCache.end() || OI->second->OverDefined.empty()) | |||
321 | continue; | |||
322 | auto &ValueSet = OI->second->OverDefined; | |||
323 | ||||
324 | bool changed = false; | |||
325 | for (Value *V : ValsToClear) { | |||
326 | if (!ValueSet.erase(V)) | |||
327 | continue; | |||
328 | ||||
329 | // If we removed anything, then we potentially need to update | |||
330 | // blocks successors too. | |||
331 | changed = true; | |||
332 | } | |||
333 | ||||
334 | if (!changed) continue; | |||
335 | ||||
336 | llvm::append_range(worklist, successors(ToUpdate)); | |||
337 | } | |||
338 | } | |||
339 | ||||
340 | ||||
341 | namespace { | |||
342 | /// An assembly annotator class to print LazyValueCache information in | |||
343 | /// comments. | |||
344 | class LazyValueInfoImpl; | |||
345 | class LazyValueInfoAnnotatedWriter : public AssemblyAnnotationWriter { | |||
346 | LazyValueInfoImpl *LVIImpl; | |||
347 | // While analyzing which blocks we can solve values for, we need the dominator | |||
348 | // information. | |||
349 | DominatorTree &DT; | |||
350 | ||||
351 | public: | |||
352 | LazyValueInfoAnnotatedWriter(LazyValueInfoImpl *L, DominatorTree &DTree) | |||
353 | : LVIImpl(L), DT(DTree) {} | |||
354 | ||||
355 | void emitBasicBlockStartAnnot(const BasicBlock *BB, | |||
356 | formatted_raw_ostream &OS) override; | |||
357 | ||||
358 | void emitInstructionAnnot(const Instruction *I, | |||
359 | formatted_raw_ostream &OS) override; | |||
360 | }; | |||
361 | } | |||
362 | namespace { | |||
363 | // The actual implementation of the lazy analysis and update. Note that the | |||
364 | // inheritance from LazyValueInfoCache is intended to be temporary while | |||
365 | // splitting the code and then transitioning to a has-a relationship. | |||
366 | class LazyValueInfoImpl { | |||
367 | ||||
368 | /// Cached results from previous queries | |||
369 | LazyValueInfoCache TheCache; | |||
370 | ||||
371 | /// This stack holds the state of the value solver during a query. | |||
372 | /// It basically emulates the callstack of the naive | |||
373 | /// recursive value lookup process. | |||
374 | SmallVector<std::pair<BasicBlock*, Value*>, 8> BlockValueStack; | |||
375 | ||||
376 | /// Keeps track of which block-value pairs are in BlockValueStack. | |||
377 | DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet; | |||
378 | ||||
379 | /// Push BV onto BlockValueStack unless it's already in there. | |||
380 | /// Returns true on success. | |||
381 | bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) { | |||
382 | if (!BlockValueSet.insert(BV).second) | |||
383 | return false; // It's already in the stack. | |||
384 | ||||
385 | LLVM_DEBUG(dbgs() << "PUSH: " << *BV.second << " in "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << "PUSH: " << *BV. second << " in " << BV.first->getName() << "\n"; } } while (false) | |||
386 | << BV.first->getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << "PUSH: " << *BV. second << " in " << BV.first->getName() << "\n"; } } while (false); | |||
387 | BlockValueStack.push_back(BV); | |||
388 | return true; | |||
389 | } | |||
390 | ||||
391 | AssumptionCache *AC; ///< A pointer to the cache of @llvm.assume calls. | |||
392 | const DataLayout &DL; ///< A mandatory DataLayout | |||
393 | ||||
394 | /// Declaration of the llvm.experimental.guard() intrinsic, | |||
395 | /// if it exists in the module. | |||
396 | Function *GuardDecl; | |||
397 | ||||
398 | Optional<ValueLatticeElement> getBlockValue(Value *Val, BasicBlock *BB, | |||
399 | Instruction *CxtI); | |||
400 | Optional<ValueLatticeElement> getEdgeValue(Value *V, BasicBlock *F, | |||
401 | BasicBlock *T, Instruction *CxtI = nullptr); | |||
402 | ||||
403 | // These methods process one work item and may add more. A false value | |||
404 | // returned means that the work item was not completely processed and must | |||
405 | // be revisited after going through the new items. | |||
406 | bool solveBlockValue(Value *Val, BasicBlock *BB); | |||
407 | Optional<ValueLatticeElement> solveBlockValueImpl(Value *Val, BasicBlock *BB); | |||
408 | Optional<ValueLatticeElement> solveBlockValueNonLocal(Value *Val, | |||
409 | BasicBlock *BB); | |||
410 | Optional<ValueLatticeElement> solveBlockValuePHINode(PHINode *PN, | |||
411 | BasicBlock *BB); | |||
412 | Optional<ValueLatticeElement> solveBlockValueSelect(SelectInst *S, | |||
413 | BasicBlock *BB); | |||
414 | Optional<ConstantRange> getRangeFor(Value *V, Instruction *CxtI, | |||
415 | BasicBlock *BB); | |||
416 | Optional<ValueLatticeElement> solveBlockValueBinaryOpImpl( | |||
417 | Instruction *I, BasicBlock *BB, | |||
418 | std::function<ConstantRange(const ConstantRange &, | |||
419 | const ConstantRange &)> OpFn); | |||
420 | Optional<ValueLatticeElement> solveBlockValueBinaryOp(BinaryOperator *BBI, | |||
421 | BasicBlock *BB); | |||
422 | Optional<ValueLatticeElement> solveBlockValueCast(CastInst *CI, | |||
423 | BasicBlock *BB); | |||
424 | Optional<ValueLatticeElement> solveBlockValueOverflowIntrinsic( | |||
425 | WithOverflowInst *WO, BasicBlock *BB); | |||
426 | Optional<ValueLatticeElement> solveBlockValueIntrinsic(IntrinsicInst *II, | |||
427 | BasicBlock *BB); | |||
428 | Optional<ValueLatticeElement> solveBlockValueExtractValue( | |||
429 | ExtractValueInst *EVI, BasicBlock *BB); | |||
430 | bool isNonNullAtEndOfBlock(Value *Val, BasicBlock *BB); | |||
431 | void intersectAssumeOrGuardBlockValueConstantRange(Value *Val, | |||
432 | ValueLatticeElement &BBLV, | |||
433 | Instruction *BBI); | |||
434 | ||||
435 | void solve(); | |||
436 | ||||
437 | public: | |||
438 | /// This is the query interface to determine the lattice value for the | |||
439 | /// specified Value* at the context instruction (if specified) or at the | |||
440 | /// start of the block. | |||
441 | ValueLatticeElement getValueInBlock(Value *V, BasicBlock *BB, | |||
442 | Instruction *CxtI = nullptr); | |||
443 | ||||
444 | /// This is the query interface to determine the lattice value for the | |||
445 | /// specified Value* at the specified instruction using only information | |||
446 | /// from assumes/guards and range metadata. Unlike getValueInBlock(), no | |||
447 | /// recursive query is performed. | |||
448 | ValueLatticeElement getValueAt(Value *V, Instruction *CxtI); | |||
449 | ||||
450 | /// This is the query interface to determine the lattice | |||
451 | /// value for the specified Value* that is true on the specified edge. | |||
452 | ValueLatticeElement getValueOnEdge(Value *V, BasicBlock *FromBB, | |||
453 | BasicBlock *ToBB, | |||
454 | Instruction *CxtI = nullptr); | |||
455 | ||||
456 | /// Complete flush all previously computed values | |||
457 | void clear() { | |||
458 | TheCache.clear(); | |||
459 | } | |||
460 | ||||
461 | /// Printing the LazyValueInfo Analysis. | |||
462 | void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) { | |||
463 | LazyValueInfoAnnotatedWriter Writer(this, DTree); | |||
464 | F.print(OS, &Writer); | |||
465 | } | |||
466 | ||||
467 | /// This is part of the update interface to inform the cache | |||
468 | /// that a block has been deleted. | |||
469 | void eraseBlock(BasicBlock *BB) { | |||
470 | TheCache.eraseBlock(BB); | |||
471 | } | |||
472 | ||||
473 | /// This is the update interface to inform the cache that an edge from | |||
474 | /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc. | |||
475 | void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc); | |||
476 | ||||
477 | LazyValueInfoImpl(AssumptionCache *AC, const DataLayout &DL, | |||
478 | Function *GuardDecl) | |||
479 | : AC(AC), DL(DL), GuardDecl(GuardDecl) {} | |||
480 | }; | |||
481 | } // end anonymous namespace | |||
482 | ||||
483 | ||||
484 | void LazyValueInfoImpl::solve() { | |||
485 | SmallVector<std::pair<BasicBlock *, Value *>, 8> StartingStack( | |||
486 | BlockValueStack.begin(), BlockValueStack.end()); | |||
487 | ||||
488 | unsigned processedCount = 0; | |||
489 | while (!BlockValueStack.empty()) { | |||
490 | processedCount++; | |||
491 | // Abort if we have to process too many values to get a result for this one. | |||
492 | // Because of the design of the overdefined cache currently being per-block | |||
493 | // to avoid naming-related issues (IE it wants to try to give different | |||
494 | // results for the same name in different blocks), overdefined results don't | |||
495 | // get cached globally, which in turn means we will often try to rediscover | |||
496 | // the same overdefined result again and again. Once something like | |||
497 | // PredicateInfo is used in LVI or CVP, we should be able to make the | |||
498 | // overdefined cache global, and remove this throttle. | |||
499 | if (processedCount > MaxProcessedPerValue) { | |||
500 | LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << "Giving up on stack because we are getting too deep\n" ; } } while (false) | |||
501 | dbgs() << "Giving up on stack because we are getting too deep\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << "Giving up on stack because we are getting too deep\n" ; } } while (false); | |||
502 | // Fill in the original values | |||
503 | while (!StartingStack.empty()) { | |||
504 | std::pair<BasicBlock *, Value *> &e = StartingStack.back(); | |||
505 | TheCache.insertResult(e.second, e.first, | |||
506 | ValueLatticeElement::getOverdefined()); | |||
507 | StartingStack.pop_back(); | |||
508 | } | |||
509 | BlockValueSet.clear(); | |||
510 | BlockValueStack.clear(); | |||
511 | return; | |||
512 | } | |||
513 | std::pair<BasicBlock *, Value *> e = BlockValueStack.back(); | |||
514 | assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!")(static_cast <bool> (BlockValueSet.count(e) && "Stack value should be in BlockValueSet!" ) ? void (0) : __assert_fail ("BlockValueSet.count(e) && \"Stack value should be in BlockValueSet!\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 514, __extension__ __PRETTY_FUNCTION__ )); | |||
515 | ||||
516 | if (solveBlockValue(e.second, e.first)) { | |||
517 | // The work item was completely processed. | |||
518 | assert(BlockValueStack.back() == e && "Nothing should have been pushed!")(static_cast <bool> (BlockValueStack.back() == e && "Nothing should have been pushed!") ? void (0) : __assert_fail ("BlockValueStack.back() == e && \"Nothing should have been pushed!\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 518, __extension__ __PRETTY_FUNCTION__ )); | |||
519 | #ifndef NDEBUG | |||
520 | Optional<ValueLatticeElement> BBLV = | |||
521 | TheCache.getCachedValueInfo(e.second, e.first); | |||
522 | assert(BBLV && "Result should be in cache!")(static_cast <bool> (BBLV && "Result should be in cache!" ) ? void (0) : __assert_fail ("BBLV && \"Result should be in cache!\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 522, __extension__ __PRETTY_FUNCTION__ )); | |||
523 | LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << "POP " << *e.second << " in " << e.first->getName() << " = " << *BBLV << "\n"; } } while (false) | |||
524 | dbgs() << "POP " << *e.second << " in " << e.first->getName() << " = "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << "POP " << *e.second << " in " << e.first->getName() << " = " << *BBLV << "\n"; } } while (false) | |||
525 | << *BBLV << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << "POP " << *e.second << " in " << e.first->getName() << " = " << *BBLV << "\n"; } } while (false); | |||
526 | #endif | |||
527 | ||||
528 | BlockValueStack.pop_back(); | |||
529 | BlockValueSet.erase(e); | |||
530 | } else { | |||
531 | // More work needs to be done before revisiting. | |||
532 | assert(BlockValueStack.back() != e && "Stack should have been pushed!")(static_cast <bool> (BlockValueStack.back() != e && "Stack should have been pushed!") ? void (0) : __assert_fail ("BlockValueStack.back() != e && \"Stack should have been pushed!\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 532, __extension__ __PRETTY_FUNCTION__ )); | |||
533 | } | |||
534 | } | |||
535 | } | |||
536 | ||||
537 | Optional<ValueLatticeElement> LazyValueInfoImpl::getBlockValue( | |||
538 | Value *Val, BasicBlock *BB, Instruction *CxtI) { | |||
539 | // If already a constant, there is nothing to compute. | |||
540 | if (Constant *VC = dyn_cast<Constant>(Val)) | |||
541 | return ValueLatticeElement::get(VC); | |||
542 | ||||
543 | if (Optional<ValueLatticeElement> OptLatticeVal = | |||
544 | TheCache.getCachedValueInfo(Val, BB)) { | |||
545 | intersectAssumeOrGuardBlockValueConstantRange(Val, *OptLatticeVal, CxtI); | |||
546 | return OptLatticeVal; | |||
547 | } | |||
548 | ||||
549 | // We have hit a cycle, assume overdefined. | |||
550 | if (!pushBlockValue({ BB, Val })) | |||
551 | return ValueLatticeElement::getOverdefined(); | |||
552 | ||||
553 | // Yet to be resolved. | |||
554 | return std::nullopt; | |||
555 | } | |||
556 | ||||
557 | static ValueLatticeElement getFromRangeMetadata(Instruction *BBI) { | |||
558 | switch (BBI->getOpcode()) { | |||
559 | default: break; | |||
560 | case Instruction::Load: | |||
561 | case Instruction::Call: | |||
562 | case Instruction::Invoke: | |||
563 | if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range)) | |||
564 | if (isa<IntegerType>(BBI->getType())) { | |||
565 | return ValueLatticeElement::getRange( | |||
566 | getConstantRangeFromMetadata(*Ranges)); | |||
567 | } | |||
568 | break; | |||
569 | }; | |||
570 | // Nothing known - will be intersected with other facts | |||
571 | return ValueLatticeElement::getOverdefined(); | |||
572 | } | |||
573 | ||||
574 | bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) { | |||
575 | assert(!isa<Constant>(Val) && "Value should not be constant")(static_cast <bool> (!isa<Constant>(Val) && "Value should not be constant") ? void (0) : __assert_fail ( "!isa<Constant>(Val) && \"Value should not be constant\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 575, __extension__ __PRETTY_FUNCTION__ )); | |||
576 | assert(!TheCache.getCachedValueInfo(Val, BB) &&(static_cast <bool> (!TheCache.getCachedValueInfo(Val, BB ) && "Value should not be in cache") ? void (0) : __assert_fail ("!TheCache.getCachedValueInfo(Val, BB) && \"Value should not be in cache\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 577, __extension__ __PRETTY_FUNCTION__ )) | |||
577 | "Value should not be in cache")(static_cast <bool> (!TheCache.getCachedValueInfo(Val, BB ) && "Value should not be in cache") ? void (0) : __assert_fail ("!TheCache.getCachedValueInfo(Val, BB) && \"Value should not be in cache\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 577, __extension__ __PRETTY_FUNCTION__ )); | |||
578 | ||||
579 | // Hold off inserting this value into the Cache in case we have to return | |||
580 | // false and come back later. | |||
581 | Optional<ValueLatticeElement> Res = solveBlockValueImpl(Val, BB); | |||
582 | if (!Res) | |||
583 | // Work pushed, will revisit | |||
584 | return false; | |||
585 | ||||
586 | TheCache.insertResult(Val, BB, *Res); | |||
587 | return true; | |||
588 | } | |||
589 | ||||
590 | Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueImpl( | |||
591 | Value *Val, BasicBlock *BB) { | |||
592 | Instruction *BBI = dyn_cast<Instruction>(Val); | |||
593 | if (!BBI || BBI->getParent() != BB) | |||
594 | return solveBlockValueNonLocal(Val, BB); | |||
595 | ||||
596 | if (PHINode *PN = dyn_cast<PHINode>(BBI)) | |||
597 | return solveBlockValuePHINode(PN, BB); | |||
598 | ||||
599 | if (auto *SI = dyn_cast<SelectInst>(BBI)) | |||
600 | return solveBlockValueSelect(SI, BB); | |||
601 | ||||
602 | // If this value is a nonnull pointer, record it's range and bailout. Note | |||
603 | // that for all other pointer typed values, we terminate the search at the | |||
604 | // definition. We could easily extend this to look through geps, bitcasts, | |||
605 | // and the like to prove non-nullness, but it's not clear that's worth it | |||
606 | // compile time wise. The context-insensitive value walk done inside | |||
607 | // isKnownNonZero gets most of the profitable cases at much less expense. | |||
608 | // This does mean that we have a sensitivity to where the defining | |||
609 | // instruction is placed, even if it could legally be hoisted much higher. | |||
610 | // That is unfortunate. | |||
611 | PointerType *PT = dyn_cast<PointerType>(BBI->getType()); | |||
612 | if (PT && isKnownNonZero(BBI, DL)) | |||
613 | return ValueLatticeElement::getNot(ConstantPointerNull::get(PT)); | |||
614 | ||||
615 | if (BBI->getType()->isIntegerTy()) { | |||
616 | if (auto *CI = dyn_cast<CastInst>(BBI)) | |||
617 | return solveBlockValueCast(CI, BB); | |||
618 | ||||
619 | if (BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI)) | |||
620 | return solveBlockValueBinaryOp(BO, BB); | |||
621 | ||||
622 | if (auto *EVI = dyn_cast<ExtractValueInst>(BBI)) | |||
623 | return solveBlockValueExtractValue(EVI, BB); | |||
624 | ||||
625 | if (auto *II = dyn_cast<IntrinsicInst>(BBI)) | |||
626 | return solveBlockValueIntrinsic(II, BB); | |||
627 | } | |||
628 | ||||
629 | LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << " compute BB '" << BB->getName() << "' - unknown inst def found.\n"; } } while (false) | |||
630 | << "' - unknown inst def found.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << " compute BB '" << BB->getName() << "' - unknown inst def found.\n"; } } while (false); | |||
631 | return getFromRangeMetadata(BBI); | |||
632 | } | |||
633 | ||||
634 | static void AddNonNullPointer(Value *Ptr, NonNullPointerSet &PtrSet) { | |||
635 | // TODO: Use NullPointerIsDefined instead. | |||
636 | if (Ptr->getType()->getPointerAddressSpace() == 0) | |||
637 | PtrSet.insert(getUnderlyingObject(Ptr)); | |||
638 | } | |||
639 | ||||
640 | static void AddNonNullPointersByInstruction( | |||
641 | Instruction *I, NonNullPointerSet &PtrSet) { | |||
642 | if (LoadInst *L = dyn_cast<LoadInst>(I)) { | |||
643 | AddNonNullPointer(L->getPointerOperand(), PtrSet); | |||
644 | } else if (StoreInst *S = dyn_cast<StoreInst>(I)) { | |||
645 | AddNonNullPointer(S->getPointerOperand(), PtrSet); | |||
646 | } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) { | |||
647 | if (MI->isVolatile()) return; | |||
648 | ||||
649 | // FIXME: check whether it has a valuerange that excludes zero? | |||
650 | ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength()); | |||
651 | if (!Len || Len->isZero()) return; | |||
652 | ||||
653 | AddNonNullPointer(MI->getRawDest(), PtrSet); | |||
654 | if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) | |||
655 | AddNonNullPointer(MTI->getRawSource(), PtrSet); | |||
656 | } | |||
657 | } | |||
658 | ||||
659 | bool LazyValueInfoImpl::isNonNullAtEndOfBlock(Value *Val, BasicBlock *BB) { | |||
660 | if (NullPointerIsDefined(BB->getParent(), | |||
661 | Val->getType()->getPointerAddressSpace())) | |||
662 | return false; | |||
663 | ||||
664 | Val = Val->stripInBoundsOffsets(); | |||
665 | return TheCache.isNonNullAtEndOfBlock(Val, BB, [](BasicBlock *BB) { | |||
666 | NonNullPointerSet NonNullPointers; | |||
667 | for (Instruction &I : *BB) | |||
668 | AddNonNullPointersByInstruction(&I, NonNullPointers); | |||
669 | return NonNullPointers; | |||
670 | }); | |||
671 | } | |||
672 | ||||
673 | Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueNonLocal( | |||
674 | Value *Val, BasicBlock *BB) { | |||
675 | ValueLatticeElement Result; // Start Undefined. | |||
676 | ||||
677 | // If this is the entry block, we must be asking about an argument. The | |||
678 | // value is overdefined. | |||
679 | if (BB->isEntryBlock()) { | |||
680 | assert(isa<Argument>(Val) && "Unknown live-in to the entry block")(static_cast <bool> (isa<Argument>(Val) && "Unknown live-in to the entry block") ? void (0) : __assert_fail ("isa<Argument>(Val) && \"Unknown live-in to the entry block\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 680, __extension__ __PRETTY_FUNCTION__ )); | |||
681 | return ValueLatticeElement::getOverdefined(); | |||
682 | } | |||
683 | ||||
684 | // Loop over all of our predecessors, merging what we know from them into | |||
685 | // result. If we encounter an unexplored predecessor, we eagerly explore it | |||
686 | // in a depth first manner. In practice, this has the effect of discovering | |||
687 | // paths we can't analyze eagerly without spending compile times analyzing | |||
688 | // other paths. This heuristic benefits from the fact that predecessors are | |||
689 | // frequently arranged such that dominating ones come first and we quickly | |||
690 | // find a path to function entry. TODO: We should consider explicitly | |||
691 | // canonicalizing to make this true rather than relying on this happy | |||
692 | // accident. | |||
693 | for (BasicBlock *Pred : predecessors(BB)) { | |||
694 | Optional<ValueLatticeElement> EdgeResult = getEdgeValue(Val, Pred, BB); | |||
695 | if (!EdgeResult) | |||
696 | // Explore that input, then return here | |||
697 | return std::nullopt; | |||
698 | ||||
699 | Result.mergeIn(*EdgeResult); | |||
700 | ||||
701 | // If we hit overdefined, exit early. The BlockVals entry is already set | |||
702 | // to overdefined. | |||
703 | if (Result.isOverdefined()) { | |||
704 | LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << " compute BB '" << BB->getName() << "' - overdefined because of pred '" << Pred->getName() << "' (non local).\n"; } } while (false) | |||
705 | << "' - overdefined because of pred '"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << " compute BB '" << BB->getName() << "' - overdefined because of pred '" << Pred->getName() << "' (non local).\n"; } } while (false) | |||
706 | << Pred->getName() << "' (non local).\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << " compute BB '" << BB->getName() << "' - overdefined because of pred '" << Pred->getName() << "' (non local).\n"; } } while (false); | |||
707 | return Result; | |||
708 | } | |||
709 | } | |||
710 | ||||
711 | // Return the merged value, which is more precise than 'overdefined'. | |||
712 | assert(!Result.isOverdefined())(static_cast <bool> (!Result.isOverdefined()) ? void (0 ) : __assert_fail ("!Result.isOverdefined()", "llvm/lib/Analysis/LazyValueInfo.cpp" , 712, __extension__ __PRETTY_FUNCTION__)); | |||
713 | return Result; | |||
714 | } | |||
715 | ||||
716 | Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValuePHINode( | |||
717 | PHINode *PN, BasicBlock *BB) { | |||
718 | ValueLatticeElement Result; // Start Undefined. | |||
719 | ||||
720 | // Loop over all of our predecessors, merging what we know from them into | |||
721 | // result. See the comment about the chosen traversal order in | |||
722 | // solveBlockValueNonLocal; the same reasoning applies here. | |||
723 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { | |||
724 | BasicBlock *PhiBB = PN->getIncomingBlock(i); | |||
725 | Value *PhiVal = PN->getIncomingValue(i); | |||
726 | // Note that we can provide PN as the context value to getEdgeValue, even | |||
727 | // though the results will be cached, because PN is the value being used as | |||
728 | // the cache key in the caller. | |||
729 | Optional<ValueLatticeElement> EdgeResult = | |||
730 | getEdgeValue(PhiVal, PhiBB, BB, PN); | |||
731 | if (!EdgeResult) | |||
732 | // Explore that input, then return here | |||
733 | return std::nullopt; | |||
734 | ||||
735 | Result.mergeIn(*EdgeResult); | |||
736 | ||||
737 | // If we hit overdefined, exit early. The BlockVals entry is already set | |||
738 | // to overdefined. | |||
739 | if (Result.isOverdefined()) { | |||
740 | LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << " compute BB '" << BB->getName() << "' - overdefined because of pred (local).\n" ; } } while (false) | |||
741 | << "' - overdefined because of pred (local).\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << " compute BB '" << BB->getName() << "' - overdefined because of pred (local).\n" ; } } while (false); | |||
742 | ||||
743 | return Result; | |||
744 | } | |||
745 | } | |||
746 | ||||
747 | // Return the merged value, which is more precise than 'overdefined'. | |||
748 | assert(!Result.isOverdefined() && "Possible PHI in entry block?")(static_cast <bool> (!Result.isOverdefined() && "Possible PHI in entry block?") ? void (0) : __assert_fail ( "!Result.isOverdefined() && \"Possible PHI in entry block?\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 748, __extension__ __PRETTY_FUNCTION__ )); | |||
749 | return Result; | |||
750 | } | |||
751 | ||||
752 | static ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond, | |||
753 | bool isTrueDest = true); | |||
754 | ||||
755 | // If we can determine a constraint on the value given conditions assumed by | |||
756 | // the program, intersect those constraints with BBLV | |||
757 | void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange( | |||
758 | Value *Val, ValueLatticeElement &BBLV, Instruction *BBI) { | |||
759 | BBI = BBI ? BBI : dyn_cast<Instruction>(Val); | |||
760 | if (!BBI) | |||
761 | return; | |||
762 | ||||
763 | BasicBlock *BB = BBI->getParent(); | |||
764 | for (auto &AssumeVH : AC->assumptionsFor(Val)) { | |||
765 | if (!AssumeVH) | |||
766 | continue; | |||
767 | ||||
768 | // Only check assumes in the block of the context instruction. Other | |||
769 | // assumes will have already been taken into account when the value was | |||
770 | // propagated from predecessor blocks. | |||
771 | auto *I = cast<CallInst>(AssumeVH); | |||
772 | if (I->getParent() != BB || !isValidAssumeForContext(I, BBI)) | |||
773 | continue; | |||
774 | ||||
775 | BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0))); | |||
776 | } | |||
777 | ||||
778 | // If guards are not used in the module, don't spend time looking for them | |||
779 | if (GuardDecl && !GuardDecl->use_empty() && | |||
780 | BBI->getIterator() != BB->begin()) { | |||
781 | for (Instruction &I : make_range(std::next(BBI->getIterator().getReverse()), | |||
782 | BB->rend())) { | |||
783 | Value *Cond = nullptr; | |||
784 | if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond)))) | |||
785 | BBLV = intersect(BBLV, getValueFromCondition(Val, Cond)); | |||
786 | } | |||
787 | } | |||
788 | ||||
789 | if (BBLV.isOverdefined()) { | |||
790 | // Check whether we're checking at the terminator, and the pointer has | |||
791 | // been dereferenced in this block. | |||
792 | PointerType *PTy = dyn_cast<PointerType>(Val->getType()); | |||
793 | if (PTy && BB->getTerminator() == BBI && | |||
794 | isNonNullAtEndOfBlock(Val, BB)) | |||
795 | BBLV = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy)); | |||
796 | } | |||
797 | } | |||
798 | ||||
799 | static ConstantRange getConstantRangeOrFull(const ValueLatticeElement &Val, | |||
800 | Type *Ty, const DataLayout &DL) { | |||
801 | if (Val.isConstantRange()) | |||
802 | return Val.getConstantRange(); | |||
803 | return ConstantRange::getFull(DL.getTypeSizeInBits(Ty)); | |||
804 | } | |||
805 | ||||
806 | Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueSelect( | |||
807 | SelectInst *SI, BasicBlock *BB) { | |||
808 | // Recurse on our inputs if needed | |||
809 | Optional<ValueLatticeElement> OptTrueVal = | |||
810 | getBlockValue(SI->getTrueValue(), BB, SI); | |||
811 | if (!OptTrueVal) | |||
812 | return std::nullopt; | |||
813 | ValueLatticeElement &TrueVal = *OptTrueVal; | |||
814 | ||||
815 | Optional<ValueLatticeElement> OptFalseVal = | |||
816 | getBlockValue(SI->getFalseValue(), BB, SI); | |||
817 | if (!OptFalseVal) | |||
818 | return std::nullopt; | |||
819 | ValueLatticeElement &FalseVal = *OptFalseVal; | |||
820 | ||||
821 | if (TrueVal.isConstantRange() || FalseVal.isConstantRange()) { | |||
822 | const ConstantRange &TrueCR = | |||
823 | getConstantRangeOrFull(TrueVal, SI->getType(), DL); | |||
824 | const ConstantRange &FalseCR = | |||
825 | getConstantRangeOrFull(FalseVal, SI->getType(), DL); | |||
826 | Value *LHS = nullptr; | |||
827 | Value *RHS = nullptr; | |||
828 | SelectPatternResult SPR = matchSelectPattern(SI, LHS, RHS); | |||
829 | // Is this a min specifically of our two inputs? (Avoid the risk of | |||
830 | // ValueTracking getting smarter looking back past our immediate inputs.) | |||
831 | if (SelectPatternResult::isMinOrMax(SPR.Flavor) && | |||
832 | ((LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) || | |||
833 | (RHS == SI->getTrueValue() && LHS == SI->getFalseValue()))) { | |||
834 | ConstantRange ResultCR = [&]() { | |||
835 | switch (SPR.Flavor) { | |||
836 | default: | |||
837 | llvm_unreachable("unexpected minmax type!")::llvm::llvm_unreachable_internal("unexpected minmax type!", "llvm/lib/Analysis/LazyValueInfo.cpp" , 837); | |||
838 | case SPF_SMIN: /// Signed minimum | |||
839 | return TrueCR.smin(FalseCR); | |||
840 | case SPF_UMIN: /// Unsigned minimum | |||
841 | return TrueCR.umin(FalseCR); | |||
842 | case SPF_SMAX: /// Signed maximum | |||
843 | return TrueCR.smax(FalseCR); | |||
844 | case SPF_UMAX: /// Unsigned maximum | |||
845 | return TrueCR.umax(FalseCR); | |||
846 | }; | |||
847 | }(); | |||
848 | return ValueLatticeElement::getRange( | |||
849 | ResultCR, TrueVal.isConstantRangeIncludingUndef() || | |||
850 | FalseVal.isConstantRangeIncludingUndef()); | |||
851 | } | |||
852 | ||||
853 | if (SPR.Flavor == SPF_ABS) { | |||
854 | if (LHS == SI->getTrueValue()) | |||
855 | return ValueLatticeElement::getRange( | |||
856 | TrueCR.abs(), TrueVal.isConstantRangeIncludingUndef()); | |||
857 | if (LHS == SI->getFalseValue()) | |||
858 | return ValueLatticeElement::getRange( | |||
859 | FalseCR.abs(), FalseVal.isConstantRangeIncludingUndef()); | |||
860 | } | |||
861 | ||||
862 | if (SPR.Flavor == SPF_NABS) { | |||
863 | ConstantRange Zero(APInt::getZero(TrueCR.getBitWidth())); | |||
864 | if (LHS == SI->getTrueValue()) | |||
865 | return ValueLatticeElement::getRange( | |||
866 | Zero.sub(TrueCR.abs()), FalseVal.isConstantRangeIncludingUndef()); | |||
867 | if (LHS == SI->getFalseValue()) | |||
868 | return ValueLatticeElement::getRange( | |||
869 | Zero.sub(FalseCR.abs()), FalseVal.isConstantRangeIncludingUndef()); | |||
870 | } | |||
871 | } | |||
872 | ||||
873 | // Can we constrain the facts about the true and false values by using the | |||
874 | // condition itself? This shows up with idioms like e.g. select(a > 5, a, 5). | |||
875 | // TODO: We could potentially refine an overdefined true value above. | |||
876 | Value *Cond = SI->getCondition(); | |||
877 | TrueVal = intersect(TrueVal, | |||
878 | getValueFromCondition(SI->getTrueValue(), Cond, true)); | |||
879 | FalseVal = intersect(FalseVal, | |||
880 | getValueFromCondition(SI->getFalseValue(), Cond, false)); | |||
881 | ||||
882 | ValueLatticeElement Result = TrueVal; | |||
883 | Result.mergeIn(FalseVal); | |||
884 | return Result; | |||
885 | } | |||
886 | ||||
887 | Optional<ConstantRange> LazyValueInfoImpl::getRangeFor(Value *V, | |||
888 | Instruction *CxtI, | |||
889 | BasicBlock *BB) { | |||
890 | Optional<ValueLatticeElement> OptVal = getBlockValue(V, BB, CxtI); | |||
891 | if (!OptVal) | |||
892 | return std::nullopt; | |||
893 | return getConstantRangeOrFull(*OptVal, V->getType(), DL); | |||
894 | } | |||
895 | ||||
896 | Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueCast( | |||
897 | CastInst *CI, BasicBlock *BB) { | |||
898 | // Without knowing how wide the input is, we can't analyze it in any useful | |||
899 | // way. | |||
900 | if (!CI->getOperand(0)->getType()->isSized()) | |||
901 | return ValueLatticeElement::getOverdefined(); | |||
902 | ||||
903 | // Filter out casts we don't know how to reason about before attempting to | |||
904 | // recurse on our operand. This can cut a long search short if we know we're | |||
905 | // not going to be able to get any useful information anways. | |||
906 | switch (CI->getOpcode()) { | |||
907 | case Instruction::Trunc: | |||
908 | case Instruction::SExt: | |||
909 | case Instruction::ZExt: | |||
910 | case Instruction::BitCast: | |||
911 | break; | |||
912 | default: | |||
913 | // Unhandled instructions are overdefined. | |||
914 | LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << " compute BB '" << BB->getName() << "' - overdefined (unknown cast).\n" ; } } while (false) | |||
915 | << "' - overdefined (unknown cast).\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << " compute BB '" << BB->getName() << "' - overdefined (unknown cast).\n" ; } } while (false); | |||
916 | return ValueLatticeElement::getOverdefined(); | |||
917 | } | |||
918 | ||||
919 | // Figure out the range of the LHS. If that fails, we still apply the | |||
920 | // transfer rule on the full set since we may be able to locally infer | |||
921 | // interesting facts. | |||
922 | Optional<ConstantRange> LHSRes = getRangeFor(CI->getOperand(0), CI, BB); | |||
923 | if (!LHSRes) | |||
924 | // More work to do before applying this transfer rule. | |||
925 | return std::nullopt; | |||
926 | const ConstantRange &LHSRange = LHSRes.value(); | |||
927 | ||||
928 | const unsigned ResultBitWidth = CI->getType()->getIntegerBitWidth(); | |||
929 | ||||
930 | // NOTE: We're currently limited by the set of operations that ConstantRange | |||
931 | // can evaluate symbolically. Enhancing that set will allows us to analyze | |||
932 | // more definitions. | |||
933 | return ValueLatticeElement::getRange(LHSRange.castOp(CI->getOpcode(), | |||
934 | ResultBitWidth)); | |||
935 | } | |||
936 | ||||
937 | Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueBinaryOpImpl( | |||
938 | Instruction *I, BasicBlock *BB, | |||
939 | std::function<ConstantRange(const ConstantRange &, | |||
940 | const ConstantRange &)> OpFn) { | |||
941 | // Figure out the ranges of the operands. If that fails, use a | |||
942 | // conservative range, but apply the transfer rule anyways. This | |||
943 | // lets us pick up facts from expressions like "and i32 (call i32 | |||
944 | // @foo()), 32" | |||
945 | Optional<ConstantRange> LHSRes = getRangeFor(I->getOperand(0), I, BB); | |||
946 | Optional<ConstantRange> RHSRes = getRangeFor(I->getOperand(1), I, BB); | |||
947 | if (!LHSRes || !RHSRes) | |||
948 | // More work to do before applying this transfer rule. | |||
949 | return std::nullopt; | |||
950 | ||||
951 | const ConstantRange &LHSRange = LHSRes.value(); | |||
952 | const ConstantRange &RHSRange = RHSRes.value(); | |||
953 | return ValueLatticeElement::getRange(OpFn(LHSRange, RHSRange)); | |||
954 | } | |||
955 | ||||
956 | Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueBinaryOp( | |||
957 | BinaryOperator *BO, BasicBlock *BB) { | |||
958 | assert(BO->getOperand(0)->getType()->isSized() &&(static_cast <bool> (BO->getOperand(0)->getType() ->isSized() && "all operands to binary operators are sized" ) ? void (0) : __assert_fail ("BO->getOperand(0)->getType()->isSized() && \"all operands to binary operators are sized\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 959, __extension__ __PRETTY_FUNCTION__ )) | |||
959 | "all operands to binary operators are sized")(static_cast <bool> (BO->getOperand(0)->getType() ->isSized() && "all operands to binary operators are sized" ) ? void (0) : __assert_fail ("BO->getOperand(0)->getType()->isSized() && \"all operands to binary operators are sized\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 959, __extension__ __PRETTY_FUNCTION__ )); | |||
960 | if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(BO)) { | |||
961 | unsigned NoWrapKind = 0; | |||
962 | if (OBO->hasNoUnsignedWrap()) | |||
963 | NoWrapKind |= OverflowingBinaryOperator::NoUnsignedWrap; | |||
964 | if (OBO->hasNoSignedWrap()) | |||
965 | NoWrapKind |= OverflowingBinaryOperator::NoSignedWrap; | |||
966 | ||||
967 | return solveBlockValueBinaryOpImpl( | |||
968 | BO, BB, | |||
969 | [BO, NoWrapKind](const ConstantRange &CR1, const ConstantRange &CR2) { | |||
970 | return CR1.overflowingBinaryOp(BO->getOpcode(), CR2, NoWrapKind); | |||
971 | }); | |||
972 | } | |||
973 | ||||
974 | return solveBlockValueBinaryOpImpl( | |||
975 | BO, BB, [BO](const ConstantRange &CR1, const ConstantRange &CR2) { | |||
976 | return CR1.binaryOp(BO->getOpcode(), CR2); | |||
977 | }); | |||
978 | } | |||
979 | ||||
980 | Optional<ValueLatticeElement> | |||
981 | LazyValueInfoImpl::solveBlockValueOverflowIntrinsic(WithOverflowInst *WO, | |||
982 | BasicBlock *BB) { | |||
983 | return solveBlockValueBinaryOpImpl( | |||
984 | WO, BB, [WO](const ConstantRange &CR1, const ConstantRange &CR2) { | |||
985 | return CR1.binaryOp(WO->getBinaryOp(), CR2); | |||
986 | }); | |||
987 | } | |||
988 | ||||
989 | Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueIntrinsic( | |||
990 | IntrinsicInst *II, BasicBlock *BB) { | |||
991 | if (!ConstantRange::isIntrinsicSupported(II->getIntrinsicID())) { | |||
992 | LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << " compute BB '" << BB->getName() << "' - unknown intrinsic.\n"; } } while (false) | |||
993 | << "' - unknown intrinsic.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << " compute BB '" << BB->getName() << "' - unknown intrinsic.\n"; } } while (false); | |||
994 | return getFromRangeMetadata(II); | |||
995 | } | |||
996 | ||||
997 | SmallVector<ConstantRange, 2> OpRanges; | |||
998 | for (Value *Op : II->args()) { | |||
999 | Optional<ConstantRange> Range = getRangeFor(Op, II, BB); | |||
1000 | if (!Range) | |||
1001 | return std::nullopt; | |||
1002 | OpRanges.push_back(*Range); | |||
1003 | } | |||
1004 | ||||
1005 | return ValueLatticeElement::getRange( | |||
1006 | ConstantRange::intrinsic(II->getIntrinsicID(), OpRanges)); | |||
1007 | } | |||
1008 | ||||
1009 | Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueExtractValue( | |||
1010 | ExtractValueInst *EVI, BasicBlock *BB) { | |||
1011 | if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand())) | |||
1012 | if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 0) | |||
1013 | return solveBlockValueOverflowIntrinsic(WO, BB); | |||
1014 | ||||
1015 | // Handle extractvalue of insertvalue to allow further simplification | |||
1016 | // based on replaced with.overflow intrinsics. | |||
1017 | if (Value *V = simplifyExtractValueInst( | |||
1018 | EVI->getAggregateOperand(), EVI->getIndices(), | |||
1019 | EVI->getModule()->getDataLayout())) | |||
1020 | return getBlockValue(V, BB, EVI); | |||
1021 | ||||
1022 | LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << " compute BB '" << BB->getName() << "' - overdefined (unknown extractvalue).\n" ; } } while (false) | |||
1023 | << "' - overdefined (unknown extractvalue).\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << " compute BB '" << BB->getName() << "' - overdefined (unknown extractvalue).\n" ; } } while (false); | |||
1024 | return ValueLatticeElement::getOverdefined(); | |||
1025 | } | |||
1026 | ||||
1027 | static bool matchICmpOperand(APInt &Offset, Value *LHS, Value *Val, | |||
1028 | ICmpInst::Predicate Pred) { | |||
1029 | if (LHS == Val) | |||
1030 | return true; | |||
1031 | ||||
1032 | // Handle range checking idiom produced by InstCombine. We will subtract the | |||
1033 | // offset from the allowed range for RHS in this case. | |||
1034 | const APInt *C; | |||
1035 | if (match(LHS, m_Add(m_Specific(Val), m_APInt(C)))) { | |||
1036 | Offset = *C; | |||
1037 | return true; | |||
1038 | } | |||
1039 | ||||
1040 | // Handle the symmetric case. This appears in saturation patterns like | |||
1041 | // (x == 16) ? 16 : (x + 1). | |||
1042 | if (match(Val, m_Add(m_Specific(LHS), m_APInt(C)))) { | |||
1043 | Offset = -*C; | |||
1044 | return true; | |||
1045 | } | |||
1046 | ||||
1047 | // If (x | y) < C, then (x < C) && (y < C). | |||
1048 | if (match(LHS, m_c_Or(m_Specific(Val), m_Value())) && | |||
1049 | (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_ULE)) | |||
1050 | return true; | |||
1051 | ||||
1052 | // If (x & y) > C, then (x > C) && (y > C). | |||
1053 | if (match(LHS, m_c_And(m_Specific(Val), m_Value())) && | |||
1054 | (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE)) | |||
1055 | return true; | |||
1056 | ||||
1057 | return false; | |||
1058 | } | |||
1059 | ||||
1060 | /// Get value range for a "(Val + Offset) Pred RHS" condition. | |||
1061 | static ValueLatticeElement getValueFromSimpleICmpCondition( | |||
1062 | CmpInst::Predicate Pred, Value *RHS, const APInt &Offset) { | |||
1063 | ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(), | |||
1064 | /*isFullSet=*/true); | |||
1065 | if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) | |||
1066 | RHSRange = ConstantRange(CI->getValue()); | |||
1067 | else if (Instruction *I = dyn_cast<Instruction>(RHS)) | |||
1068 | if (auto *Ranges = I->getMetadata(LLVMContext::MD_range)) | |||
1069 | RHSRange = getConstantRangeFromMetadata(*Ranges); | |||
1070 | ||||
1071 | ConstantRange TrueValues = | |||
1072 | ConstantRange::makeAllowedICmpRegion(Pred, RHSRange); | |||
1073 | return ValueLatticeElement::getRange(TrueValues.subtract(Offset)); | |||
1074 | } | |||
1075 | ||||
1076 | static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI, | |||
1077 | bool isTrueDest) { | |||
1078 | Value *LHS = ICI->getOperand(0); | |||
1079 | Value *RHS = ICI->getOperand(1); | |||
1080 | ||||
1081 | // Get the predicate that must hold along the considered edge. | |||
1082 | CmpInst::Predicate EdgePred = | |||
1083 | isTrueDest ? ICI->getPredicate() : ICI->getInversePredicate(); | |||
1084 | ||||
1085 | if (isa<Constant>(RHS)) { | |||
1086 | if (ICI->isEquality() && LHS == Val) { | |||
1087 | if (EdgePred == ICmpInst::ICMP_EQ) | |||
1088 | return ValueLatticeElement::get(cast<Constant>(RHS)); | |||
1089 | else if (!isa<UndefValue>(RHS)) | |||
1090 | return ValueLatticeElement::getNot(cast<Constant>(RHS)); | |||
1091 | } | |||
1092 | } | |||
1093 | ||||
1094 | Type *Ty = Val->getType(); | |||
1095 | if (!Ty->isIntegerTy()) | |||
1096 | return ValueLatticeElement::getOverdefined(); | |||
1097 | ||||
1098 | unsigned BitWidth = Ty->getScalarSizeInBits(); | |||
1099 | APInt Offset(BitWidth, 0); | |||
1100 | if (matchICmpOperand(Offset, LHS, Val, EdgePred)) | |||
1101 | return getValueFromSimpleICmpCondition(EdgePred, RHS, Offset); | |||
1102 | ||||
1103 | CmpInst::Predicate SwappedPred = CmpInst::getSwappedPredicate(EdgePred); | |||
1104 | if (matchICmpOperand(Offset, RHS, Val, SwappedPred)) | |||
1105 | return getValueFromSimpleICmpCondition(SwappedPred, LHS, Offset); | |||
1106 | ||||
1107 | const APInt *Mask, *C; | |||
1108 | if (match(LHS, m_And(m_Specific(Val), m_APInt(Mask))) && | |||
1109 | match(RHS, m_APInt(C))) { | |||
1110 | // If (Val & Mask) == C then all the masked bits are known and we can | |||
1111 | // compute a value range based on that. | |||
1112 | if (EdgePred == ICmpInst::ICMP_EQ) { | |||
1113 | KnownBits Known; | |||
1114 | Known.Zero = ~*C & *Mask; | |||
1115 | Known.One = *C & *Mask; | |||
1116 | return ValueLatticeElement::getRange( | |||
1117 | ConstantRange::fromKnownBits(Known, /*IsSigned*/ false)); | |||
1118 | } | |||
1119 | // If (Val & Mask) != 0 then the value must be larger than the lowest set | |||
1120 | // bit of Mask. | |||
1121 | if (EdgePred == ICmpInst::ICMP_NE && !Mask->isZero() && C->isZero()) { | |||
1122 | return ValueLatticeElement::getRange(ConstantRange::getNonEmpty( | |||
1123 | APInt::getOneBitSet(BitWidth, Mask->countTrailingZeros()), | |||
1124 | APInt::getZero(BitWidth))); | |||
1125 | } | |||
1126 | } | |||
1127 | ||||
1128 | // If (X urem Modulus) >= C, then X >= C. | |||
1129 | // If trunc X >= C, then X >= C. | |||
1130 | // TODO: An upper bound could be computed as well. | |||
1131 | if (match(LHS, m_CombineOr(m_URem(m_Specific(Val), m_Value()), | |||
1132 | m_Trunc(m_Specific(Val)))) && | |||
1133 | match(RHS, m_APInt(C))) { | |||
1134 | // Use the icmp region so we don't have to deal with different predicates. | |||
1135 | ConstantRange CR = ConstantRange::makeExactICmpRegion(EdgePred, *C); | |||
1136 | if (!CR.isEmptySet()) | |||
1137 | return ValueLatticeElement::getRange(ConstantRange::getNonEmpty( | |||
1138 | CR.getUnsignedMin().zext(BitWidth), APInt(BitWidth, 0))); | |||
1139 | } | |||
1140 | ||||
1141 | return ValueLatticeElement::getOverdefined(); | |||
1142 | } | |||
1143 | ||||
1144 | // Handle conditions of the form | |||
1145 | // extractvalue(op.with.overflow(%x, C), 1). | |||
1146 | static ValueLatticeElement getValueFromOverflowCondition( | |||
1147 | Value *Val, WithOverflowInst *WO, bool IsTrueDest) { | |||
1148 | // TODO: This only works with a constant RHS for now. We could also compute | |||
1149 | // the range of the RHS, but this doesn't fit into the current structure of | |||
1150 | // the edge value calculation. | |||
1151 | const APInt *C; | |||
1152 | if (WO->getLHS() != Val || !match(WO->getRHS(), m_APInt(C))) | |||
1153 | return ValueLatticeElement::getOverdefined(); | |||
1154 | ||||
1155 | // Calculate the possible values of %x for which no overflow occurs. | |||
1156 | ConstantRange NWR = ConstantRange::makeExactNoWrapRegion( | |||
1157 | WO->getBinaryOp(), *C, WO->getNoWrapKind()); | |||
1158 | ||||
1159 | // If overflow is false, %x is constrained to NWR. If overflow is true, %x is | |||
1160 | // constrained to it's inverse (all values that might cause overflow). | |||
1161 | if (IsTrueDest) | |||
1162 | NWR = NWR.inverse(); | |||
1163 | return ValueLatticeElement::getRange(NWR); | |||
1164 | } | |||
1165 | ||||
1166 | static Optional<ValueLatticeElement> | |||
1167 | getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest, | |||
1168 | bool isRevisit, | |||
1169 | SmallDenseMap<Value *, ValueLatticeElement> &Visited, | |||
1170 | SmallVectorImpl<Value *> &Worklist) { | |||
1171 | if (!isRevisit) { | |||
1172 | if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond)) | |||
1173 | return getValueFromICmpCondition(Val, ICI, isTrueDest); | |||
1174 | ||||
1175 | if (auto *EVI = dyn_cast<ExtractValueInst>(Cond)) | |||
1176 | if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand())) | |||
1177 | if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 1) | |||
1178 | return getValueFromOverflowCondition(Val, WO, isTrueDest); | |||
1179 | } | |||
1180 | ||||
1181 | Value *L, *R; | |||
1182 | bool IsAnd; | |||
1183 | if (match(Cond, m_LogicalAnd(m_Value(L), m_Value(R)))) | |||
1184 | IsAnd = true; | |||
1185 | else if (match(Cond, m_LogicalOr(m_Value(L), m_Value(R)))) | |||
1186 | IsAnd = false; | |||
1187 | else | |||
1188 | return ValueLatticeElement::getOverdefined(); | |||
1189 | ||||
1190 | auto LV = Visited.find(L); | |||
1191 | auto RV = Visited.find(R); | |||
1192 | ||||
1193 | // if (L && R) -> intersect L and R | |||
1194 | // if (!(L || R)) -> intersect L and R | |||
1195 | // if (L || R) -> union L and R | |||
1196 | // if (!(L && R)) -> union L and R | |||
1197 | if ((isTrueDest ^ IsAnd) && (LV != Visited.end())) { | |||
1198 | ValueLatticeElement V = LV->second; | |||
1199 | if (V.isOverdefined()) | |||
1200 | return V; | |||
1201 | if (RV != Visited.end()) { | |||
1202 | V.mergeIn(RV->second); | |||
1203 | return V; | |||
1204 | } | |||
1205 | } | |||
1206 | ||||
1207 | if (LV == Visited.end() || RV == Visited.end()) { | |||
1208 | assert(!isRevisit)(static_cast <bool> (!isRevisit) ? void (0) : __assert_fail ("!isRevisit", "llvm/lib/Analysis/LazyValueInfo.cpp", 1208, __extension__ __PRETTY_FUNCTION__)); | |||
1209 | if (LV == Visited.end()) | |||
1210 | Worklist.push_back(L); | |||
1211 | if (RV == Visited.end()) | |||
1212 | Worklist.push_back(R); | |||
1213 | return std::nullopt; | |||
1214 | } | |||
1215 | ||||
1216 | return intersect(LV->second, RV->second); | |||
1217 | } | |||
1218 | ||||
1219 | ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond, | |||
1220 | bool isTrueDest) { | |||
1221 | assert(Cond && "precondition")(static_cast <bool> (Cond && "precondition") ? void (0) : __assert_fail ("Cond && \"precondition\"", "llvm/lib/Analysis/LazyValueInfo.cpp" , 1221, __extension__ __PRETTY_FUNCTION__)); | |||
1222 | SmallDenseMap<Value*, ValueLatticeElement> Visited; | |||
1223 | SmallVector<Value *> Worklist; | |||
1224 | ||||
1225 | Worklist.push_back(Cond); | |||
1226 | do { | |||
1227 | Value *CurrentCond = Worklist.back(); | |||
1228 | // Insert an Overdefined placeholder into the set to prevent | |||
1229 | // infinite recursion if there exists IRs that use not | |||
1230 | // dominated by its def as in this example: | |||
1231 | // "%tmp3 = or i1 undef, %tmp4" | |||
1232 | // "%tmp4 = or i1 undef, %tmp3" | |||
1233 | auto Iter = | |||
1234 | Visited.try_emplace(CurrentCond, ValueLatticeElement::getOverdefined()); | |||
1235 | bool isRevisit = !Iter.second; | |||
1236 | Optional<ValueLatticeElement> Result = getValueFromConditionImpl( | |||
1237 | Val, CurrentCond, isTrueDest, isRevisit, Visited, Worklist); | |||
1238 | if (Result) { | |||
1239 | Visited[CurrentCond] = *Result; | |||
1240 | Worklist.pop_back(); | |||
1241 | } | |||
1242 | } while (!Worklist.empty()); | |||
1243 | ||||
1244 | auto Result = Visited.find(Cond); | |||
1245 | assert(Result != Visited.end())(static_cast <bool> (Result != Visited.end()) ? void (0 ) : __assert_fail ("Result != Visited.end()", "llvm/lib/Analysis/LazyValueInfo.cpp" , 1245, __extension__ __PRETTY_FUNCTION__)); | |||
1246 | return Result->second; | |||
1247 | } | |||
1248 | ||||
1249 | // Return true if Usr has Op as an operand, otherwise false. | |||
1250 | static bool usesOperand(User *Usr, Value *Op) { | |||
1251 | return is_contained(Usr->operands(), Op); | |||
1252 | } | |||
1253 | ||||
1254 | // Return true if the instruction type of Val is supported by | |||
1255 | // constantFoldUser(). Currently CastInst, BinaryOperator and FreezeInst only. | |||
1256 | // Call this before calling constantFoldUser() to find out if it's even worth | |||
1257 | // attempting to call it. | |||
1258 | static bool isOperationFoldable(User *Usr) { | |||
1259 | return isa<CastInst>(Usr) || isa<BinaryOperator>(Usr) || isa<FreezeInst>(Usr); | |||
1260 | } | |||
1261 | ||||
1262 | // Check if Usr can be simplified to an integer constant when the value of one | |||
1263 | // of its operands Op is an integer constant OpConstVal. If so, return it as an | |||
1264 | // lattice value range with a single element or otherwise return an overdefined | |||
1265 | // lattice value. | |||
1266 | static ValueLatticeElement constantFoldUser(User *Usr, Value *Op, | |||
1267 | const APInt &OpConstVal, | |||
1268 | const DataLayout &DL) { | |||
1269 | assert(isOperationFoldable(Usr) && "Precondition")(static_cast <bool> (isOperationFoldable(Usr) && "Precondition") ? void (0) : __assert_fail ("isOperationFoldable(Usr) && \"Precondition\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 1269, __extension__ __PRETTY_FUNCTION__ )); | |||
1270 | Constant* OpConst = Constant::getIntegerValue(Op->getType(), OpConstVal); | |||
1271 | // Check if Usr can be simplified to a constant. | |||
1272 | if (auto *CI = dyn_cast<CastInst>(Usr)) { | |||
1273 | assert(CI->getOperand(0) == Op && "Operand 0 isn't Op")(static_cast <bool> (CI->getOperand(0) == Op && "Operand 0 isn't Op") ? void (0) : __assert_fail ("CI->getOperand(0) == Op && \"Operand 0 isn't Op\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 1273, __extension__ __PRETTY_FUNCTION__ )); | |||
1274 | if (auto *C = dyn_cast_or_null<ConstantInt>( | |||
1275 | simplifyCastInst(CI->getOpcode(), OpConst, | |||
1276 | CI->getDestTy(), DL))) { | |||
1277 | return ValueLatticeElement::getRange(ConstantRange(C->getValue())); | |||
1278 | } | |||
1279 | } else if (auto *BO = dyn_cast<BinaryOperator>(Usr)) { | |||
1280 | bool Op0Match = BO->getOperand(0) == Op; | |||
1281 | bool Op1Match = BO->getOperand(1) == Op; | |||
1282 | assert((Op0Match || Op1Match) &&(static_cast <bool> ((Op0Match || Op1Match) && "Operand 0 nor Operand 1 isn't a match" ) ? void (0) : __assert_fail ("(Op0Match || Op1Match) && \"Operand 0 nor Operand 1 isn't a match\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 1283, __extension__ __PRETTY_FUNCTION__ )) | |||
1283 | "Operand 0 nor Operand 1 isn't a match")(static_cast <bool> ((Op0Match || Op1Match) && "Operand 0 nor Operand 1 isn't a match" ) ? void (0) : __assert_fail ("(Op0Match || Op1Match) && \"Operand 0 nor Operand 1 isn't a match\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 1283, __extension__ __PRETTY_FUNCTION__ )); | |||
1284 | Value *LHS = Op0Match ? OpConst : BO->getOperand(0); | |||
1285 | Value *RHS = Op1Match ? OpConst : BO->getOperand(1); | |||
1286 | if (auto *C = dyn_cast_or_null<ConstantInt>( | |||
1287 | simplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) { | |||
1288 | return ValueLatticeElement::getRange(ConstantRange(C->getValue())); | |||
1289 | } | |||
1290 | } else if (isa<FreezeInst>(Usr)) { | |||
1291 | assert(cast<FreezeInst>(Usr)->getOperand(0) == Op && "Operand 0 isn't Op")(static_cast <bool> (cast<FreezeInst>(Usr)->getOperand (0) == Op && "Operand 0 isn't Op") ? void (0) : __assert_fail ("cast<FreezeInst>(Usr)->getOperand(0) == Op && \"Operand 0 isn't Op\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 1291, __extension__ __PRETTY_FUNCTION__ )); | |||
1292 | return ValueLatticeElement::getRange(ConstantRange(OpConstVal)); | |||
1293 | } | |||
1294 | return ValueLatticeElement::getOverdefined(); | |||
1295 | } | |||
1296 | ||||
1297 | /// Compute the value of Val on the edge BBFrom -> BBTo. Returns false if | |||
1298 | /// Val is not constrained on the edge. Result is unspecified if return value | |||
1299 | /// is false. | |||
1300 | static std::optional<ValueLatticeElement> getEdgeValueLocal(Value *Val, | |||
1301 | BasicBlock *BBFrom, | |||
1302 | BasicBlock *BBTo) { | |||
1303 | // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we | |||
1304 | // know that v != 0. | |||
1305 | if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) { | |||
1306 | // If this is a conditional branch and only one successor goes to BBTo, then | |||
1307 | // we may be able to infer something from the condition. | |||
1308 | if (BI->isConditional() && | |||
1309 | BI->getSuccessor(0) != BI->getSuccessor(1)) { | |||
1310 | bool isTrueDest = BI->getSuccessor(0) == BBTo; | |||
1311 | assert(BI->getSuccessor(!isTrueDest) == BBTo &&(static_cast <bool> (BI->getSuccessor(!isTrueDest) == BBTo && "BBTo isn't a successor of BBFrom") ? void ( 0) : __assert_fail ("BI->getSuccessor(!isTrueDest) == BBTo && \"BBTo isn't a successor of BBFrom\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 1312, __extension__ __PRETTY_FUNCTION__ )) | |||
1312 | "BBTo isn't a successor of BBFrom")(static_cast <bool> (BI->getSuccessor(!isTrueDest) == BBTo && "BBTo isn't a successor of BBFrom") ? void ( 0) : __assert_fail ("BI->getSuccessor(!isTrueDest) == BBTo && \"BBTo isn't a successor of BBFrom\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 1312, __extension__ __PRETTY_FUNCTION__ )); | |||
1313 | Value *Condition = BI->getCondition(); | |||
1314 | ||||
1315 | // If V is the condition of the branch itself, then we know exactly what | |||
1316 | // it is. | |||
1317 | if (Condition == Val) | |||
1318 | return ValueLatticeElement::get(ConstantInt::get( | |||
1319 | Type::getInt1Ty(Val->getContext()), isTrueDest)); | |||
1320 | ||||
1321 | // If the condition of the branch is an equality comparison, we may be | |||
1322 | // able to infer the value. | |||
1323 | ValueLatticeElement Result = getValueFromCondition(Val, Condition, | |||
1324 | isTrueDest); | |||
1325 | if (!Result.isOverdefined()) | |||
1326 | return Result; | |||
1327 | ||||
1328 | if (User *Usr = dyn_cast<User>(Val)) { | |||
1329 | assert(Result.isOverdefined() && "Result isn't overdefined")(static_cast <bool> (Result.isOverdefined() && "Result isn't overdefined" ) ? void (0) : __assert_fail ("Result.isOverdefined() && \"Result isn't overdefined\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 1329, __extension__ __PRETTY_FUNCTION__ )); | |||
1330 | // Check with isOperationFoldable() first to avoid linearly iterating | |||
1331 | // over the operands unnecessarily which can be expensive for | |||
1332 | // instructions with many operands. | |||
1333 | if (isa<IntegerType>(Usr->getType()) && isOperationFoldable(Usr)) { | |||
1334 | const DataLayout &DL = BBTo->getModule()->getDataLayout(); | |||
1335 | if (usesOperand(Usr, Condition)) { | |||
1336 | // If Val has Condition as an operand and Val can be folded into a | |||
1337 | // constant with either Condition == true or Condition == false, | |||
1338 | // propagate the constant. | |||
1339 | // eg. | |||
1340 | // ; %Val is true on the edge to %then. | |||
1341 | // %Val = and i1 %Condition, true. | |||
1342 | // br %Condition, label %then, label %else | |||
1343 | APInt ConditionVal(1, isTrueDest ? 1 : 0); | |||
1344 | Result = constantFoldUser(Usr, Condition, ConditionVal, DL); | |||
1345 | } else { | |||
1346 | // If one of Val's operand has an inferred value, we may be able to | |||
1347 | // infer the value of Val. | |||
1348 | // eg. | |||
1349 | // ; %Val is 94 on the edge to %then. | |||
1350 | // %Val = add i8 %Op, 1 | |||
1351 | // %Condition = icmp eq i8 %Op, 93 | |||
1352 | // br i1 %Condition, label %then, label %else | |||
1353 | for (unsigned i = 0; i < Usr->getNumOperands(); ++i) { | |||
1354 | Value *Op = Usr->getOperand(i); | |||
1355 | ValueLatticeElement OpLatticeVal = | |||
1356 | getValueFromCondition(Op, Condition, isTrueDest); | |||
1357 | if (Optional<APInt> OpConst = OpLatticeVal.asConstantInteger()) { | |||
1358 | Result = constantFoldUser(Usr, Op, *OpConst, DL); | |||
1359 | break; | |||
1360 | } | |||
1361 | } | |||
1362 | } | |||
1363 | } | |||
1364 | } | |||
1365 | if (!Result.isOverdefined()) | |||
1366 | return Result; | |||
1367 | } | |||
1368 | } | |||
1369 | ||||
1370 | // If the edge was formed by a switch on the value, then we may know exactly | |||
1371 | // what it is. | |||
1372 | if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) { | |||
1373 | Value *Condition = SI->getCondition(); | |||
1374 | if (!isa<IntegerType>(Val->getType())) | |||
1375 | return std::nullopt; | |||
1376 | bool ValUsesConditionAndMayBeFoldable = false; | |||
1377 | if (Condition != Val) { | |||
1378 | // Check if Val has Condition as an operand. | |||
1379 | if (User *Usr = dyn_cast<User>(Val)) | |||
1380 | ValUsesConditionAndMayBeFoldable = isOperationFoldable(Usr) && | |||
1381 | usesOperand(Usr, Condition); | |||
1382 | if (!ValUsesConditionAndMayBeFoldable) | |||
1383 | return std::nullopt; | |||
1384 | } | |||
1385 | assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&(static_cast <bool> ((Condition == Val || ValUsesConditionAndMayBeFoldable ) && "Condition != Val nor Val doesn't use Condition" ) ? void (0) : __assert_fail ("(Condition == Val || ValUsesConditionAndMayBeFoldable) && \"Condition != Val nor Val doesn't use Condition\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 1386, __extension__ __PRETTY_FUNCTION__ )) | |||
1386 | "Condition != Val nor Val doesn't use Condition")(static_cast <bool> ((Condition == Val || ValUsesConditionAndMayBeFoldable ) && "Condition != Val nor Val doesn't use Condition" ) ? void (0) : __assert_fail ("(Condition == Val || ValUsesConditionAndMayBeFoldable) && \"Condition != Val nor Val doesn't use Condition\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 1386, __extension__ __PRETTY_FUNCTION__ )); | |||
1387 | ||||
1388 | bool DefaultCase = SI->getDefaultDest() == BBTo; | |||
1389 | unsigned BitWidth = Val->getType()->getIntegerBitWidth(); | |||
1390 | ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/); | |||
1391 | ||||
1392 | for (auto Case : SI->cases()) { | |||
1393 | APInt CaseValue = Case.getCaseValue()->getValue(); | |||
1394 | ConstantRange EdgeVal(CaseValue); | |||
1395 | if (ValUsesConditionAndMayBeFoldable) { | |||
1396 | User *Usr = cast<User>(Val); | |||
1397 | const DataLayout &DL = BBTo->getModule()->getDataLayout(); | |||
1398 | ValueLatticeElement EdgeLatticeVal = | |||
1399 | constantFoldUser(Usr, Condition, CaseValue, DL); | |||
1400 | if (EdgeLatticeVal.isOverdefined()) | |||
1401 | return std::nullopt; | |||
1402 | EdgeVal = EdgeLatticeVal.getConstantRange(); | |||
1403 | } | |||
1404 | if (DefaultCase) { | |||
1405 | // It is possible that the default destination is the destination of | |||
1406 | // some cases. We cannot perform difference for those cases. | |||
1407 | // We know Condition != CaseValue in BBTo. In some cases we can use | |||
1408 | // this to infer Val == f(Condition) is != f(CaseValue). For now, we | |||
1409 | // only do this when f is identity (i.e. Val == Condition), but we | |||
1410 | // should be able to do this for any injective f. | |||
1411 | if (Case.getCaseSuccessor() != BBTo && Condition == Val) | |||
1412 | EdgesVals = EdgesVals.difference(EdgeVal); | |||
1413 | } else if (Case.getCaseSuccessor() == BBTo) | |||
1414 | EdgesVals = EdgesVals.unionWith(EdgeVal); | |||
1415 | } | |||
1416 | return ValueLatticeElement::getRange(std::move(EdgesVals)); | |||
1417 | } | |||
1418 | return std::nullopt; | |||
1419 | } | |||
1420 | ||||
1421 | /// Compute the value of Val on the edge BBFrom -> BBTo or the value at | |||
1422 | /// the basic block if the edge does not constrain Val. | |||
1423 | Optional<ValueLatticeElement> LazyValueInfoImpl::getEdgeValue( | |||
1424 | Value *Val, BasicBlock *BBFrom, BasicBlock *BBTo, Instruction *CxtI) { | |||
1425 | // If already a constant, there is nothing to compute. | |||
1426 | if (Constant *VC = dyn_cast<Constant>(Val)) | |||
1427 | return ValueLatticeElement::get(VC); | |||
1428 | ||||
1429 | ValueLatticeElement LocalResult = | |||
1430 | getEdgeValueLocal(Val, BBFrom, BBTo) | |||
1431 | .value_or(ValueLatticeElement::getOverdefined()); | |||
1432 | if (hasSingleValue(LocalResult)) | |||
1433 | // Can't get any more precise here | |||
1434 | return LocalResult; | |||
1435 | ||||
1436 | Optional<ValueLatticeElement> OptInBlock = | |||
1437 | getBlockValue(Val, BBFrom, BBFrom->getTerminator()); | |||
1438 | if (!OptInBlock) | |||
1439 | return std::nullopt; | |||
1440 | ValueLatticeElement &InBlock = *OptInBlock; | |||
1441 | ||||
1442 | // We can use the context instruction (generically the ultimate instruction | |||
1443 | // the calling pass is trying to simplify) here, even though the result of | |||
1444 | // this function is generally cached when called from the solve* functions | |||
1445 | // (and that cached result might be used with queries using a different | |||
1446 | // context instruction), because when this function is called from the solve* | |||
1447 | // functions, the context instruction is not provided. When called from | |||
1448 | // LazyValueInfoImpl::getValueOnEdge, the context instruction is provided, | |||
1449 | // but then the result is not cached. | |||
1450 | intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI); | |||
1451 | ||||
1452 | return intersect(LocalResult, InBlock); | |||
1453 | } | |||
1454 | ||||
1455 | ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB, | |||
1456 | Instruction *CxtI) { | |||
1457 | LLVM_DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << "LVI Getting block end value " << *V << " at '" << BB->getName() << "'\n"; } } while (false) | |||
1458 | << BB->getName() << "'\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << "LVI Getting block end value " << *V << " at '" << BB->getName() << "'\n"; } } while (false); | |||
1459 | ||||
1460 | assert(BlockValueStack.empty() && BlockValueSet.empty())(static_cast <bool> (BlockValueStack.empty() && BlockValueSet.empty()) ? void (0) : __assert_fail ("BlockValueStack.empty() && BlockValueSet.empty()" , "llvm/lib/Analysis/LazyValueInfo.cpp", 1460, __extension__ __PRETTY_FUNCTION__ )); | |||
1461 | Optional<ValueLatticeElement> OptResult = getBlockValue(V, BB, CxtI); | |||
1462 | if (!OptResult) { | |||
1463 | solve(); | |||
1464 | OptResult = getBlockValue(V, BB, CxtI); | |||
1465 | assert(OptResult && "Value not available after solving")(static_cast <bool> (OptResult && "Value not available after solving" ) ? void (0) : __assert_fail ("OptResult && \"Value not available after solving\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 1465, __extension__ __PRETTY_FUNCTION__ )); | |||
1466 | } | |||
1467 | ||||
1468 | ValueLatticeElement Result = *OptResult; | |||
1469 | LLVM_DEBUG(dbgs() << " Result = " << Result << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << " Result = " << Result << "\n"; } } while (false); | |||
1470 | return Result; | |||
1471 | } | |||
1472 | ||||
1473 | ValueLatticeElement LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) { | |||
1474 | LLVM_DEBUG(dbgs() << "LVI Getting value " << *V << " at '" << CxtI->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << "LVI Getting value " << *V << " at '" << CxtI->getName() << "'\n" ; } } while (false) | |||
1475 | << "'\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << "LVI Getting value " << *V << " at '" << CxtI->getName() << "'\n" ; } } while (false); | |||
1476 | ||||
1477 | if (auto *C = dyn_cast<Constant>(V)) | |||
1478 | return ValueLatticeElement::get(C); | |||
1479 | ||||
1480 | ValueLatticeElement Result = ValueLatticeElement::getOverdefined(); | |||
1481 | if (auto *I = dyn_cast<Instruction>(V)) | |||
1482 | Result = getFromRangeMetadata(I); | |||
1483 | intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI); | |||
1484 | ||||
1485 | LLVM_DEBUG(dbgs() << " Result = " << Result << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << " Result = " << Result << "\n"; } } while (false); | |||
1486 | return Result; | |||
1487 | } | |||
1488 | ||||
1489 | ValueLatticeElement LazyValueInfoImpl:: | |||
1490 | getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, | |||
1491 | Instruction *CxtI) { | |||
1492 | LLVM_DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << "LVI Getting edge value " << *V << " from '" << FromBB->getName() << "' to '" << ToBB->getName() << "'\n" ; } } while (false) | |||
1493 | << FromBB->getName() << "' to '" << ToBB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << "LVI Getting edge value " << *V << " from '" << FromBB->getName() << "' to '" << ToBB->getName() << "'\n" ; } } while (false) | |||
1494 | << "'\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << "LVI Getting edge value " << *V << " from '" << FromBB->getName() << "' to '" << ToBB->getName() << "'\n" ; } } while (false); | |||
1495 | ||||
1496 | Optional<ValueLatticeElement> Result = getEdgeValue(V, FromBB, ToBB, CxtI); | |||
1497 | if (!Result) { | |||
1498 | solve(); | |||
1499 | Result = getEdgeValue(V, FromBB, ToBB, CxtI); | |||
1500 | assert(Result && "More work to do after problem solved?")(static_cast <bool> (Result && "More work to do after problem solved?" ) ? void (0) : __assert_fail ("Result && \"More work to do after problem solved?\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 1500, __extension__ __PRETTY_FUNCTION__ )); | |||
1501 | } | |||
1502 | ||||
1503 | LLVM_DEBUG(dbgs() << " Result = " << *Result << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("lazy-value-info")) { dbgs() << " Result = " << *Result << "\n"; } } while (false); | |||
1504 | return *Result; | |||
1505 | } | |||
1506 | ||||
1507 | void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, | |||
1508 | BasicBlock *NewSucc) { | |||
1509 | TheCache.threadEdgeImpl(OldSucc, NewSucc); | |||
1510 | } | |||
1511 | ||||
1512 | //===----------------------------------------------------------------------===// | |||
1513 | // LazyValueInfo Impl | |||
1514 | //===----------------------------------------------------------------------===// | |||
1515 | ||||
1516 | /// This lazily constructs the LazyValueInfoImpl. | |||
1517 | static LazyValueInfoImpl &getImpl(void *&PImpl, AssumptionCache *AC, | |||
1518 | const Module *M) { | |||
1519 | if (!PImpl) { | |||
1520 | assert(M && "getCache() called with a null Module")(static_cast <bool> (M && "getCache() called with a null Module" ) ? void (0) : __assert_fail ("M && \"getCache() called with a null Module\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 1520, __extension__ __PRETTY_FUNCTION__ )); | |||
1521 | const DataLayout &DL = M->getDataLayout(); | |||
1522 | Function *GuardDecl = M->getFunction( | |||
1523 | Intrinsic::getName(Intrinsic::experimental_guard)); | |||
1524 | PImpl = new LazyValueInfoImpl(AC, DL, GuardDecl); | |||
1525 | } | |||
1526 | return *static_cast<LazyValueInfoImpl*>(PImpl); | |||
1527 | } | |||
1528 | ||||
1529 | bool LazyValueInfoWrapperPass::runOnFunction(Function &F) { | |||
1530 | Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); | |||
1531 | Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F); | |||
1532 | ||||
1533 | if (Info.PImpl) | |||
1534 | getImpl(Info.PImpl, Info.AC, F.getParent()).clear(); | |||
1535 | ||||
1536 | // Fully lazy. | |||
1537 | return false; | |||
1538 | } | |||
1539 | ||||
1540 | void LazyValueInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { | |||
1541 | AU.setPreservesAll(); | |||
1542 | AU.addRequired<AssumptionCacheTracker>(); | |||
1543 | AU.addRequired<TargetLibraryInfoWrapperPass>(); | |||
1544 | } | |||
1545 | ||||
1546 | LazyValueInfo &LazyValueInfoWrapperPass::getLVI() { return Info; } | |||
1547 | ||||
1548 | LazyValueInfo::~LazyValueInfo() { releaseMemory(); } | |||
1549 | ||||
1550 | void LazyValueInfo::releaseMemory() { | |||
1551 | // If the cache was allocated, free it. | |||
1552 | if (PImpl) { | |||
1553 | delete &getImpl(PImpl, AC, nullptr); | |||
1554 | PImpl = nullptr; | |||
1555 | } | |||
1556 | } | |||
1557 | ||||
1558 | bool LazyValueInfo::invalidate(Function &F, const PreservedAnalyses &PA, | |||
1559 | FunctionAnalysisManager::Invalidator &Inv) { | |||
1560 | // We need to invalidate if we have either failed to preserve this analyses | |||
1561 | // result directly or if any of its dependencies have been invalidated. | |||
1562 | auto PAC = PA.getChecker<LazyValueAnalysis>(); | |||
1563 | if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>())) | |||
1564 | return true; | |||
1565 | ||||
1566 | return false; | |||
1567 | } | |||
1568 | ||||
1569 | void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); } | |||
1570 | ||||
1571 | LazyValueInfo LazyValueAnalysis::run(Function &F, | |||
1572 | FunctionAnalysisManager &FAM) { | |||
1573 | auto &AC = FAM.getResult<AssumptionAnalysis>(F); | |||
1574 | auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F); | |||
1575 | ||||
1576 | return LazyValueInfo(&AC, &F.getParent()->getDataLayout(), &TLI); | |||
1577 | } | |||
1578 | ||||
1579 | /// Returns true if we can statically tell that this value will never be a | |||
1580 | /// "useful" constant. In practice, this means we've got something like an | |||
1581 | /// alloca or a malloc call for which a comparison against a constant can | |||
1582 | /// only be guarding dead code. Note that we are potentially giving up some | |||
1583 | /// precision in dead code (a constant result) in favour of avoiding a | |||
1584 | /// expensive search for a easily answered common query. | |||
1585 | static bool isKnownNonConstant(Value *V) { | |||
1586 | V = V->stripPointerCasts(); | |||
1587 | // The return val of alloc cannot be a Constant. | |||
1588 | if (isa<AllocaInst>(V)) | |||
1589 | return true; | |||
1590 | return false; | |||
1591 | } | |||
1592 | ||||
1593 | Constant *LazyValueInfo::getConstant(Value *V, Instruction *CxtI) { | |||
1594 | // Bail out early if V is known not to be a Constant. | |||
1595 | if (isKnownNonConstant(V)) | |||
1596 | return nullptr; | |||
1597 | ||||
1598 | BasicBlock *BB = CxtI->getParent(); | |||
1599 | ValueLatticeElement Result = | |||
1600 | getImpl(PImpl, AC, BB->getModule()).getValueInBlock(V, BB, CxtI); | |||
1601 | ||||
1602 | if (Result.isConstant()) | |||
1603 | return Result.getConstant(); | |||
1604 | if (Result.isConstantRange()) { | |||
1605 | const ConstantRange &CR = Result.getConstantRange(); | |||
1606 | if (const APInt *SingleVal = CR.getSingleElement()) | |||
1607 | return ConstantInt::get(V->getContext(), *SingleVal); | |||
1608 | } | |||
1609 | return nullptr; | |||
1610 | } | |||
1611 | ||||
1612 | ConstantRange LazyValueInfo::getConstantRange(Value *V, Instruction *CxtI, | |||
1613 | bool UndefAllowed) { | |||
1614 | assert(V->getType()->isIntegerTy())(static_cast <bool> (V->getType()->isIntegerTy()) ? void (0) : __assert_fail ("V->getType()->isIntegerTy()" , "llvm/lib/Analysis/LazyValueInfo.cpp", 1614, __extension__ __PRETTY_FUNCTION__ )); | |||
| ||||
1615 | unsigned Width = V->getType()->getIntegerBitWidth(); | |||
1616 | BasicBlock *BB = CxtI->getParent(); | |||
1617 | ValueLatticeElement Result = | |||
1618 | getImpl(PImpl, AC, BB->getModule()).getValueInBlock(V, BB, CxtI); | |||
1619 | if (Result.isUnknown()) | |||
1620 | return ConstantRange::getEmpty(Width); | |||
1621 | if (Result.isConstantRange(UndefAllowed)) | |||
1622 | return Result.getConstantRange(UndefAllowed); | |||
1623 | // We represent ConstantInt constants as constant ranges but other kinds | |||
1624 | // of integer constants, i.e. ConstantExpr will be tagged as constants | |||
1625 | assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&(static_cast <bool> (!(Result.isConstant() && isa <ConstantInt>(Result.getConstant())) && "ConstantInt value must be represented as constantrange" ) ? void (0) : __assert_fail ("!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) && \"ConstantInt value must be represented as constantrange\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 1626, __extension__ __PRETTY_FUNCTION__ )) | |||
1626 | "ConstantInt value must be represented as constantrange")(static_cast <bool> (!(Result.isConstant() && isa <ConstantInt>(Result.getConstant())) && "ConstantInt value must be represented as constantrange" ) ? void (0) : __assert_fail ("!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) && \"ConstantInt value must be represented as constantrange\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 1626, __extension__ __PRETTY_FUNCTION__ )); | |||
1627 | return ConstantRange::getFull(Width); | |||
1628 | } | |||
1629 | ||||
1630 | /// Determine whether the specified value is known to be a | |||
1631 | /// constant on the specified edge. Return null if not. | |||
1632 | Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB, | |||
1633 | BasicBlock *ToBB, | |||
1634 | Instruction *CxtI) { | |||
1635 | Module *M = FromBB->getModule(); | |||
1636 | ValueLatticeElement Result = | |||
1637 | getImpl(PImpl, AC, M).getValueOnEdge(V, FromBB, ToBB, CxtI); | |||
1638 | ||||
1639 | if (Result.isConstant()) | |||
1640 | return Result.getConstant(); | |||
1641 | if (Result.isConstantRange()) { | |||
1642 | const ConstantRange &CR = Result.getConstantRange(); | |||
1643 | if (const APInt *SingleVal = CR.getSingleElement()) | |||
1644 | return ConstantInt::get(V->getContext(), *SingleVal); | |||
1645 | } | |||
1646 | return nullptr; | |||
1647 | } | |||
1648 | ||||
1649 | ConstantRange LazyValueInfo::getConstantRangeOnEdge(Value *V, | |||
1650 | BasicBlock *FromBB, | |||
1651 | BasicBlock *ToBB, | |||
1652 | Instruction *CxtI) { | |||
1653 | unsigned Width = V->getType()->getIntegerBitWidth(); | |||
1654 | Module *M = FromBB->getModule(); | |||
1655 | ValueLatticeElement Result = | |||
1656 | getImpl(PImpl, AC, M).getValueOnEdge(V, FromBB, ToBB, CxtI); | |||
1657 | ||||
1658 | if (Result.isUnknown()) | |||
1659 | return ConstantRange::getEmpty(Width); | |||
1660 | if (Result.isConstantRange()) | |||
1661 | return Result.getConstantRange(); | |||
1662 | // We represent ConstantInt constants as constant ranges but other kinds | |||
1663 | // of integer constants, i.e. ConstantExpr will be tagged as constants | |||
1664 | assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&(static_cast <bool> (!(Result.isConstant() && isa <ConstantInt>(Result.getConstant())) && "ConstantInt value must be represented as constantrange" ) ? void (0) : __assert_fail ("!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) && \"ConstantInt value must be represented as constantrange\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 1665, __extension__ __PRETTY_FUNCTION__ )) | |||
1665 | "ConstantInt value must be represented as constantrange")(static_cast <bool> (!(Result.isConstant() && isa <ConstantInt>(Result.getConstant())) && "ConstantInt value must be represented as constantrange" ) ? void (0) : __assert_fail ("!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) && \"ConstantInt value must be represented as constantrange\"" , "llvm/lib/Analysis/LazyValueInfo.cpp", 1665, __extension__ __PRETTY_FUNCTION__ )); | |||
1666 | return ConstantRange::getFull(Width); | |||
1667 | } | |||
1668 | ||||
1669 | static LazyValueInfo::Tristate | |||
1670 | getPredicateResult(unsigned Pred, Constant *C, const ValueLatticeElement &Val, | |||
1671 | const DataLayout &DL, TargetLibraryInfo *TLI) { | |||
1672 | // If we know the value is a constant, evaluate the conditional. | |||
1673 | Constant *Res = nullptr; | |||
1674 | if (Val.isConstant()) { | |||
1675 | Res = ConstantFoldCompareInstOperands(Pred, Val.getConstant(), C, DL, TLI); | |||
1676 | if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res)) | |||
1677 | return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True; | |||
1678 | return LazyValueInfo::Unknown; | |||
1679 | } | |||
1680 | ||||
1681 | if (Val.isConstantRange()) { | |||
1682 | ConstantInt *CI = dyn_cast<ConstantInt>(C); | |||
1683 | if (!CI) return LazyValueInfo::Unknown; | |||
1684 | ||||
1685 | const ConstantRange &CR = Val.getConstantRange(); | |||
1686 | if (Pred == ICmpInst::ICMP_EQ) { | |||
1687 | if (!CR.contains(CI->getValue())) | |||
1688 | return LazyValueInfo::False; | |||
1689 | ||||
1690 | if (CR.isSingleElement()) | |||
1691 | return LazyValueInfo::True; | |||
1692 | } else if (Pred == ICmpInst::ICMP_NE) { | |||
1693 | if (!CR.contains(CI->getValue())) | |||
1694 | return LazyValueInfo::True; | |||
1695 | ||||
1696 | if (CR.isSingleElement()) | |||
1697 | return LazyValueInfo::False; | |||
1698 | } else { | |||
1699 | // Handle more complex predicates. | |||
1700 | ConstantRange TrueValues = ConstantRange::makeExactICmpRegion( | |||
1701 | (ICmpInst::Predicate)Pred, CI->getValue()); | |||
1702 | if (TrueValues.contains(CR)) | |||
1703 | return LazyValueInfo::True; | |||
1704 | if (TrueValues.inverse().contains(CR)) | |||
1705 | return LazyValueInfo::False; | |||
1706 | } | |||
1707 | return LazyValueInfo::Unknown; | |||
1708 | } | |||
1709 | ||||
1710 | if (Val.isNotConstant()) { | |||
1711 | // If this is an equality comparison, we can try to fold it knowing that | |||
1712 | // "V != C1". | |||
1713 | if (Pred == ICmpInst::ICMP_EQ) { | |||
1714 | // !C1 == C -> false iff C1 == C. | |||
1715 | Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE, | |||
1716 | Val.getNotConstant(), C, DL, | |||
1717 | TLI); | |||
1718 | if (Res->isNullValue()) | |||
1719 | return LazyValueInfo::False; | |||
1720 | } else if (Pred == ICmpInst::ICMP_NE) { | |||
1721 | // !C1 != C -> true iff C1 == C. | |||
1722 | Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE, | |||
1723 | Val.getNotConstant(), C, DL, | |||
1724 | TLI); | |||
1725 | if (Res->isNullValue()) | |||
1726 | return LazyValueInfo::True; | |||
1727 | } | |||
1728 | return LazyValueInfo::Unknown; | |||
1729 | } | |||
1730 | ||||
1731 | return LazyValueInfo::Unknown; | |||
1732 | } | |||
1733 | ||||
1734 | /// Determine whether the specified value comparison with a constant is known to | |||
1735 | /// be true or false on the specified CFG edge. Pred is a CmpInst predicate. | |||
1736 | LazyValueInfo::Tristate | |||
1737 | LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, | |||
1738 | BasicBlock *FromBB, BasicBlock *ToBB, | |||
1739 | Instruction *CxtI) { | |||
1740 | Module *M = FromBB->getModule(); | |||
1741 | ValueLatticeElement Result = | |||
1742 | getImpl(PImpl, AC, M).getValueOnEdge(V, FromBB, ToBB, CxtI); | |||
1743 | ||||
1744 | return getPredicateResult(Pred, C, Result, M->getDataLayout(), TLI); | |||
1745 | } | |||
1746 | ||||
1747 | LazyValueInfo::Tristate | |||
1748 | LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C, | |||
1749 | Instruction *CxtI, bool UseBlockValue) { | |||
1750 | // Is or is not NonNull are common predicates being queried. If | |||
1751 | // isKnownNonZero can tell us the result of the predicate, we can | |||
1752 | // return it quickly. But this is only a fastpath, and falling | |||
1753 | // through would still be correct. | |||
1754 | Module *M = CxtI->getModule(); | |||
1755 | const DataLayout &DL = M->getDataLayout(); | |||
1756 | if (V->getType()->isPointerTy() && C->isNullValue() && | |||
1757 | isKnownNonZero(V->stripPointerCastsSameRepresentation(), DL)) { | |||
1758 | if (Pred == ICmpInst::ICMP_EQ) | |||
1759 | return LazyValueInfo::False; | |||
1760 | else if (Pred == ICmpInst::ICMP_NE) | |||
1761 | return LazyValueInfo::True; | |||
1762 | } | |||
1763 | ||||
1764 | ValueLatticeElement Result = UseBlockValue | |||
1765 | ? getImpl(PImpl, AC, M).getValueInBlock(V, CxtI->getParent(), CxtI) | |||
1766 | : getImpl(PImpl, AC, M).getValueAt(V, CxtI); | |||
1767 | Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI); | |||
1768 | if (Ret != Unknown) | |||
1769 | return Ret; | |||
1770 | ||||
1771 | // Note: The following bit of code is somewhat distinct from the rest of LVI; | |||
1772 | // LVI as a whole tries to compute a lattice value which is conservatively | |||
1773 | // correct at a given location. In this case, we have a predicate which we | |||
1774 | // weren't able to prove about the merged result, and we're pushing that | |||
1775 | // predicate back along each incoming edge to see if we can prove it | |||
1776 | // separately for each input. As a motivating example, consider: | |||
1777 | // bb1: | |||
1778 | // %v1 = ... ; constantrange<1, 5> | |||
1779 | // br label %merge | |||
1780 | // bb2: | |||
1781 | // %v2 = ... ; constantrange<10, 20> | |||
1782 | // br label %merge | |||
1783 | // merge: | |||
1784 | // %phi = phi [%v1, %v2] ; constantrange<1,20> | |||
1785 | // %pred = icmp eq i32 %phi, 8 | |||
1786 | // We can't tell from the lattice value for '%phi' that '%pred' is false | |||
1787 | // along each path, but by checking the predicate over each input separately, | |||
1788 | // we can. | |||
1789 | // We limit the search to one step backwards from the current BB and value. | |||
1790 | // We could consider extending this to search further backwards through the | |||
1791 | // CFG and/or value graph, but there are non-obvious compile time vs quality | |||
1792 | // tradeoffs. | |||
1793 | BasicBlock *BB = CxtI->getParent(); | |||
1794 | ||||
1795 | // Function entry or an unreachable block. Bail to avoid confusing | |||
1796 | // analysis below. | |||
1797 | pred_iterator PI = pred_begin(BB), PE = pred_end(BB); | |||
1798 | if (PI == PE) | |||
1799 | return Unknown; | |||
1800 | ||||
1801 | // If V is a PHI node in the same block as the context, we need to ask | |||
1802 | // questions about the predicate as applied to the incoming value along | |||
1803 | // each edge. This is useful for eliminating cases where the predicate is | |||
1804 | // known along all incoming edges. | |||
1805 | if (auto *PHI = dyn_cast<PHINode>(V)) | |||
1806 | if (PHI->getParent() == BB) { | |||
1807 | Tristate Baseline = Unknown; | |||
1808 | for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) { | |||
1809 | Value *Incoming = PHI->getIncomingValue(i); | |||
1810 | BasicBlock *PredBB = PHI->getIncomingBlock(i); | |||
1811 | // Note that PredBB may be BB itself. | |||
1812 | Tristate Result = | |||
1813 | getPredicateOnEdge(Pred, Incoming, C, PredBB, BB, CxtI); | |||
1814 | ||||
1815 | // Keep going as long as we've seen a consistent known result for | |||
1816 | // all inputs. | |||
1817 | Baseline = (i == 0) ? Result /* First iteration */ | |||
1818 | : (Baseline == Result ? Baseline | |||
1819 | : Unknown); /* All others */ | |||
1820 | if (Baseline == Unknown) | |||
1821 | break; | |||
1822 | } | |||
1823 | if (Baseline != Unknown) | |||
1824 | return Baseline; | |||
1825 | } | |||
1826 | ||||
1827 | // For a comparison where the V is outside this block, it's possible | |||
1828 | // that we've branched on it before. Look to see if the value is known | |||
1829 | // on all incoming edges. | |||
1830 | if (!isa<Instruction>(V) || cast<Instruction>(V)->getParent() != BB) { | |||
1831 | // For predecessor edge, determine if the comparison is true or false | |||
1832 | // on that edge. If they're all true or all false, we can conclude | |||
1833 | // the value of the comparison in this block. | |||
1834 | Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI); | |||
1835 | if (Baseline != Unknown) { | |||
1836 | // Check that all remaining incoming values match the first one. | |||
1837 | while (++PI != PE) { | |||
1838 | Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI); | |||
1839 | if (Ret != Baseline) | |||
1840 | break; | |||
1841 | } | |||
1842 | // If we terminated early, then one of the values didn't match. | |||
1843 | if (PI == PE) { | |||
1844 | return Baseline; | |||
1845 | } | |||
1846 | } | |||
1847 | } | |||
1848 | ||||
1849 | return Unknown; | |||
1850 | } | |||
1851 | ||||
1852 | LazyValueInfo::Tristate LazyValueInfo::getPredicateAt(unsigned P, Value *LHS, | |||
1853 | Value *RHS, | |||
1854 | Instruction *CxtI, | |||
1855 | bool UseBlockValue) { | |||
1856 | CmpInst::Predicate Pred = (CmpInst::Predicate)P; | |||
1857 | ||||
1858 | if (auto *C = dyn_cast<Constant>(RHS)) | |||
1859 | return getPredicateAt(P, LHS, C, CxtI, UseBlockValue); | |||
1860 | if (auto *C = dyn_cast<Constant>(LHS)) | |||
1861 | return getPredicateAt(CmpInst::getSwappedPredicate(Pred), RHS, C, CxtI, | |||
1862 | UseBlockValue); | |||
1863 | ||||
1864 | // Got two non-Constant values. Try to determine the comparison results based | |||
1865 | // on the block values of the two operands, e.g. because they have | |||
1866 | // non-overlapping ranges. | |||
1867 | if (UseBlockValue) { | |||
1868 | Module *M = CxtI->getModule(); | |||
1869 | ValueLatticeElement L = | |||
1870 | getImpl(PImpl, AC, M).getValueInBlock(LHS, CxtI->getParent(), CxtI); | |||
1871 | if (L.isOverdefined()) | |||
1872 | return LazyValueInfo::Unknown; | |||
1873 | ||||
1874 | ValueLatticeElement R = | |||
1875 | getImpl(PImpl, AC, M).getValueInBlock(RHS, CxtI->getParent(), CxtI); | |||
1876 | Type *Ty = CmpInst::makeCmpResultType(LHS->getType()); | |||
1877 | if (Constant *Res = L.getCompare((CmpInst::Predicate)P, Ty, R, | |||
1878 | M->getDataLayout())) { | |||
1879 | if (Res->isNullValue()) | |||
1880 | return LazyValueInfo::False; | |||
1881 | if (Res->isOneValue()) | |||
1882 | return LazyValueInfo::True; | |||
1883 | } | |||
1884 | } | |||
1885 | return LazyValueInfo::Unknown; | |||
1886 | } | |||
1887 | ||||
1888 | void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, | |||
1889 | BasicBlock *NewSucc) { | |||
1890 | if (PImpl) { | |||
1891 | getImpl(PImpl, AC, PredBB->getModule()) | |||
1892 | .threadEdge(PredBB, OldSucc, NewSucc); | |||
1893 | } | |||
1894 | } | |||
1895 | ||||
1896 | void LazyValueInfo::eraseBlock(BasicBlock *BB) { | |||
1897 | if (PImpl) { | |||
1898 | getImpl(PImpl, AC, BB->getModule()).eraseBlock(BB); | |||
1899 | } | |||
1900 | } | |||
1901 | ||||
1902 | void LazyValueInfo::clear(const Module *M) { | |||
1903 | if (PImpl) { | |||
1904 | getImpl(PImpl, AC, M).clear(); | |||
1905 | } | |||
1906 | } | |||
1907 | ||||
1908 | void LazyValueInfo::printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) { | |||
1909 | if (PImpl) { | |||
1910 | getImpl(PImpl, AC, F.getParent()).printLVI(F, DTree, OS); | |||
1911 | } | |||
1912 | } | |||
1913 | ||||
1914 | // Print the LVI for the function arguments at the start of each basic block. | |||
1915 | void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot( | |||
1916 | const BasicBlock *BB, formatted_raw_ostream &OS) { | |||
1917 | // Find if there are latticevalues defined for arguments of the function. | |||
1918 | auto *F = BB->getParent(); | |||
1919 | for (const auto &Arg : F->args()) { | |||
1920 | ValueLatticeElement Result = LVIImpl->getValueInBlock( | |||
1921 | const_cast<Argument *>(&Arg), const_cast<BasicBlock *>(BB)); | |||
1922 | if (Result.isUnknown()) | |||
1923 | continue; | |||
1924 | OS << "; LatticeVal for: '" << Arg << "' is: " << Result << "\n"; | |||
1925 | } | |||
1926 | } | |||
1927 | ||||
1928 | // This function prints the LVI analysis for the instruction I at the beginning | |||
1929 | // of various basic blocks. It relies on calculated values that are stored in | |||
1930 | // the LazyValueInfoCache, and in the absence of cached values, recalculate the | |||
1931 | // LazyValueInfo for `I`, and print that info. | |||
1932 | void LazyValueInfoAnnotatedWriter::emitInstructionAnnot( | |||
1933 | const Instruction *I, formatted_raw_ostream &OS) { | |||
1934 | ||||
1935 | auto *ParentBB = I->getParent(); | |||
1936 | SmallPtrSet<const BasicBlock*, 16> BlocksContainingLVI; | |||
1937 | // We can generate (solve) LVI values only for blocks that are dominated by | |||
1938 | // the I's parent. However, to avoid generating LVI for all dominating blocks, | |||
1939 | // that contain redundant/uninteresting information, we print LVI for | |||
1940 | // blocks that may use this LVI information (such as immediate successor | |||
1941 | // blocks, and blocks that contain uses of `I`). | |||
1942 | auto printResult = [&](const BasicBlock *BB) { | |||
1943 | if (!BlocksContainingLVI.insert(BB).second) | |||
1944 | return; | |||
1945 | ValueLatticeElement Result = LVIImpl->getValueInBlock( | |||
1946 | const_cast<Instruction *>(I), const_cast<BasicBlock *>(BB)); | |||
1947 | OS << "; LatticeVal for: '" << *I << "' in BB: '"; | |||
1948 | BB->printAsOperand(OS, false); | |||
1949 | OS << "' is: " << Result << "\n"; | |||
1950 | }; | |||
1951 | ||||
1952 | printResult(ParentBB); | |||
1953 | // Print the LVI analysis results for the immediate successor blocks, that | |||
1954 | // are dominated by `ParentBB`. | |||
1955 | for (const auto *BBSucc : successors(ParentBB)) | |||
1956 | if (DT.dominates(ParentBB, BBSucc)) | |||
1957 | printResult(BBSucc); | |||
1958 | ||||
1959 | // Print LVI in blocks where `I` is used. | |||
1960 | for (const auto *U : I->users()) | |||
1961 | if (auto *UseI = dyn_cast<Instruction>(U)) | |||
1962 | if (!isa<PHINode>(UseI) || DT.dominates(ParentBB, UseI->getParent())) | |||
1963 | printResult(UseI->getParent()); | |||
1964 | ||||
1965 | } | |||
1966 | ||||
1967 | namespace { | |||
1968 | // Printer class for LazyValueInfo results. | |||
1969 | class LazyValueInfoPrinter : public FunctionPass { | |||
1970 | public: | |||
1971 | static char ID; // Pass identification, replacement for typeid | |||
1972 | LazyValueInfoPrinter() : FunctionPass(ID) { | |||
1973 | initializeLazyValueInfoPrinterPass(*PassRegistry::getPassRegistry()); | |||
1974 | } | |||
1975 | ||||
1976 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |||
1977 | AU.setPreservesAll(); | |||
1978 | AU.addRequired<LazyValueInfoWrapperPass>(); | |||
1979 | AU.addRequired<DominatorTreeWrapperPass>(); | |||
1980 | } | |||
1981 | ||||
1982 | // Get the mandatory dominator tree analysis and pass this in to the | |||
1983 | // LVIPrinter. We cannot rely on the LVI's DT, since it's optional. | |||
1984 | bool runOnFunction(Function &F) override { | |||
1985 | dbgs() << "LVI for function '" << F.getName() << "':\n"; | |||
1986 | auto &LVI = getAnalysis<LazyValueInfoWrapperPass>().getLVI(); | |||
1987 | auto &DTree = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); | |||
1988 | LVI.printLVI(F, DTree, dbgs()); | |||
1989 | return false; | |||
1990 | } | |||
1991 | }; | |||
1992 | } | |||
1993 | ||||
1994 | char LazyValueInfoPrinter::ID = 0; | |||
1995 | INITIALIZE_PASS_BEGIN(LazyValueInfoPrinter, "print-lazy-value-info",static void *initializeLazyValueInfoPrinterPassOnce(PassRegistry &Registry) { | |||
1996 | "Lazy Value Info Printer Pass", false, false)static void *initializeLazyValueInfoPrinterPassOnce(PassRegistry &Registry) { | |||
1997 | INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)initializeLazyValueInfoWrapperPassPass(Registry); | |||
1998 | INITIALIZE_PASS_END(LazyValueInfoPrinter, "print-lazy-value-info",PassInfo *PI = new PassInfo( "Lazy Value Info Printer Pass", "print-lazy-value-info" , &LazyValueInfoPrinter::ID, PassInfo::NormalCtor_t(callDefaultCtor <LazyValueInfoPrinter>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeLazyValueInfoPrinterPassFlag ; void llvm::initializeLazyValueInfoPrinterPass(PassRegistry & Registry) { llvm::call_once(InitializeLazyValueInfoPrinterPassFlag , initializeLazyValueInfoPrinterPassOnce, std::ref(Registry)) ; } | |||
1999 | "Lazy Value Info Printer Pass", false, false)PassInfo *PI = new PassInfo( "Lazy Value Info Printer Pass", "print-lazy-value-info" , &LazyValueInfoPrinter::ID, PassInfo::NormalCtor_t(callDefaultCtor <LazyValueInfoPrinter>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeLazyValueInfoPrinterPassFlag ; void llvm::initializeLazyValueInfoPrinterPass(PassRegistry & Registry) { llvm::call_once(InitializeLazyValueInfoPrinterPassFlag , initializeLazyValueInfoPrinterPassOnce, std::ref(Registry)) ; } |
1 | //===- ValueLattice.h - Value constraint analysis ---------------*- 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 | #ifndef LLVM_ANALYSIS_VALUELATTICE_H | |||
10 | #define LLVM_ANALYSIS_VALUELATTICE_H | |||
11 | ||||
12 | #include "llvm/IR/Constants.h" | |||
13 | #include "llvm/IR/ConstantRange.h" | |||
14 | #include "llvm/IR/Instructions.h" | |||
15 | ||||
16 | //===----------------------------------------------------------------------===// | |||
17 | // ValueLatticeElement | |||
18 | //===----------------------------------------------------------------------===// | |||
19 | ||||
20 | namespace llvm { | |||
21 | ||||
22 | class Constant; | |||
23 | ||||
24 | /// This class represents lattice values for constants. | |||
25 | /// | |||
26 | /// FIXME: This is basically just for bringup, this can be made a lot more rich | |||
27 | /// in the future. | |||
28 | /// | |||
29 | class ValueLatticeElement { | |||
30 | enum ValueLatticeElementTy { | |||
31 | /// This Value has no known value yet. As a result, this implies the | |||
32 | /// producing instruction is dead. Caution: We use this as the starting | |||
33 | /// state in our local meet rules. In this usage, it's taken to mean | |||
34 | /// "nothing known yet". | |||
35 | /// Transition to any other state allowed. | |||
36 | unknown, | |||
37 | ||||
38 | /// This Value is an UndefValue constant or produces undef. Undefined values | |||
39 | /// can be merged with constants (or single element constant ranges), | |||
40 | /// assuming all uses of the result will be replaced. | |||
41 | /// Transition allowed to the following states: | |||
42 | /// constant | |||
43 | /// constantrange_including_undef | |||
44 | /// overdefined | |||
45 | undef, | |||
46 | ||||
47 | /// This Value has a specific constant value. The constant cannot be undef. | |||
48 | /// (For constant integers, constantrange is used instead. Integer typed | |||
49 | /// constantexprs can appear as constant.) Note that the constant state | |||
50 | /// can be reached by merging undef & constant states. | |||
51 | /// Transition allowed to the following states: | |||
52 | /// overdefined | |||
53 | constant, | |||
54 | ||||
55 | /// This Value is known to not have the specified value. (For constant | |||
56 | /// integers, constantrange is used instead. As above, integer typed | |||
57 | /// constantexprs can appear here.) | |||
58 | /// Transition allowed to the following states: | |||
59 | /// overdefined | |||
60 | notconstant, | |||
61 | ||||
62 | /// The Value falls within this range. (Used only for integer typed values.) | |||
63 | /// Transition allowed to the following states: | |||
64 | /// constantrange (new range must be a superset of the existing range) | |||
65 | /// constantrange_including_undef | |||
66 | /// overdefined | |||
67 | constantrange, | |||
68 | ||||
69 | /// This Value falls within this range, but also may be undef. | |||
70 | /// Merging it with other constant ranges results in | |||
71 | /// constantrange_including_undef. | |||
72 | /// Transition allowed to the following states: | |||
73 | /// overdefined | |||
74 | constantrange_including_undef, | |||
75 | ||||
76 | /// We can not precisely model the dynamic values this value might take. | |||
77 | /// No transitions are allowed after reaching overdefined. | |||
78 | overdefined, | |||
79 | }; | |||
80 | ||||
81 | ValueLatticeElementTy Tag : 8; | |||
82 | /// Number of times a constant range has been extended with widening enabled. | |||
83 | unsigned NumRangeExtensions : 8; | |||
84 | ||||
85 | /// The union either stores a pointer to a constant or a constant range, | |||
86 | /// associated to the lattice element. We have to ensure that Range is | |||
87 | /// initialized or destroyed when changing state to or from constantrange. | |||
88 | union { | |||
89 | Constant *ConstVal; | |||
90 | ConstantRange Range; | |||
91 | }; | |||
92 | ||||
93 | /// Destroy contents of lattice value, without destructing the object. | |||
94 | void destroy() { | |||
95 | switch (Tag) { | |||
96 | case overdefined: | |||
97 | case unknown: | |||
98 | case undef: | |||
99 | case constant: | |||
100 | case notconstant: | |||
101 | break; | |||
102 | case constantrange_including_undef: | |||
103 | case constantrange: | |||
104 | Range.~ConstantRange(); | |||
105 | break; | |||
106 | }; | |||
107 | } | |||
108 | ||||
109 | public: | |||
110 | /// Struct to control some aspects related to merging constant ranges. | |||
111 | struct MergeOptions { | |||
112 | /// The merge value may include undef. | |||
113 | bool MayIncludeUndef; | |||
114 | ||||
115 | /// Handle repeatedly extending a range by going to overdefined after a | |||
116 | /// number of steps. | |||
117 | bool CheckWiden; | |||
118 | ||||
119 | /// The number of allowed widening steps (including setting the range | |||
120 | /// initially). | |||
121 | unsigned MaxWidenSteps; | |||
122 | ||||
123 | MergeOptions() : MergeOptions(false, false) {} | |||
124 | ||||
125 | MergeOptions(bool MayIncludeUndef, bool CheckWiden, | |||
126 | unsigned MaxWidenSteps = 1) | |||
127 | : MayIncludeUndef(MayIncludeUndef), CheckWiden(CheckWiden), | |||
128 | MaxWidenSteps(MaxWidenSteps) {} | |||
129 | ||||
130 | MergeOptions &setMayIncludeUndef(bool V = true) { | |||
131 | MayIncludeUndef = V; | |||
132 | return *this; | |||
133 | } | |||
134 | ||||
135 | MergeOptions &setCheckWiden(bool V = true) { | |||
136 | CheckWiden = V; | |||
137 | return *this; | |||
138 | } | |||
139 | ||||
140 | MergeOptions &setMaxWidenSteps(unsigned Steps = 1) { | |||
141 | CheckWiden = true; | |||
142 | MaxWidenSteps = Steps; | |||
143 | return *this; | |||
144 | } | |||
145 | }; | |||
146 | ||||
147 | // ConstVal and Range are initialized on-demand. | |||
148 | ValueLatticeElement() : Tag(unknown), NumRangeExtensions(0) {} | |||
149 | ||||
150 | ~ValueLatticeElement() { destroy(); } | |||
151 | ||||
152 | ValueLatticeElement(const ValueLatticeElement &Other) | |||
153 | : Tag(Other.Tag), NumRangeExtensions(0) { | |||
154 | switch (Other.Tag) { | |||
155 | case constantrange: | |||
156 | case constantrange_including_undef: | |||
157 | new (&Range) ConstantRange(Other.Range); | |||
158 | NumRangeExtensions = Other.NumRangeExtensions; | |||
159 | break; | |||
160 | case constant: | |||
161 | case notconstant: | |||
162 | ConstVal = Other.ConstVal; | |||
163 | break; | |||
164 | case overdefined: | |||
165 | case unknown: | |||
166 | case undef: | |||
167 | break; | |||
168 | } | |||
169 | } | |||
170 | ||||
171 | ValueLatticeElement(ValueLatticeElement &&Other) | |||
172 | : Tag(Other.Tag), NumRangeExtensions(0) { | |||
173 | switch (Other.Tag) { | |||
174 | case constantrange: | |||
175 | case constantrange_including_undef: | |||
176 | new (&Range) ConstantRange(std::move(Other.Range)); | |||
177 | NumRangeExtensions = Other.NumRangeExtensions; | |||
178 | break; | |||
179 | case constant: | |||
180 | case notconstant: | |||
181 | ConstVal = Other.ConstVal; | |||
| ||||
182 | break; | |||
183 | case overdefined: | |||
184 | case unknown: | |||
185 | case undef: | |||
186 | break; | |||
187 | } | |||
188 | Other.Tag = unknown; | |||
189 | } | |||
190 | ||||
191 | ValueLatticeElement &operator=(const ValueLatticeElement &Other) { | |||
192 | destroy(); | |||
193 | new (this) ValueLatticeElement(Other); | |||
194 | return *this; | |||
195 | } | |||
196 | ||||
197 | ValueLatticeElement &operator=(ValueLatticeElement &&Other) { | |||
198 | destroy(); | |||
199 | new (this) ValueLatticeElement(std::move(Other)); | |||
200 | return *this; | |||
201 | } | |||
202 | ||||
203 | static ValueLatticeElement get(Constant *C) { | |||
204 | ValueLatticeElement Res; | |||
205 | if (isa<UndefValue>(C)) | |||
206 | Res.markUndef(); | |||
207 | else | |||
208 | Res.markConstant(C); | |||
209 | return Res; | |||
210 | } | |||
211 | static ValueLatticeElement getNot(Constant *C) { | |||
212 | ValueLatticeElement Res; | |||
213 | assert(!isa<UndefValue>(C) && "!= undef is not supported")(static_cast <bool> (!isa<UndefValue>(C) && "!= undef is not supported") ? void (0) : __assert_fail ("!isa<UndefValue>(C) && \"!= undef is not supported\"" , "llvm/include/llvm/Analysis/ValueLattice.h", 213, __extension__ __PRETTY_FUNCTION__)); | |||
214 | Res.markNotConstant(C); | |||
215 | return Res; | |||
216 | } | |||
217 | static ValueLatticeElement getRange(ConstantRange CR, | |||
218 | bool MayIncludeUndef = false) { | |||
219 | if (CR.isFullSet()) | |||
220 | return getOverdefined(); | |||
221 | ||||
222 | if (CR.isEmptySet()) { | |||
223 | ValueLatticeElement Res; | |||
224 | if (MayIncludeUndef) | |||
225 | Res.markUndef(); | |||
226 | return Res; | |||
227 | } | |||
228 | ||||
229 | ValueLatticeElement Res; | |||
230 | Res.markConstantRange(std::move(CR), | |||
231 | MergeOptions().setMayIncludeUndef(MayIncludeUndef)); | |||
232 | return Res; | |||
233 | } | |||
234 | static ValueLatticeElement getOverdefined() { | |||
235 | ValueLatticeElement Res; | |||
236 | Res.markOverdefined(); | |||
237 | return Res; | |||
238 | } | |||
239 | ||||
240 | bool isUndef() const { return Tag == undef; } | |||
241 | bool isUnknown() const { return Tag == unknown; } | |||
242 | bool isUnknownOrUndef() const { return Tag == unknown || Tag == undef; } | |||
243 | bool isConstant() const { return Tag == constant; } | |||
244 | bool isNotConstant() const { return Tag == notconstant; } | |||
245 | bool isConstantRangeIncludingUndef() const { | |||
246 | return Tag == constantrange_including_undef; | |||
247 | } | |||
248 | /// Returns true if this value is a constant range. Use \p UndefAllowed to | |||
249 | /// exclude non-singleton constant ranges that may also be undef. Note that | |||
250 | /// this function also returns true if the range may include undef, but only | |||
251 | /// contains a single element. In that case, it can be replaced by a constant. | |||
252 | bool isConstantRange(bool UndefAllowed = true) const { | |||
253 | return Tag == constantrange || (Tag == constantrange_including_undef && | |||
254 | (UndefAllowed || Range.isSingleElement())); | |||
255 | } | |||
256 | bool isOverdefined() const { return Tag == overdefined; } | |||
257 | ||||
258 | Constant *getConstant() const { | |||
259 | assert(isConstant() && "Cannot get the constant of a non-constant!")(static_cast <bool> (isConstant() && "Cannot get the constant of a non-constant!" ) ? void (0) : __assert_fail ("isConstant() && \"Cannot get the constant of a non-constant!\"" , "llvm/include/llvm/Analysis/ValueLattice.h", 259, __extension__ __PRETTY_FUNCTION__)); | |||
260 | return ConstVal; | |||
261 | } | |||
262 | ||||
263 | Constant *getNotConstant() const { | |||
264 | assert(isNotConstant() && "Cannot get the constant of a non-notconstant!")(static_cast <bool> (isNotConstant() && "Cannot get the constant of a non-notconstant!" ) ? void (0) : __assert_fail ("isNotConstant() && \"Cannot get the constant of a non-notconstant!\"" , "llvm/include/llvm/Analysis/ValueLattice.h", 264, __extension__ __PRETTY_FUNCTION__)); | |||
265 | return ConstVal; | |||
266 | } | |||
267 | ||||
268 | /// Returns the constant range for this value. Use \p UndefAllowed to exclude | |||
269 | /// non-singleton constant ranges that may also be undef. Note that this | |||
270 | /// function also returns a range if the range may include undef, but only | |||
271 | /// contains a single element. In that case, it can be replaced by a constant. | |||
272 | const ConstantRange &getConstantRange(bool UndefAllowed = true) const { | |||
273 | assert(isConstantRange(UndefAllowed) &&(static_cast <bool> (isConstantRange(UndefAllowed) && "Cannot get the constant-range of a non-constant-range!") ? void (0) : __assert_fail ("isConstantRange(UndefAllowed) && \"Cannot get the constant-range of a non-constant-range!\"" , "llvm/include/llvm/Analysis/ValueLattice.h", 274, __extension__ __PRETTY_FUNCTION__)) | |||
274 | "Cannot get the constant-range of a non-constant-range!")(static_cast <bool> (isConstantRange(UndefAllowed) && "Cannot get the constant-range of a non-constant-range!") ? void (0) : __assert_fail ("isConstantRange(UndefAllowed) && \"Cannot get the constant-range of a non-constant-range!\"" , "llvm/include/llvm/Analysis/ValueLattice.h", 274, __extension__ __PRETTY_FUNCTION__)); | |||
275 | return Range; | |||
276 | } | |||
277 | ||||
278 | Optional<APInt> asConstantInteger() const { | |||
279 | if (isConstant() && isa<ConstantInt>(getConstant())) { | |||
280 | return cast<ConstantInt>(getConstant())->getValue(); | |||
281 | } else if (isConstantRange() && getConstantRange().isSingleElement()) { | |||
282 | return *getConstantRange().getSingleElement(); | |||
283 | } | |||
284 | return std::nullopt; | |||
285 | } | |||
286 | ||||
287 | bool markOverdefined() { | |||
288 | if (isOverdefined()) | |||
289 | return false; | |||
290 | destroy(); | |||
291 | Tag = overdefined; | |||
292 | return true; | |||
293 | } | |||
294 | ||||
295 | bool markUndef() { | |||
296 | if (isUndef()) | |||
297 | return false; | |||
298 | ||||
299 | assert(isUnknown())(static_cast <bool> (isUnknown()) ? void (0) : __assert_fail ("isUnknown()", "llvm/include/llvm/Analysis/ValueLattice.h", 299, __extension__ __PRETTY_FUNCTION__)); | |||
300 | Tag = undef; | |||
301 | return true; | |||
302 | } | |||
303 | ||||
304 | bool markConstant(Constant *V, bool MayIncludeUndef = false) { | |||
305 | if (isa<UndefValue>(V)) | |||
306 | return markUndef(); | |||
307 | ||||
308 | if (isConstant()) { | |||
309 | assert(getConstant() == V && "Marking constant with different value")(static_cast <bool> (getConstant() == V && "Marking constant with different value" ) ? void (0) : __assert_fail ("getConstant() == V && \"Marking constant with different value\"" , "llvm/include/llvm/Analysis/ValueLattice.h", 309, __extension__ __PRETTY_FUNCTION__)); | |||
310 | return false; | |||
311 | } | |||
312 | ||||
313 | if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) | |||
314 | return markConstantRange( | |||
315 | ConstantRange(CI->getValue()), | |||
316 | MergeOptions().setMayIncludeUndef(MayIncludeUndef)); | |||
317 | ||||
318 | assert(isUnknown() || isUndef())(static_cast <bool> (isUnknown() || isUndef()) ? void ( 0) : __assert_fail ("isUnknown() || isUndef()", "llvm/include/llvm/Analysis/ValueLattice.h" , 318, __extension__ __PRETTY_FUNCTION__)); | |||
319 | Tag = constant; | |||
320 | ConstVal = V; | |||
321 | return true; | |||
322 | } | |||
323 | ||||
324 | bool markNotConstant(Constant *V) { | |||
325 | assert(V && "Marking constant with NULL")(static_cast <bool> (V && "Marking constant with NULL" ) ? void (0) : __assert_fail ("V && \"Marking constant with NULL\"" , "llvm/include/llvm/Analysis/ValueLattice.h", 325, __extension__ __PRETTY_FUNCTION__)); | |||
326 | if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) | |||
327 | return markConstantRange( | |||
328 | ConstantRange(CI->getValue() + 1, CI->getValue())); | |||
329 | ||||
330 | if (isa<UndefValue>(V)) | |||
331 | return false; | |||
332 | ||||
333 | if (isNotConstant()) { | |||
334 | assert(getNotConstant() == V && "Marking !constant with different value")(static_cast <bool> (getNotConstant() == V && "Marking !constant with different value" ) ? void (0) : __assert_fail ("getNotConstant() == V && \"Marking !constant with different value\"" , "llvm/include/llvm/Analysis/ValueLattice.h", 334, __extension__ __PRETTY_FUNCTION__)); | |||
335 | return false; | |||
336 | } | |||
337 | ||||
338 | assert(isUnknown())(static_cast <bool> (isUnknown()) ? void (0) : __assert_fail ("isUnknown()", "llvm/include/llvm/Analysis/ValueLattice.h", 338, __extension__ __PRETTY_FUNCTION__)); | |||
339 | Tag = notconstant; | |||
340 | ConstVal = V; | |||
341 | return true; | |||
342 | } | |||
343 | ||||
344 | /// Mark the object as constant range with \p NewR. If the object is already a | |||
345 | /// constant range, nothing changes if the existing range is equal to \p | |||
346 | /// NewR and the tag. Otherwise \p NewR must be a superset of the existing | |||
347 | /// range or the object must be undef. The tag is set to | |||
348 | /// constant_range_including_undef if either the existing value or the new | |||
349 | /// range may include undef. | |||
350 | bool markConstantRange(ConstantRange NewR, | |||
351 | MergeOptions Opts = MergeOptions()) { | |||
352 | assert(!NewR.isEmptySet() && "should only be called for non-empty sets")(static_cast <bool> (!NewR.isEmptySet() && "should only be called for non-empty sets" ) ? void (0) : __assert_fail ("!NewR.isEmptySet() && \"should only be called for non-empty sets\"" , "llvm/include/llvm/Analysis/ValueLattice.h", 352, __extension__ __PRETTY_FUNCTION__)); | |||
353 | ||||
354 | if (NewR.isFullSet()) | |||
355 | return markOverdefined(); | |||
356 | ||||
357 | ValueLatticeElementTy OldTag = Tag; | |||
358 | ValueLatticeElementTy NewTag = | |||
359 | (isUndef() || isConstantRangeIncludingUndef() || Opts.MayIncludeUndef) | |||
360 | ? constantrange_including_undef | |||
361 | : constantrange; | |||
362 | if (isConstantRange()) { | |||
363 | Tag = NewTag; | |||
364 | if (getConstantRange() == NewR) | |||
365 | return Tag != OldTag; | |||
366 | ||||
367 | // Simple form of widening. If a range is extended multiple times, go to | |||
368 | // overdefined. | |||
369 | if (Opts.CheckWiden && ++NumRangeExtensions > Opts.MaxWidenSteps) | |||
370 | return markOverdefined(); | |||
371 | ||||
372 | assert(NewR.contains(getConstantRange()) &&(static_cast <bool> (NewR.contains(getConstantRange()) && "Existing range must be a subset of NewR") ? void (0) : __assert_fail ("NewR.contains(getConstantRange()) && \"Existing range must be a subset of NewR\"" , "llvm/include/llvm/Analysis/ValueLattice.h", 373, __extension__ __PRETTY_FUNCTION__)) | |||
373 | "Existing range must be a subset of NewR")(static_cast <bool> (NewR.contains(getConstantRange()) && "Existing range must be a subset of NewR") ? void (0) : __assert_fail ("NewR.contains(getConstantRange()) && \"Existing range must be a subset of NewR\"" , "llvm/include/llvm/Analysis/ValueLattice.h", 373, __extension__ __PRETTY_FUNCTION__)); | |||
374 | Range = std::move(NewR); | |||
375 | return true; | |||
376 | } | |||
377 | ||||
378 | assert(isUnknown() || isUndef())(static_cast <bool> (isUnknown() || isUndef()) ? void ( 0) : __assert_fail ("isUnknown() || isUndef()", "llvm/include/llvm/Analysis/ValueLattice.h" , 378, __extension__ __PRETTY_FUNCTION__)); | |||
379 | ||||
380 | NumRangeExtensions = 0; | |||
381 | Tag = NewTag; | |||
382 | new (&Range) ConstantRange(std::move(NewR)); | |||
383 | return true; | |||
384 | } | |||
385 | ||||
386 | /// Updates this object to approximate both this object and RHS. Returns | |||
387 | /// true if this object has been changed. | |||
388 | bool mergeIn(const ValueLatticeElement &RHS, | |||
389 | MergeOptions Opts = MergeOptions()) { | |||
390 | if (RHS.isUnknown() || isOverdefined()) | |||
391 | return false; | |||
392 | if (RHS.isOverdefined()) { | |||
393 | markOverdefined(); | |||
394 | return true; | |||
395 | } | |||
396 | ||||
397 | if (isUndef()) { | |||
398 | assert(!RHS.isUnknown())(static_cast <bool> (!RHS.isUnknown()) ? void (0) : __assert_fail ("!RHS.isUnknown()", "llvm/include/llvm/Analysis/ValueLattice.h" , 398, __extension__ __PRETTY_FUNCTION__)); | |||
399 | if (RHS.isUndef()) | |||
400 | return false; | |||
401 | if (RHS.isConstant()) | |||
402 | return markConstant(RHS.getConstant(), true); | |||
403 | if (RHS.isConstantRange()) | |||
404 | return markConstantRange(RHS.getConstantRange(true), | |||
405 | Opts.setMayIncludeUndef()); | |||
406 | return markOverdefined(); | |||
407 | } | |||
408 | ||||
409 | if (isUnknown()) { | |||
410 | assert(!RHS.isUnknown() && "Unknow RHS should be handled earlier")(static_cast <bool> (!RHS.isUnknown() && "Unknow RHS should be handled earlier" ) ? void (0) : __assert_fail ("!RHS.isUnknown() && \"Unknow RHS should be handled earlier\"" , "llvm/include/llvm/Analysis/ValueLattice.h", 410, __extension__ __PRETTY_FUNCTION__)); | |||
411 | *this = RHS; | |||
412 | return true; | |||
413 | } | |||
414 | ||||
415 | if (isConstant()) { | |||
416 | if (RHS.isConstant() && getConstant() == RHS.getConstant()) | |||
417 | return false; | |||
418 | if (RHS.isUndef()) | |||
419 | return false; | |||
420 | markOverdefined(); | |||
421 | return true; | |||
422 | } | |||
423 | ||||
424 | if (isNotConstant()) { | |||
425 | if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant()) | |||
426 | return false; | |||
427 | markOverdefined(); | |||
428 | return true; | |||
429 | } | |||
430 | ||||
431 | auto OldTag = Tag; | |||
432 | assert(isConstantRange() && "New ValueLattice type?")(static_cast <bool> (isConstantRange() && "New ValueLattice type?" ) ? void (0) : __assert_fail ("isConstantRange() && \"New ValueLattice type?\"" , "llvm/include/llvm/Analysis/ValueLattice.h", 432, __extension__ __PRETTY_FUNCTION__)); | |||
433 | if (RHS.isUndef()) { | |||
434 | Tag = constantrange_including_undef; | |||
435 | return OldTag != Tag; | |||
436 | } | |||
437 | ||||
438 | if (!RHS.isConstantRange()) { | |||
439 | // We can get here if we've encountered a constantexpr of integer type | |||
440 | // and merge it with a constantrange. | |||
441 | markOverdefined(); | |||
442 | return true; | |||
443 | } | |||
444 | ||||
445 | ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange()); | |||
446 | return markConstantRange( | |||
447 | std::move(NewR), | |||
448 | Opts.setMayIncludeUndef(RHS.isConstantRangeIncludingUndef())); | |||
449 | } | |||
450 | ||||
451 | // Compares this symbolic value with Other using Pred and returns either | |||
452 | /// true, false or undef constants, or nullptr if the comparison cannot be | |||
453 | /// evaluated. | |||
454 | Constant *getCompare(CmpInst::Predicate Pred, Type *Ty, | |||
455 | const ValueLatticeElement &Other, | |||
456 | const DataLayout &DL) const; | |||
457 | ||||
458 | unsigned getNumRangeExtensions() const { return NumRangeExtensions; } | |||
459 | void setNumRangeExtensions(unsigned N) { NumRangeExtensions = N; } | |||
460 | }; | |||
461 | ||||
462 | static_assert(sizeof(ValueLatticeElement) <= 40, | |||
463 | "size of ValueLatticeElement changed unexpectedly"); | |||
464 | ||||
465 | raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val); | |||
466 | } // end namespace llvm | |||
467 | #endif |