%%
%% $Id$
%%
%% Copyright 1989-2016 MINES ParisTech
%%
%% This file is part of PIPS.
%%
%% PIPS is free software: you can redistribute it and/or modify it
%% under the terms of the GNU General Public License as published by
%% the Free Software Foundation, either version 3 of the License, or
%% any later version.
%%
%% PIPS is distributed in the hope that it will be useful, but WITHOUT ANY
%% WARRANTY; without even the implied warranty of MERCHANTABILITY or
%% FITNESS FOR A PARTICULAR PURPOSE.
%%
%% See the GNU General Public License for more details.
%%
%% You should have received a copy of the GNU General Public License
%% along with PIPS.  If not, see <http://www.gnu.org/licenses/>.
%%
\documentclass{article}

\usepackage[latin1]{inputenc}
\usepackage{newgen_domain}

%%\input{/usr/share/local/lib/tex/macroslocales/Dimensions.tex}

\title{PIPS: Mechanism for the Automatic Consistency Management and 
Phase Activation (pipsmake)}
\author{François Irigoin \\
    Pierre Jouvelot \\
    Rémi Triolet\\
\\
    CAI, École des mines de Paris}

\begin{document}
\maketitle
%% \sloppy

\section*{Introduction}

The interprocedural and interactive nature of PIPS make necessary the
management of pieces of information linked to a particular module and
phase, i.e. an analysis or a transformation. These pieces of
information, called resources, may be reused by future phases as long
as they are consistent, else they must be recomputed. This is true for
any compiler but worse when interprocedural analyses and
transformations since inter-module dependencies are created.

The consistency management and recomputation of these pieces of
information, i.e. resources, could have been spread out in each of the
transformations and analyses of PIPS. It seemed much better to
centralize in one library the management of dependencies between
phases and the maintenance of the coherence between different
pieces of information, i.e. resources.

The {\tt pipsmake} library offers two principal entry points: {\tt
  make} and {\tt apply}. The first one is used to request a particular
piece of information in a consistent state, without having to worry
about the calculation of all the different resources which are
necessary for its calculation. The second one is used to apply a
particular compiler pass, also known as a {\em rule}. A rule includes
not only the name of the pass, but also the list of resources
necessary for the execution of the pass and the list of resources
generated by the pass. A resource is linked to a module and to a kind:
for instance the \verb/CODE/ of function \verb/foo/.

When a given resource must be found or recomputed, the set of rules
are scanned to find out which rule produces the resource, and which
secondary resources are necessary to compute the requested resource.

When several rules allow the calculation of a particular resource, 
an activation mechanism is used to define the default rule. 
This is indispensible to be able to treat the recursive calls 
produced by the successive manifestation of rules without having to 
request too much information concerning user partameters. 

By default, the first rule producing a particular resource 
is considered activated. When several rules are available to produce 
the same resource, this resource must be the only one produced
by this rule. In this manner it is coherent to activate rules dynamically.

A set of rules and particular resources may be statically defined 
in a file named {\tt pipsmake.rc}. The library 
{\tt pipsmake} contains the modules which perform the reading of such a file 
to initialize a a set of rules in memory and to write to
disc a set of rules in a format compatible with their future
read. 

This is automatically made possible by certain interactive PIPS interfaces,
on condition that the available alternative rules 
as well as the resource they produce have an alias name.

We present successively the structures of the data used 
to store in memory a set of derivation rules, virtual resources 
and real resources.  

\section{Set of derivation rules}

\domain{Makefile = rules:rule* x active\_phases:string*}
{The domaine {\tt makefile} is used by the high-level driver 
to describe between the different Pips phases. A
{\tt Makefile} is a list of rules ({\tt rule}), each rule 
describing one of the Pips phases. In other words, the {\tt Makefile} gives the 
list of phases active at the present instant {\tt
active\_phases}. Remember that each type of resource may 
possibly be produced by different phases, but that only one 
phase is usable at any given instant. 

Note, the new fonctionalities for multiple resource production 
imply an ambiguity concerning the notion of active rule; 
active nature of the active rules being possible for a subset of 
rules which they produce (in particular in the case of patially cyclical
rules). }

\section{Definition of a particular rule}

\domain{Rule = phase:string x required:virtual\_resource* x produced:virtual\_resource* x preserved:virtual\_resource* x modified:virtual\_resource* x pre\_transformation:virtual\_resource* x  post\_transformation:virtual\_resource*}
{The domain {\tt rule} permits the description of the actions of the phases of
  Pips on the resources managed by pips-db. Each phase
  requires that certain resources by available disponibles ({\tt
  required}), it begins by executing potential 
  transformations ({\tt pre\_transformation}), then produces one or 
  several resources ({\tt produced}), and modifies others ({\tt
  modified}). The difference between the resources produced and 
  and those modified permit the driver to successively manifest the phases on the 
  correct order. 
  Post processing phases are stored in {\tt post\_transformation}

The transformation phases act on the code of the modules, which 
generally implies that the information which describe this module
are lost. Yet, certain among them do transformations
which are so minor that certain descriptions are preserved ({\tt
preserved}). This is notably the case of the privatization which 
all these descriptions preserved. Here is a list of the Pips phases.
\begin{description}
\item[parser] syntaxic and calculation analysis of the control graph,
\item[linker] editing of links,
\item[proper-effects] calculation of the proper effects of the instructions,
\item[cumulated-effects] calculation of the cumulated effects of the instructions, 
\item[usedef] calculation of the used-def chains and the def-use chains,
\item[privatizer] variable privatization ,
\item[dgkennedy] calculation of the dependency graph with the {\em niveaux de
Kennedy}, 
\item[dgwolfe] calculation of the dependency graph with the {\em vecteurs
de direction de Wolfe},
\end{description}
}

\section{Definition of a Virtual Resource}

The virtual resources are the variables which may be instantiated 
in a real resource or in a list of real resources.

\domain{Virtual\_resource = name:string x owner }
{The domain {\tt virtual\_resource} permits the designation of a resource
read or modifie'd by a phase descibing precicely in addition to the nature of the 
resource ({\tt datum}) if the resource accessed is that which is attatched to the 
module, a program, to the modules accessed by the module to which the phase 
is apples or that which called it ({\tt owner}). Here is the list
of all the resources which Pips may be able to calculate.

\begin{description}

\item[source] file source of a module Fortran; result of 
the initialization;

\item[code] module code with structured control graph; 
result of the control and parsing action;

\item[entities] program entites; resultat of the initialisation, of
the parser and the linker;

\item[callees] modules callede directely by a module; result of
the linker; 

\item[proper-effects] proper effect of the instructions for a module; the
term {\em propre} signifies that thg effets of the instruction blocs 
produced (loops, tests, ...) are not taken into account; result
of proper-effects; 

\item[cumulated-effects] cumulated effect of the instructions for a 
module; the term {\em cumulé} signifies that the effects of the instruction blocs 
prodiced (loops, tests, ...) are taken into account; 
result ofe cumulated-effects; 

\item[sdfi] {\em summary data flow information} of a module; it is an
abstract of the cumlulated effets of the module's instruction bloc; produce an abstraction of
the effets consist of the elimination of the effets of the local variables of 
the module and, in th ecase of tables, the globalization of each effect 
erasing the expressions of indices in the process; the result of cumulated-effects;

\item[chains] {\em use-def} and {\em def-use chains} of a module;
result of usedef;

\item[dgkennedy] dependancy graph with the {\em niveaux de
Kennedy}; 

\item[dgwolfe] dependancy graph with the {\em dependance direction
  vectors} (Wolfe);

\end{description}
}

\domain{Owner = \{ program , module , main , callees , callers , all ,  select , compilation_unit \}}
{The domain {\tt owner} permits the precise description of the virtual dependency rule
concerning which modules are attached, the ressources read,
written, produced or preserved. This could be the module itself
({\tt module}), the modules called by the module to which the phase is
applied ({\tt callees}) or which it calls {\tt caller}), or
all the modules of the programme in question({\tt all}). The program
({\tt program}) itself in fact caracterizes a particular workspace
an so indirecty the set of modules no which we wish to perform work. 
The name of a pogram is generally not
automatically derived from the code source because we can easily 
wish to derive several versions of the same sequential
original code and give a different name to each different version.

This supplementary attribute of the dependancies
allows the top-level driver to manage multiple calls made necessary
by the interprocedural nature of Pips and the elimination
of the auto-recursion of the database manager. 

\texttt{select} is a fake owner, to be used to select (or activate) rules
from other pipsmake rules. Should only be used with the bang rules?
}

\section{Real Resources}

The real resources correspond to a particular set of data produced by
a module or a particular program by a particular phase. The virtual
resources take their value among these real resources, but these
derivation rules of pipsmake are still generic and therefore still
defined in terms of de virtual resources.

\domain{Real\_resource = resource\_name:string x owner\_name:string}
{The domain {\tt real\_resource} is a private domain for pipsmake which 
serves to enable the manifestation of a set of virtual resources for a 
given program and a module.} 

\end{document}
\end