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