PLDI 2025
Mon 16 - Fri 20 June 2025 Seoul, South Korea

This program is tentative and subject to change.

Wed 18 Jun 2025 11:50 - 12:10 at Grand Ball Room 1 - Compilers 1

Equality saturation has gained significant interest as a powerful optimization and reasoning technique. At its heart is the e-graph data structure, that space-efficiently represents equal sub-terms uniquely.
An important open problem in this context is extending this efficient representation to languages featuring (bound) variables.
Independent of how we represent variables in e-graphs, either as names or nameless (using de Bruijn indices), sharing is broken as sub-terms that differ only in the names of their variables are represented separately.
This results in aggressive e-graph growth, bad performance, as well as reduced expressiveness.

In this paper, we present a novel approach to representing bound variables in e-graphs by making them a first-class built-in feature of the data structure.
Our <em>slotted e-graph</em> represents terms that differ only by (bound or free) variable names uniquely.
To do so, e-classes that represent equivalent terms via e-nodes are parameterized by <em>slots</em>, abstracting over free variables of the represented terms.
Referring to an e-class from an e-node now requires relating the variables from its context to the slots of the e-class.

Our evaluation of slotted e-graph uses two case studies from compiler optimization and theorem proving to show that performing equality saturation for languages with bound variables is greatly simplified and that we can solve practically relevant problems that cannot be solved with e-graphs using de Bruijn indices.

This program is tentative and subject to change.

Wed 18 Jun

Displayed time zone: Seoul change

10:30 - 12:10
10:30
20m
Talk
Partial Evaluation, Whole-Program Compilation
PLDI Research Papers
Chris Fallin F5, Maxwell Bernstein Recurse Center
DOI
10:50
20m
Talk
Exploiting Undefined Behavior in C/C++ Programs for Optimization: A Study on the Performance Impact
PLDI Research Papers
Lucian Popescu INESC-ID; Instituto Superior Técnico - University of Lisbon; Politehnica University of Bucharest, Nuno P. Lopes INESC-ID; Instituto Superior Técnico - University of Lisbon
Link to publication DOI
11:10
20m
Talk
Relaxing Alias Analysis: Exploring the Unexplored Space
PLDI Research Papers
Michel Weber ETH Zurich, Theodoros Theodoridis ETH Zurich, Zhendong Su ETH Zurich
DOI
11:30
20m
Talk
Webs and Flow-Directed Well-Typedness Preserving Program Transformations
PLDI Research Papers
Benjamin Quiring University of Maryland, David Van Horn University of Maryland, John Reppy University of Chicago, Olin Shivers Northeastern University
DOI
11:50
20m
Talk
Slotted E-Graphs: First-Class Support for (Bound) Variables in E-Graphs
PLDI Research Papers
Rudi Schneider Technische Universität Berlin, Marcus Rossel Barkhausen Institut, Amir Shaikhha University of Edinburgh, Andrés Goens University of Amsterdam, Thomas Koehler CNRS - ICube Lab, Michel Steuwer Technische Universität Berlin
DOI