[MemorySSA] Don't treat lifetime.end as NoAlias

[nikic]

Summary

MemorySSA currently treats lifetime.end intrinsics as not aliasing anything. This breaks MemorySSA-based MemCpyOpt, because we'll happily move a read of a pointer below a lifetime.end intrinsic, as no clobber is reported.

I think the MemorySSA modelling here isn't correct. lifetime.end(p) has approximately the same effect as doing a memcpy(p, undef), and should be treated as a clobber.

This patch removes the special handling of lifetime.end, leaving alias analysis to handle it appropriately.

[fhahn]

I think this makes sense on a high level, but I am not sure about the exact reason for the current handling. Perhaps @asbirlea or @george.burgess.iv have more context on this?

[asbirlea]

I'm not familiar with the original reasoning, so here are some thoughts.

The test that's updated doesn't make sense to me as it was done originally. The load access for P after a lifetime.end is strange.

Where I'd see this being useful is in loop optimizations, for temporaries declared inside a loop. Going around the loop to determine if an access can be hoisted/sunk, would need to bypass the lifetime marker, otherwise the clobbering access would remain the phi. But then any loop transformation using this information to take the access out of the loop, would need to also consider the lifetime markers found inside the loop and move or remove them. It's possible this is already happening right now and the lifetime markers are removed as being dead code, and that's why we haven't encountered the issue.
So, while I think MSSA's special handling on its own makes sense, I don't think any transformation currently uses this in a proper way.

I'm running some testing to check if this impacts optimizations in a meaningful way.

[asbirlea]

This looks good!

llvm/lib/Analysis/MemorySSA.cpp

if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(DefInst)) {
     // These intrinsics will show up as affecting memory, but they are just
     // markers, mostly.
     //
     // FIXME: We probably don't actually want MemorySSA to model these at all
     // (including creating MemoryAccesses for them): we just end up inventing
     // clobbers where they don't really exist at all. Please see D43269 for
     // context.
     switch (II->getIntrinsicID()) {
-    case Intrinsic::lifetime_end:
     case Intrinsic::invariant_start:
     case Intrinsic::invariant_end:
     case Intrinsic::assume:
     case Intrinsic::experimental_noalias_scope_decl:
       return {false, NoAlias};
     case Intrinsic::dbg_addr:
     case Intrinsic::dbg_declare:
     case Intrinsic::dbg_label:
UpwardsMemoryQuery(const Instruction *Inst, const MemoryAccess *Access)
       : IsCall(isa<CallBase>(Inst)), Inst(Inst), OriginalAccess(Access) {
     if (!IsCall)
       StartingLoc = MemoryLocation::get(Inst);
   }
 };
 
 } // end anonymous namespace
 
-static bool lifetimeEndsAt(MemoryDef *MD, const MemoryLocation &Loc,
-                           BatchAAResults &AA) {
-  Instruction *Inst = MD->getMemoryInst();
-  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
-    switch (II->getIntrinsicID()) {
-    case Intrinsic::lifetime_end: {
-      MemoryLocation ArgLoc = MemoryLocation::getAfter(II->getArgOperand(1));
-      return AA.alias(ArgLoc, Loc) == MustAlias;
-    }
-    default:
-      return false;
-    }
-  }
-  return false;
-}
-
 template <typename AliasAnalysisType>
 static bool isUseTriviallyOptimizableToLiveOnEntry(AliasAnalysisType &AA,
                                                    const Instruction *I) {
   // If the memory can't be changed, then loads of the memory can't be
   // clobbered.
   if (auto *LI = dyn_cast<LoadInst>(I))
     return I->hasMetadata(LLVMContext::MD_invariant_load) ||
            AA.pointsToConstantMemory(MemoryLocation::get(LI));
while (UpperBound > LocInfo.LowerBound) {
           assert(UpperBound != 0);
           --UpperBound;
         }
         FoundClobberResult = true;
         break;
       }
 
       MemoryDef *MD = cast<MemoryDef>(VersionStack[UpperBound]);
-      // If the lifetime of the pointer ends at this instruction, it's live on
-      // entry.
-      if (!UseMLOC.IsCall && lifetimeEndsAt(MD, UseMLOC.getLoc(), *AA)) {
-        // Reset UpperBound to liveOnEntryDef's place in the stack
-        UpperBound = 0;
-        FoundClobberResult = true;
-        LocInfo.AR = MustAlias;
-        break;
-      }
       ClobberAlias CA = instructionClobbersQuery(MD, MU, UseMLOC, *AA);
       if (CA.IsClobber) {
         FoundClobberResult = true;
         LocInfo.AR = CA.AR;
         break;
       }
       --UpperBound;
     }

llvm/test/Analysis/MemorySSA/lifetime-simple.ll

 ; RUN: opt -basic-aa -print-memoryssa -verify-memoryssa -enable-new-pm=0 -analyze < %s 2>&1 | FileCheck %s
 ; RUN: opt -aa-pipeline=basic-aa -passes='print<memoryssa>,verify<memoryssa>' -disable-output < %s 2>&1 | FileCheck %s
-; This test checks a number of things:
-; First, the lifetime markers should not clobber any uses of Q or P.
-; Second, the loads of P are MemoryUse(LiveOnEntry) due to the placement of the markers vs the loads.
+; This test checks that lifetime markers are considered clobbers of %P,
+; and due to lack of noalias information, of %Q as well.
 
 define i8 @test(i8* %P, i8* %Q) {
 entry:
 ; CHECK:  1 = MemoryDef(liveOnEntry)
 ; CHECK-NEXT:   call void @llvm.lifetime.start.p0i8(i64 32, i8* %P)
   call void @llvm.lifetime.start.p0i8(i64 32, i8* %P)
 ; CHECK:  MemoryUse(1)
 ; CHECK-NEXT:   %0 = load i8, i8* %P
   %0 = load i8, i8* %P
 ; CHECK:  2 = MemoryDef(1)
 ; CHECK-NEXT:   store i8 1, i8* %P
   store i8 1, i8* %P
 ; CHECK:  3 = MemoryDef(2)
 ; CHECK-NEXT:   call void @llvm.lifetime.end.p0i8(i64 32, i8* %P)
   call void @llvm.lifetime.end.p0i8(i64 32, i8* %P)
-; CHECK:  MemoryUse(liveOnEntry)
+; CHECK:  MemoryUse(3)
 ; CHECK-NEXT:   %1 = load i8, i8* %P
   %1 = load i8, i8* %P
-; CHECK:  MemoryUse(2)
+; CHECK:  MemoryUse(3)
 ; CHECK-NEXT:   %2 = load i8, i8* %Q
   %2 = load i8, i8* %Q
   ret i8 %1
 }
 declare void @llvm.lifetime.start.p0i8(i64 %S, i8* nocapture %P) readonly
 declare void @llvm.lifetime.end.p0i8(i64 %S, i8* nocapture %P)

llvm/test/Transforms/MemCpyOpt/lifetime.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -O2 -S -enable-memcpyopt-memoryssa=0 | FileCheck %s --check-prefixes=CHECK,NO_MSSA
-; RUN: opt < %s -O2 -S -enable-memcpyopt-memoryssa=1 -verify-memoryssa | FileCheck %s --check-prefixes=CHECK,MSSA
+; RUN: opt < %s -O2 -S -enable-memcpyopt-memoryssa=0 | FileCheck %s
+; RUN: opt < %s -O2 -S -enable-memcpyopt-memoryssa=1 -verify-memoryssa | FileCheck %s
 
 ; performCallSlotOptzn in MemCpy should not exchange the calls to
 ; @llvm.lifetime.start and @llvm.memcpy.
 
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture readonly, i64, i1) #1
 declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture) #1
 declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture) #1
 
bb:
   call void @llvm.lifetime.start.p0i8(i64 16, i8* %tmp5)
   %tmp10 = getelementptr inbounds i8, i8* %tmp5, i64 7
   store i8 0, i8* %tmp10, align 1
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 8 %arg1, i8* align 8 %tmp5, i64 16, i1 false)
   call void @llvm.lifetime.end.p0i8(i64 16, i8* %tmp5)
   ret void
 }
 
-; FIXME: Miscompile.
 define void @memcpy_memcpy_across_lifetime(i8* noalias %p1, i8* noalias %p2, i8* noalias %p3) {
-; NO_MSSA-LABEL: @memcpy_memcpy_across_lifetime(
-; NO_MSSA-NEXT:    [[A:%.*]] = alloca [16 x i8], align 1
-; NO_MSSA-NEXT:    [[A8:%.*]] = getelementptr inbounds [16 x i8], [16 x i8]* [[A]], i64 0, i64 0
-; NO_MSSA-NEXT:    call void @llvm.lifetime.start.p0i8(i64 16, i8* nonnull [[A8]])
-; NO_MSSA-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 1 dereferenceable(16) [[A8]], i8* nonnull align 1 dereferenceable(16) [[P1:%.*]], i64 16, i1 false)
-; NO_MSSA-NEXT:    tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 1 dereferenceable(16) [[P1]], i8* nonnull align 1 dereferenceable(16) [[P2:%.*]], i64 16, i1 false)
-; NO_MSSA-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 1 dereferenceable(16) [[P2]], i8* nonnull align 1 dereferenceable(16) [[A8]], i64 16, i1 false)
-; NO_MSSA-NEXT:    call void @llvm.lifetime.end.p0i8(i64 16, i8* nonnull [[A8]])
-; NO_MSSA-NEXT:    tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 1 dereferenceable(16) [[P3:%.*]], i8* nonnull align 1 dereferenceable(16) [[P2]], i64 16, i1 false)
-; NO_MSSA-NEXT:    ret void
-;
-; MSSA-LABEL: @memcpy_memcpy_across_lifetime(
-; MSSA-NEXT:    [[A:%.*]] = alloca [16 x i8], align 1
-; MSSA-NEXT:    [[A8:%.*]] = getelementptr inbounds [16 x i8], [16 x i8]* [[A]], i64 0, i64 0
-; MSSA-NEXT:    call void @llvm.lifetime.start.p0i8(i64 16, i8* nonnull [[A8]])
-; MSSA-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 1 dereferenceable(16) [[A8]], i8* nonnull align 1 dereferenceable(16) [[P1:%.*]], i64 16, i1 false)
-; MSSA-NEXT:    tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 1 dereferenceable(16) [[P1]], i8* nonnull align 1 dereferenceable(16) [[P2:%.*]], i64 16, i1 false)
-; MSSA-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 1 dereferenceable(16) [[P2]], i8* nonnull align 1 dereferenceable(16) [[A8]], i64 16, i1 false)
-; MSSA-NEXT:    call void @llvm.lifetime.end.p0i8(i64 16, i8* nonnull [[A8]])
-; MSSA-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 1 dereferenceable(16) [[P3:%.*]], i8* nonnull align 1 dereferenceable(16) [[A8]], i64 16, i1 false)
-; MSSA-NEXT:    ret void
+; CHECK-LABEL: @memcpy_memcpy_across_lifetime(
+; CHECK-NEXT:    [[A:%.*]] = alloca [16 x i8], align 1
+; CHECK-NEXT:    [[A8:%.*]] = getelementptr inbounds [16 x i8], [16 x i8]* [[A]], i64 0, i64 0
+; CHECK-NEXT:    call void @llvm.lifetime.start.p0i8(i64 16, i8* nonnull [[A8]])
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 1 dereferenceable(16) [[A8]], i8* nonnull align 1 dereferenceable(16) [[P1:%.*]], i64 16, i1 false)
+; CHECK-NEXT:    tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 1 dereferenceable(16) [[P1]], i8* nonnull align 1 dereferenceable(16) [[P2:%.*]], i64 16, i1 false)
+; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 1 dereferenceable(16) [[P2]], i8* nonnull align 1 dereferenceable(16) [[A8]], i64 16, i1 false)
+; CHECK-NEXT:    call void @llvm.lifetime.end.p0i8(i64 16, i8* nonnull [[A8]])
+; CHECK-NEXT:    tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 1 dereferenceable(16) [[P3:%.*]], i8* nonnull align 1 dereferenceable(16) [[P2]], i64 16, i1 false)
+; CHECK-NEXT:    ret void
 ;
   %a = alloca [16 x i8]
   %a8 = bitcast [16 x i8]* %a to i8*
   call void @llvm.lifetime.start.p0i8(i64 16, i8* %a8)
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %a8, i8* %p1, i64 16, i1 false)
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %p1, i8* %p2, i64 16, i1 false)
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %p2, i8* %a8, i64 16, i1 false)
   call void @llvm.lifetime.end.p0i8(i64 16, i8* %a8)
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %p3, i8* %p2, i64 16, i1 false)
   ret void
 }
 
 attributes #1 = { argmemonly nounwind }