Scanning Index Sets with Polynomial Bounds Using Cylindrical Algebraic Decomposition

Abstract. Automatic, model-based program transformation relies on the ability to generate code from a model description of the program. In the context of automatic parallelisation, cache optimisation and similar transformations, the task is to generate loop nests which enumerate the iteration points within given domains. Several approaches to code gener-ation from polyhedral descriptions of iteration sets have been proposed and are in use. We present an approach to generating loop nests for index sets with arbitrary polynomials as bounds using cylindrical alge-braic decomposition. The generated loops are efficient in the sense that no integer superset is enumerated. We also state where this technique is useful, i.e., where non-linearities in the loop bounds arise in loop pro-gram transformations and show some examples for our approach with polyhedral and non-polyhedral input.