Array Privatization 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 arrays with loop-invariant subscripts

   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.