WSL Node.prototype.visit should probably do memoization
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 7 Sep 2017 21:18:43 +0000 (21:18 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 7 Sep 2017 21:18:43 +0000 (21:18 +0000)
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):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@221757 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Tools/ChangeLog
Tools/WebGPUShadingLanguageRI/All.js
Tools/WebGPUShadingLanguageRI/FuncInstantiator.js
Tools/WebGPUShadingLanguageRI/Node.js
Tools/WebGPUShadingLanguageRI/Rewriter.js
Tools/WebGPUShadingLanguageRI/Test.html
Tools/WebGPUShadingLanguageRI/Visitor.js
Tools/WebGPUShadingLanguageRI/VisitorBase.js [new file with mode: 0644]

index 637e13a..feffb3f 100644 (file)
@@ -1,3 +1,32 @@
+2017-09-07  Filip Pizlo  <fpizlo@apple.com>
+
+        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  <wenson_hsieh@apple.com>
 
         [Directory Upload] Extend drag and drop support to iOS
index 647356d..4e5666d 100644 (file)
@@ -29,6 +29,7 @@ load("Type.js");
 load("ReferenceType.js");
 load("Value.js");
 load("Expression.js");
+load("VisitorBase.js");
 load("Rewriter.js");
 load("Visitor.js");
 
index e6a7da0..be63f51 100644 (file)
@@ -76,7 +76,7 @@ class FuncInstantiator {
         
         let substitution = new InstantiationSubstitution(func.typeParameters, typeArguments);
         
-        class Instantiate {
+        class Instantiate extends VisitorBase {
             visitFuncDef(func)
             {
                 return new FuncDef(
index 6a3b247..04e3889 100644 (file)
 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)
             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;
     }
     
index 65fdb78..5cec804 100644 (file)
 // 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();
     }
     
index c130e6f..46c8227 100644 (file)
@@ -6,6 +6,7 @@
 <script src="ReferenceType.js"></script>
 <script src="Value.js"></script>
 <script src="Expression.js"></script>
+<script src="VisitorBase.js"></script>
 <script src="Rewriter.js"></script>
 <script src="Visitor.js"></script>
 <script src="AddressSpace.js"></script>
index d4dac63..f71b28b 100644 (file)
  */
 "use strict";
 
-class Visitor {
+class Visitor extends VisitorBase {
     constructor()
     {
+        super();
     }
     
     visitProgram(node)
diff --git a/Tools/WebGPUShadingLanguageRI/VisitorBase.js b/Tools/WebGPUShadingLanguageRI/VisitorBase.js
new file mode 100644 (file)
index 0000000..8c92a6c
--- /dev/null
@@ -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();
+    }
+}