diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -5312,6 +5312,26 @@ } const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { + // If all incoming values of the phi are the same then we can reuse the same + // expression for the unique incoming value. + Value *UniqueIncomingValue = PN->hasConstantValue(); + if (UniqueIncomingValue && !isa(UniqueIncomingValue)) { + // It's not possible to get into a cycle here as a result of calling getSCEV + // because the only way to have a valid IR with a cyclic constant phi is to + // have something like: + // lab1: + // %a = phi [%b, lab2] + // br label %lab2 + // lab2: + // %b = phi [%a, lab1] + // br label %lab1 + // where lab1 and lab2 are not reachable from entry. Instructions that are + // not reachable are dealt with at the start of getSCEV as undefined. + const SCEV *Result = getSCEV(UniqueIncomingValue); + ValueExprMap[SCEVCallbackVH(PN, this)] = Result; + return Result; + } + if (const SCEV *S = createAddRecFromPHI(PN)) return S; diff --git a/llvm/test/Analysis/ScalarEvolution/solve-quadratic-i1.ll b/llvm/test/Analysis/ScalarEvolution/solve-quadratic-i1.ll --- a/llvm/test/Analysis/ScalarEvolution/solve-quadratic-i1.ll +++ b/llvm/test/Analysis/ScalarEvolution/solve-quadratic-i1.ll @@ -57,9 +57,9 @@ ; CHECK-NEXT: %v6 = add nuw nsw i32 %v1, 1 ; CHECK-NEXT: --> {4,+,1}<%b1> U: [4,7) S: [4,7) Exits: 6 LoopDispositions: { %b1: Computable } ; CHECK-NEXT: %v7 = phi i32 [ %v1, %b1 ] -; CHECK-NEXT: --> %v7 U: [3,6) S: [3,6) +; CHECK-NEXT: --> {3,+,1}<%b1> U: [3,6) S: [3,6) ; CHECK-NEXT: %v8 = phi i16 [ %v3, %b1 ] -; CHECK-NEXT: --> %v8 U: full-set S: full-set +; CHECK-NEXT: --> {3,+,4,+,1}<%b1> U: full-set S: full-set ; CHECK-NEXT: Determining loop execution counts for: @f1 ; CHECK-NEXT: Loop %b3: Unpredictable backedge-taken count. ; CHECK-NEXT: Loop %b3: Unpredictable max backedge-taken count. diff --git a/llvm/test/Analysis/ScalarEvolution/solve-quadratic-overflow.ll b/llvm/test/Analysis/ScalarEvolution/solve-quadratic-overflow.ll --- a/llvm/test/Analysis/ScalarEvolution/solve-quadratic-overflow.ll +++ b/llvm/test/Analysis/ScalarEvolution/solve-quadratic-overflow.ll @@ -12,11 +12,11 @@ ; CHECK-NEXT: %v3 = mul i16 %v2, %v2 ; CHECK-NEXT: --> {1,+,3,+,2}<%b1> U: full-set S: full-set Exits: 0 LoopDispositions: { %b1: Computable } ; CHECK-NEXT: %v5 = phi i16 [ %v2, %b1 ] -; CHECK-NEXT: --> %v5 U: [-256,0) S: [-256,0) +; CHECK-NEXT: --> {-1,+,-1}<%b1> U: [-256,0) S: [-256,0) ; CHECK-NEXT: %v6 = phi i16 [ %v3, %b1 ] -; CHECK-NEXT: --> %v6 U: full-set S: full-set +; CHECK-NEXT: --> {1,+,3,+,2}<%b1> U: full-set S: full-set ; CHECK-NEXT: %v7 = sext i16 %v5 to i32 -; CHECK-NEXT: --> (sext i16 %v5 to i32) U: [-256,0) S: [-256,0) +; CHECK-NEXT: --> {-1,+,-1}<%b1> U: [-256,0) S: [-256,0) ; CHECK-NEXT: Determining loop execution counts for: @f0 ; CHECK-NEXT: Loop %b1: backedge-taken count is 255 ; CHECK-NEXT: Loop %b1: max backedge-taken count is 255 diff --git a/llvm/test/Analysis/ScalarEvolution/trivial-phis.ll b/llvm/test/Analysis/ScalarEvolution/trivial-phis.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Analysis/ScalarEvolution/trivial-phis.ll @@ -0,0 +1,177 @@ +; RUN: opt < %s -analyze -scalar-evolution | FileCheck %s + +; CHECK-LABEL @test1 +; CHECK: %add.lcssa.wide = phi i64 [ %indvars.iv.next, %do.body ] +; CHECK-NEXT: --> {1,+,1}<%do.body> + +define i64 @test1(i32 signext %n, float* %A) { +entry: + %0 = sext i32 %n to i64 + br label %do.body + +do.body: ; preds = %do.body, %entry + %indvars.iv = phi i64 [ %indvars.iv.next, %do.body ], [ 0, %entry ] + %arrayidx = getelementptr inbounds float, float* %A, i64 %indvars.iv + store float 1.000000e+00, float* %arrayidx, align 4 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %cmp = icmp slt i64 %indvars.iv.next, %0 + br i1 %cmp, label %do.body, label %do.end + +do.end: ; preds = %do.body + %add.lcssa.wide = phi i64 [ %indvars.iv.next, %do.body ] + ret i64 %add.lcssa.wide +} + +; CHECK-LABEL @test2 +; CHECK: %tmp24 = phi i64 [ %tmp14, %bb22 ], [ %tmp14, %bb13 ] +; CHECK-NEXT: --> {1,+,1}[[WrapFlags:.*]]<%bb13> + +define void @test2(i64 %arg, i32* noalias %arg1) { +bb: + %tmp = icmp slt i64 0, %arg + br i1 %tmp, label %bb7, label %bb48 + +bb7: ; preds = %bb + br label %bb8 + +bb8: ; preds = %bb44, %bb7 + %tmp9 = phi i64 [ 0, %bb7 ], [ %tmp45, %bb44 ] + %tmp10 = add nsw i64 %arg, -1 + %tmp11 = icmp slt i64 1, %tmp10 + br i1 %tmp11, label %bb12, label %bb43 + +bb12: ; preds = %bb8 + br label %bb13 + +bb13: ; preds = %bb39, %bb12 + %tmp14 = phi i64 [ 1, %bb12 ], [ %tmp40, %bb39 ] + %tmp15 = icmp slt i64 0, %arg + br i1 %tmp15, label %bb16, label %bb23 + +bb16: ; preds = %bb13 + br label %bb17 + +bb17: ; preds = %bb19, %bb16 + %tmp18 = phi i64 [ 0, %bb16 ], [ %tmp20, %bb19 ] + br label %bb19 + +bb19: ; preds = %bb17 + %tmp20 = add nuw nsw i64 %tmp18, 1 + %tmp21 = icmp slt i64 %tmp20, %arg + br i1 %tmp21, label %bb17, label %bb22 + +bb22: ; preds = %bb19 + br label %bb23 + +bb23: ; preds = %bb22, %bb13 + %tmp24 = phi i64 [ %tmp14, %bb22 ], [ %tmp14, %bb13 ] + %tmp25 = icmp slt i64 0, %arg + br i1 %tmp25, label %bb26, label %bb37 + +bb26: ; preds = %bb23 + br label %bb27 + +bb27: ; preds = %bb33, %bb26 + %tmp28 = phi i64 [ 0, %bb26 ], [ %tmp34, %bb33 ] + %tmp29 = mul nsw i64 %tmp9, %arg + %tmp30 = getelementptr inbounds i32, i32* %arg1, i64 %tmp24 + %tmp31 = getelementptr inbounds i32, i32* %tmp30, i64 %tmp29 + %tmp32 = load i32, i32* %tmp31, align 4 + br label %bb33 + +bb33: ; preds = %bb27 + %tmp34 = add nuw nsw i64 %tmp28, 1 + %tmp35 = icmp slt i64 %tmp34, %arg + br i1 %tmp35, label %bb27, label %bb36 + +bb36: ; preds = %bb33 + br label %bb37 + +bb37: ; preds = %bb36, %bb23 + %tmp38 = phi i64 [ %tmp24, %bb36 ], [ %tmp24, %bb23 ] + br label %bb39 + +bb39: ; preds = %bb37 + %tmp40 = add nuw nsw i64 %tmp38, 1 + %tmp41 = icmp slt i64 %tmp40, %tmp10 + br i1 %tmp41, label %bb13, label %bb42 + +bb42: ; preds = %bb39 + br label %bb43 + +bb43: ; preds = %bb42, %bb8 + br label %bb44 + +bb44: ; preds = %bb43 + %tmp45 = add nuw nsw i64 %tmp9, 1 + %tmp46 = icmp slt i64 %tmp45, %arg + br i1 %tmp46, label %bb8, label %bb47 + +bb47: ; preds = %bb44 + br label %bb48 + +bb48: ; preds = %bb47, %bb + ret void +} + +; CHECK-LABEL @test3 +; CHECK: %tmp24 = phi i64 [ %tmp14, %bb13 ], [ %tmp14, %bb17 ] +; CHECK-NEXT: --> {1,+,1}[[WrapFlags:.*]]<%bb13> +; CHECK: %tmp38 = phi i64 [ %tmp24, %bb23 ], [ %tmp24, %bb27 ] +; CHECK-NEXT: --> {1,+,1}[[WrapFlags:.*]]<%bb13> + +define void @test3(i64 %arg, i32* %arg1) { +bb: + %tmp = icmp slt i64 0, %arg + br i1 %tmp, label %bb8, label %bb48 + +bb8: ; preds = %bb, %bb44 + %tmp9 = phi i64 [ %tmp45, %bb44 ], [ 0, %bb ] + %tmp10 = add nsw i64 %arg, -1 + %tmp11 = icmp slt i64 1, %tmp10 + br i1 %tmp11, label %bb13, label %bb44 + +bb13: ; preds = %bb8, %bb39 + %tmp14 = phi i64 [ %tmp40, %bb39 ], [ 1, %bb8 ] + %tmp15 = icmp slt i64 0, %arg + br i1 %tmp15, label %bb17_a, label %bb23 + +bb17_a: + %tmp18 = phi i64 [ %tmp20, %bb17 ], [ 0, %bb13 ] + %tmp20 = add nuw nsw i64 %tmp18, 1 + + br label %bb17 + +bb17: ; preds = %bb13, %bb17 + %tmp21 = icmp slt i64 %tmp20, %arg + br i1 %tmp21, label %bb17_a, label %bb23 + +bb23: ; preds = %bb17, %bb13 + %tmp24 = phi i64 [ %tmp14, %bb13 ], [ %tmp14, %bb17 ] + %tmp25 = icmp slt i64 0, %arg + br i1 %tmp25, label %bb27, label %bb39 + +bb27: ; preds = %bb23, %bb27 + %tmp28 = phi i64 [ %tmp34, %bb27 ], [ 0, %bb23 ] + %tmp29 = mul nsw i64 %tmp9, %arg + %tmp30 = getelementptr inbounds i32, i32* %arg1, i64 %tmp24 + %tmp31 = getelementptr inbounds i32, i32* %tmp30, i64 %tmp29 + %tmp32 = load i32, i32* %tmp31, align 4 + %tmp34 = add nuw nsw i64 %tmp28, 1 + %tmp35 = icmp slt i64 %tmp34, %arg + br i1 %tmp35, label %bb27, label %bb39 + +bb39: ; preds = %bb23, %bb27 + %tmp38 = phi i64 [ %tmp24, %bb23 ], [ %tmp24, %bb27 ] + %tmp40 = add nuw nsw i64 %tmp38, 1 + %tmp41 = icmp slt i64 %tmp40, %tmp10 + br i1 %tmp41, label %bb13, label %bb44 + +bb44: ; preds = %bb8, %bb39 + %tmp45 = add nuw nsw i64 %tmp9, 1 + %tmp46 = icmp slt i64 %tmp45, %arg + br i1 %tmp46, label %bb8, label %bb48 + +bb48: ; preds = %bb44, %bb + ret void +} diff --git a/llvm/test/Transforms/IndVarSimplify/lftr-pr20680.ll b/llvm/test/Transforms/IndVarSimplify/lftr-pr20680.ll --- a/llvm/test/Transforms/IndVarSimplify/lftr-pr20680.ll +++ b/llvm/test/Transforms/IndVarSimplify/lftr-pr20680.ll @@ -21,9 +21,6 @@ ; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i32 [ [[INDVARS_IV_NEXT:%.*]], [[FOR_INC13:%.*]] ], [ -14, [[ENTRY:%.*]] ] ; CHECK-NEXT: br i1 [[TOBOOL2]], label [[FOR_INC13]], label [[FOR_BODY3_LR_PH:%.*]] ; CHECK: for.body3.lr.ph: -; CHECK-NEXT: [[TMP2:%.*]] = add nsw i32 [[INDVARS_IV]], 1 -; CHECK-NEXT: [[TMP3:%.*]] = icmp ult i32 [[TMP2]], 3 -; CHECK-NEXT: [[DIV:%.*]] = select i1 [[TMP3]], i32 [[INDVARS_IV]], i32 0 ; CHECK-NEXT: br i1 false, label [[FOR_BODY3_LR_PH_SPLIT_US:%.*]], label [[FOR_BODY3_LR_PH_FOR_BODY3_LR_PH_SPLIT_CRIT_EDGE:%.*]] ; CHECK: for.body3.lr.ph.for.body3.lr.ph.split_crit_edge: ; CHECK-NEXT: br label [[FOR_BODY3_LR_PH_SPLIT:%.*]] @@ -80,7 +77,6 @@ ; CHECK: for.cond2.for.inc13_crit_edge.us-lcssa.us.us-lcssa: ; CHECK-NEXT: br label [[FOR_COND2_FOR_INC13_CRIT_EDGE_US_LCSSA_US]] ; CHECK: for.cond2.for.inc13_crit_edge.us-lcssa.us: -; CHECK-NEXT: [[COND_LCSSA_PH_US:%.*]] = phi i32 [ [[DIV]], [[FOR_COND2_FOR_INC13_CRIT_EDGE_US_LCSSA_US_US_LCSSA]] ], [ [[DIV]], [[FOR_COND2_FOR_INC13_CRIT_EDGE_US_LCSSA_US_US_LCSSA_US]] ] ; CHECK-NEXT: br label [[FOR_COND2_FOR_INC13_CRIT_EDGE:%.*]] ; CHECK: for.body3.lr.ph.split: ; CHECK-NEXT: br i1 [[TOBOOL]], label [[FOR_BODY3_LR_PH_SPLIT_SPLIT_US:%.*]], label [[FOR_BODY3_LR_PH_SPLIT_FOR_BODY3_LR_PH_SPLIT_SPLIT_CRIT_EDGE:%.*]] @@ -135,11 +131,9 @@ ; CHECK: for.cond2.for.inc13_crit_edge.us-lcssa.us-lcssa: ; CHECK-NEXT: br label [[FOR_COND2_FOR_INC13_CRIT_EDGE_US_LCSSA]] ; CHECK: for.cond2.for.inc13_crit_edge.us-lcssa: -; CHECK-NEXT: [[COND_LCSSA_PH:%.*]] = phi i32 [ [[INDVARS_IV]], [[FOR_COND2_FOR_INC13_CRIT_EDGE_US_LCSSA_US_LCSSA]] ], [ [[INDVARS_IV]], [[FOR_COND2_FOR_INC13_CRIT_EDGE_US_LCSSA_US_LCSSA_US]] ] ; CHECK-NEXT: br label [[FOR_COND2_FOR_INC13_CRIT_EDGE]] ; CHECK: for.cond2.for.inc13_crit_edge: -; CHECK-NEXT: [[COND_LCSSA:%.*]] = phi i32 [ [[COND_LCSSA_PH]], [[FOR_COND2_FOR_INC13_CRIT_EDGE_US_LCSSA]] ], [ [[COND_LCSSA_PH_US]], [[FOR_COND2_FOR_INC13_CRIT_EDGE_US_LCSSA_US]] ] -; CHECK-NEXT: store i32 [[COND_LCSSA]], i32* @c, align 4 +; CHECK-NEXT: store i32 [[INDVARS_IV]], i32* @c, align 4 ; CHECK-NEXT: br label [[FOR_INC13]] ; CHECK: for.inc13: ; CHECK-NEXT: [[INDVARS_IV_NEXT]] = add nsw i32 [[INDVARS_IV]], 1 diff --git a/llvm/test/Transforms/LoopIdiom/scev-invalidation.ll b/llvm/test/Transforms/LoopIdiom/scev-invalidation.ll --- a/llvm/test/Transforms/LoopIdiom/scev-invalidation.ll +++ b/llvm/test/Transforms/LoopIdiom/scev-invalidation.ll @@ -1,3 +1,6 @@ +; Since I don't expect this patch to land until a solution is provided to the LCSSA issue, I'm going to xfail this for now. +; (This can be unblocked likely by making SCEVExpander preserve lcssa: https://reviews.llvm.org/D71538) +; XFAIL: * ; RUN: opt -S -indvars -loop-idiom < %s ; PR14214 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" diff --git a/llvm/test/Transforms/LoopStrengthReduce/funclet.ll b/llvm/test/Transforms/LoopStrengthReduce/funclet.ll --- a/llvm/test/Transforms/LoopStrengthReduce/funclet.ll +++ b/llvm/test/Transforms/LoopStrengthReduce/funclet.ll @@ -45,7 +45,9 @@ ; CHECK-LABEL: define void @f( ; CHECK: cleanuppad within none [] -; CHECK-NEXT: ptrtoint i8* %phi2 to i32 +; CHECK-NEXT: br label %loop_body +; CHECK: loop_body: +; CHECK-NEXT: %lsr.iv = phi i32 [ %lsr.iv.next, %iter ], define void @g() personality i32 (...)* @_except_handler3 { entry: @@ -87,8 +89,9 @@ ; CHECK-LABEL: define void @g( ; CHECK: blah: ; CHECK-NEXT: catchpad within %cs [] -; CHECK-NEXT: ptrtoint i8* %phi2 to i32 - +; CHECK-NEXT: br label %loop_body +; CHECK: loop_body: +; CHECK-NEXT: %lsr.iv = phi i32 [ %lsr.iv.next, %iter ], define void @h() personality i32 (...)* @_except_handler3 { entry: @@ -129,8 +132,9 @@ ; CHECK-LABEL: define void @h( ; CHECK: blug: +; CHECK-NOT: %phi2 = phi i8* [ %tmp96, %pad ] ; CHECK: catchpad within %cs [] -; CHECK-NEXT: ptrtoint i8* %phi2 to i32 +; CHECK-NEXT: br label %loop_body define void @i() personality i32 (...)* @_except_handler3 { entry: @@ -170,7 +174,8 @@ } ; CHECK-LABEL: define void @i( -; CHECK: ptrtoint i8* %phi2 to i32 +; CHECK: loop_head: +; CHECK-NEXT: br label %loop_body define void @test1(i32* %b, i32* %c) personality i32 (...)* @__CxxFrameHandler3 { entry: