From 9d0796e5d0346c8444adf59c5dfa338ca2fb3f01 Mon Sep 17 00:00:00 2001
From: Daniel Berlin <dberlin@dberlin.org>
Date: Fri, 24 Mar 2017 05:30:34 +0000
Subject: [PATCH] NewGVN: Fix PR32403 - Handling of undef in phis was not quite
 correct due to LLVM's view of phi nodes.  It would cause NewGVN not to
 fixpoint in some interesting edge cases.

llvm-svn: 298687
---
 llvm/lib/Transforms/Scalar/NewGVN.cpp  | 15 +++++++-
 llvm/test/Transforms/NewGVN/pr32403.ll | 65 ++++++++++++++++++++++++++++++++++
 2 files changed, 79 insertions(+), 1 deletion(-)
 create mode 100644 llvm/test/Transforms/NewGVN/pr32403.ll

diff --git a/llvm/lib/Transforms/Scalar/NewGVN.cpp b/llvm/lib/Transforms/Scalar/NewGVN.cpp
index 5aa8c5c..437f9d1 100644
--- a/llvm/lib/Transforms/Scalar/NewGVN.cpp
+++ b/llvm/lib/Transforms/Scalar/NewGVN.cpp
@@ -368,6 +368,7 @@ private:
   const Expression *performSymbolicPredicateInfoEvaluation(Instruction *);
 
   // Congruence finding.
+  bool someEquivalentDominates(const Instruction *, const Instruction *) const;
   Value *lookupOperandLeader(Value *) const;
   void performCongruenceFinding(Instruction *, const Expression *);
   void moveValueToNewCongruenceClass(Instruction *, CongruenceClass *,
@@ -724,6 +725,18 @@ const CallExpression *NewGVN::createCallExpression(CallInst *CI,
   return E;
 }
 
+// Return true if some equivalent of instruction Inst dominates instruction U.
+bool NewGVN::someEquivalentDominates(const Instruction *Inst,
+                                     const Instruction *U) const {
+  auto *CC = ValueToClass.lookup(Inst);
+  assert(isa<Instruction>(CC->RepLeader) && CC->RepLeader == Inst);
+  if (CC)
+    return llvm::any_of(CC->Members, [&](const Value *Member) {
+      return DT->dominates(cast<Instruction>(Member), U);
+    });
+  return false;
+}
+
 // See if we have a congruence class and leader for this operand, and if so,
 // return it. Otherwise, return the operand itself.
 Value *NewGVN::lookupOperandLeader(Value *V) const {
@@ -1054,7 +1067,7 @@ const Expression *NewGVN::performSymbolicPHIEvaluation(Instruction *I) {
     if (HasUndef) {
       // Only have to check for instructions
       if (auto *AllSameInst = dyn_cast<Instruction>(AllSameValue))
-        if (!DT->dominates(AllSameInst, I))
+        if (!someEquivalentDominates(AllSameInst, I))
           return E;
     }
 
diff --git a/llvm/test/Transforms/NewGVN/pr32403.ll b/llvm/test/Transforms/NewGVN/pr32403.ll
new file mode 100644
index 0000000..2552e0e
--- /dev/null
+++ b/llvm/test/Transforms/NewGVN/pr32403.ll
@@ -0,0 +1,65 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+;RUN: opt -newgvn -S < %s | FileCheck %s
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.12.0"
+
+; Function Attrs: nounwind ssp uwtable
+define void @reorder_ref_pic_list() local_unnamed_addr {
+; CHECK-LABEL: @reorder_ref_pic_list(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 undef, label [[FOR_END:%.*]], label [[FOR_BODY_PREHEADER:%.*]]
+; CHECK:       for.body.preheader:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[REFIDXLX_0:%.*]] = phi i32 [ [[INC_I51:%.*]], [[IF_ELSE58:%.*]] ], [ 0, [[FOR_BODY_PREHEADER]] ]
+; CHECK-NEXT:    br i1 undef, label [[IF_THEN13:%.*]], label [[IF_ELSE58]]
+; CHECK:       if.then13:
+; CHECK-NEXT:    [[INC_I:%.*]] = add nsw i32 [[REFIDXLX_0]], 1
+; CHECK-NEXT:    br label [[FOR_BODY8_I:%.*]]
+; CHECK:       for.body8.i:
+; CHECK-NEXT:    br i1 undef, label [[FOR_INC24_I:%.*]], label [[IF_THEN17_I:%.*]]
+; CHECK:       if.then17.i:
+; CHECK-NEXT:    br label [[FOR_INC24_I]]
+; CHECK:       for.inc24.i:
+; CHECK-NEXT:    br label [[FOR_BODY8_I]]
+; CHECK:       if.else58:
+; CHECK-NEXT:    [[INC_I51]] = add nsw i32 [[REFIDXLX_0]], 1
+; CHECK-NEXT:    br label [[FOR_BODY]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 undef, label %for.end, label %for.body.preheader
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.body:                                         ; preds = %if.else58, %for.body.preheader
+  %refIdxLX.0 = phi i32 [ %inc.i51, %if.else58 ], [ 0, %for.body.preheader ]
+  br i1 undef, label %if.then13, label %if.else58
+
+if.then13:                                        ; preds = %for.body
+  %inc.i = add nsw i32 %refIdxLX.0, 1
+  br label %for.body8.i
+
+for.body8.i:                                      ; preds = %for.inc24.i, %if.then13
+  %nIdx.052.i = phi i32 [ %inc.i, %if.then13 ], [ %nIdx.1.i, %for.inc24.i ]
+  br i1 undef, label %for.inc24.i, label %if.then17.i
+
+if.then17.i:                                      ; preds = %for.body8.i
+  br label %for.inc24.i
+
+for.inc24.i:                                      ; preds = %if.then17.i, %for.body8.i
+  %nIdx.1.i = phi i32 [ undef, %if.then17.i ], [ %nIdx.052.i, %for.body8.i ]
+  br label %for.body8.i
+
+if.else58:                                        ; preds = %for.body
+  %inc.i51 = add nsw i32 %refIdxLX.0, 1
+  br label %for.body
+
+for.end:                                          ; preds = %entry
+  ret void
+}
+
+
+
-- 
2.7.4