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 "DFGStrengthReductionPhase.h"
28
29#if ENABLE(DFG_JIT)
30
31#include "DFGGraph.h"
32#include "DFGInsertionSet.h"
33#include "DFGPhase.h"
34#include "DFGPredictionPropagationPhase.h"
35#include "DFGVariableAccessDataDump.h"
36#include "JSCInlines.h"
37
38namespace JSC { namespace DFG {
39
40class StrengthReductionPhase : public Phase {
41public:
42    StrengthReductionPhase(Graph& graph)
43        : Phase(graph, "strength reduction")
44        , m_insertionSet(graph)
45    {
46    }
47
48    bool run()
49    {
50        ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
51
52        m_changed = false;
53
54        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
55            m_block = m_graph.block(blockIndex);
56            if (!m_block)
57                continue;
58            for (m_nodeIndex = 0; m_nodeIndex < m_block->size(); ++m_nodeIndex) {
59                m_node = m_block->at(m_nodeIndex);
60                handleNode();
61            }
62            m_insertionSet.execute(m_block);
63        }
64
65        return m_changed;
66    }
67
68private:
69    void handleNode()
70    {
71        switch (m_node->op()) {
72        case BitOr:
73            handleCommutativity();
74
75            if (m_node->child2()->isConstant()) {
76                JSValue op2 = m_graph.valueOfJSConstant(m_node->child2().node());
77                if (op2.isInt32() && !op2.asInt32()) {
78                    convertToIdentityOverChild1();
79                    break;
80                }
81            }
82            break;
83
84        case BitXor:
85        case BitAnd:
86            handleCommutativity();
87            break;
88
89        case BitLShift:
90        case BitRShift:
91        case BitURShift:
92            if (m_node->child2()->isConstant()) {
93                JSValue op2 = m_graph.valueOfJSConstant(m_node->child2().node());
94                if (op2.isInt32() && !(op2.asInt32() & 0x1f)) {
95                    convertToIdentityOverChild1();
96                    break;
97                }
98            }
99            break;
100
101        case UInt32ToNumber:
102            if (m_node->child1()->op() == BitURShift
103                && m_node->child1()->child2()->isConstant()) {
104                JSValue shiftAmount = m_graph.valueOfJSConstant(
105                    m_node->child1()->child2().node());
106                if (shiftAmount.isInt32() && (shiftAmount.asInt32() & 0x1f)
107                    && m_node->arithMode() != Arith::DoOverflow) {
108                    m_node->convertToIdentity();
109                    m_changed = true;
110                    break;
111                }
112            }
113            break;
114
115        case ArithAdd:
116            handleCommutativity();
117
118            if (m_graph.isInt32Constant(m_node->child2().node())) {
119                int32_t value = m_graph.valueOfInt32Constant(
120                    m_node->child2().node());
121                if (!value) {
122                    convertToIdentityOverChild1();
123                    break;
124                }
125            }
126            break;
127
128        case ArithMul:
129            handleCommutativity();
130            break;
131
132        case ArithSub:
133            if (m_graph.isInt32Constant(m_node->child2().node())
134                && m_node->isBinaryUseKind(Int32Use)) {
135                int32_t value = m_graph.valueOfInt32Constant(m_node->child2().node());
136                if (-value != value) {
137                    m_node->setOp(ArithAdd);
138                    m_node->child2().setNode(
139                        m_insertionSet.insertConstant(
140                            m_nodeIndex, m_node->origin, jsNumber(-value)));
141                    m_changed = true;
142                    break;
143                }
144            }
145            break;
146
147        case GetArrayLength:
148            if (JSArrayBufferView* view = m_graph.tryGetFoldableViewForChild1(m_node))
149                foldTypedArrayPropertyToConstant(view, jsNumber(view->length()));
150            break;
151
152        case GetTypedArrayByteOffset:
153            if (JSArrayBufferView* view = m_graph.tryGetFoldableView(m_node->child1().node()))
154                foldTypedArrayPropertyToConstant(view, jsNumber(view->byteOffset()));
155            break;
156
157        case GetIndexedPropertyStorage:
158            if (JSArrayBufferView* view = m_graph.tryGetFoldableViewForChild1(m_node)) {
159                if (view->mode() != FastTypedArray) {
160                    prepareToFoldTypedArray(view);
161                    m_node->convertToConstantStoragePointer(view->vector());
162                    m_changed = true;
163                    break;
164                } else {
165                    // FIXME: It would be awesome to be able to fold the property storage for
166                    // these GC-allocated typed arrays. For now it doesn't matter because the
167                    // most common use-cases for constant typed arrays involve large arrays with
168                    // aliased buffer views.
169                    // https://bugs.webkit.org/show_bug.cgi?id=125425
170                }
171            }
172            break;
173
174        case ValueRep:
175        case Int52Rep:
176        case DoubleRep: {
177            // This short-circuits circuitous conversions, like ValueRep(DoubleRep(value)) or
178            // even more complicated things. Like, it can handle a beast like
179            // ValueRep(DoubleRep(Int52Rep(value))).
180
181            // The only speculation that we would do beyond validating that we have a type that
182            // can be represented a certain way is an Int32 check that would appear on Int52Rep
183            // nodes. For now, if we see this and the final type we want is an Int52, we use it
184            // as an excuse not to fold. The only thing we would need is a Int52RepInt32Use kind.
185            bool hadInt32Check = false;
186            if (m_node->op() == Int52Rep) {
187                if (m_node->child1().useKind() != Int32Use)
188                    break;
189                hadInt32Check = true;
190            }
191            for (Node* node = m_node->child1().node(); ; node = node->child1().node()) {
192                if (canonicalResultRepresentation(node->result()) ==
193                    canonicalResultRepresentation(m_node->result())) {
194                    m_insertionSet.insertNode(
195                        m_nodeIndex, SpecNone, Phantom, m_node->origin, m_node->child1());
196                    if (hadInt32Check) {
197                        // FIXME: Consider adding Int52RepInt32Use or even DoubleRepInt32Use,
198                        // which would be super weird. The latter would only arise in some
199                        // seriously circuitous conversions.
200                        if (canonicalResultRepresentation(node->result()) != NodeResultJS)
201                            break;
202
203                        m_insertionSet.insertNode(
204                            m_nodeIndex, SpecNone, Phantom, m_node->origin,
205                            Edge(node, Int32Use));
206                    }
207                    m_node->child1() = node->defaultEdge();
208                    m_node->convertToIdentity();
209                    m_changed = true;
210                    break;
211                }
212
213                switch (node->op()) {
214                case Int52Rep:
215                    if (node->child1().useKind() != Int32Use)
216                        break;
217                    hadInt32Check = true;
218                    continue;
219
220                case DoubleRep:
221                case ValueRep:
222                    continue;
223
224                default:
225                    break;
226                }
227                break;
228            }
229            break;
230        }
231
232        default:
233            break;
234        }
235    }
236
237    void convertToIdentityOverChild(unsigned childIndex)
238    {
239        m_insertionSet.insertNode(
240            m_nodeIndex, SpecNone, Phantom, m_node->origin, m_node->children);
241        m_node->children.removeEdge(childIndex ^ 1);
242        m_node->convertToIdentity();
243        m_changed = true;
244    }
245
246    void convertToIdentityOverChild1()
247    {
248        convertToIdentityOverChild(0);
249    }
250
251    void convertToIdentityOverChild2()
252    {
253        convertToIdentityOverChild(1);
254    }
255
256    void foldTypedArrayPropertyToConstant(JSArrayBufferView* view, JSValue constant)
257    {
258        prepareToFoldTypedArray(view);
259        m_graph.convertToConstant(m_node, constant);
260        m_changed = true;
261    }
262
263    void prepareToFoldTypedArray(JSArrayBufferView* view)
264    {
265        m_insertionSet.insertNode(
266            m_nodeIndex, SpecNone, TypedArrayWatchpoint, m_node->origin,
267            OpInfo(view));
268        m_insertionSet.insertNode(
269            m_nodeIndex, SpecNone, Phantom, m_node->origin, m_node->children);
270    }
271
272    void handleCommutativity()
273    {
274        // If the right side is a constant then there is nothing left to do.
275        if (m_node->child2()->hasConstant())
276            return;
277
278        // This case ensures that optimizations that look for x + const don't also have
279        // to look for const + x.
280        if (m_node->child1()->hasConstant()) {
281            std::swap(m_node->child1(), m_node->child2());
282            m_changed = true;
283            return;
284        }
285
286        // This case ensures that CSE is commutativity-aware.
287        if (m_node->child1().node() > m_node->child2().node()) {
288            std::swap(m_node->child1(), m_node->child2());
289            m_changed = true;
290            return;
291        }
292    }
293
294    InsertionSet m_insertionSet;
295    BasicBlock* m_block;
296    unsigned m_nodeIndex;
297    Node* m_node;
298    bool m_changed;
299};
300
301bool performStrengthReduction(Graph& graph)
302{
303    SamplingRegion samplingRegion("DFG Strength Reduction Phase");
304    return runPhase<StrengthReductionPhase>(graph);
305}
306
307} } // namespace JSC::DFG
308
309#endif // ENABLE(DFG_JIT)
310
311