Counting Loop Iterations

In the case of loops, an estimate for the values of $W_i$ in (1) can be derived by considering the number of times that each part of the loop body is executed. This corresponds to the problem of enumerating the integer points of a polytope, a complicated problem for which it is not known whether a polynomial algorithm exists [1]. In the context of loop nests, some techniques to solve this problem are described in [5,14,17].

In general, counting the number of times, $n$, that a statement surrounded by $m$ loops is executed can be computed by an expression of the form

$$n = \sum_{i_1=l_1}^{u_1} \sum_{i_2=l_2}^{u_2} \cdots \sum_{i_m=l_m}^{u_m} 1,$$ (3)

where $l_j, u_j$ are the lower and upper bounds, respectively, of the $j$-th loop, $1 \leq j \leq m$. Whenever, for each loop, the loop bounds are constant, integer expressions, known at compile-time, it is trivial to show that $n = \prod_{j=1}^{m} \sum_{i_j=l_j}^{u_j} 1$. However, in a variety of situations, the loop bounds may be non-constant (for instance, dependent on the index of an outer loop), or may contain expressions whose value is unknown at compile-time. For the latter, the most important constraint to respect when evaluating sums such as these in (3), is whether the upper bound is greater than the lower bound. Considering this may lead to different answers when symbolic bounds are involved. In this paper, whenever this is the case, we split the loop iterations in such a way that the upper bound is always greater than the lower bound; this is discussed in Section 3.4.