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