Don't IPO over functions that can be de-refined
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 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`
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.
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
llvm-svn: 265762
diff --git a/llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp b/llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp
index 2392a1b..d1da0f75 100644
--- a/llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp
+++ b/llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp
@@ -329,7 +329,7 @@
// %v = load i32 %p
// ret void
// }
- if (!Fn.isStrongDefinitionForLinker())
+ if (!Fn.hasExactDefinition())
return false;
// Functions with local linkage should already have been handled, except the
diff --git a/llvm/lib/Transforms/IPO/FunctionAttrs.cpp b/llvm/lib/Transforms/IPO/FunctionAttrs.cpp
index b145771..ec6062a 100644
--- a/llvm/lib/Transforms/IPO/FunctionAttrs.cpp
+++ b/llvm/lib/Transforms/IPO/FunctionAttrs.cpp
@@ -69,9 +69,10 @@
// Already perfect!
return MAK_ReadNone;
- // Definitions with weak linkage may be overridden at linktime with
- // something that writes memory, so treat them like declarations.
- if (F.isDeclaration() || F.mayBeOverridden()) {
+ // Non-exact function definitions may not be selected at link time, and an
+ // alternative version that writes to memory may be selected. See the comment
+ // on GlobalValue::isDefinitionExact for more details.
+ if (!F.hasExactDefinition()) {
if (AliasAnalysis::onlyReadsMemory(MRB))
return MAK_ReadOnly;
@@ -284,8 +285,7 @@
}
Function *F = CS.getCalledFunction();
- if (!F || F->isDeclaration() || F->mayBeOverridden() ||
- !SCCNodes.count(F)) {
+ if (!F || !F->hasExactDefinition() || !SCCNodes.count(F)) {
Captured = true;
return true;
}
@@ -490,9 +490,10 @@
// Check each function in turn, determining which pointer arguments are not
// captured.
for (Function *F : SCCNodes) {
- // Definitions with weak linkage may be overridden at linktime with
- // something that captures pointers, so treat them like declarations.
- if (F->isDeclaration() || F->mayBeOverridden())
+ // We can infer and propagate function attributes only when we know that the
+ // definition we'll get at link time is *exactly* the definition we see now.
+ // For more details, see GlobalValue::mayBeDerefined.
+ if (!F->hasExactDefinition())
continue;
// Functions that are readonly (or readnone) and nounwind and don't return
@@ -745,9 +746,10 @@
if (F->doesNotAlias(0))
continue;
- // Definitions with weak linkage may be overridden at linktime, so
- // treat them like declarations.
- if (F->isDeclaration() || F->mayBeOverridden())
+ // We can infer and propagate function attributes only when we know that the
+ // definition we'll get at link time is *exactly* the definition we see now.
+ // For more details, see GlobalValue::mayBeDerefined.
+ if (!F->hasExactDefinition())
return false;
// We annotate noalias return values, which are only applicable to
@@ -859,9 +861,10 @@
Attribute::NonNull))
continue;
- // Definitions with weak linkage may be overridden at linktime, so
- // treat them like declarations.
- if (F->isDeclaration() || F->mayBeOverridden())
+ // We can infer and propagate function attributes only when we know that the
+ // definition we'll get at link time is *exactly* the definition we see now.
+ // For more details, see GlobalValue::mayBeDerefined.
+ if (!F->hasExactDefinition())
return false;
// We annotate nonnull return values, which are only applicable to
diff --git a/llvm/lib/Transforms/IPO/GlobalOpt.cpp b/llvm/lib/Transforms/IPO/GlobalOpt.cpp
index e793d1b..5bae069 100644
--- a/llvm/lib/Transforms/IPO/GlobalOpt.cpp
+++ b/llvm/lib/Transforms/IPO/GlobalOpt.cpp
@@ -2366,7 +2366,7 @@
}
// If the aliasee may change at link time, nothing can be done - bail out.
- if (J->mayBeOverridden())
+ if (J->isInterposable())
continue;
Constant *Aliasee = J->getAliasee();
diff --git a/llvm/lib/Transforms/IPO/IPConstantPropagation.cpp b/llvm/lib/Transforms/IPO/IPConstantPropagation.cpp
index af541d1..060aac1 100644
--- a/llvm/lib/Transforms/IPO/IPConstantPropagation.cpp
+++ b/llvm/lib/Transforms/IPO/IPConstantPropagation.cpp
@@ -161,9 +161,10 @@
if (F.getReturnType()->isVoidTy())
return false; // No return value.
- // If this function could be overridden later in the link stage, we can't
- // propagate information about its results into callers.
- if (F.mayBeOverridden())
+ // We can infer and propagate the return value only when we know that the
+ // definition we'll get at link time is *exactly* the definition we see now.
+ // For more details, see GlobalValue::mayBeDerefined.
+ if (!F.isDefinitionExact())
return false;
// Check to see if this function returns a constant.
diff --git a/llvm/lib/Transforms/IPO/MergeFunctions.cpp b/llvm/lib/Transforms/IPO/MergeFunctions.cpp
index 719603a..d68c050 100644
--- a/llvm/lib/Transforms/IPO/MergeFunctions.cpp
+++ b/llvm/lib/Transforms/IPO/MergeFunctions.cpp
@@ -1572,7 +1572,7 @@
if (!*I) continue;
Function *F = cast<Function>(*I);
if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() &&
- !F->mayBeOverridden()) {
+ !F->isInterposable()) {
Changed |= insert(F);
}
}
@@ -1586,7 +1586,7 @@
if (!*I) continue;
Function *F = cast<Function>(*I);
if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() &&
- F->mayBeOverridden()) {
+ F->isInterposable()) {
Changed |= insert(F);
}
}
@@ -1683,7 +1683,7 @@
// Replace G with a simple tail call to bitcast(F). Also replace direct uses
// of G with bitcast(F). Deletes G.
void MergeFunctions::writeThunk(Function *F, Function *G) {
- if (!G->mayBeOverridden()) {
+ if (!G->isInterposable()) {
// Redirect direct callers of G to F.
replaceDirectCallers(G, F);
}
@@ -1744,8 +1744,8 @@
// Merge two equivalent functions. Upon completion, Function G is deleted.
void MergeFunctions::mergeTwoFunctions(Function *F, Function *G) {
- if (F->mayBeOverridden()) {
- assert(G->mayBeOverridden());
+ if (F->isInterposable()) {
+ assert(G->isInterposable());
// Make them both thunks to the same internal function.
Function *H = Function::Create(F->getFunctionType(), F->getLinkage(), "",
@@ -1828,8 +1828,8 @@
//
// When one function is weak and the other is strong there is an order imposed
// already. We process strong functions before weak functions.
- if ((OldF.getFunc()->mayBeOverridden() && NewFunction->mayBeOverridden()) ||
- (!OldF.getFunc()->mayBeOverridden() && !NewFunction->mayBeOverridden()))
+ if ((OldF.getFunc()->isInterposable() && NewFunction->isInterposable()) ||
+ (!OldF.getFunc()->isInterposable() && !NewFunction->isInterposable()))
if (OldF.getFunc()->getName() > NewFunction->getName()) {
// Swap the two functions.
Function *F = OldF.getFunc();
@@ -1839,7 +1839,7 @@
}
// Never thunk a strong function to a weak function.
- assert(!OldF.getFunc()->mayBeOverridden() || NewFunction->mayBeOverridden());
+ assert(!OldF.getFunc()->isInterposable() || NewFunction->isInterposable());
DEBUG(dbgs() << " " << OldF.getFunc()->getName()
<< " == " << NewFunction->getName() << '\n');
diff --git a/llvm/lib/Transforms/IPO/PruneEH.cpp b/llvm/lib/Transforms/IPO/PruneEH.cpp
index 22a95fa..464b86c 100644
--- a/llvm/lib/Transforms/IPO/PruneEH.cpp
+++ b/llvm/lib/Transforms/IPO/PruneEH.cpp
@@ -93,7 +93,10 @@
if (!F) {
SCCMightUnwind = true;
SCCMightReturn = true;
- } else if (F->isDeclaration() || F->mayBeOverridden()) {
+ } else if (F->isDeclaration() || F->isInterposable()) {
+ // Note: isInterposable (as opposed to hasExactDefinition) is fine above,
+ // since we're not inferring new attributes here, but only using existing,
+ // assumed to be correct, function attributes.
SCCMightUnwind |= !F->doesNotThrow();
SCCMightReturn |= !F->doesNotReturn();
} else {
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp b/llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp
index 48f258c..d27f107 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp
@@ -640,7 +640,7 @@
}
if (GlobalAlias *GA = dyn_cast<GlobalAlias>(P)) {
- if (GA->mayBeOverridden())
+ if (!GA->isInterposable())
return false;
Worklist.push_back(GA->getAliasee());
continue;
diff --git a/llvm/lib/Transforms/ObjCARC/ObjCARCAPElim.cpp b/llvm/lib/Transforms/ObjCARC/ObjCARCAPElim.cpp
index 969e77c..1bb0739 100644
--- a/llvm/lib/Transforms/ObjCARC/ObjCARCAPElim.cpp
+++ b/llvm/lib/Transforms/ObjCARC/ObjCARCAPElim.cpp
@@ -70,7 +70,7 @@
/// possibly produce autoreleases.
bool ObjCARCAPElim::MayAutorelease(ImmutableCallSite CS, unsigned Depth) {
if (const Function *Callee = CS.getCalledFunction()) {
- if (Callee->isDeclaration() || Callee->mayBeOverridden())
+ if (!Callee->hasExactDefinition())
return true;
for (const BasicBlock &BB : *Callee) {
for (const Instruction &I : BB)
diff --git a/llvm/lib/Transforms/ObjCARC/ObjCARCContract.cpp b/llvm/lib/Transforms/ObjCARC/ObjCARCContract.cpp
index f276d66..ef70d4c 100644
--- a/llvm/lib/Transforms/ObjCARC/ObjCARCContract.cpp
+++ b/llvm/lib/Transforms/ObjCARC/ObjCARCContract.cpp
@@ -605,7 +605,7 @@
cast<GEPOperator>(Arg)->hasAllZeroIndices())
Arg = cast<GEPOperator>(Arg)->getPointerOperand();
else if (isa<GlobalAlias>(Arg) &&
- !cast<GlobalAlias>(Arg)->mayBeOverridden())
+ !cast<GlobalAlias>(Arg)->isInterposable())
Arg = cast<GlobalAlias>(Arg)->getAliasee();
else
break;
diff --git a/llvm/lib/Transforms/Scalar/SCCP.cpp b/llvm/lib/Transforms/Scalar/SCCP.cpp
index 80aace2..2242a2b 100644
--- a/llvm/lib/Transforms/Scalar/SCCP.cpp
+++ b/llvm/lib/Transforms/Scalar/SCCP.cpp
@@ -1724,9 +1724,9 @@
if (F->isDeclaration())
continue;
- // If this is a strong or ODR definition of this function, then we can
- // propagate information about its result into callsites of it.
- if (!F->mayBeOverridden())
+ // If this is an exact definition of this function, then we can propagate
+ // information about its result into callsites of it.
+ if (F->hasExactDefinition())
Solver.AddTrackedFunction(&*F);
// If this function only has direct calls that we can see, we can track its
diff --git a/llvm/lib/Transforms/Scalar/SROA.cpp b/llvm/lib/Transforms/Scalar/SROA.cpp
index 42d3bd3..3c42b79 100644
--- a/llvm/lib/Transforms/Scalar/SROA.cpp
+++ b/llvm/lib/Transforms/Scalar/SROA.cpp
@@ -1549,7 +1549,7 @@
if (Operator::getOpcode(Ptr) == Instruction::BitCast) {
Ptr = cast<Operator>(Ptr)->getOperand(0);
} else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(Ptr)) {
- if (GA->mayBeOverridden())
+ if (GA->isInterposable())
break;
Ptr = GA->getAliasee();
} else {
diff --git a/llvm/lib/Transforms/Utils/Evaluator.cpp b/llvm/lib/Transforms/Utils/Evaluator.cpp
index 47cf5ff..cd130ab 100644
--- a/llvm/lib/Transforms/Utils/Evaluator.cpp
+++ b/llvm/lib/Transforms/Utils/Evaluator.cpp
@@ -427,7 +427,7 @@
// Resolve function pointers.
Function *Callee = dyn_cast<Function>(getVal(CS.getCalledValue()));
- if (!Callee || Callee->mayBeOverridden()) {
+ if (!Callee || Callee->isInterposable()) {
DEBUG(dbgs() << "Can not resolve function pointer.\n");
return false; // Cannot resolve.
}