[apple/javascriptcore.git] / dfg / DFGStrengthReductionPhase.cpp

/*
 * Copyright (C) 2013 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 */

#include "config.h"
#include "DFGStrengthReductionPhase.h"

#if ENABLE(DFG_JIT)

#include "DFGGraph.h"
#include "DFGInsertionSet.h"
#include "DFGPhase.h"
#include "DFGPredictionPropagationPhase.h"
#include "DFGVariableAccessDataDump.h"
#include "JSCInlines.h"

namespace JSC { namespace DFG {

class StrengthReductionPhase : public Phase {
public:
    StrengthReductionPhase(Graph& graph)
        : Phase(graph, "strength reduction")
        , m_insertionSet(graph)
    {
    }
    
    bool run()
    {
        ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
        
        m_changed = false;
        
        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
            m_block = m_graph.block(blockIndex);
            if (!m_block)
                continue;
            for (m_nodeIndex = 0; m_nodeIndex < m_block->size(); ++m_nodeIndex) {
                m_node = m_block->at(m_nodeIndex);
                handleNode();
            }
            m_insertionSet.execute(m_block);
        }
        
        return m_changed;
    }

private:
    void handleNode()
    {
        switch (m_node->op()) {
        case BitOr:
            handleCommutativity();

            if (m_node->child2()->isConstant()) {
                JSValue op2 = m_graph.valueOfJSConstant(m_node->child2().node());
                if (op2.isInt32() && !op2.asInt32()) {
                    convertToIdentityOverChild1();
                    break;
                }
            }
            break;
            
        case BitXor:
        case BitAnd:
            handleCommutativity();
            break;
            
        case BitLShift:
        case BitRShift:
        case BitURShift:
            if (m_node->child2()->isConstant()) {
                JSValue op2 = m_graph.valueOfJSConstant(m_node->child2().node());
                if (op2.isInt32() && !(op2.asInt32() & 0x1f)) {
                    convertToIdentityOverChild1();
                    break;
                }
            }
            break;
            
        case UInt32ToNumber:
            if (m_node->child1()->op() == BitURShift
                && m_node->child1()->child2()->isConstant()) {
                JSValue shiftAmount = m_graph.valueOfJSConstant(
                    m_node->child1()->child2().node());
                if (shiftAmount.isInt32() && (shiftAmount.asInt32() & 0x1f)
                    && m_node->arithMode() != Arith::DoOverflow) {
                    m_node->convertToIdentity();
                    m_changed = true;
                    break;
                }
            }
            break;
            
        case ArithAdd:
            handleCommutativity();
            
            if (m_graph.isInt32Constant(m_node->child2().node())) {
                int32_t value = m_graph.valueOfInt32Constant(
                    m_node->child2().node());
                if (!value) {
                    convertToIdentityOverChild1();
                    break;
                }
            }
            break;
            
        case ArithMul:
            handleCommutativity();
            break;
            
        case ArithSub:
            if (m_graph.isInt32Constant(m_node->child2().node())
                && m_node->isBinaryUseKind(Int32Use)) {
                int32_t value = m_graph.valueOfInt32Constant(m_node->child2().node());
                if (-value != value) {
                    m_node->setOp(ArithAdd);
                    m_node->child2().setNode(
                        m_insertionSet.insertConstant(
                            m_nodeIndex, m_node->origin, jsNumber(-value)));
                    m_changed = true;
                    break;
                }
            }
            break;
            
        case GetArrayLength:
            if (JSArrayBufferView* view = m_graph.tryGetFoldableViewForChild1(m_node))
                foldTypedArrayPropertyToConstant(view, jsNumber(view->length()));
            break;
            
        case GetTypedArrayByteOffset:
            if (JSArrayBufferView* view = m_graph.tryGetFoldableView(m_node->child1().node()))
                foldTypedArrayPropertyToConstant(view, jsNumber(view->byteOffset()));
            break;
            
        case GetIndexedPropertyStorage:
            if (JSArrayBufferView* view = m_graph.tryGetFoldableViewForChild1(m_node)) {
                if (view->mode() != FastTypedArray) {
                    prepareToFoldTypedArray(view);
                    m_node->convertToConstantStoragePointer(view->vector());
                    m_changed = true;
                    break;
                } else {
                    // FIXME: It would be awesome to be able to fold the property storage for
                    // these GC-allocated typed arrays. For now it doesn't matter because the
                    // most common use-cases for constant typed arrays involve large arrays with
                    // aliased buffer views.
                    // https://bugs.webkit.org/show_bug.cgi?id=125425
                }
            }
            break;
            
        case ValueRep:
        case Int52Rep:
        case DoubleRep: {
            // This short-circuits circuitous conversions, like ValueRep(DoubleRep(value)) or
            // even more complicated things. Like, it can handle a beast like
            // ValueRep(DoubleRep(Int52Rep(value))).
            
            // The only speculation that we would do beyond validating that we have a type that
            // can be represented a certain way is an Int32 check that would appear on Int52Rep
            // nodes. For now, if we see this and the final type we want is an Int52, we use it
            // as an excuse not to fold. The only thing we would need is a Int52RepInt32Use kind.
            bool hadInt32Check = false;
            if (m_node->op() == Int52Rep) {
                if (m_node->child1().useKind() != Int32Use)
                    break;
                hadInt32Check = true;
            }
            for (Node* node = m_node->child1().node(); ; node = node->child1().node()) {
                if (canonicalResultRepresentation(node->result()) ==
                    canonicalResultRepresentation(m_node->result())) {
                    m_insertionSet.insertNode(
                        m_nodeIndex, SpecNone, Phantom, m_node->origin, m_node->child1());
                    if (hadInt32Check) {
                        // FIXME: Consider adding Int52RepInt32Use or even DoubleRepInt32Use,
                        // which would be super weird. The latter would only arise in some
                        // seriously circuitous conversions.
                        if (canonicalResultRepresentation(node->result()) != NodeResultJS)
                            break;
                        
                        m_insertionSet.insertNode(
                            m_nodeIndex, SpecNone, Phantom, m_node->origin,
                            Edge(node, Int32Use));
                    }
                    m_node->child1() = node->defaultEdge();
                    m_node->convertToIdentity();
                    m_changed = true;
                    break;
                }
                
                switch (node->op()) {
                case Int52Rep:
                    if (node->child1().useKind() != Int32Use)
                        break;
                    hadInt32Check = true;
                    continue;
                    
                case DoubleRep:
                case ValueRep:
                    continue;
                    
                default:
                    break;
                }
                break;
            }
            break;
        }
            
        default:
            break;
        }
    }
            
    void convertToIdentityOverChild(unsigned childIndex)
    {
        m_insertionSet.insertNode(
            m_nodeIndex, SpecNone, Phantom, m_node->origin, m_node->children);
        m_node->children.removeEdge(childIndex ^ 1);
        m_node->convertToIdentity();
        m_changed = true;
    }
    
    void convertToIdentityOverChild1()
    {
        convertToIdentityOverChild(0);
    }
    
    void convertToIdentityOverChild2()
    {
        convertToIdentityOverChild(1);
    }
    
    void foldTypedArrayPropertyToConstant(JSArrayBufferView* view, JSValue constant)
    {
        prepareToFoldTypedArray(view);
        m_graph.convertToConstant(m_node, constant);
        m_changed = true;
    }
    
    void prepareToFoldTypedArray(JSArrayBufferView* view)
    {
        m_insertionSet.insertNode(
            m_nodeIndex, SpecNone, TypedArrayWatchpoint, m_node->origin,
            OpInfo(view));
        m_insertionSet.insertNode(
            m_nodeIndex, SpecNone, Phantom, m_node->origin, m_node->children);
    }
    
    void handleCommutativity()
    {
        // If the right side is a constant then there is nothing left to do.
        if (m_node->child2()->hasConstant())
            return;
        
        // This case ensures that optimizations that look for x + const don't also have
        // to look for const + x.
        if (m_node->child1()->hasConstant()) {
            std::swap(m_node->child1(), m_node->child2());
            m_changed = true;
            return;
        }
        
        // This case ensures that CSE is commutativity-aware.
        if (m_node->child1().node() > m_node->child2().node()) {
            std::swap(m_node->child1(), m_node->child2());
            m_changed = true;
            return;
        }
    }
    
    InsertionSet m_insertionSet;
    BasicBlock* m_block;
    unsigned m_nodeIndex;
    Node* m_node;
    bool m_changed;
};
    
bool performStrengthReduction(Graph& graph)
{
    SamplingRegion samplingRegion("DFG Strength Reduction Phase");
    return runPhase<StrengthReductionPhase>(graph);
}

} } // namespace JSC::DFG

#endif // ENABLE(DFG_JIT)
Commit	Line	Data
81345200 A	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
	38	namespace JSC { namespace DFG {
	39
	40	class StrengthReductionPhase : public Phase {
	41	public:
	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
68	private:
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
301	bool 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