This is an archive of the discontinued LLVM Phabricator instance.

[BasicBlockUtils] Allow splitting predecessors with callbr terminators
ClosedPublic

Authored by nikic on Jul 6 2022, 7:41 AM.

Details

Summary

SplitBlockPredecessors currently asserts if one of the predecessor terminators is a callbr. This limitation was originally necessary, because just like with indirectbr, it was not possible to replace successors of a callbr. However, this is no longer the case since D67252. As the requirement nowadays is that callbr must reference all blockaddrs directly in the call arguments, and these get automatically updated when setSuccessor() is called, we no longer need this limitation.

The only thing we need to do here is use replaceSuccessorWith() instead of replaceUsesOfWith(), because only the former does the necessary blockaddr updating magic.

I believe there's other similar limitations that can be removed, e.g. related to critical edge splitting.

Diff Detail

Event Timeline

nikic created this revision.Jul 6 2022, 7:41 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 6 2022, 7:41 AM
nikic requested review of this revision.Jul 6 2022, 7:41 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 6 2022, 7:41 AM
nikic updated this revision to Diff 442573.Jul 6 2022, 7:47 AM

Remove one more check.

instead of replaceUsesOfWith(), because only the former does the necessary blockaddr updating magic.

Indeed, see: https://reviews.llvm.org/D74947.

Thanks for the patch, will do review and more testing later. Just getting back online after a long holiday weekend.

nickdesaulniers added inline comments.Jul 6 2022, 9:37 AM
llvm/lib/Transforms/Scalar/LICM.cpp
1510–1512

I think I attempted this in https://reviews.llvm.org/D94833, see the attached bug report from @nathanchance .

nikic added inline comments.Jul 6 2022, 9:51 AM
llvm/lib/Transforms/Scalar/LICM.cpp
1510–1512

I think that patch was missing the change to SplitBlockPredecessors() done here.

If we don't support using arbitrary blockaddresses as destinations, can we stop using blockaddress to represent the destinations? The presence of blockaddress blocks optimizations even if we aren't imposing the full control flow restrictions.

nikic added a comment.Jul 6 2022, 12:03 PM

If we don't support using arbitrary blockaddresses as destinations, can we stop using blockaddress to represent the destinations? The presence of blockaddress blocks optimizations even if we aren't imposing the full control flow restrictions.

Yeah, dropping the blockaddress arguments sounds reasonable and should largely remove the need for special handling of callbr in transforms. I think a possible way to do this would be to say that we implicitly pass the blockaddresses for all callbr targets at the end of the argument list. (Not sure I want to volunteer for that change though...)

If we don't support using arbitrary blockaddresses as destinations, can we stop using blockaddress to represent the destinations? The presence of blockaddress blocks optimizations even if we aren't imposing the full control flow restrictions.

That's what I had in mind in https://github.com/ClangBuiltLinux/linux/issues/972. Particularly because of https://reviews.llvm.org/D74947. On my TODO list, but seemingly never high enough priority.

nickdesaulniers accepted this revision.Jul 6 2022, 2:42 PM

Thanks for the patch and feedback on my linked issue. Testing x86_64 and arm64 defconfig, defconfig+thinLTO Linux kernel builds + boots.

This revision is now accepted and ready to land.Jul 6 2022, 2:42 PM

I did a set of builds with this patch on mainline and saw no issues.

This revision was landed with ongoing or failed builds.Jul 7 2022, 12:18 AM
This revision was automatically updated to reflect the committed changes.

If we don't support using arbitrary blockaddresses as destinations, can we stop using blockaddress to represent the destinations? The presence of blockaddress blocks optimizations even if we aren't imposing the full control flow restrictions.

Just to be clear: the original intent of the LLVM IR design here was that it would be valid to store a blockaddress into some memory, and then call that stored address inside a callbr asm. Thus the callbr asm might or might not even have _any_ blockaddress inputs itself -- that a blockaddress was an argument to the callbr had no special significance vs the blockaddress anywhere else. All possible destinations the callbr could jump to must be listed as indirect labels, however.

I do think that was a reasonable design choice to make, but we've already moved halfway away from it in a sort of ad-hoc fashion...

nikic added a comment.Jul 7 2022, 6:59 AM

If we don't support using arbitrary blockaddresses as destinations, can we stop using blockaddress to represent the destinations? The presence of blockaddress blocks optimizations even if we aren't imposing the full control flow restrictions.

Just to be clear: the original intent of the LLVM IR design here was that it would be valid to store a blockaddress into some memory, and then call that stored address inside a callbr asm. Thus the callbr asm might or might not even have _any_ blockaddress inputs itself -- that a blockaddress was an argument to the callbr had no special significance vs the blockaddress anywhere else. All possible destinations the callbr could jump to must be listed as indirect labels, however.

I do think that was a reasonable design choice to make, but we've already moved halfway away from it in a sort of ad-hoc fashion...

Yes, that was the original design, which essentially made callbr the same as indirectbr. I assume that this design was later discarded because this generality is not necessary (or particularly useful) to support asm goto. At the same time, giving callbr the same semantics as indirectbr prevents many CFG optimizations and increases the chances of miscompiles and assertion failures for any CFG transform that does not have explicit handling for callbr. It's a reasonable design in principle, but not probably not a good tradeoff for its intended use-case.

I've put up https://reviews.llvm.org/D129288 to decouple callbr representation from blockaddresses entirely (on the IR level), which should allow us to remove the remaining callbr-related special cases, and also make it clearer that callbr cannot be used with arbitrary blockaddresses.