B3::reduceStrength() should do DCE
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 29 Oct 2015 01:57:17 +0000 (01:57 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 29 Oct 2015 01:57:17 +0000 (01:57 +0000)
https://bugs.webkit.org/show_bug.cgi?id=150656

Reviewed by Saam Barati.

* 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.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@191718 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/b3/B3BasicBlock.cpp
Source/JavaScriptCore/b3/B3BasicBlock.h
Source/JavaScriptCore/b3/B3Procedure.cpp
Source/JavaScriptCore/b3/B3Procedure.h
Source/JavaScriptCore/b3/B3ProcedureInlines.h
Source/JavaScriptCore/b3/B3ReduceStrength.cpp

index 6db42b722b8617e9bd62514563293585a0370020..29ef5f8541b5830f09347b764319406497a4d0d2 100644 (file)
@@ -1,3 +1,26 @@
+2015-10-28  Filip Pizlo  <fpizlo@apple.com>
+
+        B3::reduceStrength() should do DCE
+        https://bugs.webkit.org/show_bug.cgi?id=150656
+
+        Reviewed by Saam Barati.
+
+        * 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
index 56c6533b70c1555c3cbb271adf8163bf281b7801..09cbe74a2f75c3893779afdea3e91c97d05348ae 100644 (file)
@@ -29,6 +29,7 @@
 #if ENABLE(B3_JIT)
 
 #include "B3BasicBlockUtils.h"
+#include "B3Procedure.h"
 #include "B3Value.h"
 #include <wtf/ListDump.h>
 
@@ -66,13 +67,15 @@ bool BasicBlock::replacePredecessor(BasicBlock* from, BasicBlock* to)
     return B3::replacePredecessor(this, from, to);
 }
 
-void BasicBlock::removeNops()
+void BasicBlock::removeNops(Procedure& procedure)
 {
     unsigned sourceIndex = 0;
     unsigned targetIndex = 0;
     while (sourceIndex < size()) {
         Value* value = m_values[sourceIndex++];
-        if (value->opcode() != Nop)
+        if (value->opcode() == Nop)
+            procedure.deleteValue(value);
+        else
             m_values[targetIndex++] = value;
     }
     m_values.resize(targetIndex);
index 7761e24e3be7a82d342993d298c7b0db5bb004ca..b2f4f632ae7f7016f7dd854e80303bedc407d2bf 100644 (file)
@@ -95,7 +95,7 @@ public:
 
     double frequency() const { return m_frequency; }
 
-    void removeNops();
+    void removeNops(Procedure&);
 
     void dump(PrintStream&) const;
     void deepDump(PrintStream&) const;
index cef9bf93f6dfcef0b27e5cd0e1e7f80811d26fe7..d551c6ca95bcc8a44b3f46fcbb8351d603c6d707 100644 (file)
@@ -73,6 +73,24 @@ Vector<BasicBlock*> Procedure::blocksInPostOrder()
     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)
index af37d9be788a1034876d74e2143f4fa746ca158c..288b431177e3a57edab22d2f73985cdf26f9fa56 100644 (file)
@@ -132,7 +132,7 @@ public:
 
             iterator(const Procedure& procedure, unsigned index)
                 : m_procedure(&procedure)
-                , m_index(index)
+                , m_index(findNext(index))
             {
             }
 
@@ -143,7 +143,7 @@ public:
 
             iterator& operator++()
             {
-                m_index++;
+                m_index = findNext(m_index + 1);
                 return *this;
             }
 
@@ -159,6 +159,12 @@ public:
             }
 
         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;
@@ -177,6 +183,8 @@ public:
 
     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)
     {
@@ -186,8 +194,11 @@ public:
     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;
 };
 
index 1e3d933b1edc3e1c5195cad4b240d95f15f40db6..644eb450bafe24d1b3c92b4a69203aed99fae38b 100644 (file)
@@ -36,9 +36,10 @@ namespace JSC { namespace B3 {
 template<typename ValueType, typename... Arguments>
 ValueType* Procedure::add(Arguments... arguments)
 {
-    std::unique_ptr<ValueType> value(new ValueType(m_values.size(), arguments...));
+    size_t index = addValueIndex();
+    std::unique_ptr<ValueType> value(new ValueType(index, arguments...));
     ValueType* result = value.get();
-    m_values.append(WTF::move(value));
+    m_values[index] = WTF::move(value);
     return result;
 }
 
index 36796a328254571c8634fadc2867046f04591086..d9b4f033d0d6bbfbbcca94072dddeaf0a78f42bb 100644 (file)
@@ -32,6 +32,7 @@
 #include "B3MemoryValue.h"
 #include "B3PhaseScope.h"
 #include "B3ProcedureInlines.h"
+#include "B3UseCounts.h"
 #include "B3ValueInlines.h"
 
 namespace JSC { namespace B3 {
@@ -59,8 +60,15 @@ public:
                     process();
                 m_insertionSet.execute(m_block);
 
-                // FIXME: This should also do DCE.
-                block->removeNops();
+                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;