[MemorySSA] Add invariant.group handling

[Prazek]

Summary

Now loads with invariant group will have the same
MemoryUse as dominating store/load with the same
invariant.group and pointer operand.

The algorithm is O(#invariant.group loads/stores in function),
which is much better compared to O(n^2) in MemDep.

NewGVN now handles some devirtualization cases, but
unfortunatelly not all of them.

[Prazek]

Added back removed empty lines

[george.burgess.iv]

Thanks for this!

Haven't looked over the patch in great detail, but I do have a few high-level questions:

• Is it possible for an invariant group barrier to ever be removed from/added to a function? If so, then we're either going to have to treat it as Def, or we're going to have to add a byTheWayThisInvariantBarrierIsNowDead and/or a weHaveANewInvariantBarrier function to MemorySSA.

• Is it possible to add/remove/move an operation with invariant group metadata on it? If so, we'll probably need to change the update API to handle those cases sanely (otherwise, looks like PerBlockInvariantGroupAccesses can end up with dangling pointers?)

lib/Transforms/Utils/MemorySSA.cpp

1338

VersionStack.push_back(MSSA->getLiveOnEntryDef()); below takes care of that; liveOnEntryDef exists in the entry block, so it always dominates everything. :)

If you'd like to add commentary/asserts, feel free (though preferably as a separate commit).

[• dberlin]

A few things

1. I'm curious why this isn't just added to the use optimizer more directly, it looks like you are computing info about most-dominating accesses, etc, which the stack already has.
2. If this isn't done in the walker, it'll never work in the face of updates.

[• dberlin]

(IE the use optimizer is a faster version of the walker, it's not better.
You are making something that is better, but if you don't add that to the walker, newly built memoryssa will support it but updated won't)

[Prazek]

In D29064#654327, @george.burgess.iv wrote:

Thanks for this!

Haven't looked over the patch in great detail, but I do have a few high-level questions:

• Is it possible for an invariant group barrier to ever be removed from/added to a function? If so, then we're either going to have to treat it as Def, or we're going to have to add a byTheWayThisInvariantBarrierIsNowDead and/or a weHaveANewInvariantBarrier function to MemorySSA.

Yes, it is sometimes possible to remove barrier. Case like

%unused = i8* @llvm.invariant.group.barrier(%x)

So when the result is unused. I think this could be achieved by giving some attributes to barrier like readonly, so that optimizer will
know that this can be removed if return value is unused. I haven't looked into that in the detail, but I am sure there is, or could
exist attribute that does this.

Other case is when barrier has only
one use, which is barrier, then we could remove it

%b = @llvm.invariant.group.barrier(%p)
%b2 = @llvm.invariant.group.barrier(%b)

In this case %b could be removed.

Hovewer I am thinking about some other method. I would like to have all the optimizations
working the same as if I would remove all the barriers and invariant groups, but without removing them.
One of the case is

store 42, %p
%a = @llvm.invariant.group.barrier(%p)
load %a

In this case the load will have the correct MemoryUse, but the optimizer won't be able to figure out the value of load
or the case like

store 42, %x
%a = @llvm.invariant.group.barrier(%x)
store 41, %a

In this case first store is dead.
So I don't yet know how to handle these cases, but I will at DSE and newGVN to figure it out.

• Is it possible to add/remove/move an operation with invariant group metadata on it? If so, we'll probably need to change the update API to handle those cases sanely (otherwise, looks like PerBlockInvariantGroupAccesses can end up with dangling pointers?)

Yes, PerBlockInvariantGroupAccess will have dangling pointers, but I was planning to only use it in OptimizeUses, which is used only ones where we still have all the instructions. Hovewer this might change because I have to take a look at the walker as Daniel said.

[Prazek]

In D29064#654390, @dberlin wrote:

A few things

1. I'm curious why this isn't just added to the use optimizer more directly, it looks like you are computing info about most-dominating accesses, etc, which the stack already has.

do you mean optimizeUsesInBlock? I think this functions is already big enough with a lot of logic, so by having it in the different functions it is much simpler (and also the information about the stack is narrowed only to the things that I need)

2. If this isn't done in the walker, it'll never work in the face of updates.

(IE the use optimizer is a faster version of the walker, it's not better.
You are making something that is better, but if you don't add that to the walker, newly built memoryssa will support it but updated won't)

I haven't noticed that. I will fix the walker soon

[Prazek]

lib/Transforms/Utils/MemorySSA.cpp

1338

That's what I thought, which means that !VersionStack.empty() is always true.
I will rewrite this loop later to make it more clear.

[davide]

This probably needs rebasing after the recent Danny's change. First round of comments inline.

include/llvm/Transforms/Utils/MemorySSA.h

633–637

comment this function? (as the one above)

lib/Transforms/Utils/MemorySSA.cpp

1508

s/pesimize/pessimize.

1514–1517

Ternary op here maybe?

1537

if it's not used, can you remove that separately?

1579–1582

instead of a static function here you can probably make this a lambda inside buildMemorySSA() ?

[davide]

(and thanks for taking care of this).

[Prazek]

In D29064#659605, @davide wrote:

(and thanks for taking care of this).

Sure, I will finish this after exams. I need to think more about the walkers and updater

[Prazek]

I implemented this properly with Arthur in https://reviews.llvm.org/D109134

include/llvm/Transforms/Utils/MemorySSA.h

public:
   inline bool isLiveOnEntryDef(const MemoryAccess *MA) const {
     return MA == LiveOnEntryDef.get();
   }
 
   inline MemoryAccess *getLiveOnEntryDef() const {
     return LiveOnEntryDef.get();
   }
 
+  using InvariantGroupAccesses = SmallVector<MemoryUseOrDef *, 4>;
   using AccessList = iplist<MemoryAccess>;
 
   /// \brief Return the list of MemoryAccess's for a given basic block.
   ///
   /// This list is not modifiable by the user.
   const AccessList *getBlockAccesses(const BasicBlock *BB) const {
     return getWritableBlockAccesses(BB);
   }
protected:
   void verifyOrdering(Function &F) const;
 
   // This is used by the use optimizer class
   AccessList *getWritableBlockAccesses(const BasicBlock *BB) const {
     auto It = PerBlockAccesses.find(BB);
     return It == PerBlockAccesses.end() ? nullptr : It->second.get();
   }
 
+  const InvariantGroupAccesses *
+  getInvariantGroupBlockAccesses(const BasicBlock *BB) const {
+    auto It = PerBlockInvariantGroupAccesses.find(BB);
+    return It == PerBlockInvariantGroupAccesses.end() ? nullptr : &It->second;
+  }
+
 private:
   class CachingWalker;
   class OptimizeUses;
 
   CachingWalker *getWalkerImpl();
   void buildMemorySSA();
   void optimizeUses();
 
   void verifyUseInDefs(MemoryAccess *, MemoryAccess *) const;
   using AccessMap = DenseMap<const BasicBlock *, std::unique_ptr<AccessList>>;
+  using UseOrDefAccessMap =
+      DenseMap<const BasicBlock *, InvariantGroupAccesses>;
 
   void
   determineInsertionPoint(const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks);
   void computeDomLevels(DenseMap<DomTreeNode *, unsigned> &DomLevels);
   void markUnreachableAsLiveOnEntry(BasicBlock *BB);
   bool dominatesUse(const MemoryAccess *, const MemoryAccess *) const;
   MemoryUseOrDef *createNewAccess(Instruction *);
   MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *);
private:
 
   AliasAnalysis *AA;
   DominatorTree *DT;
   Function &F;
 
   // Memory SSA mappings
   DenseMap<const Value *, MemoryAccess *> ValueToMemoryAccess;
   AccessMap PerBlockAccesses;
+  UseOrDefAccessMap PerBlockInvariantGroupAccesses;
   std::unique_ptr<MemoryAccess> LiveOnEntryDef;
 
   // Domination mappings
   // Note that the numbering is local to a block, even though the map is
   // global.
   mutable SmallPtrSet<const BasicBlock *, 16> BlockNumberingValid;
   mutable DenseMap<const MemoryAccess *, unsigned long> BlockNumbering;
 

lib/Transforms/Utils/MemorySSA.cpp

MemorySSA::~MemorySSA() {
   // Drop all our references
   for (const auto &Pair : PerBlockAccesses)
     for (MemoryAccess &MA : *Pair.second)
       MA.dropAllReferences();
 }
 
 MemorySSA::AccessList *MemorySSA::getOrCreateAccessList(const BasicBlock *BB) {
   auto Res = PerBlockAccesses.insert(std::make_pair(BB, nullptr));
   
   if (Res.second)
     Res.first->second = make_unique<AccessList>();
   return Res.first->second.get();
 }
 
 /// This class is a batch walker of all MemoryUse's in the program, and points
 /// their defining access at the thing that actually clobbers them.  Because it
 /// is a batch walker that touches everything, it does not operate like the
struct MemlocStackInfo {
     const BasicBlock *LowerBoundBlock;
     // This is where the last walk for this memory location ended.
     unsigned long LastKill;
     bool LastKillValid;
   };
   void optimizeUsesInBlock(const BasicBlock *, unsigned long &, unsigned long &,
                            SmallVectorImpl<MemoryAccess *> &,
                            DenseMap<MemoryLocOrCall, MemlocStackInfo> &);
+  /// Maps load/store pointer operand with its group to the most dominating
+  /// defining access.
+  using MostDominatingInvariantGroupMap =
+      DenseMap<std::pair<Value *, MDNode *>, MemoryAccess *>;
+
+  struct InsertedInvariantGroupInfo {
+    Value *PointerOperand;
+    MDNode *InvariantGroup;
+    MemoryAccess *DefiningAccess;
+  };
+  /// Optimizes memory uses based on !invariant.group metadata.
+  void optimizeInvariantGroupUsesInBlock(
+      const BasicBlock *, MostDominatingInvariantGroupMap &,
+      SmallVectorImpl<InsertedInvariantGroupInfo> &);
+
   MemorySSA *MSSA;
   MemorySSAWalker *Walker;
   AliasAnalysis *AA;
   DominatorTree *DT;
 };
 
 /// Optimize the uses in a given block This is basically the SSA renaming
 /// algorithm, with one caveat: We are able to use a single stack for all
if (Accesses == nullptr)
     return;
 
   // Pop everything that doesn't dominate the current block off the stack,
   // increment the PopEpoch to account for this.
   while (!VersionStack.empty()) {
     BasicBlock *BackBlock = VersionStack.back()->getBlock();
     if (DT->dominates(BackBlock, BB))
       break;
+    // FIXME: This doesn't check if stack if stack empty.
+    // fix it, or write a comment if sentinel exists.
     while (VersionStack.back()->getBlock() == BackBlock)
       VersionStack.pop_back();
     ++PopEpoch;
   }
   for (MemoryAccess &MA : *Accesses) {
     auto *MU = dyn_cast<MemoryUse>(&MA);
     if (!MU) {
       VersionStack.push_back(&MA);
if (FoundClobberResult || UpperBound < LocInfo.LastKill) {
       // LastKill.
       MU->setDefiningAccess(VersionStack[LocInfo.LastKill], true);
     }
     LocInfo.LowerBound = VersionStack.size() - 1;
     LocInfo.LowerBoundBlock = BB;
   }
 }
 
+void MemorySSA::OptimizeUses::optimizeInvariantGroupUsesInBlock(
+    const BasicBlock *BB,
+    MostDominatingInvariantGroupMap &MostDominatingInvariantGroup,
+    SmallVectorImpl<InsertedInvariantGroupInfo> &InsertedInvariants) {
+
+  const auto *InvariantGroupAccesses = MSSA->getInvariantGroupBlockAccesses(BB);
+  if (!InvariantGroupAccesses)
+    return;
+
+  // Erase inserted information from not dominated blocks.
+  BasicBlock *LastBlock = nullptr;
+  while (!InsertedInvariants.empty()) {
+    BasicBlock *const CurrentBlock =
+        InsertedInvariants.back().DefiningAccess->getBlock();
+    // Cache Last block to avoid checking for dominance.
+    if (LastBlock != CurrentBlock) {
+      LastBlock = CurrentBlock;
+      if (DT->dominates(CurrentBlock, BB))
+        break;
+    }
+    
+    InsertedInvariantGroupInfo GI = InsertedInvariants.back();
+    MostDominatingInvariantGroup.erase({GI.PointerOperand, GI.InvariantGroup});
+    InsertedInvariants.pop_back();
+  }
+
+  // Walk all loads/stores with !invariant.group, checking if there is
+  // dominating memory access with coresponding pointer operand and invariant
+  // group. If found then use it, if not then add it to map.
+  for (MemoryUseOrDef *MU : *InvariantGroupAccesses) {
+    auto *I = MU->getMemoryInst();
+    InsertedInvariantGroupInfo GI;
+    GI.InvariantGroup = I->getMetadata(LLVMContext::MD_invariant_group);
+    if (auto *LI = dyn_cast<LoadInst>(I))
+      GI.PointerOperand = LI->getPointerOperand()->stripPointerCasts();
+    else if (auto *SI = dyn_cast<StoreInst>(I))
+      GI.PointerOperand = SI->getPointerOperand()->stripPointerCasts();
+    assert(GI.PointerOperand && GI.InvariantGroup && "Nonnulls inserted");
+
+    const auto It = MostDominatingInvariantGroup.find(
+        {GI.PointerOperand, GI.InvariantGroup});
+    // We found dominating Instruction with the same operand and group.
+    if (It != MostDominatingInvariantGroup.end()) {
+      // Can't optimize Defs.
+      if (isa<MemoryDef>(MU))
+        continue;
+
+      // Skip liveOnEntry uses to not pesimize.
+      if (MSSA->isLiveOnEntryDef(MU->getDefiningAccess()))
+        continue;
+      MU->setDefiningAccess(It->second);
+    } else {
+      MemoryAccess *InsertingAccess;
+      if (isa<MemoryUse>(MU))
+        InsertingAccess = MU->getDefiningAccess();
+      else // MemoryDef
+        InsertingAccess = MU;
+
+      GI.DefiningAccess = InsertingAccess;
+      MostDominatingInvariantGroup[{GI.PointerOperand, GI.InvariantGroup}] =
+          InsertingAccess;
+      InsertedInvariants.push_back(GI);
+    }
+  }
+}
+
 /// Optimize uses to point to their actual clobbering definitions.
 void MemorySSA::OptimizeUses::optimizeUses() {
 
   // We perform a non-recursive top-down dominator tree walk
   struct StackInfo {
     const DomTreeNode *Node;
     DomTreeNode::const_iterator Iter;
   };
 
   SmallVector<MemoryAccess *, 16> VersionStack;
+  // FIXME: this is not used.
   SmallVector<StackInfo, 16> DomTreeWorklist;
   DenseMap<MemoryLocOrCall, MemlocStackInfo> LocStackInfo;
   VersionStack.push_back(MSSA->getLiveOnEntryDef());
 
+  MostDominatingInvariantGroupMap InvariantGroups;
+  SmallVector<InsertedInvariantGroupInfo, 16> InsertedInvariantGroups;
   unsigned long StackEpoch = 1;
   unsigned long PopEpoch = 1;
-  for (const auto *DomNode : depth_first(DT->getRootNode()))
+  for (const auto *DomNode : depth_first(DT->getRootNode())) {
     optimizeUsesInBlock(DomNode->getBlock(), StackEpoch, PopEpoch, VersionStack,
                         LocStackInfo);
+    optimizeInvariantGroupUsesInBlock(DomNode->getBlock(), InvariantGroups,
+                                      InsertedInvariantGroups);
+  }
 }
 
 void MemorySSA::placePHINodes(
     const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks,
     const DenseMap<const BasicBlock *, unsigned int> &BBNumbers) {
   // Determine where our MemoryPhi's should go
   ForwardIDFCalculator IDFs(*DT);
   IDFs.setDefiningBlocks(DefiningBlocks);
for (auto &BB : IDFBlocks) {
     AccessList *Accesses = getOrCreateAccessList(BB);
     MemoryPhi *Phi = new MemoryPhi(BB->getContext(), BB, NextID++);
     ValueToMemoryAccess[BB] = Phi;
     // Phi's always are placed at the front of the block.
     Accesses->push_front(Phi);
   }
 }
 
+static bool hasInvariantGroupMD(const Instruction &I) {
+  return I.getMetadata(LLVMContext::MD_invariant_group) != nullptr;
+}
+
 void MemorySSA::buildMemorySSA() {
   // We create an access to represent "live on entry", for things like
   // arguments or users of globals, where the memory they use is defined before
   // the beginning of the function. We do not actually insert it into the IR.
   // We do not define a live on exit for the immediate uses, and thus our
   // semantics do *not* imply that something with no immediate uses can simply
   // be removed.
   BasicBlock &StartingPoint = F.getEntryBlock();
   LiveOnEntryDef = make_unique<MemoryDef>(F.getContext(), nullptr, nullptr,
                                           &StartingPoint, NextID++);
   DenseMap<const BasicBlock *, unsigned int> BBNumbers;
   unsigned NextBBNum = 0;
 
   // We maintain lists of memory accesses per-block, trading memory for time. We
   // could just look up the memory access for every possible instruction in the
   // stream.
   SmallPtrSet<BasicBlock *, 32> DefiningBlocks;
   SmallPtrSet<BasicBlock *, 32> DefUseBlocks;
+  SmallVector<MemoryUseOrDef *, 4> InvariantGroupAccesses;
   // Go through each block, figure out where defs occur, and chain together all
   // the accesses.
   for (BasicBlock &B : F) {
     BBNumbers[&B] = NextBBNum++;
     bool InsertIntoDef = false;
     AccessList *Accesses = nullptr;
     for (Instruction &I : B) {
       MemoryUseOrDef *MUD = createNewAccess(&I);
       if (!MUD)
         continue;
       InsertIntoDef |= isa<MemoryDef>(MUD);
 
       if (!Accesses)
         Accesses = getOrCreateAccessList(&B);
       Accesses->push_back(MUD);
+
+      if (hasInvariantGroupMD(I))
+        InvariantGroupAccesses.push_back(MUD);
     }
     if (InsertIntoDef)
       DefiningBlocks.insert(&B);
     if (Accesses)
       DefUseBlocks.insert(&B);
+    if (!InvariantGroupAccesses.empty()) {
+      PerBlockInvariantGroupAccesses.try_emplace(
+          &B, std::move(InvariantGroupAccesses));
+      InvariantGroupAccesses.clear();
+    }
   }
   placePHINodes(DefiningBlocks, BBNumbers);
 
   // Now do regular SSA renaming on the MemoryDef/MemoryUse. Visited will get
   // filled in with all blocks.
   SmallPtrSet<BasicBlock *, 16> Visited;
   renamePass(DT->getRootNode(), LiveOnEntryDef.get(), Visited);
 

test/Transforms/Util/MemorySSA/invariant-groups.ll

 
 ; This have to be MemoryUse(1), because we can't skip the barrier based on
 ; invariant.group.
 ; CHECK: MemoryUse(2)
 ; CHECK-NEXT: %2 = load i32
   %2 = load i32, i32* %a32, align 4, !invariant.group !0
   ret i32 %2
 }
+; CHECK-LABEL: define i8 @differentGroups
+define i8 @differentGroups(i8* %a) {
+; CHECK: 1 = MemoryDef(liveOnEntry)
+  store i8 0, i8* %a, align 4, !invariant.group !0
+; CHECK: 2 = MemoryDef(1)
+  store i8 0, i8* %a, align 4, !invariant.group !1
+; CHECK 3 = MemoryDef(2)
+  call void @clobber8(i8* %a)
 
+; CHECK: MemoryUse(1)
+  %1 = load i8, i8* %a, !invariant.group !0
+; CHECK: MemoryUse(2)
+  %2 = load i8, i8* %a, !invariant.group !1
+; CHECK: MemoryUse(3)
+  %3 = load i8, i8* %a, !invariant.group !2
+; CHECK: MemoryUse(1)
+  %4 = load i8, i8* %a, !invariant.group !0
+  ret i8 %4
+}
+
+; CHECK-LABEL: define i32 @skipBarrier
 define i32 @skipBarrier(i32* %a) {
 ; CHECK: 1 = MemoryDef(liveOnEntry)
 ; CHECK-NEXT: store i32 0
   store i32 0, i32* %a, align 4, !invariant.group !0
 
   %1 = bitcast i32* %a to i8*
   %a8 = call i8* @llvm.invariant.group.barrier(i8* %1)
   %a32 = bitcast i8* %a8 to i32*

 ; 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: 1 = MemoryDef(liveOnEntry)
 ; CHECK-NEXT: store i32 1
   store i32 1, i32* @g, align 4
 
-; FIXME: based on invariant.group it should be MemoryUse(liveOnEntry)
-; CHECK: MemoryUse(1)
+; CHECK: MemoryUse(liveOnEntry)
 ; 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: 3 = MemoryDef(2)
 ; CHECK-NEXT: store i32 2
   store i32 2, i32* @g, align 4
 
-; FIXME: This can be changed to MemoryUse(2)
-; CHECK: MemoryUse(3)
+; CHECK: MemoryUse(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)
+; CHECK: MemoryUse(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)
+; CHECK: MemoryUse(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: call void @clobber
   br i1 undef, label %Loop.Body, label %Loop.End
 
 Loop.Body:
 ; 4 = MemoryPhi({entry,2},{Loop.Body,3},{Loop.End,5})
 ; CHECK: MemoryUse(4)
 ; CHECK-NEXT: %0 = load i8
   %0 = load i8, i8* %after, !invariant.group !0
 
-; FIXME: MemoryUse(1)
-; CHECK: MemoryUse(4)
+; CHECK: MemoryUse(1)
 ; CHECK-NEXT: %1 = load i8
   %1 = load i8, i8* %p, !invariant.group !0
 
 ; CHECK: 3 = MemoryDef(4)
   store i8 4, i8* %after, !invariant.group !0
 
   br i1 undef, label %Loop.End, label %Loop.Body
 
 Loop.End:
 ; 5 = MemoryPhi({entry,2},{Loop.Body,3})
 ; CHECK: MemoryUse(5)
 ; CHECK-NEXT: %2 = load
-  %2 = load i8, i8* %after, align 4, !invariant.group !0
+  %2 = load i8, i8* %after, !invariant.group !0
 
-; FIXME: MemoryUse(1)
-; CHECK: MemoryUse(5)
+; CHECK: MemoryUse(1)
 ; CHECK-NEXT: %3 = load
-  %3 = load i8, i8* %p, align 4, !invariant.group !0
+  %3 = load i8, i8* %p, !invariant.group !0
   br i1 undef, label %Ret, label %Loop.Body
 
 Ret:
   ret i8 %3
 }
 
-
 define i8 @loop3(i8* %p) {
 entry:
 ; CHECK: 1 = MemoryDef(liveOnEntry)
 ; CHECK-NEXT: store i8
   store i8 4, i8* %p, !invariant.group !0
 ; CHECK: 2 = MemoryDef(1)
 ; CHECK-NEXT: call void @clobber
   call void @clobber8(i8* %p)
   %after = call i8* @llvm.invariant.group.barrier(i8* %p)
   br i1 undef, label %Loop.Body, label %Loop.End
 
 Loop.Body:
 ; CHECK: 6 = MemoryPhi({entry,2},{Loop.Body,3},{Loop.next,4},{Loop.End,5})
 ; CHECK: MemoryUse(6)
 ; CHECK-NEXT: %0 = load i8
   %0 = load i8, i8* %after, !invariant.group !0
 
 ; CHECK: 3 = MemoryDef(6)
 ; CHECK-NEXT: call void @clobber8
   call void @clobber8(i8* %after)
 
-; FIXME: MemoryUse(6)
-; CHECK: MemoryUse(3)
+; CHECK: MemoryUse(6)
 ; 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: 4 = MemoryDef(3)
 ; CHECK-NEXT: call void @clobber8
   call void @clobber8(i8* %after)
 
-; FIXME: MemoryUse(6)
-; CHECK: MemoryUse(4)
+; CHECK: MemoryUse(6)
 ; 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: 7 = MemoryPhi({entry,2},{Loop.next,4})
 ; CHECK: MemoryUse(7)
 ; CHECK-NEXT: %3 = load
   %3 = load i8, i8* %after, align 4, !invariant.group !0
 
 ; CHECK: 5 = MemoryDef(7)
 ; CHECK-NEXT: call void @clobber8
   call void @clobber8(i8* %after)
 
-; FIXME: MemoryUse(7)
-; CHECK: MemoryUse(5)
+; CHECK: MemoryUse(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
 }
 

 
 Loop.Pre:
 ; CHECK: MemoryUse(2)
 ; CHECK-NEXT: %0 = load i8
   %0 = load i8, i8* %after, !invariant.group !0
   br label %Loop.Body
 Loop.Body:
 ; CHECK: 4 = MemoryPhi({Loop.Pre,2},{Loop.Body,3},{Loop.End,5})
-; CHECK-NEXT: MemoryUse(4)
+; CHECK-NEXT: MemoryUse(2)
 ; CHECK-NEXT: %1 = load i8
   %1 = load i8, i8* %after, !invariant.group !0
 
-; FIXME: MemoryUse(2)
-; CHECK: MemoryUse(4)
+; CHECK: MemoryUse(1)
 ; CHECK-NEXT: %2 = load i8
   %2 = load i8, i8* %p, !invariant.group !0
 
 ; CHECK: 3 = MemoryDef(4)
+; CHECK-NEXT: store
   store i8 4, i8* %after, !invariant.group !0
   br i1 undef, label %Loop.End, label %Loop.Body
 
 Loop.End:
 ; CHECK: 5 = MemoryPhi({entry,2},{Loop.Body,3})
-; CHECK-NEXT: MemoryUse(5)
+; CHECK-NEXT: MemoryUse(2)
 ; CHECK-NEXT: %3 = load
   %3 = load i8, i8* %after, align 4, !invariant.group !0
 
-; FIXME: MemoryUse(2)
-; CHECK: MemoryUse(5)
+; CHECK: MemoryUse(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
 }
+; CHECK-LABEL: define i8 @diamond
+define i8 @diamond(i8* %p) {
+entry:
+; CHECK: 1 = MemoryDef(liveOnEntry)
+  store i8 4, i8* %p, !invariant.group !0
+  %after = call i8* @llvm.invariant.group.barrier(i8* %p)
+; CHECK: 2 = MemoryDef(1)
+  call void @clobber8(i8* %p)
+  br i1 undef, label %First, label %Ret
+
+First:                                            ; preds = %entry
+; CHECK: MemoryUse(2)
+  %0 = load i8, i8* %after, !invariant.group !0
+; CHECK: 3 = MemoryDef(2)
+  call void @clobber8(i8* %p)
+  br i1 undef, label %Second1, label %Second2
+
+Second1:                                          ; preds = %First
+; CHECK: 4 = MemoryDef(3)
+  call void @clobber8(i8* %p)
+; CHECK: MemoryUse(4)
+  %1 = load i8, i8* %after, !invariant.group !1
+; CHECK: MemoryUse(1)
+  %2 = load i8, i8* %p, !invariant.group !0
+; CHECK: MemoryUse(4)
+  %3 = load i8, i8* %p, !invariant.group !1
+; CHECK: 5 = MemoryDef(4)
+  call void @clobber8(i8* %p)
+  br label %Diamond
+
+Second2:                                          ; preds = %First
+; CHECK: 6 = MemoryDef(3)
+  call void @clobber8(i8* %p)
+; CHECK: MemoryUse(6)
+  %4 = load i8, i8* %after, !invariant.group !1
+; CHECK: MemoryUse(1)
+  %5 = load i8, i8* %p, !invariant.group !0
+; CHECK: MemoryUse(6)
+  %6 = load i8, i8* %p, !invariant.group !1
+; CHECK: 7 = MemoryDef(6)
+  call void @clobber8(i8* %p)
+  br label %Diamond
+
+Diamond:                                          ; preds = %Second2, %Second1
+; CHECK: 11 = MemoryPhi({Second1,5},{Second2,7})
+; CHECK: 8 = MemoryDef(11)
+  call void @clobber8(i8* %p)
+; CHECK: MemoryUse(8)
+  %7 = load i8, i8* %after, !invariant.group !1
+; CHECK: MemoryUse(1)
+  %8 = load i8, i8* %p, !invariant.group !0
+; CHECK: MemoryUse(8)
+  %9 = load i8, i8* %p, !invariant.group !1
+; CHECK: MemoryUse(8)
+  %10 = load i8, i8* %after, !invariant.group !1
+; CHECK: MemoryUse(8)
+  %11 = load i8, i8* %after, !invariant.group !2
+; CHECK: 9 = MemoryDef(8)
+  call void @clobber8(i8* %p)
+  br label %Ret
+
+Ret:                                              ; preds = %Diamond, %entry
+; CHECK: 12 = MemoryPhi({entry,2},{Diamond,9})
+; CHECK: 10 = MemoryDef(12)
+  call void @clobber8(i8* %p)
+; CHECK: MemoryUse(10)
+  %12 = load i8, i8* %after, !invariant.group !2
+; CHECK: MemoryUse(10)
+  %13 = load i8, i8* %after, !invariant.group !1
+; CHECK: MemoryUse(1)
+  %14 = load i8, i8* %p, !invariant.group !0
+; CHECK: MemoryUse(10)
+  %15 = load i8, i8* %p, !invariant.group !1
+  ret i8 %15
+}
+
+; From NewGVN/invariant.group.ll
+@unknownPtr = external global i8
+; CHECK-LABEL: define void @testGlobal() {
+define void @testGlobal() {
+; CHECK: MemoryUse(liveOnEntry)
+  %a = load i8, i8* @unknownPtr, !invariant.group !0
+; CHECK: 1 = MemoryDef(liveOnEntry)
+  call void @clobber8(i8* @unknownPtr)
+; CHECK: MemoryUse(liveOnEntry)
+  %1 = load i8, i8* @unknownPtr, !invariant.group !0
+; CHECK: 2 = MemoryDef(1)
+  call void @clobber8(i8* @unknownPtr)
+  %b0 = bitcast i8* @unknownPtr to i1*
+; CHECK: 3 = MemoryDef(2)
+  call void @clobber8(i8* @unknownPtr)
+; CHECK: MemoryUse(liveOnEntry)
+  %2 = load i1, i1* %b0, !invariant.group !0
+; CHECK: 4 = MemoryDef(3)
+  call void @clobber8(i8* @unknownPtr)
+; CHECK: MemoryUse(liveOnEntry)
+  %3 = load i1, i1* %b0, !invariant.group !0
+  ret void
+}
+
+
+%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*
+declare void @_ZN1A3fooEv(%struct.A*)
+declare void @_ZN1AC1Ev(%struct.A*)
+declare i8* @getPointer(i8*)
+
+; CHECK-LABEL: define void @combiningBitCastWithLoad() {
+define void @combiningBitCastWithLoad() {
+  %a = alloca %struct.A*, align 8
+  %s2 = bitcast %struct.A** %a to i8*
+; CHECK: 1 = MemoryDef(liveOnEntry)
+  call void @clobber8(i8* null)
+  %x = bitcast i8* %s2 to i1*
+; CHECK: 2 = MemoryDef(1)
+  store i1 1, i1* %x, !invariant.group !0
+  %1 = bitcast i8* %s2 to %struct.A*
+; CHECK: 3 = MemoryDef(2)
+  call void @_ZN1AC1Ev(%struct.A* %1)
+  %2 = bitcast %struct.A* %1 to i8***
+; CHECK: MemoryUse(2)
+  %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)
+; CHECK: 4 = MemoryDef(3)
+  store %struct.A* %1, %struct.A** %a, align 8
+; CHECK: MemoryUse(4)
+  %3 = load %struct.A*, %struct.A** %a, align 8
+  %4 = bitcast %struct.A* %3 to void (%struct.A*)***
+; CHECK: MemoryUse(4)
+  %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
+; CHECK: MemoryUse(4)
+  %5 = load void (%struct.A*)*, void (%struct.A*)** %vfn, align 8
+; CHECK: 5 = MemoryDef(4)
+  call void %5(%struct.A* %3)
+  ret void
+}
 
 declare i8* @llvm.invariant.group.barrier(i8*)
 declare void @clobber(i32*)
 declare void @clobber8(i8*)
 
 
 !0 = !{!"group1"}
+!1 = !{!"other"}
+!2 = !{!"other2"}