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