2 * Copyright (C) 2012-2015 Apple Inc. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
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.
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.
27 #include "DFGValidate.h"
31 #include "CodeBlockWithJITType.h"
32 #include "DFGMayExit.h"
33 #include "JSCInlines.h"
34 #include <wtf/Assertions.h>
35 #include <wtf/BitVector.h>
37 namespace JSC { namespace DFG {
41 Validate(Graph& graph, GraphDumpMode graphDumpMode, CString graphDumpBeforePhase)
43 , m_graphDumpMode(graphDumpMode)
44 , m_graphDumpBeforePhase(graphDumpBeforePhase)
48 #define VALIDATE(context, assertion) do { \
51 dataLogF("\n\n\nAt "); \
52 reportValidationContext context; \
53 dataLogF(": validation failed: %s (%s:%d).\n", #assertion, __FILE__, __LINE__); \
54 dumpGraphIfAppropriate(); \
55 WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #assertion); \
60 #define V_EQUAL(context, left, right) do { \
61 if (left != right) { \
63 dataLogF("\n\n\nAt "); \
64 reportValidationContext context; \
65 dataLogF(": validation failed: (%s = ", #left); \
67 dataLogF(") == (%s = ", #right); \
69 dataLogF(") (%s:%d).\n", __FILE__, __LINE__); \
70 dumpGraphIfAppropriate(); \
71 WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #left " == " #right); \
76 #define notSet (static_cast<size_t>(-1))
80 // NB. This code is not written for performance, since it is not intended to run
83 // Validate that all local variables at the head of the root block are dead.
84 BasicBlock* root = m_graph.block(0);
85 for (unsigned i = 0; i < root->variablesAtHead.numberOfLocals(); ++i)
86 V_EQUAL((virtualRegisterForLocal(i), root), static_cast<Node*>(0), root->variablesAtHead.local(i));
88 // Validate ref counts and uses.
89 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
90 BasicBlock* block = m_graph.block(blockIndex);
93 VALIDATE((block), block->isReachable);
94 for (size_t i = 0; i < block->numNodes(); ++i)
95 m_myRefCounts.add(block->node(i), 0);
97 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
98 BasicBlock* block = m_graph.block(blockIndex);
101 for (size_t i = 0; i < block->numNodes(); ++i) {
102 Node* node = block->node(i);
103 m_acceptableNodes.add(node);
104 if (!node->shouldGenerate())
106 if (node->op() == Upsilon) {
107 VALIDATE((node), m_graph.m_form == SSA);
108 if (node->phi()->shouldGenerate())
109 m_myRefCounts.find(node)->value++;
111 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
112 // Phi children in LoadStore form are invalid.
113 if (m_graph.m_form == LoadStore && block->isPhiIndex(i))
116 Edge edge = m_graph.child(node, j);
120 m_myRefCounts.find(edge.node())->value++;
122 validateEdgeWithDoubleResultIfNecessary(node, edge);
123 VALIDATE((node, edge), edge->hasInt52Result() == (edge.useKind() == Int52RepUse));
125 if (m_graph.m_form == SSA) {
126 // In SSA, all edges must hasResult().
127 VALIDATE((node, edge), edge->hasResult());
131 // Unless I'm a Flush, Phantom, GetLocal, or Phi, my children should hasResult().
132 switch (node->op()) {
135 VALIDATE((node, edge), edge->hasVariableAccessData(m_graph));
136 VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData());
139 VALIDATE((node, edge), edge->hasVariableAccessData(m_graph));
140 VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData());
141 VALIDATE((node, edge), edge->op() != SetLocal);
144 VALIDATE((node, edge), edge->hasVariableAccessData(m_graph));
145 if (m_graph.m_unificationState == LocallyUnified)
147 VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData());
150 VALIDATE((node, edge), edge->hasResult());
157 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
158 BasicBlock* block = m_graph.block(blockIndex);
161 for (size_t i = 0; i < block->numNodes(); ++i) {
162 Node* node = block->node(i);
163 if (m_graph.m_refCountState == ExactRefCount)
164 V_EQUAL((node), m_myRefCounts.get(node), node->adjustedRefCount());
167 bool foundTerminal = false;
168 for (size_t i = 0 ; i < block->size(); ++i) {
169 Node* node = block->at(i);
170 if (node->isTerminal()) {
171 foundTerminal = true;
172 for (size_t j = i + 1; j < block->size(); ++j) {
174 VALIDATE((node), node->op() == Phantom || node->op() == PhantomLocal || node->op() == Flush || node->op() == Check);
175 m_graph.doToChildren(
178 VALIDATE((node, edge), shouldNotHaveTypeCheck(edge.useKind()));
184 VALIDATE((block), foundTerminal);
186 for (size_t i = 0; i < block->size(); ++i) {
187 Node* node = block->at(i);
189 VALIDATE((node), node->origin.semantic.isSet() == node->origin.forExit.isSet());
190 VALIDATE((node), !mayExit(m_graph, node) || node->origin.forExit.isSet());
191 VALIDATE((node), !node->hasStructure() || !!node->structure());
192 VALIDATE((node), !node->hasCellOperand() || node->cellOperand()->value().isCell());
193 VALIDATE((node), !node->hasCellOperand() || !!node->cellOperand()->value());
195 if (!(node->flags() & NodeHasVarArgs)) {
197 VALIDATE((node), !node->child3());
199 VALIDATE((node), !node->child2());
202 switch (node->op()) {
204 VALIDATE((node), canonicalResultRepresentation(node->result()) == canonicalResultRepresentation(node->child1()->result()));
209 VALIDATE((node), !!node->child1());
210 switch (node->child1().useKind()) {
219 VALIDATE((node), !"Bad use kind");
237 case CompareGreaterEq:
239 case CompareEqConstant:
240 case CompareStrictEq:
241 VALIDATE((node), !!node->child1());
242 VALIDATE((node), !!node->child2());
245 VALIDATE((node), !node->transition()->previous->dfgShouldWatch());
247 case MultiPutByOffset:
248 for (unsigned i = node->multiPutByOffsetData().variants.size(); i--;) {
249 const PutByIdVariant& variant = node->multiPutByOffsetData().variants[i];
250 if (variant.kind() != PutByIdVariant::Transition)
252 VALIDATE((node), !variant.oldStructureForTransition()->dfgShouldWatch());
257 VALIDATE((node), node->isNumberConstant());
265 switch (m_graph.m_form) {
279 GraphDumpMode m_graphDumpMode;
280 CString m_graphDumpBeforePhase;
282 HashMap<Node*, unsigned> m_myRefCounts;
283 HashSet<Node*> m_acceptableNodes;
287 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
288 BasicBlock* block = m_graph.block(blockIndex);
292 HashSet<Node*> phisInThisBlock;
293 HashSet<Node*> nodesInThisBlock;
295 for (size_t i = 0; i < block->numNodes(); ++i) {
296 Node* node = block->node(i);
297 nodesInThisBlock.add(node);
298 if (block->isPhiIndex(i))
299 phisInThisBlock.add(node);
300 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
301 Edge edge = m_graph.child(node, j);
304 VALIDATE((node, edge), m_acceptableNodes.contains(edge.node()));
308 for (size_t i = 0; i < block->phis.size(); ++i) {
309 Node* node = block->phis[i];
310 ASSERT(phisInThisBlock.contains(node));
311 VALIDATE((node), node->op() == Phi);
312 VirtualRegister local = node->local();
313 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
314 // Phi children in LoadStore form are invalid.
315 if (m_graph.m_form == LoadStore && block->isPhiIndex(i))
318 Edge edge = m_graph.child(node, j);
324 edge->op() == SetLocal
325 || edge->op() == SetArgument
326 || edge->op() == Flush
327 || edge->op() == Phi);
329 if (phisInThisBlock.contains(edge.node()))
332 if (nodesInThisBlock.contains(edge.node())) {
335 edge->op() == SetLocal
336 || edge->op() == SetArgument
337 || edge->op() == Flush);
342 // There must exist a predecessor block that has this node index in
343 // its tail variables.
345 for (unsigned k = 0; k < block->predecessors.size(); ++k) {
346 BasicBlock* prevBlock = block->predecessors[k];
347 VALIDATE((block->predecessors[k]), prevBlock);
348 Node* prevNode = prevBlock->variablesAtTail.operand(local);
349 // If we have a Phi that is not referring to *this* block then all predecessors
350 // must have that local available.
351 VALIDATE((local, block, block->predecessors[k]), prevNode);
352 switch (prevNode->op()) {
356 prevNode = prevNode->child1().node();
361 if (node->shouldGenerate()) {
362 VALIDATE((local, block->predecessors[k], prevNode),
363 prevNode->shouldGenerate());
366 (local, block->predecessors[k], prevNode),
367 prevNode->op() == SetLocal
368 || prevNode->op() == SetArgument
369 || prevNode->op() == Phi);
370 if (prevNode == edge.node()) {
374 // At this point it cannot refer into this block.
375 VALIDATE((local, block->predecessors[k], prevNode), !prevBlock->isInBlock(edge.node()));
378 VALIDATE((node, edge), found);
382 Operands<size_t> getLocalPositions(
383 block->variablesAtHead.numberOfArguments(),
384 block->variablesAtHead.numberOfLocals());
385 Operands<size_t> setLocalPositions(
386 block->variablesAtHead.numberOfArguments(),
387 block->variablesAtHead.numberOfLocals());
389 for (size_t i = 0; i < block->variablesAtHead.numberOfArguments(); ++i) {
390 VALIDATE((virtualRegisterForArgument(i), block), !block->variablesAtHead.argument(i) || block->variablesAtHead.argument(i)->hasVariableAccessData(m_graph));
391 if (m_graph.m_form == ThreadedCPS)
392 VALIDATE((virtualRegisterForArgument(i), block), !block->variablesAtTail.argument(i) || block->variablesAtTail.argument(i)->hasVariableAccessData(m_graph));
394 getLocalPositions.argument(i) = notSet;
395 setLocalPositions.argument(i) = notSet;
397 for (size_t i = 0; i < block->variablesAtHead.numberOfLocals(); ++i) {
398 VALIDATE((virtualRegisterForLocal(i), block), !block->variablesAtHead.local(i) || block->variablesAtHead.local(i)->hasVariableAccessData(m_graph));
399 if (m_graph.m_form == ThreadedCPS)
400 VALIDATE((virtualRegisterForLocal(i), block), !block->variablesAtTail.local(i) || block->variablesAtTail.local(i)->hasVariableAccessData(m_graph));
402 getLocalPositions.local(i) = notSet;
403 setLocalPositions.local(i) = notSet;
406 for (size_t i = 0; i < block->size(); ++i) {
407 Node* node = block->at(i);
408 ASSERT(nodesInThisBlock.contains(node));
409 VALIDATE((node), node->op() != Phi);
410 VALIDATE((node), node->origin.forExit.isSet());
411 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
412 Edge edge = m_graph.child(node, j);
415 VALIDATE((node, edge), nodesInThisBlock.contains(edge.node()));
416 switch (node->op()) {
422 VALIDATE((node, edge), !phisInThisBlock.contains(edge.node()));
427 switch (node->op()) {
431 case PhantomNewObject:
432 case PhantomNewFunction:
433 case PhantomCreateActivation:
434 case GetMyArgumentByVal:
436 case CheckStructureImmediate:
437 case MaterializeNewObject:
438 case MaterializeCreateActivation:
442 VALIDATE((node), !"unexpected node type in CPS");
445 VALIDATE((node), m_graph.m_fixpointState != FixpointNotConverged);
451 if (!node->shouldGenerate())
453 switch (node->op()) {
455 // Ignore GetLocal's that we know to be dead, but that the graph
456 // doesn't yet know to be dead.
457 if (!m_myRefCounts.get(node))
459 if (m_graph.m_form == ThreadedCPS) {
460 VALIDATE((node, block), getLocalPositions.operand(node->local()) == notSet);
461 VALIDATE((node, block), !!node->child1());
463 getLocalPositions.operand(node->local()) = i;
466 // Only record the first SetLocal. There may be multiple SetLocals
467 // because of flushing.
468 if (setLocalPositions.operand(node->local()) != notSet)
470 setLocalPositions.operand(node->local()) = i;
473 // This acts like a reset. It's ok to have a second GetLocal for a local in the same
474 // block if we had a SetArgument for that local.
475 getLocalPositions.operand(node->local()) = notSet;
476 setLocalPositions.operand(node->local()) = notSet;
483 if (m_graph.m_form == LoadStore)
486 for (size_t i = 0; i < block->variablesAtHead.numberOfArguments(); ++i) {
488 block, getLocalPositions, setLocalPositions, virtualRegisterForArgument(i));
490 for (size_t i = 0; i < block->variablesAtHead.numberOfLocals(); ++i) {
492 block, getLocalPositions, setLocalPositions, virtualRegisterForLocal(i));
499 // FIXME: Add more things here.
500 // https://bugs.webkit.org/show_bug.cgi?id=123471
502 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
503 BasicBlock* block = m_graph.block(blockIndex);
507 VALIDATE((block), block->phis.isEmpty());
509 unsigned nodeIndex = 0;
510 for (; nodeIndex < block->size() && !block->at(nodeIndex)->origin.forExit.isSet(); nodeIndex++) { }
512 VALIDATE((block), nodeIndex < block->size());
514 for (; nodeIndex < block->size(); nodeIndex++)
515 VALIDATE((block->at(nodeIndex)), block->at(nodeIndex)->origin.forExit.isSet());
517 for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
518 Node* node = block->at(nodeIndex);
519 switch (node->op()) {
521 VALIDATE((node), !node->origin.forExit.isSet());
526 case GetLocalUnlinked:
529 VALIDATE((node), !"bad node type for SSA");
533 // FIXME: Add more things here.
534 // https://bugs.webkit.org/show_bug.cgi?id=123471
541 void validateEdgeWithDoubleResultIfNecessary(Node* node, Edge edge)
543 if (!edge->hasDoubleResult())
546 if (m_graph.m_planStage < PlanStage::AfterFixup)
547 VALIDATE((node, edge), edge.useKind() == UntypedUse);
549 VALIDATE((node, edge), edge.useKind() == DoubleRepUse || edge.useKind() == DoubleRepRealUse || edge.useKind() == DoubleRepMachineIntUse);
553 BasicBlock* block, Operands<size_t>& getLocalPositions,
554 Operands<size_t>& setLocalPositions, VirtualRegister operand)
556 if (getLocalPositions.operand(operand) == notSet)
558 if (setLocalPositions.operand(operand) == notSet)
562 (block->at(getLocalPositions.operand(operand)),
563 block->at(setLocalPositions.operand(operand)),
565 getLocalPositions.operand(operand) < setLocalPositions.operand(operand));
568 void reportValidationContext(Node* node)
570 dataLogF("@%u", node->index());
573 void reportValidationContext(BasicBlock* block)
575 dataLog("Block ", *block);
578 void reportValidationContext(Node* node, Edge edge)
580 dataLog(node, " -> ", edge);
583 void reportValidationContext(VirtualRegister local, BasicBlock* block)
586 dataLog(local, " in null Block ");
590 dataLog(local, " in Block ", *block);
593 void reportValidationContext(
594 VirtualRegister local, BasicBlock* sourceBlock, BasicBlock* destinationBlock)
596 dataLog(local, " in Block ", *sourceBlock, " -> ", *destinationBlock);
599 void reportValidationContext(
600 VirtualRegister local, BasicBlock* sourceBlock, Node* prevNode)
602 dataLog(prevNode, " for ", local, " in Block ", *sourceBlock);
605 void reportValidationContext(Node* node, BasicBlock* block)
607 dataLog(node, " in Block ", *block);
610 void reportValidationContext(Node* node, Node* node2, BasicBlock* block)
612 dataLog(node, " and ", node2, " in Block ", *block);
615 void reportValidationContext(
616 Node* node, BasicBlock* block, Node* expectedNode, Edge incomingEdge)
618 dataLog(node, " in Block ", *block, ", searching for ", expectedNode, " from ", incomingEdge);
621 void dumpGraphIfAppropriate()
623 if (m_graphDumpMode == DontDumpGraph)
626 if (!m_graphDumpBeforePhase.isNull()) {
627 dataLog("Before phase:\n");
628 dataLog(m_graphDumpBeforePhase);
630 dataLog("At time of failure:\n");
635 void validate(Graph& graph, GraphDumpMode graphDumpMode, CString graphDumpBeforePhase)
637 Validate validationObject(graph, graphDumpMode, graphDumpBeforePhase);
638 validationObject.validate();
641 } } // namespace JSC::DFG
643 #endif // ENABLE(DFG_JIT)