21 Oct 2004 22:22:22 -0400

Related articles |
---|

IR transforms for side-effect elimination m.a.ellis@ncl.ac.uk (Martin Ellis) (2004-10-21) |

From: | Martin Ellis <m.a.ellis@ncl.ac.uk> |

Newsgroups: | comp.compilers |

Date: | 21 Oct 2004 22:22:22 -0400 |

Organization: | University of Newcastle upon Tyne |

Keywords: | optimize, question |

Posted-Date: | 21 Oct 2004 22:22:22 EDT |

Hi all,

I'm looking for papers/books about transforms that eliminate

side-effects from an IR fragment for finding ILP, particularly ones

that consider their correctness using formal techniques.

I'd also appreciate comments on how various transformation can be

combined and any pointers to other useful literature...

The most appropriate reference I've found so far is Appel's Modern

Compiler Implementation in ML, which describes a transformation on

IR-trees that moves all the constructs with state and control

side-effects to the top of each tree.

The ML implementation given as 5 mutually recursive functions, and I

have been thinking about how one might prove its correctness (preserve

semantics and lift side-effects). Anyone know of similar/

simpler/alternative presentations of this idea?

The Dragon book describes the construction of a DAG but from a tuple

representation. I'm interested in combinations of this technique with

that described in Appel:

1) Not combine them at all, just use the tuple->DAG method for CSE,

finding parallelism, and rearranging for better register use. Then

DAG->ISA instructions.

2) IR-trees->IR-tuples (as in Appel, but generating IR rather than for

an ISA), then IR-tuples->DAG (as Dragon book), then generate code for

a specific architecture: DAG->ISA instructions.

3) IR-trees->DAG->ISA instructions. This is probably what I want,

as it skips conversion to and from tuples as in (2) but I don't think

I've seen any presentation of Trees->DAG anywhere - anyone?

(DAG->ISA is in the 'Crafting a Compiler' books).

I'm not fond of (1) because generating tuples from an AST doesn't

seem very natural to me - but does (2) sound a bit heavy handed?

Am I likely to run into problems translating IR-trees to DAGs in (3)?

Thanks for all comments and suggestions,

Martin

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.