Check out my first novel, midnight's simulacra!
Compiler Design: Difference between revisions
From dankwiki
| Line 19: | Line 19: | ||
''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. | ||
==Dataflow Analysis== | ==Dataflow/Dependency Analysis== | ||
One major purpose of dataflow analysis is observing safety constraints across reordering transformations. | One major purpose of dataflow analysis is observing safety constraints across reordering transformations. | ||
If a statement S writes to a variable V, S is said to ''define'' V. If statement S reads from a variable V, S is said to ''use'' V (the two are not mutually exclusive). A definition of v is ''killed'' between p1 and p2 if every path between them contains a definition of v; conversely, if a path exists from p1 to p2 which does not redefine v, and v has been defined on input to p1, it ''reaches'' p2 from p1. In this situation, v would furthermore be ''live'' at p1 (or immediately after p1, if p1 assigned it); a variable is live at a point if that instantiation of the variable might be used in the future. | If a statement S writes to a variable V, S is said to ''define'' V. If statement S reads from a variable V, S is said to ''use'' V (the two are not mutually exclusive). A definition of v is ''killed'' between p1 and p2 if every path between them contains a definition of v; conversely, if a path exists from p1 to p2 which does not redefine v, and v has been defined on input to p1, it ''reaches'' p2 from p1. In this situation, v would furthermore be ''live'' at p1 (or immediately after p1, if p1 assigned it); a variable is live at a point if that instantiation of the variable might be used in the future. | ||
| Line 37: | Line 37: | ||
* It's much easier to perform global value numbering optimizations in this representation (see Muchnick, p378-396) | * It's much easier to perform global value numbering optimizations in this representation (see Muchnick, p378-396) | ||
** Global value numbering is much more complete that basic common subexpression elimination | ** Global value numbering is much more complete that basic common subexpression elimination | ||
===Loops=== | ===Loops=== | ||
