Check out my first novel, midnight's simulacra!
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: | ||
==Control Flow== | ==Control Flow== | ||
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). | |||
Revision as of 10:06, 9 March 2009
Control Flow
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).
