[InstCombine] Don't transfer BitCastInst at InstCombine pass when the user of BitCast is lifetime marker

[ChuanqiXu]

Summary

It is a usual pattern to get the lifetime marker of Instruction I:

SmallPtrSet<Instruction*, 4> LifetimeMarkers;
for (User *U : I->users()) {
    if ( U is a lifetime marker)
        LifetimeMarkers.insert(U);
    if (BitCastInst* BCI=dyn_cast<BitCastInst>(U)){
        for (User* BCIUser:BCI->users())
            if (BCIUser is a lifetime marker)
                LifetimeMarkers.insert(BCIUser);
    }
}

In another word, the lifetime marker of an instruction I is either a user of I or a user of a user of I which is a BitCastInst. Although I don't find any rule for this pattern, I find it in a lot of codes.

However, in the InstCombine pass, it would try to transfer BitCast to a GEP when the target type of BitCast could be transferred by the source type of BitCast, which would break this pattern.

So I try to Disable the transferring process when the user of BitCast is lifetime marker.

[nikic]

I don't think this is the right approach to the problem. Can you give some more information on which places in LLVM assume that only bitcasts feed into lifetime intrinsics?

[lebedev.ri]

In D84821#2183027, @nikic wrote:

I don't think this is the right approach to the problem.

Can you give some more information on which places in LLVM assume that only bitcasts feed into lifetime intrinsics?

I'm not sure any such assumption being made is sane. Those passes should be fixed instead.

[ChuanqiXu]

In D84821#2183027, @nikic wrote:

I don't think this is the right approach to the problem. Can you give some more information on which places in LLVM assume that only bitcasts feed into lifetime intrinsics?

From the CodeExtractor.cpp, CoroFrame.cpp and StackLifetime.cpp, I find such assumptions. I also find that there are other methods to collect lifetime marker of an instruction. For example, in the Inline Module, it finds among all the users of the instruction I to find which is used by lifetime marker. And in the InstCombineLoadStore.cpp, I find it collects lifetime marker by calculates the users with kind BitCast, GEP and AddrSpaceCastInst (which means there are cases which are not covered by this patch). What I want to say here is that the style of collecting lifetime marker seems a little out-of-order.

In D84821#2183271, @lebedev.ri wrote:

I'm not sure any such assumption being made is sane. Those passes should be fixed instead.

Yes. We can fix this problem by either fixing other passes or fixing this pass. We need find out that which one is more natural. In my thought, when I want to collect lifetime marker as a newbie here, I will go to see how the lifetime marker is created. So I find CreateLifetimeStart and CreateLifetimeEnd in LLVM and CreateCall ('lifetime_start' or lifetime_end`') in clang's CodeGen` module. In all of the methods, the logic is to judge whether the type of the source value is i8*. If the type of the source value is i8*, the Create* methods will create a direct call to lifetime intrinsics. Otherwise, the Create* methods will create a BitCast to convert the type of source value to i8*. So from the process, I think it is natural for code reader who is not so familiar with LLVM to think that he can collect lifetime marker by judge the instruction itself and the users who is BitCastInst.

[ChuanqiXu]

In D84821#2183795, @ChuanqiXu wrote:

In D84821#2183027, @nikic wrote:

I don't think this is the right approach to the problem. Can you give some more information on which places in LLVM assume that only bitcasts feed into lifetime intrinsics?

From the CodeExtractor.cpp, CoroFrame.cpp and StackLifetime.cpp, I find such assumptions. I also find that there are other methods to collect lifetime marker of an instruction. For example, in the Inline Module, it finds among all the users of the instruction I to find which is used by lifetime marker. And in the InstCombineLoadStore.cpp, I find it collects lifetime marker by calculates the users with kind BitCast, GEP and AddrSpaceCastInst (which means there are cases which are not covered by this patch). What I want to say here is that the style of collecting lifetime marker seems a little out-of-order.

In D84821#2183271, @lebedev.ri wrote:

I'm not sure any such assumption being made is sane. Those passes should be fixed instead.

Yes. We can fix this problem by either fixing other passes or fixing this pass. We need find out that which one is more natural. In my thought, when I want to collect lifetime marker as a newbie here, I will go to see how the lifetime marker is created. So I find CreateLifetimeStart and CreateLifetimeEnd in LLVM and CreateCall ('lifetime_start' or lifetime_end`') in clang's CodeGen` module. In all of the methods, the logic is to judge whether the type of the source value is i8*. If the type of the source value is i8*, the Create* methods will create a direct call to lifetime intrinsics. Otherwise, the Create* methods will create a BitCast to convert the type of source value to i8*. So from the process, I think it is natural for code reader who is not so familiar with LLVM to think that he can collect lifetime marker by judge the instruction itself and the users who is BitCastInst.

After I re-read the inline Module, I find it is not search for every user who is used by lifetime marker. Instead, inline Module uses the stripPointerCasts API to find the uses who are pointer casts, all-zero GEPs or aliases. I think it is a better practice to collect lifetime marker and lifetime marker user. So I agree with we should fix other passes who used the wrong pattern.

clang/test/CodeGen/aggregate-assign-call.c

struct S baz(int i, volatile int *j) {
   do {
     // O1: %[[P:[^ ]+]] = bitcast %struct.S* %[[TMP1_ALLOCA]] to i8*
     // O1-LEGACY: call void @llvm.lifetime.start.p0i8({{[^,]*}}, i8* %[[P]])
     // O1-NEWPM: call void @llvm.lifetime.start.p0i8({{[^,]*}}, i8* nonnull %[[P]])
     //
     // O1-LEGACY: %[[P:[^ ]+]] = bitcast %struct.S* %[[TMP1_ALLOCA]] to i8*
     // O1-LEGACY: call void @llvm.lifetime.end.p0i8({{[^,]*}}, i8* %[[P]])
     // O1-NEWPM: %[[TMP3:.*]] = bitcast %struct.S* %[[TMP2_ALLOCA]] to i8*
-    // O1-NEWPM: call void @llvm.lifetime.end.p0i8({{[^,]*}}, i8* nonnull %[[P]])
+    // O1-NEWPM: call void @llvm.lifetime.end.p0i8({{[^,]*}}, i8* nonnull %{{[0-9]}})
     //
     // O1-LEGACY: call void @foo_int(%struct.S* sret align 4 %[[TMP1_ALLOCA]],
     // O1-NEWPM: call void @foo_int(%struct.S* nonnull sret align 4 %[[TMP1_ALLOCA]],
     // O1: call void @llvm.memcpy
     // O1-LEGACY: %[[P:[^ ]+]] = bitcast %struct.S* %[[TMP1_ALLOCA]] to i8*
     // O1-LEGACY: call void @llvm.lifetime.end.p0i8({{[^,]*}}, i8* %[[P]])
     // O1-NEWPM: call void @llvm.lifetime.end.p0i8({{[^,]*}}, i8* nonnull %[[P]])
     // O1-LEGACY: %[[P:[^ ]+]] = bitcast %struct.S* %[[TMP2_ALLOCA]] to i8*

clang/test/CodeGen/temporary-lifetime-exceptions.cpp

 // RUN: %clang_cc1 %s -fexceptions -fcxx-exceptions -std=c++11 -O1 -triple x86_64 -emit-llvm -o - | FileCheck %s
 
 // lifetime.end should be invoked even if the destructor doesn't run due to an
 // exception thrown from previous ctor call.
 
 struct A { A(); ~A(); };
 A Baz(const A&);
 
 void Test1() {
   // CHECK-LABEL: @_Z5Test1v(
-  // CHECK: getelementptr
+  // CHECK: entry
+  // CHECK: bitcast
   // CHECK-NEXT: call void @llvm.lifetime.start.p0i8(i64 1, i8* nonnull [[TMP:[^ ]+]])
-  // CHECK-NEXT: getelementptr
+  // CHECK-NEXT: bitcast
   // CHECK-NEXT: call void @llvm.lifetime.start.p0i8(i64 1, i8* nonnull [[TMP1:[^ ]+]])
 
   // Normal exit
   // CHECK: call void @llvm.lifetime.end.p0i8(i64 1, i8* nonnull [[TMP1]])
   // CHECK-NEXT: call void @llvm.lifetime.end.p0i8(i64 1, i8* nonnull [[TMP]])
 
   // Exception exit
   // CHECK: call void @llvm.lifetime.end.p0i8(i64 1, i8* nonnull [[TMP1]])
   // CHECK-NEXT: call void @llvm.lifetime.end.p0i8(i64 1, i8* nonnull [[TMP]])
   Baz(Baz(A()));
 }

clang/test/CodeGenCXX/auto-var-init.cpp

 
 TEST_UNINIT(paddedpackednested, paddedpackednested);
 // CHECK-LABEL: @test_paddedpackednested_uninit()
 // CHECK:       %uninit = alloca %struct.paddedpackednested, align
 // CHECK-NEXT:  call void @{{.*}}used{{.*}}%uninit)
 // PATTERN-LABEL: @test_paddedpackednested_uninit()
 // PATTERN-O0: call void @llvm.memcpy{{.*}} @__const.test_paddedpackednested_uninit.uninit
 // PATTERN-O1: getelementptr
-// PATTERN-O1: call void @llvm.memset.p0i8.i64(i8* nonnull align 1 dereferenceable(10) %0, i8 [[I8]], i64 10, i1 false
+// PATTERN-O1: call void @llvm.memset.p0i8.i64(i8* nonnull align 1 dereferenceable(10) %1, i8 [[I8]], i64 10, i1 false
 // ZERO-LABEL: @test_paddedpackednested_uninit()
 // ZERO: call void @llvm.memset{{.*}}, i8 0,
 
 TEST_BRACES(paddedpackednested, paddedpackednested);
 // CHECK-LABEL: @test_paddedpackednested_braces()
 // CHECK:       %braces = alloca %struct.paddedpackednested, align [[ALIGN:[0-9]*]]
 // CHECK-NEXT:  bitcast
 // CHECK-NEXT:  call void @llvm.memset{{.*}}(i8* align [[ALIGN]] %{{.*}}, i8 0, i64 10, i1 false)

 
 TEST_UNINIT(tailpad4, tailpad[4]);
 // CHECK-LABEL: @test_tailpad4_uninit()
 // CHECK:       %uninit = alloca [4 x %struct.tailpad], align
 // CHECK-NEXT:  call void @{{.*}}used{{.*}}%uninit)
 // PATTERN-LABEL: @test_tailpad4_uninit()
 // PATTERN-O0: call void @llvm.memcpy{{.*}} @__const.test_tailpad4_uninit.uninit
 // PATTERN-O1: bitcast
-// PATTERN-O1: call void @llvm.memset{{.*}}({{.*}}0, i8 [[I8]], i64 16
+// PATTERN-O1: call void @llvm.memset{{.*}}({{.*}}1, i8 [[I8]], i64 16
 // ZERO-LABEL: @test_tailpad4_uninit()
 // ZERO: call void @llvm.memset{{.*}}, i8 0,
 
 TEST_BRACES(tailpad4, tailpad[4]);
 // CHECK-LABEL: @test_tailpad4_braces()
 // CHECK:       %braces = alloca [4 x %struct.tailpad], align [[ALIGN:[0-9]*]]
 // CHECK-NEXT:  bitcast
 // CHECK-NEXT:  call void @llvm.memset{{.*}}(i8* align [[ALIGN]] %{{.*}}, i8 0, i64 16, i1 false)

clang/test/CodeGenCXX/nrvo.cpp

X test2(bool B) {
 
   X x;
   X y;
   if (B)
     return y;
   return x;
 
   // CHECK: call {{.*}} @_ZN1XC1Ev
-  // CHECK-NEXT: {{.*}} getelementptr inbounds %class.X, %class.X* %y, i32 0, i32 0
+  // CHECK-NEXT: {{.*}} bitcast %class.X* %y to i8*
   // CHECK-NEXT: call void @llvm.lifetime.start
   // CHECK-NEXT: call {{.*}} @_ZN1XC1Ev
   // CHECK: call {{.*}} @_ZN1XC1ERKS_
   // CHECK: call {{.*}} @_ZN1XD1Ev
   // CHECK-NEXT: call void @llvm.lifetime.end
   // CHECK: call {{.*}} @_ZN1XD1Ev
   // CHECK-NEXT: call void @llvm.lifetime.end
   // CHECK: ret void

 #endif
 
 // rdar://problem/10430868
 // CHECK-LABEL: define void @_Z5test6v
 X test6() {
   X a __attribute__((aligned(8)));
   return a;
   // CHECK:      [[A:%.*]] = alloca [[X:%.*]], align 8
-  // CHECK-NEXT: [[PTR:%.*]] = getelementptr inbounds %class.X, %class.X* [[A]], i32 0, i32 0
+  // CHECK-NEXT: [[PTR:%.*]] = bitcast %class.X* [[A]] to i8*
   // CHECK-NEXT: call void @llvm.lifetime.start.p0i8(i64 1, i8* nonnull [[PTR]])
   // CHECK-NEXT: call {{.*}} @_ZN1XC1Ev([[X]]* nonnull [[A]])
   // CHECK-NEXT: call {{.*}} @_ZN1XC1ERKS_([[X]]* {{%.*}}, [[X]]* nonnull align {{[0-9]+}} dereferenceable({{[0-9]+}}) [[A]])
   // CHECK-NEXT: call {{.*}} @_ZN1XD1Ev([[X]]* nonnull [[A]])
   // CHECK-NEXT: call void @llvm.lifetime.end.p0i8(i64 1, i8* nonnull [[PTR]])
   // CHECK-NEXT: ret void
 }
 

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

for (auto It = OldPN->user_begin(), End = OldPN->user_end(); It != End; ) {
       }
     }
   }
 
   return RetVal;
 }
 
 Instruction *InstCombinerImpl::visitBitCast(BitCastInst &CI) {
+  auto isLifetimeMarker = [&](auto I){
+    if (IntrinsicInst* II = dyn_cast<IntrinsicInst>(I))
+      if (II->isLifetimeStartOrEnd())
+        return true;
+    return false;
+    /// Is this a bette style?
+    /// return isa<IntrinsicInst>(I) &&
+    //         cast<IntrinsicInst>(I)->isLifetimeStartOrEnd();
+  };
+
+  /// If all the users of BitCast is lifetime marker,
+  /// don't change it.
+  if (all_of(CI.users(), isLifetimeMarker))
+    return nullptr;
+
+  /// Clone CI for other User than lifetime marker to
+  /// enable possible optimization.
+  if (any_of(CI.users(), isLifetimeMarker))
+  {
+    /// Here must be some user of CI is not lifetime marker
+    BitCastInst* NewBitCast = cast<BitCastInst>(CI.clone());
+    NewBitCast->insertAfter(&CI);
+    SmallVector<User*, 4> UsersNotLifetimeMarker;
+    for (User* U:CI.users())
+      if (!isLifetimeMarker(U))
+        UsersNotLifetimeMarker.push_back(U);
+
+    for (User* U:UsersNotLifetimeMarker)
+      U->replaceUsesOfWith(&CI, NewBitCast);
+
+    Worklist.add(NewBitCast);
+    return nullptr;
+  }
+
   // If the operands are integer typed then apply the integer transforms,
   // otherwise just apply the common ones.
   Value *Src = CI.getOperand(0);
   Type *SrcTy = Src->getType();
   Type *DestTy = CI.getType();
 
   // Get rid of casts from one type to the same type. These are useless and can
   // be replaced by the operand.

llvm/test/Transforms/InstCombine/bitcast-lifetime.ll

+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+%char.array = type { [500 x i8] }
+declare void @consume(%char.array*)
+declare void @consume.i8.ptr(i8*)
+
+; CHECK-LABEL: @bitcast_to_lifetime_marker_i8_array(
+; CHECK: %cast = bitcast %char.array* %a to i8*
+
+define void @bitcast_to_lifetime_marker_i8_array(){
+  %a = alloca %char.array
+  %cast = bitcast %char.array* %a to i8*
+  call void @llvm.lifetime.start.p0i8(i64 500, i8* %cast)
+  call void @consume(%char.array* %a)
+  call void @llvm.lifetime.end.p0i8(i64 500, i8* %cast)
+  ret void
+}
+
+; CHECK-LABEL: @bitcast_to_lifetime_marker_other_use(
+; CHECK: %cast = bitcast %char.array* %a to i8*
+; CHECK: %{{.*}} = getelementptr inbounds %char.array, %char.array*
+
+define void @bitcast_to_lifetime_marker_other_use(){
+  %a = alloca %char.array
+  %cast = bitcast %char.array* %a to i8*
+  call void @llvm.lifetime.start.p0i8(i64 500, i8* %cast)
+  call void @consume(%char.array* %a)
+  call void @consume.i8.ptr(i8* %cast)
+  call void @llvm.lifetime.end.p0i8(i64 500, i8* %cast)
+  ret void
+}
+
+declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture)
+declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture)
 No newline at end of file

llvm/test/Transforms/MemCpyOpt/memcpy-to-memset-with-lifetimes.ll

 
 }
 
 define void @bar([8 x i64]* noalias nocapture sret dereferenceable(64) %sret, [8 x i64]* noalias nocapture dereferenceable(64) %out) {
 ; CHECK-LABEL: @bar(
 ; CHECK-NEXT:  entry-block:
 ; CHECK-NEXT:    [[A:%.*]] = alloca [8 x i64], align 8
 ; CHECK-NEXT:    [[A_CAST:%.*]] = bitcast [8 x i64]* [[A]] to i8*
+; CHECK-NEXT:    [[A_CAST_COPY:%.*]] = bitcast
 ; CHECK-NEXT:    call void @llvm.lifetime.start.p0i8(i64 64, i8* nonnull [[A_CAST]])
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* nonnull align 8 dereferenceable(64) [[A_CAST]], i8 0, i64 64, i1 false)
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* nonnull align 8 dereferenceable(64) [[A_CAST_COPY]], i8 0, i64 64, i1 false)
 ; CHECK-NEXT:    [[SRET_CAST:%.*]] = bitcast [8 x i64]* [[SRET:%.*]] to i8*
 ; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* nonnull align 8 dereferenceable(64) [[SRET_CAST]], i8 0, i64 64, i1 false)
-; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* nonnull align 8 dereferenceable(32) [[A_CAST]], i8 42, i64 32, i1 false)
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* nonnull align 8 dereferenceable(32) [[A_CAST_COPY]], i8 42, i64 32, i1 false)
 ; CHECK-NEXT:    [[OUT_CAST:%.*]] = bitcast [8 x i64]* [[OUT:%.*]] to i8*
-; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 8 dereferenceable(64) [[OUT_CAST]], i8* nonnull align 8 dereferenceable(64) [[A_CAST]], i64 64, i1 false)
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 8 dereferenceable(64) [[OUT_CAST]], i8* nonnull align 8 dereferenceable(64) [[A_CAST_COPY]], i64 64, i1 false)
 ; CHECK-NEXT:    call void @llvm.lifetime.end.p0i8(i64 64, i8* nonnull [[A_CAST]])
 ; CHECK-NEXT:    ret void
 ;
 entry-block:
   %a = alloca [8 x i64], align 8
   %a.cast = bitcast [8 x i64]* %a to i8*
   call void @llvm.lifetime.start.p0i8(i64 64, i8* %a.cast)
   call void @llvm.memset.p0i8.i64(i8* align 8 %a.cast, i8 0, i64 64, i1 false)