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:

• `if` conditionals involving variables that are not a loop iterator or a parameter, e.g., `if (A[i][j] == 0)`.
• `if` conditionals involving loop iterators and/or a parameter to form a non-affine expression, e.g., `if (i * j == 0)`.
• Non-affine `for` initialization or test condition, e.g., `for (j = 0; j < i * i; ++i)`.
• Non-affine array access, e.g., `A[i*N][j % i]` or `A[B[i]]`.

### 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:

• The only allowed control statements are `for` and `if`.
• There is no function call in the SCoP.
• There is no explicit pointer arithmetic/manipulation in the SCoP (no `&` nor `*` operators).
• `goto`, `break` and `continue` statements are forbidden.
• Arrays represent distinct memory locations (one per accessed array cell), and arrays are not aliased (note: no check is performed by PolyOpt/C for this property, it is the responsibility of the user to not feed ill-formed arrays).
• Loops increment by step of one.

### 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:

• `for (i = 0, j = 0; ...)`: more than one initialization.
• `for (i = max(a,b) + max(c,d); ...)`: not a valid conjunction.
• `for (i = max(a,b) + P; ...)`: not a valid conjunction.
• `for (i = a < b ? b : a; ...)`: not a (syntactically) valid ternary `max` operator.

#### 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:

• `for (i = 0; i < 1 || i < 2)`: disjunctions are not allowed.
• `for (i = 0; i < min(a,b) + min(c,d); ...)`: not a valid conjunction.
• `for (i = 0; min(i, N); ...)`: missing the `var opComp` part.
• `for (i = 0; i > P; ...)`: incorrect comparison operator.
• `for (i = 0; i < (a > b ? b : a); ...)`: not a (syntactically) valid ternary `max` operator.

#### 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:

• `if (i == 0 || c == 0)`: disjunctions are not allowed.
• `if (i < max(A,B))`: not a valid `max` constraint.
• `if (i == 42/5)`: not an integer term.

#### 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]; } ```