Line data Source code
1 : //===- LazyValueInfo.cpp - Value constraint analysis ------------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file defines the interface for lazy computation of value constraint
11 : // information.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : #include "llvm/Analysis/LazyValueInfo.h"
16 : #include "llvm/ADT/DenseSet.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/ValueTracking.h"
23 : #include "llvm/Analysis/ValueLattice.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/Support/Debug.h"
37 : #include "llvm/Support/FormattedStream.h"
38 : #include "llvm/Support/raw_ostream.h"
39 : #include <map>
40 : using namespace llvm;
41 : using namespace PatternMatch;
42 :
43 : #define DEBUG_TYPE "lazy-value-info"
44 :
45 : // This is the number of worklist items we will process to try to discover an
46 : // answer for a given value.
47 : static const unsigned MaxProcessedPerValue = 500;
48 :
49 : char LazyValueInfoWrapperPass::ID = 0;
50 33336 : INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info",
51 : "Lazy Value Information Analysis", false, true)
52 33336 : INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
53 33336 : INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
54 124663 : INITIALIZE_PASS_END(LazyValueInfoWrapperPass, "lazy-value-info",
55 : "Lazy Value Information Analysis", false, true)
56 :
57 : namespace llvm {
58 0 : FunctionPass *createLazyValueInfoPass() { return new LazyValueInfoWrapperPass(); }
59 : }
60 :
61 : AnalysisKey LazyValueAnalysis::Key;
62 :
63 : /// Returns true if this lattice value represents at most one possible value.
64 : /// This is as precise as any lattice value can get while still representing
65 : /// reachable code.
66 : static bool hasSingleValue(const ValueLatticeElement &Val) {
67 1820281 : if (Val.isConstantRange() &&
68 : Val.getConstantRange().isSingleElement())
69 : // Integer constants are single element ranges
70 : return true;
71 1726287 : if (Val.isConstant())
72 : // Non integer constants
73 : return true;
74 : return false;
75 : }
76 :
77 : /// Combine two sets of facts about the same value into a single set of
78 : /// facts. Note that this method is not suitable for merging facts along
79 : /// different paths in a CFG; that's what the mergeIn function is for. This
80 : /// is for merging facts gathered about the same value at the same location
81 : /// through two independent means.
82 : /// Notes:
83 : /// * This method does not promise to return the most precise possible lattice
84 : /// value implied by A and B. It is allowed to return any lattice element
85 : /// which is at least as strong as *either* A or B (unless our facts
86 : /// conflict, see below).
87 : /// * Due to unreachable code, the intersection of two lattice values could be
88 : /// contradictory. If this happens, we return some valid lattice value so as
89 : /// not confuse the rest of LVI. Ideally, we'd always return Undefined, but
90 : /// we do not make this guarantee. TODO: This would be a useful enhancement.
91 1014869 : static ValueLatticeElement intersect(const ValueLatticeElement &A,
92 : const ValueLatticeElement &B) {
93 : // Undefined is the strongest state. It means the value is known to be along
94 : // an unreachable path.
95 1014869 : if (A.isUndefined())
96 : return A;
97 1014869 : if (B.isUndefined())
98 : return B;
99 :
100 : // If we gave up for one, but got a useable fact from the other, use it.
101 1014367 : if (A.isOverdefined())
102 : return B;
103 43993 : if (B.isOverdefined())
104 : return A;
105 :
106 : // Can't get any more precise than constants.
107 : if (hasSingleValue(A))
108 : return A;
109 : if (hasSingleValue(B))
110 : return B;
111 :
112 : // Could be either constant range or not constant here.
113 15008 : if (!A.isConstantRange() || !B.isConstantRange()) {
114 : // TODO: Arbitrary choice, could be improved
115 : return A;
116 : }
117 :
118 : // Intersect two constant ranges
119 : ConstantRange Range =
120 14964 : A.getConstantRange().intersectWith(B.getConstantRange());
121 : // Note: An empty range is implicitly converted to overdefined internally.
122 : // TODO: We could instead use Undefined here since we've proven a conflict
123 : // and thus know this path must be unreachable.
124 14964 : return ValueLatticeElement::getRange(std::move(Range));
125 : }
126 :
127 : //===----------------------------------------------------------------------===//
128 : // LazyValueInfoCache Decl
129 : //===----------------------------------------------------------------------===//
130 :
131 : namespace {
132 : /// A callback value handle updates the cache when values are erased.
133 : class LazyValueInfoCache;
134 : struct LVIValueHandle final : public CallbackVH {
135 : // Needs to access getValPtr(), which is protected.
136 : friend struct DenseMapInfo<LVIValueHandle>;
137 :
138 : LazyValueInfoCache *Parent;
139 :
140 : LVIValueHandle(Value *V, LazyValueInfoCache *P)
141 371940 : : CallbackVH(V), Parent(P) { }
142 :
143 : void deleted() override;
144 282 : void allUsesReplacedWith(Value *V) override {
145 : deleted();
146 282 : }
147 : };
148 : } // end anonymous namespace
149 :
150 : namespace {
151 : /// This is the cache kept by LazyValueInfo which
152 : /// maintains information about queries across the clients' queries.
153 : class LazyValueInfoCache {
154 : /// This is all of the cached block information for exactly one Value*.
155 : /// The entries are sorted by the BasicBlock* of the
156 : /// entries, allowing us to do a lookup with a binary search.
157 : /// Over-defined lattice values are recorded in OverDefinedCache to reduce
158 : /// memory overhead.
159 : struct ValueCacheEntryTy {
160 371940 : ValueCacheEntryTy(Value *V, LazyValueInfoCache *P) : Handle(V, P) {}
161 : LVIValueHandle Handle;
162 : SmallDenseMap<PoisoningVH<BasicBlock>, ValueLatticeElement, 4> BlockVals;
163 : };
164 :
165 : /// This tracks, on a per-block basis, the set of values that are
166 : /// over-defined at the end of that block.
167 : typedef DenseMap<PoisoningVH<BasicBlock>, SmallPtrSet<Value *, 4>>
168 : OverDefinedCacheTy;
169 : /// Keep track of all blocks that we have ever seen, so we
170 : /// don't spend time removing unused blocks from our caches.
171 : DenseSet<PoisoningVH<BasicBlock> > SeenBlocks;
172 :
173 : /// This is all of the cached information for all values,
174 : /// mapped from Value* to key information.
175 : DenseMap<Value *, std::unique_ptr<ValueCacheEntryTy>> ValueCache;
176 : OverDefinedCacheTy OverDefinedCache;
177 :
178 :
179 : public:
180 1146822 : void insertResult(Value *Val, BasicBlock *BB,
181 : const ValueLatticeElement &Result) {
182 1146821 : SeenBlocks.insert(BB);
183 :
184 : // Insert over-defined values into their own cache to reduce memory
185 : // overhead.
186 1146821 : if (Result.isOverdefined())
187 720941 : OverDefinedCache[BB].insert(Val);
188 : else {
189 425880 : auto It = ValueCache.find_as(Val);
190 425880 : if (It == ValueCache.end()) {
191 371940 : ValueCache[Val] = make_unique<ValueCacheEntryTy>(Val, this);
192 185970 : It = ValueCache.find_as(Val);
193 : assert(It != ValueCache.end() && "Val was just added to the map!");
194 : }
195 425880 : It->second->BlockVals[BB] = Result;
196 : }
197 1146822 : }
198 :
199 5664909 : bool isOverdefined(Value *V, BasicBlock *BB) const {
200 11329818 : auto ODI = OverDefinedCache.find(BB);
201 :
202 5664909 : if (ODI == OverDefinedCache.end())
203 : return false;
204 :
205 3958910 : return ODI->second.count(V);
206 : }
207 :
208 4013823 : bool hasCachedValueInfo(Value *V, BasicBlock *BB) const {
209 4013823 : if (isOverdefined(V, BB))
210 : return true;
211 :
212 3272186 : auto I = ValueCache.find_as(V);
213 3272186 : if (I == ValueCache.end())
214 : return false;
215 :
216 2435068 : return I->second->BlockVals.count(BB);
217 : }
218 :
219 1651086 : ValueLatticeElement getCachedValueInfo(Value *V, BasicBlock *BB) const {
220 1651086 : if (isOverdefined(V, BB))
221 : return ValueLatticeElement::getOverdefined();
222 :
223 632250 : auto I = ValueCache.find_as(V);
224 632250 : if (I == ValueCache.end())
225 : return ValueLatticeElement();
226 1264500 : auto BBI = I->second->BlockVals.find(BB);
227 632250 : if (BBI == I->second->BlockVals.end())
228 : return ValueLatticeElement();
229 632250 : return BBI->second;
230 : }
231 :
232 : /// clear - Empty the cache.
233 0 : void clear() {
234 : SeenBlocks.clear();
235 0 : ValueCache.clear();
236 0 : OverDefinedCache.clear();
237 0 : }
238 :
239 : /// Inform the cache that a given value has been deleted.
240 : void eraseValue(Value *V);
241 :
242 : /// This is part of the update interface to inform the cache
243 : /// that a block has been deleted.
244 : void eraseBlock(BasicBlock *BB);
245 :
246 : /// Updates the cache to remove any influence an overdefined value in
247 : /// OldSucc might have (unless also overdefined in NewSucc). This just
248 : /// flushes elements from the cache and does not add any.
249 : void threadEdgeImpl(BasicBlock *OldSucc,BasicBlock *NewSucc);
250 :
251 : friend struct LVIValueHandle;
252 : };
253 : }
254 :
255 363 : void LazyValueInfoCache::eraseValue(Value *V) {
256 16924 : for (auto I = OverDefinedCache.begin(), E = OverDefinedCache.end(); I != E;) {
257 : // Copy and increment the iterator immediately so we can erase behind
258 : // ourselves.
259 : auto Iter = I++;
260 : SmallPtrSetImpl<Value *> &ValueSet = Iter->second;
261 16561 : ValueSet.erase(V);
262 16561 : if (ValueSet.empty())
263 : OverDefinedCache.erase(Iter);
264 : }
265 :
266 363 : ValueCache.erase(V);
267 363 : }
268 :
269 81 : void LVIValueHandle::deleted() {
270 : // This erasure deallocates *this, so it MUST happen after we're done
271 : // using any and all members of *this.
272 726 : Parent->eraseValue(*this);
273 81 : }
274 :
275 30650 : void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
276 : // Shortcut if we have never seen this block.
277 30650 : DenseSet<PoisoningVH<BasicBlock> >::iterator I = SeenBlocks.find(BB);
278 30650 : if (I == SeenBlocks.end())
279 26289 : return;
280 : SeenBlocks.erase(I);
281 :
282 8722 : auto ODI = OverDefinedCache.find(BB);
283 4361 : if (ODI != OverDefinedCache.end())
284 : OverDefinedCache.erase(ODI);
285 :
286 24468 : for (auto &I : ValueCache)
287 40214 : I.second->BlockVals.erase(BB);
288 : }
289 :
290 2525 : void LazyValueInfoCache::threadEdgeImpl(BasicBlock *OldSucc,
291 : BasicBlock *NewSucc) {
292 : // When an edge in the graph has been threaded, values that we could not
293 : // determine a value for before (i.e. were marked overdefined) may be
294 : // possible to solve now. We do NOT try to proactively update these values.
295 : // Instead, we clear their entries from the cache, and allow lazy updating to
296 : // recompute them when needed.
297 :
298 : // The updating process is fairly simple: we need to drop cached info
299 : // for all values that were marked overdefined in OldSucc, and for those same
300 : // values in any successor of OldSucc (except NewSucc) in which they were
301 : // also marked overdefined.
302 : std::vector<BasicBlock*> worklist;
303 2525 : worklist.push_back(OldSucc);
304 :
305 5050 : auto I = OverDefinedCache.find(OldSucc);
306 2525 : if (I == OverDefinedCache.end())
307 : return; // Nothing to process here.
308 316 : SmallVector<Value *, 4> ValsToClear(I->second.begin(), I->second.end());
309 :
310 : // Use a worklist to perform a depth-first search of OldSucc's successors.
311 : // NOTE: We do not need a visited list since any blocks we have already
312 : // visited will have had their overdefined markers cleared already, and we
313 : // thus won't loop to their successors.
314 2054 : while (!worklist.empty()) {
315 1896 : BasicBlock *ToUpdate = worklist.back();
316 : worklist.pop_back();
317 :
318 : // Skip blocks only accessible through NewSucc.
319 2646 : if (ToUpdate == NewSucc) continue;
320 :
321 : // If a value was marked overdefined in OldSucc, and is here too...
322 1703 : auto OI = OverDefinedCache.find(ToUpdate);
323 1703 : if (OI == OverDefinedCache.end())
324 : continue;
325 : SmallPtrSetImpl<Value *> &ValueSet = OI->second;
326 :
327 : bool changed = false;
328 2369 : for (Value *V : ValsToClear) {
329 1844 : if (!ValueSet.erase(V))
330 : continue;
331 :
332 : // If we removed anything, then we potentially need to update
333 : // blocks successors too.
334 : changed = true;
335 :
336 1314 : if (ValueSet.empty()) {
337 : OverDefinedCache.erase(OI);
338 : break;
339 : }
340 : }
341 :
342 525 : if (!changed) continue;
343 :
344 953 : worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate));
345 : }
346 : }
347 :
348 :
349 : namespace {
350 : /// An assembly annotator class to print LazyValueCache information in
351 : /// comments.
352 : class LazyValueInfoImpl;
353 4 : class LazyValueInfoAnnotatedWriter : public AssemblyAnnotationWriter {
354 : LazyValueInfoImpl *LVIImpl;
355 : // While analyzing which blocks we can solve values for, we need the dominator
356 : // information. Since this is an optional parameter in LVI, we require this
357 : // DomTreeAnalysis pass in the printer pass, and pass the dominator
358 : // tree to the LazyValueInfoAnnotatedWriter.
359 : DominatorTree &DT;
360 :
361 : public:
362 : LazyValueInfoAnnotatedWriter(LazyValueInfoImpl *L, DominatorTree &DTree)
363 4 : : LVIImpl(L), DT(DTree) {}
364 :
365 : virtual void emitBasicBlockStartAnnot(const BasicBlock *BB,
366 : formatted_raw_ostream &OS);
367 :
368 : virtual void emitInstructionAnnot(const Instruction *I,
369 : formatted_raw_ostream &OS);
370 : };
371 : }
372 : namespace {
373 : // The actual implementation of the lazy analysis and update. Note that the
374 : // inheritance from LazyValueInfoCache is intended to be temporary while
375 : // splitting the code and then transitioning to a has-a relationship.
376 : class LazyValueInfoImpl {
377 :
378 : /// Cached results from previous queries
379 : LazyValueInfoCache TheCache;
380 :
381 : /// This stack holds the state of the value solver during a query.
382 : /// It basically emulates the callstack of the naive
383 : /// recursive value lookup process.
384 : SmallVector<std::pair<BasicBlock*, Value*>, 8> BlockValueStack;
385 :
386 : /// Keeps track of which block-value pairs are in BlockValueStack.
387 : DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;
388 :
389 : /// Push BV onto BlockValueStack unless it's already in there.
390 : /// Returns true on success.
391 1167215 : bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
392 1167215 : if (!BlockValueSet.insert(BV).second)
393 : return false; // It's already in the stack.
394 :
395 : LLVM_DEBUG(dbgs() << "PUSH: " << *BV.second << " in "
396 : << BV.first->getName() << "\n");
397 1147458 : BlockValueStack.push_back(BV);
398 1147458 : return true;
399 : }
400 :
401 : AssumptionCache *AC; ///< A pointer to the cache of @llvm.assume calls.
402 : const DataLayout &DL; ///< A mandatory DataLayout
403 : DominatorTree *DT; ///< An optional DT pointer.
404 : DominatorTree *DisabledDT; ///< Stores DT if it's disabled.
405 :
406 : ValueLatticeElement getBlockValue(Value *Val, BasicBlock *BB);
407 : bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
408 : ValueLatticeElement &Result, Instruction *CxtI = nullptr);
409 : bool hasBlockValue(Value *Val, BasicBlock *BB);
410 :
411 : // These methods process one work item and may add more. A false value
412 : // returned means that the work item was not completely processed and must
413 : // be revisited after going through the new items.
414 : bool solveBlockValue(Value *Val, BasicBlock *BB);
415 : bool solveBlockValueImpl(ValueLatticeElement &Res, Value *Val,
416 : BasicBlock *BB);
417 : bool solveBlockValueNonLocal(ValueLatticeElement &BBLV, Value *Val,
418 : BasicBlock *BB);
419 : bool solveBlockValuePHINode(ValueLatticeElement &BBLV, PHINode *PN,
420 : BasicBlock *BB);
421 : bool solveBlockValueSelect(ValueLatticeElement &BBLV, SelectInst *S,
422 : BasicBlock *BB);
423 : bool solveBlockValueBinaryOp(ValueLatticeElement &BBLV, BinaryOperator *BBI,
424 : BasicBlock *BB);
425 : bool solveBlockValueCast(ValueLatticeElement &BBLV, CastInst *CI,
426 : BasicBlock *BB);
427 : void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
428 : ValueLatticeElement &BBLV,
429 : Instruction *BBI);
430 :
431 : void solve();
432 :
433 : public:
434 : /// This is the query interface to determine the lattice
435 : /// value for the specified Value* at the end of the specified block.
436 : ValueLatticeElement getValueInBlock(Value *V, BasicBlock *BB,
437 : Instruction *CxtI = nullptr);
438 :
439 : /// This is the query interface to determine the lattice
440 : /// value for the specified Value* at the specified instruction (generally
441 : /// from an assume intrinsic).
442 : ValueLatticeElement getValueAt(Value *V, Instruction *CxtI);
443 :
444 : /// This is the query interface to determine the lattice
445 : /// value for the specified Value* that is true on the specified edge.
446 : ValueLatticeElement getValueOnEdge(Value *V, BasicBlock *FromBB,
447 : BasicBlock *ToBB,
448 : Instruction *CxtI = nullptr);
449 :
450 : /// Complete flush all previously computed values
451 : void clear() {
452 0 : TheCache.clear();
453 : }
454 :
455 : /// Printing the LazyValueInfo Analysis.
456 4 : void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
457 : LazyValueInfoAnnotatedWriter Writer(this, DTree);
458 4 : F.print(OS, &Writer);
459 4 : }
460 :
461 : /// This is part of the update interface to inform the cache
462 : /// that a block has been deleted.
463 : void eraseBlock(BasicBlock *BB) {
464 30650 : TheCache.eraseBlock(BB);
465 : }
466 :
467 : /// Disables use of the DominatorTree within LVI.
468 : void disableDT() {
469 203820 : if (DT) {
470 : assert(!DisabledDT && "Both DT and DisabledDT are not nullptr!");
471 : std::swap(DT, DisabledDT);
472 : }
473 : }
474 :
475 : /// Enables use of the DominatorTree within LVI. Does nothing if the class
476 : /// instance was initialized without a DT pointer.
477 : void enableDT() {
478 131292 : if (DisabledDT) {
479 : assert(!DT && "Both DT and DisabledDT are not nullptr!");
480 : std::swap(DT, DisabledDT);
481 : }
482 : }
483 :
484 : /// This is the update interface to inform the cache that an edge from
485 : /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc.
486 : void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
487 :
488 : LazyValueInfoImpl(AssumptionCache *AC, const DataLayout &DL,
489 : DominatorTree *DT = nullptr)
490 75817 : : AC(AC), DL(DL), DT(DT), DisabledDT(nullptr) {}
491 : };
492 : } // end anonymous namespace
493 :
494 :
495 670538 : void LazyValueInfoImpl::solve() {
496 : SmallVector<std::pair<BasicBlock *, Value *>, 8> StartingStack(
497 : BlockValueStack.begin(), BlockValueStack.end());
498 :
499 : unsigned processedCount = 0;
500 2294262 : while (!BlockValueStack.empty()) {
501 1623742 : processedCount++;
502 : // Abort if we have to process too many values to get a result for this one.
503 : // Because of the design of the overdefined cache currently being per-block
504 : // to avoid naming-related issues (IE it wants to try to give different
505 : // results for the same name in different blocks), overdefined results don't
506 : // get cached globally, which in turn means we will often try to rediscover
507 : // the same overdefined result again and again. Once something like
508 : // PredicateInfo is used in LVI or CVP, we should be able to make the
509 : // overdefined cache global, and remove this throttle.
510 1623742 : if (processedCount > MaxProcessedPerValue) {
511 : LLVM_DEBUG(
512 : dbgs() << "Giving up on stack because we are getting too deep\n");
513 : // Fill in the original values
514 36 : while (!StartingStack.empty()) {
515 : std::pair<BasicBlock *, Value *> &e = StartingStack.back();
516 18 : TheCache.insertResult(e.second, e.first,
517 18 : ValueLatticeElement::getOverdefined());
518 : StartingStack.pop_back();
519 : }
520 : BlockValueSet.clear();
521 : BlockValueStack.clear();
522 18 : return;
523 : }
524 1623724 : std::pair<BasicBlock *, Value *> e = BlockValueStack.back();
525 : assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
526 :
527 1623724 : if (solveBlockValue(e.second, e.first)) {
528 : // The work item was completely processed.
529 : assert(BlockValueStack.back() == e && "Nothing should have been pushed!");
530 : assert(TheCache.hasCachedValueInfo(e.second, e.first) &&
531 : "Result should be in cache!");
532 :
533 : LLVM_DEBUG(
534 : dbgs() << "POP " << *e.second << " in " << e.first->getName() << " = "
535 : << TheCache.getCachedValueInfo(e.second, e.first) << "\n");
536 :
537 : BlockValueStack.pop_back();
538 : BlockValueSet.erase(e);
539 : } else {
540 : // More work needs to be done before revisiting.
541 : assert(BlockValueStack.back() != e && "Stack should have been pushed!");
542 : }
543 : }
544 : }
545 :
546 : bool LazyValueInfoImpl::hasBlockValue(Value *Val, BasicBlock *BB) {
547 : // If already a constant, there is nothing to compute.
548 2392774 : if (isa<Constant>(Val))
549 : return true;
550 :
551 2390099 : return TheCache.hasCachedValueInfo(Val, BB);
552 : }
553 :
554 1653741 : ValueLatticeElement LazyValueInfoImpl::getBlockValue(Value *Val,
555 : BasicBlock *BB) {
556 : // If already a constant, there is nothing to compute.
557 : if (Constant *VC = dyn_cast<Constant>(Val))
558 : return ValueLatticeElement::get(VC);
559 :
560 1651086 : return TheCache.getCachedValueInfo(Val, BB);
561 : }
562 :
563 579860 : static ValueLatticeElement getFromRangeMetadata(Instruction *BBI) {
564 : switch (BBI->getOpcode()) {
565 : default: break;
566 : case Instruction::Load:
567 : case Instruction::Call:
568 : case Instruction::Invoke:
569 234681 : if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))
570 25182 : if (isa<IntegerType>(BBI->getType())) {
571 : return ValueLatticeElement::getRange(
572 12591 : getConstantRangeFromMetadata(*Ranges));
573 : }
574 : break;
575 : };
576 : // Nothing known - will be intersected with other facts
577 : return ValueLatticeElement::getOverdefined();
578 : }
579 :
580 1623724 : bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) {
581 1623724 : if (isa<Constant>(Val))
582 : return true;
583 :
584 1623724 : if (TheCache.hasCachedValueInfo(Val, BB)) {
585 : // If we have a cached value, use that.
586 : LLVM_DEBUG(dbgs() << " reuse BB '" << BB->getName() << "' val="
587 : << TheCache.getCachedValueInfo(Val, BB) << '\n');
588 :
589 : // Since we're reusing a cached value, we don't need to update the
590 : // OverDefinedCache. The cache will have been properly updated whenever the
591 : // cached value was inserted.
592 : return true;
593 : }
594 :
595 : // Hold off inserting this value into the Cache in case we have to return
596 : // false and come back later.
597 : ValueLatticeElement Res;
598 1623724 : if (!solveBlockValueImpl(Res, Val, BB))
599 : // Work pushed, will revisit
600 : return false;
601 :
602 1146804 : TheCache.insertResult(Val, BB, Res);
603 1146804 : return true;
604 : }
605 :
606 1623724 : bool LazyValueInfoImpl::solveBlockValueImpl(ValueLatticeElement &Res,
607 : Value *Val, BasicBlock *BB) {
608 :
609 : Instruction *BBI = dyn_cast<Instruction>(Val);
610 1477717 : if (!BBI || BBI->getParent() != BB)
611 915998 : return solveBlockValueNonLocal(Res, Val, BB);
612 :
613 : if (PHINode *PN = dyn_cast<PHINode>(BBI))
614 196664 : return solveBlockValuePHINode(Res, PN, BB);
615 :
616 : if (auto *SI = dyn_cast<SelectInst>(BBI))
617 4562 : return solveBlockValueSelect(Res, SI, BB);
618 :
619 : // If this value is a nonnull pointer, record it's range and bailout. Note
620 : // that for all other pointer typed values, we terminate the search at the
621 : // definition. We could easily extend this to look through geps, bitcasts,
622 : // and the like to prove non-nullness, but it's not clear that's worth it
623 : // compile time wise. The context-insensitive value walk done inside
624 : // isKnownNonZero gets most of the profitable cases at much less expense.
625 : // This does mean that we have a sensativity to where the defining
626 : // instruction is placed, even if it could legally be hoisted much higher.
627 : // That is unfortunate.
628 506500 : PointerType *PT = dyn_cast<PointerType>(BBI->getType());
629 309246 : if (PT && isKnownNonZero(BBI, DL)) {
630 214396 : Res = ValueLatticeElement::getNot(ConstantPointerNull::get(PT));
631 107198 : return true;
632 : }
633 798604 : if (BBI->getType()->isIntegerTy()) {
634 : if (auto *CI = dyn_cast<CastInst>(BBI))
635 8833 : return solveBlockValueCast(Res, CI, BB);
636 :
637 : BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI);
638 50099 : if (BO && isa<ConstantInt>(BO->getOperand(1)))
639 42500 : return solveBlockValueBinaryOp(Res, BO, BB);
640 : }
641 :
642 : LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
643 : << "' - unknown inst def found.\n");
644 347969 : Res = getFromRangeMetadata(BBI);
645 347969 : return true;
646 : }
647 :
648 2089447 : static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) {
649 : if (LoadInst *L = dyn_cast<LoadInst>(I)) {
650 909794 : return L->getPointerAddressSpace() == 0 &&
651 909416 : GetUnderlyingObject(L->getPointerOperand(),
652 : L->getModule()->getDataLayout()) == Ptr;
653 : }
654 : if (StoreInst *S = dyn_cast<StoreInst>(I)) {
655 852001 : return S->getPointerAddressSpace() == 0 &&
656 851244 : GetUnderlyingObject(S->getPointerOperand(),
657 : S->getModule()->getDataLayout()) == Ptr;
658 : }
659 : if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
660 2168 : if (MI->isVolatile()) return false;
661 :
662 : // FIXME: check whether it has a valuerange that excludes zero?
663 : ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
664 1615 : if (!Len || Len->isZero()) return false;
665 :
666 1615 : if (MI->getDestAddressSpace() == 0)
667 3226 : if (GetUnderlyingObject(MI->getRawDest(),
668 : MI->getModule()->getDataLayout()) == Ptr)
669 : return true;
670 : if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
671 580 : if (MTI->getSourceAddressSpace() == 0)
672 1156 : if (GetUnderlyingObject(MTI->getRawSource(),
673 : MTI->getModule()->getDataLayout()) == Ptr)
674 64 : return true;
675 : }
676 : return false;
677 : }
678 :
679 : /// Return true if the allocation associated with Val is ever dereferenced
680 : /// within the given basic block. This establishes the fact Val is not null,
681 : /// but does not imply that the memory at Val is dereferenceable. (Val may
682 : /// point off the end of the dereferenceable part of the object.)
683 179546 : static bool isObjectDereferencedInBlock(Value *Val, BasicBlock *BB) {
684 : assert(Val->getType()->isPointerTy());
685 :
686 179546 : const DataLayout &DL = BB->getModule()->getDataLayout();
687 179546 : Value *UnderlyingVal = GetUnderlyingObject(Val, DL);
688 : // If 'GetUnderlyingObject' didn't converge, skip it. It won't converge
689 : // inside InstructionDereferencesPointer either.
690 179546 : if (UnderlyingVal == GetUnderlyingObject(UnderlyingVal, DL, 1))
691 2239416 : for (Instruction &I : *BB)
692 2089447 : if (InstructionDereferencesPointer(&I, UnderlyingVal))
693 : return true;
694 : return false;
695 : }
696 :
697 915998 : bool LazyValueInfoImpl::solveBlockValueNonLocal(ValueLatticeElement &BBLV,
698 : Value *Val, BasicBlock *BB) {
699 : ValueLatticeElement Result; // Start Undefined.
700 :
701 : // If this is the entry block, we must be asking about an argument. The
702 : // value is overdefined.
703 1831996 : if (BB == &BB->getParent()->getEntryBlock()) {
704 : assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
705 : // Before giving up, see if we can prove the pointer non-null local to
706 : // this particular block.
707 33922 : PointerType *PTy = dyn_cast<PointerType>(Val->getType());
708 30555 : if (PTy &&
709 48922 : (isKnownNonZero(Val, DL) ||
710 21757 : (isObjectDereferencedInBlock(Val, BB) &&
711 3390 : !NullPointerIsDefined(BB->getParent(), PTy->getAddressSpace())))) {
712 46707 : Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy));
713 : } else {
714 36706 : Result = ValueLatticeElement::getOverdefined();
715 : }
716 33922 : BBLV = Result;
717 33922 : return true;
718 : }
719 :
720 : // Loop over all of our predecessors, merging what we know from them into
721 : // result. If we encounter an unexplored predecessor, we eagerly explore it
722 : // in a depth first manner. In practice, this has the effect of discovering
723 : // paths we can't analyze eagerly without spending compile times analyzing
724 : // other paths. This heuristic benefits from the fact that predecessors are
725 : // frequently arranged such that dominating ones come first and we quickly
726 : // find a path to function entry. TODO: We should consider explicitly
727 : // canonicalizing to make this true rather than relying on this happy
728 : // accident.
729 1257593 : for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
730 : ValueLatticeElement EdgeResult;
731 1018342 : if (!getEdgeValue(Val, *PI, BB, EdgeResult))
732 : // Explore that input, then return here
733 : return false;
734 :
735 607617 : Result.mergeIn(EdgeResult, DL);
736 :
737 : // If we hit overdefined, exit early. The BlockVals entry is already set
738 : // to overdefined.
739 607617 : if (Result.isOverdefined()) {
740 : LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
741 : << "' - overdefined because of pred (non local).\n");
742 : // Before giving up, see if we can prove the pointer non-null local to
743 : // this particular block.
744 232100 : PointerType *PTy = dyn_cast<PointerType>(Val->getType());
745 187366 : if (PTy && isObjectDereferencedInBlock(Val, BB) &&
746 26187 : !NullPointerIsDefined(BB->getParent(), PTy->getAddressSpace())) {
747 78561 : Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy));
748 : }
749 :
750 232100 : BBLV = Result;
751 232100 : return true;
752 : }
753 : }
754 :
755 : // Return the merged value, which is more precise than 'overdefined'.
756 : assert(!Result.isOverdefined());
757 239251 : BBLV = Result;
758 239251 : return true;
759 : }
760 :
761 196664 : bool LazyValueInfoImpl::solveBlockValuePHINode(ValueLatticeElement &BBLV,
762 : PHINode *PN, BasicBlock *BB) {
763 : ValueLatticeElement Result; // Start Undefined.
764 :
765 : // Loop over all of our predecessors, merging what we know from them into
766 : // result. See the comment about the chosen traversal order in
767 : // solveBlockValueNonLocal; the same reasoning applies here.
768 308710 : for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
769 : BasicBlock *PhiBB = PN->getIncomingBlock(i);
770 : Value *PhiVal = PN->getIncomingValue(i);
771 : ValueLatticeElement EdgeResult;
772 : // Note that we can provide PN as the context value to getEdgeValue, even
773 : // though the results will be cached, because PN is the value being used as
774 : // the cache key in the caller.
775 302287 : if (!getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN))
776 : // Explore that input, then return here
777 : return false;
778 :
779 261952 : Result.mergeIn(EdgeResult, DL);
780 :
781 : // If we hit overdefined, exit early. The BlockVals entry is already set
782 : // to overdefined.
783 261952 : if (Result.isOverdefined()) {
784 : LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
785 : << "' - overdefined because of pred (local).\n");
786 :
787 149906 : BBLV = Result;
788 149906 : return true;
789 : }
790 : }
791 :
792 : // Return the merged value, which is more precise than 'overdefined'.
793 : assert(!Result.isOverdefined() && "Possible PHI in entry block?");
794 6423 : BBLV = Result;
795 6423 : return true;
796 : }
797 :
798 : static ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond,
799 : bool isTrueDest = true);
800 :
801 : // If we can determine a constraint on the value given conditions assumed by
802 : // the program, intersect those constraints with BBLV
803 0 : void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
804 : Value *Val, ValueLatticeElement &BBLV, Instruction *BBI) {
805 0 : BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
806 0 : if (!BBI)
807 0 : return;
808 :
809 0 : for (auto &AssumeVH : AC->assumptionsFor(Val)) {
810 0 : if (!AssumeVH)
811 0 : continue;
812 : auto *I = cast<CallInst>(AssumeVH);
813 0 : if (!isValidAssumeForContext(I, BBI, DT))
814 0 : continue;
815 :
816 0 : BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0)));
817 : }
818 :
819 : // If guards are not used in the module, don't spend time looking for them
820 0 : auto *GuardDecl = BBI->getModule()->getFunction(
821 : Intrinsic::getName(Intrinsic::experimental_guard));
822 0 : if (!GuardDecl || GuardDecl->use_empty())
823 0 : return;
824 :
825 0 : for (Instruction &I : make_range(BBI->getIterator().getReverse(),
826 0 : BBI->getParent()->rend())) {
827 0 : Value *Cond = nullptr;
828 0 : if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))
829 0 : BBLV = intersect(BBLV, getValueFromCondition(Val, Cond));
830 : }
831 : }
832 :
833 4562 : bool LazyValueInfoImpl::solveBlockValueSelect(ValueLatticeElement &BBLV,
834 : SelectInst *SI, BasicBlock *BB) {
835 :
836 : // Recurse on our inputs if needed
837 3228 : if (!hasBlockValue(SI->getTrueValue(), BB)) {
838 1251 : if (pushBlockValue(std::make_pair(BB, SI->getTrueValue())))
839 : return false;
840 1 : BBLV = ValueLatticeElement::getOverdefined();
841 1 : return true;
842 : }
843 3311 : ValueLatticeElement TrueVal = getBlockValue(SI->getTrueValue(), BB);
844 : // If we hit overdefined, don't ask more queries. We want to avoid poisoning
845 : // extra slots in the table if we can.
846 3311 : if (TrueVal.isOverdefined()) {
847 551 : BBLV = ValueLatticeElement::getOverdefined();
848 551 : return true;
849 : }
850 :
851 2395 : if (!hasBlockValue(SI->getFalseValue(), BB)) {
852 1128 : if (pushBlockValue(std::make_pair(BB, SI->getFalseValue())))
853 : return false;
854 0 : BBLV = ValueLatticeElement::getOverdefined();
855 0 : return true;
856 : }
857 1632 : ValueLatticeElement FalseVal = getBlockValue(SI->getFalseValue(), BB);
858 : // If we hit overdefined, don't ask more queries. We want to avoid poisoning
859 : // extra slots in the table if we can.
860 1632 : if (FalseVal.isOverdefined()) {
861 704 : BBLV = ValueLatticeElement::getOverdefined();
862 704 : return true;
863 : }
864 :
865 928 : if (TrueVal.isConstantRange() && FalseVal.isConstantRange()) {
866 : const ConstantRange &TrueCR = TrueVal.getConstantRange();
867 : const ConstantRange &FalseCR = FalseVal.getConstantRange();
868 657 : Value *LHS = nullptr;
869 657 : Value *RHS = nullptr;
870 657 : SelectPatternResult SPR = matchSelectPattern(SI, LHS, RHS);
871 : // Is this a min specifically of our two inputs? (Avoid the risk of
872 : // ValueTracking getting smarter looking back past our immediate inputs.)
873 657 : if (SelectPatternResult::isMinOrMax(SPR.Flavor) &&
874 157 : LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) {
875 : ConstantRange ResultCR = [&]() {
876 : switch (SPR.Flavor) {
877 : default:
878 : llvm_unreachable("unexpected minmax type!");
879 : case SPF_SMIN: /// Signed minimum
880 : return TrueCR.smin(FalseCR);
881 : case SPF_UMIN: /// Unsigned minimum
882 : return TrueCR.umin(FalseCR);
883 : case SPF_SMAX: /// Signed maximum
884 : return TrueCR.smax(FalseCR);
885 : case SPF_UMAX: /// Unsigned maximum
886 : return TrueCR.umax(FalseCR);
887 : };
888 102 : }();
889 204 : BBLV = ValueLatticeElement::getRange(ResultCR);
890 : return true;
891 : }
892 :
893 : // TODO: ABS, NABS from the SelectPatternResult
894 : }
895 :
896 : // Can we constrain the facts about the true and false values by using the
897 : // condition itself? This shows up with idioms like e.g. select(a > 5, a, 5).
898 : // TODO: We could potentially refine an overdefined true value above.
899 : Value *Cond = SI->getCondition();
900 1652 : TrueVal = intersect(TrueVal,
901 2478 : getValueFromCondition(SI->getTrueValue(), Cond, true));
902 1652 : FalseVal = intersect(FalseVal,
903 2478 : getValueFromCondition(SI->getFalseValue(), Cond, false));
904 :
905 : // Handle clamp idioms such as:
906 : // %24 = constantrange<0, 17>
907 : // %39 = icmp eq i32 %24, 0
908 : // %40 = add i32 %24, -1
909 : // %siv.next = select i1 %39, i32 16, i32 %40
910 : // %siv.next = constantrange<0, 17> not <-1, 17>
911 : // In general, this can handle any clamp idiom which tests the edge
912 : // condition via an equality or inequality.
913 : if (auto *ICI = dyn_cast<ICmpInst>(Cond)) {
914 : ICmpInst::Predicate Pred = ICI->getPredicate();
915 : Value *A = ICI->getOperand(0);
916 : if (ConstantInt *CIBase = dyn_cast<ConstantInt>(ICI->getOperand(1))) {
917 : auto addConstants = [](ConstantInt *A, ConstantInt *B) {
918 : assert(A->getType() == B->getType());
919 : return ConstantInt::get(A->getType(), A->getValue() + B->getValue());
920 : };
921 : // See if either input is A + C2, subject to the constraint from the
922 : // condition that A != C when that input is used. We can assume that
923 : // that input doesn't include C + C2.
924 : ConstantInt *CIAdded;
925 423 : switch (Pred) {
926 : default: break;
927 : case ICmpInst::ICMP_EQ:
928 367 : if (match(SI->getFalseValue(), m_Add(m_Specific(A),
929 367 : m_ConstantInt(CIAdded)))) {
930 9 : auto ResNot = addConstants(CIBase, CIAdded);
931 18 : FalseVal = intersect(FalseVal,
932 18 : ValueLatticeElement::getNot(ResNot));
933 : }
934 : break;
935 : case ICmpInst::ICMP_NE:
936 6 : if (match(SI->getTrueValue(), m_Add(m_Specific(A),
937 6 : m_ConstantInt(CIAdded)))) {
938 0 : auto ResNot = addConstants(CIBase, CIAdded);
939 0 : TrueVal = intersect(TrueVal,
940 0 : ValueLatticeElement::getNot(ResNot));
941 : }
942 : break;
943 : };
944 : }
945 : }
946 :
947 : ValueLatticeElement Result; // Start Undefined.
948 826 : Result.mergeIn(TrueVal, DL);
949 826 : Result.mergeIn(FalseVal, DL);
950 826 : BBLV = Result;
951 : return true;
952 : }
953 :
954 8833 : bool LazyValueInfoImpl::solveBlockValueCast(ValueLatticeElement &BBLV,
955 : CastInst *CI,
956 : BasicBlock *BB) {
957 8833 : if (!CI->getOperand(0)->getType()->isSized()) {
958 : // Without knowing how wide the input is, we can't analyze it in any useful
959 : // way.
960 0 : BBLV = ValueLatticeElement::getOverdefined();
961 0 : return true;
962 : }
963 :
964 : // Filter out casts we don't know how to reason about before attempting to
965 : // recurse on our operand. This can cut a long search short if we know we're
966 : // not going to be able to get any useful information anways.
967 : switch (CI->getOpcode()) {
968 : case Instruction::Trunc:
969 : case Instruction::SExt:
970 : case Instruction::ZExt:
971 : case Instruction::BitCast:
972 : break;
973 : default:
974 : // Unhandled instructions are overdefined.
975 : LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
976 : << "' - overdefined (unknown cast).\n");
977 1572 : BBLV = ValueLatticeElement::getOverdefined();
978 1572 : return true;
979 : }
980 :
981 : // Figure out the range of the LHS. If that fails, we still apply the
982 : // transfer rule on the full set since we may be able to locally infer
983 : // interesting facts.
984 7260 : if (!hasBlockValue(CI->getOperand(0), BB))
985 3582 : if (pushBlockValue(std::make_pair(BB, CI->getOperand(0))))
986 : // More work to do before applying this transfer rule.
987 : return false;
988 :
989 : const unsigned OperandBitWidth =
990 3679 : DL.getTypeSizeInBits(CI->getOperand(0)->getType());
991 3679 : ConstantRange LHSRange = ConstantRange(OperandBitWidth);
992 3678 : if (hasBlockValue(CI->getOperand(0), BB)) {
993 3679 : ValueLatticeElement LHSVal = getBlockValue(CI->getOperand(0), BB);
994 3679 : intersectAssumeOrGuardBlockValueConstantRange(CI->getOperand(0), LHSVal,
995 : CI);
996 3679 : if (LHSVal.isConstantRange())
997 : LHSRange = LHSVal.getConstantRange();
998 : }
999 :
1000 3679 : const unsigned ResultBitWidth = CI->getType()->getIntegerBitWidth();
1001 :
1002 : // NOTE: We're currently limited by the set of operations that ConstantRange
1003 : // can evaluate symbolically. Enhancing that set will allows us to analyze
1004 : // more definitions.
1005 7358 : BBLV = ValueLatticeElement::getRange(LHSRange.castOp(CI->getOpcode(),
1006 3679 : ResultBitWidth));
1007 : return true;
1008 : }
1009 :
1010 42500 : bool LazyValueInfoImpl::solveBlockValueBinaryOp(ValueLatticeElement &BBLV,
1011 : BinaryOperator *BO,
1012 : BasicBlock *BB) {
1013 :
1014 : assert(BO->getOperand(0)->getType()->isSized() &&
1015 : "all operands to binary operators are sized");
1016 :
1017 : // Filter out operators we don't know how to reason about before attempting to
1018 : // recurse on our operand(s). This can cut a long search short if we know
1019 : // we're not going to be able to get any useful information anyways.
1020 : switch (BO->getOpcode()) {
1021 : case Instruction::Add:
1022 : case Instruction::Sub:
1023 : case Instruction::Mul:
1024 : case Instruction::UDiv:
1025 : case Instruction::Shl:
1026 : case Instruction::LShr:
1027 : case Instruction::AShr:
1028 : case Instruction::And:
1029 : case Instruction::Or:
1030 : // continue into the code below
1031 : break;
1032 : default:
1033 : // Unhandled instructions are overdefined.
1034 : LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
1035 : << "' - overdefined (unknown binary operator).\n");
1036 653 : BBLV = ValueLatticeElement::getOverdefined();
1037 653 : return true;
1038 : };
1039 :
1040 : // Figure out the range of the LHS. If that fails, use a conservative range,
1041 : // but apply the transfer rule anyways. This lets us pick up facts from
1042 : // expressions like "and i32 (call i32 @foo()), 32"
1043 41828 : if (!hasBlockValue(BO->getOperand(0), BB))
1044 19915 : if (pushBlockValue(std::make_pair(BB, BO->getOperand(0))))
1045 : // More work to do before applying this transfer rule.
1046 : return false;
1047 :
1048 : const unsigned OperandBitWidth =
1049 21947 : DL.getTypeSizeInBits(BO->getOperand(0)->getType());
1050 43894 : ConstantRange LHSRange = ConstantRange(OperandBitWidth);
1051 21928 : if (hasBlockValue(BO->getOperand(0), BB)) {
1052 21932 : ValueLatticeElement LHSVal = getBlockValue(BO->getOperand(0), BB);
1053 21932 : intersectAssumeOrGuardBlockValueConstantRange(BO->getOperand(0), LHSVal,
1054 : BO);
1055 21932 : if (LHSVal.isConstantRange())
1056 : LHSRange = LHSVal.getConstantRange();
1057 : }
1058 :
1059 : ConstantInt *RHS = cast<ConstantInt>(BO->getOperand(1));
1060 43894 : ConstantRange RHSRange = ConstantRange(RHS->getValue());
1061 :
1062 : // NOTE: We're currently limited by the set of operations that ConstantRange
1063 : // can evaluate symbolically. Enhancing that set will allows us to analyze
1064 : // more definitions.
1065 : Instruction::BinaryOps BinOp = BO->getOpcode();
1066 43894 : BBLV = ValueLatticeElement::getRange(LHSRange.binaryOp(BinOp, RHSRange));
1067 : return true;
1068 : }
1069 :
1070 712880 : static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
1071 : bool isTrueDest) {
1072 : Value *LHS = ICI->getOperand(0);
1073 : Value *RHS = ICI->getOperand(1);
1074 : CmpInst::Predicate Predicate = ICI->getPredicate();
1075 :
1076 712880 : if (isa<Constant>(RHS)) {
1077 456339 : if (ICI->isEquality() && LHS == Val) {
1078 : // We know that V has the RHS constant if this is a true SETEQ or
1079 : // false SETNE.
1080 26652 : if (isTrueDest == (Predicate == ICmpInst::ICMP_EQ))
1081 : return ValueLatticeElement::get(cast<Constant>(RHS));
1082 : else
1083 : return ValueLatticeElement::getNot(cast<Constant>(RHS));
1084 : }
1085 : }
1086 :
1087 1372456 : if (!Val->getType()->isIntegerTy())
1088 : return ValueLatticeElement::getOverdefined();
1089 :
1090 : // Use ConstantRange::makeAllowedICmpRegion in order to determine the possible
1091 : // range of Val guaranteed by the condition. Recognize comparisons in the from
1092 : // of:
1093 : // icmp <pred> Val, ...
1094 : // icmp <pred> (add Val, Offset), ...
1095 : // The latter is the range checking idiom that InstCombine produces. Subtract
1096 : // the offset from the allowed range for RHS in this case.
1097 :
1098 : // Val or (add Val, Offset) can be on either hand of the comparison
1099 257284 : if (LHS != Val && !match(LHS, m_Add(m_Specific(Val), m_ConstantInt()))) {
1100 : std::swap(LHS, RHS);
1101 226249 : Predicate = CmpInst::getSwappedPredicate(Predicate);
1102 : }
1103 :
1104 257284 : ConstantInt *Offset = nullptr;
1105 257284 : if (LHS != Val)
1106 222697 : match(LHS, m_Add(m_Specific(Val), m_ConstantInt(Offset)));
1107 :
1108 257284 : if (LHS == Val || Offset) {
1109 : // Calculate the range of values that are allowed by the comparison
1110 : ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(),
1111 113316 : /*isFullSet=*/true);
1112 : if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
1113 21601 : RHSRange = ConstantRange(CI->getValue());
1114 : else if (Instruction *I = dyn_cast<Instruction>(RHS))
1115 12471 : if (auto *Ranges = I->getMetadata(LLVMContext::MD_range))
1116 4 : RHSRange = getConstantRangeFromMetadata(*Ranges);
1117 :
1118 : // If we're interested in the false dest, invert the condition
1119 : CmpInst::Predicate Pred =
1120 37772 : isTrueDest ? Predicate : CmpInst::getInversePredicate(Predicate);
1121 : ConstantRange TrueValues =
1122 37772 : ConstantRange::makeAllowedICmpRegion(Pred, RHSRange);
1123 :
1124 37772 : if (Offset) // Apply the offset from above.
1125 3185 : TrueValues = TrueValues.subtract(Offset->getValue());
1126 :
1127 37772 : return ValueLatticeElement::getRange(std::move(TrueValues));
1128 : }
1129 :
1130 : return ValueLatticeElement::getOverdefined();
1131 : }
1132 :
1133 : static ValueLatticeElement
1134 : getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
1135 : DenseMap<Value*, ValueLatticeElement> &Visited);
1136 :
1137 : static ValueLatticeElement
1138 773134 : getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest,
1139 : DenseMap<Value*, ValueLatticeElement> &Visited) {
1140 : if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond))
1141 712880 : return getValueFromICmpCondition(Val, ICI, isTrueDest);
1142 :
1143 : // Handle conditions in the form of (cond1 && cond2), we know that on the
1144 : // true dest path both of the conditions hold. Similarly for conditions of
1145 : // the form (cond1 || cond2), we know that on the false dest path neither
1146 : // condition holds.
1147 : BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond);
1148 17668 : if (!BO || (isTrueDest && BO->getOpcode() != BinaryOperator::And) ||
1149 7347 : (!isTrueDest && BO->getOpcode() != BinaryOperator::Or))
1150 : return ValueLatticeElement::getOverdefined();
1151 :
1152 : // Prevent infinite recursion if Cond references itself as in this example:
1153 : // Cond: "%tmp4 = and i1 %tmp4, undef"
1154 : // BL: "%tmp4 = and i1 %tmp4, undef"
1155 : // BR: "i1 undef"
1156 : Value *BL = BO->getOperand(0);
1157 : Value *BR = BO->getOperand(1);
1158 5414 : if (BL == Cond || BR == Cond)
1159 : return ValueLatticeElement::getOverdefined();
1160 :
1161 10824 : return intersect(getValueFromCondition(Val, BL, isTrueDest, Visited),
1162 16236 : getValueFromCondition(Val, BR, isTrueDest, Visited));
1163 : }
1164 :
1165 : static ValueLatticeElement
1166 773396 : getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
1167 : DenseMap<Value*, ValueLatticeElement> &Visited) {
1168 773396 : auto I = Visited.find(Cond);
1169 773396 : if (I != Visited.end())
1170 262 : return I->second;
1171 :
1172 773134 : auto Result = getValueFromConditionImpl(Val, Cond, isTrueDest, Visited);
1173 773134 : Visited[Cond] = Result;
1174 : return Result;
1175 : }
1176 :
1177 762572 : ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond,
1178 : bool isTrueDest) {
1179 : assert(Cond && "precondition");
1180 : DenseMap<Value*, ValueLatticeElement> Visited;
1181 762572 : return getValueFromCondition(Val, Cond, isTrueDest, Visited);
1182 : }
1183 :
1184 : // Return true if Usr has Op as an operand, otherwise false.
1185 37768 : static bool usesOperand(User *Usr, Value *Op) {
1186 37768 : return find(Usr->operands(), Op) != Usr->op_end();
1187 : }
1188 :
1189 : // Return true if the instruction type of Val is supported by
1190 : // constantFoldUser(). Currently CastInst and BinaryOperator only. Call this
1191 : // before calling constantFoldUser() to find out if it's even worth attempting
1192 : // to call it.
1193 : static bool isOperationFoldable(User *Usr) {
1194 : return isa<CastInst>(Usr) || isa<BinaryOperator>(Usr);
1195 : }
1196 :
1197 : // Check if Usr can be simplified to an integer constant when the value of one
1198 : // of its operands Op is an integer constant OpConstVal. If so, return it as an
1199 : // lattice value range with a single element or otherwise return an overdefined
1200 : // lattice value.
1201 294 : static ValueLatticeElement constantFoldUser(User *Usr, Value *Op,
1202 : const APInt &OpConstVal,
1203 : const DataLayout &DL) {
1204 : assert(isOperationFoldable(Usr) && "Precondition");
1205 294 : Constant* OpConst = Constant::getIntegerValue(Op->getType(), OpConstVal);
1206 : // Check if Usr can be simplified to a constant.
1207 : if (auto *CI = dyn_cast<CastInst>(Usr)) {
1208 : assert(CI->getOperand(0) == Op && "Operand 0 isn't Op");
1209 436 : if (auto *C = dyn_cast_or_null<ConstantInt>(
1210 : SimplifyCastInst(CI->getOpcode(), OpConst,
1211 : CI->getDestTy(), DL))) {
1212 218 : return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
1213 : }
1214 : } else if (auto *BO = dyn_cast<BinaryOperator>(Usr)) {
1215 : bool Op0Match = BO->getOperand(0) == Op;
1216 : bool Op1Match = BO->getOperand(1) == Op;
1217 : assert((Op0Match || Op1Match) &&
1218 : "Operand 0 nor Operand 1 isn't a match");
1219 76 : Value *LHS = Op0Match ? OpConst : BO->getOperand(0);
1220 76 : Value *RHS = Op1Match ? OpConst : BO->getOperand(1);
1221 152 : if (auto *C = dyn_cast_or_null<ConstantInt>(
1222 : SimplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) {
1223 20 : return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
1224 : }
1225 : }
1226 : return ValueLatticeElement::getOverdefined();
1227 : }
1228 :
1229 : /// Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
1230 : /// Val is not constrained on the edge. Result is unspecified if return value
1231 : /// is false.
1232 1700716 : static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
1233 : BasicBlock *BBTo, ValueLatticeElement &Result) {
1234 : // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
1235 : // know that v != 0.
1236 : if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
1237 : // If this is a conditional branch and only one successor goes to BBTo, then
1238 : // we may be able to infer something from the condition.
1239 2091861 : if (BI->isConditional() &&
1240 : BI->getSuccessor(0) != BI->getSuccessor(1)) {
1241 695041 : bool isTrueDest = BI->getSuccessor(0) == BBTo;
1242 : assert(BI->getSuccessor(!isTrueDest) == BBTo &&
1243 : "BBTo isn't a successor of BBFrom");
1244 : Value *Condition = BI->getCondition();
1245 :
1246 : // If V is the condition of the branch itself, then we know exactly what
1247 : // it is.
1248 695041 : if (Condition == Val) {
1249 2757 : Result = ValueLatticeElement::get(ConstantInt::get(
1250 2757 : Type::getInt1Ty(Val->getContext()), isTrueDest));
1251 2757 : return true;
1252 : }
1253 :
1254 : // If the condition of the branch is an equality comparison, we may be
1255 : // able to infer the value.
1256 692284 : Result = getValueFromCondition(Val, Condition, isTrueDest);
1257 692284 : if (!Result.isOverdefined())
1258 : return true;
1259 :
1260 : if (User *Usr = dyn_cast<User>(Val)) {
1261 : assert(Result.isOverdefined() && "Result isn't overdefined");
1262 : // Check with isOperationFoldable() first to avoid linearly iterating
1263 : // over the operands unnecessarily which can be expensive for
1264 : // instructions with many operands.
1265 1058150 : if (isa<IntegerType>(Usr->getType()) && isOperationFoldable(Usr)) {
1266 36502 : const DataLayout &DL = BBTo->getModule()->getDataLayout();
1267 36502 : if (usesOperand(Usr, Condition)) {
1268 : // If Val has Condition as an operand and Val can be folded into a
1269 : // constant with either Condition == true or Condition == false,
1270 : // propagate the constant.
1271 : // eg.
1272 : // ; %Val is true on the edge to %then.
1273 : // %Val = and i1 %Condition, true.
1274 : // br %Condition, label %then, label %else
1275 16 : APInt ConditionVal(1, isTrueDest ? 1 : 0);
1276 32 : Result = constantFoldUser(Usr, Condition, ConditionVal, DL);
1277 : } else {
1278 : // If one of Val's operand has an inferred value, we may be able to
1279 : // infer the value of Val.
1280 : // eg.
1281 : // ; %Val is 94 on the edge to %then.
1282 : // %Val = add i8 %Op, 1
1283 : // %Condition = icmp eq i8 %Op, 93
1284 : // br i1 %Condition, label %then, label %else
1285 104969 : for (unsigned i = 0; i < Usr->getNumOperands(); ++i) {
1286 : Value *Op = Usr->getOperand(i);
1287 : ValueLatticeElement OpLatticeVal =
1288 68551 : getValueFromCondition(Op, Condition, isTrueDest);
1289 68551 : if (Optional<APInt> OpConst = OpLatticeVal.asConstantInteger()) {
1290 136 : Result = constantFoldUser(Usr, Op, OpConst.getValue(), DL);
1291 : break;
1292 : }
1293 : }
1294 : }
1295 : }
1296 : }
1297 630078 : if (!Result.isOverdefined())
1298 : return true;
1299 : }
1300 : }
1301 :
1302 : // If the edge was formed by a switch on the value, then we may know exactly
1303 : // what it is.
1304 : if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
1305 : Value *Condition = SI->getCondition();
1306 33374 : if (!isa<IntegerType>(Val->getType()))
1307 : return false;
1308 : bool ValUsesConditionAndMayBeFoldable = false;
1309 4789 : if (Condition != Val) {
1310 : // Check if Val has Condition as an operand.
1311 : if (User *Usr = dyn_cast<User>(Val))
1312 1266 : ValUsesConditionAndMayBeFoldable = isOperationFoldable(Usr) &&
1313 1266 : usesOperand(Usr, Condition);
1314 3883 : if (!ValUsesConditionAndMayBeFoldable)
1315 4081 : return false;
1316 : }
1317 : assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&
1318 : "Condition != Val nor Val doesn't use Condition");
1319 :
1320 708 : bool DefaultCase = SI->getDefaultDest() == BBTo;
1321 708 : unsigned BitWidth = Val->getType()->getIntegerBitWidth();
1322 1416 : ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
1323 :
1324 3717 : for (auto Case : SI->cases()) {
1325 : APInt CaseValue = Case.getCaseValue()->getValue();
1326 6018 : ConstantRange EdgeVal(CaseValue);
1327 3009 : if (ValUsesConditionAndMayBeFoldable) {
1328 : User *Usr = cast<User>(Val);
1329 210 : const DataLayout &DL = BBTo->getModule()->getDataLayout();
1330 : ValueLatticeElement EdgeLatticeVal =
1331 210 : constantFoldUser(Usr, Condition, CaseValue, DL);
1332 210 : if (EdgeLatticeVal.isOverdefined())
1333 : return false;
1334 : EdgeVal = EdgeLatticeVal.getConstantRange();
1335 : }
1336 3009 : if (DefaultCase) {
1337 : // It is possible that the default destination is the destination of
1338 : // some cases. We cannot perform difference for those cases.
1339 : // We know Condition != CaseValue in BBTo. In some cases we can use
1340 : // this to infer Val == f(Condition) is != f(CaseValue). For now, we
1341 : // only do this when f is identity (i.e. Val == Condition), but we
1342 : // should be able to do this for any injective f.
1343 1839 : if (Case.getCaseSuccessor() != BBTo && Condition == Val)
1344 1605 : EdgesVals = EdgesVals.difference(EdgeVal);
1345 1170 : } else if (Case.getCaseSuccessor() == BBTo)
1346 517 : EdgesVals = EdgesVals.unionWith(EdgeVal);
1347 : }
1348 1416 : Result = ValueLatticeElement::getRange(std::move(EdgesVals));
1349 708 : return true;
1350 : }
1351 : return false;
1352 : }
1353 :
1354 : /// Compute the value of Val on the edge BBFrom -> BBTo or the value at
1355 : /// the basic block if the edge does not constrain Val.
1356 1889054 : bool LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom,
1357 : BasicBlock *BBTo,
1358 : ValueLatticeElement &Result,
1359 : Instruction *CxtI) {
1360 : // If already a constant, there is nothing to compute.
1361 : if (Constant *VC = dyn_cast<Constant>(Val)) {
1362 188338 : Result = ValueLatticeElement::get(VC);
1363 188338 : return true;
1364 : }
1365 :
1366 : ValueLatticeElement LocalResult;
1367 1700716 : if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult))
1368 : // If we couldn't constrain the value on the edge, LocalResult doesn't
1369 : // provide any information.
1370 3270034 : LocalResult = ValueLatticeElement::getOverdefined();
1371 :
1372 : if (hasSingleValue(LocalResult)) {
1373 : // Can't get any more precise here
1374 5474 : Result = LocalResult;
1375 5474 : return true;
1376 : }
1377 :
1378 1695242 : if (!hasBlockValue(Val, BBFrom)) {
1379 687531 : if (pushBlockValue(std::make_pair(BBFrom, Val)))
1380 : return false;
1381 : // No new information.
1382 19741 : Result = LocalResult;
1383 19741 : return true;
1384 : }
1385 :
1386 : // Try to intersect ranges of the BB and the constraint on the edge.
1387 1007711 : ValueLatticeElement InBlock = getBlockValue(Val, BBFrom);
1388 1007711 : intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock,
1389 : BBFrom->getTerminator());
1390 : // We can use the context instruction (generically the ultimate instruction
1391 : // the calling pass is trying to simplify) here, even though the result of
1392 : // this function is generally cached when called from the solve* functions
1393 : // (and that cached result might be used with queries using a different
1394 : // context instruction), because when this function is called from the solve*
1395 : // functions, the context instruction is not provided. When called from
1396 : // LazyValueInfoImpl::getValueOnEdge, the context instruction is provided,
1397 : // but then the result is not cached.
1398 1007711 : intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI);
1399 :
1400 2015422 : Result = intersect(LocalResult, InBlock);
1401 : return true;
1402 : }
1403 :
1404 615476 : ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB,
1405 : Instruction *CxtI) {
1406 : LLVM_DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
1407 : << BB->getName() << "'\n");
1408 :
1409 : assert(BlockValueStack.empty() && BlockValueSet.empty());
1410 614540 : if (!hasBlockValue(V, BB)) {
1411 453808 : pushBlockValue(std::make_pair(BB, V));
1412 453808 : solve();
1413 : }
1414 615476 : ValueLatticeElement Result = getBlockValue(V, BB);
1415 615476 : intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1416 :
1417 : LLVM_DEBUG(dbgs() << " Result = " << Result << "\n");
1418 615476 : return Result;
1419 : }
1420 :
1421 274779 : ValueLatticeElement LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) {
1422 : LLVM_DEBUG(dbgs() << "LVI Getting value " << *V << " at '" << CxtI->getName()
1423 : << "'\n");
1424 :
1425 : if (auto *C = dyn_cast<Constant>(V))
1426 : return ValueLatticeElement::get(C);
1427 :
1428 : ValueLatticeElement Result = ValueLatticeElement::getOverdefined();
1429 : if (auto *I = dyn_cast<Instruction>(V))
1430 463782 : Result = getFromRangeMetadata(I);
1431 274690 : intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
1432 :
1433 : LLVM_DEBUG(dbgs() << " Result = " << Result << "\n");
1434 : return Result;
1435 : }
1436 :
1437 351695 : ValueLatticeElement LazyValueInfoImpl::
1438 : getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
1439 : Instruction *CxtI) {
1440 : LLVM_DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
1441 : << FromBB->getName() << "' to '" << ToBB->getName()
1442 : << "'\n");
1443 :
1444 : ValueLatticeElement Result;
1445 351695 : if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) {
1446 216730 : solve();
1447 216730 : bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result, CxtI);
1448 : (void)WasFastQuery;
1449 : assert(WasFastQuery && "More work to do after problem solved?");
1450 : }
1451 :
1452 : LLVM_DEBUG(dbgs() << " Result = " << Result << "\n");
1453 351695 : return Result;
1454 : }
1455 :
1456 0 : void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1457 : BasicBlock *NewSucc) {
1458 2525 : TheCache.threadEdgeImpl(OldSucc, NewSucc);
1459 0 : }
1460 :
1461 : //===----------------------------------------------------------------------===//
1462 : // LazyValueInfo Impl
1463 : //===----------------------------------------------------------------------===//
1464 :
1465 : /// This lazily constructs the LazyValueInfoImpl.
1466 1685946 : static LazyValueInfoImpl &getImpl(void *&PImpl, AssumptionCache *AC,
1467 : const DataLayout *DL,
1468 : DominatorTree *DT = nullptr) {
1469 1685946 : if (!PImpl) {
1470 : assert(DL && "getCache() called with a null DataLayout");
1471 151634 : PImpl = new LazyValueInfoImpl(AC, *DL, DT);
1472 : }
1473 1685946 : return *static_cast<LazyValueInfoImpl*>(PImpl);
1474 : }
1475 :
1476 88362 : bool LazyValueInfoWrapperPass::runOnFunction(Function &F) {
1477 88362 : Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1478 88362 : const DataLayout &DL = F.getParent()->getDataLayout();
1479 :
1480 : DominatorTreeWrapperPass *DTWP =
1481 88362 : getAnalysisIfAvailable<DominatorTreeWrapperPass>();
1482 88362 : Info.DT = DTWP ? &DTWP->getDomTree() : nullptr;
1483 88362 : Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1484 :
1485 88362 : if (Info.PImpl)
1486 0 : getImpl(Info.PImpl, Info.AC, &DL, Info.DT).clear();
1487 :
1488 : // Fully lazy.
1489 88362 : return false;
1490 : }
1491 :
1492 3476 : void LazyValueInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1493 : AU.setPreservesAll();
1494 : AU.addRequired<AssumptionCacheTracker>();
1495 : AU.addRequired<TargetLibraryInfoWrapperPass>();
1496 3476 : }
1497 :
1498 175486 : LazyValueInfo &LazyValueInfoWrapperPass::getLVI() { return Info; }
1499 :
1500 4243 : LazyValueInfo::~LazyValueInfo() { releaseMemory(); }
1501 :
1502 92604 : void LazyValueInfo::releaseMemory() {
1503 : // If the cache was allocated, free it.
1504 92604 : if (PImpl) {
1505 75817 : delete &getImpl(PImpl, AC, nullptr);
1506 75817 : PImpl = nullptr;
1507 : }
1508 92604 : }
1509 :
1510 201 : bool LazyValueInfo::invalidate(Function &F, const PreservedAnalyses &PA,
1511 : FunctionAnalysisManager::Invalidator &Inv) {
1512 : // We need to invalidate if we have either failed to preserve this analyses
1513 : // result directly or if any of its dependencies have been invalidated.
1514 : auto PAC = PA.getChecker<LazyValueAnalysis>();
1515 201 : if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
1516 50 : (DT && Inv.invalidate<DominatorTreeAnalysis>(F, PA)))
1517 176 : return true;
1518 :
1519 : return false;
1520 : }
1521 :
1522 88362 : void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); }
1523 :
1524 261 : LazyValueInfo LazyValueAnalysis::run(Function &F,
1525 : FunctionAnalysisManager &FAM) {
1526 : auto &AC = FAM.getResult<AssumptionAnalysis>(F);
1527 : auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
1528 : auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
1529 :
1530 261 : return LazyValueInfo(&AC, &F.getParent()->getDataLayout(), &TLI, DT);
1531 : }
1532 :
1533 : /// Returns true if we can statically tell that this value will never be a
1534 : /// "useful" constant. In practice, this means we've got something like an
1535 : /// alloca or a malloc call for which a comparison against a constant can
1536 : /// only be guarding dead code. Note that we are potentially giving up some
1537 : /// precision in dead code (a constant result) in favour of avoiding a
1538 : /// expensive search for a easily answered common query.
1539 : static bool isKnownNonConstant(Value *V) {
1540 : V = V->stripPointerCasts();
1541 : // The return val of alloc cannot be a Constant.
1542 : if (isa<AllocaInst>(V))
1543 : return true;
1544 : return false;
1545 : }
1546 :
1547 685434 : Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB,
1548 : Instruction *CxtI) {
1549 : // Bail out early if V is known not to be a Constant.
1550 : if (isKnownNonConstant(V))
1551 : return nullptr;
1552 :
1553 611769 : const DataLayout &DL = BB->getModule()->getDataLayout();
1554 : ValueLatticeElement Result =
1555 611769 : getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
1556 :
1557 611769 : if (Result.isConstant())
1558 1 : return Result.getConstant();
1559 611768 : if (Result.isConstantRange()) {
1560 : const ConstantRange &CR = Result.getConstantRange();
1561 10812 : if (const APInt *SingleVal = CR.getSingleElement())
1562 12 : return ConstantInt::get(V->getContext(), *SingleVal);
1563 : }
1564 : return nullptr;
1565 : }
1566 :
1567 3596 : ConstantRange LazyValueInfo::getConstantRange(Value *V, BasicBlock *BB,
1568 : Instruction *CxtI) {
1569 : assert(V->getType()->isIntegerTy());
1570 3596 : unsigned Width = V->getType()->getIntegerBitWidth();
1571 3596 : const DataLayout &DL = BB->getModule()->getDataLayout();
1572 : ValueLatticeElement Result =
1573 3596 : getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
1574 3596 : if (Result.isUndefined())
1575 0 : return ConstantRange(Width, /*isFullSet=*/false);
1576 3596 : if (Result.isConstantRange())
1577 2355 : return Result.getConstantRange();
1578 : // We represent ConstantInt constants as constant ranges but other kinds
1579 : // of integer constants, i.e. ConstantExpr will be tagged as constants
1580 : assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1581 : "ConstantInt value must be represented as constantrange");
1582 1241 : return ConstantRange(Width, /*isFullSet=*/true);
1583 : }
1584 :
1585 : /// Determine whether the specified value is known to be a
1586 : /// constant on the specified edge. Return null if not.
1587 250900 : Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
1588 : BasicBlock *ToBB,
1589 : Instruction *CxtI) {
1590 250900 : const DataLayout &DL = FromBB->getModule()->getDataLayout();
1591 : ValueLatticeElement Result =
1592 250900 : getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1593 :
1594 250900 : if (Result.isConstant())
1595 277 : return Result.getConstant();
1596 250623 : if (Result.isConstantRange()) {
1597 : const ConstantRange &CR = Result.getConstantRange();
1598 29282 : if (const APInt *SingleVal = CR.getSingleElement())
1599 1588 : return ConstantInt::get(V->getContext(), *SingleVal);
1600 : }
1601 : return nullptr;
1602 : }
1603 :
1604 3436 : ConstantRange LazyValueInfo::getConstantRangeOnEdge(Value *V,
1605 : BasicBlock *FromBB,
1606 : BasicBlock *ToBB,
1607 : Instruction *CxtI) {
1608 3436 : unsigned Width = V->getType()->getIntegerBitWidth();
1609 3436 : const DataLayout &DL = FromBB->getModule()->getDataLayout();
1610 : ValueLatticeElement Result =
1611 3436 : getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1612 :
1613 3436 : if (Result.isUndefined())
1614 0 : return ConstantRange(Width, /*isFullSet=*/false);
1615 3436 : if (Result.isConstantRange())
1616 2534 : return Result.getConstantRange();
1617 : // We represent ConstantInt constants as constant ranges but other kinds
1618 : // of integer constants, i.e. ConstantExpr will be tagged as constants
1619 : assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
1620 : "ConstantInt value must be represented as constantrange");
1621 902 : return ConstantRange(Width, /*isFullSet=*/true);
1622 : }
1623 :
1624 : static LazyValueInfo::Tristate
1625 372138 : getPredicateResult(unsigned Pred, Constant *C, const ValueLatticeElement &Val,
1626 : const DataLayout &DL, TargetLibraryInfo *TLI) {
1627 : // If we know the value is a constant, evaluate the conditional.
1628 : Constant *Res = nullptr;
1629 372138 : if (Val.isConstant()) {
1630 4560 : Res = ConstantFoldCompareInstOperands(Pred, Val.getConstant(), C, DL, TLI);
1631 : if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
1632 4559 : return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True;
1633 : return LazyValueInfo::Unknown;
1634 : }
1635 :
1636 367578 : if (Val.isConstantRange()) {
1637 : ConstantInt *CI = dyn_cast<ConstantInt>(C);
1638 : if (!CI) return LazyValueInfo::Unknown;
1639 :
1640 : const ConstantRange &CR = Val.getConstantRange();
1641 38407 : if (Pred == ICmpInst::ICMP_EQ) {
1642 21026 : if (!CR.contains(CI->getValue()))
1643 : return LazyValueInfo::False;
1644 :
1645 17453 : if (CR.isSingleElement())
1646 : return LazyValueInfo::True;
1647 17381 : } else if (Pred == ICmpInst::ICMP_NE) {
1648 4556 : if (!CR.contains(CI->getValue()))
1649 : return LazyValueInfo::True;
1650 :
1651 4497 : if (CR.isSingleElement())
1652 : return LazyValueInfo::False;
1653 : } else {
1654 : // Handle more complex predicates.
1655 : ConstantRange TrueValues = ConstantRange::makeExactICmpRegion(
1656 24424 : (ICmpInst::Predicate)Pred, CI->getValue());
1657 12825 : if (TrueValues.contains(CR))
1658 1226 : return LazyValueInfo::True;
1659 12075 : if (TrueValues.inverse().contains(CR))
1660 : return LazyValueInfo::False;
1661 : }
1662 32293 : return LazyValueInfo::Unknown;
1663 : }
1664 :
1665 329163 : if (Val.isNotConstant()) {
1666 : // If this is an equality comparison, we can try to fold it knowing that
1667 : // "V != C1".
1668 4141 : if (Pred == ICmpInst::ICMP_EQ) {
1669 : // !C1 == C -> false iff C1 == C.
1670 4007 : Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1671 : Val.getNotConstant(), C, DL,
1672 : TLI);
1673 4007 : if (Res->isNullValue())
1674 : return LazyValueInfo::False;
1675 134 : } else if (Pred == ICmpInst::ICMP_NE) {
1676 : // !C1 != C -> true iff C1 == C.
1677 56 : Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1678 : Val.getNotConstant(), C, DL,
1679 : TLI);
1680 56 : if (Res->isNullValue())
1681 : return LazyValueInfo::True;
1682 : }
1683 135 : return LazyValueInfo::Unknown;
1684 : }
1685 :
1686 : return LazyValueInfo::Unknown;
1687 : }
1688 :
1689 : /// Determine whether the specified value comparison with a constant is known to
1690 : /// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
1691 : LazyValueInfo::Tristate
1692 97359 : LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
1693 : BasicBlock *FromBB, BasicBlock *ToBB,
1694 : Instruction *CxtI) {
1695 97359 : const DataLayout &DL = FromBB->getModule()->getDataLayout();
1696 : ValueLatticeElement Result =
1697 97359 : getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1698 :
1699 97359 : return getPredicateResult(Pred, C, Result, DL, TLI);
1700 : }
1701 :
1702 : LazyValueInfo::Tristate
1703 341646 : LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C,
1704 : Instruction *CxtI) {
1705 : // Is or is not NonNull are common predicates being queried. If
1706 : // isKnownNonZero can tell us the result of the predicate, we can
1707 : // return it quickly. But this is only a fastpath, and falling
1708 : // through would still be correct.
1709 341646 : const DataLayout &DL = CxtI->getModule()->getDataLayout();
1710 934619 : if (V->getType()->isPointerTy() && C->isNullValue() &&
1711 251327 : isKnownNonZero(V->stripPointerCasts(), DL)) {
1712 66867 : if (Pred == ICmpInst::ICMP_EQ)
1713 : return LazyValueInfo::False;
1714 2 : else if (Pred == ICmpInst::ICMP_NE)
1715 : return LazyValueInfo::True;
1716 : }
1717 274779 : ValueLatticeElement Result = getImpl(PImpl, AC, &DL, DT).getValueAt(V, CxtI);
1718 274779 : Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
1719 274779 : if (Ret != Unknown)
1720 : return Ret;
1721 :
1722 : // Note: The following bit of code is somewhat distinct from the rest of LVI;
1723 : // LVI as a whole tries to compute a lattice value which is conservatively
1724 : // correct at a given location. In this case, we have a predicate which we
1725 : // weren't able to prove about the merged result, and we're pushing that
1726 : // predicate back along each incoming edge to see if we can prove it
1727 : // separately for each input. As a motivating example, consider:
1728 : // bb1:
1729 : // %v1 = ... ; constantrange<1, 5>
1730 : // br label %merge
1731 : // bb2:
1732 : // %v2 = ... ; constantrange<10, 20>
1733 : // br label %merge
1734 : // merge:
1735 : // %phi = phi [%v1, %v2] ; constantrange<1,20>
1736 : // %pred = icmp eq i32 %phi, 8
1737 : // We can't tell from the lattice value for '%phi' that '%pred' is false
1738 : // along each path, but by checking the predicate over each input separately,
1739 : // we can.
1740 : // We limit the search to one step backwards from the current BB and value.
1741 : // We could consider extending this to search further backwards through the
1742 : // CFG and/or value graph, but there are non-obvious compile time vs quality
1743 : // tradeoffs.
1744 274662 : if (CxtI) {
1745 274662 : BasicBlock *BB = CxtI->getParent();
1746 :
1747 : // Function entry or an unreachable block. Bail to avoid confusing
1748 : // analysis below.
1749 274662 : pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1750 274662 : if (PI == PE)
1751 51357 : return Unknown;
1752 :
1753 : // If V is a PHI node in the same block as the context, we need to ask
1754 : // questions about the predicate as applied to the incoming value along
1755 : // each edge. This is useful for eliminating cases where the predicate is
1756 : // known along all incoming edges.
1757 : if (auto *PHI = dyn_cast<PHINode>(V))
1758 17836 : if (PHI->getParent() == BB) {
1759 : Tristate Baseline = Unknown;
1760 17864 : for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
1761 : Value *Incoming = PHI->getIncomingValue(i);
1762 : BasicBlock *PredBB = PHI->getIncomingBlock(i);
1763 : // Note that PredBB may be BB itself.
1764 17603 : Tristate Result = getPredicateOnEdge(Pred, Incoming, C, PredBB, BB,
1765 : CxtI);
1766 :
1767 : // Keep going as long as we've seen a consistent known result for
1768 : // all inputs.
1769 17603 : Baseline = (i == 0) ? Result /* First iteration */
1770 6093 : : (Baseline == Result ? Baseline : Unknown); /* All others */
1771 12002 : if (Baseline == Unknown)
1772 : break;
1773 : }
1774 11510 : if (Baseline != Unknown)
1775 : return Baseline;
1776 : }
1777 :
1778 : // For a comparison where the V is outside this block, it's possible
1779 : // that we've branched on it before. Look to see if the value is known
1780 : // on all incoming edges.
1781 226267 : if (!isa<Instruction>(V) ||
1782 206732 : cast<Instruction>(V)->getParent() != BB) {
1783 : // For predecessor edge, determine if the comparison is true or false
1784 : // on that edge. If they're all true or all false, we can conclude
1785 : // the value of the comparison in this block.
1786 50696 : Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1787 50696 : if (Baseline != Unknown) {
1788 : // Check that all remaining incoming values match the first one.
1789 4777 : while (++PI != PE) {
1790 1815 : Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1791 1815 : if (Ret != Baseline) break;
1792 : }
1793 : // If we terminated early, then one of the values didn't match.
1794 4090 : if (PI == PE) {
1795 : return Baseline;
1796 : }
1797 : }
1798 : }
1799 : }
1800 : return Unknown;
1801 : }
1802 :
1803 2531 : void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1804 : BasicBlock *NewSucc) {
1805 2531 : if (PImpl) {
1806 2525 : const DataLayout &DL = PredBB->getModule()->getDataLayout();
1807 2525 : getImpl(PImpl, AC, &DL, DT).threadEdge(PredBB, OldSucc, NewSucc);
1808 : }
1809 2531 : }
1810 :
1811 36487 : void LazyValueInfo::eraseBlock(BasicBlock *BB) {
1812 36487 : if (PImpl) {
1813 30650 : const DataLayout &DL = BB->getModule()->getDataLayout();
1814 30650 : getImpl(PImpl, AC, &DL, DT).eraseBlock(BB);
1815 : }
1816 36487 : }
1817 :
1818 :
1819 4 : void LazyValueInfo::printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) {
1820 4 : if (PImpl) {
1821 4 : getImpl(PImpl, AC, DL, DT).printLVI(F, DTree, OS);
1822 : }
1823 4 : }
1824 :
1825 204233 : void LazyValueInfo::disableDT() {
1826 204233 : if (PImpl)
1827 203820 : getImpl(PImpl, AC, DL, DT).disableDT();
1828 204233 : }
1829 :
1830 219783 : void LazyValueInfo::enableDT() {
1831 219783 : if (PImpl)
1832 131292 : getImpl(PImpl, AC, DL, DT).enableDT();
1833 219783 : }
1834 :
1835 : // Print the LVI for the function arguments at the start of each basic block.
1836 16 : void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(
1837 : const BasicBlock *BB, formatted_raw_ostream &OS) {
1838 : // Find if there are latticevalues defined for arguments of the function.
1839 16 : auto *F = BB->getParent();
1840 53 : for (auto &Arg : F->args()) {
1841 37 : ValueLatticeElement Result = LVIImpl->getValueInBlock(
1842 37 : const_cast<Argument *>(&Arg), const_cast<BasicBlock *>(BB));
1843 37 : if (Result.isUndefined())
1844 : continue;
1845 74 : OS << "; LatticeVal for: '" << Arg << "' is: " << Result << "\n";
1846 : }
1847 16 : }
1848 :
1849 : // This function prints the LVI analysis for the instruction I at the beginning
1850 : // of various basic blocks. It relies on calculated values that are stored in
1851 : // the LazyValueInfoCache, and in the absence of cached values, recalculate the
1852 : // LazyValueInfo for `I`, and print that info.
1853 43 : void LazyValueInfoAnnotatedWriter::emitInstructionAnnot(
1854 : const Instruction *I, formatted_raw_ostream &OS) {
1855 :
1856 43 : auto *ParentBB = I->getParent();
1857 : SmallPtrSet<const BasicBlock*, 16> BlocksContainingLVI;
1858 : // We can generate (solve) LVI values only for blocks that are dominated by
1859 : // the I's parent. However, to avoid generating LVI for all dominating blocks,
1860 : // that contain redundant/uninteresting information, we print LVI for
1861 : // blocks that may use this LVI information (such as immediate successor
1862 : // blocks, and blocks that contain uses of `I`).
1863 : auto printResult = [&](const BasicBlock *BB) {
1864 : if (!BlocksContainingLVI.insert(BB).second)
1865 : return;
1866 : ValueLatticeElement Result = LVIImpl->getValueInBlock(
1867 : const_cast<Instruction *>(I), const_cast<BasicBlock *>(BB));
1868 : OS << "; LatticeVal for: '" << *I << "' in BB: '";
1869 : BB->printAsOperand(OS, false);
1870 : OS << "' is: " << Result << "\n";
1871 43 : };
1872 :
1873 43 : printResult(ParentBB);
1874 : // Print the LVI analysis results for the immediate successor blocks, that
1875 : // are dominated by `ParentBB`.
1876 160 : for (auto *BBSucc : successors(ParentBB))
1877 74 : if (DT.dominates(ParentBB, BBSucc))
1878 39 : printResult(BBSucc);
1879 :
1880 : // Print LVI in blocks where `I` is used.
1881 69 : for (auto *U : I->users())
1882 : if (auto *UseI = dyn_cast<Instruction>(U))
1883 26 : if (!isa<PHINode>(UseI) || DT.dominates(ParentBB, UseI->getParent()))
1884 24 : printResult(UseI->getParent());
1885 :
1886 43 : }
1887 :
1888 : namespace {
1889 : // Printer class for LazyValueInfo results.
1890 : class LazyValueInfoPrinter : public FunctionPass {
1891 : public:
1892 : static char ID; // Pass identification, replacement for typeid
1893 0 : LazyValueInfoPrinter() : FunctionPass(ID) {
1894 0 : initializeLazyValueInfoPrinterPass(*PassRegistry::getPassRegistry());
1895 : }
1896 :
1897 0 : void getAnalysisUsage(AnalysisUsage &AU) const override {
1898 : AU.setPreservesAll();
1899 : AU.addRequired<LazyValueInfoWrapperPass>();
1900 : AU.addRequired<DominatorTreeWrapperPass>();
1901 0 : }
1902 :
1903 : // Get the mandatory dominator tree analysis and pass this in to the
1904 : // LVIPrinter. We cannot rely on the LVI's DT, since it's optional.
1905 0 : bool runOnFunction(Function &F) override {
1906 0 : dbgs() << "LVI for function '" << F.getName() << "':\n";
1907 0 : auto &LVI = getAnalysis<LazyValueInfoWrapperPass>().getLVI();
1908 0 : auto &DTree = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1909 0 : LVI.printLVI(F, DTree, dbgs());
1910 0 : return false;
1911 : }
1912 : };
1913 : }
1914 :
1915 : char LazyValueInfoPrinter::ID = 0;
1916 10756 : INITIALIZE_PASS_BEGIN(LazyValueInfoPrinter, "print-lazy-value-info",
1917 : "Lazy Value Info Printer Pass", false, false)
1918 10756 : INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
1919 21512 : INITIALIZE_PASS_END(LazyValueInfoPrinter, "print-lazy-value-info",
1920 : "Lazy Value Info Printer Pass", false, false)
|
