ægraph (aegraph，或acyclic e-graph) 实现。

ægraph是e-graph的一种形式。我们将首先描述e-graph，然后描述aegraph作为它的一种稍微弱一些但高度优化的变体。

该库的主要目标是显式内存高效和减少分配。我们需要尽可能快和尽可能小，以最小化对生产编译器编译时间的影响。

e-graph

e-graph，或等价图，是一种基于节点的中间表示（IR）数据结构，由eclasses和enodes组成。一个eclass包含一个或多个enodes；在语义上，一个eclass类似于一个值，而一个enode是计算该值的一种方式。如果多个enodes在一个eclass中，该数据结构断言这些enodes中的任何一个，如果评估，都会产生相同的值。

e-graph还包含一个去重哈希表，因此如果用户多次创建相同的e-node，它们将得到相同的eclass ID。

在常规用例中，e-graph用于为函数体或其他基于表达式的代码构建节点海洋IR，然后对e-graph应用重写规则。每个重写可能会引入一个新的e-node，它与现有的e-node等价，然后将两个e-node的类合并在一起。

在简单情况下，这会导致一个包含一系列新添加的e-nodes的eclass，即表达式的所有已知形式，但请注意，如果重写规则重写为现有的e-node（通过去重发现），重写可能会导致存在一段时间两个e-class的合并。

一个e图的enodes将它们的参数指向类，而不是直接指向其他节点。这是e图能够进行规范化的关键：当两个已经被其他e节点用作参数的e类进行并集操作时，所有指向这些e类的e节点也会重新进行规范化。这可能导致eclass的“级联”并集操作，这个过程会发现所有单个等式的传递性影响。这个过程被称为“等价饱和”。

无环e图（aegraph）

虽然e图功能强大，但构建和饱和它可能也很昂贵：表达式可能有很多不同的形式（因为可能有很多不同的重写），级联规范化需要维护昂贵的重型数据结构。

这个crate引入了aegraph：一个无环e图。这个数据结构将e类存储为不可变持久数据结构。一个id可以指向eclass的某个级别：eclass在某一时刻节点的快照。这个id所引用的节点永远不会改变，尽管eclass以后可能会增长。

并集也是一个创建新eclass id的操作：原始的eclass ID指向原始eclass内容，而union()操作的结果指向包含所有节点的eclass。

为了允许充分的规范化，enode通常存储每个参数的最新eclass id，但使用规范化的eclass id计算哈希和等价。我们使用类似于传统e图的并查找数据结构定义这样的规范id。它通常是引用eclass一部分的最低id。

这种数据结构的持久性和不可变性产生了一个极其重要的特性：它是无环的！这极大地简化了操作。

• 当“细化”出e图回线性代码，以便我们可以生成机器代码时，我们不需要打破循环。一个给定的enode不能间接地引用它自己。

• 在应用重写规则时，从给定id看到的eclass的节点永远不会改变。这意味着我们只需要在那个节点id上应用重写规则一次。

数据结构和示例

每个eclass id都指向一个表条目（“eclass节点”，它与“enode”不同），可以是以下之一

• 单个enode；
• 一个enode和一个它附加到的较早的eclass id（一个“子”eclass节点）；
• 一个包含两个较早eclass id的“并集节点”。

构建aegraph仅包括向eclass节点表的末尾添加新条目。任何给定eclass节点引用的enode只能引用较早的eclass id。

例如，考虑以下eclass表

   eclass/enode table

    eclass1    iconst(1)
    eclass2    blockparam(block0, 0)
    eclass3    iadd(eclass1, eclass2)

这表示表达式iadd(blockparam(block0, 0), iconst(1))（作为eclass3的唯一enode）。

现在，假设我们在进一步构建函数体时添加另一个enode iadd(eclass3, iconst(1))。iconst(1)将被去重到eclass1，而顶层的iadd将成为它自己的新eclass（eclass4）。

    eclass4    iadd(eclass3, eclass1)

现在我们应用我们的重写规则集，并将这些结果合并成 x + 1 + 1 为 x + 2；因此我们得到

    eclass5    iconst(2)
    eclass6    union(iadd(eclass2, eclass5), eclass4)

请注意，我们为新的表达式添加了节点，并将其与之前的 eclass4 进行了并集操作。从逻辑上讲，这代表了一个包含两个节点（x + 1 + 1 和 x + 2 的表示）的单个 eclass，而 eclass 的最新 id，即 eclass6，可以访问 eclass 中的所有节点（这里是在 eclass6 中存储的节点和之前在 elcass4 中的节点）。

aegraph 与 egraph

一个 aegraph 在哪里比 e-graph 弱？或者说，为什么要维护数据结构以允许进行全部（重）规范化的操作，例如使用父指针递归更新父节点？

这个问题值得进一步研究，但到目前为止，它似乎仅限于以下情况

• 表达式 E1 已被内联到 aegraph 中。
• 表达式 E2 已被内联到 aegraph 中。它将 E1 作为一个或多个运算符的参数，因此引用了 E1 的（目前）最新 id。
• 表达式 E3 已被内联到 aegraph 中。触发了一个重写规则，将 E3 与 E1 联合。

在 e-graph 中，最后一步将触发 E1 所有“父节点”（用户）的重规范化；因此 E2 将使用表示 E1 和 E3 联合的 id 进行重规范化。在代码生成时，E2 可以选择使用由 E1 或 E3 的运算符计算出的值。在 aegraph 中，情况并非如此：E2 的 e-class 和 e-nodes 在创建后是不可变的，因此 E2 仅引用 E1 的值表示（整个 e-class 的“切片”）。

虽然一开始这似乎相当受限，但实际上似乎与重写规则的即时应用有很好的相互作用：通过在 E1 内联时应用我们知道的全部重写，E2 可以在创建时引用最佳版本。上述场景只有在以下情况下才会导致错过优化

• 存在从 E3 到 E1 的重写规则，但没有从 E1 到 E3 的规则；并且
• E3 比 E1 更便宜。

换句话说，这只有在存在将重写为更昂贵方向的规则时才有意义。这在我们计划编写的重写规则中不太可能发生；如果可能表达许多等价性，如结合性、交换性等，这可能会更加重要。

请注意，上述内容代表了我们理解的最佳情况，但可能还有我们遗漏的情况；对此问题的更完整检查将涉及在此软件包的（a）egraph 上构建完整的等价性饱和循环，并通过许多基准测试来查看它是否会产生任何差异。

重写规则（FLAX：快速本地化 aegraph 扩展）

电子图或aegraph最常见的用途是作为编译器的中间表示（IR）。在这种用法中，我们通常希望使用一组表示有效变换（等价且希望更简单的计算结果方式）的重写规则来转换程序。aegraph支持以相当直接的方式应用规则：每当向表中添加一个新的eclass条目时，我们就会调用一个顶层的“应用所有重写规则”的入口点。此入口点会根据需要创建新节点，完成后，将重写后的节点与原始节点合并。因此，我们立即将新值扩展到其所有表示形式。

这种即时扩展与传统“等价饱和”e-egraph系统形成对比，在后者中，通常最好分批应用规则，然后修复规范化的结果。这种方法在egg e-egraph引擎中被引入[^1]。我们称我们的系统为FLAX（因为flax是egg的替代品）：快速本地化aegraph扩展。

这种技术在aegraph中可行，而在传统的e-graph中（至少是高效地）不可行的原因在于，一旦创建，节点数据结构是不可变的：一个eclass id将始终指向一个固定的enodes集合。在它们合并时，不会重新规范化eclass参数；但这也通常不是必要的，因为参数已经被处理并急切地重写。换句话说，急切重写和不可变的数据结构相互允许对方实用；它们共同工作。

[^1]: M Willsey, C Nandi, Y R Wang, O Flatt, Z Tatlock, P Panchekha. "egg: Fast and Flexible Equality Saturation." In POPL 2021. https://dl.acm.org/doi/10.1145/3434304