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() == SetArgumentDefinitely);
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 SetArgumentDefinitely:
238 case SetArgumentMaybe:
239 case PhantomLocal:
240 case Flush: {
241 // The block transfers the value from head to tail.
242 destination = variableAt(index);
243 break;
244 }
245
246 case GetLocal: {
247 // The block refines the value with additional speculations.
248 destination = forNode(node);
249
250 // We need to make sure that we don't broaden the type beyond what the flush
251 // format says it will be. The value may claim to have changed abstract state
252 // but it's type cannot change without a store. For example:
253 //
254 // Block #1:
255 // 0: GetLocal(loc42, FlushFormatInt32)
256 // 1: PutStructure(Check: Cell: @0, ArrayStructure)
257 // ...
258 // 2: Branch(T: #1, F: #2)
259 //
260 // In this case the AbstractState of @0 will say it's an SpecArray but the only
261 // reason that would have happened is because we would have exited the cell check.
262
263 FlushFormat flushFormat = node->variableAccessData()->flushFormat();
264 destination.filter(typeFilterFor(flushFormat));
265 break;
266 }
267 case SetLocal: {
268 // The block sets the variable, and potentially refines it, both
269 // before and after setting it. Since the SetLocal already did
270 // a type check based on the flush format's type, we're only interested
271 // in refinements within that type hierarchy. Otherwise, we may end up
272 // saying that any GetLocals reachable from this basic block load something
273 // outside of that hierarchy, e.g:
274 //
275 // a: JSConstant(jsNumber(0))
276 // b: SetLocal(Int32:@a, loc1, FlushedInt32)
277 // c: ArrayifyToStructure(Cell:@a)
278 // d: Jump(...)
279 //
280 // In this example, we can't trust whatever type ArrayifyToStructure sets
281 // @a to. We're only interested in the subset of that type that intersects
282 // with Int32.
283 AbstractValue value = forNode(node->child1());
284 value.filter(typeFilterFor(node->variableAccessData()->flushFormat()));
285 destination = value;
286 break;
287 }
288
289 default:
290 RELEASE_ASSERT_NOT_REACHED();
291 break;
292 }
293 }
294 break;
295 }
296
297 case SSA: {
298 for (size_t i = 0; i < block->valuesAtTail.size(); ++i) {
299 AbstractValue& destination = block->valuesAtTail[i];
300
301 if (!m_activeVariables[i]) {
302 destination = block->valuesAtHead[i];
303 destination.fastForwardFromTo(epochAtHead, currentEpoch);
304 continue;
305 }
306
307 block->valuesAtTail[i] = variableAt(i);
308 }
309
310 for (NodeAbstractValuePair& valueAtTail : block->ssa->valuesAtTail)
311 valueAtTail.value = forNode(valueAtTail.node);
312 break;
313 }
314
315 default:
316 RELEASE_ASSERT_NOT_REACHED();
317 }
318
319 reset();
320
321 return mergeToSuccessors(block);
322}
323
324void InPlaceAbstractState::reset()
325{
326 m_block = 0;
327 m_isValid = false;
328 m_branchDirection = InvalidBranchDirection;
329 m_structureClobberState = StructuresAreWatched;
330}
331
332void InPlaceAbstractState::activateVariable(size_t variableIndex)
333{
334 AbstractValue& value = m_variables[variableIndex];
335 value = m_block->valuesAtHead[variableIndex];
336 value.m_effectEpoch = m_epochAtHead;
337 m_activeVariables[variableIndex] = true;
338}
339
340bool InPlaceAbstractState::merge(BasicBlock* from, BasicBlock* to)
341{
342 if (DFGInPlaceAbstractStateInternal::verbose)
343 dataLog(" Merging from ", pointerDump(from), " to ", pointerDump(to), "\n");
344 ASSERT(from->variablesAtTail.numberOfArguments() == to->variablesAtHead.numberOfArguments());
345 ASSERT(from->variablesAtTail.numberOfLocals() == to->variablesAtHead.numberOfLocals());
346
347 bool changed = false;
348
349 changed |= checkAndSet(
350 to->cfaStructureClobberStateAtHead,
351 DFG::merge(from->cfaStructureClobberStateAtTail, to->cfaStructureClobberStateAtHead));
352
353 switch (m_graph.m_form) {
354 case ThreadedCPS: {
355 for (size_t argument = 0; argument < from->variablesAtTail.numberOfArguments(); ++argument) {
356 AbstractValue& destination = to->valuesAtHead.argument(argument);
357 changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.argument(argument), to->variablesAtHead.argument(argument), from->variablesAtTail.argument(argument));
358 }
359
360 for (size_t local = 0; local < from->variablesAtTail.numberOfLocals(); ++local) {
361 AbstractValue& destination = to->valuesAtHead.local(local);
362 changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.local(local), to->variablesAtHead.local(local), from->variablesAtTail.local(local));
363 }
364 break;
365 }
366
367 case SSA: {
368 for (size_t i = from->valuesAtTail.size(); i--;)
369 changed |= to->valuesAtHead[i].merge(from->valuesAtTail[i]);
370
371 for (NodeAbstractValuePair& entry : to->ssa->valuesAtHead) {
372 NodeFlowProjection node = entry.node;
373 if (DFGInPlaceAbstractStateInternal::verbose)
374 dataLog(" Merging for ", node, ": from ", forNode(node), " to ", entry.value, "\n");
375#ifndef NDEBUG
376 unsigned valueCountInFromBlock = 0;
377 for (NodeAbstractValuePair& fromBlockValueAtTail : from->ssa->valuesAtTail) {
378 if (fromBlockValueAtTail.node == node) {
379 ASSERT(fromBlockValueAtTail.value == forNode(node));
380 ++valueCountInFromBlock;
381 }
382 }
383 ASSERT(valueCountInFromBlock == 1);
384#endif
385
386 changed |= entry.value.merge(forNode(node));
387
388 if (DFGInPlaceAbstractStateInternal::verbose)
389 dataLog(" Result: ", entry.value, "\n");
390 }
391 break;
392 }
393
394 default:
395 RELEASE_ASSERT_NOT_REACHED();
396 break;
397 }
398
399 if (!to->cfaHasVisited)
400 changed = true;
401
402 if (DFGInPlaceAbstractStateInternal::verbose)
403 dataLog(" Will revisit: ", changed, "\n");
404 to->cfaShouldRevisit |= changed;
405
406 return changed;
407}
408
409inline bool InPlaceAbstractState::mergeToSuccessors(BasicBlock* basicBlock)
410{
411 Node* terminal = basicBlock->terminal();
412
413 ASSERT(terminal->isTerminal());
414
415 switch (terminal->op()) {
416 case Jump: {
417 ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
418 return merge(basicBlock, terminal->targetBlock());
419 }
420
421 case Branch: {
422 ASSERT(basicBlock->cfaBranchDirection != InvalidBranchDirection);
423 bool changed = false;
424 if (basicBlock->cfaBranchDirection != TakeFalse)
425 changed |= merge(basicBlock, terminal->branchData()->taken.block);
426 if (basicBlock->cfaBranchDirection != TakeTrue)
427 changed |= merge(basicBlock, terminal->branchData()->notTaken.block);
428 return changed;
429 }
430
431 case Switch: {
432 // FIXME: It would be cool to be sparse conditional for Switch's. Currently
433 // we're not. However I somehow doubt that this will ever be a big deal.
434 ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
435 SwitchData* data = terminal->switchData();
436 bool changed = merge(basicBlock, data->fallThrough.block);
437 for (unsigned i = data->cases.size(); i--;)
438 changed |= merge(basicBlock, data->cases[i].target.block);
439 return changed;
440 }
441
442 case EntrySwitch: {
443 EntrySwitchData* data = terminal->entrySwitchData();
444 bool changed = false;
445 for (unsigned i = data->cases.size(); i--;)
446 changed |= merge(basicBlock, data->cases[i]);
447 return changed;
448 }
449
450 case Return:
451 case TailCall:
452 case DirectTailCall:
453 case TailCallVarargs:
454 case TailCallForwardVarargs:
455 case Unreachable:
456 case Throw:
457 case ThrowStaticError:
458 ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
459 return false;
460
461 default:
462 RELEASE_ASSERT_NOT_REACHED();
463 return false;
464 }
465}
466
467inline bool InPlaceAbstractState::mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, Node* destinationNode, Node* sourceNode)
468{
469 if (!destinationNode)
470 return false;
471
472 ASSERT_UNUSED(sourceNode, sourceNode);
473
474 // FIXME: We could do some sparse conditional propagation here!
475
476 return destination.merge(source);
477}
478
479} } // namespace JSC::DFG
480
481#endif // ENABLE(DFG_JIT)
482
483