Skip to content

Fix CSE hash collision in value numbering#581

Open
eric wants to merge 1 commit intogorgonia:masterfrom
fancybits:fix-cse-hash-collision
Open

Fix CSE hash collision in value numbering#581
eric wants to merge 1 commit intogorgonia:masterfrom
fancybits:fix-cse-hash-collision

Conversation

@eric
Copy link
Copy Markdown

@eric eric commented Mar 15, 2026

The value numbering function vn() used only the 32-bit FNV hash to determine if two nodes are equivalent for common subexpression elimination. When two different nodes had a hash collision, the second node was incorrectly treated as a duplicate of the first, causing it to share the first node's register and interval. This led to the wrong value being read at execution time.

For example, a slice op producing shape (1,1,5) could hash-collide with a MatMul producing shape (10000,1). The MatMul would be treated as equivalent to the slice op, and any consumer of the MatMul would read the slice op's value instead.

The fix adds a nodeEq check to verify actual equivalence before declaring a CSE match, consistent with how ExprGraph.AddNode already handles hash collisions.

The value numbering function vn() used only the 32-bit FNV hash to
determine if two nodes are equivalent for common subexpression
elimination. When two different nodes had a hash collision, the second
node was incorrectly treated as a duplicate of the first, causing it
to share the first node's register and interval. This led to the
wrong value being read at execution time.

For example, a slice op producing shape (1,1,5) could hash-collide
with a MatMul producing shape (10000,1). The MatMul would be treated
as equivalent to the slice op, and any consumer of the MatMul would
read the slice op's value instead.

The fix adds a nodeEq check to verify actual equivalence before
declaring a CSE match, consistent with how ExprGraph.AddNode already
handles hash collisions.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant