Compiler Design: Difference between revisions
(Created page with '==Control Flow== * A control flow graph is a multigraph G defined by vertices corresponding to basic blocks, and edges corresponding to transitions between those basic blocks. **...')
|Line 1:||Line 1:|
is a , and basic block sequence of instructions that can only be entered via the first (''leader'') instruction, and only exited by the last instruction , is ). block a to b if and only if:
* either b immediately follows a, and a does not end in an unconditional branch,
* or a ends in a branch, b is a target
that an indirect branch
Revision as of 06:06, 9 March 2009
The first instruction of the program is a leader, as is every target of a branch, and every instruction following a branch (including conditional branches and procedure returns) is a leader. A basic block is the largest sequence of instructions that can only be entered via the first (leader) instruction, and only exited by the last instruction (terminator, although this is not common terminology). A basic block a flows to b if and only if:
- either b immediately follows a, and a does not end in an unconditional branch,
- or a ends in a branch, of which b is a potential target.
Note that an indirect branch, without context information, trivializes all blocks (every instruction becomes a leader) and flows to them all from at least that point (an arborescence is formed)!
The directed multigraph defined by interpreting basic blocks as vertices, and flow relationships as edges, yields its control flow graph (CFG).