[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> } } 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`.

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