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

David Chase <chase@world.std.com>
8 May 1997 21:28:06 -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)
[16 later articles]
| List of all articles for this month |

From: David Chase <chase@world.std.com>
Newsgroups: comp.compilers
Date: 8 May 1997 21:28:06 -0400
Organization: Compilers Central
Keywords: code, optimize

Anton Ertl wrote:
[ how to generate code for N-way register exchange ? ]


I think there was some mention of this in Knuth (of course), I dimly
remember this being part of an algorithms homework assignment of some
significance many years ago. If the sets of registers are the same
(as they would be for parameters) then you can view it as a
permutation, and any permutation can be represented as a set of
cycles, and you can do a cycle of length in N in N+1 moves using a
single scratch register.


e.g.


    abcdef => badfce


    1 <- 2 <- 1


    3 <- 4 <- 6 <- 5 <- 3


Finding the cycles takes some time, I believe computing the expected
case for that time is the interesting part of the homework problem.
Of course, in the general case, this is not a proper permutation,
since the register sets may not be equal, and some of the sources
may be trashed. I think this means that you can save one move per
"cycle" (and they are not really cycles then).


David Chase




--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.