[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 ↗

(On Diff #339756)

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–881

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/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());
   Ptr = cast<Constant>(Ptr->stripPointerCasts());
+  if (ForLoadOperand) {
+    while (isa<GlobalAlias>(Ptr) && !cast<GlobalAlias>(Ptr)->isInterposable() &&
+           !cast<GlobalAlias>(Ptr)->getBaseObject()->isInterposable()) {
+      Ptr = cast<GlobalAlias>(Ptr)->getAliasee();
+    }
+  }
+
   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/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
+}