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