770309 - IonMonkey: Fuse polymorphic ICs with polymorphic inlining

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

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

v8-deltablue has a pattern like:

for (...) {
   c = ...
   c.execute();
}

Where we've determined that |c.execute| only has a few possible values, and we inline through each possible value by guarding on the function identity. We can do better though, in that we should be able to eliminate both the property load and the function identity guard. The shape guard (or in our case, a TypeObject guard) alone should be enough to determine whether we can inline. See methodjit/Compiler.cpp!jsop_getprop_dispatch for details.

Comment 1

[Kannan Vijayan [:djvj]]

Attachment: WIP-ish patch for this

Current patch for doing this.  It works, but it's somewhat compilation heavy due to some hefty ResumePoint manipulation and lots of extra block-creation (which creates more resume points).

I want to rework this to use a single conceptual instruction that does a multi-way branch, instead of sequencing a series of guard blocks for each inlined function.  I expect this to make the code simpler, easier to read and understand, and easier to adapt for future modeifications (like Bug 772049 coming up).

Until then, here is the current working patch.

Comment 2

[Kannan Vijayan [:djvj]]

Attachment: Rework Polymorphic Inlining: Add PolyInlineDispatch Instruction

First step in rework:

Change the original polymorphic inlining code to use a single PolyInlineDispatch instruction to do the dispatching instead of multiple InlineFunctionGuard instructions in their own guard basic blocks.

I've split these into 3 patches for readability's sake:
1. Add the PolyInlineDispatch instruction
2. Change IonBuilder to use PolyInlineDispatch instead of InlineFunctionGuard
3. Remove the InlineFunctionGuard instruction

Comment 3

[Kannan Vijayan [:djvj]]

Attachment: Rework Polymorphic Inlining: Change IonBuilder to use PolyInlineDispatch instead of InlineFunctionGuard

Comment 4

[Kannan Vijayan [:djvj]]

Attachment: Rework Polymorphic Inlining: Remove InlineFunctionGuard instruction.

Comment 5

[Jan de Mooij [:jandem]]

Comment on attachment 641137 [details] [diff] [review]
Rework Polymorphic Inlining: Add PolyInlineDispatch Instruction

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

Nice

::: js/src/ion/CodeGenerator.cpp
@@ +210,5 @@
> +
> +    for(size_t i = 0; i < mir->numCases(); i++) {
> +        JSFunction *func = mir->getFunction(i);
> +        LBlock *target = mir->getSuccessor(i)->lir();
> +        if(i < mir->numCases() - 1) {

Super nit: space between if/for and (.

@@ +214,5 @@
> +        if(i < mir->numCases() - 1) {
> +            Label guardFailed;
> +            masm.cmpPtr(inputReg, ImmGCPtr(func));
> +            masm.j(Assembler::NotEqual, &guardFailed);
> +            masm.jump(target->label());

masm.branchPtr(Assembler::Equal, inputReg, ImmGCPtr(func), target->label());

And fall-through if it's not equal.

::: js/src/ion/MIR.h
@@ +990,5 @@
> +    struct Entry {
> +        CompilerRootFunction func;
> +        MBasicBlock *block;
> +        MConstant *funcConst;
> +        MDefinition *thisDefn;

I assume funcConst and thisDefn will be used in another patch?

@@ +1030,5 @@
> +    static MPolyInlineDispatch *New(MDefinition *ins) {
> +        return new MPolyInlineDispatch(ins);
> +    }
> +
> +    size_t numCases() const {

Nit: numCallees/addCallee seems slightly more descriptive.

Comment 6

[Jan de Mooij [:jandem]]

Comment on attachment 641138 [details] [diff] [review]
Rework Polymorphic Inlining: Change IonBuilder to use PolyInlineDispatch instead of InlineFunctionGuard

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

r=me with comments addressed.

::: js/src/ion/IonBuilder.cpp
@@ +2786,3 @@
>                               MDefinitionVector &argv, MBasicBlock *bottom,
>                               Vector<MDefinition *, 8, IonAllocPolicy> &retvalDefns,
> +                             int polyCase)

Nit: maybe calleeIndex?

@@ +2997,5 @@
> +                if (!thisDefn)
> +                    return false;
> +            } else {
> +                thisDefn = argv[0];
> +            }

In the |constructing| case, this will always create |this| values for all constructors. Can we move this (no pun intended) back to jsop_call_inline or did it have other problems?

@@ +3000,5 @@
> +                thisDefn = argv[0];
> +            }
> +
> +            // Add case to PolyInlineDispatch
> +            disp->addCase(func, NULL, constFun, thisDefn);

Nit: if func will always correspond with constFun, we can get the JSFunction * from the MConstant so that we don't have to store both.

Comment 7

[Jan de Mooij [:jandem]]

Comment on attachment 641139 [details] [diff] [review]
Rework Polymorphic Inlining: Remove InlineFunctionGuard instruction.

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

Thanks for splitting this up, a lot easier to review!

Comment 8

[Kannan Vijayan [:djvj]]

Attachment: First stab.

Explanation of the approach:

1. In the builder for jsop_getprop(), if processing a JSOP_CALLPROP, the site is examined to see if we can infer a partial table mapping TypeObjects for the object to JSFunction constants for the result.  This table is stored within the GetPropertyCache instruction itself.

2. When we reach an inlineable call site, we the MDefinition that defines the callee function.  If this MDefinition is either an annotated GetPropertyCache, or derive from an annotated GetPropertyCache (via a TypeBarrier and Unbox), and there are no users of the callee function (which guarantees that no ResumePoints have captured the callee between the CALLPROP for the GetPropertyCache and the CALL we're inlining), then we choose to change the inlining method from guarding on the callee to guarding on the target object's typeobjects.

3. The remaining changes all relate to adding a fallback block to MPolyInlineDispatch.  There are a few major issues that arise from this:

a) BY the time we arrive at the JSOP_CALL, we've already processed the JSOP_CALLPROP and any intervening bytecode to generate the arguments.  These definitions are pushed on the stack.  Any new block created at this point would automatically capture the GetPropertyCache in its EntryResumePoint, which will make eliminating it difficult.

b) Even if we do eliminate the GetPropertyCache, the IonBuilder's "current PC" when we inline is now well past the PC of the GetPropertyCache.  This means that naively adding a GetPropertyCache to the fallback block will cause correctness issues if the GetPropertyCache ever induces a bailout - since it'll return to the wrong PC, and will have the wrong stack (because the call arguments will be pushed).

To avoid these issues, the following somewhat convoluted procedure is adopted:

i) In the block for the CALL, the stack entry for the function callee is replaced with a constant Undefined.  This is OK because in each entry block to the inlined functions, this stack slot (and the corresponding slot in the EntryResumePoint) is replaced with the MConstant for their respective JSFunctions.

ii) The fallback block is split up into 3 sections: fallbackPredBlock, fallbackMidBlock, and fallbackEndBlock.

iii) fallbackPredBlock does nothing but pop the argument MDefinitions, as well as the callee MDefinition, off of the abstract stack, and performs a GOTO to fallbackMidBlock.

iv) fallbackMidBlock is created with its PC being that of the JSOP_CALLPROP that generated the GetPropertyCache.  Since it inherits it stack from fallbackPredBlock, its stack is in the correct form.  These two properties mean that if it bails, it'll bail out to the location of the JSOP_CALLPROP with the correct stack.  This block does the GetPropertyCache, re-pushes the argument MDefinitions, and executes a GOTO to fallbackEndBlock.

v) fallbackEndBlock is created with the "regular pc" corresponding to the call.  It'll inherit the correct stack from fallbackMidBlock.  This block adds the MPrepareCall, MPassArgs, and does the call.

The rest of the code should be relatively straightforward from the comments and the procedure above.

I hope this is not too confusing or weird.

Comment 9

[Jan de Mooij [:jandem]]

Comment on attachment 644460 [details] [diff] [review]
First stab.

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

Resetting review flag, will review the updated patch.

Comment 10

[Kannan Vijayan [:djvj]]

Attachment: Stab 2.

Changed MGetPropertyCache to hold a pointer to the table of TypeObject => JSFunction mappings, so as to not waste space on the majority of MGetPropertyCache instructions that don't serve as precursors to inline call dispatches.

Also, fixed an additional bug where snapshots weren't getting taken properly for the fallback block.  This requires taking an early MResumePoint snapshot at the time of the MGetPropertyCache creation (but not attaching it to anything), and then later attaching it as the entryResumePoint for the poly-inline-call fallback block.

This is necessary because it's the only reasonable way to capture the stack state at the point of the MGetPropertyCache and transport it forward to the fallback block when we are in inlineScriptedCall.

Comment 11

[Jan de Mooij [:jandem]]

Comment on attachment 646415 [details] [diff] [review]
Stab 2.

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

Nice work. Most comments are just nits but some require some larger changes so I think another review would be good.

Can you also add some tests for the different cases, like both with fallback block and without?

::: js/src/ion/IonBuilder.cpp
@@ +2908,5 @@
>      return true;
>  }
>  
>  bool
> +IonBuilder::CheckInlineableGetPropertyCache(uint32_t argc, MGetPropertyCache **getPropCachePtr)

Nit: you can change the return type to MGetPropertyCache * and return NULL if not inlineable.

@@ +2954,5 @@
> +        return true;
> +    }
> +
> +    // Check for MUnbox[MIRType_Object, Infallible] <- MTypeBarrier <- MGetPropertyCache
> +    if (!funcDefn->isUnbox() || funcDefn->toUnbox()->useCount() > 0)

Nit: you can remove the useCount() > 0 check here, the |if| below checks it too.

@@ +2961,5 @@
> +    MUnbox *unbox = current->peek(funcDefnDepth)->toUnbox();
> +    if (unbox->useCount() > 0 ||
> +        unbox->mode() != MUnbox::Infallible ||
> +        !unbox->input()->isTypeBarrier())
> +        return false;

Nit: braces around the body since the condition spans multiple lines.

@@ +2974,5 @@
> +    // Check that there are inline cases to consider.
> +    if (getPropCache->numInlineCases() == 0)
> +        return false;
> +
> +    // Ensure ethat the input to the GetPropertyCache is the thisDefn for this function.

Nit: s/ethat/that.

@@ +3047,5 @@
> +        MGetPropertyCache *newGetPropCache = MGetPropertyCache::New(cx, getPropCache);
> +        fallbackBlock->add(newGetPropCache);
> +
> +        JS_ASSERT(getPropCache->useCount() == 0);
> +        getPropCache->block()->discard(getPropCache);

Instead of adding a new instruction you can add a new method MBasicBlock::moveTo (or something) similar to MBasicBlock::moveBefore.

Then you can just do

getPropCache->block()->moveTo(fallbackBlock, getPropCache);

And something similar for the else-branch. This also means you can remove the MGetPropertyCache::New method.

@@ +3111,5 @@
> +        int32 argno = argc - i;
> +        MDefinition *argDefn = fallbackEndBlock->pop();
> +        JS_ASSERT(!argDefn->isPassArg());
> +        MPassArg *passArg = MPassArg::New(argDefn);
> +        if (!passArg)

Nit: no need to NULL-check the return value, the memory ballast ensures this won't fail.

@@ +3131,5 @@
> +
> +    MBasicBlock *top = current;
> +    current = fallbackEndBlock;
> +    if (!pushTypeBarrier(call, types, barrier)) {
> +        current = top;

Nit: I don't think we have to set |current| in this case, OOM will abort compilation.

@@ +3258,5 @@
> +            graph_.moveBlockToEnd(disp->getFallbackMidBlock());
> +            graph_.moveBlockToEnd(disp->getFallbackEndBlock());
> +
> +            MBasicBlock *fallbackEndBlock = disp->getFallbackEndBlock();
> +            JS_ASSERT(fallbackEndBlock != NULL);

Nit: if fallbackEndBlock is NULL, the code below will crash immediately. In these cases we don't assert non-NULL.

@@ +3324,5 @@
> +        // Check the depth change:
> +        //  -argc for popped args
> +        //  -2 for callee/this
> +        //  +1 for retval
> +        JS_ASSERT(bottom->stackDepth() == origStackDepth - argc - 1);

Is it possible to move this assert after the current if-else (and rename "bottom" to "current"), so that it checks both branches?

@@ +5405,5 @@
> +            continue;
> +        }
> +
> +        if (!targetFunctions.append(obj))
> +                return false;

Style nit: indentation seems off, maybe a tab instead of spaces.

@@ +5420,5 @@
> +        return false;
> +
> +    // Check was successful, annotate the GetPropertyCache.
> +    for (unsigned int i = 0; i < objCount; i++) {
> +        if (targetFunctions[i] == NULL)

Can we merge this loop with the previous loop? JM can't do that because the second loop emits code (so we can't give up in the middle of it) but I think it's okay here and it would avoid having to add NULL to targetFunctions.

@@ +5434,5 @@
> +        // as an invalidation in objTypes.  However, this is NOT the case, as a protoType might
> +        // change from a mapping to one function in objTypes to another function also in objTypes,
> +        // which I'm guessing would not trigger an invalidation, but would render the guard logic
> +        // incorrect.  So I'm guessing we need to freeze on these as well.
> +        protoTypes->addFreeze(cx);

This shouldn't be necessary, the getSingleton(cx) call below will add a constraint to recompile if the result of getSingleton would change, and the getProperty(cx, id, false) ensures the script is recompiled if the property is removed or something.

@@ +5465,5 @@
> +        MResumePoint *resumePoint = MResumePoint::New(current, pc, callerResumePoint_,
> +                                                      MResumePoint::ResumeAt);
> +        if (!resumePoint)
> +            return false;
> +        getPropCache->setPriorResumePoint(resumePoint);

As you said on IRC, this should handle the GetPropCache resumepoint as well.

::: js/src/ion/IonBuilder.h
@@ +405,5 @@
>      inline bool TestCommonPropFunc(JSContext *cx, types::TypeSet *types,
>                                     HandleId id, JSFunction **funcp, 
>                                     bool isGetter);
>  
> +    bool AnnotateGetPropertyCache(JSContext *cx, MDefinition *obj, MGetPropertyCache *getPropCache,

Style nit: first letter should be lowercase for class methods, uppercase for functions not in a class (TestCommonPropFunc should have been testCommonPropFunc too), also below.

::: js/src/ion/MIR.h
@@ +941,5 @@
>  
> +    void setSuccessor(size_t i, MBasicBlock *successor) {
> +        JS_ASSERT(i < numSuccessors());
> +        if (getPropCache_ && (i == numSuccessors() - 1)) {
> +            fallbackPrepBlock_ = successor;

Nit: single-line condition and bodies so no braces

@@ +966,5 @@
> +    }
> +
> +    MBasicBlock *getSuccessor(size_t i) const {
> +        JS_ASSERT(i < numSuccessors());
> +        if (getPropCache_ && (i == numSuccessors() - 1)) {

Style nit: then and else branches fit on a single line so no braces needed.

@@ +1022,5 @@
> +    MGetPropertyCache *getPropertyCache() const {
> +        return getPropCache_;
> +    }
> +
> +    MBasicBlock *getFallbackPrepBlock() const {

Style nit: s/getFallback../fallback..

@@ +4015,3 @@
>        : MUnaryInstruction(obj),
>          name_(name),
> +        idempotent_(false),

As discussed on IRC, it would be cool if we could move all extra members and methods to a new class and store a pointer to that in GetPropertyCache. Saves some memory but also separates the inlining data from the GetProp operation.

::: js/src/ion/MIRGraph.cpp
@@ +191,5 @@
>                  if (!phi->addInput(pred->getSlot(i)))
>                      return NULL;
>                  addPhi(phi);
>                  setSlot(i, phi);
> +                if (!resumePointExists)

Nit: can you instead JS_ASSERT(!resumePointExists); right before this loop?

Comment 12

[Kannan Vijayan [:djvj]]

Attachment: Third try

Patch with requested changes addressed.

Additionally fixed an issue with construction of correct snapshots.  The previous patch ran into a recently added assert ensuring that resume point stack states matched up with the expected stack for the resume point's PC.

This revealed some errors where the correct stack state wasn't getting initialized before capturing resume points.

In particular, the bytecode generated for |foo.bar(arg1, arg2)|
looks something like:

<bytecode for |foo|>
dup
callprop "bar"
swap
<byte code for |arg1|>
<byte code for |arg2|>
call

The resume point prior to the callprop should have two copies of |foo| on the stack.  And moreover, to move between the stack state immediately before the getprop and immediately before the call is more than just a matter of pushing/popping the appropriate definitions.

The fix for this was to capture additional resume points at the appropriate locations that captured the stack state, and to add a mechanism for creating blocks using those resume points' stack state as their initial stack.

Comment 13

[Jan de Mooij [:jandem]]

Comment on attachment 647213 [details] [diff] [review]
Third try

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

Looks great, mostly style nits remaining. r=me with the comments addressed.

This really needs tests though, at least for the fallback path and ideally also for bailouts using the various resume points.

::: js/src/ion/IonBuilder.cpp
@@ +2944,5 @@
> +    if (funcDefn->isGetPropertyCache()) {
> +        MGetPropertyCache *getPropCache = funcDefn->toGetPropertyCache();
> +        JS_ASSERT(getPropCache->object()->type() == MIRType_Object);
> +
> +        if (getPropCache->useCount() > 0)

Don't we also need the "if (getPropCache->object() != thisDefn) check" here too, like below? It would be good to factor the GetPropertyCache checks out to a new function and call it here and below.

@@ +3052,5 @@
> +    // The fallbackBlock inherits the state of the stack right before the getprop, which
> +    // means we have to pop off the target of the getprop before performing it.
> +#ifdef DEBUG
> +    MDefinition *checkTargetObject = fallbackBlock->pop();
> +    JS_ASSERT(checkTargetObject == targetObject);

Nit: this can be

DebugOnly<MDefinition *> checkTargetObject = fallbackBlock->pop();
JS_ASSERT(checkTargetObject == targetObject);

::: js/src/ion/IonBuilder.h
@@ +408,5 @@
>  
> +    bool annotateGetPropertyCache(JSContext *cx, MDefinition *obj, MGetPropertyCache *getPropCache,
> +                                  types::TypeSet *objTypes, types::TypeSet *pushedTypes);
> +
> +    MGetPropertyCache *CheckInlineableGetPropertyCache(uint32_t argc);

Nit: lower-case first letter.

@@ +411,5 @@
> +
> +    MGetPropertyCache *CheckInlineableGetPropertyCache(uint32_t argc);
> +
> +    MPolyInlineDispatch *
> +    MakePolyInlineDispatch(JSContext *cx, AutoObjectVector &targets, int argc,

Ditto.

::: js/src/ion/MIR.h
@@ +3849,5 @@
> +    jsbytecode *pc_;
> +    MResumePoint *priorResumePoint_;
> +    Vector<Entry, 4, IonAllocPolicy> entries_;
> +
> +public:

Nit: indent with two spaces.

@@ +3858,5 @@
> +        JS_ASSERT(priorResumePoint_ == NULL);
> +        priorResumePoint_ = resumePoint;
> +    }
> +
> +    MResumePoint *priorResumePoint() const { return priorResumePoint_; }

Nit: body and end brace should have their own line, also for the other methods (there are different styles but this is what most of IM uses).

Comment 14

[Kannan Vijayan [:djvj]]

https://hg.mozilla.org/projects/ionmonkey/rev/bb67e083fb01