Category: Compiler Design

Directed Acyclic Graphs | DAGs | Examples

Compiler Design

Directed Acyclic Graph-

 

Directed Acyclic Graph (DAG) is a special kind of Abstract Syntax Tree.

 

  • Each node of it contains a unique value.
  • It does not contain any cycles in it, hence called Acyclic.

 

Optimization Of Basic Blocks-

 

DAG is a very useful data structure for implementing transformations on Basic Blocks.

 

  • A DAG is constructed for optimizing the basic block.
  • A DAG is usually constructed using Three Address Code.
  • Transformations such as dead code elimination and common sub expression elimination are then applied.

 

Properties-

 

  • Reachability relation forms a partial order in DAGs.
  • Both transitive closure & transitive reduction are uniquely defined for DAGs.
  • Topological Orderings are defined for DAGs.

 

Applications-

 

DAGs are used for the following purposes-

  • 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.
  • To simplify the list of Quadruples by not executing the assignment instructions x:=y unless they are necessary and eliminating the common sub-expressions.

 

Construction of DAGs-

 

Following rules are used for the construction of DAGs-

 

Rule-01:

 

In a DAG,

  • Interior nodes always represent the operators.
  • Exterior nodes (leaf nodes) always represent the names, identifiers or constants.

 

Rule-02:

 

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.
  • This action helps in detecting the common sub-expressions and avoiding the re-computation of the same.

 

Rule-03:

 

The assignment instructions of the form x:=y are not performed unless they are necessary.

 

Also Read- Code Optimization

 

PRACTICE PROBLEMS BASED ON DIRECTED ACYCLIC GRAPHS-

 

Problem-01:

 

Consider the following expression and construct a DAG for it-

         ( a + b ) x ( a + b + c )

 

Solution-

 

Three Address Code for the given expression is-

 

T1 = a + b

T2 = T1 + c

T3 = T1 x T2

 

Now, Directed Acyclic Graph is-

 

 

NOTE

 

From the constructed DAG, we observe-

  • The common sub-expression (a+b) has been expressed into a single node in the DAG.
  • The computation is carried out only once and stored in the identifier T1 and reused later.

 

This illustrates how the construction scheme of a DAG identifies the common sub-expression and helps in eliminating its re-computation later.

 

Problem-02:

 

Consider the following expression and construct a DAG for it-

( ( ( a + a ) + ( a + a ) ) + ( ( a + a ) + ( a + a ) ) )

 

Solution-

 

Directed Acyclic Graph for the given expression is-

 

 

Problem-03:

 

Consider the following block and construct a DAG for it-

 

(1) a = b x c

(2) d = b

(3) e = d x c

(4) b = e

(5) f = b + c

(6) g = f + d

 

Solution-

 

Directed Acyclic Graph for the given block is-

 

 

Problem-04:

 

Optimize the block in the Problem-03.

 

Solution-

 

Step-01:

 

Firstly, construct a DAG for the given block (already done above).

 

Step-02:

 

Now, the optimized block can be generated by traversing the DAG.

  • The common sub-expression e = d x c which is actually b x c (since d = b) is eliminated.
  • The dead code b = e is eliminated.

 

The optimized block is-

 

(1) a = b x c

(2) d = b

(3) f = a + c

(4) g = f + d

 

Problem-05:

 

Consider the following basic block-

 

B10:

S1 = 4 x I

S2 = addr(A) – 4

S3 = S2[S1]

S4 = 4 x I

S5 = addr(B) – 4

S6 = S5[S4]

S7 = S3 x S6

S8 = PROD + S7

PROD = S8

S9 = I + 1

I = S9

If I <= 20 goto L10

 

  1. Draw a directed acyclic graph and identify local common sub-expressions.
  2. After eliminating the common sub-expressions, re-write the basic block.

 

Solution-

 

Directed Acyclic Graph for the given basic block is-

 

 

In this code fragment,

  • 4 x I is a common sub-expression. Hence, we can eliminate because S1 = S4.
  • We can optimize S8 = PROD + S7 and PROD = S8 as PROD = PROD + S7.
  • We can optimize S9 = I + 1 and I = S9 as I = I + 1.

 

After eliminating S4, S8 and S9, we get the following basic block-

 

B10:

S1 = 4 x I

S2 = addr(A) – 4

S3 = S2[S1]

S5 = addr(B) – 4

S6 = S5[S1]

S7 = S3 x S6

PROD = PROD + S7

I = I + 1

If I <= 20 goto L10

 

To gain  better understanding about Directed Acyclic Graphs,

Watch this Video Lecture

 

Download Handwritten Notes Here-

 

 

Next Article- Misc Problems On Directed Acyclic Graphs

 

Get more notes and other study material of Compiler Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Basic Blocks and Flow Graphs | Examples

Compiler Design

Basic Blocks-

 

Basic block is a set of statements that always executes in a sequence one after the other.

 

The characteristics of basic blocks are-

  • They do not contain any kind of jump statements in them.
  • There is no possibility of branching or getting halt in the middle.
  • All the statements execute in the same order they appear.
  • They do not lose lose the flow control of the program.

 

Example Of Basic Block-

 

Three Address Code for the expression a = b + c + d is-

 

 

Here,

  • All the statements execute in a sequence one after the other.
  • Thus, they form a basic block.

 

Also Read- Three Address Code

 

Example Of Not A Basic Block-

 

Three Address Code for the expression If A<B then 1 else 0 is-

 

 

Here,

  • The statements do not execute in a sequence one after the other.
  • Thus, they do not form a basic block.

 

Partitioning Intermediate Code Into Basic Blocks-

 

Any given code can be partitioned into basic blocks using the following rules-

 

Rule-01: Determining Leaders-

 

Following statements of the code are called as Leaders–

  • First statement of the code.
  • Statement that is a target of the conditional or unconditional goto statement.
  • Statement that appears immediately after a goto statement.

 

Rule-02: Determining Basic Blocks-

 

  • All the statements that follow the leader (including the leader) till the next leader appears form one basic block.
  • The first statement of the code is called as the first leader.
  • The block containing the first leader is called as Initial block.

 

Flow Graphs-

 

A flow graph is a directed graph with flow control information added to the basic blocks.

 

  • The basic blocks serve as nodes of the flow graph.
  • There is a directed edge from block B1 to block B2 if B2 appears immediately after B1 in the code.

 

PRACTICE PROBLEMS BASED ON BASIC BLOCKS & FLOW GRAPHS-

 

Problem-01:

 

Compute the basic blocks for the given three address statements-

 

(1) PROD = 0

(2) I = 1

(3) T2 = addr(A) – 4

(4) T4 = addr(B) – 4

(5) T1 = 4 x I

(6) T3 = T2[T1]

(7) T5 = T4[T1]

(8) T6 = T3 x T5

(9) PROD = PROD + T6

(10) I = I + 1

(11) IF I <=20 GOTO (5)

 

Solution-

 

We have-

  • PROD = 0 is a leader since first statement of the code is a leader.
  • T1 = 4 x I is a leader since target of the conditional goto statement is a leader.

 

Now, the given code can be partitioned into two basic blocks as-

 

 

Problem-02:

 

Draw a flow graph for the three address statements given in problem-01.

 

Solution-

 

  • Firstly, we compute the basic blocks (already done above).
  • Secondly, we assign the flow control information.

 

The required flow graph is-

 

 

Also Read- More Problems On Basic Blocks & Flow Graphs

 

To gain better understanding about Basic Blocks and Flow Graphs,

Watch this Video Lecture

 

Download Handwritten Notes Here-

 

 

Next Article- Directed Acyclic Graphs

 

Get more notes and other study material of Compiler Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.