Towards Optimising Programs with Sketch-Guided Polyhedral Compilation

When programmers use semi-automatic compilers, they typically write optimisation scripts, to guide the compiler towards key optimisations. Instead of writing scripts, it may be preferable to write sketches that focus on the desired structure of the optimised code, without worrying about individual transformations. In this article, we present a new semi-automatic, sketchguided compilation approach. We introduce a sketch language that enables expressing the result of imperative loop transformations and a new polyhedral algorithm capable of generating code constrained by both a sketch and a computation specification.