[turbofan] Do not replace actual duplicates when value numbering

[turbofan] Do not replace actual duplicates when value numbering

The value numbering reducer has collision checks for nodes that mutated,
but kept the same hash, and are now equivalent to another node. However,
it can also accidentally hit itself, if it mutated, changed hash, but
ran over the location it was previously in.

After this patch, it checks to see if it is comparing against itself,
and skips over itself. Additionally, if this check is at the end of the
collisions, it opportunistically removes the duplicate entry and reduces
the size pressure on the list. We can do the same opportunistic clean up
if we happen to find a colliding equivalent entry, since we move it from
its original position to a new one.

Drive-by change: Ensure that the collision replacement checks types in
the same way that normal replacement does.

Committed: https://crrev.com/b7761100e367af60411e1f0cb1519d815d1959ce
Cr-Commit-Position: refs/heads/master@{#40757}

[Leszek Swirski, 2016-11-03 14:01:20]

The CQ bit was checked by leszeks@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-11-03 14:01:36]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-11-03 14:24:45]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-11-03 14:24:46]

Dry run: This issue passed the CQ dry run.

[Leszek Swirski, 2016-11-03 14:52:54]

leszeks@chromium.org changed reviewers:
+ bmeurer@chromium.org, jarin@chromium.org

[Leszek Swirski, 2016-11-03 14:52:54]

Hi Benedikt and Jaro,

I noticed this happening occasionally in a couple of the larger benchmarks.
Could you take a look and see if this is a correct/sane change? It makes sense
to me but I may be missing something.

@Jaro, could you also advise whether we should be doing the type checking in the
collision loop, same as we do for the normal path?

[Benedikt Meurer, 2016-11-03 16:12:54]

LGTM.

[Jarin, 2016-11-04 10:03:15]

On 2016/11/03 14:52:54, Leszek Swirski wrote:
> Hi Benedikt and Jaro,
> 
> I noticed this happening occasionally in a couple of the larger benchmarks.
> Could you take a look and see if this is a correct/sane change? It makes sense
> to me but I may be missing something.
> 
> @Jaro, could you also advise whether we should be doing the type checking in
the
> collision loop, same as we do for the normal path?

Yeah, I think we should do the type checking. Good catch.

[Leszek Swirski, 2016-11-04 10:13:23]

The CQ bit was checked by leszeks@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-11-04 10:13:33]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[Leszek Swirski, 2016-11-04 10:15:05]

Description was changed from

==========
[turbofan] Do not replace actual duplicates when value numbering

The value numbering reducer has collision checks for nodes that mutated,
but kept the same hash, and are now equivalent to another node. However,
it can also accidentally hit itself, if it mutated, changed hash, but
ran over the location it was previously in.

After this patch, it checks to see if it is comparing against itself,
and skips over itself. Additionally, if this check is at the end of the
collisions, it opportunistically removes the duplicate entry and reduces
the size pressure on the list. We can do the same opportunistic clean up
if we happen to find a colliding equivalent entry, since we move it from
its original position to a new one.
==========

to

==========
[turbofan] Do not replace actual duplicates when value numbering

The value numbering reducer has collision checks for nodes that mutated,
but kept the same hash, and are now equivalent to another node. However,
it can also accidentally hit itself, if it mutated, changed hash, but
ran over the location it was previously in.

After this patch, it checks to see if it is comparing against itself,
and skips over itself. Additionally, if this check is at the end of the
collisions, it opportunistically removes the duplicate entry and reduces
the size pressure on the list. We can do the same opportunistic clean up
if we happen to find a colliding equivalent entry, since we move it from
its original position to a new one.

Drive-by change: Ensure that the collision replacement checks types in
the same way that normal replacement does.
==========

[Leszek Swirski, 2016-11-04 10:16:56]

leszeks@chromium.org changed required reviewers:
+ jarin@chromium.org

[Leszek Swirski, 2016-11-04 10:16:56]

@Jaro: Cool, done. PTAL, I've marked you down as a required reviewer.

[Jarin, 2016-11-04 10:35:03]

lgtm. Thanks!

[commit-bot: I haz the power, 2016-11-04 10:37:45]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-11-04 10:37:46]

Dry run: This issue passed the CQ dry run.

[Leszek Swirski, 2016-11-04 10:38:10]

The CQ bit was checked by leszeks@chromium.org

[Leszek Swirski, 2016-11-04 10:38:10]

The patchset sent to the CQ was uploaded after l-g-t-m from bmeurer@chromium.org
Link to the patchset: https://codereview.chromium.org/2475653002/#ps20001
(title: "Fix replacement type-check")

[commit-bot: I haz the power, 2016-11-04 10:38:12]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-11-04 10:40:25]

Committed patchset #2 (id:20001)

[commit-bot: I haz the power, 2016-11-17 22:22:23]

Description was changed from

==========
[turbofan] Do not replace actual duplicates when value numbering

The value numbering reducer has collision checks for nodes that mutated,
but kept the same hash, and are now equivalent to another node. However,
it can also accidentally hit itself, if it mutated, changed hash, but
ran over the location it was previously in.

After this patch, it checks to see if it is comparing against itself,
and skips over itself. Additionally, if this check is at the end of the
collisions, it opportunistically removes the duplicate entry and reduces
the size pressure on the list. We can do the same opportunistic clean up
if we happen to find a colliding equivalent entry, since we move it from
its original position to a new one.

Drive-by change: Ensure that the collision replacement checks types in
the same way that normal replacement does.
==========

to

==========
[turbofan] Do not replace actual duplicates when value numbering

The value numbering reducer has collision checks for nodes that mutated,
but kept the same hash, and are now equivalent to another node. However,
it can also accidentally hit itself, if it mutated, changed hash, but
ran over the location it was previously in.

After this patch, it checks to see if it is comparing against itself,
and skips over itself. Additionally, if this check is at the end of the
collisions, it opportunistically removes the duplicate entry and reduces
the size pressure on the list. We can do the same opportunistic clean up
if we happen to find a colliding equivalent entry, since we move it from
its original position to a new one.

Drive-by change: Ensure that the collision replacement checks types in
the same way that normal replacement does.

Committed: https://crrev.com/b7761100e367af60411e1f0cb1519d815d1959ce
Cr-Commit-Position: refs/heads/master@{#40757}
==========

[commit-bot: I haz the power, 2016-11-17 22:22:24]

Patchset 2 (id:??) landed as
https://crrev.com/b7761100e367af60411e1f0cb1519d815d1959ce
Cr-Commit-Position: refs/heads/master@{#40757}