1/* 2 * Copyright (C) 2012-2014 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 "JSCInlines.h" 33#include <wtf/Assertions.h> 34#include <wtf/BitVector.h> 35 36namespace JSC { namespace DFG { 37 38class Validate { 39public: 40 Validate(Graph& graph, GraphDumpMode graphDumpMode) 41 : m_graph(graph) 42 , m_graphDumpMode(graphDumpMode) 43 { 44 } 45 46 #define VALIDATE(context, assertion) do { \ 47 if (!(assertion)) { \ 48 startCrashing(); \ 49 dataLogF("\n\n\nAt "); \ 50 reportValidationContext context; \ 51 dataLogF(": validation %s (%s:%d) failed.\n", #assertion, __FILE__, __LINE__); \ 52 dumpGraphIfAppropriate(); \ 53 WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #assertion); \ 54 CRASH(); \ 55 } \ 56 } while (0) 57 58 #define V_EQUAL(context, left, right) do { \ 59 if (left != right) { \ 60 startCrashing(); \ 61 dataLogF("\n\n\nAt "); \ 62 reportValidationContext context; \ 63 dataLogF(": validation (%s = ", #left); \ 64 dataLog(left); \ 65 dataLogF(") == (%s = ", #right); \ 66 dataLog(right); \ 67 dataLogF(") (%s:%d) failed.\n", __FILE__, __LINE__); \ 68 dumpGraphIfAppropriate(); \ 69 WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #left " == " #right); \ 70 CRASH(); \ 71 } \ 72 } while (0) 73 74 #define notSet (static_cast<size_t>(-1)) 75 76 void validate() 77 { 78 // NB. This code is not written for performance, since it is not intended to run 79 // in release builds. 80 81 // Validate that all local variables at the head of the root block are dead. 82 BasicBlock* root = m_graph.block(0); 83 for (unsigned i = 0; i < root->variablesAtHead.numberOfLocals(); ++i) 84 V_EQUAL((virtualRegisterForLocal(i), root), static_cast<Node*>(0), root->variablesAtHead.local(i)); 85 86 // Validate ref counts and uses. 87 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) { 88 BasicBlock* block = m_graph.block(blockIndex); 89 if (!block) 90 continue; 91 VALIDATE((block), block->isReachable); 92 for (size_t i = 0; i < block->numNodes(); ++i) 93 m_myRefCounts.add(block->node(i), 0); 94 } 95 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) { 96 BasicBlock* block = m_graph.block(blockIndex); 97 if (!block) 98 continue; 99 for (size_t i = 0; i < block->numNodes(); ++i) { 100 Node* node = block->node(i); 101 m_acceptableNodes.add(node); 102 if (!node->shouldGenerate()) 103 continue; 104 if (node->op() == Upsilon) { 105 VALIDATE((node), m_graph.m_form == SSA); 106 if (node->phi()->shouldGenerate()) 107 m_myRefCounts.find(node)->value++; 108 } 109 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) { 110 // Phi children in LoadStore form are invalid. 111 if (m_graph.m_form == LoadStore && block->isPhiIndex(i)) 112 continue; 113 114 Edge edge = m_graph.child(node, j); 115 if (!edge) 116 continue; 117 118 m_myRefCounts.find(edge.node())->value++; 119 120 VALIDATE((node, edge), edge->hasDoubleResult() == (edge.useKind() == DoubleRepUse || edge.useKind() == DoubleRepRealUse || edge.useKind() == DoubleRepMachineIntUse)); 121 VALIDATE((node, edge), edge->hasInt52Result() == (edge.useKind() == Int52RepUse)); 122 123 if (m_graph.m_form == SSA) { 124 // In SSA, all edges must hasResult(). 125 VALIDATE((node, edge), edge->hasResult()); 126 continue; 127 } 128 129 // Unless I'm a Flush, Phantom, GetLocal, or Phi, my children should hasResult(). 130 switch (node->op()) { 131 case Flush: 132 case GetLocal: 133 VALIDATE((node, edge), edge->hasVariableAccessData(m_graph)); 134 VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData()); 135 break; 136 case PhantomLocal: 137 VALIDATE((node, edge), edge->hasVariableAccessData(m_graph)); 138 VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData()); 139 VALIDATE((node, edge), edge->op() != SetLocal); 140 break; 141 case Phi: 142 VALIDATE((node, edge), edge->hasVariableAccessData(m_graph)); 143 if (m_graph.m_unificationState == LocallyUnified) 144 break; 145 VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData()); 146 break; 147 case Phantom: 148 switch (m_graph.m_form) { 149 case LoadStore: 150 if (j) { 151 VALIDATE((node, edge), edge->hasResult()); 152 break; 153 } 154 switch (edge->op()) { 155 case Phi: 156 case SetArgument: 157 case SetLocal: 158 break; 159 default: 160 VALIDATE((node, edge), edge->hasResult()); 161 break; 162 } 163 break; 164 case ThreadedCPS: 165 VALIDATE((node, edge), edge->hasResult()); 166 break; 167 case SSA: 168 RELEASE_ASSERT_NOT_REACHED(); 169 break; 170 } 171 break; 172 default: 173 VALIDATE((node, edge), edge->hasResult()); 174 break; 175 } 176 } 177 } 178 } 179 180 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) { 181 BasicBlock* block = m_graph.block(blockIndex); 182 if (!block) 183 continue; 184 for (size_t i = 0; i < block->numNodes(); ++i) { 185 Node* node = block->node(i); 186 if (m_graph.m_refCountState == ExactRefCount) 187 V_EQUAL((node), m_myRefCounts.get(node), node->adjustedRefCount()); 188 else 189 V_EQUAL((node), node->refCount(), 1); 190 } 191 192 for (size_t i = 0 ; i < block->size() - 1; ++i) { 193 Node* node = block->at(i); 194 VALIDATE((node), !node->isTerminal()); 195 } 196 197 for (size_t i = 0; i < block->size(); ++i) { 198 Node* node = block->at(i); 199 200 if (node->hasStructure()) 201 VALIDATE((node), !!node->structure()); 202 203 switch (node->op()) { 204 case Identity: 205 VALIDATE((node), canonicalResultRepresentation(node->result()) == canonicalResultRepresentation(node->child1()->result())); 206 break; 207 default: 208 break; 209 } 210 } 211 } 212 213 switch (m_graph.m_form) { 214 case LoadStore: 215 case ThreadedCPS: 216 validateCPS(); 217 break; 218 219 case SSA: 220 validateSSA(); 221 break; 222 } 223 } 224 225private: 226 Graph& m_graph; 227 GraphDumpMode m_graphDumpMode; 228 229 HashMap<Node*, unsigned> m_myRefCounts; 230 HashSet<Node*> m_acceptableNodes; 231 232 void validateCPS() 233 { 234 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) { 235 BasicBlock* block = m_graph.block(blockIndex); 236 if (!block) 237 continue; 238 239 HashSet<Node*> phisInThisBlock; 240 HashSet<Node*> nodesInThisBlock; 241 242 for (size_t i = 0; i < block->numNodes(); ++i) { 243 Node* node = block->node(i); 244 nodesInThisBlock.add(node); 245 if (block->isPhiIndex(i)) 246 phisInThisBlock.add(node); 247 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) { 248 Edge edge = m_graph.child(node, j); 249 if (!edge) 250 continue; 251 VALIDATE((node, edge), m_acceptableNodes.contains(edge.node())); 252 } 253 } 254 255 for (size_t i = 0; i < block->phis.size(); ++i) { 256 Node* node = block->phis[i]; 257 ASSERT(phisInThisBlock.contains(node)); 258 VALIDATE((node), node->op() == Phi); 259 VirtualRegister local = node->local(); 260 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) { 261 // Phi children in LoadStore form are invalid. 262 if (m_graph.m_form == LoadStore && block->isPhiIndex(i)) 263 continue; 264 265 Edge edge = m_graph.child(node, j); 266 if (!edge) 267 continue; 268 269 VALIDATE( 270 (node, edge), 271 edge->op() == SetLocal 272 || edge->op() == SetArgument 273 || edge->op() == Flush 274 || edge->op() == Phi); 275 276 if (phisInThisBlock.contains(edge.node())) 277 continue; 278 279 if (nodesInThisBlock.contains(edge.node())) { 280 VALIDATE( 281 (node, edge), 282 edge->op() == SetLocal 283 || edge->op() == SetArgument 284 || edge->op() == Flush); 285 286 continue; 287 } 288 289 // There must exist a predecessor block that has this node index in 290 // its tail variables. 291 bool found = false; 292 for (unsigned k = 0; k < block->predecessors.size(); ++k) { 293 BasicBlock* prevBlock = block->predecessors[k]; 294 VALIDATE((block->predecessors[k]), prevBlock); 295 Node* prevNode = prevBlock->variablesAtTail.operand(local); 296 // If we have a Phi that is not referring to *this* block then all predecessors 297 // must have that local available. 298 VALIDATE((local, block, block->predecessors[k]), prevNode); 299 switch (prevNode->op()) { 300 case GetLocal: 301 case Flush: 302 case PhantomLocal: 303 prevNode = prevNode->child1().node(); 304 break; 305 default: 306 break; 307 } 308 if (node->shouldGenerate()) { 309 VALIDATE((local, block->predecessors[k], prevNode), 310 prevNode->shouldGenerate()); 311 } 312 VALIDATE( 313 (local, block->predecessors[k], prevNode), 314 prevNode->op() == SetLocal 315 || prevNode->op() == SetArgument 316 || prevNode->op() == Phi); 317 if (prevNode == edge.node()) { 318 found = true; 319 break; 320 } 321 // At this point it cannot refer into this block. 322 VALIDATE((local, block->predecessors[k], prevNode), !prevBlock->isInBlock(edge.node())); 323 } 324 325 VALIDATE((node, edge), found); 326 } 327 } 328 329 Operands<size_t> getLocalPositions( 330 block->variablesAtHead.numberOfArguments(), 331 block->variablesAtHead.numberOfLocals()); 332 Operands<size_t> setLocalPositions( 333 block->variablesAtHead.numberOfArguments(), 334 block->variablesAtHead.numberOfLocals()); 335 336 for (size_t i = 0; i < block->variablesAtHead.numberOfArguments(); ++i) { 337 VALIDATE((virtualRegisterForArgument(i), block), !block->variablesAtHead.argument(i) || block->variablesAtHead.argument(i)->hasVariableAccessData(m_graph)); 338 if (m_graph.m_form == ThreadedCPS) 339 VALIDATE((virtualRegisterForArgument(i), block), !block->variablesAtTail.argument(i) || block->variablesAtTail.argument(i)->hasVariableAccessData(m_graph)); 340 341 getLocalPositions.argument(i) = notSet; 342 setLocalPositions.argument(i) = notSet; 343 } 344 for (size_t i = 0; i < block->variablesAtHead.numberOfLocals(); ++i) { 345 VALIDATE((virtualRegisterForLocal(i), block), !block->variablesAtHead.local(i) || block->variablesAtHead.local(i)->hasVariableAccessData(m_graph)); 346 if (m_graph.m_form == ThreadedCPS) 347 VALIDATE((virtualRegisterForLocal(i), block), !block->variablesAtTail.local(i) || block->variablesAtTail.local(i)->hasVariableAccessData(m_graph)); 348 349 getLocalPositions.local(i) = notSet; 350 setLocalPositions.local(i) = notSet; 351 } 352 353 for (size_t i = 0; i < block->size(); ++i) { 354 Node* node = block->at(i); 355 ASSERT(nodesInThisBlock.contains(node)); 356 VALIDATE((node), node->op() != Phi); 357 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) { 358 Edge edge = m_graph.child(node, j); 359 if (!edge) 360 continue; 361 VALIDATE((node, edge), nodesInThisBlock.contains(edge.node())); 362 switch (node->op()) { 363 case PhantomLocal: 364 case GetLocal: 365 case Flush: 366 break; 367 case Phantom: 368 if (m_graph.m_form == LoadStore && !j) 369 break; 370 FALLTHROUGH; 371 default: 372 VALIDATE((node, edge), !phisInThisBlock.contains(edge.node())); 373 break; 374 } 375 } 376 377 if (!node->shouldGenerate()) 378 continue; 379 switch (node->op()) { 380 case GetLocal: 381 if (node->variableAccessData()->isCaptured()) 382 break; 383 // Ignore GetLocal's that we know to be dead, but that the graph 384 // doesn't yet know to be dead. 385 if (!m_myRefCounts.get(node)) 386 break; 387 if (m_graph.m_form == ThreadedCPS) 388 VALIDATE((node, block), getLocalPositions.operand(node->local()) == notSet); 389 getLocalPositions.operand(node->local()) = i; 390 break; 391 case SetLocal: 392 if (node->variableAccessData()->isCaptured()) 393 break; 394 // Only record the first SetLocal. There may be multiple SetLocals 395 // because of flushing. 396 if (setLocalPositions.operand(node->local()) != notSet) 397 break; 398 setLocalPositions.operand(node->local()) = i; 399 break; 400 default: 401 break; 402 } 403 } 404 405 if (m_graph.m_form == LoadStore) 406 continue; 407 408 for (size_t i = 0; i < block->variablesAtHead.numberOfArguments(); ++i) { 409 checkOperand( 410 block, getLocalPositions, setLocalPositions, virtualRegisterForArgument(i)); 411 } 412 for (size_t i = 0; i < block->variablesAtHead.numberOfLocals(); ++i) { 413 checkOperand( 414 block, getLocalPositions, setLocalPositions, virtualRegisterForLocal(i)); 415 } 416 } 417 } 418 419 void validateSSA() 420 { 421 // FIXME: Add more things here. 422 // https://bugs.webkit.org/show_bug.cgi?id=123471 423 424 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) { 425 BasicBlock* block = m_graph.block(blockIndex); 426 if (!block) 427 continue; 428 429 unsigned nodeIndex = 0; 430 for (; nodeIndex < block->size() && !block->at(nodeIndex)->origin.isSet(); nodeIndex++) { } 431 432 VALIDATE((block), nodeIndex < block->size()); 433 434 for (; nodeIndex < block->size(); nodeIndex++) 435 VALIDATE((block->at(nodeIndex)), block->at(nodeIndex)->origin.isSet()); 436 437 for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) { 438 Node* node = block->at(nodeIndex); 439 switch (node->op()) { 440 case Phi: 441 VALIDATE((node), !node->origin.isSet()); 442 break; 443 444 default: 445 // FIXME: Add more things here. 446 // https://bugs.webkit.org/show_bug.cgi?id=123471 447 break; 448 } 449 } 450 } 451 } 452 453 void checkOperand( 454 BasicBlock* block, Operands<size_t>& getLocalPositions, 455 Operands<size_t>& setLocalPositions, VirtualRegister operand) 456 { 457 if (getLocalPositions.operand(operand) == notSet) 458 return; 459 if (setLocalPositions.operand(operand) == notSet) 460 return; 461 462 VALIDATE( 463 (block->at(getLocalPositions.operand(operand)), 464 block->at(setLocalPositions.operand(operand)), 465 block), 466 getLocalPositions.operand(operand) < setLocalPositions.operand(operand)); 467 } 468 469 void reportValidationContext(Node* node) 470 { 471 dataLogF("@%u", node->index()); 472 } 473 474 void reportValidationContext(BasicBlock* block) 475 { 476 dataLog("Block ", *block); 477 } 478 479 void reportValidationContext(Node* node, Edge edge) 480 { 481 dataLog(node, " -> ", edge); 482 } 483 484 void reportValidationContext(VirtualRegister local, BasicBlock* block) 485 { 486 if (!block) { 487 dataLog("r", local, " in null Block "); 488 return; 489 } 490 491 dataLog("r", local, " in Block ", *block); 492 } 493 494 void reportValidationContext( 495 VirtualRegister local, BasicBlock* sourceBlock, BasicBlock* destinationBlock) 496 { 497 dataLog("r", local, " in Block ", *sourceBlock, " -> ", *destinationBlock); 498 } 499 500 void reportValidationContext( 501 VirtualRegister local, BasicBlock* sourceBlock, Node* prevNode) 502 { 503 dataLog(prevNode, " for r", local, " in Block ", *sourceBlock); 504 } 505 506 void reportValidationContext(Node* node, BasicBlock* block) 507 { 508 dataLog(node, " in Block ", *block); 509 } 510 511 void reportValidationContext(Node* node, Node* node2, BasicBlock* block) 512 { 513 dataLog(node, " and ", node2, " in Block ", *block); 514 } 515 516 void reportValidationContext( 517 Node* node, BasicBlock* block, Node* expectedNode, Edge incomingEdge) 518 { 519 dataLog(node, " in Block ", *block, ", searching for ", expectedNode, " from ", incomingEdge); 520 } 521 522 void dumpGraphIfAppropriate() 523 { 524 if (m_graphDumpMode == DontDumpGraph) 525 return; 526 dataLog("At time of failure:\n"); 527 m_graph.dump(); 528 } 529}; 530 531void validate(Graph& graph, GraphDumpMode graphDumpMode) 532{ 533 Validate validationObject(graph, graphDumpMode); 534 validationObject.validate(); 535} 536 537} } // namespace JSC::DFG 538 539#endif // ENABLE(DFG_JIT) 540 541