dart2js cps: Add more constraint rules to bounds-check elimination.

dart2js cps: Add more constraint rules to bounds-check elimination.

The sign of a +/- operation is computed, which can help in cases where
the result could not be proven to be within 53-bit range.

Also added rules for ~/, %, >>, &, and unary negation operators.

BUG=
R=sra@google.com

Committed: https://github.com/dart-lang/sdk/commit/ab37dac248ecdb49a28ec6bb057c11e046d8be29

[asgerf, 2015-11-27 15:10:29]

Patchset #2 (id:20001) has been deleted

[asgerf, 2015-11-27 15:23:05]

asgerf@google.com changed reviewers:
+ sra@google.com

[sra1, 2015-11-27 20:28:22]

https://codereview.chromium.org/1479193002/diff/1/pkg/compiler/lib/src/cps_ir...
File pkg/compiler/lib/src/cps_ir/bounds_checker.dart (right):

https://codereview.chromium.org/1479193002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/bounds_checker.dart:417: }
Also:  x >> k  <=  MAX_UINT32 >> k

Base64(De|En)coder contains  s.codeUnitAt(... >> 18)
which is in bounds since s.length == 64.

https://codereview.chromium.org/1479193002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/bounds_checker.dart:423: //   Should we do the
rewrite here?
We would want to do the check on InvokeMethod to see if we can rewrite to  a
builtin.

https://codereview.chromium.org/1479193002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/bounds_checker.dart:424: if
(isDefinitelyGreaterThanOrEqualToConstant(leftVar, 0) &&
We do this test a lot. How many steps does it take?
If we stored min/max on some of the variables, that would be a fast cache of the
information already derived from the type or constant value.

https://codereview.chromium.org/1479193002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/bounds_checker.dart:451: }
~x  == MAX_UINT32 - x,  if x is uint32.

Not sure we will learn anything useful.

[asgerf, 2015-11-30 13:46:03]

https://codereview.chromium.org/1479193002/diff/1/pkg/compiler/lib/src/cps_ir...
File pkg/compiler/lib/src/cps_ir/bounds_checker.dart (right):

https://codereview.chromium.org/1479193002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/bounds_checker.dart:417: }
On 2015/11/27 20:28:21, sra1 wrote:
> Also:  x >> k  <=  MAX_UINT32 >> k
> 
> Base64(De|En)coder contains  s.codeUnitAt(... >> 18)
> which is in bounds since s.length == 64.

Done.

https://codereview.chromium.org/1479193002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/bounds_checker.dart:423: //   Should we do the
rewrite here?
On 2015/11/27 20:28:21, sra1 wrote:
> We would want to do the check on InvokeMethod to see if we can rewrite to  a
> builtin.

My point was we could consider doing the rewriting in this pass.

https://codereview.chromium.org/1479193002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/bounds_checker.dart:424: if
(isDefinitelyGreaterThanOrEqualToConstant(leftVar, 0) &&
On 2015/11/27 20:28:21, sra1 wrote:
> We do this test a lot. How many steps does it take?
> If we stored min/max on some of the variables, that would be a fast cache of
the
> information already derived from the type or constant value.

The bounds checker is a bit wasteful like this, but so far when I have tried to
remove the redundant checks I cannot measure the difference afterwards. There
are just not enough of these operators for this to have a measurable impact on
the benchmark suite.

But we can do better.  I'll do some more rigorous performance testing and get
back to you.

https://codereview.chromium.org/1479193002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/bounds_checker.dart:451: }
On 2015/11/27 20:28:21, sra1 wrote:
> ~x  == MAX_UINT32 - x,  if x is uint32.
> 
> Not sure we will learn anything useful.

Seems really unlikely to make a difference.

Connecting variables comes at a cost since it might connect two otherwise
disconnected sets of variables, making graph searches slower.

[sra1, 2015-12-01 01:03:39]

lgtm

[asgerf, 2015-12-01 16:19:35]

https://codereview.chromium.org/1479193002/diff/1/pkg/compiler/lib/src/cps_ir...
File pkg/compiler/lib/src/cps_ir/bounds_checker.dart (right):

https://codereview.chromium.org/1479193002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/bounds_checker.dart:424: if
(isDefinitelyGreaterThanOrEqualToConstant(leftVar, 0) &&
On 2015/11/30 13:46:03, asgerf wrote:
> On 2015/11/27 20:28:21, sra1 wrote:
> > We do this test a lot. How many steps does it take?
> > If we stored min/max on some of the variables, that would be a fast cache of
> the
> > information already derived from the type or constant value.
> 
> The bounds checker is a bit wasteful like this, but so far when I have tried
to
> remove the redundant checks I cannot measure the difference afterwards. There
> are just not enough of these operators for this to have a measurable impact on
> the benchmark suite.
> 
> But we can do better.  I'll do some more rigorous performance testing and get
> back to you.

I made unary checks a bit faster with a special case in the octagon domain.
Caching the min/max or just checking for uint32 directly didn't seem to have
much impact, though.

[asgerf, 2015-12-01 16:20:20]

Description was changed from

==========
dart2js cps: Add more constraint rules to bounds-check elimination.

The sign of a +/- operation is computed, which can help in cases where
the result could not be proven to be within 53-bit range.

Also added rules for ~/, %, >>, &, and unary negation operators.

BUG=
==========

to

==========
dart2js cps: Add more constraint rules to bounds-check elimination.

The sign of a +/- operation is computed, which can help in cases where
the result could not be proven to be within 53-bit range.

Also added rules for ~/, %, >>, &, and unary negation operators.

BUG=
R=sra@google.com

Committed:
https://github.com/dart-lang/sdk/commit/ab37dac248ecdb49a28ec6bb057c11e046d8be29
==========

[asgerf, 2015-12-01 16:20:21]

Committed patchset #4 (id:80001) manually as
ab37dac248ecdb49a28ec6bb057c11e046d8be29 (presubmit successful).