Evaluation and Implementation of Dominance Breaking Presolving Techniques in the Unison Compiler Back-End
Mikael Almgren · KTH Publication Database DiVA (KTH Royal Institute of Technology) · 2015
Constraint-based compiler back-ends use constraint programming to solve some of the translation stages that a compiler back-end typically is constructed of. Using constraint programming enables the compiler to generate optimal target code that is faster and more robust compared to code generated by a traditional compiler back-end. With constraint programming, problems are modeled and automatically solved by a constraint solver. A method to make the solving less time-consuming is presolving. Presolving derives new information about a problem that can be applied to its model before the actual solving. This thesis focuses on evaluating a set of dominance breaking presolving techniques in a constraint-based compiler back-end. A dominance relation in constraint programming is two assignments that are in some sense equivalent. Based on the evaluation some of the presolving techniques are re-implemented in an open source constraint-solving toolkit, to remove dependencies on proprietary, but commonly available, systems inside the constraint-based compiler. The re-implemented techniques show similar or better performance than the original implementations of the techniques. In the best case, the re-implemented techniques shows an efficiency increase of 50 % compared to the original implementations.