Pipsmake library

---

Contents

• 1) Introduction
• 2) Internal description
• 3) Resource management
• 4) Application programing interface
• 5) Related work

---

1) Introduction

From a theorectical point of view, the object types and functions avalaible in PIPS define an heterogenous algebra with contructors (e.g. parser), extarctors (e.g. prettyprinter) and operators (e.g. loop unrolling). Very few combinations of functions make sense, but many functions and object types are available. This abundance is confusing for casual and experienced users and is was deemed necessary to assist them by providing default computation rules and automatic consistency management.

The Pipsmake library - not so far from the Unix make utility - is intended for interprocedural use. The objects it manages are resources, stored in memory or/and on disk. The phases are described by generic rules, which use and produce resources.

---

2) Internal description

2.1) Different kinds of rules

The pipsmake.rc file contains rules, which define the behaviour of the library. PIPS phases have been divided in two types:

• Analyses, generating one or more resources.
  These phases cannot require resources they produce. e.g. parser, dependance graph, parallel views ...
• Transformations, modifying one or more existing resources.
  These phases update resources - all produced resources are required. e.g. loop unrolling, dead code elimination ...

Let's see an example of analyses:

parser                 > MODULE.parsed_code
                       > MODULE.callees
    < PROGRAM.entities
    < MODULE.source_file

hpfc_close             > PROGRAM.hpfc_commons
    ! SELECT.hpfc_parser
    ! ALL.hpfc_directives
    # PROGRAM.entities
    # PROGRAM.hpfc_status
    < MAIN.hpfc_host

The first rule is the parser phase. To parse a module, you need the resources describing the entities of the whole program and the source file of the module to be up-to-date. Then you'll get the parsed code of the module and its callees (i.e. the list of the functions it calls).
The second rule - much more complex - is the last one of the HPF compiler. It will create the resource hpfc_commons for the program. It requires the resource hpfc_host of the main function and it will destroy the resources entities and hpfc_status. Morover it will first run the transformation called hpfc_directives. Also it requires the code to be parsed by hpfc_parser instead of the usual parser.

Now take a look at some transformations:

unroll                 > MODULE.code
    < PROGRAM.entities
    < MODULE.code

hpfc_filter            > MODULE.source_file
    < MODULE.source_file

hpfc_directives        > MODULE.code
                       > PROGRAM.hpfc_status
    < PROGRAM.entities
    < PROGRAM.hpfc_status
    < MODULE.code

The first transformation describes the loop unrolling phase. It needs the entities of the program and it will update the code of the module.
The second phase is a source file filter made for the HPF compiler. So it will update the source file of the desired module.
The last example - used by the rule hpfc_close - is a transformation updating the code and the hpfc_status.

Let's see another excerpt of the configuration file, which emphasizes the inter-procedural capabilities of Pipsmake:

proper_effects         > MODULE.proper_effects 
    < PROGRAM.entities
    < MODULE.code
    < CALLEES.summary_effects

cumulated_effects      > MODULE.cumulated_effects
    < PROGRAM.entities 
    < MODULE.code 
    < MODULE.proper_effects

summary_effects        > MODULE.summary_effects
    < PROGRAM.entities
    < MODULE.code 
    < MODULE.cumulated_effects

Here, for instance, the phase cumulated_effects computes the accumulated effects (such as a read on a given variable, called entity in PIPS) of all the statements of a MODULE. It needs the definition of all the entities of the PROGRAM - recall that PIPS is interprocedural-, the code of the module and its proper effects, i.e. the effects of the atomic subroutine calls. This architecture is incremental, since data structures are computed only when needed by some phase, and flexible, since each phase does not have to worry about the others and only request resources at its outset. This organization permits the interprocedurality to be almost transparent to the programmer of a given phase since he can ignore how resources are computed. Each necessary resource is requested from Pipsdbm and the appropriate function has previously been automatically activated by Pipsmake, if the rules are correct. This allows for easy implementations of both top-down and bottom-up algorithms on the call graph of a program. Note however that it relies heavily upon the non recursivity of Fortran77. It also provides the database structure necessary to combine interprocedural analysis and the speed necessary for interactivity: objects are computed only when there is a need to and when they are not already available and up-to-date.

2.2) Complete rule format

Frist a rule has a name ;=), and a list of constraints concerning its appliance which are:

• required resources (<)
  These resources need to be proved up to date before applying the rule
• output resources (>)
  These resources will be produced by this rule
• modified resources (#)
  These resources are going to be destroyed (they are needed only if they are in the required_resources list)
• unalterated resources (=)
  These resources will not be altered by the appliance of the rule unless rule dependancies should state it (they will be touched)
• transformation rules to be applied before (!)
  These are rule names corresponding to transformations which have to be run before

Rules are generic and will be instanciated for a module at runtime. For a given module name, resources owner may be:

• PROGRAM: the complete program (i.e. all modules in the source files)
• MODULE: the module itself
• MAIN: the main module (if any)
• ALL: all the modules
• CALLERS: the set of calling modules (of the current one)
• CALLEES: the set of called modules (by the current one)
• SELECT: allows to force a selection, if several rules may produce a same resource. does only make sense with the bang syntax.

A resource is referenced by both its - lowercase- name and its - uppercase - owner with the following syntax:

    OWNER.name

Resources with a generic owner are called virtual resources. When instanciated they are called real resources.

You may want to see the complete description of the rules for PIPS. Note that a consistent subset of these rules could be defined to derive automatically a tool with a subset of PIPS capabilities. For instance, PIPS could be restricted to program analyses or to parallelization for shared-memory machines.

2.3) Up to date resources

For each resource, at least one analyse rule producing it should exist. If many rules could be used to produce a resource, then the first one - in the file - is used. In order to specify another rule, a rule activation process is present.

According to the rule activated for a given resource, one can say this resource is up to date when:

• the resource exists - in the database
• all the required resources (<) but the modified ones (#) are up to date (recursively)
• the logical dates of the previous resources are less or equal to the current resource one

Resources logical dates have been introduced because of the lack of precision of Unix files dates. It is a number, incremented by one for each new phase launched by pipsmake. So that resources built by the same rule will have the same logical date. For file resources Unix dates are kept, too. It is then possible to determine whether such a resource has been modified - e.g. edited.

---

3) Resource management

A data base - created on NewGen - allow clear resources status management. Some resources are unloadable, some can only be kept in memory and others can be stored either in memory or on disk. This data manager (pipsdbm) gives confort and security to the resources manipulations. Called on demand, this library will give clean resource status (e.g. date) or allow consistent resource modifications.

---

4) A.P.I.

The Application Programing Interface of this library consists of three functions:

• make(resource name, owner name): is going to build the resources 'resource name' for the set of modules described by 'owner name'.
• apply(phase name, owner name): will apply the phase 'phase name' to the set of modules described by 'owner name'.
• activate(phase name): will activate this rule for all it produced resources. It is going do delete from the database all the produced resources recursively (using activated rules only).

---

5) Related work

• F. Irigoin, P. Jouvelot and R. Triolet, "Semantical Interprocedural Parallelization: An Overview of the PIPS Project", ACM International Conference on Supercomputing, June 1991.
• Mary W. Hall, John M. Mellor-Crummey,Alan Carle and René G. Rodríguez, "FIAT: A Framework for Interprocedural Analysis and Transformation", sixth workshop on languages and compilers for parallel computing, Portland, OR, August 1993.
• D.A. Padua, K.A. Faigin, J.P. Hoeflinger, P.M. Petersen and S.A. Weatherford, "The Polaris Internal Representation", fourth international workshop on compilers for parallel computers, Delft, December 1993.
• A.H. Veen and M. de Lange, "Overview of the PREPARE Project", fourth international workshop on compilers for parallel computers, Delft, December 1993.

---