This is an archive of the discontinued LLVM Phabricator instance.

[DAG] Fold (shl (sext (add_nsw x, c1)), c2) -> (add (shl (sext x), c2), c1 << c2)
ClosedPublic

Authored by RKSimon on Aug 30 2023, 6:30 AM.

Details

Summary

Assuming the ADD is nsw then it may be sign-extended to merge with a SHL op in a similar fold to the existing (shl (add x, c1), c2) -> (add (shl x, c2), c1 << c2) fold.

This is most useful for helping to expose address math for X86, but has also touched several aarch64 test cases as well - I think they are benign but would like some confirmation.

@craig.topper RISCV uses isDesirableToCommuteWithShift to prevent creating shifted adds with larger offsets - should this be extended to peek through ext nodes as well? If so I'll need to add suitable test coverage. IIRC there's implicit extension on RISCV targets that I'm not very familiar with.

Alive2: https://alive2.llvm.org/ce/z/2UpSbJ

Diff Detail

Event Timeline

RKSimon created this revision.Aug 30 2023, 6:30 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 30 2023, 6:30 AM
RKSimon requested review of this revision.Aug 30 2023, 6:30 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 30 2023, 6:30 AM
Herald added a subscriber: wangpc. · View Herald Transcript
RKSimon edited the summary of this revision. (Show Details)Aug 30 2023, 2:10 PM

The Arm parts seem OK to me

Missing a test with nuw + zext and negative tests (maybe missing flag or nsw + zext / nuw + sext).

pengfei added inline comments.Aug 30 2023, 7:02 PM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
10012–10013

Do we need to consider the possibility of overflow when c1 << c2?

goldstein.w.n added inline comments.Aug 30 2023, 7:27 PM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
10012–10013

Shouldnt need to, the proof stands even with

pengfei added inline comments.Aug 30 2023, 10:04 PM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
10012–10013

I'm not sure about the zext one if we always put c1 << c2 in the displacement. The displacement can only be signed int.

RKSimon planned changes to this revision.Aug 31 2023, 1:44 AM

OK, I'll just go with sext/nsw for now - I'll add some explicit negative tests, although there are plenty of existing test cases that implicity do this for us already.

goldstein.w.n added inline comments.Aug 31 2023, 3:09 AM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
10012–10013

Oh that's a good point

RKSimon updated this revision to Diff 554976.Aug 31 2023, 4:20 AM
RKSimon retitled this revision from [DAG] Fold (shl (ext (add x, c1)), c2) -> (add (shl (ext x), c2), c1 << c2) to [DAG] Fold (shl (sext (add_nsw x, c1)), c2) -> (add (shl (sext x), c2), c1 << c2).
RKSimon edited the summary of this revision. (Show Details)

rebase - limit to sext/add_nsw - added negative tests

rebase - limit to sext/add_nsw - added negative tests

Can you make the tests related?

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
10013

Add TODO for zext if nuw + c1 << c2 stays imm32? (or more conservatively same int width class).

rebase - limit to sext/add_nsw - added negative tests

Can you make the tests related?

I'm sorry, please can you explain what you mean by this?

rebase - limit to sext/add_nsw - added negative tests

Can you make the tests related?

I'm sorry, please can you explain what you mean by this?

Make them related revisions? Or have you already pushed.

Any further comments - does any of the RISCV gurus have any thoughts on whether isDesirableToCommuteWithShift needs adjusting?

goldstein.w.n accepted this revision.Sep 1 2023, 11:45 AM

Any further comments - does any of the RISCV gurus have any thoughts on whether isDesirableToCommuteWithShift needs adjusting?

X86 aspect LGTM.

This revision is now accepted and ready to land.Sep 1 2023, 11:45 AM

Cheers - I'll push this in a couple of days as long as there's no objections from RISCV @craig.topper?

This revision was landed with ongoing or failed builds.Sep 6 2023, 2:07 AM
This revision was automatically updated to reflect the committed changes.

Sorry, this change breaks llvm-project/llvm/test/Transforms/InferAddressSpaces/AMDGPU/flat_atomic.ll:

https://lab.llvm.org/buildbot/#/builders/249/builds/9078

I will revert this patch to unbreak the tests at HEAD.