There are many algorithms for the space-time mapping of nested loops. Some
of them even make the optimal choices within their framework. We propose a
preprocessing phase for algorithms in the polytope model, which extends the
model and yields space-time mappings whose schedule is, in some cases, ord
ers of magnitude faster. These are cases in which the dependence graph has
small irregularities. The basic idea is to split the index set of the loop
nests into parts with a regular dependence structure and apply the existing
space-time mapping algorithms to these parts individually. This work is ba
sed on a seminal idea in the more limited context of loop parallelization a
t the code level. We elevate the idea to the model level (our model is the
polytope model), which increases its applicability by providing a clearer a
nd wider range of choices at an acceptable analysis cost. Index set splitti
ng is one facet in the effort to extend the power of the polytope model and
to enable the generation of competitive tar-get code.