blob: af3bb4a1d1f1d0582d0eeec62324e24ab569ed94 [file]
; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --check-globals none --version 6
; REQUIRES: asserts
; RUN: opt < %s -p 'loop-vectorize' -force-vector-interleave=1 -S \
; RUN: -force-vector-width=4 -debug-only=loop-accesses,loop-vectorize,loop-utils 2> %t | FileCheck %s
; RUN: cat %t | FileCheck %s --check-prefix=DEBUG
target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
; Equivalent example in C:
; void diff_checks(int32_t *dst, int32_t *src, int m, int n) {
; for (int i = 0; i < m; i++) {
; for (int j = 0; j < n; j++) {
; dst[(i * (n + 1)) + j] = src[(i * n) + j];
; }
; }
; }
; NOTE: The strides of the starting address values in the inner loop differ, i.e.
; '(i * (n + 1))' vs '(i * n)'.
; DEBUG-LABEL: 'diff_checks'
; DEBUG: LAA: Found an analyzable loop: inner.loop
; DEBUG: LAA: Not creating diff runtime check, since these cannot be hoisted out of the outer loop
; DEBUG: LAA: Adding RT check for range:
; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting
; DEBUG-NEXT: LAA: ... but need to check stride is positive: (4 * (sext i32 (1 + %n)<nuw> to i64))<nsw>
; 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)
; DEBUG-NEXT: LAA: Adding RT check for range:
; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting
; DEBUG-NEXT: Start: %src End: ((4 * (zext i32 %m to i64) * (zext i32 %n to i64)) + %src)
define void @diff_checks(ptr nocapture noundef writeonly %dst, ptr nocapture noundef readonly %src, i32 noundef %m, i32 noundef %n) {
; CHECK-LABEL: define void @diff_checks(
; CHECK-SAME: ptr noundef writeonly captures(none) [[DST:%.*]], ptr noundef readonly captures(none) [[SRC:%.*]], i32 noundef [[M:%.*]], i32 noundef [[N:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[ADD5:%.*]] = add nuw i32 [[N]], 1
; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[N]] to i64
; CHECK-NEXT: [[TMP1:%.*]] = sext i32 [[ADD5]] to i64
; CHECK-NEXT: [[WIDE_M:%.*]] = zext i32 [[M]] to i64
; CHECK-NEXT: [[WIDE_N:%.*]] = zext i32 [[N]] to i64
; CHECK-NEXT: [[TMP7:%.*]] = shl nsw i64 [[TMP1]], 2
; CHECK-NEXT: [[TMP8:%.*]] = mul i64 [[WIDE_N]], [[WIDE_M]]
; CHECK-NEXT: [[TMP9:%.*]] = shl i64 [[TMP8]], 2
; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP9]]
; CHECK-NEXT: [[TMP2:%.*]] = add nsw i64 [[WIDE_M]], -1
; CHECK-NEXT: [[TMP3:%.*]] = mul i64 [[TMP2]], [[TMP1]]
; CHECK-NEXT: [[TMP4:%.*]] = shl i64 [[TMP3]], 2
; CHECK-NEXT: [[TMP5:%.*]] = shl nuw nsw i64 [[WIDE_N]], 2
; CHECK-NEXT: [[TMP6:%.*]] = add i64 [[TMP4]], [[TMP5]]
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP6]]
; CHECK-NEXT: br label %[[OUTER_LOOP:.*]]
; CHECK: [[OUTER_LOOP]]:
; CHECK-NEXT: [[IV_OUTER:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[IV_OUTER_NEXT:%.*]], %[[INNER_EXIT:.*]] ]
; CHECK-NEXT: [[TMP10:%.*]] = mul nsw i64 [[IV_OUTER]], [[TMP0]]
; CHECK-NEXT: [[TMP11:%.*]] = mul nsw i64 [[IV_OUTER]], [[TMP1]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_N]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP1]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: [[STRIDE_CHECK:%.*]] = icmp slt i64 [[TMP7]], 0
; CHECK-NEXT: [[TMP12:%.*]] = or i1 [[FOUND_CONFLICT]], [[STRIDE_CHECK]]
; CHECK-NEXT: br i1 [[TMP12]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[N_MOD_VF:%.*]] = and i64 [[WIDE_N]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[WIDE_N]], [[N_MOD_VF]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP13:%.*]] = add nuw nsw i64 [[INDEX]], [[TMP10]]
; CHECK-NEXT: [[TMP14:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP13]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP14]], align 4, !alias.scope [[META0:![0-9]+]]
; CHECK-NEXT: [[TMP15:%.*]] = add nsw i64 [[INDEX]], [[TMP11]]
; CHECK-NEXT: [[TMP16:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP15]]
; CHECK-NEXT: store <4 x i32> [[WIDE_LOAD]], ptr [[TMP16]], align 4, !alias.scope [[META3:![0-9]+]], !noalias [[META0]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP17:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP17]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP5:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_N]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[INNER_EXIT]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER_LOOP]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER_LOOP:.*]]
; CHECK: [[INNER_LOOP]]:
; CHECK-NEXT: [[IV_INNER:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_INNER_NEXT:%.*]], %[[INNER_LOOP]] ]
; CHECK-NEXT: [[TMP18:%.*]] = add nuw nsw i64 [[IV_INNER]], [[TMP10]]
; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP18]]
; CHECK-NEXT: [[TMP19:%.*]] = load i32, ptr [[ARRAYIDX_US]], align 4
; CHECK-NEXT: [[TMP20:%.*]] = add nsw i64 [[IV_INNER]], [[TMP11]]
; CHECK-NEXT: [[ARRAYIDX9_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP20]]
; CHECK-NEXT: store i32 [[TMP19]], ptr [[ARRAYIDX9_US]], align 4
; CHECK-NEXT: [[IV_INNER_NEXT]] = add nuw nsw i64 [[IV_INNER]], 1
; CHECK-NEXT: [[INNER_EXIT_COND:%.*]] = icmp eq i64 [[IV_INNER_NEXT]], [[WIDE_N]]
; CHECK-NEXT: br i1 [[INNER_EXIT_COND]], label %[[INNER_EXIT]], label %[[INNER_LOOP]], !llvm.loop [[LOOP8:![0-9]+]]
; CHECK: [[INNER_EXIT]]:
; CHECK-NEXT: [[IV_OUTER_NEXT]] = add nuw nsw i64 [[IV_OUTER]], 1
; CHECK-NEXT: [[OUTER_EXIT_COND:%.*]] = icmp eq i64 [[IV_OUTER_NEXT]], [[WIDE_M]]
; CHECK-NEXT: br i1 [[OUTER_EXIT_COND]], label %[[OUTER_EXIT:.*]], label %[[OUTER_LOOP]]
; CHECK: [[OUTER_EXIT]]:
; CHECK-NEXT: ret void
;
entry:
%add5 = add nuw i32 %n, 1
%0 = zext i32 %n to i64
%1 = sext i32 %add5 to i64
%wide.m = zext i32 %m to i64
%wide.n = zext i32 %n to i64
br label %outer.loop
outer.loop:
%iv.outer = phi i64 [ 0, %entry ], [ %iv.outer.next, %inner.exit ]
%2 = mul nsw i64 %iv.outer, %0
%3 = mul nsw i64 %iv.outer, %1
br label %inner.loop
inner.loop:
%iv.inner = phi i64 [ 0, %outer.loop ], [ %iv.inner.next, %inner.loop ]
%4 = add nuw nsw i64 %iv.inner, %2
%arrayidx.us = getelementptr inbounds i32, ptr %src, i64 %4
%5 = load i32, ptr %arrayidx.us, align 4
%6 = add nsw i64 %iv.inner, %3
%arrayidx9.us = getelementptr inbounds i32, ptr %dst, i64 %6
store i32 %5, ptr %arrayidx9.us, align 4
%iv.inner.next = add nuw nsw i64 %iv.inner, 1
%inner.exit.cond = icmp eq i64 %iv.inner.next, %wide.n
br i1 %inner.exit.cond, label %inner.exit, label %inner.loop
inner.exit:
%iv.outer.next = add nuw nsw i64 %iv.outer, 1
%outer.exit.cond = icmp eq i64 %iv.outer.next, %wide.m
br i1 %outer.exit.cond, label %outer.exit, label %outer.loop
outer.exit:
ret void
}
; Equivalent example in C:
; void full_checks(int32_t *dst, int32_t *src, int m, int n) {
; for (int i = 0; i < m; i++) {
; for (int j = 0; j < n; j++) {
; dst[(i * n) + j] += src[(i * n) + j];
; }
; }
; }
; We decide to do full runtime checks here (as opposed to diff checks) due to
; the additional load of 'dst[(i * n) + j]' in the loop.
; DEBUG-LABEL: 'full_checks'
; DEBUG: LAA: Found an analyzable loop: inner.loop
; DEBUG-NOT: LAA: Creating diff runtime check for:
; DEBUG: LAA: Adding RT check for range:
; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting
; DEBUG-NEXT: Start: %dst End: ((4 * (zext i32 %m to i64) * (zext i32 %n to i64)) + %dst)
; DEBUG-NEXT: LAA: Adding RT check for range:
; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting
; DEBUG-NEXT: Start: %src End: ((4 * (zext i32 %m to i64) * (zext i32 %n to i64)) + %src)
define void @full_checks(ptr nocapture noundef %dst, ptr nocapture noundef readonly %src, i32 noundef %m, i32 noundef %n) {
; CHECK-LABEL: define void @full_checks(
; CHECK-SAME: ptr noundef captures(none) [[DST:%.*]], ptr noundef readonly captures(none) [[SRC:%.*]], i32 noundef [[M:%.*]], i32 noundef [[N:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[N]] to i64
; CHECK-NEXT: [[WIDE_M:%.*]] = zext i32 [[M]] to i64
; CHECK-NEXT: [[WIDE_N:%.*]] = zext i32 [[N]] to i64
; CHECK-NEXT: [[TMP1:%.*]] = mul i64 [[WIDE_N]], [[WIDE_M]]
; CHECK-NEXT: [[TMP2:%.*]] = shl i64 [[TMP1]], 2
; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP2]]
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP2]]
; CHECK-NEXT: br label %[[OUTER_LOOP:.*]]
; CHECK: [[OUTER_LOOP]]:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[OUTER_IV_NEXT:%.*]], %[[INNER_EXIT:.*]] ]
; CHECK-NEXT: [[TMP3:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP0]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_N]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP1]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[N_MOD_VF:%.*]] = and i64 [[WIDE_N]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[WIDE_N]], [[N_MOD_VF]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP4:%.*]] = add nuw nsw i64 [[INDEX]], [[TMP3]]
; CHECK-NEXT: [[TMP5:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP4]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP5]], align 4, !alias.scope [[META9:![0-9]+]]
; CHECK-NEXT: [[TMP6:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP4]]
; CHECK-NEXT: [[WIDE_LOAD2:%.*]] = load <4 x i32>, ptr [[TMP6]], align 4, !alias.scope [[META12:![0-9]+]], !noalias [[META9]]
; CHECK-NEXT: [[TMP7:%.*]] = add nsw <4 x i32> [[WIDE_LOAD2]], [[WIDE_LOAD]]
; CHECK-NEXT: store <4 x i32> [[TMP7]], ptr [[TMP6]], align 4, !alias.scope [[META12]], !noalias [[META9]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP8:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP8]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP14:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_N]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[INNER_EXIT]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER_LOOP]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER_LOOP:.*]]
; CHECK: [[INNER_LOOP]]:
; CHECK-NEXT: [[IV_INNER:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_INNER_NEXT:%.*]], %[[INNER_LOOP]] ]
; CHECK-NEXT: [[TMP9:%.*]] = add nuw nsw i64 [[IV_INNER]], [[TMP3]]
; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP9]]
; CHECK-NEXT: [[TMP10:%.*]] = load i32, ptr [[ARRAYIDX_US]], align 4
; CHECK-NEXT: [[ARRAYIDX8_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP9]]
; CHECK-NEXT: [[TMP11:%.*]] = load i32, ptr [[ARRAYIDX8_US]], align 4
; CHECK-NEXT: [[ADD9_US:%.*]] = add nsw i32 [[TMP11]], [[TMP10]]
; CHECK-NEXT: store i32 [[ADD9_US]], ptr [[ARRAYIDX8_US]], align 4
; CHECK-NEXT: [[IV_INNER_NEXT]] = add nuw nsw i64 [[IV_INNER]], 1
; CHECK-NEXT: [[INNER_EXIT_COND:%.*]] = icmp eq i64 [[IV_INNER_NEXT]], [[WIDE_N]]
; CHECK-NEXT: br i1 [[INNER_EXIT_COND]], label %[[INNER_EXIT]], label %[[INNER_LOOP]], !llvm.loop [[LOOP15:![0-9]+]]
; CHECK: [[INNER_EXIT]]:
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nuw nsw i64 [[OUTER_IV]], 1
; CHECK-NEXT: [[OUTER_EXIT_COND:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[WIDE_M]]
; CHECK-NEXT: br i1 [[OUTER_EXIT_COND]], label %[[OUTER_EXIT:.*]], label %[[OUTER_LOOP]]
; CHECK: [[OUTER_EXIT]]:
; CHECK-NEXT: ret void
;
entry:
%0 = zext i32 %n to i64
%wide.m = zext i32 %m to i64
%wide.n = zext i32 %n to i64
br label %outer.loop
outer.loop:
%outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %inner.exit ]
%1 = mul nsw i64 %outer.iv, %0
br label %inner.loop
inner.loop:
%iv.inner = phi i64 [ 0, %outer.loop ], [ %iv.inner.next, %inner.loop ]
%2 = add nuw nsw i64 %iv.inner, %1
%arrayidx.us = getelementptr inbounds i32, ptr %src, i64 %2
%3 = load i32, ptr %arrayidx.us, align 4
%arrayidx8.us = getelementptr inbounds i32, ptr %dst, i64 %2
%4 = load i32, ptr %arrayidx8.us, align 4
%add9.us = add nsw i32 %4, %3
store i32 %add9.us, ptr %arrayidx8.us, align 4
%iv.inner.next = add nuw nsw i64 %iv.inner, 1
%inner.exit.cond = icmp eq i64 %iv.inner.next, %wide.n
br i1 %inner.exit.cond, label %inner.exit, label %inner.loop
inner.exit:
%outer.iv.next = add nuw nsw i64 %outer.iv, 1
%outer.exit.cond = icmp eq i64 %outer.iv.next, %wide.m
br i1 %outer.exit.cond, label %outer.exit, label %outer.loop
outer.exit:
ret void
}
; Equivalent example in C:
; void full_checks_diff_strides(int32_t *dst, int32_t *src, int m, int n) {
; for (int i = 0; i < m; i++) {
; for (int j = 0; j < n; j++) {
; dst[(i * (n + 1)) + j] += src[(i * n) + j];
; }
; }
; }
; We decide to do full runtime checks here (as opposed to diff checks) due to
; the additional load of 'dst[(i * n) + j]' in the loop.
; NOTE: This is different to the test above (@full_checks) because the dst array
; is accessed with a higher stride compared src, and therefore the inner loop
; runtime checks will vary for each outer loop iteration.
; DEBUG-LABEL: 'full_checks_diff_strides'
; DEBUG: LAA: Found an analyzable loop: inner.loop
; DEBUG-NOT: LAA: Creating diff runtime check for:
; DEBUG: LAA: Adding RT check for range:
; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting
; 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)
; DEBUG-NEXT: LAA: Adding RT check for range:
; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting
; DEBUG-NEXT: Start: %src End: ((4 * (zext i32 %m to i64) * (zext i32 %n to i64)) + %src)
define void @full_checks_diff_strides(ptr nocapture noundef %dst, ptr nocapture noundef readonly %src, i32 noundef %m, i32 noundef %n) {
; CHECK-LABEL: define void @full_checks_diff_strides(
; CHECK-SAME: ptr noundef captures(none) [[DST:%.*]], ptr noundef readonly captures(none) [[SRC:%.*]], i32 noundef [[M:%.*]], i32 noundef [[N:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[WIDE_M:%.*]] = zext i32 [[M]] to i64
; CHECK-NEXT: [[WIDE_N:%.*]] = zext i32 [[N]] to i64
; CHECK-NEXT: [[TMP5:%.*]] = mul i64 [[WIDE_N]], [[WIDE_M]]
; CHECK-NEXT: [[TMP6:%.*]] = shl i64 [[TMP5]], 2
; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP6]]
; CHECK-NEXT: [[TMP0:%.*]] = add nsw i64 [[WIDE_M]], -1
; CHECK-NEXT: [[TMP1:%.*]] = shl nuw nsw i64 [[WIDE_N]], 2
; CHECK-NEXT: [[TMP2:%.*]] = add nuw nsw i64 [[TMP1]], 4
; CHECK-NEXT: [[TMP3:%.*]] = mul i64 [[TMP0]], [[TMP2]]
; CHECK-NEXT: [[TMP4:%.*]] = add i64 [[TMP3]], [[TMP1]]
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP4]]
; CHECK-NEXT: br label %[[OUTER_LOOP:.*]]
; CHECK: [[OUTER_LOOP]]:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[OUTER_IV_NEXT:%.*]], %[[INNER_EXIT:.*]] ]
; CHECK-NEXT: [[NPLUS1:%.*]] = add nuw nsw i32 [[N]], 1
; CHECK-NEXT: [[WIDE_NPLUS1:%.*]] = zext i32 [[NPLUS1]] to i64
; CHECK-NEXT: [[TMP7:%.*]] = mul nsw i64 [[OUTER_IV]], [[WIDE_N]]
; CHECK-NEXT: [[TMP8:%.*]] = mul nsw i64 [[OUTER_IV]], [[WIDE_NPLUS1]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_N]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP1]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[N_MOD_VF:%.*]] = and i64 [[WIDE_N]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[WIDE_N]], [[N_MOD_VF]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP9:%.*]] = add nuw nsw i64 [[INDEX]], [[TMP7]]
; CHECK-NEXT: [[TMP10:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP9]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP10]], align 4, !alias.scope [[META16:![0-9]+]]
; CHECK-NEXT: [[TMP11:%.*]] = add nuw nsw i64 [[INDEX]], [[TMP8]]
; CHECK-NEXT: [[TMP12:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP11]]
; CHECK-NEXT: [[WIDE_LOAD2:%.*]] = load <4 x i32>, ptr [[TMP12]], align 4, !alias.scope [[META19:![0-9]+]], !noalias [[META16]]
; CHECK-NEXT: [[TMP13:%.*]] = add nsw <4 x i32> [[WIDE_LOAD2]], [[WIDE_LOAD]]
; CHECK-NEXT: store <4 x i32> [[TMP13]], ptr [[TMP12]], align 4, !alias.scope [[META19]], !noalias [[META16]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP14:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP14]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP21:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_N]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[INNER_EXIT]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER_LOOP]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER_LOOP:.*]]
; CHECK: [[INNER_LOOP]]:
; CHECK-NEXT: [[IV_INNER:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_INNER_NEXT:%.*]], %[[INNER_LOOP]] ]
; CHECK-NEXT: [[TMP15:%.*]] = add nuw nsw i64 [[IV_INNER]], [[TMP7]]
; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP15]]
; CHECK-NEXT: [[TMP16:%.*]] = load i32, ptr [[ARRAYIDX_US]], align 4
; CHECK-NEXT: [[TMP17:%.*]] = add nuw nsw i64 [[IV_INNER]], [[TMP8]]
; CHECK-NEXT: [[ARRAYIDX8_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP17]]
; CHECK-NEXT: [[TMP18:%.*]] = load i32, ptr [[ARRAYIDX8_US]], align 4
; CHECK-NEXT: [[ADD9_US:%.*]] = add nsw i32 [[TMP18]], [[TMP16]]
; CHECK-NEXT: store i32 [[ADD9_US]], ptr [[ARRAYIDX8_US]], align 4
; CHECK-NEXT: [[IV_INNER_NEXT]] = add nuw nsw i64 [[IV_INNER]], 1
; CHECK-NEXT: [[INNER_EXIT_COND:%.*]] = icmp eq i64 [[IV_INNER_NEXT]], [[WIDE_N]]
; CHECK-NEXT: br i1 [[INNER_EXIT_COND]], label %[[INNER_EXIT]], label %[[INNER_LOOP]], !llvm.loop [[LOOP22:![0-9]+]]
; CHECK: [[INNER_EXIT]]:
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nuw nsw i64 [[OUTER_IV]], 1
; CHECK-NEXT: [[OUTER_EXIT_COND:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[WIDE_M]]
; CHECK-NEXT: br i1 [[OUTER_EXIT_COND]], label %[[OUTER_EXIT:.*]], label %[[OUTER_LOOP]]
; CHECK: [[OUTER_EXIT]]:
; CHECK-NEXT: ret void
;
entry:
%wide.m = zext i32 %m to i64
%wide.n = zext i32 %n to i64
br label %outer.loop
outer.loop:
%outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %inner.exit ]
%nplus1 = add nuw nsw i32 %n, 1
%wide.nplus1 = zext i32 %nplus1 to i64
%0 = mul nsw i64 %outer.iv, %wide.n
%1 = mul nsw i64 %outer.iv, %wide.nplus1
br label %inner.loop
inner.loop:
%iv.inner = phi i64 [ 0, %outer.loop ], [ %iv.inner.next, %inner.loop ]
%2 = add nuw nsw i64 %iv.inner, %0
%arrayidx.us = getelementptr inbounds i32, ptr %src, i64 %2
%3 = load i32, ptr %arrayidx.us, align 4
%4 = add nuw nsw i64 %iv.inner, %1
%arrayidx8.us = getelementptr inbounds i32, ptr %dst, i64 %4
%5 = load i32, ptr %arrayidx8.us, align 4
%add9.us = add nsw i32 %5, %3
store i32 %add9.us, ptr %arrayidx8.us, align 4
%iv.inner.next = add nuw nsw i64 %iv.inner, 1
%inner.exit.cond = icmp eq i64 %iv.inner.next, %wide.n
br i1 %inner.exit.cond, label %inner.exit, label %inner.loop
inner.exit:
%outer.iv.next = add nuw nsw i64 %outer.iv, 1
%outer.exit.cond = icmp eq i64 %outer.iv.next, %wide.m
br i1 %outer.exit.cond, label %outer.exit, label %outer.loop
outer.exit:
ret void
}
; Equivalent example in C:
; void diff_checks_src_start_invariant(int32_t *dst, int32_t *src, int m, int n) {
; for (int i = 0; i < m; i++) {
; for (int j = 0; j < n; j++) {
; dst[(i * n) + j] = src[j];
; }
; }
; }
; DEBUG-LABEL: 'diff_checks_src_start_invariant'
; DEBUG: LAA: Found an analyzable loop: inner.loop
; DEBUG-NOT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting
define void @diff_checks_src_start_invariant(ptr nocapture noundef writeonly %dst, ptr nocapture noundef readonly %src, i32 noundef %m, i32 noundef %n) {
; CHECK-LABEL: define void @diff_checks_src_start_invariant(
; CHECK-SAME: ptr noundef writeonly captures(none) [[DST:%.*]], ptr noundef readonly captures(none) [[SRC:%.*]], i32 noundef [[M:%.*]], i32 noundef [[N:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[SRC2:%.*]] = ptrtoaddr ptr [[SRC]] to i64
; CHECK-NEXT: [[DST1:%.*]] = ptrtoaddr ptr [[DST]] to i64
; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[N]] to i64
; CHECK-NEXT: [[WIDE_M:%.*]] = zext i32 [[M]] to i64
; CHECK-NEXT: [[WIDE_N:%.*]] = zext i32 [[N]] to i64
; CHECK-NEXT: [[TMP2:%.*]] = shl nuw nsw i64 [[WIDE_N]], 2
; CHECK-NEXT: [[TMP1:%.*]] = sub i64 [[DST1]], [[SRC2]]
; CHECK-NEXT: br label %[[OUTER_LOOP:.*]]
; CHECK: [[OUTER_LOOP]]:
; CHECK-NEXT: [[IV_OUTER:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[IV_OUTER_NEXT:%.*]], %[[INNER_LOOP_EXIT:.*]] ]
; CHECK-NEXT: [[TMP5:%.*]] = mul nsw i64 [[IV_OUTER]], [[TMP0]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_N]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[TMP13:%.*]] = mul i64 [[IV_OUTER]], [[TMP2]]
; CHECK-NEXT: [[TMP4:%.*]] = add i64 [[TMP1]], [[TMP13]]
; CHECK-NEXT: [[TMP12:%.*]] = sub i64 [[TMP4]], 1
; CHECK-NEXT: [[DIFF_CHECK:%.*]] = icmp ult i64 [[TMP12]], 15
; CHECK-NEXT: br i1 [[DIFF_CHECK]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[N_MOD_VF:%.*]] = and i64 [[WIDE_N]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[WIDE_N]], [[N_MOD_VF]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP6:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[INDEX]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP6]], align 4
; CHECK-NEXT: [[TMP7:%.*]] = add nuw nsw i64 [[INDEX]], [[TMP5]]
; CHECK-NEXT: [[TMP8:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP7]]
; CHECK-NEXT: store <4 x i32> [[WIDE_LOAD]], ptr [[TMP8]], align 4
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP9:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP9]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP23:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_N]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[INNER_LOOP_EXIT]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER_LOOP]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER_LOOP:.*]]
; CHECK: [[INNER_LOOP]]:
; CHECK-NEXT: [[IV_INNER:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_INNER_NEXT:%.*]], %[[INNER_LOOP]] ]
; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[IV_INNER]]
; CHECK-NEXT: [[TMP10:%.*]] = load i32, ptr [[ARRAYIDX_US]], align 4
; CHECK-NEXT: [[TMP11:%.*]] = add nuw nsw i64 [[IV_INNER]], [[TMP5]]
; CHECK-NEXT: [[ARRAYIDX6_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP11]]
; CHECK-NEXT: store i32 [[TMP10]], ptr [[ARRAYIDX6_US]], align 4
; CHECK-NEXT: [[IV_INNER_NEXT]] = add nuw nsw i64 [[IV_INNER]], 1
; CHECK-NEXT: [[INNER_EXIT_COND:%.*]] = icmp eq i64 [[IV_INNER_NEXT]], [[WIDE_N]]
; CHECK-NEXT: br i1 [[INNER_EXIT_COND]], label %[[INNER_LOOP_EXIT]], label %[[INNER_LOOP]], !llvm.loop [[LOOP24:![0-9]+]]
; CHECK: [[INNER_LOOP_EXIT]]:
; CHECK-NEXT: [[IV_OUTER_NEXT]] = add nuw nsw i64 [[IV_OUTER]], 1
; CHECK-NEXT: [[OUTER_EXIT_COND:%.*]] = icmp eq i64 [[IV_OUTER_NEXT]], [[WIDE_M]]
; CHECK-NEXT: br i1 [[OUTER_EXIT_COND]], label %[[OUTER_LOOP_EXIT:.*]], label %[[OUTER_LOOP]]
; CHECK: [[OUTER_LOOP_EXIT]]:
; CHECK-NEXT: ret void
;
entry:
%0 = zext i32 %n to i64
%wide.m = zext i32 %m to i64
%wide.n = zext i32 %n to i64
br label %outer.loop
outer.loop:
%iv.outer = phi i64 [ 0, %entry ], [ %iv.outer.next, %inner.loop.exit ]
%1 = mul nsw i64 %iv.outer, %0
br label %inner.loop
inner.loop:
%iv.inner = phi i64 [ 0, %outer.loop ], [ %iv.inner.next, %inner.loop ]
%arrayidx.us = getelementptr inbounds i32, ptr %src, i64 %iv.inner
%2 = load i32, ptr %arrayidx.us, align 4
%3 = add nuw nsw i64 %iv.inner, %1
%arrayidx6.us = getelementptr inbounds i32, ptr %dst, i64 %3
store i32 %2, ptr %arrayidx6.us, align 4
%iv.inner.next = add nuw nsw i64 %iv.inner, 1
%inner.exit.cond = icmp eq i64 %iv.inner.next, %wide.n
br i1 %inner.exit.cond, label %inner.loop.exit, label %inner.loop
inner.loop.exit:
%iv.outer.next = add nuw nsw i64 %iv.outer, 1
%outer.exit.cond = icmp eq i64 %iv.outer.next, %wide.m
br i1 %outer.exit.cond, label %outer.loop.exit, label %outer.loop
outer.loop.exit:
ret void
}
; Equivalent example in C:
; void full_checks_src_start_invariant(int32_t *dst, int32_t *src, int m, int n) {
; for (int i = 0; i < m; i++) {
; for (int j = 0; j < n; j++) {
; dst[(i * n) + j] += src[j];
; }
; }
; }
; DEBUG-LABEL: 'full_checks_src_start_invariant'
; DEBUG: LAA: Found an analyzable loop: inner.loop
; DEBUG: LAA: Adding RT check for range:
; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting
; DEBUG-NEXT: Start: %dst End: ((4 * (zext i32 %m to i64) * (zext i32 %n to i64)) + %dst)
; DEBUG-NEXT: LAA: Adding RT check for range:
; DEBUG-NEXT: Start: %src End: ((4 * (zext i32 %n to i64))<nuw><nsw> + %src)
define void @full_checks_src_start_invariant(ptr nocapture noundef %dst, ptr nocapture noundef readonly %src, i32 noundef %m, i32 noundef %n) {
; CHECK-LABEL: define void @full_checks_src_start_invariant(
; CHECK-SAME: ptr noundef captures(none) [[DST:%.*]], ptr noundef readonly captures(none) [[SRC:%.*]], i32 noundef [[M:%.*]], i32 noundef [[N:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[N]] to i64
; CHECK-NEXT: [[WIDE_M:%.*]] = zext i32 [[M]] to i64
; CHECK-NEXT: [[WIDE_N:%.*]] = zext i32 [[N]] to i64
; CHECK-NEXT: [[TMP3:%.*]] = shl nuw nsw i64 [[WIDE_N]], 2
; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP3]]
; CHECK-NEXT: [[TMP1:%.*]] = mul i64 [[WIDE_N]], [[WIDE_M]]
; CHECK-NEXT: [[TMP2:%.*]] = shl i64 [[TMP1]], 2
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP2]]
; CHECK-NEXT: br label %[[OUTER_LOOP:.*]]
; CHECK: [[OUTER_LOOP]]:
; CHECK-NEXT: [[IV_OUTER:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[IV_OUTER_NEXT:%.*]], %[[INNER_LOOP_EXIT:.*]] ]
; CHECK-NEXT: [[TMP4:%.*]] = mul nsw i64 [[IV_OUTER]], [[TMP0]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_N]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP1]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[N_MOD_VF:%.*]] = and i64 [[WIDE_N]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[WIDE_N]], [[N_MOD_VF]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP5:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[INDEX]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP5]], align 4, !alias.scope [[META25:![0-9]+]]
; CHECK-NEXT: [[TMP6:%.*]] = add nuw nsw i64 [[INDEX]], [[TMP4]]
; CHECK-NEXT: [[TMP7:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP6]]
; CHECK-NEXT: [[WIDE_LOAD2:%.*]] = load <4 x i32>, ptr [[TMP7]], align 4, !alias.scope [[META28:![0-9]+]], !noalias [[META25]]
; CHECK-NEXT: [[TMP8:%.*]] = add nsw <4 x i32> [[WIDE_LOAD2]], [[WIDE_LOAD]]
; CHECK-NEXT: store <4 x i32> [[TMP8]], ptr [[TMP7]], align 4, !alias.scope [[META28]], !noalias [[META25]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP9:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP9]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP30:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_N]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[INNER_LOOP_EXIT]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER_LOOP]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER_LOOP:.*]]
; CHECK: [[INNER_LOOP]]:
; CHECK-NEXT: [[IV_INNER:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_INNER_NEXT:%.*]], %[[INNER_LOOP]] ]
; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[IV_INNER]]
; CHECK-NEXT: [[TMP10:%.*]] = load i32, ptr [[ARRAYIDX_US]], align 4
; CHECK-NEXT: [[TMP11:%.*]] = add nuw nsw i64 [[IV_INNER]], [[TMP4]]
; CHECK-NEXT: [[ARRAYIDX6_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP11]]
; CHECK-NEXT: [[TMP12:%.*]] = load i32, ptr [[ARRAYIDX6_US]], align 4
; CHECK-NEXT: [[ADD7_US:%.*]] = add nsw i32 [[TMP12]], [[TMP10]]
; CHECK-NEXT: store i32 [[ADD7_US]], ptr [[ARRAYIDX6_US]], align 4
; CHECK-NEXT: [[IV_INNER_NEXT]] = add nuw nsw i64 [[IV_INNER]], 1
; CHECK-NEXT: [[INNER_EXIT_COND:%.*]] = icmp eq i64 [[IV_INNER_NEXT]], [[WIDE_N]]
; CHECK-NEXT: br i1 [[INNER_EXIT_COND]], label %[[INNER_LOOP_EXIT]], label %[[INNER_LOOP]], !llvm.loop [[LOOP31:![0-9]+]]
; CHECK: [[INNER_LOOP_EXIT]]:
; CHECK-NEXT: [[IV_OUTER_NEXT]] = add nuw nsw i64 [[IV_OUTER]], 1
; CHECK-NEXT: [[OUTER_EXIT_COND:%.*]] = icmp eq i64 [[IV_OUTER_NEXT]], [[WIDE_M]]
; CHECK-NEXT: br i1 [[OUTER_EXIT_COND]], label %[[OUTER_LOOP_EXIT:.*]], label %[[OUTER_LOOP]]
; CHECK: [[OUTER_LOOP_EXIT]]:
; CHECK-NEXT: ret void
;
entry:
%0 = zext i32 %n to i64
%wide.m = zext i32 %m to i64
%wide.n = zext i32 %n to i64
br label %outer.loop
outer.loop:
%iv.outer = phi i64 [ 0, %entry ], [ %iv.outer.next, %inner.loop.exit ]
%1 = mul nsw i64 %iv.outer, %0
br label %inner.loop
inner.loop:
%iv.inner = phi i64 [ 0, %outer.loop ], [ %iv.inner.next, %inner.loop ]
%arrayidx.us = getelementptr inbounds i32, ptr %src, i64 %iv.inner
%2 = load i32, ptr %arrayidx.us, align 4
%3 = add nuw nsw i64 %iv.inner, %1
%arrayidx6.us = getelementptr inbounds i32, ptr %dst, i64 %3
%4 = load i32, ptr %arrayidx6.us, align 4
%add7.us = add nsw i32 %4, %2
store i32 %add7.us, ptr %arrayidx6.us, align 4
%iv.inner.next = add nuw nsw i64 %iv.inner, 1
%inner.exit.cond = icmp eq i64 %iv.inner.next, %wide.n
br i1 %inner.exit.cond, label %inner.loop.exit, label %inner.loop
inner.loop.exit:
%iv.outer.next = add nuw nsw i64 %iv.outer, 1
%outer.exit.cond = icmp eq i64 %iv.outer.next, %wide.m
br i1 %outer.exit.cond, label %outer.loop.exit, label %outer.loop
outer.loop.exit:
ret void
}
; Equivalent example in C:
; void triple_nested_loop_mixed_access(int *dst, int *src, int m, int n, int o) {
; for (int i = 0; i < m; i++) {
; for (int j = 0; j < n; j++) {
; for (int l = 0; l < o; l++) {
; dst[(i * n * (o + 1)) + (j * o) + l] += src[(i * n * o) + l];
; }
; }
; }
; }
; The 'src' access varies with the outermost loop, rather than the parent of the
; innermost loop. Hence we don't expand `src`, although in theory we could do.
; DEBUG-LABEL: 'triple_nested_loop_mixed_access'
; DEBUG: LAA: Found an analyzable loop: inner.loop
; DEBUG-NOT: LAA: Creating diff runtime check for:
; DEBUG: LAA: Adding RT check for range:
; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting
; 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>
; DEBUG-NEXT: LAA: Adding RT check for range:
; 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>
define void @triple_nested_loop_mixed_access(ptr nocapture noundef %dst, ptr nocapture noundef readonly %src, i32 noundef %m, i32 noundef %n, i32 noundef %o) {
; CHECK-LABEL: define void @triple_nested_loop_mixed_access(
; CHECK-SAME: ptr noundef captures(none) [[DST:%.*]], ptr noundef readonly captures(none) [[SRC:%.*]], i32 noundef [[M:%.*]], i32 noundef [[N:%.*]], i32 noundef [[O:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[ADD11:%.*]] = add nsw i32 [[O]], 1
; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[O]] to i64
; CHECK-NEXT: [[TMP1:%.*]] = zext i32 [[N]] to i64
; CHECK-NEXT: [[TMP2:%.*]] = zext i32 [[ADD11]] to i64
; CHECK-NEXT: [[WIDE_TRIP_COUNT68:%.*]] = zext i32 [[M]] to i64
; CHECK-NEXT: [[WIDE_TRIP_COUNT60:%.*]] = zext i32 [[N]] to i64
; CHECK-NEXT: [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[O]] to i64
; CHECK-NEXT: [[TMP3:%.*]] = shl nuw nsw i64 [[WIDE_TRIP_COUNT]], 2
; CHECK-NEXT: [[TMP5:%.*]] = mul i64 [[WIDE_TRIP_COUNT]], [[TMP1]]
; CHECK-NEXT: [[TMP6:%.*]] = shl i64 [[TMP5]], 2
; CHECK-NEXT: [[TMP7:%.*]] = mul i64 [[TMP1]], [[TMP2]]
; CHECK-NEXT: [[TMP8:%.*]] = shl i64 [[TMP7]], 2
; CHECK-NEXT: br label %[[OUTER_OUTER_LOOP:.*]]
; CHECK: [[OUTER_OUTER_LOOP]]:
; CHECK-NEXT: [[OUTER_OUTER_IV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[OUTER_OUTER_IV_NEXT:%.*]], %[[OUTER_LOOP_END:.*]] ]
; CHECK-NEXT: [[TMP13:%.*]] = mul i64 [[TMP6]], [[OUTER_OUTER_IV]]
; CHECK-NEXT: [[TMP12:%.*]] = add i64 [[TMP3]], [[TMP13]]
; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP12]]
; CHECK-NEXT: [[SCEVGEP3:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP13]]
; CHECK-NEXT: [[TMP10:%.*]] = mul i64 [[TMP8]], [[OUTER_OUTER_IV]]
; CHECK-NEXT: [[TMP11:%.*]] = add i64 [[TMP6]], [[TMP10]]
; CHECK-NEXT: [[SCEVGEP5:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP11]]
; CHECK-NEXT: [[SCEVGEP6:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP10]]
; CHECK-NEXT: [[TMP14:%.*]] = mul nsw i64 [[OUTER_OUTER_IV]], [[TMP1]]
; CHECK-NEXT: [[TMP15:%.*]] = mul nsw i64 [[TMP14]], [[TMP0]]
; CHECK-NEXT: [[TMP16:%.*]] = mul nsw i64 [[TMP14]], [[TMP2]]
; CHECK-NEXT: br label %[[OUTER_LOOP:.*]]
; CHECK: [[OUTER_LOOP]]:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ [[OUTER_IV_NEXT:%.*]], %[[INNER_LOOP_END:.*]] ], [ 0, %[[OUTER_OUTER_LOOP]] ]
; CHECK-NEXT: [[TMP17:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP0]]
; CHECK-NEXT: [[TMP18:%.*]] = add nuw nsw i64 [[TMP17]], [[TMP16]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_TRIP_COUNT]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[SCEVGEP6]], [[SCEVGEP2]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SCEVGEP3]], [[SCEVGEP5]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[N_MOD_VF:%.*]] = and i64 [[WIDE_TRIP_COUNT]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[WIDE_TRIP_COUNT]], [[N_MOD_VF]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP19:%.*]] = add nuw nsw i64 [[INDEX]], [[TMP15]]
; CHECK-NEXT: [[TMP20:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP19]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP20]], align 4, !alias.scope [[META32:![0-9]+]]
; CHECK-NEXT: [[TMP21:%.*]] = add nuw nsw i64 [[TMP18]], [[INDEX]]
; CHECK-NEXT: [[TMP22:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP21]]
; CHECK-NEXT: [[WIDE_LOAD4:%.*]] = load <4 x i32>, ptr [[TMP22]], align 4, !alias.scope [[META35:![0-9]+]], !noalias [[META32]]
; CHECK-NEXT: [[TMP23:%.*]] = add nsw <4 x i32> [[WIDE_LOAD4]], [[WIDE_LOAD]]
; CHECK-NEXT: store <4 x i32> [[TMP23]], ptr [[TMP22]], align 4, !alias.scope [[META35]], !noalias [[META32]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP24:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP24]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP37:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_TRIP_COUNT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[INNER_LOOP_END]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER_LOOP]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER_LOOP:.*]]
; CHECK: [[INNER_LOOP]]:
; CHECK-NEXT: [[INNER_IV:%.*]] = phi i64 [ [[INNER_IV_NEXT:%.*]], %[[INNER_LOOP]] ], [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ]
; CHECK-NEXT: [[TMP25:%.*]] = add nuw nsw i64 [[INNER_IV]], [[TMP15]]
; CHECK-NEXT: [[ARRAYIDX_US_US_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP25]]
; CHECK-NEXT: [[TMP26:%.*]] = load i32, ptr [[ARRAYIDX_US_US_US]], align 4
; CHECK-NEXT: [[TMP27:%.*]] = add nuw nsw i64 [[TMP18]], [[INNER_IV]]
; CHECK-NEXT: [[ARRAYIDX17_US_US_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP27]]
; CHECK-NEXT: [[TMP28:%.*]] = load i32, ptr [[ARRAYIDX17_US_US_US]], align 4
; CHECK-NEXT: [[ADD18_US_US_US:%.*]] = add nsw i32 [[TMP28]], [[TMP26]]
; CHECK-NEXT: store i32 [[ADD18_US_US_US]], ptr [[ARRAYIDX17_US_US_US]], align 4
; CHECK-NEXT: [[INNER_IV_NEXT]] = add nuw nsw i64 [[INNER_IV]], 1
; CHECK-NEXT: [[EXITCOND_NOT:%.*]] = icmp eq i64 [[INNER_IV_NEXT]], [[WIDE_TRIP_COUNT]]
; CHECK-NEXT: br i1 [[EXITCOND_NOT]], label %[[INNER_LOOP_END]], label %[[INNER_LOOP]], !llvm.loop [[LOOP38:![0-9]+]]
; CHECK: [[INNER_LOOP_END]]:
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nuw nsw i64 [[OUTER_IV]], 1
; CHECK-NEXT: [[EXIT_OUTER:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[WIDE_TRIP_COUNT60]]
; CHECK-NEXT: br i1 [[EXIT_OUTER]], label %[[OUTER_LOOP_END]], label %[[OUTER_LOOP]]
; CHECK: [[OUTER_LOOP_END]]:
; CHECK-NEXT: [[OUTER_OUTER_IV_NEXT]] = add nuw nsw i64 [[OUTER_OUTER_IV]], 1
; CHECK-NEXT: [[EXIT_OUTER_OUTER:%.*]] = icmp eq i64 [[OUTER_OUTER_IV_NEXT]], [[WIDE_TRIP_COUNT68]]
; CHECK-NEXT: br i1 [[EXIT_OUTER_OUTER]], label %[[EXIT:.*]], label %[[OUTER_OUTER_LOOP]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
%add11 = add nsw i32 %o, 1
%0 = zext i32 %o to i64
%1 = zext i32 %n to i64
%2 = zext i32 %add11 to i64
%wide.trip.count68 = zext i32 %m to i64
%wide.trip.count60 = zext i32 %n to i64
%wide.trip.count = zext i32 %o to i64
br label %outer.outer.loop
outer.outer.loop:
%outer.outer.iv = phi i64 [ 0, %entry ], [ %outer.outer.iv.next, %outer.loop.end ]
%3 = mul nsw i64 %outer.outer.iv, %1
%4 = mul nsw i64 %3, %0
%5 = mul nsw i64 %3, %2
br label %outer.loop
outer.loop:
%outer.iv = phi i64 [ %outer.iv.next, %inner.loop.end ], [ 0, %outer.outer.loop ]
%6 = mul nsw i64 %outer.iv, %0
%7 = add nuw nsw i64 %6, %5
br label %inner.loop
inner.loop:
%inner.iv = phi i64 [ %inner.iv.next, %inner.loop ], [ 0, %outer.loop ]
%8 = add nuw nsw i64 %inner.iv, %4
%arrayidx.us.us.us = getelementptr inbounds i32, ptr %src, i64 %8
%9 = load i32, ptr %arrayidx.us.us.us, align 4
%10 = add nuw nsw i64 %7, %inner.iv
%arrayidx17.us.us.us = getelementptr inbounds i32, ptr %dst, i64 %10
%11 = load i32, ptr %arrayidx17.us.us.us, align 4
%add18.us.us.us = add nsw i32 %11, %9
store i32 %add18.us.us.us, ptr %arrayidx17.us.us.us, align 4
%inner.iv.next = add nuw nsw i64 %inner.iv, 1
%exitcond.not = icmp eq i64 %inner.iv.next, %wide.trip.count
br i1 %exitcond.not, label %inner.loop.end, label %inner.loop
inner.loop.end:
%outer.iv.next = add nuw nsw i64 %outer.iv, 1
%exit.outer = icmp eq i64 %outer.iv.next, %wide.trip.count60
br i1 %exit.outer, label %outer.loop.end, label %outer.loop
outer.loop.end:
%outer.outer.iv.next = add nuw nsw i64 %outer.outer.iv, 1
%exit.outer.outer = icmp eq i64 %outer.outer.iv.next, %wide.trip.count68
br i1 %exit.outer.outer, label %exit, label %outer.outer.loop
exit:
ret void
}
; Equivalent example in C:
; void uncomputable_outer_tc(int32_t *dst, int32_t *src, char *str, int n) {
; int i;
; while (str[i] != '\0') {
; for (int j = 0; j < n; j++) {
; dst[(i * (n + 1)) + j] += src[(i * n) + j];
; }
; i++;
; }
; }
; Outer loop trip count is uncomputable so we shouldn't expand the ranges.
; DEBUG-LABEL: 'uncomputable_outer_tc'
; DEBUG: LAA: Found an analyzable loop: inner.loop
; DEBUG: LAA: Adding RT check for range:
; 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>
; DEBUG-NEXT: LAA: Adding RT check for range:
; 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>
define void @uncomputable_outer_tc(ptr nocapture noundef %dst, ptr nocapture noundef readonly %src, ptr nocapture noundef readonly %str, i32 noundef %n) {
; CHECK-LABEL: define void @uncomputable_outer_tc(
; CHECK-SAME: ptr noundef captures(none) [[DST:%.*]], ptr noundef readonly captures(none) [[SRC:%.*]], ptr noundef readonly captures(none) [[STR:%.*]], i32 noundef [[N:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*:]]
; CHECK-NEXT: [[TMP0:%.*]] = load i8, ptr [[STR]], align 1
; CHECK-NEXT: [[CMP_NOT23:%.*]] = icmp ne i8 [[TMP0]], 0
; CHECK-NEXT: [[CMP221:%.*]] = icmp sgt i32 [[N]], 0
; CHECK-NEXT: [[OR_COND:%.*]] = and i1 [[CMP_NOT23]], [[CMP221]]
; CHECK-NEXT: br i1 [[OR_COND]], label %[[OUTER_LOOP_PREHEADER:.*]], label %[[WHILE_END:.*]]
; CHECK: [[OUTER_LOOP_PREHEADER]]:
; CHECK-NEXT: [[ADD6:%.*]] = add nuw nsw i32 [[N]], 1
; CHECK-NEXT: [[TMP1:%.*]] = zext i32 [[N]] to i64
; CHECK-NEXT: [[TMP2:%.*]] = zext i32 [[ADD6]] to i64
; CHECK-NEXT: [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[N]] to i64
; CHECK-NEXT: [[TMP4:%.*]] = shl nuw nsw i64 [[WIDE_TRIP_COUNT]], 2
; CHECK-NEXT: [[OUTER_IV:%.*]] = shl nuw nsw i64 [[TMP2]], 2
; CHECK-NEXT: br label %[[OUTER_LOOP:.*]]
; CHECK: [[OUTER_LOOP]]:
; CHECK-NEXT: [[TMP3:%.*]] = phi i64 [ 0, %[[OUTER_LOOP_PREHEADER]] ], [ [[OUTER_IV_NEXT:%.*]], %[[INNER_LOOP_EXIT:.*]] ]
; CHECK-NEXT: [[TMP10:%.*]] = mul nsw i64 [[TMP3]], [[TMP1]]
; CHECK-NEXT: [[TMP11:%.*]] = mul nsw i64 [[TMP3]], [[TMP2]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_TRIP_COUNT]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[TMP6:%.*]] = mul i64 [[TMP3]], [[OUTER_IV]]
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP6]]
; CHECK-NEXT: [[TMP7:%.*]] = add i64 [[TMP4]], [[TMP6]]
; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP7]]
; CHECK-NEXT: [[TMP8:%.*]] = mul i64 [[TMP3]], [[TMP4]]
; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP8]]
; CHECK-NEXT: [[TMP9:%.*]] = add i64 [[TMP4]], [[TMP8]]
; CHECK-NEXT: [[SCEVGEP3:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP9]]
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[SCEVGEP]], [[SCEVGEP3]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SCEVGEP2]], [[SCEVGEP1]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[N_MOD_VF:%.*]] = and i64 [[WIDE_TRIP_COUNT]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[WIDE_TRIP_COUNT]], [[N_MOD_VF]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP12:%.*]] = add nsw i64 [[INDEX]], [[TMP10]]
; CHECK-NEXT: [[TMP13:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP12]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP13]], align 4, !alias.scope [[META39:![0-9]+]]
; CHECK-NEXT: [[TMP14:%.*]] = add nsw i64 [[INDEX]], [[TMP11]]
; CHECK-NEXT: [[TMP15:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP14]]
; CHECK-NEXT: [[WIDE_LOAD4:%.*]] = load <4 x i32>, ptr [[TMP15]], align 4, !alias.scope [[META42:![0-9]+]], !noalias [[META39]]
; CHECK-NEXT: [[TMP16:%.*]] = add nsw <4 x i32> [[WIDE_LOAD4]], [[WIDE_LOAD]]
; CHECK-NEXT: store <4 x i32> [[TMP16]], ptr [[TMP15]], align 4, !alias.scope [[META42]], !noalias [[META39]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP17:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP17]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP44:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_TRIP_COUNT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[INNER_LOOP_EXIT]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER_LOOP]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER_LOOP:.*]]
; CHECK: [[INNER_LOOP]]:
; CHECK-NEXT: [[INNER_IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[INNER_IV_NEXT:%.*]], %[[INNER_LOOP]] ]
; CHECK-NEXT: [[TMP18:%.*]] = add nsw i64 [[INNER_IV]], [[TMP10]]
; CHECK-NEXT: [[ARRAYIDX5_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP18]]
; CHECK-NEXT: [[TMP19:%.*]] = load i32, ptr [[ARRAYIDX5_US]], align 4
; CHECK-NEXT: [[TMP20:%.*]] = add nsw i64 [[INNER_IV]], [[TMP11]]
; CHECK-NEXT: [[ARRAYIDX10_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP20]]
; CHECK-NEXT: [[TMP21:%.*]] = load i32, ptr [[ARRAYIDX10_US]], align 4
; CHECK-NEXT: [[ADD11_US:%.*]] = add nsw i32 [[TMP21]], [[TMP19]]
; CHECK-NEXT: store i32 [[ADD11_US]], ptr [[ARRAYIDX10_US]], align 4
; CHECK-NEXT: [[INNER_IV_NEXT]] = add nuw nsw i64 [[INNER_IV]], 1
; CHECK-NEXT: [[EXITCOND_NOT:%.*]] = icmp eq i64 [[INNER_IV_NEXT]], [[WIDE_TRIP_COUNT]]
; CHECK-NEXT: br i1 [[EXITCOND_NOT]], label %[[INNER_LOOP_EXIT]], label %[[INNER_LOOP]], !llvm.loop [[LOOP45:![0-9]+]]
; CHECK: [[INNER_LOOP_EXIT]]:
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add i64 [[TMP3]], 1
; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i8, ptr [[STR]], i64 [[OUTER_IV_NEXT]]
; CHECK-NEXT: [[TMP22:%.*]] = load i8, ptr [[ARRAYIDX_US]], align 1
; CHECK-NEXT: [[CMP_NOT_US:%.*]] = icmp eq i8 [[TMP22]], 0
; CHECK-NEXT: br i1 [[CMP_NOT_US]], label %[[WHILE_END_LOOPEXIT:.*]], label %[[OUTER_LOOP]]
; CHECK: [[WHILE_END_LOOPEXIT]]:
; CHECK-NEXT: br label %[[WHILE_END]]
; CHECK: [[WHILE_END]]:
; CHECK-NEXT: ret void
;
entry:
%0 = load i8, ptr %str, align 1
%cmp.not23 = icmp ne i8 %0, 0
%cmp221 = icmp sgt i32 %n, 0
%or.cond = and i1 %cmp.not23, %cmp221
br i1 %or.cond, label %outer.loop.preheader, label %while.end
outer.loop.preheader:
%add6 = add nuw nsw i32 %n, 1
%1 = zext i32 %n to i64
%2 = zext i32 %add6 to i64
%wide.trip.count = zext i32 %n to i64
br label %outer.loop
outer.loop:
%outer.iv = phi i64 [ 0, %outer.loop.preheader ], [ %outer.iv.next, %inner.loop.exit ]
%3 = mul nsw i64 %outer.iv, %1
%4 = mul nsw i64 %outer.iv, %2
br label %inner.loop
inner.loop:
%inner.iv = phi i64 [ 0, %outer.loop ], [ %inner.iv.next, %inner.loop ]
%5 = add nsw i64 %inner.iv, %3
%arrayidx5.us = getelementptr inbounds i32, ptr %src, i64 %5
%6 = load i32, ptr %arrayidx5.us, align 4
%7 = add nsw i64 %inner.iv, %4
%arrayidx10.us = getelementptr inbounds i32, ptr %dst, i64 %7
%8 = load i32, ptr %arrayidx10.us, align 4
%add11.us = add nsw i32 %8, %6
store i32 %add11.us, ptr %arrayidx10.us, align 4
%inner.iv.next = add nuw nsw i64 %inner.iv, 1
%exitcond.not = icmp eq i64 %inner.iv.next, %wide.trip.count
br i1 %exitcond.not, label %inner.loop.exit, label %inner.loop
inner.loop.exit:
%outer.iv.next = add i64 %outer.iv, 1
%arrayidx.us = getelementptr inbounds i8, ptr %str, i64 %outer.iv.next
%9 = load i8, ptr %arrayidx.us, align 1
%cmp.not.us = icmp eq i8 %9, 0
br i1 %cmp.not.us, label %while.end, label %outer.loop
while.end:
ret void
}
; Equivalent example in C:
; void decreasing_inner_iv(int32_t *dst, int32_t *src, int stride1, int stride2, int m, int n) {
; for (int i = 0; i < m; i++) {
; for (int j = n; j >= 0; j--) {
; dst[(i * stride1) + j] += src[(i * stride2) + j];
; }
; }
; }
; Inner IV is decreasing, but this isn't a problem and we can still expand the
; runtime checks correctly to cover the whole loop.
; DEBUG-LABEL: 'decreasing_inner_iv'
; DEBUG: LAA: Found an analyzable loop: inner.loop
; DEBUG: LAA: Adding RT check for range:
; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting
; DEBUG-NEXT: LAA: ... but need to check stride is positive: (4 * (sext i32 %stride1 to i64))<nsw>
; 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)
; DEBUG-NEXT: LAA: Adding RT check for range:
; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting
; DEBUG-NEXT: LAA: ... but need to check stride is positive: (4 * (sext i32 %stride2 to i64))<nsw>
; 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)
define 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) {
; CHECK-LABEL: define void @decreasing_inner_iv(
; 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:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*:]]
; CHECK-NEXT: [[CMP20:%.*]] = icmp sgt i32 [[M]], 0
; CHECK-NEXT: [[CMP218:%.*]] = icmp sgt i32 [[N]], -1
; CHECK-NEXT: [[OR_COND:%.*]] = and i1 [[CMP20]], [[CMP218]]
; CHECK-NEXT: br i1 [[OR_COND]], label %[[OUTER_LOOP_PRE:.*]], label %[[EXIT:.*]]
; CHECK: [[OUTER_LOOP_PRE]]:
; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[N]] to i64
; CHECK-NEXT: [[TMP1:%.*]] = sext i32 [[STRIDE2]] to i64
; CHECK-NEXT: [[TMP2:%.*]] = sext i32 [[STRIDE1]] to i64
; CHECK-NEXT: [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[M]] to i64
; CHECK-NEXT: [[TMP14:%.*]] = shl nsw i64 [[TMP1]], 2
; CHECK-NEXT: [[TMP9:%.*]] = shl nsw i64 [[TMP2]], 2
; CHECK-NEXT: [[TMP3:%.*]] = add nsw i64 [[WIDE_TRIP_COUNT]], -1
; CHECK-NEXT: [[TMP4:%.*]] = mul i64 [[TMP3]], [[TMP1]]
; CHECK-NEXT: [[TMP5:%.*]] = shl i64 [[TMP4]], 2
; CHECK-NEXT: [[TMP6:%.*]] = shl nuw nsw i64 [[TMP0]], 2
; CHECK-NEXT: [[TMP7:%.*]] = add i64 [[TMP5]], [[TMP6]]
; CHECK-NEXT: [[TMP8:%.*]] = add i64 [[TMP7]], 4
; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP8]]
; CHECK-NEXT: [[TMP10:%.*]] = mul i64 [[TMP3]], [[TMP2]]
; CHECK-NEXT: [[TMP11:%.*]] = shl i64 [[TMP10]], 2
; CHECK-NEXT: [[TMP12:%.*]] = add i64 [[TMP11]], [[TMP6]]
; CHECK-NEXT: [[TMP13:%.*]] = add i64 [[TMP12]], 4
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP13]]
; CHECK-NEXT: br label %[[OUTER_LOOP:.*]]
; CHECK: [[OUTER_LOOP]]:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, %[[OUTER_LOOP_PRE]] ], [ [[OUTER_IV_NEXT:%.*]], %[[INNER_LOOP_EXIT:.*]] ]
; CHECK-NEXT: [[TMP15:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP1]]
; CHECK-NEXT: [[TMP16:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP2]]
; CHECK-NEXT: [[TMP17:%.*]] = add nuw nsw i64 [[TMP0]], 1
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[TMP17]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP1]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: [[STRIDE_CHECK:%.*]] = icmp slt i64 [[TMP9]], 0
; CHECK-NEXT: [[TMP18:%.*]] = or i1 [[FOUND_CONFLICT]], [[STRIDE_CHECK]]
; CHECK-NEXT: [[STRIDE_CHECK2:%.*]] = icmp slt i64 [[TMP14]], 0
; CHECK-NEXT: [[TMP19:%.*]] = or i1 [[TMP18]], [[STRIDE_CHECK2]]
; CHECK-NEXT: br i1 [[TMP19]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[N_MOD_VF:%.*]] = and i64 [[TMP17]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[TMP17]], [[N_MOD_VF]]
; CHECK-NEXT: [[TMP20:%.*]] = sub i64 [[TMP0]], [[N_VEC]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP21:%.*]] = sub i64 [[TMP0]], [[INDEX]]
; CHECK-NEXT: [[TMP22:%.*]] = add nsw i64 [[TMP21]], [[TMP15]]
; CHECK-NEXT: [[TMP23:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP22]]
; CHECK-NEXT: [[TMP27:%.*]] = getelementptr inbounds i8, ptr [[TMP23]], i64 -12
; CHECK-NEXT: [[REVERSE:%.*]] = load <4 x i32>, ptr [[TMP27]], align 4, !alias.scope [[META46:![0-9]+]]
; CHECK-NEXT: [[TMP25:%.*]] = add nsw i64 [[TMP21]], [[TMP16]]
; CHECK-NEXT: [[TMP26:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP25]]
; CHECK-NEXT: [[TMP34:%.*]] = getelementptr inbounds i8, ptr [[TMP26]], i64 -12
; CHECK-NEXT: [[REVERSE4:%.*]] = load <4 x i32>, ptr [[TMP34]], align 4, !alias.scope [[META49:![0-9]+]], !noalias [[META46]]
; CHECK-NEXT: [[TMP28:%.*]] = add nsw <4 x i32> [[REVERSE4]], [[REVERSE]]
; CHECK-NEXT: store <4 x i32> [[TMP28]], ptr [[TMP34]], align 4, !alias.scope [[META49]], !noalias [[META46]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP29:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP29]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP51:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[TMP17]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[INNER_LOOP_EXIT]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[TMP20]], %[[MIDDLE_BLOCK]] ], [ [[TMP0]], %[[OUTER_LOOP]] ], [ [[TMP0]], %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER_LOOP:.*]]
; CHECK: [[INNER_LOOP]]:
; CHECK-NEXT: [[INNER_IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[INNER_IV_NEXT:%.*]], %[[INNER_LOOP]] ]
; CHECK-NEXT: [[TMP30:%.*]] = add nsw i64 [[INNER_IV]], [[TMP15]]
; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP30]]
; CHECK-NEXT: [[TMP31:%.*]] = load i32, ptr [[ARRAYIDX_US]], align 4
; CHECK-NEXT: [[TMP32:%.*]] = add nsw i64 [[INNER_IV]], [[TMP16]]
; CHECK-NEXT: [[ARRAYIDX8_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP32]]
; CHECK-NEXT: [[TMP33:%.*]] = load i32, ptr [[ARRAYIDX8_US]], align 4
; CHECK-NEXT: [[ADD9_US:%.*]] = add nsw i32 [[TMP33]], [[TMP31]]
; CHECK-NEXT: store i32 [[ADD9_US]], ptr [[ARRAYIDX8_US]], align 4
; CHECK-NEXT: [[INNER_IV_NEXT]] = add nsw i64 [[INNER_IV]], -1
; CHECK-NEXT: [[CMP2_US:%.*]] = icmp sgt i64 [[INNER_IV]], 0
; CHECK-NEXT: br i1 [[CMP2_US]], label %[[INNER_LOOP]], label %[[INNER_LOOP_EXIT]], !llvm.loop [[LOOP52:![0-9]+]]
; CHECK: [[INNER_LOOP_EXIT]]:
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nuw nsw i64 [[OUTER_IV]], 1
; CHECK-NEXT: [[EXITCOND_NOT:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[WIDE_TRIP_COUNT]]
; CHECK-NEXT: br i1 [[EXITCOND_NOT]], label %[[OUTER_LOOP_EXIT:.*]], label %[[OUTER_LOOP]]
; CHECK: [[OUTER_LOOP_EXIT]]:
; CHECK-NEXT: br label %[[EXIT]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
%cmp20 = icmp sgt i32 %m, 0
%cmp218 = icmp sgt i32 %n, -1
%or.cond = and i1 %cmp20, %cmp218
br i1 %or.cond, label %outer.loop.pre, label %exit
outer.loop.pre:
%0 = zext i32 %n to i64
%1 = sext i32 %stride2 to i64
%2 = sext i32 %stride1 to i64
%wide.trip.count = zext i32 %m to i64
br label %outer.loop
outer.loop:
%outer.iv = phi i64 [ 0, %outer.loop.pre ], [ %outer.iv.next, %inner.loop.exit ]
%3 = mul nsw i64 %outer.iv, %1
%4 = mul nsw i64 %outer.iv, %2
br label %inner.loop
inner.loop:
%inner.iv = phi i64 [ %0, %outer.loop ], [ %inner.iv.next, %inner.loop ]
%5 = add nsw i64 %inner.iv, %3
%arrayidx.us = getelementptr inbounds i32, ptr %src, i64 %5
%6 = load i32, ptr %arrayidx.us, align 4
%7 = add nsw i64 %inner.iv, %4
%arrayidx8.us = getelementptr inbounds i32, ptr %dst, i64 %7
%8 = load i32, ptr %arrayidx8.us, align 4
%add9.us = add nsw i32 %8, %6
store i32 %add9.us, ptr %arrayidx8.us, align 4
%inner.iv.next = add nsw i64 %inner.iv, -1
%cmp2.us = icmp sgt i64 %inner.iv, 0
br i1 %cmp2.us, label %inner.loop, label %inner.loop.exit
inner.loop.exit:
%outer.iv.next = add nuw nsw i64 %outer.iv, 1
%exitcond.not = icmp eq i64 %outer.iv.next, %wide.trip.count
br i1 %exitcond.not, label %outer.loop.exit, label %outer.loop
outer.loop.exit:
br label %exit
exit:
ret void
}
; Equivalent example in C:
; void decreasing_outer_iv(int32_t *dst, int32_t *src, int stride1, int stride2, int m, int n) {
; for (int i = m - 1; i >= 0; i--) {
; for (int j = 0; j <= n; j++) {
; dst[(i * stride1) + j] += src[(i * stride2) + j];
; }
; }
; }
; Outer IV is decreasing, but the direction of memory accesses also depends
; upon the signedness of stride1.
; DEBUG-LABEL: 'decreasing_outer_iv'
; DEBUG: LAA: Found an analyzable loop: inner.loop
; DEBUG: LAA: Adding RT check for range:
; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting
; DEBUG-NEXT: LAA: ... but need to check stride is positive: (-4 * (sext i32 %stride1 to i64))<nsw>
; 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)
; DEBUG-NEXT: LAA: Adding RT check for range:
; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting
; DEBUG-NEXT: LAA: ... but need to check stride is positive: (-4 * (sext i32 %stride2 to i64))<nsw>
; 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)
define 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) {
; CHECK-LABEL: define void @decreasing_outer_iv(
; 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:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*:]]
; CHECK-NEXT: [[CMP21:%.*]] = icmp slt i32 [[M]], 1
; CHECK-NEXT: [[CMP2_NOT18:%.*]] = icmp slt i32 [[N]], 0
; CHECK-NEXT: [[OR_COND:%.*]] = or i1 [[CMP21]], [[CMP2_NOT18]]
; CHECK-NEXT: br i1 [[OR_COND]], label %[[EXIT:.*]], label %[[OUTER_LOOP_PRE:.*]]
; CHECK: [[OUTER_LOOP_PRE]]:
; CHECK-NEXT: [[TMP0:%.*]] = add nuw i32 [[N]], 1
; CHECK-NEXT: [[TMP1:%.*]] = zext i32 [[M]] to i64
; CHECK-NEXT: [[TMP2:%.*]] = sext i32 [[STRIDE1]] to i64
; CHECK-NEXT: [[TMP3:%.*]] = sext i32 [[STRIDE2]] to i64
; CHECK-NEXT: [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[TMP0]] to i64
; CHECK-NEXT: [[TMP14:%.*]] = mul nsw i64 [[TMP3]], -4
; CHECK-NEXT: [[TMP9:%.*]] = mul nsw i64 [[TMP2]], -4
; CHECK-NEXT: [[TMP6:%.*]] = shl nsw i64 [[TMP3]], 2
; CHECK-NEXT: [[TMP7:%.*]] = shl nuw nsw i64 [[WIDE_TRIP_COUNT]], 2
; CHECK-NEXT: [[TMP8:%.*]] = add i64 [[TMP6]], [[TMP7]]
; CHECK-NEXT: [[SCEVGEP3:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP8]]
; CHECK-NEXT: [[TMP10:%.*]] = mul i64 [[TMP3]], [[TMP1]]
; CHECK-NEXT: [[TMP11:%.*]] = shl i64 [[TMP10]], 2
; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP11]]
; CHECK-NEXT: [[TMP12:%.*]] = shl nsw i64 [[TMP2]], 2
; CHECK-NEXT: [[TMP13:%.*]] = add i64 [[TMP12]], [[TMP7]]
; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP13]]
; CHECK-NEXT: [[TMP29:%.*]] = mul i64 [[TMP2]], [[TMP1]]
; CHECK-NEXT: [[TMP30:%.*]] = shl i64 [[TMP29]], 2
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP30]]
; CHECK-NEXT: br label %[[OUTER_LOOP:.*]]
; CHECK: [[OUTER_LOOP]]:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ [[TMP1]], %[[OUTER_LOOP_PRE]] ], [ [[OUTER_IV_NEXT:%.*]], %[[INNER_LOOP_EXIT:.*]] ]
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nsw i64 [[OUTER_IV]], -1
; CHECK-NEXT: [[TMP15:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP3]]
; CHECK-NEXT: [[TMP16:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP2]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_TRIP_COUNT]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[SCEVGEP]], [[SCEVGEP3]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SCEVGEP2]], [[SCEVGEP1]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: [[STRIDE_CHECK:%.*]] = icmp slt i64 [[TMP9]], 0
; CHECK-NEXT: [[TMP17:%.*]] = or i1 [[FOUND_CONFLICT]], [[STRIDE_CHECK]]
; CHECK-NEXT: [[STRIDE_CHECK4:%.*]] = icmp slt i64 [[TMP14]], 0
; CHECK-NEXT: [[TMP18:%.*]] = or i1 [[TMP17]], [[STRIDE_CHECK4]]
; CHECK-NEXT: br i1 [[TMP18]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[N_MOD_VF:%.*]] = and i64 [[WIDE_TRIP_COUNT]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[WIDE_TRIP_COUNT]], [[N_MOD_VF]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP19:%.*]] = add nsw i64 [[INDEX]], [[TMP15]]
; CHECK-NEXT: [[TMP20:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP19]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP20]], align 4, !alias.scope [[META53:![0-9]+]]
; CHECK-NEXT: [[TMP21:%.*]] = add nsw i64 [[INDEX]], [[TMP16]]
; CHECK-NEXT: [[TMP22:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP21]]
; CHECK-NEXT: [[WIDE_LOAD5:%.*]] = load <4 x i32>, ptr [[TMP22]], align 4, !alias.scope [[META56:![0-9]+]], !noalias [[META53]]
; CHECK-NEXT: [[TMP23:%.*]] = add nsw <4 x i32> [[WIDE_LOAD5]], [[WIDE_LOAD]]
; CHECK-NEXT: store <4 x i32> [[TMP23]], ptr [[TMP22]], align 4, !alias.scope [[META56]], !noalias [[META53]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP24:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP24]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP58:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_TRIP_COUNT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[INNER_LOOP_EXIT]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER_LOOP]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER_LOOP:.*]]
; CHECK: [[INNER_LOOP]]:
; CHECK-NEXT: [[INNER_IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[INNER_IV_NEXT:%.*]], %[[INNER_LOOP]] ]
; CHECK-NEXT: [[TMP25:%.*]] = add nsw i64 [[INNER_IV]], [[TMP15]]
; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP25]]
; CHECK-NEXT: [[TMP26:%.*]] = load i32, ptr [[ARRAYIDX]], align 4
; CHECK-NEXT: [[TMP27:%.*]] = add nsw i64 [[INNER_IV]], [[TMP16]]
; CHECK-NEXT: [[ARRAYIDX8:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP27]]
; CHECK-NEXT: [[TMP28:%.*]] = load i32, ptr [[ARRAYIDX8]], align 4
; CHECK-NEXT: [[ADD9:%.*]] = add nsw i32 [[TMP28]], [[TMP26]]
; CHECK-NEXT: store i32 [[ADD9]], ptr [[ARRAYIDX8]], align 4
; CHECK-NEXT: [[INNER_IV_NEXT]] = add nuw nsw i64 [[INNER_IV]], 1
; CHECK-NEXT: [[EXITCOND_NOT:%.*]] = icmp eq i64 [[INNER_IV_NEXT]], [[WIDE_TRIP_COUNT]]
; CHECK-NEXT: br i1 [[EXITCOND_NOT]], label %[[INNER_LOOP_EXIT]], label %[[INNER_LOOP]], !llvm.loop [[LOOP59:![0-9]+]]
; CHECK: [[INNER_LOOP_EXIT]]:
; CHECK-NEXT: [[CMP:%.*]] = icmp sgt i64 [[OUTER_IV]], 1
; CHECK-NEXT: br i1 [[CMP]], label %[[OUTER_LOOP]], label %[[OUTER_LOOP_EXIT:.*]]
; CHECK: [[OUTER_LOOP_EXIT]]:
; CHECK-NEXT: br label %[[EXIT]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
%cmp21 = icmp slt i32 %m, 1
%cmp2.not18 = icmp slt i32 %n, 0
%or.cond = or i1 %cmp21, %cmp2.not18
br i1 %or.cond, label %exit, label %outer.loop.pre
outer.loop.pre:
%0 = add nuw i32 %n, 1
%1 = zext i32 %m to i64
%2 = sext i32 %stride1 to i64
%3 = sext i32 %stride2 to i64
%wide.trip.count = zext i32 %0 to i64
br label %outer.loop
outer.loop:
%outer.iv = phi i64 [ %1, %outer.loop.pre ], [ %outer.iv.next, %inner.loop.exit ]
%outer.iv.next = add nsw i64 %outer.iv, -1
%4 = mul nsw i64 %outer.iv, %3
%5 = mul nsw i64 %outer.iv, %2
br label %inner.loop
inner.loop:
%inner.iv = phi i64 [ 0, %outer.loop ], [ %inner.iv.next, %inner.loop ]
%6 = add nsw i64 %inner.iv, %4
%arrayidx = getelementptr inbounds i32, ptr %src, i64 %6
%7 = load i32, ptr %arrayidx, align 4
%8 = add nsw i64 %inner.iv, %5
%arrayidx8 = getelementptr inbounds i32, ptr %dst, i64 %8
%9 = load i32, ptr %arrayidx8, align 4
%add9 = add nsw i32 %9, %7
store i32 %add9, ptr %arrayidx8, align 4
%inner.iv.next = add nuw nsw i64 %inner.iv, 1
%exitcond.not = icmp eq i64 %inner.iv.next, %wide.trip.count
br i1 %exitcond.not, label %inner.loop.exit, label %inner.loop
inner.loop.exit:
%cmp = icmp sgt i64 %outer.iv, 1
br i1 %cmp, label %outer.loop, label %outer.loop.exit
outer.loop.exit:
br label %exit
exit:
ret void
}
; Equivalent example in C:
; void foo(int32_t *dst, int32_t *src, int stride1, int stride2, int m, int n) {
; for (int i = 0; i < m; i++) {
; for (int j = 0; j < n; j++) {
; dst[(i * (n + 1)) + (j * stride1)] += src[(i * n) + (j * stride2)];
; }
; }
; }
; DEBUG-LABEL: 'unknown_inner_stride'
; DEBUG: LAA: Found an analyzable loop: inner.loop
; DEBUG: LAA: Adding RT check for range:
; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting
; 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)
; DEBUG-NEXT: LAA: Adding RT check for range:
; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting
; DEBUG-NEXT: Start: %src End: ((4 * (zext i32 %m to i64) * (zext i32 %n to i64)) + %src)
define 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) {
; CHECK-LABEL: define void @unknown_inner_stride(
; 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:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*:]]
; CHECK-NEXT: [[CMP26:%.*]] = icmp sgt i32 [[M]], 0
; CHECK-NEXT: [[CMP224:%.*]] = icmp sgt i32 [[N]], 0
; CHECK-NEXT: [[OR_COND:%.*]] = and i1 [[CMP26]], [[CMP224]]
; CHECK-NEXT: br i1 [[OR_COND]], label %[[OUTER_LOOP_PREHEADER:.*]], label %[[EXIT:.*]]
; CHECK: [[OUTER_LOOP_PREHEADER]]:
; CHECK-NEXT: [[ADD6:%.*]] = add nuw nsw i32 [[N]], 1
; CHECK-NEXT: [[TMP0:%.*]] = sext i32 [[STRIDE2]] to i64
; CHECK-NEXT: [[TMP1:%.*]] = sext i32 [[STRIDE1]] to i64
; CHECK-NEXT: [[TMP2:%.*]] = zext i32 [[N]] to i64
; CHECK-NEXT: [[TMP3:%.*]] = zext i32 [[ADD6]] to i64
; CHECK-NEXT: [[WIDE_TRIP_COUNT39:%.*]] = zext i32 [[M]] to i64
; CHECK-NEXT: [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[N]] to i64
; CHECK-NEXT: [[TMP9:%.*]] = mul i64 [[WIDE_TRIP_COUNT]], [[WIDE_TRIP_COUNT39]]
; CHECK-NEXT: [[TMP10:%.*]] = shl i64 [[TMP9]], 2
; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP10]]
; CHECK-NEXT: [[TMP4:%.*]] = add nsw i64 [[WIDE_TRIP_COUNT39]], -1
; CHECK-NEXT: [[TMP5:%.*]] = mul i64 [[TMP4]], [[TMP3]]
; CHECK-NEXT: [[TMP6:%.*]] = shl i64 [[TMP5]], 2
; CHECK-NEXT: [[TMP7:%.*]] = shl nuw nsw i64 [[WIDE_TRIP_COUNT]], 2
; CHECK-NEXT: [[TMP8:%.*]] = add i64 [[TMP6]], [[TMP7]]
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP8]]
; CHECK-NEXT: br label %[[OUTER_LOOP:.*]]
; CHECK: [[OUTER_LOOP]]:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, %[[OUTER_LOOP_PREHEADER]] ], [ [[OUTER_IV_NEXT:%.*]], %[[INNER_LOOP_EXIT:.*]] ]
; CHECK-NEXT: [[TMP11:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP2]]
; CHECK-NEXT: [[TMP12:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP3]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[WIDE_TRIP_COUNT]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_SCEVCHECK:.*]]
; CHECK: [[VECTOR_SCEVCHECK]]:
; CHECK-NEXT: [[IDENT_CHECK:%.*]] = icmp ne i32 [[STRIDE1]], 1
; CHECK-NEXT: [[IDENT_CHECK1:%.*]] = icmp ne i32 [[STRIDE2]], 1
; CHECK-NEXT: [[TMP13:%.*]] = or i1 [[IDENT_CHECK]], [[IDENT_CHECK1]]
; CHECK-NEXT: br i1 [[TMP13]], label %[[SCALAR_PH]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP2]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[N_MOD_VF:%.*]] = and i64 [[WIDE_TRIP_COUNT]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[WIDE_TRIP_COUNT]], [[N_MOD_VF]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP14:%.*]] = add nsw i64 [[INDEX]], [[TMP11]]
; CHECK-NEXT: [[TMP15:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP14]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP15]], align 4, !alias.scope [[META60:![0-9]+]]
; CHECK-NEXT: [[TMP16:%.*]] = add nsw i64 [[INDEX]], [[TMP12]]
; CHECK-NEXT: [[TMP17:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP16]]
; CHECK-NEXT: [[WIDE_LOAD3:%.*]] = load <4 x i32>, ptr [[TMP17]], align 4, !alias.scope [[META63:![0-9]+]], !noalias [[META60]]
; CHECK-NEXT: [[TMP18:%.*]] = add nsw <4 x i32> [[WIDE_LOAD3]], [[WIDE_LOAD]]
; CHECK-NEXT: store <4 x i32> [[TMP18]], ptr [[TMP17]], align 4, !alias.scope [[META63]], !noalias [[META60]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP19:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP19]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP65:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[WIDE_TRIP_COUNT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[INNER_LOOP_EXIT]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER_LOOP]] ], [ 0, %[[VECTOR_SCEVCHECK]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER_LOOP:.*]]
; CHECK: [[INNER_LOOP]]:
; CHECK-NEXT: [[INNER_IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[INNER_IV_NEXT:%.*]], %[[INNER_LOOP]] ]
; CHECK-NEXT: [[TMP20:%.*]] = mul nsw i64 [[INNER_IV]], [[TMP0]]
; CHECK-NEXT: [[TMP21:%.*]] = add nsw i64 [[TMP20]], [[TMP11]]
; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP21]]
; CHECK-NEXT: [[TMP22:%.*]] = load i32, ptr [[ARRAYIDX_US]], align 4
; CHECK-NEXT: [[TMP23:%.*]] = mul nsw i64 [[INNER_IV]], [[TMP1]]
; CHECK-NEXT: [[TMP24:%.*]] = add nsw i64 [[TMP23]], [[TMP12]]
; CHECK-NEXT: [[ARRAYIDX11_US:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP24]]
; CHECK-NEXT: [[TMP25:%.*]] = load i32, ptr [[ARRAYIDX11_US]], align 4
; CHECK-NEXT: [[ADD12_US:%.*]] = add nsw i32 [[TMP25]], [[TMP22]]
; CHECK-NEXT: store i32 [[ADD12_US]], ptr [[ARRAYIDX11_US]], align 4
; CHECK-NEXT: [[INNER_IV_NEXT]] = add nuw nsw i64 [[INNER_IV]], 1
; CHECK-NEXT: [[EXITCOND_NOT:%.*]] = icmp eq i64 [[INNER_IV_NEXT]], [[WIDE_TRIP_COUNT]]
; CHECK-NEXT: br i1 [[EXITCOND_NOT]], label %[[INNER_LOOP_EXIT]], label %[[INNER_LOOP]], !llvm.loop [[LOOP66:![0-9]+]]
; CHECK: [[INNER_LOOP_EXIT]]:
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nuw nsw i64 [[OUTER_IV]], 1
; CHECK-NEXT: [[EXITCOND40_NOT:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[WIDE_TRIP_COUNT39]]
; CHECK-NEXT: br i1 [[EXITCOND40_NOT]], label %[[EXIT_LOOPEXIT:.*]], label %[[OUTER_LOOP]]
; CHECK: [[EXIT_LOOPEXIT]]:
; CHECK-NEXT: br label %[[EXIT]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
%cmp26 = icmp sgt i32 %m, 0
%cmp224 = icmp sgt i32 %n, 0
%or.cond = and i1 %cmp26, %cmp224
br i1 %or.cond, label %outer.loop.preheader, label %exit
outer.loop.preheader:
%add6 = add nuw nsw i32 %n, 1
%0 = sext i32 %stride2 to i64
%1 = sext i32 %stride1 to i64
%2 = zext i32 %n to i64
%3 = zext i32 %add6 to i64
%wide.trip.count39 = zext i32 %m to i64
%wide.trip.count = zext i32 %n to i64
br label %outer.loop
outer.loop:
%outer.iv = phi i64 [ 0, %outer.loop.preheader ], [ %outer.iv.next, %inner.loop.exit ]
%4 = mul nsw i64 %outer.iv, %2
%5 = mul nsw i64 %outer.iv, %3
br label %inner.loop
inner.loop:
%inner.iv = phi i64 [ 0, %outer.loop ], [ %inner.iv.next, %inner.loop ]
%6 = mul nsw i64 %inner.iv, %0
%7 = add nsw i64 %6, %4
%arrayidx.us = getelementptr inbounds i32, ptr %src, i64 %7
%8 = load i32, ptr %arrayidx.us, align 4
%9 = mul nsw i64 %inner.iv, %1
%10 = add nsw i64 %9, %5
%arrayidx11.us = getelementptr inbounds i32, ptr %dst, i64 %10
%11 = load i32, ptr %arrayidx11.us, align 4
%add12.us = add nsw i32 %11, %8
store i32 %add12.us, ptr %arrayidx11.us, align 4
%inner.iv.next = add nuw nsw i64 %inner.iv, 1
%exitcond.not = icmp eq i64 %inner.iv.next, %wide.trip.count
br i1 %exitcond.not, label %inner.loop.exit, label %inner.loop
inner.loop.exit:
%outer.iv.next = add nuw nsw i64 %outer.iv, 1
%exitcond40.not = icmp eq i64 %outer.iv.next, %wide.trip.count39
br i1 %exitcond40.not, label %exit, label %outer.loop
exit:
ret void
}
; Test case where the AddRec for the pointers in the inner loop have the AddRec
; of the outer loop as start value. It is sufficient to subtract the start
; values (%dst, %src) of the outer AddRecs.
define 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) {
; CHECK-LABEL: define void @nested_loop_start_of_inner_ptr_addrec_is_same_outer_addrec(
; CHECK-SAME: ptr noundef captures(none) [[DST:%.*]], ptr noundef readonly captures(none) [[SRC:%.*]], i64 noundef [[M:%.*]], i64 noundef [[N:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[SRC2:%.*]] = ptrtoaddr ptr [[SRC]] to i64
; CHECK-NEXT: [[DST1:%.*]] = ptrtoaddr ptr [[DST]] to i64
; CHECK-NEXT: [[TMP0:%.*]] = sub i64 [[DST1]], [[SRC2]]
; CHECK-NEXT: br label %[[OUTER_LOOP:.*]]
; CHECK: [[OUTER_LOOP]]:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[OUTER_IV_NEXT:%.*]], %[[INNER_EXIT:.*]] ]
; CHECK-NEXT: [[MUL:%.*]] = mul nsw i64 [[OUTER_IV]], [[N]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[N]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[TMP6:%.*]] = sub i64 [[TMP0]], 1
; CHECK-NEXT: [[DIFF_CHECK:%.*]] = icmp ult i64 [[TMP6]], 15
; CHECK-NEXT: br i1 [[DIFF_CHECK]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[N_MOD_VF:%.*]] = and i64 [[N]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[N]], [[N_MOD_VF]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP1:%.*]] = add nuw nsw i64 [[INDEX]], [[MUL]]
; CHECK-NEXT: [[TMP2:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP1]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP2]], align 4
; CHECK-NEXT: [[TMP3:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP1]]
; CHECK-NEXT: [[TMP4:%.*]] = add nsw <4 x i32> [[WIDE_LOAD]], splat (i32 10)
; CHECK-NEXT: store <4 x i32> [[TMP4]], ptr [[TMP3]], align 4
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP5:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP5]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP67:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[N]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[INNER_EXIT]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER_LOOP]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER_LOOP:.*]]
; CHECK: [[INNER_LOOP]]:
; CHECK-NEXT: [[IV_INNER:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_INNER_NEXT:%.*]], %[[INNER_LOOP]] ]
; CHECK-NEXT: [[IDX:%.*]] = add nuw nsw i64 [[IV_INNER]], [[MUL]]
; CHECK-NEXT: [[GEP_SRC:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[IDX]]
; CHECK-NEXT: [[L:%.*]] = load i32, ptr [[GEP_SRC]], align 4
; CHECK-NEXT: [[GEP_DST:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IDX]]
; CHECK-NEXT: [[ADD:%.*]] = add nsw i32 [[L]], 10
; CHECK-NEXT: store i32 [[ADD]], ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[IV_INNER_NEXT]] = add nuw nsw i64 [[IV_INNER]], 1
; CHECK-NEXT: [[INNER_EXIT_COND:%.*]] = icmp eq i64 [[IV_INNER_NEXT]], [[N]]
; CHECK-NEXT: br i1 [[INNER_EXIT_COND]], label %[[INNER_EXIT]], label %[[INNER_LOOP]], !llvm.loop [[LOOP68:![0-9]+]]
; CHECK: [[INNER_EXIT]]:
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nuw nsw i64 [[OUTER_IV]], 1
; CHECK-NEXT: [[OUTER_EXIT_COND:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[M]]
; CHECK-NEXT: br i1 [[OUTER_EXIT_COND]], label %[[OUTER_EXIT:.*]], label %[[OUTER_LOOP]]
; CHECK: [[OUTER_EXIT]]:
; CHECK-NEXT: ret void
;
entry:
br label %outer.loop
outer.loop:
%outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %inner.exit ]
%mul = mul nsw i64 %outer.iv, %n
br label %inner.loop
inner.loop:
%iv.inner = phi i64 [ 0, %outer.loop ], [ %iv.inner.next, %inner.loop ]
%idx = add nuw nsw i64 %iv.inner, %mul
%gep.src = getelementptr inbounds i32, ptr %src, i64 %idx
%l = load i32, ptr %gep.src, align 4
%gep.dst = getelementptr inbounds i32, ptr %dst, i64 %idx
%add = add nsw i32 %l, 10
store i32 %add, ptr %gep.dst, align 4
%iv.inner.next = add nuw nsw i64 %iv.inner, 1
%inner.exit.cond = icmp eq i64 %iv.inner.next, %n
br i1 %inner.exit.cond, label %inner.exit, label %inner.loop
inner.exit:
%outer.iv.next = add nuw nsw i64 %outer.iv, 1
%outer.exit.cond = icmp eq i64 %outer.iv.next, %m
br i1 %outer.exit.cond, label %outer.exit, label %outer.loop
outer.exit:
ret void
}
; The stride for the access in the inner loop is known to be non-negative via
; loop guards.
define void @stride_check_known_via_loop_guard(ptr %C, ptr %A, i32 %Acols) {
; CHECK-LABEL: define void @stride_check_known_via_loop_guard(
; CHECK-SAME: ptr [[C:%.*]], ptr [[A:%.*]], i32 [[ACOLS:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*:]]
; CHECK-NEXT: [[PRE_C:%.*]] = icmp ugt i32 [[ACOLS]], 0
; CHECK-NEXT: br i1 [[PRE_C]], label %[[EXIT:.*]], label %[[OUTER_HEADER_PREHEADER:.*]]
; CHECK: [[OUTER_HEADER_PREHEADER]]:
; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[A]], i64 8
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[C]], i64 8000
; CHECK-NEXT: br label %[[OUTER_HEADER:.*]]
; CHECK: [[OUTER_HEADER]]:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ [[OUTER_IV_NEXT:%.*]], %[[OUTER_LATCH:.*]] ], [ 0, %[[OUTER_HEADER_PREHEADER]] ]
; CHECK-NEXT: [[MUL_US:%.*]] = mul i32 [[OUTER_IV]], [[ACOLS]]
; CHECK-NEXT: [[ARRAYIDX_US:%.*]] = getelementptr inbounds double, ptr [[A]], i32 [[MUL_US]]
; CHECK-NEXT: br label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[C]], [[SCEVGEP1]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[A]], [[SCEVGEP]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label %[[SCALAR_PH:.*]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[TMP0:%.*]] = load double, ptr [[ARRAYIDX_US]], align 8, !alias.scope [[META69:![0-9]+]]
; CHECK-NEXT: [[BROADCAST_SPLATINSERT:%.*]] = insertelement <4 x double> poison, double [[TMP0]], i64 0
; CHECK-NEXT: [[BROADCAST_SPLAT:%.*]] = shufflevector <4 x double> [[BROADCAST_SPLATINSERT]], <4 x double> poison, <4 x i32> zeroinitializer
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i32 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds double, ptr [[C]], i32 [[INDEX]]
; CHECK-NEXT: store <4 x double> [[BROADCAST_SPLAT]], ptr [[TMP1]], align 8, !alias.scope [[META72:![0-9]+]], !noalias [[META69]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i32 [[INDEX]], 4
; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i32 [[INDEX_NEXT]], 1000
; CHECK-NEXT: br i1 [[TMP2]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP74:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: br label %[[OUTER_LATCH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: br label %[[INNER:.*]]
; CHECK: [[INNER]]:
; CHECK-NEXT: [[INNER_IV:%.*]] = phi i32 [ 0, %[[SCALAR_PH]] ], [ [[INNER_IV_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[GEP_C:%.*]] = getelementptr inbounds double, ptr [[C]], i32 [[INNER_IV]]
; CHECK-NEXT: [[L:%.*]] = load double, ptr [[ARRAYIDX_US]], align 8
; CHECK-NEXT: store double [[L]], ptr [[GEP_C]], align 8
; CHECK-NEXT: [[INNER_IV_NEXT]] = add i32 [[INNER_IV]], 1
; CHECK-NEXT: [[INNER_C:%.*]] = icmp eq i32 [[INNER_IV_NEXT]], 1000
; CHECK-NEXT: br i1 [[INNER_C]], label %[[OUTER_LATCH]], label %[[INNER]], !llvm.loop [[LOOP75:![0-9]+]]
; CHECK: [[OUTER_LATCH]]:
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add i32 [[OUTER_IV]], 1
; CHECK-NEXT: [[OUTER_C:%.*]] = icmp ult i32 [[OUTER_IV]], 128
; CHECK-NEXT: br i1 [[OUTER_C]], label %[[EXIT_LOOPEXIT:.*]], label %[[OUTER_HEADER]]
; CHECK: [[EXIT_LOOPEXIT]]:
; CHECK-NEXT: br label %[[EXIT]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
%pre.c = icmp ugt i32 %Acols, 0
br i1 %pre.c, label %exit, label %outer.header
outer.header:
%outer.iv = phi i32 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
%mul.us = mul i32 %outer.iv, %Acols
%arrayidx.us = getelementptr inbounds double, ptr %A, i32 %mul.us
br label %inner
inner:
%inner.iv = phi i32 [ 0, %outer.header ], [ %inner.iv.next, %inner ]
%gep.C = getelementptr inbounds double, ptr %C, i32 %inner.iv
%l = load double, ptr %arrayidx.us, align 8
store double %l, ptr %gep.C, align 8
%inner.iv.next = add i32 %inner.iv, 1
%inner.c = icmp eq i32 %inner.iv.next, 1000
br i1 %inner.c, label %outer.latch, label %inner
outer.latch:
%outer.iv.next = add i32 %outer.iv, 1
%outer.c = icmp ult i32 %outer.iv, 128
br i1 %outer.c, label %exit, label %outer.header
exit:
ret void
}
; Equivalent example in C:
; void shared_strides(uint8_t *dst, uint8_t *src1, uint8_t *src2, int stride1,
; int stride2, int m, int n) {
; for (int i = 0; i < m; i++) {
; for (int j = 0; j < n; j++) {
; dst[(i * stride1) + j] = src1[(i * stride2) + j] + src2[(i * stride2) + j];
; }
; }
; }
; We need to check that both stride1 and stride2 aren't negative, but even
; though they're used twice each ([dst, src1], [dst, src2]) we only need to
; check them once.
; DEBUG-LABEL: 'shared_strides'
; DEBUG: LAA: Found an analyzable loop: inner.loop
; DEBUG: LAA: Adding RT check for range:
; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting
; DEBUG-NEXT: LAA: ... but need to check stride is positive: (sext i32 %stride1 to i64)
; DEBUG: LAA: Adding RT check for range:
; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting
; DEBUG-NEXT: LAA: ... but need to check stride is positive: (sext i32 %stride2 to i64)
; DEBUG: LAA: Adding RT check for range:
; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting
; DEBUG-NEXT: LAA: ... but need to check stride is positive: (sext i32 %stride1 to i64)
; DEBUG: LAA: Adding RT check for range:
; DEBUG-NEXT: LAA: Expanded RT check for range to include outer loop in order to permit hoisting
; DEBUG-NEXT: LAA: ... but need to check stride is positive: (sext i32 %stride2 to i64)
define void @shared_strides(ptr noundef %dst, ptr noundef readonly %src1, ptr noundef readonly %src2, i32 noundef %stride1, i32 noundef %stride2, i32 noundef %m, i32 noundef %n) {
; CHECK-LABEL: define void @shared_strides(
; CHECK-SAME: ptr noundef [[DST:%.*]], ptr noundef readonly [[SRC1:%.*]], ptr noundef readonly [[SRC2:%.*]], i32 noundef [[STRIDE1:%.*]], i32 noundef [[STRIDE2:%.*]], i32 noundef [[M:%.*]], i32 noundef [[N:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*:]]
; CHECK-NEXT: [[CMP20:%.*]] = icmp sgt i32 [[M]], 0
; CHECK-NEXT: [[CMP218:%.*]] = icmp sgt i32 [[N]], 0
; CHECK-NEXT: [[OR_COND:%.*]] = and i1 [[CMP20]], [[CMP218]]
; CHECK-NEXT: br i1 [[OR_COND]], label %[[OUTER_LOOP_PRE:.*]], label %[[EXIT:.*]]
; CHECK: [[OUTER_LOOP_PRE]]:
; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[N]] to i64
; CHECK-NEXT: [[TMP1:%.*]] = sext i32 [[STRIDE2]] to i64
; CHECK-NEXT: [[TMP2:%.*]] = sext i32 [[STRIDE1]] to i64
; CHECK-NEXT: [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[M]] to i64
; CHECK-NEXT: [[TMP3:%.*]] = add nsw i64 [[WIDE_TRIP_COUNT]], -1
; CHECK-NEXT: [[TMP4:%.*]] = mul i64 [[TMP3]], [[TMP1]]
; CHECK-NEXT: [[TMP5:%.*]] = add i64 [[TMP4]], [[TMP0]]
; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[SRC2]], i64 [[TMP5]]
; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[SRC1]], i64 [[TMP5]]
; CHECK-NEXT: [[TMP6:%.*]] = mul i64 [[TMP3]], [[TMP2]]
; CHECK-NEXT: [[TMP7:%.*]] = add i64 [[TMP6]], [[TMP0]]
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP7]]
; CHECK-NEXT: br label %[[OUTER_LOOP:.*]]
; CHECK: [[OUTER_LOOP]]:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, %[[OUTER_LOOP_PRE]] ], [ [[OUTER_IV_NEXT:%.*]], %[[INNER_LOOP_EXIT:.*]] ]
; CHECK-NEXT: [[TMP8:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP1]]
; CHECK-NEXT: [[TMP9:%.*]] = mul nsw i64 [[OUTER_IV]], [[TMP2]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[TMP0]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP1]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC1]], [[SCEVGEP]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: [[STRIDE_CHECK:%.*]] = icmp slt i64 [[TMP2]], 0
; CHECK-NEXT: [[TMP10:%.*]] = or i1 [[FOUND_CONFLICT]], [[STRIDE_CHECK]]
; CHECK-NEXT: [[STRIDE_CHECK3:%.*]] = icmp slt i64 [[TMP1]], 0
; CHECK-NEXT: [[TMP11:%.*]] = or i1 [[TMP10]], [[STRIDE_CHECK3]]
; CHECK-NEXT: [[BOUND04:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP2]]
; CHECK-NEXT: [[BOUND15:%.*]] = icmp ult ptr [[SRC2]], [[SCEVGEP]]
; CHECK-NEXT: [[FOUND_CONFLICT6:%.*]] = and i1 [[BOUND04]], [[BOUND15]]
; CHECK-NEXT: [[CONFLICT_RDX:%.*]] = or i1 [[TMP11]], [[FOUND_CONFLICT6]]
; CHECK-NEXT: br i1 [[CONFLICT_RDX]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[TMP12:%.*]] = and i64 [[TMP0]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[TMP0]], [[TMP12]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP13:%.*]] = add nsw i64 [[INDEX]], [[TMP8]]
; CHECK-NEXT: [[TMP14:%.*]] = getelementptr inbounds i8, ptr [[SRC1]], i64 [[TMP13]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i8>, ptr [[TMP14]], align 1, !alias.scope [[META76:![0-9]+]]
; CHECK-NEXT: [[TMP15:%.*]] = getelementptr inbounds i8, ptr [[SRC2]], i64 [[TMP13]]
; CHECK-NEXT: [[WIDE_LOAD7:%.*]] = load <4 x i8>, ptr [[TMP15]], align 1, !alias.scope [[META79:![0-9]+]]
; CHECK-NEXT: [[TMP16:%.*]] = add <4 x i8> [[WIDE_LOAD]], [[WIDE_LOAD7]]
; CHECK-NEXT: [[TMP17:%.*]] = add nsw i64 [[INDEX]], [[TMP9]]
; CHECK-NEXT: [[TMP18:%.*]] = getelementptr inbounds i8, ptr [[DST]], i64 [[TMP17]]
; CHECK-NEXT: store <4 x i8> [[TMP16]], ptr [[TMP18]], align 1, !alias.scope [[META81:![0-9]+]], !noalias [[META83:![0-9]+]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP19:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP19]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP84:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[TMP0]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[INNER_LOOP_EXIT]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER_LOOP]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER_LOOP:.*]]
; CHECK: [[INNER_LOOP]]:
; CHECK-NEXT: [[INNER_IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[INNER_IV_NEXT:%.*]], %[[INNER_LOOP]] ]
; CHECK-NEXT: [[TMP20:%.*]] = add nsw i64 [[INNER_IV]], [[TMP8]]
; CHECK-NEXT: [[ARRAYIDX1:%.*]] = getelementptr inbounds i8, ptr [[SRC1]], i64 [[TMP20]]
; CHECK-NEXT: [[TMP21:%.*]] = load i8, ptr [[ARRAYIDX1]], align 1
; CHECK-NEXT: [[ARRAYIDX2:%.*]] = getelementptr inbounds i8, ptr [[SRC2]], i64 [[TMP20]]
; CHECK-NEXT: [[TMP22:%.*]] = load i8, ptr [[ARRAYIDX2]], align 1
; CHECK-NEXT: [[ADD:%.*]] = add i8 [[TMP21]], [[TMP22]]
; CHECK-NEXT: [[TMP23:%.*]] = add nsw i64 [[INNER_IV]], [[TMP9]]
; CHECK-NEXT: [[ARRAYIDX3:%.*]] = getelementptr inbounds i8, ptr [[DST]], i64 [[TMP23]]
; CHECK-NEXT: store i8 [[ADD]], ptr [[ARRAYIDX3]], align 1
; CHECK-NEXT: [[INNER_IV_NEXT]] = add nuw nsw i64 [[INNER_IV]], 1
; CHECK-NEXT: [[EXITCOND_INNER:%.*]] = icmp eq i64 [[INNER_IV_NEXT]], [[TMP0]]
; CHECK-NEXT: br i1 [[EXITCOND_INNER]], label %[[INNER_LOOP_EXIT]], label %[[INNER_LOOP]], !llvm.loop [[LOOP85:![0-9]+]]
; CHECK: [[INNER_LOOP_EXIT]]:
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nuw nsw i64 [[OUTER_IV]], 1
; CHECK-NEXT: [[EXITCOND_NOT:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[WIDE_TRIP_COUNT]]
; CHECK-NEXT: br i1 [[EXITCOND_NOT]], label %[[OUTER_LOOP_EXIT:.*]], label %[[OUTER_LOOP]]
; CHECK: [[OUTER_LOOP_EXIT]]:
; CHECK-NEXT: br label %[[EXIT]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
%cmp20 = icmp sgt i32 %m, 0
%cmp218 = icmp sgt i32 %n, 0
%or.cond = and i1 %cmp20, %cmp218
br i1 %or.cond, label %outer.loop.pre, label %exit
outer.loop.pre:
%0 = zext i32 %n to i64
%1 = sext i32 %stride2 to i64
%2 = sext i32 %stride1 to i64
%wide.trip.count = zext i32 %m to i64
br label %outer.loop
outer.loop:
%outer.iv = phi i64 [ 0, %outer.loop.pre ], [ %outer.iv.next, %inner.loop.exit ]
%3 = mul nsw i64 %outer.iv, %1
%4 = mul nsw i64 %outer.iv, %2
br label %inner.loop
inner.loop:
%inner.iv = phi i64 [ 0, %outer.loop ], [ %inner.iv.next, %inner.loop ]
%5 = add nsw i64 %inner.iv, %3
%arrayidx1 = getelementptr inbounds i8, ptr %src1, i64 %5
%6 = load i8, ptr %arrayidx1, align 1
%arrayidx2 = getelementptr inbounds i8, ptr %src2, i64 %5
%7 = load i8, ptr %arrayidx2, align 1
%add = add i8 %6, %7
%8 = add nsw i64 %inner.iv, %4
%arrayidx3 = getelementptr inbounds i8, ptr %dst, i64 %8
store i8 %add, ptr %arrayidx3, align 1
%inner.iv.next = add nuw nsw i64 %inner.iv, 1
%exitcond.inner = icmp eq i64 %inner.iv.next, %0
br i1 %exitcond.inner, label %inner.loop.exit, label %inner.loop
inner.loop.exit:
%outer.iv.next = add nuw nsw i64 %outer.iv, 1
%exitcond.not = icmp eq i64 %outer.iv.next, %wide.trip.count
br i1 %exitcond.not, label %outer.loop.exit, label %outer.loop
outer.loop.exit:
br label %exit
exit:
ret void
}
; Bounds with a udiv by a non-zero, non-poison divisor are hoisted.
define void @udiv_known_nonzero(ptr %dst, ptr %src, i64 %n, i64 noundef %x) mustprogress {
; CHECK-LABEL: define void @udiv_known_nonzero(
; CHECK-SAME: ptr [[DST:%.*]], ptr [[SRC:%.*]], i64 [[N:%.*]], i64 noundef [[X:%.*]]) #[[ATTR0:[0-9]+]] {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[S:%.*]] = or i64 [[X]], 1
; CHECK-NEXT: [[UMAX:%.*]] = call i64 @llvm.umax.i64(i64 [[S]], i64 [[N]])
; CHECK-NEXT: [[TMP0:%.*]] = add i64 [[UMAX]], -1
; CHECK-NEXT: [[TMP1:%.*]] = udiv i64 [[TMP0]], [[S]]
; CHECK-NEXT: [[TMP2:%.*]] = shl i64 [[TMP1]], 3
; CHECK-NEXT: [[TMP3:%.*]] = add nuw nsw i64 [[TMP2]], 4
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP3]]
; CHECK-NEXT: [[TMP4:%.*]] = shl i64 [[TMP1]], 2
; CHECK-NEXT: [[TMP5:%.*]] = add i64 [[TMP4]], 101380
; CHECK-NEXT: [[SCEVGEP5:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP5]]
; CHECK-NEXT: br label %[[OUTER:.*]]
; CHECK: [[OUTER]]:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[OUTER_IV_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT: [[DST_OFF:%.*]] = mul i64 [[OUTER_IV]], 1024
; CHECK-NEXT: [[DST_O:%.*]] = getelementptr inbounds i8, ptr [[DST]], i64 [[DST_OFF]]
; CHECK-NEXT: [[TMP6:%.*]] = call i64 @llvm.umax.i64(i64 [[S]], i64 [[N]])
; CHECK-NEXT: [[TMP7:%.*]] = add i64 [[TMP6]], -1
; CHECK-NEXT: [[TMP8:%.*]] = udiv i64 [[TMP7]], [[S]]
; CHECK-NEXT: [[TMP9:%.*]] = add nuw i64 [[TMP8]], 1
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[TMP9]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP5]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[TMP10:%.*]] = and i64 [[TMP9]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[TMP9]], [[TMP10]]
; CHECK-NEXT: [[TMP11:%.*]] = mul i64 [[N_VEC]], [[S]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[VEC_IND:%.*]] = phi <4 x i64> [ <i64 0, i64 1, i64 2, i64 3>, %[[VECTOR_PH]] ], [ [[VEC_IND_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP12:%.*]] = shl nuw nsw <4 x i64> [[VEC_IND]], splat (i64 1)
; CHECK-NEXT: [[TMP13:%.*]] = extractelement <4 x i64> [[TMP12]], i64 0
; CHECK-NEXT: [[TMP14:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP13]]
; CHECK-NEXT: [[TMP15:%.*]] = extractelement <4 x i64> [[TMP12]], i64 1
; CHECK-NEXT: [[TMP16:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP15]]
; CHECK-NEXT: [[TMP17:%.*]] = extractelement <4 x i64> [[TMP12]], i64 2
; CHECK-NEXT: [[TMP18:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP17]]
; CHECK-NEXT: [[TMP19:%.*]] = extractelement <4 x i64> [[TMP12]], i64 3
; CHECK-NEXT: [[TMP20:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP19]]
; CHECK-NEXT: [[TMP21:%.*]] = load i32, ptr [[TMP14]], align 4, !alias.scope [[META86:![0-9]+]]
; CHECK-NEXT: [[TMP22:%.*]] = load i32, ptr [[TMP16]], align 4, !alias.scope [[META86]]
; CHECK-NEXT: [[TMP23:%.*]] = load i32, ptr [[TMP18]], align 4, !alias.scope [[META86]]
; CHECK-NEXT: [[TMP24:%.*]] = load i32, ptr [[TMP20]], align 4, !alias.scope [[META86]]
; CHECK-NEXT: [[TMP25:%.*]] = insertelement <4 x i32> poison, i32 [[TMP21]], i64 0
; CHECK-NEXT: [[TMP26:%.*]] = insertelement <4 x i32> [[TMP25]], i32 [[TMP22]], i64 1
; CHECK-NEXT: [[TMP27:%.*]] = insertelement <4 x i32> [[TMP26]], i32 [[TMP23]], i64 2
; CHECK-NEXT: [[TMP28:%.*]] = insertelement <4 x i32> [[TMP27]], i32 [[TMP24]], i64 3
; CHECK-NEXT: [[TMP29:%.*]] = getelementptr inbounds i32, ptr [[DST_O]], i64 [[INDEX]]
; CHECK-NEXT: store <4 x i32> [[TMP28]], ptr [[TMP29]], align 4, !alias.scope [[META89:![0-9]+]], !noalias [[META86]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[VEC_IND_NEXT]] = add nuw nsw <4 x i64> [[VEC_IND]], splat (i64 4)
; CHECK-NEXT: [[TMP30:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP30]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP91:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[TMP9]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[OUTER_LATCH]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[TMP11]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: [[BC_RESUME_VAL3:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER:.*]]
; CHECK: [[INNER]]:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[K:%.*]] = phi i64 [ [[BC_RESUME_VAL3]], %[[SCALAR_PH]] ], [ [[K_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[K_2:%.*]] = shl nuw nsw i64 [[K]], 1
; CHECK-NEXT: [[GEP_SRC:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[K_2]]
; CHECK-NEXT: [[L:%.*]] = load i32, ptr [[GEP_SRC]], align 4
; CHECK-NEXT: [[GEP_DST:%.*]] = getelementptr inbounds i32, ptr [[DST_O]], i64 [[K]]
; CHECK-NEXT: store i32 [[L]], ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[K_NEXT]] = add nuw nsw i64 [[K]], 1
; CHECK-NEXT: [[IV_NEXT]] = add nuw i64 [[IV]], [[S]]
; CHECK-NEXT: [[C:%.*]] = icmp ult i64 [[IV_NEXT]], [[N]]
; CHECK-NEXT: br i1 [[C]], label %[[INNER]], label %[[OUTER_LATCH]], !llvm.loop [[LOOP92:![0-9]+]]
; CHECK: [[OUTER_LATCH]]:
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nuw i64 [[OUTER_IV]], 1
; CHECK-NEXT: [[EC:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], 100
; CHECK-NEXT: br i1 [[EC]], label %[[EXIT:.*]], label %[[OUTER]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
%s = or i64 %x, 1
br label %outer
outer:
%outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
%dst.off = mul i64 %outer.iv, 1024
%dst.o = getelementptr inbounds i8, ptr %dst, i64 %dst.off
br label %inner
inner:
%iv = phi i64 [ 0, %outer ], [ %iv.next, %inner ]
%k = phi i64 [ 0, %outer ], [ %k.next, %inner ]
%k.2 = shl nuw nsw i64 %k, 1
%gep.src = getelementptr inbounds i32, ptr %src, i64 %k.2
%l = load i32, ptr %gep.src
%gep.dst = getelementptr inbounds i32, ptr %dst.o, i64 %k
store i32 %l, ptr %gep.dst
%k.next = add nuw nsw i64 %k, 1
%iv.next = add nuw i64 %iv, %s
%c = icmp ult i64 %iv.next, %n
br i1 %c, label %inner, label %outer.latch
outer.latch:
%outer.iv.next = add nuw i64 %outer.iv, 1
%ec = icmp eq i64 %outer.iv.next, 100
br i1 %ec, label %exit, label %outer
exit:
ret void
}
; Bounds with a udiv by a non-zero, maybe-poison divisor are not hoisted.
define void @udiv_known_nonzero_maybe_poison(ptr %dst, ptr %src, i64 %n, i64 %x, i1 %g) {
; CHECK-LABEL: define void @udiv_known_nonzero_maybe_poison(
; CHECK-SAME: ptr [[DST:%.*]], ptr [[SRC:%.*]], i64 [[N:%.*]], i64 [[X:%.*]], i1 [[G:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[S:%.*]] = or i64 [[X]], 1
; CHECK-NEXT: [[UMAX:%.*]] = call i64 @llvm.umax.i64(i64 [[S]], i64 [[N]])
; CHECK-NEXT: [[TMP0:%.*]] = add i64 [[UMAX]], -1
; CHECK-NEXT: br label %[[OUTER:.*]]
; CHECK: [[OUTER]]:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[OUTER_IV_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT: [[DST_OFF:%.*]] = mul i64 [[OUTER_IV]], 1024
; CHECK-NEXT: [[DST_O:%.*]] = getelementptr i8, ptr [[DST]], i64 [[DST_OFF]]
; CHECK-NEXT: br i1 [[G]], label %[[INNER_PH:.*]], label %[[OUTER_LATCH]]
; CHECK: [[INNER_PH]]:
; CHECK-NEXT: [[TMP1:%.*]] = call i64 @llvm.umax.i64(i64 [[S]], i64 [[N]])
; CHECK-NEXT: [[TMP2:%.*]] = add i64 [[TMP1]], -1
; CHECK-NEXT: [[TMP3:%.*]] = udiv i64 [[TMP2]], [[S]]
; CHECK-NEXT: [[TMP4:%.*]] = add nuw i64 [[TMP3]], 1
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[TMP4]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_SCEVCHECK:.*]]
; CHECK: [[VECTOR_SCEVCHECK]]:
; CHECK-NEXT: [[IDENT_CHECK:%.*]] = icmp sle i64 [[S]], 0
; CHECK-NEXT: br i1 [[IDENT_CHECK]], label %[[SCALAR_PH]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[TMP5:%.*]] = udiv i64 [[TMP0]], [[S]]
; CHECK-NEXT: [[TMP6:%.*]] = shl i64 [[TMP5]], 2
; CHECK-NEXT: [[TMP7:%.*]] = add i64 [[TMP6]], 101380
; CHECK-NEXT: [[TMP8:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP7]]
; CHECK-NEXT: [[TMP9:%.*]] = shl i64 [[TMP5]], 3
; CHECK-NEXT: [[TMP10:%.*]] = add nuw nsw i64 [[TMP9]], 4
; CHECK-NEXT: [[TMP11:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP10]]
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[TMP11]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[TMP8]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[TMP12:%.*]] = and i64 [[TMP4]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[TMP4]], [[TMP12]]
; CHECK-NEXT: [[TMP13:%.*]] = mul i64 [[N_VEC]], [[S]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[VEC_IND:%.*]] = phi <4 x i64> [ <i64 0, i64 1, i64 2, i64 3>, %[[VECTOR_PH]] ], [ [[VEC_IND_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP14:%.*]] = shl nuw nsw <4 x i64> [[VEC_IND]], splat (i64 1)
; CHECK-NEXT: [[TMP15:%.*]] = extractelement <4 x i64> [[TMP14]], i64 0
; CHECK-NEXT: [[TMP16:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP15]]
; CHECK-NEXT: [[TMP17:%.*]] = extractelement <4 x i64> [[TMP14]], i64 1
; CHECK-NEXT: [[TMP18:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP17]]
; CHECK-NEXT: [[TMP19:%.*]] = extractelement <4 x i64> [[TMP14]], i64 2
; CHECK-NEXT: [[TMP20:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP19]]
; CHECK-NEXT: [[TMP21:%.*]] = extractelement <4 x i64> [[TMP14]], i64 3
; CHECK-NEXT: [[TMP22:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP21]]
; CHECK-NEXT: [[TMP23:%.*]] = load i32, ptr [[TMP16]], align 4, !alias.scope [[META93:![0-9]+]]
; CHECK-NEXT: [[TMP24:%.*]] = load i32, ptr [[TMP18]], align 4, !alias.scope [[META93]]
; CHECK-NEXT: [[TMP25:%.*]] = load i32, ptr [[TMP20]], align 4, !alias.scope [[META93]]
; CHECK-NEXT: [[TMP26:%.*]] = load i32, ptr [[TMP22]], align 4, !alias.scope [[META93]]
; CHECK-NEXT: [[TMP27:%.*]] = insertelement <4 x i32> poison, i32 [[TMP23]], i64 0
; CHECK-NEXT: [[TMP28:%.*]] = insertelement <4 x i32> [[TMP27]], i32 [[TMP24]], i64 1
; CHECK-NEXT: [[TMP29:%.*]] = insertelement <4 x i32> [[TMP28]], i32 [[TMP25]], i64 2
; CHECK-NEXT: [[TMP30:%.*]] = insertelement <4 x i32> [[TMP29]], i32 [[TMP26]], i64 3
; CHECK-NEXT: [[TMP31:%.*]] = getelementptr inbounds i32, ptr [[DST_O]], i64 [[INDEX]]
; CHECK-NEXT: store <4 x i32> [[TMP30]], ptr [[TMP31]], align 4, !alias.scope [[META96:![0-9]+]], !noalias [[META93]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[VEC_IND_NEXT]] = add nuw nsw <4 x i64> [[VEC_IND]], splat (i64 4)
; CHECK-NEXT: [[TMP32:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP32]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP98:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[TMP4]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[OUTER_LATCH_LOOPEXIT:.*]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[TMP13]], %[[MIDDLE_BLOCK]] ], [ 0, %[[INNER_PH]] ], [ 0, %[[VECTOR_SCEVCHECK]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: [[BC_RESUME_VAL2:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[INNER_PH]] ], [ 0, %[[VECTOR_SCEVCHECK]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER:.*]]
; CHECK: [[INNER]]:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[K:%.*]] = phi i64 [ [[BC_RESUME_VAL2]], %[[SCALAR_PH]] ], [ [[K_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[K_2:%.*]] = shl nuw nsw i64 [[K]], 1
; CHECK-NEXT: [[GEP_SRC:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[K_2]]
; CHECK-NEXT: [[L:%.*]] = load i32, ptr [[GEP_SRC]], align 4
; CHECK-NEXT: [[GEP_DST:%.*]] = getelementptr inbounds i32, ptr [[DST_O]], i64 [[K]]
; CHECK-NEXT: store i32 [[L]], ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[K_NEXT]] = add nuw nsw i64 [[K]], 1
; CHECK-NEXT: [[IV_NEXT]] = add nuw i64 [[IV]], [[S]]
; CHECK-NEXT: [[C:%.*]] = icmp ult i64 [[IV_NEXT]], [[N]]
; CHECK-NEXT: br i1 [[C]], label %[[INNER]], label %[[OUTER_LATCH_LOOPEXIT]], !llvm.loop [[LOOP99:![0-9]+]]
; CHECK: [[OUTER_LATCH_LOOPEXIT]]:
; CHECK-NEXT: br label %[[OUTER_LATCH]]
; CHECK: [[OUTER_LATCH]]:
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nuw i64 [[OUTER_IV]], 1
; CHECK-NEXT: [[EC:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], 100
; CHECK-NEXT: br i1 [[EC]], label %[[EXIT:.*]], label %[[OUTER]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
%s = or i64 %x, 1
br label %outer
outer:
%outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
%dst.off = mul i64 %outer.iv, 1024
%dst.o = getelementptr i8, ptr %dst, i64 %dst.off
br i1 %g, label %inner.ph, label %outer.latch
inner.ph:
br label %inner
inner:
%iv = phi i64 [ 0, %inner.ph ], [ %iv.next, %inner ]
%k = phi i64 [ 0, %inner.ph ], [ %k.next, %inner ]
%k.2 = shl nuw nsw i64 %k, 1
%gep.src = getelementptr inbounds i32, ptr %src, i64 %k.2
%l = load i32, ptr %gep.src
%gep.dst = getelementptr inbounds i32, ptr %dst.o, i64 %k
store i32 %l, ptr %gep.dst
%k.next = add nuw nsw i64 %k, 1
%iv.next = add nuw i64 %iv, %s
%c = icmp ult i64 %iv.next, %n
br i1 %c, label %inner, label %outer.latch
outer.latch:
%outer.iv.next = add nuw i64 %outer.iv, 1
%ec = icmp eq i64 %outer.iv.next, 100
br i1 %ec, label %exit, label %outer
exit:
ret void
}
; The minimum iteration check only folds to true after the hoisted runtime
; check bounds were created, making the vector loop dead. Make sure no IR is
; generated for the dead bounds.
define void @vector_loop_dead_after_hoisting_checks(ptr %dst, ptr %src, i1 %c, i32 %n, i64 %stride) {
; CHECK-LABEL: define void @vector_loop_dead_after_hoisting_checks(
; CHECK-SAME: ptr [[DST:%.*]], ptr [[SRC:%.*]], i1 [[C:%.*]], i32 [[N:%.*]], i64 [[STRIDE:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*:]]
; CHECK-NEXT: [[SEL:%.*]] = select i1 [[C]], i32 0, i32 0
; CHECK-NEXT: [[GUARD:%.*]] = icmp sgt i32 [[SEL]], [[N]]
; CHECK-NEXT: br i1 [[GUARD]], label %[[EXIT:.*]], label %[[OUTER_PH:.*]]
; CHECK: [[OUTER_PH]]:
; CHECK-NEXT: [[TC:%.*]] = zext i32 [[SEL]] to i64
; CHECK-NEXT: br label %[[OUTER:.*]]
; CHECK: [[OUTER_LOOPEXIT:.*]]:
; CHECK-NEXT: br label %[[OUTER]]
; CHECK: [[OUTER]]:
; CHECK-NEXT: br label %[[INNER:.*]]
; CHECK: [[INNER]]:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, %[[OUTER]] ], [ [[IV_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[PTR_DST:%.*]] = phi ptr [ [[DST]], %[[OUTER]] ], [ [[PTR_DST_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[STRIDE_SQ:%.*]] = mul i64 [[STRIDE]], [[STRIDE]]
; CHECK-NEXT: [[OFF:%.*]] = mul i64 [[STRIDE_SQ]], [[IV]]
; CHECK-NEXT: [[GEP_SRC:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[OFF]]
; CHECK-NEXT: [[L:%.*]] = load float, ptr [[GEP_SRC]], align 4
; CHECK-NEXT: store float 0.000000e+00, ptr [[PTR_DST]], align 4
; CHECK-NEXT: [[PTR_DST_NEXT]] = getelementptr i8, ptr [[PTR_DST]], i64 4
; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT: [[EC:%.*]] = icmp eq i64 [[IV_NEXT]], [[TC]]
; CHECK-NEXT: br i1 [[EC]], label %[[OUTER_LOOPEXIT]], label %[[INNER]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
%sel = select i1 %c, i32 0, i32 0
%guard = icmp sgt i32 %sel, %n
br i1 %guard, label %exit, label %outer.ph
outer.ph:
%tc = zext i32 %sel to i64
br label %outer
outer:
br label %inner
inner:
%iv = phi i64 [ 0, %outer ], [ %iv.next, %inner ]
%ptr.dst = phi ptr [ %dst, %outer ], [ %ptr.dst.next, %inner ]
%stride.sq = mul i64 %stride, %stride
%off = mul i64 %stride.sq, %iv
%gep.src = getelementptr i8, ptr %src, i64 %off
%l = load float, ptr %gep.src, align 4
store float 0.000000e+00, ptr %ptr.dst, align 4
%ptr.dst.next = getelementptr i8, ptr %ptr.dst, i64 4
%iv.next = add i64 %iv, 1
%ec = icmp eq i64 %iv.next, %tc
br i1 %ec, label %outer, label %inner
exit:
ret void
}
; The memory runtime check folds to false, but leaves a dead compare behind
; that keeps the hoisted bound expansions alive. Make sure no later expansion
; re-uses them and the cleanup of the check block doesn't remove them.
define void @memcheck_folds_to_false_keeps_expansions(ptr %p, i32 %n, i64 %m) {
; CHECK-LABEL: define void @memcheck_folds_to_false_keeps_expansions(
; CHECK-SAME: ptr [[P:%.*]], i32 [[N:%.*]], i64 [[M:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[CNT:%.*]] = zext i32 [[N]] to i64
; CHECK-NEXT: [[TOTAL:%.*]] = mul i64 [[CNT]], [[M]]
; CHECK-NEXT: [[TOTAL_BYTES:%.*]] = shl i64 [[TOTAL]], 2
; CHECK-NEXT: [[Q:%.*]] = getelementptr i8, ptr [[P]], i64 [[TOTAL_BYTES]]
; CHECK-NEXT: [[TMP0:%.*]] = mul i64 [[M]], [[CNT]]
; CHECK-NEXT: [[TMP1:%.*]] = shl i64 [[TMP0]], 3
; CHECK-NEXT: [[TMP2:%.*]] = mul i64 [[M]], [[CNT]]
; CHECK-NEXT: [[TMP3:%.*]] = shl i64 [[TMP2]], 4
; CHECK-NEXT: br label %[[OUTER:.*]]
; CHECK: [[OUTER]]:
; CHECK-NEXT: [[INDUCTION_IV:%.*]] = phi i64 [ [[INDUCTION_IV_NEXT:%.*]], %[[OUTER_LATCH:.*]] ], [ 0, %[[ENTRY]] ]
; CHECK-NEXT: [[J:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[J_NEXT:%.*]], %[[OUTER_LATCH]] ]
; CHECK-NEXT: [[TMP4:%.*]] = mul i64 [[TMP3]], [[J]]
; CHECK-NEXT: [[TMP5:%.*]] = add i64 [[TMP1]], [[TMP4]]
; CHECK-NEXT: [[ROW:%.*]] = mul i64 [[J]], [[CNT]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[CNT]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[TMP6:%.*]] = and i64 [[CNT]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[CNT]], [[TMP6]]
; CHECK-NEXT: [[TMP7:%.*]] = mul i64 [[N_VEC]], [[INDUCTION_IV]]
; CHECK-NEXT: [[TMP8:%.*]] = trunc i64 [[INDUCTION_IV]] to i32
; CHECK-NEXT: [[BROADCAST_SPLATINSERT:%.*]] = insertelement <4 x i32> poison, i32 [[TMP8]], i64 0
; CHECK-NEXT: [[BROADCAST_SPLAT:%.*]] = shufflevector <4 x i32> [[BROADCAST_SPLATINSERT]], <4 x i32> poison, <4 x i32> zeroinitializer
; CHECK-NEXT: [[TMP9:%.*]] = mul <4 x i32> <i32 0, i32 1, i32 2, i32 3>, [[BROADCAST_SPLAT]]
; CHECK-NEXT: [[TMP10:%.*]] = shl i32 [[TMP8]], 2
; CHECK-NEXT: [[BROADCAST_SPLATINSERT1:%.*]] = insertelement <4 x i32> poison, i32 [[TMP10]], i64 0
; CHECK-NEXT: [[BROADCAST_SPLAT2:%.*]] = shufflevector <4 x i32> [[BROADCAST_SPLATINSERT1]], <4 x i32> poison, <4 x i32> zeroinitializer
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[VEC_IND:%.*]] = phi <4 x i32> [ [[TMP9]], %[[VECTOR_PH]] ], [ [[VEC_IND_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP11:%.*]] = add i64 [[ROW]], [[INDEX]]
; CHECK-NEXT: [[TMP12:%.*]] = getelementptr inbounds i32, ptr [[Q]], i64 [[TMP11]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP12]], align 4, !alias.scope [[META100:![0-9]+]]
; CHECK-NEXT: [[TMP13:%.*]] = getelementptr inbounds i32, ptr [[P]], i64 [[TMP11]]
; CHECK-NEXT: [[WIDE_LOAD3:%.*]] = load <4 x i32>, ptr [[TMP13]], align 4, !alias.scope [[META103:![0-9]+]], !noalias [[META100]]
; CHECK-NEXT: [[TMP14:%.*]] = add <4 x i32> [[WIDE_LOAD]], [[WIDE_LOAD3]]
; CHECK-NEXT: [[TMP15:%.*]] = add <4 x i32> [[TMP14]], [[VEC_IND]]
; CHECK-NEXT: store <4 x i32> [[TMP15]], ptr [[TMP13]], align 4, !alias.scope [[META103]], !noalias [[META100]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[VEC_IND_NEXT]] = add <4 x i32> [[VEC_IND]], [[BROADCAST_SPLAT2]]
; CHECK-NEXT: [[TMP16:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP16]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP105:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[CNT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[OUTER_LATCH]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER]] ]
; CHECK-NEXT: [[BC_RESUME_VAL4:%.*]] = phi i64 [ [[TMP7]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER]] ]
; CHECK-NEXT: br label %[[INNER:.*]]
; CHECK: [[INNER]]:
; CHECK-NEXT: [[I:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[I_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[K:%.*]] = phi i64 [ [[BC_RESUME_VAL4]], %[[SCALAR_PH]] ], [ [[K_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[IDX:%.*]] = add i64 [[ROW]], [[I]]
; CHECK-NEXT: [[GEP_Q:%.*]] = getelementptr inbounds i32, ptr [[Q]], i64 [[IDX]]
; CHECK-NEXT: [[L_Q:%.*]] = load i32, ptr [[GEP_Q]], align 4
; CHECK-NEXT: [[GEP_P:%.*]] = getelementptr inbounds i32, ptr [[P]], i64 [[IDX]]
; CHECK-NEXT: [[L_P:%.*]] = load i32, ptr [[GEP_P]], align 4
; CHECK-NEXT: [[K_TRUNC:%.*]] = trunc i64 [[K]] to i32
; CHECK-NEXT: [[ADD:%.*]] = add i32 [[L_Q]], [[L_P]]
; CHECK-NEXT: [[SUM:%.*]] = add i32 [[ADD]], [[K_TRUNC]]
; CHECK-NEXT: store i32 [[SUM]], ptr [[GEP_P]], align 4
; CHECK-NEXT: [[TOTAL_IN:%.*]] = mul i64 [[CNT]], [[M]]
; CHECK-NEXT: [[TOTAL_BYTES2:%.*]] = shl i64 [[TOTAL_IN]], 3
; CHECK-NEXT: [[J_SQ:%.*]] = mul i64 [[J]], [[J]]
; CHECK-NEXT: [[STEP:%.*]] = mul i64 [[J_SQ]], [[TOTAL_BYTES2]]
; CHECK-NEXT: [[K_NEXT]] = add i64 [[K]], [[STEP]]
; CHECK-NEXT: [[I_NEXT]] = add i64 [[I]], 1
; CHECK-NEXT: [[EC:%.*]] = icmp eq i64 [[I_NEXT]], [[CNT]]
; CHECK-NEXT: br i1 [[EC]], label %[[OUTER_LATCH]], label %[[INNER]], !llvm.loop [[LOOP106:![0-9]+]]
; CHECK: [[OUTER_LATCH]]:
; CHECK-NEXT: [[J_NEXT]] = add i64 [[J]], 1
; CHECK-NEXT: [[EC2:%.*]] = icmp eq i64 [[J_NEXT]], [[M]]
; CHECK-NEXT: [[INDUCTION_IV_NEXT]] = add i64 [[INDUCTION_IV]], [[TMP5]]
; CHECK-NEXT: br i1 [[EC2]], label %[[EXIT:.*]], label %[[OUTER]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
%cnt = zext i32 %n to i64
%total = mul i64 %cnt, %m
%total.bytes = shl i64 %total, 2
%q = getelementptr i8, ptr %p, i64 %total.bytes
br label %outer
outer:
%j = phi i64 [ 0, %entry ], [ %j.next, %outer.latch ]
%row = mul i64 %j, %cnt
br label %inner
inner:
%i = phi i64 [ 0, %outer ], [ %i.next, %inner ]
%k = phi i64 [ 0, %outer ], [ %k.next, %inner ]
%idx = add i64 %row, %i
%gep.q = getelementptr inbounds i32, ptr %q, i64 %idx
%l.q = load i32, ptr %gep.q, align 4
%gep.p = getelementptr inbounds i32, ptr %p, i64 %idx
%l.p = load i32, ptr %gep.p, align 4
%k.trunc = trunc i64 %k to i32
%add = add i32 %l.q, %l.p
%sum = add i32 %add, %k.trunc
store i32 %sum, ptr %gep.p, align 4
%total.in = mul i64 %cnt, %m
%total.bytes2 = shl i64 %total.in, 3
%j.sq = mul i64 %j, %j
%step = mul i64 %j.sq, %total.bytes2
%k.next = add i64 %k, %step
%i.next = add i64 %i, 1
%ec = icmp eq i64 %i.next, %cnt
br i1 %ec, label %outer.latch, label %inner
outer.latch:
%j.next = add i64 %j, 1
%ec2 = icmp eq i64 %j.next, %m
br i1 %ec2, label %exit, label %outer
exit:
ret void
}
; The bound %ptr + (%step + %len + 1 - smin) mixes outer-variant and invariant
; operands. The invariant operands are summed outside the outer loop.
define void @upper_bound_invariant_operands_summed(ptr %dst, ptr %src, ptr %step.ptr, i64 %len, i64 %m) {
; CHECK-LABEL: define void @upper_bound_invariant_operands_summed(
; CHECK-SAME: ptr [[DST:%.*]], ptr [[SRC:%.*]], ptr [[STEP_PTR:%.*]], i64 [[LEN:%.*]], i64 [[M:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[SRC]], i64 1
; CHECK-NEXT: [[TMP0:%.*]] = add i64 [[LEN]], 1
; CHECK-NEXT: [[SMIN:%.*]] = call i64 @llvm.smin.i64(i64 [[LEN]], i64 0)
; CHECK-NEXT: [[TMP1:%.*]] = sub i64 [[TMP0]], [[SMIN]]
; CHECK-NEXT: [[SCEVGEP11:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP1]]
; CHECK-NEXT: br label %[[OUTER:.*]]
; CHECK: [[OUTER]]:
; CHECK-NEXT: [[PTR:%.*]] = phi ptr [ [[DST]], %[[ENTRY]] ], [ [[PTR_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT: [[J:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[J_NEXT:%.*]], %[[OUTER_LATCH]] ]
; CHECK-NEXT: [[STEP:%.*]] = load i64, ptr [[STEP_PTR]], align 8
; CHECK-NEXT: [[PTR_NEXT]] = getelementptr i8, ptr [[PTR]], i64 [[STEP]]
; CHECK-NEXT: [[TMP2:%.*]] = call i64 @llvm.smin.i64(i64 [[LEN]], i64 0)
; CHECK-NEXT: [[TMP3:%.*]] = add i64 [[LEN]], 1
; CHECK-NEXT: [[TMP4:%.*]] = sub i64 [[TMP3]], [[TMP2]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[TMP4]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[TMP7:%.*]] = add i64 [[TMP1]], [[STEP]]
; CHECK-NEXT: [[TMP8:%.*]] = getelementptr i8, ptr [[PTR]], i64 [[TMP7]]
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[TMP8]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[PTR_NEXT]], [[SCEVGEP11]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: [[BOUND012:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP]]
; CHECK-NEXT: [[BOUND113:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP11]]
; CHECK-NEXT: [[FOUND_CONFLICT14:%.*]] = and i1 [[BOUND012]], [[BOUND113]]
; CHECK-NEXT: [[CONFLICT_RDX:%.*]] = or i1 [[FOUND_CONFLICT]], [[FOUND_CONFLICT14]]
; CHECK-NEXT: [[BOUND015:%.*]] = icmp ult ptr [[PTR_NEXT]], [[SCEVGEP]]
; CHECK-NEXT: [[BOUND116:%.*]] = icmp ult ptr [[SRC]], [[TMP8]]
; CHECK-NEXT: [[FOUND_CONFLICT17:%.*]] = and i1 [[BOUND015]], [[BOUND116]]
; CHECK-NEXT: [[CONFLICT_RDX18:%.*]] = or i1 [[CONFLICT_RDX]], [[FOUND_CONFLICT17]]
; CHECK-NEXT: br i1 [[CONFLICT_RDX18]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[TMP9:%.*]] = and i64 [[TMP4]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[TMP4]], [[TMP9]]
; CHECK-NEXT: [[TMP10:%.*]] = sub i64 [[LEN]], [[N_VEC]]
; CHECK-NEXT: [[TMP11:%.*]] = getelementptr i8, ptr [[DST]], i64 [[N_VEC]]
; CHECK-NEXT: [[TMP12:%.*]] = getelementptr i8, ptr [[PTR_NEXT]], i64 [[N_VEC]]
; CHECK-NEXT: [[TMP13:%.*]] = load i8, ptr [[SRC]], align 1, !alias.scope [[META107:![0-9]+]]
; CHECK-NEXT: [[BROADCAST_SPLATINSERT:%.*]] = insertelement <4 x i8> poison, i8 [[TMP13]], i64 0
; CHECK-NEXT: [[BROADCAST_SPLAT:%.*]] = shufflevector <4 x i8> [[BROADCAST_SPLATINSERT]], <4 x i8> poison, <4 x i32> zeroinitializer
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[NEXT_GEP:%.*]] = getelementptr i8, ptr [[DST]], i64 [[INDEX]]
; CHECK-NEXT: [[NEXT_GEP19:%.*]] = getelementptr i8, ptr [[PTR_NEXT]], i64 [[INDEX]]
; CHECK-NEXT: store <4 x i8> zeroinitializer, ptr [[NEXT_GEP]], align 1, !alias.scope [[META110:![0-9]+]], !noalias [[META112:![0-9]+]]
; CHECK-NEXT: store <4 x i8> [[BROADCAST_SPLAT]], ptr [[NEXT_GEP19]], align 1, !alias.scope [[META114:![0-9]+]], !noalias [[META107]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP14:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP14]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP115:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[TMP4]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[OUTER_LATCH]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[TMP10]], %[[MIDDLE_BLOCK]] ], [ [[LEN]], %[[OUTER]] ], [ [[LEN]], %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: [[BC_RESUME_VAL20:%.*]] = phi ptr [ [[TMP11]], %[[MIDDLE_BLOCK]] ], [ [[DST]], %[[OUTER]] ], [ [[DST]], %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: [[BC_RESUME_VAL21:%.*]] = phi ptr [ [[TMP12]], %[[MIDDLE_BLOCK]] ], [ [[PTR_NEXT]], %[[OUTER]] ], [ [[PTR_NEXT]], %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER:.*]]
; CHECK: [[INNER]]:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[P:%.*]] = phi ptr [ [[BC_RESUME_VAL20]], %[[SCALAR_PH]] ], [ [[P_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[Q:%.*]] = phi ptr [ [[BC_RESUME_VAL21]], %[[SCALAR_PH]] ], [ [[Q_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: store i8 0, ptr [[P]], align 1
; CHECK-NEXT: [[V:%.*]] = load i8, ptr [[SRC]], align 1
; CHECK-NEXT: store i8 [[V]], ptr [[Q]], align 1
; CHECK-NEXT: [[P_NEXT]] = getelementptr i8, ptr [[P]], i64 1
; CHECK-NEXT: [[Q_NEXT]] = getelementptr i8, ptr [[Q]], i64 1
; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], -1
; CHECK-NEXT: [[EC:%.*]] = icmp sgt i64 [[IV]], 0
; CHECK-NEXT: br i1 [[EC]], label %[[INNER]], label %[[OUTER_LATCH]], !llvm.loop [[LOOP116:![0-9]+]]
; CHECK: [[OUTER_LATCH]]:
; CHECK-NEXT: [[J_NEXT]] = add i64 [[J]], 1
; CHECK-NEXT: [[EC2:%.*]] = icmp eq i64 [[J_NEXT]], [[M]]
; CHECK-NEXT: br i1 [[EC2]], label %[[EXIT:.*]], label %[[OUTER]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
br label %outer
outer:
%ptr = phi ptr [ %dst, %entry ], [ %ptr.next, %outer.latch ]
%j = phi i64 [ 0, %entry ], [ %j.next, %outer.latch ]
%step = load i64, ptr %step.ptr, align 8
%ptr.next = getelementptr i8, ptr %ptr, i64 %step
br label %inner
inner:
%iv = phi i64 [ %len, %outer ], [ %iv.next, %inner ]
%p = phi ptr [ %dst, %outer ], [ %p.next, %inner ]
%q = phi ptr [ %ptr.next, %outer ], [ %q.next, %inner ]
store i8 0, ptr %p, align 1
%v = load i8, ptr %src, align 1
store i8 %v, ptr %q, align 1
%p.next = getelementptr i8, ptr %p, i64 1
%q.next = getelementptr i8, ptr %q, i64 1
%iv.next = add i64 %iv, -1
%ec = icmp sgt i64 %iv, 0
br i1 %ec, label %inner, label %outer.latch
outer.latch:
%j.next = add i64 %j, 1
%ec2 = icmp eq i64 %j.next, %m
br i1 %ec2, label %exit, label %outer
exit:
ret void
}
; Bases %A, %B are invariant, the offset %off varies. The +4 for %B is added to
; the variant offset instead of the base.
; TODO: Fold the constant offset into the invariant base and hoist it.
define void @invariant_base_and_constant_offset_hoisted(ptr %A, ptr %B, ptr %Offs, i64 %n, i64 %m) {
; CHECK-LABEL: define void @invariant_base_and_constant_offset_hoisted(
; CHECK-SAME: ptr [[A:%.*]], ptr [[B:%.*]], ptr [[OFFS:%.*]], i64 [[N:%.*]], i64 [[M:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[TMP0:%.*]] = shl i64 [[M]], 2
; CHECK-NEXT: [[TMP16:%.*]] = add i64 [[TMP0]], 4
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[B]], i64 [[TMP16]]
; CHECK-NEXT: [[SCEVGEP7:%.*]] = getelementptr i8, ptr [[B]], i64 4
; CHECK-NEXT: [[SCEVGEP8:%.*]] = getelementptr i8, ptr [[A]], i64 [[TMP0]]
; CHECK-NEXT: br label %[[OUTER:.*]]
; CHECK: [[OUTER]]:
; CHECK-NEXT: [[I:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[I_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT: [[OFF_P:%.*]] = getelementptr i64, ptr [[OFFS]], i64 [[I]]
; CHECK-NEXT: [[OFF:%.*]] = load i64, ptr [[OFF_P]], align 8
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[M]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[TMP1:%.*]] = shl i64 [[OFF]], 2
; CHECK-NEXT: [[TMP2:%.*]] = getelementptr i8, ptr [[A]], i64 [[TMP1]]
; CHECK-NEXT: [[TMP4:%.*]] = getelementptr i8, ptr [[SCEVGEP8]], i64 [[TMP1]]
; CHECK-NEXT: [[TMP6:%.*]] = getelementptr i8, ptr [[SCEVGEP7]], i64 [[TMP1]]
; CHECK-NEXT: [[TMP8:%.*]] = getelementptr i8, ptr [[SCEVGEP]], i64 [[TMP1]]
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[TMP2]], [[TMP8]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[TMP6]], [[TMP4]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[TMP9:%.*]] = and i64 [[M]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[M]], [[TMP9]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP10:%.*]] = add i64 [[OFF]], [[INDEX]]
; CHECK-NEXT: [[TMP11:%.*]] = add i64 [[TMP10]], 1
; CHECK-NEXT: [[TMP12:%.*]] = getelementptr i32, ptr [[B]], i64 [[TMP11]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP12]], align 4, !alias.scope [[META117:![0-9]+]]
; CHECK-NEXT: [[TMP13:%.*]] = getelementptr i32, ptr [[A]], i64 [[TMP10]]
; CHECK-NEXT: [[WIDE_LOAD7:%.*]] = load <4 x i32>, ptr [[TMP13]], align 4, !alias.scope [[META120:![0-9]+]], !noalias [[META117]]
; CHECK-NEXT: [[TMP14:%.*]] = add <4 x i32> [[WIDE_LOAD]], [[WIDE_LOAD7]]
; CHECK-NEXT: store <4 x i32> [[TMP14]], ptr [[TMP13]], align 4, !alias.scope [[META120]], !noalias [[META117]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP15:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP15]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP122:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[M]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[OUTER_LATCH]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER:.*]]
; CHECK: [[INNER]]:
; CHECK-NEXT: [[J:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[J_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[IDX:%.*]] = add i64 [[OFF]], [[J]]
; CHECK-NEXT: [[IDX1:%.*]] = add i64 [[IDX]], 1
; CHECK-NEXT: [[B_P:%.*]] = getelementptr i32, ptr [[B]], i64 [[IDX1]]
; CHECK-NEXT: [[V:%.*]] = load i32, ptr [[B_P]], align 4
; CHECK-NEXT: [[A_P:%.*]] = getelementptr i32, ptr [[A]], i64 [[IDX]]
; CHECK-NEXT: [[W:%.*]] = load i32, ptr [[A_P]], align 4
; CHECK-NEXT: [[S:%.*]] = add i32 [[V]], [[W]]
; CHECK-NEXT: store i32 [[S]], ptr [[A_P]], align 4
; CHECK-NEXT: [[J_NEXT]] = add i64 [[J]], 1
; CHECK-NEXT: [[EC:%.*]] = icmp eq i64 [[J_NEXT]], [[M]]
; CHECK-NEXT: br i1 [[EC]], label %[[OUTER_LATCH]], label %[[INNER]], !llvm.loop [[LOOP123:![0-9]+]]
; CHECK: [[OUTER_LATCH]]:
; CHECK-NEXT: [[I_NEXT]] = add i64 [[I]], 1
; CHECK-NEXT: [[EC2:%.*]] = icmp eq i64 [[I_NEXT]], [[N]]
; CHECK-NEXT: br i1 [[EC2]], label %[[EXIT:.*]], label %[[OUTER]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
br label %outer
outer:
%i = phi i64 [ 0, %entry ], [ %i.next, %outer.latch ]
%off.p = getelementptr i64, ptr %Offs, i64 %i
%off = load i64, ptr %off.p, align 8
br label %inner
inner:
%j = phi i64 [ 0, %outer ], [ %j.next, %inner ]
%idx = add i64 %off, %j
%idx1 = add i64 %idx, 1
%b.p = getelementptr i32, ptr %B, i64 %idx1
%v = load i32, ptr %b.p, align 4
%a.p = getelementptr i32, ptr %A, i64 %idx
%w = load i32, ptr %a.p, align 4
%s = add i32 %v, %w
store i32 %s, ptr %a.p, align 4
%j.next = add i64 %j, 1
%ec = icmp eq i64 %j.next, %m
br i1 %ec, label %outer.latch, label %inner
outer.latch:
%i.next = add i64 %i, 1
%ec2 = icmp eq i64 %i.next, %n
br i1 %ec2, label %exit, label %outer
exit:
ret void
}
; The start %p + (%x + %i) has an invariant base but only variant offsets, so
; there is nothing to hoist.
define void @ptr_base_invariant_no_invariant_operand(ptr %p, ptr %q, ptr %xs, i64 %n, i64 %m) {
; CHECK-LABEL: define void @ptr_base_invariant_no_invariant_operand(
; CHECK-SAME: ptr [[P:%.*]], ptr [[Q:%.*]], ptr [[XS:%.*]], i64 [[N:%.*]], i64 [[M:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[TMP0:%.*]] = shl i64 [[N]], 2
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[Q]], i64 [[TMP0]]
; CHECK-NEXT: br label %[[OUTER:.*]]
; CHECK: [[OUTER]]:
; CHECK-NEXT: [[I:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[I_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT: [[XP:%.*]] = getelementptr i64, ptr [[XS]], i64 [[I]]
; CHECK-NEXT: [[X:%.*]] = load i64, ptr [[XP]], align 8
; CHECK-NEXT: [[PI:%.*]] = getelementptr i8, ptr [[P]], i64 [[I]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[N]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[TMP1:%.*]] = add i64 [[X]], [[I]]
; CHECK-NEXT: [[TMP2:%.*]] = getelementptr i8, ptr [[P]], i64 [[TMP1]]
; CHECK-NEXT: [[TMP3:%.*]] = add i64 [[N]], [[I]]
; CHECK-NEXT: [[TMP4:%.*]] = add i64 [[X]], [[TMP3]]
; CHECK-NEXT: [[TMP5:%.*]] = getelementptr i8, ptr [[P]], i64 [[TMP4]]
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[Q]], [[TMP5]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[TMP2]], [[SCEVGEP]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[TMP6:%.*]] = and i64 [[N]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[N]], [[TMP6]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP7:%.*]] = add i64 [[X]], [[INDEX]]
; CHECK-NEXT: [[TMP8:%.*]] = getelementptr i8, ptr [[PI]], i64 [[TMP7]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i8>, ptr [[TMP8]], align 1, !alias.scope [[META124:![0-9]+]]
; CHECK-NEXT: [[TMP9:%.*]] = sext <4 x i8> [[WIDE_LOAD]] to <4 x i32>
; CHECK-NEXT: [[TMP10:%.*]] = getelementptr i32, ptr [[Q]], i64 [[INDEX]]
; CHECK-NEXT: store <4 x i32> [[TMP9]], ptr [[TMP10]], align 4, !alias.scope [[META127:![0-9]+]], !noalias [[META124]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP11:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP11]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP129:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[N]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[OUTER_LATCH]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER:.*]]
; CHECK: [[INNER]]:
; CHECK-NEXT: [[J:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[J_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[OFF:%.*]] = add i64 [[X]], [[J]]
; CHECK-NEXT: [[A_P:%.*]] = getelementptr i8, ptr [[PI]], i64 [[OFF]]
; CHECK-NEXT: [[V:%.*]] = load i8, ptr [[A_P]], align 1
; CHECK-NEXT: [[E:%.*]] = sext i8 [[V]] to i32
; CHECK-NEXT: [[B_P:%.*]] = getelementptr i32, ptr [[Q]], i64 [[J]]
; CHECK-NEXT: store i32 [[E]], ptr [[B_P]], align 4
; CHECK-NEXT: [[J_NEXT]] = add i64 [[J]], 1
; CHECK-NEXT: [[EC:%.*]] = icmp eq i64 [[J_NEXT]], [[N]]
; CHECK-NEXT: br i1 [[EC]], label %[[OUTER_LATCH]], label %[[INNER]], !llvm.loop [[LOOP130:![0-9]+]]
; CHECK: [[OUTER_LATCH]]:
; CHECK-NEXT: [[I_NEXT]] = add i64 [[I]], 1
; CHECK-NEXT: [[EC2:%.*]] = icmp eq i64 [[I_NEXT]], [[M]]
; CHECK-NEXT: br i1 [[EC2]], label %[[EXIT:.*]], label %[[OUTER]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
br label %outer
outer:
%i = phi i64 [ 0, %entry ], [ %i.next, %outer.latch ]
%xp = getelementptr i64, ptr %xs, i64 %i
%x = load i64, ptr %xp
%pi = getelementptr i8, ptr %p, i64 %i
br label %inner
inner:
%j = phi i64 [ 0, %outer ], [ %j.next, %inner ]
%off = add i64 %x, %j
%a.p = getelementptr i8, ptr %pi, i64 %off
%v = load i8, ptr %a.p
%e = sext i8 %v to i32
%b.p = getelementptr i32, ptr %q, i64 %j
store i32 %e, ptr %b.p
%j.next = add i64 %j, 1
%ec = icmp eq i64 %j.next, %n
br i1 %ec, label %outer.latch, label %inner
outer.latch:
%i.next = add i64 %i, 1
%ec2 = icmp eq i64 %i.next, %m
br i1 %ec2, label %exit, label %outer
exit:
ret void
}
; FIXME: The bounds of %src are computed from the first and last outer iteration,
; but the offset is quadratic in the outer IV (non-monotonic), so they may not
; cover all accessed addresses.
define void @expanded_bounds_non_affine_outer(ptr %dst, ptr %src, i64 %k, i64 %m, i64 %n) {
; CHECK-LABEL: define void @expanded_bounds_non_affine_outer(
; CHECK-SAME: ptr [[DST:%.*]], ptr [[SRC:%.*]], i64 [[K:%.*]], i64 [[M:%.*]], i64 [[N:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[TMP0:%.*]] = shl i64 [[K]], 2
; CHECK-NEXT: [[TMP1:%.*]] = add i64 [[TMP0]], -4
; CHECK-NEXT: [[TMP2:%.*]] = add i64 [[M]], -1
; CHECK-NEXT: [[TMP3:%.*]] = mul i64 [[TMP2]], [[TMP1]]
; CHECK-NEXT: [[TMP4:%.*]] = shl i64 [[N]], 2
; CHECK-NEXT: [[TMP5:%.*]] = add i64 [[TMP3]], [[TMP4]]
; CHECK-NEXT: [[TMP6:%.*]] = zext i64 [[TMP2]] to i65
; CHECK-NEXT: [[TMP7:%.*]] = add i64 [[M]], -2
; CHECK-NEXT: [[TMP8:%.*]] = zext i64 [[TMP7]] to i65
; CHECK-NEXT: [[TMP9:%.*]] = mul i65 [[TMP6]], [[TMP8]]
; CHECK-NEXT: [[TMP10:%.*]] = lshr i65 [[TMP9]], 1
; CHECK-NEXT: [[TMP11:%.*]] = trunc i65 [[TMP10]] to i64
; CHECK-NEXT: [[TMP12:%.*]] = shl i64 [[TMP11]], 3
; CHECK-NEXT: [[TMP13:%.*]] = sub i64 [[TMP5]], [[TMP12]]
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP13]]
; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP4]]
; CHECK-NEXT: br label %[[OUTER:.*]]
; CHECK: [[OUTER]]:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[OUTER_IV_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT: [[K_SUB:%.*]] = sub i64 [[K]], [[OUTER_IV]]
; CHECK-NEXT: [[ROW:%.*]] = mul i64 [[OUTER_IV]], [[K_SUB]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[N]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP2]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: [[TMP14:%.*]] = mul i64 [[OUTER_IV]], -8
; CHECK-NEXT: [[TMP15:%.*]] = add i64 [[TMP1]], [[TMP14]]
; CHECK-NEXT: [[STRIDE_CHECK:%.*]] = icmp slt i64 [[TMP15]], 0
; CHECK-NEXT: [[TMP16:%.*]] = or i1 [[FOUND_CONFLICT]], [[STRIDE_CHECK]]
; CHECK-NEXT: br i1 [[TMP16]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[TMP17:%.*]] = and i64 [[N]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[N]], [[TMP17]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP18:%.*]] = add i64 [[ROW]], [[INDEX]]
; CHECK-NEXT: [[TMP19:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP18]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP19]], align 4, !alias.scope [[META131:![0-9]+]]
; CHECK-NEXT: [[TMP20:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[INDEX]]
; CHECK-NEXT: [[WIDE_LOAD3:%.*]] = load <4 x i32>, ptr [[TMP20]], align 4, !alias.scope [[META134:![0-9]+]], !noalias [[META131]]
; CHECK-NEXT: [[TMP21:%.*]] = add <4 x i32> [[WIDE_LOAD3]], [[WIDE_LOAD]]
; CHECK-NEXT: store <4 x i32> [[TMP21]], ptr [[TMP20]], align 4, !alias.scope [[META134]], !noalias [[META131]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP22:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP22]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP136:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[N]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[OUTER_LATCH]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER:.*]]
; CHECK: [[INNER]]:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[IDX:%.*]] = add i64 [[ROW]], [[IV]]
; CHECK-NEXT: [[GEP_SRC:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[IDX]]
; CHECK-NEXT: [[L_SRC:%.*]] = load i32, ptr [[GEP_SRC]], align 4
; CHECK-NEXT: [[GEP_DST:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IV]]
; CHECK-NEXT: [[L_DST:%.*]] = load i32, ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[ADD:%.*]] = add i32 [[L_DST]], [[L_SRC]]
; CHECK-NEXT: store i32 [[ADD]], ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT: [[EC:%.*]] = icmp eq i64 [[IV_NEXT]], [[N]]
; CHECK-NEXT: br i1 [[EC]], label %[[OUTER_LATCH]], label %[[INNER]], !llvm.loop [[LOOP137:![0-9]+]]
; CHECK: [[OUTER_LATCH]]:
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add i64 [[OUTER_IV]], 1
; CHECK-NEXT: [[EC2:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[M]]
; CHECK-NEXT: br i1 [[EC2]], label %[[EXIT:.*]], label %[[OUTER]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
br label %outer.header
outer.header:
%outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
%k.sub = sub i64 %k, %outer.iv
%row = mul i64 %outer.iv, %k.sub
br label %inner
inner:
%iv = phi i64 [ 0, %outer.header ], [ %iv.next, %inner ]
%idx = add i64 %row, %iv
%gep.src = getelementptr inbounds i32, ptr %src, i64 %idx
%l.src = load i32, ptr %gep.src
%gep.dst = getelementptr inbounds i32, ptr %dst, i64 %iv
%l.dst = load i32, ptr %gep.dst
%add = add i32 %l.dst, %l.src
store i32 %add, ptr %gep.dst
%iv.next = add i64 %iv, 1
%ec = icmp eq i64 %iv.next, %n
br i1 %ec, label %outer.latch, label %inner
outer.latch:
%outer.iv.next = add i64 %outer.iv, 1
%ec2 = icmp eq i64 %outer.iv.next, %m
br i1 %ec2, label %exit, label %outer.header
exit:
ret void
}
; FIXME: The bounds are extrapolated to the last outer iteration, but the inner loop
; (and its accesses) may not execute in it, so the expanded pointers are not
; guaranteed to be in bounds / to cover accessed memory.
define void @expanded_bounds_inner_loop_skipped(ptr %dst, ptr %src, ptr %flags, i64 %s, i64 %m, i64 %n) {
; CHECK-LABEL: define void @expanded_bounds_inner_loop_skipped(
; CHECK-SAME: ptr [[DST:%.*]], ptr [[SRC:%.*]], ptr [[FLAGS:%.*]], i64 [[S:%.*]], i64 [[M:%.*]], i64 [[N:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[TMP0:%.*]] = shl i64 [[S]], 2
; CHECK-NEXT: [[TMP1:%.*]] = add i64 [[M]], -1
; CHECK-NEXT: [[TMP2:%.*]] = mul i64 [[S]], [[TMP1]]
; CHECK-NEXT: [[TMP3:%.*]] = shl i64 [[TMP2]], 2
; CHECK-NEXT: [[TMP4:%.*]] = shl i64 [[N]], 2
; CHECK-NEXT: [[TMP5:%.*]] = add i64 [[TMP3]], [[TMP4]]
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP5]]
; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP5]]
; CHECK-NEXT: br label %[[OUTER:.*]]
; CHECK: [[OUTER]]:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[OUTER_IV_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT: [[GEP_FLAG:%.*]] = getelementptr i8, ptr [[FLAGS]], i64 [[OUTER_IV]]
; CHECK-NEXT: [[FLAG:%.*]] = load i8, ptr [[GEP_FLAG]], align 1
; CHECK-NEXT: [[SKIP:%.*]] = icmp eq i8 [[FLAG]], 0
; CHECK-NEXT: br i1 [[SKIP]], label %[[OUTER_LATCH]], label %[[INNER_PH:.*]]
; CHECK: [[INNER_PH]]:
; CHECK-NEXT: [[ROW:%.*]] = mul i64 [[OUTER_IV]], [[S]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[N]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP2]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: [[STRIDE_CHECK:%.*]] = icmp slt i64 [[TMP0]], 0
; CHECK-NEXT: [[TMP6:%.*]] = or i1 [[FOUND_CONFLICT]], [[STRIDE_CHECK]]
; CHECK-NEXT: br i1 [[TMP6]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[TMP7:%.*]] = and i64 [[N]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[N]], [[TMP7]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP8:%.*]] = add i64 [[ROW]], [[INDEX]]
; CHECK-NEXT: [[TMP9:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP8]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP9]], align 4, !alias.scope [[META138:![0-9]+]]
; CHECK-NEXT: [[TMP10:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP8]]
; CHECK-NEXT: [[WIDE_LOAD3:%.*]] = load <4 x i32>, ptr [[TMP10]], align 4, !alias.scope [[META141:![0-9]+]], !noalias [[META138]]
; CHECK-NEXT: [[TMP11:%.*]] = add <4 x i32> [[WIDE_LOAD3]], [[WIDE_LOAD]]
; CHECK-NEXT: store <4 x i32> [[TMP11]], ptr [[TMP10]], align 4, !alias.scope [[META141]], !noalias [[META138]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP12:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP12]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP143:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[N]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[OUTER_LATCH_LOOPEXIT:.*]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[INNER_PH]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER:.*]]
; CHECK: [[INNER]]:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[IDX:%.*]] = add i64 [[ROW]], [[IV]]
; CHECK-NEXT: [[GEP_SRC:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[IDX]]
; CHECK-NEXT: [[L_SRC:%.*]] = load i32, ptr [[GEP_SRC]], align 4
; CHECK-NEXT: [[GEP_DST:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IDX]]
; CHECK-NEXT: [[L_DST:%.*]] = load i32, ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[ADD:%.*]] = add i32 [[L_DST]], [[L_SRC]]
; CHECK-NEXT: store i32 [[ADD]], ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT: [[EC:%.*]] = icmp eq i64 [[IV_NEXT]], [[N]]
; CHECK-NEXT: br i1 [[EC]], label %[[OUTER_LATCH_LOOPEXIT]], label %[[INNER]], !llvm.loop [[LOOP144:![0-9]+]]
; CHECK: [[OUTER_LATCH_LOOPEXIT]]:
; CHECK-NEXT: br label %[[OUTER_LATCH]]
; CHECK: [[OUTER_LATCH]]:
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add i64 [[OUTER_IV]], 1
; CHECK-NEXT: [[EC2:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[M]]
; CHECK-NEXT: br i1 [[EC2]], label %[[EXIT:.*]], label %[[OUTER]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
br label %outer.header
outer.header:
%outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
%gep.flag = getelementptr i8, ptr %flags, i64 %outer.iv
%flag = load i8, ptr %gep.flag
%skip = icmp eq i8 %flag, 0
br i1 %skip, label %outer.latch, label %inner.ph
inner.ph:
%row = mul i64 %outer.iv, %s
br label %inner
inner:
%iv = phi i64 [ 0, %inner.ph ], [ %iv.next, %inner ]
%idx = add i64 %row, %iv
%gep.src = getelementptr inbounds i32, ptr %src, i64 %idx
%l.src = load i32, ptr %gep.src
%gep.dst = getelementptr inbounds i32, ptr %dst, i64 %idx
%l.dst = load i32, ptr %gep.dst
%add = add i32 %l.dst, %l.src
store i32 %add, ptr %gep.dst
%iv.next = add i64 %iv, 1
%ec = icmp eq i64 %iv.next, %n
br i1 %ec, label %outer.latch, label %inner
outer.latch:
%outer.iv.next = add i64 %outer.iv, 1
%ec2 = icmp eq i64 %outer.iv.next, %m
br i1 %ec2, label %exit, label %outer.header
exit:
ret void
}
; FIXME: %src is only accessed in outer iterations where %skip is false, but its
; bounds are extrapolated to the last outer iteration, which is not guaranteed to
; access it.
define void @expanded_bounds_access_via_phi(ptr %dst, ptr %src, ptr %other, ptr %flags, i64 %s, i64 %m, i64 %n) {
; CHECK-LABEL: define void @expanded_bounds_access_via_phi(
; CHECK-SAME: ptr [[DST:%.*]], ptr [[SRC:%.*]], ptr [[OTHER:%.*]], ptr [[FLAGS:%.*]], i64 [[S:%.*]], i64 [[M:%.*]], i64 [[N:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[TMP0:%.*]] = shl i64 [[S]], 2
; CHECK-NEXT: [[TMP1:%.*]] = shl i64 [[N]], 2
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[OTHER]], i64 [[TMP1]]
; CHECK-NEXT: [[TMP2:%.*]] = add i64 [[M]], -1
; CHECK-NEXT: [[TMP3:%.*]] = mul i64 [[S]], [[TMP2]]
; CHECK-NEXT: [[TMP4:%.*]] = shl i64 [[TMP3]], 2
; CHECK-NEXT: [[TMP5:%.*]] = add i64 [[TMP4]], [[TMP1]]
; CHECK-NEXT: [[SCEVGEP6:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP5]]
; CHECK-NEXT: [[SCEVGEP7:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP1]]
; CHECK-NEXT: br label %[[OUTER:.*]]
; CHECK: [[OUTER]]:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[OUTER_IV_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT: [[GEP_FLAG:%.*]] = getelementptr i8, ptr [[FLAGS]], i64 [[OUTER_IV]]
; CHECK-NEXT: [[FLAG:%.*]] = load i8, ptr [[GEP_FLAG]], align 1
; CHECK-NEXT: [[SKIP:%.*]] = icmp eq i8 [[FLAG]], 0
; CHECK-NEXT: [[ROW:%.*]] = mul i64 [[OUTER_IV]], [[S]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[N]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP6]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP7]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: [[STRIDE_CHECK:%.*]] = icmp slt i64 [[TMP0]], 0
; CHECK-NEXT: [[TMP6:%.*]] = or i1 [[FOUND_CONFLICT]], [[STRIDE_CHECK]]
; CHECK-NEXT: [[BOUND08:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP]]
; CHECK-NEXT: [[BOUND19:%.*]] = icmp ult ptr [[OTHER]], [[SCEVGEP7]]
; CHECK-NEXT: [[FOUND_CONFLICT10:%.*]] = and i1 [[BOUND08]], [[BOUND19]]
; CHECK-NEXT: [[CONFLICT_RDX:%.*]] = or i1 [[TMP6]], [[FOUND_CONFLICT10]]
; CHECK-NEXT: br i1 [[CONFLICT_RDX]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[TMP7:%.*]] = and i64 [[N]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[N]], [[TMP7]]
; CHECK-NEXT: [[BROADCAST_SPLATINSERT:%.*]] = insertelement <4 x i64> poison, i64 [[ROW]], i64 0
; CHECK-NEXT: [[BROADCAST_SPLAT:%.*]] = shufflevector <4 x i64> [[BROADCAST_SPLATINSERT]], <4 x i64> poison, <4 x i32> zeroinitializer
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[VEC_IND:%.*]] = phi <4 x i64> [ <i64 0, i64 1, i64 2, i64 3>, %[[VECTOR_PH]] ], [ [[VEC_IND_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP8:%.*]] = add <4 x i64> [[BROADCAST_SPLAT]], [[VEC_IND]]
; CHECK-NEXT: [[WIDE_GEP:%.*]] = getelementptr inbounds [4 x i8], ptr [[SRC]], <4 x i64> [[TMP8]]
; CHECK-NEXT: [[WIDE_GEP11:%.*]] = getelementptr inbounds [4 x i8], ptr [[OTHER]], <4 x i64> [[VEC_IND]]
; CHECK-NEXT: [[PREDPHI:%.*]] = select i1 [[SKIP]], <4 x ptr> [[WIDE_GEP11]], <4 x ptr> [[WIDE_GEP]]
; CHECK-NEXT: [[TMP9:%.*]] = extractelement <4 x ptr> [[PREDPHI]], i64 0
; CHECK-NEXT: [[TMP10:%.*]] = load i32, ptr [[TMP9]], align 4
; CHECK-NEXT: [[TMP11:%.*]] = extractelement <4 x ptr> [[PREDPHI]], i64 1
; CHECK-NEXT: [[TMP12:%.*]] = load i32, ptr [[TMP11]], align 4
; CHECK-NEXT: [[TMP13:%.*]] = extractelement <4 x ptr> [[PREDPHI]], i64 2
; CHECK-NEXT: [[TMP14:%.*]] = load i32, ptr [[TMP13]], align 4
; CHECK-NEXT: [[TMP15:%.*]] = extractelement <4 x ptr> [[PREDPHI]], i64 3
; CHECK-NEXT: [[TMP16:%.*]] = load i32, ptr [[TMP15]], align 4
; CHECK-NEXT: [[TMP17:%.*]] = insertelement <4 x i32> poison, i32 [[TMP10]], i64 0
; CHECK-NEXT: [[TMP18:%.*]] = insertelement <4 x i32> [[TMP17]], i32 [[TMP12]], i64 1
; CHECK-NEXT: [[TMP19:%.*]] = insertelement <4 x i32> [[TMP18]], i32 [[TMP14]], i64 2
; CHECK-NEXT: [[TMP20:%.*]] = insertelement <4 x i32> [[TMP19]], i32 [[TMP16]], i64 3
; CHECK-NEXT: [[TMP21:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[INDEX]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP21]], align 4, !alias.scope [[META145:![0-9]+]], !noalias [[META148:![0-9]+]]
; CHECK-NEXT: [[TMP22:%.*]] = add <4 x i32> [[WIDE_LOAD]], [[TMP20]]
; CHECK-NEXT: store <4 x i32> [[TMP22]], ptr [[TMP21]], align 4, !alias.scope [[META145]], !noalias [[META148]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[VEC_IND_NEXT]] = add <4 x i64> [[VEC_IND]], splat (i64 4)
; CHECK-NEXT: [[TMP23:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP23]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP151:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[N]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[OUTER_LATCH]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER:.*]]
; CHECK: [[INNER]]:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], %[[INNER_LATCH:.*]] ]
; CHECK-NEXT: [[IDX:%.*]] = add i64 [[ROW]], [[IV]]
; CHECK-NEXT: [[GEP_SRC:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[IDX]]
; CHECK-NEXT: [[GEP_OTHER:%.*]] = getelementptr inbounds i32, ptr [[OTHER]], i64 [[IV]]
; CHECK-NEXT: br i1 [[SKIP]], label %[[INNER_LATCH]], label %[[THEN:.*]]
; CHECK: [[THEN]]:
; CHECK-NEXT: br label %[[INNER_LATCH]]
; CHECK: [[INNER_LATCH]]:
; CHECK-NEXT: [[PTR:%.*]] = phi ptr [ [[GEP_OTHER]], %[[INNER]] ], [ [[GEP_SRC]], %[[THEN]] ]
; CHECK-NEXT: [[L_SRC:%.*]] = load i32, ptr [[PTR]], align 4
; CHECK-NEXT: [[GEP_DST:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IV]]
; CHECK-NEXT: [[L_DST:%.*]] = load i32, ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[ADD:%.*]] = add i32 [[L_DST]], [[L_SRC]]
; CHECK-NEXT: store i32 [[ADD]], ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT: [[EC:%.*]] = icmp eq i64 [[IV_NEXT]], [[N]]
; CHECK-NEXT: br i1 [[EC]], label %[[OUTER_LATCH]], label %[[INNER]], !llvm.loop [[LOOP152:![0-9]+]]
; CHECK: [[OUTER_LATCH]]:
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add i64 [[OUTER_IV]], 1
; CHECK-NEXT: [[EC2:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[M]]
; CHECK-NEXT: br i1 [[EC2]], label %[[EXIT:.*]], label %[[OUTER]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
br label %outer.header
outer.header:
%outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
%gep.flag = getelementptr i8, ptr %flags, i64 %outer.iv
%flag = load i8, ptr %gep.flag
%skip = icmp eq i8 %flag, 0
%row = mul i64 %outer.iv, %s
br label %inner.header
inner.header:
%iv = phi i64 [ 0, %outer.header ], [ %iv.next, %inner.latch ]
%idx = add i64 %row, %iv
%gep.src = getelementptr inbounds i32, ptr %src, i64 %idx
%gep.other = getelementptr inbounds i32, ptr %other, i64 %iv
br i1 %skip, label %inner.latch, label %then
then:
br label %inner.latch
inner.latch:
%ptr = phi ptr [ %gep.other, %inner.header ], [ %gep.src, %then ]
%l.src = load i32, ptr %ptr
%gep.dst = getelementptr inbounds i32, ptr %dst, i64 %iv
%l.dst = load i32, ptr %gep.dst
%add = add i32 %l.dst, %l.src
store i32 %add, ptr %gep.dst
%iv.next = add i64 %iv, 1
%ec = icmp eq i64 %iv.next, %n
br i1 %ec, label %outer.latch, label %inner.header
outer.latch:
%outer.iv.next = add i64 %outer.iv, 1
%ec2 = icmp eq i64 %outer.iv.next, %m
br i1 %ec2, label %exit, label %outer.header
exit:
ret void
}
; FIXME: The cycle may never terminate, so later outer iterations may never run,
; but the bounds are extrapolated to the last outer iteration.
define void @expanded_bounds_irreducible_cycle(ptr %dst, ptr %src, ptr %flags, i64 %s, i64 %m, i64 %n) {
; CHECK-LABEL: define void @expanded_bounds_irreducible_cycle(
; CHECK-SAME: ptr [[DST:%.*]], ptr [[SRC:%.*]], ptr [[FLAGS:%.*]], i64 [[S:%.*]], i64 [[M:%.*]], i64 [[N:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[TMP0:%.*]] = shl i64 [[S]], 2
; CHECK-NEXT: [[TMP1:%.*]] = add i64 [[M]], -1
; CHECK-NEXT: [[TMP2:%.*]] = mul i64 [[S]], [[TMP1]]
; CHECK-NEXT: [[TMP3:%.*]] = shl i64 [[TMP2]], 2
; CHECK-NEXT: [[TMP4:%.*]] = shl i64 [[N]], 2
; CHECK-NEXT: [[TMP5:%.*]] = add i64 [[TMP3]], [[TMP4]]
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP5]]
; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP5]]
; CHECK-NEXT: br label %[[OUTER:.*]]
; CHECK: [[OUTER]]:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[OUTER_IV_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT: [[GEP_FLAG:%.*]] = getelementptr i8, ptr [[FLAGS]], i64 [[OUTER_IV]]
; CHECK-NEXT: [[FLAG:%.*]] = load i8, ptr [[GEP_FLAG]], align 1
; CHECK-NEXT: [[C:%.*]] = icmp eq i8 [[FLAG]], 0
; CHECK-NEXT: br i1 [[C]], label %[[CYCLE_A:.*]], label %[[CYCLE_B:.*]]
; CHECK: [[CYCLE_A]]:
; CHECK-NEXT: br label %[[CYCLE_B]]
; CHECK: [[CYCLE_B]]:
; CHECK-NEXT: br i1 [[C]], label %[[CYCLE_A]], label %[[INNER_PH:.*]]
; CHECK: [[INNER_PH]]:
; CHECK-NEXT: [[ROW:%.*]] = mul i64 [[OUTER_IV]], [[S]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[N]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP2]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: [[STRIDE_CHECK:%.*]] = icmp slt i64 [[TMP0]], 0
; CHECK-NEXT: [[TMP6:%.*]] = or i1 [[FOUND_CONFLICT]], [[STRIDE_CHECK]]
; CHECK-NEXT: br i1 [[TMP6]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[TMP7:%.*]] = and i64 [[N]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[N]], [[TMP7]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP8:%.*]] = add i64 [[ROW]], [[INDEX]]
; CHECK-NEXT: [[TMP9:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP8]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP9]], align 4, !alias.scope [[META153:![0-9]+]]
; CHECK-NEXT: [[TMP10:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP8]]
; CHECK-NEXT: [[WIDE_LOAD3:%.*]] = load <4 x i32>, ptr [[TMP10]], align 4, !alias.scope [[META156:![0-9]+]], !noalias [[META153]]
; CHECK-NEXT: [[TMP11:%.*]] = add <4 x i32> [[WIDE_LOAD3]], [[WIDE_LOAD]]
; CHECK-NEXT: store <4 x i32> [[TMP11]], ptr [[TMP10]], align 4, !alias.scope [[META156]], !noalias [[META153]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP12:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP12]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP158:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[N]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[OUTER_LATCH]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[INNER_PH]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER:.*]]
; CHECK: [[INNER]]:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[IDX:%.*]] = add i64 [[ROW]], [[IV]]
; CHECK-NEXT: [[GEP_SRC:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[IDX]]
; CHECK-NEXT: [[L_SRC:%.*]] = load i32, ptr [[GEP_SRC]], align 4
; CHECK-NEXT: [[GEP_DST:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IDX]]
; CHECK-NEXT: [[L_DST:%.*]] = load i32, ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[ADD:%.*]] = add i32 [[L_DST]], [[L_SRC]]
; CHECK-NEXT: store i32 [[ADD]], ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT: [[EC:%.*]] = icmp eq i64 [[IV_NEXT]], [[N]]
; CHECK-NEXT: br i1 [[EC]], label %[[OUTER_LATCH]], label %[[INNER]], !llvm.loop [[LOOP159:![0-9]+]]
; CHECK: [[OUTER_LATCH]]:
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add i64 [[OUTER_IV]], 1
; CHECK-NEXT: [[EC2:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[M]]
; CHECK-NEXT: br i1 [[EC2]], label %[[EXIT:.*]], label %[[OUTER]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
br label %outer.header
outer.header:
%outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
%gep.flag = getelementptr i8, ptr %flags, i64 %outer.iv
%flag = load i8, ptr %gep.flag
%c = icmp eq i8 %flag, 0
br i1 %c, label %cycle.a, label %cycle.b
cycle.a:
br label %cycle.b
cycle.b:
br i1 %c, label %cycle.a, label %inner.ph
inner.ph:
%row = mul i64 %outer.iv, %s
br label %inner
inner:
%iv = phi i64 [ 0, %inner.ph ], [ %iv.next, %inner ]
%idx = add i64 %row, %iv
%gep.src = getelementptr inbounds i32, ptr %src, i64 %idx
%l.src = load i32, ptr %gep.src
%gep.dst = getelementptr inbounds i32, ptr %dst, i64 %idx
%l.dst = load i32, ptr %gep.dst
%add = add i32 %l.dst, %l.src
store i32 %add, ptr %gep.dst
%iv.next = add i64 %iv, 1
%ec = icmp eq i64 %iv.next, %n
br i1 %ec, label %outer.latch, label %inner
outer.latch:
%outer.iv.next = add i64 %outer.iv, 1
%ec2 = icmp eq i64 %outer.iv.next, %m
br i1 %ec2, label %exit, label %outer.header
exit:
ret void
}
; FIXME: The outer loop may exit before the last iteration, but the bounds are
; extrapolated to the last outer iteration.
define void @expanded_bounds_outer_early_exit(ptr %dst, ptr %src, i64 %s, i64 %m, i64 %n, i64 %stop) {
; CHECK-LABEL: define void @expanded_bounds_outer_early_exit(
; CHECK-SAME: ptr [[DST:%.*]], ptr [[SRC:%.*]], i64 [[S:%.*]], i64 [[M:%.*]], i64 [[N:%.*]], i64 [[STOP:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[TMP0:%.*]] = shl i64 [[S]], 2
; CHECK-NEXT: [[TMP1:%.*]] = add i64 [[M]], -1
; CHECK-NEXT: [[TMP2:%.*]] = mul i64 [[S]], [[TMP1]]
; CHECK-NEXT: [[TMP3:%.*]] = shl i64 [[TMP2]], 2
; CHECK-NEXT: [[TMP4:%.*]] = shl i64 [[N]], 2
; CHECK-NEXT: [[TMP5:%.*]] = add i64 [[TMP3]], [[TMP4]]
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP5]]
; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP5]]
; CHECK-NEXT: br label %[[OUTER:.*]]
; CHECK: [[OUTER]]:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[OUTER_IV_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT: [[EARLY:%.*]] = icmp eq i64 [[OUTER_IV]], [[STOP]]
; CHECK-NEXT: br i1 [[EARLY]], label %[[EXIT:.*]], label %[[INNER_PH:.*]]
; CHECK: [[INNER_PH]]:
; CHECK-NEXT: [[ROW:%.*]] = mul i64 [[OUTER_IV]], [[S]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[N]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP2]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: [[STRIDE_CHECK:%.*]] = icmp slt i64 [[TMP0]], 0
; CHECK-NEXT: [[TMP6:%.*]] = or i1 [[FOUND_CONFLICT]], [[STRIDE_CHECK]]
; CHECK-NEXT: br i1 [[TMP6]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[TMP7:%.*]] = and i64 [[N]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[N]], [[TMP7]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP8:%.*]] = add i64 [[ROW]], [[INDEX]]
; CHECK-NEXT: [[TMP9:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP8]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP9]], align 4, !alias.scope [[META160:![0-9]+]]
; CHECK-NEXT: [[TMP10:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP8]]
; CHECK-NEXT: [[WIDE_LOAD3:%.*]] = load <4 x i32>, ptr [[TMP10]], align 4, !alias.scope [[META163:![0-9]+]], !noalias [[META160]]
; CHECK-NEXT: [[TMP11:%.*]] = add <4 x i32> [[WIDE_LOAD3]], [[WIDE_LOAD]]
; CHECK-NEXT: store <4 x i32> [[TMP11]], ptr [[TMP10]], align 4, !alias.scope [[META163]], !noalias [[META160]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP12:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP12]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP165:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[N]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[OUTER_LATCH]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[INNER_PH]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER:.*]]
; CHECK: [[INNER]]:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[IDX:%.*]] = add i64 [[ROW]], [[IV]]
; CHECK-NEXT: [[GEP_SRC:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[IDX]]
; CHECK-NEXT: [[L_SRC:%.*]] = load i32, ptr [[GEP_SRC]], align 4
; CHECK-NEXT: [[GEP_DST:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IDX]]
; CHECK-NEXT: [[L_DST:%.*]] = load i32, ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[ADD:%.*]] = add i32 [[L_DST]], [[L_SRC]]
; CHECK-NEXT: store i32 [[ADD]], ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT: [[EC:%.*]] = icmp eq i64 [[IV_NEXT]], [[N]]
; CHECK-NEXT: br i1 [[EC]], label %[[OUTER_LATCH]], label %[[INNER]], !llvm.loop [[LOOP166:![0-9]+]]
; CHECK: [[OUTER_LATCH]]:
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add i64 [[OUTER_IV]], 1
; CHECK-NEXT: [[EC2:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[M]]
; CHECK-NEXT: br i1 [[EC2]], label %[[EXIT]], label %[[OUTER]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
br label %outer.header
outer.header:
%outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
%early = icmp eq i64 %outer.iv, %stop
br i1 %early, label %exit, label %inner.ph
inner.ph:
%row = mul i64 %outer.iv, %s
br label %inner
inner:
%iv = phi i64 [ 0, %inner.ph ], [ %iv.next, %inner ]
%idx = add i64 %row, %iv
%gep.src = getelementptr inbounds i32, ptr %src, i64 %idx
%l.src = load i32, ptr %gep.src
%gep.dst = getelementptr inbounds i32, ptr %dst, i64 %idx
%l.dst = load i32, ptr %gep.dst
%add = add i32 %l.dst, %l.src
store i32 %add, ptr %gep.dst
%iv.next = add i64 %iv, 1
%ec = icmp eq i64 %iv.next, %n
br i1 %ec, label %outer.latch, label %inner
outer.latch:
%outer.iv.next = add i64 %outer.iv, 1
%ec2 = icmp eq i64 %outer.iv.next, %m
br i1 %ec2, label %exit, label %outer.header
exit:
ret void
}
; FIXME: Without inbounds on %src.row, the pointers expanded to the last outer
; iteration may wrap, so they are not known to cover the accessed range.
define void @expanded_bounds_outer_gep_not_inbounds(ptr %dst, ptr %src, i64 %s, i64 %m, i64 %n) {
; CHECK-LABEL: define void @expanded_bounds_outer_gep_not_inbounds(
; CHECK-SAME: ptr [[DST:%.*]], ptr [[SRC:%.*]], i64 [[S:%.*]], i64 [[M:%.*]], i64 [[N:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[TMP0:%.*]] = shl i64 [[S]], 2
; CHECK-NEXT: [[TMP1:%.*]] = add i64 [[M]], -1
; CHECK-NEXT: [[TMP2:%.*]] = mul i64 [[S]], [[TMP1]]
; CHECK-NEXT: [[TMP3:%.*]] = shl i64 [[TMP2]], 2
; CHECK-NEXT: [[TMP4:%.*]] = shl i64 [[N]], 2
; CHECK-NEXT: [[TMP5:%.*]] = add i64 [[TMP3]], [[TMP4]]
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP5]]
; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP5]]
; CHECK-NEXT: br label %[[OUTER:.*]]
; CHECK: [[OUTER]]:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[OUTER_IV_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT: [[ROW:%.*]] = mul i64 [[OUTER_IV]], [[S]]
; CHECK-NEXT: [[SRC_ROW:%.*]] = getelementptr i32, ptr [[SRC]], i64 [[ROW]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[N]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP2]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: [[STRIDE_CHECK:%.*]] = icmp slt i64 [[TMP0]], 0
; CHECK-NEXT: [[TMP6:%.*]] = or i1 [[FOUND_CONFLICT]], [[STRIDE_CHECK]]
; CHECK-NEXT: br i1 [[TMP6]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[TMP7:%.*]] = and i64 [[N]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[N]], [[TMP7]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP8:%.*]] = getelementptr inbounds i32, ptr [[SRC_ROW]], i64 [[INDEX]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP8]], align 4, !alias.scope [[META167:![0-9]+]]
; CHECK-NEXT: [[TMP9:%.*]] = add i64 [[ROW]], [[INDEX]]
; CHECK-NEXT: [[TMP10:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP9]]
; CHECK-NEXT: [[WIDE_LOAD3:%.*]] = load <4 x i32>, ptr [[TMP10]], align 4, !alias.scope [[META170:![0-9]+]], !noalias [[META167]]
; CHECK-NEXT: [[TMP11:%.*]] = add <4 x i32> [[WIDE_LOAD3]], [[WIDE_LOAD]]
; CHECK-NEXT: store <4 x i32> [[TMP11]], ptr [[TMP10]], align 4, !alias.scope [[META170]], !noalias [[META167]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP12:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP12]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP172:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[N]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[OUTER_LATCH]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER:.*]]
; CHECK: [[INNER]]:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[GEP_SRC:%.*]] = getelementptr inbounds i32, ptr [[SRC_ROW]], i64 [[IV]]
; CHECK-NEXT: [[L_SRC:%.*]] = load i32, ptr [[GEP_SRC]], align 4
; CHECK-NEXT: [[IDX:%.*]] = add i64 [[ROW]], [[IV]]
; CHECK-NEXT: [[GEP_DST:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IDX]]
; CHECK-NEXT: [[L_DST:%.*]] = load i32, ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[ADD:%.*]] = add i32 [[L_DST]], [[L_SRC]]
; CHECK-NEXT: store i32 [[ADD]], ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT: [[EC:%.*]] = icmp eq i64 [[IV_NEXT]], [[N]]
; CHECK-NEXT: br i1 [[EC]], label %[[OUTER_LATCH]], label %[[INNER]], !llvm.loop [[LOOP173:![0-9]+]]
; CHECK: [[OUTER_LATCH]]:
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add i64 [[OUTER_IV]], 1
; CHECK-NEXT: [[EC2:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[M]]
; CHECK-NEXT: br i1 [[EC2]], label %[[EXIT:.*]], label %[[OUTER]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
br label %outer.header
outer.header:
%outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
%row = mul i64 %outer.iv, %s
%src.row = getelementptr i32, ptr %src, i64 %row
br label %inner
inner:
%iv = phi i64 [ 0, %outer.header ], [ %iv.next, %inner ]
%gep.src = getelementptr inbounds i32, ptr %src.row, i64 %iv
%l.src = load i32, ptr %gep.src
%idx = add i64 %row, %iv
%gep.dst = getelementptr inbounds i32, ptr %dst, i64 %idx
%l.dst = load i32, ptr %gep.dst
%add = add i32 %l.dst, %l.src
store i32 %add, ptr %gep.dst
%iv.next = add i64 %iv, 1
%ec = icmp eq i64 %iv.next, %n
br i1 %ec, label %outer.latch, label %inner
outer.latch:
%outer.iv.next = add i64 %outer.iv, 1
%ec2 = icmp eq i64 %outer.iv.next, %m
br i1 %ec2, label %exit, label %outer.header
exit:
ret void
}
; FIXME: The bounds of the select of two pointers are extrapolated to the last outer
; iteration, which is not known to cover the accessed range of both.
define void @expanded_bounds_forked_ptr(ptr %dst, ptr %src, i64 %s, i64 %m, i64 %n, i64 %k) {
; CHECK-LABEL: define void @expanded_bounds_forked_ptr(
; CHECK-SAME: ptr [[DST:%.*]], ptr [[SRC:%.*]], i64 [[S:%.*]], i64 [[M:%.*]], i64 [[N:%.*]], i64 [[K:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[TMP0:%.*]] = shl i64 [[S]], 2
; CHECK-NEXT: [[TMP1:%.*]] = add i64 [[M]], -1
; CHECK-NEXT: [[TMP2:%.*]] = mul i64 [[S]], [[TMP1]]
; CHECK-NEXT: [[TMP3:%.*]] = shl i64 [[TMP2]], 2
; CHECK-NEXT: [[TMP4:%.*]] = shl i64 [[N]], 2
; CHECK-NEXT: [[TMP5:%.*]] = add i64 [[TMP3]], [[TMP4]]
; CHECK-NEXT: [[TMP6:%.*]] = add i64 [[TMP5]], 4
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP6]]
; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP5]]
; CHECK-NEXT: br label %[[OUTER:.*]]
; CHECK: [[OUTER]]:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[OUTER_IV_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT: [[ROW:%.*]] = mul i64 [[OUTER_IV]], [[S]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[N]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[TMP7:%.*]] = freeze ptr [[SRC]]
; CHECK-NEXT: [[TMP8:%.*]] = freeze ptr [[SCEVGEP]]
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[TMP8]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[TMP7]], [[SCEVGEP2]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: [[STRIDE_CHECK:%.*]] = icmp slt i64 [[TMP0]], 0
; CHECK-NEXT: [[TMP9:%.*]] = or i1 [[FOUND_CONFLICT]], [[STRIDE_CHECK]]
; CHECK-NEXT: br i1 [[TMP9]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[TMP10:%.*]] = and i64 [[N]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[N]], [[TMP10]]
; CHECK-NEXT: [[BROADCAST_SPLATINSERT:%.*]] = insertelement <4 x i64> poison, i64 [[ROW]], i64 0
; CHECK-NEXT: [[BROADCAST_SPLAT:%.*]] = shufflevector <4 x i64> [[BROADCAST_SPLATINSERT]], <4 x i64> poison, <4 x i32> zeroinitializer
; CHECK-NEXT: [[BROADCAST_SPLATINSERT3:%.*]] = insertelement <4 x i64> poison, i64 [[K]], i64 0
; CHECK-NEXT: [[BROADCAST_SPLAT4:%.*]] = shufflevector <4 x i64> [[BROADCAST_SPLATINSERT3]], <4 x i64> poison, <4 x i32> zeroinitializer
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[VEC_IND:%.*]] = phi <4 x i64> [ <i64 0, i64 1, i64 2, i64 3>, %[[VECTOR_PH]] ], [ [[VEC_IND_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP11:%.*]] = add <4 x i64> [[BROADCAST_SPLAT]], [[VEC_IND]]
; CHECK-NEXT: [[TMP12:%.*]] = extractelement <4 x i64> [[TMP11]], i64 0
; CHECK-NEXT: [[TMP13:%.*]] = add <4 x i64> [[TMP11]], splat (i64 1)
; CHECK-NEXT: [[TMP14:%.*]] = icmp ult <4 x i64> [[VEC_IND]], [[BROADCAST_SPLAT4]]
; CHECK-NEXT: [[TMP15:%.*]] = select <4 x i1> [[TMP14]], <4 x i64> [[TMP11]], <4 x i64> [[TMP13]]
; CHECK-NEXT: [[TMP16:%.*]] = extractelement <4 x i64> [[TMP15]], i64 0
; CHECK-NEXT: [[TMP17:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP16]]
; CHECK-NEXT: [[TMP18:%.*]] = extractelement <4 x i64> [[TMP15]], i64 1
; CHECK-NEXT: [[TMP19:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP18]]
; CHECK-NEXT: [[TMP20:%.*]] = extractelement <4 x i64> [[TMP15]], i64 2
; CHECK-NEXT: [[TMP21:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP20]]
; CHECK-NEXT: [[TMP22:%.*]] = extractelement <4 x i64> [[TMP15]], i64 3
; CHECK-NEXT: [[TMP23:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP22]]
; CHECK-NEXT: [[TMP24:%.*]] = load i32, ptr [[TMP17]], align 4, !alias.scope [[META174:![0-9]+]]
; CHECK-NEXT: [[TMP25:%.*]] = load i32, ptr [[TMP19]], align 4, !alias.scope [[META174]]
; CHECK-NEXT: [[TMP26:%.*]] = load i32, ptr [[TMP21]], align 4, !alias.scope [[META174]]
; CHECK-NEXT: [[TMP27:%.*]] = load i32, ptr [[TMP23]], align 4, !alias.scope [[META174]]
; CHECK-NEXT: [[TMP28:%.*]] = insertelement <4 x i32> poison, i32 [[TMP24]], i64 0
; CHECK-NEXT: [[TMP29:%.*]] = insertelement <4 x i32> [[TMP28]], i32 [[TMP25]], i64 1
; CHECK-NEXT: [[TMP30:%.*]] = insertelement <4 x i32> [[TMP29]], i32 [[TMP26]], i64 2
; CHECK-NEXT: [[TMP31:%.*]] = insertelement <4 x i32> [[TMP30]], i32 [[TMP27]], i64 3
; CHECK-NEXT: [[TMP32:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP12]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP32]], align 4, !alias.scope [[META177:![0-9]+]], !noalias [[META174]]
; CHECK-NEXT: [[TMP33:%.*]] = add <4 x i32> [[WIDE_LOAD]], [[TMP31]]
; CHECK-NEXT: store <4 x i32> [[TMP33]], ptr [[TMP32]], align 4, !alias.scope [[META177]], !noalias [[META174]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[VEC_IND_NEXT]] = add <4 x i64> [[VEC_IND]], splat (i64 4)
; CHECK-NEXT: [[TMP34:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP34]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP179:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[N]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[OUTER_LATCH]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER:.*]]
; CHECK: [[INNER]]:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[IDX:%.*]] = add i64 [[ROW]], [[IV]]
; CHECK-NEXT: [[IDX_1:%.*]] = add i64 [[IDX]], 1
; CHECK-NEXT: [[C:%.*]] = icmp ult i64 [[IV]], [[K]]
; CHECK-NEXT: [[SEL:%.*]] = select i1 [[C]], i64 [[IDX]], i64 [[IDX_1]]
; CHECK-NEXT: [[GEP_SRC:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[SEL]]
; CHECK-NEXT: [[L_SRC:%.*]] = load i32, ptr [[GEP_SRC]], align 4
; CHECK-NEXT: [[GEP_DST:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IDX]]
; CHECK-NEXT: [[L_DST:%.*]] = load i32, ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[ADD:%.*]] = add i32 [[L_DST]], [[L_SRC]]
; CHECK-NEXT: store i32 [[ADD]], ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT: [[EC:%.*]] = icmp eq i64 [[IV_NEXT]], [[N]]
; CHECK-NEXT: br i1 [[EC]], label %[[OUTER_LATCH]], label %[[INNER]], !llvm.loop [[LOOP180:![0-9]+]]
; CHECK: [[OUTER_LATCH]]:
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add i64 [[OUTER_IV]], 1
; CHECK-NEXT: [[EC2:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[M]]
; CHECK-NEXT: br i1 [[EC2]], label %[[EXIT:.*]], label %[[OUTER]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
br label %outer.header
outer.header:
%outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
%row = mul i64 %outer.iv, %s
br label %inner
inner:
%iv = phi i64 [ 0, %outer.header ], [ %iv.next, %inner ]
%idx = add i64 %row, %iv
%idx.1 = add i64 %idx, 1
%c = icmp ult i64 %iv, %k
%sel = select i1 %c, i64 %idx, i64 %idx.1
%gep.src = getelementptr inbounds i32, ptr %src, i64 %sel
%l.src = load i32, ptr %gep.src
%gep.dst = getelementptr inbounds i32, ptr %dst, i64 %idx
%l.dst = load i32, ptr %gep.dst
%add = add i32 %l.dst, %l.src
store i32 %add, ptr %gep.dst
%iv.next = add i64 %iv, 1
%ec = icmp eq i64 %iv.next, %n
br i1 %ec, label %outer.latch, label %inner
outer.latch:
%outer.iv.next = add i64 %outer.iv, 1
%ec2 = icmp eq i64 %outer.iv.next, %m
br i1 %ec2, label %exit, label %outer.header
exit:
ret void
}
; FIXME: Without inbounds on %dst.row.next, the pointers expanded to the last outer
; iteration may wrap, so they are not known to cover the accessed range.
define void @expanded_bounds_ptr_iv_not_inbounds(ptr %dst, ptr %src, i64 %s, i64 %m, i64 %n) {
; CHECK-LABEL: define void @expanded_bounds_ptr_iv_not_inbounds(
; CHECK-SAME: ptr [[DST:%.*]], ptr [[SRC:%.*]], i64 [[S:%.*]], i64 [[M:%.*]], i64 [[N:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[TMP0:%.*]] = shl i64 [[S]], 2
; CHECK-NEXT: [[TMP1:%.*]] = add i64 [[M]], -1
; CHECK-NEXT: [[TMP2:%.*]] = mul i64 [[S]], [[TMP1]]
; CHECK-NEXT: [[TMP3:%.*]] = shl i64 [[TMP2]], 2
; CHECK-NEXT: [[TMP4:%.*]] = shl i64 [[N]], 2
; CHECK-NEXT: [[TMP5:%.*]] = add i64 [[TMP3]], [[TMP4]]
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP5]]
; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP5]]
; CHECK-NEXT: br label %[[OUTER:.*]]
; CHECK: [[OUTER]]:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[OUTER_IV_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT: [[DST_ROW:%.*]] = phi ptr [ [[DST]], %[[ENTRY]] ], [ [[DST_ROW_NEXT:%.*]], %[[OUTER_LATCH]] ]
; CHECK-NEXT: [[ROW:%.*]] = mul i64 [[OUTER_IV]], [[S]]
; CHECK-NEXT: [[SRC_ROW:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[ROW]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[N]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP2]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: [[STRIDE_CHECK:%.*]] = icmp slt i64 [[TMP0]], 0
; CHECK-NEXT: [[TMP6:%.*]] = or i1 [[FOUND_CONFLICT]], [[STRIDE_CHECK]]
; CHECK-NEXT: br i1 [[TMP6]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[TMP7:%.*]] = and i64 [[N]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[N]], [[TMP7]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP8:%.*]] = getelementptr inbounds i32, ptr [[SRC_ROW]], i64 [[INDEX]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP8]], align 4, !alias.scope [[META181:![0-9]+]]
; CHECK-NEXT: [[TMP9:%.*]] = getelementptr inbounds i32, ptr [[DST_ROW]], i64 [[INDEX]]
; CHECK-NEXT: [[WIDE_LOAD3:%.*]] = load <4 x i32>, ptr [[TMP9]], align 4, !alias.scope [[META184:![0-9]+]], !noalias [[META181]]
; CHECK-NEXT: [[TMP10:%.*]] = add <4 x i32> [[WIDE_LOAD3]], [[WIDE_LOAD]]
; CHECK-NEXT: store <4 x i32> [[TMP10]], ptr [[TMP9]], align 4, !alias.scope [[META184]], !noalias [[META181]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP11:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP11]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP186:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[N]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[OUTER_LATCH]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER:.*]]
; CHECK: [[INNER]]:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[GEP_SRC:%.*]] = getelementptr inbounds i32, ptr [[SRC_ROW]], i64 [[IV]]
; CHECK-NEXT: [[L_SRC:%.*]] = load i32, ptr [[GEP_SRC]], align 4
; CHECK-NEXT: [[GEP_DST:%.*]] = getelementptr inbounds i32, ptr [[DST_ROW]], i64 [[IV]]
; CHECK-NEXT: [[L_DST:%.*]] = load i32, ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[ADD:%.*]] = add i32 [[L_DST]], [[L_SRC]]
; CHECK-NEXT: store i32 [[ADD]], ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT: [[EC:%.*]] = icmp eq i64 [[IV_NEXT]], [[N]]
; CHECK-NEXT: br i1 [[EC]], label %[[OUTER_LATCH]], label %[[INNER]], !llvm.loop [[LOOP187:![0-9]+]]
; CHECK: [[OUTER_LATCH]]:
; CHECK-NEXT: [[DST_ROW_NEXT]] = getelementptr i32, ptr [[DST_ROW]], i64 [[S]]
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add i64 [[OUTER_IV]], 1
; CHECK-NEXT: [[EC2:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[M]]
; CHECK-NEXT: br i1 [[EC2]], label %[[EXIT:.*]], label %[[OUTER]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
br label %outer.header
outer.header:
%outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
%dst.row = phi ptr [ %dst, %entry ], [ %dst.row.next, %outer.latch ]
%row = mul i64 %outer.iv, %s
%src.row = getelementptr inbounds i32, ptr %src, i64 %row
br label %inner
inner:
%iv = phi i64 [ 0, %outer.header ], [ %iv.next, %inner ]
%gep.src = getelementptr inbounds i32, ptr %src.row, i64 %iv
%l.src = load i32, ptr %gep.src
%gep.dst = getelementptr inbounds i32, ptr %dst.row, i64 %iv
%l.dst = load i32, ptr %gep.dst
%add = add i32 %l.dst, %l.src
store i32 %add, ptr %gep.dst
%iv.next = add i64 %iv, 1
%ec = icmp eq i64 %iv.next, %n
br i1 %ec, label %outer.latch, label %inner
outer.latch:
%dst.row.next = getelementptr i32, ptr %dst.row, i64 %s
%outer.iv.next = add i64 %outer.iv, 1
%ec2 = icmp eq i64 %outer.iv.next, %m
br i1 %ec2, label %exit, label %outer.header
exit:
ret void
}
; FIXME: The call may not return, so later outer iterations may never run, but the
; bounds are extrapolated to the last outer iteration.
define void @expanded_bounds_outer_call(ptr %dst, ptr %src, i64 %s, i64 %m, i64 %n) {
; CHECK-LABEL: define void @expanded_bounds_outer_call(
; CHECK-SAME: ptr [[DST:%.*]], ptr [[SRC:%.*]], i64 [[S:%.*]], i64 [[M:%.*]], i64 [[N:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[TMP0:%.*]] = shl i64 [[S]], 2
; CHECK-NEXT: [[TMP1:%.*]] = add i64 [[M]], -1
; CHECK-NEXT: [[TMP2:%.*]] = mul i64 [[S]], [[TMP1]]
; CHECK-NEXT: [[TMP3:%.*]] = shl i64 [[TMP2]], 2
; CHECK-NEXT: [[TMP4:%.*]] = shl i64 [[N]], 2
; CHECK-NEXT: [[TMP5:%.*]] = add i64 [[TMP3]], [[TMP4]]
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP5]]
; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP5]]
; CHECK-NEXT: br label %[[OUTER:.*]]
; CHECK: [[OUTER]]:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[OUTER_IV_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT: [[ROW:%.*]] = mul i64 [[OUTER_IV]], [[S]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[N]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP2]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: [[STRIDE_CHECK:%.*]] = icmp slt i64 [[TMP0]], 0
; CHECK-NEXT: [[TMP6:%.*]] = or i1 [[FOUND_CONFLICT]], [[STRIDE_CHECK]]
; CHECK-NEXT: br i1 [[TMP6]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[TMP7:%.*]] = and i64 [[N]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[N]], [[TMP7]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP8:%.*]] = add i64 [[ROW]], [[INDEX]]
; CHECK-NEXT: [[TMP9:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP8]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP9]], align 4, !alias.scope [[META188:![0-9]+]]
; CHECK-NEXT: [[TMP10:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP8]]
; CHECK-NEXT: [[WIDE_LOAD3:%.*]] = load <4 x i32>, ptr [[TMP10]], align 4, !alias.scope [[META191:![0-9]+]], !noalias [[META188]]
; CHECK-NEXT: [[TMP11:%.*]] = add <4 x i32> [[WIDE_LOAD3]], [[WIDE_LOAD]]
; CHECK-NEXT: store <4 x i32> [[TMP11]], ptr [[TMP10]], align 4, !alias.scope [[META191]], !noalias [[META188]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP12:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP12]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP193:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[N]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[OUTER_LATCH]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER:.*]]
; CHECK: [[INNER]]:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[IDX:%.*]] = add i64 [[ROW]], [[IV]]
; CHECK-NEXT: [[GEP_SRC:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[IDX]]
; CHECK-NEXT: [[L_SRC:%.*]] = load i32, ptr [[GEP_SRC]], align 4
; CHECK-NEXT: [[GEP_DST:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IDX]]
; CHECK-NEXT: [[L_DST:%.*]] = load i32, ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[ADD:%.*]] = add i32 [[L_DST]], [[L_SRC]]
; CHECK-NEXT: store i32 [[ADD]], ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT: [[EC:%.*]] = icmp eq i64 [[IV_NEXT]], [[N]]
; CHECK-NEXT: br i1 [[EC]], label %[[OUTER_LATCH]], label %[[INNER]], !llvm.loop [[LOOP194:![0-9]+]]
; CHECK: [[OUTER_LATCH]]:
; CHECK-NEXT: call void @may_not_return()
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add i64 [[OUTER_IV]], 1
; CHECK-NEXT: [[EC2:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[M]]
; CHECK-NEXT: br i1 [[EC2]], label %[[EXIT:.*]], label %[[OUTER]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
br label %outer.header
outer.header:
%outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
%row = mul i64 %outer.iv, %s
br label %inner
inner:
%iv = phi i64 [ 0, %outer.header ], [ %iv.next, %inner ]
%idx = add i64 %row, %iv
%gep.src = getelementptr inbounds i32, ptr %src, i64 %idx
%l.src = load i32, ptr %gep.src
%gep.dst = getelementptr inbounds i32, ptr %dst, i64 %idx
%l.dst = load i32, ptr %gep.dst
%add = add i32 %l.dst, %l.src
store i32 %add, ptr %gep.dst
%iv.next = add i64 %iv, 1
%ec = icmp eq i64 %iv.next, %n
br i1 %ec, label %outer.latch, label %inner
outer.latch:
call void @may_not_return()
%outer.iv.next = add i64 %outer.iv, 1
%ec2 = icmp eq i64 %outer.iv.next, %m
br i1 %ec2, label %exit, label %outer.header
exit:
ret void
}
declare void @may_not_return()
; Bounds of pointer IVs advanced by inbounds GEPs are expanded.
define void @expanded_bounds_ptr_ivs(ptr %dst, ptr %src, i64 %s, i64 %m, i64 %n) {
; CHECK-LABEL: define void @expanded_bounds_ptr_ivs(
; CHECK-SAME: ptr [[DST:%.*]], ptr [[SRC:%.*]], i64 [[S:%.*]], i64 [[M:%.*]], i64 [[N:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[TMP0:%.*]] = shl i64 [[S]], 2
; CHECK-NEXT: [[TMP1:%.*]] = add i64 [[M]], -1
; CHECK-NEXT: [[TMP2:%.*]] = mul i64 [[S]], [[TMP1]]
; CHECK-NEXT: [[TMP3:%.*]] = shl i64 [[TMP2]], 2
; CHECK-NEXT: [[TMP4:%.*]] = shl i64 [[N]], 2
; CHECK-NEXT: [[TMP5:%.*]] = add i64 [[TMP3]], [[TMP4]]
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP5]]
; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP5]]
; CHECK-NEXT: br label %[[OUTER:.*]]
; CHECK: [[OUTER]]:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[OUTER_IV_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT: [[DST_ROW:%.*]] = phi ptr [ [[DST]], %[[ENTRY]] ], [ [[DST_ROW_NEXT:%.*]], %[[OUTER_LATCH]] ]
; CHECK-NEXT: [[ROW:%.*]] = mul i64 [[OUTER_IV]], [[S]]
; CHECK-NEXT: [[SRC_ROW:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[ROW]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[N]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP2]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: [[STRIDE_CHECK:%.*]] = icmp slt i64 [[TMP0]], 0
; CHECK-NEXT: [[TMP6:%.*]] = or i1 [[FOUND_CONFLICT]], [[STRIDE_CHECK]]
; CHECK-NEXT: br i1 [[TMP6]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[TMP7:%.*]] = and i64 [[N]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[N]], [[TMP7]]
; CHECK-NEXT: [[TMP8:%.*]] = shl i64 [[N_VEC]], 2
; CHECK-NEXT: [[TMP9:%.*]] = getelementptr i8, ptr [[SRC_ROW]], i64 [[TMP8]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP10:%.*]] = shl i64 [[INDEX]], 2
; CHECK-NEXT: [[NEXT_GEP:%.*]] = getelementptr i8, ptr [[SRC_ROW]], i64 [[TMP10]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[NEXT_GEP]], align 4, !alias.scope [[META195:![0-9]+]]
; CHECK-NEXT: [[TMP11:%.*]] = getelementptr inbounds i32, ptr [[DST_ROW]], i64 [[INDEX]]
; CHECK-NEXT: [[WIDE_LOAD3:%.*]] = load <4 x i32>, ptr [[TMP11]], align 4, !alias.scope [[META198:![0-9]+]], !noalias [[META195]]
; CHECK-NEXT: [[TMP12:%.*]] = add <4 x i32> [[WIDE_LOAD3]], [[WIDE_LOAD]]
; CHECK-NEXT: store <4 x i32> [[TMP12]], ptr [[TMP11]], align 4, !alias.scope [[META198]], !noalias [[META195]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP13:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP13]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP200:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[N]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[OUTER_LATCH]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: [[BC_RESUME_VAL4:%.*]] = phi ptr [ [[TMP9]], %[[MIDDLE_BLOCK]] ], [ [[SRC_ROW]], %[[OUTER]] ], [ [[SRC_ROW]], %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER:.*]]
; CHECK: [[INNER]]:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[PTR_SRC:%.*]] = phi ptr [ [[BC_RESUME_VAL4]], %[[SCALAR_PH]] ], [ [[PTR_SRC_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[L_SRC:%.*]] = load i32, ptr [[PTR_SRC]], align 4
; CHECK-NEXT: [[GEP_DST:%.*]] = getelementptr inbounds i32, ptr [[DST_ROW]], i64 [[IV]]
; CHECK-NEXT: [[L_DST:%.*]] = load i32, ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[ADD:%.*]] = add i32 [[L_DST]], [[L_SRC]]
; CHECK-NEXT: store i32 [[ADD]], ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[PTR_SRC_NEXT]] = getelementptr inbounds i32, ptr [[PTR_SRC]], i64 1
; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT: [[EC:%.*]] = icmp eq i64 [[IV_NEXT]], [[N]]
; CHECK-NEXT: br i1 [[EC]], label %[[OUTER_LATCH]], label %[[INNER]], !llvm.loop [[LOOP201:![0-9]+]]
; CHECK: [[OUTER_LATCH]]:
; CHECK-NEXT: [[DST_ROW_NEXT]] = getelementptr inbounds i32, ptr [[DST_ROW]], i64 [[S]]
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add i64 [[OUTER_IV]], 1
; CHECK-NEXT: [[EC2:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[M]]
; CHECK-NEXT: br i1 [[EC2]], label %[[EXIT:.*]], label %[[OUTER]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
br label %outer.header
outer.header:
%outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
%dst.row = phi ptr [ %dst, %entry ], [ %dst.row.next, %outer.latch ]
%row = mul i64 %outer.iv, %s
%src.row = getelementptr inbounds i32, ptr %src, i64 %row
br label %inner
inner:
%iv = phi i64 [ 0, %outer.header ], [ %iv.next, %inner ]
%ptr.src = phi ptr [ %src.row, %outer.header ], [ %ptr.src.next, %inner ]
%l.src = load i32, ptr %ptr.src
%gep.dst = getelementptr inbounds i32, ptr %dst.row, i64 %iv
%l.dst = load i32, ptr %gep.dst
%add = add i32 %l.dst, %l.src
store i32 %add, ptr %gep.dst
%ptr.src.next = getelementptr inbounds i32, ptr %ptr.src, i64 1
%iv.next = add i64 %iv, 1
%ec = icmp eq i64 %iv.next, %n
br i1 %ec, label %outer.latch, label %inner
outer.latch:
%dst.row.next = getelementptr inbounds i32, ptr %dst.row, i64 %s
%outer.iv.next = add i64 %outer.iv, 1
%ec2 = icmp eq i64 %outer.iv.next, %m
br i1 %ec2, label %exit, label %outer.header
exit:
ret void
}
; Bounds versioned on a stride loaded in the outer loop are not expanded.
define void @expanded_bounds_outer_varying_stride(ptr %dst, ptr %src, ptr %strides, i64 %s, i64 %k, i64 %m, i64 %n) {
; CHECK-LABEL: define void @expanded_bounds_outer_varying_stride(
; CHECK-SAME: ptr [[DST:%.*]], ptr [[SRC:%.*]], ptr [[STRIDES:%.*]], i64 [[S:%.*]], i64 [[K:%.*]], i64 [[M:%.*]], i64 [[N:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[TMP0:%.*]] = shl i64 [[S]], 2
; CHECK-NEXT: [[TMP1:%.*]] = shl i64 [[K]], 2
; CHECK-NEXT: [[TMP2:%.*]] = add i64 [[M]], -1
; CHECK-NEXT: [[TMP3:%.*]] = mul i64 [[S]], [[TMP2]]
; CHECK-NEXT: [[TMP4:%.*]] = shl i64 [[TMP3]], 2
; CHECK-NEXT: [[TMP5:%.*]] = shl i64 [[N]], 2
; CHECK-NEXT: [[TMP6:%.*]] = add i64 [[TMP4]], [[TMP5]]
; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP6]]
; CHECK-NEXT: [[TMP7:%.*]] = mul i64 [[K]], [[TMP2]]
; CHECK-NEXT: [[TMP8:%.*]] = shl i64 [[TMP7]], 2
; CHECK-NEXT: [[TMP9:%.*]] = add i64 [[TMP8]], [[TMP5]]
; CHECK-NEXT: [[SCEVGEP3:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP9]]
; CHECK-NEXT: br label %[[OUTER:.*]]
; CHECK: [[OUTER]]:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[OUTER_IV_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT: [[GEP_ST:%.*]] = getelementptr inbounds i64, ptr [[STRIDES]], i64 [[OUTER_IV]]
; CHECK-NEXT: [[ST:%.*]] = load i64, ptr [[GEP_ST]], align 8
; CHECK-NEXT: [[ROW_SRC:%.*]] = mul i64 [[OUTER_IV]], [[S]]
; CHECK-NEXT: [[ROW_DST:%.*]] = mul i64 [[OUTER_IV]], [[K]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[N]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_SCEVCHECK:.*]]
; CHECK: [[VECTOR_SCEVCHECK]]:
; CHECK-NEXT: [[IDENT_CHECK:%.*]] = icmp ne i64 [[ST]], 1
; CHECK-NEXT: br i1 [[IDENT_CHECK]], label %[[SCALAR_PH]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[DST]], [[SCEVGEP]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[SRC]], [[SCEVGEP3]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: [[STRIDE_CHECK:%.*]] = icmp slt i64 [[TMP1]], 0
; CHECK-NEXT: [[TMP10:%.*]] = or i1 [[FOUND_CONFLICT]], [[STRIDE_CHECK]]
; CHECK-NEXT: [[STRIDE_CHECK4:%.*]] = icmp slt i64 [[TMP0]], 0
; CHECK-NEXT: [[TMP11:%.*]] = or i1 [[TMP10]], [[STRIDE_CHECK4]]
; CHECK-NEXT: br i1 [[TMP11]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[TMP12:%.*]] = and i64 [[N]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[N]], [[TMP12]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP13:%.*]] = add i64 [[ROW_SRC]], [[INDEX]]
; CHECK-NEXT: [[TMP14:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP13]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP14]], align 4, !alias.scope [[META202:![0-9]+]]
; CHECK-NEXT: [[TMP15:%.*]] = add i64 [[ROW_DST]], [[INDEX]]
; CHECK-NEXT: [[TMP16:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP15]]
; CHECK-NEXT: store <4 x i32> [[WIDE_LOAD]], ptr [[TMP16]], align 4, !alias.scope [[META205:![0-9]+]], !noalias [[META202]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP17:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP17]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP207:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[N]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[OUTER_LATCH]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER]] ], [ 0, %[[VECTOR_SCEVCHECK]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER:.*]]
; CHECK: [[INNER]]:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[IV_ST:%.*]] = mul i64 [[IV]], [[ST]]
; CHECK-NEXT: [[IDX_SRC:%.*]] = add i64 [[ROW_SRC]], [[IV_ST]]
; CHECK-NEXT: [[GEP_SRC:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[IDX_SRC]]
; CHECK-NEXT: [[L:%.*]] = load i32, ptr [[GEP_SRC]], align 4
; CHECK-NEXT: [[IDX_DST:%.*]] = add i64 [[ROW_DST]], [[IV]]
; CHECK-NEXT: [[GEP_DST:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IDX_DST]]
; CHECK-NEXT: store i32 [[L]], ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT: [[EC:%.*]] = icmp eq i64 [[IV_NEXT]], [[N]]
; CHECK-NEXT: br i1 [[EC]], label %[[OUTER_LATCH]], label %[[INNER]], !llvm.loop [[LOOP208:![0-9]+]]
; CHECK: [[OUTER_LATCH]]:
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add i64 [[OUTER_IV]], 1
; CHECK-NEXT: [[EC2:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[M]]
; CHECK-NEXT: br i1 [[EC2]], label %[[EXIT:.*]], label %[[OUTER]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
br label %outer.header
outer.header:
%outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
%gep.st = getelementptr inbounds i64, ptr %strides, i64 %outer.iv
%st = load i64, ptr %gep.st
%row.src = mul i64 %outer.iv, %s
%row.dst = mul i64 %outer.iv, %k
br label %inner
inner:
%iv = phi i64 [ 0, %outer.header ], [ %iv.next, %inner ]
%iv.st = mul i64 %iv, %st
%idx.src = add i64 %row.src, %iv.st
%gep.src = getelementptr inbounds i32, ptr %src, i64 %idx.src
%l = load i32, ptr %gep.src
%idx.dst = add i64 %row.dst, %iv
%gep.dst = getelementptr inbounds i32, ptr %dst, i64 %idx.dst
store i32 %l, ptr %gep.dst
%iv.next = add i64 %iv, 1
%ec = icmp eq i64 %iv.next, %n
br i1 %ec, label %outer.latch, label %inner
outer.latch:
%outer.iv.next = add i64 %outer.iv, 1
%ec2 = icmp eq i64 %outer.iv.next, %m
br i1 %ec2, label %exit, label %outer.header
exit:
ret void
}
; FIXME: The inner trip count depends on the outer IV, so the bounds are not
; expanded and, as the outer steps differ, no diff check is used either; the
; check is recomputed in every outer iteration.
define void @expanded_bounds_triangular_diff_check(ptr %dst, ptr %src, i64 %s, i64 %t, i64 %m) {
; CHECK-LABEL: define void @expanded_bounds_triangular_diff_check(
; CHECK-SAME: ptr [[DST:%.*]], ptr [[SRC:%.*]], i64 [[S:%.*]], i64 [[T:%.*]], i64 [[M:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*]]:
; CHECK-NEXT: [[TMP0:%.*]] = shl i64 [[S]], 2
; CHECK-NEXT: [[TMP1:%.*]] = add i64 [[TMP0]], 4
; CHECK-NEXT: [[TMP2:%.*]] = shl i64 [[T]], 2
; CHECK-NEXT: [[TMP3:%.*]] = add i64 [[TMP2]], 4
; CHECK-NEXT: br label %[[OUTER:.*]]
; CHECK: [[OUTER]]:
; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[OUTER_IV_NEXT:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT: [[OUTER_IV_NEXT]] = add nuw i64 [[OUTER_IV]], 1
; CHECK-NEXT: [[ROW_SRC:%.*]] = mul i64 [[OUTER_IV]], [[S]]
; CHECK-NEXT: [[ROW_DST:%.*]] = mul i64 [[OUTER_IV]], [[T]]
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[OUTER_IV_NEXT]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_MEMCHECK:.*]]
; CHECK: [[VECTOR_MEMCHECK]]:
; CHECK-NEXT: [[TMP4:%.*]] = mul i64 [[OUTER_IV]], [[TMP2]]
; CHECK-NEXT: [[TMP5:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP4]]
; CHECK-NEXT: [[TMP6:%.*]] = mul i64 [[OUTER_IV]], [[TMP3]]
; CHECK-NEXT: [[TMP7:%.*]] = add i64 4, [[TMP6]]
; CHECK-NEXT: [[TMP8:%.*]] = getelementptr i8, ptr [[DST]], i64 [[TMP7]]
; CHECK-NEXT: [[TMP9:%.*]] = mul i64 [[OUTER_IV]], [[TMP0]]
; CHECK-NEXT: [[TMP10:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP9]]
; CHECK-NEXT: [[TMP11:%.*]] = mul i64 [[OUTER_IV]], [[TMP1]]
; CHECK-NEXT: [[TMP12:%.*]] = add i64 4, [[TMP11]]
; CHECK-NEXT: [[TMP13:%.*]] = getelementptr i8, ptr [[SRC]], i64 [[TMP12]]
; CHECK-NEXT: [[BOUND0:%.*]] = icmp ult ptr [[TMP5]], [[TMP13]]
; CHECK-NEXT: [[BOUND1:%.*]] = icmp ult ptr [[TMP10]], [[TMP8]]
; CHECK-NEXT: [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
; CHECK-NEXT: br i1 [[FOUND_CONFLICT]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[TMP14:%.*]] = and i64 [[OUTER_IV_NEXT]], 3
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[OUTER_IV_NEXT]], [[TMP14]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP15:%.*]] = add i64 [[ROW_SRC]], [[INDEX]]
; CHECK-NEXT: [[TMP16:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[TMP15]]
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <4 x i32>, ptr [[TMP16]], align 4, !alias.scope [[META209:![0-9]+]]
; CHECK-NEXT: [[TMP17:%.*]] = add i64 [[ROW_DST]], [[INDEX]]
; CHECK-NEXT: [[TMP18:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[TMP17]]
; CHECK-NEXT: store <4 x i32> [[WIDE_LOAD]], ptr [[TMP18]], align 4, !alias.scope [[META212:![0-9]+]], !noalias [[META209]]
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP19:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP19]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP214:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[CMP_N]], label %[[OUTER_LATCH]], label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[OUTER]] ], [ 0, %[[VECTOR_MEMCHECK]] ]
; CHECK-NEXT: br label %[[INNER:.*]]
; CHECK: [[INNER]]:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], %[[INNER]] ]
; CHECK-NEXT: [[IDX_SRC:%.*]] = add i64 [[ROW_SRC]], [[IV]]
; CHECK-NEXT: [[GEP_SRC:%.*]] = getelementptr inbounds i32, ptr [[SRC]], i64 [[IDX_SRC]]
; CHECK-NEXT: [[L:%.*]] = load i32, ptr [[GEP_SRC]], align 4
; CHECK-NEXT: [[IDX_DST:%.*]] = add i64 [[ROW_DST]], [[IV]]
; CHECK-NEXT: [[GEP_DST:%.*]] = getelementptr inbounds i32, ptr [[DST]], i64 [[IDX_DST]]
; CHECK-NEXT: store i32 [[L]], ptr [[GEP_DST]], align 4
; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1
; CHECK-NEXT: [[EC:%.*]] = icmp eq i64 [[IV_NEXT]], [[OUTER_IV_NEXT]]
; CHECK-NEXT: br i1 [[EC]], label %[[OUTER_LATCH]], label %[[INNER]], !llvm.loop [[LOOP215:![0-9]+]]
; CHECK: [[OUTER_LATCH]]:
; CHECK-NEXT: [[EC2:%.*]] = icmp eq i64 [[OUTER_IV_NEXT]], [[M]]
; CHECK-NEXT: br i1 [[EC2]], label %[[EXIT:.*]], label %[[OUTER]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
br label %outer.header
outer.header:
%outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
%outer.iv.next = add nuw i64 %outer.iv, 1
%row.src = mul i64 %outer.iv, %s
%row.dst = mul i64 %outer.iv, %t
br label %inner
inner:
%iv = phi i64 [ 0, %outer.header ], [ %iv.next, %inner ]
%idx.src = add i64 %row.src, %iv
%gep.src = getelementptr inbounds i32, ptr %src, i64 %idx.src
%l = load i32, ptr %gep.src
%idx.dst = add i64 %row.dst, %iv
%gep.dst = getelementptr inbounds i32, ptr %dst, i64 %idx.dst
store i32 %l, ptr %gep.dst
%iv.next = add i64 %iv, 1
%ec = icmp eq i64 %iv.next, %outer.iv.next
br i1 %ec, label %outer.latch, label %inner
outer.latch:
%ec2 = icmp eq i64 %outer.iv.next, %m
br i1 %ec2, label %exit, label %outer.header
exit:
ret void
}