WebKit Bugzilla
Attachment 361467 Details for
Bug 194222
: Reduce the number of iterations in B3ReduceStrength
Home
|
New
|
Browse
|
Search
|
[?]
|
Reports
|
Requests
|
Help
|
New Account
|
Log In
Remember
[x]
|
Forgot Password
Login:
[x]
[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:
WIP_Arith+Shifts+FP
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);
You cannot view the attachment while viewing its details because your browser does not support IFRAMEs.
View the attachment on a separate page
.
View Attachment As Diff
View Attachment As Raw
Actions:
View
|
Formatted Diff
|
Diff
Attachments on
bug 194222
:
361360
|
361361
|
361452
|
361467
|
361480