intersectionOfPastValuesAtHead must filter values after they've observed an invalidat...
[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                     AbstractValue value = block->valuesAtHead[i];
146                     // We need to guarantee that when we do an OSR entry, we validate the incoming
147                     // value as if it could be live past an invalidation point. Otherwise, we may
148                     // OSR enter with a value with the wrong structure, and an InvalidationPoint's
149                     // promise of filtering the structure set of certain values is no longer upheld.
150                     value.m_structure.observeInvalidationPoint();
151                     block->intersectionOfPastValuesAtHead[i].filter(value);
152                 }
153             }
154         }
155         
156         return true;
157     }
158     
159 private:
160     bool injectOSR(BasicBlock* block)
161     {
162         if (m_verbose)
163             dataLog("   Found must-handle block: ", *block, "\n");
164         
165         bool changed = false;
166         const Operands<JSValue>& mustHandleValues = m_graph.m_plan.mustHandleValues();
167         for (size_t i = mustHandleValues.size(); i--;) {
168             int operand = mustHandleValues.operandForIndex(i);
169             JSValue value = mustHandleValues[i];
170             Node* node = block->variablesAtHead.operand(operand);
171             if (!node) {
172                 if (m_verbose)
173                     dataLog("   Not live: ", VirtualRegister(operand), "\n");
174                 continue;
175             }
176             
177             if (m_verbose)
178                 dataLog("   Widening ", VirtualRegister(operand), " with ", value, "\n");
179             
180             AbstractValue& target = block->valuesAtHead.operand(operand);
181             changed |= target.mergeOSREntryValue(m_graph, value);
182             target.fixTypeForRepresentation(
183                 m_graph, resultFor(node->variableAccessData()->flushFormat()));
184         }
185         
186         if (changed || !block->cfaHasVisited) {
187             block->cfaShouldRevisit = true;
188             return true;
189         }
190         
191         return false;
192     }
193     
194     void performBlockCFA(BasicBlock* block)
195     {
196         if (!block)
197             return;
198         if (!block->cfaShouldRevisit)
199             return;
200         if (m_verbose)
201             dataLog("   Block ", *block, ":\n");
202         
203         if (m_blocksWithOSR.remove(block))
204             injectOSR(block);
205         
206         m_state.beginBasicBlock(block);
207         if (m_verbose) {
208             dataLog("      head vars: ", block->valuesAtHead, "\n");
209             if (m_graph.m_form == SSA)
210                 dataLog("      head regs: ", nodeValuePairListDump(block->ssa->valuesAtHead), "\n");
211         }
212         for (unsigned i = 0; i < block->size(); ++i) {
213             Node* node = block->at(i);
214             if (m_verbose) {
215                 dataLogF("      %s @%u: ", Graph::opName(node->op()), node->index());
216                 
217                 if (!safeToExecute(m_state, m_graph, node))
218                     dataLog("(UNSAFE) ");
219                 
220                 dataLog(m_state.variablesForDebugging(), " ", m_interpreter);
221                 
222                 dataLogF("\n");
223             }
224             if (!m_interpreter.execute(i)) {
225                 if (m_verbose)
226                     dataLogF("         Expect OSR exit.\n");
227                 break;
228             }
229             
230             if (!ASSERT_DISABLED
231                 && m_state.didClobberOrFolded() != writesOverlap(m_graph, node, JSCell_structureID))
232                 DFG_CRASH(m_graph, node, toCString("AI-clobberize disagreement; AI says ", m_state.clobberState(), " while clobberize says ", writeSet(m_graph, node)).data());
233         }
234         if (m_verbose) {
235             dataLogF("      tail regs: ");
236             m_interpreter.dump(WTF::dataFile());
237             dataLogF("\n");
238         }
239         m_changed |= m_state.endBasicBlock();
240         
241         if (m_verbose) {
242             dataLog("      tail vars: ", block->valuesAtTail, "\n");
243             if (m_graph.m_form == SSA)
244                 dataLog("      head regs: ", nodeValuePairListDump(block->ssa->valuesAtTail), "\n");
245         }
246     }
247     
248     void performForwardCFA()
249     {
250         ++m_count;
251         if (m_verbose)
252             dataLogF("CFA [%u]\n", m_count);
253         
254         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex)
255             performBlockCFA(m_graph.block(blockIndex));
256     }
257
258 private:
259     InPlaceAbstractState m_state;
260     AbstractInterpreter<InPlaceAbstractState> m_interpreter;
261     BlockSet m_blocksWithOSR;
262     
263     bool m_verbose;
264     
265     bool m_changed;
266     unsigned m_count;
267 };
268
269 bool performCFA(Graph& graph)
270 {
271     return runPhase<CFAPhase>(graph);
272 }
273
274 } } // namespace JSC::DFG
275
276 #endif // ENABLE(DFG_JIT)