[ConstantFolding] Look through local aliases when simplify GEPs

[aeubanks]

Summary

Only consider aliases that themselves aren't interposable and alias to
something that isn't interposable.

MSVC-style RTTI uses GEPs through local aliases for vtables.

With this patch, we can simplify the following C++ code into just one
function with a constant return value:

namespace {
        struct A {
                virtual int f() = 0;
                virtual ~A() = default;
        };
        struct B: A {
                virtual int f() override { return 41; }
                virtual ~B() = default;
        };
}

int foo() {
        std::unique_ptr<A> a = std::make_unique<B>();
        return a->f();
}

[rnk]

+@pcc who added the test and @erichkeane who adjusted the API recently

Some proir art:
https://reviews.llvm.org/rG2452d7030b84d358165f5f76c9270937b4ea1a91
https://reviews.llvm.org/D68584

llvm/lib/IR/Value.cpp

612–613

I wonder if it would be safe to power up all of the other versions of pointer stripping to look through local aliases.

[erichkeane]

So I guess I don't understand what this does differently than stripPointerCastsAndAliases? Is limiting this to local aliases that important?

[pcc]

Can you make it so that the load ends up being replaced with the loaded value, without replacing the GEP itself? That would seem to address the MSVC issue.

llvm/lib/IR/Value.cpp

612–613

I don't think we should. It wouldn't be safe to allow passes to replace @alias with @aliasee with this IR:

@alias = internal alias @aliasee
@aliasee = linkonce_odr global i32 42

We should also avoid the QoI issue (missing symbol table entry) that would result from such replacement given this IR:

@alias = internal alias @aliasee
@aliasee = private global i32 42

[aeubanks]

In D99240#2649567, @pcc wrote:

Can you make it so that the load ends up being replaced with the loaded value, without replacing the GEP itself? That would seem to address the MSVC issue.

What's the benefit of that over this approach? We'd have to potentially end up doing the same thing for stores and maybe other places.

llvm/lib/IR/Value.cpp

612–613

Why is the first transform not safe?

[aeubanks]

In D99240#2649468, @erichkeane wrote:

So I guess I don't understand what this does differently than stripPointerCastsAndAliases? Is limiting this to local aliases that important?

I initially tried using stripPointerCastsAndAliases(), but gep-alias.ll failed because it was specifically checking that we don't look through non-local aliases. The original comments in the test explain it better.

[nikic]

I would expect those internal aliases to be replaced by the aliasee in the first place -- is the problem that this happens too late?

[pcc]

In D99240#2650901, @aeubanks wrote:

In D99240#2649567, @pcc wrote:

Can you make it so that the load ends up being replaced with the loaded value, without replacing the GEP itself? That would seem to address the MSVC issue.

What's the benefit of that over this approach?

In general, the use of an alias is deliberate. We shouldn't be indiscriminately replacing them with aliasees as that may break semantics or lead to QoI issues. Instead, we should be making targeted replacements where they are known to be safe. In particular, replacing the load with the loaded value is safe because linkonce_odr (or external, etc.) on the alias guarantees that the value loaded from any copy of the aliasee is the same. So it doesn't matter whether we (a compile time) read from this translation unit's copy of the global or some other copy.

We'd have to potentially end up doing the same thing for stores and maybe other places.

Can you show an example of a beneficial transformation that would apply to stores?

llvm/lib/IR/Value.cpp

612–613

Because it would replace a reference to this object file's copy of @aliasee with a reference to the copy of @aliasee selected by the linker, and those could potentially be different (and have different addresses, which is observable).

[aeubanks]

In D99240#2650972, @nikic wrote:

I would expect those internal aliases to be replaced by the aliasee in the first place -- is the problem that this happens too late?

Which pass does this?

The original snippet had a GEP of an alias which itself is another GEP into a global.

[nikic]

In D99240#2651044, @aeubanks wrote:

In D99240#2650972, @nikic wrote:

I would expect those internal aliases to be replaced by the aliasee in the first place -- is the problem that this happens too late?

Which pass does this?

The original snippet had a GEP of an alias which itself is another GEP into a global.

At least -globalopt does that. Not sure if any other passes do.

[aeubanks]

Ah I see, https://github.com/llvm/llvm-project/blob/61a55c8812e790842799ba1de5bd81fe8afb3b16/llvm/lib/Transforms/IPO/GlobalOpt.cpp#L2953. It only works if the aliasee is a global value. Extending globalopt to handle aliasees that may be a constant expression containing a global value, rather than just a global value, would probably work as well. Either way is fine by me.

globalopt specifically deletes aliases when possible, so it seems fair to do that here as well, even if that may remove entries from the symbol table.

llvm/lib/IR/Value.cpp

612–613

It doesn't end up using the copy of @aliasee selected by the linker?

globalopt actually performs this transform:

$ cat /tmp/y.ll
@alias = internal alias i32, i32* @aliasee
@aliasee = linkonce_odr global i32 42

define i32 @foo() {
  %i = load i32, i32* @alias
  ret i32 %i
}
$ opt -passes=globalopt /tmp/y.ll -S
@aliasee = linkonce_odr local_unnamed_addr global i32 42

define i32 @foo() local_unnamed_addr {
  %i = load i32, i32* @aliasee, align 4
  ret i32 %i
}

[pcc]

In D99240#2651342, @aeubanks wrote:

Ah I see, https://github.com/llvm/llvm-project/blob/61a55c8812e790842799ba1de5bd81fe8afb3b16/llvm/lib/Transforms/IPO/GlobalOpt.cpp#L2953. It only works if the aliasee is a global value. Extending globalopt to handle aliasees that may be a constant expression containing a global value, rather than just a global value, would probably work as well. Either way is fine by me.

globalopt specifically deletes aliases when possible, so it seems fair to do that here as well, even if that may remove entries from the symbol table.

The presence of a bug in globalopt doesn't justify introducing a bug here as well.

llvm/lib/IR/Value.cpp

612–613

It doesn't end up using the copy of @aliasee selected by the linker?

No, it doesn't. @alias is specifically a reference to this object file's copy of the data defined by the @aliasee global.

globalopt actually performs this transform:

I think that's a bug then.

[nikic]

In D99240#2651342, @aeubanks wrote:

Ah I see, https://github.com/llvm/llvm-project/blob/61a55c8812e790842799ba1de5bd81fe8afb3b16/llvm/lib/Transforms/IPO/GlobalOpt.cpp#L2953. It only works if the aliasee is a global value. Extending globalopt to handle aliasees that may be a constant expression containing a global value, rather than just a global value, would probably work as well. Either way is fine by me.

Could you share (or maybe add to the test) the actual alias/gep structure you want to optimize? It would make sense to me to always replace aliases with local linkage, even if they don't directly point to a global value. For non-local (but non-interposable) linkage it may not be profitable to do this. (I guess it might not be universally profitable for local linkage either in that an expensive constant expression could be duplicated, but I think we usually assume that constant expressions are cheap.)

llvm/lib/IR/Value.cpp

612–613

Because it would replace a reference to this object file's copy of @aliasee with a reference to the copy of @aliasee selected by the linker, and those could potentially be different (and have different addresses, which is observable).

I don't think I understand the problem. Ignoring unnamed_addr, @alias and @aliasee are required to have the same address. If another copy of @aliasee is chosen by the linker, then @alias is required to point to that other copy, which is compatible with replacing uses of @alias with @aliasee in the first place.

[pcc]

llvm/lib/IR/Value.cpp

612–613

Sorry, but that's not how aliases work. An alias is just another symbol that points to the same section as the aliasee. There's nothing linking them at the object file level. So they are each independently subject to symbol resolution by the linker.

[nikic]

llvm/lib/IR/Value.cpp

612–613

This is how aliases are specified by LangRef:

Aliases that are not unnamed_addr are guaranteed to have the same address as the aliasee expression. unnamed_addr ones are only guaranteed to point to the same content.

If this doesn't match your understanding of how aliases work, please submit a patch to adjust the specification.

[aeubanks]

The (relevant part of the) code in the description after -O2 is:

@global = private unnamed_addr constant { [3 x i8*] } { [3 x i8*] [i8* bitcast (%struct.wibble* @global.1 to i8*), i8* bitcast (i32 (%struct.bar*)* @spam.12 to i8*), i8* bitcast (i8* (%struct.bar*, i32)* @blam to i8*)] }, comdat($"??_7B@?A0x8E5408E2@@6B@")

@alias = internal unnamed_addr alias i8*, getelementptr inbounds ({ [3 x i8*] }, { [3 x i8*] }* @global, i32 0, i32 0, i32 1)

define dso_local i32 @foo() local_unnamed_addr #0 personality i8* bitcast (i32 (...)* @spam to i8*) {
bb:
  %tmp = tail call noalias nonnull dereferenceable(8) i8* @"??2@YAPEAX_K@Z"(i64 8) #5, !noalias !8
  %tmp1 = bitcast i8* %tmp to %struct.bar*
  %tmp2 = getelementptr inbounds %struct.bar, %struct.bar* %tmp1, i64 0, i32 0, i32 0
  store i32 (...)** bitcast (i8** @alias to i32 (...)**), i32 (...)*** %tmp2, align 8, !tbaa !11, !noalias !8
  %tmp3 = getelementptr %struct.bar, %struct.bar* %tmp1, i64 0, i32 0
  %tmp4 = load i8* (%struct.eggs*, i32)*, i8* (%struct.eggs*, i32)** bitcast (i8** getelementptr inbounds (i8*, i8** @alias, i64 1) to i8* (%struct.eggs*, i32)**), align 16
  %tmp5 = tail call i8* %tmp4(%struct.eggs* nonnull dereferenceable(8) %tmp3, i32 1) #6
  ret i32 41
}

%tmp4's operand gets simplified to the proper function pointer entry in @global with this change.

[pcc]

llvm/lib/IR/Value.cpp

612–613

I think that's talking about prior to linker symbol resolution. The LangRef could certainly be clarified on that point though. I'll see if I can get a chance to update it.

[rnk]

To add some context to the IR fragment, in the MSVC C++ ABI, the vtable symbol (??_7...) points to the first virtual method slot in the table. If RTTI is enabled, a pointer to the RTTI data precedes the vtable, giving you this table (assuming 64-bit pointers):

• rtti data (offset -8)
• vtable symbol (??_7) -->
• virtual method 1 (offset 0)
• virtual method 2 (offset 8)
• ...

LLVM does not have a concept of globals where the symbol points to the middle of the data, so we came up with this wacky alias representation, where we have private data, and then an alias into the private data with some offset.

We considered the alternative of adding some kind of "prefix data" to the IR. In the end, we rejected it, although I forget why exactly.

In contrast, the Itanium C++ ABI has fewer vtable symbols, and the address points, the addresses that are actually installed into object vptr slots, are offset from the main vtable symbol.

[aeubanks]

only consider non-interposable aliases with non-interposable aliasees

[rnk]

I think Arthur is right, it should be safe to look through local aliases to local linkage globals. I think we can actually do this in the "for alias analysis" variant of strip pointer casts, and we should consider that.

[pcc]

In D99240#2684236, @rnk wrote:

I think Arthur is right, it should be safe to look through local aliases to local linkage globals. I think we can actually do this in the "for alias analysis" variant of strip pointer casts, and we should consider that.

Again, safe doesn't mean it's a good idea.

[aeubanks]

I'll see if I can do this just for load instructions

llvm/lib/IR/Value.cpp

612–613

We can power down

[rnk]

To add some specificity, we wouldn't want to go around ripping out all of our ??_7 vtable aliases and replacing them with references to the underlying private global. Consider:

@"??_7Foo@@6B@" = unnamed_addr alias i8*, getelementptr inbounds ({ [2 x i8*] }, { [2 x i8*] }* @0, i32 0, i32 0, i32 1)
define dso_local nonnull %struct.Foo* @"??0Foo@@QEAA@XZ"(%struct.Foo* nonnull returned align 8 dereferenceable(8) %this) unnamed_addr #0 align 2 {
entry:
  %0 = getelementptr inbounds %struct.Foo, %struct.Foo* %this, i64 0, i32 0
  store i32 (...)** bitcast (i8** @"??_7Foo@@6B@" to i32 (...)**), i32 (...)*** %0, align 8, !tbaa !3
  ret %struct.Foo* %this
}

This compiles to:

"??0Foo@@QEAA@XZ":                      # @"??0Foo@@QEAA@XZ"
# %bb.0:                                # %entry                
        movq    %rcx, %rax
        leaq    "??_7Foo@@6B@"(%rip), %rcx
        movq    %rcx, (%rax)
        retq

If you do the replacement here:

define dso_local nonnull %struct.Foo* @"??0Foo@@QEAA@XZ"(%struct.Foo* nonnull returned align 8 dereferenceable(8) %this) unnamed_addr #0 align 2 {
entry:
  %0 = getelementptr inbounds %struct.Foo, %struct.Foo* %this, i64 0, i32 0
  store i32 (...)** bitcast (i8** getelementptr inbounds ({ [2 x i8*] }, { [2 x i8*] }* @0, i32 0, i32 0, i32 1) to i32 (...)**), i32 (...)*** %0, align 8, !tbaa !3
  ret %struct.Foo* %this
}

You get this code, which is less good:

"??0Foo@@QEAA@XZ":                      # @"??0Foo@@QEAA@XZ"
# %bb.0:                                # %entry
        movq    %rcx, %rax
        leaq    .L__unnamed_1+8(%rip), %rcx
        movq    %rcx, (%rax)
        retq

That creates a relocation to the section instead of the symbol.

This alias happens to be external, so it wouldn't be stripped by this change, but even if it were internal, it's nicer to refer to the internal alias than the private symbol.

[aeubanks]

abandoning in favor of D100923

llvm/include/llvm/IR/Value.h

public:
   /// Returns the original uncasted value.  If this is called on a non-pointer
   /// value, it returns 'this'.
   const Value *stripPointerCastsAndAliases() const;
   Value *stripPointerCastsAndAliases() {
     return const_cast<Value *>(
         static_cast<const Value *>(this)->stripPointerCastsAndAliases());
   }
 
+  /// Strip off pointer casts, all-zero GEPs, address space casts, and local
+  /// aliases.
+  ///
+  /// Returns the original uncasted value.  If this is called on a non-pointer
+  /// value, it returns 'this'.
+  const Value *stripPointerCastsAndLocalAliases() const;
+  Value *stripPointerCastsAndLocalAliases() {
+    return const_cast<Value *>(
+        static_cast<const Value *>(this)->stripPointerCastsAndLocalAliases());
+  }
+
   /// Strip off pointer casts, all-zero GEPs and address space casts
   /// but ensures the representation of the result stays the same.
   ///
   /// Returns the original uncasted value with the same representation. If this
   /// is called on a non-pointer value, it returns 'this'.
   const Value *stripPointerCastsSameRepresentation() const;
   Value *stripPointerCastsSameRepresentation() {
     return const_cast<Value *>(static_cast<const Value *>(this)

llvm/lib/Analysis/ConstantFolding.cpp

Constant *CastGEPIndices(Type *SrcElemTy, ArrayRef<Constant *> Ops,
   if (!Any)
     return nullptr;
 
   Constant *C = ConstantExpr::getGetElementPtr(
       SrcElemTy, Ops[0], NewIdxs, /*InBounds=*/false, InRangeIndex);
   return ConstantFoldConstant(C, DL, TLI);
 }
 
-/// Strip the pointer casts, but preserve the address space information.
+/// Strip the pointer casts and local aliases, but preserve the address space
+/// information.
 Constant *StripPtrCastKeepAS(Constant *Ptr, Type *&ElemTy) {
   assert(Ptr->getType()->isPointerTy() && "Not a pointer type");
   auto *OldPtrTy = cast<PointerType>(Ptr->getType());
-  Ptr = cast<Constant>(Ptr->stripPointerCasts());
+  Ptr = cast<Constant>(Ptr->stripPointerCastsAndLocalAliases());
   auto *NewPtrTy = cast<PointerType>(Ptr->getType());
 
   ElemTy = NewPtrTy->getPointerElementType();
 
   // Preserve the address space number of the pointer.
   if (NewPtrTy->getAddressSpace() != OldPtrTy->getAddressSpace()) {
     NewPtrTy = ElemTy->getPointerTo(OldPtrTy->getAddressSpace());
     Ptr = ConstantExpr::getPointerCast(Ptr, NewPtrTy);

llvm/lib/IR/Value.cpp

void Value::replaceUsesOutsideBlock(Value *New, BasicBlock *BB) {
   });
 }
 
 namespace {
 // Various metrics for how much to strip off of pointers.
 enum PointerStripKind {
   PSK_ZeroIndices,
   PSK_ZeroIndicesAndAliases,
+  PSK_ZeroIndicesAndLocalAliases,
   PSK_ZeroIndicesSameRepresentation,
   PSK_ForAliasAnalysis,
   PSK_InBoundsConstantIndices,
   PSK_InBounds
 };
 
 template <PointerStripKind StripKind> static void NoopCallback(const Value *) {}
 
static const Value *stripPointerCastsAndOffsets(
 
   Visited.insert(V);
   do {
     Func(V);
     if (auto *GEP = dyn_cast<GEPOperator>(V)) {
       switch (StripKind) {
       case PSK_ZeroIndices:
       case PSK_ZeroIndicesAndAliases:
+      case PSK_ZeroIndicesAndLocalAliases:
       case PSK_ZeroIndicesSameRepresentation:
       case PSK_ForAliasAnalysis:
         if (!GEP->hasAllZeroIndices())
           return V;
         break;
       case PSK_InBoundsConstantIndices:
         if (!GEP->hasAllConstantIndices())
           return V;
if (auto *GEP = dyn_cast<GEPOperator>(V)) {
         return V;
     } else if (StripKind != PSK_ZeroIndicesSameRepresentation &&
                Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
       // TODO: If we know an address space cast will not change the
       //       representation we could look through it here as well.
       V = cast<Operator>(V)->getOperand(0);
     } else if (StripKind == PSK_ZeroIndicesAndAliases && isa<GlobalAlias>(V)) {
       V = cast<GlobalAlias>(V)->getAliasee();
+    } else if (StripKind == PSK_ZeroIndicesAndLocalAliases &&
+               isa<GlobalAlias>(V) && cast<GlobalAlias>(V)->hasLocalLinkage()) {
+      V = cast<GlobalAlias>(V)->getAliasee();
     } else if (StripKind == PSK_ForAliasAnalysis && isa<PHINode>(V) &&
                cast<PHINode>(V)->getNumIncomingValues() == 1) {
       V = cast<PHINode>(V)->getIncomingValue(0);
     } else {
       if (const auto *Call = dyn_cast<CallBase>(V)) {
         if (const Value *RV = Call->getReturnedArgOperand()) {
           V = RV;
           continue;

 const Value *Value::stripPointerCasts() const {
   return stripPointerCastsAndOffsets<PSK_ZeroIndices>(this);
 }
 
 const Value *Value::stripPointerCastsAndAliases() const {
   return stripPointerCastsAndOffsets<PSK_ZeroIndicesAndAliases>(this);
 }
 
+const Value *Value::stripPointerCastsAndLocalAliases() const {
+  return stripPointerCastsAndOffsets<PSK_ZeroIndicesAndLocalAliases>(this);
+}
+
 const Value *Value::stripPointerCastsSameRepresentation() const {
   return stripPointerCastsAndOffsets<PSK_ZeroIndicesSameRepresentation>(this);
 }
 
 const Value *Value::stripInBoundsConstantOffsets() const {
   return stripPointerCastsAndOffsets<PSK_InBoundsConstantIndices>(this);
 }
 

llvm/test/Transforms/InstSimplify/ConstProp/gep-alias.ll

-; RUN: opt -instcombine -S -o - %s | FileCheck %s
-; Test that we don't replace an alias with its aliasee when simplifying GEPs.
-; In this test case the transformation is invalid because it replaces the
-; reference to the symbol "b" (which refers to whichever instance of "b"
-; was chosen by the linker) with a reference to "a" (which refers to the
-; specific instance of "b" in this module).
-
-target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
-target triple = "x86_64-unknown-linux-gnu"
-
-@a = internal global [3 x i8*] zeroinitializer
-@b = linkonce_odr alias [3 x i8*], [3 x i8*]* @a
-
-define i8** @f() {
-  ; CHECK: ret i8** getelementptr ([3 x i8*], [3 x i8*]* @b, i64 0, i64 1)
-  ret i8** getelementptr ([3 x i8*], [3 x i8*]* @b, i64 0, i64 1)
-}
+; RUN: opt -instcombine -S -o - %s | FileCheck %s
+; Test that we don't replace an alias with its aliasee if the alias is non-local when simplifying GEPs.
+; The transformation is invalid for @f() because it replaces the
+; reference to the symbol "b" (which refers to whichever instance of "b"
+; was chosen by the linker) with a reference to "a" (which refers to the
+; specific instance of "b" in this module).
+; It's fine to look through local aliases though.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@a = internal global [3 x i8*] zeroinitializer
+@b = linkonce_odr alias [3 x i8*], [3 x i8*]* @a
+@c = internal alias [3 x i8*], [3 x i8*]* @a
+@d = private alias [3 x i8*], [3 x i8*]* @a
+
+define i8** @f() {
+; CHECK: ret i8** getelementptr ([3 x i8*], [3 x i8*]* @b, i64 0, i64 1)
+  ret i8** getelementptr ([3 x i8*], [3 x i8*]* @b, i64 0, i64 1)
+}
+
+define i8** @g() {
+; CHECK: ret i8** getelementptr inbounds ([3 x i8*], [3 x i8*]* @a, i64 0, i64 1)
+  ret i8** getelementptr ([3 x i8*], [3 x i8*]* @c, i64 0, i64 1)
+}
+
+define i8** @h() {
+; CHECK: ret i8** getelementptr inbounds ([3 x i8*], [3 x i8*]* @a, i64 0, i64 1)
+  ret i8** getelementptr ([3 x i8*], [3 x i8*]* @d, i64 0, i64 1)
+}