Scribd
Upload
37 views1 page

Cs8602-Compiler Design LAB Mini Project Implementation of Directed Acyclic Graph

The document discusses implementing a directed acyclic graph (DAG) to optimize basic blocks by applying transformations like dead code elimination and common subexpression elimination. DAGs are used to determine expressions computed multiple times, variables used but not defined in a block, and statements that can be made available outside a block to simplify the list of quadruples.

Uploaded by

Vishnu priya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
37 views1 page

Cs8602-Compiler Design LAB Mini Project Implementation of Directed Acyclic Graph

The document discusses implementing a directed acyclic graph (DAG) to optimize basic blocks by applying transformations like dead code elimination and common subexpression elimination. DAGs are used to determine expressions computed multiple times, variables used but not defined in a block, and statements that can be made available outside a block to simplify the list of quadruples.

Uploaded by

Vishnu priya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 1

CS8602- COMPILER DESIGN LAB

MINI PROJECT
IMPLEMENTATION OF DIRECTED ACYCLIC GRAPH

ABSTRACT

Directed Acyclic Graph (DAG) is a tool that depicts the structure of basic blocks,
helps to see the flow of values flowing among the basic blocks, and offers optimization too.
DAG provides easy transformation on basic blocks. Here a DAG is constructed for
optimizing the basic block and is usually constructed using three address code.
Transformations such as dead code elimination and common sub expression elimination are
then applied. The properties of DAGs are Reachability relation forms a partial order in
DAGs, Both transitive closure & transitive reduction are uniquely defined for DAGs and
topological orderings are defined for DAGs.

DAGs are used to determine the expressions which have been computed more than
once (called common sub-expressions), to determine the names whose computation has
been done outside the block but used inside the block, to determine the statements of the
block whose computed value can be made available outside the block and to simplify the
list of quadruples by not executing the assignment instructions x:=y unless they are
necessary and eliminating the common sub-expressions.In DAG, Leaf nodes represent
identifiers, names or constants, Interior nodes represent operators, Interior nodes also
represent the results of expressions or the identifiers/name where the values are to be stored
or assigned. While constructing a DAG, a check is made to find if there exists any node
with the same value, a new node is created only when there does not exist any node with
the same value and this action helps in detecting the common sub-expressions and avoiding
the re-computation of the same.

BY,
P.VISHNU PRIYA
311518104053
III BE-CSE

You might also like