shylie/llvm-project
1
0
Fork 0
Code Issues Pull Requests Actions 6 Packages Projects Releases Wiki Activity
llvm-project/llvm/test/Transforms/LoopVectorize/interleaved-accesses-requiring-scev-predicates.ll
Florian Hahn 50b9ca4dda
[VPlan] Simplify Plan's entry in removeBranchOnConst. (#154510) 
After https://github.com/llvm/llvm-project/pull/153643, there may be a
BranchOnCond with constant condition in the entry block.

Simplify those in removeBranchOnConst. This removes a number of
redundant conditional branch from entry blocks.

In some cases, it may also make the original scalar loop unreachable,
because we know it will never execute. In that case, we need to remove
the loop from LoopInfo, because all unreachable blocks may dominate each
other, making LoopInfo invalid. In those cases, we can also completely
remove the loop, for which I'll share a follow-up patch.

Depends on https://github.com/llvm/llvm-project/pull/153643.

PR: https://github.com/llvm/llvm-project/pull/154510
2025-09-18 19:25:05 +01:00

254 lines
14 KiB
LLVM
Raw Permalink Blame History

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --check-globals none --version 5
; RUN: opt -S -passes=loop-vectorize -force-vector-width=4 -force-vector-interleave=1 -enable-interleaved-mem-accesses=true %s | FileCheck %s
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
; Check that the interleaved-mem-access analysis currently does not create an
; interleave group for access 'a' due to the possible pointer wrap-around.
;
; To begin with, in this test the candidate interleave group can be created
; only when getPtrStride is called with Assume=true. Next, because
; the interleave-group of the loads is not full (has gaps), we also need to check
; for possible pointer wrapping. Here we currently use Assume=false and as a
; result cannot prove the transformation is safe and therefore invalidate the
; candidate interleave group.
;
; void func(unsigned * __restrict a, unsigned * __restrict b, unsigned char x, unsigned char y) {
; int i = 0;
; for (unsigned char index = x; i < y; index +=2, ++i)
; b[i] = aptr 2;
;
; }
define void @wrap_around_scev_check(ptr noalias %a, ptr noalias %b, i8 %x, i8 %y) {
; CHECK-LABEL: define void @wrap_around_scev_check(
; CHECK-SAME: ptr noalias [[A:%.*]], ptr noalias [[B:%.*]], i8 [[X:%.*]], i8 [[Y:%.*]]) {
; CHECK-NEXT: [[ENTRY:.*:]]
; CHECK-NEXT: [[CMP9:%.*]] = icmp eq i8 [[Y]], 0
; CHECK-NEXT: br i1 [[CMP9]], label %[[EXIT:.*]], label %[[LOOP_PREHEADER:.*]]
; CHECK: [[LOOP_PREHEADER]]:
; CHECK-NEXT: [[WIDE_TRIP_COUNT:%.*]] = zext i8 [[Y]] to i64
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ule i64 [[WIDE_TRIP_COUNT]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_SCEVCHECK:.*]]
; CHECK: [[VECTOR_SCEVCHECK]]:
; CHECK-NEXT: [[TMP0:%.*]] = add nsw i64 [[WIDE_TRIP_COUNT]], -1
; CHECK-NEXT: [[TMP1:%.*]] = trunc i64 [[TMP0]] to i8
; CHECK-NEXT: [[MUL1:%.*]] = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 2, i8 [[TMP1]])
; CHECK-NEXT: [[MUL_RESULT:%.*]] = extractvalue { i8, i1 } [[MUL1]], 0
; CHECK-NEXT: [[TMP4:%.*]] = extractvalue { i8, i1 } [[MUL1]], 1
; CHECK-NEXT: [[TMP2:%.*]] = add i8 [[X]], [[MUL_RESULT]]
; CHECK-NEXT: [[TMP3:%.*]] = icmp ult i8 [[TMP2]], [[X]]
; CHECK-NEXT: [[TMP5:%.*]] = or i1 [[TMP3]], [[TMP4]]
; CHECK-NEXT: [[TMP17:%.*]] = icmp ugt i64 [[TMP0]], 255
; CHECK-NEXT: [[TMP18:%.*]] = or i1 [[TMP5]], [[TMP17]]
; CHECK-NEXT: br i1 [[TMP18]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[N_MOD_VF:%.*]] = urem i64 [[WIDE_TRIP_COUNT]], 4
; CHECK-NEXT: [[TMP6:%.*]] = icmp eq i64 [[N_MOD_VF]], 0
; CHECK-NEXT: [[TMP7:%.*]] = select i1 [[TMP6]], i64 4, i64 [[N_MOD_VF]]
; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[WIDE_TRIP_COUNT]], [[TMP7]]
; CHECK-NEXT: [[DOTCAST:%.*]] = trunc i64 [[N_VEC]] to i8
; CHECK-NEXT: [[TMP8:%.*]] = mul i8 [[DOTCAST]], 2
; CHECK-NEXT: [[TMP9:%.*]] = add i8 [[X]], [[TMP8]]
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[DOTCAST2:%.*]] = trunc i64 [[INDEX]] to i8
; CHECK-NEXT: [[TMP10:%.*]] = mul i8 [[DOTCAST2]], 2
; CHECK-NEXT: [[OFFSET_IDX:%.*]] = add i8 [[X]], [[TMP10]]
; CHECK-NEXT: [[TMP11:%.*]] = zext i8 [[OFFSET_IDX]] to i64
; CHECK-NEXT: [[TMP12:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[TMP11]]
; CHECK-NEXT: [[WIDE_VEC:%.*]] = load <8 x i32>, ptr [[TMP12]], align 4
; CHECK-NEXT: [[STRIDED_VEC:%.*]] = shufflevector <8 x i32> [[WIDE_VEC]], <8 x i32> poison, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
; CHECK-NEXT: [[TMP13:%.*]] = shl <4 x i32> [[STRIDED_VEC]], splat (i32 1)
; CHECK-NEXT: [[TMP14:%.*]] = getelementptr inbounds i32, ptr [[B]], i64 [[INDEX]]
; CHECK-NEXT: store <4 x i32> [[TMP13]], ptr [[TMP14]], align 4
; 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 [[LOOP0:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: br label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[LOOP_PREHEADER]] ], [ 0, %[[VECTOR_SCEVCHECK]] ]
; CHECK-NEXT: [[BC_RESUME_VAL3:%.*]] = phi i8 [ [[TMP9]], %[[MIDDLE_BLOCK]] ], [ [[X]], %[[LOOP_PREHEADER]] ], [ [[X]], %[[VECTOR_SCEVCHECK]] ]
; CHECK-NEXT: br label %[[LOOP:.*]]
; CHECK: [[LOOP]]:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], %[[LOOP]] ]
; CHECK-NEXT: [[INDEX_011:%.*]] = phi i8 [ [[BC_RESUME_VAL3]], %[[SCALAR_PH]] ], [ [[ADD:%.*]], %[[LOOP]] ]
; CHECK-NEXT: [[IDXPROM:%.*]] = zext i8 [[INDEX_011]] to i64
; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[IDXPROM]]
; CHECK-NEXT: [[TMP16:%.*]] = load i32, ptr [[ARRAYIDX]], align 4
; CHECK-NEXT: [[MUL:%.*]] = shl i32 [[TMP16]], 1
; CHECK-NEXT: [[ARRAYIDX2:%.*]] = getelementptr inbounds i32, ptr [[B]], i64 [[IV]]
; CHECK-NEXT: store i32 [[MUL]], ptr [[ARRAYIDX2]], align 4
; CHECK-NEXT: [[ADD]] = add i8 [[INDEX_011]], 2
; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[IV_NEXT]], [[WIDE_TRIP_COUNT]]
; CHECK-NEXT: br i1 [[EXITCOND]], label %[[EXIT_LOOPEXIT:.*]], label %[[LOOP]], !llvm.loop [[LOOP3:![0-9]+]]
; CHECK: [[EXIT_LOOPEXIT]]:
; CHECK-NEXT: br label %[[EXIT]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
entry:
%cmp9 = icmp eq i8 %y, 0
br i1 %cmp9, label %exit, label %loop.preheader
loop.preheader:
%wide.trip.count = zext i8 %y to i64
br label %loop
loop:
%iv = phi i64 [ 0, %loop.preheader ], [ %iv.next, %loop ]
%index.011 = phi i8 [ %x, %loop.preheader ], [ %add, %loop ]
%idxprom = zext i8 %index.011 to i64
%arrayidx = getelementptr inbounds i32, ptr %a, i64 %idxprom
%0 = load i32, ptr %arrayidx, align 4
%mul = shl i32 %0, 1
%arrayidx2 = getelementptr inbounds i32, ptr %b, i64 %iv
store i32 %mul, ptr %arrayidx2, align 4
%add = add i8 %index.011, 2
%iv.next = add nuw nsw i64 %iv, 1
%exitcond = icmp eq i64 %iv.next, %wide.trip.count
br i1 %exitcond, label %exit, label %loop
exit:
ret void
}
; For %gep, we have the following SCEV: ((4 * (zext i4 {0,+,5}<%loop> to i64))<nuw><nsw> + %x).
; Note the i4 bit wide AddRec {0,+,5}. It is known to wrap in the loop with trip count 16.
define void @wrap_predicate_for_interleave_group_wraps_for_known_trip_count(ptr noalias %x, ptr noalias %out) {
; CHECK-LABEL: define void @wrap_predicate_for_interleave_group_wraps_for_known_trip_count(
; CHECK-SAME: ptr noalias [[X:%.*]], ptr noalias [[OUT:%.*]]) {
; CHECK-NEXT: [[START:.*]]:
; CHECK-NEXT: br label %[[VECTOR_SCEVCHECK:.*]]
; CHECK: [[VECTOR_SCEVCHECK]]:
; CHECK-NEXT: [[MUL:%.*]] = call { i4, i1 } @llvm.umul.with.overflow.i4(i4 5, i4 -1)
; CHECK-NEXT: [[MUL_OVERFLOW:%.*]] = extractvalue { i4, i1 } [[MUL]], 1
; CHECK-NEXT: br i1 [[MUL_OVERFLOW]], label %[[SCALAR_PH:.*]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: br label %[[VECTOR_BODY:.*]]
; CHECK: [[VECTOR_BODY]]:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP0:%.*]] = mul nuw nsw i64 [[INDEX]], 5
; CHECK-NEXT: [[TMP1:%.*]] = and i64 [[TMP0]], 15
; CHECK-NEXT: [[TMP2:%.*]] = getelementptr inbounds nuw i32, ptr [[X]], i64 [[TMP1]]
; CHECK-NEXT: [[WIDE_VEC:%.*]] = load <20 x i32>, ptr [[TMP2]], align 4
; CHECK-NEXT: [[STRIDED_VEC:%.*]] = shufflevector <20 x i32> [[WIDE_VEC]], <20 x i32> poison, <4 x i32> <i32 0, i32 5, i32 10, i32 15>
; CHECK-NEXT: [[TMP3:%.*]] = getelementptr inbounds nuw i32, ptr [[OUT]], i64 [[INDEX]]
; CHECK-NEXT: store <4 x i32> [[STRIDED_VEC]], ptr [[TMP3]], align 4
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP4:%.*]] = icmp eq i64 [[INDEX_NEXT]], 12
; CHECK-NEXT: br i1 [[TMP4]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP4:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: br label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ 12, %[[MIDDLE_BLOCK]] ], [ 0, %[[VECTOR_SCEVCHECK]] ]
; CHECK-NEXT: br label %[[LOOP:.*]]
; CHECK: [[LOOP]]:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], %[[LOOP]] ]
; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
; CHECK-NEXT: [[IV_MUL5:%.*]] = mul nuw nsw i64 [[IV]], 5
; CHECK-NEXT: [[IV_MUL5_MASKED:%.*]] = and i64 [[IV_MUL5]], 15
; CHECK-NEXT: [[GEP:%.*]] = getelementptr inbounds nuw i32, ptr [[X]], i64 [[IV_MUL5_MASKED]]
; CHECK-NEXT: [[V:%.*]] = load i32, ptr [[GEP]], align 4
; CHECK-NEXT: [[OUT_I:%.*]] = getelementptr inbounds nuw i32, ptr [[OUT]], i64 [[IV]]
; CHECK-NEXT: store i32 [[V]], ptr [[OUT_I]], align 4
; CHECK-NEXT: [[EXITCOND_NOT:%.*]] = icmp eq i64 [[IV_NEXT]], 16
; CHECK-NEXT: br i1 [[EXITCOND_NOT]], label %[[EXIT:.*]], label %[[LOOP]], !llvm.loop [[LOOP5:![0-9]+]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
start:
br label %loop
loop:
%iv = phi i64 [ 0, %start ], [ %iv.next, %loop ]
%iv.next = add nuw nsw i64 %iv, 1
%iv.mul5 = mul nuw nsw i64 %iv, 5
%iv.mul5.masked = and i64 %iv.mul5, 15
%gep = getelementptr inbounds nuw i32, ptr %x, i64 %iv.mul5.masked
%v = load i32, ptr %gep, align 4
%out.i = getelementptr inbounds nuw i32, ptr %out, i64 %iv
store i32 %v, ptr %out.i, align 4
%exitcond.not = icmp eq i64 %iv.next, 16
br i1 %exitcond.not, label %exit, label %loop
exit:
ret void
}
; For %gep, we have the following SCEV: ((4 * (zext i4 {0,+,3}<%loop> to i64))<nuw><nsw> + %x).
; Note the i4 bit wide AddRec {0,+,3}. It may wrap, depending on the trip count.
define void @wrap_predicate_for_interleave_group_unknown_trip_count(ptr noalias %x, ptr noalias %out, i64 %n) {
; CHECK-LABEL: define void @wrap_predicate_for_interleave_group_unknown_trip_count(
; CHECK-SAME: ptr noalias [[X:%.*]], ptr noalias [[OUT:%.*]], i64 [[N:%.*]]) {
; CHECK-NEXT: [[START:.*]]:
; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ule i64 [[N]], 4
; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label %[[SCALAR_PH:.*]], label %[[VECTOR_SCEVCHECK:.*]]
; CHECK: [[VECTOR_SCEVCHECK]]:
; CHECK-NEXT: [[TMP0:%.*]] = add i64 [[N]], -1
; CHECK-NEXT: [[TMP9:%.*]] = trunc i64 [[TMP0]] to i4
; CHECK-NEXT: [[MUL:%.*]] = call { i4, i1 } @llvm.umul.with.overflow.i4(i4 3, i4 [[TMP9]])
; CHECK-NEXT: [[MUL_OVERFLOW:%.*]] = extractvalue { i4, i1 } [[MUL]], 1
; CHECK-NEXT: [[TMP1:%.*]] = icmp ugt i64 [[TMP0]], 15
; CHECK-NEXT: [[TMP10:%.*]] = or i1 [[MUL_OVERFLOW]], [[TMP1]]
; CHECK-NEXT: br i1 [[TMP10]], label %[[SCALAR_PH]], label %[[VECTOR_PH:.*]]
; CHECK: [[VECTOR_PH]]:
; CHECK-NEXT: [[N_MOD_VF:%.*]] = urem i64 [[N]], 4
; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i64 [[N_MOD_VF]], 0
; CHECK-NEXT: [[TMP7:%.*]] = select i1 [[TMP2]], i64 4, i64 [[N_MOD_VF]]
; 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:%.*]] = mul nuw nsw i64 [[INDEX]], 3
; CHECK-NEXT: [[TMP3:%.*]] = and i64 [[TMP8]], 15
; CHECK-NEXT: [[TMP4:%.*]] = getelementptr inbounds nuw i32, ptr [[X]], i64 [[TMP3]]
; CHECK-NEXT: [[WIDE_VEC:%.*]] = load <12 x i32>, ptr [[TMP4]], align 4
; CHECK-NEXT: [[STRIDED_VEC:%.*]] = shufflevector <12 x i32> [[WIDE_VEC]], <12 x i32> poison, <4 x i32> <i32 0, i32 3, i32 6, i32 9>
; CHECK-NEXT: [[TMP5:%.*]] = getelementptr inbounds nuw i32, ptr [[OUT]], i64 [[INDEX]]
; CHECK-NEXT: store <4 x i32> [[STRIDED_VEC]], ptr [[TMP5]], align 4
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 4
; CHECK-NEXT: [[TMP6:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]]
; CHECK-NEXT: br i1 [[TMP6]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP6:![0-9]+]]
; CHECK: [[MIDDLE_BLOCK]]:
; CHECK-NEXT: br label %[[SCALAR_PH]]
; CHECK: [[SCALAR_PH]]:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], %[[MIDDLE_BLOCK]] ], [ 0, %[[START]] ], [ 0, %[[VECTOR_SCEVCHECK]] ]
; CHECK-NEXT: br label %[[LOOP:.*]]
; CHECK: [[LOOP]]:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], %[[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], %[[LOOP]] ]
; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
; CHECK-NEXT: [[IV_MUL5:%.*]] = mul nuw nsw i64 [[IV]], 3
; CHECK-NEXT: [[IV_MUL5_MASKED:%.*]] = and i64 [[IV_MUL5]], 15
; CHECK-NEXT: [[GEP:%.*]] = getelementptr inbounds nuw i32, ptr [[X]], i64 [[IV_MUL5_MASKED]]
; CHECK-NEXT: [[V:%.*]] = load i32, ptr [[GEP]], align 4
; CHECK-NEXT: [[OUT_I:%.*]] = getelementptr inbounds nuw i32, ptr [[OUT]], i64 [[IV]]
; CHECK-NEXT: store i32 [[V]], ptr [[OUT_I]], align 4
; CHECK-NEXT: [[EXITCOND_NOT:%.*]] = icmp eq i64 [[IV_NEXT]], [[N]]
; CHECK-NEXT: br i1 [[EXITCOND_NOT]], label %[[EXIT:.*]], label %[[LOOP]], !llvm.loop [[LOOP7:![0-9]+]]
; CHECK: [[EXIT]]:
; CHECK-NEXT: ret void
;
start:
br label %loop
loop:
%iv = phi i64 [ 0, %start ], [ %iv.next, %loop ]
%iv.next = add nuw nsw i64 %iv, 1
%iv.mul3 = mul nuw nsw i64 %iv, 3
%iv.mul3.masked = and i64 %iv.mul3, 15
%gep = getelementptr inbounds nuw i32, ptr %x, i64 %iv.mul3.masked
%v = load i32, ptr %gep, align 4
%out.i = getelementptr inbounds nuw i32, ptr %out, i64 %iv
store i32 %v, ptr %out.i, align 4
%exitcond.not = icmp eq i64 %iv.next, %n
br i1 %exitcond.not, label %exit, label %loop
exit:
ret void
}
Reference in New Issue View Git Blame Copy Permalink