Last Comment Bug 717466 - IonMonkey: Compile JSOP_INSTANCEOF
: IonMonkey: Compile JSOP_INSTANCEOF
Status: RESOLVED FIXED
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: All All
: -- normal with 1 vote (vote)
: ---
Assigned To: kosver
:
: Jason Orendorff [:jorendorff]
Mentors:
Depends on:
Blocks: 684381
  Show dependency treegraph
 
Reported: 2012-01-11 16:52 PST by kosver
Modified: 2012-06-13 20:35 PDT (History)
3 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
WIP (15.80 KB, patch)
2012-01-12 15:10 PST, kosver
no flags Details | Diff | Splinter Review
v1 (16.71 KB, patch)
2012-01-12 18:09 PST, kosver
no flags Details | Diff | Splinter Review
v2 (21.10 KB, patch)
2012-03-07 13:00 PST, kosver
no flags Details | Diff | Splinter Review
v3 (21.29 KB, patch)
2012-03-15 13:43 PDT, kosver
no flags Details | Diff | Splinter Review
v4 (16.08 KB, patch)
2012-04-18 08:36 PDT, kosver
no flags Details | Diff | Splinter Review
v5 (16.41 KB, patch)
2012-04-20 05:50 PDT, kosver
no flags Details | Diff | Splinter Review
Forgot to add testcase (2.23 KB, patch)
2012-04-20 05:56 PDT, kosver
no flags Details | Diff | Splinter Review
v6 (18.65 KB, patch)
2012-04-20 16:49 PDT, kosver
dvander: review+
Details | Diff | Splinter Review

Description kosver 2012-01-11 16:52:53 PST
We still need to implement JSOP_INSTANCEOF.
Comment 1 kosver 2012-01-12 15:10:57 PST
Created attachment 588204 [details] [diff] [review]
WIP
Comment 2 kosver 2012-01-12 18:09:38 PST
Created attachment 588271 [details] [diff] [review]
v1

Ready for review, but will first let it rest. Maybe I come up with a defect.

Typeof is implemented with type policy for objects. All the rest will fold into MConstant(false). It is written in asm, except for the GetProperty. It works for function and bound functions.

So this patch 
- creates MTypeof, LTypeofO
- abstracts OutOfLineGetPropertyCache so every opcode can use it (LTypeofO needs to access PropertyCache)
- add option for making ObjectPolicy only unbox Value and Object. (So MTypeof can unfold non-object types to false.)
Comment 3 kosver 2012-01-13 11:27:48 PST
I've also made a version with callVM and checked performance. 
- asm: 4.1s for 350.000 iterations
- callVM: 4.5s for 350.000 iterations
So it's worth to keep the asm.
Comment 4 David Anderson [:dvander] 2012-02-29 18:30:05 PST
Comment on attachment 588271 [details] [diff] [review]
v1

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

Patch is definitely on the right track! Comments below are mostly about instanceof semantics, which are surprisingly tricky.

::: js/src/ion/CodeGenerator.cpp
@@ +1043,5 @@
> +    // Check Function
> +    masm.bind(&checkFunction);
> +    masm.loadBaseShape(protoShape, proto);
> +    masm.cmpPtr(Operand(proto, BaseShape::offsetOfClass()), ImmWord(&js::FunctionClass));
> +    masm.j(Assembler::NotEqual, &returnFalse);

If only it were this easy :D the not-function case is harder to handle, because you have to call [[HasInstance]]. There's a few possibilities here.

Idea 1: If we determined earlier that the operation is not effectful (i.e. we guaranteed the rhs was a function), then you can opt to not generate this code. Otherwise, the "returnFalse" path should go to an OutOfLine path that callVMs to a HasInstance(JSContext *, const Value &, JSObject *) call or something.

Idea 2: Split InstanceOf into two IRs, at the MIR and LIR level: CallInstanceOf (which will always use a callVM), and InstanceOf which does this code here.

I personally prefer #1 since you've mostly written all the code for it already :)

::: js/src/ion/IonBuilder.cpp
@@ +3136,5 @@
> +    MInstanceof *ins = new MInstanceof(obj, proto, script, pc);
> +    current->add(ins);
> +    current->push(ins);
> +    
> +    return true;

The "instanceof" spec says that we must call [[HasInstance]] on the rhs. For functions, that looks up .prototype, which is a special property - it cannot be reconfigured, and it's always a normal slot. That means if the rhs is a function, instanceof is not effectful - but otherwise, we must assume arbitrary things could happen. That means a call to resumeAfter(pc) is needed, so we don't accidentally re-execute the instanceof operation.

Unfortunately, marking instanceof effectful means it can't be hoisted or eliminated. But we can optimize a little. For earley-boyer, TI can always tell us that the exact function represented by the rhs:

TypeOracle::BinaryTypes b = oracle->binaryTypes(script, pc);
if (b.rhsTypes) {
    if (JSObject *singleton = b.rhsTypes->getSingleton(cx)) {
        if (singleton->isFunction()) {
            ....
    }
}

In this case, we can leave off the resumeAfter(pc), and the AliasSet can be ObjectFields|Slot instead of All.

::: js/src/ion/LIR-Common.h
@@ +1134,4 @@
>      }
>  };
>  
> +class LInstanceofO : public LInstructionHelper<1, 2, 2>

LInstanceof0 -> LInstanceOf

::: js/src/ion/LOpcodes.h
@@ +109,5 @@
>      _(CallGetName)                  \
>      _(CallGetNameTypeOf)            \
>      _(ArrayLength)                  \
> +    _(StringLength)                 \
> +    _(InstanceofO)

Instanceof0 -> InstanceOf

::: js/src/ion/MIR.cpp
@@ +784,5 @@
> +MInstanceof::foldsTo(bool useValueNumbers)
> +{
> +    // instanceOf with a primitive is always false
> +    if (obj()->type() != MIRType_Object || proto()->type() != MIRType_Object) {
> +        return MConstant::New(BooleanValue(false));

|primitive in x| might be a valid folding, but |x in primitive| is not since an error has to be reported. I'd just remove this function to be safe - if you wanted, you could check ECMAScript to see if we need to call [[HasInstance]] for a primitive lhs.

::: js/src/ion/MIR.h
@@ +2497,4 @@
>      }
>  };
>  
> +class MInstanceof 

MInstanceof -> MInstanceOf

@@ +2522,5 @@
> +
> +    MDefinition *foldsTo(bool useValueNumbers);
> +
> +    MDefinition *obj() const {
> +        return getOperand(0);

This is really just the right-hand side, it's not necessarily an object (in fact earley-boyer often passes a string). See comments on the TypePolicy.

@@ +2526,5 @@
> +        return getOperand(0);
> +    }
> +
> +    MDefinition *proto() const {
> +        return getOperand(1);

"obj" would be better here than "proto" since it could be an arbitrary object.

@@ +2530,5 @@
> +        return getOperand(1);
> +    }
> +
> +    JSScript *script() const {
> +        return script_;

Instead of storing the script here, you can use block()->info().script()

@@ +2537,5 @@
> +        return pc_;
> +    }
> +    
> +    virtual AliasSet getAliasSet() const {
> +        return AliasSet::None();

See comments in IonBuilder - this can't be None, unfortunately.

::: js/src/ion/TypePolicy.h
@@ +127,5 @@
> +  protected:
> +    // If this is set to True, this will only unbox when input is Value or Object-type
> +    // Else it will unbox Value and convert primitive with ValueToNonNullObject
> +    // Default: false
> +    bool leaveNonObjects_;

Instead of these changes to ObjectPolicy, could you just introduce an InstanceOfPolicy? The simplest thing to do is ensure that the lhs is a box, and the rhs is an object.

This means a few little things in the LIR will have to change: the number of inputs will be BOX_PIECES + 1, and you'll need a check that the LHS value is actually an object (if it's not, the result of the expression is just false).
Comment 5 kosver 2012-03-07 13:00:17 PST
Created attachment 603831 [details] [diff] [review]
v2

I've looked into ECMAScript reference and it states that only function objects has [[HasInstance]] (p34 ECMASCRIPT 5.1). So actually my patch was on the right track. In short: ECMAScript describes two different implementations of the [[HasInstance]], one for bound functions and one for other fuctions. The bound functions simply call the [[HasInstance]] of its bound function and the other version has an algo for going over the prototype chain. When the rhs is neither (so it will have no HasInstance), it should generate a TypeError. I've updated the code so it bailouts.

Also both implementations return false when lhs isn't an object, so I've kept the fastpath.

I've updated the code so it uses the new version of OutOfLineCaches.

Because the code uses an OutOfLineCache and bailout, it is forced to have an resumepoint and safepoint. That implies that the opcode becomes is effective. (bummer)

On the upside, I've eliminated the use of 1 temporary register, without loss of speed. 

ready for review
Comment 6 David Anderson [:dvander] 2012-03-07 13:04:06 PST
In SpiderMonkey, other things have [[HasInstance]] hooks: XML objects, proxies, something related to generators - maybe things in the browser too since we expose [[HasInstance]] of hooks as an API, but I'm not sure who uses it.
Comment 7 kosver 2012-03-09 16:07:58 PST
(In reply to David Anderson [:dvander] from comment #6)
> In SpiderMonkey, other things have [[HasInstance]] hooks: XML objects,
> proxies, something related to generators - maybe things in the browser too
> since we expose [[HasInstance]] of hooks as an API, but I'm not sure who
> uses it.

Ah, okay. Didn't know there was so much that used it. Though my patch should handle it, it bailouts for non-functions. Will update the patch tomorrow-evening (I hope), so ionmonkey also can call HasInstance. If this bug is in a hotline, it can always be reviewed and I can make a follow-up bug/patch...
Comment 8 kosver 2012-03-15 13:43:17 PDT
Created attachment 606343 [details] [diff] [review]
v3

Same as v2 but with CallVM to HasInstance when object isn't a function.
So ready for review.
Comment 9 David Anderson [:dvander] 2012-04-04 18:53:51 PDT
Comment on attachment 606343 [details] [diff] [review]
v3

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

Getting close! Some problems remain with folding.

::: js/src/ion/CodeGenerator.cpp
@@ +1999,5 @@
> +    switch (ins->op()) {
> +      case LInstruction::LOp_Instanceof:
> +        atom = GetIonContext()->cx->runtime->atomState.classPrototypeAtom;
> +  		objReg = ToRegister(ins->getOperand(1));
> +  		output = TypedOrValueRegister(MIRType_Object, ToAnyRegister(ins->getDef(0)));

nit: some hard-tabs leaked in here and below

::: js/src/ion/LIR-Common.h
@@ +2332,5 @@
> +        return getDef(0);
> +    }
> +    
> +    static const size_t LHS = 0;
> +    static const size_t RHS = 1;

Nit: I'd just remove these and hardcode 0 and 1 above, since you already have the lhs()/rhs() calls.

::: js/src/ion/Lowering.cpp
@@ +1403,5 @@
> +    JS_ASSERT(lhs->type() != MIRType_Value && rhs->type() == MIRType_Object);
> +
> +    // Instanceof with non-object will always return false
> +    if (lhs->type() != MIRType_Object) {
> +        return define(new LInteger(0), ins);

This folding is not allowed if we don't know whether the RHS is a function.

::: js/src/ion/MIR.cpp
@@ +975,5 @@
> +    JS_ASSERT(rhs()->type() == MIRType_Object);
> +    
> +    // instanceOf with a primitive is always false
> +    if (lhs()->type() != MIRType_Object) {
> +        return MConstant::New(BooleanValue(false));

This folding is only allowed if the RHS is known to be a function.

::: js/src/ion/TypePolicy.cpp
@@ +375,5 @@
> +InstanceofPolicy::adjustInputs(MInstruction *def)
> +{
> +    // Unbox first operand (to Object if type is unknown)
> +    if (def->getOperand(0)->type() == MIRType_Value) {
> +        adjustInput(def,0);

This LHS type policy won't work after you've removed the folding. Two suggestions (there are probably other things that work too):
 (1) Always box this input, then make the LIR take in a box instead. Then you'll need to do a primitive test and unbox in the generated code. Your patch is close to this already.
 (2) You could also try to decompose a little more and split everything into two cases.
   (a) Type Inference tells you the right-hand side is an object.
     i. Emit a function guard.
     ii. Emit MInstanceOf, then you can keep the constant folding and get rid of the OOL
         path.
   (b) Nothing known about RHS - emit MCallInstanceOf as a slow case.
Comment 10 kosver 2012-04-18 08:36:28 PDT
Created attachment 616155 [details] [diff] [review]
v4

I've implemented (1), but made a distinction when LHS is an object or not. So when TI returns Object, it will not box. I've not done (2) because (1) with Value will probably be faster on the occasionally function object.

In a followup path/bug I will to implement a fastpath for function objects with a function guard. So this will be (2) but with ASM instead of HasInstanceCall in (b).
Comment 11 kosver 2012-04-20 05:50:00 PDT
Created attachment 616944 [details] [diff] [review]
v5

Still the same version as v4, but now succeeds all tests (in 32bit and 64bit, didn't try arm)
Comment 12 kosver 2012-04-20 05:56:19 PDT
Created attachment 616945 [details] [diff] [review]
Forgot to add testcase
Comment 13 kosver 2012-04-20 16:49:41 PDT
Created attachment 617141 [details] [diff] [review]
v6

Fixed an issue. Now the instanceof will also work on the full v8 benchmark.
Comment 14 David Anderson [:dvander] 2012-06-13 15:33:41 PDT
Comment on attachment 617141 [details] [diff] [review]
v6

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

Looks great, thank you for doing this! We're almost ready to land a bunch of scope work and this now blocks earley-boyer performance. I'll apply the nits below and checkin for you today.

::: js/src/ion/CodeGenerator.cpp
@@ +3012,5 @@
> +    Label HasInstanceCall;    
> +    Label HasInstanceBoundFunction;    
> +    Label HasInstanceFunction;    
> +    Label ret;
> +    Label goOn;

nits: these names are a little better:
  callHasInstance,
  boundFunctionCheck,
  boundFunctionDone,
  done

and goOn can be moved inside the if statement where it's used.

@@ +3124,5 @@
> +    pushArg(rhs);
> +    if (!callVM(FHasInstance, ins))
> +        return false;
> +    masm.storeCallResult(output);
> +    restoreLive(ins);

This should be in an out-of-line path.

::: js/src/ion/IonBuilder.cpp
@@ +4242,5 @@
> +IonBuilder::jsop_instanceof()
> +{
> +    MDefinition *proto = current->pop();
> +    MDefinition *obj = current->pop();
> +    MInstanceof *ins = new MInstanceof(obj, proto);

nit: s/Instanceof/InstanceOf/ (applies to whole patch)

::: js/src/ion/TypePolicy.cpp
@@ +386,5 @@
> +{
> +    // Box first operand if it isn't object
> +    if (def->getOperand(0)->type() != MIRType_Object) {
> +       BoxPolicy<0>::staticAdjustInputs(def);
> +    }

Nit: braces aren't needed here

::: js/src/ion/VMFunctions.cpp
@@ +191,5 @@
>  }
>  
> +bool 
> +CallHasInstance(JSContext *cx, JSObject *obj, const Value &v, JSBool *bp){
> +    *bp = false; 

nit: { on new line, initialization of  *bp isn't needed.
Comment 15 Paul Wright 2012-06-13 15:37:00 PDT
(In reply to David Anderson [:dvander] from comment #14)
> Comment on attachment 617141 [details] [diff] [review]
> v6
> 
> Review of attachment 617141 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Looks great, thank you for doing this! We're almost ready to land a bunch of
> scope work 
> 

Which bugs should I be looking at to follow this scope work?
Comment 16 David Anderson [:dvander] 2012-06-13 20:35:46 PDT
https://hg.mozilla.org/projects/ionmonkey/rev/fd561e74aeda

(In reply to Paul Wright from comment #15)
> Which bugs should I be looking at to follow this scope work?

bug 761685 is where it starts on the IonMonkey side

Note You need to log in before you can comment on or make changes to this bug.