[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

1463

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

if (Depth < MaxAnalysisRecursionDepth - 1 && Known.isUnknown()) {
         // 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.
+        // TODO: See if we can base recursion limiter on number of incoming phi
+        // edges so we don't overly clamp analysis.
         computeKnownBits(IncValue, Known2, MaxAnalysisRecursionDepth - 1, 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/ValueTracking/phi-known-bits.ll

T:
   ret i8 %r
 F:
   br label %T
 }
 
 define i8 @phi_ugt_high_bits_and_known(i8 %xx) {
 ; CHECK-LABEL: @phi_ugt_high_bits_and_known(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[X:%.*]] = or i8 [[XX:%.*]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i8 [[X]], -65
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i8 [[XX:%.*]], -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]], 65
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 65
 ; CHECK:       F:
 ; CHECK-NEXT:    br label [[T]]
 ;
 entry:
   %x = or i8 %xx, 1
   %cmp = icmp ugt i8 %x, 191
   br i1 %cmp, label %T, label %F
 T:

llvm/test/CodeGen/Thumb2/mve-blockplacement.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=thumbv8.1m.main-none-none-eabi -verify-machineinstrs -mattr=+mve %s -o - | FileCheck %s
 
 @var_36 = hidden local_unnamed_addr global i8 0, align 1
 @arr_61 = hidden local_unnamed_addr global [1 x i32] zeroinitializer, align 4
 
 define i32 @test(i8 zeroext %var_2, i16 signext %var_15, ptr %arr_60) {
 ; CHECK-LABEL: test:
 ; CHECK:       @ %bb.0: @ %entry
 ; CHECK-NEXT:    .save {r4, r5, r6, r7, r8, r9, r10, r11, lr}
 ; CHECK-NEXT:    push.w {r4, r5, r6, r7, r8, r9, r10, r11, lr}
+; CHECK-NEXT:    .pad #16
+; CHECK-NEXT:    sub sp, #16
 ; CHECK-NEXT:    cmp r0, #0
-; CHECK-NEXT:    beq.w .LBB0_10
+; CHECK-NEXT:    beq.w .LBB0_11
 ; CHECK-NEXT:  @ %bb.1: @ %for.cond1.preheader
 ; CHECK-NEXT:    cmp r2, #0
-; CHECK-NEXT:    beq.w .LBB0_11
+; CHECK-NEXT:    beq.w .LBB0_12
 ; CHECK-NEXT:  @ %bb.2: @ %for.cond1.preheader1
-; CHECK-NEXT:    movw r8, :lower16:var_36
+; CHECK-NEXT:    addw r0, r2, #441
+; CHECK-NEXT:    str r0, [sp, #8] @ 4-byte Spill
+; CHECK-NEXT:    addw r0, r2, #419
+; CHECK-NEXT:    str r0, [sp, #4] @ 4-byte Spill
+; CHECK-NEXT:    addw r0, r2, #397
+; CHECK-NEXT:    movw r5, :lower16:var_36
+; CHECK-NEXT:    str r0, [sp] @ 4-byte Spill
 ; CHECK-NEXT:    movw r0, #27476
-; CHECK-NEXT:    addw r10, r2, #397
-; CHECK-NEXT:    mov.w r9, #11
-; CHECK-NEXT:    movt r8, :upper16:var_36
+; CHECK-NEXT:    movt r5, :upper16:var_36
 ; CHECK-NEXT:    sdiv r1, r0, r1
-; CHECK-NEXT:    mov.w r11, #0
-; CHECK-NEXT:  .LBB0_3: @ %for.cond6.preheader
+; CHECK-NEXT:    str r2, [sp, #12] @ 4-byte Spill
+; CHECK-NEXT:  .LBB0_3: @ %for.cond1
 ; CHECK-NEXT:    @ =>This Loop Header: Depth=1
 ; CHECK-NEXT:    @ Child Loop BB0_4 Depth 2
-; CHECK-NEXT:    @ Child Loop BB0_6 Depth 2
-; CHECK-NEXT:    @ Child Loop BB0_8 Depth 2
-; CHECK-NEXT:    movs r0, #22
-; CHECK-NEXT:    dls lr, r9
-; CHECK-NEXT:    mla r7, r11, r0, r10
-; CHECK-NEXT:    movw r0, :lower16:arr_61
-; CHECK-NEXT:    movt r0, :upper16:arr_61
-; CHECK-NEXT:    adds r0, #4
-; CHECK-NEXT:    mov r3, r2
-; CHECK-NEXT:    mov r6, r0
-; CHECK-NEXT:  .LBB0_4: @ %for.body10
+; CHECK-NEXT:    @ Child Loop BB0_5 Depth 3
+; CHECK-NEXT:    @ Child Loop BB0_7 Depth 3
+; CHECK-NEXT:    @ Child Loop BB0_9 Depth 3
+; CHECK-NEXT:    ldr.w r12, [sp, #8] @ 4-byte Reload
+; CHECK-NEXT:    mov.w r10, #0
+; CHECK-NEXT:    ldrd r8, r0, [sp] @ 8-byte Folded Reload
+; CHECK-NEXT:  .LBB0_4: @ %for.cond6.preheader
 ; CHECK-NEXT:    @ Parent Loop BB0_3 Depth=1
-; CHECK-NEXT:    @ => This Inner Loop Header: Depth=2
-; CHECK-NEXT:    str r3, [r6, #-4]
-; CHECK-NEXT:    add.w r12, r3, #396
-; CHECK-NEXT:    ldrb r5, [r7, #-1]
-; CHECK-NEXT:    add.w r3, r3, #792
-; CHECK-NEXT:    cmp r5, #0
-; CHECK-NEXT:    ite ne
-; CHECK-NEXT:    sxthne r5, r1
-; CHECK-NEXT:    moveq r5, #0
-; CHECK-NEXT:    cmp r5, #0
-; CHECK-NEXT:    str.w r12, [r6]
-; CHECK-NEXT:    cset r5, ne
-; CHECK-NEXT:    adds r6, #8
-; CHECK-NEXT:    strb.w r5, [r8]
-; CHECK-NEXT:    ldrb r5, [r7]
-; CHECK-NEXT:    adds r7, #2
-; CHECK-NEXT:    cmp r5, #0
-; CHECK-NEXT:    ite ne
-; CHECK-NEXT:    sxthne r5, r1
-; CHECK-NEXT:    moveq r5, #0
-; CHECK-NEXT:    cmp r5, #0
-; CHECK-NEXT:    cset r5, ne
-; CHECK-NEXT:    strb.w r5, [r8]
-; CHECK-NEXT:    le lr, .LBB0_4
-; CHECK-NEXT:  @ %bb.5: @ %for.cond.cleanup9
-; CHECK-NEXT:    @ in Loop: Header=BB0_3 Depth=1
-; CHECK-NEXT:    add.w r3, r11, #1
-; CHECK-NEXT:    movs r7, #22
-; CHECK-NEXT:    dls lr, r9
-; CHECK-NEXT:    mov r6, r0
-; CHECK-NEXT:    uxtb r3, r3
-; CHECK-NEXT:    smlabb r7, r3, r7, r10
-; CHECK-NEXT:    mov r3, r2
-; CHECK-NEXT:  .LBB0_6: @ %for.body10.1
+; CHECK-NEXT:    @ => This Loop Header: Depth=2
+; CHECK-NEXT:    @ Child Loop BB0_5 Depth 3
+; CHECK-NEXT:    @ Child Loop BB0_7 Depth 3
+; CHECK-NEXT:    @ Child Loop BB0_9 Depth 3
+; CHECK-NEXT:    movw r3, :lower16:arr_61
+; CHECK-NEXT:    movt r3, :upper16:arr_61
+; CHECK-NEXT:    add.w r11, r3, #4
+; CHECK-NEXT:    movs r3, #11
+; CHECK-NEXT:    dls lr, r3
+; CHECK-NEXT:    mov r4, r11
+; CHECK-NEXT:    mov r3, r8
+; CHECK-NEXT:  .LBB0_5: @ %for.body10
 ; CHECK-NEXT:    @ Parent Loop BB0_3 Depth=1
-; CHECK-NEXT:    @ => This Inner Loop Header: Depth=2
-; CHECK-NEXT:    str r3, [r6, #-4]
-; CHECK-NEXT:    add.w r4, r3, #396
-; CHECK-NEXT:    ldrb r5, [r7, #-1]
-; CHECK-NEXT:    add.w r3, r3, #792
-; CHECK-NEXT:    cmp r5, #0
+; CHECK-NEXT:    @ Parent Loop BB0_4 Depth=2
+; CHECK-NEXT:    @ => This Inner Loop Header: Depth=3
+; CHECK-NEXT:    str r2, [r4, #-4]
+; CHECK-NEXT:    ldrb r6, [r3, #-1]
+; CHECK-NEXT:    cmp r6, #0
 ; CHECK-NEXT:    ite ne
-; CHECK-NEXT:    sxthne r5, r1
-; CHECK-NEXT:    moveq r5, #0
-; CHECK-NEXT:    cmp r5, #0
-; CHECK-NEXT:    str r4, [r6]
-; CHECK-NEXT:    cset r5, ne
-; CHECK-NEXT:    adds r6, #8
-; CHECK-NEXT:    strb.w r5, [r8]
-; CHECK-NEXT:    ldrb r5, [r7]
-; CHECK-NEXT:    adds r7, #2
-; CHECK-NEXT:    cmp r5, #0
+; CHECK-NEXT:    sxthne.w r9, r1
+; CHECK-NEXT:    moveq.w r9, #0
+; CHECK-NEXT:    add.w r6, r2, #396
+; CHECK-NEXT:    cmp.w r9, #0
+; CHECK-NEXT:    str r6, [r4]
+; CHECK-NEXT:    cset r6, ne
+; CHECK-NEXT:    strb r6, [r5]
+; CHECK-NEXT:    add.w r2, r2, #792
+; CHECK-NEXT:    ldrb r6, [r3]
+; CHECK-NEXT:    adds r4, #8
+; CHECK-NEXT:    adds r3, #2
+; CHECK-NEXT:    cmp r6, #0
 ; CHECK-NEXT:    ite ne
-; CHECK-NEXT:    sxthne r5, r1
-; CHECK-NEXT:    moveq r5, #0
-; CHECK-NEXT:    cmp r5, #0
-; CHECK-NEXT:    cset r5, ne
-; CHECK-NEXT:    strb.w r5, [r8]
-; CHECK-NEXT:    le lr, .LBB0_6
-; CHECK-NEXT:  @ %bb.7: @ %for.cond.cleanup9.1
-; CHECK-NEXT:    @ in Loop: Header=BB0_3 Depth=1
-; CHECK-NEXT:    add.w r3, r11, #2
-; CHECK-NEXT:    movs r7, #22
-; CHECK-NEXT:    dls lr, r9
-; CHECK-NEXT:    uxtb r3, r3
-; CHECK-NEXT:    smlabb r7, r3, r7, r10
-; CHECK-NEXT:    mov r3, r2
-; CHECK-NEXT:  .LBB0_8: @ %for.body10.2
+; CHECK-NEXT:    sxthne r6, r1
+; CHECK-NEXT:    moveq r6, #0
+; CHECK-NEXT:    cmp r6, #0
+; CHECK-NEXT:    cset r6, ne
+; CHECK-NEXT:    strb r6, [r5]
+; CHECK-NEXT:    le lr, .LBB0_5
+; CHECK-NEXT:  @ %bb.6: @ %for.cond.cleanup9
+; CHECK-NEXT:    @ in Loop: Header=BB0_4 Depth=2
+; CHECK-NEXT:    movs r2, #11
+; CHECK-NEXT:    mov r4, r11
+; CHECK-NEXT:    dls lr, r2
+; CHECK-NEXT:    mov r3, r0
+; CHECK-NEXT:    ldr r2, [sp, #12] @ 4-byte Reload
+; CHECK-NEXT:  .LBB0_7: @ %for.body10.1
 ; CHECK-NEXT:    @ Parent Loop BB0_3 Depth=1
-; CHECK-NEXT:    @ => This Inner Loop Header: Depth=2
-; CHECK-NEXT:    str r3, [r0, #-4]
-; CHECK-NEXT:    ldrb r6, [r7, #-1]
+; CHECK-NEXT:    @ Parent Loop BB0_4 Depth=2
+; CHECK-NEXT:    @ => This Inner Loop Header: Depth=3
+; CHECK-NEXT:    str r2, [r4, #-4]
+; CHECK-NEXT:    add.w r7, r2, #396
+; CHECK-NEXT:    ldrb r6, [r3, #-1]
+; CHECK-NEXT:    add.w r2, r2, #792
 ; CHECK-NEXT:    cmp r6, #0
 ; CHECK-NEXT:    ite ne
-; CHECK-NEXT:    sxthne r5, r1
-; CHECK-NEXT:    moveq r5, #0
-; CHECK-NEXT:    add.w r6, r3, #396
-; CHECK-NEXT:    cmp r5, #0
-; CHECK-NEXT:    str r6, [r0]
+; CHECK-NEXT:    sxthne r6, r1
+; CHECK-NEXT:    moveq r6, #0
+; CHECK-NEXT:    cmp r6, #0
+; CHECK-NEXT:    str r7, [r4]
 ; CHECK-NEXT:    cset r6, ne
-; CHECK-NEXT:    strb.w r6, [r8]
-; CHECK-NEXT:    add.w r3, r3, #792
-; CHECK-NEXT:    ldrb r6, [r7]
-; CHECK-NEXT:    adds r0, #8
-; CHECK-NEXT:    adds r7, #2
+; CHECK-NEXT:    adds r4, #8
+; CHECK-NEXT:    strb r6, [r5]
+; CHECK-NEXT:    ldrb r6, [r3]
+; CHECK-NEXT:    adds r3, #2
 ; CHECK-NEXT:    cmp r6, #0
 ; CHECK-NEXT:    ite ne
-; CHECK-NEXT:    sxthne r5, r1
-; CHECK-NEXT:    moveq r5, #0
-; CHECK-NEXT:    cmp r5, #0
+; CHECK-NEXT:    sxthne r6, r1
+; CHECK-NEXT:    moveq r6, #0
+; CHECK-NEXT:    cmp r6, #0
 ; CHECK-NEXT:    cset r6, ne
-; CHECK-NEXT:    strb.w r6, [r8]
-; CHECK-NEXT:    le lr, .LBB0_8
-; CHECK-NEXT:  @ %bb.9: @ %for.cond.cleanup9.2
-; CHECK-NEXT:    @ in Loop: Header=BB0_3 Depth=1
-; CHECK-NEXT:    add.w r0, r11, #3
-; CHECK-NEXT:    uxtb.w r11, r0
-; CHECK-NEXT:    cmp.w r11, #18
-; CHECK-NEXT:    it hs
-; CHECK-NEXT:    movhs.w r11, #0
+; CHECK-NEXT:    strb r6, [r5]
+; CHECK-NEXT:    le lr, .LBB0_7
+; CHECK-NEXT:  @ %bb.8: @ %for.cond.cleanup9.1
+; CHECK-NEXT:    @ in Loop: Header=BB0_4 Depth=2
+; CHECK-NEXT:    movs r2, #11
+; CHECK-NEXT:    mov r3, r12
+; CHECK-NEXT:    dls lr, r2
+; CHECK-NEXT:    ldr r2, [sp, #12] @ 4-byte Reload
+; CHECK-NEXT:  .LBB0_9: @ %for.body10.2
+; CHECK-NEXT:    @ Parent Loop BB0_3 Depth=1
+; CHECK-NEXT:    @ Parent Loop BB0_4 Depth=2
+; CHECK-NEXT:    @ => This Inner Loop Header: Depth=3
+; CHECK-NEXT:    str r2, [r11, #-4]
+; CHECK-NEXT:    add.w r6, r2, #396
+; CHECK-NEXT:    ldrb r4, [r3, #-1]
+; CHECK-NEXT:    add.w r2, r2, #792
+; CHECK-NEXT:    cmp r4, #0
+; CHECK-NEXT:    ite ne
+; CHECK-NEXT:    sxthne r4, r1
+; CHECK-NEXT:    moveq r4, #0
+; CHECK-NEXT:    cmp r4, #0
+; CHECK-NEXT:    str.w r6, [r11]
+; CHECK-NEXT:    cset r4, ne
+; CHECK-NEXT:    add.w r11, r11, #8
+; CHECK-NEXT:    strb r4, [r5]
+; CHECK-NEXT:    ldrb r4, [r3]
+; CHECK-NEXT:    adds r3, #2
+; CHECK-NEXT:    cmp r4, #0
+; CHECK-NEXT:    ite ne
+; CHECK-NEXT:    sxthne r4, r1
+; CHECK-NEXT:    moveq r4, #0
+; CHECK-NEXT:    cmp r4, #0
+; CHECK-NEXT:    cset r4, ne
+; CHECK-NEXT:    strb r4, [r5]
+; CHECK-NEXT:    le lr, .LBB0_9
+; CHECK-NEXT:  @ %bb.10: @ %for.cond.cleanup9.2
+; CHECK-NEXT:    @ in Loop: Header=BB0_4 Depth=2
+; CHECK-NEXT:    add.w r2, r10, #3
+; CHECK-NEXT:    add.w r12, r12, #66
+; CHECK-NEXT:    adds r0, #66
+; CHECK-NEXT:    add.w r8, r8, #66
+; CHECK-NEXT:    uxtb.w r10, r2
+; CHECK-NEXT:    ldr r2, [sp, #12] @ 4-byte Reload
+; CHECK-NEXT:    cmp.w r10, #18
+; CHECK-NEXT:    blo.w .LBB0_4
 ; CHECK-NEXT:    b .LBB0_3
-; CHECK-NEXT:  .LBB0_10: @ %for.cond.cleanup
+; CHECK-NEXT:  .LBB0_11: @ %for.cond.cleanup
+; CHECK-NEXT:    add sp, #16
 ; CHECK-NEXT:    pop.w {r4, r5, r6, r7, r8, r9, r10, r11, pc}
-; CHECK-NEXT:  .LBB0_11: @ %for.cond1.us.preheader
+; CHECK-NEXT:  .LBB0_12: @ %for.cond1.us.preheader
 ; CHECK-NEXT:    movw r0, :lower16:arr_61
 ; CHECK-NEXT:    movs r1, #0
 ; CHECK-NEXT:    movt r0, :upper16:arr_61
 ; CHECK-NEXT:    str r1, [r0, #84]
 ; CHECK-NEXT:    .inst.n 0xdefe
 entry:
   %tobool.not = icmp eq i8 %var_2, 0
   br i1 %tobool.not, label %for.cond.cleanup, label %for.cond1.preheader