Page MenuHomePhabricator

Add constant combines for `(urem/srem (mul X, Y), (mul X, Z))`
ClosedPublic

Authored by goldstein.w.n on Jan 31 2023, 1:57 PM.

Details

Summary

We can handle the following cases + some nsw/nuw flags:

(srem (mul X, Y), (mul X, Z))

[If `srem(Y, Z) == 0`]
    -> 0
        - https://alive2.llvm.org/ce/z/PW4XZ-
[If `srem(Y, Z) == Y`]
    -> `(mul nuw nsw X, Y)`
        - https://alive2.llvm.org/ce/z/DQe9Ek
    -> `(mul nsw X, Y)`
        - https://alive2.llvm.org/ce/z/Nr_MdH

[If `Y`/`Z` are constant]
    -> `(mul/shl nuw nsw X, (srem Y, Z))`
        - https://alive2.llvm.org/ce/z/ccTFj2
        - https://alive2.llvm.org/ce/z/i_UQ5A
    -> `(mul/shl nsw X, (srem Y, Z))`
        - https://alive2.llvm.org/ce/z/mQKc63
        - https://alive2.llvm.org/ce/z/uERkKH

(urem (mul X, Y), (mul X, Z))

[If `urem(Y, Z) == 0`]
    -> 0
        - https://alive2.llvm.org/ce/z/LL7UVR
[If `srem(Y, Z) == Y`]
    -> `(mul nuw nsw X, Y)`
        - https://alive2.llvm.org/ce/z/9Kgs_i
    -> `(mul nuw X, Y)`
        - https://alive2.llvm.org/ce/z/ow9i8u

[If `Y`/`Z` are constant]
    -> `(mul nuw nsw X, (srem Y, Z))`
        - https://alive2.llvm.org/ce/z/mNnQqJ
        - https://alive2.llvm.org/ce/z/Bj_DR-
        - https://alive2.llvm.org/ce/z/X6ZEtQ
    -> `(mul nuw X, (srem Y, Z))`
        - https://alive2.llvm.org/ce/z/SJYtUV

The rationale for doing this all in InstCombine rather than handling
the constant mul cases in InstSimplify is we often create a new
instruction because we are able to deduce more nsw/nuw flags than
the original instruction had.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
goldstein.w.n edited the summary of this revision. (Show Details)Feb 9 2023, 9:14 AM

Fix some nits + vscale tests

I think not implementing several of my suggestions because of a future patch is a mistake. I don't think they're nits and have some obvious benefits for readability and control flow, and I'm of the opinion that leaving code that anticipates future work that may or may not even land or be reverted is not ideal, so I'll leave this for someone else to approve.

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1738

nit: If you don't use auto to hide away small details like this for short lived variables then I don't see much reason to use it at all. If you combine the below block into match statements the fact that these are pointers becomes an unimportant detail.

I think not implementing several of my suggestions because of a future patch is a mistake. I don't think they're nits and have some obvious benefits for readability and control flow, and I'm of the opinion that leaving code that anticipates future work that may or may not even land or be reverted is not ideal, so I'll leave this for someone else to approve.

Sorry, missed this earlier, just seeing now.

If you insist, will update accordingly. Think this version has all your concerns addressed.

Rebase + fix nits

Rebase + fix nits (wrong patch last time)

goldstein.w.n marked an inline comment as done.Feb 13 2023, 7:42 PM
goldstein.w.n marked 3 inline comments as done.
goldstein.w.n added inline comments.Feb 13 2023, 7:48 PM
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1742–1755

We can do

ConstantInt *ConstY, *ConstZ;
Constant *CY, *CZ;
if (!I.getType()->isVectorTy() || !match(Y, m_Constant(CY)) ||
    !match(CY->getSplatValue(), m_ConstantInt(ConstY)) ||
    !match(Z, m_Constant(CZ)) ||
    !match(CZ->getSplatValue(), m_ConstantInt(ConstZ)))
  if (!match(Y, m_ConstantInt(ConstY)) || !match(Z, m_ConstantInt(ConstZ)))
    return nullptr;

Irreverent of keeping aligned with the generic patch, I find that logic much harder to follow. There are alot of conditions and non-intuitive short-circuit requirements.

Which saves us a few lines, and this also lets us remove the later check for

if (!ConstY || !ConstZ)
  return nullptr;
MattDevereau accepted this revision.Feb 15 2023, 3:12 AM
This revision is now accepted and ready to land.Feb 15 2023, 3:12 AM

@MattDevereau thanks for completing the review, sorry about the friction earlier.

Any chance you can also review the generic impl: D143417

sdesmalen requested changes to this revision.Feb 16 2023, 8:31 AM

Hi @goldstein.w.n, I'm still going through the patch but already found that some code paths are currently untested. I am requesting changes to avoid you from landing it.
In general my preference would be to limit the cases your code handles, rather than adding more tests for more possible combinations of shifts/muls. That makes the code-changes easier to review and helps identify the test-coverage for the different code-paths you've added.

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1712–1713

Is that true? shl is not commutative, i.e. (a * b) == (b * a), but (a << b) != (b << a)

Also, this patch is already quite complicated, I would prefer to keep it simple at first and only match: urem/srem (mul/shl X, Y), (mul/shl X, Z)
where 'X' is matched with m_Specific. Then later patches can maybe relax those conditions further.

1714

When I comment this part of the condition out, all tests still pass.

1718

When I comment this part of the condition out, all tests still pass.

1718

When I comment this part of the condition out, all tests still pass

1733–1735

When I comment this code out, all tests still pass.

Can this case ever happen? (I would have expected InstCombine/InstSimplify to have folded that case away already)

This revision now requires changes to proceed.Feb 16 2023, 8:31 AM
sdesmalen added inline comments.Feb 16 2023, 9:21 AM
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1724–1727

These can be cast<BinaryOperator> instead, since we know (from the match above) that they're either Mul or Shl, so they must be BinaryOperator's.

1737–1750

nit: You can write this a bit shorter like this:

ConstantInt *ConstY = nullptr, *ConstZ = nullptr;
if (I.getType()->isVectorTy()) {
  if (auto *CY = dyn_cast<Constant>(Y))
    ConstY = dyn_cast<ConstantInt>(CY->getSplatValue());
  if (auto *CZ = dyn_cast<Constant>(Z))
    ConstZ = dyn_cast<ConstantInt>(CZ->getSplatValue());
} else {
  ConstY = dyn_cast<ConstantInt>(Y);
  ConstZ = dyn_cast<ConstantInt>(Z);
}

Split of shift code + fix some nits

goldstein.w.n retitled this revision from [InstCombine] Add combines for `(urem/srem (mul/shl X, Y), (mul/shl X, Z))` to Add constant combines for `(urem/srem (mul X, Y), (mul X, Z))`.
goldstein.w.n edited the summary of this revision. (Show Details)
goldstein.w.n marked 2 inline comments as done.Feb 16 2023, 3:38 PM
goldstein.w.n added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1712–1713

Is that true? shl is not commutative, i.e. (a * b) == (b * a), but (a << b) != (b << a)

You are right. Made this patch only cover mul so its a non-issue here, but the shl patch (see D144225) cover it.

Also, this patch is already quite complicated, I would prefer to keep it simple at first and only match: urem/srem (mul/shl X, Y), (mul/shl X, Z)
where 'X' is matched with m_Specific. Then later patches can maybe relax those conditions further.

I tried doing this, but found it significantly more complicated because the m_Specific logic for both lhs/rhs as well as special cases for shl paired with mul. To try and simplify I spit off the shl patch (so hopefully easier to review). If you insist, however, it is implementable to match + m_Specific so LMK.

1718

When I comment this part of the condition out, all tests still pass

Added more tests that require this logic.

1718

When I comment this part of the condition out, all tests still pass.

Removed from this patch.

1733–1735

When I comment this code out, all tests still pass.

Can this case ever happen? (I would have expected InstCombine/InstSimplify to have folded that case away already)

Removed the BO0/BO1 checks, but !X can happen.

1737–1750

nit: You can write this a bit shorter like this:

ConstantInt *ConstY = nullptr, *ConstZ = nullptr;
if (I.getType()->isVectorTy()) {
  if (auto *CY = dyn_cast<Constant>(Y))
    ConstY = dyn_cast<ConstantInt>(CY->getSplatValue());
  if (auto *CZ = dyn_cast<Constant>(Z))
    ConstZ = dyn_cast<ConstantInt>(CZ->getSplatValue());
} else {
  ConstY = dyn_cast<ConstantInt>(Y);
  ConstZ = dyn_cast<ConstantInt>(Z);
}

Made it a lambda function.

goldstein.w.n marked an inline comment as done.Feb 16 2023, 3:38 PM
goldstein.w.n marked an inline comment as not done.
goldstein.w.n added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1714

When I comment this part of the condition out, all tests still pass.

Added additional tests.

Thanks for simplifying this patch a bit!

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1712–1713

To use m_Specific you can do the following:

Value *X = nullptr, *Y = nullptr, *Z = nullptr;
if (!match(Op0, m_Mul(m_Value(X), m_Value(Y))) &&
    !match(Op0, m_Shl(m_Value(X), m_Value(Y))))
  return nullptr;
if (!match(Op1, m_Mul(m_Specific(X), m_Value(Z))) &&
    !match(Op1, m_Shl(m_Specific(X), m_Value(Z))))
  return nullptr;

I prefer this explicit matching over trying assign X, Y and Z from A, B, C and D, since that logic tries to cover various different combinations and is harder to follow. Note that the version I wrote above also allows for the case where Y and Z are a Shl.

1726

No variables really need to be captured for this function. You can also write it more compactly as:

if (Op->getType()->isVectorTy())
  if (auto *COp = dyn_cast<Constant>(Op))
    return dyn_cast<ConstantInt>(COp->getSplatValue());
return dyn_cast<ConstantInt>(Op);
goldstein.w.n added inline comments.Feb 20 2023, 11:30 AM
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1712–1713

To use m_Specific you can do the following:

Value *X = nullptr, *Y = nullptr, *Z = nullptr;
if (!match(Op0, m_Mul(m_Value(X), m_Value(Y))) &&
    !match(Op0, m_Shl(m_Value(X), m_Value(Y))))
  return nullptr;
if (!match(Op1, m_Mul(m_Specific(X), m_Value(Z))) &&
    !match(Op1, m_Shl(m_Specific(X), m_Value(Z))))
  return nullptr;

This doesn't quite work. It misses things like:

%a = mul i8 %Y, %X
%b = mul i8 %X, %Z

To do (just mul) with match it needs to be:

if ((match(Op0, m_Mul(m_Value(X), m_Value(Z))) &&
     match(Op1, m_c_Mul(m_Specific(X), m_Value(Y)))) ||
    (match(Op0, m_Mul(m_Value(Z), m_Value(X))) &&
     match(Op1, m_c_Mul(m_Specific(X), m_Value(Y)))))

To get shl will be 3x more of these (shl/mul, mul/shl, shl/shl).

I prefer this explicit matching over trying assign X, Y and Z from A, B, C and D, since that logic tries to cover various different combinations and is harder to follow. Note that the version I wrote above also allows for the case where Y and Z are a Shl.

Okay. Will change to use match.

goldstein.w.n added inline comments.Feb 20 2023, 12:17 PM
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1726

No variables really need to be captured for this function. You can also write it more compactly as:

if (Op->getType()->isVectorTy())
  if (auto *COp = dyn_cast<Constant>(Op))
    return dyn_cast<ConstantInt>(COp->getSplatValue());
return dyn_cast<ConstantInt>(Op);

That doesn't work. If vec is a non-splat constant it will fault from dyn_cast<ConstantInt>(nullptr).

But it can be:

if (Op->getType()->isVectorTy())
  if (auto *COp = dyn_cast<Constant>(Op)) {
    auto *CSplat = COp->getSplatValue();
    return CSplat ? dyn_cast<ConstantInt>(CSplat) : nullptr;
  }
return dyn_cast<ConstantInt>(Op);
goldstein.w.n marked an inline comment as done.Feb 20 2023, 12:17 PM

Use match instead of handwritten logic

goldstein.w.n added inline comments.Feb 20 2023, 12:20 PM
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1712–1713

To use m_Specific you can do the following:

Value *X = nullptr, *Y = nullptr, *Z = nullptr;
if (!match(Op0, m_Mul(m_Value(X), m_Value(Y))) &&
    !match(Op0, m_Shl(m_Value(X), m_Value(Y))))
  return nullptr;
if (!match(Op1, m_Mul(m_Specific(X), m_Value(Z))) &&
    !match(Op1, m_Shl(m_Specific(X), m_Value(Z))))
  return nullptr;

I prefer this explicit matching over trying assign X, Y and Z from A, B, C and D, since that logic tries to cover various different combinations and is harder to follow. Note that the version I wrote above also allows for the case where Y and Z are a Shl.

No changes to results in the mul case, but this improves the codegen for the generic mul/shl case as the handwritten logic was just glossing over some handleable cases :)

See D144225 for all the match logic.

nikic added inline comments.Feb 20 2023, 1:29 PM
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1721

Why doesn't this use match(Y, m_APInt(APIntY)) etc? As far as I can tell you don't use the ConstantInt itself, and m_APInt already handles splats.

1732

BinaryOperator -> OverflowingBinaryOperator to avoid constant expression crash.

goldstein.w.n added inline comments.Feb 20 2023, 1:56 PM
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1721

Why doesn't this use match(Y, m_APInt(APIntY)) etc? As far as I can tell you don't use the ConstantInt itself, and m_APInt already handles splats.

That would work for this patch (can update if thats preference), but last in the series (D143417) generalizes this to non-constants so would have to return to this code either way.

goldstein.w.n marked an inline comment as done.Feb 20 2023, 2:06 PM

BinaryOperator -> OverflowingBinaryOperator

goldstein.w.n marked 9 inline comments as done.Mon, Feb 27, 10:30 AM
sdesmalen added inline comments.Tue, Feb 28, 3:46 AM
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1721

Since we're reviewing this patch, and not D143417, I would prefer you to use m_APInt here. D143417 can change it back if that's what it needs to do.

1723

nit: Please move this closer to its use. Also, is it worth calling it IsSigned?

1738

There is an implied condition that if RemYZ = 0, then Y >= Z, consequently mul X, Z cannot overflow if mul X, Y cannot overflow.

I think the code would be easier to follow if you do something like this:

bool LHSNoWrap = IsSRem ? BO0HasNSW : BO0HasNUW;
bool RHSNoWrap = IsSRem ? BO1HasNSW : BO1HasNUW;
if (Y >= Z && LHSNoWrap) {
  // Handle case for RemYZ == 0 and Y >= Z
} else if (Y < Z && RHSNoWrap) {
  // Handle case for RemYZ == Y
}
1761

if Y >= Z and mul X, Y doesn't overflow, then mul X, Z also can't overflow, so the test for B01HasNSW can be removed?

1767–1769

nit: It is easier to write:

BO->setHasNoSignedWrap(BO0HasNSW);
BO->setHasNoUnsignedWrap(BO0HasNUW);
goldstein.w.n marked 2 inline comments as done.Fri, Mar 3, 1:18 PM

Sorry for the delay, didn't see your replies till just now :(

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1721

DOne, likewise for the shift patch.

1723

nit: Please move this closer to its use. Also, is it worth calling it IsSigned?

Moved closer, it was original IsSigned but matt asked for change to IsSRem. Personally I'm agnostic.

1738

There is an implied condition that if RemYZ = 0, then Y >= Z, consequently mul X, Z cannot overflow if mul X, Y cannot overflow.

the Y >= Z -> implied flags doesn't seem to verify in all cases i.e:
https://alive2.llvm.org/ce/z/bc8BXG
vs
https://alive2.llvm.org/ce/z/uERkKH

or
https://alive2.llvm.org/ce/z/BUuMfn
vs
https://alive2.llvm.org/ce/z/X6ZEtQ

I don't doubt that there may be more cases we can add, but would prefer to leave that as a todo.

I think the code would be easier to follow if you do something like this:

bool LHSNoWrap = IsSRem ? BO0HasNSW : BO0HasNUW;
bool RHSNoWrap = IsSRem ? BO1HasNSW : BO1HasNUW;
if (Y >= Z && LHSNoWrap) {
  // Handle case for RemYZ == 0 and Y >= Z
} else if (Y < Z && RHSNoWrap) {
  // Handle case for RemYZ == Y
}

Done.

1761

if Y >= Z and mul X, Y doesn't overflow, then mul X, Z also can't overflow, so the test for B01HasNSW can be removed?

Doesn't verify: https://alive2.llvm.org/ce/z/_yqMCk

goldstein.w.n marked an inline comment as done.

Fix many a nit

sdesmalen accepted this revision.Fri, Mar 10, 5:36 AM
sdesmalen added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1738

That makes sense, my thinking here was guided by the unsigned case.

1739–1742

nit:

BO->setHasNoSignedWrap(IsSRem || BO0HasNSW);
BO->setHasNoUnsignedWrap(!IsSRem || BO0HasNUW);
This revision is now accepted and ready to land.Fri, Mar 10, 5:36 AM
goldstein.w.n marked 2 inline comments as done.Mon, Mar 13, 12:10 AM
goldstein.w.n added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
1739–1742

Fixed, any chance you can also checkout D143417 and D144225?

I'm happy to look at one of the other patches. Can you land this patch in the meantime?

This revision was landed with ongoing or failed builds.Thu, Mar 16, 11:02 AM
This revision was automatically updated to reflect the committed changes.
goldstein.w.n marked an inline comment as done.