Anonymous

Compiler Design: Difference between revisions

From dankwiki
108 bytes added ,  05:55, 29 April 2009
Line 18: Line 18:
Kosaraju's algorithm is improved upon by [[Tarjan's Algorithm]] and [[Gabow's Algorithm]].
Kosaraju's algorithm is improved upon by [[Tarjan's Algorithm]] and [[Gabow's Algorithm]].
''Natural loop'' identification proceeds via identification of ''back edges'' (edges from a node b to a node a, where a dominates b). A loop is associated with every such back edge; if a backedge exists from b to a, the associated loop is entered at a, and consists additionally of all nodes which can reach b without going through a. Similarly, a loop is associated with the target of every back edge, this being the union of all such backedges' associated natural loops.
''Natural loop'' identification proceeds via identification of ''back edges'' (edges from a node b to a node a, where a dominates b). A loop is associated with every such back edge; if a backedge exists from b to a, the associated loop is entered at a, and consists additionally of all nodes which can reach b without going through a. Similarly, a loop is associated with the target of every back edge, this being the union of all such backedges' associated natural loops.
===Dead code elimination===
Control flow analysis by itself is sufficient to remove some unreachable code.


==Dataflow/Dependency Analysis==
==Dataflow/Dependency Analysis==