Implement structural arrays for typed objects

RESOLVED FIXED in mozilla32

Status

()

defect
RESOLVED FIXED
5 years ago
5 years ago

People

(Reporter: nmatsakis, Assigned: nmatsakis)

Tracking

unspecified
mozilla32
x86
Linux
Points:
---
Dependency tree / graph
Bug Flags:
in-testsuite +

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(10 attachments, 2 obsolete attachments)

3.96 KB, patch
sfink
: review+
Details | Diff | Splinter Review
33.35 KB, patch
sfink
: review+
Details | Diff | Splinter Review
15.31 KB, patch
nmatsakis
: review+
Details | Diff | Splinter Review
28.53 KB, patch
jandem
: review+
Details | Diff | Splinter Review
928 bytes, patch
sfink
: review+
Details | Diff | Splinter Review
1.47 KB, patch
bhackett
: review+
Details | Diff | Splinter Review
10.86 KB, patch
bhackett
: review+
Details | Diff | Splinter Review
2.61 KB, patch
sfink
: review+
Details | Diff | Splinter Review
44.50 KB, patch
sfink
: review+
Details | Diff | Splinter Review
66.04 KB, patch
Details | Diff | Splinter Review
(Assignee)

Description

5 years ago
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)

Updated

5 years ago
(Assignee)

Updated

5 years ago
Assignee: nobody → nmatsakis
(Assignee)

Updated

5 years ago
Whiteboard: [leave-open]
(Assignee)

Comment 1

5 years ago
Attachment #8393484 - Flags: review?(sphink)
(Assignee)

Comment 2

5 years ago
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)
(Assignee)

Comment 3

5 years ago
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 on attachment 8393484 [details] [diff] [review]
Bug973238-Part1.diff

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

This was already dead?
Attachment #8393484 - Flags: review?(sphink) → review+
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)?
Attachment #8393485 - Flags: review?(sphink) → review+
(Assignee)

Comment 6

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

yes.
(Assignee)

Comment 7

5 years ago
(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.
(Assignee)

Updated

5 years ago
Depends on: 966575
(Assignee)

Updated

5 years ago
Depends on: 989276
(Assignee)

Comment 8

5 years ago
Try run for patches 1 and 2, rebased: https://tbpl.mozilla.org/?tree=Try&rev=35871c44d4f2
(Assignee)

Comment 10

5 years ago
Posted 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)
(Assignee)

Comment 11

5 years ago
Posted 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]
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.
Attachment #8400167 - Flags: review?(sphink) → review+
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()?
Attachment #8400181 - Flags: review?(sphink)
Attachment #8400181 - Flags: review?(jdemooij)
Attachment #8400181 - Flags: review+
(Assignee)

Comment 14

5 years ago
Address nits, r=sfink
Attachment #8400167 - Attachment is obsolete: true
Attachment #8400323 - Flags: review+
(Assignee)

Comment 15

5 years ago
Address nits from sfink. Re-r? jandem.
Attachment #8400181 - Attachment is obsolete: true
Attachment #8400181 - Flags: review?(jdemooij)
Attachment #8400325 - Flags: review?(jdemooij)
(Assignee)

Comment 16

5 years ago
this private flag was a holdover from long, long ago.
Attachment #8400362 - Flags: review?(sphink)
(Assignee)

Comment 17

5 years ago
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)
(Assignee)

Comment 18

5 years ago
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]
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);
Attachment #8400325 - Flags: review?(jdemooij) → review+
(Assignee)

Comment 23

5 years ago
Attachment #8423908 - Flags: review?(sphink)
(Assignee)

Comment 24

5 years ago
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)
(Assignee)

Comment 25

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

Comment 27

5 years ago
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]
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?
Attachment #8424147 - Flags: review?(jdemooij)
Attachment #8423908 - Flags: review?(sphink) → review+
Attachment #8423909 - Flags: review?(sphink) → review+
(Assignee)

Comment 31

5 years ago
Try run for patches 4-9: https://tbpl.mozilla.org/?tree=Try&rev=3bd8865c951c
Flags: needinfo?(nmatsakis)
(Assignee)

Updated

5 years ago
Depends on: 1022356
(Assignee)

Comment 34

5 years ago
Opened bug 1022356 to represent the remaining work, as recommended by RyanVM. Added as a pre-req to this bug.
Resolving per comment 34.
Status: NEW → RESOLVED
Last Resolved: 5 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.