[llvm-dev] Fixed Point Support in LLVM

Tue Aug 21 21:37:37 PDT 2018

> On Aug 21, 2018, at 11:12 PM, Philip Reames <listmail at philipreames.com> wrote:
> 
> 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.

On the "conceptual burden" point, can you elaborate on why you think you'd be
forced to think about fixed-point types if they were added to IR?

There are a number of things in the current design of IR that are real burdens
because you have to remember them every time you work with certain operations,
like how a load can be volatile or atomic.  But those are flaws in the design of those
operations — they should really be different instructions — rather than inherent
problems that would have to be duplicated for any new feature.  I imagine fixed-point
types would have their own set of operations, like floating-point types do, as opposed
to (say) overloading the existing add, mul, icmp, etc. instructions.

> 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.

In my experience, that's not a good approach to designing an IR.  Pretty much
any representation can be made to work with enough hacks in the right places.
And nobody wants to rewrite a working end-to-end system; you just keep extending
the hacks.

> 
> 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.

Do you find that you can reliably select a saturating instruction from such a pattern?
I imagine that the tree of selects would get pretty complicated for, say, a saturating
signed multiplication.

John.

> 
> 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
> 