aengelke

I agree; and the article seems to have also quite a few technical flaws:

- Register width: we somewhat maxed out at 512 bits, with Intel going back to 256 bits for non-server CPUs. I don't see larger widths on the horizon (even if SVE theoretically supports up to 2048 bits, I don't know any implementation with ~~>256~~ >512 bits). Larger bit widths are not beneficial for most applications and the few applications that are (e.g., some HPC codes) are nowadays served by GPUs.

- The post mentions available opcode space: while opcode space is limited, a reasonably well-designed ISA (e.g., AArch64) has enough holes for extensions. Adding new instructions doesn't require ABI changes, and while adding new registers requires some kernel changes, this is well understood at this point.

- "What is worse, software developers often have to target several SIMD generations" -- no way around this, though, unless auto-vectorization becomes substantially better. Adjusting the register width is not the big problem when porting code, making better use of available instructions is.

- "The packed SIMD paradigm is that there is a 1:1 mapping between the register width and the execution unit width" -- no. E.g., AMD's Zen 4 does double pumping, and AVX was IIRC originally designed to support this as well (although Intel went directly for 256-bit units).

- "At the same time many SIMD operations are pipelined and require several clock cycles to complete" -- well, they are pipelined, but many SIMD instructions have the same latency as their scalar counterpart.

- "Consequently, loops have to be unrolled in order to avoid stalls and keep the pipeline busy." -- loop unroll has several benefits, mostly to reduce the overhead of the loop and to avoid data dependencies between loop iterations. Larger basic blocks are better for hardware as every branch, even if predicted correctly, has a small penalty. "Loop unrolling also increases register pressure" -- it does, but code that really requires >32 registers is extremely rare, so a good instruction scheduler in the compiler can avoid spilling.

In my experience, dynamic vector sizes make code slower, because they inhibit optimizations. E.g., spilling a dynamically sized vector is like a dynamic stack allocation with a dynamic offset. I don't think SVE delivered any large benefits, both in terms of performance (there's not much hardware with SVE to begin with...) and compiler support. RISC-V pushes further into this direction, we'll see how this turns out.

I'd add code quality as a reason. I find it much easier to understand and modify code in LLVM compared to GCC. Both have a fairly steep learning curve and not too much documentation, but often I (personally) find LLVM's architecture to be more thought out and easier to understand. GCC's age shows in the code base and it feels like many concepts and optimizations are just bolted on without "required" architectural changes for a proper integration.

libgccjit is, despite its name, just another front-end for GIMPLE. The JIT-part is realized through compiling the object file to a shared library and using dlopen on this.

One big problem with libgccjit, despite its fairly bad compile-time performance, is that it's GPL-licensed and thereby makes the entire application GPL, which makes it impossible to use not just in proprietary use-cases but also in cases where incompatible licenses are involved.

> attempting to separate them, like what most if not all compilers do, results in (sometimes very) suboptimal results

Not separating them would have a big disadvantage: all register allocation decisions need to be strictly local, because information about upcoming instructions and their register constraints is not available. Even simple graph coloring algorithms give much better code than algorithms with local decisions only.

In our baseline/unoptimized compiler, we do ISel+RegAlloc(+Encoding) combined in a single step and we get lots of easily avoidable moves and spills. (These typically don't hurt performance that much on modern out-of-order CPUs with store forwarding, but substantially increase the code size.)

There was a paper about this at CGO earlier this year [1]. Correctness is a problem that is hard to solve, though; 50% accuracy might not be enough for serious use cases, especially given that the relation to the original input for manual intervention is hard to preserve.

[1]: https://arxiv.org/abs/2305.12520

Side note: Intel CPUs since Skylake and also recent AMD CPUs (since Zen 3 or so?) store a history for indirect branches. On such processors, using threaded jumps does not really improve performance anymore (I've even seen 1-2% slowdowns on some cores).

TZCNT and BSF are not completely identical even for non-zero input: BSF sets the ZF when the input is zero, TZCNT sets ZF when the output is zero (i.e., the least significant bit is set).

The behavior/penalty of 66/67 length-changing prefixes is documented in the Intel Optimization Reference Manual (3.4.2.3):

> Assembly/Compiler Coding Rule 19. (MH impact, MH generality) Favor generating code using imm8 or imm32 values instead of imm16 values.

> how they interact with the FS/GS prefixes (64/65)

For memory operations, they are ignored: 64-2e-65-3e gives 65 as segment override. (From my memory and the resulting implementation, I did some tests with hardware a few years back.)

I do need to check myself how 2e/3e on branches interact with other segment overrides, though.

> Other architectures, like [...] ARMv8, are much more consistent.

From an instruction/operation perspective, AArch64 is more clean. However, from an instruction operand and encoding perspective, AArch64 is a lot less consistent than x86. Consider the different operand types: on x86, there are a dozen register types, immediate (8/16/32/64 bits), and memory operands (always the same layout). On AArch64, there's: GP regs, incremented GP reg (MOPS extension), extended GP reg (e.g., SXTB), shifted GP reg, stack pointer, FP reg, vector register, vector register element, vector register table, vector register table element, a dozen types of memory operands, conditions, and a dozen types of immediate encodings (including the fascinating and very useful, but also very non-trivial encoding of logical immediates [1]).

AArch64 also has some register constraints: some vector operations can only encode register 0-15 or 0-7; not to mention SVE with it's "movprfx" prefix instruction that is only valid in front of a few selected instructions.

[1]: https://github.com/aengelke/disarm/blob/master/encode.c#L19-...

Thanks for the pointer to QEMU's decoder! I actually never looked at it before.

So you coded all the tables manually in C -- interesting, that's quite some effort. I opted to autogenerate the tables (and keep them as data only => smaller memory footprint) [1,2]. That's doable, because x86 encodings are mostly fairly consistent. I can also generate an encoder from it (ok, you don't need that). Re 'custom size "xh"': AVX-512 also has fourth and eighth. Also interesting that you have a separate row for "66+F2". I special case these two (CRC32, MOVBE) instructions with a flag.

I think the prefix decoding is not quite right for x86-64: 26/2e/36/3e are ignored in 64-bit mode, except for 2e/3e as branch-not-taken/taken hints and 3e as notrack. (See SDM Vol. 1 3.3.7.1 "Other segment override prefixes (CS, DS, ES, and SS) are ignored.") Also, REX prefixes that don't immediately preceed the opcode (or VEX/EVEX prefix) are ignored. Anyhow, I need to take a closer look at the decoder with more time. :-)

> For EVEX my plan is to keep the raw bits until after the opcode has been read

I came to the same conclusion that this is necessary with APX. The map+prefix+opcode combination identifies how the other fields are to be interpreted. For AVX-512, storing the last byte was sufficient, but with APX, vvvv got a second meaning.

> Nevertheless there are several cases in which the manual is wrong or doesn't say the whole story.

Yes... especially for corner cases, getting real hardware is the only reliable way to find out, how the CPU behaves.

[1]: https://github.com/aengelke/fadec/blob/master/instrs.txt [2]: https://github.com/aengelke/fadec/blob/master/decode.c

> A lot of this is done in software (microcode).

No, that's not the case, since >30 years. Microcode is only used for implementing some complex instructions (mostly system instructions). Most regular instructions (and the rest of the core) don't use microcode and their expansions into uOps are hardwired. Also the entire execution unit is hardwired.

There are typically some undocumented registers (MSRs on x86) that can control how the core behaves (e.g., kill switches for certain optimizations). These can then be changed by microcode updates.

Bonus quirk: there's BSF/BSR, for which the Intel SDM states that on zero input, the destination has an undefined value. (AMD documents that the destination is not modified in that case.) And then there's glibc, which happily uses the undocumented fact that the destination is also unmodified on Intel [1]. It took me quite some time to track down the issue in my binary translator. (There's also TZCNT/LZCNT, which is BSF/BSR encoded with F3-prefix -- which is silently ignored on older processors not supporting the extension. So the same code will behave differently on different CPUs. At least, that's documented.)

Encoding: People often complain about prefixes, but IMHO, that's by far not the worst thing. It is well known and somewhat well documented. There are worse quirks: For example, REX/VEX/EVEX.RXB extension bits are ignored when they do not apply (e.g., MMX registers); except for mask registers (k0-k7), where they trigger #UD -- also fine -- except if the register is encoded in ModRM.rm, in which case the extension bit is ignored again.

APX takes the number of quirks to a different level: the REX2 prefix can encode general-purpose registers r16-r31, but not xmm16-xmm31; the EVEX prefix has several opcode-dependent layouts; and the extension bits for a register used depend on the register type (XMM registers use X3:B3:rm and V4:X3:idx; GP registers use B4:B3:rm, X4:X3:idx). I can't give a complete list yet, I still haven't finished my APX decoder after a year...

[1]: https://sourceware.org/bugzilla/show_bug.cgi?id=31748

Nice summary! Additional changes I have planned:

- Removing per-instruction timers, which add a measurable overhead even when disabled (https://github.com/llvm/llvm-project/pull/97046)

- Splitting AsmPrinterHandler (used for unwind info) and DebugHandler (used also for per-instruction location information) to avoid two virtual function calls per instruction (https://github.com/llvm/llvm-project/pull/96785)

- Remove several maps from ELFObjectWriter, including some std::map (changed locally, need to make PR)

- Faster section allocation, remove ELF "mergeable section info" hash maps (although this is called just ~40 times per object file, it is very measurable in JIT use cases when compiling many small objects) (planned)

- X86 encoding in general; this consumes quite some time and looks very inefficient -- having written my own x86 encoder, I'm confident that there's a lot of improvement potential. (not started)

Some takeaways on a higher level -- most of these aren't really surprising, but nonetheless are very frequent problems(/patterns) in the LLVM code base:

- Maps/hash maps/sets are quite expensive when used frequently, and sometimes can be easily avoided, e.g., with a vector or, for pointer keys, a pointer dereference

- Virtual functions(/abstraction) calls comes at a cost, especially when done frequently

- raw_svector_ostream is slow, because writes are virtual function calls and don't get inlined (I previously replaced raw_svector_ostream with a SmallVector&: https://reviews.llvm.org/D145792)

- Frequent heap allocations are costly, especially with glibc's malloc

- Many small inefficiencies add up (=> many small improvements do, too)

It works and is easier to read, but there's an important catch: it is not obvious when the compiler falls back to an inefficient scalar implementation that might even be less efficient than not using SIMD at all. Example: https://godbolt.org/z/McKfxjbaj

Thanks for the blog post, it's always nice to see performance improvements in Postgres! I'm curious: how much time is spent for LLVM on some real queries and how is LLVM configured (i.e., which passes, which back-end optimization, etc.)? In our experience [1], LLVM can be reasonably fast when optimized for compile time without optimizations and the -O0 back-end pipeline, but obviously still 10-20x slower compared to other approaches.

Also, in our experience, copy-and-patch-generated code tends to be quite slow and hard to optimize (we tried some things [2; Sec. 5], but there's still quite a gap (see Fig. 3 for a database evaluation)). Do you have some numbers on the run-time slowdown compared to LLVM? Any future plans for implementing multi-tiering, so dynamically switching from the quickly compiled code to LLVM-optimized code?

[1]: https://home.in.tum.de/~engelke/pubs/2403-cgo.pdf [2]: https://home.in.tum.de/~engelke/pubs/2403-cc.pdf

It is an old idea with a new name. For example, QEMU orginally worked like this [1] and they already used relocations to patch in constants, before they later moved to TCG for higher-quality code.

[1]: https://www.usenix.org/legacy/event/usenix05/tech/freenix/fu...

The change was withdrawn to improve it for F41 [1]. There were concerns about using $PATH to find executables for v2/v3/v4, especially for containers and absolute path specifications.

[1]: https://pagure.io/fesco/issue/3151

> That way the location of the .text section becomes reachable to the running program via the section header table.

Not sure why you would want to find .text in the program, but if you do, the linker (at least ld.bfd and ld.lld do) adds the symbols __executable_start and _etext, which surround the program code. Using linker-resolved symbols is much more reliable than parsing section headers.

> In addition to that, they must also be sorted! For some weird reason

For efficiency and simplicity when loading.

Re your article:

> Unless I can figure out a way to move the program header table to the end of the file without breaking everything

This should be doable, but you need to make sure that the program headers are mapped to memory (i.e., completely covered by a PT_LOAD segment).

I do wonder why you use program headers, though: depending on your exact use case, it might be easier to link against an object file containing only data (e.g., from objcopy) and use symbols instead.

Nice visualization of the ELF headers. However, the article has a few inaccuracies:

- ELF files are used not only for executables, but also object files, shared libraries, and also coredumps. Different parts of the ELF format serve different purposes, although there is a lot of overlap.

- The program headers don't state the location of .text, but indicate the area of the file that should be mapped into memory.

- Dynamic linking doesn't require section headers. The dynamic loader (ld.so) parses the program headers for a PT_DYNAMIC entry, which refers to the .dynamic section (which in turn refers to .dynsym, .dynstr, .rela.dyn, .init_array, etc.).

- Relocation sections (what is a relocation symbol?) are required for static linking, where every section with relocations gets its own relocation section, so .text gets .rela.text. Also, in object files, sections must use relocations to refer to other sections. Executables don't need to have relocations.

- The alignment of PT_LOAD segments must be at least the page size: the kernel or loader will use mmap to map the file, so alignments smaller than the page size won't work.

- The first section table entry must be of type SHT_NULL. The magic value SHN_UNDEF (=0) is used to refer to undefined symbols, so referring to the first section in, e.g., the symbol table, is not possible.

Although not required for a minimal file, any "modern" ELF executable should have a PT_GNU_STACK program header with flags read+write, otherwise the stack will get mapped as executable memory region, thereby creating a large and often avoidable attack vector.

Dynamic linking doesn't require section headers, either, just a PT_DYNAMIC program header to refer to the .dynamic section (which in turn refers to .dynsym, .dynstr, .rela.dyn, .init_array, stc.).

> People think binary analysis is something special, it's not, just compilers.

I (conceptually) agree! But there's different sorts of compilers, and they have different requirements, which (should) materialize in the code representation. An offline C/C++ compiler has different requirements than a JIT JavaScript compiler, and so their architecture is very different. The IR should be express the relevant operations/data structures well and should easily support the analyses/transformations. If LLVM is a good fit for you, that's great. But in many cases, it's not.

I've been bitten from being warned about not writing my own IR (effort concerns), and in hindsight, it would've been the much easier way, both for low-level and high-level transformations. IMHO, people should not be afraid to roll their own IR and make it a good fit for their use case.

> one could at least use MLIR

MLIR is a nice idea (and great for selling/publishing). I find the implementation to be somewhat lacking and constraining, difficult to work with, and not particularly efficient.

> no one wants to learn your custom IR

That's a problem, but there's no silver bullet.

> allow merging them, which QEMU does, even if just at basic block level. IIRC post-SIGSEGV state is not 100% correct in QEMU

A quick and very limited testing shows that all registers and even status flags are correct in the ucontext in the signal handler. Glancing at the source code, TCG optimizations (e.g., liveness analysis) primarily apply to temporaries, but the architectural registers are always updated. That's also why QEMU is so slow (and easy to beat in papers, which very often disregard strict correctness).

Function-level lifting to LLVM gives massive performance improvements, but sacrifices correctness w.r.t. signals (synchronous and also asynchronous, unless you add a check for pending signals to every loop, or somehow else recover the state in not-too-distant time).

> [LLVM in QEMU] has already been done, but never upstreamed.

Yeah, that's a long history, and it never worked great, the architectures are too different. LLVM is great for compiling functions while QEMU compiles basic blocks, which is somewhat required for correctness. LLVM for binary translation requires longer superblocks (HQEMU) or functions (Instrew).

I don't see _correct_ binary translation with LLVM as viable anytime soon, though: every memory access can cause a synchronous signal (SIGSEGV/SIGBUS), and I'd expect recovering the full register state at the prior instruction boundary from the LLVM-compiled code to come at severe performance penalties.

> Adding an on-disk cache would also be quite useful.

I implemented a persistent cache in Instrew to work around LLVM's high compile times. Cache access is done by decoding the code-to-be-translated (very fast) and using a hash of that code for lookup. So shared libraries and even the same code in different binaries will hit the cache, regardless of their address or path name.

If translation is fast (QEMU/TCG), caching is probably not very useful, though.

> The problem with all lifters is though that even a trivial "add rax, 1" generated a lot of IL code (probably 50-100 lines in LLVM IL)

Why is this a problem? The addition is one LLVM-IR instruction (add), followed by flag computation (maybe 10-20 instrs). Dead code elimination will afterwards quickly remove unused instructions (e.g., unused flags).

> register1 += 1

I don't see how this could be beneficial, especially on x86 where you can have "mov rax, rdx; add rax, 1" and "lea rax, [rdx + 1]", which do mostly the same (the former clobbers flags). SSA removes registers and shows the semantic operations clearly.

> Rolling your own infrastructure is not a great idea IMO

For the start, I'd agree, but as soon as you want to do non-trivial things, I don't think that standard compiler IRs (e.g., LLVM) are a good way for binary analysis. (POV: been there, done that.) The time investment in fighting the existing IR quickly becomes larger than just writing a custom IR, which is not _that_ much effort. Running O2 optimizations sounds great in theory, but is often not too helpful in practice.

LLVM is clearly intended to provide a (not too large) set of semantics that can be mapped easily to different architectures. This is great for compilation, but not for the other direction, as even simple things like add-with-carry end up being multiple non-trivial instructions which aren't handled by existing optimization patterns. The same goes for vector instructions, where many patterns are encoded in the back-ends and not in the IR passes. So you end up writing custom passes fairly quickly, but still fight against an IR that doesn't allow you to express the things you'd like to have.

In the long run, a custom IR allows for a much more idiomatic code representation and more flexible analyses; not to mention that LLVM-IR is fairly heavy-weight and not particularly efficient. If I were to write another binary translator (I wrote Instrew/Rellume based on LLVM), I would definitely not choose LLVM.

I completely agree on the SMT part. I experimented with SMT, but standard data flow analysis suffice 90% of the time and are much more efficient and predictable.

Disclosure: I work in one of TUM's database groups.

From a researcher's perspective, upstream (Linux) kernel development is not attractive: it's a very time-consuming and lengthy process, often involving several iterations, which doesn't help with getting things done (i.e., PhD thesis and/or publications). Working around the kernel is much easier and, moreover, typically results in better performance, due to fewer context switches, better integration with the rest of the system, and more predictable behavior when running on other machines.

That said, some people in our group started looking into operating systems, but focus more on unikernels for cloud environments.

Userland exec was a very interesting read when I came across it some years ago; thanks for publishing it!

The technique still mostly works, but on recent glibc+Linux, you also have to unregister the rseq area before cleaning out the address space (which requires computing the address first, which is a little cumbersome). Otherwise, if the rseq area is registered but unmapped, the kernel will forcefully stop the program.

(That said, nowadays memfd_create + fexecve is likely a more robust alternative in many cases.)