1/*
2 * Copyright (C) 2013, 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#ifndef DFGAbstractInterpreter_h
27#define DFGAbstractInterpreter_h
28
29#if ENABLE(DFG_JIT)
30
31#include "DFGAbstractValue.h"
32#include "DFGBranchDirection.h"
33#include "DFGGraph.h"
34#include "DFGNode.h"
35
36namespace JSC { namespace DFG {
37
38template<typename AbstractStateType>
39class AbstractInterpreter {
40public:
41    AbstractInterpreter(Graph&, AbstractStateType&);
42    ~AbstractInterpreter();
43
44    AbstractValue& forNode(Node* node)
45    {
46        return m_state.forNode(node);
47    }
48
49    AbstractValue& forNode(Edge edge)
50    {
51        return forNode(edge.node());
52    }
53
54    Operands<AbstractValue>& variables()
55    {
56        return m_state.variables();
57    }
58
59    bool needsTypeCheck(Node* node, SpeculatedType typesPassedThrough)
60    {
61        return !forNode(node).isType(typesPassedThrough);
62    }
63
64    bool needsTypeCheck(Edge edge, SpeculatedType typesPassedThrough)
65    {
66        return needsTypeCheck(edge.node(), typesPassedThrough);
67    }
68
69    bool needsTypeCheck(Edge edge)
70    {
71        return needsTypeCheck(edge, typeFilterFor(edge.useKind()));
72    }
73
74    // Abstractly executes the given node. The new abstract state is stored into an
75    // abstract stack stored in *this. Loads of local variables (that span
76    // basic blocks) interrogate the basic block's notion of the state at the head.
77    // Stores to local variables are handled in endBasicBlock(). This returns true
78    // if execution should continue past this node. Notably, it will return true
79    // for block terminals, so long as those terminals are not Return or Unreachable.
80    //
81    // This is guaranteed to be equivalent to doing:
82    //
83    // if (state.startExecuting(index)) {
84    //     state.executeEdges(index);
85    //     result = state.executeEffects(index);
86    // } else
87    //     result = true;
88    bool execute(unsigned indexInBlock);
89    bool execute(Node*);
90
91    // Indicate the start of execution of the node. It resets any state in the node,
92    // that is progressively built up by executeEdges() and executeEffects(). In
93    // particular, this resets canExit(), so if you want to "know" between calls of
94    // startExecuting() and executeEdges()/Effects() whether the last run of the
95    // analysis concluded that the node can exit, you should probably set that
96    // information aside prior to calling startExecuting().
97    bool startExecuting(Node*);
98    bool startExecuting(unsigned indexInBlock);
99
100    // Abstractly execute the edges of the given node. This runs filterEdgeByUse()
101    // on all edges of the node. You can skip this step, if you have already used
102    // filterEdgeByUse() (or some equivalent) on each edge.
103    void executeEdges(Node*);
104    void executeEdges(unsigned indexInBlock);
105
106    ALWAYS_INLINE void filterEdgeByUse(Node* node, Edge& edge)
107    {
108        ASSERT(mayHaveTypeCheck(edge.useKind()) || !needsTypeCheck(edge));
109        filterByType(node, edge, typeFilterFor(edge.useKind()));
110    }
111
112    // Abstractly execute the effects of the given node. This changes the abstract
113    // state assuming that edges have already been filtered.
114    bool executeEffects(unsigned indexInBlock);
115    bool executeEffects(unsigned clobberLimit, Node*);
116
117    void dump(PrintStream& out);
118
119    template<typename T>
120    FiltrationResult filter(T node, const StructureSet& set)
121    {
122        return filter(forNode(node), set);
123    }
124
125    template<typename T>
126    FiltrationResult filterArrayModes(T node, ArrayModes arrayModes)
127    {
128        return filterArrayModes(forNode(node), arrayModes);
129    }
130
131    template<typename T>
132    FiltrationResult filter(T node, SpeculatedType type)
133    {
134        return filter(forNode(node), type);
135    }
136
137    template<typename T>
138    FiltrationResult filterByValue(T node, JSValue value)
139    {
140        return filterByValue(forNode(node), value);
141    }
142
143    FiltrationResult filter(AbstractValue&, const StructureSet&);
144    FiltrationResult filterArrayModes(AbstractValue&, ArrayModes);
145    FiltrationResult filter(AbstractValue&, SpeculatedType);
146    FiltrationResult filterByValue(AbstractValue&, JSValue);
147
148private:
149    void clobberWorld(const CodeOrigin&, unsigned indexInBlock);
150    void clobberCapturedVars(const CodeOrigin&);
151    void clobberStructures(unsigned indexInBlock);
152
153    enum BooleanResult {
154        UnknownBooleanResult,
155        DefinitelyFalse,
156        DefinitelyTrue
157    };
158    BooleanResult booleanResult(Node*, AbstractValue&);
159
160    void setBuiltInConstant(Node* node, JSValue value)
161    {
162        AbstractValue& abstractValue = forNode(node);
163        abstractValue.set(m_graph, value);
164        abstractValue.fixTypeForRepresentation(node);
165    }
166
167    void setConstant(Node* node, JSValue value)
168    {
169        setBuiltInConstant(node, value);
170        m_state.setFoundConstants(true);
171    }
172
173    ALWAYS_INLINE void filterByType(Node* node, Edge& edge, SpeculatedType type)
174    {
175        AbstractValue& value = forNode(edge);
176        if (!value.isType(type)) {
177            node->setCanExit(true);
178            edge.setProofStatus(NeedsCheck);
179        } else
180            edge.setProofStatus(IsProved);
181
182        filter(value, type);
183    }
184
185    void verifyEdge(Node*, Edge);
186    void verifyEdges(Node*);
187
188    CodeBlock* m_codeBlock;
189    Graph& m_graph;
190    AbstractStateType& m_state;
191};
192
193} } // namespace JSC::DFG
194
195#endif // ENABLE(DFG_JIT)
196
197#endif // DFGAbstractInterpreter_h
198
199