[GlobalOpt] Don't replace alias with aliasee if either alias/aliasee may be preemptible

[MaskRay]

Summary

Generalize D99629 for ELF. A default visibility non-local symbol is preemptible
in a -shared link. isInterposable is an insufficient condition.

Moreover, a non-preemptible alias may be referenced in a sub constant expression
which intends to lower to a PC-relative relocation. Replacing the alias with a
preemptible aliasee may introduce a linker error.

Respect dso_preemptable and suppress optimization to fix the abose issues. With
the change, alias = 345 will not be rewritten to use aliasee in a -fpic
compile.

int aliasee;
extern int alias __attribute__((alias("aliasee"), visibility("hidden")));
void foo() { alias = 345; } // intended to access the local copy

While here, refine the condition for the alias as well.

For some binary formats like COFF, isInterposable is a sufficient condition.
But I think canonicalization for the changed case has little advantage, so I
don't bother to add the Triple(M.getTargetTriple()).isOSBinFormatELF() or
getPICLevel/getPIELevel complexity.

For instrumentations, it's recommended not to create aliases that refer to
globals that have a weak linkage or is preemptible. However, the following is
supported and the IR needs to handle such cases.

int aliasee __attribute__((weak));
extern int alias __attribute__((alias("aliasee")));

There are other places where GlobalAlias isInterposable usage may need to be
fixed.

[MaskRay]

simplify

[efriedma]

This seems awfully confusing, and almost completely undocumented in LangRef.

If I'm understanding correctly, when you have an alias that refers to a global, the alias doesn't refer to a global symbol. It instead refers to the content of the global, as emitted into the object file. So resolving an alias that refers to a symbol that has weak linkage, or default visibility, can have weird effects: the linker might end up resolving the symbol differently.

So I guess I have two questions:

1. If we have a definition that isn't weak or interposable, but has default linkage, would it make sense to teach the backend to use an alias to refer to the global? So we don't have to worry about it going through the PLT or whatever. Maybe this would explode somehow?
2. Can we forbid aliases that refer to globals that are interposable, or use weak linkage? In theory, this prohibition doesn't cause any loss of generality in IR: we can turn a weak definition into an alias pointing to an internal definition, which should be essentially equivalent.

I'm not too concerned about high-quality optimizations for aliases. I'm mostly just concerned that it isn't clear what optimizations are legal.

[aeubanks]

+1, having all of this actually documented would be great
I'm still very confused about alias semantics

[MaskRay]

Add a C example this patch will fix.

Update LangRef.

[MaskRay]

remove a stale comment.

[rnk]

How does the new code handle the weak linkages? Can strong symbol definitions from native object files prevail over weak alias definitions in a partial LTO situation?

[MaskRay]

Check both !GlobalValue::isInterposableLinkage(GV.getLinkage()) and dso_local.

(Spot by rnk): The previous diff might incorrectly optimize a WeakAny alias, which was wrong since the alias might be replaced with another in the same linked unit.

[efriedma]

Do we need to fix other places? I tried grepping for GlobalAlias, and at least BasicAliasAnalysis.cpp and MemoryBuiltins.cpp and StackSafetyAnalysis.cpp contain similar isInterposable() checks.

In D107249#2919094, @efriedma wrote:

2. Can we forbid aliases that refer to globals that are interposable, or use weak linkage? In theory, this prohibition doesn't cause any loss of generality in IR: we can turn a weak definition into an alias pointing to an internal definition, which should be essentially equivalent.

Any comment on this?

[MaskRay]

In D107249#3285600, @efriedma wrote:

Do we need to fix other places? I tried grepping for GlobalAlias, and at least BasicAliasAnalysis.cpp and MemoryBuiltins.cpp and StackSafetyAnalysis.cpp contain similar isInterposable() checks.

Maybe. Perhaps cross that bridge when we come to it.

In D107249#2919094, @efriedma wrote:

2. Can we forbid aliases that refer to globals that are interposable, or use weak linkage? In theory, this prohibition doesn't cause any loss of generality in IR: we can turn a weak definition into an alias pointing to an internal definition, which should be essentially equivalent.

Any comment on this?

We cannot reject such aliases. GCC supports:

int aliasee __attribute__((weak));
extern int alias __attribute__((alias("aliasee")));

Perhaps LLVM's instrumentations are better of not creating such aliases, but the IR needs to be handled.

[rnk]

lgtm

llvm/lib/Transforms/IPO/GlobalOpt.cpp

2258

nit: this captures nothing, right? You can drop the &.

[MaskRay]

fic comment and remove unneeded & capture

[aeubanks]

Hmm I'm seeing functions being visited a bunch of times during the simplification pipeline in the big module I'm looking at.

[MaskRay]

@zatrazz https://sourceware.org/git/?p=glibc.git;a=shortlog;h=refs/heads/azanella/clang the bootstrap issue you saw can be fixed by applying this patch (but it was reverted for a timeout issue).

In elf/rtld.c,

// Without the patch, Clang may convert _rtld_local access to the unexpected _rtld_global access, leading to GOT indirection
extern struct rtld_global _rtld_local
    __attribute__ ((alias ("_rtld_global"), visibility ("hidden")));

In bootstrap_map.l_addr = elf_machine_load_address ();,
using Clang without this patch, the statement compiles to use R_X86_64_REX_GOTPCRELX _rtld_global-0x4, which may load a zero address (GOT relocations haven't been applied yet)

With this patch or with GCC, the PC-relative R_X86_64_PC32 _rtld_local-0x4 is used, which works.

[aeubanks]

Sorry, still trying to figure out why this causes compile times to blow up in some cases. In the case I was looking at it went from ~150s to ~5700s.

[aeubanks]

the module I'm looking at has a huge RefSCC (>20000 SCCs)

this change is somehow causing us to hit the case where we optimize the RefSCC, cause a function in one of the contained SCCs to now be in a child SCC (perhaps because a call/reference to it was eliminated in another function), bail out from the current RefSCC to go and optimize the new child RefSCC/SCC (since the pipeline is bottom-up), then revisit the original now slightly smaller RefSCC, and repeat
commenting out https://github.com/llvm/llvm-project/blob/74cf8575f74ab6b0d9641e0e3acf3e9328a5e365/llvm/lib/Analysis/CGSCCPassManager.cpp#L233 (and the corresponding assert below) fixes the issue, although I'm not sure that's the proper fix

I looked at the RefSCC visit order without this patch and it actually does something similar, but nowhere near as bad as with this patch. I still haven't figured out which pass is causing the call graph to move around, investigating that

[aeubanks]

D121953 should fix the compile time issues, I'll reland this after that goes in

llvm/docs/LangRef.rst

 
 * No alias in the expression can be weak as the possibility of the
   intermediate alias being overridden cannot be represented in an
   object file.
 
 * No global value in the expression can be a declaration, since that
   would require a relocation, which is not possible.
 
+* If either the alias or the aliasee may be replaced by a symbol outside the
+  module at link time or runtime, any optimization cannot replace the alias with
+  the aliasee, since the behavior may be different. The alias may be used as a
+  name guaranteed to point to the content in the current module.
+
 .. _langref_ifunc:
 
 IFuncs
 -------
 
 IFuncs, like as aliases, don't create any new data or func. They are just a new
 symbol that dynamic linker resolves at runtime by calling a resolver function.
 

llvm/lib/Transforms/IPO/GlobalOpt.cpp

 OptimizeGlobalAliases(Module &M,
                       SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) {
   bool Changed = false;
   LLVMUsed Used(M);
 
   for (GlobalValue *GV : Used.used())
     Used.compilerUsedErase(GV);
 
+  // Return whether GV is explicitly or implicitly dso_local and not replaceable
+  // by another definition in the current linkage unit.
+  auto IsModuleLocal = [](GlobalValue &GV) {
+    return !GlobalValue::isInterposableLinkage(GV.getLinkage()) &&
+           (GV.isDSOLocal() || GV.isImplicitDSOLocal());
+  };
+
   for (GlobalAlias &J : llvm::make_early_inc_range(M.aliases())) {
     // Aliases without names cannot be referenced outside this module.
     if (!J.hasName() && !J.isDeclaration() && !J.hasLocalLinkage())
       J.setLinkage(GlobalValue::InternalLinkage);
 
     if (deleteIfDead(J, NotDiscardableComdats)) {
       Changed = true;
       continue;
     }
 
     // If the alias can change at link time, nothing can be done - bail out.
-    if (J.isInterposable())
+    if (!IsModuleLocal(J))
       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. We also can't replace the alias with the aliasee
-    // if the aliasee is interposable because aliases point to the local
-    // definition.
+    // if the aliasee may be preemptible at runtime. On ELF, a non-preemptible
+    // alias can be used to access the definition as if preemption did not
+    // happen.
     // TODO: Try to handle non-zero GEPs of local aliasees.
-    if (!Target || Target->isInterposable())
+    if (!Target || !IsModuleLocal(*Target))
       continue;
+
     Target->removeDeadConstantUsers();
 
     // Make all users of the alias use the aliasee instead.
     bool RenameTarget;
     if (!hasUsesToReplace(J, Used, RenameTarget))
       continue;
 
     J.replaceAllUsesWith(ConstantExpr::getBitCast(Aliasee, J.getType()));

llvm/test/Transforms/GlobalOpt/2009-02-15-ResolveAlias.ll

 ; RUN: opt < %s -passes=globalopt -S | FileCheck %s
 
 define internal void @f() {
 ; CHECK-NOT: @f(
-; CHECK: define void @a
+; CHECK: define dso_local void @a
   ret void
 }
 
-@a = alias void (), void ()* @f
+@a = dso_local alias void (), void ()* @f
 
-define void @g() {
+define hidden void @g() {
   call void() @a()
   ret void
 }
 
 @b = internal alias  void (),  void ()* @g
 ; CHECK-NOT: @b
 
 define void @h() {
   call void() @b()
 ; CHECK: call void @g
   ret void
 }
 

llvm/test/Transforms/GlobalOpt/alias-resolve.ll

 ; RUN: opt < %s -passes=globalopt -S | FileCheck %s
 
 @foo1 = alias void (), void ()* @foo2
+;; foo2 is dso_local and non-weak. Resolved.
 ; CHECK: @foo1 = alias void (), void ()* @bar2
 
-@foo2 = alias void(), void()* @bar1
-; CHECK: @foo2 = alias void (), void ()* @bar2
-
-@bar1  = alias void (), void ()* @bar2
-; CHECK: @bar1 = alias void (), void ()* @bar2
-
-@weak1 = weak alias void (), void ()* @bar2
-; CHECK: @weak1 = weak alias void (), void ()* @bar2
+@foo2 = dso_local alias void(), void()* @bar1
+;; bar1 is dso_local and non-weak. Resolved.
+; CHECK: @foo2 = dso_local alias void (), void ()* @bar2
+
+@bar1  = dso_local alias void (), void ()* @bar2
+; CHECK: @bar1 = dso_local alias void (), void ()* @bar2
+
+@weak1 = weak dso_local alias void (), void ()* @bar2
+;; weak1 may be replaced with another definition in the linkage unit. Not resolved.
+; CHECK: @weak1 = weak dso_local alias void (), void ()* @bar2
 
 @bar4 = private unnamed_addr constant [2 x i8*] zeroinitializer
 @foo4 = weak_odr unnamed_addr alias i8*, getelementptr inbounds ([2 x i8*], [2 x i8*]* @bar4, i32 0, i32 1)
 ; CHECK: @foo4 = weak_odr unnamed_addr alias i8*, getelementptr inbounds ([2 x i8*], [2 x i8*]* @bar4, i32 0, i32 1)
 
 @priva  = private alias void (), void ()* @bar5
 ; CHECK: @priva = private alias void (), void ()* @bar5
 
-define void @bar2() {
+define dso_local void @bar2() {
   ret void
 }
-; CHECK: define void @bar2()
+; CHECK: define dso_local void @bar2()
 
 define weak void @bar5() {
   ret void
 }
 ; CHECK: define weak void @bar5()
 
 define void @baz() {
 entry:
          call void @foo1()
-; CHECK: call void @bar2()
+;; foo1 is dso_preemptable. Not resolved.
+; CHECK: call void @foo1()
 
          call void @foo2()
+;; foo2 is dso_local and non-weak. Resolved.
 ; CHECK: call void @bar2()
 
          call void @bar1()
+;; bar1 is dso_local and non-weak. Resolved.
 ; CHECK: call void @bar2()
 
          call void @weak1()
+;; weak1 is weak. Not resolved.
 ; CHECK: call void @weak1()
 
          call void @priva()
+;; priva has a local linkage. Resolved.
 ; CHECK: call void @priva()
 
          ret void
 }
 
-@foo3 = alias void (), void ()* @bar3
+@foo3 = dso_local alias void (), void ()* @bar3
 ; CHECK-NOT: bar3
 
 define internal void @bar3() {
   ret void
 }
-;CHECK: define void @foo3
+;CHECK: define dso_local void @foo3

llvm/test/Transforms/GlobalOpt/alias-used-address-space.ll

 ; RUN: opt -S -passes=globalopt < %s | FileCheck %s
 
 target datalayout = "p:32:32:32-p1:16:16:16"
 
-@c = addrspace(1) global i8 42
+@c = hidden addrspace(1) global i8 42
 
 @i = internal addrspace(1) global i8 42
 
 ; CHECK: @ia = internal addrspace(1) global i8 42
 @ia = internal alias i8, i8 addrspace(1)* @i
 
 @llvm.used = appending global [1 x i8*] [i8* addrspacecast (i8 addrspace(1)* @ca to i8*)], section "llvm.metadata"
 ; CHECK-DAG: @llvm.used = appending global [1 x i8*] [i8* addrspacecast (i8 addrspace(1)* @ca to i8*)], section "llvm.metadata"

llvm/test/Transforms/GlobalOpt/alias-used.ll

 ; RUN: opt < %s -passes=globalopt -S | FileCheck %s
 
-@c = global i8 42
+@c = dso_local global i8 42
 
 @i = internal global i8 42
 ; CHECK: @ia = internal global i8 42
 @ia = internal alias i8, i8* @i
 
 @llvm.used = appending global [3 x i8*] [i8* bitcast (void ()* @fa to i8*), i8* bitcast (void ()* @f to i8*), i8* @ca], section "llvm.metadata"
 ; CHECK-DAG: @llvm.used = appending global [3 x i8*] [i8* @ca, i8* bitcast (void ()* @f to i8*), i8* bitcast (void ()* @fa to i8*)], section "llvm.metadata"
 

 ; CHECK-NOT: @fa2
 
 @fa3 = internal alias void (), void ()* @f
 ; CHECK: @fa3
 
 @ca = internal alias i8, i8* @c
 ; CHECK: @ca = internal alias i8, i8* @c
 
-define void @f() {
+define hidden void @f() {
   ret void
 }
 
 define i8* @g() {
   ret i8* bitcast (void ()* @fa to i8*);
 }
 
 define i8* @g2() {