Add support for two-level tiling

By default we only use one level of tiling for loops, but in general tiling
for multiple levels is trivial for us. Hence, we add a set of options that
allow people to play with a second level of tiling. If this is profitable for
some cases we can work on heuristics that allow us to identify these cases
and use two-level tiling for them.

llvm-svn: 245563

2 files changed, 50 insertions, 14 deletions

diff --git a/polly/lib/Transform/ScheduleOptimizer.cpp b/polly/lib/Transform/ScheduleOptimizer.cpp
index c0584c1b99c..8c773d817a1 100644
--- a/polly/lib/Transform/ScheduleOptimizer.cpp
+++ b/polly/lib/Transform/ScheduleOptimizer.cpp
@@ -71,11 +71,6 @@ using namespace polly;
 
 #define DEBUG_TYPE "polly-opt-isl"
 
-static cl::opt<bool> EnableTiling("polly-tiling",
-                                  cl::desc("Enable loop tiling"),
-                                  cl::init(true), cl::ZeroOrMore,
-                                  cl::cat(PollyCategory));
-
 static cl::opt<std::string>
     OptimizeDeps("polly-opt-optimize-only",
                  cl::desc("Only a certain kind of dependences (all/raw)"),
@@ -113,18 +108,40 @@ static cl::opt<int> PrevectorWidth(
         "The number of loop iterations to strip-mine for pre-vectorization"),
     cl::Hidden, cl::init(4), cl::ZeroOrMore, cl::cat(PollyCategory));
 
-static cl::opt<int> DefaultTileSize(
+static cl::opt<bool> FirstLevelTiling("polly-tiling",
+                                      cl::desc("Enable loop tiling"),
+                                      cl::init(true), cl::ZeroOrMore,
+                                      cl::cat(PollyCategory));
+
+static cl::opt<int> FirstLevelDefaultTileSize(
     "polly-default-tile-size",
     cl::desc("The default tile size (if not enough were provided by"
              " --polly-tile-sizes)"),
     cl::Hidden, cl::init(32), cl::ZeroOrMore, cl::cat(PollyCategory));
 
-static cl::list<int> TileSizes("polly-tile-sizes",
-                               cl::desc("A tile size"
-                                        " for each loop dimension, filled with"
-                                        " --polly-default-tile-size"),
-                               cl::Hidden, cl::ZeroOrMore, cl::CommaSeparated,
-                               cl::cat(PollyCategory));
+static cl::list<int> FirstLevelTileSizes(
+    "polly-tile-sizes", cl::desc("A tile size for each loop dimension, filled "
+                                 "with --polly-default-tile-size"),
+    cl::Hidden, cl::ZeroOrMore, cl::CommaSeparated, cl::cat(PollyCategory));
+
+static cl::opt<bool>
+    SecondLevelTiling("polly-2nd-level-tiling",
+                      cl::desc("Enable a 2nd level loop of loop tiling"),
+                      cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
+
+static cl::opt<int> SecondLevelDefaultTileSize(
+    "polly-2nd-level-default-tile-size",
+    cl::desc("The default 2nd-level tile size (if not enough were provided by"
+             " --polly-2nd-level-tile-sizes)"),
+    cl::Hidden, cl::init(16), cl::ZeroOrMore, cl::cat(PollyCategory));
+
+static cl::list<int>
+    SecondLevelTileSizes("polly-2nd-level-tile-sizes",
+                         cl::desc("A tile size for each loop dimension, filled "
+                                  "with --polly-default-tile-size"),
+                         cl::Hidden, cl::ZeroOrMore, cl::CommaSeparated,
+                         cl::cat(PollyCategory));
+
 namespace {
 
 class IslScheduleOptimizer : public ScopPass {
@@ -325,8 +342,11 @@ IslScheduleOptimizer::optimizeBand(__isl_take isl_schedule_node *Node,
   if (!isTileableBandNode(Node))
     return Node;
 
-  if (EnableTiling)
-    Node = tileNode(Node, TileSizes, DefaultTileSize);
+  if (FirstLevelTiling)
+    Node = tileNode(Node, FirstLevelTileSizes, FirstLevelDefaultTileSize);
+
+  if (SecondLevelTiling)
+    Node = tileNode(Node, SecondLevelTileSizes, SecondLevelDefaultTileSize);
 
   if (PollyVectorizerChoice == VECTORIZER_NONE)
     return Node;
diff --git a/polly/test/ScheduleOptimizer/rectangular-tiling.ll b/polly/test/ScheduleOptimizer/rectangular-tiling.ll
index 56e9262346d..4d3bbe650ca 100644
--- a/polly/test/ScheduleOptimizer/rectangular-tiling.ll
+++ b/polly/test/ScheduleOptimizer/rectangular-tiling.ll
@@ -1,6 +1,12 @@
 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-opt-isl -analyze -polly-ast -polly-tile-sizes=256,16 < %s | FileCheck %s
 ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-opt-isl -analyze -polly-tiling=false -polly-ast -polly-tile-sizes=256,16 -polly-no-early-exit < %s | FileCheck %s --check-prefix=NOTILING
 
+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-opt-isl -analyze \
+; RUN:                -polly-2nd-level-tiling -polly-ast \
+; RUN:                -polly-tile-sizes=256,16 -polly-no-early-exit \
+; RUN:                -polly-2nd-level-tile-sizes=16,8 < %s | \
+; RUN: FileCheck %s --check-prefix=TWOLEVEL
+
 ; CHECK: for (int c0 = 0; c0 <= 3; c0 += 1)
 ; CHECK:   for (int c1 = 0; c1 <= 31; c1 += 1)
 ; CHECK:     for (int c2 = 0; c2 <= 255; c2 += 1)
@@ -11,6 +17,16 @@
 ; NOTILING:   for (int c1 = 0; c1 <= 511; c1 += 1)
 ; NOTILING:     Stmt_for_body3(c0, c1);
 
+
+; TWOLEVEL: for (int c0 = 0; c0 <= 3; c0 += 1)
+; TWOLEVEL:   for (int c1 = 0; c1 <= 31; c1 += 1)
+; TWOLEVEL:     for (int c2 = 0; c2 <= 15; c2 += 1)
+; TWOLEVEL:       for (int c3 = 0; c3 <= 1; c3 += 1)
+; TWOLEVEL:         for (int c4 = 0; c4 <= 15; c4 += 1)
+; TWOLEVEL:           for (int c5 = 0; c5 <= 7; c5 += 1)
+; TWOLEVEL:             Stmt_for_body3(256 * c0 + 16 * c2 + c4, 16 * c1 + 8 * c3 + c5);
+
+
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
 
 ; Function Attrs: nounwind