6
$\begingroup$

E-graphs 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. 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?

$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$
    – rpjohnst
    Sep 17, 2023 at 17:37
  • $\begingroup$ @rpjohnst Sure ─ so how can this kind of optimisation be performed correctly using e-graphs? Or can it not? $\endgroup$
    – kaya3
    Sep 17, 2023 at 20:03
  • $\begingroup$ 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.) $\endgroup$
    – rpjohnst
    Sep 18, 2023 at 2:03
  • $\begingroup$ 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. $\endgroup$
    – Corbin
    Sep 18, 2023 at 16:29
  • $\begingroup$ @rpjohnst That sounds like an answer, not a comment—please post it as one! $\endgroup$
    – Alexis King
    Sep 18, 2023 at 17:04

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .