1/*
2 * Copyright (C) 2012-2016 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 "DFGValidate.h"
28
29#if ENABLE(DFG_JIT)
30
31#include "CodeBlockWithJITType.h"
32#include "DFGClobberize.h"
33#include "DFGClobbersExitState.h"
34#include "DFGDominators.h"
35#include "DFGMayExit.h"
36#include "JSCInlines.h"
37#include <wtf/Assertions.h>
38
39namespace JSC { namespace DFG {
40
41namespace {
42
43class Validate {
44public:
45 Validate(Graph& graph, GraphDumpMode graphDumpMode, CString graphDumpBeforePhase)
46 : m_graph(graph)
47 , m_graphDumpMode(graphDumpMode)
48 , m_graphDumpBeforePhase(graphDumpBeforePhase)
49 {
50 }
51
52 #define VALIDATE(context, assertion) do { \
53 if (!(assertion)) { \
54 startCrashing(); \
55 dataLogF("\n\n\nAt "); \
56 reportValidationContext context; \
57 dataLogF(": validation failed: %s (%s:%d).\n", #assertion, __FILE__, __LINE__); \
58 dumpGraphIfAppropriate(); \
59 WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #assertion); \
60 CRASH(); \
61 } \
62 } while (0)
63
64 #define V_EQUAL(context, left, right) do { \
65 if (left != right) { \
66 startCrashing(); \
67 dataLogF("\n\n\nAt "); \
68 reportValidationContext context; \
69 dataLogF(": validation failed: (%s = ", #left); \
70 dataLog(left); \
71 dataLogF(") == (%s = ", #right); \
72 dataLog(right); \
73 dataLogF(") (%s:%d).\n", __FILE__, __LINE__); \
74 dumpGraphIfAppropriate(); \
75 WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #left " == " #right); \
76 CRASH(); \
77 } \
78 } while (0)
79
80 #define notSet (static_cast<size_t>(-1))
81
82 void validate()
83 {
84 // NB. This code is not written for performance, since it is not intended to run
85 // in release builds.
86
87 VALIDATE((m_graph.block(0)), m_graph.isRoot(m_graph.block(0)));
88 VALIDATE((m_graph.block(0)), m_graph.block(0) == m_graph.m_roots[0]);
89
90 for (BasicBlock* block : m_graph.m_roots)
91 VALIDATE((block), block->predecessors.isEmpty());
92
93 // Validate that all local variables at the head of all entrypoints are dead.
94 for (BasicBlock* entrypoint : m_graph.m_roots) {
95 for (unsigned i = 0; i < entrypoint->variablesAtHead.numberOfLocals(); ++i)
96 V_EQUAL((virtualRegisterForLocal(i), entrypoint), static_cast<Node*>(nullptr), entrypoint->variablesAtHead.local(i));
97 }
98
99 // Validate ref counts and uses.
100 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
101 BasicBlock* block = m_graph.block(blockIndex);
102 if (!block)
103 continue;
104 VALIDATE((block), block->isReachable);
105 for (size_t i = 0; i < block->numNodes(); ++i)
106 m_myRefCounts.add(block->node(i), 0);
107 }
108 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
109 BasicBlock* block = m_graph.block(blockIndex);
110 if (!block)
111 continue;
112 for (size_t i = 0; i < block->numNodes(); ++i) {
113 Node* node = block->node(i);
114 m_acceptableNodes.add(node);
115 if (!node->shouldGenerate())
116 continue;
117 if (node->op() == Upsilon) {
118 VALIDATE((node), m_graph.m_form == SSA);
119 if (node->phi()->shouldGenerate())
120 m_myRefCounts.find(node)->value++;
121 }
122 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
123 // Phi children in LoadStore form are invalid.
124 if (m_graph.m_form == LoadStore && block->isPhiIndex(i))
125 continue;
126
127 Edge edge = m_graph.child(node, j);
128 if (!edge)
129 continue;
130
131 m_myRefCounts.find(edge.node())->value++;
132
133 validateEdgeWithDoubleResultIfNecessary(node, edge);
134 VALIDATE((node, edge), edge->hasInt52Result() == (edge.useKind() == Int52RepUse));
135
136 if (m_graph.m_form == SSA) {
137 // In SSA, all edges must hasResult().
138 VALIDATE((node, edge), edge->hasResult());
139 continue;
140 }
141
142 // Unless I'm a Flush, Phantom, GetLocal, or Phi, my children should hasResult().
143 switch (node->op()) {
144 case Flush:
145 case GetLocal:
146 VALIDATE((node, edge), edge->hasVariableAccessData(m_graph));
147 VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData());
148 break;
149 case PhantomLocal:
150 VALIDATE((node, edge), edge->hasVariableAccessData(m_graph));
151 VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData());
152 VALIDATE((node, edge), edge->op() != SetLocal);
153 break;
154 case Phi:
155 VALIDATE((node, edge), edge->hasVariableAccessData(m_graph));
156 if (m_graph.m_unificationState == LocallyUnified)
157 break;
158 VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData());
159 break;
160 default:
161 VALIDATE((node, edge), edge->hasResult());
162 break;
163 }
164 }
165 }
166 }
167
168 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
169 BasicBlock* block = m_graph.block(blockIndex);
170 if (!block)
171 continue;
172 for (size_t i = 0; i < block->numNodes(); ++i) {
173 Node* node = block->node(i);
174 if (m_graph.m_refCountState == ExactRefCount)
175 V_EQUAL((node), m_myRefCounts.get(node), node->adjustedRefCount());
176 }
177
178 bool foundTerminal = false;
179 for (size_t i = 0 ; i < block->size(); ++i) {
180 Node* node = block->at(i);
181 if (node->isTerminal()) {
182 foundTerminal = true;
183 for (size_t j = i + 1; j < block->size(); ++j) {
184 node = block->at(j);
185 VALIDATE((node), node->op() == Phantom || node->op() == PhantomLocal || node->op() == Flush || node->op() == Check);
186 m_graph.doToChildren(
187 node,
188 [&] (Edge edge) {
189 VALIDATE((node, edge), shouldNotHaveTypeCheck(edge.useKind()));
190 });
191 }
192 break;
193 }
194 }
195 VALIDATE((block), foundTerminal);
196
197 for (size_t i = 0; i < block->size(); ++i) {
198 Node* node = block->at(i);
199
200 VALIDATE((node), node->origin.isSet());
201 VALIDATE((node), node->origin.semantic.isSet() == node->origin.forExit.isSet());
202 VALIDATE((node), !(!node->origin.forExit.isSet() && node->origin.exitOK));
203 VALIDATE((node), !(mayExit(m_graph, node) == Exits && !node->origin.exitOK));
204
205 if (i) {
206 Node* previousNode = block->at(i - 1);
207 VALIDATE(
208 (node),
209 !clobbersExitState(m_graph, previousNode)
210 || !node->origin.exitOK
211 || node->op() == ExitOK
212 || node->origin.forExit != previousNode->origin.forExit);
213 VALIDATE(
214 (node),
215 !(!previousNode->origin.exitOK && node->origin.exitOK)
216 || node->op() == ExitOK
217 || node->origin.forExit != previousNode->origin.forExit);
218 }
219
220 VALIDATE((node), !node->hasStructure() || !!node->structure().get());
221 VALIDATE((node), !node->hasCellOperand() || node->cellOperand()->value().isCell());
222 VALIDATE((node), !node->hasCellOperand() || !!node->cellOperand()->value());
223
224 if (!(node->flags() & NodeHasVarArgs)) {
225 if (!node->child2())
226 VALIDATE((node), !node->child3());
227 if (!node->child1())
228 VALIDATE((node), !node->child2());
229 }
230
231 switch (node->op()) {
232 case Identity:
233 case IdentityWithProfile:
234 VALIDATE((node), canonicalResultRepresentation(node->result()) == canonicalResultRepresentation(node->child1()->result()));
235 break;
236 case SetLocal:
237 case PutStack:
238 case Upsilon:
239 VALIDATE((node), !!node->child1());
240 switch (node->child1().useKind()) {
241 case UntypedUse:
242 case CellUse:
243 case KnownCellUse:
244 case Int32Use:
245 case KnownInt32Use:
246 case Int52RepUse:
247 case DoubleRepUse:
248 case BooleanUse:
249 case KnownBooleanUse:
250 break;
251 default:
252 VALIDATE((node), !"Bad use kind");
253 break;
254 }
255 break;
256 case MakeRope:
257 case ValueAdd:
258 case ValueSub:
259 case ValueMul:
260 case ValueDiv:
261 case ValueMod:
262 case ValuePow:
263 case ArithAdd:
264 case ArithSub:
265 case ArithMul:
266 case ArithIMul:
267 case ArithDiv:
268 case ArithMod:
269 case ArithMin:
270 case ArithMax:
271 case ArithPow:
272 case CompareLess:
273 case CompareLessEq:
274 case CompareGreater:
275 case CompareGreaterEq:
276 case CompareBelow:
277 case CompareBelowEq:
278 case CompareEq:
279 case CompareStrictEq:
280 case SameValue:
281 case StrCat:
282 VALIDATE((node), !!node->child1());
283 VALIDATE((node), !!node->child2());
284 break;
285 case CompareEqPtr:
286 VALIDATE((node), !!node->child1());
287 VALIDATE((node), !!node->cellOperand()->value() && node->cellOperand()->value().isCell());
288 break;
289 case CheckStructureOrEmpty:
290 VALIDATE((node), is64Bit());
291 VALIDATE((node), !!node->child1());
292 VALIDATE((node), node->child1().useKind() == CellUse);
293 break;
294 case CheckStructure:
295 case StringFromCharCode:
296 VALIDATE((node), !!node->child1());
297 break;
298 case PutStructure:
299 VALIDATE((node), !node->transition()->previous->dfgShouldWatch());
300 break;
301 case MultiPutByOffset:
302 for (unsigned i = node->multiPutByOffsetData().variants.size(); i--;) {
303 const PutByIdVariant& variant = node->multiPutByOffsetData().variants[i];
304 if (variant.kind() != PutByIdVariant::Transition)
305 continue;
306 VALIDATE((node), !variant.oldStructureForTransition()->dfgShouldWatch());
307 }
308 break;
309 case MaterializeNewObject:
310 for (RegisteredStructure structure : node->structureSet()) {
311 // This only supports structures that are JSFinalObject or JSArray.
312 VALIDATE(
313 (node),
314 structure->classInfo() == JSFinalObject::info()
315 || structure->classInfo() == JSArray::info());
316
317 // We only support certain indexing shapes.
318 VALIDATE((node), !hasAnyArrayStorage(structure->indexingType()));
319 }
320 break;
321 case DoubleConstant:
322 case Int52Constant:
323 VALIDATE((node), node->isNumberConstant());
324 break;
325 case GetByOffset:
326 case PutByOffset:
327 // FIXME: We should be able to validate that GetByOffset and PutByOffset are
328 // using the same object for storage and base. I think this means finally
329 // splitting these nodes into two node types, one for inline and one for
330 // out-of-line. The out-of-line one will require that the first node is storage,
331 // while the inline one will not take a storage child at all.
332 // https://bugs.webkit.org/show_bug.cgi?id=159602
333 break;
334 case HasOwnProperty: {
335 VALIDATE((node), !!m_graph.m_vm.hasOwnPropertyCache());
336 break;
337 }
338 case GetVectorLength: {
339 Array::Type type = node->arrayMode().type();
340 VALIDATE((node), type == Array::ArrayStorage || type == Array::SlowPutArrayStorage);
341 break;
342 }
343 case CPUIntrinsic: {
344 switch (node->intrinsic()) {
345 case CPUMfenceIntrinsic:
346 case CPURdtscIntrinsic:
347 case CPUCpuidIntrinsic:
348 case CPUPauseIntrinsic:
349 break;
350 default:
351 VALIDATE((node), false);
352 break;
353 }
354 break;
355 }
356 case GetArgumentCountIncludingThis: {
357 if (InlineCallFrame* inlineCallFrame = node->argumentsInlineCallFrame())
358 VALIDATE((node), inlineCallFrame->isVarargs());
359 break;
360 }
361 case NewArray:
362 VALIDATE((node), node->vectorLengthHint() >= node->numChildren());
363 break;
364 case NewArrayBuffer:
365 VALIDATE((node), node->vectorLengthHint() >= node->castOperand<JSImmutableButterfly*>()->length());
366 break;
367 default:
368 break;
369 }
370 }
371 }
372
373 switch (m_graph.m_form) {
374 case LoadStore:
375 case ThreadedCPS:
376 validateCPS();
377 break;
378
379 case SSA:
380 validateSSA();
381 break;
382 }
383
384 // Validate clobbered states.
385 struct DefLambdaAdaptor {
386 Function<void(PureValue)> pureValue;
387 Function<void(HeapLocation, LazyNode)> locationAndNode;
388
389 void operator()(PureValue value) const
390 {
391 pureValue(value);
392 }
393
394 void operator()(HeapLocation location, LazyNode node) const
395 {
396 locationAndNode(location, node);
397 }
398 };
399 for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
400 for (Node* node : *block) {
401 clobberize(m_graph, node,
402 [&] (AbstractHeap) { },
403 [&] (AbstractHeap heap)
404 {
405 // CSE assumes that HEAP TOP is never written.
406 // If this assumption is weakened, you need to update clobbering
407 // in CSE accordingly.
408 if (heap.kind() == Stack)
409 VALIDATE((node), !heap.payload().isTop());
410 },
411 DefLambdaAdaptor {
412 [&] (PureValue) { },
413 [&] (HeapLocation location, LazyNode)
414 {
415 VALIDATE((node), location.heap().kind() != SideState);
416
417 // More specific kinds should be used instead.
418 VALIDATE((node), location.heap().kind() != World);
419 VALIDATE((node), location.heap().kind() != Heap);
420 }
421 });
422 }
423 }
424
425 for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
426 // We expect the predecessor list to be de-duplicated.
427 HashSet<BasicBlock*> predecessors;
428 for (BasicBlock* predecessor : block->predecessors)
429 predecessors.add(predecessor);
430 VALIDATE((block), predecessors.size() == block->predecessors.size());
431 }
432 }
433
434private:
435 Graph& m_graph;
436 GraphDumpMode m_graphDumpMode;
437 CString m_graphDumpBeforePhase;
438
439 HashMap<Node*, unsigned> m_myRefCounts;
440 HashSet<Node*> m_acceptableNodes;
441
442 void validateCPS()
443 {
444 VALIDATE((), !m_graph.m_rootToArguments.isEmpty()); // We should have at least one root.
445 VALIDATE((), m_graph.m_rootToArguments.size() == m_graph.m_roots.size());
446 for (BasicBlock* root : m_graph.m_rootToArguments.keys())
447 VALIDATE((), m_graph.m_roots.contains(root));
448
449 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
450 BasicBlock* block = m_graph.block(blockIndex);
451 if (!block)
452 continue;
453
454 HashSet<Node*> phisInThisBlock;
455 HashSet<Node*> nodesInThisBlock;
456
457 for (size_t i = 0; i < block->numNodes(); ++i) {
458 Node* node = block->node(i);
459 nodesInThisBlock.add(node);
460 if (block->isPhiIndex(i))
461 phisInThisBlock.add(node);
462 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
463 Edge edge = m_graph.child(node, j);
464 if (!edge)
465 continue;
466 VALIDATE((node, edge), m_acceptableNodes.contains(edge.node()));
467 }
468 }
469
470 {
471 HashSet<Node*> seenNodes;
472 for (size_t i = 0; i < block->size(); ++i) {
473 Node* node = block->at(i);
474 m_graph.doToChildren(node, [&] (const Edge& edge) {
475 Node* child = edge.node();
476 VALIDATE((node), block->isInPhis(child) || seenNodes.contains(child));
477 });
478 seenNodes.add(node);
479 }
480 }
481
482 for (size_t i = 0; i < block->phis.size(); ++i) {
483 Node* node = block->phis[i];
484 ASSERT(phisInThisBlock.contains(node));
485 VALIDATE((node), node->op() == Phi);
486 VirtualRegister local = node->local();
487 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
488 // Phi children in LoadStore form are invalid.
489 if (m_graph.m_form == LoadStore && block->isPhiIndex(i))
490 continue;
491
492 Edge edge = m_graph.child(node, j);
493 if (!edge)
494 continue;
495
496 VALIDATE(
497 (node, edge),
498 edge->op() == SetLocal
499 || edge->op() == SetArgumentDefinitely
500 || edge->op() == SetArgumentMaybe
501 || edge->op() == Phi);
502
503 if (phisInThisBlock.contains(edge.node()))
504 continue;
505
506 if (nodesInThisBlock.contains(edge.node())) {
507 VALIDATE(
508 (node, edge),
509 edge->op() == SetLocal
510 || edge->op() == SetArgumentDefinitely
511 || edge->op() == SetArgumentMaybe);
512
513 continue;
514 }
515
516 // There must exist a predecessor block that has this node index in
517 // its tail variables.
518 bool found = false;
519 for (unsigned k = 0; k < block->predecessors.size(); ++k) {
520 BasicBlock* prevBlock = block->predecessors[k];
521 VALIDATE((block->predecessors[k]), prevBlock);
522 Node* prevNode = prevBlock->variablesAtTail.operand(local);
523 // If we have a Phi that is not referring to *this* block then all predecessors
524 // must have that local available.
525 VALIDATE((local, block, block->predecessors[k]), prevNode);
526 switch (prevNode->op()) {
527 case GetLocal:
528 case Flush:
529 case PhantomLocal:
530 prevNode = prevNode->child1().node();
531 break;
532 default:
533 break;
534 }
535 if (node->shouldGenerate()) {
536 VALIDATE((local, block->predecessors[k], prevNode),
537 prevNode->shouldGenerate());
538 }
539 VALIDATE(
540 (local, block->predecessors[k], prevNode),
541 prevNode->op() == SetLocal
542 || prevNode->op() == SetArgumentDefinitely
543 || prevNode->op() == SetArgumentMaybe
544 || prevNode->op() == Phi);
545 if (prevNode == edge.node()) {
546 found = true;
547 break;
548 }
549 // At this point it cannot refer into this block.
550 VALIDATE((local, block->predecessors[k], prevNode), !prevBlock->isInBlock(edge.node()));
551 }
552
553 VALIDATE((node, edge), found);
554 }
555 }
556
557 Operands<size_t> getLocalPositions(
558 block->variablesAtHead.numberOfArguments(),
559 block->variablesAtHead.numberOfLocals());
560 Operands<size_t> setLocalPositions(
561 block->variablesAtHead.numberOfArguments(),
562 block->variablesAtHead.numberOfLocals());
563
564 for (size_t i = 0; i < block->variablesAtHead.numberOfArguments(); ++i) {
565 VALIDATE((virtualRegisterForArgument(i), block), !block->variablesAtHead.argument(i) || block->variablesAtHead.argument(i)->accessesStack(m_graph));
566 if (m_graph.m_form == ThreadedCPS)
567 VALIDATE((virtualRegisterForArgument(i), block), !block->variablesAtTail.argument(i) || block->variablesAtTail.argument(i)->accessesStack(m_graph));
568
569 getLocalPositions.argument(i) = notSet;
570 setLocalPositions.argument(i) = notSet;
571 }
572 for (size_t i = 0; i < block->variablesAtHead.numberOfLocals(); ++i) {
573 VALIDATE((virtualRegisterForLocal(i), block), !block->variablesAtHead.local(i) || block->variablesAtHead.local(i)->accessesStack(m_graph));
574 if (m_graph.m_form == ThreadedCPS)
575 VALIDATE((virtualRegisterForLocal(i), block), !block->variablesAtTail.local(i) || block->variablesAtTail.local(i)->accessesStack(m_graph));
576
577 getLocalPositions.local(i) = notSet;
578 setLocalPositions.local(i) = notSet;
579 }
580
581 for (size_t i = 0; i < block->size(); ++i) {
582 Node* node = block->at(i);
583 ASSERT(nodesInThisBlock.contains(node));
584 VALIDATE((node), node->op() != Phi);
585 VALIDATE((node), node->origin.forExit.isSet());
586 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
587 Edge edge = m_graph.child(node, j);
588 if (!edge)
589 continue;
590 VALIDATE((node, edge), nodesInThisBlock.contains(edge.node()));
591 switch (node->op()) {
592 case PhantomLocal:
593 case GetLocal:
594 case Flush:
595 break;
596 default:
597 VALIDATE((node, edge), !phisInThisBlock.contains(edge.node()));
598 break;
599 }
600 }
601
602 switch (node->op()) {
603 case Phi:
604 case Upsilon:
605 case CheckInBounds:
606 case PhantomNewObject:
607 case PhantomNewFunction:
608 case PhantomNewGeneratorFunction:
609 case PhantomNewAsyncFunction:
610 case PhantomNewAsyncGeneratorFunction:
611 case PhantomCreateActivation:
612 case PhantomNewRegexp:
613 case GetMyArgumentByVal:
614 case GetMyArgumentByValOutOfBounds:
615 case PutHint:
616 case CheckStructureImmediate:
617 case MaterializeCreateActivation:
618 case PutStack:
619 case KillStack:
620 case GetStack:
621 case EntrySwitch:
622 case InitializeEntrypointArguments:
623 VALIDATE((node), !"unexpected node type in CPS");
624 break;
625 case MaterializeNewObject: {
626 // CPS only allows array lengths to be constant. This constraint only exists
627 // because we don't have DFG support for anything more and we don't need any
628 // other kind of support for now.
629 ObjectMaterializationData& data = node->objectMaterializationData();
630 for (unsigned i = data.m_properties.size(); i--;) {
631 PromotedLocationDescriptor descriptor = data.m_properties[i];
632 Edge edge = m_graph.varArgChild(node, 1 + i);
633 switch (descriptor.kind()) {
634 case PublicLengthPLoc:
635 case VectorLengthPLoc:
636 VALIDATE((node, edge), edge->isInt32Constant());
637 break;
638 default:
639 break;
640 }
641 }
642
643 // CPS only allows one structure.
644 VALIDATE((node), node->structureSet().size() == 1);
645
646 // CPS disallows int32 and double arrays. Those require weird type checks and
647 // conversions. They are not needed in the DFG right now. We should add support
648 // for these if the DFG ever needs it.
649 for (RegisteredStructure structure : node->structureSet()) {
650 VALIDATE((node), !hasInt32(structure->indexingType()));
651 VALIDATE((node), !hasDouble(structure->indexingType()));
652 }
653 break;
654 }
655 case Phantom:
656 VALIDATE((node), m_graph.m_fixpointState != FixpointNotConverged);
657 break;
658 default:
659 break;
660 }
661
662 if (!node->shouldGenerate())
663 continue;
664 switch (node->op()) {
665 case GetLocal:
666 // Ignore GetLocal's that we know to be dead, but that the graph
667 // doesn't yet know to be dead.
668 if (!m_myRefCounts.get(node))
669 break;
670 if (m_graph.m_form == ThreadedCPS) {
671 VALIDATE((node, block), getLocalPositions.operand(node->local()) == notSet);
672 VALIDATE((node, block), !!node->child1());
673 VALIDATE((node, block), node->child1()->op() == SetArgumentDefinitely || node->child1()->op() == Phi);
674 }
675 getLocalPositions.operand(node->local()) = i;
676 break;
677 case SetLocal:
678 // Only record the first SetLocal. There may be multiple SetLocals
679 // because of flushing.
680 if (setLocalPositions.operand(node->local()) != notSet)
681 break;
682 setLocalPositions.operand(node->local()) = i;
683 break;
684 case SetArgumentDefinitely:
685 // This acts like a reset. It's ok to have a second GetLocal for a local in the same
686 // block if we had a SetArgumentDefinitely for that local.
687 getLocalPositions.operand(node->local()) = notSet;
688 setLocalPositions.operand(node->local()) = notSet;
689 break;
690 case SetArgumentMaybe:
691 break;
692 case Flush:
693 case PhantomLocal:
694 if (m_graph.m_form == ThreadedCPS) {
695 VALIDATE((node, block),
696 node->child1()->op() == Phi
697 || node->child1()->op() == SetLocal
698 || node->child1()->op() == SetArgumentDefinitely
699 || node->child1()->op() == SetArgumentMaybe);
700 if (node->op() == PhantomLocal)
701 VALIDATE((node, block), node->child1()->op() != SetArgumentMaybe);
702 }
703 break;
704 default:
705 break;
706 }
707 }
708
709 if (m_graph.m_form == LoadStore)
710 continue;
711
712 for (size_t i = 0; i < block->variablesAtHead.numberOfArguments(); ++i) {
713 checkOperand(
714 block, getLocalPositions, setLocalPositions, virtualRegisterForArgument(i));
715 }
716 for (size_t i = 0; i < block->variablesAtHead.numberOfLocals(); ++i) {
717 checkOperand(
718 block, getLocalPositions, setLocalPositions, virtualRegisterForLocal(i));
719 }
720 }
721
722 if (m_graph.m_form == ThreadedCPS) {
723 Vector<Node*> worklist;
724 HashSet<Node*> seen;
725 for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
726 for (Node* node : *block) {
727 if (node->op() == GetLocal || node->op() == PhantomLocal) {
728 worklist.append(node);
729 auto addResult = seen.add(node);
730 VALIDATE((node, block), addResult.isNewEntry);
731 }
732 }
733 }
734
735 while (worklist.size()) {
736 Node* node = worklist.takeLast();
737 switch (node->op()) {
738 case PhantomLocal:
739 case GetLocal: {
740 Node* child = node->child1().node();
741 if (seen.add(child).isNewEntry)
742 worklist.append(child);
743 break;
744 }
745 case Phi: {
746 for (unsigned i = 0; i < m_graph.numChildren(node); ++i) {
747 Edge edge = m_graph.child(node, i);
748 if (!edge)
749 continue;
750 if (seen.add(edge.node()).isNewEntry)
751 worklist.append(edge.node());
752 }
753 break;
754 }
755 case SetLocal:
756 case SetArgumentDefinitely:
757 break;
758 case SetArgumentMaybe:
759 VALIDATE((node), !"Should not reach SetArgumentMaybe. GetLocal that has data flow that reaches a SetArgumentMaybe is invalid IR.");
760 break;
761 default:
762 VALIDATE((node), !"Unexpected node type.");
763 break;
764 }
765 }
766 }
767 }
768
769 void validateSSA()
770 {
771 // FIXME: Add more things here.
772 // https://bugs.webkit.org/show_bug.cgi?id=123471
773
774 VALIDATE((), m_graph.m_roots.size() == 1);
775 VALIDATE((), m_graph.m_roots[0] == m_graph.block(0));
776 VALIDATE((), !m_graph.m_argumentFormats.isEmpty()); // We always have at least one entrypoint.
777 VALIDATE((), m_graph.m_rootToArguments.isEmpty()); // This is only used in CPS.
778
779 m_graph.initializeNodeOwners();
780
781 auto& dominators = m_graph.ensureSSADominators();
782
783 for (unsigned entrypointIndex : m_graph.m_entrypointIndexToCatchBytecodeIndex.keys())
784 VALIDATE((), entrypointIndex > 0); // By convention, 0 is the entrypoint index for the op_enter entrypoint, which can not be in a catch.
785
786 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
787 BasicBlock* block = m_graph.block(blockIndex);
788 if (!block)
789 continue;
790
791 VALIDATE((block), block->phis.isEmpty());
792
793 bool didSeeExitOK = false;
794 bool isOSRExited = false;
795
796 HashSet<Node*> nodesInThisBlock;
797
798 for (auto* node : *block) {
799 didSeeExitOK |= node->origin.exitOK;
800 switch (node->op()) {
801 case Phi:
802 // Phi cannot exit, and it would be wrong to hoist anything to the Phi that could
803 // exit.
804 VALIDATE((node), !node->origin.exitOK);
805
806 // It never makes sense to have exitOK anywhere in the block before a Phi. It's only
807 // OK to exit after all Phis are done.
808 VALIDATE((node), !didSeeExitOK);
809 break;
810
811 case GetLocal:
812 case SetLocal:
813 case SetArgumentDefinitely:
814 case SetArgumentMaybe:
815 case Phantom:
816 VALIDATE((node), !"bad node type for SSA");
817 break;
818
819 default:
820 // FIXME: Add more things here.
821 // https://bugs.webkit.org/show_bug.cgi?id=123471
822 break;
823 }
824
825 if (isOSRExited)
826 continue;
827 switch (node->op()) {
828 case PhantomNewObject:
829 case PhantomNewFunction:
830 case PhantomNewGeneratorFunction:
831 case PhantomNewAsyncFunction:
832 case PhantomNewAsyncGeneratorFunction:
833 case PhantomCreateActivation:
834 case PhantomDirectArguments:
835 case PhantomCreateRest:
836 case PhantomClonedArguments:
837 case PhantomNewRegexp:
838 case MovHint:
839 case Upsilon:
840 case ForwardVarargs:
841 case CallForwardVarargs:
842 case TailCallForwardVarargs:
843 case TailCallForwardVarargsInlinedCaller:
844 case ConstructForwardVarargs:
845 case GetMyArgumentByVal:
846 case GetMyArgumentByValOutOfBounds:
847 break;
848
849 case Check:
850 case CheckVarargs:
851 // FIXME: This is probably not correct.
852 break;
853
854 case PutHint:
855 VALIDATE((node), node->child1()->isPhantomAllocation());
856 break;
857
858 case PhantomSpread:
859 VALIDATE((node), m_graph.m_form == SSA);
860 // We currently support PhantomSpread over PhantomCreateRest and PhantomNewArrayBuffer.
861 VALIDATE((node), node->child1()->op() == PhantomCreateRest || node->child1()->op() == PhantomNewArrayBuffer);
862 break;
863
864 case PhantomNewArrayWithSpread: {
865 VALIDATE((node), m_graph.m_form == SSA);
866 BitVector* bitVector = node->bitVector();
867 for (unsigned i = 0; i < node->numChildren(); i++) {
868 Node* child = m_graph.varArgChild(node, i).node();
869 if (bitVector->get(i)) {
870 // We currently support PhantomSpread over PhantomCreateRest and PhantomNewArrayBuffer.
871 VALIDATE((node), child->op() == PhantomSpread);
872 } else
873 VALIDATE((node), !child->isPhantomAllocation());
874 }
875 break;
876 }
877
878 case PhantomNewArrayBuffer:
879 VALIDATE((node), m_graph.m_form == SSA);
880 VALIDATE((node), node->vectorLengthHint() >= node->castOperand<JSImmutableButterfly*>()->length());
881 break;
882
883 case NewArrayWithSpread: {
884 BitVector* bitVector = node->bitVector();
885 for (unsigned i = 0; i < node->numChildren(); i++) {
886 Node* child = m_graph.varArgChild(node, i).node();
887 if (child->isPhantomAllocation()) {
888 VALIDATE((node), bitVector->get(i));
889 VALIDATE((node), m_graph.m_form == SSA);
890 VALIDATE((node), child->op() == PhantomSpread);
891 }
892 }
893 break;
894 }
895
896 case Spread:
897 VALIDATE((node), !node->child1()->isPhantomAllocation() || node->child1()->op() == PhantomCreateRest || node->child1()->op() == PhantomNewArrayBuffer);
898 break;
899
900 case EntrySwitch:
901 VALIDATE((node), node->entrySwitchData()->cases.size() == m_graph.m_numberOfEntrypoints);
902 break;
903
904 case InitializeEntrypointArguments:
905 VALIDATE((node), node->entrypointIndex() < m_graph.m_numberOfEntrypoints);
906 break;
907
908 default:
909 m_graph.doToChildren(
910 node,
911 [&] (const Edge& edge) {
912 VALIDATE((node), !edge->isPhantomAllocation());
913 });
914 break;
915 }
916
917 isOSRExited |= node->isPseudoTerminal();
918
919 m_graph.doToChildren(node, [&] (Edge child) {
920 VALIDATE((node), dominators.strictlyDominates(child->owner, block) || nodesInThisBlock.contains(child.node()));
921 });
922 nodesInThisBlock.add(node);
923 }
924 }
925 }
926
927 void validateEdgeWithDoubleResultIfNecessary(Node* node, Edge edge)
928 {
929 if (!edge->hasDoubleResult())
930 return;
931
932 if (m_graph.m_planStage < PlanStage::AfterFixup)
933 return;
934
935 VALIDATE((node, edge), edge.useKind() == DoubleRepUse || edge.useKind() == DoubleRepRealUse || edge.useKind() == DoubleRepAnyIntUse);
936 }
937
938 void checkOperand(
939 BasicBlock* block, Operands<size_t>& getLocalPositions,
940 Operands<size_t>& setLocalPositions, VirtualRegister operand)
941 {
942 if (getLocalPositions.operand(operand) == notSet)
943 return;
944 if (setLocalPositions.operand(operand) == notSet)
945 return;
946
947 VALIDATE(
948 (block->at(getLocalPositions.operand(operand)),
949 block->at(setLocalPositions.operand(operand)),
950 block),
951 getLocalPositions.operand(operand) < setLocalPositions.operand(operand));
952 }
953
954 void reportValidationContext() { }
955
956 void reportValidationContext(Node* node)
957 {
958 dataLogF("@%u", node->index());
959 }
960
961 void reportValidationContext(BasicBlock* block)
962 {
963 dataLog("Block ", *block);
964 }
965
966 void reportValidationContext(Node* node, Edge edge)
967 {
968 dataLog(node, " -> ", edge);
969 }
970
971 void reportValidationContext(VirtualRegister local, BasicBlock* block)
972 {
973 if (!block) {
974 dataLog(local, " in null Block ");
975 return;
976 }
977
978 dataLog(local, " in Block ", *block);
979 }
980
981 void reportValidationContext(
982 VirtualRegister local, BasicBlock* sourceBlock, BasicBlock* destinationBlock)
983 {
984 dataLog(local, " in Block ", *sourceBlock, " -> ", *destinationBlock);
985 }
986
987 void reportValidationContext(
988 VirtualRegister local, BasicBlock* sourceBlock, Node* prevNode)
989 {
990 dataLog(prevNode, " for ", local, " in Block ", *sourceBlock);
991 }
992
993 void reportValidationContext(Node* node, BasicBlock* block)
994 {
995 dataLog(node, " in Block ", *block);
996 }
997
998 void reportValidationContext(Node* node, Node* node2, BasicBlock* block)
999 {
1000 dataLog(node, " and ", node2, " in Block ", *block);
1001 }
1002
1003 void reportValidationContext(
1004 Node* node, BasicBlock* block, Node* expectedNode, Edge incomingEdge)
1005 {
1006 dataLog(node, " in Block ", *block, ", searching for ", expectedNode, " from ", incomingEdge);
1007 }
1008
1009 void dumpGraphIfAppropriate()
1010 {
1011 if (m_graphDumpMode == DontDumpGraph)
1012 return;
1013 dataLog("\n");
1014 if (!m_graphDumpBeforePhase.isNull()) {
1015 dataLog("Before phase:\n");
1016 dataLog(m_graphDumpBeforePhase);
1017 }
1018 dataLog("At time of failure:\n");
1019 m_graph.dump();
1020 }
1021};
1022
1023} // End anonymous namespace.
1024
1025void validate(Graph& graph, GraphDumpMode graphDumpMode, CString graphDumpBeforePhase)
1026{
1027 Validate validationObject(graph, graphDumpMode, graphDumpBeforePhase);
1028 validationObject.validate();
1029}
1030
1031} } // namespace JSC::DFG
1032
1033#endif // ENABLE(DFG_JIT)
1034
1035