Polyhedral Techniques for Parametric Memory Requirement Estimation 137
Having determined in the same way the previous last writes (the sources)
for all the remaining reads (the sinks), the next step is to count the sources
and the sinks that precede a given iteration, and make the difference between
both. For instance, if we only consider the reading accesses t[j] in statement
S2 and their sources, this computation would be, for any iteration (i
,j
)of
the second loop nest:
# {i ∈ dom R
1
}−# {(j, 0,j) ∈ R
1
| (0,j) ≺ (i
,j
)}if i
=0
#{(i, j) ∈ dom R
2
|(i, j) ≺(i
,j
)}−#{(i, j, k, l ) ∈R
2
| (k, l) ≺(i
,j
)}if i
> 0
resulting in the number of live elements for any iteration (i, j)inS
2
= n −i.
Hence the maximal number of live elements is equal to n.
The whole ...