[ConstFold] Simplify a load's GEP operand through local aliases

[aeubanks]

Summary

MSVC-style RTTI produces loads through a GEP of a local alias which
itself is a GEP. Currently we aren't able to devirtualize any virtual
calls when MSVC RTTI is enabled.

This patch attempts to simplify a load's GEP operand by calling
SymbolicallyEvaluateGEP() with an option to look through local aliases.

[rnk]

Should we go forward with something in the direction of D101103 instead, or is this still the way forward?

llvm/lib/IR/Value.cpp

624–625

Do we need checks for non-interposability on the alias and aliasee here?

[aeubanks]

properly handle non-interposable aliases, add tests

[aeubanks]

rebase
add comments

[rnk]

llvm/lib/Analysis/ConstantFolding.cpp

874

We talked about moving the alias handling here rather than adding an IR helper.

[aeubanks]

move everything out of Value into ConstantFolding.cpp

[rnk]

lgtm

[nikic]

llvm/lib/Analysis/ConstantFolding.cpp

877

This code uses a different check than the top-level case (https://github.com/llvm/llvm-project/blob/26223af256bb8f0aa1a82989882c81ffae44c6d1/llvm/lib/Analysis/ConstantFolding.cpp#L682-L684). Namely it also checks that the base object is not interposable. What's the reason for the difference? I'd expect both of them to use the same conditions.

[aeubanks]

llvm/lib/Analysis/ConstantFolding.cpp

877

See the discussions in https://reviews.llvm.org/D99240, https://reviews.llvm.org/D65118, https://bugs.llvm.org/show_bug.cgi?id=27866.

I keep getting confused by these explanations. But as I understand it right now, we are only allowed to replace an alias with its aliasee if both are not interposable (but we may not want to do this anyway). However, we can look through an alias to get the aliasee's contents if the alias is not interposable. So this patch is probably overly restrictive.

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 *stripPointerCasts() const;
   Value *stripPointerCasts() {
     return const_cast<Value *>(
         static_cast<const Value *>(this)->stripPointerCasts());
   }
 
+  /// Strip off pointer casts and local aliases to local aliasees.
+  ///
+  /// Returns the original uncasted value. If this is called on a non-pointer
+  /// value, it returns 'this'. This function should be used only in constant
+  /// folding loads.
+  const Value *stripPointerCastsForLoadOperand() const;
+  Value *stripPointerCastsForLoadOperand() {
+    return const_cast<Value *>(
+        static_cast<const Value *>(this)->stripPointerCastsForLoadOperand());
+  }
+
   /// Strip off pointer casts, all-zero GEPs, address space casts, and aliases.
   ///
   /// 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());

llvm/lib/Analysis/ConstantFolding.cpp

 #include <cfenv>
 #include <cmath>
 #include <cstddef>
 #include <cstdint>
 
 using namespace llvm;
 
 namespace {
+Constant *SymbolicallyEvaluateGEP(const GEPOperator *GEP,
+                                  ArrayRef<Constant *> Ops,
+                                  const DataLayout &DL,
+                                  const TargetLibraryInfo *TLI,
+                                  bool ForLoadOperand);
 
 //===----------------------------------------------------------------------===//
 // Constant Folding internal helper functions
 //===----------------------------------------------------------------------===//
 
 static Constant *foldConstVectorToAPInt(APInt &Result, Type *DestTy,
                                         Constant *C, Type *SrcEltTy,
                                         unsigned NumSrcElts,
Constant *llvm::ConstantFoldLoadFromConstPtr(Constant *C, Type *Ty,
 
   if (CE->getOpcode() == Instruction::GetElementPtr) {
     if (auto *GV = dyn_cast<GlobalVariable>(CE->getOperand(0))) {
       if (GV->isConstant() && GV->hasDefinitiveInitializer()) {
         if (Constant *V = ConstantFoldLoadThroughGEPConstantExpr(
                 GV->getInitializer(), CE, Ty, DL))
           return V;
       }
+    } else {
+      // Try to simplify GEP if the pointer operand wasn't a GlobalVariable.
+      // SymbolicallyEvaluateGEP() with `ForLoadOperand = true` can potentially
+      // simplify the GEP more than it normally would have been, but should only
+      // be used for const folding loads.
+      SmallVector<Constant *> Ops;
+      for (unsigned I = 0, E = CE->getNumOperands(); I != E; ++I)
+        Ops.push_back(cast<Constant>(CE->getOperand(I)));
+      if (auto *Simplified = dyn_cast_or_null<ConstantExpr>(
+              SymbolicallyEvaluateGEP(cast<GEPOperator>(CE), Ops, DL, nullptr,
+                                      /*ForLoadOperand*/ true))) {
+        // If the symbolically evaluated GEP is another GEP, we can only const
+        // fold it if the resulting pointer operand is a GlobalValue. Otherwise
+        // there is nothing else to simplify since the GEP is already in the
+        // most simplified form.
+        if (auto *SimplifiedGEP = dyn_cast<GEPOperator>(Simplified)) {
+          if (auto *GV = dyn_cast<GlobalVariable>(Simplified->getOperand(0))) {
+            if (GV->isConstant() && GV->hasDefinitiveInitializer()) {
+              if (Constant *V = ConstantFoldLoadThroughGEPConstantExpr(
+                      GV->getInitializer(), Simplified, Ty, DL))
+                return V;
+            }
+          }
+        } else {
+          return ConstantFoldLoadFromConstPtr(Simplified, Ty, DL);
+        }
+      }
     }
   }
 
   if (CE->getOpcode() == Instruction::BitCast)
     if (Constant *LoadedC = ConstantFoldLoadThroughBitcastExpr(CE, Ty, DL))
       return LoadedC;
 
   // Instead of loading constant c string, use corresponding integer value
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.
-Constant *StripPtrCastKeepAS(Constant *Ptr, Type *&ElemTy) {
+Constant *StripPtrCastKeepAS(Constant *Ptr, Type *&ElemTy,
+                             bool ForLoadOperand) {
   assert(Ptr->getType()->isPointerTy() && "Not a pointer type");
   auto *OldPtrTy = cast<PointerType>(Ptr->getType());
+  if (ForLoadOperand)
+    Ptr = cast<Constant>(Ptr->stripPointerCastsForLoadOperand());
+  else
     Ptr = cast<Constant>(Ptr->stripPointerCasts());
   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);
   }
   return Ptr;
 }
 
 /// If we can symbolically evaluate the GEP constant expression, do so.
 Constant *SymbolicallyEvaluateGEP(const GEPOperator *GEP,
                                   ArrayRef<Constant *> Ops,
                                   const DataLayout &DL,
-                                  const TargetLibraryInfo *TLI) {
+                                  const TargetLibraryInfo *TLI,
+                                  bool ForLoadOperand) {
   const GEPOperator *InnermostGEP = GEP;
   bool InBounds = GEP->isInBounds();
 
   Type *SrcElemTy = GEP->getSourceElementType();
   Type *ResElemTy = GEP->getResultElementType();
   Type *ResTy = GEP->getType();
   if (!SrcElemTy->isSized() || isa<ScalableVectorType>(SrcElemTy))
     return nullptr;
for (unsigned i = 1, e = Ops.size(); i != e; ++i)
       }
 
   unsigned BitWidth = DL.getTypeSizeInBits(IntIdxTy);
   APInt Offset =
       APInt(BitWidth,
             DL.getIndexedOffsetInType(
                 SrcElemTy,
                 makeArrayRef((Value * const *)Ops.data() + 1, Ops.size() - 1)));
-  Ptr = StripPtrCastKeepAS(Ptr, SrcElemTy);
+  Ptr = StripPtrCastKeepAS(Ptr, SrcElemTy, ForLoadOperand);
 
   // If this is a GEP of a GEP, fold it all into a single GEP.
   while (auto *GEP = dyn_cast<GEPOperator>(Ptr)) {
     InnermostGEP = GEP;
     InBounds &= GEP->isInBounds();
 
     SmallVector<Value *, 4> NestedOps(GEP->op_begin() + 1, GEP->op_end());
 
     // Do not try the incorporate the sub-GEP if some index is not a number.
     bool AllConstantInt = true;
     for (Value *NestedOp : NestedOps)
       if (!isa<ConstantInt>(NestedOp)) {
         AllConstantInt = false;
         break;
       }
     if (!AllConstantInt)
       break;
 
     Ptr = cast<Constant>(GEP->getOperand(0));
     SrcElemTy = GEP->getSourceElementType();
     Offset += APInt(BitWidth, DL.getIndexedOffsetInType(SrcElemTy, NestedOps));
-    Ptr = StripPtrCastKeepAS(Ptr, SrcElemTy);
+    Ptr = StripPtrCastKeepAS(Ptr, SrcElemTy, ForLoadOperand);
   }
 
   // If the base value for this address is a literal integer value, fold the
   // getelementptr to the resulting integer value casted to the pointer type.
   APInt BasePtr(BitWidth, 0);
   if (auto *CE = dyn_cast<ConstantExpr>(Ptr)) {
     if (CE->getOpcode() == Instruction::IntToPtr) {
       if (auto *Base = dyn_cast<ConstantInt>(CE->getOperand(0)))
Constant *ConstantFoldInstOperandsImpl(const Value *InstOrCE, unsigned Opcode,
 
   if (Instruction::isBinaryOp(Opcode))
     return ConstantFoldBinaryOpOperands(Opcode, Ops[0], Ops[1], DL);
 
   if (Instruction::isCast(Opcode))
     return ConstantFoldCastOperand(Opcode, Ops[0], DestTy, DL);
 
   if (auto *GEP = dyn_cast<GEPOperator>(InstOrCE)) {
-    if (Constant *C = SymbolicallyEvaluateGEP(GEP, Ops, DL, TLI))
+    if (Constant *C = SymbolicallyEvaluateGEP(GEP, Ops, DL, TLI,
+                                              /*ForLoadOperand*/ false))
       return C;
 
     return ConstantExpr::getGetElementPtr(GEP->getSourceElementType(), Ops[0],
                                           Ops.slice(1), GEP->isInBounds(),
                                           GEP->getInRangeIndex());
   }
 
   if (auto *CE = dyn_cast<ConstantExpr>(InstOrCE))

llvm/lib/IR/Value.cpp

 
 namespace {
 // Various metrics for how much to strip off of pointers.
 enum PointerStripKind {
   PSK_ZeroIndices,
   PSK_ZeroIndicesAndAliases,
   PSK_ZeroIndicesSameRepresentation,
   PSK_ForAliasAnalysis,
+  PSK_ForLoadOperand,
   PSK_InBoundsConstantIndices,
   PSK_InBounds
 };
 
 template <PointerStripKind StripKind> static void NoopCallback(const Value *) {}
 
 template <PointerStripKind StripKind>
 static const Value *stripPointerCastsAndOffsets(
if (auto *GEP = dyn_cast<GEPOperator>(V)) {
       case PSK_InBoundsConstantIndices:
         if (!GEP->hasAllConstantIndices())
           return V;
         LLVM_FALLTHROUGH;
       case PSK_InBounds:
         if (!GEP->isInBounds())
           return V;
         break;
+      case PSK_ForLoadOperand:
+        return V;
       }
       V = GEP->getPointerOperand();
     } else if (Operator::getOpcode(V) == Instruction::BitCast) {
       V = cast<Operator>(V)->getOperand(0);
       if (!V->getType()->isPointerTy())
         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_ForLoadOperand && isa<GlobalAlias>(V) &&
+               !cast<GlobalAlias>(V)->isInterposable() &&
+               !cast<GlobalAlias>(V)->getBaseObject()->isInterposable()) {
+      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;
static const Value *stripPointerCastsAndOffsets(
   return V;
 }
 } // end anonymous namespace
 
 const Value *Value::stripPointerCasts() const {
   return stripPointerCastsAndOffsets<PSK_ZeroIndices>(this);
 }
 
+const Value *Value::stripPointerCastsForLoadOperand() const {
+  return stripPointerCastsAndOffsets<PSK_ForLoadOperand>(this);
+}
+
 const Value *Value::stripPointerCastsAndAliases() const {
   return stripPointerCastsAndOffsets<PSK_ZeroIndicesAndAliases>(this);
 }
 
 const Value *Value::stripPointerCastsSameRepresentation() const {
   return stripPointerCastsAndOffsets<PSK_ZeroIndicesSameRepresentation>(this);
 }
 

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

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -passes=instsimplify -S < %s | FileCheck %s
+
+@a1 = internal alias i32, getelementptr ({[3 x i32]}, {[3 x i32]}* @b, i32 0, i32 0, i32 1)
+@a2 = weak alias i32, getelementptr ({[3 x i32]}, {[3 x i32]}* @b, i32 0, i32 0, i32 1)
+@b = internal constant {[3 x i32]} {[3 x i32] [i32 2, i32 3, i32 4]}
+
+@c = internal alias i32, getelementptr ({[3 x i32]}, {[3 x i32]}* @d, i32 0, i32 0, i32 1)
+@d = weak constant {[3 x i32]} {[3 x i32] [i32 2, i32 3, i32 4]}
+
+define i32 @f() {
+; CHECK-LABEL: @f(
+; CHECK-NEXT:    ret i32 4
+;
+  %a = load i32, i32* getelementptr (i32, i32* @a1, i64 1)
+  ret i32 %a
+}
+
+define i32 @g() {
+; CHECK-LABEL: @g(
+; CHECK-NEXT:    [[A:%.*]] = load i32, i32* getelementptr (i32, i32* @a2, i64 1), align 4
+; CHECK-NEXT:    ret i32 [[A]]
+;
+  %a = load i32, i32* getelementptr (i32, i32* @a2, i64 1)
+  ret i32 %a
+}
+
+define i32 @h() {
+; CHECK-LABEL: @h(
+; CHECK-NEXT:    [[A:%.*]] = load i32, i32* getelementptr (i32, i32* @c, i64 1), align 4
+; CHECK-NEXT:    ret i32 [[A]]
+;
+  %a = load i32, i32* getelementptr (i32, i32* @c, i64 1)
+  ret i32 %a
+}