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;

        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 PutStructureHint:

        case PhantomNewObject:

        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.

        //

        // - 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.

        if (!performSinking(DontConsiderPhis))

            return false;

        while (performSinking(ConsiderPhis)) { }

        return true;

    }

private:

    enum PhiMode {

        ConsiderPhis,

        DontConsiderPhis

    };

    bool performSinking(PhiMode phiMode)

    {

        m_graph.computeRefCounts();

        m_phiChildren = PhiChildren(m_graph);

        performLivenessAnalysis();

        performOSRAvailabilityAnalysis();

        // Conduct one fixpoint iteration, that involves finding nodes that are candidates for

        // sinking and then sinking them. We proceed roughly as follows:

        //

        // 1) Identify Phis that it would be meaningful to sink.

        // 2) Figure out if the things that are sinkable would be profitable to sink.

        // 3) Sink them.

        m_phiSinkCandidates.clear();

        if (phiMode == ConsiderPhis)

            identifyPhiSinkingCandidates();

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

    {

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

            for (Node* node : *block) {

                if (node->op() != Phi)

                    continue;

                PhiChildren::List& upsilons = phiChildren.upsilonsOf(node);

                if (upsilons.isEmpty())

                    continue;

                if (upsilons[0]->child1()->op() != MaterializeNewObject)

                    continue;

                bool allChildrenAreUniquelyReferenced = true;

                for (Node* upsilonNode : upsilons) {

                    if (upsilonNode->child1()->refCount() != 1) {

                        allChildrenAreUniquelyReferenced = false;

                        break;

                    }

                }

                if (!allChildrenAreUniquelyReferenced)

                    continue;

                bool allChildrenAreSameType = true;

                for (unsigned i = upsilons.size(); i-- > 1;) {

                    if (upsilons[i]->child1()->op() != upsilons[0]->child1()->op()) {

                        allChildrenAreSameType = false;

                        break;

                    }

                }

                if (!allChildrenAreSameType)

                    continue;

                // This could be a pessimisation if the various materializations are too

                // different from one another. We use a simple heuristic here: all of the

                // materializations must share at least half of their fields with the first

                // one.

                bool allAreSimilarEnough = true;

                for (unsigned i = upsilons.size(); i-- > 1;) {

                    float score =

                        upsilons[i]->child1()->objectMaterializationData().similarityScore(

                            upsilons[0]->child1()->objectMaterializationData());

                    if (score < 0.5) {

                        allAreSimilarEnough = false;

                        break;

                    }

                }

                if (!allAreSimilarEnough)

                    continue;

                m_phiSinkCandidates.append(node);

            }

        }

    }

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

    {

        // Lower those operations on phantom allocations that write to properties of those

        // objects. It turns out that this is the only thing we can lower right now, and it's also

        // very useful to lower these things here. We can't yet lower operations like GetByOffset

        // because for those we would need to have done the SSA calculation. SSA calculation

        // depends on us doing the lowering, to reveal the SSA nodes for things like the structure

        // in a PutStructure. We also don't lower the allocations themselves, because their

        // original form still contains some useful information. It turns out that basically this

        // lowers all of the writing operations.

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

            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {

                Node* node = block->at(nodeIndex);

                switch (node->op()) {

                case PutByOffset: {

                    node->convertToPutByOffsetHint();

                    break;

                }

                case PutStructure: {

                    Node* structure = m_insertionSet.insertNode(

                        nodeIndex, SpecNone, PhantomStructure, node->origin,

                        OpInfo(node->transition()->next));

                    node->convertToPutStructureHint(structure);

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

                promoteIncludingMaterializations(

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

        }

        // Fix up 

        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 all of the Defs. This includes:

        //

        // - Defs for the sunken fields at the point of creation. We create Bottom values when

        //   necessary. The point is to always have *some* value for each field that could ever

        //   be associated with an object.

        //

        // - Upsilons and Phis for the constituent fields of a Phi over materializations that we

        //   decided to sink.

        //

        // - Defs for the actual stores to fields that occur in the program.

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

            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {

                Node* node = block->at(nodeIndex);

                if (node->op() == Upsilon) {

                    if (!m_sinkCandidates.contains(node->phi()))

                        continue;

                    continue;

                }

            }

            m_insertionSet.execute(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 Phi:

            if (m_phiSinkCandidates.contains(node))

                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;

        }

    }

    NodeType allocationType(Node* escapee)

    {

        if (escapee->op() == Phi)

            return m_phiChildren.upsilonsOf(escapee)->child1().node()->op();

        return esapee->op();

    }

    Node* createMaterialize(Node* escapee, const NodeOrigin whereOrigin)

    {

        switch (allocationType(escapee)) {

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

        Node* node, const WriteFunctor& write, const ReadFunctor& read)

    {

        if (node->op() == Upsilon) {

            if (!m_sinkCandidates.contains(node->phi()))

                return;

            promoteMaterialization(node->child1().node(), node->phi(), write);

            return;

        }

        promote(node, write, read);

    }

    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 PutByOffset:

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

                unsigned identifierNumber =

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

                AbstractHeap heap(NamedProperties, identifierNumber);

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

            }

            break;

        default:

            break;

        }

    }

    template<typename WriteFunctor>

    void promoteMaterialization(Node* node, Node* phi, const WriteFunctor& write)

    {

        ASSERT(node->op() == MaterializeNewObject);

        write(HeapLocation(StructureLoc, JSCell_structureID, phi), m_graph.varArgChild(node, 0));

        for (unsigned i = 0; i < node->objectMaterializationData().m_properties.size(); ++i) {

            Edge edge = m_graph.varArgChild(node, i + 1);

            AbstractHeap heap(NamedProperties, value.m_identifierNumber);

            write(HeapLocation(NamedPropertyLoc, heap, phi), edge);

        }

    }

    PhiChildren m_phiChildren;

    HashSet<Node*> m_phiSinkCandidates;

    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