About Directed Acyclic Graph
For Basic Blocks
DAG (for a Basic Block)
• Leaves labeled by unique identifiers
– constants or variables
• Interior nodes labeled by operator symbols
• Nodes carry sequence of identifiers for labels
– sequence may be empty
– these are identifiers deemed to be holding the
value of the expression identified by the node
(i.e., the operator)
Creation of DAG for Basic Block
• Starting with an empty DAG
– process statements within block one at a time
– thereby adding to and/or altering DAG
• Every identifier in Basic Block ultimately gets
associated with some node of the DAG
– which may change
– found through function node(identifier)
• returns null if identifier not yet been associated with
any node
If next instruction is x := y op z
• If node(y) is null, a new leaf node labeled y is created
– subsequent node(y) made to point to that
• If node(z) is null, a new leaf node labeled z is created
– subsequent node(z) made to point to that
• A node labeled ‘op’ whose left child is node(y) and
right child is node(z), is searched for
– such a node is created if not found
– in either event, n, node created/ found used in next step
• x is deleted from associated identifiers for node(x) and
then x is appended to n found in previous step
Example Basic Block
Address 3-Address Code
(1) t1 := 4 * i
(2) t2 := a[t1]
(3) t3 := 4 * i
(4) t4 := b[t1]
(5) t5 := t2 * t4
(6) t6 := prod * t5
(7) prod := t6
(8) t7 := i + 1
(9) i := t7
(10) if i < 20 goto (3)
DAG Creation Intermediate Stages
Newly created
t1 := 4 * i * t1 Found after
search
4 i
t2 := a[t1] [] t2
* t1
a 4 i
DAG Creation Intermediate Stages
t3 := 4 * i [] t2 [] t4
t4 := b[t3]
* t1, t3
a b 4 i
Created t7
t7 := i + 1 Found i
+ t7, i
i := t7
i0 1
Found t7 then updated i
DAG for Basic Block
+ t6, prod
prod0 * t5
[] t2 [] t4 <= (3)
20
* t1, t3 + t7, i
a b 4 i0 1
Note: Identifier leaves with suffixes indicate older nodes that got deleted
Basic Block and DAG
Address 3-Address Code
(1) t1 := 4 * i + t6, prod
(2) t2 := a[t1]
(3) t3 := 4 * i * t5
prod0
(4) t4 := b[t1]
(5) t5 := t2 * t4
[] t2 [] t4 <= (3)
(6) t6 := prod * t5
(7) prod := t6 20
(8) t7 := i + 1 * t1, t3 + t7, i
(9) i := t7
(10) if i < 20 goto (3) a b 4 i0 1
