This is an archive of the discontinued LLVM Phabricator instance.

[RISCV] Lower more BUILD_VECTOR sequences to RVV's VID
ClosedPublic

Authored by frasercrmck on Jun 25 2021, 8:02 AM.

Details

Summary

This relands a6ca88e908b5befcd9b0f8c8cb40f53095cc17bc which was originally
reverted due to overflow bugs in e3fa2b1eab60342dc882b7b888658b03c472fa2b.

This patch teaches the compiler to identify a wider variety of
BUILD_VECTORs which form integer arithmetic sequences, and to lower
them to vid.v with modifications for non-unit steps and non-zero
addends.

The sequences handled by this optimization must either be monotonically
increasing or decreasing. Consecutive elements holding the same value
indicate a fractional step which, while simple mathematically,
becomes more complex to handle both in the realm of lossy integer
division and in the presence of undefs.

For example, a common "interleaving" shuffle index will be lowered by
LLVM to both <0,u,1,u,2,...> and <u,0,u,1,u,...> BUILD_VECTOR
nodes. Either of these would ideally be lowered to vid.v shifted right
by 1. Detection of this sequence in presence of general undef values
is more complicated, however: <0,u,u,1,> could match either
<0,0,0,1,> or <0,0,1,1,> depending on later values in the sequence.
Both are possible, so backtracking or multiple passes is inevitable.

Sticking to monotonic sequences keeps the logic simpler as it can be
done in one pass. Fractional steps will likely be a separate
optimization in a future patch.

Diff Detail

Event Timeline

frasercrmck created this revision.Jun 25 2021, 8:02 AM
frasercrmck requested review of this revision.Jun 25 2021, 8:02 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 25 2021, 8:02 AM
  • space out function and change comment a bit
  • also it'll re-run the builds...
  • add missing word to comment
craig.topper added inline comments.Jun 25 2021, 12:30 PM
llvm/lib/Target/RISCV/RISCVISelLowering.cpp
1582

Isn't it simm5?

1597

Step == -1 -> negate?

llvm/test/CodeGen/RISCV/rvv/fixed-vectors-fp-shuffles.ll
179

This can I think be

vid.v v28
vrsub.vx v28, 4
frasercrmck marked an inline comment as done.
  • rebase
  • change imm6 heuristic to imm5
  • add optimization for negative steps
frasercrmck marked 2 inline comments as done.Jul 13 2021, 3:37 AM
frasercrmck added inline comments.
llvm/lib/Target/RISCV/RISCVISelLowering.cpp
1582

At least I was close! Fixed, cheers.

1597

Yep, thanks! I now catch steps where the absolute value is a power-of-two and use a reverse SUB to account. By combining it with the Addend handling we see better codegen below. Doing ISD::SUB followed ISD::ADD isn't combined for reasons explained below.

llvm/test/CodeGen/RISCV/rvv/fixed-vectors-fp-shuffles.ll
179

Yeah, thanks. I actually saw that codegen when at first I was doing scalable-vector post-VID adjustments (ISD::ADD etc.). This was wrong, however, as we dropped the fixed vector length info. When I corrected it to adjustments after converting from the scalable container type I saw worse code generation as the fixed-vector ISD nodes are immediately custom-lowered to RISCVISD counterparts without going through any DAGCombining.

This desired code generation is now "fixed" by doing "negate + addend" folding above while working on your earlier suggestion for negative steps.

I'm not a huge fan of having to do our own optimizations at this level. Perhaps if we did this BUILD_VECTOR optimization earlier in combining we'd save some bother, but we'd also have to make SHUFFLE_VECTOR happen earlier to allow its indices to go through the same process.

frasercrmck marked 2 inline comments as done.

rebase

This revision is now accepted and ready to land.Jul 15 2021, 8:39 AM
This revision was landed with ongoing or failed builds.Jul 16 2021, 2:44 AM
This revision was automatically updated to reflect the committed changes.
frasercrmck added inline comments.Jul 16 2021, 7:16 AM
llvm/lib/Target/RISCV/RISCVISelLowering.cpp
1416

This may overflow here e.g. 0 - INT64_MIN.

1434

This may also overflow

frasercrmck reopened this revision.Jul 19 2021, 3:20 AM
This revision is now accepted and ready to land.Jul 19 2021, 3:20 AM

fix overflows and element-sized arithmetic

frasercrmck edited the summary of this revision. (Show Details)Jul 19 2021, 3:21 AM
This revision was landed with ongoing or failed builds.Jul 22 2021, 1:45 AM
This revision was automatically updated to reflect the committed changes.