# How is the iteration space of a nested for-loop containing two sequential nested loops represented?

In a general for loop of the form:

for (i = 0, i <= n, i++) {
for (j = i, j <= n, j++)
...
for (k = i, k <= n, k++)
...
}


What form do the inequalities representing the iteration space take? Or what convex polyhedron represents this?

Background I am looking at the Dragon Book's chapter on parallelisation. This talks in detail of nested loops of the form:

for (i = 0, i <= n, i++) {
for (j = i, j <= n, j++)
...
}


but not of the form described at the top.

The iteration space of d-deep nested loops can be represented as: $$\{ i \in \mathbb{Z}^d \mid Bi + b \geq 0 \}$$

where B is a $d \times d$ integer matrix and b is a vector of length $d$

My question is basically do I have to do anything different when a loop contains multiple inner loops not nested within each other?

• Could you please provide some background for the question? You can check the FAQ for some tips about writing a good question. Jan 31 '12 at 19:24
• Don't you want 0≤i≤n, i≤j≤n, and i≤k≤n, like it says right there in the code? Feb 1 '12 at 9:01

This isn't really my area, but I think you want to Google for "the polytope model" or "the polyhedral model", and specifically for "affine-by-statement scheduling". The basic idea is that iterations in a loop nested $d$ deep are turned into a $d$-dimensional polytope, and that each iteration is a point within the polytope. You can then look at data dependencies between the iterations to figure out how to parallelize code (which turn out to correspond to affine transformations of the polytope).