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

Cliff Click <cliffc@risc.sps.mot.com>
12 May 1997 00:22:08 -0400

          From comp.compilers

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]
| List of all articles for this month |

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.