Attachment 361467 Details for Bug 194222 – WIP_Arith+Shifts+FP

[patch] WIP_Arith+Shifts+FP

WIP_194222_Most (text/plain), 46.78 KB, created by Robin Morisset on 2019-02-07 16:25:49 PST

(hide)

Description:

Filename:

MIME Type:

Creator: Robin Morisset

Created: 2019-02-07 16:25:49 PST

Size: 46.78 KB

patch

obsolete

>Index: Source/JavaScriptCore/b3/B3ReduceStrength.cpp
>===================================================================
>--- Source/JavaScriptCore/b3/B3ReduceStrength.cpp	(revision 241128)
>+++ Source/JavaScriptCore/b3/B3ReduceStrength.cpp	(working copy)
>@@ -484,88 +484,22 @@
>     }
>     
> private:
>-    void reduceValueStrength()
>+    // If giveUp is true and this function cannot find a clever way of producing the requested value, it returns nullptr
>+    Value* tryReducing(Kind kind, Value* child0 = nullptr, Value* child1 = nullptr, Value* child2 = nullptr, bool giveUp = false)
>     {
>-        switch (m_value->opcode()) {
>+        switch(kind.opcode()) {
>         case Opaque:
>             // Turn this: Opaque(Opaque(value))
>             // Into this: Opaque(value)
>-            if (m_value->child(0)->opcode() == Opaque) {
>-                replaceWithIdentity(m_value->child(0));
>-                break;
>-            }
>+            if (child0->opcode() == Opaque)
>+                return child0;
>+
>             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;
>-                    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;
>-            }
>-            
>-            // Turn this: Add(constant1, constant2)
>-            // Into this: constant1 + constant2
>-            if (Value* constantAdd = m_value->child(0)->addConstant(m_proc, m_value->child(1))) {
>-                replaceWithNewValue(constantAdd);
>-                break;
>-            }
>+            if (Value* value = tryReducingCommutativity(kind, child0, child1))
>+                return value;
> 
>-            // 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.
>             //
>@@ -574,166 +508,157 @@
>             //    0 + -0 = 0
>             //    -0 + 0 = 0
>             //    -0 + -0 = -0
>-            if (m_value->child(1)->isInt(0) || m_value->child(1)->isNegativeZero()) {
>-                replaceWithIdentity(m_value->child(0));
>-                break;
>+            if (child1->isInt(0) || child1->isNegativeZero()) {
>+                return child0;
>             }
> 
>-            if (m_value->isInteger()) {
>-                // Turn this: Integer Add(value, Neg(otherValue))
>-                // Into this: Sub(value, otherValue)
>-                if (m_value->child(1)->opcode() == Neg) {
>-                    replaceWithNew<Value>(Sub, m_value->origin(), m_value->child(0), m_value->child(1)->child(0));
>-                    break;
>+            // Turn this: Add(constant1, constant2)
>+            // Into this: constant1 + constant2
>+            if (Value* value = child0->addConstant(m_proc, child1))
>+                return value;
>+
>+            if (child0->isInteger()) {
>+                if (child0->opcode() == Add && child0->child(1)->hasInt()) {
>+                    // Turn this: Add(Add(value, constant1), constant2)
>+                    // Into this: Add(value, constant1 + constant2)
>+                    Value* newSum = child1->addConstant(m_proc, child0->child(1));
>+                    if (newSum)
>+                        return tryReducing(Add, child0->child(0), newSum);
>+                    
>+                    // Turn this: Add(Add(value, constant), otherValue)
>+                    // Into this: Add(Add(value, otherValue), constant)
>+                    if (child0->child(1)->hasInt()) {
>+                        Value* value = child0->child(0);
>+                        Value* constant = child0->child(1);
>+                        Value* otherValue = child1;
>+                        // 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.
>+                        Value* newAdd = tryReducing(Add, value, otherValue);
>+                        return tryReducing(Add, newAdd, constant);
>+                    }
>                 }
> 
>-                // Turn this: Integer Add(Neg(value), otherValue)
>-                // Into this: Sub(otherValue, value)
>-                if (m_value->child(0)->opcode() == Neg) {
>-                    replaceWithNew<Value>(Sub, m_value->origin(), m_value->child(1), m_value->child(0)->child(0));
>-                    break;
>+                // Turn this: Add(otherValue, Add(value, constant))
>+                // Into this: Add(Add(value, otherValue), constant)
>+                if (child1->opcode() == Add && child1->child(1)->hasInt()) {
>+                    Value* value = child1->child(0);
>+                    Value* constant = child1->child(1);
>+                    Value* otherValue = child0;
>+                    // This creates a duplicate add. That's dangerous but probably fine, see above.
>+                    Value* newAdd = tryReducing(Add, value, otherValue);
>+                    return tryReducing(Add, newAdd, constant);
>                 }
> 
>-                // Turn this: Integer Add(Sub(0, value), -1)
>+                // Turn this: Add(value, value)
>+                // Into this: Shl(value, 1)
>+                // This is a useful canonicalization. It's not meant to be a strength reduction.
>+                if (child0 == child1) {
>+                    Value* const1 = m_insertionSet.insert<Const32Value>(m_index, m_value->origin(), 1);
>+                    return tryReducing(Shl, child0, const1);
>+                }
>+
>+                // Turn this: Add(value, Neg(otherValue))
>+                // Into this: Sub(value, otherValue)
>+                if (child1->opcode() == Neg)
>+                    return tryReducing(Sub, child0, child1->child(0));
>+                
>+                // Turn this: Add(Neg(value), otherValue)
>+                // Into this: Sub(otherValue, value)
>+                if (child0->opcode() == Neg)
>+                    return tryReducing(Sub, child1, child0->child(0));
>+                
>+                // Turn this: Add(Sub(0, value), -1)
>                 // Into this: BitXor(value, -1)
>-                if (m_value->child(0)->opcode() == Sub
>-                    && m_value->child(1)->isInt(-1)
>-                    && m_value->child(0)->child(0)->isInt(0)) {
>-                    replaceWithNew<Value>(BitXor, m_value->origin(), m_value->child(0)->child(1), m_value->child(1));
>-                    break;
>-                }
>+                if (child0->opcode() == Sub && child1->isInt(-1) && child0->child(0)->isInt(0))
>+                    return tryReducing(BitXor, child0->child(1), child1);
>             }
>-
>+                
>             break;
>-
>+        
>         case Sub:
>             // Turn this: Sub(constant1, constant2)
>             // Into this: constant1 - constant2
>-            if (Value* constantSub = m_value->child(0)->subConstant(m_proc, m_value->child(1))) {
>-                replaceWithNewValue(constantSub);
>-                break;
>-            }
>+            if (Value* constantSub = child0->subConstant(m_proc, child1))
>+                return constantSub;
> 
>-            if (m_value->isInteger()) {
>+            if (child0->isInteger()) {
>                 // Turn this: Sub(value, constant)
>                 // Into this: Add(value, -constant)
>-                if (Value* negatedConstant = m_value->child(1)->negConstant(m_proc)) {
>-                    m_insertionSet.insertValue(m_index, negatedConstant);
>-                    replaceWithNew<Value>(
>-                        Add, m_value->origin(), m_value->child(0), negatedConstant);
>-                    break;
>-                }
>-                
>+                if (Value* negatedConstant = child1->negConstant(m_proc))
>+                    return tryReducing(Add, child0, negatedConstant);
>+
>                 // Turn this: Sub(0, value)
>                 // Into this: Neg(value)
>-                if (m_value->child(0)->isInt(0)) {
>-                    replaceWithNew<Value>(Neg, m_value->origin(), m_value->child(1));
>-                    break;
>-                }
>+                if (child0->isInt(0))
>+                    return tryReducing(Neg, child1);
> 
>                 // Turn this: Sub(value, value)
>                 // Into this: 0
>-                if (m_value->child(0) == m_value->child(1)) {
>-                    replaceWithNewValue(m_proc.addIntConstant(m_value, 0));
>-                    break;
>-                }
>+                if (child0 == child1)
>+                    return m_proc.addIntConstant(m_value, 0);
> 
>                 // Turn this: Sub(value, Neg(otherValue))
>                 // Into this: Add(value, otherValue)
>-                if (m_value->child(1)->opcode() == Neg) {
>-                    replaceWithNew<Value>(Add, m_value->origin(), m_value->child(0), m_value->child(1)->child(0));
>-                    break;
>-                }
>+                if (child1->opcode() == Neg)
>+                    return tryReducing(Add, child0, child1->child(0));
>             }
> 
>             break;
>-            
>+
>         case Neg:
>             // Turn this: Neg(constant)
>             // Into this: -constant
>-            if (Value* constant = m_value->child(0)->negConstant(m_proc)) {
>-                replaceWithNewValue(constant);
>-                break;
>-            }
>-            
>+            if (Value* constant = child0->negConstant(m_proc))
>+                return constant;
>+
>             // Turn this: Neg(Neg(value))
>             // Into this: value
>-            if (m_value->child(0)->opcode() == Neg) {
>-                replaceWithIdentity(m_value->child(0)->child(0));
>-                break;
>-            }
>-            
>+            if (child0->opcode() == Neg)
>+                return child0->child(0);
>+
>             // Turn this: Integer Neg(Sub(value, otherValue))
>             // Into this: Sub(otherValue, value)
>-            if (m_value->isInteger() && m_value->child(0)->opcode() == Sub) {
>-                replaceWithNew<Value>(Sub, m_value->origin(), m_value->child(0)->child(1), m_value->child(0)->child(0));
>-                break;
>-            }
>+            if (child0->isInteger() && child0->opcode() == Sub)
>+                return tryReducing(Sub, child0->child(1), child0->child(0));
> 
>             break;
> 
>         case Mul:
>-            handleCommutativity();
>+            if (Value* value = tryReducingCommutativity(kind, child0, child1))
>+                return value;
> 
>-            // Turn this: Mul(constant1, constant2)
>-            // Into this: constant1 * constant2
>-            if (Value* value = m_value->child(0)->mulConstant(m_proc, m_value->child(1))) {
>-                replaceWithNewValue(value);
>-                break;
>-            }
>+            if (child1->hasInt()) {
>+                int64_t factor = child1->asInt();
> 
>-            if (m_value->child(1)->hasInt()) {
>-                int64_t factor = m_value->child(1)->asInt();
>-
>                 // Turn this: Mul(value, 0)
>                 // Into this: 0
>                 // Note that we don't do this for doubles because that's wrong. For example, -1 * 0
>                 // and 1 * 0 yield different results.
>-                if (!factor) {
>-                    replaceWithIdentity(m_value->child(1));
>-                    break;
>-                }
>+                if (!factor)
>+                    return child1;
> 
>                 // Turn this: Mul(value, 1)
>                 // Into this: value
>-                if (factor == 1) {
>-                    replaceWithIdentity(m_value->child(0));
>-                    break;
>-                }
>+                if (factor == 1)
>+                    return child0;
> 
>                 // Turn this: Mul(value, -1)
>-                // Into this: Sub(0, value)
>-                if (factor == -1) {
>-                    replaceWithNewValue(
>-                        m_proc.add<Value>(
>-                            Sub, m_value->origin(),
>-                            m_insertionSet.insertIntConstant(m_index, m_value, 0),
>-                            m_value->child(0)));
>-                    break;
>-                }
>-                
>+                // Into this: Neg(value)
>+                if (factor == -1)
>+                    return tryReducing(Neg, child0);
>+
>                 // Turn this: Mul(value, constant)
>                 // Into this: Shl(value, log2(constant))
>                 if (hasOneBitSet(factor)) {
>                     unsigned shiftAmount = WTF::fastLog2(static_cast<uint64_t>(factor));
>-                    replaceWithNewValue(
>-                        m_proc.add<Value>(
>-                            Shl, m_value->origin(), m_value->child(0),
>-                            m_insertionSet.insert<Const32Value>(
>-                                m_index, m_value->origin(), shiftAmount)));
>-                    break;
>+                    Value* shiftConstant = m_insertionSet.insert<Const32Value>(m_index, m_value->origin(), shiftAmount);
>+                    return tryReducing(Shl, child0, shiftConstant);
>                 }
>-            } else if (m_value->child(1)->hasDouble()) {
>-                double factor = m_value->child(1)->asDouble();
>+            } else if (child1->hasDouble() && child1->asDouble() == 1.0)
>+                    return child0;
> 
>-                // Turn this: Mul(value, 1)
>-                // Into this: value
>-                if (factor == 1) {
>-                    replaceWithIdentity(m_value->child(0));
>-                    break;
>-                }
>-            }
>-
>             break;
> 
>         case Div:
>@@ -742,31 +667,25 @@
>             // Note that this uses Div<Chill> semantics. That's fine, because the rules for Div
>             // are strictly weaker: it has corner cases where it's allowed to do anything it
>             // likes.
>-            if (replaceWithNewValue(m_value->child(0)->divConstant(m_proc, m_value->child(1))))
>-                break;
>+            if (Value* value = child0->divConstant(m_proc, child1))
>+                return value;
> 
>-            if (m_value->child(1)->hasInt()) {
>-                switch (m_value->child(1)->asInt()) {
>+            if (child1->hasInt()) {
>+                switch (child1->asInt()) {
>                 case -1:
>                     // Turn this: Div(value, -1)
>                     // Into this: Neg(value)
>-                    replaceWithNewValue(
>-                        m_proc.add<Value>(Neg, m_value->origin(), m_value->child(0)));
>-                    break;
>-
>+                    return tryReducing(Neg, child0);
>                 case 0:
>                     // Turn this: Div(value, 0)
>                     // Into this: 0
>                     // We can do this because it's precisely correct for ChillDiv and for Div we
>                     // are allowed to do whatever we want.
>-                    replaceWithIdentity(m_value->child(1));
>-                    break;
>-
>+                    return child1;
>                 case 1:
>                     // Turn this: Div(value, 1)
>                     // Into this: value
>-                    replaceWithIdentity(m_value->child(0));
>-                    break;
>+                    return child0;
> 
>                 default:
>                     // Perform super comprehensive strength reduction of division. Currently we
>@@ -774,86 +693,68 @@
>                     // operation. We emulate it using 64-bit multiply. We can't emulate 64-bit
>                     // high multiply with a 128-bit multiply because we don't have a 128-bit
>                     // multiply. We could do it with a patchpoint if we cared badly enough.
>-
>-                    if (m_value->type() != Int32)
>+                    if (child0->type() != Int32)
>                         break;
>                     
>                     if (m_proc.optLevel() < 2)
>                         break;
>-
>-                    int32_t divisor = m_value->child(1)->asInt32();
>+                    
>+                    int32_t divisor = child1->asInt32();
>                     DivisionMagic<int32_t> magic = computeDivisionMagic(divisor);
>-
>+                    
>                     // Perform the "high" multiplication. We do it just to get the high bits.
>                     // This is sort of like multiplying by the reciprocal, just more gnarly. It's
>                     // from Hacker's Delight and I don't claim to understand it.
>-                    Value* magicQuotient = m_insertionSet.insert<Value>(
>-                        m_index, Trunc, m_value->origin(),
>-                        m_insertionSet.insert<Value>(
>-                            m_index, ZShr, m_value->origin(),
>-                            m_insertionSet.insert<Value>(
>-                                m_index, Mul, m_value->origin(),
>-                                m_insertionSet.insert<Value>(
>-                                    m_index, SExt32, m_value->origin(), m_value->child(0)),
>-                                m_insertionSet.insert<Const64Value>(
>-                                    m_index, m_value->origin(), magic.magicMultiplier)),
>-                            m_insertionSet.insert<Const32Value>(
>-                                m_index, m_value->origin(), 32)));
>+                    Value* sext32Child0 = tryReducing(SExt32, child0);
>+                    Value* constMagicMultiplier = m_insertionSet.insert<Const64Value>(m_index, m_value->origin(), magic.magicMultiplier);
>+                    Value* product = tryReducing(Mul, sext32Child0, constMagicMultiplier);
>+                    Value* const32 = m_insertionSet.insert<Const32Value>(m_index, m_value->origin(), 32);
>+                    Value* shift = tryReducing(ZShr, product, const32);
>+                    Value* magicQuotient = tryReducing(Trunc, shift);
> 
>-                    if (divisor > 0 && magic.magicMultiplier < 0) {
>-                        magicQuotient = m_insertionSet.insert<Value>(
>-                            m_index, Add, m_value->origin(), magicQuotient, m_value->child(0));
>-                    }
>-                    if (divisor < 0 && magic.magicMultiplier > 0) {
>-                        magicQuotient = m_insertionSet.insert<Value>(
>-                            m_index, Sub, m_value->origin(), magicQuotient, m_value->child(0));
>-                    }
>+                    if (divisor > 0 && magic.magicMultiplier < 0)
>+                        magicQuotient = tryReducing(Add, magicQuotient, child0);
>+                    else if (divisor < 0 && magic.magicMultiplier > 0)
>+                        magicQuotient = tryReducing(Sub, magicQuotient, child0);
>+
>                     if (magic.shift > 0) {
>-                        magicQuotient = m_insertionSet.insert<Value>(
>-                            m_index, SShr, m_value->origin(), magicQuotient,
>-                            m_insertionSet.insert<Const32Value>(
>-                                m_index, m_value->origin(), magic.shift));
>+                        Value* magicShift = m_insertionSet.insert<Const32Value>(m_index, m_value->origin(), magic.shift);
>+                        magicQuotient = tryReducing(SShr, magicQuotient, magicShift);
>                     }
>-                    replaceWithIdentity(
>-                        m_insertionSet.insert<Value>(
>-                            m_index, Add, m_value->origin(), magicQuotient,
>-                            m_insertionSet.insert<Value>(
>-                                m_index, ZShr, m_value->origin(), magicQuotient,
>-                                m_insertionSet.insert<Const32Value>(
>-                                    m_index, m_value->origin(), 31))));
>-                    break;
>+
>+                    Value* const31 = m_insertionSet.insert<Const32Value>(m_index, m_value->origin(), 31);
>+                    Value* shiftedMagicQuotient = tryReducing(ZShr, magicQuotient, const31);
>+                    return tryReducing(Add, magicQuotient, shiftedMagicQuotient);
>                 }
>-                break;
>             }
>+
>             break;
> 
>         case UDiv:
>             // Turn this: UDiv(constant1, constant2)
>             // Into this: constant1 / constant2
>-            if (replaceWithNewValue(m_value->child(0)->uDivConstant(m_proc, m_value->child(1))))
>-                break;
>+            if (Value* value = child0->uDivConstant(m_proc, child1))
>+                return value;
> 
>-            if (m_value->child(1)->hasInt()) {
>-                switch (m_value->child(1)->asInt()) {
>-                case 0:
>-                    // Turn this: UDiv(value, 0)
>-                    // Into this: 0
>-                    // We can do whatever we want here so we might as well do the chill thing,
>-                    // in case we add chill versions of UDiv in the future.
>-                    replaceWithIdentity(m_value->child(1));
>-                    break;
>-
>-                case 1:
>-                    // Turn this: UDiv(value, 1)
>-                    // Into this: value
>-                    replaceWithIdentity(m_value->child(0));
>-                    break;
>-                default:
>-                    // FIXME: We should do comprehensive strength reduction for unsigned numbers. Likely,
>-                    // we will just want copy what llvm does. https://bugs.webkit.org/show_bug.cgi?id=164809
>-                    break;
>+            if (child1->hasInt()) {
>+                switch (child1->asInt()) {
>+                    case 0:
>+                        // Turn this: UDiv(value, 0)
>+                        // Into this: 0
>+                        // We can do whatever we want here so we might as well do the chill thing,
>+                        // in case we add chill versions of UDiv in the future.
>+                        return child1;
>+                    case 1:
>+                        // Turn this: UDiv(value, 1)
>+                        // Into this: value
>+                        return child0;
>+                    default:
>+                        // FIXME: We should do comprehensive strength reduction for unsigned numbers. Likely,
>+                        // we will just want copy what llvm does. https://bugs.webkit.org/show_bug.cgi?id=164809
>+                        break;
>                 }
>             }
>+
>             break;
> 
>         case Mod:
>@@ -860,70 +761,288 @@
>             // Turn this: Mod(constant1, constant2)
>             // Into this: constant1 / constant2
>             // Note that this uses Mod<Chill> semantics.
>-            if (replaceWithNewValue(m_value->child(0)->modConstant(m_proc, m_value->child(1))))
>-                break;
>+            if (Value* value = child0->modConstant(m_proc, child1))
>+                return value;
> 
>             // Modulo by constant is more efficient if we turn it into Div, and then let Div get
>             // optimized.
>-            if (m_value->child(1)->hasInt()) {
>-                switch (m_value->child(1)->asInt()) {
>-                case 0:
>-                    // Turn this: Mod(value, 0)
>-                    // Into this: 0
>-                    // This is correct according to ChillMod semantics.
>-                    replaceWithIdentity(m_value->child(1));
>+            if (child1->hasInt()) {
>+                // Turn this: Mod(value, 0)
>+                // Into this: 0
>+                // This is correct according to ChillMod semantics.
>+                if (!child1->asInt())
>+                    return child1;
>+
>+                if (m_proc.optLevel() < 2)
>                     break;
> 
>-                default:
>-                    if (m_proc.optLevel() < 2)
>-                        break;
>-                    
>-                    // Turn this: Mod(N, D)
>-                    // Into this: Sub(N, Mul(Div(N, D), D))
>-                    //
>-                    // This is a speed-up because we use our existing Div optimizations.
>-                    //
>-                    // Here's an easier way to look at it:
>-                    //     N % D = N - N / D * D
>-                    //
>-                    // Note that this does not work for D = 0 and ChillMod. The expected result is 0.
>-                    // That's why we have a special-case above.
>-                    //     X % 0 = X - X / 0 * 0 = X     (should be 0)
>-                    //
>-                    // This does work for the D = -1 special case.
>-                    //     -2^31 % -1 = -2^31 - -2^31 / -1 * -1
>-                    //                = -2^31 - -2^31 * -1
>-                    //                = -2^31 - -2^31
>-                    //                = 0
>+                // Turn this: Mod(N, D)
>+                // Into this: Sub(N, Mul(Div(N, D), D))
>+                //
>+                // This is a speed-up because we use our existing Div optimizations.
>+                //
>+                // Here's an easier way to look at it:
>+                //     N % D = N - N / D * D
>+                //
>+                // Note that this does not work for D = 0 and ChillMod. The expected result is 0.
>+                // That's why we have a special-case above.
>+                //     X % 0 = X - X / 0 * 0 = X     (should be 0)
>+                //
>+                // This does work for the D = -1 special case.
>+                //     -2^31 % -1 = -2^31 - -2^31 / -1 * -1
>+                //                = -2^31 - -2^31 * -1
>+                //                = -2^31 - -2^31
>+                //                = 0
>+                Kind divKind = Div;
>+                divKind.setIsChill(m_value->isChill());
>+                Value* div = tryReducing(divKind, child0, child1);
>+                Value* mul = tryReducing(Mul, div, child1);
>+                return tryReducing(Sub, child0, mul);
>+            }
> 
>-                    Kind divKind = Div;
>-                    divKind.setIsChill(m_value->isChill());
>-
>-                    replaceWithIdentity(
>-                        m_insertionSet.insert<Value>(
>-                            m_index, Sub, m_value->origin(),
>-                            m_value->child(0),
>-                            m_insertionSet.insert<Value>(
>-                                m_index, Mul, m_value->origin(),
>-                                m_insertionSet.insert<Value>(
>-                                    m_index, divKind, m_value->origin(),
>-                                    m_value->child(0), m_value->child(1)),
>-                                m_value->child(1))));
>-                    break;
>-                }
>-                break;
>-            }
>-            
>             break;
> 
>         case UMod:
>             // Turn this: UMod(constant1, constant2)
>             // Into this: constant1 / constant2
>-            replaceWithNewValue(m_value->child(0)->uModConstant(m_proc, m_value->child(1)));
>+            if (Value* value = child0->uModConstant(m_proc, child1))
>+                return value;
>+
>             // FIXME: We should do what we do for Mod since the same principle applies here.
>             // https://bugs.webkit.org/show_bug.cgi?id=164809
>             break;
> 
>+        case Shl:
>+            // Turn this: Shl(constant1, constant2)
>+            // Into this: constant1 << constant2
>+            if (Value* constant = child0->shlConstant(m_proc, child1))
>+                return constant;
>+
>+            if (Value* value = tryReducingShift(kind, child0, child1))
>+                return value;
>+
>+            break;
>+
>+        case SShr:
>+            // Turn this: SShr(constant1, constant2)
>+            // Into this: constant1 >> constant2
>+            if (Value* constant = child0->sShrConstant(m_proc, child1))
>+                return constant;
>+
>+            if (child1->hasInt32()
>+                && child0->opcode() == Shl
>+                && child0->child(1)->hasInt32()
>+                && child1->asInt32() == child0->child(1)->asInt32()) {
>+                switch (child1->asInt32()) {
>+                case 16:
>+                    if (child0->type() == Int32) {
>+                        // Turn this: SShr(Shl(value, 16), 16)
>+                        // Into this: SExt16(value)
>+                        return tryReducing(SExt16, child0->child(0));
>+                    }
>+                    break;
>+
>+                case 24:
>+                    if (child0->type() == Int32) {
>+                        // Turn this: SShr(Shl(value, 24), 24)
>+                        // Into this: SExt8(value)
>+                        return tryReducing(SExt8, child0->child(0));
>+                    }
>+                    break;
>+
>+                case 32:
>+                    if (child0->type() == Int64) {
>+                        // Turn this: SShr(Shl(value, 32), 32)
>+                        // Into this: SExt32(Trunc(value))
>+                        Value* trunc = tryReducing(Trunc, child0->child(0));
>+                        return tryReducing(SExt32, trunc);
>+                    }
>+                    break;
>+
>+                    // FIXME: Add cases for 48 and 56, but that would translate to SExt32(SExt8) or
>+                    // SExt32(SExt16), which we don't currently lower efficiently.
>+
>+                default:
>+                    break;
>+                }
>+            }
>+
>+            if (Value* value = tryReducingShift(kind, child0, child1))
>+                return value;
>+
>+            break;
>+
>+        case ZShr:
>+            // Turn this: ZShr(constant1, constant2)
>+            // Into this: (unsigned)constant1 >> constant2
>+            if (Value* constant = child0->zShrConstant(m_proc, child1))
>+                return constant;
>+            
>+            if (Value* value = tryReducingShift(kind, child0, child1))
>+                return value;
>+
>+            break;
>+
>+        case RotR:
>+            // Turn this: RotR(constant1, constant2)
>+            // Into this: (constant1 >> constant2) | (constant1 << sizeof(constant1) * 8 - constant2)
>+            if (Value* constant = child0->rotRConstant(m_proc, child1))
>+                return constant;
>+
>+            if (Value* value = tryReducingShift(kind, child0, child1))
>+                return value;
>+
>+            break;
>+
>+        case RotL:
>+            // Turn this: RotL(constant1, constant2)
>+            // Into this: (constant1 << constant2) | (constant1 >> sizeof(constant1) * 8 - constant2)
>+            if (Value* constant = child0->rotLConstant(m_proc, child1))
>+                return constant;
>+
>+            if (Value* value = tryReducingShift(kind, child0, child1))
>+                return value;
>+
>+            break;
>+
>+        case Abs:
>+            // Turn this: Abs(constant)
>+            // Into this: fabs<value->type()>(constant)
>+            if (Value* constant = child0->absConstant(m_proc))
>+                return constant;
>+
>+            // Turn this: Abs(Abs(value))
>+            // Into this: Abs(value)
>+            if (child0->opcode() == Abs)
>+                return child0;
>+
>+            // Turn this: Abs(Neg(value))
>+            // Into this: Abs(value)
>+            if (child0->opcode() == Neg)
>+                return tryReducing(Abs, child0->child(0));
>+
>+            // Turn this: Abs(BitwiseCast(value))
>+            // Into this: BitwiseCast(And(value, mask-top-bit))
>+            if (child0->opcode() == BitwiseCast) {
>+                Value* mask;
>+                if (child0->type() == Double)
>+                    mask = m_insertionSet.insert<Const64Value>(m_index, m_value->origin(), ~(1ll << 63));
>+                else
>+                    mask = m_insertionSet.insert<Const32Value>(m_index, m_value->origin(), ~(1l << 31));
>+
>+                Value* bitAnd = tryReducing(BitAnd, child0->child(0), mask);
>+                return tryReducing(BitwiseCast, bitAnd);
>+            }
>+
>+            break;
>+
>+        case Ceil:
>+            // Turn this: Ceil(constant)
>+            // Into this: ceil<value->type()>(constant)
>+            if (Value* constant = child0->ceilConstant(m_proc))
>+                return constant;
>+            
>+            // Turn this: Ceil(roundedValue)
>+            // Into this: roundedValue
>+            if (child0->isRounded())
>+                return child0;
>+
>+            break;
>+
>+        case Floor:
>+            // Turn this: Floor(constant)
>+            // Into this: floor<value->type()>(constant)
>+            if (Value* constant = child0->floorConstant(m_proc))
>+                return constant;
>+
>+            // Turn this: Floor(roundedValue)
>+            // Into this: roundedValue
>+            if (child0->isRounded())
>+                return child0;
>+
>+            break;
>+
>+        case Sqrt:
>+            // Turn this: Sqrt(constant)
>+            // Into this: sqrt<value->type()>(constant)
>+            if (Value* constant = child0->sqrtConstant(m_proc))
>+                return constant;
>+
>+            break;
>+
>+        default:
>+            break;
>+        }
>+
>+        if (giveUp)
>+            return nullptr;
>+        if (child1 == nullptr)
>+            return m_insertionSet.insert<Value>(m_index, kind, m_value->origin(), child0);
>+        if (child2 == nullptr)
>+            return m_insertionSet.insert<Value>(m_index, kind, m_value->origin(), child0, child1);
>+        return m_insertionSet.insert<Value>(m_index, kind, m_value->origin(), child0, child1, child2);
>+    }
>+
>+    // We canonicalize commutative operations in three ways:
>+    // - AtomicStrongCAS first (important for some patterns to be recognized by LowerToAir)
>+    // - Constants last (makes it easier to eliminate them)
>+    // - Other operands sorted by their index (we use the index over the address to make this at least slightly deterministic)
>+    Value* tryReducingCommutativity(Kind kind, Value* child0, Value* child1)
>+    {
>+        ASSERT(child0 != nullptr);
>+        ASSERT(child1 != nullptr);
>+
>+        if (child1->isConstant() || child0->opcode() == AtomicStrongCAS)
>+            return nullptr;
>+
>+        if (child0->isConstant() || child1->opcode() == AtomicStrongCAS || child0->index() > child1->index())
>+            return tryReducing(kind, child1, child0);
>+        
>+        return nullptr;
>+    }
>+
>+    Value* tryReducingShift(Kind kind, Value* child0, Value* child1)
>+    {
>+        ASSERT(child0 != nullptr);
>+        ASSERT(child1 != nullptr);
>+
>+        // Shift anything by zero is identity.
>+        if (child1->isInt32(0))
>+            return child0;
>+
>+        // The shift already masks its shift amount. If the shift amount is being masked by a
>+        // redundant amount, then remove the mask. For example,
>+        // Turn this: Shl(@x, BitAnd(@y, 63))
>+        // Into this: Shl(@x, @y)
>+        unsigned mask = sizeofType(child0->type()) * 8 - 1;
>+        if (child1->opcode() == BitAnd && child1->child(1)->hasInt32() && (child1->child(1)->asInt32() & mask) == mask)
>+            return tryReducing(kind, child0, child1->child(0));
>+
>+        return nullptr;
>+    }
>+
>+    void reduceValueStrength()
>+    {
>+        Value* reducedValue = nullptr;
>+        switch(m_value->numChildren()) {
>+            case 1:
>+                reducedValue = tryReducing(m_value->kind(), m_value->child(0), nullptr, nullptr, true);
>+                break;
>+            case 2:
>+                reducedValue = tryReducing(m_value->kind(), m_value->child(0), m_value->child(1), nullptr, true);
>+                break;
>+            case 3:
>+                reducedValue = tryReducing(m_value->kind(), m_value->child(0), m_value->child(1), m_value->child(2), true);
>+                break;
>+            default:
>+                break;
>+        }
>+        if (reducedValue) {
>+            replaceWithIdentity(reducedValue);
>+            return;
>+        }
>+
>+        switch (m_value->opcode()) {
>         case BitAnd:
>             handleCommutativity();
> 
>@@ -1119,191 +1238,8 @@
> 
>             break;
> 
>-        case Shl:
>-            // Turn this: Shl(constant1, constant2)
>-            // Into this: constant1 << constant2
>-            if (Value* constant = m_value->child(0)->shlConstant(m_proc, m_value->child(1))) {
>-                replaceWithNewValue(constant);
>-                break;
>-            }
>+        
> 
>-            handleShiftAmount();
>-            break;
>-
>-        case SShr:
>-            // Turn this: SShr(constant1, constant2)
>-            // Into this: constant1 >> constant2
>-            if (Value* constant = m_value->child(0)->sShrConstant(m_proc, m_value->child(1))) {
>-                replaceWithNewValue(constant);
>-                break;
>-            }
>-
>-            if (m_value->child(1)->hasInt32()
>-                && m_value->child(0)->opcode() == Shl
>-                && m_value->child(0)->child(1)->hasInt32()
>-                && m_value->child(1)->asInt32() == m_value->child(0)->child(1)->asInt32()) {
>-                switch (m_value->child(1)->asInt32()) {
>-                case 16:
>-                    if (m_value->type() == Int32) {
>-                        // Turn this: SShr(Shl(value, 16), 16)
>-                        // Into this: SExt16(value)
>-                        replaceWithNewValue(
>-                            m_proc.add<Value>(
>-                                SExt16, m_value->origin(), m_value->child(0)->child(0)));
>-                    }
>-                    break;
>-
>-                case 24:
>-                    if (m_value->type() == Int32) {
>-                        // Turn this: SShr(Shl(value, 24), 24)
>-                        // Into this: SExt8(value)
>-                        replaceWithNewValue(
>-                            m_proc.add<Value>(
>-                                SExt8, m_value->origin(), m_value->child(0)->child(0)));
>-                    }
>-                    break;
>-
>-                case 32:
>-                    if (m_value->type() == Int64) {
>-                        // Turn this: SShr(Shl(value, 32), 32)
>-                        // Into this: SExt32(Trunc(value))
>-                        replaceWithNewValue(
>-                            m_proc.add<Value>(
>-                                SExt32, m_value->origin(),
>-                                m_insertionSet.insert<Value>(
>-                                    m_index, Trunc, m_value->origin(),
>-                                    m_value->child(0)->child(0))));
>-                    }
>-                    break;
>-
>-                // FIXME: Add cases for 48 and 56, but that would translate to SExt32(SExt8) or
>-                // SExt32(SExt16), which we don't currently lower efficiently.
>-
>-                default:
>-                    break;
>-                }
>-
>-                if (m_value->opcode() != SShr)
>-                    break;
>-            }
>-
>-            handleShiftAmount();
>-            break;
>-
>-        case ZShr:
>-            // Turn this: ZShr(constant1, constant2)
>-            // Into this: (unsigned)constant1 >> constant2
>-            if (Value* constant = m_value->child(0)->zShrConstant(m_proc, m_value->child(1))) {
>-                replaceWithNewValue(constant);
>-                break;
>-            }
>-
>-            handleShiftAmount();
>-            break;
>-
>-        case RotR:
>-            // Turn this: RotR(constant1, constant2)
>-            // Into this: (constant1 >> constant2) | (constant1 << sizeof(constant1) * 8 - constant2)
>-            if (Value* constant = m_value->child(0)->rotRConstant(m_proc, m_value->child(1))) {
>-                replaceWithNewValue(constant);
>-                break;
>-            }
>-
>-            handleShiftAmount();
>-            break;
>-
>-        case RotL:
>-            // Turn this: RotL(constant1, constant2)
>-            // Into this: (constant1 << constant2) | (constant1 >> sizeof(constant1) * 8 - constant2)
>-            if (Value* constant = m_value->child(0)->rotLConstant(m_proc, m_value->child(1))) {
>-                replaceWithNewValue(constant);
>-                break;
>-            }
>-
>-            handleShiftAmount();
>-            break;
>-
>-        case Abs:
>-            // Turn this: Abs(constant)
>-            // Into this: fabs<value->type()>(constant)
>-            if (Value* constant = m_value->child(0)->absConstant(m_proc)) {
>-                replaceWithNewValue(constant);
>-                break;
>-            }
>-
>-            // Turn this: Abs(Abs(value))
>-            // Into this: Abs(value)
>-            if (m_value->child(0)->opcode() == Abs) {
>-                replaceWithIdentity(m_value->child(0));
>-                break;
>-            }
>-                
>-            // Turn this: Abs(Neg(value))
>-            // Into this: Abs(value)
>-            if (m_value->child(0)->opcode() == Neg) {
>-                replaceWithIdentity(m_value->child(0)->child(0));
>-                break;
>-            }
>-
>-            // Turn this: Abs(BitwiseCast(value))
>-            // Into this: BitwiseCast(And(value, mask-top-bit))
>-            if (m_value->child(0)->opcode() == BitwiseCast) {
>-                Value* mask;
>-                if (m_value->type() == Double)
>-                    mask = m_insertionSet.insert<Const64Value>(m_index, m_value->origin(), ~(1ll << 63));
>-                else
>-                    mask = m_insertionSet.insert<Const32Value>(m_index, m_value->origin(), ~(1l << 31));
>-
>-                Value* bitAnd = m_insertionSet.insert<Value>(m_index, BitAnd, m_value->origin(),
>-                    m_value->child(0)->child(0),
>-                    mask);
>-                Value* cast = m_insertionSet.insert<Value>(m_index, BitwiseCast, m_value->origin(), bitAnd);
>-                replaceWithIdentity(cast);
>-                break;
>-            }
>-            break;
>-
>-        case Ceil:
>-            // Turn this: Ceil(constant)
>-            // Into this: ceil<value->type()>(constant)
>-            if (Value* constant = m_value->child(0)->ceilConstant(m_proc)) {
>-                replaceWithNewValue(constant);
>-                break;
>-            }
>-
>-            // Turn this: Ceil(roundedValue)
>-            // Into this: roundedValue
>-            if (m_value->child(0)->isRounded()) {
>-                replaceWithIdentity(m_value->child(0));
>-                break;
>-            }
>-            break;
>-
>-        case Floor:
>-            // Turn this: Floor(constant)
>-            // Into this: floor<value->type()>(constant)
>-            if (Value* constant = m_value->child(0)->floorConstant(m_proc)) {
>-                replaceWithNewValue(constant);
>-                break;
>-            }
>-
>-            // Turn this: Floor(roundedValue)
>-            // Into this: roundedValue
>-            if (m_value->child(0)->isRounded()) {
>-                replaceWithIdentity(m_value->child(0));
>-                break;
>-            }
>-            break;
>-
>-        case Sqrt:
>-            // Turn this: Sqrt(constant)
>-            // Into this: sqrt<value->type()>(constant)
>-            if (Value* constant = m_value->child(0)->sqrtConstant(m_proc)) {
>-                replaceWithNewValue(constant);
>-                break;
>-            }
>-            break;
>-
>         case BitwiseCast:
>             // Turn this: BitwiseCast(constant)
>             // Into this: bitwise_cast<value->type()>(constant)
>@@ -2323,27 +2259,6 @@
>         m_changed = true;
>     }
> 
>-    void handleShiftAmount()
>-    {
>-        // Shift anything by zero is identity.
>-        if (m_value->child(1)->isInt32(0)) {
>-            replaceWithIdentity(m_value->child(0));
>-            return;
>-        }
>-
>-        // The shift already masks its shift amount. If the shift amount is being masked by a
>-        // redundant amount, then remove the mask. For example,
>-        // Turn this: Shl(@x, BitAnd(@y, 63))
>-        // Into this: Shl(@x, @y)
>-        unsigned mask = sizeofType(m_value->type()) * 8 - 1;
>-        if (m_value->child(1)->opcode() == BitAnd
>-            && m_value->child(1)->child(1)->hasInt32()
>-            && (m_value->child(1)->child(1)->asInt32() & mask) == mask) {
>-            m_value->child(1) = m_value->child(1)->child(0);
>-            m_changed = true;
>-        }
>-    }
>-
>     void replaceIfRedundant()
>     {
>         m_changed |= m_pureCSE.process(m_value, *m_dominators);
>Index: Source/JavaScriptCore/b3/testb3.cpp
>===================================================================
>--- Source/JavaScriptCore/b3/testb3.cpp	(revision 241128)
>+++ Source/JavaScriptCore/b3/testb3.cpp	(working copy)
>@@ -3984,7 +3984,7 @@
> {
>     Procedure proc;
>     BasicBlock* root = proc.addBlock();
>-    Value* neg = root->appendNew<Value>(proc, Abs, Origin(),
>+    Value* neg = root->appendNew<Value>(proc, Neg, Origin(),
>         root->appendNew<ArgumentRegValue>(proc, Origin(), FPRInfo::argumentFPR0));
>     Value* abs = root->appendNew<Value>(proc, Abs, Origin(), neg);
>     root->appendNewControlValue(proc, Return, Origin(), abs);

Actions: View | Formatted Diff | Diff

Attachments on bug 194222: 361360 | 361361 | 361452 | 361467 | 361480