Attachment 238343 Details for Bug 136330 – and now, with an OSR availability story!

[patch] and now, with an OSR availability story!

blah.patch (text/plain), 80.73 KB, created by Filip Pizlo on 2014-09-18 18:13:05 PDT

(hide)

Description:

Filename:

MIME Type:

Creator: Filip Pizlo

Created: 2014-09-18 18:13:05 PDT

Size: 80.73 KB

patch

obsolete

>Index: Source/JavaScriptCore/dfg/DFGAvailabilityMap.cpp
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGAvailabilityMap.cpp	(revision 0)
>+++ Source/JavaScriptCore/dfg/DFGAvailabilityMap.cpp	(working copy)
>@@ -0,0 +1,86 @@
>+/*
>+ * Copyright (C) 2014 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. 
>+ */
>+
>+#include "config.h"
>+#include "DFGAvailabilityMap.h"
>+
>+#if ENABLE(DFG_JIT)
>+
>+#include <wtf/ListDump.h>
>+
>+namespace JSC { namespace DFG {
>+
>+void AvailabilityMap::prune()
>+{
>+    HashSet<Node*> possibleNodes;
>+    
>+    for (unsigned i = m_locals.size(); i--;) {
>+        if (m_locals[i].hasNode())
>+            possibleNodes.add(m_locals[i].node());
>+    }
>+
>+    unsigned oldPossibleNodesSize;
>+    do {
>+        oldPossibleNodesSize = possibleNodes.size();
>+        for (auto pair : m_heap) {
>+            if (pair.value.hasNode() && possibleNodes.contains(pair.key.base()))
>+                possibleNodes.add(pair.value.node());
>+        }
>+    } while (oldPossibleNodesSize != possibleNodes.size());
>+    
>+    HashMap<PromotedHeapLocation, Availability> newHeap;
>+    for (auto pair : m_heap) {
>+        if (possibleNodes.contains(pair.key.base()))
>+            newHeap.add(pair.key, pair.value);
>+    }
>+    m_heap = newHeap;
>+}
>+
>+void AvailabilityMap::dump(PrintStream& out) const
>+{
>+    out.print("{locals = ", m_locals, "; heap = ", mapDump(m_heap), "}");
>+}
>+
>+bool AvailabilityMap::operator==(const AvailabilityMap& other) const
>+{
>+    return m_locals == other.m_locals
>+        && m_heap == other.m_heap;
>+}
>+
>+void AvailabilityMap::merge(const AvailabilityMap& other)
>+{
>+    for (unsigned i = other.m_locals.size(); i--;)
>+        locals[i] = other.m_locals[i].merge(locals[i]);
>+    
>+    for (auto pair : other.m_heap) {
>+        auto result = m_heap.add(pair.key, Availability());
>+        result.iterator->value = pair.value.merge(result.iterator->value);
>+    }
>+}
>+
>+} } // namespace JSC::DFG
>+
>+#endif // ENABLE(DFG_JIT)
>+
>Index: Source/JavaScriptCore/dfg/DFGAvailabilityMap.h
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGAvailabilityMap.h	(revision 0)
>+++ Source/JavaScriptCore/dfg/DFGAvailabilityMap.h	(working copy)
>@@ -0,0 +1,53 @@
>+/*
>+ * Copyright (C) 2014 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. 
>+ */
>+
>+#ifndef DFGAvailabilityMap_h
>+#define DFGAvailabilityMap_h
>+
>+#if ENABLE(DFG_JIT)
>+
>+#include "DFGAvailability.h"
>+
>+namespace JSC { namespace DFG {
>+
>+struct AvailabilityMap {
>+    void prune();
>+    
>+    void dump(PrintStream& out) const;
>+    
>+    bool operator==(const AvailabilityMap& other) const;
>+    
>+    void merge(const AvailabilityMap& other);
>+    
>+    Operands<Availability> m_locals;
>+    HashMap<PromotedHeapLocation, Availability> m_heap;
>+};
>+
>+} } // namespace JSC::DFG
>+
>+#endif // ENABLE(DFG_JIT)
>+
>+#endif // DFGAvailabilityMap_h
>+
>Index: Source/JavaScriptCore/dfg/DFGBasicBlock.cpp
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGBasicBlock.cpp	(revision 173672)
>+++ Source/JavaScriptCore/dfg/DFGBasicBlock.cpp	(working copy)
>@@ -118,9 +118,9 @@ void BasicBlock::dump(PrintStream& out) 
> }
> 
> BasicBlock::SSAData::SSAData(BasicBlock* block)
>-    : availabilityAtHead(OperandsLike, block->variablesAtHead)
>-    , availabilityAtTail(OperandsLike, block->variablesAtHead)
> {
>+    m_availabilityAtHead.m_locals = Operands<Availability>(OperandsLike, block->variablesAtHead);
>+    m_availabilityAtTail.m_locals = Operands<Availability>(OperandsLike, block->variablesAtHead);
> }
> 
> BasicBlock::SSAData::~SSAData() { }
>Index: Source/JavaScriptCore/dfg/DFGBasicBlock.h
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGBasicBlock.h	(revision 173672)
>+++ Source/JavaScriptCore/dfg/DFGBasicBlock.h	(working copy)
>@@ -46,6 +46,7 @@ class Graph;
> class InsertionSet;
> 
> typedef Vector<BasicBlock*, 2> PredecessorList;
>+typedef Vector<Node*, 8> BlockNodeList;
> 
> struct BasicBlock : RefCounted<BasicBlock> {
>     BasicBlock(
>@@ -85,6 +86,9 @@ struct BasicBlock : RefCounted<BasicBloc
>     bool isInPhis(Node* node) const;
>     bool isInBlock(Node* myNode) const;
>     
>+    BlockNodeList::iterator begin() { return m_nodes.begin(); }
>+    BlockNodeList::iterator end() { return m_nodes.end(); }
>+    
>     unsigned numSuccessors() { return last()->numSuccessors(); }
>     
>     BasicBlock*& successor(unsigned index)
>@@ -96,6 +100,76 @@ struct BasicBlock : RefCounted<BasicBloc
>         return last()->successorForCondition(condition);
>     }
>     
>+    class SuccessorsIterable {
>+    public:
>+        SuccessorsIterable()
>+            : m_block(nullptr)
>+        {
>+        }
>+        
>+        SuccessorsIterable(BasicBlock* block)
>+            : m_block(block)
>+        {
>+        }
>+        
>+        class iterator {
>+        public:
>+            iterator()
>+                : m_block(nullptr)
>+                , m_index(UINT_MAX)
>+            {
>+            }
>+            
>+            iterator(BasicBlock* block, unsigned index)
>+                : m_block(block)
>+                , m_index(index)
>+            {
>+            }
>+            
>+            BasicBlock* operator*()
>+            {
>+                return m_block->successor(index);
>+            }
>+            
>+            iterator& operator++()
>+            {
>+                m_index++;
>+                return *this;
>+            }
>+            
>+            bool operator==(const iterator& other) const
>+            {
>+                return m_index == other.m_index;
>+            }
>+            
>+            bool operator!=(const iterator& other) const
>+            {
>+                return !(*this == other);
>+            }
>+        private:
>+            BasicBlock* m_block;
>+            unsigned m_index;
>+        };
>+        
>+        iterator begin()
>+        {
>+            return iterator(m_block, 0);
>+        }
>+        
>+        iterator end()
>+        {
>+            return iterator(m_block, m_block->numSuccessors());
>+        }
>+        
>+    private:
>+        BasicBlock* m_block;
>+    };
>+    
>+    SuccessorsIterable successors()
>+    {
>+        return SuccessorsIterable(this);
>+    }
>+    
>     void removePredecessor(BasicBlock* block);
>     void replacePredecessor(BasicBlock* from, BasicBlock* to);
> 
>@@ -169,8 +243,9 @@ struct BasicBlock : RefCounted<BasicBloc
>     unsigned innerMostLoopIndices[numberOfInnerMostLoopIndices];
> 
>     struct SSAData {
>-        Operands<Availability> availabilityAtHead;
>-        Operands<Availability> availabilityAtTail;
>+        AvailabilityMap availabilityAtHead;
>+        AvailabilityMap availabilityAtTail;
>+        
>         HashSet<Node*> liveAtHead;
>         HashSet<Node*> liveAtTail;
>         HashMap<Node*, AbstractValue> valuesAtHead;
>@@ -183,7 +258,7 @@ struct BasicBlock : RefCounted<BasicBloc
>     
> private:
>     friend class InsertionSet;
>-    Vector<Node*, 8> m_nodes;
>+    BlockNodeList m_nodes;
> };
> 
> typedef Vector<BasicBlock*, 5> BlockList;
>Index: Source/JavaScriptCore/dfg/DFGGraph.h
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGGraph.h	(revision 173672)
>+++ Source/JavaScriptCore/dfg/DFGGraph.h	(working copy)
>@@ -681,6 +681,110 @@ public:
>     BlockList blocksInPreOrder();
>     BlockList blocksInPostOrder();
>     
>+    class NaturalBlockIterable {
>+    public:
>+        NaturalBlockIterable()
>+            : m_graph(nullptr)
>+        {
>+        }
>+        
>+        NaturalBlockIterable(Graph& graph)
>+            : m_graph(&graph)
>+        {
>+        }
>+        
>+        class iterator {
>+        public:
>+            iterator()
>+                : m_graph(nullptr)
>+                , m_index(0)
>+            {
>+            }
>+            
>+            iterator(Graph& graph, BlockIndex index)
>+                : m_graph(&graph)
>+                , m_index(findNext(index))
>+            {
>+            }
>+            
>+            BasicBlock *operator*()
>+            {
>+                return m_graph->block(index);
>+            }
>+            
>+            iterator& operator++()
>+            {
>+                m_index = findNext(m_index);
>+                return *this;
>+            }
>+            
>+            bool operator==(const iterator& other) const
>+            {
>+                return m_index == other.m_index;
>+            }
>+            
>+            bool operator!=(const iterator& other) const
>+            {
>+                return !(*this == other);
>+            }
>+            
>+        private:
>+            BlockIndex findNext(BlockIndex index)
>+            {
>+                while (index < m_graph->numBlocks() && !m_graph->block(index))
>+                    index++;
>+                return index;
>+            }
>+            
>+            Graph* m_graph;
>+            BlockIndex m_index;
>+        };
>+        
>+        iterator begin()
>+        {
>+            return iterator(*m_graph, 0);
>+        }
>+        
>+        iterator end()
>+        {
>+            return iterator(*m_graph, m_graph->numBlocks());
>+        }
>+        
>+    private:
>+        Graph* m_graph;
>+    };
>+    
>+    NaturalBlockIterable blocksInNaturalOrder()
>+    {
>+        return NaturalBlockIterable(*this);
>+    }
>+    
>+    template<typename ChildFunctor>
>+    void doToChildrenWithNode(Node* node, const ChildFunctor& functor)
>+    {
>+        DFG_NODE_DO_TO_CHILDREN(node, functor);
>+    }
>+    
>+    template<typename ChildFunctor>
>+    void doToChildEdges(Node* node, const ChildFunctor& functor)
>+    {
>+        doToChildrenWithNode(
>+            node,
>+            [&functor] (Node*, Edge& edge) {
>+                functor(edge);
>+            });
>+    }
>+    
>+    template<typename ChildFunctor>
>+    void doToChildren(Node* node, const ChildFunctor& functor)
>+    {
>+        doToChildrenWithNode(
>+            node,
>+            [&functor] (Node*, Edge edge) {
>+                functor(edge);
>+            });
>+    }
>+    
>     Profiler::Compilation* compilation() { return m_plan.compilation.get(); }
>     
>     DesiredIdentifiers& identifiers() { return m_plan.identifiers; }
>@@ -741,6 +845,7 @@ public:
>     Bag<SwitchData> m_switchData;
>     Bag<MultiGetByOffsetData> m_multiGetByOffsetData;
>     Bag<MultiPutByOffsetData> m_multiPutByOffsetData;
>+    Bag<ObjectMaterializationData> m_objectMaterializationData;
>     Vector<InlineVariableData, 4> m_inlineVariableData;
>     HashMap<CodeBlock*, std::unique_ptr<FullBytecodeLiveness>> m_bytecodeLiveness;
>     bool m_hasArguments;
>Index: Source/JavaScriptCore/dfg/DFGHeapLocation.cpp
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGHeapLocation.cpp	(revision 173672)
>+++ Source/JavaScriptCore/dfg/DFGHeapLocation.cpp	(working copy)
>@@ -147,6 +147,10 @@ void printInternal(PrintStream& out, Loc
>     case AllocationProfileWatchpointLoc:
>         out.print("AllocationProfileWatchpointLoc");
>         return;
>+        
>+    case StructureLoc:
>+        out.print("StructureLoc");
>+        return;
>     }
>     
>     RELEASE_ASSERT_NOT_REACHED();
>Index: Source/JavaScriptCore/dfg/DFGHeapLocation.h
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGHeapLocation.h	(revision 173672)
>+++ Source/JavaScriptCore/dfg/DFGHeapLocation.h	(working copy)
>@@ -55,6 +55,7 @@ enum LocationKind {
>     MyArgumentsLengthLoc,
>     NamedPropertyLoc,
>     SetterLoc,
>+    StructureLoc,
>     TypeOfLoc,
>     TypedArrayByteOffsetLoc,
>     VarInjectionWatchpointLoc,
>Index: Source/JavaScriptCore/dfg/DFGInsertOSRHintsForUpdate.cpp
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGInsertOSRHintsForUpdate.cpp	(revision 0)
>+++ Source/JavaScriptCore/dfg/DFGInsertOSRHintsForUpdate.cpp	(working copy)
>@@ -0,0 +1,58 @@
>+/*
>+ * Copyright (C) 2014 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. 
>+ */
>+
>+#include "config.h"
>+#include "DFGInsertOSRHintsForUpdate.h"
>+
>+#if ENABLE(DFG_JIT)
>+
>+namespace JSC { namespace DFG {
>+
>+void insertOSRHintsForUpdate(
>+    InsertionSet& insertionSet, unsigned nodeIndex, AvailabilityMap& availability,
>+    Node* originalNode, Node* newNode)
>+{
>+    for (unsigned i = availability.m_locals.size(); i--;) {
>+        int operand = availability.m_ocals.operandForIndex(i);
>+        
>+        if (availability.m_locals[i].hasNode() && availability.m_locals[i].node() == originalNode) {
>+            insertionSet.insertNode(
>+                nodeIndex, SpecNone, MovHint, NodeOrigin(), OpInfo(operand),
>+                newNode->defaultEdge());
>+        }
>+    }
>+    
>+    for (auto pair : availability.m_heap) {
>+        if (pair.value.hasNode() && pair.value.node() == originalNode) {
>+            insertionSet.insertNode(
>+                nodeIndex, pair.key.createHint(insertionSet.graph(), NodeOrigin(), newNode));
>+        }
>+    }
>+}
>+
>+} } // namespace JSC::DFG
>+
>+#endif // ENABLE(DFG_JIT)
>+
>Index: Source/JavaScriptCore/dfg/DFGInsertOSRHintsForUpdate.h
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGInsertOSRHintsForUpdate.h	(revision 0)
>+++ Source/JavaScriptCore/dfg/DFGInsertOSRHintsForUpdate.h	(working copy)
>@@ -0,0 +1,45 @@
>+/*
>+ * Copyright (C) 2014 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. 
>+ */
>+
>+#ifndef DFGInsertOSRHintsForUpdate_h
>+#define DFGInsertOSRHintsForUpdate_h
>+
>+#if ENABLE(DFG_JIT)
>+
>+#include "DFGInsertionSet.h"
>+#include "DFGAvailabilityMap.h"
>+
>+namespace JSC { namespace DFG {
>+
>+void insertOSRHintsForUpdate(
>+    InsertionSet&, unsigned nodeIndex, AvailabilityMap&,
>+    Node* originalNode, Node* newNode);
>+
>+} } // namespace JSC::DFG
>+
>+#endif // ENABLE(DFG_JIT)
>+
>+#endif // DFGInsertOSRHintsForUpdate_h
>+
>Index: Source/JavaScriptCore/dfg/DFGInsertionSet.h
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGInsertionSet.h	(revision 173672)
>+++ Source/JavaScriptCore/dfg/DFGInsertionSet.h	(working copy)
>@@ -43,6 +43,8 @@ public:
>     {
>     }
>     
>+    Graph& graph() { return m_graph; }
>+    
>     Node* insert(const Insertion& insertion)
>     {
>         ASSERT(!m_insertions.size() || m_insertions.last().index() <= insertion.index());
>Index: Source/JavaScriptCore/dfg/DFGNode.h
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGNode.h	(revision 173672)
>+++ Source/JavaScriptCore/dfg/DFGNode.h	(working copy)
>@@ -38,6 +38,7 @@
> #include "DFGNodeFlags.h"
> #include "DFGNodeOrigin.h"
> #include "DFGNodeType.h"
>+#include "DFGObjectMaterializationData.h"
> #include "DFGTransition.h"
> #include "DFGUseKind.h"
> #include "DFGVariableAccessData.h"
>@@ -495,6 +496,35 @@ struct Node {
>         m_flags &= ~NodeClobbersWorld;
>     }
>     
>+    void convertToPutByOffsetHint()
>+    {
>+        ASSERT(m_op == PutByOffset);
>+        m_op = PutByOffsetHint;
>+        m_opInfo = storageAccessData().identifierNumber;
>+        child1() = child2();
>+        child2() = child3();
>+        child3() = Edge();
>+    }
>+    
>+    void convertToPutStructureHint(Node* structure)
>+    {
>+        ASSERT(m_op == PutStructure);
>+        ASSERT(structure->structure() == transition()->next);
>+        m_op = PhantomPutStructure;
>+        m_opInfo = 0;
>+        child2() = Edge(structure, KnownCellUse);
>+    }
>+    
>+    void convertToPhantomNewObject()
>+    {
>+        ASSERT(m_op == NewObject || m_op == MaterializeNewObject);
>+        m_op = PhantomNewObject;
>+        m_flags &= ~NodeHasVarArgs;
>+        m_opInfo = 0;
>+        m_opInfo2 = 0;
>+        children = AdjacencyList();
>+    }
>+    
>     void convertToPhantomLocal()
>     {
>         ASSERT(m_op == Phantom && (child1()->op() == Phi || child1()->op() == SetLocal || child1()->op() == SetArgument));
>@@ -699,6 +729,7 @@ struct Node {
>         case PutById:
>         case PutByIdFlush:
>         case PutByIdDirect:
>+        case PutByOffsetHint:
>             return true;
>         default:
>             return false;
>@@ -1100,6 +1131,7 @@ struct Node {
>     {
>         switch (op()) {
>         case PutStructure:
>+        case PutStructureHint:
>         case AllocatePropertyStorage:
>         case ReallocatePropertyStorage:
>             return true;
>@@ -1136,6 +1168,7 @@ struct Node {
>         case ArrayifyToStructure:
>         case NewObject:
>         case NewStringObject:
>+        case PhantomStructure:
>             return true;
>         default:
>             return false;
>@@ -1150,7 +1183,14 @@ struct Node {
>     
>     bool hasStorageAccessData()
>     {
>-        return op() == GetByOffset || op() == GetGetterSetterByOffset || op() == PutByOffset;
>+        switch (op()) {
>+        case GetByOffset:
>+        case PutByOffset:
>+        case GetGetterSetterByOffset:
>+            return true;
>+        default:
>+            return false;
>+        }
>     }
>     
>     unsigned storageAccessDataIndex()
>@@ -1179,6 +1219,16 @@ struct Node {
>         return *reinterpret_cast<MultiPutByOffsetData*>(m_opInfo);
>     }
>     
>+    bool hasObjectMaterializationData()
>+    {
>+        return op() == MaterializeNewObject;
>+    }
>+    
>+    ObjectMaterializationData& objectMaterializationData()
>+    {
>+        return *reinterpret_cast<ObjectMaterializationData*>(m_opInfo);
>+    }
>+    
>     bool hasFunctionDeclIndex()
>     {
>         return op() == NewFunction
>Index: Source/JavaScriptCore/dfg/DFGNodeType.h
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGNodeType.h	(revision 173672)
>+++ Source/JavaScriptCore/dfg/DFGNodeType.h	(working copy)
>@@ -228,6 +228,14 @@ namespace JSC { namespace DFG {
>     macro(NewTypedArray, NodeResultJS | NodeClobbersWorld | NodeMustGenerate) \
>     macro(NewRegexp, NodeResultJS) \
>     \
>+    /* Support for allocation sinking. */\
>+    macro(PhantomNewObject, NodeResultJS) \
>+    macro(PhantomStructure, NodeResultJS) \
>+    macro(PutByOffsetHint, NodeMustGenerate) \
>+    macro(CheckStructureImmediate, NodeMustGenerate) \
>+    macro(PutStructureHint, NodeMustGenerate) \
>+    macro(MaterializeNewObject, NodeResultJS | NodeHasVarArgs) \
>+    \
>     /* Nodes for misc operations. */\
>     macro(Breakpoint, NodeMustGenerate) \
>     macro(ProfileWillCall, NodeMustGenerate) \
>Index: Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp	(revision 173672)
>+++ Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp	(working copy)
>@@ -87,6 +87,8 @@ public:
>                 for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex)
>                     calculator.executeNode(block->at(nodeIndex));
>                 
>+                calculator.m_availability.prune();
>+                
>                 if (calculator.m_availability == block->ssa->availabilityAtTail)
>                     continue;
>                 
>@@ -95,11 +97,7 @@ public:
>                 
>                 for (unsigned successorIndex = block->numSuccessors(); successorIndex--;) {
>                     BasicBlock* successor = block->successor(successorIndex);
>-                    for (unsigned i = calculator.m_availability.size(); i--;) {
>-                        successor->ssa->availabilityAtHead[i] =
>-                            calculator.m_availability[i].merge(
>-                                successor->ssa->availabilityAtHead[i]);
>-                    }
>+                    successor->ssa->availabilityAtHead.merge(calculator.m_availability);
>                 }
>             }
>         } while (changed);
>@@ -127,38 +125,50 @@ void LocalOSRAvailabilityCalculator::beg
>     m_availability = block->ssa->availabilityAtHead;
> }
> 
>+void LocalOSRAvailabilityCalculator::endBlock(BasicBlock* block)
>+{
>+    m_availability = block->ssa->availabilityAtTail;
>+}
>+
> void LocalOSRAvailabilityCalculator::executeNode(Node* node)
> {
>     switch (node->op()) {
>     case SetLocal: {
>         VariableAccessData* variable = node->variableAccessData();
>-        m_availability.operand(variable->local()) =
>+        m_availability.m_locals.operand(variable->local()) =
>             Availability(node->child1().node(), variable->flushedAt());
>         break;
>     }
> 
>     case GetArgument: {
>         VariableAccessData* variable = node->variableAccessData();
>-        m_availability.operand(variable->local()) =
>+        m_availability.m_locals.operand(variable->local()) =
>             Availability(node, variable->flushedAt());
>         break;
>     }
> 
>     case MovHint: {
>-        m_availability.operand(node->unlinkedLocal()) =
>+        m_availability.m_locals.operand(node->unlinkedLocal()) =
>             Availability(node->child1().node());
>         break;
>     }
> 
>     case ZombieHint: {
>-        m_availability.operand(node->unlinkedLocal()) =
>+        m_availability.m_locals.operand(node->unlinkedLocal()) =
>             Availability::unavailable();
>         break;
>     }
>-
>+        
>     default:
>         break;
>     }
>+    
>+    promote(
>+        node,
>+        [&] (PromotedHeapLocation location, Edge value) {
>+            m_availability.m_heap.set(location, Availability(value.node()));
>+        },
>+        [&] (PromotedHeapLocation) { });
> }
> 
> } } // namespace JSC::DFG
>Index: Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.h
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.h	(revision 173672)
>+++ Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.h	(working copy)
>@@ -49,9 +49,10 @@ public:
>     ~LocalOSRAvailabilityCalculator();
>     
>     void beginBlock(BasicBlock*);
>+    void endBlock(BasicBlock*); // Useful if you want to get data for the end of the block. You don't need to call this if you did beginBlock() and then executeNode() for every node.
>     void executeNode(Node*);
>     
>-    Operands<Availability> m_availability;
>+    AvailabilityMap m_availability;
> };
> 
> } } // namespace JSC::DFG
>Index: Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp	(revision 0)
>+++ Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp	(working copy)
>@@ -0,0 +1,729 @@
>+/*
>+ * Copyright (C) 2014 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. 
>+ */
>+
>+#include "config.h"
>+#include "DFGObjectAllocationSinkingPhase.h"
>+
>+#if ENABLE(DFG_JIT)
>+
>+#include "DFGAbstractHeap.h"
>+#include "DFGClobberize.h"
>+#include "DFGGraph.h"
>+#include "DFGInsertionSet.h"
>+#include "DFGPhase.h"
>+#include "JSCInlines.h"
>+
>+namespace JSC { namespace DFG {
>+
>+class ObjectAllocationSinkingPhase : public Phase {
>+public:
>+    ObjectAllocationSinkingPhase(Graph& graph)
>+        : Phase(graph, "object allocation sinking")
>+        , m_ssaCalculator(graph)
>+        , m_insertionSet(graph)
>+    {
>+    }
>+    
>+    bool run()
>+    {
>+        ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
>+        
>+        m_changed = false;
>+        
>+        // Logically we wish to consider every NewObject and sink it. However it's definitely not
>+        // profitable to sink a NewObject that will always escape. So, first we do a very simple
>+        // forward flow analysis that determines the set of NewObject nodes that have any chance
>+        // of benefiting from object allocation sinking. Then we fixpoint the following rules:
>+        //
>+        // - For each NewObject, we turn the original NewObject into a PhantomNewObject and then
>+        //   we insert MaterializeNewObject just before each escaping site. Note that Upsilons
>+        //   constitute escaping sites. Then we use forward flow to eliminate unnecessary cases of
>+        //   MaterializeNewObject. We use the SSACalculator to insert these materializations. If a
>+        //   Phi is ever created that has the PhantomNewObject as one of its kids, then we insert
>+        //   a MaterializeNewObject in front of it; this way we never have a Phi that is confused
>+        //   about whether or not it has the real object. We then turn each PutByOffset over a
>+        //   PhantomNewObject into a PutByOffsetHint.
>+        //
>+        // - We perform the same optimization for MaterializeNewObject. This allows us to cover
>+        //   cases where we had MaterializeNewObject flowing into a PutByOffsetHint.
>+        //
>+        // We could also add this rule:
>+        //
>+        // - If all of the Upsilons of a Phi have a MaterializeNewObject that isn't used by anyone
>+        //   else, then replace the Phi with the MaterializeNewObject.
>+        //
>+        //   FIXME: Implement this. Note that this totally doable but it requires some gnarly
>+        //   code, and to be effective the pruner needs to be aware of it. Currently any Upsilon
>+        //   is considered to be an escape even by the pruner, so it's unlikely that we'll see
>+        //   many cases of Phi over Materializations.
>+        //   https://bugs.webkit.org/show_bug.cgi?id=136927
>+        
>+        if (!performSinking())
>+            return false;
>+        
>+        while (performSinking()) { }
>+        
>+        return true;
>+    }
>+
>+private:
>+    bool performSinking()
>+    {
>+        m_graph.computeRefCounts();
>+        performLivenessAnalysis();
>+        performOSRAvailabilityAnalysis();
>+        
>+        // We want to only do sinking for those things that would benefit. We use a rough
>+        // heuristic: if it's possible for an allocation to make it to a return without escaping,
>+        // then we assume that it's worth sinking. It's a simple forward flow problem.
>+        //
>+        // It just so happens that this forward flow problem also tells us where we would
>+        // materialize those nodes that we choose to sink.
>+        pruneSinkingCandidates();
>+        if (m_sinkCandidates.isEmpty())
>+            return false;
>+        
>+        // At this point we are committed to sinking the sinking candidates.
>+        determineMaterializationPoints();
>+        placeMaterializationPoints();
>+        lowerNonReadingOperationsOnPhantomAllocations();
>+        promoteSunkenFields();
>+        
>+        return true;
>+    }
>+    
>+    void pruneSinkingCandidates()
>+    {
>+        m_sinkCandidates.clear();
>+        BlockMap<HashSet<Node*>> sinkCandidatesAtHead(m_graph);
>+        BlockMap<HashSet<Node*>> sinkCandidatesAtTail(m_graph);
>+        
>+        bool changed;
>+        do {
>+            changed = false;
>+            for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
>+                HashSet<Node*> sinkCandidates = sinkCandidatesAtHead[block];
>+                for (Node* node : *block) {
>+                    handleNode(
>+                        node,
>+                        [&] () {
>+                            sinkCandidates.add(node);
>+                        },
>+                        [&] (Node* escapee) {
>+                            sinkCandidates.remove(escapee);
>+                        });
>+                }
>+                if (sinkCandidatesAtTail[block] == sinkCandidates)
>+                    continue;
>+                
>+                sinkCandidatesAtTail[block] = sinkCandidates;
>+                changed = true;
>+                
>+                for (BasicBlock* successorBlock : block->successors()) {
>+                    for (Node* sinkCandidate : sinkCandidates) {
>+                        if (!successorBlock->ssa->liveAtHead.contains(sinkCandidate))
>+                            continue;
>+                        sinkCandidatesAtHead[successorBlock].add(sinkCandidate);
>+                    }
>+                }
>+            }
>+        } while (changed);
>+        
>+        // A node is a sink candidate if it is in the sinkCandidatesAtTail of a block but not in
>+        // the liveAtTail of that same block.
>+        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
>+            for (Node* sinkCandidate : sinkCandidatesAtTail[block]) {
>+                if (!block->ssa->liveAtTail.contains(sinkCandidate))
>+                    m_sinkCandidates.add(sinkCandidate);
>+            }
>+        }
>+    }
>+    
>+    void determineMaterializationPoints()
>+    {
>+        // The premise of this pass is that if there exists a point in the program where some
>+        // path from a phantom allocation site to that point causes materialization, then *all*
>+        // paths cause materialization. This should mean that there are never any redundant
>+        // materializations.
>+        
>+        m_edgeToMaterializationPoint.clear();
>+        
>+        BlockMap<HashSet<Node*>> materializedAtHead;
>+        BlockMap<HashSet<Node*>> materializedAtTail;
>+        
>+        bool changed;
>+        do {
>+            changed = false;
>+            for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
>+                HashSet<Node*> materialized = materializedAtHead[block];
>+                for (Node* node : *block) {
>+                    handleNode(
>+                        node,
>+                        doNothing,
>+                        [&] (Node* escapee) {
>+                            if (m_sinkCandidates.contains(escapee))
>+                                materialized.add(escapee);
>+                        });
>+                }
>+                
>+                if (materialized == materializedAtTail[block])
>+                    continue;
>+                
>+                changed = true;
>+                
>+                for (BasicBlock* successorBlock : block->successors()) {
>+                    for (Node* materializee : materialized) {
>+                        if (!successorBlock->ssa->liveAtHead.contains(materializee))
>+                            continue;
>+                        materializedAtHead[successorBlock].add(materializee);
>+                    }
>+                }
>+            }
>+        } while (changed);
>+        
>+        // A materialization edge exists at any point where a node escapes but hasn't been
>+        // materialized yet.
>+        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
>+            HashSet<Node*> materialized = materializedAtHead[block];
>+            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
>+                Node* node = block->at(nodeIndex);
>+                
>+                handleNode(
>+                    node,
>+                    doNothing,
>+                    [&] (Node* escapee) {
>+                        if (!m_sinkCandidates.contains(escapee))
>+                            return;
>+                        
>+                        if (!materialized.add(escapee))
>+                            return;
>+                        
>+                        m_edgeToMaterializationPoint.add(
>+                            std::make_pair(where, escapee),
>+                            createMaterialize(escapee, node->origin));
>+                    });
>+            }
>+        }
>+    }
>+    
>+    void placeMaterializationPoints()
>+    {
>+        m_ssaCalculator.reset();
>+        
>+        HashMap<Node*, SSACalculator::Variable*> nodeToVariable;
>+        Vector<Node*> indexToNode;
>+        
>+        for (Node* node : m_sinkCandidates) {
>+            SSACalculator::Variable* variable = m_ssaCalculator.newVariable();
>+            nodeToVariable.add(node, variable);
>+            ASSERT(indexToNode.size() == variable->index());
>+            indexToNode.append(node);
>+        }
>+        
>+        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
>+            for (Node* node : *block) {
>+                if (SSACalculator::Variable* variable = nodeToVariable.get(node))
>+                    m_ssaCalculator.newDef(variable, block, node);
>+                
>+                m_graph.doToChildren(
>+                    node,
>+                    [&] (Edge edge) {
>+                        Node* materialize =
>+                            m_edgeToMaterializationPoint.get(std::make_pair(node, edge.node()));
>+                        if (!materialize)
>+                            return;
>+                        
>+                        m_ssaCalculator.newDef(
>+                            nodeToVariable.get(edge.node()), block, materialize);
>+                    });
>+            }
>+        }
>+        
>+        m_ssaCalculator.computePhis(
>+            [&] (SSACalculator::Variable* variable, BasicBlock* block) -> Node* {
>+                Node* allocation = indexToNode[variable->index()];
>+                if (!block->ssa->liveAtHead.contains(allocation))
>+                    return nullptr;
>+                
>+                Node* phiNode = m_graph.addNode(allocation->prediction(), Phi, NodeOrigin());
>+                phiNode->mergeFlags(NodeResultJS);
>+                return phiNode;
>+            });
>+        
>+        // Place Phis in the right places. Replace all uses of any allocation with the appropriate
>+        // materialization. Create the appropriate Upsilon nodes.
>+        LocalOSRAvailabilityCalculator availabilityCalculator;
>+        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
>+            HashMap<Node*, Node*> mapping;
>+            
>+            for (Node* candidate : block->ssa->liveAtHead) {
>+                SSACalculator::Variable* variable = nodeToVariable.get(candidate);
>+                if (!variable)
>+                    continue;
>+                
>+                Def* def = m_ssaCalculator.reachingDefAtHead(block, variable);
>+                if (!def)
>+                    continue;
>+                
>+                mapping.add(indexToNode[variable->index()], def->value());
>+            }
>+            
>+            availabilityCalculator.beginBlock(block);
>+            for (SSACalculator::Def* phiDef : m_ssaCalculator.phisForBlock(block)) {
>+                m_insertionSet.insert(0, phiDef->value());
>+                
>+                Node* originalNode = indexToNode[phiDef->variable()->index()];
>+                insertOSRHintsForUpdate(
>+                    m_insertionSet, 0, availabilityCalculator, originalNode, phiDef->value());
>+
>+                mapping.add(originalNode, phiDef->value());
>+            }
>+            
>+            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
>+                Node* node = block->at(nodeIndex);
>+
>+                m_graph.doToChildEdges(
>+                    node,
>+                    [&] (Edge edge) {
>+                        Node* materialize = m_edgeToMaterializationPoint.get(
>+                            std::make_pair(node, edge.node()));
>+                        if (materialize) {
>+                            m_insertionSet.insert(nodeIndex, materialize);
>+                            insertOSRHintsForUpdate(
>+                                m_insertionSet, nodeIndex, availabilityCalculator,
>+                                edge.node(), materialize);
>+                        }
>+                    });
>+
>+                availabilityCalculator.executeNode(node);
>+                
>+                m_graph.doToChildEdges(
>+                    node,
>+                    [&] (Edge& edge) {
>+                        if (Node* materialize = mapping.get(edge.node()))
>+                            edge.setNode(materialize);
>+                    });
>+            }
>+            
>+            size_t upsilonInsertionPoint = block->size() - 1;
>+            NodeOrigin upsilonOrigin = block->last()->origin;
>+            for (BasicBlock* successorBlock : block->successors()) {
>+                for (SSACalculator::Def* phiDef : m_ssaCalculator.phisForBlock(successorBlock)) {
>+                    Node* phiNode = phiDef->value();
>+                    SSACalculator::Variable* variable = phiDef->variable();
>+                    Node* allocation = indexToNode[variable->index()];
>+                    
>+                    Node* originalIncoming = mapping.get(allocation);
>+                    Node* incoming;
>+                    if (originalIncoming == allocation) {
>+                        // If we have a Phi that combines materializations with the original
>+                        // phantom object, then the path with the phantom object must materialize.
>+                        
>+                        incoming = createMaterialize(allocation, upsilonOrigin);
>+                        m_insertionSet.insert(upsilonInsertionPoint, incoming);
>+                        insertOSRHintsForUpdate(
>+                            m_insertionSet, upsilonInsertionPoint, availabilityCalculator,
>+                            originalIncoming, incoming);
>+                    } else
>+                        incoming = originalIncoming;
>+                    
>+                    Node* upsilon = m_insertionSet.insertNode(
>+                        upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin,
>+                        OpInfo(phiNode), incoming->defaultEdge());
>+                    
>+                    if (originalIncoming == allocation) {
>+                        m_edgeToMaterializationPoint.add(
>+                            std::make_pair(upsilon, allocation), incoming);
>+                    }
>+                }
>+            }
>+            
>+            m_insertionSet.execute(block);
>+        }
>+        
>+        // At this point we have dummy materialization nodes along with edges to them. This means
>+        // that the part of the control flow graph that prefers to see actual object allocations
>+        // is completely fixed up, except for the materializations themselves.
>+    }
>+    
>+    void lowerNonReadingOperationsOnPhantomAllocations()
>+    {
>+        // Lower everything but reading operations on phantom allocations. We absolutely have to
>+        // lower all writes so as to reveal them to the SSA calculator. We cannot lower reads
>+        // because the whole point is that those go away completely.
>+        
>+        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
>+            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
>+                Node* node = block->at(nodeIndex);
>+                switch (node->op()) {
>+                case PutByOffset: {
>+                    if (m_sinkCandidates.contains(node->child2().node()))
>+                        node->convertToPutByOffsetHint();
>+                    break;
>+                }
>+                    
>+                case PutStructure: {
>+                    if (m_sinkCandidates.contains(node->child1().node())) {
>+                        Node* structure = m_insertionSet.insertNode(
>+                            nodeIndex, SpecCellOther, PhantomStructure, node->origin,
>+                            OpInfo(node->transition()->next));
>+                        node->convertToPutStructureHint(structure);
>+                    }
>+                    break;
>+                }
>+                    
>+                case NewObject: {
>+                    if (m_sinkCandidates.contains(node)) {
>+                        Node* structure = m_insertionSet.insertNode(
>+                            nodeIndex + 1, SpecCellOther, PhantomStructure, node->origin,
>+                            OpInfo(node->structure()));
>+                        m_insertionSet.insertNode(
>+                            nodeIndex + 1, SpecNone, PutStructureHint, node->origin,
>+                            Edge(node, KnownCellUse), Edge(structure, KnownCellUse));
>+                        node->convertToPhantomNewObject();
>+                    }
>+                    break;
>+                }
>+                    
>+                case MaterializeNewObject: {
>+                    if (m_sinkCandidates.contains(node)) {
>+                        m_insertionSet.insertNode(
>+                            nodeIndex + 1, SpecNone, PutStructureHint, node->origin,
>+                            Edge(node, KnownCellUse), m_graph.varArgChild(node, 0));
>+                        for (unsigned i = 0; i < node->objectMaterializationData().m_properties.size(); ++i) {
>+                            m_insertionSet.insertNode(
>+                                nodeIndex + 1, SpecNone, PutByOffsetHint, node->origin,
>+                                Edge(node, KnownCellUse),m_graph.varArgChild(node, i + 1));
>+                        }
>+                        node->convertToPhantomNewObject();
>+                    }
>+                    break;
>+                }
>+                    
>+                default:
>+                    break;
>+                }
>+            }
>+            m_insertionSet.execute(block);
>+        }
>+    }
>+    
>+    void promoteSunkenFields()
>+    {
>+        // Henceforth when we encounter a materialization point, we will want to ask *who* it is
>+        // a materialization for. Invert the map to be able to answer such questions.
>+        m_materializationPointToEscapee.clear();
>+        for (auto pair : m_edgeToMaterializationPoint)
>+            m_materializationPointToEscapee.add(pair.value, pair.key.second);
>+        
>+        // Collect the set of heap locations that we will be operating over.
>+        HashSet<PromotedHeapLocation> locations;
>+        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
>+            for (Node* node : *block) {
>+                promote(
>+                    node,
>+                    [&] (PromotedHeapLocation location, Edge) {
>+                        locations.add(location);
>+                    },
>+                    [&] (PromotedHeapLocation location) {
>+                        locations.add(location);
>+                    });
>+            }
>+        }
>+        
>+        // Figure out which locations belong to which allocations.
>+        m_locationsForAllocation.clear();
>+        for (PromotedHeapLocation location : locations) {
>+            auto result = m_locationsForAllocation.add(location.base(), Vector<PromotedHeapLocation>());
>+            ASSERT(!result.iterator->value.contains(location));
>+            result.iterator->value.append(location);
>+        }
>+        
>+        // For each sunken thingy, make sure we create Bottom values for all of its fields.
>+        // Note that this has the hilarious slight inefficiency of creating redundant hints for
>+        // things that were previously materializations. This should only impact compile times and
>+        // not code quality, and it's necessary for soundness without some data structure hackage.
>+        // For example, a MaterializeNewObject that we choose to sink may have new fields added to
>+        // it conditionally. That would necessitate Bottoms.
>+        Node* bottom = nullptr;
>+        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
>+            if (block == m_graph.block(0))
>+                bottom = m_insertionSet.insertNode(0, SpecNone, Bottom, NodeOrigin());
>+            
>+            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
>+                Node* node = block->at(nodeIndex);
>+                for (PromotedHeapLocation location : locationsForAllocation.get(node)) {
>+                    m_insertionSet.insertNode(
>+                        nodeIndex + 1, location.createHint(m_graph, node->origin, bottom));
>+                }
>+            }
>+            m_insertionSet.execute(block);
>+        }
>+
>+        m_ssaCalculator.reset();
>+
>+        // Collect the set of "variables" that we will be sinking.
>+        m_locationToVariable.clear();
>+        m_indexToLocation.clear();
>+        for (PromotedHeapLocation location : locations) {
>+            SSACalculator::Variable* variable = m_ssaCalculator.newVariable();
>+            locationToVariable.add(location, variable);
>+            ASSERT(indexToLocation.size() == variable->index());
>+            indexToLocation.append(location);
>+        }
>+        
>+        // Create Defs from the existing hints.
>+        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
>+            for (Node* node : *block) {
>+                promote(
>+                    node,
>+                    [&] (PromotedHeapLocation location, Edge value) {
>+                        SSACalculator::Variable* variable = locationToVariable.get(location);
>+                        m_ssaCalculator.newDef(variable, block, value.node());
>+                    },
>+                    doNothing);
>+            }
>+        }
>+        
>+        // OMG run the SSA calculator to create Phis!
>+        m_ssaCalculator.computePhis(
>+            [&] (SSACalculator::Variable* variable, BasicBlock* block) -> Node* {
>+                PromotedHeapLocation location = indexToLocation[variable->index()];
>+                if (!block->ssa->liveAtHead.contains(location.base()))
>+                    return nullptr;
>+                
>+                Node* phiNode = m_graph.addNode(SpecHeapTop, Phi, NodeOrigin());
>+                phiNode->mergeFlags(NodeResultJS);
>+                return phiNode;
>+            });
>+        
>+        // Place Phis in the right places, replace all uses of any load with the appropriate
>+        // value, and create the appropriate Upsilon nodes.
>+        m_graph.clearReplacements();
>+        for (BasicBlock* block : m_graph.blocksInPreOrder()) {
>+            // This mapping table is intended to be lazy. If something is omitted from the table,
>+            // it means that there haven't been any local stores to that promoted heap location.
>+            m_localMapping.clear();
>+            
>+            // Insert the Phi functions that we had previously created.
>+            for (SSACalculator::Def* phiDef : m_ssaCalculator.phisForBlock(block)) {
>+                PromotedHeapLocation location = m_indexToLocation[phiDef->variable()->index()];
>+                
>+                m_insertionSet.insert(
>+                    0, phiDef->value());
>+                m_insertionSet.insert(
>+                    0, location.createHint(m_graph, NodeOrigin(), phiDef->value()));
>+                m_localMapping.add(location, phiDef->value());
>+            }
>+            
>+            // Process the block and replace all uses of loads with the promoted value.
>+            for (Node* node : *block) {
>+                m_graph.performSubstitution(node);
>+                
>+                if (Node* escapee = m_materializationPointToEscapee.get(node))
>+                    populateMaterialize(block, node, escapee);
>+                
>+                promote(
>+                    node,
>+                    [&] (PromotedHeapLocation location, Edge value) {
>+                        m_localMapping.set(location, edge.node());
>+                    },
>+                    [&] (PromotedHeapLocation location) {
>+                        node->replaceWith(resolve(block, location));
>+                    });
>+            }
>+            
>+            // Gotta drop some Upsilons.
>+            size_t upsilonInsertionPoint = block->size() - 1;
>+            NodeOrigin upsilonOrigin = block->last()->origin;
>+            for (BasicBlock* successorBlock : block->successors()) {
>+                for (SSACalculator::Def* phiDef : m_ssaCalculator.phisForBlock(successorBlock)) {
>+                    Node* phiNode = phiDef->value();
>+                    SSACalculator::Variable* variable = phiDef->variable();
>+                    PromotedHeapLocation location = m_indexToLocation[variable->index()];
>+                    Node* incoming = resolve(block, location);
>+                    
>+                    m_insertionSet.insertNode(
>+                        upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin,
>+                        OpInfo(phiNode), incoming->defaultEdge());
>+                }
>+            }
>+            
>+            m_insertionSet.execute(block);
>+        }
>+    }
>+    
>+    Node* resolve(BasicBlock* block, PromotedHeapLocation location)
>+    {
>+        if (Node* result = m_localMapping.get(location))
>+            return result;
>+        
>+        // This implies that there is no local mapping. Find a non-local mapping.
>+        Def* def = m_ssaCalculator.nonLocalReachingDef(block, m_locationToVariable.get(location));
>+        ASSERT(def);
>+        ASSERT(def->value());
>+        m_localMapping.add(locaftion, def->value());
>+        return def->value();
>+    }
>+
>+    template<typename... Args>
>+    static void doNothing(Args...) { }
>+    
>+    template<typename SinkCandidateFunctor, typename EscapeFunctor>
>+    void handleNode(
>+        Node* node,
>+        const SinkCandidateFunctor& sinkCandidate,
>+        const EscapeFunctor& escape)
>+    {
>+        switch (node->op()) {
>+        case NewObject:
>+        case MaterializeNewObject:
>+            sinkCandidate();
>+            break;
>+            
>+        case CheckStructure:
>+        case GetByOffset:
>+        case MultiGetByOffset:
>+        case PutStructure:
>+        case GetGetterSetterByOffset:
>+        case MovHint:
>+            break;
>+            
>+        case PutByOffset:
>+            escape(node->child3().node());
>+            break;
>+            
>+        case MultiPutByOffset:
>+            // FIXME: In the future we should be able to handle this. It's just a matter of
>+            // building the appropriate *Hint variant of this instruction, along with a
>+            // PhantomStructureSelect node - since this transforms the Structure in a conditional
>+            // way.
>+            // https://bugs.webkit.org/show_bug.cgi?id=136924
>+            escape(node->child1().node());
>+            escape(node->child2().node());
>+            break;
>+
>+        default:
>+            m_graph.doToChildren(
>+                node,
>+                [&escape] (Edge edge) {
>+                    escape(edge.node());
>+                });
>+            break;
>+        }
>+    }
>+    
>+    Node* createMaterialize(Node* escapee, const NodeOrigin whereOrigin)
>+    {
>+        switch (escapee->op()) {
>+        case NewObject:
>+        case MaterializeNewObject:
>+            return m_graph.addNode(
>+                escapee->prediction(), MaterializeNewObject,
>+                NodeOrigin(
>+                    escapee->origin.semantic,
>+                    whereOrigin.forExit),
>+                OpInfo(m_graph.m_objectMaterializationData.add()),
>+                OpInfo(), 0, 0);
>+            
>+        default:
>+            DFG_CRASH(m_graph, where, "Bad escapee op");
>+            return nullptr;
>+        }
>+        
>+        return result;
>+    }
>+    
>+    void populateMaterialize(BasicBlock* block, Node* node, Node* escapee)
>+    {
>+        switch (node->op()) {
>+        case MaterializeNewObject: {
>+            ObjectMaterializationData* data = node->objectMaterializationData();
>+            unsigned firstChild = m_graph.m_varArgChildren.size();
>+            
>+            Vector<PromotedHeapLocation>& locations = m_LocationsForAllocation.get(escapee);
>+            
>+            PromotedHeapLocation structure(StructurePLoc, escapee);
>+            ASSERT(locations.contains(structure));
>+            
>+            m_graph.m_varArgChildren.append(resolve(block, structure));
>+            
>+            for (unsigned i = 0; i < locations.size(); ++i) {
>+                switch (locations[i].kind()) {
>+                case StructurePLoc: {
>+                    ASSERT(locations[i] == structure);
>+                    break;
>+                }
>+                    
>+                case NamedPropertyPLoc: {
>+                    Node* value = resolve(block, locations[i]);
>+                    if (value->op() == Bottom) {
>+                        // We can skip Bottoms entirely.
>+                        break;
>+                    }
>+                    
>+                    data->m_properties.append(PhantomPropertyValue(locations[i].info()));
>+                    m_graph.m_varArgChildren.append(value);
>+                    break;
>+                }
>+                    
>+                default:
>+                    DFG_CRASH(m_graph, node, "Bad location kind");
>+                }
>+            }
>+            
>+            node->children = AdjacencyList(
>+                AdjacencyList::Variable,
>+                firstChild, m_graph.m_varArgChildren.size() - firstChild);
>+            break;
>+        }
>+            
>+        default:
>+            DFG_CRASH(m_graph, node, "Bad materialize op");
>+            break;
>+        }
>+    }
>+    
>+    SSACalculator m_ssaCalculator;
>+    HashSet<Node*> m_sinkCandidates;
>+    HashMap<std::pair<Node*, Node*>, Node*> m_edgeToMaterializationPoint;
>+    HashMap<Node*, Node*> m_materializationPointToEscapee;
>+    HashMap<Node*, Vector<PromotedHeapLocation>> m_locationsForAllocation;
>+    HashMap<PromotedHeapLocation, SSACalculator::Variable*> m_locationToVariable;
>+    Vector<PromotedHeapLocation> m_indexToLocation;
>+    HashMap<PromotedHeapLocation, Node*> m_localMapping;
>+    InsertionSet m_insertionSet;
>+};
>+    
>+bool performObjectAllocationSinking(Graph& graph)
>+{
>+    SamplingRegion samplingRegion("DFG Object Allocation Sinking Phase");
>+    return runPhase<ObjectAllocationSinkingPhase>(graph);
>+}
>+
>+} } // namespace JSC::DFG
>+
>+#endif // ENABLE(DFG_JIT)
>+
>Index: Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.h
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.h	(revision 0)
>+++ Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.h	(working copy)
>@@ -0,0 +1,47 @@
>+/*
>+ * Copyright (C) 2014 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. 
>+ */
>+
>+#ifndef DFGObjectAllocationSinkingPhase_h
>+#define DFGObjectAllocationSinkingPhase_h
>+
>+#if ENABLE(DFG_JIT)
>+
>+namespace JSC { namespace DFG {
>+
>+class Graph;
>+
>+// Sinks object allocations down to their uses. This will sink the allocations over OSR exits, by
>+// replacing all stores to those objects with store hints so that OSR exit can materialize the
>+// object. This may sink allocations past returns, creating control flow paths along which the
>+// objects are not allocated at all. Replaces all uses of the objects' fields with SSA data flow.
>+
>+bool performObjectAllocationSinking(Graph&);
>+
>+} } // namespace JSC::DFG
>+
>+#endif // ENABLE(DFG_JIT)
>+
>+#endif // DFGObjectAllocationSinkingPhase_h
>+
>Index: Source/JavaScriptCore/dfg/DFGObjectMaterializationData.cpp
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGObjectMaterializationData.cpp	(revision 0)
>+++ Source/JavaScriptCore/dfg/DFGObjectMaterializationData.cpp	(working copy)
>@@ -0,0 +1,58 @@
>+/*
>+ * Copyright (C) 2014 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. 
>+ */
>+
>+#include "config.h"
>+#include "DFGObjectMaterializationData.h"
>+
>+namespace JSC { namespace DFG {
>+
>+void PhantomPropertyValue::dump(PrintStream& out) const
>+{
>+    out.print("id", m_identifierNumber);
>+}
>+
>+void ObjectMaterializationData::dump(PrintStream& out) const
>+{
>+    out.print("[", listDump(m_properties), "]");
>+}
>+
>+float ObjectMaterializationData::oneWaySimilarityScore(
>+    const ObjectMaterializationData& other) const
>+{
>+    unsigned numHits = 0;
>+    for (PhantomPropertyValue value : m_properties) {
>+        if (other.m_properties.contains(value))
>+            numHits++;
>+    }
>+    return static_cast<float>(numHits) / static_cast<float>(m_properties.size());
>+}
>+
>+float ObjectMaterializationData::similarityScore(const ObjectMaterializationData& other) const
>+{
>+    return std::min(oneWaySimilarityScore(other), other.oneWaySimilarityScore(*this));
>+}
>+
>+} } // namespace JSC::DFG
>+
>Index: Source/JavaScriptCore/dfg/DFGObjectMaterializationData.h
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGObjectMaterializationData.h	(revision 0)
>+++ Source/JavaScriptCore/dfg/DFGObjectMaterializationData.h	(working copy)
>@@ -0,0 +1,72 @@
>+/*
>+ * Copyright (C) 2014 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. 
>+ */
>+
>+#ifndef DFGObjectMaterializationData_h
>+#define DFGObjectMaterializationData_h
>+
>+#if ENABLE(DFG_JIT)
>+
>+namespace JSC { namespace DFG {
>+
>+struct PhantomPropertyValue {
>+    PhantomPropertyValue()
>+        : m_identifierNumber(UINT_MAX)
>+    {
>+    }
>+    
>+    PhantomPropertyValue(unsigned identifierNumber)
>+        : m_identifierNumber(identifierNumber)
>+    {
>+    }
>+    
>+    unsigned m_identifierNumber;
>+    
>+    bool operator==(const PhantomPropertyValue& other) const
>+    {
>+        return m_identifierNumber == other.m_identifierNumber;
>+    }
>+    
>+    void dump(PrintStream&) const;
>+};
>+
>+struct ObjectMaterializationData {
>+    // Determines the meaning of the passed nodes.
>+    Vector<PhantomPropertyValue> m_properties;
>+    
>+    void dump(PrintStream&) const;
>+    
>+    // The fraction of my properties that the other data has.
>+    float oneWaySimilarityScore(const ObjectMaterializationData&) const;
>+    
>+    // The minimum of the two possible one-way scores.
>+    float similarityScore(const ObjectMaterializationData&) const;
>+};
>+
>+} } // namespace JSC::DFG
>+
>+#endif // ENABLE(DFG_JIT)
>+
>+#endif // DFGObjectMaterializationData_h
>+
>Index: Source/JavaScriptCore/dfg/DFGPhiChildren.cpp
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGPhiChildren.cpp	(revision 0)
>+++ Source/JavaScriptCore/dfg/DFGPhiChildren.cpp	(working copy)
>@@ -0,0 +1,61 @@
>+/*
>+ * Copyright (C) 2014 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. 
>+ */
>+
>+#include "config.h"
>+#include "DFGPhiChildren.h"
>+
>+#if ENABLE(DFG_JIT)
>+
>+namespace JSC { namespace DFG {
>+
>+PhiChildren::PhiChildren()
>+{
>+}
>+
>+PhiChildren::PhiChildren(Graph& graph)
>+{
>+    for (BasicBlock* block : graph.blocksInNaturalOrder()) {
>+        for (Node* node : *block) {
>+            if (node->op() != Upsilon)
>+                continue;
>+            
>+            m_children.add(node->phi(), List()).iterator->value.append(node);
>+        }
>+    }
>+}
>+
>+PhiChildren::~PhiChildren()
>+{
>+}
>+
>+const PhiChildren::List& PhiChildren::childrenOf(Node* node) const
>+{
>+    return m_children.get(node);
>+}
>+
>+} } // namespace JSC::DFG
>+
>+#endif // ENABLE(DFG_JIT)
>+
>Index: Source/JavaScriptCore/dfg/DFGPhiChildren.h
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGPhiChildren.h	(revision 0)
>+++ Source/JavaScriptCore/dfg/DFGPhiChildren.h	(working copy)
>@@ -0,0 +1,53 @@
>+/*
>+ * Copyright (C) 2014 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. 
>+ */
>+
>+#ifndef DFGPhiChildren_h
>+#define DFGPhiChildren_h
>+
>+#if ENABLE(DFG_JIT)
>+
>+namespace JSC { namespace DFG {
>+
>+class PhiChildren {
>+public:
>+    typedef Vector<Node*, 3> List;
>+    
>+    PhiChildren();
>+    PhiChildren(Graph&);
>+    ~PhiChildren();
>+    
>+    // The list of Upsilons that point to the children of the Phi.
>+    const List& upsilonsOf(Node*) const;
>+    
>+private:
>+    HashMap<Node*, List> m_children;
>+};
>+
>+} } // namespace JSC::DFG
>+
>+#endif // ENABLE(DFG_JIT)
>+
>+#endif // DFGPhiChildren_h
>+
>Index: Source/JavaScriptCore/dfg/DFGPromotedHeapLocation.cpp
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGPromotedHeapLocation.cpp	(revision 0)
>+++ Source/JavaScriptCore/dfg/DFGPromotedHeapLocation.cpp	(working copy)
>@@ -0,0 +1,86 @@
>+/*
>+ * Copyright (C) 2014 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. 
>+ */
>+
>+#include "config.h"
>+#include "DFGPromotedHeapLocation.h"
>+
>+#if ENABLE(DFG_JIT)
>+
>+namespace JSC { namespace DFG {
>+
>+Node* PromotedHeapLocation::createHint(Graph& graph, NodeOrigin origin, Node* value)
>+{
>+    switch (kind()) {
>+    case StructurePLoc:
>+        return graph.addNode(
>+            SpecNone, PutStructureHint, origin,
>+            Edge(base(), KnownCellUse), value);
>+        
>+    case NamedPropertyPLoc:
>+        return graph.addNode(
>+            SpecNone, PutByOffsetHint, origin,
>+            OpInfo(location.info()), Edge(base(), KnownCellUse), value);
>+        
>+    case InvalidPromotedLocationKind:
>+        return nullptr;
>+    }
>+    
>+    RELEASE_ASSERT_NOT_REACHED();
>+}
>+
>+void PromotedHeapLocation::dump(PrintStream& out) const
>+{
>+    out.print(m_kind, "(", m_base, ", ", m_info, ")");
>+}
>+
>+} } // namespace JSC::DFG
>+
>+namespace WTF {
>+
>+using namespace JSC::DFG;
>+
>+void printInternal(PrintStream& out, PromotedLocationKind kind)
>+{
>+    switch (kind) {
>+    case InvalidPromotedLocationKind:
>+        out.print("InvalidPromotedLocationKind");
>+        return;
>+        
>+    case StructurePLoc:
>+        out.print("StructurePLoc");
>+        return;
>+        
>+    case NamedPropertyPLoc:
>+        out.print("NamedPropertyPLoc");
>+        return;
>+    }
>+    
>+    RELEASE_ASSERT_NOT_REACHED();
>+}
>+
>+} // namespace WTF;
>+
>+#endif // ENABLE(DFG_JIT)
>+
>Index: Source/JavaScriptCore/dfg/DFGPromotedHeapLocation.h
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGPromotedHeapLocation.h	(revision 0)
>+++ Source/JavaScriptCore/dfg/DFGPromotedHeapLocation.h	(working copy)
>@@ -0,0 +1,173 @@
>+/*
>+ * Copyright (C) 2014 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. 
>+ */
>+
>+#ifndef DFGPromotedHeapLocation_h
>+#define DFGPromotedHeapLocation_h
>+
>+#if ENABLE(DFG_JIT)
>+
>+#include "DFGNode.h"
>+#include <wtf/PrintStream.h>
>+
>+namespace JSC { namespace DFG {
>+
>+enum PromotedLocationKind {
>+    InvalidPromotedLocationKind,
>+    
>+    StructurePLoc,
>+    NamedPropertyPLoc
>+};
>+
>+class PromotedHeapLocation {
>+public:
>+    PromotedHeapLocation(
>+        PromotedLocationKind kind = InvalidPromotedLocationKind,
>+        Node* base = nullptr, unsigned info = 0)
>+        : m_base(base)
>+        , m_kind(kind)
>+        , m_info(info)
>+    {
>+    }
>+    
>+    PromotedHeapLocation(
>+        PromotedLocationKind kind, Edge base, unsigned info = 0)
>+        : PromotedHeapLocation(kind, base.node(), info)
>+    {
>+    }
>+    
>+    PromotedHeapLocation(WTF::HashTableDeletedValueType)
>+        : m_base(nullptr)
>+        , m_kind(InvalidPromotedLocationKind)
>+        , m_info(1)
>+    {
>+    }
>+    
>+    Node* createHint(Graph&, NodeOrigin, Node* value);
>+    
>+    bool operator!() const { return m_kind == InvalidPromotedLocationKind; }
>+    
>+    PromotedLocationKind kind() const { return m_kind; }
>+    Node* base() const { return m_base; }
>+    unsigned info() const { return m_info; }
>+    
>+    unsigned hash() const
>+    {
>+        return m_kind + WTF::PtrHash<Node*>::hash(m_base) + m_info;
>+    }
>+    
>+    bool operator==(const PromotedHeapLocation& other) const
>+    {
>+        return m_base == other.m_base
>+            && m_kind == other.m_kind
>+            && m_info == other.m_info;
>+    }
>+    
>+    bool isHashTableDeletedValue() const
>+    {
>+        return m_kind == InvalidPromotedLocationKind && m_info;
>+    }
>+    
>+    void dump(PrintStream& out) const;
>+    
>+private:
>+    Node* m_base;
>+    PromotedLocationKind m_kind;
>+    unsigned m_info;
>+};
>+
>+// Note that the write functor is really the useful thing here. The read functor is only useful
>+// for the object allocation sinking phase.
>+template<typename WriteFunctor, typename ReadFunctor>
>+void promote(Node* node, const WriteFunctor& write, const ReadFunctor& read)
>+{
>+    switch (node->op()) {
>+    case CheckStructure:
>+        if (m_sinkCandidates.contains(node->child1().node()))
>+            read(PromotedHeapLocation(StructurePLoc, node->child1()));
>+        break;
>+            
>+    case GetByOffset:
>+    case GetGetterSetterByOffset:
>+        if (m_sinkCandidates.contains(node->child2().node())) {
>+            unsigned identifierNumber =
>+                graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber;
>+            read(PromotedHeapLocation(NamedPropertyPLoc, node->child2(), identifierNumber));
>+        }
>+        break;
>+                                  
>+    case MultiGetByOffset:
>+        if (m_sinkCandidates.contains(node->child1().node())) {
>+            unsigned identifierNumber = node->multiGetByOffsetData().identifierNumber;
>+            read(PromotedHeapLocation(NamedPropertyPLoc, node->child1(), identiferNumber));
>+        }
>+        break;
>+            
>+    case PutStructureHint:
>+        if (m_sinkCandidates.contains(node->child1().node()))
>+            write(PromotedHeapLocation(StructurePLoc, node->child1()), node->child2());
>+        break;
>+            
>+    case PutByOffsetHint:
>+        if (m_sinkCandidates.contains(node->child1().node())) {
>+            unsigned identifierNumber = node->identifierNumber();
>+            write(
>+                PromotedHeapLocation(NamedPropertyPLoc, node->child1(), identifierNumber),
>+                node->child2().node());
>+        }
>+        break;
>+
>+    default:
>+        break;
>+    }
>+}
>+
>+struct PromotedHeapLocationHash {
>+    static unsigned hash(const PromotedHeapLocation& key) { return key.hash(); }
>+    static bool equal(const PromotedHeapLocation& a, const PromotedHeapLocation& b) { return a == b; }
>+    static const bool safeToCompareToEmptyOrDeleted = true;
>+};
>+
>+} } // namespace JSC::DFG
>+
>+namespace WTF {
>+
>+void printInternal(PrintStream&, JSC::DFG::PromotedLocationKind);
>+
>+template<typename T> struct DefaultHash;
>+template<> struct DefaultHash<JSC::DFG::PromotedHeapLocation> {
>+    typedef JSC::DFG::PromotedHeapLocationHash Hash;
>+};
>+
>+template<typename T> struct HashTraits;
>+template<> struct HashTraits<JSC::DFG::PromotedHeapLocation> : SimpleClassHashTraits<JSC::DFG::PromotedHeapLocation> {
>+    static const bool emptyValueIsZero = false;
>+};
>+
>+} // namespace WTF
>+
>+#endif // ENABLE(DFG_JIT)
>+
>+#endif // DFGPromotedHeapLocation_h
>+
>Index: Source/JavaScriptCore/dfg/DFGSSACalculator.cpp
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGSSACalculator.cpp	(revision 173672)
>+++ Source/JavaScriptCore/dfg/DFGSSACalculator.cpp	(working copy)
>@@ -66,6 +66,17 @@ SSACalculator::~SSACalculator()
> {
> }
> 
>+void SSACalculator::reset()
>+{
>+    m_variables.clear();
>+    m_defs.clear();
>+    m_phis.clear();
>+    for (BlockIndex blockIndex = m_data.size(); blockIndex--;) {
>+        m_data[blockIndex].m_defs.clear();
>+        m_data[blockIndex].m_phis.clear();
>+    }
>+}
>+
> SSACalculator::Variable* SSACalculator::newVariable()
> {
>     return &m_variables.alloc(Variable(m_variables.size()));
>Index: Source/JavaScriptCore/dfg/DFGSSACalculator.h
>===================================================================
>--- Source/JavaScriptCore/dfg/DFGSSACalculator.h	(revision 173672)
>+++ Source/JavaScriptCore/dfg/DFGSSACalculator.h	(working copy)
>@@ -105,6 +105,8 @@ public:
>     SSACalculator(Graph&);
>     ~SSACalculator();
>     
>+    void reset();
>+    
>     class Variable {
>     public:
>         unsigned index() const { return m_index; }
>Index: Source/WTF/wtf/Bag.h
>===================================================================
>--- Source/WTF/wtf/Bag.h	(revision 173672)
>+++ Source/WTF/wtf/Bag.h	(working copy)
>@@ -46,17 +46,23 @@ private:
>     
> public:
>     Bag()
>-        : m_head(0)
>+        : m_head(nullptr)
>     {
>     }
>     
>     ~Bag()
>     {
>+        clear();
>+    }
>+    
>+    void clear()
>+    {
>         while (m_head) {
>             Node* current = m_head;
>             m_head = current->m_next;
>             delete current;
>         }
>+        m_head = nullptr;
>     }
>     
>     template<typename... Args>

Actions: View | Formatted Diff | Diff

Attachments on bug 136330: 238103 | 238151 | 238154 | 238219 | 238232 | 238317 | 238320 | 238334 | 238343 | 238415 | 238419 | 238425 | 238432 | 238441 | 238487 | 238493 | 238496 | 238508 | 238514 | 238516 | 238577 | 238607 | 238629 | 238668 | 238684 | 238688 | 238689 | 238692