Page MenuHomePhabricator

[Fixed Point Arithmetic] Fixed Point Addition
ClosedPublic

Authored by leonardchan on Oct 25 2018, 4:08 PM.

Details

Summary

This patch covers addition between fixed point types and other fixed point types or integers, using the conversion rules described in 4.1.4 of N1169.

Usual arithmetic rules do not apply to binary operations when one of the operands is a fixed point type, and the result of the operation must be calculated with the full precision of the operands, so we should not perform any casting to a common type.

This patch does not include constant expression evaluation for addition of fixed point types. That will be addressed in another patch since I think this one is already big enough.

Diff Detail

Repository
rL LLVM

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes

The only thing I didn't include in this patch were the suggested changes to FixedPointSemantics which would indicate if the semantics were original from an integer type. I'm not sure how necessary this is because AFAIK the only time we would need to care if the semantics came from an int is during conversion from a fixed point type to an int, which should only occur during casting and not binary operations. In that sense, I don't think this info needs to be something bound to the semantics, but more to the conversion operation. I also don't think that would be relevant for this patch since all integers get converted to fixed point types anyway and not the other way around.

For the integer conversion though, I was going to add that in a separate fixed-point-to-int and int-to-fixed-point patch.

Okay, that's fine! You're right in that the semantics commoning will never produce an integer semantic like that.

clang/lib/Basic/FixedPoint.cpp
129 ↗(On Diff #173961)

Does this properly compensate for types of equal width but different signedness?

If you have a signed 8-bit 7-scale fixed point number, and operate with an unsigned 8-bit integer, you'll get CommonWidth=15 and CommonScale=7, leaving 8 bits of integral. But the MSB in that cannot both be sign bit and unsigned MSB at the same time. I think you need an extra bit.

135 ↗(On Diff #173961)

If one has padding but the other doesn't, then the padding must be significant, so the full precision semantic cannot have padding.

clang/lib/CodeGen/CGExprScalar.cpp
3385 ↗(On Diff #173961)

Can EmitFixedPointConversion not determine this on its own?

3387 ↗(On Diff #173961)

'align' usually means something else. Maybe 'Convert the operands to the full precision type' and 'FullLHS'?

clang/lib/Sema/SemaExpr.cpp
1306 ↗(On Diff #173961)

Does this handle compound assignment? The other functions handle this specially.

1403 ↗(On Diff #173961)

Can this commutation be folded into the function to align it with the rest?

leonardchan marked 5 inline comments as done.
leonardchan added inline comments.
clang/lib/Basic/FixedPoint.cpp
129 ↗(On Diff #173961)

Added test for this also.

clang/lib/Sema/SemaExpr.cpp
1306 ↗(On Diff #173961)

Currently no. I was initially intending to add addition compound assignment in a different patch, but do you think it would be appropriate to include it here? I imagine the changes to Sema wouldn't be difficult, but would probably require adding a lot more tests.

I'd be interested in seeing tests for two saturating unsigned _Fract with and without padding.

If the padding case emits a uadd_sat, that seems wrong; uadd_sat doesn't saturate on the padding bit, but will saturate the whole number, which can result in invalid representation both with or without saturation taking effect.

Common semantics for unsigned types with padding might need a bit of trickery to get it to do the right thing.

clang/lib/CodeGen/CGExprScalar.cpp
3383 ↗(On Diff #174080)

Missing a C there.

clang/lib/Sema/SemaExpr.cpp
1306 ↗(On Diff #173961)

That's fine by me, then. Take it in the next patch.

clang/test/Frontend/fixed_point_add.c
36 ↗(On Diff #174080)

What do these comments refer to? The scale is the same for both operands here.

leonardchan marked 13 inline comments as done.

I'd be interested in seeing tests for two saturating unsigned _Fract with and without padding.

If the padding case emits a uadd_sat, that seems wrong; uadd_sat doesn't saturate on the padding bit, but will saturate the whole number, which can result in invalid representation both with or without saturation taking effect.

Common semantics for unsigned types with padding might need a bit of trickery to get it to do the right thing.

Good case to bring up. For addition, I think we just need to add an extra condition that checks for unsigned padding in the result. Added this test also.

clang/test/Frontend/fixed_point_add.c
36 ↗(On Diff #174080)

This was meant to be a addition with a short _Accum and _Fract, but accidentally typed this instead. Added that test after this one.

Good case to bring up. For addition, I think we just need to add an extra condition that checks for unsigned padding in the result. Added this test also.

Actually this was wrong. Updated and instead dictate how the appropriate number of bits to getCommonSemantics. The saturation intrinsics handle unsigned padding types correctly now and only add the extra padding bit to the common width if both operands have unsigned padding and the result is not saturated (to prevent an unnecessary ext + trunc on non saturating operations).

ebevhan added inline comments.Nov 16 2018, 8:52 AM
clang/lib/CodeGen/CGExprScalar.cpp
3385 ↗(On Diff #173961)

What I meant here was that rather than zeroing out the saturation mode on the common semantic because we know that the common conversion won't saturate, EmitFixedPointConversion should be able to pick up on the fact that converting from semantic A to semantic B shouldn't cause saturation and not emit a saturating conversion in that case. Then you can set the saturation on the common semantic properly, since the operation should be saturating.

Even for something like sat_uf * sat_uf with padding, where the common type conversion should be (16w, 15scale, uns, sat, pad) -> (15w, 15scale, uns, sat, nopad), EmitFixedPointConversion shouldn't emit a saturation, since the number of integral bits hasn't changed.

clang/test/Frontend/fixed_point_add.c
269 ↗(On Diff #174279)

This is probably a candidate for an isel optimization. This operation also works as an i16 ssat.add with a negative-clamp-to-zero afterwards, and if the target supports i16 ssat.add natively then it will likely be a lot more efficient than whatever an i15 uadd.sat produces.

leonardchan marked an inline comment as done.
leonardchan added inline comments.
clang/test/Frontend/fixed_point_add.c
269 ↗(On Diff #174279)

Do you think it would be more efficient for now then if instead we did SHL by 1, saturate, then [AL]SHR by 1? This way we could use i16 ssat.add instead of i15 ssat.add?

@ebevhan Any more comments on this patch?

@ebevhan Any more comments on this patch?

It's strange, I feel like I've responded to the last comment twice now but there's nothing in Phab.

Generally I think it's good! One final note; I assume we could technically reuse/rename the EmitFixedPointAdd function and use it to emit other binops when those are added?

clang/test/Frontend/fixed_point_add.c
269 ↗(On Diff #174279)

We should probably just do it in isel or instcombine instead. We don't know at this point which intrinsic is a better choice (though, I think power-of-two-types are generally better).

leonardchan marked an inline comment as done.Nov 26 2018, 10:38 AM

Generally I think it's good! One final note; I assume we could technically reuse/rename the EmitFixedPointAdd function and use it to emit other binops when those are added?

Yes, but I imagine if we choose to keep the call to EmitFixedPointConversion to cast both operands to a common type, this wouldn't be reused for division or multiplication since I believe those do not require for the operands to be converted to a common type.

clang/test/Frontend/fixed_point_add.c
269 ↗(On Diff #174279)

Ok. Are you suggesting something should be changed here though? I imagine that during legalization, i15 ssat.add would be legalized into i16 ssat.add if that is what's natively supported.

Generally I think it's good! One final note; I assume we could technically reuse/rename the EmitFixedPointAdd function and use it to emit other binops when those are added?

Yes, but I imagine if we choose to keep the call to EmitFixedPointConversion to cast both operands to a common type, this wouldn't be reused for division or multiplication since I believe those do not require for the operands to be converted to a common type.

They don't? The example given by the spec is even int * _Fract.

clang/test/Frontend/fixed_point_add.c
269 ↗(On Diff #174279)

No, it doesn't have to be changed. Just something to keep in mind.

i15 ssat.add would be legalized into i16 ssat.add if that is what's natively supported.

Sure, but I meant that i15 usat.add could be more efficient as i16 ssat.add.

leonardchan marked an inline comment as done.Nov 27 2018, 11:33 AM

Generally I think it's good! One final note; I assume we could technically reuse/rename the EmitFixedPointAdd function and use it to emit other binops when those are added?

Yes, but I imagine if we choose to keep the call to EmitFixedPointConversion to cast both operands to a common type, this wouldn't be reused for division or multiplication since I believe those do not require for the operands to be converted to a common type.

They don't? The example given by the spec is even int * _Fract.

Oh, I meant that the scales of both operands won't need to be aligned before performing the operation. Since for multiplication, we can multiply fixed point numbers in any scale without shifting and only need to perform a shift on the result to convert to the destination type. Although this would only apply to non-saturating multiplication since to use the intrinsics, both operands would need to be in the same scale.

@rjmccall Any more comments on this patch?

clang/test/Frontend/fixed_point_add.c
269 ↗(On Diff #174279)

Got it. Thanks!

Generally I think it's good! One final note; I assume we could technically reuse/rename the EmitFixedPointAdd function and use it to emit other binops when those are added?

Yes, but I imagine if we choose to keep the call to EmitFixedPointConversion to cast both operands to a common type, this wouldn't be reused for division or multiplication since I believe those do not require for the operands to be converted to a common type.

They don't? The example given by the spec is even int * _Fract.

Oh, I meant that the scales of both operands won't need to be aligned before performing the operation. Since for multiplication, we can multiply fixed point numbers in any scale without shifting and only need to perform a shift on the result to convert to the destination type. Although this would only apply to non-saturating multiplication since to use the intrinsics, both operands would need to be in the same scale.

I see what you mean, but the fixed-point multiplication intrinsic requires the operands to be in the same scale.

It's certainly interesting to degenerate integer-with-fixedpoint to just a mul (since the scaling factor is 2^-n * 2^0, which is just 2^-n), but in the general case you can't avoid doing the scale alignment. Unless I'm missing something.

It's certainly interesting to degenerate integer-with-fixedpoint to just a mul (since the scaling factor is 2^-n * 2^0, which is just 2^-n), but in the general case you can't avoid doing the scale alignment. Unless I'm missing something.

No you're right. Sorry, for some reason I kept only thinking about the saturation fixed point intrinsics and not the regular fixed point ones.

@rjmccall Any more comments on this patch? As soon as I get LGTM, I can reuse the functions here for subtraction and use the updated UsualArithmeticConversions for casing between fixed point types in other patches.

rjmccall added inline comments.Nov 29 2018, 10:28 AM
clang/include/clang/AST/ASTContext.h
2638 ↗(On Diff #174640)

Please include in the comment here that, unlike getCorrespondingUnsignedType, this has to be specific to fixed-point types because there are unsigned integer types like bool and char8_t that don't have signed equivalents.

clang/include/clang/Basic/FixedPoint.h
41 ↗(On Diff #174640)

assert(!(IsSigned && HasUnsignedPadding) && ...);, please.

67 ↗(On Diff #174640)

Actually representing the fully-precise value is operation-specific; you'd need a different calculation for at least addition and multiplication, and maybe also subtraction and (maybe?) division. Is this what you actually want?

70 ↗(On Diff #174640)

This is trivial enough that it should probably be implemented inline.

clang/lib/AST/ASTContext.cpp
10489 ↗(On Diff #174640)

Does getIntWidth do the thing you want for bool?

clang/lib/Basic/FixedPoint.cpp
141 ↗(On Diff #174640)

Is this right? If I have a+b+c+d+e+f+g+h+i, where those are all the same signed type, won't the width of the common semantics keep growing as I add more operands?

leonardchan marked 14 inline comments as done.
leonardchan added inline comments.
clang/include/clang/Basic/FixedPoint.h
67 ↗(On Diff #174640)

For addition and subtraction, I believe we just need to extend and shift to a type that is large enough to hold the larger scale and integral bits, then we can do a normal add/sub. I think the relational operations can use this also since we would just need to resize and align scales for them.

For multiplication, the intrinsics we will use also assume the scale for both operands are the same, which I believe will also require finding semantics large enough to hold the larger scale and integral bits.

declare iN @llvm.smul.fix(iN %L, %iN R, i32 %Scale)

Division is similar since the saturating and non-saturating intrinsics assume both operands have the same scale.

declare iN @llvm.sdiv.fix(iN %L, %iN R, i32 %Scale)

In each of these cases, I believe the common semantics just needs to be large enough to hold the scale and largest representable value, which is what this method does.

clang/lib/AST/ASTContext.cpp
10489 ↗(On Diff #174640)

I think so. The resulting semantics for this should be unsigned with a width of 1. I believe a _Bool currently never gets passed to this since UsualUnaryConversions casts a _Bool into an int.

Currently adding a fixed point type with a bool is treated the same as adding with an int. Added a test for this also.

clang/lib/Basic/FixedPoint.cpp
141 ↗(On Diff #174640)

This should be right. Each addition is split into separate binary operations which produce separate common fixed point semantics from 2 different semantics. The width is also primarily made from the larger scale and large number of integral bits (which excludes the sign or unsigned padding).

For example:

a+b -> Width: 32 (scale 14 + integral bits 16 + sign bit 1)
(a+b)+c -> Width: 32 ^^^^^
((a+b)+c)+d -> Width: 32 ^^^^^

Added a test for this.

rjmccall added inline comments.Nov 29 2018, 7:11 PM
clang/include/clang/Basic/FixedPoint.h
67 ↗(On Diff #174640)

Okay, so I believe what you're saying is that getCommonSemantics is defined as returning a semantics that is capable of precisely representing both input values, not one that's capable of precisely representing the result of the computation. The documentation could be clearer about that.

clang/lib/Basic/FixedPoint.cpp
141 ↗(On Diff #174640)

I see. If that's done consistently then it's fine that it technically slightly misrepresents the range of negative values.

clang/lib/CodeGen/CGExprScalar.cpp
3370 ↗(On Diff #175965)

Please use cast.

clang/lib/Sema/SemaExpr.cpp
1237 ↗(On Diff #175965)

Please optimize this function around expecting a BuiltinType. That is, instead of separately checking for an integer type here, please assert it when (1) the getAs fails or (2) you fall into the default case.

1304 ↗(On Diff #175965)

Hmm. So adding a signed integer to an unsigned fixed-point type always converts the integer to unsigned? That's a little weird, but only because the fixed-point rule seems to be the other way. Anyway, I assume it's not a bug in the spec.

ebevhan added inline comments.Nov 30 2018, 12:37 AM
clang/lib/Sema/SemaExpr.cpp
1304 ↗(On Diff #175965)

handleFixedPointConversion only calculates the result type of the expression, not the calculation type. The final result type of the operation will be the unsigned fixed-point type, but the calculation itself will be done in a signed type with enough precision to represent both the signed integer and the unsigned fixed-point type.

Though, if the result ends up being negative, the final result is undefined unless the type is saturating. I don't think there is a test for the saturating case (signed integer + unsigned saturating fixed-point) in the SaturatedAddition tests.

rjmccall added inline comments.Nov 30 2018, 8:44 AM
clang/lib/Sema/SemaExpr.cpp
1304 ↗(On Diff #175965)

handleFixedPointConversion only calculates the result type of the expression, not the calculation type.

Right, I understand that, but the result type of the expression obviously impacts the expressive range of the result, since you can end up with a negative value.

Hmm. With that said, if the general principle is to perform the operation with full precision on the original operand values, why are unsigned fixed-point operands coerced to their corresponding signed types *before* the operation? This is precision-limiting if the unsigned representation doesn't use a padding bit. That seems like a bug in the spec.

leonardchan marked 6 inline comments as done.
leonardchan added inline comments.
clang/include/clang/Basic/FixedPoint.h
67 ↗(On Diff #174640)

Yup. Updated the documentation.

clang/lib/Sema/SemaExpr.cpp
1304 ↗(On Diff #175965)

Hmm. With that said, if the general principle is to perform the operation with full precision on the original operand values, why are unsigned fixed-point operands coerced to their corresponding signed types *before* the operation? This is precision-limiting if the unsigned representation doesn't use a padding bit. That seems like a bug in the spec.

Possibly. When the standard mentions converting from signed to unsigned fixed point, the only requirement involved is conservation of magnitude (the number of integral bits excluding the sign)

when signed and unsigned fixed-point types are mixed, the unsigned type is converted to the corresponding signed type, and this should go without loss of magnitude

This is just speculation, but I'm under the impression that not as much "attention" was given for unsigned types as for signed types since "In the embedded processor world, support for unsigned fixed-point data types is rare; normally only signed fixed-point data types are supported", but was kept anyway since unsigned types are used a lot.

However, to disallow unsigned fixed-point arithmetic from programming languages (in general, and from C in particular) based on this observation, seems overly restrictive.

I also imagine that if the programmer needs more precision, the correct approach would be to cast up to a type with a higher scale. The standard seems to make an effort to expose as much in regards to the underlying fixed point types as possible:

it should be possible to write fixed-point algorithms that are independent of the actual fixed-point hardware support. This implies that a programmer (or a running program) should have access to all parameters that define the behavior of the underlying hardware (in other words: even if these parameters are implementation-defined).

So the user would at least know that unsigned types may not have the same scale as their corresponding signed types if the hardware handles them with different scales.

Also added test for signed integer + unsigned saturating fixed point.

rjmccall added inline comments.Dec 1 2018, 7:47 AM
clang/lib/Sema/SemaExpr.cpp
1304 ↗(On Diff #175965)

As long as we maintain the same typing behavior, does the standard permit us to just Do The Right Thing here and do the extended arithmetic with the original unsigned operand? I'm sure there are some cases where we would produce a slightly different value than an implementation that does the coercion before the operation, but that might be permitted under the standard, and as you say, it would only affect some situations that it doesn't seem the standard has given much thought to.

ebevhan added inline comments.Dec 3 2018, 5:55 AM
clang/lib/Sema/SemaExpr.cpp
1304 ↗(On Diff #175965)

The coercion of unsigned to signed is likely done for pragmatic reasons; if you have a signed and unsigned type of the same rank, operating on them together won't require any 'extra bits'. This means that if your hardware has native support for the operations, you won't end up in a situation where you really need 33 or 34 bits (for a 32 bit value) to actually perform the operation. This is one of the benefits of these kinds of implicit conversions.

It probably makes the implementation a bit easier as well, since you don't have to consider cases where both sides have different signedness. The loss of the extra bit of precision from the unsigned operand is probably not considered to be very important. As Leonard said, if you wanted higher precision you can simply use the next rank of types. ...Of course, they seem to have forgotten that that exact issue with differing signedness also applies to operations with fixed-point and integer operands.

Personally, I think the spec could be a bit more restrictive with how it handles these conversions, as the way they are now makes it really hard to generate code sensibly for machines that have native support for these kinds of operations; in many cases you'll end up requiring a couple bits too many or a couple bits too few to fit in a sensible register size, and ensuring that the scales match what your hardware can handle is also a challenge.

rjmccall added inline comments.Dec 3 2018, 1:05 PM
clang/lib/Sema/SemaExpr.cpp
1304 ↗(On Diff #175965)

The coercion of unsigned to signed is likely done for pragmatic reasons; if you have a signed and unsigned type of the same rank, operating on them together won't require any 'extra bits'. This means that if your hardware has native support for the operations, you won't end up in a situation where you really need 33 or 34 bits (for a 32 bit value) to actually perform the operation. This is one of the benefits of these kinds of implicit conversions.

Yeah, I can see that. I think it really depends on the target. If you have hardware support, and you're using an unpadded representation for unsigned fixed-point values, then preserving the extra bit on mixed-signedness operations will sometimes prevent you from using the hardware optimally. On the other hand, if you don't have hardware support, preserving the extra bit is usually easier than not: e.g., IIUC, multiplying a 32-bit signed _Fract with a 32-bit unpadded unsigned _Fract means just doing a 64-bit multiplication and dropping the low 32 bits, whereas doing the conversion first actually requires extra operations to ensure that the low bit doesn't contribute to the result. And a target with hardware support is probably going to use a padded format for unsigned fixed-point precisely so that it can take advantage of the hardware.

...Of course, they seem to have forgotten that that exact issue with differing signedness also applies to operations with fixed-point and integer operands.

Right.

leonardchan marked an inline comment as done.Dec 3 2018, 2:41 PM
leonardchan added inline comments.
clang/lib/Sema/SemaExpr.cpp
1304 ↗(On Diff #175965)

For signed-unsigned multiplication, we could do that without having to do the conversion first, but in the case of addition and subtraction, we would still need to drop a bit with unpadded unsigned types so both have the same scales.

I don't want to make too many assumptions about hardware support, but I imagine that if one supports 32 bit signed addition, and unsigned types did not have padding, it would be better instead to LSHR on unsigned fixed point type then do 32 bit signed addition rather than SEXT+SHL on the signed fixed point type then do 33 bit signed addition.

rjmccall added inline comments.Dec 3 2018, 3:47 PM
clang/lib/Sema/SemaExpr.cpp
1304 ↗(On Diff #175965)

[I}n the case of addition and subtraction, we would still need to drop a bit with unpadded unsigned types so both have the same scales.

Right, but I don't think it matters because you're dropping that bit either way: with the specified semantics, you do the conversion beforehand which drops the bit, and with full-precision semantics, the bit isn't going to be representable and dropping it during the computation is equivalent to either rounding down (addition) or up (subtraction), either of which is allowed.

I don't want to make too many assumptions about hardware support, but I imagine that if one supports 32 bit signed addition, and unsigned types did not have padding, it would be better instead to LSHR on unsigned fixed point type then do 32 bit signed addition rather than SEXT+SHL on the signed fixed point type then do 33 bit signed addition.

My point is just that (1) the 33-bit signed addition can just be a 32-bit signed addition given that you ultimately have to produce a 32-bit result and (2) targets with hardware support are unlikely to use an unpadded unsigned type anyway. Although I suppose (2) is a bit questionable because hardware support could be added well after an ABI has been settled on.

leonardchan marked an inline comment as done.Dec 4 2018, 9:55 AM
leonardchan added inline comments.
clang/lib/Sema/SemaExpr.cpp
1304 ↗(On Diff #175965)

Ok. So should anything be changed here then if both semantics work? Currently we still do the 32 bit addition for signed and unsigned types.

rjmccall added inline comments.Dec 4 2018, 10:42 AM
clang/lib/Sema/SemaExpr.cpp
1304 ↗(On Diff #175965)

Well, most of what we're doing here is trying to lay good groundwork for all operations, and "both semantics work" is only true for same-rank addition, which is why I'm asking whether we should consider what semantics we actually want in general.

leonardchan marked an inline comment as done.Dec 4 2018, 3:10 PM
leonardchan added inline comments.
clang/lib/Sema/SemaExpr.cpp
1304 ↗(On Diff #175965)

I think the semantics for all binary arithmetic operators (+, -, *, /) can be simplified to:

  1. If one operand is a signed fixed point type and the other an unsigned type, convert the unsigned type to a signed type (which may involve reducing the scale).
  2. Find the common type of both operands that can hold both the larger scale and magnitude of the 2 operands, and cast them to this common type.
  3. Perform the binary operation.
  4. Cast to result type.

I think the semantics for addition are already settled with these semantics, and I believe subtraction shares the same semantics as those for addition. As you said before, the extra bit would not even matter with full precision since it would be trimmed anyway when converting from the common type to the result, and rounding can be either up or down.

Signed integer addition/subtraction with an unsigned fixed point type with these semantics will only lead to undefined behavior if the difference in the values between both types is negative since a negative value cannot be represented by an unsigned fixed point type (unless the result is saturating).

For multiplication and division, the result could technically be calculated also without having to cast between both sides, although for using the fixed point mul/div intrinsics, both operands would need to be casted to a common type with the same scale anyway. If a bit does end up getting dropped when casting an operand from unsigned to signed in (1), that dropped bit would not be representable when casting to the result anyway and the standard still allows us to return a rounded result.

When multiplying or dividing between a fixed point and integer though, we could just perform a regular integer mul/div if the result is non-saturating without having to perform the steps above. For saturating mul/div with an int, it might be easier to cast both sides to a common type then call the saturating fixed point mul/div intrinsics. In either case, I do not think rounding will be an issue here since we can still calculate the result precisely and the result will be either rounded up or down.

These semantics do not apply to comparison/relational operands, where if we do compare operands of different types or ranks, we would just need to find the common type between the 2 and perform the comparison.

rjmccall added inline comments.Dec 4 2018, 7:28 PM
clang/lib/Sema/SemaExpr.cpp
1304 ↗(On Diff #175965)

As you said before, the extra bit would not even matter with full precision since it would be trimmed anyway when converting from the common type to the result, and rounding can be either up or down.

Note that this is only true if the unsigned value has a scale that's greater than or equal to the scale of the result type, which is true for same-rank addition but not necessarily with mixed-rank.

For multiplication and division, the result could technically be calculated also without having to cast between both sides, although for using the fixed point mul/div intrinsics, both operands would need to be casted to a common type with the same scale anyway. If a bit does end up getting dropped when casting an operand from unsigned to signed in (1), that dropped bit would not be representable when casting to the result anyway and the standard still allows us to return a rounded result.

In a _Fract multiplication (or a mixed-rank multiplication), the extra bit of precision can affect higher bits in the result. Consider an 8-bit format where you're multiplying unsigned 000.00001 with signed +010.0000: if you do this multiplication in full precision, the result is +000.0001, but if you do the conversion first, the result is 0.

On some level, it just seems really strange to me that the spec calls for doing arbitrary-precision arithmetic and then converting to the result type for every situation except a signed/unsigned mismatch.

ebevhan added inline comments.Dec 5 2018, 7:34 AM
clang/lib/Sema/SemaExpr.cpp
1304 ↗(On Diff #175965)

Wait, wait... You might be on to something.

The spec says in 4.1.4:

In order to get useful and attainable results, the usual arithmetic conversions do not apply to the combination of an integer type and a fixed-point type, or the combination of two fixed-point types.
In these cases:

  1. the result of the operation is calculated using the values of the two operands, with their full precision;
  2. if one operand has signed fixed-point type and the other operand has unsigned fixed-point type, then the unsigned fixed-point operand is converted to its corresponding signed fixed-point type and the resulting type is the type of the converted operand;
  3. the result type is the type with the highest rank, [...]

(1) comes before (2); not after. In other words, shouldn't the true result of the operation be computed before the unsigned-signed correction? Point 2 is just worded really oddly, with 'operand is converted' and 'resulting type'.

It says that "the unsigned fixed-point operand is converted to its corresponding signed fixed-point type and the resulting type is the type of the converted operand", but this doesn't mean that the resulting converted operand is actually used, only its type is. This means that for the purpose of result type calculation in (3), the converted operand type from (2) will be used as that operand's type, rather than the unsigned type itself. Or?

The wording here is very hard to interpret.

rjmccall added inline comments.Dec 5 2018, 7:58 AM
clang/lib/Sema/SemaExpr.cpp
1304 ↗(On Diff #175965)

Sure, I think you could make an argument for (2) only being meant to participate in determining the result type. At the very least, that seems more consistent, especially with the behavior for fixed-point + integer operations. Do you have any existing contact with the committee?

ebevhan added inline comments.Dec 5 2018, 8:24 AM
clang/lib/Sema/SemaExpr.cpp
1304 ↗(On Diff #175965)

Do you have any existing contact with the committee?

I don't, no. Do you know who to contact regarding this sort of thing?

For the record, I just tested this with avr-gcc, which supports the E-C fixed-point (without padding on unsigned):

// 0.00390625 is 2*-8.
short _Accum calc = (unsigned short _Accum)0.00390625uk + (signed short _Accum)2.0k;

This produces:

calc:
        .byte   0
        .byte   1

If the unsigned was converted to signed (Q8.7) first, it should have had its bit stripped.

leonardchan marked an inline comment as done.
leonardchan added inline comments.
clang/lib/Sema/SemaExpr.cpp
1304 ↗(On Diff #175965)

After thinking about it, it seems more sensible to actually cast the type from unsigned to signed in (2) since that would go against (1). I also looked into contacting the committee but couldn't find any relevant emails.

Updated so that when determining the resulting type, the unsigned fixed point type is converted to that of the signed fixed point operand before comparing ranks. This does not cast the unsigned operand to the signed operand. Now the only casting done is converting to the common type.

Okay, thanks, that makes sense to me.

I'll ask around to find a way to contact the C committee.

Okay, thanks, that makes sense to me.

I'll ask around to find a way to contact the C committee.

@rjmccall Any updates on this? If we aren't able to find a way to contact anyone affiliated with publishing the spec, we could at least double check against avr-gcc for consistency regarding semantics.

We sent the question out, but we haven't gotten a response yet. I think going forward under the idea that this just changes the type but does the operation on the original operand types is the right way to go forward in the short term.

We sent the question out, but we haven't gotten a response yet. I think going forward under the idea that this just changes the type but does the operation on the original operand types is the right way to go forward in the short term.

Ok. Do you think it would be safe to submit this patch currently with the operations handled as you mentioned, or should we wait until we get a response and I can attach future revisions to this patch?

I'm fine with making this change under the assumption that we've gotten the language rule right. Even if that weren't abstractly reasonable for general language work — and I do think it's reasonable when we have a good-faith question about the right semantics — this is clearly still an experimental implementation and will be for several months yet, and hopefully it won't take that long for us to get a response.

I'm fine with making this change under the assumption that we've gotten the language rule right. Even if that weren't abstractly reasonable for general language work — and I do think it's reasonable when we have a good-faith question about the right semantics — this is clearly still an experimental implementation and will be for several months yet, and hopefully it won't take that long for us to get a response.

@rjmccall Have you received a response yet? If not, do you think you have an estimate on the response time, or also mind sharing the contact information if that's ok?

I'm fine with making this change under the assumption that we've gotten the language rule right. Even if that weren't abstractly reasonable for general language work — and I do think it's reasonable when we have a good-faith question about the right semantics — this is clearly still an experimental implementation and will be for several months yet, and hopefully it won't take that long for us to get a response.

@rjmccall Have you received a response yet? If not, do you think you have an estimate on the response time, or also mind sharing the contact information if that's ok?

I just have a coworker who's part of the committee. I think you might be over-opimistic about how quickly things get answered with the C committee, though. We should not allow our work to be blocked waiting for a response.

I'm fine with making this change under the assumption that we've gotten the language rule right. Even if that weren't abstractly reasonable for general language work — and I do think it's reasonable when we have a good-faith question about the right semantics — this is clearly still an experimental implementation and will be for several months yet, and hopefully it won't take that long for us to get a response.

@rjmccall Have you received a response yet? If not, do you think you have an estimate on the response time, or also mind sharing the contact information if that's ok?

I just have a coworker who's part of the committee. I think you might be over-opimistic about how quickly things get answered with the C committee, though. We should not allow our work to be blocked waiting for a response.

The committee was less helpful than I hoped, but what I decided to take away from their response was that we should not artificially lose precision here by separating the signedness conversion from the operation.

I'm fine with making this change under the assumption that we've gotten the language rule right. Even if that weren't abstractly reasonable for general language work — and I do think it's reasonable when we have a good-faith question about the right semantics — this is clearly still an experimental implementation and will be for several months yet, and hopefully it won't take that long for us to get a response.

@rjmccall Have you received a response yet? If not, do you think you have an estimate on the response time, or also mind sharing the contact information if that's ok?

I just have a coworker who's part of the committee. I think you might be over-opimistic about how quickly things get answered with the C committee, though. We should not allow our work to be blocked waiting for a response.

The committee was less helpful than I hoped, but what I decided to take away from their response was that we should not artificially lose precision here by separating the signedness conversion from the operation.

Understood. I imagine this is a good way to proceed still. Currently in this patch, the signedness only affects determining the resulting type and does not change the operands during the operation. Is there anything else with this patch that should be addressed, or is it still fine to proceed without committing this patch yet?

rjmccall accepted this revision.Jan 15 2019, 5:15 PM

I think that's the right direction, yeah.

I thought I told you it was fine to commit this patch under that assumption awhile ago. Did I just never click "accept"?

This revision is now accepted and ready to land.Jan 15 2019, 5:15 PM

I think that's the right direction, yeah.

I thought I told you it was fine to commit this patch under that assumption awhile ago. Did I just never click "accept"?

Whoops. I don't think there was an accept, so I kept this patch on hold.

This revision was automatically updated to reflect the committed changes.