From f47b8f1cd16220afddaa8cf3d0e69a4ba2a2bd17 Mon Sep 17 00:00:00 2001
From: Daniel Berlin <dberlin@dberlin.org>
Date: Tue, 11 Apr 2017 00:07:26 +0000
Subject: [PATCH] Revert "NewGVN: Don't propagate over phi backedges where
 undef causes us to have >1 value." It's not ready yet this was an accidental
 commit :(

This reverts r299903

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@299904 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/Scalar/NewGVN.cpp | 34 ++++++----------------------------
 1 file changed, 6 insertions(+), 28 deletions(-)

diff --git a/lib/Transforms/Scalar/NewGVN.cpp b/lib/Transforms/Scalar/NewGVN.cpp
index cd44a77f6fa..1e6692482bd 100644
--- a/lib/Transforms/Scalar/NewGVN.cpp
+++ b/lib/Transforms/Scalar/NewGVN.cpp
@@ -334,9 +334,6 @@ class NewGVN {
   // Number of function arguments, used by ranking
   unsigned int NumFuncArgs;
 
-  // RPOOrdering of basic blocks
-  DenseMap<const DomTreeNode *, unsigned> RPOOrdering;
-
   // Congruence class info.
 
   // This class is called INITIAL in the paper. It is the class everything
@@ -435,7 +432,7 @@ private:
   // Expression handling.
   const Expression *createExpression(Instruction *);
   const Expression *createBinaryExpression(unsigned, Type *, Value *, Value *);
-  PHIExpression *createPHIExpression(Instruction *, bool&);
+  PHIExpression *createPHIExpression(Instruction *);
   const VariableExpression *createVariableExpression(Value *);
   const ConstantExpression *createConstantExpression(Constant *);
   const Expression *createVariableOrConstant(Value *V);
@@ -630,8 +627,7 @@ void NewGVN::deleteExpression(const Expression *E) {
   ExpressionAllocator.Deallocate(E);
 }
 
-PHIExpression *NewGVN::createPHIExpression(Instruction *I,
-                                           bool &HasBackedge) {
+PHIExpression *NewGVN::createPHIExpression(Instruction *I) {
   BasicBlock *PHIBlock = I->getParent();
   auto *PN = cast<PHINode>(I);
   auto *E =
@@ -641,8 +637,6 @@ PHIExpression *NewGVN::createPHIExpression(Instruction *I,
   E->setType(I->getType());
   E->setOpcode(I->getOpcode());
 
-  unsigned PHIRPO = RPOOrdering.lookup(DT->getNode(PHIBlock));
-
   // Filter out unreachable phi operands.
   auto Filtered = make_filter_range(PN->operands(), [&](const Use &U) {
     return ReachableEdges.count({PN->getIncomingBlock(U), PHIBlock});
@@ -650,11 +644,6 @@ PHIExpression *NewGVN::createPHIExpression(Instruction *I,
 
   std::transform(Filtered.begin(), Filtered.end(), op_inserter(E),
                  [&](const Use &U) -> Value * {
-                   auto *BB = PN->getIncomingBlock(U);
-                   auto *DTN = DT->getNode(BB);
-                   if (RPOOrdering.lookup(DTN) >= PHIRPO)
-                     HasBackedge = true;
-
                    // Don't try to transform self-defined phis.
                    if (U == PN)
                      return PN;
@@ -1326,8 +1315,7 @@ bool NewGVN::setMemoryClass(const MemoryAccess *From,
 
 // Evaluate PHI nodes symbolically, and create an expression result.
 const Expression *NewGVN::performSymbolicPHIEvaluation(Instruction *I) {
-  bool HasBackedge = false;
-  auto *E = cast<PHIExpression>(createPHIExpression(I, HasBackedge));
+  auto *E = cast<PHIExpression>(createPHIExpression(I));
   // We match the semantics of SimplifyPhiNode from InstructionSimplify here.
 
   // See if all arguaments are the same.
@@ -1349,12 +1337,10 @@ const Expression *NewGVN::performSymbolicPHIEvaluation(Instruction *I) {
     deleteExpression(E);
     return createConstantExpression(UndefValue::get(I->getType()));
   }
-  unsigned NumOps = 0;
   Value *AllSameValue = *(Filtered.begin());
   ++Filtered.begin();
   // Can't use std::equal here, sadly, because filter.begin moves.
-  if (llvm::all_of(Filtered, [AllSameValue, &NumOps](const Value *V) {
-        ++NumOps;
+  if (llvm::all_of(Filtered, [AllSameValue](const Value *V) {
         return V == AllSameValue;
       })) {
     // In LLVM's non-standard representation of phi nodes, it's possible to have
@@ -1367,15 +1353,6 @@ const Expression *NewGVN::performSymbolicPHIEvaluation(Instruction *I) {
     // We also special case undef, so that if we have an undef, we can't use the
     // common value unless it dominates the phi block.
     if (HasUndef) {
-      // If we have undef and at least one other value, this is really a
-      // multivalued phi.  We can't ignore the undef when going over a backedge
-      // unless the value being propagated *is* undef itself.  This is because
-      // if they are all undef, they will not become less undef (and if they
-      // did, we will stop them here).  Note that NumOps does not include the
-      // undef itself.
-      if (HasBackedge && NumOps > 0 && !isa<UndefValue>(AllSameValue))
-        return E;
-
       // Only have to check for instructions
       if (auto *AllSameInst = dyn_cast<Instruction>(AllSameValue))
         if (!someEquivalentDominates(AllSameInst, I))
@@ -2582,6 +2559,7 @@ bool NewGVN::runGVN() {
   // The dominator tree does guarantee that, for a given dom tree node, it's
   // parent must occur before it in the RPO ordering. Thus, we only need to sort
   // the siblings.
+  DenseMap<const DomTreeNode *, unsigned> RPOOrdering;
   ReversePostOrderTraversal<Function *> RPOT(&F);
   unsigned Counter = 0;
   for (auto &B : RPOT) {
@@ -2594,7 +2572,7 @@ bool NewGVN::runGVN() {
     auto *Node = DT->getNode(B);
     if (Node->getChildren().size() > 1)
       std::sort(Node->begin(), Node->end(),
-                [&](const DomTreeNode *A, const DomTreeNode *B) {
+                [&RPOOrdering](const DomTreeNode *A, const DomTreeNode *B) {
                   return RPOOrdering[A] < RPOOrdering[B];
                 });
   }
-- 
2.11.0