Closed Bug 973238 Opened 7 years ago Closed 7 years ago

Implement structural arrays for typed objects


(Core :: JavaScript Engine, defect)

Not set





(Reporter: nmatsakis, Assigned: nmatsakis)




(10 files, 2 obsolete files)

3.96 KB, patch
: review+
Details | Diff | Splinter Review
33.35 KB, patch
: review+
Details | Diff | Splinter Review
15.31 KB, patch
: review+
Details | Diff | Splinter Review
28.53 KB, patch
: review+
Details | Diff | Splinter Review
928 bytes, patch
: review+
Details | Diff | Splinter Review
1.47 KB, patch
: review+
Details | Diff | Splinter Review
10.86 KB, patch
: review+
Details | Diff | Splinter Review
2.61 KB, patch
: review+
Details | Diff | Splinter Review
44.50 KB, patch
: review+
Details | Diff | Splinter Review
66.04 KB, patch
Details | Diff | Splinter Review
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
Assignee: nobody → nmatsakis
Whiteboard: [leave-open]
Attachment #8393484 - Flags: review?(sphink)
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.
Attachment #8393485 - Flags: review?(sphink)
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: 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 on attachment 8393484 [details] [diff] [review]

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

This was already dead?
Attachment #8393484 - Flags: review?(sphink) → review+
Comment on attachment 8393485 [details] [diff] [review]

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)?
Attachment #8393485 - Flags: review?(sphink) → review+
(In reply to Steve Fink [:sfink] from comment #4)
> This was already dead?

(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.
Depends on: 966575
Depends on: 989276
Try run for patches 1 and 2, rebased:
Attached patch Bug972581-Part3.diff (obsolete) — Splinter Review
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.
Attachment #8400167 - Flags: review?(sphink)
Attached patch Bug973238-Part4.diff (obsolete) — Splinter Review
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).
Attachment #8400181 - Flags: review?(sphink)
Comment on attachment 8400167 [details] [diff] [review]

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.


::: 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.
Attachment #8400167 - Flags: review?(sphink) → review+
Comment on attachment 8400181 [details] [diff] [review]

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 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()?
Attachment #8400181 - Flags: review?(sphink)
Attachment #8400181 - Flags: review?(jdemooij)
Attachment #8400181 - Flags: review+
Address nits, r=sfink
Attachment #8400167 - Attachment is obsolete: true
Attachment #8400323 - Flags: review+
Address nits from sfink. Re-r? jandem.
Attachment #8400181 - Attachment is obsolete: true
Attachment #8400181 - Flags: review?(jdemooij)
Attachment #8400325 - Flags: review?(jdemooij)
this private flag was a holdover from long, long ago.
Attachment #8400362 - Flags: review?(sphink)
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.
Attachment #8400364 - Flags: review?(bhackett1024)
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.
Attachment #8400365 - Flags: review?(bhackett1024)
Attachment #8400364 - Flags: review?(bhackett1024) → review+
Attachment #8400365 - Flags: review?(bhackett1024) → review+
Attachment #8400362 - Flags: review?(sphink) → review+
Comment on attachment 8400325 [details] [diff] [review]

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()),
Attachment #8400325 - Flags: review?(jdemooij) → review+
Attachment #8423908 - Flags: review?(sphink)
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.
Attachment #8423909 - Flags: review?(sphink)
Try run for part 4, 5, 6, and 7:
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.
Attachment #8424147 - Flags: review?(jdemooij)
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 on attachment 8424147 [details] [diff] [review]

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

I started looking at the patch but I'm a bit confused by the 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/
@@ -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?
Attachment #8424147 - Flags: review?(jdemooij)
Attachment #8423908 - Flags: review?(sphink) → review+
Attachment #8423909 - Flags: review?(sphink) → review+
Try run for patches 4-9:
Flags: needinfo?(nmatsakis)
Depends on: 1022356
Opened bug 1022356 to represent the remaining work, as recommended by RyanVM. Added as a pre-req to this bug.
Resolving per comment 34.
Closed: 7 years ago
Resolution: --- → FIXED
Whiteboard: [leave-open]
Target Milestone: --- → mozilla32
You need to log in before you can comment on or make changes to this bug.