This is an archive of the discontinued LLVM Phabricator instance.

[AssumeBundles] Use assume bundles in isKnownNonZero
ClosedPublic

Authored by Tyker on Mar 13 2020, 11:14 AM.

Details

Summary

Use nonnull and dereferenceable from an assume bundle in isKnownNonZero

Diff Detail

Event Timeline

Tyker created this revision.Mar 13 2020, 11:14 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 13 2020, 11:14 AM
jdoerfert added inline comments.Mar 13 2020, 8:05 PM
llvm/lib/Analysis/ValueTracking.cpp
708

I feel we need to move some/all of this complexity into KnowledgeRetention.
Ideally, one (or at least I) would like something along the lines of:

if (Q.DT && Q.CtxI) {
SmallVector<AttributeKind, 2> AttrKinds;
AttrKinds.append(Attribute::NonNull);
if (llvm::NullPointerIsDefined(Q.CtxI->getFunction(), V->getType()->getPointerAddressSpace()))
   AttrKinds.append(Attribute::Dereferenceable);
if (hasKnownAttributeDominatingInst(*V, AttrKinds, *Q.DT, *Q.CtxI))
  return true;
}

The impl of hasKnownAttributeDominatingInst does the required steps, thus looking at the uses. Actually all the steps should be in getKnownNonNullAndDerefBytesForUse which lives in Attributor.cpp. It does actually more, e.g., use in a call site or and recursive queries via the Attributor, but we should somehow share this logic.

My suggestion:

  1. Something similar to the above interface in KnowledgeRetention
  2. Make Attributor etc. in getKnownNonNullAndDerefBytesForUse optional.
  3. Teach getKnownNonNullAndDerefBytesForUse about assume uses.
  4. Make the getKnownNonNullAndDerefBytesForUse logic public and invoke it if we have an attribute kind NonNull or Dereferenceable[_or_null].

WDYT?

jdoerfert added inline comments.Mar 13 2020, 9:00 PM
llvm/lib/Analysis/ValueTracking.cpp
708

Maybe hasKnownAttributeDominatingInst should not need to look for deref at all as we derive it from deref in the Attributor. Otherwise we could make a helper to encapsulate the NullPointerIsDefined stuff.

Tyker updated this revision to Diff 251015.Mar 18 2020, 2:13 AM
Tyker marked an inline comment as done.

Updated based on review comments.

fhahn added a subscriber: fhahn.
fhahn added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
697

nit: is llvm:: needed?

llvm/lib/IR/KnowledgeRetention.cpp
314 ↗(On Diff #251015)

There's AssumptionCache, which is used in various places that inspect assumes, including ValueTracking. Is there a reason to not use it here?

If there is a layering problem, I think that would need a bit more thought, but ideally we would re-use the existing infrastructure to make things available as widely as possible.

318 ↗(On Diff #251015)

There's isValidAssumeForContext (in ValueTracking.h, https://llvm.org/doxygen/namespacellvm.html#af1d57d70f59588a35ebfe3c4f50fecd2), which already has a similar check (but more general and not necessarily requiring DT. It might be good to use that here instead.

Tyker updated this revision to Diff 251055.Mar 18 2020, 6:16 AM

updated the API so that getKnownNonNullAndDerefBytesForUse can use it as well.

Tyker marked 3 inline comments as done.Mar 18 2020, 6:47 AM
Tyker added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
708

i adapted the getKnownNonNullAndDerefBytesForUse to use the same code. but i am not sure this matches what you had in mind.

Maybe hasKnownAttributeDominatingInst should not need to look for deref at all as we derive it from deref in the Attributor. Otherwise we
could make a helper to encapsulate the NullPointerIsDefined stuff.

in ValueTracking this is not needed if the attributor has run before. but i am not sure all places that can add a deref attribute will add a nonnull as well when they can. if you are confident i am fine with not looking for deref.
in the attributor we should definitely look at both nonnull and deref.

llvm/lib/IR/KnowledgeRetention.cpp
314 ↗(On Diff #251015)

isValidAssumeForContext is now used and i saw the improvement in a test case.

for AssumptionCache. it could be used here but i think it would be costlier to use it than what we currently have.
we are working with knowledge in operand bundles, the assume is always the direct user of the value it knows something about (which is not true for boolean assumes). so we can iterate over all uses (non-recursively) to find all candidate llvm.assume. looking up the knowledge in the assume is cheaper when we have the the operand number which is only available when we lookup from the uses.

I have minor comments but I think this is fine. Please wait on the approval of @fhahn .

llvm/include/llvm/IR/KnowledgeRetention.h
136 ↗(On Diff #251055)

Return true iff U is a use ... with an attribute in AttrKinds. There is no predicate.

144 ↗(On Diff #251055)

- and this assume dominate the instruction Ctx.

The above description matches a convenient wrapper we should add (I also mention that below).

llvm/lib/Analysis/ValueTracking.cpp
704

I don't think DT is mandatory here (line 664).

708

This is fine with me. We might want to add a helper that adds this "common" filter (return isValidAssumeForContext(Assume, Q.CxtI, Q.DT);) given an instruction (CtxI) and an optional dom tree.

llvm/test/Analysis/ValueTracking/assume.ll
92

Add test4b, as test4 but with:
define i32 @test4b(i32* readonly %0, i1 %cond) "null-pointer-is-valid"="true" {

fhahn added inline comments.Mar 20 2020, 2:21 AM
llvm/lib/IR/KnowledgeRetention.cpp
302 ↗(On Diff #251055)

This could be an early exit (like auto *II = dyn_cast....; if (!II) return none().

314 ↗(On Diff #251015)

for AssumptionCache. it could be used here but i think it would be costlier to use it than what we currently have.

I am not sure how using assumptionCache would be more costly, assuming it is already populated?

we are working with knowledge in operand bundles, the assume is always the direct user of the value it knows something about (which is not true for boolean assumes).

But you still have to check all uses of each value (of which many may not be assumptions), to find the available assumptions IIUC. By using AssumptionCache, you can skip the traversal of the use list, which should be quite beneficial, assuming most values do not have associated assumptions.

Tyker updated this revision to Diff 251830.Mar 21 2020, 3:14 AM
Tyker marked 7 inline comments as done.

Fixed review comments.

Tyker updated this revision to Diff 251831.Mar 21 2020, 3:17 AM
Tyker added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
708

isValidAssumeForContext is in Analysis so we can't access it from KnowledgeRetention.

llvm/lib/IR/KnowledgeRetention.cpp
314 ↗(On Diff #251015)

when we lookup from use, we can use the operand number so we can use getKnowledgeFromOperandInAssume which is expected to be cheaper than log N for N being the number of element in the assume. if we don't have the operand number, we have to fallback to linear search.

that said i think we can be get the best of both world by improving AssumptionCache to store the operand bundle index with the assume. but this should probably go into an other patch.

fhahn added inline comments.Mar 25 2020, 4:20 AM
llvm/lib/Analysis/ValueTracking.cpp
708

That's unfortunate in terms of layering :(

I assume the reason this is in IR is because of the AssumeBuilder part, right?

Did you consider splitting the code into an analysis part (that lives in lib/Analysis and can share utilities with ValueTracking & co) & a transform part (that lives in either IR/Transforms)?

I think it would be great to share utilities with the existing code that deals with assumes, as that might lead to general improvements that also benefit the existing code, increases test coverage and reduces duplication.

llvm/lib/IR/KnowledgeRetention.cpp
314 ↗(On Diff #251015)

Right, I see what you mean now. I guess it all depends on what we expect to be larger, the number of (non-assume) uses of the value or the number of operands in the assume. I would expect the former to be larger in practice, given that most values do not have any assume users.

Tyker updated this revision to Diff 252547.Mar 25 2020, 5:08 AM

rebased

Tyker marked an inline comment as done.Mar 25 2020, 6:08 AM
Tyker added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
708

That's unfortunate in terms of layering :(

i agree

I assume the reason this is in IR is because of the AssumeBuilder part, right?

Yes this is why.

Did you consider splitting the code into an analysis part (that lives in lib/Analysis and can share utilities with ValueTracking & co) & a transform > part (that lives in either IR/Transforms)?

yeah i think this is going to happen. but there are too many constraints to satisfy them all, although we can satisfy more constraint than we currently do.
a list of constraint is:

  • Test for the Query part depend on the AssumeBuilder part.
  • We would like the Query part to have access to Analysis for the situation we have here and many more i think.
  • In rG57c964aaa76bfaa908398fbd9d8c9d6d19856859#909236, @nikic wrote: "Are you sure IR is the right place for this? I don't think that we have any passes in there, apart from the IR verifier. Possibly this needs splitting up into parts that are needed by analysis and by transforms?"
  • When working on improvement on the assume builder i saw some situation where having access to Analysis is beneficial.
  • The AssumeBuilder part doesn't logically fit in Analysis

I think that moving the Query part to Analysis is overall a good idea.
however placing the AssumeBuilder part always break some constraint either it is in IR, Analysis or Transform.
if placed in IR we have a pass in IR (for testing) which is subotimal and AssumeBuilder part can't use Analysis.
if placed in Analysis it intuitively doesn't fit there.
if placed in Transform we either need to change the testing method for the Query part or test it from Transform.

reames resigned from this revision.Mar 25 2020, 11:12 AM
Tyker updated this revision to Diff 254131.Apr 1 2020, 2:25 AM

rebased on D77171

fhahn added inline comments.Apr 1 2020, 3:18 AM
llvm/lib/Analysis/ValueTracking.cpp
708

Test for the Query part depend on the AssumeBuilder part.

Is that the main reason for being in IR/ currently?

I think a better compromise would be to have the AsumeBuilder in Transforms/Utils or something and then test the query part in Transform/ there as well. Also, shouldn't it be also possible to test the query part without the AssumeBuilder, by specifying the expected assume bundles in the IR directly?

In rG57c964aaa76bfaa908398fbd9d8c9d6d19856859#909236, @nikic wrote: "Are you sure IR is the right place for this? I don't think that we have any passes in there, apart from the IR verifier. Possibly this needs splitting up into parts that are needed by analysis and by transforms?"

+1 to moving the pass out of IR/.

I think that moving the Query part to Analysis is overall a good idea.

Sounds good. That should be a relatively straight forward change I think.

however placing the AssumeBuilder part always break some constraint either it is in IR, Analysis or Transform.

As mentioned above, if the main reason for it being in IR/ is the unit tests, I would recommend directly construction instruction with assume bundles for the tests in Analysis/ (if possible. I might miss some details here). Conceptually the pass should be somewhere in Transforms/. I think a comparable case is PredicateInfo, which lives in llvm/include/llvm/Transforms/Utils/PredicateInfo.h.

Tyker marked an inline comment as done.Apr 1 2020, 6:08 AM
Tyker added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
708

this is going to be fixed by D77171.
and this patch have been rebased on it.
so i added the getKnowledgeValidInContext as requested.

Tyker updated this revision to Diff 254810.Apr 3 2020, 8:06 AM

rebase on D77402 and add support for assumption cache.

fhahn added inline comments.Apr 3 2020, 9:56 AM
llvm/lib/Analysis/ValueTracking.cpp
708

SGTM, thanks!

I'm fine with this, one test needs an update though.

llvm/test/Transforms/Attributor/nonnull.ll
36

I don't think these test what they should (the change in the Attributor). Since the Attributor knows about assumes (D74888) it can do this deduction already: https://godbolt.org/z/S-PNc-

I think this should work as test though:
https://godbolt.org/z/_6mVi3

fhahn added inline comments.Apr 4 2020, 11:50 AM
llvm/lib/Analysis/AssumeBundleQueries.cpp
133

This probably could be simplified by using the stuff from PatternMatch.h, e.g. something like match(U->getUser(), m_Intrinsic<Intrinsic::assume>(m_Specific(U))

147

nit: llvm:: not needed there I think

151

Can the cache contain elements that are not assumes? I think ideally it would only contain entries with valid assume calls.

155

llvm:: not needed here I think as there is using namespace llvm.

llvm/lib/Analysis/ValueTracking.cpp
695

nit: llvm:: not needed I think

Tyker updated this revision to Diff 255168.EditedApr 5 2020, 8:21 AM
Tyker marked 5 inline comments as done.

addressed comments.
add asserts to make sure that both path of getKnowledgeForValue lead to the same result.

llvm/lib/Analysis/AssumeBundleQueries.cpp
151

the assumption cache cannot hold valid pointers to non-assume instruction.
but it can hold nullptr if an assume was in cache and gets deleted.

Tyker updated this revision to Diff 257252.Apr 14 2020, 2:54 AM

rebased

fhahn added inline comments.Apr 15 2020, 10:15 AM
llvm/include/llvm/Analysis/AssumeBundleQueries.h
18

Nothing from the header seems to be actually used. Forward declare Instruction?

19

I could not find anything that uses declarations from PassManager.h. Did I miss something?

20

Nothing from the header seems to be actually used. Forward declare DominatorTree?

103

unrelated nit: property that holds?

105–109

unrelated, but it is not clear from the comment what ArgValue is referring to. Might be good to clarify

145

nit: Return

146

nit: period at end of sentence.

150

nit: Return

155

llvm:: not needed?

158

nit: Return

llvm/lib/Analysis/AssumeBundleQueries.cpp
133

It would be slightly better to just use cast<> after the check I think.

llvm/lib/Transforms/IPO/Attributor.cpp
19 ↗(On Diff #257252)

all new includes unused?

Tyker updated this revision to Diff 258259.Apr 17 2020, 1:50 AM
Tyker marked 13 inline comments as done.

addressed comments.

fhahn added a comment.Apr 17 2020, 5:23 AM

Thanks for all the changes! The patch looks good to me with respect to my comments, but I think it would be good for someone else to have another look as well.

llvm/include/llvm/Analysis/AssumeBundleQueries.h
106

nit: For example ..... of at least for:

  • AttrKind will...
  • WasOn will be
  • argValue will be...
llvm/lib/Analysis/ValueTracking.cpp
703

Just a side note: it would be good to unify the assumption handling for both variants :)

Tyker updated this revision to Diff 258371.Apr 17 2020, 10:48 AM
Tyker marked an inline comment as done.

addressed comments.

jdoerfert accepted this revision.Apr 22 2020, 10:23 AM

LGTM. One nit below and the Attributor test needs to be changed (see my 2 comments) and rebased + updated wrt check lines.

llvm/lib/Analysis/AssumeBundleQueries.cpp
139

Nit: const auto &AttrKind : AttrKinds) or no auto but the type. Especially the name Attr is (by me) associated with llvm::Attribute not the kind enum.

llvm/test/Transforms/Attributor/nonnull.ll
144

We don't check these prefixes anymore. We need to create a call of test10 to see the return attirbute (I think).

This revision is now accepted and ready to land.Apr 22 2020, 10:23 AM
This revision was automatically updated to reflect the committed changes.