Changeset 215453 in webkit


Ignore:
Timestamp:
Apr 17, 2017 11:43:54 PM (7 years ago)
Author:
sbarati@apple.com
Message:

BytecodeGenerator ".call" and ".apply" is exponential in nesting depth
​https://bugs.webkit.org/show_bug.cgi?id=139847
<rdar://problem/19321122>

Reviewed by Oliver Hunt.

JSTests:

  • stress/call-apply-exponential-bytecode-size.js: Added.

(assert):
(const.inc):
(const.inc2):
(bar):
(randomApplyOrCall):
(baz):
(jaz):
(haz):
(foo):

Source/JavaScriptCore:

The BytecodeGenerator's .apply(...) and .call(...) code would
emit bytecode for the evaluation of its arguments twice. This
is exponential, specifically, 2n, where n is the nesting depth of
.call(...) or .apply(...) inside other .call(...) or .apply(...).

The reason we emit code for the arguments twice is that we try
to emit efficient code for when .call or .apply is Function.prototype.call
or Function.prototype.apply. Because of this, we compare .call/.apply to
Function.prototype.call/.apply, and if they're the same, we emit a specialized
function call in bytecode. Otherwise, we emit the generalized version.

This patch makes it so that each .call(...) and .apply(...) records
its max inner nesting depth. Then, we only perform the optimization
for the bottom k (where k = 6) layers of the nesting tree. The reason we
apply the optimization to the bottom k layers instead of top k layers
is that we'll produce less code this way.

  • bytecompiler/NodesCodegen.cpp:

(JSC::CallFunctionCallDotNode::emitBytecode):
(JSC::ApplyFunctionCallDotNode::emitBytecode):

  • parser/ASTBuilder.h:

(JSC::ASTBuilder::makeFunctionCallNode):

  • parser/NodeConstructors.h:

(JSC::CallFunctionCallDotNode::CallFunctionCallDotNode):
(JSC::ApplyFunctionCallDotNode::ApplyFunctionCallDotNode):

  • parser/Nodes.h:
  • parser/Parser.cpp:

(JSC::recordCallOrApplyDepth):
(JSC::Parser<LexerType>::parseMemberExpression):

  • parser/Parser.h:

(JSC::Parser::CallOrApplyDepth::CallOrApplyDepth):
(JSC::Parser::CallOrApplyDepth::maxChildDepth):
(JSC::Parser::CallOrApplyDepth::~CallOrApplyDepth):

  • parser/SyntaxChecker.h:

(JSC::SyntaxChecker::makeFunctionCallNode):

Location:
trunk
Files:
1 added
9 edited

Legend:

Unmodified
Added
Removed

  • trunk/JSTests/ChangeLog

    r215451 r215453  
     12017-04-17  Saam Barati  <sbarati@apple.com>
     2
     3        BytecodeGenerator ".call" and ".apply" is exponential in nesting depth
     4        https://bugs.webkit.org/show_bug.cgi?id=139847
     5        <rdar://problem/19321122>
     6
     7        Reviewed by Oliver Hunt.
     8
     9        * stress/call-apply-exponential-bytecode-size.js: Added.
     10        (assert):
     11        (const.inc):
     12        (const.inc2):
     13        (bar):
     14        (randomApplyOrCall):
     15        (baz):
     16        (jaz):
     17        (haz):
     18        (foo):
     19
    1202017-04-17  Mark Lam  <mark.lam@apple.com>
    221

  • trunk/Source/JavaScriptCore/ChangeLog

    r215451 r215453  
     12017-04-17  Saam Barati  <sbarati@apple.com>
     2
     3        BytecodeGenerator ".call" and ".apply" is exponential in nesting depth
     4        https://bugs.webkit.org/show_bug.cgi?id=139847
     5        <rdar://problem/19321122>
     6
     7        Reviewed by Oliver Hunt.
     8
     9        The BytecodeGenerator's .apply(...) and .call(...) code would
     10        emit bytecode for the evaluation of its arguments twice. This
     11        is exponential, specifically, 2^n, where n is the nesting depth of
     12        .call(...) or .apply(...) inside other .call(...) or .apply(...).
     13       
     14        The reason we emit code for the arguments twice is that we try
     15        to emit efficient code for when .call or .apply is Function.prototype.call
     16        or Function.prototype.apply. Because of this, we compare .call/.apply to
     17        Function.prototype.call/.apply, and if they're the same, we emit a specialized
     18        function call in bytecode. Otherwise, we emit the generalized version.
     19       
     20        This patch makes it so that each .call(...) and .apply(...) records
     21        its max inner nesting depth. Then, we only perform the optimization
     22        for the bottom k (where k = 6) layers of the nesting tree. The reason we
     23        apply the optimization to the bottom k layers instead of top k layers
     24        is that we'll produce less code this way.
     25
     26        * bytecompiler/NodesCodegen.cpp:
     27        (JSC::CallFunctionCallDotNode::emitBytecode):
     28        (JSC::ApplyFunctionCallDotNode::emitBytecode):
     29        * parser/ASTBuilder.h:
     30        (JSC::ASTBuilder::makeFunctionCallNode):
     31        * parser/NodeConstructors.h:
     32        (JSC::CallFunctionCallDotNode::CallFunctionCallDotNode):
     33        (JSC::ApplyFunctionCallDotNode::ApplyFunctionCallDotNode):
     34        * parser/Nodes.h:
     35        * parser/Parser.cpp:
     36        (JSC::recordCallOrApplyDepth):
     37        (JSC::Parser<LexerType>::parseMemberExpression):
     38        * parser/Parser.h:
     39        (JSC::Parser::CallOrApplyDepth::CallOrApplyDepth):
     40        (JSC::Parser::CallOrApplyDepth::maxChildDepth):
     41        (JSC::Parser::CallOrApplyDepth::~CallOrApplyDepth):
     42        * parser/SyntaxChecker.h:
     43        (JSC::SyntaxChecker::makeFunctionCallNode):
     44
    1452017-04-17  Mark Lam  <mark.lam@apple.com>
    246

  • trunk/Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp

    r214931 r215453  
    11901190RegisterID* CallFunctionCallDotNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)
    11911191{
    1192     Ref<Label> realCall = generator.newLabel();
    1193     Ref<Label> end = generator.newLabel();
    11941192    RefPtr<RegisterID> base = generator.emitNode(m_base);
    11951193    generator.emitExpressionInfo(subexpressionDivot(), subexpressionStart(), subexpressionEnd());
    11961194    RefPtr<RegisterID> function;
    1197     bool emitCallCheck = !generator.isBuiltinFunction();
    1198     if (emitCallCheck) {
     1195    RefPtr<RegisterID> returnValue = generator.finalDestination(dst);
     1196
     1197    auto makeFunction = [&] {
    11991198        if (m_base->isSuperNode()) {
    12001199            RefPtr<RegisterID> thisValue = generator.ensureThis();
    … …  
    12021201        } else
    12031202            function = generator.emitGetById(generator.tempDestination(dst), base.get(), generator.propertyNames().builtinNames().callPublicName());
     1203    };
     1204
     1205    bool emitCallCheck = !generator.isBuiltinFunction();
     1206    if (m_callOrApplyChildDepth > 4 && emitCallCheck) {
     1207        makeFunction();
     1208        CallArguments callArguments(generator, m_args);
     1209        generator.emitMove(callArguments.thisRegister(), base.get());
     1210        generator.emitCallInTailPosition(returnValue.get(), function.get(), NoExpectedFunction, callArguments, divot(), divotStart(), divotEnd(), DebuggableCall::Yes);
     1211        generator.moveToDestinationIfNeeded(dst, returnValue.get());
     1212        return returnValue.get();
     1213    }
     1214
     1215    Ref<Label> realCall = generator.newLabel();
     1216    Ref<Label> end = generator.newLabel();
     1217
     1218    if (emitCallCheck) {
     1219        makeFunction();
    12041220        generator.emitJumpIfNotFunctionCall(function.get(), realCall.get());
    12051221    }
    1206     RefPtr<RegisterID> returnValue = generator.finalDestination(dst);
    12071222    {
    12081223        if (m_args->m_listNode && m_args->m_listNode->m_expr && m_args->m_listNode->m_expr->isSpreadExpression()) {
    … …  
    12571272    bool mayBeCall = areTrivialApplyArguments(m_args);
    12581273
    1259     Ref<Label> realCall = generator.newLabel();
    1260     Ref<Label> end = generator.newLabel();
     1274    RefPtr<RegisterID> function;
    12611275    RefPtr<RegisterID> base = generator.emitNode(m_base);
    1262     generator.emitExpressionInfo(subexpressionDivot(), subexpressionStart(), subexpressionEnd());
    1263     RefPtr<RegisterID> function;
    1264     RefPtr<RegisterID> returnValue = generator.finalDestination(dst, function.get());
    1265     bool emitCallCheck = !generator.isBuiltinFunction();
    1266     if (emitCallCheck) {
     1276    RefPtr<RegisterID> returnValue = generator.finalDestination(dst);
     1277    auto makeFunction = [&] {
    12671278        if (m_base->isSuperNode()) {
    12681279            RefPtr<RegisterID> thisValue = generator.ensureThis();
    … …  
    12701281        } else
    12711282            function = generator.emitGetById(generator.tempDestination(dst), base.get(), generator.propertyNames().builtinNames().applyPublicName());
     1283    };
     1284
     1285    bool emitCallCheck = !generator.isBuiltinFunction();
     1286    if (m_callOrApplyChildDepth > 4 && emitCallCheck) {
     1287        makeFunction();
     1288        CallArguments callArguments(generator, m_args);
     1289        generator.emitMove(callArguments.thisRegister(), base.get());
     1290        generator.emitCallInTailPosition(returnValue.get(), function.get(), NoExpectedFunction, callArguments, divot(), divotStart(), divotEnd(), DebuggableCall::Yes);
     1291        generator.moveToDestinationIfNeeded(dst, returnValue.get());
     1292        return returnValue.get();
     1293    }
     1294
     1295    Ref<Label> realCall = generator.newLabel();
     1296    Ref<Label> end = generator.newLabel();
     1297    generator.emitExpressionInfo(subexpressionDivot(), subexpressionStart(), subexpressionEnd());
     1298    if (emitCallCheck) {
     1299        makeFunction();
    12721300        generator.emitJumpIfNotFunctionApply(function.get(), realCall.get());
    12731301    }

  • trunk/Source/JavaScriptCore/parser/ASTBuilder.h

    r215165 r215453  
    130130
    131131    ExpressionNode* makeBinaryNode(const JSTokenLocation&, int token, std::pair<ExpressionNode*, BinaryOpInfo>, std::pair<ExpressionNode*, BinaryOpInfo>);
    132     ExpressionNode* makeFunctionCallNode(const JSTokenLocation&, ExpressionNode* func, ArgumentsNode* args, const JSTextPosition& divotStart, const JSTextPosition& divot, const JSTextPosition& divotEnd);
     132    ExpressionNode* makeFunctionCallNode(const JSTokenLocation&, ExpressionNode* func, ArgumentsNode* args, const JSTextPosition& divotStart, const JSTextPosition& divot, const JSTextPosition& divotEnd, size_t callOrApplyChildDepth);
    133133
    134134    JSC::SourceElements* createSourceElements() { return new (m_parserArena) JSC::SourceElements(); }
    … …  
    13021302}
    13031303
    1304 ExpressionNode* ASTBuilder::makeFunctionCallNode(const JSTokenLocation& location, ExpressionNode* func, ArgumentsNode* args, const JSTextPosition& divotStart, const JSTextPosition& divot, const JSTextPosition& divotEnd)
     1304ExpressionNode* ASTBuilder::makeFunctionCallNode(const JSTokenLocation& location, ExpressionNode* func, ArgumentsNode* args, const JSTextPosition& divotStart, const JSTextPosition& divot, const JSTextPosition& divotEnd, size_t callOrApplyChildDepth)
    13051305{
    13061306    ASSERT(divot.offset >= divot.lineStartOffset);
    … …  
    13341334    FunctionCallDotNode* node;
    13351335    if (dot->identifier() == m_vm->propertyNames->builtinNames().callPublicName() || dot->identifier() == m_vm->propertyNames->builtinNames().callPrivateName())
    1336         node = new (m_parserArena) CallFunctionCallDotNode(location, dot->base(), dot->identifier(), args, divot, divotStart, divotEnd);
     1336        node = new (m_parserArena) CallFunctionCallDotNode(location, dot->base(), dot->identifier(), args, divot, divotStart, divotEnd, callOrApplyChildDepth);
    13371337    else if (dot->identifier() == m_vm->propertyNames->builtinNames().applyPublicName() || dot->identifier() == m_vm->propertyNames->builtinNames().applyPrivateName())
    1338         node = new (m_parserArena) ApplyFunctionCallDotNode(location, dot->base(), dot->identifier(), args, divot, divotStart, divotEnd);
     1338        node = new (m_parserArena) ApplyFunctionCallDotNode(location, dot->base(), dot->identifier(), args, divot, divotStart, divotEnd, callOrApplyChildDepth);
    13391339    else
    13401340        node = new (m_parserArena) FunctionCallDotNode(location, dot->base(), dot->identifier(), args, divot, divotStart, divotEnd);

  • trunk/Source/JavaScriptCore/parser/NodeConstructors.h

    r214038 r215453  
    404404    }
    405405
    406     inline CallFunctionCallDotNode::CallFunctionCallDotNode(const JSTokenLocation& location, ExpressionNode* base, const Identifier& ident, ArgumentsNode* args, const JSTextPosition& divot, const JSTextPosition& divotStart, const JSTextPosition& divotEnd)
     406    inline CallFunctionCallDotNode::CallFunctionCallDotNode(const JSTokenLocation& location, ExpressionNode* base, const Identifier& ident, ArgumentsNode* args, const JSTextPosition& divot, const JSTextPosition& divotStart, const JSTextPosition& divotEnd, size_t callOrApplyChildDepth)
    407407        : FunctionCallDotNode(location, base, ident, args, divot, divotStart, divotEnd)
    408     {
    409     }
    410 
    411     inline ApplyFunctionCallDotNode::ApplyFunctionCallDotNode(const JSTokenLocation& location, ExpressionNode* base, const Identifier& ident, ArgumentsNode* args, const JSTextPosition& divot, const JSTextPosition& divotStart, const JSTextPosition& divotEnd)
     408        , m_callOrApplyChildDepth(callOrApplyChildDepth)
     409    {
     410    }
     411
     412    inline ApplyFunctionCallDotNode::ApplyFunctionCallDotNode(const JSTokenLocation& location, ExpressionNode* base, const Identifier& ident, ArgumentsNode* args, const JSTextPosition& divot, const JSTextPosition& divotStart, const JSTextPosition& divotEnd, size_t callOrApplyChildDepth)
    412413        : FunctionCallDotNode(location, base, ident, args, divot, divotStart, divotEnd)
     414        , m_callOrApplyChildDepth(callOrApplyChildDepth)
    413415    {
    414416    }

  • trunk/Source/JavaScriptCore/parser/Nodes.h

    r214038 r215453  
    885885    class CallFunctionCallDotNode : public FunctionCallDotNode {
    886886    public:
    887         CallFunctionCallDotNode(const JSTokenLocation&, ExpressionNode* base, const Identifier&, ArgumentsNode*, const JSTextPosition& divot, const JSTextPosition& divotStart, const JSTextPosition& divotEnd);
    888 
    889     private:
    890         RegisterID* emitBytecode(BytecodeGenerator&, RegisterID* = 0) override;
     887        CallFunctionCallDotNode(const JSTokenLocation&, ExpressionNode* base, const Identifier&, ArgumentsNode*, const JSTextPosition& divot, const JSTextPosition& divotStart, const JSTextPosition& divotEnd, size_t callOrApplyChildDepth);
     888
     889    private:
     890        RegisterID* emitBytecode(BytecodeGenerator&, RegisterID* = 0) override;
     891        size_t m_callOrApplyChildDepth;
    891892    };
    892893   
    893894    class ApplyFunctionCallDotNode : public FunctionCallDotNode {
    894895    public:
    895         ApplyFunctionCallDotNode(const JSTokenLocation&, ExpressionNode* base, const Identifier&, ArgumentsNode*, const JSTextPosition& divot, const JSTextPosition& divotStart, const JSTextPosition& divotEnd);
    896 
    897     private:
    898         RegisterID* emitBytecode(BytecodeGenerator&, RegisterID* = 0) override;
     896        ApplyFunctionCallDotNode(const JSTokenLocation&, ExpressionNode* base, const Identifier&, ArgumentsNode*, const JSTextPosition& divot, const JSTextPosition& divotStart, const JSTextPosition& divotEnd, size_t callOrApplyChildDepth);
     897
     898    private:
     899        RegisterID* emitBytecode(BytecodeGenerator&, RegisterID* = 0) override;
     900        size_t m_callOrApplyChildDepth;
    899901    };
    900902

  • trunk/Source/JavaScriptCore/parser/Parser.cpp

    r215395 r215453  
    43854385}
    43864386
     4387template <typename TreeBuilder, typename ParserType, typename = typename std::enable_if<std::is_same<TreeBuilder, ASTBuilder>::value>::type>
     4388static inline void recordCallOrApplyDepth(ParserType* parser, VM& vm, std::optional<typename ParserType::CallOrApplyDepth>& callOrApplyDepth, ExpressionNode* expression)
     4389{
     4390    if (expression->isDotAccessorNode()) {
     4391        DotAccessorNode* dot = static_cast<DotAccessorNode*>(expression);
     4392        bool isCallOrApply = dot->identifier() == vm.propertyNames->builtinNames().callPublicName() || dot->identifier() == vm.propertyNames->builtinNames().applyPublicName();
     4393        if (isCallOrApply)
     4394            callOrApplyDepth.emplace(parser);
     4395    }
     4396}
     4397
     4398template <typename TreeBuilder, typename ParserType, typename = typename std::enable_if<std::is_same<TreeBuilder, SyntaxChecker>::value>::type>
     4399static inline void recordCallOrApplyDepth(ParserType*, VM&, std::optional<typename ParserType::CallOrApplyDepth>&, SyntaxChecker::Expression)
     4400{
     4401}
     4402
    43874403template <typename LexerType>
    43884404template <class TreeBuilder> TreeExpression Parser<LexerType>::parseMemberExpression(TreeBuilder& context)
    … …  
    44994515                size_t usedVariablesSize = currentScope()->currentUsedVariablesSize();
    45004516                JSTextPosition expressionEnd = lastTokenEndPosition();
     4517                std::optional<CallOrApplyDepth> callOrApplyDepth;
     4518                recordCallOrApplyDepth<TreeBuilder>(this, *m_vm, callOrApplyDepth, base);
     4519
    45014520                TreeArguments arguments = parseArguments(context);
    45024521
    … …  
    45264545                        functionScope->setInnerArrowFunctionUsesSuperCall();
    45274546                }
    4528                 base = context.makeFunctionCallNode(startLocation, base, arguments, expressionStart, expressionEnd, lastTokenEndPosition());
     4547                base = context.makeFunctionCallNode(startLocation, base, arguments, expressionStart,
     4548                    expressionEnd, lastTokenEndPosition(), callOrApplyDepth ? callOrApplyDepth->maxChildDepth() : 0);
    45294549            }
    45304550            m_parserState.nonLHSCount = nonLHSCount;

  • trunk/Source/JavaScriptCore/parser/Parser.h

    r215395 r215453  
    887887    JSTextPosition positionBeforeLastNewline() const { return m_lexer->positionBeforeLastNewline(); }
    888888    JSTokenLocation locationBeforeLastToken() const { return m_lexer->lastTokenLocation(); }
     889
     890    struct CallOrApplyDepth {
     891        CallOrApplyDepth(Parser* parser)
     892            : m_parser(parser)
     893            , m_parent(parser->m_callOrApplyDepth)
     894            , m_depth(m_parent ? m_parent->m_depth + 1 : 0)
     895            , m_childDepth(m_depth)
     896        {
     897            parser->m_callOrApplyDepth = this;
     898        }
     899
     900        size_t maxChildDepth() const
     901        {
     902            ASSERT(m_childDepth >= m_depth);
     903            return m_childDepth - m_depth;
     904        }
     905
     906        ~CallOrApplyDepth()
     907        {
     908            if (m_parent)
     909                m_parent->m_childDepth = std::max(m_childDepth, m_parent->m_childDepth);
     910            m_parser->m_callOrApplyDepth = m_parent;
     911        }
     912
     913    private:
     914
     915        Parser* m_parser;
     916        CallOrApplyDepth* m_parent;
     917        size_t m_depth;
     918        size_t m_childDepth;
     919    };
    889920
    890921private:
    … …  
    17811812    RefPtr<ModuleScopeData> m_moduleScopeData;
    17821813    DebuggerParseData* m_debuggerParseData;
     1814    CallOrApplyDepth* m_callOrApplyDepth { nullptr };
    17831815
    17841816    struct DepthManager {

  • trunk/Source/JavaScriptCore/parser/SyntaxChecker.h

    r215165 r215453  
    144144
    145145    int createSourceElements() { return SourceElementsResult; }
    146     ExpressionType makeFunctionCallNode(const JSTokenLocation&, int, int, int, int, int) { return CallExpr; }
     146    ExpressionType makeFunctionCallNode(const JSTokenLocation&, int, int, int, int, int, size_t) { return CallExpr; }
    147147    ExpressionType createCommaExpr(const JSTokenLocation&, ExpressionType expr) { return expr; }
    148148    ExpressionType appendToCommaExpr(const JSTokenLocation&, ExpressionType& head, ExpressionType, ExpressionType next) { head = next; return next; }
Note: See TracChangeset for help on using the changeset viewer.