AST Generation Paper published in TOPLAS
The July issue of TOPLAS contains a 50 page discussion of the AST generation
techniques used in Polly. This discussion gives not only an in-depth
description of how we (re)generate an imperative AST from our polyhedral based
mathematical program description, but also gives interesting insights about:
- Schedule trees: A tree-based mathematical program description that enables us
to perform loop transformations on an abstract level, while issues like the
generation of the correct loop structure and loop bounds will be taken care of
by our AST generator.
- Polyhedral unrolling: We discuss techniques that allow the unrolling of
non-trivial loops in the context of parameteric loop bounds, complex tile
shapes and conditionally executed statements. Such unrolling support enables
the generation of predicated code e.g. in the context of GPGPU computing.
- Isolation for full/partial tile separation: We discuss native support for
handling full/partial tile separation and -- in general -- native support for
isolation of boundary cases to enable smooth code generation for core
computations.
- AST generation with modulo constraints: We discuss how modulo mappings are
lowered to efficient C/LLVM code.
- User-defined constraint sets for run-time checks We discuss how arbitrary
sets of constraints can be used to automatically create run-time checks that
ensure a set of constrainst actually hold. This feature is very useful to
verify at run-time various assumptions that have been taken program
optimization.
Polyhedral AST generation is more than scanning polyhedra
Tobias Grosser, Sven Verdoolaege, Albert Cohen
ACM Transations on Programming Languages and Systems (TOPLAS), 37(4), July 2015
llvm-svn: 245157
diff --git a/polly/lib/Transform/ScheduleOptimizer.cpp b/polly/lib/Transform/ScheduleOptimizer.cpp
index 26b9668..1e06309 100644
--- a/polly/lib/Transform/ScheduleOptimizer.cpp
+++ b/polly/lib/Transform/ScheduleOptimizer.cpp
@@ -7,14 +7,43 @@
//
//===----------------------------------------------------------------------===//
//
-// This pass the isl to calculate a schedule that is optimized for parallelism
-// and tileablility. The algorithm used in isl is an optimized version of the
-// algorithm described in following paper:
+// This pass generates an entirey new schedule tree from the data dependences
+// and iteration domains. The new schedule tree is computed in two steps:
//
-// U. Bondhugula, A. Hartono, J. Ramanujam, and P. Sadayappan.
-// A Practical Automatic Polyhedral Parallelizer and Locality Optimizer.
-// In Proceedings of the 2008 ACM SIGPLAN Conference On Programming Language
-// Design and Implementation, PLDI ’08, pages 101–113. ACM, 2008.
+// 1) The isl scheduling optimizer is run
+//
+// The isl scheduling optimizer creates a new schedule tree that maximizes
+// parallelism and tileability and minimizes data-dependence distances. The
+// algorithm used is a modified version of the ``Pluto'' algorithm:
+//
+// U. Bondhugula, A. Hartono, J. Ramanujam, and P. Sadayappan.
+// A Practical Automatic Polyhedral Parallelizer and Locality Optimizer.
+// In Proceedings of the 2008 ACM SIGPLAN Conference On Programming Language
+// Design and Implementation, PLDI ’08, pages 101–113. ACM, 2008.
+//
+// 2) A set of post-scheduling transformations is applied on the schedule tree.
+//
+// These optimizations include:
+//
+// - Tiling of the innermost tilable bands
+// - Prevectorization - The coice of a possible outer loop that is strip-mined
+// to the innermost level to enable inner-loop
+// vectorization.
+// - Some optimizations for spatial locality are also planned.
+//
+// For a detailed description of the schedule tree itself please see section 6
+// of:
+//
+// Polyhedral AST generation is more than scanning polyhedra
+// Tobias Grosser, Sven Verdoolaege, Albert Cohen
+// ACM Transations on Programming Languages and Systems (TOPLAS),
+// 37(4), July 2015
+// http://www.grosser.es/#pub-polyhedral-AST-generation
+//
+// This publication also contains a detailed discussion of the different options
+// for polyhedral loop unrolling, full/partial tile separation and other uses
+// of the schedule tree.
+//
//===----------------------------------------------------------------------===//
#include "polly/ScheduleOptimizer.h"