In the generated code, each statement must be executed
for some set of iterations in a common iteration space.
The iterations that must be executed for each statement
are described by a set of linear constraints and stride
constraints involving the iteration variables and any number of symbolic
constants (e.g., `n`).
The iterations must be executed in lexicographic order.
If the active iterations for different statements overlap,
the execution of the iterations of those statements must be interleaved
appropriately.

A case involving two statements is shown in Figure 4. This example is contrived so as to illustrate our techniques, but reflects problems that arise in realistic problems. We could compute the convex hull of the union of all the domains, iterate over the points within the hull and for each point, test which statements should be executed (Figure 5). We describe [KP93b] techniques that can generate more efficient code (Figure 6), something not addressed by other researchers. This case is relatively simple, because it does not involve any symbolic constants and is only 2 dimensional. Our techniques can handle these additional complications.

`for y := 1 to 8 do for x := 1 to 11 do if 0 x-y 3 then s1[y,x] if 9 x+y 12 then s2[y,x]
`

`
`

Figure 5: Naive code to iterate over Figure 4 minipage

Figure 4: Iteration space with overlapping regions

`for y := 1 to 8 do for x := y to min(y+3,7-y) do s1[y,x] for x := 8-y to min(y-1,12-y) do s2[y,x] for x := max(y,8-y) to min(y+3,12-y) do s1[y,x] s2[y,x] for x := max(y,13-y) to y+3 do s1[y,x] for x := max(y+2,8-y) to 12-y do s2[y,x] `

Figure 6: Efficient code to iterate over Figure 4

minipage

figure