Array Dependence Analysis

I am a student at UIUC doing a course project for my compilers class. My partner and I are interested in array dependence analysis in loop nests in MLIR. Can someone point us to existing analysis already in MLIR, if it exists, and comment on its design? We would also welcome suggestions for our project, such as useful algorithms that we could implement and contribute.

The -test-memref-dependence-check pass performs such a dependence analysis, checking for dependences between memref accesses that are affine load/stores. It relies on a number of mostly simple techniques that involve manipulation of linear equalities and inequalities including the GCD test, GCD tightening, Gaussian elimination, and Fourier-Motzkin elimination. As output, it emits dependences as vectors with a range of the distance along each dimension. Dependence analysis information is used in other passes like affine fusion, the parallelism detection test pass, and store to load forwarding. The pass/utility is unfortunately not documented even summarily at https://mlir.llvm.org/docs/Passes/ (perhaps because it’s a test pass) but the code comments and test cases have a lot of information.

If you are interested in working on MLIR in general, we have a list of open projects.

If you are interested in loop transformations specifically, I’d say various kinds of tiling (diamond, hexagonal, @bondhugula will have the paper links) or going towards affine scheduling (though we need a solver) might of interest. However, both may be quite time-consuming for a class project.