[Polly] Map the new load to the base pointer of the invariant load hoisted load

[gareevroman]

Summary

Map the new load to the base pointer of the invariant load hoisted load to be able to find the alias information for it.

[grosser]

Hi Roman,

as already discussed on the phone call, we certainly have a problem with the alias set annotator where no no-alias metadata is emitted for hoisted base pointers. However, it seems we do not yet fully understand the issue and the commit message and the patch itself are hard to verify. The very first step we should take is to write a minimal test case. I suggest the following one:

define void @metadata(float** %A, float** %B) {
entry:
  %ptrA = load float*, float** %A
  %ptrB = load float*, float** %B
  br label %for

for:
  %indvar = phi i64 [0, %entry], [%indvar.next, %for]
  %indvar.next = add i64 %indvar, 1
  store float 42.0, float* %ptrA
  store float 42.0, float* %ptrB
  %icmp = icmp sle i64 %indvar, 1024
  br i1 %icmp, label %for, label %exit

exit:
  ret void
}

define void @nometadata(float** %A, float** %B) {
entry:
  br label %for

for:
  %indvar = phi i64 [0, %entry], [%indvar.next, %for]
  %indvar.next = add i64 %indvar, 1
  %ptrA = load float*, float** %A
  %ptrB = load float*, float** %B
  store float 42.0, float* %ptrA
  store float 42.0, float* %ptrB
  %icmp = icmp sle i64 %indvar, 1024
  br i1 %icmp, label %for, label %exit

exit:
  ret void
}

This test case took only 10 minute to write for me. Generally it makes reviewing a lot easier if you try to get to such a minimal test case. If this does not work and you don't feel you make progress, that's OK. In this case I am happy to help. (For this patch I had the feeling you had doubts regarding how to write such a test case, which is why I went in to help you).

Looking at this test case, I believe the change itself is almost what is needed. However, plainly copying the metadata is wrong. The base pointers used in the scop should refer to "poly.alias.scope.MemRef_ptrA" and "poly.alias.scope.MemRef_ptrB", but currently refer to "poly.alias.scope.MemRef_A" and "poly.alias.scope.MemRef_B". The right approach is probably to look for the basepointer of the invariant load hoisted load and see if for this base pointer alias information is available.

[gareevroman]

Hi Tobias,

This test case took only 10 minute to write for me. Generally it makes reviewing a lot easier if you try to get to such a minimal test case. If this does not work and you don't feel you make progress, that's OK. In this case I am happy to help. (For this patch I had the feeling you had doubts regarding how to write such a test case, which is why I went in to help you).

Thanks! I think that we can also remove the array B.

Looking at this test case, I believe the change itself is almost what is needed. However, plainly copying the metadata is wrong. The base pointers used in the scop should refer to "poly.alias.scope.MemRef_ptrA" and "poly.alias.scope.MemRef_ptrB", but currently refer to "poly.alias.scope.MemRef_A" and "poly.alias.scope.MemRef_B". The right approach is probably to look for the basepointer of the invariant load hoisted load and see if for this base pointer alias information is available.

Right. Should we map the new load to the basepointer of the invariant load hoisted load to be able to do it? (I've tried to implement it in the new version of the patch).

[grosser]

Perfect. This looks a lot better! Thanks for the cleanup!

test/Isl/CodeGen/invariant_load_alias_metadata.ll

8

Can you include the arguments of !alias.scope and !noalias as well as the metadata referenced to the check lines?

This metadata I mean:

!0 = distinct !{!0, !1, !"polly.alias.scope.MemRef_A"}
!1 = distinct !{!1, !"polly.alias.scope.domain"}
!2 = !{!3}
!3 = distinct !{!3, !1, !"polly.alias.scope.MemRef_ptrA"}

[gareevroman]

Since, according to "assert(MA->isArrayKind() && MA->isRead())", MA models an array and it is a read memory access, AccInst, the access instruction of MA, is a base pointer and PreloadVal should be always mapped to it.

[gareevroman]

Add the removed line.

[grosser]

Hi Roman,

this indeed looks a lot better. Can you please include the arguments of !alias.scope and !noalias as well as the metadata referenced in the check lines, and then commit?

Best,
Tobias

include/polly/CodeGen/IRBuilder.h

void addAlternativeAliasBases(
                      llvm::AssertingVH<llvm::Value>> &NewMap) {
     AlternativeAliasBases.insert(NewMap.begin(), NewMap.end());
   }
 
   /// Delete the set of alternative alias bases
   void resetAlternativeAliasBases() { AlternativeAliasBases.clear(); }
 
 private:
+  /// Get the base pointer for the instruction @p I.
+  llvm::Value *getBasePointer(llvm::Instruction *Inst);
+
   /// 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;

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);
 }
 
-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;
-
+llvm::Value *ScopAnnotator::getBasePointer(Instruction *Inst) {
   auto MemInst = MemAccInst::dyn_cast(Inst);
   if (!MemInst)
-    return;
+    return nullptr;
 
   auto *Ptr = MemInst.getPointerOperand();
   if (!Ptr)
-    return;
+    return nullptr;
 
   auto *PtrSCEV = SE->getSCEV(Ptr);
   auto *BaseSCEV = SE->getPointerBase(PtrSCEV);
   auto *SU = dyn_cast<SCEVUnknown>(BaseSCEV);
 
   if (!SU)
+    return nullptr;
+
+  return SU->getValue();
+}
+
+void ScopAnnotator::annotate(Instruction *Inst) {
+  if (!Inst->mayReadOrWriteMemory())
     return;
 
-  auto *BasePtr = SU->getValue();
+  if (!ParallelLoops.empty())
+    Inst->setMetadata("llvm.mem.parallel_loop_access", ParallelLoops.back());
+
+  // TODO: Use the ScopArrayInfo once available here.
+  if (!AliasScopeDomain)
+    return;
+
+  auto *BasePtr = getBasePointer(Inst);
 
   if (!BasePtr)
     return;
 
   auto AliasScope = AliasScopeMap.lookup(BasePtr);
 
   if (!AliasScope) {
+    auto *PointerOperandInst = dyn_cast<Instruction>(BasePtr);
+    if (PointerOperandInst && PointerOperandInst->getMetadata("alias.scope"))
+      BasePtr = getBasePointer(PointerOperandInst);
+    else
       BasePtr = AlternativeAliasBases.lookup(BasePtr);
+
     if (!BasePtr)
       return;
 
     AliasScope = AliasScopeMap.lookup(BasePtr);
     if (!AliasScope)
       return;
   }
 
   assert(OtherAliasScopeListMap.count(BasePtr) &&
          "BasePtr either expected in AliasScopeMap and OtherAlias...Map");
   auto *OtherAliasScopeList = OtherAliasScopeListMap[BasePtr];
 
   Inst->setMetadata("alias.scope", AliasScope);
   Inst->setMetadata("noalias", OtherAliasScopeList);
 }

test/Isl/CodeGen/invariant_load_alias_metadata.ll

+; RUN: opt %loadPolly -polly-codegen -polly-invariant-load-hoisting=true \
+; RUN: -S < %s | FileCheck %s
+;
+; This test case checks whether Polly generates alias metadata in case of
+; the ublas gemm kernel and polly-invariant-load-hoisting.
+;
+; CHECK: load double, double* %p_arrayidx.i.i.i, align 8, !alias.scope
+; CHECK: store double %p_add, double* %p_arrayidx.i.i.i, align 8, !alias.scope
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%"class.boost::numeric::ublas::matrix" = type { i64, i64, %"class.boost::numeric::ublas::unbounded_array" }
+%"class.boost::numeric::ublas::unbounded_array" = type { %"class.std::allocator", i64, double* }
+%"class.std::allocator" = type { i8 }
+
+define void @_Z4gemmRN5boost7numeric5ublas6matrixIdNS1_15basic_row_majorImlEENS1_15unbounded_arrayIdSaIdEEEEES9_S9_dd(%"class.boost::numeric::ublas::matrix"* dereferenceable(40) %C, %"class.boost::numeric::ublas::matrix"* dereferenceable(40) %A, %"class.boost::numeric::ublas::matrix"* dereferenceable(40) %B, double %alpha, double %beta) {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  br label %for.cond3.preheader
+
+for.cond3.preheader:                              ; preds = %for.cond.cleanup5, %entry.split
+  %i.040 = phi i64 [ 0, %entry.split ], [ %inc18, %for.cond.cleanup5 ]
+  br label %for.cond7.preheader
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup5
+  ret void
+
+for.cond7.preheader:                              ; preds = %for.cond.cleanup9, %for.cond3.preheader
+  %j.039 = phi i64 [ 0, %for.cond3.preheader ], [ %inc15, %for.cond.cleanup9 ]
+  br label %for.body10
+
+for.cond.cleanup5:                                ; preds = %for.cond.cleanup9
+  %inc18 = add nuw nsw i64 %i.040, 1
+  %exitcond53 = icmp ne i64 %inc18, 1024
+  br i1 %exitcond53, label %for.cond3.preheader, label %for.cond.cleanup
+
+for.cond.cleanup9:                                ; preds = %for.body10
+  %inc15 = add nuw nsw i64 %j.039, 1
+  %exitcond52 = icmp ne i64 %inc15, 1024
+  br i1 %exitcond52, label %for.cond7.preheader, label %for.cond.cleanup5
+
+for.body10:                                       ; preds = %for.body10, %for.cond7.preheader
+  %k.038 = phi i64 [ 0, %for.cond7.preheader ], [ %inc, %for.body10 ]
+  %size2_.i.i46 = getelementptr inbounds %"class.boost::numeric::ublas::matrix", %"class.boost::numeric::ublas::matrix"* %A, i64 0, i32 1
+  %tmp = load i64, i64* %size2_.i.i46, align 8
+  %mul.i.i.i47 = mul i64 %tmp, %i.040
+  %add.i.i.i48 = add i64 %mul.i.i.i47, %k.038
+  %data_.i4.i.i49 = getelementptr inbounds %"class.boost::numeric::ublas::matrix", %"class.boost::numeric::ublas::matrix"* %A, i64 0, i32 2, i32 2
+  %tmp1 = load double*, double** %data_.i4.i.i49, align 8
+  %arrayidx.i.i.i50 = getelementptr inbounds double, double* %tmp1, i64 %add.i.i.i48
+  %tmp2 = load double, double* %arrayidx.i.i.i50, align 8
+  %size2_.i.i41 = getelementptr inbounds %"class.boost::numeric::ublas::matrix", %"class.boost::numeric::ublas::matrix"* %B, i64 0, i32 1
+  %tmp3 = load i64, i64* %size2_.i.i41, align 8
+  %mul.i.i.i42 = mul i64 %tmp3, %k.038
+  %add.i.i.i43 = add i64 %mul.i.i.i42, %j.039
+  %data_.i4.i.i44 = getelementptr inbounds %"class.boost::numeric::ublas::matrix", %"class.boost::numeric::ublas::matrix"* %B, i64 0, i32 2, i32 2
+  %tmp4 = load double*, double** %data_.i4.i.i44, align 8
+  %arrayidx.i.i.i45 = getelementptr inbounds double, double* %tmp4, i64 %add.i.i.i43
+  %tmp5 = load double, double* %arrayidx.i.i.i45, align 8
+  %mul = fmul double %tmp2, %tmp5
+  %size2_.i.i = getelementptr inbounds %"class.boost::numeric::ublas::matrix", %"class.boost::numeric::ublas::matrix"* %C, i64 0, i32 1
+  %tmp6 = load i64, i64* %size2_.i.i, align 8
+  %mul.i.i.i = mul i64 %tmp6, %i.040
+  %add.i.i.i = add i64 %mul.i.i.i, %j.039
+  %data_.i4.i.i = getelementptr inbounds %"class.boost::numeric::ublas::matrix", %"class.boost::numeric::ublas::matrix"* %C, i64 0, i32 2, i32 2
+  %tmp7 = load double*, double** %data_.i4.i.i, align 8
+  %arrayidx.i.i.i = getelementptr inbounds double, double* %tmp7, i64 %add.i.i.i
+  %tmp8 = load double, double* %arrayidx.i.i.i, align 8
+  %add = fadd double %mul, %tmp8
+  store double %add, double* %arrayidx.i.i.i, align 8
+  %inc = add nuw nsw i64 %k.038, 1
+  %exitcond = icmp ne i64 %inc, 1024
+  br i1 %exitcond, label %for.body10, label %for.cond.cleanup9
+}