Re: Questions about partial redundancy elimination

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

Return to the comp.compilers page.
Search the comp.compilers archives again.