e3141e69f7f5ab821b1479459c655264f47b95bd
[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 ValueMul:
259                 case ValueDiv:
260                 case ValueMod:
261                 case ValuePow:
262                 case ArithAdd:
263                 case ArithSub:
264                 case ArithMul:
265                 case ArithIMul:
266                 case ArithDiv:
267                 case ArithMod:
268                 case ArithMin:
269                 case ArithMax:
270                 case ArithPow:
271                 case CompareLess:
272                 case CompareLessEq:
273                 case CompareGreater:
274                 case CompareGreaterEq:
275                 case CompareBelow:
276                 case CompareBelowEq:
277                 case CompareEq:
278                 case CompareStrictEq:
279                 case SameValue:
280                 case StrCat:
281                     VALIDATE((node), !!node->child1());
282                     VALIDATE((node), !!node->child2());
283                     break;
284                 case CompareEqPtr:
285                     VALIDATE((node), !!node->child1());
286                     VALIDATE((node), !!node->cellOperand()->value() && node->cellOperand()->value().isCell());
287                     break;
288                 case CheckStructureOrEmpty:
289                     VALIDATE((node), is64Bit());
290                     VALIDATE((node), !!node->child1());
291                     VALIDATE((node), node->child1().useKind() == CellUse);
292                     break;
293                 case CheckStructure:
294                 case StringFromCharCode:
295                     VALIDATE((node), !!node->child1());
296                     break;
297                 case PutStructure:
298                     VALIDATE((node), !node->transition()->previous->dfgShouldWatch());
299                     break;
300                 case MultiPutByOffset:
301                     for (unsigned i = node->multiPutByOffsetData().variants.size(); i--;) {
302                         const PutByIdVariant& variant = node->multiPutByOffsetData().variants[i];
303                         if (variant.kind() != PutByIdVariant::Transition)
304                             continue;
305                         VALIDATE((node), !variant.oldStructureForTransition()->dfgShouldWatch());
306                     }
307                     break;
308                 case MaterializeNewObject:
309                     for (RegisteredStructure structure : node->structureSet()) {
310                         // This only supports structures that are JSFinalObject or JSArray.
311                         VALIDATE(
312                             (node),
313                             structure->classInfo() == JSFinalObject::info()
314                             || structure->classInfo() == JSArray::info());
315
316                         // We only support certain indexing shapes.
317                         VALIDATE((node), !hasAnyArrayStorage(structure->indexingType()));
318                     }
319                     break;
320                 case DoubleConstant:
321                 case Int52Constant:
322                     VALIDATE((node), node->isNumberConstant());
323                     break;
324                 case GetByOffset:
325                 case PutByOffset:
326                     // FIXME: We should be able to validate that GetByOffset and PutByOffset are
327                     // using the same object for storage and base. I think this means finally
328                     // splitting these nodes into two node types, one for inline and one for
329                     // out-of-line. The out-of-line one will require that the first node is storage,
330                     // while the inline one will not take a storage child at all.
331                     // https://bugs.webkit.org/show_bug.cgi?id=159602
332                     break;
333                 case HasOwnProperty: {
334                     VALIDATE((node), !!m_graph.m_vm.hasOwnPropertyCache());
335                     break;
336                 }
337                 case GetVectorLength: {
338                     Array::Type type = node->arrayMode().type();
339                     VALIDATE((node), type == Array::ArrayStorage || type == Array::SlowPutArrayStorage);
340                     break;
341                 }
342                 case CPUIntrinsic: {
343                     switch (node->intrinsic()) {
344                     case CPUMfenceIntrinsic:
345                     case CPURdtscIntrinsic:
346                     case CPUCpuidIntrinsic:
347                     case CPUPauseIntrinsic:
348                         break;
349                     default:
350                         VALIDATE((node), false);
351                         break;
352                     }
353                     break;
354                 }
355                 case GetArgumentCountIncludingThis: {
356                     if (InlineCallFrame* inlineCallFrame = node->argumentsInlineCallFrame())
357                         VALIDATE((node), inlineCallFrame->isVarargs());
358                     break;
359                 }
360                 case NewArray:
361                     VALIDATE((node), node->vectorLengthHint() >= node->numChildren());
362                     break;
363                 case NewArrayBuffer:
364                     VALIDATE((node), node->vectorLengthHint() >= node->castOperand<JSImmutableButterfly*>()->length());
365                     break;
366                 default:
367                     break;
368                 }
369             }
370         }
371         
372         switch (m_graph.m_form) {
373         case LoadStore:
374         case ThreadedCPS:
375             validateCPS();
376             break;
377             
378         case SSA:
379             validateSSA();
380             break;
381         }
382
383         // Validate clobbered states.
384         struct DefLambdaAdaptor {
385             Function<void(PureValue)> pureValue;
386             Function<void(HeapLocation, LazyNode)> locationAndNode;
387
388             void operator()(PureValue value) const
389             {
390                 pureValue(value);
391             }
392
393             void operator()(HeapLocation location, LazyNode node) const
394             {
395                 locationAndNode(location, node);
396             }
397         };
398         for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
399             for (Node* node : *block) {
400                 clobberize(m_graph, node,
401                     [&] (AbstractHeap) { },
402                     [&] (AbstractHeap heap)
403                     {
404                         // CSE assumes that HEAP TOP is never written.
405                         // If this assumption is weakened, you need to update clobbering
406                         // in CSE accordingly.
407                         if (heap.kind() == Stack)
408                             VALIDATE((node), !heap.payload().isTop());
409                     },
410                     DefLambdaAdaptor {
411                         [&] (PureValue) { },
412                         [&] (HeapLocation location, LazyNode)
413                         {
414                             VALIDATE((node), location.heap().kind() != SideState);
415
416                             // More specific kinds should be used instead.
417                             VALIDATE((node), location.heap().kind() != World);
418                             VALIDATE((node), location.heap().kind() != Heap);
419                         }
420                 });
421             }
422         }
423
424         for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
425             // We expect the predecessor list to be de-duplicated.
426             HashSet<BasicBlock*> predecessors;
427             for (BasicBlock* predecessor : block->predecessors)
428                 predecessors.add(predecessor);
429             VALIDATE((block), predecessors.size() == block->predecessors.size());
430         }
431     }
432     
433 private:
434     Graph& m_graph;
435     GraphDumpMode m_graphDumpMode;
436     CString m_graphDumpBeforePhase;
437     
438     HashMap<Node*, unsigned> m_myRefCounts;
439     HashSet<Node*> m_acceptableNodes;
440     
441     void validateCPS()
442     {
443         VALIDATE((), !m_graph.m_rootToArguments.isEmpty()); // We should have at least one root.
444         VALIDATE((), m_graph.m_rootToArguments.size() == m_graph.m_roots.size());
445         for (BasicBlock* root : m_graph.m_rootToArguments.keys())
446             VALIDATE((), m_graph.m_roots.contains(root));
447
448         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
449             BasicBlock* block = m_graph.block(blockIndex);
450             if (!block)
451                 continue;
452             
453             HashSet<Node*> phisInThisBlock;
454             HashSet<Node*> nodesInThisBlock;
455             
456             for (size_t i = 0; i < block->numNodes(); ++i) {
457                 Node* node = block->node(i);
458                 nodesInThisBlock.add(node);
459                 if (block->isPhiIndex(i))
460                     phisInThisBlock.add(node);
461                 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
462                     Edge edge = m_graph.child(node, j);
463                     if (!edge)
464                         continue;
465                     VALIDATE((node, edge), m_acceptableNodes.contains(edge.node()));
466                 }
467             }
468
469             {
470                 HashSet<Node*> seenNodes;
471                 for (size_t i = 0; i < block->size(); ++i) {
472                     Node* node = block->at(i);
473                     m_graph.doToChildren(node, [&] (const Edge& edge) {
474                         Node* child = edge.node();
475                         VALIDATE((node), block->isInPhis(child) || seenNodes.contains(child));
476                     });
477                     seenNodes.add(node);
478                 }
479             }
480             
481             for (size_t i = 0; i < block->phis.size(); ++i) {
482                 Node* node = block->phis[i];
483                 ASSERT(phisInThisBlock.contains(node));
484                 VALIDATE((node), node->op() == Phi);
485                 VirtualRegister local = node->local();
486                 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
487                     // Phi children in LoadStore form are invalid.
488                     if (m_graph.m_form == LoadStore && block->isPhiIndex(i))
489                         continue;
490                     
491                     Edge edge = m_graph.child(node, j);
492                     if (!edge)
493                         continue;
494                     
495                     VALIDATE(
496                         (node, edge),
497                         edge->op() == SetLocal
498                         || edge->op() == SetArgumentDefinitely
499                         || edge->op() == SetArgumentMaybe
500                         || edge->op() == Phi);
501                     
502                     if (phisInThisBlock.contains(edge.node()))
503                         continue;
504                     
505                     if (nodesInThisBlock.contains(edge.node())) {
506                         VALIDATE(
507                             (node, edge),
508                             edge->op() == SetLocal
509                             || edge->op() == SetArgumentDefinitely
510                             || edge->op() == SetArgumentMaybe);
511                         
512                         continue;
513                     }
514                     
515                     // There must exist a predecessor block that has this node index in
516                     // its tail variables.
517                     bool found = false;
518                     for (unsigned k = 0; k < block->predecessors.size(); ++k) {
519                         BasicBlock* prevBlock = block->predecessors[k];
520                         VALIDATE((block->predecessors[k]), prevBlock);
521                         Node* prevNode = prevBlock->variablesAtTail.operand(local);
522                         // If we have a Phi that is not referring to *this* block then all predecessors
523                         // must have that local available.
524                         VALIDATE((local, block, block->predecessors[k]), prevNode);
525                         switch (prevNode->op()) {
526                         case GetLocal:
527                         case Flush:
528                         case PhantomLocal:
529                             prevNode = prevNode->child1().node();
530                             break;
531                         default:
532                             break;
533                         }
534                         if (node->shouldGenerate()) {
535                             VALIDATE((local, block->predecessors[k], prevNode),
536                                      prevNode->shouldGenerate());
537                         }
538                         VALIDATE(
539                             (local, block->predecessors[k], prevNode),
540                             prevNode->op() == SetLocal
541                             || prevNode->op() == SetArgumentDefinitely
542                             || prevNode->op() == SetArgumentMaybe
543                             || prevNode->op() == Phi);
544                         if (prevNode == edge.node()) {
545                             found = true;
546                             break;
547                         }
548                         // At this point it cannot refer into this block.
549                         VALIDATE((local, block->predecessors[k], prevNode), !prevBlock->isInBlock(edge.node()));
550                     }
551                     
552                     VALIDATE((node, edge), found);
553                 }
554             }
555             
556             Operands<size_t> getLocalPositions(
557                 block->variablesAtHead.numberOfArguments(),
558                 block->variablesAtHead.numberOfLocals());
559             Operands<size_t> setLocalPositions(
560                 block->variablesAtHead.numberOfArguments(),
561                 block->variablesAtHead.numberOfLocals());
562             
563             for (size_t i = 0; i < block->variablesAtHead.numberOfArguments(); ++i) {
564                 VALIDATE((virtualRegisterForArgument(i), block), !block->variablesAtHead.argument(i) || block->variablesAtHead.argument(i)->accessesStack(m_graph));
565                 if (m_graph.m_form == ThreadedCPS)
566                     VALIDATE((virtualRegisterForArgument(i), block), !block->variablesAtTail.argument(i) || block->variablesAtTail.argument(i)->accessesStack(m_graph));
567                 
568                 getLocalPositions.argument(i) = notSet;
569                 setLocalPositions.argument(i) = notSet;
570             }
571             for (size_t i = 0; i < block->variablesAtHead.numberOfLocals(); ++i) {
572                 VALIDATE((virtualRegisterForLocal(i), block), !block->variablesAtHead.local(i) || block->variablesAtHead.local(i)->accessesStack(m_graph));
573                 if (m_graph.m_form == ThreadedCPS)
574                     VALIDATE((virtualRegisterForLocal(i), block), !block->variablesAtTail.local(i) || block->variablesAtTail.local(i)->accessesStack(m_graph));
575
576                 getLocalPositions.local(i) = notSet;
577                 setLocalPositions.local(i) = notSet;
578             }
579             
580             for (size_t i = 0; i < block->size(); ++i) {
581                 Node* node = block->at(i);
582                 ASSERT(nodesInThisBlock.contains(node));
583                 VALIDATE((node), node->op() != Phi);
584                 VALIDATE((node), node->origin.forExit.isSet());
585                 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
586                     Edge edge = m_graph.child(node, j);
587                     if (!edge)
588                         continue;
589                     VALIDATE((node, edge), nodesInThisBlock.contains(edge.node()));
590                     switch (node->op()) {
591                     case PhantomLocal:
592                     case GetLocal:
593                     case Flush:
594                         break;
595                     default:
596                         VALIDATE((node, edge), !phisInThisBlock.contains(edge.node()));
597                         break;
598                     }
599                 }
600                 
601                 switch (node->op()) {
602                 case Phi:
603                 case Upsilon:
604                 case CheckInBounds:
605                 case PhantomNewObject:
606                 case PhantomNewFunction:
607                 case PhantomNewGeneratorFunction:
608                 case PhantomNewAsyncFunction:
609                 case PhantomNewAsyncGeneratorFunction:
610                 case PhantomCreateActivation:
611                 case PhantomNewRegexp:
612                 case GetMyArgumentByVal:
613                 case GetMyArgumentByValOutOfBounds:
614                 case PutHint:
615                 case CheckStructureImmediate:
616                 case MaterializeCreateActivation:
617                 case PutStack:
618                 case KillStack:
619                 case GetStack:
620                 case EntrySwitch:
621                 case InitializeEntrypointArguments:
622                     VALIDATE((node), !"unexpected node type in CPS");
623                     break;
624                 case MaterializeNewObject: {
625                     // CPS only allows array lengths to be constant. This constraint only exists
626                     // because we don't have DFG support for anything more and we don't need any
627                     // other kind of support for now.
628                     ObjectMaterializationData& data = node->objectMaterializationData();
629                     for (unsigned i = data.m_properties.size(); i--;) {
630                         PromotedLocationDescriptor descriptor = data.m_properties[i];
631                         Edge edge = m_graph.varArgChild(node, 1 + i);
632                         switch (descriptor.kind()) {
633                         case PublicLengthPLoc:
634                         case VectorLengthPLoc:
635                             VALIDATE((node, edge), edge->isInt32Constant());
636                             break;
637                         default:
638                             break;
639                         }
640                     }
641
642                     // CPS only allows one structure.
643                     VALIDATE((node), node->structureSet().size() == 1);
644
645                     // CPS disallows int32 and double arrays. Those require weird type checks and
646                     // conversions. They are not needed in the DFG right now. We should add support
647                     // for these if the DFG ever needs it.
648                     for (RegisteredStructure structure : node->structureSet()) {
649                         VALIDATE((node), !hasInt32(structure->indexingType()));
650                         VALIDATE((node), !hasDouble(structure->indexingType()));
651                     }
652                     break;
653                 }
654                 case Phantom:
655                     VALIDATE((node), m_graph.m_fixpointState != FixpointNotConverged);
656                     break;
657                 default:
658                     break;
659                 }
660                 
661                 if (!node->shouldGenerate())
662                     continue;
663                 switch (node->op()) {
664                 case GetLocal:
665                     // Ignore GetLocal's that we know to be dead, but that the graph
666                     // doesn't yet know to be dead.
667                     if (!m_myRefCounts.get(node))
668                         break;
669                     if (m_graph.m_form == ThreadedCPS) {
670                         VALIDATE((node, block), getLocalPositions.operand(node->local()) == notSet);
671                         VALIDATE((node, block), !!node->child1());
672                         VALIDATE((node, block), node->child1()->op() == SetArgumentDefinitely || node->child1()->op() == Phi);
673                     }
674                     getLocalPositions.operand(node->local()) = i;
675                     break;
676                 case SetLocal:
677                     // Only record the first SetLocal. There may be multiple SetLocals
678                     // because of flushing.
679                     if (setLocalPositions.operand(node->local()) != notSet)
680                         break;
681                     setLocalPositions.operand(node->local()) = i;
682                     break;
683                 case SetArgumentDefinitely:
684                     // This acts like a reset. It's ok to have a second GetLocal for a local in the same
685                     // block if we had a SetArgumentDefinitely for that local.
686                     getLocalPositions.operand(node->local()) = notSet;
687                     setLocalPositions.operand(node->local()) = notSet;
688                     break;
689                 case SetArgumentMaybe:
690                     break;
691                 case Flush:
692                 case PhantomLocal:
693                     if (m_graph.m_form == ThreadedCPS) {
694                         VALIDATE((node, block), 
695                             node->child1()->op() == Phi
696                             || node->child1()->op() == SetLocal
697                             || node->child1()->op() == SetArgumentDefinitely
698                             || node->child1()->op() == SetArgumentMaybe);
699                         if (node->op() == PhantomLocal)
700                             VALIDATE((node, block), node->child1()->op() != SetArgumentMaybe);
701                     }
702                     break;
703                 default:
704                     break;
705                 }
706             }
707             
708             if (m_graph.m_form == LoadStore)
709                 continue;
710             
711             for (size_t i = 0; i < block->variablesAtHead.numberOfArguments(); ++i) {
712                 checkOperand(
713                     block, getLocalPositions, setLocalPositions, virtualRegisterForArgument(i));
714             }
715             for (size_t i = 0; i < block->variablesAtHead.numberOfLocals(); ++i) {
716                 checkOperand(
717                     block, getLocalPositions, setLocalPositions, virtualRegisterForLocal(i));
718             }
719         }
720
721         if (m_graph.m_form == ThreadedCPS) {
722             Vector<Node*> worklist;
723             HashSet<Node*> seen;
724             for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
725                 for (Node* node : *block) {
726                     if (node->op() == GetLocal || node->op() == PhantomLocal) {
727                         worklist.append(node);
728                         auto addResult = seen.add(node);
729                         VALIDATE((node, block), addResult.isNewEntry);
730                     }
731                 }
732             }
733
734             while (worklist.size()) {
735                 Node* node = worklist.takeLast();
736                 switch (node->op()) {
737                 case PhantomLocal:
738                 case GetLocal: {
739                     Node* child = node->child1().node();
740                     if (seen.add(child).isNewEntry)
741                         worklist.append(child);
742                     break;
743                 }
744                 case Phi: {
745                     for (unsigned i = 0; i < m_graph.numChildren(node); ++i) {
746                         Edge edge = m_graph.child(node, i);
747                         if (!edge)
748                             continue;
749                         if (seen.add(edge.node()).isNewEntry)
750                             worklist.append(edge.node());
751                     }
752                     break;
753                 }
754                 case SetLocal:
755                 case SetArgumentDefinitely:
756                     break;
757                 case SetArgumentMaybe:
758                     VALIDATE((node), !"Should not reach SetArgumentMaybe. GetLocal that has data flow that reaches a SetArgumentMaybe is invalid IR.");
759                     break;
760                 default:
761                     VALIDATE((node), !"Unexecpted node type.");
762                     break;
763                 }
764             }
765         }
766     }
767     
768     void validateSSA()
769     {
770         // FIXME: Add more things here.
771         // https://bugs.webkit.org/show_bug.cgi?id=123471
772         
773         VALIDATE((), m_graph.m_roots.size() == 1);
774         VALIDATE((), m_graph.m_roots[0] == m_graph.block(0));
775         VALIDATE((), !m_graph.m_argumentFormats.isEmpty()); // We always have at least one entrypoint.
776         VALIDATE((), m_graph.m_rootToArguments.isEmpty()); // This is only used in CPS.
777
778         for (unsigned entrypointIndex : m_graph.m_entrypointIndexToCatchBytecodeOffset.keys())
779             VALIDATE((), entrypointIndex > 0); // By convention, 0 is the entrypoint index for the op_enter entrypoint, which can not be in a catch.
780
781         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
782             BasicBlock* block = m_graph.block(blockIndex);
783             if (!block)
784                 continue;
785             
786             VALIDATE((block), block->phis.isEmpty());
787
788             bool didSeeExitOK = false;
789             bool isOSRExited = false;
790             
791             for (auto* node : *block) {
792                 didSeeExitOK |= node->origin.exitOK;
793                 switch (node->op()) {
794                 case Phi:
795                     // Phi cannot exit, and it would be wrong to hoist anything to the Phi that could
796                     // exit.
797                     VALIDATE((node), !node->origin.exitOK);
798
799                     // It never makes sense to have exitOK anywhere in the block before a Phi. It's only
800                     // OK to exit after all Phis are done.
801                     VALIDATE((node), !didSeeExitOK);
802                     break;
803                     
804                 case GetLocal:
805                 case SetLocal:
806                 case SetArgumentDefinitely:
807                 case SetArgumentMaybe:
808                 case Phantom:
809                     VALIDATE((node), !"bad node type for SSA");
810                     break;
811
812                 default:
813                     // FIXME: Add more things here.
814                     // https://bugs.webkit.org/show_bug.cgi?id=123471
815                     break;
816                 }
817
818                 if (isOSRExited)
819                     continue;
820                 switch (node->op()) {
821                 case PhantomNewObject:
822                 case PhantomNewFunction:
823                 case PhantomNewGeneratorFunction:
824                 case PhantomNewAsyncFunction:
825                 case PhantomNewAsyncGeneratorFunction:
826                 case PhantomCreateActivation:
827                 case PhantomDirectArguments:
828                 case PhantomCreateRest:
829                 case PhantomClonedArguments:
830                 case PhantomNewRegexp:
831                 case MovHint:
832                 case Upsilon:
833                 case ForwardVarargs:
834                 case CallForwardVarargs:
835                 case TailCallForwardVarargs:
836                 case TailCallForwardVarargsInlinedCaller:
837                 case ConstructForwardVarargs:
838                 case GetMyArgumentByVal:
839                 case GetMyArgumentByValOutOfBounds:
840                     break;
841
842                 case Check:
843                 case CheckVarargs:
844                     // FIXME: This is probably not correct.
845                     break;
846
847                 case PutHint:
848                     VALIDATE((node), node->child1()->isPhantomAllocation());
849                     break;
850
851                 case PhantomSpread:
852                     VALIDATE((node), m_graph.m_form == SSA);
853                     // We currently support PhantomSpread over PhantomCreateRest and PhantomNewArrayBuffer.
854                     VALIDATE((node), node->child1()->op() == PhantomCreateRest || node->child1()->op() == PhantomNewArrayBuffer);
855                     break;
856
857                 case PhantomNewArrayWithSpread: {
858                     VALIDATE((node), m_graph.m_form == SSA);
859                     BitVector* bitVector = node->bitVector();
860                     for (unsigned i = 0; i < node->numChildren(); i++) {
861                         Node* child = m_graph.varArgChild(node, i).node();
862                         if (bitVector->get(i)) {
863                             // We currently support PhantomSpread over PhantomCreateRest and PhantomNewArrayBuffer.
864                             VALIDATE((node), child->op() == PhantomSpread);
865                         } else
866                             VALIDATE((node), !child->isPhantomAllocation());
867                     }
868                     break;
869                 }
870
871                 case PhantomNewArrayBuffer:
872                     VALIDATE((node), m_graph.m_form == SSA);
873                     VALIDATE((node), node->vectorLengthHint() >= node->castOperand<JSImmutableButterfly*>()->length());
874                     break;
875
876                 case NewArrayWithSpread: {
877                     BitVector* bitVector = node->bitVector();
878                     for (unsigned i = 0; i < node->numChildren(); i++) {
879                         Node* child = m_graph.varArgChild(node, i).node();
880                         if (child->isPhantomAllocation()) {
881                             VALIDATE((node), bitVector->get(i));
882                             VALIDATE((node), m_graph.m_form == SSA);
883                             VALIDATE((node), child->op() == PhantomSpread);
884                         }
885                     }
886                     break;
887                 }
888
889                 case Spread:
890                     VALIDATE((node), !node->child1()->isPhantomAllocation() || node->child1()->op() == PhantomCreateRest || node->child1()->op() == PhantomNewArrayBuffer);
891                     break;
892
893                 case EntrySwitch:
894                     VALIDATE((node), node->entrySwitchData()->cases.size() == m_graph.m_numberOfEntrypoints);
895                     break;
896
897                 case InitializeEntrypointArguments:
898                     VALIDATE((node), node->entrypointIndex() < m_graph.m_numberOfEntrypoints);
899                     break;
900
901                 default:
902                     m_graph.doToChildren(
903                         node,
904                         [&] (const Edge& edge) {
905                             VALIDATE((node), !edge->isPhantomAllocation());
906                         });
907                     break;
908                 }
909                 isOSRExited |= node->isPseudoTerminal();
910             }
911         }
912     }
913
914     void validateEdgeWithDoubleResultIfNecessary(Node* node, Edge edge)
915     {
916         if (!edge->hasDoubleResult())
917             return;
918
919         if (m_graph.m_planStage < PlanStage::AfterFixup)
920             return;
921         
922         VALIDATE((node, edge), edge.useKind() == DoubleRepUse || edge.useKind() == DoubleRepRealUse || edge.useKind() == DoubleRepAnyIntUse);
923     }
924
925     void checkOperand(
926         BasicBlock* block, Operands<size_t>& getLocalPositions,
927         Operands<size_t>& setLocalPositions, VirtualRegister operand)
928     {
929         if (getLocalPositions.operand(operand) == notSet)
930             return;
931         if (setLocalPositions.operand(operand) == notSet)
932             return;
933         
934         VALIDATE(
935             (block->at(getLocalPositions.operand(operand)),
936              block->at(setLocalPositions.operand(operand)),
937              block),
938             getLocalPositions.operand(operand) < setLocalPositions.operand(operand));
939     }
940     
941     void reportValidationContext() { }
942
943     void reportValidationContext(Node* node)
944     {
945         dataLogF("@%u", node->index());
946     }
947     
948     void reportValidationContext(BasicBlock* block)
949     {
950         dataLog("Block ", *block);
951     }
952     
953     void reportValidationContext(Node* node, Edge edge)
954     {
955         dataLog(node, " -> ", edge);
956     }
957     
958     void reportValidationContext(VirtualRegister local, BasicBlock* block)
959     {
960         if (!block) {
961             dataLog(local, " in null Block ");
962             return;
963         }
964
965         dataLog(local, " in Block ", *block);
966     }
967     
968     void reportValidationContext(
969         VirtualRegister local, BasicBlock* sourceBlock, BasicBlock* destinationBlock)
970     {
971         dataLog(local, " in Block ", *sourceBlock, " -> ", *destinationBlock);
972     }
973     
974     void reportValidationContext(
975         VirtualRegister local, BasicBlock* sourceBlock, Node* prevNode)
976     {
977         dataLog(prevNode, " for ", local, " in Block ", *sourceBlock);
978     }
979     
980     void reportValidationContext(Node* node, BasicBlock* block)
981     {
982         dataLog(node, " in Block ", *block);
983     }
984     
985     void reportValidationContext(Node* node, Node* node2, BasicBlock* block)
986     {
987         dataLog(node, " and ", node2, " in Block ", *block);
988     }
989     
990     void reportValidationContext(
991         Node* node, BasicBlock* block, Node* expectedNode, Edge incomingEdge)
992     {
993         dataLog(node, " in Block ", *block, ", searching for ", expectedNode, " from ", incomingEdge);
994     }
995     
996     void dumpGraphIfAppropriate()
997     {
998         if (m_graphDumpMode == DontDumpGraph)
999             return;
1000         dataLog("\n");
1001         if (!m_graphDumpBeforePhase.isNull()) {
1002             dataLog("Before phase:\n");
1003             dataLog(m_graphDumpBeforePhase);
1004         }
1005         dataLog("At time of failure:\n");
1006         m_graph.dump();
1007     }
1008 };
1009
1010 } // End anonymous namespace.
1011
1012 void validate(Graph& graph, GraphDumpMode graphDumpMode, CString graphDumpBeforePhase)
1013 {
1014     Validate validationObject(graph, graphDumpMode, graphDumpBeforePhase);
1015     validationObject.validate();
1016 }
1017
1018 } } // namespace JSC::DFG
1019
1020 #endif // ENABLE(DFG_JIT)
1021