DAG (Directed Acyclic Graph) in Compiler Design

In compiler design, a Directed Acyclic Graph (DAG) is used to represent expressions,

optimize code, and eliminate redundant computations. It helps in common subexpression
elimination, constant folding, and reusing previously computed values.

Steps for Constructing a DAG in Compiler Design

1. Tokenization & Parsing – Convert source code into a parse tree using lexical and
syntax analysis.
2. Identify Operators & Operands – Recognize expressions, variables, constants,
and operations.
3. Check for Existing Nodes – If an identical subexpression exists, reuse the existing
node instead of creating a new one.
4. Create Nodes for Unique Subexpressions – Assign a node for each unique
operation and operand.
5. Establish Directed Edges – Connect nodes to represent dependencies.
6. Optimize by Eliminating Redundant Computations – Avoid recalculating already
computed expressions.
7. Generate Intermediate Code – Convert the DAG representation into an
intermediate code format (e.g., three-address code).
8. Register Allocation & Instruction Selection – Assign registers efficiently using
DAG structure.
9. Perform Dead Code Elimination – Remove unused computations based on the
DAG.
10.Final Code Generation – Convert the optimized DAG into machine code.
Examples of DAG in Compiler Design
1. Common Subexpression Elimination
o Example:
t1 = a + b
t2 = a + b
t3 = t1 * c
o The expression a + b is computed twice; a DAG eliminates redundancy.
2. Constant Folding
o Example:
x=4+6
y=x*2
o The compiler evaluates 4 + 6 at compile-time and replaces x with 10.
3. Code Optimization in Expression Trees
o Example: ((a + b) + c) + d
o DAG representation reduces redundant operations.
4. Register Allocation Optimization
o DAG helps in minimizing register usage by reusing intermediate results.
5. Loop-Invariant Code Motion
o Moving computations that do not change within a loop outside to optimize
execution.
6. Dependency Graph for Instruction Scheduling
o Helps reorder instructions to improve performance while maintaining
correctness.
7. Eliminating Dead Code
o If an assigned value is never used, the DAG helps detect and remove it.
8. Boolean Expression Optimization
o Example: if ((x && y) && y)
o DAG eliminates redundant y evaluation.
9. DAG Representation in SSA (Static Single Assignment) Form
o Used in modern compilers for better optimization and analysis.
 10.Optimization in Switch-Case Statements
 DAG helps rearrange conditions and eliminate unnecessary evaluations.
Examples of DAG (Directed Acyclic Graph)

Example 1: Common Subexpression Elimination

Expression:
t1 = a + b
t2 = a + b
t3 = t1 * c
DAG Representation:
 (a + b) is computed twice → Only one node for (a + b).
 t1 and t2 point to the same node.

(+)
/ \
a b
\
(*)
/ \
t1 c
Optimized Code:
t1 = a + b
t3 = t1 * c
Example 2: Constant Folding
Expression:
x=4+6
y=x*2
DAG Representation:
 4 + 6 is a constant expression, so it is evaluated at compile-time.
(*)
/ \
10 2
Optimized Code:
y = 10 * 2 // Replaces x with 10

Example 3: Eliminating Dead Code

Expression:
a=b+c
x=5
x = a * 2 // Overwrites x, making `x = 5` dead code
DAG Representation:
 The assignment x = 5 is never used.

(*)
/ \
a 2
Optimized Code:
a=b+c
x=a*2
Example 4: Code Optimization in Expression Trees
Expression:
z = ((a + b) + c) + d
DAG Representation:
 Instead of computing a + b multiple times, reuse the intermediate result.
(+)
/ \
(+) d
/ \
a b
\
c
Optimized Code:
t1 = a + b
t2 = t1 + c
z = t2 + d

Example 5: Loop-Invariant Code Motion

Expression:
for (i = 0; i < n; i++) {
x = a + b; // This does not depend on i
y = x * i;
}
DAG Optimization:
 a + b is loop-invariant and can be moved outside the loop.
Optimized Code:
x = a + b;
for (i = 0; i < n; i++) {
y = x * i;
}
Example 6: Boolean Expression Optimization
Expression:
if ((x && y) && y)
DAG Representation:
 The second y is redundant.
(&&)
/ \
x y
Optimized Code:
if (x && y)

Example 7: Dependency Graph for Instruction Scheduling

Expression:
t1 = a + b
t2 = c * d
t3 = t1 + t2
t4 = t3 / e
DAG Representation:
(/)
/ \
(+) e
/ \
(+) (*)
/\ / \
a bc d
Optimized Code Execution Order:
t1 = a + b
t2 = c * d
t3 = t1 + t2
t4 = t3 / e
(Parallel execution is possible for t1 and t2.)

Example 8: DAG Representation in SSA (Static Single Assignment)

Expression:
x=a+b
y=x+c
x=y+d
DAG Representation:
 The second x is independent of the first one.
(+)
/ \
(+) d
/ \
x1 c
/ \
a b
Optimized Code Using SSA:
x1 = a + b
y = x1 + c
x2 = y + d

Example 9: Strength Reduction

Expression:
y=x*8
DAG Optimization:
 Multiplication by 8 can be replaced by bitwise shift.
(<<)
|
x
Optimized Code:
y = x << 3

Example 10: Optimization in Switch-Case Statements

Code:
switch (x) {
case 1: y = a + b; break;
case 2: y = a + b; break;
case 3: y = a + b; break;
}
DAG Representation:
 y = a + b is common in all cases.
(+)
/ \
a b
Optimized Code:
t = a + b;
switch (x) {
case 1: y = t; break;
case 2: y = t; break;
case 3: y = t; break;
}
Backpatching in Compiler Design

Introduction to Backpatching
Backpatching is a technique used in syntax-directed translation to
handle control flow statements efficiently. It is primarily used for generating intermediate
code for constructs such as **if-else statements, loops, switch-case, and break/continue
statements**. The key idea is to delay the resolution of jump addresses until all required
information is available.
Steps for Backpatching
1. Create Lists for Unresolved Jumps:
- Maintain lists for `true` and `false` jumps in conditions.
- Maintain lists for `break` and `continue` statements in loops.

2. Generate Intermediate Code with Placeholders:

- Use placeholders (e.g., `_` or `??`) for jump addresses that are not yet determined.

3. Propagate True and False Lists:

- The `true` list links to where execution continues when the condition is true.
- The `false` list links to where execution continues when the condition is false.

4. Merge Jump Lists When Necessary:

- Merge lists of multiple conditional statements using `merge(list1, list2)`.

5. Backpatch Unresolved Addresses:

- Replace placeholder addresses with actual jump labels once they are known.
Examples of Backpatching

Example 1: Simple `if` Statement

Code:
if (a > b)
x = 10;
Intermediate Code (Before Backpatching):
IF a > b GOTO _ (true list: [1])
GOTO _ (false list: [2])
x = 10
After Backpatching:
IF a > b GOTO L1
GOTO L2
L1: x = 10
L2: // next statement
Example 2: `if-else` Statement
Code:
if (a > b)
x = 10;
else
x = 20;
Final Code After Backpatching:
IF a > b GOTO L1
GOTO L2
L1: x = 10
GOTO L3
L2: x = 20
L3: // next statement
Example 3: `while` Loop
Code:
while (a > b) {
x = x + 1;
}
Final Code After Backpatching:
L1:
IF a > b GOTO L2
GOTO L3
L2: x = x + 1
GOTO L1
L3: // next statement
Example 4: `for` Loop
Code:
for (i = 0; i < 10; i++) {
x = x + i;
}
Final Code After Backpatching:
i=0
L1:
IF i < 10 GOTO L2
GOTO L3
L2: x = x + i
i=i+1
GOTO L1
L3: // next statement
Example 5: `do-while` Loop
Code:
do {
x = x + 2;
} while (x < 100);
Final Code After Backpatching:
L1: x = x + 2
IF x < 100 GOTO L1
Example 6: Nested `if-else` Statements
Code:
if (a > b)
if (a > c)
x = 10;
else
x = 20;
Final Code After Backpatching:
IF a > b GOTO L1
GOTO L4
L1: IF a > c GOTO L2
GOTO L3
L2: x = 10
GOTO L5
L3: x = 20
L5: // next statement
L4: // next statement
Example 7: `break` in Loops
Code:
while (x < 10) {
if (x == 5) break;
x = x + 1;
}
Final Code After Backpatching:
L1: IF x < 10 GOTO L2
GOTO L4
L2: IF x == 5 GOTO L3
x=x+1
GOTO L1
L3: GOTO L4
L4: // next statement
Example 8: `continue` in Loops
Code:
while (x < 10) {
if (x == 5) continue;
x = x + 1;
}
Final Code After Backpatching:
L1: IF x < 10 GOTO L2
GOTO L4
L2: IF x == 5 GOTO L1
x=x+1
GOTO L1
L4: // next statement
Example 9: `switch-case` Statement
Code:
switch (a) {
case 1: x = 10; break;
case 2: x = 20; break;
}
Final Code After Backpatching:
IF a == 1 GOTO L1
IF a == 2 GOTO L2
GOTO L3
L1: x = 10
GOTO L3
L2: x = 20
GOTO L3
L3: // next statement
Example 10: `if-else-if` Ladder
Code:
if (a > b)
x = 10;
else if (a > c)
x = 20;
else
x = 30;
Final Code After Backpatching:
IF a > b GOTO L1
IF a > c GOTO L2
GOTO L3
L1: x = 10
GOTO L4
L2: x = 20
GOTO L4
L3: x = 30
L4: // next statement