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

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> > This is equivalent to the problem of recoding the
> > multi-assignment (a1, a2, a3, ...) := (b1, b2, b3, ...)
> > into simple assignments,


Barton C. Massey wrote:
> 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.


This is indeed the technique the Moto compiler uses.


Cliff
--
Cliff Click, Ph.D. Compiler Researcher & Designer
RISC Software, Motorola PowerPC Compilers
cliffc@risc.sps.mot.com (512) 891-7240
--

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