
Polyhedral Techniques for Parametric Memory Requirement Estimation 127
1 for(i=1;i<=n;++i)
2
for(j=1;j<=n-2*i;++j)
3 /* S */
Figure 4.3 A slightly less simple loop nest.
Besides polynomials and cells, we need one final ingredient to describe the
number of elements in a polyhedral set in general. To show the need for this
final ingredient, consider the loop nest in Figure 4.3. The iteration domain
can be described as
{(i, j) | 1 ≤ i ≤ n ∧1 ≤ j ≤ n − 2i }.
This iteration domain is shown in Figure 4.4 for varying values of
n. Note
that the upper bound on the
i-loop is slightly misleading, as the j-loop is
only executed for values of
i that result in an upper b