Move back primary header includes next to config.h
[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 #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
43 namespace JSC { namespace DFG {
44
45 namespace {
46
47 struct LoopData {
48     LoopData()
49         : preHeader(0)
50     {
51     }
52     
53     ClobberSet writes;
54     BasicBlock* preHeader;
55 };
56
57 } // anonymous namespace
58
59 class LICMPhase : public Phase {
60     static const bool verbose = false;
61     
62 public:
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
202 private:
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
282 bool 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