Never include *Inlines.h files in interface headers, and never include *Inlines.h...
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGLivenessAnalysisPhase.cpp
1 /*
2  * Copyright (C) 2013 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
28 #if ENABLE(DFG_JIT)
29
30 #include "DFGLivenessAnalysisPhase.h"
31
32 #include "DFGBasicBlockInlines.h"
33 #include "DFGGraph.h"
34 #include "DFGInsertionSet.h"
35 #include "DFGPhase.h"
36 #include "Operations.h"
37
38 namespace JSC { namespace DFG {
39
40 class LivenessAnalysisPhase : public Phase {
41 public:
42     LivenessAnalysisPhase(Graph& graph)
43         : Phase(graph, "liveness analysis")
44     {
45     }
46     
47     bool run()
48     {
49         ASSERT(m_graph.m_form == SSA);
50         
51         // Liveness is a backwards analysis; the roots are the blocks that
52         // end in a terminal (Return/Throw/ThrowReferenceError). For now, we
53         // use a fixpoint formulation since liveness is a rapid analysis with
54         // convergence guaranteed after O(connectivity).
55         
56         // Start by assuming that everything is dead.
57         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
58             BasicBlock* block = m_graph.block(blockIndex);
59             if (!block)
60                 continue;
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             dataLog(
73                 "Bad liveness analysis result: live at root is not empty: ",
74                 nodeListDump(m_graph.block(0)->ssa->liveAtHead), "\n");
75             dataLog("IR at time of error:\n");
76             m_graph.dump();
77             CRASH();
78         }
79         
80         return true;
81     }
82
83 private:
84     void process(BlockIndex blockIndex)
85     {
86         BasicBlock* block = m_graph.block(blockIndex);
87         if (!block)
88             return;
89         
90         // FIXME: It's likely that this can be improved, for static analyses that use
91         // HashSets. https://bugs.webkit.org/show_bug.cgi?id=118455
92         m_live = block->ssa->liveAtTail;
93         
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         if (m_live == block->ssa->liveAtHead)
136             return;
137         
138         m_changed = true;
139         block->ssa->liveAtHead = m_live;
140         for (unsigned i = block->predecessors.size(); i--;)
141             block->predecessors[i]->ssa->liveAtTail.add(m_live.begin(), m_live.end());
142     }
143     
144     void addChildUse(Node*, Edge& edge)
145     {
146         addChildUse(edge);
147     }
148     
149     void addChildUse(Edge& edge)
150     {
151         edge.setKillStatus(m_live.add(edge.node()).isNewEntry ? DoesKill : DoesNotKill);
152     }
153     
154     bool m_changed;
155     HashSet<Node*> m_live;
156 };
157
158 bool performLivenessAnalysis(Graph& graph)
159 {
160     SamplingRegion samplingRegion("DFG Liveness Analysis Phase");
161     return runPhase<LivenessAnalysisPhase>(graph);
162 }
163
164 } } // namespace JSC::DFG
165
166 #endif // ENABLE(DFG_JIT)
167