Use marker nodes to annotate the different levels of tiling

Currently, marker nodes are ignored during AST generation, but visible in the
-debug-only=polly-ast output.

llvm-svn: 245809

4 files changed, 61 insertions, 14 deletions

diff --git a/polly/include/polly/CodeGen/IslNodeBuilder.h b/polly/include/polly/CodeGen/IslNodeBuilder.h
index 3298e9de929..1adb86e7ef2 100644
--- a/polly/include/polly/CodeGen/IslNodeBuilder.h
+++ b/polly/include/polly/CodeGen/IslNodeBuilder.h
@@ -174,6 +174,14 @@ private:
   /// @param NewValues A map that maps certain llvm::Values to new llvm::Values.
   void updateValues(ParallelLoopGenerator::ValueToValueMapTy &NewValues);
 
+  /// @brief Generate code for a marker now.
+  ///
+  /// For mark nodes with an unknown name, we just forward the code generation
+  /// to its child. This is currently the only behavior implemented, as there is
+  /// currently not special handling for marker nodes implemented.
+  ///
+  /// @param Mark The node we generate code for.
+  void createMark(__isl_take isl_ast_node *Marker);
   void createFor(__isl_take isl_ast_node *For);
   void createForVector(__isl_take isl_ast_node *For, int VectorWidth);
   void createForSequential(__isl_take isl_ast_node *For);
diff --git a/polly/lib/CodeGen/IslNodeBuilder.cpp b/polly/lib/CodeGen/IslNodeBuilder.cpp
index 60619c35bbd..b3582079a3f 100644
--- a/polly/lib/CodeGen/IslNodeBuilder.cpp
+++ b/polly/lib/CodeGen/IslNodeBuilder.cpp
@@ -275,6 +275,12 @@ void IslNodeBuilder::createUserVector(__isl_take isl_ast_node *User,
   isl_ast_node_free(User);
 }
 
+void IslNodeBuilder::createMark(__isl_take isl_ast_node *Node) {
+  auto Child = isl_ast_node_mark_get_node(Node);
+  create(Child);
+  isl_ast_node_free(Node);
+}
+
 void IslNodeBuilder::createForVector(__isl_take isl_ast_node *For,
                                      int VectorWidth) {
   isl_ast_node *Body = isl_ast_node_for_get_body(For);
@@ -691,7 +697,8 @@ void IslNodeBuilder::create(__isl_take isl_ast_node *Node) {
   case isl_ast_node_error:
     llvm_unreachable("code generation error");
   case isl_ast_node_mark:
-    llvm_unreachable("Mark node unexpected");
+    createMark(Node);
+    return;
   case isl_ast_node_for:
     createFor(Node);
     return;
diff --git a/polly/lib/Transform/ScheduleOptimizer.cpp b/polly/lib/Transform/ScheduleOptimizer.cpp
index 10614478c50..0296af4e909 100644
--- a/polly/lib/Transform/ScheduleOptimizer.cpp
+++ b/polly/lib/Transform/ScheduleOptimizer.cpp
@@ -187,13 +187,16 @@ private:
   /// @brief Tile a schedule node.
   ///
   /// @param Node            The node to tile.
+  /// @param Identifier      An name that identifies this kind of tiling and
+  ///                        that is used to mark the tiled loops in the
+  ///                        generated AST.
   /// @param TileSizes       A vector of tile sizes that should be used for
   ///                        tiling.
   /// @param DefaultTileSize A default tile size that is used for dimensions
   ///                        that are not covered by the TileSizes vector.
   static __isl_give isl_schedule_node *
-  tileNode(__isl_take isl_schedule_node *Node, ArrayRef<int> TileSizes,
-           int DefaultTileSize);
+  tileNode(__isl_take isl_schedule_node *Node, const char *Identifier,
+           ArrayRef<int> TileSizes, int DefaultTileSize);
 
   /// @brief Check if this node is a band node we want to tile.
   ///
@@ -317,17 +320,30 @@ IslScheduleOptimizer::prevectSchedBand(__isl_take isl_schedule_node *Node,
 
 __isl_give isl_schedule_node *
 IslScheduleOptimizer::tileNode(__isl_take isl_schedule_node *Node,
-                               ArrayRef<int> TileSizes, int DefaultTileSize) {
+                               const char *Identifier, ArrayRef<int> TileSizes,
+                               int DefaultTileSize) {
   auto Ctx = isl_schedule_node_get_ctx(Node);
   auto Space = isl_schedule_node_band_get_space(Node);
   auto Dims = isl_space_dim(Space, isl_dim_set);
   auto Sizes = isl_multi_val_zero(Space);
+  std::string IdentifierString(Identifier);
   for (unsigned i = 0; i < Dims; i++) {
     auto tileSize = i < TileSizes.size() ? TileSizes[i] : DefaultTileSize;
     Sizes = isl_multi_val_set_val(Sizes, i, isl_val_int_from_si(Ctx, tileSize));
   }
+  auto TileLoopMarkerStr = IdentifierString + " - Tiles";
+  isl_id *TileLoopMarker =
+      isl_id_alloc(Ctx, TileLoopMarkerStr.c_str(), nullptr);
+  Node = isl_schedule_node_insert_mark(Node, TileLoopMarker);
+  Node = isl_schedule_node_child(Node, 0);
   Node = isl_schedule_node_band_tile(Node, Sizes);
-  return isl_schedule_node_child(Node, 0);
+  Node = isl_schedule_node_child(Node, 0);
+  auto PointLoopMarkerStr = IdentifierString + " - Points";
+  isl_id *PointLoopMarker =
+      isl_id_alloc(Ctx, PointLoopMarkerStr.c_str(), nullptr);
+  Node = isl_schedule_node_insert_mark(Node, PointLoopMarker);
+  Node = isl_schedule_node_child(Node, 0);
+  return Node;
 }
 
 bool IslScheduleOptimizer::isTileableBandNode(
@@ -365,14 +381,17 @@ IslScheduleOptimizer::optimizeBand(__isl_take isl_schedule_node *Node,
     return Node;
 
   if (FirstLevelTiling)
-    Node = tileNode(Node, FirstLevelTileSizes, FirstLevelDefaultTileSize);
+    Node = tileNode(Node, "1st level tiling", FirstLevelTileSizes,
+                    FirstLevelDefaultTileSize);
 
   if (SecondLevelTiling)
-    Node = tileNode(Node, SecondLevelTileSizes, SecondLevelDefaultTileSize);
+    Node = tileNode(Node, "2nd level tiling", SecondLevelTileSizes,
+                    SecondLevelDefaultTileSize);
 
   if (RegisterTiling) {
     auto *Ctx = isl_schedule_node_get_ctx(Node);
-    Node = tileNode(Node, RegisterTileSizes, RegisterDefaultTileSize);
+    Node = tileNode(Node, "Register tiling", RegisterTileSizes,
+                    RegisterDefaultTileSize);
     Node = isl_schedule_node_band_set_ast_build_options(
         Node, isl_union_set_read_from_str(Ctx, "{unroll[x]}"));
   }
diff --git a/polly/test/ScheduleOptimizer/rectangular-tiling.ll b/polly/test/ScheduleOptimizer/rectangular-tiling.ll
index 2aa8917f2fd..4da5bb35fc0 100644
--- a/polly/test/ScheduleOptimizer/rectangular-tiling.ll
+++ b/polly/test/ScheduleOptimizer/rectangular-tiling.ll
@@ -22,8 +22,10 @@
 ; RUN:                -polly-2nd-level-tile-sizes=16,8 < %s | \
 ; RUN: FileCheck %s --check-prefix=TWO-PLUS-REGISTER-PLUS-VECTORIZATION
 
+; CHECK: // 1st level tiling - Tiles
 ; CHECK: for (int c0 = 0; c0 <= 3; c0 += 1)
 ; CHECK:   for (int c1 = 0; c1 <= 31; c1 += 1)
+; CHECK:     // 1st level tiling - Points
 ; CHECK:     for (int c2 = 0; c2 <= 255; c2 += 1)
 ; CHECK:       for (int c3 = 0; c3 <= 15; c3 += 1)
 ; CHECK:         Stmt_for_body3(256 * c0 + c2, 16 * c1 + c3);
@@ -33,26 +35,37 @@
 ; NOTILING:     Stmt_for_body3(c0, c1);
 
 
+; TWOLEVEL: // 1st level tiling - Tiles
 ; TWOLEVEL: for (int c0 = 0; c0 <= 3; c0 += 1)
 ; TWOLEVEL:   for (int c1 = 0; c1 <= 31; c1 += 1)
+; TWOLEVEL:     // 1st level tiling - Points
+; TWOLEVEL:     // 2nd level tiling - Tiles
 ; TWOLEVEL:     for (int c2 = 0; c2 <= 15; c2 += 1)
 ; TWOLEVEL:       for (int c3 = 0; c3 <= 1; c3 += 1)
+; TWOLEVEL:         // 2nd level tiling - Points
 ; 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);
 
 
+; TWO-PLUS-REGISTER: // 1st level tiling - Tiles
 ; TWO-PLUS-REGISTER: for (int c0 = 0; c0 <= 3; c0 += 1)
 ; TWO-PLUS-REGISTER:   for (int c1 = 0; c1 <= 31; c1 += 1)
+; TWO-PLUS-REGISTER:     // 1st level tiling - Points
+; TWO-PLUS-REGISTER:     // 2nd level tiling - Tiles
 ; TWO-PLUS-REGISTER:     for (int c2 = 0; c2 <= 15; c2 += 1)
 ; TWO-PLUS-REGISTER:       for (int c3 = 0; c3 <= 1; c3 += 1)
+; TWO-PLUS-REGISTER:         // 2nd level tiling - Points
+; TWO-PLUS-REGISTER:         // Register tiling - Tiles
 ; TWO-PLUS-REGISTER:         for (int c4 = 0; c4 <= 7; c4 += 1)
-; TWO-PLUS-REGISTER:           for (int c5 = 0; c5 <= 3; c5 += 1) {
-; TWO-PLUS-REGISTER:             Stmt_for_body3(256 * c0 + 16 * c2 + 2 * c4, 16 * c1 + 8 * c3 + 2 * c5);
-; TWO-PLUS-REGISTER:             Stmt_for_body3(256 * c0 + 16 * c2 + 2 * c4, 16 * c1 + 8 * c3 + 2 * c5 + 1);
-; TWO-PLUS-REGISTER:             Stmt_for_body3(256 * c0 + 16 * c2 + 2 * c4 + 1, 16 * c1 + 8 * c3 + 2 * c5);
-; TWO-PLUS-REGISTER:             Stmt_for_body3(256 * c0 + 16 * c2 + 2 * c4 + 1, 16 * c1 + 8 * c3 + 2 * c5 + 1);
-; TWO-PLUS-REGISTER:           }
+; TWO-PLUS-REGISTER:           for (int c5 = 0; c5 <= 3; c5 += 1)
+; TWO-PLUS-REGISTER:             // Register tiling - Points
+; TWO-PLUS-REGISTER:             {
+; TWO-PLUS-REGISTER:               Stmt_for_body3(256 * c0 + 16 * c2 + 2 * c4, 16 * c1 + 8 * c3 + 2 * c5);
+; TWO-PLUS-REGISTER:               Stmt_for_body3(256 * c0 + 16 * c2 + 2 * c4, 16 * c1 + 8 * c3 + 2 * c5 + 1);
+; TWO-PLUS-REGISTER:               Stmt_for_body3(256 * c0 + 16 * c2 + 2 * c4 + 1, 16 * c1 + 8 * c3 + 2 * c5);
+; TWO-PLUS-REGISTER:               Stmt_for_body3(256 * c0 + 16 * c2 + 2 * c4 + 1, 16 * c1 + 8 * c3 + 2 * c5 + 1);
+; TWO-PLUS-REGISTER:             }
 
 ; TWO-PLUS-REGISTER-PLUS-VECTORIZATION: #pragma known-parallel
 ; TWO-PLUS-REGISTER-PLUS-VECTORIZATION: for (int c0 = 0; c0 <= 3; c0 += 1)