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