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]]`

.

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.

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.

`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.

`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.

`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.

`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.

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