[MLIR] Add tiling validity check to loop tiling pass

Authored by kumasento on Aug 6 2020, 1:25 PM.


[MLIR] Add tiling validity check to loop tiling pass

This revision aims to provide a new API, checkTilingLegality, to
verify that the loop tiling result still satisifes the dependence
constraints of the original loop nest.

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>


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.

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.

[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

Differential Revision: https://reviews.llvm.org/D84882