[ValueTracking] Search dominate condition to check if a value is pow2 or not

[bcl5980]

Summary

https://alive2.llvm.org/ce/z/RQqeWE

[StephenFan]

llvm/lib/Analysis/ValueTracking.cpp

2274

It seems it is no test coveraged here.

[bcl5980]

llvm/lib/Analysis/ValueTracking.cpp

2274

I think @known_power_of_two_urem_dominate_y_and_yminus1_eq_0 already covered it.

[StephenFan]

llvm/lib/Analysis/ValueTracking.cpp

2274

Oh, It was covered. But only when OrZero is false, if it would be better to also cover the case that OrZero is true.

[bcl5980]

add negative test for OrZero is false.

llvm/lib/Analysis/ValueTracking.cpp

static bool getShuffleDemandedElts(const ShuffleVectorInst *Shuf,
   }
 
   int NumElts =
       cast<FixedVectorType>(Shuf->getOperand(0)->getType())->getNumElements();
   return llvm::getShuffleDemandedElts(NumElts, Shuf->getShuffleMask(),
                                       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<Value *, bool>
+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);
 
 static void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth,
                              const Query &Q) {
   // Since the number of lanes in a scalable vector is unknown at compile time,
   // we track one bit which is implicitly broadcast to all lanes.  This means
   // that all lanes in a scalable vector are considered demanded.
bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero, unsigned Depth,
   // is a power of two only if the first operand is a power of two and not
   // copying a sign bit (sdiv int_min, 2).
   if (match(V, m_Exact(m_LShr(m_Value(), m_Value()))) ||
       match(V, m_Exact(m_UDiv(m_Value(), m_Value())))) {
     return isKnownToBeAPowerOfTwo(cast<Operator>(V)->getOperand(0), OrZero,
                                   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<Intrinsic::ctpop>(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;
 }
 
 /// Test whether a GEP's result is known to be non-null.
 ///
 /// Uses properties inherent in a GEP to try to determine whether it is known
 /// to be non-null.
 ///
if (std::optional<bool> Imp =
             isImpliedCondition(LHS, RHS2, DL, LHSIsTrue, Depth + 1))
       if (*Imp == false)
         return false;
   }
 
   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<Value *, bool>
-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<bool> llvm::isImpliedByDomCondition(const Value *Cond,
                                                   const Instruction *ContextI,
                                                   const DataLayout &DL) {
   assert(Cond->getType()->isIntOrIntVectorTy(1) && "Condition must be bool");
   auto PredCond = getDomPredecessorCondition(ContextI);
   if (PredCond.first)
     return isImpliedCondition(PredCond.first, Cond, DL, PredCond.second);
   return std::nullopt;

llvm/test/Analysis/ValueTracking/known-power-of-two-urem.ll

for.body:
   %i = add nuw i64 %phi, 1
   %icmp = icmp ugt i64 %i, 0
   br i1 %icmp, label %for.body, label %for.end
 
 for.end:
   %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)

llvm/test/Transforms/InstCombine/icmp-dom.ll

f:
   ret i1 %cmp2
 }
 
 ; This used to infinite loop because of a conflict
 ; with min/max canonicalization.
 
 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
 ;
   %maxcmp = icmp ugt i32 %i, 1
   %umax = select i1 %maxcmp, i32 %i, i32 1
   %i4 = icmp sgt i32 %umax, 0
   br i1 %i4, label %truelabel, label %falselabel
 
 truelabel:
   %mincmp = icmp ult i32 %umax, 2
   %smin = select i1 %mincmp, i32 %umax, i32 2
   ret i32 %smin
 
 falselabel:
   ret i32 0
 }
 
 ; This used to infinite loop because of a conflict
 ; with min/max canonicalization.
 
 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
 ;
   %maxcmp = icmp sgt i8 %i, -127
   %smax = select i1 %maxcmp, i8 %i, i8 -127
   %i4 = icmp ugt i8 %smax, 128
   br i1 %i4, label %truelabel, label %falselabel
 
 truelabel:
   %mincmp = icmp slt i8 %smax, -126
   %umin = select i1 %mincmp, i8 %smax, i8 -126
   ret i8 %umin
 
 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)