Index: llvm/test/Analysis/ScalarEvolution/2008-11-18-Stride1.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/2008-11-18-Stride1.ll +++ llvm/test/Analysis/ScalarEvolution/2008-11-18-Stride1.ll @@ -1,38 +1,59 @@ +; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 2 ; RUN: opt < %s -disable-output "-passes=print" 2>&1 | FileCheck %s -; CHECK: Loop %bb: backedge-taken count is ((-5 + %x) /u 3) -; CHECK: Loop %bb: constant max backedge-taken count is 1431655764 - - ; ScalarEvolution can't compute a trip count because it doesn't know if ; dividing by the stride will have a remainder. This could theoretically ; be teaching it how to use a more elaborate trip count computation. define i32 @f(i32 %x) nounwind readnone { +; CHECK-LABEL: 'f' +; CHECK-NEXT: Classifying expressions for: @f +; CHECK-NEXT: %indvar = phi i32 [ 0, %bb.nph ], [ %indvar.next, %bb1 ] +; CHECK-NEXT: --> {0,+,1}<%bb> U: [0,1431655765) S: [0,1431655765) Exits: ((-5 + %x) /u 3) LoopDispositions: { %bb: Computable } +; CHECK-NEXT: %tmp = mul i32 %indvar, -3 +; CHECK-NEXT: --> {0,+,-3}<%bb> U: [4,1) S: [4,1) Exits: (-3 * ((-5 + %x) /u 3)) LoopDispositions: { %bb: Computable } +; CHECK-NEXT: %x_addr.04 = add i32 %tmp, %x +; CHECK-NEXT: --> {%x,+,-3}<%bb> U: full-set S: full-set Exits: ((-3 * ((-5 + %x) /u 3)) + %x) LoopDispositions: { %bb: Computable } +; CHECK-NEXT: %1 = add i32 %x_addr.04, -3 +; CHECK-NEXT: --> {(-3 + %x),+,-3}<%bb> U: full-set S: full-set Exits: (-3 + (-3 * ((-5 + %x) /u 3)) + %x) LoopDispositions: { %bb: Computable } +; CHECK-NEXT: %indvar.next = add i32 %indvar, 1 +; CHECK-NEXT: --> {1,+,1}<%bb> U: [1,1431655766) S: [1,1431655766) Exits: (1 + ((-5 + %x) /u 3)) LoopDispositions: { %bb: Computable } +; CHECK-NEXT: %lcssa = phi i32 [ %1, %bb1 ] +; CHECK-NEXT: --> {(-3 + %x),+,-3}<%bb> U: full-set S: full-set --> (-3 + (-3 * ((-5 + %x) /u 3)) + %x) U: full-set S: full-set +; CHECK-NEXT: %x_addr.0.lcssa = phi i32 [ %lcssa, %bb1.bb2_crit_edge ], [ %x, %entry ] +; CHECK-NEXT: --> %x_addr.0.lcssa U: full-set S: full-set +; CHECK-NEXT: Determining loop execution counts for: @f +; CHECK-NEXT: Loop %bb: backedge-taken count is ((-5 + %x) /u 3) +; CHECK-NEXT: Loop %bb: constant max backedge-taken count is 1431655764 +; CHECK-NEXT: Loop %bb: symbolic max backedge-taken count is ((-5 + %x) /u 3) +; CHECK-NEXT: Loop %bb: Predicated backedge-taken count is ((-5 + %x) /u 3) +; CHECK-NEXT: Predicates: +; CHECK: Loop %bb: Trip multiple is 1 +; entry: - %0 = icmp ugt i32 %x, 4 ; [#uses=1] - br i1 %0, label %bb.nph, label %bb2 + %0 = icmp ugt i32 %x, 4 ; [#uses=1] + br i1 %0, label %bb.nph, label %bb2 bb.nph: ; preds = %entry - br label %bb + br label %bb bb: ; preds = %bb.nph, %bb1 - %indvar = phi i32 [ 0, %bb.nph ], [ %indvar.next, %bb1 ] ; [#uses=2] - %tmp = mul i32 %indvar, -3 ; [#uses=1] - %x_addr.04 = add i32 %tmp, %x ; [#uses=1] - %1 = add i32 %x_addr.04, -3 ; [#uses=2] - br label %bb1 + %indvar = phi i32 [ 0, %bb.nph ], [ %indvar.next, %bb1 ] ; [#uses=2] + %tmp = mul i32 %indvar, -3 ; [#uses=1] + %x_addr.04 = add i32 %tmp, %x ; [#uses=1] + %1 = add i32 %x_addr.04, -3 ; [#uses=2] + br label %bb1 bb1: ; preds = %bb - %2 = icmp ugt i32 %1, 4 ; [#uses=1] - %indvar.next = add i32 %indvar, 1 ; [#uses=1] - br i1 %2, label %bb, label %bb1.bb2_crit_edge + %2 = icmp ugt i32 %1, 4 ; [#uses=1] + %indvar.next = add i32 %indvar, 1 ; [#uses=1] + br i1 %2, label %bb, label %bb1.bb2_crit_edge bb1.bb2_crit_edge: ; preds = %bb1 - %.lcssa = phi i32 [ %1, %bb1 ] ; [#uses=1] - br label %bb2 + %lcssa = phi i32 [ %1, %bb1 ] ; [#uses=1] + br label %bb2 bb2: ; preds = %bb1.bb2_crit_edge, %entry - %x_addr.0.lcssa = phi i32 [ %.lcssa, %bb1.bb2_crit_edge ], [ %x, %entry ] ; [#uses=1] - ret i32 %x_addr.0.lcssa + %x_addr.0.lcssa = phi i32 [ %lcssa, %bb1.bb2_crit_edge ], [ %x, %entry ] ; [#uses=1] + ret i32 %x_addr.0.lcssa } Index: llvm/test/Analysis/ScalarEvolution/2008-12-11-SMaxOverflow.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/2008-12-11-SMaxOverflow.ll +++ llvm/test/Analysis/ScalarEvolution/2008-12-11-SMaxOverflow.ll @@ -1,30 +1,47 @@ +; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 2 ; RUN: opt < %s -disable-output "-passes=print" 2>&1 | FileCheck %s -; CHECK: @f -; CHECK: Loop %bb16.preheader: backedge-taken count is (-1 + %c.idx.val) - define i32 @f(i32 %c.idx.val) { - +; CHECK-LABEL: 'f' +; CHECK-NEXT: Classifying expressions for: @f +; CHECK-NEXT: %k.018 = add i32 %c.idx.val, -1 +; CHECK-NEXT: --> (-1 + %c.idx.val) U: full-set S: full-set +; CHECK-NEXT: %k.019 = phi i32 [ %k.0, %bb18 ], [ %k.018, %bb2 ] +; CHECK-NEXT: --> {(-1 + %c.idx.val),+,-1}<%bb16.preheader> U: full-set S: full-set Exits: 0 LoopDispositions: { %bb16.preheader: Computable } +; CHECK-NEXT: %x = phi i32 [ 0, %bb2 ], [ %x.1, %bb18 ] +; CHECK-NEXT: --> {0,+,1}<%bb16.preheader> U: [0,-2147483647) S: [0,-2147483647) Exits: (-1 + %c.idx.val) LoopDispositions: { %bb16.preheader: Computable } +; CHECK-NEXT: %x.1 = add i32 %x, 1 +; CHECK-NEXT: --> {1,+,1}<%bb16.preheader> U: [1,-2147483646) S: [1,-2147483646) Exits: %c.idx.val LoopDispositions: { %bb16.preheader: Computable } +; CHECK-NEXT: %k.0 = add i32 %k.019, -1 +; CHECK-NEXT: --> {(-2 + %c.idx.val),+,-1}<%bb16.preheader> U: full-set S: full-set Exits: -1 LoopDispositions: { %bb16.preheader: Computable } +; CHECK-NEXT: Determining loop execution counts for: @f +; CHECK-NEXT: Loop %bb16.preheader: backedge-taken count is (-1 + %c.idx.val) +; CHECK-NEXT: Loop %bb16.preheader: constant max backedge-taken count is -2147483648 +; CHECK-NEXT: Loop %bb16.preheader: symbolic max backedge-taken count is (-1 + %c.idx.val) +; CHECK-NEXT: Loop %bb16.preheader: Predicated backedge-taken count is (-1 + %c.idx.val) +; CHECK-NEXT: Predicates: +; CHECK: Loop %bb16.preheader: Trip multiple is 1 +; bb2: - %k.018 = add i32 %c.idx.val, -1 ; [#uses=2] - %a14 = icmp slt i32 %k.018, 0 ; [#uses=1] - br i1 %a14, label %bb19, label %bb16.preheader + %k.018 = add i32 %c.idx.val, -1 ; [#uses=2] + %a14 = icmp slt i32 %k.018, 0 ; [#uses=1] + br i1 %a14, label %bb19, label %bb16.preheader bb16.preheader: - %k.019 = phi i32 [ %k.0, %bb18 ], [ %k.018, %bb2 ] ; [#uses=5] - %x = phi i32 [ 0, %bb2 ], [ %x.1, %bb18] - br label %bb18 + %k.019 = phi i32 [ %k.0, %bb18 ], [ %k.018, %bb2 ] ; [#uses=5] + %x = phi i32 [ 0, %bb2 ], [ %x.1, %bb18] + br label %bb18 bb18: ; preds = %bb18.loopexit - %x.1 = add i32 %x, 1 - %k.0 = add i32 %k.019, -1 ; [#uses=2] - %a107 = icmp slt i32 %k.0, 0 ; [#uses=1] - br i1 %a107, label %bb18.bb19_crit_edge, label %bb16.preheader + %x.1 = add i32 %x, 1 + %k.0 = add i32 %k.019, -1 ; [#uses=2] + %a107 = icmp slt i32 %k.0, 0 ; [#uses=1] + br i1 %a107, label %bb18.bb19_crit_edge, label %bb16.preheader bb18.bb19_crit_edge: - ret i32 %x + ret i32 %x bb19: - ret i32 0 + ret i32 0 } Index: llvm/test/Analysis/ScalarEvolution/trip-count12.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/trip-count12.ll +++ llvm/test/Analysis/ScalarEvolution/trip-count12.ll @@ -1,10 +1,37 @@ +; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 2 ; RUN: opt < %s -disable-output "-passes=print" 2>&1 | FileCheck %s -; CHECK: Determining loop execution counts for: @test -; CHECK: Loop %for.body: backedge-taken count is ((-2 + %len) /u 2) -; CHECK: Loop %for.body: constant max backedge-taken count is 1073741823 - define zeroext i16 @test(ptr nocapture %p, i32 %len) nounwind readonly { +; CHECK-LABEL: 'test' +; CHECK-NEXT: Classifying expressions for: @test +; CHECK-NEXT: %p.addr.05 = phi ptr [ %incdec.ptr, %for.body ], [ %p, %for.body.preheader ] +; CHECK-NEXT: --> {%p,+,2}<%for.body> U: full-set S: full-set Exits: ((2 * ((zext i32 (-2 + %len) to i64) /u 2)) + %p) LoopDispositions: { %for.body: Computable } +; CHECK-NEXT: %len.addr.04 = phi i32 [ %sub, %for.body ], [ %len, %for.body.preheader ] +; CHECK-NEXT: --> {%len,+,-2}<%for.body> U: full-set S: full-set Exits: ((-2 * ((-2 + %len) /u 2)) + %len) LoopDispositions: { %for.body: Computable } +; CHECK-NEXT: %res.03 = phi i32 [ %add, %for.body ], [ 0, %for.body.preheader ] +; CHECK-NEXT: --> %res.03 U: full-set S: full-set Exits: <> LoopDispositions: { %for.body: Variant } +; CHECK-NEXT: %incdec.ptr = getelementptr inbounds i16, ptr %p.addr.05, i32 1 +; CHECK-NEXT: --> {(2 + %p),+,2}<%for.body> U: full-set S: full-set Exits: (2 + (2 * ((zext i32 (-2 + %len) to i64) /u 2)) + %p) LoopDispositions: { %for.body: Computable } +; CHECK-NEXT: %0 = load i16, ptr %p.addr.05, align 2 +; CHECK-NEXT: --> %0 U: full-set S: full-set Exits: <> LoopDispositions: { %for.body: Variant } +; CHECK-NEXT: %conv = zext i16 %0 to i32 +; CHECK-NEXT: --> (zext i16 %0 to i32) U: [0,65536) S: [0,65536) Exits: <> LoopDispositions: { %for.body: Variant } +; CHECK-NEXT: %add = add i32 %conv, %res.03 +; CHECK-NEXT: --> ((zext i16 %0 to i32) + %res.03) U: full-set S: full-set Exits: <> LoopDispositions: { %for.body: Variant } +; CHECK-NEXT: %sub = add nsw i32 %len.addr.04, -2 +; CHECK-NEXT: --> {(-2 + %len),+,-2}<%for.body> U: full-set S: full-set Exits: (-2 + (-2 * ((-2 + %len) /u 2)) + %len) LoopDispositions: { %for.body: Computable } +; CHECK-NEXT: %extract.t = trunc i32 %add to i16 +; CHECK-NEXT: --> ((trunc i32 %res.03 to i16) + %0) U: full-set S: full-set +; CHECK-NEXT: %res.0.lcssa.off0 = phi i16 [ %extract.t, %for.cond.for.end_crit_edge ], [ 0, %entry ] +; CHECK-NEXT: --> %res.0.lcssa.off0 U: full-set S: full-set +; CHECK-NEXT: Determining loop execution counts for: @test +; CHECK-NEXT: Loop %for.body: backedge-taken count is ((-2 + %len) /u 2) +; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is 1073741823 +; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is ((-2 + %len) /u 2) +; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is ((-2 + %len) /u 2) +; CHECK-NEXT: Predicates: +; CHECK: Loop %for.body: Trip multiple is 1 +; entry: %cmp2 = icmp sgt i32 %len, 1 br i1 %cmp2, label %for.body.preheader, label %for.end