1573 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 22; REQUIRES: asserts3; RUN: opt < %s -p 'loop-vectorize' -force-vector-interleave=1 -S \4; RUN: -force-vector-width=4 -debug-only=loop-accesses,loop-vectorize,loop-utils 2> %t | FileCheck %s5; RUN: cat %t | FileCheck %s --check-prefix=DEBUG6 7target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"8 9; Equivalent example in C:10; void diff_checks(int32_t *dst, int32_t *src, int m, int n) {11; for (int i = 0; i < m; i++) {12; for (int j = 0; j < n; j++) {13; dst[(i * (n + 1)) + j] = src[(i * n) + j];14; }15; }16; }17; NOTE: The strides of the starting address values in the inner loop differ, i.e.18; '(i * (n + 1))' vs '(i * n)'.19 20; DEBUG-LABEL: 'diff_checks'21; DEBUG: LAA: Found an analyzable loop: inner.loop22; DEBUG: LAA: Not creating diff runtime check, since these cannot be hoisted out of the outer loop23; DEBUG: LAA: Adding RT check for range:24; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting25; DEBUG-NEXT: LAA: ... but need to check stride is positive: (4 * (sext i32 (1 + %n)<nuw> to i64))<nsw>26; DEBUG-NEXT: Start: %dst End: ((4 * (zext i32 %n to i64))<nuw><nsw> + (4 * (sext i32 (1 + %n)<nuw> to i64) * (-1 + (zext i32 %m to i64))<nsw>) + %dst)27; DEBUG-NEXT: LAA: Adding RT check for range:28; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting29; DEBUG-NEXT: Start: %src End: ((4 * (zext i32 %m to i64) * (zext i32 %n to i64)) + %src)30 31define void @diff_checks(ptr nocapture noundef writeonly %dst, ptr nocapture noundef readonly %src, i32 noundef %m, i32 noundef %n) {32; CHECK-LABEL: define void @diff_checks33; CHECK-SAME: (ptr noundef writeonly captures(none) [[DST:%.*]], ptr noundef readonly captures(none) [[SRC:%.*]], i32 noundef [[M:%.*]], i32 noundef [[N:%.*]]) {34; CHECK-NEXT: entry:35; CHECK-NEXT: [[ADD5:%.*]] = add nuw i32 [[N]], 136; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[N]] to i6437; CHECK-NEXT: [[TMP1:%.*]] = sext i32 [[ADD5]] to i6438; CHECK-NEXT: [[WIDE_M:%.*]] = zext i32 [[M]] to i6439; CHECK-NEXT: [[WIDE_N:%.*]] = zext i32 [[N]] to i6440; CHECK-NEXT: [[TMP2:%.*]] = add nsw i64 [[WIDE_M]], -141; CHECK-NEXT: [[TMP3:%.*]] = mul i64 [[TMP2]], [[TMP1]]42; CHECK-NEXT: [[TMP4:%.*]] = shl i64 [[TMP3]], 243; CHECK-NEXT: [[TMP5:%.*]] = shl nuw nsw i64 [[WIDE_N]], 244; CHECK-NEXT: [[TMP6:%.*]] = add i64 [[TMP4]], [[TMP5]]45; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP6]]46; CHECK-NEXT: [[TMP7:%.*]] = shl nsw i64 [[TMP1]], 247; CHECK-NEXT: [[TMP8:%.*]] = mul i64 [[WIDE_N]], [[WIDE_M]]48; CHECK-NEXT: [[TMP9:%.*]] = shl i64 [[TMP8]], 249; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP9]]50; CHECK-NEXT: br label [[OUTER_LOOP:%.*]]51; CHECK: outer.loop:52; CHECK-NEXT: [[IV_OUTER:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_OUTER_NEXT:%.*]], [[INNER_EXIT:%.*]] ]53; CHECK-NEXT: [[TMP10:%.*]] = mul nsw i64 [[IV_OUTER]], [[TMP0]]54; CHECK-NEXT: [[TMP11:%.*]] = mul nsw i64 [[IV_OUTER]], [[TMP1]]55; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_N]], 456; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]]57; CHECK: vector.memcheck:58; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP1]]59; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP]]60; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]61; CHECK-NEXT: [[STRIDE_CHECK:%.*]] = icmp slt i64 [[TMP7]], 062; CHECK-NEXT: [[TMP12:%.*]] = or i1 [[FOUND_CONFLICT]], [[STRIDE_CHECK]]63; CHECK-NEXT: br i1 [[TMP12]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]64; CHECK: vector.ph:65; CHECK-NEXT: [[N_MOD_VF:%.*]] = urem i64 [[WIDE_N]], 466; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[WIDE_N]], [[N_MOD_VF]]67; CHECK-NEXT: br label [[VECTOR_BODY:%.*]]68; CHECK: vector.body:69; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]70; CHECK-NEXT: [[TMP13:%.*]] = add nuw nsw i64 [[INDEX]], [[TMP10]]71; CHECK-NEXT: [[TMP14:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP13]]72; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP14]], align 4, !alias.scope [[META0:![0-9]+]]73; CHECK-NEXT: [[TMP15:%.*]] = add nsw i64 [[INDEX]], [[TMP11]]74; CHECK-NEXT: [[TMP16:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP15]]75; CHECK-NEXT: store <4 x i32> [[WIDE_LOAD]], ptr [[TMP16]], align 4, !alias.scope [[META3:![0-9]+]], !noalias [[META0]]76; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 477; CHECK-NEXT: [[TMP17:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]78; CHECK-NEXT: br i1 [[TMP17]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP5:![0-9]+]]79; CHECK: middle.block:80; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_N]], [[N_VEC]]81; CHECK-NEXT: br i1 [[CMP_N]], label [[INNER_EXIT]], label [[SCALAR_PH]]82; CHECK: scalar.ph:83; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[OUTER_LOOP]] ], [ 0, [[VECTOR_MEMCHECK]] ]84; CHECK-NEXT: br label [[INNER_LOOP:%.*]]85; CHECK: inner.loop:86; CHECK-NEXT: [[IV_INNER:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_INNER_NEXT:%.*]], [[INNER_LOOP]] ]87; CHECK-NEXT: [[TMP18:%.*]] = add nuw nsw i64 [[IV_INNER]], [[TMP10]]88; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP18]]89; CHECK-NEXT: [[TMP19:%.*]] = load i32, ptr [[ARRAYIDX_US]], align 490; CHECK-NEXT: [[TMP20:%.*]] = add nsw i64 [[IV_INNER]], [[TMP11]]91; CHECK-NEXT: [[ARRAYIDX9_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP20]]92; CHECK-NEXT: store i32 [[TMP19]], ptr [[ARRAYIDX9_US]], align 493; CHECK-NEXT: [[IV_INNER_NEXT]] = add nuw nsw i64 [[IV_INNER]], 194; CHECK-NEXT: [[INNER_EXIT_COND:%.*]] = icmp eq i64 [[IV_INNER_NEXT]], [[WIDE_N]]95; CHECK-NEXT: br i1 [[INNER_EXIT_COND]], label [[INNER_EXIT]], label [[INNER_LOOP]], !llvm.loop [[LOOP8:![0-9]+]]96; CHECK: inner.exit:97; CHECK-NEXT: [[IV_OUTER_NEXT]] = add nuw nsw i64 [[IV_OUTER]], 198; CHECK-NEXT: [[OUTER_EXIT_COND:%.*]] = icmp eq i64 [[IV_OUTER_NEXT]], [[WIDE_M]]99; CHECK-NEXT: br i1 [[OUTER_EXIT_COND]], label [[OUTER_EXIT:%.*]], label [[OUTER_LOOP]]100; CHECK: outer.exit:101; CHECK-NEXT: ret void102;103entry:104 %add5 = add nuw i32 %n, 1105 %0 = zext i32 %n to i64106 %1 = sext i32 %add5 to i64107 %wide.m = zext i32 %m to i64108 %wide.n = zext i32 %n to i64109 br label %outer.loop110 111outer.loop:112 %iv.outer = phi i64 [ 0, %entry ], [ %iv.outer.next, %inner.exit ]113 %2 = mul nsw i64 %iv.outer, %0114 %3 = mul nsw i64 %iv.outer, %1115 br label %inner.loop116 117inner.loop:118 %iv.inner = phi i64 [ 0, %outer.loop ], [ %iv.inner.next, %inner.loop ]119 %4 = add nuw nsw i64 %iv.inner, %2120 %arrayidx.us = getelementptr inbounds i32, ptr %src, i64 %4121 %5 = load i32, ptr %arrayidx.us, align 4122 %6 = add nsw i64 %iv.inner, %3123 %arrayidx9.us = getelementptr inbounds i32, ptr %dst, i64 %6124 store i32 %5, ptr %arrayidx9.us, align 4125 %iv.inner.next = add nuw nsw i64 %iv.inner, 1126 %inner.exit.cond = icmp eq i64 %iv.inner.next, %wide.n127 br i1 %inner.exit.cond, label %inner.exit, label %inner.loop128 129inner.exit:130 %iv.outer.next = add nuw nsw i64 %iv.outer, 1131 %outer.exit.cond = icmp eq i64 %iv.outer.next, %wide.m132 br i1 %outer.exit.cond, label %outer.exit, label %outer.loop133 134outer.exit:135 ret void136}137 138 139; Equivalent example in C:140; void full_checks(int32_t *dst, int32_t *src, int m, int n) {141; for (int i = 0; i < m; i++) {142; for (int j = 0; j < n; j++) {143; dst[(i * n) + j] += src[(i * n) + j];144; }145; }146; }147; We decide to do full runtime checks here (as opposed to diff checks) due to148; the additional load of 'dst[(i * n) + j]' in the loop.149 150; DEBUG-LABEL: 'full_checks'151; DEBUG: LAA: Found an analyzable loop: inner.loop152; DEBUG-NOT: LAA: Creating diff runtime check for:153; DEBUG: LAA: Adding RT check for range:154; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting155; DEBUG-NEXT: Start: %dst End: ((4 * (zext i32 %m to i64) * (zext i32 %n to i64)) + %dst)156; DEBUG-NEXT: LAA: Adding RT check for range:157; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting158; DEBUG-NEXT: Start: %src End: ((4 * (zext i32 %m to i64) * (zext i32 %n to i64)) + %src)159 160define void @full_checks(ptr nocapture noundef %dst, ptr nocapture noundef readonly %src, i32 noundef %m, i32 noundef %n) {161; CHECK-LABEL: define void @full_checks162; CHECK-SAME: (ptr noundef captures(none) [[DST:%.*]], ptr noundef readonly captures(none) [[SRC:%.*]], i32 noundef [[M:%.*]], i32 noundef [[N:%.*]]) {163; CHECK-NEXT: entry:164; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[N]] to i64165; CHECK-NEXT: [[WIDE_M:%.*]] = zext i32 [[M]] to i64166; CHECK-NEXT: [[WIDE_N:%.*]] = zext i32 [[N]] to i64167; CHECK-NEXT: [[TMP1:%.*]] = mul i64 [[WIDE_N]], [[WIDE_M]]168; CHECK-NEXT: [[TMP2:%.*]] = shl i64 [[TMP1]], 2169; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP2]]170; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP2]]171; CHECK-NEXT: br label [[OUTER_LOOP:%.*]]172; CHECK: outer.loop:173; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_IV_NEXT:%.*]], [[INNER_EXIT:%.*]] ]174; CHECK-NEXT: [[TMP3:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP0]]175; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_N]], 4176; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]]177; CHECK: vector.memcheck:178; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP1]]179; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP]]180; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]181; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]182; CHECK: vector.ph:183; CHECK-NEXT: [[N_MOD_VF:%.*]] = urem i64 [[WIDE_N]], 4184; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[WIDE_N]], [[N_MOD_VF]]185; CHECK-NEXT: br label [[VECTOR_BODY:%.*]]186; CHECK: vector.body:187; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]188; CHECK-NEXT: [[TMP4:%.*]] = add nuw nsw i64 [[INDEX]], [[TMP3]]189; CHECK-NEXT: [[TMP5:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP4]]190; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP5]], align 4, !alias.scope [[META9:![0-9]+]]191; CHECK-NEXT: [[TMP6:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP4]]192; CHECK-NEXT: [[WIDE_LOAD2:%.*]] = load <4 x i32>, ptr [[TMP6]], align 4, !alias.scope [[META12:![0-9]+]], !noalias [[META9]]193; CHECK-NEXT: [[TMP7:%.*]] = add nsw <4 x i32> [[WIDE_LOAD2]], [[WIDE_LOAD]]194; CHECK-NEXT: store <4 x i32> [[TMP7]], ptr [[TMP6]], align 4, !alias.scope [[META12]], !noalias [[META9]]195; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4196; CHECK-NEXT: [[TMP8:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]197; CHECK-NEXT: br i1 [[TMP8]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP14:![0-9]+]]198; CHECK: middle.block:199; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_N]], [[N_VEC]]200; CHECK-NEXT: br i1 [[CMP_N]], label [[INNER_EXIT]], label [[SCALAR_PH]]201; CHECK: scalar.ph:202; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[OUTER_LOOP]] ], [ 0, [[VECTOR_MEMCHECK]] ]203; CHECK-NEXT: br label [[INNER_LOOP:%.*]]204; CHECK: inner.loop:205; CHECK-NEXT: [[IV_INNER:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_INNER_NEXT:%.*]], [[INNER_LOOP]] ]206; CHECK-NEXT: [[TMP9:%.*]] = add nuw nsw i64 [[IV_INNER]], [[TMP3]]207; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP9]]208; CHECK-NEXT: [[TMP10:%.*]] = load i32, ptr [[ARRAYIDX_US]], align 4209; CHECK-NEXT: [[ARRAYIDX8_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP9]]210; CHECK-NEXT: [[TMP11:%.*]] = load i32, ptr [[ARRAYIDX8_US]], align 4211; CHECK-NEXT: [[ADD9_US:%.*]] = add nsw i32 [[TMP11]], [[TMP10]]212; CHECK-NEXT: store i32 [[ADD9_US]], ptr [[ARRAYIDX8_US]], align 4213; CHECK-NEXT: [[IV_INNER_NEXT]] = add nuw nsw i64 [[IV_INNER]], 1214; CHECK-NEXT: [[INNER_EXIT_COND:%.*]] = icmp eq i64 [[IV_INNER_NEXT]], [[WIDE_N]]215; CHECK-NEXT: br i1 [[INNER_EXIT_COND]], label [[INNER_EXIT]], label [[INNER_LOOP]], !llvm.loop [[LOOP15:![0-9]+]]216; CHECK: inner.exit:217; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nuw nsw i64 [[OUTER_IV]], 1218; CHECK-NEXT: [[OUTER_EXIT_COND:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[WIDE_M]]219; CHECK-NEXT: br i1 [[OUTER_EXIT_COND]], label [[OUTER_EXIT:%.*]], label [[OUTER_LOOP]]220; CHECK: outer.exit:221; CHECK-NEXT: ret void222;223entry:224 %0 = zext i32 %n to i64225 %wide.m = zext i32 %m to i64226 %wide.n = zext i32 %n to i64227 br label %outer.loop228 229outer.loop:230 %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %inner.exit ]231 %1 = mul nsw i64 %outer.iv, %0232 br label %inner.loop233 234inner.loop:235 %iv.inner = phi i64 [ 0, %outer.loop ], [ %iv.inner.next, %inner.loop ]236 %2 = add nuw nsw i64 %iv.inner, %1237 %arrayidx.us = getelementptr inbounds i32, ptr %src, i64 %2238 %3 = load i32, ptr %arrayidx.us, align 4239 %arrayidx8.us = getelementptr inbounds i32, ptr %dst, i64 %2240 %4 = load i32, ptr %arrayidx8.us, align 4241 %add9.us = add nsw i32 %4, %3242 store i32 %add9.us, ptr %arrayidx8.us, align 4243 %iv.inner.next = add nuw nsw i64 %iv.inner, 1244 %inner.exit.cond = icmp eq i64 %iv.inner.next, %wide.n245 br i1 %inner.exit.cond, label %inner.exit, label %inner.loop246 247inner.exit:248 %outer.iv.next = add nuw nsw i64 %outer.iv, 1249 %outer.exit.cond = icmp eq i64 %outer.iv.next, %wide.m250 br i1 %outer.exit.cond, label %outer.exit, label %outer.loop251 252outer.exit:253 ret void254}255 256 257; Equivalent example in C:258; void full_checks_diff_strides(int32_t *dst, int32_t *src, int m, int n) {259; for (int i = 0; i < m; i++) {260; for (int j = 0; j < n; j++) {261; dst[(i * (n + 1)) + j] += src[(i * n) + j];262; }263; }264; }265; We decide to do full runtime checks here (as opposed to diff checks) due to266; the additional load of 'dst[(i * n) + j]' in the loop.267; NOTE: This is different to the test above (@full_checks) because the dst array268; is accessed with a higher stride compared src, and therefore the inner loop269; runtime checks will vary for each outer loop iteration.270 271; DEBUG-LABEL: 'full_checks_diff_strides'272; DEBUG: LAA: Found an analyzable loop: inner.loop273; DEBUG-NOT: LAA: Creating diff runtime check for:274; DEBUG: LAA: Adding RT check for range:275; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting276; DEBUG-NEXT: Start: %dst End: ((4 * (zext i32 %n to i64))<nuw><nsw> + ((4 + (4 * (zext i32 %n to i64))<nuw><nsw>)<nuw><nsw> * (-1 + (zext i32 %m to i64))<nsw>) + %dst)277; DEBUG-NEXT: LAA: Adding RT check for range:278; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting279; DEBUG-NEXT: Start: %src End: ((4 * (zext i32 %m to i64) * (zext i32 %n to i64)) + %src)280 281define void @full_checks_diff_strides(ptr nocapture noundef %dst, ptr nocapture noundef readonly %src, i32 noundef %m, i32 noundef %n) {282; CHECK-LABEL: define void @full_checks_diff_strides283; CHECK-SAME: (ptr noundef captures(none) [[DST:%.*]], ptr noundef readonly captures(none) [[SRC:%.*]], i32 noundef [[M:%.*]], i32 noundef [[N:%.*]]) {284; CHECK-NEXT: entry:285; CHECK-NEXT: [[WIDE_M:%.*]] = zext i32 [[M]] to i64286; CHECK-NEXT: [[WIDE_N:%.*]] = zext i32 [[N]] to i64287; CHECK-NEXT: [[TMP0:%.*]] = add nsw i64 [[WIDE_M]], -1288; CHECK-NEXT: [[TMP1:%.*]] = shl nuw nsw i64 [[WIDE_N]], 2289; CHECK-NEXT: [[TMP2:%.*]] = add nuw nsw i64 [[TMP1]], 4290; CHECK-NEXT: [[TMP3:%.*]] = mul i64 [[TMP0]], [[TMP2]]291; CHECK-NEXT: [[TMP4:%.*]] = add i64 [[TMP3]], [[TMP1]]292; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP4]]293; CHECK-NEXT: [[TMP5:%.*]] = mul i64 [[WIDE_N]], [[WIDE_M]]294; CHECK-NEXT: [[TMP6:%.*]] = shl i64 [[TMP5]], 2295; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP6]]296; CHECK-NEXT: br label [[OUTER_LOOP:%.*]]297; CHECK: outer.loop:298; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_IV_NEXT:%.*]], [[INNER_EXIT:%.*]] ]299; CHECK-NEXT: [[NPLUS1:%.*]] = add nuw nsw i32 [[N]], 1300; CHECK-NEXT: [[WIDE_NPLUS1:%.*]] = zext i32 [[NPLUS1]] to i64301; CHECK-NEXT: [[TMP7:%.*]] = mul nsw i64 [[OUTER_IV]], [[WIDE_N]]302; CHECK-NEXT: [[TMP8:%.*]] = mul nsw i64 [[OUTER_IV]], [[WIDE_NPLUS1]]303; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_N]], 4304; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]]305; CHECK: vector.memcheck:306; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP1]]307; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP]]308; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]309; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]310; CHECK: vector.ph:311; CHECK-NEXT: [[N_MOD_VF:%.*]] = urem i64 [[WIDE_N]], 4312; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[WIDE_N]], [[N_MOD_VF]]313; CHECK-NEXT: br label [[VECTOR_BODY:%.*]]314; CHECK: vector.body:315; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]316; CHECK-NEXT: [[TMP9:%.*]] = add nuw nsw i64 [[INDEX]], [[TMP7]]317; CHECK-NEXT: [[TMP10:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP9]]318; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP10]], align 4, !alias.scope [[META16:![0-9]+]]319; CHECK-NEXT: [[TMP11:%.*]] = add nuw nsw i64 [[INDEX]], [[TMP8]]320; CHECK-NEXT: [[TMP12:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP11]]321; CHECK-NEXT: [[WIDE_LOAD2:%.*]] = load <4 x i32>, ptr [[TMP12]], align 4, !alias.scope [[META19:![0-9]+]], !noalias [[META16]]322; CHECK-NEXT: [[TMP13:%.*]] = add nsw <4 x i32> [[WIDE_LOAD2]], [[WIDE_LOAD]]323; CHECK-NEXT: store <4 x i32> [[TMP13]], ptr [[TMP12]], align 4, !alias.scope [[META19]], !noalias [[META16]]324; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4325; CHECK-NEXT: [[TMP14:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]326; CHECK-NEXT: br i1 [[TMP14]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP21:![0-9]+]]327; CHECK: middle.block:328; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_N]], [[N_VEC]]329; CHECK-NEXT: br i1 [[CMP_N]], label [[INNER_EXIT]], label [[SCALAR_PH]]330; CHECK: scalar.ph:331; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[OUTER_LOOP]] ], [ 0, [[VECTOR_MEMCHECK]] ]332; CHECK-NEXT: br label [[INNER_LOOP:%.*]]333; CHECK: inner.loop:334; CHECK-NEXT: [[IV_INNER:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_INNER_NEXT:%.*]], [[INNER_LOOP]] ]335; CHECK-NEXT: [[TMP15:%.*]] = add nuw nsw i64 [[IV_INNER]], [[TMP7]]336; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP15]]337; CHECK-NEXT: [[TMP16:%.*]] = load i32, ptr [[ARRAYIDX_US]], align 4338; CHECK-NEXT: [[TMP17:%.*]] = add nuw nsw i64 [[IV_INNER]], [[TMP8]]339; CHECK-NEXT: [[ARRAYIDX8_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP17]]340; CHECK-NEXT: [[TMP18:%.*]] = load i32, ptr [[ARRAYIDX8_US]], align 4341; CHECK-NEXT: [[ADD9_US:%.*]] = add nsw i32 [[TMP18]], [[TMP16]]342; CHECK-NEXT: store i32 [[ADD9_US]], ptr [[ARRAYIDX8_US]], align 4343; CHECK-NEXT: [[IV_INNER_NEXT]] = add nuw nsw i64 [[IV_INNER]], 1344; CHECK-NEXT: [[INNER_EXIT_COND:%.*]] = icmp eq i64 [[IV_INNER_NEXT]], [[WIDE_N]]345; CHECK-NEXT: br i1 [[INNER_EXIT_COND]], label [[INNER_EXIT]], label [[INNER_LOOP]], !llvm.loop [[LOOP22:![0-9]+]]346; CHECK: inner.exit:347; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nuw nsw i64 [[OUTER_IV]], 1348; CHECK-NEXT: [[OUTER_EXIT_COND:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[WIDE_M]]349; CHECK-NEXT: br i1 [[OUTER_EXIT_COND]], label [[OUTER_EXIT:%.*]], label [[OUTER_LOOP]]350; CHECK: outer.exit:351; CHECK-NEXT: ret void352;353entry:354 %wide.m = zext i32 %m to i64355 %wide.n = zext i32 %n to i64356 br label %outer.loop357 358outer.loop:359 %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %inner.exit ]360 %nplus1 = add nuw nsw i32 %n, 1361 %wide.nplus1 = zext i32 %nplus1 to i64362 %0 = mul nsw i64 %outer.iv, %wide.n363 %1 = mul nsw i64 %outer.iv, %wide.nplus1364 br label %inner.loop365 366inner.loop:367 %iv.inner = phi i64 [ 0, %outer.loop ], [ %iv.inner.next, %inner.loop ]368 %2 = add nuw nsw i64 %iv.inner, %0369 %arrayidx.us = getelementptr inbounds i32, ptr %src, i64 %2370 %3 = load i32, ptr %arrayidx.us, align 4371 %4 = add nuw nsw i64 %iv.inner, %1372 %arrayidx8.us = getelementptr inbounds i32, ptr %dst, i64 %4373 %5 = load i32, ptr %arrayidx8.us, align 4374 %add9.us = add nsw i32 %5, %3375 store i32 %add9.us, ptr %arrayidx8.us, align 4376 %iv.inner.next = add nuw nsw i64 %iv.inner, 1377 %inner.exit.cond = icmp eq i64 %iv.inner.next, %wide.n378 br i1 %inner.exit.cond, label %inner.exit, label %inner.loop379 380inner.exit:381 %outer.iv.next = add nuw nsw i64 %outer.iv, 1382 %outer.exit.cond = icmp eq i64 %outer.iv.next, %wide.m383 br i1 %outer.exit.cond, label %outer.exit, label %outer.loop384 385outer.exit:386 ret void387}388 389 390; Equivalent example in C:391; void diff_checks_src_start_invariant(int32_t *dst, int32_t *src, int m, int n) {392; for (int i = 0; i < m; i++) {393; for (int j = 0; j < n; j++) {394; dst[(i * n) + j] = src[j];395; }396; }397; }398 399; DEBUG-LABEL: 'diff_checks_src_start_invariant'400; DEBUG: LAA: Found an analyzable loop: inner.loop401; DEBUG-NOT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting402 403define void @diff_checks_src_start_invariant(ptr nocapture noundef writeonly %dst, ptr nocapture noundef readonly %src, i32 noundef %m, i32 noundef %n) {404; CHECK-LABEL: define void @diff_checks_src_start_invariant405; CHECK-SAME: (ptr noundef writeonly captures(none) [[DST:%.*]], ptr noundef readonly captures(none) [[SRC:%.*]], i32 noundef [[M:%.*]], i32 noundef [[N:%.*]]) {406; CHECK-NEXT: entry:407; CHECK-NEXT: [[SRC2:%.*]] = ptrtoint ptr [[SRC]] to i64408; CHECK-NEXT: [[DST1:%.*]] = ptrtoint ptr [[DST]] to i64409; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[N]] to i64410; CHECK-NEXT: [[WIDE_M:%.*]] = zext i32 [[M]] to i64411; CHECK-NEXT: [[WIDE_N:%.*]] = zext i32 [[N]] to i64412; CHECK-NEXT: [[TMP1:%.*]] = sub i64 [[DST1]], [[SRC2]]413; CHECK-NEXT: [[TMP2:%.*]] = shl i64 [[WIDE_N]], 2414; CHECK-NEXT: br label [[OUTER_LOOP:%.*]]415; CHECK: outer.loop:416; CHECK-NEXT: [[IV_OUTER:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_OUTER_NEXT:%.*]], [[INNER_LOOP_EXIT:%.*]] ]417; CHECK-NEXT: [[TMP3:%.*]] = mul i64 [[TMP2]], [[IV_OUTER]]418; CHECK-NEXT: [[TMP4:%.*]] = add i64 [[TMP1]], [[TMP3]]419; CHECK-NEXT: [[TMP5:%.*]] = mul nsw i64 [[IV_OUTER]], [[TMP0]]420; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_N]], 4421; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]]422; CHECK: vector.memcheck:423; CHECK-NEXT: [[DIFF_CHECK:%.*]] = icmp ult i64 [[TMP4]], 16424; CHECK-NEXT: br i1 [[DIFF_CHECK]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]425; CHECK: vector.ph:426; CHECK-NEXT: [[N_MOD_VF:%.*]] = urem i64 [[WIDE_N]], 4427; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[WIDE_N]], [[N_MOD_VF]]428; CHECK-NEXT: br label [[VECTOR_BODY:%.*]]429; CHECK: vector.body:430; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]431; CHECK-NEXT: [[TMP6:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[INDEX]]432; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP6]], align 4433; CHECK-NEXT: [[TMP7:%.*]] = add nuw nsw i64 [[INDEX]], [[TMP5]]434; CHECK-NEXT: [[TMP8:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP7]]435; CHECK-NEXT: store <4 x i32> [[WIDE_LOAD]], ptr [[TMP8]], align 4436; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4437; CHECK-NEXT: [[TMP9:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]438; CHECK-NEXT: br i1 [[TMP9]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP23:![0-9]+]]439; CHECK: middle.block:440; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_N]], [[N_VEC]]441; CHECK-NEXT: br i1 [[CMP_N]], label [[INNER_LOOP_EXIT]], label [[SCALAR_PH]]442; CHECK: scalar.ph:443; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[OUTER_LOOP]] ], [ 0, [[VECTOR_MEMCHECK]] ]444; CHECK-NEXT: br label [[INNER_LOOP:%.*]]445; CHECK: inner.loop:446; CHECK-NEXT: [[IV_INNER:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_INNER_NEXT:%.*]], [[INNER_LOOP]] ]447; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[IV_INNER]]448; CHECK-NEXT: [[TMP10:%.*]] = load i32, ptr [[ARRAYIDX_US]], align 4449; CHECK-NEXT: [[TMP11:%.*]] = add nuw nsw i64 [[IV_INNER]], [[TMP5]]450; CHECK-NEXT: [[ARRAYIDX6_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP11]]451; CHECK-NEXT: store i32 [[TMP10]], ptr [[ARRAYIDX6_US]], align 4452; CHECK-NEXT: [[IV_INNER_NEXT]] = add nuw nsw i64 [[IV_INNER]], 1453; CHECK-NEXT: [[INNER_EXIT_COND:%.*]] = icmp eq i64 [[IV_INNER_NEXT]], [[WIDE_N]]454; CHECK-NEXT: br i1 [[INNER_EXIT_COND]], label [[INNER_LOOP_EXIT]], label [[INNER_LOOP]], !llvm.loop [[LOOP24:![0-9]+]]455; CHECK: inner.loop.exit:456; CHECK-NEXT: [[IV_OUTER_NEXT]] = add nuw nsw i64 [[IV_OUTER]], 1457; CHECK-NEXT: [[OUTER_EXIT_COND:%.*]] = icmp eq i64 [[IV_OUTER_NEXT]], [[WIDE_M]]458; CHECK-NEXT: br i1 [[OUTER_EXIT_COND]], label [[OUTER_LOOP_EXIT:%.*]], label [[OUTER_LOOP]]459; CHECK: outer.loop.exit:460; CHECK-NEXT: ret void461;462entry:463 %0 = zext i32 %n to i64464 %wide.m = zext i32 %m to i64465 %wide.n = zext i32 %n to i64466 br label %outer.loop467 468outer.loop:469 %iv.outer = phi i64 [ 0, %entry ], [ %iv.outer.next, %inner.loop.exit ]470 %1 = mul nsw i64 %iv.outer, %0471 br label %inner.loop472 473inner.loop:474 %iv.inner = phi i64 [ 0, %outer.loop ], [ %iv.inner.next, %inner.loop ]475 %arrayidx.us = getelementptr inbounds i32, ptr %src, i64 %iv.inner476 %2 = load i32, ptr %arrayidx.us, align 4477 %3 = add nuw nsw i64 %iv.inner, %1478 %arrayidx6.us = getelementptr inbounds i32, ptr %dst, i64 %3479 store i32 %2, ptr %arrayidx6.us, align 4480 %iv.inner.next = add nuw nsw i64 %iv.inner, 1481 %inner.exit.cond = icmp eq i64 %iv.inner.next, %wide.n482 br i1 %inner.exit.cond, label %inner.loop.exit, label %inner.loop483 484inner.loop.exit:485 %iv.outer.next = add nuw nsw i64 %iv.outer, 1486 %outer.exit.cond = icmp eq i64 %iv.outer.next, %wide.m487 br i1 %outer.exit.cond, label %outer.loop.exit, label %outer.loop488 489outer.loop.exit:490 ret void491}492 493 494; Equivalent example in C:495; void full_checks_src_start_invariant(int32_t *dst, int32_t *src, int m, int n) {496; for (int i = 0; i < m; i++) {497; for (int j = 0; j < n; j++) {498; dst[(i * n) + j] += src[j];499; }500; }501; }502 503; DEBUG-LABEL: 'full_checks_src_start_invariant'504; DEBUG: LAA: Found an analyzable loop: inner.loop505; DEBUG: LAA: Adding RT check for range:506; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting507; DEBUG-NEXT: Start: %dst End: ((4 * (zext i32 %m to i64) * (zext i32 %n to i64)) + %dst)508; DEBUG-NEXT: LAA: Adding RT check for range:509; DEBUG-NEXT: Start: %src End: ((4 * (zext i32 %n to i64))<nuw><nsw> + %src)510 511define void @full_checks_src_start_invariant(ptr nocapture noundef %dst, ptr nocapture noundef readonly %src, i32 noundef %m, i32 noundef %n) {512; CHECK-LABEL: define void @full_checks_src_start_invariant513; CHECK-SAME: (ptr noundef captures(none) [[DST:%.*]], ptr noundef readonly captures(none) [[SRC:%.*]], i32 noundef [[M:%.*]], i32 noundef [[N:%.*]]) {514; CHECK-NEXT: entry:515; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[N]] to i64516; CHECK-NEXT: [[WIDE_M:%.*]] = zext i32 [[M]] to i64517; CHECK-NEXT: [[WIDE_N:%.*]] = zext i32 [[N]] to i64518; CHECK-NEXT: [[TMP1:%.*]] = mul i64 [[WIDE_N]], [[WIDE_M]]519; CHECK-NEXT: [[TMP2:%.*]] = shl i64 [[TMP1]], 2520; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP2]]521; CHECK-NEXT: [[TMP3:%.*]] = shl nuw nsw i64 [[WIDE_N]], 2522; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP3]]523; CHECK-NEXT: br label [[OUTER_LOOP:%.*]]524; CHECK: outer.loop:525; CHECK-NEXT: [[IV_OUTER:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_OUTER_NEXT:%.*]], [[INNER_LOOP_EXIT:%.*]] ]526; CHECK-NEXT: [[TMP4:%.*]] = mul nsw i64 [[IV_OUTER]], [[TMP0]]527; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_N]], 4528; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]]529; CHECK: vector.memcheck:530; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP1]]531; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP]]532; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]533; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]534; CHECK: vector.ph:535; CHECK-NEXT: [[N_MOD_VF:%.*]] = urem i64 [[WIDE_N]], 4536; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[WIDE_N]], [[N_MOD_VF]]537; CHECK-NEXT: br label [[VECTOR_BODY:%.*]]538; CHECK: vector.body:539; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]540; CHECK-NEXT: [[TMP5:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[INDEX]]541; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP5]], align 4, !alias.scope [[META25:![0-9]+]]542; CHECK-NEXT: [[TMP6:%.*]] = add nuw nsw i64 [[INDEX]], [[TMP4]]543; CHECK-NEXT: [[TMP7:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP6]]544; CHECK-NEXT: [[WIDE_LOAD2:%.*]] = load <4 x i32>, ptr [[TMP7]], align 4, !alias.scope [[META28:![0-9]+]], !noalias [[META25]]545; CHECK-NEXT: [[TMP8:%.*]] = add nsw <4 x i32> [[WIDE_LOAD2]], [[WIDE_LOAD]]546; CHECK-NEXT: store <4 x i32> [[TMP8]], ptr [[TMP7]], align 4, !alias.scope [[META28]], !noalias [[META25]]547; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4548; CHECK-NEXT: [[TMP9:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]549; CHECK-NEXT: br i1 [[TMP9]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP30:![0-9]+]]550; CHECK: middle.block:551; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_N]], [[N_VEC]]552; CHECK-NEXT: br i1 [[CMP_N]], label [[INNER_LOOP_EXIT]], label [[SCALAR_PH]]553; CHECK: scalar.ph:554; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[OUTER_LOOP]] ], [ 0, [[VECTOR_MEMCHECK]] ]555; CHECK-NEXT: br label [[INNER_LOOP:%.*]]556; CHECK: inner.loop:557; CHECK-NEXT: [[IV_INNER:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_INNER_NEXT:%.*]], [[INNER_LOOP]] ]558; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[IV_INNER]]559; CHECK-NEXT: [[TMP10:%.*]] = load i32, ptr [[ARRAYIDX_US]], align 4560; CHECK-NEXT: [[TMP11:%.*]] = add nuw nsw i64 [[IV_INNER]], [[TMP4]]561; CHECK-NEXT: [[ARRAYIDX6_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP11]]562; CHECK-NEXT: [[TMP12:%.*]] = load i32, ptr [[ARRAYIDX6_US]], align 4563; CHECK-NEXT: [[ADD7_US:%.*]] = add nsw i32 [[TMP12]], [[TMP10]]564; CHECK-NEXT: store i32 [[ADD7_US]], ptr [[ARRAYIDX6_US]], align 4565; CHECK-NEXT: [[IV_INNER_NEXT]] = add nuw nsw i64 [[IV_INNER]], 1566; CHECK-NEXT: [[INNER_EXIT_COND:%.*]] = icmp eq i64 [[IV_INNER_NEXT]], [[WIDE_N]]567; CHECK-NEXT: br i1 [[INNER_EXIT_COND]], label [[INNER_LOOP_EXIT]], label [[INNER_LOOP]], !llvm.loop [[LOOP31:![0-9]+]]568; CHECK: inner.loop.exit:569; CHECK-NEXT: [[IV_OUTER_NEXT]] = add nuw nsw i64 [[IV_OUTER]], 1570; CHECK-NEXT: [[OUTER_EXIT_COND:%.*]] = icmp eq i64 [[IV_OUTER_NEXT]], [[WIDE_M]]571; CHECK-NEXT: br i1 [[OUTER_EXIT_COND]], label [[OUTER_LOOP_EXIT:%.*]], label [[OUTER_LOOP]]572; CHECK: outer.loop.exit:573; CHECK-NEXT: ret void574;575entry:576 %0 = zext i32 %n to i64577 %wide.m = zext i32 %m to i64578 %wide.n = zext i32 %n to i64579 br label %outer.loop580 581outer.loop:582 %iv.outer = phi i64 [ 0, %entry ], [ %iv.outer.next, %inner.loop.exit ]583 %1 = mul nsw i64 %iv.outer, %0584 br label %inner.loop585 586inner.loop:587 %iv.inner = phi i64 [ 0, %outer.loop ], [ %iv.inner.next, %inner.loop ]588 %arrayidx.us = getelementptr inbounds i32, ptr %src, i64 %iv.inner589 %2 = load i32, ptr %arrayidx.us, align 4590 %3 = add nuw nsw i64 %iv.inner, %1591 %arrayidx6.us = getelementptr inbounds i32, ptr %dst, i64 %3592 %4 = load i32, ptr %arrayidx6.us, align 4593 %add7.us = add nsw i32 %4, %2594 store i32 %add7.us, ptr %arrayidx6.us, align 4595 %iv.inner.next = add nuw nsw i64 %iv.inner, 1596 %inner.exit.cond = icmp eq i64 %iv.inner.next, %wide.n597 br i1 %inner.exit.cond, label %inner.loop.exit, label %inner.loop598 599inner.loop.exit:600 %iv.outer.next = add nuw nsw i64 %iv.outer, 1601 %outer.exit.cond = icmp eq i64 %iv.outer.next, %wide.m602 br i1 %outer.exit.cond, label %outer.loop.exit, label %outer.loop603 604outer.loop.exit:605 ret void606}607 608 609; Equivalent example in C:610; void triple_nested_loop_mixed_access(int *dst, int *src, int m, int n, int o) {611; for (int i = 0; i < m; i++) {612; for (int j = 0; j < n; j++) {613; for (int l = 0; l < o; l++) {614; dst[(i * n * (o + 1)) + (j * o) + l] += src[(i * n * o) + l];615; }616; }617; }618; }619; The 'src' access varies with the outermost loop, rather than the parent of the620; innermost loop. Hence we don't expand `src`, although in theory we could do.621 622; DEBUG-LABEL: 'triple_nested_loop_mixed_access'623; DEBUG: LAA: Found an analyzable loop: inner.loop624; DEBUG-NOT: LAA: Creating diff runtime check for:625; DEBUG: LAA: Adding RT check for range:626; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting627; DEBUG-NEXT: Start: {%dst,+,(4 * (zext i32 (1 + %o)<nsw> to i64) * (zext i32 %n to i64))}<%outer.outer.loop> End: {((4 * (zext i32 %n to i64) * (zext i32 %o to i64)) + %dst),+,(4 * (zext i32 (1 + %o)<nsw> to i64) * (zext i32 %n to i64))}<%outer.outer.loop>628; DEBUG-NEXT: LAA: Adding RT check for range:629; DEBUG-NEXT: Start: {%src,+,(4 * (zext i32 %n to i64) * (zext i32 %o to i64))}<%outer.outer.loop> End: {((4 * (zext i32 %o to i64))<nuw><nsw> + %src),+,(4 * (zext i32 %n to i64) * (zext i32 %o to i64))}<%outer.outer.loop>630 631define void @triple_nested_loop_mixed_access(ptr nocapture noundef %dst, ptr nocapture noundef readonly %src, i32 noundef %m, i32 noundef %n, i32 noundef %o) {632; CHECK-LABEL: define void @triple_nested_loop_mixed_access633; CHECK-SAME: (ptr noundef captures(none) [[DST:%.*]], ptr noundef readonly captures(none) [[SRC:%.*]], i32 noundef [[M:%.*]], i32 noundef [[N:%.*]], i32 noundef [[O:%.*]]) {634; CHECK-NEXT: entry:635; CHECK-NEXT: [[ADD11:%.*]] = add nsw i32 [[O]], 1636; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[O]] to i64637; CHECK-NEXT: [[TMP1:%.*]] = zext i32 [[N]] to i64638; CHECK-NEXT: [[TMP2:%.*]] = zext i32 [[ADD11]] to i64639; CHECK-NEXT: [[WIDE_TRIP_COUNT68:%.*]] = zext i32 [[M]] to i64640; CHECK-NEXT: [[WIDE_TRIP_COUNT60:%.*]] = zext i32 [[N]] to i64641; CHECK-NEXT: [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[O]] to i64642; CHECK-NEXT: [[TMP3:%.*]] = mul i64 [[TMP1]], [[TMP2]]643; CHECK-NEXT: [[TMP4:%.*]] = shl i64 [[TMP3]], 2644; CHECK-NEXT: [[TMP5:%.*]] = mul i64 [[WIDE_TRIP_COUNT]], [[TMP1]]645; CHECK-NEXT: [[TMP6:%.*]] = shl i64 [[TMP5]], 2646; CHECK-NEXT: [[TMP7:%.*]] = mul i64 [[WIDE_TRIP_COUNT]], [[TMP1]]647; CHECK-NEXT: [[TMP8:%.*]] = shl i64 [[TMP7]], 2648; CHECK-NEXT: [[TMP9:%.*]] = shl nuw nsw i64 [[WIDE_TRIP_COUNT]], 2649; CHECK-NEXT: br label [[OUTER_OUTER_LOOP:%.*]]650; CHECK: outer.outer.loop:651; CHECK-NEXT: [[OUTER_OUTER_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_OUTER_IV_NEXT:%.*]], [[OUTER_LOOP_END:%.*]] ]652; CHECK-NEXT: [[TMP10:%.*]] = mul i64 [[TMP4]], [[OUTER_OUTER_IV]]653; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP10]]654; CHECK-NEXT: [[TMP11:%.*]] = add i64 [[TMP6]], [[TMP10]]655; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP11]]656; CHECK-NEXT: [[TMP12:%.*]] = mul i64 [[TMP8]], [[OUTER_OUTER_IV]]657; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP12]]658; CHECK-NEXT: [[TMP13:%.*]] = add i64 [[TMP9]], [[TMP12]]659; CHECK-NEXT: [[SCEVGEP3:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP13]]660; CHECK-NEXT: [[TMP14:%.*]] = mul nsw i64 [[OUTER_OUTER_IV]], [[TMP1]]661; CHECK-NEXT: [[TMP15:%.*]] = mul nsw i64 [[TMP14]], [[TMP0]]662; CHECK-NEXT: [[TMP16:%.*]] = mul nsw i64 [[TMP14]], [[TMP2]]663; CHECK-NEXT: br label [[OUTER_LOOP:%.*]]664; CHECK: outer.loop:665; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ [[OUTER_IV_NEXT:%.*]], [[INNER_LOOP_END:%.*]] ], [ 0, [[OUTER_OUTER_LOOP]] ]666; CHECK-NEXT: [[TMP17:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP0]]667; CHECK-NEXT: [[TMP18:%.*]] = add nuw nsw i64 [[TMP17]], [[TMP16]]668; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_TRIP_COUNT]], 4669; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]]670; CHECK: vector.memcheck:671; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[SCEVGEP]], [[SCEVGEP3]]672; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SCEVGEP2]], [[SCEVGEP1]]673; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]674; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]675; CHECK: vector.ph:676; CHECK-NEXT: [[N_MOD_VF:%.*]] = urem i64 [[WIDE_TRIP_COUNT]], 4677; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[WIDE_TRIP_COUNT]], [[N_MOD_VF]]678; CHECK-NEXT: br label [[VECTOR_BODY:%.*]]679; CHECK: vector.body:680; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]681; CHECK-NEXT: [[TMP19:%.*]] = add nuw nsw i64 [[INDEX]], [[TMP15]]682; CHECK-NEXT: [[TMP20:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP19]]683; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP20]], align 4, !alias.scope [[META32:![0-9]+]]684; CHECK-NEXT: [[TMP21:%.*]] = add nuw nsw i64 [[TMP18]], [[INDEX]]685; CHECK-NEXT: [[TMP22:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP21]]686; CHECK-NEXT: [[WIDE_LOAD4:%.*]] = load <4 x i32>, ptr [[TMP22]], align 4, !alias.scope [[META35:![0-9]+]], !noalias [[META32]]687; CHECK-NEXT: [[TMP23:%.*]] = add nsw <4 x i32> [[WIDE_LOAD4]], [[WIDE_LOAD]]688; CHECK-NEXT: store <4 x i32> [[TMP23]], ptr [[TMP22]], align 4, !alias.scope [[META35]], !noalias [[META32]]689; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4690; CHECK-NEXT: [[TMP24:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]691; CHECK-NEXT: br i1 [[TMP24]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP37:![0-9]+]]692; CHECK: middle.block:693; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_TRIP_COUNT]], [[N_VEC]]694; CHECK-NEXT: br i1 [[CMP_N]], label [[INNER_LOOP_END]], label [[SCALAR_PH]]695; CHECK: scalar.ph:696; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[OUTER_LOOP]] ], [ 0, [[VECTOR_MEMCHECK]] ]697; CHECK-NEXT: br label [[INNER_LOOP:%.*]]698; CHECK: inner.loop:699; CHECK-NEXT: [[INNER_IV:%.*]] = phi i64 [ [[INNER_IV_NEXT:%.*]], [[INNER_LOOP]] ], [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ]700; CHECK-NEXT: [[TMP25:%.*]] = add nuw nsw i64 [[INNER_IV]], [[TMP15]]701; CHECK-NEXT: [[ARRAYIDX_US_US_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP25]]702; CHECK-NEXT: [[TMP26:%.*]] = load i32, ptr [[ARRAYIDX_US_US_US]], align 4703; CHECK-NEXT: [[TMP27:%.*]] = add nuw nsw i64 [[TMP18]], [[INNER_IV]]704; CHECK-NEXT: [[ARRAYIDX17_US_US_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP27]]705; CHECK-NEXT: [[TMP28:%.*]] = load i32, ptr [[ARRAYIDX17_US_US_US]], align 4706; CHECK-NEXT: [[ADD18_US_US_US:%.*]] = add nsw i32 [[TMP28]], [[TMP26]]707; CHECK-NEXT: store i32 [[ADD18_US_US_US]], ptr [[ARRAYIDX17_US_US_US]], align 4708; CHECK-NEXT: [[INNER_IV_NEXT]] = add nuw nsw i64 [[INNER_IV]], 1709; CHECK-NEXT: [[EXITCOND_NOT:%.*]] = icmp eq i64 [[INNER_IV_NEXT]], [[WIDE_TRIP_COUNT]]710; CHECK-NEXT: br i1 [[EXITCOND_NOT]], label [[INNER_LOOP_END]], label [[INNER_LOOP]], !llvm.loop [[LOOP38:![0-9]+]]711; CHECK: inner.loop.end:712; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nuw nsw i64 [[OUTER_IV]], 1713; CHECK-NEXT: [[EXIT_OUTER:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[WIDE_TRIP_COUNT60]]714; CHECK-NEXT: br i1 [[EXIT_OUTER]], label [[OUTER_LOOP_END]], label [[OUTER_LOOP]]715; CHECK: outer.loop.end:716; CHECK-NEXT: [[OUTER_OUTER_IV_NEXT]] = add nuw nsw i64 [[OUTER_OUTER_IV]], 1717; CHECK-NEXT: [[EXIT_OUTER_OUTER:%.*]] = icmp eq i64 [[OUTER_OUTER_IV_NEXT]], [[WIDE_TRIP_COUNT68]]718; CHECK-NEXT: br i1 [[EXIT_OUTER_OUTER]], label [[EXIT:%.*]], label [[OUTER_OUTER_LOOP]]719; CHECK: exit:720; CHECK-NEXT: ret void721;722entry:723 %add11 = add nsw i32 %o, 1724 %0 = zext i32 %o to i64725 %1 = zext i32 %n to i64726 %2 = zext i32 %add11 to i64727 %wide.trip.count68 = zext i32 %m to i64728 %wide.trip.count60 = zext i32 %n to i64729 %wide.trip.count = zext i32 %o to i64730 br label %outer.outer.loop731 732outer.outer.loop:733 %outer.outer.iv = phi i64 [ 0, %entry ], [ %outer.outer.iv.next, %outer.loop.end ]734 %3 = mul nsw i64 %outer.outer.iv, %1735 %4 = mul nsw i64 %3, %0736 %5 = mul nsw i64 %3, %2737 br label %outer.loop738 739outer.loop:740 %outer.iv = phi i64 [ %outer.iv.next, %inner.loop.end ], [ 0, %outer.outer.loop ]741 %6 = mul nsw i64 %outer.iv, %0742 %7 = add nuw nsw i64 %6, %5743 br label %inner.loop744 745inner.loop:746 %inner.iv = phi i64 [ %inner.iv.next, %inner.loop ], [ 0, %outer.loop ]747 %8 = add nuw nsw i64 %inner.iv, %4748 %arrayidx.us.us.us = getelementptr inbounds i32, ptr %src, i64 %8749 %9 = load i32, ptr %arrayidx.us.us.us, align 4750 %10 = add nuw nsw i64 %7, %inner.iv751 %arrayidx17.us.us.us = getelementptr inbounds i32, ptr %dst, i64 %10752 %11 = load i32, ptr %arrayidx17.us.us.us, align 4753 %add18.us.us.us = add nsw i32 %11, %9754 store i32 %add18.us.us.us, ptr %arrayidx17.us.us.us, align 4755 %inner.iv.next = add nuw nsw i64 %inner.iv, 1756 %exitcond.not = icmp eq i64 %inner.iv.next, %wide.trip.count757 br i1 %exitcond.not, label %inner.loop.end, label %inner.loop758 759inner.loop.end:760 %outer.iv.next = add nuw nsw i64 %outer.iv, 1761 %exit.outer = icmp eq i64 %outer.iv.next, %wide.trip.count60762 br i1 %exit.outer, label %outer.loop.end, label %outer.loop763 764outer.loop.end:765 %outer.outer.iv.next = add nuw nsw i64 %outer.outer.iv, 1766 %exit.outer.outer = icmp eq i64 %outer.outer.iv.next, %wide.trip.count68767 br i1 %exit.outer.outer, label %exit, label %outer.outer.loop768 769exit:770 ret void771}772 773 774; Equivalent example in C:775; void uncomputable_outer_tc(int32_t *dst, int32_t *src, char *str, int n) {776; int i;777; while (str[i] != '\0') {778; for (int j = 0; j < n; j++) {779; dst[(i * (n + 1)) + j] += src[(i * n) + j];780; }781; i++;782; }783; }784; Outer loop trip count is uncomputable so we shouldn't expand the ranges.785 786; DEBUG-LABEL: 'uncomputable_outer_tc'787; DEBUG: LAA: Found an analyzable loop: inner.loop788; DEBUG: LAA: Adding RT check for range:789; DEBUG-NEXT: Start: {%dst,+,(4 * (zext i32 (1 + %n) to i64))<nuw><nsw>}<%outer.loop> End: {((4 * (zext i32 %n to i64))<nuw><nsw> + %dst),+,(4 * (zext i32 (1 + %n) to i64))<nuw><nsw>}<%outer.loop>790; DEBUG-NEXT: LAA: Adding RT check for range:791; DEBUG-NEXT: Start: {%src,+,(4 * (zext i32 %n to i64))<nuw><nsw>}<%outer.loop> End: {((4 * (zext i32 %n to i64))<nuw><nsw> + %src),+,(4 * (zext i32 %n to i64))<nuw><nsw>}<%outer.loop>792 793define void @uncomputable_outer_tc(ptr nocapture noundef %dst, ptr nocapture noundef readonly %src, ptr nocapture noundef readonly %str, i32 noundef %n) {794; CHECK-LABEL: define void @uncomputable_outer_tc795; CHECK-SAME: (ptr noundef captures(none) [[DST:%.*]], ptr noundef readonly captures(none) [[SRC:%.*]], ptr noundef readonly captures(none) [[STR:%.*]], i32 noundef [[N:%.*]]) {796; CHECK-NEXT: entry:797; CHECK-NEXT: [[TMP0:%.*]] = load i8, ptr [[STR]], align 1798; CHECK-NEXT: [[CMP_NOT23:%.*]] = icmp ne i8 [[TMP0]], 0799; CHECK-NEXT: [[CMP221:%.*]] = icmp sgt i32 [[N]], 0800; CHECK-NEXT: [[OR_COND:%.*]] = and i1 [[CMP_NOT23]], [[CMP221]]801; CHECK-NEXT: br i1 [[OR_COND]], label [[OUTER_LOOP_PREHEADER:%.*]], label [[WHILE_END:%.*]]802; CHECK: outer.loop.preheader:803; CHECK-NEXT: [[ADD6:%.*]] = add nuw nsw i32 [[N]], 1804; CHECK-NEXT: [[TMP1:%.*]] = zext i32 [[N]] to i64805; CHECK-NEXT: [[TMP2:%.*]] = zext i32 [[ADD6]] to i64806; CHECK-NEXT: [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[N]] to i64807; CHECK-NEXT: [[TMP3:%.*]] = shl i64 [[TMP2]], 2808; CHECK-NEXT: [[TMP4:%.*]] = shl nuw nsw i64 [[WIDE_TRIP_COUNT]], 2809; CHECK-NEXT: [[TMP5:%.*]] = shl i64 [[WIDE_TRIP_COUNT]], 2810; CHECK-NEXT: br label [[OUTER_LOOP:%.*]]811; CHECK: outer.loop:812; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, [[OUTER_LOOP_PREHEADER]] ], [ [[OUTER_IV_NEXT:%.*]], [[INNER_LOOP_EXIT:%.*]] ]813; CHECK-NEXT: [[TMP6:%.*]] = mul i64 [[TMP3]], [[OUTER_IV]]814; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP6]]815; CHECK-NEXT: [[TMP7:%.*]] = add i64 [[TMP4]], [[TMP6]]816; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP7]]817; CHECK-NEXT: [[TMP8:%.*]] = mul i64 [[TMP5]], [[OUTER_IV]]818; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP8]]819; CHECK-NEXT: [[TMP9:%.*]] = add i64 [[TMP4]], [[TMP8]]820; CHECK-NEXT: [[SCEVGEP3:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP9]]821; CHECK-NEXT: [[TMP10:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP1]]822; CHECK-NEXT: [[TMP11:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP2]]823; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_TRIP_COUNT]], 4824; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]]825; CHECK: vector.memcheck:826; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[SCEVGEP]], [[SCEVGEP3]]827; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SCEVGEP2]], [[SCEVGEP1]]828; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]829; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]830; CHECK: vector.ph:831; CHECK-NEXT: [[N_MOD_VF:%.*]] = urem i64 [[WIDE_TRIP_COUNT]], 4832; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[WIDE_TRIP_COUNT]], [[N_MOD_VF]]833; CHECK-NEXT: br label [[VECTOR_BODY:%.*]]834; CHECK: vector.body:835; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]836; CHECK-NEXT: [[TMP12:%.*]] = add nsw i64 [[INDEX]], [[TMP10]]837; CHECK-NEXT: [[TMP13:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP12]]838; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP13]], align 4, !alias.scope [[META39:![0-9]+]]839; CHECK-NEXT: [[TMP14:%.*]] = add nsw i64 [[INDEX]], [[TMP11]]840; CHECK-NEXT: [[TMP15:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP14]]841; CHECK-NEXT: [[WIDE_LOAD4:%.*]] = load <4 x i32>, ptr [[TMP15]], align 4, !alias.scope [[META42:![0-9]+]], !noalias [[META39]]842; CHECK-NEXT: [[TMP16:%.*]] = add nsw <4 x i32> [[WIDE_LOAD4]], [[WIDE_LOAD]]843; CHECK-NEXT: store <4 x i32> [[TMP16]], ptr [[TMP15]], align 4, !alias.scope [[META42]], !noalias [[META39]]844; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4845; CHECK-NEXT: [[TMP17:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]846; CHECK-NEXT: br i1 [[TMP17]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP44:![0-9]+]]847; CHECK: middle.block:848; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_TRIP_COUNT]], [[N_VEC]]849; CHECK-NEXT: br i1 [[CMP_N]], label [[INNER_LOOP_EXIT]], label [[SCALAR_PH]]850; CHECK: scalar.ph:851; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[OUTER_LOOP]] ], [ 0, [[VECTOR_MEMCHECK]] ]852; CHECK-NEXT: br label [[INNER_LOOP:%.*]]853; CHECK: inner.loop:854; CHECK-NEXT: [[INNER_IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[INNER_IV_NEXT:%.*]], [[INNER_LOOP]] ]855; CHECK-NEXT: [[TMP18:%.*]] = add nsw i64 [[INNER_IV]], [[TMP10]]856; CHECK-NEXT: [[ARRAYIDX5_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP18]]857; CHECK-NEXT: [[TMP19:%.*]] = load i32, ptr [[ARRAYIDX5_US]], align 4858; CHECK-NEXT: [[TMP20:%.*]] = add nsw i64 [[INNER_IV]], [[TMP11]]859; CHECK-NEXT: [[ARRAYIDX10_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP20]]860; CHECK-NEXT: [[TMP21:%.*]] = load i32, ptr [[ARRAYIDX10_US]], align 4861; CHECK-NEXT: [[ADD11_US:%.*]] = add nsw i32 [[TMP21]], [[TMP19]]862; CHECK-NEXT: store i32 [[ADD11_US]], ptr [[ARRAYIDX10_US]], align 4863; CHECK-NEXT: [[INNER_IV_NEXT]] = add nuw nsw i64 [[INNER_IV]], 1864; CHECK-NEXT: [[EXITCOND_NOT:%.*]] = icmp eq i64 [[INNER_IV_NEXT]], [[WIDE_TRIP_COUNT]]865; CHECK-NEXT: br i1 [[EXITCOND_NOT]], label [[INNER_LOOP_EXIT]], label [[INNER_LOOP]], !llvm.loop [[LOOP45:![0-9]+]]866; CHECK: inner.loop.exit:867; CHECK-NEXT: [[OUTER_IV_NEXT]] = add i64 [[OUTER_IV]], 1868; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i8, ptr [[STR]], i64 [[OUTER_IV_NEXT]]869; CHECK-NEXT: [[TMP22:%.*]] = load i8, ptr [[ARRAYIDX_US]], align 1870; CHECK-NEXT: [[CMP_NOT_US:%.*]] = icmp eq i8 [[TMP22]], 0871; CHECK-NEXT: br i1 [[CMP_NOT_US]], label [[WHILE_END_LOOPEXIT:%.*]], label [[OUTER_LOOP]]872; CHECK: while.end.loopexit:873; CHECK-NEXT: br label [[WHILE_END]]874; CHECK: while.end:875; CHECK-NEXT: ret void876;877entry:878 %0 = load i8, ptr %str, align 1879 %cmp.not23 = icmp ne i8 %0, 0880 %cmp221 = icmp sgt i32 %n, 0881 %or.cond = and i1 %cmp.not23, %cmp221882 br i1 %or.cond, label %outer.loop.preheader, label %while.end883 884outer.loop.preheader:885 %add6 = add nuw nsw i32 %n, 1886 %1 = zext i32 %n to i64887 %2 = zext i32 %add6 to i64888 %wide.trip.count = zext i32 %n to i64889 br label %outer.loop890 891outer.loop:892 %outer.iv = phi i64 [ 0, %outer.loop.preheader ], [ %outer.iv.next, %inner.loop.exit ]893 %3 = mul nsw i64 %outer.iv, %1894 %4 = mul nsw i64 %outer.iv, %2895 br label %inner.loop896 897inner.loop:898 %inner.iv = phi i64 [ 0, %outer.loop ], [ %inner.iv.next, %inner.loop ]899 %5 = add nsw i64 %inner.iv, %3900 %arrayidx5.us = getelementptr inbounds i32, ptr %src, i64 %5901 %6 = load i32, ptr %arrayidx5.us, align 4902 %7 = add nsw i64 %inner.iv, %4903 %arrayidx10.us = getelementptr inbounds i32, ptr %dst, i64 %7904 %8 = load i32, ptr %arrayidx10.us, align 4905 %add11.us = add nsw i32 %8, %6906 store i32 %add11.us, ptr %arrayidx10.us, align 4907 %inner.iv.next = add nuw nsw i64 %inner.iv, 1908 %exitcond.not = icmp eq i64 %inner.iv.next, %wide.trip.count909 br i1 %exitcond.not, label %inner.loop.exit, label %inner.loop910 911inner.loop.exit:912 %outer.iv.next = add i64 %outer.iv, 1913 %arrayidx.us = getelementptr inbounds i8, ptr %str, i64 %outer.iv.next914 %9 = load i8, ptr %arrayidx.us, align 1915 %cmp.not.us = icmp eq i8 %9, 0916 br i1 %cmp.not.us, label %while.end, label %outer.loop917 918while.end:919 ret void920}921 922 923; Equivalent example in C:924; void decreasing_inner_iv(int32_t *dst, int32_t *src, int stride1, int stride2, int m, int n) {925; for (int i = 0; i < m; i++) {926; for (int j = n; j >= 0; j--) {927; dst[(i * stride1) + j] += src[(i * stride2) + j];928; }929; }930; }931; Inner IV is decreasing, but this isn't a problem and we can still expand the932; runtime checks correctly to cover the whole loop.933 934; DEBUG-LABEL: 'decreasing_inner_iv'935; DEBUG: LAA: Found an analyzable loop: inner.loop936; DEBUG: LAA: Adding RT check for range:937; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting938; DEBUG-NEXT: LAA: ... but need to check stride is positive: (4 * (sext i32 %stride1 to i64))<nsw>939; DEBUG-NEXT: Start: %dst End: (4 + (4 * (zext i32 %n to i64))<nuw><nsw> + (4 * (sext i32 %stride1 to i64) * (-1 + (zext i32 %m to i64))<nsw>) + %dst)940; DEBUG-NEXT: LAA: Adding RT check for range:941; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting942; DEBUG-NEXT: LAA: ... but need to check stride is positive: (4 * (sext i32 %stride2 to i64))<nsw>943; DEBUG-NEXT: Start: %src End: (4 + (4 * (zext i32 %n to i64))<nuw><nsw> + (4 * (sext i32 %stride2 to i64) * (-1 + (zext i32 %m to i64))<nsw>) + %src)944 945define void @decreasing_inner_iv(ptr nocapture noundef %dst, ptr nocapture noundef readonly %src, i32 noundef %stride1, i32 noundef %stride2, i32 noundef %m, i32 noundef %n) {946; CHECK-LABEL: define void @decreasing_inner_iv947; CHECK-SAME: (ptr noundef captures(none) [[DST:%.*]], ptr noundef readonly captures(none) [[SRC:%.*]], i32 noundef [[STRIDE1:%.*]], i32 noundef [[STRIDE2:%.*]], i32 noundef [[M:%.*]], i32 noundef [[N:%.*]]) {948; CHECK-NEXT: entry:949; CHECK-NEXT: [[CMP20:%.*]] = icmp sgt i32 [[M]], 0950; CHECK-NEXT: [[CMP218:%.*]] = icmp sgt i32 [[N]], -1951; CHECK-NEXT: [[OR_COND:%.*]] = and i1 [[CMP20]], [[CMP218]]952; CHECK-NEXT: br i1 [[OR_COND]], label [[OUTER_LOOP_PRE:%.*]], label [[EXIT:%.*]]953; CHECK: outer.loop.pre:954; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[N]] to i64955; CHECK-NEXT: [[TMP1:%.*]] = sext i32 [[STRIDE2]] to i64956; CHECK-NEXT: [[TMP2:%.*]] = sext i32 [[STRIDE1]] to i64957; CHECK-NEXT: [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[M]] to i64958; CHECK-NEXT: [[TMP3:%.*]] = add nsw i64 [[WIDE_TRIP_COUNT]], -1959; CHECK-NEXT: [[TMP4:%.*]] = mul i64 [[TMP3]], [[TMP2]]960; CHECK-NEXT: [[TMP5:%.*]] = shl i64 [[TMP4]], 2961; CHECK-NEXT: [[TMP6:%.*]] = shl nuw nsw i64 [[TMP0]], 2962; CHECK-NEXT: [[TMP7:%.*]] = add i64 [[TMP5]], [[TMP6]]963; CHECK-NEXT: [[TMP8:%.*]] = add i64 [[TMP7]], 4964; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP8]]965; CHECK-NEXT: [[TMP9:%.*]] = shl nsw i64 [[TMP2]], 2966; CHECK-NEXT: [[TMP10:%.*]] = mul i64 [[TMP3]], [[TMP1]]967; CHECK-NEXT: [[TMP11:%.*]] = shl i64 [[TMP10]], 2968; CHECK-NEXT: [[TMP12:%.*]] = add i64 [[TMP11]], [[TMP6]]969; CHECK-NEXT: [[TMP13:%.*]] = add i64 [[TMP12]], 4970; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP13]]971; CHECK-NEXT: [[TMP14:%.*]] = shl nsw i64 [[TMP1]], 2972; CHECK-NEXT: [[TMP15:%.*]] = add nuw nsw i64 [[TMP0]], 1973; CHECK-NEXT: br label [[OUTER_LOOP:%.*]]974; CHECK: outer.loop:975; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, [[OUTER_LOOP_PRE]] ], [ [[OUTER_IV_NEXT:%.*]], [[INNER_LOOP_EXIT:%.*]] ]976; CHECK-NEXT: [[TMP16:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP1]]977; CHECK-NEXT: [[TMP17:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP2]]978; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[TMP15]], 4979; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]]980; CHECK: vector.memcheck:981; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP1]]982; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP]]983; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]984; CHECK-NEXT: [[STRIDE_CHECK:%.*]] = icmp slt i64 [[TMP9]], 0985; CHECK-NEXT: [[TMP18:%.*]] = or i1 [[FOUND_CONFLICT]], [[STRIDE_CHECK]]986; CHECK-NEXT: [[STRIDE_CHECK2:%.*]] = icmp slt i64 [[TMP14]], 0987; CHECK-NEXT: [[TMP19:%.*]] = or i1 [[TMP18]], [[STRIDE_CHECK2]]988; CHECK-NEXT: br i1 [[TMP19]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]989; CHECK: vector.ph:990; CHECK-NEXT: [[N_MOD_VF:%.*]] = urem i64 [[TMP15]], 4991; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[TMP15]], [[N_MOD_VF]]992; CHECK-NEXT: [[TMP20:%.*]] = sub i64 [[TMP0]], [[N_VEC]]993; CHECK-NEXT: br label [[VECTOR_BODY:%.*]]994; CHECK: vector.body:995; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]996; CHECK-NEXT: [[OFFSET_IDX:%.*]] = sub i64 [[TMP0]], [[INDEX]]997; CHECK-NEXT: [[TMP21:%.*]] = add nsw i64 [[OFFSET_IDX]], [[TMP16]]998; CHECK-NEXT: [[TMP22:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP21]]999; CHECK-NEXT: [[TMP23:%.*]] = getelementptr inbounds i32, ptr [[TMP22]], i64 01000; CHECK-NEXT: [[TMP24:%.*]] = getelementptr inbounds i32, ptr [[TMP23]], i64 -31001; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP24]], align 4, !alias.scope [[META46:![0-9]+]]1002; CHECK-NEXT: [[REVERSE:%.*]] = shufflevector <4 x i32> [[WIDE_LOAD]], <4 x i32> poison, <4 x i32> <i32 3, i32 2, i32 1, i32 0>1003; CHECK-NEXT: [[TMP25:%.*]] = add nsw i64 [[OFFSET_IDX]], [[TMP17]]1004; CHECK-NEXT: [[TMP26:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP25]]1005; CHECK-NEXT: [[TMP27:%.*]] = getelementptr inbounds i32, ptr [[TMP26]], i64 01006; CHECK-NEXT: [[TMP28:%.*]] = getelementptr inbounds i32, ptr [[TMP27]], i64 -31007; CHECK-NEXT: [[WIDE_LOAD3:%.*]] = load <4 x i32>, ptr [[TMP28]], align 4, !alias.scope [[META49:![0-9]+]], !noalias [[META46]]1008; CHECK-NEXT: [[REVERSE4:%.*]] = shufflevector <4 x i32> [[WIDE_LOAD3]], <4 x i32> poison, <4 x i32> <i32 3, i32 2, i32 1, i32 0>1009; CHECK-NEXT: [[TMP29:%.*]] = add nsw <4 x i32> [[REVERSE4]], [[REVERSE]]1010; CHECK-NEXT: [[REVERSE5:%.*]] = shufflevector <4 x i32> [[TMP29]], <4 x i32> poison, <4 x i32> <i32 3, i32 2, i32 1, i32 0>1011; CHECK-NEXT: store <4 x i32> [[REVERSE5]], ptr [[TMP28]], align 4, !alias.scope [[META49]], !noalias [[META46]]1012; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 41013; CHECK-NEXT: [[TMP30:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]1014; CHECK-NEXT: br i1 [[TMP30]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP51:![0-9]+]]1015; CHECK: middle.block:1016; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[TMP15]], [[N_VEC]]1017; CHECK-NEXT: br i1 [[CMP_N]], label [[INNER_LOOP_EXIT]], label [[SCALAR_PH]]1018; CHECK: scalar.ph:1019; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[TMP20]], [[MIDDLE_BLOCK]] ], [ [[TMP0]], [[OUTER_LOOP]] ], [ [[TMP0]], [[VECTOR_MEMCHECK]] ]1020; CHECK-NEXT: br label [[INNER_LOOP:%.*]]1021; CHECK: inner.loop:1022; CHECK-NEXT: [[INNER_IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[INNER_IV_NEXT:%.*]], [[INNER_LOOP]] ]1023; CHECK-NEXT: [[TMP31:%.*]] = add nsw i64 [[INNER_IV]], [[TMP16]]1024; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP31]]1025; CHECK-NEXT: [[TMP32:%.*]] = load i32, ptr [[ARRAYIDX_US]], align 41026; CHECK-NEXT: [[TMP33:%.*]] = add nsw i64 [[INNER_IV]], [[TMP17]]1027; CHECK-NEXT: [[ARRAYIDX8_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP33]]1028; CHECK-NEXT: [[TMP34:%.*]] = load i32, ptr [[ARRAYIDX8_US]], align 41029; CHECK-NEXT: [[ADD9_US:%.*]] = add nsw i32 [[TMP34]], [[TMP32]]1030; CHECK-NEXT: store i32 [[ADD9_US]], ptr [[ARRAYIDX8_US]], align 41031; CHECK-NEXT: [[INNER_IV_NEXT]] = add nsw i64 [[INNER_IV]], -11032; CHECK-NEXT: [[CMP2_US:%.*]] = icmp sgt i64 [[INNER_IV]], 01033; CHECK-NEXT: br i1 [[CMP2_US]], label [[INNER_LOOP]], label [[INNER_LOOP_EXIT]], !llvm.loop [[LOOP52:![0-9]+]]1034; CHECK: inner.loop.exit:1035; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nuw nsw i64 [[OUTER_IV]], 11036; CHECK-NEXT: [[EXITCOND_NOT:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[WIDE_TRIP_COUNT]]1037; CHECK-NEXT: br i1 [[EXITCOND_NOT]], label [[OUTER_LOOP_EXIT:%.*]], label [[OUTER_LOOP]]1038; CHECK: outer.loop.exit:1039; CHECK-NEXT: br label [[EXIT]]1040; CHECK: exit:1041; CHECK-NEXT: ret void1042;1043entry:1044 %cmp20 = icmp sgt i32 %m, 01045 %cmp218 = icmp sgt i32 %n, -11046 %or.cond = and i1 %cmp20, %cmp2181047 br i1 %or.cond, label %outer.loop.pre, label %exit1048 1049outer.loop.pre:1050 %0 = zext i32 %n to i641051 %1 = sext i32 %stride2 to i641052 %2 = sext i32 %stride1 to i641053 %wide.trip.count = zext i32 %m to i641054 br label %outer.loop1055 1056outer.loop:1057 %outer.iv = phi i64 [ 0, %outer.loop.pre ], [ %outer.iv.next, %inner.loop.exit ]1058 %3 = mul nsw i64 %outer.iv, %11059 %4 = mul nsw i64 %outer.iv, %21060 br label %inner.loop1061 1062inner.loop:1063 %inner.iv = phi i64 [ %0, %outer.loop ], [ %inner.iv.next, %inner.loop ]1064 %5 = add nsw i64 %inner.iv, %31065 %arrayidx.us = getelementptr inbounds i32, ptr %src, i64 %51066 %6 = load i32, ptr %arrayidx.us, align 41067 %7 = add nsw i64 %inner.iv, %41068 %arrayidx8.us = getelementptr inbounds i32, ptr %dst, i64 %71069 %8 = load i32, ptr %arrayidx8.us, align 41070 %add9.us = add nsw i32 %8, %61071 store i32 %add9.us, ptr %arrayidx8.us, align 41072 %inner.iv.next = add nsw i64 %inner.iv, -11073 %cmp2.us = icmp sgt i64 %inner.iv, 01074 br i1 %cmp2.us, label %inner.loop, label %inner.loop.exit1075 1076inner.loop.exit:1077 %outer.iv.next = add nuw nsw i64 %outer.iv, 11078 %exitcond.not = icmp eq i64 %outer.iv.next, %wide.trip.count1079 br i1 %exitcond.not, label %outer.loop.exit, label %outer.loop1080 1081outer.loop.exit:1082 br label %exit1083 1084exit:1085 ret void1086}1087 1088 1089; Equivalent example in C:1090; void decreasing_outer_iv(int32_t *dst, int32_t *src, int stride1, int stride2, int m, int n) {1091; for (int i = m - 1; i >= 0; i--) {1092; for (int j = 0; j <= n; j++) {1093; dst[(i * stride1) + j] += src[(i * stride2) + j];1094; }1095; }1096; }1097; Outer IV is decreasing, but the direction of memory accesses also depends1098; upon the signedness of stride1.1099 1100; DEBUG-LABEL: 'decreasing_outer_iv'1101; DEBUG: LAA: Found an analyzable loop: inner.loop1102; DEBUG: LAA: Adding RT check for range:1103; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting1104; DEBUG-NEXT: LAA: ... but need to check stride is positive: (-4 * (sext i32 %stride1 to i64))<nsw>1105; DEBUG-NEXT: Start: ((4 * (zext i32 %m to i64) * (sext i32 %stride1 to i64)) + %dst) End: ((4 * (zext i32 (1 + %n) to i64))<nuw><nsw> + (4 * (sext i32 %stride1 to i64))<nsw> + %dst)1106; DEBUG-NEXT: LAA: Adding RT check for range:1107; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting1108; DEBUG-NEXT: LAA: ... but need to check stride is positive: (-4 * (sext i32 %stride2 to i64))<nsw>1109; DEBUG-NEXT: Start: ((4 * (zext i32 %m to i64) * (sext i32 %stride2 to i64)) + %src) End: ((4 * (zext i32 (1 + %n) to i64))<nuw><nsw> + (4 * (sext i32 %stride2 to i64))<nsw> + %src)1110 1111define void @decreasing_outer_iv(ptr nocapture noundef %dst, ptr nocapture noundef readonly %src, i32 noundef %stride1, i32 noundef %stride2, i32 noundef %m, i32 noundef %n) {1112; CHECK-LABEL: define void @decreasing_outer_iv1113; CHECK-SAME: (ptr noundef captures(none) [[DST:%.*]], ptr noundef readonly captures(none) [[SRC:%.*]], i32 noundef [[STRIDE1:%.*]], i32 noundef [[STRIDE2:%.*]], i32 noundef [[M:%.*]], i32 noundef [[N:%.*]]) {1114; CHECK-NEXT: entry:1115; CHECK-NEXT: [[CMP21:%.*]] = icmp slt i32 [[M]], 11116; CHECK-NEXT: [[CMP2_NOT18:%.*]] = icmp slt i32 [[N]], 01117; CHECK-NEXT: [[OR_COND:%.*]] = or i1 [[CMP21]], [[CMP2_NOT18]]1118; CHECK-NEXT: br i1 [[OR_COND]], label [[EXIT:%.*]], label [[OUTER_LOOP_PRE:%.*]]1119; CHECK: outer.loop.pre:1120; CHECK-NEXT: [[TMP0:%.*]] = add nuw i32 [[N]], 11121; CHECK-NEXT: [[TMP1:%.*]] = zext i32 [[M]] to i641122; CHECK-NEXT: [[TMP2:%.*]] = sext i32 [[STRIDE1]] to i641123; CHECK-NEXT: [[TMP3:%.*]] = sext i32 [[STRIDE2]] to i641124; CHECK-NEXT: [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[TMP0]] to i641125; CHECK-NEXT: [[TMP4:%.*]] = mul i64 [[TMP2]], [[TMP1]]1126; CHECK-NEXT: [[TMP5:%.*]] = shl i64 [[TMP4]], 21127; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP5]]1128; CHECK-NEXT: [[TMP6:%.*]] = shl nsw i64 [[TMP2]], 21129; CHECK-NEXT: [[TMP7:%.*]] = shl nuw nsw i64 [[WIDE_TRIP_COUNT]], 21130; CHECK-NEXT: [[TMP8:%.*]] = add i64 [[TMP6]], [[TMP7]]1131; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP8]]1132; CHECK-NEXT: [[TMP9:%.*]] = mul nsw i64 [[TMP2]], -41133; CHECK-NEXT: [[TMP10:%.*]] = mul i64 [[TMP3]], [[TMP1]]1134; CHECK-NEXT: [[TMP11:%.*]] = shl i64 [[TMP10]], 21135; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP11]]1136; CHECK-NEXT: [[TMP12:%.*]] = shl nsw i64 [[TMP3]], 21137; CHECK-NEXT: [[TMP13:%.*]] = add i64 [[TMP12]], [[TMP7]]1138; CHECK-NEXT: [[SCEVGEP3:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP13]]1139; CHECK-NEXT: [[TMP14:%.*]] = mul nsw i64 [[TMP3]], -41140; CHECK-NEXT: br label [[OUTER_LOOP:%.*]]1141; CHECK: outer.loop:1142; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ [[TMP1]], [[OUTER_LOOP_PRE]] ], [ [[OUTER_IV_NEXT:%.*]], [[INNER_LOOP_EXIT:%.*]] ]1143; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nsw i64 [[OUTER_IV]], -11144; CHECK-NEXT: [[TMP15:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP3]]1145; CHECK-NEXT: [[TMP16:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP2]]1146; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_TRIP_COUNT]], 41147; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]]1148; CHECK: vector.memcheck:1149; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[SCEVGEP]], [[SCEVGEP3]]1150; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SCEVGEP2]], [[SCEVGEP1]]1151; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]1152; CHECK-NEXT: [[STRIDE_CHECK:%.*]] = icmp slt i64 [[TMP9]], 01153; CHECK-NEXT: [[TMP17:%.*]] = or i1 [[FOUND_CONFLICT]], [[STRIDE_CHECK]]1154; CHECK-NEXT: [[STRIDE_CHECK4:%.*]] = icmp slt i64 [[TMP14]], 01155; CHECK-NEXT: [[TMP18:%.*]] = or i1 [[TMP17]], [[STRIDE_CHECK4]]1156; CHECK-NEXT: br i1 [[TMP18]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]1157; CHECK: vector.ph:1158; CHECK-NEXT: [[N_MOD_VF:%.*]] = urem i64 [[WIDE_TRIP_COUNT]], 41159; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[WIDE_TRIP_COUNT]], [[N_MOD_VF]]1160; CHECK-NEXT: br label [[VECTOR_BODY:%.*]]1161; CHECK: vector.body:1162; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]1163; CHECK-NEXT: [[TMP19:%.*]] = add nsw i64 [[INDEX]], [[TMP15]]1164; CHECK-NEXT: [[TMP20:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP19]]1165; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP20]], align 4, !alias.scope [[META53:![0-9]+]]1166; CHECK-NEXT: [[TMP21:%.*]] = add nsw i64 [[INDEX]], [[TMP16]]1167; CHECK-NEXT: [[TMP22:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP21]]1168; CHECK-NEXT: [[WIDE_LOAD5:%.*]] = load <4 x i32>, ptr [[TMP22]], align 4, !alias.scope [[META56:![0-9]+]], !noalias [[META53]]1169; CHECK-NEXT: [[TMP23:%.*]] = add nsw <4 x i32> [[WIDE_LOAD5]], [[WIDE_LOAD]]1170; CHECK-NEXT: store <4 x i32> [[TMP23]], ptr [[TMP22]], align 4, !alias.scope [[META56]], !noalias [[META53]]1171; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 41172; CHECK-NEXT: [[TMP24:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]1173; CHECK-NEXT: br i1 [[TMP24]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP58:![0-9]+]]1174; CHECK: middle.block:1175; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_TRIP_COUNT]], [[N_VEC]]1176; CHECK-NEXT: br i1 [[CMP_N]], label [[INNER_LOOP_EXIT]], label [[SCALAR_PH]]1177; CHECK: scalar.ph:1178; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[OUTER_LOOP]] ], [ 0, [[VECTOR_MEMCHECK]] ]1179; CHECK-NEXT: br label [[INNER_LOOP:%.*]]1180; CHECK: inner.loop:1181; CHECK-NEXT: [[INNER_IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[INNER_IV_NEXT:%.*]], [[INNER_LOOP]] ]1182; CHECK-NEXT: [[TMP25:%.*]] = add nsw i64 [[INNER_IV]], [[TMP15]]1183; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP25]]1184; CHECK-NEXT: [[TMP26:%.*]] = load i32, ptr [[ARRAYIDX]], align 41185; CHECK-NEXT: [[TMP27:%.*]] = add nsw i64 [[INNER_IV]], [[TMP16]]1186; CHECK-NEXT: [[ARRAYIDX8:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP27]]1187; CHECK-NEXT: [[TMP28:%.*]] = load i32, ptr [[ARRAYIDX8]], align 41188; CHECK-NEXT: [[ADD9:%.*]] = add nsw i32 [[TMP28]], [[TMP26]]1189; CHECK-NEXT: store i32 [[ADD9]], ptr [[ARRAYIDX8]], align 41190; CHECK-NEXT: [[INNER_IV_NEXT]] = add nuw nsw i64 [[INNER_IV]], 11191; CHECK-NEXT: [[EXITCOND_NOT:%.*]] = icmp eq i64 [[INNER_IV_NEXT]], [[WIDE_TRIP_COUNT]]1192; CHECK-NEXT: br i1 [[EXITCOND_NOT]], label [[INNER_LOOP_EXIT]], label [[INNER_LOOP]], !llvm.loop [[LOOP59:![0-9]+]]1193; CHECK: inner.loop.exit:1194; CHECK-NEXT: [[CMP:%.*]] = icmp sgt i64 [[OUTER_IV]], 11195; CHECK-NEXT: br i1 [[CMP]], label [[OUTER_LOOP]], label [[OUTER_LOOP_EXIT:%.*]]1196; CHECK: outer.loop.exit:1197; CHECK-NEXT: br label [[EXIT]]1198; CHECK: exit:1199; CHECK-NEXT: ret void1200;1201entry:1202 %cmp21 = icmp slt i32 %m, 11203 %cmp2.not18 = icmp slt i32 %n, 01204 %or.cond = or i1 %cmp21, %cmp2.not181205 br i1 %or.cond, label %exit, label %outer.loop.pre1206 1207outer.loop.pre:1208 %0 = add nuw i32 %n, 11209 %1 = zext i32 %m to i641210 %2 = sext i32 %stride1 to i641211 %3 = sext i32 %stride2 to i641212 %wide.trip.count = zext i32 %0 to i641213 br label %outer.loop1214 1215outer.loop:1216 %outer.iv = phi i64 [ %1, %outer.loop.pre ], [ %outer.iv.next, %inner.loop.exit ]1217 %outer.iv.next = add nsw i64 %outer.iv, -11218 %4 = mul nsw i64 %outer.iv, %31219 %5 = mul nsw i64 %outer.iv, %21220 br label %inner.loop1221 1222inner.loop:1223 %inner.iv = phi i64 [ 0, %outer.loop ], [ %inner.iv.next, %inner.loop ]1224 %6 = add nsw i64 %inner.iv, %41225 %arrayidx = getelementptr inbounds i32, ptr %src, i64 %61226 %7 = load i32, ptr %arrayidx, align 41227 %8 = add nsw i64 %inner.iv, %51228 %arrayidx8 = getelementptr inbounds i32, ptr %dst, i64 %81229 %9 = load i32, ptr %arrayidx8, align 41230 %add9 = add nsw i32 %9, %71231 store i32 %add9, ptr %arrayidx8, align 41232 %inner.iv.next = add nuw nsw i64 %inner.iv, 11233 %exitcond.not = icmp eq i64 %inner.iv.next, %wide.trip.count1234 br i1 %exitcond.not, label %inner.loop.exit, label %inner.loop1235 1236inner.loop.exit:1237 %cmp = icmp sgt i64 %outer.iv, 11238 br i1 %cmp, label %outer.loop, label %outer.loop.exit1239 1240outer.loop.exit:1241 br label %exit1242 1243exit:1244 ret void1245}1246 1247 1248; Equivalent example in C:1249; void foo(int32_t *dst, int32_t *src, int stride1, int stride2, int m, int n) {1250; for (int i = 0; i < m; i++) {1251; for (int j = 0; j < n; j++) {1252; dst[(i * (n + 1)) + (j * stride1)] += src[(i * n) + (j * stride2)];1253; }1254; }1255; }1256 1257 1258; DEBUG-LABEL: 'unknown_inner_stride'1259; DEBUG: LAA: Found an analyzable loop: inner.loop1260; DEBUG: LAA: Adding RT check for range:1261; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting1262; DEBUG-NEXT: Start: %dst End: ((4 * (zext i32 %n to i64))<nuw><nsw> + (4 * (zext i32 (1 + %n) to i64) * (-1 + (zext i32 %m to i64))<nsw>) + %dst)1263; DEBUG-NEXT: LAA: Adding RT check for range:1264; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting1265; DEBUG-NEXT: Start: %src End: ((4 * (zext i32 %m to i64) * (zext i32 %n to i64)) + %src)1266 1267define void @unknown_inner_stride(ptr nocapture noundef %dst, ptr nocapture noundef readonly %src, i32 noundef %stride1, i32 noundef %stride2, i32 noundef %m, i32 noundef %n) {1268; CHECK-LABEL: define void @unknown_inner_stride1269; CHECK-SAME: (ptr noundef captures(none) [[DST:%.*]], ptr noundef readonly captures(none) [[SRC:%.*]], i32 noundef [[STRIDE1:%.*]], i32 noundef [[STRIDE2:%.*]], i32 noundef [[M:%.*]], i32 noundef [[N:%.*]]) {1270; CHECK-NEXT: entry:1271; CHECK-NEXT: [[CMP26:%.*]] = icmp sgt i32 [[M]], 01272; CHECK-NEXT: [[CMP224:%.*]] = icmp sgt i32 [[N]], 01273; CHECK-NEXT: [[OR_COND:%.*]] = and i1 [[CMP26]], [[CMP224]]1274; CHECK-NEXT: br i1 [[OR_COND]], label [[OUTER_LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]1275; CHECK: outer.loop.preheader:1276; CHECK-NEXT: [[ADD6:%.*]] = add nuw nsw i32 [[N]], 11277; CHECK-NEXT: [[TMP0:%.*]] = sext i32 [[STRIDE2]] to i641278; CHECK-NEXT: [[TMP1:%.*]] = sext i32 [[STRIDE1]] to i641279; CHECK-NEXT: [[TMP2:%.*]] = zext i32 [[N]] to i641280; CHECK-NEXT: [[TMP3:%.*]] = zext i32 [[ADD6]] to i641281; CHECK-NEXT: [[WIDE_TRIP_COUNT39:%.*]] = zext i32 [[M]] to i641282; CHECK-NEXT: [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[N]] to i641283; CHECK-NEXT: [[TMP4:%.*]] = add nsw i64 [[WIDE_TRIP_COUNT39]], -11284; CHECK-NEXT: [[TMP5:%.*]] = mul i64 [[TMP4]], [[TMP3]]1285; CHECK-NEXT: [[TMP6:%.*]] = shl i64 [[TMP5]], 21286; CHECK-NEXT: [[TMP7:%.*]] = shl nuw nsw i64 [[WIDE_TRIP_COUNT]], 21287; CHECK-NEXT: [[TMP8:%.*]] = add i64 [[TMP6]], [[TMP7]]1288; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP8]]1289; CHECK-NEXT: [[TMP9:%.*]] = mul i64 [[WIDE_TRIP_COUNT]], [[WIDE_TRIP_COUNT39]]1290; CHECK-NEXT: [[TMP10:%.*]] = shl i64 [[TMP9]], 21291; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP10]]1292; CHECK-NEXT: br label [[OUTER_LOOP:%.*]]1293; CHECK: outer.loop:1294; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, [[OUTER_LOOP_PREHEADER]] ], [ [[OUTER_IV_NEXT:%.*]], [[INNER_LOOP_EXIT:%.*]] ]1295; CHECK-NEXT: [[TMP11:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP2]]1296; CHECK-NEXT: [[TMP12:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP3]]1297; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_TRIP_COUNT]], 41298; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_SCEVCHECK:%.*]]1299; CHECK: vector.scevcheck:1300; CHECK-NEXT: [[IDENT_CHECK:%.*]] = icmp ne i32 [[STRIDE1]], 11301; CHECK-NEXT: [[IDENT_CHECK1:%.*]] = icmp ne i32 [[STRIDE2]], 11302; CHECK-NEXT: [[TMP13:%.*]] = or i1 [[IDENT_CHECK]], [[IDENT_CHECK1]]1303; CHECK-NEXT: br i1 [[TMP13]], label [[SCALAR_PH]], label [[VECTOR_MEMCHECK:%.*]]1304; CHECK: vector.memcheck:1305; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP2]]1306; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP]]1307; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]1308; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]1309; CHECK: vector.ph:1310; CHECK-NEXT: [[N_MOD_VF:%.*]] = urem i64 [[WIDE_TRIP_COUNT]], 41311; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[WIDE_TRIP_COUNT]], [[N_MOD_VF]]1312; CHECK-NEXT: br label [[VECTOR_BODY:%.*]]1313; CHECK: vector.body:1314; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]1315; CHECK-NEXT: [[TMP14:%.*]] = add nsw i64 [[INDEX]], [[TMP11]]1316; CHECK-NEXT: [[TMP15:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP14]]1317; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP15]], align 4, !alias.scope [[META60:![0-9]+]]1318; CHECK-NEXT: [[TMP16:%.*]] = add nsw i64 [[INDEX]], [[TMP12]]1319; CHECK-NEXT: [[TMP17:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP16]]1320; CHECK-NEXT: [[WIDE_LOAD3:%.*]] = load <4 x i32>, ptr [[TMP17]], align 4, !alias.scope [[META63:![0-9]+]], !noalias [[META60]]1321; CHECK-NEXT: [[TMP18:%.*]] = add nsw <4 x i32> [[WIDE_LOAD3]], [[WIDE_LOAD]]1322; CHECK-NEXT: store <4 x i32> [[TMP18]], ptr [[TMP17]], align 4, !alias.scope [[META63]], !noalias [[META60]]1323; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 41324; CHECK-NEXT: [[TMP19:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]1325; CHECK-NEXT: br i1 [[TMP19]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP65:![0-9]+]]1326; CHECK: middle.block:1327; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_TRIP_COUNT]], [[N_VEC]]1328; CHECK-NEXT: br i1 [[CMP_N]], label [[INNER_LOOP_EXIT]], label [[SCALAR_PH]]1329; CHECK: scalar.ph:1330; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[OUTER_LOOP]] ], [ 0, [[VECTOR_SCEVCHECK]] ], [ 0, [[VECTOR_MEMCHECK]] ]1331; CHECK-NEXT: br label [[INNER_LOOP:%.*]]1332; CHECK: inner.loop:1333; CHECK-NEXT: [[INNER_IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[INNER_IV_NEXT:%.*]], [[INNER_LOOP]] ]1334; CHECK-NEXT: [[TMP20:%.*]] = mul nsw i64 [[INNER_IV]], [[TMP0]]1335; CHECK-NEXT: [[TMP21:%.*]] = add nsw i64 [[TMP20]], [[TMP11]]1336; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP21]]1337; CHECK-NEXT: [[TMP22:%.*]] = load i32, ptr [[ARRAYIDX_US]], align 41338; CHECK-NEXT: [[TMP23:%.*]] = mul nsw i64 [[INNER_IV]], [[TMP1]]1339; CHECK-NEXT: [[TMP24:%.*]] = add nsw i64 [[TMP23]], [[TMP12]]1340; CHECK-NEXT: [[ARRAYIDX11_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP24]]1341; CHECK-NEXT: [[TMP25:%.*]] = load i32, ptr [[ARRAYIDX11_US]], align 41342; CHECK-NEXT: [[ADD12_US:%.*]] = add nsw i32 [[TMP25]], [[TMP22]]1343; CHECK-NEXT: store i32 [[ADD12_US]], ptr [[ARRAYIDX11_US]], align 41344; CHECK-NEXT: [[INNER_IV_NEXT]] = add nuw nsw i64 [[INNER_IV]], 11345; CHECK-NEXT: [[EXITCOND_NOT:%.*]] = icmp eq i64 [[INNER_IV_NEXT]], [[WIDE_TRIP_COUNT]]1346; CHECK-NEXT: br i1 [[EXITCOND_NOT]], label [[INNER_LOOP_EXIT]], label [[INNER_LOOP]], !llvm.loop [[LOOP66:![0-9]+]]1347; CHECK: inner.loop.exit:1348; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nuw nsw i64 [[OUTER_IV]], 11349; CHECK-NEXT: [[EXITCOND40_NOT:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[WIDE_TRIP_COUNT39]]1350; CHECK-NEXT: br i1 [[EXITCOND40_NOT]], label [[EXIT_LOOPEXIT:%.*]], label [[OUTER_LOOP]]1351; CHECK: exit.loopexit:1352; CHECK-NEXT: br label [[EXIT]]1353; CHECK: exit:1354; CHECK-NEXT: ret void1355;1356entry:1357 %cmp26 = icmp sgt i32 %m, 01358 %cmp224 = icmp sgt i32 %n, 01359 %or.cond = and i1 %cmp26, %cmp2241360 br i1 %or.cond, label %outer.loop.preheader, label %exit1361 1362outer.loop.preheader:1363 %add6 = add nuw nsw i32 %n, 11364 %0 = sext i32 %stride2 to i641365 %1 = sext i32 %stride1 to i641366 %2 = zext i32 %n to i641367 %3 = zext i32 %add6 to i641368 %wide.trip.count39 = zext i32 %m to i641369 %wide.trip.count = zext i32 %n to i641370 br label %outer.loop1371 1372outer.loop:1373 %outer.iv = phi i64 [ 0, %outer.loop.preheader ], [ %outer.iv.next, %inner.loop.exit ]1374 %4 = mul nsw i64 %outer.iv, %21375 %5 = mul nsw i64 %outer.iv, %31376 br label %inner.loop1377 1378inner.loop:1379 %inner.iv = phi i64 [ 0, %outer.loop ], [ %inner.iv.next, %inner.loop ]1380 %6 = mul nsw i64 %inner.iv, %01381 %7 = add nsw i64 %6, %41382 %arrayidx.us = getelementptr inbounds i32, ptr %src, i64 %71383 %8 = load i32, ptr %arrayidx.us, align 41384 %9 = mul nsw i64 %inner.iv, %11385 %10 = add nsw i64 %9, %51386 %arrayidx11.us = getelementptr inbounds i32, ptr %dst, i64 %101387 %11 = load i32, ptr %arrayidx11.us, align 41388 %add12.us = add nsw i32 %11, %81389 store i32 %add12.us, ptr %arrayidx11.us, align 41390 %inner.iv.next = add nuw nsw i64 %inner.iv, 11391 %exitcond.not = icmp eq i64 %inner.iv.next, %wide.trip.count1392 br i1 %exitcond.not, label %inner.loop.exit, label %inner.loop1393 1394inner.loop.exit:1395 %outer.iv.next = add nuw nsw i64 %outer.iv, 11396 %exitcond40.not = icmp eq i64 %outer.iv.next, %wide.trip.count391397 br i1 %exitcond40.not, label %exit, label %outer.loop1398 1399exit:1400 ret void1401}1402 1403 1404; Test case where the AddRec for the pointers in the inner loop have the AddRec1405; of the outer loop as start value. It is sufficient to subtract the start1406; values (%dst, %src) of the outer AddRecs.1407define void @nested_loop_start_of_inner_ptr_addrec_is_same_outer_addrec(ptr nocapture noundef %dst, ptr nocapture noundef readonly %src, i64 noundef %m, i64 noundef %n) {1408; CHECK-LABEL: define void @nested_loop_start_of_inner_ptr_addrec_is_same_outer_addrec1409; CHECK-SAME: (ptr noundef captures(none) [[DST:%.*]], ptr noundef readonly captures(none) [[SRC:%.*]], i64 noundef [[M:%.*]], i64 noundef [[N:%.*]]) {1410; CHECK-NEXT: entry:1411; CHECK-NEXT: [[SRC2:%.*]] = ptrtoint ptr [[SRC]] to i641412; CHECK-NEXT: [[DST1:%.*]] = ptrtoint ptr [[DST]] to i641413; CHECK-NEXT: [[TMP0:%.*]] = sub i64 [[DST1]], [[SRC2]]1414; CHECK-NEXT: br label [[OUTER_LOOP:%.*]]1415; CHECK: outer.loop:1416; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_IV_NEXT:%.*]], [[INNER_EXIT:%.*]] ]1417; CHECK-NEXT: [[MUL:%.*]] = mul nsw i64 [[OUTER_IV]], [[N]]1418; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[N]], 41419; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_MEMCHECK:%.*]]1420; CHECK: vector.memcheck:1421; CHECK-NEXT: [[DIFF_CHECK:%.*]] = icmp ult i64 [[TMP0]], 161422; CHECK-NEXT: br i1 [[DIFF_CHECK]], label [[SCALAR_PH]], label [[VECTOR_PH:%.*]]1423; CHECK: vector.ph:1424; CHECK-NEXT: [[N_MOD_VF:%.*]] = urem i64 [[N]], 41425; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[N]], [[N_MOD_VF]]1426; CHECK-NEXT: br label [[VECTOR_BODY:%.*]]1427; CHECK: vector.body:1428; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]1429; CHECK-NEXT: [[TMP1:%.*]] = add nuw nsw i64 [[INDEX]], [[MUL]]1430; CHECK-NEXT: [[TMP2:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP1]]1431; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP2]], align 41432; CHECK-NEXT: [[TMP3:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP1]]1433; CHECK-NEXT: [[TMP4:%.*]] = add nsw <4 x i32> [[WIDE_LOAD]], splat (i32 10)1434; CHECK-NEXT: store <4 x i32> [[TMP4]], ptr [[TMP3]], align 41435; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 41436; CHECK-NEXT: [[TMP5:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]1437; CHECK-NEXT: br i1 [[TMP5]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP67:![0-9]+]]1438; CHECK: middle.block:1439; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[N]], [[N_VEC]]1440; CHECK-NEXT: br i1 [[CMP_N]], label [[INNER_EXIT]], label [[SCALAR_PH]]1441; CHECK: scalar.ph:1442; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[OUTER_LOOP]] ], [ 0, [[VECTOR_MEMCHECK]] ]1443; CHECK-NEXT: br label [[INNER_LOOP:%.*]]1444; CHECK: inner.loop:1445; CHECK-NEXT: [[IV_INNER:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_INNER_NEXT:%.*]], [[INNER_LOOP]] ]1446; CHECK-NEXT: [[IDX:%.*]] = add nuw nsw i64 [[IV_INNER]], [[MUL]]1447; CHECK-NEXT: [[GEP_SRC:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[IDX]]1448; CHECK-NEXT: [[L:%.*]] = load i32, ptr [[GEP_SRC]], align 41449; CHECK-NEXT: [[GEP_DST:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IDX]]1450; CHECK-NEXT: [[ADD:%.*]] = add nsw i32 [[L]], 101451; CHECK-NEXT: store i32 [[ADD]], ptr [[GEP_DST]], align 41452; CHECK-NEXT: [[IV_INNER_NEXT]] = add nuw nsw i64 [[IV_INNER]], 11453; CHECK-NEXT: [[INNER_EXIT_COND:%.*]] = icmp eq i64 [[IV_INNER_NEXT]], [[N]]1454; CHECK-NEXT: br i1 [[INNER_EXIT_COND]], label [[INNER_EXIT]], label [[INNER_LOOP]], !llvm.loop [[LOOP68:![0-9]+]]1455; CHECK: inner.exit:1456; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nuw nsw i64 [[OUTER_IV]], 11457; CHECK-NEXT: [[OUTER_EXIT_COND:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[M]]1458; CHECK-NEXT: br i1 [[OUTER_EXIT_COND]], label [[OUTER_EXIT:%.*]], label [[OUTER_LOOP]]1459; CHECK: outer.exit:1460; CHECK-NEXT: ret void1461;1462entry:1463 br label %outer.loop1464 1465outer.loop:1466 %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %inner.exit ]1467 %mul = mul nsw i64 %outer.iv, %n1468 br label %inner.loop1469 1470inner.loop:1471 %iv.inner = phi i64 [ 0, %outer.loop ], [ %iv.inner.next, %inner.loop ]1472 %idx = add nuw nsw i64 %iv.inner, %mul1473 %gep.src = getelementptr inbounds i32, ptr %src, i64 %idx1474 %l = load i32, ptr %gep.src, align 41475 %gep.dst = getelementptr inbounds i32, ptr %dst, i64 %idx1476 %add = add nsw i32 %l, 101477 store i32 %add, ptr %gep.dst, align 41478 %iv.inner.next = add nuw nsw i64 %iv.inner, 11479 %inner.exit.cond = icmp eq i64 %iv.inner.next, %n1480 br i1 %inner.exit.cond, label %inner.exit, label %inner.loop1481 1482inner.exit:1483 %outer.iv.next = add nuw nsw i64 %outer.iv, 11484 %outer.exit.cond = icmp eq i64 %outer.iv.next, %m1485 br i1 %outer.exit.cond, label %outer.exit, label %outer.loop1486 1487outer.exit:1488 ret void1489}1490 1491; The stride for the access in the inner loop is known to be non-negative via1492; loop guards.1493define void @stride_check_known_via_loop_guard(ptr %C, ptr %A, i32 %Acols) {1494; CHECK-LABEL: define void @stride_check_known_via_loop_guard1495; CHECK-SAME: (ptr [[C:%.*]], ptr [[A:%.*]], i32 [[ACOLS:%.*]]) {1496; CHECK-NEXT: entry:1497; CHECK-NEXT: [[PRE_C:%.*]] = icmp ugt i32 [[ACOLS]], 01498; CHECK-NEXT: br i1 [[PRE_C]], label [[EXIT:%.*]], label [[OUTER_HEADER_PREHEADER:%.*]]1499; CHECK: outer.header.preheader:1500; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[C]], i64 80001501; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[A]], i64 81502; CHECK-NEXT: br label [[OUTER_HEADER:%.*]]1503; CHECK: outer.header:1504; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ [[OUTER_IV_NEXT:%.*]], [[OUTER_LATCH:%.*]] ], [ 0, [[OUTER_HEADER_PREHEADER]] ]1505; CHECK-NEXT: [[MUL_US:%.*]] = mul i32 [[OUTER_IV]], [[ACOLS]]1506; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr double, ptr [[A]], i32 [[MUL_US]]1507; CHECK-NEXT: br label [[VECTOR_MEMCHECK:%.*]]1508; CHECK: vector.memcheck:1509; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[C]], [[SCEVGEP1]]1510; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[A]], [[SCEVGEP]]1511; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]1512; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]1513; CHECK: vector.ph:1514; CHECK-NEXT: [[TMP0:%.*]] = load double, ptr [[ARRAYIDX_US]], align 8, !alias.scope [[META69:![0-9]+]]1515; CHECK-NEXT: [[BROADCAST_SPLATINSERT:%.*]] = insertelement <4 x double> poison, double [[TMP0]], i64 01516; CHECK-NEXT: [[BROADCAST_SPLAT:%.*]] = shufflevector <4 x double> [[BROADCAST_SPLATINSERT]], <4 x double> poison, <4 x i32> zeroinitializer1517; CHECK-NEXT: br label [[VECTOR_BODY:%.*]]1518; CHECK: vector.body:1519; CHECK-NEXT: [[INDEX:%.*]] = phi i32 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]1520; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds double, ptr [[C]], i32 [[INDEX]]1521; CHECK-NEXT: store <4 x double> [[BROADCAST_SPLAT]], ptr [[TMP1]], align 8, !alias.scope [[META72:![0-9]+]], !noalias [[META69]]1522; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i32 [[INDEX]], 41523; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i32 [[INDEX_NEXT]], 10001524; CHECK-NEXT: br i1 [[TMP2]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP74:![0-9]+]]1525; CHECK: middle.block:1526; CHECK-NEXT: br label [[OUTER_LATCH]]1527; CHECK: scalar.ph:1528; CHECK-NEXT: br label [[INNER:%.*]]1529; CHECK: inner:1530; CHECK-NEXT: [[INNER_IV:%.*]] = phi i32 [ 0, [[SCALAR_PH]] ], [ [[INNER_IV_NEXT:%.*]], [[INNER]] ]1531; CHECK-NEXT: [[GEP_C:%.*]] = getelementptr inbounds double, ptr [[C]], i32 [[INNER_IV]]1532; CHECK-NEXT: [[L:%.*]] = load double, ptr [[ARRAYIDX_US]], align 81533; CHECK-NEXT: store double [[L]], ptr [[GEP_C]], align 81534; CHECK-NEXT: [[INNER_IV_NEXT]] = add i32 [[INNER_IV]], 11535; CHECK-NEXT: [[INNER_C:%.*]] = icmp eq i32 [[INNER_IV_NEXT]], 10001536; CHECK-NEXT: br i1 [[INNER_C]], label [[OUTER_LATCH]], label [[INNER]], !llvm.loop [[LOOP75:![0-9]+]]1537; CHECK: outer.latch:1538; CHECK-NEXT: [[OUTER_IV_NEXT]] = add i32 [[OUTER_IV]], 11539; CHECK-NEXT: [[OUTER_C:%.*]] = icmp ult i32 [[OUTER_IV]], 1281540; CHECK-NEXT: br i1 [[OUTER_C]], label [[EXIT_LOOPEXIT:%.*]], label [[OUTER_HEADER]]1541; CHECK: exit.loopexit:1542; CHECK-NEXT: br label [[EXIT]]1543; CHECK: exit:1544; CHECK-NEXT: ret void1545;1546entry:1547 %pre.c = icmp ugt i32 %Acols, 01548 br i1 %pre.c, label %exit, label %outer.header1549 1550outer.header:1551 %outer.iv = phi i32 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]1552 %mul.us = mul i32 %outer.iv, %Acols1553 %arrayidx.us = getelementptr double, ptr %A, i32 %mul.us1554 br label %inner1555 1556inner:1557 %inner.iv = phi i32 [ 0, %outer.header ], [ %inner.iv.next, %inner ]1558 %gep.C = getelementptr inbounds double, ptr %C, i32 %inner.iv1559 %l = load double, ptr %arrayidx.us, align 81560 store double %l, ptr %gep.C, align 81561 %inner.iv.next = add i32 %inner.iv, 11562 %inner.c = icmp eq i32 %inner.iv.next, 10001563 br i1 %inner.c, label %outer.latch, label %inner1564 1565outer.latch:1566 %outer.iv.next = add i32 %outer.iv, 11567 %outer.c = icmp ult i32 %outer.iv, 1281568 br i1 %outer.c, label %exit, label %outer.header1569 1570exit:1571 ret void1572}1573