This is an archive of the discontinued LLVM Phabricator instance.

Ignore/Drop droppable uses for code-sinking in InstCombine
ClosedPublic

Authored by Tyker on Feb 1 2020, 9:16 AM.

Details

Summary

This patch allows code-sinking in InstCombine to be performed when instruction have uses in llvm.assume.

Use are considered droppable when it is preferable to modify the User such that the use disappears rather than to prevent a transformation because of the use.
for now uses are considered droppable if they are in an llvm.assume.

Diff Detail

Event Timeline

Tyker created this revision.Feb 1 2020, 9:16 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 1 2020, 9:16 AM
Tyker updated this revision to Diff 241912.Feb 1 2020, 11:58 PM

Please add a commit message on this one and maybe remove the WIP tag as it is supposed to be reviewed and actually working, right?

Tyker retitled this revision from [WIP] Ignore/Drop droppable uses for code-sinking in InstCombine to Ignore/Drop droppable uses for code-sinking in InstCombine.Feb 2 2020, 10:52 AM
Tyker edited the summary of this revision. (Show Details)
Tyker added a comment.Feb 2 2020, 11:02 AM

Please add a commit message on this one and maybe remove the WIP tag as it is supposed to be reviewed and actually working, right?

the title kind says it all. yes it is working as expected and should be ready for review.

code-sinking in InstCombine is far from as aggressive as it could be. is it also done somewhere else ?
i think that instead of a single use in the successor block we could just code-sink to the successor block dominate all undroppable uses of the instruction if it exists.
or maybe find the highest common dominator of all undroppable uses and if it is not the current basic block code-sink the instruction to it.

Please add a commit message on this one and maybe remove the WIP tag as it is supposed to be reviewed and actually working, right?

the title kind says it all. yes it is working as expected and should be ready for review.

Arguably, "droppable uses" is a new concept you need to explain in the commit message.

code-sinking in InstCombine is far from as aggressive as it could be. is it also done somewhere else ?
i think that instead of a single use in the successor block we could just code-sink to the successor block dominate all undroppable uses of the instruction if it exists.
or maybe find the highest common dominator of all undroppable uses and if it is not the current basic block code-sink the instruction to it.

There is for sure potential, I think we have another sinking pass but I'd need to check.

Tyker edited the summary of this revision. (Show Details)Feb 6 2020, 12:03 PM
jdoerfert added inline comments.Feb 19 2020, 11:57 AM
llvm/lib/Transforms/Utils/KnowledgeRetention.cpp
263 ↗(On Diff #245463)

We do we disallow empty BundleOpInfo here?

llvm/test/Transforms/InstCombine/assume.ll
294

Why don't we sink this one anymore?

441

This test opens up the question if we want to sink simple instructions when we need to destroy assumes. I guess that is unrelated to this patch though.

466

Could you add a test case with a FIXME that show we drop too many assumes when we sink, e.g. the ones that are still dominated.

Tyker marked 2 inline comments as done.Feb 19 2020, 12:18 PM
Tyker added inline comments.
llvm/lib/Transforms/Utils/KnowledgeRetention.cpp
263 ↗(On Diff #245463)

i am not sure i understood the question.

we will return true for empty bundles.

this is a simple utility to check if the operand bundle of an llvm.assume still holds any information. it is used in a few places because instcombine was removing instructions like call void @llvm.assume(i1 true) ["nonnull"(%p)] because the argument to the call is known to be true so the assume was considered useless which is not true anymore.

llvm/test/Transforms/InstCombine/assume.ll
294

in this case there is a single use which is droppable (in an llvm.assume). so hasOneUse return true, but getSingleUndroppableUse returns null. so the old passe will sink the instruction whereas the new won't.

this doesn't matter however because this instruction is only used in an @llvm.assume so it is already dead and the backend will it cleanup.

jdoerfert added inline comments.Feb 19 2020, 12:34 PM
llvm/lib/Transforms/Utils/KnowledgeRetention.cpp
263 ↗(On Diff #245463)

Oh, empty bundles like call void @llvm.assume(i1 true) ["cold"()] ?
Maybe we should put a comment here because I will forget again.

Nit: no != nullptr

Tyker marked an inline comment as done.Feb 19 2020, 1:05 PM
Tyker added inline comments.
llvm/lib/Transforms/Utils/KnowledgeRetention.cpp
263 ↗(On Diff #245463)

call void @llvm.assume(i1 true) ["cold"()] is not considered empty.

this function returns true for truly empty/absent bundles like call void @llvm.assume(i1 true).
or for bundles for which there was WasOn arguments but they have all been dropped. for example if we had call void @llvm.assume(i1 true) ["nonnull"(%p)] and the use of %p get gets dropped. all the only information the assume contains is that a value used to be nonnull, which is basically useless. so the function returns true for those bundles as well.

the general rule is this function returns true if the operand bundle of the assume doesn't hold any usable information. so if this function returns true and the argument of the assume is always true the whole assume should be removed.

i realize that this function probably deserve a more detailed comment.

lebedev.ri added inline comments.Feb 20 2020, 3:28 AM
llvm/lib/IR/AsmWriter.cpp
2557 ↗(On Diff #245463)

Would it be better to ensure that we can't end up in such
seemingly-degenerate state in the first place,
by cleaning up bundles?

Tyker marked an inline comment as done.Feb 21 2020, 7:47 AM
Tyker added inline comments.
llvm/lib/IR/AsmWriter.cpp
2557 ↗(On Diff #245463)

i agree than not having that state would be better but i don't think it is possible without rebuilding instruction after we dropped uses in them.

an other solution could be to mark dropped uses with an undef value instead of a nullptr.

Tyker marked an inline comment as done.Feb 23 2020, 3:04 AM
Tyker added inline comments.
llvm/lib/IR/AsmWriter.cpp
2557 ↗(On Diff #245463)

i tried to find a better solution to represent "dropped" values. but not solution seems to be good.

  • nullptr is problematic because many place assume that operands are never null.
  • rebuilding instructions seems like too expensive for what we are trying to do.

maybe adding a new kind of value to represent it, that is ignored everywhere. but changing the IR for this seems like overkill.

any thought ?

jdoerfert added inline comments.Mar 2 2020, 6:48 PM
llvm/lib/IR/AsmWriter.cpp
2557 ↗(On Diff #245463)

I like the undef solution if we clarify in the LangRef that an assume on undef is ignored.

If we could change the bundle tag we could set it to "ignore", and then pass undef.

llvm/test/Transforms/InstCombine/assume.ll
294

I see.

Tyker updated this revision to Diff 248211.Mar 4 2020, 9:19 AM
Tyker marked an inline comment as done.

rebased this patch on the changes of previous patches in the stack.

Tyker updated this revision to Diff 248231.Mar 4 2020, 10:07 AM
Tyker updated this revision to Diff 249000.Mar 8 2020, 9:11 AM
Tyker edited the summary of this revision. (Show Details)

rebased

jdoerfert added inline comments.Mar 13 2020, 12:48 AM
llvm/lib/Transforms/Utils/Local.cpp
416 ↗(On Diff #249000)

Can you split the isAssumeWithEmptyBundle changes. They look good to me and can be commited, assuming you can add a simple test case showing that instcombine/instsimplify/... will remove certain assume(true) but not all.

For the Instcombine sutff I would probably prefer another opinion (@lebedev.ri @spatel @nikic)

Tyker updated this revision to Diff 250261.Mar 13 2020, 10:53 AM

splitted into this patch and D76147

I like this, let's see if someone else want to comment.

This revision is now accepted and ready to land.Mar 19 2020, 9:40 PM
nikic added a comment.Mar 20 2020, 1:58 AM

Just a general question from my side: In what direction is this heading?

Is this particular transform (InstCombine code sinking) something where assumes were observed to be problematic in practice? Or is this more of a proof-of-concept that will be extended to other one-use checks in InstCombine? (There's a lot of them, and I'm slightly concerned about the amount of boilerplate that would have to be introduced to handle this everywhere.)

Tyker added a comment.Mar 20 2020, 2:40 AM

Just a general question from my side: In what direction is this heading?

Is this particular transform (InstCombine code sinking) something where assumes were observed to be problematic in practice? Or is this more of a proof-of-concept that will be extended to other one-use checks in InstCombine? (There's a lot of them, and I'm slightly concerned about the amount of boilerplate that would have to be introduced to handle this everywhere.)

this is intended as a proof of concept, code-sinking seemed like an easy place to start. I agree with you that extending it to all of instcombine not going to be easy particularly on the testing side.
but we are going to add more assumes with patches like D75825 (disabled by default for now). so we need to minimize the negative impact of assume on other transformations. it is easier to do for assume with operand bundles rather than boolean assumes.

This revision was automatically updated to reflect the committed changes.
MaskRay added a subscriber: MaskRay.EditedMar 25 2020, 5:32 PM

This patch caused an assertion failure on UserParent = PN->getIncomingBlock(*I->use_begin()); .

This can be triggered when a bootstrapped clang builds llvm-symbolizer with ThinLTO with minimized bitcode files clang -c -fthinlto-index=AutoUpgrade.o.thinlto.bc AutoUpgrade.bc -O3 (llvm/lib/IR/AutoUpgrade.cpp).

I am trying to figure out a minimal reproduce.

This patch caused an assertion failure on UserParent = PN->getIncomingBlock(*I->use_begin()); .

This can be triggered when a bootstrapped clang builds llvm-symbolizer with ThinLTO with minimized bitcode files clang -c -fthinlto-index=AutoUpgrade.o.thinlto.bc AutoUpgrade.bc -O3 (llvm/lib/IR/AutoUpgrade.cpp).

I am trying to figure out a minimal reproduce.

Pushed a probable fix: 4c52d51e784ca7603969f2a664e5430d41b9d5dc.

nikic added a comment.Mar 26 2020, 1:35 AM

For the record, this change has caused a small but measurable compile-time regression (http://llvm-compile-time-tracker.com/compare.php?from=b539f18c565656cdd49fc0c37efbaa8e584b2d65&to=f1a9efabcb9bc37b663b0e03ed3d5a5aa7cc055e&stat=instructions). It's not a problem for this change taken by itself, but may be a problem if these APIs are going to see significantly wider use.

Tyker added a comment.EditedMar 27 2020, 7:13 AM

thank you

For the record, this change has caused a small but measurable compile-time regression (http://llvm-compile-time-tracker.com/compare.php?from=b539f18c565656cdd49fc0c37efbaa8e584b2d65&to=f1a9efabcb9bc37b663b0e03ed3d5a5aa7cc055e&stat=instructions). It's not a problem for this change taken by itself, but may be a problem if these APIs are going to see significantly wider use.

i added a patch to minimize the overhead by storing inside the Use whether it is droppable. D76923.