Closed Bug 725966 Opened 12 years ago Closed 3 years ago

IonMonkey: Fast path for typeof x == y

Categories

(Core :: JavaScript Engine, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
95 Branch
Tracking Status
firefox95 --- fixed

People

(Reporter: jandem, Assigned: anba)

References

(Blocks 2 open bugs)

Details

(Whiteboard: [ion:t])

Attachments

(11 files, 4 obsolete files)

v3
41.29 KB, patch
Details | Diff | Splinter Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
48 bytes, text/x-phabricator-request
Details | Review
Like JM, we should have fast paths for these expressions:

typeof x == "..."
typeof x === ".."
Assignee: general → evilpies
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?
Attached patch WIP (obsolete) — Splinter Review
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.
Blocks: 765980
Attached patch WIP v2 (obsolete) — Splinter Review
This has TypeOfIsAndBranch. Still lacking tests.
Attachment #628407 - Attachment is obsolete: true
Attached patch v1 (obsolete) — Splinter Review
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.
Attachment #639772 - Attachment is obsolete: true
Attachment #642014 - Flags: review?(jdemooij)
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).
Attachment #642014 - Flags: review?(jdemooij) → review+
Attached patch v2 (obsolete) — Splinter Review
Thank you for spotting this stupid bug :) Just attached the updated version.
Attachment #642014 - Attachment is obsolete: true
Attachment #642759 - Flags: review+
Depends on: 774510
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.
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?
Attached patch v3Splinter Review
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.
Attachment #642759 - Attachment is obsolete: true
I am not working on this.
Assignee: evilpies → general
Blocks: 606648
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.
s/object/"object"
Assignee: general → nobody
Some day this should really be done. I would imagine integrating this with the "filter types at branches" infrastructure might be useful.

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

Flags: needinfo?(andrebargull)

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.

Flags: needinfo?(andrebargull)

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

Assignee: nobody → andrebargull
Status: NEW → ASSIGNED

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

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

Depends on D128070

JSTYPE_NULL was added for e4x.

Depends on D128071

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

Depends on D128072

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

  • 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

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

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

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

Pushed by andre.bargull@gmail.com:
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

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

Flags: needinfo?(andrebargull)

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

Flags: needinfo?(andrebargull)
Pushed by andre.bargull@gmail.com:
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

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

Regressions: 1736307
Regressions: 1736783
You need to log in before you can comment on or make changes to this bug.