how to generate code for (a,b):=(b,a)

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
multi-assignment


(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
on this?


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.


E.g.:


(r0, r1):= (r1, r0)


Pass 1:


r2:=r0;


Pass 2:


r0:=r1;
r1:=r2;


One way this problem does arise is in the following piece of C code:


long bar(long,long,long);


long foo(long a, long b, long c)
{
    return bar(c,a,b);
}


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.
- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/home.html
--

Return to the comp.compilers page.
Search the comp.compilers archives again.