Attachment 371371 Details for Bug 198155 – patch

[patch] patch

c-backup.diff (text/plain), 16.20 KB, created by Saam Barati on 2019-06-04 20:32:28 PDT

(hide)

Description:

Filename:

MIME Type:

Creator: Saam Barati

Created: 2019-06-04 20:32:28 PDT

Size: 16.20 KB

patch

obsolete

>Index: Source/WebCore/ChangeLog
>===================================================================
>--- Source/WebCore/ChangeLog	(revision 246095)
>+++ Source/WebCore/ChangeLog	(working copy)
>@@ -1,3 +1,40 @@
>+2019-06-04  Saam Barati  <sbarati@apple.com>
>+
>+        [WHLSL] checkDuplicateFunctions() should not be O(n^2)
>+        https://bugs.webkit.org/show_bug.cgi?id=198155
>+        <rdar://problem/51288811>
>+
>+        Reviewed by NOBODY (OOPS!).
>+
>+        Originally, we filed this bug because we thought checkDuplicateFunctions()
>+        would take on the order of hundreds of milliseconds when using the
>+        full standard library. However, I was never able to reproduce that phase
>+        taking that long. I was seeing it take 3.5-4ms. Anyways, it makes sense
>+        to make this phase not be O(N^2), since the number of functions is a user
>+        controlled value. I am now seeing ~2.5ms to run this phase against the
>+        full standard library. On a microbenchmark I checked against, where there
>+        were 100,000 unique functions, this pass runs twice as fast as it used
>+        to, now taking 450ms instead of 900ms.
>+
>+        * Modules/webgpu/WHLSL/AST/WHLSLArrayReferenceType.h:
>+        (WebCore::WHLSL::AST::ArrayReferenceType::ArrayReferenceType):
>+        * Modules/webgpu/WHLSL/AST/WHLSLArrayType.h:
>+        * Modules/webgpu/WHLSL/AST/WHLSLPointerType.h:
>+        (WebCore::WHLSL::AST::PointerType::PointerType):
>+        * Modules/webgpu/WHLSL/AST/WHLSLReferenceType.h:
>+        * Modules/webgpu/WHLSL/AST/WHLSLTypeReference.h:
>+        * Modules/webgpu/WHLSL/AST/WHLSLUnnamedType.h:
>+        * Modules/webgpu/WHLSL/WHLSLCheckDuplicateFunctions.cpp:
>+        (WebCore::WHLSL::DuplicateFunctionKey::DuplicateFunctionKey):
>+        (WebCore::WHLSL::DuplicateFunctionKey::isEmptyValue const):
>+        (WebCore::WHLSL::DuplicateFunctionKey::isHashTableDeletedValue const):
>+        (WebCore::WHLSL::DuplicateFunctionKey::hash const):
>+        (WebCore::WHLSL::DuplicateFunctionKey::operator== const):
>+        (WebCore::WHLSL::DuplicateFunctionKey::Hash::hash):
>+        (WebCore::WHLSL::DuplicateFunctionKey::Hash::equal):
>+        (WebCore::WHLSL::DuplicateFunctionKey::Traits::isEmptyValue):
>+        (WebCore::WHLSL::checkDuplicateFunctions):
>+
> 2019-06-04  Michael Catanzaro  <mcatanzaro@igalia.com>
> 
>         Fix miscellaneous build warnings
>Index: Source/WebCore/Modules/webgpu/WHLSL/WHLSLCheckDuplicateFunctions.cpp
>===================================================================
>--- Source/WebCore/Modules/webgpu/WHLSL/WHLSLCheckDuplicateFunctions.cpp	(revision 246051)
>+++ Source/WebCore/Modules/webgpu/WHLSL/WHLSLCheckDuplicateFunctions.cpp	(working copy)
>@@ -32,56 +32,105 @@
> #include "WHLSLArrayType.h"
> #include "WHLSLInferTypes.h"
> #include "WHLSLTypeReference.h"
>+#include <wtf/HashSet.h>
>+#include <wtf/HashTraits.h>
> 
> namespace WebCore {
> 
> namespace WHLSL {
> 
>-bool checkDuplicateFunctions(const Program& program)
>-{
>-    Vector<std::reference_wrapper<const AST::FunctionDeclaration>> functions;
>-    for (auto& functionDefinition : program.functionDefinitions())
>-        functions.append(functionDefinition);
>-    for (auto& nativeFunctionDeclaration : program.nativeFunctionDeclarations())
>-        functions.append(nativeFunctionDeclaration);
>+class DuplicateFunctionKey {
>+public:
>+    DuplicateFunctionKey() = default;
>+    DuplicateFunctionKey(WTF::HashTableDeletedValueType)
>+    {
>+        m_function = bitwise_cast<AST::FunctionDeclaration*>(static_cast<uintptr_t>(1));
>+    }
> 
>-    std::sort(functions.begin(), functions.end(), [](const AST::FunctionDeclaration& a, const AST::FunctionDeclaration& b) -> bool {
>-        if (a.name().length() < b.name().length())
>-            return true;
>-        if (a.name().length() > b.name().length())
>+    DuplicateFunctionKey(const AST::FunctionDeclaration& function)
>+        : m_function(&function)
>+    { }
>+
>+    bool isEmptyValue() const { return !m_function; }
>+    bool isHashTableDeletedValue() const { return m_function == bitwise_cast<AST::FunctionDeclaration*>(static_cast<uintptr_t>(1)); }
>+
>+    unsigned hash() const
>+    {
>+        unsigned hash = IntHash<size_t>::hash(m_function->parameters().size());
>+        hash ^= m_function->name().hash();
>+        for (size_t i = 0; i < m_function->parameters().size(); ++i)
>+            hash ^= m_function->parameters()[i]->type().value()->hash();
>+
>+        // Note: We can't take into account return type in this hash function unless
>+        // we're a cast, since we want two functions with different return types,
>+        // but all things else equal, to be "equal" with respect to finding duplicates.
>+        // Casts with different return types are always *not* equal to each other from
>+        // the perspective of duplicate detection.
>+        if (m_function->isCast())
>+            hash ^= m_function->type().hash();
>+
>+        return hash;
>+    }
>+
>+    bool operator==(const DuplicateFunctionKey& other) const
>+    {
>+        if (m_function->parameters().size() != other.m_function->parameters().size())
>             return false;
>-        for (unsigned i = 0; i < a.name().length(); ++i) {
>-            if (a.name()[i] < b.name()[i])
>-                return true;
>-            if (a.name()[i] > b.name()[i])
>+
>+        if (m_function->name() != other.m_function->name())
>+            return false;
>+
>+        ASSERT(m_function->isCast() == other.m_function->isCast());
>+
>+        for (size_t i = 0; i < m_function->parameters().size(); ++i) {
>+            if (!matches(*m_function->parameters()[i]->type(), *other.m_function->parameters()[i]->type()))
>                 return false;
>         }
>+
>+        // At this point, we have the same name, and the same parameters. We're only *not* a duplicate now if
>+        // we're a cast with a different return type. If we're not a cast, we're now a duplicate. We don't
>+        // allow overloading of return types. If we're a cast, we're not a duplicate if our return types 
>+        // are different.
>+
>+        if (!m_function->isCast())
>+            return true;
>+
>+        if (matches(m_function->type(), other.m_function->type()))
>+            return true;
>+
>         return false;
>-    });
>-    for (size_t i = 0; i < functions.size(); ++i) {
>-        for (size_t j = i + 1; j < functions.size(); ++j) {
>-            if (functions[i].get().name() != functions[j].get().name())
>-                break;
>-            if (is<AST::NativeFunctionDeclaration>(functions[i].get()) && is<AST::NativeFunctionDeclaration>(functions[j].get()))
>-                continue;
>-            if (functions[i].get().parameters().size() != functions[j].get().parameters().size())
>-                continue;
>-            if (functions[i].get().isCast() && !matches(functions[i].get().type(), functions[j].get().type()))
>-                continue;
>-            bool same = true;
>-            for (size_t k = 0; k < functions[i].get().parameters().size(); ++k) {
>-                if (!matches(*functions[i].get().parameters()[k]->type(), *functions[j].get().parameters()[k]->type())) {
>-                    same = false;
>-                    break;
>-                }
>-            }
>-            if (same)
>-                return false;
>+    }
>+
>+    struct Hash {
>+        static unsigned hash(const DuplicateFunctionKey& key)
>+        {
>+            return key.hash();
>         }
>-        
>-        if (functions[i].get().name() == "operator&[]" && functions[i].get().parameters().size() == 2
>-            && is<AST::ArrayReferenceType>(static_cast<const AST::UnnamedType&>(*functions[i].get().parameters()[0]->type()))) {
>-            auto& type = static_cast<const AST::UnnamedType&>(*functions[i].get().parameters()[1]->type());
>+
>+        static bool equal(const DuplicateFunctionKey& a, const DuplicateFunctionKey& b)
>+        {
>+            return a == b;
>+        }
>+
>+        static const bool safeToCompareToEmptyOrDeleted = false;
>+        static const bool emptyValueIsZero = true;
>+    };
>+
>+    struct Traits : public WTF::SimpleClassHashTraits<DuplicateFunctionKey> {
>+        static const bool hasIsEmptyValueFunction = true;
>+        static bool isEmptyValue(const DuplicateFunctionKey& key) { return key.isEmptyValue(); }
>+    };
>+
>+private:
>+    const AST::FunctionDeclaration* m_function { nullptr };
>+};
>+
>+bool checkDuplicateFunctions(const Program& program)
>+{
>+    auto passesStaticChecks = [&] (const AST::FunctionDeclaration& function) {
>+        if (function.name() == "operator&[]" && function.parameters().size() == 2
>+            && is<AST::ArrayReferenceType>(static_cast<const AST::UnnamedType&>(*function.parameters()[0]->type()))) {
>+            auto& type = static_cast<const AST::UnnamedType&>(*function.parameters()[1]->type());
>             if (is<AST::TypeReference>(type)) {
>                 // FIXME: https://bugs.webkit.org/show_bug.cgi?id=198161 Shouldn't we already know whether the types have been resolved by now?
>                 if (auto* resolvedType = downcast<AST::TypeReference>(type).maybeResolvedType()) {
>@@ -92,17 +141,45 @@ bool checkDuplicateFunctions(const Progr
>                     }
>                 }
>             }
>-        } else if (functions[i].get().name() == "operator.length" && functions[i].get().parameters().size() == 1
>-            && (is<AST::ArrayReferenceType>(static_cast<const AST::UnnamedType&>(*functions[i].get().parameters()[0]->type()))
>-            || is<AST::ArrayType>(static_cast<const AST::UnnamedType&>(*functions[i].get().parameters()[0]->type()))))
>-            return false;
>-        else if (functions[i].get().name() == "operator=="
>-            && functions[i].get().parameters().size() == 2
>-            && is<AST::ReferenceType>(static_cast<const AST::UnnamedType&>(*functions[i].get().parameters()[0]->type()))
>-            && is<AST::ReferenceType>(static_cast<const AST::UnnamedType&>(*functions[i].get().parameters()[1]->type()))
>-            && matches(*functions[i].get().parameters()[0]->type(), *functions[i].get().parameters()[1]->type()))
>+        } else if (function.name() == "operator.length" && function.parameters().size() == 1
>+            && (is<AST::ArrayReferenceType>(static_cast<const AST::UnnamedType&>(*function.parameters()[0]->type()))
>+            || is<AST::ArrayType>(static_cast<const AST::UnnamedType&>(*function.parameters()[0]->type()))))
>+            return false;
>+        else if (function.name() == "operator=="
>+            && function.parameters().size() == 2
>+            && is<AST::ReferenceType>(static_cast<const AST::UnnamedType&>(*function.parameters()[0]->type()))
>+            && is<AST::ReferenceType>(static_cast<const AST::UnnamedType&>(*function.parameters()[1]->type()))
>+            && matches(*function.parameters()[0]->type(), *function.parameters()[1]->type()))
>+            return false;
>+
>+        return true;
>+    };
>+
>+    HashSet<DuplicateFunctionKey, DuplicateFunctionKey::Hash, DuplicateFunctionKey::Traits> functions;
>+
>+    auto add = [&] (const AST::FunctionDeclaration& function) {
>+        auto addResult = functions.add(DuplicateFunctionKey { function });
>+        if (!addResult.isNewEntry)
>+            return false;
>+        return passesStaticChecks(function);
>+    };
>+
>+    for (auto& functionDefinition : program.functionDefinitions()) {
>+        if (!add(functionDefinition.get()))
>             return false;
>     }
>+
>+    for (auto& nativeFunctionDeclaration : program.nativeFunctionDeclarations()) {
>+        // Native function declarations are never equal to each other. So we don't need
>+        // to add them to the set, because they can't collide with each other. Instead, we
>+        // just check that no user-defined function is a duplicate.
>+        ASSERT(passesStaticChecks(nativeFunctionDeclaration.get()));
>+        if (functions.contains(DuplicateFunctionKey { nativeFunctionDeclaration.get() }))
>+            return false;
>+        if (!ASSERT_DISABLED)
>+            ASSERT(add(nativeFunctionDeclaration.get()));
>+    }
>+
>     return true;
> }
> 
>Index: Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLArrayReferenceType.h
>===================================================================
>--- Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLArrayReferenceType.h	(revision 246051)
>+++ Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLArrayReferenceType.h	(working copy)
>@@ -39,9 +39,10 @@ namespace WHLSL {
> namespace AST {
> 
> class ArrayReferenceType : public ReferenceType {
>+    using Base = ReferenceType;
> public:
>     ArrayReferenceType(Lexer::Token&& origin, AddressSpace addressSpace, UniqueRef<UnnamedType>&& elementType)
>-        : ReferenceType(WTFMove(origin), addressSpace, WTFMove(elementType))
>+        : Base(WTFMove(origin), addressSpace, WTFMove(elementType))
>     {
>     }
> 
>@@ -57,6 +58,11 @@ public:
>         return makeUniqueRef<ArrayReferenceType>(Lexer::Token(origin()), addressSpace(), elementType().clone());
>     }
> 
>+    unsigned hash() const override
>+    {
>+        return this->Base::hash() ^ StringHasher::computeLiteralHash("array");
>+    }
>+
> private:
> };
> 
>Index: Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLArrayType.h
>===================================================================
>--- Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLArrayType.h	(revision 246051)
>+++ Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLArrayType.h	(working copy)
>@@ -64,6 +64,11 @@ public:
>         return makeUniqueRef<ArrayType>(Lexer::Token(origin()), m_elementType->clone(), m_numElements);
>     }
> 
>+    unsigned hash() const override
>+    {
>+        return WTF::IntHash<unsigned>::hash(m_numElements) ^ m_elementType->hash();
>+    }
>+
> private:
>     UniqueRef<UnnamedType> m_elementType;
>     unsigned m_numElements;
>Index: Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLPointerType.h
>===================================================================
>--- Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLPointerType.h	(revision 246051)
>+++ Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLPointerType.h	(working copy)
>@@ -39,9 +39,10 @@ namespace WHLSL {
> namespace AST {
> 
> class PointerType : public ReferenceType {
>+    using Base = ReferenceType;
> public:
>     PointerType(Lexer::Token&& origin, AddressSpace addressSpace, UniqueRef<UnnamedType> elementType)
>-        : ReferenceType(WTFMove(origin), addressSpace, WTFMove(elementType))
>+        : Base(WTFMove(origin), addressSpace, WTFMove(elementType))
>     {
>     }
> 
>@@ -57,6 +58,11 @@ public:
>         return makeUniqueRef<PointerType>(Lexer::Token(origin()), addressSpace(), elementType().clone());
>     }
> 
>+    unsigned hash() const override
>+    {
>+        return this->Base::hash() ^ StringHasher::computeLiteralHash("pointer");
>+    }
>+
> private:
> };
> 
>Index: Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLReferenceType.h
>===================================================================
>--- Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLReferenceType.h	(revision 246051)
>+++ Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLReferenceType.h	(working copy)
>@@ -59,6 +59,11 @@ public:
>     const UnnamedType& elementType() const { return m_elementType; }
>     UnnamedType& elementType() { return m_elementType; }
> 
>+    unsigned hash() const override
>+    {
>+        return ~m_elementType->hash();
>+    }
>+
> private:
>     AddressSpace m_addressSpace;
>     UniqueRef<UnnamedType> m_elementType;
>Index: Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLTypeReference.h
>===================================================================
>--- Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLTypeReference.h	(revision 246051)
>+++ Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLTypeReference.h	(working copy)
>@@ -99,6 +99,14 @@ public:
>         return cloneTypeReference();
>     }
> 
>+    unsigned hash() const override
>+    {
>+        // We only need this for now after the name resolver, and it simplifies
>+        // two hashes being equal in light of typedefs.
>+        ASSERT(m_resolvedType);
>+        return WTF::PtrHash<const Type*>::hash(&unifyNode());
>+    }
>+
> private:
>     String m_name;
>     TypeArguments m_typeArguments;
>Index: Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLUnnamedType.h
>===================================================================
>--- Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLUnnamedType.h	(revision 246051)
>+++ Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLUnnamedType.h	(working copy)
>@@ -63,6 +63,8 @@ public:
> 
>     virtual UniqueRef<UnnamedType> clone() const = 0;
> 
>+    virtual unsigned hash() const = 0;
>+
>     const Lexer::Token& origin() const { return m_origin; }
> 
> private:

Flags:

mmaxfield: review+
ews-watchlist: commit-queue-

Actions: View | Formatted Diff | Diff

Attachments on bug 198155: 371371 | 371381 | 371407