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