Attachment #238154 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;



#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.
        //
        // 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.
        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
            HashSet<Node*> materialized = materializedAtHead[block];
            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++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()));
                        
                        m_materializationPoints.add(std::make_pair(node, escapee), materialize);
                    });
            }
            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.
        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());
            }
            
            // FIXME: I feel like this completely messes up preexisting MovHints.
            for (SSACalculator::Def* phiDef : ssaCalculator.phisForBlock(block)) {
                m_insertionSet.insert(0, phiDef->value());
                mapping.add(indexToNode[phiDef->variable()->index()], phiDef->value());
            }
            
            for (Node* node : *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/DFGObjectAllocationSinkingPhase.cpp_sec1
- Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp +436 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	//
111	// It just so happens that this forward flow problem also tells us where we would
112	// materialize those nodes that we choose to sink.
113	pruneSinkingCandidates();
114
115	// At this point we are committed to sinking the sinking candidates.
116	determineMaterializationPoints();
117	placeMaterializationPoints();
118	promoteSunkenFields();
119
120	return m_changed;
121	}
122
123	void identifyPhiSinkingCandidates()
124	{
125	for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
126	for (Node* node : *block) {
127	if (node->op() != Phi)
128	continue;
129
130	PhiChildren::List& upsilons = phiChildren.upsilonsOf(node);
131	if (upsilons.isEmpty())
132	continue;
133
134	if (upsilons[0]->child1()->op() != MaterializeNewObject)
135	continue;
136
137	bool allChildrenAreUniquelyReferenced = true;
138	for (Node* upsilonNode : upsilons) {
139	if (upsilonNode->child1()->refCount() != 1) {
140	allChildrenAreUniquelyReferenced = false;
141	break;
142	}
143	}
144	if (!allChildrenAreUniquelyReferenced)
145	continue;
146
147	bool allChildrenAreSameType = true;
148	for (unsigned i = upsilons.size(); i-- > 1;) {
149	if (upsilons[i]->child1()->op() != upsilons[0]->child1()->op()) {
150	allChildrenAreSameType = false;
151	break;
152	}
153	}
154	if (!allChildrenAreSameType)
155	continue;
156
157	// This could be a pessimisation if the various materializations are too
158	// different from one another. We use a simple heuristic here: all of the
159	// materializations must share at least half of their fields with the first
160	// one.
161	bool allAreSimilarEnough = true;
162	for (unsigned i = upsilons.size(); i-- > 1;) {
163	float score =
164	upsilons[i]->child1()->objectMaterializationData().similarityScore(
165	upsilons[0]->child1()->objectMaterializationData());
166	if (score < 0.5) {
167	allAreSimilarEnough = false;
168	break;
169	}
170	}
171	if (!allAreSimilarEnough)
172	continue;
173
174	m_phiSinkCandidates.append(node);
175	}
176	}
177	}
178
179	void pruneSinkingCandidates()
180	{
181	m_sinkCandidates.clear();
182	BlockMap<HashSet<Node*>> sinkCandidatesAtHead(m_graph);
183	BlockMap<HashSet<Node*>> sinkCandidatesAtTail(m_graph);
184
185	bool changed;
186	do {
187	changed = false;
188	for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
189	HashSet<Node*> sinkCandidates = sinkCandidatesAtHead[block];
190	for (Node* node : *block) {
191	handleNode(
192	node,
193	[&] () {
194	sinkCandidates.add(node);
195	},
196	[&] (Node* escapee) {
197	sinkCandidates.remove(escapee);
198	});
199	}
200	if (sinkCandidatesAtTail[block] == sinkCandidates)
201	continue;
202
203	sinkCandidatesAtTail[block] = sinkCandidates;
204	changed = true;
205
206	for (BasicBlock* successorBlock : block->successors()) {
207	for (Node* sinkCandidate : sinkCandidates) {
208	if (!successorBlock->ssa->liveAtHead.contains(sinkCandidate))
209	continue;
210	sinkCandidatesAtHead[successorBlock].add(sinkCandidate);
211	}
212	}
213	}
214	} while (changed);
215
216	// A node is a sink candidate if it is in the sinkCandidatesAtTail of a block but not in
217	// the liveAtTail of that same block.
218	for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
219	for (Node* sinkCandidate : sinkCandidatesAtTail[block]) {
220	if (!block->ssa->liveAtTail.contains(sinkCandidate))
221	m_sinkCandidates.add(sinkCandidate);
222	}
223	}
224
225	// A node should be materialized if it is a sinking candidate, and we haven't removed it
226	// from the sink candidates set yet - since that means that it may not have been
227	// materialized yet.
228	// FIXME: oddly, anytime that we would have a basic block where something is "maybe
229	// materialized", we would make it always materialized by having the not-materializing
230	}
231
232	void determineMaterializationPoints()
233	{
234	// The premise of this pass is that if there exists a point in the program where some
235	// path from a phantom allocation site to that point causes materialization, then all
236	// paths cause materialization.
237
238	m_materializationPoints.clear();
239
240	BlockMap<HashSet<Node*>> materializedAtHead;
241	BlockMap<HashSet<Node*>> materializedAtTail;
242
243	bool changed;
244	do {
245	changed = false;
246	for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
247	HashSet<Node*> materialized = materializedAtHead[block];
248	for (Node* node : *block) {
249	handleNode(
250	node,
251	doNothing,
252	[&] (Node* escapee) {
253	materialized.add(escapee);
254	});
255	}
256
257	if (materialized == materializedAtTail[block])
258	continue;
259
260	changed = true;
261
262	for (BasicBlock* successorBlock : block->successors()) {
263	for (Node* materializee : materialized) {
264	if (!successorBlock->ssa->liveAtHead.contains(materializee))
265	continue;
266	materializedAtHead[successorBlock].add(materializee);
267	}
268	}
269	}
270	} while (changed);
271
272	// A materialization edge exists at any point where a node escapes but hasn't been
273	// materialized yet.
274	for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
275	HashSet<Node*> materialized = materializedAtHead[block];
276	for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
277	handleNode(
278	node,
279	doNothing,
280	[&] (Node* escapee) {
281	if (!materialized.add(escapee))
282	return;
283
284	Node* materialize = m_insertionSet.insertNode(
285	nodeIndex, escapee->prediction(), MaterializeNewObject,
286	NodeOrigin(
287	escapee->origin.semantic,
288	node->origin.forExit),
289	OpInfo(m_graph.m_objectMaterializationData.add()));
290
291	m_materializationPoints.add(std::make_pair(node, escapee), materialize);
292	});
293	}
294	m_insertionSet.execute(block);
295	}
296	}
297
298	void placeMaterializationPoints()
299	{
300	SSACalculator ssaCalculator(m_graph);
301
302	HashMap<Node, SSACalculator::Variable> nodeToVariable;
303	Vector<Node*> indexToNode;
304
305	for (Node* node : m_sinkCandidates) {
306	SSACalculator::Variable* variable = ssaCalculator.newVariable();
307	nodeToVariable.add(node, variable);
308	ASSERT(indexToNode.size() == variable->index());
309	indexToNode.append(node);
310
311	node->setOpAndDefaultFlags(PhantomNewObject);
312	}
313
314	for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
315	for (Node* node : *block) {
316	if (SSACalculator::Variable* variable = nodeToVariable.get(node))
317	ssaCalculator.newDef(variable, block, node);
318
319	m_graph.doToChildren(
320	node,
321	[&] (Edge edge) {
322	Node* materialize =
323	m_materializationPoints.get(std::make_pair(node, edge.node()));
324	if (!materialize)
325	return;
326
327	ssaCalculator.newDef(
328	nodeToVariable.get(edge.node()), block, materialize);
329	});
330	}
331	}
332
333	ssaCalculator.computePhis(
334	[&] (SSACalculator::Variable* variable, BasicBlock* block) -> Node* {
335	Node* allocation = indexToNode[variable->index()];
336	if (!block->ssa->liveAtHead.contains(allocation))
337	return nullptr;
338
339	Node* phiNode = m_graph.addNode(
340	allocation->prediction(), Phi, NodeOrigin());
341	phiNode->mergeFlags(NodeResultJS);
342	return phiNode;
343	});
344
345	// Place Phis in the right places. Replace all uses of any allocation with the appropriate
346	// materialization. Create the appropriate Upsilon nodes.
347	for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
348	HashMap<Node, Node> mapping;
349
350	for (Node* candidate : block->ssa->liveAtHead) {
351	SSACalculator::Variable* variable = nodeToVariable.get(candidate);
352	if (!variable)
353	continue;
354
355	Def* def = ssaCalculator.reachingDefAtHead(block, variable);
356	if (!def)
357	continue;
358
359	mapping.add(indexToNode[variable->index()], def->value());
360	}
361
362	// FIXME: I feel like this completely messes up preexisting MovHints.
363	for (SSACalculator::Def* phiDef : ssaCalculator.phisForBlock(block)) {
364	m_insertionSet.insert(0, phiDef->value());
365	mapping.add(indexToNode[phiDef->variable()->index()], phiDef->value());
366	}
367
368	for (Node* node : *block) {
369
370	}
371	}
372	}
373
374	template<typename... Args>
375	static void doNothing(Args...) { }
376
377	template<typename SinkCandidateFunctor, typename EscapeFunctor>
378	void handleNode(
379	Node* node,
380	const SinkCandidateFunctor& sinkCandidate,
381	const EscapeFunctor& escape)
382	{
383	switch (node->op()) {
384	case NewObject:
385	case MaterializeNewObject:
386	sinkCandidate();
387	break;
388
389	case Phi:
390	if (m_phiSinkCandidates.contains(node))
391	sinkCandidate();
392	break;
393
394	case CheckStructure:
395	case GetByOffset:
396	case MultiGetByOffset:
397	case PutStructure:
398	case GetGetterSetterByOffset:
399	break;
400
401	case PutByOffset:
402	escape(node->child3().node());
403	break;
404
405	case MultiPutByOffset:
406	escape(node->child3().node());
407	break;
408
409	default:
410	m_graph.doToChildren(
411	node,
412	[&escape] (Edge edge) {
413	escape(edge.node());
414	});
415	break;
416	}
417	}
418
419	PhiChildren m_phiChildren;
420	HashSet<Node*> m_phiSinkCandidates;
421	HashSet<Node*> m_sinkCandidates;
422	HashMap<std::pair<Node, Node>, Node*> m_materializationPoints;
423	InsertionSet m_insertionSet;
424	bool m_changed;
425	};
426
427	bool performObjectAllocationSinking(Graph& graph)
428	{
429	SamplingRegion samplingRegion("DFG Object Allocation Sinking Phase");
430	return runPhase<ObjectAllocationSinkingPhase>(graph);
431	}
432
433	} } // namespace JSC::DFG
434
435	#endif // ENABLE(DFG_JIT)
436

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