[Polly] Generalize the pattern matching to the case of tensor contractions
authorRoman Gareev <gareevroman@gmail.com>
Sat, 21 May 2022 19:40:33 +0000 (22:40 +0300)
committerRoman Gareev <gareevroman@gmail.com>
Sun, 7 Aug 2022 10:10:32 +0000 (13:10 +0300)
commitb02c7e2b630a04701d12efd2376f25eff2767279
tree1d57311eb996b0fe9665994a98622030d34efc8b
parent6bb51bf06214af3690af7034f4edeb265732c481
[Polly] Generalize the pattern matching to the case of tensor contractions

The pattern matching optimization of Polly detects and optimizes dense general
matrix-matrix multiplication. The generated code is close to high performance
implementations of matrix-matrix multiplications, which are contained in
manually tuned libraries. The described pattern matching optimization is
a particular case of tensor contraction optimization, which was
introduced in [1].

This patch generalizes the pattern matching to the case of tensor contractions
using the form of data dependencies and memory accesses produced by tensor
contractions [1].

Optimization of tensor contractions will be added in the next patch. Following
the ideas introduced in [2], it will logically represent tensor contraction
operands as matrix multiplication operands and use an approach for
optimization of matrix-matrix multiplications.

[1] - Gareev R., Grosser T., Kruse M. High-Performance Generalized Tensor
Op­erations: A Compiler-Oriented Approach // ACM Transactions on
Architec­ture and Code Optimization (TACO). 2018. Vol. 15, no. 3.
P. 34:1–34:27. DOI: 10.1145/3235029.

[2] - Matthews D. High-Performance Tensor Contraction without BLAS // SIAM
Journal on Scientific Computing. 2018. Vol. 40, no. 1. P. C 1—C 24.
DOI: 110.1137/16m108968x.

Reviewed By: Meinersbur

Differential Revision: https://reviews.llvm.org/D114336
21 files changed:
polly/include/polly/Support/ISLTools.h
polly/lib/Support/ISLTools.cpp
polly/lib/Transform/MatmulOptimizer.cpp
polly/lib/Transform/ScheduleOptimizer.cpp
polly/test/ScheduleOptimizer/pattern-matching-based-opts-after-delicm.ll
polly/test/ScheduleOptimizer/pattern-matching-based-opts-after-delicm_2.ll [new file with mode: 0644]
polly/test/ScheduleOptimizer/pattern-matching-based-opts.ll
polly/test/ScheduleOptimizer/pattern-matching-based-opts_11.ll
polly/test/ScheduleOptimizer/pattern-matching-based-opts_15.ll
polly/test/ScheduleOptimizer/pattern-matching-based-opts_16.ll [new file with mode: 0644]
polly/test/ScheduleOptimizer/pattern-matching-based-opts_17.ll [new file with mode: 0644]
polly/test/ScheduleOptimizer/pattern-matching-based-opts_18.ll [new file with mode: 0644]
polly/test/ScheduleOptimizer/pattern-matching-based-opts_19.ll [new file with mode: 0644]
polly/test/ScheduleOptimizer/pattern-matching-based-opts_2.ll
polly/test/ScheduleOptimizer/pattern-matching-based-opts_20.ll [new file with mode: 0644]
polly/test/ScheduleOptimizer/pattern-matching-based-opts_21.ll [new file with mode: 0644]
polly/test/ScheduleOptimizer/pattern-matching-based-opts_22.ll [new file with mode: 0644]
polly/test/ScheduleOptimizer/pattern-matching-based-opts_23.ll [new file with mode: 0644]
polly/test/ScheduleOptimizer/pattern-matching-based-opts_24.ll [new file with mode: 0644]
polly/test/ScheduleOptimizer/pattern-matching-based-opts_25.ll [new file with mode: 0644]
polly/test/ScheduleOptimizer/pattern-matching-based-opts_4.ll