30 May 1998 11:57:00 -0400

Related articles |
---|

Book: symbol table, type system, code generation? polymer@drschulz.em.uunet.de (Dr. Oliver Schulz) (1998-05-04) |

Re:Book: symbol table, type system, code generation? james.grosbach@Microchip.COM (1998-05-07) |

Re: Re:Book: symbol table, type system, code generation? anton@mips.complang.tuwien.ac.at (1998-05-12) |

Re: Re:Book: symbol table, type system, code generation? Peter.Damron@Eng.Sun.COM (1998-05-26) |

Re: Re:Book: symbol table, type system, code generation? anton@mips.complang.tuwien.ac.at (1998-05-30) |

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

Newsgroups: | comp.compilers |

Date: | 30 May 1998 11:57:00 -0400 |

Organization: | Institut fuer Computersprachen, Technische Universitaet Wien |

References: | 98-05-005 98-05-046 98-05-066 98-05-121 |

Keywords: | books, tools |

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

*> >In Section 9.2 (on basic block dependence graphs for instruction*

*> >scheduling) the algorithm presented for building the graph compares*

*> >every instruction with every other instruction, resulting in quadratic*

*> >complexity and redundant dependence edges. A linear method that*

*> >introduces fewer redundant edges is known (and even if you don't know*

*> >it, it's not that hard to figure out), but it is not even mentioned.*

Peter.Damron@Eng.Sun.COM (Peter C. Damron) writes:

*> The algorithm presented in the book is not very fast, but the problem*

*> is quadratic in general. If you limit the number of resources, and*

*> consider only register type resources, then you can build the DAG in*

*> linear time. But if you introduce either virtual registers (unbounded*

*> resources) or memory resources (and load/store disambiguation), then*

*> the problem becomes quadratic, though approx. linear time in practice.*

1) The algorithm in Muchnick's book is always quadratic. And the

redundant edges it introduces make the scheduler slower, and (in

extreme cases) may cause worse schedules.

2) Given a very realistic restriction on the machine architecture, the

use of an unlimited number of registers (or other resources) does not

make the problem quadratic. The restriction is that every instruction

can only read and write a limited number of registers/resources. This

limits the amount of work done per instruction to a constant amount

(if you attribute the work of adding flow and antidependences to the

reader of the resource), making the algorithm linear in the number of

instructions.

*> E.g. to do load/store disambiguation, you may have to compare every*

*> store with every load, since the aliasing relation (or points-to) is*

*> not transitive.*

That depends on the kind of disambiguation you perform. E.g., if you

just divide the references into disjoint classes and don't do any

disambiguation within classes (as you may do for a simple type-based

disambiguation), you do not have to compare every store with every

load: just introduce dependences between a load of a class and the

last and the next store of the same class; you also have to introduce

a dependence between a store and the last store of the same class.

With a little phantasy you can extend this to ANSI C type-based

disambiguation.

Even if you use a disambiguation, where you have to compare every

store to every other memory reference in the basic block, the

quadratic component typically has a much lower constant factor (my

guess: a factor of 10-100 lower for typical instruction distributions)

than the algorithm presented in the book, and the time for building

the graphs is probably dominated by the linear component in practice.

*> Here's a couple of fairly recent references on tree pattern matching.*

*> (I can't find the iburg one at the moment)*

*>*

*> %T Simple and Efficient BURS Table Generation*

The journal version is:

@Article{proebsting95toplas,

author = "Todd A. Proebsting",

title = "BURS Automata Generation",

journal = toplas,

year = "1995",

volume = "17",

number = "3",

pages = "461--486",

month = may

*}*

*> %T Engineering a Simple, Efficient Code-Generator Generator*

This is the iburg paper.

- anton

--

M. Anton Ertl Some things have to be seen to be believed

anton@mips.complang.tuwien.ac.at Most things have to be believed to be seen

http://www.complang.tuwien.ac.at/anton/home.html

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.