Check out my first novel, midnight's simulacra!
Compiler Design: Difference between revisions
| Line 1: | Line 1: | ||
==Control Flow== | ==Control Flow== | ||
==Control Flow Graph== | |||
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: | 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, | * either b immediately follows a, and a does not end in an unconditional branch, | ||
| Line 5: | Line 6: | ||
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)! | 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). | The directed multigraph defined by interpreting basic blocks as vertices, and flow relationships as edges, yields its control flow graph (CFG). A start node exists for each CFG, corresponding to the basic block whose header is the first instruction of the program. | ||
===Dominance=== | |||
We induce the domination relation on vertices of a CFG, and thus basic blocks of the underlying program. A vertex a ''dominates'' b (a <= b) if every path from the start node s to b passes through a. A vertex a ''properly dominates'' b (a < b) if a dominates and is not equal to b. A vertex a ''directly/immediately dominates'' b (a <d b) if a properly dominates b, and a dominates no vertex c that dominates b. | |||
* It should be obvious that a's preceding of b in the CFG is not necessary for even immediate dominance of b by a. | |||
Revision as of 10:16, 9 March 2009
Control Flow
Control Flow Graph
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). A start node exists for each CFG, corresponding to the basic block whose header is the first instruction of the program.
Dominance
We induce the domination relation on vertices of a CFG, and thus basic blocks of the underlying program. A vertex a dominates b (a <= b) if every path from the start node s to b passes through a. A vertex a properly dominates b (a < b) if a dominates and is not equal to b. A vertex a directly/immediately dominates b (a <d b) if a properly dominates b, and a dominates no vertex c that dominates b.
- It should be obvious that a's preceding of b in the CFG is not necessary for even immediate dominance of b by a.
