pips@cri.mines-paristech.fr
Techniques developed for PIPS can be re-used for signal processing code written in C, because pointers, data structures and dynamic allocation are not used much, and for Java code optimization because array boundary checking must be minimized conservatively.
PIPS is a free open workbench which has been used as support to develop new analyses or program transformations by several teams from CEA-DAM, Southampton University, SRU, ENST Bretagne and ENS Cachan. These new developments benefit at no cost from the general infrastructure and from already available analyses and transformations. PIPS has also been used to develop a HPF prototype compiler and to study optimizations for HPF.
PIPS is not primarily designed to support compiler back-end
research like SUIF but is much better as a Fortran source-to-source
tool because the data types (e.g. complex) the code structures, the
comments and, to some extent, the initial statement numbers are preserved.
What is in Pips ?
INPUTS
|
OUTPUTS
|
PIPS was initially designed as an automatic parallelizer for scientific programs. It takes as input Fortran 77 codes and emphasizes interprocedural techniques for program analyses. PIPS specific interprocedural analyses are precondition and array region computations. PIPS automatically computes affine preconditions for integer scalar variables which are much more powerful than standard constant propagation or forward substitution as shown below:
I = 1
N = 10
J = 3
C P(I,J,N) {I==1, J==3, N==10}
DO WHILE (I.LT.N)
C P(I,J,N) {N==10, I<=9, 5<=2I+J, J<=3}
PRINT *, I
IF (T(I).GT.0.) THEN
J = J-2
ENDIF
I = I+1
ENDDO
C P(I,J,N) {N==10, I==10, 5<=2I+J, J<=3}
PRINT *, I, J
|
PIPS also computes several kinds of polyhedral array regions (READ,
WRITE, IN and OUT) which are used for array and partial array
interprocedural privatization as well as for interprocedural
parallelization. Here, for instance, array TI is
automatically privatized in spite of its initialization thru the call to
PVNMUT:
!$OMP PARALLEL DO PRIVATE(J)
DO K = K1, K2
!$OMP PARALLEL DO PRIVATE(TI(1:3))
DO J = J1, JA
CALL PVNMUT(TI)
T(J,K,NN) = S*TI(1)
T(J,K,NN+1) = S*TI(2)
T(J,K,NN+2) = S*TI(3)
ENDDO
ENDDO
|
As mentioned above, PIPS can also be used as a reverse engineering
tool. Region analyses provide useful summaries of procedure effects, while
precondition-based partial evaluation and dead-code elimination reduce
code size. Cloning has also be used successfully to split a routine
implementing several functionalities into a set of routines implementing
each exactly one functionality. Automatic cleaning of declarations is
useful when commons are over-declared thru include statements.
Analyses and Transformations
All analyses and transformations are listed in the documentation of the PIPS API and of PIPS interfaces. Static analyses compute call graphs, memory effects, use-def chains, dependence graphs, interprocedural checks, transformers, preconditions, continuation conditions, complexity estimation, reduction detection, array regions (read, write, in and out, may or exact), aliases and complementary sections. The results of analyses can be displayed with the source code, with the call graph or with an elapsed interprocedural control flow graph, as texts or as graphs. The dependence graphs can also be displayed either as texts or graphs.
Several parallelization algorithms are available, including Allen&Kennedy, as well as automatic code distribution, including a prototype HPF compiler, hpfc. Different views of the parallel outputs are available: HPF, OpenMP, Fortran90, Cray Fortran. Furthermore, the polyhedral method of Pr. Feautrier also is implemented.
Program transformations include loop distribution, scalar and
array privatization, atomizers (reduction of a statements to a three-address
form), loop unrolling (partial and full), strip-mining, loop interchange,
partial evaluation, dead-code elimination, use-def elimination, control
restructuring, loop normalization, declaration
cleaning, cloning, forward substitution and expression optimizations.
Workbench
PIPS is based on linear algebra techniques for analyses, e.g. dependence testing, as well as for code generation, e.g. loop interchange or tiling.
Analyses and transformations are driven by a make system, (pipsmake) which enforces consistency across analyses and modules, and results are stored for future interprocedural use in a database by a resource manager (pipsdbm). The workbench is made of phases that are called on demand to perform the analyses or transformations required by the user. Thus interprocedural requests are very easy to formulate: only the final in demand result must be specified.
PIPS is built on top of two other tools. The first one is Newgen which manages data structures a la IDL. It provides basic manipulation functions for data structures described in a declaration file. It supports persistent data and type hierarchies. An introductory paper (in English) and a tutorial (in French) are available.
All PIPS data-types are based on Newgen. A description of PIPS internal representation is available in a technical report. The mapping of Fortran onto the PIPS internal representation is described in Technical Report TR E/105, Section 2.
The second tool is the Linear C3 library which handles vectors, matrices, linear constraints and structures based on these such as polyhedra. The algorithms used are designed for integer and/or rational coefficients. This library is extensively used for analyses such as dependence test, precondition and region computation, and for transformations, such as tiling, and for code generation, such as send and receive code in HPF compilation. The Linear C3 library is a joint project with IRISA and PRISM laboratories, partially funded by CNRS. IRISA contributed an implementation of Chernikova algorithm and PRISM a C implementation of PIP (Parametric Integer Programming).
Five user interfaces are available: a Shell interface (Pips), a line interface (Tpips user manual and tpips man) and three window-based interfaces. The three X-window interfaces Wpips, Epips and Jpips to the workbench are the best suited for new users (see the wpips man and WPips and EPips user manual). The last interface is Java based but not yet available. Click here for a Wpips screen snapshot.
.
History
PIPS has been developed at CRI
since 1988, thru several research projects funded by the French DoD
(DRET), the French NSF (CNRS) and the European Union (ESPRIT
programs). The initial design was made by Rémi TRIOLET,
François IRIGOIN and Pierre JOUVELOT. This initial design has
proved good enough since then and has not required any major change. The
overview paper presented at ICS'91 still
is up-to-date, although major functionalities have been added since.
Pips Bibliography
PIPS OVERVIEWS
|
The current research objectives are:
Ten years after its inception, PIPS as a workbench is still alive and well. PIPS provides a robust infrastructure for new experiments in compilation, program analysis, optimization, transformation and parallelization. The PIPS developer environment is described in a technical report but it also is possible to develop new phases on top of but outside of PIPS since all (in fact, most...) PIPS data structures can be reloaded using Newgen primitives from C or Lisp programs.
PIPS is written in C and developed under Linux. PIPS
can also be used under Solaris, under
AIX and Digital UNIX. Two versions are available: Integer values are
represented either by 32-bit or by 64-bit words. The source code is
available on request and executables are
downloadable.
Maintenance and Support
Send your comments, questions and requests to pips-support@cri.mines-paristech.fr.