Bug 98898 - Support op_typeof in the DFG
Summary: Support op_typeof in the DFG
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Oliver Hunt
URL:
Keywords:
Depends on: 106415
Blocks:
  Show dependency treegraph
 
Reported: 2012-10-10 06:57 PDT by Valery Ignatyev
Modified: 2013-01-08 22:33 PST (History)
5 users (show)

See Also:


Attachments
patch with fix (10.68 KB, patch)
2012-10-10 06:58 PDT, Valery Ignatyev
fpizlo: review-
buildbot: commit-queue-
Details | Formatted Diff | Diff
patch (7.66 KB, patch)
2012-10-16 06:55 PDT, Valery Ignatyev
buildbot: commit-queue-
Details | Formatted Diff | Diff
test_patch (8.86 KB, patch)
2012-10-25 03:45 PDT, Valery Ignatyev
buildbot: commit-queue-
Details | Formatted Diff | Diff
test_patch (9.70 KB, patch)
2012-10-31 06:17 PDT, Valery Ignatyev
no flags Details | Formatted Diff | Diff
Patch (17.77 KB, patch)
2012-12-11 14:20 PST, Oliver Hunt
no flags Details | Formatted Diff | Diff
Patch (18.08 KB, patch)
2012-12-11 14:46 PST, Oliver Hunt
no flags Details | Formatted Diff | Diff
Patch (20.63 KB, patch)
2012-12-11 17:31 PST, Oliver Hunt
no flags Details | Formatted Diff | Diff
Patch (20.72 KB, patch)
2012-12-12 17:57 PST, Oliver Hunt
no flags Details | Formatted Diff | Diff
Patch (31.66 KB, patch)
2013-01-08 18:28 PST, Oliver Hunt
no flags Details | Formatted Diff | Diff
Patch (31.43 KB, patch)
2013-01-08 18:33 PST, Oliver Hunt
fpizlo: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Valery Ignatyev 2012-10-10 06:57:27 PDT
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
Comment 1 Valery Ignatyev 2012-10-10 06:58:43 PDT
Created attachment 167992 [details]
patch with fix
Comment 2 Alexey Proskuryakov 2012-10-10 11:05:01 PDT
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).
Comment 3 Build Bot 2012-10-10 12:52:13 PDT
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
Comment 4 Filip Pizlo 2012-10-10 13:32:27 PDT
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.
Comment 5 Valery Ignatyev 2012-10-16 06:55:38 PDT
Created attachment 168940 [details]
patch

Everything fixed according to the review.
Comment 6 Build Bot 2012-10-16 08:28:01 PDT
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
Comment 7 Valery Ignatyev 2012-10-25 03:45:16 PDT
Created attachment 170602 [details]
test_patch
Comment 8 Build Bot 2012-10-25 14:51:52 PDT
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
Comment 9 Valery Ignatyev 2012-10-26 01:45:04 PDT
(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.
Comment 10 Filip Pizlo 2012-10-26 01:53:32 PDT
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.
Comment 11 Valery Ignatyev 2012-10-31 06:17:54 PDT
Created attachment 171631 [details]
test_patch
Comment 12 Build Bot 2012-10-31 11:49:10 PDT
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
Comment 13 Valery Ignatyev 2012-11-01 03:17:07 PDT
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?
Comment 14 Oliver Hunt 2012-12-11 14:20:32 PST
Created attachment 178875 [details]
Patch
Comment 15 Filip Pizlo 2012-12-11 14:33:27 PST
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.
Comment 16 Oliver Hunt 2012-12-11 14:46:13 PST
Created attachment 178883 [details]
Patch
Comment 17 Oliver Hunt 2012-12-11 17:31:46 PST
Created attachment 178931 [details]
Patch
Comment 18 Filip Pizlo 2012-12-12 16:20:19 PST
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
Comment 19 Oliver Hunt 2012-12-12 16:25:20 PST
(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?
Comment 20 Filip Pizlo 2012-12-12 17:24:26 PST
(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.
Comment 21 Oliver Hunt 2012-12-12 17:57:17 PST
Created attachment 179170 [details]
Patch
Comment 22 Oliver Hunt 2012-12-13 16:33:51 PST
Committed r137683: <http://trac.webkit.org/changeset/137683>
Comment 23 Filip Pizlo 2012-12-13 19:15:04 PST
This breaks gmail (insta-crash).
Comment 24 Filip Pizlo 2012-12-13 19:18:13 PST
Rolled out in http://trac.webkit.org/changeset/137699
Comment 25 Filip Pizlo 2012-12-13 20:06:49 PST
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
Comment 26 Oliver Hunt 2013-01-08 18:28:22 PST
Created attachment 181816 [details]
Patch
Comment 27 Oliver Hunt 2013-01-08 18:33:24 PST
Created attachment 181817 [details]
Patch
Comment 28 Oliver Hunt 2013-01-08 18:38:45 PST
Committed r139145: <http://trac.webkit.org/changeset/139145>