Attachment 361846 Details for Bug 194081 – Patch

[patch] Patch

B3ReduceStrengthAssociativity (text/plain), 17.83 KB, created by Robin Morisset on 2019-02-12 14:41:34 PST

(hide)

Description:

Filename:

MIME Type:

Creator: Robin Morisset

Created: 2019-02-12 14:41:34 PST

Size: 17.83 KB

patch

obsolete

>Index: Source/JavaScriptCore/ChangeLog
>===================================================================
>--- Source/JavaScriptCore/ChangeLog	(revision 241319)
>+++ Source/JavaScriptCore/ChangeLog	(working copy)
>@@ -1,3 +1,28 @@
>+2019-02-12  Robin Morisset  <rmorisset@apple.com>
>+
>+        B3ReduceStrength should use associativity to canonicalize
>+        https://bugs.webkit.org/show_bug.cgi?id=194081
>+
>+        Reviewed by NOBODY (OOPS!).
>+
>+        This replaces the ad-hoc approach previously used for Add by a general handleCommutativityAssociativity() used by Add/Mul/BitOr/BitAnd/BitXor.
>+        If the value is the root of an interesting expression tree (i.e. some of its children have the same opcode), we gather the leaves of the expression tree, sort them, and rebuild m_value as a properly canonicalized expression tree.
>+        There are a few minor subtleties:
>+        - We only run for Add/Mul on integers, as they are not associative on floating point values in general.
>+        - If we see the same node twice inside the expression tree for Add/Mul, we must bail out. Otherwise we may be trying to fully expand an exponentially large expression that was compressed by sharing.
>+            - However, if we see the same node twice for BitAnd/BitOr we can just ignore it.
>+            - We could in theory try to do something smart for BitXor, but currently we just bail out as for Add/Mul
>+        - We must teach each operation to deal with Op(Op(foo, bar), baz) as if it were Op(foo, Op(bar, baz)) for a few cases.
>+
>+        I used a HashSet and not an IndexSet for the inner nodes seen, as I expect that set to be usually tiny, and an IndexSet's size depends on the number of indices in use by the procedure.
>+
>+        This patch may in theory cause some code duplication by reducing sharing a bit, but nothing more than what was already true for Add.
>+
>+        No new tests, as there are already quite a few tests for associativity in testb3.cpp
>+          (e.g. testSpillGP, testBitXorImmBitXorArgImm, etc..)
>+
>+        * b3/B3ReduceStrength.cpp:
>+
> 2019-02-12  Michael Catanzaro  <mcatanzaro@igalia.com>
> 
>         Unreviewed, fix -Wimplicit-fallthrough warning after r241140
>Index: Source/JavaScriptCore/b3/B3ReduceStrength.cpp
>===================================================================
>--- Source/JavaScriptCore/b3/B3ReduceStrength.cpp	(revision 241267)
>+++ Source/JavaScriptCore/b3/B3ReduceStrength.cpp	(working copy)
>@@ -497,57 +497,12 @@
>             break;
>             
>         case Add:
>-            handleCommutativity();
>-            
>-            if (m_value->child(0)->opcode() == Add && m_value->isInteger()) {
>-                // Turn this: Add(Add(value, constant1), constant2)
>-                // Into this: Add(value, constant1 + constant2)
>-                Value* newSum = m_value->child(1)->addConstant(m_proc, m_value->child(0)->child(1));
>-                if (newSum) {
>-                    m_insertionSet.insertValue(m_index, newSum);
>-                    m_value->child(0) = m_value->child(0)->child(0);
>-                    m_value->child(1) = newSum;
>-                    m_changed = true;
>+            if (m_value->isInteger()) {
>+                if (handleCommutativityAssociativity())
>                     break;
>-                }
>-                
>-                // Turn this: Add(Add(value, constant), otherValue)
>-                // Into this: Add(Add(value, otherValue), constant)
>-                if (!m_value->child(1)->hasInt() && m_value->child(0)->child(1)->hasInt()) {
>-                    Value* value = m_value->child(0)->child(0);
>-                    Value* constant = m_value->child(0)->child(1);
>-                    Value* otherValue = m_value->child(1);
>-                    // This could create duplicate code if Add(value, constant) is used elsewhere.
>-                    // However, we already model adding a constant as if it was free in other places
>-                    // so let's just roll with it. The alternative would mean having to do good use
>-                    // counts, which reduceStrength() currently doesn't have.
>-                    m_value->child(0) =
>-                        m_insertionSet.insert<Value>(
>-                            m_index, Add, m_value->origin(), value, otherValue);
>-                    m_value->child(1) = constant;
>-                    m_changed = true;
>-                    break;
>-                }
>-            }
>-            
>-            // Turn this: Add(otherValue, Add(value, constant))
>-            // Into this: Add(Add(value, otherValue), constant)
>-            if (m_value->isInteger()
>-                && !m_value->child(0)->hasInt()
>-                && m_value->child(1)->opcode() == Add
>-                && m_value->child(1)->child(1)->hasInt()) {
>-                Value* value = m_value->child(1)->child(0);
>-                Value* constant = m_value->child(1)->child(1);
>-                Value* otherValue = m_value->child(0);
>-                // This creates a duplicate add. That's dangerous but probably fine, see above.
>-                m_value->child(0) =
>-                    m_insertionSet.insert<Value>(
>-                        m_index, Add, m_value->origin(), value, otherValue);
>-                m_value->child(1) = constant;
>-                m_changed = true;
>-                break;
>-            }
>-            
>+            } else
>+                handleCommutativity();
>+
>             // Turn this: Add(constant1, constant2)
>             // Into this: constant1 + constant2
>             if (Value* constantAdd = m_value->child(0)->addConstant(m_proc, m_value->child(1))) {
>@@ -555,17 +510,6 @@
>                 break;
>             }
> 
>-            // Turn this: Integer Add(value, value)
>-            // Into this: Shl(value, 1)
>-            // This is a useful canonicalization. It's not meant to be a strength reduction.
>-            if (m_value->isInteger() && m_value->child(0) == m_value->child(1)) {
>-                replaceWithNewValue(
>-                    m_proc.add<Value>(
>-                        Shl, m_value->origin(), m_value->child(0),
>-                        m_insertionSet.insert<Const32Value>(m_index, m_value->origin(), 1)));
>-                break;
>-            }
>-
>             // Turn this: Add(value, zero)
>             // Into an Identity.
>             //
>@@ -580,6 +524,28 @@
>             }
> 
>             if (m_value->isInteger()) {
>+                // Turn this: Integer Add(value, value)
>+                // Into this: Shl(value, 1)
>+                // This is a useful canonicalization. It's not meant to be a strength reduction.
>+                if (m_value->child(0) == m_value->child(1)) {
>+                    replaceWithNewValue(m_proc.add<Value>(
>+                        Shl, m_value->origin(), m_value->child(0),
>+                        m_insertionSet.insert<Const32Value>(m_index, m_value->origin(), 1)));
>+                    break;
>+                }
>+
>+                // Turn this: Integer Add(Add(value, constant1), constant2)
>+                // Into this: Add(value, constant1 + constant2)
>+                if (m_value->child(0)->opcode() == Add) {
>+                    if (Value* newSum = m_value->child(1)->addConstant(m_proc, m_value->child(0)->child(1))) {
>+                        m_insertionSet.insertValue(m_index, newSum);
>+                        m_value->child(0) = m_value->child(0)->child(0);
>+                        m_value->child(1) = newSum;
>+                        m_changed = true;
>+                        break;
>+                    }
>+                }
>+
>                 // Turn this: Integer Add(value, Neg(otherValue))
>                 // Into this: Sub(value, otherValue)
>                 if (m_value->child(1)->opcode() == Neg) {
>@@ -673,7 +639,11 @@
>             break;
> 
>         case Mul:
>-            handleCommutativity();
>+            if (m_value->isInteger()) {
>+                if (handleCommutativityAssociativity())
>+                    break;
>+            } else
>+                handleCommutativity();
> 
>             // Turn this: Mul(constant1, constant2)
>             // Into this: constant1 * constant2
>@@ -711,7 +681,19 @@
>                             m_value->child(0)));
>                     break;
>                 }
>-                
>+
>+                // Turn this: Integer Mul(Add(value, constant1), constant2)
>+                // Into this: Mul(value, constant1 * constant2)
>+                if (m_value->child(0)->opcode() == Mul) {
>+                    if (Value* newProd = m_value->child(1)->mulConstant(m_proc, m_value->child(0)->child(1))) {
>+                        m_insertionSet.insertValue(m_index, newProd);
>+                        m_value->child(0) = m_value->child(0)->child(0);
>+                        m_value->child(1) = newProd;
>+                        m_changed = true;
>+                        break;
>+                    }
>+                }
>+                    
>                 // Turn this: Mul(value, constant)
>                 // Into this: Shl(value, log2(constant))
>                 if (hasOneBitSet(factor)) {
>@@ -925,7 +907,8 @@
>             break;
> 
>         case BitAnd:
>-            handleCommutativity();
>+            if (handleCommutativityAssociativity())
>+                break;
> 
>             // Turn this: BitAnd(constant1, constant2)
>             // Into this: constant1 & constant2
>@@ -934,9 +917,9 @@
>                 break;
>             }
> 
>-            // Turn this: BitAnd(BitAnd(value, constant1), constant2)
>-            // Into this: BitAnd(value, constant1 & constant2).
>             if (m_value->child(0)->opcode() == BitAnd) {
>+                // Turn this: BitAnd(BitAnd(value, constant1), constant2)
>+                // Into this: BitAnd(value, constant1 & constant2).
>                 Value* newConstant = m_value->child(1)->bitAndConstant(m_proc, m_value->child(0)->child(1));
>                 if (newConstant) {
>                     m_insertionSet.insertValue(m_index, newConstant);
>@@ -943,6 +926,11 @@
>                     m_value->child(0) = m_value->child(0)->child(0);
>                     m_value->child(1) = newConstant;
>                     m_changed = true;
>+                    // Turn this: BitAnd(BitAnd(value, x), x)
>+                    // Into this: BitAnd(value, x).
>+                } else if (m_value->child(0)->child(1) == m_value->child(1)) {
>+                    replaceWithIdentity(m_value->child(0));
>+                    break;
>                 }
>             }
> 
>@@ -1027,7 +1015,8 @@
>             break;
> 
>         case BitOr:
>-            handleCommutativity();
>+            if (handleCommutativityAssociativity())
>+                break;
> 
>             // Turn this: BitOr(constant1, constant2)
>             // Into this: constant1 | constant2
>@@ -1036,9 +1025,9 @@
>                 break;
>             }
> 
>-            // Turn this: BitOr(BitOr(value, constant1), constant2)
>-            // Into this: BitOr(value, constant1 & constant2).
>             if (m_value->child(0)->opcode() == BitOr) {
>+                // Turn this: BitOr(BitOr(value, constant1), constant2)
>+                // Into this: BitOr(value, constant1 & constant2).
>                 Value* newConstant = m_value->child(1)->bitOrConstant(m_proc, m_value->child(0)->child(1));
>                 if (newConstant) {
>                     m_insertionSet.insertValue(m_index, newConstant);
>@@ -1045,6 +1034,11 @@
>                     m_value->child(0) = m_value->child(0)->child(0);
>                     m_value->child(1) = newConstant;
>                     m_changed = true;
>+                    // Turn this: BitOr(BitOr(value, x), x)
>+                    // Into this: BitOr(value, x).
>+                } else if (m_value->child(0)->child(1) == m_value->child(1)) {
>+                    replaceWithIdentity(m_value->child(0));
>+                    break;
>                 }
>             }
> 
>@@ -1073,7 +1067,8 @@
>             break;
> 
>         case BitXor:
>-            handleCommutativity();
>+            if (handleCommutativityAssociativity())
>+                break;
> 
>             // Turn this: BitXor(constant1, constant2)
>             // Into this: constant1 ^ constant2
>@@ -1082,9 +1077,9 @@
>                 break;
>             }
> 
>-            // Turn this: BitXor(BitXor(value, constant1), constant2)
>-            // Into this: BitXor(value, constant1 ^ constant2).
>             if (m_value->child(0)->opcode() == BitXor) {
>+                // Turn this: BitXor(BitXor(value, constant1), constant2)
>+                // Into this: BitXor(value, constant1 ^ constant2).
>                 Value* newConstant = m_value->child(1)->bitXorConstant(m_proc, m_value->child(0)->child(1));
>                 if (newConstant) {
>                     m_insertionSet.insertValue(m_index, newConstant);
>@@ -1091,6 +1086,11 @@
>                     m_value->child(0) = m_value->child(0)->child(0);
>                     m_value->child(1) = newConstant;
>                     m_changed = true;
>+                    // Turn this: BitXor(BitXor(otherValue, valueX), valueX)
>+                    // Into this: otherValue.
>+                } else if (m_value->child(0)->child(1) == m_value->child(1)) {
>+                    replaceWithIdentity(m_value->child(0)->child(0));
>+                    break;
>                 }
>             }
> 
>@@ -2170,29 +2170,31 @@
>         predecessor->updatePredecessorsAfter();
>     }
> 
>+    // AtomicStrongCAS should always go first, it is expected by some pattern in B3LowerToAir
>+    // Constants should always go last, this let us eliminate them in various patterns in this file
>+    // Finally we sort everything else by index to canonicalize expressions, and make things easier for CSE.
>+    //   We use the index and not the address to make this at least slightly deterministic.
>+    static bool shouldGoBefore(Value* x, Value* y)
>+    {
>+        if ((x->opcode() == AtomicStrongCAS && y->opcode() != AtomicStrongCAS)
>+            || (!x->isConstant() && y->isConstant())) {
>+            return true;
>+        }
>+        
>+        if ((x->opcode() != AtomicStrongCAS && y->opcode() == AtomicStrongCAS)
>+            || (x->isConstant() && !y->isConstant())) {
>+            return false;
>+        }
>+        
>+        return x->index() < y->index();
>+    };
>+
>     static bool shouldSwapBinaryOperands(Value* value)
>     {
>         // Note that we have commutative operations that take more than two children. Those operations may
>         // commute their first two children while leaving the rest unaffected.
>         ASSERT(value->numChildren() >= 2);
>-
>-        // Leave it alone if the right child is a constant.
>-        if (value->child(1)->isConstant()
>-            || value->child(0)->opcode() == AtomicStrongCAS)
>-            return false;
>-
>-        if (value->child(0)->isConstant())
>-            return true;
>-
>-        if (value->child(1)->opcode() == AtomicStrongCAS)
>-            return true;
>-
>-        // Sort the operands. This is an important canonicalization. We use the index instead of
>-        // the address to make this at least slightly deterministic.
>-        if (value->child(0)->index() > value->child(1)->index())
>-            return true;
>-
>-        return false;
>+        return shouldGoBefore(value->child(1), value->child(0));
>     }
> 
>     // Turn this: Add(constant, value)
>@@ -2210,6 +2212,68 @@
>         }
>     }
> 
>+    // Returns true if m_value has been replaced by an identity.
>+    bool handleCommutativityAssociativity()
>+    {
>+        ASSERT(m_value->numChildren() == 2);
>+
>+        if (m_proc.optLevel() < 2) {
>+            handleCommutativity();
>+            return false;
>+        }
>+
>+        Opcode op = m_value->opcode();
>+        if (m_value->child(0)->opcode() != op && m_value->child(1)->opcode() != op) {
>+            handleCommutativity();
>+            return false;
>+        }
>+
>+        // Since child(0) is already canonicalized, if this condition is true, there is nothing for us to do.
>+        if (m_value->child(0)->opcode() == op
>+            && m_value->child(1)->opcode() != op
>+            && !shouldGoBefore(m_value->child(1), m_value->child(0)->child(1))) {
>+            return false;
>+        }
>+        
>+        // If we have work to do, we proceed in two steps:
>+        // - first we gather all of the leaves of the expression tree rooted at m_values (Values that have a different op)
>+        // - then we sort them, and generate the canonical expression tree.
>+
>+        // We must track the already visited inner nodes, to abort if one has already been seen.
>+        // Otherwise we will try to expand the tree, which would take exponential time and space for the following code (or any other example with lots of sharing):
>+        //  @2 = Add(@1, @0);
>+        //  @3 = Add(@2, @1);
>+        //  ...
>+        //  @n+2 = Add(@n+!, @n);
>+        // This pattern appears in testB3::testSpillGP.
>+        // One exception is BitAnd and BitOr: we can just ignore repeated copies of operands as they are idempotent.
>+        HashSet<Value*> treeInnerNodes;
>+        Vector<Value*, 4> leaves;
>+        Vector<Value*, 1> worklist = { m_value };
>+        while (!worklist.isEmpty()) {
>+            Value* val = worklist.takeLast();
>+            if (val->opcode() == op) {
>+                if (treeInnerNodes.contains(val)) {
>+                    if (op == BitOr || op == BitAnd)
>+                        continue;
>+                    return false;
>+                }
>+                treeInnerNodes.add(val);
>+                worklist.append(val->child(0));
>+                worklist.append(val->child(1));
>+            } else // val->opcode != op
>+                leaves.append(val);
>+        }
>+
>+        std::sort(leaves.begin(), leaves.end(), [](Value* x, Value* y) {return shouldGoBefore(x, y);});
>+        
>+        Value* lastOp = m_insertionSet.insert<Value>(m_index, op, m_value->origin(), leaves[0], leaves[1]);
>+        for (size_t i = 2; i < leaves.size(); ++i)
>+            lastOp = m_insertionSet.insert<Value>(m_index, op, m_value->origin(), lastOp, leaves[i]);
>+        replaceWithIdentity(lastOp);
>+        return true;
>+    }
>+
>     struct CanonicalizedComparison {
>         Opcode opcode;
>         Value* operands[2];

Flags:

rmorisset: review-

Actions: View | Formatted Diff | Diff

Attachments on bug 194081: 361843 | 361846 | 366286 | 366288 | 366294 | 366657 | 366686 | 366687