[ScopBuilder] scalar-indep: Fix mutually referencing PHIs.

Two or more PHIs mutually using each other directly or indirectly as
incoming value could cause that a PHI WRITE be added before the PHI READ
(i.e. it overwrites the current incoming value with the next incoming
value before it being read).

Fix by ensuring that the PHI WRITE and PHI READ are in the same statement.

This should fix the miscompile of SingleSource/Benchmark/Misc/whetstone
from the test-suite.

llvm-svn: 324934

3 files changed, 165 insertions, 0 deletions

diff --git a/polly/lib/Analysis/ScopBuilder.cpp b/polly/lib/Analysis/ScopBuilder.cpp
index a04b4dd66fa..aa114527e6c 100644
--- a/polly/lib/Analysis/ScopBuilder.cpp
+++ b/polly/lib/Analysis/ScopBuilder.cpp
@@ -809,6 +809,44 @@ joinOrderedInstructions(EquivalenceClasses<Instruction *> &UnionFind,
   }
 }
 
+/// If the BasicBlock has an edge from itself, ensure that the PHI WRITEs for
+/// the incoming values from this block are executed after the PHI READ.
+///
+/// Otherwise it could overwrite the incoming value from before the BB with the
+/// value for the next execution. This can happen if the PHI WRITE is added to
+/// the statement with the instruction that defines the incoming value (instead
+/// of the last statement of the same BB). To ensure that the PHI READ and WRITE
+/// are in order, we put both into the statement. PHI WRITEs are always executed
+/// after PHI READs when they are in the same statement.
+///
+/// TODO: This is an overpessimization. We only have to ensure that the PHI
+/// WRITE is not put into a statement containing the PHI itself. That could also
+/// be done by
+/// - having all (strongly connected) PHIs in a single statement,
+/// - unite only the PHIs in the operand tree of the PHI WRITE (because it only
+///   has a chance of being lifted before a PHI by being in a statement with a
+///   PHI that comes before in the basic block), or
+/// - when uniting statements, ensure that no (relevant) PHIs are overtaken.
+static void joinOrderedPHIs(EquivalenceClasses<Instruction *> &UnionFind,
+                            ArrayRef<Instruction *> ModeledInsts) {
+  for (Instruction *Inst : ModeledInsts) {
+    PHINode *PHI = dyn_cast<PHINode>(Inst);
+    if (!PHI)
+      continue;
+
+    int Idx = PHI->getBasicBlockIndex(PHI->getParent());
+    if (Idx < 0)
+      continue;
+
+    Instruction *IncomingVal =
+        dyn_cast<Instruction>(PHI->getIncomingValue(Idx));
+    if (!IncomingVal)
+      continue;
+
+    UnionFind.unionSets(PHI, IncomingVal);
+  }
+}
+
 void ScopBuilder::buildEqivClassBlockStmts(BasicBlock *BB) {
   Loop *L = LI.getLoopFor(BB);
 
@@ -835,6 +873,7 @@ void ScopBuilder::buildEqivClassBlockStmts(BasicBlock *BB) {
 
   joinOperandTree(UnionFind, ModeledInsts);
   joinOrderedInstructions(UnionFind, ModeledInsts);
+  joinOrderedPHIs(UnionFind, ModeledInsts);
 
   // The list of instructions for statement (statement represented by the leader
   // instruction). The order of statements instructions is reversed such that
diff --git a/polly/test/ScopInfo/granularity_scalar-indep_cross-referencing-phi1.ll b/polly/test/ScopInfo/granularity_scalar-indep_cross-referencing-phi1.ll
new file mode 100644
index 00000000000..85b499aa2e5
--- /dev/null
+++ b/polly/test/ScopInfo/granularity_scalar-indep_cross-referencing-phi1.ll
@@ -0,0 +1,62 @@
+; RUN: opt %loadPolly -polly-stmt-granularity=scalar-indep -polly-print-instructions -polly-scops -analyze < %s | FileCheck %s -match-full-lines
+;
+; Two PHIs, cross-referencing each other. The PHI READs must be carried-out
+; before the PHI WRITEs to ensure that the value when entering the block is
+; read.
+; This means that either both PHIs have to be in the same statement, or the
+; PHI WRITEs located in a statement after the PHIs.
+;
+; for (int j = 0; j < n; j += 1) {
+;    double valA = 42.0;
+;    double valB = 21.0;
+;
+; body:
+;   double tmp = valA;
+;   valA = valB;
+;   valB = tmp;
+;   A[0] = valA;
+; }
+;
+define void @func(i32 %n, double* noalias nonnull %A) {
+entry:
+  br label %for
+
+for:
+  %j = phi i32 [0, %entry], [%j.inc, %for]
+  %valA = phi double [42.0, %entry], [%valB, %for]
+  %valB = phi double [21.0, %entry], [%valA, %for]
+  store double %valA, double* %A
+  %j.cmp = icmp slt i32 %j, %n
+  %j.inc = add nuw nsw i32 %j, 1
+  br i1 %j.cmp, label %for, label %exit
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK:      Statements {
+; CHECK-NEXT:     Stmt_for
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [n] -> { Stmt_for[i0] : 0 <= i0 <= n; Stmt_for[0] : n < 0 };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [n] -> { Stmt_for[i0] -> [i0] : i0 <= n; Stmt_for[0] -> [0] : n < 0 };
+; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             [n] -> { Stmt_for[i0] -> MemRef_valA__phi[] };
+; CHECK-NEXT:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             [n] -> { Stmt_for[i0] -> MemRef_valA__phi[] };
+; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             [n] -> { Stmt_for[i0] -> MemRef_valB__phi[] };
+; CHECK-NEXT:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             [n] -> { Stmt_for[i0] -> MemRef_valB__phi[] };
+; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_for[i0] -> MemRef_A[0] };
+; CHECK-NEXT:         Instructions {
+; CHECK-NEXT:               %valA = phi double [ 4.200000e+01, %entry ], [ %valB, %for ]
+; CHECK-NEXT:               %valB = phi double [ 2.100000e+01, %entry ], [ %valA, %for ]
+; CHECK-NEXT:               store double %valA, double* %A
+; CHECK-NEXT:         }
+; CHECK-NEXT: }
diff --git a/polly/test/ScopInfo/granularity_scalar-indep_cross-referencing-phi2.ll b/polly/test/ScopInfo/granularity_scalar-indep_cross-referencing-phi2.ll
new file mode 100644
index 00000000000..f792911af29
--- /dev/null
+++ b/polly/test/ScopInfo/granularity_scalar-indep_cross-referencing-phi2.ll
@@ -0,0 +1,64 @@
+; RUN: opt %loadPolly -polly-stmt-granularity=scalar-indep -polly-print-instructions -polly-scops -analyze < %s | FileCheck %s -match-full-lines
+;
+; Two PHIs, cross-referencing each other. The PHI READs must be carried-out
+; before the PHI WRITEs to ensure that the value when entering the block is
+; read.
+; This means that either both PHIs have to be in the same statement, or the
+; PHI WRITEs located in a statement after the PHIs.
+;
+; for (int j = 0; j < n; j += 1) {
+;    double valA = 42.0;
+;    double valB = 21.0;
+;
+; body:
+;   double tmp = valA;
+;   valA = valB;
+;   valB = tmp;
+;   A[0] = valA;
+; }
+;
+define void @func(i32 %n, double* noalias nonnull %A) {
+entry:
+  br label %for
+
+for:
+  %j = phi i32 [0, %entry], [%j.inc, %for]
+  %valA = phi double [42.0, %entry], [%valB, %for]
+  %valB = phi double [21.0, %entry], [%add, %for]
+  store double %valB, double* %A
+  %add = fadd double %valA, 0.1
+  %j.cmp = icmp slt i32 %j, %n
+  %j.inc = add nuw nsw i32 %j, 1
+  br i1 %j.cmp, label %for, label %exit
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK:      Statements {
+; CHECK-NEXT:     Stmt_for
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [n] -> { Stmt_for[i0] : 0 <= i0 <= n; Stmt_for[0] : n < 0 };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [n] -> { Stmt_for[i0] -> [i0] : i0 <= n; Stmt_for[0] -> [0] : n < 0 };
+; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             [n] -> { Stmt_for[i0] -> MemRef_valA__phi[] };
+; CHECK-NEXT:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             [n] -> { Stmt_for[i0] -> MemRef_valA__phi[] };
+; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             [n] -> { Stmt_for[i0] -> MemRef_valB__phi[] };
+; CHECK-NEXT:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             [n] -> { Stmt_for[i0] -> MemRef_valB__phi[] };
+; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_for[i0] -> MemRef_A[0] };
+; CHECK-NEXT:         Instructions {
+; CHECK-NEXT:               %valA = phi double [ 4.200000e+01, %entry ], [ %valB, %for ]
+; CHECK-NEXT:               %valB = phi double [ 2.100000e+01, %entry ], [ %add, %for ]
+; CHECK-NEXT:               store double %valB, double* %A
+; CHECK-NEXT:               %add = fadd double %valA, 1.000000e-01
+; CHECK-NEXT:         }
+; CHECK-NEXT: }