Index: llvm/lib/Analysis/ScalarEvolution.cpp =================================================================== --- llvm/lib/Analysis/ScalarEvolution.cpp +++ llvm/lib/Analysis/ScalarEvolution.cpp @@ -2778,7 +2778,28 @@ // This follows from the fact that the no-wrap flags on the outer add // expression are applicable on the 0th iteration, when the add recurrence // will be equal to its start value. - AddRecOps[0] = getAddExpr(LIOps, Flags, Depth + 1); + // However AddRec's loop might be runtime dead and 0th iteration may not + // happen. In this case out implication of flags would be incorrect. + // We say that AddRec's loop is guaranteed to be executed if its header + // dominates all loop's latches used in expression. + SmallPtrSet UsedLoops; + for (auto Op : LIOps) + getUsedLoops(Op, UsedLoops); + bool is0thIterationGuaranteed = all_of(UsedLoops, [&](const Loop *L) { + SmallVector Latches; + L->getLoopLatches(Latches); + return Latches.size() && + all_of(Latches, [&](BasicBlock *Latch) { + return DT.dominates(AddRec->getLoop()->getHeader(), Latch); + }); + }); + SCEV::NoWrapFlags FlagsForNewStart = Flags; + // If there is no guarantee for 0th iteration, try our best for infer + // flags. + if (!is0thIterationGuaranteed) + FlagsForNewStart = StrengthenNoWrapFlags( + this, scAddExpr, LIOps, SCEV::NoWrapFlags::FlagAnyWrap); + AddRecOps[0] = getAddExpr(LIOps, FlagsForNewStart, Depth + 1); // Build the new addrec. Propagate the NUW and NSW flags if both the // outer add and the inner addrec are guaranteed to have no overflow. Index: llvm/test/Analysis/ScalarEvolution/nuw-add-nested-loops.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/nuw-add-nested-loops.ll +++ llvm/test/Analysis/ScalarEvolution/nuw-add-nested-loops.ll @@ -7,19 +7,27 @@ ; incorrect transformation. ; CHECK-ANALYSIS: %r.ivi.next = add nuw nsw i32 %r.ivi, 1 -; CHECK-ANALYSIS-NEXT: --> {{{{}}-399,+,1}<%outer_header>,+,1}<%right_header> +; CHECK-ANALYSIS-NEXT: --> {{{{}}-399,+,1}<%outer_header>,+,1}<%right_header> ; CHECK-ANALYSIS: %l.ivi.next = add nsw i32 %l.ivi, 1 -; CHECK-ANALYSIS-NEXT: --> {{{{}}-399,+,1}<%outer_header>,+,1}<%left_header> +; CHECK-ANALYSIS-NEXT: --> {{{{}}-399,+,1}<%outer_header>,+,1}<%left_header> define void @test(i1 %c) { ; CHECK-LABEL: @test( ; CHECK-NEXT: entry: ; CHECK-NEXT: br label [[OUTER_HEADER:%.*]] ; CHECK: outer_header: -; CHECK-NEXT: [[IVO:%.*]] = phi i32 [ -400, [[ENTRY:%.*]] ], [ [[IVO_NEXT:%.*]], [[OUTER_BACKEDGE:%.*]] ] +; CHECK-NEXT: [[INDVARS_IV4:%.*]] = phi i32 [ [[INDVARS_IV_NEXT5:%.*]], [[OUTER_BACKEDGE:%.*]] ], [ 402, [[ENTRY:%.*]] ] +; CHECK-NEXT: [[INDVARS_IV2:%.*]] = phi i32 [ [[INDVARS_IV_NEXT3:%.*]], [[OUTER_BACKEDGE]] ], [ 399, [[ENTRY]] ] +; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i32 [ [[INDVARS_IV_NEXT:%.*]], [[OUTER_BACKEDGE]] ], [ -399, [[ENTRY]] ] +; CHECK-NEXT: [[IVO:%.*]] = phi i32 [ -400, [[ENTRY]] ], [ [[IVO_NEXT:%.*]], [[OUTER_BACKEDGE]] ] +; CHECK-NEXT: [[UMAX:%.*]] = call i32 @llvm.umax.i32(i32 [[INDVARS_IV]], i32 400) +; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[UMAX]], [[INDVARS_IV2]] +; CHECK-NEXT: [[UMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[INDVARS_IV4]], i32 [[TMP0]]) ; CHECK-NEXT: br i1 [[C:%.*]], label [[LEFT_HEADER_PREHEADER:%.*]], label [[RIGHT_HEADER_PREHEADER:%.*]] ; CHECK: right_header.preheader: ; CHECK-NEXT: br label [[RIGHT_HEADER:%.*]] ; CHECK: left_header.preheader: +; CHECK-NEXT: [[TMP1:%.*]] = icmp ne i32 [[TMP0]], [[UMIN]] +; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i32 [[INDVARS_IV4]], [[UMIN]] ; CHECK-NEXT: br label [[LEFT_HEADER:%.*]] ; CHECK: right_header: ; CHECK-NEXT: [[R_IVI:%.*]] = phi i32 [ [[R_IVI_NEXT:%.*]], [[RIGHT_HEADER]] ], [ [[IVO]], [[RIGHT_HEADER_PREHEADER]] ] @@ -27,11 +35,12 @@ ; CHECK-NEXT: [[R_IVI_NEXT_SDIV:%.*]] = sdiv i32 -1, [[R_IVI_NEXT]] ; CHECK-NEXT: [[R_IVI_NEXT_ZEXT:%.*]] = zext i32 [[R_IVI_NEXT_SDIV]] to i64 ; CHECK-NEXT: call void @bar(i64 [[R_IVI_NEXT_ZEXT]]) -; CHECK-NEXT: br i1 false, label [[OUTER_BACKEDGE_LOOPEXIT1:%.*]], label [[RIGHT_HEADER]] +; CHECK-NEXT: [[R_C:%.*]] = icmp sgt i32 [[R_IVI_NEXT]], 1 +; CHECK-NEXT: br i1 [[R_C]], label [[OUTER_BACKEDGE_LOOPEXIT1:%.*]], label [[RIGHT_HEADER]] ; CHECK: left_header: -; CHECK-NEXT: br i1 false, label [[LEFT_BACKEDGE:%.*]], label [[OUTER_BACKEDGE_LOOPEXIT:%.*]] +; CHECK-NEXT: br i1 [[TMP1]], label [[LEFT_BACKEDGE:%.*]], label [[OUTER_BACKEDGE_LOOPEXIT:%.*]] ; CHECK: left_backedge: -; CHECK-NEXT: br i1 false, label [[LEFT_EXIT:%.*]], label [[LEFT_HEADER]] +; CHECK-NEXT: br i1 [[TMP2]], label [[LEFT_EXIT:%.*]], label [[LEFT_HEADER]] ; CHECK: left_exit: ; CHECK-NEXT: call void @foo() ; CHECK-NEXT: br label [[OUTER_BACKEDGE]] @@ -42,6 +51,9 @@ ; CHECK: outer_backedge: ; CHECK-NEXT: [[IVO_NEXT]] = add nuw nsw i32 [[IVO]], 1 ; CHECK-NEXT: [[C_2:%.*]] = icmp sgt i32 [[IVO]], -2 +; CHECK-NEXT: [[INDVARS_IV_NEXT]] = add nsw i32 [[INDVARS_IV]], 1 +; CHECK-NEXT: [[INDVARS_IV_NEXT3]] = add nsw i32 [[INDVARS_IV2]], -1 +; CHECK-NEXT: [[INDVARS_IV_NEXT5]] = add nsw i32 [[INDVARS_IV4]], -1 ; CHECK-NEXT: br i1 [[C_2]], label [[EXIT:%.*]], label [[OUTER_HEADER]] ; CHECK: exit: ; CHECK-NEXT: ret void Index: llvm/test/Analysis/ScalarEvolution/nuw-add-sibling-loops.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/nuw-add-sibling-loops.ll +++ llvm/test/Analysis/ScalarEvolution/nuw-add-sibling-loops.ll @@ -4,9 +4,9 @@ ; for expression corresponding to outer_header loop. ; CHECK-ANALYSIS: %r.ivi.next = add nuw nsw i32 %r.ivi, 1 -; CHECK-ANALYSIS-NEXT: {{{{}}-399,+,1}<%outer_header>,+,1}<%right_header> +; CHECK-ANALYSIS-NEXT: {{{{}}-399,+,1}<%outer_header>,+,1}<%right_header> ; CHECK-ANALYSIS: %l.ivi.next = add nsw i32 %l.ivi, 1 -; CHECK-ANALYSIS-NEXT: {{{{}}-399,+,1}<%outer_header>,+,1}<%left_header> +; CHECK-ANALYSIS-NEXT: {{{{}}-399,+,1}<%outer_header>,+,1}<%left_header> define void @test(i1 %c) { entry: br label %outer_header