When extracting an RTL implementation from an e-graph, one is immediately faced with the question of common subexpressions. Common subexpressions are naturally extracted as part of the e-graph construction process [1]} and ideally we would want to utilize this information in the resulting hardware, for example extracting \((x+1) \times (x+1)\)  as \(\texttt {let } y = x+1\text{ in }y \times y\) . However, this makes the extraction problem an inherently global problem over the e-classes, in the sense that the optimal e-node implementation for a given e-class may depend on the selected e-node implementation of the other e-classes in the graph. Previous solutions have solved this by posing optimal extraction as an integer linear programming (ILP) problem [2]}, [3]}, and we follow the same approach in this work.
