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 INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info", 51 "Lazy Value Information Analysis", false, true) 52 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 53 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 54 INITIALIZE_PASS_END(LazyValueInfoWrapperPass, "lazy-value-info", 55 "Lazy Value Information Analysis", false, true) 56 57 namespace llvm { 58 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 if (Val.isConstantRange() && 68 Val.getConstantRange().isSingleElement()) 69 // Integer constants are single element ranges 70 return true; 71 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 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 if (A.isUndefined()) 96 return A; 97 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 if (A.isOverdefined()) 102 return B; 103 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 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 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 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 : CallbackVH(V), Parent(P) { } 142 143 void deleted() override; 144 void allUsesReplacedWith(Value *V) override { 145 deleted(); 146 } 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 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 void insertResult(Value *Val, BasicBlock *BB, 181 const ValueLatticeElement &Result) { 182 SeenBlocks.insert(BB); 183 184 // Insert over-defined values into their own cache to reduce memory 185 // overhead. 186 if (Result.isOverdefined()) 187 OverDefinedCache[BB].insert(Val); 188 else { 189 auto It = ValueCache.find_as(Val); 190 if (It == ValueCache.end()) { 191 ValueCache[Val] = make_unique<ValueCacheEntryTy>(Val, this); 192 It = ValueCache.find_as(Val); 193 assert(It != ValueCache.end() && "Val was just added to the map!"); 194 } 195 It->second->BlockVals[BB] = Result; 196 } 197 } 198 199 bool isOverdefined(Value *V, BasicBlock *BB) const { 200 auto ODI = OverDefinedCache.find(BB); 201 202 if (ODI == OverDefinedCache.end()) 203 return false; 204 205 return ODI->second.count(V); 206 } 207 208 bool hasCachedValueInfo(Value *V, BasicBlock *BB) const { 209 if (isOverdefined(V, BB)) 210 return true; 211 212 auto I = ValueCache.find_as(V); 213 if (I == ValueCache.end()) 214 return false; 215 216 return I->second->BlockVals.count(BB); 217 } 218 219 ValueLatticeElement getCachedValueInfo(Value *V, BasicBlock *BB) const { 220 if (isOverdefined(V, BB)) 221 return ValueLatticeElement::getOverdefined(); 222 223 auto I = ValueCache.find_as(V); 224 if (I == ValueCache.end()) 225 return ValueLatticeElement(); 226 auto BBI = I->second->BlockVals.find(BB); 227 if (BBI == I->second->BlockVals.end()) 228 return ValueLatticeElement(); 229 return BBI->second; 230 } 231 232 /// clear - Empty the cache. 233 void clear() { 234 SeenBlocks.clear(); 235 ValueCache.clear(); 236 OverDefinedCache.clear(); 237 } 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 void LazyValueInfoCache::eraseValue(Value *V) { 256 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 ValueSet.erase(V); 262 if (ValueSet.empty()) 263 OverDefinedCache.erase(Iter); 264 } 265 266 ValueCache.erase(V); 267 } 268 269 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 Parent->eraseValue(*this); 273 } 274 275 void LazyValueInfoCache::eraseBlock(BasicBlock *BB) { 276 // Shortcut if we have never seen this block. 277 DenseSet<PoisoningVH<BasicBlock> >::iterator I = SeenBlocks.find(BB); 278 if (I == SeenBlocks.end()) 279 return; 280 SeenBlocks.erase(I); 281 282 auto ODI = OverDefinedCache.find(BB); 283 if (ODI != OverDefinedCache.end()) 284 OverDefinedCache.erase(ODI); 285 286 for (auto &I : ValueCache) 287 I.second->BlockVals.erase(BB); 288 } 289 290 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 worklist.push_back(OldSucc); 304 305 auto I = OverDefinedCache.find(OldSucc); 306 if (I == OverDefinedCache.end()) 307 return; // Nothing to process here. 308 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 while (!worklist.empty()) { 315 BasicBlock *ToUpdate = worklist.back(); 316 worklist.pop_back(); 317 318 // Skip blocks only accessible through NewSucc. 319 if (ToUpdate == NewSucc) continue; 320 321 // If a value was marked overdefined in OldSucc, and is here too... 322 auto OI = OverDefinedCache.find(ToUpdate); 323 if (OI == OverDefinedCache.end()) 324 continue; 325 SmallPtrSetImpl<Value *> &ValueSet = OI->second; 326 327 bool changed = false; 328 for (Value *V : ValsToClear) { 329 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 if (ValueSet.empty()) { 337 OverDefinedCache.erase(OI); 338 break; 339 } 340 } 341 342 if (!changed) continue; 343 344 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 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 : 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 bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) { 392 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 BlockValueStack.push_back(BV); 398 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 TheCache.clear(); 453 } 454 455 /// Printing the LazyValueInfo Analysis. 456 void printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) { 457 LazyValueInfoAnnotatedWriter Writer(this, DTree); 458 F.print(OS, &Writer); 459 } 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 TheCache.eraseBlock(BB); 465 } 466 467 /// Disables use of the DominatorTree within LVI. 468 void disableDT() { 469 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 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 : AC(AC), DL(DL), DT(DT), DisabledDT(nullptr) {} 491 }; 492 } // end anonymous namespace 493 494 495 void LazyValueInfoImpl::solve() { 496 SmallVector<std::pair<BasicBlock *, Value *>, 8> StartingStack( 497 BlockValueStack.begin(), BlockValueStack.end()); 498 499 unsigned processedCount = 0; 500 while (!BlockValueStack.empty()) { 501 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 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 while (!StartingStack.empty()) { 515 std::pair<BasicBlock *, Value *> &e = StartingStack.back(); 516 TheCache.insertResult(e.second, e.first, 517 ValueLatticeElement::getOverdefined()); 518 StartingStack.pop_back(); 519 } 520 BlockValueSet.clear(); 521 BlockValueStack.clear(); 522 return; 523 } 524 std::pair<BasicBlock *, Value *> e = BlockValueStack.back(); 525 assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!"); 526 527 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 if (isa<Constant>(Val)) 549 return true; 550 551 return TheCache.hasCachedValueInfo(Val, BB); 552 } 553 554 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 return TheCache.getCachedValueInfo(Val, BB); 561 } 562 563 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 if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range)) 570 if (isa<IntegerType>(BBI->getType())) { 571 return ValueLatticeElement::getRange( 572 getConstantRangeFromMetadata(*Ranges)); 573 } 574 break; 575 }; 576 // Nothing known - will be intersected with other facts 577 return ValueLatticeElement::getOverdefined(); 578 } 579 580 bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) { 581 if (isa<Constant>(Val)) 582 return true; 583 584 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 if (!solveBlockValueImpl(Res, Val, BB)) 599 // Work pushed, will revisit 600 return false; 601 602 TheCache.insertResult(Val, BB, Res); 603 return true; 604 } 605 606 bool LazyValueInfoImpl::solveBlockValueImpl(ValueLatticeElement &Res, 607 Value *Val, BasicBlock *BB) { 608 609 Instruction *BBI = dyn_cast<Instruction>(Val); 610 if (!BBI || BBI->getParent() != BB) 611 return solveBlockValueNonLocal(Res, Val, BB); 612 613 if (PHINode *PN = dyn_cast<PHINode>(BBI)) 614 return solveBlockValuePHINode(Res, PN, BB); 615 616 if (auto *SI = dyn_cast<SelectInst>(BBI)) 617 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 PointerType *PT = dyn_cast<PointerType>(BBI->getType()); 629 if (PT && isKnownNonZero(BBI, DL)) { 630 Res = ValueLatticeElement::getNot(ConstantPointerNull::get(PT)); 631 return true; 632 } 633 if (BBI->getType()->isIntegerTy()) { 634 if (auto *CI = dyn_cast<CastInst>(BBI)) 635 return solveBlockValueCast(Res, CI, BB); 636 637 BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI); 638 if (BO && isa<ConstantInt>(BO->getOperand(1))) 639 return solveBlockValueBinaryOp(Res, BO, BB); 640 } 641 642 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName() 643 << "' - unknown inst def found.\n"); 644 Res = getFromRangeMetadata(BBI); 645 return true; 646 } 647 648 static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) { 649 if (LoadInst *L = dyn_cast<LoadInst>(I)) { 650 return L->getPointerAddressSpace() == 0 && 651 GetUnderlyingObject(L->getPointerOperand(), 652 L->getModule()->getDataLayout()) == Ptr; 653 } 654 if (StoreInst *S = dyn_cast<StoreInst>(I)) { 655 return S->getPointerAddressSpace() == 0 && 656 GetUnderlyingObject(S->getPointerOperand(), 657 S->getModule()->getDataLayout()) == Ptr; 658 } 659 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) { 660 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 if (!Len || Len->isZero()) return false; 665 666 if (MI->getDestAddressSpace() == 0) 667 if (GetUnderlyingObject(MI->getRawDest(), 668 MI->getModule()->getDataLayout()) == Ptr) 669 return true; 670 if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) 671 if (MTI->getSourceAddressSpace() == 0) 672 if (GetUnderlyingObject(MTI->getRawSource(), 673 MTI->getModule()->getDataLayout()) == Ptr) 674 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 static bool isObjectDereferencedInBlock(Value *Val, BasicBlock *BB) { 684 assert(Val->getType()->isPointerTy()); 685 686 const DataLayout &DL = BB->getModule()->getDataLayout(); 687 Value *UnderlyingVal = GetUnderlyingObject(Val, DL); 688 // If 'GetUnderlyingObject' didn't converge, skip it. It won't converge 689 // inside InstructionDereferencesPointer either. 690 if (UnderlyingVal == GetUnderlyingObject(UnderlyingVal, DL, 1)) 691 for (Instruction &I : *BB) 692 if (InstructionDereferencesPointer(&I, UnderlyingVal)) 693 return true; 694 return false; 695 } 696 697 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 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 PointerType *PTy = dyn_cast<PointerType>(Val->getType()); 708 if (PTy && 709 (isKnownNonZero(Val, DL) || 710 (isObjectDereferencedInBlock(Val, BB) && 711 !NullPointerIsDefined(BB->getParent(), PTy->getAddressSpace())))) { 712 Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy)); 713 } else { 714 Result = ValueLatticeElement::getOverdefined(); 715 } 716 BBLV = Result; 717 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 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 730 ValueLatticeElement EdgeResult; 731 if (!getEdgeValue(Val, *PI, BB, EdgeResult)) 732 // Explore that input, then return here 733 return false; 734 735 Result.mergeIn(EdgeResult, DL); 736 737 // If we hit overdefined, exit early. The BlockVals entry is already set 738 // to overdefined. 739 if (Result.isOverdefined()) { 740 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName() 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 PointerType *PTy = dyn_cast<PointerType>(Val->getType()); 745 if (PTy && isObjectDereferencedInBlock(Val, BB) && 746 !NullPointerIsDefined(BB->getParent(), PTy->getAddressSpace())) { 747 Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy)); 748 } 749 750 BBLV = Result; 751 return true; 752 } 753 } 754 755 // Return the merged value, which is more precise than 'overdefined'. 756 assert(!Result.isOverdefined()); 757 BBLV = Result; 758 return true; 759 } 760 761 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 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 if (!getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN)) 776 // Explore that input, then return here 777 return false; 778 779 Result.mergeIn(EdgeResult, DL); 780 781 // If we hit overdefined, exit early. The BlockVals entry is already set 782 // to overdefined. 783 if (Result.isOverdefined()) { 784 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName() 785 << "' - overdefined because of pred (local).\n"); 786 787 BBLV = Result; 788 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 BBLV = Result; 795 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 void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange( 804 Value *Val, ValueLatticeElement &BBLV, Instruction *BBI) { 805 BBI = BBI ? BBI : dyn_cast<Instruction>(Val); 806 if (!BBI) 807 return; 808 809 for (auto &AssumeVH : AC->assumptionsFor(Val)) { 810 if (!AssumeVH) 811 continue; 812 auto *I = cast<CallInst>(AssumeVH); 813 if (!isValidAssumeForContext(I, BBI, DT)) 814 continue; 815 816 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 auto *GuardDecl = BBI->getModule()->getFunction( 821 Intrinsic::getName(Intrinsic::experimental_guard)); 822 if (!GuardDecl || GuardDecl->use_empty()) 823 return; 824 825 for (Instruction &I : make_range(BBI->getIterator().getReverse(), 826 BBI->getParent()->rend())) { 827 Value *Cond = nullptr; 828 if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond)))) 829 BBLV = intersect(BBLV, getValueFromCondition(Val, Cond)); 830 } 831 } 832 833 bool LazyValueInfoImpl::solveBlockValueSelect(ValueLatticeElement &BBLV, 834 SelectInst *SI, BasicBlock *BB) { 835 836 // Recurse on our inputs if needed 837 if (!hasBlockValue(SI->getTrueValue(), BB)) { 838 if (pushBlockValue(std::make_pair(BB, SI->getTrueValue()))) 839 return false; 840 BBLV = ValueLatticeElement::getOverdefined(); 841 return true; 842 } 843 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 if (TrueVal.isOverdefined()) { 847 BBLV = ValueLatticeElement::getOverdefined(); 848 return true; 849 } 850 851 if (!hasBlockValue(SI->getFalseValue(), BB)) { 852 if (pushBlockValue(std::make_pair(BB, SI->getFalseValue()))) 853 return false; 854 BBLV = ValueLatticeElement::getOverdefined(); 855 return true; 856 } 857 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 if (FalseVal.isOverdefined()) { 861 BBLV = ValueLatticeElement::getOverdefined(); 862 return true; 863 } 864 865 if (TrueVal.isConstantRange() && FalseVal.isConstantRange()) { 866 const ConstantRange &TrueCR = TrueVal.getConstantRange(); 867 const ConstantRange &FalseCR = FalseVal.getConstantRange(); 868 Value *LHS = nullptr; 869 Value *RHS = nullptr; 870 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 if (SelectPatternResult::isMinOrMax(SPR.Flavor) && 874 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 }(); 889 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 TrueVal = intersect(TrueVal, 901 getValueFromCondition(SI->getTrueValue(), Cond, true)); 902 FalseVal = intersect(FalseVal, 903 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 switch (Pred) { 926 default: break; 927 case ICmpInst::ICMP_EQ: 928 if (match(SI->getFalseValue(), m_Add(m_Specific(A), 929 m_ConstantInt(CIAdded)))) { 930 auto ResNot = addConstants(CIBase, CIAdded); 931 FalseVal = intersect(FalseVal, 932 ValueLatticeElement::getNot(ResNot)); 933 } 934 break; 935 case ICmpInst::ICMP_NE: 936 if (match(SI->getTrueValue(), m_Add(m_Specific(A), 937 m_ConstantInt(CIAdded)))) { 938 auto ResNot = addConstants(CIBase, CIAdded); 939 TrueVal = intersect(TrueVal, 940 ValueLatticeElement::getNot(ResNot)); 941 } 942 break; 943 }; 944 } 945 } 946 947 ValueLatticeElement Result; // Start Undefined. 948 Result.mergeIn(TrueVal, DL); 949 Result.mergeIn(FalseVal, DL); 950 BBLV = Result; 951 return true; 952 } 953 954 bool LazyValueInfoImpl::solveBlockValueCast(ValueLatticeElement &BBLV, 955 CastInst *CI, 956 BasicBlock *BB) { 957 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 BBLV = ValueLatticeElement::getOverdefined(); 961 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 BBLV = ValueLatticeElement::getOverdefined(); 978 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 if (!hasBlockValue(CI->getOperand(0), BB)) 985 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 DL.getTypeSizeInBits(CI->getOperand(0)->getType()); 991 ConstantRange LHSRange = ConstantRange(OperandBitWidth); 992 if (hasBlockValue(CI->getOperand(0), BB)) { 993 ValueLatticeElement LHSVal = getBlockValue(CI->getOperand(0), BB); 994 intersectAssumeOrGuardBlockValueConstantRange(CI->getOperand(0), LHSVal, 995 CI); 996 if (LHSVal.isConstantRange()) 997 LHSRange = LHSVal.getConstantRange(); 998 } 999 1000 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 BBLV = ValueLatticeElement::getRange(LHSRange.castOp(CI->getOpcode(), 1006 ResultBitWidth)); 1007 return true; 1008 } 1009 1010 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 BBLV = ValueLatticeElement::getOverdefined(); 1037 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 if (!hasBlockValue(BO->getOperand(0), BB)) 1044 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 DL.getTypeSizeInBits(BO->getOperand(0)->getType()); 1050 ConstantRange LHSRange = ConstantRange(OperandBitWidth); 1051 if (hasBlockValue(BO->getOperand(0), BB)) { 1052 ValueLatticeElement LHSVal = getBlockValue(BO->getOperand(0), BB); 1053 intersectAssumeOrGuardBlockValueConstantRange(BO->getOperand(0), LHSVal, 1054 BO); 1055 if (LHSVal.isConstantRange()) 1056 LHSRange = LHSVal.getConstantRange(); 1057 } 1058 1059 ConstantInt *RHS = cast<ConstantInt>(BO->getOperand(1)); 1060 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 BBLV = ValueLatticeElement::getRange(LHSRange.binaryOp(BinOp, RHSRange)); 1067 return true; 1068 } 1069 1070 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 if (isa<Constant>(RHS)) { 1077 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 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 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 if (LHS != Val && !match(LHS, m_Add(m_Specific(Val), m_ConstantInt()))) { 1100 std::swap(LHS, RHS); 1101 Predicate = CmpInst::getSwappedPredicate(Predicate); 1102 } 1103 1104 ConstantInt *Offset = nullptr; 1105 if (LHS != Val) 1106 match(LHS, m_Add(m_Specific(Val), m_ConstantInt(Offset))); 1107 1108 if (LHS == Val || Offset) { 1109 // Calculate the range of values that are allowed by the comparison 1110 ConstantRange RHSRange(RHS->getType()->getIntegerBitWidth(), 1111 /*isFullSet=*/true); 1112 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) 1113 RHSRange = ConstantRange(CI->getValue()); 1114 else if (Instruction *I = dyn_cast<Instruction>(RHS)) 1115 if (auto *Ranges = I->getMetadata(LLVMContext::MD_range)) 1116 RHSRange = getConstantRangeFromMetadata(*Ranges); 1117 1118 // If we're interested in the false dest, invert the condition 1119 CmpInst::Predicate Pred = 1120 isTrueDest ? Predicate : CmpInst::getInversePredicate(Predicate); 1121 ConstantRange TrueValues = 1122 ConstantRange::makeAllowedICmpRegion(Pred, RHSRange); 1123 1124 if (Offset) // Apply the offset from above. 1125 TrueValues = TrueValues.subtract(Offset->getValue()); 1126 1127 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 getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest, 1139 DenseMap<Value*, ValueLatticeElement> &Visited) { 1140 if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond)) 1141 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 if (!BO || (isTrueDest && BO->getOpcode() != BinaryOperator::And) || 1149 (!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 if (BL == Cond || BR == Cond) 1159 return ValueLatticeElement::getOverdefined(); 1160 1161 return intersect(getValueFromCondition(Val, BL, isTrueDest, Visited), 1162 getValueFromCondition(Val, BR, isTrueDest, Visited)); 1163 } 1164 1165 static ValueLatticeElement 1166 getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest, 1167 DenseMap<Value*, ValueLatticeElement> &Visited) { 1168 auto I = Visited.find(Cond); 1169 if (I != Visited.end()) 1170 return I->second; 1171 1172 auto Result = getValueFromConditionImpl(Val, Cond, isTrueDest, Visited); 1173 Visited[Cond] = Result; 1174 return Result; 1175 } 1176 1177 ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond, 1178 bool isTrueDest) { 1179 assert(Cond && "precondition"); 1180 DenseMap<Value*, ValueLatticeElement> Visited; 1181 return getValueFromCondition(Val, Cond, isTrueDest, Visited); 1182 } 1183 1184 // Return true if Usr has Op as an operand, otherwise false. 1185 static bool usesOperand(User *Usr, Value *Op) { 1186 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 static ValueLatticeElement constantFoldUser(User *Usr, Value *Op, 1202 const APInt &OpConstVal, 1203 const DataLayout &DL) { 1204 assert(isOperationFoldable(Usr) && "Precondition"); 1205 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 if (auto *C = dyn_cast_or_null<ConstantInt>( 1210 SimplifyCastInst(CI->getOpcode(), OpConst, 1211 CI->getDestTy(), DL))) { 1212 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 Value *LHS = Op0Match ? OpConst : BO->getOperand(0); 1220 Value *RHS = Op1Match ? OpConst : BO->getOperand(1); 1221 if (auto *C = dyn_cast_or_null<ConstantInt>( 1222 SimplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) { 1223 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 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 if (BI->isConditional() && 1240 BI->getSuccessor(0) != BI->getSuccessor(1)) { 1241 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 if (Condition == Val) { 1249 Result = ValueLatticeElement::get(ConstantInt::get( 1250 Type::getInt1Ty(Val->getContext()), isTrueDest)); 1251 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 Result = getValueFromCondition(Val, Condition, isTrueDest); 1257 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 if (isa<IntegerType>(Usr->getType()) && isOperationFoldable(Usr)) { 1266 const DataLayout &DL = BBTo->getModule()->getDataLayout(); 1267 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 APInt ConditionVal(1, isTrueDest ? 1 : 0); 1276 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 for (unsigned i = 0; i < Usr->getNumOperands(); ++i) { 1286 Value *Op = Usr->getOperand(i); 1287 ValueLatticeElement OpLatticeVal = 1288 getValueFromCondition(Op, Condition, isTrueDest); 1289 if (Optional<APInt> OpConst = OpLatticeVal.asConstantInteger()) { 1290 Result = constantFoldUser(Usr, Op, OpConst.getValue(), DL); 1291 break; 1292 } 1293 } 1294 } 1295 } 1296 } 1297 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 if (!isa<IntegerType>(Val->getType())) 1307 return false; 1308 bool ValUsesConditionAndMayBeFoldable = false; 1309 if (Condition != Val) { 1310 // Check if Val has Condition as an operand. 1311 if (User *Usr = dyn_cast<User>(Val)) 1312 ValUsesConditionAndMayBeFoldable = isOperationFoldable(Usr) && 1313 usesOperand(Usr, Condition); 1314 if (!ValUsesConditionAndMayBeFoldable) 1315 return false; 1316 } 1317 assert((Condition == Val || ValUsesConditionAndMayBeFoldable) && 1318 "Condition != Val nor Val doesn't use Condition"); 1319 1320 bool DefaultCase = SI->getDefaultDest() == BBTo; 1321 unsigned BitWidth = Val->getType()->getIntegerBitWidth(); 1322 ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/); 1323 1324 for (auto Case : SI->cases()) { 1325 APInt CaseValue = Case.getCaseValue()->getValue(); 1326 ConstantRange EdgeVal(CaseValue); 1327 if (ValUsesConditionAndMayBeFoldable) { 1328 User *Usr = cast<User>(Val); 1329 const DataLayout &DL = BBTo->getModule()->getDataLayout(); 1330 ValueLatticeElement EdgeLatticeVal = 1331 constantFoldUser(Usr, Condition, CaseValue, DL); 1332 if (EdgeLatticeVal.isOverdefined()) 1333 return false; 1334 EdgeVal = EdgeLatticeVal.getConstantRange(); 1335 } 1336 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 if (Case.getCaseSuccessor() != BBTo && Condition == Val) 1344 EdgesVals = EdgesVals.difference(EdgeVal); 1345 } else if (Case.getCaseSuccessor() == BBTo) 1346 EdgesVals = EdgesVals.unionWith(EdgeVal); 1347 } 1348 Result = ValueLatticeElement::getRange(std::move(EdgesVals)); 1349 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 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 Result = ValueLatticeElement::get(VC); 1363 return true; 1364 } 1365 1366 ValueLatticeElement LocalResult; 1367 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 LocalResult = ValueLatticeElement::getOverdefined(); 1371 1372 if (hasSingleValue(LocalResult)) { 1373 // Can't get any more precise here 1374 Result = LocalResult; 1375 return true; 1376 } 1377 1378 if (!hasBlockValue(Val, BBFrom)) { 1379 if (pushBlockValue(std::make_pair(BBFrom, Val))) 1380 return false; 1381 // No new information. 1382 Result = LocalResult; 1383 return true; 1384 } 1385 1386 // Try to intersect ranges of the BB and the constraint on the edge. 1387 ValueLatticeElement InBlock = getBlockValue(Val, BBFrom); 1388 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 intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI); 1399 1400 Result = intersect(LocalResult, InBlock); 1401 return true; 1402 } 1403 1404 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 if (!hasBlockValue(V, BB)) { 1411 pushBlockValue(std::make_pair(BB, V)); 1412 solve(); 1413 } 1414 ValueLatticeElement Result = getBlockValue(V, BB); 1415 intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI); 1416 1417 LLVM_DEBUG(dbgs() << " Result = " << Result << "\n"); 1418 return Result; 1419 } 1420 1421 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 Result = getFromRangeMetadata(I); 1431 intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI); 1432 1433 LLVM_DEBUG(dbgs() << " Result = " << Result << "\n"); 1434 return Result; 1435 } 1436 1437 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 if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) { 1446 solve(); 1447 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 return Result; 1454 } 1455 1456 void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, 1457 BasicBlock *NewSucc) { 1458 TheCache.threadEdgeImpl(OldSucc, NewSucc); 1459 } 1460 1461 //===----------------------------------------------------------------------===// 1462 // LazyValueInfo Impl 1463 //===----------------------------------------------------------------------===// 1464 1465 /// This lazily constructs the LazyValueInfoImpl. 1466 static LazyValueInfoImpl &getImpl(void *&PImpl, AssumptionCache *AC, 1467 const DataLayout *DL, 1468 DominatorTree *DT = nullptr) { 1469 if (!PImpl) { 1470 assert(DL && "getCache() called with a null DataLayout"); 1471 PImpl = new LazyValueInfoImpl(AC, *DL, DT); 1472 } 1473 return *static_cast<LazyValueInfoImpl*>(PImpl); 1474 } 1475 1476 bool LazyValueInfoWrapperPass::runOnFunction(Function &F) { 1477 Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 1478 const DataLayout &DL = F.getParent()->getDataLayout(); 1479 1480 DominatorTreeWrapperPass *DTWP = 1481 getAnalysisIfAvailable<DominatorTreeWrapperPass>(); 1482 Info.DT = DTWP ? &DTWP->getDomTree() : nullptr; 1483 Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); 1484 1485 if (Info.PImpl) 1486 getImpl(Info.PImpl, Info.AC, &DL, Info.DT).clear(); 1487 1488 // Fully lazy. 1489 return false; 1490 } 1491 1492 void LazyValueInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 1493 AU.setPreservesAll(); 1494 AU.addRequired<AssumptionCacheTracker>(); 1495 AU.addRequired<TargetLibraryInfoWrapperPass>(); 1496 } 1497 1498 LazyValueInfo &LazyValueInfoWrapperPass::getLVI() { return Info; } 1499 1500 LazyValueInfo::~LazyValueInfo() { releaseMemory(); } 1501 1502 void LazyValueInfo::releaseMemory() { 1503 // If the cache was allocated, free it. 1504 if (PImpl) { 1505 delete &getImpl(PImpl, AC, nullptr); 1506 PImpl = nullptr; 1507 } 1508 } 1509 1510 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 if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) || 1516 (DT && Inv.invalidate<DominatorTreeAnalysis>(F, PA))) 1517 return true; 1518 1519 return false; 1520 } 1521 1522 void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); } 1523 1524 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 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 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 const DataLayout &DL = BB->getModule()->getDataLayout(); 1554 ValueLatticeElement Result = 1555 getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI); 1556 1557 if (Result.isConstant()) 1558 return Result.getConstant(); 1559 if (Result.isConstantRange()) { 1560 const ConstantRange &CR = Result.getConstantRange(); 1561 if (const APInt *SingleVal = CR.getSingleElement()) 1562 return ConstantInt::get(V->getContext(), *SingleVal); 1563 } 1564 return nullptr; 1565 } 1566 1567 ConstantRange LazyValueInfo::getConstantRange(Value *V, BasicBlock *BB, 1568 Instruction *CxtI) { 1569 assert(V->getType()->isIntegerTy()); 1570 unsigned Width = V->getType()->getIntegerBitWidth(); 1571 const DataLayout &DL = BB->getModule()->getDataLayout(); 1572 ValueLatticeElement Result = 1573 getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI); 1574 if (Result.isUndefined()) 1575 return ConstantRange(Width, /*isFullSet=*/false); 1576 if (Result.isConstantRange()) 1577 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 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 Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB, 1588 BasicBlock *ToBB, 1589 Instruction *CxtI) { 1590 const DataLayout &DL = FromBB->getModule()->getDataLayout(); 1591 ValueLatticeElement Result = 1592 getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI); 1593 1594 if (Result.isConstant()) 1595 return Result.getConstant(); 1596 if (Result.isConstantRange()) { 1597 const ConstantRange &CR = Result.getConstantRange(); 1598 if (const APInt *SingleVal = CR.getSingleElement()) 1599 return ConstantInt::get(V->getContext(), *SingleVal); 1600 } 1601 return nullptr; 1602 } 1603 1604 ConstantRange LazyValueInfo::getConstantRangeOnEdge(Value *V, 1605 BasicBlock *FromBB, 1606 BasicBlock *ToBB, 1607 Instruction *CxtI) { 1608 unsigned Width = V->getType()->getIntegerBitWidth(); 1609 const DataLayout &DL = FromBB->getModule()->getDataLayout(); 1610 ValueLatticeElement Result = 1611 getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI); 1612 1613 if (Result.isUndefined()) 1614 return ConstantRange(Width, /*isFullSet=*/false); 1615 if (Result.isConstantRange()) 1616 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 return ConstantRange(Width, /*isFullSet=*/true); 1622 } 1623 1624 static LazyValueInfo::Tristate 1625 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 if (Val.isConstant()) { 1630 Res = ConstantFoldCompareInstOperands(Pred, Val.getConstant(), C, DL, TLI); 1631 if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res)) 1632 return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True; 1633 return LazyValueInfo::Unknown; 1634 } 1635 1636 if (Val.isConstantRange()) { 1637 ConstantInt *CI = dyn_cast<ConstantInt>(C); 1638 if (!CI) return LazyValueInfo::Unknown; 1639 1640 const ConstantRange &CR = Val.getConstantRange(); 1641 if (Pred == ICmpInst::ICMP_EQ) { 1642 if (!CR.contains(CI->getValue())) 1643 return LazyValueInfo::False; 1644 1645 if (CR.isSingleElement()) 1646 return LazyValueInfo::True; 1647 } else if (Pred == ICmpInst::ICMP_NE) { 1648 if (!CR.contains(CI->getValue())) 1649 return LazyValueInfo::True; 1650 1651 if (CR.isSingleElement()) 1652 return LazyValueInfo::False; 1653 } else { 1654 // Handle more complex predicates. 1655 ConstantRange TrueValues = ConstantRange::makeExactICmpRegion( 1656 (ICmpInst::Predicate)Pred, CI->getValue()); 1657 if (TrueValues.contains(CR)) 1658 return LazyValueInfo::True; 1659 if (TrueValues.inverse().contains(CR)) 1660 return LazyValueInfo::False; 1661 } 1662 return LazyValueInfo::Unknown; 1663 } 1664 1665 if (Val.isNotConstant()) { 1666 // If this is an equality comparison, we can try to fold it knowing that 1667 // "V != C1". 1668 if (Pred == ICmpInst::ICMP_EQ) { 1669 // !C1 == C -> false iff C1 == C. 1670 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE, 1671 Val.getNotConstant(), C, DL, 1672 TLI); 1673 if (Res->isNullValue()) 1674 return LazyValueInfo::False; 1675 } else if (Pred == ICmpInst::ICMP_NE) { 1676 // !C1 != C -> true iff C1 == C. 1677 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE, 1678 Val.getNotConstant(), C, DL, 1679 TLI); 1680 if (Res->isNullValue()) 1681 return LazyValueInfo::True; 1682 } 1683 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 LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, 1693 BasicBlock *FromBB, BasicBlock *ToBB, 1694 Instruction *CxtI) { 1695 const DataLayout &DL = FromBB->getModule()->getDataLayout(); 1696 ValueLatticeElement Result = 1697 getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI); 1698 1699 return getPredicateResult(Pred, C, Result, DL, TLI); 1700 } 1701 1702 LazyValueInfo::Tristate 1703 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 const DataLayout &DL = CxtI->getModule()->getDataLayout(); 1710 if (V->getType()->isPointerTy() && C->isNullValue() && 1711 isKnownNonZero(V->stripPointerCasts(), DL)) { 1712 if (Pred == ICmpInst::ICMP_EQ) 1713 return LazyValueInfo::False; 1714 else if (Pred == ICmpInst::ICMP_NE) 1715 return LazyValueInfo::True; 1716 } 1717 ValueLatticeElement Result = getImpl(PImpl, AC, &DL, DT).getValueAt(V, CxtI); 1718 Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI); 1719 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 if (CxtI) { 1745 BasicBlock *BB = CxtI->getParent(); 1746 1747 // Function entry or an unreachable block. Bail to avoid confusing 1748 // analysis below. 1749 pred_iterator PI = pred_begin(BB), PE = pred_end(BB); 1750 if (PI == PE) 1751 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 if (PHI->getParent() == BB) { 1759 Tristate Baseline = Unknown; 1760 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 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 Baseline = (i == 0) ? Result /* First iteration */ 1770 : (Baseline == Result ? Baseline : Unknown); /* All others */ 1771 if (Baseline == Unknown) 1772 break; 1773 } 1774 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 if (!isa<Instruction>(V) || 1782 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 Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI); 1787 if (Baseline != Unknown) { 1788 // Check that all remaining incoming values match the first one. 1789 while (++PI != PE) { 1790 Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI); 1791 if (Ret != Baseline) break; 1792 } 1793 // If we terminated early, then one of the values didn't match. 1794 if (PI == PE) { 1795 return Baseline; 1796 } 1797 } 1798 } 1799 } 1800 return Unknown; 1801 } 1802 1803 void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, 1804 BasicBlock *NewSucc) { 1805 if (PImpl) { 1806 const DataLayout &DL = PredBB->getModule()->getDataLayout(); 1807 getImpl(PImpl, AC, &DL, DT).threadEdge(PredBB, OldSucc, NewSucc); 1808 } 1809 } 1810 1811 void LazyValueInfo::eraseBlock(BasicBlock *BB) { 1812 if (PImpl) { 1813 const DataLayout &DL = BB->getModule()->getDataLayout(); 1814 getImpl(PImpl, AC, &DL, DT).eraseBlock(BB); 1815 } 1816 } 1817 1818 1819 void LazyValueInfo::printLVI(Function &F, DominatorTree &DTree, raw_ostream &OS) { 1820 if (PImpl) { 1821 getImpl(PImpl, AC, DL, DT).printLVI(F, DTree, OS); 1822 } 1823 } 1824 1825 void LazyValueInfo::disableDT() { 1826 if (PImpl) 1827 getImpl(PImpl, AC, DL, DT).disableDT(); 1828 } 1829 1830 void LazyValueInfo::enableDT() { 1831 if (PImpl) 1832 getImpl(PImpl, AC, DL, DT).enableDT(); 1833 } 1834 1835 // Print the LVI for the function arguments at the start of each basic block. 1836 void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot( 1837 const BasicBlock *BB, formatted_raw_ostream &OS) { 1838 // Find if there are latticevalues defined for arguments of the function. 1839 auto *F = BB->getParent(); 1840 for (auto &Arg : F->args()) { 1841 ValueLatticeElement Result = LVIImpl->getValueInBlock( 1842 const_cast<Argument *>(&Arg), const_cast<BasicBlock *>(BB)); 1843 if (Result.isUndefined()) 1844 continue; 1845 OS << "; LatticeVal for: '" << Arg << "' is: " << Result << "\n"; 1846 } 1847 } 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 void LazyValueInfoAnnotatedWriter::emitInstructionAnnot( 1854 const Instruction *I, formatted_raw_ostream &OS) { 1855 1856 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 }; 1872 1873 printResult(ParentBB); 1874 // Print the LVI analysis results for the immediate successor blocks, that 1875 // are dominated by `ParentBB`. 1876 for (auto *BBSucc : successors(ParentBB)) 1877 if (DT.dominates(ParentBB, BBSucc)) 1878 printResult(BBSucc); 1879 1880 // Print LVI in blocks where `I` is used. 1881 for (auto *U : I->users()) 1882 if (auto *UseI = dyn_cast<Instruction>(U)) 1883 if (!isa<PHINode>(UseI) || DT.dominates(ParentBB, UseI->getParent())) 1884 printResult(UseI->getParent()); 1885 1886 } 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 LazyValueInfoPrinter() : FunctionPass(ID) { 1894 initializeLazyValueInfoPrinterPass(*PassRegistry::getPassRegistry()); 1895 } 1896 1897 void getAnalysisUsage(AnalysisUsage &AU) const override { 1898 AU.setPreservesAll(); 1899 AU.addRequired<LazyValueInfoWrapperPass>(); 1900 AU.addRequired<DominatorTreeWrapperPass>(); 1901 } 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 bool runOnFunction(Function &F) override { 1906 dbgs() << "LVI for function '" << F.getName() << "':\n"; 1907 auto &LVI = getAnalysis<LazyValueInfoWrapperPass>().getLVI(); 1908 auto &DTree = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 1909 LVI.printLVI(F, DTree, dbgs()); 1910 return false; 1911 } 1912 }; 1913 } 1914 1915 char LazyValueInfoPrinter::ID = 0; 1916 INITIALIZE_PASS_BEGIN(LazyValueInfoPrinter, "print-lazy-value-info", 1917 "Lazy Value Info Printer Pass", false, false) 1918 INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass) 1919 INITIALIZE_PASS_END(LazyValueInfoPrinter, "print-lazy-value-info", 1920 "Lazy Value Info Printer Pass", false, false) 1921