1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; REQUIRES: asserts
3; RUN: opt < %s -S -debug -passes=loop-idiom 2>&1 | FileCheck %s
4; The C code to generate this testcase:
5; void test(int *ar, int n, int m)
6; {
7;	  long i;
8;	  for (i=0; i<n; ++i) {
9;     int *arr = ar + i * m;
10;     memset(arr, 0, i + m * sizeof(int));
11;   }
12; }
13
14; Check on debug outputs...
15; CHECK: loop-idiom Scanning: F[MemsetSize_LoopVariant] Countable Loop %for.body
16; CHECK-NEXT: memset size is non-constant
17; CHECK-NEXT: memset size is not a loop-invariant, abort
18; CHECK: loop-idiom Scanning: F[MemsetSize_Stride_Mismatch] Countable Loop %for.body
19; CHECK-NEXT: memset size is non-constant
20; CHECK-NEXT: MemsetSizeSCEV: (4 * (sext i32 %m to i64))<nsw>
21; CHECK-NEXT: PositiveStrideSCEV: (4 + (4 * (sext i32 %m to i64))<nsw>)<nsw>
22; CHECK-NEXT: Try to fold SCEV based on loop guard
23; CHECK-NEXT: FoldedMemsetSize: (4 * (sext i32 %m to i64))<nsw>
24; CHECK-NEXT: FoldedPositiveStride: (4 + (4 * (sext i32 %m to i64))<nsw>)<nsw>
25; CHECK-NEXT: SCEV don't match, abort
26; CHECK: loop-idiom Scanning: F[NonZeroAddressSpace] Countable Loop %for.cond1.preheader
27; CHECK-NEXT: memset size is non-constant
28; CHECK-NEXT: pointer is not in address space zero, abort
29; CHECK: loop-idiom Scanning: F[NonAffinePointer] Countable Loop %for.body
30; CHECK-NEXT: Pointer is not affine, abort
31
32define void @MemsetSize_LoopVariant(i32* %ar, i32 %n, i32 %m) {
33; CHECK-LABEL: @MemsetSize_LoopVariant(
34; CHECK-NEXT:  entry:
35; CHECK-NEXT:    [[CONV:%.*]] = sext i32 [[N:%.*]] to i64
36; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 0, [[CONV]]
37; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END:%.*]]
38; CHECK:       for.body.lr.ph:
39; CHECK-NEXT:    [[CONV1:%.*]] = sext i32 [[M:%.*]] to i64
40; CHECK-NEXT:    [[CONV2:%.*]] = sext i32 [[M]] to i64
41; CHECK-NEXT:    [[MUL3:%.*]] = mul i64 [[CONV2]], 4
42; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
43; CHECK:       for.body:
44; CHECK-NEXT:    [[I_02:%.*]] = phi i64 [ 0, [[FOR_BODY_LR_PH]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]
45; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i64 [[I_02]], [[CONV1]]
46; CHECK-NEXT:    [[ADD_PTR:%.*]] = getelementptr inbounds i32, i32* [[AR:%.*]], i64 [[MUL]]
47; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i32* [[ADD_PTR]] to i8*
48; CHECK-NEXT:    [[ADD:%.*]] = add nsw i64 [[I_02]], [[MUL3]]
49; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[TMP0]], i8 0, i64 [[ADD]], i1 false)
50; CHECK-NEXT:    br label [[FOR_INC]]
51; CHECK:       for.inc:
52; CHECK-NEXT:    [[INC]] = add nuw nsw i64 [[I_02]], 1
53; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[INC]], [[CONV]]
54; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_COND_FOR_END_CRIT_EDGE:%.*]]
55; CHECK:       for.cond.for.end_crit_edge:
56; CHECK-NEXT:    br label [[FOR_END]]
57; CHECK:       for.end:
58; CHECK-NEXT:    ret void
59;
60entry:
61  %conv = sext i32 %n to i64
62  %cmp1 = icmp slt i64 0, %conv
63  br i1 %cmp1, label %for.body.lr.ph, label %for.end
64
65for.body.lr.ph:                                   ; preds = %entry
66  %conv1 = sext i32 %m to i64
67  %conv2 = sext i32 %m to i64
68  %mul3 = mul i64 %conv2, 4
69  br label %for.body
70
71for.body:                                         ; preds = %for.body.lr.ph, %for.inc
72  %i.02 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]
73  %mul = mul nsw i64 %i.02, %conv1
74  %add.ptr = getelementptr inbounds i32, i32* %ar, i64 %mul
75  %0 = bitcast i32* %add.ptr to i8*
76  %add = add nsw i64 %i.02, %mul3
77  call void @llvm.memset.p0i8.i64(i8* align 4 %0, i8 0, i64 %add, i1 false)
78  br label %for.inc
79
80for.inc:                                          ; preds = %for.body
81  %inc = add nuw nsw i64 %i.02, 1
82  %cmp = icmp slt i64 %inc, %conv
83  br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge
84
85for.cond.for.end_crit_edge:                       ; preds = %for.inc
86  br label %for.end
87
88for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry
89  ret void
90}
91; void test(int *ar, int n, int m)
92; {
93;	  long i;
94;	  for (i=0; i<n; ++i) {
95;     int *arr = ar + i + i * m;
96;     memset(arr, 0, m * sizeof(int));
97;   }
98; }
99define void @MemsetSize_Stride_Mismatch(i32* %ar, i32 %n, i32 %m) {
100; CHECK-LABEL: @MemsetSize_Stride_Mismatch(
101; CHECK-NEXT:  entry:
102; CHECK-NEXT:    [[CONV:%.*]] = sext i32 [[N:%.*]] to i64
103; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 0, [[CONV]]
104; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END:%.*]]
105; CHECK:       for.body.lr.ph:
106; CHECK-NEXT:    [[CONV1:%.*]] = sext i32 [[M:%.*]] to i64
107; CHECK-NEXT:    [[CONV3:%.*]] = sext i32 [[M]] to i64
108; CHECK-NEXT:    [[MUL4:%.*]] = mul i64 [[CONV3]], 4
109; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
110; CHECK:       for.body:
111; CHECK-NEXT:    [[I_02:%.*]] = phi i64 [ 0, [[FOR_BODY_LR_PH]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]
112; CHECK-NEXT:    [[ADD_PTR:%.*]] = getelementptr inbounds i32, i32* [[AR:%.*]], i64 [[I_02]]
113; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i64 [[I_02]], [[CONV1]]
114; CHECK-NEXT:    [[ADD_PTR2:%.*]] = getelementptr inbounds i32, i32* [[ADD_PTR]], i64 [[MUL]]
115; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i32* [[ADD_PTR2]] to i8*
116; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[TMP0]], i8 0, i64 [[MUL4]], i1 false)
117; CHECK-NEXT:    br label [[FOR_INC]]
118; CHECK:       for.inc:
119; CHECK-NEXT:    [[INC]] = add nuw nsw i64 [[I_02]], 1
120; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[INC]], [[CONV]]
121; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_COND_FOR_END_CRIT_EDGE:%.*]]
122; CHECK:       for.cond.for.end_crit_edge:
123; CHECK-NEXT:    br label [[FOR_END]]
124; CHECK:       for.end:
125; CHECK-NEXT:    ret void
126;
127entry:
128  %conv = sext i32 %n to i64
129  %cmp1 = icmp slt i64 0, %conv
130  br i1 %cmp1, label %for.body.lr.ph, label %for.end
131
132for.body.lr.ph:                                   ; preds = %entry
133  %conv1 = sext i32 %m to i64
134  %conv3 = sext i32 %m to i64
135  %mul4 = mul i64 %conv3, 4
136  br label %for.body
137
138for.body:                                         ; preds = %for.body.lr.ph, %for.inc
139  %i.02 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]
140  %add.ptr = getelementptr inbounds i32, i32* %ar, i64 %i.02
141  %mul = mul nsw i64 %i.02, %conv1
142  %add.ptr2 = getelementptr inbounds i32, i32* %add.ptr, i64 %mul
143  %0 = bitcast i32* %add.ptr2 to i8*
144  call void @llvm.memset.p0i8.i64(i8* align 4 %0, i8 0, i64 %mul4, i1 false)
145  br label %for.inc
146
147for.inc:                                          ; preds = %for.body
148  %inc = add nuw nsw i64 %i.02, 1
149  %cmp = icmp slt i64 %inc, %conv
150  br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge
151
152for.cond.for.end_crit_edge:                       ; preds = %for.inc
153  br label %for.end
154
155for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry
156  ret void
157}
158
159define void @NonZeroAddressSpace(i32 addrspace(2)* nocapture %ar, i64 %n, i64 %m) {
160; CHECK-LABEL: @NonZeroAddressSpace(
161; CHECK-NEXT:  entry:
162; CHECK-NEXT:    [[TMP0:%.*]] = shl nuw i64 [[M:%.*]], 2
163; CHECK-NEXT:    br label [[FOR_COND1_PREHEADER:%.*]]
164; CHECK:       for.cond1.preheader:
165; CHECK-NEXT:    [[I_017:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INC5:%.*]], [[FOR_INC4:%.*]] ]
166; CHECK-NEXT:    [[TMP1:%.*]] = mul i64 [[M]], [[I_017]]
167; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i32, i32 addrspace(2)* [[AR:%.*]], i64 [[TMP1]]
168; CHECK-NEXT:    [[SCEVGEP1:%.*]] = bitcast i32 addrspace(2)* [[SCEVGEP]] to i8 addrspace(2)*
169; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i64 [[I_017]], [[M]]
170; CHECK-NEXT:    call void @llvm.memset.p2i8.i64(i8 addrspace(2)* align 4 [[SCEVGEP1]], i8 0, i64 [[TMP0]], i1 false)
171; CHECK-NEXT:    br label [[FOR_INC4]]
172; CHECK:       for.inc4:
173; CHECK-NEXT:    [[INC5]] = add nuw nsw i64 [[I_017]], 1
174; CHECK-NEXT:    [[EXITCOND18_NOT:%.*]] = icmp eq i64 [[INC5]], [[N:%.*]]
175; CHECK-NEXT:    br i1 [[EXITCOND18_NOT]], label [[FOR_END6:%.*]], label [[FOR_COND1_PREHEADER]]
176; CHECK:       for.end6:
177; CHECK-NEXT:    ret void
178;
179entry:
180  %0 = shl nuw i64 %m, 2
181  br label %for.cond1.preheader
182
183for.cond1.preheader:                              ; preds = %for.inc4, %entry
184  %i.017 = phi i64 [ 0, %entry ], [ %inc5, %for.inc4 ]
185  %1 = mul i64 %m, %i.017
186  %scevgep = getelementptr i32, i32 addrspace(2)* %ar, i64 %1
187  %scevgep1 = bitcast i32 addrspace(2)* %scevgep to i8 addrspace(2)*
188  %mul = mul nsw i64 %i.017, %m
189  call void @llvm.memset.p2i8.i64(i8 addrspace(2)* align 4 %scevgep1, i8 0, i64 %0, i1 false)
190  br label %for.inc4
191
192for.inc4:                                         ; preds = %for.cond1.preheader
193  %inc5 = add nuw nsw i64 %i.017, 1
194  %exitcond18.not = icmp eq i64 %inc5, %n
195  br i1 %exitcond18.not, label %for.end6, label %for.cond1.preheader
196
197for.end6:                                         ; preds = %for.inc4
198  ret void
199}
200
201; void test(int *ar, int n, int m)
202; {
203;   long i;
204;   for (i=0; i<n; ++i) {
205;     int *arr = ar + i * m;
206;     memset(arr, 0, m * sizeof(int));
207; 	  ar = ar + i;
208;   }
209; }
210define void @NonAffinePointer(i32* %ar, i32 %n, i32 %m) {
211; CHECK-LABEL: @NonAffinePointer(
212; CHECK-NEXT:  entry:
213; CHECK-NEXT:    [[CONV:%.*]] = sext i32 [[N:%.*]] to i64
214; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 0, [[CONV]]
215; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_BODY_LR_PH:%.*]], label [[FOR_END:%.*]]
216; CHECK:       for.body.lr.ph:
217; CHECK-NEXT:    [[CONV1:%.*]] = sext i32 [[M:%.*]] to i64
218; CHECK-NEXT:    [[CONV2:%.*]] = sext i32 [[M]] to i64
219; CHECK-NEXT:    [[MUL3:%.*]] = mul i64 [[CONV2]], 4
220; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
221; CHECK:       for.body:
222; CHECK-NEXT:    [[AR_ADDR_03:%.*]] = phi i32* [ [[AR:%.*]], [[FOR_BODY_LR_PH]] ], [ [[ADD_PTR4:%.*]], [[FOR_INC:%.*]] ]
223; CHECK-NEXT:    [[I_02:%.*]] = phi i64 [ 0, [[FOR_BODY_LR_PH]] ], [ [[INC:%.*]], [[FOR_INC]] ]
224; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i64 [[I_02]], [[CONV1]]
225; CHECK-NEXT:    [[ADD_PTR:%.*]] = getelementptr inbounds i32, i32* [[AR_ADDR_03]], i64 [[MUL]]
226; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i32* [[ADD_PTR]] to i8*
227; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[TMP0]], i8 0, i64 [[MUL3]], i1 false)
228; CHECK-NEXT:    [[ADD_PTR4]] = getelementptr inbounds i32, i32* [[AR_ADDR_03]], i64 [[I_02]]
229; CHECK-NEXT:    br label [[FOR_INC]]
230; CHECK:       for.inc:
231; CHECK-NEXT:    [[INC]] = add nuw nsw i64 [[I_02]], 1
232; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[INC]], [[CONV]]
233; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_COND_FOR_END_CRIT_EDGE:%.*]]
234; CHECK:       for.cond.for.end_crit_edge:
235; CHECK-NEXT:    br label [[FOR_END]]
236; CHECK:       for.end:
237; CHECK-NEXT:    ret void
238;
239entry:
240  %conv = sext i32 %n to i64
241  %cmp1 = icmp slt i64 0, %conv
242  br i1 %cmp1, label %for.body.lr.ph, label %for.end
243
244for.body.lr.ph:                                   ; preds = %entry
245  %conv1 = sext i32 %m to i64
246  %conv2 = sext i32 %m to i64
247  %mul3 = mul i64 %conv2, 4
248  br label %for.body
249
250for.body:                                         ; preds = %for.body.lr.ph, %for.inc
251  %ar.addr.03 = phi i32* [ %ar, %for.body.lr.ph ], [ %add.ptr4, %for.inc ]
252  %i.02 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]
253  %mul = mul nsw i64 %i.02, %conv1
254  %add.ptr = getelementptr inbounds i32, i32* %ar.addr.03, i64 %mul
255  %0 = bitcast i32* %add.ptr to i8*
256  call void @llvm.memset.p0i8.i64(i8* align 4 %0, i8 0, i64 %mul3, i1 false)
257  %add.ptr4 = getelementptr inbounds i32, i32* %ar.addr.03, i64 %i.02
258  br label %for.inc
259
260for.inc:                                          ; preds = %for.body
261  %inc = add nuw nsw i64 %i.02, 1
262  %cmp = icmp slt i64 %inc, %conv
263  br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge
264
265for.cond.for.end_crit_edge:                       ; preds = %for.inc
266  br label %for.end
267
268for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry
269  ret void
270}
271
272declare void @llvm.memset.p0i8.i64(i8* nocapture writeonly, i8, i64, i1 immarg)
273declare void @llvm.memset.p2i8.i64(i8 addrspace(2)* nocapture writeonly, i8, i64, i1 immarg)
274