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