An unusual Performance approach using Synthetic registers, and a request for guidance.

An unusual Performance approach using Synthetic registers, and a request for guidance.

[Andy Walker]

I am working on a somewhat different approach for gcc for the 'x86 machines.  
My assembler experience is from application development on IBM Mainframes - 
the 360/370/390 stuff.  

I find the thought of only 8, or really, 6 general purpose registers being 
available for the compiler to be just rediculous.  On the s/390 equipment, we 
had 16 GP registers, and that was half what we really needed.  

I am modifying 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.

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 more-or-less efficiently.  
Because there is no specific or formal approach for intermediate results, 
they are not handled efficiently.  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.  

When I was a boy, a register had a physical presence.  It was as big as an 
office desk, and, with power supply, weighed as much as a car.  Now, it is a 
"state" of the machine, and one would be hard pressed to point to the exact 
spot where the register exists, no matter how good the microscope.  

A 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, or nearly 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 special 
instructions.  In reality, those special instructions are mostly-specified 
"modrm" instructions.  I am using "modrm" instructions to minimize 
instruction length and to decrease complexity. 

My first attempt is to add 32 general purpose Synthetic registers.  The 
contiguous block of Sythetic 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, aligned, block of 
128 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.  If your call stack is 10 calls deep, you get 320 
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, it may be worthwhile 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. and have done some partial coding in anticipation 
of their use.

There is an additional price for Synthetic registers.  I could not figure out 
a simple way to use the frame pointer, so I dragooned the "C" register, 
register number 2, to be used as the base register for the modrm 
instructions.  Time will tell if this is Dumb, or Dumber.  I am absolutely 
convinced there is a better way.  I just do not know yet what it is. 

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

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.  Describing the instructions to the compiler as 
register instructions when in fact data is written into the L1 cache may be 
too cute.  I fear that the scheduler will not see the difference, and the 
result will be frequent instruction stalls, something that I hoped this 
approach would reduce.

So much for the Big Talk.  Obviously, if this were all working now, I would 
not be asking for help, instead, I would be announcing where to get a copy of 
the modified code.  

I have many questions, mostly of a trivial nature, and would greatly 
appreciate any help.

		Andrew Walker

Re: An unusual Performance approach using Synthetic registers, and a request for guidance.

[Michael S. Zick]

On Friday 27 December 2002 02:27 am, Andy Walker wrote:
>
> There is an additional price for Synthetic registers.  I could not figure
> out a simple way to use the frame pointer, so I dragooned the "C" register,
> register number 2, to be used as the base register for the modrm
> instructions.  Time will tell if this is Dumb, or Dumber.  I am absolutely
> convinced there is a better way.  I just do not know yet what it is.
>
Within the x86 instruction set, the "C" (%ECX) register may not be your best 
choice.  
Not because of compiler usage of the register, but because of uses 
of the register outside of the compiler (Hand coded __asm__ ).
That is; hand coded __asm__, is hand coded to use ISA features that the 
compiler doesn't otherwise use.  Of those unused features, the %ECX register
related special portions of the ISA are frequently used.

A similar, but much weaker, argument could be made against using the 
%ESI and %EDI registers.

The %EAX and %EDX registers are out of the question (the ISA single and
double length result registers).

If you wanted to enforce the -fomit-frame-pointer option, the %EBP register
has possibilities (if you also restrict yourself to stack/heap/data in the
same address space).  But this path would probably be too restrictive for a
general implementation.

Hmm... we seem to be running out of registers...

Indeed, some (non-gnu) compilers reserve the %EBX register for internal uses.

So, I think (personal opinion here), using the %EBX register as the base 
(frame pointer) of the synthetic register frames should be your first choice.

Think of it as generating code for a load/store ISA machine with the primary
registers addressed %EBX relative.  This gives you two, double length,
secondary registers (The %EAX/%EDX pair and the %ESI/%EDI pair) with
a single length scratch register (%EAX).
That is, you would be generating code for a 64bit (split) register size with 
coding for a 32bit register size the exceptional case.
That allows you to combine your two register pairs to handle 128bit data
as another exceptional case to the 64bit (split) register size coding;
and a single 32bit scratch register (%ECX) that can be tested for zero with
a single byte instruction.

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.
That decision was driven by a desire to use the data-type conversion
features of the FPU portion of the ISA as an intregal part of the synthetic
machine.

I should note that the above was done before the FPU learned to do
vector instructions.  Which now might require a re-think of the old
plan.

Going beyond the register mapping I used departs too much from what
you are planning to be of much use; 
But my register mapping from the synthetic machine to the real hardware 
was:

Primary registers (frame): %EBX relative (a "zero address", stack machine, 
with the addition of directly addressable registers)
First secondary register: %EAX/%EDX or FPU TOS(relative) as appropriate.
Second secondary register: %ESI/%EDI or FPU TOS(relative) as appropriate.
Scratch/Counter/Test for Zero register: %ECX
I retained the ISA usage of the %EBP/%ESP register pair.
I captured the FPU stack over-run, under-run exceptions to extend its
hardware register stack into the synthetic (primary) registers (in my case,
a stack rather than a fixed number of synthetic registers.
Considering the FPU/ALU instruction set as a whole, I subset it to those
instructions that worked directly on the actual hardware mappings.

Mike

Re: An unusual Performance approach using Synthetic registers, and a request for guidance.

[Michael S. Zick]

On Friday 27 December 2002 10:09 am, Michael S. Zick wrote:
>
> Think of it as generating code for a load/store ISA machine with the
> primary registers addressed %EBX relative.  This gives you two, double
> length, secondary registers (The %EAX/%EDX pair and the %ESI/%EDI pair)
> with a single length scratch register (%EAX).
Thats: %ECX - - - - - - - - - - - - - ^ ^ ^

My proof-reader is on vacation this month.

Mike

Re: An unusual Performance approach using Synthetic registers, and a request for guidance.

[Alexandre Oliva]

On Dec 27, 2002, "Michael S. Zick" <mszick@goquest.com> wrote:

> So, I think (personal opinion here), using the %EBX register as the base 
> (frame pointer) of the synthetic register frames should be your first choice.

'cept %EBX is used as the PIC base register, and you can't really
remap that to a virtual register unless you change PLT entries.

-- 
Alexandre Oliva   Enjoy Guarana', see http://www.ic.unicamp.br/~oliva/
Red Hat GCC Developer                 aoliva@{redhat.com, gcc.gnu.org}
CS PhD student at IC-Unicamp        oliva@{lsd.ic.unicamp.br, gnu.org}
Free Software Evangelist                Professional serial bug killer

Re: An unusual Performance approach using Synthetic registers, and a request for guidance.

[Michael S. Zick]

On Friday 27 December 2002 10:07 pm, Alexandre Oliva wrote:
> On Dec 27, 2002, "Michael S. Zick" <mszick@goquest.com> wrote:
> > So, I think (personal opinion here), using the %EBX register as the base
> > (frame pointer) of the synthetic register frames should be your first
> > choice.
>
> 'cept %EBX is used as the PIC base register, and you can't really
> remap that to a virtual register unless you change PLT entries.
>
Indeed, that could well present a technical challenge.
Depends on how the question behind the project is approached.

For the general question:
"If a complex instruction set machine had as many registers as
a RISC machine, what..."

I see two approachs to investigating this sort of question;

1) Modify the compiler to support, in general, Synthetic Register Arrays.
Wherein one could/would butt heads with any and all current design 
decisions for a particular port....

2) Do a "new port" to a Synthetic Machine that 99% maps to real hardware,
leaving the compiler internals untouched.
You get to make your own design decisions that way and perhaps learn
if path (1) above is worth doing.

Mike

Re: An unusual Performance approach using Synthetic registers, and a request for guidance.

[Andy Walker]

Thank you for your comments.

On Friday 27 December 2002 10:09 am, Michael S. Zick wrote:

<snip>

> Within the x86 instruction set, the "C" (%ECX) register may not be your
> best choice.
> Not because of compiler usage of the register, but because of uses
> of the register outside of the compiler (Hand coded __asm__ ).
> That is; hand coded __asm__, is hand coded to use ISA features that the
> compiler doesn't otherwise use.  Of those unused features, the %ECX
> register related special portions of the ISA are frequently used.

I agree that there is a great deal of hand coded assembler that uses the ecx 
register.  If I can figure out how, I will use the ebp register and make it 
do double duty.  

> A similar, but much weaker, argument could be made against using the
> %ESI and %EDI registers.

Registers esi and edi are used in gcc/i386 for loop control in memcpy.  If I 
use one of them for the Synthetic base register, I have to find another real 
general purpose register to use for memcopy.  

> The %EAX and %EDX registers are out of the question (the ISA single and
> double length result registers).

Yes.

> If you wanted to enforce the -fomit-frame-pointer option, the %EBP register
> has possibilities (if you also restrict yourself to stack/heap/data in the
> same address space).  But this path would probably be too restrictive for a
> general implementation.  

Why would this be too restrictive?

> Hmm... we seem to be running out of registers...

Yes.

<snip>
> So, I think (personal opinion here), using the %EBX register as the base
> (frame pointer) of the synthetic register frames should be your first
> choice.

It was.

> Think of it as generating code for a load/store ISA machine with the
> primary registers addressed %EBX relative.  This gives you two, double
> length, secondary registers (The %EAX/%EDX pair and the %ESI/%EDI pair)
> with a single length scratch register (%EAX).
> That is, you would be generating code for a 64bit (split) register size
> with coding for a 32bit register size the exceptional case.
> That allows you to combine your two register pairs to handle 128bit data
> as another exceptional case to the 64bit (split) register size coding;
> and a single 32bit scratch register (%ECX) that can be tested for zero with
> a single byte instruction.
>
> 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.

Neat!

> That decision was driven by a desire to use the data-type conversion
> features of the FPU portion of the ISA as an intregal part of the synthetic
> machine.
>
> I should note that the above was done before the FPU learned to do
> vector instructions.  Which now might require a re-think of the old
> plan.
>
> Going beyond the register mapping I used departs too much from what
> you are planning to be of much use;
> But my register mapping from the synthetic machine to the real hardware
> was:
>
> Primary registers (frame): %EBX relative (a "zero address", stack machine,
> with the addition of directly addressable registers)
> First secondary register: %EAX/%EDX or FPU TOS(relative) as appropriate.
> Second secondary register: %ESI/%EDI or FPU TOS(relative) as appropriate.
> Scratch/Counter/Test for Zero register: %ECX
> I retained the ISA usage of the %EBP/%ESP register pair.
> I captured the FPU stack over-run, under-run exceptions to extend its
> hardware register stack into the synthetic (primary) registers (in my case,
> a stack rather than a fixed number of synthetic registers.

Interesting.  Given the x86 limitation of only doing fpu comparisons to 
stack-top values, I bet this was pretty efficient.

> Considering the FPU/ALU instruction set as a whole, I subset it to those
> instructions that worked directly on the actual hardware mappings.
>
> Mike

Re: An unusual Performance approach using Synthetic registers, and a request for guidance.

[Andy Walker]

On Friday 27 December 2002 10:07 pm, Alexandre Oliva wrote:
> On Dec 27, 2002, "Michael S. Zick" <mszick@goquest.com> wrote:
> > So, I think (personal opinion here), using the %EBX register as the base
> > (frame pointer) of the synthetic register frames should be your first
> > choice.
>
> 'cept %EBX is used as the PIC base register, and you can't really
> remap that to a virtual register unless you change PLT entries.

Thank you, Alexandre.  

This is why I changed my mind and used ecx instead of ebx.

Andy

Re: An unusual Performance approach using Synthetic registers, and a request for guidance.

[Andy Walker]

On Saturday 28 December 2002 07:54 am, Michael S. Zick wrote:

<snip>

> For the general question:
> "If a complex instruction set machine had as many registers as
> a RISC machine, what..."
>
> I see two approachs to investigating this sort of question;
>
> 1) Modify the compiler to support, in general, Synthetic Register Arrays.
> Wherein one could/would butt heads with any and all current design
> decisions for a particular port....

My current approach.  

> 2) Do a "new port" to a Synthetic Machine that 99% maps to real hardware,
> leaving the compiler internals untouched.
> You get to make your own design decisions that way and perhaps learn
> if path (1) above is worth doing.
> Mike

If what I am doing gets too complicated, I will keep your suggestion in mind. 
 The current ix86 machine description file alone has about ten thousand lines 
in it.  That is a lot to replace.

Andy

Re: An unusual Performance approach using Synthetic registers, and a request for guidance.

[Andy Walker]

Yes, I agree.  Thank you.

Andy

On Sunday 29 December 2002 03:47 am, Bonzini wrote:
> > Orthogonality?  I am sorry.  I do not understand.  Could you be a bit
> > more descriptive?
>
> The lack of memory-to-memory move instructions, for example.  Synthetic
> registers would have to be moved inside the core to do arithmetic on them.
> It's already a problem not to have three-operand math, synthetic registers
> would make the x86 basically an accumulator-based chip (move from reg to
> accumulator, sum accumulator to reg) and also limit the ability to use LEA
> to do arithmetics.
>
> Paolo

Re: An unusual Performance approach using Synthetic registers, and a request for guidance.

[Bonzini]

> Orthogonality?  I am sorry.  I do not understand.  Could you be a bit more
> descriptive?

The lack of memory-to-memory move instructions, for example.  Synthetic
registers would have to be moved inside the core to do arithmetic on them.
It's already a problem not to have three-operand math, synthetic registers
would make the x86 basically an accumulator-based chip (move from reg to
accumulator, sum accumulator to reg) and also limit the ability to use LEA
to do arithmetics.

Paolo

Re: An unusual Performance approach using Synthetic registers, and a request for guidance.

[Andy Walker]

On Friday 27 December 2002 03:25 pm, Dave Hudson wrote:

<snip>

>
> 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.  We completely hide the
> accumulator register W and the partial multiply result MULH.  All of our
> normal insn patterns start off not understanding anything about the
> hidden regs and then in the machine-dependent reorg we split insn
> patterns into ones that explicitly use the previously hidden regs and
> run a series of processor-specific passes to eliminate any redundancy.
>
> It's not pretty, but it does work very well.

Then this approach is not completely insane.  Thank you.

Andy

>
> Regards,
> Dave

Re: An unusual Performance approach using Synthetic registers, and a request for guidance.

[Andy Walker]

Thank you for your comments.

On Friday 27 December 2002 05:54 am, Bonzini wrote:

<snip>

> The only
> problem might be in the lack of orthogonality in the x86 instruction set.

Orthogonality?  I am sorry.  I do not understand.  Could you be a bit more 
descriptive?

> Go ahead, and good luck!
>
> Paolo

Re: An unusual Performance approach using Synthetic registers, and a request for guidance.

[Dave Hudson]

Hi Paolo,

Bonzini wrote:
> 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).  I also hope that because of the good L1
> coherency of the stack, this might pay well on the x86 as well.  The only
> problem might be in the lack of orthogonality in the x86 instruction set.

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.  We completely hide the 
accumulator register W and the partial multiply result MULH.  All of our 
normal insn patterns start off not understanding anything about the 
hidden regs and then in the machine-dependent reorg we split insn 
patterns into ones that explicitly use the previously hidden regs and 
run a series of processor-specific passes to eliminate any redundancy.

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


Regards,
Dave

Re: An unusual Performance approach using Synthetic registers, and a request for guidance.

[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).  I also hope that because of the good L1
coherency of the stack, this might pay well on the x86 as well.  The only
problem might be in the lack of orthogonality in the x86 instruction set.

Go ahead, and good luck!

Paolo