|how to generate code for (a,b):=(b,a) email@example.com (1997-05-05)|
|Re: how to generate code for (a,b):=(b,a) firstname.lastname@example.org (David Chase) (1997-05-08)|
|how to generate code for (a,b):=(b,a) Dave@occl-cam.demon.co.uk (Dave Lloyd) (1997-05-08)|
|Re: how to generate code for (a,b):=(b,a) email@example.com (1997-05-08)|
|Re: how to generate code for (a,b):=(b,a) Robert.Harley@inria.fr (1997-05-08)|
|Re: how to generate code for (a,b):=(b,a) firstname.lastname@example.org (David L Moore) (1997-05-08)|
|Re: how to generate code for (a,b):=(b,a) email@example.com (1997-05-08)|
|[19 later articles]|
|From:||firstname.lastname@example.org (Anton Ertl)|
|Date:||5 May 1997 22:01:37 -0400|
|Organization:||TU Wien, Institut fuer Computersprachen|
|Keywords:||code, optimize, question|
In a code generator we have a problem of moving the contents of
several registers to other registers, as if the copies happened
simultaneously. This is equivalent to the problem of recoding the
(a1, a2, a3, ...) := (b1, b2, b3, ...)
into simple assignments, where the bs are not necessarily different
from as or other bs (but ai<>aj for i<>j).
I am looking for a very fast algorithm for doing this. Of course it
would be nice if it would also produce good code.
This problem occurs frequently in compilers, so are there any papers
A simple algorithm for this problem is to have two passes: The first
one copies any register, that is the source of a move to
higher-numbered target register, to a free register and replaces the
reference to that source register in the multi-assignment with a
reference to the (once) free register. The second pass performs all
the copies, starting with the lowest-numbered target register.
(r0, r1):= (r1, r0)
One way this problem does arise is in the following piece of C code:
long foo(long a, long b, long c)
BTW, I have compiled this on an Alpha under Digital "Unix" 4.0b with
"cc -O5" and "gcc -O3". Both compilers generate 5 moves for this piece
of code, i.e., one too many (of course, given that they generate 17
and 16 instructions (respectively) overall, one additional move does
not hurt that much.
M. Anton Ertl
Return to the
Search the comp.compilers archives again.