Re: DAG Construction Process

Uncle Noah <>
Wed, 31 Oct 2007 01:38:42 -0700

          From comp.compilers

Related articles
DAG Construction Process (2007-10-31)
Re: DAG Construction Process (Uncle Noah) (2007-10-31)
| List of all articles for this month |

From: Uncle Noah <>
Newsgroups: comp.compilers
Date: Wed, 31 Oct 2007 01:38:42 -0700
Organization: Compilers Central
References: 07-10-101
Keywords: optimize, analysis
Posted-Date: 31 Oct 2007 09:57:35 EDT

On Oct 31, 4:58 am, wrote:
> I am trying to implement optimization within a basic block. I
> understand that the Conversion of unoptimized code to DAG and
> subsequent regeneration of quads from the DAG is a good way to
> optimize the Intermediate code. I read the Algorithm given in pp 549
> of the Dragon Book.
> I do not understand how to create a DAG for scenarios where there is
> an assignment as the the first access of leaves. For e.g., if the
> unoptimized IC is of the form
> f = b + c
> c = b
> My questions are
> (1) Can leaves have attached identifiers ?
> (2) The code regeneration talks of walking through interior nodes in
> the DAG for the optimal code generation. In case leaves have attached
> identifiers, then how do we deal with that during the Quad
> regeneration ?
> (3) How would we be able to differentiate the situation where we have
> unoptimized code as
> f = b + c
> c = b
> v/s
> c = b
> f = b + c
> Can somebody shed more light on this or point to material for DAG
> construction for Basic Blocks ?

My tool, named "bbpart" is a DAG constructor for CFGnodes (that is:
basic blocks) that works for the SUIF2/Machine-SUIF 2 latest
distributions. It extracts DDGs (data-dependence graphs) which are
DAGs (for basic block scope) from SUIFvm IR (intermediate
representation). You can think of SUIFvm IR as a form of assembly for
a symbolic (virtual) machine.

You can the find two versions of the pass (it is a compiler pass for
Machine-SUIF, affectionately called MachSUIF) here:

Direct links:

Kind regards
Nikolaos Kavvadias

Post a followup to this message

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