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