Hacker News Reader

Comment by Joker_vD | Hacker News Reader

So, binary translation at instruction-level granularity? I imagine widening the scope to basic blocks would help with quality of the generated code, but I suppose 2/3 of native speed is quite good already.

View on HN

Yes, it would be more efficiant, but it will also be more costly to generate. It would also render the handling of Signal more tricky (need to always be able to go back from the RV64 address to the orignial x86_64 address in case of a SEGFAULT for example). Also, intra-block jump make this more complicated. Box64 does a limited full-block optimisation for the Flags handling and SSE/x87/MMX register attribution, but that's pretty much. Some constant propagation mecanism would be nice and could save a lot of opcode, but no worked as been done it that direction for now (maybe later, it always bother me when I look at generated code dump to see also those multiple constant assigned multiple time).

Constant propagation and also tracking of nonzero bits has been a huge performance improvement in QEMU. The latter helps a lot with x86's automated zero extension, because if you know the high 32 bits are zero you can use a 64-bit move instead of an AND.

But QEMU only does one basic block at a time without jumps so it's relatively easy to implement.

(I tested "7z b" and QEMU user mode emulation is about 30% for x86-on-x86, I'm curious to see how it fares for x86-on-RISCV but I don't have a board to test on).

That's basically how the original qemu worked. It used GCC to generate target machine code "snippets" for each source instruction, and then simply stitched them together. (Nowadays the translation is a bit more complex and works at the basic block level.)

Wild tangent.

I've got a gist of what a basic block is due to online discussions. I know it is roughly a list of instructions and that jumps are the boundaries.

But I'm looking to understand it on a more fundamental level.

I'm guessing the subject is SSA / single static assignment and compiler theory? Just wanna ask publicly if I'm on the right track, and if I'm following this discussion correctly.

It's definitely a fundamental concept of compiler theory. Wikipedia has a reasonable description: https://en.wikipedia.org/wiki/Basic_block

It's not specific to SSA, though SSA assumes it's working with basic blocks (as do a lot of compiler algorithms). And yeah, writeups of compiler theory (and compiler practice) are where to go for more detailed discussion.

The core idea I think is that control flow complicates the kinds of analysis a lot of optimisation and other compiler passes need to do; so by first breaking the input into pieces which have very restricted possible flows of control ("only entered at the top, only exited at the bottom" is the classic definition) then:

1. You can get quite a long way with optimisations that only work within a basic block, and the restriction to within-a-BB simplifies things a lot because it can entirely ignore control flow

2. Analysis that only cares about control flow can work on a graph of BBs and ignore the individual-statement/instruction details, because the BB graph captures all the detail of what can branch where

Read the book "Engineering a compiler" if you want to get a medium-hard but nicely written intro to basically all of the basics. Skip the bit about parsing, it doesn't matter for what you want to learn.

Reply on news.ycombinator.com