41472cfe240d3ca7b3dd9449f4e9622eb88d558f
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGStrengthReductionPhase.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
28 #if ENABLE(DFG_JIT)
29
30 #include "DFGStrengthReductionPhase.h"
31
32 #include "DFGGraph.h"
33 #include "DFGInsertionSet.h"
34 #include "DFGPhase.h"
35 #include "DFGPredictionPropagationPhase.h"
36 #include "DFGVariableAccessDataDump.h"
37 #include "JSCInlines.h"
38
39 namespace JSC { namespace DFG {
40
41 class StrengthReductionPhase : public Phase {
42 public:
43     StrengthReductionPhase(Graph& graph)
44         : Phase(graph, "strength reduction")
45         , m_insertionSet(graph)
46     {
47     }
48     
49     bool run()
50     {
51         ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
52         
53         m_changed = false;
54         
55         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
56             m_block = m_graph.block(blockIndex);
57             if (!m_block)
58                 continue;
59             for (m_nodeIndex = 0; m_nodeIndex < m_block->size(); ++m_nodeIndex) {
60                 m_node = m_block->at(m_nodeIndex);
61                 handleNode();
62             }
63             m_insertionSet.execute(m_block);
64         }
65         
66         return m_changed;
67     }
68
69 private:
70     void handleNode()
71     {
72         switch (m_node->op()) {
73         case BitOr:
74             handleCommutativity();
75
76             if (m_node->child2()->isConstant()) {
77                 JSValue op2 = m_graph.valueOfJSConstant(m_node->child2().node());
78                 if (op2.isInt32() && !op2.asInt32()) {
79                     convertToIdentityOverChild1();
80                     break;
81                 }
82             }
83             break;
84             
85         case BitXor:
86         case BitAnd:
87             handleCommutativity();
88             break;
89             
90         case BitLShift:
91         case BitRShift:
92         case BitURShift:
93             if (m_node->child2()->isConstant()) {
94                 JSValue op2 = m_graph.valueOfJSConstant(m_node->child2().node());
95                 if (op2.isInt32() && !(op2.asInt32() & 0x1f)) {
96                     convertToIdentityOverChild1();
97                     break;
98                 }
99             }
100             break;
101             
102         case UInt32ToNumber:
103             if (m_node->child1()->op() == BitURShift
104                 && m_node->child1()->child2()->isConstant()) {
105                 JSValue shiftAmount = m_graph.valueOfJSConstant(
106                     m_node->child1()->child2().node());
107                 if (shiftAmount.isInt32() && (shiftAmount.asInt32() & 0x1f)) {
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         default:
175             break;
176         }
177     }
178             
179     void convertToIdentityOverChild(unsigned childIndex)
180     {
181         m_insertionSet.insertNode(
182             m_nodeIndex, SpecNone, Phantom, m_node->origin, m_node->children);
183         m_node->children.removeEdge(childIndex ^ 1);
184         m_node->convertToIdentity();
185         m_changed = true;
186     }
187     
188     void convertToIdentityOverChild1()
189     {
190         convertToIdentityOverChild(0);
191     }
192     
193     void convertToIdentityOverChild2()
194     {
195         convertToIdentityOverChild(1);
196     }
197     
198     void foldTypedArrayPropertyToConstant(JSArrayBufferView* view, JSValue constant)
199     {
200         prepareToFoldTypedArray(view);
201         m_graph.convertToConstant(m_node, constant);
202         m_changed = true;
203     }
204     
205     void prepareToFoldTypedArray(JSArrayBufferView* view)
206     {
207         m_insertionSet.insertNode(
208             m_nodeIndex, SpecNone, TypedArrayWatchpoint, m_node->origin,
209             OpInfo(view));
210         m_insertionSet.insertNode(
211             m_nodeIndex, SpecNone, Phantom, m_node->origin, m_node->children);
212     }
213     
214     void handleCommutativity()
215     {
216         // If the right side is a constant then there is nothing left to do.
217         if (m_node->child2()->hasConstant())
218             return;
219         
220         // This case ensures that optimizations that look for x + const don't also have
221         // to look for const + x.
222         if (m_node->child1()->hasConstant()) {
223             std::swap(m_node->child1(), m_node->child2());
224             m_changed = true;
225             return;
226         }
227         
228         // This case ensures that CSE is commutativity-aware.
229         if (m_node->child1().node() > m_node->child2().node()) {
230             std::swap(m_node->child1(), m_node->child2());
231             m_changed = true;
232             return;
233         }
234     }
235     
236     InsertionSet m_insertionSet;
237     BasicBlock* m_block;
238     unsigned m_nodeIndex;
239     Node* m_node;
240     bool m_changed;
241 };
242     
243 bool performStrengthReduction(Graph& graph)
244 {
245     SamplingRegion samplingRegion("DFG Strength Reduction Phase");
246     return runPhase<StrengthReductionPhase>(graph);
247 }
248
249 } } // namespace JSC::DFG
250
251 #endif // ENABLE(DFG_JIT)
252