Page MenuHomePhabricator

[Intrinsic] Add fixed point division intrinsics.
Needs ReviewPublic

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.Wed, Nov 13, 7:51 AM

Updated langref.

ilya added a subscriber: ilya.Tue, Nov 26, 8:54 AM
Ka-Ka added a subscriber: Ka-Ka.Tue, Nov 26, 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.Wed, Dec 4, 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.Wed, Dec 4, 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.Fri, Dec 6, 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.Fri, Dec 6, 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