A Reinforcement Learning Environment for Polyhedral Optimizations
  The polyhedral model allows a structured way of defining semantics-preserving
transformations to improve the performance of a large class of loops. Finding
profitable points in this space is a hard problem which is usually approached
by heuristics that generalize from domain-expert knowledge. Existing problem
formulations in state-of-the-art heuristics depend on the shape of particular
loops, making it hard to leverage generic and more powerful optimization
techniques from the machine learning domain. In this paper, we propose PolyGym,
a shape-agnostic formulation for the space of legal transformations in the
polyhedral model as a Markov Decision Process (MDP). Instead of using
transformations, the formulation is based on an abstract space of possible
schedules. In this formulation, states model partial schedules, which are
constructed by actions that are reusable across different loops. With a simple
heuristic to traverse the space, we demonstrate that our formulation is
powerful enough to match and outperform state-of-the-art heuristics. On the
Polybench benchmark suite, we found transformations that led to a speedup of
3.39x over LLVM O3, which is 1.83x better than the speedup achieved by ISL. Our
generic MDP formulation enables using reinforcement learning to learn
optimization policies over a wide range of loops. This also contributes to the
emerging field of machine learning in compilers, as it exposes a novel problem
formulation that can push the limits of existing methods.
