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


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

Fixes PR26774.

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


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 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 done
by LLVM. 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, the optimizer has license to fold undef to any non-undef

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.

Note: this is not just a problem with atomics or with linking
differently optimized object files. See PR26774 for more realistic
examples that involved neither.

This patch:

This change introduces a new set of linkage 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.

Reviewers: chandlerc, hfinkel, dexonsmith, joker.eph, rnk

Subscribers: mcrosier, llvm-commits

Differential Revision: http://reviews.llvm.org/D18634


sanjoyApr 7 2016, 5:48 PM
Differential Revision
D18634: Don't IPO over functions that can be de-refined
rL265761: ValueMapper: Unduplicate RF_NoModuleLevelChanges check, NFC