Changeset 286053 in webkit

Timestamp:

Nov 19, 2021, 1:38:27 AM (5 years ago)

Author:

rmorisset@apple.com

Message:

AirFixObviousSpills should be optimized
​https://bugs.webkit.org/show_bug.cgi?id=228052

Reviewed by Yusuke Suzuki.

There were two problems with AirFixObviousSpills:

• merge() had a quadratic blow-up, as for each element in a vector, it was searching it in a different vector.
• it would visit blocks even when their state at head had not changed.

I fixed the first problem by making sure that the vectors are sorted before calling merge, and making use of that invariant in the search of the vectors
(see filterVectorAgainst)
This reduced the total time spent in that phase from 390ms to 230ms, and the worst case time spent in that phase for one function from 100ms to 30ms (all of the results in this Changelog are for JetStream2 on a M1 MBP).

I fixed the second problem even more easily by adding a m_shouldVisit BitVector. I also moved the m_wasVisited boolean that was in State to a m_notBottom BitVector for simplicity and symmetry.
That change further reduced the total/max time from 230ms/30ms to 140ms/16ms.

• b3/air/AirFixObviousSpills.cpp:

Location:

trunk/Source/JavaScriptCore

Files:

• ChangeLog (modified) (1 diff)
• b3/air/AirFixObviousSpills.cpp (modified) (13 diffs)

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2021-11-19  Robin Morisset  <rmorisset@apple.com>
+
+        AirFixObviousSpills should be optimized
+        https://bugs.webkit.org/show_bug.cgi?id=228052
+
+        Reviewed by Yusuke Suzuki.
+
+        There were two problems with AirFixObviousSpills:
+        - merge() had a quadratic blow-up, as for each element in a vector, it was searching it in a different vector.
+        - it would visit blocks even when their state at head had not changed.
+
+        I fixed the first problem by making sure that the vectors are sorted before calling merge, and making use of that invariant in the search of the vectors
+        (see filterVectorAgainst)
+        This reduced the total time spent in that phase from 390ms to 230ms, and the worst case time spent in that phase for one function from 100ms to 30ms (all of the results in this Changelog are for JetStream2 on a M1 MBP).
+
+        I fixed the second problem even more easily by adding a m_shouldVisit BitVector. I also moved the m_wasVisited boolean that was in State to a m_notBottom BitVector for simplicity and symmetry.
+        That change further reduced the total/max time from 230ms/30ms to 140ms/16ms.
+
+        * b3/air/AirFixObviousSpills.cpp:
+
 2021-11-18  Robin Morisset  <rmorisset@apple.com>
 

trunk/Source/JavaScriptCore/b3/air/AirFixObviousSpills.cpp

@@ -49 +49 @@
         : m_code(code)
         , m_atHead(code.size())
+        , m_notBottom(code.size())
+        , m_shouldVisit(code.size())
     {
     }
@@ -64 +66 @@
     void computeAliases()
     {
-        m_atHead[m_code[0]].wasVisited = true;
+        m_notBottom.quickSet(0);
+        m_shouldVisit.quickSet(0);
         
         bool changed = true;
@@ -70 +73 @@
             changed = false;
             
-            for (BasicBlock* block : m_code) {
+            for (unsigned blockIndex : m_shouldVisit) {
+                m_shouldVisit.quickClear(blockIndex);
+                BasicBlock* block = m_code[blockIndex];
+                ASSERT(m_notBottom.quickGet(blockIndex));
                 m_block = block;
                 m_state = m_atHead[block];
-                if (!m_state.wasVisited)
-                    continue;
 
                 if (AirFixObviousSpillsInternal::verbose)
@@ -82 +86 @@
                     executeInst();
 
+                // Before we call merge we must make sure that the two states are sorted.
+                m_state.sort();
+
                 for (BasicBlock* successor : block->successorBlocks()) {
+                    unsigned successorIndex = successor->index();
                     State& toState = m_atHead[successor];
-                    if (toState.wasVisited)
-                        changed |= toState.merge(m_state);
-                    else {
+                    if (m_notBottom.quickGet(successorIndex)) {
+                        bool changedAtSuccessorHead = toState.merge(m_state);
+                        if (changedAtSuccessorHead) {
+                            changed = true;
+                            m_shouldVisit.quickSet(successorIndex);
+                        }
+                    } else { // The state at head of successor is bottom
                         toState = m_state;
                         changed = true;
+                        m_notBottom.quickSet(successorIndex);
+                        m_shouldVisit.quickSet(successorIndex);
                     }
                 }
@@ -100 +114 @@
             m_block = block;
             m_state = m_atHead[block];
-            RELEASE_ASSERT(m_state.wasVisited);
+            RELEASE_ASSERT(m_notBottom.quickGet(block->index()));
 
             for (m_instIndex = 0; m_instIndex < block->size(); ++m_instIndex) {
@@ -342 +356 @@
         }
 
+        bool operator<(const RegConst& other) const
+        {
+            return reg < other.reg || (reg == other.reg && constant < other.constant);
+        }
+
         void dump(PrintStream& out) const
         {
@@ -379 +398 @@
                 && reg == other.reg
                 && mode == other.mode;
+        }
+
+        bool operator<(const RegSlot& other) const
+        {
+            // We ignore `mode` on purpose, see merge() for how we deal with it.
+            return slot < other.slot || (slot == other.slot && reg < other.reg);
         }
 
@@ -424 +449 @@
         }
 
+        bool operator<(const SlotConst& other) const
+        {
+            return slot < other.slot || (slot == other.slot && constant < other.constant);
+        }
+
         void dump(PrintStream& out) const
         {
@@ -436 +466 @@
         void addAlias(const RegConst& newAlias)
         {
-            return regConst.append(newAlias);
+            regConst.append(newAlias);
+#if ASSERT_ENABLED
+            m_isSorted = false;
+#endif
         }
         void addAlias(const RegSlot& newAlias)
         {
-            return regSlot.append(newAlias);
+            regSlot.append(newAlias);
+#if ASSERT_ENABLED
+            m_isSorted = false;
+#endif
         }
         void addAlias(const SlotConst& newAlias)
         {
-            return slotConst.append(newAlias);
+            slotConst.append(newAlias);
+#if ASSERT_ENABLED
+            m_isSorted = false;
+#endif
         }
         
@@ -545 +584 @@
         }
 
+        void sort()
+        {
+            std::sort(regConst.begin(), regConst.end(), [] (const RegConst& a, const RegConst& b) {
+                return a < b;
+            });
+            std::sort(slotConst.begin(), slotConst.end(), [] (const SlotConst& a, const SlotConst& b) {
+                return a < b;
+            });
+            std::sort(regSlot.begin(), regSlot.end(), [] (const RegSlot& a, const RegSlot& b) {
+                return a < b;
+            });
+#if ASSERT_ENABLED
+            m_isSorted = true;
+#endif
+        }
+
+        // Takes two sorted vectors, for each element in the first, it looks for the first element in the second which is not smaller.
+        // If such an element exist, call f on both the element from the first vector and this element.
+        // Remove the element from the first vector unless f returned true (so f says whether to keep the element)
+        // Returns true if any element has been removed.
+        template<typename T, typename Func>
+        static bool filterVectorAgainst(Vector<T>& own, const Vector<T>& other, Func f)
+        {
+            const T* it = other.begin();
+            const T* end = other.end();
+            return !!own.removeAllMatching(
+                [&] (T& alias) {
+                    it = std::find_if_not(it, end, [&] (const T& otherAlias) {
+                        return otherAlias < alias;
+                    });
+                    if (it == end)
+                        return true;
+                    return !f(alias, *it);
+            });
+        }
+
         bool merge(const State& other)
         {
+            ASSERT(m_isSorted);
+            ASSERT(other.m_isSorted);
             bool changed = false;
-            
-            changed |= !!regConst.removeAllMatching(
-                [&] (RegConst& alias) -> bool {
-                    const RegConst* otherAlias = other.getRegConst(alias.reg);
-                    if (!otherAlias)
-                        return true;
-                    if (alias.constant != otherAlias->constant)
-                        return true;
+
+            changed |= filterVectorAgainst(regConst, other.regConst, [](RegConst& a, const RegConst& b) { return a == b; });
+            changed |= filterVectorAgainst(slotConst, other.slotConst, [](SlotConst& a, const SlotConst& b) { return a == b; });
+            changed |= filterVectorAgainst(regSlot, other.regSlot, [&](RegSlot& alias, const RegSlot& otherAlias) {
+                if (alias.reg != otherAlias.reg || alias.slot != otherAlias.slot)
                     return false;
-                });
-
-            changed |= !!slotConst.removeAllMatching(
-                [&] (SlotConst& alias) -> bool {
-                    const SlotConst* otherAlias = other.getSlotConst(alias.slot);
-                    if (!otherAlias)
-                        return true;
-                    if (alias.constant != otherAlias->constant)
-                        return true;
-                    return false;
-                });
-
-            changed |= !!regSlot.removeAllMatching(
-                [&] (RegSlot& alias) -> bool {
-                    const RegSlot* otherAlias = other.getRegSlot(alias.reg, alias.slot);
-                    if (!otherAlias)
-                        return true;
-                    if (alias.mode != RegSlot::Match32 && alias.mode != otherAlias->mode) {
-                        alias.mode = RegSlot::Match32;
-                        changed = true;
-                    }
-                    return false;
-                });
+                if (alias.mode != RegSlot::Match32 && alias.mode != otherAlias.mode) {
+                    alias.mode = RegSlot::Match32;
+                    changed = true;
+                }
+                return true;
+            });
 
             return changed;
@@ -588 +645 @@
             out.print(
                 "{regConst = [", listDump(regConst), "], slotConst = [", listDump(slotConst),
-                "], regSlot = [", listDump(regSlot), "], wasVisited = ", wasVisited, "}");
+                "], regSlot = [", listDump(regSlot), "]}");
         }
 
@@ -594 +651 @@
         Vector<SlotConst> slotConst;
         Vector<RegSlot> regSlot;
-        bool wasVisited { false };
+#if ASSERT_ENABLED
+        bool m_isSorted { true };
+#endif
     };
 
@@ -600 +659 @@
     IndexMap<BasicBlock*, State> m_atHead;
     State m_state;
+    BitVector m_notBottom;
+    BitVector m_shouldVisit;
     BasicBlock* m_block { nullptr };
     unsigned m_instIndex { 0 };