Index: polly/trunk/lib/Analysis/ScopBuilder.cpp
===================================================================
--- polly/trunk/lib/Analysis/ScopBuilder.cpp
+++ polly/trunk/lib/Analysis/ScopBuilder.cpp
@@ -2027,6 +2027,10 @@
       continue;
 
     Instruction *Leader = UnionFind.getLeaderValue(Inst);
+    // Since previous iterations might have merged sets, some items in
+    // SeenLeaders are not leaders anymore. However, The new leader of
+    // previously merged instructions must be one of the former leaders of
+    // these merged instructions.
     bool Inserted = SeenLeaders.insert(Leader);
     if (Inserted)
       continue;
@@ -2036,10 +2040,12 @@
     // 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)
+      // We are backtracking from the last element until we see Inst's leader
+      // in SeenLeaders and merge all into one set. Although leaders of
+      // instructions change during the execution of this loop, it's irrelevant
+      // as we are just searching for the element that we already confirmed is
+      // in the list.
+      if (Prev == Leader)
         break;
       UnionFind.unionSets(Prev, Leader);
     }
Index: polly/trunk/test/ScopInfo/granularity_scalar-indep_ordered-2.ll
===================================================================
--- polly/trunk/test/ScopInfo/granularity_scalar-indep_ordered-2.ll
+++ polly/trunk/test/ScopInfo/granularity_scalar-indep_ordered-2.ll
@@ -0,0 +1,80 @@
+; RUN: opt %loadPolly -polly-stmt-granularity=scalar-indep -polly-print-instructions -polly-scops -analyze < %s | FileCheck %s -match-full-lines
+;
+; This case should be split into two statements because {X[0], Y[0]}
+; and {A[0], B[0]} do not intersect.
+;
+;
+; for (int j = 0; j < n; j += 1) {
+; body:
+;   double valX = X[0];
+;   Y[0] = valX;
+;   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, double* noalias nonnull %X, double* noalias nonnull %Y) {
+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:
+      %valX = load double, double* %X
+      store double %valX, double* %Y
+      %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, 0] };
+; CHECK-NEXT:         ReadAccess :=	[Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_body[i0] -> MemRef_X[0] };
+; CHECK-NEXT:         MustWriteAccess :=	[Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_body[i0] -> MemRef_Y[0] };
+; CHECK-NEXT:         Instructions {
+; CHECK-NEXT:               %valX = load double, double* %X
+; CHECK-NEXT:               store double %valX, double* %Y
+; CHECK-NEXT:         }
+; CHECK-NEXT: 	Stmt_body_b
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [n] -> { Stmt_body_b[i0] : 0 <= i0 < n };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [n] -> { Stmt_body_b[i0] -> [i0, 1] };
+; CHECK-NEXT:         ReadAccess :=	[Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_body_b[i0] -> MemRef_A[0] };
+; CHECK-NEXT:         ReadAccess :=	[Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_body_b[i0] -> MemRef_B[0] };
+; CHECK-NEXT:         MustWriteAccess :=	[Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_body_b[i0] -> MemRef_A[0] };
+; CHECK-NEXT:         MustWriteAccess :=	[Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_body_b[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: }