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