This is an archive of the discontinued LLVM Phabricator instance.

[ValueTracking] isKnownNonZero() should take non-null-ness assumptions into consideration (PR43267)
ClosedPublic

Authored by lebedev.ri on Dec 18 2019, 6:34 AM.

Details

Summary

It is pretty common to assume that something is not zero.
Even optimizer itself sometimes emits such assumptions
(e.g. addAssumeNonNull() in PromoteMemoryToRegister.cpp).

But we currently don't deal with such assumptions :)
The only way isKnownNonZero() handles assumptions is
by calling computeKnownBits() which calls computeKnownBitsFromAssume().
But x != 0 does not tell us anything about set bits,
it only says that there are *some* set bits.
So naturally, KnownBits does not get populated,
and we fail to make use of this assumption.

I propose to deal with this special case by special-casing it
via adding a isKnownNonZeroFromAssume() that returns boolean
when there is such an assumption.

https://rise4fun.com/Alive/6yR

Fixes PR43267.

Diff Detail

Event Timeline

lebedev.ri created this revision.Dec 18 2019, 6:34 AM
nikic added a comment.Dec 18 2019, 6:43 AM

Have you considered integrating this in isKnownNonNullFromDominatingCondition() instead? It already iterates over all users of V != 0 style conditions and could easily consider assumes in addition to branches. That may be more efficient than handling it separately.

nikic added a comment.Dec 18 2019, 6:47 AM

I should mention that CVP also handles this, but as most things in CVP it only works across basic blocks (until D69686 lands). I do think it's reasonable to also have this in ValueTracking though.

Have you considered integrating this in isKnownNonNullFromDominatingCondition() instead? It already iterates over all users of V != 0 style conditions and could easily consider assumes in addition to branches.
That may be more efficient than handling it separately.

I'm not sure why it would be better than relying on the infrastructure specifically designed to handling assumptions?
It isn't obvious to me which approach is more performant, without benchmarks either approach may be much worse than the other one.

nikic added a comment.Dec 18 2019, 7:45 AM

Have you considered integrating this in isKnownNonNullFromDominatingCondition() instead? It already iterates over all users of V != 0 style conditions and could easily consider assumes in addition to branches.
That may be more efficient than handling it separately.

I'm not sure why it would be better than relying on the infrastructure specifically designed to handling assumptions?
It isn't obvious to me which approach is more performant, without benchmarks either approach may be much worse than the other one.

It's a question of which existing infrastructure you want to reuse ;) isKnownNonNullFromDominatingCondition() already handles many other scenarios involving dominating conditions and assume-like operations, but misses a check for the actual assumes.

In particular https://github.com/llvm-mirror/llvm/blob/2c4ca6832fa6b306ee6a7010bfb80a3f2596f824/lib/Analysis/ValueTracking.cpp#L1965-L1968 already deals with llvm.experimental.guard(). Adding support for assumes should be as simple as replacing isGuard() with isGuard() || isAssume() there.

Does that make sense?

Have you considered integrating this in isKnownNonNullFromDominatingCondition() instead? It already iterates over all users of V != 0 style conditions and could easily consider assumes in addition to branches.
That may be more efficient than handling it separately.

I'm not sure why it would be better than relying on the infrastructure specifically designed to handling assumptions?
It isn't obvious to me which approach is more performant, without benchmarks either approach may be much worse than the other one.

It's a question of which existing infrastructure you want to reuse ;) isKnownNonNullFromDominatingCondition() already handles many other scenarios involving dominating conditions and assume-like operations, but misses a check for the actual assumes.

In particular https://github.com/llvm-mirror/llvm/blob/2c4ca6832fa6b306ee6a7010bfb80a3f2596f824/lib/Analysis/ValueTracking.cpp#L1965-L1968 already deals with llvm.experimental.guard(). Adding support for assumes should be as simple as replacing isGuard() with isGuard() || isAssume() there.

Does that make sense?

I get that. The question is, given we have AssumptionCache abstraction, why do we want to avoid it.

I think the code looks fine. (One minor comment inlined).

I will not accept because of the placement discussion. I have not strong opinion (yet) as long as we make sure not only LVI can use this.

llvm/lib/Analysis/ValueTracking.cpp
623

< is also fine, however unlikely.

lebedev.ri marked 2 inline comments as done.

Address inline comment - also handle strict signed comparisons - https://rise4fun.com/Alive/plslNp

lebedev.ri added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
623

I get that. The question is, given we have AssumptionCache abstraction, why do we want to avoid it.

As this code now handles more predicates than the other code-path, I'm okay with your approach.

llvm/lib/Analysis/ValueTracking.cpp
623

As you went through the effort of supporting different predicates, possibly extend this to also handle non-zero constant? That is, not just x > 0 but also x > 100. Something along the lines of...

if (!match(Cmp, m_ICmp(Pred, m_V, m_APInt(C))))
  return false;

// Possibly without the non-canonical predicates?
switch (Pred) {
case ICmpInst::ICMP_NE:
  return C->isNullValue();
case ICmpInst::ICMP_UGT:
  return true;
case ICmpInst::ICMP_UGE:
  return !C->isNullValue();
case ICmpInst::ICMP_SGT:
  return C->isNonNegative();
case ICmpInst::ICMP_SGE:
  return C->isStrictlyPositive();
case ICmpInst::ICMP_SLT:
  return !C->isStrictlyPositive();
case ICmpInst::ICMP_SLE:
  return C->isNegative();
}
xbolva00 added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
593

getFunction()?

623

Tests?

lebedev.ri edited the summary of this revision. (Show Details)Dec 18 2019, 12:32 PM
lebedev.ri marked 2 inline comments as done.

Add FIXME comment, drop untested cases.

llvm/lib/Analysis/ValueTracking.cpp
623

On a second thought, i don't really feel like trying to handle everything at once.
X != 0 is the main motivation here.
Many other cases can be handled (https://rise4fun.com/Alive/6yR),
but i don't know that we need to special-handle them.
Do we know generic KnownBits (computeKnownBitsFromAssume)
does not handle them? I don't, and i won't until there are tests.

Though after sleeping on it, and finding the right microscope for this nail, other predicates added.
Hopefully the change can now proceed.

While there, handle assume(y u< v) too.

jdoerfert accepted this revision.Dec 19 2019, 11:35 AM

LGTM. One suggestion below.

FWIW. The way I read the comments by @nikic, I think this can be pushed.

llvm/lib/Analysis/ValueTracking.cpp
648

I'd move the isValidAssumeForContext(I, Q.CxtI, Q.DT) as early as possible, assuming I haven't overlooked a case where it is not called.

This revision is now accepted and ready to land.Dec 19 2019, 11:35 AM
nikic added inline comments.Dec 19 2019, 12:02 PM
llvm/lib/Analysis/ValueTracking.cpp
648

As isValidAssumeForContext() may need to perform a full block scan, I think it's preferable to check this condition last, and existing code seems to follow this, even if it means duplicating many isValidAssumeForContext() calls. I do agree though that it would be good to restructure the code in a way that only requires writing out the check once. Basically return icmpImpliesNonZero() && isValidAssumeForContext().

nikic added inline comments.Dec 19 2019, 12:12 PM
llvm/test/Transforms/InstCombine/assume.ll
298

Is this transform correct? As escape is not willreturn we don't necessarily reach the assume below, or?

nikic requested changes to this revision.Dec 19 2019, 12:19 PM
nikic added inline comments.
llvm/test/Transforms/InstCombine/assume.ll
298

I think this might be a bug in isValidAssumeForContext(): https://github.com/llvm-mirror/llvm/blob/2c4ca6832fa6b306ee6a7010bfb80a3f2596f824/lib/Analysis/ValueTracking.cpp#L570 shouldn't be using std::next().

Probably this never mattered before, but I believe this needs to be fixed before this patch can land.

This revision now requires changes to proceed.Dec 19 2019, 12:19 PM
lebedev.ri marked 6 inline comments as done.

Addressed inline comments.

nikic added inline comments.Dec 19 2019, 1:39 PM
llvm/lib/Analysis/ValueTracking.cpp
572

Does just BasicBlock::const_iterator I(CxtI), IE(Inv); work?

611

Any particular reason to use m_ConstantInt() over m_APInt() here? The difference in vector handling?

636

nit: Unnecessary newline.

llvm/test/Transforms/InstCombine/assume.ll
272

I'm assuming that we first evaluate the icmp below, then the load is one-use and gets sunk. I'm wondering why the assume is not converted into !nonnull metadata after that, as the control dependence is now gone.

lebedev.ri marked 4 inline comments as done.

Some more nits addressed (these are several commits locally)

llvm/lib/Analysis/ValueTracking.cpp
611

I've never ever seen assumptions for vectors, so either should be fine.

llvm/test/Transforms/InstCombine/assume.ll
272

The best i can tell is because isEphemeralValueOf() says so?
I'm not really familiar with that, best to file a bug.

nikic accepted this revision.Dec 19 2019, 2:38 PM

LGTM, thanks!

llvm/test/Transforms/InstCombine/assume.ll
272

Oooh, that makes sense... If we convert the assume to !nonnull, we'd just end up eliminating the load completely afterwards and lose the information.

It might make sense to slightly tweak the test (maybe add a use of %load in not_taken?) so the sinking does not happen. As it is right now, the test no longer tests what it was originally testing, even if the transform still fails for an unrelated reason.

This revision is now accepted and ready to land.Dec 19 2019, 2:38 PM

Thank you for the review.

llvm/test/Transforms/InstCombine/assume.ll
272

The confusing thing is, if i manually sink load+cmp, then we add !nonnull and remove everything here.

nikic added inline comments.Dec 19 2019, 3:02 PM
llvm/test/Transforms/InstCombine/assume.ll
272

If the instruction is manually sunk, then we (probably) first convert the first assume into !nonnull (because there is still the other use in the second icmp, so not ephemeral), then fold the icmp, then dce the load. Not ideal, but probably also not really preventable.