9,579
edits
Compiler Design: Difference between revisions
From dankwiki
→Dataflow Analysis
| Line 22: | Line 22: | ||
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. | ||
* Liveness -- backwards-may | * Reaching analysis -- forwards dataflow problem, 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) | ** Copy propagation eliminates assignment statements, when safe (when modification of upwards-exposed uses of the target may be modified) | ||
* Def-Use chain -- a definition D of a variable, and all uses of that variable it can reach (those reached from D) | * Liveness analysis -- backwards-may dataflow problem, 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) | |||
** Common subexpression elimination lexically matches subexpressions, and can preserve them in registers | |||
===Intermediate Representations=== | |||
* SSA (Single Static Assignment) and CPS (Continuation-Passing Style) are equivalent (Kelsey 1995, Appel 1998 '''FIXME full citations!''') | |||
* SSA makes use-def chains explicit, and restricts them to a single element each | |||
* 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 | |||
===Dependency Analysis=== | ===Dependency Analysis=== | ||
