This is an archive of the discontinued LLVM Phabricator instance.

Differential D74944

[LoopVectorize] Fix cost for calls to functions that have vector versions
ClosedPublic

Authored by nemanjai on Feb 20 2020, 7:25 PM.

Details

Reviewers
fpetrogalli
fhahn
sdesmalen
Commits
rGc46b85aaf4d4: [LoopVectorize] Fix cost for calls to functions that have vector versions
Summary

A recent commit (https://reviews.llvm.org/rG66c120f02560ef528a60924104ead66f330190f1) changed the cost for calls to functions that have a vector version for some vectorization factor. However, no check is performed for whether the vectorization factor matches the current one being cost modeled. This leads to attempts to widen call instructions to a vectorization factor for which such a function does not exist, which in turn leads to an assertion failure.

This patch adds the check for vectorization factor (i.e. not just that the called function has a vector version for some VF, but that it has a vector version for this VF).

Diff Detail

Event Timeline

nemanjai created this revision.Feb 20 2020, 7:25 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 20 2020, 7:25 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
Harbormaster completed remote builds in B46969: Diff 245781.Feb 20 2020, 7:55 PM
fpetrogalli added a comment.Feb 21 2020, 8:47 AM

Hi @nemanjai , thank you for pointing this out! I didn't realize that my code was creating this problem.

Kind regards,

Francesco

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
3280–3283

I think that what you have implemented here is doing something very similar to what is already implemented the API provided by the VFShape class and the VFDatabase.

You could first build the VFShape you expect to have for VF and CI by invoking the get method at https://github.com/llvm/llvm-project/blob/f37e899fd73d1a8958246d761eeb306a8846e81a/llvm/include/llvm/Analysis/VectorUtils.h#L103:

VFShape Shape = VFShape::get(*CI, {VF, false} /* EC*/, false /*HasGlobalPred */);

This will create the "shape" that the vector version of the vector call associated with CI will have when trying to vectorize with a vectorization factor of VF.

Then, you can check whether that specific shape for VF is available by querying the VFDatabase with it (see https://github.com/llvm/llvm-project/blob/f37e899fd73d1a8958246d761eeb306a8846e81a/llvm/include/llvm/Analysis/VectorUtils.h#L242):

VFDatabase(*CI).getVectorizedFunction(Shape);

This call will return a nullptr if there is no vector function that realizes vectorization with VF lanes.

3286

VectorMappings.empty() || NoMappingForVF): something is redundant here. Surely if VectorMappings.empty() there is NoMappingForVF. At the same time, if there is NoMappingForVF we should not attempt to vectorize? Or am I missing something?

llvm/test/Transforms/LoopVectorize/widened-massv-call.ll
3

The problem you have pointed out is not related to the use of any specific -vector-library, as the VFDatabase class is build around the vector-function-abi-variant attribute in IR (see https://llvm.org/docs/LangRef.html#call-site-attributes).

I am happy for you to keep this MASSV-specific test, but I think you should also add a test in which the problem is raised directly by a call that uses the vector-function-abi-variant attribute.

Also, I think that you should also add a test in which you use the attribute, and vectorization doesn't happen because there are some mappings in the attribute, but there is no mapping for the VF being checked.

nemanjai marked 2 inline comments as done.Feb 21 2020, 10:09 AM
nemanjai added inline comments.
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
3280–3283

Ah, cool. I didn't really look at the interface very much. Thanks for the suggestion.

3286

Right, the cost we return in this block includes the scalarization cost, so if NoMappingForVF is true, we won't try to vectorize. I suppose we could return some extremely high cost in this case that is guaranteed not to allow vectorization.

I just implemented it this way because this just gets us back to the behaviour before the commit.

nemanjai updated this revision to Diff 245931.Feb 21 2020, 11:23 AM

Updated to use the info from VFDatabase. Thanks @fpetrogalli!

Harbormaster completed remote builds in B47029: Diff 245931.Feb 21 2020, 11:48 AM
fpetrogalli added a comment.Feb 21 2020, 11:49 AM

Hi @nemanjai ,

thank you for updating the code.

Sorry for being picky, I think you should add another test. Your code need to work also for the vector-function-avi-variant attribute and not just for the -vector-library= option.

Kind regards,

Francesco

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
3281

You should not use auto when the type is not obvious: http://llvm.org/docs/CodingStandards.html#use-auto-type-deduction-to-make-code-more-readable

Please s/auto/Function/.

3283

Nit: I just noticed that also the !TLI condition can probably be removed?

nemanjai added a comment.Feb 24 2020, 7:42 AM
In D74944#1887086, @fpetrogalli wrote:

Hi @nemanjai ,

thank you for updating the code.

Sorry for being picky, I think you should add another test. Your code need to work also for the vector-function-avi-variant attribute and not just for the -vector-library= option.

Kind regards,

Francesco

Will do. Note also that this will be the only such test case as far as I can tell, so we might want to add some more coverage there as well independent of this patch.

nemanjai marked an inline comment as done.Feb 24 2020, 7:52 AM
nemanjai added inline comments.
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
3283

Can you please justify? I think the idea is that if we didn't have a TLI object, we would end up with nullptr from getVectorizedFunction() but want to make sure.

nemanjai updated this revision to Diff 246217.Feb 24 2020, 7:56 AM

Removed egregious use of auto and added a vfabi atrribute test case.

fpetrogalli added a comment.Feb 24 2020, 8:27 AM
In D74944#1889360, @nemanjai wrote:
In D74944#1887086, @fpetrogalli wrote:

Hi @nemanjai ,

thank you for updating the code.

Sorry for being picky, I think you should add another test. Your code need to work also for the vector-function-avi-variant attribute and not just for the -vector-library= option.

Kind regards,

Francesco

Will do. Note also that this will be the only such test case as far as I can tell, so we might want to add some more coverage there as well independent of this patch.

Yes, you are right. I'll prepare a patch that does vectorization without using the pre-built TLI infos, just the attribute in the IR.

Thank you for your work!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
3283

Please correct me if I am wrong, but it seems to me that the situation !VecFunc when VecFunc == nullptr is not checked by the tests you have in this patch.

I believe that such test can be done by using the same IR as in llvm/test/Transforms/LoopVectorize/widened-massv-vfabi-attr.ll, with the attribute string being replaced by a 4 lane mangled name _ZGV_LLVM_N4v_llvm.sin.f64(whatever).

Could you please add such test?

Regarding the following:

Can you please justify? I think the idea is that if we didn't have a TLI object, we would end up with nullptr from getVectorizedFunction() but want to make sure.

The TLI is not needed anymore in the LoopVectorizer to check for vectorized function, because all infos needed are carried by the VFDatabase. The TLI is a requirement of the InjectTLIMappings pass, which populate the IR with the vector-function-abi-variant attribute that are constructed out of the ones stored in the TLI. By explaining this, I just realized that removing the !TLI from inside the vectorizer might require a separate patch, so I am happy for you to keep it in here. Sorry for the noise.

Harbormaster completed remote builds in B47136: Diff 246217.Feb 24 2020, 9:44 AM
nemanjai added a comment.Feb 24 2020, 2:51 PM

I am not sure I am actually following what it is you are requesting in terms of testing. Perhaps I need to describe the problems I am solving more thoroughly.

  1. The actual failure only happens with MASSV as far as I can tell. I've actually tried very hard to find a situation in which it can happen with other vector libraries, to no avail. I'll explain why below.
  2. I have added a test case that runs the entire pipeline with the -vector-library option as well as a test case that omits the pass that adds the attributes - i.e. a test for which the vectorizer uses the provided attributes.
  3. The problem is precisely a missing vector function for a vectorization factor of 4, so I am not sure how it would help if I provided an attribute for a fictional function that covers such a vectorization factor.

So why is this uniquely a PPC/MASSV problem?
For the SVML library, no attempt will ever be made to select a vectorization factor wider than 8 (since the largest vector register the X86 back end specifies is 256). Since all the functions for SVML have a VF=8 variant, the problem will never happen. We can artificially force the problem to happen with SVML if we use the same test case and --force-vector-width=16. But I don't think that is representative of real-world code.
For the Accelerate library, there are only entries for the f32 type so we will never attempt to vectorize to anything wider than a factor of 4. Of course, we can artificially force the assert with the same option.
I am not opposed to adding two test cases I just described, but I think they will be artificial and superfluous since the problem is the same regardless of the vector library used.

fpetrogalli accepted this revision.Feb 25 2020, 7:57 AM

Hello @nemanjai , thank you for the exhaustive explanation.

This LGTM now!

Francesco

This revision is now accepted and ready to land.Feb 25 2020, 7:57 AM
Closed by commit rGc46b85aaf4d4: [LoopVectorize] Fix cost for calls to functions that have vector versions (authored by nemanjai). · Explain WhyFeb 26 2020, 7:45 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents

PathSize
llvm/
lib/
Transforms/
Vectorize/
5 lines
test/
Transforms/
LoopVectorize/
59 lines
60 lines

Diff 246872

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

  • This file is larger than 256 KB, so syntax highlighting is disabled by default.
Show First 20 Lines • Show All 3,271 Lines • ▼ Show 20 Linesunsigned LoopVectorizationCostModel::getVectorCallCost(CallInst *CI,
// packing the return values to a vector. // packing the return values to a vector.
unsigned ScalarizationCost = getScalarizationOverhead(CI, VF); unsigned ScalarizationCost = getScalarizationOverhead(CI, VF);
unsigned Cost = ScalarCallCost * VF + ScalarizationCost; unsigned Cost = ScalarCallCost * VF + ScalarizationCost;
// If we can't emit a vector call for this function, then the currently found // If we can't emit a vector call for this function, then the currently found
// cost is the cost we need to return. // cost is the cost we need to return.
NeedToScalarize = true; NeedToScalarize = true;
if (!TLI || CI->isNoBuiltin() || VFDatabase::getMappings(*CI).empty()) VFShape Shape = VFShape::get(*CI, {VF, false}, false /*HasGlobalPred*/);
Function *VecFunc = VFDatabase(*CI).getVectorizedFunction(Shape);
fpetrogalliUnsubmitted
Not Done
ReplyInline Actions

You should not use auto when the type is not obvious: http://llvm.org/docs/CodingStandards.html#use-auto-type-deduction-to-make-code-more-readable

Please s/auto/Function/.

fpetrogalli: You should not use auto when the type is not obvious: http://llvm.org/docs/CodingStandards.
if (!TLI || CI->isNoBuiltin() || !VecFunc)
fpetrogalliUnsubmitted
Not Done
ReplyInline Actions

I think that what you have implemented here is doing something very similar to what is already implemented the API provided by the VFShape class and the VFDatabase.

You could first build the VFShape you expect to have for VF and CI by invoking the get method at https://github.com/llvm/llvm-project/blob/f37e899fd73d1a8958246d761eeb306a8846e81a/llvm/include/llvm/Analysis/VectorUtils.h#L103:

VFShape Shape = VFShape::get(*CI, {VF, false} /* EC*/, false /*HasGlobalPred */);

This will create the "shape" that the vector version of the vector call associated with CI will have when trying to vectorize with a vectorization factor of VF.

Then, you can check whether that specific shape for VF is available by querying the VFDatabase with it (see https://github.com/llvm/llvm-project/blob/f37e899fd73d1a8958246d761eeb306a8846e81a/llvm/include/llvm/Analysis/VectorUtils.h#L242):

VFDatabase(*CI).getVectorizedFunction(Shape);

This call will return a nullptr if there is no vector function that realizes vectorization with VF lanes.

fpetrogalli: I think that what you have implemented here is doing something very similar to what is already…
nemanjaiAuthorUnsubmitted
Done
ReplyInline Actions

Ah, cool. I didn't really look at the interface very much. Thanks for the suggestion.

nemanjai: Ah, cool. I didn't really look at the interface very much. Thanks for the suggestion.
fpetrogalliUnsubmitted
Not Done
ReplyInline Actions

Nit: I just noticed that also the !TLI condition can probably be removed?

fpetrogalli: Nit: I just noticed that also the `!TLI` condition can probably be removed?
nemanjaiAuthorUnsubmitted
Done
ReplyInline Actions

Can you please justify? I think the idea is that if we didn't have a TLI object, we would end up with nullptr from getVectorizedFunction() but want to make sure.

nemanjai: Can you please justify? I think the idea is that if we didn't have a TLI object, we would end…
fpetrogalliUnsubmitted
Not Done
ReplyInline Actions

Please correct me if I am wrong, but it seems to me that the situation !VecFunc when VecFunc == nullptr is not checked by the tests you have in this patch.

I believe that such test can be done by using the same IR as in llvm/test/Transforms/LoopVectorize/widened-massv-vfabi-attr.ll, with the attribute string being replaced by a 4 lane mangled name _ZGV_LLVM_N4v_llvm.sin.f64(whatever).

Could you please add such test?

Regarding the following:

Can you please justify? I think the idea is that if we didn't have a TLI object, we would end up with nullptr from getVectorizedFunction() but want to make sure.

The TLI is not needed anymore in the LoopVectorizer to check for vectorized function, because all infos needed are carried by the VFDatabase. The TLI is a requirement of the InjectTLIMappings pass, which populate the IR with the vector-function-abi-variant attribute that are constructed out of the ones stored in the TLI. By explaining this, I just realized that removing the !TLI from inside the vectorizer might require a separate patch, so I am happy for you to keep it in here. Sorry for the noise.

fpetrogalli: Please correct me if I am wrong, but it seems to me that the situation `!VecFunc` when `VecFunc…
return Cost; return Cost;
// If the corresponding vector cost is cheaper, return its cost. // If the corresponding vector cost is cheaper, return its cost.
fpetrogalliUnsubmitted
Not Done
ReplyInline Actions

VectorMappings.empty() || NoMappingForVF): something is redundant here. Surely if VectorMappings.empty() there is NoMappingForVF. At the same time, if there is NoMappingForVF we should not attempt to vectorize? Or am I missing something?

fpetrogalli: `VectorMappings.empty() || NoMappingForVF)`: something is redundant here. Surely if…
nemanjaiAuthorUnsubmitted
Done
ReplyInline Actions

Right, the cost we return in this block includes the scalarization cost, so if NoMappingForVF is true, we won't try to vectorize. I suppose we could return some extremely high cost in this case that is guaranteed not to allow vectorization.

I just implemented it this way because this just gets us back to the behaviour before the commit.

nemanjai: Right, the cost we return in this block includes the scalarization cost, so if `NoMappingForVF`…
unsigned VectorCallCost = TTI.getCallInstrCost(nullptr, RetTy, Tys); unsigned VectorCallCost = TTI.getCallInstrCost(nullptr, RetTy, Tys);
if (VectorCallCost < Cost) { if (VectorCallCost < Cost) {
NeedToScalarize = false; NeedToScalarize = false;
return VectorCallCost; return VectorCallCost;
} }
return Cost; return Cost;
} }
▲ Show 20 Lines • Show All 4,722 Lines • Show Last 20 Lines

llvm/test/Transforms/LoopVectorize/widened-massv-call.ll

  • This file was added.
; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -vector-library=MASSV -force-vector-interleave=1 \
; RUN: -vectorizer-maximize-bandwidth -O2 -loop-vectorize \
fpetrogalliUnsubmitted
Not Done
ReplyInline Actions

The problem you have pointed out is not related to the use of any specific -vector-library, as the VFDatabase class is build around the vector-function-abi-variant attribute in IR (see https://llvm.org/docs/LangRef.html#call-site-attributes).

I am happy for you to keep this MASSV-specific test, but I think you should also add a test in which the problem is raised directly by a call that uses the vector-function-abi-variant attribute.

Also, I think that you should also add a test in which you use the attribute, and vectorization doesn't happen because there are some mappings in the attribute, but there is no mapping for the VF being checked.

fpetrogalli: The problem you have pointed out is not related to the use of any specific `-vector-library`…
; RUN: -mtriple=powerpc64le-unknown-linux -S -mcpu=pwr9 2>&1 | FileCheck %s
define dso_local double @test(float* %Arr) {
; CHECK-LABEL: @test(
; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[VECTOR_BODY:%.*]]
; CHECK: vector.body:
; CHECK-NEXT: [[INDEX:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
; CHECK-NEXT: [[VEC_PHI:%.*]] = phi <2 x double> [ zeroinitializer, [[ENTRY]] ], [ [[TMP5:%.*]], [[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[INDEX]] to i64
; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds float, float* [[ARR:%.*]], i64 [[TMP0]]
; CHECK-NEXT: [[TMP2:%.*]] = bitcast float* [[TMP1]] to <2 x float>*
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <2 x float>, <2 x float>* [[TMP2]], align 4
; CHECK-NEXT: [[TMP3:%.*]] = fpext <2 x float> [[WIDE_LOAD]] to <2 x double>
; CHECK-NEXT: [[TMP4:%.*]] = call fast <2 x double> @__sind2_massv(<2 x double> [[TMP3]])
; CHECK-NEXT: [[TMP5]] = fadd fast <2 x double> [[TMP4]], [[VEC_PHI]]
; CHECK-NEXT: [[INDEX_NEXT]] = add i32 [[INDEX]], 2
; CHECK-NEXT: [[TMP6:%.*]] = icmp eq i32 [[INDEX_NEXT]], 128
; CHECK-NEXT: br i1 [[TMP6]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop !0
; CHECK: middle.block:
; CHECK-NEXT: [[DOTLCSSA:%.*]] = phi <2 x double> [ [[TMP5]], [[VECTOR_BODY]] ]
; CHECK-NEXT: [[RDX_SHUF:%.*]] = shufflevector <2 x double> [[DOTLCSSA]], <2 x double> undef, <2 x i32> <i32 1, i32 undef>
; CHECK-NEXT: [[BIN_RDX:%.*]] = fadd fast <2 x double> [[DOTLCSSA]], [[RDX_SHUF]]
; CHECK-NEXT: [[TMP7:%.*]] = extractelement <2 x double> [[BIN_RDX]], i32 0
; CHECK-NEXT: ret double [[TMP7]]
;
entry:
br label %for.cond
for.cond:
%Sum.0 = phi double [ 0.000000e+00, %entry ], [ %add, %for.inc ]
%i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
%cmp = icmp slt i32 %i.0, 128
br i1 %cmp, label %for.body, label %for.cond.cleanup
for.cond.cleanup:
br label %for.end
for.body:
%idxprom = sext i32 %i.0 to i64
%arrayidx = getelementptr inbounds float, float* %Arr, i64 %idxprom
%0 = load float, float* %arrayidx, align 4
%conv = fpext float %0 to double
%1 = call fast double @llvm.sin.f64(double %conv)
%add = fadd fast double %Sum.0, %1
br label %for.inc
for.inc:
%inc = add nsw i32 %i.0, 1
br label %for.cond
for.end:
ret double %Sum.0
}
declare double @llvm.sin.f64(double)

llvm/test/Transforms/LoopVectorize/widened-massv-vfabi-attr.ll

  • This file was added.
; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt -vectorizer-maximize-bandwidth -mtriple=powerpc64le-- -S \
; RUN: -targetlibinfo -loop-simplify -loop-rotate -loop-vectorize \
; RUN: -instcombine -simplifycfg -force-vector-interleave=1 < %s | FileCheck %s
define dso_local double @test(float* %Arr) {
; CHECK-LABEL: @test(
; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[VECTOR_BODY:%.*]]
; CHECK: vector.body:
; CHECK-NEXT: [[INDEX:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
; CHECK-NEXT: [[VEC_PHI:%.*]] = phi <2 x double> [ zeroinitializer, [[ENTRY]] ], [ [[TMP5:%.*]], [[VECTOR_BODY]] ]
; CHECK-NEXT: [[TMP0:%.*]] = sext i32 [[INDEX]] to i64
; CHECK-NEXT: [[TMP1:%.*]] = getelementptr inbounds float, float* [[ARR:%.*]], i64 [[TMP0]]
; CHECK-NEXT: [[TMP2:%.*]] = bitcast float* [[TMP1]] to <2 x float>*
; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <2 x float>, <2 x float>* [[TMP2]], align 4
; CHECK-NEXT: [[TMP3:%.*]] = fpext <2 x float> [[WIDE_LOAD]] to <2 x double>
; CHECK-NEXT: [[TMP4:%.*]] = call fast <2 x double> @__sind2_massv(<2 x double> [[TMP3]])
; CHECK-NEXT: [[TMP5]] = fadd fast <2 x double> [[VEC_PHI]], [[TMP4]]
; CHECK-NEXT: [[INDEX_NEXT]] = add i32 [[INDEX]], 2
; CHECK-NEXT: [[TMP6:%.*]] = icmp eq i32 [[INDEX_NEXT]], 128
; CHECK-NEXT: br i1 [[TMP6]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop !0
; CHECK: middle.block:
; CHECK-NEXT: [[RDX_SHUF:%.*]] = shufflevector <2 x double> [[TMP5]], <2 x double> undef, <2 x i32> <i32 1, i32 undef>
; CHECK-NEXT: [[BIN_RDX:%.*]] = fadd fast <2 x double> [[TMP5]], [[RDX_SHUF]]
; CHECK-NEXT: [[TMP7:%.*]] = extractelement <2 x double> [[BIN_RDX]], i32 0
; CHECK-NEXT: ret double [[TMP7]]
;
entry:
br label %for.cond
for.cond:
%Sum.0 = phi double [ 0.000000e+00, %entry ], [ %add, %for.inc ]
%i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
%cmp = icmp slt i32 %i.0, 128
br i1 %cmp, label %for.body, label %for.cond.cleanup
for.cond.cleanup:
br label %for.end
for.body:
%idxprom = sext i32 %i.0 to i64
%arrayidx = getelementptr inbounds float, float* %Arr, i64 %idxprom
%0 = load float, float* %arrayidx, align 4
%conv = fpext float %0 to double
%1 = call fast double @llvm.sin.f64(double %conv) #1
%add = fadd fast double %Sum.0, %1
br label %for.inc
for.inc:
%inc = add nsw i32 %i.0, 1
br label %for.cond
for.end:
ret double %Sum.0
}
declare double @llvm.sin.f64(double) #0
declare <2 x double> @__sind2_massv(<2 x double>) #0
attributes #0 = { nounwind readnone speculatable willreturn }
attributes #1 = { "vector-function-abi-variant"="_ZGV_LLVM_N2v_llvm.sin.f64(__sind2_massv)" }