* flow-analysis and Offner's notes
@ 2018-06-09 0:17 Matt Wette
2018-06-09 13:34 ` Matt Wette
0 siblings, 1 reply; 3+ messages in thread
From: Matt Wette @ 2018-06-09 0:17 UTC (permalink / raw)
To: guile-devel
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
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: flow-analysis and Offner's notes
2018-06-09 0:17 flow-analysis and Offner's notes Matt Wette
@ 2018-06-09 13:34 ` Matt Wette
2018-06-09 15:20 ` Matt Wette
0 siblings, 1 reply; 3+ messages in thread
From: Matt Wette @ 2018-06-09 13:34 UTC (permalink / raw)
To: guile-devel
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.
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: flow-analysis and Offner's notes
2018-06-09 13:34 ` Matt Wette
@ 2018-06-09 15:20 ` Matt Wette
0 siblings, 0 replies; 3+ messages in thread
From: Matt Wette @ 2018-06-09 15:20 UTC (permalink / raw)
To: guile-devel
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.
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2018-06-09 15:20 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2018-06-09 0:17 flow-analysis and Offner's notes Matt Wette
2018-06-09 13:34 ` Matt Wette
2018-06-09 15:20 ` Matt Wette
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).