[turbofan] Handle collisions properly in value numbering.

src/compiler/value-numbering-reducer.cc

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/compiler/value-numbering-reducer.h"
 
 #include <cstring>
 
 #include "src/base/functional.h"
 #include "src/compiler/node.h"
@@ skipping 70 matching lines @@
         // Have to insert a new entry.
         entries_[i] = node;
         size_++;
 
         // Resize to keep load factor below 1/kCapacityToSizeRatio.
         if (size_ * kCapacityToSizeRatio >= capacity_) Grow();
       }
       DCHECK(size_ * kCapacityToSizeRatio < capacity_);
       return NoChange();
     }
+
     if (entry == node) {
-      return NoChange();
+      // We need to check for a certain class of collisions here. Imagine the
+      // following scenario:
+      //
+      //  1. We insert node1 with op1 and certain inputs at index i.
+      //  2. We insert node2 with op2 and certain inputs at index i+1.
+      //  3. Some other reducer changes node1 to op2 and the inputs from node2.
+      //
+      // Now we are called again to reduce node1, and we would return NoChange
+      // in this case because we find node1 first, but what we should actually
+      // do is return Replace(node2) instead.
+      for (size_t j = (i + 1) & mask;; j = (j + 1) & mask) {
+        Node* entry = entries_[j];
+        if (!entry) {
+          // No collision, {node} is fine.
+          return NoChange();
+        }
+        if (entry->IsDead()) {
+          continue;
+        }
+        if (Equals(entry, node)) {
+          // Overwrite the colliding entry with the actual entry.
+          entries_[i] = entry;
+          return Replace(entry);
+        }
+      }
     }
 
     // Skip dead entries, but remember their indices so we can reuse them.
     if (entry->IsDead()) {
       dead = i;
       continue;
     }
     if (Equals(entry, node)) {
       return Replace(entry);
     }
@@ skipping 27 matching lines @@
         size_++;
         break;
       }
     }
   }
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8