This is an archive of the discontinued LLVM Phabricator instance.

[LV] Allow assume calls in predicated blocks.
ClosedPublic

Authored by fhahn on Oct 10 2019, 9:50 AM.

Details

Summary

The assume intrinsic is intentionally marked as may reading/writing
memory, to avoid passes moving them around. When flattening the CFG
for predicated blocks, we have to drop the assume calls, as they
are control-flow dependent.

Note that this patch also moves setting State->CFG.PrevVPBB after
we executed the recipes in a VPBB. This way, we have access to the real
VPBB while executing a block.

Fixes PR43620.

Diff Detail

Event Timeline

fhahn created this revision.Oct 10 2019, 9:50 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 10 2019, 9:50 AM
xbolva00 added inline comments.
llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp
904

You can drop m_Value()

if (match(&I, m_Intrinsic<Intrinsic::assume>())) {

Wil work too

hfinkel added inline comments.
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
7002

Unintentional whitespace change?

fhahn updated this revision to Diff 224464.Oct 10 2019, 1:44 PM

Address comments, thanks!

fhahn marked 2 inline comments as done.Oct 10 2019, 1:44 PM
fhahn added inline comments.
llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp
904

Excellent, thanks!

fhahn marked an inline comment as done.Oct 10 2019, 1:46 PM
fhahn added inline comments.
llvm/test/Transforms/LoopVectorize/predicate-assume.ll
3

I've not added a test with calls to assume in the loop header here, because we already have them in llvm/test/Transforms/LoopVectorize/X86/assume.ll.

Ayal added a comment.Oct 13 2019, 3:25 AM

If conditional assumes are to be dropped, better do so on entry to VPlan, as in DeadInstructions, rather than representing them in ReplicateRecipe (as do unconditional assumes) and silencing their code generation.

To retain conditional assumes along with their control flow, they could be marked under isScalarWithPredication; but this complicates vectorization, plus what use are such assumes when all else is if-converted(?)

Conditional assumes under uniform control flow could be retained, along with the uniform control flow they depend upon; this may be mostly relevant for outerloop vectorization.

hsaito added a comment.EditedOct 14 2019, 10:44 AM

If conditional assumes are to be dropped, better do so on entry to VPlan, as in DeadInstructions, rather than representing them in ReplicateRecipe (as do unconditional assumes) and silencing their code generation.

To retain conditional assumes along with their control flow, they could be marked under isScalarWithPredication; but this complicates vectorization, plus what use are such assumes when all else is if-converted(?)

Conditional assumes under uniform control flow could be retained, along with the uniform control flow they depend upon; this may be mostly relevant for outerloop vectorization.

To be more precise:

Assumes should be dropped at the time the vectorizer makes the incompatible decision ---- i.e. a assume is no longer "to be guarded" by the original (per-element or uniform) condition. Right now, in the non-VPlan-native path, recording of the decisions already made happens at entry to VPlan. In the VPlan native path, this would be VPlan to VPlan xform, as the decisions are recorded as they are made.

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

Do we want to keep this white space?

fhahn added a comment.Oct 20 2019, 4:23 PM

If conditional assumes are to be dropped, better do so on entry to VPlan, as in DeadInstructions, rather than representing them in ReplicateRecipe (as do unconditional assumes) and silencing their code generation.

To retain conditional assumes along with their control flow, they could be marked under isScalarWithPredication; but this complicates vectorization, plus what use are such assumes when all else is if-converted(?)

Conditional assumes under uniform control flow could be retained, along with the uniform control flow they depend upon; this may be mostly relevant for outerloop vectorization.

I thought it might be desirable to only drop the calls at the point where we know for certain that we cannot preserve them: when we emit them in a block that gets merge in its predecessor. By doing it in the recipe, it should also be applicable to the outer loop vectorization. Alternatively we can drop them all as a first step, if that is preferred. Please let me know :)

I think we should try too hard to retain them (through marking them as scalar-with-predication), as the benefit of them for the vectorized loop after the vectorizer is likely to be quite small.

Ayal added a comment.Oct 21 2019, 1:52 PM

If conditional assumes are to be dropped, better do so on entry to VPlan, as in DeadInstructions, rather than representing them in ReplicateRecipe (as do unconditional assumes) and silencing their code generation.

To retain conditional assumes along with their control flow, they could be marked under isScalarWithPredication; but this complicates vectorization, plus what use are such assumes when all else is if-converted(?)

Conditional assumes under uniform control flow could be retained, along with the uniform control flow they depend upon; this may be mostly relevant for outerloop vectorization.

I thought it might be desirable to only drop the calls at the point where we know for certain that we cannot preserve them: when we emit them in a block that gets merge in its predecessor. By doing it in the recipe, it should also be applicable to the outer loop vectorization. Alternatively we can drop them all as a first step, if that is preferred. Please let me know :)

I vote to simply drop conditional assumes as a first step, at this time. In any case it's better in general if decisions get represented explicitly in VPlan, rather than having such logic kick in during code-gen. (Even if a block gets merged in its predecessor, better also check that the latter has more than one successor.) Following D68577 such assumes could be dropped as a VPlan-to-VPlan transformation.

I think we should try too hard to retain them (through marking them as scalar-with-predication), as the benefit of them for the vectorized loop after the vectorizer is likely to be quite small.

should >> should not?

For the sake of completeness, note that a conditional assume could be retained even under predication, by combining its block predicate within the assume predicate. I.e., a conditional "if (c) assume (p)" can be converted to an unconditional "assume (c implies p)" or "assume (!c || p)".

fhahn planned changes to this revision.Oct 31 2019, 3:38 PM

Thanks, I’ll update the patch to drop the assume calls for now and let’s go from there

uenoku added a subscriber: uenoku.Nov 2 2019, 9:24 AM
fhahn updated this revision to Diff 231111.Nov 26 2019, 11:15 AM

Updated to use Vplan2VPlan transform to drop assume calls, if required.

Build result: FAILURE - Could not check out parent git hash "dcb1398d042ac24cdf8ff0ff7ac7ad2e310ac2dd". It was not found in the repository. Did you configure the "Parent Revision" in Phabricator properly? Trying to apply the patch to the master branch instead...

ERROR: arc patch failed with error code 1. Check build log for details.
Log files: console-log.txt, CMakeCache.txt

gilr added a subscriber: gilr.Dec 6 2019, 1:44 AM
gilr added inline comments.
llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp
89 ↗(On Diff #231111)

Shouldn't this recurse into regions for completeness?

98 ↗(On Diff #231111)

This block is only asserting. Can it be compressed into the asserted expression / go under an #ifdef assert / use llvm_unreachable()?

llvm/lib/Transforms/Vectorize/VPlanTransforms.h
32 ↗(On Diff #231111)

dropAssumes()?

llvm/test/Transforms/LoopVectorize/predicate-assume.ll
11

Enough to CHECK for VPlan and then CHECK-NOT for the assert?

40

Enough to CHECK for vector.body and then CHECK-NOT for the assert?

Ayal added a comment.Dec 28 2019, 9:06 AM

[snip]

I vote to simply drop conditional assumes as a first step, at this time. [snip] Following D68577 such assumes could be dropped as a VPlan-to-VPlan transformation.

The alternative mentioned above of following D68577 would result in something like

+ auto &ConditionalAssumes = Legal->getConditionalAssumes();
...
  // Mark instructions we'll need to discard later as
  // ingredients whose recipe we'll need to record.
+  for (auto ConditionalAssume : ConditionalAssumes)
+    RecipeBuilder.recordRecipeOf(ConditionalAssume);
+
...
+  // Discard conditional assumes.
+  for (auto ConditionalAssume : ConditionalAssumes)
+    RecipeBuilder.getRecipe(ConditionalAssume)->eraseFromParent();

where Legal->getConditionalAssumes() is analogous to the proposed Legal->mustDropAssumes(), returning the set of conditional assumes rather than boolean.

Hence the vote to simply include all ConditionalAssumes in DeadInstructions instead.

Having a VPInstruction-based VPlan-to-VPlan transformation would be fine, of course, which drops assumes in if-converted blocks and keeps those under (retained, if any) uniform branches. For buildVPlanWithVPRecipes, however, it would be better to make progress on refactoring Recipes into VPInstructions, wrt assume intrinsics in this case, than to start befriending Recipes and examine their ingredients. As for the VPInstruction-based transformation, should VPInstruction provide an adequate interface (isAssume(), or perhaps an Assume Opcode?) rather than befriending it and examining its UnderlyingInstr(?).

fhahn updated this revision to Diff 236189.Jan 4 2020, 10:13 AM

[snip]
Hence the vote to simply include all ConditionalAssumes in DeadInstructions instead.

Having a VPInstruction-based VPlan-to-VPlan transformation would be fine, of course, which drops assumes in if-converted blocks and keeps those under (retained, if any) uniform branches. For buildVPlanWithVPRecipes, however, it would be better to make progress on refactoring Recipes into VPInstructions, wrt assume intrinsics in this case, than to start befriending Recipes and examine their ingredients. As for the VPInstruction-based transformation, should VPInstruction provide an adequate interface (isAssume(), or perhaps an Assume Opcode?) rather than befriending it and examining its UnderlyingInstr(?).

Agreed! Let's keep things simple in this patch.

I went ahead and updated the patch to collect the assume instructions in Legal and then add them to the dead instructions just before creating the recipies. Alternatively we could record and remove the assume instructions, but it seems using DeadInstructions is slightly more straight forward.

Unit tests: fail. 61241 tests passed, 3 failed and 736 were skipped.

failed: libc++.std/thread/thread_mutex/thread_mutex_requirements/thread_mutex_requirements_mutex/thread_mutex_class/try_lock.pass.cpp
failed: libc++.std/thread/thread_mutex/thread_mutex_requirements/thread_mutex_requirements_mutex/thread_mutex_recursive/lock.pass.cpp
failed: libc++.std/thread/thread_mutex/thread_mutex_requirements/thread_mutex_requirements_mutex/thread_mutex_recursive/try_lock.pass.cpp

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Ayal added a comment.Jan 5 2020, 12:29 PM

Thanks. Perhaps it's better for Legal to declare via getConditionalAssumes() what is being returning, and let LVP decide what to do with them(*), rather than to assume from the start via getAssumesToDrop() that they must all be dropped.

LVP could collect all conditional assumes itself, btw, but it's easier for Legal to do so, and also logical as they deserve special attention in terms of legality.

(*) As discussed, instead of dropping such assumes could be retained if their condition is retained (being uniform or if handled via isScalarWithPredication()/sinkScalarOperands()?) or if their condition is fused into the assumption.

fhahn updated this revision to Diff 236263.Jan 5 2020, 1:36 PM

Thanks. Perhaps it's better for Legal to declare via getConditionalAssumes() what is being returning, and let LVP decide what to do with them(*), rather than to assume from the start via getAssumesToDrop() that they must all be dropped.

LVP could collect all conditional assumes itself, btw, but it's easier for Legal to do so, and also logical as they deserve special attention in terms of legality.

+1, getAssumesToDrop makes more sense when we improve things in the future. I've updated the name.

Unit tests: pass. 61250 tests passed, 0 failed and 736 were skipped.

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

gilr added inline comments.Jan 6 2020, 5:06 AM
llvm/test/Transforms/LoopVectorize/predicate-assume.ll
3

It would be better to add the new predicated cases to the existing assume.ll.
(Not sure why it resides under X86 - seems it could instead be target independent and force vectorization, but that can be done separately)

11

ping?

40

ping?

fhahn updated this revision to Diff 236417.Jan 6 2020, 10:40 AM
fhahn marked 3 inline comments as done.

Remove auto-generated check lines.

fhahn marked 2 inline comments as done.Jan 6 2020, 10:42 AM

Thanks. Perhaps it's better for Legal to declare via getConditionalAssumes() what is being returning, and let LVP decide what to do with them(*), rather than to assume from the start via getAssumesToDrop() that they must all be dropped.

LVP could collect all conditional assumes itself, btw, but it's easier for Legal to do so, and also logical as they deserve special attention in terms of legality.

(*) As discussed, instead of dropping such assumes could be retained if their condition is retained (being uniform or if handled via isScalarWithPredication()/sinkScalarOperands()?) or if their condition is fused into the assumption.

llvm/test/Transforms/LoopVectorize/predicate-assume.ll
3

I am not sure. I personally prefer smaller, more targeted test files, but if you think having a larger test file is better I'll merge them.

11

Ah sorry, I totally missed that. I agree it's better to just check for assumes. The autogenerated checks are unnecessary verbose.

Unit tests: pass. 61257 tests passed, 0 failed and 736 were skipped.

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Ayal accepted this revision.Jan 12 2020, 3:36 AM

Agree that it's better to merge the new conditional assume tests with the existing unconditional assume tests in the same file.

Thanks for making the changes!

llvm/test/Transforms/LoopVectorize/predicate-assume.ll
3

The above forthcoming comment emphasizes that these tests complement each other: “I've not added a test with calls to assume in the loop header here, because we already have them in llvm/test/Transforms/LoopVectorize/X86/assume.ll”.

Quoting the end of https://llvm.org/docs/TestingGuide.html#writing-new-regression-tests:
“Put related tests into a single file rather than having a separate file per test. Check if there are files already covering your feature and consider adding your code there instead of creating a new file.”

This revision is now accepted and ready to land.Jan 12 2020, 3:36 AM
fhahn added a comment.Jan 16 2020, 2:13 AM

Agree that it's better to merge the new conditional assume tests with the existing unconditional assume tests in the same file.

Sure! I've made the X86/assume.ll test non-X86 specific and I'll land the patch with the new test added to it directly.

Thanks for taking a look!

This revision was automatically updated to reflect the committed changes.