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