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