Re: Retraction: terminology: double-rooted DAG?

Joel Jones wrote:
> I don't recall the source, but I have heard these referred to as hammocks.


I've also heard this, I think perhaps in the context of "Sharir's
graph decomposition" (either Vinod Grover or Peter Damron mentioned
this to me, back when I worked at Sun. Perhaps it is fresher in their
minds, if they are reading this).


One difficulty that I recall using hammocks in the context of graph
decomposition is that they don't fit all programming languages very
well. If you're working in something like Java, where exceptions can
be thrown (and these are probably visible to the control-flow
analyzer) your "single exit" has a vast number of predecessors, and
this combines hammocks that you'd rather keep separate (note that this
may be an artifact of my imperfect understand of Sharir's work).


Or, in other words, typical control flow graphs are not symmetrical
with respect to reversed edges.


What I ended up trying instead, which felt like a compromise between
theoretical niceness and typical program structure, was a
decomposition "relative to the current loop (strongly connected
component)". A distinction is made between edges that remain within
the SCC, and edges that exit the SCC, and hammocks and whatnot are
computed considering only those edges that remain within the SCC, with
the modification that hammocks can be noted as being the source of
exit edges. This is basically a hack, reflecting the bias that loops
are expected to loop (actual profiling information might tell you
otherwise, but actual profiling information might force you to use an
even hackier decomposition), because these decompositions are often
used (but not only used) to capture the notion of "locality" (consider
Callahan and Koblenz's register allocation work). I don't know if
this modified decomposition was generally useful; I heard that they
pulled it out of the compiler after I left (the algorithm for
computing it was goofy, to say the least).


--
David Chase, chase@world.std.com
--

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