This is an archive of the discontinued LLVM Phabricator instance.

[LICM] Reassociate & hoist sub expressions
ClosedPublic

Authored by mkazantsev on Apr 11 2023, 2:28 AM.

Details

Summary

LICM could reassociate mixed variant/invariant comparison/arithmetic operations
and hoist invariant parts out of loop if it can prove that they can be computed
without overflow. Motivating example here:

INV1 - VAR1 < INV2

can be turned into

VAR > INV1 - INV2

if we can prove no-signed-overflow here. Then INV1 - INV2 can be computed
out of loop, so we save one arithmetic operation in-loop.

I tried to make it as general as possible in this patch. For some reason it only
works when no-overflow facts are known from non-contextual facts, but this
is maybe a limitation of SCEV. It can be a subject of further improvement in
SCEV.

Diff Detail

Event Timeline

mkazantsev created this revision.Apr 11 2023, 2:28 AM
mkazantsev requested review of this revision.Apr 11 2023, 2:28 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 11 2023, 2:28 AM
nikic added a comment.Apr 11 2023, 2:32 AM

I'll check, but I'm pretty sure LICM shouldn't use SCEV because it is part of LPM1, not LPM2.

nikic added a comment.Apr 11 2023, 2:33 AM

Could you please rebase this patch to current main?

mkazantsev planned changes to this revision.Apr 11 2023, 2:34 AM
mkazantsev added a reviewer: aleksandr.popov.

planned rebase

Wow, I'm so lucky to make this change in this exact place in this exact moment :)

mkazantsev added inline comments.Apr 11 2023, 2:54 AM
llvm/lib/Transforms/Scalar/LICM.cpp
2582

Should have used eraseInstruction

anna added inline comments.Apr 24 2023, 2:09 PM
llvm/lib/Transforms/Scalar/LICM.cpp
2601

This gets confusing enough to read for me .. will take a while to parse this :)

Can I suggest to start with the minimal pattern you wanted to support? I see you have couple of swaps earlier as well to handle all general forms.

mkazantsev planned changes to this revision.Apr 25 2023, 12:52 AM

@anna I have split off the minimul piece of functionality as D149132. Will rebase this one now.

Rebased on top of split off piece. I also tried to simplify the explanation and math formulae.

mkazantsev retitled this revision from [LICM] Reassociate & hoist add/sub expressions to [LICM] Reassociate & hoist sub expressions.Apr 25 2023, 1:40 AM
mkazantsev marked an inline comment as done.Apr 25 2023, 1:52 AM
mkazantsev added inline comments.
llvm/lib/Transforms/Scalar/LICM.cpp
2601

I tried to do it more reader-friendly. :)

mkazantsev marked an inline comment as done.Apr 25 2023, 2:22 AM

General question: don't you want to separate sub and add handling in completely different functions.
To be honest, there will be small code duplication but in this case no need to mixup add and sub logic.
It will be easier to review and support in the future.

If duplication is a problem you can create functions for sub and add to keep first and last lines are in common.

anna added a comment.Apr 25 2023, 9:19 AM

General question: don't you want to separate sub and add handling in completely different functions.
To be honest, there will be small code duplication but in this case no need to mixup add and sub logic.
It will be easier to review and support in the future.

If duplication is a problem you can create functions for sub and add to keep first and last lines are in common.

Strongly agree with this :)

General question: don't you want to separate sub and add handling in completely different functions.
To be honest, there will be small code duplication but in this case no need to mixup add and sub logic.
It will be easier to review and support in the future.

If duplication is a problem you can create functions for sub and add to keep first and last lines are in common.

But code for sub is exactly same as the code that handles both add and sub, with 2 lines of difference.

mkazantsev planned changes to this revision.Apr 25 2023, 11:55 PM

This will require rebase.

General question: don't you want to separate sub and add handling in completely different functions.
To be honest, there will be small code duplication but in this case no need to mixup add and sub logic.
It will be easier to review and support in the future.

If duplication is a problem you can create functions for sub and add to keep first and last lines are in common.

But code for sub is exactly same as the code that handles both add and sub, with 2 lines of difference.

ok, will review after rebase.

mkazantsev updated this revision to Diff 518657.May 2 2023, 2:19 AM

Rebased & split off sub code from add as Serguei and Anna have proposed.

mkazantsev planned changes to this revision.May 2 2023, 2:40 AM

Rolling back to SCEV version.

mkazantsev requested review of this revision.May 2 2023, 4:59 AM

Bringing SCEV to LICM brings potential correctness issues. I'll rather try to support this in value tracking.

skatkov accepted this revision.May 28 2023, 9:19 PM

LGTM with comment for consideration - I do not insist.

llvm/lib/Transforms/Scalar/LICM.cpp
2581

Not sure it is more readable (may be only for me) but consider

// C1 - LV < C2 case, so we need C1 - C2 does not overflow.
if (VariantSubtracted && computeOverflowForSignedSub(InvariantOp, InvariantRHS, DL, AC,
                                         &ICmp, DT) != llvm::OverflowResult::NeverOverflows)
  return false;
// LV - C1 < C2 case, so we need C1 + C2 does not overflow.
if (!ValueSubrtacted && computeOverflowForSignedAdd(InvariantOp, InvariantRHS, DL, AC,
                                         &ICmp, DT) != llvm::OverflowResult::NeverOverflows)
  return false;
This revision is now accepted and ready to land.May 28 2023, 9:19 PM
This revision was landed with ongoing or failed builds.May 28 2023, 10:53 PM
This revision was automatically updated to reflect the committed changes.