Page MenuHomePhabricator

Hoist llvm.assume into single predecessor if block otherwise empty
Needs ReviewPublic

Authored by markus on May 28 2021, 6:38 AM.

Details

Summary

Here is a first go at what was discussed in the thread of https://lists.llvm.org/pipermail/llvm-dev/2021-May/150739.html

Hoist llvm.assume instrinsics (and rewrite condition) from blocks where they would inhibit transformation by SimplifyCFGOpt::simplifyUncondBranch.

Diff Detail

Event Timeline

markus created this revision.May 28 2021, 6:38 AM
markus requested review of this revision.May 28 2021, 6:38 AM
Herald added a project: Restricted Project. · View Herald TranscriptMay 28 2021, 6:38 AM
nikic added a reviewer: nikic.EditedMay 28 2021, 6:55 AM
nikic added a subscriber: nikic.

This kind of transformation should probably eventually reside in lib/Transforms/Utils/SimplifyCFG.cpp but for now it seemed easier and a smaller change to just leave it in CodeGenPrepare.

I don't think this transform makes a lot of sense in CGP, I'd prefer it to go directly to SimplifyCFG (after which we can drop the CGP code).

However, I'm not sure the whole concept of "hoisting assumes" even makes sense. I'm not sure if we have any passes that can reason about assume(c1 || c2) conditions. We have a lot that can reason about assume(c1 && c2) once it has been canonicalized to assume(c1) assume(c2), but probably nothing that handles ||. The only case in which it could end up being useful is if at a later point, we can show that c1 is actually false, which means we can fold it to just assume(c2), at which point it becomes usable.

Another thing to consider is that assumes with operand bundles would require a more complex transform, to convert the operand bundle form back into a condition form.

I think we would be better off to just drop these assumes. The framing I'm thinking of here is that SimplifyCFG should generally be ignoring ephemeral values in transforms. So if normally SimplifyCFG would drop a block that contains no instructions, then it should also drop a block that only contains ephemeral values.

This kind of transformation should probably eventually reside in lib/Transforms/Utils/SimplifyCFG.cpp but for now it seemed easier and a smaller change to just leave it in CodeGenPrepare.

I don't think this transform makes a lot of sense in CGP, I'd prefer it to go directly to SimplifyCFG (after which we can drop the CGP code).

I agree.

I think we would be better off to just drop these assumes. The framing I'm thinking of here is that SimplifyCFG should generally be ignoring ephemeral values in transforms. So if normally SimplifyCFG would drop a block that contains no instructions, then it should also drop a block that only contains ephemeral values.

I disagree.

if (x)
  assume(y)

is a natural way to spell something for the user.
We should not just drop it without having a good reason.
While we might not use assume(x && y) directly, we will use it if we specialize x to true in some places.

markus updated this revision to Diff 348737.May 31 2021, 1:01 AM

Since there seem to be agreement on the placement in SimplifyCFG the code has been moved there.

Wrt assume operand bundles I am thinking that those can always simply be dropped.

Old CodeGenPrepare tests have been temporarily disabled but will be revamped in the SimplifyCFG setting once it is decided if this transformation should hoist or drop assumes (from or in otherwise empty blocks).

reames added a comment.Jun 4 2021, 3:14 PM

This kind of transformation should probably eventually reside in lib/Transforms/Utils/SimplifyCFG.cpp but for now it seemed easier and a smaller change to just leave it in CodeGenPrepare.

I don't think this transform makes a lot of sense in CGP, I'd prefer it to go directly to SimplifyCFG (after which we can drop the CGP code).

I agree.

I think we would be better off to just drop these assumes. The framing I'm thinking of here is that SimplifyCFG should generally be ignoring ephemeral values in transforms. So if normally SimplifyCFG would drop a block that contains no instructions, then it should also drop a block that only contains ephemeral values.

I disagree.

if (x)
  assume(y)

is a natural way to spell something for the user.
We should not just drop it without having a good reason.
While we might not use assume(x && y) directly, we will use it if we specialize x to true in some places.

Er, I think you misread the comment you were replying to. The comment was discussing assume(A || B), your response is discussing assume(A && B). Given the context of the discussion, that difference seems important.

My own opinion is closer to that of @nikic. I think we should not be letting assumes block transforms. We should attempt to salvage assume information where we can, but only on a best effort basis. I do think we should generate the assume(A || B) form if that's the logical salvage even if nothing currently can infer from that.

reames added a comment.Jun 4 2021, 3:15 PM

Wrt assume operand bundles I am thinking that those can always simply be dropped.

I think you can simply ignore operand bundle forms. This is not on by default, and the implementation isn't yet mature. The folks working on that can pay the cost of figuring out what to do for them. As long as your code doesn't crash on operand bundle assumes, I don't really care what it does with them.

reames added inline comments.Jun 4 2021, 3:21 PM
llvm/lib/CodeGen/CodeGenPrepare.cpp
380 ↗(On Diff #348737)

Please split the new transform in SimplifyCFG and the deletion of the old CGP code into two patches. The former should be independently worthwhile if structured properly.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp
6776

I don't think this is the right framing. We don't want to unconditionally hoist assumes, we only want to hoist them if they'd otherwise inhibit a transformation. (e.g. If the successor block was otherwise empty, we hoist as part of threading the edge to the successors successor.)

llvm/test/Transforms/InstCombine/assume-align.ll
20

If we don't predicate the store, the shown transform here does not appear profitable.

reames requested changes to this revision.Jun 4 2021, 3:21 PM
This revision now requires changes to proceed.Jun 4 2021, 3:21 PM
jdoerfert added a comment.EditedJun 4 2021, 3:41 PM

[EDIT respond to the assume bundle comment]

This kind of transformation should probably eventually reside in lib/Transforms/Utils/SimplifyCFG.cpp but for now it seemed easier and a smaller change to just leave it in CodeGenPrepare.

I don't think this transform makes a lot of sense in CGP, I'd prefer it to go directly to SimplifyCFG (after which we can drop the CGP code).

I agree.

I think we would be better off to just drop these assumes. The framing I'm thinking of here is that SimplifyCFG should generally be ignoring ephemeral values in transforms. So if normally SimplifyCFG would drop a block that contains no instructions, then it should also drop a block that only contains ephemeral values.

I disagree.

if (x)
  assume(y)

is a natural way to spell something for the user.
We should not just drop it without having a good reason.
While we might not use assume(x && y) directly, we will use it if we specialize x to true in some places.

Er, I think you misread the comment you were replying to. The comment was discussing assume(A || B), your response is discussing assume(A && B). Given the context of the discussion, that difference seems important.

My own opinion is closer to that of @nikic. I think we should not be letting assumes block transforms. We should attempt to salvage assume information where we can, but only on a best effort basis. I do think we should generate the assume(A || B) form if that's the logical salvage even if nothing currently can infer from that.

Unsure if I got it right or wrong before but what you said last is what I like too. Salvage assumes in blocks we want to remove if possible. At the same time, "ignore" assumes when the decision for transformations are made.

Wrt assume operand bundles I am thinking that those can always simply be dropped.

I think you can simply ignore operand bundle forms. This is not on by default, and the implementation isn't yet mature. The folks working on that can pay the cost of figuring out what to do for them. As long as your code doesn't crash on operand bundle assumes, I don't really care what it does with them.

Given that operand bundles for align are the default, people might care: https://clang.godbolt.org/z/Kq8c81T15
That said, I think dropping them is the only reasonable choice we have right now. We don't have a concept of a "pre-condition" that needs to hold in order for the rest to be usable.

markus added a comment.Jun 7 2021, 3:30 AM

My own opinion is closer to that of @nikic. I think we should not be letting assumes block transforms. We should attempt to salvage assume information where we can, but only on a best effort basis. I do think we should generate the assume(A || B) form if that's the logical salvage even if nothing currently can infer from that.

Unsure if I got it right or wrong before but what you said last is what I like too. Salvage assumes in blocks we want to remove if possible. At the same time, "ignore" assumes when the decision for transformations are made.

So what does this mean in practice?
I interpret it as follows:
We provide a function say bool isBlockEmptyExceptAssumes(BasicBlock *BB) and we update the decision making of all the existing CFG transformations to use that. We provide another function say void hoistAssumesFromBlockKnownToBeOtherwiseEmpty(BasicBlock *BB) that all those CFG transformations need to call during their transformation if they used that fact that any of the blocks checked out as true with the former function.

Now maybe there aren't that many CFG transformations where this is relevant and maybe it integrates easily, I don't know, but it does seem like a somewhat larger change.

llvm/lib/CodeGen/CodeGenPrepare.cpp
380 ↗(On Diff #348737)

That makes sense. Will do.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp
6776

I don't fully understand this comment. The current patch does not unconditionally hoist assumes. It hoists assumes if the block in question is otherwise empty. Thus preventing those assumes from inhibiting other transformations later on. Of course it will require another iteration of CFG considerations but isn't that the way these CFG optimizations are generally structured (one transform enables another transform)?

I guess one way I could interpret this comment is that we should provide a utility function say isBlockEmptyExceptAssumes() that can then be queried in the decision making of all the other CFG transformations. So if a block only contains assumes then treat it as if it was empty when performing those optimizations. Maybe that is doable but it does not seem obvious that it would integrate easily with the existing transformations.

llvm/test/Transforms/InstCombine/assume-align.ll
20

I didn't even know that we had predicated scalar stores on IR. Either way is it a generic comment that it would be good if the stores was eventually predicated (in the final emission) or does it imply that predication should happen as part of simplify-cfg now with the added transformation?

We provide a function say bool isBlockEmptyExceptAssumes(BasicBlock *BB) and we update the decision making of all the existing CFG transformations to use that. We provide another function say void hoistAssumesFromBlockKnownToBeOtherwiseEmpty(BasicBlock *BB) that all those CFG transformations need to call during their transformation if they used that fact that any of the blocks checked out as true with the former function.

Now maybe there aren't that many CFG transformations where this is relevant and maybe it integrates easily, I don't know, but it does seem like a somewhat larger change.

The above sounds sensible. To keep it small you can use it only in the transformation relevant to you right now. We can update others as we go.

markus updated this revision to Diff 350601.Jun 8 2021, 7:33 AM

Is this the way we want to integrate into SimplifyCFG? Currently only tested with the supplied lit-test.

Not sure I've actually captured all the logic in how we ended up here, considering the original problem was that CodeGenPrepare is too pessimistic when it removes all llvm.assume intrinsics when doing CFG transformations.

The first patch from @markus aimed at improving CodeGenPrepare by making it a bit less aggressive and keeping some llvm.assumes. And then there was an idea to make it even less aggressive by also salvaging some llvm.assume intrinsics.

Now, we have ended up with a patch modifying SimplifyCFG instead. Which obviously doesn't solve the problems we have in CodeGenPrepare. So what is the ultimate goal with this approach? Is the idea that we should remove the CFG transformations in CodeGenPrepare (at least eliminateMostlyEmptyBlocks?) in a follow up patch? Or is the idea to reuse these Utils helpers in CodeGenPrepare when doing such CFG transforms?

I mean, currently the CFG tranformations in CodeGenPrepare might depend on the existence of llvm.assume in the code. That problem still exist unless we also do something in CodeGenPrepare as well, given that the ultimate goal still is that we want to keep/salvage as many llvm.assume intrinsics as possible until ISel.
According to code comments in CodeGenPrepare those transforms are done (at least partially) as a cleanup after early IR passes in codegen such as LSR. And not all targets are running SimplifyCFG between LSR and CodeGenPrepare. Maybe the idea is to also add SimplifyCFG to the codegen pipeline just before CodeGenPrepare as a preparation to remove CodeGenPrepare::eliminateMostlyEmptyBlocks?

I thought the problem was that a block with an assume caused us to miss out on some backed optimization.
The proposed solution was to eliminate blocks that only contain an assume as side effect early as middle-end
optimizations would also benefit from a simplified CFG.

bjope added a comment.Jun 14 2021, 1:08 PM

I thought the problem was that a block with an assume caused us to miss out on some backed optimization.
The proposed solution was to eliminate blocks that only contain an assume as side effect early as middle-end
optimizations would also benefit from a simplified CFG.

The problem @markus is working on is that the assumes are removed already in CodeGenPrepare. So there is no assumes left in the IR after CodeGenPrepare, and any AliasAnalysis queries after CodeGenPrepare won't benefit from the assumes.
Thus, any guidance here that isn't moving towards the goal of handling assumes better in CodeGenPrepare (preferrably keeping/salvaging as many assumes as possible) is a bit confusing.

nikic added a comment.Jun 14 2021, 1:14 PM

@bjope This SimplifyCFG patch allows us to remove the assume dropping code in CGP subsequently.

llvm/lib/Transforms/Utils/Local.cpp
1112

This needs to be CreateLogicalOr.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp
307

You need isSafeToSpeculativelyExecute() here, not just !mayHaveSideEffects().

Thanks @bjope for the input. I do share your concern. While I think we all agree that SimplifyCFG is the right place for this kind of transformation the steps that would follow acceptance and landing of the current patch do not seem to directly lead to being able to remove the unconditional assume elimination from CodeGenPrepare. At least not without possibly introducing other degradation as there may be other transformation that have run in between and now put assumes in inconvenient places. As pointed out by @bjope.

markus updated this revision to Diff 352078.Jun 15 2021, 2:54 AM
markus edited the summary of this revision. (Show Details)

Updated to address (some) review comments, clang-tidy warnings and taking the Succ->getSinglePredecessor() condition into account to avoid duplication of instructions.