Compilers - DAG Construction Process

Author

DAG Construction Process

raghavan97@yahoo.co.in

2007-10-31, 4:35 am

Hi,

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 ?

Thanks.

Bye,
Raghavan V

Uncle Noah

2007-10-31, 7:20 pm

On Oct 31, 4:58 am, raghava...@yahoo.co.in 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:
http://electronics.physics.auth.gr/.../kavvadias.html

Direct links:
http://electronics.physics.auth.gr/...rt-1.0.1.tar.gz
http://electronics.physics.auth.gr/...t-1.0.7a.tar.gz

Kind regards
Nikolaos Kavvadias

Sponsored Links