ahoDragonBookBasic2007

This section is a pretty basic overview of basic blocks and control-flow graphs (CFGs). Should be mostly review so I skimmed this basically.

Basic blocks

In short, we divide up our intermediate code into basic blocks. Within a basic block, execution enters at the start of the block—its first instruction—and continues without halting, branching, or jumping until the last instruction of the block. These blocks form a control flow graph, with directed edges between BBs showing where control flow can go.

A leader is a start of a basic block.

Use and liveness

Often times we want to know when a var’s value will be used next. Let’s formally define the notion of a use of a name.

Let’s say statement assigns a value to variable x. If statement uses x, and execution flows from to without x being reassigned to, we say uses the value of x computed at statement . We also say that x is live at statement .

To find liveness, we go backwards from the end of a basic block. When starting, assume all variables are live. Whenever we hit an assignment, we set the assigned var to “not live” and its used operands to “live.”

Control flow graphs

CFGs connect basic blocks:

Nodes can have successors and predecessors. There is also entry and exit nodes.

Loops

A set of nodes forms a loop if contains a node called the loop entry, such that:

1. isn’t ENTRY.
2. No node in besides has a predecessor outside of .
3. Every node in has a non-empty path, completely within , to .