DFG implementation of op_strcat should inline rope allocations
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGBackwardsPropagationPhase.cpp
1 /*
2  * Copyright (C) 2013 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 "Operations.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         for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) {
48             BasicBlock* block = m_graph.m_blocks[blockIndex].get();
49             if (!block)
50                 continue;
51             
52             // Prevent a tower of overflowing additions from creating a value that is out of the
53             // safe 2^48 range.
54             m_allowNestedOverflowingAdditions = block->size() < (1 << 16);
55             
56             for (unsigned indexInBlock = block->size(); indexInBlock--;)
57                 propagate(block->at(indexInBlock));
58         }
59         
60         return true;
61     }
62
63 private:
64     bool isNotNegZero(Node* node)
65     {
66         if (!m_graph.isNumberConstant(node))
67             return false;
68         double value = m_graph.valueOfNumberConstant(node);
69         return !value && 1.0 / value < 0.0;
70     }
71     
72     bool isNotZero(Node* node)
73     {
74         if (!m_graph.isNumberConstant(node))
75             return false;
76         return !!m_graph.valueOfNumberConstant(node);
77     }
78
79     // Tests if the absolute value is strictly less than the power of two.
80     template<int power>
81     bool isWithinPowerOfTwoForConstant(Node* node)
82     {
83         JSValue immediateValue = node->valueOfJSConstant(codeBlock());
84         if (!immediateValue.isNumber())
85             return false;
86         double immediate = immediateValue.asNumber();
87         return immediate > -(static_cast<int64_t>(1) << power) && immediate < (static_cast<int64_t>(1) << power);
88     }
89     
90     template<int power>
91     bool isWithinPowerOfTwoNonRecursive(Node* node)
92     {
93         if (node->op() != JSConstant)
94             return false;
95         return isWithinPowerOfTwoForConstant<power>(node);
96     }
97     
98     template<int power>
99     bool isWithinPowerOfTwo(Node* node)
100     {
101         switch (node->op()) {
102         case JSConstant: {
103             return isWithinPowerOfTwoForConstant<power>(node);
104         }
105             
106         case BitAnd: {
107             if (power > 31)
108                 return true;
109             
110             return isWithinPowerOfTwoNonRecursive<power>(node->child1().node())
111                 || isWithinPowerOfTwoNonRecursive<power>(node->child2().node());
112         }
113             
114         case BitOr:
115         case BitXor:
116         case BitLShift:
117         case ValueToInt32: {
118             return power > 31;
119         }
120             
121         case BitRShift:
122         case BitURShift: {
123             if (power > 31)
124                 return true;
125             
126             Node* shiftAmount = node->child2().node();
127             if (shiftAmount->op() != JSConstant)
128                 return false;
129             JSValue immediateValue = shiftAmount->valueOfJSConstant(codeBlock());
130             if (!immediateValue.isInt32())
131                 return false;
132             return immediateValue.asInt32() > 32 - power;
133         }
134             
135         default:
136             return false;
137         }
138     }
139
140     template<int power>
141     bool isWithinPowerOfTwo(Edge edge)
142     {
143         return isWithinPowerOfTwo<power>(edge.node());
144     }
145
146     bool mergeDefaultFlags(Node* node)
147     {
148         bool changed = false;
149         if (node->flags() & NodeHasVarArgs) {
150             for (unsigned childIdx = node->firstChild();
151                 childIdx < node->firstChild() + node->numChildren();
152                 childIdx++) {
153                 if (!!m_graph.m_varArgChildren[childIdx])
154                     changed |= m_graph.m_varArgChildren[childIdx]->mergeFlags(NodeUsedAsValue);
155             }
156         } else {
157             if (!node->child1())
158                 return changed;
159             changed |= node->child1()->mergeFlags(NodeUsedAsValue);
160             if (!node->child2())
161                 return changed;
162             changed |= node->child2()->mergeFlags(NodeUsedAsValue);
163             if (!node->child3())
164                 return changed;
165             changed |= node->child3()->mergeFlags(NodeUsedAsValue);
166         }
167         return changed;
168     }
169     
170     void propagate(Node* node)
171     {
172         NodeFlags flags = node->flags() & NodeBackPropMask;
173         
174         switch (node->op()) {
175         case GetLocal: {
176             VariableAccessData* variableAccessData = node->variableAccessData();
177             variableAccessData->mergeFlags(flags);
178             break;
179         }
180             
181         case SetLocal: {
182             VariableAccessData* variableAccessData = node->variableAccessData();
183             if (!variableAccessData->isLoadedFrom())
184                 break;
185             node->child1()->mergeFlags(NodeUsedAsValue);
186             break;
187         }
188             
189         case BitAnd:
190         case BitOr:
191         case BitXor:
192         case BitRShift:
193         case BitLShift:
194         case BitURShift: {
195             flags |= NodeUsedAsInt;
196             flags &= ~(NodeUsedAsNumber | NodeNeedsNegZero | NodeUsedAsOther);
197             node->child1()->mergeFlags(flags);
198             node->child2()->mergeFlags(flags);
199             break;
200         }
201             
202         case ValueToInt32: {
203             flags |= NodeUsedAsInt;
204             flags &= ~(NodeUsedAsNumber | NodeNeedsNegZero | NodeUsedAsOther);
205             node->child1()->mergeFlags(flags);
206             break;
207         }
208             
209         case StringCharCodeAt: {
210             node->child1()->mergeFlags(NodeUsedAsValue);
211             node->child2()->mergeFlags(NodeUsedAsValue | NodeUsedAsInt);
212             break;
213         }
214             
215         case Identity: 
216         case UInt32ToNumber: {
217             node->child1()->mergeFlags(flags);
218             break;
219         }
220
221         case ValueAdd: {
222             if (isNotNegZero(node->child1().node()) || isNotNegZero(node->child2().node()))
223                 flags &= ~NodeNeedsNegZero;
224             if (node->child1()->hasNumberResult() || node->child2()->hasNumberResult())
225                 flags &= ~NodeUsedAsOther;
226             if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2()))
227                 flags |= NodeUsedAsNumber;
228             if (!m_allowNestedOverflowingAdditions)
229                 flags |= NodeUsedAsNumber;
230             
231             node->child1()->mergeFlags(flags);
232             node->child2()->mergeFlags(flags);
233             break;
234         }
235             
236         case ArithAdd: {
237             if (isNotNegZero(node->child1().node()) || isNotNegZero(node->child2().node()))
238                 flags &= ~NodeNeedsNegZero;
239             if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2()))
240                 flags |= NodeUsedAsNumber;
241             if (!m_allowNestedOverflowingAdditions)
242                 flags |= NodeUsedAsNumber;
243             
244             node->child1()->mergeFlags(flags);
245             node->child2()->mergeFlags(flags);
246             break;
247         }
248             
249         case ArithSub: {
250             if (isNotZero(node->child1().node()) || isNotZero(node->child2().node()))
251                 flags &= ~NodeNeedsNegZero;
252             if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2()))
253                 flags |= NodeUsedAsNumber;
254             if (!m_allowNestedOverflowingAdditions)
255                 flags |= NodeUsedAsNumber;
256             
257             node->child1()->mergeFlags(flags);
258             node->child2()->mergeFlags(flags);
259             break;
260         }
261             
262         case ArithNegate: {
263             flags &= ~NodeUsedAsOther;
264
265             node->child1()->mergeFlags(flags);
266             break;
267         }
268             
269         case ArithMul: {
270             // As soon as a multiply happens, we can easily end up in the part
271             // of the double domain where the point at which you do truncation
272             // can change the outcome. So, ArithMul always forces its inputs to
273             // check for overflow. Additionally, it will have to check for overflow
274             // itself unless we can prove that there is no way for the values
275             // produced to cause double rounding.
276             
277             if (!isWithinPowerOfTwo<22>(node->child1().node())
278                 && !isWithinPowerOfTwo<22>(node->child2().node()))
279                 flags |= NodeUsedAsNumber;
280             
281             node->mergeFlags(flags);
282             
283             flags |= NodeUsedAsNumber | NodeNeedsNegZero;
284             flags &= ~NodeUsedAsOther;
285
286             node->child1()->mergeFlags(flags);
287             node->child2()->mergeFlags(flags);
288             break;
289         }
290             
291         case ArithDiv: {
292             flags |= NodeUsedAsNumber | NodeNeedsNegZero;
293             flags &= ~NodeUsedAsOther;
294
295             node->child1()->mergeFlags(flags);
296             node->child2()->mergeFlags(flags);
297             break;
298         }
299             
300         case ArithMod: {
301             flags |= NodeUsedAsNumber | NodeNeedsNegZero;
302             flags &= ~NodeUsedAsOther;
303
304             node->child1()->mergeFlags(flags);
305             node->child2()->mergeFlags(flags);
306             break;
307         }
308             
309         case GetByVal: {
310             node->child1()->mergeFlags(NodeUsedAsValue);
311             node->child2()->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther | NodeUsedAsInt);
312             break;
313         }
314             
315         case GetMyArgumentByValSafe: {
316             node->child1()->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther | NodeUsedAsInt);
317             break;
318         }
319             
320         case NewArrayWithSize: {
321             node->child1()->mergeFlags(NodeUsedAsValue | NodeUsedAsInt);
322             break;
323         }
324             
325         case StringCharAt: {
326             node->child1()->mergeFlags(NodeUsedAsValue);
327             node->child2()->mergeFlags(NodeUsedAsValue | NodeUsedAsInt);
328             break;
329         }
330             
331         case ToString: {
332             node->child1()->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther);
333             break;
334         }
335             
336         case ToPrimitive: {
337             node->child1()->mergeFlags(flags);
338             break;
339         }
340             
341         case PutByVal: {
342             m_graph.varArgChild(node, 0)->mergeFlags(NodeUsedAsValue);
343             m_graph.varArgChild(node, 1)->mergeFlags(NodeUsedAsNumber | NodeUsedAsOther | NodeUsedAsInt);
344             m_graph.varArgChild(node, 2)->mergeFlags(NodeUsedAsValue);
345             break;
346         }
347             
348         default:
349             mergeDefaultFlags(node);
350             break;
351         }
352     }
353     
354     bool m_allowNestedOverflowingAdditions;
355 };
356
357 bool performBackwardsPropagation(Graph& graph)
358 {
359     SamplingRegion samplingRegion("DFG Backwards Propagation Phase");
360     return runPhase<BackwardsPropagationPhase>(graph);
361 }
362
363 } } // namespace JSC::DFG
364
365 #endif // ENABLE(DFG_JIT)
366