Evaluating the egg Equality Saturation Superoptimizer

Superoptimization is the idea of creating the most optimal program possible from a given input program. Equality saturation is a method of superoptimization using rewrite rules and e-graphs. A rewrite rule defines a piece of code that can be rewritten as another part while keeping equal behavior. This is added to an e-graph, a data structure which is able to express a lot of equal programs efficiently using e-nodes and e-classes. Egg is a general equality saturation superoptimizer developed in Rust, which has been the basis of multiple extensions. This research first aimed to validate claims made by the creators of egg which stated that rebuilding improved equality saturation. Secondly, the research aimed to evaluate the performance of egg when supplying a different amount of rewrite rules. The research found that egg indeed does improve equality saturation, with an 88× speedup for a part of the algorithm as claimed by the creators, but a claim of 21× overall speedup is an overestimate, as an overall speedup of between 16.4× and 17.4× was achieved. The second part shows that providing egg with extra unused rewrite rules slows the algorithm down, although the slowdown seems to decrease when the size of the program increases. The second part also tried to draw a conclusion on adding rewrite rules which will be applied indirectly via multiple other rewrite rules, called implied rewrite rules. Two tests indicated a speedup, but another indicated a slowdown. This means it is unknown if adding implied rewrite rules is beneficial, as no general conclusion could be drawn. Therefore, egg seems to benefit from removing unused rewrite rules, and might benefit from adding implied rewrite rules.CSE3000 Research ProjectComputer Science and Engineerin