Check out my first novel, midnight's simulacra!
Compiler Design: Difference between revisions
From dankwiki
No edit summary |
|||
| Line 9: | Line 9: | ||
The antisymmetric, transitive, 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. | The antisymmetric, transitive, 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 (it is important to note that this refers to loops in the generated code, not loop constructs of the source language, and furthermore that all possible loops will be found (ie, unstructured loops constructed from C <tt>goto</tt>s)). Discover all strongly-connected subgraphs of the CFG (subgraphs where, for each vertex, a path ('''not''' necessarily an edge) exists from that vertex to all other nodes of the subgraph); if a subgraph contains a node dominating all that subgraph's nodes, the subgraph is a loop. The trivial case is, of course, a statement which jumps to itself, ala the BASIC program <tt>10 GOTO 10</tt>. Implementation via [[Kosaraju's Algorithm]] is simple, with O(|V|+|E|) time complexity using graph encoding and O(N<sup>2</sup>) time complexity using adjacency matrices: | Loops can be discovered via domination analysis (it is important to note that this refers to loops in the generated code, not loop constructs of the source language, and furthermore that all possible loops will be found (ie, unstructured loops constructed from C <tt>goto</tt>s)). Discover all strongly-connected subgraphs (SCCs) of the CFG (subgraphs where, for each vertex, a path ('''not''' necessarily an edge) exists from that vertex to all other nodes of the subgraph); if a subgraph contains a node dominating all that subgraph's nodes, the subgraph is a loop. The trivial case is, of course, a statement which jumps to itself, ala the BASIC program <tt>10 GOTO 10</tt>. Implementation via [[Kosaraju's Algorithm]] is simple, with O(|V|+|E|) time complexity using graph encoding and O(N<sup>2</sup>) time complexity using adjacency matrices: | ||
* Perform a recursive depth-first traversal of the graph starting from s. Each time you return, add that node onto an auxiliary vector. Upon the traversal's completion, this vector sorts the nodes topologically. | * Perform a recursive depth-first traversal of the graph starting from s. Each time you return, add that node onto an auxiliary vector. Upon the traversal's completion, this vector sorts the nodes topologically. | ||
* Until the the vector is empty, use the last node of the vector to begin traversing the transpose graph. | * Until the the vector is empty, use the last node of the vector to begin traversing the transpose graph. Remove the path from the vector; these paths partition the graph into SCCs. | ||
==See Also== | ==See Also== | ||
* [http://scienceblogs.com/goodmath/2007/10/computing_strongly_connected_c.php Computing Strongly Connected Subgraphs] from [http://scienceblogs.com/goodmath Good Math, Bad Math] | * [http://scienceblogs.com/goodmath/2007/10/computing_strongly_connected_c.php Computing Strongly Connected Subgraphs] from [http://scienceblogs.com/goodmath Good Math, Bad Math] | ||
