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...