1/*
2 * Copyright (C) 2013-2015 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 "DFGOSRAvailabilityAnalysisPhase.h"
28
29#if ENABLE(DFG_JIT)
30
31#include "DFGBasicBlockInlines.h"
32#include "DFGGraph.h"
33#include "DFGInsertionSet.h"
34#include "DFGPhase.h"
35#include "JSCInlines.h"
36
37namespace JSC { namespace DFG {
38namespace DFGOSRAvailabilityAnalysisPhaseInternal {
39static constexpr bool verbose = false;
40}
41
42class OSRAvailabilityAnalysisPhase : public Phase {
43public:
44 OSRAvailabilityAnalysisPhase(Graph& graph)
45 : Phase(graph, "OSR availability analysis")
46 {
47 }
48
49 bool run()
50 {
51 ASSERT(m_graph.m_form == SSA);
52
53 for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
54 BasicBlock* block = m_graph.block(blockIndex);
55 if (!block)
56 continue;
57 block->ssa->availabilityAtHead.clear();
58 block->ssa->availabilityAtTail.clear();
59 }
60
61 BasicBlock* root = m_graph.block(0);
62 root->ssa->availabilityAtHead.m_locals.fill(Availability::unavailable());
63
64 for (unsigned argument = 0; argument < m_graph.block(0)->valuesAtHead.numberOfArguments(); ++argument)
65 root->ssa->availabilityAtHead.m_locals.argument(argument) = Availability::unavailable();
66
67 // This could be made more efficient by processing blocks in reverse postorder.
68
69 auto dumpAvailability = [] (BasicBlock* block) {
70 dataLogLn(block->ssa->availabilityAtHead);
71 dataLogLn(block->ssa->availabilityAtTail);
72 };
73
74 auto dumpBytecodeLivenessAtHead = [&] (BasicBlock* block) {
75 dataLog("Live: ");
76 m_graph.forAllLiveInBytecode(
77 block->at(0)->origin.forExit,
78 [&] (VirtualRegister reg) {
79 dataLog(reg, " ");
80 });
81 dataLogLn("");
82 };
83
84 LocalOSRAvailabilityCalculator calculator(m_graph);
85 bool changed;
86 do {
87 changed = false;
88
89 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
90 BasicBlock* block = m_graph.block(blockIndex);
91 if (!block)
92 continue;
93
94 if (DFGOSRAvailabilityAnalysisPhaseInternal::verbose) {
95 dataLogLn("Before changing Block #", block->index);
96 dumpAvailability(block);
97 }
98 calculator.beginBlock(block);
99
100 for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex)
101 calculator.executeNode(block->at(nodeIndex));
102
103 if (calculator.m_availability == block->ssa->availabilityAtTail)
104 continue;
105
106 block->ssa->availabilityAtTail = calculator.m_availability;
107 changed = true;
108
109 if (DFGOSRAvailabilityAnalysisPhaseInternal::verbose) {
110 dataLogLn("After changing Block #", block->index);
111 dumpAvailability(block);
112 }
113
114 for (unsigned successorIndex = block->numSuccessors(); successorIndex--;) {
115 BasicBlock* successor = block->successor(successorIndex);
116 successor->ssa->availabilityAtHead.merge(calculator.m_availability);
117 }
118
119 for (unsigned successorIndex = block->numSuccessors(); successorIndex--;) {
120 BasicBlock* successor = block->successor(successorIndex);
121 successor->ssa->availabilityAtHead.pruneByLiveness(
122 m_graph, successor->at(0)->origin.forExit);
123 if (DFGOSRAvailabilityAnalysisPhaseInternal::verbose) {
124 dataLogLn("After pruning Block #", successor->index);
125 dumpAvailability(successor);
126 dumpBytecodeLivenessAtHead(successor);
127 }
128 }
129 }
130 } while (changed);
131
132 if (validationEnabled()) {
133
134 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
135 BasicBlock* block = m_graph.block(blockIndex);
136 if (!block)
137 continue;
138
139 calculator.beginBlock(block);
140
141 for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
142 if (block->at(nodeIndex)->origin.exitOK) {
143 // If we're allowed to exit here, the heap must be in a state
144 // where exiting wouldn't crash. These particular fields are
145 // required for correctness because we use them during OSR exit
146 // to do meaningful things. It would be wrong for any of them
147 // to be dead.
148
149 AvailabilityMap availabilityMap = calculator.m_availability;
150 availabilityMap.pruneByLiveness(m_graph, block->at(nodeIndex)->origin.forExit);
151
152 for (auto heapPair : availabilityMap.m_heap) {
153 switch (heapPair.key.kind()) {
154 case ActivationScopePLoc:
155 case ActivationSymbolTablePLoc:
156 case FunctionActivationPLoc:
157 case FunctionExecutablePLoc:
158 case StructurePLoc:
159 if (heapPair.value.isDead()) {
160 dataLogLn("PromotedHeapLocation is dead, but should not be: ", heapPair.key);
161 availabilityMap.dump(WTF::dataFile());
162 CRASH();
163 }
164 break;
165
166 default:
167 break;
168 }
169 }
170 }
171
172 calculator.executeNode(block->at(nodeIndex));
173 }
174 }
175 }
176
177 return true;
178 }
179
180};
181
182bool performOSRAvailabilityAnalysis(Graph& graph)
183{
184 return runPhase<OSRAvailabilityAnalysisPhase>(graph);
185}
186
187LocalOSRAvailabilityCalculator::LocalOSRAvailabilityCalculator(Graph& graph)
188 : m_graph(graph)
189{
190}
191
192LocalOSRAvailabilityCalculator::~LocalOSRAvailabilityCalculator()
193{
194}
195
196void LocalOSRAvailabilityCalculator::beginBlock(BasicBlock* block)
197{
198 m_availability = block->ssa->availabilityAtHead;
199}
200
201void LocalOSRAvailabilityCalculator::endBlock(BasicBlock* block)
202{
203 m_availability = block->ssa->availabilityAtTail;
204}
205
206void LocalOSRAvailabilityCalculator::executeNode(Node* node)
207{
208 switch (node->op()) {
209 case PutStack: {
210 StackAccessData* data = node->stackAccessData();
211 m_availability.m_locals.operand(data->local).setFlush(data->flushedAt());
212 break;
213 }
214
215 case KillStack: {
216 m_availability.m_locals.operand(node->unlinkedLocal()).setFlush(FlushedAt(ConflictingFlush));
217 break;
218 }
219
220 case GetStack: {
221 StackAccessData* data = node->stackAccessData();
222 m_availability.m_locals.operand(data->local) = Availability(node, data->flushedAt());
223 break;
224 }
225
226 case MovHint: {
227 m_availability.m_locals.operand(node->unlinkedLocal()).setNode(node->child1().node());
228 break;
229 }
230
231 case ZombieHint: {
232 m_availability.m_locals.operand(node->unlinkedLocal()).setNodeUnavailable();
233 break;
234 }
235
236 case InitializeEntrypointArguments: {
237 unsigned entrypointIndex = node->entrypointIndex();
238 const Vector<FlushFormat>& argumentFormats = m_graph.m_argumentFormats[entrypointIndex];
239 for (unsigned argument = argumentFormats.size(); argument--; ) {
240 FlushedAt flushedAt = FlushedAt(argumentFormats[argument], virtualRegisterForArgument(argument));
241 m_availability.m_locals.argument(argument) = Availability(flushedAt);
242 }
243 break;
244 }
245
246 case LoadVarargs:
247 case ForwardVarargs: {
248 LoadVarargsData* data = node->loadVarargsData();
249 m_availability.m_locals.operand(data->count) =
250 Availability(FlushedAt(FlushedInt32, data->machineCount));
251 for (unsigned i = data->limit; i--;) {
252 m_availability.m_locals.operand(VirtualRegister(data->start.offset() + i)) =
253 Availability(FlushedAt(FlushedJSValue, VirtualRegister(data->machineStart.offset() + i)));
254 }
255 break;
256 }
257
258 case PhantomCreateRest:
259 case PhantomDirectArguments:
260 case PhantomClonedArguments: {
261 InlineCallFrame* inlineCallFrame = node->origin.semantic.inlineCallFrame();
262 if (!inlineCallFrame) {
263 // We don't need to record anything about how the arguments are to be recovered. It's just a
264 // given that we can read them from the stack.
265 break;
266 }
267
268 unsigned numberOfArgumentsToSkip = 0;
269 if (node->op() == PhantomCreateRest)
270 numberOfArgumentsToSkip = node->numberOfArgumentsToSkip();
271
272 if (inlineCallFrame->isVarargs()) {
273 // Record how to read each argument and the argument count.
274 Availability argumentCount =
275 m_availability.m_locals.operand(inlineCallFrame->stackOffset + CallFrameSlot::argumentCount);
276
277 m_availability.m_heap.set(PromotedHeapLocation(ArgumentCountPLoc, node), argumentCount);
278 }
279
280 if (inlineCallFrame->isClosureCall) {
281 Availability callee = m_availability.m_locals.operand(
282 inlineCallFrame->stackOffset + CallFrameSlot::callee);
283 m_availability.m_heap.set(PromotedHeapLocation(ArgumentsCalleePLoc, node), callee);
284 }
285
286 for (unsigned i = numberOfArgumentsToSkip; i < inlineCallFrame->argumentCountIncludingThis - 1; ++i) {
287 Availability argument = m_availability.m_locals.operand(
288 inlineCallFrame->stackOffset + CallFrame::argumentOffset(i));
289
290 m_availability.m_heap.set(PromotedHeapLocation(ArgumentPLoc, node, i), argument);
291 }
292 break;
293 }
294
295 case PutHint: {
296 m_availability.m_heap.set(
297 PromotedHeapLocation(node->child1().node(), node->promotedLocationDescriptor()),
298 Availability(node->child2().node()));
299 break;
300 }
301
302 case PhantomSpread:
303 m_availability.m_heap.set(PromotedHeapLocation(SpreadPLoc, node), Availability(node->child1().node()));
304 break;
305
306 case PhantomNewArrayWithSpread:
307 for (unsigned i = 0; i < node->numChildren(); i++) {
308 Node* child = m_graph.varArgChild(node, i).node();
309 m_availability.m_heap.set(PromotedHeapLocation(NewArrayWithSpreadArgumentPLoc, node, i), Availability(child));
310 }
311 break;
312
313 case PhantomNewArrayBuffer:
314 m_availability.m_heap.set(PromotedHeapLocation(NewArrayBufferPLoc, node), Availability(node->child1().node()));
315 break;
316
317 default:
318 break;
319 }
320}
321
322} } // namespace JSC::DFG
323
324#endif // ENABLE(DFG_JIT)
325
326