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