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

[goldstein.w.n]

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.

[goldstein.w.n]

Fix some nits + vscale tests

[MattDevereau]

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.

[goldstein.w.n]

In D143014#4115845, @MattDevereau wrote:

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.

[goldstein.w.n]

Rebase + fix nits

[goldstein.w.n]

Rebase + fix nits (wrong patch last time)

[goldstein.w.n]

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;

[goldstein.w.n]

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

Any chance you can also review the generic impl: D143417

[sdesmalen]

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)

[sdesmalen]

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);
}

[goldstein.w.n]

Split of shift code + fix some nits

[goldstein.w.n]

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]

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

1714

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

Added additional tests.

[sdesmalen]

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]

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]

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]

Use match instead of handwritten logic

[goldstein.w.n]

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]

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]

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]

BinaryOperator -> OverflowingBinaryOperator

[goldstein.w.n]

@sdesmalen ping.

[sdesmalen]

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]

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]

Fix many a nit

[sdesmalen]

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);

[goldstein.w.n]

Fix nits

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

1739–1742

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

[sdesmalen]

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