Robust Program Specialization using Equality Saturation
Date:
I gave an early talk on program specialization at the 19th Workshop on Compiler-Driven Performance (CDP 2022), co-located with the 32nd International Conference on Collaborative Advances in Software and Computing (CASCON). This work planted the seeds of what would later become my Latent Idiom Recognition (LIAR) paper.
My focus was on how equality saturation could be used not just to optimize programs, but to robustly restructure them so they would naturally align with accelerator APIs. Idiom recognition was the central challenge: seemingly simple algebraic rewrites, like turning X ยท Y into the BLAS gemm idiom, were surprisingly fragile when left to pattern matching alone. Minor variations could hide the idiom entirely.
In this talk, I explored a different approach. By expressing programs in a purely functional array language, powered by the build and ifold operators, and combining general-purpose rewrites with accelerator-specific ones, we could give equality saturation enough room to discover the idioms rather than requiring them to be hand-coded. I showed how this method could uncover familiar BLAS kernels like dot products, gemv, and gemm inside the PolyBench benchmarks even when those idioms were buried under layers of syntactic variation.
CDP 2022 was the first public outing of this idea. As a concrete case study, I demonstrated how our method successfully identified matrix operations (dot products, gemv, gemm) in the PolyBench benchmark suite and automatically rewrote them into BLAS calls. The results showed high coverage, with benchmarks like 1mm and slim-2mm achieving close to 100% idiom recognition.
The talk introduced the minimalist semantics and rewrite machinery that eventually matured into LIAR: a general-purpose framework where both programs and idioms live in the same compact functional IR. LIAR extended the early vision of this talk and demonstrated that such an approach could match idioms across BLAS and PyTorch, yielding substantial performance gains.
The slide deck for this talk is available as PDF.