This is an archive of the discontinued LLVM Phabricator instance.

Teach InlineCost to account for a null check which can be folded away
ClosedPublic

Authored by reames on Apr 20 2015, 2:45 PM.

Details

Summary

If we have a caller that knows a particular argument can never be null, we can exploit this fact while simplifying values in the inline cost analysis. This has the effect of reducing the cost for inlining when a null check is present in the callee, but the value is known non null in the caller. In particular, any dependent control flow can be discounted from the cost estimate.

Note that this is only adjusting the inline cost analysis. As separate changes, I'm going to add support for propagating the null attribute to the call site. An alternate approach would be the have the inline cost analysis ask a ValueTracking question about the caller's formal argument. Separating this into two pieces using the already existing nonnull attribute seemed preferable.

Does anyone think I need to teach InlineFunction to exploit the attribute in the same way? Or are we willing to assume this will happen correctly after inlining?

Diff Detail

Repository
rL LLVM

Event Timeline

reames updated this revision to Diff 24065.Apr 20 2015, 2:45 PM
reames retitled this revision from to Teach InlineCost to account for a null check which can be folded away.
reames updated this object.
reames edited the test plan for this revision. (Show Details)
reames added reviewers: chandlerc, nlewycky.
reames added a subscriber: Unknown Object (MLST).
sanjoy added a subscriber: sanjoy.Apr 20 2015, 4:24 PM

Minor comment inline. Other than that I don't see any issues with this change, but I also don't know this area of code well enough to LGTM this.

lib/Analysis/IPA/InlineCost.cpp
568 ↗(On Diff #24065)

There is an Argument::getArgNo.

reames updated this revision to Diff 24082.Apr 20 2015, 5:09 PM

Addressing Sanjoys comment. Thanks! I figured that had to exist, but wasn't finding it on Function. Turns out it was on Argument instead. :)

chandlerc edited edge metadata.Apr 24 2015, 4:55 PM

FYI, returning from vacs and travel next week. This will be on my queue.

ping x4.

Chandler, I'd really like to commit this, any chance you could take a look?

reames added a comment.Jun 1 2015, 2:03 PM

ping x 5 (this has been open for over a month)

Two weeks ago, I brought a copy of this review to the social and got review comments from Chandler in person.

He mentioned two minor issues:

  1. A helper function should be abstracted for the non-null handling since it now makes up a large part of the function.
  2. The comments need to emphasize that this is about accessing attributes at the *callsite* more clearly.

I'm about to upload a patch with both of these addressed.

He also expressed concern over the fact that the CallSite (and thus possibly the caller) was exposed to ICA. His concern wasn't w.r.t. to this change per se, but whether a future change might build on this one in a way which would make caching inline cost analysis in the future more difficult. He stated he needed more time to consider the mater before making up his mind on review feedback.

Chandler - Have you come to any conclusions?

reames updated this revision to Diff 27725.Jun 15 2015, 4:25 PM
reames edited edge metadata.

Addressing review comments.

FWIW, I've spent a *lot* of time thinking about this patch. I'm slowly becoming more OK with it. I still have some concerns, but thinking a lot more about the nature of a call site and how we're using it is making me more comfortable.

Two minor points below I'd like your thoughts on...

lib/Analysis/IPA/InlineCost.cpp
525 ↗(On Diff #27725)

What do you think about making this a generic wrapper around CS.paramHasAttr rather than a not-null specific wrapper? We should be careful to *always* use this method to query for attributes, and I'm not sure we do today.

537–542 ↗(On Diff #27725)

Actually, why do we need this at all?

Shouldn't we synthesize a non-null argument attribute given an alloca argument? That would then allow us to propagate it to a non-null parameter attribute if *all* calls have it. That would in turn trip all the optimization opportunities that happen when we *can't* inline. Anyways, somewhat separate from this patch. But if you agree that this should be superfluous, perhaps add a FIXME to remove this code when we DTRT?

Oh no, oh no, never mind. We would still miss cases where we don't re-construct argument attributes on call instructions we've inlined into new callers... There is so much work needed to remove this.

Responding to Chandler's questions.

lib/Analysis/IPA/InlineCost.cpp
525 ↗(On Diff #27725)

I'm not sure what the point of this would be. Are you looking for something to limit access to the CallSite variable? Or something else?

Just to make sure I read your question right, you were asking about a wrapper of the form:
bool CallAnalyzer::hasParamAttr(Value *V, Attributes::AttributeKind Attr)

Right?

(I'm not *opposed* to this; I just don't see the point of the extra abstraction.)

537–542 ↗(On Diff #27725)

I was with you until your last paragraph where you pointed out a case I hadn't thought of. Just to make sure I'm clear, you concerned about something like this right?
a() { alloca a; b(a ) }
b(ptr) { c(ptr) }
c(ptr) { if ptr != null: do_x() }

With the scheme you proposed, we'd have:
inline b into a
reanalyze b's callsite to c in a
inline c into a

It's the need for the reanalyze step your concerned about right? In particular, whether this could happen within the inliner itself without running additional passes?

chandlerc added inline comments.Jun 15 2015, 5:21 PM
lib/Analysis/IPA/InlineCost.cpp
525 ↗(On Diff #27725)

The reason for suggesting this is that it makes it obvious how the next person should query some *other* attribute off of the call site in the CallAnalyzer. It also (IMO) makes it less likely that they'll do so incorrectly.

Essentially, I'm trying to separate the non-null property testing from the callsite attribute querying.

I would probably name it 'isArgumentWithAttribute(Value *V, Attributes::AttributeKind Attr)' or something along those lines.

537–542 ↗(On Diff #27725)

Yes, exactly.

reames added inline comments.Jun 15 2015, 5:34 PM
lib/Analysis/IPA/InlineCost.cpp
525 ↗(On Diff #27725)

I'm fine with this proposal and will upload a patch tomorrow with it done.

p.s. Given I like the removal of copied code the isKnownNonNull extraction resulted in, I plan to keep both.

A general comment: null check code is pretty common, so this patch will be very useful in those scenarios to get better inline cost estimate.

reames updated this revision to Diff 27783.Jun 16 2015, 2:56 PM

Address review comment by Chandler. Also, rename CS to CandidateCS to reduce ambiguity with common parameter name in the file.

chandlerc accepted this revision.Jun 26 2015, 12:40 AM
chandlerc edited edge metadata.

Sorry I didn't cycle back to this more quickly. LGTM, thanks for the minor refactorings to make things more clear. I like both the names and the resulting code structure a lot.

This revision is now accepted and ready to land.Jun 26 2015, 12:40 AM
This revision was automatically updated to reflect the committed changes.