8 May 1997 21:38:43 -0400

Related articles |
---|

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

Re: how to generate code for (a,b):=(b,a) chase@world.std.com (David Chase) (1997-05-08) |

how to generate code for (a,b):=(b,a) Dave@occl-cam.demon.co.uk (Dave Lloyd) (1997-05-08) |

Re: how to generate code for (a,b):=(b,a) bart@time.cirl.uoregon.edu (1997-05-08) |

Re: how to generate code for (a,b):=(b,a) Robert.Harley@inria.fr (1997-05-08) |

Re: how to generate code for (a,b):=(b,a) dlmoore@ix.netcom.com (David L Moore) (1997-05-08) |

Re: how to generate code for (a,b):=(b,a) preston@cs.rice.edu (1997-05-08) |

Re: how to generate code for (a,b):=(b,a) cliffc@risc.sps.mot.com (Cliff Click) (1997-05-12) |

Re: how to generate code for (a,b):=(b,a) wilson@cs.utexas.edu (1997-05-12) |

Re: how to generate code for (a,b):=(b,a) tim@wfn-shop.Princeton.EDU (1997-05-13) |

[14 later articles] |

From: | bart@time.cirl.uoregon.edu (Barton C. Massey) |

Newsgroups: | comp.compilers |

Date: | 8 May 1997 21:38:43 -0400 |

Organization: | CIRL |

References: | 97-05-058 |

Keywords: | code, optimize |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.