[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

lib/CodeGen/IslNodeBuilder.cpp

if (ParamId)
       IDToValue[ParamId] = PreloadVal;
     isl_id_free(ParamId);
   }
 
   BasicBlock *EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock();
   auto *Alloca = new AllocaInst(AccInstTy, AccInst->getName() + ".preload.s2a");
   Alloca->insertBefore(&*EntryBB->getFirstInsertionPt());
   Builder.CreateStore(PreloadVal, Alloca);
+  ValueMapT PreloadedPointer;
+  PreloadedPointer[PreloadVal] = AccInst;
+  Annotator.addAlternativeAliasBases(PreloadedPointer);
 
   for (auto *DerivedSAI : SAI->getDerivedSAIs()) {
     Value *BasePtr = DerivedSAI->getBasePtr();
 
     for (const MemoryAccess *MA : MAs) {
       // As the derived SAI information is quite coarse, any load from the
       // current SAI could be the base pointer of the derived SAI, however we
       // should only change the base pointer of the derived SAI if we actually
       // preloaded it.
       if (BasePtr == MA->getBaseAddr()) {
         assert(BasePtr->getType() == PreloadVal->getType());
         DerivedSAI->setBasePtr(PreloadVal);
       }
 
       // For scalar derived SAIs we remap the alloca used for the derived value.
       if (BasePtr == MA->getAccessInstruction())
         ScalarMap[DerivedSAI] = Alloca;
     }
   }
 
   for (const MemoryAccess *MA : MAs) {
-
     Instruction *MAAccInst = MA->getAccessInstruction();
     // Use the escape system to get the correct value to users outside the SCoP.
     BlockGenerator::EscapeUserVectorTy EscapeUsers;
     for (auto *U : MAAccInst->users())
       if (Instruction *UI = dyn_cast<Instruction>(U))
         if (!S.contains(UI))
           EscapeUsers.push_back(UI);
 

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:  store float 4.200000e+01, float* %polly.access.A.load, !alias.scope
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @nometadata(float** %A) {
+  entry:
+    br label %for
+
+  for:
+    %indvar = phi i64 [0, %entry], [%indvar.next, %for]
+    %indvar.next = add i64 %indvar, 1
+    %ptrA = load float*, float** %A
+    store float 42.0, float* %ptrA
+    %icmp = icmp sle i64 %indvar, 1024
+    br i1 %icmp, label %for, label %exit
+
+  exit:
+    ret void
+}