Replace WTF::move with WTFMove
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGLivenessAnalysisPhase.cpp
1 /*
2  * Copyright (C) 2013, 2015 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 "DFGGraph.h"
33 #include "DFGInsertionSet.h"
34 #include "DFGPhase.h"
35 #include "JSCInlines.h"
36
37 namespace JSC { namespace DFG {
38
39 class LivenessAnalysisPhase : public Phase {
40 public:
41     LivenessAnalysisPhase(Graph& graph)
42         : Phase(graph, "liveness analysis")
43     {
44     }
45     
46     bool run()
47     {
48         ASSERT(m_graph.m_form == SSA);
49         
50         // Liveness is a backwards analysis; the roots are the blocks that
51         // end in a terminal (Return/Throw/ThrowReferenceError). For now, we
52         // use a fixpoint formulation since liveness is a rapid analysis with
53         // convergence guaranteed after O(connectivity).
54         
55         // Start by assuming that everything is dead.
56         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
57             BasicBlock* block = m_graph.block(blockIndex);
58             if (!block)
59                 continue;
60             block->ssa->liveAtTailIsDirty = true;
61             block->ssa->liveAtHead.clear();
62             block->ssa->liveAtTail.clear();
63         }
64         
65         do {
66             m_changed = false;
67             for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;)
68                 process(blockIndex);
69         } while (m_changed);
70         
71         if (!m_graph.block(0)->ssa->liveAtHead.isEmpty()) {
72             DFG_CRASH(
73                 m_graph, nullptr,
74                 toCString(
75                     "Bad liveness analysis result: live at root is not empty: ",
76                     nodeListDump(m_graph.block(0)->ssa->liveAtHead)).data());
77         }
78         
79         return true;
80     }
81
82 private:
83     void process(BlockIndex blockIndex)
84     {
85         BasicBlock* block = m_graph.block(blockIndex);
86         if (!block)
87             return;
88
89         if (!block->ssa->liveAtTailIsDirty)
90             return;
91         block->ssa->liveAtTailIsDirty = false;
92
93         m_live = block->ssa->liveAtTail;
94         for (unsigned nodeIndex = block->size(); nodeIndex--;) {
95             Node* node = block->at(nodeIndex);
96             
97             // Given an Upsilon:
98             //
99             //    n: Upsilon(@x, ^p)
100             //
101             // We say that it def's @p and @n and uses @x.
102             //
103             // Given a Phi:
104             //
105             //    p: Phi()
106             //
107             // We say nothing. It's neither a use nor a def.
108             //
109             // Given a node:
110             //
111             //    n: Thingy(@a, @b, @c)
112             //
113             // We say that it def's @n and uses @a, @b, @c.
114             
115             switch (node->op()) {
116             case Upsilon: {
117                 Node* phi = node->phi();
118                 m_live.remove(phi);
119                 m_live.remove(node);
120                 m_live.add(node->child1().node());
121                 break;
122             }
123                 
124             case Phi: {
125                 break;
126             }
127                 
128             default:
129                 m_live.remove(node);
130                 DFG_NODE_DO_TO_CHILDREN(m_graph, node, addChildUse);
131                 break;
132             }
133         }
134         
135         for (Node* node : m_live) {
136             if (!block->ssa->liveAtHead.contains(node)) {
137                 m_changed = true;
138                 for (unsigned i = block->predecessors.size(); i--;) {
139                     BasicBlock* predecessor = block->predecessors[i];
140                     if (predecessor->ssa->liveAtTail.add(node).isNewEntry)
141                         predecessor->ssa->liveAtTailIsDirty = true;
142                 }
143             }
144         }
145         block->ssa->liveAtHead = WTFMove(m_live);
146     }
147     
148     void addChildUse(Node*, Edge& edge)
149     {
150         addChildUse(edge);
151     }
152     
153     void addChildUse(Edge& edge)
154     {
155         edge.setKillStatus(m_live.add(edge.node()).isNewEntry ? DoesKill : DoesNotKill);
156     }
157     
158     bool m_changed;
159     HashSet<Node*> m_live;
160 };
161
162 bool performLivenessAnalysis(Graph& graph)
163 {
164     SamplingRegion samplingRegion("DFG Liveness Analysis Phase");
165     return runPhase<LivenessAnalysisPhase>(graph);
166 }
167
168 } } // namespace JSC::DFG
169
170 #endif // ENABLE(DFG_JIT)
171