Associativity and Commutativity in Equality Saturation
In the authors' words
Equality saturation is a promising technique for program optimization which sidesteps the phase ordering problem. However, current e-graph implementations grow exponentially large, even for simple examples. Many practical applications involve associative and commutative (AC) operators. We present an extension of relational e-matching that handles AC operators natively by storing terms as multisets. Preliminary results show that equality saturation modulo AC uses asymptotically less memory in certain cases.
Main resultLimitation the authors admit
Appeared: Friday, October 2. arXiv. Preprint, not yet peer-reviewed.