Denis Barthou

Albert Cohen
email: acohen@prism.uvsq.fr

Jean-Fran Cois Collard

Maximal Static Expansion

Introduction

Data dependences are known to hamper automatic parallelization of imperative programs and their e cient compilation on modern processors or supercomputers. A general method to reduce the number of memory-based dependences is to disambiguate memory accesses in assigning distinct memory locations to non-con icting writes, i.e. to expand data structures. In parallel processing, expanding a datum also allows to place one copy of the datum on each processor, enhancing parallelism. This technique is known as privatization [START_REF] Schrijver | Theory of linear and integer programming[END_REF][START_REF] Knobe | Array SSA form and its use in parallelization[END_REF][START_REF] Collard | Construction of DO loops from systems of a ne constraints[END_REF] and is extremely important to parallelizing and vectorizing compilers 22].

Another way to expand data structures is to use the SSA (or Array SSA 19]) form in the generated code, i.e., without eliminating the renaming associated with SSA. In a more aggressive optimization, each memory location is written at most once, and the program is said to be in (plain) single assignment (SA) form [START_REF] Darte | Optimal ne and medium grain parallelism detection in polyhedral reduced dependence graphs[END_REF][START_REF] Carter | E cient multiprocessor parallelism via hierarchical tiling[END_REF]. Unfortunately, when the control ow cannot be predicted at compile-time, some run-time computation is needed to preserve the original data ow: in the static single-assignment framework, functions may be needed to \merge" multiple reaching de nitions, i.e. possible data de nitions due to several incoming control paths 12]. Such functions may be an overhead at run-time, especially for non-scalar data structures or when replicated data are distributed across processors. We are thus looking for a static expansion, i.e. an expansion of data structures that does not need a function. (Notice that according to our de nition, an expansion in the static single assignment framework may not be static.) The goal of this paper is to automatically nd a static way to expand all data structures as much as possible, i.e. the maximal static expansion (MSE). It may be considered as one possible trade-o between parallelism and memory usage. Other possibilities include memory usage, architecture-speci c optimizations, etc. and also dependence removal techniques based on a priori knowledge about which dependences hamper parallel execution 6]. All these techniques are compatible with the MSE framework: requiring the expansion to be static is just an additional constraint on the whole program transformation.

We present a framework to derive the maximal static expansion. The input of this framework is the (perhaps conservative) output of a reaching de nition analysis, so our method is \optimal" with respect to the precision of this analysis. Our framework is valid for any imperative program, without restriction|the only restrictions being those of your favorite reaching de nition analysis. We then present an algorithm to construct the maximal static expansion for programs with arrays and scalars only, but where subscripts and control structures are unrestricted. This paper actually extends our previous work on static expansion 3], a detailed comparison is proposed in Section 9.

The paper is organized as follows: Section 2 studies motivating examples showing what we want to achieve. Section 3 formally de nes the problem of expansion without s. Section 4 introduces a general framework, MSE, to solve this problem. This framework is applied in Section 5 to derive an algorithm for maximal static expansion on arrays and scalars. This algorithm is illustrated on the motivating examples in Section 6. Parallelizing compilers applications are studied in Section 7, and Section 8 reports experimental results. Section 9 contrasts this paper with related work, before we wrap up in Section 10.

Motivating Examples

The general framework presented in this paper is valid for any imperative programs. However, the three examples we study in this section are basically loop nests over arrays (mainly because our own analysis 4, 2] is restricted to such programs).

De nitions

For any statement, the iteration vector is the vector built from surrounding loop counters. Each iteration of a loop spawns instances of statements included in the loop body. In the example program, the for loop on i yields N instances of T , denoted by hT; 1i; : : : ; hT; N i. Moreover, we introduce arti cial integer counters for while loops. E.g., instances of S in Figure 1 are labeled hS; i; wi, with 1 i N and w 1. The execution order on instances is denoted by .

First Example: Dynamic Control Flow

We rst study the pseudo-code shown in Figure 1; this kernel appears in several convolution codes 1 . Parts denoted by have no side-e ect. Each instance hT; ii assigns a new value to variable x. In turn, statement S assigns x an unde ned number of times (possibly zero). The value read in x by statement R is thus de ned either by T , or by some instance of S, in the same iteration of the for loop (the same i). Therefore, if the expansion assigns distinct memory locations to hT; ii and to instances of hS; i; wi, how could instance hR; ii \know" which memory location to read from?

To formalize this problem, we use a reaching de nition analysis to describe where values are de ned and where they are used. We assume that the reaching de nition analysis works at statement instance level. Moreover the analysis may be more or less accurate: when the exact de nition that reaches a read instance cannot be predicted at compile time, we suppose that it returns a conservative set of possible reaching de nitions for this read.

We may thus call RD the mapping from a read instance to its set of reaching de nitions. Applied to the example in Figure 1, it tells us that the set RD (hS; i; wi) of de nitions reaching instance hS; i; wi is: RD(hS; i; wi) = if w > 1 then fhS; i; w 1ig else fhT; iig (1) And the set RD(hR; ii) of de nitions reaching instance hR; ii is: RD(hR; ii) = hT; ii hS; i; wi : w 1 ;

(2) where w is an arti cial counter of the while-loop.

Let us try to expand scalar x. One way is to convert the program into single-assignment form, making T write into x' i] and S into x'' i; w]: then, each memory location is assigned to at most once, complying with the de nition of single-assignment (SA). However, what should right-hand sides look like now? A brute-force application of (2) yields the program in Figure 2. While the right-hand side of S only depends on w, the right-hand side of R depends on the control ow, thus needing a function similar to a function in the static single-assignment (SSA) framework (even if, on this introductory example, the function would be very simple) 8]. The aim of this paper is to expand x as much as possible in this program but without having to insert functions.

for i = 1 to N do T x' i] = while do S x'' i,w] = if w > 1 then x'' i,w-1] else x' i]
A possible static expansion is to uniformly expand x into x i] and to avoid output dependencies between distinct iterations of the for loop. Figure 3 shows the resulting maximal static expansion of this example. Because the while loop is sequential, it has the same degree of parallelism and is simpler than the program in single-assignment.

Notice that it should be easy to adapt the array privatization techniques by Maydan et al. 20] to handle the program in Figure 1; this would tell us that x can be privatized along i. However, we want to do more than privatization along loops, as illustrated in the following examples.

Second Example: Array Expansion

Let us give a more complex example: the program in Figure 4 iteratively computes the maximum of an array B then applies some function foo on its elements. This program is representative of real x 1..N] for i = 1 to N do

T x i] = while do S x i] = x i] end while R = x i] end for
T A i] = 0 for j = 1 to N do S if B j]>A i] then A i] = B j] R B j] = foo (B j], A i])
end for end for When i > 1, it is easy to see that any value read in array B at instance hS; i; ji or hR; i; ji is de ned by hR; i 1; ji. When i = 1, the initial value of B j] is read: we assume that the reaching de nition of hR; 1; ji and hS; 1; ji is some \virtual" instance ? which executes before all other instances in the program.

Concerning A, since T executes at the beginning of every iteration of the outer loop, a read access to A in instance hS; i; ji may only be de ned by hT; ii or hS; i; j 0 i, for some j 0 , 1 j 0 < j.

The result cannot be made more precise, however, because the value of the predicate B j]>A i] is unknown at compile time. Figure 4 summarizes the reaching de nition relations between instances of S and R: an arrow from (i 0 ; j 0 ) to (i; j) means that instance (i 0 ; j 0 ) of S or R de nes a value that may reach another instance (i; j) of S or R.

Because each statement involves several references to memory, we need to recall which array is considered in the reaching de nition analysis. We will thus consider pairs of run-time instances and array references instead of simple instances (this will be formally stated in the next section). Now, the result of an instance-wise reaching de nition analysis are: RD(hR; i; ji; B j]) = RD(hS; i; ji; B j]) = if i > 1 then hR; i 1; ji else ? RD(hR; i; ji; A i]) = fhS; i; j 0 i : 1 j 0 jg fhT; iig RD(hS; i; ji; A i]) = fhS; i; j 0 i : 1 j 0 < jg fhT; iig [START_REF] Barthou | Array Data ow Analysis in Presence of Non-a ne Constraints[END_REF] Because some reaching de nitions are not known exactly (non-singleton sets), converting this program to SA form would require run-time computation of the memory locations read by R and S, i.e. functions.

However, expansion of array B along the inner loop does not require functions, because we could compute the exact reaching de nition of references to B j] in instances of R and S. This is in fact the result of maximal static expansion. The expanded program is shown in Figure 5; the rst iteration of the outer loop has been \peeled out" to avoid costly tests at every iteration.

real A 1..N], B 1..N], B' 1..N,1..N] T 1 A 1] = 0 for j = 1 to N do S 1 if B j]>A 1] then A 1] = B j] R 1 B' j] = foo (B j], A 1])
end for for i = 2 to N do

T A i] = 0 for j = 1 to N do S if B' i-1,j]>A i] then A i] = B' i-1,j] R B' i,j] = foo (B' i-1,j], A i])
end for end for Figure 5: Maximal static expansion for the second example.

One may apply classical scheduling algorithms 15, 13] (possibly combined with some tiling of the iteration space 17, 7]) to the expanded program. One possible solution would be to execute in a single \parallel front" all instances hS; i; ji and hR; i; ji such that i + j is equal to some constant t. The resulting program has the same degree of parallelism as the corresponding single-assignment program, without the run-time overhead.

Third Example: Non-A ne Array Subscripts

Consider the program in Figure 6.a, where foo and bar are arbitrary subscript functions2 . Since all array elements are assigned by T , the value read by R at the i th iteration must have been produced by S or T at the same iteration. The data-ow graph is similar to the rst example: RD (hR; ii) = hS; ii hT; i; ji : 1 j N : [START_REF] Barthou | Maximal static expansion[END_REF] Maximal static expansion adds a new dimension to A subscripted by i. This allows the rst loop to execute in parallel. These examples show the need for an automatic static expansion technique. We present in the following section a formal de nition of expansion and a general framework for maximal static expansion. We then describe an expansion algorithm for arrays that yields the expanded programs shown above. Notice that it is easy to recognize the original programs in their expanded counterparts, which is a convenient property of our algorithm.

It is natural to compare array privatization [START_REF] Knobe | Array SSA form and its use in parallelization[END_REF][START_REF] Schrijver | Theory of linear and integer programming[END_REF][START_REF] Collard | Construction of DO loops from systems of a ne constraints[END_REF] and maximal static expansion: both methods expose parallelism in programs at a lower cost than single-assignment form transformation. However, privatization generally resorts to dynamic restoration of the data ow, it requires that no dependences are carried by the privatized loop, and it cannot discover \skewed" parallelism across several loops; it is thus less powerful than general array expansion techniques like maximal static expansion. Indeed, because of loop-carried dependences, the example of Section 2.3 is not privatizable (no single loop is parallel and diagonal execution fronts must be considered).

Problem Statement

Let us start with some vocabulary, then introduce static expansion.

De nitions

Because of the state of memory and possible interactions with its environment, several executions of the same program may yield di erent sets of run-time statement instances and di erent sets of memory accesses. For a given program P , a program execution e is de ned as an execution trace of P , which is a nite or in nite (when the program does not terminate) sequence of con gurations| i.e. machine states. The set of all possible program executions is denoted by E.

Our program analysis and transformation techniques should be able to distinguish between the run-time instances of a statement. The sequential execution order of the program de nes a total order, denoted by , over statement instances. Each statement can involve several array or scalar references, which themselves have several instances called accesses.

De nition 1 (Access) A pair (o; r) of a run-time statement instance and a reference in the statement is called an access.

The set of all possible accesses (for every possible execution) is denoted by A. This set can be decomposed into two parts: R is the set of all reads|i.e. accesses performing some read in memory|and W is the set of all writes. We consider functions and relations over statement instances and accesses.

From the previous de nitions, a given execution of an imperative program can be seen as a pair ( ; f e ), where is the sequential order over all statement instances and f e maps every access to the memory location it either reads or writes. Function f e is the storage mapping of the program. Subscript e in f e |and in the following functions and relations|means that f e is the exact storage mapping for execution e 2 E. An exact knowledge of f e is impossible in general, since f e may depend on the initial state of memory and/or input data. We therefore assume that a previous analysis provides a conservative, \may" alias information May: 8e 2 E; 8v; w 2 W : f e (v) = f e (w) =) v May w:

We also assume an instancewise reaching de nition analysis has been performed: it computes a mapping from each read access (the use) to the statement instance or instances that may produce the value. For a given execution e 2 E, it is denoted by RD e : 8u 2 R; v 2 W : v =RD e (u) def ()

v u ^fe (u) = f e (v) ^ 8w 2 W : u w _ w v _ f e (v) 6 = f e (w) :
So de nition v reaches use u if it executes before the use, if both refer to the same memory location, and if no intervening write w kills the de nition.

Here again, knowing RD e exactly for every execution e is impossible. We thus assume that a conservative approximation|over all possible executions|of RD e is discovered by the instancewise reaching de nition analysis:

De nition 2 (Pessimistic approximation of reaching de nitions) Relation RD is any conservative approximation of function RD e s.t. 8e 2 E; 8u 2 R; 8v 2 W : v =RD e (u) ) v RD u.

Notice that the \theoretical" RD e is a function: each read has at most one de ning write, possibly none. The \practical" RD has to be a relation: more than one de nition may be considered to reach a given use.

Notice also that RD should not be de ned w.r.t. May: otherwise, the reaching-de nition information would be overly approximate. Indeed, one of the di culties addressed in 4, 2, 28, 24] is to avoid this approximation. Conversely, it is easy to build an example where two instances v and w are such that v RD w and :(v May w).

A storage mapping f 0 e is called memory expansion of f e when it uses at least as much memory as f e . More precisely:

De nition 3 (Expansion) For a given execution e 2 E, a storage mapping f 0 e is called memory expansion of f e if 8v; w 2 W : f 0 e (v) = f 0 e (w) =) f e (v) = f e (w):

Introducing Static Expansion

Static expansion has rst been introduced in 3]. The idea is to avoid dynamic restoration of the data ow. Let us consider two writes v and w belonging to the same set of reaching de nitions of some read u. If they both write in the same memory location (f e (v) = f e (w)) and if we assign two distinct memory locations to v and w (f 0 e (v) 6 = f 0 e (w)), then a function is needed to restore the data ow since we do not know which of the two locations has the value needed by u.

We introduce the following relation between de nitions that possibly reach the same read (recall that we do not require the reaching de nition analysis to give exact results): 8v; w 2 W : vRw () 9u 2 R : v RD u ^w RD u:

Whenever two de nitions reaching the same read assign the same memory location in the original program, they must still assign the same memory location in the expanded program. Since \assigning the same memory location" is an equivalence relation, we actually use R , the transitive closure of R (see Section 5.1 for computation details). Relation R , therefore, generalizes webs 21] to instances of references, and the rest of this paper shows how to compute R in the presence of arrays. (Strictly speaking, webs include de nitions and uses, whereas R apply to de nitions only.)

Relation R holds between de nitions that reach the same use. Therefore, mapping these writes to di erent memory locations is precisely the case where functions would be necessary, a case a static expansion is designed to avoid:

De nition 4 (Static Expansion) Given an execution e 2 E, an expansion f 0 e is static if 8v; w 2 W : vR w ^fe (v) = f e (w) =) f 0 e (v) = f 0 e (w):

Now, we are interested in removing as many dependences as possible, without introducing functions. We are looking for the maximal static expansion (MSE), assigning the largest number of memory locations while verifying (5):

De nition 5 (Maximal Static Expansion) Given an execution e 2 E, a static expansion f 0 e is maximal on the set of writes W, if for any static expansion f 00 e , 8v; w 2 W : f 0 e (v) = f 0 e (w) =) f 00 e (v) = f 00 e (w):

Intuitively, if f 0 e is maximal, then f 00 e cannot do better: it maps two writes to the same memory location when f 0 e does. We need to characterize the sets of statement instances on which a maximal static expansion f 0 e is constant, i.e. equivalence classes of relation fu; v 2 W : f 0 e (u) = f 0 e (v)g. However, this hardly gives us an expansion scheme, because this result does not tell us how much each individual memory location should be expanded. The purpose of Section 4 is to design a practical expansion algorithm for each memory location used in the original program.

Maximal Static Expansion

Following the lines of 3], we are interested in the static expansion which removes the largest number of dependences.

Lemma 1 (Maximal Static Expansion) Given an execution e 2 E, storage mapping f 0 e is a maximal static expansion if and only if 8v; w 2 W : vR w ^fe

(v) = f e (w) () f 0 e (v) = f 0 e (w) (7)
Proof: Su cient condition|the \if" part Let f 0 e be a mapping s.t. 8u; v 2 W : f 0 e (u) = f 0 e (v) , uR v ^fe (u) = f e (v): By de nition, f 0 e is a static expansion. Let us show that f 0 e is maximal. Suppose that for u; v 2 W: f 0 e (u) = f 0 e (v). ( 7) implies uR v and f e (u) = f e (v). Thus, from [START_REF] Barthou | Fuzzy array data ow analysis[END_REF], any other static expansion f 00 e satis es f 00 e (u) = f 00 e (v) too. Hence, f 0 e (u) = f 0 e (v) ) f 00 e (u) = f 00 e (v), so f 0 e is maximal.

Necessary condition|the \only if" part

Let f 0 e be a maximal static expansion. Because f 0 e is a static expansion, we only have to prove that 8u; v 2 W : f 0 e (u) = f 0 e (v) ) uR v ^fe (u) = f e (v).

On the one hand, f 0 e (u) = f 0 e (v) ) f e (u) = f e (v) because f e is an expansion. On the other hand, for some u and v in W, assume f 0 e (u) = f 0 e (v) and :uR v. We show that it contradicts the maximality of f 0 e : for any w in W, let f 00 e (w) = f 0 e (w) when :uR w, and f 00 e (w) = c when uR w, for some c 6 = f 0 e (u). f 00 e is a static expansion: By construction, f 00 e (u 0 ) = f 00 e (v 0 ) for any u 0 and v 0 such that u 0 R v 0 . The contradiction comes from the fact that f 00 e (u) 6 = f 00 e (v). Results above make use of a general memory expansion f 0 e . However, constructing it from scratch is another issue. To see why, consider a memory location c and two accesses v and w writing into c. Assume that vR w: these accesses must assign the same memory location in the expanded program. Now assume the contrary: if :vR w, then the expansion should make them assign two distinct memory locations.

We are thus strongly encouraged to choose an expansion f 0 e of the form (f e ; ) where function is constructed by the analysis and must be constant on equivalence classes of R . For a given execution e, f 0 e is a maximal static expansion if function satis es the following equation:

8v; w 2 W; f e (v) = f e (w) : vR w () (v) = (w):

In practice, f e (v) = f e (w) can only be decided when f e is a ne. In general, we have to approximate f e with relation May and derive two constraints from the previous equation:

Expansion must be static: 8v; w 2 W : v May w ^vR w =) (v) = (w);

Expansion must be maximal: 8v; w 2 W : v May w ^:(vR w) =) (v) 6 = (w): ( 9)

Notice ( 9) is a graph coloring problem: it says that two writes cannot \share the same color" if related. However, handling the symbolic equations involved and ( 8) and ( 9) simultaneously make the construction of a di cult problem.

On the other hand, the computation is easier if we assume relation May is transitive : constructing in [START_REF] Carter | E cient multiprocessor parallelism via hierarchical tiling[END_REF] becomes a problem of enumerating equivalence classes. (Actually, we believe that relation May di ers from May only in contrived examples.) Therefore, we consider the following maximal static expansion criterion: 8v; w 2 W; v May w : vR w () (v) = (w) [START_REF] Collard | Fuzzy array data ow analysis[END_REF] Now, given an equivalence class of May, classes of R are exactly the sets where storage mapping f 0 e is constant:

Theorem 1 Given a program execution e 2 E, a storage mapping f 0 e = (f e ; ) is a maximal static expansion i for each equivalence class C 2 W May , is constant on each class in C R and takes distinct values between di erent classes: 8v; w 2 C : vR w , (v) = (w).

Proof: C 2 W May denotes a set of writes which may assign the same memory cell, and C R is the set of equivalence classes for relation R on writes in C. A straightforward application of (10) concludes the proof.

Notice that is only constrained within the same class C: if C 1 ; C 2 2 W May with C 1 6 = C 2 , u 1 2 C 1 and u 2 2 C 2 , nothing prevents that (u 1 ) = (u 2 ). As a consequence, two maximal static expansions f 0 e and f 00 e are identical on a class of W May , up to a one-to-one mapping between constant values. An interesting result follows:

Lemma 2 The expansion factor for each memory location assigned by writes in C is Card( C R ).

Let C be an equivalence class in W May (statement instances that may hit the same memory location). Suppose we have a function mapping each write u in C to a representative of its equivalence class in C (see Section 5.1 for details). One may label each class in C R , or equiva- lently, label each element of (C). Such a labeling scheme is obviously arbitrary, but all programs transformed using our method are equivalent up to a permutation of these labels. Labeling boils down to scanning exactly once all the integer points in the set of representatives (C), which can be done using classical techniques 1, 10]. Now, remember that function f 0 e is of the form (f e ; ). From Theorem 1, we can take for (u) the label we choose for (u), then storage mapping f 0 e is a maximal static expansion for our program.

Eventually, one has to generate code for the expanded program, using storage mapping f 0 e . It is done in Section 5.1.

Algorithm

The maximal static expansion (MSE) scheme we just designed is general enough to handle any imperative program. More precisely, you may expand any imperative program using MSE, provided that a reaching de nition analysis technique can handle it (at the instance level) and that transitive closure computation, relation composition, intersection, and so on, are feasible in your framework.

Expanding scalars and arrays is done by renaming the variables and adding new dimensions to arrays; however, no straightforward expansion exists for trees, graphs, dynamic data structures with pointers... In the general case, appropriate expansion \rules" must be de ned|depending on both the data and control structures.

In the remainder of the paper, since we apply our own reaching de nition analysis to maximal static expansion, we inherit its syntactical restrictions: data structures are scalars and arrays; Pointers are not allowed. Loops, conditionals and array subscripts are unrestricted. This does not mean that the MSE framework is limited to loop nests and arrays: only the practical code generation algorithm is.

Expansion Algorithm

We present the expansion algorithm in Figure 7.

An interesting but technical remark would be that, seeing function as a parameterized vector, a few dimensions may have constant values on large and regular sets of accesses. Indeed, they may represent the \statement part" of an instance. In such case, splitting array A into several (renamed) data structures 3 should improve performance and decrease memory usage (avoiding convex hulls of disjoint polyhedra). Other techniques reducing the number of useless memory locations allocated by our algorithm are not described in this paper.

Finding Representatives for Equivalence Classes

Finding a canonical representative in a set is not a simple matter, and di erent techniques may yield di erent complexity numbers. We choose the lexicographic minimum because it can be computed using classical techniques, and our rst experiments gave us good results. Right-hand side: For any reference in the right-hand side, one has to nd the label of the source of the read. Technically, any read A Subscript(u)] is transformed into A Subscript(u); (RD (u))]. (Recall that RD (u) is a set, mapped by construction of to a single label (RD (u)).) When is a conditional whose predicate is a ne w.r.t. loop counters, the conditional should be taken out of A's subscript for e ciency.

Sixth

Step, Shape Declaration: Let A be the maximum value of (u) on write accesses u to an array A. (This is a componentwise maximum when (u) is a vector.) Then, previous declaration A : : : ] is transformed into A : : : ; A ]. A :::; max u2W^Array(u)=A (u)]. Notice also that representatives must be described by a function on write instances. Therefore, the good \parametric" properties of lexicographical minimum computations [START_REF] Darte | Optimal ne and medium grain parallelism detection in polyhedral reduced dependence graphs[END_REF][START_REF] Pieper | Parallelizing Compilers: Implementation and E ectiveness[END_REF] are well suited to our purpose.

A general technique to compute the lexicographical minimum follows. Let be an equivalence relation, and C an equivalence class for . The lexicographical minimum of C is:

min (C) = v 2 C s:t: @u 2 C; u v: (11)
Since is a relation, we can rewrite the de nition with algebraic operations:

min (C) = n( ) (C) (12)
5.3 Is our Result Maximal?

Our expansion scheme depends on the transitive closure calculator, and of course on the accuracy of input information: instancewise reaching de nitions RD and approximation May of the original program storage mapping. We would like to stress the fact that the expansion produced is static and maximal with respect to the results yielded by these parts, whatever their accuracy:

The exact transitive closure may not be available (for computability or complexity reasons) and may therefore be over-approximated. The expansion factor of a memory location c is then lower than Card( fu2W:fe(u)=cg R ). However, the expansion remains static and is maximal with respect to the transitive closure given to the algorithm. Relation May approximating the storage mapping of the original program may be more or less precise, but we required it to be conservative. Being overly conservative has no impact on the maximality of the result, but the more accurate relation May , the less useless (i.e. unused) memory is allocated by the expanded program.

What about Complexity and Practical Use?

We consider in turn every computation involved in the algorithm.

Computing the reciprocal relation RD 1 of RD is di erent from computing the inverse of a function and merely consists in a swap of the two arguments of RD.

Composing two relations RD and RD 0 boils down to eliminating y in x RD y ^y RD 0 z.

This can be done in polynomial time with the Fourier-Motzkin algorithm 23]. The number of constraints for this problem is equal to twice the number of surrounding loops, plus the number of governing conditionals and the number of dimensions of the array considered.

Computing the exact transitive closure of R or May is impossible in general (Presburger arithmetic is not closed over transitive closure). However, very precise conservative approximations (if not exact results) can be computed. Kelly et al. [START_REF] Irigoin | Supernode partitioning[END_REF]] do not give a formal bound on the complexity of their algorithm, but their implementation in the Omega toolkit proved to be e cient if not concise. Notice again that the exact transitive closure is not necessary for our expansion scheme to be correct.

Moreover, R and May happens to be transitive in most practical cases. In our implementation, this is rst checked before triggering the computation of the closure by testing whether the di erence (R R) n R is empty. This step is solved by integer linear programming: it can be done with the simplex algorithm which is exponential in the worse case but polynomial in the mean 14]. In all three examples, both relations R and May are already transitive.

In the algorithm above, is a lexicographical minimum. The expansion scheme just needs a way to pick one element per equivalence class. Computing the lexicographical minimum is easy to implement but may sometimes be rather expensive: it is still an integer linear programming problem. Finally, numbering classes becomes costly only when we have to scan a polyhedral set of representatives in dimension greater than 1. In practice, we only had intervals on our examples.

To sum up these observations, we may consider two cases:

either relations May and R are already transitive (as in our simple examples), and the algorithm complexity is equivalent to that of two integer linear programs (of similar size);

or the transitive closure algorithm must be applied, with a probably exponential complexity in the number of disjuncts in May or R; if such a complexity is not tolerable, Omega also provides a quite fast \a ne closure" algorithm as a conservative approximation of transitive closure 23].

What about Application to Real Codes?

Despite good performance results on small kernels (see following sections), it is obvious that reaching de nition analysis and MSE will become unacceptably expensive on larger codes. When addressing real programs, it is therefore necessary to apply the MSE algorithm independently to several loop nests. A parallelizing compiler (or a pro ler) can isolate loop nests that are critical program parts and where spending time in powerful optimization techniques is valuable. Such techniques have been investigated in the Polaris 5] and SUIF 16] projects. However, some values may be initialized outside of the analyzed code. When the set of possible reaching de nitions for some read accesses is not a singleton and includes ?, it is necessary to perform some copy-in at the beginning of the code: each array holding values read in the considered part must be copied into the appropriate expanded arrays. This may be expensive when expanded arrays hold many copies of original values, but the process is fully parallel and is likely to cost slightly less than the loop nest itself. In particular, there is no need for tracking write accesses into temporary arrays as for function computation.

There is a simple way to avoid copy-in, to the cost of some loss in the expansion degree. It consists in inserting \virtual write accesses"|before any other access in the loop nest|for every memory location and replacing ?s in the reaching de nition relation by the appropriate virtual access. Since all ?s have been removed, computing the maximal static expansion from the modi ed reaching de nition relation requires no copy-in; but additional constraints due to the \virtual accesses" may forbid some array expansions. This technique is especially useful when many temporary arrays are involved in a loop nest.

Morever, the data structures created by MSE on each loop nest may be di erent, and accesses to the same original array may now be inconsistent. Consider for instance the original pseudo code in Figure 8.a. We assume the rst nest was processed separately by MSE, and the second nest by any technique. The code appears in Figure 8.b. Clearly, references to A may be inconsistent: a read reference in the second nest does not know which 1 to read from.

A simple solution is then to insert, between the two loop nests, a copy-out code in which the original structure is restored (see Figure 8). Doing this only requires to add, at the end of the rst nest \virtual accesses" that reads every memory locations written in the nest. Reaching de nitions within the nest give the identity of the memory location to read from. Notice that unlike functions on arrays, there is no need for this copy-out code to keep track of write accesses with additional statements and temporary arrays 4 . If we call V (c) the \virtual access" to memory location c after the loop nest, we can compute the maximal static expansion for the nest and the additional \virtual accesses", and the value to copy back into c is located in (c; (RD (V (c)))).

Fortunately, with some knowledge on the program-wide ow of data, several optimizations can remove the copy-out code 5 . The simplest optimization is to remove the copy-out code for some data structure when no read access executing after the nest uses a value produced inside this nest. The copy-out code can also be removed when the read accesses executing after the nest can be considered as the \virtual accesses". Eventually, it is always possible to remove the copy-out code in performing a forward substitution of (c; (RD (V (c)))) into read accesses to a memory location c in following nests. We have thus proved that MSE is an incremental technique, i.e. it can be applied independently on several loop nests. Doing this, however, requires to add constraints to the expansion|through the use of \virtual accesses"|to enforce that no interference will occur with other nests in the program. This is still cheaper than functions since no there is no need to track write accesses. This solution is fully \static" but it may also forbid useful expansions in some cases.

Back to the Examples

This section applies our algorithm to the motivating examples, using the Omega Calculator 23] as a tool to manipulate a ne relations.

First Example

Let us consider the program in Figure 1. Using the Omega Calculator text-based interface, we describe a step-by-step execution of the expansion algorithm. We have to code instances as integervalued vectors. An instance hS s ; ii is denoted by vector i,..,s], where ..] possibly pads the vector with zeroes. We number statements T , S, R with 1, 2, 3 in this order, so hT; ii, hS; i; ji and hR; ii are written i,0,1], i,j,2] and i,0,3], respectively.

Step 1. From (1) and (2), we construct the relation S of reaching de nitions:

# S := { i,1,2]-> i,0,1] : 1<=i<=N} # union { i,w,2]-> i,w-1,2] : 1<=i<=N && 2<=w} # union { i,0,3]-> i,0,1] : 1<=i<=N} # union { i,0,3]-> i,w,2] : 1<=i<=N && 1<=w};
Since we have only one memory location, relation May tells us that all instances are related together, and can be omitted.

Step 2. Computing R is straightforward: # S' := inverse S; # Rel := S(S'); # Rel; { i,0,1]-> i,0,1] : 1<=i<=N} union { i,w,2]-> i,0,1] : 1<=i<=N && 1<=w} union { i,0,1]-> i,w',2] : 1<=i<=N && 1<=w'} union { i,w,2]-> i,w',2] : 1<=i<=N && 1<=w' && 1<=w}

In mathematical terms, we get: hT; iiRhT; ii () 1 i N hS; i; wiRhS; i; w 0 i () 1 i N; w 1; w 0 1 hS; i; wiRhT; ii () 1 i N ^w 1 hT; iiRhS; i; w 0 i ()

1 i N ^w0 1 ( 13
)
Relation R is already transitive, no closure computation is necessary: R = R

Step 3. There is only one equivalence class for May .

Let us choose (u) as the rst executed instance in the equivalence class of u for R (the least instance according to the sequential order): (u) = min (fu 0 : u 0 R ug).

To compute the lexicographical minimum, we describe by a relation of the form: ( i; w; s]) = i 0 ; w 0 ; s 0 ] s.t. i; w; s]; i 0 ; w 0 ; s 0 ] 2 W ^ i; w; s]R i 0 ; w 0 ; s 0 ] ^(@ i 00 ; w 00 ; s 00 ] 2 W : i; w; s]R i 00 ; w 00 ; s 00 ] ^ i 0 ; w 0 ; s 0 ] i 00 ; w 00 ; s 00 ])

Here i; w; s] 2 W is always true, and we may compute this expression using (12): 8i; w; 1 i N; w 1 : (hT; ii) = hT; ii; (hS; i; wi) = hT; ii:

Step 4. Computing (W) yields N instances of the form hT; ii. Maximal static expansion of accesses to variable x requires N memory locations. Here, we choose i as an obvious label for representative hT; ii: 8i; w; 1 i N; w 1 : (hS; i; wi) = (hT; ii) = i: (

Step 5. All left-hand side references to x are transformed into x i]; all references to x in the right hand side are transformed into x i] too since their reaching de nitions are instances of S or T for the same i. The expanded code is thus exactly the one found intuitively in Figure 3.

Step 6. The size declaration of the new array is x 1..N].

Second Example

We now consider the program in Figure 4. Instances hT; ii, hS; i; ji and hR; i; ji are denoted by i,0,1], i,j,2] and i,j,3], respectively.

Step 1. From (3), the relation S of reaching de nitions is de ned as:

# S := { i,j,2]-> i,0,1] : 1<=i,j<=N} # union { i,j,3]-> i,0,1] : 1<=i,j<=N} # union { i,j,2]-> i,j',2] : 1<=i,j,j'<=N && j'<j} # union { i,j,3]-> i,j',2] : 1<=i,j,j'<=N && j'<=j} # union { i,j,2]-> i-1,j,3] : 2<=i<=N && 1<=j<=N} # union { i,j,3]-> i-1,j,3] : 2<=i<=N && 1<=j<=N};

It is easy to compute relation May since all array subscripts are a ne. This relation is in fact transitive, i.e. May=May :

# May := { i,0,1]-> i,0,1] : 1<=i<=N} # union { i,j,2]-> i,j',2] : 1<=i,j,j'<=N} # union { i,0,1]-> i,j,2] : 1<=i,j<=N} # union { i,j,2]-> i,0,1] : 1<=i,j<=N} # union { i,j,3]-> i',j,3] : 1<=i,i',j<=N};
Step 2. As in the rst example, we compute relation R using Omega:

# S' := inverse S; # Rel := S(S'); # Rel;

{ i,0,1] -> i,0,1] : 1 <= i <= N} union { i,j,2] -> i,0,1] : 1 <= i <= N && 1 <= j <= N} union { i,j,3] -> i+1,0,1] : 1 <= i < N && 1 <= j <= N} union { i,0,1] -> i,j',2] : 1 <= i <= N && 1 <= j' <= N} union { i,j,2] -> i,j',2] : 1 <= i <= N && 1 <= j <= N && 1 <= j' <= N} union { i,j,3] -> i+1,j',2] : 1 <= j' <= j <= N && 1 <= i < N} union { i,0,1] -> i-1,j', 3
] : 2 <= i <= N && 1 <= j' <= N} union { i,j,2] -> i-1,j',3] : 1 <= j <= j' <= N && 2 <= i <= N} union { i,j,3] -> i,j,3] : 1 <= i < N && 1 <= j <= N} Computation of (Rel compose Rel) -Rel shows that relation R is already transitive: R = R .

Step 3. For u 2 C, (u) = min (fu 0 May u : u 0 R ug). We compute (u) using (12) and Omega:

# Lex := { i,0,1]-> i',0,1] : 1<=i<i'<=N} # union { i,0,1]-> i',j',2] : 1<=i<=i'<=N && 1<=j'<=N} # union { i,0,1]-> i',j',3] : 1<=i<=i'<=N && 1<=j'<=N} # union { i,j,2]-> i',0,1] : 1<=i<i'<=N && 1<=j<=N} # union { i,j,2]-> i',j',2] : 1<=i<=i'<=N # && (1<=j<j'<=N || 1<=i<i'<=N)} # union { i,j,2]-> i',j',3] : 1<=i<=i'<=N # && (1<=j<=j'<=N || 1<=i<i'<=N)} # union { i,j,3]-> i',0,1] : 1<=i<i'<=N && 1<=j<=N} # union { i,j,3]-> i',j',2] : 1<=i<=i'<=N # && (1<=j<j'<=N || 1<=i<i'<=N)} # union { i,j,3]-> i',j',3] : 1<=i<=i'<=N # && (1<=j<j'<=N || 1<=i<i'<=N)};
# RelMay := Rel intersection May; # Rho := RelMay -(Lex compose RelMay); # Rho; { i,0,1] -> i,0,1] : 1 <= i <= N} union { i,j,2] -> i,0,1] : 1 <= i <= N && 1 <= j <= N} union { i,j,3] -> i,j,3] : 1 <= i < N && 1 <= j <= N} That is:

8i; 1 i N : (hT; ii) = hT; ii 8i; j; 1 i N; 1 j N : (hS; i; ji) = hT; ii 8i; j; 1 i N; 1 j N : (hR; i; ji) = hR; i; ji

Step 4. We consider each array in turn. Let C be an equivalence class for relation May associated with writes to array B. There is an integer k s.t. C = fhR; i; ki : 1 i N g. Conversely, if C is an equivalence class associated with A, there is an integer k s.t. C = fhT; k; 0ig fhS; k; ji : 1 j N g. Let us now restrict the domain of to every equivalence class of R (Beware that the \backslash" symbol denotes the restriction of a relation's domain in Omega, not set subtraction):

# CB := { i,k,3] : 1<=i<=N}; # CA := { k,0,1]} union { k,j,2] : 1<=j<=N}; # Rho \ CB; { i,k,3] -> i,k,3] : 1 <= k <= N && 1 <= i < N} # Rho \ CA; { k,0,1] -> k,0,1] : 1 <= k <= N} union { k,j,2] -> k,0,1] : 1 <= k <= N && 1 <= j <= N}
A labeling can be found mechanically: for a given k, each instance hR; i; ki is mapped to a distinct representative, we thus choose (hR; i; ki) = i; for a given k, all instances hT; ki and hS; k; ji are mapped to the same representative, we are thus required to consider (hT; ki) = (hS; k; ji) = 1. We have thus computed the following labeling of write accesses: 8i; j; 1 i N; 1 j N : (hR; i; ji) = i 8i; j; 1 i N; 1 j N : (hS; i; ji) = (hT; ii) = 1

Step 5. Only references to array B are expanded: the static expansion code appears in Figure 5 (with an additional loop-peeling).

Step 6. Array A is unchanged and array B is expanded as B 1..N,1..N].

Third Example: Non-A ne Array Subscripts

We consider the program in Figure 6.a. Instances hT; i; ji, hS; ii and hR; ii are written i,j,1], i,0,2] and i,0,3].

Step 1. From (4), we build the relation of reaching de nitions: # S := { i,0,3]-> i,j,1] : 1<=i,j<=N} # union { i,0,3]-> i,0,2] : 1<=i<=N};

Since some subscripts are non a ne, we cannot compute at compile-time the exact relation between instances writing in some location A x]. We can only make the following conservative approximation of May: all instances are related together (because they may assign the same memory location).

Step 2. # S' := inverse S; # Rel := S(S'); # Rel; { i,j,1]-> i,j',1] : 1<=i<=N && 1<=j<=N && 1<=j'<=N} union { i,0,2]-> i,j',1] : 1<=i<=N && 1<=j'<=N} union { i,j,1]-> i,0,2] : 1<=i<=N && 1<=j<=N} union { i,0,2]-> i,0,2] : 1<=i<=N} R is already transitive: R = R .

Step 3. There is only one equivalence class for May .

We compute (u) using Omega: 8i; 1 i N :

(hS; ii) = hT; i; 1i 8i; j; 1 i N; 1 j N :

(hT; i; ji) = hT; i; 1i Note that every hT; i; ji instance is in relation with hT; i; 1i.

Step 4. Computing (W) yields N instances of the form hT; ii. Maximal static expansion of accesses to variable x requires N memory locations. We can use i to label these representatives; the resulting function is:

(hS; ii) = (hT; i; ji) = i:

Step 5. Using this labeling, all left hand side references to A ] become A , i] in the expanded code. Since the source of hR; ii is an instance of S or T at the same iteration i, the right hand side of R is expanded the same way. Expanding the code thus leads to the intuitive result given in Figure 6.b.

Step 6. The size declaration of A is now A 1..N,1..N].

Parallelization

This section aims to characterize correct parallel execution orders for an expanded program. In our framework, parallelization means construction of a parallel program ( 0 ; f 0 e ) where 0 is a sub-order of .

Computing Dependences After Maximal Static Expansion

The bene t memory expansion is to remove spurious dependences due to memory reuse. But with MSE, some memory-based dependences may remain. We consider an execution e of the expanded program with sequential execution order, ( ; f 0 e ). Let us denote by ( ;f 0 e ) e the exact dependence relation of ( ; f 0 e ), and let ( ;f 0 e ) denote its conservative approximation. Notice that ( ;f 0 e ) actually equals the RD function when the program is converted to single-assignment form (but not SSA).

Dependences left by MSE are, as usual, of three kinds: (1) output dependences due to writes connected to each other by functions. (2) True dependences, from a de nition to a read, where the de nition either may reach the read or is related (by R ) to a de nition that reaches the read.

(3) Anti dependences from a read to a de nition where the de nition, even if it executes after the read, is related (by R ) to a de nition that reaches the read. From equation [START_REF] Collard | Fuzzy array data ow analysis[END_REF], we de ne ( ;f 0 Then, the following de nition of ( ;f 0 e ) is the best conservative approximation of ( ;f 0 e ) e (supposing relation May is the best available approximation of function f e and RD is the best approximation of RD e ): 8v; w 2 A : v ( ;f 0 e ) w def () v RD w [START_REF] Feautrier | Data ow analysis of scalar and array references[END_REF] _ v May w ^vR w ^v w [START_REF] Feautrier | Some e cient solution to the a ne scheduling problem, part II, multidimensional time[END_REF] _ 9u 2 W : u RD w ^v May u ^vR u ^v w [START_REF] Hall | Maximizing multiprocessor performance with the SUIF compiler[END_REF] _ 9u 2 W : u RD v ^u May w ^uR w ^v w [START_REF] Irigoin | Supernode partitioning[END_REF] Now, since May and R are re exive relations, we observe that (15) implies [START_REF] Hall | Maximizing multiprocessor performance with the SUIF compiler[END_REF]. We may simplify the de nition of ( ;f 0 e ) :

8v; w 2 W : v ( ;f 0 e ) w def () v May w ^vR w ^v w 8v 2 W; w 2 R : v ( ;f 0 e ) w def () 9u 2 W : u RD w ^v May u ^vR u ^v w 8v 2 R; w 2 W : v ( ;f 0 e ) w def () 9u 2 W : u RD v ^u May w ^uR w ^v w [START_REF] Kelly | Transitive closure of in nite graphs and its applications[END_REF] Eventually, we get an algebraic de nition of the dependence relation after maximal static expansion:

( ;f 0 e ) = (May \R ) (May \R ) RD RD 1 (May \R ): (20)
The rst term describes output-dependences, the second one describes true-dependences (including reaching de nitions), and the third one describes anti-dependences.

What about Parallel Execution Order?

We can rely on classical algorithms to compute parallel order 0 from the dependence graph associated with ( ;f 0 e ) (cf. Theorem 2). In particular, when relation ( ;f 0 e ) is a ne|i.e. involves only a ne inequalities over loop counters and symbolic constants|scheduling 15, 13] algorithms can be applied. With some additional hypotheses on the original program (such as being a perfect nest of loops), tiling 17, 7] algorithms also apply. Any parallel order 0 (over operations) must \satisfy" dependence relation ( ;f 0 e ) (over accesses): 8e; 8(o 1 ; r 1 ); (o 2 ; r 2 ) 2 A : (o 1 ; r 1 ) ( ;f 0 e ) (o 2 ; r 2 ) ) o 1 0 o 2 (where o 1 ; o 2 are operations and r 1 ; r 2 are references in a statement). Now we want a static description and approximate ( ;f 0 e ) for every execution.

Theorem 2 (Parallel execution order correctness criterion) Given the following condition, the parallel order is correct for the maximal static expansion of the program (it preserves the original program semantics). 8(o 1 ; r 1 ); (o 2 ; r 2 ) 2 A : (o 1 ; r 1 ) ( ;f 0 e ) (o 2 ; r 2 ) =) o 1 0 o 2 :

(21)

Parallelization Example

To illustrate ( 20) and ( 21), we parallelize the rst example in Figure 1. First, we de ne the sequential execution order within Omega (with conventions de ned in Section 6.1):

# Lex := { i,w,2]-> i',w',2] : 1<=i<=i'<=N && 1<=w,w' # && (i<i' || w<w')} # union { i,0,1]-> i',w',2] : 1<=i<=i'<=N && 1<=w'} # union { i,w,2]-> i',0,1] : 1<=i,i'<=N && 1<=w && i<i'} # union { i,0,1]-> i',0,1] : 1<=i<i'<=N} # union { i,0,3]-> i',0,3] : 1<=i<i'<=N} # union { i,0,1]-> i',0,3] : 1<=i<=i'<=N} # union { i,0,3]-> i',0,1] : 1<=i<i'<=N} # union { i,w,2]-> i',0,3] : 1<=i<=i'<=N && 1<=w} # union { i,0,3]-> i',w',2] : 1<=i<i'<=N && 1<=w'};
Second, recall from Section 6.1 that all writes are in relation for May (since the data structure is a scalar variable), and that relation R is de ned by [START_REF] Cytron | E ciently computing static single assignment form and the control dependence graph[END_REF]. We compute ( ;f 0 e ) from (20):

# D := (R union R(S) union S'(R)) intersection Lex; # D; { i,w,2] -> i,w',2] : 1 <= i <= N && 1 <= w < w'} union { i,0,1] -> i,w',2] : 1 <= i <= N && 1 <= w'} union { i,0,1] -> i,0,3] : 1 <= i <= N} union { i,w,2] -> i,0,3] : 1 <= i <= N && 1 <= w}
After MSE, the only remaining dependences are between operations sharing the same value of i. It makes the outer loop parallel (it was not the case without expansion of scalar x). The parallel program in maximal static expansion is given in Figure 9.b.

Experiments

We ran a few experiments on an SGI Origin 2000, using the mp library (but not PCA, the built-in automatic parallelizer...). Implementation issues are discussed in Section 8.2.

Performance Results for the First Example

For the rst example, the parallel SA and MSE programs are given in Figure 9. Remember that w is an arti cial counter of the while-loop, and M is the maximum number of iterations of this loop. We have seen that a function is necessary for SA form, but it can be computed at low cost: it represents the last iteration of the inner loop. 10 rst describes speed-ups for the maximal static expansion relative to the original sequential program, then speed-ups for the MSE version relative to the single-assignment form. Due to function removal, MSE shows a better scaling : the relative speed-up quickly goes over 2. Moreover, for larger memory sizes, the SA program may swap or fail for lack of memory.

Implementation

A prototype of maximal static expansion is implemented in C++ on top of the Omega library.

Computing the class representatives is rather fast for our three examples: it validates our choice to compute function (mapping operations to their representatives) using a lexicographical minimum. As expected, checking for transitivity and computing the lexicographic minimum take approximately the same amount of time (around 100 milliseconds on a 32MB Sun SPARCstation 5). Interestingly, the whole MSE transformation appears to be much faster than FADA, the instancewise reaching de nition analysis (which is necessary for most parallelization schemes based on memory expansion). Our main concern, so far, would be to nd a way to approximate the expressions of transitive closures when they become large.

Related Work

If the input program is built of nested for loops with a ne bounds and accesses arrays with a ne subscripts, one can nd a static expansion which is also in single-assignment form. Feautrier 14] coined the term static control programs for this class of programs.

In the case of programs with general control and unrestricted arrays subscripts, array reaching de nition analyses are approximate 9, 4, 2, 27, 28]: Several writes may be the unique de nition of a given value, but the analysis cannot tell. 8] describes how to obtain a single-assignment program at the price of dynamic restoration of data ow.

Many studies are related to array privatization. As hinted above, Maydan et al. [START_REF] Knobe | Array SSA form and its use in parallelization[END_REF]] proposed an algorithm for array privatization. However, their method only applies to static control programs. Tu and Padua 26] proposed a privatization technique for a very large class of programs; but it resorts to dynamic restoration of the data ow. Another accurate approach using array regions has been described by Creusillet 11]. Her method avoids the cost of a dynamic restoration and copies back the privatized elements into the original arrays. As we remarked in Section 2.4, privatization only detects parallelism along the enclosing loops and is less powerful than general array expansion techniques (cf. program example in Section 2.3). Conversely, privatization leads to lower memory overhead in general.

Array SSA 19] generalizes SSA to Arrays. It may be used as a concrete form for generated code, so as to expand arrays. Its main drawback is the need for functions. The very purpose of MSE is to expand data structures as much as possible without having to introduce functions.

Our previous paper on Maximal Static Expansion 3] had a di erent approach to non a ne subscripts. In that case, representatives of equivalence classes were systematically labeled with a distinct name. This guaranteed correctness, but sometimes yielded excessive expansion, as illustrated in the following example. The de nition reaching hR; ii is exactly hS; ii. Assuming Perm (which may be an array or a function) is a permutation, no expansion is needed, because instances of S assign distinct memory locations. However, there are N equivalence classes of R , so the original MSE would label them with i; 1 i N , and expand array A into a two-dimensional array: The modi ed framework presented in this paper avoids such unnecessary expansion, thanks to relation May. Indeed, 8i; i 0 2 f1; : : : ; N g : hS; ii May hS; i 0 i () i = i 0 : 22 Therefore, any equivalence class for relation May =May is a singleton.

Conclusion and Perspectives

Expanding data structures is a classical optimization to cut memory-based dependences. However, the generated code has to ensure that all reads refer to the correct memory cell. When control ow is dynamic, the main drawback of such methods is therefore that some run-time computation has to be done to decide the identity of the correct memory cell.

This paper presented a new and general expansion framework: a cell can be expanded at most as many times as there are classes of independent (as far as reaching de nitions are concerned) writes. A practical algorithm was given and applied to real-life loop nests accessing arrays.

Interestingly enough, the framework does not require any precise reaching de nition analysis, nor does it require the closure computation to be exact. Conservative approximate results are ne as well, the only drawback being a probable loss in static expansion. However, we cannot do any better than that, and in accordance to our de nition, the static expansion we derive is still maximal. When the reaching de nition analysis and/or the transitive closure tool give poor results, our expansion scheme does not fail but degrades gracefully.

Future work will study the application of the framework to a wider class of problems. We also intend to enhance the algorithm so as to handle pointer-based data structures and recursive programs.

Figure 1 :

 1 Figure 1: First example.

Figure 2 :

 2 Figure 2: First example, continued.

Figure 3 :

 3 Figure 3: Expanded version of the rst example.

Figure 4 :

 4 Figure 4: Second example.

Figure 6

 6 Figure 6.a: Source program.

Figure 6 :

 6 Figure 6.b: Expanded version.Figure 6: Third Example.

  Input: The original program, reaching de nitions expressed as an a ne relationRD over iteration variables and symbolic constants, and may-alias relation May. Output: Maximal static expansion of the program, with shape declaration of the new data structures. First Step, Computing Relation May : Compute relation May , as shown in Section 5.4. Second Step, Computing Relation R : Compute relation R =RD RD 1 , where RD 1 is the symmetrical relation of RD. Computation of the transitive closure R is performed with Omega 18]; see Section 5.4 for practical computation details. Third Step, Computing Representatives: The representative of a write u 2 C is: (u) = min (fu 0 May u : u 0 R ug). Fourth Step, Labeling Representatives: To label memory locations, we consider in turn (parametrically) each equivalence class C for relation May , and restrict the domain of to C. We then associate each location to an integer point in the a ne polyhedron of representatives (C). Polyhedron scanning techniques 1, 10] can be applied to compute labeling function . Fifth Step, Code Generation: Control structures are left unchanged in the program (parallelization is the subject of Section 7). Left-hand side: Any reference A Subscript(u)] in left-hand side|Subscript(u) denotes the subscript function|is transformed into A Subscript(u); (u)].

Figure 7 :

 7 Figure 7: Algorithm for maximal static expansion

Figure 8

 8 Figure 8.a: Original code.

Figure 8 :

 8 Figure 8.c: MSE with copy-out.Figure 8: Inserting copy-out code.

  (v) = f e (w) ^vR w ^v w _ f e (v) = f e (RD e (w)) ^vR RD e (w) ^v w _ f e (w) = f e (RD e (v))^RD e (v)R w ^v w

Figure 9 Figure 9 :

 99 Figure 9.a: Single assignment

Figure 10 :

 10 Figure 10: Experimental results for the rst example.

  for i = 1 to N do S A Perm(i),i] = R = A Perm(i),i] end for

Table in Figure

 in

Published in the International Journal of Parallel Programming, 28(3):213{243, June 2000. Copyright c 2000 Plenum Publishing Corporation.

Such codes include horn.c by T. Burkit, implementing Horn and Schunck's algorithm to perform 3D Gaussian smoothing by separable convolution, and singh.c, written by J. Barron, implementation of Ajit Singh, ICCV, 1990, pages 168{177. Both codes may be found, among others, in the repository http://www.cs.cmu.edu/afs/cs/project/cil/ftp/html/v-source.html.

A foo (i)] stands for an array subscript between 1 and N, \too complex" to be analyzed at compile-time.

Recall that in single-assignment form, statements assign disjoint (renamed) data structures.

Copy-out code can indeed be viewed as a special case of function implementation.

Let us notice that, if MSE is used in codesign, the intermediate copy-code and associated data structures would correspond to additional logic and bu ers, respectively. Both should be minimized in complexity and/or size.

Acknowledgments: Authors are supported by the French MENRT and CNRS, INRIA project AAA, and the German-French ProCoPe program. Access to the SGI Origin 2000 was provided by the Universit e Louis Pasteur, Strasbourg, thanks to G.-R. Perrin. We would like to thank Paul Feautrier, M ax Geigl, Martin Griebl, Fran cois Irigoin and Vincent Lefebvre for fruitful discussions on this topic.