This diff aims to provide a new API, checkTilingLegality, to verify that the loop tiling result still satisifes the dependence constraints of the original loop nest.
Background
Previously, there was no check for the validity of tiling. 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
srcOpInst -> srcOp