Lines Matching +full:depth +full:- +full:wise
1 //===- LazyValueInfo.cpp - Value constraint analysis ------------*- C++ -*-===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
12 //===----------------------------------------------------------------------===//
47 #define DEBUG_TYPE "lazy-value-info"
57 INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info",
61 INITIALIZE_PASS_END(LazyValueInfoWrapperPass, "lazy-value-info",
86 //===----------------------------------------------------------------------===//
88 //===----------------------------------------------------------------------===//
113 /// the per-value lattice elements, as well as a separate set for
134 return It->second.get();
142 return It->second.get();
156 // Insert over-defined values into their own cache to reduce memory
159 Entry->OverDefined.insert(Val);
161 Entry->LatticeElements.insert({Val, Result});
172 if (Entry->OverDefined.count(V))
175 auto LatticeIt = Entry->LatticeElements.find_as(V);
176 if (LatticeIt == Entry->LatticeElements.end())
179 return LatticeIt->second;
186 if (!Entry->NonNullPointers) {
187 Entry->NonNullPointers = InitFn(BB);
188 for (Value *V : *Entry->NonNullPointers)
192 return Entry->NonNullPointers->count(V);
195 /// clear - Empty the cache.
217 Pair.second->LatticeElements.erase(V);
218 Pair.second->OverDefined.erase(V);
219 if (Pair.second->NonNullPointers)
220 Pair.second->NonNullPointers->erase(V);
231 Parent->eraseValue(*this);
254 if (!Entry || Entry->OverDefined.empty())
256 SmallVector<Value *, 4> ValsToClear(Entry->OverDefined.begin(),
257 Entry->OverDefined.end());
259 // Use a worklist to perform a depth-first search of OldSucc's successors.
272 if (OI == BlockCache.end() || OI->second->OverDefined.empty())
274 auto &ValueSet = OI->second->OverDefined;
324 /// Keeps track of which block-value pairs are in BlockValueStack.
334 << BV.first->getName() << "\n");
404 bool UseBlockValue, unsigned Depth = 0);
471 // Because of the design of the overdefined cache currently being per-block
472 // to avoid naming-related issues (IE it wants to try to give different
506 dbgs() << "POP " << *e.second << " in " << e.first->getName() << " = "
542 switch (BBI->getOpcode()) {
547 if (std::optional<ConstantRange> Range = cast<CallBase>(BBI)->getRange())
551 if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))
552 if (isa<IntegerType>(BBI->getType())) {
558 // Nothing known - will be intersected with other facts
581 if (!BBI || BBI->getParent() != BB)
593 // and the like to prove non-nullness, but it's not clear that's worth it
594 // compile time wise. The context-insensitive value walk done inside
599 PointerType *PT = dyn_cast<PointerType>(BBI->getType());
603 if (BBI->getType()->isIntOrIntVectorTy()) {
620 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
621 << "' - unknown inst def found.\n");
627 if (Ptr->getType()->getPointerAddressSpace() == 0)
634 AddNonNullPointer(L->getPointerOperand(), PtrSet);
636 AddNonNullPointer(S->getPointerOperand(), PtrSet);
638 if (MI->isVolatile()) return;
641 ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
642 if (!Len || Len->isZero()) return;
644 AddNonNullPointer(MI->getRawDest(), PtrSet);
646 AddNonNullPointer(MTI->getRawSource(), PtrSet);
651 if (NullPointerIsDefined(BB->getParent(),
652 Val->getType()->getPointerAddressSpace()))
655 Val = Val->stripInBoundsOffsets();
669 if (BB->isEntryBlock()) {
670 assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
671 if (std::optional<ConstantRange> Range = cast<Argument>(Val)->getRange())
678 // in a depth first manner. In practice, this has the effect of discovering
696 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
697 << "' - overdefined because of pred '"
698 << Pred->getName() << "' (non local).\n");
715 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
716 BasicBlock *PhiBB = PN->getIncomingBlock(i);
717 Value *PhiVal = PN->getIncomingValue(i);
732 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
733 << "' - overdefined because of pred (local).\n");
752 BasicBlock *BB = BBI->getParent();
753 for (auto &AssumeVH : AC->assumptionsFor(Val)) {
761 if (I->getParent() != BB || !isValidAssumeForContext(I, BBI))
764 BBLV = BBLV.intersect(*getValueFromCondition(Val, I->getArgOperand(0),
770 if (GuardDecl && !GuardDecl->use_empty() &&
771 BBI->getIterator() != BB->begin()) {
773 make_range(std::next(BBI->getIterator().getReverse()), BB->rend())) {
785 PointerType *PTy = dyn_cast<PointerType>(Val->getType());
786 if (PTy && BB->getTerminator() == BBI &&
796 getBlockValue(SI->getTrueValue(), BB, SI);
802 getBlockValue(SI->getFalseValue(), BB, SI);
808 const ConstantRange &TrueCR = TrueVal.asConstantRange(SI->getType());
809 const ConstantRange &FalseCR = FalseVal.asConstantRange(SI->getType());
816 ((LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) ||
817 (RHS == SI->getTrueValue() && LHS == SI->getFalseValue()))) {
838 if (LHS == SI->getTrueValue())
841 if (LHS == SI->getFalseValue())
848 if (LHS == SI->getTrueValue())
851 if (LHS == SI->getFalseValue())
860 Value *Cond = SI->getCondition();
865 TrueVal.intersect(*getValueFromCondition(SI->getTrueValue(), Cond,
869 FalseVal.intersect(*getValueFromCondition(SI->getFalseValue(), Cond,
884 return OptVal->asConstantRange(V->getType());
892 switch (CI->getOpcode()) {
899 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
900 << "' - overdefined (unknown cast).\n");
907 std::optional<ConstantRange> LHSRes = getRangeFor(CI->getOperand(0), CI, BB);
913 const unsigned ResultBitWidth = CI->getType()->getScalarSizeInBits();
918 return ValueLatticeElement::getRange(LHSRange.castOp(CI->getOpcode(),
927 Value *LHS = I->getOperand(0);
928 Value *RHS = I->getOperand(1);
932 bool XIsLHS) -> std::optional<ValueLatticeElement> {
933 Value *Cond = Y->getCondition();
935 Constant *TrueC = dyn_cast<Constant>(Y->getTrueValue());
938 Constant *FalseC = dyn_cast<Constant>(Y->getFalseValue());
947 ->asConstantRange(X->getType()));
951 ->asConstantRange(X->getType()));
952 ConstantRange TrueY = TrueC->toConstantRange();
953 ConstantRange FalseY = FalseC->toConstantRange();
993 assert(BO->getOperand(0)->getType()->isSized() &&
996 unsigned NoWrapKind = OBO->getNoWrapKind();
1000 return CR1.overflowingBinaryOp(BO->getOpcode(), CR2, NoWrapKind);
1006 return CR1.binaryOp(BO->getOpcode(), CR2);
1015 return CR1.binaryOp(WO->getBinaryOp(), CR2);
1022 if (!ConstantRange::isIntrinsicSupported(II->getIntrinsicID())) {
1023 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
1024 << "' - unknown intrinsic.\n");
1029 for (Value *Op : II->args()) {
1037 ConstantRange::intrinsic(II->getIntrinsicID(), OpRanges))
1045 getBlockValue(IEI->getOperand(1), BB, IEI);
1051 getBlockValue(IEI->getOperand(0), BB, IEI);
1059 if (OptEltVal->isConstant())
1069 if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))
1070 if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 0)
1076 EVI->getAggregateOperand(), EVI->getIndices(),
1077 EVI->getDataLayout()))
1080 LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
1081 << "' - overdefined (unknown extractvalue).\n");
1101 Offset = -*C;
1125 ConstantRange RHSRange(RHS->getType()->getScalarSizeInBits(),
1128 RHSRange = ConstantRange(CI->getValue());
1131 getBlockValue(RHS, CxtI->getParent(), CxtI);
1134 RHSRange = R->asConstantRange(RHS->getType());
1158 return Invert ? CR->inverse() : CR;
1165 unsigned BitWidth = RHS->getType()->getScalarSizeInBits();
1172 ConstantRange::makeExactICmpRegion(Pred, RHSConst->getValue());
1185 Value *LHS = ICI->getOperand(0);
1186 Value *RHS = ICI->getOperand(1);
1190 isTrueDest ? ICI->getPredicate() : ICI->getInversePredicate();
1193 if (ICI->isEquality() && LHS == Val) {
1201 Type *Ty = Val->getType();
1202 if (!Ty->isIntegerTy())
1205 unsigned BitWidth = Ty->getScalarSizeInBits();
1251 // icmp slt (ashr X, ShAmtC), C --> icmp slt X, C << ShAmtC
1258 EdgePred, *C, [&](const APInt &RHS) -> std::optional<ConstantRange> {
1269 // a - b or ptrtoint(a) - ptrtoint(b) ==/!= 0 if a ==/!= b
1271 if (ICI->isEquality() && match(Val, m_Sub(m_Value(X), m_Value(Y)))) {
1276 Constant *NullVal = Constant::getNullValue(Val->getType());
1294 if (WO->getLHS() != Val || !match(WO->getRHS(), m_APInt(C)))
1299 WO->getBinaryOp(), *C, WO->getNoWrapKind());
1311 unsigned Depth) {
1316 if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))
1317 if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 1)
1320 if (++Depth == MaxAnalysisRecursionDepth)
1325 return getValueFromCondition(Val, N, !IsTrueDest, UseBlockValue, Depth);
1337 getValueFromCondition(Val, L, IsTrueDest, UseBlockValue, Depth);
1341 getValueFromCondition(Val, R, IsTrueDest, UseBlockValue, Depth);
1345 // if (L && R) -> intersect L and R
1346 // if (!(L || R)) -> intersect !L and !R
1347 // if (L || R) -> union L and R
1348 // if (!(L && R)) -> union !L and !R
1350 LV->mergeIn(*RV);
1354 return LV->intersect(*RV);
1359 return is_contained(Usr->operands(), Op);
1378 Constant* OpConst = Constant::getIntegerValue(Op->getType(), OpConstVal);
1381 assert(CI->getOperand(0) == Op && "Operand 0 isn't Op");
1383 simplifyCastInst(CI->getOpcode(), OpConst,
1384 CI->getDestTy(), DL))) {
1385 return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
1388 bool Op0Match = BO->getOperand(0) == Op;
1389 bool Op1Match = BO->getOperand(1) == Op;
1392 Value *LHS = Op0Match ? OpConst : BO->getOperand(0);
1393 Value *RHS = Op1Match ? OpConst : BO->getOperand(1);
1395 simplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) {
1396 return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
1399 assert(cast<FreezeInst>(Usr)->getOperand(0) == Op && "Operand 0 isn't Op");
1405 /// Compute the value of Val on the edge BBFrom -> BBTo.
1411 if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
1414 if (BI->isConditional() &&
1415 BI->getSuccessor(0) != BI->getSuccessor(1)) {
1416 bool isTrueDest = BI->getSuccessor(0) == BBTo;
1417 assert(BI->getSuccessor(!isTrueDest) == BBTo &&
1419 Value *Condition = BI->getCondition();
1426 Type::getInt1Ty(Val->getContext()), isTrueDest));
1435 if (!Result->isOverdefined())
1439 assert(Result->isOverdefined() && "Result isn't overdefined");
1443 if (isa<IntegerType>(Usr->getType()) && isOperationFoldable(Usr)) {
1444 const DataLayout &DL = BBTo->getDataLayout();
1463 for (unsigned i = 0; i < Usr->getNumOperands(); ++i) {
1464 Value *Op = Usr->getOperand(i);
1476 if (!Result->isOverdefined())
1483 if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
1484 Value *Condition = SI->getCondition();
1485 if (!isa<IntegerType>(Val->getType()))
1499 bool DefaultCase = SI->getDefaultDest() == BBTo;
1500 unsigned BitWidth = Val->getType()->getIntegerBitWidth();
1503 for (auto Case : SI->cases()) {
1504 APInt CaseValue = Case.getCaseValue()->getValue();
1508 const DataLayout &DL = BBTo->getDataLayout();
1532 /// Compute the value of Val on the edge BBFrom -> BBTo or the value at
1551 getBlockValue(Val, BBFrom, BBFrom->getTerminator());
1566 return LocalResult->intersect(InBlock);
1572 << BB->getName() << "'\n");
1588 LLVM_DEBUG(dbgs() << "LVI Getting value " << *V << " at '" << CxtI->getName()
1607 << FromBB->getName() << "' to '" << ToBB->getName()
1627 ValueLatticeElement VL = getValueInBlock(V, CxtI->getParent(), CxtI);
1636 auto *CurrI = cast<Instruction>(CurrU->getUser());
1640 if (!isGuaranteedNotToBeUndef(SI->getCondition(), AC))
1642 if (CurrU->getOperandNo() == 1)
1644 *getValueFromCondition(V, SI->getCondition(), /*IsTrueDest*/ true,
1646 else if (CurrU->getOperandNo() == 2)
1648 *getValueFromCondition(V, SI->getCondition(), /*IsTrueDest*/ false,
1651 // TODO: Use non-local query?
1652 CondVal = *getEdgeValueLocal(V, PHI->getIncomingBlock(*CurrU),
1653 PHI->getParent(), /*UseBlockValue*/ false);
1658 // Only follow one-use chain, to allow direct intersection of conditions.
1661 // Stop walking if we hit a non-speculatable instruction. Even if the
1667 if (!CurrI->hasOneUse() ||
1670 CurrU = &*CurrI->use_begin();
1680 //===----------------------------------------------------------------------===//
1682 //===----------------------------------------------------------------------===//
1688 Impl->clear();
1706 const DataLayout &DL = M->getDataLayout();
1757 V = V->stripPointerCasts();
1769 BasicBlock *BB = CxtI->getParent();
1771 getOrCreateImpl(BB->getModule()).getValueInBlock(V, BB, CxtI);
1778 return ConstantInt::get(V->getType(), *SingleVal);
1785 BasicBlock *BB = CxtI->getParent();
1787 getOrCreateImpl(BB->getModule()).getValueInBlock(V, BB, CxtI);
1788 return Result.asConstantRange(V->getType(), UndefAllowed);
1795 getOrCreateImpl(Inst->getModule()).getValueAtUse(U);
1796 return Result.asConstantRange(U->getType(), UndefAllowed);
1804 Module *M = FromBB->getModule();
1813 return ConstantInt::get(V->getType(), *SingleVal);
1822 Module *M = FromBB->getModule();
1826 return Result.asConstantRange(V->getType(), /*UndefAllowed*/ true);
1836 Type *ResTy = CmpInst::makeCmpResultType(C->getType());
1839 ConstantRange RHS = C->toConstantRange();
1851 // !C1 == C -> false iff C1 == C.
1854 if (Res && Res->isNullValue())
1857 // !C1 != C -> true iff C1 == C.
1860 if (Res && Res->isNullValue())
1875 Module *M = FromBB->getModule();
1879 return getPredicateResult(Pred, C, Result, M->getDataLayout());
1889 Module *M = CxtI->getModule();
1890 const DataLayout &DL = M->getDataLayout();
1891 if (V->getType()->isPointerTy() && C->isNullValue() &&
1892 isKnownNonZero(V->stripPointerCastsSameRepresentation(), DL)) {
1893 Type *ResTy = CmpInst::makeCmpResultType(C->getType());
1902 UseBlockValue ? Impl.getValueInBlock(V, CxtI->getParent(), CxtI)
1928 // CFG and/or value graph, but there are non-obvious compile time vs quality
1930 BasicBlock *BB = CxtI->getParent();
1943 if (PHI->getParent() == BB) {
1945 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
1946 Value *Incoming = PHI->getIncomingValue(i);
1947 BasicBlock *PredBB = PHI->getIncomingBlock(i);
1967 if (!isa<Instruction>(V) || cast<Instruction>(V)->getParent() != BB) {
1998 // Got two non-Constant values. Try to determine the comparison results based
2000 // non-overlapping ranges.
2002 Module *M = CxtI->getModule();
2004 getOrCreateImpl(M).getValueInBlock(LHS, CxtI->getParent(), CxtI);
2009 getOrCreateImpl(M).getValueInBlock(RHS, CxtI->getParent(), CxtI);
2010 Type *Ty = CmpInst::makeCmpResultType(LHS->getType());
2011 return L.getCompare(Pred, Ty, R, M->getDataLayout());
2019 Impl->threadEdge(PredBB, OldSucc, NewSucc);
2024 Impl->forgetValue(V);
2029 Impl->eraseBlock(BB);
2034 Impl->clear();
2039 Impl->printLVI(F, DTree, OS);
2046 auto *F = BB->getParent();
2047 for (const auto &Arg : F->args()) {
2048 ValueLatticeElement Result = LVIImpl->getValueInBlock(
2063 auto *ParentBB = I->getParent();
2073 ValueLatticeElement Result = LVIImpl->getValueInBlock(
2076 BB->printAsOperand(OS, false);
2088 for (const auto *U : I->users())
2090 if (!isa<PHINode>(UseI) || DT.dominates(ParentBB, UseI->getParent()))
2091 printResult(UseI->getParent());