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