<p><a href="https://egraphs-good.github.io/" rel="noreferrer">E-graphs</a> are a neat intermediate representation for program transformations and optimisations, which group program terms into equivalence classes (e-classes). An optimising compiler can then select the &quot;best&quot; representative from each e-class during code generation.</p>
<p>However, in some circumstances there may be two or more e-classes, where the correctness of the generated code depends on corresponding representatives being chosen from each class; i.e. the choice of representatives is not independent. For example, suppose our program has a set of small natural numbers, and we want the compiler to consider two possible representations: either a standard set data structure, or a <a href="https://en.wikipedia.org/wiki/Bit_array" rel="noreferrer">bitmask</a>. In that case, we have the following semantic equivalences:</p>
<ul>
<li><code>my_set = set()</code> is equivalent to <code>my_mask = 0</code></li>
<li><code>my_set.add(x)</code> is equivalent to <code>my_mask |= 1 &lt;&lt; x</code></li>
<li><code>y in my_set</code> is equivalent to <code>(my_mask &amp; (1 &lt;&lt; y)) != 0</code></li>
</ul>
<p>In order for the generated code to be correct, the compiler must consistently choose either the former or the latter representative from each e-class. If we select <code>my_mask |= 1 &lt;&lt; x</code> from one e-class and <code>y in my_set</code> from another, then the generated code will be incorrect (even if the compiler knew to declare both variables). Put another way, the members of each e-class are only equivalent depending on which representatives are chosen from other e-classes.</p>
<p>How can an optimisation like this be implemented correctly using e-graphs?</p>

<compilers><optimization><e-graphs>
How to ensure coherent choices of representatives in an e-graph?
CC BY-SA 4.0
2023-09-17T17:37:08.250Z
A valid e-graph has a "congruence invariant," which means that an equivalence between `x` and `y` must also imply an equivalence between `f(x)` and `f(y)`. Performing these rewrites (`set()` => `0`, `set.add(x)` => `set | (1 << x)`, etc) each individually violates this invariant and so is incompatible with e-graphs in this form.
rpjohnst
CC BY-SA 4.0
2023-09-17T20:03:47.507Z
@rpjohnst Sure ─ so how can this kind of optimisation be performed correctly using e-graphs? Or can it not?
kaya3
CC BY-SA 4.0
2023-09-18T02:03:29.950Z
Well, phrased the other way, it can be performed using e-graphs if and only if you can organize the language in such a way that these rewrites are "local" and preserve congruence. (If I knew of an obvious way to do this or reason that it was impossible, I would have written an answer- short of that, I'm just pointing to the relevant invariant.)
rpjohnst
CC BY-SA 4.0
2023-09-18T16:29:45.190Z
In practice, you'd have a local type context, and you'd commit to one of the possible types prior to extraction; then, type-guided extraction is possible (at least `egg` supports this...) However, the only way to know which commitment is more efficient would be to perform two extractions and compare their cost, which would lead to combinatorial explosion. I can write a complete answer later, if nobody else gets to it.
Corbin
CC BY-SA 4.0
2023-09-18T17:04:42.347Z
@rpjohnst That sounds like an answer, not a comment—please post it as one!
Alexis King
<p>You have to create one whole (sub) e-graph for the standard set version and another whole (sub) e-graph for the bitmask version.  These two e-graphs fragments are then equivalent.  Further optimization/transformation proceeds as normal, considering each of the two (sub) e-graphs, and finally the only option for later code generation is to choose one or the other.</p>

CC BY-SA 4.0
2023-09-19T15:07:30.177Z
2023-09-19T17:38:40.383Z
2023-09-19T17:38:40.383Z
Erik Eidt
<p>An e-graph does not just group terms into equivalence classes, but <em>congruence classes.</em> This means that an equivalence between terms <code>x</code> and <code>y</code> also implies an equivalence between terms <code>f(x)</code> and <code>f(y)</code>.</p>
<p>Congruence is important because e-graphs implicitly rely on it every time a rewrite is applied. All terms that use the rule's LHS are also immediately rewritten to use the RHS, and vice versa, because merging two e-classes preserves all uses of both.</p>
<p>Your example does not preserve congruence, and this will cause problems long before extraction time. For example, rewriting the term <code>set()</code> to <code>0</code> would also imply that <code>x + 0</code> should be rewritten to <code>x + set()</code> (using <code>x + _</code> for <code>f</code>).</p>

CC BY-SA 4.0
2023-09-18T21:46:13.217Z
2023-09-18T21:46:13.217Z
rpjohnst
# How to ensure coherent choices of representatives in an e-graph?
Posted by: username_0 on 2023-09-17
[E-graphs](https://egraphs-good.github.io/) are a neat intermediate representation for program transformations and optimisations, which group program terms into equivalence classes (e-classes). An optimising compiler can then select the "best" representative from each e-class during code generation.

However, in some circumstances there may be two or more e-classes, where the correctness of the generated code depends on corresponding representatives being chosen from each class; i.e. the choice of representatives is not independent. For example, suppose our program has a set of small natural numbers, and we want the compiler to consider two possible representations: either a standard set data structure, or a [bitmask](https://en.wikipedia.org/wiki/Bit_array). In that case, we have the following semantic equivalences:

* `my_set = set()` is equivalent to `my_mask = 0`
* `my_set.add(x)` is equivalent to `my_mask |= 1 << x`
* `y in my_set` is equivalent to `(my_mask & (1 << y)) != 0`

In order for the generated code to be correct, the compiler must consistently choose either the former or the latter representative from each e-class. If we select `my_mask |= 1 << x` from one e-class and `y in my_set` from another, then the generated code will be incorrect (even if the compiler knew to declare both variables). Put another way, the members of each e-class are only equivalent depending on which representatives are chosen from other e-classes.

How can an optimisation like this be implemented correctly using e-graphs?
**Tags:** compilers optimization e-graphs
> **Comments:**
> **username_1**: A valid e-graph has a "congruence invariant," which means that an equivalence between `x` and `y` must also imply an equivalence between `f(x)` and `f(y)`. Performing these rewrites (`set()` => `0`, `set.add(x)` => `set | (1 << x)`, etc) each individually violates this invariant and so is incompatible with e-graphs in this form.  
> **username_0**: @rpjohnst Sure ─ so how can this kind of optimisation be performed correctly using e-graphs? Or can it not?  
> **username_1**: Well, phrased the other way, it can be performed using e-graphs if and only if you can organize the language in such a way that these rewrites are "local" and preserve congruence. (If I knew of an obvious way to do this or reason that it was impossible, I would have written an answer- short of that, I'm just pointing to the relevant invariant.)  
> **username_2**: In practice, you'd have a local type context, and you'd commit to one of the possible types prior to extraction; then, type-guided extraction is possible (at least `egg` supports this...) However, the only way to know which commitment is more efficient would be to perform two extractions and compare their cost, which would lead to combinatorial explosion. I can write a complete answer later, if nobody else gets to it.  
> **username_3**: @rpjohnst That sounds like an answer, not a comment—please post it as one!  
---
## 2 answers
### Answer by username_4 on 2023-09-19. Score: 5 | Accepted answer
You have to create one whole (sub) e-graph for the standard set version and another whole (sub) e-graph for the bitmask version.  These two e-graphs fragments are then equivalent.  Further optimization/transformation proceeds as normal, considering each of the two (sub) e-graphs, and finally the only option for later code generation is to choose one or the other.
---
### Answer by username_1 on 2023-09-18. Score: 5
An e-graph does not just group terms into equivalence classes, but *congruence classes.* This means that an equivalence between terms `x` and `y` also implies an equivalence between terms `f(x)` and `f(y)`.

Congruence is important because e-graphs implicitly rely on it every time a rewrite is applied. All terms that use the rule's LHS are also immediately rewritten to use the RHS, and vice versa, because merging two e-classes preserves all uses of both.

Your example does not preserve congruence, and this will cause problems long before extraction time. For example, rewriting the term `set()` to `0` would also imply that `x + 0` should be rewritten to `x + set()` (using `x + _` for `f`).
---
