602641 - JM: Refactor GETELEM IC

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[David Anderson [:dvander] - inactive, e-mail if emergency]

The code for generating these paths is fairly hairy and does not easily lend itself to typed array specialization, or some DOM PICs peterv was interested in.

Let's just defer code generation for it instead.

Comment 1

[David Anderson [:dvander] - inactive, e-mail if emergency]

Will do SETELEM in another bug since this patch is getting way too big.

Comment 2

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: patch

voop. This patch has a lot of refactoring and cleanups so I apologize for the noise. The notable changes:

 * GetElementIC can now support two sets of stub chains, one for string keys and one for integer keys. This is so typed arrays, string elements, and potentially other things can be implemented without another huge refactoring like this.

 * ICs now return a "LookupStatus" which is ternary [Error, Uncacheable, Cacheable]. It helps propagate errors better than the old boolean.

 * A bunch of getprop related stuff was factored out into a helper class.

 * To simplify things, we teleport along prototype chains now. This removed the "objRemat" field from PICInfo.

 * I had to up the PIC limit to 17 for the new IC. The old GETELEM could inline one string-property stub, and losing that one extra path was a 1ms loss on string-fasta.

This looks like noise (*maybe* 1-2ms on sunspider), and a reproducible 2% win on v8. It's hard to say from what - teleporting removed a bunch of loads and improved register use, and the getelem path has better register allocation now.

Comment 3

[David Anderson [:dvander] - inactive, e-mail if emergency]

(also worth nothing, this patch is a net loss of ~150 lines of code)

Comment 4

[Chris Leary [:cdleary] (not checking bugmail)]

(In reply to comment #2)
>  * To simplify things, we teleport along prototype chains now. This removed the
> "objRemat" field from PICInfo.

What does teleport mean?

Comment 5

[Brendan Eich [:brendan]]

(In reply to comment #4)
> (In reply to comment #2)
> >  * To simplify things, we teleport along prototype chains now. This removed the
> > "objRemat" field from PICInfo.
> 
> What does teleport mean?

https://developer.mozilla.org/En/SpiderMonkey/Internals/Property_cache#Non-adding_cache_entries (last paragraph)

/be

Comment 6

[Brendan Eich [:brendan]]

Comment on attachment 485935 [details] [diff] [review]
patch

Righteous patch!

/be

Comment 7

[David Mandelin [:dmandelin]]

Comment on attachment 485935 [details] [diff] [review]
patch

>+int gxse_detect = 0;
>+bool gxse_bool = false;

Looks like leftover code.

> bool
> mjit::Compiler::jsop_getelem()
>@@ -1516,30 +1390,93 @@ mjit::Compiler::jsop_getelem()
>         return true;
>     }
> 
>-    if (id->isTypeKnown() && id->getKnownType() == JSVAL_TYPE_STRING && id->isConstant()) {
>-        /* Never happens, or I'd optimize it. */
>-        jsop_getelem_slow();
>-        return true;
>+    // Guard on the object type. The additional patching is needed because
>+    // the code after does not use linkExit(), and thus leave() will not
>+    // link all sync blocks.
>+    MaybeJump objTypeGuard;
>+    if (!obj->isTypeKnown()) {
>+        Jump objectGuard = frame.testObject(Assembler::NotEqual, obj);
>+        objectGuard.linkTo(masm.label(), &masm);
>     }

objTypeGuard never gets set. Also, the immediate linkTo looks funny. That might be a dup of the linkTo in the code below that tries to use objTypeGuard. Not sure which is the real one.

>+    // Get a mutable register for the ID type.
>+    frame.maybeUnpinReg(pinnedIdType);
>+    if (id->isConstant() || id->isTypeKnown())
>+        ic.typeReg = frame.allocReg();
>+    else
>+        ic.typeReg = frame.copyTypeIntoReg(id);

OK for this patch. But this seems tricky. It looks like the user needs to know a lot about what copyTypeIntoReg does in order to know this is correct. Maybe we need to add APIs that take pinned regs as arguments and use them up. Failing that, we should probably document exactly which APIs implicitly do that (take a reg, but won't clobber it until they've done their thing)--or are they all like that?

>+    if (!id->isNotType(JSVAL_TYPE_INT32)) {

Confusing. Let's add an API |mightBeType|.

>+struct GetElementIC : public BaseIC {
>+    // When generating a new type check, this contains the type register.
>+    // Each stub chains off a type check path, and may clobber the register,
>+    // ultimately placing the out-type in it.
>+    // Note: The type reg is always available, but will contain garbage if
>+    // the type is constant.
>+    RegisterID typeReg   : 5;
>+
>+    // Register containing the object pointer, also the out-data register.
>+    RegisterID objReg    : 5;

These are good comments (applies to that whole section). But I think they could be a bit better, by being more brutally explicit. One way to do it would be to write a separate ABI spec, along the lines of:

  On entry to a PIC stub:
    typeReg     holds the type of the id, but only if the id's type is non-constant
    objReg      holds a JSObject *, the base object for the getelem

    - the inline fast path's guard exits and guard exits from generated stubs must
      maintain or establish these invariants.

  On exit from a PIC stub:
    typeReg     holds the type of the result value
    objReg      holds the payload of the result value

    - the inline fast path's end point and rejoin exits from generate stubs must
      establish these postconditions.

A second way is to just be a bit more explicit and pattern-y with these comments:

      // At stub entry/stub guard exit:    holds the type of the id if type is non-constant
      // At stub rejoin exit:              holds the result type
      RegisterID typeReg   : 5;

      // At stub entry/stub guard exit:    holds the base object
      // At stub rejoin exit:              holds the result result payload
      RegisterID objReg    : 5;

>+    LookupStatus error(JSContext *cx) {
>+        return error();
>     }

Not sure what this adds to the other overload for |error|.

>+    if (idval.isInt32()) {
>+        if (!INT_FITS_IN_JSID(idval.toInt32()))
>+            goto intern_big_int;
>+        id = INT_TO_JSID(idval.toInt32());
>+    } else {
>+      intern_big_int:
>+        if (!js_InternNonIntElementId(cx, obj, idval, &id))
>+            THROW();
>+    }

I think this can be:

      if (idval.isInt32() && INT_FITS_IN_JSID(idval.toInt32()))
          id = INT_TO_JSID(idval.toInt32());
      } else {
          if (!js_InternNonIntElementId(cx, obj, idval, &id))
              THROW();
      }

I'm also not sure on what that part is for. Is that for when the base object is not a dense array and the property id is an int32? Does attachGetProp work in that case? It seems to assume the id will always be a string so something seems wrong here.

>+void JS_FASTCALL
>+ic::GetElement(VMFrame &f, ic::GetElementIC *ic)
...
>+    if (ic->stubsGenerated == MAX_PIC_STUBS || ic->shouldUpdate(cx)) {

Seems like it should be MAX_GETELEM_IC_STUBS. But actually, we disable once we hit the max, so we shouldn't even reach this point in that condition, so maybe the first part is not needed? Or, maybe it's totally right and opaque enough to require a comment.

>+    // Guard on the string's type and identity.
>+    MaybeJump atomTypeGuard;
>+    if (hasInlineTypeGuard() && !inlineTypeGuardPatched) {
>+        JS_ASSERT(!idRemat.isTypeKnown());
>+        atomTypeGuard = masm.testString(Assembler::NotEqual, typeReg);
>+    } else {
>+        JS_ASSERT_IF(!hasInlineTypeGuard(), idRemat.knownType() == JSVAL_TYPE_STRING);
>+    }

The if condition seems to be assuming an invariant that if the inline type guard has been patched, then there is a previous stub that guards that the id is a string. I think this is true but it seems fragile. We should have more assertions, or record that more explicitly in the PIC, or at least document it.

Second, what ensures the assertion in the else part. It seems to me that we could have a case where the id is always an int and we fail the dense array guard in the fast path. In that case, there would be no inline type guard, but the id type is not string.

Comment 8

[David Mandelin [:dmandelin]]

I forgot one thing: we should add a bunch of new test cases for this. I can help you with that if you want--it may be useful to have the tests written by someone other than the patch author.

Comment 9

[David Anderson [:dvander] - inactive, e-mail if emergency]

(In reply to comment #7)
> objTypeGuard never gets set. Also, the immediate linkTo looks funny.

Thanks, this was totally bogus, and actually caused a bug in no-ic mode.

> 
> >+    // Get a mutable register for the ID type.
> >+    frame.maybeUnpinReg(pinnedIdType);
> >+    if (id->isConstant() || id->isTypeKnown())
> >+        ic.typeReg = frame.allocReg();
> >+    else
> >+        ic.typeReg = frame.copyTypeIntoReg(id);
> 
> OK for this patch. But this seems tricky. It looks like the user needs to know
> a lot about what copyTypeIntoReg does in order to know this is correct.

Admittedly the use here is a little confusing. But copyTypeIntoReg()'s documentation already says exactly what it does: tempRegForType + allocReg + move and nothing more. I've clarified what that code is doing, though.

> 
> >+    if (!id->isNotType(JSVAL_TYPE_INT32)) {
> 
> Confusing. Let's add an API |mightBeType|.

Ouch, yeah, weird double negative :)

> A second way is to just be a bit more explicit and pattern-y with these
> comments:

Okay, the register state is more explicit now.

> >+    LookupStatus error(JSContext *cx) {
> >+        return error();
> >     }
> 
> Not sure what this adds to the other overload for |error|.

It's needed for the GetPropertyHelper template. It'll go away once all the ICs are split out of the union.

> The if condition seems to be assuming an invariant that if the inline type
> guard has been patched, then there is a previous stub that guards that the id
> is a string. I think this is true

Yup, that is exactly right. I'll add a comment explaining how it works and how we maintain the invariant.

> 
> Second, what ensures the assertion in the else part. It seems to me that we
> could have a case where the id is always an int and we fail the dense array
> guard in the fast path. In that case, there would be no inline type guard, but
> the id type is not string.

In this scenario, we would not hit the attachGetProp() case.

Comment 10

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: interdiff

Comment 11

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: v2

Comment 12

[David Anderson [:dvander] - inactive, e-mail if emergency]

http://hg.mozilla.org/tracemonkey/rev/1b3abe381bd6 and
http://hg.mozilla.org/tracemonkey/rev/3d1ae3d363d5

Comment 13

[David Anderson [:dvander] - inactive, e-mail if emergency]

http://hg.mozilla.org/mozilla-central/rev/1b3abe381bd6