This is an archive of the discontinued LLVM Phabricator instance.

[Intrinsic] Add fixed point division intrinsics.
ClosedPublic

Authored by ebevhan on Nov 8 2019, 6:46 AM.

Details

Summary

This patch adds intrinsics and ISelDAG nodes for
signed and unsigned fixed-point division:

llvm.sdiv.fix.*
llvm.udiv.fix.*

These intrinsics perform scaled division on two
integers or vectors of integers. They are required
for the implementation of the Embedded-C fixed-point
arithmetic in Clang.

Event Timeline

ebevhan created this revision.Nov 8 2019, 6:46 AM
Herald added a project: Restricted Project. · View Herald TranscriptNov 8 2019, 6:46 AM
ebevhan marked an inline comment as done.Nov 8 2019, 7:06 AM

I will preface this by saying that I'm not terribly pleased with this solution. There is no (easy) way to construct a wide division during operation legalization if the wider type is not legal, so we have to do a whole bunch of work upfront to avoid having to expand. It feels really hacky, but I'm not sure there's any other way of doing it given ISelDAG's design.

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
7143–7145

I'm unsure if this is acceptable. I wanted to align the default expansions of division, multiplication, and shifts, but correcting for rounding requires extra code since regular signed division rounds toward zero.

ebevhan updated this revision to Diff 229100.Nov 13 2019, 7:51 AM

Updated langref.

ilya added a subscriber: ilya.Nov 26 2019, 8:54 AM
Ka-Ka added a subscriber: Ka-Ka.Nov 26 2019, 11:23 AM

Sorry for the holdup. Right now I'm just writing a bunch of tests to validate the IR expansion produces the correct division results. As of now, the patch LGTM, but I'd prefer holding off submitting the revision until I finish validating (unless you think it's better to submit now then fix any potential bugs that may be found later since I don't think anyone will be immediately using this). Here's a few comments I have so far:

  • This will need another rebase. I ran into a merge conflict this morning against ToT.
  • I think @llvm.sdiv.fix.i4(i4 -2, i4 2, i32 0) produces the incorrect result. This returns -2 instead of -1. I'm looking over the patch to see what could've caused it, but you might be able to find it faster than I can.
leonardchan added inline comments.Dec 4 2019, 2:08 PM
llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
7164

Ah, I think you want this to instead be ISD::SETNE and RemNonZero

leonardchan added inline comments.Dec 4 2019, 4:48 PM
llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
7168–7170

There's a corner case here where there won't be a subtraction if the true value of a division is between -1 and 0. For -6 / 7, the remainder will be non-zero, but quotient will be zero since sdiv rounds towards zero.

I think you need to instead check if only one of the signs of either operand is negative to check if the quotient is negative:

SDValue LHSNeg = DAG.getSetCC(dl, BoolVT, LHS, Zero, ISD::SETLT);
SDValue RHSNeg = DAG.getSetCC(dl, BoolVT, RHS, Zero, ISD::SETLT);
SDValue QuotNeg = DAG.getNode(ISD::XOR, dl, BoolVT, LHSNeg, RHSNeg);
ebevhan added inline comments.Dec 6 2019, 12:54 AM
llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
7164

Oh, you're right. Really surprised I didn't catch this in my testing.

7168–7170

Yep, I see what you mean.

ebevhan added inline comments.Dec 6 2019, 1:09 AM
llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
7168–7170

Though, would it also work to check if the Remainder is negative instead of nonzero?

Alrighty, it looks like everything in this patch should be ok after those 2 changes. I can send you the script I used to generate tests if you'd like to use it also.

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
7168–7170

Hmm I don't think that would work since srem of 2 negative numbers would return a negative number: srem -7, -3 == -1

ebevhan updated this revision to Diff 232800.Dec 9 2019, 3:30 AM

Fix review comments.

ebevhan marked an inline comment as done.Dec 9 2019, 3:32 AM

I think I'd like someone who has more specialized SelectionDAG knowledge to come with some input as well, but it doesn't seem like anyone else is looking at the patch.

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp
7168–7170

Ah, that's true.

Maybe @craig.topper has some input on this design.

craig.topper accepted this revision.Dec 10 2019, 2:07 PM

I don't really like the code In SelectionDAGBuilder, but I don't have a better solution either. So LGTM.

This revision is now accepted and ready to land.Dec 10 2019, 2:07 PM

I've been holding off on this for a while because the design made implementing saturated division a lot more complicated than it ought to be.

I'm very tempted to just scrap the promotion and expansion of the node altogether, determine if the node is legal (or easily promotable) directly in SelectionDAGBuilder and if it is not, expand it straight away. That's also a hack, but saves a ton of headache in the later stages, especially for the saturating operation.

It's either that or a libcall, but I really don't feel like that should be necessary; it should absolutely be possible to do this without one.

ebevhan updated this revision to Diff 236802.Jan 8 2020, 5:55 AM

Rebased.

uabelho added a subscriber: uabelho.Jan 8 2020, 6:14 AM

I'll submit this for @ebevhan in a little bit.

This revision was automatically updated to reflect the committed changes.