Attachment #264284 for bug #150656

View Details Raw Unified Return to Bug 150656



2015-10-28  Filip Pizlo  <fpizlo@apple.com>

        B3::reduceStrength() should do DCE
        https://bugs.webkit.org/show_bug.cgi?id=150656

        Reviewed by NOBODY (OOPS!).

        * b3/B3BasicBlock.cpp:
        (JSC::B3::BasicBlock::removeNops): This now deletes the values from the procedure, to preserve the invariant that valuesInProc == valuesInBlocks.
        * b3/B3BasicBlock.h:
        * b3/B3Procedure.cpp:
        (JSC::B3::Procedure::deleteValue): Add a utility used by removeNops().
        (JSC::B3::Procedure::addValueIndex): Make sure that we reuse Value indices so that m_values doesn't get too sparse.
        * b3/B3Procedure.h:
        (JSC::B3::Procedure::ValuesCollection::iterator::iterator): Teach this that m_values can be slightly sparse.
        (JSC::B3::Procedure::ValuesCollection::iterator::operator++):
        (JSC::B3::Procedure::ValuesCollection::iterator::operator!=):
        (JSC::B3::Procedure::ValuesCollection::iterator::findNext):
        (JSC::B3::Procedure::values):
        * b3/B3ProcedureInlines.h:
        (JSC::B3::Procedure::add): Use addValueIndex() instead of always creating a new index.
        * b3/B3ReduceStrength.cpp: Implement the optimization using UseCounts and Effects.

2015-10-28  Joseph Pecoraro  <pecoraro@apple.com>

        Web Inspector: Remove unused / duplicate WebSocket timeline records



#if ENABLE(B3_JIT)

#include "B3BasicBlockUtils.h"
#include "B3Procedure.h"
#include "B3Value.h"
#include <wtf/ListDump.h>


    return B3::replacePredecessor(this, from, to);
}

void BasicBlock::removeNops(Procedure& procedure)
{
    unsigned sourceIndex = 0;
    unsigned targetIndex = 0;
    while (sourceIndex < size()) {
        Value* value = m_values[sourceIndex++];
        if (value->opcode() == Nop)
            procedure.deleteValue(value);
        else
            m_values[targetIndex++] = value;
    }
    m_values.resize(targetIndex);

Lines 95-101 public: Source/JavaScriptCore/b3/B3BasicBlock.h_sec1
- Source/JavaScriptCore/b3/B3BasicBlock.h -1 / +1 lines
95		95
96	double frequency() const { return m_frequency; }	96	double frequency() const { return m_frequency; }
97		97
98	void removeNops();	98	void removeNops(Procedure&);
99		99
100	void dump(PrintStream&) const;	100	void dump(PrintStream&) const;
101	void deepDump(PrintStream&) const;	101	void deepDump(PrintStream&) const;



    return B3::blocksInPostOrder(at(0));
}

void Procedure::deleteValue(Value* value)
{
    ASSERT(m_values[value->index()].get() == value);
    m_valueIndexFreeList.append(value->index());
    m_values[value->index()] = nullptr;
}

size_t Procedure::addValueIndex()
{
    if (m_valueIndexFreeList.isEmpty()) {
        size_t index = m_values.size();
        m_values.append(nullptr);
        return index;
    }
    
    return m_valueIndexFreeList.takeLast();
}

} } // namespace JSC::B3

#endif // ENABLE(B3_JIT)




            iterator(const Procedure& procedure, unsigned index)
                : m_procedure(&procedure)
                , m_index(findNext(index))
            {
            }



            iterator& operator++()
            {
                m_index = findNext(m_index + 1);
                return *this;
            }


            }

        private:
            unsigned findNext(unsigned index)
            {
                while (index < m_procedure->m_values.size() && !m_procedure->m_values[index])
                    index++;
                return index;
            }

            const Procedure* m_procedure;
            unsigned m_index;


    ValuesCollection values() const { return ValuesCollection(*this); }

    void deleteValue(Value*);

    // The name has to be a string literal, since we don't do any memory management for the string.
    void setLastPhaseName(const char* name)
    {

    const char* lastPhaseName() const { return m_lastPhaseName; }

private:
    JS_EXPORT_PRIVATE size_t addValueIndex();
    
    Vector<std::unique_ptr<BasicBlock>> m_blocks;
    Vector<std::unique_ptr<Value>> m_values;
    Vector<size_t> m_valueIndexFreeList;
    const char* m_lastPhaseName;
};




template<typename ValueType, typename... Arguments>
ValueType* Procedure::add(Arguments... arguments)
{
    size_t index = addValueIndex();;
    std::unique_ptr<ValueType> value(new ValueType(index, arguments...));
    ValueType* result = value.get();
    m_values[index] = WTF::move(value);
    return result;
}




#include "B3MemoryValue.h"
#include "B3PhaseScope.h"
#include "B3ProcedureInlines.h"
#include "B3UseCounts.h"
#include "B3ValueInlines.h"

namespace JSC { namespace B3 {

                    process();
                m_insertionSet.execute(m_block);

                block->removeNops(m_proc);
            }

            UseCounts useCounts(m_proc);
            for (Value* value : m_proc.values()) {
                if (!useCounts[value] && !value->effects().mustExecute()) {
                    value->replaceWithNop();
                    m_changed = true;
                }
            }
            
            result |= m_changed;

Return to Bug 150656

Lines 29-34 Source/JavaScriptCore/b3/B3BasicBlock.cpp_sec1
- Source/JavaScriptCore/b3/B3BasicBlock.cpp -2 / +5 lines
29	#if ENABLE(B3_JIT)	29	#if ENABLE(B3_JIT)
30		30
31	#include "B3BasicBlockUtils.h"	31	#include "B3BasicBlockUtils.h"
		32	#include "B3Procedure.h"
32	#include "B3Value.h"	33	#include "B3Value.h"
33	#include <wtf/ListDump.h>	34	#include <wtf/ListDump.h>
34		35
Lines 66-78 bool BasicBlock::replacePredecessor(Basi Source/JavaScriptCore/b3/B3BasicBlock.cpp_sec2
66	return B3::replacePredecessor(this, from, to);	67	return B3::replacePredecessor(this, from, to);
67	}	68	}
68		69
69	void BasicBlock::removeNops()	70	void BasicBlock::removeNops(Procedure& procedure)
70	{	71	{
71	unsigned sourceIndex = 0;	72	unsigned sourceIndex = 0;
72	unsigned targetIndex = 0;	73	unsigned targetIndex = 0;
73	while (sourceIndex < size()) {	74	while (sourceIndex < size()) {
74	Value* value = m_values[sourceIndex++];	75	Value* value = m_values[sourceIndex++];
75	if (value->opcode() != Nop)	76	if (value->opcode() == Nop)
		77	procedure.deleteValue(value);
		78	else
76	m_values[targetIndex++] = value;	79	m_values[targetIndex++] = value;
77	}	80	}
78	m_values.resize(targetIndex);	81	m_values.resize(targetIndex);

Lines 73-78 Vector<BasicBlock*> Procedure::blocksInP Source/JavaScriptCore/b3/B3Procedure.cpp_sec1
- Source/JavaScriptCore/b3/B3Procedure.cpp +18 lines
73	return B3::blocksInPostOrder(at(0));	73	return B3::blocksInPostOrder(at(0));
74	}	74	}
75		75
		76	void Procedure::deleteValue(Value* value)
		77	{
		78	ASSERT(m_values[value->index()].get() == value);
		79	m_valueIndexFreeList.append(value->index());
		80	m_values[value->index()] = nullptr;
		81	}
		82
		83	size_t Procedure::addValueIndex()
		84	{
		85	if (m_valueIndexFreeList.isEmpty()) {
		86	size_t index = m_values.size();
		87	m_values.append(nullptr);
		88	return index;
		89	}
		90
		91	return m_valueIndexFreeList.takeLast();
		92	}
		93
76	} } // namespace JSC::B3	94	} } // namespace JSC::B3
77		95
78	#endif // ENABLE(B3_JIT)	96	#endif // ENABLE(B3_JIT)

Lines 132-138 public: Source/JavaScriptCore/b3/B3Procedure.h_sec1
- Source/JavaScriptCore/b3/B3Procedure.h -2 / +13 lines
132		132
133	iterator(const Procedure& procedure, unsigned index)	133	iterator(const Procedure& procedure, unsigned index)
134	: m_procedure(&procedure)	134	: m_procedure(&procedure)
135	, m_index(index)	135	, m_index(findNext(index))
136	{	136	{
137	}	137	}
138		138
Lines 143-149 public: Source/JavaScriptCore/b3/B3Procedure.h_sec2
143		143
144	iterator& operator++()	144	iterator& operator++()
145	{	145	{
146	m_index++;	146	m_index = findNext(m_index + 1);
147	return *this;	147	return *this;
148	}	148	}
149		149
Lines 159-164 public: Source/JavaScriptCore/b3/B3Procedure.h_sec3
159	}	159	}
160		160
161	private:	161	private:
		162	unsigned findNext(unsigned index)
		163	{
		164	while (index < m_procedure->m_values.size() && !m_procedure->m_values[index])
		165	index++;
		166	return index;
		167	}
162		168
163	const Procedure* m_procedure;	169	const Procedure* m_procedure;
164	unsigned m_index;	170	unsigned m_index;
Lines 177-182 public: Source/JavaScriptCore/b3/B3Procedure.h_sec4
177		183
178	ValuesCollection values() const { return ValuesCollection(*this); }	184	ValuesCollection values() const { return ValuesCollection(*this); }
179		185
		186	void deleteValue(Value*);
		187
180	// The name has to be a string literal, since we don't do any memory management for the string.	188	// The name has to be a string literal, since we don't do any memory management for the string.
181	void setLastPhaseName(const char* name)	189	void setLastPhaseName(const char* name)
182	{	190	{
Lines 186-193 public: Source/JavaScriptCore/b3/B3Procedure.h_sec5
186	const char* lastPhaseName() const { return m_lastPhaseName; }	194	const char* lastPhaseName() const { return m_lastPhaseName; }
187		195
188	private:	196	private:
		197	JS_EXPORT_PRIVATE size_t addValueIndex();
		198
189	Vector<std::unique_ptr<BasicBlock>> m_blocks;	199	Vector<std::unique_ptr<BasicBlock>> m_blocks;
190	Vector<std::unique_ptr<Value>> m_values;	200	Vector<std::unique_ptr<Value>> m_values;
		201	Vector<size_t> m_valueIndexFreeList;
191	const char* m_lastPhaseName;	202	const char* m_lastPhaseName;
192	};	203	};
193		204

Lines 36-44 namespace JSC { namespace B3 { Source/JavaScriptCore/b3/B3ProcedureInlines.h_sec1
- Source/JavaScriptCore/b3/B3ProcedureInlines.h -2 / +3 lines
36	template<typename ValueType, typename... Arguments>	36	template<typename ValueType, typename... Arguments>
37	ValueType* Procedure::add(Arguments... arguments)	37	ValueType* Procedure::add(Arguments... arguments)
38	{	38	{
39	std::unique_ptr<ValueType> value(new ValueType(m_values.size(), arguments...));	39	size_t index = addValueIndex();;
		40	std::unique_ptr<ValueType> value(new ValueType(index, arguments...));
40	ValueType* result = value.get();	41	ValueType* result = value.get();
41	m_values.append(WTF::move(value));	42	m_values[index] = WTF::move(value);
42	return result;	43	return result;
43	}	44	}
44		45

Lines 32-37 Source/JavaScriptCore/b3/B3ReduceStrength.cpp_sec1
- Source/JavaScriptCore/b3/B3ReduceStrength.cpp -2 / +10 lines
32	#include "B3MemoryValue.h"	32	#include "B3MemoryValue.h"
33	#include "B3PhaseScope.h"	33	#include "B3PhaseScope.h"
34	#include "B3ProcedureInlines.h"	34	#include "B3ProcedureInlines.h"
		35	#include "B3UseCounts.h"
35	#include "B3ValueInlines.h"	36	#include "B3ValueInlines.h"
36		37
37	namespace JSC { namespace B3 {	38	namespace JSC { namespace B3 {
Lines 59-66 public: Source/JavaScriptCore/b3/B3ReduceStrength.cpp_sec2
59	process();	60	process();
60	m_insertionSet.execute(m_block);	61	m_insertionSet.execute(m_block);
61		62
62	// FIXME: This should also do DCE.	63	block->removeNops(m_proc);
63	block->removeNops();	64	}
		65
		66	UseCounts useCounts(m_proc);
		67	for (Value* value : m_proc.values()) {
		68	if (!useCounts[value] && !value->effects().mustExecute()) {
		69	value->replaceWithNop();
		70	m_changed = true;
		71	}
64	}	72	}
65		73
66	result \|= m_changed;	74	result \|= m_changed;

Lines 1-3 Source/JavaScriptCore/ChangeLog_sec1
- Source/JavaScriptCore/ChangeLog +23 lines
		1	2015-10-28 Filip Pizlo <fpizlo@apple.com>
		2
		3	B3::reduceStrength() should do DCE
		4	https://bugs.webkit.org/show_bug.cgi?id=150656
		5
		6	Reviewed by NOBODY (OOPS!).
		7
		8	* b3/B3BasicBlock.cpp:
		9	(JSC::B3::BasicBlock::removeNops): This now deletes the values from the procedure, to preserve the invariant that valuesInProc == valuesInBlocks.
		10	* b3/B3BasicBlock.h:
		11	* b3/B3Procedure.cpp:
		12	(JSC::B3::Procedure::deleteValue): Add a utility used by removeNops().
		13	(JSC::B3::Procedure::addValueIndex): Make sure that we reuse Value indices so that m_values doesn't get too sparse.
		14	* b3/B3Procedure.h:
		15	(JSC::B3::Procedure::ValuesCollection::iterator::iterator): Teach this that m_values can be slightly sparse.
		16	(JSC::B3::Procedure::ValuesCollection::iterator::operator++):
		17	(JSC::B3::Procedure::ValuesCollection::iterator::operator!=):
		18	(JSC::B3::Procedure::ValuesCollection::iterator::findNext):
		19	(JSC::B3::Procedure::values):
		20	* b3/B3ProcedureInlines.h:
		21	(JSC::B3::Procedure::add): Use addValueIndex() instead of always creating a new index.
		22	* b3/B3ReduceStrength.cpp: Implement the optimization using UseCounts and Effects.
		23
1	2015-10-28 Joseph Pecoraro <pecoraro@apple.com>	24	2015-10-28 Joseph Pecoraro <pecoraro@apple.com>
2		25
3	Web Inspector: Remove unused / duplicate WebSocket timeline records	26	Web Inspector: Remove unused / duplicate WebSocket timeline records