diff --git a/llvm/lib/IR/Instruction.cpp b/llvm/lib/IR/Instruction.cpp
--- a/llvm/lib/IR/Instruction.cpp
+++ b/llvm/lib/IR/Instruction.cpp
@@ -488,7 +488,6 @@
   if (!std::equal(op_begin(), op_end(), I->op_begin()))
     return false;
 
-  // WARNING: this logic must be kept in sync with EliminateDuplicatePHINodes()!
   if (const PHINode *thisPHI = dyn_cast<PHINode>(this)) {
     const PHINode *otherPHI = cast<PHINode>(I);
     return std::equal(thisPHI->block_begin(), thisPHI->block_end(),
diff --git a/llvm/lib/Transforms/Utils/Local.cpp b/llvm/lib/Transforms/Utils/Local.cpp
--- a/llvm/lib/Transforms/Utils/Local.cpp
+++ b/llvm/lib/Transforms/Utils/Local.cpp
@@ -93,17 +93,6 @@
 STATISTIC(NumRemoved, "Number of unreachable basic blocks removed");
 STATISTIC(NumPHICSEs, "Number of PHI's that got CSE'd");
 
-static cl::opt<bool> PHICSEDebugHash(
-    "phicse-debug-hash",
-#ifdef EXPENSIVE_CHECKS
-    cl::init(true),
-#else
-    cl::init(false),
-#endif
-    cl::Hidden,
-    cl::desc("Perform extra assertion checking to verify that PHINodes's hash "
-             "function is well-behaved w.r.t. its isEqual predicate"));
-
 // Max recursion depth for collectBitParts used when detecting bswap and
 // bitreverse idioms
 static const unsigned BitPartRecursionMaxDepth = 64;
@@ -1132,84 +1121,35 @@
   return true;
 }
 
-// WARNING: this logic must be kept in sync with
-//          Instruction::isIdenticalToWhenDefined()!
 bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) {
   // This implementation doesn't currently consider undef operands
   // specially. Theoretically, two phis which are identical except for
   // one having an undef where the other doesn't could be collapsed.
 
-  struct PHIDenseMapInfo {
-    static PHINode *getEmptyKey() {
-      return DenseMapInfo<PHINode *>::getEmptyKey();
-    }
-
-    static PHINode *getTombstoneKey() {
-      return DenseMapInfo<PHINode *>::getTombstoneKey();
-    }
-
-    static bool isSentinel(PHINode *PN) {
-      return PN == getEmptyKey() || PN == getTombstoneKey();
-    }
-
-    static unsigned getHashValueImpl(PHINode *PN) {
-      // Compute a hash value on the operands. Instcombine will likely have
-      // sorted them, which helps expose duplicates, but we have to check all
-      // the operands to be safe in case instcombine hasn't run.
-      return static_cast<unsigned>(hash_combine(
-          hash_combine_range(PN->value_op_begin(), PN->value_op_end()),
-          hash_combine_range(PN->block_begin(), PN->block_end())));
-    }
-
-    static unsigned getHashValue(PHINode *PN) {
-#ifndef NDEBUG
-      // If -phicse-debug-hash was specified, return a constant -- this
-      // will force all hashing to collide, so we'll exhaustively search
-      // the table for a match, and the assertion in isEqual will fire if
-      // there's a bug causing equal keys to hash differently.
-      if (PHICSEDebugHash)
-        return 0;
-#endif
-      return getHashValueImpl(PN);
-    }
-
-    static bool isEqualImpl(PHINode *LHS, PHINode *RHS) {
-      if (isSentinel(LHS) || isSentinel(RHS))
-        return LHS == RHS;
-      return LHS->isIdenticalTo(RHS);
-    }
-
-    static bool isEqual(PHINode *LHS, PHINode *RHS) {
-      // These comparisons are nontrivial, so assert that equality implies
-      // hash equality (DenseMap demands this as an invariant).
-      bool Result = isEqualImpl(LHS, RHS);
-      assert(!Result || (isSentinel(LHS) && LHS == RHS) ||
-             getHashValueImpl(LHS) == getHashValueImpl(RHS));
-      return Result;
-    }
-  };
-
-  // Set of unique PHINodes.
-  DenseSet<PHINode *, PHIDenseMapInfo> PHISet;
+  bool Changed = false;
 
   // Examine each PHI.
-  bool Changed = false;
-  for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I++);) {
-    auto Inserted = PHISet.insert(PN);
-    if (!Inserted.second) {
-      // A duplicate. Replace this PHI with its duplicate.
+  // Note that increment of I must *NOT* be in the iteration_expression, since
+  // we don't want to immediately advance when we restart from the beginning.
+  for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I);) {
+    ++I;
+    // Is there an identical PHI node in this basic block?
+    // Note that we only look in the upper square's triangle,
+    // we already checked that the lower triangle PHI's aren't identical.
+    for (auto J = I; PHINode *DuplicatePN = dyn_cast<PHINode>(J); ++J) {
+      if (!DuplicatePN->isIdenticalToWhenDefined(PN))
+        continue;
+      // A duplicate. Replace this PHI with the base PHI.
       ++NumPHICSEs;
-      PN->replaceAllUsesWith(*Inserted.first);
-      PN->eraseFromParent();
+      DuplicatePN->replaceAllUsesWith(PN);
+      DuplicatePN->eraseFromParent();
       Changed = true;
 
-      // The RAUW can change PHIs that we already visited. Start over from the
-      // beginning.
-      PHISet.clear();
+      // The RAUW can change PHIs that we already visited.
       I = BB->begin();
+      break; // Start over from the beginning.
     }
   }
-
   return Changed;
 }