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