[Polly] Split statements on encountering store instructions.

[nandini12396]

Summary

Introduce -polly-stmt-granularity=store option.

[nandini12396]

@Meinersbur : Should I change the checks in all the failing tests? But I think they may change again after the way of split is modified.

[grosser]

Hi Nandini,

no need to change tests. I would just run this once over polybench to see if anything fails.

Now, the actual heuristic we want to implement should likely be something ala:

I would rather aim for making a scop statement a specific subset of the
instructions in the basic block. As a first step, we could then aim for the
minimal DAGs that do not yet require the introduction of new scalar
dependences. E.g. a DAG like this:

 Load    Load
    \  /  |
     op   op
       \ /
      Store

Using these DAGs we keep the changes small, we enable more fine-grained
transformations and we do avoid any risks due to scalar expension.

as discussed here: https://bugs.llvm.org/show_bug.cgi?id=12402

Hence, starting from the last store, add all (non-synthesizable) instructions belonging to this store's operand tree (and collect the set of memory locations read from). Then proceed to the next store. If the store's memory location conflicts with any of the memory locations read add the next store's operand tree to the very same statement. If the read set of the earlier store and the subsequent writes do not interfere,

Best,
Tobias

[nandini12396]

Hello Sir,

no need to change tests. I would just run this once over polybench to see if anything fails.

I ran LNT on the llvm test-suite with cflags -O3 -mllvm -polly -mllvm -polly-process-unprofitable and there are no failures.
However, there are some assertion fails in polly/tests/ itself. One such example is test/Isl/CodeGen/non-affine-dominance-generated-entering.ll.
I will try to understand this and let you know.

Thank you,
Nandini

[Meinersbur]

Sorry for my absence for a while, a paper submission deadline came in the way.

I think we should not use "one and only one" strategy. We may want to run experiments to compare different strategies with each other. I suggest adding an option to switch between strategies, such as:

enum class GranularityChoice {
	BasicBlocks,
	Stores
};

static cl::opt<GranularityChoice> StmtGranularity("polly-stmt-granularity", 
	cl::desc("Select the statement granularity algorithm"),
	cl::values(
		clEnumValN(GranularityChoice::BasicBlocks, "bb", "Entire basic blocks granularity"),
		clEnumValN(GranularityChoice::Stores, "store", "Store-level granularity")
	),
	 cl::init(GranularityChoice::BasicBlocks), 
	cl::cat(PollyCategory));

This allows us to implement multiple strategies. Existing regression tests do not need to be changed.

One day we determined a "best" strategy, we only need to change the default. Regression tests can continue using -polly-stmt-granularity=bb.

The store-level granularity you implemented looks ok. I suggest to keep the polly_split_after metadata splitting which allows us to force splitting whatever the -polly-stmt-granularity setting is. The only tests I observe crashing (and therefore should fix) are ScopInfo/invariant_load_zext_parameter-2.ll and Isl\CodeGen\non-affine-dominance-generated-entering.ll.

Ideas for follow-up patches:

• A instruction-level granularity where each statement has at most one instruction. I don't expect it to be useful in production, but for stress-testing Polly with lots of statements.

• We could improve store-level granularity by only adding instructions required by that store to the same statement (if not yet added to another statement yet). Instructions not required by any store can be put in its own statement. -polly-optree would move it anyway, but it would be nice it had less work to do and have fewer dependencies if -polly-optree is not used.

[nandini12396]

Hello Sir,

Somehow, there are no assertion failures after your changes :).

[nandini12396]

but, those test-case fail when we add -polly-stmt-granularity=store still. Do we need to fix them?

[Meinersbur]

Please add at least one test case for the new feature (splitting at stores).

Yes please fix the crashes. You can make a copy of the test cases and add -polly-stmt-granularity=store. There should never be any input that makes the compiler crash.

[Meinersbur]

lib/Analysis/ScopBuilder.cpp

740–744 ↗

(On Diff #116827)

I looked at non-affine-dominance-generated-entering-1.ll and these lines causes the region-stmt for subregionStmt to split, but we cannot split region statements yet. We must not break the loop here, there are no additional statements for a region-stmt.

Tobias recently added instruction lists for a region-stmts entry node. Support for splitting it shouldn't that hard anymore (If you want to implement that, please try in a different patch)

[nandini12396]

@Meinersbur: Oh I see that. Thank you, I will try that now.

[nandini12396]

@Meinersbur : After your commit rL314665, these tests no longer fail.

[Meinersbur]

In D37337#888368, @nandini12396 wrote:

@Meinersbur : After your commit rL314665, these tests no longer fail.

Could you rebase this patch?

[nandini12396]

rebase

[Meinersbur]

Please add at least one test case where a basic block is successfully split up and check that there are two statements now.

lib/Analysis/ScopBuilder.cpp

697 ↗

(On Diff #117690)

Not specificfor this patch:
StoreInsts are not the only instructions that write to memory, some CallInsts do as well: memset, etc.
There is Instruction::mayWriteToMemory(). Should we split at those as well?

test/Isl/CodeGen/non-affine-dominance-generated-entering-1.ll

3–7 ↗

(On Diff #117690)

Please update the description of what this test is for.

9–16 ↗

(On Diff #117690)

If this test is for testing the capability to split statement, we should test the result of the split (ScopInfo -analyze output)

test/ScopInfo/invariant_load_zext_parameter-3.ll

4 ↗

(On Diff #117690)

Please update the description of what this test is for.

25–29 ↗

(On Diff #117690)

If this test is for testing the capability to split statement, we should test the result of the split (ScopInfo -analyze output)

[Meinersbur]

LGTM, going to committ...

Thanks a lot!

test/ScopInfo/stmt_split_on_store.ll

1 ↗

(On Diff #126274)

Very nice test case.

[Meinersbur]

I filed a bug for this option: http://llvm.org/PR35623 .

This is likely not specific to the -polly-stmt-granularity=store option, but for splitting in general.

polly/trunk/include/polly/ScopBuilder.h

class ScopBuilder {
   ///
   /// @returns True if the instruction should be modeled.
   bool shouldModelInst(Instruction *Inst, Loop *L);
 
   /// Create one or more ScopStmts for @p BB.
   ///
   /// Consecutive instructions are associated to the same statement until a
   /// separator is found.
-  void buildSequentialBlockStmts(BasicBlock *BB);
+  void buildSequentialBlockStmts(BasicBlock *BB, bool SplitOnStore = false);
 
   /// Create one or more ScopStmts for @p BB using equivalence classes.
   ///
   /// Instructions of a basic block that belong to the same equivalence class
   /// are added to the same statement.
   void buildEqivClassBlockStmts(BasicBlock *BB);
 
   /// Create ScopStmt for all BBs and non-affine subregions of @p SR.

polly/trunk/lib/Analysis/ScopBuilder.cpp

 // Multiplicative reductions can be disabled separately as these kind of
 // operations can overflow easily. Additive reductions and bit operations
 // are in contrast pretty stable.
 static cl::opt<bool> DisableMultiplicativeReductions(
     "polly-disable-multiplicative-reductions",
     cl::desc("Disable multiplicative reductions"), cl::Hidden, cl::ZeroOrMore,
     cl::init(false), cl::cat(PollyCategory));
 
-enum class GranularityChoice { BasicBlocks, ScalarIndependence };
+enum class GranularityChoice { BasicBlocks, ScalarIndependence, Stores };
 
 static cl::opt<GranularityChoice> StmtGranularity(
     "polly-stmt-granularity",
     cl::desc(
         "Algorithm to use for splitting basic blocks into multiple statements"),
     cl::values(clEnumValN(GranularityChoice::BasicBlocks, "bb",
                           "One statement per basic block"),
                clEnumValN(GranularityChoice::ScalarIndependence, "scalar-indep",
-                          "Scalar independence heuristic")),
+                          "Scalar independence heuristic"),
+               clEnumValN(GranularityChoice::Stores, "store",
+                          "Store-level granularity")),
     cl::init(GranularityChoice::BasicBlocks), cl::cat(PollyCategory));
 
 void ScopBuilder::buildPHIAccesses(ScopStmt *PHIStmt, PHINode *PHI,
                                    Region *NonAffineSubRegion,
                                    bool IsExitBlock) {
   // PHI nodes that are in the exit block of the region, hence if IsExitBlock is
   // true, are not modeled as ordinary PHI nodes as they are not part of the
   // region. However, we model the operands in the predecessor blocks that are
void ScopBuilder::buildAccessFunctions() {
   }
 }
 
 bool ScopBuilder::shouldModelInst(Instruction *Inst, Loop *L) {
   return !isa<TerminatorInst>(Inst) && !isIgnoredIntrinsic(Inst) &&
          !canSynthesize(Inst, *scop, &SE, L);
 }
 
-void ScopBuilder::buildSequentialBlockStmts(BasicBlock *BB) {
+void ScopBuilder::buildSequentialBlockStmts(BasicBlock *BB, bool SplitOnStore) {
   Loop *SurroundingLoop = LI.getLoopFor(BB);
 
   int Count = 0;
   std::vector<Instruction *> Instructions;
   for (Instruction &Inst : *BB) {
     if (shouldModelInst(&Inst, SurroundingLoop))
       Instructions.push_back(&Inst);
-    if (Inst.getMetadata("polly_split_after")) {
+    if (Inst.getMetadata("polly_split_after") ||
+        (SplitOnStore && isa<StoreInst>(Inst))) {
       scop->addScopStmt(BB, SurroundingLoop, Instructions, Count);
       Count++;
       Instructions.clear();
     }
   }
 
   scop->addScopStmt(BB, SurroundingLoop, Instructions, Count);
 }
else {
       BasicBlock *BB = I->getNodeAs<BasicBlock>();
       switch (StmtGranularity) {
       case GranularityChoice::BasicBlocks:
         buildSequentialBlockStmts(BB);
         break;
       case GranularityChoice::ScalarIndependence:
         buildEqivClassBlockStmts(BB);
         break;
+      case GranularityChoice::Stores:
+        buildSequentialBlockStmts(BB, true);
+        break;
       }
     }
 }
 
 void ScopBuilder::buildAccessFunctions(ScopStmt *Stmt, BasicBlock &BB,
                                        Region *NonAffineSubRegion) {
   assert(
       Stmt &&

polly/trunk/test/ScopInfo/stmt_split_on_store.ll

+; RUN: opt %loadPolly -polly-scops -analyze -polly-stmt-granularity=store -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:    Statements {
+; CHECK-NEXT:   Stmt_Stmt
+; CHECK-NEXT:       Domain :=
+; CHECK-NEXT:           { Stmt_Stmt[i0] : 0 <= i0 <= 1023 };
+; CHECK-NEXT:       Schedule :=
+; CHECK-NEXT:           { Stmt_Stmt[i0] -> [i0, 0] };
+; CHECK-NEXT:       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
+; CHECK-NEXT:       }
+; CHECK-NEXT:   Stmt_Stmt1
+; CHECK-NEXT:       Domain :=
+; CHECK-NEXT:           { Stmt_Stmt1[i0] : 0 <= i0 <= 1023 };
+; CHECK-NEXT:       Schedule :=
+; CHECK-NEXT:           { Stmt_Stmt1[i0] -> [i0, 1] };
+; CHECK-NEXT:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:           { Stmt_Stmt1[i0] -> MemRef_B[i0] };
+; CHECK-NEXT:       Instructions {
+; CHECK-NEXT:             store i32 %i.0, i32* %arrayidx2, align 4
+; CHECK-NEXT:       }
+; 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
+  %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
+}