Change ListIterator to only check for concurrent modification at each iteration

Change ListIterator to only check for concurrent modification at each iteration
in checked mode.

It also checks at the end in all cases.

Iteration only goes from 0 to the original length of the list.
This ensures that iterating a list while adding to it (like by x.addAll(x))
is caught instead of growing until out-of-memory.
For well-behaved programs this makes no difference since length and original
length stay the same.
Also, it means that calling moveNext again later, after increasing the length,
will not make iteration continue. After returning false, iteration is always
done.
However, it means that reducing the length causes an out-of-range read before
reaching the end, and before a concurrent modification error can happen.

R=sra@google.com

Committed: https://code.google.com/p/dart/source/detail?r=45198

[Lasse Reichstein Nielsen, 2015-03-20 10:39:58]

lrn@google.com changed reviewers:
+ floitsch@google.com, sra@google.com

[sra1, 2015-03-20 12:36:59]

For dart2js we want compile

  for (var e in a){...}

to something that
 (1) is equivalent to the ListIterator (i.e. a valid optimization), and
 (2) looks like this loop:

  for (var i = 0;  i < a.length; i++) {
    var e = a[i];
    ...
  }

There are two reasons for desiring this form, where a.length is accessed on each
iteration.  It eliminates array bounds checks at two levels:

(a) dart2js can see that a[i] is guarded by i < a.length so can avoid emitting
an array bounds check to signal IndexError.  The key information is that there
is no possibility of the length changing between the check and the indexing
since there is no code between them.

(b) JavaScript engine can see something similar: a[i] is guarded by i < a.length
and can eliminate the bounds check within its internal implementation of lists.

Manually hoisting the array length will usually both confuse dart2js and the
JavaScript engine into generating an array bounds check.  In cases where the
JavaScript engine would not be confused, it can hoist a.length itself.

The JavaScript case is discussed here:
http://mrale.ph/blog/2014/12/24/array-length-caching.html

[Lasse Reichstein Nielsen, 2015-04-15 13:24:55]

Is this closer to what you need?

[floitsch, 2015-04-15 13:26:14]

I would be ok with this. It makes the code faster and in checked mode it still
triggers.

[sra1, 2015-04-15 19:17:26]

I would like to move forward with the assert-only check.

Please also update the iterator called ArrayIterator in js_lib/js_array.dart

[sra1, 2015-04-15 19:19:27]

lgtm

[Lasse Reichstein Nielsen, 2015-04-16 09:08:11]

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

[floitsch, 2015-04-16 11:20:57]

CCing a few VM devs, since they might want to look at their strategies of
dealing with list-iterations.

[sra1, 2015-04-16 17:56:21]

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

[sra1, 2015-04-16 17:56:21]

I apologize that I misread the CL.

I had misread it as no checks at all in production mode.
This is what we need to generate idiomatic JS - no checks.

We can't generate the check after the loop since there must be no checks on exit
via break statements.
Generating the check as part of the loop condition is as bad (or worse) for V8
than in the update since it puts unknown code between i < a.length and a[i].

The only way to get from 26us to 14us on jsshell is to have no check at all.  I
guess I was reading what I wanted to read.

I apologize for saying lgtm, we should revert until we get this sorted out.