This is an archive of the discontinued LLVM Phabricator instance.

Exploit dereferenceable_or_null attribute in LICM pass
ClosedPublic

Authored by apilipenko on Apr 24 2015, 5:56 AM.

Details

Summary

Allow hoisting of loads from values marked with dereferenceable_or_null attribute. For values marked with the attribute perform context-sensitive analysis to determine whether it's known-non-null or not.

By now context-sensitive non-null analysis is implemented in two different ways: using LazyValueInfo and using dominating conditions. I don't know which one is better, so it's up for discussion.

Diff Detail

Event Timeline

apilipenko updated this revision to Diff 24384.Apr 24 2015, 5:56 AM
apilipenko retitled this revision from to Exploit dereferenceable_or_null attribute in LICM pass.
apilipenko updated this object.
apilipenko edited the test plan for this revision. (Show Details)
apilipenko added reviewers: hfinkel, reames, sanjoy.
apilipenko added a subscriber: Unknown Object (MLST).
sanjoy edited edge metadata.Apr 29 2015, 7:42 PM

After going through the LazyValueInfo code, I cannot easily think of a case where walking dominating uses will be more powerful than LVI. Do you have such an example? If not, then I think we should just use LVI.

After going through the LazyValueInfo code, I cannot easily think of a case where walking dominating uses will be more powerful than LVI. Do you have such an example? If not, then I think we should just use LVI.

LVI is definitely more powerful. The concern about LVI is that it's expensive analysis and when used widely can affect compilation time. Dominating uses is much simple and covers most of the explicit null checks.

I meant to get to this after your reply, but I somehow forgot. Sorry for that!

I'd say you should split out the LVI related to changes into a later patch. That later LVI change should come with test cases that show when it is more powerful than the domtree based approach. Given our use cases, I suspect LVI won't be necessary.

Other than that, I'm okay with this patch (the domtree part). There may be some concerns about compile time, but impact on compile time should not affect anyone not generating dereferenceable_or_null values. I don't want to LGTM it at this point only because

a. I want to have a look at the final version of the patch, without the `getDereferenceableOrNullBytes` accessors or the LVI dependency, before an LGTM
b. Even after (a), I think we should wait on at least one other review to take a look
include/llvm/IR/Argument.h
71 ↗(On Diff #24384)

Given that these are simple getters and are basically extensions of r235132, I think they can go in without further review. Same applies to changes in CallSite.h, Function.h and Instructions.h. One way to do this would be to split these out as a separate review (and remove them from this one) and we can independently LGTM that one and check it in.

apilipenko updated this revision to Diff 24957.May 5 2015, 9:40 AM
apilipenko edited edge metadata.

Missing dereferenceable_or_null getters are separated to another review (http://reviews.llvm.org/D9499). LVI changes removed.

hfinkel added inline comments.May 5 2015, 2:39 PM
include/llvm/Analysis/ValueTracking.h
239

return -> returns

244

What does this comment mean? It is saying anything nonobvious/nontrivial?

reames requested changes to this revision.May 5 2015, 4:15 PM
reames edited edge metadata.

I'm not particularly worried about compile time w.r.t. this patch. The much more invasive version of this in ValueTracking appears to be a non-issue. (Which reminds me, I need to actually enable that!)

With the current round of comments addressed (two comments, one bug fix), I'm willing to sign off on this. We've had plenty of time for interested reviewers to take a look and three different people have looked at it. Not sure what else we could wait for. :)

lib/Analysis/ValueTracking.cpp
3175

Er, the use can definitely be not a branch instruction. I think you're missing:
if (!BI) continue;

Add a test case which covers this please.

lib/Transforms/Scalar/LICM.cpp
650–651

This comment is now stale. Possibly:
// If it is not a trapping instruction, it is always safe to hoist. If the instruction is known not to trap when moved to the preheader, it is also safe to hoist.

This revision now requires changes to proceed.May 5 2015, 4:15 PM
apilipenko added inline comments.May 6 2015, 8:08 AM
include/llvm/Analysis/ValueTracking.h
244

That is the comment from original function description. I left it to say that this function can perform context insensitive analysis. Any suggestions for better wording?

apilipenko updated this revision to Diff 25048.May 6 2015, 8:14 AM
apilipenko edited edge metadata.

Review findings addressed.

reames accepted this revision.May 6 2015, 9:47 AM
reames edited edge metadata.

LGTM w/final comments addressed. Would you like me to commit this for you?

include/llvm/Analysis/ValueTracking.h
244

Given this is the original comment describing the unchanged behaviour, I think you can leave it as is. If Hal disagrees, we can revise this in a separate change.

lib/Analysis/ValueTracking.cpp
3175

I'd prefer you use an early continue here rather than increase the nesting depth.

test/Transforms/LICM/hoist-deref-load.ll
226

Please remove any unnecessary attributes. Sorry for not noticing that before.

This revision is now accepted and ready to land.May 6 2015, 9:47 AM
apilipenko added inline comments.May 7 2015, 3:41 AM
test/Transforms/LICM/hoist-deref-load.ll
226

Does it makes sense to remove them from existing test cases as well?

apilipenko updated this revision to Diff 25151.May 7 2015, 3:43 AM
apilipenko edited edge metadata.

Review findings fixed.

LGTM w/final comments addressed. Would you like me to commit this for you?

Yes, please.

Artur, when applying the patch I'm getting merge conflicts. They look simple, but I'd prefer you rebase just to make sure I don't make any mistakes while resolving them. You have more of the context than I do.

apilipenko updated this revision to Diff 25757.May 14 2015, 1:03 AM

Rebased patch.

This revision was automatically updated to reflect the committed changes.