Introduction
Over the last year I’ve been gradually becoming “the MLIR guy” among a group of cryptography researchers, oriented around our HEIR project which is built on MLIR. Many folks in this community have told me they find MLIR difficult to learn, so I wrote a series of tutorials aimed at complete beginners—in the sense that the intended audience doesn’t know MLIR, LLVM, or much about compilers, but they do know how to write C++.
The feedback has been very positive, and so I’d like to propose upstreaming it. This RFC is to solicit feedback about the scope, how it should be structured in the monorepo (or not), and what additional topics should be included.
Background
Core emphasis
I wrote my tutorial as a more detailed and incremental version of the toy tutorial, with a heavier focus on the software development lifecycle: how to set up the C++/tablegen boilerplate, how to write lit tests, how to construct pipelines and what to do when seeing various common errors, and details specific to out-of-tree projects that use MLIR as a dependency (e.g., how to configure lit from scratch).
In this sense, the tutorial is very much aimed at out-of-tree users of MLIR rather than upstream contributors. I spend much time on basic questions like, “how do you run an upstream pass?” and, “what traits already exist and what do they do?”
Current tutorial outline
- Build System (Getting Started)
- Brief history of MLIR
- Bazel build system tutorial
- Running and Testing a Lowering
- Basic MLIR syntax
- Using the
mlir-opt
command line tool to run upstream passes lit
,FileCheck
, andmlir-cpu-runner
- Writing Our First Pass
- Making a custom
project-opt
binary - Writing a trivial pass without tablegen (walk the IR and call
mlir::affine::loopUnrollFull
on everyaffine.for
op) - Reimplementing the above using a rewrite pattern
- Writing a rewrite pattern that uses greedy engine nontrivially (“unroll” mul ops as iterated add ops)
- Making a custom
- Using Tablegen for Passes
- Reimplementing the unroll pass from (3) using tablegen
- Manually inspecting the generated C++
- Defining a New Dialect
- High level discussion of what dialects are for
- Create an empty
polynomial
dialect shell in tablegen - Defining types and ops in tablegen
- Custom assembly formats
- Adding a custom type attribute
- Using Traits
- High level view of why traits/interfaces are useful (dialect-agnostic passes)
- A survey of all general upstream traits I could find
- Adding
Pure
andElementwiseMappable
topolynomial
and seeing what upstream passes can operate on it as a result.
- Folders and Constant Propagation
- A deeper dive on
sccp
- Adding a
ConstantLike
op and folders topolynomial
- A deeper dive on
- Verifiers
- Studying traits that add verifiers
- Adding a custom verifier
- Adding a custom verifier using a custom trait
- Canonicalizers and Declarative Rewrite Patterns
- Discussion of
-canonicalize
- Adding canonicalization patterns in C++
- Rewriting the patterns to use DRR.
- Discussion of
- Dialect Conversion
- Discussion of why dialect conversion is hard (types) and existing conversion passes
- Lowering polynomial to standard MLIR.
- Discussion of
unrealized_conversion_cast
, type materialization hooks, and why this conversion pass doesn’t need them.
- Lowering through LLVM
- Defining a pass pipeline
- Lowering poly to LLVM (and a sort of backwards way of figuring out what passes to run)
- Bufferization
mlir-translate --mlir-to-llvmir -> llc -> clang -> ./a.out -> FileCheck
for a full e2e test.
- A Global Optimization and Dataflow Analysis
- Analysis passes & overview of what dataflow analysis does
- The
IntegerRangeAnalysis
and reusing it with custom types - A global optimization that uses the int range analysis to set up an ILP, solve it, and insert new ops into the IR.
Deficiencies/quirks of current tutorial
Bias toward HEIR’s problems
The tutorial series was intended to be a ramp for people who want to contribute to the HEIR project, and happens to be general enough that non-cryptographers find it useful. As such, there are various aspects of the tutorial that are biased toward HEIR that we may not want to focus on upstream. In particular:
- The use of bazel as the build system (the tutorial does have a CMake build alongside bazel, but bazel is the “primary” build system and I suspect the CMake config in the tutorial could be greatly improved)
- The choices of rewrite patterns are unrealistic for most compilers, but not all too unrealistic for FHE.
- The polynomial dialect’s custom type/attribute is a bit heavy for an introduction. I double dipped here, using this as a way to study/bootstrap an early version of a more fully-functional polynomial dialect that I’m working on upstreaming. Also polynomial ring math might be too intimidating for the average MLIR newbie.
- The global optimization article is a direct port of an academic paper relevant to HEIR.
- My lack of knowledge of the internal design of MLIR (e.g., how an op is laid out in memory) shows through in some places.
Sequential organization
The tutorials are organized sequentially, in that each article corresponds to a single pull request in a GitHub project, and the different sections of each article link to specific commits. The commits are organized in such a way that they can be read easily in order. E.g., one commit might set up pure boilerplate and ensure a pass with a no-op body can build, then the next commit might add a naive implementation of the pass, then the next commit improves on the naive implementation. In between, the article shows particular inputs, outputs, and error messages so that the reader can reproduce them at any point.
This poses a challenge for long-term maintenance of a tutorial kept in sync with HEAD, because earlier commits cannot be retroactively updated to account for API incompatibilities introduced in later commits. And the process of updating intermediate input/output/messages would be infeasible.
My tutorial gets around this by pinning to a particular LLVM commit hash, and twice in the tutorial series I show the process of updating the hash and fixing what breaks. I personally think this “commit-by-commit” style is helpful, but I don’t have any data to support that readers are actually relying on this, or if they just go read the code at HEAD. I’m open to suggestions for how to square this circle with an upstream tutorial, but without any solution I will upstream a version of the tutorial that gives up on this style.
Avoidance of MLIR internals
I explicitly avoided discussing internal details of MLIR, except in places where it was necessary (like how dialect conversion works). While I think much of this tutorial is best framed with MLIR as an opaque API, there are surely some parts that would benefit from side-information about MLIR internals. I simply don’t know enough about MLIR to know where those places are and what information would be useful there. I’m looking to the community for help there.
Not-yet-covered topics
I had a list of additional topics I wanted to cover in more detail, such as
- Defining/working with region-holding ops
- Custom dataflow analyses
- Slices
- Defining passes that depend only on interfaces/traits
- PDLL
Open to other suggestions.
Proposal
I will incrementally start to upstream the tutorial articles with the following modifications:
- Use CMake as the primary build system, so that it can be part of the upstream test suite like toy.
- Add one tutorial (that is not part of the build) that shows how to use bazel for an out-of-tree project.
- Modify the tutorial to link to lines of code at HEAD, in lieu of linking to commits/PRs.
- Use a GH-actions-based alerting mechanism to keep the links in sync with the code (maybe “if this then that” directives? Does LLVM have something like this configured upstream?)
- Use a dialect that is not
polynomial
for the intermediate tutorials, sincepolynomial
will be upstreamed to MLIR and conflict. Open to suggestions.
I will keep a GH issue tracking the remaining work to be done.
Alternatives
- Keep the tutorial as is (owned by me), but link to it from the MLIR tutorials page.
- The tutorial lives as a repository owned by the llvm GH org, but still out of the monorepo. This can maintain the commit-by-commit style, and pin to a particular LLVM commit, while allowing us to update it to more recent LLVM commits as needed. I would reimplement the tutorials commit-by-commit (PR-by-PR) in the new location, to give folks a chance to review the code and prose and make suggestions for improvements, rather than just changing ownership of the existing tutorial in-place.