Code Split

Basic Block

The split and the generation of maximum basic code block has following rules:

• Find Entry
• Extend

This means, we need to first find all entry lines in the TAC code, then from the start of entry line to extend the code block until we can't extend it anymore.

Find Entry Line

A TAC line could be entry line of BB if it satisfies one of the following criteria:

• Is start of the code.
• Is line after conditional jump line. (Not the one after goto or halt)
• Is target line of other jump line (Jump type not limited).

Checkout TSU PDFP267 for more info.

Control Flow Graph

Use basic block as nodes, use goto relation as edges.

Dominator Sets

Basically, for a node $N$, the calculation of its dominator set $Dom(N)$ follows two rules:

• $Dom(N) \ni N$ (This node itself)
• $Dom(N) \supset \bigcap Dom(P_i)$ (Intersection of all dominator sets of direct parents of this node)

In above, $P_i$ is all direct parents of node $N$.

Loops

If there is an edge start from a node, pointing to any of its dominator nodes, then this edge is called back edge. It's quite easy to determine a loop once we find back edge.

Consider a back edge $n \to d$, then the following nodes all together constitute a natural loop (or loop):

• $n$: Itself.
• $d$: Dominator being pointed.
• All nodes that has a path to $n$ that do not contain $d$. (Do not contain $d$ actually make sure the node is inside the loop, checkout the example image below)

Note that loop node could also comes from the down side!

In diagram above, the back edge $4 \to 2$ is associated with a loop with node set:

$$ {4,2,3,7,5,6} $$

In which $5,6,7$ would sometimes be ignored.