This is an archive of the discontinued LLVM Phabricator instance.

[ValueTracking] use nonnull argument attribute to eliminate null checks
ClosedPublic

Authored by spatel on Dec 31 2016, 12:06 PM.

Details

Summary

Enhancing value tracking's analysis of null-ness was suggested in D27855, so here's a first attempt at that.

Irony: the ultimate motivation for this change is to make LLVM itself faster by improving the IR for dyn_cast, but we can't do that without adding analysis and transforms that will likely slow us down even more until we have all of the pieces in place.

Ie, this won't solve PR28430 alone:
https://llvm.org/bugs/show_bug.cgi?id=28430

Diff Detail

Event Timeline

spatel updated this revision to Diff 82777.Dec 31 2016, 12:06 PM
spatel retitled this revision from to [ValueTracking] use nonnull argument attribute to eliminate null checks.
spatel updated this object.
spatel added a subscriber: llvm-commits.
chandlerc edited edge metadata.Dec 31 2016, 1:59 PM

Can you add a some negative tests showing that we don't eliminate null checks *before* a call?

Also would be good to test a subtle case but one I think is correct: when CtxtI is the call instruction with the nonnull. I'm imagining something like deducing nonnull for one argument from the attribute on another when the same pointer is passed to both. Not sure what transform pass to use but it seems a good case to document.

Finally, before this goes in, I think we may need to do something to prevent worsening the bugs exposed by newer glibc marking memcpy and friends with nonnull....

spatel updated this revision to Diff 82786.Jan 1 2017, 10:01 AM
spatel edited edge metadata.

Patch updated:
No changes to the code, but added test cases as suggested by Chandler.

Can you add a some negative tests showing that we don't eliminate null checks *before* a call?

Repurposed the 'caller4' test so that the null check comes before the call. I think this shows a missed opportunity to simplify the check, but let me know if I'm not seeing that correctly. Also, added a 'caller5' test where we can't simplify the check.

Also would be good to test a subtle case but one I think is correct: when CtxtI is the call instruction with the nonnull. I'm imagining something like deducing nonnull for one argument from the attribute on another when the same pointer is passed to both. Not sure what transform pass to use but it seems a good case to document.

Added an instcombine test 'deduce_nonnull_from_another_call' that isn't quite what was suggested, but shows that the value tracking improvement affects an existing transform in InstCombiner::visitCallSite().

Finally, before this goes in, I think we may need to do something to prevent worsening the bugs exposed by newer glibc marking memcpy and friends with nonnull....

If there are required changes for clang/llvm itself, I could use some hints about how to sniff those out. I found this mail from Aug 2015:
http://lists.llvm.org/pipermail/llvm-dev/2015-August/088950.html
and this commit:
rL243927
...we need to add more guard checks around memcpy() and other string.h functions?

reames requested changes to this revision.Jan 3 2017, 9:26 PM
reames edited edge metadata.
reames added inline comments.
lib/Analysis/ValueTracking.cpp
3385

Please handle invokes as well. Use CallSite to abstract over both.

3409

Huh, this should really be handling assumes as well. Can you file a separate bug for that?

This revision now requires changes to proceed.Jan 3 2017, 9:26 PM
spatel added inline comments.Jan 4 2017, 8:27 AM
lib/Analysis/ValueTracking.cpp
3409

I think we can use PR31512 to track this:
https://llvm.org/bugs/show_bug.cgi?id=31512
...but let me know if you think another report is needed.

spatel updated this revision to Diff 83065.Jan 4 2017, 9:30 AM
spatel edited edge metadata.
spatel marked an inline comment as done.

Patch updated:

  1. Changed to use CallSite so we include invokes in the analysis.
  2. Added test case with an invoke to show a transform.

Ping.

Like D27114, this isn't adding nonnull where there was none before; it's just using what's already available. So we don't need to hold this up for clang?

PR31512 doesn't represent Philip's request anymore, so I opened PR31929 for that:
https://llvm.org/bugs/show_bug.cgi?id=31929

reames accepted this revision.Feb 10 2017, 9:40 AM

LGTM

test/Analysis/ValueTracking/known-nonnull-at.ll
76

Minor: We can actually fold the null_check on this path because the call dominates the *use*. However, you can happily ignore that. :)

This revision is now accepted and ready to land.Feb 10 2017, 9:40 AM
spatel added inline comments.Feb 11 2017, 10:36 AM
test/Analysis/ValueTracking/known-nonnull-at.ll
76

Nice catch! I think we can't do that with -instsimplify because it requires modifying the ret insts, but -gvn does the job:

$ ./opt -gvn nullch.ll -S
...

define i1 @caller5(i8* %x, i8* %y) {
  %null_check = icmp eq i8* %y, null
  br i1 %null_check, label %t, label %f

t:                                                ; preds = %0
  ret i1 true

f:                                                ; preds = %0
  call void @bar(i8* %x, i8* %y)
  ret i1 false
}
This revision was automatically updated to reflect the committed changes.