[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

32 ↗

(On Diff #110003)

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 ↗

(On Diff #111299)

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 ↗

(On Diff #112155)

[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)

660 ↗

(On Diff #112155)

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?

670 ↗

(On Diff #112155)

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 ↗

(On Diff #112155)

Both statements are still named "Stmt_Stmt"?

[nandini12396]

lib/Analysis/ScopBuilder.cpp

623 ↗

(On Diff #112155)

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.

polly/trunk/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);

polly/trunk/include/polly/ScopInfo.h

 ///
 /// It is further described by its iteration domain, its schedule and its data
 /// accesses.
 /// At the moment every statement represents a single basic block of LLVM-IR.
 class ScopStmt {
 public:
   /// Create the ScopStmt from a BasicBlock.
   ScopStmt(Scop &parent, BasicBlock &bb, Loop *SurroundingLoop,
-           std::vector<Instruction *> Instructions);
+           std::vector<Instruction *> Instructions, int Count);
 
   /// Create an overapproximating ScopStmt for the region @p R.
   ScopStmt(Scop &parent, Region &R, Loop *SurroundingLoop);
 
   /// Create a copy statement.
   ///
   /// @param Stmt       The parent statement.
   /// @param SourceRel  The source location.
private:
   ///
   /// A new statement for @p BB will be created and added to the statement
   /// vector
   /// and map.
   ///
   /// @param BB              The basic block we build the statement for.
   /// @param SurroundingLoop The loop the created statement is contained in.
   /// @param Instructions    The instructions in the statement.
+  /// @param Count           The index of the created statement in @p BB.
   void addScopStmt(BasicBlock *BB, Loop *SurroundingLoop,
-                   std::vector<Instruction *> Instructions);
+                   std::vector<Instruction *> Instructions, int Count);
 
   /// Create a new SCoP statement for @p R.
   ///
   /// A new statement for @p R will be created and added to the statement vector
   /// and map.
   ///
   /// @param R               The region we build the statement for.
   /// @param SurroundingLoop The loop the created statement is contained in.

polly/trunk/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 {
+      int Count = 0;
       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, Count);
+          Count++;
+          Instructions.clear();
+        }
       }
       Loop *SurroundingLoop = LI.getLoopFor(I->getNodeAs<BasicBlock>());
       scop->addScopStmt(I->getNodeAs<BasicBlock>(), SurroundingLoop,
-                        Instructions);
+                        Instructions, Count);
     }
 }
 
 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;
 
+  int Count = 0;
+  bool Split = false;
   for (Instruction &Inst : BB) {
+    if (Split) {
+      Split = false;
+      Count++;
+    }
+    if (Inst.getMetadata("polly_split_after"))
+      Split = true;
+
+    if (Stmt && Stmt->isBlockStmt() && Stmt != scop->getStmtListFor(&BB)[Count])
+      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;
 

polly/trunk/lib/Analysis/ScopInfo.cpp

 ScopStmt::ScopStmt(Scop &parent, Region &R, Loop *SurroundingLoop)
     : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), R(&R),
       Build(nullptr), SurroundingLoop(SurroundingLoop) {
   BaseName = getIslCompatibleName(
       "Stmt", R.getNameStr(), parent.getNextStmtIdx(), "", UseInstructionNames);
 }
 
 ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb, Loop *SurroundingLoop,
-                   std::vector<Instruction *> Instructions)
+                   std::vector<Instruction *> Instructions, int Count)
     : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), BB(&bb),
       Build(nullptr), SurroundingLoop(SurroundingLoop),
       Instructions(Instructions) {
-  BaseName = getIslCompatibleName("Stmt", &bb, parent.getNextStmtIdx(), "",
+  std::string S = "";
+  if (Count != 0)
+    S += std::to_string(Count);
+  BaseName = getIslCompatibleName("Stmt", &bb, parent.getNextStmtIdx(), S,
                                   UseInstructionNames);
 }
 
 ScopStmt::ScopStmt(Scop &parent, isl::map SourceRel, isl::map TargetRel,
                    isl::set NewDomain)
     : Parent(parent), InvalidDomain(nullptr), Domain(NewDomain),
       Build(nullptr) {
   BaseName = getIslCompatibleName("CopyStmt_", "",
static isl::multi_union_pw_aff mapToDimension(isl::union_set USet, int N) {
   (void)Res;
 
   assert(Res == isl::stat::ok);
 
   return isl::multi_union_pw_aff(isl::union_pw_multi_aff(Result));
 }
 
 void Scop::addScopStmt(BasicBlock *BB, Loop *SurroundingLoop,
-                       std::vector<Instruction *> Instructions) {
+                       std::vector<Instruction *> Instructions, int Count) {
   assert(BB && "Unexpected nullptr!");
-  Stmts.emplace_back(*this, *BB, SurroundingLoop, Instructions);
+  Stmts.emplace_back(*this, *BB, SurroundingLoop, Instructions, Count);
   auto *Stmt = &Stmts.back();
   StmtMap[BB].push_back(Stmt);
   for (Instruction *Inst : Instructions) {
     assert(!InstStmtMap.count(Inst) &&
            "Unexpected statement corresponding to the instruction.");
     InstStmtMap[Inst] = Stmt;
   }
 }
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.empty())
     return StmtList.back();
   return nullptr;

polly/trunk/test/Isl/CodeGen/stmt_split_no_dependence.ll

+; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
+;
+; CHECK:   store i32 %8, i32* %scevgep, align 4, !alias.scope !1, !noalias !3
+; CHECK:   store i32 %9, i32* %scevgep4, align 4, !alias.scope !4, !noalias !5
+;
+;      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"} 

polly/trunk/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:    }
-
-; 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
-}

polly/trunk/test/ScopInfo/stmt_split_exit_of_region_stmt.ll

+; RUN: opt %loadPolly -polly-scops -analyze -polly-print-instructions < %s | FileCheck %s
+;
+; CHECK:    Statements {
+; CHECK-NEXT:   Stmt_Region__TO__Stmt
+; CHECK-NEXT:       Domain :=
+; CHECK-NEXT:           { Stmt_Region__TO__Stmt[i0] : 0 <= i0 <= 1023 };
+; CHECK-NEXT:       Schedule :=
+; CHECK-NEXT:           { Stmt_Region__TO__Stmt[i0] -> [i0, 0] };
+; CHECK-NEXT:       MayWriteAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:           { Stmt_Region__TO__Stmt[i0] -> MemRef_C[0] };
+; CHECK-NEXT:   Stmt_Stmt
+; CHECK-NEXT:       Domain :=
+; CHECK-NEXT:           { Stmt_Stmt[i0] : 0 <= i0 <= 1023 };
+; CHECK-NEXT:       Schedule :=
+; CHECK-NEXT:           { Stmt_Stmt[i0] -> [i0, 1] };
+; 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, !polly_split_after !0
+; 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, 2] };
+; 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, double* %C) {
+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 %Region
+
+Region:                                           ; preds = %for.body
+  %cond = fcmp oeq double 2.100000e+01, 2.100000e+01
+  br i1 %cond, label %Region_true, label %Stmt
+
+Region_true:                                      ; preds = %Region
+  store double 0.000000e+00, double* %C
+  br label %Stmt
+
+Stmt:                                             ; preds = %Region_true, %Region
+  %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"}

polly/trunk/test/ScopInfo/stmt_split_no_dependence.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:    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, !polly_split_after !0
+; 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, !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"}

polly/trunk/test/ScopInfo/stmt_split_on_synthesizable.ll

+; RUN: opt %loadPolly -polly-scops -analyze -polly-print-instructions < %s | FileCheck %s
+;
+; 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, double* %C) #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:
+  %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, !polly_split_after !0
+  %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"}

polly/trunk/test/ScopInfo/stmt_split_phi_in_beginning_bb.ll

+; RUN: opt %loadPolly -polly-scops -analyze -polly-print-instructions < %s | FileCheck %s
+;
+; 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 %phi, i32* %arrayidx, align 4, !polly_split_after !0
+; 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:
+  %phi = phi i32 [0, %for.body]
+  %idxprom = sext i32 %i.0 to i64
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom
+  store i32 %phi, 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"}

polly/trunk/test/ScopInfo/stmt_split_phi_in_stmt.ll

+; RUN: opt %loadPolly -polly-scops -analyze -polly-print-instructions < %s | FileCheck %s
+;
+; 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, !polly_split_after !0
+; 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:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:           { Stmt_Stmt1[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:       Instructions {
+; CHECK-NEXT:             %d = fadd double 2.100000e+01, 2.100000e+01
+; CHECK-NEXT:             store i32 %i.0, i32* %arrayidx2, align 4
+; CHECK-NEXT:       }
+; CHECK-NEXT:   Stmt_for_inc
+; CHECK-NEXT:       Domain :=
+; CHECK-NEXT:           { Stmt_for_inc[i0] : 0 <= i0 <= 1023 };
+; CHECK-NEXT:       Schedule :=
+; CHECK-NEXT:           { Stmt_for_inc[i0] -> [i0, 2] };
+; CHECK-NEXT:       ReadAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:           { Stmt_for_inc[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:           { Stmt_for_inc[i0] -> MemRef_C[0] };
+; CHECK-NEXT:       Instructions {
+; CHECK-NEXT:             %phi = phi double [ %d, %Stmt ]
+; CHECK-NEXT:             store double %phi, double* %C
+; CHECK-NEXT:       }
+; CHECK-NEXT:   }
+;
+; Function Attrs: noinline nounwind uwtable
+define void @func(i32* %A, i32* %B, double* %C) #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:
+  %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
+  %d = fadd double 21.0, 21.0
+  %arrayidx2 = getelementptr inbounds i32, i32* %B, i64 %idxprom1
+  store i32 %i.0, i32* %arrayidx2, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %Stmt
+  %phi = phi double [%d, %Stmt]
+  store double %phi, double* %C
+  %add = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+!0 = !{!"polly_split_after"}

polly/trunk/test/ScopInfo/stmt_split_within_loop.ll

+; RUN: opt %loadPolly -polly-scops -analyze -polly-print-instructions < %s | FileCheck %s
+;
+; CHECK:    Statements {
+; CHECK-NEXT:   Stmt_Stmt
+; CHECK-NEXT:       Domain :=
+; CHECK-NEXT:           { Stmt_Stmt[i0, i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 512 };
+; CHECK-NEXT:       Schedule :=
+; CHECK-NEXT:           { Stmt_Stmt[i0, i1] -> [i0, i1, 0] };
+; CHECK-NEXT:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:           { Stmt_Stmt[i0, i1] -> MemRef_A[i0] };
+; CHECK-NEXT:       Instructions {
+; CHECK-NEXT:             store i32 %i.0, i32* %arrayidx, align 4, !polly_split_after !0
+; CHECK-NEXT:       }
+; CHECK-NEXT:   Stmt_Stmt1
+; CHECK-NEXT:       Domain :=
+; CHECK-NEXT:           { Stmt_Stmt1[i0, i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 512 };
+; CHECK-NEXT:       Schedule :=
+; CHECK-NEXT:           { Stmt_Stmt1[i0, i1] -> [i0, i1, 1] };
+; CHECK-NEXT:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:           { Stmt_Stmt1[i0, i1] -> MemRef_B[i0] };
+; CHECK-NEXT:       Instructions {
+; CHECK-NEXT:             store i32 %i.0, i32* %arrayidx2, align 4
+; CHECK-NEXT:             %cond = icmp slt i32 %j, 512
+; CHECK-NEXT:       }
+; CHECK-NEXT:   }
+;
+; Function Attrs: noinline nounwind uwtable
+define void @func(i32* %A, i32* %B, double* %C) #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:
+  %j = phi i32 [ 0, %for.body ], [ %inc, %Stmt ]
+  %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
+  %inc = add nsw i32 %j, 1
+  %cond = icmp slt i32 %j, 512
+  br i1 %cond, label %Stmt, 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"}