In order to produce high-quality code, compilers have to rely on the results of static program analyses. To date, implementing these analyses has been difficult, expensive, and error-prone.
The PAG Program Analyzer Generator provides for a generation of efficient analyzers from concise specifications. PAG-generated interprocedural analyzers can be easily integrated into existing compilers.
PAG has been successfully used in an ESPRIT project to generate several analyzers (including alias analysis and constant propagation) for industrial grade ANSI-C and Fortran90 compilers. One of the main reasons it is currently widely used in university circles is because it generates efficient code (ANSI-C) and enables analyzers to be generated which are flexible, maintainable and portable.
In order to generate an analyzer using PAG, two specifications have to be written: one for the definition of the data structures, including the abstract domain, and one containing the analysis parameters, definition of the transfer functions and, optionally, some support functions.
From these files PAG generates C files and a compile script that creates a library which has to be linked to the compiler. A call to the analyzer has to be inserted in the compiler driver.
The company AbsInt offers commercial licenses of PAG. Look here.
There is a Web interface to the PAG system. It has restricted capabilities and a simplified specification mechanism. Just have a look at it.
To obtain the full PAG system a license is required:
- Use of PAG is free for universities. The license agreement for research purposes can be downloaded here (PDF, 25kB).
- For a commercial license agreement, please contact Florian Martin.
To decide whether you like to obtain a license you can take a look at the manual (PS, 990kB).
Thanks to Hanne Riis Nielson, I have a list of suggested exercises for PAG/WWW:
- Modify the live variables analysis to perform faint variables analysis: A variable is a faint variable if it is dead or if it is only used to calculate new values for faint variables; otherwise it is strongly live. As an example, in
x := 1; x := x-1; x := 2,xwill be faint after each of the three assignments (whereas it is dead after second and third assignment, but it is live after the first assignment).- A detection of signs analysis will model all the negative numbers by the symbol "-", zero by the symbol "0", and the positive numbers by the symbol "+". So the set
{-2,-1,1}will be modelled by the set{-,+}, that is an element ofP({-,0,+}). Modify the constant propagation analysis to perform a detection of signs analysis.- A parity analysis models all the even numbers by the symbol "even" and all the odd numbers by the symbol "odd". So the set
{0,2}will be modelled by{even}whereas{0,1}is modelled by{even,odd}. Modify the constant propagation analysis to perform a parity analysis.- Modify the constant propagation analysis to take the values of tests into account by having two transfer functions associated with boolean expressions, one to be used in the case the true branch is followed and one to be used in the case the false branch is followed.
- The upwards exposed uses analysis is the dual of the reaching definitions analysis: it determines for each definition of a variable which uses it might have.
- The copy-propagation analysis determines for each program point if there is a path to it from a copy assignment, say
x := y, where there are no assignments toy.- The dominator analysis determines for each assignment which other assignments it is dominated by: one assignment is dominated by another if every possible execution of the latter will be preceeded by an execution of the former.
The solutions for these exercises can be found here (with a proper password).
Keywords: abstract interpretation, compiler, compiler technology, PAG, program analysis, optimization, program analyzer generator, program optimization, static program analysis, Programmanalyse, statische Programmanalyse, Programmanalysatorgenerator, data flow analysis, compiler construction, tool, optimisation