Page MenuHomePhabricator

[AssumeBundles] Use assume bundles in isKnownNonZero
Needs ReviewPublic

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

Details

Summary

Use nonnull and dereferenceable from an assume bundle in isKnownNonZero

Diff Detail

Unit TestsFailed

TimeTest
3,300 mslldb-api.functionalities/thread_plan::TestThreadPlanCommands.py
Script: -- /usr/bin/python /mnt/disks/ssd0/agent/workspace/BETA_amd64_debian_testing_clang8/llvm-project/lldb/test/API/dotest.py --arch x86_64 -s /mnt/disks/ssd0/agent/workspace/BETA_amd64_debian_testing_clang8/llvm-project/build/lldb-test-traces -S nm -u CXXFLAGS -u CFLAGS --env ARCHIVER=/usr/bin/ar --env OBJCOPY=/usr/bin/objcopy --env LLVM_LIBS_DIR=/mnt/disks/ssd0/agent/workspace/BETA_amd64_debian_testing_clang8/llvm-project/build/./lib --build-dir /mnt/disks/ssd0/agent/workspace/BETA_amd64_debian_testing_clang8/llvm-project/build/lldb-test-build.noindex --lldb-module-cache-dir /mnt/disks/ssd0/agent/workspace/BETA_amd64_debian_testing_clang8/llvm-project/build/lldb-test-build.noindex/module-cache-lldb/lldb-api --clang-module-cache-dir /mnt/disks/ssd0/agent/workspace/BETA_amd64_debian_testing_clang8/llvm-project/build/lldb-test-build.noindex/module-cache-clang/lldb-api --executable /mnt/disks/ssd0/agent/workspace/BETA_amd64_debian_testing_clang8/llvm-project/build/./bin/lldb --compiler /mnt/disks/ssd0/agent/workspace/BETA_amd64_debian_testing_clang8/llvm-project/build/./bin/clang --dsymutil /mnt/disks/ssd0/agent/workspace/BETA_amd64_debian_testing_clang8/llvm-project/build/./bin/dsymutil --filecheck /mnt/disks/ssd0/agent/workspace/BETA_amd64_debian_testing_clang8/llvm-project/build/./bin/FileCheck --lldb-libs-dir /mnt/disks/ssd0/agent/workspace/BETA_amd64_debian_testing_clang8/llvm-project/build/./lib /mnt/disks/ssd0/agent/workspace/BETA_amd64_debian_testing_clang8/llvm-project/lldb/test/API/functionalities/thread_plan -p TestThreadPlanCommands.py
150 mslldb-unit.Host/_/HostTests::ConnectionFileDescriptorTest.TCPGetURIv6
Note: Google Test filter = ConnectionFileDescriptorTest.TCPGetURIv6 [==========] Running 1 test from 1 test case. [----------] Global test environment set-up.

Event Timeline

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

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.Fri, Mar 13, 9:00 PM
llvm/lib/Analysis/ValueTracking.cpp
712

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.Wed, Mar 18, 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
701

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.Wed, Mar 18, 6:16 AM

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

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

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
708

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

712

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.Fri, Mar 20, 2:21 AM
llvm/lib/IR/KnowledgeRetention.cpp
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.

302 ↗(On Diff #251055)

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

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

Fixed review comments.

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

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.Wed, Mar 25, 4:20 AM
llvm/lib/Analysis/ValueTracking.cpp
712

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.Wed, Mar 25, 5:08 AM

rebased

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

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.Wed, Mar 25, 11:12 AM
Tyker updated this revision to Diff 254131.Wed, Apr 1, 2:25 AM

rebased on D77171

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

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.Wed, Apr 1, 6:08 AM
Tyker added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
712

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.Fri, Apr 3, 8:06 AM

rebase on D77402 and add support for assumption cache.

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

SGTM, thanks!

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

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

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.Sat, Apr 4, 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
699

nit: llvm:: not needed I think

Tyker updated this revision to Diff 255168.EditedSun, Apr 5, 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.