fa9c1bc969f90fda37bb254a16e39d915f0b823c
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGCFAPhase.cpp
1 /*
2  * Copyright (C) 2011-2018 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 "DFGCFAPhase.h"
28
29 #if ENABLE(DFG_JIT)
30
31 #include "DFGAbstractInterpreterInlines.h"
32 #include "DFGBlockSet.h"
33 #include "DFGClobberSet.h"
34 #include "DFGGraph.h"
35 #include "DFGInPlaceAbstractState.h"
36 #include "DFGPhase.h"
37 #include "DFGSafeToExecute.h"
38 #include "OperandsInlines.h"
39 #include "JSCInlines.h"
40
41 namespace JSC { namespace DFG {
42
43 class CFAPhase : public Phase {
44 public:
45     CFAPhase(Graph& graph)
46         : Phase(graph, "control flow analysis")
47         , m_state(graph)
48         , m_interpreter(graph, m_state)
49         , m_verbose(Options::verboseCFA())
50     {
51     }
52     
53     bool run()
54     {
55         ASSERT(m_graph.m_form == ThreadedCPS || m_graph.m_form == SSA);
56         ASSERT(m_graph.m_unificationState == GloballyUnified);
57         ASSERT(m_graph.m_refCountState == EverythingIsLive);
58         
59         m_count = 0;
60
61         if (m_verbose && !shouldDumpGraphAtEachPhase(m_graph.m_plan.mode())) {
62             dataLog("Graph before CFA:\n");
63             m_graph.dump();
64         }
65         
66         // This implements a pseudo-worklist-based forward CFA, except that the visit order
67         // of blocks is the bytecode program order (which is nearly topological), and
68         // instead of a worklist we just walk all basic blocks checking if cfaShouldRevisit
69         // is set to true. This is likely to balance the efficiency properties of both
70         // worklist-based and forward fixpoint-based approaches. Like a worklist-based
71         // approach, it won't visit code if it's meaningless to do so (nothing changed at
72         // the head of the block or the predecessors have not been visited). Like a forward
73         // fixpoint-based approach, it has a high probability of only visiting a block
74         // after all predecessors have been visited. Only loops will cause this analysis to
75         // revisit blocks, and the amount of revisiting is proportional to loop depth.
76         
77         m_state.initialize();
78         
79         if (m_graph.m_form != SSA) {
80             if (m_verbose)
81                 dataLog("   Widening state at OSR entry block.\n");
82             
83             // Widen the abstract values at the block that serves as the must-handle OSR entry.
84             for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
85                 BasicBlock* block = m_graph.block(blockIndex);
86                 if (!block)
87                     continue;
88                 
89                 if (!block->isOSRTarget)
90                     continue;
91                 if (block->bytecodeBegin != m_graph.m_plan.osrEntryBytecodeIndex())
92                     continue;
93                 
94                 // We record that the block needs some OSR stuff, but we don't do that yet. We want to
95                 // handle OSR entry data at the right time in order to get the best compile times. If we
96                 // simply injected OSR data right now, then we'd potentially cause a loop body to be
97                 // interpreted with just the constants we feed it, which is more expensive than if we
98                 // interpreted it with non-constant values. If we always injected this data after the
99                 // main pass of CFA ran, then we would potentially spend a bunch of time rerunning CFA
100                 // after convergence. So, we try very hard to inject OSR data for a block when we first
101                 // naturally come to see it - see the m_blocksWithOSR check in performBlockCFA(). This
102                 // way, we:
103                 //
104                 // - Reduce the likelihood of interpreting the block with constants, since we will inject
105                 //   the OSR entry constants on top of whatever abstract values we got for that block on
106                 //   the first pass. The mix of those two things is likely to not be constant.
107                 //
108                 // - Reduce the total number of CFA reexecutions since we inject the OSR data as part of
109                 //   the normal flow of CFA instead of having to do a second fixpoint. We may still have
110                 //   to do a second fixpoint if we don't even reach the OSR entry block during the main
111                 //   run of CFA, but in that case at least we're not being redundant.
112                 m_blocksWithOSR.add(block);
113             }
114         }
115
116         do {
117             m_changed = false;
118             performForwardCFA();
119         } while (m_changed);
120         
121         if (m_graph.m_form != SSA) {
122             for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
123                 BasicBlock* block = m_graph.block(blockIndex);
124                 if (!block)
125                     continue;
126                 
127                 if (m_blocksWithOSR.remove(block))
128                     m_changed |= injectOSR(block);
129             }
130             
131             while (m_changed) {
132                 m_changed = false;
133                 performForwardCFA();
134             }
135         
136             // Make sure we record the intersection of all proofs that we ever allowed the
137             // compiler to rely upon.
138             for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
139                 BasicBlock* block = m_graph.block(blockIndex);
140                 if (!block)
141                     continue;
142                 
143                 block->intersectionOfCFAHasVisited &= block->cfaHasVisited;
144                 for (unsigned i = block->intersectionOfPastValuesAtHead.size(); i--;)
145                     block->intersectionOfPastValuesAtHead[i].filter(block->valuesAtHead[i]);
146             }
147         }
148         
149         return true;
150     }
151     
152 private:
153     bool injectOSR(BasicBlock* block)
154     {
155         if (m_verbose)
156             dataLog("   Found must-handle block: ", *block, "\n");
157         
158         bool changed = false;
159         const Operands<JSValue>& mustHandleValues = m_graph.m_plan.mustHandleValues();
160         for (size_t i = mustHandleValues.size(); i--;) {
161             int operand = mustHandleValues.operandForIndex(i);
162             JSValue value = mustHandleValues[i];
163             Node* node = block->variablesAtHead.operand(operand);
164             if (!node) {
165                 if (m_verbose)
166                     dataLog("   Not live: ", VirtualRegister(operand), "\n");
167                 continue;
168             }
169             
170             if (m_verbose)
171                 dataLog("   Widening ", VirtualRegister(operand), " with ", value, "\n");
172             
173             AbstractValue& target = block->valuesAtHead.operand(operand);
174             changed |= target.mergeOSREntryValue(m_graph, value);
175             target.fixTypeForRepresentation(
176                 m_graph, resultFor(node->variableAccessData()->flushFormat()));
177         }
178         
179         if (changed || !block->cfaHasVisited) {
180             block->cfaShouldRevisit = true;
181             return true;
182         }
183         
184         return false;
185     }
186     
187     void performBlockCFA(BasicBlock* block)
188     {
189         if (!block)
190             return;
191         if (!block->cfaShouldRevisit)
192             return;
193         if (m_verbose)
194             dataLog("   Block ", *block, ":\n");
195         
196         if (m_blocksWithOSR.remove(block))
197             injectOSR(block);
198         
199         m_state.beginBasicBlock(block);
200         if (m_verbose) {
201             dataLog("      head vars: ", block->valuesAtHead, "\n");
202             if (m_graph.m_form == SSA)
203                 dataLog("      head regs: ", nodeValuePairListDump(block->ssa->valuesAtHead), "\n");
204         }
205         for (unsigned i = 0; i < block->size(); ++i) {
206             Node* node = block->at(i);
207             if (m_verbose) {
208                 dataLogF("      %s @%u: ", Graph::opName(node->op()), node->index());
209                 
210                 if (!safeToExecute(m_state, m_graph, node))
211                     dataLog("(UNSAFE) ");
212                 
213                 dataLog(m_state.variablesForDebugging(), " ", m_interpreter);
214                 
215                 dataLogF("\n");
216             }
217             if (!m_interpreter.execute(i)) {
218                 if (m_verbose)
219                     dataLogF("         Expect OSR exit.\n");
220                 break;
221             }
222             
223             if (!ASSERT_DISABLED
224                 && m_state.didClobberOrFolded() != writesOverlap(m_graph, node, JSCell_structureID))
225                 DFG_CRASH(m_graph, node, toCString("AI-clobberize disagreement; AI says ", m_state.clobberState(), " while clobberize says ", writeSet(m_graph, node)).data());
226         }
227         if (m_verbose) {
228             dataLogF("      tail regs: ");
229             m_interpreter.dump(WTF::dataFile());
230             dataLogF("\n");
231         }
232         m_changed |= m_state.endBasicBlock();
233         
234         if (m_verbose) {
235             dataLog("      tail vars: ", block->valuesAtTail, "\n");
236             if (m_graph.m_form == SSA)
237                 dataLog("      head regs: ", nodeValuePairListDump(block->ssa->valuesAtTail), "\n");
238         }
239     }
240     
241     void performForwardCFA()
242     {
243         ++m_count;
244         if (m_verbose)
245             dataLogF("CFA [%u]\n", m_count);
246         
247         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex)
248             performBlockCFA(m_graph.block(blockIndex));
249     }
250
251 private:
252     InPlaceAbstractState m_state;
253     AbstractInterpreter<InPlaceAbstractState> m_interpreter;
254     BlockSet m_blocksWithOSR;
255     
256     bool m_verbose;
257     
258     bool m_changed;
259     unsigned m_count;
260 };
261
262 bool performCFA(Graph& graph)
263 {
264     return runPhase<CFAPhase>(graph);
265 }
266
267 } } // namespace JSC::DFG
268
269 #endif // ENABLE(DFG_JIT)