[GSoC 2016] [Polly] [WIP] Apply all necessary tilings and interchangings to get a macro-kernel

[gareevroman]

Summary

This is the second patch to apply the BLIS matmul optimization pattern on matmul kernels (http://www.cs.utexas.edu/users/flame/pubs/TOMS-BLIS-Analytical.pdf). BLIS implements gemm as three nested loops around a macro-kernel, plus two packing routines. The macro-kernel is implemented in terms of two additional loops around a micro-kernel. The micro-kernel is a loop around a rank-1 (i.e., outer product) update. In this change we create the BLIS macro-kernel by applying a combination of tiling and interchanging. In subsequent changes we will implement the packing transformation.

[gareevroman]

This is a draft of the second patch to apply the BLIS matmul optimization pattern on matmul kernels. I'm not sure how it is better to implement interchanging of loops using schedule trees. That's why I would be very grateful for your comments, feedback and ideas.

I think that there are two ways to do it. The first way is to split a band node two times and perform sink to get the desired order of dimensions. In this case, the subtree of the band node would probably cause issues, if, for example, it contains mark nodes. As far as I know, they can't be sinked and should be manually reinserted.

The second way is to manually interchange dimensions of a partial schedule, delete the band node and insert a band node, which contains a new partial schedule. I've implemented it in the patch. However, there is a possible issue, because isl_schedule_node_delete can't be applied to a band node with an anchored subtree and isl_schedule_node_insert_partial_schedule can't be be applied to the schedule tree, which has anchored nodes.

[Meinersbur]

Thanks for the patch and meaningful comments.

include/polly/ScheduleOptimizer.h

124

vice versa

243–252

Please don't copy-paste the same text. There is a @see tag to refer to other parts.

lib/Transform/ScheduleOptimizer.cpp

539

also check for CacheLevelAssociativityDegrees.size() >=2 to avoid out-of-range errors?

553

You can use

int MacroKernelParams[] = {Mc, Nc, Kc};

here. It is automatically converted to ArrayRef<int>.

560–562

Style: No single return in an else branch. The following style seems to be established.

  if (c) {
    ...
    return X;
  }
  return Y;
}

578

Add an empty line befire to make clear that what is coming is another section?

[gareevroman]

In D21491#462093, @Meinersbur wrote:

Thanks for the patch and meaningful comments.

Thank you for the comments! I'll try to address them soon.

[gareevroman]

Changed according to the comments.

[gareevroman]

lib/Transform/ScheduleOptimizer.cpp

539

As far as I understand, it requires information about the first two levels of cache to determine all the parameters (Kc, Mc, Nc) of a macro-kernel. I've added a corresponding comment in the new version of the patch.

560–562

Thanks. In the new version I've tried to also take into account "Use Early Exits and continue to Simplify Code"

578

Yes, it's the reason. Probably, it's not good. I wasn't sure wether we should create a function to create a micro-kernel that contains only "std::vector<int> MicroKernelParams{Mr, Nr};" and "Node = applyRegisterTiling(Node, MicroKernelParams, 1);"

[grosser]

Hi Roman,

thanks for this patch and Michael thank you for your review! I added a couple of comments.

Best,
Tobias

include/polly/ScheduleOptimizer.h

111

Not part of this commit, but please add in a separate commit (no review needed) full title/author information to this paper, in case this link becomes dead at some point.

119

"interchanging The"

This seems incomplete.

121

This paper is already referenced earlier. No need to reference it again.

I personally would suggest to use @see to reference your implementation of the BLIS macro kernel, which than contains the macro-kernel specific information -- in sufficient detail to be self-contained without the BLIS paper.

122

Drop "it should be noticed". It does not add any additional information.

123

Drop "should". It does not add any specific information.

129

Make this a "TODO:"

129

Make this a TODO:

247

Can you document what "Mr" describes?

Also, the documentation of this function requires to have read the BLIS paper to understand what this parameter means. That seems not ideal. I suggest to expand this documentation to be (mostly) self contained.

(It seems you may have had more documentation here before. I suggest to move the documentation you have from optimizeMatMulPattern and add the @see in the other function).

lib/Transform/ScheduleOptimizer.cpp

138

What about" -polly-target-cache-level-associativity - The associativity of each cache level"

and CacheLevelAssociativity

144

What about "-polly-target-cache-level-sizes - The size of each cache level"?

and CacheLevelSizes

531

Nice!

540

than two.

554

In the subsequent patch you pull out the parameter calculation in a helper function. I suggest to do this already in this patch as otherwise code is just unnecessarily moved around.

559

Instead of just storing these parameters in a list of integers, I suggest to introduce a struct that allows us to encapsulate these parameters and access them by name.

struct MacroKernelParamsTy {                                                     
  int Mc;                                                                        
  int Nc;                                                                        
  int Kc;                                                                        
};                                                                               
                                                                                 
void foo() {                                                                     
  int Mc, Nc, Kc;                                                                
  struct MacroKernelParamsTy MacroKernelParams = {Mc, Nc, Kc};                   
}

560–562

Nice!

578

I am in favor of a new function. It might be mostly empty, but it helps to the code.

[gareevroman]

Hi Tobias,

Thank you for the comments! I've tried to address them. Should we pull out creation of the BLIS micro-kernel and its parameters in helper functions in a separate patch?

[gareevroman]

include/polly/ScheduleOptimizer.h

107–138

I'll try to do it soon.

[gareevroman]

The test case was missed.

[grosser]

Hi Roman,

this patch looks very good to me now. Please commit changes that just improve the code structure or documentation of existing code separately.

We can probably still improve the documentation of the cost functions further, but for now this looks sufficient. After all the infrastructure is in place, I expect that we perform further experiments and performance tuning. The results of these efforts will -- at the end of your summer of code -- certainly help us to extend the documentation.

include/polly/ScheduleOptimizer.h

48

Nice!

107–139

Very nice documentation!

153

"account in creation" -> "account during the creation of the BLIS of the BLIS kernels and the computation of their parameters."

164

The node is required to successfully pass ScheduleTreeOptimizer::isMatrMultPattern

245

The values of ...

259

The values passed in MicroKernelParam are used ...

lib/Transform/ScheduleOptimizer.cpp

585

During the computation of the matrix multiplication,

588

"It" sounds not right. What is it referring to?

598

Nice. This change and some of the changes to improve documentation can be committed separately.

608

Its 2nd for "second" or 1st for "first, "1nd" does not make sense.

617

We choose the Mr and Nr parameters of the micro kernel to be large enough such that no stalls

619

the updates _of_ the resulting

621

be as small as possible

[Meinersbur]

lib/Transform/ScheduleOptimizer.cpp

595

MicroKernelParamsTy,MacroKernelParamsTy are small enough to be passed by value.

[gareevroman]

lib/Transform/ScheduleOptimizer.cpp

595

MicroKernelParamsTy,MacroKernelParamsTy are small enough to be passed by value.

Hi Michael,

shouldn't we follow advices from "Effective C++", according to LLVM Coding Standards?

As far as I understand, in item 20 it is stated that the only types for which we can reasonably assume that pass-by-value is inexpensive are build-in types and STL iterator and function object types.

[Meinersbur]

lib/Transform/ScheduleOptimizer.cpp

595

LLVM has its own types that are neither STL or built-ins that are meant to be passes by value: ArrayRef, StringRef, PointerIntPair, CallSite, etc.

"Effective C++" in the LLVM Coding Standards is referenced as the source of some recommendations, not as implicit import of rules.

We can reasonable assume that passing these types by value is inexpensive as we declared them ourselves as POD with few members in its header.

Since C++11 it can be better to pass even heavy objects by value if the function is going to consume/take ownership using std::move().

However, please feel free to not change it if you prefer this style.

[mreisinger]

test/ScheduleOptimizer/pattern-matching-based-opts_3.ll

66

"1nd" - see Tobias' note from above

70

"1nd" - see Tobias' note from above

[gareevroman]

lib/Transform/ScheduleOptimizer.cpp

595

Thanks for the explanation.

LLVM has its own types that are neither STL or built-ins that are meant to be passes by value: ArrayRef, StringRef, PointerIntPair, CallSite, etc.
"Effective C++" in the LLVM Coding Standards is referenced as the source of some recommendations, not as implicit import of rules.

As far as I understand, according to the description, LLVM Coding Standards should not be regarded as an absolute requirement to be followed in all instances and "Effective C++" is one of the two books, which are proposed as particularly important books for work. I just tried to understand how much they are important for us.

We can reasonable assume that passing these types by value is inexpensive as we declared them ourselves as POD with few members in its header.
Since C++11 it can be better to pass even heavy objects by value if the function is going to consume/take ownership using std::move().

Yes, I agree with it. My understanding is that in this case passing by reference can be a precaution, because implementation of a user-defined type can be changed in future.

However, please feel free to not change it if you prefer this style.

I prefer to follow LLVM Coding Standards. OK, I'll fix it so they are passed by value.

[gareevroman]

@grosser, @Meinersbur, @mreisinger, thank you for the comments! I've tried to address them in r276616 and r276627.

include/polly/ScheduleOptimizer.h

public:
   ///                 to.
   /// @param TTI      Target Transform Info.
   /// @returns        The transformed schedule.
   static __isl_give isl_schedule *
   optimizeSchedule(__isl_take isl_schedule *Schedule,
                    const llvm::TargetTransformInfo *TTI = nullptr);
 
   /// @brief Apply schedule tree transformations.
   ///
   /// This function takes a node in an (possibly already optimized) schedule
   /// tree and applies a set of additional optimizations on this schedule tree
   /// node and its descendents. The transformations applied include:
   ///
   ///   - Tiling
   ///   - Prevectorization
   ///
   /// @param Node The schedule object post-transformations will be applied to.
private:
   ///
   /// @param Node            The node to register tile.
   /// @param TileSizes       A vector of tile sizes that should be used for
   ///                        tiling.
   /// @param DefaultTileSize A default tile size that is used for dimensions
   static __isl_give isl_schedule_node *
   applyRegisterTiling(__isl_take isl_schedule_node *Node,
                       llvm::ArrayRef<int> TileSizes, int DefaultTileSize);
 
   /// @brief Apply the BLIS matmul optimization pattern
   ///
   /// Apply the BLIS matmul optimization pattern
   /// (http://www.cs.utexas.edu/users/flame/pubs/TOMS-BLIS-Analytical.pdf).
   /// BLIS implements gemm as three nested loops around a macro-kernel,
   /// plus two packing routines. The macro-kernel is implemented in terms
   /// of two additional loops around a micro-kernel. The micro-kernel
   /// is a loop around a rank-1 (i.e., outer product) update.
   ///
   /// We create the BLIS micro-kernel by applying a combination of tiling
-  /// and unrolling. In subsequent changes we will add the extraction
-  /// of the BLIS macro-kernel and implement the packing transformation.
+  /// and unrolling. The BLIS macro-kernel is created by applying
+  /// a combination of tiling and interchanging The description of calculated
+  /// values and utilized algorithms can be found in
+  /// (http://www.cs.utexas.edu/users/flame/pubs/TOMS-BLIS-Analytical.pdf).
+  /// However, it should be noticed that in our case matrixes are stored in
+  /// row-major order. Consequently we should use formulas specified for
+  /// the matrix A to calculate values related to the matrix B and vice versa.
+  /// We should also take into account the row-major order, when we perform
+  /// tiling and interchanging of loops to create the BLIS micro-kernel and
+  /// the BLIS macro-kernel.
+  ///
+  /// In subsequent changes we will implement the packing transformation.
   ///
   /// It is assumed that the Node is successfully checked
   /// by ScheduleTreeOptimizer::isMatrMultPattern. Consequently
   /// in case of matmul kernels the application of optimizeMatMulPattern
   /// can lead to close-to-peak performance. Maybe it can be generalized
   /// to effectively optimize the whole class of successfully checked
   /// statements.
   ///
   /// @param Node the node that contains a band to be optimized.
   /// @return Modified isl_schedule_node.
   static __isl_give isl_schedule_node *
   optimizeMatMulPattern(__isl_take isl_schedule_node *Node,
                         const llvm::TargetTransformInfo *TTI);
 
   /// @brief Check if this node is a band node we want to tile.
   ///
   /// We look for innermost band nodes where individual dimensions are marked as
   /// permutable.
   ///
   /// @param Node The node to check.
   static bool isTileableBandNode(__isl_keep isl_schedule_node *Node);
 
   /// @brief Pre-vectorizes one scheduling dimension of a schedule band.
   ///
   /// prevectSchedBand splits out the dimension DimToVectorize, tiles it and
   /// sinks the resulting point loop.
   ///
   /// Example (DimToVectorize=0, VectorWidth=4):
   ///
   /// | Before transformation:
   /// |
   /// | A[i,j] -> [i,j]
   /// |
   /// | for (i = 0; i < 128; i++)
   /// |    for (j = 0; j < 128; j++)
   /// |      A(i,j);
   ///
   /// | After transformation:
   /// |
   /// | for (it = 0; it < 32; it+=1)
   /// |    for (j = 0; j < 128; j++)
   /// |      for (ip = 0; ip <= 3; ip++)
   /// |        A(4 * it + ip,j);
private:
   ///    read memory access and the last one is write memory access.
   /// 5. all subscripts of the last memory access of the statement don't
   ///    contain the variable used in the inner loop.
   /// If this is the case, we could try to use an approach that is similar to
   /// the one used to get close-to-peak performance of matrix multiplications.
   ///
   /// @param Node The node to check.
   static bool isMatrMultPattern(__isl_keep isl_schedule_node *Node);
+
+  /// @brief Create the BLIS micro-kernel
+  ///
+  /// We create the BLIS macro-kernel by applying a combination of tiling
+  /// and interchanging.
+  ///
+  /// @param Node The schedule node to be modified.
+  /// @param Mr The parameter of the BLIS micro-kernel.
+  /// @param Nr The parameter of the BLIS micro-kernel.
+  ///
+  /// @see ScheduleTreeOptimizer::optimizeMatMulPattern
+  static __isl_give isl_schedule_node *
+  createMacroKernel(__isl_take isl_schedule_node *Node, int Mr, int Nr);
 };
 
 #endif

lib/Transform/ScheduleOptimizer.cpp

 
 static cl::opt<int> ThrougputVectorFma(
     "polly-target-througput-vector-fma",
     cl::desc("A throughput of the processor floating-point arithmetic units "
              "expressed in the number of vector fused multiply-add "
              "instructions per clock cycle."),
     cl::Hidden, cl::init(1), cl::ZeroOrMore, cl::cat(PollyCategory));
 
+static cl::list<int> CacheLevelAssociativityDegrees(
+    "polly-target-cache-level-associativity-degrees",
+    cl::desc("An associativity degree of each cache level."), cl::Hidden,
+    cl::ZeroOrMore, cl::CommaSeparated, cl::cat(PollyCategory));
+
+static cl::list<int>
+    CacheLevelSizes("polly-target-level-cache-sizes",
+                    cl::desc("A size of each cache level specified in bytes."),
+                    cl::Hidden, cl::ZeroOrMore, cl::CommaSeparated,
+                    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> FirstLevelTileSizes(
     "polly-tile-sizes", cl::desc("A tile size for each loop dimension, filled "
static __isl_give isl_map *circularShiftOutputDims(__isl_take isl_map *IslMap) {
   if (DimNum == 0)
     return IslMap;
   auto InputDimsId = isl_map_get_tuple_id(IslMap, isl_dim_in);
   IslMap = isl_map_move_dims(IslMap, isl_dim_in, 0, isl_dim_out, DimNum - 1, 1);
   IslMap = isl_map_move_dims(IslMap, isl_dim_out, 0, isl_dim_in, 0, 1);
   return isl_map_set_tuple_id(IslMap, isl_dim_in, InputDimsId);
 }
 
+/// @brief Permute two dimensions of the band node.
+///
+/// Permute FirstDim and SecondDim dimensions of the Node.
+///
+/// @param Node The band node to be modified.
+/// @param FirstDim The first dimension to be permuted.
+/// @param SecondDim The second dimension to be permuted.
+static __isl_give isl_schedule_node *
+permuteBandNodeDimensions(__isl_take isl_schedule_node *Node, unsigned FirstDim,
+                          unsigned SecondDim) {
+  assert(isl_schedule_node_get_type(Node) == isl_schedule_node_band &&
+         isl_schedule_node_band_n_member(Node) > std::max(FirstDim, SecondDim));
+  auto PartialSchedule = isl_schedule_node_band_get_partial_schedule(Node);
+  auto PartialScheduleFirstDim =
+      isl_multi_union_pw_aff_get_union_pw_aff(PartialSchedule, FirstDim);
+  auto PartialScheduleSecondDim =
+      isl_multi_union_pw_aff_get_union_pw_aff(PartialSchedule, SecondDim);
+  PartialSchedule = isl_multi_union_pw_aff_set_union_pw_aff(
+      PartialSchedule, SecondDim, PartialScheduleFirstDim);
+  PartialSchedule = isl_multi_union_pw_aff_set_union_pw_aff(
+      PartialSchedule, FirstDim, PartialScheduleSecondDim);
+  Node = isl_schedule_node_delete(Node);
+  Node = isl_schedule_node_insert_partial_schedule(Node, PartialSchedule);
+  return Node;
+}
+
+__isl_give isl_schedule_node *
+ScheduleTreeOptimizer::createMacroKernel(__isl_take isl_schedule_node *Node,
+                                         int Mr, int Nr) {
+  assert(isl_schedule_node_get_type(Node) == isl_schedule_node_band);
+  // According to www.cs.utexas.edu/users/flame/pubs/TOMS-BLIS-Analytical.pdf,
+  // it requires information about the first two levels of a cache to determine
+  // all the parameters of a macro-kernel. It also checks that an associativity
+  // degree of a cache level is greater that two. Otherwise, another algorithm
+  // for determination of the parameters should be used.
+  if (!(Mr > 0 && Nr > 0 && CacheLevelSizes.size() >= 2 &&
+        CacheLevelAssociativityDegrees.size() >= 2 && CacheLevelSizes[0] > 0 &&
+        CacheLevelSizes[1] > 0 && CacheLevelAssociativityDegrees[0] > 2 &&
+        CacheLevelAssociativityDegrees[1] > 2))
+    return Node;
+  int Cbr = floor((CacheLevelAssociativityDegrees[0] - 1) /
+                  (1 + static_cast<double>(Mr) / Nr));
+  int Kc =
+      (Cbr * CacheLevelSizes[0]) / (Nr * CacheLevelAssociativityDegrees[0] * 8);
+  double Cac =
+      static_cast<double>(Mr * Kc * 8 * CacheLevelAssociativityDegrees[1]) /
+      CacheLevelSizes[1];
+  double Cbc =
+      static_cast<double>(Nr * Kc * 8 * CacheLevelAssociativityDegrees[1]) /
+      CacheLevelSizes[1];
+  int Mc = floor(Mr / Cac);
+  int Nc = floor((Nr * (CacheLevelAssociativityDegrees[1] - 2)) / Cbc);
+  int MacroKernelParams[] = {Mc, Nc, Kc};
+  Node = tileNode(Node, "1nd level tiling", MacroKernelParams, 1);
+  Node = isl_schedule_node_parent(isl_schedule_node_parent(Node));
+  Node = permuteBandNodeDimensions(Node, 1, 2);
+  return isl_schedule_node_child(isl_schedule_node_child(Node, 0), 0);
+}
+
 __isl_give isl_schedule_node *ScheduleTreeOptimizer::optimizeMatMulPattern(
     __isl_take isl_schedule_node *Node, const llvm::TargetTransformInfo *TTI) {
   assert(TTI && "The target transform info should be provided.");
-  // Get a micro-kernel.
   // Nvec - Number of double-precision floating-point numbers that can be hold
   // by a vector register. Use 2 by default.
   auto Nvec = TTI->getRegisterBitWidth(true) / 64;
   if (Nvec == 0)
     Nvec = 2;
   int Nr =
       ceil(sqrt(Nvec * LatencyVectorFma * ThrougputVectorFma) / Nvec) * Nvec;
   int Mr = ceil(Nvec * LatencyVectorFma * ThrougputVectorFma / Nr);
-  std::vector<int> MicroKernelParams{Mr, Nr};
+  Node = createMacroKernel(Node, Mr, Nr);
+  // Get a micro-kernel.
+  int MicroKernelParams[] = {Mr, Nr};
   Node = applyRegisterTiling(Node, MicroKernelParams, 1);
   return Node;
 }
 
 bool ScheduleTreeOptimizer::isMatrMultPattern(
     __isl_keep isl_schedule_node *Node) {
   auto *PartialSchedule =
       isl_schedule_node_band_get_partial_schedule_union_map(Node);
   if (isl_schedule_node_band_n_member(Node) != 3 ||
       isl_union_map_n_map(PartialSchedule) != 1) {
     isl_union_map_free(PartialSchedule);
     return false;
   }
   auto *NewPartialSchedule = isl_map_from_union_map(PartialSchedule);
   NewPartialSchedule = circularShiftOutputDims(NewPartialSchedule);
   if (containsMatrMult(NewPartialSchedule)) {
     isl_map_free(NewPartialSchedule);
     return true;
   }
   isl_map_free(NewPartialSchedule);
   return false;
 }
 
 __isl_give isl_schedule_node *
 ScheduleTreeOptimizer::optimizeBand(__isl_take isl_schedule_node *Node,
                                     void *User) {
   if (!isTileableBandNode(Node))
     return Node;
 
   if (PMBasedOpts && User && isMatrMultPattern(Node)) {
     DEBUG(dbgs() << "The matrix multiplication pattern was detected\n");
     const llvm::TargetTransformInfo *TTI;
     TTI = static_cast<const llvm::TargetTransformInfo *>(User);
     Node = optimizeMatMulPattern(Node, TTI);
   }
 
   return standardBandOpts(Node, User);
 }
 
 __isl_give isl_schedule *
 ScheduleTreeOptimizer::optimizeSchedule(__isl_take isl_schedule *Schedule,
                                         const llvm::TargetTransformInfo *TTI) {
   isl_schedule_node *Root = isl_schedule_get_root(Schedule);
   Root = optimizeScheduleNode(Root, TTI);
   isl_schedule_free(Schedule);
   auto S = isl_schedule_node_get_schedule(Root);
   isl_schedule_node_free(Root);
   return S;
 }
 

test/ScheduleOptimizer/pattern-matching-based-opts_3.ll

 ; RUN: opt %loadPolly -polly-opt-isl -polly-pattern-matching-based-opts=true -polly-target-througput-vector-fma=1 -polly-target-latency-vector-fma=8 -analyze -polly-ast < %s 2>&1 | FileCheck %s
+; RUN: opt %loadPolly -polly-opt-isl -polly-pattern-matching-based-opts=true -polly-target-througput-vector-fma=1 -polly-target-latency-vector-fma=8 -analyze -polly-ast -polly-target-cache-level-associativity-degrees=8,8 -polly-target-level-cache-sizes=32768,262144 < %s 2>&1 | FileCheck %s --check-prefix=EXTRACTION-OF-MACRO-KERNEL
 ;
 ;    /* C := alpha*A*B + beta*C */
 ;    for (i = 0; i < _PB_NI; i++)
 ;      for (j = 0; j < _PB_NJ; j++)
 ;        {
 ;    C[i][j] *= beta;
 ;    for (k = 0; k < _PB_NK; ++k)
 ;      C[i][j] += alpha * A[i][k] * B[k][j];

 ; CHECK:              Stmt_bb24(4 * c0 + 3, 8 * c1 + 4, c2);
 ; CHECK:              Stmt_bb24(4 * c0 + 3, 8 * c1 + 5, c2);
 ; CHECK:              Stmt_bb24(4 * c0 + 3, 8 * c1 + 6, c2);
 ; CHECK:              Stmt_bb24(4 * c0 + 3, 8 * c1 + 7, c2);
 ; CHECK:            }
 ; CHECK:          }
 ; CHECK:    }
 ;
+; EXTRACTION-OF-MACRO-KERNEL:      // 1nd level tiling - Tiles
+; EXTRACTION-OF-MACRO-KERNEL:      for (int c0 = 0; c0 <= 65; c0 += 1)
+; EXTRACTION-OF-MACRO-KERNEL:        for (int c1 = 0; c1 <= 3; c1 += 1)
+; EXTRACTION-OF-MACRO-KERNEL:          for (int c2 = 0; c2 <= 10; c2 += 1) {
+; EXTRACTION-OF-MACRO-KERNEL:            // 1nd level tiling - Points
+; EXTRACTION-OF-MACRO-KERNEL:            // Register tiling - Tiles
+; EXTRACTION-OF-MACRO-KERNEL:            for (int c3 = 0; c3 <= 3; c3 += 1)
+; EXTRACTION-OF-MACRO-KERNEL:              for (int c4 = 0; c4 <= 11; c4 += 1)
+; EXTRACTION-OF-MACRO-KERNEL:                for (int c5 = 0; c5 <= 255; c5 += 1) {
+; EXTRACTION-OF-MACRO-KERNEL:                  // Register tiling - Points
+; EXTRACTION-OF-MACRO-KERNEL:                  // 1st level tiling - Tiles
+; EXTRACTION-OF-MACRO-KERNEL:                  // 1st level tiling - Points
+; EXTRACTION-OF-MACRO-KERNEL:                  {
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3, 96 * c2 + 8 * c4, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3, 96 * c2 + 8 * c4 + 1, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3, 96 * c2 + 8 * c4 + 2, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3, 96 * c2 + 8 * c4 + 3, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3, 96 * c2 + 8 * c4 + 4, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3, 96 * c2 + 8 * c4 + 5, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3, 96 * c2 + 8 * c4 + 6, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3, 96 * c2 + 8 * c4 + 7, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 1, 96 * c2 + 8 * c4, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 1, 96 * c2 + 8 * c4 + 1, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 1, 96 * c2 + 8 * c4 + 2, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 1, 96 * c2 + 8 * c4 + 3, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 1, 96 * c2 + 8 * c4 + 4, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 1, 96 * c2 + 8 * c4 + 5, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 1, 96 * c2 + 8 * c4 + 6, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 1, 96 * c2 + 8 * c4 + 7, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 2, 96 * c2 + 8 * c4, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 2, 96 * c2 + 8 * c4 + 1, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 2, 96 * c2 + 8 * c4 + 2, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 2, 96 * c2 + 8 * c4 + 3, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 2, 96 * c2 + 8 * c4 + 4, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 2, 96 * c2 + 8 * c4 + 5, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 2, 96 * c2 + 8 * c4 + 6, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 2, 96 * c2 + 8 * c4 + 7, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 3, 96 * c2 + 8 * c4, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 3, 96 * c2 + 8 * c4 + 1, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 3, 96 * c2 + 8 * c4 + 2, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 3, 96 * c2 + 8 * c4 + 3, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 3, 96 * c2 + 8 * c4 + 4, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 3, 96 * c2 + 8 * c4 + 5, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 3, 96 * c2 + 8 * c4 + 6, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                    Stmt_bb24(16 * c0 + 4 * c3 + 3, 96 * c2 + 8 * c4 + 7, 256 * c1 + c5);
+; EXTRACTION-OF-MACRO-KERNEL:                  }
+; EXTRACTION-OF-MACRO-KERNEL:                }
+; EXTRACTION-OF-MACRO-KERNEL:          }
+; EXTRACTION-OF-MACRO-KERNEL:    }
+;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-unknown"
 
 define internal void @kernel_gemm(i32 %arg, i32 %arg1, i32 %arg2, double %arg3, double %arg4, [1056 x double]* %arg5, [1024 x double]* %arg6, [1056 x double]* %arg7) #0 {
 bb:
   br label %bb8
 
 bb8:                                              ; preds = %bb39, %bb