Bug 98898 – Support op_typeof in the DFG

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Valery Ignatyev]

Allows to apply DFG on functions with typeof. Replace Typeof DFG node with appropriate constant using profile data.
Atrificial example:
function f() {
    var i,s;
    for (i = 0; i < 1000000000; i++) {
      var k = [];
  	  s = typeof(k);
    }
  return s;
}

without patch
real	0m51.053s
user	0m50.963s
sys	0m0.068s

with patch
real	0m1.960s
user	0m1.948s
sys	0m0.008s

[Valery Ignatyev]

Created attachment 167992 [details]
patch with fix

[Alexey Proskuryakov]

Is this patch ready for review? If so, please mark it as "review?" by going to Details view (link is to the right from the patch).

[Build Bot]

Comment on attachment 167992 [details]
patch with fix

Attachment 167992 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/14253344

New failing tests:
fast/workers/worker-close-more.html
fast/js/JSON-parse.html

[Filip Pizlo]

Comment on attachment 167992 [details]
patch with fix

View in context: https://bugs.webkit.org/attachment.cgi?id=167992&action=review

> Source/JavaScriptCore/dfg/DFGAbstractState.cpp:1545
> +    case Typeof:
> +        node.setCanExit(true);
> +        m_foundConstants = true;
> +        break;

This should at the *very least* say forNode(nodeIndex).set(SpecString).  At this point you have no knowledge of what Typeof will return.

And as I say in comments in ConstantFolding, this should do type casing to see if we can prove Typeof away.

> Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:2941
> +            NEXT_OPCODE(op_new_func_exp);

This should be NEXT_OPCODE(op_new_func_exp)

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:114
> +                SpeculatedType child = m_graph[node.child1()].prediction();

You meant m_state.forNode(node.child1()).m_type.

The prediction is unsound - it's just what we *thing* that the node *might* be, rather than what we *know* the node *to* be.

If you want to optimize Typeof based on predictions, then it cause Typeof to get compiled into a speculation check followed by the relevant constant.

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:126
> +                if (isObjectSpeculation(child))
> +                    value = JSValue(jsString(&m_graph.m_globalData, String("object")));
> +                else if (isNumberSpeculation(child))
> +                    value = JSValue(jsString(&m_graph.m_globalData, String("number")));
> +                else if (isStringSpeculation(child))
> +                    value = JSValue(jsString(&m_graph.m_globalData, String("string")));
> +                else if (isFunctionSpeculation(child))
> +                    value = JSValue(jsString(&m_graph.m_globalData, String("function")));
> +                else if (isBooleanSpeculation(child))
> +                    value = JSValue(jsString(&m_graph.m_globalData, String("boolean")));

This does not belong here.  Prediction-based optimizations should be done in Fixup rather than ConstantFolding.  But, as I say above, the fact that you're doing a prediction-based optimization is probably wrong.

You should take this code and move it to AbstractState so that the CFA can fixpoint on it.

Probably the right thing is to have both:

1) If the predictions say Blah then Fixup should emit a node to speculate Blah and then emit the constant node in place of the Typeof.

2) If the proofs (i.e. AbstractState) say Blah then the AbstractState will use logic like the thing you have above to mark the Typeof node as being known-constant, and then constant folding will just do the right things.

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:133
> +                    Node foe(ForceOSRExit, node.codeOrigin);
> +                    foe.setRefCount(1);
> +                    NodeIndex foeNodeIndex = m_graph.size();
> +                    m_graph.append(foe);
> +                    m_insertionSet.append(indexInBlock - 1, foeNodeIndex);
> +                    break;

I don't like this at all.  Why not just have the Typeof node call a C function if it's not optimized out?

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:188
> +                Node& child1 = m_graph[node.child1()];
> +                if (child1.op() == GetLocal) {
> +                    NodeIndex previousLocalAccess = NoNode;
> +                    if (block->variablesAtHead.operand(child1.local()) == node.child1()
> +                        && m_graph[child1.child1()].op() == Phi) {
> +                    // We expect this to be the common case.
> +                        ASSERT(block->isInPhis(child1.child1().index()));
> +                        previousLocalAccess = child1.child1().index();
> +                        block->variablesAtHead.operand(child1.local()) = previousLocalAccess;
> +                    } else {
> +                        ASSERT(indexInBlock - 1 > 0);
> +                        // Must search for the previous access to this local.
> +                        for (BlockIndex subIndexInBlock = indexInBlock - 1 ; subIndexInBlock--;) {
> +                            NodeIndex subNodeIndex = block->at(subIndexInBlock);
> +                            Node& subNode = m_graph[subNodeIndex];
> +                            if (!subNode.shouldGenerate())
> +                                continue;
> +                            if (!subNode.hasVariableAccessData())
> +                                continue;
> +                            if (subNode.local() != child1.local())
> +                                continue;
> +                            // The two must have been unified.
> +                            ASSERT(subNode.variableAccessData() == child1.variableAccessData());
> +                            previousLocalAccess = subNodeIndex;
> +                            break;
> +                        }
> +                        if (previousLocalAccess == NoNode) {
> +                            // The previous access must have been a Phi.
> +                            for (BlockIndex phiIndexInBlock = block->phis.size(); phiIndexInBlock--;) {
> +                                NodeIndex phiNodeIndex = block->phis[phiIndexInBlock];
> +                                Node& phiNode = m_graph[phiNodeIndex];
> +                                if (!phiNode.shouldGenerate())
> +                                    continue;
> +                                if (phiNode.local() != child1.local())
> +                                    continue;
> +                                // The two must have been unified.
> +                                ASSERT(phiNode.variableAccessData() == child1.variableAccessData());
> +                                previousLocalAccess = phiNodeIndex;
> +                                break;
> +                            }
> +                            ASSERT(previousLocalAccess != NoNode);
> +                        }
> +                    }
> +
> +                    ASSERT(previousLocalAccess != NoNode);
> +                    NodeIndex tailNodeIndex = block->variablesAtTail.operand(child1.local());
> +                    if (tailNodeIndex == node.child1())
> +                        block->variablesAtTail.operand(child1.local()) = previousLocalAccess;
> +                    else {
> +                        ASSERT(m_graph[tailNodeIndex].op() == Flush);
> +                        ASSERT(m_graph[tailNodeIndex].op() == SetLocal);
> +                    }
> +                    child1.setOpAndDefaultFlags(Phantom);

Are you duplicating code here?  Why?

And why are you killing the GetLocal child of the Typeof node?

> Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp:689
> +        }
> +            break;

break; should be inside the { }.

> Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp:4287
> +    case Typeof:
> +        ASSERT_NOT_REACHED();
> +        break;

As I said in my comments in ConstantFolding, the fall back for Typeof should be a procedure call.

[Valery Ignatyev]

Created attachment 168940 [details]
patch

Everything fixed according to the review.

[Build Bot]

Comment on attachment 168940 [details]
patch

Attachment 168940 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/14386164

New failing tests:
fast/workers/worker-close-more.html

[Valery Ignatyev]

Created attachment 170602 [details]
test_patch

[Build Bot]

Comment on attachment 170602 [details]
test_patch

Attachment 170602 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/14566772

New failing tests:
fast/workers/worker-close-more.html

[Valery Ignatyev]

(In reply to comment #8)
> (From update of attachment 170602 [details])
> Attachment 170602 [details] did not pass mac-ews (mac):
> Output: http://queues.webkit.org/results/14566772
> 
> New failing tests:
> fast/workers/worker-close-more.html

Can anybody help me to fix bug in the patch?
I have no idea where to look. I can't write any simple test with error.
'run-webkit-test' shows to much failing tests, maybe by reason of incorrect setup.

[Filip Pizlo]

Comment on attachment 170602 [details]
test_patch

View in context: https://bugs.webkit.org/attachment.cgi?id=170602&action=review

I think you're almost there.  You just need a solution to *really weird* the object-is-undefined and object-is-function cases.

When you do so, be careful about the possibility that doing what jsTypeStringForValue() would cause side-effects.  In fact, I don't think you can do the whole getCallData() thing without a call frame (you don't really have a call frame in the JIT - I mean, I think we pass one in, but it's not really meant to be used because it can be in a pretty weird state since we're in the middle of OSR), and I'm pretty sure that it can have weird side effects.

> Source/JavaScriptCore/dfg/DFGAbstractState.cpp:699
> +    case Typeof: {
> +        JSValue child = forNode(node.child1()).value();
> +        if (child) {
> +            bool constantWasSet = false;
> +            SpeculatedType type = forNode(node.child1()).m_type;
> +            if (isObjectSpeculation(type))
> +                constantWasSet = trySetConstant(nodeIndex, jsString(&m_graph.m_globalData, String("object")));
> +            else if (isNumberSpeculation(type))
> +                constantWasSet = trySetConstant(nodeIndex, jsString(&m_graph.m_globalData, String("number")));
> +            else if (isStringSpeculation(type))
> +                constantWasSet = trySetConstant(nodeIndex, jsString(&m_graph.m_globalData, String("string")));
> +            else if (isFunctionSpeculation(type))
> +                constantWasSet = trySetConstant(nodeIndex, jsString(&m_graph.m_globalData, String("function")));
> +            else if (isBooleanSpeculation(type))
> +                constantWasSet = trySetConstant(nodeIndex, jsString(&m_graph.m_globalData, String("boolean")));
> +
> +            if (constantWasSet) {
> +                m_foundConstants = true;
> +                break;
> +            }
> +        }
> +        forNode(nodeIndex).set(SpecString);
> +        break;
> +    }

This is mostly right.  You've written it in the right form and style.  But, it has a bug: you're not matching the behavior of jsTypeStringForValue:

JSValue jsTypeStringForValue(CallFrame* callFrame, JSValue v)
{
    JSGlobalData& globalData = callFrame->globalData();
    if (v.isUndefined())
        return globalData.smallStrings.undefinedString(&globalData);
    if (v.isBoolean())
        return globalData.smallStrings.booleanString(&globalData);
    if (v.isNumber())
        return globalData.smallStrings.numberString(&globalData);
    if (v.isString())
        return globalData.smallStrings.stringString(&globalData);
    if (v.isObject()) {
        // Return "undefined" for objects that should be treated
        // as null when doing comparisons.
        if (asObject(v)->structure()->masqueradesAsUndefined(callFrame->lexicalGlobalObject()))
            return globalData.smallStrings.undefinedString(&globalData);
        CallData callData;
        JSObject* object = asObject(v);
        if (object->methodTable()->getCallData(object, callData) != CallTypeNone)
            return globalData.smallStrings.functionString(&globalData);
    }
    return globalData.smallStrings.objectString(&globalData);
}

In particular, if you have an object constant, you still need to check if it masquerades as undefined, or if it's callable.  Even things that aren't functions can pretend to be, by providing a call trap.

[Valery Ignatyev]

Created attachment 171631 [details]
test_patch

[Build Bot]

Comment on attachment 171631 [details]
test_patch

Attachment 171631 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/14693202

New failing tests:
fast/workers/worker-close-more.html

[Valery Ignatyev]

I've tried to fix the problem, and think that the last patch performs conservative replacement with the constant.
I didn't completely understand, when the object can pretend to be a function. Can you please provide an example? Is it concerned with valueOf?

>  CallData callData;
>  JSObject* object = asObject(v);
>  if (object->methodTable()->getCallData(object, callData) != CallTypeNone)
>      return globalData.smallStrings.functionString(&globalData);
Also I didn't find any way to emulate this behaviour without 'getCallData'.
I found that 'CallTypeNone' returns only 'InternalFunction' and 'JSCell'.

And the last one question. Is it possible to run the failing test without all testing enviroment? If so, how to do it? Is it necessary to run it on Mac?

[Oliver Hunt]

Created attachment 178875 [details]
Patch

[Filip Pizlo]

Comment on attachment 178875 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=178875&action=review

You're almost there.  Just fix the CFA (AbstractState) to filter the same way that the codegen speculates.

> Source/JavaScriptCore/dfg/DFGAbstractState.cpp:736
> +        node.setCanExit(true);
> +        forNode(nodeIndex).set(SpecString);

Somewhere in here you should filter according to the speculations that the codegen does.  Like, if codegen speculates cell, this should filter cell.  Same for string, etc.

[Oliver Hunt]

Created attachment 178883 [details]
Patch

[Oliver Hunt]

Created attachment 178931 [details]
Patch

[Filip Pizlo]

Comment on attachment 178931 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=178931&action=review

> Source/JavaScriptCore/dfg/DFGAbstractState.cpp:715
> +            case IsObject:
> +                if (child.isNull() || !child.isObject()) {
> +                    constantWasSet = trySetConstant(nodeIndex, jsBoolean(child.isNull()));
> +                    break;
> +                }

Can you add the same smarts you added for TypeOf to the IsThingies?

> Source/JavaScriptCore/dfg/DFGAbstractState.cpp:749
> +        if (isStringSpeculation(abstractChild.m_type)) {

else if

> Source/JavaScriptCore/dfg/DFGAbstractState.cpp:756
> +        if (isFinalObjectSpeculation(abstractChild.m_type) || isArraySpeculation(abstractChild.m_type) || isArgumentsSpeculation(abstractChild.m_type)) {

ditto

> Source/JavaScriptCore/dfg/DFGAbstractState.cpp:763
> +        if (isFunctionSpeculation(abstractChild.m_type)) {

ditto

> Source/JavaScriptCore/dfg/DFGAbstractState.cpp:770
> +        if (isBooleanSpeculation(abstractChild.m_type)) {

ditto

[Oliver Hunt]

(In reply to comment #18)
> (From update of attachment 178931 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=178931&action=review
> 
> > Source/JavaScriptCore/dfg/DFGAbstractState.cpp:715
> > +            case IsObject:
> > +                if (child.isNull() || !child.isObject()) {
> > +                    constantWasSet = trySetConstant(nodeIndex, jsBoolean(child.isNull()));
> > +                    break;
> > +                }
> 
> Can you add the same smarts you added for TypeOf to the IsThingies?

When I did, things started to get slower.  I wanted to deal with them separately because my assumption is that i'll need to change their codegen as well and i'd rather not conflate that with this patch.

> 
> > Source/JavaScriptCore/dfg/DFGAbstractState.cpp:749
> > +        if (isStringSpeculation(abstractChild.m_type)) {
> 
> else if
> 
> > Source/JavaScriptCore/dfg/DFGAbstractState.cpp:756
> > +        if (isFinalObjectSpeculation(abstractChild.m_type) || isArraySpeculation(abstractChild.m_type) || isArgumentsSpeculation(abstractChild.m_type)) {
> 
> ditto
> 
> > Source/JavaScriptCore/dfg/DFGAbstractState.cpp:763
> > +        if (isFunctionSpeculation(abstractChild.m_type)) {
> 
> ditto
> 
> > Source/JavaScriptCore/dfg/DFGAbstractState.cpp:770
> > +        if (isBooleanSpeculation(abstractChild.m_type)) {
> 
> ditto

K, i'd gone for not using the else as it seemed that in the general case break would have prevented those paths from going further.  Incidentally when can trySetConstant fail?

[Filip Pizlo]

(In reply to comment #19)
> (In reply to comment #18)
> > (From update of attachment 178931 [details] [details])
> > View in context: https://bugs.webkit.org/attachment.cgi?id=178931&action=review
> > 
> > > Source/JavaScriptCore/dfg/DFGAbstractState.cpp:715
> > > +            case IsObject:
> > > +                if (child.isNull() || !child.isObject()) {
> > > +                    constantWasSet = trySetConstant(nodeIndex, jsBoolean(child.isNull()));
> > > +                    break;
> > > +                }
> > 
> > Can you add the same smarts you added for TypeOf to the IsThingies?
> 
> When I did, things started to get slower.  I wanted to deal with them separately because my assumption is that i'll need to change their codegen as well and i'd rather not conflate that with this patch.
> 
> > 
> > > Source/JavaScriptCore/dfg/DFGAbstractState.cpp:749
> > > +        if (isStringSpeculation(abstractChild.m_type)) {
> > 
> > else if
> > 
> > > Source/JavaScriptCore/dfg/DFGAbstractState.cpp:756
> > > +        if (isFinalObjectSpeculation(abstractChild.m_type) || isArraySpeculation(abstractChild.m_type) || isArgumentsSpeculation(abstractChild.m_type)) {
> > 
> > ditto
> > 
> > > Source/JavaScriptCore/dfg/DFGAbstractState.cpp:763
> > > +        if (isFunctionSpeculation(abstractChild.m_type)) {
> > 
> > ditto
> > 
> > > Source/JavaScriptCore/dfg/DFGAbstractState.cpp:770
> > > +        if (isBooleanSpeculation(abstractChild.m_type)) {
> > 
> > ditto
> 
> K, i'd gone for not using the else as it seemed that in the general case break would have prevented those paths from going further.  Incidentally when can trySetConstant fail?

When the proven constant value is different from the predicted value.  There's no way to say that a constant has a different prediction than the speculated type you wouldn't compute for that constant.

This can happen due to inlining.  We guard against it by simply not constant propagating over those pathologies.

[Oliver Hunt]

Created attachment 179170 [details]
Patch

[Oliver Hunt]

Committed r137683: <http://trac.webkit.org/changeset/137683>

[Filip Pizlo]

This breaks gmail (insta-crash).

[Filip Pizlo]

Rolled out in http://trac.webkit.org/changeset/137699

[Filip Pizlo]

It also looks like this had set the bots on fire with loads of crashes:

http://build.webkit.org/results/Apple%20Lion%20Debug%20WK1%20(Tests)/r137685%20(5317)/results.html

[Oliver Hunt]

Created attachment 181816 [details]
Patch

[Oliver Hunt]

Created attachment 181817 [details]
Patch

[Oliver Hunt]

Committed r139145: <http://trac.webkit.org/changeset/139145>

[Ryosuke Niwa]

It appears that this patch broke two worker tests:
http://test-results.appspot.com/dashboards/flakiness_dashboard.html#group=%40ToT%20-%20webkit.org&tests=fast%2Fworkers%2Fworker-close-more.html%2Cfast%2Fworkers%2Fworker-lifecycle.html

http://build.webkit.org/results/Apple%20MountainLion%20Release%20WK2%20(Tests)/r139154%20(4586)/results.html

fast/workers/worker-close-more.html and fast/workers/worker-lifecycle.html