Stream: cranelift

Topic: Considering cranelift for a project but have many questions

Luiz Berti (Apr 14 2023 at 15:15):

Hello there :wave:

I've been considering Cranelift for a project but it's hard to piece together the current status of things based on GitHub alone. So I'd be thankful to get some answers to the following:

1. Incomplete support for i8 and i16?

   The support for i8 and i16 arithmetic is incomplete and use could lead to bugs

   I found this mentioned in the docs, and don't know if this is still the case, but if it is, in what ways is it incomplete and how would it break?

2. Is ISLE advanced enough for me to implement automatic symbolic differentiation of SSA-form programs within it? Can ISLE work as a standalone/generic program transformation tool, or is it too tied to the way it is currently used in Cranelift?

3. How hard would it be to implement a SPIR-V backend for Cranelift, as far as the Cranelift part is concerned? A follow up to that is: how adequate is CLIF for expressing GPU computation? (I noticed that the max amount of lanes supported is 256 for SIMD vectors)

4. Is support for f16 planned? On this same note, are there plans to do LLVM style arbitrary width integers?

5. Is there any support for LLVM style coroutine suspension and resumption? Or is the current practice to just defunctionalize everything by hand? Are there plans to add support for this?

6. There doesn’t seem to be any facilities for overflow checks and the like in the IR. Is this due to the lack of exception support? I know this is already being worked on and if the Roadmap is to be believed it should land in the first half of 2023

7. Tail-call optimization support is also being worked on by what I saw on GitHub. How is the progress on this?

Sorry about the boatload of questions, but I’d be really happy to get some answers on them.

Thanks in advance.

fitzgen (he/him) (Apr 14 2023 at 15:32):

1. there shouldn't be any miscompilations (i.e. generating incorrect code) but you may find that some operations that should work for i8/i16 will panic on lowering because we haven't implemented them for the backend yet. these are generally relatively easy to implement, so could be a great way to start contributing to cranelift if you're interested in that at all

2. ISLE is not inherently tied to cranelift at all, but also that is what we use and maintain it for, so feature requests driven by other uses (for example) likely won't get very far unless cranelift is also benefiting. but to strictly answer your question: yes it is a general, non-cranelift-specific language

3. I believe there was some initial attempts at doing this but the folks working on it pivoted away to a different approach. because SPIR-V is pretty different from a traditional ISA it wasn't really a "backend" in the way that our x64/aarch64/etc support is, so much as a CLIF-to-SPIR-V translator. should be possible. unclear to me how much work it would be.

4. it has not been discussed before

5. this is pretty unlikely to be something that cranelift itself supports. the frontend should desugar these things or introduce runtime library calls for the suspend and resume (this is the approach wasmtime takes)

6. there are various operations that check for overflow, eg https://docs.rs/cranelift-codegen/latest/cranelift_codegen/ir/trait.InstBuilder.html#method.iadd_carry and https://docs.rs/cranelift-codegen/latest/cranelift_codegen/ir/trait.InstBuilder.html#method.uadd_overflow_trap but there are probably still some operations that could have these variations but don't. if you notice anything missing, bug reports and PRs are very welcome!

7. I am working on this right now. going well. currently overhauling Wasmtime's trampolines such that tail calls will be possible (this is like 90% of the work) and then I'll start implementing the actual tail calling convention (easy and non-invasive in comparison to the trampolines overhaul)

let me know if anything isn't clear or if you have follow up questions!

Luiz Berti (Apr 14 2023 at 15:43):

Thanks for the super speedy response! (and no better source on ISLE than the main author himself too :)

Just a few, small followups (for now at least, I'll probably start having a lot more questions once I start implementing things hehe)

1. I could definitely take a look at that. Would love some pointers to the relevant places in the codebase if you have them handy;
2. Would like your opinion if doing autodiff inside ISLE is a "too insane" idea that would never work, or do you think there's a chance?

fitzgen (he/him) (Apr 14 2023 at 16:34):

I'm not the main author of ISLE; original author was @Chris Fallin, I just did the initial integration with Cranelift. at this point @Trevor Elliott and @Jamey Sharp have done a lot of work on it as well

Chris Fallin (Apr 14 2023 at 16:34):

I'll second the point about flexibility of ISLE: when we designed the language we wanted to make sure to keep the separation between the core semantics and the "Cranelift prelude" clear. We have other efforts ongoing that depend on interpreting the language in different ways (isle-veri specifically) so any leakage between abstraction layers affects us there too. All that to say, while we're unlikely to go and build a new ISLE feature just for an external request, it is aligned with our own interests to keep it general and clean :-)

Chris Fallin (Apr 14 2023 at 16:36):

I'm not so sure about auto-differentiation; I'd want to hear more about your ideas on what the language itself would need to provide there, e.g., what new primitives or what analyses are necessary. I could very much believe that introspection of the rules in some way might help (i.e., treating the rules as first-class data is the right way of going about this), but I'd also warn that the way we've written rules now is functional/value-based at the higher layers but bottoms out in a more imperative style in the "glue" to emission, so one would have to be a little careful to draw the analysis boundaries properly

Chris Fallin (Apr 14 2023 at 16:37):

(credit where credit is due: ISLE was largely inspired by @fitzgen (he/him) 's earlier work on Peepmatic, another rewriting system on CLIF)

fitzgen (he/him) (Apr 14 2023 at 16:41):

Luiz Berti said:

Thanks for the super speedy response! (and no better source on ISLE than the main author himself too :)

Just a few, small followups (for now at least, I'll probably start having a lot more questions once I start implementing things hehe)

1. I could definitely take a look at that. Would love some pointers to the relevant places in the codebase if you have them handy;
2. Would like your opinion if doing autodiff inside ISLE is a "too insane" idea that would never work, or do you think there's a chance?

for example, sadd_sat (saturating signed addition) is only defined on x64 for i8x16 and i16x8: https://github.com/bytecodealliance/wasmtime/blob/main/cranelift/codegen/src/isa/x64/lower.isle#L184-L190

it is defined to work with any integer vector type, however, so it is missing i32x4 and i64x2 implementations: https://docs.rs/cranelift-codegen/latest/cranelift_codegen/ir/trait.InstBuilder.html#method.sadd_sat

adding them would basically involve figuring out what instruction sequence they should lower to, making sure we have an MInst variant (defined in inst.isle: https://github.com/bytecodealliance/wasmtime/blob/main/cranelift/codegen/src/isa/x64/inst.isle#L8) for all those instructions, and then adding the (rule (lower ...) ...) to tie it all together

I'm not sure what you mean by "autodiff"

Luiz Berti (Apr 14 2023 at 17:09):

Chris Fallin said:

I'm not so sure about auto-differentiation; I'd want to hear more about your ideas on what the language itself would need to provide there, e.g., what new primitives or what analyses are necessary. I could very much believe that introspection of the rules in some way might help (i.e., treating the rules as first-class data is the right way of going about this), but I'd also warn that the way we've written rules now is functional/value-based at the higher layers but bottoms out in a more imperative style in the "glue" to emission, so one would have to be a little careful to draw the analysis boundaries properly

I'm not entirely sure myself on everything that goes into implementing AD as this would be my first time, but I am mostly referencing Zygote which does AD for Julia's SSA IR, and Enzyme which does this for LLVM and MLIR.

I think your point about introspection/reflection is probably on the right track though, but I guess I'll just try it out and see "if it sticks". I originally thought ISLE was a lot more tied to CLIF than it actually is, but now that I've read some more about it I see that it's quite general, and so my previous questions about it feels a bit uninformed.

Luiz Berti (Apr 14 2023 at 17:14):

fitzgen (he/him) said:

I'm not sure what you mean by "autodiff"

Automatic differentiation basically means taking the partial derivative of an arbitrary function wrt its inputs. This is the foundation of just about all ML frameworks.

About the credit thing, I guess I carried over an assumption from the Peepmatic materials I was referencing, but didn't mean to imply you were the only author. Sorry if it came across that way

Chris Fallin (Apr 14 2023 at 17:15):

It sounds to me like what you want to build is maybe more of a pass over the IR than anything to do with our rules in ISLE? We use ISLE to express (with the appropriate preludes/bindings) both CLIF-to-CLIF rewrites, in the mid-end, and CLIF-to-instruction lowerings, in the backends. But if I understand correctly, the differentiation of a program is also a program (e.g., page 5 of the Zygote paper, the del(f) operator), so you want a pass that consumes CLIF and produces CLIF where each operator is replaced with the derivative of that operator, I think

Chris Fallin (Apr 14 2023 at 17:17):

This also feels somewhat related to the CLIF interpreter and its support for abstract interpretation (since removed I think but it's still in history?) -- cc @Andrew Brown on that

Luiz Berti (Apr 14 2023 at 17:18):

Yup, I think you got it right, this would be sort of an off-to-the-side pass that generates more functions on top of the ones we already had, not a part of the main lowering pipeline.

Luiz Berti (Apr 14 2023 at 17:20):

Ohh I'm sad to hear it got removed, would definitely like that feature in the interpreter crate

Jamey Sharp (Apr 14 2023 at 17:47):

I'm a big fan of automatic differentiation. The ability to find the derivative at a point of any computable function is so cool, and much broader than its recent use in machine learning. I've implemented extended Kalman filters that way before, for example.

A CLIF-to-CLIF transformation for forward-mode AD would pair up every intermediate value with a new value representing the derivative, computed by some sequence of instructions that's selected based on the original instruction. You could certainly write ISLE rules describing, for example, how to turn imul into an application of the product rule. You'd combine that with some Rust code that walks over each instruction in the function and keeps track of how the original values map to their derivatives.

Jamey Sharp (Apr 14 2023 at 18:01):

Also, regarding overflow checking, we just merged a substantial overhaul to the instructions available for that purpose (https://github.com/bytecodealliance/wasmtime/pull/5784). That should be in the release that'll happen around May 20th, or you can use the version in git now.

Luiz Berti (Apr 14 2023 at 18:35):

Awesome stuff, will probably switch to git instead of waiting a month haha. Thank you!

scottmcm (Apr 18 2023 at 18:46):

Luiz Berti said:

1. Incomplete support for i8 and i16?

FWIW, last I asked about it I heard that everything ought to work fine, though there's always the possibility of bugs or gaps.

<https://bytecodealliance.zulipchat.com/#narrow/stream/217117-cranelift/topic/.E2.9C.94.20.60isub.60.20on.20.60I8.60/near/339779522>

So maybe that scary text should be removed :smile:

Chris Fallin (Apr 18 2023 at 19:00):

I'd be happy to review a PR if someone wants to remove the warnings, given that we haven't had issues with i8/i16 for a bit

Alexa VanHattum (Apr 18 2023 at 19:04):

@Chris Fallin opened a PR here: https://github.com/bytecodealliance/wasmtime/pull/6233

Chris Fallin (Apr 18 2023 at 19:09):

awesome, thank you!

Last updated: Nov 22 2024 at 17:03 UTC