Page MenuHomePhabricator

Don't IPO over functions that can be de-refined
ClosedPublic

Authored by sanjoy on Mar 30 2016, 5:03 PM.

Details

Summary

Fixes PR26774.

If you're aware of the issue, feel free to skip the "Motivation"
section and jump directly to "This patch".

Motivation:

I define "refinement" as discarding behaviors from a program that the
optimizer has license to discard. So transforming:

void f(unsigned x) {
  unsigned t = 5 / x;
  (void)t;
}

to

void f(unsigned x) { }

is refinement, since the behavior went from "if x == 0 then undefined
else nothing" to "nothing" (the optimizer has license to discard
undefined behavior).

Refinement is a fundamental aspect of many mid-level optimizations
LLVM does. For instance, transforming x == (x + 1) to false also
involves refinement since the expression's value went from "if x is
undef then { true or false } else { false }" to "false" (by
definition of undef, the optimizer has license to fold undef to
any non-undef value).

Unfortunately, refinement implies that the optimizer cannot assume
that the implementation of a function it can see has all of the
behavior an unoptimized or a differently optimized version of the same
function can have. This is a problem for functions with comdat
linkage, where a function can be replaced by an unoptimized or a
differently optimized version of the same source level function.

For instance, FunctionAttrs cannot assume a comdat function is
actually readnone even if it does not have any loads or stores in
it; since there may have been loads and stores in the "original
function" that were refined out in the currently visible variant, and
at the link step the linker may in fact choose an implementation with
a load or a store. As an example, consider a function that does two
atomic loads from the same memory location, and writes to memory only
if the two values are not equal. The optimizer is allowed to refine
this function by first CSE'ing the two loads, and the folding the
comparision to always report that the two values are equal. Such a
refined variant will look like it is readonly. However, the
unoptimized version of the function can still write to memory (since
the two loads can result in different values), and selecting the
unoptimized version at link time will retroactively invalidate
transforms we may have done under the assumption that the function
does not write to memory.

This patch:

This change introduces a new set of linkaged types, predicated as
GlobalValue::mayBeDerefined that returns true if the linkage type
allows a function to be replaced by a differently optimized variant at
link time. It then changes a set of IPO passes to bail out if they see
such a function.

Diff Detail

Repository
rL LLVM

Event Timeline

sanjoy updated this revision to Diff 52157.Mar 30 2016, 5:03 PM
sanjoy retitled this revision from to Don't IPO over functions that can be de-refined.
sanjoy updated this object.
sanjoy added a subscriber: llvm-commits.
mehdi_amini added inline comments.Mar 30 2016, 5:30 PM
include/llvm/IR/GlobalValue.h
300 ↗(On Diff #52157)

Isn't it what isStrongDefinitionForLinker() would return?

I don't see why we need a new predicate? (there are probably already too many...)

sanjoy added inline comments.Mar 30 2016, 5:39 PM
include/llvm/IR/GlobalValue.h
300 ↗(On Diff #52157)

Isn't it what isStrongDefinitionForLinker() would return?

Yes, except that isStrongDefinitionForLinker returns false for
declarations as well. But most places where I check mayBeDerefined
I also check for isDeclaration, so that's not really a problem.

I don't see why we need a new predicate? (there are probably already too many...)

I was trying to have a distinction between the linkage type, and the
IPO restriction it implies. So, for instance, if we later add a new
function attribute that allows for the same replacement semantics (or
extract out the optimization restrictions into a function attribute,
and have the linkage type be solely about the linker), then we'd know
what places to update.

Having said that, I don't have a strong opinion one way or the other,
so if the consensus is that it is better to use
isStrongDefinitionForLinker, then I'll change the patch to do that.

So at this point both @joker.eph and @rnk would rather have this path be in terms of isStrongDefinitionForLinker; so I'll do that rename tomorrow unless someone objects before then.

chandlerc edited edge metadata.Mar 30 2016, 6:56 PM
chandlerc added a subscriber: chandlerc.

I would really like to see fewer predicates here. It is too hard to figure
out the right one.

isStrongDefinitionForLinker doesn't make a lot of sense to me as the
spelling of the predicate though because it doesn't tell me, the
optimization author, what it means.

Note that I think mayBeOverridden will become irrelevant with this change,
and so I would look closely at removing that or re-using it.

isStrongDefinitionForLinker doesn't make a lot of sense to me as the
spelling of the predicate though because it doesn't tell me, the
optimization author, what it means.

If we want to common isStrongDefinitionForLinker and
mayBeDerefined, we'll be stuck with using it both in the linker and
in IR level transforms; so we'd need a name that makes sense for both
contexts.

Note that I think mayBeOverridden will become irrelevant with this change,
and so I would look closely at removing that or re-using it.

We will still need a predicate that says "this function can be
replaced with an arbitrary other function at link time[1]" (i.e. can
be interposed); since in that case we have to prevent inlining as
well.

[1]: in mayBeDerefined, the invariant is that what the optimizer sees is
always *a* correct implementation of the source function.

rnk edited edge metadata.Mar 31 2016, 9:31 AM

I would really like to see fewer predicates here. It is too hard to figure
out the right one.

isStrongDefinitionForLinker doesn't make a lot of sense to me as the
spelling of the predicate though because it doesn't tell me, the
optimization author, what it means.

Even if it were renamed to isStrongDefinition? There is no difference between the notions of "strong definition" and "strong definition for linker". In both cases you're looking at the true definition of the symbol. It cannot be de-refined, assuming LLVM's optimizations always refine things.

Now it occurs to me that there are instrumentation passes like MSan that can de-refine code after optimization, and make a readnone function into a function that stores to shadow memory. I wonder if that matters.

Note that I think mayBeOverridden will become irrelevant with this change,
and so I would look closely at removing that or re-using it.

Well, the inliner still needs mayBeOverridden or some equivalent way of separating ODR linkages from non-ODR linkages. It's the only IPO transform that everyone agrees is safe for ODR functions.

In D18634#388277, @rnk wrote:

Now it occurs to me that there are instrumentation passes like MSan
that can de-refine code after optimization, and make a readnone
function into a function that stores to shadow memory. I wonder if
that matters.

I'd say such "instrumentation" passes are not about de-refinement, but
about adding non-observable behavior (though I don't know exactly what
MSan does).

Another example of this sort of thing is the 'Self healing' in Azul's
LVB (load value barrier) -- semantically it is a load, except that it
may also write to memory in a way that won't change observable
behavior.

Note that I think mayBeOverridden will become irrelevant with this change,
and so I would look closely at removing that or re-using it.

Well, the inliner still needs mayBeOverridden or some equivalent way
of separating ODR linkages from non-ODR linkages. It's the only IPO
transform that everyone agrees is safe for ODR functions.

Another way to split this is into isStrongDefinition and
isReplacableODRDefinition (I'd rather have written the second one as
isWeakODRDefinition, but that's confusing since we already have the
weak_odr linkage). Does that sound better?

sanjoy updated this revision to Diff 52280.Mar 31 2016, 1:46 PM
sanjoy edited edge metadata.

Address review discussions.

I've changed the API to be based around "exactness". An "exact"
definition is one that cannot be overridden or de-refined. I've also
removed the confusing "mayBeOverridden is a subset of mayBeDerefined"
bit.

PTAL.

chandlerc added inline comments.Mar 31 2016, 2:42 PM
include/llvm/IR/GlobalValue.h
248 ↗(On Diff #52280)

I think it would be helpful to rename this to match your exact predicates. If you want to keep some parts, i would make them private. This will nicely ensure the complete audit of call sites.

289 ↗(On Diff #52280)

I would make this private, as folks should really be calling the predicates below.

296–298 ↗(On Diff #52280)

This seems wrong. If the function may be overridden, then it necessarily may be overridden by a function which is less refined?

I actually think having these form nicely nested sets is better.

lib/Transforms/IPO/FunctionAttrs.cpp
493–494 ↗(On Diff #52280)

I would change this to be positive: "We can only infer things using an exact definition."

748–749 ↗(On Diff #52280)

ditto

lib/Transforms/IPO/IPConstantPropagation.cpp
164–165 ↗(On Diff #52280)

Use exact terminology here?

sanjoy updated this revision to Diff 52321.Mar 31 2016, 6:37 PM
sanjoy marked 4 inline comments as done.

Address @chandlerc 's review

sanjoy added inline comments.Mar 31 2016, 6:37 PM
include/llvm/IR/GlobalValue.h
296–298 ↗(On Diff #52280)

This seems wrong. If the function may be overridden, then it necessarily may be overridden by a function which is less refined?

I actually think having these form nicely nested sets is better.

I had that form initially (and I prefer that more). I thought this one would be less confusing, but looks like it isn't. Switched to nested sets.

Thinking a bit more about this, but this is looking pretty nice. Will do a final pass shortly.

include/llvm/IR/GlobalValue.h
143–151 ↗(On Diff #52321)

Do we want to invert this (and above) so that the default is conservatively correct if we add a new linkage?

lib/Analysis/GlobalsModRef.cpp
475 ↗(On Diff #52321)

is derefinable -> is not an exact definition

lib/Analysis/InlineCost.cpp
1483 ↗(On Diff #52321)

Missing '.'

sanjoy updated this revision to Diff 52324.Mar 31 2016, 8:33 PM
sanjoy marked 2 inline comments as done.
  • address review
chandlerc accepted this revision.Apr 7 2016, 12:48 AM
chandlerc edited edge metadata.

Comment changes suggested below.

This looks really great Sanjoy, and thanks for driving all of this. Feel free to commit with comment fixes.

Some additional things we really need here:

  1. Send a heads up email to llvm-dev and cfe-dev. I think folks are going to be really, really surprised by regressions due to this and I don't want too much confusion.
  1. Update the release notes with some of the context so that when the next release goes out we have documentation about why we're changing behavior here.
include/llvm/IR/GlobalValue.h
103–124 ↗(On Diff #52324)

I think you should move this *awesome* explanation to the comment on isDefinitionExact, and just leave the first paragraph here. This is the comment optimization authors need to read when calling the predicates.

132–133 ↗(On Diff #52324)

Same issue as with mayBeOverridden IMO -- we should either have the default be conservatively correct or fully enumerate the switch.

335–336 ↗(On Diff #52324)

Add some (hopefully short) hints about what the implications are for transformations and analyses.

lib/Transforms/IPO/FunctionAttrs.cpp
72 ↗(On Diff #52324)

Update this cross reference when you update the comments.

73 ↗(On Diff #52324)

"be overridden at linktime with something that writes memory" -> "not be selected at link time, and an alternative version that writes to memory may be selected"

Mostly trying to avoid making it seem like this only happens intentionally.

This revision is now accepted and ready to land.Apr 7 2016, 12:48 AM
This revision was automatically updated to reflect the committed changes.
sanjoy marked 5 inline comments as done.