Egg: Efficient Equality Saturation for Rewriting Expressions

Add to your list(s) Download to your calendar using vCal

• Sam Coward (Imperial College)
• Monday 12 July 2021, 16:00-17:00
• Teams (in the "CAS Seminars" team).

If you have a question about this talk, please contact George A Constantinides.

Most projects that use some form of rewrite engine suffer from the phase ordering problem, which asks the question what order should you apply your rewrites in. Equality saturation offers a solution to this problem, using e-graphs. E-graphs, originally developed in the 70s, provide a very dense representation of a congruence relation over different expressions. The basic idea behind equality saturation is to continue to apply your rewrites to the e-graph until further rewrites add no additional information to it. Egg is an open-source library from the University of Washington, providing an efficient implementation of equality saturation, adding a couple of novel contributions to enhance performance. Assigning some cost metric to the nodes of our graph allows us to extract the “best” expression from the e-graph.

This talk is part of the CAS Talks series.

This talk is included in these lists:

• Andrea Picciau's list
• CAS Talks
• Circuits and Systems Group: Internal Seminars
• Teams (in the "CAS Seminars" team)

Note that ex-directory lists are not shown.