Change how globalopt handles aliases in llvm.used.

Instead of a custom implementation of replaceAllUsesWith, we just call
replaceAllUsesWith and recreate llvm.used and llvm.compiler-used.

This change is particularity interesting because it makes llvm see
through what clang is doing with static used functions in extern "C"
contexts. With this change, running clang -O2 in

extern "C" {
  __attribute__((used)) static void foo() {}
}

produces

@llvm.used = appending global [1 x i8*] [i8* bitcast (void ()* @foo to
i8*)], section "llvm.metadata"
define internal void @foo() #0 {
entry:
  ret void
}

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@183756 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 156 insertions, 100 deletions

diff --git a/lib/Transforms/IPO/GlobalOpt.cpp b/lib/Transforms/IPO/GlobalOpt.cpp
index 4a9cb27b03..72ba250f47 100644
--- a/lib/Transforms/IPO/GlobalOpt.cpp
+++ b/lib/Transforms/IPO/GlobalOpt.cpp
@@ -3041,107 +3041,168 @@ bool GlobalOpt::OptimizeGlobalCtorsList(GlobalVariable *&GCL) {
   return true;
 }
 
-static Value::use_iterator getFirst(Value *V, SmallPtrSet<Use*, 8> &Tried) {
-  for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I) {
-    Use *U = &I.getUse();
-    if (Tried.count(U))
-      continue;
-
-    User *Usr = *I;
-    GlobalVariable *GV = dyn_cast<GlobalVariable>(Usr);
-    if (!GV || !GV->hasName()) {
-      Tried.insert(U);
-      return I;
-    }
+/// \brief Given "llvm.used" or "llvm.compiler_used" as a global name, collect
+/// the initializer elements of that global in Set and return the global itself.
+static GlobalVariable *
+collectUsedGlobalVariables(const Module &M, const char *Name,
+                           SmallPtrSet<GlobalValue *, 8> &Set) {
+  GlobalVariable *GV = M.getGlobalVariable(Name);
+  if (!GV || !GV->hasInitializer())
+    return GV;
 
-    StringRef Name = GV->getName();
-    if (Name != "llvm.used" && Name != "llvm.compiler_used") {
-      Tried.insert(U);
-      return I;
-    }
+  const ConstantArray *Init = cast<ConstantArray>(GV->getInitializer());
+  for (unsigned I = 0, E = Init->getNumOperands(); I != E; ++I) {
+    Value *Op = Init->getOperand(I);
+    GlobalValue *G = cast<GlobalValue>(Op->stripPointerCastsNoFollowAliases());
+    Set.insert(G);
   }
-  return V->use_end();
+  return GV;
 }
 
-static bool replaceAllNonLLVMUsedUsesWith(Constant *Old, Constant *New);
+static int compareNames(const void *A, const void *B) {
+  const GlobalValue *VA = *reinterpret_cast<GlobalValue* const*>(A);
+  const GlobalValue *VB = *reinterpret_cast<GlobalValue* const*>(B);
+  if (VA->getName() < VB->getName())
+    return -1;
+  if (VB->getName() < VA->getName())
+    return 1;
+  return 0;
+}
 
-static bool replaceUsesOfWithOnConstant(ConstantArray *CA, Value *From,
-                                        Value *ToV, Use *U) {
-  Constant *To = cast<Constant>(ToV);
+static void setUsedInitializer(GlobalVariable &V,
+                               SmallPtrSet<GlobalValue *, 8> Init) {
+  SmallVector<llvm::Constant *, 8> UsedArray;
+  PointerType *Int8PtrTy = Type::getInt8PtrTy(V.getContext());
 
-  SmallVector<Constant*, 8> NewOps;
-  for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) {
-    Constant *Op = CA->getOperand(i);
-    NewOps.push_back(Op == From ? To : Op);
-  }
+  for (SmallPtrSet<GlobalValue *, 8>::iterator I = Init.begin(), E = Init.end();
+       I != E; ++I) {
+    Constant *Cast = llvm::ConstantExpr::getBitCast(*I, Int8PtrTy);
+    UsedArray.push_back(Cast);
+  }
+  // Sort to get deterministic order.
+  array_pod_sort(UsedArray.begin(), UsedArray.end(), compareNames);
+  ArrayType *ATy = ArrayType::get(Int8PtrTy, UsedArray.size());
+
+  Module *M = V.getParent();
+  V.removeFromParent();
+  GlobalVariable *NV =
+      new GlobalVariable(*M, ATy, false, llvm::GlobalValue::AppendingLinkage,
+                         llvm::ConstantArray::get(ATy, UsedArray), "");
+  NV->takeName(&V);
+  NV->setSection("llvm.metadata");
+  delete &V;
+}
 
-  Constant *Replacement = ConstantArray::get(CA->getType(), NewOps);
-  assert(Replacement != CA && "CA didn't contain From!");
+namespace {
+/// \brief An easy to access representation of llvm.used and llvm.compiler_used.
+class LLVMUsed {
+  SmallPtrSet<GlobalValue *, 8> Used;
+  SmallPtrSet<GlobalValue *, 8> CompilerUsed;
+  GlobalVariable *UsedV;
+  GlobalVariable *CompilerUsedV;
 
-  bool Ret = replaceAllNonLLVMUsedUsesWith(CA, Replacement);
-  if (Replacement->use_empty())
-    Replacement->destroyConstant();
-  if (CA->use_empty())
-    CA->destroyConstant();
-  return Ret;
+public:
+  LLVMUsed(const Module &M) {
+    UsedV = collectUsedGlobalVariables(M, "llvm.used", Used);
+    CompilerUsedV =
+        collectUsedGlobalVariables(M, "llvm.compiler_used", CompilerUsed);
+  }
+  typedef SmallPtrSet<GlobalValue *, 8>::iterator iterator;
+  iterator usedBegin() { return Used.begin(); }
+  iterator usedEnd() { return Used.end(); }
+  iterator compilerUsedBegin() { return CompilerUsed.begin(); }
+  iterator compilerUsedEnd() { return CompilerUsed.end(); }
+  bool usedCount(GlobalValue *GV) const { return Used.count(GV); }
+  bool compilerUsedCount(GlobalValue *GV) const {
+    return CompilerUsed.count(GV);
+  }
+  bool usedErase(GlobalValue *GV) { return Used.erase(GV); }
+  bool compilerUsedErase(GlobalValue *GV) { return CompilerUsed.erase(GV); }
+  bool usedInsert(GlobalValue *GV) { return Used.insert(GV); }
+  bool compilerUsedInsert(GlobalValue *GV) { return CompilerUsed.insert(GV); }
+
+  void syncVariablesAndSets() {
+    if (UsedV)
+      setUsedInitializer(*UsedV, Used);
+    if (CompilerUsedV)
+      setUsedInitializer(*CompilerUsedV, CompilerUsed);
+  }
+};
 }
 
-static bool replaceUsesOfWithOnConstant(ConstantExpr *CE, Value *From,
-                                        Value *ToV, Use *U) {
-  Constant *To = cast<Constant>(ToV);
-  SmallVector<Constant*, 8> NewOps;
-  for (unsigned i = 0, e = CE->getNumOperands(); i != e; ++i) {
-    Constant *Op = CE->getOperand(i);
-    NewOps.push_back(Op == From ? To : Op);
-  }
+static bool hasUseOtherThanLLVMUsed(GlobalAlias &GA, const LLVMUsed &U) {
+  if (GA.use_empty()) // No use at all.
+    return false;
 
-  Constant *Replacement = CE->getWithOperands(NewOps);
-  assert(Replacement != CE && "CE didn't contain From!");
+  assert((!U.usedCount(&GA) || !U.compilerUsedCount(&GA)) &&
+         "We should have removed the duplicated "
+         "element from llvm.compiler_used");
+  if (!GA.hasOneUse())
+    // Strictly more than one use. So at least one is not in llvm.used and
+    // llvm.compiler_used.
+    return true;
 
-  bool Ret = replaceAllNonLLVMUsedUsesWith(CE, Replacement);
-  if (Replacement->use_empty())
-    Replacement->destroyConstant();
-  if (CE->use_empty())
-    CE->destroyConstant();
-  return Ret;
+  // Exactly one use. Check if it is in llvm.used or llvm.compiler_used.
+  return !U.usedCount(&GA) && !U.compilerUsedCount(&GA);
 }
 
-static bool replaceUsesOfWithOnConstant(Constant *C, Value *From, Value *To,
-                                        Use *U) {
-  if (ConstantArray *CA = dyn_cast<ConstantArray>(C))
-    return replaceUsesOfWithOnConstant(CA, From, To, U);
-  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
-    return replaceUsesOfWithOnConstant(CE, From, To, U);
-  C->replaceUsesOfWithOnConstant(From, To, U);
-  return true;
+static bool hasMoreThanOneUseOtherThanLLVMUsed(GlobalValue &V,
+                                               const LLVMUsed &U) {
+  unsigned N = 2;
+  assert((!U.usedCount(&V) || !U.compilerUsedCount(&V)) &&
+         "We should have removed the duplicated "
+         "element from llvm.compiler_used");
+  if (U.usedCount(&V) || U.compilerUsedCount(&V))
+    ++N;
+  return V.hasNUsesOrMore(N);
 }
 
-static bool replaceAllNonLLVMUsedUsesWith(Constant *Old, Constant *New) {
-  SmallPtrSet<Use*, 8> Tried;
-  bool Ret = false;
-  for (;;) {
-    Value::use_iterator I = getFirst(Old, Tried);
-    if (I == Old->use_end())
-      break;
-    Use &U = I.getUse();
+static bool mayHaveOtherReferences(GlobalAlias &GA, const LLVMUsed &U) {
+  if (!GA.hasLocalLinkage())
+    return true;
 
-    // Must handle Constants specially, we cannot call replaceUsesOfWith on a
-    // constant because they are uniqued.
-    if (Constant *C = dyn_cast<Constant>(U.getUser())) {
-      if (!isa<GlobalValue>(C)) {
-        Ret |= replaceUsesOfWithOnConstant(C, Old, New, &U);
-        continue;
-      }
-    }
+  return U.usedCount(&GA) || U.compilerUsedCount(&GA);
+}
 
-    U.set(New);
+static bool hasUsesToReplace(GlobalAlias &GA, LLVMUsed &U, bool &RenameTarget) {
+  RenameTarget = false;
+  bool Ret = false;
+  if (hasUseOtherThanLLVMUsed(GA, U))
     Ret = true;
-  }
-  return Ret;
+
+  // If the alias is externally visible, we may still be able to simplify it.
+  if (!mayHaveOtherReferences(GA, U))
+    return Ret;
+
+  // If the aliasee has internal linkage, give it the name and linkage
+  // of the alias, and delete the alias.  This turns:
+  //   define internal ... @f(...)
+  //   @a = alias ... @f
+  // into:
+  //   define ... @a(...)
+  Constant *Aliasee = GA.getAliasee();
+  GlobalValue *Target = cast<GlobalValue>(Aliasee->stripPointerCasts());
+  if (!Target->hasLocalLinkage())
+    return Ret;
+
+  // Do not perform the transform if multiple aliases potentially target the
+  // aliasee. This check also ensures that it is safe to replace the section
+  // and other attributes of the aliasee with those of the alias.
+  if (hasMoreThanOneUseOtherThanLLVMUsed(*Target, U))
+    return Ret;
+
+  RenameTarget = true;
+  return true;
 }
 
 bool GlobalOpt::OptimizeGlobalAliases(Module &M) {
   bool Changed = false;
+  LLVMUsed Used(M);
+
+  for (SmallPtrSet<GlobalValue *, 8>::iterator I = Used.usedBegin(),
+                                               E = Used.usedEnd();
+       I != E; ++I)
+    Used.compilerUsedErase(*I);
 
   for (Module::alias_iterator I = M.alias_begin(), E = M.alias_end();
        I != E;) {
@@ -3156,45 +3217,40 @@ bool GlobalOpt::OptimizeGlobalAliases(Module &M) {
     Constant *Aliasee = J->getAliasee();
     GlobalValue *Target = cast<GlobalValue>(Aliasee->stripPointerCasts());
     Target->removeDeadConstantUsers();
-    bool hasOneUse = Target->hasOneUse() && Aliasee->hasOneUse();
 
     // Make all users of the alias use the aliasee instead.
-    if (replaceAllNonLLVMUsedUsesWith(J, Aliasee)) {
-      ++NumAliasesResolved;
-      Changed = true;
-    }
-    if (!J->use_empty())
+    bool RenameTarget;
+    if (!hasUsesToReplace(*J, Used, RenameTarget))
       continue;
 
-    // If the alias is externally visible, we may still be able to simplify it.
-    if (!J->hasLocalLinkage()) {
-      // If the aliasee has internal linkage, give it the name and linkage
-      // of the alias, and delete the alias.  This turns:
-      //   define internal ... @f(...)
-      //   @a = alias ... @f
-      // into:
-      //   define ... @a(...)
-      if (!Target->hasLocalLinkage())
-        continue;
-
-      // Do not perform the transform if multiple aliases potentially target the
-      // aliasee. This check also ensures that it is safe to replace the section
-      // and other attributes of the aliasee with those of the alias.
-      if (!hasOneUse)
-        continue;
+    J->replaceAllUsesWith(Aliasee);
+    ++NumAliasesResolved;
+    Changed = true;
 
+    if (RenameTarget) {
       // Give the aliasee the name, linkage and other attributes of the alias.
       Target->takeName(J);
       Target->setLinkage(J->getLinkage());
       Target->GlobalValue::copyAttributesFrom(J);
+
+      if (Used.usedErase(J))
+        Used.usedInsert(Target);
+
+      if (Used.compilerUsedErase(J))
+        Used.compilerUsedInsert(Target);
     }
 
+    if (mayHaveOtherReferences(*J, Used))
+      continue;
+
     // Delete the alias.
     M.getAliasList().erase(J);
     ++NumAliasesRemoved;
     Changed = true;
   }
 
+  Used.syncVariablesAndSets();
+
   return Changed;
 }