Re: An unusual Performance approach using Synthetic registers

[Andy Walker <ja_walker at earthlink dot net>]

On Sunday 05 January 2003 08:20 am, Tom Lord wrote:
> For ja_walker (and, I'd guess this is important): that means that
> just blindly "tricking" the register allocator isn't the best way to
> do it -- because it makes more sense to store _some_ values in
> synthregs than it does to store locals and arguments in them.  So, add
> some weights somewhere or else you'll waste synthregs left and right.
> Otherwise, what you lose for locals/args (the dominant case) will
> probably exceed what you gain for other values.

We shall have to see.  I fully expect to have to rewrite the whole thing as 
soon as we get a few runs to see what it is really doing.  This is my third 
rewrite already.

The implementation is a little more complicated than "blind trickery".  But 
not much.  My fond hope is that the additional restrictions will be 
sufficient, and that the optimizer will quite happily use the Synthetic 
registers when it is prudent to do so.  If not, I may have to do some tuning 
by disparaging other alternatives, either a little, or a lot.

I have created a new register class, "k" for Synthetic.  (Obvious, no?  Not 
to me either!)  "k" class registers are not base class registers, index class 
registers, or general registers.  They are also not general operands.  
Therefore, they do not get sucked into being used for everything, and I 
minimize the code changes and checking I have to do.  Also, the optimizer and 
allocator passes get every oportunity to generate the cleanest code with the 
real restrictions in mind.  Big plus here:  we may be able to keep Reload's 
sticky fingers off the natural registers if there are enough Synthetic 
registers.  If there are enough natural registers, then register allocation 
is trivial, register coalescing is unnecessary, and spills never happen.

If Synthetic registers are used, then the hard frame pointer is required.  
Hard frame pointer is realigned onto a 32 byte boundary, and old frame 
pointer and pc are moved accordingly.  Synthetic registers are the 32 full 
word locations immediately below the hard frame pointer.  In light of Robert 
Dewar's comments about stack slot accesses through the hard frame pointer, I 
am reconsidering this. 

I have created some new predicate routines to check whether an operand is, 
for example, a general_or_synth_operand.  These are used in instruction 
predicates for instructions that might use a Synthetic register.  Appropriate 
predicates prevent Synthetic register to memory instructions, in exactly the 
same way that memory-to-memory instructions are prevented.

All Synthetic registers are mode SI.  Period.  If this does not prove out my 
concept in at least a few instances, then the concept will never work, no 
matter how many other modes I add.  If it does prove out my concept, I can 
make a rational decision about how much extra work to put into implementing 
other modes.  

The list of instructions that might operate on a Synthetic register is short: 
mov, add, sub, neg, and, or, xor, ror, rol, ashl, ashr, and lshr (sp?).  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, or it may be a destination in 
conjunction with an immediate value.

The instructions that might use a Synthetic register are almost unchanged.  
"k" registers are added as the first alternative, with the same restrictive 
syntax used for "m", memory, references.  

For register allocation, the allocation list starts with and runs through all 
the Synthetic registers before trying a general register.  

Finally, in the routine that generates the register-representative character 
string to be concatenated to the current instruction,  I intercept Synthetic 
registers and generate appropriate base-offset addresses.  I know I do not 
know exactly what I am doing here, so it will take some sorting out.  The 
formulation is clear.  The RTL is not.

I do not expect this to be enough, but it is start.

Andy