bytecodealliance / bytecodealliance/wasmtime
Compact `cranelift_codegen::ir::Layout` representation?
- Dominant language
- Rust
- Stars
- 18.6k
- Forks
- 1.8k
- Avg merge
- 1d 19h
- Merged PRs (30d)
- 121
Description
The `ir::layout` module keeps track of the ordering of instructions and extended basic blocks in a function. It is currently implemented with doubly linked lists of EBBs and instructions. All program points have a sequence number so the `ProgramOrder` trait can be implemented efficiently.
This representation uses 20 bytes per EBB and 16 bytes per instruction. We should experiment with a more compact layout representation:
- Use entity maps to assign a sequence number to every EBB and every instruction.
- Keep a B+-tree of the EBBs in layout order.
- Keep a B+-tree of all the instructions in layout order.
This compact representation uses 8 bytes per EBB and 8 bytes per instruction plus a minimal overhead for the non-leaf nodes in the B+-trees.
The `Cursor` struct should probably contain a path to its position in both B+-trees which means that the standard library B-trees won't work.
Contributor guide
Assessment
This issue has not been assessed yet.