  Rewrite systems [6, 10, 12] have been widely employing equality saturation
[9], which is an optimisation methodology that uses a saturated e-graph to
represent all possible sequences of rewrite simultaneously, and then extracts
the optimal one. As such, optimal results can be achieved by avoiding the
phase-ordering problem. However, we observe that when the e-graph is not
saturated, it cannot represent all possible rewrite opportunities and therefore
the phase-ordering problem is re-introduced during the construction phase of
the e-graph. To address this problem, we propose MCTS-GEB, a domain-general
rewrite system that applies reinforcement learning (RL) to e-graph
construction. At its core, MCTS-GEB uses a Monte Carlo Tree Search (MCTS) [3]
to efficiently plan for the optimal e-graph construction, and therefore it can
effectively eliminate the phase-ordering problem at the construction phase and
achieve better performance within a reasonable time. Evaluation in two
different domains shows MCTS-GEB can outperform the state-of-the-art rewrite
systems by up to 49x, while the optimisation can generally take less than an
hour, indicating MCTS-GEB is a promising building block for the future
generation of rewrite systems.
