dfg/DFGValidate.cpp

   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
  36 namespace JSC { namespace DFG {
  37
  38 class Validate {
  39 public:
  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
 225 private:
 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
 531 void 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