xref: /llvm-project/llvm/test/Transforms/IndVarSimplify/monotonic_checks.ll (revision 864bb84a427de367528d15270790dd152871daf2) 
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt -passes=indvars -S < %s | FileCheck %s
3
4; Monotonic decrementing iv. we should be able to prove that %iv.next <s len
5; basing on its nsw and the fact that its starting value <s len.
6define i32 @test_01(ptr %p) {
7; CHECK-LABEL: @test_01(
8; CHECK-NEXT:  entry:
9; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4, [[RNG0:!range !.*]]
10; CHECK-NEXT:    br label [[LOOP:%.*]]
11; CHECK:       loop:
12; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
13; CHECK-NEXT:    [[IV_NEXT]] = add nsw i32 [[IV]], -1
14; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]]
15; CHECK:       backedge:
16; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 0
17; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
18; CHECK:       fail:
19; CHECK-NEXT:    ret i32 -1
20; CHECK:       exit:
21; CHECK-NEXT:    ret i32 0
22;
23entry:
24  %len = load i32, ptr %p, !range !0
25  br label %loop
26
27loop:
28  %iv = phi i32 [%len, %entry], [%iv.next, %backedge]
29  %iv.next = add i32 %iv, -1
30  %rc = icmp slt i32 %iv.next, %len
31  br i1 %rc, label %backedge, label %fail
32
33backedge:
34  %loop.cond = icmp ne i32 %iv, 0
35  br i1 %loop.cond, label %loop, label %exit
36
37fail:
38  ret i32 -1
39
40exit:
41  ret i32 0
42}
43
44; We should not remove this range check because signed overflow is possible here (start at len = 0).
45define i32 @test_01_neg(ptr %p) {
46; CHECK-LABEL: @test_01_neg(
47; CHECK-NEXT:  entry:
48; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4, [[RNG0]]
49; CHECK-NEXT:    br label [[LOOP:%.*]]
50; CHECK:       loop:
51; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
52; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
53; CHECK-NEXT:    [[RC:%.*]] = icmp slt i32 [[IV_NEXT]], [[LEN]]
54; CHECK-NEXT:    br i1 [[RC]], label [[BACKEDGE]], label [[FAIL:%.*]]
55; CHECK:       backedge:
56; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 1
57; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
58; CHECK:       fail:
59; CHECK-NEXT:    ret i32 -1
60; CHECK:       exit:
61; CHECK-NEXT:    ret i32 0
62;
63entry:
64  %len = load i32, ptr %p, !range !0
65  br label %loop
66
67loop:
68  %iv = phi i32 [%len, %entry], [%iv.next, %backedge]
69  %iv.next = add i32 %iv, -1
70  %rc = icmp slt i32 %iv.next, %len
71  br i1 %rc, label %backedge, label %fail
72
73backedge:
74  %loop.cond = icmp ne i32 %iv, 1
75  br i1 %loop.cond, label %loop, label %exit
76
77fail:
78  ret i32 -1
79
80exit:
81  ret i32 0
82}
83
84; Monotonic incrementing iv. we should be able to prove that %iv.next >s len
85; basing on its nsw and the fact that its starting value >s len.
86define i32 @test_02(ptr %p) {
87; CHECK-LABEL: @test_02(
88; CHECK-NEXT:  entry:
89; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4, [[RNG1:!range !.*]]
90; CHECK-NEXT:    br label [[LOOP:%.*]]
91; CHECK:       loop:
92; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
93; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
94; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]]
95; CHECK:       backedge:
96; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 0
97; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
98; CHECK:       fail:
99; CHECK-NEXT:    ret i32 -1
100; CHECK:       exit:
101; CHECK-NEXT:    ret i32 0
102;
103entry:
104  %len = load i32, ptr %p, !range !1
105  br label %loop
106
107loop:
108  %iv = phi i32 [%len, %entry], [%iv.next, %backedge]
109  %iv.next = add i32 %iv, 1
110  %rc = icmp sgt i32 %iv.next, %len
111  br i1 %rc, label %backedge, label %fail
112
113backedge:
114  %loop.cond = icmp ne i32 %iv, 0
115  br i1 %loop.cond, label %loop, label %exit
116
117fail:
118  ret i32 -1
119
120exit:
121  ret i32 0
122}
123
124; We should not remove this range check because signed overflow is possible here (start at len = -1).
125define i32 @test_02_neg(ptr %p) {
126; CHECK-LABEL: @test_02_neg(
127; CHECK-NEXT:  entry:
128; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4, [[RNG1]]
129; CHECK-NEXT:    br label [[LOOP:%.*]]
130; CHECK:       loop:
131; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
132; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
133; CHECK-NEXT:    [[RC:%.*]] = icmp sgt i32 [[IV_NEXT]], [[LEN]]
134; CHECK-NEXT:    br i1 [[RC]], label [[BACKEDGE]], label [[FAIL:%.*]]
135; CHECK:       backedge:
136; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], -2
137; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
138; CHECK:       fail:
139; CHECK-NEXT:    ret i32 -1
140; CHECK:       exit:
141; CHECK-NEXT:    ret i32 0
142;
143entry:
144  %len = load i32, ptr %p, !range !1
145  br label %loop
146
147loop:
148  %iv = phi i32 [%len, %entry], [%iv.next, %backedge]
149  %iv.next = add i32 %iv, 1
150  %rc = icmp sgt i32 %iv.next, %len
151  br i1 %rc, label %backedge, label %fail
152
153backedge:
154  %loop.cond = icmp ne i32 %iv, -2
155  br i1 %loop.cond, label %loop, label %exit
156
157fail:
158  ret i32 -1
159
160exit:
161  ret i32 0
162}
163
164define i32 @test_03(ptr %p) {
165; CHECK-LABEL: @test_03(
166; CHECK-NEXT:  entry:
167; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4, [[RNG2:!range !.*]]
168; CHECK-NEXT:    br label [[LOOP:%.*]]
169; CHECK:       loop:
170; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
171; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
172; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]]
173; CHECK:       backedge:
174; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 1000
175; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
176; CHECK:       fail:
177; CHECK-NEXT:    ret i32 -1
178; CHECK:       exit:
179; CHECK-NEXT:    ret i32 0
180;
181entry:
182  %len = load i32, ptr %p, !range !2
183  br label %loop
184
185loop:
186  %iv = phi i32 [%len, %entry], [%iv.next, %backedge]
187  %iv.next = add i32 %iv, 1
188  %rc = icmp sgt i32 %iv.next, %len
189  br i1 %rc, label %backedge, label %fail
190
191backedge:
192  %loop.cond = icmp ne i32 %iv, 1000
193  br i1 %loop.cond, label %loop, label %exit
194
195fail:
196  ret i32 -1
197
198exit:
199  ret i32 0
200}
201
202define i32 @test_04(ptr %p) {
203; CHECK-LABEL: @test_04(
204; CHECK-NEXT:  entry:
205; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4, [[RNG2]]
206; CHECK-NEXT:    br label [[LOOP:%.*]]
207; CHECK:       loop:
208; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
209; CHECK-NEXT:    [[IV_NEXT]] = add nsw i32 [[IV]], -1
210; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]]
211; CHECK:       backedge:
212; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 0
213; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
214; CHECK:       fail:
215; CHECK-NEXT:    ret i32 -1
216; CHECK:       exit:
217; CHECK-NEXT:    ret i32 0
218;
219entry:
220  %len = load i32, ptr %p, !range !2
221  br label %loop
222
223loop:
224  %iv = phi i32 [%len, %entry], [%iv.next, %backedge]
225  %iv.next = add i32 %iv, -1
226  %rc = icmp slt i32 %iv.next, %len
227  br i1 %rc, label %backedge, label %fail
228
229backedge:
230  %loop.cond = icmp ne i32 %iv, 0
231  br i1 %loop.cond, label %loop, label %exit
232
233fail:
234  ret i32 -1
235
236exit:
237  ret i32 0
238}
239
240!0 = !{i32 0, i32 2147483647}
241!1 = !{i32 -2147483648, i32 0}
242!2 = !{i32 0, i32 1000}
243