xref: /llvm-project/llvm/test/Transforms/InstCombine/gep-combine-loop-invariant.ll (revision 462cb3cd6cecd0511ecaf0e3ebcaba455ece587d) 
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt < %s -passes=instcombine -S | FileCheck %s
3
4target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
5target triple = "x86_64-unknown-linux-gnu"
6
7define i32 @foo(ptr nocapture readnone %match, i32 %cur_match, i32 %best_len, i32 %scan_end, ptr nocapture readonly %prev, i32 %limit, i32 %chain_length, ptr nocapture readonly %win, i32 %wmask) {
8; CHECK-LABEL: @foo(
9; CHECK-NEXT:  entry:
10; CHECK-NEXT:    [[IDX_EXT2:%.*]] = zext i32 [[CUR_MATCH:%.*]] to i64
11; CHECK-NEXT:    [[ADD_PTR4:%.*]] = getelementptr inbounds nuw i8, ptr [[WIN:%.*]], i64 [[IDX_EXT2]]
12; CHECK-NEXT:    [[IDX_EXT1:%.*]] = zext i32 [[BEST_LEN:%.*]] to i64
13; CHECK-NEXT:    [[ADD_PTR25:%.*]] = getelementptr inbounds nuw i8, ptr [[ADD_PTR4]], i64 [[IDX_EXT1]]
14; CHECK-NEXT:    [[ADD_PTR36:%.*]] = getelementptr inbounds i8, ptr [[ADD_PTR25]], i64 -1
15; CHECK-NEXT:    [[I1:%.*]] = load i32, ptr [[ADD_PTR36]], align 4
16; CHECK-NEXT:    [[CMP7:%.*]] = icmp eq i32 [[I1]], [[SCAN_END:%.*]]
17; CHECK-NEXT:    br i1 [[CMP7]], label [[DO_END:%.*]], label [[IF_THEN_LR_PH:%.*]]
18; CHECK:       if.then.lr.ph:
19; CHECK-NEXT:    br label [[IF_THEN:%.*]]
20; CHECK:       do.body:
21; CHECK-NEXT:    [[IDX_EXT:%.*]] = zext i32 [[I4:%.*]] to i64
22; CHECK-NEXT:    [[ADD_PTR:%.*]] = getelementptr inbounds nuw i8, ptr [[WIN]], i64 [[IDX_EXT]]
23; CHECK-NEXT:    [[ADD_PTR2:%.*]] = getelementptr inbounds nuw i8, ptr [[ADD_PTR]], i64 [[IDX_EXT1]]
24; CHECK-NEXT:    [[ADD_PTR3:%.*]] = getelementptr inbounds i8, ptr [[ADD_PTR2]], i64 -1
25; CHECK-NEXT:    [[I3:%.*]] = load i32, ptr [[ADD_PTR3]], align 4
26; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[I3]], [[SCAN_END]]
27; CHECK-NEXT:    br i1 [[CMP]], label [[DO_END]], label [[IF_THEN]]
28; CHECK:       if.then:
29; CHECK-NEXT:    [[CUR_MATCH_ADDR_09:%.*]] = phi i32 [ [[CUR_MATCH]], [[IF_THEN_LR_PH]] ], [ [[I4]], [[DO_BODY:%.*]] ]
30; CHECK-NEXT:    [[CHAIN_LENGTH_ADDR_08:%.*]] = phi i32 [ [[CHAIN_LENGTH:%.*]], [[IF_THEN_LR_PH]] ], [ [[DEC:%.*]], [[DO_BODY]] ]
31; CHECK-NEXT:    [[AND:%.*]] = and i32 [[CUR_MATCH_ADDR_09]], [[WMASK:%.*]]
32; CHECK-NEXT:    [[IDXPROM:%.*]] = zext i32 [[AND]] to i64
33; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds nuw i32, ptr [[PREV:%.*]], i64 [[IDXPROM]]
34; CHECK-NEXT:    [[I4]] = load i32, ptr [[ARRAYIDX]], align 4
35; CHECK-NEXT:    [[CMP4:%.*]] = icmp ugt i32 [[I4]], [[LIMIT:%.*]]
36; CHECK-NEXT:    br i1 [[CMP4]], label [[LAND_LHS_TRUE:%.*]], label [[DO_END]]
37; CHECK:       land.lhs.true:
38; CHECK-NEXT:    [[DEC]] = add i32 [[CHAIN_LENGTH_ADDR_08]], -1
39; CHECK-NEXT:    [[CMP5:%.*]] = icmp eq i32 [[DEC]], 0
40; CHECK-NEXT:    br i1 [[CMP5]], label [[DO_END]], label [[DO_BODY]]
41; CHECK:       do.end:
42; CHECK-NEXT:    [[CONT_0:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ 0, [[IF_THEN]] ], [ 0, [[LAND_LHS_TRUE]] ], [ 1, [[DO_BODY]] ]
43; CHECK-NEXT:    ret i32 [[CONT_0]]
44;
45entry:
46  %idx.ext2 = zext i32 %cur_match to i64
47  %add.ptr4 = getelementptr inbounds i8, ptr %win, i64 %idx.ext2
48  %idx.ext1 = zext i32 %best_len to i64
49  %add.ptr25 = getelementptr inbounds i8, ptr %add.ptr4, i64 %idx.ext1
50  %add.ptr36 = getelementptr inbounds i8, ptr %add.ptr25, i64 -1
51  %i1 = load i32, ptr %add.ptr36, align 4
52  %cmp7 = icmp eq i32 %i1, %scan_end
53  br i1 %cmp7, label %do.end, label %if.then.lr.ph
54
55if.then.lr.ph:                                    ; preds = %entry
56  br label %if.then
57
58do.body:                                          ; preds = %land.lhs.true
59  %chain_length.addr.0 = phi i32 [ %dec, %land.lhs.true ]
60  %cur_match.addr.0 = phi i32 [ %i4, %land.lhs.true ]
61  %idx.ext = zext i32 %cur_match.addr.0 to i64
62  %add.ptr = getelementptr inbounds i8, ptr %win, i64 %idx.ext
63  %add.ptr2 = getelementptr inbounds i8, ptr %add.ptr, i64 %idx.ext1
64  %add.ptr3 = getelementptr inbounds i8, ptr %add.ptr2, i64 -1
65  %i3 = load i32, ptr %add.ptr3, align 4
66  %cmp = icmp eq i32 %i3, %scan_end
67  br i1 %cmp, label %do.end, label %if.then
68
69if.then:                                          ; preds = %do.body, %if.then.lr.ph
70  %cur_match.addr.09 = phi i32 [ %cur_match, %if.then.lr.ph ], [ %cur_match.addr.0, %do.body ]
71  %chain_length.addr.08 = phi i32 [ %chain_length, %if.then.lr.ph ], [ %chain_length.addr.0, %do.body ]
72  %and = and i32 %cur_match.addr.09, %wmask
73  %idxprom = zext i32 %and to i64
74  %arrayidx = getelementptr inbounds i32, ptr %prev, i64 %idxprom
75  %i4 = load i32, ptr %arrayidx, align 4
76  %cmp4 = icmp ugt i32 %i4, %limit
77  br i1 %cmp4, label %land.lhs.true, label %do.end
78
79land.lhs.true:                                    ; preds = %if.then
80  %dec = add i32 %chain_length.addr.08, -1
81  %cmp5 = icmp eq i32 %dec, 0
82  br i1 %cmp5, label %do.end, label %do.body
83
84do.end:                                           ; preds = %land.lhs.true, %if.then, %do.body, %entry
85  %cont.0 = phi i32 [ 1, %entry ], [ 0, %if.then ], [ 0, %land.lhs.true ], [ 1, %do.body ]
86  ret i32 %cont.0
87}
88
89declare void @blackhole(<2 x ptr>)
90
91define void @PR37005(ptr %base, ptr %in) {
92; CHECK-LABEL: @PR37005(
93; CHECK-NEXT:  entry:
94; CHECK-NEXT:    br label [[LOOP:%.*]]
95; CHECK:       loop:
96; CHECK-NEXT:    [[E1:%.*]] = getelementptr inbounds ptr, ptr [[IN:%.*]], i64 undef
97; CHECK-NEXT:    [[E2:%.*]] = getelementptr inbounds nuw i8, ptr [[E1]], i64 48
98; CHECK-NEXT:    [[E4:%.*]] = getelementptr inbounds ptr, ptr [[E2]], <2 x i64> <i64 0, i64 1>
99; CHECK-NEXT:    [[PI1:%.*]] = ptrtoint <2 x ptr> [[E4]] to <2 x i64>
100; CHECK-NEXT:    [[TMP0:%.*]] = lshr <2 x i64> [[PI1]], splat (i64 14)
101; CHECK-NEXT:    [[SL1:%.*]] = and <2 x i64> [[TMP0]], splat (i64 1125899906842496)
102; CHECK-NEXT:    [[E5:%.*]] = getelementptr inbounds i8, ptr [[BASE:%.*]], <2 x i64> [[SL1]]
103; CHECK-NEXT:    [[E6:%.*]] = getelementptr inbounds i8, <2 x ptr> [[E5]], i64 80
104; CHECK-NEXT:    call void @blackhole(<2 x ptr> [[E6]])
105; CHECK-NEXT:    br label [[LOOP]]
106;
107entry:
108  br label %loop
109
110loop:                                             ; preds = %loop, %entry
111  %e1 = getelementptr inbounds ptr, ptr %in, i64 undef
112  %e2 = getelementptr inbounds ptr, ptr %e1, i64 6
113  %e4 = getelementptr inbounds ptr, ptr %e2, <2 x i64> <i64 0, i64 1>
114  %pi1 = ptrtoint <2 x ptr> %e4 to <2 x i64>
115  %lr1 = lshr <2 x i64> %pi1, <i64 21, i64 21>
116  %sl1 = shl nuw nsw <2 x i64> %lr1, <i64 7, i64 7>
117  %e5 = getelementptr inbounds i8, ptr %base, <2 x i64> %sl1
118  %e6 = getelementptr inbounds i8, <2 x ptr> %e5, i64 80
119  call void @blackhole(<2 x ptr> %e6)
120  br label %loop
121}
122
123define void @PR37005_2(ptr %base, ptr %in) {
124; CHECK-LABEL: @PR37005_2(
125; CHECK-NEXT:  entry:
126; CHECK-NEXT:    br label [[LOOP:%.*]]
127; CHECK:       loop:
128; CHECK-NEXT:    [[E1:%.*]] = getelementptr inbounds ptr, ptr [[IN:%.*]], i64 undef
129; CHECK-NEXT:    [[E2:%.*]] = getelementptr inbounds nuw i8, ptr [[E1]], i64 48
130; CHECK-NEXT:    [[PI1:%.*]] = ptrtoint ptr [[E2]] to i64
131; CHECK-NEXT:    [[TMP0:%.*]] = lshr i64 [[PI1]], 14
132; CHECK-NEXT:    [[SL1:%.*]] = and i64 [[TMP0]], 1125899906842496
133; CHECK-NEXT:    [[E5:%.*]] = getelementptr inbounds nuw i8, ptr [[BASE:%.*]], i64 [[SL1]]
134; CHECK-NEXT:    [[E6:%.*]] = getelementptr inbounds i8, ptr [[E5]], <2 x i64> <i64 80, i64 60>
135; CHECK-NEXT:    call void @blackhole(<2 x ptr> [[E6]])
136; CHECK-NEXT:    br label [[LOOP]]
137;
138entry:
139  br label %loop
140
141loop:                                             ; preds = %loop, %entry
142  %e1 = getelementptr inbounds ptr, ptr %in, i64 undef
143  %e2 = getelementptr inbounds ptr, ptr %e1, i64 6
144  %pi1 = ptrtoint ptr %e2 to i64
145  %lr1 = lshr i64 %pi1, 21
146  %sl1 = shl nuw nsw i64 %lr1, 7
147  %e5 = getelementptr inbounds i8, ptr %base, i64 %sl1
148  %e6 = getelementptr inbounds i8, ptr %e5, <2 x i64> <i64 80, i64 60>
149  call void @blackhole(<2 x ptr> %e6)
150  br label %loop
151}
152
153define void @PR37005_3(<2 x ptr> %base, ptr %in) {
154; CHECK-LABEL: @PR37005_3(
155; CHECK-NEXT:  entry:
156; CHECK-NEXT:    br label [[LOOP:%.*]]
157; CHECK:       loop:
158; CHECK-NEXT:    [[E1:%.*]] = getelementptr inbounds ptr, ptr [[IN:%.*]], i64 undef
159; CHECK-NEXT:    [[E2:%.*]] = getelementptr inbounds nuw i8, ptr [[E1]], i64 48
160; CHECK-NEXT:    [[E4:%.*]] = getelementptr inbounds ptr, ptr [[E2]], <2 x i64> <i64 0, i64 1>
161; CHECK-NEXT:    [[PI1:%.*]] = ptrtoint <2 x ptr> [[E4]] to <2 x i64>
162; CHECK-NEXT:    [[TMP0:%.*]] = lshr <2 x i64> [[PI1]], splat (i64 14)
163; CHECK-NEXT:    [[SL1:%.*]] = and <2 x i64> [[TMP0]], splat (i64 1125899906842496)
164; CHECK-NEXT:    [[E5:%.*]] = getelementptr inbounds i8, <2 x ptr> [[BASE:%.*]], <2 x i64> [[SL1]]
165; CHECK-NEXT:    [[E6:%.*]] = getelementptr inbounds i8, <2 x ptr> [[E5]], i64 80
166; CHECK-NEXT:    call void @blackhole(<2 x ptr> [[E6]])
167; CHECK-NEXT:    br label [[LOOP]]
168;
169entry:
170  br label %loop
171
172loop:                                             ; preds = %loop, %entry
173  %e1 = getelementptr inbounds ptr, ptr %in, i64 undef
174  %e2 = getelementptr inbounds ptr, ptr %e1, i64 6
175  %e4 = getelementptr inbounds ptr, ptr %e2, <2 x i64> <i64 0, i64 1>
176  %pi1 = ptrtoint <2 x ptr> %e4 to <2 x i64>
177  %lr1 = lshr <2 x i64> %pi1, <i64 21, i64 21>
178  %sl1 = shl nuw nsw <2 x i64> %lr1, <i64 7, i64 7>
179  %e5 = getelementptr inbounds i8, <2 x ptr> %base, <2 x i64> %sl1
180  %e6 = getelementptr inbounds i8, <2 x ptr> %e5, i64 80
181  call void @blackhole(<2 x ptr> %e6)
182  br label %loop
183}
184
185; This would crash because we did not expect to be able to constant fold a GEP.
186
187define void @PR51485(<2 x i64> %v) {
188; CHECK-LABEL: @PR51485(
189; CHECK-NEXT:  entry:
190; CHECK-NEXT:    br label [[LOOP:%.*]]
191; CHECK:       loop:
192; CHECK-NEXT:    [[SL1:%.*]] = shl nuw nsw <2 x i64> [[V:%.*]], splat (i64 7)
193; CHECK-NEXT:    [[E5:%.*]] = getelementptr inbounds i8, ptr @PR51485, <2 x i64> [[SL1]]
194; CHECK-NEXT:    [[E6:%.*]] = getelementptr inbounds i8, <2 x ptr> [[E5]], i64 80
195; CHECK-NEXT:    call void @blackhole(<2 x ptr> [[E6]])
196; CHECK-NEXT:    br label [[LOOP]]
197;
198entry:
199  br label %loop
200
201loop:                                             ; preds = %loop, %entry
202  %sl1 = shl nuw nsw <2 x i64> %v, <i64 7, i64 7>
203  %e5 = getelementptr inbounds i8, ptr @PR51485, <2 x i64> %sl1
204  %e6 = getelementptr inbounds i8, <2 x ptr> %e5, i64 80
205  call void @blackhole(<2 x ptr> %e6)
206  br label %loop
207}
208
209; Avoid folding the GEP outside the loop to inside, and increasing loop
210; instruction count.
211define float @gep_cross_loop(ptr %_arg_, ptr %_arg_3, float %_arg_8) {
212; CHECK-LABEL: @gep_cross_loop(
213; CHECK-NEXT:  entry:
214; CHECK-NEXT:    [[I:%.*]] = load i64, ptr [[_ARG_:%.*]], align 8
215; CHECK-NEXT:    [[ADD_PTR:%.*]] = getelementptr inbounds float, ptr [[_ARG_3:%.*]], i64 [[I]]
216; CHECK-NEXT:    br label [[FOR_COND_I:%.*]]
217; CHECK:       for.cond.i:
218; CHECK-NEXT:    [[IDX:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[ADD11_I:%.*]], [[FOR_BODY_I:%.*]] ]
219; CHECK-NEXT:    [[SUM:%.*]] = phi float [ 0.000000e+00, [[ENTRY]] ], [ [[ADD_I:%.*]], [[FOR_BODY_I]] ]
220; CHECK-NEXT:    [[CMP:%.*]] = icmp samesign ult i64 [[IDX]], 17
221; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY_I]], label [[FOR_COND_I_I_I_PREHEADER:%.*]]
222; CHECK:       for.cond.i.i.i.preheader:
223; CHECK-NEXT:    ret float [[SUM]]
224; CHECK:       for.body.i:
225; CHECK-NEXT:    [[ARRAYIDX_I84_I:%.*]] = getelementptr inbounds nuw float, ptr [[ADD_PTR]], i64 [[IDX]]
226; CHECK-NEXT:    [[I1:%.*]] = load float, ptr [[ARRAYIDX_I84_I]], align 4
227; CHECK-NEXT:    [[ADD_I]] = fadd fast float [[SUM]], [[I1]]
228; CHECK-NEXT:    [[ADD11_I]] = add nuw nsw i64 [[IDX]], 1
229; CHECK-NEXT:    br label [[FOR_COND_I]]
230;
231entry:
232  %i = load i64, ptr %_arg_, align 8
233  %add.ptr = getelementptr inbounds float, ptr %_arg_3, i64 %i
234  br label %for.cond.i
235
236for.cond.i:                                       ; preds = %for.body.i, %entry
237  %idx = phi i64 [ 0, %entry ], [ %add11.i, %for.body.i ]
238  %sum = phi float [ 0.000000e+00, %entry ], [ %add.i, %for.body.i ]
239  %cmp = icmp ule i64 %idx, 16
240  br i1 %cmp, label %for.body.i, label %for.cond.i.i.i.preheader
241
242for.cond.i.i.i.preheader:                         ; preds = %for.cond.i
243  ret float %sum
244
245for.body.i:                                       ; preds = %for.cond.i
246  %arrayidx.i84.i = getelementptr inbounds float, ptr %add.ptr, i64 %idx
247  %i1 = load float, ptr %arrayidx.i84.i, align 4
248  %add.i = fadd fast float %sum, %i1
249  %add11.i = add nsw i64 %idx, 1
250  br label %for.cond.i
251}
252
253declare void @use(ptr)
254
255define void @only_one_inbounds(ptr %ptr, i1 %c, i32 noundef %arg1, i32 noundef %arg2) {
256; CHECK-LABEL: @only_one_inbounds(
257; CHECK-NEXT:  entry:
258; CHECK-NEXT:    [[ARG2_EXT:%.*]] = zext i32 [[ARG2:%.*]] to i64
259; CHECK-NEXT:    br label [[LOOP:%.*]]
260; CHECK:       loop:
261; CHECK-NEXT:    [[ARG1_EXT:%.*]] = zext i32 [[ARG1:%.*]] to i64
262; CHECK-NEXT:    [[PTR2:%.*]] = getelementptr inbounds nuw i8, ptr [[PTR:%.*]], i64 [[ARG1_EXT]]
263; CHECK-NEXT:    [[PTR3:%.*]] = getelementptr i8, ptr [[PTR2]], i64 [[ARG2_EXT]]
264; CHECK-NEXT:    call void @use(ptr [[PTR3]])
265; CHECK-NEXT:    br i1 [[C:%.*]], label [[LOOP]], label [[EXIT:%.*]]
266; CHECK:       exit:
267; CHECK-NEXT:    ret void
268;
269entry:
270  %arg2.ext = zext i32 %arg2 to i64
271  br label %loop
272
273loop:                                             ; preds = %loop, %entry
274  %arg1.ext = zext i32 %arg1 to i64
275  %ptr2 = getelementptr inbounds i8, ptr %ptr, i64 %arg1.ext
276  %ptr3 = getelementptr i8, ptr %ptr2, i64 %arg2.ext
277  call void @use(ptr %ptr3)
278  br i1 %c, label %loop, label %exit
279
280exit:                                             ; preds = %loop
281  ret void
282}
283
284define void @both_inbounds_one_neg(ptr %ptr, i1 %c, i32 noundef %arg) {
285; CHECK-LABEL: @both_inbounds_one_neg(
286; CHECK-NEXT:  entry:
287; CHECK-NEXT:    br label [[LOOP:%.*]]
288; CHECK:       loop:
289; CHECK-NEXT:    [[ARG_EXT:%.*]] = zext i32 [[ARG:%.*]] to i64
290; CHECK-NEXT:    [[PTR2:%.*]] = getelementptr inbounds nuw i8, ptr [[PTR:%.*]], i64 [[ARG_EXT]]
291; CHECK-NEXT:    [[PTR3:%.*]] = getelementptr inbounds i8, ptr [[PTR2]], i64 -1
292; CHECK-NEXT:    call void @use(ptr nonnull [[PTR3]])
293; CHECK-NEXT:    br i1 [[C:%.*]], label [[LOOP]], label [[EXIT:%.*]]
294; CHECK:       exit:
295; CHECK-NEXT:    ret void
296;
297entry:
298  br label %loop
299
300loop:                                             ; preds = %loop, %entry
301  %arg.ext = zext i32 %arg to i64
302  %ptr2 = getelementptr inbounds i8, ptr %ptr, i64 %arg.ext
303  %ptr3 = getelementptr inbounds i8, ptr %ptr2, i64 -1
304  call void @use(ptr %ptr3)
305  br i1 %c, label %loop, label %exit
306
307exit:                                             ; preds = %loop
308  ret void
309}
310
311define void @both_inbounds_pos(ptr %ptr, i1 %c, i32 noundef %arg) {
312; CHECK-LABEL: @both_inbounds_pos(
313; CHECK-NEXT:  entry:
314; CHECK-NEXT:    br label [[LOOP:%.*]]
315; CHECK:       loop:
316; CHECK-NEXT:    [[ARG_EXT:%.*]] = zext i32 [[ARG:%.*]] to i64
317; CHECK-NEXT:    [[PTR2:%.*]] = getelementptr inbounds nuw i8, ptr [[PTR:%.*]], i64 [[ARG_EXT]]
318; CHECK-NEXT:    [[PTR3:%.*]] = getelementptr inbounds nuw i8, ptr [[PTR2]], i64 1
319; CHECK-NEXT:    call void @use(ptr nonnull [[PTR3]])
320; CHECK-NEXT:    br i1 [[C:%.*]], label [[LOOP]], label [[EXIT:%.*]]
321; CHECK:       exit:
322; CHECK-NEXT:    ret void
323;
324entry:
325  br label %loop
326
327loop:                                             ; preds = %loop, %entry
328  %arg.ext = zext i32 %arg to i64
329  %ptr2 = getelementptr inbounds i8, ptr %ptr, i64 %arg.ext
330  %ptr3 = getelementptr inbounds i8, ptr %ptr2, i64 1
331  call void @use(ptr %ptr3)
332  br i1 %c, label %loop, label %exit
333
334exit:                                             ; preds = %loop
335  ret void
336}
337