[turbofan] Bidirectional representation inference.

[turbofan] Bidirectional representation inference.

This changes representation inference to be bidirectional:
1. truncations are propagated from uses to definitions.
2. output types are propagated from definitions to uses.
(and nodes are revisited until fixpoint.)

At the moment, (2) is used only superficially; the idea here is to
use the output type propagation to propagate types from type feedback.

For the output types to be usable, we need to keep track of the type
of the JavaScript value rather than the truncated value. Otherwise,
representation inference could not rely on the ranges indicated
by the values.

For example, for "var b = (a|0) + (a|0); return (b/16) >>> 0",
the type of b cannot be int32; otherwise the division "b/16"
would believe that it is fine to do an integer division on
the truncated value, which would give a wrong result for
2^31 <= a < 2^32.

The change makes representation inference a bit more expensive
(the phase is about 20% slower), but since this is only small part
of the overall compiler time, the overall effect is negligible.
If the running time becomes a problem, we could optimize this by
remembering when the nodes are stable (ie., no further changes to
type/truncations) and/or explicit subscriptions for changes.

BUG=v8:4583
R=bmeurer@chromium.org
LOG=N

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

[Jarin, 2015-12-01 12:40:06]

Description was changed from

==========
[turbofan] Bidirectional representation inference.

This changes representation inference to be bidirectional:
1. truncations are propagated from uses to definitions.
2. output types are propagated from definitions to uses.
(and nodes are revisited until fixpoint.)

At the moment, (2) is used only superficially; the idea here is to
use the output type propagation to propagate types from type feedback.

For the output types to be usable, we need to keep track of the type
of the JavaScript value rather than the truncated value. Otherwise,
representation inference could not rely on the ranges indicated
by the values.

For example, for "var b = (a|0) + (a|0); return (b/16) >>> 0",
the type of b cannot be int32; otherwise the division "b/16"
would believe that it is fine to do an integer division on
the truncated value, which would give a wrong result for
2^31 <= a < 2^32.

BUG=v8:4583
R=bmeurer@chromium.org
LOG=N
==========

to

==========
[turbofan] Bidirectional representation inference.

This changes representation inference to be bidirectional:
1. truncations are propagated from uses to definitions.
2. output types are propagated from definitions to uses.
(and nodes are revisited until fixpoint.)

At the moment, (2) is used only superficially; the idea here is to
use the output type propagation to propagate types from type feedback.

For the output types to be usable, we need to keep track of the type
of the JavaScript value rather than the truncated value. Otherwise,
representation inference could not rely on the ranges indicated
by the values.

For example, for "var b = (a|0) + (a|0); return (b/16) >>> 0",
the type of b cannot be int32; otherwise the division "b/16"
would believe that it is fine to do an integer division on
the truncated value, which would give a wrong result for
2^31 <= a < 2^32.

The change makes representation inference a bit more expensive (the phase is
about 20% slower),
but since this is only small part of the overall compiler time, the overall
effect is negligible.
If the running time is trouble, we could optimize this by remembering when the
nodes are stable (ie.,
no further changes to type/truncations) and/or explicit subscriptions for
changes.

BUG=v8:4583
R=bmeurer@chromium.org
LOG=N
==========

[Jarin, 2015-12-01 12:40:47]

Description was changed from

==========
[turbofan] Bidirectional representation inference.

This changes representation inference to be bidirectional:
1. truncations are propagated from uses to definitions.
2. output types are propagated from definitions to uses.
(and nodes are revisited until fixpoint.)

At the moment, (2) is used only superficially; the idea here is to
use the output type propagation to propagate types from type feedback.

For the output types to be usable, we need to keep track of the type
of the JavaScript value rather than the truncated value. Otherwise,
representation inference could not rely on the ranges indicated
by the values.

For example, for "var b = (a|0) + (a|0); return (b/16) >>> 0",
the type of b cannot be int32; otherwise the division "b/16"
would believe that it is fine to do an integer division on
the truncated value, which would give a wrong result for
2^31 <= a < 2^32.

The change makes representation inference a bit more expensive (the phase is
about 20% slower),
but since this is only small part of the overall compiler time, the overall
effect is negligible.
If the running time is trouble, we could optimize this by remembering when the
nodes are stable (ie.,
no further changes to type/truncations) and/or explicit subscriptions for
changes.

BUG=v8:4583
R=bmeurer@chromium.org
LOG=N
==========

to

==========
[turbofan] Bidirectional representation inference.

This changes representation inference to be bidirectional:
1. truncations are propagated from uses to definitions.
2. output types are propagated from definitions to uses.
(and nodes are revisited until fixpoint.)

At the moment, (2) is used only superficially; the idea here is to
use the output type propagation to propagate types from type feedback.

For the output types to be usable, we need to keep track of the type
of the JavaScript value rather than the truncated value. Otherwise,
representation inference could not rely on the ranges indicated
by the values.

For example, for "var b = (a|0) + (a|0); return (b/16) >>> 0",
the type of b cannot be int32; otherwise the division "b/16"
would believe that it is fine to do an integer division on
the truncated value, which would give a wrong result for
2^31 <= a < 2^32.

The change makes representation inference a bit more expensive 
(the phase is about 20% slower), but since this is only small part
of the overall compiler time, the overall effect is negligible.
If the running time is trouble, we could optimize this by remembering
when the nodes are stable (ie., no further changes to 
type/truncations) and/or explicit subscriptions for changes.

BUG=v8:4583
R=bmeurer@chromium.org
LOG=N
==========

[Jarin, 2015-12-01 12:41:36]

Description was changed from

==========
[turbofan] Bidirectional representation inference.

This changes representation inference to be bidirectional:
1. truncations are propagated from uses to definitions.
2. output types are propagated from definitions to uses.
(and nodes are revisited until fixpoint.)

At the moment, (2) is used only superficially; the idea here is to
use the output type propagation to propagate types from type feedback.

For the output types to be usable, we need to keep track of the type
of the JavaScript value rather than the truncated value. Otherwise,
representation inference could not rely on the ranges indicated
by the values.

For example, for "var b = (a|0) + (a|0); return (b/16) >>> 0",
the type of b cannot be int32; otherwise the division "b/16"
would believe that it is fine to do an integer division on
the truncated value, which would give a wrong result for
2^31 <= a < 2^32.

The change makes representation inference a bit more expensive 
(the phase is about 20% slower), but since this is only small part
of the overall compiler time, the overall effect is negligible.
If the running time is trouble, we could optimize this by remembering
when the nodes are stable (ie., no further changes to 
type/truncations) and/or explicit subscriptions for changes.

BUG=v8:4583
R=bmeurer@chromium.org
LOG=N
==========

to

==========
[turbofan] Bidirectional representation inference.

This changes representation inference to be bidirectional:
1. truncations are propagated from uses to definitions.
2. output types are propagated from definitions to uses.
(and nodes are revisited until fixpoint.)

At the moment, (2) is used only superficially; the idea here is to
use the output type propagation to propagate types from type feedback.

For the output types to be usable, we need to keep track of the type
of the JavaScript value rather than the truncated value. Otherwise,
representation inference could not rely on the ranges indicated
by the values.

For example, for "var b = (a|0) + (a|0); return (b/16) >>> 0",
the type of b cannot be int32; otherwise the division "b/16"
would believe that it is fine to do an integer division on
the truncated value, which would give a wrong result for
2^31 <= a < 2^32.

The change makes representation inference a bit more expensive 
(the phase is about 20% slower), but since this is only small part
of the overall compiler time, the overall effect is negligible.
If the running time becomes a problem, we could optimize this by 
remembering when the nodes are stable (ie., no further changes to 
type/truncations) and/or explicit subscriptions for changes.

BUG=v8:4583
R=bmeurer@chromium.org
LOG=N
==========

[Jarin, 2015-12-01 12:42:41]

Could you take a look at this tiny and completely benign change?

[Benedikt Meurer, 2015-12-01 13:26:38]

I'm not sure about this commit. For the purpose mentioned in the description
it's LGTM, but I'm not sure we actually need it (yet).

[Jarin, 2015-12-01 13:50:12]

On 2015/12/01 13:26:38, Benedikt Meurer wrote:
> I'm not sure about this commit. For the purpose mentioned in the description
> it's LGTM, but I'm not sure we actually need it (yet).

Yeah, I think I am not landing it just yet. First, we should see what we get if
we just try to use the feedback and then see whether we can improve on this with
some representation inference technology.

[Jarin, 2016-01-05 10:56:17]

The CQ bit was checked by jarin@chromium.org

[Jarin, 2016-01-05 10:56:17]

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/1490763003/#ps20001
(title: "Rebase")

[commit-bot: I haz the power, 2016-01-05 10:56:28]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1490763003/20001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1490763003/20001

[Jarin, 2016-01-05 10:56:48]

The CQ bit was unchecked by jarin@chromium.org

[Jarin, 2016-01-05 10:57:31]

The CQ bit was checked by jarin@chromium.org

[Jarin, 2016-01-05 10:57:31]

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/1490763003/#ps40001
(title: "Rebase")

[commit-bot: I haz the power, 2016-01-05 10:57:39]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1490763003/40001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1490763003/40001

[commit-bot: I haz the power, 2016-01-05 11:56:07]

Description was changed from

==========
[turbofan] Bidirectional representation inference.

This changes representation inference to be bidirectional:
1. truncations are propagated from uses to definitions.
2. output types are propagated from definitions to uses.
(and nodes are revisited until fixpoint.)

At the moment, (2) is used only superficially; the idea here is to
use the output type propagation to propagate types from type feedback.

For the output types to be usable, we need to keep track of the type
of the JavaScript value rather than the truncated value. Otherwise,
representation inference could not rely on the ranges indicated
by the values.

For example, for "var b = (a|0) + (a|0); return (b/16) >>> 0",
the type of b cannot be int32; otherwise the division "b/16"
would believe that it is fine to do an integer division on
the truncated value, which would give a wrong result for
2^31 <= a < 2^32.

The change makes representation inference a bit more expensive 
(the phase is about 20% slower), but since this is only small part
of the overall compiler time, the overall effect is negligible.
If the running time becomes a problem, we could optimize this by 
remembering when the nodes are stable (ie., no further changes to 
type/truncations) and/or explicit subscriptions for changes.

BUG=v8:4583
R=bmeurer@chromium.org
LOG=N
==========

to

==========
[turbofan] Bidirectional representation inference.

This changes representation inference to be bidirectional:
1. truncations are propagated from uses to definitions.
2. output types are propagated from definitions to uses.
(and nodes are revisited until fixpoint.)

At the moment, (2) is used only superficially; the idea here is to
use the output type propagation to propagate types from type feedback.

For the output types to be usable, we need to keep track of the type
of the JavaScript value rather than the truncated value. Otherwise,
representation inference could not rely on the ranges indicated
by the values.

For example, for "var b = (a|0) + (a|0); return (b/16) >>> 0",
the type of b cannot be int32; otherwise the division "b/16"
would believe that it is fine to do an integer division on
the truncated value, which would give a wrong result for
2^31 <= a < 2^32.

The change makes representation inference a bit more expensive 
(the phase is about 20% slower), but since this is only small part
of the overall compiler time, the overall effect is negligible.
If the running time becomes a problem, we could optimize this by 
remembering when the nodes are stable (ie., no further changes to 
type/truncations) and/or explicit subscriptions for changes.

BUG=v8:4583
R=bmeurer@chromium.org
LOG=N
==========

[commit-bot: I haz the power, 2016-01-05 11:56:08]

Committed patchset #3 (id:40001)

[commit-bot: I haz the power, 2016-01-05 11:56:47]

Description was changed from

==========
[turbofan] Bidirectional representation inference.

This changes representation inference to be bidirectional:
1. truncations are propagated from uses to definitions.
2. output types are propagated from definitions to uses.
(and nodes are revisited until fixpoint.)

At the moment, (2) is used only superficially; the idea here is to
use the output type propagation to propagate types from type feedback.

For the output types to be usable, we need to keep track of the type
of the JavaScript value rather than the truncated value. Otherwise,
representation inference could not rely on the ranges indicated
by the values.

For example, for "var b = (a|0) + (a|0); return (b/16) >>> 0",
the type of b cannot be int32; otherwise the division "b/16"
would believe that it is fine to do an integer division on
the truncated value, which would give a wrong result for
2^31 <= a < 2^32.

The change makes representation inference a bit more expensive 
(the phase is about 20% slower), but since this is only small part
of the overall compiler time, the overall effect is negligible.
If the running time becomes a problem, we could optimize this by 
remembering when the nodes are stable (ie., no further changes to 
type/truncations) and/or explicit subscriptions for changes.

BUG=v8:4583
R=bmeurer@chromium.org
LOG=N
==========

to

==========
[turbofan] Bidirectional representation inference.

This changes representation inference to be bidirectional:
1. truncations are propagated from uses to definitions.
2. output types are propagated from definitions to uses.
(and nodes are revisited until fixpoint.)

At the moment, (2) is used only superficially; the idea here is to
use the output type propagation to propagate types from type feedback.

For the output types to be usable, we need to keep track of the type
of the JavaScript value rather than the truncated value. Otherwise,
representation inference could not rely on the ranges indicated
by the values.

For example, for "var b = (a|0) + (a|0); return (b/16) >>> 0",
the type of b cannot be int32; otherwise the division "b/16"
would believe that it is fine to do an integer division on
the truncated value, which would give a wrong result for
2^31 <= a < 2^32.

The change makes representation inference a bit more expensive
(the phase is about 20% slower), but since this is only small part
of the overall compiler time, the overall effect is negligible.
If the running time becomes a problem, we could optimize this by
remembering when the nodes are stable (ie., no further changes to
type/truncations) and/or explicit subscriptions for changes.

BUG=v8:4583
R=bmeurer@chromium.org
LOG=N

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

[commit-bot: I haz the power, 2016-01-05 11:56:48]

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