[KnownBits] Limited recursion through phi operands

[reames]

Summary

This change adjusts the phi handling in known-bits to allow recursing into phi operands, but adjusts the depth parameter to avoid potential exponential compile time growth. Specifically, the remaining depth limit is even divided across the number of operands with the depth per operand adjusted upwards so that the total number of recursion steps is limited to the same value we'd perform on a tree of e.g. binary instructions.

This looks on the surface like it might allow a large degree of fan out, but it doesn't. Some examples follow to help explain.

Term the difference between current depth and max depth as "budget". Max depth currently defaults to 6.

Consider:

• A one operand phi increases depth by one. This behaves just like any non-phi instruction.
• A two operand phi increases depth by half of budget.
• A three operand phi increases depth by two thirds of the remaining budget.
• Etc..

Put this together, and we can only recurse through at most two (non-single operand) phis. The first phi splits the budget, and the second one splits it again. For 2 operands, that means we'd divided budget by 4. Since max budget is 6, that means we're down to per operand budget of 1 (required to preserve prior behavior), and won't recurse further.

[reames]

Hoist invariant code out of the loop.

[RKSimon]

Thanks for looking at this! I guess it comes down to increased compile time - do you have a branch that could be tested on https://llvm-compile-time-tracker.com ?

[foad]

Specifically, the remaining depth limit is even divided across the number of operands with the depth per operand adjusted upwards so that the total number of recursion steps is limited to the same value we'd perform on a tree of e.g. binary instructions.

I don't quite get the logic here. Are you saying that for a tree of binary instructions we do about 2^6 recursive steps, and for a tree of N-operand phis you'd like to keep the same limit of about 2^6 steps instead of risking it blow up to N^6 steps? If so then I think you'd need to reduce depth by log2(N) at each step. Or perhaps max(log2(N), 1) to handle the 1-operand phi case gracefully.

[nikic]

Compile-time: http://llvm-compile-time-tracker.com/compare.php?from=c04eab8c78e517210c7641551ec008b09bfe20d0&to=b16b7055f4440d416e2b8da337c0a926f121be89&stat=instructions

llvm/lib/Analysis/ValueTracking.cpp

case Instruction::PHI: {
     // taking conservative care to avoid excessive recursion.
     if (Depth < MaxAnalysisRecursionDepth - 1 && !Known.Zero && !Known.One) {
       // Skip if every incoming value references to ourself.
       if (isa_and_nonnull<UndefValue>(P->hasConstantValue()))
         break;
 
       Known.Zero.setAllBits();
       Known.One.setAllBits();
-      for (unsigned u = 0, e = P->getNumIncomingValues(); u < e; ++u) {
+      const unsigned RemainingTotalBudget =
+        MaxAnalysisRecursionDepth - 1 - Depth;
+      const unsigned NumIncoming = P->getNumIncomingValues();
+      const unsigned NewDepth = MaxAnalysisRecursionDepth -
+        std::max(1U, RemainingTotalBudget / NumIncoming);
+      assert(NewDepth > Depth && NewDepth < MaxAnalysisRecursionDepth);
+      for (unsigned u = 0, e = NumIncoming; u < e; ++u) {
         Value *IncValue = P->getIncomingValue(u);
         // Skip direct self references.
         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).
         Query 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);
+        // Recurse, but spread our depth remaining across all operands to
+        // avoid exponential compile time.  Always allow one recursive step
+        // so that e.g. constants are handled regardless of number of operands.
+        computeKnownBits(IncValue, Known2, NewDepth, 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.

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/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/runtime-unroll-remainder.ll

 ; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[ARRAYIDX_EPIL]], align 4
 ; CHECK-NEXT:    [[ARRAYIDX2_EPIL:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i64 [[INDVARS_IV_UNR]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = load i32, i32* [[ARRAYIDX2_EPIL]], align 4
 ; CHECK-NEXT:    [[MUL_EPIL:%.*]] = mul nsw i32 [[TMP3]], [[TMP2]]
 ; 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, i32* [[A]], i64 [[INDVARS_IV_NEXT_EPIL]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = load i32, i32* [[ARRAYIDX_EPIL_1]], align 4
 ; CHECK-NEXT:    [[ARRAYIDX2_EPIL_1:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 [[INDVARS_IV_NEXT_EPIL]]
 ; CHECK-NEXT:    [[TMP5:%.*]] = load i32, i32* [[ARRAYIDX2_EPIL_1]], align 4
 ; CHECK-NEXT:    [[MUL_EPIL_1:%.*]] = mul nsw i32 [[TMP5]], [[TMP4]]
 ; 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, i32* [[A]], i64 [[INDVARS_IV_NEXT_EPIL_1]]
 ; CHECK-NEXT:    [[TMP6:%.*]] = load i32, i32* [[ARRAYIDX_EPIL_2]], align 4
 ; CHECK-NEXT:    [[ARRAYIDX2_EPIL_2:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 [[INDVARS_IV_NEXT_EPIL_1]]
 ; CHECK-NEXT:    [[TMP7:%.*]] = load i32, i32* [[ARRAYIDX2_EPIL_2]], align 4
 ; CHECK-NEXT:    [[MUL_EPIL_2:%.*]] = mul nsw i32 [[TMP7]], [[TMP6]]
 ; 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: