Re: From quads to AST

krishna@cs.unm.edu (Ksheerabdhi Krishna)
Wed, 18 Aug 1993 20:21:11 GMT

          From comp.compilers

Related articles
From quads to AST cheung@unx.sas.com (1993-08-10)
Re: From quads to AST daniel@quilty.stanford.edu (1993-08-13)
Re: From quads to AST krishna@cs.unm.edu (1993-08-18)
| List of all articles for this month |

Newsgroups: comp.compilers
From: krishna@cs.unm.edu (Ksheerabdhi Krishna)
Keywords: optimize
Organization: Computer Science Department, University of New Mexico
References: 93-08-049 93-08-074
Date: Wed, 18 Aug 1993 20:21:11 GMT

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
--


Post a followup to this message

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