Stack walking: space and time trade-offs

On most Linux platforms (except AArch32, which uses .ARM.exidx), DWARF .eh_frame is required for C++ exception handling and stack unwinding to retrieve callee-saved registers. While .eh_frame can be used for call trace recording, it is often criticized for its runtime overhead. As an alternative, developers can enable frame pointers, or adopt SFrame, a newer format designed specifically for profiling. This article examines the size overhead of enabling non-DWARF stack walking mechanisms when building several LLVM executables.

Runtime performance analysis will be added in a future update.

Stack walking mechanisms

DWARF .eh_frame: comprehensive but slower, supports additional features like C++ exception handling
Frame pointers: fast but costs a register and code size
SFrame: a new format being developed, profiling only
x86 Last Branch Records (LBR): Skylake increased the LBR stack size to 32.

Space overhead analysis

Frame pointer size impact

For most architectures, GCC defaults to -fomit-frame-pointer in -O compilation to free up a register for general use. To enable frame pointers, specify -fno-omit-frame-pointer, which reserves the frame pointer register (e.g., rbp on x86-64) and emits push/pop instructions in function prologues/epilogues.

For leaf functions (those that don't call other functions), while the frame pointer register should still be reserved for consistency, the push/pop operations are often unnecessary. Compilers provide -momit-leaf-frame-pointer (with target-specific defaults) to reduce code size.

The viability of this optimization depends on the target architecture:

On AArch64, the return address is available in the link register (X30). The immediate caller can be retrieved by inspecting X30, so -momit-leaf-frame-pointer does not compromise unwinding.
On x86-64, after the prologue instructions execute, the return address is stored at RSP plus an offset. An unwinder needs to know the stack frame size to retrieve the return address, or it must utilize DWARF information for the leaf frame and then switch to the FP chain for parent frames.

Beyond this architectural consideration, there are additional practical reasons to use -momit-leaf-frame-pointer on x86-64:

Many hand-written assembly implementations (including numerous glibc functions) don't establish frame pointers, creating gaps in the frame pointer chain anyway.
In the prologue sequence push rbp; mov rbp, rsp, after the first instruction executes, RBP does not yet reference the current stack frame. When shrink-wrapping optimizations are enabled, the instruction region where RBP still holds the old value becomes larger, increasing the window where the frame pointer is unreliable.

Given these trade-offs, three common configurations have emerged:

omitting FP: -fomit-frame-pointer -momit-leaf-frame-pointer (smallest overhead)
reserving FP, but removing FP push/pop for leaf functions: -fno-omit-frame-pointer -momit-leaf-frame-pointer (frame pointer chain omitting the leaf frame)
reserving FP: -fno-omit-frame-pointer -mno-omit-leaf-frame-pointer (complete frame pointer chain, largest overhead)

The size impact varies significantly by program.

% /tmp/exp/readelf_analyzer.rb /tmp/out/custom-{none,nonleaf,all}/bin/{llvm-mc,opt}
Filename                            |       .text size |        EH size |  VM size | VM increase
------------------------------------+------------------+----------------+----------+------------
/tmp/out/custom-none/bin/llvm-mc    |  2114687 (23.7%) |  367992 (4.1%) |  8914057 |           -
/tmp/out/custom-nonleaf/bin/llvm-mc |  2124143 (24.0%) |  301688 (3.4%) |  8856713 |       -0.6%
/tmp/out/custom-all/bin/llvm-mc     |  2149535 (24.0%) |  362408 (4.1%) |  8942729 |       +0.3%
/tmp/out/custom-none/bin/opt        | 39018511 (70.2%) | 4561112 (8.2%) | 55583965 |           -
/tmp/out/custom-nonleaf/bin/opt     | 38879897 (71.4%) | 3542288 (6.5%) | 54424789 |       -2.1%
/tmp/out/custom-all/bin/opt         | 38980905 (71.0%) | 3888624 (7.1%) | 54871285 |       -1.3%

For instance, llvm-mc is dominated by read-only data, making the relative .text percentage quite small, so frame pointer impact on the VM size is minimal. ("VM size" is a metric reported by bloaty, representing the total p_memsz size of PT_LOAD segments, excluding alignment padding.) As expected, llvm-mc grows larger as more functions set up the frame pointer chain. However, opt actually becomes smaller when -fno-omit-frame-pointer is enabled—a counterintuitive result that warrants explanation.

Without frame pointer, the compiler uses RSP-relative addressing to access stack objects. When using the register-indirect + disp8/disp32 addresing mode, RSP needs an extra SIB byte while RBP doesn't. For larger functions accessing many local variables, the savings from shorter RBP-relative encodings can outweigh the additional push rbp; mov rbp, rsp; pop rbp instructions in the prologues/epilogues.

% echo 'mov rax, [rsp+8]; mov rax, [rbp-8]' | /tmp/Rel/bin/llvm-mc -x86-asm-syntax=intel -output-asm-variant=1 -show-encoding
        mov     rax, qword ptr [rsp + 8]        # encoding: [0x48,0x8b,0x44,0x24,0x08]
        mov     rax, qword ptr [rbp - 8]        # encoding: [0x48,0x8b,0x45,0xf8]

# ModR/M byte 0x44: Mod=01 (register-indirect addressing + disp8), Reg=0 (dest reg RAX), R/M=100 (SIB byte follows)
# ModR/M byte 0x45: Mod=01 (register-indirect addressing + disp8), Reg=0 (dest reg RAX), R/M=101 (RBP)

SFrame vs .eh_frame

Oracle is advocating for SFrame adoption in Linux distributions. The SFrame implementation is handled by the assembler and linker rather than the compiler. Let's build the latest binutils-gdb to test it.

Building test program

We'll use the clang compiler from https://github.com/llvm/llvm-project/tree/release/21.x as our test program.

There are still issues related to garbage collection (object file format design issue), so I'll just disable -Wl,--gc-sections.



@@ -331,4 +331,4 @@ function(add_link_opts target_name)
         # TODO Revisit this later on z/OS.
-        set_property(TARGET ${target_name} APPEND_STRING PROPERTY
-                     LINK_FLAGS " -Wl,--gc-sections")
+        #set_property(TARGET ${target_name} APPEND_STRING PROPERTY
+        #             LINK_FLAGS " -Wl,--gc-sections")
       endif()

1
2

configure-llvm custom-sframe -DLLVM_TARGETS_TO_BUILD=host -DLLVM_ENABLE_PROJECTS='clang' -DLLVM_ENABLE_UNWIND_TABLES=on -DLLVM_ENABLE_LLD=off -DCMAKE_{EXE,SHARED}_LINKER_FLAGS=-fuse-ld=bfd -DCMAKE_C_COMPILER=$HOME/opt/gcc-15/bin/gcc -DCMAKE_CXX_COMPILER=$HOME/opt/gcc-15/bin/g++ -DCMAKE_C_FLAGS="-B$HOME/opt/binutils/bin -Wa,--gsframe" -DCMAKE_CXX_FLAGS="-B$HOME/opt/binutils/bin -Wa,--gsframe"
ninja -C /tmp/out/custom-sframe clang

% ~/Dev/bloaty/out/release/bloaty /tmp/out/custom-sframe/bin/clang
    FILE SIZE        VM SIZE
 --------------  --------------
  63.9%  88.0Mi  73.9%  88.0Mi    .text
  11.1%  15.2Mi   0.0%       0    .strtab
   7.2%  9.96Mi   8.4%  9.96Mi    .rodata
   6.4%  8.87Mi   7.5%  8.87Mi    .sframe
   5.1%  7.07Mi   5.9%  7.07Mi    .eh_frame
   2.9%  3.96Mi   0.0%       0    .symtab
   1.4%  1.98Mi   1.7%  1.98Mi    .data.rel.ro
   0.9%  1.23Mi   1.0%  1.23Mi    [LOAD #4 [R]]
   0.7%   999Ki   0.8%   999Ki    .eh_frame_hdr
   0.0%       0   0.5%   614Ki    .bss
   0.2%   294Ki   0.2%   294Ki    .data
   0.0%  23.1Ki   0.0%  23.1Ki    .rela.dyn
   0.0%  8.99Ki   0.0%  8.99Ki    .dynstr
   0.0%  8.77Ki   0.0%  8.77Ki    .dynsym
   0.0%  7.24Ki   0.0%  7.24Ki    .rela.plt
   0.0%  6.73Ki   0.0%       0    [Unmapped]
   0.0%  6.29Ki   0.0%  3.84Ki    [21 Others]
   0.0%  4.84Ki   0.0%  4.84Ki    .plt
   0.0%  3.36Ki   0.0%  3.30Ki    .init_array
   0.0%  2.50Ki   0.0%  2.50Ki    .hash
   0.0%  2.44Ki   0.0%  2.44Ki    .got.plt
 100.0%   137Mi 100.0%   119Mi    TOTAL
% /tmp/exp/eh_size.rb /tmp/out/custom-sframe/bin/clang
clang: sframe=9303875 eh_frame=7408976 eh_frame_hdr=1023004 eh=8431980 sframe/eh_frame=1.2558 sframe/eh=1.1034

To better understand the size comparison, here's the Ruby script /tmp/exp/eh_size.rb that extracts and compares section sizes:

#!/usr/bin/env ruby
file = ARGV[0]

sections = `readelf -W -S "#{file}"`.lines
  .select {|l| l.match(/^\s*\[\d+\]/) }
  .map {|l| parts = l.split; [parts[1], parts[5].to_i(16)] }
  .to_h

sframe = sections['.sframe'] || 0
eh_frame = sections['.eh_frame'] || 0
eh_frame_hdr = sections['.eh_frame_hdr'] || 0
combined = eh_frame + eh_frame_hdr

sframe_ehframe_ratio = eh_frame > 0 ? (sframe.to_f / eh_frame).round(4) : 'N/A'
sframe_eh_ratio = combined > 0 ? (sframe.to_f / combined).round(4) : 'N/A'

puts "#{File.basename(file)}: sframe=#{sframe} eh_frame=#{eh_frame} eh_frame_hdr=#{eh_frame_hdr} eh=#{combined} sframe/eh_frame=#{sframe_ehframe_ratio} sframe/eh=#{sframe_eh_ratio}"

The results show that .sframe (8.87 MiB) is approximately 10% larger than the combined size of .eh_frame and .eh_frame_hdr (7.07 + 0.99 = 8.06 MiB). While SFrame is designed for efficiency during stack walking, it carries a non-trivial space overhead compared to traditional DWARF unwind information.

SFrame vs FP

Having examined SFrame's overhead compared to .eh_frame, let's now compare the two primary approaches for non-hardware-assisted stack walking.

Frame pointer approach: Reserve FP but omit push/pop for leaf functions g++ -fno-omit-frame-pointer -momit-leaf-frame-pointer
SFrame approach: Omit FP and use SFrame metadata g++ -fomit-frame-pointer -momit-leaf-frame-pointer -Wa,--gsframe

To conduct a fair comparison, we build LLVM executables using both approaches with both Clang and GCC compilers. The following script configures and builds test binaries with each combination:

#!/bin/zsh
conf() {
  configure-llvm $@ -DCMAKE_EXE_LINKER_FLAGS='-pie -Wl,-z,pack-relative-relocs' -DLLVM_ENABLE_UNWIND_TABLES=on \
    -DCMAKE_{EXE,SHARED}_LINKER_FLAGS=-fuse-ld=bfd -DLLVM_ENABLE_LLD=off
}

clang=-fno-integrated-as
gcc=("-DCMAKE_C_COMPILER=$HOME/opt/gcc-15/bin/gcc" "-DCMAKE_CXX_COMPILER=$HOME/opt/gcc-15/bin/g++")

fp="-fno-omit-frame-pointer -momit-leaf-frame-pointer -B$HOME/opt/binutils/bin -Wa,--gsframe=no"
sframe="-fomit-frame-pointer -momit-leaf-frame-pointer -B$HOME/opt/binutils/bin -Wa,--gsframe"

conf custom-fp -DCMAKE_{C,CXX}_FLAGS="$clang $fp"
conf custom-sframe -DCMAKE_{C,CXX}_FLAGS="$clang $sframe"
conf custom-fp-gcc -DCMAKE_{C,CXX}_FLAGS="$fp" ${gcc[@]}
conf custom-sframe-gcc -DCMAKE_{C,CXX}_FLAGS="$sframe" ${gcc[@]}

for i in fp sframe fp-gcc sframe-gcc; do ninja -C /tmp/out/custom-$i llvm-mc opt; done

The results reveal interesting differences between compiler implementations:

% /tmp/exp/readelf_analyzer.rb /tmp/out/custom-{fp,sframe,fp-gcc,sframe-gcc}/bin/{llvm-mc,opt}
Filename                               |       .text size |        EH size |   .sframe size |  VM size | VM increase
---------------------------------------+------------------+----------------+----------------+----------+------------
/tmp/out/custom-fp/bin/llvm-mc         |  2124031 (23.5%) |  301136 (3.3%) |       0 (0.0%) |  9050149 |           -
/tmp/out/custom-sframe/bin/llvm-mc     |  2114383 (22.3%) |  367452 (3.9%) |  348235 (3.7%) |  9483621 |       +4.8%
/tmp/out/custom-fp-gcc/bin/llvm-mc     |  2744214 (29.2%) |  301836 (3.2%) |       0 (0.0%) |  9389677 |       +3.8%
/tmp/out/custom-sframe-gcc/bin/llvm-mc |  2705860 (27.7%) |  354292 (3.6%) |  356073 (3.6%) |  9780985 |       +8.1%
/tmp/out/custom-fp/bin/opt             | 38872825 (69.9%) | 3538408 (6.4%) |       0 (0.0%) | 55598265 |           -
/tmp/out/custom-sframe/bin/opt         | 39011167 (62.4%) | 4557012 (7.3%) | 4452908 (7.1%) | 62494509 |      +12.4%
/tmp/out/custom-fp-gcc/bin/opt         | 54654471 (78.1%) | 3631068 (5.2%) |       0 (0.0%) | 70001565 |      +25.9%
/tmp/out/custom-sframe-gcc/bin/opt     | 53644639 (70.4%) | 4857236 (6.4%) | 5263558 (6.9%) | 76205645 |      +37.1%

SFrame incurs a significant VM size increase.
GCC-built binaries are significantly larger than their Clang counterparts, probably due to more aggressive inlining or vectorization strategies.

With Clang-built binaries, the frame pointer configuration produces a smaller opt executable (55.6 MiB) compared to the SFrame configuration (62.5 MiB). This reinforces our earlier observation that RBP addressing can be more compact than RSP-relative addressing for large functions with frequent local variable accesses.

Assembly comparison reveals that functions using RBP and RSP addressing produce quite similar code.

In contrast, GCC-built binaries show the opposite trend: the frame pointer version of opt (70.0 MiB) is smaller than the SFrame version (76.2 MiB).

The generated assembly differs significantly between omit-FP and non-omit-FP builds, I have compared symbol sizes between two GCC builds.

1	nvim -d =(/tmp/Rel/bin/llvm-nm -U --size-sort /tmp/out/custom-fp-gcc/bin/llvm-mc) =(/tmp/Rel/bin/llvm-nm -U --size-sort /tmp/out/custom-sframe-gcc/bin/llvm-mc)

Many functions, such as _ZN4llvm15ELFObjectWriter24executePostLayoutBindingEv, have significant more instructions in the keep-FP build. This suggests that GCC's frame pointer code generation may not be as optimized as its default omit-FP path.

Runtime performance analysis

TODO

perf record overhead with EH

perf record overhead with FP

Summary

This article examines the space overhead of different stack walking mechanisms when building LLVM executables.

Frame pointer configurations: Enabling frame pointers (-fno-omit-frame-pointer) with leaf frame optimization (-momit-leaf-frame-pointer) can paradoxically reduce x86-64 binary size for large programs like opt. This occurs because RBP-relative addressing produces more compact encodings than RSP-relative addressing, which requires an extra SIB byte. The savings from shorter instructions can outweigh the prologue/epilogue overhead.

SFrame vs .eh_frame: For the x86-64 clang executable, SFrame metadata is approximately 10% larger than the combined size of .eh_frame and .eh_frame_hdr. Given the significant VM size overhead and the lack of clear advantages over established alternatives, I am skeptical about SFrame's viability as the future of stack walking for userspace programs. While SFrame will receive a major revision V3 in the upcoming months, it needs to achieve substantial size reductions comparable to existing compact unwinding schemes to justify its adoption over frame pointers. I hope interested folks can implement something similar to macOS's compact unwind descriptors (with x86-64 support) and OpenVMS's.

GCC's frame pointer code generation appears less optimized than its default omit-frame-pointer path, as evidenced by substantial differences in generated assembly.

Runtime performance analysis remains to be conducted to complete the trade-off evaluation.

Appendix: `configure-llvm`

This script specifies common options when configuring llvm-project: https://github.com/MaskRay/Config/blob/master/home/bin/configure-llvm

-DCMAKE_CXX_ARCHIVE_CREATE="$HOME/Stable/bin/llvm-ar qc --thin <TARGET> <OBJECTS>" -DCMAKE_CXX_ARCHIVE_FINISH=:: Use thin archives to reduce disk usage
-DLLVM_TARGETS_TO_BUILD=host: Build a single target
-DCLANG_ENABLE_OBJC_REWRITER=off -DCLANG_ENABLE_STATIC_ANALYZER=off: Disable less popular components
-DLLVM_ENABLE_PLUGINS=off -DCLANG_PLUGIN_SUPPORT=off: Disable -Wl,--export-dynamic, preventing large .dynsym and .dynstr sections

Appendix: My SFrame build

mkdir -p out/release && cd out/release
../../configure --prefix=$HOME/opt/binutils --disable-multilib
make -j $(nproc) all-ld all-binutils all-gas
make -j $(nproc) install-ld install-binutils install-gas

Appendix: `readelf_analyzer.rb`

This Ruby script invokes readelf -WSl to collect section and VM sizes.

#!/usr/bin/env ruby
def analyze_output(output)
  state = text = vm = eh_frame = eh_frame_hdr = sframe = 0

  output.each_line do |line|
    case line
    when /Section Headers:/; state = 1
    when /Program Headers:/; state = 2
    when /Section to Segment/; state = 3
    end

    parts = line.split
    if state == 1
      
      bracket_idx = parts.find_index { |p| p.match(/^\[\d+\]$/) }
      next unless bracket_idx
      name = parts[bracket_idx + 1]
      case name
      when /^\.text/; text += parts[bracket_idx + 5].to_i(16)
      when '.eh_frame'; eh_frame = parts[bracket_idx + 5].to_i(16)
      when '.eh_frame_hdr'; eh_frame_hdr = parts[bracket_idx + 5].to_i(16)
      when '.sframe'; sframe = parts[bracket_idx + 5].to_i(16)
      end
    end

    if state == 2 && parts[0] == 'LOAD'
      vm += parts[5].to_i(16)
    end
  end

  { text: text, eh: eh_frame + eh_frame_hdr, sframe: sframe, vm: vm }
end

if ARGV.empty?
  puts "Error: No files specified"
  exit 1
end


basename_groups = Hash.new {|h, k| h[k] = [] }
has_sframe = false

ARGV.each do |file|
  output = `readelf -WSl "#{file}"`
  if $?.exitstatus != 0
    puts "Error running readelf on #{file}: #{output}"
    exit 1
  end
  data = analyze_output(output)
  has_sframe ||= data[:sframe] > 0
  basename_groups[File.basename(file)] << [file, data]
end


header = ["Filename", ".text size", "EH size"]
header << ".sframe size" if has_sframe
header << "VM size" << "VM increase"
rows = [header]

basename_groups.each do |basename, files|
  base_vm = files.first[1][:vm]  

  files.each do |filename, data|
    text_pct = ((data[:text].to_f / data[:vm]) * 100).round(1)
    eh_pct = ((data[:eh].to_f / data[:vm]) * 100).round(1)

    row = [filename, "#{data[:text]} (#{text_pct}%)", "#{data[:eh]} (#{eh_pct}%)"]
    if has_sframe
      sframe_pct = ((data[:sframe].to_f / data[:vm]) * 100).round(1)
      row << "#{data[:sframe]} (#{sframe_pct}%)"
    end
    row << data[:vm].to_s

    row << if data[:vm] == base_vm
      "-"
    else
      vm_increase_pct = ((data[:vm] - base_vm).to_f / base_vm * 100).round(1)
      "+#{vm_increase_pct}%"
    end

    rows << row
  end
end


col_widths = (0...rows[0].length).map { |col| rows.map { |row| row[col].length }.max }


puts rows[0].zip(col_widths).map.with_index { |(content, width), idx|
  idx == 0 ? content.ljust(width) : content.rjust(width)
}.join(" | ")
puts col_widths.map { |width| "-" * width }.join("-+-")


rows[1..-1].each do |row|
  puts row.zip(col_widths).map.with_index { |(content, width), idx|
    idx == 0 ? content.ljust(width) : content.rjust(width)
  }.join(" | ")
end