Reviewers: Sven Panne,
Description:
[turbofan] Handle collisions properly in value numbering.
[email protected]
Please review this at https://codereview.chromium.org/795433003/
Base URL: https://chromium.googlesource.com/v8/v8.git@master
Affected files (+26, -1 lines):
M src/compiler/value-numbering-reducer.cc
Index: src/compiler/value-numbering-reducer.cc
diff --git a/src/compiler/value-numbering-reducer.cc
b/src/compiler/value-numbering-reducer.cc
index
f4cf1d486266c2331fe95e39deb4dbc9130b4c74..734b3e8e8ee870f04b500e2f784849d95dd77505
100644
--- a/src/compiler/value-numbering-reducer.cc
+++ b/src/compiler/value-numbering-reducer.cc
@@ -88,8 +88,33 @@ Reduction ValueNumberingReducer::Reduce(Node* node) {
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.
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
