This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] fold signed absolute diff patterns
ClosedPublic

Authored by spatel on Mar 1 2023, 8:35 AM.

Details

Summary

This overlaps partially with the codegen patch D144789. This needs nsw for correctness, and I'm not sure if there's an unsigned equivalent:
https://alive2.llvm.org/ce/z/ErmQ-9

This is obviously an improvement in IR, and it looks like a codegen win for all targets and data types that I sampled.

The 'nabs' case is not as clean because I think it would require clearing nsw from the subtract to be correct, so that's left as a potential follow-up (and seems less likely to occur in real code).

Diff Detail

Event Timeline

spatel created this revision.Mar 1 2023, 8:35 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 1 2023, 8:35 AM
spatel requested review of this revision.Mar 1 2023, 8:35 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 1 2023, 8:35 AM
goldstein.w.n added inline comments.Mar 1 2023, 9:05 AM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
970

It also works for nuw: https://alive2.llvm.org/ce/z/YfWtvG (either op can be either nsw/nuw)

spatel marked an inline comment as done.Mar 2 2023, 6:17 AM
spatel added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
970

Good point - the icmp+select filters out the poison either way. But if we match nuw, we can't propagate it:
https://alive2.llvm.org/ce/z/2b5jiJ

So if the sub has >1 use, we'll need to clear the nuw on the existing sub or create a new instruction with nsw set. I don't think it's safe to alter the flags on the existing instruction if there's more than one use.

This might overlap with changes needed to support the "nabs" pattern that I mentioned in the patch description. Ok, if we make it a TODO for this patch? I'll add more tests either way.

spatel marked an inline comment as done.Mar 2 2023, 6:29 AM
spatel added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
970

"Alter" in that sentence should have been "set". We can always clear no-wrap flags safely, but we can't set them without some context.

RKSimon added inline comments.Mar 2 2023, 7:04 AM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
970

A TODO should be fine - thanks

spatel planned changes to this revision.Mar 2 2023, 7:29 AM
spatel added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
970

On 2nd thought, this patch has a bug if the subtracts have both "nsw" and "nuw" set. So we need to do the more complicated logic in this step anyway. :)

spatel updated this revision to Diff 501869.Mar 2 2023, 7:47 AM

Patch updated:

  1. Match any pair of no-wrap subtracts.
  2. But only propagate "nsw" with restrictions.

I added tests to try to make sure we are covering all of the variations and confirmed those and several others with Alive2.

RKSimon accepted this revision.Mar 3 2023, 4:27 AM

LGTM

This revision is now accepted and ready to land.Mar 3 2023, 4:27 AM
goldstein.w.n added inline comments.Mar 3 2023, 10:02 AM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
980

Why does one-use allow it to be nsw?

spatel marked an inline comment as done.Mar 3 2023, 10:25 AM
spatel added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
980

If there's one use of the subtract (no other use than the use we are about to replace), then we know that the sub is "nsw" in this context even if it was "nuw" before:
https://alive2.llvm.org/ce/z/cmSzrG

That's what we are verifying in the abs_diff_signed_sgt_nuw test.

But if there's another use, then we can't add "nsw" to the existing instruction because it may not be safe in the other user's context:
https://alive2.llvm.org/ce/z/mio8xf

This is more complicated than the usual no-wrap propagation. I can add text like this to the code comment if this helped to explain it.

This revision was landed with ongoing or failed builds.Mar 6 2023, 10:53 AM
This revision was automatically updated to reflect the committed changes.
spatel marked an inline comment as done.