Summary: Graph-based intermediate representations.

This is the summary of responses I got from my original query about
graph-based intermediate representations.


=============== 1 ==============================


I'm not really sure, what do you want to represent with graphs(?). For
conventional languages (as C) I think you'll find a lot of information
(Flow models, dependence graphs) but not very detailed in the last few years
SIGPLAN notices - lookout for the conference proceedings there. Some basic
work can be found in (book) Aho Ulman... Principals of Compiler Design (or
something like that, sorry), J. Ferrante et.al.: The program Dependence
graph and it's use in optimization, in ACM Transactions on Programming
Languages and Systems, don't know the year, mut be around 1986. You'll find
other references in the SIPLAN articles (look for things like program
slicing, program comparing...). Maybe you should look also at the end of the
seventies in SIGPLAN, there have been some articles concerning language
editors, those use attributed syntax trees which can be seen as spanning
trees over the semantic model graph of a program.
Even if you want to represent your hardware this way, I think it'll be
useful to read some of these things if this is done by high level
descriptions. Simply reading a VHDL language reference manual gives some
ideas how a graph model (for simulation) can be created (not detailed).
--
tom
-----------------------------------------------------------------------
snail mail: phone: +49-231 755 4825
                Thomas Dettmer
        University of Dortmund FAX: +49-231 75 15 32
Department of Computer Science I
              Post Box 50 05 00
            D-4600 Dortmund 50
    Federal Republic of Germany
email: dettmer@saturn.ls1.informatik.uni-dortmund.de


=============== 2 ==============================


You might review the work done by Emil Girczcyk and John Knight when
Emil was John's Ph.D. student. His representation was a combined
control data flow graph (CDFG). His work (a paper was published on
using ADA as a behavioral description language) was used in the
area of silicon compilation. I believe that John's mail address
is jknight@uhura.doe.carleton.ca
Hope this helps... duncan
--
Duncan Glendinning CAnet: ddrg@mentor.gandalf.ca, ddrg@gandalf.ca
Gandalf Data Ltd. Voice: (613) 723-6500
Nepean, Ontario Fax: (613) 226-1717
Canada K2E 7M4


=============== 3 ==============================


Reply-To: Paul J Landsberg <pjl2@edu.columbia.cc.cunixb>


Bell Labs uses tools which create VLSI layout from C-like code.
I know Kurt Kuetzer or Kreutzer? is involved, maybe Dwight Hill.
Of course I don't know how amenable they are to public discussion.
Try giving Murray Hill bell Labs a call to locate them.
Paul


=============== 4 ==============================


Reply-To: John Hagerman <hagerman@edu.cmu.ece.rx7>


There is much research in Behavioral Synthesis, the general goal of
which is to convert a behavioral description of a digital system into
a hardware implementation (at the register-transfer level, usually).


The research group I am in here at Carnegie Mellon has a set of tools,
collectively known as the System Architects' Workbench, which use an
internal representation called the Value Trace (VT), first described
by Michael McFarland (Master's Thesis, 1978). One problem with the VT
is that data and control information are not well separated, making
certain operations (such as transformations) rather difficult. I may
work on fixing this problem as a part of my work.


I don't know whether detailed descriptions of other representations
are available. I do know that Sangiovanni-Vincentelli at Stanford has
a system called Hercules that uses a behavioral language based on C
called HardwareC.


- John


=============== 5 ==============================


You may be able to get some ideas from IF1. A graph based
IR for SISAL. Though SISAL is an applicative language
I think it could be used with C without much extra effort.


In fact the compiler developed at Lawrence Livermore National
Labs and Univ Colorodo compiles SISAL -> IF1 -> C.


IF1 is fairly high level. The reference is,


"IF1, AN Intermediate Form for Applicative Languages",
Stephen Skedzielewski and John Glauert
Lawrence Livermore National Labs
1985


Ed Harcourt (harcourt@cscadm.ncsu.edu)


=============== 6 ==============================


Reply-To: Ira Baxter <baxter@edu.UCI.ICS.zola>


@phdthesis(vandenBosch81a,
    author = "Peter van den Bosch",
    title = "{The Translation of Programming Languages through
the use of a Graph Transformation Language}",
    school = "Department of Computer Science,
University of British Columbia, Vancouver B. C., Canada",
    year = 1981,
    annotation = {shows how to use graph-to-graph transformations for
code compilation}
)


=============== 7 ==============================


Reply-To: William "R." Greene <greene@edu.unc.cs>
Subject: Graph-based IR


A well-known and widely used graph-based intermediate representation for
Ada is DIANA (Descriptive Intermediate Attributed Notation for Ada). The
latest reference I have is


      DIANA Reference Manual
      Draft Revision 4
      5 May 1986
      Kathryn L. McKinley and Carl F. Schaefer
      Intermetrics, Inc.
      IR-MD-078


This is from the Intermetrics office at Bethesda, Maryland. The Revision 3
document is better known and more widely available (Springer-Verlag, as I
recall, printed it, and I think it's available from NTIS as well) and
probably as useful to you, especially if you're not implementing Ada.
--

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