[ScopBuilder] Skip getting leader when merging statements to close holes.
Function joinOrderedInstructions merges instructions when a leader is encountered twice.
It also notices that leaders in SeenLeaders may lose their leadership in previous merging,
and tries to handle the case using following code:
Instruction *PrevLeader = UnionFind.getLeaderValue(SeenLeaders.back());
However, this is wrong because it always gets leader for the last element of SeenLeaders,
and I believe it's wrong even we get leader for Prev here. As a result, Statements in cases
like the one in patch aren't merged as expected. After investigation, I believe it's
unnecessary to get leader instruction at all. This is based on fact: Although leaders in
SeenLeaders could lose leadership, they only lose to others in SeenLeaders, in other words,
one existing leader will be chosen as new leader of merged equivalent statements. We can
take advantage of this and simply check if current leader equals to Prev and break merging
if it does.
The patch also adds a new test.
Patch by bin.narwal <bin.narwal@gmail.com>
Differential Revision: https://reviews.llvm.org/D67007
git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@371801 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/ScopBuilder.cpp b/lib/Analysis/ScopBuilder.cpp
index 29f27f2..554e9a8 100644
--- a/lib/Analysis/ScopBuilder.cpp
+++ b/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);
}
diff --git a/test/ScopInfo/granularity_scalar-indep_ordered-2.ll b/test/ScopInfo/granularity_scalar-indep_ordered-2.ll
new file mode 100644
index 0000000..f61c2e6
--- /dev/null
+++ b/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: }
