1/*
2 * Copyright (C) 2013, 2014 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 "DFGLICMPhase.h"
28
29#if ENABLE(DFG_JIT)
30
31#include "DFGAbstractInterpreterInlines.h"
32#include "DFGAtTailAbstractState.h"
33#include "DFGBasicBlockInlines.h"
34#include "DFGClobberSet.h"
35#include "DFGClobberize.h"
36#include "DFGEdgeDominates.h"
37#include "DFGGraph.h"
38#include "DFGInsertionSet.h"
39#include "DFGPhase.h"
40#include "DFGSafeToExecute.h"
41#include "JSCInlines.h"
42
43namespace JSC { namespace DFG {
44
45namespace {
46
47struct LoopData {
48    LoopData()
49        : preHeader(0)
50    {
51    }
52
53    ClobberSet writes;
54    BasicBlock* preHeader;
55};
56
57} // anonymous namespace
58
59class LICMPhase : public Phase {
60    static const bool verbose = false;
61
62public:
63    LICMPhase(Graph& graph)
64        : Phase(graph, "LICM")
65        , m_interpreter(graph, m_state)
66    {
67    }
68
69    bool run()
70    {
71        ASSERT(m_graph.m_form == SSA);
72
73        m_graph.m_dominators.computeIfNecessary(m_graph);
74        m_graph.m_naturalLoops.computeIfNecessary(m_graph);
75
76        m_data.resize(m_graph.m_naturalLoops.numLoops());
77
78        // Figure out the set of things each loop writes to, not including blocks that
79        // belong to inner loops. We fix this later.
80        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
81            BasicBlock* block = m_graph.block(blockIndex);
82            if (!block)
83                continue;
84
85            // Skip blocks that are proved to not execute.
86            // FIXME: This shouldn't be needed.
87            // https://bugs.webkit.org/show_bug.cgi?id=128584
88            if (!block->cfaHasVisited)
89                continue;
90
91            const NaturalLoop* loop = m_graph.m_naturalLoops.innerMostLoopOf(block);
92            if (!loop)
93                continue;
94            LoopData& data = m_data[loop->index()];
95            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
96                Node* node = block->at(nodeIndex);
97
98                // Don't look beyond parts of the code that definitely always exit.
99                // FIXME: This shouldn't be needed.
100                // https://bugs.webkit.org/show_bug.cgi?id=128584
101                if (node->op() == ForceOSRExit)
102                    break;
103
104                addWrites(m_graph, node, data.writes);
105            }
106        }
107
108        // For each loop:
109        // - Identify its pre-header.
110        // - Make sure its outer loops know what it clobbers.
111        for (unsigned loopIndex = m_graph.m_naturalLoops.numLoops(); loopIndex--;) {
112            const NaturalLoop& loop = m_graph.m_naturalLoops.loop(loopIndex);
113            LoopData& data = m_data[loop.index()];
114            for (
115                const NaturalLoop* outerLoop = m_graph.m_naturalLoops.innerMostOuterLoop(loop);
116                outerLoop;
117                outerLoop = m_graph.m_naturalLoops.innerMostOuterLoop(*outerLoop))
118                m_data[outerLoop->index()].writes.addAll(data.writes);
119
120            BasicBlock* header = loop.header();
121            BasicBlock* preHeader = 0;
122            for (unsigned i = header->predecessors.size(); i--;) {
123                BasicBlock* predecessor = header->predecessors[i];
124                if (m_graph.m_dominators.dominates(header, predecessor))
125                    continue;
126                RELEASE_ASSERT(!preHeader || preHeader == predecessor);
127                preHeader = predecessor;
128            }
129
130            RELEASE_ASSERT(preHeader->last()->op() == Jump);
131
132            data.preHeader = preHeader;
133        }
134
135        m_graph.initializeNodeOwners();
136
137        // Walk all basic blocks that belong to loops, looking for hoisting opportunities.
138        // We try to hoist to the outer-most loop that permits it. Hoisting is valid if:
139        // - The node doesn't write anything.
140        // - The node doesn't read anything that the loop writes.
141        // - The preHeader's state at tail makes the node safe to execute.
142        // - The loop's children all belong to nodes that strictly dominate the loop header.
143        // - The preHeader's state at tail is still valid. This is mostly to save compile
144        //   time and preserve some kind of sanity, if we hoist something that must exit.
145        //
146        // Also, we need to remember to:
147        // - Update the state-at-tail with the node we hoisted, so future hoist candidates
148        //   know about any type checks we hoisted.
149        //
150        // For maximum profit, we walk blocks in DFS order to ensure that we generally
151        // tend to hoist dominators before dominatees.
152        Vector<BasicBlock*> depthFirst;
153        m_graph.getBlocksInDepthFirstOrder(depthFirst);
154        Vector<const NaturalLoop*> loopStack;
155        bool changed = false;
156        for (
157            unsigned depthFirstIndex = 0;
158            depthFirstIndex < depthFirst.size();
159            ++depthFirstIndex) {
160
161            BasicBlock* block = depthFirst[depthFirstIndex];
162            const NaturalLoop* loop = m_graph.m_naturalLoops.innerMostLoopOf(block);
163            if (!loop)
164                continue;
165
166            loopStack.resize(0);
167            for (
168                const NaturalLoop* current = loop;
169                current;
170                current = m_graph.m_naturalLoops.innerMostOuterLoop(*current))
171                loopStack.append(current);
172
173            // Remember: the loop stack has the inner-most loop at index 0, so if we want
174            // to bias hoisting to outer loops then we need to use a reverse loop.
175
176            if (verbose) {
177                dataLog(
178                    "Attempting to hoist out of block ", *block, " in loops:\n");
179                for (unsigned stackIndex = loopStack.size(); stackIndex--;) {
180                    dataLog(
181                        "        ", *loopStack[stackIndex], ", which writes ",
182                        m_data[loopStack[stackIndex]->index()].writes, "\n");
183                }
184            }
185
186            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
187                Node*& nodeRef = block->at(nodeIndex);
188                if (doesWrites(m_graph, nodeRef)) {
189                    if (verbose)
190                        dataLog("    Not hoisting ", nodeRef, " because it writes things.\n");
191                    continue;
192                }
193
194                for (unsigned stackIndex = loopStack.size(); stackIndex--;)
195                    changed |= attemptHoist(block, nodeRef, loopStack[stackIndex]);
196            }
197        }
198
199        return changed;
200    }
201
202private:
203    bool attemptHoist(BasicBlock* fromBlock, Node*& nodeRef, const NaturalLoop* loop)
204    {
205        Node* node = nodeRef;
206        LoopData& data = m_data[loop->index()];
207
208        if (!data.preHeader->cfaDidFinish) {
209            if (verbose)
210                dataLog("    Not hoisting ", node, " because CFA is invalid.\n");
211            return false;
212        }
213
214        if (!edgesDominate(m_graph, node, data.preHeader)) {
215            if (verbose) {
216                dataLog(
217                    "    Not hoisting ", node, " because it isn't loop invariant.\n");
218            }
219            return false;
220        }
221
222        if (readsOverlap(m_graph, node, data.writes)) {
223            if (verbose) {
224                dataLog(
225                    "    Not hoisting ", node,
226                    " because it reads things that the loop writes.\n");
227            }
228            return false;
229        }
230
231        m_state.initializeTo(data.preHeader);
232        if (!safeToExecute(m_state, m_graph, node)) {
233            if (verbose) {
234                dataLog(
235                    "    Not hoisting ", node, " because it isn't safe to execute.\n");
236            }
237            return false;
238        }
239
240        if (verbose) {
241            dataLog(
242                "    Hoisting ", node, " from ", *fromBlock, " to ", *data.preHeader,
243                "\n");
244        }
245
246        data.preHeader->insertBeforeLast(node);
247        node->misc.owner = data.preHeader;
248        NodeOrigin originalOrigin = node->origin;
249        node->origin.forExit = data.preHeader->last()->origin.forExit;
250
251        // Modify the states at the end of the preHeader of the loop we hoisted to,
252        // and all pre-headers inside the loop.
253        // FIXME: This could become a scalability bottleneck. Fortunately, most loops
254        // are small and anyway we rapidly skip over basic blocks here.
255        for (unsigned bodyIndex = loop->size(); bodyIndex--;) {
256            BasicBlock* subBlock = loop->at(bodyIndex);
257            const NaturalLoop* subLoop = m_graph.m_naturalLoops.headerOf(subBlock);
258            if (!subLoop)
259                continue;
260            BasicBlock* subPreHeader = m_data[subLoop->index()].preHeader;
261            if (!subPreHeader->cfaDidFinish)
262                continue;
263            m_state.initializeTo(subPreHeader);
264            m_interpreter.execute(node);
265        }
266
267        // It just so happens that all of the nodes we currently know how to hoist
268        // don't have var-arg children. That may change and then we can fix this
269        // code. But for now we just assert that's the case.
270        RELEASE_ASSERT(!(node->flags() & NodeHasVarArgs));
271
272        nodeRef = m_graph.addNode(SpecNone, Phantom, originalOrigin, node->children);
273
274        return true;
275    }
276
277    AtTailAbstractState m_state;
278    AbstractInterpreter<AtTailAbstractState> m_interpreter;
279    Vector<LoopData> m_data;
280};
281
282bool performLICM(Graph& graph)
283{
284    SamplingRegion samplingRegion("DFG LICM Phase");
285    return runPhase<LICMPhase>(graph);
286}
287
288} } // namespace JSC::DFG
289
290#endif // ENABLE(DFG_JIT)
291
292