[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 limitter 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/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 }