[Evaluator] Improve evaluation of load/store

[evgeny777]

Summary

When storing pointers in struct/class constructor clang often generates IR like this:

define internal void @_GLOBAL__sub_I_main.cpp()  {
  %1 = load i64, i64* bitcast (%struct.A** @gA to i64*), align 8
  store i64 %1, i64* bitcast (%struct.S* @s to i64*), align 8
  ret void
}

which corresponds to following C++ code:

extern A *gA;
struct S {
  A* _a;
} SObj(gA);

With D43077 it is now possible to import variables from different TU when using ThinLTO,
so it would be nice to optimize such static ctors out.

[evgeny777]

Any comments on this?

[tejohnson]

Sorry for the delay. I don't feel super confident reviewing these change. I looked back at who touched the ComputeLoadResult code last (besides pcc who simply extracted it out of GlobalOpt into Utils), and it was Chris Lattner in 2005! So I am not completely sure who to add to as a reviewer at this point.
Poking around LLVM though, I see that there is some very similar handling in llvm::ConstantFoldLoadFromConstPtr (ConstantFolding.cpp). In particular, the handling of P as a GlobalVariable or GEP appears identical to what is already in Evaluator::ComputeLoadResult. It already has handling for bitcasts, although that handling appears quite a bit more complex that what you added to ComputeLoadResult. I'm wondering whether ComputeLoadResult can be refactored to just call ConstantFoldLoadFromConstPtr, or whether there is a reason it needs to remain distinct (and why the bitcast handling added here is simpler).

[evgeny777]

Unfortunately ConstantFoldLoadFromConstPtr seems to be useful, because it checks for GV initializer being constant and we're not forced by this constraint when evaluating static ctors.
However it turned out we can use ConstantFoldLoadThroughBitcast when evaluating both load and store.

[tejohnson]

LGTM with some minor comments below.

include/llvm/Analysis/ConstantFolding.h

150 ↗

(On Diff #137443)

document

lib/Transforms/Utils/Evaluator.cpp

202 ↗

(On Diff #137443)

The two opcode cases are both doing the same checks (is it a global variable with a definitive initializer), but the checking is structured differently. Suggest structuring the checks the same way for both opcodes.

llvm/trunk/include/llvm/Analysis/ConstantFolding.h

 bool canConstantFoldCallTo(ImmutableCallSite CS, const Function *F);
 
 /// ConstantFoldCall - Attempt to constant fold a call to the specified function
 /// with the specified arguments, returning null if unsuccessful.
 Constant *ConstantFoldCall(ImmutableCallSite CS, Function *F,
                            ArrayRef<Constant *> Operands,
                            const TargetLibraryInfo *TLI = nullptr);
 
+/// ConstantFoldLoadThroughBitcast - try to cast constant to destination type
+/// returning null if unsuccessful. Can cast pointer to pointer or pointer to
+/// integer and vice versa if their sizes are equal.
+Constant *ConstantFoldLoadThroughBitcast(Constant *C, Type *DestTy,
+                                         const DataLayout &DL);
+
 /// \brief Check whether the given call has no side-effects.
 /// Specifically checks for math routimes which sometimes set errno.
 bool isMathLibCallNoop(CallSite CS, const TargetLibraryInfo *TLI);
 }
 
 #endif

llvm/trunk/lib/Analysis/ConstantFolding.cpp

bool llvm::IsConstantOffsetFromGlobal(Constant *C, GlobalValue *&GV,
   // Otherwise, add any offset that our operands provide.
   if (!GEP->accumulateConstantOffset(DL, TmpOffset))
     return false;
 
   Offset = TmpOffset;
   return true;
 }
 
+Constant *llvm::ConstantFoldLoadThroughBitcast(Constant *C, Type *DestTy,
+                                         const DataLayout &DL) {
+  do {
+    Type *SrcTy = C->getType();
+
+    // If the type sizes are the same and a cast is legal, just directly
+    // cast the constant.
+    if (DL.getTypeSizeInBits(DestTy) == DL.getTypeSizeInBits(SrcTy)) {
+      Instruction::CastOps Cast = Instruction::BitCast;
+      // If we are going from a pointer to int or vice versa, we spell the cast
+      // differently.
+      if (SrcTy->isIntegerTy() && DestTy->isPointerTy())
+        Cast = Instruction::IntToPtr;
+      else if (SrcTy->isPointerTy() && DestTy->isIntegerTy())
+        Cast = Instruction::PtrToInt;
+
+      if (CastInst::castIsValid(Cast, C, DestTy))
+        return ConstantExpr::getCast(Cast, C, DestTy);
+    }
+
+    // If this isn't an aggregate type, there is nothing we can do to drill down
+    // and find a bitcastable constant.
+    if (!SrcTy->isAggregateType())
+      return nullptr;
+
+    // We're simulating a load through a pointer that was bitcast to point to
+    // a different type, so we can try to walk down through the initial
+    // elements of an aggregate to see if some part of th e aggregate is
+    // castable to implement the "load" semantic model.
+    C = C->getAggregateElement(0u);
+  } while (C);
+
+  return nullptr;
+}
+
 namespace {
 
 /// Recursive helper to read bits out of global. C is the constant being copied
 /// out of. ByteOffset is an offset into C. CurPtr is the pointer to copy
 /// results into and BytesLeft is the number of bytes left in
 /// the CurPtr buffer. DL is the DataLayout.
 bool ReadDataFromGlobal(Constant *C, uint64_t ByteOffset, unsigned char *CurPtr,
                         unsigned BytesLeft, const DataLayout &DL) {
for (unsigned i = 1; i != BytesLoaded; ++i) {
       ResultVal <<= 8;
       ResultVal |= RawBytes[i];
     }
   }
 
   return ConstantInt::get(IntType->getContext(), ResultVal);
 }
 
-Constant *ConstantFoldLoadThroughBitcast(ConstantExpr *CE, Type *DestTy,
+Constant *ConstantFoldLoadThroughBitcastExpr(ConstantExpr *CE, Type *DestTy,
                                              const DataLayout &DL) {
   auto *SrcPtr = CE->getOperand(0);
   auto *SrcPtrTy = dyn_cast<PointerType>(SrcPtr->getType());
   if (!SrcPtrTy)
     return nullptr;
   Type *SrcTy = SrcPtrTy->getPointerElementType();
 
   Constant *C = ConstantFoldLoadFromConstPtr(SrcPtr, SrcTy, DL);
   if (!C)
     return nullptr;
 
-  do {
-    Type *SrcTy = C->getType();
-
-    // If the type sizes are the same and a cast is legal, just directly
-    // cast the constant.
-    if (DL.getTypeSizeInBits(DestTy) == DL.getTypeSizeInBits(SrcTy)) {
-      Instruction::CastOps Cast = Instruction::BitCast;
-      // If we are going from a pointer to int or vice versa, we spell the cast
-      // differently.
-      if (SrcTy->isIntegerTy() && DestTy->isPointerTy())
-        Cast = Instruction::IntToPtr;
-      else if (SrcTy->isPointerTy() && DestTy->isIntegerTy())
-        Cast = Instruction::PtrToInt;
-
-      if (CastInst::castIsValid(Cast, C, DestTy))
-        return ConstantExpr::getCast(Cast, C, DestTy);
-    }
-
-    // If this isn't an aggregate type, there is nothing we can do to drill down
-    // and find a bitcastable constant.
-    if (!SrcTy->isAggregateType())
-      return nullptr;
-
-    // We're simulating a load through a pointer that was bitcast to point to
-    // a different type, so we can try to walk down through the initial
-    // elements of an aggregate to see if some part of th e aggregate is
-    // castable to implement the "load" semantic model.
-    C = C->getAggregateElement(0u);
-  } while (C);
-
-  return nullptr;
+  return llvm::ConstantFoldLoadThroughBitcast(C, DestTy, DL);
 }
 
 } // end anonymous namespace
 
 Constant *llvm::ConstantFoldLoadFromConstPtr(Constant *C, Type *Ty,
                                              const DataLayout &DL) {
   // First, try the easy cases:
   if (auto *GV = dyn_cast<GlobalVariable>(C))
if (auto *GV = dyn_cast<GlobalVariable>(CE->getOperand(0))) {
         if (Constant *V =
              ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE))
           return V;
       }
     }
   }
 
   if (CE->getOpcode() == Instruction::BitCast)
-    if (Constant *LoadedC = ConstantFoldLoadThroughBitcast(CE, Ty, DL))
+    if (Constant *LoadedC = ConstantFoldLoadThroughBitcastExpr(CE, Ty, DL))
       return LoadedC;
 
   // Instead of loading constant c string, use corresponding integer value
   // directly if string length is small enough.
   StringRef Str;
   if (getConstantStringInfo(CE, Str) && !Str.empty()) {
     size_t StrLen = Str.size();
     unsigned NumBits = Ty->getPrimitiveSizeInBits();

llvm/trunk/lib/Transforms/Utils/Evaluator.cpp

// operand to the value operand.
       // external globals.
       return cast<GlobalVariable>(CE->getOperand(0))->hasUniqueInitializer();
     }
   }
 
   return false;
 }
 
+static Constant *getInitializer(Constant *C) {
+  auto *GV = dyn_cast<GlobalVariable>(C);
+  return GV && GV->hasDefinitiveInitializer() ? GV->getInitializer() : nullptr;
+}
+
 /// Return the value that would be computed by a load from P after the stores
 /// reflected by 'memory' have been performed.  If we can't decide, return null.
 Constant *Evaluator::ComputeLoadResult(Constant *P) {
   // If this memory location has been recently stored, use the stored value: it
   // is the most up-to-date.
   DenseMap<Constant*, Constant*>::const_iterator I = MutatedMemory.find(P);
   if (I != MutatedMemory.end()) return I->second;
 
   // Access it.
   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) {
     if (GV->hasDefinitiveInitializer())
       return GV->getInitializer();
     return nullptr;
   }
 
+  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(P)) {
+    switch (CE->getOpcode()) {
     // Handle a constantexpr getelementptr.
-  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(P))
-    if (CE->getOpcode() == Instruction::GetElementPtr &&
-        isa<GlobalVariable>(CE->getOperand(0))) {
-      GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
-      if (GV->hasDefinitiveInitializer())
-        return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE);
-    }
+    case Instruction::GetElementPtr:
+      if (auto *I = getInitializer(CE->getOperand(0)))
+        return ConstantFoldLoadThroughGEPConstantExpr(I, CE);
+      break;
+    // Handle a constantexpr bitcast.
+    case Instruction::BitCast:
+      if (auto *I = getInitializer(CE->getOperand(0)))
+        return ConstantFoldLoadThroughBitcast(
+            I, P->getType()->getPointerElementType(), DL);
+      break;
+    }
 
   return nullptr;  // don't know how to evaluate.
 }
 
 /// Evaluate all instructions in block BB, returning true if successful, false
 /// if we can't evaluate it.  NewBB returns the next BB that control flows into,
 /// or null upon return.
 bool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst,
if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
           // stored value.
           Ptr = CE->getOperand(0);
 
           Type *NewTy = cast<PointerType>(Ptr->getType())->getElementType();
 
           // In order to push the bitcast onto the stored value, a bitcast
           // from NewTy to Val's type must be legal.  If it's not, we can try
           // introspecting NewTy to find a legal conversion.
-          while (!Val->getType()->canLosslesslyBitCastTo(NewTy)) {
+          Constant *NewVal;
+          while (!(NewVal = ConstantFoldLoadThroughBitcast(Val, NewTy, DL))) {
             // If NewTy is a struct, we can convert the pointer to the struct
             // into a pointer to its first member.
             // FIXME: This could be extended to support arrays as well.
             if (StructType *STy = dyn_cast<StructType>(NewTy)) {
               NewTy = STy->getTypeAtIndex(0U);
 
               IntegerType *IdxTy = IntegerType::get(NewTy->getContext(), 32);
               Constant *IdxZero = ConstantInt::get(IdxTy, 0, false);
               Constant * const IdxList[] = {IdxZero, IdxZero};
 
               Ptr = ConstantExpr::getGetElementPtr(nullptr, Ptr, IdxList);
               if (auto *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI))
                 Ptr = FoldedPtr;
 
             // If we can't improve the situation by introspecting NewTy,
             // we have to give up.
             } else {
               DEBUG(dbgs() << "Failed to bitcast constant ptr, can not "
                     "evaluate.\n");
               return false;
             }
           }
 
-          // If we found compatible types, go ahead and push the bitcast
-          // onto the stored value.
-          Val = ConstantExpr::getBitCast(Val, NewTy);
-
+          Val = NewVal;
           DEBUG(dbgs() << "Evaluated bitcast: " << *Val << "\n");
         }
       }
 
       MutatedMemory[Ptr] = Val;
     } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) {
       InstResult = ConstantExpr::get(BO->getOpcode(),
                                      getVal(BO->getOperand(0)),

llvm/trunk/test/Transforms/GlobalOpt/evaluate-bitcast.ll

+; RUN: opt -globalopt -instcombine %s -S -o - | FileCheck %s
+
+; Static constructor should have been optimized out
+; CHECK:       i32 @main
+; CHECK-NEXT:     ret i32 69905
+; CHECK-NOT:   _GLOBAL__sub_I_main.cpp
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-linux-gnu"
+
+%struct.S = type { %struct.A* }
+%struct.A = type { i64, i64 }
+
+@s = internal local_unnamed_addr global %struct.S zeroinitializer, align 8
[e-mail]_ctors = appending global [1 x { i32, void ()*, i8* }] [{ i32, void ()*, i8* } { i32 65535, void ()* @_GLOBAL__sub_I_main.cpp, i8* null }]
+@gA = available_externally dso_local local_unnamed_addr global %struct.A* inttoptr (i64 69905 to %struct.A*), align 8
+
+define dso_local i32 @main() local_unnamed_addr {
+  %1 = load i64, i64* bitcast (%struct.S* @s to i64*), align 8
+  %2 = trunc i64 %1 to i32
+  ret i32 %2
+}
+
+define internal void @_GLOBAL__sub_I_main.cpp() section ".text.startup" {
+  %1 = load i64, i64* bitcast (%struct.A** @gA to i64*), align 8
+  store i64 %1, i64* bitcast (%struct.S* @s to i64*), align 8
+  ret void
+}