Imported WebKit commit eb5c1b8fe4d4b1b90b5137433fc58a91da0e6878 (http://svn.webkit.org/repository/webkit/trunk@118516)

1 files changed, 362 insertions, 0 deletions

diff --git a/Source/JavaScriptCore/dfg/DFGValidate.cpp b/Source/JavaScriptCore/dfg/DFGValidate.cpp
new file mode 100644
index 000000000..2b26123d8
--- /dev/null
+++ b/Source/JavaScriptCore/dfg/DFGValidate.cpp
@@ -0,0 +1,362 @@
+/*
+ * Copyright (C) 2012 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "config.h"
+#include "DFGValidate.h"
+
+#if ENABLE(DFG_JIT)
+
+#include <wtf/Assertions.h>
+#include <wtf/BitVector.h>
+
+namespace JSC { namespace DFG {
+
+#if DFG_ENABLE(VALIDATION)
+
+class Validate {
+public:
+    Validate(Graph& graph, GraphDumpMode graphDumpMode)
+        : m_graph(graph)
+        , m_graphDumpMode(graphDumpMode)
+    {
+    }
+    
+    #define VALIDATE(context, assertion) do { \
+        if (!(assertion)) { \
+            dataLog("\n\n\nAt "); \
+            reportValidationContext context; \
+            dataLog(": validation %s (%s:%d) failed.\n", #assertion, __FILE__, __LINE__); \
+            dumpGraphIfAppropriate(); \
+            WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #assertion); \
+            CRASH(); \
+        } \
+    } while (0)
+    
+    #define V_EQUAL(context, left, right) do { \
+        if (left != right) { \
+            dataLog("\n\n\nAt "); \
+            reportValidationContext context; \
+            dataLog(": validation (%s = ", #left); \
+            dumpData(left); \
+            dataLog(") == (%s = ", #right); \
+            dumpData(right); \
+            dataLog(") (%s:%d) failed.\n", __FILE__, __LINE__); \
+            dumpGraphIfAppropriate(); \
+            WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #left " == " #right); \
+            CRASH(); \
+        } \
+    } while (0)
+
+    #define notSet (static_cast<size_t>(-1))
+
+    void validate()
+    {
+        // NB. This code is not written for performance, since it is not intended to run
+        // in release builds.
+        
+        // Validate ref counts and uses.
+        Vector<unsigned> myRefCounts;
+        myRefCounts.fill(0, m_graph.size());
+        BitVector acceptableNodeIndices;
+        for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
+            BasicBlock* block = m_graph.m_blocks[blockIndex].get();
+            if (!block)
+                continue;
+            if (!block->isReachable)
+                continue;
+            for (size_t i = 0; i < block->numNodes(); ++i) {
+                NodeIndex nodeIndex = block->nodeIndex(i);
+                acceptableNodeIndices.set(nodeIndex);
+                Node& node = m_graph[nodeIndex];
+                if (!node.shouldGenerate())
+                    continue;
+                for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
+                    Edge edge = m_graph.child(node, j);
+                    if (!edge)
+                        continue;
+                    
+                    myRefCounts[edge.index()]++;
+                    
+                    // Unless I'm a Flush, Phantom, GetLocal, or Phi, my children should hasResult().
+                    switch (node.op()) {
+                    case Flush:
+                    case Phantom:
+                    case GetLocal:
+                    case Phi:
+                        break;
+                    default:
+                        VALIDATE((nodeIndex, edge), m_graph[edge].hasResult());
+                        break;
+                    }
+                }
+            }
+        }
+        for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
+            BasicBlock* block = m_graph.m_blocks[blockIndex].get();
+            if (!block)
+                continue;
+            if (!block->isReachable)
+                continue;
+            
+            BitVector phisInThisBlock;
+            BitVector nodesInThisBlock;
+            
+            for (size_t i = 0; i < block->numNodes(); ++i) {
+                NodeIndex nodeIndex = block->nodeIndex(i);
+                Node& node = m_graph[nodeIndex];
+                nodesInThisBlock.set(nodeIndex);
+                if (block->isPhiIndex(i))
+                    phisInThisBlock.set(nodeIndex);
+                V_EQUAL((nodeIndex), myRefCounts[nodeIndex], node.adjustedRefCount());
+                for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
+                    Edge edge = m_graph.child(node, j);
+                    if (!edge)
+                        continue;
+                    VALIDATE((nodeIndex, edge), acceptableNodeIndices.get(edge.index()));
+                }
+            }
+            
+            for (size_t i = 0; i < block->phis.size(); ++i) {
+                NodeIndex nodeIndex = block->phis[i];
+                Node& node = m_graph[nodeIndex];
+                ASSERT(phisInThisBlock.get(nodeIndex));
+                VALIDATE((nodeIndex), node.op() == Phi);
+                VirtualRegister local = node.local();
+                for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
+                    Edge edge = m_graph.child(node, j);
+                    if (!edge)
+                        continue;
+                    
+                    VALIDATE((nodeIndex, edge),
+                             m_graph[edge].op() == SetLocal
+                             || m_graph[edge].op() == SetArgument
+                             || m_graph[edge].op() == Flush
+                             || m_graph[edge].op() == Phi);
+                    
+                    if (phisInThisBlock.get(edge.index()))
+                        continue;
+                    
+                    if (nodesInThisBlock.get(edge.index())) {
+                        VALIDATE((nodeIndex, edge),
+                                 m_graph[edge].op() == SetLocal
+                                 || m_graph[edge].op() == SetArgument
+                                 || m_graph[edge].op() == Flush);
+                        
+                        continue;
+                    }
+                    
+                    // There must exist a predecessor block that has this node index in
+                    // its tail variables.
+                    bool found = false;
+                    for (unsigned k = 0; k < block->m_predecessors.size(); ++k) {
+                        BasicBlock* prevBlock = m_graph.m_blocks[block->m_predecessors[k]].get();
+                        VALIDATE((Block, block->m_predecessors[k]), prevBlock);
+                        VALIDATE((Block, block->m_predecessors[k]), prevBlock->isReachable);
+                        NodeIndex prevNodeIndex = prevBlock->variablesAtTail.operand(local);
+                        // If we have a Phi that is not referring to *this* block then all predecessors
+                        // must have that local available.
+                        VALIDATE((local, blockIndex, Block, block->m_predecessors[k]), prevNodeIndex != NoNode);
+                        Node* prevNode = &m_graph[prevNodeIndex];
+                        if (prevNode->op() == GetLocal) {
+                            prevNodeIndex = prevNode->child1().index();
+                            prevNode = &m_graph[prevNodeIndex];
+                        }
+                        if (node.shouldGenerate()) {
+                            VALIDATE((local, block->m_predecessors[k], prevNodeIndex),
+                                     prevNode->shouldGenerate());
+                        }
+                        VALIDATE((local, block->m_predecessors[k], prevNodeIndex),
+                                 prevNode->op() == SetLocal
+                                 || prevNode->op() == SetArgument
+                                 || prevNode->op() == Flush
+                                 || prevNode->op() == Phi);
+                        if (prevNodeIndex == edge.index()) {
+                            found = true;
+                            break;
+                        }
+                        // At this point it cannot refer into this block.
+                        VALIDATE((local, block->m_predecessors[k], prevNodeIndex), !prevBlock->isInBlock(edge.index()));
+                    }
+                    
+                    VALIDATE((nodeIndex, edge), found);
+                }
+            }
+            
+            Operands<size_t> getLocalPositions(
+                block->variablesAtHead.numberOfArguments(),
+                block->variablesAtHead.numberOfLocals());
+            Operands<size_t> setLocalPositions(
+                block->variablesAtHead.numberOfArguments(),
+                block->variablesAtHead.numberOfLocals());
+            
+            for (size_t i = 0; i < block->variablesAtHead.numberOfArguments(); ++i) {
+                getLocalPositions.argument(i) = notSet;
+                setLocalPositions.argument(i) = notSet;
+            }
+            for (size_t i = 0; i < block->variablesAtHead.numberOfLocals(); ++i) {
+                getLocalPositions.local(i) = notSet;
+                setLocalPositions.local(i) = notSet;
+            }
+            
+            for (size_t i = 0; i < block->size(); ++i) {
+                NodeIndex nodeIndex = block->at(i);
+                Node& node = m_graph[nodeIndex];
+                ASSERT(nodesInThisBlock.get(nodeIndex));
+                VALIDATE((nodeIndex), node.op() != Phi);
+                for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
+                    Edge edge = m_graph.child(node, j);
+                    if (!edge)
+                        continue;
+                    VALIDATE((nodeIndex, edge), nodesInThisBlock.get(nodeIndex));
+                }
+                
+                if (!node.shouldGenerate())
+                    continue;
+                switch (node.op()) {
+                case GetLocal:
+                    if (node.variableAccessData()->isCaptured())
+                        break;
+                    VALIDATE((nodeIndex, blockIndex), getLocalPositions.operand(node.local()) == notSet);
+                    getLocalPositions.operand(node.local()) = i;
+                    break;
+                case SetLocal:
+                    if (node.variableAccessData()->isCaptured())
+                        break;
+                    // Only record the first SetLocal. There may be multiple SetLocals
+                    // because of flushing.
+                    if (setLocalPositions.operand(node.local()) != notSet)
+                        break;
+                    setLocalPositions.operand(node.local()) = i;
+                    break;
+                default:
+                    break;
+                }
+            }
+            
+            for (size_t i = 0; i < block->variablesAtHead.numberOfArguments(); ++i) {
+                checkOperand(
+                    blockIndex, getLocalPositions, setLocalPositions, argumentToOperand(i));
+            }
+            for (size_t i = 0; i < block->variablesAtHead.numberOfLocals(); ++i) {
+                checkOperand(
+                    blockIndex, getLocalPositions, setLocalPositions, i);
+            }
+        }
+    }
+    
+private:
+    Graph& m_graph;
+    GraphDumpMode m_graphDumpMode;
+    
+    void checkOperand(
+        BlockIndex blockIndex, Operands<size_t>& getLocalPositions,
+        Operands<size_t>& setLocalPositions, int operand)
+    {
+        if (getLocalPositions.operand(operand) == notSet)
+            return;
+        if (setLocalPositions.operand(operand) == notSet)
+            return;
+        
+        BasicBlock* block = m_graph.m_blocks[blockIndex].get();
+        
+        VALIDATE(
+            (block->at(getLocalPositions.operand(operand)),
+             block->at(setLocalPositions.operand(operand)),
+             blockIndex),
+            getLocalPositions.operand(operand) < setLocalPositions.operand(operand));
+    }
+    
+    void reportValidationContext(NodeIndex nodeIndex)
+    {
+        dataLog("@%u", nodeIndex);
+    }
+    
+    enum BlockTag { Block };
+    void reportValidationContext(BlockTag, BlockIndex blockIndex)
+    {
+        dataLog("Block #%u", blockIndex);
+    }
+    
+    void reportValidationContext(NodeIndex nodeIndex, Edge edge)
+    {
+        dataLog("@%u -> %s@%u", nodeIndex, useKindToString(edge.useKind()), edge.index());
+    }
+    
+    void reportValidationContext(
+        VirtualRegister local, BlockIndex sourceBlockIndex, BlockTag, BlockIndex destinationBlockIndex)
+    {
+        dataLog("r%d in Block #%u -> #%u", local, sourceBlockIndex, destinationBlockIndex);
+    }
+    
+    void reportValidationContext(
+        VirtualRegister local, BlockIndex sourceBlockIndex, NodeIndex prevNodeIndex)
+    {
+        dataLog("@%u for r%d in Block #%u", prevNodeIndex, local, sourceBlockIndex);
+    }
+    
+    void reportValidationContext(
+        NodeIndex nodeIndex, BlockIndex blockIndex)
+    {
+        dataLog("@%u in Block #%u", nodeIndex, blockIndex);
+    }
+    
+    void reportValidationContext(
+        NodeIndex nodeIndex, NodeIndex nodeIndex2, BlockIndex blockIndex)
+    {
+        dataLog("@%u and @%u in Block #%u", nodeIndex, nodeIndex2, blockIndex);
+    }
+    
+    void reportValidationContext(
+        NodeIndex nodeIndex, BlockIndex blockIndex, NodeIndex expectedNodeIndex, Edge incomingEdge)
+    {
+        dataLog("@%u in Block #%u, searching for @%u from @%u", nodeIndex, blockIndex, expectedNodeIndex, incomingEdge.index());
+    }
+    
+    void dumpData(unsigned value)
+    {
+        dataLog("%u", value);
+    }
+    
+    void dumpGraphIfAppropriate()
+    {
+        if (m_graphDumpMode == DontDumpGraph)
+            return;
+        dataLog("Graph at time of failure:\n");
+        m_graph.dump();
+    }
+};
+
+void validate(Graph& graph, GraphDumpMode graphDumpMode)
+{
+    Validate validationObject(graph, graphDumpMode);
+    validationObject.validate();
+}
+
+#endif // DFG_ENABLE(VALIDATION)
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+