More type checking performance improvements and a bug fix in intrinsifier.

More type checking performance improvements and a bug fix in intrinsifier.
With "frog --leg", type checked mdoe is now "only" 5x slower (used to be 10x).
Committed: https://code.google.com/p/dart/source/detail?r=5915

[regis, 2012-03-27 22:04:48]

LGTM!!

[sra1, 2012-03-28 01:16:50]

DBC

https://chromiumcodereview.appspot.com/9844003/diff/6003/runtime/vm/code_gene...
File runtime/vm/code_generator_ia32.cc (right):

https://chromiumcodereview.appspot.com/9844003/diff/6003/runtime/vm/code_gene...
runtime/vm/code_generator_ia32.cc:1550: Label loop_done, loop;
This is a test where Dart can be much faster than JS.
This was a single test in Oberon.
Each class descriptor contains a table of pointers to all the superclasses,
including a self reference at the slot corresponding to the depth of the class
(number of extends from Object).

x is C =>
  x->class_offset->superclasses[C.extends_depth] == C.descriptor

Since C.extends_depth and C.descriptor are constants by this time, the generated
code can be:

  mov r2, [r1 + class_offset]
  cmp [r2 + superclasses + C.extends_depth*4], #C.descriptor
  jz yes

The original paper "Type-extension type test can be performed in constant time",
Norman H. Cohen, has a check on the inheritance depth but that can be avoided in
most cases (depth <= K) by always allocating at least K slots, or storing
something after the table that cannot contain a pointer to a class descriptor. 
If a variable sized descriptor is not possible, some clever hybrid could be
used, e.g. keep the top K slots in-line in the class descriptor, so most 'x is
C' tests can use the fast trick and fall back on the loop (bounded by a depth
check instead of null check) for depth > K.

https://chromiumcodereview.appspot.com/9844003/diff/6003/runtime/vm/code_gene...
runtime/vm/code_generator_ia32.cc:1618: __ cmpl(EDI, Immediate(0));
Should be unnecessary since SUB sets CC

[srdjan, 2012-03-28 01:46:23]

https://chromiumcodereview.appspot.com/9844003/diff/6003/runtime/vm/code_gene...
File runtime/vm/code_generator_ia32.cc (right):

https://chromiumcodereview.appspot.com/9844003/diff/6003/runtime/vm/code_gene...
runtime/vm/code_generator_ia32.cc:1550: Label loop_done, loop;
On 2012/03/28 01:16:50, sra1 wrote:
> This is a test where Dart can be much faster than JS.
> This was a single test in Oberon.
> Each class descriptor contains a table of pointers to all the superclasses,
> including a self reference at the slot corresponding to the depth of the class
> (number of extends from Object).
> 
> x is C =>
>   x->class_offset->superclasses[C.extends_depth] == C.descriptor
> 
> Since C.extends_depth and C.descriptor are constants by this time, the
generated
> code can be:
> 
>   mov r2, [r1 + class_offset]
>   cmp [r2 + superclasses + C.extends_depth*4], #C.descriptor
>   jz yes
> 
> The original paper "Type-extension type test can be performed in constant
time",
> Norman H. Cohen, has a check on the inheritance depth but that can be avoided
in
> most cases (depth <= K) by always allocating at least K slots, or storing
> something after the table that cannot contain a pointer to a class descriptor.

> If a variable sized descriptor is not possible, some clever hybrid could be
> used, e.g. keep the top K slots in-line in the class descriptor, so most 'x is
> C' tests can use the fast trick and fall back on the loop (bounded by a depth
> check instead of null check) for depth > K.

Thanks. The purpose of this CL is to quickly eliminate runtime calls, which are
still the most expensive part of checked mode. A quick supertype check is on our
TODO list.

https://chromiumcodereview.appspot.com/9844003/diff/6003/runtime/vm/code_gene...
runtime/vm/code_generator_ia32.cc:1618: __ cmpl(EDI, Immediate(0));
On 2012/03/28 01:16:50, sra1 wrote:
> Should be unnecessary since SUB sets CC

Thanks. Next CL.