Support for lifetime begin/end markers in the use optimizer

[• dberlin]

Summary

Depends on D23072

[• dberlin]

• Remove dead comment

[• dberlin]

Tests coming.
George, i also am not clear on the proper way to integrate this into the walker and clobber checker :)

[• dberlin]

• Fix bug, add test

[• dberlin]

• Reword

[george.burgess.iv]

LGTM with nits; thanks!

lib/Transforms/Utils/MemorySSA.cpp

180 ↗

(On Diff #66534)

Please kill these brackets

181 ↗

(On Diff #66534)

return AA.isMustAlias(...);?

test/Transforms/Util/MemorySSA/lifetime-simple.ll

2 ↗

(On Diff #66534)

Please add a newline after this line

10 ↗

(On Diff #66534)

Is there a reason these aren't vanilla CHECKs?

(If not, please also add the ; CHECK-NEXT: %0 = load ... after each check for MemoryDef/MemoryUse, for consistency with the other tests)

[• dberlin]

Rebase

llvm/trunk/lib/Transforms/Utils/MemorySSA.cpp

struct UpwardsMemoryQuery {
 
   UpwardsMemoryQuery(const Instruction *Inst, const MemoryAccess *Access)
       : IsCall(ImmutableCallSite(Inst)), Inst(Inst), OriginalAccess(Access) {
     if (!IsCall)
       StartingLoc = MemoryLocation::get(Inst);
   }
 };
 
+static bool lifetimeEndsAt(MemoryDef *MD, const MemoryLocation &Loc,
+                           AliasAnalysis &AA) {
+  Instruction *Inst = MD->getMemoryInst();
+  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
+    switch (II->getIntrinsicID()) {
+      case Intrinsic::lifetime_start:
+      case Intrinsic::lifetime_end:
+        return AA.isMustAlias(MemoryLocation(II->getArgOperand(1)), Loc);
+    default:
+      return false;
+    }
+  }
+  return false;
+}
+
 static bool instructionClobbersQuery(MemoryDef *MD,
                                      const MemoryLocation &UseLoc,
                                      const Instruction *UseInst,
                                      AliasAnalysis &AA) {
   Instruction *DefInst = MD->getMemoryInst();
   assert(DefInst && "Defining instruction not actually an instruction");
 
+  if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(DefInst)) {
+    // These intrinsics will show up as affecting memory, but they are just
+    // markers.
+    switch (II->getIntrinsicID()) {
+    case Intrinsic::lifetime_start:
+    case Intrinsic::lifetime_end:
+    case Intrinsic::invariant_start:
+    case Intrinsic::invariant_end:
+    case Intrinsic::assume:
+      return false;
+    default:
+      break;
+    }
+  }
+
   ImmutableCallSite UseCS(UseInst);
   if (UseCS) {
     ModRefInfo I = AA.getModRefInfo(DefInst, UseCS);
     return I != MRI_NoModRef;
   }
   return AA.getModRefInfo(DefInst, UseLoc) & MRI_Mod;
 }
 
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;
+        break;
+      }
       if (instructionClobbersQuery(MD, MU, UseMLOC, *AA)) {
         FoundClobberResult = true;
         break;
       }
       --UpperBound;
     }
     // At the end of this loop, UpperBound is either a clobber, or lower bound
     // PHI walking may cause it to be < LowerBound, and in fact, < LastKill.

llvm/trunk/test/Transforms/Util/MemorySSA/lifetime-simple.ll

+; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -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.
+
+define i8 @test(i8* %P, i8* %Q) {
+entry:
+; CHECK:  1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT:   call void @llvm.lifetime.start(i64 32, i8* %P)
+  call void @llvm.lifetime.start(i64 32, i8* %P)
+; CHECK:  MemoryUse(liveOnEntry)
+; 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(i64 32, i8* %P)
+  call void @llvm.lifetime.end(i64 32, i8* %P)
+; CHECK:  MemoryUse(liveOnEntry)
+; CHECK-NEXT:   %1 = load i8, i8* %P
+  %1 = load i8, i8* %P
+; CHECK:  MemoryUse(2)
+; CHECK-NEXT:   %2 = load i8, i8* %Q
+  %2 = load i8, i8* %Q
+  ret i8 %1
+}
+declare void @llvm.lifetime.start(i64 %S, i8* nocapture %P) readonly
+declare void @llvm.lifetime.end(i64 %S, i8* nocapture %P)