how to generate code for (a,b):=(b,a) (Anton Ertl)
5 May 1997 22:01:37 -0400

          From comp.compilers

Related articles
how to generate code for (a,b):=(b,a) (1997-05-05)
Re: how to generate code for (a,b):=(b,a) (David Chase) (1997-05-08)
how to generate code for (a,b):=(b,a) (Dave Lloyd) (1997-05-08)
Re: how to generate code for (a,b):=(b,a) (1997-05-08)
Re: how to generate code for (a,b):=(b,a) (1997-05-08)
Re: how to generate code for (a,b):=(b,a) (David L Moore) (1997-05-08)
Re: how to generate code for (a,b):=(b,a) (1997-05-08)
[19 later articles]
| List of all articles for this month |

From: (Anton Ertl)
Newsgroups: comp.compilers
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
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.


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

Pass 1:


Pass 2:


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

Post a followup to this message

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