68f16a1ceadc8eeb5a88b7f7b18b6e2cbbc6cd06
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGAbstractState.h
1 /*
2  * Copyright (C) 2011 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 "DFGGraph.h"
35 #include "DFGNode.h"
36 #include <wtf/Vector.h>
37
38 namespace JSC {
39
40 class CodeBlock;
41
42 namespace DFG {
43
44 struct BasicBlock;
45
46 // This implements the notion of an abstract state for flow-sensitive intraprocedural
47 // control flow analysis (CFA), with a focus on the elimination of redundant type checks.
48 // It also implements most of the mechanisms of abstract interpretation that such an
49 // analysis would use. This class should be used in two idioms:
50 //
51 // 1) Performing the CFA. In this case, AbstractState should be run over all basic
52 //    blocks repeatedly until convergence is reached. Convergence is defined by
53 //    endBasicBlock(AbstractState::MergeToSuccessors) returning false for all blocks.
54 //
55 // 2) Rematerializing the results of a previously executed CFA. In this case,
56 //    AbstractState should be run over whatever basic block you're interested in up
57 //    to the point of the node at which you'd like to interrogate the known type
58 //    of all other nodes. At this point it's safe to discard the AbstractState entirely,
59 //    call reset(), or to run it to the end of the basic block and call
60 //    endBasicBlock(AbstractState::DontMerge). The latter option is safest because
61 //    it performs some useful integrity checks.
62 //
63 // After the CFA is run, the inter-block state is saved at the heads and tails of all
64 // basic blocks. This allows the intra-block state to be rematerialized by just
65 // executing the CFA for that block. If you need to know inter-block state only, then
66 // you only need to examine the BasicBlock::m_valuesAtHead or m_valuesAtTail fields.
67 //
68 // Running this analysis involves the following, modulo the inter-block state
69 // merging and convergence fixpoint:
70 //
71 // AbstractState state(codeBlock, graph);
72 // state.beginBasicBlock(basicBlock);
73 // bool endReached = true;
74 // for (NodeIndex idx = basicBlock.begin; idx < basicBlock.end; ++idx) {
75 //     if (!state.execute(idx))
76 //         break;
77 // }
78 // bool result = state.endBasicBlock(<either Merge or DontMerge>);
79
80 class AbstractState {
81 public:
82     enum MergeMode {
83         // Don't merge the state in AbstractState with basic blocks.
84         DontMerge,
85         
86         // Merge the state in AbstractState with the tail of the basic
87         // block being analyzed.
88         MergeToTail,
89         
90         // Merge the state in AbstractState with the tail of the basic
91         // block, and with the heads of successor blocks.
92         MergeToSuccessors
93     };
94     
95     enum BranchDirection {
96         // This is not a branch and so there is no branch direction, or
97         // the branch direction has yet to be set.
98         InvalidBranchDirection,
99         
100         // The branch takes the true case.
101         TakeTrue,
102         
103         // The branch takes the false case.
104         TakeFalse,
105         
106         // For all we know, the branch could go either direction, so we
107         // have to assume the worst.
108         TakeBoth
109     };
110     
111     static const char* branchDirectionToString(BranchDirection branchDirection)
112     {
113         switch (branchDirection) {
114         case InvalidBranchDirection:
115             return "Invalid";
116         case TakeTrue:
117             return "TakeTrue";
118         case TakeFalse:
119             return "TakeFalse";
120         case TakeBoth:
121             return "TakeBoth";
122         }
123     }
124
125     AbstractState(Graph&);
126     
127     ~AbstractState();
128     
129     AbstractValue& forNode(NodeIndex nodeIndex)
130     {
131         return m_nodes[nodeIndex];
132     }
133     
134     AbstractValue& forNode(Edge nodeUse)
135     {
136         return forNode(nodeUse.index());
137     }
138     
139     Operands<AbstractValue>& variables()
140     {
141         return m_variables;
142     }
143     
144     // Call this before beginning CFA to initialize the abstract values of
145     // arguments, and to indicate which blocks should be listed for CFA
146     // execution.
147     static void initialize(Graph&);
148
149     // Start abstractly executing the given basic block. Initializes the
150     // notion of abstract state to what we believe it to be at the head
151     // of the basic block, according to the basic block's data structures.
152     // This method also sets cfaShouldRevisit to false.
153     void beginBasicBlock(BasicBlock*);
154     
155     // Finish abstractly executing a basic block. If MergeToTail or
156     // MergeToSuccessors is passed, then this merges everything we have
157     // learned about how the state changes during this block's execution into
158     // the block's data structures. There are three return modes, depending
159     // on the value of mergeMode:
160     //
161     // DontMerge:
162     //    Always returns false.
163     //
164     // MergeToTail:
165     //    Returns true if the state of the block at the tail was changed.
166     //    This means that you must call mergeToSuccessors(), and if that
167     //    returns true, then you must revisit (at least) the successor
168     //    blocks. False will always be returned if the block is terminal
169     //    (i.e. ends in Throw or Return, or has a ForceOSRExit inside it).
170     //
171     // MergeToSuccessors:
172     //    Returns true if the state of the block at the tail was changed,
173     //    and, if the state at the heads of successors was changed.
174     //    A true return means that you must revisit (at least) the successor
175     //    blocks. This also sets cfaShouldRevisit to true for basic blocks
176     //    that must be visited next.
177     //
178     // If you'd like to know what direction the branch at the end of the
179     // basic block is thought to have taken, you can pass a non-0 pointer
180     // for BranchDirection.
181     bool endBasicBlock(MergeMode, BranchDirection* = 0);
182     
183     // Reset the AbstractState. This throws away any results, and at this point
184     // you can safely call beginBasicBlock() on any basic block.
185     void reset();
186     
187     // Abstractly executes the given node. The new abstract state is stored into an
188     // abstract register file stored in *this. Loads of local variables (that span
189     // basic blocks) interrogate the basic block's notion of the state at the head.
190     // Stores to local variables are handled in endBasicBlock(). This returns true
191     // if execution should continue past this node. Notably, it will return true
192     // for block terminals, so long as those terminals are not Return or variants
193     // of Throw.
194     bool execute(unsigned);
195     
196     // Is the execution state still valid? This will be false if execute() has
197     // returned false previously.
198     bool isValid() const { return m_isValid; }
199     
200     // Merge the abstract state stored at the first block's tail into the second
201     // block's head. Returns true if the second block's state changed. If so,
202     // that block must be abstractly interpreted again. This also sets
203     // to->cfaShouldRevisit to true, if it returns true, or if to has not been
204     // visited yet.
205     bool merge(BasicBlock* from, BasicBlock* to);
206     
207     // Merge the abstract state stored at the block's tail into all of its
208     // successors. Returns true if any of the successors' states changed. Note
209     // that this is automatically called in endBasicBlock() if MergeMode is
210     // MergeToSuccessors.
211     bool mergeToSuccessors(Graph&, BasicBlock*, BranchDirection);
212
213     void dump(FILE* out);
214     
215 private:
216     void clobberWorld(const CodeOrigin&, unsigned indexInBlock);
217     void clobberStructures(unsigned indexInBlock);
218     
219     bool mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, NodeIndex);
220     
221     static bool mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, NodeIndex destinationNodeIndex, NodeIndex sourceNodeIndex);
222     
223     void speculateInt32Unary(Node& node, bool forceCanExit = false)
224     {
225         AbstractValue& childValue = forNode(node.child1());
226         node.setCanExit(forceCanExit || !isInt32Speculation(childValue.m_type));
227         childValue.filter(SpecInt32);
228     }
229     
230     void speculateNumberUnary(Node& node)
231     {
232         AbstractValue& childValue = forNode(node.child1());
233         node.setCanExit(!isNumberSpeculation(childValue.m_type));
234         childValue.filter(SpecNumber);
235     }
236     
237     void speculateBooleanUnary(Node& node)
238     {
239         AbstractValue& childValue = forNode(node.child1());
240         node.setCanExit(!isBooleanSpeculation(childValue.m_type));
241         childValue.filter(SpecBoolean);
242     }
243     
244     void speculateInt32Binary(Node& node, bool forceCanExit = false)
245     {
246         AbstractValue& childValue1 = forNode(node.child1());
247         AbstractValue& childValue2 = forNode(node.child2());
248         node.setCanExit(
249             forceCanExit
250             || !isInt32Speculation(childValue1.m_type)
251             || !isInt32Speculation(childValue2.m_type));
252         childValue1.filter(SpecInt32);
253         childValue2.filter(SpecInt32);
254     }
255     
256     void speculateNumberBinary(Node& node)
257     {
258         AbstractValue& childValue1 = forNode(node.child1());
259         AbstractValue& childValue2 = forNode(node.child2());
260         node.setCanExit(
261             !isNumberSpeculation(childValue1.m_type)
262             || !isNumberSpeculation(childValue2.m_type));
263         childValue1.filter(SpecNumber);
264         childValue2.filter(SpecNumber);
265     }
266     
267     CodeBlock* m_codeBlock;
268     Graph& m_graph;
269     
270     Vector<AbstractValue, 64> m_nodes;
271     Operands<AbstractValue> m_variables;
272     BasicBlock* m_block;
273     bool m_haveStructures;
274     bool m_foundConstants;
275     
276     bool m_isValid;
277     
278     BranchDirection m_branchDirection; // This is only set for blocks that end in Branch and that execute to completion (i.e. m_isValid == true).
279 };
280
281 } } // namespace JSC::DFG
282
283 #endif // ENABLE(DFG_JIT)
284
285 #endif // DFGAbstractState_h
286