Rename dataLog() and dataLogV() to dataLogF() and dataLogFV()
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGValidate.cpp
1 /*
2  * Copyright (C) 2012 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 <wtf/Assertions.h>
32 #include <wtf/BitVector.h>
33
34 namespace JSC { namespace DFG {
35
36 #if DFG_ENABLE(VALIDATION)
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             dataLogF("\n\n\nAt "); \
49             reportValidationContext context; \
50             dataLogF(": validation %s (%s:%d) failed.\n", #assertion, __FILE__, __LINE__); \
51             dumpGraphIfAppropriate(); \
52             WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #assertion); \
53             CRASH(); \
54         } \
55     } while (0)
56     
57     #define V_EQUAL(context, left, right) do { \
58         if (left != right) { \
59             dataLogF("\n\n\nAt "); \
60             reportValidationContext context; \
61             dataLogF(": validation (%s = ", #left); \
62             dumpData(left); \
63             dataLogF(") == (%s = ", #right); \
64             dumpData(right); \
65             dataLogF(") (%s:%d) failed.\n", __FILE__, __LINE__); \
66             dumpGraphIfAppropriate(); \
67             WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #left " == " #right); \
68             CRASH(); \
69         } \
70     } while (0)
71
72     #define notSet (static_cast<size_t>(-1))
73
74     void validate()
75     {
76         // NB. This code is not written for performance, since it is not intended to run
77         // in release builds.
78         
79         // Validate ref counts and uses.
80         Vector<unsigned> myRefCounts;
81         myRefCounts.fill(0, m_graph.size());
82         BitVector acceptableNodeIndices;
83         for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
84             BasicBlock* block = m_graph.m_blocks[blockIndex].get();
85             if (!block)
86                 continue;
87             if (!block->isReachable)
88                 continue;
89             for (size_t i = 0; i < block->numNodes(); ++i) {
90                 NodeIndex nodeIndex = block->nodeIndex(i);
91                 acceptableNodeIndices.set(nodeIndex);
92                 Node& node = m_graph[nodeIndex];
93                 if (!node.shouldGenerate())
94                     continue;
95                 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
96                     Edge edge = m_graph.child(node, j);
97                     if (!edge)
98                         continue;
99                     
100                     myRefCounts[edge.index()]++;
101                     
102                     // Unless I'm a Flush, Phantom, GetLocal, or Phi, my children should hasResult().
103                     switch (node.op()) {
104                     case Flush:
105                     case Phantom:
106                     case GetLocal:
107                     case Phi:
108                         break;
109                     default:
110                         VALIDATE((nodeIndex, edge), m_graph[edge].hasResult());
111                         break;
112                     }
113                 }
114             }
115         }
116         for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
117             BasicBlock* block = m_graph.m_blocks[blockIndex].get();
118             if (!block)
119                 continue;
120             if (!block->isReachable)
121                 continue;
122             
123             BitVector phisInThisBlock;
124             BitVector nodesInThisBlock;
125             
126             for (size_t i = 0; i < block->numNodes(); ++i) {
127                 NodeIndex nodeIndex = block->nodeIndex(i);
128                 Node& node = m_graph[nodeIndex];
129                 nodesInThisBlock.set(nodeIndex);
130                 if (block->isPhiIndex(i))
131                     phisInThisBlock.set(nodeIndex);
132                 V_EQUAL((nodeIndex), myRefCounts[nodeIndex], node.adjustedRefCount());
133                 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
134                     Edge edge = m_graph.child(node, j);
135                     if (!edge)
136                         continue;
137                     VALIDATE((nodeIndex, edge), acceptableNodeIndices.get(edge.index()));
138                 }
139             }
140             
141             for (size_t i = 0; i < block->phis.size(); ++i) {
142                 NodeIndex nodeIndex = block->phis[i];
143                 Node& node = m_graph[nodeIndex];
144                 ASSERT(phisInThisBlock.get(nodeIndex));
145                 VALIDATE((nodeIndex), node.op() == Phi);
146                 VirtualRegister local = node.local();
147                 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
148                     Edge edge = m_graph.child(node, j);
149                     if (!edge)
150                         continue;
151                     
152                     VALIDATE((nodeIndex, edge),
153                              m_graph[edge].op() == SetLocal
154                              || m_graph[edge].op() == SetArgument
155                              || m_graph[edge].op() == Flush
156                              || m_graph[edge].op() == Phi);
157                     
158                     if (phisInThisBlock.get(edge.index()))
159                         continue;
160                     
161                     if (nodesInThisBlock.get(edge.index())) {
162                         VALIDATE((nodeIndex, edge),
163                                  m_graph[edge].op() == SetLocal
164                                  || m_graph[edge].op() == SetArgument
165                                  || m_graph[edge].op() == Flush);
166                         
167                         continue;
168                     }
169                     
170                     // There must exist a predecessor block that has this node index in
171                     // its tail variables.
172                     bool found = false;
173                     for (unsigned k = 0; k < block->m_predecessors.size(); ++k) {
174                         BasicBlock* prevBlock = m_graph.m_blocks[block->m_predecessors[k]].get();
175                         VALIDATE((Block, block->m_predecessors[k]), prevBlock);
176                         VALIDATE((Block, block->m_predecessors[k]), prevBlock->isReachable);
177                         NodeIndex prevNodeIndex = prevBlock->variablesAtTail.operand(local);
178                         // If we have a Phi that is not referring to *this* block then all predecessors
179                         // must have that local available.
180                         VALIDATE((local, blockIndex, Block, block->m_predecessors[k]), prevNodeIndex != NoNode);
181                         Node* prevNode = &m_graph[prevNodeIndex];
182                         if (prevNode->op() == GetLocal) {
183                             prevNodeIndex = prevNode->child1().index();
184                             prevNode = &m_graph[prevNodeIndex];
185                         }
186                         if (node.shouldGenerate()) {
187                             VALIDATE((local, block->m_predecessors[k], prevNodeIndex),
188                                      prevNode->shouldGenerate());
189                         }
190                         VALIDATE((local, block->m_predecessors[k], prevNodeIndex),
191                                  prevNode->op() == SetLocal
192                                  || prevNode->op() == SetArgument
193                                  || prevNode->op() == Flush
194                                  || prevNode->op() == Phi);
195                         if (prevNodeIndex == edge.index()) {
196                             found = true;
197                             break;
198                         }
199                         // At this point it cannot refer into this block.
200                         VALIDATE((local, block->m_predecessors[k], prevNodeIndex), !prevBlock->isInBlock(edge.index()));
201                     }
202                     
203                     VALIDATE((nodeIndex, edge), found);
204                 }
205             }
206             
207             Operands<size_t> getLocalPositions(
208                 block->variablesAtHead.numberOfArguments(),
209                 block->variablesAtHead.numberOfLocals());
210             Operands<size_t> setLocalPositions(
211                 block->variablesAtHead.numberOfArguments(),
212                 block->variablesAtHead.numberOfLocals());
213             
214             for (size_t i = 0; i < block->variablesAtHead.numberOfArguments(); ++i) {
215                 getLocalPositions.argument(i) = notSet;
216                 setLocalPositions.argument(i) = notSet;
217             }
218             for (size_t i = 0; i < block->variablesAtHead.numberOfLocals(); ++i) {
219                 getLocalPositions.local(i) = notSet;
220                 setLocalPositions.local(i) = notSet;
221             }
222             
223             for (size_t i = 0; i < block->size(); ++i) {
224                 NodeIndex nodeIndex = block->at(i);
225                 Node& node = m_graph[nodeIndex];
226                 ASSERT(nodesInThisBlock.get(nodeIndex));
227                 VALIDATE((nodeIndex), node.op() != Phi);
228                 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
229                     Edge edge = m_graph.child(node, j);
230                     if (!edge)
231                         continue;
232                     VALIDATE((nodeIndex, edge), nodesInThisBlock.get(nodeIndex));
233                 }
234                 
235                 if (!node.shouldGenerate())
236                     continue;
237                 switch (node.op()) {
238                 case GetLocal:
239                     if (node.variableAccessData()->isCaptured())
240                         break;
241                     VALIDATE((nodeIndex, blockIndex), getLocalPositions.operand(node.local()) == notSet);
242                     getLocalPositions.operand(node.local()) = i;
243                     break;
244                 case SetLocal:
245                     if (node.variableAccessData()->isCaptured())
246                         break;
247                     // Only record the first SetLocal. There may be multiple SetLocals
248                     // because of flushing.
249                     if (setLocalPositions.operand(node.local()) != notSet)
250                         break;
251                     setLocalPositions.operand(node.local()) = i;
252                     break;
253                 default:
254                     break;
255                 }
256             }
257             
258             for (size_t i = 0; i < block->variablesAtHead.numberOfArguments(); ++i) {
259                 checkOperand(
260                     blockIndex, getLocalPositions, setLocalPositions, argumentToOperand(i));
261             }
262             for (size_t i = 0; i < block->variablesAtHead.numberOfLocals(); ++i) {
263                 checkOperand(
264                     blockIndex, getLocalPositions, setLocalPositions, i);
265             }
266         }
267     }
268     
269 private:
270     Graph& m_graph;
271     GraphDumpMode m_graphDumpMode;
272     
273     void checkOperand(
274         BlockIndex blockIndex, Operands<size_t>& getLocalPositions,
275         Operands<size_t>& setLocalPositions, int operand)
276     {
277         if (getLocalPositions.operand(operand) == notSet)
278             return;
279         if (setLocalPositions.operand(operand) == notSet)
280             return;
281         
282         BasicBlock* block = m_graph.m_blocks[blockIndex].get();
283         
284         VALIDATE(
285             (block->at(getLocalPositions.operand(operand)),
286              block->at(setLocalPositions.operand(operand)),
287              blockIndex),
288             getLocalPositions.operand(operand) < setLocalPositions.operand(operand));
289     }
290     
291     void reportValidationContext(NodeIndex nodeIndex)
292     {
293         dataLogF("@%u", nodeIndex);
294     }
295     
296     enum BlockTag { Block };
297     void reportValidationContext(BlockTag, BlockIndex blockIndex)
298     {
299         dataLogF("Block #%u", blockIndex);
300     }
301     
302     void reportValidationContext(NodeIndex nodeIndex, Edge edge)
303     {
304         dataLogF("@%u -> %s@%u", nodeIndex, useKindToString(edge.useKind()), edge.index());
305     }
306     
307     void reportValidationContext(
308         VirtualRegister local, BlockIndex sourceBlockIndex, BlockTag, BlockIndex destinationBlockIndex)
309     {
310         dataLogF("r%d in Block #%u -> #%u", local, sourceBlockIndex, destinationBlockIndex);
311     }
312     
313     void reportValidationContext(
314         VirtualRegister local, BlockIndex sourceBlockIndex, NodeIndex prevNodeIndex)
315     {
316         dataLogF("@%u for r%d in Block #%u", prevNodeIndex, local, sourceBlockIndex);
317     }
318     
319     void reportValidationContext(
320         NodeIndex nodeIndex, BlockIndex blockIndex)
321     {
322         dataLogF("@%u in Block #%u", nodeIndex, blockIndex);
323     }
324     
325     void reportValidationContext(
326         NodeIndex nodeIndex, NodeIndex nodeIndex2, BlockIndex blockIndex)
327     {
328         dataLogF("@%u and @%u in Block #%u", nodeIndex, nodeIndex2, blockIndex);
329     }
330     
331     void reportValidationContext(
332         NodeIndex nodeIndex, BlockIndex blockIndex, NodeIndex expectedNodeIndex, Edge incomingEdge)
333     {
334         dataLogF("@%u in Block #%u, searching for @%u from @%u", nodeIndex, blockIndex, expectedNodeIndex, incomingEdge.index());
335     }
336     
337     void dumpData(unsigned value)
338     {
339         dataLogF("%u", value);
340     }
341     
342     void dumpGraphIfAppropriate()
343     {
344         if (m_graphDumpMode == DontDumpGraph)
345             return;
346         dataLogF("Graph at time of failure:\n");
347         m_graph.dump();
348     }
349 };
350
351 void validate(Graph& graph, GraphDumpMode graphDumpMode)
352 {
353     Validate validationObject(graph, graphDumpMode);
354     validationObject.validate();
355 }
356
357 #endif // DFG_ENABLE(VALIDATION)
358
359 } } // namespace JSC::DFG
360
361 #endif // ENABLE(DFG_JIT)
362