cetus.analysis
Class ArrayPrivatization

java.lang.Object
  cetus.analysis.AnalysisPass
      cetus.analysis.ArrayPrivatization

public class ArrayPrivatization
extends AnalysisPass

ArrayPrivatization performs privatization analysis of the program. It tries to find privatizable variables (scalars and arrays) which are written first then read in a loop body. The high-level algorithm in below describes the process of detecting privatizable variables, both scalars and array sections, in a loop. The set operations that appear in the algorithm are performed on the array sections if the variable is an array. We use the power of symbolic analysis techniques in Cetus to make the symbolic section operation possible. For example, [1:m] (intersect) [1:n] results in [1:n] if the expression comparison tool with the value range set can decide n is less than or equal to m.

The algorithm traverses a loop nest from the innermost to the outermost loop. At each level, it first collects definitions (write references) and uses (read references) in the loop body. Uses that are covered by prior definitions create privatizable variables (or array sections) for the current loop. The other uses are upward exposed, creating read references seen in the outer loop. Second, the algorithm aggregates all these array sections over the loop iteration space, creating the array sections that are private, written and upward exposed for the entire loop. The aggregation for the written sections (DEF) computes the must-defined regular sections of the arrays over the entire loop iteration while the aggregation of upward-exposed sections (UEU) requires only the conservative value ranges of the sections (may-used sections). This algorithm is a slightly simpler version of the one used in the Polaris parallelizing compiler for Fortran77 programs.

 procedure Privatization(L)

   Input : Loop L
   Output: DEF[L], UEU[L], PRI[L]
   // DEF: Definded set
   // USE: Used set
   // UEU: Upward-exposed set
   // PRI: Private variables
   // (^): intersection, (v): union

   foreach direct inner loop L' in L
     (DEF[L'],USE[L']) = Privatization(L')

   G(N,E) = BuildCFG(L)
   // BuildCFG builds a CFG with the inner loops represented as super nodes

   Iteratively solve data flow equation DEF for node n in N
     DEFin[n] = (^) {DEFout[p], p in predecessors of n}
     DEFout[n] = (DEFin[n]-KILL[n]) (v) DEF[n]

   DEF[L] = {}
   UEU[L] = {}
   PRI[L] = CollectCandidates(L)
   // CollectCandidates collects variables that satisfies the following:
   // 1. It has write access in the loop body.
   // 2. Its subscript do not contain loop-variant variables.

   foreach loop-exiting node e in N
     DEF[L] = DEF[L] (^) DEFout[e]

   foreach node n in N
     UEU[L] = UEU[L] (v) (USE[n]-DEFin[n])

   foreach variable v in UEU[L]
     PRI[L] = PRI[L]-{v}

   DEF[L] = AggregateDEF(DEF[L])
   UEU[L] = AggregateUSE(UEU[L])
   // AggregateDEF aggregates array sections in DEF (MUST set)
   // AggregateUSE aggregates array sections in USE (MAY set)

   return (DEF[L], UEU[L])

 end
 

Array privatization is invoked by specifying the flag -privatize, and the result is stored as an annotation that contains the set of private variables. We do not consider a variable with user-defined type as a candidate private variable, but intend to widen the scope of the analysis in the future.

Field Summary

Fields inherited from class cetus.analysis.AnalysisPass

program

Constructor Summary

ArrayPrivatization(Program program)
Constructs an array privatization analyzer for a program.

Method Summary

void	analyzeProcedure(Procedure proc) Starts array privatization for a procedure.
java.lang.String	getPassName() Returns the pass name.
void	start() Starts array privatization by calling the procedure-level driver for each procedure within the program.

Methods inherited from class cetus.analysis.AnalysisPass

run, startAndCheck

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ArrayPrivatization

public ArrayPrivatization(Program program)

Constructs an array privatization analyzer for a program.

Parameters:

program - the input program.

Method Detail

getPassName

public java.lang.String getPassName()

Returns the pass name.

Specified by:

getPassName in class AnalysisPass

Returns:

the pass name in string.

start

public void start()

Starts array privatization by calling the procedure-level driver for each procedure within the program.

Specified by:

start in class AnalysisPass

analyzeProcedure

public void analyzeProcedure(Procedure proc)

Starts array privatization for a procedure. It first computes the range map of the procedure to enable subsequent symbolic operations, then calls analyzeLoop(Loop) to analyze the outer-most loops in the procedure. The final step is to annotate the analysis result for each loop in the procedure.

Parameters:

proc - the input procedure.