- Revision
- 221757
- Author
- [email protected]
- Date
- 2017-09-07 14:18:43 -0700 (Thu, 07 Sep 2017)
Log Message
WSL Node.prototype.visit should probably do memoization
https://bugs.webkit.org/show_bug.cgi?id=176286
Reviewed by Mark Lam.
Visitors can sometimes revisit the same thing. For example, we may visit a FuncDef because it belongs
to Program and we may visit it again because a CallExpression resolved to it. That's just plain silly.
Our tests don't currently do this, so it's not a performance problem, yet. Also, we usually avoid that
kind of repetitive visiting inside the visitor implementations. But as far as I can tell, this is an
emergent property rather than a deliberate design.
This change just makes the policy super explicit. If you visit something more than once with the same
visitor, you get the same answer back. This is achieved by means of a memo table inside each visitor.
* WebGPUShadingLanguageRI/All.js:
* WebGPUShadingLanguageRI/FuncInstantiator.js:
* WebGPUShadingLanguageRI/Node.js:
(Node.prototype.visit):
* WebGPUShadingLanguageRI/Rewriter.js:
(Rewriter):
* WebGPUShadingLanguageRI/Test.html:
* WebGPUShadingLanguageRI/Visitor.js:
(Visitor):
* WebGPUShadingLanguageRI/VisitorBase.js: Added.
(VisitorBase):
Modified Paths
Added Paths
Diff
Modified: trunk/Tools/ChangeLog (221756 => 221757)
--- trunk/Tools/ChangeLog 2017-09-07 20:55:50 UTC (rev 221756)
+++ trunk/Tools/ChangeLog 2017-09-07 21:18:43 UTC (rev 221757)
@@ -1,3 +1,32 @@
+2017-09-07 Filip Pizlo <[email protected]>
+
+ WSL Node.prototype.visit should probably do memoization
+ https://bugs.webkit.org/show_bug.cgi?id=176286
+
+ Reviewed by Mark Lam.
+
+ Visitors can sometimes revisit the same thing. For example, we may visit a FuncDef because it belongs
+ to Program and we may visit it again because a CallExpression resolved to it. That's just plain silly.
+
+ Our tests don't currently do this, so it's not a performance problem, yet. Also, we usually avoid that
+ kind of repetitive visiting inside the visitor implementations. But as far as I can tell, this is an
+ emergent property rather than a deliberate design.
+
+ This change just makes the policy super explicit. If you visit something more than once with the same
+ visitor, you get the same answer back. This is achieved by means of a memo table inside each visitor.
+
+ * WebGPUShadingLanguageRI/All.js:
+ * WebGPUShadingLanguageRI/FuncInstantiator.js:
+ * WebGPUShadingLanguageRI/Node.js:
+ (Node.prototype.visit):
+ * WebGPUShadingLanguageRI/Rewriter.js:
+ (Rewriter):
+ * WebGPUShadingLanguageRI/Test.html:
+ * WebGPUShadingLanguageRI/Visitor.js:
+ (Visitor):
+ * WebGPUShadingLanguageRI/VisitorBase.js: Added.
+ (VisitorBase):
+
2017-09-07 Wenson Hsieh <[email protected]>
[Directory Upload] Extend drag and drop support to iOS
Modified: trunk/Tools/WebGPUShadingLanguageRI/All.js (221756 => 221757)
--- trunk/Tools/WebGPUShadingLanguageRI/All.js 2017-09-07 20:55:50 UTC (rev 221756)
+++ trunk/Tools/WebGPUShadingLanguageRI/All.js 2017-09-07 21:18:43 UTC (rev 221757)
@@ -29,6 +29,7 @@
load("ReferenceType.js");
load("Value.js");
load("_expression_.js");
+load("VisitorBase.js");
load("Rewriter.js");
load("Visitor.js");
Modified: trunk/Tools/WebGPUShadingLanguageRI/FuncInstantiator.js (221756 => 221757)
--- trunk/Tools/WebGPUShadingLanguageRI/FuncInstantiator.js 2017-09-07 20:55:50 UTC (rev 221756)
+++ trunk/Tools/WebGPUShadingLanguageRI/FuncInstantiator.js 2017-09-07 21:18:43 UTC (rev 221757)
@@ -76,7 +76,7 @@
let substitution = new InstantiationSubstitution(func.typeParameters, typeArguments);
- class Instantiate {
+ class Instantiate extends VisitorBase {
visitFuncDef(func)
{
return new FuncDef(
Modified: trunk/Tools/WebGPUShadingLanguageRI/Node.js (221756 => 221757)
--- trunk/Tools/WebGPUShadingLanguageRI/Node.js 2017-09-07 20:55:50 UTC (rev 221756)
+++ trunk/Tools/WebGPUShadingLanguageRI/Node.js 2017-09-07 21:18:43 UTC (rev 221757)
@@ -27,11 +27,9 @@
class Node {
visit(visitor)
{
- // FIXME: We could stash a memo table in the visitor. So, before calling the visitor, we ask
- // it if they have seen this node before. If they have, then we return what they returned the
- // last time. This also trivially makes the rewriter do remapping correctly. The downside of
- // not doing it is mostly that various visitors might check the same types multiple times.
- // https://bugs.webkit.org/show_bug.cgi?id=176286
+ let memoTable = visitor._memoTable;
+ if (memoTable.has(this))
+ return memoTable.get(this);
let visitFunc = visitor["visit" + this.constructor.name];
if (!visitFunc)
@@ -38,7 +36,8 @@
throw new Error("No visit function for " + this.constructor.name + " in " + visitor.constructor.name);
let returnValue = visitFunc.call(visitor, this);
if ("returnValue" in visitor)
- return visitor.returnValue;
+ returnValue = visitor.returnValue;
+ memoTable.set(this, returnValue);
return returnValue;
}
Modified: trunk/Tools/WebGPUShadingLanguageRI/Rewriter.js (221756 => 221757)
--- trunk/Tools/WebGPUShadingLanguageRI/Rewriter.js 2017-09-07 20:55:50 UTC (rev 221756)
+++ trunk/Tools/WebGPUShadingLanguageRI/Rewriter.js 2017-09-07 21:18:43 UTC (rev 221757)
@@ -27,9 +27,10 @@
// FIXME: This should have sensible behavior when it encounters definitions that it cannot handle. Right
// now we are hackishly preventing this by wrapping things in TypeRef. That's probably wrong.
// https://bugs.webkit.org/show_bug.cgi?id=176208
-class Rewriter {
+class Rewriter extends VisitorBase {
constructor()
{
+ super();
this._mapping = new Map();
}
Modified: trunk/Tools/WebGPUShadingLanguageRI/Test.html (221756 => 221757)
--- trunk/Tools/WebGPUShadingLanguageRI/Test.html 2017-09-07 20:55:50 UTC (rev 221756)
+++ trunk/Tools/WebGPUShadingLanguageRI/Test.html 2017-09-07 21:18:43 UTC (rev 221757)
@@ -6,6 +6,7 @@
<script src=""
<script src=""
<script src=""
+<script src=""
<script src=""
<script src=""
<script src=""
Modified: trunk/Tools/WebGPUShadingLanguageRI/Visitor.js (221756 => 221757)
--- trunk/Tools/WebGPUShadingLanguageRI/Visitor.js 2017-09-07 20:55:50 UTC (rev 221756)
+++ trunk/Tools/WebGPUShadingLanguageRI/Visitor.js 2017-09-07 21:18:43 UTC (rev 221757)
@@ -24,9 +24,10 @@
*/
"use strict";
-class Visitor {
+class Visitor extends VisitorBase {
constructor()
{
+ super();
}
visitProgram(node)
Added: trunk/Tools/WebGPUShadingLanguageRI/VisitorBase.js (0 => 221757)
--- trunk/Tools/WebGPUShadingLanguageRI/VisitorBase.js (rev 0)
+++ trunk/Tools/WebGPUShadingLanguageRI/VisitorBase.js 2017-09-07 21:18:43 UTC (rev 221757)
@@ -0,0 +1,32 @@
+/*
+ * Copyright (C) 2017 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+"use strict";
+
+class VisitorBase {
+ constructor()
+ {
+ this._memoTable = new Map();
+ }
+}
