[EarlyCSE] Exploit open ended invariant.start scopes

[reames]

Summary

If we have an invariant.start with no corresponding invariant.end, then the memory location becomes invariant indefinitely after the invariant.start. As a result, anything dominated by the start is guaranteed to see the value the memory location had when the invariant.start executed.

This patch adds an AvailableInvariants table which tracks the generation a particular memory location became invariant and then uses that information to allow value forwarding that would otherwise be disallowed by potentially aliasing stores. (Reminder: In EarlyCSE everything clobbers everything by default.)

This should be compatible with the MemorySSA variant, but design is generational. We can and should add first class support for invariant.start within MemorySSA at a later time.

[anna]

Patch looks good to me. Let's wait if anyone else has any comments.

lib/Transforms/Scalar/EarlyCSE.cpp

695 ↗

(On Diff #135772)

I couldn't parse this comment.

803 ↗

(On Diff #135772)

Pls add a comment here that this handles invariant end. So, AvailableInvariants are guaranteed to be invariant indefinitely from CurrentGeneration onwards.

test/Transforms/EarlyCSE/invariant-loads.ll

99 ↗

(On Diff #135772)

why are we not able to catch this case? invariant.load is more powerful than invariant.start and we unconditionally return true for isOperatingOnInvariantMemAt

test/Transforms/EarlyCSE/invariant.start.ll

257 ↗

(On Diff #135772)

Any idea if MemorySSA will catch this case?

[reames]

lib/Transforms/Scalar/EarlyCSE.cpp

695 ↗

(On Diff #135772)

There are a family of intrinsics which were partially taught to early CSE "as if" they were real loads and stores. This code doesn't handle them yet because it was added as a layer on tp of MemLoc, not part of the MemLoc routines themselves. I have no plans to handle them.

test/Transforms/EarlyCSE/invariant-loads.ll

99 ↗

(On Diff #135772)

The way this works currently is that we're only creating invariant scopes for invariant.start calls. I agree we could (and in the near future will) create them for invariant.load, but at the moment we're not. Given that, the call advances the generation. The unconditional "yes" for invariant_loads isn't triggered since we never pass in the load. Instead, we see the store is not an invariant_load and fallback to the conservative logic.

test/Transforms/EarlyCSE/invariant.start.ll

257 ↗

(On Diff #135772)

At the moment, MemorySSA has no knowledge of invariant.start, so no. I do plan on adding support, but I'm going to start with open ended scopes.

[reames]

Clarify a couple of comments.

Note: Since this has been LGTM, I'm going to wait until next week for additional comment and then submit.

[anna]

test/Transforms/EarlyCSE/invariant-loads.ll

99 ↗

(On Diff #135772)

ah that makes sense! Thanks for the clarification.

llvm/trunk/lib/Transforms/Scalar/EarlyCSE.cpp

public:
   /// locations.  Note that atomic and/or volatile loads and stores can be
   /// present the table; it is the responsibility of the consumer to inspect
   /// the atomicity/volatility if needed.
   struct LoadValue {
     Instruction *DefInst = nullptr;
     unsigned Generation = 0;
     int MatchingId = -1;
     bool IsAtomic = false;
+
+    // TODO: Remove this flag.  It would be strictly stronger to add a record
+    // to the AvailableInvariant table when passing the invariant load instead.
     bool IsInvariant = false;
 
     LoadValue() = default;
     LoadValue(Instruction *Inst, unsigned Generation, unsigned MatchingId,
               bool IsAtomic, bool IsInvariant)
         : DefInst(Inst), Generation(Generation), MatchingId(MatchingId),
           IsAtomic(IsAtomic), IsInvariant(IsInvariant) {}
   };
 
   using LoadMapAllocator =
       RecyclingAllocator<BumpPtrAllocator,
                          ScopedHashTableVal<Value *, LoadValue>>;
   using LoadHTType =
       ScopedHashTable<Value *, LoadValue, DenseMapInfo<Value *>,
                       LoadMapAllocator>;
 
   LoadHTType AvailableLoads;
   
+  // A scoped hash table mapping memory locations (represented as typed
+  // addresses) to generation numbers at which that memory location became
+  // (henceforth indefinitely) invariant.
+  using InvariantMapAllocator =
+      RecyclingAllocator<BumpPtrAllocator,
+                         ScopedHashTableVal<MemoryLocation, unsigned>>;
+  using InvariantHTType =
+      ScopedHashTable<MemoryLocation, unsigned, DenseMapInfo<MemoryLocation>,
+                      InvariantMapAllocator>;
+  InvariantHTType AvailableInvariants;
+
   /// \brief A scoped hash table of the current values of read-only call
   /// values.
   ///
   /// It uses the same generation count as loads.
   using CallHTType =
       ScopedHashTable<CallValue, std::pair<Instruction *, unsigned>>;
   CallHTType AvailableCalls;
 

 
 private:
   // Almost a POD, but needs to call the constructors for the scoped hash
   // tables so that a new scope gets pushed on. These are RAII so that the
   // scope gets popped when the NodeScope is destroyed.
   class NodeScope {
   public:
     NodeScope(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
-              CallHTType &AvailableCalls)
-        : Scope(AvailableValues), LoadScope(AvailableLoads),
-          CallScope(AvailableCalls) {}
+              InvariantHTType &AvailableInvariants, CallHTType &AvailableCalls)
+        InvariantScope(AvailableInvariants), CallScope(AvailableCalls) {}
     NodeScope(const NodeScope &) = delete;
     NodeScope &operator=(const NodeScope &) = delete;
 
   private:
     ScopedHTType::ScopeTy Scope;
     LoadHTType::ScopeTy LoadScope;
+    InvariantHTType::ScopeTy InvariantScope;
     CallHTType::ScopeTy CallScope;
   };
 
   // Contains all the needed information to create a stack for doing a depth
   // first traversal of the tree. This includes scopes for values, loads, and
   // calls as well as the generation. There is a child iterator so that the
   // children do not need to be store separately.
   class StackNode {
   public:
     StackNode(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
-              CallHTType &AvailableCalls, unsigned cg, DomTreeNode *n,
-              DomTreeNode::iterator child, DomTreeNode::iterator end)
+              InvariantHTType &AvailableInvariants, CallHTType &AvailableCalls,
+              unsigned cg, DomTreeNode *n, DomTreeNode::iterator child,
+              DomTreeNode::iterator end)
         : CurrentGeneration(cg), ChildGeneration(cg), Node(n), ChildIter(child),
-          EndIter(end), Scopes(AvailableValues, AvailableLoads, AvailableCalls)
+          EndIter(end),
+          Scopes(AvailableValues, AvailableLoads, AvailableInvariants,
+                 AvailableCalls)
           {}
     StackNode(const StackNode &) = delete;
     StackNode &operator=(const StackNode &) = delete;
 
     // Accessors.
     unsigned currentGeneration() { return CurrentGeneration; }
     unsigned childGeneration() { return ChildGeneration; }
     void childGeneration(unsigned generation) { ChildGeneration = generation; }
if (auto *LI = dyn_cast<LoadInst>(Inst))
       return LI;
     if (auto *SI = dyn_cast<StoreInst>(Inst))
       return SI->getValueOperand();
     assert(isa<IntrinsicInst>(Inst) && "Instruction not supported");
     return TTI.getOrCreateResultFromMemIntrinsic(cast<IntrinsicInst>(Inst),
                                                  ExpectedType);
   }
 
+  /// Return true if the instruction is known to only operate on memory
+  /// provably invariant in the given "generation".
+  bool isOperatingOnInvariantMemAt(Instruction *I, unsigned GenAt);
+
   bool isSameMemGeneration(unsigned EarlierGeneration, unsigned LaterGeneration,
                            Instruction *EarlierInst, Instruction *LaterInst);
 
   void removeMSSA(Instruction *Inst) {
     if (!MSSA)
       return;
     // Removing a store here can leave MemorySSA in an unoptimized state by
     // creating MemoryPhis that have identical arguments and by creating
bool EarlyCSE::isSameMemGeneration(unsigned EarlierGeneration,
   // LaterInst, if LaterDef dominates EarlierInst then it can't occur between
   // EarlierInst and LaterInst and neither can any other write that potentially
   // clobbers LaterInst.
   MemoryAccess *LaterDef =
       MSSA->getWalker()->getClobberingMemoryAccess(LaterInst);
   return MSSA->dominates(LaterDef, EarlierMA);
 }
 
+bool EarlyCSE::isOperatingOnInvariantMemAt(Instruction *I, unsigned GenAt) {
+  // A location loaded from with an invariant_load is assumed to *never* change
+  // within the visible scope of the compilation.
+  if (auto *LI = dyn_cast<LoadInst>(I))
+    if (LI->getMetadata(LLVMContext::MD_invariant_load))
+      return true;
+
+  auto MemLocOpt = MemoryLocation::getOrNone(I);
+  if (!MemLocOpt)
+    // "target" intrinsic forms of loads aren't currently known to
+    // MemoryLocation::get.  TODO
+    return false;
+  MemoryLocation MemLoc = *MemLocOpt;
+  if (!AvailableInvariants.count(MemLoc))
+    return false;
+
+  // Is the generation at which this became invariant older than the
+  // current one?
+  return AvailableInvariants.lookup(MemLoc) <= GenAt;
+}
+
 bool EarlyCSE::processNode(DomTreeNode *Node) {
   bool Changed = false;
   BasicBlock *BB = Node->getBlock();
 
   // If this block has a single predecessor, then the predecessor is the parent
   // of the domtree node and all of the live out memory values are still current
   // in this block.  If this block has multiple predecessors, then they could
   // have invalidated the live-out memory values of our parent value.  For now,
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
     }
 
     // Skip sideeffect intrinsics, for the same reason as assume intrinsics.
     if (match(Inst, m_Intrinsic<Intrinsic::sideeffect>())) {
       DEBUG(dbgs() << "EarlyCSE skipping sideeffect: " << *Inst << '\n');
       continue;
     }
 
-    // Skip invariant.start intrinsics since they only read memory, and we can
-    // forward values across it. Also, we dont need to consume the last store
-    // since the semantics of invariant.start allow us to perform DSE of the
-    // last store, if there was a store following invariant.start. Consider:
+    // We can skip all invariant.start intrinsics since they only read memory,
+    // and we can forward values across it. For invariant starts without
+    // invariant ends, we can use the fact that the invariantness never ends to
+    // start a scope in the current generaton which is true for all future
+    // generations.  Also, we dont need to consume the last store since the
+    // semantics of invariant.start allow us to perform   DSE of the last
+    // store, if there was a store following invariant.start. Consider: 
     //
     // store 30, i8* p
     // invariant.start(p)
     // store 40, i8* p
     // We can DSE the store to 30, since the store 40 to invariant location p
     // causes undefined behaviour.
-    if (match(Inst, m_Intrinsic<Intrinsic::invariant_start>()))
+    if (match(Inst, m_Intrinsic<Intrinsic::invariant_start>())) {
+      // If there are any uses, the scope might end.  
+      if (!Inst->use_empty())
         continue;
+      auto *CI = cast<CallInst>(Inst);
+      MemoryLocation MemLoc = MemoryLocation::getForArgument(CI, 1, TLI);
+      AvailableInvariants.insert(MemLoc, CurrentGeneration);
+      continue;
+    }
 
     if (match(Inst, m_Intrinsic<Intrinsic::experimental_guard>())) {
       if (auto *CondI =
               dyn_cast<Instruction>(cast<CallInst>(Inst)->getArgOperand(0))) {
         if (SimpleValue::canHandle(CondI)) {
           // Do we already know the actual value of this condition?
           if (auto *KnownCond = AvailableValues.lookup(CondI)) {
             // Is the condition known to be true?
if (MemInst.isValid() && MemInst.isLoad()) {
       // load.
       LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
       if (InVal.DefInst != nullptr &&
           InVal.MatchingId == MemInst.getMatchingId() &&
           // We don't yet handle removing loads with ordering of any kind.
           !MemInst.isVolatile() && MemInst.isUnordered() &&
           // We can't replace an atomic load with one which isn't also atomic.
           InVal.IsAtomic >= MemInst.isAtomic() &&
-          (InVal.IsInvariant || MemInst.isInvariantLoad() ||
+          (InVal.IsInvariant ||
+           isOperatingOnInvariantMemAt(Inst, InVal.Generation) ||
            isSameMemGeneration(InVal.Generation, CurrentGeneration,
                                InVal.DefInst, Inst))) {
         Value *Op = getOrCreateResult(InVal.DefInst, Inst->getType());
         if (Op != nullptr) {
           DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << *Inst
                        << "  to: " << *InVal.DefInst << '\n');
           if (!Inst->use_empty())
             Inst->replaceAllUsesWith(Op);
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
     // the store originally was.
     if (MemInst.isValid() && MemInst.isStore()) {
       LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
       if (InVal.DefInst &&
           InVal.DefInst == getOrCreateResult(Inst, InVal.DefInst->getType()) &&
           InVal.MatchingId == MemInst.getMatchingId() &&
           // We don't yet handle removing stores with ordering of any kind.
           !MemInst.isVolatile() && MemInst.isUnordered() &&
+          (isOperatingOnInvariantMemAt(Inst, InVal.Generation) ||
            isSameMemGeneration(InVal.Generation, CurrentGeneration,
-                              InVal.DefInst, Inst)) {
+                               InVal.DefInst, Inst))) {
         // It is okay to have a LastStore to a different pointer here if MemorySSA
         // tells us that the load and store are from the same memory generation.
         // In that case, LastStore should keep its present value since we're
         // removing the current store.
         assert((!LastStore ||
                 ParseMemoryInst(LastStore, TTI).getPointerOperand() ==
                     MemInst.getPointerOperand() ||
                 MSSA) &&
bool EarlyCSE::run() {
   // discussion on this:
   // http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html
   std::deque<StackNode *> nodesToProcess;
 
   bool Changed = false;
 
   // Process the root node.
   nodesToProcess.push_back(new StackNode(
-      AvailableValues, AvailableLoads, AvailableCalls, CurrentGeneration,
-      DT.getRootNode(), DT.getRootNode()->begin(), DT.getRootNode()->end()));
+      AvailableValues, AvailableLoads, AvailableInvariants, AvailableCalls,
+      CurrentGeneration, DT.getRootNode(),
+      DT.getRootNode()->begin(), DT.getRootNode()->end()));
 
   // Save the current generation.
   unsigned LiveOutGeneration = CurrentGeneration;
 
   // Process the stack.
   while (!nodesToProcess.empty()) {
     // Grab the first item off the stack. Set the current generation, remove
     // the node from the stack, and process it.
     StackNode *NodeToProcess = nodesToProcess.back();
 
     // Initialize class members.
     CurrentGeneration = NodeToProcess->currentGeneration();
 
     // Check if the node needs to be processed.
     if (!NodeToProcess->isProcessed()) {
       // Process the node.
       Changed |= processNode(NodeToProcess->node());
       NodeToProcess->childGeneration(CurrentGeneration);
       NodeToProcess->process();
     } else if (NodeToProcess->childIter() != NodeToProcess->end()) {
       // Push the next child onto the stack.
       DomTreeNode *child = NodeToProcess->nextChild();
       nodesToProcess.push_back(
-          new StackNode(AvailableValues, AvailableLoads, AvailableCalls,
-                        NodeToProcess->childGeneration(), child, child->begin(),
-                        child->end()));
+          new StackNode(AvailableValues, AvailableLoads, AvailableInvariants,
+                        AvailableCalls, NodeToProcess->childGeneration(),
+                        child, child->begin(), child->end()));
     } else {
       // It has been processed, and there are no more children to process,
       // so delete it and pop it off the stack.
       delete NodeToProcess;
       nodesToProcess.pop_back();
     }
   } // while (!nodes...)
 

llvm/trunk/test/Transforms/EarlyCSE/invariant-loads.ll

 ; CHECK: merge:
 ; CHECK-NEXT:   %val1 = load i32, i32* %ptr
 ; CHECK-NEXT:   call void @clobber_and_use(i32 %val1)
 
   %val1 = load i32, i32* %ptr
   call void @clobber_and_use(i32 %val1)
   ret void
 }
+
+define void @test_false_negative_dse(i32* %p, i1 %cnd) {
+; CHECK-LABEL: @test_false_negative_dse
+; CHECK: store
+  %v1 = load i32, i32* %p, !invariant.load !{}
+  call void @clobber_and_use(i32 %v1)
+  store i32 %v1, i32* %p
+  ret void
+}

llvm/trunk/test/Transforms/EarlyCSE/invariant.start.ll

 ; RUN: opt < %s -S -early-cse | FileCheck %s
 ; RUN: opt < %s -S -passes=early-cse | FileCheck %s
 
 declare {}* @llvm.invariant.start.p0i8(i64, i8* nocapture) nounwind readonly
 declare void @llvm.invariant.end.p0i8({}*, i64, i8* nocapture) nounwind
 
 ; Check that we do load-load forwarding over invariant.start, since it does not
 ; clobber memory
-define i8 @test1(i8 *%P) {
-  ; CHECK-LABEL: @test1(
+define i8 @test_bypass1(i8 *%P) {
+  ; CHECK-LABEL: @test_bypass1(
   ; CHECK-NEXT: %V1 = load i8, i8* %P
   ; CHECK-NEXT: %i = call {}* @llvm.invariant.start.p0i8(i64 1, i8* %P)
   ; CHECK-NEXT: ret i8 0
 
-
   %V1 = load i8, i8* %P
   %i = call {}* @llvm.invariant.start.p0i8(i64 1, i8* %P)
   %V2 = load i8, i8* %P
   %Diff = sub i8 %V1, %V2
   ret i8 %Diff
 }
 
 
 ; Trivial Store->load forwarding over invariant.start
-define i8 @test2(i8 *%P) {
-  ; CHECK-LABEL: @test2(
+define i8 @test_bypass2(i8 *%P) {
+  ; CHECK-LABEL: @test_bypass2(
   ; CHECK-NEXT: store i8 42, i8* %P
   ; CHECK-NEXT: %i = call {}* @llvm.invariant.start.p0i8(i64 1, i8* %P)
   ; CHECK-NEXT: ret i8 42
 
-
   store i8 42, i8* %P
   %i = call {}* @llvm.invariant.start.p0i8(i64 1, i8* %P)
   %V1 = load i8, i8* %P
   ret i8 %V1
 }
 
 ; We can DSE over invariant.start calls, since the first store to
 ; %P is valid, and the second store is actually unreachable based on semantics
 ; of invariant.start.
-define void @test3(i8* %P) {
-
-; CHECK-LABEL: @test3(
+define void @test_bypass3(i8* %P) {
+; CHECK-LABEL: @test_bypass3(
 ; CHECK-NEXT:  %i = call {}* @llvm.invariant.start.p0i8(i64 1, i8* %P)
 ; CHECK-NEXT:  store i8 60, i8* %P
 
-
   store i8 50, i8* %P
   %i = call {}* @llvm.invariant.start.p0i8(i64 1, i8* %P)
   store i8 60, i8* %P
   ret void
 }
 
 
 ; FIXME: Now the first store can actually be eliminated, since there is no read within
 ; the invariant region, between start and end.
-define void @test4(i8* %P) {
+define void @test_bypass4(i8* %P) {
 
-; CHECK-LABEL: @test4(
+; CHECK-LABEL: @test_bypass4(
 ; CHECK-NEXT: store i8 50, i8* %P
 ; CHECK-NEXT:  %i = call {}* @llvm.invariant.start.p0i8(i64 1, i8* %P)
 ; CHECK-NEXT: call void @llvm.invariant.end.p0i8({}* %i, i64 1, i8* %P)
 ; CHECK-NEXT:  store i8 60, i8* %P
 
 
   store i8 50, i8* %P
   %i = call {}* @llvm.invariant.start.p0i8(i64 1, i8* %P)
   call void @llvm.invariant.end.p0i8({}* %i, i64 1, i8* %P)
   store i8 60, i8* %P
   ret void
 }
+
+
+declare void @clobber()
+declare {}* @llvm.invariant.start.p0i32(i64 %size, i32* nocapture %ptr)
+declare void @llvm.invariant.end.p0i32({}*, i64, i32* nocapture) nounwind
+
+define i32 @test_before_load(i32* %p) {
+; CHECK-LABEL: @test_before_load
+; CHECK: ret i32 0
+  call {}* @llvm.invariant.start.p0i32(i64 4, i32* %p)
+  %v1 = load i32, i32* %p
+  call void @clobber()
+  %v2 = load i32, i32* %p
+  %sub = sub i32 %v1, %v2
+  ret i32 %sub
+}
+
+define i32 @test_before_clobber(i32* %p) {
+; CHECK-LABEL: @test_before_clobber
+; CHECK: ret i32 0
+  %v1 = load i32, i32* %p
+  call {}* @llvm.invariant.start.p0i32(i64 4, i32* %p)
+  call void @clobber()
+  %v2 = load i32, i32* %p
+  %sub = sub i32 %v1, %v2
+  ret i32 %sub
+}
+
+define i32 @test_unanalzyable_load(i32* %p) {
+; CHECK-LABEL: @test_unanalzyable_load
+; CHECK: ret i32 0
+  call {}* @llvm.invariant.start.p0i32(i64 4, i32* %p)
+  call void @clobber()
+  %v1 = load i32, i32* %p
+  call void @clobber()
+  %v2 = load i32, i32* %p
+  %sub = sub i32 %v1, %v2
+  ret i32 %sub
+}
+
+define i32 @test_negative_after_clobber(i32* %p) {
+; CHECK-LABEL: @test_negative_after_clobber
+; CHECK: ret i32 %sub
+  %v1 = load i32, i32* %p
+  call void @clobber()
+  call {}* @llvm.invariant.start.p0i32(i64 4, i32* %p)
+  %v2 = load i32, i32* %p
+  %sub = sub i32 %v1, %v2
+  ret i32 %sub
+}
+
+define i32 @test_merge(i32* %p, i1 %cnd) {
+; CHECK-LABEL: @test_merge
+; CHECK: ret i32 0
+  %v1 = load i32, i32* %p
+  call {}* @llvm.invariant.start.p0i32(i64 4, i32* %p)
+  br i1 %cnd, label %merge, label %taken
+
+taken:
+  call void @clobber()
+  br label %merge
+merge:
+  %v2 = load i32, i32* %p
+  %sub = sub i32 %v1, %v2
+  ret i32 %sub
+}
+
+define i32 @test_negative_after_mergeclobber(i32* %p, i1 %cnd) {
+; CHECK-LABEL: @test_negative_after_mergeclobber
+; CHECK: ret i32 %sub
+  %v1 = load i32, i32* %p
+  br i1 %cnd, label %merge, label %taken
+
+taken:
+  call void @clobber()
+  br label %merge
+merge:
+  call {}* @llvm.invariant.start.p0i32(i64 4, i32* %p)
+  %v2 = load i32, i32* %p
+  %sub = sub i32 %v1, %v2
+  ret i32 %sub
+}
+
+; In theory, this version could work, but earlycse is incapable of
+; merging facts along distinct paths.  
+define i32 @test_false_negative_merge(i32* %p, i1 %cnd) {
+; CHECK-LABEL: @test_false_negative_merge
+; CHECK: ret i32 %sub
+  %v1 = load i32, i32* %p
+  br i1 %cnd, label %merge, label %taken
+
+taken:
+  call {}* @llvm.invariant.start.p0i32(i64 4, i32* %p)
+  call void @clobber()
+  br label %merge
+merge:
+  %v2 = load i32, i32* %p
+  %sub = sub i32 %v1, %v2
+  ret i32 %sub
+}
+
+define i32 @test_merge_unanalyzable_load(i32* %p, i1 %cnd) {
+; CHECK-LABEL: @test_merge_unanalyzable_load
+; CHECK: ret i32 0
+  call {}* @llvm.invariant.start.p0i32(i64 4, i32* %p)
+  call void @clobber()
+  %v1 = load i32, i32* %p
+  br i1 %cnd, label %merge, label %taken
+
+taken:
+  call void @clobber()
+  br label %merge
+merge:
+  %v2 = load i32, i32* %p
+  %sub = sub i32 %v1, %v2
+  ret i32 %sub
+}
+
+define void @test_dse_before_load(i32* %p, i1 %cnd) {
+; CHECK-LABEL: @test_dse_before_load
+; CHECK-NOT: store
+  call {}* @llvm.invariant.start.p0i32(i64 4, i32* %p)
+  %v1 = load i32, i32* %p
+  call void @clobber()
+  store i32 %v1, i32* %p
+  ret void
+}
+
+define void @test_dse_after_load(i32* %p, i1 %cnd) {
+; CHECK-LABEL: @test_dse_after_load
+; CHECK-NOT: store
+  %v1 = load i32, i32* %p
+  call {}* @llvm.invariant.start.p0i32(i64 4, i32* %p)
+  call void @clobber()
+  store i32 %v1, i32* %p
+  ret void
+}
+
+
+; In this case, we have a false negative since MemoryLocation is implicitly
+; typed due to the user of a Value to represent the address.  Note that other
+; passes will canonicalize away the bitcasts in this example.
+define i32 @test_false_negative_types(i32* %p) {
+; CHECK-LABEL: @test_false_negative_types
+; CHECK: ret i32 %sub
+  call {}* @llvm.invariant.start.p0i32(i64 4, i32* %p)
+  %v1 = load i32, i32* %p
+  call void @clobber()
+  %pf = bitcast i32* %p to float*
+  %v2f = load float, float* %pf
+  %v2 = bitcast float %v2f to i32
+  %sub = sub i32 %v1, %v2
+  ret i32 %sub
+}
+
+define i32 @test_negative_size1(i32* %p) {
+; CHECK-LABEL: @test_negative_size1
+; CHECK: ret i32 %sub
+  call {}* @llvm.invariant.start.p0i32(i64 3, i32* %p)
+  %v1 = load i32, i32* %p
+  call void @clobber()
+  %v2 = load i32, i32* %p
+  %sub = sub i32 %v1, %v2
+  ret i32 %sub
+}
+
+define i32 @test_negative_size2(i32* %p) {
+; CHECK-LABEL: @test_negative_size2
+; CHECK: ret i32 %sub
+  call {}* @llvm.invariant.start.p0i32(i64 0, i32* %p)
+  %v1 = load i32, i32* %p
+  call void @clobber()
+  %v2 = load i32, i32* %p
+  %sub = sub i32 %v1, %v2
+  ret i32 %sub
+}
+
+define i32 @test_negative_scope(i32* %p) {
+; CHECK-LABEL: @test_negative_scope
+; CHECK: ret i32 %sub
+  %scope = call {}* @llvm.invariant.start.p0i32(i64 4, i32* %p)
+  call void @llvm.invariant.end.p0i32({}* %scope, i64 4, i32* %p)
+  %v1 = load i32, i32* %p
+  call void @clobber()
+  %v2 = load i32, i32* %p
+  %sub = sub i32 %v1, %v2
+  ret i32 %sub
+}
+
+define i32 @test_false_negative_scope(i32* %p) {
+; CHECK-LABEL: @test_false_negative_scope
+; CHECK: ret i32 %sub
+  %scope = call {}* @llvm.invariant.start.p0i32(i64 4, i32* %p)
+  %v1 = load i32, i32* %p
+  call void @clobber()
+  %v2 = load i32, i32* %p
+  call void @llvm.invariant.end.p0i32({}* %scope, i64 4, i32* %p)
+  %sub = sub i32 %v1, %v2
+  ret i32 %sub
+}
+
+; Invariant load defact starts an invariant.start scope of the appropriate size
+define i32 @test_invariant_load_scope(i32* %p) {
+; CHECK-LABEL: @test_invariant_load_scope
+; CHECK: ret i32 0
+  %v1 = load i32, i32* %p, !invariant.load !{}
+  call void @clobber()
+  %v2 = load i32, i32* %p
+  %sub = sub i32 %v1, %v2
+  ret i32 %sub
+}