[ValueTracking] Use predicates for incoming phi-edges to deduce non-zero

[goldstein.w.n]

Summary

This is basically a copy and paste of the same logic we do in
computeKnownBits but adapts it for just isKnownNonZero.

[goldstein.w.n]

Rebase

[nikic]

LGTM

llvm/lib/Analysis/ValueTracking.cpp

2685

if (TrueSucc != FalseSucc) would be less confusing, I think?

llvm/test/Transforms/JumpThreading/phi-known.ll

1

Please pre-commit regenerating this test with UTC.

[goldstein.w.n]

llvm/lib/Analysis/ValueTracking.cpp

2685

This is cut/paste from the knownbits codes. Would rather just add NFC follow up to both of these two update to less confusing logic (and will do so unless you object).

[goldstein.w.n]

Rebase ontop of jump threading NFC

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

llvm/lib/Analysis/ValueTracking.cpp

case Instruction::PHI: {
 
     // Check if all incoming values are non-zero using recursion.
     SimplifyQuery RecQ = Q;
     unsigned NewDepth = std::max(Depth, MaxAnalysisRecursionDepth - 1);
     return llvm::all_of(PN->operands(), [&](const Use &U) {
       if (U.get() == PN)
         return true;
       RecQ.CxtI = PN->getIncomingBlock(U)->getTerminator();
+      // Check if the branch on the phi excludes zero.
+      ICmpInst::Predicate Pred;
+      Value *X;
+      BasicBlock *TrueSucc, *FalseSucc;
+      if (match(RecQ.CxtI,
+                m_Br(m_c_ICmp(Pred, m_Specific(U.get()), m_Value(X)),
+                     m_BasicBlock(TrueSucc), m_BasicBlock(FalseSucc)))) {
+        // Check for cases of duplicate successors.
+        if ((TrueSucc == PN->getParent()) != (FalseSucc == PN->getParent())) {
+          // If we're using the false successor, invert the predicate.
+          if (FalseSucc == PN->getParent())
+            Pred = CmpInst::getInversePredicate(Pred);
+          if (cmpExcludesZero(Pred, X))
+            return true;
+        }
+      }
+      // Finally recurse on the edge and check it directly.
       return isKnownNonZero(U.get(), DemandedElts, NewDepth, RecQ);
     });
   }
   case Instruction::ExtractElement:
     if (const auto *EEI = dyn_cast<ExtractElementInst>(I)) {
       const Value *Vec = EEI->getVectorOperand();
       const Value *Idx = EEI->getIndexOperand();
       auto *CIdx = dyn_cast<ConstantInt>(Idx);

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=instsimplify < %s -S | FileCheck %s
 
 define i1 @phi_ugt_non_zero(i8 %x) {
 ; CHECK-LABEL: @phi_ugt_non_zero(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i8 [[X:%.*]], 32
 ; CHECK-NEXT:    br i1 [[CMP]], label [[T:%.*]], label [[F:%.*]]
 ; CHECK:       T:
-; CHECK-NEXT:    [[V:%.*]] = phi i8 [ [[X]], [[ENTRY:%.*]] ], [ -1, [[F]] ]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[V]], 0
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       F:
 ; CHECK-NEXT:    br i1 true, label [[T]], label [[F]]
 ;
 entry:
   %cmp = icmp ugt i8 %x, 32
   br i1 %cmp, label %T, label %F
 T:
   %v = phi i8 [ %x, %entry], [-1, %F]
   %r = icmp eq i8 %v, 0
   ret i1 %r
 F:
   br i1 true, label %T, label %F
 }
 
 define i1 @phi_ugeh_non_zero(i8 %x) {
 ; CHECK-LABEL: @phi_ugeh_non_zero(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp uge i8 [[X:%.*]], 32
 ; CHECK-NEXT:    br i1 [[CMP]], label [[T:%.*]], label [[F:%.*]]
 ; CHECK:       T:
-; CHECK-NEXT:    [[V:%.*]] = phi i8 [ [[X]], [[ENTRY:%.*]] ], [ -1, [[F]] ]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[V]], 0
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       F:
 ; CHECK-NEXT:    br i1 true, label [[T]], label [[F]]
 ;
 entry:
   %cmp = icmp uge i8 %x, 32
   br i1 %cmp, label %T, label %F
 T:
   %v = phi i8 [ %x, %entry], [-1, %F]

 define i1 @phi_ult_non_zero(i8 %x) {
 ; CHECK-LABEL: @phi_ult_non_zero(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[X:%.*]], 123
 ; CHECK-NEXT:    br i1 [[CMP]], label [[T:%.*]], label [[F:%.*]]
 ; CHECK:       T:
 ; CHECK-NEXT:    br i1 true, label [[F]], label [[T]]
 ; CHECK:       F:
-; CHECK-NEXT:    [[V:%.*]] = phi i8 [ [[X]], [[ENTRY:%.*]] ], [ -1, [[T]] ]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[V]], 0
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %cmp = icmp ult i8 %x, 123
   br i1 %cmp, label %T, label %F
 T:
   br i1 true, label %F, label %T
 F:
   %v = phi i8 [ %x, %entry], [-1, %T]
   %r = icmp eq i8 %v, 0
   ret i1 %r
 }
 
 define i1 @phi_ule_non_zero(i8 %x) {
 ; CHECK-LABEL: @phi_ule_non_zero(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i8 [[X:%.*]], 123
 ; CHECK-NEXT:    br i1 [[CMP]], label [[T:%.*]], label [[F:%.*]]
 ; CHECK:       T:
 ; CHECK-NEXT:    br i1 true, label [[F]], label [[T]]
 ; CHECK:       F:
-; CHECK-NEXT:    [[V:%.*]] = phi i8 [ [[X]], [[ENTRY:%.*]] ], [ -1, [[T]] ]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[V]], 0
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %cmp = icmp ule i8 %x, 123
   br i1 %cmp, label %T, label %F
 T:
   br i1 true, label %F, label %T
 F:
   %v = phi i8 [ %x, %entry], [-1, %T]

 }
 
 define i1 @phi_ne_non_zero(i8 %x) {
 ; CHECK-LABEL: @phi_ne_non_zero(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne 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:%.*]] = icmp eq i8 [[V]], 0
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       F:
 ; CHECK-NEXT:    br i1 true, label [[T]], label [[F]]
 ;
 entry:
   %cmp = icmp ne i8 %x, 0
   br i1 %cmp, label %T, label %F
 T:
   %v = phi i8 [ %x, %entry], [-1, %F]
   %r = icmp eq i8 %v, 0
   ret i1 %r
 F:
   br i1 true, label %T, label %F
 }
 
 define i1 @phi_eq_non_zero(i8 %x) {
 ; CHECK-LABEL: @phi_eq_non_zero(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[X:%.*]], 44
 ; CHECK-NEXT:    br i1 [[CMP]], label [[T:%.*]], label [[F:%.*]]
 ; CHECK:       T:
-; CHECK-NEXT:    [[V:%.*]] = phi i8 [ [[X]], [[ENTRY:%.*]] ], [ -1, [[F]] ]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[V]], 0
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       F:
 ; CHECK-NEXT:    br i1 true, label [[T]], label [[F]]
 ;
 entry:
   %cmp = icmp eq i8 %x, 44
   br i1 %cmp, label %T, label %F
 T:
   %v = phi i8 [ %x, %entry], [-1, %F]
   %r = icmp eq i8 %v, 0
   ret i1 %r
 F:
   br i1 true, label %T, label %F
 }
 
 define i1 @phi_eq_non_zero2(i8 %x) {
 ; CHECK-LABEL: @phi_eq_non_zero2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[X:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[T:%.*]], label [[F:%.*]]
 ; CHECK:       T:
 ; CHECK-NEXT:    br i1 true, label [[F]], label [[T]]
 ; CHECK:       F:
-; CHECK-NEXT:    [[V:%.*]] = phi i8 [ [[X]], [[ENTRY:%.*]] ], [ -1, [[T]] ]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[V]], 0
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %cmp = icmp eq i8 %x, 0
   br i1 %cmp, label %T, label %F
 T:
   br i1 true, label %F, label %T
 F:
   %v = phi i8 [ %x, %entry], [-1, %T]
   %r = icmp eq i8 %v, 0
   ret i1 %r
 }

llvm/test/Transforms/FunctionAttrs/nonnull.ll

;
   %b = getelementptr inbounds i8, ptr %a, i64 %n
   ret ptr %b
 }
 
 ; TEST 11
 ; char* test11(char *p) {
 ;   return p? p: nonnull();
 ; }
-; FIXME: missing nonnull
 define ptr @test11(ptr) local_unnamed_addr {
-; FNATTRS-LABEL: define ptr @test11
+; FNATTRS-LABEL: define nonnull ptr @test11
 ; FNATTRS-SAME: (ptr readnone [[TMP0:%.*]]) local_unnamed_addr {
 ; FNATTRS-NEXT:    [[TMP2:%.*]] = icmp eq ptr [[TMP0]], null
 ; FNATTRS-NEXT:    br i1 [[TMP2]], label [[TMP3:%.*]], label [[TMP5:%.*]]
 ; FNATTRS:       3:
 ; FNATTRS-NEXT:    [[TMP4:%.*]] = tail call ptr @ret_nonnull()
 ; FNATTRS-NEXT:    br label [[TMP5]]
 ; FNATTRS:       5:
 ; FNATTRS-NEXT:    [[TMP6:%.*]] = phi ptr [ [[TMP4]], [[TMP3]] ], [ [[TMP0]], [[TMP1:%.*]] ]
 ; FNATTRS-NEXT:    ret ptr [[TMP6]]
 ;
-; ATTRIBUTOR-LABEL: define ptr @test11
+; ATTRIBUTOR-LABEL: define nonnull ptr @test11
 ; ATTRIBUTOR-SAME: (ptr [[TMP0:%.*]]) local_unnamed_addr {
 ; ATTRIBUTOR-NEXT:    [[TMP2:%.*]] = icmp eq ptr [[TMP0]], null
 ; ATTRIBUTOR-NEXT:    br i1 [[TMP2]], label [[TMP3:%.*]], label [[TMP5:%.*]]
 ; ATTRIBUTOR:       3:
 ; ATTRIBUTOR-NEXT:    [[TMP4:%.*]] = tail call ptr @ret_nonnull()
 ; ATTRIBUTOR-NEXT:    br label [[TMP5]]
 ; ATTRIBUTOR:       5:
 ; ATTRIBUTOR-NEXT:    [[TMP6:%.*]] = phi ptr [ [[TMP4]], [[TMP3]] ], [ [[TMP0]], [[TMP1:%.*]] ]

llvm/test/Transforms/JumpThreading/phi-known.ll

 ; RUN: opt -S -passes=jump-threading %s | FileCheck %s
 
 ; Value of predicate known on all inputs (trivial case)
 ; Note: InstCombine/EarlyCSE would also get this case
 define void @test(ptr %p, ptr %addr) {
 ; CHECK-LABEL: @test
 entry:
   %cmp0 = icmp eq ptr %p, null
   br i1 %cmp0, label %exit, label %loop

 exit:
   ret void
 }
 
 ; If the inputs don't branch the same way, we can't rewrite
 ; Well, we could unroll this loop exactly twice, but that's
 ; a different transform.
 define void @test_mixed(ptr %p) {
-; CHECK-LABEL: @test_mixed
+; CHECK-LABEL: define void @test_mixed
+; CHECK-SAME: (ptr [[P:%.*]]) {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP0:%.*]] = icmp eq ptr [[P]], null
+; CHECK-NEXT:    br i1 [[CMP0]], label [[EXIT:%.*]], label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
 entry:
   %cmp0 = icmp eq ptr %p, null
   br i1 %cmp0, label %exit, label %loop
 loop:
-; CHECK-LABEL: loop:
-; CHECK-NEXT: phi
-; CHECK-NEXT: %cmp1 = icmp
-; CHECK-NEXT: br i1 %cmp1
   %p1 = phi ptr [%p, %entry], [%p1, %loop]
   %cmp1 = icmp ne ptr %p1, null
   br i1 %cmp1, label %exit, label %loop
 exit:
   ret void
 }
 
 ; The eq predicate is always true if we go through the path from