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