i128 support

[sunfishcode]

Rust has an i128 type, so a rustc backend will need a way to support it. While one option would be to oblige the frontend to lower i128 into i64 operations, Cretonne already has legalization strategies for splitting integers in half, and much of this code ought to work for i128.

The tricky part is that the iconst instruction, as well as all *_imm instructions, uses imm64. One option is to just change these to Imm128. I'm inclined to do that, as it keeps i128 consistent with the other integer types. However, most users don't need i128, so it would be good to ensure that doing this doesn't add significant overhead or complexity for users that don't use it.

Another option would be to introduce an i128const instruction, and leave the *_imm variants unsupported in i128. That wouldn't impact users that don't use it, though it'd be less tidy.

[eira-fransham]

Why not have arbitrary-sized integers, like LLVM?

[sunfishcode]

The short-term answer is that Cranelift is focusing on being a codegen-oriented IR, for general-purpose CPUs, and arbitrary-sized integers aren't very relevant there.

Longer term, it depends on how important it ends up being, and whether simpler alternatives would suffice for the things we actually need to do. What's your use case?

[eira-fransham]

Ah yeah, for a codegen IR it makes a lot less sense. The code required to make it generic would be more complexity than it's worth. There are languages with arbitrary-bit-sized integers, like zig but you can easily generate IR for them using the available integers as primitives.

It might be worth requiring frontends to generate the 128-bit number emulation themselves. I don't believe that there are any x86 or ARM instructions operating on 128-bit numbers, apart from the result of x86 mulq (and maybe ARM's equivalent? I don't know ARM) which you could support by having the IR's multiplication instruction on 64-bit numbers return a pair.

[ckaran]

As a suggestion, you might want to reserve any tokens that match i[0-9]+ and u[0-9]+. If you want to expand the IR to include i128 and u128 in the future (or something less sane like i65536), you'll have the option. If you want to write code to check that people aren't using these as identifiers, that's fine, but I think just putting it in the docs will be enough (anyone that violates the docs has to deal with the consequences in the future).

[sunfishcode]

Fortunately, in our text format, user-provided identifiers use sigils, so we can add whatever type names we want without worry of them colliding :-). So the question here is just about what features Cranelift should provide, and at what levels.

[ckaran]

I'm betting I'm going to learn more about that tomorrow during your talk! 😄

Personally, I would like to see a i128 and u128 type, simply so that cranelift can directly support rust, but if that is a pain to implement, then it isn't worth it.

[programmerjake]

It might be worth requiring frontends to generate the 128-bit number emulation themselves. I don't believe that there are any x86 or ARM instructions operating on 128-bit numbers, apart from the result of x86 mulq (and maybe ARM's equivalent? I don't know ARM) which you could support by having the IR's multiplication instruction on 64-bit numbers return a pair.

x86_64 supports 128 by 64-bit divisions and remainders and 128-bit shifts as single instructions. both x86_64 and arm64 support 128-bit cmpxchg.

[gnzlbg]

@programmerjake IIRC those get the lower and higher 64-bits of each 128-bit integer passed separately, so one does not need 128-bit integers to expose those.

[sunfishcode]

For many 128-bit operations, we can make calls into compiler-rt/libgcc, which have functions like __multi3 and __divti3 for doing full 128-bit multiplication and division. For add and subtract, we can use carry/borrow flags.

The question in this issue though is about IR design. Should we make all immediates in the IR 128-bit, to support i128-bit in a uniform way with other types, or should we make i128 special?

If anyone is interested in working on this, I'm starting to think we should prefer to make i128 special. Have a dedicated i128const instruction, and make *_imm instructions unavailable in i128 -- because they'd have to get legalized back out anyway.

[gnzlbg]

The question in this issue though is about IR design. Should we make all immediates in the IR 128-bit, to support i128-bit in a uniform way with other types, or should we make i128 special?

The alternative is not supporting i128 at all. What's the advantage of exposing 128-bit integers in the IR vs not-doing so and requiring front ends to transform those to operations on 64-bit or 32-bit integers (e.g. by calling compiler-rt themselves) ?

I suppose that exposing 128-bit integers would allow more "optimizations" but IIRC cranelift does not perform these kind of optimizations yet.

Should we make all immediates in the IR 128-bit,

If Cranelift goes down this route, and one day it turns out it needs to add 256-bit integer support, would it be possible to make all immediates in the IR be 256-bit integers in a backwards compatible way?

[programmerjake]

Should we make all immediates in the IR 128-bit,

If Cranelift goes down this route, and one day it turns out it needs to add 256-bit integer support, would it be possible to make all immediates in the IR be 256-bit integers in a backwards compatible way?

One way to do that that might work is instead of switching to a plain i128, is to switch to a newtype that wraps i128 and behaves like an arbitrary precision integer except that it can't hold numbers outside the range of i128 (for now). When switching to i256, the range is then extended.