Resuming development of Synthetic Registers (really long)

Andy Walker ja_walker@sbcglobal.net
Sat Sep 18 00:00:00 GMT 2010


*Back to Synthetic Registers*

This is a request for guidance and assistance in implementing an unusual 
performance approach using Synthetic Registers.

I am modifying the x86-32 backend of GCC to add Synthetic Registers. If 
I am mistaken, this is a big waste of time. If I am correct, (meaning 
"really, really lucky") then this may provide a significant increase in 
speed for executables. Long ago, I found a description on the internet 
of someone else who tried this on a different compiler, and achieved 
speed-ups. Some increases were 148%. Unfortunately, I have not been able 
to rediscover that description.

Synthetic Registers are memory locations that are treated, and described 
to the compiler, as registers.

Each Synthetic Register is a Word of memory, defined to the compiler as 
a register. If my readings in machine architecture are correct, then for 
modern machines, L1 cache access is as fast as register access. Because 
the Synthetic Registers will be frequently accessed, they will remain in 
L1 cache, and give register-like performance. The compiler is "told" 
that the Synthetic Registers must be accessed with their own 
instructions. In reality, those special instructions are 
mostly-specified "modrm" instructions. I am using "modrm" instructions 
to minimize instruction length and to decrease complexity.

The concept was first proposed by Lal George, one of the creators of the 
IRC (Iterated Register Coalescing) algorithm for color-graphing. Quoting 
Mr. George, from the synopsis [bolding by me]

    “Thus, for the x86, the conceptual model of the architecture has
    been extended with a set of memory locations that are treated as
    registers. The net effect is one where temporaries are computed into
    memory locations and passed as arguments to functions. *The use of
    these memory locations managed in this way can be as fast as using
    registers, where the register allocation algorithm is indirectly
    taking the hardware register renaming mechanism into account*.”


SMLNJ: Intel x86 back end Compiler Controlled Memory (1999)
Lal George

Conceptually, Synthetic Registers are similar to actual registers, with 
many of the same characteristics. Clearly, this cannot include basing or 
indexing, because of the addressing modes on the x86 architecture.

Synthetic Registers are not "virtual", because they are not a simulation 
of a register, using a lot of instructions to perform a simple operation.

Synthetic Registers are not "pseudo" because they are not temporary or 
symbolic representations of real registers. Once implemented, they are 
every bit as real as the “real” registers.

Because of the x86 architecture, they may be used with many of the same 
instructions for "real" registers, with the same results. Because of the 
narrow way they are defined, they will operate as fast as "real" registers.

These days, with register-renaming, even the real registers themselves 
are somewhat ephemeral.

Synthetic Registers are an imperfect answer. They are limited to 
binary-type instructions. They cannot be used as base or index 
registers. They cannot be directly copied to memory.

The right answer was finally implemented in the 64-bit architectures – 
just implement more registers.

If the Synthetic Registers are properly defined to the compiler, the 
compiler will believe that it has more useable registers, and will use 
pre-existing optimization mechanisms for registers, without further 
changes.

The philosophy is straightforward. I believe that GCC could handle 
intermediate results more efficiently. Register based values are now 
handled very efficiently. Memory based values are handled less 
efficiently. As far as I know, there is no cost distinction between the 
first slot on the stack and the last. I believe that for long functions, 
more than a hundred lines of code, GCC compiled code spends much of its 
time recreating intermediate results again and again. This is because 
there is no place to store intermediate results, other than in the 
registers, and so the results are discarded and recreated.

Register allocation schemes, including Color-graphing, work poorly, the 
fewer registers there are available for use. Six registers are sub-optimal.

Again, Lal George: “The standard Chaitin graph coloring register 
allocation cannot be used directly for machines with few registers, as 
all temporaries wind up being spilled, making for a poor Allocation.”

I first proposed this on the GCC mailing list on Friday, December 27, 2002.

We discussed it on the GCC mailing list for two weeks, and I received a 
number of helpful emails. At the end of the two weeks, my workload 
significantly increased and I had to drop it at the time. Those who 
kindly responded were:

Daniel Berlin Kevin Handy Diego Novillo
Paolo Bonzini Dave Hudson Alexandre Oliva
Denis Chertykov Janis Johnson Toshi
Marcel Cox Chris Lattner Zack Weinberg
Robert Dewar Tom Lord
Daniel Egger James Mansion


I now have time available and want to pick up where I left off.

A search using the keywords “synthetic registers andy walker” retrieved 
all the relevant messages in the GCC archive.

My concept was original, but not novel. Chris Lattner directed me to the 
paper by Lal George.

 From Mr. GeorgeÂ’s paper, it appears that his implementation of 
Synthetic Registers was successful.

Other posters also validated the concept.

On the GCC mailing list, Dave Hudson responded with this:

        [Paolo Bonzini]
        That's not unusual. If one had, say, to write a back-end for the
        6502, one
        might think of representing the zero-page as caller-save
        registers, and hide the weeny three registers A,X,Y from the
        middle-end (using them only
        internally, or very near to this). Â…


    This strategy is exactly what the IP2k port of gcc does. We use 32
    directly addressable memory locations as our common "registers" and
    expose the two pointer and stack pointer regs. <snip>

    It's not pretty, but it does work very well.


Michael S. Zick, responding to another of my comments, said this:

    The argument I presented above is not 100% academic...

    I have actually done (in a non-compiler context) such x86
    programming, with the added decoration of making the primary
    registers 10 bytes long so that they could hold any FPU/ALU data type.


Daniel Egger said: “if you have a look at register rich architectures 
like PPC you'll see that the generated code rarely exceeds a number of 
16 used registers, most of them being used for parameters and return 
values.”

The instructions that can operate on a Synthetic Register are: MOV, ADD, 
SUB, NEG, AND, OR, XOR, ROR, ROL, ASHL, ASHR, and LSHR. In addition, a 
synthetic register may be a source for a MUL or DIVMOD. For this short 
list of instructions, a Synthetic register can be a source or 
destination, in conjunction with a register. It may also be a 
destination in conjunction with an immediate value.

My own assembler experience is from application development on IBM 
Mainframes - the 360/370/390 series. On the s/390 equipment, we had 16 
General Purpose registers, and that was half what we really needed. I 
find the thought of only 8, or really, 6 general-purpose registers being 
available for the compiler to be just ridiculous.

I intend to change the stack layout, in spite of a sage comment by 
Marcel Cox about the ABI – “any change to the stack layout that would 
lead to ABI incompatibilities would certainly not have a chance of ever 
being accepted.”

My first thought is to use the frame pointer as the base pointer for the 
Synthetic Registers.

My first step is simply to add storage on the stack for a number of 
general-purpose Synthetic Registers, but not use them.

The contiguous block of Synthetic Registers is aligned on whatever block 
boundary is used by the L1 cache. There must be real memory somewhere 
from which the L1 cache will be drawn. I am implementing it as an extra 
block of bytes in the frame. This means that every function will have 
its own block of Synthetic Registers and there will be no need to save 
or restore Synthetic Registers. Synthetic Registers will not be 
clobbered by function calls.

If the call stack is 10 calls deep, we get 10 different sets of 
Synthetic Registers. Also, a function compiled with Synthetic Registers 
can be linked to, and called from, a function compiled without Synthetic 
Registers, with no additional complexity.

Once this part is working, I want to look into varying the number of 
Synthetic Registers, depending upon the needs of the compiler for a 
particular function. I am also quite curious about the value of 
Synthetic floating-point registers.

I will set up the allocation order so that the Synthetic Registers are 
allocated before the general purpose registers. This way, 
general-purpose registers are reserved for situations where Synthetic 
Registers are not appropriate.

Initially, all of my changes will be to files: ix86.c, ix86.h, ix86.md, 
ix86-protos.h, and config.gcc. No changes to any register allocating or 
scheduling routines or files.

In ix86.h, I am declaring the first pseudo-register to be number 84.

The draft code changes that I made years ago have been lost, so I am 
starting from scratch again.

Initial question: any obvious landmines in changing the prologue and 
epilogue to stick in an additional 40 bytes on the stack?

Andy



More information about the Gcc-help mailing list