Anonymous

Compiler Design: Difference between revisions

From dankwiki
518 bytes added ,  05:06, 29 April 2009
Line 21: Line 21:
==Dataflow Analysis==
==Dataflow 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.
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.
* Liveness -- backwards-may analysis, set union as confluence operator
* Use-Define chain -- a use U of a variable, and all definitions of that variable which can reach it (those live relative to U)
* Def-Use chain -- a definition D of a variable, and all uses of that variable it can reach (those reached from D)


===Dependency Analysis===
===Dependency Analysis===