This is an archive of the discontinued LLVM Phabricator instance.

[InstSimplify] Simplify UREM and SREM left shifted operands

Authored by MattDevereau on Jan 30 2023, 8:24 AM.



If both operands of a rem instruction are left shifts of the same value, this can be simplified to 0 or the first operand

Diff Detail

Event Timeline

MattDevereau created this revision.Jan 30 2023, 8:24 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 30 2023, 8:24 AM
MattDevereau requested review of this revision.Jan 30 2023, 8:24 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 30 2023, 8:24 AM

Nice improvement @MattDevereau! I just had a few minor comments ...


Perhaps you can create a temp variable here to reuse the logic, i.e.

bool NoWrap = (IsSigned && Q.IIQ.hasNoSignedWrap(Shift)) ||
  (!IsSigned && Q.IIQ.hasNoUnsignedWrap(Shift));
if (S1 >= S2 && NoWrap)
  return Constant::getNullValue(Shift->getType());

if (NoWrap)
  return Op0;

Could you leave comments on the negative tests explaining why they fail? If it makes it easier you could put all the negative tests together?


Is it worth having a negative test for srem with nuw shifts as well? We shouldn't do any simplification in that case either.

MattDevereau added inline comments.Jan 30 2023, 9:13 AM

I'm not sure this suggestion is correct, they key thing here being Shift = cast<OverflowingBinaryOperator>(Op1); on line 1010 which changes Shift to be a cast of Op1 instead of Op0 on which the nsw/nuw flags are checked, which is because the larger shift value needs its flags checking. If we went ahead with this, in this example ( NoWrap would evaluate to true while the transform is not viable.


Sure thing, should be simple enough


I personally think the current tests are ok since we have one test for nsw which is testing the presence of nsw, and one which tests for it's absence and other flags aren't particularly relevant. These tests are quite compact though so I suppose there's no harm in adding extra cases.

goldstein.w.n added inline comments.

Instead of a new helper maybe this should be in simplifyRem which already appears to have:

// (X << Y) % X -> 0
if (Q.IIQ.UseInstrInfo &&
    ((Opcode == Instruction::SRem &&
      match(Op0, m_NSWShl(m_Specific(Op1), m_Value()))) ||
     (Opcode == Instruction::URem &&
      match(Op0, m_NUWShl(m_Specific(Op1), m_Value())))))
  return Constant::getNullValue(Op0->getType());

This is really just a superset of that case, so maybe expanding the existing logic would be simpler?

goldstein.w.n added inline comments.Jan 30 2023, 10:35 AM

Maybe add a TODO for the more generalized case of (rem (mul nsw/nuw X, C1), (mul nsw/nuw X, C2) if C1 % C2 == 0 -> 0 We seem to be missing it:

david-arm added inline comments.Jan 31 2023, 1:17 AM

Sure, I was just thinking that specifically we don't want to perform the simplification for any of nsw or nuw. They both mark the instruction as not wrapping, but only the signed version applies here. It's just because your logic accepts both nsw and nuw flags as valid, but *only if* the signedness matches the instruction. I was hoping to defend against someone accidentally rewriting your code in future and losing the signedness checks.

Inlined unnecessary helper function
Added comments to negative tests
Added more incorrect flag tests

MattDevereau marked 3 inline comments as done.Jan 31 2023, 3:38 AM
MattDevereau added inline comments.

I've inlined it into simplifyRem which I think looks a lot neater now. Thank you for the feedback.


I've added negative tests for urem with nsw and srem with nuw now.

MattDevereau planned changes to this revision.Feb 2 2023, 1:30 AM
MattDevereau marked an inline comment as done.

Note that this patch will likely be dropped in favour of

MattDevereau abandoned this revision.Mar 14 2023, 3:06 AM