This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Simplify Add with remainder expressions as operands.
ClosedPublic

Authored by bixia on Apr 23 2018, 11:16 AM.

Details

Summary

Simplify integer add expression X % C0 + (( X / C0 ) % C1) * C0 to
X % (C0 * C1). This is a common pattern seen in code generated by the XLA
GPU backend.

Add test cases for this new optimization.

Diff Detail

Repository
rL LLVM

Event Timeline

bixia created this revision.Apr 23 2018, 11:16 AM
bixia edited the summary of this revision. (Show Details)Apr 23 2018, 11:21 AM
lebedev.ri added inline comments.
lib/Transforms/InstCombine/InstCombineAddSub.cpp
1047 ↗(On Diff #143604)

m_c_Mul()
And please make sure that there is a test for both combinations.

1065 ↗(On Diff #143604)

The formatting looks off, maybe use clang-format on the diff (you could use a git post-commit hook)

1103 ↗(On Diff #143604)

You take address of MulOpv, and then immediately deference it in match_rem().
Maybe pass it by reference (Value *&Op)

1229 ↗(On Diff #143604)

Here and everywhere - no need for {} in such one-line cases.

test/Transforms/InstCombine/add4.ll
1 ↗(On Diff #143604)

Please use llvm/utils/update_test_checks.py, and ideally split the initial tests (with the output as of trunk) into parent differential, rebase this differential ontop of that one, so the changes are more clear.

craig.topper added inline comments.
lib/Transforms/InstCombine/InstCombineAddSub.cpp
1059 ↗(On Diff #143604)

signess->signedness

1062 ↗(On Diff #143604)

Can you pass Op as Value *&Op?

1069 ↗(On Diff #143604)

If you use dyn_cast, you need to check the result isn't null. If it can never fail use 'cast'

1085 ↗(On Diff #143604)

What guarantees the ConstantInt only uses 64 bits or less?

1114 ↗(On Diff #143604)

&& should be at the end of the previous line. If they won't fit, bring "X == DivOpv" down. Or just clang-format thsi.

1122 ↗(On Diff #143604)

Unchecked dyn_cast

1123 ↗(On Diff #143604)

The IR builder will never give you back an existing instruction. The only optimization it can do is to constant fold, but that wouldn't castable to an Instruction.

sanjoy requested changes to this revision.Apr 23 2018, 11:49 AM

Some style nits -- will review the content of the patch once these are fixed. You might want to skim through these: https://llvm.org/docs/CodingStandards.html http://llvm.org/docs/ProgrammersManual.html

lib/Transforms/InstCombine/InstCombineAddSub.cpp
1047 ↗(On Diff #143604)

I'm not sure if m_c_Mul is necessary here -- we should be canonicalizing multiplications such that the constant operand, if there is any, is always the RHS.

1052 ↗(On Diff #143604)

getZExtValue will crash if the constant does not fit in 64 bits. It is probably better to keep constants as APInt throughout.

sanjoy added inline comments.Apr 23 2018, 11:49 AM
lib/Transforms/InstCombine/InstCombineAddSub.cpp
1045 ↗(On Diff #143604)

LLVM naming style is CamelCase so this should be MatchMul.

1066 ↗(On Diff #143604)

Use m_Power2.

1069 ↗(On Diff #143604)

dyn_cast<T>(V)->foo() is never necessary. If V is always of type T then use cast<> not dyn_cast<>. If V may not be of type T then dyn_cast<> may return nullptr and cause UB (so you need to check the value returned by dyn_cast<>).

More details at http://llvm.org/docs/ProgrammersManual.html#the-isa-cast-and-dyn-cast-templates

1108 ↗(On Diff #143604)

IsSigned_2 needs a more descriptive name.

This revision now requires changes to proceed.Apr 23 2018, 11:49 AM

I'm not sure I see anything that ensures C1*C2 doesn't overflow. And in particular if C1*C2 overflows and produces 0, the resulting remainder instruction is UB.

bixia updated this revision to Diff 143772.Apr 24 2018, 9:32 AM
bixia marked 14 inline comments as done.
  • Use instnamer to fix names.
bixia added inline comments.Apr 24 2018, 9:33 AM
lib/Transforms/InstCombine/InstCombineAddSub.cpp
1047 ↗(On Diff #143604)

I removed one of the two m_Mul assuming that the operation is canonicalized.

1085 ↗(On Diff #143604)

Changed to use APInt instead.

bixia updated this revision to Diff 143773.Apr 24 2018, 9:37 AM
  • Use instnamer to fix names.
bixia updated this revision to Diff 143790.Apr 24 2018, 11:42 AM
  • Use prefix ++ instead of postfix ++.
sanjoy requested changes to this revision.Apr 24 2018, 12:02 PM

Mostly nits except for the comment with the Alive proofs (didn't get to the meat of the patch yet).

lib/Transforms/InstCombine/InstCombineAddSub.cpp
1035 ↗(On Diff #143773)

Are these correct interpretations of this transform:

https://rise4fun.com/Alive/j4G (signed)
https://rise4fun.com/Alive/RQB (unsigned)

? If so, Alive seems to think they're incorrect.

1037 ↗(On Diff #143773)

Can this condition ever be false? You're calling this only from visitAdd right?

1045 ↗(On Diff #143773)

Use m_APInt instead of manually calling CI->getValue().

1049 ↗(On Diff #143773)

Is this lifetime of this APInt correct? Won't it go out of scope once MatchMul returns?

1064 ↗(On Diff #143773)

Use m_APInt here too.

1070 ↗(On Diff #143773)

Braces around Opcode == Instruction::SRem are not necessary.

1087 ↗(On Diff #143773)

Probably better to do this as a separate change, but it might be nice to push all of this logic (division as udiv or as an lshr) into a matcher.

1098 ↗(On Diff #143773)

LLVM style would be MulOpV and MulOpC, but you can also say MulLHS and MulRHS -- you can tell which is constant and which isn't by the C++ type.

1101 ↗(On Diff #143773)

I don't think you need the ( around the call to MatchRem.

1101 ↗(On Diff #143773)

I think this sort of thing will be more readable if you give examples of what you're matching using the C++ names right before the if:

// Match I = (X  % C0) + (MulOpv * MulOpc)

etc.

1107 ↗(On Diff #143773)

Same here:

// Match MulOpv = RemOpv % C1

though here the benefit is less because the code is simpler.

1120 ↗(On Diff #143773)

Can just be replaceInstUsesWith(I, cast<Instruction>(NewVal)). However, please state why NewVal can not be a constant.

This revision now requires changes to proceed.Apr 24 2018, 12:02 PM

Fixed Alive proof for the signed case: https://rise4fun.com/Alive/zJr

Granted, I'm pretty sure this patch doesn't check the precondition correctly.

bixia updated this revision to Diff 143819.Apr 24 2018, 3:10 PM
bixia marked 14 inline comments as done.
  • Use prefix ++ instead of postfix ++.
bixia added inline comments.Apr 24 2018, 3:32 PM
lib/Transforms/InstCombine/InstCombineAddSub.cpp
1035 ↗(On Diff #143773)

Added check to make sure C0*C1 does not overflow.

1037 ↗(On Diff #143773)

Removed.

1049 ↗(On Diff #143773)

The temp constructed by APInt(...) is copied to C.

1120 ↗(On Diff #143773)

I put a comment that says NewVal can't be a constant because I is not a constant.

bixia updated this revision to Diff 143833.Apr 24 2018, 4:20 PM
  • Applied git clang-format.
sanjoy requested changes to this revision.Apr 25 2018, 9:50 AM
sanjoy added inline comments.
lib/Transforms/InstCombine/InstCombineAddSub.cpp
1035 ↗(On Diff #143833)

s/(C0) * C1)/(C0 * C1)/

1041 ↗(On Diff #143833)

We're not getting much leverage from making these lambdas -- how about making them static helper functions? That'll reduce the indentation and make SimplifyAddWithRemainder a bit smaller.

1042 ↗(On Diff #143833)

Let's call this something other than CI since CI usually means ConstantInt.

Same comment applies below.

1062 ↗(On Diff #143833)

Instead of (*CI + 1).isPowerOf2() you can do CI->isAllOnesValue() to avoid the addition and also read a bit cleaner.

1081 ↗(On Diff #143833)

Can this match a ConstantExpr (which isn't an Instruction and will fail the cast<> below)? Or have we checked before that E is an Instruction?

1095 ↗(On Diff #143833)

Let's call this MulWillOverflow.

1108 ↗(On Diff #143833)

Since you're checking this anyway, how about:

// Match I = X % C0 + MulOpV * C0
1114 ↗(On Diff #143833)

LLVM style will be Rem2IsSigned or InnerRemIsSigned (since 2 isn't very discriminating).

1115 ↗(On Diff #143833)

Should be MulOpV in the comment.

1120 ↗(On Diff #143833)

Instead of commenting RemOpV = DivOpV / DivOpC how about commenting RemOpV = X / C0?

1123 ↗(On Diff #143833)

How about s/C0_C1/NewDivisor ? Generally LLVM coding style does not allow underscores in variable names.

1130 ↗(On Diff #143833)

The cast<> to Instruction is probably not necessary -- replaceInstUsesWith takes a Value as its second argument.

1231 ↗(On Diff #143833)

LLVM style avoids braces around single line statements like this.

1232 ↗(On Diff #143833)

Might be worth being consistent with the previous clause where replaceInstUsesWith is called here, not in the callee.

lib/Transforms/InstCombine/InstCombineInternal.h
629 ↗(On Diff #143833)

No need for \brief in new doxygen comments -- we now build the docs with autobrief which means the first sentence is automatically considered \brief.

test/Transforms/InstCombine/add4.ll
92 ↗(On Diff #143833)

You should probably add a test case with where the add does not have nuw or nsw, just to show that these flags are not necessary.

This revision now requires changes to proceed.Apr 25 2018, 9:50 AM
bixia updated this revision to Diff 143972.Apr 25 2018, 11:21 AM
  • Remove nuw nsw from the tests.
bixia added inline comments.Apr 25 2018, 11:23 AM
test/Transforms/InstCombine/add4.ll
92 ↗(On Diff #143833)

Removed nuw nsw from the tests.

bixia updated this revision to Diff 143983.Apr 25 2018, 12:03 PM
  • Removed nuw nsw from the tests.
  • Removed \brief from the comment.
bixia updated this revision to Diff 143994.Apr 25 2018, 1:27 PM
bixia marked 12 inline comments as done.
  • Removed nuw nsw from the tests.
bixia updated this revision to Diff 144012.Apr 25 2018, 2:44 PM
bixia marked 11 inline comments as done.
  • Removed nuw nsw from the tests.
bixia updated this revision to Diff 144013.Apr 25 2018, 2:47 PM
bixia marked 2 inline comments as done.
  • Removed nuw nsw from the tests.
bixia added inline comments.Apr 25 2018, 2:48 PM
lib/Transforms/InstCombine/InstCombineAddSub.cpp
1062 ↗(On Diff #143833)

the two are not equivalent.

1081 ↗(On Diff #143833)

Remove the use of the cast.

1087 ↗(On Diff #143773)

Will consider doing this in another change.

sanjoy accepted this revision.Apr 26 2018, 12:38 PM

lgtm with minor nits.

lib/Transforms/InstCombine/InstCombineAddSub.cpp
1043 ↗(On Diff #144013)

This is optional, but in these cases I find it easier to avoid the else and write it as:

if (match(E, m_Mul(m_Value(Op), m_APInt(AI)))) {
  C = *AI;
  return true;
}

if (match(E, m_Shl(m_Value(Op), m_APInt(AI)))) {
  C = APInt(AI->getBitWidth(), 1);
  C <<= *AI;
  return true;
}

Same below.

1126 ↗(On Diff #144013)

LLVM style discourages underscores in variable names.

1128 ↗(On Diff #144013)

Minor, but a ternary operation may be more readable here.

1233 ↗(On Diff #144013)

LLVM style says no braces for single line statements.

This revision is now accepted and ready to land.Apr 26 2018, 12:38 PM
bixia updated this revision to Diff 144186.Apr 26 2018, 1:28 PM
bixia marked 7 inline comments as done.
  • Removed nuw nsw from the tests.
This revision was automatically updated to reflect the committed changes.