summaryrefslogtreecommitdiff
path: root/test/Analysis/ScalarEvolution
diff options
context:
space:
mode:
Diffstat (limited to 'test/Analysis/ScalarEvolution')
-rw-r--r--test/Analysis/ScalarEvolution/avoid-assume-hang.ll139
-rw-r--r--test/Analysis/ScalarEvolution/constant_condition.ll51
-rw-r--r--test/Analysis/ScalarEvolution/flags-from-poison.ll592
-rw-r--r--test/Analysis/ScalarEvolution/infer-prestart-no-wrap.ll10
-rw-r--r--test/Analysis/ScalarEvolution/min-max-exprs.ll2
-rw-r--r--test/Analysis/ScalarEvolution/no-wrap-add-exprs.ll122
-rw-r--r--test/Analysis/ScalarEvolution/non-IV-phi.ll59
-rw-r--r--test/Analysis/ScalarEvolution/pr24757.ll35
-rw-r--r--test/Analysis/ScalarEvolution/pr25369.ll78
-rw-r--r--test/Analysis/ScalarEvolution/scev-aa.ll2
-rw-r--r--test/Analysis/ScalarEvolution/shift-op.ll164
-rw-r--r--test/Analysis/ScalarEvolution/smax-br-phi-idioms.ll128
-rw-r--r--test/Analysis/ScalarEvolution/trip-count.ll5
-rw-r--r--test/Analysis/ScalarEvolution/zext-wrap.ll2
14 files changed, 1379 insertions, 10 deletions
diff --git a/test/Analysis/ScalarEvolution/avoid-assume-hang.ll b/test/Analysis/ScalarEvolution/avoid-assume-hang.ll
new file mode 100644
index 0000000000000..e2428ed1f73f7
--- /dev/null
+++ b/test/Analysis/ScalarEvolution/avoid-assume-hang.ll
@@ -0,0 +1,139 @@
+; RUN: opt %s -always-inline | opt -analyze -scalar-evolution
+; There was optimization bug in ScalarEvolution, that causes too long
+; compute time and stack overflow crash.
+
+declare void @body(i32)
+declare void @llvm.assume(i1)
+
+define available_externally void @assume1(i64 %i.ext, i64 %a) alwaysinline {
+ %cmp0 = icmp ne i64 %i.ext, %a
+ call void @llvm.assume(i1 %cmp0)
+
+ %a1 = add i64 %a, 1
+ %cmp1 = icmp ne i64 %i.ext, %a1
+ call void @llvm.assume(i1 %cmp1)
+
+ %a2 = add i64 %a1, 1
+ %cmp2 = icmp ne i64 %i.ext, %a2
+ call void @llvm.assume(i1 %cmp2)
+
+ %a3 = add i64 %a2, 1
+ %cmp3 = icmp ne i64 %i.ext, %a3
+ call void @llvm.assume(i1 %cmp3)
+
+ %a4 = add i64 %a3, 1
+ %cmp4 = icmp ne i64 %i.ext, %a4
+ call void @llvm.assume(i1 %cmp4)
+
+ ret void
+}
+
+define available_externally void @assume2(i64 %i.ext, i64 %a) alwaysinline {
+ call void @assume1(i64 %i.ext, i64 %a)
+
+ %a1 = add i64 %a, 5
+ %cmp1 = icmp ne i64 %i.ext, %a1
+ call void @assume1(i64 %i.ext, i64 %a1)
+
+ %a2 = add i64 %a1, 5
+ %cmp2 = icmp ne i64 %i.ext, %a2
+ call void @assume1(i64 %i.ext, i64 %a2)
+
+ %a3 = add i64 %a2, 5
+ %cmp3 = icmp ne i64 %i.ext, %a3
+ call void @assume1(i64 %i.ext, i64 %a3)
+
+ %a4 = add i64 %a3, 5
+ %cmp4 = icmp ne i64 %i.ext, %a4
+ call void @assume1(i64 %i.ext, i64 %a4)
+
+ ret void
+}
+
+define available_externally void @assume3(i64 %i.ext, i64 %a) alwaysinline {
+ call void @assume2(i64 %i.ext, i64 %a)
+
+ %a1 = add i64 %a, 25
+ %cmp1 = icmp ne i64 %i.ext, %a1
+ call void @assume2(i64 %i.ext, i64 %a1)
+
+ %a2 = add i64 %a1, 25
+ %cmp2 = icmp ne i64 %i.ext, %a2
+ call void @assume2(i64 %i.ext, i64 %a2)
+
+ %a3 = add i64 %a2, 25
+ %cmp3 = icmp ne i64 %i.ext, %a3
+ call void @assume2(i64 %i.ext, i64 %a3)
+
+ %a4 = add i64 %a3, 25
+ %cmp4 = icmp ne i64 %i.ext, %a4
+ call void @assume2(i64 %i.ext, i64 %a4)
+
+ ret void
+}
+
+define available_externally void @assume4(i64 %i.ext, i64 %a) alwaysinline {
+ call void @assume3(i64 %i.ext, i64 %a)
+
+ %a1 = add i64 %a, 125
+ %cmp1 = icmp ne i64 %i.ext, %a1
+ call void @assume3(i64 %i.ext, i64 %a1)
+
+ %a2 = add i64 %a1, 125
+ %cmp2 = icmp ne i64 %i.ext, %a2
+ call void @assume3(i64 %i.ext, i64 %a2)
+
+ %a3 = add i64 %a2, 125
+ %cmp3 = icmp ne i64 %i.ext, %a3
+ call void @assume3(i64 %i.ext, i64 %a3)
+
+ %a4 = add i64 %a3, 125
+ %cmp4 = icmp ne i64 %i.ext, %a4
+ call void @assume3(i64 %i.ext, i64 %a4)
+
+ ret void
+}
+
+define available_externally void @assume5(i64 %i.ext, i64 %a) alwaysinline {
+ call void @assume4(i64 %i.ext, i64 %a)
+
+ %a1 = add i64 %a, 625
+ %cmp1 = icmp ne i64 %i.ext, %a1
+ call void @assume4(i64 %i.ext, i64 %a1)
+
+ %a2 = add i64 %a1, 625
+ %cmp2 = icmp ne i64 %i.ext, %a2
+ call void @assume4(i64 %i.ext, i64 %a2)
+
+ %a3 = add i64 %a2, 625
+ %cmp3 = icmp ne i64 %i.ext, %a3
+ call void @assume4(i64 %i.ext, i64 %a3)
+
+ %a4 = add i64 %a3, 625
+ %cmp4 = icmp ne i64 %i.ext, %a4
+ call void @assume4(i64 %i.ext, i64 %a4)
+
+ ret void
+}
+
+define void @fn(i32 %init) {
+entry:
+ br label %loop
+
+loop:
+ %i = phi i32 [%init, %entry], [%next, %loop]
+ call void @body(i32 %i)
+
+ %i.ext = zext i32 %i to i64
+
+ call void @assume5(i64 %i.ext, i64 500000000)
+
+ %i.next = add i64 %i.ext, 1
+ %next = trunc i64 %i.next to i32
+ %done = icmp eq i32 %i, 500000000
+
+ br i1 %done, label %exit, label %loop
+
+exit:
+ ret void
+} \ No newline at end of file
diff --git a/test/Analysis/ScalarEvolution/constant_condition.ll b/test/Analysis/ScalarEvolution/constant_condition.ll
new file mode 100644
index 0000000000000..32ab91b2c857b
--- /dev/null
+++ b/test/Analysis/ScalarEvolution/constant_condition.ll
@@ -0,0 +1,51 @@
+; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
+
+define i32 @branch_true(i32 %x, i32 %y) {
+; CHECK-LABEL: Classifying expressions for: @branch_true
+ entry:
+ br i1 true, label %add, label %merge
+
+ add:
+ %sum = add i32 %x, %y
+ br label %merge
+
+ merge:
+ %v = phi i32 [ %sum, %add ], [ %x, %entry ]
+; CHECK: %v = phi i32 [ %sum, %add ], [ %x, %entry ]
+; CHECK-NEXT: --> (%x + %y) U: full-set S: full-set
+ ret i32 %v
+}
+
+define i32 @branch_false(i32 %x, i32 %y) {
+; CHECK-LABEL: Classifying expressions for: @branch_false
+ entry:
+ br i1 false, label %add, label %merge
+
+ add:
+ %sum = add i32 %x, %y
+ br label %merge
+
+ merge:
+ %v = phi i32 [ %sum, %add ], [ %x, %entry ]
+; CHECK: %v = phi i32 [ %sum, %add ], [ %x, %entry ]
+; CHECK-NEXT: --> %x U: full-set S: full-set
+ ret i32 %v
+}
+
+define i32 @select_true(i32 %x, i32 %y) {
+; CHECK-LABEL: Classifying expressions for: @select_true
+ entry:
+ %v = select i1 true, i32 %x, i32 %y
+; CHECK: %v = select i1 true, i32 %x, i32 %y
+; CHECK-NEXT: --> %x U: full-set S: full-set
+ ret i32 %v
+}
+
+define i32 @select_false(i32 %x, i32 %y) {
+; CHECK-LABEL: Classifying expressions for: @select_false
+ entry:
+ %v = select i1 false, i32 %x, i32 %y
+; CHECK: %v = select i1 false, i32 %x, i32 %y
+; CHECK-NEXT: --> %y U: full-set S: full-set
+ ret i32 %v
+}
diff --git a/test/Analysis/ScalarEvolution/flags-from-poison.ll b/test/Analysis/ScalarEvolution/flags-from-poison.ll
new file mode 100644
index 0000000000000..b1fe7f1138b6c
--- /dev/null
+++ b/test/Analysis/ScalarEvolution/flags-from-poison.ll
@@ -0,0 +1,592 @@
+; RUN: opt < %s -S -analyze -scalar-evolution | FileCheck %s
+
+; Positive and negative tests for inferring flags like nsw from
+; reasoning about how a poison value from overflow would trigger
+; undefined behavior.
+
+define void @foo() {
+ ret void
+}
+
+; Example where an add should get the nsw flag, so that a sext can be
+; distributed over the add.
+define void @test-add-nsw(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-nsw
+entry:
+ br label %loop
+loop:
+ %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nsw>
+ %index32 = add nsw i32 %i, %offset
+
+; CHECK: %index64 =
+; CHECK: --> {(sext i32 %offset to i64),+,1}<nsw>
+ %index64 = sext i32 %index32 to i64
+
+ %ptr = getelementptr inbounds float, float* %input, i64 %index64
+ %nexti = add nsw i32 %i, 1
+ %f = load float, float* %ptr, align 4
+ call void @foo()
+ %exitcond = icmp eq i32 %nexti, %numIterations
+ br i1 %exitcond, label %exit, label %loop
+exit:
+ ret void
+}
+
+; Example where an add should get the nuw flag.
+define void @test-add-nuw(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-nuw
+entry:
+ br label %loop
+loop:
+ %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nuw>
+ %index32 = add nuw i32 %i, %offset
+
+ %ptr = getelementptr inbounds float, float* %input, i32 %index32
+ %nexti = add nuw i32 %i, 1
+ %f = load float, float* %ptr, align 4
+ %exitcond = icmp eq i32 %nexti, %numIterations
+ br i1 %exitcond, label %exit, label %loop
+
+exit:
+ ret void
+}
+
+; With no load to trigger UB from poison, we cannot infer nsw.
+define void @test-add-no-load(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-no-load
+entry:
+ br label %loop
+loop:
+ %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nw>
+ %index32 = add nsw i32 %i, %offset
+
+ %ptr = getelementptr inbounds float, float* %input, i32 %index32
+ %nexti = add nuw i32 %i, 1
+ %exitcond = icmp eq i32 %nexti, %numIterations
+ br i1 %exitcond, label %exit, label %loop
+
+exit:
+ ret void
+}
+
+; The current code is only supposed to look at the loop header, so
+; it should not infer nsw in this case, as that would require looking
+; outside the loop header.
+define void @test-add-not-header(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-not-header
+entry:
+ br label %loop
+loop:
+ %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
+ br label %loop2
+loop2:
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nw>
+ %index32 = add nsw i32 %i, %offset
+
+ %ptr = getelementptr inbounds float, float* %input, i32 %index32
+ %nexti = add nsw i32 %i, 1
+ %f = load float, float* %ptr, align 4
+ %exitcond = icmp eq i32 %nexti, %numIterations
+ br i1 %exitcond, label %exit, label %loop
+exit:
+ ret void
+}
+
+; Same thing as test-add-not-header, but in this case only the load
+; instruction is outside the loop header.
+define void @test-add-not-header2(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-not-header2
+entry:
+ br label %loop
+loop:
+ %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nw>
+ %index32 = add nsw i32 %i, %offset
+
+ %ptr = getelementptr inbounds float, float* %input, i32 %index32
+ %nexti = add nsw i32 %i, 1
+ br label %loop2
+loop2:
+ %f = load float, float* %ptr, align 4
+ %exitcond = icmp eq i32 %nexti, %numIterations
+ br i1 %exitcond, label %exit, label %loop
+exit:
+ ret void
+}
+
+; The call instruction makes it not guaranteed that the add will be
+; executed, since it could run forever or throw an exception, so we
+; cannot assume that the UB is realized.
+define void @test-add-call(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-call
+entry:
+ br label %loop
+loop:
+ %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nw>
+ call void @foo()
+ %index32 = add nsw i32 %i, %offset
+
+ %ptr = getelementptr inbounds float, float* %input, i32 %index32
+ %nexti = add nsw i32 %i, 1
+ %f = load float, float* %ptr, align 4
+ %exitcond = icmp eq i32 %nexti, %numIterations
+ br i1 %exitcond, label %exit, label %loop
+exit:
+ ret void
+}
+
+; Same issue as test-add-call, but this time the call is between the
+; producer of poison and the load that consumes it.
+define void @test-add-call2(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-call2
+entry:
+ br label %loop
+loop:
+ %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nw>
+ %index32 = add nsw i32 %i, %offset
+
+ %ptr = getelementptr inbounds float, float* %input, i32 %index32
+ %nexti = add nsw i32 %i, 1
+ call void @foo()
+ %f = load float, float* %ptr, align 4
+ %exitcond = icmp eq i32 %nexti, %numIterations
+ br i1 %exitcond, label %exit, label %loop
+exit:
+ ret void
+}
+
+; Without inbounds, GEP does not propagate poison in the very
+; conservative approach used here.
+define void @test-add-no-inbounds(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-no-inbounds
+entry:
+ br label %loop
+loop:
+ %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nw>
+ %index32 = add nsw i32 %i, %offset
+
+ %ptr = getelementptr float, float* %input, i32 %index32
+ %nexti = add nsw i32 %i, 1
+ %f = load float, float* %ptr, align 4
+ %exitcond = icmp eq i32 %nexti, %numIterations
+ br i1 %exitcond, label %exit, label %loop
+exit:
+ ret void
+}
+
+; Multiplication by a non-zero constant propagates poison if there is
+; a nuw or nsw flag on the multiplication.
+define void @test-add-mul-propagates(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-mul-propagates
+entry:
+ br label %loop
+loop:
+ %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nsw>
+ %index32 = add nsw i32 %i, %offset
+
+ %indexmul = mul nuw i32 %index32, 2
+ %ptr = getelementptr inbounds float, float* %input, i32 %indexmul
+ %nexti = add nsw i32 %i, 1
+ %f = load float, float* %ptr, align 4
+ %exitcond = icmp eq i32 %nexti, %numIterations
+ br i1 %exitcond, label %exit, label %loop
+exit:
+ ret void
+}
+
+; Multiplication by a non-constant should not propagate poison in the
+; very conservative approach used here.
+define void @test-add-mul-no-propagation(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-mul-no-propagation
+entry:
+ br label %loop
+loop:
+ %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nw>
+ %index32 = add nsw i32 %i, %offset
+
+ %indexmul = mul nsw i32 %index32, %offset
+ %ptr = getelementptr inbounds float, float* %input, i32 %indexmul
+ %nexti = add nsw i32 %i, 1
+ %f = load float, float* %ptr, align 4
+ %exitcond = icmp eq i32 %nexti, %numIterations
+ br i1 %exitcond, label %exit, label %loop
+exit:
+ ret void
+}
+
+; Multiplication by a non-zero constant does not propagate poison
+; without a no-wrap flag.
+define void @test-add-mul-no-propagation2(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-mul-no-propagation2
+entry:
+ br label %loop
+loop:
+ %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nw>
+ %index32 = add nsw i32 %i, %offset
+
+ %indexmul = mul i32 %index32, 2
+ %ptr = getelementptr inbounds float, float* %input, i32 %indexmul
+ %nexti = add nsw i32 %i, 1
+ %f = load float, float* %ptr, align 4
+ %exitcond = icmp eq i32 %nexti, %numIterations
+ br i1 %exitcond, label %exit, label %loop
+exit:
+ ret void
+}
+
+; Division by poison triggers UB.
+define void @test-add-div(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-div
+entry:
+ br label %loop
+loop:
+ %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %j =
+; CHECK: --> {%offset,+,1}<nsw>
+ %j = add nsw i32 %i, %offset
+
+ %q = sdiv i32 %numIterations, %j
+ %nexti = add nsw i32 %i, 1
+ %exitcond = icmp eq i32 %nexti, %numIterations
+ br i1 %exitcond, label %exit, label %loop
+exit:
+ ret void
+}
+
+; Remainder of poison by non-poison divisor does not trigger UB.
+define void @test-add-div2(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-div2
+entry:
+ br label %loop
+loop:
+ %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %j =
+; CHECK: --> {%offset,+,1}<nw>
+ %j = add nsw i32 %i, %offset
+
+ %q = sdiv i32 %j, %numIterations
+ %nexti = add nsw i32 %i, 1
+ %exitcond = icmp eq i32 %nexti, %numIterations
+ br i1 %exitcond, label %exit, label %loop
+exit:
+ ret void
+}
+
+; Store to poison address triggers UB.
+define void @test-add-store(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-store
+entry:
+ br label %loop
+loop:
+ %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nsw>
+ %index32 = add nsw i32 %i, %offset
+
+ %ptr = getelementptr inbounds float, float* %input, i32 %index32
+ %nexti = add nsw i32 %i, 1
+ store float 1.0, float* %ptr, align 4
+ %exitcond = icmp eq i32 %nexti, %numIterations
+ br i1 %exitcond, label %exit, label %loop
+exit:
+ ret void
+}
+
+; Three sequential adds where the middle add should have nsw. There is
+; a special case for sequential adds and this test covers that. We have to
+; put the final add first in the program since otherwise the special case
+; is not triggered, hence the strange basic block ordering.
+define void @test-add-twice(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-twice
+entry:
+ br label %loop
+loop2:
+; CHECK: %seq =
+; CHECK: --> {(2 + %offset),+,1}<nw>
+ %seq = add nsw nuw i32 %index32, 1
+ %exitcond = icmp eq i32 %nexti, %numIterations
+ br i1 %exitcond, label %exit, label %loop
+
+loop:
+ %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
+
+ %j = add nsw i32 %i, 1
+; CHECK: %index32 =
+; CHECK: --> {(1 + %offset),+,1}<nsw>
+ %index32 = add nsw i32 %j, %offset
+
+ %ptr = getelementptr inbounds float, float* %input, i32 %index32
+ %nexti = add nsw i32 %i, 1
+ store float 1.0, float* %ptr, align 4
+ br label %loop2
+exit:
+ ret void
+}
+
+; Example where a mul should get the nsw flag, so that a sext can be
+; distributed over the mul.
+define void @test-mul-nsw(float* %input, i32 %stride, i32 %numIterations) {
+; CHECK-LABEL: @test-mul-nsw
+entry:
+ br label %loop
+loop:
+ %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {0,+,%stride}<nsw>
+ %index32 = mul nsw i32 %i, %stride
+
+; CHECK: %index64 =
+; CHECK: --> {0,+,(sext i32 %stride to i64)}<nsw>
+ %index64 = sext i32 %index32 to i64
+
+ %ptr = getelementptr inbounds float, float* %input, i64 %index64
+ %nexti = add nsw i32 %i, 1
+ %f = load float, float* %ptr, align 4
+ %exitcond = icmp eq i32 %nexti, %numIterations
+ br i1 %exitcond, label %exit, label %loop
+exit:
+ ret void
+}
+
+; Example where a mul should get the nuw flag.
+define void @test-mul-nuw(float* %input, i32 %stride, i32 %numIterations) {
+; CHECK-LABEL: @test-mul-nuw
+entry:
+ br label %loop
+loop:
+ %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {0,+,%stride}<nuw>
+ %index32 = mul nuw i32 %i, %stride
+
+ %ptr = getelementptr inbounds float, float* %input, i32 %index32
+ %nexti = add nuw i32 %i, 1
+ %f = load float, float* %ptr, align 4
+ %exitcond = icmp eq i32 %nexti, %numIterations
+ br i1 %exitcond, label %exit, label %loop
+
+exit:
+ ret void
+}
+
+; Example where a shl should get the nsw flag, so that a sext can be
+; distributed over the shl.
+define void @test-shl-nsw(float* %input, i32 %start, i32 %numIterations) {
+; CHECK-LABEL: @test-shl-nsw
+entry:
+ br label %loop
+loop:
+ %i = phi i32 [ %nexti, %loop ], [ %start, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {(256 * %start),+,256}<nsw>
+ %index32 = shl nsw i32 %i, 8
+
+; CHECK: %index64 =
+; CHECK: --> {(sext i32 (256 * %start) to i64),+,256}<nsw>
+ %index64 = sext i32 %index32 to i64
+
+ %ptr = getelementptr inbounds float, float* %input, i64 %index64
+ %nexti = add nsw i32 %i, 1
+ %f = load float, float* %ptr, align 4
+ %exitcond = icmp eq i32 %nexti, %numIterations
+ br i1 %exitcond, label %exit, label %loop
+exit:
+ ret void
+}
+
+; Example where a shl should get the nuw flag.
+define void @test-shl-nuw(float* %input, i32 %numIterations) {
+; CHECK-LABEL: @test-shl-nuw
+entry:
+ br label %loop
+loop:
+ %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {0,+,512}<nuw>
+ %index32 = shl nuw i32 %i, 9
+
+ %ptr = getelementptr inbounds float, float* %input, i32 %index32
+ %nexti = add nuw i32 %i, 1
+ %f = load float, float* %ptr, align 4
+ %exitcond = icmp eq i32 %nexti, %numIterations
+ br i1 %exitcond, label %exit, label %loop
+
+exit:
+ ret void
+}
+
+; Example where a sub should *not* get the nsw flag, because of how
+; scalar evolution represents A - B as A + (-B) and -B can wrap even
+; in cases where A - B does not.
+define void @test-sub-no-nsw(float* %input, i32 %start, i32 %sub, i32 %numIterations) {
+; CHECK-LABEL: @test-sub-no-nsw
+entry:
+ br label %loop
+loop:
+ %i = phi i32 [ %nexti, %loop ], [ %start, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {((-1 * %sub) + %start),+,1}<nw>
+ %index32 = sub nsw i32 %i, %sub
+ %index64 = sext i32 %index32 to i64
+
+ %ptr = getelementptr inbounds float, float* %input, i64 %index64
+ %nexti = add nsw i32 %i, 1
+ %f = load float, float* %ptr, align 4
+ %exitcond = icmp eq i32 %nexti, %numIterations
+ br i1 %exitcond, label %exit, label %loop
+exit:
+ ret void
+}
+
+; Example where a sub should get the nsw flag as the RHS cannot be the
+; minimal signed value.
+define void @test-sub-nsw(float* %input, i32 %start, i32 %sub, i32 %numIterations) {
+; CHECK-LABEL: @test-sub-nsw
+entry:
+ %halfsub = ashr i32 %sub, 1
+ br label %loop
+loop:
+ %i = phi i32 [ %nexti, %loop ], [ %start, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {((-1 * %halfsub)<nsw> + %start),+,1}<nsw>
+ %index32 = sub nsw i32 %i, %halfsub
+ %index64 = sext i32 %index32 to i64
+
+ %ptr = getelementptr inbounds float, float* %input, i64 %index64
+ %nexti = add nsw i32 %i, 1
+ %f = load float, float* %ptr, align 4
+ %exitcond = icmp eq i32 %nexti, %numIterations
+ br i1 %exitcond, label %exit, label %loop
+exit:
+ ret void
+}
+
+; Example where a sub should get the nsw flag, since the LHS is non-negative,
+; which implies that the RHS cannot be the minimal signed value.
+define void @test-sub-nsw-lhs-non-negative(float* %input, i32 %sub, i32 %numIterations) {
+; CHECK-LABEL: @test-sub-nsw-lhs-non-negative
+entry:
+ br label %loop
+loop:
+ %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {(-1 * %sub),+,1}<nsw>
+ %index32 = sub nsw i32 %i, %sub
+
+; CHECK: %index64 =
+; CHECK: --> {(sext i32 (-1 * %sub) to i64),+,1}<nsw>
+ %index64 = sext i32 %index32 to i64
+
+ %ptr = getelementptr inbounds float, float* %input, i64 %index64
+ %nexti = add nsw i32 %i, 1
+ %f = load float, float* %ptr, align 4
+ %exitcond = icmp eq i32 %nexti, %numIterations
+ br i1 %exitcond, label %exit, label %loop
+exit:
+ ret void
+}
+
+; Two adds with a sub in the middle and the sub should have nsw. There is
+; a special case for sequential adds/subs and this test covers that. We have to
+; put the final add first in the program since otherwise the special case
+; is not triggered, hence the strange basic block ordering.
+define void @test-sub-with-add(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-sub-with-add
+entry:
+ br label %loop
+loop2:
+; CHECK: %seq =
+; CHECK: --> {(2 + (-1 * %offset)),+,1}<nw>
+ %seq = add nsw nuw i32 %index32, 1
+ %exitcond = icmp eq i32 %nexti, %numIterations
+ br i1 %exitcond, label %exit, label %loop
+
+loop:
+ %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
+
+ %j = add nsw i32 %i, 1
+; CHECK: %index32 =
+; CHECK: --> {(1 + (-1 * %offset)),+,1}<nsw>
+ %index32 = sub nsw i32 %j, %offset
+
+ %ptr = getelementptr inbounds float, float* %input, i32 %index32
+ %nexti = add nsw i32 %i, 1
+ store float 1.0, float* %ptr, align 4
+ br label %loop2
+exit:
+ ret void
+}
+
+
+; Subtraction of two recurrences. The addition in the SCEV that this
+; maps to is NSW, but the negation of the RHS does not since that
+; recurrence could be the most negative representable value.
+define void @subrecurrences(i32 %outer_l, i32 %inner_l, i32 %val) {
+; CHECK-LABEL: @subrecurrences
+ entry:
+ br label %outer
+
+outer:
+ %o_idx = phi i32 [ 0, %entry ], [ %o_idx.inc, %outer.be ]
+ %o_idx.inc = add nsw i32 %o_idx, 1
+ %cond = icmp eq i32 %o_idx, %val
+ br i1 %cond, label %inner, label %outer.be
+
+inner:
+ %i_idx = phi i32 [ 0, %outer ], [ %i_idx.inc, %inner ]
+ %i_idx.inc = add nsw i32 %i_idx, 1
+; CHECK: %v =
+; CHECK-NEXT: --> {{[{][{]}}-1,+,-1}<nw><%outer>,+,1}<nsw><%inner>
+ %v = sub nsw i32 %i_idx, %o_idx.inc
+ %forub = udiv i32 1, %v
+ %cond2 = icmp eq i32 %i_idx, %inner_l
+ br i1 %cond2, label %outer.be, label %inner
+
+outer.be:
+ %cond3 = icmp eq i32 %o_idx, %outer_l
+ br i1 %cond3, label %exit, label %outer
+
+exit:
+ ret void
+}
diff --git a/test/Analysis/ScalarEvolution/infer-prestart-no-wrap.ll b/test/Analysis/ScalarEvolution/infer-prestart-no-wrap.ll
index 078ca03ff14e1..5c372b5d7b8a1 100644
--- a/test/Analysis/ScalarEvolution/infer-prestart-no-wrap.ll
+++ b/test/Analysis/ScalarEvolution/infer-prestart-no-wrap.ll
@@ -11,7 +11,7 @@ define void @infer.sext.0(i1* %c, i32 %start) {
%idx.inc = add nsw i32 %idx, 1
%idx.inc.sext = sext i32 %idx.inc to i64
; CHECK: %idx.inc.sext = sext i32 %idx.inc to i64
-; CHECK-NEXT: --> {(1 + (sext i32 %start to i64)),+,1}<nsw><%loop>
+; CHECK-NEXT: --> {(1 + (sext i32 %start to i64))<nsw>,+,1}<nsw><%loop>
%condition = icmp eq i32 %counter, 1
%counter.inc = add i32 %counter, 1
br i1 %condition, label %exit, label %loop
@@ -31,7 +31,7 @@ define void @infer.zext.0(i1* %c, i32 %start) {
%idx.inc = add nuw i32 %idx, 1
%idx.inc.sext = zext i32 %idx.inc to i64
; CHECK: %idx.inc.sext = zext i32 %idx.inc to i64
-; CHECK-NEXT: --> {(1 + (zext i32 %start to i64)),+,1}<nuw><%loop>
+; CHECK-NEXT: --> {(1 + (zext i32 %start to i64))<nuw><nsw>,+,1}<nuw><%loop>
%condition = icmp eq i32 %counter, 1
%counter.inc = add i32 %counter, 1
br i1 %condition, label %exit, label %loop
@@ -51,7 +51,7 @@ define void @infer.sext.1(i32 %start, i1* %c) {
%idx = phi i32 [ %start.real, %entry ], [ %idx.inc, %loop ]
%idx.sext = sext i32 %idx to i64
; CHECK: %idx.sext = sext i32 %idx to i64
-; CHECK-NEXT: --> {(2 + (sext i32 (4 * %start) to i64)),+,2}<nsw><%loop>
+; CHECK-NEXT: --> {(2 + (sext i32 (4 * %start) to i64))<nsw>,+,2}<nsw><%loop>
%idx.inc = add nsw i32 %idx, 2
%condition = load i1, i1* %c
br i1 %condition, label %exit, label %loop
@@ -71,7 +71,7 @@ define void @infer.sext.2(i1* %c, i8 %start) {
%idx = phi i8 [ %start.inc, %entry ], [ %idx.inc, %loop ]
%idx.sext = sext i8 %idx to i16
; CHECK: %idx.sext = sext i8 %idx to i16
-; CHECK-NEXT: --> {(1 + (sext i8 %start to i16)),+,1}<nsw><%loop>
+; CHECK-NEXT: --> {(1 + (sext i8 %start to i16))<nsw>,+,1}<nsw><%loop>
%idx.inc = add nsw i8 %idx, 1
%condition = load volatile i1, i1* %c
br i1 %condition, label %exit, label %loop
@@ -91,7 +91,7 @@ define void @infer.zext.1(i1* %c, i8 %start) {
%idx = phi i8 [ %start.inc, %entry ], [ %idx.inc, %loop ]
%idx.zext = zext i8 %idx to i16
; CHECK: %idx.zext = zext i8 %idx to i16
-; CHECK-NEXT: --> {(1 + (zext i8 %start to i16)),+,1}<nuw><%loop>
+; CHECK-NEXT: --> {(1 + (zext i8 %start to i16))<nuw><nsw>,+,1}<nuw><%loop>
%idx.inc = add nuw i8 %idx, 1
%condition = load volatile i1, i1* %c
br i1 %condition, label %exit, label %loop
diff --git a/test/Analysis/ScalarEvolution/min-max-exprs.ll b/test/Analysis/ScalarEvolution/min-max-exprs.ll
index 892fc23fe6b2e..e8c1e33e095f8 100644
--- a/test/Analysis/ScalarEvolution/min-max-exprs.ll
+++ b/test/Analysis/ScalarEvolution/min-max-exprs.ll
@@ -33,7 +33,7 @@ bb2: ; preds = %bb1
%tmp9 = select i1 %tmp4, i64 %tmp5, i64 %tmp6
; min(N, i+3)
; CHECK: select i1 %tmp4, i64 %tmp5, i64 %tmp6
-; CHECK-NEXT: --> (-1 + (-1 * ((-1 + (-1 * (sext i32 {3,+,1}<nw><%bb1> to i64))) smax (-1 + (-1 * (sext i32 %N to i64))))))
+; CHECK-NEXT: --> (-1 + (-1 * ((-1 + (-1 * (sext i32 {3,+,1}<nuw><%bb1> to i64))<nsw>)<nsw> smax (-1 + (-1 * (sext i32 %N to i64))<nsw>)<nsw>))<nsw>)<nsw>
%tmp11 = getelementptr inbounds i32, i32* %A, i64 %tmp9
%tmp12 = load i32, i32* %tmp11, align 4
%tmp13 = shl nsw i32 %tmp12, 1
diff --git a/test/Analysis/ScalarEvolution/no-wrap-add-exprs.ll b/test/Analysis/ScalarEvolution/no-wrap-add-exprs.ll
new file mode 100644
index 0000000000000..c24d7173e4ee5
--- /dev/null
+++ b/test/Analysis/ScalarEvolution/no-wrap-add-exprs.ll
@@ -0,0 +1,122 @@
+; RUN: opt -S -analyze -scalar-evolution < %s | FileCheck %s
+
+!0 = !{i8 0, i8 127}
+
+define void @f0(i8* %len_addr) {
+; CHECK-LABEL: Classifying expressions for: @f0
+ entry:
+ %len = load i8, i8* %len_addr, !range !0
+ %len_norange = load i8, i8* %len_addr
+; CHECK: %len = load i8, i8* %len_addr, !range !0
+; CHECK-NEXT: --> %len U: [0,127) S: [0,127)
+; CHECK: %len_norange = load i8, i8* %len_addr
+; CHECK-NEXT: --> %len_norange U: full-set S: full-set
+
+ %t0 = add i8 %len, 1
+ %t1 = add i8 %len, 2
+; CHECK: %t0 = add i8 %len, 1
+; CHECK-NEXT: --> (1 + %len)<nuw><nsw> U: [1,-128) S: [1,-128)
+; CHECK: %t1 = add i8 %len, 2
+; CHECK-NEXT: --> (2 + %len)<nuw> U: [2,-127) S: [2,-127)
+
+ %t2 = sub i8 %len, 1
+ %t3 = sub i8 %len, 2
+; CHECK: %t2 = sub i8 %len, 1
+; CHECK-NEXT: --> (-1 + %len)<nsw> U: [-1,126) S: [-1,126)
+; CHECK: %t3 = sub i8 %len, 2
+; CHECK-NEXT: --> (-2 + %len)<nsw> U: [-2,125) S: [-2,125)
+
+ %q0 = add i8 %len_norange, 1
+ %q1 = add i8 %len_norange, 2
+; CHECK: %q0 = add i8 %len_norange, 1
+; CHECK-NEXT: --> (1 + %len_norange) U: full-set S: full-set
+; CHECK: %q1 = add i8 %len_norange, 2
+; CHECK-NEXT: --> (2 + %len_norange) U: full-set S: full-set
+
+ %q2 = sub i8 %len_norange, 1
+ %q3 = sub i8 %len_norange, 2
+; CHECK: %q2 = sub i8 %len_norange, 1
+; CHECK-NEXT: --> (-1 + %len_norange) U: full-set S: full-set
+; CHECK: %q3 = sub i8 %len_norange, 2
+; CHECK-NEXT: --> (-2 + %len_norange) U: full-set S: full-set
+
+ ret void
+}
+
+define void @f1(i8* %len_addr) {
+; CHECK-LABEL: Classifying expressions for: @f1
+ entry:
+ %len = load i8, i8* %len_addr, !range !0
+ %len_norange = load i8, i8* %len_addr
+; CHECK: %len = load i8, i8* %len_addr, !range !0
+; CHECK-NEXT: --> %len U: [0,127) S: [0,127)
+; CHECK: %len_norange = load i8, i8* %len_addr
+; CHECK-NEXT: --> %len_norange U: full-set S: full-set
+
+ %t0 = add i8 %len, -1
+ %t1 = add i8 %len, -2
+; CHECK: %t0 = add i8 %len, -1
+; CHECK-NEXT: --> (-1 + %len)<nsw> U: [-1,126) S: [-1,126)
+; CHECK: %t1 = add i8 %len, -2
+; CHECK-NEXT: --> (-2 + %len)<nsw> U: [-2,125) S: [-2,125)
+
+ %t0.sext = sext i8 %t0 to i16
+ %t1.sext = sext i8 %t1 to i16
+; CHECK: %t0.sext = sext i8 %t0 to i16
+; CHECK-NEXT: --> (-1 + (zext i8 %len to i16))<nsw> U: [-1,126) S: [-1,126)
+; CHECK: %t1.sext = sext i8 %t1 to i16
+; CHECK-NEXT: --> (-2 + (zext i8 %len to i16))<nsw> U: [-2,125) S: [-2,125)
+
+ %q0 = add i8 %len_norange, 1
+ %q1 = add i8 %len_norange, 2
+; CHECK: %q0 = add i8 %len_norange, 1
+; CHECK-NEXT: --> (1 + %len_norange) U: full-set S: full-set
+; CHECK: %q1 = add i8 %len_norange, 2
+; CHECK-NEXT: --> (2 + %len_norange) U: full-set S: full-set
+
+ %q0.sext = sext i8 %q0 to i16
+ %q1.sext = sext i8 %q1 to i16
+; CHECK: %q0.sext = sext i8 %q0 to i16
+; CHECK-NEXT: --> (sext i8 (1 + %len_norange) to i16) U: [-128,128) S: [-128,128)
+; CHECK: %q1.sext = sext i8 %q1 to i16
+; CHECK-NEXT: --> (sext i8 (2 + %len_norange) to i16) U: [-128,128) S: [-128,128)
+
+ ret void
+}
+
+define void @f2(i8* %len_addr) {
+; CHECK-LABEL: Classifying expressions for: @f2
+ entry:
+ %len = load i8, i8* %len_addr, !range !0
+ %len_norange = load i8, i8* %len_addr
+; CHECK: %len = load i8, i8* %len_addr, !range !0
+; CHECK-NEXT: --> %len U: [0,127) S: [0,127)
+; CHECK: %len_norange = load i8, i8* %len_addr
+; CHECK-NEXT: --> %len_norange U: full-set S: full-set
+
+ %t0 = add i8 %len, 1
+ %t1 = add i8 %len, 2
+; CHECK: %t0 = add i8 %len, 1
+; CHECK-NEXT: --> (1 + %len)<nuw><nsw>
+; CHECK: %t1 = add i8 %len, 2
+; CHECK-NEXT: --> (2 + %len)<nuw>
+
+ %t0.zext = zext i8 %t0 to i16
+ %t1.zext = zext i8 %t1 to i16
+; CHECK: %t0.zext = zext i8 %t0 to i16
+; CHECK-NEXT: --> (1 + (zext i8 %len to i16))<nuw><nsw> U: [1,128) S: [1,128)
+; CHECK: %t1.zext = zext i8 %t1 to i16
+; CHECK-NEXT: --> (2 + (zext i8 %len to i16))<nuw><nsw> U: [2,129) S: [2,129)
+
+ %q0 = add i8 %len_norange, 1
+ %q1 = add i8 %len_norange, 2
+ %q0.zext = zext i8 %q0 to i16
+ %q1.zext = zext i8 %q1 to i16
+
+; CHECK: %q0.zext = zext i8 %q0 to i16
+; CHECK-NEXT: --> (zext i8 (1 + %len_norange) to i16) U: [0,256) S: [0,256)
+; CHECK: %q1.zext = zext i8 %q1 to i16
+; CHECK-NEXT: --> (zext i8 (2 + %len_norange) to i16) U: [0,256) S: [0,256)
+
+ ret void
+}
diff --git a/test/Analysis/ScalarEvolution/non-IV-phi.ll b/test/Analysis/ScalarEvolution/non-IV-phi.ll
new file mode 100644
index 0000000000000..f0d6c2f5d9d33
--- /dev/null
+++ b/test/Analysis/ScalarEvolution/non-IV-phi.ll
@@ -0,0 +1,59 @@
+; RUN: opt -scalar-evolution -analyze < %s | FileCheck %s
+
+define void @test1(i8 %t, i32 %len) {
+; CHECK-LABEL: test1
+; CHECK: %sphi = phi i32 [ %ext, %entry ], [ %idx.inc.ext, %loop ]
+; CHECK-NEXT: --> (zext i8 {%t,+,1}<%loop> to i32)
+
+ entry:
+ %st = zext i8 %t to i16
+ %ext = zext i8 %t to i32
+ %ecmp = icmp ult i16 %st, 42
+ br i1 %ecmp, label %loop, label %exit
+
+ loop:
+
+ %idx = phi i8 [ %t, %entry ], [ %idx.inc, %loop ]
+ %sphi = phi i32 [ %ext, %entry ], [%idx.inc.ext, %loop]
+
+ %idx.inc = add i8 %idx, 1
+ %idx.inc.ext = zext i8 %idx.inc to i32
+ %idx.ext = zext i8 %idx to i32
+
+ %c = icmp ult i32 %idx.inc.ext, %len
+ br i1 %c, label %loop, label %exit
+
+ exit:
+ ret void
+}
+
+define void @test2(i8 %t, i32 %len) {
+; CHECK-LABEL: test2
+; CHECK: %sphi = phi i32 [ %ext.mul, %entry ], [ %mul, %loop ]
+; CHECK-NEXT: --> (4 * (zext i8 {%t,+,1}<%loop> to i32))
+
+ entry:
+ %st = zext i8 %t to i16
+ %ext = zext i8 %t to i32
+ %ext.mul = mul i32 %ext, 4
+
+ %ecmp = icmp ult i16 %st, 42
+ br i1 %ecmp, label %loop, label %exit
+
+ loop:
+
+ %idx = phi i8 [ %t, %entry ], [ %idx.inc, %loop ]
+ %sphi = phi i32 [ %ext.mul, %entry ], [%mul, %loop]
+
+ %idx.inc = add i8 %idx, 1
+ %idx.inc.ext = zext i8 %idx.inc to i32
+ %mul = mul i32 %idx.inc.ext, 4
+
+ %idx.ext = zext i8 %idx to i32
+
+ %c = icmp ult i32 %idx.inc.ext, %len
+ br i1 %c, label %loop, label %exit
+
+ exit:
+ ret void
+}
diff --git a/test/Analysis/ScalarEvolution/pr24757.ll b/test/Analysis/ScalarEvolution/pr24757.ll
new file mode 100644
index 0000000000000..815adcde0e9df
--- /dev/null
+++ b/test/Analysis/ScalarEvolution/pr24757.ll
@@ -0,0 +1,35 @@
+; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
+
+; CHECK: Loop %bb1: backedge-taken count is (zext i7 (trunc i8 %a.promoted to i7) to i8)
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.10.0"
+
+@a = global i8 -127, align 1
+@b = common global i32 0, align 4
+
+declare void @use(i32)
+
+define i32 @main() {
+bb:
+ %a.promoted = load i8, i8* @a
+ br label %bb1
+
+bb1: ; preds = %bb1, %bb
+ %tmp = phi i8 [ %tmp2, %bb1 ], [ %a.promoted, %bb ]
+ %tmp2 = add i8 %tmp, -1
+ %tmp3 = sext i8 %tmp to i32
+ %tmp4 = xor i32 %tmp3, -1
+ %tmp5 = sext i8 %tmp2 to i32
+ %tmpf = sub nsw i32 %tmp4, %tmp5
+ %tmp6 = trunc i32 %tmpf to i8
+ %tmp7 = icmp eq i8 %tmp6, 0
+ br i1 %tmp7, label %bb8, label %bb1
+
+bb8: ; preds = %bb1
+ store i8 %tmp2, i8* @a
+ store i32 %tmp4, i32* @b
+ %tmp9 = sext i8 %tmp2 to i32
+ call void @use(i32 %tmp9)
+ ret i32 0
+}
diff --git a/test/Analysis/ScalarEvolution/pr25369.ll b/test/Analysis/ScalarEvolution/pr25369.ll
new file mode 100644
index 0000000000000..10754867a3683
--- /dev/null
+++ b/test/Analysis/ScalarEvolution/pr25369.ll
@@ -0,0 +1,78 @@
+; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @hoge1() {
+; CHECK-LABEL: Classifying expressions for: @hoge1
+bb:
+ br i1 undef, label %bb4, label %bb2
+
+bb2: ; preds = %bb2, %bb
+ br i1 false, label %bb4, label %bb2
+
+bb3: ; preds = %bb4
+ %tmp = add i32 %tmp10, -1
+ br label %bb13
+
+bb4: ; preds = %bb4, %bb2, %bb
+ %tmp5 = phi i64 [ %tmp11, %bb4 ], [ 1, %bb2 ], [ 1, %bb ]
+ %tmp6 = phi i32 [ %tmp10, %bb4 ], [ 0, %bb2 ], [ 0, %bb ]
+ %tmp7 = load i32, i32* undef, align 4
+ %tmp8 = add i32 %tmp7, %tmp6
+ %tmp9 = add i32 undef, %tmp8
+ %tmp10 = add i32 undef, %tmp9
+ %tmp11 = add nsw i64 %tmp5, 3
+ %tmp12 = icmp eq i64 %tmp11, 64
+ br i1 %tmp12, label %bb3, label %bb4
+
+; CHECK: Loop %bb4: backedge-taken count is 20
+; CHECK: Loop %bb4: max backedge-taken count is 20
+
+bb13: ; preds = %bb13, %bb3
+ %tmp14 = phi i64 [ 0, %bb3 ], [ %tmp15, %bb13 ]
+ %tmp15 = add nuw nsw i64 %tmp14, 1
+ %tmp16 = trunc i64 %tmp15 to i32
+ %tmp17 = icmp eq i32 %tmp16, %tmp
+ br i1 %tmp17, label %bb18, label %bb13
+
+bb18: ; preds = %bb13
+ ret void
+}
+
+define void @hoge2() {
+; CHECK-LABEL: Classifying expressions for: @hoge2
+bb:
+ br i1 undef, label %bb4, label %bb2
+
+bb2: ; preds = %bb2, %bb
+ br i1 false, label %bb4, label %bb2
+
+bb3: ; preds = %bb4
+ %tmp = add i32 %tmp10, -1
+ br label %bb13
+
+bb4: ; preds = %bb4, %bb2, %bb
+ %tmp5 = phi i64 [ %tmp11, %bb4 ], [ 1, %bb2 ], [ 3, %bb ]
+ %tmp6 = phi i32 [ %tmp10, %bb4 ], [ 0, %bb2 ], [ 0, %bb ]
+ %tmp7 = load i32, i32* undef, align 4
+ %tmp8 = add i32 %tmp7, %tmp6
+ %tmp9 = add i32 undef, %tmp8
+ %tmp10 = add i32 undef, %tmp9
+ %tmp11 = add nsw i64 %tmp5, 3
+ %tmp12 = icmp eq i64 %tmp11, 64
+ br i1 %tmp12, label %bb3, label %bb4
+
+; CHECK: Loop %bb4: Unpredictable backedge-taken count.
+; CHECK: Loop %bb4: Unpredictable max backedge-taken count.
+
+bb13: ; preds = %bb13, %bb3
+ %tmp14 = phi i64 [ 0, %bb3 ], [ %tmp15, %bb13 ]
+ %tmp15 = add nuw nsw i64 %tmp14, 1
+ %tmp16 = trunc i64 %tmp15 to i32
+ %tmp17 = icmp eq i32 %tmp16, %tmp
+ br i1 %tmp17, label %bb18, label %bb13
+
+bb18: ; preds = %bb13
+ ret void
+}
diff --git a/test/Analysis/ScalarEvolution/scev-aa.ll b/test/Analysis/ScalarEvolution/scev-aa.ll
index e2123f44f1676..47a84d57c3b3c 100644
--- a/test/Analysis/ScalarEvolution/scev-aa.ll
+++ b/test/Analysis/ScalarEvolution/scev-aa.ll
@@ -1,4 +1,4 @@
-; RUN: opt < %s -scev-aa -aa-eval -print-all-alias-modref-info \
+; RUN: opt -disable-output < %s -disable-basicaa -scev-aa -aa-eval -print-all-alias-modref-info \
; RUN: 2>&1 | FileCheck %s
; At the time of this writing, -basicaa misses the example of the form
diff --git a/test/Analysis/ScalarEvolution/shift-op.ll b/test/Analysis/ScalarEvolution/shift-op.ll
new file mode 100644
index 0000000000000..fe832d5676876
--- /dev/null
+++ b/test/Analysis/ScalarEvolution/shift-op.ll
@@ -0,0 +1,164 @@
+; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
+
+define void @test0(i32 %init) {
+; CHECK-LABEL: Classifying expressions for: @test0
+; CHECK: Loop %loop: max backedge-taken count is 32
+ entry:
+ br label %loop
+
+ loop:
+ %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
+ %iv.shift = lshr i32 %iv, 1
+ %exit.cond = icmp eq i32 %iv, 0
+ br i1 %exit.cond, label %leave, label %loop
+
+ leave:
+ ret void
+}
+
+define void @test1(i32 %init) {
+; CHECK-LABEL: Classifying expressions for: @test1
+; CHECK: Loop %loop: max backedge-taken count is 32
+ entry:
+ br label %loop
+
+ loop:
+ %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
+ %iv.shift = shl i32 %iv, 1
+ %exit.cond = icmp eq i32 %iv, 0
+ br i1 %exit.cond, label %leave, label %loop
+
+ leave:
+ ret void
+}
+
+define void @test2(i32 %init) {
+; CHECK-LABEL: Determining loop execution counts for: @test2
+; CHECK: Loop %loop: Unpredictable max backedge-taken count.
+
+; Unpredictable because %iv could "stabilize" to either -1 or 0,
+; depending on %init.
+ entry:
+ br label %loop
+
+ loop:
+ %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
+ %iv.shift = ashr i32 %iv, 1
+ %exit.cond = icmp eq i32 %iv, 0
+ br i1 %exit.cond, label %leave, label %loop
+
+ leave:
+ ret void
+}
+
+define void @test3(i32* %init.ptr) {
+; CHECK-LABEL: Determining loop execution counts for: @test3
+; CHECK: Loop %loop: max backedge-taken count is 32
+ entry:
+ %init = load i32, i32* %init.ptr, !range !0
+ br label %loop
+
+ loop:
+ %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
+ %iv.shift = ashr i32 %iv, 1
+ %exit.cond = icmp eq i32 %iv, 0
+ br i1 %exit.cond, label %leave, label %loop
+
+ leave:
+ ret void
+}
+
+define void @test4(i32* %init.ptr) {
+; CHECK-LABEL: Classifying expressions for: @test4
+; CHECK-LABEL: Loop %loop: max backedge-taken count is 32
+ entry:
+ %init = load i32, i32* %init.ptr, !range !1
+ br label %loop
+
+ loop:
+ %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
+ %iv.shift = ashr i32 %iv, 1
+ %exit.cond = icmp eq i32 %iv, -1
+ br i1 %exit.cond, label %leave, label %loop
+
+ leave:
+ ret void
+}
+
+define void @test5(i32* %init.ptr) {
+; CHECK-LABEL: Determining loop execution counts for: @test5
+; CHECK: Loop %loop: Unpredictable max backedge-taken count.
+
+; %iv will "stabilize" to -1, so this is an infinite loop
+ entry:
+ %init = load i32, i32* %init.ptr, !range !1
+ br label %loop
+
+ loop:
+ %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
+ %iv.shift = ashr i32 %iv, 1
+ %exit.cond = icmp eq i32 %iv, 0
+ br i1 %exit.cond, label %leave, label %loop
+
+ leave:
+ ret void
+}
+
+define void @test6(i32 %init, i32 %shift.amt) {
+; CHECK-LABEL: Determining loop execution counts for: @test6
+; CHECK: Loop %loop: Unpredictable max backedge-taken count.
+
+; Potentially infinite loop, since %shift.amt could be 0
+ entry:
+ br label %loop
+
+ loop:
+ %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
+ %iv.shift = lshr i32 %iv, %shift.amt
+ %exit.cond = icmp eq i32 %iv, 0
+ br i1 %exit.cond, label %leave, label %loop
+
+ leave:
+ ret void
+}
+
+define void @test7(i32 %init) {
+; CHECK-LABEL: Classifying expressions for: @test7
+; CHECK: Loop %loop: max backedge-taken count is 32
+
+ entry:
+ br label %loop
+
+ loop:
+ %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
+ %iv.shift = lshr i32 %iv, 1
+ %exit.cond = icmp eq i32 %iv.shift, 0
+ br i1 %exit.cond, label %leave, label %loop
+
+ leave:
+ ret void
+}
+
+define void @test8(i32 %init) {
+; CHECK-LABEL: Classifying expressions for: @test8
+; CHECK: Loop %loop: Unpredictable max backedge-taken count.
+
+; In this test case, %iv.test stabilizes to 127, not -1, so the loop
+; is infinite.
+
+ entry:
+ br label %loop
+
+ loop:
+ %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
+ %iv.shift = ashr i32 %iv, 1
+ %iv.test = lshr i32 %iv, 1
+ %exit.cond = icmp eq i32 %iv.test, -1
+ br i1 %exit.cond, label %leave, label %loop
+
+ leave:
+ ret void
+}
+
+!0 = !{i32 0, i32 50000}
+!1 = !{i32 -5000, i32 -1}
diff --git a/test/Analysis/ScalarEvolution/smax-br-phi-idioms.ll b/test/Analysis/ScalarEvolution/smax-br-phi-idioms.ll
new file mode 100644
index 0000000000000..500f3e16c8f5f
--- /dev/null
+++ b/test/Analysis/ScalarEvolution/smax-br-phi-idioms.ll
@@ -0,0 +1,128 @@
+; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
+
+define i32 @f0(i32 %x, i32 %y) {
+; CHECK-LABEL: Classifying expressions for: @f0
+ entry:
+ %c = icmp sgt i32 %y, 0
+ br i1 %c, label %add, label %merge
+
+ add:
+ %sum = add i32 %x, %y
+ br label %merge
+
+ merge:
+ %v = phi i32 [ %sum, %add ], [ %x, %entry ]
+; CHECK: %v = phi i32 [ %sum, %add ], [ %x, %entry ]
+; CHECK-NEXT: --> ((0 smax %y) + %x) U: full-set S: full-set
+ ret i32 %v
+}
+
+define i32 @f1(i32 %x, i32 %y) {
+; CHECK-LABEL: Classifying expressions for: @f1
+ entry:
+ %c = icmp sge i32 %y, 0
+ br i1 %c, label %add, label %merge
+
+ add:
+ %sum = add i32 %x, %y
+ br label %merge
+
+ merge:
+ %v = phi i32 [ %sum, %add ], [ %x, %entry ]
+; CHECK: %v = phi i32 [ %sum, %add ], [ %x, %entry ]
+; CHECK-NEXT: --> ((0 smax %y) + %x) U: full-set S: full-set
+ ret i32 %v
+}
+
+define i32 @f2(i32 %x, i32 %y, i32* %ptr) {
+; CHECK-LABEL: Classifying expressions for: @f2
+ entry:
+ %c = icmp sge i32 %y, 0
+ br i1 %c, label %add, label %merge
+
+ add:
+ %lv = load i32, i32* %ptr
+ br label %merge
+
+ merge:
+ %v = phi i32 [ %lv, %add ], [ %x, %entry ]
+; CHECK: %v = phi i32 [ %lv, %add ], [ %x, %entry ]
+; CHECK-NEXT: --> %v U: full-set S: full-set
+ ret i32 %v
+}
+
+define i32 @f3(i32 %x, i32 %init, i32 %lim) {
+; CHECK-LABEL: Classifying expressions for: @f3
+ entry:
+ br label %loop
+
+loop:
+ %iv = phi i32 [ %init, %entry ], [ %iv.inc, %merge ]
+ %iv.inc = add i32 %iv, 1
+ %c = icmp sge i32 %iv, 0
+ br i1 %c, label %add, label %merge
+
+ add:
+ %sum = add i32 %x, %iv
+ br label %merge
+
+ merge:
+ %v = phi i32 [ %sum, %add ], [ %x, %loop ]
+; CHECK: %v = phi i32 [ %sum, %add ], [ %x, %loop ]
+; CHECK-NEXT: --> ((0 smax {%init,+,1}<%loop>) + %x) U: full-set S: full-set
+ %be.cond = icmp eq i32 %iv.inc, %lim
+ br i1 %be.cond, label %loop, label %leave
+
+ leave:
+ ret i32 0
+}
+
+define i32 @f4(i32 %x, i32 %init, i32 %lim) {
+; CHECK-LABEL: Classifying expressions for: @f4
+ entry:
+ %c = icmp sge i32 %init, 0
+ br i1 %c, label %add, label %merge
+
+ add:
+ br label %loop
+
+ loop:
+ %iv = phi i32 [ %init, %add ], [ %iv.inc, %loop ]
+ %iv.inc = add i32 %iv, 1
+ %be.cond = icmp eq i32 %iv.inc, %lim
+ br i1 %be.cond, label %loop, label %add.cont
+
+ add.cont:
+ %sum = add i32 %x, %iv
+ br label %merge
+
+ merge:
+ %v = phi i32 [ %sum, %add.cont ], [ %x, %entry ]
+; CHECK: %v = phi i32 [ %sum, %add.cont ], [ %x, %entry ]
+; CHECK-NEXT: --> %v U: full-set S: full-set
+ ret i32 %v
+}
+
+define i32 @f5(i32* %val) {
+; CHECK-LABEL: Classifying expressions for: @f5
+entry:
+ br label %for.end
+
+for.condt:
+ br i1 true, label %for.cond.0, label %for.end
+
+for.end:
+ %inc = load i32, i32* %val
+ br i1 false, label %for.condt, label %for.cond.0
+
+for.cond.0:
+ %init = phi i32 [ 0, %for.condt ], [ %inc, %for.end ]
+
+; CHECK: %init = phi i32 [ 0, %for.condt ], [ %inc, %for.end ]
+; CHECK-NEXT: --> %init U: full-set S: full-set
+
+; Matching "through" %init will break LCSSA at the SCEV expression
+; level.
+
+ ret i32 %init
+}
diff --git a/test/Analysis/ScalarEvolution/trip-count.ll b/test/Analysis/ScalarEvolution/trip-count.ll
index 1b75c88c753c2..89750810d1b72 100644
--- a/test/Analysis/ScalarEvolution/trip-count.ll
+++ b/test/Analysis/ScalarEvolution/trip-count.ll
@@ -1,4 +1,5 @@
; RUN: opt < %s -analyze -scalar-evolution -scalar-evolution-max-iterations=0 | FileCheck %s
+; RUN: opt < %s -passes='print<scalar-evolution>' -disable-output 2>&1 | FileCheck %s
; PR1101
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
@@ -6,7 +7,7 @@ target triple = "x86_64-unknown-linux-gnu"
@A = weak global [1000 x i32] zeroinitializer, align 32
-; CHECK: Printing analysis 'Scalar Evolution Analysis' for function 'test1':
+; CHECK-LABEL: Determining loop execution counts for: @test1
; CHECK: backedge-taken count is 10000
define void @test1(i32 %N) {
@@ -32,7 +33,7 @@ return: ; preds = %bb5
}
; PR22795
-; CHECK: Printing analysis 'Scalar Evolution Analysis' for function 'test2':
+; CHECK-LABEL: Classifying expressions for: @test2
; CHECK: %iv = phi i32 [ -1, %entry ], [ %next.1, %for.inc.1 ]
; CHECK-NEXT: --> {-1,+,2}<%preheader> U: full-set S: full-set Exits: 13
diff --git a/test/Analysis/ScalarEvolution/zext-wrap.ll b/test/Analysis/ScalarEvolution/zext-wrap.ll
index f56e4556c697a..5bc149e2309a2 100644
--- a/test/Analysis/ScalarEvolution/zext-wrap.ll
+++ b/test/Analysis/ScalarEvolution/zext-wrap.ll
@@ -10,7 +10,7 @@ bb.i: ; preds = %bb1.i, %bb.nph
; This cast shouldn't be folded into the addrec.
; CHECK: %tmp = zext i8 %l_95.0.i1 to i16
-; CHECK: --> (zext i8 {0,+,-1}<%bb.i> to i16){{ U: [^ ]+ S: [^ ]+}}{{ *}}Exits: 2
+; CHECK: --> (zext i8 {0,+,-1}<nw><%bb.i> to i16){{ U: [^ ]+ S: [^ ]+}}{{ *}}Exits: 2
%tmp = zext i8 %l_95.0.i1 to i16
generated by cgit v1.3 (git 2.53.0) at 2026-09-08 05:39:17 +0000