BytecodeGenerator ".call" and ".apply" is exponential in nesting depth
authorsbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 18 Apr 2017 06:43:54 +0000 (06:43 +0000)
committersbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 18 Apr 2017 06:43:54 +0000 (06:43 +0000)
commita8e793ee2069bb2e219dc9f545c69b72418f275d
tree4d879baf576c46098ca1349bbdf30816c7671a29
parent4948e9a321d240e06732267494f4f2a145773218
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, 2^n, 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):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@215453 268f45cc-cd09-0410-ab3c-d52691b4dbfc
JSTests/ChangeLog
JSTests/stress/call-apply-exponential-bytecode-size.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp
Source/JavaScriptCore/parser/ASTBuilder.h
Source/JavaScriptCore/parser/NodeConstructors.h
Source/JavaScriptCore/parser/Nodes.h
Source/JavaScriptCore/parser/Parser.cpp
Source/JavaScriptCore/parser/Parser.h
Source/JavaScriptCore/parser/SyntaxChecker.h