8 May 1997 21:42:44 -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) |

[13 later articles] |

From: | Robert.Harley@inria.fr (Robert Harley) |

Newsgroups: | comp.compilers |

Date: | 8 May 1997 21:42:44 -0400 |

Organization: | I.N.R.I.A Rocquencourt |

References: | 97-05-058 |

Keywords: | code, optimize |

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:

*>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).*

First delete the assignments for which a_i is equal to the

corresponding b_i. Then if there is an a_i which does not occur among

the b_j's emit the assignment a_i := b_i and delete it. Keep doing

this until you are left with a permutation of the remaining registers.

Factor that permutation into disjoint cyclic permutations. Each

cyclic permutation, of length n say, can be done with one temporary

register and n+1 assignments in the obvious way.

*>[...]*

*>long bar(long,long,long);*

*>*

*>long foo(long a, long b, long c)*

*>{*

*> return bar(c,a,b);*

*>}*

*>*

*>BTW, I have compiled this on an Alpha under Digital "Unix" 4.0b with*

*>"cc -O5" and "gcc -O3". Both compilers generate 5 moves for this piece*

*>of code, i.e., one too many [...]*

In this case there is a single cyclic permutation of length three

which can clearly be done with one temporary and four assignments, but

there are dependencies between the successive assignments. If there

were several cyclic permutations, their assignments could be interleaved,

but here it is presumably faster to use extra temporaries and

assignments to take advantage of multiple issue.

-- Rob.

.-. Robert.Harley@inria.fr .-.

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.