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.m_blocks[0].get();
  80         for (unsigned i = 0; i < root->variablesAtHead.numberOfLocals(); ++i)
  81             V_EQUAL((static_cast<VirtualRegister>(i), 0), static_cast<Node*>(0), root->variablesAtHead.local(i));
  82
  83         // Validate ref counts and uses.
  84         HashMap<Node*, unsigned> myRefCounts;
  85         for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
  86             BasicBlock* block = m_graph.m_blocks[blockIndex].get();
  87             if (!block || !block->isReachable)
  88                 continue;
  89             for (size_t i = 0; i < block->numNodes(); ++i)
  90                 myRefCounts.add(block->node(i), 0);
  91         }
  92         HashSet<Node*> acceptableNodes;
  93         for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
  94             BasicBlock* block = m_graph.m_blocks[blockIndex].get();
  95             if (!block || !block->isReachable)
  96                 continue;
  97             for (size_t i = 0; i < block->numNodes(); ++i) {
  98                 Node* node = block->node(i);
  99                 acceptableNodes.add(node);
 100                 if (!node->shouldGenerate())
 101                     continue;
 102                 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
 103                     // Phi children in LoadStore form are invalid.
 104                     if (m_graph.m_form == LoadStore && block->isPhiIndex(i))
 105                         continue;
 106
 107                     Edge edge = m_graph.child(node, j);
 108                     if (!edge)
 109                         continue;
 110
 111                     myRefCounts.find(edge.node())->value++;
 112
 113                     // Unless I'm a Flush, Phantom, GetLocal, or Phi, my children should hasResult().
 114                     switch (node->op()) {
 115                     case Flush:
 116                     case GetLocal:
 117                         VALIDATE((node, edge), edge->hasVariableAccessData());
 118                         VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData());
 119                         break;
 120                     case PhantomLocal:
 121                         VALIDATE((node, edge), edge->hasVariableAccessData());
 122                         VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData());
 123                         VALIDATE((node, edge), edge->op() != SetLocal);
 124                         break;
 125                     case Phi:
 126                         VALIDATE((node, edge), edge->hasVariableAccessData());
 127                         if (m_graph.m_unificationState == LocallyUnified)
 128                             break;
 129                         VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData());
 130                         break;
 131                     case Phantom:
 132                         switch (m_graph.m_form) {
 133                         case LoadStore:
 134                             if (j) {
 135                                 VALIDATE((node, edge), edge->hasResult());
 136                                 break;
 137                             }
 138                             switch (edge->op()) {
 139                             case Phi:
 140                             case SetArgument:
 141                             case SetLocal:
 142                                 break;
 143                             default:
 144                                 VALIDATE((node, edge), edge->hasResult());
 145                                 break;
 146                             }
 147                             break;
 148                         case ThreadedCPS:
 149                             VALIDATE((node, edge), edge->hasResult());
 150                             break;
 151                         }
 152                         break;
 153                     default:
 154                         VALIDATE((node, edge), edge->hasResult());
 155                         break;
 156                     }
 157                 }
 158             }
 159         }
 160         for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
 161             BasicBlock* block = m_graph.m_blocks[blockIndex].get();
 162             if (!block || !block->isReachable)
 163                 continue;
 164
 165             HashSet<Node*> phisInThisBlock;
 166             HashSet<Node*> nodesInThisBlock;
 167
 168             for (size_t i = 0; i < block->numNodes(); ++i) {
 169                 Node* node = block->node(i);
 170                 nodesInThisBlock.add(node);
 171                 if (block->isPhiIndex(i))
 172                     phisInThisBlock.add(node);
 173                 if (m_graph.m_refCountState == ExactRefCount)
 174                     V_EQUAL((node), myRefCounts.get(node), node->adjustedRefCount());
 175                 else
 176                     V_EQUAL((node), node->refCount(), 1);
 177                 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
 178                     Edge edge = m_graph.child(node, j);
 179                     if (!edge)
 180                         continue;
 181                     VALIDATE((node, edge), acceptableNodes.contains(edge.node()));
 182                 }
 183             }
 184
 185             for (size_t i = 0; i < block->phis.size(); ++i) {
 186                 Node* node = block->phis[i];
 187                 ASSERT(phisInThisBlock.contains(node));
 188                 VALIDATE((node), node->op() == Phi);
 189                 VirtualRegister local = node->local();
 190                 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
 191                     // Phi children in LoadStore form are invalid.
 192                     if (m_graph.m_form == LoadStore && block->isPhiIndex(i))
 193                         continue;
 194
 195                     Edge edge = m_graph.child(node, j);
 196                     if (!edge)
 197                         continue;
 198
 199                     VALIDATE(
 200                         (node, edge),
 201                         edge->op() == SetLocal
 202                         || edge->op() == SetArgument
 203                         || edge->op() == Flush
 204                         || edge->op() == Phi
 205                         || edge->op() == ZombieHint
 206                         || edge->op() == MovHint
 207                         || edge->op() == MovHintAndCheck);
 208
 209                     if (phisInThisBlock.contains(edge.node()))
 210                         continue;
 211
 212                     if (nodesInThisBlock.contains(edge.node())) {
 213                         VALIDATE(
 214                             (node, edge),
 215                             edge->op() == SetLocal
 216                             || edge->op() == ZombieHint
 217                             || edge->op() == MovHint
 218                             || edge->op() == MovHintAndCheck
 219                             || edge->op() == SetArgument
 220                             || edge->op() == Flush);
 221
 222                         continue;
 223                     }
 224
 225                     // There must exist a predecessor block that has this node index in
 226                     // its tail variables.
 227                     bool found = false;
 228                     for (unsigned k = 0; k < block->m_predecessors.size(); ++k) {
 229                         BasicBlock* prevBlock = m_graph.m_blocks[block->m_predecessors[k]].get();
 230                         VALIDATE((Block, block->m_predecessors[k]), prevBlock);
 231                         VALIDATE((Block, block->m_predecessors[k]), prevBlock->isReachable);
 232                         Node* prevNode = prevBlock->variablesAtTail.operand(local);
 233                         // If we have a Phi that is not referring to *this* block then all predecessors
 234                         // must have that local available.
 235                         VALIDATE((local, blockIndex, Block, block->m_predecessors[k]), prevNode);
 236                         switch (prevNode->op()) {
 237                         case GetLocal:
 238                         case Flush:
 239                         case PhantomLocal:
 240                             prevNode = prevNode->child1().node();
 241                             break;
 242                         default:
 243                             break;
 244                         }
 245                         if (node->shouldGenerate()) {
 246                             VALIDATE((local, block->m_predecessors[k], prevNode),
 247                                      prevNode->shouldGenerate());
 248                         }
 249                         VALIDATE(
 250                             (local, block->m_predecessors[k], prevNode),
 251                             prevNode->op() == SetLocal
 252                             || prevNode->op() == MovHint
 253                             || prevNode->op() == MovHintAndCheck
 254                             || prevNode->op() == ZombieHint
 255                             || prevNode->op() == SetArgument
 256                             || prevNode->op() == Phi);
 257                         if (prevNode == edge.node()) {
 258                             found = true;
 259                             break;
 260                         }
 261                         // At this point it cannot refer into this block.
 262                         VALIDATE((local, block->m_predecessors[k], prevNode), !prevBlock->isInBlock(edge.node()));
 263                     }
 264
 265                     VALIDATE((node, edge), found);
 266                 }
 267             }
 268
 269             Operands<size_t> getLocalPositions(
 270                 block->variablesAtHead.numberOfArguments(),
 271                 block->variablesAtHead.numberOfLocals());
 272             Operands<size_t> setLocalPositions(
 273                 block->variablesAtHead.numberOfArguments(),
 274                 block->variablesAtHead.numberOfLocals());
 275
 276             for (size_t i = 0; i < block->variablesAtHead.numberOfArguments(); ++i) {
 277                 VALIDATE((static_cast<VirtualRegister>(argumentToOperand(i)), blockIndex), !block->variablesAtHead.argument(i) || block->variablesAtHead.argument(i)->hasVariableAccessData());
 278                 if (m_graph.m_form == ThreadedCPS)
 279                     VALIDATE((static_cast<VirtualRegister>(argumentToOperand(i)), blockIndex), !block->variablesAtTail.argument(i) || block->variablesAtTail.argument(i)->hasVariableAccessData());
 280
 281                 getLocalPositions.argument(i) = notSet;
 282                 setLocalPositions.argument(i) = notSet;
 283             }
 284             for (size_t i = 0; i < block->variablesAtHead.numberOfLocals(); ++i) {
 285                 VALIDATE((static_cast<VirtualRegister>(i), blockIndex), !block->variablesAtHead.local(i) || block->variablesAtHead.local(i)->hasVariableAccessData());
 286                 if (m_graph.m_form == ThreadedCPS)
 287                     VALIDATE((static_cast<VirtualRegister>(i), blockIndex), !block->variablesAtTail.local(i) || block->variablesAtTail.local(i)->hasVariableAccessData());
 288
 289                 getLocalPositions.local(i) = notSet;
 290                 setLocalPositions.local(i) = notSet;
 291             }
 292
 293             for (size_t i = 0; i < block->size(); ++i) {
 294                 Node* node = block->at(i);
 295                 ASSERT(nodesInThisBlock.contains(node));
 296                 VALIDATE((node), node->op() != Phi);
 297                 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
 298                     Edge edge = m_graph.child(node, j);
 299                     if (!edge)
 300                         continue;
 301                     VALIDATE((node, edge), nodesInThisBlock.contains(edge.node()));
 302                     switch (node->op()) {
 303                     case PhantomLocal:
 304                     case GetLocal:
 305                     case Flush:
 306                         break;
 307                     case Phantom:
 308                         if (m_graph.m_form == LoadStore && !j)
 309                             break;
 310                     default:
 311                         VALIDATE((node, edge), !phisInThisBlock.contains(edge.node()));
 312                         break;
 313                     }
 314                 }
 315
 316                 if (!node->shouldGenerate())
 317                     continue;
 318                 switch (node->op()) {
 319                 case GetLocal:
 320                     if (node->variableAccessData()->isCaptured())
 321                         break;
 322                     // Ignore GetLocal's that we know to be dead, but that the graph
 323                     // doesn't yet know to be dead.
 324                     if (!myRefCounts.get(node))
 325                         break;
 326                     if (m_graph.m_form == ThreadedCPS)
 327                         VALIDATE((node, blockIndex), getLocalPositions.operand(node->local()) == notSet);
 328                     getLocalPositions.operand(node->local()) = i;
 329                     break;
 330                 case SetLocal:
 331                     if (node->variableAccessData()->isCaptured())
 332                         break;
 333                     // Only record the first SetLocal. There may be multiple SetLocals
 334                     // because of flushing.
 335                     if (setLocalPositions.operand(node->local()) != notSet)
 336                         break;
 337                     setLocalPositions.operand(node->local()) = i;
 338                     break;
 339                 default:
 340                     break;
 341                 }
 342             }
 343
 344             if (m_graph.m_form == LoadStore)
 345                 continue;
 346
 347             for (size_t i = 0; i < block->variablesAtHead.numberOfArguments(); ++i) {
 348                 checkOperand(
 349                     blockIndex, getLocalPositions, setLocalPositions, argumentToOperand(i));
 350             }
 351             for (size_t i = 0; i < block->variablesAtHead.numberOfLocals(); ++i) {
 352                 checkOperand(
 353                     blockIndex, getLocalPositions, setLocalPositions, i);
 354             }
 355         }
 356     }
 357
 358 private:
 359     Graph& m_graph;
 360     GraphDumpMode m_graphDumpMode;
 361
 362     void checkOperand(
 363         BlockIndex blockIndex, Operands<size_t>& getLocalPositions,
 364         Operands<size_t>& setLocalPositions, int operand)
 365     {
 366         if (getLocalPositions.operand(operand) == notSet)
 367             return;
 368         if (setLocalPositions.operand(operand) == notSet)
 369             return;
 370
 371         BasicBlock* block = m_graph.m_blocks[blockIndex].get();
 372
 373         VALIDATE(
 374             (block->at(getLocalPositions.operand(operand)),
 375              block->at(setLocalPositions.operand(operand)),
 376              blockIndex),
 377             getLocalPositions.operand(operand) < setLocalPositions.operand(operand));
 378     }
 379
 380     void reportValidationContext(Node* node)
 381     {
 382         dataLogF("@%u", node->index());
 383     }
 384
 385     enum BlockTag { Block };
 386     void reportValidationContext(BlockTag, BlockIndex blockIndex)
 387     {
 388         dataLogF("Block #%u", blockIndex);
 389     }
 390
 391     void reportValidationContext(Node* node, Edge edge)
 392     {
 393         dataLog(node, " -> ", edge);
 394     }
 395
 396     void reportValidationContext(VirtualRegister local, BlockIndex blockIndex)
 397     {
 398         dataLogF("r%d in Block #%u", local, blockIndex);
 399     }
 400
 401     void reportValidationContext(
 402         VirtualRegister local, BlockIndex sourceBlockIndex, BlockTag, BlockIndex destinationBlockIndex)
 403     {
 404         dataLogF("r%d in Block #%u -> #%u", local, sourceBlockIndex, destinationBlockIndex);
 405     }
 406
 407     void reportValidationContext(
 408         VirtualRegister local, BlockIndex sourceBlockIndex, Node* prevNode)
 409     {
 410         dataLogF("@%u for r%d in Block #%u", prevNode->index(), local, sourceBlockIndex);
 411     }
 412
 413     void reportValidationContext(
 414         Node* node, BlockIndex blockIndex)
 415     {
 416         dataLogF("@%u in Block #%u", node->index(), blockIndex);
 417     }
 418
 419     void reportValidationContext(
 420         Node* node, Node* node2, BlockIndex blockIndex)
 421     {
 422         dataLogF("@%u and @%u in Block #%u", node->index(), node2->index(), blockIndex);
 423     }
 424
 425     void reportValidationContext(
 426         Node* node, BlockIndex blockIndex, Node* expectedNode, Edge incomingEdge)
 427     {
 428         dataLog(node, " in Block #", blockIndex, ", searching for ", expectedNode, " from ", incomingEdge);
 429     }
 430
 431     void dumpGraphIfAppropriate()
 432     {
 433         if (m_graphDumpMode == DontDumpGraph)
 434             return;
 435         dataLog("At time of failure:\n");
 436         m_graph.dump();
 437     }
 438 };
 439
 440 void validate(Graph& graph, GraphDumpMode graphDumpMode)
 441 {
 442     Validate validationObject(graph, graphDumpMode);
 443     validationObject.validate();
 444 }
 445
 446 } } // namespace JSC::DFG
 447
 448 #endif // ENABLE(DFG_JIT)
 449