[Polly] Introduce another level of metadata to distinguish non-aliasing accesses

[gareevroman]

Summary

Introduce another level of alias metadata to distinguish the individual non-aliasing accesses that have inter iteration alias-free base pointers marked with "Inter iteration alias-free" mark nodes.. It can be used to, for example, distinguish different stores (loads) produced by unrolling of the innermost loops and, subsequently, sink (hoist) them by LICM.

[gareevroman]

P.S: This is a draft of the patch. Currently, it's the responsibility of the user of IRBuilder to make sure that only individual non-aliasing accesses have pointer operands marked with "polly.no.inter.iteration.aliasing" metatdata.

I would be very grateful for your comments, feedback and ideas!

[gareevroman]

Use mark nodes to mark base pointers.

[gareevroman]

Add the test case.

[grosser]

Hi Roman,

this looks good to me.

include/polly/CodeGen/IRBuilder.h

void addAlternativeAliasBases(
       llvm::DenseMap<llvm::AssertingVH<llvm::Value>,
                      llvm::AssertingVH<llvm::Value>> &NewMap) {
     AlternativeAliasBases.insert(NewMap.begin(), NewMap.end());
   }
 
   /// Delete the set of alternative alias bases
   void resetAlternativeAliasBases() { AlternativeAliasBases.clear(); }
 
+  /// Add inter iteration alias-free base pointer @p BasePtr.
+  void addInterIterationAliasFreeBasePtr(llvm::Value *BasePtr);
+
 private:
+  /// Annotate with the second level alias metadata
+  ///
+  /// Annotate the instruction @p I with the second level alias metadata
+  /// to distinguish the individual non-aliasing accesses that have inter
+  /// iteration alias-free base pointers.
+  ///
+  /// @param I The instruction to be annotated.
+  /// @param BasePtr The base pointer of @p I.
+  void annotateSecondLevel(llvm::Instruction *I, llvm::Value *BasePtr);
+
   /// The ScalarEvolution analysis we use to find base pointers.
   llvm::ScalarEvolution *SE;
 
   /// All loops currently under construction.
   llvm::SmallVector<llvm::Loop *, 8> ActiveLoops;
 
   /// Metadata pointing to parallel loops currently under construction.
   llvm::SmallVector<llvm::MDNode *, 8> ParallelLoops;
 
   /// The alias scope domain for the current SCoP.
   llvm::MDNode *AliasScopeDomain;
 
   /// A map from base pointers to its alias scope.
   llvm::DenseMap<llvm::AssertingVH<llvm::Value>, llvm::MDNode *> AliasScopeMap;
 
   /// A map from base pointers to an alias scope list of other pointers.
   llvm::DenseMap<llvm::AssertingVH<llvm::Value>, llvm::MDNode *>
       OtherAliasScopeListMap;
 
+  /// A map from pointers to second level alias scopes.
+  llvm::DenseMap<llvm::AssertingVH<llvm::Value>, llvm::MDNode *>
+      SecondLevelAliasScopeMap;
+
+  /// A map from pointers to second level alias scope list of other pointers.
+  llvm::DenseMap<llvm::AssertingVH<llvm::Value>, llvm::MDNode *>
+      SecondLevelOtherAliasScopeListMap;
+
+  /// Inter iteration alias-free base pointers.
+  llvm::SmallPtrSet<llvm::Value *, 4> InterIterationAliasFreeBasePtrs;
+
   llvm::DenseMap<llvm::AssertingVH<llvm::Value>, llvm::AssertingVH<llvm::Value>>
       AlternativeAliasBases;
 };
 
 /// Add Polly specifics when running IRBuilder.
 ///
 /// This is used to add additional items such as e.g. the llvm.loop.parallel
 /// metadata.

lib/CodeGen/IRBuilder.cpp

if (!IsParallel)
     return;
 
   assert(!ParallelLoops.empty() && "Expected a parallel loop to annotate");
   MDNode *Ids = ParallelLoops.back();
   MDNode *Id = cast<MDNode>(Ids->getOperand(Ids->getNumOperands() - 1));
   B->setMetadata("llvm.loop", Id);
 }
 
+/// Get the pointer operand
+///
+/// @param Inst The instruction to be analyzed.
+/// @return the pointer operand in case @p Inst is a memory access
+///         instruction and nullptr otherwise.
+static llvm::Value *getMemAccInstPointerOperand(Instruction *Inst) {
+  auto MemInst = MemAccInst::dyn_cast(Inst);
+  if (!MemInst)
+    return nullptr;
+
+  return MemInst.getPointerOperand();
+}
+
+void ScopAnnotator::annotateSecondLevel(llvm::Instruction *Inst,
+                                        llvm::Value *BasePtr) {
+  auto *Ptr = getMemAccInstPointerOperand(Inst);
+  if (!Ptr)
+    return;
+  auto SecondLevelAliasScope = SecondLevelAliasScopeMap.lookup(Ptr);
+  auto SecondLevelOtherAliasScopeList =
+      SecondLevelOtherAliasScopeListMap.lookup(Ptr);
+  if (!SecondLevelAliasScope) {
+    auto AliasScope = AliasScopeMap.lookup(BasePtr);
+    if (!AliasScope)
+      return;
+    LLVMContext &Ctx = SE->getContext();
+    SecondLevelAliasScope = getID(
+        Ctx, AliasScope, MDString::get(Ctx, "second level alias metadata"));
+    SecondLevelAliasScopeMap[Ptr] = SecondLevelAliasScope;
+    Metadata *Args = {SecondLevelAliasScope};
+    auto SecondLevelBasePtrAliasScopeList =
+        SecondLevelAliasScopeMap.lookup(BasePtr);
+    SecondLevelAliasScopeMap[BasePtr] = MDNode::concatenate(
+        SecondLevelBasePtrAliasScopeList, MDNode::get(Ctx, Args));
+    auto OtherAliasScopeList = OtherAliasScopeListMap.lookup(BasePtr);
+    SecondLevelOtherAliasScopeList = MDNode::concatenate(
+        OtherAliasScopeList, SecondLevelBasePtrAliasScopeList);
+    SecondLevelOtherAliasScopeListMap[Ptr] = SecondLevelOtherAliasScopeList;
+  }
+  Inst->setMetadata("alias.scope", SecondLevelAliasScope);
+  Inst->setMetadata("noalias", SecondLevelOtherAliasScopeList);
+}
+
 void ScopAnnotator::annotate(Instruction *Inst) {
   if (!Inst->mayReadOrWriteMemory())
     return;
 
   if (!ParallelLoops.empty())
     Inst->setMetadata("llvm.mem.parallel_loop_access", ParallelLoops.back());
 
   // TODO: Use the ScopArrayInfo once available here.
   if (!AliasScopeDomain)
     return;
 
-  auto MemInst = MemAccInst::dyn_cast(Inst);
-  if (!MemInst)
-    return;
-
-  auto *Ptr = MemInst.getPointerOperand();
+  auto *Ptr = getMemAccInstPointerOperand(Inst);
   if (!Ptr)
     return;
 
   auto *PtrSCEV = SE->getSCEV(Ptr);
   auto *BaseSCEV = SE->getPointerBase(PtrSCEV);
   auto *SU = dyn_cast<SCEVUnknown>(BaseSCEV);
 
   if (!SU)
if (!AliasScope) {
     if (!AliasScope)
       return;
   }
 
   assert(OtherAliasScopeListMap.count(BasePtr) &&
          "BasePtr either expected in AliasScopeMap and OtherAlias...Map");
   auto *OtherAliasScopeList = OtherAliasScopeListMap[BasePtr];
 
+  if (InterIterationAliasFreeBasePtrs.count(BasePtr)) {
+    annotateSecondLevel(Inst, BasePtr);
+    return;
+  }
+
   Inst->setMetadata("alias.scope", AliasScope);
   Inst->setMetadata("noalias", OtherAliasScopeList);
 }
+
+void ScopAnnotator::addInterIterationAliasFreeBasePtr(llvm::Value *BasePtr) {
+  if (!BasePtr)
+    return;
+
+  InterIterationAliasFreeBasePtrs.insert(BasePtr);
+}

lib/CodeGen/IslNodeBuilder.cpp

if (!strcmp(isl_id_get_name(Id), "SIMD") &&
     int VectorWidth = getNumberOfIterations(Child);
     if (Vector && 1 < VectorWidth && VectorWidth <= 16)
       createForVector(Child, VectorWidth);
     else
       createForSequential(Child, true);
     isl_id_free(Id);
     return;
   }
+  if (!strcmp(isl_id_get_name(Id), "Inter iteration alias-free")) {
+    auto *BasePtr = static_cast<Value *>(isl_id_get_user(Id));
+    Annotator.addInterIterationAliasFreeBasePtr(BasePtr);
+  }
   create(Child);
   isl_id_free(Id);
 }
 
 void IslNodeBuilder::createForVector(__isl_take isl_ast_node *For,
                                      int VectorWidth) {
   isl_ast_node *Body = isl_ast_node_for_get_body(For);
   isl_ast_expr *Init = isl_ast_node_for_get_init(For);

lib/Transform/ScheduleOptimizer.cpp

isolateAndUnrollMatMulInnerLoops(__isl_take isl_schedule_node *Node,
   Node = isl_schedule_node_parent(isl_schedule_node_parent(Node));
   IsolateOption = getIsolateOptions(Prefix, 3);
   Options = isl_union_set_union(IsolateOption, AtomicOption);
   Node = isl_schedule_node_band_set_ast_build_options(Node, Options);
   Node = isl_schedule_node_child(isl_schedule_node_child(Node, 0), 0);
   return Node;
 }
 
+/// Mark @p BasePtr with "Inter iteration alias-free" mark node.
+///
+/// @param Node The child of the mark node to be inserted.
+/// @param BasePtr The pointer to be marked.
+/// @return The modified isl_schedule_node.
+static isl_schedule_node *markInterIterationAliasFree(isl_schedule_node *Node,
+                                                      llvm::Value *BasePtr) {
+  if (!BasePtr)
+    return Node;
+
+  auto *Ctx = isl_schedule_node_get_ctx(Node);
+  auto *Id = isl_id_alloc(Ctx, "Inter iteration alias-free", BasePtr);
+  return isl_schedule_node_child(isl_schedule_node_insert_mark(Node, Id), 0);
+}
+
 __isl_give isl_schedule_node *ScheduleTreeOptimizer::optimizeMatMulPattern(
     __isl_take isl_schedule_node *Node, const llvm::TargetTransformInfo *TTI,
     MatMulInfoTy &MMI) {
   assert(TTI && "The target transform info should be provided.");
+  Node = markInterIterationAliasFree(Node, MMI.WriteToC->getLatestBaseAddr());
   int DimOutNum = isl_schedule_node_band_n_member(Node);
   assert(DimOutNum > 2 && "In case of the matrix multiplication the loop nest "
                           "and, consequently, the corresponding scheduling "
                           "functions have at least three dimensions.");
   Node = permuteBandNodeDimensions(Node, MMI.i, DimOutNum - 3);
   int NewJ = MMI.j == DimOutNum - 3 ? MMI.i : MMI.j;
   int NewK = MMI.k == DimOutNum - 3 ? MMI.i : MMI.k;
   Node = permuteBandNodeDimensions(Node, NewJ, DimOutNum - 2);

test/ScheduleOptimizer/mat_mul_pattern_data_layout_2.ll

 ; CHECK-NEXT:      // 1st level tiling - Tiles
 ; CHECK-NEXT:      for (int c0 = 0; c0 <= 32; c0 += 1)
 ; CHECK-NEXT:        for (int c1 = 0; c1 <= 32; c1 += 1) {
 ; CHECK-NEXT:          // 1st level tiling - Points
 ; CHECK-NEXT:          for (int c2 = 0; c2 <= 31; c2 += 1)
 ; CHECK-NEXT:            for (int c3 = 0; c3 <= 31; c3 += 1)
 ; CHECK-NEXT:              Stmt_bb9(32 * c0 + c2, 32 * c1 + c3);
 ; CHECK-NEXT:        }
+; CHECK-NEXT:      // Inter iteration alias-free
 ; CHECK-NEXT:      // 1st level tiling - Tiles
 ; CHECK-NEXT:      for (int c1 = 0; c1 <= 3; c1 += 1) {
 ; CHECK-NEXT:        for (int c3 = 0; c3 <= 1055; c3 += 1)
 ; CHECK-NEXT:          for (int c4 = 256 * c1; c4 <= min(1022, 256 * c1 + 255); c4 += 1)
 ; CHECK-NEXT:            CopyStmt_0(0, c3, c4);
 ; CHECK-NEXT:        for (int c2 = 0; c2 <= 10; c2 += 1) {
 ; CHECK-NEXT:          for (int c3 = 96 * c2; c3 <= 96 * c2 + 95; c3 += 1)
 ; CHECK-NEXT:            for (int c5 = 256 * c1; c5 <= min(1022, 256 * c1 + 255); c5 += 1)

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

 ; CHECK-NEXT:      // 1st level tiling - Tiles
 ; CHECK-NEXT:      for (int c0 = 0; c0 <= 32; c0 += 1)
 ; CHECK-NEXT:        for (int c1 = 0; c1 <= 32; c1 += 1) {
 ; CHECK-NEXT:          // 1st level tiling - Points
 ; CHECK-NEXT:          for (int c2 = 0; c2 <= 31; c2 += 1)
 ; CHECK-NEXT:            for (int c3 = 0; c3 <= 31; c3 += 1)
 ; CHECK-NEXT:              Stmt_bb9(32 * c0 + c2, 32 * c1 + c3);
 ; CHECK-NEXT:        }
+; CHECK-NEXT:      // Inter iteration alias-free
 ; CHECK-NEXT:      // Register tiling - Tiles
 ; CHECK-NEXT:      for (int c0 = 0; c0 <= 131; c0 += 1)
 ; CHECK-NEXT:        for (int c1 = 0; c1 <= 263; c1 += 1)
 ; CHECK-NEXT:          for (int c2 = 0; c2 <= 1023; c2 += 1) {
 ; CHECK-NEXT:            // Register tiling - Points
 ; CHECK-NEXT:            {
 ; CHECK-NEXT:              Stmt_Copy_0(4 * c1, 8 * c0, c2);
 ; CHECK-NEXT:              Stmt_Copy_0(4 * c1, 8 * c0 + 1, c2);

 ; EXTRACTION-OF-MACRO-KERNEL-NEXT:      // 1st level tiling - Tiles
 ; EXTRACTION-OF-MACRO-KERNEL-NEXT:      for (int c0 = 0; c0 <= 32; c0 += 1)
 ; EXTRACTION-OF-MACRO-KERNEL-NEXT:        for (int c1 = 0; c1 <= 32; c1 += 1) {
 ; EXTRACTION-OF-MACRO-KERNEL-NEXT:          // 1st level tiling - Points
 ; EXTRACTION-OF-MACRO-KERNEL-NEXT:          for (int c2 = 0; c2 <= 31; c2 += 1)
 ; EXTRACTION-OF-MACRO-KERNEL-NEXT:            for (int c3 = 0; c3 <= 31; c3 += 1)
 ; EXTRACTION-OF-MACRO-KERNEL-NEXT:              Stmt_bb9(32 * c0 + c2, 32 * c1 + c3);
 ; EXTRACTION-OF-MACRO-KERNEL-NEXT:        }
+; EXTRACTION-OF-MACRO-KERNEL-NEXT:      // Inter iteration alias-free
 ; EXTRACTION-OF-MACRO-KERNEL-NEXT:      // 1st level tiling - Tiles
 ; EXTRACTION-OF-MACRO-KERNEL-NEXT:      for (int c1 = 0; c1 <= 3; c1 += 1) {
 ; EXTRACTION-OF-MACRO-KERNEL-NEXT:        for (int c3 = 0; c3 <= 1055; c3 += 1)
 ; EXTRACTION-OF-MACRO-KERNEL-NEXT:          for (int c4 = 256 * c1; c4 <= 256 * c1 + 255; c4 += 1)
 ; EXTRACTION-OF-MACRO-KERNEL-NEXT:            CopyStmt_0(0, c3, c4);
 ; EXTRACTION-OF-MACRO-KERNEL-NEXT:        for (int c2 = 0; c2 <= 10; c2 += 1) {
 ; EXTRACTION-OF-MACRO-KERNEL-NEXT:          for (int c3 = 96 * c2; c3 <= 96 * c2 + 95; c3 += 1)
 ; EXTRACTION-OF-MACRO-KERNEL-NEXT:            for (int c5 = 256 * c1; c5 <= 256 * c1 + 255; c5 += 1)

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

 ;
 ;    /* C := A * B + C */
 ;    for (i = 0; i < _PB_NI; i++)
 ;      for (j = 0; j < _PB_NJ; j++)
 ;  for (k = 0; k < _PB_NK; ++k)
 ;    C[i][j] += A[i][k] * B[k][j];
 ;
 ; CHECK:    if (ni >= 1) {
+; CHECK-NEXT:      // Inter iteration alias-free
 ; CHECK-NEXT:      // 1st level tiling - Tiles
 ; CHECK-NEXT:      for (int c0 = 0; c0 <= floord(nj - 1, 2048); c0 += 1)
 ; CHECK-NEXT:        for (int c1 = 0; c1 <= floord(nk - 1, 256); c1 += 1) {
 ; CHECK-NEXT:          for (int c3 = 2048 * c0; c3 <= min(nj - 1, 2048 * c0 + 2047); c3 += 1)
 ; CHECK-NEXT:            for (int c4 = 256 * c1; c4 <= min(nk - 1, 256 * c1 + 255); c4 += 1)
 ; CHECK-NEXT:              CopyStmt_0(0, c3, c4);
 ; CHECK-NEXT:          for (int c2 = 0; c2 <= floord(ni - 1, 96); c2 += 1) {
 ; CHECK-NEXT:            if (c0 == 0)