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

[sanjoy]

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.

[mehdi_amini]

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]

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.

[sanjoy]

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]

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.

[sanjoy]

In D18634#387841, @chandlerc wrote:

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]

In D18634#387841, @chandlerc wrote:

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.

[sanjoy]

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]

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]

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]

Address @chandlerc 's review

[sanjoy]

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.

[chandlerc]

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]

• address review

[chandlerc]

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.

2. 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.

llvm/trunk/include/llvm/IR/GlobalValue.h

private:
   // Give subclasses access to what otherwise would be wasted padding.
   // (19 + 3 + 2 + 1 + 2 + 5) == 32.
   unsigned SubClassData : GlobalValueSubClassDataBits;
 
   friend class Constant;
   void destroyConstantImpl();
   Value *handleOperandChangeImpl(Value *From, Value *To);
 
+  /// Returns true if the definition of this global may be replaced by a
+  /// differently optimized variant of the same source level function at link
+  /// time.
+  bool mayBeDerefined() const {
+    switch (getLinkage()) {
+    case WeakODRLinkage:
+    case LinkOnceODRLinkage:
+    case AvailableExternallyLinkage:
+      return true;
+
+    case WeakAnyLinkage:
+    case LinkOnceAnyLinkage:
+    case CommonLinkage:
+    case ExternalWeakLinkage:
+    case ExternalLinkage:
+    case AppendingLinkage:
+    case InternalLinkage:
+    case PrivateLinkage:
+      return mayBeOverridden();
+    }
+
+    llvm_unreachable("Fully covered switch above!");
+  }
+
+  /// Whether the definition of this global may be replaced by something
+  /// non-equivalent at link time. For example, if a function has weak linkage
+  /// then the code defining it may be replaced by different code.
+  bool mayBeOverridden() const {
+    switch (getLinkage()) {
+    case WeakAnyLinkage:
+    case LinkOnceAnyLinkage:
+    case CommonLinkage:
+    case ExternalWeakLinkage:
+      return true;
+
+    case AvailableExternallyLinkage:
+    case LinkOnceODRLinkage:
+    case WeakODRLinkage:
+      // The above three cannot be overridden but can be de-refined.
+
+    case ExternalLinkage:
+    case AppendingLinkage:
+    case InternalLinkage:
+    case PrivateLinkage:
+      return false;
+    }
+
+    llvm_unreachable("Fully covered switch above!");
+  }
+
 protected:
   /// \brief The intrinsic ID for this subclass (which must be a Function).
   ///
   /// This member is defined by this class, but not used for anything.
   /// Subclasses can use it to store their intrinsic ID, if they have one.
   ///
   /// This is stored here to save space in Function on 64-bit hosts.
   Intrinsic::ID IntID;
public:
 
   /// Whether the definition of this global may be discarded if it is not used
   /// in its compilation unit.
   static bool isDiscardableIfUnused(LinkageTypes Linkage) {
     return isLinkOnceLinkage(Linkage) || isLocalLinkage(Linkage) ||
            isAvailableExternallyLinkage(Linkage);
   }
 
-  /// Whether the definition of this global may be replaced by something
-  /// non-equivalent at link time. For example, if a function has weak linkage
-  /// then the code defining it may be replaced by different code.
-  static bool mayBeOverridden(LinkageTypes Linkage) {
-    return Linkage == WeakAnyLinkage || Linkage == LinkOnceAnyLinkage ||
-           Linkage == CommonLinkage || Linkage == ExternalWeakLinkage;
-  }
-
   /// Whether the definition of this global may be replaced at link time.  NB:
   /// Using this method outside of the code generators is almost always a
   /// mistake: when working at the IR level use mayBeOverridden instead as it
   /// knows about ODR semantics.
   static bool isWeakForLinker(LinkageTypes Linkage)  {
     return Linkage == WeakAnyLinkage || Linkage == WeakODRLinkage ||
            Linkage == LinkOnceAnyLinkage || Linkage == LinkOnceODRLinkage ||
            Linkage == CommonLinkage || Linkage == ExternalWeakLinkage;
   }
 
+  /// Return true if the currently visible definition of this global (if any) is
+  /// exactly the definition we will see at runtime.
+  ///
+  /// Non-exact linkage types inhibits most non-inlining IPO, since a
+  /// differently optimized variant of the same function can have different
+  /// observable or undefined behavior than in the variant currently visible.
+  /// For instance, we could have started with
+  ///
+  ///   void foo(int *v) {
+  ///     int t = 5 / v[0];
+  ///     (void) t;
+  ///   }
+  ///
+  /// and "refined" it to
+  ///
+  ///   void foo(int *v) { }
+  ///
+  /// However, we cannot infer readnone for `foo`, since that would justify
+  /// DSE'ing a store to `v[0]` across a call to `foo`, which can cause
+  /// undefined behavior if the linker replaces the actual call destination with
+  /// the unoptimized `foo`.
+  ///
+  /// Inlining is okay across non-exact linkage types as long as they're not
+  /// interposable (see \c isInterposable), since in such cases the currently
+  /// visible variant is *a* correct implementation of the original source
+  /// function; it just isn't the *only* correct implementation.
+  bool isDefinitionExact() const {
+    return !mayBeDerefined();
+  }
+
+  /// Return true if this global has an exact defintion.
+  bool hasExactDefinition() const {
+    // While this computes exactly the same thing as
+    // isStrongDefinitionForLinker, the intended uses are different.  This
+    // function is intended to help decide if specific inter-procedural
+    // transforms are correct, while isStrongDefinitionForLinker's intended use
+    // is in low level code generation.
+    return !isDeclaration() && isDefinitionExact();
+  }
+
+  /// Return true if this global's definition can be substituted with an
+  /// *arbitrary* definition at link time.  We cannot do any IPO or inlinining
+  /// across interposable call edges, since the callee can be replaced with
+  /// something arbitrary at link time.
+  bool isInterposable() const { return mayBeOverridden(); }
+
   bool hasExternalLinkage() const { return isExternalLinkage(getLinkage()); }
   bool hasAvailableExternallyLinkage() const {
     return isAvailableExternallyLinkage(getLinkage());
   }
   bool hasLinkOnceLinkage() const { return isLinkOnceLinkage(getLinkage()); }
   bool hasLinkOnceODRLinkage() const {
     return isLinkOnceODRLinkage(getLinkage());
   }
void setLinkage(LinkageTypes LT) {
     Linkage = LT;
   }
   LinkageTypes getLinkage() const { return LinkageTypes(Linkage); }
 
   bool isDiscardableIfUnused() const {
     return isDiscardableIfUnused(getLinkage());
   }
 
-  bool mayBeOverridden() const { return mayBeOverridden(getLinkage()); }
-
   bool isWeakForLinker() const { return isWeakForLinker(getLinkage()); }
 
   /// Copy all additional attributes (those not needed to create a GlobalValue)
   /// from the GlobalValue Src to this one.
   virtual void copyAttributesFrom(const GlobalValue *Src);
 
   /// If special LLVM prefix that is used to inform the asm printer to not emit
   /// usual symbol prefix before the symbol name is used then return linkage
bool isDeclarationForLinker() const {
     if (hasAvailableExternallyLinkage())
       return true;
 
     return isDeclaration();
   }
 
   /// Returns true if this global's definition will be the one chosen by the
   /// linker.
+  ///
+  /// NB! Ideally this should not be used at the IR level at all.  If you're
+  /// interested in optimization constraints implied by the linker's ability to
+  /// choose an implementation, prefer using \c hasExactDefinition.
   bool isStrongDefinitionForLinker() const {
     return !(isDeclarationForLinker() || isWeakForLinker());
   }
 
   // Returns true if the alignment of the value can be unilaterally
   // increased.
   bool canIncreaseAlignment() const;
 

llvm/trunk/include/llvm/IR/GlobalVariable.h

public:
   ///
   /// @b = global weak SomeType* null - Initializer is neither definitive nor
   /// unique.
   ///
   /// @c = global weak_odr SomeType* null - Initializer is definitive, but not
   /// unique.
   inline bool hasDefinitiveInitializer() const {
     return hasInitializer() &&
-      // The initializer of a global variable with weak linkage may change at
-      // link time.
-      !mayBeOverridden() &&
+      // The initializer of a global variable may change to something arbitrary
+      // at link time.
+      !isInterposable() &&
       // The initializer of a global variable with the externally_initialized
       // marker may change at runtime before C++ initializers are evaluated.
       !isExternallyInitialized();
   }
 
   /// hasUniqueInitializer - Whether the global variable has an initializer, and
   /// any changes made to the initializer will turn up in the final executable.
   inline bool hasUniqueInitializer() const {

llvm/trunk/lib/Analysis/BasicAliasAnalysis.cpp

/*static*/ const Value *BasicAAResult::DecomposeGEPExpression(
 
   BaseOffs = 0;
   do {
     // See if this is a bitcast or GEP.
     const Operator *Op = dyn_cast<Operator>(V);
     if (!Op) {
       // The only non-operator case we can handle are GlobalAliases.
       if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
-        if (!GA->mayBeOverridden()) {
+        if (!GA->isInterposable()) {
           V = GA->getAliasee();
           continue;
         }
       }
       return V;
     }
 
     if (Op->getOpcode() == Instruction::BitCast ||

llvm/trunk/lib/Analysis/ConstantFolding.cpp

 Constant *llvm::ConstantFoldLoadFromConstPtr(Constant *C, Type *Ty,
                                              const DataLayout &DL) {
   // First, try the easy cases:
   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C))
     if (GV->isConstant() && GV->hasDefinitiveInitializer())
       return GV->getInitializer();
 
   if (auto *GA = dyn_cast<GlobalAlias>(C))
-    if (GA->getAliasee() && !GA->mayBeOverridden())
+    if (GA->getAliasee() && !GA->isInterposable())
       return ConstantFoldLoadFromConstPtr(GA->getAliasee(), Ty, DL);
 
   // If the loaded value isn't a constant expr, we can't handle it.
   ConstantExpr *CE = dyn_cast<ConstantExpr>(C);
   if (!CE)
     return nullptr;
 
   if (CE->getOpcode() == Instruction::GetElementPtr) {

llvm/trunk/lib/Analysis/GlobalsModRef.cpp

 /// function.
 void GlobalsAAResult::AnalyzeCallGraph(CallGraph &CG, Module &M) {
   // We do a bottom-up SCC traversal of the call graph.  In other words, we
   // visit all callees before callers (leaf-first).
   for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
     const std::vector<CallGraphNode *> &SCC = *I;
     assert(!SCC.empty() && "SCC with no functions?");
 
-    if (!SCC[0]->getFunction() || SCC[0]->getFunction()->mayBeOverridden()) {
-      // Calls externally or is weak - can't say anything useful. Remove any existing
-      // function records (may have been created when scanning globals).
+    if (!SCC[0]->getFunction() || !SCC[0]->getFunction()->isDefinitionExact()) {
+      // Calls externally or not exact - can't say anything useful. Remove any
+      // existing function records (may have been created when scanning
+      // globals).
       for (auto *Node : SCC)
         FunctionInfos.erase(Node->getFunction());
       continue;
     }
 
     FunctionInfo &FI = FunctionInfos[SCC[0]->getFunction()];
     bool KnowNothing = false;
 
if (auto *InputGV = dyn_cast<GlobalValue>(Input)) {
         return false;
 
       // Distinct GlobalVariables never alias, unless overriden or zero-sized.
       // FIXME: The condition can be refined, but be conservative for now.
       auto *GVar = dyn_cast<GlobalVariable>(GV);
       auto *InputGVar = dyn_cast<GlobalVariable>(InputGV);
       if (GVar && InputGVar &&
           !GVar->isDeclaration() && !InputGVar->isDeclaration() &&
-          !GVar->mayBeOverridden() && !InputGVar->mayBeOverridden()) {
+          !GVar->isInterposable() && !InputGVar->isInterposable()) {
         Type *GVType = GVar->getInitializer()->getType();
         Type *InputGVType = InputGVar->getInitializer()->getType();
         if (GVType->isSized() && InputGVType->isSized() &&
             (DL.getTypeAllocSize(GVType) > 0) &&
             (DL.getTypeAllocSize(InputGVType) > 0))
           continue;
       }
 

llvm/trunk/lib/Analysis/InlineCost.cpp

ConstantInt *CallAnalyzer::stripAndComputeInBoundsConstantOffsets(Value *&V) {
   do {
     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
       if (!GEP->isInBounds() || !accumulateGEPOffset(*GEP, Offset))
         return nullptr;
       V = GEP->getPointerOperand();
     } else if (Operator::getOpcode(V) == Instruction::BitCast) {
       V = cast<Operator>(V)->getOperand(0);
     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
-      if (GA->mayBeOverridden())
+      if (GA->isInterposable())
         break;
       V = GA->getAliasee();
     } else {
       break;
     }
     assert(V->getType()->isPointerTy() && "Unexpected operand type!");
   } while (Visited.insert(V).second);
 
InlineCost llvm::getInlineCost(CallSite CS, Function *Callee,
   // always-inline attribute).
   if (!functionsHaveCompatibleAttributes(CS.getCaller(), Callee, CalleeTTI))
     return llvm::InlineCost::getNever();
 
   // Don't inline this call if the caller has the optnone attribute.
   if (CS.getCaller()->hasFnAttribute(Attribute::OptimizeNone))
     return llvm::InlineCost::getNever();
 
-  // Don't inline functions which can be redefined at link-time to mean
-  // something else.  Don't inline functions marked noinline or call sites
-  // marked noinline.
-  if (Callee->mayBeOverridden() ||
+  // Don't inline functions which can be interposed at link-time.  Don't inline
+  // functions marked noinline or call sites marked noinline.
+  // Note: inlining non-exact non-interposable fucntions is fine, since we know
+  // we have *a* correct implementation of the source level function.
+  if (Callee->isInterposable() ||
       Callee->hasFnAttribute(Attribute::NoInline) || CS.isNoInline())
     return llvm::InlineCost::getNever();
 
   DEBUG(llvm::dbgs() << "      Analyzing call of " << Callee->getName()
         << "...\n");
 
   CallAnalyzer CA(CalleeTTI, ACT, *Callee, DefaultThreshold, CS);
   bool ShouldInline = CA.analyzeCall(CS);

llvm/trunk/lib/Analysis/InstructionSimplify.cpp

do {
     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
       if ((!AllowNonInbounds && !GEP->isInBounds()) ||
           !GEP->accumulateConstantOffset(DL, Offset))
         break;
       V = GEP->getPointerOperand();
     } else if (Operator::getOpcode(V) == Instruction::BitCast) {
       V = cast<Operator>(V)->getOperand(0);
     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
-      if (GA->mayBeOverridden())
+      if (GA->isInterposable())
         break;
       V = GA->getAliasee();
     } else {
       break;
     }
     assert(V->getType()->getScalarType()->isPointerTy() &&
            "Unexpected operand type!");
   } while (Visited.insert(V).second);

llvm/trunk/lib/Analysis/Loads.cpp

bool llvm::isSafeToLoadUnconditionally(Value *V, unsigned Align,
   Type *BaseType = nullptr;
   unsigned BaseAlign = 0;
   if (const AllocaInst *AI = dyn_cast<AllocaInst>(Base)) {
     // An alloca is safe to load from as load as it is suitably aligned.
     BaseType = AI->getAllocatedType();
     BaseAlign = AI->getAlignment();
   } else if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Base)) {
     // Global variables are not necessarily safe to load from if they are
-    // overridden. Their size may change or they may be weak and require a test
-    // to determine if they were in fact provided.
-    if (!GV->mayBeOverridden()) {
+    // interposed arbitrarily. Their size may change or they may be weak and
+    // require a test to determine if they were in fact provided.
+    if (!GV->isInterposable()) {
       BaseType = GV->getType()->getElementType();
       BaseAlign = GV->getAlignment();
     }
   }
 
   PointerType *AddrTy = cast<PointerType>(V->getType());
   uint64_t LoadSize = DL.getTypeStoreSize(AddrTy->getElementType());
 

llvm/trunk/lib/Analysis/MemoryBuiltins.cpp

SizeOffsetType ObjectSizeOffsetVisitor::visitGEPOperator(GEPOperator &GEP) {
   APInt Offset(IntTyBits, 0);
   if (!bothKnown(PtrData) || !GEP.accumulateConstantOffset(DL, Offset))
     return unknown();
 
   return std::make_pair(PtrData.first, PtrData.second + Offset);
 }
 
 SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalAlias(GlobalAlias &GA) {
-  if (GA.mayBeOverridden())
+  if (GA.isInterposable())
     return unknown();
   return compute(GA.getAliasee());
 }
 
 SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalVariable(GlobalVariable &GV){
   if (!GV.hasDefinitiveInitializer())
     return unknown();
 

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

if (Instruction *I = dyn_cast<Instruction>(V)) {
     // analysis depends on.
     if (!DT.isReachableFromEntry(I->getParent()))
       return getUnknown(V);
   } else if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
     return getConstant(CI);
   else if (isa<ConstantPointerNull>(V))
     return getZero(V->getType());
   else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V))
-    return GA->mayBeOverridden() ? getUnknown(V) : getSCEV(GA->getAliasee());
+    return GA->isInterposable() ? getUnknown(V) : getSCEV(GA->getAliasee());
   else if (!isa<ConstantExpr>(V))
     return getUnknown(V);
 
   Operator *U = cast<Operator>(V);
   if (auto BO = MatchBinaryOp(U)) {
     switch (BO->Opcode) {
     case Instruction::Add: {
       // The simple thing to do would be to just call getSCEV on both operands

llvm/trunk/lib/Analysis/ValueTracking.cpp

void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
   // Limit search depth.
   // All recursive calls that increase depth must come after this.
   if (Depth == MaxDepth)
     return;
 
   // A weak GlobalAlias is totally unknown. A non-weak GlobalAlias has
   // the bits of its aliasee.
   if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
-    if (!GA->mayBeOverridden())
+    if (!GA->isInterposable())
       computeKnownBits(GA->getAliasee(), KnownZero, KnownOne, Depth + 1, Q);
     return;
   }
 
   if (Operator *I = dyn_cast<Operator>(V))
     computeKnownBitsFromOperator(I, KnownZero, KnownOne, Depth, Q);
 
   // Aligned pointers have trailing zeros - refine KnownZero set
if (GEPOperator *GEP = dyn_cast<GEPOperator>(Ptr)) {
 
       ByteOffset += GEPOffset;
 
       Ptr = GEP->getPointerOperand();
     } else if (Operator::getOpcode(Ptr) == Instruction::BitCast ||
                Operator::getOpcode(Ptr) == Instruction::AddrSpaceCast) {
       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 {
       break;
     }
   }
   Offset = ByteOffset.getSExtValue();
   return Ptr;
if (!V->getType()->isPointerTy())
     return V;
   for (unsigned Count = 0; MaxLookup == 0 || Count < MaxLookup; ++Count) {
     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
       V = GEP->getPointerOperand();
     } else if (Operator::getOpcode(V) == Instruction::BitCast ||
                Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
       V = cast<Operator>(V)->getOperand(0);
     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
-      if (GA->mayBeOverridden())
+      if (GA->isInterposable())
         return V;
       V = GA->getAliasee();
     } else {
       // See if InstructionSimplify knows any relevant tricks.
       if (Instruction *I = dyn_cast<Instruction>(V))
         // TODO: Acquire a DominatorTree and AssumptionCache and use them.
         if (Value *Simplified = SimplifyInstruction(I, DL, nullptr)) {
           V = Simplified;

llvm/trunk/lib/IR/Value.cpp

if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
           return V;
         break;
       }
       V = GEP->getPointerOperand();
     } else if (Operator::getOpcode(V) == Instruction::BitCast ||
                Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
       V = cast<Operator>(V)->getOperand(0);
     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
-      if (StripKind == PSK_ZeroIndices || GA->mayBeOverridden())
+      if (StripKind == PSK_ZeroIndices || GA->isInterposable())
         return V;
       V = GA->getAliasee();
     } else {
       return V;
     }
     assert(V->getType()->isPointerTy() && "Unexpected operand type!");
   } while (Visited.insert(V).second);
 

llvm/trunk/lib/IR/Verifier.cpp

void Verifier::visitAliaseeSubExpr(SmallPtrSetImpl<const GlobalAlias*> &Visited,
                                    const GlobalAlias &GA, const Constant &C) {
   if (const auto *GV = dyn_cast<GlobalValue>(&C)) {
     Assert(!GV->isDeclarationForLinker(), "Alias must point to a definition",
            &GA);
 
     if (const auto *GA2 = dyn_cast<GlobalAlias>(GV)) {
       Assert(Visited.insert(GA2).second, "Aliases cannot form a cycle", &GA);
 
-      Assert(!GA2->mayBeOverridden(), "Alias cannot point to a weak alias",
+      Assert(!GA2->isInterposable(), "Alias cannot point to an interposable alias",
              &GA);
     } else {
       // Only continue verifying subexpressions of GlobalAliases.
       // Do not recurse into global initializers.
       return;
     }
   }
 

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

bool DAE::RemoveDeadArgumentsFromCallers(Function &Fn)
   // semantics. In the below example, the dead load from %p may not have been
   // eliminated from the linker-chosen copy of f, so replacing %p with undef
   // in callers may introduce undefined behavior.
   //
   // define linkonce_odr void @f(i32* %p) {
   //   %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
   // fragile (variadic) ones which we can improve here.
   if (Fn.hasLocalLinkage() && !Fn.getFunctionType()->isVarArg())
     return false;
 
   // Don't touch naked functions. The assembly might be using an argument, or

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

 
 static MemoryAccessKind checkFunctionMemoryAccess(Function &F, AAResults &AAR,
                                                   const SCCNodeSet &SCCNodes) {
   FunctionModRefBehavior MRB = AAR.getModRefBehavior(&F);
   if (MRB == FMRB_DoesNotAccessMemory)
     // 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;
 
     // Conservatively assume it writes to memory.
     return MAK_MayWrite;
   }
 
   // Scan the function body for instructions that may read or write memory.
struct ArgumentUsesTracker : public CaptureTracker {
   bool captured(const Use *U) override {
     CallSite CS(U->getUser());
     if (!CS.getInstruction()) {
       Captured = true;
       return true;
     }
 
     Function *F = CS.getCalledFunction();
-    if (!F || F->isDeclaration() || F->mayBeOverridden() ||
-        !SCCNodes.count(F)) {
+    if (!F || !F->hasExactDefinition() || !SCCNodes.count(F)) {
       Captured = true;
       return true;
     }
 
     // Note: the callee and the two successor blocks *follow* the argument
     // operands.  This means there is no need to adjust UseIndex to account for
     // these.
 
static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) {
   ArgumentGraph AG;
 
   AttrBuilder B;
   B.addAttribute(Attribute::NoCapture);
 
   // 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
     // a value can't capture arguments. Don't analyze them.
     if (F->onlyReadsMemory() && F->doesNotThrow() &&
         F->getReturnType()->isVoidTy()) {
       for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
            ++A) {

 static bool addNoAliasAttrs(const SCCNodeSet &SCCNodes) {
   // Check each function in turn, determining which functions return noalias
   // pointers.
   for (Function *F : SCCNodes) {
     // Already noalias.
     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
     // pointer types.
     if (!F->getReturnType()->isPointerTy())
       continue;
 
     if (!isFunctionMallocLike(F, SCCNodes))
static bool addNonNullAttrs(const SCCNodeSet &SCCNodes,
   // Check each function in turn, determining which functions return nonnull
   // pointers.
   for (Function *F : SCCNodes) {
     // Already nonnull.
     if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex,
                                         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
     // pointer types.
     if (!F->getReturnType()->isPointerTy())
       continue;
 
     bool Speculative = false;

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

if (!J->hasName() && !J->isDeclaration() && !J->hasLocalLinkage())
       J->setLinkage(GlobalValue::InternalLinkage);
 
     if (deleteIfDead(*J)) {
       Changed = true;
       continue;
     }
 
     // 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();
     GlobalValue *Target = dyn_cast<GlobalValue>(Aliasee->stripPointerCasts());
     // We can't trivially replace the alias with the aliasee if the aliasee is
     // non-trivial in some way.
     // TODO: Try to handle non-zero GEPs of local aliasees.
     if (!Target)

llvm/trunk/lib/Transforms/IPO/IPConstantPropagation.cpp

 //
 // Additionally if a function always returns one of its arguments directly,
 // callers will be updated to use the value they pass in directly instead of
 // using the return value.
 bool IPCP::PropagateConstantReturn(Function &F) {
   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.
   SmallVector<Value *,4> RetVals;
   StructType *STy = dyn_cast<StructType>(F.getReturnType());
   if (STy)
     for (unsigned i = 0, e = STy->getNumElements(); i < e; ++i) 
       RetVals.push_back(UndefValue::get(STy->getElementType(i)));

llvm/trunk/lib/Transforms/IPO/MergeFunctions.cpp

do {
 
     // Insert only strong functions and merge them. Strong function merging
     // always deletes one of them.
     for (std::vector<WeakVH>::iterator I = Worklist.begin(),
            E = Worklist.end(); I != E; ++I) {
       if (!*I) continue;
       Function *F = cast<Function>(*I);
       if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() &&
-          !F->mayBeOverridden()) {
+          !F->isInterposable()) {
         Changed |= insert(F);
       }
     }
 
     // Insert only weak functions and merge them. By doing these second we
     // create thunks to the strong function when possible. When two weak
     // functions are identical, we create a new strong function with two weak
     // weak thunks to it which are identical but not mergable.
     for (std::vector<WeakVH>::iterator I = Worklist.begin(),
            E = Worklist.end(); I != E; ++I) {
       if (!*I) continue;
       Function *F = cast<Function>(*I);
       if (!F->isDeclaration() && !F->hasAvailableExternallyLinkage() &&
-          F->mayBeOverridden()) {
+          F->isInterposable()) {
         Changed |= insert(F);
       }
     }
     DEBUG(dbgs() << "size of FnTree: " << FnTree.size() << '\n');
   } while (!Deferred.empty());
 
   FnTree.clear();
   GlobalNumbers.clear();
else if (SrcTy->isPointerTy() && DestTy->isIntegerTy())
     return Builder.CreatePtrToInt(V, DestTy);
   else
     return Builder.CreateBitCast(V, DestTy);
 }
 
 // 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);
   }
 
   // If G was internal then we may have replaced all uses of G with F. If so,
   // stop here and delete G. There's no need for a thunk.
   if (G->hasLocalLinkage() && G->use_empty()) {
     G->eraseFromParent();
void MergeFunctions::writeAlias(Function *F, Function *G) {
   G->eraseFromParent();
 
   DEBUG(dbgs() << "writeAlias: " << GA->getName() << '\n');
   ++NumAliasesWritten;
 }
 
 // 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(), "",
                                    F->getParent());
     H->copyAttributesFrom(F);
     H->takeName(F);
     removeUsers(F);
     F->replaceAllUsesWith(H);
bool MergeFunctions::insert(Function *NewFunction) {
   }
 
   // Impose a total order (by name) on the replacement of functions. This is
   // important when operating on more than one module independently to prevent
   // cycles of thunks calling each other when the modules are linked together.
   //
   // 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();
       replaceFunctionInTree(*Result.first, NewFunction);
       NewFunction = F;
       assert(OldF.getFunc() != F && "Must have swapped the functions.");
     }
 
   // 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');
 
   Function *DeleteF = NewFunction;
   mergeTwoFunctions(OldF.getFunc(), DeleteF);
   return true;
 }

llvm/trunk/lib/Transforms/IPO/PruneEH.cpp

bool PruneEH::runOnSCC(CallGraphSCC &SCC) {
   //
   bool SCCMightUnwind = false, SCCMightReturn = false;
   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); 
        (!SCCMightUnwind || !SCCMightReturn) && I != E; ++I) {
     Function *F = (*I)->getFunction();
     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 {
       bool CheckUnwind = !SCCMightUnwind && !F->doesNotThrow();
       bool CheckReturn = !SCCMightReturn && !F->doesNotReturn();
       // Determine if we should scan for InlineAsm in a naked function as it
       // is the only way to return without a ReturnInst.  Only do this for
       // no-inline functions as functions which may be inlined cannot

llvm/trunk/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

do {
 
     if (PHINode *PN = dyn_cast<PHINode>(P)) {
       for (Value *IncValue : PN->incoming_values())
         Worklist.push_back(IncValue);
       continue;
     }
 
     if (GlobalAlias *GA = dyn_cast<GlobalAlias>(P)) {
-      if (GA->mayBeOverridden())
+      if (!GA->isInterposable())
         return false;
       Worklist.push_back(GA->getAliasee());
       continue;
     }
 
     // If we know how big this object is, and it is less than MaxSize, continue
     // searching. Otherwise, return false.
     if (AllocaInst *AI = dyn_cast<AllocaInst>(P)) {

llvm/trunk/lib/Transforms/ObjCARC/ObjCARCAPElim.cpp

 void ObjCARCAPElim::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesCFG();
 }
 
 /// Interprocedurally determine if calls made by the given call site can
 /// 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)
         if (ImmutableCallSite JCS = ImmutableCallSite(&I))
           // This recursion depth limit is arbitrary. It's just great
           // enough to cover known interesting testcases.
           if (Depth < 3 &&
               !JCS.onlyReadsMemory() &&

llvm/trunk/lib/Transforms/ObjCARC/ObjCARCContract.cpp

for (;;) {
 
       // If Arg is a no-op casted pointer, strip one level of casts and iterate.
       if (const BitCastInst *BI = dyn_cast<BitCastInst>(Arg))
         Arg = BI->getOperand(0);
       else if (isa<GEPOperator>(Arg) &&
                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;
     }
   }
 
   // If this function has no escaping allocas or suspicious vararg usage,
   // objc_storeStrong calls can be marked with the "tail" keyword.

llvm/trunk/lib/Transforms/Scalar/SCCP.cpp

bool IPSCCP::runOnModule(Module &M) {
 
   // Loop over all functions, marking arguments to those with their addresses
   // taken or that are external as overdefined.
   //
   for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
     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
     // arguments and return value aggressively, and can assume it is not called
     // unless we see evidence to the contrary.
     if (F->hasLocalLinkage()) {
       if (AddressIsTaken(&*F))
         AddressTakenFunctions.insert(&*F);

llvm/trunk/lib/Transforms/Scalar/SROA.cpp

if (Ptr->getType()->isIntegerTy(8)) {
       Int8Ptr = Ptr;
       Int8PtrOffset = Offset;
     }
 
     // Peel off a layer of the pointer and update the offset appropriately.
     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 {
       break;
     }
     assert(Ptr->getType()->isPointerTy() && "Unexpected operand type!");
   } while (Visited.insert(Ptr).second);
 

llvm/trunk/lib/Transforms/Utils/Evaluator.cpp

if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
         }
 
         DEBUG(dbgs() << "Unknown intrinsic. Can not evaluate.\n");
         return false;
       }
 
       // 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.
       }
 
       SmallVector<Constant*, 8> Formals;
       for (User::op_iterator i = CS.arg_begin(), e = CS.arg_end(); i != e; ++i)
         Formals.push_back(getVal(*i));
 

llvm/trunk/test/Analysis/GlobalsModRef/comdat-ipo.ll

+; RUN: opt < %s -basicaa -globals-aa -gvn -S | FileCheck %s
+
+; See PR26774
+
+@X = internal global i32 4
+
+define i32 @test(i32* %P) {
+; CHECK:      @test
+; CHECK-NEXT: store i32 12, i32* @X
+; CHECK-NEXT: call void @doesnotmodX()
+; CHECK-NEXT:  %V = load i32, i32* @X
+; CHECK-NEXT:  ret i32 %V
+  store i32 12, i32* @X
+  call void @doesnotmodX( )
+  %V = load i32, i32* @X
+  ret i32 %V
+}
+
+define linkonce_odr void @doesnotmodX() {
+  ret void
+}

llvm/trunk/test/Transforms/FunctionAttrs/comdat-ipo.ll

+; RUN: opt < %s -functionattrs -S | FileCheck %s
+
+; See PR26774
+
+; CHECK-LABEL: define void @bar(i8* readonly) {
+define void @bar(i8* readonly) {
+  call void @foo(i8* %0)
+  ret void
+}
+
+
+; CHECK-LABEL: define linkonce_odr void @foo(i8* readonly) {
+define linkonce_odr void @foo(i8* readonly) {
+  call void @bar(i8* %0)
+  ret void
+}

llvm/trunk/test/Transforms/IPConstantProp/comdat-ipo.ll

+; RUN: opt < %s -ipconstprop -S | FileCheck %s
+
+; See PR26774
+
+define i32 @baz() {
+  ret i32 10
+}
+
+; We can const-prop @baz's return value *into* @foo, but cannot
+; constprop @foo's return value into bar.
+
+define linkonce_odr i32 @foo() {
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:  %val = call i32 @baz()
+; CHECK-NEXT:  ret i32 10
+
+  %val = call i32 @baz()
+  ret i32 %val
+}
+
+define i32 @bar() {
+; CHECK-LABEL: @bar(
+; CHECK-NEXT:  %val = call i32 @foo()
+; CHECK-NEXT:  ret i32 %val
+
+  %val = call i32 @foo()
+  ret i32 %val
+}

llvm/trunk/test/Transforms/Inline/comdat-ipo.ll

+; RUN: opt -inline -S < %s | FileCheck %s
+
+define i32 @caller() {
+; CHECK-LABEL: @caller(
+; CHECK-NEXT:  %val2 = call i32 @linkonce_callee(i32 42)
+; CHECK-NEXT:  ret i32 %val2
+
+  %val = call i32 @odr_callee()
+  %val2 = call i32 @linkonce_callee(i32 %val);
+  ret i32 %val2
+}
+
+define linkonce_odr i32 @odr_callee() {
+  ret i32 42
+}
+
+define linkonce i32 @linkonce_callee(i32 %val) {
+  ret i32 %val
+}

llvm/trunk/test/Transforms/ObjCARC/comdat-ipo.ll

+; RUN: opt -S -objc-arc-apelim < %s | FileCheck %s
+
+; See PR26774
+
[e-mail]_ctors = appending global [2 x { i32, void ()* }] [{ i32, void ()* } { i32 65535, void ()* @_GLOBAL__I_x }, { i32, void ()* } { i32 65535, void ()* @_GLOBAL__I_y }]
+
+@x = global i32 0
+
+declare i32 @bar() nounwind
+
+define linkonce_odr i32 @foo() nounwind {
+entry:
+  ret i32 5
+}
+
+define internal void @__cxx_global_var_init() {
+entry:
+  %call = call i32 @foo()
+  store i32 %call, i32* @x, align 4
+  ret void
+}
+
+define internal void @__dxx_global_var_init() {
+entry:
+  %call = call i32 @bar()
+  store i32 %call, i32* @x, align 4
+  ret void
+}
+
+; CHECK-LABEL: define internal void @_GLOBAL__I_x() {
+define internal void @_GLOBAL__I_x() {
+entry:
+; CHECK:  call i8* @objc_autoreleasePoolPush()
+; CHECK-NEXT:  call void @__cxx_global_var_init()
+; CHECK-NEXT:  call void @objc_autoreleasePoolPop(i8* %0)
+; CHECK-NEXT:  ret void
+
+  %0 = call i8* @objc_autoreleasePoolPush() nounwind
+  call void @__cxx_global_var_init()
+  call void @objc_autoreleasePoolPop(i8* %0) nounwind
+  ret void
+}
+
+define internal void @_GLOBAL__I_y() {
+entry:
+  %0 = call i8* @objc_autoreleasePoolPush() nounwind
+  call void @__dxx_global_var_init()
+  call void @objc_autoreleasePoolPop(i8* %0) nounwind
+  ret void
+}
+
+declare i8* @objc_autoreleasePoolPush()
+declare void @objc_autoreleasePoolPop(i8*)

llvm/trunk/test/Transforms/SCCP/comdat-ipo.ll

+; RUN: opt < %s -ipsccp -S | FileCheck %s
+
+; See PR26774
+
+define i32 @baz() {
+  ret i32 10
+}
+
+; We can const-prop @baz's return value *into* @foo, but cannot
+; constprop @foo's return value into bar.
+
+define linkonce_odr i32 @foo() {
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:  %val = call i32 @baz()
+; CHECK-NEXT:  ret i32 10
+
+  %val = call i32 @baz()
+  ret i32 %val
+}
+
+define i32 @bar() {
+; CHECK-LABEL: @bar(
+; CHECK-NEXT:  %val = call i32 @foo()
+; CHECK-NEXT:  ret i32 %val
+
+  %val = call i32 @foo()
+  ret i32 %val
+}

llvm/trunk/test/Verifier/alias.ll

 ; CHECK-NEXT: i32* @test2_a
 ; CHECK-NEXT: Aliases cannot form a cycle
 ; CHECK-NEXT: i32* @test2_b
 
 
 @test3_a = global i32 42
 @test3_b = weak alias i32, i32* @test3_a
 @test3_c = alias i32, i32* @test3_b
-; CHECK: Alias cannot point to a weak alias
+; CHECK: Alias cannot point to an interposable alias
 ; CHECK-NEXT: i32* @test3_c