[Polly][ScopBuilder] Introduce -polly-stmt-granularity=scalar-indep option.

[Meinersbur]

Summary

The option splits BasicBlocks into minimal statements such that no additional scalar dependencies are introduced.

The algorithm is based on a union-find structure, and unites sets if putting them into separate statements would introduce a scalar dependencies. As a consequence, instructions may be split into separate statements such their relative order is different than the statements they are in. This is accounted for instructions whose relative order matters (e.g. memory accesses).

The algorithm is generic in that heuristic changes can be made with relative ease. We might relax the order requirement for read-reads or accesses to different base pointers. Forwardable instructions can be made to not cause a join.

This implementation gives us a speed-up of 82% in SPEC 2006 456.hmmer benchmark by allowing loop-distribution in a hot loop.

[nandini12396]

@Meinersbur : A quick q. Even if the split introduced new scalar dependences, wouldnt forward op tree pass take care of it?

[bollu]

lib/Analysis/ScopBuilder.cpp

110 ↗

(On Diff #117140)

Nit: Could you add a one line explanation as to what the granularity refers to, please?

758 ↗

(On Diff #117140)

I don't understand, what is this loop trying to do? As best as I can tell, it checks that if we have seen Leader previously (Inserted == false), then we fuse Leader` with everything that was added after Leader.

Is this to ensure that in situations like this:

A
B
A

A and B are forced into the same basic block?

Either way, I'd appreciate it if it was written in a separate function or something, because it seems nice and modular.

766 ↗

(On Diff #117140)

Nit: could you please provide the concrete type used here? (Instruction *)

772 ↗

(On Diff #117140)

AFAICT, we don't need to call getLeaderValue on SeenLeaders.back(), because SeenLeaders only contains leaders.

787 ↗

(On Diff #117140)

Nit: please give this a concrete type (Instruction *)

796 ↗

(On Diff #117140)

Nit: could you factor this out into a separate function or a lambda? insertLeaderInstructions(...), or insertEquivalenceClassInstructions

[Meinersbur]

In D38403#884413, @nandini12396 wrote:

@Meinersbur : A quick q. Even if the split introduced new scalar dependences, wouldnt forward op tree pass take care of it?

ForwardOpTree cannot forward everything, only 'speculatable' instructions and loads that are known to not have changed.

Even though this might cover a large number of cases, I tried to get something that conservatively doesn't do anything worse than it was before. More aggressive strategies (such as splitting each write access into its own statement) can be implemented as well.

[grosser]

Cool. Would be great to see the LICM working.

[grosser]

I mean see it working with LICM. Thanks Michael!

[nandini12396]

In D38403#884443, @Meinersbur wrote:

ForwardOpTree cannot forward everything, only 'speculatable' instructions and loads that are known to not have changed.

Ok. So, this option will, in future cover https://reviews.llvm.org/D37337#859617 ?

[Meinersbur]

• Add unit tests
• Refactor
• Handle scalar dependencies due to incoming values
• Add comments

[Meinersbur]

In D38403#884578, @nandini12396 wrote:

In D38403#884443, @Meinersbur wrote:

ForwardOpTree cannot forward everything, only 'speculatable' instructions and loads that are known to not have changed.

Ok. So, this option will, in future cover https://reviews.llvm.org/D37337#859617 ?

Yes, although I think Tobias also had in mind what ForwardOpTree does today. Currently getScopStmt(Instruction*) allows returning only a single ScopStmt anyway, such that at this stage we cannot duplicate instructions into multiple statements. Although we could choose a 'primary' location for each instruction. There is definitely still room for improvement.

lib/Analysis/ScopBuilder.cpp

772 ↗

(On Diff #117140)

Former leaders may have merged into other leaders since it was added.

[grosser]

Hi Michael,

thanks for the update. Is the commit message up-to-date (AKA is the WIP still open or has it been resolved). Would be good to know before I start a more in-depth review!

Best,
Tobias

test/ScopInfo/granularity_scalar-indep.ll

4 ↗

(On Diff #117659)

interleaved

[Meinersbur]

In D38403#888103, @grosser wrote:

Hi Michael,

thanks for the update. Is the commit message up-to-date (AKA is the WIP still open or has it been resolved). Would be good to know before I start a more in-depth review!

The issue has been resolved bt commits rr314662 to r314665. I removed the [WIP] tag, but forgot to update the summary.

[bollu]

lib/Analysis/ScopBuilder.cpp

711 ↗

(On Diff #117659)

Just to clarify: An Instruction I is ordered if there exists an instruction J such that I; J != J; I, correct?

739 ↗

(On Diff #117659)

Consider joinPHIWritesToEpilogue?

799 ↗

(On Diff #117659)

Consider a name such as joinAllAfterEpilogue? I feel that this name carries the intent a little better.

test/ScopInfo/granularity_scalar-indep_noepilogue.ll

3 ↗

(On Diff #117659)

Nit: epilogie -> epilogue

[Meinersbur]

lib/Analysis/ScopBuilder.cpp

711 ↗

(On Diff #117659)

Not exactly, but it's the right idea.

Nit: Equality (!=) is not the right relation. If I;J is a tuple, then those are never equal. If it is a set, they are always equal. What you mean is some equivalence relation for semantics, which is difficult to define formally. I also don't intend to guarantee that if this function is true, that such an instruction J exists. Interactions with a third instruction K between I and J might also be possible, or depend on the code around. It is more that if it returns false and any permutation of non-ordered instructions have the same semantics in any context.

I'd stay with a verbal definition.

739 ↗

(On Diff #117659)

I call "epilogue" the last statement of a basic block where the PHI writes are added to. That is, PHI writes are always in the epilogue, whether this function is called or not.

More exact would be joinStatementsContainingDefinitionsOfIncomingValuesInSuccessorBlockWithEpilogue.

If PHI writes are added to the statement containing the definition instead of the writes, this function becomes useless. I hope to implement that sometime.

799 ↗

(On Diff #117659)

Good idea.

test/ScopInfo/granularity_scalar-indep.ll

4 ↗

(On Diff #117659)

thanks

test/ScopInfo/granularity_scalar-indep_noepilogue.ll

3 ↗

(On Diff #117659)

thanks

[bollu]

Thanks for the very clean patch :) I really like reviewing your code, it's always really well written.

lib/Analysis/ScopBuilder.cpp

711 ↗

(On Diff #117659)

Thanks for the correction!

Consider adding the explanation you just gave to the comment, in that case?

"An unordered instruction is an instruction, such that a sequence of unordered instructions can be permuted without changing semantics. An ordered instruction is an instruction that is not unordered."

[grosser]

Very cool. That looks good to me (after addressing Siddharth's comments).

lib/Analysis/ScopBuilder.cpp

709 ↗

(On Diff #117659)

its semantics

[Meinersbur]

• Address comments
• Fix return instead of continue bug

polly/trunk/include/polly/ScopBuilder.h

class ScopBuilder {
   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);
 
+  /// 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.
   ///
   /// @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);
 

polly/trunk/lib/Analysis/ScopBuilder.cpp

 #include "polly/ScopDetectionDiagnostic.h"
 #include "polly/ScopInfo.h"
 #include "polly/Support/SCEVValidator.h"
 #include "polly/Support/ScopHelper.h"
 #include "polly/Support/VirtualInstruction.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/EquivalenceClasses.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/OptimizationDiagnosticInfo.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Analysis/RegionIterator.h"
 #include "llvm/Analysis/ScalarEvolution.h"

 // 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 };
+enum class GranularityChoice { BasicBlocks, ScalarIndepependence };
 
 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")),
+                          "One statement per basic block"),
+               clEnumValN(GranularityChoice::ScalarIndepependence,
+                          "scalar-indep", "Scalar independence heuristic")),
     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
if (Inst.getMetadata("polly_split_after")) {
       Count++;
       Instructions.clear();
     }
   }
 
   scop->addScopStmt(BB, SurroundingLoop, Instructions, Count);
 }
 
+/// Is @p Inst an ordered instruction?
+///
+/// An unordered instruction is an instruction, such that a sequence of
+/// unordered instructions can be permuted without changing semantics. Any
+/// instruction for which this is not always the case is ordered.
+static bool isOrderedInstruction(Instruction *Inst) {
+  return Inst->mayHaveSideEffects() || Inst->mayReadOrWriteMemory();
+}
+
+/// Join instructions to the same statement if one uses the scalar result of the
+/// other.
+static void joinOperandTree(EquivalenceClasses<Instruction *> &UnionFind,
+                            ArrayRef<Instruction *> ModeledInsts) {
+  for (Instruction *Inst : ModeledInsts) {
+    if (isa<PHINode>(Inst))
+      continue;
+
+    for (Use &Op : Inst->operands()) {
+      Instruction *OpInst = dyn_cast<Instruction>(Op.get());
+      if (!OpInst)
+        continue;
+
+      // Check if OpInst is in the BB and is a modeled instruction.
+      auto OpVal = UnionFind.findValue(OpInst);
+      if (OpVal == UnionFind.end())
+        continue;
+
+      UnionFind.unionSets(Inst, OpInst);
+    }
+  }
+}
+
+/// Join instructions that are used as incoming value in successor PHIs into the
+/// epilogue.
+static void
+joinIncomingPHIValuesIntoEpilogue(EquivalenceClasses<Instruction *> &UnionFind,
+                                  ArrayRef<Instruction *> ModeledInsts,
+                                  BasicBlock *BB) {
+  for (BasicBlock *Succ : successors(BB)) {
+    for (Instruction &SuccInst : *Succ) {
+      PHINode *SuccPHI = dyn_cast<PHINode>(&SuccInst);
+      if (!SuccPHI)
+        break;
+
+      Value *IncomingVal = SuccPHI->getIncomingValueForBlock(BB);
+      Instruction *IncomingInst = dyn_cast<Instruction>(IncomingVal);
+      if (!IncomingInst)
+        continue;
+      if (IncomingInst->getParent() != BB)
+        continue;
+      if (UnionFind.findValue(IncomingInst) == UnionFind.end())
+        continue;
+
+      UnionFind.unionSets(nullptr, IncomingInst);
+    }
+  }
+}
+
+/// Ensure that the order of ordered instructions does not change.
+///
+/// If we encounter an ordered instruction enclosed in instructions belonging to
+/// a different statement (which might as well contain ordered instructions, but
+/// this is not tested here), join them.
+static void
+joinOrderedInstructions(EquivalenceClasses<Instruction *> &UnionFind,
+                        ArrayRef<Instruction *> ModeledInsts) {
+  SetVector<Instruction *> SeenLeaders;
+  for (Instruction *Inst : ModeledInsts) {
+    if (!isOrderedInstruction(Inst))
+      continue;
+
+    Instruction *Leader = UnionFind.getLeaderValue(Inst);
+    bool Inserted = SeenLeaders.insert(Leader);
+    if (Inserted)
+      continue;
+
+    // Merge statements to close holes. Say, we have already seen statements A
+    // and B, in this order. Then we see an instruction of A again and we would
+    // see the pattern "A B A". This function joins all statements until the
+    // only seen occurrence of A.
+    for (Instruction *Prev : reverse(SeenLeaders)) {
+      // Items added to 'SeenLeaders' are leaders, but may have lost their
+      // leadership status when merged into another statement.
+      Instruction *PrevLeader = UnionFind.getLeaderValue(SeenLeaders.back());
+      if (PrevLeader == Leader)
+        break;
+      UnionFind.unionSets(Prev, Leader);
+    }
+  }
+}
+
+/// Also ensure that the epilogue is the last statement relative to all ordered
+/// instructions.
+///
+/// This is basically joinOrderedInstructions() but using the epilogue as
+/// 'ordered instruction'.
+static void joinAllAfterEpilogue(EquivalenceClasses<Instruction *> &UnionFind,
+                                 ArrayRef<Instruction *> ModeledInsts) {
+  bool EpilogueSeen = false;
+  for (Instruction *Inst : ModeledInsts) {
+    auto PHIWritesLeader = UnionFind.findLeader(nullptr);
+    auto InstLeader = UnionFind.findLeader(Inst);
+
+    if (PHIWritesLeader == InstLeader)
+      EpilogueSeen = true;
+
+    if (!isOrderedInstruction(Inst))
+      continue;
+
+    if (EpilogueSeen)
+      UnionFind.unionSets(PHIWritesLeader, InstLeader);
+  }
+}
+
+void ScopBuilder::buildEqivClassBlockStmts(BasicBlock *BB) {
+  Loop *L = LI.getLoopFor(BB);
+
+  // Extracting out modeled instructions saves us from checking
+  // shouldModelInst() repeatedly.
+  SmallVector<Instruction *, 32> ModeledInsts;
+  EquivalenceClasses<Instruction *> UnionFind;
+  for (Instruction &Inst : *BB) {
+    if (!shouldModelInst(&Inst, L))
+      continue;
+    ModeledInsts.push_back(&Inst);
+    UnionFind.insert(&Inst);
+  }
+
+  // 'nullptr' represents the last statement for a basic block. It contains no
+  // instructions, but holds the PHI write accesses for successor basic blocks.
+  // If a PHI has an incoming value defined in this BB, it can also be merged
+  // with other statements.
+  // TODO: We wouldn't need this if we would add PHIWrites into the statement
+  // that defines the incoming value (if in the BB) instead of always the last,
+  // so we could unconditionally always add a last statement.
+  UnionFind.insert(nullptr);
+
+  joinOperandTree(UnionFind, ModeledInsts);
+  joinIncomingPHIValuesIntoEpilogue(UnionFind, ModeledInsts, BB);
+  joinOrderedInstructions(UnionFind, ModeledInsts);
+  joinAllAfterEpilogue(UnionFind, ModeledInsts);
+
+  // The list of instructions for statement (statement represented by the leader
+  // instruction). The order of statements instructions is reversed such that
+  // the epilogue is first. This makes it easier to ensure that the epilogue is
+  // the last statement.
+  MapVector<Instruction *, std::vector<Instruction *>> LeaderToInstList;
+
+  // Ensure that the epilogue is last.
+  LeaderToInstList[nullptr];
+
+  // Collect the instructions of all leaders. UnionFind's member iterator
+  // unfortunately are not in any specific order.
+  for (Instruction &Inst : reverse(*BB)) {
+    auto LeaderIt = UnionFind.findLeader(&Inst);
+    if (LeaderIt == UnionFind.member_end())
+      continue;
+
+    std::vector<Instruction *> &InstList = LeaderToInstList[*LeaderIt];
+    InstList.push_back(&Inst);
+  }
+
+  // Finally build the statements.
+  int Count = 0;
+  for (auto &Instructions : reverse(LeaderToInstList)) {
+    std::vector<Instruction *> &InstList = Instructions.second;
+    std::reverse(InstList.begin(), InstList.end());
+    scop->addScopStmt(BB, L, std::move(InstList), Count);
+    Count += 1;
+  }
+}
+
 void ScopBuilder::buildStmts(Region &SR) {
   if (scop->isNonAffineSubRegion(&SR)) {
     std::vector<Instruction *> Instructions;
     Loop *SurroundingLoop =
         getFirstNonBoxedLoopFor(SR.getEntry(), LI, scop->getBoxedLoops());
     for (Instruction &Inst : *SR.getEntry())
       if (shouldModelInst(&Inst, SurroundingLoop))
         Instructions.push_back(&Inst);
     scop->addScopStmt(&SR, SurroundingLoop, Instructions);
     return;
   }
 
   for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
     if (I->isSubRegion())
       buildStmts(*I->getNodeAs<Region>());
     else {
       BasicBlock *BB = I->getNodeAs<BasicBlock>();
       switch (StmtGranularity) {
       case GranularityChoice::BasicBlocks:
         buildSequentialBlockStmts(BB);
         break;
+      case GranularityChoice::ScalarIndepependence:
+        buildEqivClassBlockStmts(BB);
+        break;
       }
     }
 }
 
 void ScopBuilder::buildAccessFunctions(ScopStmt *Stmt, BasicBlock &BB,
                                        Region *NonAffineSubRegion) {
   assert(
       Stmt &&

polly/trunk/test/ScopInfo/granularity_scalar-indep.ll

+; RUN: opt %loadPolly -polly-stmt-granularity=scalar-indep -polly-print-instructions -polly-scops -analyze < %s | FileCheck %s -match-full-lines
+;
+; Split a block into two independent statements that share no scalar.
+; This case has the instructions of the two statements interleaved, such that
+; splitting the BasicBlock in the middle would cause a scalar dependency.
+;
+; for (int j = 0; j < n; j += 1) {
+; body:
+;   double valA = A[0];
+;   double valB = 21.0 + 21.0;
+;   A[0] = valA;
+;   B[0] = valB;
+; }
+;
+define void @func(i32 %n, double* noalias nonnull %A, double* noalias nonnull %B) {
+entry:
+  br label %for
+
+for:
+  %j = phi i32 [0, %entry], [%j.inc, %inc]
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %body, label %exit
+
+    body:
+      %valA = load double, double* %A
+      %valB = fadd double 21.0, 21.0
+      store double %valA, double* %A
+      store double %valB, double* %B
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK:      Statements {
+; CHECK-NEXT:     Stmt_body
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [n] -> { Stmt_body[i0] : 0 <= i0 < n };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [n] -> { Stmt_body[i0] -> [i0, 0] };
+; CHECK-NEXT:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_body[i0] -> MemRef_A[0] };
+; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_body[i0] -> MemRef_A[0] };
+; CHECK-NEXT:         Instructions {
+; CHECK-NEXT:               %valA = load double, double* %A
+; CHECK-NEXT:               store double %valA, double* %A
+; CHECK-NEXT:         }
+; CHECK-NEXT:     Stmt_body1
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [n] -> { Stmt_body1[i0] : 0 <= i0 < n };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [n] -> { Stmt_body1[i0] -> [i0, 1] };
+; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_body1[i0] -> MemRef_B[0] };
+; CHECK-NEXT:         Instructions {
+; CHECK-NEXT:               %valB = fadd double 2.100000e+01, 2.100000e+01
+; CHECK-NEXT:               store double %valB, double* %B
+; CHECK-NEXT:         }
+; CHECK-NEXT: }

polly/trunk/test/ScopInfo/granularity_scalar-indep_epilogue.ll

+; RUN: opt %loadPolly -polly-stmt-granularity=scalar-indep -polly-print-instructions -polly-scops -analyze < %s | FileCheck %s -match-full-lines
+;
+; Split a block into two independent statements that share no scalar.
+; This case has an independent statement just for PHI writes.
+;
+; for (int j = 0; j < n; j += 1) {
+; bodyA:
+;   double valA = A[0];
+;   A[0] = valA;
+;
+; bodyB:
+;   phi = 42.0;
+; }
+;
+define void @func(i32 %n, double* noalias nonnull %A) {
+entry:
+  br label %for
+
+for:
+  %j = phi i32 [0, %entry], [%j.inc, %inc]
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %bodyA, label %exit
+
+    bodyA:
+      %valA = load double, double* %A
+      store double %valA, double* %A
+      br label %bodyB
+
+    bodyB:
+      %phi = phi double [42.0, %bodyA]
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK:      Statements {
+; CHECK-NEXT:     Stmt_bodyA
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] : 0 <= i0 < n };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] -> [i0, 0] };
+; CHECK-NEXT:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] -> MemRef_A[0] };
+; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] -> MemRef_A[0] };
+; CHECK-NEXT:         Instructions {
+; CHECK-NEXT:             %valA = load double, double* %A
+; CHECK-NEXT:             store double %valA, double* %A
+; CHECK-NEXT:         }
+; CHECK-NEXT:     Stmt_bodyA1
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [n] -> { Stmt_bodyA1[i0] : 0 <= i0 < n };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [n] -> { Stmt_bodyA1[i0] -> [i0, 1] };
+; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             [n] -> { Stmt_bodyA1[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:         Instructions {
+; CHECK-NEXT:         }
+; CHECK-NEXT: }

polly/trunk/test/ScopInfo/granularity_scalar-indep_epilogue_last.ll

+; RUN: opt %loadPolly -polly-stmt-granularity=scalar-indep -polly-print-instructions -polly-scops -analyze < %s | FileCheck %s -match-full-lines
+;
+; Check that the statement where the PHI writes are in always comes last.
+; Otherwise we'd need to introduce a scalar dependency from the statement
+; defining a value to the last statement of a basic block.
+;
+; for (int j = 0; j < n; j += 1) {
+; bodyA:
+;   double valA = A[0];
+;   A[0] = valA;
+;   double valB = B[0];
+;   B[0] = valB;
+;
+; bodyB:
+;   phi = valA;
+; }
+;
+define void @func(i32 %n, double* noalias nonnull %A, double* noalias nonnull %B) {
+entry:
+  br label %for
+
+for:
+  %j = phi i32 [0, %entry], [%j.inc, %inc]
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %bodyA, label %exit
+
+    bodyA:
+      %valA = load double, double* %A
+      store double %valA, double* %A
+      %valB = load double, double* %B
+      store double %valB, double* %B
+      br label %bodyB
+
+    bodyB:
+      %phi = phi double [%valA, %bodyA]
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK:      Statements {
+; CHECK-NEXT:     Stmt_bodyA
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] : 0 <= i0 < n };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] -> [i0] };
+; CHECK-NEXT:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] -> MemRef_A[0] };
+; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] -> MemRef_A[0] };
+; CHECK-NEXT:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] -> MemRef_B[0] };
+; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] -> MemRef_B[0] };
+; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:         Instructions {
+; CHECK-NEXT:               %valA = load double, double* %A
+; CHECK-NEXT:               store double %valA, double* %A
+; CHECK-NEXT:               %valB = load double, double* %B
+; CHECK-NEXT:               store double %valB, double* %B
+; CHECK-NEXT:         }
+; CHECK-NEXT: }

polly/trunk/test/ScopInfo/granularity_scalar-indep_noepilogue.ll

+; RUN: opt %loadPolly -polly-stmt-granularity=scalar-indep -polly-print-instructions -polly-scops -analyze < %s | FileCheck %s -match-full-lines
+;
+; This case has no explicit epilogue for PHI writes because it would
+; have a scalar dependency to the previous statement.
+;
+; for (int j = 0; j < n; j += 1) {
+; bodyA:
+;   double valA = A[0];
+;   A[0] = valA;
+;
+; bodyB:
+;   phi = valA;
+; }
+;
+define void @func(i32 %n, double* noalias nonnull %A) {
+entry:
+  br label %for
+
+for:
+  %j = phi i32 [0, %entry], [%j.inc, %inc]
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %bodyA, label %exit
+
+    bodyA:
+      %valA = load double, double* %A
+      store double %valA, double* %A
+      br label %bodyB
+
+    bodyB:
+      %phi = phi double [%valA, %bodyA]
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK:      Statements {
+; CHECK-NEXT:     Stmt_bodyA
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] : 0 <= i0 < n };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] -> [i0] };
+; CHECK-NEXT:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] -> MemRef_A[0] };
+; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] -> MemRef_A[0] };
+; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:         Instructions {
+; CHECK-NEXT:               %valA = load double, double* %A
+; CHECK-NEXT:               store double %valA, double* %A
+; CHECK-NEXT:         }
+; CHECK-NEXT: }

polly/trunk/test/ScopInfo/granularity_scalar-indep_ordered.ll

+; RUN: opt %loadPolly -polly-stmt-granularity=scalar-indep -polly-print-instructions -polly-scops -analyze < %s | FileCheck %s -match-full-lines
+;
+; This case cannot be split into two statements because the order of
+; loads and store would be violated.
+;
+; for (int j = 0; j < n; j += 1) {
+; body:
+;   double valA = A[0];
+;   double valB = B[0];
+;   A[0] = valA;
+;   A[0] = valB;
+; }
+;
+define void @func(i32 %n, double* noalias nonnull %A, double* noalias nonnull %B) {
+entry:
+  br label %for
+
+for:
+  %j = phi i32 [0, %entry], [%j.inc, %inc]
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %body, label %exit
+
+    body:
+      %valA = load double, double* %A
+      %valB = load double, double* %B
+      store double %valA, double* %A
+      store double %valB, double* %A
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK:     Statements {
+; CHECK-NEXT:      Stmt_body
+; CHECK-NEXT:          Domain :=
+; CHECK-NEXT:              [n] -> { Stmt_body[i0] : 0 <= i0 < n };
+; CHECK-NEXT:          Schedule :=
+; CHECK-NEXT:              [n] -> { Stmt_body[i0] -> [i0] };
+; CHECK-NEXT:          ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:              [n] -> { Stmt_body[i0] -> MemRef_A[0] };
+; CHECK-NEXT:          ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:              [n] -> { Stmt_body[i0] -> MemRef_B[0] };
+; CHECK-NEXT:          MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:              [n] -> { Stmt_body[i0] -> MemRef_A[0] };
+; CHECK-NEXT:          MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:              [n] -> { Stmt_body[i0] -> MemRef_A[0] };
+; CHECK-NEXT:          Instructions {
+; CHECK-NEXT:                %valA = load double, double* %A
+; CHECK-NEXT:                %valB = load double, double* %B
+; CHECK-NEXT:                store double %valA, double* %A
+; CHECK-NEXT:                store double %valB, double* %A
+; CHECK-NEXT:          }
+; CHECK-NEXT: }