725966 - IonMonkey: Fast path for typeof x == y

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jan de Mooij [:jandem]]

Like JM, we should have fast paths for these expressions:

typeof x == "..."
typeof x === ".."

Comment 1

[Tom S. (please needinfo tschuster)]

So finally ;) I started looking into this. But I have the fear that this is going to introduce some kind of opcode fusing, so I don't like that. 

Probably the easiest way to solve this:
- Introduce MComapreS
- This way we don't have a box for the typeof and string
- Do the fusing (a bit like for LIsNullOrUndefined) in visitCompare so when we have lhs/rhs is typeof and lhs/rhs is string then do MTypeOfIs

Some other idea I had, introduce JSOP_TYPEOFIS, this way we dodge most of the above problems and also can handle the lhs/rhs switch easier in JM!

Some feedback?

Comment 2

[Tom S. (please needinfo tschuster)]

Attachment: WIP

After finding some stupid bug, where I wrongfully assumed that ops in Class is a pointer and not inside.

So yeah this has the simple case for typeof x == '..', where this typeof compare isn't inside an if block. Still needs this.

This also broke comparing with strings, so I need to refresh Bug 721438.

Comment 3

[Tom S. (please needinfo tschuster)]

Attachment: WIP v2

This has TypeOfIsAndBranch. Still lacking tests.

Comment 4

[Tom S. (please needinfo tschuster)]

Attachment: v1

I actually like this version of the patch. It's still very verbose, but I don't think there are a lot of ways to make it even simpler. The typeof x === "object" and typeof y === "function" look a little bit strange, because we implement a typeOf hook and our JSFunction objects have no Call hook!

Oh and tests, they are auto generated, so if you have some suggestions should be easy enough to add them.

Comment 5

[Jan de Mooij [:jandem]]

Comment on attachment 642014 [details] [diff] [review]
v1

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

Looks good, thanks for taking this! r=me with nits below addressed.

The TypeOfIs and TypeOfIsAndBranch cases are very similar, but I agree that trying to combine them will probably make it worse.

::: js/src/ion/CodeGenerator.cpp
@@ +1823,5 @@
>      emitBranch(cond, lir->ifTrue(), lir->ifFalse());
>      return true;
>  }
>  
> +JSType

Nit: "static JSType".

@@ +1829,5 @@
> +{
> +    JSRuntime *rt = cx->runtime;
> +    JSType type = JSTYPE_LIMIT;
> +    if (EqualStrings(str, rt->atomState.typeAtoms[JSTYPE_STRING])) {
> +        type = JSTYPE_STRING;

Nit: you can remove the braces and return early:

if (EqualStrings(str, ...))
    return JSTYPE_STRING;
...
return JSTYPE_LIMIT;

@@ +1883,5 @@
> +        masm.branchTestNull(Assembler::Equal, tag, &isObject);
> +        masm.branchTestObject(Assembler::NotEqual, tag, &isntObject);
> +
> +        masm.unboxObject(value, output);
> +        masm.loadBaseShape(output, output);

This should be masm.loadObjClass. Please find out why the test didn't catch this though, in case there are other problems.

@@ +1912,5 @@
> +        Label isFunction, isntFunction, done;
> +        masm.branchTestObject(Assembler::NotEqual, tag, &isntFunction);
> +
> +        masm.unboxObject(value, output);
> +        masm.loadBaseShape(output, output);

masm.loadObjClass(output, output);

@@ +1935,5 @@
> +    } else if (type == JSTYPE_XML) {
> +        // Don't even really bother.
> +        cond = masm.testObject(Assembler::NotEqual, value);
> +        if (!bailoutIf(cond, lir->snapshot()))
> +            return false;

This should be Assembler::Equal, we want to bailout if the input is an object. Also add some tests to jit-test/tests/e4x/*, we have to live with it for a few more months.. ;)

@@ +1994,5 @@
> +
> +        masm.unboxObject(value, temp);
> +        masm.loadBaseShape(temp, temp);
> +
> +        masm.loadBaseShapeClass(temp, temp);

Nit: the previous two lines can be masm.loadObjClass(temp, temp);

@@ +2015,5 @@
> +        } else {
> +            // Swap branches.
> +            ifTrue = lir->ifFalse();
> +            ifFalse = lir->ifTrue();
> +        }

Nit: can we move the branch-swapping to the top of the function? It avoids duplicating this for object and function and may simplify the XML and LIMIT cases too.

@@ +2025,5 @@
> +
> +        masm.unboxObject(value, temp);
> +        masm.loadBaseShape(temp, temp);
> +
> +        masm.loadBaseShapeClass(temp, temp);

Nit: 

masm.unboxObject(value, temp);
masm.loadObjClass(temp, temp);

@@ +2039,5 @@
> +    } else if (type == JSTYPE_XML) {
> +        // Don't even really bother.
> +        cond = masm.testObject(Assembler::NotEqual, value);
> +        if (!bailoutIf(cond, lir->snapshot()))
> +            return false;

Nit: Assembler::Equal here too.

::: js/src/ion/LIR-Common.h
@@ +1075,5 @@
>  
> +class LTypeOfIs : public LInstructionHelper<1, BOX_PIECES, 0>
> +{
> +    JSOp op_;
> +    const js::Value &v_;

You can remove the & here, storing a reference seems dangerous.

@@ +1100,5 @@
> +
> +class LTypeOfIsAndBranch : public LInstructionHelper<0, BOX_PIECES, 1>
> +{
> +    JSOp jsop_;
> +    const js::Value &v_;

Same here.

::: js/src/ion/Lowering.cpp
@@ +411,5 @@
>  
> +
> +        if (comp->specialization() == MIRType_String) {
> +            // We are only allowed to reorder if it's really going to match.
> +            if (IsTypeOfCompare(left, right) || IsTypeOfCompare(right, left)) {

Nit: if the specialization is "string", swapping the arguments is not observable, so it's okay to just swap and then call IsTypeOfCompare.

::: js/src/jit-test/tests/ion/typeof-is.js
@@ +44,5 @@
> +function isUndefined2(x) {
> +    if ("undefined" === typeof x)
> +        return true;
> +    return false;
> +}

Nit: would be good to add isBanana(x) or something here too.

@@ +46,5 @@
> +        return true;
> +    return false;
> +}
> +
> +for (var i = 0; i < 10000; i++) {

Nit: considering the large loop body, 100 or so may be better (tests run with --ion-eager / --no-jm).

Comment 6

[Tom S. (please needinfo tschuster)]

Attachment: v2

Thank you for spotting this stupid bug :) Just attached the updated version.

Comment 7

[Tom S. (please needinfo tschuster)]

Oh well I just realized this patch has a pretty big gapping hole and for a lot of code this is now actually slower than before!

Because for some strange reason we don't eliminate the LTypeOfV, but still do LTypeOfIs.

Comment 8

[Tom S. (please needinfo tschuster)]

We never set emitAtUse for the MTypeOf, because for some reason the instruction has an second usage namely MBox. I have no idea where this is coming from, I can't see it in iongraph after all. Maybe something with resumepoints?

Comment 9

[Tom S. (please needinfo tschuster)]

Attachment: v3

So I changed the approach somewhat. We know do the fusing in IonBuilder. This also allows us to stop doing the StringCompare in CodeGenerator. There is one small problem:

eg. for code like this

>t = typeof obj
>if (t == 'object')
>  x.push(t)  

We are not allowed to just remove the typeof and such. The problem is at the point of the compare the typeof still has an use count of 1.

Comment 10

[Tom S. (please needinfo tschuster)]

I am not working on this.

Comment 11

[Tom S. (please needinfo tschuster)]

For everyone who wants to try this. I think it might be easier to transform the two patterns typeof x == 'object' and object == typeof x in bytecode.

Comment 12

[Tom S. (please needinfo tschuster)]

s/object/"object"

Comment 13

[Tom S. (please needinfo tschuster)]

Some day this should really be done. I would imagine integrating this with the "filter types at branches" infrastructure might be useful.

Comment 14

[Tom S. (please needinfo tschuster)]

André I thought you had written a patch for this in bug 1655465. Did it not work?

Comment 15

[André Bargull [:anba]]

The (obsoleted) patches in bug 1655465 relied on using GVN for MLoadValueTag, but unfortunately that approach doesn't work on ARM64, because masm.extractTag doesn't return a JSValueTag on that platform.

Comment 16

[André Bargull [:anba]]

Attachment: Bug 725966 - Part 1: Use EnumSet to track remaining types. r=jandem!

Using EnumSet simplifies the code and makes it faster, for example the
constructor is inlined at "-02" and set operations are all constant time.

Comment 17

[André Bargull [:anba]]

Attachment: Bug 725966 - Part 2: Don't skip JSVAL_TYPE_OBJECT checks. r=jandem!

This isn't currently an issue, because the number of observed types is
restricted to six, which means JSVAL_TYPE_OBJECT currently can't be last,
but it seems nicer to explicitly handle this case, because otherwise it might
confuse the reader and if we ever support seven or more types in the
observed types set, we could introduce a subtle bug here.

Depends on D128069

Comment 18

[André Bargull [:anba]]

Attachment: Bug 725966 - Part 3: Sort common property names alphabetically. r=jandem!

Only because I noticed this while working on the next patch in this stack.

Depends on D128070

Comment 19

[André Bargull [:anba]]

Attachment: Bug 725966 - Part 4: Remove JSTYPE_NULL. r=jandem!

JSTYPE_NULL was added for e4x.

Depends on D128071

Comment 20

[André Bargull [:anba]]

Attachment: Bug 725966 - Part 5: Split MTypeOf in two separate MIR instructions. r=jandem!

Split MTypeOf in two separate instructions so it's easier to further
optimise it in comparison contexts, see part 8.

Depends on D128072

Comment 21

[André Bargull [:anba]]

Attachment: Bug 725966 - Part 6: Move typeof comparison detection into a separate function. r=jandem!

Moves the typeof equality comparison detection into a separate function, so
we can reuse it in part 8. Additionally it was updated to handle all possible
JSType constants.

Depends on D128073

Comment 22

[André Bargull [:anba]]

Attachment: Bug 725966 - Part 7: Handle remaining types when folding typeof. r=jandem!

• JSTYPE_UNDEFINED is similar to JSTYPE_OBJECT and has to handle both
  undefined and objects inputs.
• JSTYPE_FUNCTION can never occur when the input isn't an object.
• JSTYPE_LIMIT means the string constant isn't a valid type name.

Depends on D128074

Comment 23

[André Bargull [:anba]]

Attachment: Bug 725966 - Part 8: Fold away typeof string comparisons. r=jandem!

This optimisation folds away string comparisons when typeof appears in
equality comparison contexts:

MTypeOfName(MTypeOf(input)) == MConstant(string)

is now optimised to:

MTypeOf(input) == MConstant(int32).

Depends on D128075

Comment 24

[André Bargull [:anba]]

Attachment: Bug 725966 - Part 9: Add `MacroAssembler::test{Number,Boolean,String,Symbol,BigInt}Set()`. r=jandem!

Add testThingSet methods in preparation for the next part.

MIPS doesn't support MacroAssembler::emitSet(), so we have to introduce this
additional abstraction.

Depends on D128076

Comment 25

[André Bargull [:anba]]

Attachment: Bug 725966 - Part 10: Optimise typeof in simple comparison contexts. r=jandem!

This is based on Tom's original patch in bug 725966.

As the last optimisation in this stack, optimise typeof in simple comparison
contexts. For example:

if (typeof thing === "number") { ... }

is now optimised into:

if (IsNumber(thing)) { ... }

This optimisation is only used when there's a single user of the MTypeOfName
instruction to avoid slowing down the case when typeof is used in switch
statements.

For example consider:

switch (typeof thing) {
  case "object":
  case "undefined":
  case "number":
  case "boolean":
  case "string":
  case "symbol":
  case "bigint":
  case "function":
}

If thing was a function, using the MTypeOfIs optimisation would mean that
the type tag is split eight times (for each case statement), possibly even
two OOL calls when the function is a proxy (for the "object" and "undefined"
cases).

Depends on D128077

Comment 26

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/0c2849b874cb
Part 1: Use EnumSet to track remaining types. r=jandem
https://hg.mozilla.org/integration/autoland/rev/1b847f9f911a
Part 2: Don't skip JSVAL_TYPE_OBJECT checks. r=jandem
https://hg.mozilla.org/integration/autoland/rev/5d8a68d1f36b
Part 3: Sort common property names alphabetically. r=jandem
https://hg.mozilla.org/integration/autoland/rev/25723de19680
Part 4: Remove JSTYPE_NULL. r=jandem
https://hg.mozilla.org/integration/autoland/rev/5508f47f0571
Part 5: Split MTypeOf in two separate MIR instructions. r=jandem
https://hg.mozilla.org/integration/autoland/rev/7659142f5ede
Part 6: Move typeof comparison detection into a separate function. r=jandem
https://hg.mozilla.org/integration/autoland/rev/fc925bdde132
Part 7: Handle remaining types when folding typeof. r=jandem
https://hg.mozilla.org/integration/autoland/rev/d90d0eeda9a7
Part 8: Fold away typeof string comparisons. r=jandem
https://hg.mozilla.org/integration/autoland/rev/d085abe7302d
Part 9: Add `MacroAssembler::test{Number,Boolean,String,Symbol,BigInt}Set()`. r=jandem
https://hg.mozilla.org/integration/autoland/rev/1708b6a2373d
Part 10: Optimise typeof in simple comparison contexts. r=jandem

Comment 27

[Marian-Vasile Laza]

Backed out 10 changesets (Bug 725966) for causing build bustages on CodeGenerator.cpp.
Backout link
Push with failures
Failure Log

Comment 28

[André Bargull [:anba]]

I'll look into it, seems like some GCC specific issue.

Comment 29

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/2faf162d473a
Part 1: Use EnumSet to track remaining types. r=jandem
https://hg.mozilla.org/integration/autoland/rev/2406b5231307
Part 2: Don't skip JSVAL_TYPE_OBJECT checks. r=jandem
https://hg.mozilla.org/integration/autoland/rev/f34552d29d22
Part 3: Sort common property names alphabetically. r=jandem
https://hg.mozilla.org/integration/autoland/rev/3aac3ca5cdbb
Part 4: Remove JSTYPE_NULL. r=jandem
https://hg.mozilla.org/integration/autoland/rev/2198d91bb27c
Part 5: Split MTypeOf in two separate MIR instructions. r=jandem
https://hg.mozilla.org/integration/autoland/rev/5798488e85bb
Part 6: Move typeof comparison detection into a separate function. r=jandem
https://hg.mozilla.org/integration/autoland/rev/0b43bb2f2d8b
Part 7: Handle remaining types when folding typeof. r=jandem
https://hg.mozilla.org/integration/autoland/rev/e419b06ed3d4
Part 8: Fold away typeof string comparisons. r=jandem
https://hg.mozilla.org/integration/autoland/rev/a490916980ca
Part 9: Add `MacroAssembler::test{Number,Boolean,String,Symbol,BigInt}Set()`. r=jandem
https://hg.mozilla.org/integration/autoland/rev/4cc431f61ab0
Part 10: Optimise typeof in simple comparison contexts. r=jandem

Comment 30

[Noemi Erli[:noemi_erli]]

https://hg.mozilla.org/mozilla-central/rev/2faf162d473a
https://hg.mozilla.org/mozilla-central/rev/2406b5231307
https://hg.mozilla.org/mozilla-central/rev/f34552d29d22
https://hg.mozilla.org/mozilla-central/rev/3aac3ca5cdbb
https://hg.mozilla.org/mozilla-central/rev/2198d91bb27c
https://hg.mozilla.org/mozilla-central/rev/5798488e85bb
https://hg.mozilla.org/mozilla-central/rev/0b43bb2f2d8b
https://hg.mozilla.org/mozilla-central/rev/e419b06ed3d4
https://hg.mozilla.org/mozilla-central/rev/a490916980ca
https://hg.mozilla.org/mozilla-central/rev/4cc431f61ab0

Comment 31

[Tom S. (please needinfo tschuster)]

Very cool. Thanks André for finally getting this done.