[InstCombine] avoid crash from deleting an instruction that still has uses (PR43723)

[spatel]

Summary

This whole thing seems fragile, but I've never looked at this code before this.

We gather a set of white-listed instructions in isAllocSiteRemovable() and then replace/erase them. But we don't know in general if the instructions in the set have uses amongst themselves, so order of deletion makes a difference.

There's already a special-case for the llvm.objectsize intrinsic, so add another for llvm.invariant.end.

Should fix:
https://bugs.llvm.org/show_bug.cgi?id=43723

[efriedma]

How confident are we that there aren't other uses of the return value of llvm.invariant.start?

[spatel]

In D69977#1739212, @efriedma wrote:

How confident are we that there aren't other uses of the return value of llvm.invariant.start?

Personally, I'm not confident because I haven't looked at these before:
http://llvm.org/docs/LangRef.html#memory-use-markers

But based on my initial reading, only invariant.end is meant to use invariant.start? We could assert that the 'end' has a corresponding 'start' and that it is the only user?

[spatel]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

2332–2336

For reference - these are the potential intrinsics that we can encounter in the code below. The 'default' case says we can't see anything outside of this set.

[efriedma]

I'd be more comfortable if we actually verified the uses of the invariant.start.

(As far as I can tell, the other possible instructions/intrinsics are either explicitly handled, or have a void return value.)

[spatel]

Patch updated:
Try harder to verify that a llvm.invariant.start is used as expected by llvm.invariant.end. If so, delete both at the same time. If not, don't try to delete the 'start'.

[efriedma]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

2412

Is it not too late here? I would have thought we need to check in isAllocSiteRemovable.

[spatel]

Patch updated:
Don't put an unexpected llvm.invariant.start in the kill list to begin with.

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

2412

I'm not imagining how it would fail, but checking sooner definitely seems more efficient than nested loops. Will change.

[efriedma]

LGTM

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

for (User *U : PI->users()) {
 
           case Intrinsic::memmove:
           case Intrinsic::memcpy:
           case Intrinsic::memset: {
             MemIntrinsic *MI = cast<MemIntrinsic>(II);
             if (MI->isVolatile() || MI->getRawDest() != PI)
               return false;
             LLVM_FALLTHROUGH;
           }
-          case Intrinsic::invariant_start:
           case Intrinsic::invariant_end:
           case Intrinsic::lifetime_start:
           case Intrinsic::lifetime_end:
           case Intrinsic::objectsize:
             Users.emplace_back(I);
             continue;
+          case Intrinsic::invariant_start:
+            // Only delete this if it has no uses or a single 'end' use.
+            if (I->use_empty())
+              Users.emplace_back(I);
+            else if (I->hasOneUse() &&
+                     match(I->user_back(),
+                           m_Intrinsic<Intrinsic::invariant_end>()))
+              Users.emplace_back(I);
+            continue;
           }
         }
 
         if (isFreeCall(I, TLI)) {
           Users.emplace_back(I);
           continue;
         }
         return false;
Instruction *InstCombiner::visitAllocSite(Instruction &MI) {
   std::unique_ptr<DIBuilder> DIB;
   if (isa<AllocaInst>(MI)) {
     DIIs = FindDbgAddrUses(&MI);
     DIB.reset(new DIBuilder(*MI.getModule(), /*AllowUnresolved=*/false));
   }
 
   if (isAllocSiteRemovable(&MI, Users, &TLI)) {
     for (unsigned i = 0, e = Users.size(); i != e; ++i) {
-      // Lowering all @llvm.objectsize calls first because they may
-      // use a bitcast/GEP of the alloca we are removing.
       if (!Users[i])
        continue;
 
       Instruction *I = cast<Instruction>(&*Users[i]);
-
       if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
+        // Lowering all @llvm.objectsize calls first because they may
+        // use a bitcast/GEP of the alloca we are removing.
         if (II->getIntrinsicID() == Intrinsic::objectsize) {
           Value *Result =
               lowerObjectSizeCall(II, DL, &TLI, /*MustSucceed=*/true);
           replaceInstUsesWith(*I, Result);
           eraseInstFromFunction(*I);
           Users[i] = nullptr; // Skip examining in the next loop.
         }
+        // Erase llvm.invariant.end because we expect that it uses an
+        // llvm.invariant.start that we will remove below.
+        if (II->getIntrinsicID() == Intrinsic::invariant_end) {
+          eraseInstFromFunction(*I);
+          Users[i] = nullptr; // Skip examining in the next loop.
+        }
       }
     }
     for (unsigned i = 0, e = Users.size(); i != e; ++i) {
       if (!Users[i])
         continue;
 
       Instruction *I = cast<Instruction>(&*Users[i]);
 

llvm/test/Transforms/InstCombine/builtin-object-size-ptr.ll

;
   %buf1 = getelementptr inbounds %struct.V, %struct.V* %var, i32 0, i32 0
   %arrayidx = getelementptr inbounds [10 x i8], [10 x i8]* %buf1, i64 0, i64 1
   %t1 = call i64 @llvm.objectsize.i64.p0i8(i8* %arrayidx, i1 false)
   %conv = trunc i64 %t1 to i32
   call void @llvm.lifetime.end.p0i8(i64 28, i8* %t0) #3
   ret i32 %conv
 }
 
+; This used to crash while erasing instructions:
+; https://bugs.llvm.org/show_bug.cgi?id=43723
+
+define void @PR43723() {
+; CHECK-LABEL: @PR43723(
+; CHECK-NEXT:    ret void
+;
+  %tab = alloca [10 x i8], align 16
+  %t0 = bitcast [10 x i8]* %tab to i8*
+  call void @llvm.memset.p0i8.i64(i8* align 16 %t0, i8 9, i64 10, i1 false)
+  %t1 = call {}* @llvm.invariant.start.p0i8(i64 10, i8* align 16 %t0)
+  call void @llvm.invariant.end.p0i8({}* %t1, i64 10, i8* align 16 %t0)
+  ret void
+
+  uselistorder i8* %t0, { 1, 0, 2 }
+}
+
+define void @unknown_use_of_invariant_start({}** %p) {
+; CHECK-LABEL: @unknown_use_of_invariant_start(
+; CHECK-NEXT:    [[T1:%.*]] = call {}* @llvm.invariant.start.p0i8(i64 10, i8* align 16 undef)
+; CHECK-NEXT:    store {}* [[T1]], {}** [[P:%.*]], align 8
+; CHECK-NEXT:    ret void
+;
+  %tab = alloca [10 x i8], align 16
+  %t0 = bitcast [10 x i8]* %tab to i8*
+  call void @llvm.memset.p0i8.i64(i8* align 16 %t0, i8 9, i64 10, i1 false)
+  %t1 = call {}* @llvm.invariant.start.p0i8(i64 10, i8* align 16 %t0)
+  call void @llvm.invariant.end.p0i8({}* %t1, i64 10, i8* align 16 %t0)
+  store {}* %t1, {}** %p
+  ret void
+}
+
 declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture) #1
 declare i64 @llvm.objectsize.i64.p0i8(i8*, i1) #2
 declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture) #1
+declare void @llvm.memset.p0i8.i64(i8* nocapture writeonly, i8, i64, i1 immarg) #0
+declare {}* @llvm.invariant.start.p0i8(i64 immarg, i8* nocapture) #0
+declare void @llvm.invariant.end.p0i8({}*, i64 immarg, i8* nocapture) #0