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