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

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

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

1065

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

1103

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

1231

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

test/Transforms/InstCombine/add4.ll
1

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

signess->signedness

1062

Can you pass Op as Value *&Op?

1069

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

1085

What guarantees the ConstantInt only uses 64 bits or less?

1114

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

1122

Unchecked dyn_cast

1123

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

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

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

LLVM naming style is CamelCase so this should be MatchMul.

1066

Use m_Power2.

1069

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

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

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

1085

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

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

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

1045

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

1049

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

1064

Use m_APInt here too.

1070

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

1087

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

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

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

1101

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

Same here:

// Match MulOpv = RemOpv % C1

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

1120

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

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

1037

Removed.

1049

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

1120

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

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

1041

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

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

Same comment applies below.

1062

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

1081

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

Let's call this MulWillOverflow.

1108

Since you're checking this anyway, how about:

// Match I = X % C0 + MulOpV * C0
1114

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

1115

Should be MulOpV in the comment.

1120

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

1123

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

1130

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

1231

LLVM style avoids braces around single line statements like this.

1232

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

lib/Transforms/InstCombine/InstCombineInternal.h
629

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

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

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

the two are not equivalent.

1081

Remove the use of the cast.

1087

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

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

LLVM style discourages underscores in variable names.

1128

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

1231

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.