This is an archive of the discontinued LLVM Phabricator instance.

[Attributor] Deduce "nonnull" attribute
ClosedPublic

Authored by uenoku on Jun 20 2019, 8:20 AM.

Diff Detail

Repository
rL LLVM

Event Timeline

uenoku created this revision.Jun 20 2019, 8:20 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 20 2019, 8:20 AM
uenoku updated this revision to Diff 205821.Jun 20 2019, 8:24 AM

Fix test.

uenoku added a comment.EditedJun 20 2019, 9:24 AM

Currently, nonnull is deduced if all the return values are defined by nonnull return function.

I'll make it see function arguments later.

uenoku updated this revision to Diff 206785.Jun 26 2019, 11:42 PM

When a return value is an argument, see it.

uenoku updated this revision to Diff 206786.Jun 26 2019, 11:43 PM

Fix patch.

Please add tests that do pointer arithmetic, e.g., return a + 1.

jdoerfert added inline comments.Jun 27 2019, 1:24 PM
llvm/include/llvm/Transforms/IPO/Attributor.h
676 ↗(On Diff #206786)

copy and past comment, also above

llvm/lib/Transforms/IPO/Attributor.cpp
719 ↗(On Diff #206786)

Undef values are fine. undef basically allows you to "chose" a value, so we can "chose" something other than null.

724 ↗(On Diff #206786)

You should (also) ask for the AANonNull attribute for the value and if you get an abstract attribute that says nonnull we are fine. That should subsume some of the code below and also trigger ones we have AANonNullArgument.

731 ↗(On Diff #206786)

You should ask value tracking via isKnownNonZero here as well. It will need to be improved still to use optimistic information but it is better than nothing.

743 ↗(On Diff #206786)

The predicate above will be reused later on. Maybe "generate" it in a function in AANonNullImpl for a given Attributor.

uenoku updated this revision to Diff 207215.Jun 30 2019, 12:49 AM

Add tests and AANonNullArgument

uenoku marked 4 inline comments as done.Jun 30 2019, 12:50 AM
uenoku updated this revision to Diff 207217.Jun 30 2019, 1:01 AM

Fix typo and add comment.

jdoerfert added inline comments.Jul 1 2019, 12:51 PM
llvm/lib/Transforms/IPO/Attributor.cpp
682 ↗(On Diff #207217)

Explain the behavior of the generate better, what does it return, true for nonnull?

727 ↗(On Diff #207217)

Why would you indicate a fixpoint here? If there is no attribute present in the IR we can still deduce it.

738 ↗(On Diff #207217)

No braces around a single statement

759 ↗(On Diff #207217)

Why do we need to duplicate the A.getAAFor ... code and the ceck afterwards?
Couldn't we just ask for auto *NonNullAA = A.getAAFor<AANonNull>(*this, RV); regardless whether it is an argument, call, or something else?

767 ↗(On Diff #207217)

In that case, move the "indicatePessimisticFixpoint" from the init method here. Than one can at least see what is going on.

llvm/test/Transforms/FunctionAttrs/nonnull.ll
107 ↗(On Diff #207217)

One more with inbounds (below, untested!) and maybe some without inbounds while we are at it.

; CHECK: define i8* @test10
; FIXME: missing nonnull
; ATTRIBUTOR: define i8* @test10
define i8* @test10(i8* %a, i64 %n) {
  %cmp = icmp ne i64 %n, null 
  call void @llvm.assume(i1 %cmp)
  %b = getelementptr inbounds i8, i8* %a, i64 %n
  ret i8* %b
}
uenoku updated this revision to Diff 207486.EditedJul 2 2019, 1:34 AM

Address comments.

uenoku marked 4 inline comments as done.Jul 2 2019, 1:34 AM
uenoku updated this revision to Diff 208106.Jul 4 2019, 6:34 PM

Use isKnownNonZero.

uenoku marked an inline comment as done.Jul 4 2019, 6:35 PM
uenoku updated this revision to Diff 208107.Jul 4 2019, 6:38 PM
uenoku marked an inline comment as done.

Fix comment.

jdoerfert added inline comments.Jul 5 2019, 12:35 PM
llvm/lib/Transforms/IPO/Attributor.cpp
687 ↗(On Diff #208107)

Why isn't isAssumedNonNull() sufficient here?

740 ↗(On Diff #208107)

Please add here something like:

FIXME: The `AAReturnedValues` should provide the predicate with the `ReturnInst` vector as well such that we can use the control flow sensitive version of `isKnownNonZero`. This should fix `test11` in `test/Transforms/FunctionAttrs/nonnull.ll`
764 ↗(On Diff #208107)

CHANGED

770 ↗(On Diff #208107)

I don't think you need the "Impl" part.

uenoku updated this revision to Diff 208609.Jul 9 2019, 1:34 AM

Address comments.

uenoku marked 5 inline comments as done.Jul 9 2019, 1:35 AM
uenoku updated this revision to Diff 208798.Jul 9 2019, 1:46 PM
uenoku retitled this revision from [Attributor] Deduce "nonnull" on return value to [Attributor] Deduce "nonnull" attribute.
uenoku edited the summary of this revision. (Show Details)
  • Deduce nonnull on functions argument if we have nonnull in whole call sites (mostly based on D59202).
  • Deduce nonnull on a call site argument if the passed value is assumed nonnull.

I think this is almost ready.

llvm/include/llvm/Transforms/IPO/Attributor.h
261 ↗(On Diff #208798)

No newline and "sites" in the first line.

llvm/lib/Transforms/IPO/Attributor.cpp
682 ↗(On Diff #208798)

"Generate a predicate that checks if a given value is assumed nonnull".

705 ↗(On Diff #208798)

This comment is a bit out of place. I don't think you need it at all.

835 ↗(On Diff #208798)

You can pass this value to the AbstractAttribute constructor (via a new AANonNullImpl and AANonNull constructor so there is no need to overload this method and keep track of the argument number.

854 ↗(On Diff #208798)

isKnowNonNull(&V, ...) ?

1064 ↗(On Diff #208798)

Could you move this to the remaining Attributor impl, please.

llvm/test/Transforms/FunctionAttrs/nonnull.ll
344 ↗(On Diff #208798)

These are a lot of copies. Could we somehow make the "default" check and only specialize/copy when the two (-funcattr and -attributor) generate different code? Or is this already what you did and I just missed it? Also, could you add FIXMEs where we fail to deduce something with the attributor?

uenoku added inline comments.Jul 10 2019, 8:18 AM
llvm/lib/Transforms/IPO/Attributor.cpp
854 ↗(On Diff #208798)

isKnowNonNull(&V, ...)?

Could you explain more detail?

jdoerfert added inline comments.Jul 10 2019, 9:13 AM
llvm/lib/Transforms/IPO/Attributor.cpp
854 ↗(On Diff #208798)

Sorry. Any reason you do not use the isKnownNonNull functionality here (as you did above)? The check for an AANonNullImpl attribute will only succeed if the values is a call or argument.

xbolva00 added a subscriber: xbolva00.EditedJul 10 2019, 10:30 AM

Hello,

Maybe you remember https://reviews.llvm.org/D53342 ? Should we do it “InstCombine”-way or some alternative one ?

It could fit Atributor nicely, but not sure if nonnull dropping isn’t something weird for Attributor.

Maybe you remember https://reviews.llvm.org/D53342 ? Should we do it “InstCombine”-way or some alternative one ?

I did not, thanks for reminding me. What do you mean by the "InstCombine"-way and what alternatives do you have in mind?
Sorry that I'm a bit lost at the moment, I looked at D53342 and I seemed there are still problems with that patch even though the idea is very useful and we should add it.

Maybe you remember https://reviews.llvm.org/D53342 ? Should we do it “InstCombine”-way or some alternative one ?

I did not, thanks for reminding me. What do you mean by the "InstCombine"-way and what alternatives do you have in mind?
Sorry that I'm a bit lost at the moment, I looked at D53342 and I seemed there are still problems with that patch even though the idea is very useful and we should add it.

I want to ask, whether it is okay to set/drop nonnull attribute in InstCombine or you would like to see this setting/dropping in Attributor.

If you are OK with “InstCombine”-way, I can rebase/update my patch.

Maybe you remember https://reviews.llvm.org/D53342 ? Should we do it “InstCombine”-way or some alternative one ?

I did not, thanks for reminding me. What do you mean by the "InstCombine"-way and what alternatives do you have in mind?
Sorry that I'm a bit lost at the moment, I looked at D53342 and I seemed there are still problems with that patch even though the idea is very useful and we should add it.

I want to ask, whether it is okay to set/drop nonnull attribute in InstCombine or you would like to see this setting/dropping in Attributor.

If you are OK with “InstCombine”-way, I can rebase/update my patch.

I think placing attributes for known library functions should not be part of the Attributor. So, rebase & update your patch and I'll review it.

uenoku updated this revision to Diff 209268.Jul 11 2019, 11:04 AM
uenoku marked 7 inline comments as done.

Address comments.

uenoku marked an inline comment as done.Jul 11 2019, 11:09 AM
uenoku added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
854 ↗(On Diff #208798)

I understand you are saying about isKnownNonZero :).

define internal i32* @f1(i32* %arg) {
bb:
  %tmp = icmp eq i32* %arg, null
  br i1 %tmp, label %bb9, label %bb1

bb1:                                              ; preds = %bb
  %tmp2 = load i32, i32* %arg, align 4
  %tmp3 = icmp eq i32 %tmp2, 0
  br i1 %tmp3, label %bb6, label %bb4

bb4:                                              ; preds = %bb1
  %tmp5 = getelementptr inbounds i32, i32* %arg, i64 1
  %tmp5b = tail call i32* @f3(i32* %tmp5)
  br label %bb9

bb6:                                              ; preds = %bb1
  %tmp7 = tail call i32* @f2(i32* %arg)
  ret i32* %tmp7

bb9:                                              ; preds = %bb4, %bb
  %tmp10 = phi i32* [ %tmp5, %bb4 ], [ inttoptr (i64 4 to i32*), %bb ]
  ret i32* %tmp10
}

define internal i32* @f2(i32* %arg) {
bb:
  %tmp = tail call i32* @f1(i32* %arg)
  ret i32* %tmp
}

define dso_local noalias i32* @f3(i32* %arg) {
bb:
  %tmp = call i32* @f1(i32* %arg)
  ret i32* null
}

Another test case to show some shortcomings of the current approach.

llvm/lib/Transforms/IPO/Attributor.cpp
835 ↗(On Diff #208798)

It seems without the argument number you have to do a linear search. I didn't realize that. Can we store the argument number but still pass the CS.getArgOperand(ArgNo) to the AANonNullImpl constructor as well?

854 ↗(On Diff #208798)

That is what I meant all along ;)

676 ↗(On Diff #209268)

Copy & Paste

801 ↗(On Diff #209268)

We have to make sure we do not get the AANonNullImpl for the argument back when none exists for the call site argument. So you have to test that the associated value of NonNullCSArgAA is the call site operand, or you check that NonNullCSArgAA is not this.

838 ↗(On Diff #209268)

Add a strongly worded comment here telling people they should not (explicitly) look at the argument of the callee in this method.

843 ↗(On Diff #209268)

It's only about the assumed state. So, UNCHANGED as we assumed non-null already otherwise updateImpl wouldn't be called.

llvm/test/Transforms/FunctionAttrs/nonnull.ll
147 ↗(On Diff #209268)

We derive nonnull here because test13 is dead, correct? Maybe that is not what you wanted to test ;)

We accumulated some unnecessary virtual declarations in the Attributor. I created D64637 to remove them in already committed patches. It would be good if you remove them in your active patches too.

uenoku updated this revision to Diff 209593.Jul 12 2019, 2:31 PM
uenoku updated this revision to Diff 209594.
uenoku marked 6 inline comments as done.

Add test and address comments.

uenoku marked an inline comment as done.Jul 12 2019, 2:39 PM
uenoku added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
801 ↗(On Diff #209268)

We have to make sure we do not get the AANonNullImpl for the argument back when none exists for the call site argument. So you have to test that the associated value of NonNullCSArgAA is the call site operand, or you check that NonNullCSArgAA is not this.

I could understand the previous implementation didn't work well. But I couldn't understand the latter. I think it is sufficient to query CS.getArgOperand(ArgNo) to Attributor, isn't it?

uenoku updated this revision to Diff 209657.Jul 12 2019, 5:53 PM
jdoerfert added inline comments.Jul 13 2019, 9:51 AM
llvm/lib/Transforms/IPO/Attributor.cpp
1101 ↗(On Diff #209657)

registerAA(*new AANonNullCallSiteArgument(CS, i, InfoCache), i);

uenoku updated this revision to Diff 209720.Jul 14 2019, 4:17 AM

Fix AANonNullArgument::updateImpl.

uenoku updated this revision to Diff 209723.Jul 14 2019, 5:22 AM

Add other tests and check-all passed.

uenoku updated this revision to Diff 209724.Jul 14 2019, 5:25 AM

Fix typo.

jdoerfert accepted this revision.Jul 14 2019, 10:59 AM

Small nits that should be fixed but other than that this looks good to me.

llvm/lib/Transforms/IPO/Attributor.cpp
1147 ↗(On Diff #209724)

I think we should switch the order here. If we have an AANonNull for the call site we should use it for sure. Otherwise, look at the paramAttr and ask isKnownNonZero. The latter is not necessarily cheap so we should use information computed already first.

You want CallBase not CallInst, or better, compare the anchoredvalue with the CS inst.

1160 ↗(On Diff #209724)

The whole "direction" concept is something I talked about but I don't think we actually need it. Let's just say we need to do it to avoid circular conclusions.

1167 ↗(On Diff #209724)

This seems like something we can move in the initialize method as it should not change over time.

1171 ↗(On Diff #209724)

I improved getAAFor such that whenever it returns a non-null pointer the state of that abstract attribute is valid. That means we do not need to check for a valid state at the call sites.

llvm/test/Transforms/FunctionAttrs/nonnull.ll
4 ↗(On Diff #209724)

We need a target layout here. The test is now dependent on the sizes of pointer (I think) and without target layout it might take the host values which would be bad for 32bit machines.

170 ↗(On Diff #209724)

Will be fixed with D64708.

This revision is now accepted and ready to land.Jul 14 2019, 10:59 AM
uenoku updated this revision to Diff 209749.EditedJul 14 2019, 2:39 PM
uenoku marked 7 inline comments as done.

Address comments. I'll commit when D64708 have been landed.

Address comments. I'll commit when D64708 have been landed.

landed.

uenoku updated this revision to Diff 209763.Jul 14 2019, 11:07 PM

Fix test.

This revision was automatically updated to reflect the committed changes.