Skip to content

Commit 5ce3272

Browse files
sanjoysanjoy
committedApr 8, 2016
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
1 parent 0fa8aca commit 5ce3272

32 files changed

+336
-72
lines changed
 

‎llvm/include/llvm/IR/GlobalValue.h

+100-10
Original file line numberDiff line numberDiff line change
@@ -96,6 +96,56 @@ class GlobalValue : public Constant {
9696
void destroyConstantImpl();
9797
Value *handleOperandChangeImpl(Value *From, Value *To);
9898

99+
/// Returns true if the definition of this global may be replaced by a
100+
/// differently optimized variant of the same source level function at link
101+
/// time.
102+
bool mayBeDerefined() const {
103+
switch (getLinkage()) {
104+
case WeakODRLinkage:
105+
case LinkOnceODRLinkage:
106+
case AvailableExternallyLinkage:
107+
return true;
108+
109+
case WeakAnyLinkage:
110+
case LinkOnceAnyLinkage:
111+
case CommonLinkage:
112+
case ExternalWeakLinkage:
113+
case ExternalLinkage:
114+
case AppendingLinkage:
115+
case InternalLinkage:
116+
case PrivateLinkage:
117+
return mayBeOverridden();
118+
}
119+
120+
llvm_unreachable("Fully covered switch above!");
121+
}
122+
123+
/// Whether the definition of this global may be replaced by something
124+
/// non-equivalent at link time. For example, if a function has weak linkage
125+
/// then the code defining it may be replaced by different code.
126+
bool mayBeOverridden() const {
127+
switch (getLinkage()) {
128+
case WeakAnyLinkage:
129+
case LinkOnceAnyLinkage:
130+
case CommonLinkage:
131+
case ExternalWeakLinkage:
132+
return true;
133+
134+
case AvailableExternallyLinkage:
135+
case LinkOnceODRLinkage:
136+
case WeakODRLinkage:
137+
// The above three cannot be overridden but can be de-refined.
138+
139+
case ExternalLinkage:
140+
case AppendingLinkage:
141+
case InternalLinkage:
142+
case PrivateLinkage:
143+
return false;
144+
}
145+
146+
llvm_unreachable("Fully covered switch above!");
147+
}
148+
99149
protected:
100150
/// \brief The intrinsic ID for this subclass (which must be a Function).
101151
///
@@ -242,14 +292,6 @@ class GlobalValue : public Constant {
242292
isAvailableExternallyLinkage(Linkage);
243293
}
244294

245-
/// Whether the definition of this global may be replaced by something
246-
/// non-equivalent at link time. For example, if a function has weak linkage
247-
/// then the code defining it may be replaced by different code.
248-
static bool mayBeOverridden(LinkageTypes Linkage) {
249-
return Linkage == WeakAnyLinkage || Linkage == LinkOnceAnyLinkage ||
250-
Linkage == CommonLinkage || Linkage == ExternalWeakLinkage;
251-
}
252-
253295
/// Whether the definition of this global may be replaced at link time. NB:
254296
/// Using this method outside of the code generators is almost always a
255297
/// mistake: when working at the IR level use mayBeOverridden instead as it
@@ -260,6 +302,52 @@ class GlobalValue : public Constant {
260302
Linkage == CommonLinkage || Linkage == ExternalWeakLinkage;
261303
}
262304

305+
/// Return true if the currently visible definition of this global (if any) is
306+
/// exactly the definition we will see at runtime.
307+
///
308+
/// Non-exact linkage types inhibits most non-inlining IPO, since a
309+
/// differently optimized variant of the same function can have different
310+
/// observable or undefined behavior than in the variant currently visible.
311+
/// For instance, we could have started with
312+
///
313+
/// void foo(int *v) {
314+
/// int t = 5 / v[0];
315+
/// (void) t;
316+
/// }
317+
///
318+
/// and "refined" it to
319+
///
320+
/// void foo(int *v) { }
321+
///
322+
/// However, we cannot infer readnone for `foo`, since that would justify
323+
/// DSE'ing a store to `v[0]` across a call to `foo`, which can cause
324+
/// undefined behavior if the linker replaces the actual call destination with
325+
/// the unoptimized `foo`.
326+
///
327+
/// Inlining is okay across non-exact linkage types as long as they're not
328+
/// interposable (see \c isInterposable), since in such cases the currently
329+
/// visible variant is *a* correct implementation of the original source
330+
/// function; it just isn't the *only* correct implementation.
331+
bool isDefinitionExact() const {
332+
return !mayBeDerefined();
333+
}
334+
335+
/// Return true if this global has an exact defintion.
336+
bool hasExactDefinition() const {
337+
// While this computes exactly the same thing as
338+
// isStrongDefinitionForLinker, the intended uses are different. This
339+
// function is intended to help decide if specific inter-procedural
340+
// transforms are correct, while isStrongDefinitionForLinker's intended use
341+
// is in low level code generation.
342+
return !isDeclaration() && isDefinitionExact();
343+
}
344+
345+
/// Return true if this global's definition can be substituted with an
346+
/// *arbitrary* definition at link time. We cannot do any IPO or inlinining
347+
/// across interposable call edges, since the callee can be replaced with
348+
/// something arbitrary at link time.
349+
bool isInterposable() const { return mayBeOverridden(); }
350+
263351
bool hasExternalLinkage() const { return isExternalLinkage(getLinkage()); }
264352
bool hasAvailableExternallyLinkage() const {
265353
return isAvailableExternallyLinkage(getLinkage());
@@ -291,8 +379,6 @@ class GlobalValue : public Constant {
291379
return isDiscardableIfUnused(getLinkage());
292380
}
293381

294-
bool mayBeOverridden() const { return mayBeOverridden(getLinkage()); }
295-
296382
bool isWeakForLinker() const { return isWeakForLinker(getLinkage()); }
297383

298384
/// Copy all additional attributes (those not needed to create a GlobalValue)
@@ -365,6 +451,10 @@ class GlobalValue : public Constant {
365451

366452
/// Returns true if this global's definition will be the one chosen by the
367453
/// linker.
454+
///
455+
/// NB! Ideally this should not be used at the IR level at all. If you're
456+
/// interested in optimization constraints implied by the linker's ability to
457+
/// choose an implementation, prefer using \c hasExactDefinition.
368458
bool isStrongDefinitionForLinker() const {
369459
return !(isDeclarationForLinker() || isWeakForLinker());
370460
}

‎llvm/include/llvm/IR/GlobalVariable.h

+3-3
Original file line numberDiff line numberDiff line change
@@ -94,9 +94,9 @@ class GlobalVariable : public GlobalObject, public ilist_node<GlobalVariable> {
9494
/// unique.
9595
inline bool hasDefinitiveInitializer() const {
9696
return hasInitializer() &&
97-
// The initializer of a global variable with weak linkage may change at
98-
// link time.
99-
!mayBeOverridden() &&
97+
// The initializer of a global variable may change to something arbitrary
98+
// at link time.
99+
!isInterposable() &&
100100
// The initializer of a global variable with the externally_initialized
101101
// marker may change at runtime before C++ initializers are evaluated.
102102
!isExternallyInitialized();

‎llvm/lib/Analysis/BasicAliasAnalysis.cpp

+1-1
Original file line numberDiff line numberDiff line change
@@ -359,7 +359,7 @@ static int64_t adjustToPointerSize(int64_t Offset, unsigned PointerSize) {
359359
if (!Op) {
360360
// The only non-operator case we can handle are GlobalAliases.
361361
if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
362-
if (!GA->mayBeOverridden()) {
362+
if (!GA->isInterposable()) {
363363
V = GA->getAliasee();
364364
continue;
365365
}

‎llvm/lib/Analysis/ConstantFolding.cpp

+1-1
Original file line numberDiff line numberDiff line change
@@ -531,7 +531,7 @@ Constant *llvm::ConstantFoldLoadFromConstPtr(Constant *C, Type *Ty,
531531
return GV->getInitializer();
532532

533533
if (auto *GA = dyn_cast<GlobalAlias>(C))
534-
if (GA->getAliasee() && !GA->mayBeOverridden())
534+
if (GA->getAliasee() && !GA->isInterposable())
535535
return ConstantFoldLoadFromConstPtr(GA->getAliasee(), Ty, DL);
536536

537537
// If the loaded value isn't a constant expr, we can't handle it.

‎llvm/lib/Analysis/GlobalsModRef.cpp

+5-4
Original file line numberDiff line numberDiff line change
@@ -471,9 +471,10 @@ void GlobalsAAResult::AnalyzeCallGraph(CallGraph &CG, Module &M) {
471471
const std::vector<CallGraphNode *> &SCC = *I;
472472
assert(!SCC.empty() && "SCC with no functions?");
473473

474-
if (!SCC[0]->getFunction() || SCC[0]->getFunction()->mayBeOverridden()) {
475-
// Calls externally or is weak - can't say anything useful. Remove any existing
476-
// function records (may have been created when scanning globals).
474+
if (!SCC[0]->getFunction() || !SCC[0]->getFunction()->isDefinitionExact()) {
475+
// Calls externally or not exact - can't say anything useful. Remove any
476+
// existing function records (may have been created when scanning
477+
// globals).
477478
for (auto *Node : SCC)
478479
FunctionInfos.erase(Node->getFunction());
479480
continue;
@@ -699,7 +700,7 @@ bool GlobalsAAResult::isNonEscapingGlobalNoAlias(const GlobalValue *GV,
699700
auto *InputGVar = dyn_cast<GlobalVariable>(InputGV);
700701
if (GVar && InputGVar &&
701702
!GVar->isDeclaration() && !InputGVar->isDeclaration() &&
702-
!GVar->mayBeOverridden() && !InputGVar->mayBeOverridden()) {
703+
!GVar->isInterposable() && !InputGVar->isInterposable()) {
703704
Type *GVType = GVar->getInitializer()->getType();
704705
Type *InputGVType = InputGVar->getInitializer()->getType();
705706
if (GVType->isSized() && InputGVType->isSized() &&

‎llvm/lib/Analysis/InlineCost.cpp

+6-5
Original file line numberDiff line numberDiff line change
@@ -1125,7 +1125,7 @@ ConstantInt *CallAnalyzer::stripAndComputeInBoundsConstantOffsets(Value *&V) {
11251125
} else if (Operator::getOpcode(V) == Instruction::BitCast) {
11261126
V = cast<Operator>(V)->getOperand(0);
11271127
} else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
1128-
if (GA->mayBeOverridden())
1128+
if (GA->isInterposable())
11291129
break;
11301130
V = GA->getAliasee();
11311131
} else {
@@ -1477,10 +1477,11 @@ InlineCost llvm::getInlineCost(CallSite CS, Function *Callee,
14771477
if (CS.getCaller()->hasFnAttribute(Attribute::OptimizeNone))
14781478
return llvm::InlineCost::getNever();
14791479

1480-
// Don't inline functions which can be redefined at link-time to mean
1481-
// something else. Don't inline functions marked noinline or call sites
1482-
// marked noinline.
1483-
if (Callee->mayBeOverridden() ||
1480+
// Don't inline functions which can be interposed at link-time. Don't inline
1481+
// functions marked noinline or call sites marked noinline.
1482+
// Note: inlining non-exact non-interposable fucntions is fine, since we know
1483+
// we have *a* correct implementation of the source level function.
1484+
if (Callee->isInterposable() ||
14841485
Callee->hasFnAttribute(Attribute::NoInline) || CS.isNoInline())
14851486
return llvm::InlineCost::getNever();
14861487

‎llvm/lib/Analysis/InstructionSimplify.cpp

+1-1
Original file line numberDiff line numberDiff line change
@@ -616,7 +616,7 @@ static Constant *stripAndComputeConstantOffsets(const DataLayout &DL, Value *&V,
616616
} else if (Operator::getOpcode(V) == Instruction::BitCast) {
617617
V = cast<Operator>(V)->getOperand(0);
618618
} else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
619-
if (GA->mayBeOverridden())
619+
if (GA->isInterposable())
620620
break;
621621
V = GA->getAliasee();
622622
} else {

‎llvm/lib/Analysis/Loads.cpp

+3-3
Original file line numberDiff line numberDiff line change
@@ -299,9 +299,9 @@ bool llvm::isSafeToLoadUnconditionally(Value *V, unsigned Align,
299299
BaseAlign = AI->getAlignment();
300300
} else if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Base)) {
301301
// Global variables are not necessarily safe to load from if they are
302-
// overridden. Their size may change or they may be weak and require a test
303-
// to determine if they were in fact provided.
304-
if (!GV->mayBeOverridden()) {
302+
// interposed arbitrarily. Their size may change or they may be weak and
303+
// require a test to determine if they were in fact provided.
304+
if (!GV->isInterposable()) {
305305
BaseType = GV->getType()->getElementType();
306306
BaseAlign = GV->getAlignment();
307307
}

‎llvm/lib/Analysis/MemoryBuiltins.cpp

+1-1
Original file line numberDiff line numberDiff line change
@@ -529,7 +529,7 @@ SizeOffsetType ObjectSizeOffsetVisitor::visitGEPOperator(GEPOperator &GEP) {
529529
}
530530

531531
SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalAlias(GlobalAlias &GA) {
532-
if (GA.mayBeOverridden())
532+
if (GA.isInterposable())
533533
return unknown();
534534
return compute(GA.getAliasee());
535535
}

‎llvm/lib/Analysis/ScalarEvolution.cpp

+1-1
Original file line numberDiff line numberDiff line change
@@ -4828,7 +4828,7 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) {
48284828
else if (isa<ConstantPointerNull>(V))
48294829
return getZero(V->getType());
48304830
else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V))
4831-
return GA->mayBeOverridden() ? getUnknown(V) : getSCEV(GA->getAliasee());
4831+
return GA->isInterposable() ? getUnknown(V) : getSCEV(GA->getAliasee());
48324832
else if (!isa<ConstantExpr>(V))
48334833
return getUnknown(V);
48344834

‎llvm/lib/Analysis/ValueTracking.cpp

+3-3
Original file line numberDiff line numberDiff line change
@@ -1450,7 +1450,7 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
14501450
// A weak GlobalAlias is totally unknown. A non-weak GlobalAlias has
14511451
// the bits of its aliasee.
14521452
if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
1453-
if (!GA->mayBeOverridden())
1453+
if (!GA->isInterposable())
14541454
computeKnownBits(GA->getAliasee(), KnownZero, KnownOne, Depth + 1, Q);
14551455
return;
14561456
}
@@ -2640,7 +2640,7 @@ Value *llvm::GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset,
26402640
Operator::getOpcode(Ptr) == Instruction::AddrSpaceCast) {
26412641
Ptr = cast<Operator>(Ptr)->getOperand(0);
26422642
} else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(Ptr)) {
2643-
if (GA->mayBeOverridden())
2643+
if (GA->isInterposable())
26442644
break;
26452645
Ptr = GA->getAliasee();
26462646
} else {
@@ -2836,7 +2836,7 @@ Value *llvm::GetUnderlyingObject(Value *V, const DataLayout &DL,
28362836
Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
28372837
V = cast<Operator>(V)->getOperand(0);
28382838
} else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
2839-
if (GA->mayBeOverridden())
2839+
if (GA->isInterposable())
28402840
return V;
28412841
V = GA->getAliasee();
28422842
} else {

‎llvm/lib/IR/Value.cpp

+1-1
Original file line numberDiff line numberDiff line change
@@ -460,7 +460,7 @@ static Value *stripPointerCastsAndOffsets(Value *V) {
460460
Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
461461
V = cast<Operator>(V)->getOperand(0);
462462
} else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
463-
if (StripKind == PSK_ZeroIndices || GA->mayBeOverridden())
463+
if (StripKind == PSK_ZeroIndices || GA->isInterposable())
464464
return V;
465465
V = GA->getAliasee();
466466
} else {

‎llvm/lib/IR/Verifier.cpp

+1-1
Original file line numberDiff line numberDiff line change
@@ -626,7 +626,7 @@ void Verifier::visitAliaseeSubExpr(SmallPtrSetImpl<const GlobalAlias*> &Visited,
626626
if (const auto *GA2 = dyn_cast<GlobalAlias>(GV)) {
627627
Assert(Visited.insert(GA2).second, "Aliases cannot form a cycle", &GA);
628628

629-
Assert(!GA2->mayBeOverridden(), "Alias cannot point to a weak alias",
629+
Assert(!GA2->isInterposable(), "Alias cannot point to an interposable alias",
630630
&GA);
631631
} else {
632632
// Only continue verifying subexpressions of GlobalAliases.

‎llvm/lib/Transforms/IPO/DeadArgumentElimination.cpp

+1-1
Original file line numberDiff line numberDiff line change
@@ -329,7 +329,7 @@ bool DAE::RemoveDeadArgumentsFromCallers(Function &Fn)
329329
// %v = load i32 %p
330330
// ret void
331331
// }
332-
if (!Fn.isStrongDefinitionForLinker())
332+
if (!Fn.hasExactDefinition())
333333
return false;
334334

335335
// Functions with local linkage should already have been handled, except the

‎llvm/lib/Transforms/IPO/FunctionAttrs.cpp

+17-14
Original file line numberDiff line numberDiff line change
@@ -69,9 +69,10 @@ static MemoryAccessKind checkFunctionMemoryAccess(Function &F, AAResults &AAR,
6969
// Already perfect!
7070
return MAK_ReadNone;
7171

72-
// Definitions with weak linkage may be overridden at linktime with
73-
// something that writes memory, so treat them like declarations.
74-
if (F.isDeclaration() || F.mayBeOverridden()) {
72+
// Non-exact function definitions may not be selected at link time, and an
73+
// alternative version that writes to memory may be selected. See the comment
74+
// on GlobalValue::isDefinitionExact for more details.
75+
if (!F.hasExactDefinition()) {
7576
if (AliasAnalysis::onlyReadsMemory(MRB))
7677
return MAK_ReadOnly;
7778

@@ -284,8 +285,7 @@ struct ArgumentUsesTracker : public CaptureTracker {
284285
}
285286

286287
Function *F = CS.getCalledFunction();
287-
if (!F || F->isDeclaration() || F->mayBeOverridden() ||
288-
!SCCNodes.count(F)) {
288+
if (!F || !F->hasExactDefinition() || !SCCNodes.count(F)) {
289289
Captured = true;
290290
return true;
291291
}
@@ -490,9 +490,10 @@ static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) {
490490
// Check each function in turn, determining which pointer arguments are not
491491
// captured.
492492
for (Function *F : SCCNodes) {
493-
// Definitions with weak linkage may be overridden at linktime with
494-
// something that captures pointers, so treat them like declarations.
495-
if (F->isDeclaration() || F->mayBeOverridden())
493+
// We can infer and propagate function attributes only when we know that the
494+
// definition we'll get at link time is *exactly* the definition we see now.
495+
// For more details, see GlobalValue::mayBeDerefined.
496+
if (!F->hasExactDefinition())
496497
continue;
497498

498499
// Functions that are readonly (or readnone) and nounwind and don't return
@@ -745,9 +746,10 @@ static bool addNoAliasAttrs(const SCCNodeSet &SCCNodes) {
745746
if (F->doesNotAlias(0))
746747
continue;
747748

748-
// Definitions with weak linkage may be overridden at linktime, so
749-
// treat them like declarations.
750-
if (F->isDeclaration() || F->mayBeOverridden())
749+
// We can infer and propagate function attributes only when we know that the
750+
// definition we'll get at link time is *exactly* the definition we see now.
751+
// For more details, see GlobalValue::mayBeDerefined.
752+
if (!F->hasExactDefinition())
751753
return false;
752754

753755
// We annotate noalias return values, which are only applicable to
@@ -859,9 +861,10 @@ static bool addNonNullAttrs(const SCCNodeSet &SCCNodes,
859861
Attribute::NonNull))
860862
continue;
861863

862-
// Definitions with weak linkage may be overridden at linktime, so
863-
// treat them like declarations.
864-
if (F->isDeclaration() || F->mayBeOverridden())
864+
// We can infer and propagate function attributes only when we know that the
865+
// definition we'll get at link time is *exactly* the definition we see now.
866+
// For more details, see GlobalValue::mayBeDerefined.
867+
if (!F->hasExactDefinition())
865868
return false;
866869

867870
// We annotate nonnull return values, which are only applicable to

‎llvm/lib/Transforms/IPO/GlobalOpt.cpp

+1-1
Original file line numberDiff line numberDiff line change
@@ -2366,7 +2366,7 @@ bool GlobalOpt::OptimizeGlobalAliases(Module &M) {
23662366
}
23672367

23682368
// If the aliasee may change at link time, nothing can be done - bail out.
2369-
if (J->mayBeOverridden())
2369+
if (J->isInterposable())
23702370
continue;
23712371

23722372
Constant *Aliasee = J->getAliasee();

0 commit comments

Comments
 (0)
Please sign in to comment.