[Polly][GEMM] Include parameter constraints in isMatMulOperandAcc

[ttheodor]

Summary

Polly can fail to detect a GEMM pattern due to constraints imposed by
valid integer values (e.g. p0 >=0 and p0 < 2^64-1). These constraints
are not taken into account in isMatMulOperandAcc when "possible" access
relations are constructed.

Fix by intersecting the candidate access relations with the Scop's
context which includes these constraints.

[Meinersbur]

Thanks for the patch. Could run polly-update-format and add a test case?

lib/Transform/ScheduleOptimizer.cpp

1159

unrelated change

[ttheodor]

Add test and fix formatting.

[Meinersbur]

LGTM, but I cannot apply the patch. I assume you uploaded a diff relative to your own version. E.g. there is no newline in at line 1159 in trunk.

It would be nice to have a commit message describing why this is changes, what the intended effect is, and how the change facilitates the effect.

[Meinersbur]

The additional test pattern-matching-based-opts_15.ll still succeeds when I remove intersect_params(Context)?

[ttheodor]

In D43932#1028149, @Meinersbur wrote:

The additional test pattern-matching-based-opts_15.ll still succeeds when I remove intersect_params(Context)?

I generated pattern-matching-based-opts_15.ll with create_ll.sh. If I run clang++ gemm.cpp -mllvm -polly -O3 -c -mllvm -polly-pattern-matching-based-opts -mllvm -stats 2>&1 | grep matrix (with gemm.cpp containing the C++ code embedded in the test) then it only prints something if the intersect_params(Context) is present.

[Meinersbur]

What is your gemm.cpp? The source in pattern-matching-based-opts_15.ll does not correspond to the source in your email: "GEMM pattern matching fails with parametric array sizes". The latter uses unit64_t while the former is from Polybench.

[ttheodor]

gemm.cpp is:

/* C := alpha*A*B + beta*C */
void kernel_gemm(int _PB_NI, int _PB_NJ, int _PB_NK, double alpha, double beta,
                 double *A, double *B, double *C) {
    for (int i = 0; i < _PB_NI; i++)
        for (int j = 0; j < _PB_NJ; j++) {
            C[i * _PB_NJ + j] *= beta;
            for (int k = 0; k < _PB_NK; ++k)
                C[i * _PB_NJ + j] +=
                    alpha * A[i * _PB_NK + k] * B[k * _PB_NJ + j];
        }
}

The one I posted in the e-mail is actually wrong (I didn't linearize properly the accesses) but incidentally exhibits the same behavior when it comes to pattern matching.

[Meinersbur]

Could you try to make pattern-matching-based-opts_15.ll fail without this intersect_params? Instead of create_ll.sh, try using -mllvm -polly-dump-before-file=file.ll to get a more accurate .ll file as Polly sees it when invoked withing clang.