Tue, 18 May 1993 15:05:20 GMT

Related articles |
---|

Questions about partial redundancy elimination baxter@Austin.slcs.slb.com (1993-04-30) |

Re: Questions about partial redundancy elimination preston@dawn.cs.rice.edu (1993-05-01) |

Re: Questions about partial redundancy elimination bill@amber.csd.harris.com (1993-05-03) |

Re: Questions about partial redundancy elimination max@nic.gac.edu (1993-05-04) |

Re: Questions about partial redundancy elimination preston@dawn.cs.rice.edu (1993-05-05) |

Questions about partial redundancy elimination jk@informatik.uni-kiel.dbp.de (1993-05-17) |

Re: Questions about partial redundancy elimination uday@cse.iitb.ernet.in (1993-05-18) |

Newsgroups: | comp.compilers |

From: | uday@cse.iitb.ernet.in (Uday P Khedkar) |

Keywords: | optimize, bibliography |

Organization: | Compilers Central |

References: | 93-05-008 93-05-079 |

Date: | Tue, 18 May 1993 15:05:20 GMT |

There has been a lot of discussion on partial redundancy elimination.

Jens Knoop (jk@informatik.uni-kiel.dbp.de) makes some very insightful

statements. [Not that others don't have any insights :-)].

He writes

*>within a complete program. In contrast, common subexpression*

*>elimination (CSE) is *semantically* in that it usually stands for the*

*>elimination of (totally) redundant computations between (syntactically*

*>different) terms within basic blocks. CSE was pioneered by the value*

That's right. I would qualify Knoop's use of the name "CSE" by "local CSE"

as against "global CSE". I hope this makes his statement more concrete.

*>equality at execution time. PRE-algorithms working on flow graphs*

*>composed of basic blocks usually assume that CSE has been done before*

*>PRE starts. In particular, this guarantees that every basic block*

That's right. This is one assumption without which one can't proceed,

though it's rarely stated explicitly.

*>Conceptually, commutative operators do not cause any problems. Central*

*>for PRE-algorithms is a local predicate Comp(n) indicating whether a*

*>term t is computed in node n or not. If e.g. t equals t1 + t2 and you*

*>want to exploit the commutativity of addition just define Comp(n) to be*

*>true if n contains an occurrence of t1 + t2 or of t2 + t1. Note that*

That's very true; not just conceptually, but practically too. At least our

implementation of MRA leaves the botheration of commutativity to the

computaion of Comp(n) which is a local property.

*>elimation". In contrast, a practically important feature of this*

*>algorithm, which is inherited from its underlying algorithm for lazy*

*>code motion of [KRSpldi92,KRStoplas93], is that PRE is performed by*

*>purely unidirectional analyses. In fact, except for the algorithm of*

Of late there has been a lot of importance attached to decomposition into

unidirectional flows.

*>[DS88] (which, however, requires more analyses than the one of*

*>[KRSpldi92]), all previous PRE-algorithms*

*>[Chowphd,Dh83,Dh88,Dh91,JD82a,JD82b,MR79,So89] require a bidirectional*

*>data flow analysis ([DRZpldi92] is conceptually based on an underlying*

*>bidirectional analysis). Bidirectional analyses, however, are*

*>conceptually and computationally more complex than unidirectional*

There is really no need to worry about the complexity of bidirectional

problems anymore, thanks to the popl93 paper

@inproceedings{width,

author = {D. M. Dhamdhere and Uday P. Khedker},

title = {Complexity of bidirectional data flow analysis},

booktitle = popl,

pages = {397--???},

year = 1993

}

*>ones: In contrast to the unidirectional case, where reducible programs*

*>can be dealt with in O(n*log(n)) time, where n characterizes the size*

*>of the argument program (e.g. number of statements), the best known*

*>estimation for bidirectional analyses is O(n^2) (detailed references*

Not quite true. See the above paper. It gives better estimates of

complexity. Apart from the formal proofs of the theoretical results, it

also gives a lot of experimental data. In particular, for the MRA, it

predicts a very strict bound on the number of iterations. Going by this

bound, I don't see why quadratic behaviour of MRA should cause

sleeplessness anymore.

A slight digression : The paper defines a notion of the "width" of a graph

which is a fine blend of the properties of graph structures and patterns

of data flows. The width is shown to bound the number of iterations of

round robin algorithm for the unidirectional as well as bidirectional data

flow problems. For the unidirectional problems, it provides a more

accurate bound than the traditional notion of depth of a graph.

There are several interesting outcomes of this result. See the paper for

details.

*>can be found in [KRSpldi92]). Thus, the decomposition of the*

*>originally bidirectional data flow in PRE into (straightforward)*

*>unidirectional components drastically improves on the complexity of the*

*>previous algorithms for PRE. Moreover, it is much easier to see of*

There may be cases in which decompositiona may not results in dramatic

many gains. There may be cases when deomposition may not work unless some

pre-conditions are satisfied. The above paper also provides feasibility

criteria for decomposition of arbitrary bidirectional problems. This is

achieved without requiring any insights into the data flow problem being

solved.

In particular, the decomposition suggested in PLDI92 paper

@inproceedings{KRSpldi92,

author = {Knoop, J. and R\"uthing, O. and Steffen, B.},

address = {San Francisco, CA},

booktitle = "Proc.~" # pldi #"'92",

pages = {224 - 234},

series = sigplannot,

volume = {27},

number = {7},

title = {Lazy code motion},

month = jun,

year = {1992}

}

will not work unless edge-splitting is performed. So the power of

decomposition for PRE comes from edge-splitting and not from decomposition

per se. (No flames please, see the popl93 paper for explanations).

More observations on complexity of bidirectional data flows are welcome.

Uday Khedker,

Research Scholar,

Dept. of Computer Science & Engineering,

IIT Bombay, 400 076 India.

email : uday@cse.iitb.ernet.in

Phone : +91-22-578-2545 c/o x2701, x2702.

Fax : +91-22-578-3480.

Telex : 011-71385 IITB IN.

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.