flow-analysis and Offner's notes

flow-analysis and Offner's notes

[Matt Wette]

Hi All,

Andy Windo's blog on flow-analysis in Guile references Offner's "Notes on Graph
Algorithms Used in Optimizing Compilers"?  Anyone read this manuscript?  Lemma
2.2 says, in a flow-graph, if x>>z and y>>z, then either x>>y or y>>x.  The proof
uses the argument that the path from s, the start, to z has to include both x and y.
I'm not seeing that.  Consider a graph s->x, s->y, x->z and y->z. What am I missing?
(another example, in figure 2.1 C>>K and B>>K but C and B are not ordered.)

Ref: http://www.cs.umb.edu/~offner/files/flow_graph.pdf

Matt

Re: flow-analysis and Offner's notes

[Matt Wette]

On 06/08/2018 05:17 PM, Matt Wette wrote:
> Andy Windo's blog on flow-analysis in Guile references Offner's "Notes 
> on Graph
> Algorithms Used in Optimizing Compilers"?  Anyone read this 
> manuscript?  Lemma
> 2.2 says, in a flow-graph, if x>>z and y>>z, then either x>>y or 
> y>>x.  The proof
> uses the argument that the path from s, the start, to z has to include 
> both x and y.
> I'm not seeing that.  Consider a graph s->x, s->y, x->z and y->z. What 
> am I missing?

> (another example, in figure 2.1 C>>K and B>>K but C and B are not 
> ordered.)

This example does not not qualify as C and B do not dominate K.
C dominates K iff every path from the start S to K goes through C.

Re: flow-analysis and Offner's notes

[Matt Wette]

On 06/09/2018 06:34 AM, Matt Wette wrote:
> On 06/08/2018 05:17 PM, Matt Wette wrote:
>> Andy Windo's blog on flow-analysis in Guile references Offner's 
>> "Notes on Graph
>> Algorithms Used in Optimizing Compilers"?  Anyone read this 
>> manuscript?  Lemma
>> 2.2 says, in a flow-graph, if x>>z and y>>z, then either x>>y or 
>> y>>x.  The proof
>> uses the argument that the path from s, the start, to z has to 
>> include both x and y.
>> I'm not seeing that.  Consider a graph s->x, s->y, x->z and y->z. 
>> What am I missing?

I was missing the definition of "dominates."
Sorry for the interruption.
Now need to think about this.