2.2.1 Domain Representation

As shown by the grammar, the input file describes the various informations thanks to characters, integers and domains. Each domain is defined by a set of constraints in the PolyLib format (see Wil93). They have the following syntax:

1. some optional comment lines beginning with ‘#’,
2. the row and column numbers, possibly followed by comments,
3. the constraint rows, each row corresponds to a constraint the domain have to satisfy. Each row must be on a single line and is possibly followed by comments. The constraint is an equality p(x) = 0 if the first element is 0, an inequality p(x) \geq 0 if the first element is 1. The next elements are the unknown coefficients, followed by the parameter coefficients. The last element is the constant factor.

For instance, assuming that ‘i’, ‘j’ and ‘k’ are iterators and ‘m’ and ‘n’ are parameters, the domain defined by the following constraints :

   -i + m >= 0
   -j + n >= 0
i + j - k >= 0

can be written in the input file as follows :

# This is the domain
3 7                      # 3 lines and 7 columns
# eq/in i  j  k  m  n  1 
    1  -1  0  0  1  0  0 #    -i + m >= 0
    1   0 -1  0  0  1  0 #    -j + n >= 0
    1   1  1 -1  0  0  0 # i + j - k >= 0

Each iteration domain ‘Iteration_domain’ of a given statement is a union of polyhedra ‘Domain_union’. A union is defined by its number of elements ‘Nb_domains’ and the elements themselves ‘Domain_list’. For instance, let us consider the following pseudo-code:

for (i=1;i<=n;i++) {
  if ((i >= m) || (i <= 2*m))
    S1 ;
  for (j=i+1;j<=m;j++)
    S2 ;
} 

The iteration domain of ‘S1’ can be divided into two polyhedra and written in the input file as follows:

2 # Number of polyhedra in the union
# First domain
3 5                # 3 lines and 5 columns
# eq/in i  m  n  1 
    1   1  0  0 -1 #  i >= 1
    1  -1  0  1  0 #  i <= n
    1   1 -1  0  0 #  i >= m
# Second domain
3 5                # 3 lines and 5 columns
# eq/in i  m  n  1 
    1   1  0  0 -1 #  i >= 1
    1  -1  0  1  0 #  i <= n
    1  -1  2  0  0 #  i <= 2*m

This document was generated on August 20, 2013 using texi2html 5.0.