[ValueTracking] Strengthen analysis in `computeKnownBits` of phi

[goldstein.w.n]

Summary

Use the comparison based analysis to strengthen the standard
knownbits analysis rather than choosing either/or.

[nikic]

This has substantial compile-time impact: https://llvm-compile-time-tracker.com/compare.php?from=9e515bce8a9a342ab29a8e0d3011e4985e4ec67e&to=3ea691cbae271f81cfb4ef4e3e8c6180c43d96d9&stat=instructions:u How to support computeKnownBits across phis is an open problem, but I don't think this is the solution.

[goldstein.w.n]

Remove extra depth

[goldstein.w.n]

In D157807#4582870, @nikic wrote:

This has substantial compile-time impact: https://llvm-compile-time-tracker.com/compare.php?from=9e515bce8a9a342ab29a8e0d3011e4985e4ec67e&to=3ea691cbae271f81cfb4ef4e3e8c6180c43d96d9&stat=instructions:u How to support computeKnownBits across phis is an open problem, but I don't think this is the solution.

Yeah :( dropped the depth changed + replaced with NFC. Tried a few variants that where more conservative but they also have big impact.

[nikic]

There are test failures.

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

1469

limiter?

[goldstein.w.n]

In D157807#4584209, @nikic wrote:

There are test failures.

Bah sorry, test didn't autogen.

[goldstein.w.n]

Fixup tests

[nikic]

LGTM

[goldstein.w.n]

Update missing test

llvm/lib/Analysis/ValueTracking.cpp

case Instruction::PHI: {
     // taking conservative care to avoid excessive recursion.
     if (Depth < MaxAnalysisRecursionDepth - 1 && Known.isUnknown()) {
       // Skip if every incoming value references to ourself.
       if (isa_and_nonnull<UndefValue>(P->hasConstantValue()))
         break;
 
       Known.Zero.setAllBits();
       Known.One.setAllBits();
+      // Don't blindly recurse on Depth as there can be alot of incoming edges
+      // (increasing compile time). Instead set minimum depth as the number of
+      // incoming edges. Make sure we do at least one level.
+      unsigned InLoopRecurseDepth =
+          std::min(MaxAnalysisRecursionDepth - 1,
+                   std::max(Depth + 1, P->getNumIncomingValues()));
+      //      InLoopRecurseDepth = MaxAnalysisRecursionDepth - 1;
       for (unsigned u = 0, e = P->getNumIncomingValues(); u < e; ++u) {
         Value *IncValue = P->getIncomingValue(u);
         // Skip direct self references.
-        if (IncValue == P) continue;
+        if (IncValue == P)
+          continue;
 
         // Change the context instruction to the "edge" that flows into the
         // phi. This is important because that is where the value is actually
         // "evaluated" even though it is used later somewhere else. (see also
         // D69571).
         SimplifyQuery RecQ = Q;
         RecQ.CxtI = P->getIncomingBlock(u)->getTerminator();
 
         Known2 = KnownBits(BitWidth);
 
-        // Recurse, but cap the recursion to one level, because we don't
-        // want to waste time spinning around in loops.
-        computeKnownBits(IncValue, Known2, MaxAnalysisRecursionDepth - 1, RecQ);
+        computeKnownBits(IncValue, Known2, InLoopRecurseDepth, RecQ);
 
-        // If this failed, see if we can use a conditional branch into the phi
+        // See if we can further use a conditional branch into the phi
         // to help us determine the range of the value.
-        if (Known2.isUnknown()) {
+        if (!Known2.isConstant()) {
           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);
               // Get the knownbits implied by the incoming phi condition.
               auto CR = ConstantRange::makeExactICmpRegion(Pred, *RHSC);
-              Known2 = CR.toKnownBits();
+              Known2 = Known2.unionWith(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/ScalarEvolution/outer_phi.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
 ; RUN: opt < %s -S -disable-output "-passes=print<scalar-evolution>" 2>&1 | FileCheck %s
 
 declare i1 @cond()
 
 define i32 @test_01(i32 %a, i32 %b) {
 ; CHECK-LABEL: 'test_01'
 ; CHECK-NEXT:  Classifying expressions for: @test_01
 ; CHECK-NEXT:    %outer.iv = phi i32 [ 0, %entry ], [ %iv.next, %outer.backedge ]
-; CHECK-NEXT:    --> %outer.iv U: [0,-2147483647) S: [0,-2147483647) Exits: <<Unknown>> LoopDispositions: { %outer: Variant, %inner: Invariant }
+; CHECK-NEXT:    --> %outer.iv U: [0,-2147483648) S: [0,-2147483648) Exits: <<Unknown>> LoopDispositions: { %outer: Variant, %inner: Invariant }
 ; CHECK-NEXT:    %iv = phi i32 [ 0, %outer ], [ %iv.next, %inner.backedge ]
 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%inner> U: [0,-2147483648) S: [0,-2147483648) Exits: <<Unknown>> LoopDispositions: { %inner: Computable, %outer: Variant }
 ; CHECK-NEXT:    %iv.next = add nuw nsw i32 %iv, 1
 ; CHECK-NEXT:    --> {1,+,1}<nuw><%inner> U: [1,-2147483647) S: [1,-2147483647) Exits: <<Unknown>> LoopDispositions: { %inner: Computable, %outer: Variant }
 ; CHECK-NEXT:    %inner.loop.cond = call i1 @cond()
 ; CHECK-NEXT:    --> %inner.loop.cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %inner: Variant, %outer: Variant }
 ; CHECK-NEXT:    %outer.loop.cond = call i1 @cond()
 ; CHECK-NEXT:    --> %outer.loop.cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %outer: Variant, %inner: Invariant }

llvm/test/Transforms/InstCombine/catchswitch-phi.ll

 ; CHECK:       rethrow:
 ; CHECK-NEXT:    invoke void @llvm.wasm.rethrow() #[[ATTR0:[0-9]+]] [ "funclet"(token [[TMP1]]) ]
 ; CHECK-NEXT:    to label [[UNREACHABLE:%.*]] unwind label [[CATCH_DISPATCH1]]
 ; CHECK:       catch.dispatch1:
 ; CHECK-NEXT:    [[AP_2:%.*]] = phi i8 [ [[AP_1]], [[CATCH_DISPATCH]] ], [ [[AP_1]], [[RETHROW]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[TMP2:%.*]] = catchswitch within none [label %catch.start1] unwind to caller
 ; CHECK:       catch.start1:
 ; CHECK-NEXT:    [[TMP3:%.*]] = catchpad within [[TMP2]] [ptr null]
-; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[AP_2]], 1
-; CHECK-NEXT:    [[TOBOOL1_NOT:%.*]] = icmp eq i8 [[TMP0]], 0
+; CHECK-NEXT:    [[TOBOOL1_NOT:%.*]] = icmp eq i8 [[AP_2]], 0
 ; CHECK-NEXT:    br i1 [[TOBOOL1_NOT]], label [[IF_END1:%.*]], label [[IF_THEN1:%.*]]
 ; CHECK:       if.then1:
 ; CHECK-NEXT:    br label [[IF_END1]]
 ; CHECK:       if.end1:
 ; CHECK-NEXT:    catchret from [[TMP3]] to label [[TRY_CONT]]
 ; CHECK:       try.cont:
 ; CHECK-NEXT:    ret void
 ; CHECK:       unreachable:

llvm/test/Transforms/InstCombine/known-phi-recurse.ll

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[Y:%.*]] = call i64 @llvm.ctpop.i64(i64 [[X:%.*]]), !range [[RNG0]]
 ; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i64 [[Y]] to i32
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[END:%.*]], label [[BODY:%.*]]
 ; CHECK:       body:
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
 ; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[TRUNC]], [[ENTRY:%.*]] ], [ 255, [[BODY]] ]
-; CHECK-NEXT:    [[RES:%.*]] = and i32 [[PHI]], 255
-; CHECK-NEXT:    ret i32 [[RES]]
+; CHECK-NEXT:    ret i32 [[PHI]]
 ;
 entry:
   %y = call i64 @llvm.ctpop.i64(i64 %x)
   %trunc = trunc i64 %y to i32
   br i1 %c, label %end, label %body
 body:
   br label %end
 end:

 ; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i64 [[Y]] to i32
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[END:%.*]], label [[BODY:%.*]]
 ; CHECK:       body:
 ; CHECK-NEXT:    [[Y2:%.*]] = call i64 @llvm.ctpop.i64(i64 [[X2:%.*]]), !range [[RNG0]]
 ; CHECK-NEXT:    [[TRUNC2:%.*]] = trunc i64 [[Y2]] to i32
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
 ; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[TRUNC]], [[ENTRY:%.*]] ], [ [[TRUNC2]], [[BODY]] ]
-; CHECK-NEXT:    [[RES:%.*]] = and i32 [[PHI]], 255
-; CHECK-NEXT:    ret i32 [[RES]]
+; CHECK-NEXT:    ret i32 [[PHI]]
 ;
 entry:
   %y = call i64 @llvm.ctpop.i64(i64 %x)
   %trunc = trunc i64 %y to i32
   br i1 %c, label %end, label %body
 body:
   %y2 = call i64 @llvm.ctpop.i64(i64 %x2)
   %trunc2 = trunc i64 %y2 to i32

llvm/test/Transforms/LoopUnroll/AArch64/runtime-unroll-generic.ll

 ; CHECK-A55-NEXT:    [[MUL16_EPIL:%.*]] = mul nsw i32 [[CONV15_EPIL]], [[CONV_EPIL]]
 ; CHECK-A55-NEXT:    [[ARRAYIDX20_EPIL:%.*]] = getelementptr inbounds i32, ptr [[ARG_1]], i64 [[IDX_EXT_EPIL]]
 ; CHECK-A55-NEXT:    [[TMP15:%.*]] = load i32, ptr [[ARRAYIDX20_EPIL]], align 4
 ; CHECK-A55-NEXT:    [[ADD21_EPIL:%.*]] = add nsw i32 [[MUL16_EPIL]], [[TMP15]]
 ; CHECK-A55-NEXT:    store i32 [[ADD21_EPIL]], ptr [[ARRAYIDX20_EPIL]], align 4
 ; CHECK-A55-NEXT:    [[EPIL_ITER_CMP_NOT:%.*]] = icmp eq i32 [[XTRAITER]], 1
 ; CHECK-A55-NEXT:    br i1 [[EPIL_ITER_CMP_NOT]], label [[FOR_END]], label [[FOR_BODY6_EPIL_1:%.*]]
 ; CHECK-A55:       for.body6.epil.1:
-; CHECK-A55-NEXT:    [[INC_EPIL:%.*]] = add nuw i32 [[K_03_UNR]], 1
+; CHECK-A55-NEXT:    [[INC_EPIL:%.*]] = or i32 [[K_03_UNR]], 1
 ; CHECK-A55-NEXT:    [[IDX_EXT_EPIL_1:%.*]] = zext i32 [[INC_EPIL]] to i64
 ; CHECK-A55-NEXT:    [[ARRAYIDX10_EPIL_1:%.*]] = getelementptr inbounds i16, ptr [[ARG_2]], i64 [[IDX_EXT_EPIL_1]]
 ; CHECK-A55-NEXT:    [[TMP16:%.*]] = load i16, ptr [[ARRAYIDX10_EPIL_1]], align 2
 ; CHECK-A55-NEXT:    [[CONV_EPIL_1:%.*]] = sext i16 [[TMP16]] to i32
 ; CHECK-A55-NEXT:    [[ARRAYIDX14_EPIL_1:%.*]] = getelementptr inbounds i16, ptr [[ARG_3]], i64 [[IDX_EXT_EPIL_1]]
 ; CHECK-A55-NEXT:    [[TMP17:%.*]] = load i16, ptr [[ARRAYIDX14_EPIL_1]], align 2
 ; CHECK-A55-NEXT:    [[CONV15_EPIL_1:%.*]] = sext i16 [[TMP17]] to i32
 ; CHECK-A55-NEXT:    [[MUL16_EPIL_1:%.*]] = mul nsw i32 [[CONV15_EPIL_1]], [[CONV_EPIL_1]]
 ; CHECK-A55-NEXT:    [[ARRAYIDX20_EPIL_1:%.*]] = getelementptr inbounds i32, ptr [[ARG_1]], i64 [[IDX_EXT_EPIL_1]]
 ; CHECK-A55-NEXT:    [[TMP18:%.*]] = load i32, ptr [[ARRAYIDX20_EPIL_1]], align 4
 ; CHECK-A55-NEXT:    [[ADD21_EPIL_1:%.*]] = add nsw i32 [[MUL16_EPIL_1]], [[TMP18]]
 ; CHECK-A55-NEXT:    store i32 [[ADD21_EPIL_1]], ptr [[ARRAYIDX20_EPIL_1]], align 4
 ; CHECK-A55-NEXT:    [[EPIL_ITER_CMP_1_NOT:%.*]] = icmp eq i32 [[XTRAITER]], 2
 ; CHECK-A55-NEXT:    br i1 [[EPIL_ITER_CMP_1_NOT]], label [[FOR_END]], label [[FOR_BODY6_EPIL_2:%.*]]
 ; CHECK-A55:       for.body6.epil.2:
-; CHECK-A55-NEXT:    [[INC_EPIL_1:%.*]] = add nuw i32 [[K_03_UNR]], 2
+; CHECK-A55-NEXT:    [[INC_EPIL_1:%.*]] = or i32 [[K_03_UNR]], 2
 ; CHECK-A55-NEXT:    [[IDX_EXT_EPIL_2:%.*]] = zext i32 [[INC_EPIL_1]] to i64
 ; CHECK-A55-NEXT:    [[ARRAYIDX10_EPIL_2:%.*]] = getelementptr inbounds i16, ptr [[ARG_2]], i64 [[IDX_EXT_EPIL_2]]
 ; CHECK-A55-NEXT:    [[TMP19:%.*]] = load i16, ptr [[ARRAYIDX10_EPIL_2]], align 2
 ; CHECK-A55-NEXT:    [[CONV_EPIL_2:%.*]] = sext i16 [[TMP19]] to i32
 ; CHECK-A55-NEXT:    [[ARRAYIDX14_EPIL_2:%.*]] = getelementptr inbounds i16, ptr [[ARG_3]], i64 [[IDX_EXT_EPIL_2]]
 ; CHECK-A55-NEXT:    [[TMP20:%.*]] = load i16, ptr [[ARRAYIDX14_EPIL_2]], align 2
 ; CHECK-A55-NEXT:    [[CONV15_EPIL_2:%.*]] = sext i16 [[TMP20]] to i32
 ; CHECK-A55-NEXT:    [[MUL16_EPIL_2:%.*]] = mul nsw i32 [[CONV15_EPIL_2]], [[CONV_EPIL_2]]

llvm/test/Transforms/LoopUnroll/runtime-unroll-remainder.ll

 ; CHECK-NEXT:    [[TMP1:%.*]] = load i32, ptr [[ARRAYIDX_EPIL]], align 4
 ; CHECK-NEXT:    [[ARRAYIDX2_EPIL:%.*]] = getelementptr inbounds i32, ptr [[B:%.*]], i64 [[INDVARS_IV_UNR]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = load i32, ptr [[ARRAYIDX2_EPIL]], align 4
 ; CHECK-NEXT:    [[MUL_EPIL:%.*]] = mul nsw i32 [[TMP2]], [[TMP1]]
 ; CHECK-NEXT:    [[ADD_EPIL:%.*]] = add nsw i32 [[MUL_EPIL]], [[C_010_UNR]]
 ; CHECK-NEXT:    [[EPIL_ITER_CMP_NOT:%.*]] = icmp eq i64 [[XTRAITER]], 1
 ; CHECK-NEXT:    br i1 [[EPIL_ITER_CMP_NOT]], label [[FOR_COND_CLEANUP_LOOPEXIT_EPILOG_LCSSA:%.*]], label [[FOR_BODY_EPIL_1:%.*]]
 ; CHECK:       for.body.epil.1:
-; CHECK-NEXT:    [[INDVARS_IV_NEXT_EPIL:%.*]] = add nuw nsw i64 [[INDVARS_IV_UNR]], 1
+; CHECK-NEXT:    [[INDVARS_IV_NEXT_EPIL:%.*]] = or i64 [[INDVARS_IV_UNR]], 1
 ; CHECK-NEXT:    [[ARRAYIDX_EPIL_1:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[INDVARS_IV_NEXT_EPIL]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = load i32, ptr [[ARRAYIDX_EPIL_1]], align 4
 ; CHECK-NEXT:    [[ARRAYIDX2_EPIL_1:%.*]] = getelementptr inbounds i32, ptr [[B]], i64 [[INDVARS_IV_NEXT_EPIL]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = load i32, ptr [[ARRAYIDX2_EPIL_1]], align 4
 ; CHECK-NEXT:    [[MUL_EPIL_1:%.*]] = mul nsw i32 [[TMP4]], [[TMP3]]
 ; CHECK-NEXT:    [[ADD_EPIL_1:%.*]] = add nsw i32 [[MUL_EPIL_1]], [[ADD_EPIL]]
 ; CHECK-NEXT:    [[EPIL_ITER_CMP_1_NOT:%.*]] = icmp eq i64 [[XTRAITER]], 2
 ; CHECK-NEXT:    br i1 [[EPIL_ITER_CMP_1_NOT]], label [[FOR_COND_CLEANUP_LOOPEXIT_EPILOG_LCSSA]], label [[FOR_BODY_EPIL_2:%.*]]
 ; CHECK:       for.body.epil.2:
-; CHECK-NEXT:    [[INDVARS_IV_NEXT_EPIL_1:%.*]] = add nuw nsw i64 [[INDVARS_IV_UNR]], 2
+; CHECK-NEXT:    [[INDVARS_IV_NEXT_EPIL_1:%.*]] = or i64 [[INDVARS_IV_UNR]], 2
 ; CHECK-NEXT:    [[ARRAYIDX_EPIL_2:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[INDVARS_IV_NEXT_EPIL_1]]
 ; CHECK-NEXT:    [[TMP5:%.*]] = load i32, ptr [[ARRAYIDX_EPIL_2]], align 4
 ; CHECK-NEXT:    [[ARRAYIDX2_EPIL_2:%.*]] = getelementptr inbounds i32, ptr [[B]], i64 [[INDVARS_IV_NEXT_EPIL_1]]
 ; CHECK-NEXT:    [[TMP6:%.*]] = load i32, ptr [[ARRAYIDX2_EPIL_2]], align 4
 ; CHECK-NEXT:    [[MUL_EPIL_2:%.*]] = mul nsw i32 [[TMP6]], [[TMP5]]
 ; CHECK-NEXT:    [[ADD_EPIL_2:%.*]] = add nsw i32 [[MUL_EPIL_2]], [[ADD_EPIL_1]]
 ; CHECK-NEXT:    br label [[FOR_COND_CLEANUP_LOOPEXIT_EPILOG_LCSSA]]
 ; CHECK:       for.cond.cleanup.loopexit.epilog-lcssa:

llvm/test/Transforms/PhaseOrdering/X86/pr38280.ll

 ; CHECK-NEXT:    [[ADD_PTR2]] = getelementptr inbounds i8, ptr [[SRC_ADDR_023]], i64 8
 ; CHECK-NEXT:    [[SUB]] = add i64 [[COUNT_ADDR_022]], -8
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i64 [[SUB]], 7
 ; CHECK-NEXT:    br i1 [[CMP]], label [[WHILE_BODY]], label [[WHILE_COND3_PREHEADER]]
 ; CHECK:       while.body4:
 ; CHECK-NEXT:    [[DST_ADDR_130:%.*]] = phi ptr [ [[INCDEC_PTR:%.*]], [[WHILE_BODY4]] ], [ [[DST_ADDR_0_LCSSA]], [[WHILE_COND3_PREHEADER]] ]
 ; CHECK-NEXT:    [[SRC_ADDR_129:%.*]] = phi ptr [ [[INCDEC_PTR8:%.*]], [[WHILE_BODY4]] ], [ [[SRC_ADDR_0_LCSSA]], [[WHILE_COND3_PREHEADER]] ]
 ; CHECK-NEXT:    [[COUNT_ADDR_128:%.*]] = phi i64 [ [[DEC:%.*]], [[WHILE_BODY4]] ], [ [[COUNT_ADDR_0_LCSSA]], [[WHILE_COND3_PREHEADER]] ]
-; CHECK-NEXT:    [[DEC]] = add i64 [[COUNT_ADDR_128]], -1
+; CHECK-NEXT:    [[DEC]] = add nsw i64 [[COUNT_ADDR_128]], -1
 ; CHECK-NEXT:    [[TMP2:%.*]] = load i8, ptr [[SRC_ADDR_129]], align 1
 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i8, ptr [[DST_ADDR_130]], i64 [[NEG_OFFS]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = load i8, ptr [[ARRAYIDX]], align 1
 ; CHECK-NEXT:    [[ADD6:%.*]] = add i8 [[TMP3]], [[TMP2]]
 ; CHECK-NEXT:    store i8 [[ADD6]], ptr [[DST_ADDR_130]], align 1
 ; CHECK-NEXT:    [[INCDEC_PTR]] = getelementptr inbounds i8, ptr [[DST_ADDR_130]], i64 1
 ; CHECK-NEXT:    [[INCDEC_PTR8]] = getelementptr inbounds i8, ptr [[SRC_ADDR_129]], i64 1
 ; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[DEC]], 0
-; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[WHILE_END9]], label [[WHILE_BODY4]], !llvm.loop [[LOOP0:![0-9]+]]
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[WHILE_END9]], label [[WHILE_BODY4]]
 ; CHECK:       while.end9:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %cmp21 = icmp ugt i64 %count, 7
   br i1 %cmp21, label %while.body.preheader, label %while.cond3.preheader
 
 while.body.preheader: