[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

1478–1479

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

[goldstein.w.n]

llvm/lib/Analysis/ValueTracking.cpp

1478–1479

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);
-
-              switch (Pred) {
-              case CmpInst::Predicate::ICMP_EQ:
-                Known2 = KnownBits::makeConstant(*RHSC);
-                break;
-              case CmpInst::Predicate::ICMP_ULE:
-                Known2.Zero.setHighBits(RHSC->countl_zero());
-                break;
-              case CmpInst::Predicate::ICMP_ULT:
-                Known2.Zero.setHighBits((*RHSC - 1).countl_zero());
-                break;
-              default:
-                // TODO - add additional integer predicate handling.
-                break;
-              }
+              // Get the knownbits implied by the incoming phi condition.
+              auto CR = ConstantRange::makeExactICmpRegion(Pred, *RHSC);
+              Known2 = CR.toKnownBits();
             }
           }
         }
 
         Known = Known.intersectWith(Known2);
         // If all bits have been ruled out, there's no need to check
         // more operands.
         if (Known.isUnknown())

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 label [[T]]
 ;
 entry:
   %cmp = icmp ugt i8 %x, 191
   br i1 %cmp, label %T, label %F
 T:
   %v = phi i8 [ %x, %entry], [-1, %F]
   %r = and i8 %v, 64
   ret i8 %r
 F:
   br label %T
 }
 
 define i8 @phi_ult_low_bits(i8 %x) {
 ; CHECK-LABEL: @phi_ult_low_bits(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[X:%.*]], -64
 ; CHECK-NEXT:    br i1 [[CMP]], label [[T:%.*]], label [[F:%.*]]
 ; CHECK:       T:
 ; CHECK-NEXT:    br label [[F]]
 ; CHECK:       F:
-; CHECK-NEXT:    [[V:%.*]] = phi i8 [ [[X]], [[ENTRY:%.*]] ], [ -1, [[T]] ]
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[V]], 64
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 64
 ;
 entry:
   %cmp = icmp ult i8 %x, 192
   br i1 %cmp, label %T, label %F
 T:
   br label %F
 F:
   %v = phi i8 [ %x, %entry], [-1, %T]

 }
 
 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 label [[T]]
 ;
 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 label [[T]]
 ;
 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 label [[T]]
 ;
 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 label %T
 }
 
 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 label [[T]]
 ;
 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 label [[T]]
 ;
 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 label %T
 }
 
 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 label [[T]]
 ;
 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 label [[T]]
 ;
 entry:
   %cmp = icmp sle i8 %x, -65
   br i1 %cmp, label %T, label %F
 T:
   %v = phi i8 [ %x, %entry], [0, %F]
   %r = and i8 %v, 64
   ret i8 %r
 F:
   br label %T
 }
 
 define i8 @phi_sle_low_bits(i8 %x) {
 ; CHECK-LABEL: @phi_sle_low_bits(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[X:%.*]], 65
 ; CHECK-NEXT:    br i1 [[CMP]], label [[T:%.*]], label [[F:%.*]]
 ; CHECK:       T:
 ; CHECK-NEXT:    br label [[F]]
 ; CHECK:       F:
-; CHECK-NEXT:    [[V:%.*]] = phi i8 [ [[X]], [[ENTRY:%.*]] ], [ -1, [[T]] ]
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[V]], 64
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 64
 ;
 entry:
   %cmp = icmp sle i8 %x, 64
   br i1 %cmp, label %T, label %F
 T:
   br label %F
 F:
   %v = phi i8 [ %x, %entry], [-1, %T]