Pattern Matching, Transformation and Code Replacement on a Polyhedral Representation of Nested Loops

Abstract

We present Multidimensional Match, Transform and Replace (MMTR), an extension to LLVM's Polly library, capable of matching, transforming and replacing nested loops using the polyhedral model. According to a pattern, MMTR identifies nested loops that are semantically equivalent to an optimized target implementation. Then it transforms the nested loop in such a way that it can be replaced by a call to this optimized target implementation. MMTR works for targets with fixed dimension sizes, e.g. determined by the register size, or parametrizable dimension sizes, commonly found in library calls. In some benchmarks of the Polybench suite, a successful replacement by MMTR can lead to a reduction of the runtime by a factor of greater than 200 when targeting the optimized OpenBLAS library compared to code compiled and vectorized by Clang.In order to show MMTR's capabilities in real-world applications we evaluated it with the Visual Wake Words (VWW) benchmark found in the MLPerf Tiny suite. We used microTVM to generate C code from the VWW TensorFlow Lite model. MMTR was able to reduce the inference time on the VWW workload by 66 percent when targeting the OpenBLAS implementation.