Re: [tree-ssa]quick SSAPRE question

[Daniel Berlin <dberlin at dberlin dot org>]

On Sep 26, 2003, at 7:32 AM, Per Fransson wrote:

> Hello,
>
> I know this isn't really a gcc question, but I figured this was the one
> place I could find a lot of people who have read:
>
> "Partial Redundancy Elimination in SSA Form." ACM Transactions on
> Programming Languages and Systems, 21(3): 627-676, 1999. (Robert
> Kennedy, Sun Chan, Shin-Ming Liu, Raymond Lo, Peng Tu, and Fred Chow)
>
> I don't know how many times I've started reading this article and I
> *always* get stuck in the same place:

The articles are somewhat "buggy", to be honest.

> In section 2.3 definition 2 explains "redundant" as:
>
> "If E1 and E2 are occurrences of some computation E and there is a 
> control
> flow path from E1 to E2 containing nothing that may alter the value of 
> E,
> we say that E2 is redundant with respect to E1."
>
> Definition 3 in the same section explains "exposed" as:
>
> "Let E1 be an occurrence of some computation E, and let p be some 
> point in
> the program. If there is a control flow path from p to E1 containing
> nothing that may alter the value of E and containing no occurrence of E
> between p and E1, we say that E1 is exposed with respect to p."
>
> Immediately thereafter a set (omega) is defined as:
>
> "the set of occurrences with respect to which an
> occurrence E0 is exposed and redundant"
>
> What am I missing here? It seems to me that if E0 is exposed with
> respect to an occurence it *must* also be redundant with respect to 
> that
> occurence,

Note that they actually don't define what exposed means in respect to 
an occurrence, only what it means in respect to a program point.  They 
then use it in respect to an occurrence, which leaves one guessing as 
to what program point they are trying to talk about.