DAG Basics

Here, DAG stands for directed acyclic graph.

• Leaves are initial values.
• Non-leaves are operators.
• Nodes could have a symbol list.

Node Visualize

Values are operators at the bottom of the node. Symbol list at the right side of the node. Node id write inside the node.

TAC to DAG

Single TAC

Example of B:=A and E:= C op D

Checkout TSUPDFP284 for more info.

TAC Sequence

To convert a TAC sequence into a DAG Node Forest, we should use following rules.

Define function $node(name)$, which return $id$ that most recently be associated with variable name $name$. E.g.: $node(A)=n_1$

If you don’t want to goes into detail, you could checkout the conclusion at below.

x := y

1. Create $node(y)$ if not exists (else reuse).
2. Remove old $x$ ref from $node(x)$
3. Add $x$ to symbol list of $node(y)$

x := op y

1. Create $node(y)$ if not exists. 2. $node(y)$ is not constant: Create new node $n$ with $op$ and child $node(y)$ if not exists (else reuse), then add $x$ to symbol list of $n$. 3. $node(y)$ is constant: Consider result is $x_0$, create a node with initial value $x_0$ if exists (else reuse)
2. Delete $node(y)$ if it’s created by first step and it points to constant.

x := y op z

Similar to x := op y

---

Conclusions

In conclusion, we consider several things when creating forests:

Constant Propagation

• Directly calculate initial value of the new node whenever possible.
• Remove children constant node after use if they are first created in this process.

Reuse If Possible

If there’s already a node with the same op/init and same child/children you want to create, then directly use it. (Just move $X$ to symbol list of that node)

Removing Old References

When a variable name $X$ is associated to the new node, remember to remove the old association. In this case, all variable name should only be associated with at most one single node at a time.

Note when there are two children, both of them need to be constant to trigger this rule.

DAG to TAC

Super simple, just reconstruct TAC from graph in topology order. (Tips: It could be proved you could achieve this order by creating TAC based on the order when the node has been created)