Constraint Programming in Compiler Optimization: Lessons Learned

Summary form only given. Instruction scheduling and instruction selection are two optimization problems that arise in compilers. These problems are considered intractable, and heuristic approaches are currently used in production compilers. In contrast, we have pursued constraint programming approaches that are fast and optimal. The primary goals of this application-driven research were twofold: (i) find solutions of significantly higher quality, and (ii) develop novel constraint programming techniques which have general applicability to similar optimization problems. In this talk, I will describe how successful we were in achieving these goals and some of the lessons we learned along the way.