Re: From quads to AST

daniel@quilty.stanford.edu (Daniel Weise) writes:
>The construction of the PDG starts from a CFG, not an AST. A PDG
>consists of an intertwining of a data dependence graph (DDG) and a
>control dependence graph (CDG). Methods for constructing a CDG all
>start from a CFG. The standard PDG paper (Ferrante, Ottenstein, and
>Warren, TOPLAS 86?) isn't too clear on the DDG part, but it can also
>be constructed from the CFG.


While this is true for the most, it is my duty to point out that for a
large class of programs (pgms with structured gotos - break, continue,
return) one can construct the PDG from an AST. The crucial piece here
is constructiung the CDG (which has always required CFG/PDOM
computation). Constructing the CDG from the AST involves keeping
information regrading exits and a track of regions. For people more
interested in constructing a PDG without going the CFG-PDOM-CDG route
look under ftp.cs.unm.edu in /pub/cs_tech_reports/1992/CS92-10.ps.Z


The techniques suggested in the paper really work, I have successfuly
implemented them in a front-end. The TOPLAS '86 paper is not that
clear about DDG, but Ottenstein's Software Practice and Experience paper
with Steven Ellecy makes up for that.


back to web weaving,
ksh
--

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