https://maskray.me/blog/2024-04-27-clang-o0-output-branch-displacement-and-size-increase MaskRay Home Archives Presentations [github] [twitter] [ ] 2024-04-27 Clang's -O0 output: branch displacement and size increase tl;dr Clang 19 will remove the -mrelax-all default at -O0, significantly decreasing the text section size for x86. Span-dependent instructions In assembly languages, some instructions with an immediate operand can be encoded in two (or more) forms with different sizes. On x86-64, a direct JMP/JCC can be encoded either in 2 bytes with a 8-bit relative offset or 6 bytes with a 32-bit relative offset. A short jump is preferred because it takes less space. However, when the target of the jump is too far away (out of range for a 8-bit relative offset), a near jump must be used. 1 ja foo # jump short if above, 77 2 ja foo # jump near if above, 0f 87 3 .nops 126 4 foo: ret A 1978 paper by Thomas G. Szymanski ("Assembling Code for Machines with Span-Dependent Instructions") used the term "span-dependent instructions" to refer to such instructions with short and long forms. Assemblers grapple with the challenge of choosing the optimal size for these instructions, often referred to as the "branch displacement problem" since branches are the most common type. A good resource for understanding Szymanski's work is Assembling Span-Dependent Instructions. Start small and grow Popular assemblers still used today tend to favor a "start small and grow" approach, typically requiring one more pass than Szymanski's "start big and shrink" method. This approach often results in smaller code and can handle additional complexities like alignment directives. In LLVM, the MC library (Machine Code) is reponsible for assembly, disassembly, and object file formats. Within MC, "assembler relaxation" deals with span-dependent instructions. This is distinct from linker relaxation. Eli Bendersky provides a detailed explanation in a 2013 blog post and highlights an interesting behavior: For example, when compiling with -O0, the LLVM assembler simply relaxes all jumps it encounters on first sight. This allows it to put all instructions immediately into data fragments, which ensures there's much fewer fragments overall, so the assembly process is faster and consumes less memory. When -O0 is enabled and the integrated assembler is used (common by default), clangDriver passes the -mrelax-all flag to the LLVM MC library. This sets the MCRelaxAll flag in MCTargetOptions, instructing the assembler to potentially start with the long form (near) for JMP and JCC instructions on the X86 target only. Other instructions like ADD/SUB/CMP and non-x86 architectures remain unaffected. -mrelax-all tradeoff Here is an example: 1 void foo(int a) { 2 // -mrelax-all: near jump (6 bytes) 3 // -mno-relax-all or -fno-integrated-as: short jump (2 bytes) 4 if (a) bar(); 5 } The assembly (clang -S) looks like: 1 foo: # @foo 2 # %bb.0: # %entry 3 pushq %rbp 4 movq %rsp, %rbp 5 subq $16, %rsp 6 movl %edi, -4(%rbp) 7 cmpl $0, -4(%rbp) 8 je .LBB0_2 9 # %bb.1: # %if.then 10 movb $0, %al 11 callq bar@PLT 12 .LBB0_2: # %if.end 13 addq $16, %rsp 14 popq %rbp 15 retq The JE instruction assembles to either a short jump (8-bit relative offset) or near jump (32-bit relative offset). 1 # -mrelax-all 2 MCSection 3 MCDataFragment: empty 4 MCAlignFragment: alignment=4 5 MCDataFragment: instructions including JE (jump near if equal, 6 bytes) 6 7 # -mno-relax-all 8 MCSection 9 MCDataFragment: empty 10 MCAlignFragment: alignment=4 11 MCDataFragment: instructions before JE (push; mov; sub; mov; cmp) 12 MCRelaxableFragment: JE (jump short if equal, 2 bytes). This JE could be expanded, but not in this case. 13 MCDataFragment: instructions after JE (mov; call; add; pop; ret) The impact of -mrelax-all on text section size is significant, especially when there are many branch instructions. In an x86-64 release build of lld, -mrelax-all increased the .text section size by 7.9%. This translates to a 5.4% increase in VM size and a 4.6% increase in the overall file size. In a RISC-V rv64gc release build of lld, -mrelax-all increased the .text section size by 13.7%. This translates to a 9.0% increase in VM size and a 7.2% increase in the overall file size. Dean Michael Berris proposed to remove the -mrelax-all default for -O0 in 2016, but it stalled. -mrelax-all caused undesired interaction issues with RISC-V's conditional branch transforms, leading Craig Topper to remove -mrelax-all at -O0 for RISC-V recently. This actually indicated a size regression when the condition branch transform patch landed in 2023. 1 blt a1, a2, .Lfoo 2 beqz a1, .Lfoo 3 .Lfoo: 4 5 # llvm-mc -filetype=obj -triple=riscv64 -mattr=+relax,+c -mc-relax-all 6 blt a1, a2, .Lfoo # R_RISCV_BRANCH(.Lfoo), range: +-4KiB 7 c.beqz a1, .Lfoo # R_RISCV_BRANCH(.Lfoo) 8 .Lfoo: 9 # llvm-mc -filetype=obj -triple=riscv64 -mattr=+relax,+c 10 bge a1, a2, .+8 11 jal zero, .Lfoo # R_RISCV_JAL(.Lfoo), range: +-2MiB 12 c.bneq a1, .+8 13 jal zero, .Lfoo # R_RISCV_JAL(.Lfoo) While -mrelax-all might have offered slight compile time benefits in the past, the gains are negligible today. Benchmarking using stage 2 builds of Clang showed no measurable difference between -mrelax-all and -mno-relax-all. On llvm-compile-time-tracker running the llvm-test-suite/CTMark benchmark, compile time actually increased slightly by 0.62% while the text section size decreased by 4.44%. A difference for assembly at different optimisation levels would be quite surprising. GCC/GNU assembler don't exhibit similar expansion of JMP/JCC instructions even at -O0. These arguments strengthen the case for removing -mrelax-all as the default for -O0. My patch has landed and will be included in the next major release, LLVM 19.1. Understanding the compile time difference I have studied a notorious huge file, llvm/lib/Target/X86/ X86ISelLowering.cpp. Fragment count: A significant difference exists in the number of assembler fragments generated: * -mrelax-all: 89633 * -mno-relax-all: 143852 With -mrelax-all, the number of MCRelaxableFragments is substantially reduced (to zero when building Clang). This reduction likely contributes to the compile time difference. Fixed-point iteration: -mrelax-all ensures the fixed-point iteration algorithm (almost always) converges in a single iteration. In contrast, with -mno-relax-all, around 6% of sections require additional iterations. However, this difference is likely not the primary factor affecting compile time. 1 // -mrelax-all 2 1: 13919 3 2: 1 4 5 // -mno-relax-all 6 1: 13103 7 2: 793 8 3: 23 9 4: 1 Why didn't people complain about the code size increase? Because people generally care less about -O0 code size. -O0 is frequently used with -g to include debugging information. This debug information can overshadow the size increase caused by -mrelax-all. (-O1 or above sacrifices some debuggability.) In addition, not all projects can be successfully built with -O0 optimization. This is typically due to issues like very large programs or mandatory inlining behavior. For a discussion on size reduction ideas in ELF relocatable files, please check out my blog post about Light ELF. --------------------------------------------------------------------- You might also be interested in my notes about GNU assembler and LLVM integrated assembler. Share Comments * clang * llvm * x86 Older When QOI meets XZ Please enable JavaScript to view the comments powered by Disqus. Popular Tag Cloud adc ai9 algorithm asc automaton awesome bctf binary binutils bmc build system c c++ ccls cgc chroot clang codinsanity coffee script compiler compression computer security contest csv ctf data structure debug defcon desktop docker elf emacs email emoji emscripten event expect ext4 fdpic feeds firmware floating point forensics freebsd game gcc gentoo github glibc graph drawing gtk hanoi haskell hpc image inotify ipsec irc isc j javascript josephus problem jq kernel kythe ld leetcode libunwind linker linux llvm lsp m68k makefile math maze mirror ml musl mutt n-body network nginx nim nlp node.js noip notmuch npm ocaml offlineimap oi oj openwrt parallel parser generator perl powerpc presentation puzzle python qq radare2 regex regular expression reverse engineering review riscv router rtld ruby ructfe s390x sanitizer scheme search security shell ssh stringology student festival puzzle suffix array suffix automaton summary suricata telegram telegramircd terminal tls traversal tree trendmicro udev unicode usb vim vpn vte wargame web analytics webqqircd website wechat wechatircd window manager windows x86 xbindkeys xmonad xz yanshi Blogroll * BYVoid * fqj1994 * ppwwyyxx (c) 2024 MaskRay Powered by Hexo Home Archives Presentations