Compiler Design: Difference between revisions

From dankwiki
(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==
* A control flow graph is a multigraph G defined by vertices corresponding to basic blocks, and edges corresponding to transitions between those basic blocks.
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:
** Basic block: Largest sequence of instructions that can only be entered via the first (''leader'') instruction, and only exited by the last instruction. 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. An edge exists from block a to block b if and only if:
* either b immediately follows a, and a does not end in an unconditional branch,
*** 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.
*** or a ends in a branch, and b is a target (note that an indirect branch might completely fragment the CFG!).
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 06: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).