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