Stream: git-cranelift

Topic: cranelift / Issue #34 Compact Layout representation

GitHub (Feb 28 2020 at 23:19):

alexcrichton transferred Issue #34:

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.

Last updated: Nov 22 2024 at 17:03 UTC