[Evaluator] Walk initial elements when handling load through bitcast

[rob.lougher]

Summary

On x86-64, if the following program is compiled at -O1 or above, the value 0 will be incorrectly printed.

#include <stdio.h>

union A {
  A(long long ll) : l(ll) {}
  void *p;
  long long l;
} u(12345);

long long l = u.l;

int main() {
  printf("%lld\n", l);
}

This is caused by the incorrect evaluation of the load from "u.l".

On input to the evaluator we have a store instruction, storing 12345 into "u", and a load reading the value to initialize "l". Both of these instructions are through a bitcast:

define linkonce_odr dso_local void @_ZN1AC2Ex(%union.A* %this, i64 %ll) unnamed_addr comdat align 2 {
  %l = bitcast %union.A* %this to i64*
  store i64 %ll, i64* %l, align 8
  ret void
...
define internal void @__cxx_global_var_init.1() section ".text.startup" {
  %1 = load i64, i64* bitcast (%union.A* @u to i64*), align 8
  store i64 %1, i64* @l, align 8
  ret void
}

When evaluating a store through a bitcast, the evaluator tries to move the bitcast from the pointer onto the stored value. So in this case we will go from:

store i64 %ll, i64* bitcast (%union.A* %this to i64*), align 8

to:

store %union.A bitcast (i64 %ll to %union.A), %union.A* %this, align 8

However, as the cast is invalid, it tries to "introspect" the type to get a valid cast by obtaining a pointer to the initial element. This ends up storing into the mutated memory an inttoptr of "12345", to an i8* pointer (a GEP).

This is so far OK. However, when evaluating the load, we first try to lookup the bitcast in the mutated memory (which doesn't exist). We then try to lookup the bitcast "from" pointer which also doesn't exist. But the "from" pointer is a global variable with a definitive initializer, so we end up folding the load to zero.

What is missing is equivalent logic to the store to introspect the type (in this case to obtain an i8* GEP, which does exist in the mutated memory, the inttoptr value obviously being castable to i64).

Note, when developing the patch I was unhappy with adding similar logic directly to the load case as it could get out of step again (e..g. given the comment in the code regarding arrays). Instead, I have abstracted the "introspection" into a helper function, with the specifics being handled by a passed-in lambda function. I have also taken the opportunity to replace the "getInitializer" helper function with a lambda. This is a non-functional change, and can be done separately if preferred.

[evgeny777]

I wonder if it's possible to stop using MutatedMemory for checks in ComputeLoadResult and instead start using separate map which can also be filled
in EvaluateBlock. In this new map you can use bitcast (or even first operand of bitcast) as a key.

Also please strip your patch from unrelated changes for now to make it easier to read.

lib/Transforms/Utils/Evaluator.cpp

236

This seems to be an unrelated change

375

May be use [&] ?

test/Transforms/GlobalOpt/evaluate-bitcast-2.ll

7

You should also check value of @u, I think

[rob.lougher]

Addressed review comments.

[rob.lougher]

In D60793#1469812, @evgeny777 wrote:

I wonder if it's possible to stop using MutatedMemory for checks in ComputeLoadResult and instead start using separate map which can also be filled
in EvaluateBlock. In this new map you can use bitcast (or even first operand of bitcast) as a key.

"MutatedMemory" is only used to hold evaluated store values. Using the bitcast as a key would be dangerous because we could then get different values for the same memory location (via different pointer types). Currently, the code ensures that there is only one value for each location, which is the most recent.

Also please strip your patch from unrelated changes for now to make it easier to read.

Done (see revised patch). Thanks for the review.

[evgeny777]

"MutatedMemory" is only used to hold evaluated store values

It is also used to patch initializers - see BatchCommitValueTo

Using the bitcast as a key would be dangerous

There is no straightforward way to do this in MutatedMemory because GEP is a special key type (see BatchCommitValueTo)
That's why I suggested using another map.

we could then get different values for the same memory location

How?

[rob.lougher]

In D60793#1470376, @evgeny777 wrote:

"MutatedMemory" is only used to hold evaluated store values

It is also used to patch initializers - see BatchCommitValueTo

With values from evaluated stores.

Using the bitcast as a key would be dangerous

There is no straightforward way to do this in MutatedMemory because GEP is a special key type (see BatchCommitValueTo)
That's why I suggested using another map.

we could then get different values for the same memory location

How?

union A {
  float f;
  int i;
};

void s1(union A *u) {
  u->i = 123;
}

void s2(union A *u) {
  u->f = 1.23;
}

int foo() {
  union A u;
  s1(&u);
  s2(&u);
  return u.i;
}

int i = foo();

Input to Global Var Opt:

define dso_local void @_Z2s1P1A(%union.A* %u) #0 {
  %i = bitcast %union.A* %u to i32*
  store i32 123, i32* %i, align 4, !tbaa !2
  ret void
}

define dso_local void @_Z2s2P1A(%union.A* %u) #0 {
  %f = bitcast %union.A* %u to float*
  store float 0x3FF3AE1480000000, float* %f, align 4, !tbaa !2
  ret void
}

define dso_local i32 @_Z3foov() #0 {
  %u = alloca %union.A, align 4
  %0 = bitcast %union.A* %u to i8*
  call void @llvm.lifetime.start.p0i8(i64 4, i8* %0) #3
  call void @_Z2s1P1A(%union.A* %u)
  call void @_Z2s2P1A(%union.A* %u)
  %i = bitcast %union.A* %u to i32*
  %1 = load i32, i32* %i, align 4, !tbaa !2
  call void @llvm.lifetime.end.p0i8(i64 4, i8* %0) #3
  ret i32 %1
}

Currently both store bitcasts will be replaced by a GEP to the first element, which means the load will get the correct value.

[evgeny777]

Can't operand 0 of bitcast (%union.A* %u) be used as a key?

[rob.lougher]

In D60793#1470484, @evgeny777 wrote:

Can't operand 0 of bitcast (%union.A* %u) be used as a key?

Currently the (possibly casted) stored value is of the type of the key. This means the pointer lookup at the start of ComputeLoadResult() will return a value of the correct type. I guess, my question is what's wrong with keeping it like it is?

[evgeny777]

what's wrong with keeping it like it is?

Well, if it were possible to avoid the same computation for load I'd like to avoid it. However your patch seems to also handle cases when store is using GEP and load is using bitcast:

define linkonce_odr dso_local void @_ZN1AC2Ex(%union.A* %this, i64 %ll) unnamed_addr comdat align 2 {
  %l = inttoptr i64 %ll to i8*
  %p = getelementptr inbounds %union.A, %union.A* %this, i64 0, i32 0
  store i8* %l, i8** %p
  ret void
}

define internal void @__cxx_global_var_init.1() section ".text.startup" {
  %1 = load i64, i64* bitcast (%union.A* @u to i64*), align 8
  store i64 %1, i64* @l, align 8
  ret void
}

So let's stick with current approach. I'd probably include the example above as a test case.

[rob.lougher]

In D60793#1471294, @evgeny777 wrote:

what's wrong with keeping it like it is?

Well, if it were possible to avoid the same computation for load I'd like to avoid it. However your patch seems to also handle cases when store is using GEP and load is using bitcast:

So let's stick with current approach. I'd probably include the example above as a test case.

Yes. I will add it as an extra test (after Easter, as I am now on vacation).

[rob.lougher]

Added additional test from review comments.

[evgeny777]

LGTM, thanks. I suggest waiting for 1-2 days in case @tejohnson has something to say.

[tejohnson]

I am not familiar with this code, so happy with @evgeny777 's review.

[hjyamauchi]

Hi, we encountered this issue https://bugs.llvm.org/show_bug.cgi?id=48055 which reverting this patch seems to make it go away.

Can you take a look into it?

Thanks.

[hjyamauchi]

Uploaded https://reviews.llvm.org/D92599

[jroelofs]

I have a miscompile that seems to stem from sharing the same logic between loads and stores.

In the store case, allowing evaluateBitcastFromPtr to narrow the operation to apply only to the struct's 0th element means we lose the writes to the other struct elements whenever constant folding is unable to fold an integer literal bitcast into a struct:

https://llvm.godbolt.org/z/8sYdYv5rh

[jroelofs]

https://reviews.llvm.org/D105838

lib/Transforms/Utils/Evaluator.cpp

// operand to the value operand.
       // external globals.
       return cast<GlobalVariable>(CE->getOperand(0))->hasUniqueInitializer();
     }
   }
 
   return false;
 }
 
+/// Apply 'Func' to Ptr. If this returns nullptr, introspect the pointer's
+/// type and walk down through the initial elements to obtain additional
+/// pointers to try. Returns the first non-null return value from Func, or
+/// nullptr if the type can't be introspected further.
+static Constant *
+evaluateBitcastFromPtr(Constant *Ptr, const DataLayout &DL,
+                       const TargetLibraryInfo *TLI,
+                       std::function<Constant *(Constant *)> Func) {
+  Constant *Val;
+  while (!(Val = Func(Ptr))) {
+    // If Ty 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.
+    Type *Ty = cast<PointerType>(Ptr->getType())->getElementType();
+    if (!isa<StructType>(Ty))
+      break;
+
+    IntegerType *IdxTy = IntegerType::get(Ty->getContext(), 32);
+    Constant *IdxZero = ConstantInt::get(IdxTy, 0, false);
+    Constant *const IdxList[] = {IdxZero, IdxZero};
+
+    Ptr = ConstantExpr::getGetElementPtr(Ty, Ptr, IdxList);
+    if (auto *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI))
+      Ptr = FoldedPtr;
+  }
+  return Val;
+}
+
 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;
+  auto findMemLoc = [this](Constant *Ptr) {
+    DenseMap<Constant *, Constant *>::const_iterator I =
+        MutatedMemory.find(Ptr);
+    return I != MutatedMemory.end() ? I->second : nullptr;
+  };
+
+  if (Constant *Val = findMemLoc(P))
+    return Val;
 
   // 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.
     case Instruction::GetElementPtr:
       if (auto *I = getInitializer(CE->getOperand(0)))
         return ConstantFoldLoadThroughGEPConstantExpr(I, CE);
       break;
     // Handle a constantexpr bitcast.
     case Instruction::BitCast:
-      Constant *Val = getVal(CE->getOperand(0));
-      auto MM = MutatedMemory.find(Val);
-      auto *I = (MM != MutatedMemory.end()) ? MM->second
-                                            : getInitializer(CE->getOperand(0));
-      if (I)
+      // We're evaluating a load through a pointer that was bitcast to a
+      // different type. See if the "from" pointer has recently been stored.
+      // If it hasn't, we may still be able to find a stored pointer by
+      // introspecting the type.
+      Constant *Val =
+          evaluateBitcastFromPtr(CE->getOperand(0), DL, TLI, findMemLoc);
+      if (!Val)
+        Val = getInitializer(CE->getOperand(0));
+      if (Val)
         return ConstantFoldLoadThroughBitcast(
-            I, P->getType()->getPointerElementType(), DL);
+            Val, P->getType()->getPointerElementType(), DL);
       break;
     }
   }
 
   return nullptr;  // don't know how to evaluate.
 }
 
 static Function *getFunction(Constant *C) {
if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
       }
 
       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) {
         if (CE->getOpcode() == Instruction::BitCast) {
           LLVM_DEBUG(dbgs()
                      << "Attempting to resolve bitcast on constant ptr.\n");
           // If we're evaluating a store through a bitcast, then we need
           // to pull the bitcast off the pointer type and push it onto the
-          // 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.
-          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)) {
-
-              IntegerType *IdxTy = IntegerType::get(NewTy->getContext(), 32);
-              Constant *IdxZero = ConstantInt::get(IdxTy, 0, false);
-              Constant * const IdxList[] = {IdxZero, IdxZero};
-
-              Ptr = ConstantExpr::getGetElementPtr(NewTy, Ptr, IdxList);
-              if (auto *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI))
-                Ptr = FoldedPtr;
-              NewTy = STy->getTypeAtIndex(0U);
+          // stored value. In order to push the bitcast onto the stored value,
+          // a bitcast from the pointer's element type to Val's type must be
+          // legal. If it's not, we can try introspecting the type to find a
+          // legal conversion.
+
+          auto castValTy = [&](Constant *P) -> Constant * {
+            Type *Ty = cast<PointerType>(P->getType())->getElementType();
+            if (Constant *FV = ConstantFoldLoadThroughBitcast(Val, Ty, DL)) {
+              Ptr = P;
+              return FV;
+            }
+            return nullptr;
+          };
 
-              // If we can't improve the situation by introspecting NewTy,
-              // we have to give up.
-            } else {
-              LLVM_DEBUG(dbgs() << "Failed to bitcast constant ptr, can not "
-                                   "evaluate.\n");
-              return false;
-            }
-          }
+          Constant *NewVal =
+              evaluateBitcastFromPtr(CE->getOperand(0), DL, TLI, castValTy);
+          if (!NewVal) {
 
           Val = NewVal;
           LLVM_DEBUG(dbgs() << "Evaluated bitcast: " << *Val << "\n");
         }
       }
 
       MutatedMemory[Ptr] = Val;
     } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) {

test/Transforms/GlobalOpt/evaluate-bitcast-2.ll

+; RUN: opt < %s -globalopt -S | FileCheck %s
+
+; Test the evaluation of a store and a load via a bitcast, and check
+; that globals are constant folded to the correct value.
+
+; CHECK: @u = dso_local local_unnamed_addr global %union.A { i8* inttoptr (i64 12345 to i8*) }, align 8
+; CHECK: @l = dso_local local_unnamed_addr global i64 12345, align 8
+
+; Test derived from:
+;
+; union A {
+;   A(long long ll) : l(ll) {}
+;   void *p;
+;   long long l;
+; } u(12345);
+;
+; long long l = u.l;
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%union.A = type { i8* }
+
+$_ZN1AC2Ex = comdat any
+
+@u = dso_local global %union.A zeroinitializer, align 8
+@l = dso_local global i64 0, align 8
[e-mail]_ctors = appending global [1 x { i32, void ()*, i8* }] [{ i32, void ()*, i8* } { i32 65535, void ()* @_GLOBAL__sub_I_test.cpp, i8* null }]
+
+define internal void @__cxx_global_var_init() section ".text.startup" {
+  call void @_ZN1AC2Ex(%union.A* @u, i64 12345)
+  ret void
+}
+
+define linkonce_odr dso_local void @_ZN1AC2Ex(%union.A* %this, i64 %ll) unnamed_addr comdat align 2 {
+  %l = bitcast %union.A* %this to i64*
+  store i64 %ll, i64* %l, align 8
+  ret void
+}
+
+define internal void @__cxx_global_var_init.1() section ".text.startup" {
+  %1 = load i64, i64* bitcast (%union.A* @u to i64*), align 8
+  store i64 %1, i64* @l, align 8
+  ret void
+}
+
+define internal void @_GLOBAL__sub_I_test.cpp() section ".text.startup" {
+  call void @__cxx_global_var_init()
+  call void @__cxx_global_var_init.1()
+  ret void
+}