This is an archive of the discontinued LLVM Phabricator instance.

[ValueTracking] Handle increasing mul recurrence in isKnownNonZero()
ClosedPublic

Authored by jaykang10 on Mar 22 2021, 4:07 AM.

Details

Summary

Detect a recurrence that monotonically increases with mul.

Diff Detail

Event Timeline

jaykang10 created this revision.Mar 22 2021, 4:07 AM
jaykang10 requested review of this revision.Mar 22 2021, 4:07 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 22 2021, 4:07 AM

It might make sense to rephrase this code in terms of matchSimpleRecurrence().

It might make sense to rephrase this code in terms of matchSimpleRecurrence().

Ah! Thanks for letting me know. I did not know that. Let me try.

jaykang10 updated this revision to Diff 332258.Mar 22 2021, 5:31 AM

Use matchSimpleRecurrence

It might make sense to rephrase this code in terms of matchSimpleRecurrence().

Ah! Thanks for letting me know. I did not know that. Let me try.

@nikic I have updated the patch with matchSimpleRecurrence. Please check it.

nikic added inline comments.Mar 22 2021, 11:13 AM
llvm/lib/Analysis/ValueTracking.cpp
2452–2453

I think the matchSimpleRecurrence() check should be higher, e.g. PN->getNumIncomingValues() == 2 is already part of it.

2454

I'd rename R/L to Start and Step.

2461

Why does this exclude C = 1? {1,*,2}<nuw> is still non-zero. The one value is important for inequality, but here we're checking for non-zero.

2464

Again, this isOne() check looks unnecessary to me.

llvm/test/Analysis/ValueTracking/monotonic-phi.ll
61

Why is this or needed?

79

Why does this return false? Isn't this supposed to be a negative test case, due to lack of nuw/nsw?

nikic retitled this revision from [ValueTracking] Improve phi handling in isKnownNonEqual() to [ValueTracking] Handle increasing mul recurrence in isKnownNonZero().Mar 22 2021, 11:15 AM
nikic set the repository for this revision to rG LLVM Github Monorepo.
jaykang10 added inline comments.Mar 22 2021, 11:53 AM
llvm/lib/Analysis/ValueTracking.cpp
2452–2453

Yep, you are right. I will move it up.

2454

Yep, I will rename them.

2461

You are right!!! We are checking non-zero. I will update it.

2464

Yep, I will update it.

llvm/test/Analysis/ValueTracking/monotonic-phi.ll
61

We do not need it. I will remove it.

79

Yep, it is negative test case due to lack of nuw/nsw. It could be better to check CHECK: ret i1 %cmp. I will update it.

Following comments of @nikic, updated code.

nikic added a comment.Mar 22 2021, 2:34 PM

This looks good to me, but I think needs a couple more tests:

  • Positive test for nuw instead of nsw.
  • Negative test for zero start value.
  • Negative test for negative multiply. (We can't really test zero multiply, as it will get folded away.)
  • Negative test for negative start value -- alternatively, you can slightly extend this patch and split the start value check between add and mul: Add requires strictly positive start, but for mul non-zero is sufficient, I believe.
llvm/lib/Analysis/ValueTracking.cpp
2455

Style suggestion: I would write this using m_APInt matchers, which allows you to avoid some of the nesting:

Value *Start, *Step;
const APInt *StartC, *StepC;
if (Q.IIQ.UseInstrInfo && matchSimpleRecurrence(PN, BO, Start, Step) &&
    match(Start, m_APInt(StartC)) && match(Step, m_APInt(StepC)) &&
    StartC->isStrictlyPositive()) {
  ...
}
llvm/test/Analysis/ValueTracking/monotonic-phi.ll
79

Ah, I guess I misread a CHECK-NOT as CHECK here? I've regenerated the check lines for this test in https://github.com/llvm/llvm-project/commit/b7aae9fab14540ad3b4ccda8a5f3a7284f404e63, so you can generate the expected output using llvm/utils/update_test_checks.py.

This looks good to me, but I think needs a couple more tests:

  • Positive test for nuw instead of nsw.
  • Negative test for zero start value.
  • Negative test for negative multiply. (We can't really test zero multiply, as it will get folded away.)
  • Negative test for negative start value -- alternatively, you can slightly extend this patch and split the start value check between add and mul: Add requires strictly positive start, but for mul non-zero is sufficient, I believe.

Yep, let me add more tests.

jaykang10 added inline comments.Mar 23 2021, 3:13 AM
llvm/lib/Analysis/ValueTracking.cpp
2455

Yep, it looks better. I will update it.

llvm/test/Analysis/ValueTracking/monotonic-phi.ll
79

Yep, I will use the script after adding tests.

jaykang10 updated this revision to Diff 332588.Mar 23 2021, 3:15 AM

Added more tests

nikic accepted this revision.Mar 23 2021, 1:57 PM

LGTM

This revision is now accepted and ready to land.Mar 23 2021, 1:57 PM

LGTM

Thanks @nikic If possible, can you also review https://reviews.llvm.org/D98422 please? I think it could also be ready to merge.