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