This is an archive of the discontinued LLVM Phabricator instance.

Differential D147798

[LV] Improve VF-aware uniformity checks by handling LShr.
Needs ReviewPublic

Authored by vporpo on Apr 7 2023, 11:02 AM.
This revision needs review, but there are no reviewers specified.

Details

Reviewers
None
Summary

Until now the VF-aware uniformity check would only check for division i/NUM.
This patch extends it to support shift-rights, like: i >> N.
So the access to A[i>>2] in the following loop will no longer be considered
a gather for a VF of 4.

for (i = 0; i != N; ++i)
  ... = ... A[i>>2]

Diff Detail

Revision Contents

PathSize
llvm/
lib/
Transforms/
Vectorize/
14 lines
test/
Transforms/
LoopVectorize/
X86/
56 lines

Diff 515435

llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

Show First 20 Lines • Show All 486 Lines • ▼ Show 20 Linesbool LoopVectorizationLegality::isUniformAcrossVF(Value *V, uint32_t VF,
auto *IV = TheLoop->getInductionVariable(SE); auto *IV = TheLoop->getInductionVariable(SE);
if(IV == nullptr) if(IV == nullptr)
return false; return false;
if (Instruction *I = dyn_cast<Instruction>(V)) { if (Instruction *I = dyn_cast<Instruction>(V)) {
Value *Op1; Value *Op1;
Value *Op2; Value *Op2;
if (match(V, m_BinOp(m_Value(Op1), m_Value(Op2)))) { if (match(V, m_BinOp(m_Value(Op1), m_Value(Op2)))) {
auto Opcode = cast<Instruction>(V)->getOpcode(); auto Opcode = cast<Instruction>(V)->getOpcode();
if (Opcode == Instruction::UDiv && isInductionVariable(Op1)) { if ((Opcode == Instruction::UDiv || Opcode == Instruction::LShr) &&
isInductionVariable(Op1)) {
// Return true if divisor/step is a constant and a multiple of VF. // Return true if divisor/step is a constant and a multiple of VF.
if (auto *Divisor = dyn_cast<ConstantInt>(Op2)) { if (ConstantInt *Op2Const = dyn_cast<ConstantInt>(Op2)) {
APInt DivisorVal = Opcode == Instruction::UDiv
? Op2Const->getValue()
: (APInt(64, 1) << Op2Const->getValue());
auto *VFC = ConstantInt::get(Type::getInt64Ty(V->getContext()), VF); auto *VFC = ConstantInt::get(Type::getInt64Ty(V->getContext()), VF);
bool IsIdentity = bool IsIdentity =
Opcode == Instruction::UDiv && Divisor->isOneValue(); (Opcode == Instruction::UDiv && DivisorVal.isOne()) ||
(Opcode == Instruction::LShr && DivisorVal.isZero());
std::optional<Loop::LoopBounds> LoopBounds = std::optional<Loop::LoopBounds> LoopBounds =
Loop::LoopBounds::getBounds(*TheLoop, *IV, SE); Loop::LoopBounds::getBounds(*TheLoop, *IV, SE);
assert(LoopBounds && "Missing LoopBounds!"); assert(LoopBounds && "Missing LoopBounds!");
ConstantInt *Step = dyn_cast<ConstantInt>(LoopBounds->getStepValue()); ConstantInt *Step = dyn_cast<ConstantInt>(LoopBounds->getStepValue());
// (Divisor / Step) % VF == 0 // (Divisor / Step) % VF == 0
return Step != nullptr && !IsIdentity && return Step != nullptr && !IsIdentity &&
Divisor->getValue() DivisorVal.udiv(Step->getValue())
.udiv(Step->getValue())
.srem(VFC->getValue()) .srem(VFC->getValue())
.isZero(); .isZero();
} }
} }
return isUniformAcrossVF(Op1, VF, MaxDepth) && return isUniformAcrossVF(Op1, VF, MaxDepth) &&
isUniformAcrossVF(Op2, VF, MaxDepth); isUniformAcrossVF(Op2, VF, MaxDepth);
} }
Value *Ptr; Value *Ptr;
▲ Show 20 Lines • Show All 1,003 Lines • Show Last 20 Lines

llvm/test/Transforms/LoopVectorize/X86/uniform_across_vf.ll

Show First 20 Lines • Show All 381 Lines • ▼ Show 20 Lines
; CHECK-LABEL: define void @ld_lshr1_step1 ; CHECK-LABEL: define void @ld_lshr1_step1
; CHECK-SAME: (ptr noalias [[SRC:%.*]], ptr noalias [[DST:%.*]]) #[[ATTR0]] { ; CHECK-SAME: (ptr noalias [[SRC:%.*]], ptr noalias [[DST:%.*]]) #[[ATTR0]] {
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: br i1 false, label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]] ; CHECK-NEXT: br i1 false, label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
; CHECK: vector.ph: ; CHECK: vector.ph:
; CHECK-NEXT: br label [[VECTOR_BODY:%.*]] ; CHECK-NEXT: br label [[VECTOR_BODY:%.*]]
; CHECK: vector.body: ; CHECK: vector.body:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ] ; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
; CHECK-NEXT: [[VEC_IND:%.*]] = phi <2 x i64> [ <i64 0, i64 1>, [[VECTOR_PH]] ], [ [[VEC_IND_NEXT:%.*]], [[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP0:%.*]] = add i64 [[INDEX]], 0 ; CHECK-NEXT: [[TMP0:%.*]] = add i64 [[INDEX]], 0
; CHECK-NEXT: [[TMP1:%.*]] = lshr <2 x i64> [[VEC_IND]], <i64 1, i64 1> ; CHECK-NEXT: [[TMP1:%.*]] = lshr i64 [[TMP0]], 1
; CHECK-NEXT: [[TMP2:%.*]] = extractelement <2 x i64> [[TMP1]], i32 0 ; CHECK-NEXT: [[TMP2:%.*]] = getelementptr inbounds i64, ptr [[SRC]], i64 [[TMP1]]
; CHECK-NEXT: [[TMP3:%.*]] = getelementptr inbounds i64, ptr [[SRC]], i64 [[TMP2]] ; CHECK-NEXT: [[TMP3:%.*]] = load i64, ptr [[TMP2]], align 8
; CHECK-NEXT: [[TMP4:%.*]] = extractelement <2 x i64> [[TMP1]], i32 1 ; CHECK-NEXT: [[BROADCAST_SPLATINSERT:%.*]] = insertelement <2 x i64> poison, i64 [[TMP3]], i64 0
; CHECK-NEXT: [[TMP5:%.*]] = getelementptr inbounds i64, ptr [[SRC]], i64 [[TMP4]] ; CHECK-NEXT: [[BROADCAST_SPLAT:%.*]] = shufflevector <2 x i64> [[BROADCAST_SPLATINSERT]], <2 x i64> poison, <2 x i32> zeroinitializer
; CHECK-NEXT: [[TMP6:%.*]] = load i64, ptr [[TMP3]], align 8 ; CHECK-NEXT: [[TMP4:%.*]] = add nsw <2 x i64> [[BROADCAST_SPLAT]], <i64 42, i64 42>
; CHECK-NEXT: [[TMP7:%.*]] = load i64, ptr [[TMP5]], align 8 ; CHECK-NEXT: [[TMP5:%.*]] = getelementptr inbounds i64, ptr [[DST]], i64 [[TMP0]]
; CHECK-NEXT: [[TMP8:%.*]] = insertelement <2 x i64> poison, i64 [[TMP6]], i32 0 ; CHECK-NEXT: [[TMP6:%.*]] = getelementptr inbounds i64, ptr [[TMP5]], i32 0
; CHECK-NEXT: [[TMP9:%.*]] = insertelement <2 x i64> [[TMP8]], i64 [[TMP7]], i32 1 ; CHECK-NEXT: store <2 x i64> [[TMP4]], ptr [[TMP6]], align 8
; CHECK-NEXT: [[TMP10:%.*]] = add nsw <2 x i64> [[TMP9]], <i64 42, i64 42>
; CHECK-NEXT: [[TMP11:%.*]] = getelementptr inbounds i64, ptr [[DST]], i64 [[TMP0]]
; CHECK-NEXT: [[TMP12:%.*]] = getelementptr inbounds i64, ptr [[TMP11]], i32 0
; CHECK-NEXT: store <2 x i64> [[TMP10]], ptr [[TMP12]], align 8
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 2 ; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 2
; CHECK-NEXT: [[VEC_IND_NEXT]] = add <2 x i64> [[VEC_IND]], <i64 2, i64 2> ; CHECK-NEXT: [[TMP7:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1000
; CHECK-NEXT: [[TMP13:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1000 ; CHECK-NEXT: br i1 [[TMP7]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP14:![0-9]+]]
; CHECK-NEXT: br i1 [[TMP13]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP14:![0-9]+]]
; CHECK: middle.block: ; CHECK: middle.block:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 1000, 1000 ; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 1000, 1000
; CHECK-NEXT: br i1 [[CMP_N]], label [[EXIT:%.*]], label [[SCALAR_PH]] ; CHECK-NEXT: br i1 [[CMP_N]], label [[EXIT:%.*]], label [[SCALAR_PH]]
; CHECK: scalar.ph: ; CHECK: scalar.ph:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ 1000, [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ] ; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ 1000, [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop: ; CHECK: loop:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
Show All 33 Lines
; CHECK-LABEL: define void @ld_lshr2_step1 ; CHECK-LABEL: define void @ld_lshr2_step1
; CHECK-SAME: (ptr noalias [[SRC:%.*]], ptr noalias [[DST:%.*]]) #[[ATTR0]] { ; CHECK-SAME: (ptr noalias [[SRC:%.*]], ptr noalias [[DST:%.*]]) #[[ATTR0]] {
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: br i1 false, label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]] ; CHECK-NEXT: br i1 false, label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
; CHECK: vector.ph: ; CHECK: vector.ph:
; CHECK-NEXT: br label [[VECTOR_BODY:%.*]] ; CHECK-NEXT: br label [[VECTOR_BODY:%.*]]
; CHECK: vector.body: ; CHECK: vector.body:
; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ] ; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
; CHECK-NEXT: [[VEC_IND:%.*]] = phi <2 x i64> [ <i64 0, i64 1>, [[VECTOR_PH]] ], [ [[VEC_IND_NEXT:%.*]], [[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP0:%.*]] = add i64 [[INDEX]], 0 ; CHECK-NEXT: [[TMP0:%.*]] = add i64 [[INDEX]], 0
; CHECK-NEXT: [[TMP1:%.*]] = lshr <2 x i64> [[VEC_IND]], <i64 2, i64 2> ; CHECK-NEXT: [[TMP1:%.*]] = lshr i64 [[TMP0]], 2
; CHECK-NEXT: [[TMP2:%.*]] = extractelement <2 x i64> [[TMP1]], i32 0 ; CHECK-NEXT: [[TMP2:%.*]] = getelementptr inbounds i64, ptr [[SRC]], i64 [[TMP1]]
; CHECK-NEXT: [[TMP3:%.*]] = getelementptr inbounds i64, ptr [[SRC]], i64 [[TMP2]] ; CHECK-NEXT: [[TMP3:%.*]] = load i64, ptr [[TMP2]], align 8
; CHECK-NEXT: [[TMP4:%.*]] = extractelement <2 x i64> [[TMP1]], i32 1 ; CHECK-NEXT: [[BROADCAST_SPLATINSERT:%.*]] = insertelement <2 x i64> poison, i64 [[TMP3]], i64 0
; CHECK-NEXT: [[TMP5:%.*]] = getelementptr inbounds i64, ptr [[SRC]], i64 [[TMP4]] ; CHECK-NEXT: [[BROADCAST_SPLAT:%.*]] = shufflevector <2 x i64> [[BROADCAST_SPLATINSERT]], <2 x i64> poison, <2 x i32> zeroinitializer
; CHECK-NEXT: [[TMP6:%.*]] = load i64, ptr [[TMP3]], align 8 ; CHECK-NEXT: [[TMP4:%.*]] = add nsw <2 x i64> [[BROADCAST_SPLAT]], <i64 42, i64 42>
; CHECK-NEXT: [[TMP7:%.*]] = load i64, ptr [[TMP5]], align 8 ; CHECK-NEXT: [[TMP5:%.*]] = getelementptr inbounds i64, ptr [[DST]], i64 [[TMP0]]
; CHECK-NEXT: [[TMP8:%.*]] = insertelement <2 x i64> poison, i64 [[TMP6]], i32 0 ; CHECK-NEXT: [[TMP6:%.*]] = getelementptr inbounds i64, ptr [[TMP5]], i32 0
; CHECK-NEXT: [[TMP9:%.*]] = insertelement <2 x i64> [[TMP8]], i64 [[TMP7]], i32 1 ; CHECK-NEXT: store <2 x i64> [[TMP4]], ptr [[TMP6]], align 8
; CHECK-NEXT: [[TMP10:%.*]] = add nsw <2 x i64> [[TMP9]], <i64 42, i64 42>
; CHECK-NEXT: [[TMP11:%.*]] = getelementptr inbounds i64, ptr [[DST]], i64 [[TMP0]]
; CHECK-NEXT: [[TMP12:%.*]] = getelementptr inbounds i64, ptr [[TMP11]], i32 0
; CHECK-NEXT: store <2 x i64> [[TMP10]], ptr [[TMP12]], align 8
; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 2 ; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], 2
; CHECK-NEXT: [[VEC_IND_NEXT]] = add <2 x i64> [[VEC_IND]], <i64 2, i64 2> ; CHECK-NEXT: [[TMP7:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1000
; CHECK-NEXT: [[TMP13:%.*]] = icmp eq i64 [[INDEX_NEXT]], 1000 ; CHECK-NEXT: br i1 [[TMP7]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP16:![0-9]+]]
; CHECK-NEXT: br i1 [[TMP13]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP16:![0-9]+]]
; CHECK: middle.block: ; CHECK: middle.block:
; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 1000, 1000 ; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 1000, 1000
; CHECK-NEXT: br i1 [[CMP_N]], label [[EXIT:%.*]], label [[SCALAR_PH]] ; CHECK-NEXT: br i1 [[CMP_N]], label [[EXIT:%.*]], label [[SCALAR_PH]]
; CHECK: scalar.ph: ; CHECK: scalar.ph:
; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ 1000, [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ] ; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ 1000, [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ]
; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop: ; CHECK: loop:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
Show All 31 Lines