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

Some time ago I asked the following 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
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. Off course it
would be nice if it would also produce good code.
--


There were several followups, and I also received some mail. Thanks to
all who replied.


Basically, two solutions were proposed:


1) Let the register allocator do it (adapted from a mail by Matthias
Blume):


Step 1: "Copy" all variables to new, fresh registers (these are
pseudo-registers at this stage):


(c1, c2, ...):=(b1, b2, ...)


Step 2: "Copy" the fresh registers back into the target registers:


(a1,a2,...) := (c1,c2,...)


Step 3: Run a coalescing register allocator over this stuff,
eliminating as many copies as possible.


Because the copies are scheduled in (almost) arbitrary order, this
method can be suboptimal (WRT the number of copies). E.g., consider


(a,b,c):=(c,a,b);


For a straightforward schedule like


c':=c;
a':=a;
b':=b;
a:=c';
b:=a';
c:=b';


b and a conflict with everything else, and therefore cannot be
coalesced with any of the psudoregisters. Therefore, we get five
copies, one more than optimal.


We currently use this approach for its simplicity. Maybe we will do
something better later on. One of the bad things is that it even
introduces many copies in cases where no copy to a temporary is
necessary, e.g.,


(b,c,d):=(a,b,c);


With the schedule


a'=a;
b'=b;
c'=c;
b=a';
c=b';
d=c';


we get five copies instead of the optimal three.


The following paper was suggested as reading:


Iterated Register Coalescing. Lal George and Andrew W. Appel. ACM
Transactions on Programming Languages and Systems 18(3) 300-324, May
1996. ©1996 ACM. Shorter version appeared in 23rd Annual ACM
SIGPLAN-SIGACT Symposium on Principles of Programming Languages,
January 1996.


However, it just appears to discuss a good way of doing the
coalescing.


2) The optimal special-purpose solution.


The description I liked best was by Bart Massey (I especially liked
the last sentence:-):


--
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 approach is also described in [burger+95] and (judging from the
references there) in several papers on compiling Scheme.


@InProceedings{burger+95,
    author = {Robert G. Burger and Oscar Waddell and R. Kent Dybvig},
    title = {Register Allocation Using Lazy Saves, Eager
                                    Restores, and Greedy Shuffling},
    crossref = "sigplan95",
    pages = {130--138}
}


@Proceedings{sigplan95,
    booktitle = "SIGPLAN '95 Conference on Programming Language
Design and Implementation",
    title = "SIGPLAN '95 Conference on Programming Language
Design and Implementation",
    year = "1995",
    key = "SIGPLAN '95"
}


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