Attachment #238219 for bug #136330

View Details Raw Unified Return to Bug 136330

| Differences between

and this patch

Lines 46-51 class Graph; Source/JavaScriptCore/dfg/DFGBasicBlock.h_sec1
- Source/JavaScriptCore/dfg/DFGBasicBlock.h -1 / +75 lines
46	class InsertionSet;	46	class InsertionSet;
47		47
48	typedef Vector<BasicBlock*, 2> PredecessorList;	48	typedef Vector<BasicBlock*, 2> PredecessorList;
		49	typedef Vector<Node*, 8> BlockNodeList;
49		50
50	struct BasicBlock : RefCounted<BasicBlock> {	51	struct BasicBlock : RefCounted<BasicBlock> {
51	BasicBlock(	52	BasicBlock(
Lines 85-90 struct BasicBlock : RefCounted<BasicBloc Source/JavaScriptCore/dfg/DFGBasicBlock.h_sec2
85	bool isInPhis(Node* node) const;	86	bool isInPhis(Node* node) const;
86	bool isInBlock(Node* myNode) const;	87	bool isInBlock(Node* myNode) const;
87		88
		89	BlockNodeList::iterator begin() { return m_nodes.begin(); }
		90	BlockNodeList::iterator end() { return m_nodes.end(); }
		91
88	unsigned numSuccessors() { return last()->numSuccessors(); }	92	unsigned numSuccessors() { return last()->numSuccessors(); }
89		93
90	BasicBlock*& successor(unsigned index)	94	BasicBlock*& successor(unsigned index)
Lines 96-101 struct BasicBlock : RefCounted<BasicBloc Source/JavaScriptCore/dfg/DFGBasicBlock.h_sec3
96	return last()->successorForCondition(condition);	100	return last()->successorForCondition(condition);
97	}	101	}
98		102
		103	class SuccessorsIterable {
		104	public:
		105	SuccessorsIterable()
		106	: m_block(nullptr)
		107	{
		108	}
		109
		110	SuccessorsIterable(BasicBlock* block)
		111	: m_block(block)
		112	{
		113	}
		114
		115	class iterator {
		116	public:
		117	iterator()
		118	: m_block(nullptr)
		119	, m_index(UINT_MAX)
		120	{
		121	}
		122
		123	iterator(BasicBlock* block, unsigned index)
		124	: m_block(block)
		125	, m_index(index)
		126	{
		127	}
		128
		129	BasicBlock* operator*()
		130	{
		131	return m_block->successor(index);
		132	}
		133
		134	iterator& operator++()
		135	{
		136	m_index++;
		137	return *this;
		138	}
		139
		140	bool operator==(const iterator& other) const
		141	{
		142	return m_index == other.m_index;
		143	}
		144
		145	bool operator!=(const iterator& other) const
		146	{
		147	return !(*this == other);
		148	}
		149	private:
		150	BasicBlock* m_block;
		151	unsigned m_index;
		152	};
		153
		154	iterator begin()
		155	{
		156	return iterator(m_block, 0);
		157	}
		158
		159	iterator end()
		160	{
		161	return iterator(m_block, m_block->numSuccessors());
		162	}
		163
		164	private:
		165	BasicBlock* m_block;
		166	};
167
168	SuccessorsIterable successors()
169	{
170	return SuccessorsIterable(this);
171	}
172
99	void removePredecessor(BasicBlock* block);	173	void removePredecessor(BasicBlock* block);
100	void replacePredecessor(BasicBlock* from, BasicBlock* to);	174	void replacePredecessor(BasicBlock* from, BasicBlock* to);
101		175
Lines 183-189 struct BasicBlock : RefCounted<BasicBloc Source/JavaScriptCore/dfg/DFGBasicBlock.h_sec4
183		257
184	private:	258	private:
185	friend class InsertionSet;	259	friend class InsertionSet;
186	Vector<Node*, 8> m_nodes;	260	BlockNodeList m_nodes;
187	};	261	};
188		262
189	typedef Vector<BasicBlock*, 5> BlockList;	263	typedef Vector<BasicBlock*, 5> BlockList;



    BlockList blocksInPreOrder();
    BlockList blocksInPostOrder();
    
    class NaturalBlockIterable {
    public:
        NaturalBlockIterable()
            : m_graph(nullptr)
        {
        }
        
        NaturalBlockIterable(Graph& graph)
            : m_graph(&graph)
        {
        }
        
        class iterator {
        public:
            iterator()
                : m_graph(nullptr)
                , m_index(0)
            {
            }
            
            iterator(Graph& graph, BlockIndex index)
                : m_graph(&graph)
                , m_index(findNext(index))
            {
            }
            
            BasicBlock *operator*()
            {
                return m_graph->block(index);
            }
            
            iterator& operator++()
            {
                m_index = findNext(m_index);
                return *this;
            }
            
            bool operator==(const iterator& other) const
            {
                return m_index == other.m_index;
            }
            
            bool operator!=(const iterator& other) const
            {
                return !(*this == other);
            }
            
        private:
            BlockIndex findNext(BlockIndex index)
            {
                while (index < m_graph->numBlocks() && !m_graph->block(index))
                    index++;
                return index;
            }
            
            Graph* m_graph;
            BlockIndex m_index;
        };
        
        iterator begin()
        {
            return iterator(*m_graph, 0);
        }
        
        iterator end()
        {
            return iterator(*m_graph, m_graph->numBlocks());
        }
        
    private:
        Graph* m_graph;
    };
    
    NaturalBlockIterable blocksInNaturalOrder()
    {
        return NaturalBlockIterable(*this);
    }
    
    template<typename ChildFunctor>
    void doToChildrenWithNode(Node* node, const ChildFunctor& functor)
    {
        DFG_NODE_DO_TO_CHILDREN(node, functor);
    }
    
    template<typename ChildFunctor>
    void doToChildren(Node* node, const ChildFunctor& functor)
    {
        doToChildrenWithNode(
            node,
            [&functor] (Node*, Edge edge) {
                functor(edge);
            });
    }
    
    Profiler::Compilation* compilation() { return m_plan.compilation.get(); }
    
    DesiredIdentifiers& identifiers() { return m_plan.identifiers; }

    Bag<SwitchData> m_switchData;
    Bag<MultiGetByOffsetData> m_multiGetByOffsetData;
    Bag<MultiPutByOffsetData> m_multiPutByOffsetData;
    Bag<ObjectMaterializationData> m_objectMaterializationData;
    Vector<InlineVariableData, 4> m_inlineVariableData;
    HashMap<CodeBlock*, std::unique_ptr<FullBytecodeLiveness>> m_bytecodeLiveness;
    bool m_hasArguments;



/*
 * 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 "DFGNodeFlags.h"
#include "DFGNodeOrigin.h"
#include "DFGNodeType.h"
#include "DFGObjectMaterializationData.h"
#include "DFGTransition.h"
#include "DFGUseKind.h"
#include "DFGVariableAccessData.h"

    {
        switch (op()) {
        case PutStructure:
        case PutStructureHint:
        case AllocatePropertyStorage:
        case ReallocatePropertyStorage:
            return true;

        case ArrayifyToStructure:
        case NewObject:
        case NewStringObject:
        case PhantomNewObject:
            return true;
        default:
            return false;

    
    bool hasStorageAccessData()
    {
        switch (op()) {
        case GetByOffset:
        case PutByOffset:
        case GetGetterSetterByOffset:
        case PutByOffsetHint:
            return true;
        default:
            return false;
        }
    }
    
    unsigned storageAccessDataIndex()

        return *reinterpret_cast<MultiPutByOffsetData*>(m_opInfo);
    }
    
    bool hasObjectMaterializationData()
    {
        return op() == MaterializeNewObject;
    }
    
    ObjectMaterializationData& objectMaterializationData()
    {
        return *reinterpret_cast<ObjectMaterializationData*>(m_opInfo);
    }
    
    bool hasFunctionDeclIndex()
    {
        return op() == NewFunction

Lines 228-233 namespace JSC { namespace DFG { Source/JavaScriptCore/dfg/DFGNodeType.h_sec1
- Source/JavaScriptCore/dfg/DFGNodeType.h +7 lines
228	macro(NewTypedArray, NodeResultJS \| NodeClobbersWorld \| NodeMustGenerate) \	228	macro(NewTypedArray, NodeResultJS \| NodeClobbersWorld \| NodeMustGenerate) \
229	macro(NewRegexp, NodeResultJS) \	229	macro(NewRegexp, NodeResultJS) \
230	\	230	\
		231	/* Support for allocation sinking. */\
		232	macro(PhantomNewObject, NodeResultJS) \
		233	macro(PhantomStructure, NodeResultJS) \
		234	macro(PutByOffsetHint, NodeMustGenerate) \
		235	macro(PutStructureHint, NodeMustGenerate) \
		236	macro(MaterializeNewObject, NodeResultJS \| NodeHasVarArgs) \
		237	\
231	/* Nodes for misc operations. */\	238	/* Nodes for misc operations. */\
232	macro(Breakpoint, NodeMustGenerate) \	239	macro(Breakpoint, NodeMustGenerate) \
233	macro(ProfileWillCall, NodeMustGenerate) \	240	macro(ProfileWillCall, NodeMustGenerate) \

Lines 127-132 void LocalOSRAvailabilityCalculator::beg Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp_sec1
- Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp +5 lines
127	m_availability = block->ssa->availabilityAtHead;	127	m_availability = block->ssa->availabilityAtHead;
128	}	128	}
129		129
		130	void LocalOSRAvailabilityCalculator::endBlock(BasicBlock* block)
		131	{
		132	m_availability = block->ssa->availabilityAtTail;
		133	}
		134
130	void LocalOSRAvailabilityCalculator::executeNode(Node* node)	135	void LocalOSRAvailabilityCalculator::executeNode(Node* node)
131	{	136	{
132	switch (node->op()) {	137	switch (node->op()) {

Lines 49-54 public: Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.h_sec1
- Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.h +1 lines
49	~LocalOSRAvailabilityCalculator();	49	~LocalOSRAvailabilityCalculator();
50		50
51	void beginBlock(BasicBlock*);	51	void beginBlock(BasicBlock*);
		52	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.
52	void executeNode(Node*);	53	void executeNode(Node*);
53		54
54	Operands<Availability> m_availability;	55	Operands<Availability> m_availability;



/*
 * 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_changed = false;
        
        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();

        // At this point we are committed to sinking the sinking candidates.
        determineMaterializationPoints();
        placeMaterializationPoints();
        promoteSunkenFields();
        
        return m_changed;
    }
    
    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.
        
        m_materializationPoints.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) {
                            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.
        LocalOSRAvailabilityCalculator availabilityCalculator;
        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
            HashSet<Node*> materialized = materializedAtHead[block];
            availabilityCalculator.beginBlock(block);
            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
                Node* node = block->at(nodeIndex);
                
                handleNode(
                    node,
                    doNothing,
                    [&] (Node* escapee) {
                        if (!materialized.add(escapee))
                            return;
                        
                        Node* materialize = m_insertionSet.insertNode(
                            nodeIndex, escapee->prediction(), MaterializeNewObject,
                            NodeOrigin(
                                escapee->origin.semantic,
                                node->origin.forExit),
                            OpInfo(m_graph.m_objectMaterializationData.add()));
                        
                        insertOSRHintsForUpdate(
                            m_insertionSet, nodeIndex, availabilityCalculator,
                            escapee, materialize);
                        
                        m_materializationPoints.add(std::make_pair(node, escapee), materialize);
                    });
                
                availabilityCalculator.executeNode(node);
            }
            m_insertionSet.execute(block);
        }
    }
    
    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);
            
            node->setOpAndDefaultFlags(PhantomNewObject);
        }
        
        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_materializationPoints.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 (Node* node : *block) {
                
            }
            
            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:
            break;
            
        case PutByOffset:
            escape(node->child3().node());
            break;
            
        case MultiPutByOffset:
            escape(node->child3().node());
            break;

        default:
            m_graph.doToChildren(
                node,
                [&escape] (Edge edge) {
                    escape(edge.node());
                });
            break;
        }
    }
    
    PhiChildren m_phiChildren;
    HashSet<Node*> m_phiSinkCandidates;
    HashSet<Node*> m_sinkCandidates;
    HashMap<std::pair<Node*, Node*>, Node*> m_materializationPoints;
    InsertionSet m_insertionSet;
    bool m_changed;
};
    
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


Return to Bug 136330

Lines 681-686 public: Source/JavaScriptCore/dfg/DFGGraph.h_sec1
- Source/JavaScriptCore/dfg/DFGGraph.h +95 lines
681	BlockList blocksInPreOrder();	681	BlockList blocksInPreOrder();
682	BlockList blocksInPostOrder();	682	BlockList blocksInPostOrder();
683		683
		684	class NaturalBlockIterable {
		685	public:
		686	NaturalBlockIterable()
		687	: m_graph(nullptr)
		688	{
		689	}
		690
		691	NaturalBlockIterable(Graph& graph)
		692	: m_graph(&graph)
		693	{
		694	}
		695
		696	class iterator {
		697	public:
		698	iterator()
		699	: m_graph(nullptr)
		700	, m_index(0)
		701	{
		702	}
		703
		704	iterator(Graph& graph, BlockIndex index)
		705	: m_graph(&graph)
		706	, m_index(findNext(index))
		707	{
		708	}
		709
		710	BasicBlock operator()
		711	{
		712	return m_graph->block(index);
		713	}
		714
		715	iterator& operator++()
		716	{
		717	m_index = findNext(m_index);
		718	return *this;
		719	}
		720
		721	bool operator==(const iterator& other) const
		722	{
		723	return m_index == other.m_index;
		724	}
		725
		726	bool operator!=(const iterator& other) const
		727	{
		728	return !(*this == other);
		729	}
		730
		731	private:
		732	BlockIndex findNext(BlockIndex index)
		733	{
		734	while (index < m_graph->numBlocks() && !m_graph->block(index))
		735	index++;
		736	return index;
		737	}
		738
		739	Graph* m_graph;
		740	BlockIndex m_index;
		741	};
		742
		743	iterator begin()
		744	{
		745	return iterator(*m_graph, 0);
		746	}
		747
748	iterator end()
749	{
750	return iterator(*m_graph, m_graph->numBlocks());
751	}
752
753	private:
754	Graph* m_graph;
755	};
756
757	NaturalBlockIterable blocksInNaturalOrder()
758	{
759	return NaturalBlockIterable(*this);
760	}
761
762	template<typename ChildFunctor>
763	void doToChildrenWithNode(Node* node, const ChildFunctor& functor)
764	{
765	DFG_NODE_DO_TO_CHILDREN(node, functor);
766	}
767
768	template<typename ChildFunctor>
769	void doToChildren(Node* node, const ChildFunctor& functor)
770	{
771	doToChildrenWithNode(
772	node,
773	[&functor] (Node*, Edge edge) {
774	functor(edge);
775	});
776	}
777
684	Profiler::Compilation* compilation() { return m_plan.compilation.get(); }	778	Profiler::Compilation* compilation() { return m_plan.compilation.get(); }
685		779
686	DesiredIdentifiers& identifiers() { return m_plan.identifiers; }	780	DesiredIdentifiers& identifiers() { return m_plan.identifiers; }
Lines 741-746 public: Source/JavaScriptCore/dfg/DFGGraph.h_sec2
741	Bag<SwitchData> m_switchData;	835	Bag<SwitchData> m_switchData;
742	Bag<MultiGetByOffsetData> m_multiGetByOffsetData;	836	Bag<MultiGetByOffsetData> m_multiGetByOffsetData;
743	Bag<MultiPutByOffsetData> m_multiPutByOffsetData;	837	Bag<MultiPutByOffsetData> m_multiPutByOffsetData;
		838	Bag<ObjectMaterializationData> m_objectMaterializationData;
744	Vector<InlineVariableData, 4> m_inlineVariableData;	839	Vector<InlineVariableData, 4> m_inlineVariableData;
745	HashMap<CodeBlock*, std::unique_ptr<FullBytecodeLiveness>> m_bytecodeLiveness;	840	HashMap<CodeBlock*, std::unique_ptr<FullBytecodeLiveness>> m_bytecodeLiveness;
746	bool m_hasArguments;	841	bool m_hasArguments;

Lines 38-43 Source/JavaScriptCore/dfg/DFGNode.h_sec1
- Source/JavaScriptCore/dfg/DFGNode.h -1 / +22 lines
38	#include "DFGNodeFlags.h"	38	#include "DFGNodeFlags.h"
39	#include "DFGNodeOrigin.h"	39	#include "DFGNodeOrigin.h"
40	#include "DFGNodeType.h"	40	#include "DFGNodeType.h"
		41	#include "DFGObjectMaterializationData.h"
41	#include "DFGTransition.h"	42	#include "DFGTransition.h"
42	#include "DFGUseKind.h"	43	#include "DFGUseKind.h"
43	#include "DFGVariableAccessData.h"	44	#include "DFGVariableAccessData.h"
Lines 1100-1105 struct Node { Source/JavaScriptCore/dfg/DFGNode.h_sec2
1100	{	1101	{
1101	switch (op()) {	1102	switch (op()) {
1102	case PutStructure:	1103	case PutStructure:
		1104	case PutStructureHint:
1103	case AllocatePropertyStorage:	1105	case AllocatePropertyStorage:
1104	case ReallocatePropertyStorage:	1106	case ReallocatePropertyStorage:
1105	return true;	1107	return true;
Lines 1136-1141 struct Node { Source/JavaScriptCore/dfg/DFGNode.h_sec3
1136	case ArrayifyToStructure:	1138	case ArrayifyToStructure:
1137	case NewObject:	1139	case NewObject:
1138	case NewStringObject:	1140	case NewStringObject:
		1141	case PhantomNewObject:
1139	return true;	1142	return true;
1140	default:	1143	default:
1141	return false;	1144	return false;
Lines 1150-1156 struct Node { Source/JavaScriptCore/dfg/DFGNode.h_sec4
1150		1153
1151	bool hasStorageAccessData()	1154	bool hasStorageAccessData()
1152	{	1155	{
1153	return op() == GetByOffset \|\| op() == GetGetterSetterByOffset \|\| op() == PutByOffset;	1156	switch (op()) {
		1157	case GetByOffset:
		1158	case PutByOffset:
		1159	case GetGetterSetterByOffset:
		1160	case PutByOffsetHint:
		1161	return true;
		1162	default:
		1163	return false;
		1164	}
1154	}	1165	}
1155		1166
1156	unsigned storageAccessDataIndex()	1167	unsigned storageAccessDataIndex()
Lines 1179-1184 struct Node { Source/JavaScriptCore/dfg/DFGNode.h_sec5
1179	return reinterpret_cast<MultiPutByOffsetData>(m_opInfo);	1190	return reinterpret_cast<MultiPutByOffsetData>(m_opInfo);
1180	}	1191	}
1181		1192
		1193	bool hasObjectMaterializationData()
		1194	{
		1195	return op() == MaterializeNewObject;
		1196	}
		1197
		1198	ObjectMaterializationData& objectMaterializationData()
		1199	{
		1200	return reinterpret_cast<ObjectMaterializationData>(m_opInfo);
		1201	}
		1202
1182	bool hasFunctionDeclIndex()	1203	bool hasFunctionDeclIndex()
1183	{	1204	{
1184	return op() == NewFunction	1205	return op() == NewFunction

Line 0 Source/JavaScriptCore/dfg/DFGInsertOSRHintsForUpdate.cpp_sec1
- Source/JavaScriptCore/dfg/DFGInsertOSRHintsForUpdate.cpp +51 lines
	1	/*
	2	* Copyright (C) 2014 Apple Inc. All rights reserved.
	3	*
	4	* Redistribution and use in source and binary forms, with or without
	5	* modification, are permitted provided that the following conditions
	6	* are met:
	7	* 1. Redistributions of source code must retain the above copyright
	8	* notice, this list of conditions and the following disclaimer.
	9	* 2. Redistributions in binary form must reproduce the above copyright
	10	* notice, this list of conditions and the following disclaimer in the
	11	* documentation and/or other materials provided with the distribution.
	12	*
	13	* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
	14	* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	15	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
	16	* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
	17	* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
	18	* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
	19	* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
	20	* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
	21	* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	22	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
	23	* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	24	*/
	25
	26	#include "config.h"
	27	#include "DFGInsertOSRHintsForUpdate.h"
	28
	29	#if ENABLE(DFG_JIT)
	30
	31	namespace JSC { namespace DFG {
	32
	33	void insertOSRHintsForUpdate(
	34	InsertionSet& insertionSet, unsigned nodeIndex, LocalOSRAvailabilityCalculactor& availability,
	35	Node* originalNode, Node* newNode)
	36	{
	37	for (unsigned i = availability.m_availability.size(); i--;) {
	38	int operand = availability.m_availability.operandForIndex(i);
	39
	40	if (availability[i].hasNode() && availability[i].node() == originalNode) {
	41	insertionSet.insertNode(
	42	nodeIndex, SpecNone, MovHint, NodeOrigin(), OpInfo(operand),
	43	newNode->defaultEdge());
	44	}
	45	}
	46	}
	47
	48	} } // namespace JSC::DFG
	49
	50	#endif // ENABLE(DFG_JIT)
	51

Line 0 Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp_sec1
- Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp +456 lines
		1	/*
		2	* Copyright (C) 2014 Apple Inc. All rights reserved.
		3	*
		4	* Redistribution and use in source and binary forms, with or without
		5	* modification, are permitted provided that the following conditions
		6	* are met:
		7	* 1. Redistributions of source code must retain the above copyright
		8	* notice, this list of conditions and the following disclaimer.
		9	* 2. Redistributions in binary form must reproduce the above copyright
		10	* notice, this list of conditions and the following disclaimer in the
		11	* documentation and/or other materials provided with the distribution.
		12	*
		13	* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
		14	* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
		15	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
		16	* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
		17	* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
		18	* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
		19	* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
		20	* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
		21	* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
		22	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
		23	* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
		24	*/
		25
		26	#include "config.h"
		27	#include "DFGObjectAllocationSinkingPhase.h"
		28
		29	#if ENABLE(DFG_JIT)
		30
		31	#include "DFGAbstractHeap.h"
		32	#include "DFGClobberize.h"
		33	#include "DFGGraph.h"
		34	#include "DFGInsertionSet.h"
		35	#include "DFGPhase.h"
		36	#include "JSCInlines.h"
		37
		38	namespace JSC { namespace DFG {
		39
		40	class ObjectAllocationSinkingPhase : public Phase {
		41	public:
		42	ObjectAllocationSinkingPhase(Graph& graph)
		43	: Phase(graph, "object allocation sinking")
		44	, m_insertionSet(graph)
		45	{
		46	}
		47
		48	bool run()
		49	{
		50	ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
		51
		52	m_changed = false;
		53
		54	// Logically we wish to consider every NewObject and sink it. However it's definitely not
		55	// profitable to sink a NewObject that will always escape. So, first we do a very simple
		56	// forward flow analysis that determines the set of NewObject nodes that have any chance
		57	// of benefiting from object allocation sinking. Then we fixpoint the following rules:
		58	//
		59	// - For each NewObject, we turn the original NewObject into a PhantomNewObject and then
		60	// we insert MaterializeNewObject just before each escaping site. Note that Upsilons
		61	// constitute escaping sites. Then we use forward flow to eliminate unnecessary cases of
		62	// MaterializeNewObject. We use the SSACalculator to insert these materializations. If a
		63	// Phi is ever created that has the PhantomNewObject as one of its kids, then we insert
		64	// a MaterializeNewObject in front of it; this way we never have a Phi that is confused
65	// about whether or not it has the real object. We then turn each PutByOffset over a
66	// PhantomNewObject into a PutByOffsetHint.
67	//
68	// - We perform the same optimization for MaterializeNewObject. This allows us to cover
69	// cases where we had MaterializeNewObject flowing into a PutByOffsetHint.
70	//
71	// - If all of the Upsilons of a Phi have a MaterializeNewObject that isn't used by anyone
72	// else, then replace the Phi with the MaterializeNewObject.
73
74	if (!performSinking(DontConsiderPhis))
75	return false;
76
77	while (performSinking(ConsiderPhis)) { }
78
79	return true;
80	}
81
82	private:
83	enum PhiMode {
84	ConsiderPhis,
85	DontConsiderPhis
86	};
87
88	bool performSinking(PhiMode phiMode)
89	{
90	m_changed = false;
91
92	m_graph.computeRefCounts();
93	m_phiChildren = PhiChildren(m_graph);
94
95	performLivenessAnalysis();
96	performOSRAvailabilityAnalysis();
97
98	// Conduct one fixpoint iteration, that involves finding nodes that are candidates for
99	// sinking and then sinking them. We proceed roughly as follows:
100	//
101	// 1) Identify Phis that it would be meaningful to sink.
102	// 2) Figure out if the things that are sinkable would be profitable to sink.
103	// 3) Sink them.
104
105	m_phiSinkCandidates.clear();
106	if (phiMode == ConsiderPhis)
107	identifyPhiSinkingCandidates();
108
109	// We want to only do sinking for those things that would benefit. We use a rough
110	// heuristic: if it's possible for an allocation to make it to a return without escaping,
111	// then we assume that it's worth sinking. It's a simple forward flow problem.
112	//
113	// It just so happens that this forward flow problem also tells us where we would
114	// materialize those nodes that we choose to sink.
115	pruneSinkingCandidates();
116
117	// At this point we are committed to sinking the sinking candidates.
118	determineMaterializationPoints();
119	placeMaterializationPoints();
120	promoteSunkenFields();
121
122	return m_changed;
123	}
124
125	void identifyPhiSinkingCandidates()
126	{
127	for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
128	for (Node* node : *block) {
129	if (node->op() != Phi)
130	continue;
131
132	PhiChildren::List& upsilons = phiChildren.upsilonsOf(node);
133	if (upsilons.isEmpty())
134	continue;
135
136	if (upsilons[0]->child1()->op() != MaterializeNewObject)
137	continue;
138
139	bool allChildrenAreUniquelyReferenced = true;
140	for (Node* upsilonNode : upsilons) {
141	if (upsilonNode->child1()->refCount() != 1) {
142	allChildrenAreUniquelyReferenced = false;
143	break;
144	}
145	}
146	if (!allChildrenAreUniquelyReferenced)
147	continue;
148
149	bool allChildrenAreSameType = true;
150	for (unsigned i = upsilons.size(); i-- > 1;) {
151	if (upsilons[i]->child1()->op() != upsilons[0]->child1()->op()) {
152	allChildrenAreSameType = false;
153	break;
154	}
155	}
156	if (!allChildrenAreSameType)
157	continue;
158
159	// This could be a pessimisation if the various materializations are too
160	// different from one another. We use a simple heuristic here: all of the
161	// materializations must share at least half of their fields with the first
162	// one.
163	bool allAreSimilarEnough = true;
164	for (unsigned i = upsilons.size(); i-- > 1;) {
165	float score =
166	upsilons[i]->child1()->objectMaterializationData().similarityScore(
167	upsilons[0]->child1()->objectMaterializationData());
168	if (score < 0.5) {
169	allAreSimilarEnough = false;
170	break;
171	}
172	}
173	if (!allAreSimilarEnough)
174	continue;
175
176	m_phiSinkCandidates.append(node);
177	}
178	}
179	}
180
181	void pruneSinkingCandidates()
182	{
183	m_sinkCandidates.clear();
184	BlockMap<HashSet<Node*>> sinkCandidatesAtHead(m_graph);
185	BlockMap<HashSet<Node*>> sinkCandidatesAtTail(m_graph);
186
187	bool changed;
188	do {
189	changed = false;
190	for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
191	HashSet<Node*> sinkCandidates = sinkCandidatesAtHead[block];
192	for (Node* node : *block) {
193	handleNode(
194	node,
195	[&] () {
196	sinkCandidates.add(node);
197	},
198	[&] (Node* escapee) {
199	sinkCandidates.remove(escapee);
200	});
201	}
202	if (sinkCandidatesAtTail[block] == sinkCandidates)
203	continue;
204
205	sinkCandidatesAtTail[block] = sinkCandidates;
206	changed = true;
207
208	for (BasicBlock* successorBlock : block->successors()) {
209	for (Node* sinkCandidate : sinkCandidates) {
210	if (!successorBlock->ssa->liveAtHead.contains(sinkCandidate))
211	continue;
212	sinkCandidatesAtHead[successorBlock].add(sinkCandidate);
213	}
214	}
215	}
216	} while (changed);
217
218	// A node is a sink candidate if it is in the sinkCandidatesAtTail of a block but not in
219	// the liveAtTail of that same block.
220	for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
221	for (Node* sinkCandidate : sinkCandidatesAtTail[block]) {
222	if (!block->ssa->liveAtTail.contains(sinkCandidate))
223	m_sinkCandidates.add(sinkCandidate);
224	}
225	}
226
227	// A node should be materialized if it is a sinking candidate, and we haven't removed it
228	// from the sink candidates set yet - since that means that it may not have been
229	// materialized yet.
230	// FIXME: oddly, anytime that we would have a basic block where something is "maybe
231	// materialized", we would make it always materialized by having the not-materializing
232	}
233
234	void determineMaterializationPoints()
235	{
236	// The premise of this pass is that if there exists a point in the program where some
237	// path from a phantom allocation site to that point causes materialization, then all
238	// paths cause materialization.
239
240	m_materializationPoints.clear();
241
242	BlockMap<HashSet<Node*>> materializedAtHead;
243	BlockMap<HashSet<Node*>> materializedAtTail;
244
245	bool changed;
246	do {
247	changed = false;
248	for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
249	HashSet<Node*> materialized = materializedAtHead[block];
250	for (Node* node : *block) {
251	handleNode(
252	node,
253	doNothing,
254	[&] (Node* escapee) {
255	materialized.add(escapee);
256	});
257	}
258
259	if (materialized == materializedAtTail[block])
260	continue;
261
262	changed = true;
263
264	for (BasicBlock* successorBlock : block->successors()) {
265	for (Node* materializee : materialized) {
266	if (!successorBlock->ssa->liveAtHead.contains(materializee))
267	continue;
268	materializedAtHead[successorBlock].add(materializee);
269	}
270	}
271	}
272	} while (changed);
273
274	// A materialization edge exists at any point where a node escapes but hasn't been
275	// materialized yet.
276	LocalOSRAvailabilityCalculator availabilityCalculator;
277	for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
278	HashSet<Node*> materialized = materializedAtHead[block];
279	availabilityCalculator.beginBlock(block);
280	for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
281	Node* node = block->at(nodeIndex);
282
283	handleNode(
284	node,
285	doNothing,
286	[&] (Node* escapee) {
287	if (!materialized.add(escapee))
288	return;
289
290	Node* materialize = m_insertionSet.insertNode(
291	nodeIndex, escapee->prediction(), MaterializeNewObject,
292	NodeOrigin(
293	escapee->origin.semantic,
294	node->origin.forExit),
295	OpInfo(m_graph.m_objectMaterializationData.add()));
296
297	insertOSRHintsForUpdate(
298	m_insertionSet, nodeIndex, availabilityCalculator,
299	escapee, materialize);
300
301	m_materializationPoints.add(std::make_pair(node, escapee), materialize);
302	});
303
304	availabilityCalculator.executeNode(node);
305	}
306	m_insertionSet.execute(block);
307	}
308	}
309
310	void placeMaterializationPoints()
311	{
312	SSACalculator ssaCalculator(m_graph);
313
314	HashMap<Node, SSACalculator::Variable> nodeToVariable;
315	Vector<Node*> indexToNode;
316
317	for (Node* node : m_sinkCandidates) {
318	SSACalculator::Variable* variable = ssaCalculator.newVariable();
319	nodeToVariable.add(node, variable);
320	ASSERT(indexToNode.size() == variable->index());
321	indexToNode.append(node);
322
323	node->setOpAndDefaultFlags(PhantomNewObject);
324	}
325
326	for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
327	for (Node* node : *block) {
328	if (SSACalculator::Variable* variable = nodeToVariable.get(node))
329	ssaCalculator.newDef(variable, block, node);
330
331	m_graph.doToChildren(
332	node,
333	[&] (Edge edge) {
334	Node* materialize =
335	m_materializationPoints.get(std::make_pair(node, edge.node()));
336	if (!materialize)
337	return;
338
339	ssaCalculator.newDef(
340	nodeToVariable.get(edge.node()), block, materialize);
341	});
342	}
343	}
344
345	ssaCalculator.computePhis(
346	[&] (SSACalculator::Variable* variable, BasicBlock* block) -> Node* {
347	Node* allocation = indexToNode[variable->index()];
348	if (!block->ssa->liveAtHead.contains(allocation))
349	return nullptr;
350
351	Node* phiNode = m_graph.addNode(
352	allocation->prediction(), Phi, NodeOrigin());
353	phiNode->mergeFlags(NodeResultJS);
354	return phiNode;
355	});
356
357	// Place Phis in the right places. Replace all uses of any allocation with the appropriate
358	// materialization. Create the appropriate Upsilon nodes.
359	LocalOSRAvailabilityCalculator availabilityCalculator;
360	for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
361	HashMap<Node, Node> mapping;
362
363	for (Node* candidate : block->ssa->liveAtHead) {
364	SSACalculator::Variable* variable = nodeToVariable.get(candidate);
365	if (!variable)
366	continue;
367
368	Def* def = ssaCalculator.reachingDefAtHead(block, variable);
369	if (!def)
370	continue;
371
372	mapping.add(indexToNode[variable->index()], def->value());
373	}
374
375	availabilityCalculator.beginBlock(block);
376	for (SSACalculator::Def* phiDef : ssaCalculator.phisForBlock(block)) {
377	m_insertionSet.insert(0, phiDef->value());
378
379	Node* originalNode = indexToNode[phiDef->variable()->index()];
380	insertOSRHintsForUpdate(
381	m_insertionSet, 0, availabilityCalculator, originalNode, phiDef->value());
382
383	mapping.add(originalNode, phiDef->value());
384	}
385
386	for (Node* node : *block) {
387
388	}
389
390	m_insertionSet.execute(block);
391	}
392	}
393
394	template<typename... Args>
395	static void doNothing(Args...) { }
396
397	template<typename SinkCandidateFunctor, typename EscapeFunctor>
398	void handleNode(
399	Node* node,
400	const SinkCandidateFunctor& sinkCandidate,
401	const EscapeFunctor& escape)
402	{
403	switch (node->op()) {
404	case NewObject:
405	case MaterializeNewObject:
406	sinkCandidate();
407	break;
408
409	case Phi:
410	if (m_phiSinkCandidates.contains(node))
411	sinkCandidate();
412	break;
413
414	case CheckStructure:
415	case GetByOffset:
416	case MultiGetByOffset:
417	case PutStructure:
418	case GetGetterSetterByOffset:
419	break;
420
421	case PutByOffset:
422	escape(node->child3().node());
423	break;
424
425	case MultiPutByOffset:
426	escape(node->child3().node());
427	break;
428
429	default:
430	m_graph.doToChildren(
431	node,
432	[&escape] (Edge edge) {
433	escape(edge.node());
434	});
435	break;
436	}
437	}
438
439	PhiChildren m_phiChildren;
440	HashSet<Node*> m_phiSinkCandidates;
441	HashSet<Node*> m_sinkCandidates;
442	HashMap<std::pair<Node, Node>, Node*> m_materializationPoints;
443	InsertionSet m_insertionSet;
444	bool m_changed;
445	};
446
447	bool performObjectAllocationSinking(Graph& graph)
448	{
449	SamplingRegion samplingRegion("DFG Object Allocation Sinking Phase");
450	return runPhase<ObjectAllocationSinkingPhase>(graph);
451	}
452
453	} } // namespace JSC::DFG
454
455	#endif // ENABLE(DFG_JIT)
456

Line 0 Source/JavaScriptCore/dfg/DFGObjectMaterializationData.cpp_sec1
- Source/JavaScriptCore/dfg/DFGObjectMaterializationData.cpp +58 lines
	1	/*
	2	* Copyright (C) 2014 Apple Inc. All rights reserved.
	3	*
	4	* Redistribution and use in source and binary forms, with or without
	5	* modification, are permitted provided that the following conditions
	6	* are met:
	7	* 1. Redistributions of source code must retain the above copyright
	8	* notice, this list of conditions and the following disclaimer.
	9	* 2. Redistributions in binary form must reproduce the above copyright
	10	* notice, this list of conditions and the following disclaimer in the
	11	* documentation and/or other materials provided with the distribution.
	12	*
	13	* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
	14	* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	15	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
	16	* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
	17	* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
	18	* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
	19	* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
	20	* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
	21	* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	22	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
	23	* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	24	*/
	25
	26	#include "config.h"
	27	#include "DFGObjectMaterializationData.h"
	28
	29	namespace JSC { namespace DFG {
	30
	31	void PhantomPropertyValue::dump(PrintStream& out) const
	32	{
	33	out.print("id", m_identifierNumber);
	34	}
	35
	36	void ObjectMaterializationData::dump(PrintStream& out) const
	37	{
	38	out.print("[", listDump(m_properties), "]");
	39	}
	40
	41	float ObjectMaterializationData::oneWaySimilarityScore(
	42	const ObjectMaterializationData& other) const
	43	{
	44	unsigned numHits = 0;
	45	for (PhantomPropertyValue value : m_properties) {
	46	if (other.m_properties.contains(value))
	47	numHits++;
	48	}
	49	return static_cast<float>(numHits) / static_cast<float>(m_properties.size());
	50	}
	51
	52	float ObjectMaterializationData::similarityScore(const ObjectMaterializationData& other) const
	53	{
	54	return std::min(oneWaySimilarityScore(other), other.oneWaySimilarityScore(*this));
	55	}
	56
	57	} } // namespace JSC::DFG
	58

Line 0 Source/JavaScriptCore/dfg/DFGPhiChildren.cpp_sec1
- Source/JavaScriptCore/dfg/DFGPhiChildren.cpp +61 lines
	1	/*
	2	* Copyright (C) 2014 Apple Inc. All rights reserved.
	3	*
	4	* Redistribution and use in source and binary forms, with or without
	5	* modification, are permitted provided that the following conditions
	6	* are met:
	7	* 1. Redistributions of source code must retain the above copyright
	8	* notice, this list of conditions and the following disclaimer.
	9	* 2. Redistributions in binary form must reproduce the above copyright
	10	* notice, this list of conditions and the following disclaimer in the
	11	* documentation and/or other materials provided with the distribution.
	12	*
	13	* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
	14	* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	15	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
	16	* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
	17	* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
	18	* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
	19	* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
	20	* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
	21	* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	22	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
	23	* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	24	*/
	25
	26	#include "config.h"
	27	#include "DFGPhiChildren.h"
	28
	29	#if ENABLE(DFG_JIT)
	30
	31	namespace JSC { namespace DFG {
	32
	33	PhiChildren::PhiChildren()
	34	{
	35	}
	36
	37	PhiChildren::PhiChildren(Graph& graph)
	38	{
	39	for (BasicBlock* block : graph.blocksInNaturalOrder()) {
	40	for (Node* node : *block) {
	41	if (node->op() != Upsilon)
	42	continue;
	43
	44	m_children.add(node->phi(), List()).iterator->value.append(node);
	45	}
	46	}
	47	}
	48
	49	PhiChildren::~PhiChildren()
	50	{
	51	}
	52
	53	const PhiChildren::List& PhiChildren::childrenOf(Node* node) const
	54	{
	55	return m_children.get(node);
	56	}
	57
	58	} } // namespace JSC::DFG
	59
	60	#endif // ENABLE(DFG_JIT)
	61