[apple/javascriptcore.git] / dfg / DFGValidate.cpp

/*
 * Copyright (C) 2012, 2013 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 "CodeBlockWithJITType.h"
#include <wtf/Assertions.h>
#include <wtf/BitVector.h>

namespace JSC { namespace DFG {

class Validate {
public:
    Validate(Graph& graph, GraphDumpMode graphDumpMode)
        : m_graph(graph)
        , m_graphDumpMode(graphDumpMode)
    {
    }
    
    #define VALIDATE(context, assertion) do { \
        if (!(assertion)) { \
            dataLogF("\n\n\nAt "); \
            reportValidationContext context; \
            dataLogF(": 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) { \
            dataLogF("\n\n\nAt "); \
            reportValidationContext context; \
            dataLogF(": validation (%s = ", #left); \
            dataLog(left); \
            dataLogF(") == (%s = ", #right); \
            dataLog(right); \
            dataLogF(") (%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 that all local variables at the head of the root block are dead.
        BasicBlock* root = m_graph.m_blocks[0].get();
        for (unsigned i = 0; i < root->variablesAtHead.numberOfLocals(); ++i)
            V_EQUAL((static_cast<VirtualRegister>(i), 0), static_cast<Node*>(0), root->variablesAtHead.local(i));
        
        // Validate ref counts and uses.
        HashMap<Node*, unsigned> myRefCounts;
        for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
            BasicBlock* block = m_graph.m_blocks[blockIndex].get();
            if (!block || !block->isReachable)
                continue;
            for (size_t i = 0; i < block->numNodes(); ++i)
                myRefCounts.add(block->node(i), 0);
        }
        HashSet<Node*> acceptableNodes;
        for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
            BasicBlock* block = m_graph.m_blocks[blockIndex].get();
            if (!block || !block->isReachable)
                continue;
            for (size_t i = 0; i < block->numNodes(); ++i) {
                Node* node = block->node(i);
                acceptableNodes.add(node);
                if (!node->shouldGenerate())
                    continue;
                for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
                    // Phi children in LoadStore form are invalid.
                    if (m_graph.m_form == LoadStore && block->isPhiIndex(i))
                        continue;
                    
                    Edge edge = m_graph.child(node, j);
                    if (!edge)
                        continue;
                    
                    myRefCounts.find(edge.node())->value++;
                    
                    // Unless I'm a Flush, Phantom, GetLocal, or Phi, my children should hasResult().
                    switch (node->op()) {
                    case Flush:
                    case GetLocal:
                        VALIDATE((node, edge), edge->hasVariableAccessData());
                        VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData());
                        break;
                    case PhantomLocal:
                        VALIDATE((node, edge), edge->hasVariableAccessData());
                        VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData());
                        VALIDATE((node, edge), edge->op() != SetLocal);
                        break;
                    case Phi:
                        VALIDATE((node, edge), edge->hasVariableAccessData());
                        if (m_graph.m_unificationState == LocallyUnified)
                            break;
                        VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData());
                        break;
                    case Phantom:
                        switch (m_graph.m_form) {
                        case LoadStore:
                            if (j) {
                                VALIDATE((node, edge), edge->hasResult());
                                break;
                            }
                            switch (edge->op()) {
                            case Phi:
                            case SetArgument:
                            case SetLocal:
                                break;
                            default:
                                VALIDATE((node, edge), edge->hasResult());
                                break;
                            }
                            break;
                        case ThreadedCPS:
                            VALIDATE((node, edge), edge->hasResult());
                            break;
                        }
                        break;
                    default:
                        VALIDATE((node, edge), edge->hasResult());
                        break;
                    }
                }
            }
        }
        for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
            BasicBlock* block = m_graph.m_blocks[blockIndex].get();
            if (!block || !block->isReachable)
                continue;
            
            HashSet<Node*> phisInThisBlock;
            HashSet<Node*> nodesInThisBlock;
            
            for (size_t i = 0; i < block->numNodes(); ++i) {
                Node* node = block->node(i);
                nodesInThisBlock.add(node);
                if (block->isPhiIndex(i))
                    phisInThisBlock.add(node);
                if (m_graph.m_refCountState == ExactRefCount)
                    V_EQUAL((node), myRefCounts.get(node), node->adjustedRefCount());
                else
                    V_EQUAL((node), node->refCount(), 1);
                for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
                    Edge edge = m_graph.child(node, j);
                    if (!edge)
                        continue;
                    VALIDATE((node, edge), acceptableNodes.contains(edge.node()));
                }
            }
            
            for (size_t i = 0; i < block->phis.size(); ++i) {
                Node* node = block->phis[i];
                ASSERT(phisInThisBlock.contains(node));
                VALIDATE((node), node->op() == Phi);
                VirtualRegister local = node->local();
                for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
                    // Phi children in LoadStore form are invalid.
                    if (m_graph.m_form == LoadStore && block->isPhiIndex(i))
                        continue;
                    
                    Edge edge = m_graph.child(node, j);
                    if (!edge)
                        continue;
                    
                    VALIDATE(
                        (node, edge),
                        edge->op() == SetLocal
                        || edge->op() == SetArgument
                        || edge->op() == Flush
                        || edge->op() == Phi
                        || edge->op() == ZombieHint
                        || edge->op() == MovHint
                        || edge->op() == MovHintAndCheck);
                    
                    if (phisInThisBlock.contains(edge.node()))
                        continue;
                    
                    if (nodesInThisBlock.contains(edge.node())) {
                        VALIDATE(
                            (node, edge),
                            edge->op() == SetLocal
                            || edge->op() == ZombieHint
                            || edge->op() == MovHint
                            || edge->op() == MovHintAndCheck
                            || edge->op() == SetArgument
                            || 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);
                        Node* prevNode = 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]), prevNode);
                        switch (prevNode->op()) {
                        case GetLocal:
                        case Flush:
                        case PhantomLocal:
                            prevNode = prevNode->child1().node();
                            break;
                        default:
                            break;
                        }
                        if (node->shouldGenerate()) {
                            VALIDATE((local, block->m_predecessors[k], prevNode),
                                     prevNode->shouldGenerate());
                        }
                        VALIDATE(
                            (local, block->m_predecessors[k], prevNode),
                            prevNode->op() == SetLocal
                            || prevNode->op() == MovHint
                            || prevNode->op() == MovHintAndCheck
                            || prevNode->op() == ZombieHint
                            || prevNode->op() == SetArgument
                            || prevNode->op() == Phi);
                        if (prevNode == edge.node()) {
                            found = true;
                            break;
                        }
                        // At this point it cannot refer into this block.
                        VALIDATE((local, block->m_predecessors[k], prevNode), !prevBlock->isInBlock(edge.node()));
                    }
                    
                    VALIDATE((node, 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) {
                VALIDATE((static_cast<VirtualRegister>(argumentToOperand(i)), blockIndex), !block->variablesAtHead.argument(i) || block->variablesAtHead.argument(i)->hasVariableAccessData());
                if (m_graph.m_form == ThreadedCPS)
                    VALIDATE((static_cast<VirtualRegister>(argumentToOperand(i)), blockIndex), !block->variablesAtTail.argument(i) || block->variablesAtTail.argument(i)->hasVariableAccessData());
                
                getLocalPositions.argument(i) = notSet;
                setLocalPositions.argument(i) = notSet;
            }
            for (size_t i = 0; i < block->variablesAtHead.numberOfLocals(); ++i) {
                VALIDATE((static_cast<VirtualRegister>(i), blockIndex), !block->variablesAtHead.local(i) || block->variablesAtHead.local(i)->hasVariableAccessData());
                if (m_graph.m_form == ThreadedCPS)
                    VALIDATE((static_cast<VirtualRegister>(i), blockIndex), !block->variablesAtTail.local(i) || block->variablesAtTail.local(i)->hasVariableAccessData());

                getLocalPositions.local(i) = notSet;
                setLocalPositions.local(i) = notSet;
            }
            
            for (size_t i = 0; i < block->size(); ++i) {
                Node* node = block->at(i);
                ASSERT(nodesInThisBlock.contains(node));
                VALIDATE((node), node->op() != Phi);
                for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
                    Edge edge = m_graph.child(node, j);
                    if (!edge)
                        continue;
                    VALIDATE((node, edge), nodesInThisBlock.contains(edge.node()));
                    switch (node->op()) {
                    case PhantomLocal:
                    case GetLocal:
                    case Flush:
                        break;
                    case Phantom:
                        if (m_graph.m_form == LoadStore && !j)
                            break;
                    default:
                        VALIDATE((node, edge), !phisInThisBlock.contains(edge.node()));
                        break;
                    }
                }
                
                if (!node->shouldGenerate())
                    continue;
                switch (node->op()) {
                case GetLocal:
                    if (node->variableAccessData()->isCaptured())
                        break;
                    // Ignore GetLocal's that we know to be dead, but that the graph
                    // doesn't yet know to be dead.
                    if (!myRefCounts.get(node))
                        break;
                    if (m_graph.m_form == ThreadedCPS)
                        VALIDATE((node, 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;
                }
            }
            
            if (m_graph.m_form == LoadStore)
                continue;
            
            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(Node* node)
    {
        dataLogF("@%u", node->index());
    }
    
    enum BlockTag { Block };
    void reportValidationContext(BlockTag, BlockIndex blockIndex)
    {
        dataLogF("Block #%u", blockIndex);
    }
    
    void reportValidationContext(Node* node, Edge edge)
    {
        dataLog(node, " -> ", edge);
    }
    
    void reportValidationContext(VirtualRegister local, BlockIndex blockIndex)
    {
        dataLogF("r%d in Block #%u", local, blockIndex);
    }
    
    void reportValidationContext(
        VirtualRegister local, BlockIndex sourceBlockIndex, BlockTag, BlockIndex destinationBlockIndex)
    {
        dataLogF("r%d in Block #%u -> #%u", local, sourceBlockIndex, destinationBlockIndex);
    }
    
    void reportValidationContext(
        VirtualRegister local, BlockIndex sourceBlockIndex, Node* prevNode)
    {
        dataLogF("@%u for r%d in Block #%u", prevNode->index(), local, sourceBlockIndex);
    }
    
    void reportValidationContext(
        Node* node, BlockIndex blockIndex)
    {
        dataLogF("@%u in Block #%u", node->index(), blockIndex);
    }
    
    void reportValidationContext(
        Node* node, Node* node2, BlockIndex blockIndex)
    {
        dataLogF("@%u and @%u in Block #%u", node->index(), node2->index(), blockIndex);
    }
    
    void reportValidationContext(
        Node* node, BlockIndex blockIndex, Node* expectedNode, Edge incomingEdge)
    {
        dataLog(node, " in Block #", blockIndex, ", searching for ", expectedNode, " from ", incomingEdge);
    }
    
    void dumpGraphIfAppropriate()
    {
        if (m_graphDumpMode == DontDumpGraph)
            return;
        dataLog("At time of failure:\n");
        m_graph.dump();
    }
};

void validate(Graph& graph, GraphDumpMode graphDumpMode)
{
    Validate validationObject(graph, graphDumpMode);
    validationObject.validate();
}

} } // namespace JSC::DFG

#endif // ENABLE(DFG_JIT)
Commit	Line	Data
93a37866 A	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.m_blocks[0].get();
80	for (unsigned i = 0; i < root->variablesAtHead.numberOfLocals(); ++i)
81	V_EQUAL((static_cast<VirtualRegister>(i), 0), static_cast<Node*>(0), root->variablesAtHead.local(i));
82
83	// Validate ref counts and uses.
84	HashMap<Node*, unsigned> myRefCounts;
85	for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
86	BasicBlock* block = m_graph.m_blocks[blockIndex].get();
87	if (!block \|\| !block->isReachable)
88	continue;
89	for (size_t i = 0; i < block->numNodes(); ++i)
90	myRefCounts.add(block->node(i), 0);
91	}
92	HashSet<Node*> acceptableNodes;
93	for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
94	BasicBlock* block = m_graph.m_blocks[blockIndex].get();
95	if (!block \|\| !block->isReachable)
96	continue;
97	for (size_t i = 0; i < block->numNodes(); ++i) {
98	Node* node = block->node(i);
99	acceptableNodes.add(node);
100	if (!node->shouldGenerate())
101	continue;
102	for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
103	// Phi children in LoadStore form are invalid.
104	if (m_graph.m_form == LoadStore && block->isPhiIndex(i))
105	continue;
106
107	Edge edge = m_graph.child(node, j);
108	if (!edge)
109	continue;
110
111	myRefCounts.find(edge.node())->value++;
112
113	// Unless I'm a Flush, Phantom, GetLocal, or Phi, my children should hasResult().
114	switch (node->op()) {
115	case Flush:
116	case GetLocal:
117	VALIDATE((node, edge), edge->hasVariableAccessData());
118	VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData());
119	break;
120	case PhantomLocal:
121	VALIDATE((node, edge), edge->hasVariableAccessData());
122	VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData());
123	VALIDATE((node, edge), edge->op() != SetLocal);
124	break;
125	case Phi:
126	VALIDATE((node, edge), edge->hasVariableAccessData());
127	if (m_graph.m_unificationState == LocallyUnified)
128	break;
129	VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData());
130	break;
131	case Phantom:
132	switch (m_graph.m_form) {
133	case LoadStore:
134	if (j) {
135	VALIDATE((node, edge), edge->hasResult());
136	break;
137	}
138	switch (edge->op()) {
139	case Phi:
140	case SetArgument:
141	case SetLocal:
142	break;
143	default:
144	VALIDATE((node, edge), edge->hasResult());
145	break;
146	}
147	break;
148	case ThreadedCPS:
149	VALIDATE((node, edge), edge->hasResult());
150	break;
151	}
152	break;
153	default:
154	VALIDATE((node, edge), edge->hasResult());
155	break;
156	}
157	}
158	}
159	}
160	for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
161	BasicBlock* block = m_graph.m_blocks[blockIndex].get();
162	if (!block \|\| !block->isReachable)
163	continue;
164
165	HashSet<Node*> phisInThisBlock;
166	HashSet<Node*> nodesInThisBlock;
167
168	for (size_t i = 0; i < block->numNodes(); ++i) {
169	Node* node = block->node(i);
170	nodesInThisBlock.add(node);
171	if (block->isPhiIndex(i))
172	phisInThisBlock.add(node);
173	if (m_graph.m_refCountState == ExactRefCount)
174	V_EQUAL((node), myRefCounts.get(node), node->adjustedRefCount());
175	else
176	V_EQUAL((node), node->refCount(), 1);
177	for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
178	Edge edge = m_graph.child(node, j);
179	if (!edge)
180	continue;
181	VALIDATE((node, edge), acceptableNodes.contains(edge.node()));
182	}
183	}
184
185	for (size_t i = 0; i < block->phis.size(); ++i) {
186	Node* node = block->phis[i];
187	ASSERT(phisInThisBlock.contains(node));
188	VALIDATE((node), node->op() == Phi);
189	VirtualRegister local = node->local();
190	for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
191	// Phi children in LoadStore form are invalid.
192	if (m_graph.m_form == LoadStore && block->isPhiIndex(i))
193	continue;
194
195	Edge edge = m_graph.child(node, j);
196	if (!edge)
197	continue;
198
199	VALIDATE(
200	(node, edge),
201	edge->op() == SetLocal
202	\|\| edge->op() == SetArgument
203	\|\| edge->op() == Flush
204	\|\| edge->op() == Phi
205	\|\| edge->op() == ZombieHint
206	\|\| edge->op() == MovHint
207	\|\| edge->op() == MovHintAndCheck);
208
209	if (phisInThisBlock.contains(edge.node()))
210	continue;
211
212	if (nodesInThisBlock.contains(edge.node())) {
213	VALIDATE(
214	(node, edge),
215	edge->op() == SetLocal
216	\|\| edge->op() == ZombieHint
217	\|\| edge->op() == MovHint
218	\|\| edge->op() == MovHintAndCheck
219	\|\| edge->op() == SetArgument
220	\|\| edge->op() == Flush);
221
222	continue;
223	}
224
225	// There must exist a predecessor block that has this node index in
226	// its tail variables.
227	bool found = false;
228	for (unsigned k = 0; k < block->m_predecessors.size(); ++k) {
229	BasicBlock* prevBlock = m_graph.m_blocks[block->m_predecessors[k]].get();
230	VALIDATE((Block, block->m_predecessors[k]), prevBlock);
231	VALIDATE((Block, block->m_predecessors[k]), prevBlock->isReachable);
232	Node* prevNode = prevBlock->variablesAtTail.operand(local);
233	// If we have a Phi that is not referring to this block then all predecessors
234	// must have that local available.
235	VALIDATE((local, blockIndex, Block, block->m_predecessors[k]), prevNode);
236	switch (prevNode->op()) {
237	case GetLocal:
238	case Flush:
239	case PhantomLocal:
240	prevNode = prevNode->child1().node();
241	break;
242	default:
243	break;
244	}
245	if (node->shouldGenerate()) {
246	VALIDATE((local, block->m_predecessors[k], prevNode),
247	prevNode->shouldGenerate());
248	}
249	VALIDATE(
250	(local, block->m_predecessors[k], prevNode),
251	prevNode->op() == SetLocal
252	\|\| prevNode->op() == MovHint
253	\|\| prevNode->op() == MovHintAndCheck
254	\|\| prevNode->op() == ZombieHint
255	\|\| prevNode->op() == SetArgument
256	\|\| prevNode->op() == Phi);
257	if (prevNode == edge.node()) {
258	found = true;
259	break;
260	}
261	// At this point it cannot refer into this block.
262	VALIDATE((local, block->m_predecessors[k], prevNode), !prevBlock->isInBlock(edge.node()));
263	}
264
265	VALIDATE((node, edge), found);
266	}
267	}
268
269	Operands<size_t> getLocalPositions(
270	block->variablesAtHead.numberOfArguments(),
271	block->variablesAtHead.numberOfLocals());
272	Operands<size_t> setLocalPositions(
273	block->variablesAtHead.numberOfArguments(),
274	block->variablesAtHead.numberOfLocals());
275
276	for (size_t i = 0; i < block->variablesAtHead.numberOfArguments(); ++i) {
277	VALIDATE((static_cast<VirtualRegister>(argumentToOperand(i)), blockIndex), !block->variablesAtHead.argument(i) \|\| block->variablesAtHead.argument(i)->hasVariableAccessData());
278	if (m_graph.m_form == ThreadedCPS)
279	VALIDATE((static_cast<VirtualRegister>(argumentToOperand(i)), blockIndex), !block->variablesAtTail.argument(i) \|\| block->variablesAtTail.argument(i)->hasVariableAccessData());
280
281	getLocalPositions.argument(i) = notSet;
282	setLocalPositions.argument(i) = notSet;
283	}
284	for (size_t i = 0; i < block->variablesAtHead.numberOfLocals(); ++i) {
285	VALIDATE((static_cast<VirtualRegister>(i), blockIndex), !block->variablesAtHead.local(i) \|\| block->variablesAtHead.local(i)->hasVariableAccessData());
286	if (m_graph.m_form == ThreadedCPS)
287	VALIDATE((static_cast<VirtualRegister>(i), blockIndex), !block->variablesAtTail.local(i) \|\| block->variablesAtTail.local(i)->hasVariableAccessData());
288
289	getLocalPositions.local(i) = notSet;
290	setLocalPositions.local(i) = notSet;
291	}
292
293	for (size_t i = 0; i < block->size(); ++i) {
294	Node* node = block->at(i);
295	ASSERT(nodesInThisBlock.contains(node));
296	VALIDATE((node), node->op() != Phi);
297	for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
298	Edge edge = m_graph.child(node, j);
299	if (!edge)
300	continue;
301	VALIDATE((node, edge), nodesInThisBlock.contains(edge.node()));
302	switch (node->op()) {
303	case PhantomLocal:
304	case GetLocal:
305	case Flush:
306	break;
307	case Phantom:
308	if (m_graph.m_form == LoadStore && !j)
309	break;
310	default:
311	VALIDATE((node, edge), !phisInThisBlock.contains(edge.node()));
312	break;
313	}
314	}
315
316	if (!node->shouldGenerate())
317	continue;
318	switch (node->op()) {
319	case GetLocal:
320	if (node->variableAccessData()->isCaptured())
321	break;
322	// Ignore GetLocal's that we know to be dead, but that the graph
323	// doesn't yet know to be dead.
324	if (!myRefCounts.get(node))
325	break;
326	if (m_graph.m_form == ThreadedCPS)
327	VALIDATE((node, blockIndex), getLocalPositions.operand(node->local()) == notSet);
328	getLocalPositions.operand(node->local()) = i;
329	break;
330	case SetLocal:
331	if (node->variableAccessData()->isCaptured())
332	break;
333	// Only record the first SetLocal. There may be multiple SetLocals
334	// because of flushing.
335	if (setLocalPositions.operand(node->local()) != notSet)
336	break;
337	setLocalPositions.operand(node->local()) = i;
338	break;
339	default:
340	break;
341	}
342	}
343
344	if (m_graph.m_form == LoadStore)
345	continue;
346
347	for (size_t i = 0; i < block->variablesAtHead.numberOfArguments(); ++i) {
348	checkOperand(
349	blockIndex, getLocalPositions, setLocalPositions, argumentToOperand(i));
350	}
351	for (size_t i = 0; i < block->variablesAtHead.numberOfLocals(); ++i) {
352	checkOperand(
353	blockIndex, getLocalPositions, setLocalPositions, i);
354	}
355	}
356	}
357
358	private:
359	Graph& m_graph;
360	GraphDumpMode m_graphDumpMode;
361
362	void checkOperand(
363	BlockIndex blockIndex, Operands<size_t>& getLocalPositions,
364	Operands<size_t>& setLocalPositions, int operand)
365	{
366	if (getLocalPositions.operand(operand) == notSet)
367	return;
368	if (setLocalPositions.operand(operand) == notSet)
369	return;
370
371	BasicBlock* block = m_graph.m_blocks[blockIndex].get();
372
373	VALIDATE(
374	(block->at(getLocalPositions.operand(operand)),
375	block->at(setLocalPositions.operand(operand)),
376	blockIndex),
377	getLocalPositions.operand(operand) < setLocalPositions.operand(operand));
378	}
379
380	void reportValidationContext(Node* node)
381	{
382	dataLogF("@%u", node->index());
383	}
384
385	enum BlockTag { Block };
386	void reportValidationContext(BlockTag, BlockIndex blockIndex)
387	{
388	dataLogF("Block #%u", blockIndex);
389	}
390
391	void reportValidationContext(Node* node, Edge edge)
392	{
393	dataLog(node, " -> ", edge);
394	}
395
396	void reportValidationContext(VirtualRegister local, BlockIndex blockIndex)
397	{
398	dataLogF("r%d in Block #%u", local, blockIndex);
399	}
400
401	void reportValidationContext(
402	VirtualRegister local, BlockIndex sourceBlockIndex, BlockTag, BlockIndex destinationBlockIndex)
403	{
404	dataLogF("r%d in Block #%u -> #%u", local, sourceBlockIndex, destinationBlockIndex);
405	}
406
407	void reportValidationContext(
408	VirtualRegister local, BlockIndex sourceBlockIndex, Node* prevNode)
409	{
410	dataLogF("@%u for r%d in Block #%u", prevNode->index(), local, sourceBlockIndex);
411	}
412
413	void reportValidationContext(
414	Node* node, BlockIndex blockIndex)
415	{
416	dataLogF("@%u in Block #%u", node->index(), blockIndex);
417	}
418
419	void reportValidationContext(
420	Node* node, Node* node2, BlockIndex blockIndex)
421	{
422	dataLogF("@%u and @%u in Block #%u", node->index(), node2->index(), blockIndex);
423	}
424
425	void reportValidationContext(
426	Node* node, BlockIndex blockIndex, Node* expectedNode, Edge incomingEdge)
427	{
428	dataLog(node, " in Block #", blockIndex, ", searching for ", expectedNode, " from ", incomingEdge);
429	}
430
431	void dumpGraphIfAppropriate()
432	{
433	if (m_graphDumpMode == DontDumpGraph)
434	return;
435	dataLog("At time of failure:\n");
436	m_graph.dump();
437	}
438	};
439
440	void validate(Graph& graph, GraphDumpMode graphDumpMode)
441	{
442	Validate validationObject(graph, graphDumpMode);
443	validationObject.validate();
444	}
445
446	} } // namespace JSC::DFG
447
448	#endif // ENABLE(DFG_JIT)
449