Check out my first novel, midnight's simulacra!

Compiler Design: Difference between revisions

From dankwiki
No edit summary
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.
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.
===Dependency Analysis===
* "[http://portal.acm.org/citation.cfm?id=255129.255158 On the perfect accuracy of an approximate subscript analysis test]" (Klappholz, Psarris, Kong, 1990) analyzes the GCD and Banerjee inequalities, explaining the crappiness of the former and general robustness of the latter. "[http://portal.acm.org/citation.cfm?id=110518.110525&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 On the Accuracy of the Banerjee Test]" (same authors, 1991) suggests improvements on the Banerjee test.
* "[http://portal.acm.org/citation.cfm?id=143129&dl=GUIDE&coll=GUIDE&CFID=31575025&CFTOKEN=24090323 Eliminating False Data Dependencies using the Omega Test]" (Pugh, Wonnacott, 1992) moves from integer programming-based ([http://mathworld.wolfram.com/DiophantineEquation.html Diophantine]) solutions to a subclass of the [http://en.wikipedia.org/wiki/Presburger_arithmetic Presburger formulae].
===Loops===
===Loops===
* Primary references: Allen/Kennedy ch. 2-3, Muchnick ch. 14
* Primary references: Allen/Kennedy ch. 2-3, Muchnick ch. 14
* Statement order within a loop is never a factor in preserving loop-carried dependencies
* Statement order within a loop is never a factor in preserving loop-carried dependencies


==Dependency Analysis==
===Pointers/Aliasing===
* "[http://portal.acm.org/citation.cfm?id=255129.255158 On the perfect accuracy of an approximate subscript analysis test]" (Klappholz, Psarris, Kong, 1990) analyzes the GCD and Banerjee inequalities, explaining the crappiness of the former and general robustness of the latter. "[http://portal.acm.org/citation.cfm?id=110518.110525&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 On the Accuracy of the Banerjee Test]" (same authors, 1991) suggests improvements on the Banerjee test.
* Why people still write in FORTRAN instead of C
* "[http://portal.acm.org/citation.cfm?id=143129&dl=GUIDE&coll=GUIDE&CFID=31575025&CFTOKEN=24090323 Eliminating False Data Dependencies using the Omega Test]" (Pugh, Wonnacott, 1992) moves from integer programming-based ([http://mathworld.wolfram.com/DiophantineEquation.html Diophantine]) solutions to a subclass of the [http://en.wikipedia.org/wiki/Presburger_arithmetic Presburger formulae].
* Type-based analysis (see [[ANSI C99]]'s <tt>restrict</tt> keyword), [[gcc]]'s <tt>-fstrict-aliasing</ii> directive)


==Memory Hierarchy==
==Memory Hierarchy==
Line 62: Line 67:
* [http://scienceblogs.com/goodmath/2007/10/computing_strongly_connected_c.php Computing Strongly Connected Subgraphs] from [http://scienceblogs.com/goodmath Good Math, Bad Math]
* [http://scienceblogs.com/goodmath/2007/10/computing_strongly_connected_c.php Computing Strongly Connected Subgraphs] from [http://scienceblogs.com/goodmath Good Math, Bad Math]
* The [http://llvm.org/ LLVM] Compiler Infrastructure Project at [http://www.cs.uiuc.edu/ UIUC]
* The [http://llvm.org/ LLVM] Compiler Infrastructure Project at [http://www.cs.uiuc.edu/ UIUC]
* GCC's [http://gcc.gnu.org/projects/tree-ssa/ SSA for Trees] project page