1/*
2 * Copyright (C) 2013-2015 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 "JSCInlines.h"
35
36namespace JSC { namespace DFG {
37
38class BackwardsPropagationPhase : public Phase {
39public:
40 BackwardsPropagationPhase(Graph& graph)
41 : Phase(graph, "backwards propagation")
42 {
43 }
44
45 bool run()
46 {
47 m_changed = true;
48 while (m_changed) {
49 m_changed = false;
50 for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
51 BasicBlock* block = m_graph.block(blockIndex);
52 if (!block)
53 continue;
54
55 // Prevent a tower of overflowing additions from creating a value that is out of the
56 // safe 2^48 range.
57 m_allowNestedOverflowingAdditions = block->size() < (1 << 16);
58
59 for (unsigned indexInBlock = block->size(); indexInBlock--;)
60 propagate(block->at(indexInBlock));
61 }
62 }
63
64 return true;
65 }
66
67private:
68 bool isNotNegZero(Node* node)
69 {
70 if (!node->isNumberConstant())
71 return false;
72 double value = node->asNumber();
73 return (value || 1.0 / value > 0.0);
74 }
75
76 bool isNotPosZero(Node* node)
77 {
78 if (!node->isNumberConstant())
79 return false;
80 double value = node->asNumber();
81 return (value || 1.0 / value < 0.0);
82 }
83
84 // Tests if the absolute value is strictly less than the power of two.
85 template<int power>
86 bool isWithinPowerOfTwoForConstant(Node* node)
87 {
88 JSValue immediateValue = node->asJSValue();
89 if (!immediateValue.isNumber())
90 return false;
91 double immediate = immediateValue.asNumber();
92 return immediate > -(static_cast<int64_t>(1) << power) && immediate < (static_cast<int64_t>(1) << power);
93 }
94
95 template<int power>
96 bool isWithinPowerOfTwoNonRecursive(Node* node)
97 {
98 if (!node->isNumberConstant())
99 return false;
100 return isWithinPowerOfTwoForConstant<power>(node);
101 }
102
103 template<int power>
104 bool isWithinPowerOfTwo(Node* node)
105 {
106 switch (node->op()) {
107 case DoubleConstant:
108 case JSConstant:
109 case Int52Constant: {
110 return isWithinPowerOfTwoForConstant<power>(node);
111 }
112
113 case ValueBitAnd:
114 case ArithBitAnd: {
115 if (power > 31)
116 return true;
117
118 return isWithinPowerOfTwoNonRecursive<power>(node->child1().node())
119 || isWithinPowerOfTwoNonRecursive<power>(node->child2().node());
120 }
121
122 case ArithBitOr:
123 case ArithBitXor:
124 case ValueBitOr:
125 case ValueBitXor:
126 case ValueBitLShift:
127 case ArithBitLShift: {
128 return power > 31;
129 }
130
131 case ArithBitRShift:
132 case ValueBitRShift:
133 case BitURShift: {
134 if (power > 31)
135 return true;
136
137 Node* shiftAmount = node->child2().node();
138 if (!node->isNumberConstant())
139 return false;
140 JSValue immediateValue = shiftAmount->asJSValue();
141 if (!immediateValue.isInt32())
142 return false;
143 return immediateValue.asInt32() > 32 - power;
144 }
145
146 default:
147 return false;
148 }
149 }
150
151 template<int power>
152 bool isWithinPowerOfTwo(Edge edge)
153 {
154 return isWithinPowerOfTwo<power>(edge.node());
155 }
156
157 bool mergeDefaultFlags(Node* node)
158 {
159 bool changed = false;
160 if (node->flags() & NodeHasVarArgs) {
161 for (unsigned childIdx = node->firstChild();
162 childIdx < node->firstChild() + node->numChildren();
163 childIdx++) {
164 if (!!m_graph.m_varArgChildren[childIdx])
165 changed |= m_graph.m_varArgChildren[childIdx]->mergeFlags(NodeBytecodeUsesAsValue);
166 }
167 } else {
168 if (!node->child1())
169 return changed;
170 changed |= node->child1()->mergeFlags(NodeBytecodeUsesAsValue);
171 if (!node->child2())
172 return changed;
173 changed |= node->child2()->mergeFlags(NodeBytecodeUsesAsValue);
174 if (!node->child3())
175 return changed;
176 changed |= node->child3()->mergeFlags(NodeBytecodeUsesAsValue);
177 }
178 return changed;
179 }
180
181 void propagate(Node* node)
182 {
183 NodeFlags flags = node->flags() & NodeBytecodeBackPropMask;
184
185 switch (node->op()) {
186 case GetLocal: {
187 VariableAccessData* variableAccessData = node->variableAccessData();
188 flags &= ~NodeBytecodeUsesAsInt; // We don't care about cross-block uses-as-int.
189 m_changed |= variableAccessData->mergeFlags(flags);
190 break;
191 }
192
193 case SetLocal: {
194 VariableAccessData* variableAccessData = node->variableAccessData();
195 if (!variableAccessData->isLoadedFrom())
196 break;
197 flags = variableAccessData->flags();
198 RELEASE_ASSERT(!(flags & ~NodeBytecodeBackPropMask));
199 flags |= NodeBytecodeUsesAsNumber; // Account for the fact that control flow may cause overflows that our modeling can't handle.
200 node->child1()->mergeFlags(flags);
201 break;
202 }
203
204 case Flush: {
205 VariableAccessData* variableAccessData = node->variableAccessData();
206 m_changed |= variableAccessData->mergeFlags(NodeBytecodeUsesAsValue);
207 break;
208 }
209
210 case MovHint:
211 case Check:
212 case CheckVarargs:
213 break;
214
215 case ValueBitNot:
216 case ArithBitNot: {
217 flags |= NodeBytecodeUsesAsInt;
218 flags &= ~(NodeBytecodeUsesAsNumber | NodeBytecodeNeedsNegZero | NodeBytecodeUsesAsOther);
219 flags &= ~NodeBytecodeUsesAsArrayIndex;
220 node->child1()->mergeFlags(flags);
221 break;
222 }
223
224 case ArithBitAnd:
225 case ArithBitOr:
226 case ArithBitXor:
227 case ValueBitAnd:
228 case ValueBitOr:
229 case ValueBitXor:
230 case ValueBitLShift:
231 case ArithBitLShift:
232 case ArithBitRShift:
233 case ValueBitRShift:
234 case BitURShift:
235 case ArithIMul: {
236 flags |= NodeBytecodeUsesAsInt;
237 flags &= ~(NodeBytecodeUsesAsNumber | NodeBytecodeNeedsNegZero | NodeBytecodeUsesAsOther);
238 flags &= ~NodeBytecodeUsesAsArrayIndex;
239 node->child1()->mergeFlags(flags);
240 node->child2()->mergeFlags(flags);
241 break;
242 }
243
244 case StringCharAt:
245 case StringCharCodeAt:
246 case StringCodePointAt: {
247 node->child1()->mergeFlags(NodeBytecodeUsesAsValue);
248 node->child2()->mergeFlags(NodeBytecodeUsesAsValue | NodeBytecodeUsesAsInt | NodeBytecodeUsesAsArrayIndex);
249 break;
250 }
251
252 case StringSlice: {
253 node->child1()->mergeFlags(NodeBytecodeUsesAsValue);
254 node->child2()->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsOther | NodeBytecodeUsesAsInt | NodeBytecodeUsesAsArrayIndex);
255 if (node->child3())
256 node->child3()->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsOther | NodeBytecodeUsesAsInt | NodeBytecodeUsesAsArrayIndex);
257 break;
258 }
259
260 case ArraySlice: {
261 m_graph.varArgChild(node, 0)->mergeFlags(NodeBytecodeUsesAsValue);
262
263 if (node->numChildren() == 2)
264 m_graph.varArgChild(node, 1)->mergeFlags(NodeBytecodeUsesAsValue);
265 else if (node->numChildren() == 3) {
266 m_graph.varArgChild(node, 1)->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsOther | NodeBytecodeUsesAsInt | NodeBytecodeUsesAsArrayIndex);
267 m_graph.varArgChild(node, 2)->mergeFlags(NodeBytecodeUsesAsValue);
268 } else if (node->numChildren() == 4) {
269 m_graph.varArgChild(node, 1)->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsOther | NodeBytecodeUsesAsInt | NodeBytecodeUsesAsArrayIndex);
270 m_graph.varArgChild(node, 2)->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsOther | NodeBytecodeUsesAsInt | NodeBytecodeUsesAsArrayIndex);
271 m_graph.varArgChild(node, 3)->mergeFlags(NodeBytecodeUsesAsValue);
272 }
273 break;
274 }
275
276
277 case UInt32ToNumber: {
278 node->child1()->mergeFlags(flags);
279 break;
280 }
281
282 case ValueAdd: {
283 if (isNotNegZero(node->child1().node()) || isNotNegZero(node->child2().node()))
284 flags &= ~NodeBytecodeNeedsNegZero;
285 if (node->child1()->hasNumericResult() || node->child2()->hasNumericResult() || node->child1()->hasNumberResult() || node->child2()->hasNumberResult())
286 flags &= ~NodeBytecodeUsesAsOther;
287 if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2()))
288 flags |= NodeBytecodeUsesAsNumber;
289 if (!m_allowNestedOverflowingAdditions)
290 flags |= NodeBytecodeUsesAsNumber;
291
292 node->child1()->mergeFlags(flags);
293 node->child2()->mergeFlags(flags);
294 break;
295 }
296
297 case ArithAdd: {
298 flags &= ~NodeBytecodeUsesAsOther;
299 if (isNotNegZero(node->child1().node()) || isNotNegZero(node->child2().node()))
300 flags &= ~NodeBytecodeNeedsNegZero;
301 if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2()))
302 flags |= NodeBytecodeUsesAsNumber;
303 if (!m_allowNestedOverflowingAdditions)
304 flags |= NodeBytecodeUsesAsNumber;
305
306 node->child1()->mergeFlags(flags);
307 node->child2()->mergeFlags(flags);
308 break;
309 }
310
311 case ArithClz32: {
312 flags &= ~(NodeBytecodeUsesAsNumber | NodeBytecodeNeedsNegZero | NodeBytecodeUsesAsOther | ~NodeBytecodeUsesAsArrayIndex);
313 flags |= NodeBytecodeUsesAsInt;
314 node->child1()->mergeFlags(flags);
315 break;
316 }
317
318 case ArithSub: {
319 flags &= ~NodeBytecodeUsesAsOther;
320 if (isNotNegZero(node->child1().node()) || isNotPosZero(node->child2().node()))
321 flags &= ~NodeBytecodeNeedsNegZero;
322 if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2()))
323 flags |= NodeBytecodeUsesAsNumber;
324 if (!m_allowNestedOverflowingAdditions)
325 flags |= NodeBytecodeUsesAsNumber;
326
327 node->child1()->mergeFlags(flags);
328 node->child2()->mergeFlags(flags);
329 break;
330 }
331
332 case ArithNegate: {
333 flags &= ~NodeBytecodeUsesAsOther;
334
335 node->child1()->mergeFlags(flags);
336 break;
337 }
338
339 case Inc:
340 case Dec: {
341 flags &= ~NodeBytecodeNeedsNegZero;
342 flags &= ~NodeBytecodeUsesAsOther;
343 if (!isWithinPowerOfTwo<32>(node->child1()))
344 flags |= NodeBytecodeUsesAsNumber;
345 if (!m_allowNestedOverflowingAdditions)
346 flags |= NodeBytecodeUsesAsNumber;
347
348 node->child1()->mergeFlags(flags);
349 break;
350 }
351
352 case ValueMul:
353 case ArithMul: {
354 // As soon as a multiply happens, we can easily end up in the part
355 // of the double domain where the point at which you do truncation
356 // can change the outcome. So, ArithMul always forces its inputs to
357 // check for overflow. Additionally, it will have to check for overflow
358 // itself unless we can prove that there is no way for the values
359 // produced to cause double rounding.
360
361 if (!isWithinPowerOfTwo<22>(node->child1().node())
362 && !isWithinPowerOfTwo<22>(node->child2().node()))
363 flags |= NodeBytecodeUsesAsNumber;
364
365 node->mergeFlags(flags);
366
367 flags |= NodeBytecodeUsesAsNumber | NodeBytecodeNeedsNegZero;
368 flags &= ~NodeBytecodeUsesAsOther;
369
370 node->child1()->mergeFlags(flags);
371 node->child2()->mergeFlags(flags);
372 break;
373 }
374
375 case ValueDiv:
376 case ArithDiv: {
377 flags |= NodeBytecodeUsesAsNumber | NodeBytecodeNeedsNegZero;
378 flags &= ~NodeBytecodeUsesAsOther;
379
380 node->child1()->mergeFlags(flags);
381 node->child2()->mergeFlags(flags);
382 break;
383 }
384
385 case ValueMod:
386 case ArithMod: {
387 flags |= NodeBytecodeUsesAsNumber;
388 flags &= ~NodeBytecodeUsesAsOther;
389
390 node->child1()->mergeFlags(flags);
391 node->child2()->mergeFlags(flags & ~NodeBytecodeNeedsNegZero);
392 break;
393 }
394
395 case GetByVal: {
396 m_graph.varArgChild(node, 0)->mergeFlags(NodeBytecodeUsesAsValue);
397 m_graph.varArgChild(node, 1)->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsOther | NodeBytecodeUsesAsInt | NodeBytecodeUsesAsArrayIndex);
398 break;
399 }
400
401 case NewTypedArray:
402 case NewArrayWithSize: {
403 // Negative zero is not observable. NaN versus undefined are only observable
404 // in that you would get a different exception message. So, like, whatever: we
405 // claim here that NaN v. undefined is observable.
406 node->child1()->mergeFlags(NodeBytecodeUsesAsInt | NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsOther | NodeBytecodeUsesAsArrayIndex);
407 break;
408 }
409
410 case ToString:
411 case CallStringConstructor: {
412 node->child1()->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsOther);
413 break;
414 }
415
416 case ToPrimitive:
417 case ToNumber:
418 case ToNumeric: {
419 node->child1()->mergeFlags(flags);
420 break;
421 }
422
423 case CompareLess:
424 case CompareLessEq:
425 case CompareGreater:
426 case CompareGreaterEq:
427 case CompareBelow:
428 case CompareBelowEq:
429 case CompareEq:
430 case CompareStrictEq: {
431 node->child1()->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsOther);
432 node->child2()->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsOther);
433 break;
434 }
435
436 case PutByValDirect:
437 case PutByVal: {
438 m_graph.varArgChild(node, 0)->mergeFlags(NodeBytecodeUsesAsValue);
439 m_graph.varArgChild(node, 1)->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsOther | NodeBytecodeUsesAsInt | NodeBytecodeUsesAsArrayIndex);
440 m_graph.varArgChild(node, 2)->mergeFlags(NodeBytecodeUsesAsValue);
441 break;
442 }
443
444 case Switch: {
445 SwitchData* data = node->switchData();
446 switch (data->kind) {
447 case SwitchImm:
448 // We don't need NodeBytecodeNeedsNegZero because if the cases are all integers
449 // then -0 and 0 are treated the same. We don't need NodeBytecodeUsesAsOther
450 // because if all of the cases are integers then NaN and undefined are
451 // treated the same (i.e. they will take default).
452 node->child1()->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsInt);
453 break;
454 case SwitchChar: {
455 // We don't need NodeBytecodeNeedsNegZero because if the cases are all strings
456 // then -0 and 0 are treated the same. We don't need NodeBytecodeUsesAsOther
457 // because if all of the cases are single-character strings then NaN
458 // and undefined are treated the same (i.e. they will take default).
459 node->child1()->mergeFlags(NodeBytecodeUsesAsNumber);
460 break;
461 }
462 case SwitchString:
463 // We don't need NodeBytecodeNeedsNegZero because if the cases are all strings
464 // then -0 and 0 are treated the same.
465 node->child1()->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsOther);
466 break;
467 case SwitchCell:
468 // There is currently no point to being clever here since this is used for switching
469 // on objects.
470 mergeDefaultFlags(node);
471 break;
472 }
473 break;
474 }
475
476 case Identity:
477 // This would be trivial to handle but we just assert that we cannot see these yet.
478 RELEASE_ASSERT_NOT_REACHED();
479 break;
480
481 // Note: ArithSqrt, ArithUnary and other math intrinsics don't have special
482 // rules in here because they are always followed by Phantoms to signify that if the
483 // method call speculation fails, the bytecode may use the arguments in arbitrary ways.
484 // This corresponds to that possibility of someone doing something like:
485 // Math.sin = function(x) { doArbitraryThingsTo(x); }
486
487 default:
488 mergeDefaultFlags(node);
489 break;
490 }
491 }
492
493 bool m_allowNestedOverflowingAdditions;
494 bool m_changed;
495};
496
497bool performBackwardsPropagation(Graph& graph)
498{
499 return runPhase<BackwardsPropagationPhase>(graph);
500}
501
502} } // namespace JSC::DFG
503
504#endif // ENABLE(DFG_JIT)
505
506