This is an archive of the discontinued LLVM Phabricator instance.

[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
rC Clang

Event Timeline

leonardchan added inline comments.Oct 25 2018, 4:15 PM
clang/lib/CodeGen/CGExprScalar.cpp
3424–3448

There is a case when we cannot use the sadd/uadd intrinsics because those intrinsics saturate to the width of the operands when instead we want to saturate to the width of the resulting fixed point type. The problem is that if we are given operands with different scales that require extending then shifting before adding, the bit width no longer matches that of the resulting saturated type, so the sat intrinsics instead saturate to the extended width instead of the result type width. This could be a problem with my logic though and there could be a better way to implement addition.

Otherwise, as far as I can tell, this could be addressed by replacing the clamping with an intrinsic, which would create a use case for the signed/unsigned saturation intrinsics. Alternatively, the addition intrinsics could be expanded to also provide another argument that contains a desired saturation bit width, which would allow for collapsing the saturation type case into a call to this one intrinsic function.

I think I've already expressed that I'm not at all a fan of encoding the full-precision logic in the operations themselves and not explicitly in the AST. We already have (well, not yet, but we will) routines for emitting conversions to/from/between fixed-point types of arbitrary semantics - why not use that instead of reimplementing the same logic for every binary operation?

As it is now, EmitFixedPointAdd replicates the logic for both converting from integer to fixed-point and fixed-point to fixed-point. You mention a special case with saturating addition, but this special case only exists because the routine needs to do fixed-point->saturating fixed-point on its own. If all EmitFixedPointAdd did was perform an add between two fixed-point values with the same semantics, then the logic would be much simpler and the act of conversion would be delegated to the routines that actually handle it.

I want to float the idea again of adding an AST type to encapsulate an arbitrary fixed-point semantic and using that as the 'common type' for binary operations involving fixed-point types. This would enable UsualArithmeticConversions to handle fixed-point types similarly to how it does today (find the 'common' full precision type, implicitly cast the LHS and RHS if necessary). There is one new thing that it would have to do; the result after the operation should not be the full precision type, but rather be casted to the operand type of highest rank. I don't think the existing code in SemaExpr can handle the case of adding an implicit cast after the operation. I don't think it should be hard to add, though.

clang/lib/Sema/SemaExpr.cpp
1494

I'm not sure I understand why this is in a separate function. What part of this doesn't work in UsualArithmeticConversions, in a 'handleFixedPointConversion' similar to the other cases?

1517

I feel like this logic can be folded into the rank handling. Does it work properly if you give signed types higher rank than unsigned ones?

1536

This can be avoided by making all integer types lower rank than the fixed point types. The rank between them doesn't matter, either; they can all be the same.

bjope added inline comments.Oct 26 2018, 9:13 AM
clang/lib/CodeGen/CGExprScalar.cpp
3409

LHS = Builder.CreateIntCast(LHS, CommonTy, LHSSign);

(I think that it even is possible to remove the condition and always do this (the cast will be a no-op if LHSWidth==CommonWidth))

3412

Same as above, this can be simplified as:

RHS = Builder.CreateIntCast(RHS, CommonTy, RHSSign);
3415

Arithmetically I think that it would be enough to align the scale to

std::max(std::min(LHSScale, RHSScale), ResultScale)

As adding low fractional bits outside the result precision, when we know that those bits are zero in either of the inputs, won't impact any more significant bits in the result.

Maybe your solution is easier and good enough for a first implementation. And maybe opt is smart enough to optimize this anyway. Or maybe codegen could be worse due to not using legal types. Or maybe codegen could be improved due to using sadd.sat in more cases?
Lots of "maybes", so I don't think you need to do anything about this right now. It is just an idea from my side.

3453

It should be possible to do it like this (if you add some line wrapping):

Builder.CreateBinaryIntrinsic(ResultSign ? llvm::Intrinsic::sadd_sat : 
 llvm::Intrinsic::uadd_sat, LHS, RHS);

I want to float the idea again of adding an AST type to encapsulate an arbitrary fixed-point semantic and using that as the 'common type' for binary operations involving fixed-point types. This would enable UsualArithmeticConversions to handle fixed-point types similarly to how it does today (find the 'common' full precision type, implicitly cast the LHS and RHS if necessary). There is one new thing that it would have to do; the result after the operation should not be the full precision type, but rather be casted to the operand type of highest rank. I don't think the existing code in SemaExpr can handle the case of adding an implicit cast after the operation. I don't think it should be hard to add, though.

I don't think we should add *types* just for this, but if you need to make a different kind of BinaryOperator that represents that the semantics aren't quite the same (the same way that the compound assignments have their own subclass), that seems natural to me.

I don't think we should add *types* just for this, but if you need to make a different kind of BinaryOperator that represents that the semantics aren't quite the same (the same way that the compound assignments have their own subclass), that seems natural to me.

I don't know if adding a new operator kind was what I had in mind. The operator hasn't changed, it's still a normal binary operator. Compound assignments are their own operator with its own syntax; it doesn't really strike me as the same thing.

The important difference would be that we separate the semantics of performing the conversion and the operation. I understand that adding a new type could be a bit more involved than baking the conversion into the operator, but I really do not enjoy seeing so much implicit, implementation-specific logic encapsulated in the same AST element. Anyone who wants to look at BinaryOperators with fixed-point types will need to know all of the details of how the finding the common type and conversion is done, rather than simply "it does an addition".

I don't think we should add *types* just for this, but if you need to make a different kind of BinaryOperator that represents that the semantics aren't quite the same (the same way that the compound assignments have their own subclass), that seems natural to me.

I don't know if adding a new operator kind was what I had in mind. The operator hasn't changed, it's still a normal binary operator. Compound assignments are their own operator with its own syntax; it doesn't really strike me as the same thing.

Sorry for being unclear. I wasn't suggesting adding a new BinaryOperatorKind, I was suggesting making a subclass of BinaryOperator that stored the extra information you'd like to store.

The important difference would be that we separate the semantics of performing the conversion and the operation. I understand that adding a new type could be a bit more involved than baking the conversion into the operator, but I really do not enjoy seeing so much implicit, implementation-specific logic encapsulated in the same AST element. Anyone who wants to look at BinaryOperators with fixed-point types will need to know all of the details of how the finding the common type and conversion is done, rather than simply "it does an addition".

It's not just that adding a new type is "involved", it's that it's a bad solution. Those types can't actually be expressed in the language, and changing the type system to be able to express them is going to lead to a lot of pain elsewhere.

The important difference would be that we separate the semantics of performing the conversion and the operation. I understand that adding a new type could be a bit more involved than baking the conversion into the operator, but I really do not enjoy seeing so much implicit, implementation-specific logic encapsulated in the same AST element. Anyone who wants to look at BinaryOperators with fixed-point types will need to know all of the details of how the finding the common type and conversion is done, rather than simply "it does an addition".

It's not just that adding a new type is "involved", it's that it's a bad solution. Those types can't actually be expressed in the language, and changing the type system to be able to express them is going to lead to a lot of pain elsewhere.

I did figure that it might be a bit of work to adapt other parts of the code to handle the new type, but I just prefer separating the concerns and being explicit about what work is performed. To me, the clearest way of doing that is by handling the conversions explicitly in the AST, and separately from the operators themselves. Also, not being able to deal in QualTypes for the common full precision type handling means that reusing the operator handling code in Sema won't be easy, or even possible. It would have to be computed in CreateBuiltinBinOp, since it's not possible to forward anything but QualType from the CheckXXXOperands functions.

If you don't think it's a good idea I'll concede, but then there's the question of how to get the full precision semantics into the operator (if we store it there). I guess the most straightforward path is something like:

  • In CreateBuiltinBinOp, do the normal Check function to get the result type
  • If the result is a fixed-point type, go into a separate code path
  • Ask a method for the common FixedPointSemantics of the given LHS and RHS
  • Build the correct BinaryOperator subclass.

I need to think about this to see if our downstream implementation can be adapted to work with this design.

Compound assignments are already their own subclass, though. Unless the full precision semantic information is simply baked into the regular BinaryOperator, it would require two new subclasses: one for normal full precision operators and one for compound ones? Wouldn't adding this require new hooks and code paths in visitors, even though there's really nothing different about the operator?

The type information that CompoundAssignOperator stores today is rather similar to what a full precision operator would need, though it would need to store a FixedPointSemantics instead.


I do have more comments on the code at the moment, but I'm holding off a bit on the review while we iron out some of these details.

clang/lib/CodeGen/CGExprScalar.cpp
3357

This function should not be necessary. Instead, add to FixedPointSemantics:

  • static FixedPointSemantics GetIntegerSemantics(unsigned Width, bool IsSigned) to get an FPS for a specific integer width and signedness (width=Width, scale=0, sat=false, signed=IsSigned, padding=false)
  • FixedPointSemantics getCommonSemantics(const FixedPointSemantics &Other) to get an FPS for the common full precision semantic between this FPS and another one
3398

I think all of this (or at least something equivalent to it) should be calculated in Sema, not in CodeGen.

If we go with the idea of storing the full precision semantics in the operator, all the code in CodeGen should have to do is call EmitFixedPointConversion on the LHS and RHS with the FixedPointSemantics given by the operator. Same for converting back after the operation is performed.

clang/lib/Sema/SemaExpr.cpp
1411

Maybe this should be a method on ASTContext itself? It's probably useful in other cases.

9208

I think this 'commutativity' should be handled inside the function rather than here.

The important difference would be that we separate the semantics of performing the conversion and the operation. I understand that adding a new type could be a bit more involved than baking the conversion into the operator, but I really do not enjoy seeing so much implicit, implementation-specific logic encapsulated in the same AST element. Anyone who wants to look at BinaryOperators with fixed-point types will need to know all of the details of how the finding the common type and conversion is done, rather than simply "it does an addition".

It's not just that adding a new type is "involved", it's that it's a bad solution. Those types can't actually be expressed in the language, and changing the type system to be able to express them is going to lead to a lot of pain elsewhere.

I did figure that it might be a bit of work to adapt other parts of the code to handle the new type, but I just prefer separating the concerns and being explicit about what work is performed. To me, the clearest way of doing that is by handling the conversions explicitly in the AST, and separately from the operators themselves. Also, not being able to deal in QualTypes for the common full precision type handling means that reusing the operator handling code in Sema won't be easy, or even possible. It would have to be computed in CreateBuiltinBinOp, since it's not possible to forward anything but QualType from the CheckXXXOperands functions.

If you don't think it's a good idea I'll concede, but then there's the question of how to get the full precision semantics into the operator (if we store it there). I guess the most straightforward path is something like:

  • In CreateBuiltinBinOp, do the normal Check function to get the result type
  • If the result is a fixed-point type, go into a separate code path
  • Ask a method for the common FixedPointSemantics of the given LHS and RHS
  • Build the correct BinaryOperator subclass.

I need to think about this to see if our downstream implementation can be adapted to work with this design.

Compound assignments are already their own subclass, though. Unless the full precision semantic information is simply baked into the regular BinaryOperator, it would require two new subclasses: one for normal full precision operators and one for compound ones? Wouldn't adding this require new hooks and code paths in visitors, even though there's really nothing different about the operator?

The type information that CompoundAssignOperator stores today is rather similar to what a full precision operator would need, though it would need to store a FixedPointSemantics instead.

Well, maybe the cleanest solution would be to actually fold CompoundAssignOperator back into BinaryOperator and just allow BinaryOperator to optionally store information about the intermediate type of the computation and how the operands need to be promoted. That information could be elided in the common cases where it's trivial, of course.

The infinite-precision rule here is still internal to an individual operator, right? The standard's not trying to say that we should evaluate x + y < z by doing a comparison as if all the operands were individually infinite-precision?

Well, maybe the cleanest solution would be to actually fold CompoundAssignOperator back into BinaryOperator and just allow BinaryOperator to optionally store information about the intermediate type of the computation and how the operands need to be promoted. That information could be elided in the common cases where it's trivial, of course.

That sounds like a fairly hefty refactor. Also, doing the fold would put the extra QualType info from CAO into BO, sure, but this cannot work for the full-precision case since we can't represent those with QualTypes. The information for the full precision 'type' would have to be stored separately anyway.

Or did you mean to make a subclass of that new BinaryOperator for the full precision case, and store the full precision info there?

It might just be easier to store the full-precision info in BO directly. BO might be too common to warrant the size increase, though. FixedPointSemantics can probably be optimized to only take 32 bits.

The infinite-precision rule here is still internal to an individual operator, right? The standard's not trying to say that we should evaluate x + y < z by doing a comparison as if all the operands were individually infinite-precision?

Correct, the result of the computation is 'implicitly converted' back to the result type after the operation is performed. The type of the expression will always be the result type, never the full precision type.

As a side note, comparisons are still a bit up in the air. I don't think we came to a conclusion on whether they should be done in full precision or bitwise. The spec isn't clear.

Well, maybe the cleanest solution would be to actually fold CompoundAssignOperator back into BinaryOperator and just allow BinaryOperator to optionally store information about the intermediate type of the computation and how the operands need to be promoted. That information could be elided in the common cases where it's trivial, of course.

That sounds like a fairly hefty refactor. Also, doing the fold would put the extra QualType info from CAO into BO, sure, but this cannot work for the full-precision case since we can't represent those with QualTypes. The information for the full precision 'type' would have to be stored separately anyway.

Well, it could be passed around through most code as some sort of abstractly-represented intermediate "type" which could be either a QualType or a fixed-point semantics.

It might just be easier to store the full-precision info in BO directly. BO might be too common to warrant the size increase, though. FixedPointSemantics can probably be optimized to only take 32 bits.

What you can definitely do is store a bit in BO saying that there's extra storage for the intermediate "type".

The infinite-precision rule here is still internal to an individual operator, right? The standard's not trying to say that we should evaluate x + y < z by doing a comparison as if all the operands were individually infinite-precision?

Correct, the result of the computation is 'implicitly converted' back to the result type after the operation is performed. The type of the expression will always be the result type, never the full precision type.

Okay, good.

As a side note, comparisons are still a bit up in the air. I don't think we came to a conclusion on whether they should be done in full precision or bitwise. The spec isn't clear.

...bitwise?

Well, it could be passed around through most code as some sort of abstractly-represented intermediate "type" which could be either a QualType or a fixed-point semantics.

Sounds to me like you're describing a new Type that can contain an arbitrary fixed-point semantic :)

It still feels like this just introduces inconsistencies into the form of the AST. If we do add this extra type object to the BO, won't people wonder why we use ImplicitCastExpr for non-fixedpoint operations but use the special QualTypeOrFPSemantics BinaryOperator::ComputationType; for fixedpoint operations even though they both have nearly the same semantic meaning (converting to a common type before doing the operation)?

(The difference being that using the ComputationType requires you to cast back to the result type afterwards.)

It might just be easier to store the full-precision info in BO directly. BO might be too common to warrant the size increase, though. FixedPointSemantics can probably be optimized to only take 32 bits.

What you can definitely do is store a bit in BO saying that there's extra storage for the intermediate "type".

Is this similar to how ExtQuals works? How would this be implemented?

As a side note, comparisons are still a bit up in the air. I don't think we came to a conclusion on whether they should be done in full precision or bitwise. The spec isn't clear.

...bitwise?

The spec uses different wording for the arithmetic operations and comparison operations, and it's not entirely obvious what it means. For the arithmetic operators, it has the whole section on finding the full precision common type, but for comparisons it says:

When comparing fixed-point values with fixed-point values or integer values,
the values are compared directly; the values of the operands are not converted before the
comparison is made.

What 'directly' means in conjunction with 'the operands are not converted' is not clear. It's reasonable to assume that it either means comparing value-wise (so, the same as finding a common type that fits all values and then comparing; though this would obviously require conversion), or perhaps 'directly' means a bitwise (representation) comparison. The latter seems a bit farfetched to me, though.

Well, it could be passed around through most code as some sort of abstractly-represented intermediate "type" which could be either a QualType or a fixed-point semantics.

Sounds to me like you're describing a new Type that can contain an arbitrary fixed-point semantic :)

The fact that it doesn't exist in the modeled type system is important.

The arbitrary-type overflow intrinsics have this same problem, and we did not try to solve it by creating a new type class for arbitrary-precision integers and promoting the arguments.

It still feels like this just introduces inconsistencies into the form of the AST. If we do add this extra type object to the BO, won't people wonder why we use ImplicitCastExpr for non-fixedpoint operations but use the special QualTypeOrFPSemantics BinaryOperator::ComputationType; for fixedpoint operations even though they both have nearly the same semantic meaning (converting to a common type before doing the operation)?

  1. You would have an inconsistency in either case, since e.g. numeric + otherwise always returns the same type as its operands, but this would not.
  2. The question is easily answered by pointing at the language spec. The language does not say that the operands are promoted to a common type; it says the result is determined numerically from the true numeric values of the operands.

It might just be easier to store the full-precision info in BO directly. BO might be too common to warrant the size increase, though. FixedPointSemantics can probably be optimized to only take 32 bits.

What you can definitely do is store a bit in BO saying that there's extra storage for the intermediate "type".

Is this similar to how ExtQuals works? How would this be implemented?

Take a look at how DeclRefExpr stores its various optional components.

As a side note, comparisons are still a bit up in the air. I don't think we came to a conclusion on whether they should be done in full precision or bitwise. The spec isn't clear.

...bitwise?

The spec uses different wording for the arithmetic operations and comparison operations, and it's not entirely obvious what it means. For the arithmetic operators, it has the whole section on finding the full precision common type, but for comparisons it says:

When comparing fixed-point values with fixed-point values or integer values,
the values are compared directly; the values of the operands are not converted before the
comparison is made.

What 'directly' means in conjunction with 'the operands are not converted' is not clear. It's reasonable to assume that it either means comparing value-wise (so, the same as finding a common type that fits all values and then comparing; though this would obviously require conversion), or perhaps 'directly' means a bitwise (representation) comparison. The latter seems a bit farfetched to me, though.

I think this is just like fixed-point arithmetic: you should do an exact numeric comparison, but there's no formal conversion because it would have to be a conversion to some concrete type, which could leave to (mandatory!) inexactness when there's no common type that expresses the full range of both operands.

Arguably this is all how integer arithmetic and comparisons should work, but that's not something they can fix in a TR. (Floating-point doesn't need to work this way because the FP types subset each other.)

Well, it could be passed around through most code as some sort of abstractly-represented intermediate "type" which could be either a QualType or a fixed-point semantics.

Sounds to me like you're describing a new Type that can contain an arbitrary fixed-point semantic :)

The fact that it doesn't exist in the modeled type system is important.

The arbitrary-type overflow intrinsics have this same problem, and we did not try to solve it by creating a new type class for arbitrary-precision integers and promoting the arguments.

Okay, I had a look at how those were emitted, I wasn't familiar with it until now. That's certainly a way of approaching this implementation as well, though I think the full precision info should still be in the AST somewhere rather than implied from the operand types until CodeGen.

It still feels like this just introduces inconsistencies into the form of the AST. If we do add this extra type object to the BO, won't people wonder why we use ImplicitCastExpr for non-fixedpoint operations but use the special QualTypeOrFPSemantics BinaryOperator::ComputationType; for fixedpoint operations even though they both have nearly the same semantic meaning (converting to a common type before doing the operation)?

  1. You would have an inconsistency in either case, since e.g. numeric + otherwise always returns the same type as its operands, but this would not.

True, but the CompoundAssignOperator already has that inconsistency with ComputationResultType.

  1. The question is easily answered by pointing at the language spec. The language does not say that the operands are promoted to a common type; it says the result is determined numerically from the true numeric values of the operands.

I guess. I just see that as a behavioral specification and not necessarily an implementation detail. It's perfectly acceptable to implement it as promotion to a common type (obviously, as that's what we are going to do), and I don't really see this as the spec putting any kind of requirement on how the implementation should be done.

It might just be easier to store the full-precision info in BO directly. BO might be too common to warrant the size increase, though. FixedPointSemantics can probably be optimized to only take 32 bits.

What you can definitely do is store a bit in BO saying that there's extra storage for the intermediate "type".

Is this similar to how ExtQuals works? How would this be implemented?

Take a look at how DeclRefExpr stores its various optional components.

TrailingObjects, then. That certainly wouldn't work if CompoundAssignOperator is still a subclass of BinaryOperator, so it would have to be folded in that case.

So the implementation would be with a TrailingObjects<BinaryOperator, QualType, FixedPointSemantics> where it can have 2 QualTypes and 1 FixedPointSemantics, the QualTypes being subsumed from CompoundAssignOperator.

Probably still quite a hefty amount of code that would have to be updated to make this change.

As a side note, comparisons are still a bit up in the air. I don't think we came to a conclusion on whether they should be done in full precision or bitwise. The spec isn't clear.

...bitwise?

The spec uses different wording for the arithmetic operations and comparison operations, and it's not entirely obvious what it means. For the arithmetic operators, it has the whole section on finding the full precision common type, but for comparisons it says:

When comparing fixed-point values with fixed-point values or integer values,
the values are compared directly; the values of the operands are not converted before the
comparison is made.

What 'directly' means in conjunction with 'the operands are not converted' is not clear. It's reasonable to assume that it either means comparing value-wise (so, the same as finding a common type that fits all values and then comparing; though this would obviously require conversion), or perhaps 'directly' means a bitwise (representation) comparison. The latter seems a bit farfetched to me, though.

I think this is just like fixed-point arithmetic: you should do an exact numeric comparison, but there's no formal conversion because it would have to be a conversion to some concrete type, which could leave to (mandatory!) inexactness when there's no common type that expresses the full range of both operands.

This is probably the correct interpretation, I just think it could have been stated a bit clearer that they pretty much do mean the same thing for the comparison operators as for the arithmetic operators.

  1. You would have an inconsistency in either case, since e.g. numeric + otherwise always returns the same type as its operands, but this would not.

True, but the CompoundAssignOperator already has that inconsistency with ComputationResultType.

Right, but it's the same inconsistency, which is why I'm suggesting that you treat this as an opportunity to generalize it. Or we can avoid recording it and just make it up in IRGen.

  1. The question is easily answered by pointing at the language spec. The language does not say that the operands are promoted to a common type; it says the result is determined numerically from the true numeric values of the operands.

I guess. I just see that as a behavioral specification and not necessarily an implementation detail. It's perfectly acceptable to implement it as promotion to a common type (obviously, as that's what we are going to do), and I don't really see this as the spec putting any kind of requirement on how the implementation should be done.

Of course it's a behavioral specification. All I'm saying is that the implementation detail of how we perform these operations isn't really reasonable or appropriate to express in the AST. I know it's a bit fuzzy because of some of the things we do with e.g. opaque values and so on, but the AST is not meant to be a completely implementation-defined IR; it tries to capture the formal semantics of the program including "official" conversions and so on. Integer addition is specified as converting its arguments to a common type and then performing a homogenous operation in that type. Fixed-point addition is not; it's specified as doing a heterogenous operation on the original (well, rvalue-converted) operand types.

It might just be easier to store the full-precision info in BO directly. BO might be too common to warrant the size increase, though. FixedPointSemantics can probably be optimized to only take 32 bits.

What you can definitely do is store a bit in BO saying that there's extra storage for the intermediate "type".

Is this similar to how ExtQuals works? How would this be implemented?

Take a look at how DeclRefExpr stores its various optional components.

TrailingObjects, then. That certainly wouldn't work if CompoundAssignOperator is still a subclass of BinaryOperator, so it would have to be folded in that case.

So the implementation would be with a TrailingObjects<BinaryOperator, QualType, FixedPointSemantics> where it can have 2 QualTypes and 1 FixedPointSemantics, the QualTypes being subsumed from CompoundAssignOperator.

Probably still quite a hefty amount of code that would have to be updated to make this change.

Not out of line with other features that significantly break with what's expressible. But the easy alternative to storing the intermediate "type" in the AST is to just provide a global function that can compute it on demand.

  1. The question is easily answered by pointing at the language spec. The language does not say that the operands are promoted to a common type; it says the result is determined numerically from the true numeric values of the operands.

I guess. I just see that as a behavioral specification and not necessarily an implementation detail. It's perfectly acceptable to implement it as promotion to a common type (obviously, as that's what we are going to do), and I don't really see this as the spec putting any kind of requirement on how the implementation should be done.

Of course it's a behavioral specification. All I'm saying is that the implementation detail of how we perform these operations isn't really reasonable or appropriate to express in the AST. I know it's a bit fuzzy because of some of the things we do with e.g. opaque values and so on, but the AST is not meant to be a completely implementation-defined IR; it tries to capture the formal semantics of the program including "official" conversions and so on. Integer addition is specified as converting its arguments to a common type and then performing a homogenous operation in that type. Fixed-point addition is not; it's specified as doing a heterogenous operation on the original (well, rvalue-converted) operand types.

Okay, those are good points. I guess I might have been a bit too focused on reusing the behavior of the AST to fit the implementation, but that doesn't seem to be the intention with it.

It might just be easier to store the full-precision info in BO directly. BO might be too common to warrant the size increase, though. FixedPointSemantics can probably be optimized to only take 32 bits.

What you can definitely do is store a bit in BO saying that there's extra storage for the intermediate "type".

Is this similar to how ExtQuals works? How would this be implemented?

Take a look at how DeclRefExpr stores its various optional components.

TrailingObjects, then. That certainly wouldn't work if CompoundAssignOperator is still a subclass of BinaryOperator, so it would have to be folded in that case.

So the implementation would be with a TrailingObjects<BinaryOperator, QualType, FixedPointSemantics> where it can have 2 QualTypes and 1 FixedPointSemantics, the QualTypes being subsumed from CompoundAssignOperator.

Probably still quite a hefty amount of code that would have to be updated to make this change.

Not out of line with other features that significantly break with what's expressible. But the easy alternative to storing the intermediate "type" in the AST is to just provide a global function that can compute it on demand.

Yeah, it might just be simpler to go the route of not storing the computation semantic in the AST, at least for now. That's fairly similar to the solution in the patch, so I feel a bit silly for just going around in a circle.

To make that work I think the patch needs some changes, though. There should be a function in FixedPointSemantics to find the common full-precision semantic between two semantics, and the getFixedPointSemantics in ASTContext should be amended to take integer types (or another method should be provided for this, but that one already exists). I think that the FixedPointConversions method should also be embedded into the rest of UsualArithmeticConversions as there shouldn't be any need to have it separate. You still want to do the rvalue conversion and other promotions, and the rules for fixed-point still fit into the arithmetic conversions, even in the spec.

EmitFixedPointConversion should be changed to take FixedPointSemantics rather than QualType. This has a couple of downsides:

  • It can no longer handle floating point conversions. They would have to be handled in EmitScalarConversion.
  • Conversion from integer is fine, but conversion to integer cannot be generalized away with the fixed-point semantics as they are currently, as that kind of conversion must round towards zero. This requires a rounding step for negative numbers before downscaling, which the current code does not do.

Is there a better way of generalizing this?

All EmitFixedPointAdd should have to do is get the semantics of the operands and result type, get their full-precision semantic, call EmitFixedPointConversion on both operands, do the addition, and call it again to convert back to the result value. Move as much of the conversions as possible out of the function.

Does all this sound reasonable?

Not out of line with other features that significantly break with what's expressible. But the easy alternative to storing the intermediate "type" in the AST is to just provide a global function that can compute it on demand.

Yeah, it might just be simpler to go the route of not storing the computation semantic in the AST, at least for now. That's fairly similar to the solution in the patch, so I feel a bit silly for just going around in a circle.

To make that work I think the patch needs some changes, though. There should be a function in FixedPointSemantics to find the common full-precision semantic between two semantics, and the getFixedPointSemantics in ASTContext should be amended to take integer types (or another method should be provided for this, but that one already exists). I think that the FixedPointConversions method should also be embedded into the rest of UsualArithmeticConversions as there shouldn't be any need to have it separate. You still want to do the rvalue conversion and other promotions, and the rules for fixed-point still fit into the arithmetic conversions, even in the spec.

EmitFixedPointConversion should be changed to take FixedPointSemantics rather than QualType. This has a couple of downsides:

  • It can no longer handle floating point conversions. They would have to be handled in EmitScalarConversion.
  • Conversion from integer is fine, but conversion to integer cannot be generalized away with the fixed-point semantics as they are currently, as that kind of conversion must round towards zero. This requires a rounding step for negative numbers before downscaling, which the current code does not do.

Is there a better way of generalizing this?

FixedPointSemantics is free to do whatever is convenient for the representation; if it helps to make it able to explicitly represent an integral type — and then just assert that it's never in that form when it's used in certain places, I think that works. Although you might consider making a FixedPointOrIntegralSemantics class and then making FixedPointSemantics a subclass which adds nothing to the representation but semantically asserts that it's representing a fixed-point type.

All EmitFixedPointAdd should have to do is get the semantics of the operands and result type, get their full-precision semantic, call EmitFixedPointConversion on both operands, do the addition, and call it again to convert back to the result value. Move as much of the conversions as possible out of the function.

Does all this sound reasonable?

Makes sense to me.

Not out of line with other features that significantly break with what's expressible. But the easy alternative to storing the intermediate "type" in the AST is to just provide a global function that can compute it on demand.

Yeah, it might just be simpler to go the route of not storing the computation semantic in the AST, at least for now. That's fairly similar to the solution in the patch, so I feel a bit silly for just going around in a circle.

To make that work I think the patch needs some changes, though. There should be a function in FixedPointSemantics to find the common full-precision semantic between two semantics, and the getFixedPointSemantics in ASTContext should be amended to take integer types (or another method should be provided for this, but that one already exists). I think that the FixedPointConversions method should also be embedded into the rest of UsualArithmeticConversions as there shouldn't be any need to have it separate. You still want to do the rvalue conversion and other promotions, and the rules for fixed-point still fit into the arithmetic conversions, even in the spec.

EmitFixedPointConversion should be changed to take FixedPointSemantics rather than QualType. This has a couple of downsides:

  • It can no longer handle floating point conversions. They would have to be handled in EmitScalarConversion.
  • Conversion from integer is fine, but conversion to integer cannot be generalized away with the fixed-point semantics as they are currently, as that kind of conversion must round towards zero. This requires a rounding step for negative numbers before downscaling, which the current code does not do.

Is there a better way of generalizing this?

FixedPointSemantics is free to do whatever is convenient for the representation; if it helps to make it able to explicitly represent an integral type — and then just assert that it's never in that form when it's used in certain places, I think that works. Although you might consider making a FixedPointOrIntegralSemantics class and then making FixedPointSemantics a subclass which adds nothing to the representation but semantically asserts that it's representing a fixed-point type.

It might just be simpler and a bit more general to add a DownscalingRoundsTowardZero field to FixedPointSemantics, which specifies that the source value should be rounded toward zero before downscaling. Then conversion routines could handle the integer case explicitly. I'm not sure if the field would be useful for anything else, though; it has a pretty specific meaning.

I think it's a bit odd to have FixedPointSemantics as a specialization of something else, since technically integers are a specialization of fixed-point values and not the other way around.

Not out of line with other features that significantly break with what's expressible. But the easy alternative to storing the intermediate "type" in the AST is to just provide a global function that can compute it on demand.

Yeah, it might just be simpler to go the route of not storing the computation semantic in the AST, at least for now. That's fairly similar to the solution in the patch, so I feel a bit silly for just going around in a circle.

To make that work I think the patch needs some changes, though. There should be a function in FixedPointSemantics to find the common full-precision semantic between two semantics, and the getFixedPointSemantics in ASTContext should be amended to take integer types (or another method should be provided for this, but that one already exists). I think that the FixedPointConversions method should also be embedded into the rest of UsualArithmeticConversions as there shouldn't be any need to have it separate. You still want to do the rvalue conversion and other promotions, and the rules for fixed-point still fit into the arithmetic conversions, even in the spec.

EmitFixedPointConversion should be changed to take FixedPointSemantics rather than QualType. This has a couple of downsides:

  • It can no longer handle floating point conversions. They would have to be handled in EmitScalarConversion.
  • Conversion from integer is fine, but conversion to integer cannot be generalized away with the fixed-point semantics as they are currently, as that kind of conversion must round towards zero. This requires a rounding step for negative numbers before downscaling, which the current code does not do.

Is there a better way of generalizing this?

FixedPointSemantics is free to do whatever is convenient for the representation; if it helps to make it able to explicitly represent an integral type — and then just assert that it's never in that form when it's used in certain places, I think that works. Although you might consider making a FixedPointOrIntegralSemantics class and then making FixedPointSemantics a subclass which adds nothing to the representation but semantically asserts that it's representing a fixed-point type.

It might just be simpler and a bit more general to add a DownscalingRoundsTowardZero field to FixedPointSemantics, which specifies that the source value should be rounded toward zero before downscaling. Then conversion routines could handle the integer case explicitly. I'm not sure if the field would be useful for anything else, though; it has a pretty specific meaning.

I think it's a bit odd to have FixedPointSemantics as a specialization of something else, since technically integers are a specialization of fixed-point values and not the other way around.

Well, it's not a specialization of "integer", it's a specialization of "fixed-point or integer". It depends on how useful it ends up being to know that something statically isn't integral.

leonardchan marked 11 inline comments as done.

Sorry for the delay in responding to this. Been working on a few other patches.

A couple of the bigger changes so far:

  • Added getCommonSemantics to FixedPointSemantics for finding a common full precision semantic.
  • getFixedPointSemantics accepts an int type.
  • FixedPointConversions was renamed to handleFixedPointConversions and is a part of UsualArithmeticConversions
  • EmitFixedPointAdd now works by converting both operands to a common FixedPointSemantics that can hold the full precision of the result, performing a regular add or call to the addition intrinsics, and converting back to the result type if necessary.
    • This also fixed the case with calling the sat add intrinsics.
  • Change EmitFixedPointConversion to accept FixedPointSemantics. I kept the original one still which takes QualTypes that are fixed point or integer types and gets the FixedPointSemantics from them.

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.

clang/lib/CodeGen/CGExprScalar.cpp
3409

Replaced this part with converting the operands to common semantics, then regular addition.

3412

Same as above.

3415

Same as above.

3424–3448

Fixed by converting operands to common fixed point semantics, adding, then converting the result. This ends up producing the same instructions as the original tests.

clang/lib/Sema/SemaExpr.cpp
1494

I might've misinterpreted the standard in that operations between fixed point and other fixed point or integers didn't fall under usual arithmetic conversions, but I can see how it would be simpler to keep in in UAC since almost all checks on binary operations call this.

Added a changed FixedPointConversions to handleFixedPointConversion.

1517

I think this is necessary since it seems the purpose of this is to align the scales between signed and unsigned types if they are different. For signed and unsigned types specifically, the standard also says unsigned fixed-point operand is converted to its corresponding signed fixed-point type which I think means it's an actual conversion.

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

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

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

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

Can EmitFixedPointConversion not determine this on its own?

3387

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

clang/lib/Sema/SemaExpr.cpp
1306

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

1403

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

Added test for this also.

clang/lib/Sema/SemaExpr.cpp
1306

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
3380

Missing a C there.

clang/lib/Sema/SemaExpr.cpp
1306

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

clang/test/Frontend/fixed_point_add.c
37

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
37

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

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
270

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
270

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
270

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
270

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
270

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
270

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

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

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

64

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?

67

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

clang/lib/AST/ASTContext.cpp
10489

Does getIntWidth do the thing you want for bool?

clang/lib/Basic/FixedPoint.cpp
141

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
64

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

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

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
64

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

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
3361

Please use cast.

clang/lib/Sema/SemaExpr.cpp
1237

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

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

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

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
64

Yup. Updated the documentation.

clang/lib/Sema/SemaExpr.cpp
1304

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

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

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

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

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

[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

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

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

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

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

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

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

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

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.