Prevent hoisting of certain check nodes, including [HTypeKnown].

Prevent hoisting of certain check nodes, including [HTypeKnown].

BUG=

superseded by https://codereview.chromium.org/199873004/

[sra1, 2014-03-20 15:51:49]

Are there any differences from allowing other HCheck instructions to move in
SsaCodeMotion?

[floitsch, 2014-03-20 16:07:25]

LGTM.
Make sure to address Stephen's concerns/comments.

https://codereview.chromium.org/206553002/diff/1/sdk/lib/_internal/compiler/i...
File sdk/lib/_internal/compiler/implementation/ssa/nodes.dart (right):

https://codereview.chromium.org/206553002/diff/1/sdk/lib/_internal/compiler/i...
sdk/lib/_internal/compiler/implementation/ssa/nodes.dart:2484: HInstruction
witness)
nit: I prefer aligning with the first argument.

https://codereview.chromium.org/206553002/diff/1/sdk/lib/_internal/compiler/i...
File sdk/lib/_internal/compiler/implementation/ssa/optimize.dart (right):

https://codereview.chromium.org/206553002/diff/1/sdk/lib/_internal/compiler/i...
sdk/lib/_internal/compiler/implementation/ssa/optimize.dart:1505: void
changeUsesDominatedBy(HBasicBlock dominator,
Nit: we should change the name. It's not just changing the users. It's also
inserting an HTypeKnown node.

[herhut, 2014-03-20 16:16:51]

On 2014/03/20 15:51:49, sra1 wrote:
> Are there any differences from allowing other HCheck instructions to move in
> SsaCodeMotion?

The movable ones that did not take part before (HBoundsCheck, HTypeConversion,
some HTypeKnown) that now do are all ones that use proper data-flow
dependencies. So I expect the optimizations to naturally do the right thing.
Whether this actually helps is another question. I have not seen any effect on
performance in benchmarks.

[herhut, 2014-03-20 16:25:10]

https://codereview.chromium.org/206553002/diff/1/sdk/lib/_internal/compiler/i...
File sdk/lib/_internal/compiler/implementation/ssa/nodes.dart (right):

https://codereview.chromium.org/206553002/diff/1/sdk/lib/_internal/compiler/i...
sdk/lib/_internal/compiler/implementation/ssa/nodes.dart:2484: HInstruction
witness)
On 2014/03/20 16:07:25, floitsch wrote:
> nit: I prefer aligning with the first argument.

Done.

https://codereview.chromium.org/206553002/diff/1/sdk/lib/_internal/compiler/i...
File sdk/lib/_internal/compiler/implementation/ssa/optimize.dart (right):

https://codereview.chromium.org/206553002/diff/1/sdk/lib/_internal/compiler/i...
sdk/lib/_internal/compiler/implementation/ssa/optimize.dart:1505: void
changeUsesDominatedBy(HBasicBlock dominator,
On 2014/03/20 16:07:25, floitsch wrote:
> Nit: we should change the name. It's not just changing the users. It's also
> inserting an HTypeKnown node.

It is now called [insertTypePropagationForDominatedUsers]

Done.

[sra1, 2014-03-20 16:31:00]

On 2014/03/20 16:16:51, herhut wrote:
> On 2014/03/20 15:51:49, sra1 wrote:
> > Are there any differences from allowing other HCheck instructions to move in
> > SsaCodeMotion?
> 
> The movable ones that did not take part before (HBoundsCheck, HTypeConversion,
> some HTypeKnown) that now do are all ones that use proper data-flow
> dependencies. So I expect the optimizations to naturally do the right thing.
> Whether this actually helps is another question. I have not seen any effect on
> performance in benchmarks.

What I do is look at the output on a lot of tests, e.g.
on master:
rm -rf out/ReleaseIA32/gener*
tools/test.py -mrelease -cdart2js -rd8  corelib lib pkg
cp -r out/ReleaseIA32 /tmp/V1
same again on branch, copy to /tmp/V2
use a tree diff program (e.g. meld) to inspect changes.

[sra1, 2014-03-20 18:27:37]

Your change does some nice things:

_JsonStringifier_hexDigit: [function(x) {
        var t1;
        if (J.$lt$n(x, 10) === true) {
          if (typeof x !== "number")
            return H.iae(x);
          t1 = 48 + x;
        } else {
          if (typeof x !== "number")
            return H.iae(x);
          t1 = 87 + x;
        }
        return t1;
      },
--->
JsonStringifier_hexDigit: [function(x) {
        var t1 = J.$lt$n(x, 10);
        if (typeof x !== "number")
          return H.iae(x);
        return t1 === true ? 48 + x : 87 + x;
      },

Some changes fix bugs. (we can only do digitParts.length after codeUnitAt$1.):

generated_compilations/dart2js/tests_corelib_uri_base_test/out.js

          digitsPart = match[1];
          for (t1 = J.getInterceptor$as(digitsPart), t2 = digitsPart.length, i =
0; i < t1.get$length(digitsPart); ++i) {
            t1.codeUnitAt$1(digitsPart, 0);
            if (i >= t2)
              H.throwExpression(P.RangeError$value(i));
            if (digitsPart.charCodeAt(i) > maxCharCode)
              return handleError.call$1(source);
          }
--->
          digitsPart = match[1];
          for (t1 = J.getInterceptor$as(digitsPart), i = 0; i <
t1.get$length(digitsPart); ++i) {
            t1.codeUnitAt$1(digitsPart, 0);
            if (i >= digitsPart.length)
              H.throwExpression(P.RangeError$value(i));
            if (digitsPart.charCodeAt(i) > maxCharCode)
              return handleError.call$1(source);
          }


I'd look at this one carefully:

generated_compilations/dart2js/tests_language_optimized_string_charat_test/out.js

    for (t1 = $.a, t2 = t1.length, i = 0; i < 20; ++i)
      if (0 >= t2)
        return H.ioore(t1, 0);
    if (0 >= t2)
      return H.ioore(t1, 0);
--->
    t1 = $.a;
    t2 = t1.length;
    i = 0;
    while (true) {
      if (0 >= t2)
        return H.ioore(t1, 0);
      if (!(i < 20))
        break;
      ++i;
    }

[floitsch, 2014-03-20 18:38:49]

There are some problems. The following program should exit with an error that A
does not support "~". But instead it complains that xor does not exist on B.

====
class A {}

main() {
  var list = [ 1, 2, new A() ];
  var i = list[confuse(0)];  // confuse as usual.
  var b = list[confuse(2)];
  var d = list[confuse(2)];
  if (confuse(1) > 48) {
    print(b ^ d);
  } else {
    print(b | ~d);
  }
}
====

Output:
===
    t1 = X.confuse(1);
    if (typeof b !== "number")
      return b.$xor();
    if (t1 > 48) {
      if (typeof d !== "number")
        return H.iae(d);
      P.print((b ^ d) >>> 0);
    } else
      P.print((b | J.$not$i(d)) >>> 0);
===

[floitsch, 2014-03-20 18:40:20]

On 2014/03/20 18:38:49, floitsch wrote:
> There are some problems. The following program should exit with an error that
A
> does not support "~". But instead it complains that xor does not exist on B.
should have been "does not exist on A".

> 
> ====
> class A {}
> 
> main() {
>   var list = [ 1, 2, new A() ];
>   var i = list[confuse(0)];  // confuse as usual.
>   var b = list[confuse(2)];
>   var d = list[confuse(2)];
>   if (confuse(1) > 48) {
>     print(b ^ d);
>   } else {
>     print(b | ~d);
>   }
> }
> ====
> 
> Output:
> ===
>     t1 = X.confuse(1);
>     if (typeof b !== "number")
>       return b.$xor();
>     if (t1 > 48) {
>       if (typeof d !== "number")
>         return H.iae(d);
>       P.print((b ^ d) >>> 0);
>     } else
>       P.print((b | J.$not$i(d)) >>> 0);
> ===

[herhut, 2014-03-20 19:43:03]

On 2014/03/20 18:40:20, floitsch wrote:
> On 2014/03/20 18:38:49, floitsch wrote:
> > There are some problems. The following program should exit with an error
that
> A
> > does not support "~". But instead it complains that xor does not exist on B.
> should have been "does not exist on A".
> 
> > 
> > ====
> > class A {}
> > 
> > main() {
> >   var list = [ 1, 2, new A() ];
> >   var i = list[confuse(0)];  // confuse as usual.
> >   var b = list[confuse(2)];
> >   var d = list[confuse(2)];
> >   if (confuse(1) > 48) {
> >     print(b ^ d);
> >   } else {
> >     print(b | ~d);
> >   }
> > }
> > ====
> > 
> > Output:
> > ===
> >     t1 = X.confuse(1);
> >     if (typeof b !== "number")
> >       return b.$xor();
> >     if (t1 > 48) {
> >       if (typeof d !== "number")
> >         return H.iae(d);
> >       P.print((b ^ d) >>> 0);
> >     } else
> >       P.print((b | J.$not$i(d)) >>> 0);
> > ===

A property of [HTypeConversion] is ignored for the purpose of GVN: The field
[receiverTypeCheckSelector], which holds the selector that lead to the
refinement, is not taken into account. While I first considered that this might
be a clever trick to make GVN remove redundant type conversions, I found that it
is already done somewhere else, so this probably is a bug.

[floitsch, 2014-03-20 20:05:58]

On 2014/03/20 19:43:03, herhut wrote:
> On 2014/03/20 18:40:20, floitsch wrote:
> > On 2014/03/20 18:38:49, floitsch wrote:
> > > There are some problems. The following program should exit with an error
> that
> > A
> > > does not support "~". But instead it complains that xor does not exist on
B.
> > should have been "does not exist on A".
> > 
> > > 
> > > ====
> > > class A {}
> > > 
> > > main() {
> > >   var list = [ 1, 2, new A() ];
> > >   var i = list[confuse(0)];  // confuse as usual.
> > >   var b = list[confuse(2)];
> > >   var d = list[confuse(2)];
> > >   if (confuse(1) > 48) {
> > >     print(b ^ d);
> > >   } else {
> > >     print(b | ~d);
> > >   }
> > > }
> > > ====
> > > 
> > > Output:
> > > ===
> > >     t1 = X.confuse(1);
> > >     if (typeof b !== "number")
> > >       return b.$xor();
> > >     if (t1 > 48) {
> > >       if (typeof d !== "number")
> > >         return H.iae(d);
> > >       P.print((b ^ d) >>> 0);
> > >     } else
> > >       P.print((b | J.$not$i(d)) >>> 0);
> > > ===
> 
> A property of [HTypeConversion] is ignored for the purpose of GVN: The field
> [receiverTypeCheckSelector], which holds the selector that lead to the
> refinement, is not taken into account. While I first considered that this
might
> be a clever trick to make GVN remove redundant type conversions, I found that
it
> is already done somewhere else, so this probably is a bug.

My current understanding is that we don't take throwing expressions into account
when doing code-motion.
I just created a test-case that throws the wrong exception when run on master
(without this CL).