Attachment #238151 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; }



#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) \



/*
 * 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();
        
        // 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.
        pruneSinkingCandidates();

        // At this point we are committed to sinking the sinking candidates.
        sinkSinkingCandidates();
        
        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);
            }
        }
    }
    
    void sinkSinkingCandidates()
    {
        
    }

    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;
    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 +94 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 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/DFGObjectAllocationSinkingPhase.cpp_sec1
- Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp +287 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	performLivenessAnalysis();
95
96	// Conduct one fixpoint iteration, that involves finding nodes that are candidates for
97	// sinking and then sinking them. We proceed roughly as follows:
98	//
99	// 1) Identify Phis that it would be meaningful to sink.
100	// 2) Figure out if the things that are sinkable would be profitable to sink.
101	// 3) Sink them.
102
103	m_phiSinkCandidates.clear();
104	if (phiMode == ConsiderPhis)
105	identifyPhiSinkingCandidates();
106
107	// We want to only do sinking for those things that would benefit. We use a rough
108	// heuristic: if it's possible for an allocation to make it to a return without escaping,
109	// then we assume that it's worth sinking. It's a simple forward flow problem.
110	pruneSinkingCandidates();
111
112	// At this point we are committed to sinking the sinking candidates.
113	sinkSinkingCandidates();
114
115	return m_changed;
116	}
117
118	void identifyPhiSinkingCandidates()
119	{
120	for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
121	for (Node* node : *block) {
122	if (node->op() != Phi)
123	continue;
124
125	PhiChildren::List& upsilons = phiChildren.upsilonsOf(node);
126	if (upsilons.isEmpty())
127	continue;
128
129	if (upsilons[0]->child1()->op() != MaterializeNewObject)
130	continue;
131
132	bool allChildrenAreUniquelyReferenced = true;
133	for (Node* upsilonNode : upsilons) {
134	if (upsilonNode->child1()->refCount() != 1) {
135	allChildrenAreUniquelyReferenced = false;
136	break;
137	}
138	}
139	if (!allChildrenAreUniquelyReferenced)
140	continue;
141
142	bool allChildrenAreSameType = true;
143	for (unsigned i = upsilons.size(); i-- > 1;) {
144	if (upsilons[i]->child1()->op() != upsilons[0]->child1()->op()) {
145	allChildrenAreSameType = false;
146	break;
147	}
148	}
149	if (!allChildrenAreSameType)
150	continue;
151
152	// This could be a pessimisation if the various materializations are too
153	// different from one another. We use a simple heuristic here: all of the
154	// materializations must share at least half of their fields with the first
155	// one.
156	bool allAreSimilarEnough = true;
157	for (unsigned i = upsilons.size(); i-- > 1;) {
158	float score =
159	upsilons[i]->child1()->objectMaterializationData().similarityScore(
160	upsilons[0]->child1()->objectMaterializationData());
161	if (score < 0.5) {
162	allAreSimilarEnough = false;
163	break;
164	}
165	}
166	if (!allAreSimilarEnough)
167	continue;
168
169	m_phiSinkCandidates.append(node);
170	}
171	}
172	}
173
174	void pruneSinkingCandidates()
175	{
176	m_sinkCandidates.clear();
177	BlockMap<HashSet<Node*>> sinkCandidatesAtHead(m_graph);
178	BlockMap<HashSet<Node*>> sinkCandidatesAtTail(m_graph);
179
180	bool changed;
181	do {
182	changed = false;
183	for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
184	HashSet<Node*> sinkCandidates = sinkCandidatesAtHead[block];
185	for (Node* node : *block) {
186	handleNode(
187	node,
188	[&] () {
189	sinkCandidates.add(node);
190	},
191	[&] (Node* escapee) {
192	sinkCandidates.remove(escapee);
193	});
194	}
195	if (sinkCandidatesAtTail[block] == sinkCandidates)
196	continue;
197
198	sinkCandidatesAtTail[block] = sinkCandidates;
199	changed = true;
200
201	for (BasicBlock* successorBlock : block->successors()) {
202	for (Node* sinkCandidate : sinkCandidates) {
203	if (!successorBlock->ssa->liveAtHead.contains(sinkCandidate))
204	continue;
205	sinkCandidatesAtHead[successorBlock].add(sinkCandidate);
206	}
207	}
208	}
209	} while (changed);
210
211	// A node is a sink candidate if it is in the sinkCandidatesAtTail of a block but not in
212	// the liveAtTail of that same block.
213	for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
214	for (Node* sinkCandidate : sinkCandidatesAtTail[block]) {
215	if (!block->ssa->liveAtTail.contains(sinkCandidate))
216	m_sinkCandidates.add(sinkCandidate);
217	}
218	}
219	}
220
221	void sinkSinkingCandidates()
222	{
223
224	}
225
226	template<typename... Args>
227	static void doNothing(Args...) { }
228
229	template<typename SinkCandidateFunctor, typename EscapeFunctor>
230	void handleNode(
231	Node* node,
232	const SinkCandidateFunctor& sinkCandidate,
233	const EscapeFunctor& escape)
234	{
235	switch (node->op()) {
236	case NewObject:
237	case MaterializeNewObject:
238	sinkCandidate();
239	break;
240
241	case Phi:
242	if (m_phiSinkCandidates.contains(node))
243	sinkCandidate();
244	break;
245
246	case CheckStructure:
247	case GetByOffset:
248	case MultiGetByOffset:
249	case PutStructure:
250	case GetGetterSetterByOffset:
251	break;
252
253	case PutByOffset:
254	escape(node->child3().node());
255	break;
256
257	case MultiPutByOffset:
258	escape(node->child3().node());
259	break;
260
261	default:
262	m_graph.doToChildren(
263	node,
264	[&escape] (Edge edge) {
265	escape(edge.node());
266	});
267	break;
268	}
269	}
270
271	PhiChildren m_phiChildren;
272	HashSet<Node*> m_phiSinkCandidates;
273	HashSet<Node*> m_sinkCandidates;
274	InsertionSet m_insertionSet;
275	bool m_changed;
276	};
277
278	bool performObjectAllocationSinking(Graph& graph)
279	{
280	SamplingRegion samplingRegion("DFG Object Allocation Sinking Phase");
281	return runPhase<ObjectAllocationSinkingPhase>(graph);
282	}
283
284	} } // namespace JSC::DFG
285
286	#endif // ENABLE(DFG_JIT)
287

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