<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" /><style type="text/css"><!--
#msg dl { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt;  }
#msg dl a { font-weight: bold}
#msg dl a:link    { color:#fc3; }
#msg dl a:active  { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre, #msg p { overflow: auto; background: #ffc; border: 1px #fc0 solid; padding: 6px; }
#msg ul { overflow: auto; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff  {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<title>[28923] trunk/JavaScriptCore</title>
</head>
<body>

<div id="msg">
<dl>
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/28923">28923</a></dd>
<dt>Author</dt> <dd>ggaren@apple.com</dd>
<dt>Date</dt> <dd>2007-12-20 18:18:11 -0800 (Thu, 20 Dec 2007)</dd>
</dl>

<h3>Log Message</h3>
<pre>        Reviewed by Oliver Hunt.
        
        AST optimization: Avoid NULL-checking ForNode's child nodes.
        
        0.6% speedup on SunSpider.
        
        This is a proof of concept patch that demonstrates how to optimize
        grammar productions with optional components, like
        
            for (optional; optional; optional) {
                ...
            }
            
        The parser emits NULL for an optional component that is not present.

        Instead of checking for a NULL child at execution time, a node that
        expects an optional component to be present more often than not checks
        for a NULL child at construction time, and substitutes a viable
        alternative node in its place.

        (We'd like the parser to start emitting NULL a lot more once we teach
        it to emit NULL for certain no-op productions like EmptyStatement and
        VariableStatement, so, as a foundation, it's important for nodes with
        NULL optional components to be fast.)

        * kjs/Parser.cpp:
        (KJS::Parser::didFinishParsing): Check for NULL SourceElements. Also,
        moved didFinishParsing into the .cpp file because adding a branch while
        it was in the header file caused a substantial and inexplicable
        performance regression. (Did I mention that GCC is crazy?)

        * kjs/grammar.y:

        * kjs/nodes.cpp:
        (KJS::BlockNode::BlockNode): Check for NULL SourceElements.
        (KJS::ForNode::optimizeVariableAccess): No need to check for NULL here.
        (KJS::ForNode::execute): No need to check for NULL here.
        * kjs/nodes.h:
        (KJS::ForNode::): Check for NULL SourceElements. Substitute a TrueNode
        because it's semantically harmless, and it evaluates to boolean in an
        efficient manner.</pre>

<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkJavaScriptCoreChangeLog">trunk/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkJavaScriptCorekjsParsercpp">trunk/JavaScriptCore/kjs/Parser.cpp</a></li>
<li><a href="#trunkJavaScriptCorekjsParserh">trunk/JavaScriptCore/kjs/Parser.h</a></li>
<li><a href="#trunkJavaScriptCorekjsgrammary">trunk/JavaScriptCore/kjs/grammar.y</a></li>
<li><a href="#trunkJavaScriptCorekjsnodescpp">trunk/JavaScriptCore/kjs/nodes.cpp</a></li>
<li><a href="#trunkJavaScriptCorekjsnodesh">trunk/JavaScriptCore/kjs/nodes.h</a></li>
</ul>

</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/JavaScriptCore/ChangeLog (28922 => 28923)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/JavaScriptCore/ChangeLog        2007-12-21 01:31:13 UTC (rev 28922)
+++ trunk/JavaScriptCore/ChangeLog        2007-12-21 02:18:11 UTC (rev 28923)
</span><span class="lines">@@ -1,3 +1,47 @@
</span><ins>+2007-12-20  Geoffrey Garen  &lt;ggaren@apple.com&gt;
+
+        Reviewed by Oliver Hunt.
+        
+        AST optimization: Avoid NULL-checking ForNode's child nodes.
+        
+        0.6% speedup on SunSpider.
+        
+        This is a proof of concept patch that demonstrates how to optimize
+        grammar productions with optional components, like
+        
+            for (optional; optional; optional) {
+                ...
+            }
+            
+        The parser emits NULL for an optional component that is not present.
+
+        Instead of checking for a NULL child at execution time, a node that
+        expects an optional component to be present more often than not checks
+        for a NULL child at construction time, and substitutes a viable
+        alternative node in its place.
+
+        (We'd like the parser to start emitting NULL a lot more once we teach
+        it to emit NULL for certain no-op productions like EmptyStatement and
+        VariableStatement, so, as a foundation, it's important for nodes with
+        NULL optional components to be fast.)
+
+        * kjs/Parser.cpp:
+        (KJS::Parser::didFinishParsing): Check for NULL SourceElements. Also,
+        moved didFinishParsing into the .cpp file because adding a branch while
+        it was in the header file caused a substantial and inexplicable
+        performance regression. (Did I mention that GCC is crazy?)
+
+        * kjs/grammar.y:
+
+        * kjs/nodes.cpp:
+        (KJS::BlockNode::BlockNode): Check for NULL SourceElements.
+        (KJS::ForNode::optimizeVariableAccess): No need to check for NULL here.
+        (KJS::ForNode::execute): No need to check for NULL here.
+        * kjs/nodes.h:
+        (KJS::ForNode::): Check for NULL SourceElements. Substitute a TrueNode
+        because it's semantically harmless, and it evaluates to boolean in an
+        efficient manner.
+
</ins><span class="cx"> 2007-12-20  Oliver Hunt  &lt;oliver@apple.com&gt;
</span><span class="cx"> 
</span><span class="cx">         Reviewed by Geoff.
</span></span></pre></div>
<a id="trunkJavaScriptCorekjsParsercpp"></a>
<div class="modfile"><h4>Modified: trunk/JavaScriptCore/kjs/Parser.cpp (28922 => 28923)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/JavaScriptCore/kjs/Parser.cpp        2007-12-21 01:31:13 UTC (rev 28922)
+++ trunk/JavaScriptCore/kjs/Parser.cpp        2007-12-21 02:18:11 UTC (rev 28923)
</span><span class="lines">@@ -71,6 +71,15 @@
</span><span class="cx">     }
</span><span class="cx"> }
</span><span class="cx"> 
</span><ins>+void Parser::didFinishParsing(SourceElements* sourceElements, ParserRefCountedData&lt;DeclarationStacks::VarStack&gt;* varStack, 
+                              ParserRefCountedData&lt;DeclarationStacks::FunctionStack&gt;* funcStack, int lastLine)
+{
+    m_sourceElements.set(sourceElements ? sourceElements : new SourceElements);
+    m_varDeclarations = varStack;
+    m_funcDeclarations = funcStack;
+    m_lastLine = lastLine;
+}
+
</ins><span class="cx"> Parser&amp; parser()
</span><span class="cx"> {
</span><span class="cx">     ASSERT(JSLock::currentThreadIsHoldingLock());
</span></span></pre></div>
<a id="trunkJavaScriptCorekjsParserh"></a>
<div class="modfile"><h4>Modified: trunk/JavaScriptCore/kjs/Parser.h (28922 => 28923)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/JavaScriptCore/kjs/Parser.h        2007-12-21 01:31:13 UTC (rev 28922)
+++ trunk/JavaScriptCore/kjs/Parser.h        2007-12-21 02:18:11 UTC (rev 28923)
</span><span class="lines">@@ -53,14 +53,8 @@
</span><span class="cx">         UString sourceURL() const { return m_sourceURL; }
</span><span class="cx">         int sourceId() const { return m_sourceId; }
</span><span class="cx"> 
</span><del>-        void didFinishParsing(SourceElements* sourceElements, ParserRefCountedData&lt;DeclarationStacks::VarStack&gt;* varStack, 
-                              ParserRefCountedData&lt;DeclarationStacks::FunctionStack&gt;* funcStack, int lastLine)
-        {
-            m_sourceElements.set(sourceElements);
-            m_varDeclarations = varStack;
-            m_funcDeclarations = funcStack;
-            m_lastLine = lastLine;
-        }
</del><ins>+        void didFinishParsing(SourceElements*, ParserRefCountedData&lt;DeclarationStacks::VarStack&gt;*, 
+                              ParserRefCountedData&lt;DeclarationStacks::FunctionStack&gt;*, int lastLine);
</ins><span class="cx"> 
</span><span class="cx">     private:
</span><span class="cx">         friend Parser&amp; parser();
</span></span></pre></div>
<a id="trunkJavaScriptCorekjsgrammary"></a>
<div class="modfile"><h4>Modified: trunk/JavaScriptCore/kjs/grammar.y (28922 => 28923)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/JavaScriptCore/kjs/grammar.y        2007-12-21 01:31:13 UTC (rev 28922)
+++ trunk/JavaScriptCore/kjs/grammar.y        2007-12-21 02:18:11 UTC (rev 28923)
</span><span class="lines">@@ -696,7 +696,7 @@
</span><span class="cx"> ;
</span><span class="cx"> 
</span><span class="cx"> Block:
</span><del>-    '{' '}'                             { $$ = createNodeInfo&lt;StatementNode*&gt;(new BlockNode(new SourceElements), 0, 0);
</del><ins>+    '{' '}'                             { $$ = createNodeInfo&lt;StatementNode*&gt;(new BlockNode(0), 0, 0);
</ins><span class="cx">                                           DBG($$.m_node, @1, @2); }
</span><span class="cx">   | '{' SourceElements '}'              { $$ = createNodeInfo&lt;StatementNode*&gt;(new BlockNode($2.m_node-&gt;release()), $2.m_varDeclarations, $2.m_funcDeclarations);
</span><span class="cx">                                           DBG($$.m_node, @1, @3); }
</span><span class="lines">@@ -978,7 +978,7 @@
</span><span class="cx"> ;
</span><span class="cx"> 
</span><span class="cx"> FunctionBody:
</span><del>-    /* not in spec */           { $$ = new FunctionBodyNode(new SourceElements, 0, 0); }
</del><ins>+    /* not in spec */           { $$ = new FunctionBodyNode(0, 0, 0); }
</ins><span class="cx">   | SourceElements              { $$ = new FunctionBodyNode($1.m_node-&gt;release(), $1.m_varDeclarations ? &amp;$1.m_varDeclarations-&gt;data : 0, 
</span><span class="cx">                                                                                   $1.m_funcDeclarations ? &amp;$1.m_funcDeclarations-&gt;data : 0);
</span><span class="cx">                                   // As in mergeDeclarationLists() we have to ref/deref to safely get rid of
</span><span class="lines">@@ -995,7 +995,7 @@
</span><span class="cx"> ;
</span><span class="cx"> 
</span><span class="cx"> Program:
</span><del>-    /* not in spec */                   { parser().didFinishParsing(new SourceElements, 0, 0, @0.last_line); }
</del><ins>+    /* not in spec */                   { parser().didFinishParsing(0, 0, 0, @0.last_line); }
</ins><span class="cx">     | SourceElements                    { parser().didFinishParsing($1.m_node-&gt;release(), $1.m_varDeclarations, $1.m_funcDeclarations, @1.last_line); }
</span><span class="cx"> ;
</span><span class="cx"> 
</span></span></pre></div>
<a id="trunkJavaScriptCorekjsnodescpp"></a>
<div class="modfile"><h4>Modified: trunk/JavaScriptCore/kjs/nodes.cpp (28922 => 28923)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/JavaScriptCore/kjs/nodes.cpp        2007-12-21 01:31:13 UTC (rev 28922)
+++ trunk/JavaScriptCore/kjs/nodes.cpp        2007-12-21 02:18:11 UTC (rev 28923)
</span><span class="lines">@@ -3605,7 +3605,7 @@
</span><span class="cx"> // ------------------------------ BlockNode ------------------------------------
</span><span class="cx"> 
</span><span class="cx"> BlockNode::BlockNode(SourceElements* children)
</span><del>-    : m_children(children)
</del><ins>+    : m_children(children ? children : new SourceElements)
</ins><span class="cx"> {
</span><span class="cx">     ASSERT(m_children);
</span><span class="cx"> }
</span><span class="lines">@@ -3772,12 +3772,9 @@
</span><span class="cx"> void ForNode::optimizeVariableAccess(SymbolTable&amp;, DeclarationStacks::NodeStack&amp; nodeStack)
</span><span class="cx"> {
</span><span class="cx">     nodeStack.append(statement.get());
</span><del>-    if (expr3)
-        nodeStack.append(expr3.get());
-    if (expr2)
-        nodeStack.append(expr2.get());
-    if (expr1)
-        nodeStack.append(expr1.get());
</del><ins>+    nodeStack.append(expr3.get());
+    nodeStack.append(expr2.get());
+    nodeStack.append(expr1.get());
</ins><span class="cx"> }
</span><span class="cx"> 
</span><span class="cx"> // ECMA 12.6.3
</span><span class="lines">@@ -3785,18 +3782,14 @@
</span><span class="cx"> {
</span><span class="cx">     JSValue* value = 0;
</span><span class="cx"> 
</span><del>-    if (expr1) {
-        expr1-&gt;evaluate(exec);
-        KJS_CHECKEXCEPTION
-    }
</del><ins>+    expr1-&gt;evaluate(exec);
+    KJS_CHECKEXCEPTION
</ins><span class="cx"> 
</span><span class="cx">     while (1) {
</span><del>-        if (expr2) {
-            bool b = expr2-&gt;evaluateToBoolean(exec);
-            KJS_CHECKEXCEPTION
-            if (!b)
-                break;
-        }
</del><ins>+        bool b = expr2-&gt;evaluateToBoolean(exec);
+        KJS_CHECKEXCEPTION
+        if (!b)
+            break;
</ins><span class="cx"> 
</span><span class="cx">         exec-&gt;pushIteration();
</span><span class="cx">         JSValue* statementValue = statement-&gt;execute(exec);
</span><span class="lines">@@ -3816,10 +3809,8 @@
</span><span class="cx">         }
</span><span class="cx"> 
</span><span class="cx"> continueForLoop:
</span><del>-        if (expr3) {
-            expr3-&gt;evaluate(exec);
-            KJS_CHECKEXCEPTION
-        }
</del><ins>+        expr3-&gt;evaluate(exec);
+        KJS_CHECKEXCEPTION
</ins><span class="cx">     }
</span><span class="cx">   
</span><span class="cx">     return exec-&gt;setNormalCompletion(value);
</span></span></pre></div>
<a id="trunkJavaScriptCorekjsnodesh"></a>
<div class="modfile"><h4>Modified: trunk/JavaScriptCore/kjs/nodes.h (28922 => 28923)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/JavaScriptCore/kjs/nodes.h        2007-12-21 01:31:13 UTC (rev 28922)
+++ trunk/JavaScriptCore/kjs/nodes.h        2007-12-21 02:18:11 UTC (rev 28923)
</span><span class="lines">@@ -1818,13 +1818,19 @@
</span><span class="cx"> 
</span><span class="cx">   class ForNode : public StatementNode {
</span><span class="cx">   public:
</span><del>-    ForNode(ExpressionNode* e1, ExpressionNode* e2, ExpressionNode* e3, StatementNode* s) KJS_FAST_CALL :
-      expr1(e1), expr2(e2), expr3(e3), statement(s)
</del><ins>+    ForNode(ExpressionNode* e1, ExpressionNode* e2, ExpressionNode* e3, StatementNode* s) KJS_FAST_CALL
+        : expr1(e1 ? e1 : new TrueNode)
+        , expr2(e2 ? e2 : new TrueNode)
+        , expr3(e3 ? e3 : new TrueNode)
+        , statement(s)
</ins><span class="cx">     {
</span><del>-        if (expr1)
-            expr1-&gt;optimizeForUnnecessaryResult();
-        if (expr3)
-            expr3-&gt;optimizeForUnnecessaryResult();
</del><ins>+        ASSERT(expr1);
+        ASSERT(expr2);
+        ASSERT(expr3);
+        ASSERT(statement);
+
+        expr1-&gt;optimizeForUnnecessaryResult();
+        expr3-&gt;optimizeForUnnecessaryResult();
</ins><span class="cx">     }
</span><span class="cx"> 
</span><span class="cx">     virtual void optimizeVariableAccess(SymbolTable&amp;, DeclarationStacks::NodeStack&amp;) KJS_FAST_CALL;
</span></span></pre>
</div>
</div>

</body>
</html>