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/TargetLibraryInfo.h" 21 #include "llvm/Analysis/ValueTracking.h" 22 #include "llvm/IR/CFG.h" 23 #include "llvm/IR/ConstantRange.h" 24 #include "llvm/IR/Constants.h" 25 #include "llvm/IR/DataLayout.h" 26 #include "llvm/IR/Dominators.h" 27 #include "llvm/IR/Instructions.h" 28 #include "llvm/IR/IntrinsicInst.h" 29 #include "llvm/IR/LLVMContext.h" 30 #include "llvm/IR/PatternMatch.h" 31 #include "llvm/IR/ValueHandle.h" 32 #include "llvm/Support/Debug.h" 33 #include "llvm/Support/raw_ostream.h" 34 #include <map> 35 #include <stack> 36 using namespace llvm; 37 using namespace PatternMatch; 38 39 #define DEBUG_TYPE "lazy-value-info" 40 41 char LazyValueInfoWrapperPass::ID = 0; 42 INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info", 43 "Lazy Value Information Analysis", false, true) 44 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 45 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 46 INITIALIZE_PASS_END(LazyValueInfoWrapperPass, "lazy-value-info", 47 "Lazy Value Information Analysis", false, true) 48 49 namespace llvm { 50 FunctionPass *createLazyValueInfoPass() { return new LazyValueInfoWrapperPass(); } 51 } 52 53 char LazyValueAnalysis::PassID; 54 55 //===----------------------------------------------------------------------===// 56 // LVILatticeVal 57 //===----------------------------------------------------------------------===// 58 59 /// This is the information tracked by LazyValueInfo for each value. 60 /// 61 /// FIXME: This is basically just for bringup, this can be made a lot more rich 62 /// in the future. 63 /// 64 namespace { 65 class LVILatticeVal { 66 enum LatticeValueTy { 67 /// This Value has no known value yet. As a result, this implies the 68 /// producing instruction is dead. Caution: We use this as the starting 69 /// state in our local meet rules. In this usage, it's taken to mean 70 /// "nothing known yet". 71 undefined, 72 73 /// This Value has a specific constant value. (For integers, constantrange 74 /// is used instead.) 75 constant, 76 77 /// This Value is known to not have the specified value. (For integers, 78 /// constantrange is used instead.) 79 notconstant, 80 81 /// The Value falls within this range. (Used only for integer typed values.) 82 constantrange, 83 84 /// We can not precisely model the dynamic values this value might take. 85 overdefined 86 }; 87 88 /// Val: This stores the current lattice value along with the Constant* for 89 /// the constant if this is a 'constant' or 'notconstant' value. 90 LatticeValueTy Tag; 91 Constant *Val; 92 ConstantRange Range; 93 94 public: 95 LVILatticeVal() : Tag(undefined), Val(nullptr), Range(1, true) {} 96 97 static LVILatticeVal get(Constant *C) { 98 LVILatticeVal Res; 99 if (!isa<UndefValue>(C)) 100 Res.markConstant(C); 101 return Res; 102 } 103 static LVILatticeVal getNot(Constant *C) { 104 LVILatticeVal Res; 105 if (!isa<UndefValue>(C)) 106 Res.markNotConstant(C); 107 return Res; 108 } 109 static LVILatticeVal getRange(ConstantRange CR) { 110 LVILatticeVal Res; 111 Res.markConstantRange(std::move(CR)); 112 return Res; 113 } 114 static LVILatticeVal getOverdefined() { 115 LVILatticeVal Res; 116 Res.markOverdefined(); 117 return Res; 118 } 119 120 bool isUndefined() const { return Tag == undefined; } 121 bool isConstant() const { return Tag == constant; } 122 bool isNotConstant() const { return Tag == notconstant; } 123 bool isConstantRange() const { return Tag == constantrange; } 124 bool isOverdefined() const { return Tag == overdefined; } 125 126 Constant *getConstant() const { 127 assert(isConstant() && "Cannot get the constant of a non-constant!"); 128 return Val; 129 } 130 131 Constant *getNotConstant() const { 132 assert(isNotConstant() && "Cannot get the constant of a non-notconstant!"); 133 return Val; 134 } 135 136 ConstantRange getConstantRange() const { 137 assert(isConstantRange() && 138 "Cannot get the constant-range of a non-constant-range!"); 139 return Range; 140 } 141 142 /// Return true if this is a change in status. 143 bool markOverdefined() { 144 if (isOverdefined()) 145 return false; 146 Tag = overdefined; 147 return true; 148 } 149 150 /// Return true if this is a change in status. 151 bool markConstant(Constant *V) { 152 assert(V && "Marking constant with NULL"); 153 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) 154 return markConstantRange(ConstantRange(CI->getValue())); 155 if (isa<UndefValue>(V)) 156 return false; 157 158 assert((!isConstant() || getConstant() == V) && 159 "Marking constant with different value"); 160 assert(isUndefined()); 161 Tag = constant; 162 Val = V; 163 return true; 164 } 165 166 /// Return true if this is a change in status. 167 bool markNotConstant(Constant *V) { 168 assert(V && "Marking constant with NULL"); 169 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) 170 return markConstantRange(ConstantRange(CI->getValue()+1, CI->getValue())); 171 if (isa<UndefValue>(V)) 172 return false; 173 174 assert((!isConstant() || getConstant() != V) && 175 "Marking constant !constant with same value"); 176 assert((!isNotConstant() || getNotConstant() == V) && 177 "Marking !constant with different value"); 178 assert(isUndefined() || isConstant()); 179 Tag = notconstant; 180 Val = V; 181 return true; 182 } 183 184 /// Return true if this is a change in status. 185 bool markConstantRange(ConstantRange NewR) { 186 if (isConstantRange()) { 187 if (NewR.isEmptySet()) 188 return markOverdefined(); 189 190 bool changed = Range != NewR; 191 Range = std::move(NewR); 192 return changed; 193 } 194 195 assert(isUndefined()); 196 if (NewR.isEmptySet()) 197 return markOverdefined(); 198 199 Tag = constantrange; 200 Range = std::move(NewR); 201 return true; 202 } 203 204 /// Merge the specified lattice value into this one, updating this 205 /// one and returning true if anything changed. 206 bool mergeIn(const LVILatticeVal &RHS, const DataLayout &DL) { 207 if (RHS.isUndefined() || isOverdefined()) return false; 208 if (RHS.isOverdefined()) return markOverdefined(); 209 210 if (isUndefined()) { 211 Tag = RHS.Tag; 212 Val = RHS.Val; 213 Range = RHS.Range; 214 return true; 215 } 216 217 if (isConstant()) { 218 if (RHS.isConstant()) { 219 if (Val == RHS.Val) 220 return false; 221 return markOverdefined(); 222 } 223 224 if (RHS.isNotConstant()) { 225 if (Val == RHS.Val) 226 return markOverdefined(); 227 228 // Unless we can prove that the two Constants are different, we must 229 // move to overdefined. 230 if (ConstantInt *Res = 231 dyn_cast<ConstantInt>(ConstantFoldCompareInstOperands( 232 CmpInst::ICMP_NE, getConstant(), RHS.getNotConstant(), DL))) 233 if (Res->isOne()) 234 return markNotConstant(RHS.getNotConstant()); 235 236 return markOverdefined(); 237 } 238 239 return markOverdefined(); 240 } 241 242 if (isNotConstant()) { 243 if (RHS.isConstant()) { 244 if (Val == RHS.Val) 245 return markOverdefined(); 246 247 // Unless we can prove that the two Constants are different, we must 248 // move to overdefined. 249 if (ConstantInt *Res = 250 dyn_cast<ConstantInt>(ConstantFoldCompareInstOperands( 251 CmpInst::ICMP_NE, getNotConstant(), RHS.getConstant(), DL))) 252 if (Res->isOne()) 253 return false; 254 255 return markOverdefined(); 256 } 257 258 if (RHS.isNotConstant()) { 259 if (Val == RHS.Val) 260 return false; 261 return markOverdefined(); 262 } 263 264 return markOverdefined(); 265 } 266 267 assert(isConstantRange() && "New LVILattice type?"); 268 if (!RHS.isConstantRange()) 269 return markOverdefined(); 270 271 ConstantRange NewR = Range.unionWith(RHS.getConstantRange()); 272 if (NewR.isFullSet()) 273 return markOverdefined(); 274 return markConstantRange(NewR); 275 } 276 }; 277 278 } // end anonymous namespace. 279 280 namespace llvm { 281 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) 282 LLVM_ATTRIBUTE_USED; 283 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) { 284 if (Val.isUndefined()) 285 return OS << "undefined"; 286 if (Val.isOverdefined()) 287 return OS << "overdefined"; 288 289 if (Val.isNotConstant()) 290 return OS << "notconstant<" << *Val.getNotConstant() << '>'; 291 if (Val.isConstantRange()) 292 return OS << "constantrange<" << Val.getConstantRange().getLower() << ", " 293 << Val.getConstantRange().getUpper() << '>'; 294 return OS << "constant<" << *Val.getConstant() << '>'; 295 } 296 } 297 298 /// Returns true if this lattice value represents at most one possible value. 299 /// This is as precise as any lattice value can get while still representing 300 /// reachable code. 301 static bool hasSingleValue(const LVILatticeVal &Val) { 302 if (Val.isConstantRange() && 303 Val.getConstantRange().isSingleElement()) 304 // Integer constants are single element ranges 305 return true; 306 if (Val.isConstant()) 307 // Non integer constants 308 return true; 309 return false; 310 } 311 312 /// Combine two sets of facts about the same value into a single set of 313 /// facts. Note that this method is not suitable for merging facts along 314 /// different paths in a CFG; that's what the mergeIn function is for. This 315 /// is for merging facts gathered about the same value at the same location 316 /// through two independent means. 317 /// Notes: 318 /// * This method does not promise to return the most precise possible lattice 319 /// value implied by A and B. It is allowed to return any lattice element 320 /// which is at least as strong as *either* A or B (unless our facts 321 /// conflict, see below). 322 /// * Due to unreachable code, the intersection of two lattice values could be 323 /// contradictory. If this happens, we return some valid lattice value so as 324 /// not confuse the rest of LVI. Ideally, we'd always return Undefined, but 325 /// we do not make this guarantee. TODO: This would be a useful enhancement. 326 static LVILatticeVal intersect(LVILatticeVal A, LVILatticeVal B) { 327 // Undefined is the strongest state. It means the value is known to be along 328 // an unreachable path. 329 if (A.isUndefined()) 330 return A; 331 if (B.isUndefined()) 332 return B; 333 334 // If we gave up for one, but got a useable fact from the other, use it. 335 if (A.isOverdefined()) 336 return B; 337 if (B.isOverdefined()) 338 return A; 339 340 // Can't get any more precise than constants. 341 if (hasSingleValue(A)) 342 return A; 343 if (hasSingleValue(B)) 344 return B; 345 346 // Could be either constant range or not constant here. 347 if (!A.isConstantRange() || !B.isConstantRange()) { 348 // TODO: Arbitrary choice, could be improved 349 return A; 350 } 351 352 // Intersect two constant ranges 353 ConstantRange Range = 354 A.getConstantRange().intersectWith(B.getConstantRange()); 355 // Note: An empty range is implicitly converted to overdefined internally. 356 // TODO: We could instead use Undefined here since we've proven a conflict 357 // and thus know this path must be unreachable. 358 return LVILatticeVal::getRange(std::move(Range)); 359 } 360 361 //===----------------------------------------------------------------------===// 362 // LazyValueInfoCache Decl 363 //===----------------------------------------------------------------------===// 364 365 namespace { 366 /// A callback value handle updates the cache when values are erased. 367 class LazyValueInfoCache; 368 struct LVIValueHandle final : public CallbackVH { 369 LazyValueInfoCache *Parent; 370 371 LVIValueHandle(Value *V, LazyValueInfoCache *P) 372 : CallbackVH(V), Parent(P) { } 373 374 void deleted() override; 375 void allUsesReplacedWith(Value *V) override { 376 deleted(); 377 } 378 }; 379 } 380 381 namespace { 382 /// This is the cache kept by LazyValueInfo which 383 /// maintains information about queries across the clients' queries. 384 class LazyValueInfoCache { 385 /// This is all of the cached block information for exactly one Value*. 386 /// The entries are sorted by the BasicBlock* of the 387 /// entries, allowing us to do a lookup with a binary search. 388 /// Over-defined lattice values are recorded in OverDefinedCache to reduce 389 /// memory overhead. 390 typedef SmallDenseMap<AssertingVH<BasicBlock>, LVILatticeVal, 4> 391 ValueCacheEntryTy; 392 393 /// This is all of the cached information for all values, 394 /// mapped from Value* to key information. 395 std::map<LVIValueHandle, ValueCacheEntryTy> ValueCache; 396 397 /// This tracks, on a per-block basis, the set of values that are 398 /// over-defined at the end of that block. 399 typedef DenseMap<AssertingVH<BasicBlock>, SmallPtrSet<Value *, 4>> 400 OverDefinedCacheTy; 401 OverDefinedCacheTy OverDefinedCache; 402 403 /// Keep track of all blocks that we have ever seen, so we 404 /// don't spend time removing unused blocks from our caches. 405 DenseSet<AssertingVH<BasicBlock> > SeenBlocks; 406 407 /// This stack holds the state of the value solver during a query. 408 /// It basically emulates the callstack of the naive 409 /// recursive value lookup process. 410 std::stack<std::pair<BasicBlock*, Value*> > BlockValueStack; 411 412 /// Keeps track of which block-value pairs are in BlockValueStack. 413 DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet; 414 415 /// Push BV onto BlockValueStack unless it's already in there. 416 /// Returns true on success. 417 bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) { 418 if (!BlockValueSet.insert(BV).second) 419 return false; // It's already in the stack. 420 421 DEBUG(dbgs() << "PUSH: " << *BV.second << " in " << BV.first->getName() 422 << "\n"); 423 BlockValueStack.push(BV); 424 return true; 425 } 426 427 AssumptionCache *AC; ///< A pointer to the cache of @llvm.assume calls. 428 const DataLayout &DL; ///< A mandatory DataLayout 429 DominatorTree *DT; ///< An optional DT pointer. 430 431 friend struct LVIValueHandle; 432 433 void insertResult(Value *Val, BasicBlock *BB, const LVILatticeVal &Result) { 434 SeenBlocks.insert(BB); 435 436 // Insert over-defined values into their own cache to reduce memory 437 // overhead. 438 if (Result.isOverdefined()) 439 OverDefinedCache[BB].insert(Val); 440 else 441 lookup(Val)[BB] = Result; 442 } 443 444 LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB); 445 bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T, 446 LVILatticeVal &Result, Instruction *CxtI = nullptr); 447 bool hasBlockValue(Value *Val, BasicBlock *BB); 448 449 // These methods process one work item and may add more. A false value 450 // returned means that the work item was not completely processed and must 451 // be revisited after going through the new items. 452 bool solveBlockValue(Value *Val, BasicBlock *BB); 453 bool solveBlockValueNonLocal(LVILatticeVal &BBLV, Value *Val, BasicBlock *BB); 454 bool solveBlockValuePHINode(LVILatticeVal &BBLV, PHINode *PN, BasicBlock *BB); 455 bool solveBlockValueSelect(LVILatticeVal &BBLV, SelectInst *S, 456 BasicBlock *BB); 457 bool solveBlockValueBinaryOp(LVILatticeVal &BBLV, Instruction *BBI, 458 BasicBlock *BB); 459 bool solveBlockValueCast(LVILatticeVal &BBLV, Instruction *BBI, 460 BasicBlock *BB); 461 void intersectAssumeBlockValueConstantRange(Value *Val, LVILatticeVal &BBLV, 462 Instruction *BBI); 463 464 void solve(); 465 466 ValueCacheEntryTy &lookup(Value *V) { 467 return ValueCache[LVIValueHandle(V, this)]; 468 } 469 470 bool isOverdefined(Value *V, BasicBlock *BB) const { 471 auto ODI = OverDefinedCache.find(BB); 472 473 if (ODI == OverDefinedCache.end()) 474 return false; 475 476 return ODI->second.count(V); 477 } 478 479 bool hasCachedValueInfo(Value *V, BasicBlock *BB) { 480 if (isOverdefined(V, BB)) 481 return true; 482 483 LVIValueHandle ValHandle(V, this); 484 auto I = ValueCache.find(ValHandle); 485 if (I == ValueCache.end()) 486 return false; 487 488 return I->second.count(BB); 489 } 490 491 LVILatticeVal getCachedValueInfo(Value *V, BasicBlock *BB) { 492 if (isOverdefined(V, BB)) 493 return LVILatticeVal::getOverdefined(); 494 495 return lookup(V)[BB]; 496 } 497 498 public: 499 /// This is the query interface to determine the lattice 500 /// value for the specified Value* at the end of the specified block. 501 LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB, 502 Instruction *CxtI = nullptr); 503 504 /// This is the query interface to determine the lattice 505 /// value for the specified Value* at the specified instruction (generally 506 /// from an assume intrinsic). 507 LVILatticeVal getValueAt(Value *V, Instruction *CxtI); 508 509 /// This is the query interface to determine the lattice 510 /// value for the specified Value* that is true on the specified edge. 511 LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB, 512 Instruction *CxtI = nullptr); 513 514 /// This is the update interface to inform the cache that an edge from 515 /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc. 516 void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc); 517 518 /// This is part of the update interface to inform the cache 519 /// that a block has been deleted. 520 void eraseBlock(BasicBlock *BB); 521 522 /// clear - Empty the cache. 523 void clear() { 524 SeenBlocks.clear(); 525 ValueCache.clear(); 526 OverDefinedCache.clear(); 527 } 528 529 LazyValueInfoCache(AssumptionCache *AC, const DataLayout &DL, 530 DominatorTree *DT = nullptr) 531 : AC(AC), DL(DL), DT(DT) {} 532 }; 533 } // end anonymous namespace 534 535 void LVIValueHandle::deleted() { 536 SmallVector<AssertingVH<BasicBlock>, 4> ToErase; 537 for (auto &I : Parent->OverDefinedCache) { 538 SmallPtrSetImpl<Value *> &ValueSet = I.second; 539 if (ValueSet.count(getValPtr())) 540 ValueSet.erase(getValPtr()); 541 if (ValueSet.empty()) 542 ToErase.push_back(I.first); 543 } 544 for (auto &BB : ToErase) 545 Parent->OverDefinedCache.erase(BB); 546 547 // This erasure deallocates *this, so it MUST happen after we're done 548 // using any and all members of *this. 549 Parent->ValueCache.erase(*this); 550 } 551 552 void LazyValueInfoCache::eraseBlock(BasicBlock *BB) { 553 // Shortcut if we have never seen this block. 554 DenseSet<AssertingVH<BasicBlock> >::iterator I = SeenBlocks.find(BB); 555 if (I == SeenBlocks.end()) 556 return; 557 SeenBlocks.erase(I); 558 559 auto ODI = OverDefinedCache.find(BB); 560 if (ODI != OverDefinedCache.end()) 561 OverDefinedCache.erase(ODI); 562 563 for (auto &I : ValueCache) 564 I.second.erase(BB); 565 } 566 567 void LazyValueInfoCache::solve() { 568 while (!BlockValueStack.empty()) { 569 std::pair<BasicBlock*, Value*> &e = BlockValueStack.top(); 570 assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!"); 571 572 if (solveBlockValue(e.second, e.first)) { 573 // The work item was completely processed. 574 assert(BlockValueStack.top() == e && "Nothing should have been pushed!"); 575 assert(hasCachedValueInfo(e.second, e.first) && 576 "Result should be in cache!"); 577 578 DEBUG(dbgs() << "POP " << *e.second << " in " << e.first->getName() 579 << " = " << getCachedValueInfo(e.second, e.first) << "\n"); 580 581 BlockValueStack.pop(); 582 BlockValueSet.erase(e); 583 } else { 584 // More work needs to be done before revisiting. 585 assert(BlockValueStack.top() != e && "Stack should have been pushed!"); 586 } 587 } 588 } 589 590 bool LazyValueInfoCache::hasBlockValue(Value *Val, BasicBlock *BB) { 591 // If already a constant, there is nothing to compute. 592 if (isa<Constant>(Val)) 593 return true; 594 595 return hasCachedValueInfo(Val, BB); 596 } 597 598 LVILatticeVal LazyValueInfoCache::getBlockValue(Value *Val, BasicBlock *BB) { 599 // If already a constant, there is nothing to compute. 600 if (Constant *VC = dyn_cast<Constant>(Val)) 601 return LVILatticeVal::get(VC); 602 603 SeenBlocks.insert(BB); 604 return getCachedValueInfo(Val, BB); 605 } 606 607 static LVILatticeVal getFromRangeMetadata(Instruction *BBI) { 608 switch (BBI->getOpcode()) { 609 default: break; 610 case Instruction::Load: 611 case Instruction::Call: 612 case Instruction::Invoke: 613 if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range)) 614 if (isa<IntegerType>(BBI->getType())) { 615 return LVILatticeVal::getRange(getConstantRangeFromMetadata(*Ranges)); 616 } 617 break; 618 }; 619 // Nothing known - will be intersected with other facts 620 return LVILatticeVal::getOverdefined(); 621 } 622 623 bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) { 624 if (isa<Constant>(Val)) 625 return true; 626 627 if (hasCachedValueInfo(Val, BB)) { 628 // If we have a cached value, use that. 629 DEBUG(dbgs() << " reuse BB '" << BB->getName() 630 << "' val=" << getCachedValueInfo(Val, BB) << '\n'); 631 632 // Since we're reusing a cached value, we don't need to update the 633 // OverDefinedCache. The cache will have been properly updated whenever the 634 // cached value was inserted. 635 return true; 636 } 637 638 // Hold off inserting this value into the Cache in case we have to return 639 // false and come back later. 640 LVILatticeVal Res; 641 642 Instruction *BBI = dyn_cast<Instruction>(Val); 643 if (!BBI || BBI->getParent() != BB) { 644 if (!solveBlockValueNonLocal(Res, Val, BB)) 645 return false; 646 insertResult(Val, BB, Res); 647 return true; 648 } 649 650 if (PHINode *PN = dyn_cast<PHINode>(BBI)) { 651 if (!solveBlockValuePHINode(Res, PN, BB)) 652 return false; 653 insertResult(Val, BB, Res); 654 return true; 655 } 656 657 if (auto *SI = dyn_cast<SelectInst>(BBI)) { 658 if (!solveBlockValueSelect(Res, SI, BB)) 659 return false; 660 insertResult(Val, BB, Res); 661 return true; 662 } 663 664 // If this value is a nonnull pointer, record it's range and bailout. Note 665 // that for all other pointer typed values, we terminate the search at the 666 // definition. We could easily extend this to look through geps, bitcasts, 667 // and the like to prove non-nullness, but it's not clear that's worth it 668 // compile time wise. The context-insensative value walk done inside 669 // isKnownNonNull gets most of the profitable cases at much less expense. 670 // This does mean that we have a sensativity to where the defining 671 // instruction is placed, even if it could legally be hoisted much higher. 672 // That is unfortunate. 673 PointerType *PT = dyn_cast<PointerType>(BBI->getType()); 674 if (PT && isKnownNonNull(BBI)) { 675 Res = LVILatticeVal::getNot(ConstantPointerNull::get(PT)); 676 insertResult(Val, BB, Res); 677 return true; 678 } 679 if (BBI->getType()->isIntegerTy()) { 680 if (isa<CastInst>(BBI)) { 681 if (!solveBlockValueCast(Res, BBI, BB)) 682 return false; 683 insertResult(Val, BB, Res); 684 return true; 685 } 686 BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI); 687 if (BO && isa<ConstantInt>(BO->getOperand(1))) { 688 if (!solveBlockValueBinaryOp(Res, BBI, BB)) 689 return false; 690 insertResult(Val, BB, Res); 691 return true; 692 } 693 } 694 695 DEBUG(dbgs() << " compute BB '" << BB->getName() 696 << "' - unknown inst def found.\n"); 697 Res = getFromRangeMetadata(BBI); 698 insertResult(Val, BB, Res); 699 return true; 700 } 701 702 static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) { 703 if (LoadInst *L = dyn_cast<LoadInst>(I)) { 704 return L->getPointerAddressSpace() == 0 && 705 GetUnderlyingObject(L->getPointerOperand(), 706 L->getModule()->getDataLayout()) == Ptr; 707 } 708 if (StoreInst *S = dyn_cast<StoreInst>(I)) { 709 return S->getPointerAddressSpace() == 0 && 710 GetUnderlyingObject(S->getPointerOperand(), 711 S->getModule()->getDataLayout()) == Ptr; 712 } 713 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) { 714 if (MI->isVolatile()) return false; 715 716 // FIXME: check whether it has a valuerange that excludes zero? 717 ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength()); 718 if (!Len || Len->isZero()) return false; 719 720 if (MI->getDestAddressSpace() == 0) 721 if (GetUnderlyingObject(MI->getRawDest(), 722 MI->getModule()->getDataLayout()) == Ptr) 723 return true; 724 if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) 725 if (MTI->getSourceAddressSpace() == 0) 726 if (GetUnderlyingObject(MTI->getRawSource(), 727 MTI->getModule()->getDataLayout()) == Ptr) 728 return true; 729 } 730 return false; 731 } 732 733 /// Return true if the allocation associated with Val is ever dereferenced 734 /// within the given basic block. This establishes the fact Val is not null, 735 /// but does not imply that the memory at Val is dereferenceable. (Val may 736 /// point off the end of the dereferenceable part of the object.) 737 static bool isObjectDereferencedInBlock(Value *Val, BasicBlock *BB) { 738 assert(Val->getType()->isPointerTy()); 739 740 const DataLayout &DL = BB->getModule()->getDataLayout(); 741 Value *UnderlyingVal = GetUnderlyingObject(Val, DL); 742 // If 'GetUnderlyingObject' didn't converge, skip it. It won't converge 743 // inside InstructionDereferencesPointer either. 744 if (UnderlyingVal == GetUnderlyingObject(UnderlyingVal, DL, 1)) 745 for (Instruction &I : *BB) 746 if (InstructionDereferencesPointer(&I, UnderlyingVal)) 747 return true; 748 return false; 749 } 750 751 bool LazyValueInfoCache::solveBlockValueNonLocal(LVILatticeVal &BBLV, 752 Value *Val, BasicBlock *BB) { 753 LVILatticeVal Result; // Start Undefined. 754 755 // If this is the entry block, we must be asking about an argument. The 756 // value is overdefined. 757 if (BB == &BB->getParent()->getEntryBlock()) { 758 assert(isa<Argument>(Val) && "Unknown live-in to the entry block"); 759 // Bofore giving up, see if we can prove the pointer non-null local to 760 // this particular block. 761 if (Val->getType()->isPointerTy() && 762 (isKnownNonNull(Val) || isObjectDereferencedInBlock(Val, BB))) { 763 PointerType *PTy = cast<PointerType>(Val->getType()); 764 Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy)); 765 } else { 766 Result.markOverdefined(); 767 } 768 BBLV = Result; 769 return true; 770 } 771 772 // Loop over all of our predecessors, merging what we know from them into 773 // result. 774 bool EdgesMissing = false; 775 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 776 LVILatticeVal EdgeResult; 777 EdgesMissing |= !getEdgeValue(Val, *PI, BB, EdgeResult); 778 if (EdgesMissing) 779 continue; 780 781 Result.mergeIn(EdgeResult, DL); 782 783 // If we hit overdefined, exit early. The BlockVals entry is already set 784 // to overdefined. 785 if (Result.isOverdefined()) { 786 DEBUG(dbgs() << " compute BB '" << BB->getName() 787 << "' - overdefined because of pred (non local).\n"); 788 // Bofore giving up, see if we can prove the pointer non-null local to 789 // this particular block. 790 if (Val->getType()->isPointerTy() && 791 isObjectDereferencedInBlock(Val, BB)) { 792 PointerType *PTy = cast<PointerType>(Val->getType()); 793 Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy)); 794 } 795 796 BBLV = Result; 797 return true; 798 } 799 } 800 if (EdgesMissing) 801 return false; 802 803 // Return the merged value, which is more precise than 'overdefined'. 804 assert(!Result.isOverdefined()); 805 BBLV = Result; 806 return true; 807 } 808 809 bool LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV, 810 PHINode *PN, BasicBlock *BB) { 811 LVILatticeVal Result; // Start Undefined. 812 813 // Loop over all of our predecessors, merging what we know from them into 814 // result. 815 bool EdgesMissing = false; 816 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 817 BasicBlock *PhiBB = PN->getIncomingBlock(i); 818 Value *PhiVal = PN->getIncomingValue(i); 819 LVILatticeVal EdgeResult; 820 // Note that we can provide PN as the context value to getEdgeValue, even 821 // though the results will be cached, because PN is the value being used as 822 // the cache key in the caller. 823 EdgesMissing |= !getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN); 824 if (EdgesMissing) 825 continue; 826 827 Result.mergeIn(EdgeResult, DL); 828 829 // If we hit overdefined, exit early. The BlockVals entry is already set 830 // to overdefined. 831 if (Result.isOverdefined()) { 832 DEBUG(dbgs() << " compute BB '" << BB->getName() 833 << "' - overdefined because of pred (local).\n"); 834 835 BBLV = Result; 836 return true; 837 } 838 } 839 if (EdgesMissing) 840 return false; 841 842 // Return the merged value, which is more precise than 'overdefined'. 843 assert(!Result.isOverdefined() && "Possible PHI in entry block?"); 844 BBLV = Result; 845 return true; 846 } 847 848 static bool getValueFromFromCondition(Value *Val, ICmpInst *ICI, 849 LVILatticeVal &Result, 850 bool isTrueDest = true); 851 852 // If we can determine a constraint on the value given conditions assumed by 853 // the program, intersect those constraints with BBLV 854 void LazyValueInfoCache::intersectAssumeBlockValueConstantRange(Value *Val, 855 LVILatticeVal &BBLV, 856 Instruction *BBI) { 857 BBI = BBI ? BBI : dyn_cast<Instruction>(Val); 858 if (!BBI) 859 return; 860 861 for (auto &AssumeVH : AC->assumptions()) { 862 if (!AssumeVH) 863 continue; 864 auto *I = cast<CallInst>(AssumeVH); 865 if (!isValidAssumeForContext(I, BBI, DT)) 866 continue; 867 868 Value *C = I->getArgOperand(0); 869 if (ICmpInst *ICI = dyn_cast<ICmpInst>(C)) { 870 LVILatticeVal Result; 871 if (getValueFromFromCondition(Val, ICI, Result)) 872 BBLV = intersect(BBLV, Result); 873 } 874 } 875 } 876 877 bool LazyValueInfoCache::solveBlockValueSelect(LVILatticeVal &BBLV, 878 SelectInst *SI, BasicBlock *BB) { 879 880 // Recurse on our inputs if needed 881 if (!hasBlockValue(SI->getTrueValue(), BB)) { 882 if (pushBlockValue(std::make_pair(BB, SI->getTrueValue()))) 883 return false; 884 BBLV.markOverdefined(); 885 return true; 886 } 887 LVILatticeVal TrueVal = getBlockValue(SI->getTrueValue(), BB); 888 // If we hit overdefined, don't ask more queries. We want to avoid poisoning 889 // extra slots in the table if we can. 890 if (TrueVal.isOverdefined()) { 891 BBLV.markOverdefined(); 892 return true; 893 } 894 895 if (!hasBlockValue(SI->getFalseValue(), BB)) { 896 if (pushBlockValue(std::make_pair(BB, SI->getFalseValue()))) 897 return false; 898 BBLV.markOverdefined(); 899 return true; 900 } 901 LVILatticeVal FalseVal = getBlockValue(SI->getFalseValue(), BB); 902 // If we hit overdefined, don't ask more queries. We want to avoid poisoning 903 // extra slots in the table if we can. 904 if (FalseVal.isOverdefined()) { 905 BBLV.markOverdefined(); 906 return true; 907 } 908 909 if (TrueVal.isConstantRange() && FalseVal.isConstantRange()) { 910 ConstantRange TrueCR = TrueVal.getConstantRange(); 911 ConstantRange FalseCR = FalseVal.getConstantRange(); 912 Value *LHS = nullptr; 913 Value *RHS = nullptr; 914 SelectPatternResult SPR = matchSelectPattern(SI, LHS, RHS); 915 // Is this a min specifically of our two inputs? (Avoid the risk of 916 // ValueTracking getting smarter looking back past our immediate inputs.) 917 if (SelectPatternResult::isMinOrMax(SPR.Flavor) && 918 LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) { 919 switch (SPR.Flavor) { 920 default: 921 llvm_unreachable("unexpected minmax type!"); 922 case SPF_SMIN: /// Signed minimum 923 BBLV.markConstantRange(TrueCR.smin(FalseCR)); 924 return true; 925 case SPF_UMIN: /// Unsigned minimum 926 BBLV.markConstantRange(TrueCR.umin(FalseCR)); 927 return true; 928 case SPF_SMAX: /// Signed maximum 929 BBLV.markConstantRange(TrueCR.smax(FalseCR)); 930 return true; 931 case SPF_UMAX: /// Unsigned maximum 932 BBLV.markConstantRange(TrueCR.umax(FalseCR)); 933 return true; 934 }; 935 } 936 937 // TODO: ABS, NABS from the SelectPatternResult 938 } 939 940 // Can we constrain the facts about the true and false values by using the 941 // condition itself? This shows up with idioms like e.g. select(a > 5, a, 5). 942 // TODO: We could potentially refine an overdefined true value above. 943 if (auto *ICI = dyn_cast<ICmpInst>(SI->getCondition())) { 944 LVILatticeVal TrueValTaken, FalseValTaken; 945 if (!getValueFromFromCondition(SI->getTrueValue(), ICI, 946 TrueValTaken, true)) 947 TrueValTaken.markOverdefined(); 948 if (!getValueFromFromCondition(SI->getFalseValue(), ICI, 949 FalseValTaken, false)) 950 FalseValTaken.markOverdefined(); 951 952 TrueVal = intersect(TrueVal, TrueValTaken); 953 FalseVal = intersect(FalseVal, FalseValTaken); 954 955 956 // Handle clamp idioms such as: 957 // %24 = constantrange<0, 17> 958 // %39 = icmp eq i32 %24, 0 959 // %40 = add i32 %24, -1 960 // %siv.next = select i1 %39, i32 16, i32 %40 961 // %siv.next = constantrange<0, 17> not <-1, 17> 962 // In general, this can handle any clamp idiom which tests the edge 963 // condition via an equality or inequality. 964 ICmpInst::Predicate Pred = ICI->getPredicate(); 965 Value *A = ICI->getOperand(0); 966 if (ConstantInt *CIBase = dyn_cast<ConstantInt>(ICI->getOperand(1))) { 967 auto addConstants = [](ConstantInt *A, ConstantInt *B) { 968 assert(A->getType() == B->getType()); 969 return ConstantInt::get(A->getType(), A->getValue() + B->getValue()); 970 }; 971 // See if either input is A + C2, subject to the constraint from the 972 // condition that A != C when that input is used. We can assume that 973 // that input doesn't include C + C2. 974 ConstantInt *CIAdded; 975 switch (Pred) { 976 default: break; 977 case ICmpInst::ICMP_EQ: 978 if (match(SI->getFalseValue(), m_Add(m_Specific(A), 979 m_ConstantInt(CIAdded)))) { 980 auto ResNot = addConstants(CIBase, CIAdded); 981 FalseVal = intersect(FalseVal, 982 LVILatticeVal::getNot(ResNot)); 983 } 984 break; 985 case ICmpInst::ICMP_NE: 986 if (match(SI->getTrueValue(), m_Add(m_Specific(A), 987 m_ConstantInt(CIAdded)))) { 988 auto ResNot = addConstants(CIBase, CIAdded); 989 TrueVal = intersect(TrueVal, 990 LVILatticeVal::getNot(ResNot)); 991 } 992 break; 993 }; 994 } 995 } 996 997 LVILatticeVal Result; // Start Undefined. 998 Result.mergeIn(TrueVal, DL); 999 Result.mergeIn(FalseVal, DL); 1000 BBLV = Result; 1001 return true; 1002 } 1003 1004 bool LazyValueInfoCache::solveBlockValueCast(LVILatticeVal &BBLV, 1005 Instruction *BBI, 1006 BasicBlock *BB) { 1007 if (!BBI->getOperand(0)->getType()->isSized()) { 1008 // Without knowing how wide the input is, we can't analyze it in any useful 1009 // way. 1010 BBLV.markOverdefined(); 1011 return true; 1012 } 1013 1014 // Filter out casts we don't know how to reason about before attempting to 1015 // recurse on our operand. This can cut a long search short if we know we're 1016 // not going to be able to get any useful information anways. 1017 switch (BBI->getOpcode()) { 1018 case Instruction::Trunc: 1019 case Instruction::SExt: 1020 case Instruction::ZExt: 1021 case Instruction::BitCast: 1022 break; 1023 default: 1024 // Unhandled instructions are overdefined. 1025 DEBUG(dbgs() << " compute BB '" << BB->getName() 1026 << "' - overdefined (unknown cast).\n"); 1027 BBLV.markOverdefined(); 1028 return true; 1029 } 1030 1031 // Figure out the range of the LHS. If that fails, we still apply the 1032 // transfer rule on the full set since we may be able to locally infer 1033 // interesting facts. 1034 if (!hasBlockValue(BBI->getOperand(0), BB)) 1035 if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0)))) 1036 // More work to do before applying this transfer rule. 1037 return false; 1038 1039 const unsigned OperandBitWidth = 1040 DL.getTypeSizeInBits(BBI->getOperand(0)->getType()); 1041 ConstantRange LHSRange = ConstantRange(OperandBitWidth); 1042 if (hasBlockValue(BBI->getOperand(0), BB)) { 1043 LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB); 1044 intersectAssumeBlockValueConstantRange(BBI->getOperand(0), LHSVal, BBI); 1045 if (LHSVal.isConstantRange()) 1046 LHSRange = LHSVal.getConstantRange(); 1047 } 1048 1049 const unsigned ResultBitWidth = 1050 cast<IntegerType>(BBI->getType())->getBitWidth(); 1051 1052 // NOTE: We're currently limited by the set of operations that ConstantRange 1053 // can evaluate symbolically. Enhancing that set will allows us to analyze 1054 // more definitions. 1055 LVILatticeVal Result; 1056 switch (BBI->getOpcode()) { 1057 case Instruction::Trunc: 1058 Result.markConstantRange(LHSRange.truncate(ResultBitWidth)); 1059 break; 1060 case Instruction::SExt: 1061 Result.markConstantRange(LHSRange.signExtend(ResultBitWidth)); 1062 break; 1063 case Instruction::ZExt: 1064 Result.markConstantRange(LHSRange.zeroExtend(ResultBitWidth)); 1065 break; 1066 case Instruction::BitCast: 1067 Result.markConstantRange(LHSRange); 1068 break; 1069 default: 1070 // Should be dead if the code above is correct 1071 llvm_unreachable("inconsistent with above"); 1072 break; 1073 } 1074 1075 BBLV = Result; 1076 return true; 1077 } 1078 1079 bool LazyValueInfoCache::solveBlockValueBinaryOp(LVILatticeVal &BBLV, 1080 Instruction *BBI, 1081 BasicBlock *BB) { 1082 1083 assert(BBI->getOperand(0)->getType()->isSized() && 1084 "all operands to binary operators are sized"); 1085 1086 // Filter out operators we don't know how to reason about before attempting to 1087 // recurse on our operand(s). This can cut a long search short if we know 1088 // we're not going to be able to get any useful information anways. 1089 switch (BBI->getOpcode()) { 1090 case Instruction::Add: 1091 case Instruction::Sub: 1092 case Instruction::Mul: 1093 case Instruction::UDiv: 1094 case Instruction::Shl: 1095 case Instruction::LShr: 1096 case Instruction::And: 1097 case Instruction::Or: 1098 // continue into the code below 1099 break; 1100 default: 1101 // Unhandled instructions are overdefined. 1102 DEBUG(dbgs() << " compute BB '" << BB->getName() 1103 << "' - overdefined (unknown binary operator).\n"); 1104 BBLV.markOverdefined(); 1105 return true; 1106 }; 1107 1108 // Figure out the range of the LHS. If that fails, use a conservative range, 1109 // but apply the transfer rule anyways. This lets us pick up facts from 1110 // expressions like "and i32 (call i32 @foo()), 32" 1111 if (!hasBlockValue(BBI->getOperand(0), BB)) 1112 if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0)))) 1113 // More work to do before applying this transfer rule. 1114 return false; 1115 1116 const unsigned OperandBitWidth = 1117 DL.getTypeSizeInBits(BBI->getOperand(0)->getType()); 1118 ConstantRange LHSRange = ConstantRange(OperandBitWidth); 1119 if (hasBlockValue(BBI->getOperand(0), BB)) { 1120 LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB); 1121 intersectAssumeBlockValueConstantRange(BBI->getOperand(0), LHSVal, BBI); 1122 if (LHSVal.isConstantRange()) 1123 LHSRange = LHSVal.getConstantRange(); 1124 } 1125 1126 ConstantInt *RHS = cast<ConstantInt>(BBI->getOperand(1)); 1127 ConstantRange RHSRange = ConstantRange(RHS->getValue()); 1128 1129 // NOTE: We're currently limited by the set of operations that ConstantRange 1130 // can evaluate symbolically. Enhancing that set will allows us to analyze 1131 // more definitions. 1132 LVILatticeVal Result; 1133 switch (BBI->getOpcode()) { 1134 case Instruction::Add: 1135 Result.markConstantRange(LHSRange.add(RHSRange)); 1136 break; 1137 case Instruction::Sub: 1138 Result.markConstantRange(LHSRange.sub(RHSRange)); 1139 break; 1140 case Instruction::Mul: 1141 Result.markConstantRange(LHSRange.multiply(RHSRange)); 1142 break; 1143 case Instruction::UDiv: 1144 Result.markConstantRange(LHSRange.udiv(RHSRange)); 1145 break; 1146 case Instruction::Shl: 1147 Result.markConstantRange(LHSRange.shl(RHSRange)); 1148 break; 1149 case Instruction::LShr: 1150 Result.markConstantRange(LHSRange.lshr(RHSRange)); 1151 break; 1152 case Instruction::And: 1153 Result.markConstantRange(LHSRange.binaryAnd(RHSRange)); 1154 break; 1155 case Instruction::Or: 1156 Result.markConstantRange(LHSRange.binaryOr(RHSRange)); 1157 break; 1158 default: 1159 // Should be dead if the code above is correct 1160 llvm_unreachable("inconsistent with above"); 1161 break; 1162 } 1163 1164 BBLV = Result; 1165 return true; 1166 } 1167 1168 bool getValueFromFromCondition(Value *Val, ICmpInst *ICI, 1169 LVILatticeVal &Result, bool isTrueDest) { 1170 assert(ICI && "precondition"); 1171 if (isa<Constant>(ICI->getOperand(1))) { 1172 if (ICI->isEquality() && ICI->getOperand(0) == Val) { 1173 // We know that V has the RHS constant if this is a true SETEQ or 1174 // false SETNE. 1175 if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ)) 1176 Result = LVILatticeVal::get(cast<Constant>(ICI->getOperand(1))); 1177 else 1178 Result = LVILatticeVal::getNot(cast<Constant>(ICI->getOperand(1))); 1179 return true; 1180 } 1181 1182 // Recognize the range checking idiom that InstCombine produces. 1183 // (X-C1) u< C2 --> [C1, C1+C2) 1184 ConstantInt *NegOffset = nullptr; 1185 if (ICI->getPredicate() == ICmpInst::ICMP_ULT) 1186 match(ICI->getOperand(0), m_Add(m_Specific(Val), 1187 m_ConstantInt(NegOffset))); 1188 1189 ConstantInt *CI = dyn_cast<ConstantInt>(ICI->getOperand(1)); 1190 if (CI && (ICI->getOperand(0) == Val || NegOffset)) { 1191 // Calculate the range of values that are allowed by the comparison 1192 ConstantRange CmpRange(CI->getValue()); 1193 ConstantRange TrueValues = 1194 ConstantRange::makeAllowedICmpRegion(ICI->getPredicate(), CmpRange); 1195 1196 if (NegOffset) // Apply the offset from above. 1197 TrueValues = TrueValues.subtract(NegOffset->getValue()); 1198 1199 // If we're interested in the false dest, invert the condition. 1200 if (!isTrueDest) TrueValues = TrueValues.inverse(); 1201 1202 Result = LVILatticeVal::getRange(std::move(TrueValues)); 1203 return true; 1204 } 1205 } 1206 1207 return false; 1208 } 1209 1210 /// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if 1211 /// Val is not constrained on the edge. Result is unspecified if return value 1212 /// is false. 1213 static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, 1214 BasicBlock *BBTo, LVILatticeVal &Result) { 1215 // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we 1216 // know that v != 0. 1217 if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) { 1218 // If this is a conditional branch and only one successor goes to BBTo, then 1219 // we may be able to infer something from the condition. 1220 if (BI->isConditional() && 1221 BI->getSuccessor(0) != BI->getSuccessor(1)) { 1222 bool isTrueDest = BI->getSuccessor(0) == BBTo; 1223 assert(BI->getSuccessor(!isTrueDest) == BBTo && 1224 "BBTo isn't a successor of BBFrom"); 1225 1226 // If V is the condition of the branch itself, then we know exactly what 1227 // it is. 1228 if (BI->getCondition() == Val) { 1229 Result = LVILatticeVal::get(ConstantInt::get( 1230 Type::getInt1Ty(Val->getContext()), isTrueDest)); 1231 return true; 1232 } 1233 1234 // If the condition of the branch is an equality comparison, we may be 1235 // able to infer the value. 1236 if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) 1237 if (getValueFromFromCondition(Val, ICI, Result, isTrueDest)) 1238 return true; 1239 } 1240 } 1241 1242 // If the edge was formed by a switch on the value, then we may know exactly 1243 // what it is. 1244 if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) { 1245 if (SI->getCondition() != Val) 1246 return false; 1247 1248 bool DefaultCase = SI->getDefaultDest() == BBTo; 1249 unsigned BitWidth = Val->getType()->getIntegerBitWidth(); 1250 ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/); 1251 1252 for (SwitchInst::CaseIt i : SI->cases()) { 1253 ConstantRange EdgeVal(i.getCaseValue()->getValue()); 1254 if (DefaultCase) { 1255 // It is possible that the default destination is the destination of 1256 // some cases. There is no need to perform difference for those cases. 1257 if (i.getCaseSuccessor() != BBTo) 1258 EdgesVals = EdgesVals.difference(EdgeVal); 1259 } else if (i.getCaseSuccessor() == BBTo) 1260 EdgesVals = EdgesVals.unionWith(EdgeVal); 1261 } 1262 Result = LVILatticeVal::getRange(std::move(EdgesVals)); 1263 return true; 1264 } 1265 return false; 1266 } 1267 1268 /// \brief Compute the value of Val on the edge BBFrom -> BBTo or the value at 1269 /// the basic block if the edge does not constrain Val. 1270 bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom, 1271 BasicBlock *BBTo, LVILatticeVal &Result, 1272 Instruction *CxtI) { 1273 // If already a constant, there is nothing to compute. 1274 if (Constant *VC = dyn_cast<Constant>(Val)) { 1275 Result = LVILatticeVal::get(VC); 1276 return true; 1277 } 1278 1279 LVILatticeVal LocalResult; 1280 if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult)) 1281 // If we couldn't constrain the value on the edge, LocalResult doesn't 1282 // provide any information. 1283 LocalResult.markOverdefined(); 1284 1285 if (hasSingleValue(LocalResult)) { 1286 // Can't get any more precise here 1287 Result = LocalResult; 1288 return true; 1289 } 1290 1291 if (!hasBlockValue(Val, BBFrom)) { 1292 if (pushBlockValue(std::make_pair(BBFrom, Val))) 1293 return false; 1294 // No new information. 1295 Result = LocalResult; 1296 return true; 1297 } 1298 1299 // Try to intersect ranges of the BB and the constraint on the edge. 1300 LVILatticeVal InBlock = getBlockValue(Val, BBFrom); 1301 intersectAssumeBlockValueConstantRange(Val, InBlock, BBFrom->getTerminator()); 1302 // We can use the context instruction (generically the ultimate instruction 1303 // the calling pass is trying to simplify) here, even though the result of 1304 // this function is generally cached when called from the solve* functions 1305 // (and that cached result might be used with queries using a different 1306 // context instruction), because when this function is called from the solve* 1307 // functions, the context instruction is not provided. When called from 1308 // LazyValueInfoCache::getValueOnEdge, the context instruction is provided, 1309 // but then the result is not cached. 1310 intersectAssumeBlockValueConstantRange(Val, InBlock, CxtI); 1311 1312 Result = intersect(LocalResult, InBlock); 1313 return true; 1314 } 1315 1316 LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB, 1317 Instruction *CxtI) { 1318 DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '" 1319 << BB->getName() << "'\n"); 1320 1321 assert(BlockValueStack.empty() && BlockValueSet.empty()); 1322 if (!hasBlockValue(V, BB)) { 1323 pushBlockValue(std::make_pair(BB, V)); 1324 solve(); 1325 } 1326 LVILatticeVal Result = getBlockValue(V, BB); 1327 intersectAssumeBlockValueConstantRange(V, Result, CxtI); 1328 1329 DEBUG(dbgs() << " Result = " << Result << "\n"); 1330 return Result; 1331 } 1332 1333 LVILatticeVal LazyValueInfoCache::getValueAt(Value *V, Instruction *CxtI) { 1334 DEBUG(dbgs() << "LVI Getting value " << *V << " at '" 1335 << CxtI->getName() << "'\n"); 1336 1337 if (auto *C = dyn_cast<Constant>(V)) 1338 return LVILatticeVal::get(C); 1339 1340 LVILatticeVal Result = LVILatticeVal::getOverdefined(); 1341 if (auto *I = dyn_cast<Instruction>(V)) 1342 Result = getFromRangeMetadata(I); 1343 intersectAssumeBlockValueConstantRange(V, Result, CxtI); 1344 1345 DEBUG(dbgs() << " Result = " << Result << "\n"); 1346 return Result; 1347 } 1348 1349 LVILatticeVal LazyValueInfoCache:: 1350 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, 1351 Instruction *CxtI) { 1352 DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '" 1353 << FromBB->getName() << "' to '" << ToBB->getName() << "'\n"); 1354 1355 LVILatticeVal Result; 1356 if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) { 1357 solve(); 1358 bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result, CxtI); 1359 (void)WasFastQuery; 1360 assert(WasFastQuery && "More work to do after problem solved?"); 1361 } 1362 1363 DEBUG(dbgs() << " Result = " << Result << "\n"); 1364 return Result; 1365 } 1366 1367 void LazyValueInfoCache::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, 1368 BasicBlock *NewSucc) { 1369 // When an edge in the graph has been threaded, values that we could not 1370 // determine a value for before (i.e. were marked overdefined) may be 1371 // possible to solve now. We do NOT try to proactively update these values. 1372 // Instead, we clear their entries from the cache, and allow lazy updating to 1373 // recompute them when needed. 1374 1375 // The updating process is fairly simple: we need to drop cached info 1376 // for all values that were marked overdefined in OldSucc, and for those same 1377 // values in any successor of OldSucc (except NewSucc) in which they were 1378 // also marked overdefined. 1379 std::vector<BasicBlock*> worklist; 1380 worklist.push_back(OldSucc); 1381 1382 auto I = OverDefinedCache.find(OldSucc); 1383 if (I == OverDefinedCache.end()) 1384 return; // Nothing to process here. 1385 SmallVector<Value *, 4> ValsToClear(I->second.begin(), I->second.end()); 1386 1387 // Use a worklist to perform a depth-first search of OldSucc's successors. 1388 // NOTE: We do not need a visited list since any blocks we have already 1389 // visited will have had their overdefined markers cleared already, and we 1390 // thus won't loop to their successors. 1391 while (!worklist.empty()) { 1392 BasicBlock *ToUpdate = worklist.back(); 1393 worklist.pop_back(); 1394 1395 // Skip blocks only accessible through NewSucc. 1396 if (ToUpdate == NewSucc) continue; 1397 1398 bool changed = false; 1399 for (Value *V : ValsToClear) { 1400 // If a value was marked overdefined in OldSucc, and is here too... 1401 auto OI = OverDefinedCache.find(ToUpdate); 1402 if (OI == OverDefinedCache.end()) 1403 continue; 1404 SmallPtrSetImpl<Value *> &ValueSet = OI->second; 1405 if (!ValueSet.count(V)) 1406 continue; 1407 1408 ValueSet.erase(V); 1409 if (ValueSet.empty()) 1410 OverDefinedCache.erase(OI); 1411 1412 // If we removed anything, then we potentially need to update 1413 // blocks successors too. 1414 changed = true; 1415 } 1416 1417 if (!changed) continue; 1418 1419 worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate)); 1420 } 1421 } 1422 1423 //===----------------------------------------------------------------------===// 1424 // LazyValueInfo Impl 1425 //===----------------------------------------------------------------------===// 1426 1427 /// This lazily constructs the LazyValueInfoCache. 1428 static LazyValueInfoCache &getCache(void *&PImpl, AssumptionCache *AC, 1429 const DataLayout *DL, 1430 DominatorTree *DT = nullptr) { 1431 if (!PImpl) { 1432 assert(DL && "getCache() called with a null DataLayout"); 1433 PImpl = new LazyValueInfoCache(AC, *DL, DT); 1434 } 1435 return *static_cast<LazyValueInfoCache*>(PImpl); 1436 } 1437 1438 bool LazyValueInfoWrapperPass::runOnFunction(Function &F) { 1439 Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 1440 const DataLayout &DL = F.getParent()->getDataLayout(); 1441 1442 DominatorTreeWrapperPass *DTWP = 1443 getAnalysisIfAvailable<DominatorTreeWrapperPass>(); 1444 Info.DT = DTWP ? &DTWP->getDomTree() : nullptr; 1445 Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); 1446 1447 if (Info.PImpl) 1448 getCache(Info.PImpl, Info.AC, &DL, Info.DT).clear(); 1449 1450 // Fully lazy. 1451 return false; 1452 } 1453 1454 void LazyValueInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 1455 AU.setPreservesAll(); 1456 AU.addRequired<AssumptionCacheTracker>(); 1457 AU.addRequired<TargetLibraryInfoWrapperPass>(); 1458 } 1459 1460 LazyValueInfo &LazyValueInfoWrapperPass::getLVI() { return Info; } 1461 1462 LazyValueInfo::~LazyValueInfo() { releaseMemory(); } 1463 1464 void LazyValueInfo::releaseMemory() { 1465 // If the cache was allocated, free it. 1466 if (PImpl) { 1467 delete &getCache(PImpl, AC, nullptr); 1468 PImpl = nullptr; 1469 } 1470 } 1471 1472 void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); } 1473 1474 LazyValueInfo LazyValueAnalysis::run(Function &F, FunctionAnalysisManager &FAM) { 1475 auto &AC = FAM.getResult<AssumptionAnalysis>(F); 1476 auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F); 1477 auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F); 1478 1479 return LazyValueInfo(&AC, &TLI, DT); 1480 } 1481 1482 Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB, 1483 Instruction *CxtI) { 1484 const DataLayout &DL = BB->getModule()->getDataLayout(); 1485 LVILatticeVal Result = 1486 getCache(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI); 1487 1488 if (Result.isConstant()) 1489 return Result.getConstant(); 1490 if (Result.isConstantRange()) { 1491 ConstantRange CR = Result.getConstantRange(); 1492 if (const APInt *SingleVal = CR.getSingleElement()) 1493 return ConstantInt::get(V->getContext(), *SingleVal); 1494 } 1495 return nullptr; 1496 } 1497 1498 ConstantRange LazyValueInfo::getConstantRange(Value *V, BasicBlock *BB, 1499 Instruction *CxtI) { 1500 assert(V->getType()->isIntegerTy()); 1501 unsigned Width = V->getType()->getIntegerBitWidth(); 1502 const DataLayout &DL = BB->getModule()->getDataLayout(); 1503 LVILatticeVal Result = 1504 getCache(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI); 1505 assert(!Result.isConstant()); 1506 if (Result.isUndefined()) 1507 return ConstantRange(Width, /*isFullSet=*/false); 1508 if (Result.isConstantRange()) 1509 return Result.getConstantRange(); 1510 return ConstantRange(Width, /*isFullSet=*/true); 1511 } 1512 1513 /// Determine whether the specified value is known to be a 1514 /// constant on the specified edge. Return null if not. 1515 Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB, 1516 BasicBlock *ToBB, 1517 Instruction *CxtI) { 1518 const DataLayout &DL = FromBB->getModule()->getDataLayout(); 1519 LVILatticeVal Result = 1520 getCache(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI); 1521 1522 if (Result.isConstant()) 1523 return Result.getConstant(); 1524 if (Result.isConstantRange()) { 1525 ConstantRange CR = Result.getConstantRange(); 1526 if (const APInt *SingleVal = CR.getSingleElement()) 1527 return ConstantInt::get(V->getContext(), *SingleVal); 1528 } 1529 return nullptr; 1530 } 1531 1532 static LazyValueInfo::Tristate getPredicateResult(unsigned Pred, Constant *C, 1533 LVILatticeVal &Result, 1534 const DataLayout &DL, 1535 TargetLibraryInfo *TLI) { 1536 1537 // If we know the value is a constant, evaluate the conditional. 1538 Constant *Res = nullptr; 1539 if (Result.isConstant()) { 1540 Res = ConstantFoldCompareInstOperands(Pred, Result.getConstant(), C, DL, 1541 TLI); 1542 if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res)) 1543 return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True; 1544 return LazyValueInfo::Unknown; 1545 } 1546 1547 if (Result.isConstantRange()) { 1548 ConstantInt *CI = dyn_cast<ConstantInt>(C); 1549 if (!CI) return LazyValueInfo::Unknown; 1550 1551 ConstantRange CR = Result.getConstantRange(); 1552 if (Pred == ICmpInst::ICMP_EQ) { 1553 if (!CR.contains(CI->getValue())) 1554 return LazyValueInfo::False; 1555 1556 if (CR.isSingleElement() && CR.contains(CI->getValue())) 1557 return LazyValueInfo::True; 1558 } else if (Pred == ICmpInst::ICMP_NE) { 1559 if (!CR.contains(CI->getValue())) 1560 return LazyValueInfo::True; 1561 1562 if (CR.isSingleElement() && CR.contains(CI->getValue())) 1563 return LazyValueInfo::False; 1564 } 1565 1566 // Handle more complex predicates. 1567 ConstantRange TrueValues = 1568 ICmpInst::makeConstantRange((ICmpInst::Predicate)Pred, CI->getValue()); 1569 if (TrueValues.contains(CR)) 1570 return LazyValueInfo::True; 1571 if (TrueValues.inverse().contains(CR)) 1572 return LazyValueInfo::False; 1573 return LazyValueInfo::Unknown; 1574 } 1575 1576 if (Result.isNotConstant()) { 1577 // If this is an equality comparison, we can try to fold it knowing that 1578 // "V != C1". 1579 if (Pred == ICmpInst::ICMP_EQ) { 1580 // !C1 == C -> false iff C1 == C. 1581 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE, 1582 Result.getNotConstant(), C, DL, 1583 TLI); 1584 if (Res->isNullValue()) 1585 return LazyValueInfo::False; 1586 } else if (Pred == ICmpInst::ICMP_NE) { 1587 // !C1 != C -> true iff C1 == C. 1588 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE, 1589 Result.getNotConstant(), C, DL, 1590 TLI); 1591 if (Res->isNullValue()) 1592 return LazyValueInfo::True; 1593 } 1594 return LazyValueInfo::Unknown; 1595 } 1596 1597 return LazyValueInfo::Unknown; 1598 } 1599 1600 /// Determine whether the specified value comparison with a constant is known to 1601 /// be true or false on the specified CFG edge. Pred is a CmpInst predicate. 1602 LazyValueInfo::Tristate 1603 LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, 1604 BasicBlock *FromBB, BasicBlock *ToBB, 1605 Instruction *CxtI) { 1606 const DataLayout &DL = FromBB->getModule()->getDataLayout(); 1607 LVILatticeVal Result = 1608 getCache(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI); 1609 1610 return getPredicateResult(Pred, C, Result, DL, TLI); 1611 } 1612 1613 LazyValueInfo::Tristate 1614 LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C, 1615 Instruction *CxtI) { 1616 const DataLayout &DL = CxtI->getModule()->getDataLayout(); 1617 LVILatticeVal Result = getCache(PImpl, AC, &DL, DT).getValueAt(V, CxtI); 1618 Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI); 1619 if (Ret != Unknown) 1620 return Ret; 1621 1622 // Note: The following bit of code is somewhat distinct from the rest of LVI; 1623 // LVI as a whole tries to compute a lattice value which is conservatively 1624 // correct at a given location. In this case, we have a predicate which we 1625 // weren't able to prove about the merged result, and we're pushing that 1626 // predicate back along each incoming edge to see if we can prove it 1627 // separately for each input. As a motivating example, consider: 1628 // bb1: 1629 // %v1 = ... ; constantrange<1, 5> 1630 // br label %merge 1631 // bb2: 1632 // %v2 = ... ; constantrange<10, 20> 1633 // br label %merge 1634 // merge: 1635 // %phi = phi [%v1, %v2] ; constantrange<1,20> 1636 // %pred = icmp eq i32 %phi, 8 1637 // We can't tell from the lattice value for '%phi' that '%pred' is false 1638 // along each path, but by checking the predicate over each input separately, 1639 // we can. 1640 // We limit the search to one step backwards from the current BB and value. 1641 // We could consider extending this to search further backwards through the 1642 // CFG and/or value graph, but there are non-obvious compile time vs quality 1643 // tradeoffs. 1644 if (CxtI) { 1645 BasicBlock *BB = CxtI->getParent(); 1646 1647 // Function entry or an unreachable block. Bail to avoid confusing 1648 // analysis below. 1649 pred_iterator PI = pred_begin(BB), PE = pred_end(BB); 1650 if (PI == PE) 1651 return Unknown; 1652 1653 // If V is a PHI node in the same block as the context, we need to ask 1654 // questions about the predicate as applied to the incoming value along 1655 // each edge. This is useful for eliminating cases where the predicate is 1656 // known along all incoming edges. 1657 if (auto *PHI = dyn_cast<PHINode>(V)) 1658 if (PHI->getParent() == BB) { 1659 Tristate Baseline = Unknown; 1660 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) { 1661 Value *Incoming = PHI->getIncomingValue(i); 1662 BasicBlock *PredBB = PHI->getIncomingBlock(i); 1663 // Note that PredBB may be BB itself. 1664 Tristate Result = getPredicateOnEdge(Pred, Incoming, C, PredBB, BB, 1665 CxtI); 1666 1667 // Keep going as long as we've seen a consistent known result for 1668 // all inputs. 1669 Baseline = (i == 0) ? Result /* First iteration */ 1670 : (Baseline == Result ? Baseline : Unknown); /* All others */ 1671 if (Baseline == Unknown) 1672 break; 1673 } 1674 if (Baseline != Unknown) 1675 return Baseline; 1676 } 1677 1678 // For a comparison where the V is outside this block, it's possible 1679 // that we've branched on it before. Look to see if the value is known 1680 // on all incoming edges. 1681 if (!isa<Instruction>(V) || 1682 cast<Instruction>(V)->getParent() != BB) { 1683 // For predecessor edge, determine if the comparison is true or false 1684 // on that edge. If they're all true or all false, we can conclude 1685 // the value of the comparison in this block. 1686 Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI); 1687 if (Baseline != Unknown) { 1688 // Check that all remaining incoming values match the first one. 1689 while (++PI != PE) { 1690 Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI); 1691 if (Ret != Baseline) break; 1692 } 1693 // If we terminated early, then one of the values didn't match. 1694 if (PI == PE) { 1695 return Baseline; 1696 } 1697 } 1698 } 1699 } 1700 return Unknown; 1701 } 1702 1703 void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, 1704 BasicBlock *NewSucc) { 1705 if (PImpl) { 1706 const DataLayout &DL = PredBB->getModule()->getDataLayout(); 1707 getCache(PImpl, AC, &DL, DT).threadEdge(PredBB, OldSucc, NewSucc); 1708 } 1709 } 1710 1711 void LazyValueInfo::eraseBlock(BasicBlock *BB) { 1712 if (PImpl) { 1713 const DataLayout &DL = BB->getModule()->getDataLayout(); 1714 getCache(PImpl, AC, &DL, DT).eraseBlock(BB); 1715 } 1716 } 1717