13 Jun 1997 22:07:02 -0400

Related articles |
---|

how to generate code for (a,b):=(b,a) (Summary) anton@mips.complang.tuwien.ac.at (1997-06-13) |

From: | anton@mips.complang.tuwien.ac.at (Anton Ertl) |

Newsgroups: | comp.compilers |

Date: | 13 Jun 1997 22:07:02 -0400 |

Organization: | TU Wien, Institut fuer Computersprachen |

Keywords: | optimize, code, 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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.