dart2js cps: Fix bug in bounds check elimination.

dart2js cps: Fix bug in bounds check elimination.

The cycle detection assumed that positive-weight cycles could safely be
ignored while searching for a negative-weight cycle, but this broke the
memoization in the DFS.

Do not try to use DFS to find shortest paths in cyclic graphs.

BUG=
R=kmillikin@google.com

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

[asgerf, 2015-11-26 15:58:10]

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

[asgerf, 2015-11-26 15:58:11]

I feel slightly embarrassed that I messed up a shortest path algorithm :-\

[Kevin Millikin (Google), 2015-11-27 10:44:20]

I'm afraid I don't understand the language of constraints well enough (yet) to
understand this change.  Stephen?

https://codereview.chromium.org/1474133002/diff/20001/pkg/compiler/lib/src/cp...
File pkg/compiler/lib/src/cps_ir/octagon.dart (right):

https://codereview.chromium.org/1474133002/diff/20001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/octagon.dart:96: if (_unsolvableCounter == 0 &&
_checkUnsolvable(constraint)) {
Could be:

if (_unsolvableCounter > 0 ||
    _unsolvableCounter == 0 && _checkUnsolvable(constraint)) {
  ++_unsolvableCounter;
}

I find it clearer, mostly because the two conditions are exclusive.

https://codereview.chromium.org/1474133002/diff/20001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/octagon.dart:124: // Constraints are transitively
composed like so:
This is all a bit confusing because of the signs and because constraints are of
the form v1 + v2 <= k.  Clearer:

   v1 + v2 <= k1
  -v2 + v3 <= k2
implies:
   v1 + v3 <= k1 + k2

https://codereview.chromium.org/1474133002/diff/20001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/octagon.dart:130: // We construct a graph such that
the tightest bound on `v1 - v3` is the
We construct a graph such that the tightest bound on `v1 + v3` is the
weight of the shortest path from `v1` to `-v3`.

Is that right?

https://codereview.chromium.org/1474133002/diff/20001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/octagon.dart:133: // Ever constraint `v1 - v2 <= k`
gives rise to two edges:
Ever ==> Every.

Every constraint `v1 + v2 <= k` gives rise to two edges:
    (v1) --k--> (-v2)
    (v2) --k--> (v2)

And that doesn't seem right.

https://codereview.chromium.org/1474133002/diff/20001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/octagon.dart:171: // Two new edges will be added by
the constraint:
For a constraint of the form v1 + v2 <= k?

[Kevin Millikin (Google), 2015-11-27 10:49:51]

lgtm

[asgerf, 2015-11-27 10:50:53]

https://codereview.chromium.org/1474133002/diff/20001/pkg/compiler/lib/src/cp...
File pkg/compiler/lib/src/cps_ir/octagon.dart (right):

https://codereview.chromium.org/1474133002/diff/20001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/octagon.dart:96: if (_unsolvableCounter == 0 &&
_checkUnsolvable(constraint)) {
On 2015/11/27 10:44:19, Kevin Millikin (Google) wrote:
> Could be:
> 
> if (_unsolvableCounter > 0 ||
>     _unsolvableCounter == 0 && _checkUnsolvable(constraint)) {
>   ++_unsolvableCounter;
> }
> 
> I find it clearer, mostly because the two conditions are exclusive.

Done.

https://codereview.chromium.org/1474133002/diff/20001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/octagon.dart:124: // Constraints are transitively
composed like so:
On 2015/11/27 10:44:19, Kevin Millikin (Google) wrote:
> This is all a bit confusing because of the signs and because constraints are
of
> the form v1 + v2 <= k.  Clearer:
> 
>    v1 + v2 <= k1
>   -v2 + v3 <= k2
> implies:
>    v1 + v3 <= k1 + k2

Done.

https://codereview.chromium.org/1474133002/diff/20001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/octagon.dart:130: // We construct a graph such that
the tightest bound on `v1 - v3` is the
On 2015/11/27 10:44:19, Kevin Millikin (Google) wrote:
> We construct a graph such that the tightest bound on `v1 + v3` is the
> weight of the shortest path from `v1` to `-v3`.
> 
> Is that right?

Yep. Updated.

https://codereview.chromium.org/1474133002/diff/20001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/octagon.dart:133: // Ever constraint `v1 - v2 <= k`
gives rise to two edges:
On 2015/11/27 10:44:19, Kevin Millikin (Google) wrote:
> Ever ==> Every.
> 
> Every constraint `v1 + v2 <= k` gives rise to two edges:
>     (v1) --k--> (-v2)
>     (v2) --k--> (v2)
> 
> And that doesn't seem right.

That was a typo in the second one.

https://codereview.chromium.org/1474133002/diff/20001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/octagon.dart:171: // Two new edges will be added by
the constraint:
On 2015/11/27 10:44:19, Kevin Millikin (Google) wrote:
> For a constraint of the form v1 + v2 <= k?

Yes. Done.

[asgerf, 2015-11-27 13:15:33]

Description was changed from

==========
dart2js cps: Fix bug in bounds check elimination.

The cycle detection assumed that positive-weight cycles could safely be
ignored while searching for a negative-weight cycle, but this broke the
memoization in the DFS.

Do not try to use DFS to find shortest paths in cyclic graphs.

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

to

==========
dart2js cps: Fix bug in bounds check elimination.

The cycle detection assumed that positive-weight cycles could safely be
ignored while searching for a negative-weight cycle, but this broke the
memoization in the DFS.

Do not try to use DFS to find shortest paths in cyclic graphs.

BUG=
R=kmillikin@google.com

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

[asgerf, 2015-11-27 13:15:34]

Committed patchset #3 (id:40001) manually as
09a5ed9134304fcad7f3ec5319e8c1040150f38e (presubmit successful).