# 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.