diff --git a/llvm/include/llvm/Transforms/Utils/LoopUtils.h b/llvm/include/llvm/Transforms/Utils/LoopUtils.h --- a/llvm/include/llvm/Transforms/Utils/LoopUtils.h +++ b/llvm/include/llvm/Transforms/Utils/LoopUtils.h @@ -73,7 +73,8 @@ /// /// Returns true if any modifications are made. bool formLCSSAForInstructions(SmallVectorImpl &Worklist, - DominatorTree &DT, LoopInfo &LI); + DominatorTree &DT, LoopInfo &LI, + ScalarEvolution *SE); /// Put loop into LCSSA form. /// diff --git a/llvm/lib/Transforms/Utils/LCSSA.cpp b/llvm/lib/Transforms/Utils/LCSSA.cpp --- a/llvm/lib/Transforms/Utils/LCSSA.cpp +++ b/llvm/lib/Transforms/Utils/LCSSA.cpp @@ -74,7 +74,8 @@ /// that are outside the current loop. If so, insert LCSSA PHI nodes and /// rewrite the uses. bool llvm::formLCSSAForInstructions(SmallVectorImpl &Worklist, - DominatorTree &DT, LoopInfo &LI) { + DominatorTree &DT, LoopInfo &LI, + ScalarEvolution *SE) { SmallVector UsesToRewrite; SmallSetVector PHIsToRemove; PredIteratorCache PredCache; @@ -134,6 +135,11 @@ SSAUpdater SSAUpdate(&InsertedPHIs); SSAUpdate.Initialize(I->getType(), I->getName()); + // Force re-computation of I, as some users now need to use the new PHI + // node. + if (SE) + SE->forgetValue(I); + // Insert the LCSSA phi's into all of the exit blocks dominated by the // value, and add them to the Phi's map. for (BasicBlock *ExitBB : ExitBlocks) { @@ -368,7 +374,7 @@ Worklist.push_back(&I); } } - Changed = formLCSSAForInstructions(Worklist, DT, *LI); + Changed = formLCSSAForInstructions(Worklist, DT, *LI, SE); // If we modified the code, remove any caches about the loop from SCEV to // avoid dangling entries. diff --git a/llvm/test/Transforms/LoopUnroll/unroll-preserve-scev-lcssa.ll b/llvm/test/Transforms/LoopUnroll/unroll-preserve-scev-lcssa.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/LoopUnroll/unroll-preserve-scev-lcssa.ll @@ -0,0 +1,103 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -loop-reduce -loop-unroll -unroll-runtime -verify-scev -verify-scev-strict -verify-loop-lcssa < %s -S | FileCheck %s + +; Test case for PR43458. We check that we do properly invalidate LCSSA phi +; users in SCEV. Run -loop-reduce first, so SCEV is already populated. + +define void @spam() { +; CHECK-LABEL: @spam( +; CHECK-NEXT: bb: +; CHECK-NEXT: br label [[BB3:%.*]] +; CHECK: bb3: +; CHECK-NEXT: br i1 undef, label [[BB9:%.*]], label [[BB5_PREHEADER:%.*]] +; CHECK: bb5.preheader: +; CHECK-NEXT: br label [[BB5:%.*]] +; CHECK: bb5: +; CHECK-NEXT: br label [[BB9]] +; CHECK: bb9: +; CHECK-NEXT: br i1 false, label [[BB24_PREHEADER:%.*]], label [[BB29:%.*]] +; CHECK: bb24.preheader: +; CHECK-NEXT: [[TMP0:%.*]] = add nsw i64 0, -1 +; CHECK-NEXT: [[XTRAITER:%.*]] = and i64 0, 7 +; CHECK-NEXT: [[TMP1:%.*]] = icmp ult i64 [[TMP0]], 7 +; CHECK-NEXT: br i1 [[TMP1]], label [[BB29_LOOPEXIT_UNR_LCSSA:%.*]], label [[BB24_PREHEADER_NEW:%.*]] +; CHECK: bb24.preheader.new: +; CHECK-NEXT: [[UNROLL_ITER:%.*]] = sub i64 0, [[XTRAITER]] +; CHECK-NEXT: br label [[BB24:%.*]] +; CHECK: bb24: +; CHECK-NEXT: [[TMP25:%.*]] = phi i64 [ 0, [[BB24_PREHEADER_NEW]] ], [ [[TMP26_7:%.*]], [[BB24]] ] +; CHECK-NEXT: [[NITER:%.*]] = phi i64 [ [[UNROLL_ITER]], [[BB24_PREHEADER_NEW]] ], [ [[NITER_NSUB_7:%.*]], [[BB24]] ] +; CHECK-NEXT: [[TMP26:%.*]] = add nuw nsw i64 [[TMP25]], 1 +; CHECK-NEXT: [[NITER_NSUB:%.*]] = sub i64 [[NITER]], 1 +; CHECK-NEXT: [[TMP26_1:%.*]] = add nuw nsw i64 [[TMP26]], 1 +; CHECK-NEXT: [[NITER_NSUB_1:%.*]] = sub i64 [[NITER_NSUB]], 1 +; CHECK-NEXT: [[TMP26_2:%.*]] = add nuw nsw i64 [[TMP26_1]], 1 +; CHECK-NEXT: [[NITER_NSUB_2:%.*]] = sub i64 [[NITER_NSUB_1]], 1 +; CHECK-NEXT: [[TMP26_3:%.*]] = add nuw nsw i64 [[TMP26_2]], 1 +; CHECK-NEXT: [[NITER_NSUB_3:%.*]] = sub i64 [[NITER_NSUB_2]], 1 +; CHECK-NEXT: [[TMP26_4:%.*]] = add nuw nsw i64 [[TMP26_3]], 1 +; CHECK-NEXT: [[NITER_NSUB_4:%.*]] = sub i64 [[NITER_NSUB_3]], 1 +; CHECK-NEXT: [[TMP26_5:%.*]] = add nuw nsw i64 [[TMP26_4]], 1 +; CHECK-NEXT: [[NITER_NSUB_5:%.*]] = sub i64 [[NITER_NSUB_4]], 1 +; CHECK-NEXT: [[TMP26_6:%.*]] = add nuw nsw i64 [[TMP26_5]], 1 +; CHECK-NEXT: [[NITER_NSUB_6:%.*]] = sub i64 [[NITER_NSUB_5]], 1 +; CHECK-NEXT: [[TMP26_7]] = add nuw nsw i64 [[TMP26_6]], 1 +; CHECK-NEXT: [[NITER_NSUB_7]] = sub i64 [[NITER_NSUB_6]], 1 +; CHECK-NEXT: [[NITER_NCMP_7:%.*]] = icmp ne i64 [[NITER_NSUB_7]], 0 +; CHECK-NEXT: br i1 [[NITER_NCMP_7]], label [[BB24]], label [[BB29_LOOPEXIT_UNR_LCSSA_LOOPEXIT:%.*]] +; CHECK: bb29.loopexit.unr-lcssa.loopexit: +; CHECK-NEXT: [[TMP25_UNR_PH:%.*]] = phi i64 [ [[TMP26_7]], [[BB24]] ] +; CHECK-NEXT: br label [[BB29_LOOPEXIT_UNR_LCSSA]] +; CHECK: bb29.loopexit.unr-lcssa: +; CHECK-NEXT: [[TMP25_UNR:%.*]] = phi i64 [ 0, [[BB24_PREHEADER]] ], [ [[TMP25_UNR_PH]], [[BB29_LOOPEXIT_UNR_LCSSA_LOOPEXIT]] ] +; CHECK-NEXT: [[LCMP_MOD:%.*]] = icmp ne i64 [[XTRAITER]], 0 +; CHECK-NEXT: br i1 [[LCMP_MOD]], label [[BB24_EPIL_PREHEADER:%.*]], label [[BB29_LOOPEXIT:%.*]] +; CHECK: bb24.epil.preheader: +; CHECK-NEXT: br label [[BB24_EPIL:%.*]] +; CHECK: bb24.epil: +; CHECK-NEXT: [[TMP25_EPIL:%.*]] = phi i64 [ [[TMP26_EPIL:%.*]], [[BB24_EPIL]] ], [ [[TMP25_UNR]], [[BB24_EPIL_PREHEADER]] ] +; CHECK-NEXT: [[EPIL_ITER:%.*]] = phi i64 [ [[XTRAITER]], [[BB24_EPIL_PREHEADER]] ], [ [[EPIL_ITER_SUB:%.*]], [[BB24_EPIL]] ] +; CHECK-NEXT: [[TMP26_EPIL]] = add nuw nsw i64 [[TMP25_EPIL]], 1 +; CHECK-NEXT: [[TMP27_EPIL:%.*]] = icmp slt i64 [[TMP26_EPIL]], 0 +; CHECK-NEXT: [[EPIL_ITER_SUB]] = sub i64 [[EPIL_ITER]], 1 +; CHECK-NEXT: [[EPIL_ITER_CMP:%.*]] = icmp ne i64 [[EPIL_ITER_SUB]], 0 +; CHECK-NEXT: br i1 [[EPIL_ITER_CMP]], label [[BB24_EPIL]], label [[BB29_LOOPEXIT_EPILOG_LCSSA:%.*]], !llvm.loop !0 +; CHECK: bb29.loopexit.epilog-lcssa: +; CHECK-NEXT: br label [[BB29_LOOPEXIT]] +; CHECK: bb29.loopexit: +; CHECK-NEXT: br label [[BB29]] +; CHECK: bb29: +; CHECK-NEXT: ret void +; +bb: + br label %bb3 + +bb3: ; preds = %bb9, %bb + br i1 undef, label %bb9, label %bb5 + +bb5: ; preds = %bb5, %bb3 + %tmp6 = add nsw i64 undef, 1 + br i1 undef, label %bb8, label %bb5 + +bb8: ; preds = %bb5 + br label %bb9 + +bb9: ; preds = %bb8, %bb3 + %tmp10 = phi i64 [ 0, %bb3 ], [ %tmp6, %bb8 ] + %tmp11 = trunc i64 %tmp10 to i32 + br i1 false, label %bb3, label %bb20 + +bb20: ; preds = %bb9 + %tmp21 = sext i32 %tmp11 to i64 + %tmp22 = icmp slt i64 0, %tmp21 + br i1 %tmp22, label %bb24, label %bb29 + +bb24: ; preds = %bb24, %bb20 + %tmp25 = phi i64 [ %tmp26, %bb24 ], [ 0, %bb20 ] + %tmp26 = add nuw nsw i64 %tmp25, 1 + %tmp27 = icmp slt i64 %tmp26, %tmp21 + br i1 %tmp27, label %bb24, label %bb29 + +bb29: ; preds = %bb24, %bb20 + ret void +}