MimIR

[TOC]

MimIR is a pure, graph-based, higher-order intermediate representation rooted in the Calculus of Constructions. MimIR provides:

• Dependent types, parametric polymorphism, and higher-order functions out of the box
• Extensible plugins for domain-specific axioms, types, normalizers, and code generation
• SSA without dominance: a scopeless IR for higher-order programs based on free-variable nesting
• A sea-of-nodes style IR with on-the-fly normalization, type checking, and partial evaluation

Well suited for DSL compilers, tensor compilers, automatic differentiation, regex engines, and other systems that need high-performance code from high-level abstractions.

💡 Why MimIR?

Feature	LLVM	MLIR	MimIR
Higher-order functions	❌	⚠️ (regions only)	✅ (first-class functions)
Parametric polymorphism	❌	❌	✅
Type-level abstraction	❌	❌	✅
Dependent types	❌	❌	✅
Semantic extensibility	❌	🔧 (dialect-specific C++ semantics)	✅ (typed axioms)
Program representation	CFG + instruction lists	CFG/regions + instruction lists	Arbitrary expressions (direct style + CPS)
Structural foundation	CFG + dominance	CFG/regions + dominance	Free variables + nesting
DSL embedding / semantics retention	⬇️ Low	➡️ Medium (dialects, lowering)	⬆️ High (CC, partial evaluation, typed axioms, normalizers, lowering)

@note The table compares native IR-level support and representation, not what can be emulated via custom IR extensions, closure conversion, lowering, or external analyses.

🚀 Quick Start

git clone --recursive git@github.com:AnyDSL/MimIR.git
cd MimIR
cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j$(nproc)

📦 Install (optional)

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release -DCMAKE_INSTALL_PREFIX=/my/local/install/prefix
cmake --build build -j$(nproc) -t install

See the full [🛠️ build options](@ref build_options) in the docs.

🔥 Key Innovations

🧩 Plugins

Declare new types, operations, and normalizers in a single .mim file. C++ provides the heavy lifting: optimization, lowering, and code generation.

🌊 Sea of Nodes

MimIR uses a sea-of-nodes-style program graph and extends it to the Calculus of Constructions with higher-order functions, polymorphism, and dependent types. MimIR hits the [sweet spot](@ref mut) between a fully mutable IR, which is easy to construct, and a fully immutable IR:

• Non-binder expressions are immutable:

  Hash-consing, normalization, type checking, and partial evaluation happen automatically during graph construction.

• Binders are mutable where needed:

  They support variables and recursion by “tying the knot” through in-place mutation.

• Terms and types share one graph:

  Terms, types, and type-level computations all live in the same program graph as ordinary expressions.

🪾 SSA without Dominance

Forget CFG dominance. MimIR uses free-variable nesting:

• Free variables replace dominance; the nesting tree replaces the dominator tree

• Free-variable queries “just work”:

  if (expr->free_vars().contains(x)) /*x free in expr*/
  if (expr->free_vars().has_intersection(xyz)) /*x, y, or z free in expr*/

  This is always correct. MimIR maintains free-variable information lazily, locally, and transparently: results are computed on demand, memoized, and invalidated only where needed.

• Data dependencies remain precise, even for higher-order code

• Loop peeling and unrolling reduce to simple β-reduction

• Mutual recursion and higher-order functions are handled naturally

🐉 Naming: MimIR vs Mim

MimIR is a recursive acronym for MimIR is my Intermediate Representation.

In Norse mythology, Mímir was a being of immense wisdom. After being beheaded in the Æsir–Vanir War, Odin preserved his head, which continued to speak secret knowledge and offer counsel.

Today, you have Mímir's head at your fingertips.

• MimIR refers to the core graph-based intermediate representation and its C++ API.
• Mim is a lightweight textual representation of MimIR. It is not a full-featured programming language, but provides enough syntactic sugar to concisely express polymorphic and dependent types (including type-level dependencies introduced by many type variables). Mim is mainly intended for defining plugin interfaces and writing small test cases.

Throughout the codebase, we consistently use mim / MIM for namespaces, macros, CMake variables, and related identifiers.

💬 Community

• 💬 Discord → Join the chat
• 📚 Documentation → https://anydsl.github.io/MimIR
• 💻 Examples → examples/ and lit/

Ready to build the next generation of DSL compilers?

⭐ Star MimIR on GitHub, join Discord, and let's make high-performance DSLs easy.

⚖️ License

MimIR is licensed under the MIT License.

📖 Publications

• SSA without Dominance for Higher-Order Programs
  Roland Leißa, Johannes Griebler
  
  
  

• MimIrADe: Automatic Differentiation in MimIR
  Marcel Ullrich, Sebastian Hack, Roland Leißa
  
  
  

• MimIR: An Extensible and Type-Safe Intermediate Representation for the DSL Age
  Roland Leißa, Marcel Ullrich, Joachim Meyer, Sebastian Hack