Generation of efficient nested loops from polyhedra

Automatic parallelization in the polyhedral model is based on affine transf ormations from an original computation domain (iteration space) to a target spacetime domain, often with a different transformation For each variable. Code generation is an often ignored step in this process that has a signif icant impact on the quality of the final code. It involves making a trade-o ff between code size and control code simplification/optimization. Previous methods of doing code generation are based on loop splitting, however they have nonoptimal behavior when working on parameterized programs. We presen t a general parameterized method For code generation based on dual represen tation of polyhedra. Our algorithm uses a simple recursion on the dimension s of the domains, and enables fine control over the tradeoff between code s ize and control overhead.