1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt -constraint-elimination -S %s | FileCheck %s
3
4; Tests for cases with explicit checks that %ptr + x >= %ptr. The information can
5; be used to determine that certain GEPs do not overflow.
6
7define i1 @overflow_check_1(i32* %dst) {
8; CHECK-LABEL: @overflow_check_1(
9; CHECK-NEXT:  entry:
10; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, i32* [[DST:%.*]], i64 5
11; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge i32* [[DST_5]], [[DST]]
12; CHECK-NEXT:    br i1 [[DST_5_UGE]], label [[THEN:%.*]], label [[ELSE:%.*]]
13; CHECK:       then:
14; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, i32* [[DST]], i64 4
15; CHECK-NEXT:    [[TRUE_DST_4_UGE:%.*]] = icmp uge i32* [[DST_4]], [[DST]]
16; CHECK-NEXT:    ret i1 [[TRUE_DST_4_UGE]]
17; CHECK:       else:
18; CHECK-NEXT:    ret i1 false
19;
20entry:
21  %dst.5 = getelementptr i32, i32* %dst, i64 5
22  %dst.5.uge = icmp uge i32* %dst.5, %dst
23  br i1 %dst.5.uge, label %then, label %else
24
25then:
26  %dst.4 = getelementptr i32, i32* %dst, i64 4
27  %true.dst.4.uge = icmp uge i32* %dst.4, %dst
28  ret i1 %true.dst.4.uge
29
30else:
31  ret i1 0
32}
33
34define i1 @overflow_check_2_and(i32* %dst) {
35; CHECK-LABEL: @overflow_check_2_and(
36; CHECK-NEXT:  entry:
37; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, i32* [[DST:%.*]], i64 5
38; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge i32* [[DST_5]], [[DST]]
39; CHECK-NEXT:    [[AND:%.*]] = and i1 [[DST_5_UGE]], [[DST_5_UGE]]
40; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
41; CHECK:       then:
42; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, i32* [[DST]], i64 4
43; CHECK-NEXT:    [[TRUE_DST_4_UGE:%.*]] = icmp uge i32* [[DST_4]], [[DST]]
44; CHECK-NEXT:    ret i1 [[TRUE_DST_4_UGE]]
45; CHECK:       else:
46; CHECK-NEXT:    ret i1 true
47;
48entry:
49  %dst.5 = getelementptr i32, i32* %dst, i64 5
50  %dst.5.uge = icmp uge i32* %dst.5, %dst
51  %and = and i1 %dst.5.uge, %dst.5.uge
52  br i1 %and, label %then, label %else
53
54then:
55  %dst.4 = getelementptr i32, i32* %dst, i64 4
56  %true.dst.4.uge = icmp uge i32* %dst.4, %dst
57  ret i1 %true.dst.4.uge
58
59else:
60  ret i1 true
61}
62
63define i1 @overflow_check_3_and(i32* %dst) {
64; CHECK-LABEL: @overflow_check_3_and(
65; CHECK-NEXT:  entry:
66; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, i32* [[DST:%.*]], i64 5
67; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge i32* [[DST_5]], [[DST]]
68; CHECK-NEXT:    [[AND:%.*]] = and i1 [[DST_5_UGE]], [[DST_5_UGE]]
69; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
70; CHECK:       then:
71; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, i32* [[DST]], i64 4
72; CHECK-NEXT:    [[DST_4_UGE:%.*]] = icmp uge i32* [[DST_4]], [[DST]]
73; CHECK-NEXT:    ret i1 [[DST_4_UGE]]
74; CHECK:       else:
75; CHECK-NEXT:    [[ELSE_DST_4:%.*]] = getelementptr i32, i32* [[DST]], i64 4
76; CHECK-NEXT:    [[ELSE_DST_4_UGE:%.*]] = icmp uge i32* [[ELSE_DST_4]], [[DST]]
77; CHECK-NEXT:    ret i1 [[ELSE_DST_4_UGE]]
78;
79entry:
80  %dst.5 = getelementptr i32, i32* %dst, i64 5
81  %dst.5.uge = icmp uge i32* %dst.5, %dst
82  %and = and i1 %dst.5.uge, %dst.5.uge
83  br i1 %and, label %then, label %else
84
85then:
86  %dst.4 = getelementptr i32, i32* %dst, i64 4
87  %dst.4.uge = icmp uge i32* %dst.4, %dst
88  ret i1 %dst.4.uge
89
90else:
91  %else.dst.4 = getelementptr i32, i32* %dst, i64 4
92  %else.dst.4.uge = icmp uge i32* %else.dst.4, %dst
93  ret i1 %else.dst.4.uge
94}
95
96define i1 @overflow_check_4_and(i32* %dst) {
97; CHECK-LABEL: @overflow_check_4_and(
98; CHECK-NEXT:  entry:
99; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, i32* [[DST:%.*]], i64 5
100; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge i32* [[DST_5]], [[DST]]
101; CHECK-NEXT:    [[AND:%.*]] = and i1 [[DST_5_UGE]], [[DST_5_UGE]]
102; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
103; CHECK:       then:
104; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, i32* [[DST]], i64 4
105; CHECK-NEXT:    [[TRUE_DST_4_UGE:%.*]] = icmp uge i32* [[DST_4]], [[DST]]
106; CHECK-NEXT:    [[DST_5_2:%.*]] = getelementptr i32, i32* [[DST]], i64 5
107; CHECK-NEXT:    [[TRUE_DST_5_UGE:%.*]] = icmp uge i32* [[DST_5_2]], [[DST]]
108; CHECK-NEXT:    [[RES_0:%.*]] = xor i1 [[TRUE_DST_4_UGE]], [[TRUE_DST_5_UGE]]
109; CHECK-NEXT:    [[DST_6:%.*]] = getelementptr i32, i32* [[DST]], i64 6
110; CHECK-NEXT:    [[C_DST_6_UGE:%.*]] = icmp uge i32* [[DST_6]], [[DST]]
111; CHECK-NEXT:    [[RES_1:%.*]] = xor i1 [[RES_0]], [[C_DST_6_UGE]]
112; CHECK-NEXT:    ret i1 [[RES_1]]
113; CHECK:       else:
114; CHECK-NEXT:    [[ELSE_DST_4:%.*]] = getelementptr i32, i32* [[DST]], i64 4
115; CHECK-NEXT:    [[ELSE_DST_4_UGE:%.*]] = icmp uge i32* [[ELSE_DST_4]], [[DST]]
116; CHECK-NEXT:    [[ELSE_DST_6:%.*]] = getelementptr i32, i32* [[DST]], i64 6
117; CHECK-NEXT:    [[ELSE_DST_6_UGE:%.*]] = icmp uge i32* [[ELSE_DST_6]], [[DST]]
118; CHECK-NEXT:    [[ELSE_RES_0:%.*]] = xor i1 [[ELSE_DST_4_UGE]], [[ELSE_DST_6_UGE]]
119; CHECK-NEXT:    ret i1 [[ELSE_RES_0]]
120;
121entry:
122  %dst.5 = getelementptr i32, i32* %dst, i64 5
123  %dst.5.uge = icmp uge i32* %dst.5, %dst
124  %and = and i1 %dst.5.uge, %dst.5.uge
125  br i1 %and, label %then, label %else
126
127then:
128  %dst.4 = getelementptr i32, i32* %dst, i64 4
129  %true.dst.4.uge = icmp uge i32* %dst.4, %dst
130  %dst.5.2 = getelementptr i32, i32* %dst, i64 5
131  %true.dst.5.uge = icmp uge i32* %dst.5.2, %dst
132  %res.0 = xor i1 %true.dst.4.uge, %true.dst.5.uge
133
134  %dst.6 = getelementptr i32, i32* %dst, i64 6
135  %c.dst.6.uge = icmp uge i32* %dst.6, %dst
136  %res.1 = xor i1 %res.0, %c.dst.6.uge
137
138  ret i1 %res.1
139
140else:
141  %else.dst.4 = getelementptr i32, i32* %dst, i64 4
142  %else.dst.4.uge = icmp uge i32* %else.dst.4, %dst
143  %else.dst.6 = getelementptr i32, i32* %dst, i64 6
144  %else.dst.6.uge = icmp uge i32* %else.dst.6, %dst
145  %else.res.0 = xor i1 %else.dst.4.uge, %else.dst.6.uge
146
147  ret i1 %else.res.0
148}
149
150define i1 @overflow_check_3_or(i32* %dst) {
151; CHECK-LABEL: @overflow_check_3_or(
152; CHECK-NEXT:  entry:
153; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, i32* [[DST:%.*]], i64 5
154; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge i32* [[DST_5]], [[DST]]
155; CHECK-NEXT:    [[OR:%.*]] = or i1 [[DST_5_UGE]], [[DST_5_UGE]]
156; CHECK-NEXT:    br i1 [[OR]], label [[THEN:%.*]], label [[ELSE:%.*]]
157; CHECK:       then:
158; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, i32* [[DST]], i64 4
159; CHECK-NEXT:    [[TRUE_DST_4_UGE:%.*]] = icmp uge i32* [[DST_4]], [[DST]]
160; CHECK-NEXT:    ret i1 [[TRUE_DST_4_UGE]]
161; CHECK:       else:
162; CHECK-NEXT:    ret i1 false
163;
164entry:
165  %dst.5 = getelementptr i32, i32* %dst, i64 5
166  %dst.5.uge = icmp uge i32* %dst.5, %dst
167  %or = or i1 %dst.5.uge, %dst.5.uge
168  br i1 %or, label %then, label %else
169
170then:
171  %dst.4 = getelementptr i32, i32* %dst, i64 4
172  %true.dst.4.uge = icmp uge i32* %dst.4, %dst
173  ret i1 %true.dst.4.uge
174
175else:
176  ret i1 0
177}
178
179define i1 @upper_and_lower_checks_1(i32* %dst, i32 %n) {
180; CHECK-LABEL: @upper_and_lower_checks_1(
181; CHECK-NEXT:  entry:
182; CHECK-NEXT:    [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64
183; CHECK-NEXT:    [[UPPER:%.*]] = getelementptr inbounds i32, i32* [[DST:%.*]], i64 [[N_EXT]]
184; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, i32* [[DST]], i64 5
185; CHECK-NEXT:    [[DST_5_ULT:%.*]] = icmp ult i32* [[DST_5]], [[UPPER]]
186; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge i32* [[DST_5]], [[DST]]
187; CHECK-NEXT:    [[AND_1:%.*]] = and i1 [[DST_5_ULT]], [[DST_5_UGE]]
188; CHECK-NEXT:    br i1 [[AND_1]], label [[THEN:%.*]], label [[ELSE:%.*]]
189; CHECK:       then:
190; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, i32* [[DST]], i64 4
191; CHECK-NEXT:    [[TRUE_DST_4_ULT:%.*]] = icmp ult i32* [[DST_4]], [[UPPER]]
192; CHECK-NEXT:    [[TRUE_DST_4_UGE:%.*]] = icmp uge i32* [[DST_4]], [[DST]]
193; CHECK-NEXT:    [[AND:%.*]] = and i1 [[TRUE_DST_4_ULT]], [[TRUE_DST_4_UGE]]
194; CHECK-NEXT:    ret i1 [[AND]]
195; CHECK:       else:
196; CHECK-NEXT:    ret i1 false
197;
198entry:
199  %n.ext = zext i32 %n to i64
200  %upper = getelementptr inbounds i32, i32* %dst, i64 %n.ext
201  %dst.5 = getelementptr i32, i32* %dst, i64 5
202  %dst.5.ult = icmp ult i32* %dst.5, %upper
203  %dst.5.uge = icmp uge i32* %dst.5, %dst
204  %and.1 = and i1 %dst.5.ult, %dst.5.uge
205  br i1 %and.1, label %then, label %else
206
207then:
208  %dst.4 = getelementptr i32, i32* %dst, i64 4
209  %true.dst.4.ult = icmp ult i32* %dst.4, %upper
210  %true.dst.4.uge = icmp uge i32* %dst.4, %dst
211  %and = and i1 %true.dst.4.ult, %true.dst.4.uge
212  ret i1 %and
213
214else:
215  ret i1 0
216}
217
218define i1 @upper_and_lower_checks_2_dst6(i32* %dst, i32 %n) {
219; CHECK-LABEL: @upper_and_lower_checks_2_dst6(
220; CHECK-NEXT:  entry:
221; CHECK-NEXT:    [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64
222; CHECK-NEXT:    [[UPPER:%.*]] = getelementptr inbounds i32, i32* [[DST:%.*]], i64 [[N_EXT]]
223; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, i32* [[DST]], i64 5
224; CHECK-NEXT:    [[DST_5_ULT:%.*]] = icmp ult i32* [[DST_5]], [[UPPER]]
225; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge i32* [[DST_5]], [[DST]]
226; CHECK-NEXT:    [[AND:%.*]] = and i1 [[DST_5_ULT]], [[DST_5_UGE]]
227; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
228; CHECK:       then:
229; CHECK-NEXT:    [[DST_6:%.*]] = getelementptr i32, i32* [[DST]], i64 6
230; CHECK-NEXT:    [[C_DST_6_ULT:%.*]] = icmp ult i32* [[DST_6]], [[UPPER]]
231; CHECK-NEXT:    [[TRUE_DST_6_UGE:%.*]] = icmp uge i32* [[DST_6]], [[DST]]
232; CHECK-NEXT:    [[RES:%.*]] = and i1 [[C_DST_6_ULT]], [[TRUE_DST_6_UGE]]
233; CHECK-NEXT:    ret i1 [[RES]]
234; CHECK:       else:
235; CHECK-NEXT:    ret i1 false
236;
237entry:
238  %n.ext = zext i32 %n to i64
239  %upper = getelementptr inbounds i32, i32* %dst, i64 %n.ext
240  %dst.5 = getelementptr i32, i32* %dst, i64 5
241  %dst.5.ult = icmp ult i32* %dst.5, %upper
242  %dst.5.uge = icmp uge i32* %dst.5, %dst
243  %and = and i1 %dst.5.ult, %dst.5.uge
244  br i1 %and, label %then, label %else
245
246then:
247  %dst.6 = getelementptr i32, i32* %dst, i64 6
248  %c.dst.6.ult = icmp ult i32* %dst.6, %upper
249  %true.dst.6.uge = icmp uge i32* %dst.6, %dst
250  %res = and i1 %c.dst.6.ult, %true.dst.6.uge
251  ret i1 %res
252
253else:
254  ret i1 0
255}
256
257define i1 @upper_and_lower_checks_2_dst7(i32* %dst, i32 %n) {
258; CHECK-LABEL: @upper_and_lower_checks_2_dst7(
259; CHECK-NEXT:  entry:
260; CHECK-NEXT:    [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64
261; CHECK-NEXT:    [[UPPER:%.*]] = getelementptr inbounds i32, i32* [[DST:%.*]], i64 [[N_EXT]]
262; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, i32* [[DST]], i64 5
263; CHECK-NEXT:    [[DST_5_ULT:%.*]] = icmp ult i32* [[DST_5]], [[UPPER]]
264; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge i32* [[DST_5]], [[DST]]
265; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[DST_5_ULT]], [[DST_5_UGE]]
266; CHECK-NEXT:    br i1 [[OR_COND]], label [[THEN:%.*]], label [[ELSE:%.*]]
267; CHECK:       then:
268; CHECK-NEXT:    [[DST_7:%.*]] = getelementptr i32, i32* [[DST]], i64 7
269; CHECK-NEXT:    [[C_DST_7_ULT:%.*]] = icmp ult i32* [[DST_7]], [[UPPER]]
270; CHECK-NEXT:    [[C_DST_7_UGE:%.*]] = icmp uge i32* [[DST_7]], [[DST]]
271; CHECK-NEXT:    [[RES:%.*]] = and i1 [[C_DST_7_ULT]], [[C_DST_7_UGE]]
272; CHECK-NEXT:    ret i1 [[RES]]
273; CHECK:       else:
274; CHECK-NEXT:    ret i1 false
275;
276entry:
277  %n.ext = zext i32 %n to i64
278  %upper = getelementptr inbounds i32, i32* %dst, i64 %n.ext
279  %dst.5 = getelementptr i32, i32* %dst, i64 5
280  %dst.5.ult = icmp ult i32* %dst.5, %upper
281  %dst.5.uge = icmp uge i32* %dst.5, %dst
282  %or.cond = and i1 %dst.5.ult, %dst.5.uge
283  br i1 %or.cond, label %then, label %else
284
285then:
286  %dst.7 = getelementptr i32, i32* %dst, i64 7
287  %c.dst.7.ult = icmp ult i32* %dst.7, %upper
288  %c.dst.7.uge = icmp uge i32* %dst.7, %dst
289  %res = and i1 %c.dst.7.ult, %c.dst.7.uge
290  ret i1 %res
291
292else:
293  ret i1 0
294}
295
296define i1 @upper_and_lower_checks_lt(i32* %dst, i32 %n) {
297; CHECK-LABEL: @upper_and_lower_checks_lt(
298; CHECK-NEXT:  entry:
299; CHECK-NEXT:    [[N_EXT:%.*]] = zext i32 [[N:%.*]] to i64
300; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, i32* [[DST:%.*]], i64 [[N_EXT]]
301; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge i32* [[DST_5]], [[DST]]
302; CHECK-NEXT:    [[N_EXT_UGE:%.*]] = icmp uge i64 [[N_EXT]], 3
303; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[DST_5_UGE]], [[N_EXT_UGE]]
304; CHECK-NEXT:    br i1 [[OR_COND]], label [[THEN:%.*]], label [[ELSE:%.*]]
305; CHECK:       then:
306; CHECK-NEXT:    [[DST_3:%.*]] = getelementptr i32, i32* [[DST]], i64 3
307; CHECK-NEXT:    [[TRUE_DST_3_UGE:%.*]] = icmp uge i32* [[DST_3]], [[DST]]
308; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, i32* [[DST]], i64 4
309; CHECK-NEXT:    [[C_DST_4_UGE:%.*]] = icmp uge i32* [[DST_4]], [[DST]]
310; CHECK-NEXT:    [[RES_0:%.*]] = xor i1 [[TRUE_DST_3_UGE]], [[C_DST_4_UGE]]
311; CHECK-NEXT:    ret i1 [[RES_0]]
312; CHECK:       else:
313; CHECK-NEXT:    ret i1 false
314;
315entry:
316  %n.ext = zext i32 %n to i64
317  %dst.5 = getelementptr i32, i32* %dst, i64 %n.ext
318  %dst.5.uge = icmp uge i32* %dst.5, %dst
319  %n.ext.uge = icmp uge i64 %n.ext, 3
320  %or.cond = and i1 %dst.5.uge, %n.ext.uge
321  br i1 %or.cond, label %then, label %else
322
323then:
324  %dst.3 = getelementptr i32, i32* %dst, i64 3
325  %true.dst.3.uge = icmp uge i32* %dst.3, %dst
326  %dst.4 = getelementptr i32, i32* %dst, i64 4
327  %c.dst.4.uge = icmp uge i32* %dst.4, %dst
328  %res.0 = xor i1 %true.dst.3.uge, %c.dst.4.uge
329  ret i1 %res.0
330
331else:
332  ret i1 0
333}
334