b946e466b840e06c2ad389eabda5210c77a06b26
[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 #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((virtualRegisterForLocal(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((virtualRegisterForArgument(i), block), !block->variablesAtHead.argument(i) || block->variablesAtHead.argument(i)->hasVariableAccessData(m_graph));
321                 if (m_graph.m_form == ThreadedCPS)
322                     VALIDATE((virtualRegisterForArgument(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((virtualRegisterForLocal(i), block), !block->variablesAtHead.local(i) || block->variablesAtHead.local(i)->hasVariableAccessData(m_graph));
329                 if (m_graph.m_form == ThreadedCPS)
330                     VALIDATE((virtualRegisterForLocal(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, virtualRegisterForArgument(i));
393             }
394             for (size_t i = 0; i < block->variablesAtHead.numberOfLocals(); ++i) {
395                 checkOperand(
396                     block, getLocalPositions, setLocalPositions, virtualRegisterForLocal(i));
397             }
398         }
399     }
400     
401     void checkOperand(
402         BasicBlock* block, Operands<size_t>& getLocalPositions,
403         Operands<size_t>& setLocalPositions, VirtualRegister 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", local, " in null Block ");
436             return;
437         }
438
439         dataLog("r", local, " in Block ", *block);
440     }
441     
442     void reportValidationContext(
443         VirtualRegister local, BasicBlock* sourceBlock, BasicBlock* destinationBlock)
444     {
445         dataLog("r", local, " in Block ", *sourceBlock, " -> ", *destinationBlock);
446     }
447     
448     void reportValidationContext(
449         VirtualRegister local, BasicBlock* sourceBlock, Node* prevNode)
450     {
451         dataLog(prevNode, " for r", 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