DFG should have control flow graph simplification
[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             dataLog("\n\n\nAt "); \
49             reportValidationContext context; \
50             dataLog(": 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             dataLog("\n\n\nAt "); \
60             reportValidationContext context; \
61             dataLog(": validation (%s = ", #left); \
62             dumpData(left); \
63             dataLog(") == (%s = ", #right); \
64             dumpData(right); \
65             dataLog(") (%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     void validate()
73     {
74         // NB. This code is not written for performance, since it is not intended to run
75         // in release builds.
76         
77         // Validate ref counts and uses.
78         Vector<unsigned> myRefCounts;
79         myRefCounts.fill(0, m_graph.size());
80         BitVector acceptableNodeIndices;
81         for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
82             BasicBlock* block = m_graph.m_blocks[blockIndex].get();
83             if (!block)
84                 continue;
85             if (!block->isReachable)
86                 continue;
87             for (size_t i = 0; i < block->numNodes(); ++i) {
88                 NodeIndex nodeIndex = block->nodeIndex(i);
89                 acceptableNodeIndices.set(nodeIndex);
90                 Node& node = m_graph[nodeIndex];
91                 if (!node.shouldGenerate())
92                     continue;
93                 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
94                     Edge edge = m_graph.child(node, j);
95                     if (!edge)
96                         continue;
97                     
98                     myRefCounts[edge.index()]++;
99                     
100                     // Unless I'm a Flush, Phantom, GetLocal, or Phi, my children should hasResult().
101                     switch (node.op()) {
102                     case Flush:
103                     case Phantom:
104                     case GetLocal:
105                     case Phi:
106                         break;
107                     default:
108                         VALIDATE((nodeIndex, edge), m_graph[edge].hasResult());
109                         break;
110                     }
111                 }
112             }
113         }
114         for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
115             BasicBlock* block = m_graph.m_blocks[blockIndex].get();
116             if (!block)
117                 continue;
118             if (!block->isReachable)
119                 continue;
120             
121             BitVector phisInThisBlock;
122             BitVector nodesInThisBlock;
123             
124             for (size_t i = 0; i < block->numNodes(); ++i) {
125                 NodeIndex nodeIndex = block->nodeIndex(i);
126                 Node& node = m_graph[nodeIndex];
127                 nodesInThisBlock.set(nodeIndex);
128                 if (block->isPhiIndex(i))
129                     phisInThisBlock.set(nodeIndex);
130                 V_EQUAL((nodeIndex), myRefCounts[nodeIndex], node.adjustedRefCount());
131                 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
132                     Edge edge = m_graph.child(node, j);
133                     if (!edge)
134                         continue;
135                     VALIDATE((nodeIndex, edge), acceptableNodeIndices.get(edge.index()));
136                 }
137             }
138             
139             for (size_t i = 0; i < block->phis.size(); ++i) {
140                 NodeIndex nodeIndex = block->phis[i];
141                 Node& node = m_graph[nodeIndex];
142                 ASSERT(phisInThisBlock.get(nodeIndex));
143                 VALIDATE((nodeIndex), node.op() == Phi);
144                 VirtualRegister local = node.local();
145                 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
146                     Edge edge = m_graph.child(node, j);
147                     if (!edge)
148                         continue;
149                     
150                     VALIDATE((nodeIndex, edge),
151                              m_graph[edge].op() == SetLocal
152                              || m_graph[edge].op() == SetArgument
153                              || m_graph[edge].op() == Flush
154                              || m_graph[edge].op() == Phi);
155                     
156                     if (phisInThisBlock.get(edge.index()))
157                         continue;
158                     
159                     if (nodesInThisBlock.get(edge.index())) {
160                         VALIDATE((nodeIndex, edge),
161                                  m_graph[edge].op() == SetLocal
162                                  || m_graph[edge].op() == SetArgument
163                                  || m_graph[edge].op() == Flush);
164                         
165                         continue;
166                     }
167                     
168                     // There must exist a predecessor block that has this node index in
169                     // its tail variables.
170                     bool found = false;
171                     for (unsigned k = 0; k < block->m_predecessors.size(); ++k) {
172                         BasicBlock* prevBlock = m_graph.m_blocks[block->m_predecessors[k]].get();
173                         VALIDATE((Block, block->m_predecessors[k]), prevBlock);
174                         VALIDATE((Block, block->m_predecessors[k]), prevBlock->isReachable);
175                         NodeIndex prevNodeIndex = prevBlock->variablesAtTail.operand(local);
176                         // If we have a Phi that is not referring to *this* block then all predecessors
177                         // must have that local available.
178                         VALIDATE((local, blockIndex, Block, block->m_predecessors[k]), prevNodeIndex != NoNode);
179                         Node* prevNode = &m_graph[prevNodeIndex];
180                         if (prevNode->op() == GetLocal) {
181                             prevNodeIndex = prevNode->child1().index();
182                             prevNode = &m_graph[prevNodeIndex];
183                         }
184                         if (node.shouldGenerate()) {
185                             VALIDATE((local, block->m_predecessors[k], prevNodeIndex),
186                                      prevNode->shouldGenerate());
187                         }
188                         VALIDATE((local, block->m_predecessors[k], prevNodeIndex),
189                                  prevNode->op() == SetLocal
190                                  || prevNode->op() == SetArgument
191                                  || prevNode->op() == Flush
192                                  || prevNode->op() == Phi);
193                         if (prevNodeIndex == edge.index()) {
194                             found = true;
195                             break;
196                         }
197                         // At this point it cannot refer into this block.
198                         VALIDATE((local, block->m_predecessors[k], prevNodeIndex), !prevBlock->isInBlock(edge.index()));
199                     }
200                     
201                     VALIDATE((nodeIndex, edge), found);
202                 }
203             }
204             
205             for (size_t i = 0; i < block->size(); ++i) {
206                 NodeIndex nodeIndex = block->at(i);
207                 Node& node = m_graph[nodeIndex];
208                 ASSERT(nodesInThisBlock.get(nodeIndex));
209                 VALIDATE((nodeIndex), node.op() != Phi);
210                 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
211                     Edge edge = m_graph.child(node, j);
212                     if (!edge)
213                         continue;
214                     VALIDATE((nodeIndex, edge), nodesInThisBlock.get(nodeIndex));
215                 }
216             }
217         }
218     }
219     
220 private:
221     Graph& m_graph;
222     GraphDumpMode m_graphDumpMode;
223     
224     void reportValidationContext(NodeIndex nodeIndex)
225     {
226         dataLog("@%u", nodeIndex);
227     }
228     
229     enum BlockTag { Block };
230     void reportValidationContext(BlockTag, BlockIndex blockIndex)
231     {
232         dataLog("Block #%u", blockIndex);
233     }
234     
235     void reportValidationContext(NodeIndex nodeIndex, Edge edge)
236     {
237         dataLog("@%u -> %s@%u", nodeIndex, useKindToString(edge.useKind()), edge.index());
238     }
239     
240     void reportValidationContext(
241         VirtualRegister local, BlockIndex sourceBlockIndex, BlockTag, BlockIndex destinationBlockIndex)
242     {
243         dataLog("r%d in Block #%u -> #%u", local, sourceBlockIndex, destinationBlockIndex);
244     }
245     
246     void reportValidationContext(
247         VirtualRegister local, BlockIndex sourceBlockIndex, NodeIndex prevNodeIndex)
248     {
249         dataLog("@%u for r%d in Block #%u", prevNodeIndex, local, sourceBlockIndex);
250     }
251     
252     void reportValidationContext(
253         NodeIndex nodeIndex, BlockIndex blockIndex)
254     {
255         dataLog("@%u in Block #%u", nodeIndex, blockIndex);
256     }
257     
258     void reportValidationContext(
259         NodeIndex nodeIndex, BlockIndex blockIndex, NodeIndex expectedNodeIndex, Edge incomingEdge)
260     {
261         dataLog("@%u in Block #%u, searching for @%u from @%u", nodeIndex, blockIndex, expectedNodeIndex, incomingEdge.index());
262     }
263     
264     void dumpData(unsigned value)
265     {
266         dataLog("%u", value);
267     }
268     
269     void dumpGraphIfAppropriate()
270     {
271         if (m_graphDumpMode == DontDumpGraph)
272             return;
273         dataLog("Graph at time of failure:\n");
274         m_graph.dump();
275     }
276 };
277
278 void validate(Graph& graph, GraphDumpMode graphDumpMode)
279 {
280     Validate validationObject(graph, graphDumpMode);
281     validationObject.validate();
282 }
283
284 #endif // DFG_ENABLE(VALIDATION)
285
286 } } // namespace JSC::DFG
287
288 #endif // ENABLE(DFG_JIT)
289