Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

dart2js: fails to eliminate range check in code accessing array elements in pairs #6070

Open
rakudrama opened this issue Oct 19, 2012 · 12 comments
Labels
area-web Use area-web for Dart web related issues, including the DDC and dart2js compilers and JS interop. dart2js-optimization P2 A bug or feature request we're likely to work on type-enhancement A request for a change that isn't a bug web-dart2js

Comments

@rakudrama
Copy link
Member

This example is distilled from some code where I am storing pairs of elements in an array.
The compiler should be able to eliminate the index bounds check.

pr(List a) {
  for (int i = 0; i + 1 < a.length; i += 2) {
    print('${a[i]} ${a[i+1]}');
  }
}

main() {
  var f = pr;
  f([1,2]);
  f([1,2,3,4,5]);
}

$.pr = function(a) {
  if (typeof a !== 'string' && (typeof a !== 'object' || a === null || a.constructor !== Array && !a.is$JavaScriptIndexingBehavior))
    return $.pr$bailout(1, a);
  for (var i = 0; t1 = i + 1, t2 = a.length, t1 < t2; i += 2) {
    if (i >= t2)
      throw $.ioore(i);
    var t3 = $.S(a[i]) + ' ';
    if (t1 >= a.length)
      throw $.ioore(t1);
    $.print(t3 + $.S(a[t1]));
  }
  var t2, t1;
};

If I change the check to i < a.length - 1, one access check is eliminated, but the other is not:
(I prefer the first version since the loop condition states the quantity (i+1) that must be in range.)

$.pr = function(a) {
  if (typeof a !== 'string' && (typeof a !== 'object' || a === null || a.constructor !== Array && !a.is$JavaScriptIndexingBehavior))
    return $.pr$bailout(1, a);
  for (var i = 0; i < a.length - 1; i += 2) {
    var t1 = $.S(a[i]) + ' ';
    var t2 = i + 1;
    if (t2 >= a.length)
      throw $.ioore(t2);
    $.print(t1 + $.S(a[t2]));
  }
};

@kasperl
Copy link

kasperl commented Oct 19, 2012

Set owner to ngeoffray@google.com.
Added this to the M2 milestone.
Removed Priority-Medium label.
Added Priority-Low, Accepted labels.

@peter-ahe-google
Copy link
Contributor

Removed this from the M2 milestone.
Added this to the Later milestone.
Removed Priority-Low label.
Added Priority-Medium label.

@DartBot
Copy link

DartBot commented Nov 11, 2012

This comment was originally written by ngeoffray@google.com


Note that the reason in your second version, the second check is not eliminated is because we treat the $.S call has side effects, and therefore the size of the array can change.

@rakudrama
Copy link
Member Author

Interesting.
It would be quite difficult to determine that the side effects of the various array manipulations reached via toString did not in fact change the input.

@kasperl
Copy link

kasperl commented May 23, 2013

Added TriageForM5 label.

@kasperl
Copy link

kasperl commented May 28, 2013

Removed TriageForM5 label.

@DartBot
Copy link

DartBot commented Dec 19, 2013

This comment was originally written by ngeoffray@google.com


Added Triaged label.

@DartBot
Copy link

DartBot commented Dec 19, 2013

This comment was originally written by ngeoffray@google.com


Set owner to @floitschG.

@floitschG
Copy link
Contributor

Fwiw this is what we generate now. So we still have the second check. It doesn't look like side-effects are the reason we do the bounds-check.

   for (i = 0; i < a.length; i += 2) {
      t1 = "" + a[i] + " ";
      t2 = i + 1;
      if (t2 >= a.length)
        return H.ioore(a, t2);
      line = t1 + a[t2];
      H.printString(line);
    }


Removed the owner.
Added Optimization label.

@rakudrama
Copy link
Member Author

Could still be side-effects.
HStringify is probably marked as having side-effects.
HStringify(x) generates "" + x at codegen time.

@kasperl
Copy link

kasperl commented Jul 10, 2014

Removed this from the Later milestone.
Added Oldschool-Milestone-Later label.

@kasperl
Copy link

kasperl commented Aug 4, 2014

Removed Oldschool-Milestone-Later label.

@kevmoo kevmoo added P2 A bug or feature request we're likely to work on type-enhancement A request for a change that isn't a bug and removed triaged labels Feb 29, 2016
@vsmenon vsmenon added area-web Use area-web for Dart web related issues, including the DDC and dart2js compilers and JS interop. and removed area-web Use area-web for Dart web related issues, including the DDC and dart2js compilers and JS interop. labels Jul 20, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
area-web Use area-web for Dart web related issues, including the DDC and dart2js compilers and JS interop. dart2js-optimization P2 A bug or feature request we're likely to work on type-enhancement A request for a change that isn't a bug web-dart2js
Projects
None yet
Development

No branches or pull requests

8 participants