This is an archive of the discontinued LLVM Phabricator instance.

[SCEVExpander] Move LCSSA fixup to ::expand.
ClosedPublic

Authored by fhahn on Sep 27 2022, 7:11 AM.

Details

Summary

Move LCSSA fixup from ::expandCodeForImpl to ::expand(). This has
the advantage that we directly preserve LCSSA nodes here instead of
relying on doing so in rememberInstruction. It also ensures that we
don't add the non-LCSSA-safe value to InsertedExpressions.

Alternative to D132704.

Fixes #57000.

Diff Detail

Event Timeline

fhahn created this revision.Sep 27 2022, 7:11 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 27 2022, 7:11 AM
fhahn requested review of this revision.Sep 27 2022, 7:11 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 27 2022, 7:11 AM

Maybe we should restructure the InsertedExpressions cache so it's more likely to consistently hit?

Insertion points fall into the following categories:

  • A passed-in arbitrary point.
  • The beginning of a basic block.
  • The end of a basic block.

The values are then adjusted in some cases: if the insertion point points at an inserted instruction, we adjust forward to try to reuse those instructions.

For the "beginning of a basic block" case, it doesn't really make sense to track the exact instruction where we can actually insert instructions; all that matters is that it's the "beginning". If we fix that, it should ensure we hit the cache reliably for those cases.

Doing multiple cache lookups like the current patch may sort of work in this case, but it's not clear in general why we would expect the unadjusted insertion point to be in the cache.

fhahn updated this revision to Diff 463981.Sep 29 2022, 11:50 AM

Maybe we should restructure the InsertedExpressions cache so it's more likely to consistently hit?

Insertion points fall into the following categories:

  • A passed-in arbitrary point.
  • The beginning of a basic block.
  • The end of a basic block.

The values are then adjusted in some cases: if the insertion point points at an inserted instruction, we adjust forward to try to reuse those instructions.

For the "beginning of a basic block" case, it doesn't really make sense to track the exact instruction where we can actually insert instructions; all that matters is that it's the "beginning". If we fix that, it should ensure we hit the cache reliably for those cases.

Doing multiple cache lookups like the current patch may sort of work in this case, but it's not clear in general why we would expect the unadjusted insertion point to be in the cache.

I took another closer look at where the LCSSA phi nodes should be cached. I restructured the code to move LCSSA fixup to ::expand() from ::expandCodeForImpl. This has the advantage that we directly preserve LCSSA nodes here instead of relying on doing so in rememberInstruction. It also ensures that we don't add the non-LCSSA-safe value to InsertedExpressions.

Overall the code should be mode direct, this leads to better results in a few cases (fewer unnecessary LCSSA phis) and fixes the crash in the newly added test case.

What do you think?

LGTM with one minor comment

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
2510

"SH" is unused?

efriedma accepted this revision.Sep 29 2022, 12:00 PM
This revision is now accepted and ready to land.Sep 29 2022, 12:00 PM
fhahn retitled this revision from [SCEVExpander] Check expr is available for traversed InsterPts. to [SCEVExpander] Move LCSSA fixup to ::expand..Sep 29 2022, 12:04 PM
fhahn edited the summary of this revision. (Show Details)
fhahn updated this revision to Diff 463990.Sep 29 2022, 12:10 PM

Remove unused argument, thanks!

This revision was landed with ongoing or failed builds.Sep 29 2022, 12:50 PM
This revision was automatically updated to reflect the committed changes.
fhahn added a comment.Sep 30 2022, 1:06 AM

Thanks for the review Eli!