[MemorySSA] Be less aggressive with @llvm.lifetime.start

[george.burgess.iv]

Summary

Primarily uploading to get your opinion on whether this is a MSSA bug, or insanity that shouldn't exist in IR.

After inlining, EarlyCSE may be given code like:

; snip
%.fca.0.gep.i = getelementptr inbounds [2 x i64], [2 x i64]* %retval.i, i64 0, i64 0
%.fca.1.gep.i = getelementptr inbounds [2 x i64], [2 x i64]* %retval.i, i64 0, i64 1
%.fca.1.load.i = load i64, i64* %.fca.1.gep.i, align 8
call void @llvm.lifetime.end.p0i8(i64 16, i8* %2)
%23 = bitcast %class.SkRecorder* %this to %class.SkCanvas*
call void @llvm.lifetime.start.p0i8(i64 16, i8* %2) #8
store i64 0, i64* %.fca.0.gep.i, align 8
store i64 %.fca.1.load.i, i64* %.fca.1.gep.i, align 8
call void @whatever(%class.SkCanvas* %23, %struct.SkIRect* dereferenceable(16) %tmpcast.i)
; snip

...where %2 and %tmpcast.i are bitcasted %retval.i pointers. This is a pretty roundabout way of saying "store 0 into %.fca.0.gep.i", but doesn't venture into illegal IR AFAICT.

The issue is that "%fca.1.load.i MustAlias %2" is false, so MSSA doesn't treat it as a clobber for the store into %.fca.1.gep.i. Hence, EarlyCSE considers the last store to be redundant, and eliminates it. Later passes then eliminate the now-dead %.fca.1.load.i, then the store that paired with %.fca.1.load.i dies, presumably due to being unused before lifetime.end, etc.

I imagine we can get into a similar situation if we had code like:

%foo = select %whatever, %ptr1, %ptr2 ; %ptr1 NoAlias %ptr2 
%f = load i8, i8* %foo
call void @llvm.lifetime.end.p0i8(i64 8, i8* %ptr1)
call void @llvm.lifetime.start.p0i8(i64 8, i8* %ptr1)
store i8, i8* %foo
call void @use(i8* %foo)

...We'd eliminate the store, an optimization after us turns %whatever into a constant truthy value, ...

[• dberlin]

Oh god i've been away from LLVM too long.
So, i don't know what we *want* the semantic to be.
Can you print the memoryssa dumps for this for me?
Add hal, etc, get his thoughts

One thing to realize is that the langref doesn't just say that lifetime.start means "anything before this is undefined".
It actually says anything before this *is known never to be used*
Which, imho, is stronger.

"llvm.lifetime.start’ Intrinsic
...
This intrinsic indicates that before this point in the code, the value of the memory pointed to by ptr is dead. This means that it is known to never be used and has an undefined value."

Essentially, lifetime.start/end, even for the same pointer, create things that are very two distinctly different memory objects, regardless of if they are at the same place in memory, and the compiler is free to treat them that way, at least, as these intrinsics go.

[george.burgess.iv]

+hal and philip, as requested. +gberry in case they have any earlycse thoughts

So, i don't know what we *want* the semantic to be.

Without much knowledge of the implications elsewhere, something like: "lifetime.start intrinsics represent a non-volatile, non-atomic clobber of the given range of memory for the purposes of analysis. Anything loaded from this range that has not been stored to since the lifetime.start is undef" doesn't sound insane to me.

(At least, I don't see why we need to give clobber mechanics to both lifetime.start and lifetime.end, given that AIUI they're meant to be balanced)

Can you print the memoryssa dumps for this for me?

define void @bar(i8* %foo) {
entry:
  %z = bitcast i8* %foo to i32*
  %p = getelementptr inbounds i32, i32* %z, i64 1
; MemoryUse(liveOnEntry)
  %a = load i32, i32* %p
; 1 = MemoryDef(liveOnEntry)
  call void @llvm.lifetime.end.p0i8(i64 8, i8* %foo)
; 2 = MemoryDef(1)
  call void @llvm.lifetime.start.p0i8(i64 8, i8* %foo)
; 3 = MemoryDef(2)
  store i32 0, i32* %z
; 4 = MemoryDef(3)
  store i32 %a, i32* %p
  ret void
}

It's all pretty straightforward IMO; the problematic interaction with EarlyCSE is that we don't report that 4 is clobbered by 2, so AIUI it sees 4 as a redundant store.

Essentially, lifetime.start/end, even for the same pointer, create things that are very two distinctly different memory objects, regardless of if they are at the same place in memory, and the compiler is free to treat them that way, at least, as these intrinsics go.

Agreed. So, at it's core, the DSE by EarlyCSE is effectively saying "I'm eliminating this store to object $X because it's a load of a value from object $Y that happens to reside at the same memory location."

(I realize I'm saying EarlyCSE a lot in a MSSA patch. The reason I've fixed it here is that I believe that, at the very least, MSSA users should have to opt into a 'be aggressive with lifetime intrinsics' footgun. Until there's complaining, ...)

[nlopes]

Given that the original motivation for these lifetime intrinsincs was for inlining, I don't see a reason to support multiple start/ends on the same pointer.
Or is there another new use case that I'm unaware of? Also, we don't have any transformation splitting (or even shrinking I think) these lifetimes.

[george.burgess.iv]

So, we have to support them at the moment because, at the very least, the inliner will merge allocas with non-overlapping lifetimes (see mergeInlinedArrayAllocas in lib/Transforms/IPO/Inliner.cpp). I was surprised when I saw this. :)

---

Aside: it looks like the discussion on the email thread didn't get mirrored to this review (http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20180212/526068.html + the 2 following comments).

tl;dr: we're wondering whether MSSA should care about these objects as they exist in the lifetime system, or if it should just care about memory locations. In the former case, it seems we'll either have to end up inventing clobbers that don't exist (which is a path full of sadness, apparently), or we'll have to tack on a whole different subsystem that should probably be split out. In the latter case, we move this burden to higher-level passes that know they need to care. I prefer the latter, and I think Danny does, too, but we'd like the feedback of hal and/or philip before committing to that.

[• dberlin]

To be clear, i think the lifetime system has enough issues that trying to cover it with MemorySSA as it currently exists wouldn't end up well.
Things that want to care about and try to optimize around lifetimes can do that.
Intermixing object lifetime and aliasing results in the same system will, IMHO, give you a bad time.

(though we could provide a separate def-use chain in memoryssa to try to make sense of the lifetimes if we wanted to, but it'd be hard to update given lifetimes are not that well specified)

As far as i'm aware, it's legal to do whatever you want and then drop the intrinsics
IE reuse of a load after lifetime.end is fine as long as you kill the lifetime.end

If not, IMHO, we have bigger problems.

@nlopes It's worse than you might think. We allow, and try to make sense of, stuff like this:

  A
/   \
B   C
\   /
  D 
  |
  E

A:
lifetime.start(16, %foo)
B:
lifetime.end(16, %foo)
lifetime.start(16, %foo)
C:
D:
use %foo
E:
lifetime.end(16, %foo)

It's your job to realize the lifetime.end in %E ends the lifetime of two completely different memory objects..
Or does it?
Who knows!

There's a significant set of hacks in stack coloring/etc to handle the degenerate cases.
Splitting can also occur by accident. There is no lifetime verifier or anything, so what has been allowed has degraded over time.

Hopefully some day someone will clean this up with a well defined lifetime system, using explicit tokens and a verifier.

[nlopes]

Thanks @dberlin and @george.burgess.iv. I wasn't aware of this issue.

Sometime ago we were thinking along these lines:

• change alloca to do lifetime.start by default -- just like now
• add a bit to alloca to specify that lifetime didn't start yet. (the current semantics is weird; we need to see the future to decide whether alloca is valid or not)
• make lifetime.start return the input pointer, but now valid.

e.g.:
%a = alloca i32, invalid
%p = call @lifetime.start %a
load %p ; OK
load %a ; not OK; invalid pointer

call @lifetime.end %p
load %p ; invalid

I think in this model it's possible to support multiple starts because they return a pointer that is valid until end. Didn't think much about that because I wasn't aware of the need.
While this scheme makes start more memory SSA-like, it still leaves lifetime.end having implicit side-effects. But it's a start, at least.

[george.burgess.iv]

Gentle ping for confirmation from Hal or Philip that we're OK with ignoring lifetime intrinsics (as they exist today) in MSSA. :)

[george.burgess.iv]

ping :)

[george.burgess.iv]

Ping :)

[george.burgess.iv]

Ping :)

[efriedma]

What happened to this patch? It looks like it's a fix for a miscompile?

[george.burgess.iv]

Currently, MSSA treats lifetime intrinsics as clobbers, even though they're technically not. This patch would further solidify that behavior, which might not be a good thing (e.g. there's a good argument that we shouldn't be treating lifetime intrinsics as clobbers in the first place). I'm happy to rip out what few lifetime-related pieces MSSA has, but before doing so:

• I'd like an ack from a owner (hal/reames) that this is a direction we're comfortable with supporting, and
• we'd need to vet that users of MSSA aren't relying on this behavior (EarlyCSE apparently is, probably implicitly). If they are, we'd need to fix that. :)

To your point, I'm fine with submitting this as is + picking it over to 7.0, as long as I can put a big, loud "FIXME: Lifetime intrinsics probably won't always be here," in the code.

If we do think that pretending lifetime.starts are clobbers (or similar) is overall the best way forward, then sure, this patch works and is the correct fix for the miscompile.

[george.burgess.iv]

(FWIW, I plan to commit a workaround like this tomorrow with said big scary comment, assuming no complaints appear before then. Like said, I'm more than happy to discuss the ideal path to take here even after that lands. But this is a known miscompile with a trivial workaround that should presumably also find its way into the release branch, so...)

[george.burgess.iv]

Workaround committed as r339411

lib/Analysis/MemorySSA.cpp

static bool instructionClobbersQuery(MemoryDef *MD,
                                      const Instruction *UseInst,
                                      AliasAnalysis &AA) {
   Instruction *DefInst = MD->getMemoryInst();
   assert(DefInst && "Defining instruction not actually an instruction");
   ImmutableCallSite UseCS(UseInst);
 
   if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(DefInst)) {
     // These intrinsics will show up as affecting memory, but they are just
-    // markers.
+    // markers, mostly.
     switch (II->getIntrinsicID()) {
     case Intrinsic::lifetime_start:
       if (UseCS)
         return false;
-      return AA.isMustAlias(MemoryLocation(II->getArgOperand(1)), UseLoc);
+      return !AA.isNoAlias(MemoryLocation(II->getArgOperand(1)), UseLoc);
     case Intrinsic::lifetime_end:
     case Intrinsic::invariant_start:
     case Intrinsic::invariant_end:
     case Intrinsic::assume:
       return false;
     default:
       break;
     }

test/Transforms/EarlyCSE/memoryssa.ll

 ; CHECK-NOMEMSSA-LABEL: end:
 end:
 ; CHECK-NOT: load
 ; CHECK-NOMEMSSA: load
   %v2 = load i32, i32* @G1
   store i32 %v2, i32* @G3
   ret void
 }
+
+;; Check that we respect lifetime.start/lifetime.end intrinsics when deleting
+;; stores that, without the lifetime calls, would be writebacks.
+; CHECK-LABEL: @test_writeback_lifetimes(
+; CHECK-NOMEMSSA-LABEL: @test_writeback_lifetimes(
+define void @test_writeback_lifetimes(i32* %p) {
+entry:
+  %q = getelementptr i32, i32* %p, i64 1
+  %pv = load i32, i32* %p
+  %qv = load i32, i32* %q
+  call void @llvm.lifetime.end.p0i8(i64 8, i32* %p)
+  call void @llvm.lifetime.start.p0i8(i64 8, i32* %p)
+  ; CHECK: store i32 %pv
+  ; CHECK-NOMEMSSA-LABEL: store i32 %pv
+  store i32 %pv, i32* %p
+  ; CHECK: store i32 %qv, i32* %q
+  ; CHECK-NOMEMSSA-LABEL: store i32 %qv, i32* %q
+  store i32 %qv, i32* %q
+  ret void
+}
+
+;; Check that we respect lifetime.start/lifetime.end intrinsics when deleting
+;; stores that, without the lifetime calls, would be writebacks.
+; CHECK-LABEL: @test_writeback_lifetimes_multi_arg(
+; CHECK-NOMEMSSA-LABEL: @test_writeback_lifetimes_multi_arg(
+define void @test_writeback_lifetimes_multi_arg(i32* %p, i32* %q) {
+entry:
+  %pv = load i32, i32* %p
+  %qv = load i32, i32* %q
+  call void @llvm.lifetime.end.p0i8(i64 8, i32* %p)
+  call void @llvm.lifetime.start.p0i8(i64 8, i32* %p)
+  ; CHECK: store i32 %pv
+  ; CHECK-NOMEMSSA-LABEL: store i32 %pv
+  store i32 %pv, i32* %p
+  ; CHECK: store i32 %qv, i32* %q
+  ; CHECK-NOMEMSSA-LABEL: store i32 %qv, i32* %q
+  store i32 %qv, i32* %q
+  ret void
+}
+
+declare void @llvm.lifetime.end.p0i8(i64, i32*)
+declare void @llvm.lifetime.start.p0i8(i64, i32*)

unittests/Analysis/MemorySSA.cpp

TEST_F(MemorySSATest, Irreducible) {
   MemorySSAUpdater Updater(&MSSA);
   // Create the load memory acccess
   LoadInst *LoadInst = B.CreateLoad(FirstArg);
   MemoryUse *LoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(
       LoadInst, nullptr, AfterLoopBB, MemorySSA::Beginning));
   Updater.insertUse(LoadAccess);
   MSSA.verifyMemorySSA();
 }
+
+TEST_F(MemorySSATest, LifetimeMarkersAreClobbers) {
+  // Example code:
+  // define void @a(i8* %foo) {
+  //   %bar = getelementptr i8, i8* %foo, i64 1
+  //   store i8 0, i8* %foo
+  //   store i8 0, i8* %bar
+  //   call void @llvm.lifetime.end.p0i8(i64 8, i32* %p)
+  //   call void @llvm.lifetime.start.p0i8(i64 8, i32* %p)
+  //   store i8 0, i8* %foo
+  //   store i8 0, i8* %bar
+  //   ret void
+  // }
+  //
+  // Patterns like this are possible after inlining; the stores to %foo and %bar
+  // should both be clobbered by the lifetime.start call if they're dominated by
+  // it.
+
+  IRBuilder<> B(C);
+  F = Function::Create(
+      FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
+      GlobalValue::ExternalLinkage, "F", &M);
+
+  // Make blocks
+  BasicBlock *Entry = BasicBlock::Create(C, "entry", F);
+
+  B.SetInsertPoint(Entry);
+  Value *Foo = &*F->arg_begin();
+
+  Value *Bar = B.CreateGEP(Foo, B.getInt64(1), "bar");
+
+  B.CreateStore(B.getInt8(0), Foo);
+  B.CreateStore(B.getInt8(0), Bar);
+
+  auto GetLifetimeIntrinsic = [&](Intrinsic::ID ID) {
+    return Intrinsic::getDeclaration(&M, ID, {Foo->getType()});
+  };
+
+  B.CreateCall(GetLifetimeIntrinsic(Intrinsic::lifetime_end),
+               {B.getInt64(2), Foo});
+  Instruction *LifetimeStart = B.CreateCall(
+      GetLifetimeIntrinsic(Intrinsic::lifetime_start), {B.getInt64(2), Foo});
+
+  Instruction *FooStore = B.CreateStore(B.getInt8(0), Foo);
+  Instruction *BarStore = B.CreateStore(B.getInt8(0), Bar);
+
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+
+  MemoryAccess *LifetimeStartAccess = MSSA.getMemoryAccess(LifetimeStart);
+  ASSERT_NE(LifetimeStartAccess, nullptr);
+
+  MemoryAccess *FooAccess = MSSA.getMemoryAccess(FooStore);
+  ASSERT_NE(FooAccess, nullptr);
+
+  MemoryAccess *BarAccess = MSSA.getMemoryAccess(BarStore);
+  ASSERT_NE(BarAccess, nullptr);
+
+  MemoryAccess *FooClobber =
+      MSSA.getWalker()->getClobberingMemoryAccess(FooAccess);
+  EXPECT_EQ(FooClobber, LifetimeStartAccess);
+
+  MemoryAccess *BarClobber =
+      MSSA.getWalker()->getClobberingMemoryAccess(BarAccess);
+  EXPECT_EQ(BarClobber, LifetimeStartAccess);
+}