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#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
37namespace JSC { namespace DFG {
38
39class LivenessAnalysisPhase : public Phase {
40public:
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->liveAtHead.clear();
61            block->ssa->liveAtTail.clear();
62        }
63
64        do {
65            m_changed = false;
66            for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;)
67                process(blockIndex);
68        } while (m_changed);
69
70        if (!m_graph.block(0)->ssa->liveAtHead.isEmpty()) {
71            startCrashing();
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
83private:
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
158bool 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
168