| /* |
| * Copyright (C) 2013, 2015-2016 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 "DFGLivenessAnalysisPhase.h" |
| |
| #if ENABLE(DFG_JIT) |
| |
| #include "DFGBasicBlockInlines.h" |
| #include "DFGBlockMapInlines.h" |
| #include "DFGGraph.h" |
| #include "DFGInsertionSet.h" |
| #include "DFGPhase.h" |
| #include "JSCInlines.h" |
| #include <wtf/BitVector.h> |
| #include <wtf/IndexSparseSet.h> |
| |
| namespace JSC { namespace DFG { |
| |
| class LivenessAnalysisPhase : public Phase { |
| public: |
| LivenessAnalysisPhase(Graph& graph) |
| : Phase(graph, "liveness analysis") |
| , m_dirtyBlocks(m_graph.numBlocks()) |
| , m_liveAtHead(m_graph) |
| , m_liveAtTail(m_graph) |
| , m_workset(graph.maxNodeCount() - 1) |
| { |
| } |
| |
| bool run() |
| { |
| // Start with all valid block dirty. |
| BlockIndex numBlock = m_graph.numBlocks(); |
| m_dirtyBlocks.ensureSize(numBlock); |
| for (BlockIndex blockIndex = 0; blockIndex < numBlock; ++blockIndex) { |
| if (m_graph.block(blockIndex)) |
| m_dirtyBlocks.quickSet(blockIndex); |
| } |
| |
| // Fixpoint until we do not add any new live values at tail. |
| bool changed; |
| do { |
| changed = false; |
| |
| for (BlockIndex blockIndex = numBlock; blockIndex--;) { |
| if (!m_dirtyBlocks.quickClear(blockIndex)) |
| continue; |
| |
| changed |= processBlock(blockIndex); |
| } |
| } while (changed); |
| |
| // Update the per-block node list for live and tail. |
| for (BlockIndex blockIndex = numBlock; blockIndex--;) { |
| BasicBlock* block = m_graph.block(blockIndex); |
| if (!block) |
| continue; |
| |
| { |
| const auto& liveAtHeadIndices = m_liveAtHead[blockIndex]; |
| Vector<Node*>& liveAtHead = block->ssa->liveAtHead; |
| liveAtHead.resize(0); |
| liveAtHead.reserveCapacity(liveAtHeadIndices.size()); |
| for (unsigned index : liveAtHeadIndices) |
| liveAtHead.uncheckedAppend(m_graph.nodeAt(index)); |
| } |
| { |
| const auto& liveAtTailIndices = m_liveAtTail[blockIndex]; |
| Vector<Node*>& liveAtTail = block->ssa->liveAtTail; |
| liveAtTail.resize(0); |
| liveAtTail.reserveCapacity(liveAtTailIndices.size()); |
| for (unsigned index : m_liveAtTail[blockIndex]) |
| liveAtTail.uncheckedAppend(m_graph.nodeAt(index)); |
| } |
| } |
| |
| return true; |
| } |
| |
| private: |
| bool processBlock(BlockIndex blockIndex) |
| { |
| BasicBlock* block = m_graph.block(blockIndex); |
| ASSERT_WITH_MESSAGE(block, "Only dirty blocks needs updates. A null block should never be dirty."); |
| |
| m_workset.clear(); |
| for (unsigned index : m_liveAtTail[blockIndex]) |
| m_workset.add(index); |
| |
| for (unsigned nodeIndex = block->size(); nodeIndex--;) { |
| Node* node = block->at(nodeIndex); |
| |
| // Given an Upsilon: |
| // |
| // n: Upsilon(@x, ^p) |
| // |
| // We say that it def's @p and @n and uses @x. |
| // |
| // Given a Phi: |
| // |
| // p: Phi() |
| // |
| // We say nothing. It's neither a use nor a def. |
| // |
| // Given a node: |
| // |
| // n: Thingy(@a, @b, @c) |
| // |
| // We say that it def's @n and uses @a, @b, @c. |
| |
| switch (node->op()) { |
| case Upsilon: { |
| ASSERT_WITH_MESSAGE(!m_workset.contains(node->index()), "Upsilon should not be used as defs by other nodes."); |
| |
| Node* phi = node->phi(); |
| m_workset.remove(phi->index()); |
| m_workset.add(node->child1()->index()); |
| break; |
| } |
| case Phi: { |
| break; |
| } |
| default: |
| m_workset.remove(node->index()); |
| DFG_NODE_DO_TO_CHILDREN(m_graph, node, addChildUse); |
| break; |
| } |
| } |
| |
| // Update live at head. |
| auto& liveAtHead = m_liveAtHead[blockIndex]; |
| if (m_workset.size() == liveAtHead.size()) |
| return false; |
| |
| for (unsigned liveIndexAtHead : liveAtHead) |
| m_workset.remove(liveIndexAtHead); |
| ASSERT(!m_workset.isEmpty()); |
| |
| liveAtHead.reserveCapacity(liveAtHead.size() + m_workset.size()); |
| for (unsigned newValue : m_workset) |
| liveAtHead.uncheckedAppend(newValue); |
| |
| bool changedPredecessor = false; |
| for (BasicBlock* predecessor : block->predecessors) { |
| auto& liveAtTail = m_liveAtTail[predecessor]; |
| for (unsigned newValue : m_workset) { |
| if (liveAtTail.add(newValue)) { |
| if (!m_dirtyBlocks.quickSet(predecessor->index)) |
| changedPredecessor = true; |
| } |
| } |
| } |
| return changedPredecessor; |
| } |
| |
| ALWAYS_INLINE void addChildUse(Node*, Edge& edge) |
| { |
| bool newEntry = m_workset.add(edge->index()); |
| edge.setKillStatus(newEntry ? DoesKill : DoesNotKill); |
| } |
| |
| // Blocks with new live values at tail. |
| BitVector m_dirtyBlocks; |
| |
| // Live values per block edge. |
| BlockMap<Vector<unsigned, 0, UnsafeVectorOverflow, 1>> m_liveAtHead; |
| BlockMap<HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>> m_liveAtTail; |
| |
| // Single sparse set allocated once and used by every basic block. |
| IndexSparseSet<UnsafeVectorOverflow> m_workset; |
| }; |
| |
| bool performLivenessAnalysis(Graph& graph) |
| { |
| graph.packNodeIndices(); |
| |
| return runPhase<LivenessAnalysisPhase>(graph); |
| } |
| |
| } } // namespace JSC::DFG |
| |
| #endif // ENABLE(DFG_JIT) |
| |