invariant.group handling in GVN

[Prazek]

Summary

The most important part required to make clang

devirtualization works ( ͡°͜ʖ ͡°).
The code is able to find non local dependencies, but unfortunatelly
because the caller can only handle local dependencies, I had to add
some restrictions to look for dependencies only in the same

[rsmith]

include/llvm/Analysis/MemoryDependenceAnalysis.h

420

Typo "Incariant"; use \brief insteaed of repeating the function name here.

422

will -> does

423

loads or stores -> load or store

lib/Analysis/MemoryDependenceAnalysis.cpp

379

Revert this blank line insertion.

lib/Transforms/Utils/Local.cpp

1425

instruction has -> instructions have

1426

Maybe add a FIXME stating that we should try to preserve both groups in this case.

[• dberlin]

lib/Analysis/MemoryDependenceAnalysis.cpp

402

Well, it's safe, if you verify the use is in LI->getParent()->getParent(), no?

[Prazek]

lib/Analysis/MemoryDependenceAnalysis.cpp

402

Yes, but nobody guarantee that uses list won't change when I will iterate over it.

[Prazek]

Forgot to include test!

[Prazek]

Fixed combine metadata

[nlewycky]

include/llvm/Analysis/MemoryDependenceAnalysis.h

400

I don't think that's "brief". "[A] brief description is a short one-liner" -- https://www.stack.nl/~dimitri/doxygen/manual/docblocks.html

420

Brief again.

lib/Analysis/MemoryDependenceAnalysis.cpp

399

"use list" not "uses list" (two occurrences in this line).

402

It's the 'function passes aren't allowed to look outside their functions' rule, as-if we had function passes running in parallel.

419

Hold up. If there's three loads, A B and C, all of them in the same invariant group, and C is the QueryInst for getPointerDependencyFrom, and A and B both dominate C, doesn't the value returned right here depend on the order of the use list? That seems undesirable, but I'm not sure whether that's considered a serious problem or not.

lib/Transforms/Scalar/GVN.cpp

2480

Spurious change

lib/Transforms/Utils/Local.cpp

1432–1433

Just move this part into the "case LLVMContext::MD_invariant_group:" ?

test/Transforms/GVN/invariant.group.ll

147

Space after colon

[Prazek]

You call it devirtualization? This is devirtualization

[Prazek]

lib/Analysis/MemoryDependenceAnalysis.cpp

419

it doesn't matter if we will return Def for A or B, because they will load the same value. The second thing is that we will process them in order which they are in the block, which means that for A we will do nothing, for B we will return Def(A) and remove B, and for C the same thing (because B will not longer exist)

lib/Transforms/Utils/Local.cpp

1432–1433

It won't work because we iterate over K metadata

[Prazek]

reformated

[Prazek]

small fixes

[Prazek]

Works only on single block, I don't think I will make it to work non locally

[nlewycky]

LGTM, thanks for the extensive gvn test!

include/llvm/Analysis/MemoryDependenceAnalysis.h

422

... if *it* does not find ...

426

Either "on the caller" or "at the call site".

lib/Analysis/MemoryDependenceAnalysis.cpp

398

Extra newline.

411

"equivalent"

include/llvm/Analysis/MemoryDependenceAnalysis.h

public:
     /// in more places that cached info does not necessarily keep.
     void invalidateCachedPointerInfo(Value *Ptr);
 
     /// invalidateCachedPredecessors - Clear the PredIteratorCache info.
     /// This needs to be done when the CFG changes, e.g., due to splitting
     /// critical edges.
     void invalidateCachedPredecessors();
 
-    /// getPointerDependencyFrom - Return the instruction on which a memory
+    /// \brief - Return the instruction on which a memory
     /// location depends.  If isLoad is true, this routine ignores may-aliases
     /// with read-only operations.  If isLoad is false, this routine ignores
     /// may-aliases with reads from read-only locations. If possible, pass
     /// the query instruction as well; this function may take advantage of
     /// the metadata annotated to the query instruction to refine the result.
     ///
     /// Note that this is an uncached query, and thus may be inefficient.
     ///
     MemDepResult getPointerDependencyFrom(const MemoryLocation &Loc,
                                           bool isLoad,
                                           BasicBlock::iterator ScanIt,
                                           BasicBlock *BB,
                                           Instruction *QueryInst = nullptr);
 
+    MemDepResult getSimplePointerDependencyFrom(const MemoryLocation &MemLoc,
+                                                bool isLoad,
+                                                BasicBlock::iterator ScanIt,
+                                                BasicBlock *BB,
+                                                Instruction *QueryInst);
+
+    /// \brief - This analysis looks for other
+    /// loads and stores with invariant.group metadata and the same
+    /// pointer operand. Returns Unknown if does not find anything, and Def
+    /// if it can be assumed that 2 instructions load or store the same value.
+    MemDepResult getInvariantGroupPointerDependency(LoadInst *LI);
+
     /// getLoadLoadClobberFullWidthSize - This is a little bit of analysis that
     /// looks at a memory location for a load (specified by MemLocBase, Offs,
     /// and Size) and compares it against a load.  If the specified load could
     /// be safely widened to a larger integer load that is 1) still efficient,
     /// 2) safe for the target, and 3) would provide the specified memory
     /// location value, then this function returns the size in bytes of the
     /// load width to use.  If not, this returns zero.
     static unsigned getLoadLoadClobberFullWidthSize(const Value *MemLocBase,

lib/Analysis/MemoryDependenceAnalysis.cpp

 
 
 /// getPointerDependencyFrom - Return the instruction on which a memory
 /// location depends.  If isLoad is true, this routine ignores may-aliases with
 /// read-only operations.  If isLoad is false, this routine ignores may-aliases
 /// with reads from read-only locations.  If possible, pass the query
 /// instruction as well; this function may take advantage of the metadata
 /// annotated to the query instruction to refine the result.
 MemDepResult MemoryDependenceAnalysis::getPointerDependencyFrom(
     const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
     BasicBlock *BB, Instruction *QueryInst) {
 
+  if (QueryInst != nullptr)
+    if (auto *LI = dyn_cast<LoadInst>(QueryInst)) {
+      MemDepResult invariantGroupPointerDependency =
+          getInvariantGroupPointerDependency(LI);
+      if (!invariantGroupPointerDependency.isUnknown())
+        return invariantGroupPointerDependency;
+    }
+
+  return getSimplePointerDependencyFrom(MemLoc, isLoad, ScanIt, BB, QueryInst);
+}
+
+MemDepResult
+MemoryDependenceAnalysis::getInvariantGroupPointerDependency(LoadInst *LI) {
+
+  Value *LoadOperand = LI->getPointerOperand();
+  // It's is not safe to walk the use list of global value, because nobody
+  // guarantee that uses list won't change during iteration (uses list doesn't
+  // have
+  // any lock and there might be loads in different functions being optimized
+  // in the same time).
+  if (isa<GlobalValue>(LoadOperand))
+    return MemDepResult::getUnknown();
+
+  auto *InvariantGroupMD = LI->getMetadata(LLVMContext::MD_invariant_group);
+  if (!InvariantGroupMD)
+    return MemDepResult::getUnknown();
+
+  llvm::SmallSet<Value *, 12> Seen;
+  // Queue to process all pointers that are equavalent to load operand.
+  llvm::SmallVector<Value *, 12> LoadOperandsQueue;
+  LoadOperandsQueue.push_back(LoadOperand);
+  while (!LoadOperandsQueue.empty()) {
+    Value *Ptr = LoadOperandsQueue.pop_back_val();
+    if (auto *BCI = dyn_cast<BitCastInst>(Ptr)) {
+      if (!Seen.count(BCI->getOperand(0))) {
+        LoadOperandsQueue.push_back(BCI->getOperand(0));
+        Seen.insert(BCI->getOperand(0));
+      }
+    }
+
+    for (Use &Us : Ptr->uses()) {
+      auto *U = dyn_cast<Instruction>(Us.getUser());
+      if (!U || U == LI || DT->dominates(LI, Us))
+        continue;
+
+      if (auto *BCI = dyn_cast<BitCastInst>(U)) {
+        if (!Seen.count(BCI)) {
+          LoadOperandsQueue.push_back(BCI);
+          Seen.insert(BCI);
+        }
+        // If we hit load/store with the same invariant.group metadata (and the
+        // same pointer operand) we can assume that value pointed by pointer
+        // operand didn't change.
+      } else if ((isa<LoadInst>(U) || isa<StoreInst>(U)) &&
+                 U->getMetadata(LLVMContext::MD_invariant_group) ==
+                     InvariantGroupMD)
+        return MemDepResult::getDef(U);
+    }
+  }
+
+  return MemDepResult::getUnknown();
+}
+
+MemDepResult MemoryDependenceAnalysis::getSimplePointerDependencyFrom(
+    const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
+    BasicBlock *BB, Instruction *QueryInst) {
+
   const Value *MemLocBase = nullptr;
   int64_t MemLocOffset = 0;
   unsigned Limit = BlockScanLimit;
   bool isInvariantLoad = false;
 
   // We must be careful with atomic accesses, as they may allow another thread
   //   to touch this location, cloberring it. We are conservative: if the
   //   QueryInst is not a simple (non-atomic) memory access, we automatically

lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

Instruction *InstCombiner::visitLoadInst(LoadInst &LI) {
   // separated by a few arithmetic operations.
   BasicBlock::iterator BBI = &LI;
   AAMDNodes AATags;
   if (Value *AvailableVal =
       FindAvailableLoadedValue(Op, LI.getParent(), BBI,
                                DefMaxInstsToScan, AA, &AATags)) {
     if (LoadInst *NLI = dyn_cast<LoadInst>(AvailableVal)) {
       unsigned KnownIDs[] = {
-        LLVMContext::MD_tbaa,
-        LLVMContext::MD_alias_scope,
-        LLVMContext::MD_noalias,
-        LLVMContext::MD_range,
-        LLVMContext::MD_invariant_load,
-        LLVMContext::MD_nonnull,
-      };
+          LLVMContext::MD_tbaa,           LLVMContext::MD_alias_scope,
+          LLVMContext::MD_noalias,        LLVMContext::MD_range,
+          LLVMContext::MD_invariant_load, LLVMContext::MD_nonnull,
+          LLVMContext::MD_invariant_group};
       combineMetadata(NLI, &LI, KnownIDs);
     };
 
     return ReplaceInstUsesWith(
         LI, Builder->CreateBitOrPointerCast(AvailableVal, LI.getType(),
                                             LI.getName() + ".cast"));
   }
 

lib/Transforms/Scalar/GVN.cpp

Instruction *NewLoad = new LoadInst(LoadPtr, LI->getName()+".pre", false,
                                         UnavailablePred->getTerminator());
 
     // Transfer the old load's AA tags to the new load.
     AAMDNodes Tags;
     LI->getAAMetadata(Tags);
     if (Tags)
       NewLoad->setAAMetadata(Tags);
 
+    if (auto *InvGroupMD = LI->getMetadata(LLVMContext::MD_invariant_group))
+      NewLoad->setMetadata(LLVMContext::MD_invariant_group, InvGroupMD);
+
     // Transfer DebugLoc.
     NewLoad->setDebugLoc(LI->getDebugLoc());
 
     // Add the newly created load.
     ValuesPerBlock.push_back(AvailableValueInBlock::get(UnavailablePred,
                                                         NewLoad));
     MD->invalidateCachedPointerInfo(LoadPtr);
     DEBUG(dbgs() << "GVN INSERTED " << *NewLoad << '\n');
if (Instruction *ReplInst = dyn_cast<Instruction>(Repl)) {
     // guarantees the execution of the other), then we can combine the
     // noalias scopes here and do better than the general conservative
     // answer used in combineMetadata().
 
     // In general, GVN unifies expressions over different control-flow
     // regions, and so we need a conservative combination of the noalias
     // scopes.
     static const unsigned KnownIDs[] = {
-      LLVMContext::MD_tbaa,
-      LLVMContext::MD_alias_scope,
-      LLVMContext::MD_noalias,
-      LLVMContext::MD_range,
-      LLVMContext::MD_fpmath,
-      LLVMContext::MD_invariant_load,
-    };
+        LLVMContext::MD_tbaa,           LLVMContext::MD_alias_scope,
+        LLVMContext::MD_noalias,        LLVMContext::MD_range,
+        LLVMContext::MD_fpmath,         LLVMContext::MD_invariant_load,
+        LLVMContext::MD_invariant_group};
     combineMetadata(ReplInst, I, KnownIDs);
   }
 }
 
 static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl) {
   patchReplacementInstruction(I, Repl);
   I->replaceAllUsesWith(Repl);
 }

 bool GVN::replaceOperandsWithConsts(Instruction *Instr) const {
   bool Changed = false;
   for (unsigned OpNum = 0; OpNum < Instr->getNumOperands(); ++OpNum) {
     Value *Operand = Instr->getOperand(OpNum);
     auto it = ReplaceWithConstMap.find(Operand);
     if (it != ReplaceWithConstMap.end()) {
       assert(!isa<Constant>(Operand) &&
              "Replacing constants with constants is invalid");
+      DEBUG(dbgs() << "GVN replacing: " << *Operand << " with " << *it->second
+                   << " in instruction " << *Instr << '\n');
       Instr->setOperand(OpNum, it->second);
       Changed = true;
     }
   }
   return Changed;
 }
 
 /// The given values are known to be equal in every block
bool GVN::runOnFunction(Function& F) {
   cleanupGlobalSets();
   // Do not cleanup DeadBlocks in cleanupGlobalSets() as it's called for each
   // iteration. 
   DeadBlocks.clear();
 
   return Changed;
 }
 
-
 bool GVN::processBlock(BasicBlock *BB) {
   // FIXME: Kill off InstrsToErase by doing erasing eagerly in a helper function
   // (and incrementing BI before processing an instruction).
   assert(InstrsToErase.empty() &&
          "We expect InstrsToErase to be empty across iterations");
   if (DeadBlocks.count(BB))
     return false;
 
   // Clearing map before every BB because it can be used only for single BB.
   ReplaceWithConstMap.clear();
   bool ChangedFunction = false;
 
   for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
        BI != BE;) {
+
     if (!ReplaceWithConstMap.empty())
       ChangedFunction |= replaceOperandsWithConsts(BI);
     ChangedFunction |= processInstruction(BI);
 
     if (InstrsToErase.empty()) {
       ++BI;
       continue;
     }

lib/Transforms/Scalar/MemCpyOptimizer.cpp

bool MemCpyOpt::performCallSlotOptzn(Instruction *cpy,
 
   // Drop any cached information about the call, because we may have changed
   // its dependence information by changing its parameter.
   MD->removeInstruction(C);
 
   // Update AA metadata
   // FIXME: MD_tbaa_struct and MD_mem_parallel_loop_access should also be
   // handled here, but combineMetadata doesn't support them yet
-  unsigned KnownIDs[] = {
-    LLVMContext::MD_tbaa,
-    LLVMContext::MD_alias_scope,
+  unsigned KnownIDs[] = {LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
                          LLVMContext::MD_noalias,
-  };
+                         LLVMContext::MD_invariant_group};
   combineMetadata(C, cpy, KnownIDs);
 
   // Remove the memcpy.
   MD->removeInstruction(cpy);
   ++NumMemCpyInstr;
 
   return true;
 }

lib/Transforms/Utils/Local.cpp

for (Function::iterator I = ++F.begin(); I != F.end();)
     if (!Reachable.count(I))
       I = F.getBasicBlockList().erase(I);
     else
       ++I;
 
   return true;
 }
 
-void llvm::combineMetadata(Instruction *K, const Instruction *J, ArrayRef<unsigned> KnownIDs) {
+void llvm::combineMetadata(Instruction *K, const Instruction *J,
+                           ArrayRef<unsigned> KnownIDs) {
   SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
   K->dropUnknownNonDebugMetadata(KnownIDs);
   K->getAllMetadataOtherThanDebugLoc(Metadata);
   for (unsigned i = 0, n = Metadata.size(); i < n; ++i) {
     unsigned Kind = Metadata[i].first;
     MDNode *JMD = J->getMetadata(Kind);
     MDNode *KMD = Metadata[i].second;
 
switch (Kind) {
       case LLVMContext::MD_invariant_load:
         // Only set the !invariant.load if it is present in both instructions.
         K->setMetadata(Kind, JMD);
         break;
       case LLVMContext::MD_nonnull:
         // Only set the !nonnull if it is present in both instructions.
         K->setMetadata(Kind, JMD);
         break;
+      case LLVMContext::MD_invariant_group:
+        // Preserve !invariant.group in K.
+        break;
     }
   }
+  // Set !invariant.group from J if J has it. If both instructions have it
+  // then we will just pick it from J - even when they are different.
+  // Also make sure that K is load or store - f.e. combining bitcast with load
+  // could produce bitcast with invariant.group metadata, which is invalid.
+  // FIXME: we should try to preserve both invariant.group md if they are
+  // different, but right now instruction can only have one invariant.group.
+  if (auto *JMD = J->getMetadata(LLVMContext::MD_invariant_group))
+    if (isa<LoadInst>(K) || isa<StoreInst>(K))
+      K->setMetadata(LLVMContext::MD_invariant_group, JMD);
 }
 
 unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
                                         DominatorTree &DT,
                                         const BasicBlockEdge &Root) {
   assert(From->getType() == To->getType());
   
   unsigned Count = 0;

lib/Transforms/Utils/SimplifyCFG.cpp

do {
     // For a normal instruction, we just move one to right before the branch,
     // then replace all uses of the other with the first.  Finally, we remove
     // the now redundant second instruction.
     BIParent->getInstList().splice(BI, BB1->getInstList(), I1);
     if (!I2->use_empty())
       I2->replaceAllUsesWith(I1);
     I1->intersectOptionalDataWith(I2);
     unsigned KnownIDs[] = {
-      LLVMContext::MD_tbaa,
-      LLVMContext::MD_range,
-      LLVMContext::MD_fpmath,
-      LLVMContext::MD_invariant_load,
-      LLVMContext::MD_nonnull
-    };
+        LLVMContext::MD_tbaa,    LLVMContext::MD_range,
+        LLVMContext::MD_fpmath,  LLVMContext::MD_invariant_load,
+        LLVMContext::MD_nonnull, LLVMContext::MD_invariant_group};
     combineMetadata(I1, I2, KnownIDs);
     I2->eraseFromParent();
     Changed = true;
 
     I1 = BB1_Itr++;
     I2 = BB2_Itr++;
     // Skip debug info if it is not identical.
     DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1);

lib/Transforms/Vectorize/BBVectorize.cpp

for (BasicBlock::iterator PI = BB.getFirstInsertionPt(); PI != BB.end();) {
         for (unsigned i = 0; i != NumOld; ++i)
           Tys.push_back(ReplacedOperands[i]->getType());
         CS.mutateFunctionType(
             FunctionType::get(getVecTypeForPair(L->getType(), H->getType()),
                               Tys, Old->isVarArg()));
       } else if (!isa<StoreInst>(K))
         K->mutateType(getVecTypeForPair(L->getType(), H->getType()));
 
-      unsigned KnownIDs[] = {
-        LLVMContext::MD_tbaa,
-        LLVMContext::MD_alias_scope,
-        LLVMContext::MD_noalias,
-        LLVMContext::MD_fpmath
-      };
+      unsigned KnownIDs[] = {LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
+                             LLVMContext::MD_noalias, LLVMContext::MD_fpmath,
+                             LLVMContext::MD_invariant_group};
       combineMetadata(K, H, KnownIDs);
       K->intersectOptionalDataWith(H);
 
       for (unsigned o = 0; o < NumOperands; ++o)
         K->setOperand(o, ReplacedOperands[o]);
 
       K->insertAfter(J);
 

test/Transforms/GVN/assume-equal.ll

if.else:                                          ; preds = %entry
   
   %call5 = tail call i32 %3(%struct.A* %0) #1
   br label %if.end
 
 if.end:                                           ; preds = %if.else, %if.then
   ret void
 }
 
+; Check integration with invariant.group handling
+; CHECK-LABEL: define void @invariantGroupHandling(i1 zeroext %p) {
+define void @invariantGroupHandling(i1 zeroext %p) {
+entry:
+  %call = tail call noalias i8* @_Znwm(i64 8) #4
+  %0 = bitcast i8* %call to %struct.A*
+  tail call void @_ZN1AC1Ev(%struct.A* %0) #1
+  %1 = bitcast i8* %call to i8***
+  %vtable = load i8**, i8*** %1, align 8, !invariant.group !0
+  %cmp.vtables = icmp eq i8** %vtable, getelementptr inbounds ([4 x i8*], [4 x i8*]* @_ZTV1A, i64 0, i64 2)
+  tail call void @llvm.assume(i1 %cmp.vtables)
+  br i1 %p, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  %vtable1.cast = bitcast i8** %vtable to i32 (%struct.A*)**
+  %2 = load i32 (%struct.A*)*, i32 (%struct.A*)** %vtable1.cast, align 8
+  
+; CHECK: call i32 @_ZN1A3fooEv(
+  %call2 = tail call i32 %2(%struct.A* %0) #1
+  %vtable1 = load i8**, i8*** %1, align 8, !invariant.group !0
+  %vtable2.cast = bitcast i8** %vtable1 to i32 (%struct.A*)**
+  %call1 = load i32 (%struct.A*)*, i32 (%struct.A*)** %vtable2.cast, align 8
+; CHECK: call i32 @_ZN1A3fooEv(
+  %callx = tail call i32 %call1(%struct.A* %0) #1
+  
+  %vtable2 = load i8**, i8*** %1, align 8, !invariant.group !0
+  %vtable3.cast = bitcast i8** %vtable2 to i32 (%struct.A*)**
+  %call4 = load i32 (%struct.A*)*, i32 (%struct.A*)** %vtable3.cast, align 8
+; CHECK: call i32 @_ZN1A3fooEv(
+  %cally = tail call i32 %call4(%struct.A* %0) #1
+  
+  %b = bitcast i8* %call to %struct.A**
+  %vtable3 = load %struct.A*, %struct.A** %b, align 8, !invariant.group !0
+  %vtable4.cast = bitcast %struct.A* %vtable3 to i32 (%struct.A*)**
+  %vfun = load i32 (%struct.A*)*, i32 (%struct.A*)** %vtable4.cast, align 8
+; CHECK: call i32 @_ZN1A3fooEv(
+  %unknown = tail call i32 %vfun(%struct.A* %0) #1
+  
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  %vfn47 = getelementptr inbounds i8*, i8** %vtable, i64 1
+  %vfn4 = bitcast i8** %vfn47 to i32 (%struct.A*)**
+  
+  ; CHECK: call i32 @_ZN1A3barEv(
+  %3 = load i32 (%struct.A*)*, i32 (%struct.A*)** %vfn4, align 8
+  
+  %call5 = tail call i32 %3(%struct.A* %0) #1
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  ret void
+}
+
+
 ; Checking const propagation in the same BB
 ; CHECK-LABEL: define i32 @main()
 
 define i32 @main() {
 entry:
   %call = tail call noalias i8* @_Znwm(i64 8) 
   %0 = bitcast i8* %call to %struct.A*
   tail call void @_ZN1AC1Ev(%struct.A* %0) 

 }
 
 declare noalias i8* @_Znwm(i64)
 declare void @_ZN1AC1Ev(%struct.A*)
 declare void @llvm.assume(i1)
 declare i32 @_ZN1A3fooEv(%struct.A*)
 declare i32 @_ZN1A3barEv(%struct.A*)
 
+!0 = !{!"struct A"}

test/Transforms/GVN/invariant.group.ll

+; RUN: opt < %s -gvn -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() {
+define i8 @simple() {
+entry:
+    %ptr = alloca i8
+    store i8 42, i8* %ptr, !invariant.group !0
+    call void @foo(i8* %ptr)
+
+    %a = load i8, i8* %ptr, !invariant.group !0
+    %b = load i8, i8* %ptr, !invariant.group !0
+    %c = load i8, i8* %ptr, !invariant.group !0
+; CHECK: ret i8 42
+    ret i8 %a
+}
+
+; CHECK-LABEL: define i8 @optimizable1() {
+define i8 @optimizable1() {
+entry:
+    %ptr = alloca i8
+    store i8 42, i8* %ptr, !invariant.group !0
+    %ptr2 = call i8* @llvm.invariant.group.barrier(i8* %ptr)
+    %a = load i8, i8* %ptr, !invariant.group !0
+    
+    call void @foo(i8* %ptr2); call to use %ptr2
+; CHECK: ret i8 42
+    ret i8 %a
+}
+
+; CHECK-LABEL: define i8 @optimizable2() {
+define i8 @optimizable2() {
+entry:
+    %ptr = alloca i8
+    store i8 42, i8* %ptr, !invariant.group !0
+    call void @foo(i8* %ptr)
+    
+    store i8 13, i8* %ptr ; can't use this store with invariant.group
+    %a = load i8, i8* %ptr 
+    call void @bar(i8 %a) ; call to use %a
+    
+    call void @foo(i8* %ptr)
+    %b = load i8, i8* %ptr, !invariant.group !0
+    
+; CHECK: ret i8 42
+    ret i8 %b
+}
+
+; CHECK-LABEL: define i8 @unoptimizable1() {
+define i8 @unoptimizable1() {
+entry:
+    %ptr = alloca i8
+    store i8 42, i8* %ptr
+    call void @foo(i8* %ptr)
+    %a = load i8, i8* %ptr, !invariant.group !0
+; CHECK: ret i8 %a
+    ret i8 %a
+}
+
+; CHECK-LABEL: define void @indirectLoads() {
+define void @indirectLoads() {
+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 !2
+  %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(
+  %vtable1 = load void (%struct.A*)**, void (%struct.A*)*** %4, align 8, !invariant.group !2
+  %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(
+  %vtable2 = load void (%struct.A*)**, void (%struct.A*)*** %7, align 8, !invariant.group !2
+  %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 !2
+  %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(
+  call void %11(%struct.A* %9)
+ 
+  %vtable5 = load i8**, i8*** %2, align 8, !invariant.group !2
+  %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(
+  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 !2
+  %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
+  %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 !2
+  %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
+  %a = load i8, i8* %ptr, !invariant.group !0
+; CHECK-NOT: load
+  %b = load i8, i8* %ptr, !invariant.group !1
+; 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
+  %c = load i8, i8* %ptr
+; CHECK-NOT: load
+  %d = load i8, i8* %ptr, !invariant.group !1
+; 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
+  %e = load i8, i8* %ptr, !invariant.group !1
+; 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 ![[OneMD:[0-9]]]
+  %e = load i8, i8* %ptr, !invariant.group !1
+; CHECK-NOT: load
+  %f = load i8, i8* %ptr, !invariant.group !1
+; 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 @unoptimizable2() {
+define i8 @unoptimizable2() {
+entry:
+    %ptr = alloca i8
+    store i8 42, i8* %ptr
+    call void @foo(i8* %ptr)
+    %a = load i8, i8* %ptr
+    call void @foo(i8* %ptr)
+    %b = load i8, i8* %ptr, !invariant.group !0
+    
+; CHECK: ret i8 %a
+    ret i8 %a
+}
+
+; CHECK-LABEL: define i8 @unoptimizable3() {
+define i8 @unoptimizable3() {
+entry:
+    %ptr = alloca i8
+    store i8 42, i8* %ptr, !invariant.group !0
+    %ptr2 = call i8* @getPointer(i8* %ptr)
+    %a = load i8, i8* %ptr2, !invariant.group !0
+    
+; CHECK: ret i8 %a
+    ret i8 %a
+}
+
+; CHECK-LABEL: define i8 @unoptimizable4() {
+define i8 @unoptimizable4() {
+entry:
+    %ptr = alloca i8
+    store i8 42, i8* %ptr, !invariant.group !0
+    %ptr2 = call i8* @llvm.invariant.group.barrier(i8* %ptr)
+    %a = load i8, i8* %ptr2, !invariant.group !0
+    
+; CHECK: ret i8 %a
+    ret i8 %a
+}
+
+; CHECK-LABEL: define i8 @volatile1() {
+define i8 @volatile1() {
+entry:
+    %ptr = alloca i8
+    store i8 42, i8* %ptr, !invariant.group !0
+    call void @foo(i8* %ptr)
+    %a = load i8, i8* %ptr, !invariant.group !0
+    %b = load volatile i8, i8* %ptr
+; CHECK: call void @bar(i8 %b)
+    call void @bar(i8 %b)
+
+    %c = load volatile i8, i8* %ptr, !invariant.group !0
+; FIXME: we could change %c to 42, preserving volatile load
+; CHECK: call void @bar(i8 %c)
+    call void @bar(i8 %c)
+; CHECK: ret i8 42
+    ret i8 %a
+}
+
+; CHECK-LABEL: define i8 @volatile2() {
+define i8 @volatile2() {
+entry:
+    %ptr = alloca i8
+    store i8 42, i8* %ptr, !invariant.group !0
+    call void @foo(i8* %ptr)
+    %a = load i8, i8* %ptr, !invariant.group !0
+    %b = load volatile i8, i8* %ptr
+; CHECK: call void @bar(i8 %b)
+    call void @bar(i8 %b)
+
+    %c = load volatile i8, i8* %ptr, !invariant.group !0
+; FIXME: we could change %c to 42, preserving volatile load
+; CHECK: call void @bar(i8 %c)
+    call void @bar(i8 %c)
+; CHECK: ret i8 42
+    ret i8 %a
+}
+
+
+; CHECK-LABEL: define i8 @fun() {
+define i8 @fun() {
+entry:
+    %ptr = alloca i8
+    store i8 42, i8* %ptr, !invariant.group !0
+    call void @foo(i8* %ptr)
+
+    %a = load i8, i8* %ptr, !invariant.group !0 ; Can assume that value under %ptr didn't change
+; CHECK: call void @bar(i8 42)
+    call void @bar(i8 %a)
+    
+    call void @foo(i8* %ptr)
+    %b = load i8, i8* %ptr, !invariant.group !1 ; Can't assume anything, because group changed
+; CHECK: call void @bar(i8 %b)
+    call void @bar(i8 %b)
+    
+    %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
+    store i8 %unknownValue, i8* %ptr, !invariant.group !0 
+
+    %newPtr2 = call i8* @llvm.invariant.group.barrier(i8* %ptr)
+    %d = load i8, i8* %newPtr2, !invariant.group !0  ; Can't step through invariant.group.barrier to get value of %ptr
+; CHECK: ret i8 %d
+    ret i8 %d
+}
+
+declare void @foo(i8*)
+declare void @bar(i8)
+declare i8* @getPointer(i8*)
+declare void @_ZN1A3fooEv(%struct.A*)
+declare void @_ZN1AC1Ev(%struct.A*)
+declare i8* @llvm.invariant.group.barrier(i8*)
+
+; Function Attrs: nounwind
+declare void @llvm.assume(i1 %cmp.vtables) #0
+
+
+attributes #0 = { nounwind }
+; CHECK: ![[OneMD]] = !{!"other ptr"}
+!0 = !{!"magic ptr"}
+!1 = !{!"other ptr"}
+!2 = !{!"vtable_of_a"}
 No newline at end of file