Traditional program optimization suffer from the phase ordering problem: Optimization performance is dependent upon the order of program rewrites. Once a rewrite occurs, the initial program cannot be easily recovered. E-graphs can efficiently represent many different, equivalent programs—enabling non-destructive rewrites, where the initial term is retained in the e-graph, in a process known as equality saturation. However, e-graph size tends to explode with certain rewrite rules. For example, associativity and commutativity can result in an exponentially growing e-graph. This limits the practicality of e-graph driven optimization because the time complexity of equality saturation is linearly dependent on e-graph size. The compiler backend Cranelift uses a modified version of e-graphs termed "acyclic e-graphs," where production-grade performance is achieved at the cost of acyclicity and limit the expressivity of rewrites.

We introduce destructive e-graph rewrites, where the e-graph size can be reduced during equality saturation by undoing rewrites. Given a rewrite L → R, undoing it involves finding all programs matching R and removing them from the e-graph. In the egg e-graph library, destructive rewrites speed up some benchmarks by 5x and improve with larger e-graphs. We are currently applying destructive rewrites in Herbie, a project to optimize floating point expressions that uses e-graphs during its optimization workflow. Destructive rewrites remove intermediate programs from the e-graph—an optimal program may be reached through multiple intermediate rewrites that produce intermediate programs. Once the optimal program is added to the e-graph, the intermediate programs can be removed.