dart2js cps: Add a pass for eliminating bounds checks.

dart2js cps: Add a pass for eliminating bounds checks.

The analysis uses a watered-down octagon domain which reduces range
analysis to a graph problem.

There are more ideas to try out to improve on this, but I think this is
a nice baseline to work from.

BUG=
R=sra@google.com

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

[asgerf, 2015-09-16 15:25:08]

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

[asgerf, 2015-09-16 15:25:09]

https://codereview.chromium.org/1353443002/diff/1/pkg/compiler/lib/src/tree_i...
File pkg/compiler/lib/src/tree_ir/tree_ir_tracer.dart (left):

https://codereview.chromium.org/1353443002/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/tree_ir_tracer.dart:136:
whileBlock.statements.add(node);
Drive-by bugfix

https://codereview.chromium.org/1353443002/diff/1/tests/corelib/corelib.status
File tests/corelib/corelib.status (right):

https://codereview.chromium.org/1353443002/diff/1/tests/corelib/corelib.statu...
tests/corelib/corelib.status:234: regexp/pcre_test: Crash # Stack Overflow in
LoopHierarchy.
This is a bug in LoopHierarchy. I expected there wouldn't be deeply nested join
continuations, but that doesn't hold up. I will make it use the trampoline.

[asgerf, 2015-09-21 11:47:01]

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

[asgerf, 2015-09-21 11:47:01]

R.addAll([karlklose, sra]);

[sra1, 2015-09-30 21:54:20]

lgtm

https://chromiumcodereview.appspot.com/1353443002/diff/1/pkg/compiler/lib/src...
File pkg/compiler/lib/src/cps_ir/bounds_checker.dart (right):

https://chromiumcodereview.appspot.com/1353443002/diff/1/pkg/compiler/lib/src...
pkg/compiler/lib/src/cps_ir/bounds_checker.dart:101: if (isUInt32(number)) {
Is there a benefit to matching JSPositiveInt too?

https://chromiumcodereview.appspot.com/1353443002/diff/1/pkg/compiler/lib/src...
pkg/compiler/lib/src/cps_ir/bounds_checker.dart:122: /// -------------
CONSTRAINT HELPERS -----------------
Use '//'.
This is a doc comment that applies to applyConstraint.

Ditto other section markers.

https://chromiumcodereview.appspot.com/1353443002/diff/1/pkg/compiler/lib/src...
pkg/compiler/lib/src/cps_ir/bounds_checker.dart:472: // TODO(asgerf): What we
really need is a "changes length" side effect flag.
More than that - with aliases so a.add(b[i]) does not kill b.length.

https://chromiumcodereview.appspot.com/1353443002/diff/1/pkg/compiler/lib/src...
pkg/compiler/lib/src/cps_ir/bounds_checker.dart:600: /// the loop variable never
changes value during the loop.
These are weak monotonicity, not strict, right?

https://chromiumcodereview.appspot.com/1353443002/diff/1/pkg/compiler/lib/src...
File pkg/compiler/lib/src/cps_ir/type_mask_system.dart (right):

https://chromiumcodereview.appspot.com/1353443002/diff/1/pkg/compiler/lib/src...
pkg/compiler/lib/src/cps_ir/type_mask_system.dart:70: new
TypeMask.unionOf(<TypeMask>[stringType, inferrer.fixedListType],
This needs to include the typed arrays.

https://chromiumcodereview.appspot.com/1353443002/diff/1/pkg/compiler/lib/src...
File pkg/compiler/lib/src/cps_ir/type_propagation.dart (right):

https://chromiumcodereview.appspot.com/1353443002/diff/1/pkg/compiler/lib/src...
pkg/compiler/lib/src/cps_ir/type_propagation.dart:927: if
(receiverValue.isNullable) return false;
Since a.length and a[i] throw when a==null, do we need this?

https://chromiumcodereview.appspot.com/1353443002/diff/1/tests/corelib/coreli...
File tests/corelib/corelib.status (right):

https://chromiumcodereview.appspot.com/1353443002/diff/1/tests/corelib/coreli...
tests/corelib/corelib.status:234: regexp/pcre_test: Crash # Stack Overflow in
LoopHierarchy.
On 2015/09/16 15:25:09, asgerf wrote:
> This is a bug in LoopHierarchy. I expected there wouldn't be deeply nested
join
> continuations, but that doesn't hold up. I will make it use the trampoline.

Acknowledged.

[asgerf, 2015-10-01 09:49:34]

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

https://codereview.chromium.org/1353443002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/bounds_checker.dart:101: if (isUInt32(number)) {
On 2015/09/30 21:54:19, sra1 wrote:
> Is there a benefit to matching JSPositiveInt too?

Might as well match against it.

https://codereview.chromium.org/1353443002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/bounds_checker.dart:122: /// -------------
CONSTRAINT HELPERS -----------------
On 2015/09/30 21:54:19, sra1 wrote:
> Use '//'.
> This is a doc comment that applies to applyConstraint.
> 
> Ditto other section markers.

Done.

https://codereview.chromium.org/1353443002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/bounds_checker.dart:472: // TODO(asgerf): What we
really need is a "changes length" side effect flag.
On 2015/09/30 21:54:20, sra1 wrote:
> More than that - with aliases so a.add(b[i]) does not kill b.length.

Absolutely. I just wanted to clarify why we are using the "changes index" flag.

https://codereview.chromium.org/1353443002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/bounds_checker.dart:600: /// the loop variable never
changes value during the loop.
On 2015/09/30 21:54:19, sra1 wrote:
> These are weak monotonicity, not strict, right?

Yes. Clarified in the comment.

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

https://codereview.chromium.org/1353443002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/type_mask_system.dart:70: new
TypeMask.unionOf(<TypeMask>[stringType, inferrer.fixedListType],
On 2015/09/30 21:54:20, sra1 wrote:
> This needs to include the typed arrays.

Done.

Also, there was a pretty serious bug here since 'fixedListType' actually
resolves to the core List class:

TypesTask.fixedListType -> 
JavaScriptBackend.fixedListImplementation -> 
Compiler.listClass -> 
CoreTypes.listClass

This seems like an issue with one of the above classes, since a bunch of List
variants actually return the same type mask.

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

https://codereview.chromium.org/1353443002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/type_propagation.dart:927: if
(receiverValue.isNullable) return false;
On 2015/09/30 21:54:20, sra1 wrote:
> Since a.length and a[i] throw when a==null, do we need this?

I guess not. Removed.

[asgerf, 2015-10-01 10:35:26]

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

https://codereview.chromium.org/1353443002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/type_mask_system.dart:70: new
TypeMask.unionOf(<TypeMask>[stringType, inferrer.fixedListType],
On 2015/10/01 09:49:34, asgerf wrote:
> On 2015/09/30 21:54:20, sra1 wrote:
> > This needs to include the typed arrays.
> 
> Done.
> 
> Also, there was a pretty serious bug here since 'fixedListType' actually
> resolves to the core List class:
> 
> TypesTask.fixedListType -> 
> JavaScriptBackend.fixedListImplementation -> 
> Compiler.listClass -> 
> CoreTypes.listClass
> 
> This seems like an issue with one of the above classes, since a bunch of List
> variants actually return the same type mask.

Oh nevermind, I was confused by IntelliJ. JavaScriptBackend's
fixedListImplementation actually returns the right class.

[sra1, 2015-10-12 18:00:33]

Are you ready to land this?
I did LGTM over a week ago.

[asgerf, 2015-10-13 08:05:27]

On 2015/10/12 18:00:33, sra1 wrote:
> Are you ready to land this?
> I did LGTM over a week ago.

After rebasing there was a new test failure with the inscrutable message
"Pending static".
I was on vacation last week, and I couldn't fix it in time before leaving.

Will try to land it asap.

[asgerf, 2015-10-13 14:41:06]

Committed patchset #7 (id:120001) manually as
a50105543f84819e75ed7a4f87e22d500c968639 (presubmit successful).