Attachment 233125 Details for Bug 133918 – work in progress

[patch] work in progress

blah.patch (text/plain), 13.47 KB, created by Filip Pizlo on 2014-06-14 14:42:47 PDT

(hide)

Description:

Filename:

MIME Type:

Creator: Filip Pizlo

Created: 2014-06-14 14:42:47 PDT

Size: 13.47 KB

patch

obsolete

>Index: Source/JavaScriptCore/bytecode/StructureSet.cpp
>===================================================================
>--- Source/JavaScriptCore/bytecode/StructureSet.cpp	(revision 169979)
>+++ Source/JavaScriptCore/bytecode/StructureSet.cpp	(working copy)
>@@ -26,6 +26,7 @@
> #include "config.h"
> #include "StructureSet.h"
> 
>+#include "DFGAbstractValue.h"
> #include <wtf/CommaPrinter.h>
> 
> namespace JSC {
>@@ -160,6 +161,80 @@ void StructureSet::exclude(const Structu
>         clear();
> }
> 
>+namespace {
>+
>+class StructureAbstractValueContains {
>+public:
>+    StructureAbstractValueContains(const DFG::StructureAbstractValue& value)
>+        : m_value(value)
>+    {
>+    }
>+    
>+    bool operator()(Structure* structure)
>+    {
>+        return m_value.contains(structure);
>+    }
>+private:
>+    const DFG::StructureAbstractValue& m_value;
>+};
>+
>+class SpeculatedTypeContains {
>+public:
>+    SpeculatedTypeContains(SpeculatedType type)
>+        : m_type(type)
>+    {
>+    }
>+    
>+    bool operator()(Structure* structure)
>+    {
>+        return m_type & speculationFromStructure(structure);
>+    }
>+private:
>+    SpeculatedType m_type;
>+};
>+
>+class ArrayModesContains {
>+public:
>+    ArrayModesContains(ArrayModes arrayModes)
>+        : m_arrayModes(arrayModes)
>+    {
>+    }
>+    
>+    bool operator()(Structure* structure)
>+    {
>+        return m_arrayModes & arrayModesFromStructure(structure);
>+    }
>+private:
>+    ArrayModes m_arrayModes;
>+};
>+
>+} // anonymous namespace
>+
>+void StructureSet::filter(const DFG::StructureAbstractValue& other)
>+{
>+    StructureAbstractValueContains functor(other);
>+    genericFilter(functor);
>+}
>+
>+void StructureSet::filter(SpeculatedType type)
>+{
>+    SpeculatedTypeContains functor(type);
>+    genericFilter(functor);
>+}
>+
>+void StructureSet::filter(ArrayModes arrayModes)
>+{
>+    ArrayModesContains functor(arrayModes);
>+    genericFilter(functor);
>+}
>+
>+void StructureSet::filter(const DFG::AbstractValue& other)
>+{
>+    filter(other.m_structure);
>+    filter(other.m_type);
>+    filter(other.m_arrayModes);
>+}
>+
> bool StructureSet::isSubsetOf(const StructureSet& other) const
> {
>     if (isThin()) {
>Index: Source/JavaScriptCore/bytecode/StructureSet.h
>===================================================================
>--- Source/JavaScriptCore/bytecode/StructureSet.h	(revision 169979)
>+++ Source/JavaScriptCore/bytecode/StructureSet.h	(working copy)
>@@ -34,6 +34,7 @@
> namespace JSC {
> 
> namespace DFG {
>+class AbstractValue;
> class StructureAbstractValue;
> }
> 
>@@ -96,6 +97,11 @@ public:
>     void filter(const StructureSet&);
>     void exclude(const StructureSet&);
>     
>+    void filter(const DFG::StructureAbstractValue&);
>+    void filter(SpeculatedType);
>+    void filter(ArrayModes);
>+    void filter(const DFG::AbstractValue&);
>+    
>     template<typename Functor>
>     void genericFilter(Functor& functor)
>     {
>Index: Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h	(revision 169979)
>+++ Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h	(working copy)
>@@ -1534,7 +1534,7 @@ bool AbstractInterpreter<AbstractStateTy
>         if (!forNode(node->child1()).m_structure.isClear()) {
>             observeTransition(
>                 clobberLimit, node->transition()->previous, node->transition()->next);
>-            forNode(node->child1()).set(m_graph, node->transition()->next);
>+            forNode(node->child1()).changeStructure(m_graph, node->transition()->next);
>         }
>         break;
>     case GetButterfly:
>@@ -1666,39 +1666,53 @@ bool AbstractInterpreter<AbstractStateTy
>     }
>         
>     case MultiGetByOffset: {
>-        AbstractValue& value = forNode(node->child1());
>-        ASSERT(!(value.m_type & ~SpecCell)); // Edge filtering should have already ensured this.
>-
>-        // This should just filter down the cases in MultiGetByOffset. If that results in all
>-        // cases having the same offset then we should strength reduce it to a CheckStructure +
>-        // GetByOffset.
>-        // https://bugs.webkit.org/show_bug.cgi?id=133229
>-        if (Structure* structure = value.m_structure.onlyStructure()) {
>-            bool done = false;
>-            for (unsigned i = node->multiGetByOffsetData().variants.size(); i--;) {
>-                const GetByIdVariant& variant = node->multiGetByOffsetData().variants[i];
>-                if (!variant.structureSet().contains(structure))
>-                    continue;
>-                
>-                if (variant.alternateBase())
>-                    break;
>-                
>-                filter(value, structure);
>-                forNode(node).makeHeapTop();
>+        // This code will filter the base value in a manner that is possibly different (either more
>+        // or less precise) than the way it would be filtered if this was strength-reduced to a
>+        // CheckStructure. This is fine. It's legal for different passes over the code to prove
>+        // different things about the code, so long as all of them are sound. That even includes
>+        // one guy proving that code should never execute (due to a contradiction) and another guy
>+        // not finding that contradiction. If someone ever proved that there would be a
>+        // contradiction then there must always be a contradiction. This is the case here.
>+        
>+        AbstractValue base = forNode(node->child1());
>+        StructureSet baseSet;
>+        AbstractValue result;
>+        for (unsigned i = node->multiGetByOffsetData().variants.size(); i--;) {
>+            GetByIdVariant& variant = node->multiGetByOffsetData().variants[i];
>+            StructureSet set = variant.structureSet();
>+            set.filter(base);
>+            if (set.isEmpty()) {
>                 m_state.setFoundConstants(true);
>-                done = true;
>-                break;
>+                continue;
>             }
>-            if (done)
>-                break;
>-        }
>+            baseSet.merge(set);
>+            if (!variant.specificValue()) {
>+                result.makeHeapTop();
>+                continue;
>+            }
>+            AbstractValue thisResult;
>+            thisResult.set(
>+                m_graph,
>+                m_graph.freeze(variant.specificValue()),
>+                m_state.structureClobberState());
>+            result.merge(thisResult);
>+        }
>+        
>+        // This shouldn't ever happen but it's here for completeness. Currently only the constant
>+        // folder can strength-reduce a MultiGetByOffset down to its constituent CheckStructure,
>+        // GetButterfly, GetByOffset and/or JSConstant. So if the MultiGetByOffset had already been
>+        // in a state where such a reduction was possible then we ask the constant folder to look
>+        // at this code.
>+        if (node->multiGetByOffsetData().variant.size() == 1)
>+            m_state.setFoundContants(true);
>+
>+        if (forNode(node->child1()).changeStructure(baseSet) == Contradiction)
>+            m_state.setIsValid(false);
>         
>-        StructureSet set;
>-        for (unsigned i = node->multiGetByOffsetData().variants.size(); i--;)
>-            set.merge(node->multiGetByOffsetData().variants[i].structureSet());
>+        if (result.m_value)
>+            m_state.setFoundConstants(true);
>         
>-        filter(node->child1(), set);
>-        forNode(node).makeHeapTop();
>+        forNode(node) = result;
>         break;
>     }
>             
>@@ -1707,45 +1721,14 @@ bool AbstractInterpreter<AbstractStateTy
>     }
>         
>     case MultiPutByOffset: {
>-        AbstractValue& value = forNode(node->child1());
>-        ASSERT(!(value.m_type & ~SpecCell)); // Edge filtering should have already ensured this.
>-
>-        // This should just filter down the cases in MultiPutByOffset. If that results in either
>-        // one case, or nothing but replace cases and they have the same offset, then we should
>-        // just strength reduce it to the appropriate combination of CheckStructure,
>-        // [Re]AllocatePropertyStorage, PutStructure, and PutByOffset.
>-        // https://bugs.webkit.org/show_bug.cgi?id=133229
>-        if (Structure* structure = value.m_structure.onlyStructure()) {
>-            bool done = false;
>-            for (unsigned i = node->multiPutByOffsetData().variants.size(); i--;) {
>-                const PutByIdVariant& variant = node->multiPutByOffsetData().variants[i];
>-                if (variant.oldStructure() != structure)
>-                    continue;
>-                
>-                if (variant.kind() == PutByIdVariant::Replace) {
>-                    filter(node->child1(), structure);
>-                    m_state.setFoundConstants(true);
>-                    done = true;
>-                    break;
>-                }
>-                
>-                ASSERT(variant.kind() == PutByIdVariant::Transition);
>-                clobberStructures(clobberLimit);
>-                forNode(node->child1()).set(m_graph, variant.newStructure());
>-                m_state.setFoundConstants(true);
>-                done = true;
>-                break;
>-            }
>-            if (done)
>-                break;
>-        }
>-        
>-        StructureSet oldSet;
>         StructureSet newSet;
>         TransitionVector transitions;
>         for (unsigned i = node->multiPutByOffsetData().variants.size(); i--;) {
>             const PutByIdVariant& variant = node->multiPutByOffsetData().variants[i];
>-            oldSet.add(variant.oldStructure());
>+            if (!forNode(node->child1()).contains(variant.oldStructure())) {
>+                m_state.setFoundConstants(true);
>+                continue;
>+            }
>             if (variant.kind() == PutByIdVariant::Transition) {
>                 transitions.append(Transition(variant.oldStructure(), variant.newStructure()));
>                 newSet.add(variant.newStructure());
>@@ -1755,9 +1738,9 @@ bool AbstractInterpreter<AbstractStateTy
>             }
>         }
>         
>-        filter(node->child1(), oldSet);
>         observeTransitions(clobberLimit, transitions);
>-        forNode(node->child1()).set(m_graph, newSet);
>+        if (forNode(node->child1()).changeStructure(m_graph, newSet) == Contradiction)
>+            m_state.setIsValid(false);
>         break;
>     }
>     
>Index: Source/JavaScriptCore/dfg/DFGAbstractValue.cpp
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGAbstractValue.cpp	(revision 169979)
>+++ Source/JavaScriptCore/dfg/DFGAbstractValue.cpp	(working copy)
>@@ -179,6 +179,17 @@ FiltrationResult AbstractValue::filter(G
>     return normalizeClarity(graph);
> }
> 
>+FiltrationResult AbstractValue::changeStructure(Graph& graph, const StructureSet& other)
>+{
>+    m_type &= other.speculationFromStructures();
>+    m_arrayModes = other.arrayModesFromStructures();
>+    m_structure = other;
>+    
>+    filterValueByType();
>+    
>+    return normalizeClarity(graph);
>+}
>+
> FiltrationResult AbstractValue::filterArrayModes(ArrayModes arrayModes)
> {
>     ASSERT(arrayModes);
>@@ -229,6 +240,13 @@ FiltrationResult AbstractValue::filterBy
>     return result;
> }
> 
>+bool AbstractValue::contains(Structure* structure) const
>+{
>+    return couldBeType(speculationFromStructure(structure))
>+        && (m_arrayModes & arrayModeFromStructure(structure))
>+        && m_structure.contains(structure);
>+}
>+
> void AbstractValue::filterValueByType()
> {
>     // We could go further, and ensure that if the futurePossibleStructure contravenes
>Index: Source/JavaScriptCore/dfg/DFGAbstractValue.h
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGAbstractValue.h	(revision 169979)
>+++ Source/JavaScriptCore/dfg/DFGAbstractValue.h	(working copy)
>@@ -259,13 +259,14 @@ struct AbstractValue {
>     }
>     
>     FiltrationResult filter(Graph&, const StructureSet&);
>-    
>     FiltrationResult filterArrayModes(ArrayModes arrayModes);
>-    
>     FiltrationResult filter(SpeculatedType type);
>-    
>     FiltrationResult filterByValue(const FrozenValue& value);
>     
>+    FiltrationResult changeStructure(Graph&, const StructureSet&);
>+    
>+    bool contains(Structure*) const;
>+    
>     bool validate(JSValue value) const
>     {
>         if (isHeapTop())
>Index: Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp	(revision 169979)
>+++ Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp	(working copy)
>@@ -141,6 +141,10 @@ private:
>                 Node* child = childEdge.node();
>                 MultiGetByOffsetData& data = node->multiGetByOffsetData();
> 
>+                // First prune the variants, then check if the MultiGetByOffset can be
>+                // strength-reduced to a GetByOffset.
>+                
>+                
>                 Structure* structure = m_state.forNode(child).m_structure.onlyStructure();
>                 if (!structure)
>                     break;
>Index: Source/JavaScriptCore/dfg/DFGStructureAbstractValue.h
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGStructureAbstractValue.h	(revision 169979)
>+++ Source/JavaScriptCore/dfg/DFGStructureAbstractValue.h	(working copy)
>@@ -55,6 +55,12 @@ public:
>         setClobbered(other.isClobbered());
>     }
>     
>+    ALWAYS_INLINE StructureAbstractValue& operator=(const StructureSet& other)
>+    {
>+        m_set = other;
>+        setClobbered(false);
>+        return *this;
>+    }
>     ALWAYS_INLINE StructureAbstractValue& operator=(const StructureAbstractValue& other)
>     {
>         m_set = other.m_set;

Actions: View | Formatted Diff | Diff

Attachments on bug 133918: 233125 | 233214 | 233279 | 233283 | 233321 | 233322