Abstract Optimization Graph
Interactive Guide

Equality Saturation

Explore how compilers optimize code by remembering all possibilities at once.

info

How to download this view?

I've added a "Save Offline Copy" button to the top right navigation bar. Clicking it will download this entire interactive page as a single .html file that you can open in any browser without internet.

play_circle Visualizer: (a * 2) / 2 → a

Step 0/4
Initialization

Build the E-Graph

We start by parsing the expression x = (a * 2) / 2. The graph represents the data flow.

Current Nodes

  • / (Root)
  • *
  • 2
  • a
Graph Visualization
E-Class 'a' E-Class '2' Root Class / * a 2 * / 1 Equivalent!
Original
New/Rewrite
Merge
all_inclusive

Why "Saturation"?

Traditional compilers apply optimizations in a sequence (A then B). EqSat applies all valid rules until no new information is added—until the graph is "saturated" with possibilities.

call_split

Non-Destructive

Notice we never deleted (a * 2) / 2. We just added alternatives. This means we never make a "wrong turn" during optimization that we can't undo.

account_tree

Compact Storage

By sharing common sub-expressions (nodes point to Classes, not other nodes), an E-Graph can represent exponentially many programs in polynomial space.