Page MenuHomePhabricator

[DSE] Fall back to CFG scan for unreachable terminators.
ClosedPublic

Authored by fhahn on Feb 14 2022, 11:57 AM.

Details

Summary

Blocks with UnreachableInst terminators are considered as root nodes in
the PDT. This pessimize DSE, if there are no aliasing reads from the
potentially dead store and the block with the unreachable terminator.

If the PDT has a virtual root node and any of the root nodes has
UnreachableInst as terminator, fall back to the CFG scan, even the
common dominator of all killing blocks does not post-dominate the block
with potentially dead store.

It looks like the compile-time impact for the extra scans is negligible.
https://llvm-compile-time-tracker.com/compare.php?from=779bbbf27fe631154bdfaac7a443f198d4654688&to=ac59945f1bec1c6a7d7f5590c8c69fd9c5369c53&stat=instructions

Fixes #53800.

Diff Detail

Event Timeline

fhahn created this revision.Feb 14 2022, 11:57 AM
fhahn requested review of this revision.Feb 14 2022, 11:57 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 14 2022, 11:57 AM

I'm not convinced this is right... what happens if you replace "exit" with something that throws an exception, or calls longjmp, or has an infinite loop? I'm not seeing any logic in this patch that actually reasons about the contents of the block that ends in "unreachable".

fhahn added a comment.Feb 14 2022, 1:46 PM

I'm not convinced this is right... what happens if you replace "exit" with something that throws an exception, or calls longjmp, or has an infinite loop? I'm not seeing any logic in this patch that actually reasons about the contents of the block that ends in "unreachable".

I think this part of the code should only be responsible for checking that the killed store is not visible after the function returns (= only done for objects visible to the caller around like 1496).

If there are any reads or throwing calls, those should be handled during the mem-ssa traversal earlier. If there's an infinite loop or a function that does not return, I don't think this would cause an issue, because we only need to check if there's a path to an exit that returns to the caller via a regular return. I'm not sure how the longjump case would be modeled exactly, but I think this would also need to be handled by the earlier checks before we reach this code.

There are a couple of extra tests (@unreachable_exit_with_may_unwind_call, @unreachable_exit_and_call_may_read) that should test some of the scenarios you mentioned.

As long as you've thought about it, I guess...

I'm a little confused by the different traversals, though. Have you considered just treating "ret" as reading memory, instead of analyzing "ret" using a different codepath from unwinding?

nikic added a comment.Feb 15 2022, 4:07 AM
llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
813

The first check here looks redundant. Doesn't PDT always have virtual root?

fhahn updated this revision to Diff 408998.Feb 15 2022, 12:08 PM
fhahn marked an inline comment as done.

Done,thanks!

As long as you've thought about it, I guess...

I'm a little confused by the different traversals, though. Have you considered just treating "ret" as reading memory, instead of analyzing "ret" using a different codepath from unwinding?

Initially one approach was to model reads at function exits through a special intrinsic (D73763), but in the end we went with the current approach of the extra checks.

I put up a new patch that introduces dummy loads just before exits to see how it would look in terms of compile-time, and it looks mostly neutral, with slightly more stores removed: D119879. One concern with the original patch was the use of a new intrinsic. This patch just adds dummy loads, not sure if there's a better way.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
813

It's not needed! Removed.

nikic added inline comments.Feb 15 2022, 12:31 PM
llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
1522–1529

Should be sufficient to only change this branch?

if (!PDT.dominates(CommonPred, MaybeDeadAccess->getBlock())) {
  // Comment
  if (!AnyUnreachableExit)
    return None;
  CommonPred = nullptr;
}
fhahn updated this revision to Diff 409216.Feb 16 2022, 5:17 AM

Removed unneeded branch as suggested, thanks!

fhahn marked an inline comment as done.Feb 16 2022, 5:18 AM
fhahn added inline comments.
llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
1522–1529

Good point, updated as suggested, thanks!

nikic accepted this revision.Feb 16 2022, 5:26 AM

LGTM

This revision is now accepted and ready to land.Feb 16 2022, 5:26 AM
This revision was landed with ongoing or failed builds.Feb 16 2022, 6:07 AM
This revision was automatically updated to reflect the committed changes.
fhahn marked an inline comment as done.