Index: llvm/lib/Analysis/ValueTracking.cpp =================================================================== --- llvm/lib/Analysis/ValueTracking.cpp +++ llvm/lib/Analysis/ValueTracking.cpp @@ -1562,7 +1562,13 @@ 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; @@ -1576,9 +1582,10 @@ 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. Index: llvm/test/Analysis/ScalarEvolution/outer_phi.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/outer_phi.ll +++ llvm/test/Analysis/ScalarEvolution/outer_phi.ll @@ -7,7 +7,7 @@ ; 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: <> LoopDispositions: { %outer: Variant, %inner: Invariant } +; CHECK-NEXT: --> %outer.iv U: [0,-2147483648) S: [0,-2147483648) Exits: <> LoopDispositions: { %outer: Variant, %inner: Invariant } ; CHECK-NEXT: %iv = phi i32 [ 0, %outer ], [ %iv.next, %inner.backedge ] ; CHECK-NEXT: --> {0,+,1}<%inner> U: [0,-2147483648) S: [0,-2147483648) Exits: <> LoopDispositions: { %inner: Computable, %outer: Variant } ; CHECK-NEXT: %iv.next = add nuw nsw i32 %iv, 1 Index: llvm/test/Transforms/InstCombine/known-phi-recurse.ll =================================================================== --- llvm/test/Transforms/InstCombine/known-phi-recurse.ll +++ llvm/test/Transforms/InstCombine/known-phi-recurse.ll @@ -43,8 +43,7 @@ ; 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) @@ -70,8 +69,7 @@ ; 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) Index: llvm/test/Transforms/LoopUnroll/runtime-unroll-remainder.ll =================================================================== --- llvm/test/Transforms/LoopUnroll/runtime-unroll-remainder.ll +++ llvm/test/Transforms/LoopUnroll/runtime-unroll-remainder.ll @@ -36,7 +36,7 @@ ; 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]] @@ -46,7 +46,7 @@ ; 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]] Index: llvm/test/Transforms/PhaseOrdering/X86/pr38280.ll =================================================================== --- llvm/test/Transforms/PhaseOrdering/X86/pr38280.ll +++ llvm/test/Transforms/PhaseOrdering/X86/pr38280.ll @@ -32,7 +32,7 @@ ; 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 @@ -41,7 +41,7 @@ ; 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 ;