Source/JavaScriptCore/dfg/DFGValidate.cpp

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