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

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>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).


First delete the assignments for which a_i is equal to the
corresponding b_i. Then if there is an a_i which does not occur among
the b_j's emit the assignment a_i := b_i and delete it. Keep doing
this until you are left with a permutation of the remaining registers.
Factor that permutation into disjoint cyclic permutations. Each
cyclic permutation, of length n say, can be done with one temporary
register and n+1 assignments in the obvious way.




>[...]
>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 [...]


In this case there is a single cyclic permutation of length three
which can clearly be done with one temporary and four assignments, but
there are dependencies between the successive assignments. If there
were several cyclic permutations, their assignments could be interleaved,
but here it is presumably faster to use extra temporaries and
assignments to take advantage of multiple issue.


-- Rob.
          .-. Robert.Harley@inria.fr .-.
--

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