973238 - Implement structural arrays for typed objects

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Niko Matsakis [:nmatsakis]]

In the current codebase, array types are nominal (i.e., each time you create a new array type, it gets a distinct prototype). In the new spec, there are many changes:

1. array types are structural;
2. `Type.array(D...)` creates an array *instance*
3. `Type.Array(D...)` creates a type descriptor of dimensions `D...`
4. `Type.Array.prototype` yields the canonical prototype for arrays of a particular dimension
5. The `ArrayType` constructor is removed entirely

Comment 1

[Niko Matsakis [:nmatsakis]]

Attachment: Bug973238-Part1.diff

Comment 2

[Niko Matsakis [:nmatsakis]]

Attachment: Bug973238-Part2.diff

Remove the TypedObjectPointer abstraction. It was nice, but somewhat inefficient, and not suitable now that we'll be moving to a world where typed objects link to a typed prototype and not a type descriptor.

Comment 3

[Niko Matsakis [:nmatsakis]]

I've made a lot of progress on this bug locally, but still have a ways to go. For now I'm going to try and land some of the preliminary patches so as to avoid diverging too far.

Here is the design I am moving towards. This maps quite closely to the evolving spec, which is of course no accident since impl and spec are moving (somewhat) in tandem. Spec available here: https://github.com/dslomov-chromium/typed-objects-es7. Note that some of the names I use and the names that Dmitry chose to use in the spec don't match (in particular, he uses type descriptor for what I call a typed prototype). I'll have to do some renaming in the future. For now I will avoid the term type descriptor and use type object, though it intersects with TI. I will have to rename things in our codebase sooner or later.

1. Type objects will always specify precise dimensions for arrays. They will follow a grammar like:

   T = U | [T * N]
   U = scalar | primitive | float32x4 | int32x4 | Struct { (f: T)* }

2. Each complex type object (SIMD, structs, arrays) has a link to a `prototype` field. For structs and SIMD types, this is a 1-to-1 relationship (that is, each distinct struct type has a distinct `prototype` property). All array types, however, share the same prototype, regardless of their length. Hence the prototypes can be described using the following grammar:

   P = U | [P]

We can define a function `prototype(T) = P` that erases the dimensions, and hence converts from a type object T to the prototype that it will have:

   prototype(U) = U
   prototype([T * N]) = [prototype(T)]

3. When a typed object is created by instantiating a type object T, its `[[Prototype]]` becomes the `prototype` from T (that is, `prototype(T)`). Note that the `[[Prototype]]` for typed objects is immutable.

4. To integrate with TI, we remove the addendum stuff we use now. TI already tracks the prototype as part of a TI type object, so we can directly use that to extract most of what we need (except for exact dimensions).

5. As part of TI integration, we also make all type objects singleton objects. This will help us with expressions like `Point(...)` where `Point` is a type object, and other places where type objects are referenced.

Anyway, I have a bunch of patches moving in this direction, but it's not quite there yet. For now I uploaded the first 2. Once those are reviewed and landed I'll feed in more.

Comment 4

[Steve Fink [:sfink] [:s:]]

Comment on attachment 8393484 [details] [diff] [review]
Bug973238-Part1.diff

Review of attachment 8393484 [details] [diff] [review]:
-----------------------------------------------------------------

This was already dead?

Comment 5

[Steve Fink [:sfink] [:s:]]

Comment on attachment 8393485 [details] [diff] [review]
Bug973238-Part2.diff

Review of attachment 8393485 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/builtin/TypedObject.js
@@ +270,5 @@
>  }
>  
>  // Sets `fromValue` to `this` assuming that `this` is a scalar type.
> +function TypedObjectSetScalar(descr, typedObj, offset, fromValue) {
> +  var type = DESCR_TYPE(descr);

what happpened to the assert(REPR_KIND(descr) == JS_TYPEREPR_SCALAR_KIND)?

Comment 6

[Niko Matsakis [:nmatsakis]]

(In reply to Steve Fink [:sfink] from comment #4)
> This was already dead?

yes.

Comment 7

[Niko Matsakis [:nmatsakis]]

(In reply to Steve Fink [:sfink] from comment #5)
> what happpened to the assert(REPR_KIND(descr) == JS_TYPEREPR_SCALAR_KIND)?

Not sure why I removed that; I'll add back some comparable assert.

Comment 8

[Niko Matsakis [:nmatsakis]]

Try run for patches 1 and 2, rebased: https://tbpl.mozilla.org/?tree=Try&rev=35871c44d4f2

Comment 9

[Niko Matsakis [:nmatsakis]]

Part 1:   https://hg.mozilla.org/integration/mozilla-inbound/rev/d86d8ac76b25
Part 2:   https://hg.mozilla.org/integration/mozilla-inbound/rev/ef6d290021ff

Comment 10

[Niko Matsakis [:nmatsakis]]

Attachment: Bug972581-Part3.diff

This patch creates a link from each type descriptor to a typed prototype. For now, this link is 1:1, though by the end of the patch series, all array descriptors for a given element type will share a typed prototype.

I called it a Typed Prototype because (a) it is the prototype for a Typed Object and (b) as such it carries the full typing information for that typed object. Still it's kind of a weird name and I'm not sure what to call it instead.

Comment 11

[Niko Matsakis [:nmatsakis]]

Attachment: Bug973238-Part4.diff

Now that the descriptor is reachable from the prototype, we can stop using that reserved slot for typed objects (it is still used for typed arrays).

Comment 12

[Steve Fink [:sfink] [:s:]]

Comment on attachment 8400167 [details] [diff] [review]
Bug972581-Part3.diff

Review of attachment 8400167 [details] [diff] [review]:
-----------------------------------------------------------------

I feel like I ought to have more to say about this patch, but I don't.

::: js/src/builtin/TypedObject.cpp
@@ +196,5 @@
> + * Typed Prototypes
> + *
> + * Every type descriptor has an associated prototype. Instances of
> + * that type descriptor use this as their prototype. Per the spec,
> + * typed object prototypes cannot be mutate.

*mutated

::: js/src/jsobjinlines.h
@@ +464,1 @@
>       * Explicityly disallow mutating the [[Prototype]] of Location objects

Preexisting, but typo in explicityly. Happyly, it's easy to fix.

Comment 13

[Steve Fink [:sfink] [:s:]]

Comment on attachment 8400181 [details] [diff] [review]
Bug973238-Part4.diff

Review of attachment 8400181 [details] [diff] [review]:
-----------------------------------------------------------------

And over to Jan for the jit goop.

::: js/src/jit/LIR-Common.h
@@ +3693,5 @@
>          return getOperand(0);
>      }
>  };
>  
> +// Load a typed object's prototype, which is guaranteed to be a

...to be a one legged goose with a scarlet headband?

::: js/src/tests/ecma_6/TypedObject/prototypes.js
@@ +13,5 @@
> +
> +  var uints = new Uints();
> +  assertEq(uints.__proto__, p);
> +  assertThrowsInstanceOf(function() uints.__proto__ = {},
> +                         TypeError);

I know it's the same thing, but can you also test Object.setPrototypeOf()?

Comment 14

[Niko Matsakis [:nmatsakis]]

Attachment: Bug973238-Part3.diff

Address nits, r=sfink

Comment 15

[Niko Matsakis [:nmatsakis]]

Attachment: Bug973238-Part4.diff

Address nits from sfink. Re-r? jandem.

Comment 16

[Niko Matsakis [:nmatsakis]]

Attachment: Bug973238-Part5.diff

this private flag was a holdover from long, long ago.

Comment 17

[Niko Matsakis [:nmatsakis]]

Attachment: Bug973238-Part6.diff

Now that the prototype of a typed object is linked indelibly to its type, we can get that info directly from the TI type object, which always knows the prototype.

Comment 18

[Niko Matsakis [:nmatsakis]]

Attachment: Bug973238-Part7.diff

Remove the typed object addendums. I left the generalization in place, maybe it's useful later? I could rip it out entirely too, of course.

Comment 19

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/d86d8ac76b25
https://hg.mozilla.org/mozilla-central/rev/ef6d290021ff

Comment 20

[Niko Matsakis [:nmatsakis]]

Part 3: https://hg.mozilla.org/integration/mozilla-inbound/rev/3ba8c4d47698
Try run: https://tbpl.mozilla.org/?tree=Try&rev=67ded973aabe

Comment 21

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/3ba8c4d47698

Comment 22

[Jan de Mooij [:jandem]]

Comment on attachment 8400325 [details] [diff] [review]
Bug973238-Part4.diff

Review of attachment 8400325 [details] [diff] [review]:
-----------------------------------------------------------------

Sorry for the delay. I only looked at the jit/ parts as Steve reviewed the rest.

::: js/src/jit/Lowering.cpp
@@ +2366,5 @@
> +{
> +    JS_ASSERT(ins->type() == MIRType_Object);
> +    return defineReturn(new(alloc()) LTypedObjectProto(
> +                            useFixed(ins->object(), CallTempReg0),
> +                            tempFixed(CallTempReg1)),

I don't think these have to be *Fixed (codegen doesn't depend on them being in these regs AFAICS), so just use useRegister() and temp().

Also, the indentation looks unusual. I think you can do:

return defineReturn(new(alloc()) LTypedObjectProto(useRegister(ins->object()), temp()),
                    ins);

Comment 23

[Niko Matsakis [:nmatsakis]]

Attachment: Bug973238-Part8.diff

Comment 24

[Niko Matsakis [:nmatsakis]]

Attachment: Bug973238-Part9.diff

sfink -- I decided the code would get nicer if we just separated out all the various enum constants into their own namespace, rather than attaching them to types. This seems particular true since they are used by both typed objects and typed arrays. I chose `js::type` as the namespace for these constants semi-arbitrarily.

I am not at all sure if this is the right choice of names or approach, let me know what you think. It's basically just a bikeshed issue I guess.

One thing I did not do, but which I ought to do, is to move those constants into their own header file included by both TypedObject.h and TypedArray.h.

Comment 25

[Niko Matsakis [:nmatsakis]]

Try run for part 4, 5, 6, and 7: https://tbpl.mozilla.org/?tree=Try&rev=b14a586eb93f

Comment 26

[Niko Matsakis [:nmatsakis]]

Parts 4, 5, 6, and 7:

remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/2ca44eb13ecf
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/e40e2dbf7d9e
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/472dffac7f21
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/cc81a0f56362

Comment 27

[Niko Matsakis [:nmatsakis]]

Attachment: Bug973238-Part10.diff

Refine the way that we track predicted typed object types in the JIT. We used to track sets of type descriptors, then test what conditions held for all of them. This version just tracks the information that everything has in common. It gracefully degrades through various states:

1. Precise type descriptor is known. This gives us complete information about everything, including array bounds.

2. Prototype is known. Eventually, this will be less precise, because it will mean that precise array bounds (if applicable) are not known, though the array type is still known. At this point in the patch series, though, prototypes and type descriptors still have a 1-to-1 relationship.

3. Struct prefix is known. This means that we don't know precisely which struct type the value is, but we do know a prefix of its fields. This can occur with subtyping situations.

Comment 28

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

(In reply to Niko Matsakis [:nmatsakis] from comment #26)
> Parts 4, 5, 6, and 7:
> 
> remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/2ca44eb13ecf
> remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/e40e2dbf7d9e
> remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/472dffac7f21
> remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/cc81a0f56362

Backed out in http://hg.mozilla.org/integration/mozilla-inbound/rev/a1a599888834 for build bustage: 
https://tbpl.mozilla.org/php/getParsedLog.php?id=39841659&tree=Mozilla-Inbound

Comment 29

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

The backout was still broken, but it's working on a clobber build. So maybe you just need to touch CLOBBER next time this lands?

Comment 30

[Jan de Mooij [:jandem]]

Comment on attachment 8424147 [details] [diff] [review]
Bug973238-Part10.diff

Review of attachment 8424147 [details] [diff] [review]:
-----------------------------------------------------------------

I started looking at the patch but I'm a bit confused by the moz.build change mentioned below. If you can post an updated patch addressing that I'll take a closer look :)

::: js/src/builtin/TypedObject.h
@@ +1065,5 @@
>  }
>  
> +inline js::type::Kind
> +js::TypedProto::kind() const {
> +    return typeDescr().kind();

Nit: { on its own line

::: js/src/moz.build
@@ -290,5 @@
>          'jit/shared/CodeGenerator-shared.cpp',
>          'jit/shared/Lowering-shared.cpp',
>          'jit/Snapshots.cpp',
>          'jit/StupidAllocator.cpp',
> -        'jit/TypeDescrSet.cpp',

TypeDescrSet.cpp still exists after this patch right? Should it be removed?

Comment 31

[Niko Matsakis [:nmatsakis]]

Try run for patches 4-9: https://tbpl.mozilla.org/?tree=Try&rev=3bd8865c951c

Comment 32

[Niko Matsakis [:nmatsakis]]

Pushed patches 4-9 to inbound:

remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/8de97fc223d2
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/89bd60c2a4df
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/4903226b4f2f
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/3e9ea2740183
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/880fd861075f
remote:   https://hg.mozilla.org/integration/mozilla-inbound/rev/731411eebd0a

Comment 33

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/8de97fc223d2
https://hg.mozilla.org/mozilla-central/rev/89bd60c2a4df
https://hg.mozilla.org/mozilla-central/rev/4903226b4f2f
https://hg.mozilla.org/mozilla-central/rev/3e9ea2740183
https://hg.mozilla.org/mozilla-central/rev/880fd861075f
https://hg.mozilla.org/mozilla-central/rev/731411eebd0a

Note that with the uplift being on Monday, it's probably better for tracking purposes to close this bug out and file a follow-up tracking any work that'll be landing on Fx33.

Comment 34

[Niko Matsakis [:nmatsakis]]

Opened bug 1022356 to represent the remaining work, as recommended by RyanVM. Added as a pre-req to this bug.

Comment 35

[Ryan VanderMeulen [:RyanVM]]

Resolving per comment 34.