Closed Bug 717466 Opened 12 years ago Closed 12 years ago

IonMonkey: Compile JSOP_INSTANCEOF

Categories

(Core :: JavaScript Engine, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED

People

(Reporter: nikosverschore, Assigned: nikosverschore)

References

(Blocks 1 open bug)

Details

Attachments

(1 file, 7 obsolete files)

We still need to implement JSOP_INSTANCEOF.
Blocks: 684381
Assignee: general → nikosverschore
Status: UNCONFIRMED → NEW
Ever confirmed: true
Attached patch WIP (obsolete) — Splinter Review
Attached patch v1 (obsolete) — Splinter Review
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.)
Attachment #588204 - Attachment is obsolete: true
Attachment #588271 - Flags: review?(dvander)
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 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).
Attachment #588271 - Flags: review?(dvander)
Attached patch v2 (obsolete) — Splinter Review
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
Attachment #588271 - Attachment is obsolete: true
Attachment #603831 - Flags: review?(dvander)
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.
(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...
Attached patch v3 (obsolete) — Splinter Review
Same as v2 but with CallVM to HasInstance when object isn't a function.
So ready for review.
Attachment #603831 - Attachment is obsolete: true
Attachment #603831 - Flags: review?(dvander)
Attachment #606343 - Flags: review?(dvander)
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.
Attached patch v4 (obsolete) — Splinter Review
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).
Attachment #606343 - Attachment is obsolete: true
Attachment #606343 - Flags: review?(dvander)
Attachment #616155 - Flags: review?(dvander)
Attachment #616155 - Flags: review?(dvander)
Attached patch v5 (obsolete) — Splinter Review
Still the same version as v4, but now succeeds all tests (in 32bit and 64bit, didn't try arm)
Attachment #616155 - Attachment is obsolete: true
Attachment #616944 - Flags: review?(dvander)
Attached patch Forgot to add testcase (obsolete) — Splinter Review
Attached patch v6Splinter Review
Fixed an issue. Now the instanceof will also work on the full v8 benchmark.
Attachment #616944 - Attachment is obsolete: true
Attachment #616945 - Attachment is obsolete: true
Attachment #616944 - Flags: review?(dvander)
Attachment #617141 - Flags: review?
Attachment #617141 - Flags: review? → review?(dvander)
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.
Attachment #617141 - Flags: review?(dvander) → review+
(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?
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
Status: NEW → RESOLVED
Closed: 12 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.