Next: , Previous: Introduction, Up: Top

2 Specifics of Polyhedral Programs

2.1 Static Control Parts


Sequences of (possibly imperfectly nested) loops amenable to polyhedral optimization are called static control parts (SCoP) [5], roughly defined as a set of consecutive statements such that all loop bounds and conditionals are affine functions of the surrounding loop iterators and parameters (variables whose value is unknown at compile time but invariant in the loop nest considered). In addition, for effective data dependence analysis we require the array access functions to also be affine functions of the surrounding iterators and parameters.

For instance, a valid affine expression for a conditional or a loop bound in a SCoP with three loops iterators i,j,k and two parameters N,P will be of the form a.i + b.j + c.k + d.N + e.P + f, a,b,c,d,e,f are arbitrary (possibly 0) integer numbers.

The following program is a SCoP: 

         for (i = 0; i < N; i++)
             for (j = 0; j < N; j++) {
                 A[i][j] = A[i][j] + u1[i]*v1[j]
                 if (N - i > 2)
                    A[i][j] -= 2;
              }


Numerous elements can break the SCoP property, for instance:


2.2 Additional Restrictions in PolyOpt/C


PolyOpt/C automatically extracts maximal regions that can be optimized in the Polyhedral framework. We enforce numerous additional constraints to ensure the correctness of the SCoP extraction, in particular due to dependence analysis consideration:


2.3 Allowed Control-Flow Operations


PolyOpt/C supports a wide range of affine expressions, in particular conjunctions of affine constraints can be used to bound the space. In all the following, we recall that an affine expression must involve only surrounding loop iterators and parameters (scalar variables that are invariant during the SCoP execution).

SCoP extraction is a syntactic process so there are clear definitions of what is allowed in for (init; test; increment) and if (condition) statements. We note that if the loop iterator of a for statement is used outside the scope of the loop, or is assigned in the loop body, the loop will conservatively not be considered for SCoP extraction since PolyOpt/C may change the exit value of loop iterators.


2.3.1 In for initialization statement


init can be either empty, or of the from <type> var = expressionLb. That is, a single variable initialization is supported. The expressionLb is an affine expression, or possibly a conjunction of expressions with the max(expr1, expr2) operator. The max operator can either be written using a call to the max function together with using the --polyopt-safe-math-func flag, or with the ternary operation a < b ? b : a.

If the loop has no lower bound, the polyhedral representation will assume an infinite lower bound for the loop iterator: no analysis is performed to determine if there exists an initialization of the loop iterator before the for statement.

As an illustration, all loops in the following code form a valid SCoP. 

         for (int i = max(max(N,M),P); i < N; i++)
             for (j = max(i + 2 + 3*M, Q); j < N; j++)
                for (k = i - 2 > 0 ? i - 2 : 0); k < N; k++)
                    for (l = 0; ; l++)
                        A[i][j] -= 2;

Some examples of incorrect loop lower bound include:


2.3.2 In for test statement


test can be either empty (infinite loop), or of the from var opComp expressionUb <&& var opComp expressionUb2 <&& ...> >. That is, conjunction of upper bounds are supported via the && operator. The expressionUb is an affine expression, or possibly a conjunction of expressions with the min(expr1, expr2) operator. The min operator can either be written using a call to the min function together with using the --polyopt-safe-math-func flag, or with the ternary operation a < b ? a : b. The opComp must be one of <, <=, ==.

As an illustration, all loops in the following code form a valid SCoP. 

         for (int i = 0; i < N && i < min(min(P,Q),R); i++)
             for (j = 0; j <= (i < P ? P : i); j++)
                for (k = 0; k <= 0; k++)
                    for (l = 0; ; l++)
                        A[i][j] -= 2;

Some examples of incorrect loop lower bound include:


2.3.3 In for increment statement


Loops must increment by step of one, and there must be a single operation in the increment part. Typically only i++, ++i and i+=1 are supported increments. More complex increments such as i += one or i += 1, j += 1 are not supported.

2.3.4 In if conditional statement


For if statements, the conditional expression can be an arbitrary affine expression, and a conjunction of expressions with the && operator. min and max are allowed, provided a max constrains the lower bound of a variable and a min constraints the upper bound of a variable. Most standard comparison operators are allowed: <, <=, ==, >=, >. Note that else clause is not allowed, nor is !=.

As an illustration, all loops in the following code form a valid SCoP. 

         if (i > max(M,N) && j == 0)
            if (k < 32 && k < min(min(i,j),P))
               A[i][j] = 42;

Some examples of incorrect conditional expressions include:

2.3.5 Examples


We conclude by showing some examples of SCoPs automatically detected by PolyOpt/C. Note that the only constraints for the statements (e.g., R,S,T in the next example) involve the lack of function calls, at most one variable is assigned in the statement, and using affine functions to dereference arrays. 

       alpha = 43532;
       beta = 12313;
       for (int i = 0; i < N; i++) {
     R:      v1[i] = (i+1)/N/4.0;
     S:      w[i] = 0.0;
             for (j = 0; j < N; j++)
     T:         A[i][j] = ((DATA_TYPE) i*j) / N;
         }


       for (j = 1; j <= m; j++) {
           stddev[j] = 0.0;
           for (i = 1; i <= n; i++)
           	stddev[j] += (data[i][j] - mean[j]) * (data[i][j] - mean[j]);
           stddev[j] /= float_n;
           stddev[j] = sqrt(stddev[j]);
           stddev[j] = stddev[j] <= eps ? 1.0 : stddev[j];
         }