The Cost of Flattening with Common Subexpression Elimination

Compilingasolver-independentconstraintmodeltosolverinputusu- ally involves flattening, the decomposition of complex constraints into simpler expressions to suit the solver, introducing additional variables and constraints. In previous work, we have proposed extending flattening with common subex- pression elimination (CSE) which can reduce the overhead introduced during flat- tening. In this work, we formally analyse the cost of standard flattening and CSE- based flattening: we compare time and space complexity and investigate the po- tential variable and constraint reduction from CSE-based flattening, its scope and limitations. Furthermore, we discuss flattening whole problem classes and show how to integrate CSE into class-wise flattening. We highlight the differences to instance-wise flattening and discuss open questions. Finally, our empirical analy- sis confirms our theoretical findings and demonstrates the benefits of CSE-based flattening.