[Polly] Introduce metadata for splitting of scop statement.

[nandini12396]

Summary

This patch allows annotating of metadata in ir instruction (with "polly_split_after"), which specifies where to split a particular scop statement.

[nandini12396]

@Meinersbur : Ping.

[grosser]

Did you make any progress in debugging this issue? What did you try? What do you believe is the issue?

I suggest to keep investigating in case other's don't yet have time to look into your issue.

[nandini12396]

ok. The issue seems to be that the IR it is reading is wrong. It expects some other arguments probably. I will look into it.

[Meinersbur]

test/ScopInfo/statement.ll

38

This works:

store i32 %i.0, i32* %arrayidx, align 4, !polly_split_after !0

(metadata attached to an instruction needs a name)

[nandini12396]

oh yes. thank you!

[nandini12396]

[todo] add codegen testcase.

[Meinersbur]

Can you also test (and fix) the MemoryAccesses? They are currently:

Statements {
     Stmt_Stmt
         Domain :=
             { Stmt_Stmt[i0] : 0 <= i0 <= 1023 };
         Schedule :=
             { Stmt_Stmt[i0] -> [i0, 0] };
         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
             { Stmt_Stmt[i0] -> MemRef_A[i0] };
         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
             { Stmt_Stmt[i0] -> MemRef_B[i0] };
         Instructions {
               store i32 %i.0, i32* %arrayidx, align 4, !polly_split_after !0
         }
     Stmt_Stmt
         Domain :=
             { Stmt_Stmt[i0] : 0 <= i0 <= 1023 };
         Schedule :=
             { Stmt_Stmt[i0] -> [i0, 1] };
         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
             { Stmt_Stmt[i0] -> MemRef_A[i0] };
         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
             { Stmt_Stmt[i0] -> MemRef_B[i0] };
         Instructions {
               store i32 %i.0, i32* %arrayidx2, align 4
         }

While it should be:

Statements {
     Stmt_Stmt
         Domain :=
             { Stmt_Stmt[i0] : 0 <= i0 <= 1023 };
         Schedule :=
             { Stmt_Stmt[i0] -> [i0, 0] };
         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
             { Stmt_Stmt[i0] -> MemRef_A[i0] };
         Instructions {
               store i32 %i.0, i32* %arrayidx, align 4, !polly_split_after !0
         }
     Stmt_Stmt
         Domain :=
             { Stmt_Stmt[i0] : 0 <= i0 <= 1023 };
         Schedule :=
             { Stmt_Stmt[i0] -> [i0, 1] };
         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
             { Stmt_Stmt[i0] -> MemRef_B[i0] };
         Instructions {
               store i32 %i.0, i32* %arrayidx2, align 4
         }

[Meinersbur]

Can you also ensure that the two statements get different names? Both are called "Stmt_Stmt" at the moment.

[nandini12396]

• gives correct memory access for statement.ll but various tests fail. Trying to fix them.

[nandini12396]

use correct check.

[Meinersbur]

I get 92 regression test failures.

test/ScopInfo/statement.ll

38

stmt_split_no_dependence.ll is identical to this one? You could leave this test-case as-is and instead add the CHECKs to the other one.

[nandini12396]

@Meinersbur : Please suggest what I can to do to fix these failures?

[Meinersbur]

Which one do you have problems with? What's your analysis why it doesn't work? What did you already try to fix it?

[nandini12396]

From just comparing the output, it seems that there are some memory accesses which are not getting identified by this change. This one I am very suprised about and have no clue.
Regarding the Assertion `SAI && "No ScopArrayInfo available for this base pointer"' fail, I am trying to add assert statements to check if the statements match.

[nandini12396]

Hi Sir,

I understand the problem why some memory accesses are not getting outputted. The reason is that its a memory access corresponding to an instruction which is not in the explicit instruction list of the statement. So since there is no statement corresponding to it, it is getting skipped. What we need is that all memory accesses upto a certain instruction get added to the statement split until that point. For this, should we have another instruction list? Do we also need a parameter for number of statements per BB?

[nandini12396]

[todo] fix naming

[nandini12396]

• add automatically working test cases.

[nandini12396]

missed out 2 in prev diff.

[Meinersbur]

include/polly/ScopInfo.h

1312–1313 ↗

(On Diff #112155)

[Style] With a public accessor, this field can be made private.

1602 ↗

(On Diff #112155)

It's not an "ID" (which stands for identifier) when there are multiple statements with that id.

1735 ↗

(On Diff #112155)

What is this map needed for? There is only code that adds elements, but none that queries it.

2195 ↗

(On Diff #112155)

[Style] LLVM's coding style policy says parameters/variable should start with upper case letters.

lib/Analysis/ScopBuilder.cpp

623

[Style] LLVM's coding style policy says parameters/variables should start with upper case letters.

Is there a reason to make it unsigned? IMHO using signed by default is a good idea (Motivation)

656

Could this variable have a more descriptive name than flag?

What do you need it for? Wouldn't it suffice to just increase the StmtID after the current instruction has been processed?

664

Would it be possible to use getStmtListFor(BB)[count] to get the statement this instruction is supposed to be in? This would not require introducing any new ID.

test/ScopInfo/statement.ll

12

Both statements are still named "Stmt_Stmt"?

[nandini12396]

lib/Analysis/ScopBuilder.cpp

623

sure, the example in the talk is really nice. thank you for sharing!

[nandini12396]

Addressed @Meinersbur's comments.

[nandini12396]

forgot to capitalise

[nandini12396]

addressed comments.

[Meinersbur]

LGTM. There is just the unnecessary field Count. Can you remove it (And also run polly-update-format)? Many Thanks.

include/polly/ScopInfo.h

1313 ↗

(On Diff #112697)

[Nit] This member is unused.

[nandini12396]

sorry, removed unused variable.

include/polly/ScopBuilder.h

class ScopBuilder {
   /// Create ScopStmt for all BBs and non-affine subregions of @p SR.
   ///
   /// @param SR A subregion of @p R.
   ///
   /// Some of the statements might be optimized away later when they do not
   /// access any memory and thus have no effect.
   void buildStmts(Region &SR);
 
-  /// Build the access functions for the basic block @p BB in or represented by
-  /// @p Stmt.
+  /// Build the access functions for the statement @p Stmt in or represented by
+  /// @p BB.
   ///
   /// @param Stmt               Statement to add MemoryAccesses to.
   /// @param BB                 A basic block in @p R.
   /// @param NonAffineSubRegion The non affine sub-region @p BB is in.
   /// @param IsExitBlock        Flag to indicate that @p BB is in the exit BB.
   void buildAccessFunctions(ScopStmt *Stmt, BasicBlock &BB,
                             Region *NonAffineSubRegion = nullptr,
                             bool IsExitBlock = false);

lib/Analysis/ScopBuilder.cpp

if (scop->isNonAffineSubRegion(&SR)) {
     scop->addScopStmt(&SR, SurroundingLoop);
     return;
   }
 
   for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
     if (I->isSubRegion())
       buildStmts(*I->getNodeAs<Region>());
     else {
       std::vector<Instruction *> Instructions;
       for (Instruction &Inst : *I->getNodeAs<BasicBlock>()) {
         Loop *L = LI.getLoopFor(Inst.getParent());
         if (!isa<TerminatorInst>(&Inst) && !isIgnoredIntrinsic(&Inst) &&
             !canSynthesize(&Inst, *scop, &SE, L))
           Instructions.push_back(&Inst);
+        if (Inst.getMetadata("polly_split_after")) {
+          Loop *SurroundingLoop = LI.getLoopFor(I->getNodeAs<BasicBlock>());
+          scop->addScopStmt(I->getNodeAs<BasicBlock>(), SurroundingLoop,
+                            Instructions);
+          Instructions.clear();
+        }
       }
       Loop *SurroundingLoop = LI.getLoopFor(I->getNodeAs<BasicBlock>());
       scop->addScopStmt(I->getNodeAs<BasicBlock>(), SurroundingLoop,
                         Instructions);
     }
 }
 
 void ScopBuilder::buildAccessFunctions(ScopStmt *Stmt, BasicBlock &BB,
                                        Region *NonAffineSubRegion,
                                        bool IsExitBlock) {
   assert(
       !Stmt == IsExitBlock &&
       "The exit BB is the only one that cannot be represented by a statement");
   assert(IsExitBlock || Stmt->represents(&BB));
 
   // We do not build access functions for error blocks, as they may contain
   // instructions we can not model.
   if (isErrorBlock(BB, scop->getRegion(), LI, DT) && !IsExitBlock)
     return;
 
   for (Instruction &Inst : BB) {
+    if (scop->getStmtFor(&Inst) != Stmt)
+      continue;
+
     PHINode *PHI = dyn_cast<PHINode>(&Inst);
     if (PHI)
       buildPHIAccesses(Stmt, PHI, NonAffineSubRegion, IsExitBlock);
 
     // For the exit block we stop modeling after the last PHI node.
     if (!PHI && IsExitBlock)
       break;
 
     if (auto MemInst = MemAccInst::dyn_cast(Inst)) {
       assert(Stmt && "Cannot build access function in non-existing statement");
       buildMemoryAccess(MemInst, Stmt);
     }
 
     if (isIgnoredIntrinsic(&Inst))

lib/Analysis/ScopInfo.cpp

for (MemoryAccess *Access : MemAccs) {
     auto *SAI = S.getOrCreateScopArrayInfo(Access->getOriginalBaseAddr(),
                                            ElementType, Access->Sizes, Ty);
     Access->buildAccessRelation(SAI);
     S.addAccessData(Access);
   }
 }
 
 void ScopStmt::addAccess(MemoryAccess *Access, bool Prepend) {
+  if (this != Access->Statement)
+    return;  
+
   Instruction *AccessInst = Access->getAccessInstruction();
 
   if (Access->isArrayKind()) {
     MemoryAccessList &MAL = InstructionToAccess[AccessInst];
     MAL.emplace_front(Access);
   } else if (Access->isValueKind() && Access->isWrite()) {
     Instruction *AccessVal = cast<Instruction>(Access->getAccessValue());
     assert(!ValueWrites.lookup(AccessVal));
while (LoopData.L &&
     LoopData = NextLoopData;
   }
 }
 
 ArrayRef<ScopStmt *> Scop::getStmtListFor(BasicBlock *BB) const {
   auto StmtMapIt = StmtMap.find(BB);
   if (StmtMapIt == StmtMap.end())
     return {};
-  assert(StmtMapIt->second.size() == 1 &&
-         "Each statement corresponds to exactly one BB.");
   return StmtMapIt->second;
 }
 
 ScopStmt *Scop::getLastStmtFor(BasicBlock *BB) const {
   ArrayRef<ScopStmt *> StmtList = getStmtListFor(BB);
   if (StmtList.size() > 0)
     return StmtList.back();
   return nullptr;

test/Isl/CodeGen/stmt_split_no_dependence.ll

+; RUN: opt %loadPolly -polly-codegen -polly-print-instructions < %s
+
+;      void func(int *A, int *B){
+;        for (int i = 0; i < 1024; i+=1) {
+;      Stmt:
+;          A[i] = i;
+;          B[i] = i;
+;        }
+;      }
+;
+; Function Attrs: noinline nounwind uwtable
+define void @func(i32* %A, i32* %B) #0 {
+entry:
+  br label %for.cond
+
+for.cond:            ; preds = %for.inc, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %add, %for.inc ]
+  %cmp = icmp slt i32 %i.0, 1024
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:            ; preds = %for.cond
+  br label %Stmt
+
+Stmt:              ; preds = %for.body
+  %idxprom = sext i32 %i.0 to i64
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom
+  store i32 %i.0, i32* %arrayidx, align 4, !polly_split_after !0
+  %idxprom1 = sext i32 %i.0 to i64
+  %arrayidx2 = getelementptr inbounds i32, i32* %B, i64 %idxprom1
+  store i32 %i.0, i32* %arrayidx2, align 4
+  br label %for.inc
+
+for.inc:           ; preds = %Stmt
+  %add = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:           ; preds = %for.cond
+  ret void
+}
+
+!0 = !{!"polly_split_after"} 

test/ScopInfo/statement.ll

 ; RUN: opt %loadPolly -polly-scops -analyze -polly-print-instructions < %s | FileCheck %s
 
 ;      void func(int *A, int *B){
 ;        for (int i = 0; i < 1024; i+=1) {
 ;      Stmt:
 ;          A[i] = i;
 ;          B[i] = i;
 ;        }
 ;      }
-
-; CHECK:       Instructions {
-; CHECK-NEXT:      store i32 %i.0, i32* %arrayidx, align 4
-; CHECK-NEXT:      store i32 %i.0, i32* %arrayidx2, align 4
-; CHECK-NEXT:    }
+;
+; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT       { Stmt_Stmt[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:       Instructions {
+; CHECK-NEXT:             store i32 %i.0, i32* %arrayidx, align 4, !polly_split_after !0
+; CHECK-NEXT:       }
+; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:      { Stmt_Stmt[i0] -> MemRef_B[i0] };
+; CHECK-NEXT:       Instructions {
+; CHECK-NEXT:             store i32 %i.0, i32* %arrayidx2, align 4
+; CHECK-NEXT:       }
 
 ; Function Attrs: noinline nounwind uwtable
 define void @func(i32* %A, i32* %B) #0 {
 entry:
   br label %for.cond
 
 for.cond:                                         ; preds = %for.inc, %entry
   %i.0 = phi i32 [ 0, %entry ], [ %add, %for.inc ]
   %cmp = icmp slt i32 %i.0, 1024
   br i1 %cmp, label %for.body, label %for.end
 
 for.body:                                         ; preds = %for.cond
   br label %Stmt
 
 Stmt:                                             ; preds = %for.body
   %idxprom = sext i32 %i.0 to i64
   %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom
-  store i32 %i.0, i32* %arrayidx, align 4
+  store i32 %i.0, i32* %arrayidx, align 4, !polly_split_after !0
   %idxprom1 = sext i32 %i.0 to i64
   %arrayidx2 = getelementptr inbounds i32, i32* %B, i64 %idxprom1
   store i32 %i.0, i32* %arrayidx2, align 4
   br label %for.inc
 
 for.inc:                                          ; preds = %Stmt
   %add = add nsw i32 %i.0, 1
   br label %for.cond
 
 for.end:                                          ; preds = %for.cond
   ret void
 }
+
+!0 = !{!"polly_split_after"}