[ValueTracking] Improve analysis of knownbits from incoming phi edges.

[goldstein.w.n]

Summary

Use ConstantRange::toKnownBits(ConstantRange::makeExactICmpRegion)
to get the constraints on the incoming phi edge instead of bespoke logic.
This covers a lot more cases.

Proofs: https://alive2.llvm.org/ce/z/gnj4o-

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

1530

Can this code be reduced to ConstantRange::makeExactICmpRegion() + ConstantRange::toKnownBits()?

[goldstein.w.n]

llvm/lib/Analysis/ValueTracking.cpp

1530

Convenient :)

[goldstein.w.n]

Nikics suggestion to use ConstantRange codes :)

[nikic]

LGTM

[goldstein.w.n]

Rebase

[foad]

Just fill in missing cases (TODO) for ugt, uge, sgt, sge,
slt, and sle. These are all in the same spirit as ult/uge, but
each of the other conditions have different constraints.

Update the description?

llvm/lib/Analysis/ValueTracking.cpp

1470

I don't quite understand this TODO, but it seems *maybe* you have implemented what it was suggesting?

[goldstein.w.n]

llvm/lib/Analysis/ValueTracking.cpp

1470

I interpretted it to mean use computeKnownBits on RHS instead of only accepting constant RHS.

[goldstein.w.n]

In D157800#4584089, @foad wrote:

Just fill in missing cases (TODO) for ugt, uge, sgt, sge,
slt, and sle. These are all in the same spirit as ult/uge, but
each of the other conditions have different constraints.

Update the description?

Done :)

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

llvm/lib/Analysis/ValueTracking.cpp

if (Depth < MaxAnalysisRecursionDepth - 1 && Known.isUnknown()) {
         computeKnownBits(IncValue, Known2, MaxAnalysisRecursionDepth - 1, RecQ);
 
         // If this failed, see if we can use a conditional branch into the phi
         // to help us determine the range of the value.
         if (Known2.isUnknown()) {
           ICmpInst::Predicate Pred;
           const APInt *RHSC;
           BasicBlock *TrueSucc, *FalseSucc;
           // TODO: Use RHS Value and compute range from its known bits.
           if (match(RecQ.CxtI,
                     m_Br(m_c_ICmp(Pred, m_Specific(IncValue), m_APInt(RHSC)),
                          m_BasicBlock(TrueSucc), m_BasicBlock(FalseSucc)))) {
             // Check for cases of duplicate successors.
             if ((TrueSucc == P->getParent()) != (FalseSucc == P->getParent())) {
               // If we're using the false successor, invert the predicate.
               if (FalseSucc == P->getParent())
                 Pred = CmpInst::getInversePredicate(Pred);
 
+              APInt RHS = *RHSC;
               switch (Pred) {
               case CmpInst::Predicate::ICMP_EQ:
-                Known2 = KnownBits::makeConstant(*RHSC);
+                Known2 = KnownBits::makeConstant(RHS);
                 break;
+              case CmpInst::Predicate::ICMP_ULT:
+                RHS -= 1;
+                [[fallthrough]];
               case CmpInst::Predicate::ICMP_ULE:
-                Known2.Zero.setHighBits(RHSC->countl_zero());
+                // X ule/ult Y implies highest set bit in X is leq highest set
+                // bit in Y.
+                Known2.Zero.setHighBits(RHS.countl_zero());
                 break;
-              case CmpInst::Predicate::ICMP_ULT:
-                Known2.Zero.setHighBits((*RHSC - 1).countl_zero());
+              case CmpInst::Predicate::ICMP_UGT:
+                RHS += 1;
+                [[fallthrough]];
+              case CmpInst::Predicate::ICMP_UGE:
+                // X uge/ugt Y implies any leading ones in Y must be set in X as
+                // well.
+                Known2.One.setHighBits(RHS.countl_one());
+                break;
+              case CmpInst::Predicate::ICMP_SGT:
+                // X sgt -1 -> X doesn't have signbit set
+                RHS += 1;
+                [[fallthrough]];
+              case CmpInst::Predicate::ICMP_SGE:
+                if (!RHS.isSignBitSet()) {
+                  // X sge/sgt C_Positive -> same as uge/ugt but start from
+                  // after the sign bit (and leave signbit unset).
+                  RHS.setSignBit();
+                  Known2.One.setHighBits(RHS.countl_one());
+                  Known2.One.clearSignBit();
+                  Known2.Zero.setSignBit();
+                }
+                break;
+              case CmpInst::Predicate::ICMP_SLT:
+                // X slt 0 -> X has signbit set
+                RHS -= 1;
+                [[fallthrough]];
+              case CmpInst::Predicate::ICMP_SLE:
+                if (RHS.isSignBitSet()) {
+                  // X sle/slt C_Negative -> same as ule/ult but start from
+                  // after the sign bit (and leave signbit unset).
+                  RHS.clearSignBit();
+                  Known2.Zero.setHighBits(RHS.countl_zero());
+                  Known2.Zero.clearSignBit();
+                  Known2.One.setSignBit();
+                }
                 break;
               default:
-                // TODO - add additional integer predicate handling.
                 break;
               }
             }
           }
         }
 
         Known = Known.intersectWith(Known2);
         // If all bits have been ruled out, there's no need to check
         // more operands.

llvm/test/Analysis/ValueTracking/phi-known-bits.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=instcombine < %s -S | FileCheck %s
 
 define i8 @phi_ugt_high_bits(i8 %x) {
 ; CHECK-LABEL: @phi_ugt_high_bits(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i8 [[X:%.*]], -65
 ; CHECK-NEXT:    br i1 [[CMP]], label [[T:%.*]], label [[F:%.*]]
 ; CHECK:       T:
-; CHECK-NEXT:    [[V:%.*]] = phi i8 [ [[X]], [[ENTRY:%.*]] ], [ -1, [[F]] ]
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[V]], 64
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 64
 ; CHECK:       F:
 ; CHECK-NEXT:    br i1 true, label [[T]], label [[F]]
 ;
 entry:
   %cmp = icmp ugt i8 %x, 191
   br i1 %cmp, label %T, label %F
 T:
   %v = phi i8 [ %x, %entry], [-1, %F]

 }
 
 define i8 @phi_uge_high_bits(i8 %x) {
 ; CHECK-LABEL: @phi_uge_high_bits(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i8 [[X:%.*]], -65
 ; CHECK-NEXT:    br i1 [[CMP]], label [[T:%.*]], label [[F:%.*]]
 ; CHECK:       T:
-; CHECK-NEXT:    [[V:%.*]] = phi i8 [ [[X]], [[ENTRY:%.*]] ], [ -1, [[F]] ]
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[V]], 64
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 64
 ; CHECK:       F:
 ; CHECK-NEXT:    br i1 true, label [[T]], label [[F]]
 ;
 entry:
   %cmp = icmp uge i8 %x, 192
   br i1 %cmp, label %T, label %F
 T:
   %v = phi i8 [ %x, %entry], [-1, %F]

 }
 
 define i8 @phi_sge_high_bits(i8 %x) {
 ; CHECK-LABEL: @phi_sge_high_bits(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i8 [[X:%.*]], 95
 ; CHECK-NEXT:    br i1 [[CMP]], label [[T:%.*]], label [[F:%.*]]
 ; CHECK:       T:
-; CHECK-NEXT:    [[V:%.*]] = phi i8 [ [[X]], [[ENTRY:%.*]] ], [ -1, [[F]] ]
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[V]], 96
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 96
 ; CHECK:       F:
 ; CHECK-NEXT:    br i1 true, label [[T]], label [[F]]
 ;
 entry:
   %cmp = icmp sge i8 %x, 96
   br i1 %cmp, label %T, label %F
 T:
   %v = phi i8 [ %x, %entry], [-1, %F]

 }
 
 define i8 @phi_sgt_high_bits(i8 %x) {
 ; CHECK-LABEL: @phi_sgt_high_bits(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i8 [[X:%.*]], -1
 ; CHECK-NEXT:    br i1 [[CMP]], label [[T:%.*]], label [[F:%.*]]
 ; CHECK:       T:
-; CHECK-NEXT:    [[V:%.*]] = phi i8 [ [[X]], [[ENTRY:%.*]] ], [ 0, [[F]] ]
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[V]], -128
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 0
 ; CHECK:       F:
 ; CHECK-NEXT:    br i1 true, label [[T]], label [[F]]
 ;
 entry:
   %cmp = icmp sgt i8 %x, -1
   br i1 %cmp, label %T, label %F
 T:
   %v = phi i8 [ %x, %entry], [0, %F]
   %r = and i8 %v, 128
   ret i8 %r
 F:
   br i1 true, label %T, label %F
 }
 
 define i8 @phi_sgt_high_bits2(i8 %x) {
 ; CHECK-LABEL: @phi_sgt_high_bits2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i8 [[X:%.*]], 63
 ; CHECK-NEXT:    br i1 [[CMP]], label [[T:%.*]], label [[F:%.*]]
 ; CHECK:       T:
-; CHECK-NEXT:    [[V:%.*]] = phi i8 [ [[X]], [[ENTRY:%.*]] ], [ -1, [[F]] ]
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[V]], 64
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 64
 ; CHECK:       F:
 ; CHECK-NEXT:    br i1 true, label [[T]], label [[F]]
 ;
 entry:
   %cmp = icmp sgt i8 %x, 63
   br i1 %cmp, label %T, label %F
 T:
   %v = phi i8 [ %x, %entry], [-1, %F]

 }
 
 define i8 @phi_slt_high_bits(i8 %x) {
 ; CHECK-LABEL: @phi_slt_high_bits(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[X:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[T:%.*]], label [[F:%.*]]
 ; CHECK:       T:
-; CHECK-NEXT:    [[V:%.*]] = phi i8 [ [[X]], [[ENTRY:%.*]] ], [ -1, [[F]] ]
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[V]], -128
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 -128
 ; CHECK:       F:
 ; CHECK-NEXT:    br i1 true, label [[T]], label [[F]]
 ;
 entry:
   %cmp = icmp slt i8 %x, 0
   br i1 %cmp, label %T, label %F
 T:
   %v = phi i8 [ %x, %entry], [-1, %F]
   %r = and i8 %v, 128
   ret i8 %r
 F:
   br i1 true, label %T, label %F
 }
 
 define i8 @phi_slt_high_bits2(i8 %x) {
 ; CHECK-LABEL: @phi_slt_high_bits2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[X:%.*]], -64
 ; CHECK-NEXT:    br i1 [[CMP]], label [[T:%.*]], label [[F:%.*]]
 ; CHECK:       T:
-; CHECK-NEXT:    [[V:%.*]] = phi i8 [ [[X]], [[ENTRY:%.*]] ], [ 0, [[F]] ]
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[V]], 64
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 0
 ; CHECK:       F:
 ; CHECK-NEXT:    br i1 true, label [[T]], label [[F]]
 ;
 entry:
   %cmp = icmp slt i8 %x, -64
   br i1 %cmp, label %T, label %F
 T:
   %v = phi i8 [ %x, %entry], [0, %F]

 }
 
 define i8 @phi_sle_high_bits(i8 %x) {
 ; CHECK-LABEL: @phi_sle_high_bits(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[X:%.*]], -64
 ; CHECK-NEXT:    br i1 [[CMP]], label [[T:%.*]], label [[F:%.*]]
 ; CHECK:       T:
-; CHECK-NEXT:    [[V:%.*]] = phi i8 [ [[X]], [[ENTRY:%.*]] ], [ 0, [[F]] ]
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[V]], 64
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 0
 ; CHECK:       F:
 ; CHECK-NEXT:    br i1 true, label [[T]], label [[F]]
 ;
 entry:
   %cmp = icmp sle i8 %x, -65
   br i1 %cmp, label %T, label %F
 T:
   %v = phi i8 [ %x, %entry], [0, %F]