Anonymous

Compiler Design: Difference between revisions

From dankwiki
257 bytes added ,  05:52, 9 March 2009
no edit summary
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.
===Dominance===
 
We induce the reflexive 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.
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.