Re: An unusual Performance approach using Synthetic registers

[Andy Walker <ja_walker at earthlink dot net>]

<disclaimer>  I am not the font of all knowledge and wisdom.  I can't even 
get my crystal ball to work.  Please accept my comments with this in mind. 
</disclaimer>

First: thank you for your comments.  I very much appreciate your, everyone 
else's effort to read, review, and comment on my postings.  

I think you are missing the point of Synthetic registers.  

I am not talking about optimization or code generation passes.  As far as I 
can tell, these routines are completely unaffected by the number of natural 
registers available on the target machine.  I do not know how to improve the 
quality of these two passes.  From everything that I have read, both on this 
mailing list, and from other sources, my opinion is that these two passes 
perform at World Class levels.  I doubt that I could make any significant 
improvement in either of them.

Not all architectures are created equal.  The more general purpose registers 
there are, the easier it is for the compiler to allocate registers.  
Otherwise, everyone would build single-accumulator machines and we would not 
have this discussion.  For 4 GHz machines accessing a gigabyte of real 
memory, using only six general purpose registers is analogous to draining a 
railroad car of fine dry sand through an hourglass.  It takes time.

The IBM 360/390 architecture uses 16 general purpose registers.  My 
experience from hand coding assembler in that envrionment was that 16 
registers was not quite enough.  Much better than the eight on my beloved 
PDP-11, but still not enough.  I concede that some of that may have been 
laziness on my part.  

Mr. Berlin says aspects of register allocation are N-P Complete.  I had a 
hunch this was the case.  ( N-P Complete == Programmer's Full Employment Act  
;o)  Since that is so, I expect experienced assembler programmers to be 
generally more efficient than compilers when allocating registers.  

Taking these two observations together, I estimate that a compiler would 
really need 20 to 25 registers for moderately sized programs.  

>From my point of view, the register allocator has the task of cramming 
tweny-five pounds of register into a six-pound sock.  It really needs to 
carry around twenty-five things at the same time.  Picking up one more thing 
requires laying something else down, something that will have to be picked up 
again in the future.  By the time we get down to six registers, things get to 
be pretty bad.  The things we are laying down are references.  Those are the 
things we need to tell us how to get back to the things we have to pick up.  
The task is doubled or tripled.  

The register allocator puts a great deal of effort into it, in part because 
it differentiates between registers and memory.  It assumes that all memory 
access is much more expensive than register access.

My observation is that not all memory is the same.  A limited number of 
four-byte word locations, aligned on L1 cache boundaries, can be frequently 
used.  Because they are frequently used, they remain in L1 cache.  Because 
they are in L1 cache, their access times will be similar or equal to register 
access.  Because I am using mostly modrm instructions from the x86 
instruction set, the instruction length will be similar to register to 
register instructions  ( Three bytes instead of two ).

Under these very narrow conditions, this limited number of memory locations 
perform nearly as well as registers.  Synthetic registers are pointless on a 
486.

My approach is to tell the compiler that these memory locations are really 
registers with a few special extra rules.  My hunch, and it is only a hunch, 
is that register content motion will be better handled overall, resulting in 
improved performance.  In plain english, faster throughput from less 
dithering about.  

I could easily be completely wrong, for reasons I have not considered.  

That is what makes this whole thing such an experiment.  

Andy

On Saturday 04 January 2003 08:49 am, Robert Dewar wrote:
> > What I think Diego is trying to say is, creating synthetic registers
> > for the x86 isn't going to help much, possibly not at all, because the
> > optimizer passes that could benefit already have unlimited registers
> > to work with.
>
> I would put it a different way. If "synthetic registers" help, it would
> just indicate that the optimizer and code generator is operating very
> poorly. I certainly don't have the impression that this is the case,
> at least not at the level that this naive synthetic register approach
> would help.
>
> Wouldn't it be best to take some typical kernels, look at the code
> generated by GCC, and then try by hand to see how much help SR's would be.
> I am pretty sure this will quickly discourage the approach and save a lot
> of wasted effort in modifying gcc.
>
> An approach that might really be helpful is to have the register allocator
> and scheduler understand the existence and behavior of renamed registers.
> Quite often you see gcc generated code use two registers when it could
> use one, under the illusion that this helps, when in fact it does not
> since the hardware would in any case use two registers using register
> renmaing.