12 May 1997 00:22:08 -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) |

Re: how to generate code for (a,b):=(b,a) cdg@nullstone.com (Christopher Glaeser) (1997-05-13) |

Re: how to generate code for (a,b):=(b,a) genew@vip.net (1997-05-13) |

Re: how to generate code for (a,b):=(b,a) bobduff@world.std.com (1997-05-13) |

Re: how to generate code for (a,b):=(b,a) will@ccs.neu.edu (William D Clinger) (1997-05-17) |

[10 later articles] |

From: | Cliff Click <cliffc@risc.sps.mot.com> |

Newsgroups: | comp.compilers |

Date: | 12 May 1997 00:22:08 -0400 |

Organization: | RISC Software, Motorola |

References: | 97-05-058 97-05-120 |

Keywords: | optimize, registers |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.