typedef Vector<Node*, 8> BlockNodeList;

    BlockNodeList::iterator begin() { return m_nodes.begin(); }

    BlockNodeList::iterator end() { return m_nodes.end(); }

    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);

    }

    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);

            });

    }

    Bag<ObjectMaterializationData> m_objectMaterializationData;

    case StructureLoc:

        out.print("StructureLoc");

        return;

    StructureLoc,

/*

 * 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, LocalOSRAvailabilityCalculactor& availability,

    Node* originalNode, Node* newNode)

{

    for (unsigned i = availability.m_availability.size(); i--;) {

        int operand = availability.m_availability.operandForIndex(i);

        if (availability[i].hasNode() && availability[i].node() == originalNode) {

            insertionSet.insertNode(

                nodeIndex, SpecNone, MovHint, NodeOrigin(), OpInfo(operand),

                newNode->defaultEdge());

        }

    }

}

} } // namespace JSC::DFG

#endif // ENABLE(DFG_JIT)

/*

 * 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 "DFGOSRAvailabilityAnalysisPhase.h"

namespace JSC { namespace DFG {

void insertOSRHintsForUpdate(

    InsertionSet&, unsigned nodeIndex, LocalOSRAvailabilityCalculactor&,

    Node* originalNode, Node* newNode);

} } // namespace JSC::DFG

#endif // ENABLE(DFG_JIT)

#endif // DFGInsertOSRHintsForUpdate_h

#include "DFGObjectMaterializationData.h"

    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);

    }

        case PutByOffsetHint:

        case PutStructureHint:

        case PhantomStructure:

    bool hasObjectMaterializationData()

    {

        return op() == MaterializeNewObject;

    }

    ObjectMaterializationData& objectMaterializationData()

    {

        return *reinterpret_cast<ObjectMaterializationData*>(m_opInfo);

    }

    /* Support for allocation sinking. */\

    macro(PhantomNewObject, NodeResultJS) \

    macro(PhantomStructure, NodeResultJS) \

    macro(PutByOffsetHint, NodeMustGenerate) \

    macro(CheckStructureImmediate, NodeMustGenerate) \

    macro(PutStructureHint, NodeMustGenerate) \

    macro(MaterializeNewObject, NodeResultJS | NodeHasVarArgs) \

    \

void LocalOSRAvailabilityCalculator::endBlock(BasicBlock* block)

{

    m_availability = block->ssa->availabilityAtTail;

}

    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.

/*

 * 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_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(DontConsiderPhis))

            return false;

        while (performSinking(ConsiderPhis)) { }

        return true;

    }

private:

    bool performSinking(PhiMode phiMode)

    {

        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();

        lowerOperationsOnPhantomAllocations();

        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);

            }

        }

        // A node should be materialized if it is a sinking candidate, and we haven't removed it

        // from the sink candidates set yet - since that means that it may not have been

        // materialized yet.

        // FIXME: oddly, anytime that we would have a basic block where something is "maybe

        // materialized", we would make it always materialized by having the not-materializing

    }

    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()

    {

        SSACalculator ssaCalculator(m_graph);

        HashMap<Node*, SSACalculator::Variable*> nodeToVariable;

        Vector<Node*> indexToNode;

        for (Node* node : m_sinkCandidates) {

            SSACalculator::Variable* variable = 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))

                    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;

                        ssaCalculator.newDef(

                            nodeToVariable.get(edge.node()), block, materialize);

                    });

            }

        }

        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 = ssaCalculator.reachingDefAtHead(block, variable);

                if (!def)

                    continue;

                mapping.add(indexToNode[variable->index()], def->value());

            }

            availabilityCalculator.beginBlock(block);

            for (SSACalculator::Def* phiDef : 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 : 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<HeapLocation> locations;

        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {

            for (Node* node : *block) {

                promote(

                    node,

                    [&] (HeapLocation location, Edge) {

                        locations.add(location);

                    },

                    [&] (HeapLocation location) {

                        locations.add(location);

                    });

            }

        }

        // Figure out which locations belong to which allocations.

        HashMap<Node*, Vector<HeapLocation>> locationsForAllocation;

        for (HeapLocation location : locations) {

            auto result = locationsForAllocation.add(location.base(), Vector<HeapLocation>());

            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 (HeapLocation location : locationsForAllocation.get(node)) {

                    switch (location.kind()) {

                    case StructureLoc:

                        ASSERT(location.heap() == AbstractHeap(JSCell_structureID));

                        m_insertionSet.insertNode(

                            nodeIndex + 1, SpecNone, PutStructureHint, node->origin,

                            Edge(node, KnownCellUse), bottom);

                        break;

                    case NamedPropertyLoc:

                        ASSERT(location.heap().kind() == NamedProperties);

                        m_insertionSet.insertNode(

                            nodeIndex + 1, SpecNone, PutByOffsetHint, node->origin,

                            OpInfo(location.heap().payload().value()),

                            Edge(node, KnownCellUse), bottom);

                        break;

                    default:

                        DFG_CRASH(m_graph, node, "Bad heap location kind");

                    }

                }

            }

            m_insertionSet.execute(block);

        }

        SSACalculator ssaCalculator(m_graph);

        // Collect the set of "variables" that we will be sinking.

        HashMap<HeapLocation, SSACalculator::Variable*> locationToVariable;

        Vector<HeapLocation> indexToLocation;

        for (HeapLocation location : locations) {

            SSACalculator::Variable* variable = 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,

                    [&] (HeapLocation location, Edge value) {

                        SSACalculator::Variable* variable = locationToVariable.get(location);

                        ssaCalculator.newDef(variable, block, value.node());

                    });

            }

        }

        // OMG run the SSA calculator to create Phis!

        ssaCalculator.computePhis(

            [&] (SSACalculator::Variable* variable, BasicBlock* block) {

            });

    }

    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()));

        default:

            DFG_CRASH(m_graph, where, "Bad escapee op");

            return nullpt;

        }

        return result;

    }

    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(HeapLocation(StructureLoc, JSCell_structureID, node->child1()));

            break;

        case GetByOffset:

        case GetGetterSetterByOffset:

            if (m_sinkCandidates.contains(node->child2().node())) {

                unsigned identifierNumber =

                    graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber;

                AbstractHeap heap(NamedProperties, identifierNumber);

                read(HeapLocation(NamedPropertyLoc, heap, node->child2()));

            }

            break;

        case MultiGetByOffset:

            if (m_sinkCandidates.contains(node->child1().node())) {

                AbstractHeap heap(NamedProperties, node->multiGetByOffsetData().identifierNumber);

                read(HeapLocation(NamedPropertyLoc, heap, node->child1()));

            }

            break;

        case PutStructureHint:

            if (m_sinkCandidates.contains(node->child1().node()))

                write(HeapLocation(StructureLoc, JSCell_structureID, node->child1()), node->child2());

            break;

        case PutByOffsetHint:

            if (m_sinkCandidates.contains(node->child1().node())) {

                unsigned identifierNumber = node->identifierNumber();

                AbstractHeap heap(NamedProperties, identifierNumber);

                write(HeapLocation(NamedPropertyLoc, heap, node->child1()), node->child2().node());

            }

            break;

        default:

            break;

        }

    }

    PhiChildren m_phiChildren;

    HashSet<Node*> m_sinkCandidates;

    HashMap<std::pair<Node*, Node*>, Node*> m_edgeToMaterializationPoint;

    HashMap<Node*, Node*> m_materializationPointToEscapee;

    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)

/*

 * 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

/*

 * 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

/*

 * 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 {

    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

/*

 * 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)

/*

 * 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