Check out my first novel, midnight's simulacra!
Compiler Design: Difference between revisions
No edit summary |
|||
| Line 7: | Line 7: | ||
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. | 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. | ||
The reflexive ''domination relation'' is induced 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. This relation gives rise to the [[Trees|dominator tree]], where nodes dominate all descendents in the tree. The start node s dominates all nodes, properly dominates all nodes but itself, and roots the dominator tree. | |||
* It should be obvious that a's preceding of b in the CFG is not necessary for even immediate dominance of b by a. | * It should be obvious that a's preceding of b in the CFG is not necessary for even immediate dominance of b by a. | ||
Loops can be discovered via domination analysis. | |||
Revision as of 10:52, 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.
The reflexive domination relation is induced 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. This relation gives rise to the dominator tree, where nodes dominate all descendents in the tree. The start node s dominates all nodes, properly dominates all nodes but itself, and roots the dominator tree.
- It should be obvious that a's preceding of b in the CFG is not necessary for even immediate dominance of b by a.
Loops can be discovered via domination analysis.
