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

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


Presumably the a[i] are disjoint (i.e. they form a set). Otherwise,
the simultaneous copy problem is ill-defined as stated (and I suspect
that when one reformulates it in the obvious way, finding an optimal
solution is NP hard).


Offhand, I think you can do things like this:
1) Build a directed graph whose vertices are the
registers, and whose edges are from source to
destination of the original atomic assignments.
2) Delete any trivial edges (i.e. registers assigned
to themselves).
3) Pick a root vertex and pull out a subgraph reachable
from that vertex in topological sort order. The fact
that the a[i] are disjoint means that the subgraph can
have at most one back edge. If this back edge exists,
it is part of a unique cycle in the subgraph, and is
into the root vertex you chose.
4) If necessary, emit a save into a temporary of the
value of the register which is the source of the
back-edge move.
5) Emit the non-back-edge moves in the reverse of the
original topological sort order.
6) If necessary, emit a restore from the temporary into
the destination of the back-edge move.
7) Delete this subgraph.
8) Repeat steps 3-7 as necessary.
For an n-way multi-assignment, this algorithm should run in
time o(n) and should produce optimal answers.


Anybody see a bug here?


Bart Massey
bart@cs.uoregon.edu
--

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