Basic Blocks and DAG-Based Optimization for Intermediate Code

Verified Sources

Nov 4, 2026

In compiler design, a basic block is the main unit used to build a control-flow graph (CFG) and to perform local optimizations. A basic block has:

single entry: control can enter only at the first statement,
single exit: execution leaves only at the last statement (e.g., via a jump/branch/return),
no internal jumps/branch targets except through the entry.

In three-address-code (TAC), basic blocks are identified by choosing leaders: the first instruction, the target of any jump/branch, and the instruction immediately following any jump/branch. The statements from one leader up to (but not including) the next leader form a basic block. This is the standard basis for CFG construction and many compiler optimizations.

For optimizing within a basic block, a DAG is commonly constructed to capture equivalence of computations and dependencies while ensuring no cycles. The DAG nodes typically represent:

operators for computed expressions,
variables (leaves/labels),
optional copy edges for assignments.

This enables:

common subexpression elimination,
constant folding,
and dead code elimination when liveness information is known.

Important: The DAG-based optimization and dead-code elimination are local to the block; they do not require CFG-wide global analysis.

Basic Blocks and DAG-Based Optimization (Intermediate Code)

1) What “basic block” means in the graph representation of intermediate codes

A control-flow graph (CFG) represents possible execution order. Each node is a basic block, and an edge exists if control can flow from one block to another.

Within a basic block, we assume:

every statement is executed in order (no branches in the middle),
therefore, local dataflow (like expression reuse) can be performed efficiently.

2) Constructing a DAG for a given basic block

To build a DAG from TAC, process statements sequentially and:

For each statement of the form x = y op z:
- create an operator node (op, y, z) if it doesn’t exist,
- otherwise reuse the existing operator node,
- then associate/label variable x with that operator node (the “value” computed).
For assignments x = y:
- create a copy relation (alias) from x to the same DAG node as y.

3-address-code variants are well-suited because each statement computes exactly one result.

Mermaid intuition

Construct DAG for the basic block from the given three-address code

1
Step 1
Given TAC: (1) $d=b*c$ , (2) $e=a+b$ , (3) $b=b*c$ , (4) $a=e-d$ . Expressions are $(b*c)$ , $(a+b)$ , and $(e-d)$ ; note the redefinition of $b$ affects which $(b*c)$ refers to.
2
Step 2
Create leaves (variable nodes) for $a, b, c$ . Each operator node will reference the current DAG value nodes corresponding to the operands.
3
Step 3
Create operator node $n_{bc}$ for $(\* , b, c)$ . Label $d$ to point to $n_{bc}$ . The available value of $b$ used here is the original $b$ (before statement 3).
4
Step 4
Create operator node $n_{ab}$ for $(+ , a, b)$ . Label $e$ to point to $n_{ab}$ . Here $b$ is still the original $b$ (since statement 3 hasn’t happened).
5
Step 5
This recomputes $b*c$ but with $b$ updated on the left. Since the right side uses the current $b$ value (which is still the original $b$ at this point), the expression $(b*c)$ is equivalent to the earlier one in this block; therefore reuse $n_{bc}$ and relabel the variable $b$ to point to $n_{bc}$ again.
6
Step 6
Create operator node $n_{ed}$ for $(- , e, d)$ . Label $a$ to point to $n_{ed}$ . Also note $e$ and $d$ refer to their labeled nodes from earlier: $e \to n_{ab}$ and $d \to n_{bc}$ .
7
Step 7
Operator nodes: $n_{bc}$ for $(b*c)$ , $n_{ab}$ for $(a+b)$ , $n_{ed}$ for $(e-d)$ . Variable labels at the end: $a \to n_{ed}$ ; $b \to n_{bc}$ (though $b$ is overwritten later only here); $c$ remains a leaf input; $d$ and $e$ remain labels for their computed nodes as long as used.

DAG structure (explicit)

Below is a clean DAG depiction with the final labeling after processing all statements.

Key points:

The operator $(b*c)$ is reused: both statement (1) and statement (3) compute the same expression with the same operand values at that time, so the DAG collapses them.
The final result is $a = e - d$ ; therefore the computation depends on $(a+b)$ and $(b*c)$ .

Optimize the three-address code assuming only $a$ is live on exit from the block

1
Step 1
Given: only $a$ is live on exit. Therefore, any computation whose result is not needed to compute the final live $a$ can be removed.
2
Step 2
Statement (4) computes $a$ from $e$ and $d$ . So we must know how $e$ and $d$ are obtained: $e$ comes from (2), and $d$ comes from (1).
3
Step 3
Statement (3) reassigns $b=b*c$ , but statement (4) uses $d$ (not $b$ ). Since $d$ was computed at (1) and is not overwritten, statement (3) does not affect the value of $a$ .
4
Step 4
Drop statement (3) because its result ( $b$ after stmt3) is never used to compute the final live variable $a$ .
5
Step 5
Even after dropping (3), we still keep (1) and (2) as they are necessary operands for (4). No further algebraic simplification is possible without additional information.
6
Step 6
The optimized code is: $d = b*c$ $e = a+b$ $a = e-d$

How DAG reuses expressions correctly in a block

When an expression like $(b*c)$ appears multiple times, reuse the same DAG operator node only if the operands represent the same values at that program point (i.e., no intervening redefinition changes their meaning). In this TAC, $b$ is not changed until the left side of statement (3), so the right side of (3) uses the same $b$ as (1).

Dead-code elimination depends on liveness, not on “harmless looking” redefinitions

Statement (3) looks redundant, but you must confirm whether its computed value is used. Here, $b$ is redefined at (3), yet the final live variable $a$ depends only on $d$ and $e$ , so (3) is dead. In other blocks, redefinitions can feed later computations and would not be removable.

Local optimization pipeline within a single basic block

Form basic block

Partition TAC into leaders/basic blocks (single entry/exit)."

Build expression DAG

Create operator nodes for expressions and label variables to those nodes."

Mark needed values via liveness

With only $a$ live on exit, mark DAG nodes needed to compute $a$ ."

Regenerate optimized TAC

Emit only the statements producing marked nodes, using DAG reuse to avoid duplicates."

Knowledge Check

Question 1 of 3

Q1Single choice

A basic block in intermediate code is best described as a sequence with:

A single entry point and no branches/jumps except possibly at the end

Multiple entry points but exactly one exit

Exactly one statement with no dependencies

A graph node containing only operator nodes, not variables

Explore Related Topics

Three-Address Code: Operand Count and Meaning

Control Unit of the Basic Computer: Block Diagram and Control Timing Diagrams

Which Optimization Removes Repeated Computations?

Browse all research articles