cranelift: Add support for BPF code generation

[oddcoder]

Feature

I need BPF back end code generator that is not a 100MB in size, cranelift looks ideal (based on AI prototypes).

BPF is small RISC style ISA that should be relatively straightforward to implement.

Benefit

I am working on a scripting language that compiles down to BPF and is meant to be stapable to production systems. I need a lightweight optimizing JIT capable of producting BPF assembly to be loaded in relatively constrained environments.

Currently the alternatives are one of the following:

A- compile down to bpf byte code and ship it. Sometimes that can be impractical when having diverse machines with diverse kernel versions.

B- Strap a full LLVM toolchain to to the script so that it compiles on target

Implementation

I have no idea yet how to do it yet. I hope you would surprise me by saying this a) exists b) is WIP and is fully resourced.

If not, AI was able to prototype an implementation via traversing IR and generating assembly. So least I know it is doable.

I read a bit about ISLE, and I am kind of familiar with term rewriting in general due to previous experience with proof tactics in coq.

I patched cranelift to expose its internals for an out of tree implementation of a backend. I will be doing my own implementation in traqilet/crates/bpf, by copying alot from the structure of existing backends and will PR the back-end bit by bit.

Alternatives

I am not aware of any reasonable alternatives.

[bjorn3]

cc #1129

[oddcoder]

If any users spring up with strong needs and contributors are present to work on this, we can always re-open the discussion.

well that settles it.

I am still doing the reading bits and exploring the code base but if there is a particular entry point you recommend let me know

[cfallin]

@oddcoder could you detail your thoughts on adapting to eBPF's restrictions, especially around control flow? At first pass, at least, I think I would come to this with a stronger opinion than the one I wrote in #1129 a few months ago: eBPF is different enough, and niche enough, and far enough from the use-cases that the full-time maintainers of Cranelift are able to devote time to, that in my opinion, it would be unlikely to be accepted. But if you can put together a convincing design that maps Cranelift's abstractions (arbitrary control flow and jumps, fixed machine registers, a stack with frames that we can manage) to the eBPF ISA, we're happy to hear more.

[oddcoder]

Ebpf restrictions are only a concern of the Linux kernel bpf loader, bound to change, and were never part of the ISA https://docs.kernel.org/bpf/standardization/instruction-set.html or its standerization efforts in ietf/rfc/9669. Code generator backend (if it ever support ebpf) would only concern itself with lowering IR to ISA, while disabling certain optimizations passes (loop unrolling comes to mind) I do not have concrete plan, I am working on this project over weekends. But roughly speaking, implementation would follow that of riscv code generator. Ebpf has core instructions with bunch of extensions (64bit, atomics). Would that make sense for an intial plan? Do you have any major concerns ? Message ID: ***@***.***>

…

[cfallin]

Code generator backend (if it ever support ebpf) would only concern itself
with lowering IR to ISA, while disabling certain optimizations passes (loop
unrolling comes to mind)

OK; without more detail on how you plan to, e.g., map register allocation, or our ABI and stackframe handling, or ... to eBPF, it's hard to say how realistic the plan is.

Note that we don't have a loop unroller, so that part of your message is not applicable.

I do not have concrete plan, I am working on this project over weekends.
But roughly speaking, implementation would follow that of riscv code
generator. Ebpf has core instructions with bunch of extensions (64bit,
atomics).

OK. You're of course welcome to work on it! Just noting my perspective and highlighting the design questions that would be good to nail down first before sinking too much time into it.