90d575b418509e39dbe8177552efde647e239a02
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGBackwardsPropagationPhase.cpp
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
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         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
67 private:
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
483 bool performBackwardsPropagation(Graph& graph)
484 {
485     return runPhase<BackwardsPropagationPhase>(graph);
486 }
487
488 } } // namespace JSC::DFG
489
490 #endif // ENABLE(DFG_JIT)
491