The polyhedral model is a technique for optimizing loop nests in a program. Each calculated value is modeled by a point, and the dependencies among the values from one iteration to the next are modeled by vectors connecting the points. The result is an object called a polytope that lies in an n-dimensional space, where n is the number of loops. Each point of the polytope has the values of the loop indexes as its coordinates in that space. Performance improvements can be made by applying certain kinds of geometrical transformations to the polytope and then converting the result back to code.

Analysis is carried out at compile time, based on static properties of the program, and must therefore make conservative assumptions. Previous papers proposed a framework to support dynamic analysis and speculative execution of the model. Here, Sukumaran-Rajam and Clauss show how to remove some of the constraints that the model places on the behavior of loop variables and the form of index expressions.

After introducing the problem, the authors discuss the polyhedral model and its limitations. They then provide the architecture of Apollo, the system discussed in earlier papers, and explain how they extend it to remove its constraints. The paper concludes with a review of related work and some results obtained by applying the extended framework to programs selected from several standard benchmark suites.

The paper is well written but quite dense; I would not recommend it to a novice in the optimization area. A reader is expected to understand multicore optimization techniques in general and the polyhedral model in particular. There is a good set of references to help access this material, and the examples are well chosen. A person familiar with the area should have little difficulty understanding and evaluating the authors’ contribution.