[MemorySSA] Support invariant.group metadata

[aeubanks]

Summary

The implementation is mostly copied from MemDepAnalysis. We want to look
at all loads and stores to the same pointer operand. Bitcasts and zero
GEPs of a pointer are considered the same pointer value. We choose the
most dominating instruction.

Since updating MemorySSA with invariant.group is non-trivial, for now
handling of invariant.group is not cached in any way, so it's part of
the walker. The number of loads/stores with invariant.group is small for
now anyway. We can revisit if this actually noticeably affects compile
times.

To avoid invariant.group affecting optimized uses, we need to have
optimizeUsesInBlock() not use invariant.group in any way.

Co-authored-by: Piotr Padlewski <[e-mail]>

[Prazek]

Great! We will need to take a look at what NewGVN missed and understand if this is NewGVN fault, or are we missing something on MSSA site.

llvm/unittests/Analysis/MemorySSATest.cpp

1775

UB: Add new line

[nikic]

llvm/lib/Analysis/MemorySSA.cpp

2481

Does the verifier ensure that invariant.group is only attached to loads and stores?

2514

Might make sense to initialize MostDominatingInstruction = &I and then check !DT.dominates(U, MostDominatingInstruction) here and drop GetMostDominatingInstruction?

If we already found a more dominating candidate, then there's no point in exploring uses of less-dominating candidates anymore.

2534

if (getLoadStorePointerOperand(U) == Ptr && U->hasMetadata(...)) would be a bit more future-proof here (regarding a potential future pointer provenance operand), and I think also reads nicer...

2547

I'd call this UseInvariantGroups or so.

llvm/test/Analysis/MemorySSA/invariant-groups.ll

5

Comment needs update.

[asbirlea]

I haven't yet looked in depth into the code taken from MemDepAnalysis.

Unit test looks good.

llvm/lib/Analysis/MemorySSA.cpp

1061

Add a comment that this API is not visible outside of MemorySSA, due to the MemorySSAWalker interface.

1463

Please add a comment here explaining why this specific API is called in regards to the stack changes below.

2504

Comment needs updating?

2555

Does it make sense to add an assert here the I is either LoadInst or StoreInst?

Also that the returned access is non-null.

[aeubanks]

address comments

[aeubanks]

update

[aeubanks]

llvm/lib/Analysis/MemorySSA.cpp

2481

now it does :)

2504

I think it's still technically O(N^2) in the worst case, e.g. if we a have a large BB with many loads/stores with invariant.group MD.

2514

good optimization!

[nikic]

llvm/lib/Analysis/MemorySSA.cpp

2504

You can iterate directly over Ptr->users() here.

2526

This check is now redundant, already checked above.

2560

If the found load is atomic or volatile, wouldn't it itself be the clobbering access? If yes, we should check whether ClobberMA is a MemoryUse rather than whether it is a load. Not sure whether invariant group semantics somehow preclude this.

llvm/test/Analysis/MemorySSA/invariant-groups.ll

9

Could use a TODO/FIXME comment that this is just a missing optimization, not a correctness test.

[Prazek]

llvm/lib/Analysis/MemorySSA.cpp

2514

+1, good one, haven't thought about this.

2560

I think in theory we should be able to optimzie atomic loads with invariant.group md in the same way - if optimizer gets information that 2 loads are loading the same value (because the value is invariant), then it doesn't matter if we read the value atomically.

I am not sure how we handle atomic loads with !invariant.load, but we should be able handle !invariant.group similarly. But because we don't really care about atomic invariant.loads, we could as well just bail out and not consider any of them in the analysis.

About volatile loads: I guess we can't optimize them at all, the best would be to remove all !invariant.group metadata on such loads while canonicalization, but its better to handle this here too.

[asbirlea]

llvm/lib/Analysis/MemorySSA.cpp

2517

nit: move the continue outside, in the if(auto* GEP. condition.

2526

+1, remove second if.

2562

You shouldn't need this assert. The defining access cannot be null. Can simplify to:

if (auto *LI = dyn_cast<LoadInst>(I)) 
  return ClobberMA->getDefiningAccess();

[aeubanks]

address comments

[aeubanks]

small test update

[aeubanks]

Piotr and I looked over the NewGVN test and there were some interesting missed NewGVN optimizations. These seem like things to be fixed on the NewGVN side.

1. NewGVN was correctly forwarding a stored value to a load, but wasn't calling instsimplify on that. In these cases, we were loading a function from a vtable definition which instsimplify got, but that wasn't happening with newgvn
2. NewGVN has trouble CSE'ing loads with different pointee types
3. NewGVN doesn't support assumes in some cases

[aeubanks]

is this good to go?

[asbirlea]

Yes.

[nikic]

llvm/lib/Analysis/MemorySSA.cpp

2487

Shouldn't this skip isa<Constant> in general? I think you could reach here with a constant expression (say an inttoptr expression).

[aeubanks]

isa<Constant>

llvm/lib/Analysis/MemorySSA.cpp

2487

hmm for some reason I thought most Constants had empty use lists, but that's not true

[nikic]

LGTM as well.

llvm/lib/Analysis/MemorySSA.cpp

2487

I believe there's plans to move in that direction, but they haven't been implemented yet. (And I also think they would be more in the direction of trying to fetch users of a constant asserts, than being simply empty.)

llvm/lib/Analysis/MemorySSA.cpp

MemoryAccess *getClobberingMemoryAccessBase(MemoryAccess *,
                                               const MemoryLocation &,
                                               unsigned &);
   // Third argument (bool), defines whether the clobber search should skip the
   // original queried access. If true, there will be a follow-up query searching
   // for a clobber access past "self". Note that the Optimized access is not
   // updated if a new clobber is found by this SkipSelf search. If this
   // additional query becomes heavily used we may decide to cache the result.
   // Walker instantiations will decide how to set the SkipSelf bool.
-  MemoryAccess *getClobberingMemoryAccessBase(MemoryAccess *, unsigned &, bool);
+  MemoryAccess *getClobberingMemoryAccessBase(MemoryAccess *, unsigned &, bool,
+                                              bool InvariantGroup = true);
 };
 
 /// A MemorySSAWalker that does AA walks to disambiguate accesses. It no
 /// longer does caching on its own, but the name has been retained for the
 /// moment.
 template <class AliasAnalysisType>
 class MemorySSA::CachingWalker final : public MemorySSAWalker {
   ClobberWalkerBase<AliasAnalysisType> *Walker;
 
 public:
   CachingWalker(MemorySSA *M, ClobberWalkerBase<AliasAnalysisType> *W)
       : MemorySSAWalker(M), Walker(W) {}
   ~CachingWalker() override = default;
 
   using MemorySSAWalker::getClobberingMemoryAccess;
 
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA, unsigned &UWL) {
     return Walker->getClobberingMemoryAccessBase(MA, UWL, false);
   }
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
                                           const MemoryLocation &Loc,
                                           unsigned &UWL) {
     return Walker->getClobberingMemoryAccessBase(MA, Loc, UWL);
   }
+  MemoryAccess *getClobberingMemoryAccessWithoutInvariantGroup(MemoryAccess *MA,
+                                                               unsigned &UWL) {
+    return Walker->getClobberingMemoryAccessBase(MA, UWL, false, false);
+  }
 
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA) override {
     unsigned UpwardWalkLimit = MaxCheckLimit;
     return getClobberingMemoryAccess(MA, UpwardWalkLimit);
   }
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
                                           const MemoryLocation &Loc) override {
     unsigned UpwardWalkLimit = MaxCheckLimit;
if (UpperBound - LocInfo.LowerBound > MaxCheckLimit) {
       continue;
     }
     bool FoundClobberResult = false;
     unsigned UpwardWalkLimit = MaxCheckLimit;
     while (UpperBound > LocInfo.LowerBound) {
       if (isa<MemoryPhi>(VersionStack[UpperBound])) {
         // For phis, use the walker, see where we ended up, go there
         MemoryAccess *Result =
-            Walker->getClobberingMemoryAccess(MU, UpwardWalkLimit);
+            Walker->getClobberingMemoryAccessWithoutInvariantGroup(
+                MU, UpwardWalkLimit);
         // We are guaranteed to find it or something is wrong
         while (VersionStack[UpperBound] != Result) {
           assert(UpperBound != 0);
           --UpperBound;
         }
         FoundClobberResult = true;
         break;
       }
LLVM_DEBUG({
     dbgs() << "Clobber starting at access " << *StartingAccess << "\n";
     if (I)
       dbgs() << "  for instruction " << *I << "\n";
     dbgs() << "  is " << *Clobber << "\n";
   });
   return Clobber;
 }
 
+static Instruction *getInvariantGroupClobberingInstruction(Instruction &I,
+                                                           DominatorTree &DT) {
+  if (!I.hasMetadata(LLVMContext::MD_invariant_group))
+    return nullptr;
+
+  // We consider bitcasts and zero GEPs to be the same pointer value. Start by
+  // stripping bitcasts and zero GEPs, then we will recursively look at loads
+  // and stores through bitcasts and zero GEPs.
+  Value *PointerOperand = getLoadStorePointerOperand(&I)->stripPointerCasts();
+
+  // It's not safe to walk the use list of global value because function passes
+  // aren't allowed to look outside their functions.
+  // FIXME: this could be fixed by filtering instructions from outside of
+  // current function.
+  if (isa<GlobalValue>(PointerOperand))
+    return nullptr;
+
+  // Queue to process all pointers that are equivalent to load operand.
+  SmallVector<const Value *, 8> PointerUsesQueue;
+  PointerUsesQueue.push_back(PointerOperand);
+
+  Instruction *MostDominatingInstruction = nullptr;
+  // Get the most dominating instruction.
+  auto GetMostDominatingInstruction = [&DT](Instruction *Best,
+                                            Instruction *Other) {
+    assert(Other);
+    if (Best == nullptr || DT.dominates(Other, Best))
+      return Other;
+    return Best;
+  };
+
+  // FIXME: This loop is O(N^2) because dominates can be O(n) and in worst case
+  // we will see all the instructions. It may not matter in practice. If it
+  // does, we will have to support MemorySSA construction and updates.
+  while (!PointerUsesQueue.empty()) {
+    const Value *Ptr = PointerUsesQueue.pop_back_val();
+    assert(Ptr && !isa<GlobalValue>(Ptr) &&
+           "Null or GlobalValue should not be inserted");
+
+    for (const Use &Us : Ptr->uses()) {
+      auto *U = dyn_cast<Instruction>(Us.getUser());
+      if (!U || U == &I || !DT.dominates(U, &I))
+        continue;
+
+      // Add bitcasts and zero GEPs to queue.
+      if (isa<BitCastInst>(U)) {
+        PointerUsesQueue.push_back(U);
+        continue;
+      }
+      if (auto *GEP = dyn_cast<GetElementPtrInst>(U)) {
+        if (GEP->hasAllZeroIndices()) {
+          PointerUsesQueue.push_back(U);
+          continue;
+        }
+      }
+
+      // If we hit load/store with the invariant.group metadata and the same
+      // pointer operand we can assume that value pointed to by the pointer
+      // operand didn't change.
+      if ((isa<LoadInst>(U) ||
+           (isa<StoreInst>(U) &&
+            cast<StoreInst>(U)->getPointerOperand() == Ptr)) &&
+          U->hasMetadata(LLVMContext::MD_invariant_group))
+        MostDominatingInstruction =
+            GetMostDominatingInstruction(MostDominatingInstruction, U);
+    }
+  }
+  return MostDominatingInstruction;
+}
+
 template <typename AliasAnalysisType>
 MemoryAccess *
 MemorySSA::ClobberWalkerBase<AliasAnalysisType>::getClobberingMemoryAccessBase(
-    MemoryAccess *MA, unsigned &UpwardWalkLimit, bool SkipSelf) {
+    MemoryAccess *MA, unsigned &UpwardWalkLimit, bool SkipSelf,
+    bool InvariantGroup) {
   auto *StartingAccess = dyn_cast<MemoryUseOrDef>(MA);
   // If this is a MemoryPhi, we can't do anything.
   if (!StartingAccess)
     return MA;
 
+  if (InvariantGroup) {
+    if (auto *I = getInvariantGroupClobberingInstruction(
+            *StartingAccess->getMemoryInst(), MSSA->getDomTree())) {
+      if (auto *LI = dyn_cast<LoadInst>(I))
+        return MSSA->getMemoryAccess(I)->getDefiningAccess();
+
+      return MSSA->getMemoryAccess(I);
+    }
+  }
+
   bool IsOptimized = false;
 
   // If this is an already optimized use or def, return the optimized result.
   // Note: Currently, we store the optimized def result in a separate field,
   // since we can't use the defining access.
   if (StartingAccess->isOptimized()) {
     if (!SkipSelf || !isa<MemoryDef>(StartingAccess))
       return StartingAccess->getOptimized();

llvm/test/Analysis/MemorySSA/invariant-groups.ll

 ; RUN: opt -aa-pipeline=basic-aa -passes='print<memoryssa-walker>' -verify-memoryssa < %s 2>&1 | FileCheck %s
 ;
 ; Currently, MemorySSA doesn't support invariant groups. So, we should ignore
 ; launder.invariant.group intrinsics entirely. We'll need to pay attention to
 ; them when/if we decide to support invariant groups.
 
 @g = external global i32
 
+define i32 @global() {
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: store i32 0
+  store i32 0, i32* @g, align 4, !invariant.group !0
+
+; CHECK: 2 = MemoryDef(1)
+; CHECK-NEXT: call void @clobber
+  call void @clobber(i32* @g)
+
+; Don't optimize globals.
+; CHECK: MemoryUse(2) {{.*}} clobbered by 2
+; CHECK-NEXT: %1 = load i32
+  %1 = load i32, i32* @g, align 4, !invariant.group !0
+  ret i32 %1
+}
+
 define i32 @foo(i32* %a) {
 ; CHECK: 1 = MemoryDef(liveOnEntry)
 ; CHECK-NEXT: store i32 0
   store i32 0, i32* %a, align 4, !invariant.group !0
 
 ; CHECK: 2 = MemoryDef(1)
 ; CHECK-NEXT: store i32 1
   store i32 1, i32* @g, align 4

 ; We can skip the barrier only if the "skip" is not based on !invariant.group.
 ; CHECK: MemoryUse(liveOnEntry)
 ; CHECK-NEXT: %v2 = load i32
   %v2 = load i32, i32* %a32, align 4, !invariant.group !0
 ; CHECK: 2 = MemoryDef(1)
 ; CHECK-NEXT: store i32 1
   store i32 1, i32* @g, align 4
 
-; FIXME: based on invariant.group it should be MemoryUse(liveOnEntry)
-; CHECK: MemoryUse(2) {{.*}} clobbered by 2
+; CHECK: MemoryUse(2) {{.*}} clobbered by 0
 ; CHECK-NEXT: %v3 = load i32
   %v3 = load i32, i32* %a32, align 4, !invariant.group !0
   %add = add nsw i32 %v2, %v3
   %add2 = add nsw i32 %add, %v
   ret i32 %add2
 }
 
 define i32 @handleInvariantGroups(i32* %a) {

 ; CHECK: MemoryUse(2)
 ; CHECK-NEXT: %2 = load i32
   %2 = load i32, i32* %a32, align 4, !invariant.group !0
 
 ; CHECK: 4 = MemoryDef(3)
 ; CHECK-NEXT: store i32 2
   store i32 2, i32* @g, align 4
 
-; FIXME: This can be changed to MemoryUse(2)
-; CHECK: MemoryUse(4) {{.*}} clobbered by 4
+; CHECK: MemoryUse(4) {{.*}} clobbered by 2
 ; CHECK-NEXT: %3 = load i32
   %3 = load i32, i32* %a32, align 4, !invariant.group !0
   %add = add nsw i32 %2, %3
   ret i32 %add
 }
 
 define i32 @loop(i1 %a) {
 entry:
   %0 = alloca i32, align 4
 ; CHECK: 1 = MemoryDef(liveOnEntry)
 ; CHECK-NEXT: store i32 4
   store i32 4, i32* %0, !invariant.group !0
 ; CHECK: 2 = MemoryDef(1)
 ; CHECK-NEXT: call void @clobber
   call void @clobber(i32* %0)
   br i1 %a, label %Loop.Body, label %Loop.End
 
 Loop.Body:
-; FIXME: MemoryUse(1)
-; CHECK: MemoryUse(2) {{.*}} clobbered by 2
+; CHECK: MemoryUse(2) {{.*}} clobbered by 1
 ; CHECK-NEXT: %1 = load i32
   %1 = load i32, i32* %0, !invariant.group !0
   br i1 %a, label %Loop.End, label %Loop.Body
 
 Loop.End:
-; FIXME: MemoryUse(1)
-; CHECK: MemoryUse(2) {{.*}} clobbered by 2
+; CHECK: MemoryUse(2) {{.*}} clobbered by 1
 ; CHECK-NEXT: %2 = load
   %2 = load i32, i32* %0, align 4, !invariant.group !0
   br i1 %a, label %Ret, label %Loop.Body
 
 Ret:
   ret i32 %2
 }
 
; CHECK-NEXT: %after = call i8* @llvm.launder.invariant.group.p0i8(i8* %p)
   %after = call i8* @llvm.launder.invariant.group.p0i8(i8* %p)
   br i1 undef, label %Loop.Body, label %Loop.End
 
 Loop.Body:
 ; CHECK: MemoryUse(6)
 ; CHECK-NEXT: %0 = load i8
   %0 = load i8, i8* %after, !invariant.group !0
 
-; FIXME: MemoryUse(1)
-; CHECK: MemoryUse(6) {{.*}} clobbered by 6
+; CHECK: MemoryUse(6) {{.*}} clobbered by 1
 ; CHECK-NEXT: %1 = load i8
   %1 = load i8, i8* %p, !invariant.group !0
 
 ; CHECK: 4 = MemoryDef(6)
   store i8 4, i8* %after, !invariant.group !0
 
   br i1 undef, label %Loop.End, label %Loop.Body
 
 Loop.End:
 ; CHECK: MemoryUse(5)
 ; CHECK-NEXT: %2 = load
   %2 = load i8, i8* %after, align 4, !invariant.group !0
 
-; FIXME: MemoryUse(1)
-; CHECK: MemoryUse(5) {{.*}} clobbered by 5
+; CHECK: MemoryUse(5) {{.*}} clobbered by 1
 ; CHECK-NEXT: %3 = load
   %3 = load i8, i8* %p, align 4, !invariant.group !0
   br i1 undef, label %Ret, label %Loop.Body
 
 Ret:
   ret i8 %3
 }
 

 ; CHECK: MemoryUse(8)
 ; CHECK-NEXT: %0 = load i8
   %0 = load i8, i8* %after, !invariant.group !0
 
 ; CHECK: 4 = MemoryDef(8)
 ; CHECK-NEXT: call void @clobber8
   call void @clobber8(i8* %after)
 
-; FIXME: MemoryUse(8)
-; CHECK: MemoryUse(4) {{.*}} clobbered by 4
+; CHECK: MemoryUse(4) {{.*}} clobbered by 8
 ; CHECK-NEXT: %1 = load i8
   %1 = load i8, i8* %after, !invariant.group !0
 
   br i1 undef, label %Loop.next, label %Loop.Body
 Loop.next:
 ; CHECK: 5 = MemoryDef(4)
 ; CHECK-NEXT: call void @clobber8
   call void @clobber8(i8* %after)
 
-; FIXME: MemoryUse(8)
-; CHECK: MemoryUse(5) {{.*}} clobbered by 5
+; CHECK: MemoryUse(5) {{.*}} clobbered by 8
 ; CHECK-NEXT: %2 = load i8
   %2 = load i8, i8* %after, !invariant.group !0
 
   br i1 undef, label %Loop.End, label %Loop.Body
 
 Loop.End:
 ; CHECK: MemoryUse(7)
 ; CHECK-NEXT: %3 = load
   %3 = load i8, i8* %after, align 4, !invariant.group !0
 
 ; CHECK: 6 = MemoryDef(7)
 ; CHECK-NEXT: call void @clobber8
   call void @clobber8(i8* %after)
 
-; FIXME: MemoryUse(7)
-; CHECK: MemoryUse(6) {{.*}} clobbered by 6
+; CHECK: MemoryUse(6) {{.*}} clobbered by 7
 ; CHECK-NEXT: %4 = load
   %4 = load i8, i8* %after, align 4, !invariant.group !0
   br i1 undef, label %Ret, label %Loop.Body
 
 Ret:
   ret i8 %3
 }
 

 ; CHECK-NEXT: %0 = load i8
   %0 = load i8, i8* %after, !invariant.group !0
   br label %Loop.Body
 Loop.Body:
 ; CHECK: MemoryUse(6)
 ; CHECK-NEXT: %1 = load i8
   %1 = load i8, i8* %after, !invariant.group !0
 
-; FIXME: MemoryUse(2)
-; CHECK: MemoryUse(6) {{.*}} clobbered by 6
+; CHECK: MemoryUse(6) {{.*}} clobbered by 1
 ; CHECK-NEXT: %2 = load i8
   %2 = load i8, i8* %p, !invariant.group !0
 
 ; CHECK: 4 = MemoryDef(6)
   store i8 4, i8* %after, !invariant.group !0
   br i1 undef, label %Loop.End, label %Loop.Body
 
 Loop.End:
 ; CHECK: MemoryUse(5)
 ; CHECK-NEXT: %3 = load
   %3 = load i8, i8* %after, align 4, !invariant.group !0
 
-; FIXME: MemoryUse(2)
-; CHECK: MemoryUse(5) {{.*}} clobbered by 5
+; CHECK: MemoryUse(5) {{.*}} clobbered by 1
 ; CHECK-NEXT: %4 = load
   %4 = load i8, i8* %p, align 4, !invariant.group !0
   br i1 undef, label %Ret, label %Loop.Body
 
 Ret:
   ret i8 %3
 }
 

llvm/test/Transforms/NewGVN/invariant.group.ll

-; XFAIL: *
-; RUN: opt < %s -newgvn -S | FileCheck %s
+; RUN: opt < %s -passes=newgvn -S | FileCheck %s
 
 %struct.A = type { i32 (...)** }
 @_ZTV1A = available_externally unnamed_addr constant [3 x i8*] [i8* null, i8* bitcast (i8** @_ZTI1A to i8*), i8* bitcast (void (%struct.A*)* @_ZN1A3fooEv to i8*)], align 8
 @_ZTI1A = external constant i8*
 
 @unknownPtr = external global i8
 
 ; CHECK-LABEL: define i8 @simple() {
entry:
     %b = load i8, i8* %ptr, !invariant.group !0
     
 ; CHECK: ret i8 42
     ret i8 %b
 }
 
 ; CHECK-LABEL: define i1 @proveEqualityForStrip(
 define i1 @proveEqualityForStrip(i8* %a) {
-; FIXME: The first call could be also removed by GVN. Right now
-; DCE removes it. The second call is CSE'd with the first one.
-; CHECK: %b1 = call i8* @llvm.strip.invariant.group.p0i8(i8* %a)
   %b1 = call i8* @llvm.strip.invariant.group.p0i8(i8* %a)
 ; CHECK-NOT: llvm.strip.invariant.group
   %b2 = call i8* @llvm.strip.invariant.group.p0i8(i8* %a)
   %r = icmp eq i8* %b1, %b2
 ; CHECK: ret i1 true
   ret i1 %r
 }
 
; CHECK: %vtable = load {{.*}} !invariant.group
   %vtable = load i8**, i8*** %2, align 8, !invariant.group !0
   %cmp.vtables = icmp eq i8** %vtable, getelementptr inbounds ([3 x i8*], [3 x i8*]* @_ZTV1A, i64 0, i64 2)
   call void @llvm.assume(i1 %cmp.vtables)
   
   store %struct.A* %1, %struct.A** %a, align 8
   %3 = load %struct.A*, %struct.A** %a, align 8
   %4 = bitcast %struct.A* %3 to void (%struct.A*)***
 
-; CHECK: call void @_ZN1A3fooEv(
+; FIXME: call void @_ZN1A3fooEv(
   %vtable1 = load void (%struct.A*)**, void (%struct.A*)*** %4, align 8, !invariant.group !0
   %vfn = getelementptr inbounds void (%struct.A*)*, void (%struct.A*)** %vtable1, i64 0
   %5 = load void (%struct.A*)*, void (%struct.A*)** %vfn, align 8
   call void %5(%struct.A* %3)
   %6 = load %struct.A*, %struct.A** %a, align 8
   %7 = bitcast %struct.A* %6 to void (%struct.A*)***
 
-; CHECK: call void @_ZN1A3fooEv(
+; FIXME: call void @_ZN1A3fooEv(
   %vtable2 = load void (%struct.A*)**, void (%struct.A*)*** %7, align 8, !invariant.group !0
   %vfn3 = getelementptr inbounds void (%struct.A*)*, void (%struct.A*)** %vtable2, i64 0
   %8 = load void (%struct.A*)*, void (%struct.A*)** %vfn3, align 8
   
   call void %8(%struct.A* %6)
   %9 = load %struct.A*, %struct.A** %a, align 8
   %10 = bitcast %struct.A* %9 to void (%struct.A*)***
   
   %vtable4 = load void (%struct.A*)**, void (%struct.A*)*** %10, align 8, !invariant.group !0
   %vfn5 = getelementptr inbounds void (%struct.A*)*, void (%struct.A*)** %vtable4, i64 0
   %11 = load void (%struct.A*)*, void (%struct.A*)** %vfn5, align 8
-; CHECK: call void @_ZN1A3fooEv(
+; FIXME: call void @_ZN1A3fooEv(
   call void %11(%struct.A* %9)
  
   %vtable5 = load i8**, i8*** %2, align 8, !invariant.group !0
   %vfn6 = getelementptr inbounds i8*, i8** %vtable5, i64 0
   %12 = bitcast i8** %vfn6 to void (%struct.A*)**
   %13 = load void (%struct.A*)*, void (%struct.A*)** %12, align 8
-; CHECK: call void @_ZN1A3fooEv(
+; FIXME: call void @_ZN1A3fooEv(
   call void %13(%struct.A* %9)
   
   ret void
 }
 
 ; CHECK-LABEL: define void @combiningBitCastWithLoad() {
 define void @combiningBitCastWithLoad() {
 entry:
   %a = alloca %struct.A*, align 8
   %0 = bitcast %struct.A** %a to i8*
   
   %call = call i8* @getPointer(i8* null) 
   %1 = bitcast i8* %call to %struct.A*
   call void @_ZN1AC1Ev(%struct.A* %1)
   %2 = bitcast %struct.A* %1 to i8***
   
 ; CHECK: %vtable = load {{.*}} !invariant.group
   %vtable = load i8**, i8*** %2, align 8, !invariant.group !0
   %cmp.vtables = icmp eq i8** %vtable, getelementptr inbounds ([3 x i8*], [3 x i8*]* @_ZTV1A, i64 0, i64 2)
   
   store %struct.A* %1, %struct.A** %a, align 8
-; CHECK-NOT: !invariant.group
+; FIXME-NOT: !invariant.group
   %3 = load %struct.A*, %struct.A** %a, align 8
   %4 = bitcast %struct.A* %3 to void (%struct.A*)***
 
   %vtable1 = load void (%struct.A*)**, void (%struct.A*)*** %4, align 8, !invariant.group !0
   %vfn = getelementptr inbounds void (%struct.A*)*, void (%struct.A*)** %vtable1, i64 0
   %5 = load void (%struct.A*)*, void (%struct.A*)** %vfn, align 8
   call void %5(%struct.A* %3)
 
   ret void
 }
 
 ; CHECK-LABEL:define void @loadCombine() {
 define void @loadCombine() {
 enter:
   %ptr = alloca i8
   store i8 42, i8* %ptr
   call void @foo(i8* %ptr)
-; CHECK: %[[A:.*]] = load i8, i8* %ptr, !invariant.group
+; CHECK: %[[A:.*]] = load i8, i8* %ptr, align 1, !invariant.group
   %a = load i8, i8* %ptr, !invariant.group !0
 ; CHECK-NOT: load
   %b = load i8, i8* %ptr, !invariant.group !0
 ; CHECK: call void @bar(i8 %[[A]])
   call void @bar(i8 %a)
 ; CHECK: call void @bar(i8 %[[A]])
   call void @bar(i8 %b)
   ret void
 }
 
 ; CHECK-LABEL: define void @loadCombine1() {
 define void @loadCombine1() {
 enter:
   %ptr = alloca i8
   store i8 42, i8* %ptr
   call void @foo(i8* %ptr)
-; CHECK: %[[D:.*]] = load i8, i8* %ptr, !invariant.group
+; CHECK: %[[D:.*]] = load i8, i8* %ptr, align 1, !invariant.group
   %c = load i8, i8* %ptr
 ; CHECK-NOT: load
   %d = load i8, i8* %ptr, !invariant.group !0
 ; CHECK: call void @bar(i8 %[[D]])
   call void @bar(i8 %c)
 ; CHECK: call void @bar(i8 %[[D]])
   call void @bar(i8 %d)
   ret void
 }
 
 ; CHECK-LABEL: define void @loadCombine2() {    
 define void @loadCombine2() {
 enter:
   %ptr = alloca i8
   store i8 42, i8* %ptr
   call void @foo(i8* %ptr)
-; CHECK: %[[E:.*]] = load i8, i8* %ptr, !invariant.group
+; CHECK: %[[E:.*]] = load i8, i8* %ptr, align 1, !invariant.group
   %e = load i8, i8* %ptr, !invariant.group !0
 ; CHECK-NOT: load
   %f = load i8, i8* %ptr
 ; CHECK: call void @bar(i8 %[[E]])
   call void @bar(i8 %e)
 ; CHECK: call void @bar(i8 %[[E]])
   call void @bar(i8 %f)
   ret void
 }
 
 ; CHECK-LABEL: define void @loadCombine3() {
 define void @loadCombine3() {
 enter:
   %ptr = alloca i8
   store i8 42, i8* %ptr
   call void @foo(i8* %ptr)
-; CHECK: %[[E:.*]] = load i8, i8* %ptr, !invariant.group
+; CHECK: %[[E:.*]] = load i8, i8* %ptr, align 1, !invariant.group
   %e = load i8, i8* %ptr, !invariant.group !0
 ; CHECK-NOT: load
   %f = load i8, i8* %ptr, !invariant.group !0
 ; CHECK: call void @bar(i8 %[[E]])
   call void @bar(i8 %e)
 ; CHECK: call void @bar(i8 %[[E]])
   call void @bar(i8 %f)
   ret void

 }
 
 ; CHECK-LABEL: define i8 @optimizable4() {
 define i8 @optimizable4() {
 entry:
     %ptr = alloca i8
     store i8 42, i8* %ptr, !invariant.group !0
     %ptr2 = call i8* @llvm.launder.invariant.group.p0i8(i8* %ptr)
-; CHECK-NOT: load
+; FIXME-NOT: load
     %a = load i8, i8* %ptr2, !invariant.group !0
     
-; CHECK: ret i8 42
+; FIXME: ret i8 42
     ret i8 %a
 }
 
 ; CHECK-LABEL: define i8 @volatile1() {
 define i8 @volatile1() {
 entry:
     %ptr = alloca i8
     store i8 42, i8* %ptr, !invariant.group !0
; CHECK: call void @bar(i8 42)
 
     %newPtr = call i8* @getPointer(i8* %ptr) 
     %c = load i8, i8* %newPtr, !invariant.group !0 ; Can't assume anything, because we only have information about %ptr
 ; CHECK: call void @bar(i8 %c)
     call void @bar(i8 %c)
     
     %unknownValue = load i8, i8* @unknownPtr
 ; FIXME: Can assume that %unknownValue == 42
-; CHECK: store i8 %unknownValue, i8* %ptr, !invariant.group !0
+; CHECK: store i8 %unknownValue, i8* %ptr, align 1, !invariant.group !0
     store i8 %unknownValue, i8* %ptr, !invariant.group !0 
 
     %newPtr2 = call i8* @llvm.launder.invariant.group.p0i8(i8* %ptr)
-; CHECK-NOT: load
+; FIXME-NOT: load
     %d = load i8, i8* %newPtr2, !invariant.group !0
-; CHECK: ret i8 %unknownValue
+; FIXME: ret i8 %unknownValue
     ret i8 %d
 }
 
 ; This test checks if invariant.group understands gep with zeros
 ; CHECK-LABEL: define void @testGEP0() {
 define void @testGEP0() {
   %a = alloca %struct.A, align 8
   %1 = bitcast %struct.A* %a to i8*
   %2 = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 0
   store i32 (...)** bitcast (i8** getelementptr inbounds ([3 x i8*], [3 x i8*]* @_ZTV1A, i64 0, i64 2) to i32 (...)**), i32 (...)*** %2, align 8, !invariant.group !0
 ; CHECK: call void @_ZN1A3fooEv(%struct.A* nonnull dereferenceable(8) %a)
   call void @_ZN1A3fooEv(%struct.A* nonnull dereferenceable(8) %a) ; This call may change vptr
   %3 = load i8, i8* @unknownPtr, align 4
   %4 = icmp eq i8 %3, 0
   br i1 %4, label %_Z1gR1A.exit, label %5
 
 ; This should be devirtualized by invariant.group
   %6 = bitcast %struct.A* %a to void (%struct.A*)***
   %7 = load void (%struct.A*)**, void (%struct.A*)*** %6, align 8, !invariant.group !0
   %8 = load void (%struct.A*)*, void (%struct.A*)** %7, align 8
-; CHECK: call void @_ZN1A3fooEv(%struct.A* nonnull %a)
+; FIXME: call void @_ZN1A3fooEv(%struct.A* nonnull %a)
   call void %8(%struct.A* nonnull %a)
   br label %_Z1gR1A.exit
 
 _Z1gR1A.exit:                                     ; preds = %0, %5
   ret void
 }
 
 ; Check if no optimizations are performed with global pointers.
 ; FIXME: we could do the optimizations if we would check if dependency comes
 ; from the same function.
 ; CHECK-LABEL: define void @testGlobal() {
 define void @testGlobal() {
-; CHECK:  %a = load i8, i8* @unknownPtr, !invariant.group !0
+; CHECK:  %a = load i8, i8* @unknownPtr, align 1, !invariant.group !0
    %a = load i8, i8* @unknownPtr, !invariant.group !0
    call void @foo2(i8* @unknownPtr, i8 %a)
-; CHECK:  %1 = load i8, i8* @unknownPtr, !invariant.group !0
+; CHECK:  %1 = load i8, i8* @unknownPtr, align 1, !invariant.group !0
    %1 = load i8, i8* @unknownPtr, !invariant.group !0
    call void @bar(i8 %1)
 
    %b0 = bitcast i8* @unknownPtr to i1*
    call void @fooBit(i1* %b0, i1 1)
 ; Adding regex because of canonicalization of bitcasts
 ; CHECK: %2 = load i1, i1* {{.*}}, !invariant.group !0
    %2 = load i1, i1* %b0, !invariant.group !0
    call void @fooBit(i1* %b0, i1 %2)
 ; CHECK:  %3 = load i1, i1* {{.*}}, !invariant.group !0
    %3 = load i1, i1* %b0, !invariant.group !0
    call void @fooBit(i1* %b0, i1 %3)
    ret void
 }
 ; And in the case it is not global
 ; CHECK-LABEL: define void @testNotGlobal() {
 define void @testNotGlobal() {
    %a = alloca i8
    call void @foo(i8* %a)
-; CHECK:  %b = load i8, i8* %a, !invariant.group !0
+; CHECK:  %b = load i8, i8* %a, align 1, !invariant.group !0
    %b = load i8, i8* %a, !invariant.group !0
    call void @foo2(i8* %a, i8 %b)
 
    %1 = load i8, i8* %a, !invariant.group !0
 ; CHECK: call void @bar(i8 %b)
    call void @bar(i8 %1)
 
    %b0 = bitcast i8* %a to i1*
    call void @fooBit(i1* %b0, i1 1)
-; CHECK: %1 = trunc i8 %b to i1
+; FIXME: %1 = trunc i8 %b to i1
    %2 = load i1, i1* %b0, !invariant.group !0
-; CHECK-NEXT: call void @fooBit(i1* %b0, i1 %1)
+; FIXME-NEXT: call void @fooBit(i1* %b0, i1 %1)
    call void @fooBit(i1* %b0, i1 %2)
    %3 = load i1, i1* %b0, !invariant.group !0
-; CHECK-NEXT: call void @fooBit(i1* %b0, i1 %1)
+; FIXME-NEXT: call void @fooBit(i1* %b0, i1 %1)
    call void @fooBit(i1* %b0, i1 %3)
    ret void
 }
 
 ; CHECK-LABEL: define void @handling_loops()
 define void @handling_loops() {
   %a = alloca %struct.A, align 8
   %1 = bitcast %struct.A* %a to i8*

 
 ._crit_edge.preheader:                            ; preds = %.lr.ph.i
   br label %._crit_edge
 
 ._crit_edge:                                      ; preds = %._crit_edge.preheader, %._crit_edge
   %8 = phi i8 [ %10, %._crit_edge ], [ 1, %._crit_edge.preheader ]
   %.pre = load void (%struct.A*)**, void (%struct.A*)*** %5, align 8, !invariant.group !0
   %9 = load void (%struct.A*)*, void (%struct.A*)** %.pre, align 8
-  ; CHECK: call void @_ZN1A3fooEv(%struct.A* nonnull %a)
+  ; FIXME: call void @_ZN1A3fooEv(%struct.A* nonnull %a)
   call void %9(%struct.A* nonnull %a) #3
-  ; CHECK-NOT: call void %
+  ; FIXME-NOT: call void %
   %10 = add nuw nsw i8 %8, 1
   %11 = load i8, i8* @unknownPtr, align 4
   %12 = icmp slt i8 %10, %11
   br i1 %12, label %._crit_edge, label %_Z2g2R1A.exit.loopexit
 
 _Z2g2R1A.exit.loopexit:                           ; preds = %._crit_edge
   br label %_Z2g2R1A.exit
 
 _Z2g2R1A.exit:                                    ; preds = %_Z2g2R1A.exit.loopexit, %.lr.ph.i, %0
   ret void
 }
 
 
 declare void @foo(i8*)
 declare void @foo2(i8*, i8)
 declare void @bar(i8)
 declare i8* @getPointer(i8*)
 declare void @_ZN1A3fooEv(%struct.A*)
 declare void @_ZN1AC1Ev(%struct.A*)
 declare void @fooBit(i1*, i1)
 
 declare i8* @llvm.launder.invariant.group.p0i8(i8*)
+declare i8* @llvm.strip.invariant.group.p0i8(i8*)
 
 ; Function Attrs: nounwind
 declare void @llvm.assume(i1 %cmp.vtables) #0
 
 
 attributes #0 = { nounwind }
-!0 = !{}
+!0 = !{}
 

llvm/unittests/Analysis/MemorySSATest.cpp

if (BB.getName() == "exit") {
       auto ItB =
           upward_defs_begin({ItA->first, ItA->second}, MSSA.getDomTree());
       // Check if the location information have been retained
       EXPECT_TRUE(ItB->second.Size.isPrecise());
       EXPECT_TRUE(ItB->second.Size.hasValue());
       EXPECT_TRUE(ItB->second.Size.getValue() == 8);
     }
   }
+}
+
+TEST_F(MemorySSATest, TestInvariantGroup) {
+  SMDiagnostic E;
+  auto M = parseAssemblyString("declare void @f(i8*)\n"
+                               "define i8 @test(i8* %p) {\n"
+                               "entry:\n"
+                               "  store i8 42, i8* %p, !invariant.group !0\n"
+                               "  call void @f(i8* %p)\n"
+                               "  %v = load i8, i8* %p, !invariant.group !0\n"
+                               "  ret i8 %v\n"
+                               "}\n"
+                               "!0 = !{}",
+                               E, C);
+  ASSERT_TRUE(M);
+  F = M->getFunction("test");
+  ASSERT_TRUE(F);
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+  MemorySSAWalker *Walker = Analyses->Walker;
+
+  auto &BB = F->getEntryBlock();
+  auto &SI = cast<StoreInst>(*BB.begin());
+  auto &Call = cast<CallBase>(*std::next(BB.begin()));
+  auto &LI = cast<LoadInst>(*std::next(std::next(BB.begin())));
+
+  {
+    MemoryAccess *SAccess = MSSA.getMemoryAccess(&SI);
+    MemoryAccess *LAccess = MSSA.getMemoryAccess(&LI);
+    MemoryAccess *SClobber = Walker->getClobberingMemoryAccess(SAccess);
+    EXPECT_TRUE(MSSA.isLiveOnEntryDef(SClobber));
+    MemoryAccess *LClobber = Walker->getClobberingMemoryAccess(LAccess);
+    EXPECT_EQ(SAccess, LClobber);
+  }
+
+  // remove store and verify that the memory accesses still make sense
+  MemorySSAUpdater Updater(&MSSA);
+  Updater.removeMemoryAccess(&SI);
+  SI.eraseFromParent();
+
+  {
+    MemoryAccess *CallAccess = MSSA.getMemoryAccess(&Call);
+    MemoryAccess *LAccess = MSSA.getMemoryAccess(&LI);
+    MemoryAccess *LClobber = Walker->getClobberingMemoryAccess(LAccess);
+    EXPECT_EQ(CallAccess, LClobber);
+  }
 }
 No newline at end of file