9 ms·

X86 Register Encoding

100 points by eklitzke 10y ago

pcwalton 10y ago
LLVM doesn't actually prefer the lower registers when doing register allocation. IIRC, sunfish told me that GCC doesn't either. It would be interesting to add features that try to minimize code size to the register allocator, but no compiler I know of actually does this. Partially as a consequence of this, the REX prefixes take up a lot of space in most x86-64 instruction streams. In fact, the average size of each instruction is almost exactly 4 bytes, exactly the same as in classic 32-bit RISC architectures. (This is why I dislike it when people link to that old Linus post about how x86 is better than RISC architectures because of code size; it may have been true then, but not now.)
- mikeash 10y ago
  Wouldn't you also have to look at the average number of instructions, not just the average instruction size? x86 instructions tend to do more, too.
  - pcwalton 10y ago
    The binary sizes are also similar when I last measured. Keep in mind that (a) ARM and AArch64 have quite a few addressing modes as well; (b) ARM has things like LDMIA/STMDB and AArch64's LDP/STP that compress function prologs and epilogs; (c) more registers means you don't have to spill as much; (d) three address instructions are often more compact than a MOV plus a two address instruction, which helps with typical register allocation algorithms.
    - mikeash 10y ago
      Thanks for the info, to you and all the other replies!
  - brigade 10y ago
    Every time I've looked at a hot function across x86-64 and arm(64), x86 needs more instructions too. Really the only thing x86 does more in one instruction that compilers actually use is memory operands, but they'll readily split them if it reduces the total number of loads. Which is quite often. (probably a bad choice though with modern cores) Lea too if your arithmetic fits in it... but then that has issue restrictions... Three operand and the various conditional stuff in arm64 is worth more overall.
    - pcwalton 10y ago
      Well, to be fair, LEA does allow for more compact encoding than RISC add/shift/add if the operations actually fit the template. But it's not enough to overcome the waste elsewhere. Most of the benefit of LEA is that it's three-address rather than two and that it doesn't clobber the flags, but those are solutions to problems that RISC doesn't have in the first place. Edit: Ah well, beaten by your edit. :)
  - bonzini 10y ago
    Not necessarily. For example except for LEA, they do 2-operand arithmetic. The only thing where x86 wins hands down is addressing modes and immediate moves.
    - pklausler 10y ago
      I'll grant you immediate moves, but not addressing modes. It lacks the auto-increment/update possibilities that were in the pdp-11, vax, mc68k, and power(pc), and are great for cutting down on instruction counts in loops. (Hell, on the CDC6600, address register updates were the only way you could do loads and stores; many good ideas didn't survive into the impoverished x86 era.)
- stoklund 10y ago
  LLVM has a CostPerUse attribute on register definitions that both x86-64 and ARM's Thumb2 mode use. See http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/Target/Target.td?view=markup http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/... The greedy register allocator uses the CostPerUse hints to prefer the lower registers, but it has to balance many optimization goals at once, so it is not always obvious what is going on. For example, it will: - Defer using a callee-saved register for the first time until it is worth the cost of spilling it in the prologue. It won't create a prolog spill just to use a better register. - Try to reuse function argument and return value registers to minimize register copies around function calls. IIRC, the CostPerUse attribute gave a code size savings of around 1% on x86-64 and Thumb2. On both architectures, the effect is reduced by the fact that all register operands must be from the low register set before you can use the smaller encoding.
  - pcwalton 10y ago
    Interesting! My info was out of date then. Thanks!
- kr7 10y ago
  > In fact, the average size of each instruction is almost exactly 4 bytes I was curious about this claim so I wrote a quick and dirty perl script to test it out: vmlinuz-linux = 2.71957329365681 bash = 3.95324321387071 firefox = 3.56640365053712 geany = 3.44776119402985 gzip = 4.17925462998247 perl = 4.10894941634241 python = 3.82481751824818 tar = 3.93348845041101 thunar = 3.82471016115786 radeon_drv.so = 4.02697782644402 Seems spot on, except for the kernel. I'm not sure why that has shorter instructions on average. EDIT: I ran it on git too; average was 3.96747336803081. It seems Linus' x86 wizardry does not extend to userspace in this case.
  - eloff 10y ago
    The kernel is compiled with -Os for code size last I checked (which was long ago) so that might explain the difference.
    - a-priori 10y ago
      It's been about ten years since I did any kernel work, but last I checked Linux doesn't use most of the fancy features of the CPU to avoid trashing more registers than necessary. If you know you don't do any floating point operations, for example, you know you don't need to save/restore the floating point registers on interrupts. The same might go for things like SSE. Those instructions tend to be larger, so it may partly explain the difference in average instruction size. The same explanation would apply to why the Radeon driver has a higher average.
    - flamedoge 10y ago
      I wonder if that flag does anything at the instruction encoding level
  - Flow 10y ago
    Interesting, would you mind sharing the script or give a short overview how it works?
    - 10y ago
- eloff 10y ago
  You can get quite large code size savings by using the original 8 registers everywhere you can get away with 32bit instructions - which is quite often, since they zero the upper 32 bits. e.g. XORL eax, eax will zero 64bit rax. Compilers don't seem very good at this, but I find I can usually save 10% code size when coding assembly routines just by paying attention to instruction width and which registers are used where. With 64bit instructions it doesn't matter which registers you use, the rex prefix is used anyway.
- bertr4nd 10y ago
  HHVM's register allocator has a few tricks to minimize code size. Among other things it tends to prefer the old regs to the new x64 ones. As you might imagine code size is a significant challenge for Facebook so these kind of optimizations tended to give nice wins.
  - munificent 10y ago
    > As you might imagine code size is a significant challenge for Facebook Maybe I'm missing something obvious, but why is code size a big concern for Facebook's server code?
    - twic 10y ago
      "Because Facebook's entire code base is compiled down to a single binary executable, the company's deployment process is quite different from what you'd normally expect in a PHP environment. Rossi told me that the binary, which represents the entire Facebook application, is approximately 1.5GB in size." http://arstechnica.com/business/2012/04/exclusive-a-behind-the-scenes-look-at-facebook-release-engineering/ http://arstechnica.com/business/2012/04/exclusive-a-behind-t...
      - bertr4nd 10y ago
        It's not compiled ahead of time any more, but yeah, that gives you an idea of just how darn big the server side code is.
deleted 10y ago
[deleted]
pklausler 10y ago
The OP perpetuates the mistaken assumption that x86-64 looks as it does because it extends good ol' 32-bit x86 encodings, which one might assume still work so well that one could run 32-bit code in 64-bit mode and have it still work. Which is not the case at all. Those REX prefix bytes used to be perfectly good 32-bit x86 instructions that now simply don't work in 64-bit mode with their original encodings. So the "compatibility" between 32-bit and 64-bit modes is mythical -- the Opteron could have had a nice shiny new 64-bit programming model that was far less confusing than the dog's breakfast that is x86-64, but just didn't.
- ant6n 10y ago
  They probably wanted to re-use most of the x86-32 decoder that they had on the chip anyway. Kind of strange, nowadays, an embedded armv8 cpu will come with multiple decoders (ARM32, thumb2, AARCH64).
  - gens 10y ago
    AFAIK the reason for amd64 being what it is are intels lawyers.
    - eloff 10y ago
      That makes little sense, could you elaborate? AMD could have done anything they wanted with amd64 instruction encodings.
      - gens 10y ago
        Well, not lawyers directly. More through lack of cooperation (due to competitive mentality). http://www.agner.org/optimize/blog/read.php?i=25 http://www.agner.org/optimize/blog/read.php?i=25
        eloff 10y ago
        I don't see how that matters in this case, AMD took the lead on AMD64 and Intel had to copy them afterward. They really could have done anything they wanted. As someone else here mentioned it was probably more to re-use the existing investment in x86 decoders.
alexanderstocko 10y ago
The REX prefix: http://wiki.osdev.org/X86-64_Instruction_Encoding#REX_prefix http://wiki.osdev.org/X86-64_Instruction_Encoding#REX_prefix
stephencanon 10y ago
N.B. the "Volatile?" column is specific to the Windows calling conventions. Under the Sys V calling conventions (i.e. what the world outside of Redmond uses), RDI and RSI are volatile (and used for passing the first two integer arguments).
bogomipz 10y ago
I had a question about this statement in the artcile: "The C calling convention on x86 systems specifies that callees need to save certain registers." Practically speaking is this the prologue that that C run time - crt0.o provides automatically/implicitly?
- aji 10y ago
  no, the compiler does this when generating code for functions and function calls crt0.o is the glue between how the kernel loads a program into memory and how main() expects things to work. it does basic setup tasks that can vary between platforms, but is generally things like collecting command line arguments and setting up the stack. it will also invoke exit() if main() returns, since that's how the kernel expects the process to be destroyed
  - bogomipz 10y ago
    Thanks for the response. When you say "how the kernel loads a program into memory" I assume you are referring to ld-linux.so.2? Is that correct? I imagine then that ld-linux.so.2 calls __start in crt0.o and crt0.o jumps to main(). Is this correct?
    - cnvogel 10y ago
      http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/fs/binfmt_elf.c http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.g... load_elf_binary() maps the executable to memory, and if an elf interpreter (/lib/ld-linux.so) is specified (which it normally is) also the elf interpreter. It then jumps to the entry point of the raw binary or of the elf interpreter.
      - qb45 10y ago
        > if an elf interpreter (/lib/ld-linux.so) is specified (which it normally is) I think your "normally" means "in case of dynamically linked executables".
      - 10y ago

100 points by eklitzke 10y ago

LLVM doesn't actually prefer the lower registers when doing register allocation. IIRC, sunfish told me that GCC doesn't either. It would be interesting to add features that try to minimize code size to the register allocator, but no compiler I know of actually does this. Partially as a consequence of this, the REX prefixes take up a lot of space in most x86-64 instruction streams. In fact, the average size of each instruction is almost exactly 4 bytes, exactly the same as in classic 32-bit RISC architectures. (This is why I dislike it when people link to that old Linus post about how x86 is better than RISC architectures because of code size; it may have been true then, but not now.)

mikeash 10y ago
Wouldn't you also have to look at the average number of instructions, not just the average instruction size? x86 instructions tend to do more, too.
- pcwalton 10y ago
  The binary sizes are also similar when I last measured. Keep in mind that (a) ARM and AArch64 have quite a few addressing modes as well; (b) ARM has things like LDMIA/STMDB and AArch64's LDP/STP that compress function prologs and epilogs; (c) more registers means you don't have to spill as much; (d) three address instructions are often more compact than a MOV plus a two address instruction, which helps with typical register allocation algorithms.
  - mikeash 10y ago
    Thanks for the info, to you and all the other replies!
- brigade 10y ago
  Every time I've looked at a hot function across x86-64 and arm(64), x86 needs more instructions too. Really the only thing x86 does more in one instruction that compilers actually use is memory operands, but they'll readily split them if it reduces the total number of loads. Which is quite often. (probably a bad choice though with modern cores) Lea too if your arithmetic fits in it... but then that has issue restrictions... Three operand and the various conditional stuff in arm64 is worth more overall.
  - pcwalton 10y ago
    Well, to be fair, LEA does allow for more compact encoding than RISC add/shift/add if the operations actually fit the template. But it's not enough to overcome the waste elsewhere. Most of the benefit of LEA is that it's three-address rather than two and that it doesn't clobber the flags, but those are solutions to problems that RISC doesn't have in the first place. Edit: Ah well, beaten by your edit. :)
- bonzini 10y ago
  Not necessarily. For example except for LEA, they do 2-operand arithmetic. The only thing where x86 wins hands down is addressing modes and immediate moves.
  - pklausler 10y ago
    I'll grant you immediate moves, but not addressing modes. It lacks the auto-increment/update possibilities that were in the pdp-11, vax, mc68k, and power(pc), and are great for cutting down on instruction counts in loops. (Hell, on the CDC6600, address register updates were the only way you could do loads and stores; many good ideas didn't survive into the impoverished x86 era.)
stoklund 10y ago
LLVM has a CostPerUse attribute on register definitions that both x86-64 and ARM's Thumb2 mode use. See http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/Target/Target.td?view=markup http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/... The greedy register allocator uses the CostPerUse hints to prefer the lower registers, but it has to balance many optimization goals at once, so it is not always obvious what is going on. For example, it will: - Defer using a callee-saved register for the first time until it is worth the cost of spilling it in the prologue. It won't create a prolog spill just to use a better register. - Try to reuse function argument and return value registers to minimize register copies around function calls. IIRC, the CostPerUse attribute gave a code size savings of around 1% on x86-64 and Thumb2. On both architectures, the effect is reduced by the fact that all register operands must be from the low register set before you can use the smaller encoding.
- pcwalton 10y ago
  Interesting! My info was out of date then. Thanks!
kr7 10y ago
> In fact, the average size of each instruction is almost exactly 4 bytes I was curious about this claim so I wrote a quick and dirty perl script to test it out: vmlinuz-linux = 2.71957329365681 bash = 3.95324321387071 firefox = 3.56640365053712 geany = 3.44776119402985 gzip = 4.17925462998247 perl = 4.10894941634241 python = 3.82481751824818 tar = 3.93348845041101 thunar = 3.82471016115786 radeon_drv.so = 4.02697782644402 Seems spot on, except for the kernel. I'm not sure why that has shorter instructions on average. EDIT: I ran it on git too; average was 3.96747336803081. It seems Linus' x86 wizardry does not extend to userspace in this case.
- eloff 10y ago
  The kernel is compiled with -Os for code size last I checked (which was long ago) so that might explain the difference.
  - a-priori 10y ago
    It's been about ten years since I did any kernel work, but last I checked Linux doesn't use most of the fancy features of the CPU to avoid trashing more registers than necessary. If you know you don't do any floating point operations, for example, you know you don't need to save/restore the floating point registers on interrupts. The same might go for things like SSE. Those instructions tend to be larger, so it may partly explain the difference in average instruction size. The same explanation would apply to why the Radeon driver has a higher average.
  - flamedoge 10y ago
    I wonder if that flag does anything at the instruction encoding level
- Flow 10y ago
  Interesting, would you mind sharing the script or give a short overview how it works?
  - 10y ago
eloff 10y ago
You can get quite large code size savings by using the original 8 registers everywhere you can get away with 32bit instructions - which is quite often, since they zero the upper 32 bits. e.g. XORL eax, eax will zero 64bit rax. Compilers don't seem very good at this, but I find I can usually save 10% code size when coding assembly routines just by paying attention to instruction width and which registers are used where. With 64bit instructions it doesn't matter which registers you use, the rex prefix is used anyway.
bertr4nd 10y ago
HHVM's register allocator has a few tricks to minimize code size. Among other things it tends to prefer the old regs to the new x64 ones. As you might imagine code size is a significant challenge for Facebook so these kind of optimizations tended to give nice wins.
- munificent 10y ago
  > As you might imagine code size is a significant challenge for Facebook Maybe I'm missing something obvious, but why is code size a big concern for Facebook's server code?
  - twic 10y ago
    "Because Facebook's entire code base is compiled down to a single binary executable, the company's deployment process is quite different from what you'd normally expect in a PHP environment. Rossi told me that the binary, which represents the entire Facebook application, is approximately 1.5GB in size." http://arstechnica.com/business/2012/04/exclusive-a-behind-the-scenes-look-at-facebook-release-engineering/ http://arstechnica.com/business/2012/04/exclusive-a-behind-t...
    - bertr4nd 10y ago
      It's not compiled ahead of time any more, but yeah, that gives you an idea of just how darn big the server side code is.

deleted 10y ago

[deleted]

pklausler 10y ago

The OP perpetuates the mistaken assumption that x86-64 looks as it does because it extends good ol' 32-bit x86 encodings, which one might assume still work so well that one could run 32-bit code in 64-bit mode and have it still work. Which is not the case at all. Those REX prefix bytes used to be perfectly good 32-bit x86 instructions that now simply don't work in 64-bit mode with their original encodings. So the "compatibility" between 32-bit and 64-bit modes is mythical -- the Opteron could have had a nice shiny new 64-bit programming model that was far less confusing than the dog's breakfast that is x86-64, but just didn't.

ant6n 10y ago
They probably wanted to re-use most of the x86-32 decoder that they had on the chip anyway. Kind of strange, nowadays, an embedded armv8 cpu will come with multiple decoders (ARM32, thumb2, AARCH64).
- gens 10y ago
  AFAIK the reason for amd64 being what it is are intels lawyers.
  - eloff 10y ago
    That makes little sense, could you elaborate? AMD could have done anything they wanted with amd64 instruction encodings.
    - gens 10y ago
      Well, not lawyers directly. More through lack of cooperation (due to competitive mentality). http://www.agner.org/optimize/blog/read.php?i=25 http://www.agner.org/optimize/blog/read.php?i=25
      - eloff 10y ago
        I don't see how that matters in this case, AMD took the lead on AMD64 and Intel had to copy them afterward. They really could have done anything they wanted. As someone else here mentioned it was probably more to re-use the existing investment in x86 decoders.

alexanderstocko 10y ago

The REX prefix: http://wiki.osdev.org/X86-64_Instruction_Encoding#REX_prefix http://wiki.osdev.org/X86-64_Instruction_Encoding#REX_prefix

stephencanon 10y ago

N.B. the "Volatile?" column is specific to the Windows calling conventions. Under the Sys V calling conventions (i.e. what the world outside of Redmond uses), RDI and RSI are volatile (and used for passing the first two integer arguments).

bogomipz 10y ago

I had a question about this statement in the artcile: "The C calling convention on x86 systems specifies that callees need to save certain registers." Practically speaking is this the prologue that that C run time - crt0.o provides automatically/implicitly?

aji 10y ago
no, the compiler does this when generating code for functions and function calls crt0.o is the glue between how the kernel loads a program into memory and how main() expects things to work. it does basic setup tasks that can vary between platforms, but is generally things like collecting command line arguments and setting up the stack. it will also invoke exit() if main() returns, since that's how the kernel expects the process to be destroyed
- bogomipz 10y ago
  Thanks for the response. When you say "how the kernel loads a program into memory" I assume you are referring to ld-linux.so.2? Is that correct? I imagine then that ld-linux.so.2 calls __start in crt0.o and crt0.o jumps to main(). Is this correct?
  - cnvogel 10y ago
    http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/fs/binfmt_elf.c http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.g... load_elf_binary() maps the executable to memory, and if an elf interpreter (/lib/ld-linux.so) is specified (which it normally is) also the elf interpreter. It then jumps to the entry point of the raw binary or of the elf interpreter.
    - qb45 10y ago
      > if an elf interpreter (/lib/ld-linux.so) is specified (which it normally is) I think your "normally" means "in case of dynamically linked executables".
    - 10y ago