More compact SFrames through deduplication

[Indu Bhagat]

On 1/26/26 8:06 AM, Tatsuyuki Ishi wrote:
> I took the time to turn this into a full proposal:
> https://github.com/ishitatsuyuki/binutils/blob/sframe2cframe/libsframe/ 
> packed-table.md
> 
> This is a PoC written with lots of assist from AI, but there is also 
> a ./binutils/sframe2cframe tool
> in the tree, that takes a binary with SFrame and outputs a CFrame 
> formatted file.  When
> --chunk-dwarf is specified it also does the heuristics chunking 
> described in the proposal. The
> heuristics requires parsing .eh_frame.
> 
> Using some locally created eh_frame to SFrame converter, I gathered the 
> size numbers on
> libvulkan_radeon.so (~7MB .text) for Clang and GCC generated binaries:
> 
> - Clang fp: SFrame 394702 bytes, CFrame 146670 bytes
> - Clang no-fp: SFrame 601900 bytes, CFrame 153561 bytes
> - GCC fp: SFrame 511711 bytes, CFrame 174045 bytes
> - GCC no-fp: SFrame 824558 bytes, CFrame 398175 bytes
> 
> Deduplication performs worse on GCC, which is because it schedules 
> prologs/epilogs into regular
> instructions. That said, the packed scheme yields a net benefit.
> 
> The proposed design also puts the burden on the linker to pack up the 
> table. As long as chunking is
> done beforehand by the compiler, the linker does not need to parse the 
> FRE. It only needs to
> parse the FDE table to do the bit packing. Deduplication can be done on 
> FRE strings blindly.
> 
> Let me know about your thoughts on the trade-offs.
> 

Thanks for the well-documented POC and your proposal.

For benefit of readers and to ensure I got a grasp of your proposal, 
here are some notes (summary) from my understanding.  (BTW, Tests added 
in POC commit give a quick overview of expected CFrame for the curious 
reader).

* Design differences from SFrame V3
   Today’s SFrame V3 FDE model is conceptually simple:
     - each function has a fixed-size FDE entry,
     - the FDE gives you start PC, size, and where the FRE data lives,
     - then you parse the function’s FRE rows.  FRE data is the main 
carrier of the stack trace info (e.g., CFA offsets, stack offsets, 
register info etc).

The proposal replaces that with (CFrame):
   - bit-wise PC lookup tables (using outer_bits, inner_bits, bottom_trim),
   - an "outer table" that maps PC high bits to an inner-table buckets,
   - an "inner table" containing address boundaries and FDE indices (or 
GAP sentinels),
   - an "FDE index table" that maps logical FDE (Chunk) IDs to 
deduplicated FRE payload,
   - intensive bit-packing in the above structures. Each CFrame section 
defines the number of bits used for the specific tables above (based on 
the entropy of that section). E.g., sample output of a CFrame section:
     Bit parameters: bottom_trim=0, outer_bits=8, inner_bits=8
     Bit-packing: fde_idx=8, outer_start=10, outer_count=5, 
fre_offset=13, fre_count=5
   - Chunking a single function into multiple ranges to increase FRE 
payload reuse.  With the CHUNK_STRATEGY_CALLEE_SAVED strategy, the POC 
finds "interesting" sequences (put roughly: the stack increment/stack 
frame stable/stack decrement stubs) across functions.
   - De-duplication of these FDE chunks (stack increment/stack frame 
stable/stack decrement) across functions in a CFrame section.

PS: This is a substantial redesign to the specification, not an 
incremental refinement to SFrame V3.

* There is some clear value addition by the CFrame proposal:
   - Reduced size
   - Information lookup (using the two level index along with the FDE 
index) is not asymptotically worse for stacktracers.
   - Flexibility to add new FDE types for future needs is still 
maintained AFAICT.

* Workflow in POC: The POC parses eh_frame/debug_frame data to ascertain 
the split of a function into epilogue/body/prologue. Then deduplicates 
these "chunks" across functions.

* Miscellaneous critique points:
   - On first look, the explicit GAP sentinels make me a bit 
uncomfortable, but may be its just me. (As compared to SFrame's explicit 
data on size of function) I think it may become a problem when there is 
"sparse" layout of function data in .text* sections.
   - For a few test runs on sample libraries, I tried to compare:
     1. sframe2cframe -v --chunk-dwarf  --dump
     2. sframe2cframe -v --chunk-dwarf --chunk-strategy=none
     IIUC, #2 basically shows the benefit of bit-packing in the various 
lookup tables, and #1 shows the benefit of bit-packing + de-dup of FRE 
payloads.  Is that correct ?  If so, I #2 brings a major chunk of 
benefits as compared to #1.  Is that consistent with your findings too ?

Now, at this time, my two main concerns are:

* Binary incompatibility with SFrame V3
   As I mentioned above, this breaks binary compatibility with SFrame 
V3.  CFrame is a substantial redesign of the information layout. 
Readers of SFrame V3 will need a new decoder altogether, given the 
differences in information layout (in lookup tables, FDE index).

* Implementation Complexity in toolchains
   - Most of the unknowns/risks lie here ATM, as you point out.
   - While the compiler is likely the most natural place to identify 
semantically meaningful chunk boundaries (stack increment/stack frame 
stable/stack decrement), its the linker that is best suited to a) create 
that bit-packed, two level lookup table with FDE index and b) 
deduplicate chunks across functions.
   - Next, the linker must be able to see the mapping of chunks for each 
function/symbol to implement garbage collection, ODR needing to discard 
functions from output, etc.  Handling relocations also means its best to 
avoid the CFrame index creation until link time.
   - CFrame is not relocation friendly. The input to linker needs to be 
"relocation friendly". CFrame as is cannot be fed to the linker (the 
compact index of de-duped entries is one of the problem for linker 
input).  This means that either a distinct relocatable representation 
would be needed for ET_REL, and/or CFrame would be restricted to final 
linked outputs (ET_DYN/ET_EXEC). In either case, the toolchain contract 
does become more complicated than for current SFrame V3 IMO.
   - Although obvious, but as we can see, the above points suggest a 
newfound need for additional CFI directives as the new interface between 
compiler and assembler (to identify the chunks).

Thoughts on managing these aspects of additional work/complexity (and 
binary incompatibility with SFrame V3) ?

> Tatsuyuki Ishi
> 
>> On Nov 9, 2025, at 1:35, Tatsuyuki Ishi <ishitatsuyuki@gmail.com> wrote:
>>
>> [markdown version available at https://github.com/ishitatsuyuki/ 
>> compact-frame/blob/master/pre-proposal.md] <https://github.com/ 
>> ishitatsuyuki/compact-frame/blob/master/pre-proposal.md%5D>
>