Imported QtWebKit TP3 (git b57bc6801f1876c3220d5a4bfea33d620d477443)

Change-Id: I3b1d8a2808782c9f34d50240000e20cb38d3680f
Reviewed-by: Konstantin Tokarev <annulen@yandex.ru>

1 files changed, 154 insertions, 211 deletions

diff --git a/Source/JavaScriptCore/dfg/DFGStructureAbstractValue.h b/Source/JavaScriptCore/dfg/DFGStructureAbstractValue.h
index fb5dfdaa6..a1a5f2982 100644
--- a/Source/JavaScriptCore/dfg/DFGStructureAbstractValue.h
+++ b/Source/JavaScriptCore/dfg/DFGStructureAbstractValue.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2011, 2012, 2013 Apple Inc. All rights reserved.
+ * Copyright (C) 2011-2015 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -26,298 +26,241 @@
 #ifndef DFGStructureAbstractValue_h
 #define DFGStructureAbstractValue_h
 
-#include <wtf/Platform.h>
-
 #if ENABLE(DFG_JIT)
 
+#include "DFGTransition.h"
 #include "JSCell.h"
 #include "SpeculatedType.h"
+#include "DumpContext.h"
 #include "StructureSet.h"
 
-namespace JSC { namespace DFG {
+namespace JSC {
+
+class TrackedReferences;
+
+namespace DFG {
 
 class StructureAbstractValue {
 public:
-    StructureAbstractValue()
-        : m_structure(0)
-    {
-    }
-    
+    StructureAbstractValue() { }
     StructureAbstractValue(Structure* structure)
-        : m_structure(structure)
+        : m_set(StructureSet(structure))
     {
+        setClobbered(false);
     }
-    
-    StructureAbstractValue(const StructureSet& set)
+    StructureAbstractValue(const StructureSet& other)
+        : m_set(other)
     {
-        switch (set.size()) {
-        case 0:
-            m_structure = 0;
-            break;
-            
-        case 1:
-            m_structure = set[0];
-            break;
-            
-        default:
-            m_structure = topValue();
-            break;
-        }
+        setClobbered(false);
     }
-    
-    void clear()
+    ALWAYS_INLINE StructureAbstractValue(const StructureAbstractValue& other)
+        : m_set(other.m_set)
     {
-        m_structure = 0;
+        setClobbered(other.isClobbered());
     }
     
-    void makeTop()
+    ALWAYS_INLINE StructureAbstractValue& operator=(Structure* structure)
     {
-        m_structure = topValue();
+        m_set = StructureSet(structure);
+        setClobbered(false);
+        return *this;
     }
-    
-    static StructureAbstractValue top()
+    ALWAYS_INLINE StructureAbstractValue& operator=(const StructureSet& other)
     {
-        StructureAbstractValue value;
-        value.makeTop();
-        return value;
+        m_set = other;
+        setClobbered(false);
+        return *this;
     }
-    
-    void add(Structure* structure)
+    ALWAYS_INLINE StructureAbstractValue& operator=(const StructureAbstractValue& other)
     {
-        ASSERT(!contains(structure) && !isTop());
-        if (m_structure)
-            makeTop();
-        else
-            m_structure = structure;
+        m_set = other.m_set;
+        setClobbered(other.isClobbered());
+        return *this;
     }
     
-    bool addAll(const StructureSet& other)
+    void clear()
     {
-        if (isTop() || !other.size())
-            return false;
-        if (other.size() > 1) {
-            makeTop();
-            return true;
-        }
-        if (!m_structure) {
-            m_structure = other[0];
-            return true;
-        }
-        if (m_structure == other[0])
-            return false;
-        makeTop();
-        return true;
+        m_set.clear();
+        setClobbered(false);
     }
     
-    bool addAll(const StructureAbstractValue& other)
+    void makeTop()
     {
-        if (!other.m_structure)
-            return false;
-        if (isTop())
-            return false;
-        if (other.isTop()) {
-            makeTop();
-            return true;
-        }
-        if (m_structure) {
-            if (m_structure == other.m_structure)
-                return false;
-            makeTop();
-            return true;
-        }
-        m_structure = other.m_structure;
-        return true;
+        m_set.deleteListIfNecessary();
+        m_set.m_pointer = topValue;
     }
     
-    bool contains(Structure* structure) const
-    {
-        if (isTop())
-            return true;
-        if (m_structure == structure)
-            return true;
-        return false;
-    }
+#if ASSERT_DISABLED
+    void assertIsRegistered(Graph&) const { }
+#else
+    void assertIsRegistered(Graph&) const;
+#endif
     
-    bool isSubsetOf(const StructureSet& other) const
-    {
-        if (isTop())
-            return false;
-        if (!m_structure)
-            return true;
-        return other.contains(m_structure);
-    }
+    void clobber();
+    void observeInvalidationPoint() { setClobbered(false); }
     
-    bool doesNotContainAnyOtherThan(Structure* structure) const
-    {
-        if (isTop())
-            return false;
-        if (!m_structure)
-            return true;
-        return m_structure == structure;
-    }
+    void observeTransition(Structure* from, Structure* to);
+    void observeTransitions(const TransitionVector&);
     
-    bool isSupersetOf(const StructureSet& other) const
+    static StructureAbstractValue top()
     {
-        if (isTop())
-            return true;
-        if (!other.size())
-            return true;
-        if (other.size() > 1)
-            return false;
-        return m_structure == other[0];
+        StructureAbstractValue result;
+        result.m_set.m_pointer = topValue;
+        return result;
     }
     
-    bool isSubsetOf(const StructureAbstractValue& other) const
-    {
-        if (other.isTop())
-            return true;
-        if (isTop())
-            return false;
-        if (m_structure) {
-            if (other.m_structure)
-                return m_structure == other.m_structure;
-            return false;
-        }
-        return true;
-    }
+    bool isClear() const { return m_set.isEmpty(); }
+    bool isTop() const { return m_set.m_pointer == topValue; }
+    bool isNeitherClearNorTop() const { return !isClear() && !isTop(); }
     
-    bool isSupersetOf(const StructureAbstractValue& other) const
-    {
-        return other.isSubsetOf(*this);
-    }
+    // A clobbered abstract value means that the set currently contains the m_set set of
+    // structures plus TOP, except that the "plus TOP" will go away at the next invalidation
+    // point. Note that it's tempting to think of this as "the set of structures in m_set plus
+    // the set of structures transition-reachable from m_set" - but this isn't really correct,
+    // since if we add an unwatchable structure after clobbering, the two definitions are not
+    // equivalent. If we do this, the new unwatchable structure will be added to m_set.
+    // Invalidation points do not try to "clip" the set of transition-reachable structures from
+    // m_set by looking at reachability as this would mean that the new set is TOP. Instead they
+    // literally assume that the set is just m_set rather than m_set plus TOP.
+    bool isClobbered() const { return m_set.getReservedFlag(); }
+
+    // A finite structure abstract value is one where enumerating over it will yield all
+    // of the structures that the value may have right now. This is true so long as we're
+    // neither top nor clobbered.
+    bool isFinite() const { return !isTop() && !isClobbered(); }
+
+    // An infinite structure abstract value may currently have any structure.
+    bool isInfinite() const { return !isFinite(); }
     
-    void filter(const StructureSet& other)
+    bool add(Structure* structure);
+    
+    bool merge(const StructureSet& other);
+    
+    ALWAYS_INLINE bool merge(const StructureAbstractValue& other)
     {
-        if (!m_structure)
-            return;
+        if (other.isClear())
+            return false;
         
-        if (isTop()) {
-            switch (other.size()) {
-            case 0:
-                m_structure = 0;
-                return;
-                
-            case 1:
-                m_structure = other[0];
-                return;
-                
-            default:
-                return;
-            }
-        }
+        if (isTop())
+            return false;
         
-        if (other.contains(m_structure))
-            return;
+        if (other.isTop()) {
+            makeTop();
+            return true;
+        }
         
-        m_structure = 0;
+        return mergeSlow(other);
     }
     
-    void filter(const StructureAbstractValue& other)
+    void filter(const StructureSet& other);
+    void filter(const StructureAbstractValue& other);
+    
+    ALWAYS_INLINE void filter(SpeculatedType type)
     {
-        if (isTop()) {
-            m_structure = other.m_structure;
+        if (!(type & SpecCell)) {
+            clear();
             return;
         }
-        if (m_structure == other.m_structure)
-            return;
-        if (other.isTop())
-            return;
-        m_structure = 0;
+        if (isNeitherClearNorTop())
+            filterSlow(type);
     }
     
-    void filter(SpeculatedType other)
+    ALWAYS_INLINE bool operator==(const StructureAbstractValue& other) const
     {
-        if (!(other & SpecCell)) {
-            clear();
-            return;
-        }
+        if ((m_set.isThin() && other.m_set.isThin()) || isTop() || other.isTop())
+            return m_set.m_pointer == other.m_set.m_pointer;
         
-        if (isClearOrTop())
-            return;
-
-        if (!(speculationFromStructure(m_structure) & other))
-            m_structure = 0;
+        return equalsSlow(other);
     }
     
-    bool isClear() const
+    const StructureSet& set() const
     {
-        return !m_structure;
+        ASSERT(!isTop());
+        return m_set;
     }
     
-    bool isTop() const { return m_structure == topValue(); }
-    
-    bool isClearOrTop() const { return m_structure <= topValue(); }
-    bool isNeitherClearNorTop() const { return !isClearOrTop(); }
-    
     size_t size() const
     {
         ASSERT(!isTop());
-        return !!m_structure;
+        return m_set.size();
     }
     
     Structure* at(size_t i) const
     {
         ASSERT(!isTop());
-        ASSERT(m_structure);
-        ASSERT_UNUSED(i, !i);
-        return m_structure;
+        return m_set.at(i);
     }
     
-    Structure* operator[](size_t i) const
+    Structure* operator[](size_t i) const { return at(i); }
+
+    // In most cases, what you really want to do is verify whether the set is top or clobbered, and
+    // if not, enumerate the set of structures. Use this only in cases where the singleton case is
+    // meaningfully special, like for transitions.
+    Structure* onlyStructure() const
     {
-        return at(i);
+        if (isInfinite())
+            return nullptr;
+        return m_set.onlyStructure();
     }
-    
-    Structure* last() const
+
+    template<typename Functor>
+    void forEach(const Functor& functor) const
     {
-        return at(0);
+        ASSERT(!isTop());
+        m_set.forEach(functor);
     }
     
-    SpeculatedType speculationFromStructures() const
-    {
-        if (isTop())
-            return SpecCell;
-        if (isClear())
-            return SpecNone;
-        return speculationFromStructure(m_structure);
-    }
+    void dumpInContext(PrintStream&, DumpContext*) const;
+    void dump(PrintStream&) const;
     
-    bool hasSingleton() const
-    {
-        return isNeitherClearNorTop();
-    }
+    // The methods below are all conservative and err on the side of making 'this' appear bigger
+    // than it is. For example, contains() may return true if the set is clobbered or TOP.
+    // isSubsetOf() may return false in case of ambiguities. Therefore you should only perform
+    // optimizations as a consequence of the "this is smaller" return value - so false for
+    // contains(), true for isSubsetOf(), false for isSupersetOf(), and false for overlaps().
+
+    bool contains(Structure* structure) const;
+    
+    bool isSubsetOf(const StructureSet& other) const;
+    bool isSubsetOf(const StructureAbstractValue& other) const;
     
-    Structure* singleton() const
+    bool isSupersetOf(const StructureSet& other) const;
+    bool isSupersetOf(const StructureAbstractValue& other) const
     {
-        ASSERT(isNeitherClearNorTop());
-        return m_structure;
+        return other.isSubsetOf(*this);
     }
     
-    bool operator==(const StructureAbstractValue& other) const
+    bool overlaps(const StructureSet& other) const;
+    bool overlaps(const StructureAbstractValue& other) const;
+    
+    void validateReferences(const TrackedReferences&) const;
+    
+private:
+    static const uintptr_t clobberedFlag = StructureSet::reservedFlag;
+    static const uintptr_t topValue = StructureSet::reservedValue;
+    static const unsigned polymorphismLimit = 10;
+    static const unsigned clobberedSupremacyThreshold = 2;
+    
+    void filterSlow(SpeculatedType type);
+    bool mergeSlow(const StructureAbstractValue& other);
+    
+    bool equalsSlow(const StructureAbstractValue& other) const;
+    
+    void makeTopWhenThin()
     {
-        return m_structure == other.m_structure;
+        ASSERT(m_set.isThin());
+        m_set.m_pointer = topValue;
     }
     
-    void dump(PrintStream& out) const
+    bool mergeNotTop(const StructureSet& other);
+    
+    void setClobbered(bool clobbered)
     {
-        if (isTop()) {
-            out.print("TOP");
-            return;
-        }
-        
-        out.print("[");
-        if (m_structure)
-            out.print(RawPointer(m_structure), "(", m_structure->classInfo()->className, ")");
-        out.print("]");
+        ASSERT(!isTop() || !clobbered);
+        m_set.setReservedFlag(clobbered);
     }
-
-private:
-    static Structure* topValue() { return reinterpret_cast<Structure*>(1); }
-    
-    // NB. This must have a trivial destructor.
     
-    // This can only remember one structure at a time.
-    Structure* m_structure;
+    StructureSet m_set;
 };
 
 } } // namespace JSC::DFG