534 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt -passes=loop-versioning -S < %s | FileCheck %s -check-prefix=LV3 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 not16; affine AddRecExprs. However, we can turn them into AddRecExprs17; using SCEV Predicates.18;19; Once we have an affine expression we need to add an additional NUSW20; to check that the pointers don't wrap since the GEPs are not21; inbound.22 23; The expression for %mul_ext as analyzed by SCEV is24; (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:%.*]], -132; LV-NEXT: [[TMP5:%.*]] = trunc i64 [[TMP0]] to i3233; LV-NEXT: [[MUL2:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 2, i32 [[TMP5]])34; LV-NEXT: [[MUL_OVERFLOW1:%.*]] = extractvalue { i32, i1 } [[MUL2]], 135; LV-NEXT: [[TMP1:%.*]] = icmp ugt i64 [[TMP0]], 429496729536; LV-NEXT: [[TMP8:%.*]] = or i1 [[MUL_OVERFLOW1]], [[TMP1]]37; LV-NEXT: [[MUL1:%.*]] = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 4, i64 [[TMP0]])38; LV-NEXT: [[MUL_RESULT:%.*]] = extractvalue { i64, i1 } [[MUL1]], 039; LV-NEXT: [[MUL_OVERFLOW:%.*]] = extractvalue { i64, i1 } [[MUL1]], 140; LV-NEXT: [[TMP3:%.*]] = getelementptr i8, ptr [[A:%.*]], i64 [[MUL_RESULT]]41; LV-NEXT: [[TMP4:%.*]] = icmp ult ptr [[TMP3]], [[A]]42; LV-NEXT: [[TMP6:%.*]] = or i1 [[TMP4]], [[MUL_OVERFLOW]]43; LV-NEXT: [[TMP7:%.*]] = or i1 [[TMP8]], [[TMP6]]44; LV-NEXT: br i1 [[TMP7]], 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]], 251; LV-NEXT: [[MUL_EXT_LVER_ORIG:%.*]] = zext i32 [[MUL_LVER_ORIG]] to i6452; LV-NEXT: [[ARRAYIDXA_LVER_ORIG:%.*]] = getelementptr i16, ptr [[A]], i64 [[MUL_EXT_LVER_ORIG]]53; LV-NEXT: [[LOADA_LVER_ORIG:%.*]] = load i16, ptr [[ARRAYIDXA_LVER_ORIG]], align 254; LV-NEXT: [[ARRAYIDXB_LVER_ORIG:%.*]] = getelementptr i16, ptr [[B:%.*]], i64 [[IND_LVER_ORIG]]55; LV-NEXT: [[LOADB_LVER_ORIG:%.*]] = load i16, ptr [[ARRAYIDXB_LVER_ORIG]], align 256; LV-NEXT: [[ADD_LVER_ORIG:%.*]] = mul i16 [[LOADA_LVER_ORIG]], [[LOADB_LVER_ORIG]]57; LV-NEXT: store i16 [[ADD_LVER_ORIG]], ptr [[ARRAYIDXA_LVER_ORIG]], align 258; LV-NEXT: [[INC_LVER_ORIG]] = add nuw nsw i64 [[IND_LVER_ORIG]], 159; LV-NEXT: [[INC1_LVER_ORIG]] = add i32 [[IND1_LVER_ORIG]], 160; 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]], 268; LV-NEXT: [[MUL_EXT:%.*]] = zext i32 [[MUL]] to i6469; LV-NEXT: [[ARRAYIDXA:%.*]] = getelementptr i16, ptr [[A]], i64 [[MUL_EXT]]70; LV-NEXT: [[LOADA:%.*]] = load i16, ptr [[ARRAYIDXA]], align 271; LV-NEXT: [[ARRAYIDXB:%.*]] = getelementptr i16, ptr [[B]], i64 [[IND]]72; LV-NEXT: [[LOADB:%.*]] = load i16, ptr [[ARRAYIDXB]], align 273; LV-NEXT: [[ADD:%.*]] = mul i16 [[LOADA]], [[LOADB]]74; LV-NEXT: store i16 [[ADD]], ptr [[ARRAYIDXA]], align 275; LV-NEXT: [[INC]] = add nuw nsw i64 [[IND]], 176; LV-NEXT: [[INC1]] = add i32 [[IND1]], 177; LV-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[INC]], [[N]]78; LV-NEXT: br i1 [[EXITCOND]], label [[FOR_END_LOOPEXIT2:%.*]], label [[FOR_BODY]]79; LV: for.end.loopexit:80; LV-NEXT: br label [[FOR_END:%.*]]81; LV: for.end.loopexit5:82; LV-NEXT: br label [[FOR_END]]83; LV: for.end:84; LV-NEXT: ret void85;86 ptr noalias %b, i64 %N) {87entry:88 br label %for.body89 90for.body: ; preds = %for.body, %entry91 %ind = phi i64 [ 0, %entry ], [ %inc, %for.body ]92 %ind1 = phi i32 [ 0, %entry ], [ %inc1, %for.body ]93 94 %mul = mul i32 %ind1, 295 %mul_ext = zext i32 %mul to i6496 97 %arrayidxA = getelementptr i16, ptr %a, i64 %mul_ext98 %loadA = load i16, ptr %arrayidxA, align 299 100 %arrayidxB = getelementptr i16, ptr %b, i64 %ind101 %loadB = load i16, ptr %arrayidxB, align 2102 103 %add = mul i16 %loadA, %loadB104 105 store i16 %add, ptr %arrayidxA, align 2106 107 %inc = add nuw nsw i64 %ind, 1108 %inc1 = add i32 %ind1, 1109 110 %exitcond = icmp eq i64 %inc, %N111 br i1 %exitcond, label %for.end, label %for.body112 113for.end: ; preds = %for.body114 ret void115}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 AddRecExpr125; (and implictly not affine). However, we are able to make assumptions126; that will turn the expression into an affine one and continue the127; analysis.128;129; Once we have an affine expression we need to add an additional NUSW130; to check that the pointers don't wrap since the GEPs are not131; inbounds.132;133; This loop has a negative stride for A, and the nusw flag is required in134; order to properly extend the increment from i32 -4 to i64 -4.135 136; The expression for %mul_ext as analyzed by SCEV is137; (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(ptr noalias %a,142; LV-LABEL: @f2(143; LV-NEXT: for.body.lver.check:144; LV-NEXT: [[TRUNCN:%.*]] = trunc i64 [[N:%.*]] to i32145; LV-NEXT: [[TMP0:%.*]] = add i64 [[N]], -1146; LV-NEXT: [[TMP1:%.*]] = shl i32 [[TRUNCN]], 1147; LV-NEXT: [[TMP2:%.*]] = trunc i64 [[TMP0]] to i32148; LV-NEXT: [[MUL1:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 2, i32 [[TMP2]])149; LV-NEXT: [[MUL_RESULT:%.*]] = extractvalue { i32, i1 } [[MUL1]], 0150; LV-NEXT: [[MUL_OVERFLOW:%.*]] = extractvalue { i32, i1 } [[MUL1]], 1151; LV-NEXT: [[TMP3:%.*]] = sub i32 [[TMP1]], [[MUL_RESULT]]152; LV-NEXT: [[TMP4:%.*]] = icmp ugt i32 [[TMP3]], [[TMP1]]153; LV-NEXT: [[TMP5:%.*]] = or i1 [[TMP4]], [[MUL_OVERFLOW]]154; LV-NEXT: [[TMP6:%.*]] = icmp ugt i64 [[TMP0]], 4294967295155; LV-NEXT: [[TMP7:%.*]] = or i1 [[TMP5]], [[TMP6]]156; LV-NEXT: [[TMP8:%.*]] = trunc i64 [[N]] to i31157; LV-NEXT: [[TMP9:%.*]] = zext i31 [[TMP8]] to i64158; LV-NEXT: [[TMP10:%.*]] = shl nuw nsw i64 [[TMP9]], 2159; LV-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[A:%.*]], i64 [[TMP10]]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]], 0162; LV-NEXT: [[MUL_OVERFLOW4:%.*]] = extractvalue { i64, i1 } [[MUL2]], 1163; LV-NEXT: [[TMP11:%.*]] = sub i64 0, [[MUL_RESULT3]]164; LV-NEXT: [[TMP12:%.*]] = getelementptr i8, ptr [[SCEVGEP]], i64 [[TMP11]]165; LV-NEXT: [[TMP13:%.*]] = icmp ugt ptr [[TMP12]], [[SCEVGEP]]166; LV-NEXT: [[TMP14:%.*]] = or i1 [[TMP13]], [[MUL_OVERFLOW4]]167; LV-NEXT: [[TMP15:%.*]] = or i1 [[TMP7]], [[TMP14]]168; LV-NEXT: br i1 [[TMP15]], 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]], 2175; LV-NEXT: [[MUL_EXT_LVER_ORIG:%.*]] = zext i32 [[MUL_LVER_ORIG]] to i64176; LV-NEXT: [[ARRAYIDXA_LVER_ORIG:%.*]] = getelementptr i16, ptr [[A]], i64 [[MUL_EXT_LVER_ORIG]]177; LV-NEXT: [[LOADA_LVER_ORIG:%.*]] = load i16, ptr [[ARRAYIDXA_LVER_ORIG]], align 2178; LV-NEXT: [[ARRAYIDXB_LVER_ORIG:%.*]] = getelementptr i16, ptr [[B:%.*]], i64 [[IND_LVER_ORIG]]179; LV-NEXT: [[LOADB_LVER_ORIG:%.*]] = load i16, ptr [[ARRAYIDXB_LVER_ORIG]], align 2180; LV-NEXT: [[ADD_LVER_ORIG:%.*]] = mul i16 [[LOADA_LVER_ORIG]], [[LOADB_LVER_ORIG]]181; LV-NEXT: store i16 [[ADD_LVER_ORIG]], ptr [[ARRAYIDXA_LVER_ORIG]], align 2182; LV-NEXT: [[INC_LVER_ORIG]] = add nuw nsw i64 [[IND_LVER_ORIG]], 1183; LV-NEXT: [[DEC_LVER_ORIG]] = sub i32 [[IND1_LVER_ORIG]], 1184; 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]], 2192; LV-NEXT: [[MUL_EXT:%.*]] = zext i32 [[MUL]] to i64193; LV-NEXT: [[ARRAYIDXA:%.*]] = getelementptr i16, ptr [[A]], i64 [[MUL_EXT]]194; LV-NEXT: [[LOADA:%.*]] = load i16, ptr [[ARRAYIDXA]], align 2195; LV-NEXT: [[ARRAYIDXB:%.*]] = getelementptr i16, ptr [[B]], i64 [[IND]]196; LV-NEXT: [[LOADB:%.*]] = load i16, ptr [[ARRAYIDXB]], align 2197; LV-NEXT: [[ADD:%.*]] = mul i16 [[LOADA]], [[LOADB]]198; LV-NEXT: store i16 [[ADD]], ptr [[ARRAYIDXA]], align 2199; LV-NEXT: [[INC]] = add nuw nsw i64 [[IND]], 1200; LV-NEXT: [[DEC]] = sub i32 [[IND1]], 1201; LV-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[INC]], [[N]]202; LV-NEXT: br i1 [[EXITCOND]], label [[FOR_END_LOOPEXIT5:%.*]], label [[FOR_BODY]]203; LV: for.end.loopexit:204; LV-NEXT: br label [[FOR_END:%.*]]205; LV: for.end.loopexit5:206; LV-NEXT: br label [[FOR_END]]207; LV: for.end:208; LV-NEXT: ret void209;210 ptr noalias %b, i64 %N) {211entry:212 %TruncN = trunc i64 %N to i32213 br label %for.body214 215for.body: ; preds = %for.body, %entry216 %ind = phi i64 [ 0, %entry ], [ %inc, %for.body ]217 %ind1 = phi i32 [ %TruncN, %entry ], [ %dec, %for.body ]218 219 %mul = mul i32 %ind1, 2220 %mul_ext = zext i32 %mul to i64221 222 %arrayidxA = getelementptr i16, ptr %a, i64 %mul_ext223 %loadA = load i16, ptr %arrayidxA, align 2224 225 %arrayidxB = getelementptr i16, ptr %b, i64 %ind226 %loadB = load i16, ptr %arrayidxB, align 2227 228 %add = mul i16 %loadA, %loadB229 230 store i16 %add, ptr %arrayidxA, align 2231 232 %inc = add nuw nsw i64 %ind, 1233 %dec = sub i32 %ind1, 1234 235 %exitcond = icmp eq i64 %inc, %N236 br i1 %exitcond, label %for.end, label %for.body237 238for.end: ; preds = %for.body239 ret void240}241 242; We replicate the tests above, but this time sign extend 2 * index instead243; of zero extending it.244 245; The expression for %mul_ext as analyzed by SCEV is246; 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(ptr noalias %a,251; LV-LABEL: @f3(252; LV-NEXT: for.body.lver.check:253; LV-NEXT: [[TMP0:%.*]] = add i64 [[N:%.*]], -1254; LV-NEXT: [[TMP1:%.*]] = trunc i64 [[TMP0]] to i32255; LV-NEXT: [[MUL1:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 2, i32 [[TMP1]])256; LV-NEXT: [[MUL_RESULT:%.*]] = extractvalue { i32, i1 } [[MUL1]], 0257; LV-NEXT: [[MUL_OVERFLOW:%.*]] = extractvalue { i32, i1 } [[MUL1]], 1258; LV-NEXT: [[TMP2:%.*]] = icmp slt i32 [[MUL_RESULT]], 0259; LV-NEXT: [[TMP3:%.*]] = or i1 [[TMP2]], [[MUL_OVERFLOW]]260; LV-NEXT: [[TMP4:%.*]] = icmp ugt i64 [[TMP0]], 4294967295261; LV-NEXT: [[TMP5:%.*]] = or i1 [[TMP3]], [[TMP4]]262; LV-NEXT: [[MUL2:%.*]] = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 4, i64 [[TMP0]])263; LV-NEXT: [[MUL_RESULT3:%.*]] = extractvalue { i64, i1 } [[MUL2]], 0264; LV-NEXT: [[MUL_OVERFLOW4:%.*]] = extractvalue { i64, i1 } [[MUL2]], 1265; LV-NEXT: [[TMP7:%.*]] = getelementptr i8, ptr [[A:%.*]], i64 [[MUL_RESULT3]]266; LV-NEXT: [[TMP8:%.*]] = icmp ult ptr [[TMP7]], [[A]]267; LV-NEXT: [[TMP9:%.*]] = or i1 [[TMP8]], [[MUL_OVERFLOW4]]268; LV-NEXT: [[TMP10:%.*]] = or i1 [[TMP5]], [[TMP9]]269; LV-NEXT: br i1 [[TMP10]], label [[FOR_BODY_PH_LVER_ORIG:%.*]], label [[FOR_BODY_PH:%.*]]270; LV: for.body.ph.lver.orig:271; LV-NEXT: br label [[FOR_BODY_LVER_ORIG:%.*]]272; LV: for.body.lver.orig:273; LV-NEXT: [[IND_LVER_ORIG:%.*]] = phi i64 [ 0, [[FOR_BODY_PH_LVER_ORIG]] ], [ [[INC_LVER_ORIG:%.*]], [[FOR_BODY_LVER_ORIG]] ]274; LV-NEXT: [[IND1_LVER_ORIG:%.*]] = phi i32 [ 0, [[FOR_BODY_PH_LVER_ORIG]] ], [ [[INC1_LVER_ORIG:%.*]], [[FOR_BODY_LVER_ORIG]] ]275; LV-NEXT: [[MUL_LVER_ORIG:%.*]] = mul i32 [[IND1_LVER_ORIG]], 2276; LV-NEXT: [[MUL_EXT_LVER_ORIG:%.*]] = sext i32 [[MUL_LVER_ORIG]] to i64277; LV-NEXT: [[ARRAYIDXA_LVER_ORIG:%.*]] = getelementptr i16, ptr [[A]], i64 [[MUL_EXT_LVER_ORIG]]278; LV-NEXT: [[LOADA_LVER_ORIG:%.*]] = load i16, ptr [[ARRAYIDXA_LVER_ORIG]], align 2279; LV-NEXT: [[ARRAYIDXB_LVER_ORIG:%.*]] = getelementptr i16, ptr [[B:%.*]], i64 [[IND_LVER_ORIG]]280; LV-NEXT: [[LOADB_LVER_ORIG:%.*]] = load i16, ptr [[ARRAYIDXB_LVER_ORIG]], align 2281; LV-NEXT: [[ADD_LVER_ORIG:%.*]] = mul i16 [[LOADA_LVER_ORIG]], [[LOADB_LVER_ORIG]]282; LV-NEXT: store i16 [[ADD_LVER_ORIG]], ptr [[ARRAYIDXA_LVER_ORIG]], align 2283; LV-NEXT: [[INC_LVER_ORIG]] = add nuw nsw i64 [[IND_LVER_ORIG]], 1284; LV-NEXT: [[INC1_LVER_ORIG]] = add i32 [[IND1_LVER_ORIG]], 1285; LV-NEXT: [[EXITCOND_LVER_ORIG:%.*]] = icmp eq i64 [[INC_LVER_ORIG]], [[N]]286; LV-NEXT: br i1 [[EXITCOND_LVER_ORIG]], label [[FOR_END_LOOPEXIT:%.*]], label [[FOR_BODY_LVER_ORIG]]287; LV: for.body.ph:288; LV-NEXT: br label [[FOR_BODY:%.*]]289; LV: for.body:290; LV-NEXT: [[IND:%.*]] = phi i64 [ 0, [[FOR_BODY_PH]] ], [ [[INC:%.*]], [[FOR_BODY]] ]291; LV-NEXT: [[IND1:%.*]] = phi i32 [ 0, [[FOR_BODY_PH]] ], [ [[INC1:%.*]], [[FOR_BODY]] ]292; LV-NEXT: [[MUL:%.*]] = mul i32 [[IND1]], 2293; LV-NEXT: [[MUL_EXT:%.*]] = sext i32 [[MUL]] to i64294; LV-NEXT: [[ARRAYIDXA:%.*]] = getelementptr i16, ptr [[A]], i64 [[MUL_EXT]]295; LV-NEXT: [[LOADA:%.*]] = load i16, ptr [[ARRAYIDXA]], align 2296; LV-NEXT: [[ARRAYIDXB:%.*]] = getelementptr i16, ptr [[B]], i64 [[IND]]297; LV-NEXT: [[LOADB:%.*]] = load i16, ptr [[ARRAYIDXB]], align 2298; LV-NEXT: [[ADD:%.*]] = mul i16 [[LOADA]], [[LOADB]]299; LV-NEXT: store i16 [[ADD]], ptr [[ARRAYIDXA]], align 2300; LV-NEXT: [[INC]] = add nuw nsw i64 [[IND]], 1301; LV-NEXT: [[INC1]] = add i32 [[IND1]], 1302; LV-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[INC]], [[N]]303; LV-NEXT: br i1 [[EXITCOND]], label [[FOR_END_LOOPEXIT5:%.*]], label [[FOR_BODY]]304; LV: for.end.loopexit:305; LV-NEXT: br label [[FOR_END:%.*]]306; LV: for.end.loopexit5:307; LV-NEXT: br label [[FOR_END]]308; LV: for.end:309; LV-NEXT: ret void310;311 ptr noalias %b, i64 %N) {312entry:313 br label %for.body314 315for.body: ; preds = %for.body, %entry316 %ind = phi i64 [ 0, %entry ], [ %inc, %for.body ]317 %ind1 = phi i32 [ 0, %entry ], [ %inc1, %for.body ]318 319 %mul = mul i32 %ind1, 2320 %mul_ext = sext i32 %mul to i64321 322 %arrayidxA = getelementptr i16, ptr %a, i64 %mul_ext323 %loadA = load i16, ptr %arrayidxA, align 2324 325 %arrayidxB = getelementptr i16, ptr %b, i64 %ind326 %loadB = load i16, ptr %arrayidxB, align 2327 328 %add = mul i16 %loadA, %loadB329 330 store i16 %add, ptr %arrayidxA, align 2331 332 %inc = add nuw nsw i64 %ind, 1333 %inc1 = add i32 %ind1, 1334 335 %exitcond = icmp eq i64 %inc, %N336 br i1 %exitcond, label %for.end, label %for.body337 338for.end: ; preds = %for.body339 ret void340}341 342define void @f4(ptr noalias %a,343; LV-LABEL: @f4(344; LV-NEXT: for.body.lver.check:345; LV-NEXT: [[TRUNCN:%.*]] = trunc i64 [[N:%.*]] to i32346; LV-NEXT: [[TMP0:%.*]] = add i64 [[N]], -1347; LV-NEXT: [[TMP1:%.*]] = shl i32 [[TRUNCN]], 1348; LV-NEXT: [[TMP2:%.*]] = trunc i64 [[TMP0]] to i32349; LV-NEXT: [[MUL1:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 2, i32 [[TMP2]])350; LV-NEXT: [[MUL_RESULT:%.*]] = extractvalue { i32, i1 } [[MUL1]], 0351; LV-NEXT: [[MUL_OVERFLOW:%.*]] = extractvalue { i32, i1 } [[MUL1]], 1352; LV-NEXT: [[TMP3:%.*]] = sub i32 [[TMP1]], [[MUL_RESULT]]353; LV-NEXT: [[TMP4:%.*]] = icmp sgt i32 [[TMP3]], [[TMP1]]354; LV-NEXT: [[TMP5:%.*]] = or i1 [[TMP4]], [[MUL_OVERFLOW]]355; LV-NEXT: [[TMP6:%.*]] = icmp ugt i64 [[TMP0]], 4294967295356; LV-NEXT: [[TMP7:%.*]] = or i1 [[TMP5]], [[TMP6]]357; LV-NEXT: [[TMP8:%.*]] = sext i32 [[TMP1]] to i64358; LV-NEXT: [[TMP9:%.*]] = shl nsw i64 [[TMP8]], 1359; LV-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[A:%.*]], i64 [[TMP9]]360; LV-NEXT: [[MUL2:%.*]] = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 4, i64 [[TMP0]])361; LV-NEXT: [[MUL_RESULT3:%.*]] = extractvalue { i64, i1 } [[MUL2]], 0362; LV-NEXT: [[MUL_OVERFLOW4:%.*]] = extractvalue { i64, i1 } [[MUL2]], 1363; LV-NEXT: [[TMP10:%.*]] = sub i64 0, [[MUL_RESULT3]]364; LV-NEXT: [[TMP11:%.*]] = getelementptr i8, ptr [[SCEVGEP]], i64 [[TMP10]]365; LV-NEXT: [[TMP12:%.*]] = icmp ugt ptr [[TMP11]], [[SCEVGEP]]366; LV-NEXT: [[TMP13:%.*]] = or i1 [[TMP12]], [[MUL_OVERFLOW4]]367; LV-NEXT: [[TMP14:%.*]] = or i1 [[TMP7]], [[TMP13]]368; LV-NEXT: br i1 [[TMP14]], label [[FOR_BODY_PH_LVER_ORIG:%.*]], label [[FOR_BODY_PH:%.*]]369; LV: for.body.ph.lver.orig:370; LV-NEXT: br label [[FOR_BODY_LVER_ORIG:%.*]]371; LV: for.body.lver.orig:372; LV-NEXT: [[IND_LVER_ORIG:%.*]] = phi i64 [ 0, [[FOR_BODY_PH_LVER_ORIG]] ], [ [[INC_LVER_ORIG:%.*]], [[FOR_BODY_LVER_ORIG]] ]373; LV-NEXT: [[IND1_LVER_ORIG:%.*]] = phi i32 [ [[TRUNCN]], [[FOR_BODY_PH_LVER_ORIG]] ], [ [[DEC_LVER_ORIG:%.*]], [[FOR_BODY_LVER_ORIG]] ]374; LV-NEXT: [[MUL_LVER_ORIG:%.*]] = mul i32 [[IND1_LVER_ORIG]], 2375; LV-NEXT: [[MUL_EXT_LVER_ORIG:%.*]] = sext i32 [[MUL_LVER_ORIG]] to i64376; LV-NEXT: [[ARRAYIDXA_LVER_ORIG:%.*]] = getelementptr i16, ptr [[A]], i64 [[MUL_EXT_LVER_ORIG]]377; LV-NEXT: [[LOADA_LVER_ORIG:%.*]] = load i16, ptr [[ARRAYIDXA_LVER_ORIG]], align 2378; LV-NEXT: [[ARRAYIDXB_LVER_ORIG:%.*]] = getelementptr i16, ptr [[B:%.*]], i64 [[IND_LVER_ORIG]]379; LV-NEXT: [[LOADB_LVER_ORIG:%.*]] = load i16, ptr [[ARRAYIDXB_LVER_ORIG]], align 2380; LV-NEXT: [[ADD_LVER_ORIG:%.*]] = mul i16 [[LOADA_LVER_ORIG]], [[LOADB_LVER_ORIG]]381; LV-NEXT: store i16 [[ADD_LVER_ORIG]], ptr [[ARRAYIDXA_LVER_ORIG]], align 2382; LV-NEXT: [[INC_LVER_ORIG]] = add nuw nsw i64 [[IND_LVER_ORIG]], 1383; LV-NEXT: [[DEC_LVER_ORIG]] = sub i32 [[IND1_LVER_ORIG]], 1384; LV-NEXT: [[EXITCOND_LVER_ORIG:%.*]] = icmp eq i64 [[INC_LVER_ORIG]], [[N]]385; LV-NEXT: br i1 [[EXITCOND_LVER_ORIG]], label [[FOR_END_LOOPEXIT:%.*]], label [[FOR_BODY_LVER_ORIG]]386; LV: for.body.ph:387; LV-NEXT: br label [[FOR_BODY:%.*]]388; LV: for.body:389; LV-NEXT: [[IND:%.*]] = phi i64 [ 0, [[FOR_BODY_PH]] ], [ [[INC:%.*]], [[FOR_BODY]] ]390; LV-NEXT: [[IND1:%.*]] = phi i32 [ [[TRUNCN]], [[FOR_BODY_PH]] ], [ [[DEC:%.*]], [[FOR_BODY]] ]391; LV-NEXT: [[MUL:%.*]] = mul i32 [[IND1]], 2392; LV-NEXT: [[MUL_EXT:%.*]] = sext i32 [[MUL]] to i64393; LV-NEXT: [[ARRAYIDXA:%.*]] = getelementptr i16, ptr [[A]], i64 [[MUL_EXT]]394; LV-NEXT: [[LOADA:%.*]] = load i16, ptr [[ARRAYIDXA]], align 2395; LV-NEXT: [[ARRAYIDXB:%.*]] = getelementptr i16, ptr [[B]], i64 [[IND]]396; LV-NEXT: [[LOADB:%.*]] = load i16, ptr [[ARRAYIDXB]], align 2397; LV-NEXT: [[ADD:%.*]] = mul i16 [[LOADA]], [[LOADB]]398; LV-NEXT: store i16 [[ADD]], ptr [[ARRAYIDXA]], align 2399; LV-NEXT: [[INC]] = add nuw nsw i64 [[IND]], 1400; LV-NEXT: [[DEC]] = sub i32 [[IND1]], 1401; LV-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[INC]], [[N]]402; LV-NEXT: br i1 [[EXITCOND]], label [[FOR_END_LOOPEXIT5:%.*]], label [[FOR_BODY]]403; LV: for.end.loopexit:404; LV-NEXT: br label [[FOR_END:%.*]]405; LV: for.end.loopexit5:406; LV-NEXT: br label [[FOR_END]]407; LV: for.end:408; LV-NEXT: ret void409;410 ptr noalias %b, i64 %N) {411entry:412 %TruncN = trunc i64 %N to i32413 br label %for.body414 415for.body: ; preds = %for.body, %entry416 %ind = phi i64 [ 0, %entry ], [ %inc, %for.body ]417 %ind1 = phi i32 [ %TruncN, %entry ], [ %dec, %for.body ]418 419 %mul = mul i32 %ind1, 2420 %mul_ext = sext i32 %mul to i64421 422 %arrayidxA = getelementptr i16, ptr %a, i64 %mul_ext423 %loadA = load i16, ptr %arrayidxA, align 2424 425 %arrayidxB = getelementptr i16, ptr %b, i64 %ind426 %loadB = load i16, ptr %arrayidxB, align 2427 428 %add = mul i16 %loadA, %loadB429 430 store i16 %add, ptr %arrayidxA, align 2431 432 %inc = add nuw nsw i64 %ind, 1433 %dec = sub i32 %ind1, 1434 435 %exitcond = icmp eq i64 %inc, %N436 br i1 %exitcond, label %for.end, label %for.body437 438for.end: ; preds = %for.body439 ret void440}441 442; The following function is similar to the one above, but has the GEP443; to pointer %A inbounds. The index %mul doesn't have the nsw flag.444; This means that the SCEV expression for %mul can wrap and we need445; a SCEV predicate to continue analysis.446;447; We can still analyze this by adding the required no wrap SCEV predicates.448 449define void @f5(ptr noalias %a,450; LV-LABEL: @f5(451; LV-NEXT: for.body.lver.check:452; LV-NEXT: [[TRUNCN:%.*]] = trunc i64 [[N:%.*]] to i32453; LV-NEXT: [[TMP0:%.*]] = add i64 [[N]], -1454; LV-NEXT: [[TMP1:%.*]] = shl i32 [[TRUNCN]], 1455; LV-NEXT: [[TMP2:%.*]] = trunc i64 [[TMP0]] to i32456; LV-NEXT: [[MUL1:%.*]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 2, i32 [[TMP2]])457; LV-NEXT: [[MUL_RESULT:%.*]] = extractvalue { i32, i1 } [[MUL1]], 0458; LV-NEXT: [[MUL_OVERFLOW:%.*]] = extractvalue { i32, i1 } [[MUL1]], 1459; LV-NEXT: [[TMP3:%.*]] = sub i32 [[TMP1]], [[MUL_RESULT]]460; LV-NEXT: [[TMP4:%.*]] = icmp sgt i32 [[TMP3]], [[TMP1]]461; LV-NEXT: [[TMP5:%.*]] = or i1 [[TMP4]], [[MUL_OVERFLOW]]462; LV-NEXT: [[TMP6:%.*]] = icmp ugt i64 [[TMP0]], 4294967295463; LV-NEXT: [[TMP14:%.*]] = or i1 [[TMP5]], [[TMP6]]464; LV-NEXT: br i1 [[TMP14]], label [[FOR_BODY_PH_LVER_ORIG:%.*]], label [[FOR_BODY_PH:%.*]]465; LV: for.body.ph.lver.orig:466; LV-NEXT: br label [[FOR_BODY_LVER_ORIG:%.*]]467; LV: for.body.lver.orig:468; LV-NEXT: [[IND_LVER_ORIG:%.*]] = phi i64 [ 0, [[FOR_BODY_PH_LVER_ORIG]] ], [ [[INC_LVER_ORIG:%.*]], [[FOR_BODY_LVER_ORIG]] ]469; LV-NEXT: [[IND1_LVER_ORIG:%.*]] = phi i32 [ [[TRUNCN]], [[FOR_BODY_PH_LVER_ORIG]] ], [ [[DEC_LVER_ORIG:%.*]], [[FOR_BODY_LVER_ORIG]] ]470; LV-NEXT: [[MUL_LVER_ORIG:%.*]] = mul i32 [[IND1_LVER_ORIG]], 2471; LV-NEXT: [[ARRAYIDXA_LVER_ORIG:%.*]] = getelementptr inbounds i16, ptr [[A:%.*]], i32 [[MUL_LVER_ORIG]]472; LV-NEXT: [[LOADA_LVER_ORIG:%.*]] = load i16, ptr [[ARRAYIDXA_LVER_ORIG]], align 2473; LV-NEXT: [[ARRAYIDXB_LVER_ORIG:%.*]] = getelementptr inbounds i16, ptr [[B:%.*]], i64 [[IND_LVER_ORIG]]474; LV-NEXT: [[LOADB_LVER_ORIG:%.*]] = load i16, ptr [[ARRAYIDXB_LVER_ORIG]], align 2475; LV-NEXT: [[ADD_LVER_ORIG:%.*]] = mul i16 [[LOADA_LVER_ORIG]], [[LOADB_LVER_ORIG]]476; LV-NEXT: store i16 [[ADD_LVER_ORIG]], ptr [[ARRAYIDXA_LVER_ORIG]], align 2477; LV-NEXT: [[INC_LVER_ORIG]] = add nuw nsw i64 [[IND_LVER_ORIG]], 1478; LV-NEXT: [[DEC_LVER_ORIG]] = sub i32 [[IND1_LVER_ORIG]], 1479; LV-NEXT: [[EXITCOND_LVER_ORIG:%.*]] = icmp eq i64 [[INC_LVER_ORIG]], [[N]]480; LV-NEXT: br i1 [[EXITCOND_LVER_ORIG]], label [[FOR_END_LOOPEXIT:%.*]], label [[FOR_BODY_LVER_ORIG]]481; LV: for.body.ph:482; LV-NEXT: br label [[FOR_BODY:%.*]]483; LV: for.body:484; LV-NEXT: [[IND:%.*]] = phi i64 [ 0, [[FOR_BODY_PH]] ], [ [[INC:%.*]], [[FOR_BODY]] ]485; LV-NEXT: [[IND1:%.*]] = phi i32 [ [[TRUNCN]], [[FOR_BODY_PH]] ], [ [[DEC:%.*]], [[FOR_BODY]] ]486; LV-NEXT: [[MUL:%.*]] = mul i32 [[IND1]], 2487; LV-NEXT: [[ARRAYIDXA:%.*]] = getelementptr inbounds i16, ptr [[A]], i32 [[MUL]]488; LV-NEXT: [[LOADA:%.*]] = load i16, ptr [[ARRAYIDXA]], align 2489; LV-NEXT: [[ARRAYIDXB:%.*]] = getelementptr inbounds i16, ptr [[B]], i64 [[IND]]490; LV-NEXT: [[LOADB:%.*]] = load i16, ptr [[ARRAYIDXB]], align 2491; LV-NEXT: [[ADD:%.*]] = mul i16 [[LOADA]], [[LOADB]]492; LV-NEXT: store i16 [[ADD]], ptr [[ARRAYIDXA]], align 2493; LV-NEXT: [[INC]] = add nuw nsw i64 [[IND]], 1494; LV-NEXT: [[DEC]] = sub i32 [[IND1]], 1495; LV-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[INC]], [[N]]496; LV-NEXT: br i1 [[EXITCOND]], label [[FOR_END_LOOPEXIT5:%.*]], label [[FOR_BODY]]497; LV: for.end.loopexit:498; LV-NEXT: br label [[FOR_END:%.*]]499; LV: for.end.loopexit2:500; LV-NEXT: br label [[FOR_END]]501; LV: for.end:502; LV-NEXT: ret void503;504 ptr noalias %b, i64 %N) {505entry:506 %TruncN = trunc i64 %N to i32507 br label %for.body508 509for.body: ; preds = %for.body, %entry510 %ind = phi i64 [ 0, %entry ], [ %inc, %for.body ]511 %ind1 = phi i32 [ %TruncN, %entry ], [ %dec, %for.body ]512 513 %mul = mul i32 %ind1, 2514 515 %arrayidxA = getelementptr inbounds i16, ptr %a, i32 %mul516 %loadA = load i16, ptr %arrayidxA, align 2517 518 %arrayidxB = getelementptr inbounds i16, ptr %b, i64 %ind519 %loadB = load i16, ptr %arrayidxB, align 2520 521 %add = mul i16 %loadA, %loadB522 523 store i16 %add, ptr %arrayidxA, align 2524 525 %inc = add nuw nsw i64 %ind, 1526 %dec = sub i32 %ind1, 1527 528 %exitcond = icmp eq i64 %inc, %N529 br i1 %exitcond, label %for.end, label %for.body530 531for.end: ; preds = %for.body532 ret void533}534