This diff attempts to add checkers for tiling legalityims to provide a new API, `checkTilingLegality`, to verify that the loop tiling result still satisifes the dependence constraints of the original loop nest.
The underlying algorithm is based on the condition from Irigoin and Triolet, h^T . R >= 0.## Background
Previously, there is no validation after loop tiling is performed. For instance:
```
func @diagonal_dependence() {
%A = alloc() : memref<64x64xf32>
affine.for %i = 0 to 64 {
affine.for %j = 0 to 64 {
%0 = affine.load %A[%j, %i] : memref<64x64xf32>
%1 = affine.load %A[%i, %j - 1] : memref<64x64xf32>
%2 = addf %0, %1 : f32
affine.store %2, %A[%i, %j] : memref<64x64xf32>
}
}
return
}
```
You can find more information about this example from the Section 3.11 of [1].
In general, there are three types of dependences here: two flow dependences, one in direction `(i, j) = (0, 1)` (notation that depicts a vector in the 2D iteration space), one in `(i, j) = (1, -1)`; and one anti dependence in the direction `(-1, 1)`.
Since two of them are along the diagonal in opposite directions, the default tiling method in `affine`, which tiles the iteration space into rectangles, will violate the legality condition proposed by Irigoin and Triolet [2]. [2] implies two tiles cannot depend on each other, while in the `affine` tiling case, two rectangles along the same diagonal are indeed dependent, which simply violates the rule.
This diff attempts to put together a validator that checks whether the rule from [2] is violated or not when applying the default tiling method in `affine`.
## Implementation
The canonical way to perform such validation is by examining the effect from adding the constraint from Irigoin and Triolet to the existing dependence constraints.
Since we already have the prior knowlegde that `affine` tiles in a hyper-rectangular way, and the resulting tiles will be scheduled in the same order as their respective loop indices, we can simplify the solution to just checking whether all dependence components are non-negative along the tiling dimensions.
We put this algorithm into a new API called `checkTilingLegality` under `LoopTiling.cpp`. This function iterates every `load`/`store` pair, and if there is any dependence between them, we get the dependence component and check whether it has any negative component. This function returns `failure` if the legality condition is violated.
## References
[1]. Bondhugula, Uday. Effective Automatic parallelization and locality optimization using the Polyhedral model. https://dl.acm.org/doi/book/10.5555/1559029
[2]. Irigoin, F. and Triolet, R. Supernode Partitioning. https://dl.acm.org/doi/10.1145/73560.73588
`checkTilingLegality` in LoopTiling.cpp implements this idea.