PIPS: Phases and Transformations

This page contains a very brief description of PIPS analysis and transformation phases. For more information, see the corresponding technical pages when they exist.

---

ANALYSES

Initializer

Creates the undelying data base and splits the program into modules corresponding to the different subroutines or functions.

Parser

Produces the abstract syntax tree of each module.

Controlizer

Computes the hierarchical control flow graph of the current module.

Callgraph

Interprocedural control flow graph: for each module, computes its callers.

Prettyprinters

Effects

The effects describe the memory operations of instructions. PIPS distinguishes WRITE and READ effects, as well as MAY and MUST effects. Effects on array elements are handled as effects on the whole array. Three types of effect are computed in PIPS:

• Proper effects describe the local references of an instructions. For an assignment, they contain all the variables used or defined. For a loop, they only describe the effects on the loop index, on the loop bounds, and on the increment.
• Cumulated effects are a summary of the effects of a complex statement and of its sub-statements.
• Summary effects of a subroutine are the cumulated effects of its body, from which local variables have been eliminated; these effects are used at call sites in order to obtain the proper effects, after translating the formal parameters into real ones.

Transformers

Transformers abstract the effects of intructions or procedures upon the values of integer scalar variables by giving the affine relations that exist between their values before and after the execution of a statement or procedure call. They are propagated bottom-up.

Preconditions

Preconditions are predicate over integer scalar variables. They hold just before the execution of the corresponding instruction or procedure. They are propagated top-down.

Regions

Regions are sets of array elements described by equalities and inequalities defining a convex polyhedron. There are READ, WRITE, IN and OUT regions.

Complexity

Chains

Computes use-def chains, using either effects or regions.

Dependence graphs

Static control verification

Verifies if the input program is a static control program. Pre-requisite to the computation of the Array DFG.

Array data flow graph

À la Feautrier array data flow graph.

---

TRANSFORMATIONS

Loop exchange

Loop parallelization

Loop distribution

Loop blocking

Loop unrolling

Scalar privatization

Partial evaluation

Dead code elimination

High Performance Fortran Compiler

see HPFC

---

Back to PIPS page.