Skip to content

Home

Jump to bottom
Sarah Morin edited this page Mar 10, 2026 · 3 revisions

Intarsia Optimizer Framework

Intarsia is an extensible optimizer framework written in Rust. With Intarsia, you can create an optimizer using any language, properties, and cost function of your choosing.

Intarsia draws on ideas from multiple domains (equality saturation, query optimization, etc.) to provide a generalized optimization framework. The framework supports:

  • Custom Lanugages → Define any language of operators as a Rust enum.
  • Declarative Rewrite Rules → Elegantly declare equivalences between expressions in the language. Currently implemented with ISLE.
  • Properties → Distinguish between semantically equivalent expressions based on desired/required properties. The language provides meaning, properties provide context (i.e. how we arrived at the same answer).
  • Custom Cost Model → Define a custom cost domain and cost function to use during optimization.
  • Programmable Search Strategies → Define a custom search strategy. NOTE: This feature is in development, currently we only support the default top-down Cascades search.

The basic workflow (which we cover in detail later) is:

  1. Define a language of operators and types.
  2. Define equivalence semantics with rewrite rules over the language.
  3. Define property domain and property derivation functions - how do we get from the language to the properties?
  4. Define a cost domain and a cost function mapping language and properties into the cost domain.
  5. Define an implementation of the OptimizerFramework over your language, property, and cost domains.
  6. Integrate the optimizer framework with the compiled rewrite rules.

At this point, you have built an optimizer that you can instantiate and use to optimize expressions in your language.

Why is it called Intarsia?

Intarsia is a knitting technique! Typically, when we do colorwork in knitting (i.e. create a pattern by using multiple colors of yarn at the same time) we let the excess yarn in the color we are not using hang behind our work until we are ready to use is again. These "floats" accumulate along the backside of the work -- not only are they cumbersome to manage, but they waste yarn! Intarsia is a colorwork technique where we avoid creating these floats by carefully constructing our pattern and managing the yarn. The result is a more efficient use of yarn and neater piece of knitwear.

The optimizer framework has a similar principle -- carefully combining knowledge from multiple domains (i.e. our "colors") to produce an optimized result with minimal wasted time (i.e. "floats") during the exploration.

Features

v0 Features

  • Declarative rewrites in ISLE (following a specific formatted)
  • Rust macros to easily integrate compiled ISLE with the optimizer e-graph/search modules
  • Support for any custom language defined as a Rust enum
  • Cascades style optimization strategy
  • Support for custom cost domain and cost function
  • Support for properties based optimizations

Future Developments

  • A new rewrite DSL that naturally integrates with the Rust optimizer module once compiled (no more manual integration with macros)
  • Better support for properties with a multe-graph
  • Programmable search strategies
  • Fine-grained cost-based bounding in search

Setup and Usage

Intarsia can be used like any other Rust crate.

Intarsia is not yet published on crates.io so for now we must use a git dependency or a local path dependency.

# Cargo.toml

intarsia = { git = "https://github.com/sarahmorin/intarsia.git" }

The intarsia crate includes a dependency on the intarsia-macros crate, which includes some convenient macros for implementing ISLE integration.

The intarsia-build crate, which includes some build-script helpers for working with intarsia can be included with the build-helpers feature:

# Cargo.toml

intarsia = { 
    git = "https://github.com/sarahmorin/intarsia.git",
    features = [ "build-helpers" ]
}

For a gentle introduction to using Intarsia, see Intarsia Basics.

External Dependencies

There are two external dependencies of note: ISLE and egg. Both of these dependencies are temporary conveniences. We intend to replace each with our own, bespoke implementations in the long term.

Currently, we rely on ISLE to specify rewrite rules declaratively and compile those rules to efficient Rust code. ISLE is a Cranelift project for instruction lowering in their compiler. Our use of ISLE is slightly different than its original purpose, so we do not make use of every feature and require a very specific use pattern. For the interested reader, ISLE has some great documentation. Eventually, we will implement our own rule compiler that automatically integrates with the optimizer framework. For now, relying on ISLE is convenient and allows us to focus development efforts on higher priority items. ISLE integration basics are covered in the Intarsia Basics guide; a more detailed discussion of ISLE integration can be found in ISLE Integration Guide.

Intarsia relies on egg, for its e-graph implementation. The e-graph is the foundation for compactly storing equivalent expressions. Eventually, the e-graph will be replaced by a multe-graph, which natively supports property storage.

Clone this wiki locally