Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

X86 Register Encoding

eklitzke.org

Post reply on HN
Print view View original

11–20 of 54 posts

Re: X86 Register Encoding

#11

Post by brigade »

mikeash wrote: post #9
pcwalton wrote: post #2

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 in…

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.

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.

Re: X86 Register Encoding

#12

Post by stoklund »

pcwalton wrote: post #2

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 in…

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/...

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.

Re: X86 Register Encoding

#13

Post by kr7 »

pcwalton wrote: post #2

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 in…

> 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.

Re: X86 Register Encoding

#14

Post by pcwalton »

brigade wrote: post #11
mikeash wrote: post #9

Earlier quoted context omitted.

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.

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 restrict…

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. :)

Re: X86 Register Encoding

#15

Post by eloff »

pcwalton wrote: post #2

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 in…

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.

Re: X86 Register Encoding

#16

Post by eloff »

kr7 wrote: post #13
pcwalton wrote: post #2

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 in…

> 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.02697782…

The kernel is compiled with -Os for code size last I checked (which was long ago) so that might explain the difference.

Re: X86 Register Encoding

#17

Post by bonzini »

mikeash wrote: post #9
pcwalton wrote: post #2

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 in…

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.

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.

Re: X86 Register Encoding

#18

Post by eloff »

gens wrote: post #7
ant6n wrote: post #6

Earlier quoted context omitted.

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).

AFAIK the reason for amd64 being what it is are intels lawyers.

That makes little sense, could you elaborate? AMD could have done anything they wanted with amd64 instruction encodings.

Re: X86 Register Encoding

#19

Post by mikeash »

pcwalton wrote: post #10
mikeash wrote: post #9

Earlier quoted context omitted.

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.

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 r…

Thanks for the info, to you and all the other replies!

Re: X86 Register Encoding

#20

Post by pcwalton »

stoklund wrote: post #12
pcwalton wrote: post #2

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 in…

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/... 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…

Interesting! My info was out of date then. Thanks!
Post reply on HN