Generating fast sparse matrix vector multiplication from a high level generic functional IR

Usage of high-level intermediate representations promises the generation
of fast code from a high-level description, improving the productivity of
developers while achieving the performance traditionally only reached with
low-level programming approaches. High-level IRs come in two flavors: 1)
domain-specific IRs designed to express only for a specific application
area; or 2) generic high-level IRs that can be used to generate
high-performance code across many domains. Developing generic IRs is more
challenging but offers the advantage of reusing a common compiler
infrastructure various applications. In this paper, we extend a generic
high-level IR to enable efficient computation with sparse data structures.
Crucially, we encode sparse representation using reusable dense building
blocks already present in the high-level IR. We use a form of dependent
types to model sparse matrices in CSR format by expressing the
relationship between multiple dense arrays explicitly separately storing
the length of rows, the column indices, and the non-zero values of the
matrix. We demonstrate that we achieve high-performance compared to spare
low-level library code using our extended generic high-level code
generator. On an Nvidia GPU, we outperform the highly tuned Nvidia
cuSparse implementation of SpMV multiplication across 28 sparse matrices
of varying sparsity on average by $1.7\times$.