The characterization of this dependence, the analysis of parallelism, and the transformation of the code can be done in terms of the instance-wise information provided by any polyhedral framework.
Authors of polyhedral frameworks have explored the simple 1-dimensional finite difference heat equation stencil calculation expressed by the following pseudocode: This code confounds many of the transformation systems of the 20th century, due to the need to optimize an imperfect loop nest.
A re-cap here, of the two approaches on this example, might be nice, but for now see the individual papers of Wonnacott,[15][16] and Sadayappan et al.[17] as well as others who have studied this code using different frameworks, such as Song and Li.
Examples are provided below to aid in translation: Polyhedral Frameworks support dependence analysis in a variety of ways, helping to capture the impact of symbolic terms, identify conditional dependences, and separating out the effects of memory aliasing.
The Omega Project also described the use of their algorithms for value-based output- and anti-dependences, though Feautrier's quasts could presumably be easily adapted to this as well.
There are many ways to produce a visual depiction of the process of transforming and tiling an iteration space.
Examples of this approach can be found in the publications and transformation-visualization software of Michelle Mills Strout.
There are several other points on which the frameworks differ, specifically: Integer programming is NP-complete, and Maydan showed that the problem of checking array aliasing in nested loops with affine bounds and subscripts is equivalent to integer programming; other operations, such as array dataflow analysis, are even more complex (the algorithms of the Omega Library handle the full language of Presburger Arithmetic, which is O(2^2^2^n)).
Fortunately, many problems fall into a subset of this domain where general algorithms can produce an exact answer in polynomial time.
Polylib has some operations to produce exact results for Z-polyhedra (integer points bounded by polyhedra), but at the time of this writing, significant bugs have been reported.
Polyhedral libraries such as PolyLib and PPL exploit the double description of polyhedra and therefore naturally support vertex enumeration on (non-parametric) polytopes.
The Omega Library internally performs vertex enumeration during the computation of the convex hull.
Answers not marked this way are exact descriptions of sets of integer-valued points (except in cases of bugs in the software).
Some kinds of analysis, such as Pugh and Rosser's iteration space slicing, can be most easily stated in terms of the transitive closure of the dependence information.
Both the Omega Library and isl provide a transitive closure operation that is exact for many cases that arise in programs with simple dependence patterns.