Check out my first novel, midnight's simulacra!
Compiler Design: Difference between revisions
From dankwiki
No edit summary |
|||
| Line 10: | Line 10: | ||
* 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 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. | ||
* | * Until the the vector is empty, use the last node of the vector to begin traversing the transpose graph. Removing each node reached. These disconnected traversals partition the graph into strongly connected components. | ||
==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] | ||
