Page MenuHomePhabricator

[Fixed Point Arithmetic] Fixed Point Comparisons
ClosedPublic

Authored by leonardchan on Jan 24 2019, 9:34 PM.

Details

Summary

This patch implements fixed point comparisons with other fixed point types and integers. This also provides constant expression evaluation for them.

Diff Detail

Repository
rC Clang

Event Timeline

ebevhan added inline comments.Jan 25 2019, 1:51 AM
clang/lib/CodeGen/CGExprScalar.cpp
141 ↗(On Diff #183480)

Can't it just be LHSType->isFixedPointType() || RHSType->isFixedPointType()?

I don't think there are cases where one is a fixed-point type and the other is not an integer or another fixed-point type, so if one is fixed-point then you already know it's a fixed-point operation.

clang/test/Frontend/fixed_point_comparisons.c
56 ↗(On Diff #183480)

Missing saturating and saturating/non-saturating comparisons. I'd like to see the differences between unsigned padding and not there, if there are any.

leonardchan marked 4 inline comments as done.
leonardchan added inline comments.
clang/lib/CodeGen/CGExprScalar.cpp
141 ↗(On Diff #183480)

Ah you're right.

clang/test/Frontend/fixed_point_comparisons.c
56 ↗(On Diff #183480)

I don't think there should be since we compare by converting to a common type that should fit both operands, but it does help to have tests that also confirm this. Added some saturation cases under TestSaturationComparisons.

As for padding, TestSaturationComparisons have cases comparing signed with unsigned types, and there are other cases in TestComparisons and TestIntComparisons that deal with unsigned comparisons. The way the lit tests are organized, lines marked with CHECK mean that those lines are produced for both the padding and no padding cases whereas SIGNED or UNSIGNED are produced exclusively for no padding and padding cases, respectively.

ebevhan added inline comments.Jan 28 2019, 12:14 AM
clang/test/Frontend/fixed_point_comparisons.c
56 ↗(On Diff #183480)

There is a difference between saturating signed types and saturating unsigned types, though; the common type of two of the same saturating unsigned type is one bit less due to padding.

Unless there is something in the type commoning that I've missed?

leonardchan marked 2 inline comments as done.
leonardchan added inline comments.Jan 28 2019, 4:20 PM
clang/test/Frontend/fixed_point_comparisons.c
56 ↗(On Diff #183480)

You're right. It's just that when comparing values, we care about padding and not saturation since we aren't "writing" a value, so a comparison between a _Sat short _Accum and _Sat unsigned short _Accum should be the same as one for a short _Accum and unsigned short _Accum. With unsigned padding, both operations should not result in any resizing/scaling since they're already the same size and scale.

Added a test case for this under TestSaturationComparisons.

bjope added inline comments.Jan 30 2019, 12:16 AM
clang/test/Frontend/fixed_point_comparisons.c
2 ↗(On Diff #183980)

I think it is easier to understand the checks if you for example use UNPADDED/PADDED (or STUDDED/PADDED or something like that) instead of SIGNED/UNSIGNED.

rjmccall added inline comments.Jan 31 2019, 1:53 PM
clang/lib/CodeGen/CGExprScalar.cpp
3444 ↗(On Diff #183980)

Are padding bits guaranteed zero or unspecified? Or are we just not really supporting padding bits all the way to IRGen at this time?

leonardchan marked 3 inline comments as done.
leonardchan added inline comments.
clang/lib/CodeGen/CGExprScalar.cpp
3444 ↗(On Diff #183980)

I believe the consensus was leaving them unspecified, so operations that can cause overflow into them would result in undefined behavior.

rjmccall added inline comments.Jan 31 2019, 3:53 PM
clang/lib/CodeGen/CGExprScalar.cpp
3444 ↗(On Diff #183980)

If I'm understanding you correctly, you're saying that (1) we are assuming that inputs are zero-padded and (2) we are taking advantage of the non-saturating-overflow-is-UB rule to avoid clearing the padding bits after arithmetic. That's actually what I meant by "guaranteed zero", so we have our labels reversed, but at least we understand each other now.

(I suppose you're thinking of this as "unspecified" because non-saturating arithmetic can leave an unspecified value there. I think of this as a "guarantee" because it's basically a representational invariant: it's a precondition for correctness that the bit is zero, and all operations guarantee that the bit will be zero in their well-defined cases (but overflow is not well-defined). Just a difference in perspective, I guess.)

Is this written down somewhere? Are there targets that use the opposite ABI rule that we might need to support someday?

At any rate, I think it's worth adding a short comment here explaining why it's okay to do a normal comparison despite the possibility of padding bits. Along those lines, is there any value in communicating to the backend that padded-unsigned comparisons could reasonably be done with either a signed or unsigned comparison? Are there interesting targets where one or the other is cheaper?

leonardchan marked an inline comment as done.
leonardchan added inline comments.
clang/lib/CodeGen/CGExprScalar.cpp
3444 ↗(On Diff #183980)

Yes. We assume inputs are zero padded, and that non-saturating overflow is undefined so we do not need to clear the padding after writing a new value. Sorry for the misunderstanding. I see what you mean by guaranteed zero.

Overflow in general is controlled by the FX_FRACT_OVERFLOW and FX_ACCUM_OVERFLOW pragmas, where if these are set to DEFAULT, operations that can overflow with these types is undefined according to the standard (4.1.3). In terms of padding bits, clause 6.2.6.3 mentions that the values of padding bits are "unspecified". I imagine this means that we can assume the value to be whatever we want it to, so we can assume that these values are a guaranteed zero.

I believe @ebevhan requested this being added since his downstream implementation used padding to match the scales of signed and unsigned types, so he may be able to offer more information on targets with different ABIs. We don't plan to use any special hardware, so we're following the "typical desktop processor" layout that uses the whole underlying int and no padding (mentioned in Annex 3).

In the same section, the standard also mentions types for other targets that may have padding, so there could be some value in indicating to the backend that for these particular targets, this part of the operand is padding, so select an appropriate operation that performs a comparison on this size type. But I don't know much about these processors and would just be guessing at how they work.

rjmccall added inline comments.Feb 4 2019, 2:31 PM
clang/lib/CodeGen/CGExprScalar.cpp
3444 ↗(On Diff #183980)

Okay. If we ever have a target that uses an ABI that (1) includes padding but (2) considers it to be "unspecified" in the sense of "it can validly be non-zero", we'll have to change this code, but I agree it's the right move to not preemptively generalize to cover that possibility.

ebevhan added inline comments.Feb 7 2019, 2:21 AM
clang/lib/CodeGen/CGExprScalar.cpp
3444 ↗(On Diff #183980)

Is this written down somewhere? Are there targets that use the opposite ABI rule that we might need to support someday?

What exactly do you mean by 'opposite'? That the padding is cleared after every operation?

It was (and still is) the case in our downstream implementation that all unsigned operations explicitly clear the padding bit after every operation, leading to defined behavior on overflow for such types.

3444 ↗(On Diff #183980)

To clarify on our use case, we have the padding on the unsigned types mostly to harmonize the behavior of unsigned and signed types. The only real native support is for signed types, but if the unsigned types are padded and then use signed operations to implement them, you get (almost) the same level of performance out of unsigned ones.

The primary difference between the upstream CG and our implementation is that the padding bit is always set to zero after operations. This means that overflow on the unsigned types is essentially defined as modulo wraparound instead of UB, and unsigned types will always contain a valid value.

ebevhan added inline comments.Feb 7 2019, 4:17 AM
clang/lib/CodeGen/CGExprScalar.cpp
3444 ↗(On Diff #183980)

Oops, did not mean to submit that comment further up. Was left over from an earlier session.

rjmccall added inline comments.Feb 7 2019, 8:51 AM
clang/lib/CodeGen/CGExprScalar.cpp
3444 ↗(On Diff #183980)

That's still effectively the same ABI, just (as you say) intentionally defining the result of non-saturating overflow. I assume you haven't completely eliminated UB and that you still consider an unsigned value with 1 in the padding bit (which you never produce from arithmetic, but which could be produced by e.g. memcpy) to be an illegal representation. What I mean by "opposite" would be an ABI in which that was *not* an illegal representation, and which instead defined the padding bit to be ignored. That ABI would require IRGen to clear the bit before making these comparisons.

*ping* @bevinh @rjmccall @bjope Any other comments on this patch?

rjmccall accepted this revision.Feb 21 2019, 12:08 PM

No, this LGTM.

This revision is now accepted and ready to land.Feb 21 2019, 12:08 PM
This revision was automatically updated to reflect the committed changes.