Index: llvm/lib/Analysis/ValueTracking.cpp =================================================================== --- llvm/lib/Analysis/ValueTracking.cpp +++ llvm/lib/Analysis/ValueTracking.cpp @@ -169,6 +169,37 @@ DemandedElts, DemandedLHS, DemandedRHS); } +// Returns a pair (Condition, ConditionIsTrue), where Condition is a branch +// condition dominating ContextI or nullptr, if no condition is found. +static std::pair +getDomPredecessorCondition(const Instruction *ContextI) { + if (!ContextI || !ContextI->getParent()) + return {nullptr, false}; + + // TODO: This is a poor/cheap way to determine dominance. Should we use a + // dominator tree (eg, from a SimplifyQuery) instead? + const BasicBlock *ContextBB = ContextI->getParent(); + const BasicBlock *PredBB = ContextBB->getSinglePredecessor(); + if (!PredBB) + return {nullptr, false}; + + // We need a conditional branch in the predecessor. + Value *PredCond; + BasicBlock *TrueBB, *FalseBB; + if (!match(PredBB->getTerminator(), m_Br(m_Value(PredCond), TrueBB, FalseBB))) + return {nullptr, false}; + + // The branch should get simplified. Don't bother simplifying this condition. + if (TrueBB == FalseBB) + return {nullptr, false}; + + assert((TrueBB == ContextBB || FalseBB == ContextBB) && + "Predecessor block does not point to successor?"); + + // Is this condition implied by the predecessor condition? + return {PredCond, TrueBB == ContextBB}; +} + static void computeKnownBits(const Value *V, const APInt &DemandedElts, KnownBits &Known, unsigned Depth, const Query &Q); @@ -2229,6 +2260,22 @@ Depth, Q); } + auto PredCond = getDomPredecessorCondition(Q.CxtI); + if (PredCond.first && PredCond.second) { + ICmpInst::Predicate Pred; + const APInt *CmpConst; + if (match(PredCond.first, + m_ICmp(Pred, m_Intrinsic(m_Specific(V)), + m_APInt(CmpConst)))) { + // dominate condition popcount(v) == 1, v is pow2 + if (Pred == CmpInst::ICMP_EQ && *CmpConst == 1) + return true; + // dominate condition popcount(v) < 2, v is pow2 or 0 + if (OrZero && Pred == CmpInst::ICMP_ULT && *CmpConst == 2) + return true; + } + } + return false; } @@ -7011,37 +7058,6 @@ return std::nullopt; } -// Returns a pair (Condition, ConditionIsTrue), where Condition is a branch -// condition dominating ContextI or nullptr, if no condition is found. -static std::pair -getDomPredecessorCondition(const Instruction *ContextI) { - if (!ContextI || !ContextI->getParent()) - return {nullptr, false}; - - // TODO: This is a poor/cheap way to determine dominance. Should we use a - // dominator tree (eg, from a SimplifyQuery) instead? - const BasicBlock *ContextBB = ContextI->getParent(); - const BasicBlock *PredBB = ContextBB->getSinglePredecessor(); - if (!PredBB) - return {nullptr, false}; - - // We need a conditional branch in the predecessor. - Value *PredCond; - BasicBlock *TrueBB, *FalseBB; - if (!match(PredBB->getTerminator(), m_Br(m_Value(PredCond), TrueBB, FalseBB))) - return {nullptr, false}; - - // The branch should get simplified. Don't bother simplifying this condition. - if (TrueBB == FalseBB) - return {nullptr, false}; - - assert((TrueBB == ContextBB || FalseBB == ContextBB) && - "Predecessor block does not point to successor?"); - - // Is this condition implied by the predecessor condition? - return {PredCond, TrueBB == ContextBB}; -} - std::optional llvm::isImpliedByDomCondition(const Value *Cond, const Instruction *ContextI, const DataLayout &DL) { Index: llvm/test/Analysis/ValueTracking/known-power-of-two-urem.ll =================================================================== --- llvm/test/Analysis/ValueTracking/known-power-of-two-urem.ll +++ llvm/test/Analysis/ValueTracking/known-power-of-two-urem.ll @@ -392,3 +392,58 @@ %r = phi i64 [ %sum, %for.body ] ret i64 %r } + +define i16 @known_power_of_two_urem_dominate_ctpop_eq_1(i16 %x, i16 %y) { +; CHECK-LABEL: @known_power_of_two_urem_dominate_ctpop_eq_1( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CTPOP:%.*]] = tail call i16 @llvm.ctpop.i16(i16 [[Y:%.*]]), !range [[RNG0:![0-9]+]] +; CHECK-NEXT: [[COND:%.*]] = icmp eq i16 [[CTPOP]], 1 +; CHECK-NEXT: br i1 [[COND]], label [[IF_THEN:%.*]], label [[IF_END:%.*]] +; CHECK: if.then: +; CHECK-NEXT: [[TMP0:%.*]] = add i16 [[Y]], -1 +; CHECK-NEXT: [[REM:%.*]] = and i16 [[TMP0]], [[X:%.*]] +; CHECK-NEXT: br label [[IF_END]] +; CHECK: if.end: +; CHECK-NEXT: [[R:%.*]] = phi i16 [ [[REM]], [[IF_THEN]] ], [ 0, [[ENTRY:%.*]] ] +; CHECK-NEXT: ret i16 [[R]] +; +entry: + %ctpop = tail call i16 @llvm.ctpop.i16(i16 %y) + %cond = icmp eq i16 %ctpop, 1 + br i1 %cond, label %if.then, label %if.end +if.then: + %rem = urem i16 %x, %y + br label %if.end +if.end: + %r = phi i16 [%rem, %if.then], [0, %entry] + ret i16 %r +} + +define i16 @known_power_of_two_urem_dominate_y_and_yminus1_eq_0(i16 %x, i16 %y) { +; CHECK-LABEL: @known_power_of_two_urem_dominate_y_and_yminus1_eq_0( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[TMP0:%.*]] = call i16 @llvm.ctpop.i16(i16 [[Y:%.*]]), !range [[RNG0]] +; CHECK-NEXT: [[COND:%.*]] = icmp ult i16 [[TMP0]], 2 +; CHECK-NEXT: br i1 [[COND]], label [[IF_THEN:%.*]], label [[IF_END:%.*]] +; CHECK: if.then: +; CHECK-NEXT: [[TMP1:%.*]] = add i16 [[Y]], -1 +; CHECK-NEXT: [[REM:%.*]] = and i16 [[TMP1]], [[X:%.*]] +; CHECK-NEXT: br label [[IF_END]] +; CHECK: if.end: +; CHECK-NEXT: [[R:%.*]] = phi i16 [ [[REM]], [[IF_THEN]] ], [ 0, [[ENTRY:%.*]] ] +; CHECK-NEXT: ret i16 [[R]] +; +entry: + %dec = add i16 %y, -1 + %and = and i16 %y, %dec + %cond = icmp eq i16 %and, 0 + br i1 %cond, label %if.then, label %if.end +if.then: + %rem = urem i16 %x, %y + br label %if.end +if.end: + %r = phi i16 [%rem, %if.then], [0, %entry] + ret i16 %r +} + +declare i16 @llvm.ctpop.i16(i16) Index: llvm/test/Transforms/InstCombine/icmp-dom.ll =================================================================== --- llvm/test/Transforms/InstCombine/icmp-dom.ll +++ llvm/test/Transforms/InstCombine/icmp-dom.ll @@ -353,12 +353,12 @@ define i32 @PR48900(i32 %i, ptr %p) { ; CHECK-LABEL: @PR48900( -; CHECK-NEXT: [[TMP1:%.*]] = call i32 @llvm.umax.i32(i32 [[I:%.*]], i32 1) -; CHECK-NEXT: [[I4:%.*]] = icmp sgt i32 [[TMP1]], 0 +; CHECK-NEXT: [[UMAX:%.*]] = call i32 @llvm.umax.i32(i32 [[I:%.*]], i32 1) +; CHECK-NEXT: [[I4:%.*]] = icmp sgt i32 [[UMAX]], 0 ; CHECK-NEXT: br i1 [[I4]], label [[TRUELABEL:%.*]], label [[FALSELABEL:%.*]] ; CHECK: truelabel: -; CHECK-NEXT: [[TMP2:%.*]] = call i32 @llvm.umin.i32(i32 [[TMP1]], i32 2) -; CHECK-NEXT: ret i32 [[TMP2]] +; CHECK-NEXT: [[SMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[UMAX]], i32 2) +; CHECK-NEXT: ret i32 [[SMIN]] ; CHECK: falselabel: ; CHECK-NEXT: ret i32 0 ; @@ -381,12 +381,12 @@ define i8 @PR48900_alt(i8 %i, ptr %p) { ; CHECK-LABEL: @PR48900_alt( -; CHECK-NEXT: [[TMP1:%.*]] = call i8 @llvm.smax.i8(i8 [[I:%.*]], i8 -127) -; CHECK-NEXT: [[I4:%.*]] = icmp ugt i8 [[TMP1]], -128 +; CHECK-NEXT: [[SMAX:%.*]] = call i8 @llvm.smax.i8(i8 [[I:%.*]], i8 -127) +; CHECK-NEXT: [[I4:%.*]] = icmp ugt i8 [[SMAX]], -128 ; CHECK-NEXT: br i1 [[I4]], label [[TRUELABEL:%.*]], label [[FALSELABEL:%.*]] ; CHECK: truelabel: -; CHECK-NEXT: [[TMP2:%.*]] = call i8 @llvm.smin.i8(i8 [[TMP1]], i8 -126) -; CHECK-NEXT: ret i8 [[TMP2]] +; CHECK-NEXT: [[UMIN:%.*]] = call i8 @llvm.smin.i8(i8 [[SMAX]], i8 -126) +; CHECK-NEXT: ret i8 [[UMIN]] ; CHECK: falselabel: ; CHECK-NEXT: ret i8 0 ; @@ -403,3 +403,61 @@ falselabel: ret i8 0 } + +define i1 @known_power_of_two_and_icmp_dominate_ctpop_eq_1(i16 %x, i16 %y) { +; CHECK-LABEL: @known_power_of_two_and_icmp_dominate_ctpop_eq_1( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CTPOP:%.*]] = tail call i16 @llvm.ctpop.i16(i16 [[Y:%.*]]), !range [[RNG0:![0-9]+]] +; CHECK-NEXT: [[COND:%.*]] = icmp eq i16 [[CTPOP]], 1 +; CHECK-NEXT: br i1 [[COND]], label [[IF_THEN:%.*]], label [[IF_END:%.*]] +; CHECK: if.then: +; CHECK-NEXT: [[AND2:%.*]] = and i16 [[Y]], [[X:%.*]] +; CHECK-NEXT: [[CMP:%.*]] = icmp ne i16 [[AND2]], 0 +; CHECK-NEXT: br label [[IF_END]] +; CHECK: if.end: +; CHECK-NEXT: [[R:%.*]] = phi i1 [ [[CMP]], [[IF_THEN]] ], [ false, [[ENTRY:%.*]] ] +; CHECK-NEXT: ret i1 [[R]] +; +entry: + %ctpop = tail call i16 @llvm.ctpop.i16(i16 %y) + %cond = icmp eq i16 %ctpop, 1 + br i1 %cond, label %if.then, label %if.end +if.then: + %and2 = and i16 %y, %x + %cmp = icmp eq i16 %and2, %y + br label %if.end +if.end: + %r = phi i1 [%cmp, %if.then], [false, %entry] + ret i1 %r +} + +; negative case: OrZero is false + +define i1 @known_power_of_two_and_icmp_dominate_ctpop_ult_2(i16 %x, i16 %y) { +; CHECK-LABEL: @known_power_of_two_and_icmp_dominate_ctpop_ult_2( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CTPOP:%.*]] = tail call i16 @llvm.ctpop.i16(i16 [[Y:%.*]]), !range [[RNG0]] +; CHECK-NEXT: [[COND:%.*]] = icmp ult i16 [[CTPOP]], 2 +; CHECK-NEXT: br i1 [[COND]], label [[IF_THEN:%.*]], label [[IF_END:%.*]] +; CHECK: if.then: +; CHECK-NEXT: [[AND:%.*]] = and i16 [[Y]], [[X:%.*]] +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i16 [[AND]], [[Y]] +; CHECK-NEXT: br label [[IF_END]] +; CHECK: if.end: +; CHECK-NEXT: [[R:%.*]] = phi i1 [ [[CMP]], [[IF_THEN]] ], [ false, [[ENTRY:%.*]] ] +; CHECK-NEXT: ret i1 [[R]] +; +entry: + %ctpop = tail call i16 @llvm.ctpop.i16(i16 %y) + %cond = icmp ult i16 %ctpop, 2 + br i1 %cond, label %if.then, label %if.end +if.then: + %and = and i16 %y, %x + %cmp = icmp eq i16 %and, %y + br label %if.end +if.end: + %r = phi i1 [%cmp, %if.then], [false, %entry] + ret i1 %r +} + +declare i16 @llvm.ctpop.i16(i16)