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