]> git.saurik.com Git - apple/javascriptcore.git/blob - dfg/DFGBackwardsPropagationPhase.cpp
JavaScriptCore-1218.33.tar.gz
[apple/javascriptcore.git] / dfg / DFGBackwardsPropagationPhase.cpp
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 #include "config.h"
27 #include "DFGBackwardsPropagationPhase.h"
28
29 #if ENABLE(DFG_JIT)
30
31 #include "DFGBasicBlockInlines.h"
32 #include "DFGGraph.h"
33 #include "DFGPhase.h"
34 #include "Operations.h"
35
36 namespace JSC { namespace DFG {
37
38 class BackwardsPropagationPhase : public Phase {
39 public:
40 BackwardsPropagationPhase(Graph& graph)
41 : Phase(graph, "backwards propagation")
42 {
43 }
44
45 bool run()
46 {
47 for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
48 BasicBlock* block = m_graph.m_blocks[blockIndex].get();
49 if (!block)
50 continue;
51
52 // Prevent a tower of overflowing additions from creating a value that is out of the
53 // safe 2^48 range.
54 m_allowNestedOverflowingAdditions = block->size() < (1 << 16);
55
56 for (unsigned indexInBlock = block->size(); indexInBlock--;)
57 propagate(block->at(indexInBlock));
58 }
59
60 return true;
61 }
62
63 private:
64 bool isNotNegZero(Node* node)
65 {
66 if (!m_graph.isNumberConstant(node))
67 return false;
68 double value = m_graph.valueOfNumberConstant(node);
69 return (value || 1.0 / value > 0.0);
70 }
71
72 bool isNotPosZero(Node* node)
73 {
74 if (!m_graph.isNumberConstant(node))
75 return false;
76 double value = m_graph.valueOfNumberConstant(node);
77 return (value || 1.0 / value < 0.0);
78 }
79
80 // Tests if the absolute value is strictly less than the power of two.
81 template<int power>
82 bool isWithinPowerOfTwoForConstant(Node* node)
83 {
84 JSValue immediateValue = node->valueOfJSConstant(codeBlock());
85 if (!immediateValue.isNumber())
86 return false;
87 double immediate = immediateValue.asNumber();
88 return immediate > -(static_cast<int64_t>(1) << power) && immediate < (static_cast<int64_t>(1) << power);
89 }
90
91 template<int power>
92 bool isWithinPowerOfTwoNonRecursive(Node* node)
93 {
94 if (node->op() != JSConstant)
95 return false;
96 return isWithinPowerOfTwoForConstant<power>(node);
97 }
98
99 template<int power>
100 bool isWithinPowerOfTwo(Node* node)
101 {
102 switch (node->op()) {
103 case JSConstant: {
104 return isWithinPowerOfTwoForConstant<power>(node);
105 }
106
107 case BitAnd: {
108 if (power > 31)
109 return true;
110
111 return isWithinPowerOfTwoNonRecursive<power>(node->child1().node())
112 || isWithinPowerOfTwoNonRecursive<power>(node->child2().node());
113 }
114
115 case BitOr:
116 case BitXor:
117 case BitLShift:
118 case ValueToInt32: {
119 return power > 31;
120 }
121
122 case BitRShift:
123 case BitURShift: {
124 if (power > 31)
125 return true;
126
127 Node* shiftAmount = node->child2().node();
128 if (shiftAmount->op() != JSConstant)
129 return false;
130 JSValue immediateValue = shiftAmount->valueOfJSConstant(codeBlock());
131 if (!immediateValue.isInt32())
132 return false;
133 return immediateValue.asInt32() > 32 - power;
134 }
135
136 default:
137 return false;
138 }
139 }
140
141 template<int power>
142 bool isWithinPowerOfTwo(Edge edge)
143 {
144 return isWithinPowerOfTwo<power>(edge.node());
145 }
146
147 bool mergeDefaultFlags(Node* node)
148 {
149 bool changed = false;
150 if (node->flags() & NodeHasVarArgs) {
151 for (unsigned childIdx = node->firstChild();
152 childIdx < node->firstChild() + node->numChildren();
153 childIdx++) {
154 if (!!m_graph.m_varArgChildren[childIdx])
155 changed |= m_graph.m_varArgChildren[childIdx]->mergeFlags(NodeUsedAsValue);
156 }
157 } else {
158 if (!node->child1())
159 return changed;
160 changed |= node->child1()->mergeFlags(NodeUsedAsValue);
161 if (!node->child2())
162 return changed;
163 changed |= node->child2()->mergeFlags(NodeUsedAsValue);
164 if (!node->child3())
165 return changed;
166 changed |= node->child3()->mergeFlags(NodeUsedAsValue);
167 }
168 return changed;
169 }
170
171 void propagate(Node* node)
172 {
173 NodeFlags flags = node->flags() & NodeBackPropMask;
174
175 switch (node->op()) {
176 case GetLocal: {
177 VariableAccessData* variableAccessData = node->variableAccessData();
178 variableAccessData->mergeFlags(flags);
179 break;
180 }
181
182 case SetLocal: {
183 VariableAccessData* variableAccessData = node->variableAccessData();
184 if (!variableAccessData->isLoadedFrom())
185 break;
186 node->child1()->mergeFlags(NodeUsedAsValue);
187 break;
188 }
189
190 case BitAnd:
191 case BitOr:
192 case BitXor:
193 case BitRShift:
194 case BitLShift:
195 case BitURShift:
196 case ArithIMul: {
197 flags |= NodeUsedAsInt;
198 flags &= ~(NodeUsedAsNumber | NodeNeedsNegZero | NodeUsedAsOther);
199 node->child1()->mergeFlags(flags);
200 node->child2()->mergeFlags(flags);
201 break;
202 }
203
204 case ValueToInt32: {
205 flags |= NodeUsedAsInt;
206 flags &= ~(NodeUsedAsNumber | NodeNeedsNegZero | NodeUsedAsOther);
207 node->child1()->mergeFlags(flags);
208 break;
209 }
210
211 case StringCharCodeAt: {
212 node->child1()->mergeFlags(NodeUsedAsValue);
213 node->child2()->mergeFlags(NodeUsedAsValue | NodeUsedAsInt);
214 break;
215 }
216
217 case Identity:
218 case UInt32ToNumber: {
219 node->child1()->mergeFlags(flags);
220 break;
221 }
222
223 case ValueAdd: {
224 if (isNotNegZero(node->child1().node()) || isNotNegZero(node->child2().node()))
225 flags &= ~NodeNeedsNegZero;
226 if (node->child1()->hasNumberResult() || node->child2()->hasNumberResult())
227 flags &= ~NodeUsedAsOther;
228 if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2()))
229 flags |= NodeUsedAsNumber;
230 if (!m_allowNestedOverflowingAdditions)
231 flags |= NodeUsedAsNumber;
232
233 node->child1()->mergeFlags(flags);
234 node->child2()->mergeFlags(flags);
235 break;
236 }
237
238 case ArithAdd: {
239 if (isNotNegZero(node->child1().node()) || isNotNegZero(node->child2().node()))
240 flags &= ~NodeNeedsNegZero;
241 if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2()))
242 flags |= NodeUsedAsNumber;
243 if (!m_allowNestedOverflowingAdditions)
244 flags |= NodeUsedAsNumber;
245
246 node->child1()->mergeFlags(flags);
247 node->child2()->mergeFlags(flags);
248 break;
249 }
250
251 case ArithSub: {
252 if (isNotNegZero(node->child1().node()) || isNotPosZero(node->child2().node()))
253 flags &= ~NodeNeedsNegZero;
254 if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2()))
255 flags |= NodeUsedAsNumber;
256 if (!m_allowNestedOverflowingAdditions)
257 flags |= NodeUsedAsNumber;
258
259 node->child1()->mergeFlags(flags);
260 node->child2()->mergeFlags(flags);
261 break;
262 }
263
264 case ArithNegate: {
265 flags &= ~NodeUsedAsOther;
266
267 node->child1()->mergeFlags(flags);
268 break;
269 }
270
271 case ArithMul: {
272 // As soon as a multiply happens, we can easily end up in the part
273 // of the double domain where the point at which you do truncation
274 // can change the outcome. So, ArithMul always forces its inputs to
275 // check for overflow. Additionally, it will have to check for overflow
276 // itself unless we can prove that there is no way for the values
277 // produced to cause double rounding.
278
279 if (!isWithinPowerOfTwo<22>(node->child1().node())
280 && !isWithinPowerOfTwo<22>(node->child2().node()))
281 flags |= NodeUsedAsNumber;
282
283 node->mergeFlags(flags);
284
285 flags |= NodeUsedAsNumber | NodeNeedsNegZero;
286 flags &= ~NodeUsedAsOther;
287
288 node->child1()->mergeFlags(flags);
289 node->child2()->mergeFlags(flags);
290 break;
291 }
292
293 case ArithDiv: {
294 flags |= NodeUsedAsNumber | NodeNeedsNegZero;
295 flags &= ~NodeUsedAsOther;
296
297 node->child1()->mergeFlags(flags);
298 node->child2()->mergeFlags(flags);
299 break;
300 }
301
302 case ArithMod: {
303 flags |= NodeUsedAsNumber | NodeNeedsNegZero;
304 flags &= ~NodeUsedAsOther;
305
306 node->child1()->mergeFlags(flags);
307 node->child2()->mergeFlags(flags);
308 break;
309 }
310
311 case GetByVal: {
312 node->child1()->mergeFlags(NodeUsedAsValue);
313 node->child2()->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther | NodeUsedAsInt);
314 break;
315 }
316
317 case GetMyArgumentByValSafe: {
318 node->child1()->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther | NodeUsedAsInt);
319 break;
320 }
321
322 case NewArrayWithSize: {
323 node->child1()->mergeFlags(NodeUsedAsValue | NodeUsedAsInt);
324 break;
325 }
326
327 case StringCharAt: {
328 node->child1()->mergeFlags(NodeUsedAsValue);
329 node->child2()->mergeFlags(NodeUsedAsValue | NodeUsedAsInt);
330 break;
331 }
332
333 case ToString: {
334 node->child1()->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther);
335 break;
336 }
337
338 case ToPrimitive: {
339 node->child1()->mergeFlags(flags);
340 break;
341 }
342
343 case PutByVal: {
344 m_graph.varArgChild(node, 0)->mergeFlags(NodeUsedAsValue);
345 m_graph.varArgChild(node, 1)->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther | NodeUsedAsInt);
346 m_graph.varArgChild(node, 2)->mergeFlags(NodeUsedAsValue);
347 break;
348 }
349
350 default:
351 mergeDefaultFlags(node);
352 break;
353 }
354 }
355
356 bool m_allowNestedOverflowingAdditions;
357 };
358
359 bool performBackwardsPropagation(Graph& graph)
360 {
361 SamplingRegion samplingRegion("DFG Backwards Propagation Phase");
362 return runPhase<BackwardsPropagationPhase>(graph);
363 }
364
365 } } // namespace JSC::DFG
366
367 #endif // ENABLE(DFG_JIT)
368