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. 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
A couple of thoughts here. None particularly well thought out, so please take this more as brainstorming then specific recommendations. In terms of typing, have you considered representing your fixed points as structs in IR as apposed to packed integers? I suspect - but am by no means sure - that exposing the parts to the optimizer separately may lead to better overall optimization quality. SROA is quite good at destroying small structs. In terms of ABI, how are fixed points passed as arguments and return values? This may impact your choice of IR representation. If you can get away with something simple (e.g. passed as iN, bitcast to desired types) you'll be much better off then if you have a complicated ABI. If I understand your operations, you're going to need to have the scale as an explicit parameter to your intrinsics right? If so, you're essentially going to end up with needing a family of intrinsics for each operation. You have a couple of approaches for modeling that: either constant parameters or name manging might work. Have you considered phrasing this as builtin functions as opposed to intrinsics? We have fairly decent support in TLI for conditionally available builtins where as intrinsics are generally assumed to be always supported. Phrasing your operations as a set of builtins implemented by a runtime library may allow both easier prototyping and easier per target integration. In particular, pattern matching IR to the operations would be much more natural if framed as TLI functions since we have the concept of an unsupported builtin already supported. Philip On 08/20/2018 10:59 AM, Leonard Chan via llvm-dev 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. > > 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
> 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
On 2018-08-20 21:52, Philip Reames via llvm-dev wrote:> A couple of thoughts here. None particularly well thought out, so > please take this more as brainstorming then specific recommendations. > > In terms of typing, have you considered representing your fixed points > as structs in IR as apposed to packed integers? I suspect - but am by > no means sure - that exposing the parts to the optimizer separately > may lead to better overall optimization quality. SROA is quite good > at destroying small structs.This might be an interesting idea if you're working on a C level (say, you could have structs with bitfields containing the parts of the fixed-point number), but I don't know if there's a benefit to it on IR level, since most of the operations you'd want to do on fixed-point numbers really are regular integer operations. In some basic experiments we've done with _Complex (which is represented with a struct), we find that the optimizer doesn't always do as good a job with structs as it does with just integers, even when SROA unpacks things.> > In terms of ABI, how are fixed points passed as arguments and return > values? This may impact your choice of IR representation. If you can > get away with something simple (e.g. passed as iN, bitcast to desired > types) you'll be much better off then if you have a complicated ABI.I think the discussion of ABI came up in review of one of the Clang patches; unsure what the verdict was. Most targets likely don't have a well defined ABI for fixed-point numbers, so it would be up for discussion, but I think the easiest way is just to say that fixed-point types have the same ABI as their same-sized integer counterparts. If their representation is also in the form of integers, then this is trivial.> > If I understand your operations, you're going to need to have the > scale as an explicit parameter to your intrinsics right? If so, > you're essentially going to end up with needing a family of intrinsics > for each operation. You have a couple of approaches for modeling > that: either constant parameters or name manging might work.In our implementation, the intrinsics that require a scale have one as an extra constant parameter. This is multiplication and division, and the saturating counterparts. I think that our intrinsic set would have to be extended a bit to work with the design that Leonard is working on, since we are implementing DSP-C rather than Embedded-C. Some intrinsics would have to be added (unsigned multiplication; possibly differentiating between signed and unsigned saturating addition/subtraction?) and the saturating addition/subtraction would need a scale parameter.> > Have you considered phrasing this as builtin functions as opposed to > intrinsics? We have fairly decent support in TLI for conditionally > available builtins where as intrinsics are generally assumed to be > always supported. Phrasing your operations as a set of builtins > implemented by a runtime library may allow both easier prototyping and > easier per target integration. In particular, pattern matching IR to > the operations would be much more natural if framed as TLI functions > since we have the concept of an unsupported builtin already supported.Builtins for unsupported combinations of width/scale would be interesting, but most of these operations can be expanded fairly easily, and they can be implemented in terms of integer operations anyway which already have builtins for unsupported widths/operations. Furthermore, it needs to be possible to instruction select them easily for targets with native support, so intrinsics is the simplest approach there. / Bevin
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 >
> On Aug 20, 2018, at 10:59 AM, 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.Hi Leonard, I’m sorry for the delay responding to this. Please let me +1 a few downstream comments: +1 for adding a first class type. I agree with John that this is not as bad as it might seem. This allows the core LLVM IR types (e.g. add sub etc) to be defined on these types, and for legalize to do the right thing. This makes it easier for producers of IR (e.g. clang) to handle them in a uniform way. I don’t see a downside to this. +1 to Philip’s point about getting much of an implementation in place before starting integration. This is a big enough piece of work that we should be confident in the design direction, and I don’t want to get another partial transition into the codebase that may or may not get finished. +1 to the point about figuring out the saturation situation separately from the fixed point situation. This has come up before and gets one-off solutions (e.g. in the vector space) and it would be better to have a holistic solution to this that applies everywhere - we can migrate the existing intrinsics over to a better builtin answer once it exists. In short, I’m very strongly in the camp of supporting a new builtin type. I don’t see any downside at all to it. -Chris
Hi, On 2018-08-28 07:36, Chris Lattner via llvm-dev wrote:> Hi Leonard, > > I’m sorry for the delay responding to this. Please let me +1 a few downstream comments: > > +1 for adding a first class type. I agree with John that this is not as bad as it might seem. This allows the core LLVM IR types (e.g. add sub etc) to be defined on these types, and for legalize to do the right thing. This makes it easier for producers of IR (e.g. clang) to handle them in a uniform way. I don’t see a downside to this.Assuming you meant 'operators' rather than 'types', there's an issue with that. Every line of code in LLVM today assumes that the add, sub et al. operate on integer types. Fixing that assumption sounds like quite a bit of work to me, so I think we would likely have to add new operators for all of the fixed point types. Some of those operators (like non-saturating add and sub) would essentially do the exact same thing as regular add and sub anyway, so we'd get needless duplication. Regarding legalization: depending on where we do legalization of fixed-point types/operations, it could get hairy. The type system during lowering is pretty simplistic. Fixed-point types would add multiple dimensions to the system (width, scale, possibly padding if we include that), which I think might be hard to represent efficiently in the MVT/EVT system.> +1 to Philip’s point about getting much of an implementation in place before starting integration. This is a big enough piece of work that we should be confident in the design direction, and I don’t want to get another partial transition into the codebase that may or may not get finished.So does this mean it would be implemented using integers and intrinsics first, and then moved to a new type solution? If the first solution ends up working well, would it be an unreasonable option to use it instead? / Bevin