bytecodealliance / bytecodealliance/wasmtime

Compact `cranelift_codegen::ir::Layout` representation?

Open
#1,025 4 comments 0 reactions 0 assignees View on GitHub
cranelift cranelift:goal:compile-time
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.