This is an archive of the discontinued LLVM Phabricator instance.

[InstructionSimplify] icmp simplification
ClosedPublic

Authored by SjoerdMeijer on Oct 13 2020, 6:56 AM.

Details

Summary

This improves simplifications for pattern icmp (X+Y), (X+Z) -> icmp Y,Z if only one of the operands has NSW set, e.g.:

icmp slt (x + 5), (x +nsw 6)

We can still safely rewrite this to:

icmp slt 5, 6

because we know that the LHS can't overflow if the RHS has NSW set and constant Y <= Z.

This is useful because ScalarEvolutionExpander which is used to generate code for SCEVs in different loop optimisers is not always able to put back NSW flags across control-flow.

Diff Detail

Event Timeline

SjoerdMeijer created this revision.Oct 13 2020, 6:56 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 13 2020, 6:56 AM
SjoerdMeijer requested review of this revision.Oct 13 2020, 6:56 AM
lebedev.ri added inline comments.Oct 13 2020, 7:05 AM
llvm/lib/Analysis/InstructionSimplify.cpp
2882

Please compare APInt's themselves, otherwise this will crash with an assertion for e.g. i65.

llvm/test/Transforms/InstSimplify/compare.ll
1766

Please precommit the tests.

1828

At least this one is already folded away by instcombine,
so likely there's some code to be moved/refactored/shared.
https://godbolt.org/z/Yo3d6h

Thanks for reviewing.

  • I have precommitted the tests in rG66f22411e1bb, and
  • use APInts in the comparisons.
SjoerdMeijer added inline comments.Oct 13 2020, 8:17 AM
llvm/test/Transforms/InstSimplify/compare.ll
1828

Yeah, I will look as a follow up. There is some interaction with other passes. I.e., for my motivating code example, this change enables the unroller to fully unroll these type of loops (i.e. loops with an imcp x+y, x+z condition), and then SimplifyCFG can get rid of control-flow. Thus, I need to look if there's overlap and how the passes interact, also with instcombine.

uenoku added a subscriber: uenoku.Oct 14 2020, 3:46 PM

This seems to be missing some other preconditions on the constant values:
https://rise4fun.com/Alive/EvB

This seems to be missing some other preconditions on the constant values:
https://rise4fun.com/Alive/EvB

Ah yes! Thanks for checking. It's an off-by-one error, and we need positive constants, so should be: Pre: C1 < C2 && C1 >= 0. Will fix this.

Fixed precondition, and added a test case for that.

  1. Please upload with context: https://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface
  2. There should be at least 4 positive tests to exercise each of the commuted pattern paths. Vary the types (include a vector test) for more coverage/functionality. Do we have negative tests for when nsw is on the wrong add or the predicate is not slt?
  3. I don't like the way the code around here is structured already, and this patch is making it more complicated. How about something like this:
static bool trySimplifyICmpWithAdds(CmpInst::Predicate Pred, Value *LHS,
                                    Value *RHS) {
  // Canonicalize nsw add as RHS.
  if (!match(RHS, m_NSWAdd(m_Value(), m_Value())))
    std::swap(LHS, RHS);
  if (!match(RHS, m_NSWAdd(m_Value(), m_Value())))
    return false;

  Value *X;
  const APInt *C1, *C2;
  if (!match(LHS, m_c_Add(m_Value(X), m_APInt(C1))) ||
      !match(RHS, m_c_Add(m_Specific(X), m_APInt(C2))))
    return false;

  return C1->slt(*C2) && C1->isNonNegative();
}
RKSimon added a subscriber: RKSimon.
RKSimon added inline comments.
llvm/lib/Analysis/InstructionSimplify.cpp
2879

Please would it be possible to use match + m_APInt instead? And add some uniform vector test coverage.

Thanks for your help.

  • this is using your function, the pattern matching, which indeed is much nicer,
  • and I think all tests are there, positive and negative. For example, for the positive tests, I have added all the combos, the different data types, including a vector test, and for the negative tests, there are indeed tests with different predicate and the nsw is on the 'wrong' add, etc.
spatel added inline comments.Oct 20 2020, 8:39 AM
llvm/lib/Analysis/InstructionSimplify.cpp
2870–2871

I think this works, but I'm worried that it could break if we are not careful.
If we are swapping the operands, should we also swap the predicate, and then check if it is SLT after the swap?

llvm/test/Transforms/InstSimplify/compare.ll
1875

This is not what I was expecting. To test that the commuted pattern matchibng is working, the first operand on one or both of the adds should be the constant value.

Please do go ahead with pre-committing the extra tests. No review needed unless something is still not clear.

  • Precommitted the extra tests in rG782b8f0d38c9.
  • Rebased this on that.
  • Precommitted 3 tests for testing commuting the operands in rGe86a70ce3def,
  • And rebased this on that again.
SjoerdMeijer added inline comments.Oct 21 2020, 3:11 AM
llvm/lib/Analysis/InstructionSimplify.cpp
2870–2871

Yep, more predicates could be supported here, but I thought to have a start with SLT first, hence the Pred != CmpInst::ICMP_SLT check above on line 2866, so should be fine for now?

spatel added inline comments.Oct 21 2020, 8:56 AM
llvm/lib/Analysis/InstructionSimplify.cpp
2870–2871

I think it's correct:
https://rise4fun.com/Alive/gyqW

So it's a question of what we mean when we say "canonicalize" in the code comment. Transforming the icmp so that the operands are swapped implies that the predicate is also swapped.

Either way, this patch is not complete as-is even for the SLT predicate alone. We miss this:
https://rise4fun.com/Alive/VgB

So we should note that with another TODO comment.

Thanks!
I have added support for the other SLT case and have added tests, which I have not precommitted this time (hopefully easy to spot these cases), just to completely cover the SLT case. After this, I can quickly follow up to address other predicates, if that is okay.

spatel added inline comments.Oct 21 2020, 10:32 AM
llvm/lib/Analysis/InstructionSimplify.cpp
2884

I don't think this is the correct condition:
https://rise4fun.com/Alive/EeGe

Please add a test like this to verify:

define i1 @icmp_nsw_false(i8 %V) {
  %add = add i8 %V, 121
  %addnsw = add nsw i8 %V, -104
  %cmp = icmp slt i8 %add, %addnsw
  ret i1 %cmp
}

Cheers, typo fixed: C2->isNonPositive() -> C1->isNonPositive(). And the test case added.

spatel accepted this revision.Oct 21 2020, 2:28 PM

LGTM

This revision is now accepted and ready to land.Oct 21 2020, 2:28 PM

Many thanks for reviewing!