1/*
2 * Copyright (C) 2013-2018 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#pragma once
27
28#if ENABLE(DFG_JIT)
29
30#include "DFGAbstractInterpreterClobberState.h"
31#include "DFGAbstractValue.h"
32#include "DFGBranchDirection.h"
33#include "DFGFlowMap.h"
34#include "DFGGraph.h"
35#include "DFGNode.h"
36
37namespace JSC { namespace DFG {
38
39class InPlaceAbstractState {
40 WTF_MAKE_FAST_ALLOCATED;
41public:
42 InPlaceAbstractState(Graph&);
43
44 ~InPlaceAbstractState();
45
46 explicit operator bool() const { return true; }
47
48 void createValueForNode(NodeFlowProjection) { }
49
50 ALWAYS_INLINE AbstractValue& fastForward(AbstractValue& value)
51 {
52 value.fastForwardTo(m_effectEpoch);
53 return value;
54 }
55
56 ALWAYS_INLINE void fastForwardAndFilterUnproven(AbstractValue& value, SpeculatedType type)
57 {
58 value.fastForwardToAndFilterUnproven(m_effectEpoch, type);
59 }
60
61 ALWAYS_INLINE AbstractValue& forNodeWithoutFastForward(NodeFlowProjection node)
62 {
63 return m_abstractValues.at(node);
64 }
65
66 ALWAYS_INLINE AbstractValue& forNodeWithoutFastForward(Edge edge)
67 {
68 return forNodeWithoutFastForward(edge.node());
69 }
70
71 ALWAYS_INLINE AbstractValue& forNode(NodeFlowProjection node)
72 {
73 return fastForward(m_abstractValues.at(node));
74 }
75
76 ALWAYS_INLINE AbstractValue& forNode(Edge edge)
77 {
78 return forNode(edge.node());
79 }
80
81 ALWAYS_INLINE void clearForNode(NodeFlowProjection node)
82 {
83 AbstractValue& value = m_abstractValues.at(node);
84 value.clear();
85 value.m_effectEpoch = m_effectEpoch;
86 }
87
88 ALWAYS_INLINE void clearForNode(Edge edge)
89 {
90 clearForNode(edge.node());
91 }
92
93 template<typename... Arguments>
94 ALWAYS_INLINE void setForNode(NodeFlowProjection node, Arguments&&... arguments)
95 {
96 AbstractValue& value = m_abstractValues.at(node);
97 value.set(m_graph, std::forward<Arguments>(arguments)...);
98 value.m_effectEpoch = m_effectEpoch;
99 }
100
101 template<typename... Arguments>
102 ALWAYS_INLINE void setForNode(Edge edge, Arguments&&... arguments)
103 {
104 setForNode(edge.node(), std::forward<Arguments>(arguments)...);
105 }
106
107 template<typename... Arguments>
108 ALWAYS_INLINE void setTypeForNode(NodeFlowProjection node, Arguments&&... arguments)
109 {
110 AbstractValue& value = m_abstractValues.at(node);
111 value.setType(m_graph, std::forward<Arguments>(arguments)...);
112 value.m_effectEpoch = m_effectEpoch;
113 }
114
115 template<typename... Arguments>
116 ALWAYS_INLINE void setTypeForNode(Edge edge, Arguments&&... arguments)
117 {
118 setTypeForNode(edge.node(), std::forward<Arguments>(arguments)...);
119 }
120
121 template<typename... Arguments>
122 ALWAYS_INLINE void setNonCellTypeForNode(NodeFlowProjection node, Arguments&&... arguments)
123 {
124 AbstractValue& value = m_abstractValues.at(node);
125 value.setNonCellType(std::forward<Arguments>(arguments)...);
126 value.m_effectEpoch = m_effectEpoch;
127 }
128
129 template<typename... Arguments>
130 ALWAYS_INLINE void setNonCellTypeForNode(Edge edge, Arguments&&... arguments)
131 {
132 setNonCellTypeForNode(edge.node(), std::forward<Arguments>(arguments)...);
133 }
134
135 ALWAYS_INLINE void makeBytecodeTopForNode(NodeFlowProjection node)
136 {
137 AbstractValue& value = m_abstractValues.at(node);
138 value.makeBytecodeTop();
139 value.m_effectEpoch = m_effectEpoch;
140 }
141
142 ALWAYS_INLINE void makeBytecodeTopForNode(Edge edge)
143 {
144 makeBytecodeTopForNode(edge.node());
145 }
146
147 ALWAYS_INLINE void makeHeapTopForNode(NodeFlowProjection node)
148 {
149 AbstractValue& value = m_abstractValues.at(node);
150 value.makeHeapTop();
151 value.m_effectEpoch = m_effectEpoch;
152 }
153
154 ALWAYS_INLINE void makeHeapTopForNode(Edge edge)
155 {
156 makeHeapTopForNode(edge.node());
157 }
158
159 Operands<AbstractValue>& variablesForDebugging();
160
161 unsigned numberOfArguments() const { return m_variables.numberOfArguments(); }
162 unsigned numberOfLocals() const { return m_variables.numberOfLocals(); }
163
164 AbstractValue& variableAt(size_t index)
165 {
166 activateVariableIfNecessary(index);
167 return fastForward(m_variables[index]);
168 }
169
170 AbstractValue& operand(int operand)
171 {
172 return variableAt(m_variables.operandIndex(operand));
173 }
174
175 AbstractValue& operand(VirtualRegister operand) { return this->operand(operand.offset()); }
176
177 AbstractValue& local(size_t index)
178 {
179 return variableAt(m_variables.localIndex(index));
180 }
181
182 AbstractValue& argument(size_t index)
183 {
184 return variableAt(m_variables.argumentIndex(index));
185 }
186
187 // Call this before beginning CFA to initialize the abstract values of
188 // arguments, and to indicate which blocks should be listed for CFA
189 // execution.
190 void initialize();
191
192 // Start abstractly executing the given basic block. Initializes the
193 // notion of abstract state to what we believe it to be at the head
194 // of the basic block, according to the basic block's data structures.
195 // This method also sets cfaShouldRevisit to false.
196 void beginBasicBlock(BasicBlock*);
197
198 BasicBlock* block() const { return m_block; }
199
200 // Finish abstractly executing a basic block. If MergeToTail or
201 // MergeToSuccessors is passed, then this merges everything we have
202 // learned about how the state changes during this block's execution into
203 // the block's data structures.
204 //
205 // Returns true if the state of the block at the tail was changed,
206 // and, if the state at the heads of successors was changed.
207 // A true return means that you must revisit (at least) the successor
208 // blocks. This also sets cfaShouldRevisit to true for basic blocks
209 // that must be visited next.
210 bool endBasicBlock();
211
212 // Reset the AbstractState. This throws away any results, and at this point
213 // you can safely call beginBasicBlock() on any basic block.
214 void reset();
215
216 AbstractInterpreterClobberState clobberState() const { return m_clobberState; }
217
218 // Would have the last executed node clobbered things had we not found a way to fold it?
219 bool didClobberOrFolded() const { return clobberState() != AbstractInterpreterClobberState::NotClobbered; }
220
221 // Did the last executed node clobber the world?
222 bool didClobber() const { return clobberState() == AbstractInterpreterClobberState::ClobberedStructures; }
223
224 // Are structures currently clobbered?
225 StructureClobberState structureClobberState() const { return m_structureClobberState; }
226
227 // Is the execution state still valid? This will be false if execute() has
228 // returned false previously.
229 bool isValid() const { return m_isValid; }
230
231 // Merge the abstract state stored at the first block's tail into the second
232 // block's head. Returns true if the second block's state changed. If so,
233 // that block must be abstractly interpreted again. This also sets
234 // to->cfaShouldRevisit to true, if it returns true, or if to has not been
235 // visited yet.
236 bool merge(BasicBlock* from, BasicBlock* to);
237
238 // Merge the abstract state stored at the block's tail into all of its
239 // successors. Returns true if any of the successors' states changed. Note
240 // that this is automatically called in endBasicBlock() if MergeMode is
241 // MergeToSuccessors.
242 bool mergeToSuccessors(BasicBlock*);
243
244 void clobberStructures() { m_effectEpoch.clobber(); }
245
246 void observeInvalidationPoint() { m_effectEpoch.observeInvalidationPoint(); }
247
248 // Methods intended to be called from AbstractInterpreter.
249 void setClobberState(AbstractInterpreterClobberState state) { m_clobberState = state; }
250 void mergeClobberState(AbstractInterpreterClobberState state) { m_clobberState = mergeClobberStates(m_clobberState, state); }
251 void setStructureClobberState(StructureClobberState value) { m_structureClobberState = value; }
252 void setIsValid(bool isValid) { m_isValid = isValid; }
253 void setBranchDirection(BranchDirection branchDirection) { m_branchDirection = branchDirection; }
254
255 // This method is evil - it causes a huge maintenance headache and there is a gross amount of
256 // code devoted to it. It would be much nicer to just always run the constant folder on each
257 // block. But, the last time we did it, it was a 1% SunSpider regression:
258 // https://bugs.webkit.org/show_bug.cgi?id=133947
259 // So, we should probably keep this method.
260 void setFoundConstants(bool foundConstants) { m_foundConstants = foundConstants; }
261
262 void setProofStatus(Edge& edge, ProofStatus status)
263 {
264 edge.setProofStatus(status);
265 }
266
267private:
268 ALWAYS_INLINE void activateVariableIfNecessary(size_t variableIndex)
269 {
270 if (!m_activeVariables[variableIndex])
271 activateVariable(variableIndex);
272 }
273
274 void activateVariable(size_t variableIndex);
275 void activateAllVariables();
276
277 static bool mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, Node* destinationNode, Node* sourceNode);
278
279 Graph& m_graph;
280
281 FlowMap<AbstractValue>& m_abstractValues;
282 Operands<AbstractValue> m_variables;
283 FastBitVector m_activeVariables;
284 BasicBlock* m_block;
285
286 bool m_foundConstants;
287
288 bool m_isValid;
289 AbstractInterpreterClobberState m_clobberState;
290 StructureClobberState m_structureClobberState;
291 AbstractValueClobberEpoch m_epochAtHead;
292 AbstractValueClobberEpoch m_effectEpoch;
293
294 BranchDirection m_branchDirection; // This is only set for blocks that end in Branch and that execute to completion (i.e. m_isValid == true).
295};
296
297} } // namespace JSC::DFG
298
299#endif // ENABLE(DFG_JIT)
300