Check out my first novel, midnight's simulacra!
Compiler Design: Difference between revisions
From dankwiki
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. |