a036820f50410b37ec35f2524ca3edef67f5e899
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGLivenessAnalysisPhase.cpp
1 /*
2  * Copyright (C) 2013, 2015-2016 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 "DFGLivenessAnalysisPhase.h"
28
29 #if ENABLE(DFG_JIT)
30
31 #include "DFGBasicBlockInlines.h"
32 #include "DFGBlockMapInlines.h"
33 #include "DFGFlowIndexing.h"
34 #include "DFGGraph.h"
35 #include "DFGInsertionSet.h"
36 #include "DFGPhase.h"
37 #include "JSCInlines.h"
38 #include <wtf/BitVector.h>
39 #include <wtf/IndexSparseSet.h>
40
41 namespace JSC { namespace DFG {
42
43 class LivenessAnalysisPhase : public Phase {
44 public:
45     LivenessAnalysisPhase(Graph& graph)
46         : Phase(graph, "liveness analysis")
47         , m_dirtyBlocks(m_graph.numBlocks())
48         , m_indexing(*m_graph.m_indexingCache)
49         , m_liveAtHead(m_graph)
50         , m_liveAtTail(m_graph)
51     {
52         m_graph.m_indexingCache->recompute();
53         m_workset = std::make_unique<IndexSparseSet<UnsafeVectorOverflow>>(m_graph.m_indexingCache->numIndices());
54     }
55
56     bool run()
57     {
58         // Start with all valid block dirty.
59         BlockIndex numBlock = m_graph.numBlocks();
60         m_dirtyBlocks.ensureSize(numBlock);
61         for (BlockIndex blockIndex = 0; blockIndex < numBlock; ++blockIndex) {
62             if (m_graph.block(blockIndex))
63                 m_dirtyBlocks.quickSet(blockIndex);
64         }
65
66         // Fixpoint until we do not add any new live values at tail.
67         bool changed;
68         do {
69             changed = false;
70
71             for (BlockIndex blockIndex = numBlock; blockIndex--;) {
72                 if (!m_dirtyBlocks.quickClear(blockIndex))
73                     continue;
74
75                 changed |= processBlock(blockIndex);
76             }
77         } while (changed);
78
79         // Update the per-block node list for live and tail.
80         for (BlockIndex blockIndex = numBlock; blockIndex--;) {
81             BasicBlock* block = m_graph.block(blockIndex);
82             if (!block)
83                 continue;
84
85             {
86                 const Vector<unsigned, 0, UnsafeVectorOverflow, 1>& liveAtHeadIndices = m_liveAtHead[blockIndex];
87                 Vector<NodeFlowProjection>& liveAtHead = block->ssa->liveAtHead;
88                 liveAtHead.resize(0);
89                 liveAtHead.reserveCapacity(liveAtHeadIndices.size());
90                 for (unsigned index : liveAtHeadIndices)
91                     liveAtHead.uncheckedAppend(m_indexing.nodeProjection(index));
92             }
93             {
94                 const HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>& liveAtTailIndices = m_liveAtTail[blockIndex];
95                 Vector<NodeFlowProjection>& liveAtTail = block->ssa->liveAtTail;
96                 liveAtTail.resize(0);
97                 liveAtTail.reserveCapacity(liveAtTailIndices.size());
98                 for (unsigned index : m_liveAtTail[blockIndex])
99                     liveAtTail.uncheckedAppend(m_indexing.nodeProjection(index));
100             }
101         }
102
103         return true;
104     }
105
106 private:
107     bool processBlock(BlockIndex blockIndex)
108     {
109         BasicBlock* block = m_graph.block(blockIndex);
110         ASSERT_WITH_MESSAGE(block, "Only dirty blocks needs updates. A null block should never be dirty.");
111
112         m_workset->clear();
113         for (unsigned index : m_liveAtTail[blockIndex])
114             m_workset->add(index);
115
116         for (unsigned nodeIndex = block->size(); nodeIndex--;) {
117             Node* node = block->at(nodeIndex);
118
119             auto handleEdge = [&] (Edge& edge) {
120                 bool newEntry = m_workset->add(m_indexing.index(edge.node()));
121                 edge.setKillStatus(newEntry ? DoesKill : DoesNotKill);
122             };
123             
124             switch (node->op()) {
125             case Upsilon: {
126                 ASSERT_WITH_MESSAGE(!m_workset->contains(node->index()), "Upsilon should not be used as defs by other nodes.");
127
128                 Node* phi = node->phi();
129                 m_workset->remove(m_indexing.shadowIndex(phi));
130                 handleEdge(node->child1());
131                 break;
132             }
133             case Phi: {
134                 m_workset->remove(m_indexing.index(node));
135                 m_workset->add(m_indexing.shadowIndex(node));
136                 break;
137             }
138             default:
139                 m_workset->remove(m_indexing.index(node));
140                 m_graph.doToChildren(node, handleEdge);
141                 break;
142             }
143         }
144
145         // Update live at head.
146         Vector<unsigned, 0, UnsafeVectorOverflow, 1>& liveAtHead = m_liveAtHead[blockIndex];
147         if (m_workset->size() == liveAtHead.size())
148             return false;
149
150         for (unsigned liveIndexAtHead : liveAtHead)
151             m_workset->remove(liveIndexAtHead);
152         ASSERT(!m_workset->isEmpty());
153
154         liveAtHead.reserveCapacity(liveAtHead.size() + m_workset->size());
155         for (unsigned newValue : *m_workset)
156             liveAtHead.uncheckedAppend(newValue);
157
158         bool changedPredecessor = false;
159         for (BasicBlock* predecessor : block->predecessors) {
160             HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>&
161                 liveAtTail = m_liveAtTail[predecessor];
162             for (unsigned newValue : *m_workset) {
163                 if (liveAtTail.add(newValue)) {
164                     if (!m_dirtyBlocks.quickSet(predecessor->index))
165                         changedPredecessor = true;
166                 }
167             }
168         }
169         return changedPredecessor;
170     }
171
172     // Blocks with new live values at tail.
173     BitVector m_dirtyBlocks;
174     
175     FlowIndexing& m_indexing;
176
177     // Live values per block edge.
178     BlockMap<Vector<unsigned, 0, UnsafeVectorOverflow, 1>> m_liveAtHead;
179     BlockMap<HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>> m_liveAtTail;
180
181     // Single sparse set allocated once and used by every basic block.
182     std::unique_ptr<IndexSparseSet<UnsafeVectorOverflow>> m_workset;
183 };
184
185 bool performLivenessAnalysis(Graph& graph)
186 {
187     graph.packNodeIndices();
188
189     return runPhase<LivenessAnalysisPhase>(graph);
190 }
191
192 } } // namespace JSC::DFG
193
194 #endif // ENABLE(DFG_JIT)
195