Re: Questions about partial redundancy elimination (Uday P Khedkar)
Tue, 18 May 1993 15:05:20 GMT

          From comp.compilers

Related articles
Questions about partial redundancy elimination (1993-04-30)
Re: Questions about partial redundancy elimination (1993-05-01)
Re: Questions about partial redundancy elimination (1993-05-03)
Re: Questions about partial redundancy elimination (1993-05-04)
Re: Questions about partial redundancy elimination (1993-05-05)
Questions about partial redundancy elimination (1993-05-17)
Re: Questions about partial redundancy elimination (1993-05-18)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (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 ( 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

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

>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

In particular, the decomposition suggested in PLDI92 paper
       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 :
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.