The Art of Picking Intel Registers (2003) | Hacker News Reader

The Art of Picking Intel Registers (2003)

swansontec.com

80 pointsnkurz27 comments

Oh this fills me with a mix of nostalgia and dread. The first time I saw a 'flat' instruction set such as MIPS and ARM, with a large file of registers that are treated the same, was really refreshing.

I'd imagine that examining an efficient stack architecture like the J1[1] would be even more refreshing. No need for register allocation and tremendous gains in code density. You lose the ability to do out-of-order execution, but in many situations independent operations can still be combined into a single clock cycle, and the CPU is still faster because it simply has less work to do.

[1] http://www.excamera.com/sphinx/fpga-j1.html

Isn't that even worse? Now, you have to reorder your instructions to make them more efficient and avoid exchange instructions.

Some stack architectures (e.g. Hobbit) use small offsets to allow addressing into the stack, which adds some of the flavor and flexibility of a register-based machine while still conceptually keeping all values on the stack.

Very cool link. Stack architectures faded a while ago, but I think most of that was just the huge divide in cpu to memory performance. I think there is a niche in parallelism for simpler, stack based CPU again.

In GCC you can actually offload the decision about which registers to choose if you are writing inline assembly code. You just specify what type of registers you need and GCC optimizes the assignments for you. Then you reference them with % notation - e.g. movd %1, %2. Imagine you provide this as an inline function in C++; all the calls for simple functions like arithmetic operations will be optimized on the spot instead of building stacks or moving some value to/from eax... It sped up my 3D software renderer more than twice! :)

You can also do the reverse. By adding __asm__("%ecx") to a variable declaration, you assign it to that register, while being able to perform C code as usual.

This usually results in degradation performance-wise, but has its uses.

If you're programming 16-bit assembly language, it's even more important to keep in mind the advantages and restrictions of each register, because you can only use BX, SI, DI, and BP for memory addressing.

Each register has its own personality and certain things it just does best. It is a little sad to see that RISC has "won" and modern CPU's have dozens or hundreds of registers which are just numbers.

How on earth is that sad? It's a great thing that we are finally leaving all that old cruft in the past!

For reasons like this I usually claim that 32-bit x86 chips have zero or at most one general purpose registers. Everything else is full of weird junk like this.

Also, there is the conceptual model of how an x86 computer works, and then how it actually works is another thing, for example I think the Sandy Bridge architecture has 160 physical integer registers, if I'm interpreting this correctly: http://www.anandtech.com/show/3922/intels-sandy-bridge-archi... .

Right, but the oddities and general paucity of the architectural registers makes it hard to actually put the large physical register file to use. Subtle differences in instruction selection and ordering can make a big difference in performance, eg. http://stackoverflow.com/questions/15349308/using-xmm0-regis...

That's an interesting example, but it doesn't have anything to do with "putting the physical register file to use". Register renaming always helps as long as your algorithm is dependency-free. It's probably one of the single best general purpose optimizations available to a modern CPU design.

The classic example of where register-poor ISAs hurt isn't about "subtle differences" at all. It's the fact that there are still only 8 (for i386) named registers, and so anything that needs to deal with a working set beyond that needs to do spill/fill to memory, and you can't "rename" memory accesses (though you can sort of cheat, as with the store forward optimization -- but that doesn't work nearly so well as renaming does).

The conventional x86 way of doing it was to spill to "the stack" and I'm told that their chips actually specially optimize that nowadays. But it's all very weird, deep magic in a lot of ways.

The only stack-specific special optimization that's done is fusing the decrement/increment of esp/rsp with the store µop. And that's done mainly since push/pop are one byte opcodes, unlike general load/store.

Everything else is general memory optimizations that apply for everything like the aforementioned store forwarding. It's still expensive if the CPU can't use them (mismatched load/store size, incorrect speculation, etc.)

That's... not really subtle. That's like pipelining 101. Which is nearly 30 years old now...

The only weird thing there is the compiler lucks out in generating a version that allows OoOE to save the programmer from themself.

It's subtle compared to how that code would have been written if the assembler had access to a hundred registers. The compiler didn't get lucky there, it got complex in order to handle these situations. For a less trivial loop body that required a few more registers, it's harder to arrange things to allow register renaming to happen - much harder than just unrolling the loop to use several sets of registers. It should be clear that it's always harder to hint to the CPU that it can use a new register than it is to just explicitly use a new register. It's the same as why SSA form is useful for compilers.

No, it got lucky because it's emitting exactly what the author wrote; there's nothing complex going on. In fact, I'm sure the author is stunting where it got smart and hoisted val1+val2+val3+val4+val5+val6+val7 outside of the loop, and it can't do anything else (or even emit the hand-written version) because it would violate C++'s aliasing rules or the non-associativitiy of floating point.

In effect, the compiler was asked to compile

    void foo(float &resVal, float &val1, float &val2, float &val3, float &val4, float &val5, float &val6, float &val7) {
        float tmp = val1+val2+val3+val4+val5+val6+val7;
        resVal += tmp;
    }

whereas the author wrote asm doing

    void foo(float resVal, float val1, float val2, float val3, float val4, float val5, float val6, float val7) {
        resVal += val1;
        resVal += val2;
        resVal += val3;
        resVal += val4;
        resVal += val5;
        resVal += val6;
        resVal += val7;
    }

Which isn't the same thing. And if the author unrolled it with a hundred registers, it would still be every bit as slow.

And it should be obvious that it's slow not because it's messing up OoOE, it's slow because it's one incredibly long dependency chain with a stall between each add, due to it depending on the result of the previous add. OoOE happens to be able to fix the programmer's mistake for the first case, which is luck because the programmer obviously didn't intend for it to do so.

But now I'm repeating myself...

The compiler was not explicitly told to use a temporary variable, and could have just as easily and legally put resVal in a register (if there had been another register available). The unconditional overwriting of a register's contents (the movsd instructions) that enable register renaming are not implied or required in any way by the high-level code. You can say that it's simple and obvious, but that's your level of experience getting in the way. The high-level code prescribes nothing but additions, and the smart compiler throws in 20% other instructions that make unnecessary memory accesses and comes out ahead due to register renaming and a sufficiently large reorder window. That's definitely much subtler than the still-largely-valid guidelines like preferring to use registers over memory, and using fewer instructions overall to be faster.

No, the compiler couldn't have kept resVal in a register because it doesn't know resVal doesn't alias with any of val1..val7. Therefore, it must store resVal each iteration, and it must load each of val1..val7 each iteration. Otherwise, it would violate the C++ standard.

Well, I'm assuming the programmer wrote it like that, because otherwise a smart compiler would have calculated val1+...+val7 before the loop and just added that precalculated value repeatedly.

Also it doesn't matter if it did keep resVal (and val1..val7) in a register, it would be every bit as fast as it is now.

Similarly, the compiler has no leeway about the order of floating point additions. If the C++ was written to have identical output as the asm, the compiler could not be faster than the asm without violating the C++ standard.

Again, OoOE plays absolutely positively no part whatsoever in making the asm slow. Neither does which values are in registers or memory.

It's slow because a chain of instructions that use the output of the previous as input cannot execute in fewer cycles than (latency)*(num instructions). Period.

It's the sort of thing that should have been written by the programmer as something like

   res += (val1+val2)+(val3+val4);
   res += (val5+val6)+(val7);

then we wouldn't be having this discussion...

"As a review, all x86-family CPU's have 8 general-purpose registers."

Having participated in the writing of an x86 code generator for a compiler, I wish to thank the author for a much-needed laugh from the above sentence.

This article is very interesting. The only thing that I would love to see on it, is an example about how, using the registers according to the original design, would lead to more compression in contrast to using the registers freely.

The author gives an example, you just have to fill in some blanks. To follow along, on Linux you can use the NASM assembler (sudo apt-get install nasm on Debian-like or Ubuntu-like systems).

Then you can copy-paste the assembly language from the article (I've changed the spacing for readability and added dummy definitions for the names so it will compile):

    ;demo1.asm
    source_address       equ 0x100
    destination_address  equ 0x200
    loop_count           equ 0x10

        mov esi, source_address
        mov edi, destination_address
        mov ecx, loop_count
    my_loop:
        lodsd
        ;Do some calculations with eax here.
        stosd
        loop my_loop

And assemble it, in your favorite shell type:

    nasm -l demo1.lst demo1.asm

Then here's my alternative implementation that uses different registers. You can no longer use LODSD, STOSD or LOOP instructions since these instructions only work if you chose the same registers as demo1.

    ;demo2.asm
    source_address       equ 0x100
    destination_address  equ 0x200
    loop_count           equ 0x10

        mov ebx, source_address
        mov edx, destination_address
        mov esi, loop_count
    my_loop:
        mov eax,[ebx]       ; these two instructions instead of stosd
        add ebx,4
        ;Do some calculations with eax here.
        mov [edx],eax       ; these two instructions instead of lodsd
        add edx,4
        dec esi             ; these two instructions instead of loop
        jnz my_loop

I get a demo1 of 24 bytes and a demo2 of 38 bytes. The demo1.lst and demo2.lst files produced show how many bytes are taken up by each instruction. (And if you get addresses in a crash dump, they can be used to track down the corresponding source code line.)

If you want to actually run these programs, nasm's default output (raw machine language instructions) cannot be used by most OS's. (In DOS, you can -- just rename to .COM. But a DOS target needs to tell NASM 'bits 16', to have it emit the proper prefixes for those new-fangled 32-bit instructions, and will crash without the DOS exit syscall, INT 0x20.) The magic incantations for standalone Linux assembly language programs are here:

http://blog.markloiseau.com/2012/04/hello-world-nasm-linux/

The .o file produced by an intermediate step of the instructions at the above link can be linked with C code (unless you use a Microsoft toolchain, in which case you have to instruct nasm to output .obj instead). Then you can call assembly language functions from C and vice versa. (Figuring out how to retrieve your function's arguments in assembly language is very interesting and will enlighten you about the implementation of high-level languages.) Most "real-world" assembly code does this: Most of the program is written in C, and only the functions that need the particular advantages of assembly language are written in it.

There's a handy appendix in the NASM manual that's good for answering questions like this. It doesn't tell you anything that isn't in the data sheet, but it's more concise (the x86 data "sheet" is, like, 5 volumes, and must be 2,500 pages).

http://www.posix.nl/linuxassembly/nasmdochtml/nasmdoca.html

From this you can see that many arithmetic and logic instructions have special encodings that use AL/AX/EAX as the destination. (You can also use the more general encoding to produce exactly the same instruction, but in more bytes.)

If you're working with AL/AX/EAX, then if you arrange for ESI and EDI to point into your source and dest buffers respectively, you can use LODS and STOS to fetch and store bytes. If your processing is working in a streaming-like fashion (and this isn't a bad idea, if you can arrange it) then you can fetch or store a bytes or dword, and bump the pointer, using one instruction that's 1 byte. Doing this with a MOV followed by an INC would be 2 instrutions and 3 bytes.

There is no short form for the [EBP] addressing mode, nor [EBP+reg], because you virtually always use fixed offsets with a base pointer. I think both of these end up as [EBP+0] or [EBP+reg+0], so you'll alwas waste an extra byte for the fixed displacement if you try to use EBP for something more general.

The rotate instructions have special encodings that take the rotate count in CL, since C is for count after all.

There's probably also a few more bits and pieces like the above, which was just what stuck in my mind from when I wrote code to generate x86 machine code directly. I just skimmed through the NASM doc to double check my memory.

I couldn't say whether using the shorter forms makes any realistic difference on real code these days, aside from the general 'fewer bytes = probably quicker' rule. But If you're trying to make EXEs that are 4K or less, as this guy seems to, I bet the little savings would add up.

Your other replies illustrated how preferring registers according to design will shorten the code; but that doesn't really address compression. If you use the instructions for their design purposes you're likely to end up with common sequences of instructions and arguments, which will compress better than if you didn't use the registers consistently. If you can compress your code so much that you have room to make it self-extracting, you get to cheat your size limit a bit.

When I saw this, I got a little freaked out. I pulled up this same page for a different reason today :-) I thought nkurz was snooping my logs :-)

At any rate, hopefully, one day soon. We will move away from the x86 and its legacy. While some people believe that architecture at this level doesn't matter... and they are mostly right... the x86 is still ugly.

I'm sure it's important for the demo scene (because the binary size is the only factor), but this is largely irrelevant for modern architectures when performance is considered.

Reply on news.ycombinator.com