[polly codegen] Handle multi-dimensional invariant load.

[efriedma]

Summary

If the address of a load depends on another load, make sure to emit the loads them in the right order.

[jdoerfert]

Assuming all checks prior to code generation can handle this case properly this is the "right way" to fix this. One modification and it should be good to go.

lib/CodeGen/IslNodeBuilder.cpp

1115

I do not get the comment.

1116

To get all SCEVUnknowns that might be loads which are somewhere referenced in the dimension size we need to do it somewhat like:

SetVector<Value *> Values;
findValues(ParamSCEV, SE, Values);                                                                  
for (auto *Val : Values) {
  if (auto *BaseIAClass = S.lookupInvariantEquivClass(Val) {
    ...

1128

I do not see the need here but OK.

[jdoerfert]

I realized that we should check hoisting is actually performed.

test/Isl/CodeGen/invariant-load-dimension.ll

4

Maybe add another check line that verifies we actually hoist the multidimensional loads.

Invariant Accesses: {
        ReadAccess :=	[Reduction Type: NONE] [Scalar: 0]
            [l2, l1] -> { Stmt_for_body_i[i0] -> MemRef_cpi[0, 0] };
        Execution Context: [l2, l1] -> {  :  }
        ReadAccess :=	[Reduction Type: NONE] [Scalar: 0]
            [l2, l1] -> { Stmt_for_body_lr_ph_i[] -> MemRef_cpi[0, 1] };
        Execution Context: [l2, l1] -> {  : l2 > 0 }
}

[efriedma]

Updated to correctly iterate over all the inputs to the SCEV value.

[efriedma]

https://reviews.llvm.org/rL284426 . (I accidentally committed without linking to the review, and for some reason, phabricator doesn't want to let me close this.)

lib/CodeGen/IslNodeBuilder.cpp

if (!preloadInvariantEquivClass(*BaseIAClass))
       return false;
 
     // After we preloaded the BaseIAClass we adjusted the BaseExecutionCtx and
     // we need to refine the ExecutionCtx.
     isl_set *BaseExecutionCtx = isl_set_copy(BaseIAClass->ExecutionContext);
     ExecutionCtx = isl_set_intersect(ExecutionCtx, BaseExecutionCtx);
   }
 
+  // If the size of a dimension is dependent on another class, make sure it is
+  // preloaded.
+  for (unsigned i = 1, e = SAI->getNumberOfDimensions(); i < e; ++i) {
+    const SCEV *Dim = SAI->getDimensionSize(i);
+    SetVector<Value *> Values;
+    findValues(Dim, SE, Values);
+    for (auto *Val : Values) {
+      if (auto *BaseIAClass = S.lookupInvariantEquivClass(Val)) {
+        if (!preloadInvariantEquivClass(*BaseIAClass))
+          return false;
+
+        // After we preloaded the BaseIAClass we adjusted the BaseExecutionCtx
+        // and we need to refine the ExecutionCtx.
+        isl_set *BaseExecutionCtx = isl_set_copy(BaseIAClass->ExecutionContext);
+        ExecutionCtx = isl_set_intersect(ExecutionCtx, BaseExecutionCtx);
+      }
+    }
+  }
+
   Instruction *AccInst = MA->getAccessInstruction();
   Type *AccInstTy = AccInst->getType();
 
   Value *PreloadVal = preloadInvariantLoad(*MA, isl_set_copy(ExecutionCtx));
   if (!PreloadVal)
     return false;
 
   for (const MemoryAccess *MA : MAs) {

test/Isl/CodeGen/invariant-load-dimension.ll

+; RUN: opt < %s -analyze -polly-scops -polly-process-unprofitable -polly-invariant-load-hoisting | FileCheck %s -check-prefix=SCOPS
+; RUN: opt -S < %s -polly-codegen -polly-process-unprofitable -polly-invariant-load-hoisting | FileCheck %s -check-prefix=CODEGEN
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n8:16:32-S64"
+
+%S = type { i32, i32, [12 x %L] }
+%L = type { i32, i32, double, i32, i32, i32, i32, i32 }
+
+define void @test(%S* %cpi, i1 %b) {
+; SCOPS-LABEL: Region: %if.then14---%exit
+; SCOPS:         Invariant Accesses: {
+; SCOPS-NEXT:            ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; SCOPS-NEXT:                [l2, l1] -> { Stmt_for_body_i[i0] -> MemRef_cpi[0, 0] };
+; SCOPS-NEXT:            Execution Context: [l2, l1] -> {  :  }
+; SCOPS-NEXT:            ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; SCOPS-NEXT:                [l2, l1] -> { Stmt_for_body_lr_ph_i[] -> MemRef_cpi[0, 1] };
+; SCOPS-NEXT:            Execution Context: [l2, l1] -> {  : l2 > 0 }
+; SCOPS-NEXT:    }
+; SCOPS:         Arrays {
+; SCOPS-NEXT:        i32 MemRef_cpi[*][%l1]; // Element size 4
+; SCOPS-NEXT:    }
+
+; FIXME: Figure out how to actually generate code for this loop.
+; CODEGEN-LABEL: @test(
+; CODEGEN:    polly.preload.begin:
+; CODEGEN-NEXT:  br i1 false
+
+entry:
+  %nt = getelementptr inbounds %S, %S* %cpi, i32 0, i32 1
+  br i1 %b, label %if.then14, label %exit
+
+if.then14:
+  %ns = getelementptr inbounds %S, %S* %cpi, i32 0, i32 0
+  %l0 = load i32, i32* %ns, align 8
+  %cmp12.i = icmp sgt i32 %l0, 0
+  br i1 %cmp12.i, label %for.body.lr.ph.i, label %exit
+
+for.body.lr.ph.i:
+  %l1 = load i32, i32* %nt, align 4
+  br label %for.body.i
+
+for.body.i:
+  %phi = phi i32 [ 0, %for.body.lr.ph.i ], [ %inc, %for.body.i ]
+  %mul.i163 = mul nsw i32 %phi, %l1
+  %cv = getelementptr inbounds %S, %S* %cpi, i32 0, i32 2, i32 %mul.i163, i32 0
+  store i32 0, i32* %cv, align 8
+  %inc = add nuw nsw i32 %phi, 1
+  %l2 = load i32, i32* %ns, align 8
+  %cmp.i164 = icmp slt i32 %inc, %l2
+  br i1 %cmp.i164, label %for.body.i, label %exit
+
+exit:
+  ret void
+}