[llvm-dev] Fixed Point Support in LLVM

Tue Aug 21 20:12:21 PDT 2018

I would strongly advise getting to a working end to end implementation  
- ideally entirely upstream - before proposing any new types if you 
can.  I disagree with John about the impact of a new type, not so much 
from a LOC perspective, but from a review burden/conceptual burden 
perspective.  Starting with something which works (say integers), 
implementing some of the basic missing optimizations, and having a 
working end-to-end system before proposing any major IR extensions is 
strongly advised.

OT: I noticed saturation coming up a couple of times.  For integers, we 
handle saturation by using a op.with.overflow/select idiom.  Does the 
same basic notion work for the fixed point operations?   If it does, 
that reduces the number of required operations by half.

Philip

On 08/21/2018 03:20 PM, Leonard Chan via llvm-dev wrote:
> If we were to create a new type down the line, I think the main
> features that would distinguish them from other types are the
> arbitrary width and scale. Saturation can be handled through
> instructions since saturation really only takes effect after an
> operation and doesn’t really describe anything about the bits in the
> resulting type. Signage can similarly be managed through operations
> and would be consistent with the separation in signed and unsigned int
> operations.
>
> The unsigned padding is a result of the data bits not taking the whole
> width of the underlying llvm integer in the frontend for optimization
> purposes, so (I don’t think) this would be a problem if fixed points
> were represented as a native type of arbitrary width and scale
> (similar to how llvm represents arbitrary width integers like i33).
>
> I’m unsure if I should stop what I’m working on now though to
> implement this type. Although it seems correct, there also doesn’t
> seem to be a very high demand for a new llvm type. I imagine another
> reason one would add a new type, in addition to your reasons, is that
> it represents a common type that could be used in multiple frontends,
> but it doesn’t seem like other llvm frontends actively demand this.
> For now I imagine intrinsics would be a nice middle ground and down
> the line once fixed point types are fully fleshed out, we can explore
> adding a new llvm type.
>
> On Mon, Aug 20, 2018 at 1:14 PM John McCall <rjmccall at apple.com> wrote:
>>> On Aug 20, 2018, at 1:59 PM, Leonard Chan via llvm-dev <llvm-dev at lists.llvm.org> wrote:
>>>
>>> We would like to discuss the possibility of adding support for fixed
>>> point operations, either through new types, instructions, or
>>> intrinsics. This is an extension to a previous proposal
>>> (http://lists.llvm.org/pipermail/cfe-dev/2018-April/057756.html) for
>>> implementing fixed point arithmetic entirely in clang, but John McCall
>>> brings up good points in the comments thread of
>>> https://reviews.llvm.org/D50616 for adding LLVM support.
>>>
>>> Just to summarize the proposal, Embedded-C lays out an implementation
>>> for fixed point data types and operations on them. A fixed point
>>> number is a number that contains a fractional and integral part. These
>>> types can essentially be represented as scaled integers, that is, a
>>> radix point exists somewhere in the integer that divides it into
>>> integral and fractional bits.
>>>
>>> Adding a new type seems unnecessary since all fixed point types in the
>>> spec can be represented as integers. For operations involving these
>>> integers, the scale could ideally be passed as an argument to whatever
>>> instruction or intrinsic is performing a fixed point operation. I’m
>>> not sure of the difference in work between adding a new instruction vs
>>> intrinsic, but this would ideally be done for complex operations.
>> At the risk of distracting from your narrower proposal, I'd like to pitch the idea of adding
>> fixed-point values as a new fundamental type in IR.  I think it's really easy to assume
>> that this would be a dauntingly complicated task just because it's not something that
>> most people have experience doing.  Most of the complexity would be in targets, and
>> we could easily eliminate these types in a generic legalization pass in the backend to
>> reduce that impact.
>>
>> And "all fixed point types in the spec can be represented as integers" is true
>> of literally everything in LLVM.  Every type we've got (except for opaque structs,
>> I guess) is a finite, fixed-size sequence of bits; nonetheless, we have direct support
>> for representing pointers, vectors, FP, and so on, when we could absolutely instead
>> use an appropriately-sized integer type, a large collection of intrinsics, and some sort
>> of "fpreg" attribute on call arguments to mark the difference in CCs.
>>
>> In general, I think LLVM has gotten way too addicted to the pretense that adding things
>> as intrinsics or funky instruction attributes isn't adding just as much complexity as adding
>> new types and instructions.  LLVM should clearly provide portable support for fixed-point
>> operations.  We can do that with weird integer constants and a bunch of intrinsics, but
>> that seems to me like it's just hiding the complexity and making things harder for everyone
>> involved.
>>
>> Fixed-point types would be quite similar to floating-point types in terms of their
>> overall impact on the complexity of IR — which is to say, not very big — except
>> predictably smaller because there's no analogue to the complexity around the
>> floating-point special cases (i.e. NaNs, negative zero, and infinities) and the various
>> features relating to them (e.g. the fast-math flags).  Type layout would just default to
>> using the rules for an integer of the same width.  There just isn't that much code in
>> LLVM that tries to do something different for every possible type instead of assuming
>> that
>>
>> If we did this, I would suggest separating types by representation differences, not the
>> semantics of the operations on them.  For example, we'd have different operations for
>> saturating and non-saturating arithmetic, but saturating and non-saturing types would
>> get lowered to the same IR type.  Unlike integers, though, I think maybe we wouldn't
>> want to unify signed and unsigned types because of the padded-representation issue;
>> or maybe we'd only unify types with the same internal layout, so that a padded unsigned
>> type would be different from an unpadded one of the same overall width.
>>
>> Note that having saturating-arithmetic instructions would also be useful for integers
>> and integer vectors, and could similarly be legalized generically in the backend for
>> targets that don't have direct ISA support for them.
>>
>> John.
>>
>>> Namely, intrinsics/instructions would be added for these operations:
>>> - signed multiplication
>>> - signed saturating multiplication
>>> - signed division
>>> - unsigned division
>>> - signed saturating division
>>> - unsigned saturating division
>>> - saturation
>>> - saturating addition
>>> - saturating subtraction
>>> - floating-point to fixed-point conversion
>>>
>>> Bevin Hansson has implemented these in his downstream version of
>>> clang/llvm (http://lists.llvm.org/pipermail/cfe-dev/2018-May/058019.html),
>>> and I imagine this is all we may need for intrinsics. We would like to
>>> offset complicated instructions to llvm for targets that provide
>>> native support for these operations while still being able to manage
>>> most of the semantics on the frontend since many simple operations can
>>> be done using existing instructions. These operations will default to
>>> code generated IR for architectures that do not support fixed points
>>> natively.
>>>
>>> Does anyone have any more thoughts on how to correctly approach this?
>>>
>>> Thanks,
>>> Leo
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> llvm-dev at lists.llvm.org
>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev