diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp --- a/llvm/lib/Analysis/ValueTracking.cpp +++ b/llvm/lib/Analysis/ValueTracking.cpp @@ -2334,20 +2334,89 @@ return false; } +// Helper for `isKnownNonNullFromDominatingCondition` to actually check the +// dominating condition. +static bool checkDominatingConditionForNonNull(const Value *V, const User *U, + const Query &Q) { + const Instruction *CtxI = Q.CxtI; + const DominatorTree *DT = Q.DT; + + // Consider only compare instructions uniquely controlling a branch + Value *RHS; + CmpInst::Predicate Pred; + bool NonNullIfTrue; + const User *CmpUse = nullptr; + if (match(U, m_c_ICmp(Pred, m_Specific(V), m_Value(RHS)))) { + CmpUse = U; + if (cmpExcludesZero(Pred, RHS)) + NonNullIfTrue = true; + else if (cmpExcludesZero(CmpInst::getInversePredicate(Pred), RHS)) + NonNullIfTrue = false; + else + return false; + } else + return false; + + SmallVector WorkList; + SmallPtrSet Visited; + for (const auto *CmpU : CmpUse->users()) { + + assert(WorkList.empty() && "Should be!"); + if (Visited.insert(CmpU).second) + WorkList.push_back(CmpU); + + while (!WorkList.empty()) { + auto *Curr = WorkList.pop_back_val(); + + // If a user is an AND, add all its users to the work list. We only + // propagate "pred != null" condition through AND because it is only + // correct to assume that all conditions of AND are met in true + // branch. + // TODO: Support similar logic of OR and EQ predicate? + if (NonNullIfTrue) + if (match(Curr, m_LogicalAnd(m_Value(), m_Value()))) { + for (const auto *CurrU : Curr->users()) + if (Visited.insert(CurrU).second) + WorkList.push_back(CurrU); + continue; + } + + if (const BranchInst *BI = dyn_cast(Curr)) { + assert(BI->isConditional() && "uses a comparison!"); + + BasicBlock *NonNullSuccessor = BI->getSuccessor(NonNullIfTrue ? 0 : 1); + BasicBlockEdge Edge(BI->getParent(), NonNullSuccessor); + if (Edge.isSingleEdge() && DT->dominates(Edge, CtxI->getParent())) + return true; + } else if (NonNullIfTrue && isGuard(Curr) && + DT->dominates(cast(Curr), CtxI)) { + return true; + } + } + } + + return false; +} + static bool isKnownNonNullFromDominatingCondition(const Value *V, - const Instruction *CtxI, - const DominatorTree *DT) { + unsigned DomDepth, + const Query &Q) { assert(!isa(V) && "Called for constant?"); - + const Instruction *CtxI = Q.CxtI; + const DominatorTree *DT = Q.DT; if (!CtxI || !DT) return false; - unsigned NumUsesExplored = 0; + if (DomDepth++ >= MaxAnalysisRecursionDepth) + return false; + + // Scale down number of uses explored with depth to avoid otherwise + // potentially very large exponential explosition. + unsigned NumUsesRemaining = (DomConditionsMaxUses / DomDepth) + 1; for (const auto *U : V->users()) { // Avoid massive lists - if (NumUsesExplored >= DomConditionsMaxUses) + if (NumUsesRemaining-- == 0) break; - NumUsesExplored++; // If the value is used as an argument to a call or invoke, then argument // attributes may provide an answer about null-ness. @@ -2368,56 +2437,42 @@ return true; } - // Consider only compare instructions uniquely controlling a branch - Value *RHS; - CmpInst::Predicate Pred; - if (!match(U, m_c_ICmp(Pred, m_Specific(V), m_Value(RHS)))) - continue; - - bool NonNullIfTrue; - if (cmpExcludesZero(Pred, RHS)) - NonNullIfTrue = true; - else if (cmpExcludesZero(CmpInst::getInversePredicate(Pred), RHS)) - NonNullIfTrue = false; - else - continue; - - SmallVector WorkList; - SmallPtrSet Visited; - for (const auto *CmpU : U->users()) { - assert(WorkList.empty() && "Should be!"); - if (Visited.insert(CmpU).second) - WorkList.push_back(CmpU); - - while (!WorkList.empty()) { - auto *Curr = WorkList.pop_back_val(); - - // If a user is an AND, add all its users to the work list. We only - // propagate "pred != null" condition through AND because it is only - // correct to assume that all conditions of AND are met in true branch. - // TODO: Support similar logic of OR and EQ predicate? - if (NonNullIfTrue) - if (match(Curr, m_LogicalAnd(m_Value(), m_Value()))) { - for (const auto *CurrU : Curr->users()) - if (Visited.insert(CurrU).second) - WorkList.push_back(CurrU); - continue; - } - - if (const BranchInst *BI = dyn_cast(Curr)) { - assert(BI->isConditional() && "uses a comparison!"); - - BasicBlock *NonNullSuccessor = - BI->getSuccessor(NonNullIfTrue ? 0 : 1); - BasicBlockEdge Edge(BI->getParent(), NonNullSuccessor); - if (Edge.isSingleEdge() && DT->dominates(Edge, CtxI->getParent())) - return true; - } else if (NonNullIfTrue && isGuard(Curr) && - DT->dominates(cast(Curr), CtxI)) { + bool ImpliesNonZero = false; + if (auto *OpU = dyn_cast(U)) { + switch (OpU->getOpcode()) { + case Instruction::ICmp: + if (checkDominatingConditionForNonNull(V, U, Q)) return true; + break; + case Instruction::And: + ImpliesNonZero = true; + break; + case Instruction::Sub: + if (auto *C = dyn_cast(OpU->getOperand(0))) + ImpliesNonZero = C->isNullValue(); + break; + case Instruction::Call: + if (auto *II = dyn_cast(OpU)) { + switch (II->getIntrinsicID()) { + case Intrinsic::abs: + case Intrinsic::bitreverse: + case Intrinsic::bswap: + case Intrinsic::ctpop: + ImpliesNonZero = true; + break; + default: + break; + } } + break; + default: + break; } } + if (ImpliesNonZero && + (isKnownNonZeroFromAssume(U, Q) || + isKnownNonNullFromDominatingCondition(U, DomDepth, Q))) + return true; } return false; @@ -2579,7 +2634,7 @@ } if (!isa(V) && - isKnownNonNullFromDominatingCondition(V, Q.CxtI, Q.DT)) + isKnownNonNullFromDominatingCondition(V, /*DomDepth*/ 0, Q)) return true; const Operator *I = dyn_cast(V); diff --git a/llvm/test/Analysis/ValueTracking/known-non-zero-through-dom-use.ll b/llvm/test/Analysis/ValueTracking/known-non-zero-through-dom-use.ll --- a/llvm/test/Analysis/ValueTracking/known-non-zero-through-dom-use.ll +++ b/llvm/test/Analysis/ValueTracking/known-non-zero-through-dom-use.ll @@ -58,9 +58,7 @@ ; CHECK-NEXT: br i1 [[NE]], label [[TRUE:%.*]], label [[FALSE:%.*]] ; CHECK: true: ; CHECK-NEXT: [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]] -; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i8 [[Y]], 0 -; CHECK-NEXT: [[R:%.*]] = or i1 [[CMP0]], [[CMP1]] -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 [[CMP0]] ; CHECK: false: ; CHECK-NEXT: call void @use1(i1 [[NE]]) ; CHECK-NEXT: ret i1 [[NE]] @@ -85,9 +83,7 @@ ; CHECK-NEXT: [[NE:%.*]] = icmp sgt i16 [[Z]], 3 ; CHECK-NEXT: call void @llvm.assume(i1 [[NE]]) ; CHECK-NEXT: [[CMP0:%.*]] = icmp ugt i16 [[X]], [[Y:%.*]] -; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i16 [[Y]], 0 -; CHECK-NEXT: [[R:%.*]] = or i1 [[CMP0]], [[CMP1]] -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 [[CMP0]] ; %z = call i16 @llvm.bswap.i16(i16 %x) %ne = icmp sgt i16 %z, 3 @@ -108,9 +104,8 @@ ; CHECK-NEXT: call void @use1(i1 [[RT]]) ; CHECK-NEXT: ret i1 [[RT]] ; CHECK: true: -; CHECK-NEXT: [[TMP1:%.*]] = add i8 [[X]], -1 -; CHECK-NEXT: [[TMP2:%.*]] = icmp uge i8 [[TMP1]], [[Y:%.*]] -; CHECK-NEXT: ret i1 [[TMP2]] +; CHECK-NEXT: [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]] +; CHECK-NEXT: ret i1 [[CMP0]] ; %z = call i8 @llvm.bitreverse.i8(i8 %x) %ne = icmp slt i8 %z, -4 @@ -140,9 +135,7 @@ ; CHECK-NEXT: br i1 [[NE]], label [[TRUE:%.*]], label [[FALSE:%.*]] ; CHECK: true: ; CHECK-NEXT: [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]] -; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i8 [[Y]], 0 -; CHECK-NEXT: [[R:%.*]] = or i1 [[CMP0]], [[CMP1]] -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 [[CMP0]] ; CHECK: false: ; CHECK-NEXT: call void @use1(i1 [[NE]]) ; CHECK-NEXT: ret i1 [[NE]] @@ -199,9 +192,7 @@ ; CHECK-NEXT: br i1 [[NE_NOT]], label [[FALSE:%.*]], label [[TRUE:%.*]] ; CHECK: true: ; CHECK-NEXT: [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]] -; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i8 [[Y]], 0 -; CHECK-NEXT: [[R:%.*]] = or i1 [[CMP0]], [[CMP1]] -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 [[CMP0]] ; CHECK: false: ; CHECK-NEXT: [[RT:%.*]] = icmp eq i8 [[X]], 0 ; CHECK-NEXT: call void @use1(i1 [[RT]]) @@ -237,9 +228,8 @@ ; CHECK-NEXT: [[R:%.*]] = or i1 [[CMP0]], [[CMP1]] ; CHECK-NEXT: ret i1 [[R]] ; CHECK: false: -; CHECK-NEXT: [[RT:%.*]] = icmp eq i8 [[X]], 0 -; CHECK-NEXT: call void @use1(i1 [[RT]]) -; CHECK-NEXT: ret i1 [[RT]] +; CHECK-NEXT: call void @use1(i1 false) +; CHECK-NEXT: ret i1 false ; %z = and i8 %x, 123 %ne = icmp slt i8 %z, 5 @@ -299,9 +289,7 @@ ; CHECK-NEXT: ret i1 [[RT]] ; CHECK: false: ; CHECK-NEXT: [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]] -; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i8 [[Y]], 0 -; CHECK-NEXT: [[R:%.*]] = or i1 [[CMP0]], [[CMP1]] -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 [[CMP0]] ; %z = and i8 %x, 123 %z2 = sub i8 0, %z @@ -336,9 +324,7 @@ ; CHECK-NEXT: ret i1 [[RT]] ; CHECK: false: ; CHECK-NEXT: [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]] -; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i8 [[Y]], 0 -; CHECK-NEXT: [[R:%.*]] = or i1 [[CMP0]], [[CMP1]] -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 [[CMP0]] ; %z = and i8 %x, 123 %z2 = sub i8 0, %z @@ -374,9 +360,7 @@ ; CHECK-NEXT: ret i1 [[RT]] ; CHECK: false: ; CHECK-NEXT: [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]] -; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i8 [[Y]], 0 -; CHECK-NEXT: [[R:%.*]] = or i1 [[CMP0]], [[CMP1]] -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 [[CMP0]] ; %z = and i8 %x, 123 %z2 = sub i8 0, %z @@ -408,9 +392,7 @@ ; CHECK-NEXT: [[NE:%.*]] = icmp ne i8 [[Z4]], 0 ; CHECK-NEXT: call void @llvm.assume(i1 [[NE]]) ; CHECK-NEXT: [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]] -; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i8 [[Y]], 0 -; CHECK-NEXT: [[R:%.*]] = or i1 [[CMP0]], [[CMP1]] -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 [[CMP0]] ; %z = and i8 %x, 123 %z2 = sub i8 0, %z