1/*
2 * Copyright (C) 2013-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 "DFGInPlaceAbstractState.h"
28
29#if ENABLE(DFG_JIT)
30
31#include "CodeBlock.h"
32#include "DFGBasicBlock.h"
33#include "GetByIdStatus.h"
34#include "JSCInlines.h"
35#include "PutByIdStatus.h"
36#include "StringObject.h"
37#include "SuperSampler.h"
38
39namespace JSC { namespace DFG {
40
41namespace DFGInPlaceAbstractStateInternal {
42static const bool verbose = false;
43}
44
45InPlaceAbstractState::InPlaceAbstractState(Graph& graph)
46 : m_graph(graph)
47 , m_abstractValues(*graph.m_abstractValuesCache)
48 , m_variables(m_graph.m_codeBlock->numParameters(), graph.m_localVars)
49 , m_block(0)
50{
51}
52
53InPlaceAbstractState::~InPlaceAbstractState() { }
54
55void InPlaceAbstractState::beginBasicBlock(BasicBlock* basicBlock)
56{
57 ASSERT(!m_block);
58
59 ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->valuesAtHead.numberOfLocals());
60 ASSERT(basicBlock->variablesAtTail.numberOfLocals() == basicBlock->valuesAtTail.numberOfLocals());
61 ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->variablesAtTail.numberOfLocals());
62
63 m_abstractValues.resize();
64
65 AbstractValueClobberEpoch epoch = AbstractValueClobberEpoch::first(basicBlock->cfaStructureClobberStateAtHead);
66 m_epochAtHead = epoch;
67 m_effectEpoch = epoch;
68
69 m_block = basicBlock;
70
71 m_activeVariables.clearRange(0, std::min(m_variables.size(), m_activeVariables.size()));
72 if (m_variables.size() > m_activeVariables.size())
73 m_activeVariables.resize(m_variables.size());
74
75 if (m_graph.m_form == SSA) {
76 for (NodeAbstractValuePair& entry : basicBlock->ssa->valuesAtHead) {
77 if (entry.node.isStillValid()) {
78 AbstractValue& value = m_abstractValues.at(entry.node);
79 value = entry.value;
80 value.m_effectEpoch = epoch;
81 }
82 }
83 }
84 basicBlock->cfaShouldRevisit = false;
85 basicBlock->cfaHasVisited = true;
86 m_isValid = true;
87 m_foundConstants = false;
88 m_branchDirection = InvalidBranchDirection;
89 m_structureClobberState = basicBlock->cfaStructureClobberStateAtHead;
90}
91
92static void setLiveValues(Vector<NodeAbstractValuePair>& values, const Vector<NodeFlowProjection>& live)
93{
94 values.shrink(0);
95 values.reserveCapacity(live.size());
96 for (NodeFlowProjection node : live)
97 values.uncheckedAppend(NodeAbstractValuePair { node, AbstractValue() });
98}
99
100Operands<AbstractValue>& InPlaceAbstractState::variablesForDebugging()
101{
102 activateAllVariables();
103 return m_variables;
104}
105
106void InPlaceAbstractState::activateAllVariables()
107{
108 for (size_t i = m_variables.size(); i--;)
109 activateVariableIfNecessary(i);
110}
111
112void InPlaceAbstractState::initialize()
113{
114 for (BasicBlock* entrypoint : m_graph.m_roots) {
115 entrypoint->cfaShouldRevisit = true;
116 entrypoint->cfaHasVisited = false;
117 entrypoint->cfaFoundConstants = false;
118 entrypoint->cfaStructureClobberStateAtHead = StructuresAreWatched;
119 entrypoint->cfaStructureClobberStateAtTail = StructuresAreWatched;
120
121 if (m_graph.m_form == SSA) {
122 for (size_t i = 0; i < entrypoint->valuesAtHead.numberOfArguments(); ++i) {
123 entrypoint->valuesAtHead.argument(i).clear();
124 entrypoint->valuesAtTail.argument(i).clear();
125 }
126 } else {
127 const ArgumentsVector& arguments = m_graph.m_rootToArguments.find(entrypoint)->value;
128 for (size_t i = 0; i < entrypoint->valuesAtHead.numberOfArguments(); ++i) {
129 entrypoint->valuesAtTail.argument(i).clear();
130
131 FlushFormat format;
132 Node* node = arguments[i];
133 if (!node)
134 format = FlushedJSValue;
135 else {
136 ASSERT(node->op() == SetArgument);
137 format = node->variableAccessData()->flushFormat();
138 }
139
140 switch (format) {
141 case FlushedInt32:
142 entrypoint->valuesAtHead.argument(i).setNonCellType(SpecInt32Only);
143 break;
144 case FlushedBoolean:
145 entrypoint->valuesAtHead.argument(i).setNonCellType(SpecBoolean);
146 break;
147 case FlushedCell:
148 entrypoint->valuesAtHead.argument(i).setType(m_graph, SpecCellCheck);
149 break;
150 case FlushedJSValue:
151 entrypoint->valuesAtHead.argument(i).makeBytecodeTop();
152 break;
153 default:
154 DFG_CRASH(m_graph, nullptr, "Bad flush format for argument");
155 break;
156 }
157 }
158 }
159
160 for (size_t i = 0; i < entrypoint->valuesAtHead.numberOfLocals(); ++i) {
161 entrypoint->valuesAtHead.local(i).clear();
162 entrypoint->valuesAtTail.local(i).clear();
163 }
164 }
165
166 for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
167 if (m_graph.isRoot(block)) {
168 // We bootstrapped the CFG roots above.
169 continue;
170 }
171
172 ASSERT(block->isReachable);
173 block->cfaShouldRevisit = false;
174 block->cfaHasVisited = false;
175 block->cfaFoundConstants = false;
176 block->cfaStructureClobberStateAtHead = StructuresAreWatched;
177 block->cfaStructureClobberStateAtTail = StructuresAreWatched;
178 for (size_t i = 0; i < block->valuesAtHead.numberOfArguments(); ++i) {
179 block->valuesAtHead.argument(i).clear();
180 block->valuesAtTail.argument(i).clear();
181 }
182 for (size_t i = 0; i < block->valuesAtHead.numberOfLocals(); ++i) {
183 block->valuesAtHead.local(i).clear();
184 block->valuesAtTail.local(i).clear();
185 }
186 }
187
188 if (m_graph.m_form == SSA) {
189 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
190 BasicBlock* block = m_graph.block(blockIndex);
191 if (!block)
192 continue;
193 setLiveValues(block->ssa->valuesAtHead, block->ssa->liveAtHead);
194 setLiveValues(block->ssa->valuesAtTail, block->ssa->liveAtTail);
195 }
196 }
197}
198
199bool InPlaceAbstractState::endBasicBlock()
200{
201 ASSERT(m_block);
202
203 BasicBlock* block = m_block; // Save the block for successor merging.
204
205 block->cfaFoundConstants = m_foundConstants;
206 block->cfaDidFinish = m_isValid;
207 block->cfaBranchDirection = m_branchDirection;
208
209 if (!m_isValid) {
210 reset();
211 return false;
212 }
213
214 AbstractValueClobberEpoch epochAtHead = m_epochAtHead;
215 AbstractValueClobberEpoch currentEpoch = m_effectEpoch;
216
217 block->cfaStructureClobberStateAtTail = m_structureClobberState;
218
219 switch (m_graph.m_form) {
220 case ThreadedCPS: {
221 ASSERT(block->variablesAtTail.size() == block->valuesAtTail.size());
222 ASSERT(block->variablesAtTail.size() == m_variables.size());
223 for (size_t index = m_variables.size(); index--;) {
224 Node* node = block->variablesAtTail[index];
225 if (!node)
226 continue;
227 AbstractValue& destination = block->valuesAtTail[index];
228
229 if (!m_activeVariables[index]) {
230 destination = block->valuesAtHead[index];
231 destination.fastForwardFromTo(epochAtHead, currentEpoch);
232 continue;
233 }
234
235 switch (node->op()) {
236 case Phi:
237 case SetArgument:
238 case PhantomLocal:
239 case Flush: {
240 // The block transfers the value from head to tail.
241 destination = variableAt(index);
242 break;
243 }
244
245 case GetLocal: {
246 // The block refines the value with additional speculations.
247 destination = forNode(node);
248
249 // We need to make sure that we don't broaden the type beyond what the flush
250 // format says it will be. The value may claim to have changed abstract state
251 // but it's type cannot change without a store. For example:
252 //
253 // Block #1:
254 // 0: GetLocal(loc42, FlushFormatInt32)
255 // 1: PutStructure(Check: Cell: @0, ArrayStructure)
256 // ...
257 // 2: Branch(T: #1, F: #2)
258 //
259 // In this case the AbstractState of @0 will say it's an SpecArray but the only
260 // reason that would have happened is because we would have exited the cell check.
261
262 FlushFormat flushFormat = node->variableAccessData()->flushFormat();
263 destination.filter(typeFilterFor(flushFormat));
264 break;
265 }
266 case SetLocal: {
267 // The block sets the variable, and potentially refines it, both
268 // before and after setting it. Since the SetLocal already did
269 // a type check based on the flush format's type, we're only interested
270 // in refinements within that type hierarchy. Otherwise, we may end up
271 // saying that any GetLocals reachable from this basic block load something
272 // outside of that hierarchy, e.g:
273 //
274 // a: JSConstant(jsNumber(0))
275 // b: SetLocal(Int32:@a, loc1, FlushedInt32)
276 // c: ArrayifyToStructure(Cell:@a)
277 // d: Jump(...)
278 //
279 // In this example, we can't trust whatever type ArrayifyToStructure sets
280 // @a to. We're only interested in the subset of that type that intersects
281 // with Int32.
282 AbstractValue value = forNode(node->child1());
283 value.filter(typeFilterFor(node->variableAccessData()->flushFormat()));
284 destination = value;
285 break;
286 }
287
288 default:
289 RELEASE_ASSERT_NOT_REACHED();
290 break;
291 }
292 }
293 break;
294 }
295
296 case SSA: {
297 for (size_t i = 0; i < block->valuesAtTail.size(); ++i) {
298 AbstractValue& destination = block->valuesAtTail[i];
299
300 if (!m_activeVariables[i]) {
301 destination = block->valuesAtHead[i];
302 destination.fastForwardFromTo(epochAtHead, currentEpoch);
303 continue;
304 }
305
306 block->valuesAtTail[i] = variableAt(i);
307 }
308
309 for (NodeAbstractValuePair& valueAtTail : block->ssa->valuesAtTail)
310 valueAtTail.value = forNode(valueAtTail.node);
311 break;
312 }
313
314 default:
315 RELEASE_ASSERT_NOT_REACHED();
316 }
317
318 reset();
319
320 return mergeToSuccessors(block);
321}
322
323void InPlaceAbstractState::reset()
324{
325 m_block = 0;
326 m_isValid = false;
327 m_branchDirection = InvalidBranchDirection;
328 m_structureClobberState = StructuresAreWatched;
329}
330
331void InPlaceAbstractState::activateVariable(size_t variableIndex)
332{
333 AbstractValue& value = m_variables[variableIndex];
334 value = m_block->valuesAtHead[variableIndex];
335 value.m_effectEpoch = m_epochAtHead;
336 m_activeVariables[variableIndex] = true;
337}
338
339bool InPlaceAbstractState::merge(BasicBlock* from, BasicBlock* to)
340{
341 if (DFGInPlaceAbstractStateInternal::verbose)
342 dataLog(" Merging from ", pointerDump(from), " to ", pointerDump(to), "\n");
343 ASSERT(from->variablesAtTail.numberOfArguments() == to->variablesAtHead.numberOfArguments());
344 ASSERT(from->variablesAtTail.numberOfLocals() == to->variablesAtHead.numberOfLocals());
345
346 bool changed = false;
347
348 changed |= checkAndSet(
349 to->cfaStructureClobberStateAtHead,
350 DFG::merge(from->cfaStructureClobberStateAtTail, to->cfaStructureClobberStateAtHead));
351
352 switch (m_graph.m_form) {
353 case ThreadedCPS: {
354 for (size_t argument = 0; argument < from->variablesAtTail.numberOfArguments(); ++argument) {
355 AbstractValue& destination = to->valuesAtHead.argument(argument);
356 changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.argument(argument), to->variablesAtHead.argument(argument), from->variablesAtTail.argument(argument));
357 }
358
359 for (size_t local = 0; local < from->variablesAtTail.numberOfLocals(); ++local) {
360 AbstractValue& destination = to->valuesAtHead.local(local);
361 changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.local(local), to->variablesAtHead.local(local), from->variablesAtTail.local(local));
362 }
363 break;
364 }
365
366 case SSA: {
367 for (size_t i = from->valuesAtTail.size(); i--;)
368 changed |= to->valuesAtHead[i].merge(from->valuesAtTail[i]);
369
370 for (NodeAbstractValuePair& entry : to->ssa->valuesAtHead) {
371 NodeFlowProjection node = entry.node;
372 if (DFGInPlaceAbstractStateInternal::verbose)
373 dataLog(" Merging for ", node, ": from ", forNode(node), " to ", entry.value, "\n");
374#ifndef NDEBUG
375 unsigned valueCountInFromBlock = 0;
376 for (NodeAbstractValuePair& fromBlockValueAtTail : from->ssa->valuesAtTail) {
377 if (fromBlockValueAtTail.node == node) {
378 ASSERT(fromBlockValueAtTail.value == forNode(node));
379 ++valueCountInFromBlock;
380 }
381 }
382 ASSERT(valueCountInFromBlock == 1);
383#endif
384
385 changed |= entry.value.merge(forNode(node));
386
387 if (DFGInPlaceAbstractStateInternal::verbose)
388 dataLog(" Result: ", entry.value, "\n");
389 }
390 break;
391 }
392
393 default:
394 RELEASE_ASSERT_NOT_REACHED();
395 break;
396 }
397
398 if (!to->cfaHasVisited)
399 changed = true;
400
401 if (DFGInPlaceAbstractStateInternal::verbose)
402 dataLog(" Will revisit: ", changed, "\n");
403 to->cfaShouldRevisit |= changed;
404
405 return changed;
406}
407
408inline bool InPlaceAbstractState::mergeToSuccessors(BasicBlock* basicBlock)
409{
410 Node* terminal = basicBlock->terminal();
411
412 ASSERT(terminal->isTerminal());
413
414 switch (terminal->op()) {
415 case Jump: {
416 ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
417 return merge(basicBlock, terminal->targetBlock());
418 }
419
420 case Branch: {
421 ASSERT(basicBlock->cfaBranchDirection != InvalidBranchDirection);
422 bool changed = false;
423 if (basicBlock->cfaBranchDirection != TakeFalse)
424 changed |= merge(basicBlock, terminal->branchData()->taken.block);
425 if (basicBlock->cfaBranchDirection != TakeTrue)
426 changed |= merge(basicBlock, terminal->branchData()->notTaken.block);
427 return changed;
428 }
429
430 case Switch: {
431 // FIXME: It would be cool to be sparse conditional for Switch's. Currently
432 // we're not. However I somehow doubt that this will ever be a big deal.
433 ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
434 SwitchData* data = terminal->switchData();
435 bool changed = merge(basicBlock, data->fallThrough.block);
436 for (unsigned i = data->cases.size(); i--;)
437 changed |= merge(basicBlock, data->cases[i].target.block);
438 return changed;
439 }
440
441 case EntrySwitch: {
442 EntrySwitchData* data = terminal->entrySwitchData();
443 bool changed = false;
444 for (unsigned i = data->cases.size(); i--;)
445 changed |= merge(basicBlock, data->cases[i]);
446 return changed;
447 }
448
449 case Return:
450 case TailCall:
451 case DirectTailCall:
452 case TailCallVarargs:
453 case TailCallForwardVarargs:
454 case Unreachable:
455 case Throw:
456 case ThrowStaticError:
457 ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
458 return false;
459
460 default:
461 RELEASE_ASSERT_NOT_REACHED();
462 return false;
463 }
464}
465
466inline bool InPlaceAbstractState::mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, Node* destinationNode, Node* sourceNode)
467{
468 if (!destinationNode)
469 return false;
470
471 ASSERT_UNUSED(sourceNode, sourceNode);
472
473 // FIXME: We could do some sparse conditional propagation here!
474
475 return destination.merge(source);
476}
477
478} } // namespace JSC::DFG
479
480#endif // ENABLE(DFG_JIT)
481
482