[llvm-dev] Fixed Point Support in LLVM

Tue Aug 21 20:56:22 PDT 2018

> On Aug 21, 2018, at 6:20 PM, Leonard Chan <leonardchan at google.com> 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 agree with all of this, with the caveat that we do have to make a decision
about the definedness of the padding bit.  But I think it's okay to just assume
that all targets will follow whatever decision we make; if someone blinks and
wants the opposite rule, they get to go add an extra argument to all the intrinsics.

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

It's fine to start with intrinsics, I think.  I do think it would be better to add a new
type, but I don't want to derail your project with a political argument over it.

I *will* derail your project if necessary with an argument that these ought to be
portable intrinsics, though. :)

As for other frontends, I can only speak for Swift.  Fixed-point types are not a high
priority for Swift, just like they haven't been a high priority for Clang — it's not like
Embedded C is a brand-new specification.  But if we had a reason to add them to
Swift, I would be pretty upset as a frontend author to discover that LLVM's support
was scattered and target-specific and that my best implementation option was to
copy a ton of code from Clang.

The main downsides of not having a type are:

  - Every operation that would've been overloaded by operand type instead has
    to be parameterized.  That is, your intrinsics all have to take width and scale in
    addition to signed-ness and saturating-ness; that's a lot of parameters, which
    tends to make testing and debugging harder.

  - Constants have to be written as decimal integers, which tends to make testing
    and debugging harder.

  - Targets that want to pass fixed-point values differently from integers have to
    invent some extra way of specifying that a value is fixed-point.

So it's annoying not to have types, especially if you want special CC treatment,
but it's not the end of the world.

John.

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