fourthTier: Landing the initial FTL logic in a single commit to avoid spurious
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGAbstractState.h
1 /*
2  * Copyright (C) 2011, 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 #ifndef DFGAbstractState_h
27 #define DFGAbstractState_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 #include <wtf/Vector.h>
38
39 namespace JSC {
40
41 class CodeBlock;
42
43 namespace DFG {
44
45 struct BasicBlock;
46
47 // This implements the notion of an abstract state for flow-sensitive intraprocedural
48 // control flow analysis (CFA), with a focus on the elimination of redundant type checks.
49 // It also implements most of the mechanisms of abstract interpretation that such an
50 // analysis would use. This class should be used in two idioms:
51 //
52 // 1) Performing the CFA. In this case, AbstractState should be run over all basic
53 //    blocks repeatedly until convergence is reached. Convergence is defined by
54 //    endBasicBlock(AbstractState::MergeToSuccessors) returning false for all blocks.
55 //
56 // 2) Rematerializing the results of a previously executed CFA. In this case,
57 //    AbstractState should be run over whatever basic block you're interested in up
58 //    to the point of the node at which you'd like to interrogate the known type
59 //    of all other nodes. At this point it's safe to discard the AbstractState entirely,
60 //    call reset(), or to run it to the end of the basic block and call
61 //    endBasicBlock(AbstractState::DontMerge). The latter option is safest because
62 //    it performs some useful integrity checks.
63 //
64 // After the CFA is run, the inter-block state is saved at the heads and tails of all
65 // basic blocks. This allows the intra-block state to be rematerialized by just
66 // executing the CFA for that block. If you need to know inter-block state only, then
67 // you only need to examine the BasicBlock::m_valuesAtHead or m_valuesAtTail fields.
68 //
69 // Running this analysis involves the following, modulo the inter-block state
70 // merging and convergence fixpoint:
71 //
72 // AbstractState state(codeBlock, graph);
73 // state.beginBasicBlock(basicBlock);
74 // bool endReached = true;
75 // for (unsigned i = 0; i < basicBlock->size(); ++i) {
76 //     if (!state.execute(i))
77 //         break;
78 // }
79 // bool result = state.endBasicBlock(<either Merge or DontMerge>);
80
81 class AbstractState {
82 public:
83     enum MergeMode {
84         // Don't merge the state in AbstractState with basic blocks.
85         DontMerge,
86         
87         // Merge the state in AbstractState with the tail of the basic
88         // block being analyzed.
89         MergeToTail,
90         
91         // Merge the state in AbstractState with the tail of the basic
92         // block, and with the heads of successor blocks.
93         MergeToSuccessors
94     };
95     
96     AbstractState(Graph&);
97     
98     ~AbstractState();
99     
100     AbstractValue& forNode(Node* node)
101     {
102         return node->value;
103     }
104     
105     AbstractValue& forNode(Edge edge)
106     {
107         return forNode(edge.node());
108     }
109     
110     Operands<AbstractValue>& variables()
111     {
112         return m_variables;
113     }
114     
115     bool needsTypeCheck(Node* node, SpeculatedType typesPassedThrough)
116     {
117         return forNode(node).m_type & ~typesPassedThrough;
118     }
119     
120     bool needsTypeCheck(Edge edge, SpeculatedType typesPassedThrough)
121     {
122         return needsTypeCheck(edge.node(), typesPassedThrough);
123     }
124     
125     bool needsTypeCheck(Edge edge)
126     {
127         return needsTypeCheck(edge, typeFilterFor(edge.useKind()));
128     }
129     
130     // Call this before beginning CFA to initialize the abstract values of
131     // arguments, and to indicate which blocks should be listed for CFA
132     // execution.
133     static void initialize(Graph&);
134
135     // Start abstractly executing the given basic block. Initializes the
136     // notion of abstract state to what we believe it to be at the head
137     // of the basic block, according to the basic block's data structures.
138     // This method also sets cfaShouldRevisit to false.
139     void beginBasicBlock(BasicBlock*);
140     
141     // Finish abstractly executing a basic block. If MergeToTail or
142     // MergeToSuccessors is passed, then this merges everything we have
143     // learned about how the state changes during this block's execution into
144     // the block's data structures. There are three return modes, depending
145     // on the value of mergeMode:
146     //
147     // DontMerge:
148     //    Always returns false.
149     //
150     // MergeToTail:
151     //    Returns true if the state of the block at the tail was changed.
152     //    This means that you must call mergeToSuccessors(), and if that
153     //    returns true, then you must revisit (at least) the successor
154     //    blocks. False will always be returned if the block is terminal
155     //    (i.e. ends in Throw or Return, or has a ForceOSRExit inside it).
156     //
157     // MergeToSuccessors:
158     //    Returns true if the state of the block at the tail was changed,
159     //    and, if the state at the heads of successors was changed.
160     //    A true return means that you must revisit (at least) the successor
161     //    blocks. This also sets cfaShouldRevisit to true for basic blocks
162     //    that must be visited next.
163     bool endBasicBlock(MergeMode);
164     
165     // Reset the AbstractState. This throws away any results, and at this point
166     // you can safely call beginBasicBlock() on any basic block.
167     void reset();
168     
169     // Abstractly executes the given node. The new abstract state is stored into an
170     // abstract stack stored in *this. Loads of local variables (that span
171     // basic blocks) interrogate the basic block's notion of the state at the head.
172     // Stores to local variables are handled in endBasicBlock(). This returns true
173     // if execution should continue past this node. Notably, it will return true
174     // for block terminals, so long as those terminals are not Return or variants
175     // of Throw.
176     //
177     // This is guaranteed to be equivalent to doing:
178     //
179     // if (state.startExecuting(index)) {
180     //     state.executeEdges(index);
181     //     result = state.executeEffects(index);
182     // } else
183     //     result = true;
184     bool execute(unsigned indexInBlock);
185     
186     // Indicate the start of execution of the node. It resets any state in the node,
187     // that is progressively built up by executeEdges() and executeEffects(). In
188     // particular, this resets canExit(), so if you want to "know" between calls of
189     // startExecuting() and executeEdges()/Effects() whether the last run of the
190     // analysis concluded that the node can exit, you should probably set that
191     // information aside prior to calling startExecuting().
192     bool startExecuting(Node*);
193     bool startExecuting(unsigned indexInBlock);
194     
195     // Abstractly execute the edges of the given node. This runs filterEdgeByUse()
196     // on all edges of the node. You can skip this step, if you have already used
197     // filterEdgeByUse() (or some equivalent) on each edge.
198     void executeEdges(Node*);
199     void executeEdges(unsigned indexInBlock);
200     
201     ALWAYS_INLINE void filterEdgeByUse(Node* node, Edge& edge)
202     {
203         ASSERT(mayHaveTypeCheck(edge.useKind()) || !needsTypeCheck(edge));
204         filterByType(node, edge, typeFilterFor(edge.useKind()));
205     }
206     
207     // Abstractly execute the effects of the given node. This changes the abstract
208     // state assuming that edges have already been filtered.
209     bool executeEffects(unsigned indexInBlock);
210     bool executeEffects(unsigned indexInBlock, Node*);
211     
212     // Did the last executed node clobber the world?
213     bool didClobber() const { return m_didClobber; }
214     
215     // Is the execution state still valid? This will be false if execute() has
216     // returned false previously.
217     bool isValid() const { return m_isValid; }
218     
219     // Merge the abstract state stored at the first block's tail into the second
220     // block's head. Returns true if the second block's state changed. If so,
221     // that block must be abstractly interpreted again. This also sets
222     // to->cfaShouldRevisit to true, if it returns true, or if to has not been
223     // visited yet.
224     bool merge(BasicBlock* from, BasicBlock* to);
225     
226     // Merge the abstract state stored at the block's tail into all of its
227     // successors. Returns true if any of the successors' states changed. Note
228     // that this is automatically called in endBasicBlock() if MergeMode is
229     // MergeToSuccessors.
230     bool mergeToSuccessors(Graph&, BasicBlock*);
231     
232     void dump(PrintStream& out);
233     
234 private:
235     void clobberWorld(const CodeOrigin&, unsigned indexInBlock);
236     void clobberCapturedVars(const CodeOrigin&);
237     void clobberStructures(unsigned indexInBlock);
238     
239     bool mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node*);
240     
241     static bool mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, Node* destinationNode, Node* sourceNode);
242     
243     enum BooleanResult {
244         UnknownBooleanResult,
245         DefinitelyFalse,
246         DefinitelyTrue
247     };
248     BooleanResult booleanResult(Node*, AbstractValue&);
249     
250     bool trySetConstant(Node* node, JSValue value)
251     {
252         // Make sure we don't constant fold something that will produce values that contravene
253         // predictions. If that happens then we know that the code will OSR exit, forcing
254         // recompilation. But if we tried to constant fold then we'll have a very degenerate
255         // IR: namely we'll have a JSConstant that contravenes its own prediction. There's a
256         // lot of subtle code that assumes that
257         // speculationFromValue(jsConstant) == jsConstant.prediction(). "Hardening" that code
258         // is probably less sane than just pulling back on constant folding.
259         SpeculatedType oldType = node->prediction();
260         if (mergeSpeculations(speculationFromValue(value), oldType) != oldType)
261             return false;
262         
263         forNode(node).set(value);
264         return true;
265     }
266     
267     ALWAYS_INLINE void filterByType(Node* node, Edge& edge, SpeculatedType type)
268     {
269         AbstractValue& value = forNode(edge);
270         if (value.m_type & ~type) {
271             node->setCanExit(true);
272             edge.setProofStatus(NeedsCheck);
273         } else
274             edge.setProofStatus(IsProved);
275         
276         value.filter(type);
277     }
278     
279     void verifyEdge(Node*, Edge);
280     void verifyEdges(Node*);
281     
282     CodeBlock* m_codeBlock;
283     Graph& m_graph;
284     
285     Operands<AbstractValue> m_variables;
286     BasicBlock* m_block;
287     bool m_haveStructures;
288     bool m_foundConstants;
289     
290     bool m_isValid;
291     bool m_didClobber;
292     
293     BranchDirection m_branchDirection; // This is only set for blocks that end in Branch and that execute to completion (i.e. m_isValid == true).
294 };
295
296 } } // namespace JSC::DFG
297
298 #endif // ENABLE(DFG_JIT)
299
300 #endif // DFGAbstractState_h
301