591172 - JM: Optimize 'typeof' comparisons.

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Sean Stangl [:sstangl]]

JSNES source frequently produces bytecode such as:

[jaeger] JSOps         1 00064:  34  typeof
[jaeger] JSOps         1 00065:  34  string "undefined"
[jaeger] JSOps         2 00068:  34  ne

Instead of doing a string comparison, we should detect whether the string is one of the known types, and output a comparison on the Value's type. We can optimize this entire complicated procedure to just a branchPtr().

Comment 1

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

Good idea. See similar bug 574233. This approach would cover a bunch of cases in date-format-tofte as well.

Comment 2

[Brendan Eich [:brendan]]

Could go even further, since typeof does not convert, and peephole optimize that sequence into a "isDefined" test -- have to be careful to allow for unqualified names not found in the scope chain to be used, of course.

Similar idea for isString, isNumber, etc.

/be

Comment 3

[Tom S [:evilpie]]

Attachment: Optimize typeof x === 'number'|'string'|'boolean'|'undefined'

Comment 4

[Tom S [:evilpie]]

So a few things:
 * I cant test x64 myself, somebody needs to check this please :)
 * I am not entirely sure what behavior i trigger if a variable is _not_ defined, but it seems to work. Please could somebody explain how this works?
 * I would do the other cases to, but you can't seem to distinguish function and object

Performance: 

for (var i = 0; i < 1e6; i++) {
   typeof y === "number";
}

From ~31 to ~3, other are similar, only typeof for _not_ defined variables, is still dog slow ~220 to ~180.

Comment 5

[Brendan Eich [:brendan]]

Comment on attachment 487053 [details] [diff] [review]
Optimize typeof x === 'number'|'string'|'boolean'|'undefined'

># HG changeset patch
># User Tom Schuster <[e-mail]>
># Date 1288389391 -7200
># Node ID 08c8ca7d2e185b59bca2c44cfa210ed3119bca0d
># Parent  66f4a212edebd33473bdf56408bd3af6de1c6719
>specialize sequence typeof x === 'number' etc.
>
>diff -r 66f4a212edeb -r 08c8ca7d2e18 js/src/methodjit/FastOps.cpp
>--- a/js/src/methodjit/FastOps.cpp	Thu Oct 28 12:23:00 2010 -0700
>+++ b/js/src/methodjit/FastOps.cpp	Fri Oct 29 23:56:31 2010 +0200
>@@ -914,7 +914,61 @@
>             return;
>         }
>     }
>+    
>+    
>+    

One blank line is enough, and no trailing whitespace please.

>+    JSOp fused = JSOp(PC[JSOP_TYPEOF_LENGTH]);
>+    if (fused == JSOP_STRING) {
>+        JSOp op = JSOp(PC[JSOP_TYPEOF_LENGTH + JSOP_STRING_LENGTH]);        
> 
>+        if (op == JSOP_STRICTEQ || op == JSOP_EQ || JSOP_STRICTNE || op == JSOP_NE) {
>+            JSAtom *atom = script->getAtom(fullAtomIndex(PC + JSOP_TYPEOF_LENGTH));

Note that fullAtomIndex handles only the 16-bit immediate case implied by matching JSOP_STRING, anyway, so you don't need it.

A nit on fullAtomIndex: it should use GET_UINT16, not GET_SLOTNO.

>+            JSRuntime *rt = cx->runtime;          
>+            JSValueType type;

Note uninitialized variable here -- should be initialized to JSTYPE_LIMIT.

>+            Assembler::Condition cond = (op == JSOP_STRICTEQ || op == JSOP_EQ) ? Assembler::Equal 
>+                                    : Assembler::NotEqual;              

Nit: wrap before ? and : and make them underhang the (.

>+            
>+            if (atom == rt->atomState.typeAtoms[JSTYPE_VOID]) {
>+                type = JSVAL_TYPE_UNDEFINED;
>+            } else if (atom == rt->atomState.typeAtoms[JSTYPE_STRING]) {
>+                type = JSVAL_TYPE_STRING;
>+            } else if (atom == rt->atomState.typeAtoms[JSTYPE_BOOLEAN]) {
>+                type = JSVAL_TYPE_BOOLEAN;
>+            } else if (atom == rt->atomState.typeAtoms[JSTYPE_NUMBER]) {
>+                type = JSVAL_TYPE_INT32;
>+                                
>+                /* JSVAL_TYPE_DOUBLE is 0x0 and JSVAL_TYPE_INT32 is 0x1, use <= or > to match both */
>+                cond = (cond == Assembler::Equal) ? Assembler::BelowOrEqual : Assembler::Above;
>+            }
>+            
>+            if (type) { 

Trailing space nit again, and probably elsewhere -- don't do it!

Non-nit: this should test type != JSTYPE_LIMIT.

>+                PC += JSOP_TYPEOF_LENGTH;
>+                PC += JSOP_STRING_LENGTH;
>+                
>+                RegisterID result = frame.allocReg(Registers::SingleByteRegs);
>+                
>+                #if defined JS_CPU_X86 

Nit (trailing space aside): don't we prefer # in column 1? We do in most of SpiderMonkey. Not in nanojit, but that is downstream of the nanojit-central repo and under separate style rules.

>+                if (frame.shouldAvoidTypeRemat(fe))
>+                    masm.set32(cond, masm.tagOf(frame.addressOf(fe)), ImmType(type), result);
>+                else
>+                    masm.set32(cond, frame.tempRegForType(fe), ImmType(type), result);                    
>+                #elif defined JS_CPU_X64
>+                RegisterID maskReg = frame.allocReg();
>+                masm.move(ImmType(type), maskReg);
>+
>+                RegisterID r = frame.tempRegForType(fe);
>+                masm.setPtr(cond, r, maskReg, result);
>+
>+                frame.freeReg(maskReg);
>+                #endif
>+
>+                frame.pop();
>+                frame.pushTypedPayload(JSVAL_TYPE_BOOLEAN, result);               
>+                return;                

So how does an unbound variable get evaluated here into fe, without throwing a ReferenceError prematurely (which typeof nosuchvar avoids)?

/be

Comment 6

[Tom S [:evilpie]]

>Note that fullAtomIndex handles only the 16-bit immediate case implied by
>matching JSOP_STRING, anyway, so you don't need it.
Don't know what this means

>So how does an unbound variable get evaluated here into fe, without throwing a
>ReferenceError prematurely (which typeof nosuchvar avoids)?
Yes this was kind of my question, too.

Comment 7

[Tom S [:evilpie]]

Attachment: Optimize typeof x === 'number'|'string'|'boolean'|'undefined' v2

Comment 8

[Tom S [:evilpie]]

Ops sorry!

Comment 9

[Brendan Eich [:brendan]]

(In reply to comment #6)
> >Note that fullAtomIndex handles only the 16-bit immediate case implied by
> >matching JSOP_STRING, anyway, so you don't need it.
> Don't know what this means

Not to worry, dvander knows. It's just that fullAtomIndex does only the non-full case (which is fine for now), and there's a nit about its implementation (have a look and re-read my nit about using GET_UINT16).

/be

Comment 10

[Tom S [:evilpie]]

Attachment: Optimize typeof x === 'number'|'string'|'boolean'|'undefined' v3

All nits fixed.
I do understand the |typeof nosuchvar| case now. For not defined variables we end up calling stubs::GetGlobalName, which itself calls NameOp, and if this function cant find a global variable, it throws. But beforehand it checks if the next op is typeof, and then just pushes undefined.

Comment 11

[Tom S [:evilpie]]

Attachment: v4

Uses JSVAL_TYPE_UNINITIALIZED instead of JSTYPE_LIMIT.

One number v8-earley-boyer:
js -m before: ~312ms
js -m after: ~299ms

Comment 12

[Brendan Eich [:brendan]]

(In reply to comment #11)
> Created attachment 487227 [details] [diff] [review]
> v4
> 
> Uses JSVAL_TYPE_UNINITIALIZED instead of JSTYPE_LIMIT.

Those are not from the same category (enum, ad-hoc int subrange type)! Just use JSTYPE_LIMIT, you are computing a JSType value here, not a jsval or js::Value.

/be

Comment 13

[Tom S [:evilpie]]

This isn't JSType, but JSValueType.

Comment 14

[Brendan Eich [:brendan]]

(In reply to comment #13)
> This isn't JSType, but JSValueType.

Apologies -- I'm blind. Will get eye transplants and review in a second.

/be

Comment 15

[Brendan Eich [:brendan]]

Comment on attachment 487227 [details] [diff] [review]
v4

Looks good to me, thanks for doing this.

David mentioned that he would have a look this weekend, and I'm a JM rookie, so r?'ing him too.

/be

Comment 16

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

Comment on attachment 487227 [details] [diff] [review]
v4

>+            if (type != JSVAL_TYPE_UNINITIALIZED) {
>+                PC += JSOP_TYPEOF_LENGTH;
>+                PC += JSOP_STRING_LENGTH;

This would be clearer as,
    PC += JSOP_STRING_LENGTH;
    PC += JSOP_EQ_LENGTH;

Since the compiler will add JSOP_TYPEOF_LENGTH itself when this function returns.

>+
>+                RegisterID result = frame.allocReg(Registers::SingleByteRegs);
>+
>+#if defined JS_CPU_X86
>+                if (frame.shouldAvoidTypeRemat(fe))
>+                    masm.set32(cond, masm.tagOf(frame.addressOf(fe)), ImmType(type), result);
>+                else
>+                    masm.set32(cond, frame.tempRegForType(fe), ImmType(type), result);
>+#elif defined JS_CPU_X64

This etc will assert if fe->isTypeKnown(), which can be true if the earlier detection fell through. For example,
  var x = { };
  if (typeof x == "bleh")

But in this case you know the comparison will be false anyway, so you can just push a constant.

Comment 17

[Tom S [:evilpie]]

Okay will fix #1.
But i am not quite sure about the second one, for example if someone does typeof {} == "object", we should emit true, but can because it might be an function object. So i think the easiest thing would be to do. Or did it misunderstand something?

>(fused == JSOP_STRING && !fe->isTypeKnwon())

Thanks for review.

Comment 18

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

In your case, "object" isn't detected, so if you know |fe| is typed as an object, then it's not any of the types you handle.

But you can just skip this case too :)

Comment 19

[Tom S [:evilpie]]

Attachment: v5

Comment 20

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

Nice, thanks!

Comment 21

[Sean Stangl [:sstangl]]

(In reply to comment #19)

x64 does not need to clobber a register. Instead, we should use JSC's scratchRegister by implementing a setPtr() that takes an immPtr argument for x64.

Comment 22

[Brendan Eich [:brendan]]

Comment on attachment 487397 [details] [diff] [review]
v5

>+#if defined JS_CPU_X86
>+                if (frame.shouldAvoidTypeRemat(fe))
>+                    masm.set32(cond, masm.tagOf(frame.addressOf(fe)), ImmType(type), result);
>+                else
>+                    masm.set32(cond, frame.tempRegForType(fe), ImmType(type), result);
>+#elif defined JS_CPU_X64
>+                RegisterID maskReg = frame.allocReg();
>+                masm.move(ImmType(type), maskReg);
>+
>+                RegisterID r = frame.tempRegForType(fe);
>+                masm.setPtr(cond, r, maskReg, result);
>+
>+                frame.freeReg(maskReg);
>+#endif

Is there a missing #else/#error here, or does ARM work without any extra code?

/be

Comment 23

[Sean Stangl [:sstangl]]

(In reply to comment #22)
> Is there a missing #else/#error here, or does ARM work without any extra code?
Yes, we want JS_NUNBOX32 and JS_PUNBOX64.

Comment 24

[Brendan Eich [:brendan]]

Comment on attachment 487397 [details] [diff] [review]
v5

Do what sstangl said and r? for a fast r+, I hope.

/be

Comment 25

[Tom S [:evilpie]]

Attachment: v6

Hope i got this right, i just replaced the two compiler directives.

Comment 26

[Sean Stangl [:sstangl]]

Attachment: v6 with x64 setPtr(), no clobber.

Comment 27

[Tom S [:evilpie]]

Attachment: v6 with x64 setPtr(), no clobber [thanks sstangl]

Comment 28

[Boris Zbarsky [:bzbarsky]]

Do we need a TM version of this bug?

Comment 29

[Tom S [:evilpie]]

>Do we need a TM version of this bug?
Don't known, for me it looks like, TM bakes in the types at record time.

Anyway, can somebody commit this patch or do you only accept fixes at the moment?

Comment 30

[Brendan Eich [:brendan]]

Comment on attachment 487703 [details] [diff] [review]
v6 with x64 setPtr(), no clobber [thanks sstangl]

This looks good to me for Fx4/Moz2.

/be

Comment 31

[Boris Zbarsky [:bzbarsky]]

> TM bakes in the types at record time.

TM bakes in the LHS at record time.  It still does the string compare, as far as I can tell.

Please file a followup bug on making a similar change to TM?

Comment 32

[Tom S [:evilpie]]

Okay filled bug 613967. Don't want to suck, but how is the approval going?

Comment 33

[Boris Zbarsky [:bzbarsky]]

sayrer's your approval-man.

Comment 34

[Tom S [:evilpie]]

Okay made some really stupid mistake.

Could somebody just change 
> if (op == JSOP_STRICTEQ || op == JSOP_EQ || JSOP_STRICTNE || op == JSOP_NE) {
to
> if (op == JSOP_STRICTEQ || op == JSOP_EQ || op == JSOP_STRICTNE || op == JSOP_NE) {

and commit it?

Comment 35

[David Mandelin [:dmandelin]]

http://hg.mozilla.org/tracemonkey/rev/8c5f62e68881

includes fix in comment 34.

Comment 36

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/8c5f62e68881