[InstCombine] Add constant combines for `(urem/srem (shl X, Y), (shl X, Z))`

[goldstein.w.n]

Summary

Forked from D142901 to deduce more nsw/nuw flag for the output
shl.

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

The rationale for doing this all in InstCombine rather than handling
the constant shl 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]

Use match instead of handwritten logic

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[sdesmalen]

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

1707

It might be a bit easier to follow, if you explicitly do the scaling while doing the matching, i.e.

APInt Y, Z;
const APInt *MatchY = nullptr, *MatchZ = nullptr;

// Match and normalise shift-amounts to multiplications
if (match(Op0, m_c_Mul(m_Value(X), m_APInt(MatchY)))) {
  Y = *MatchY;
  if (match(Op1, m_Shl(m_Specific(X), m_APInt(MatchZ))))
    //  rem(mul(x, y), shl(x, z))
    Z = APInt(X->getType()->getScalarSizeInBits(), 1).shl(*MatchZ);
  else if (match(Op1, m_c_Mul(m_Specific(X), m_APInt(MatchZ))))
    //  rem(mul(x, y), mul(x, z))
    Z = *MatchZ;
} else if (match(Op0, m_Shl(m_Value(X), m_APInt(MatchY)))) {
  Y = APInt(X->getType()->getScalarSizeInBits(), 1).shl(*MatchY);
  if (match(Op1, m_Shl(m_Specific(X), m_APInt(MatchZ))))
    //  rem(shl(x, y), shl(x, z))
    Z = APInt(X->getType()->getScalarSizeInBits(), 1).shl(*MatchZ);
  else if (match(Op1, m_c_Mul(m_Specific(X), m_APInt(MatchZ))))
    //  rem(shl(x, y), mul(x, z))
    Z = *MatchZ;
}

if (!MatchY || !MatchZ)
  return nullptr;

1722–1724

I can't see this case being tested anywhere. I'd suggest singling this case out from the other logic and handling it separately. Maybe you can move that to another patch (or make it part of D143417, which tries to handle a similar case). That makes this patch a bit simpler and avoids the need for GetBinOpOut.