xref: /llvm-project/llvm/test/Transforms/LoopVersioning/wrapping-pointer-versioning.ll (revision f395a4f8d5dca005c951b5a881b74ec0a96d0c4c) 
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt -loop-versioning -S < %s | FileCheck %s -check-prefix=LV
3
4target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
5
6; For this loop:
7;   unsigned index = 0;
8;   for (int i = 0; i < n; i++) {
9;    A[2 * index] = A[2 * index] + B[i];
10;    index++;
11;   }
12;
13; SCEV is unable to prove that A[2 * i] does not overflow.
14;
15; Analyzing the IR does not help us because the GEPs are not
16; affine AddRecExprs. However, we can turn them into AddRecExprs
17; using SCEV Predicates.
18;
19; Once we have an affine expression we need to add an additional NUSW
20; to check that the pointers don't wrap since the GEPs are not
21; inbound.
22
23; The expression for %mul_ext as analyzed by SCEV is
24;    (zext i32 {0,+,2}<%for.body> to i64)
25; We have added the nusw flag to turn this expression into the SCEV expression:
26;    i64 {0,+,2}<%for.body>
27
28define void @f1(i16* noalias %a,
29; LV-LABEL: @f1(
30; LV-NEXT:  for.body.lver.check:
31; LV-NEXT:    [[A5:%.*]] = bitcast i16* [[A:%.*]] to i8*
32; LV-NEXT:    [[TMP0:%.*]] = add i64 [[N:%.*]], -1
33; LV-NEXT:    [[TMP1:%.*]] = trunc i64 [[TMP0]] to i32
34; LV-NEXT:    [[MUL1:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 2, i32 [[TMP1]])
35; LV-NEXT:    [[MUL_RESULT:%.*]] = extractvalue { i32, i1 } [[MUL1]], 0
36; LV-NEXT:    [[MUL_OVERFLOW:%.*]] = extractvalue { i32, i1 } [[MUL1]], 1
37; LV-NEXT:    [[TMP2:%.*]] = add i32 0, [[MUL_RESULT]]
38; LV-NEXT:    [[TMP5:%.*]] = icmp ult i32 [[TMP2]], 0
39; LV-NEXT:    [[TMP7:%.*]] = icmp ugt i64 [[TMP0]], 4294967295
40; LV-NEXT:    [[TMP8:%.*]] = or i1 [[TMP5]], [[TMP7]]
41; LV-NEXT:    [[TMP9:%.*]] = or i1 [[TMP8]], [[MUL_OVERFLOW]]
42; LV-NEXT:    [[MUL2:%.*]] = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 4, i64 [[TMP0]])
43; LV-NEXT:    [[MUL_RESULT3:%.*]] = extractvalue { i64, i1 } [[MUL2]], 0
44; LV-NEXT:    [[MUL_OVERFLOW4:%.*]] = extractvalue { i64, i1 } [[MUL2]], 1
45; LV-NEXT:    [[TMP11:%.*]] = sub i64 0, [[MUL_RESULT3]]
46; LV-NEXT:    [[TMP12:%.*]] = getelementptr i8, i8* [[A5]], i64 [[MUL_RESULT3]]
47; LV-NEXT:    [[TMP15:%.*]] = icmp ult i8* [[TMP12]], [[A5]]
48; LV-NEXT:    [[TMP17:%.*]] = or i1 [[TMP15]], [[MUL_OVERFLOW4]]
49; LV-NEXT:    [[TMP18:%.*]] = or i1 [[TMP9]], [[TMP17]]
50; LV-NEXT:    br i1 [[TMP18]], label [[FOR_BODY_PH_LVER_ORIG:%.*]], label [[FOR_BODY_PH:%.*]]
51; LV:       for.body.ph.lver.orig:
52; LV-NEXT:    br label [[FOR_BODY_LVER_ORIG:%.*]]
53; LV:       for.body.lver.orig:
54; LV-NEXT:    [[IND_LVER_ORIG:%.*]] = phi i64 [ 0, [[FOR_BODY_PH_LVER_ORIG]] ], [ [[INC_LVER_ORIG:%.*]], [[FOR_BODY_LVER_ORIG]] ]
55; LV-NEXT:    [[IND1_LVER_ORIG:%.*]] = phi i32 [ 0, [[FOR_BODY_PH_LVER_ORIG]] ], [ [[INC1_LVER_ORIG:%.*]], [[FOR_BODY_LVER_ORIG]] ]
56; LV-NEXT:    [[MUL_LVER_ORIG:%.*]] = mul i32 [[IND1_LVER_ORIG]], 2
57; LV-NEXT:    [[MUL_EXT_LVER_ORIG:%.*]] = zext i32 [[MUL_LVER_ORIG]] to i64
58; LV-NEXT:    [[ARRAYIDXA_LVER_ORIG:%.*]] = getelementptr i16, i16* [[A]], i64 [[MUL_EXT_LVER_ORIG]]
59; LV-NEXT:    [[LOADA_LVER_ORIG:%.*]] = load i16, i16* [[ARRAYIDXA_LVER_ORIG]], align 2
60; LV-NEXT:    [[ARRAYIDXB_LVER_ORIG:%.*]] = getelementptr i16, i16* [[B:%.*]], i64 [[IND_LVER_ORIG]]
61; LV-NEXT:    [[LOADB_LVER_ORIG:%.*]] = load i16, i16* [[ARRAYIDXB_LVER_ORIG]], align 2
62; LV-NEXT:    [[ADD_LVER_ORIG:%.*]] = mul i16 [[LOADA_LVER_ORIG]], [[LOADB_LVER_ORIG]]
63; LV-NEXT:    store i16 [[ADD_LVER_ORIG]], i16* [[ARRAYIDXA_LVER_ORIG]], align 2
64; LV-NEXT:    [[INC_LVER_ORIG]] = add nuw nsw i64 [[IND_LVER_ORIG]], 1
65; LV-NEXT:    [[INC1_LVER_ORIG]] = add i32 [[IND1_LVER_ORIG]], 1
66; LV-NEXT:    [[EXITCOND_LVER_ORIG:%.*]] = icmp eq i64 [[INC_LVER_ORIG]], [[N]]
67; LV-NEXT:    br i1 [[EXITCOND_LVER_ORIG]], label [[FOR_END_LOOPEXIT:%.*]], label [[FOR_BODY_LVER_ORIG]]
68; LV:       for.body.ph:
69; LV-NEXT:    br label [[FOR_BODY:%.*]]
70; LV:       for.body:
71; LV-NEXT:    [[IND:%.*]] = phi i64 [ 0, [[FOR_BODY_PH]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
72; LV-NEXT:    [[IND1:%.*]] = phi i32 [ 0, [[FOR_BODY_PH]] ], [ [[INC1:%.*]], [[FOR_BODY]] ]
73; LV-NEXT:    [[MUL:%.*]] = mul i32 [[IND1]], 2
74; LV-NEXT:    [[MUL_EXT:%.*]] = zext i32 [[MUL]] to i64
75; LV-NEXT:    [[ARRAYIDXA:%.*]] = getelementptr i16, i16* [[A]], i64 [[MUL_EXT]]
76; LV-NEXT:    [[LOADA:%.*]] = load i16, i16* [[ARRAYIDXA]], align 2
77; LV-NEXT:    [[ARRAYIDXB:%.*]] = getelementptr i16, i16* [[B]], i64 [[IND]]
78; LV-NEXT:    [[LOADB:%.*]] = load i16, i16* [[ARRAYIDXB]], align 2
79; LV-NEXT:    [[ADD:%.*]] = mul i16 [[LOADA]], [[LOADB]]
80; LV-NEXT:    store i16 [[ADD]], i16* [[ARRAYIDXA]], align 2
81; LV-NEXT:    [[INC]] = add nuw nsw i64 [[IND]], 1
82; LV-NEXT:    [[INC1]] = add i32 [[IND1]], 1
83; LV-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INC]], [[N]]
84; LV-NEXT:    br i1 [[EXITCOND]], label [[FOR_END_LOOPEXIT6:%.*]], label [[FOR_BODY]]
85; LV:       for.end.loopexit:
86; LV-NEXT:    br label [[FOR_END:%.*]]
87; LV:       for.end.loopexit6:
88; LV-NEXT:    br label [[FOR_END]]
89; LV:       for.end:
90; LV-NEXT:    ret void
91;
92  i16* noalias %b, i64 %N) {
93entry:
94  br label %for.body
95
96for.body:                                         ; preds = %for.body, %entry
97  %ind = phi i64 [ 0, %entry ], [ %inc, %for.body ]
98  %ind1 = phi i32 [ 0, %entry ], [ %inc1, %for.body ]
99
100  %mul = mul i32 %ind1, 2
101  %mul_ext = zext i32 %mul to i64
102
103  %arrayidxA = getelementptr i16, i16* %a, i64 %mul_ext
104  %loadA = load i16, i16* %arrayidxA, align 2
105
106  %arrayidxB = getelementptr i16, i16* %b, i64 %ind
107  %loadB = load i16, i16* %arrayidxB, align 2
108
109  %add = mul i16 %loadA, %loadB
110
111  store i16 %add, i16* %arrayidxA, align 2
112
113  %inc = add nuw nsw i64 %ind, 1
114  %inc1 = add i32 %ind1, 1
115
116  %exitcond = icmp eq i64 %inc, %N
117  br i1 %exitcond, label %for.end, label %for.body
118
119for.end:                                          ; preds = %for.body
120  ret void
121}
122
123; For this loop:
124;   unsigned index = n;
125;   for (int i = 0; i < n; i++) {
126;    A[2 * index] = A[2 * index] + B[i];
127;    index--;
128;   }
129;
130; the SCEV expression for 2 * index is not an AddRecExpr
131; (and implictly not affine). However, we are able to make assumptions
132; that will turn the expression into an affine one and continue the
133; analysis.
134;
135; Once we have an affine expression we need to add an additional NUSW
136; to check that the pointers don't wrap since the GEPs are not
137; inbounds.
138;
139; This loop has a negative stride for A, and the nusw flag is required in
140; order to properly extend the increment from i32 -4 to i64 -4.
141
142; The expression for %mul_ext as analyzed by SCEV is
143;     (zext i32 {(2 * (trunc i64 %N to i32)),+,-2}<%for.body> to i64)
144; We have added the nusw flag to turn this expression into the following SCEV:
145;     i64 {zext i32 (2 * (trunc i64 %N to i32)) to i64,+,-2}<%for.body>
146
147define void @f2(i16* noalias %a,
148; LV-LABEL: @f2(
149; LV-NEXT:  for.body.lver.check:
150; LV-NEXT:    [[TRUNCN:%.*]] = trunc i64 [[N:%.*]] to i32
151; LV-NEXT:    [[TMP0:%.*]] = add i64 [[N]], -1
152; LV-NEXT:    [[TMP1:%.*]] = shl i32 [[TRUNCN]], 1
153; LV-NEXT:    [[TMP2:%.*]] = trunc i64 [[TMP0]] to i32
154; LV-NEXT:    [[MUL1:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 2, i32 [[TMP2]])
155; LV-NEXT:    [[MUL_RESULT:%.*]] = extractvalue { i32, i1 } [[MUL1]], 0
156; LV-NEXT:    [[MUL_OVERFLOW:%.*]] = extractvalue { i32, i1 } [[MUL1]], 1
157; LV-NEXT:    [[TMP4:%.*]] = sub i32 [[TMP1]], [[MUL_RESULT]]
158; LV-NEXT:    [[TMP5:%.*]] = icmp ugt i32 [[TMP4]], [[TMP1]]
159; LV-NEXT:    [[TMP8:%.*]] = icmp ugt i64 [[TMP0]], 4294967295
160; LV-NEXT:    [[TMP9:%.*]] = or i1 [[TMP5]], [[TMP8]]
161; LV-NEXT:    [[TMP10:%.*]] = or i1 [[TMP9]], [[MUL_OVERFLOW]]
162; LV-NEXT:    [[TMP12:%.*]] = trunc i64 [[N]] to i31
163; LV-NEXT:    [[TMP13:%.*]] = zext i31 [[TMP12]] to i64
164; LV-NEXT:    [[TMP14:%.*]] = shl nuw nsw i64 [[TMP13]], 1
165; LV-NEXT:    [[SCEVGEP:%.*]] = getelementptr i16, i16* [[A:%.*]], i64 [[TMP14]]
166; LV-NEXT:    [[MUL2:%.*]] = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 4, i64 [[TMP0]])
167; LV-NEXT:    [[MUL_RESULT3:%.*]] = extractvalue { i64, i1 } [[MUL2]], 0
168; LV-NEXT:    [[MUL_OVERFLOW4:%.*]] = extractvalue { i64, i1 } [[MUL2]], 1
169; LV-NEXT:    [[SCEVGEP5:%.*]] = bitcast i16* [[SCEVGEP]] to i8*
170; LV-NEXT:    [[TMP15:%.*]] = sub i64 0, [[MUL_RESULT3]]
171; LV-NEXT:    [[TMP17:%.*]] = getelementptr i8, i8* [[SCEVGEP5]], i64 [[TMP15]]
172; LV-NEXT:    [[TMP18:%.*]] = icmp ugt i8* [[TMP17]], [[SCEVGEP5]]
173; LV-NEXT:    [[TMP21:%.*]] = or i1 [[TMP18]], [[MUL_OVERFLOW4]]
174; LV-NEXT:    [[TMP22:%.*]] = or i1 [[TMP10]], [[TMP21]]
175; LV-NEXT:    br i1 [[TMP22]], label [[FOR_BODY_PH_LVER_ORIG:%.*]], label [[FOR_BODY_PH:%.*]]
176; LV:       for.body.ph.lver.orig:
177; LV-NEXT:    br label [[FOR_BODY_LVER_ORIG:%.*]]
178; LV:       for.body.lver.orig:
179; LV-NEXT:    [[IND_LVER_ORIG:%.*]] = phi i64 [ 0, [[FOR_BODY_PH_LVER_ORIG]] ], [ [[INC_LVER_ORIG:%.*]], [[FOR_BODY_LVER_ORIG]] ]
180; LV-NEXT:    [[IND1_LVER_ORIG:%.*]] = phi i32 [ [[TRUNCN]], [[FOR_BODY_PH_LVER_ORIG]] ], [ [[DEC_LVER_ORIG:%.*]], [[FOR_BODY_LVER_ORIG]] ]
181; LV-NEXT:    [[MUL_LVER_ORIG:%.*]] = mul i32 [[IND1_LVER_ORIG]], 2
182; LV-NEXT:    [[MUL_EXT_LVER_ORIG:%.*]] = zext i32 [[MUL_LVER_ORIG]] to i64
183; LV-NEXT:    [[ARRAYIDXA_LVER_ORIG:%.*]] = getelementptr i16, i16* [[A]], i64 [[MUL_EXT_LVER_ORIG]]
184; LV-NEXT:    [[LOADA_LVER_ORIG:%.*]] = load i16, i16* [[ARRAYIDXA_LVER_ORIG]], align 2
185; LV-NEXT:    [[ARRAYIDXB_LVER_ORIG:%.*]] = getelementptr i16, i16* [[B:%.*]], i64 [[IND_LVER_ORIG]]
186; LV-NEXT:    [[LOADB_LVER_ORIG:%.*]] = load i16, i16* [[ARRAYIDXB_LVER_ORIG]], align 2
187; LV-NEXT:    [[ADD_LVER_ORIG:%.*]] = mul i16 [[LOADA_LVER_ORIG]], [[LOADB_LVER_ORIG]]
188; LV-NEXT:    store i16 [[ADD_LVER_ORIG]], i16* [[ARRAYIDXA_LVER_ORIG]], align 2
189; LV-NEXT:    [[INC_LVER_ORIG]] = add nuw nsw i64 [[IND_LVER_ORIG]], 1
190; LV-NEXT:    [[DEC_LVER_ORIG]] = sub i32 [[IND1_LVER_ORIG]], 1
191; LV-NEXT:    [[EXITCOND_LVER_ORIG:%.*]] = icmp eq i64 [[INC_LVER_ORIG]], [[N]]
192; LV-NEXT:    br i1 [[EXITCOND_LVER_ORIG]], label [[FOR_END_LOOPEXIT:%.*]], label [[FOR_BODY_LVER_ORIG]]
193; LV:       for.body.ph:
194; LV-NEXT:    br label [[FOR_BODY:%.*]]
195; LV:       for.body:
196; LV-NEXT:    [[IND:%.*]] = phi i64 [ 0, [[FOR_BODY_PH]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
197; LV-NEXT:    [[IND1:%.*]] = phi i32 [ [[TRUNCN]], [[FOR_BODY_PH]] ], [ [[DEC:%.*]], [[FOR_BODY]] ]
198; LV-NEXT:    [[MUL:%.*]] = mul i32 [[IND1]], 2
199; LV-NEXT:    [[MUL_EXT:%.*]] = zext i32 [[MUL]] to i64
200; LV-NEXT:    [[ARRAYIDXA:%.*]] = getelementptr i16, i16* [[A]], i64 [[MUL_EXT]]
201; LV-NEXT:    [[LOADA:%.*]] = load i16, i16* [[ARRAYIDXA]], align 2
202; LV-NEXT:    [[ARRAYIDXB:%.*]] = getelementptr i16, i16* [[B]], i64 [[IND]]
203; LV-NEXT:    [[LOADB:%.*]] = load i16, i16* [[ARRAYIDXB]], align 2
204; LV-NEXT:    [[ADD:%.*]] = mul i16 [[LOADA]], [[LOADB]]
205; LV-NEXT:    store i16 [[ADD]], i16* [[ARRAYIDXA]], align 2
206; LV-NEXT:    [[INC]] = add nuw nsw i64 [[IND]], 1
207; LV-NEXT:    [[DEC]] = sub i32 [[IND1]], 1
208; LV-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INC]], [[N]]
209; LV-NEXT:    br i1 [[EXITCOND]], label [[FOR_END_LOOPEXIT6:%.*]], label [[FOR_BODY]]
210; LV:       for.end.loopexit:
211; LV-NEXT:    br label [[FOR_END:%.*]]
212; LV:       for.end.loopexit6:
213; LV-NEXT:    br label [[FOR_END]]
214; LV:       for.end:
215; LV-NEXT:    ret void
216;
217  i16* noalias %b, i64 %N) {
218entry:
219  %TruncN = trunc i64 %N to i32
220  br label %for.body
221
222for.body:                                         ; preds = %for.body, %entry
223  %ind = phi i64 [ 0, %entry ], [ %inc, %for.body ]
224  %ind1 = phi i32 [ %TruncN, %entry ], [ %dec, %for.body ]
225
226  %mul = mul i32 %ind1, 2
227  %mul_ext = zext i32 %mul to i64
228
229  %arrayidxA = getelementptr i16, i16* %a, i64 %mul_ext
230  %loadA = load i16, i16* %arrayidxA, align 2
231
232  %arrayidxB = getelementptr i16, i16* %b, i64 %ind
233  %loadB = load i16, i16* %arrayidxB, align 2
234
235  %add = mul i16 %loadA, %loadB
236
237  store i16 %add, i16* %arrayidxA, align 2
238
239  %inc = add nuw nsw i64 %ind, 1
240  %dec = sub i32 %ind1, 1
241
242  %exitcond = icmp eq i64 %inc, %N
243  br i1 %exitcond, label %for.end, label %for.body
244
245for.end:                                          ; preds = %for.body
246  ret void
247}
248
249; We replicate the tests above, but this time sign extend 2 * index instead
250; of zero extending it.
251
252; The expression for %mul_ext as analyzed by SCEV is
253;     i64 (sext i32 {0,+,2}<%for.body> to i64)
254; We have added the nssw flag to turn this expression into the following SCEV:
255;     i64 {0,+,2}<%for.body>
256
257define void @f3(i16* noalias %a,
258; LV-LABEL: @f3(
259; LV-NEXT:  for.body.lver.check:
260; LV-NEXT:    [[A5:%.*]] = bitcast i16* [[A:%.*]] to i8*
261; LV-NEXT:    [[TMP0:%.*]] = add i64 [[N:%.*]], -1
262; LV-NEXT:    [[TMP1:%.*]] = trunc i64 [[TMP0]] to i32
263; LV-NEXT:    [[MUL1:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 2, i32 [[TMP1]])
264; LV-NEXT:    [[MUL_RESULT:%.*]] = extractvalue { i32, i1 } [[MUL1]], 0
265; LV-NEXT:    [[MUL_OVERFLOW:%.*]] = extractvalue { i32, i1 } [[MUL1]], 1
266; LV-NEXT:    [[TMP2:%.*]] = add i32 0, [[MUL_RESULT]]
267; LV-NEXT:    [[TMP5:%.*]] = icmp slt i32 [[TMP2]], 0
268; LV-NEXT:    [[TMP7:%.*]] = icmp ugt i64 [[TMP0]], 4294967295
269; LV-NEXT:    [[TMP8:%.*]] = or i1 [[TMP5]], [[TMP7]]
270; LV-NEXT:    [[TMP9:%.*]] = or i1 [[TMP8]], [[MUL_OVERFLOW]]
271; LV-NEXT:    [[MUL2:%.*]] = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 4, i64 [[TMP0]])
272; LV-NEXT:    [[MUL_RESULT3:%.*]] = extractvalue { i64, i1 } [[MUL2]], 0
273; LV-NEXT:    [[MUL_OVERFLOW4:%.*]] = extractvalue { i64, i1 } [[MUL2]], 1
274; LV-NEXT:    [[TMP11:%.*]] = sub i64 0, [[MUL_RESULT3]]
275; LV-NEXT:    [[TMP12:%.*]] = getelementptr i8, i8* [[A5]], i64 [[MUL_RESULT3]]
276; LV-NEXT:    [[TMP15:%.*]] = icmp ult i8* [[TMP12]], [[A5]]
277; LV-NEXT:    [[TMP17:%.*]] = or i1 [[TMP15]], [[MUL_OVERFLOW4]]
278; LV-NEXT:    [[TMP18:%.*]] = or i1 [[TMP9]], [[TMP17]]
279; LV-NEXT:    br i1 [[TMP18]], label [[FOR_BODY_PH_LVER_ORIG:%.*]], label [[FOR_BODY_PH:%.*]]
280; LV:       for.body.ph.lver.orig:
281; LV-NEXT:    br label [[FOR_BODY_LVER_ORIG:%.*]]
282; LV:       for.body.lver.orig:
283; LV-NEXT:    [[IND_LVER_ORIG:%.*]] = phi i64 [ 0, [[FOR_BODY_PH_LVER_ORIG]] ], [ [[INC_LVER_ORIG:%.*]], [[FOR_BODY_LVER_ORIG]] ]
284; LV-NEXT:    [[IND1_LVER_ORIG:%.*]] = phi i32 [ 0, [[FOR_BODY_PH_LVER_ORIG]] ], [ [[INC1_LVER_ORIG:%.*]], [[FOR_BODY_LVER_ORIG]] ]
285; LV-NEXT:    [[MUL_LVER_ORIG:%.*]] = mul i32 [[IND1_LVER_ORIG]], 2
286; LV-NEXT:    [[MUL_EXT_LVER_ORIG:%.*]] = sext i32 [[MUL_LVER_ORIG]] to i64
287; LV-NEXT:    [[ARRAYIDXA_LVER_ORIG:%.*]] = getelementptr i16, i16* [[A]], i64 [[MUL_EXT_LVER_ORIG]]
288; LV-NEXT:    [[LOADA_LVER_ORIG:%.*]] = load i16, i16* [[ARRAYIDXA_LVER_ORIG]], align 2
289; LV-NEXT:    [[ARRAYIDXB_LVER_ORIG:%.*]] = getelementptr i16, i16* [[B:%.*]], i64 [[IND_LVER_ORIG]]
290; LV-NEXT:    [[LOADB_LVER_ORIG:%.*]] = load i16, i16* [[ARRAYIDXB_LVER_ORIG]], align 2
291; LV-NEXT:    [[ADD_LVER_ORIG:%.*]] = mul i16 [[LOADA_LVER_ORIG]], [[LOADB_LVER_ORIG]]
292; LV-NEXT:    store i16 [[ADD_LVER_ORIG]], i16* [[ARRAYIDXA_LVER_ORIG]], align 2
293; LV-NEXT:    [[INC_LVER_ORIG]] = add nuw nsw i64 [[IND_LVER_ORIG]], 1
294; LV-NEXT:    [[INC1_LVER_ORIG]] = add i32 [[IND1_LVER_ORIG]], 1
295; LV-NEXT:    [[EXITCOND_LVER_ORIG:%.*]] = icmp eq i64 [[INC_LVER_ORIG]], [[N]]
296; LV-NEXT:    br i1 [[EXITCOND_LVER_ORIG]], label [[FOR_END_LOOPEXIT:%.*]], label [[FOR_BODY_LVER_ORIG]]
297; LV:       for.body.ph:
298; LV-NEXT:    br label [[FOR_BODY:%.*]]
299; LV:       for.body:
300; LV-NEXT:    [[IND:%.*]] = phi i64 [ 0, [[FOR_BODY_PH]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
301; LV-NEXT:    [[IND1:%.*]] = phi i32 [ 0, [[FOR_BODY_PH]] ], [ [[INC1:%.*]], [[FOR_BODY]] ]
302; LV-NEXT:    [[MUL:%.*]] = mul i32 [[IND1]], 2
303; LV-NEXT:    [[MUL_EXT:%.*]] = sext i32 [[MUL]] to i64
304; LV-NEXT:    [[ARRAYIDXA:%.*]] = getelementptr i16, i16* [[A]], i64 [[MUL_EXT]]
305; LV-NEXT:    [[LOADA:%.*]] = load i16, i16* [[ARRAYIDXA]], align 2
306; LV-NEXT:    [[ARRAYIDXB:%.*]] = getelementptr i16, i16* [[B]], i64 [[IND]]
307; LV-NEXT:    [[LOADB:%.*]] = load i16, i16* [[ARRAYIDXB]], align 2
308; LV-NEXT:    [[ADD:%.*]] = mul i16 [[LOADA]], [[LOADB]]
309; LV-NEXT:    store i16 [[ADD]], i16* [[ARRAYIDXA]], align 2
310; LV-NEXT:    [[INC]] = add nuw nsw i64 [[IND]], 1
311; LV-NEXT:    [[INC1]] = add i32 [[IND1]], 1
312; LV-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INC]], [[N]]
313; LV-NEXT:    br i1 [[EXITCOND]], label [[FOR_END_LOOPEXIT6:%.*]], label [[FOR_BODY]]
314; LV:       for.end.loopexit:
315; LV-NEXT:    br label [[FOR_END:%.*]]
316; LV:       for.end.loopexit6:
317; LV-NEXT:    br label [[FOR_END]]
318; LV:       for.end:
319; LV-NEXT:    ret void
320;
321  i16* noalias %b, i64 %N) {
322entry:
323  br label %for.body
324
325for.body:                                         ; preds = %for.body, %entry
326  %ind = phi i64 [ 0, %entry ], [ %inc, %for.body ]
327  %ind1 = phi i32 [ 0, %entry ], [ %inc1, %for.body ]
328
329  %mul = mul i32 %ind1, 2
330  %mul_ext = sext i32 %mul to i64
331
332  %arrayidxA = getelementptr i16, i16* %a, i64 %mul_ext
333  %loadA = load i16, i16* %arrayidxA, align 2
334
335  %arrayidxB = getelementptr i16, i16* %b, i64 %ind
336  %loadB = load i16, i16* %arrayidxB, align 2
337
338  %add = mul i16 %loadA, %loadB
339
340  store i16 %add, i16* %arrayidxA, align 2
341
342  %inc = add nuw nsw i64 %ind, 1
343  %inc1 = add i32 %ind1, 1
344
345  %exitcond = icmp eq i64 %inc, %N
346  br i1 %exitcond, label %for.end, label %for.body
347
348for.end:                                          ; preds = %for.body
349  ret void
350}
351
352define void @f4(i16* noalias %a,
353; LV-LABEL: @f4(
354; LV-NEXT:  for.body.lver.check:
355; LV-NEXT:    [[TRUNCN:%.*]] = trunc i64 [[N:%.*]] to i32
356; LV-NEXT:    [[TMP0:%.*]] = add i64 [[N]], -1
357; LV-NEXT:    [[TMP1:%.*]] = shl i32 [[TRUNCN]], 1
358; LV-NEXT:    [[TMP2:%.*]] = trunc i64 [[TMP0]] to i32
359; LV-NEXT:    [[MUL1:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 2, i32 [[TMP2]])
360; LV-NEXT:    [[MUL_RESULT:%.*]] = extractvalue { i32, i1 } [[MUL1]], 0
361; LV-NEXT:    [[MUL_OVERFLOW:%.*]] = extractvalue { i32, i1 } [[MUL1]], 1
362; LV-NEXT:    [[TMP4:%.*]] = sub i32 [[TMP1]], [[MUL_RESULT]]
363; LV-NEXT:    [[TMP5:%.*]] = icmp sgt i32 [[TMP4]], [[TMP1]]
364; LV-NEXT:    [[TMP8:%.*]] = icmp ugt i64 [[TMP0]], 4294967295
365; LV-NEXT:    [[TMP9:%.*]] = or i1 [[TMP5]], [[TMP8]]
366; LV-NEXT:    [[TMP10:%.*]] = or i1 [[TMP9]], [[MUL_OVERFLOW]]
367; LV-NEXT:    [[TMP12:%.*]] = sext i32 [[TMP1]] to i64
368; LV-NEXT:    [[SCEVGEP:%.*]] = getelementptr i16, i16* [[A:%.*]], i64 [[TMP12]]
369; LV-NEXT:    [[MUL2:%.*]] = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 4, i64 [[TMP0]])
370; LV-NEXT:    [[MUL_RESULT3:%.*]] = extractvalue { i64, i1 } [[MUL2]], 0
371; LV-NEXT:    [[MUL_OVERFLOW4:%.*]] = extractvalue { i64, i1 } [[MUL2]], 1
372; LV-NEXT:    [[SCEVGEP5:%.*]] = bitcast i16* [[SCEVGEP]] to i8*
373; LV-NEXT:    [[TMP13:%.*]] = sub i64 0, [[MUL_RESULT3]]
374; LV-NEXT:    [[TMP15:%.*]] = getelementptr i8, i8* [[SCEVGEP5]], i64 [[TMP13]]
375; LV-NEXT:    [[TMP16:%.*]] = icmp ugt i8* [[TMP15]], [[SCEVGEP5]]
376; LV-NEXT:    [[TMP19:%.*]] = or i1 [[TMP16]], [[MUL_OVERFLOW4]]
377; LV-NEXT:    [[TMP20:%.*]] = or i1 [[TMP10]], [[TMP19]]
378; LV-NEXT:    br i1 [[TMP20]], label [[FOR_BODY_PH_LVER_ORIG:%.*]], label [[FOR_BODY_PH:%.*]]
379; LV:       for.body.ph.lver.orig:
380; LV-NEXT:    br label [[FOR_BODY_LVER_ORIG:%.*]]
381; LV:       for.body.lver.orig:
382; LV-NEXT:    [[IND_LVER_ORIG:%.*]] = phi i64 [ 0, [[FOR_BODY_PH_LVER_ORIG]] ], [ [[INC_LVER_ORIG:%.*]], [[FOR_BODY_LVER_ORIG]] ]
383; LV-NEXT:    [[IND1_LVER_ORIG:%.*]] = phi i32 [ [[TRUNCN]], [[FOR_BODY_PH_LVER_ORIG]] ], [ [[DEC_LVER_ORIG:%.*]], [[FOR_BODY_LVER_ORIG]] ]
384; LV-NEXT:    [[MUL_LVER_ORIG:%.*]] = mul i32 [[IND1_LVER_ORIG]], 2
385; LV-NEXT:    [[MUL_EXT_LVER_ORIG:%.*]] = sext i32 [[MUL_LVER_ORIG]] to i64
386; LV-NEXT:    [[ARRAYIDXA_LVER_ORIG:%.*]] = getelementptr i16, i16* [[A]], i64 [[MUL_EXT_LVER_ORIG]]
387; LV-NEXT:    [[LOADA_LVER_ORIG:%.*]] = load i16, i16* [[ARRAYIDXA_LVER_ORIG]], align 2
388; LV-NEXT:    [[ARRAYIDXB_LVER_ORIG:%.*]] = getelementptr i16, i16* [[B:%.*]], i64 [[IND_LVER_ORIG]]
389; LV-NEXT:    [[LOADB_LVER_ORIG:%.*]] = load i16, i16* [[ARRAYIDXB_LVER_ORIG]], align 2
390; LV-NEXT:    [[ADD_LVER_ORIG:%.*]] = mul i16 [[LOADA_LVER_ORIG]], [[LOADB_LVER_ORIG]]
391; LV-NEXT:    store i16 [[ADD_LVER_ORIG]], i16* [[ARRAYIDXA_LVER_ORIG]], align 2
392; LV-NEXT:    [[INC_LVER_ORIG]] = add nuw nsw i64 [[IND_LVER_ORIG]], 1
393; LV-NEXT:    [[DEC_LVER_ORIG]] = sub i32 [[IND1_LVER_ORIG]], 1
394; LV-NEXT:    [[EXITCOND_LVER_ORIG:%.*]] = icmp eq i64 [[INC_LVER_ORIG]], [[N]]
395; LV-NEXT:    br i1 [[EXITCOND_LVER_ORIG]], label [[FOR_END_LOOPEXIT:%.*]], label [[FOR_BODY_LVER_ORIG]]
396; LV:       for.body.ph:
397; LV-NEXT:    br label [[FOR_BODY:%.*]]
398; LV:       for.body:
399; LV-NEXT:    [[IND:%.*]] = phi i64 [ 0, [[FOR_BODY_PH]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
400; LV-NEXT:    [[IND1:%.*]] = phi i32 [ [[TRUNCN]], [[FOR_BODY_PH]] ], [ [[DEC:%.*]], [[FOR_BODY]] ]
401; LV-NEXT:    [[MUL:%.*]] = mul i32 [[IND1]], 2
402; LV-NEXT:    [[MUL_EXT:%.*]] = sext i32 [[MUL]] to i64
403; LV-NEXT:    [[ARRAYIDXA:%.*]] = getelementptr i16, i16* [[A]], i64 [[MUL_EXT]]
404; LV-NEXT:    [[LOADA:%.*]] = load i16, i16* [[ARRAYIDXA]], align 2
405; LV-NEXT:    [[ARRAYIDXB:%.*]] = getelementptr i16, i16* [[B]], i64 [[IND]]
406; LV-NEXT:    [[LOADB:%.*]] = load i16, i16* [[ARRAYIDXB]], align 2
407; LV-NEXT:    [[ADD:%.*]] = mul i16 [[LOADA]], [[LOADB]]
408; LV-NEXT:    store i16 [[ADD]], i16* [[ARRAYIDXA]], align 2
409; LV-NEXT:    [[INC]] = add nuw nsw i64 [[IND]], 1
410; LV-NEXT:    [[DEC]] = sub i32 [[IND1]], 1
411; LV-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INC]], [[N]]
412; LV-NEXT:    br i1 [[EXITCOND]], label [[FOR_END_LOOPEXIT6:%.*]], label [[FOR_BODY]]
413; LV:       for.end.loopexit:
414; LV-NEXT:    br label [[FOR_END:%.*]]
415; LV:       for.end.loopexit6:
416; LV-NEXT:    br label [[FOR_END]]
417; LV:       for.end:
418; LV-NEXT:    ret void
419;
420  i16* noalias %b, i64 %N) {
421entry:
422  %TruncN = trunc i64 %N to i32
423  br label %for.body
424
425for.body:                                         ; preds = %for.body, %entry
426  %ind = phi i64 [ 0, %entry ], [ %inc, %for.body ]
427  %ind1 = phi i32 [ %TruncN, %entry ], [ %dec, %for.body ]
428
429  %mul = mul i32 %ind1, 2
430  %mul_ext = sext i32 %mul to i64
431
432  %arrayidxA = getelementptr i16, i16* %a, i64 %mul_ext
433  %loadA = load i16, i16* %arrayidxA, align 2
434
435  %arrayidxB = getelementptr i16, i16* %b, i64 %ind
436  %loadB = load i16, i16* %arrayidxB, align 2
437
438  %add = mul i16 %loadA, %loadB
439
440  store i16 %add, i16* %arrayidxA, align 2
441
442  %inc = add nuw nsw i64 %ind, 1
443  %dec = sub i32 %ind1, 1
444
445  %exitcond = icmp eq i64 %inc, %N
446  br i1 %exitcond, label %for.end, label %for.body
447
448for.end:                                          ; preds = %for.body
449  ret void
450}
451
452; The following function is similar to the one above, but has the GEP
453; to pointer %A inbounds. The index %mul doesn't have the nsw flag.
454; This means that the SCEV expression for %mul can wrap and we need
455; a SCEV predicate to continue analysis.
456;
457; We can still analyze this by adding the required no wrap SCEV predicates.
458
459define void @f5(i16* noalias %a,
460; LV-LABEL: @f5(
461; LV-NEXT:  for.body.lver.check:
462; LV-NEXT:    [[TRUNCN:%.*]] = trunc i64 [[N:%.*]] to i32
463; LV-NEXT:    [[TMP0:%.*]] = add i64 [[N]], -1
464; LV-NEXT:    [[TMP1:%.*]] = shl i32 [[TRUNCN]], 1
465; LV-NEXT:    [[TMP2:%.*]] = trunc i64 [[TMP0]] to i32
466; LV-NEXT:    [[MUL1:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 2, i32 [[TMP2]])
467; LV-NEXT:    [[MUL_RESULT:%.*]] = extractvalue { i32, i1 } [[MUL1]], 0
468; LV-NEXT:    [[MUL_OVERFLOW:%.*]] = extractvalue { i32, i1 } [[MUL1]], 1
469; LV-NEXT:    [[TMP4:%.*]] = sub i32 [[TMP1]], [[MUL_RESULT]]
470; LV-NEXT:    [[TMP5:%.*]] = icmp sgt i32 [[TMP4]], [[TMP1]]
471; LV-NEXT:    [[TMP8:%.*]] = icmp ugt i64 [[TMP0]], 4294967295
472; LV-NEXT:    [[TMP9:%.*]] = or i1 [[TMP5]], [[TMP8]]
473; LV-NEXT:    [[TMP10:%.*]] = or i1 [[TMP9]], [[MUL_OVERFLOW]]
474; LV-NEXT:    [[TMP12:%.*]] = sext i32 [[TMP1]] to i64
475; LV-NEXT:    [[SCEVGEP:%.*]] = getelementptr i16, i16* [[A:%.*]], i64 [[TMP12]]
476; LV-NEXT:    [[MUL2:%.*]] = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 4, i64 [[TMP0]])
477; LV-NEXT:    [[MUL_RESULT3:%.*]] = extractvalue { i64, i1 } [[MUL2]], 0
478; LV-NEXT:    [[MUL_OVERFLOW4:%.*]] = extractvalue { i64, i1 } [[MUL2]], 1
479; LV-NEXT:    [[SCEVGEP5:%.*]] = bitcast i16* [[SCEVGEP]] to i8*
480; LV-NEXT:    [[TMP13:%.*]] = sub i64 0, [[MUL_RESULT3]]
481; LV-NEXT:    [[TMP15:%.*]] = getelementptr i8, i8* [[SCEVGEP5]], i64 [[TMP13]]
482; LV-NEXT:    [[TMP16:%.*]] = icmp ugt i8* [[TMP15]], [[SCEVGEP5]]
483; LV-NEXT:    [[TMP19:%.*]] = or i1 [[TMP16]], [[MUL_OVERFLOW4]]
484; LV-NEXT:    [[TMP20:%.*]] = or i1 [[TMP10]], [[TMP19]]
485; LV-NEXT:    br i1 [[TMP20]], label [[FOR_BODY_PH_LVER_ORIG:%.*]], label [[FOR_BODY_PH:%.*]]
486; LV:       for.body.ph.lver.orig:
487; LV-NEXT:    br label [[FOR_BODY_LVER_ORIG:%.*]]
488; LV:       for.body.lver.orig:
489; LV-NEXT:    [[IND_LVER_ORIG:%.*]] = phi i64 [ 0, [[FOR_BODY_PH_LVER_ORIG]] ], [ [[INC_LVER_ORIG:%.*]], [[FOR_BODY_LVER_ORIG]] ]
490; LV-NEXT:    [[IND1_LVER_ORIG:%.*]] = phi i32 [ [[TRUNCN]], [[FOR_BODY_PH_LVER_ORIG]] ], [ [[DEC_LVER_ORIG:%.*]], [[FOR_BODY_LVER_ORIG]] ]
491; LV-NEXT:    [[MUL_LVER_ORIG:%.*]] = mul i32 [[IND1_LVER_ORIG]], 2
492; LV-NEXT:    [[ARRAYIDXA_LVER_ORIG:%.*]] = getelementptr inbounds i16, i16* [[A]], i32 [[MUL_LVER_ORIG]]
493; LV-NEXT:    [[LOADA_LVER_ORIG:%.*]] = load i16, i16* [[ARRAYIDXA_LVER_ORIG]], align 2
494; LV-NEXT:    [[ARRAYIDXB_LVER_ORIG:%.*]] = getelementptr inbounds i16, i16* [[B:%.*]], i64 [[IND_LVER_ORIG]]
495; LV-NEXT:    [[LOADB_LVER_ORIG:%.*]] = load i16, i16* [[ARRAYIDXB_LVER_ORIG]], align 2
496; LV-NEXT:    [[ADD_LVER_ORIG:%.*]] = mul i16 [[LOADA_LVER_ORIG]], [[LOADB_LVER_ORIG]]
497; LV-NEXT:    store i16 [[ADD_LVER_ORIG]], i16* [[ARRAYIDXA_LVER_ORIG]], align 2
498; LV-NEXT:    [[INC_LVER_ORIG]] = add nuw nsw i64 [[IND_LVER_ORIG]], 1
499; LV-NEXT:    [[DEC_LVER_ORIG]] = sub i32 [[IND1_LVER_ORIG]], 1
500; LV-NEXT:    [[EXITCOND_LVER_ORIG:%.*]] = icmp eq i64 [[INC_LVER_ORIG]], [[N]]
501; LV-NEXT:    br i1 [[EXITCOND_LVER_ORIG]], label [[FOR_END_LOOPEXIT:%.*]], label [[FOR_BODY_LVER_ORIG]]
502; LV:       for.body.ph:
503; LV-NEXT:    br label [[FOR_BODY:%.*]]
504; LV:       for.body:
505; LV-NEXT:    [[IND:%.*]] = phi i64 [ 0, [[FOR_BODY_PH]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
506; LV-NEXT:    [[IND1:%.*]] = phi i32 [ [[TRUNCN]], [[FOR_BODY_PH]] ], [ [[DEC:%.*]], [[FOR_BODY]] ]
507; LV-NEXT:    [[MUL:%.*]] = mul i32 [[IND1]], 2
508; LV-NEXT:    [[ARRAYIDXA:%.*]] = getelementptr inbounds i16, i16* [[A]], i32 [[MUL]]
509; LV-NEXT:    [[LOADA:%.*]] = load i16, i16* [[ARRAYIDXA]], align 2
510; LV-NEXT:    [[ARRAYIDXB:%.*]] = getelementptr inbounds i16, i16* [[B]], i64 [[IND]]
511; LV-NEXT:    [[LOADB:%.*]] = load i16, i16* [[ARRAYIDXB]], align 2
512; LV-NEXT:    [[ADD:%.*]] = mul i16 [[LOADA]], [[LOADB]]
513; LV-NEXT:    store i16 [[ADD]], i16* [[ARRAYIDXA]], align 2
514; LV-NEXT:    [[INC]] = add nuw nsw i64 [[IND]], 1
515; LV-NEXT:    [[DEC]] = sub i32 [[IND1]], 1
516; LV-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INC]], [[N]]
517; LV-NEXT:    br i1 [[EXITCOND]], label [[FOR_END_LOOPEXIT6:%.*]], label [[FOR_BODY]]
518; LV:       for.end.loopexit:
519; LV-NEXT:    br label [[FOR_END:%.*]]
520; LV:       for.end.loopexit6:
521; LV-NEXT:    br label [[FOR_END]]
522; LV:       for.end:
523; LV-NEXT:    ret void
524;
525  i16* noalias %b, i64 %N) {
526entry:
527  %TruncN = trunc i64 %N to i32
528  br label %for.body
529
530for.body:                                         ; preds = %for.body, %entry
531  %ind = phi i64 [ 0, %entry ], [ %inc, %for.body ]
532  %ind1 = phi i32 [ %TruncN, %entry ], [ %dec, %for.body ]
533
534  %mul = mul i32 %ind1, 2
535
536  %arrayidxA = getelementptr inbounds i16, i16* %a, i32 %mul
537  %loadA = load i16, i16* %arrayidxA, align 2
538
539  %arrayidxB = getelementptr inbounds i16, i16* %b, i64 %ind
540  %loadB = load i16, i16* %arrayidxB, align 2
541
542  %add = mul i16 %loadA, %loadB
543
544  store i16 %add, i16* %arrayidxA, align 2
545
546  %inc = add nuw nsw i64 %ind, 1
547  %dec = sub i32 %ind1, 1
548
549  %exitcond = icmp eq i64 %inc, %N
550  br i1 %exitcond, label %for.end, label %for.body
551
552for.end:                                          ; preds = %for.body
553  ret void
554}
555