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