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