[Introduction] Redundant load reduction with invariant intrinsics

[lvoufo]

Summary

Based on the design doc at
https://docs.google.com/document/d/112O-Q_XrbrU1I4P-oiLCN9u86Qg_BYBdcDsmh7Pn9Nw/edit?usp=sharing,
it handles non-member C++ const objects.
Extensions are discussed in the design doc and will be submitted separately.

[lvoufo]

Clang-formet'ed.

[reames]

This definitely needs to be split up into a series of smaller patches to
be reviewable. I strongly suggest starting small, getting through one
cycle of review, then posting a couple more and recursing. Reading
through the diff, I see a lot of points which will need
discussion/clarification.

Also, a bit of background on what you're trying to accomplish is
required. A link to a private google doc is not sufficient.

Philip

[nlewycky]

include/llvm/IR/GlobalVariable.h

32–34

Alphabetize.

48

This is a change to the concept of what a global variable in LLVM IR is, and therefore would require a matching LangRef change (and bitcode reader/writer change).

If you need to store information about a GV for a pass, please create a map<GlobalVariable*, IntrinsicInst*> in your pass.

include/llvm/IR/Instructions.h

36–38

Alphabetize.

79

Again, this is a fundamental change to what an alloca instruction is.

Question for you, what if there's more than one invariant call on this alloca?

Note that this doesn't form a use, so what if someone deletes the invariant intrinsic? This is left hanging and pointing to nothing, or worse someone could reallocate a new different instruction at the same address.

lib/Analysis/BasicAliasAnalysis.cpp

499

What if the GV has an invariant start instruction, but the query is from before the GV initializer has finished running? A "false negative" in this if-expression fails unsafe, skipping this block will cause us to go into code which is written to assume GV->isConstant is true. If that were sufficient, then there's no need to have getInvariantStartInstruction at all, you could just set isConstant instead.

You need to check that the invariant has already executed, and the way to do that is to see that it dominates (which currently we can only do in a function-local sense). I don't know what cases you're solving this way, but my stab-in-the-dark guess is that you should probably be getting them with changes to MemoryDependenceAnalysis instead; if you see an invariant.end you can skip the scan of instructions up to the matching invariant.start which it conveniently takes as its first argument. That way, you never even get into the point of querying basicaa about the instructions in between, therefore they don't appear to be potentially conflicting for any user of memdep (GVN, DSE, Memcpyopt).

lib/IR/Instructions.cpp

1155–1158

What about II->getParent() == this->getParent()?

lib/Transforms/IPO/GlobalOpt.cpp

2246–2249

I don't think you need this?

GlobalOpt performs symbolic execution of each instruction in order. It will see, and "execute" an invariant start instruction by inserting it into the "Invariants" set above. This is a more accurate model, since before the execution occurs it is not yet constant, and it becomes constant afterwards.

I'm not sure what cases processInvariantIntrinsics is catching which the existing code is not, and I'd like to review the GlobalOpt changes independently.

2640–2641

This is what the Evaluator does (except not just for invariant intrinsics). This code is a second evaluator inside the evaluator, please don't do that, just integrate with the rest of GlobalOpt.

2646–2648

for (Function::iterator BB = F->begin(), BE = F->end(); BB != BE; ++BB) {
  // Function::iterator implicitly converts into a BasicBlock*, so "BB->..." works fine
}

2648

"BasicBlock* NextBB" --> "BasicBlock *NextBB".

2683

So the only things Eval.getVal() will return non-null for are Arguments and GlobalValues, because you've entered processInvariantIntrinsics() before evaluating the function. Good news, that's not wrong, it just doesn't have the values.

The alternative of running it afterwards would fill in the values, but be actively wrong in a case where you're inside a loop; a loop value incrementing %x from 0 to 5 would show as '5' even if it were used inside the loop.

lib/Transforms/InstCombine/InstructionCombining.cpp

1966

I don't think that's right. Proposed counterexample:

declare {}* @llvm.invariant.start(i64 %size, i8* nocapture %ptr)
declare void @llvm.invariant.end({}* %start, i64 %size, i8* nocapture %ptr)
declare i8* @malloc(i32)
define void @foo() {
  %p = call i8* @malloc(i32 1)
  %inv = call {}* @llvm.invariant.start(i64 -1, i8* %p)
  %dead = icmp eq i8* %p, i8* null
  call void @llvm.invariant.end({}* %inv, i64 -1, i8* %p)
  ret void
}

If "isAllocSiteRemovable" is true, we should just delete invariant starts and ends. There may be a pile of them, like:

%inv1 = call {}* @llvm.invariant.start(i64 -1, i8* %p)
call void @llvm.invariant.end({}* %inv1, i64 -1, i8* %p)
%inv2 = call {}* @llvm.invariant.start(i64 -1, i8* %p)
call void @llvm.invariant.end({}* %inv2, i64 -1, i8* %p)
%inv3 = call {}* @llvm.invariant.start(i64 -1, i8* %p)
call void @llvm.invariant.end({}* %inv3, i64 -1, i8* %p)

and we don't care since we already checked that it's safe to delete them all. Just nuke away!

Also, don't dyn_cast + assert the result, just use cast<>. It has the assert inside.

[lvoufo]

In D13606#263966, @reames wrote:

This definitely needs to be split up into a series of smaller patches to
be reviewable. I strongly suggest starting small, getting through one
cycle of review, then posting a couple more and recursing. Reading
through the diff, I see a lot of points which will need
discussion/clarification.

Also, a bit of background on what you're trying to accomplish is
required. A link to a private google doc is not sufficient.

Philip

Hi Philip -- This *is* the initial patch. I can't think of another way to break it down more effectively.
Thanks for pointing out the inaccessibility of the design doc.
It is not meant to be private. If one is unable to access, I believe s/he should be able to request access, which I will promptly grant (?).
Alternatively, I have made a copy available from my personal (and more public-capable) email account.
Please let me know if you encounter any more issue.

[lvoufo]

include/llvm/IR/GlobalVariable.h

48

I have been troubleshooting how to do this better. Will see what I can come up with... Thanks for the pointer.

include/llvm/IR/Instructions.h

79

Same as above.

lib/IR/Instructions.cpp

1155–1158

Good point. Thanks!

lib/Transforms/IPO/GlobalOpt.cpp

2246–2249

True. I was using it as a temporary informational tool.

[lvoufo]

lib/IR/Instructions.cpp

4030–4035

TODO: Revise this description and simplify the function signature.

lib/Transforms/IPO/Inliner.cpp

481–483

TODO: Remove this change.

[reames]

In D13606#264048, @lvoufo wrote:

In D13606#263966, @reames wrote:

This definitely needs to be split up into a series of smaller patches to
be reviewable. I strongly suggest starting small, getting through one
cycle of review, then posting a couple more and recursing. Reading
through the diff, I see a lot of points which will need
discussion/clarification.

Also, a bit of background on what you're trying to accomplish is
required. A link to a private google doc is not sufficient.

Philip

Hi Philip -- This *is* the initial patch. I can't think of another way to break it down more effectively.

Er, no. This patch currently involves changes to 5 different transform passes and 3 analysis passes. This can and must be split into smaller changes. I'd suggest striping out everything not required for *one* of the transform passes and iterate on that.

Thanks for pointing out the inaccessibility of the design doc.
It is not meant to be private. If one is unable to access, I believe s/he should be able to request access, which I will promptly grant (?).
Alternatively, I have made a copy available from my personal (and more public-capable) email account.
Please let me know if you encounter any more issue.

Thank you for sharing the doc publicly. It did help to explain the problem you're trying to solve, but it didn't really give me any insight into how your trying to solve it. Can you sketch out an architectural level summary of how you intent this to work?

[• dberlin]

I'm with Philip on this one.
This patch looks like it can be split up.
As a rule, you don't have to make everything go at once, you can do it
piece by piece.

(IE it's fine to modify one transform/analysis pass, even if nothing
but tests use it yet, and then add the use in a separate patch).

More to the point, the feedback you are getting says: "If you want
this reviewed by reviewers, you should split it up more".
So unless you can point to concrete reasons it can't be split up, you
should do that.

[lvoufo]

In D13606#267985, @dberlin wrote:

I'm with Philip on this one.
This patch looks like it can be split up.
As a rule, you don't have to make everything go at once, you can do it
piece by piece.

(IE it's fine to modify one transform/analysis pass, even if nothing
but tests use it yet, and then add the use in a separate patch).

More to the point, the feedback you are getting says: "If you want
this reviewed by reviewers, you should split it up more".
So unless you can point to concrete reasons it can't be split up, you
should do that.

Okay. Thanks for the clarifications. I'll see what I can do.

[lvoufo]

lib/Transforms/InstCombine/InstructionCombining.cpp

1966

I'm confused by this comment. What is wrong about this? Note that I here represents one of the users collected by "isAllocSiteRemovable" and which are being iterated through...

[nlewycky]

lib/Transforms/InstCombine/InstructionCombining.cpp

1966

You're right that my examples don't work because I misunderstood what 'I' is. However, I think I can still break this assert:

%inv1 = call {}* @llvm.invariant.start(i64 -1, i8* %p)
br i1 undef, label %cond_true, label %cond_false

cond_true:

call void @llvm.invarient.end({}* %inv1, i64 -1, i8* %p)
unreachable

cond_false;

call void @llvm.invarient.end({}* %inv1, i64 -1, i8* %p)
unreachable

In this case 'I' is %inv1 (one of the users of %p) and it's safe to remove according to isAllocSiteRemovable, yet it has neither zero nor one uses.

[lvoufo]

lib/Transforms/InstCombine/InstructionCombining.cpp

1966

Ah. Now I understand this one. Thanks!

[lvoufo]

lib/Transforms/IPO/GlobalOpt.cpp

2640–2641

The real reason why this version of processInvariantIntrinsics() is necessary is that EvaluateBlock() could exit before processing the invariant intrinsic call (and marking global variables 'writeonce'), e.g., if a call to a function declaration that we cannot constant fold occurs before the intrinsic call.

This processInvariantIntrinsics() complements Evaluator::EvaluateBlock() by pre-traversing the call-stack tree on the same Evaluator instance. The alternative would be to delay exits from Evaluator::EvaluateBlock() while remembering whether to exit with 'false' or 'true'; which would be a messier extension than separating the functions.

I'm rewriting this function with respect to other comments below anyway...

[lvoufo]

I think I've addressed all the comment by now. I'll be pushing in split-up patches (with corrections) next.

lib/Analysis/BasicAliasAnalysis.cpp

499

GVs, like AIs, are marked "writeonce written" (via 'setInvariantStartInstruction') immediately after initialization.
This test parallels a similar test above on AIs. That is, it should only succeed for non-"writeonce written" and non-constants.
Skipping instructions in MemoryDependenceAnalysis does not quite work in more general cases, such as where either the instantiated object itself is not const, but has const fields.
IIRC, I also ran into situations where GEPs where not eliminated as they should with their subesequent eliminated loads...
For the cases where this does work, I would rather leave it in a separate "improvement" patch.

[lvoufo]

I have addressed all the feedback so far (Thanks, Nick!) and split the updated version of this patch into 6-7 patches: D14003 (D14008 + D14009), D14004, D14005, D14006 and D14007.
Is this clearer? Would it help to split it up further?

Thanks,
--L.

[lvoufo]

lib/IR/Instructions.cpp

1155–1158

Actually, I'm not sure that this works. For example, take an alloca outside of a branch that contains an invariant_start...

[nlewycky]

lib/IR/Instructions.cpp

1155–1158

Sorry, you're right. To check that they're the same function, it's "II->getParent()->getParent() == getParent()->getParent()".

[asb]

lib/IR/Instructions.cpp

1155–1158

Actually rL254975 added Instruction::getFunction

[lvoufo]

lib/IR/Instructions.cpp

1155–1158

Thanks.

include/llvm/IR/GlobalVariable.h

 #include "llvm/ADT/ilist_node.h"
 #include "llvm/IR/GlobalObject.h"
 #include "llvm/IR/OperandTraits.h"
 
 namespace llvm {
 
 class Module;
 class Constant;
 template <typename ValueSubClass> class SymbolTableListTraits;
+class IntrinsicInst;
 
 class GlobalVariable : public GlobalObject, public ilist_node<GlobalVariable> {
   friend class SymbolTableListTraits<GlobalVariable>;
   void *operator new(size_t, unsigned) = delete;
   void operator=(const GlobalVariable &) = delete;
   GlobalVariable(const GlobalVariable &) = delete;
 
   void setParent(Module *parent);
 
   bool isConstantGlobal : 1;                   // Is this a global constant?
   bool isExternallyInitializedConstant : 1;    // Is this a global whose value
                                                // can change from its initial
                                                // value before global
                                                // initializers are run?
+  IntrinsicInst *InvariantStartInst;           // Transient
+
+  void checkInvariantStartInstruction(IntrinsicInst *II);
+
 public:
   // allocate space for exactly one operand
   void *operator new(size_t s) {
     return User::operator new(s, 1);
   }
 
   /// GlobalVariable ctor - If a parent module is specified, the global is
   /// automatically inserted into the end of the specified modules global list.
public:
 
   /// If the value is a global constant, its value is immutable throughout the
   /// runtime execution of the program.  Assigning a value into the constant
   /// leads to undefined behavior.
   ///
   bool isConstant() const { return isConstantGlobal; }
   void setConstant(bool Val) { isConstantGlobal = Val; }
 
+  IntrinsicInst *getInvariantStartInstruction() const {
+    return InvariantStartInst;
+  }
+  void setInvariantStartInstruction(IntrinsicInst *II) {
+    checkInvariantStartInstruction(II);
+    InvariantStartInst = II;
+  }
+
   bool isExternallyInitialized() const {
     return isExternallyInitializedConstant;
   }
   void setExternallyInitialized(bool Val) {
     isExternallyInitializedConstant = Val;
   }
 
   /// copyAttributesFrom - copy all additional attributes (those not needed to

include/llvm/IR/Instructions.h

 #include <iterator>
 
 namespace llvm {
 
 class APInt;
 class ConstantInt;
 class ConstantRange;
 class DataLayout;
 class LLVMContext;
+class IntrinsicInst;
 
 enum AtomicOrdering {
   NotAtomic = 0,
   Unordered = 1,
   Monotonic = 2,
   // Consume = 3,  // Not specified yet.
   Acquire = 4,
   Release = 5,
   AcquireRelease = 6,

 //===----------------------------------------------------------------------===//
 //                                AllocaInst Class
 //===----------------------------------------------------------------------===//
 
 /// AllocaInst - an instruction to allocate memory on the stack
 ///
 class AllocaInst : public UnaryInstruction {
   Type *AllocatedType;
+  IntrinsicInst *InvariantStartInst;  // Transient.
+
+  void checkInvariantStartInstruction(IntrinsicInst *II);
 
 protected:
   // Note: Instruction needs to be a friend here to call cloneImpl.
   friend class Instruction;
   AllocaInst *cloneImpl() const;
 
 public:
   explicit AllocaInst(Type *Ty, Value *ArraySize = nullptr,
public:
   /// getAlignment - Return the alignment of the memory that is being allocated
   /// by the instruction.
   ///
   unsigned getAlignment() const {
     return (1u << (getSubclassDataFromInstruction() & 31)) >> 1;
   }
   void setAlignment(unsigned Align);
 
+  IntrinsicInst *getInvariantStartInstruction() const {
+    return InvariantStartInst;
+  }
+  void setInvariantStartInstruction(IntrinsicInst *II) {
+    checkInvariantStartInstruction(II);
+    InvariantStartInst = II;
+  }
+
   /// isStaticAlloca - Return true if this alloca is in the entry block of the
   /// function and is a constant size.  If so, the code generator will fold it
   /// into the prolog/epilog code, so it is basically free.
   bool isStaticAlloca() const;
 
   /// \brief Return true if this alloca is used as an inalloca argument to a
   /// call.  Such allocas are never considered static even if they are in the
   /// entry block.
public:
   static inline bool classof(const Instruction *I) {
     return I->getOpcode() == AddrSpaceCast;
   }
   static inline bool classof(const Value *V) {
     return isa<Instruction>(V) && classof(cast<Instruction>(V));
   }
 };
 
+//===----------------------------------------------------------------------===//
+//                Processing invariant_start/end intrinsics
+//===----------------------------------------------------------------------===//
+
+IntrinsicInst *getInvariantStartInstruction(const Value *Arg);
+void setInvariantStartInstruction(Value *Arg, IntrinsicInst *Val);
+bool processInvariantIntrinsics(IntrinsicInst *II);
+void cleanupProcessedInvariantIntrinsics(Instruction *I);
+
+struct PreservedInvariantInfo {
+  IntrinsicInst *II;
+  Value *LoadedAddr;
+  PreservedInvariantInfo() : II(nullptr), LoadedAddr(nullptr) {}
+};
+
+class PreserveInvariantInfo {
+  PreservedInvariantInfo Preserved;
+  void CheckPreservedInfo();
+
+ public:
+  PreserveInvariantInfo(PreservedInvariantInfo Info) : Preserved(Info) {
+    if (Preserved.II) CheckPreservedInfo();
+  }
+  ~PreserveInvariantInfo() {
+    if (Preserved.II)
+      setInvariantStartInstruction(Preserved.LoadedAddr, Preserved.II);
+  }
+};
+
+void setPreservedInvariantInfo(PreservedInvariantInfo &Preserved,
+                               BasicBlock::iterator &ScanBackwardFrom,
+                               Value *Query, Value *QueryObj, BasicBlock *BB);
+
 } // End llvm namespace
 
 #endif

lib/Analysis/BasicAliasAnalysis.cpp

if (!Visited.insert(V).second) {
       Visited.clear();
       return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
     }
 
     // An alloca instruction defines local memory.
     if (OrLocal && isa<AllocaInst>(V))
       continue;
 
+    if (const AllocaInst *AI = dyn_cast<AllocaInst>(V))
+      if (AI->getInvariantStartInstruction()) continue;
+
     // A global constant counts as local memory for our purposes.
     if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
       // Note: this doesn't require GV to be "ODR" because it isn't legal for a
       // global to be marked constant in some modules and non-constant in
       // others.  GV may even be a declaration, not a definition.
-      if (!GV->isConstant()) {
+      if (!GV->isConstant() && !GV->getInvariantStartInstruction()) {
         Visited.clear();
         return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
       }
       continue;
     }
 
     // If both select values point to local memory, then so does the select.
     if (const SelectInst *SI = dyn_cast<SelectInst>(V)) {
AliasResult BasicAAResult::alias(const MemoryLocation &LocA,
   // shrink_and_clear so it quickly returns to the inline capacity of the
   // SmallDenseMap if it ever grows larger.
   // FIXME: This should really be shrink_to_inline_capacity_and_clear().
   AliasCache.shrink_and_clear();
   VisitedPhiBBs.clear();
   return Alias;
 }
 
+static bool isInvariantIntrinsic(ImmutableCallSite CS) {
+  const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction());
+  return II && (II->getIntrinsicID() == Intrinsic::invariant_start ||
+                II->getIntrinsicID() == Intrinsic::invariant_end);
+}
+
 /// Checks to see if the specified callsite can clobber the specified memory
 /// object.
 ///
 /// Since we only look at local properties of this function, we really can't
 /// say much about this query.  We do, however, use simple "address taken"
 /// analysis on local objects.
 ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS,
                                         const MemoryLocation &Loc) {
ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS,
   }
 
   // While the assume intrinsic is marked as arbitrarily writing so that
   // proper control dependencies will be maintained, it never aliases any
   // particular memory location.
   if (isAssumeIntrinsic(CS))
     return MRI_NoModRef;
 
+  // *.invariant.* intrinsics follow the same pattern as assume intrinsic.
+  if (isInvariantIntrinsic(CS)) return MRI_NoModRef;
+
   // The AAResultBase base class has some smarts, lets use them.
   return AAResultBase::getModRefInfo(CS, Loc);
 }
 
 ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS1,
                                         ImmutableCallSite CS2) {
   // While the assume intrinsic is marked as arbitrarily writing so that
   // proper control dependencies will be maintained, it never aliases any
   // particular memory location.
   if (isAssumeIntrinsic(CS1) || isAssumeIntrinsic(CS2))
     return MRI_NoModRef;
 
+  // *.invariant.* intrinsics follow the same pattern as assume intrinsic.
+  if (isInvariantIntrinsic(CS1) || isInvariantIntrinsic(CS2))
+    return MRI_NoModRef;
+
   // The AAResultBase base class has some smarts, lets use them.
   return AAResultBase::getModRefInfo(CS1, CS2);
 }
 
 /// Provide ad-hoc rules to disambiguate accesses through two GEP operators,
 /// both having the exact same pointer operand.
 static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
                                             uint64_t V1Size,

lib/Analysis/Loads.cpp

 }
 
 /// DefMaxInstsToScan - the default number of maximum instructions
 /// to scan in the block, used by FindAvailableLoadedValue().
 /// FindAvailableLoadedValue() was introduced in r60148, to improve jump
 /// threading in part by eliminating partially redundant loads.
 /// At that point, the value of MaxInstsToScan was already set to '6'
 /// without documented explanation.
-cl::opt<unsigned>
-llvm::DefMaxInstsToScan("available-load-scan-limit", cl::init(6), cl::Hidden,
+/// We have bumped up this number to '8' to improve the chnages of
+/// behaviorial match when -instcombine is run after or without -inline.
+cl::opt<unsigned> llvm::DefMaxInstsToScan(
+    "available-load-scan-limit", cl::init(8), cl::Hidden,
     cl::desc("Use this to specify the default maximum number of instructions "
              "to scan backward from a given instruction, when searching for "
              "available loaded value"));
 
 /// \brief Scan the ScanBB block backwards to see if we have the value at the
 /// memory address *Ptr locally available within a small number of instructions.
 ///
 /// The scan starts from \c ScanFrom. \c MaxInstsToScan specifies the maximum
 /// instructions to scan in the block. If it is set to \c 0, it will scan the whole
 /// block.
 ///
Value *llvm::FindAvailableLoadedValue(Value *Ptr, BasicBlock *ScanBB,
 
   const DataLayout &DL = ScanBB->getModule()->getDataLayout();
 
   // Try to get the store size for the type.
   uint64_t AccessSize = DL.getTypeStoreSize(AccessTy);
 
   Value *StrippedPtr = Ptr->stripPointerCasts();
 
+  // We're about to scan backwards. Preserve the initial invariant_start
+  // intrinsic marking on this load, for subsequent instructions.
+  // First, compute the info to preserve (and do not skip any instruction).
+  // Then, actually preserve the info before backward scanning starts.
+  PreservedInvariantInfo Preserved;
+  Value *LIAddr = nullptr;
+  if (LoadInst *LI = dyn_cast<LoadInst>(StrippedPtr))
+    LIAddr = GetUnderlyingObject(LI->getPointerOperand(), DL);
+  setPreservedInvariantInfo(Preserved, ScanFrom, StrippedPtr, LIAddr, ScanBB);
+  PreserveInvariantInfo PIO(Preserved);
+
   while (ScanFrom != ScanBB->begin()) {
     // We must ignore debug info directives when counting (otherwise they
     // would affect codegen).
     Instruction *Inst = --ScanFrom;
     if (isa<DbgInfoIntrinsic>(Inst))
       continue;
 
+    // Same for invariant intrinsics.
+    if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
+      if (II->getIntrinsicID() == Intrinsic::invariant_start) {
+        if (II == Preserved.II)
+          // We did not skip any instruction earlier. So, we must express that
+          // the given load is no longer pointing to constant memory.
+          llvm::setInvariantStartInstruction(Preserved.LoadedAddr, nullptr);
+        continue;
+      } else if (II->getIntrinsicID() == Intrinsic::invariant_end)
+        continue;
+    }
+
     // Restore ScanFrom to expected value in case next test succeeds
     ScanFrom++;
 
     // Don't scan huge blocks.
     if (MaxInstsToScan-- == 0)
       return nullptr;
 
     --ScanFrom;

lib/Analysis/MemoryDependenceAnalysis.cpp

MemDepResult MemoryDependenceAnalysis::getSimplePointerDependencyFrom(
   if (isLoad && QueryInst) {
     LoadInst *LI = dyn_cast<LoadInst>(QueryInst);
     if (LI && LI->getMetadata(LLVMContext::MD_invariant_load) != nullptr)
       isInvariantLoad = true;
   }
 
   const DataLayout &DL = BB->getModule()->getDataLayout();
 
+  // We're about to scan backwards. Preserve the initial invariant_start
+  // intrinsic marking on this load, for subsequent instructions.
+  // First, compute the info to preserve and prepare to skip instructions
+  // that need no further processing.
+  // Then, actually preserve the info before backward scanning starts.
+  PreservedInvariantInfo Preserved;
+  if (isLoad && QueryInst) {
+    Value *LIAddr = nullptr;
+    if (LoadInst *LI = dyn_cast<LoadInst>(QueryInst))
+      LIAddr = GetUnderlyingObject(LI->getPointerOperand(), DL);
+    setPreservedInvariantInfo(Preserved, ScanIt, QueryInst, LIAddr, BB);
+  }
+  PreserveInvariantInfo PIO(Preserved);
+
   // Create a numbered basic block to lazily compute and cache instruction
   // positions inside a BB. This is used to provide fast queries for relative
   // position between two instructions in a BB and can be used by
   // AliasAnalysis::callCapturesBefore.
   OrderedBasicBlock OBB(BB);
 
   // Walk backwards through the basic block, looking for dependencies.
   while (ScanIt != BB->begin()) {
     Instruction *Inst = --ScanIt;
 
     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
       // Debug intrinsics don't (and can't) cause dependencies.
       if (isa<DbgInfoIntrinsic>(II)) continue;
 
+    // Same for invariant intrinsics.
+    if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
+      if (II->getIntrinsicID() == Intrinsic::invariant_start) {
+        if (II == Preserved.II)
+          // We did not skip any instruction earlier. So, we must express that
+          // the given load is no longer pointing to constant memory.
+          llvm::setInvariantStartInstruction(Preserved.LoadedAddr, nullptr);
+        continue;
+      } else if (II->getIntrinsicID() == Intrinsic::invariant_end)
+        continue;
+    }
+
     // Limit the amount of scanning we do so we don't end up with quadratic
     // running time on extreme testcases.
     --Limit;
     if (!Limit)
       return MemDepResult::getUnknown();
 
     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
       // If we reach a lifetime begin or end marker, then the query ends here

lib/IR/Globals.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/GlobalAlias.h"
 #include "llvm/IR/GlobalVariable.h"
+#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/Support/ErrorHandling.h"
 using namespace llvm;
 
 //===----------------------------------------------------------------------===//
 //                            GlobalValue Class
 //===----------------------------------------------------------------------===//
bool GlobalValue::isDeclaration() const {
   assert(isa<GlobalAlias>(this));
   return false;
 }
 
 //===----------------------------------------------------------------------===//
 // GlobalVariable Implementation
 //===----------------------------------------------------------------------===//
 
+void GlobalVariable::checkInvariantStartInstruction(IntrinsicInst *II) {
+  assert((!II || II->getIntrinsicID() == Intrinsic::invariant_start) &&
+         "Given intrinsic instruction is not invariant_start");
+}
+
 GlobalVariable::GlobalVariable(Type *Ty, bool constant, LinkageTypes Link,
                                Constant *InitVal, const Twine &Name,
                                ThreadLocalMode TLMode, unsigned AddressSpace,
                                bool isExternallyInitialized)
     : GlobalObject(Ty, Value::GlobalVariableVal,
                    OperandTraits<GlobalVariable>::op_begin(this),
                    InitVal != nullptr, Link, Name, AddressSpace),
       isConstantGlobal(constant),
-      isExternallyInitializedConstant(isExternallyInitialized) {
+      isExternallyInitializedConstant(isExternallyInitialized),
+      InvariantStartInst(nullptr) {
   setThreadLocalMode(TLMode);
   if (InitVal) {
     assert(InitVal->getType() == Ty &&
            "Initializer should be the same type as the GlobalVariable!");
     Op<0>() = InitVal;
   }
 }
 
 GlobalVariable::GlobalVariable(Module &M, Type *Ty, bool constant,
                                LinkageTypes Link, Constant *InitVal,
                                const Twine &Name, GlobalVariable *Before,
                                ThreadLocalMode TLMode, unsigned AddressSpace,
                                bool isExternallyInitialized)
     : GlobalObject(Ty, Value::GlobalVariableVal,
                    OperandTraits<GlobalVariable>::op_begin(this),
                    InitVal != nullptr, Link, Name, AddressSpace),
       isConstantGlobal(constant),
-      isExternallyInitializedConstant(isExternallyInitialized) {
+      isExternallyInitializedConstant(isExternallyInitialized),
+      InvariantStartInst(nullptr) {
   setThreadLocalMode(TLMode);
   if (InitVal) {
     assert(InitVal->getType() == Ty &&
            "Initializer should be the same type as the GlobalVariable!");
     Op<0>() = InitVal;
   }
 
   if (Before)

lib/IR/Instructions.cpp

 //===-- Instructions.cpp - Implement the LLVM instructions ----------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements all of the non-inline methods for the LLVM instruction
 // classes.
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Instructions.h"
 #include "LLVMContextImpl.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
+#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/MathExtras.h"
 using namespace llvm;
 
 //===----------------------------------------------------------------------===//
 //                            CallSite Class
void BranchInst::setSuccessorV(unsigned idx, BasicBlock *B) {
   setSuccessor(idx, B);
 }
 
 
 //===----------------------------------------------------------------------===//
 //                        AllocaInst Implementation
 //===----------------------------------------------------------------------===//
 
+void AllocaInst::checkInvariantStartInstruction(IntrinsicInst *II) {
+  assert((!II || II->getIntrinsicID() == Intrinsic::invariant_start) &&
+         "Given intrinsic instruction is not invariant_start");
+}
+
 static Value *getAISize(LLVMContext &Context, Value *Amt) {
   if (!Amt)
     Amt = ConstantInt::get(Type::getInt32Ty(Context), 1);
   else {
     assert(!isa<BasicBlock>(Amt) &&
            "Passed basic block into allocation size parameter! Use other ctor");
     assert(Amt->getType()->isIntegerTy() &&
            "Allocation array size is not an integer!");

 AllocaInst::AllocaInst(Type *Ty, Value *ArraySize, const Twine &Name,
                        BasicBlock *InsertAtEnd)
     : AllocaInst(Ty, ArraySize, /*Align=*/0, Name, InsertAtEnd) {}
 
 AllocaInst::AllocaInst(Type *Ty, Value *ArraySize, unsigned Align,
                        const Twine &Name, Instruction *InsertBefore)
     : UnaryInstruction(PointerType::getUnqual(Ty), Alloca,
                        getAISize(Ty->getContext(), ArraySize), InsertBefore),
-      AllocatedType(Ty) {
+      AllocatedType(Ty),
+      InvariantStartInst(nullptr) {
   setAlignment(Align);
   assert(!Ty->isVoidTy() && "Cannot allocate void!");
   setName(Name);
 }
 
 AllocaInst::AllocaInst(Type *Ty, Value *ArraySize, unsigned Align,
                        const Twine &Name, BasicBlock *InsertAtEnd)
     : UnaryInstruction(PointerType::getUnqual(Ty), Alloca,
                        getAISize(Ty->getContext(), ArraySize), InsertAtEnd),
-      AllocatedType(Ty) {
+      AllocatedType(Ty),
+      InvariantStartInst(nullptr) {
   setAlignment(Align);
   assert(!Ty->isVoidTy() && "Cannot allocate void!");
   setName(Name);
 }
 
 // Out of line virtual method, so the vtable, etc has a home.
 AllocaInst::~AllocaInst() {
 }

 CleanupPadInst *CleanupPadInst::cloneImpl() const {
   return new (getNumOperands()) CleanupPadInst(*this);
 }
 
 UnreachableInst *UnreachableInst::cloneImpl() const {
   LLVMContext &Context = getContext();
   return new UnreachableInst(Context);
 }
+
+//===----------------------------------------------------------------------===//
+//                Processing invariant_start/end intrinsics
+//===----------------------------------------------------------------------===//
+
+void llvm::PreserveInvariantInfo::CheckPreservedInfo() {
+  assert(Preserved.II->getIntrinsicID() == Intrinsic::invariant_start &&
+         "Preserved instruction must be an invariant_start intrinsic");
+  assert(Preserved.LoadedAddr &&
+         "Can't preserve an intrinsic instruction for no load.");
+}
+
+/// If the given Query is a load from writeonce readonly memory, we can speed
+/// backward scaning by jumping to the associated invariant_start instruction,
+/// *if* the instruction is in the BB block.
+/// Then, since we would be scanning backward, undo the invariant_start
+/// intrinsic marking so that getModRefInfo() knows that the load does not
+/// point to constant memory from this point on.
+void llvm::setPreservedInvariantInfo(PreservedInvariantInfo &Preserved,
+                                     BasicBlock::iterator &ScanBackwardFrom,
+                                     Value *Query, Value *QueryObj,
+                                     BasicBlock *BB) {
+  assert(Query && "Query must exist.");
+  if (dyn_cast<LoadInst>(Query)) {
+    if (IntrinsicInst *II = llvm::getInvariantStartInstruction(QueryObj)) {
+      Preserved.II = II;
+      Preserved.LoadedAddr = QueryObj;
+    }
+  }
+}
+
+IntrinsicInst *llvm::getInvariantStartInstruction(const Value *Arg) {
+  if (!Arg) return nullptr;
+  if (const AllocaInst *AI = dyn_cast<AllocaInst>(Arg))
+    return AI->getInvariantStartInstruction();
+  if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(Arg))
+    if (!GV->isConstant()) return GV->getInvariantStartInstruction();
+  return nullptr;
+}
+
+void llvm::setInvariantStartInstruction(Value *Arg, IntrinsicInst *Val) {
+  if (!Arg) return;
+  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Arg))
+    GV->setInvariantStartInstruction(Val);
+  if (AllocaInst *AI = dyn_cast<AllocaInst>(Arg))
+    AI->setInvariantStartInstruction(Val);
+}
+
+/// \brief Process @llvm.invariant.start/end intrinsics:
+/// Mark addresses as "within a an invariant range specified by
+/// the given intrinsic call.
+bool llvm::processInvariantIntrinsics(IntrinsicInst *II) {
+  assert(II && "Can't mark a null instruction.");
+
+  if (II->getIntrinsicID() == Intrinsic::invariant_start) {
+    llvm::Value *Addr = II->getArgOperand(1)->stripPointerCasts();
+    setInvariantStartInstruction(Addr, II);
+    return true;
+  } else if (II->getIntrinsicID() == Intrinsic::invariant_end) {
+    llvm::Value *Addr = II->getArgOperand(2)->stripPointerCasts();
+    if (getInvariantStartInstruction(Addr))
+      setInvariantStartInstruction(Addr, nullptr);
+    return true;
+  }
+  return false;
+}
+
+/// \brief Cleanup after processing @llvm.invariant.start/end intrinsics:
+/// To be called when an instruction is erased from a function, e.g.,
+/// with EraseInstFromFunction(); Reset the addresses markings from
+/// processInvariantIntrinsics().
+/// NOTE: We need an efficient management of invariant info that can be
+///       reused through multiple passes such as -globalopt.
+///       This gives us that and avoids potential dangling pointers from
+///       erasing intrinsic instructions.
+void llvm::cleanupProcessedInvariantIntrinsics(Instruction *I) {
+  assert(I && "Can't cleanup a null instruction.");
+
+  // Only handle invariant intrinsics here.
+  IntrinsicInst *II = dyn_cast<IntrinsicInst>(I);
+  if (!II) return;
+
+  llvm::Value *Addr = nullptr;
+  if (II->getIntrinsicID() == Intrinsic::invariant_start)
+    Addr = II->getArgOperand(1)->stripPointerCasts();
+  else if (II->getIntrinsicID() == Intrinsic::invariant_end)
+    Addr = II->getArgOperand(2)->stripPointerCasts();
+  else
+    return;
+
+  setInvariantStartInstruction(Addr, nullptr);
+}

lib/Transforms/IPO/GlobalOpt.cpp

public:
   bool EvaluateFunction(Function *F, Constant *&RetVal,
                         const SmallVectorImpl<Constant*> &ActualArgs);
 
   /// EvaluateBlock - Evaluate all instructions in block BB, returning true if
   /// successful, false if we can't evaluate it.  NewBB returns the next BB that
   /// control flows into, or null upon return.
   bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB);
 
-  Constant *getVal(Value *V) {
+  Constant *getVal(Value *V, bool CheckComputed = true) {
     if (Constant *CV = dyn_cast<Constant>(V)) return CV;
     Constant *R = ValueStack.back().lookup(V);
-    assert(R && "Reference to an uncomputed value!");
+
+    // Allow references to uncomputed values from processInvariantIntrinsics().
+    if (CheckComputed) assert(R && "Reference to an uncomputed value!");
     return R;
   }
 
   void setVal(Value *V, Constant *C) {
     ValueStack.back()[V] = C;
   }
 
   const DenseMap<Constant*, Constant*> &getMutatedMemory() const {
     return MutatedMemory;
   }
 
   const SmallPtrSetImpl<GlobalVariable*> &getInvariants() const {
     return Invariants;
   }
 
+  const SmallPtrSetImpl<GlobalVariable *> &getReadOnlys() const {
+    return ReadOnlys;
+  }
+
 private:
   Constant *ComputeLoadResult(Constant *P);
 
   /// ValueStack - As we compute SSA register values, we store their contents
   /// here. The back of the deque contains the current function and the stack
   /// contains the values in the calling frames.
   std::deque<DenseMap<Value*, Constant*>> ValueStack;
 
private:
   /// to represent its body.  This vector is needed so we can delete the
   /// temporary globals when we are done.
   SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps;
 
   /// Invariants - These global variables have been marked invariant by the
   /// static constructor.
   SmallPtrSet<GlobalVariable*, 8> Invariants;
 
+  /// ReadOnlys - These global variables are writeonce variables that
+  /// have been marked readonly by the static constructor.
+  SmallPtrSet<GlobalVariable *, 8> ReadOnlys;
+
   /// SimpleConstants - These are constants we have checked and know to be
   /// simple enough to live in a static initializer of a global.
   SmallPtrSet<Constant*, 8> SimpleConstants;
 
   const DataLayout &DL;
   const TargetLibraryInfo *TLI;
 };
 
if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
           Value *PtrArg = getVal(II->getArgOperand(1));
           Value *Ptr = PtrArg->stripPointerCasts();
           if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
             Type *ElemTy = cast<PointerType>(GV->getType())->getElementType();
             if (!Size->isAllOnesValue() &&
                 Size->getValue().getLimitedValue() >=
                     DL.getTypeStoreSize(ElemTy)) {
               Invariants.insert(GV);
-              DEBUG(dbgs() << "Found a global var that is an invariant: " << *GV
-                    << "\n");
+              DEBUG(dbgs()
+                    << "Found a global var that is an invariant (constant): "
+                    << *GV << "\n");
+            } else if (GV->getInvariantStartInstruction()) {
+              ReadOnlys.insert(GV);
+              DEBUG(
+                  dbgs() << "Found a global var that is a readonly writeonce: "
+                         << *GV << "\n");
             } else {
               DEBUG(dbgs() << "Found a global var, but can not treat it as an "
                     "invariant.\n");
             }
           }
           // Continue even if we do nothing.
           ++CurInst;
           continue;
if (InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) {
       return true;
     }
 
     // Advance program counter.
     ++CurInst;
   }
 }
 
+static void processInvariantIntrinsics(Evaluator &Eval, Function *F) {
+  // Scan the block to process invariant intrinsics, tracing whatever
+  // call chain that can be traced.
+  // Without this, invariant intrinsics on global variables, can only be
+  // processed when the constructor calls are inlined.
+  // TODO: Instead of forcing this tracing, can we rely on -O1's -always-inline
+  // or -O2's -inline?
+  BasicBlock *BB = F->begin();
+  while (BB) {
+    BasicBlock *NextBB = nullptr;
+    BasicBlock::iterator CurInst = BB->begin();
+
+    while (CurInst) {
+      if (isa<CallInst>(CurInst) || isa<InvokeInst>(CurInst)) {
+        CallSite CS(CurInst);
+
+        if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CurInst))
+          processInvariantIntrinsics(II);
+
+        // Debug info, inline asm, intrinsics, ...
+        // can safely be ignored here.
+        if (isa<DbgInfoIntrinsic>(CS.getInstruction()) ||
+            isa<InlineAsm>(CS.getCalledValue()) ||
+            dyn_cast<IntrinsicInst>(CS.getInstruction())) {
+          ++CurInst;
+          continue;
+        }
+        Function *Callee =
+            dyn_cast_or_null<Function>(Eval.getVal(CS.getCalledValue(),
+                                                   /*CheckComputed =*/false));
+        if (!Callee || Callee->mayBeOverridden()) break;
+
+        if (!Callee->isDeclaration() &&
+            !Callee->getFunctionType()->isVarArg()) {
+          processInvariantIntrinsics(Eval, Callee);
+        }
+      } else if (isa<TerminatorInst>(CurInst)) {
+        if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) {
+          if (BI->isUnconditional())
+            NextBB = BI->getSuccessor(0);
+          else {
+            if (ConstantInt *Cond = dyn_cast_or_null<ConstantInt>(
+                    Eval.getVal(BI->getCondition(),
+                                /*CheckComputed =*/false)))
+              NextBB = BI->getSuccessor(!Cond->getZExtValue());
+          }
+        } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) {
+          if (ConstantInt *Val = dyn_cast_or_null<ConstantInt>(
+                  Eval.getVal(SI->getCondition(), /*CheckComputed =*/false)))
+            NextBB = SI->findCaseValue(Val).getCaseSuccessor();
+        } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) {
+          Value *Val = Eval.getVal(IBI->getAddress(),
+                                   /*CheckComputed =*/false)
+                           ->stripPointerCasts();
+          if (BlockAddress *BA = dyn_cast_or_null<BlockAddress>(Val))
+            NextBB = BA->getBasicBlock();
+          NextBB = nullptr;
+        } else if (isa<ReturnInst>(CurInst))
+          NextBB = nullptr;
+        break;
+      }
+
+      if (InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) {
+        NextBB = II->getNormalDest();
+        break;
+      }
+
+      ++CurInst;
+    }
+
+    BB = NextBB;
+  }
+}
+
 /// EvaluateFunction - Evaluate a call to function F, returning true if
 /// successful, false if we can't evaluate it.  ActualArgs contains the formal
 /// arguments for the function.
 bool Evaluator::EvaluateFunction(Function *F, Constant *&RetVal,
                                  const SmallVectorImpl<Constant*> &ActualArgs) {
   // Check to see if this function is already executing (recursion).  If so,
   // bail out.  TODO: we might want to accept limited recursion.
   if (std::find(CallStack.begin(), CallStack.end(), F) != CallStack.end())
bool Evaluator::EvaluateFunction(Function *F, Constant *&RetVal,
   // track of what we have executed so we can detect recursive cases etc.
   SmallPtrSet<BasicBlock*, 32> ExecutedBlocks;
 
   // CurBB - The current basic block we're evaluating.
   BasicBlock *CurBB = F->begin();
 
   BasicBlock::iterator CurInst = CurBB->begin();
 
+  // Scan the block to process invariant intrinsics.
+  // This will mark 'writeonce' global variables as written.
+  processInvariantIntrinsics(*this, F);
+
   while (1) {
     BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings.
     DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n");
 
     if (!EvaluateBlock(CurInst, NextBB))
       return false;
 
     if (!NextBB) {
DEBUG(dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '"
           << F->getName() << "' to " << Eval.getMutatedMemory().size()
           << " stores.\n");
     for (DenseMap<Constant*, Constant*>::const_iterator I =
            Eval.getMutatedMemory().begin(), E = Eval.getMutatedMemory().end();
          I != E; ++I)
       CommitValueTo(I->second, I->first);
     for (GlobalVariable *GV : Eval.getInvariants())
       GV->setConstant(true);
+
+    for (GlobalVariable *GV : Eval.getReadOnlys()) {
+      assert(GV->getInvariantStartInstruction() &&
+             "Only readonly writeonce global vars are allowed here.");
+    }
   }
 
   return EvalSuccess;
 }
 
 static int compareNames(Constant *const *A, Constant *const *B) {
   return (*A)->stripPointerCasts()->getName().compare(
       (*B)->stripPointerCasts()->getName());

lib/Transforms/IPO/Inliner.cpp

bool Inliner::runOnSCC(CallGraphSCC &SCC) {
   for (CallGraphNode *Node : SCC) {
     Function *F = Node->getFunction();
     if (!F) continue;
     
     for (BasicBlock &BB : *F)
       for (Instruction &I : BB) {
         CallSite CS(cast<Value>(&I));
         // If this isn't a call, or it is a call to an intrinsic, it can
-        // never be inlined.
-        if (!CS || isa<IntrinsicInst>(I))
-          continue;
-        
+        // never be inlined. invariant_start/end intrinsics are excepted
+        // because they should be processed when inlining other calls.
+        if (!CS || isa<IntrinsicInst>(I)) continue;
         // If this is a direct call to an external function, we can never inline
         // it.  If it is an indirect call, inlining may resolve it to be a
         // direct call, so we keep it.
         if (Function *Callee = CS.getCalledFunction())
           if (Callee->isDeclaration())
             continue;
         
         CallSites.push_back(std::make_pair(CS, -1));
bool Inliner::runOnSCC(CallGraphSCC &SCC) {
   bool LocalChange;
   do {
     LocalChange = false;
     // Iterate over the outer loop because inlining functions can cause indirect
     // calls to become direct calls.
     // CallSites may be modified inside so ranged for loop can not be used.
     for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) {
       CallSite CS = CallSites[CSi].first;
-      
       Function *Caller = CS.getCaller();
       Function *Callee = CS.getCalledFunction();
 
       // If this call site is dead and it is to a readonly function, we should
       // just delete the call instead of trying to inline it, regardless of
       // size.  This happens because IPSCCP propagates the result out of the
       // call and then we're left with the dead call.
       if (isInstructionTriviallyDead(CS.getInstruction(), &TLI)) {

lib/Transforms/InstCombine/InstCombineCalls.cpp

case Intrinsic::assume: {
     // then this one is redundant, and should be removed.
     APInt KnownZero(1, 0), KnownOne(1, 0);
     computeKnownBits(IIOperand, KnownZero, KnownOne, 0, II);
     if (KnownOne.isAllOnesValue())
       return EraseInstFromFunction(*II);
 
     break;
   }
+  case Intrinsic::invariant_start:
+  case Intrinsic::invariant_end:
+    processInvariantIntrinsics(II);
+    break;
   case Intrinsic::experimental_gc_relocate: {
     // Translate facts known about a pointer before relocating into
     // facts about the relocate value, while being careful to
     // preserve relocation semantics.
     GCRelocateOperands Operands(II);
     Value *DerivedPtr = Operands.getDerivedPtr();
     auto *GCRelocateType = cast<PointerType>(II->getType());
 

lib/Transforms/InstCombine/InstCombineInternal.h

Instruction *EraseInstFromFunction(Instruction &I) {
     // Make sure that we reprocess all operands now that we reduced their
     // use counts.
     if (I.getNumOperands() < 8) {
       for (User::op_iterator i = I.op_begin(), e = I.op_end(); i != e; ++i)
         if (Instruction *Op = dyn_cast<Instruction>(*i))
           Worklist.Add(Op);
     }
     Worklist.Remove(&I);
+    cleanupProcessedInvariantIntrinsics(&I);
     I.eraseFromParent();
     MadeIRChange = true;
     return nullptr; // Don't do anything with FI
   }
 
   void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
                         unsigned Depth, Instruction *CxtI) const {
     return llvm::computeKnownBits(V, KnownZero, KnownOne, DL, Depth, AC, CxtI,

lib/Transforms/InstCombine/InstructionCombining.cpp

for (unsigned i = 0, e = Users.size(); i != e; ++i) {
       } else if (isa<BitCastInst>(I) || isa<GetElementPtrInst>(I)) {
         ReplaceInstUsesWith(*I, UndefValue::get(I->getType()));
       } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
         if (II->getIntrinsicID() == Intrinsic::objectsize) {
           ConstantInt *CI = cast<ConstantInt>(II->getArgOperand(1));
           uint64_t DontKnow = CI->isZero() ? -1ULL : 0;
           ReplaceInstUsesWith(*I, ConstantInt::get(I->getType(), DontKnow));
         }
+
+        // If this is a paired invariant_start, then erase its invariant_end.
+        if (II->getIntrinsicID() == Intrinsic::invariant_start &&
+            !I->use_empty()) {
+          IntrinsicInst *User =
+              dyn_cast<IntrinsicInst>(cast<Instruction>(*I->user_begin()));
+          assert(I->hasOneUse() && User &&
+                 User->getIntrinsicID() == Intrinsic::invariant_end &&
+                 "The paired instruction should be an invariant_end.");
+          EraseInstFromFunction(*User);
+        }
       }
       EraseInstFromFunction(*I);
     }
 
     if (InvokeInst *II = dyn_cast<InvokeInst>(&MI)) {
       // Replace invoke with a NOP intrinsic to maintain the original CFG
       Module *M = II->getParent()->getParent()->getParent();
       Function *F = Intrinsic::getDeclaration(M, Intrinsic::donothing);

lib/Transforms/Scalar/GVN.cpp

 
 /// When calculating availability, handle an instruction
 /// by inserting it into the appropriate sets
 bool GVN::processInstruction(Instruction *I) {
   // Ignore dbg info intrinsics.
   if (isa<DbgInfoIntrinsic>(I))
     return false;
 
+  if (IntrinsicInst *IntrinsicI = dyn_cast<IntrinsicInst>(I)) {
+    if (processInvariantIntrinsics(IntrinsicI)) return false;
+  }
+
   // If the instruction can be easily simplified then do so now in preference
   // to value numbering it.  Value numbering often exposes redundancies, for
   // example if it determines that %y is equal to %x then the instruction
   // "%z = and i32 %x, %y" becomes "%z = and i32 %x, %x" which we now simplify.
   const DataLayout &DL = I->getModule()->getDataLayout();
   if (Value *V = SimplifyInstruction(I, DL, TLI, DT, AC)) {
     I->replaceAllUsesWith(V);
     if (MD && V->getType()->getScalarType()->isPointerTy())

test/Transforms/LoadElim/global-local-vars.ll

+
+;; NOTE: The CHECKLOAD-* prefixes indicate occurences of redundant loads in the output.
+;;       The CHECK-* prefixes indicate removal of redundant loads in the output. (ALL == 4-5A1-5A2-5B)
+
+;; * When the available load scan limit is 6, -instcombine does not 
+;;   eliminate some redundant loads that either it would eliminate
+;;   with a load scan limit of 8, or -gvn would eliminate.
+; RUN: opt < %s -globalopt -available-load-scan-limit=6 -instcombine -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-5B --check-prefix=CHECKLOAD-4-5A
+; RUN: opt < %s -globalopt -available-load-scan-limit=6 -instcombine -gvn -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-ALL
+; RUN: opt < %s -globalopt -available-load-scan-limit=8 -instcombine -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-5A2-5B --check-prefix=CHECKLOAD-4-5A1
+; RUN: opt < %s -globalopt -available-load-scan-limit=8 -instcombine -gvn -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-ALL
+
+;; * Adding '-inline -early-cse' enables a few more load eliminations,
+;;   but does not merge the same loads into the store as per local vars.
+; RUN: opt < %s -globalopt -available-load-scan-limit=6 -instcombine -inline -early-cse -instcombine -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECKINL --check-prefix=CHECK-5A2-5B --check-prefix=CHECKLOAD-4-5A1
+; RUN: opt < %s -globalopt -available-load-scan-limit=6 -instcombine -inline -early-cse -gvn -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECKINL --check-prefix=CHECK-ALL
+; RUN: opt < %s -globalopt -available-load-scan-limit=8 -instcombine -inline -early-cse -instcombine -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECKINL --check-prefix=CHECK-5A2-5B --check-prefix=CHECKLOAD-4-5A1
+; RUN: opt < %s -globalopt -available-load-scan-limit=8 -instcombine -inline -early-cse -gvn -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECKINL --check-prefix=CHECK-ALL
+
+;; * When the load scan limit is 8,
+;;   '-functionattrs -tailcallelim -instcombine' may be as good as '-gvn'.
+;;   But the same can't be said when the limit is 6.
+; RUN: opt < %s -globalopt -available-load-scan-limit=8 -instcombine -functionattrs -tailcallelim -instcombine -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-ALL
+; RUN: opt < %s -globalopt -available-load-scan-limit=6 -instcombine -functionattrs -tailcallelim -instcombine -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-4-5A-5B1 --check-prefix=CHECKLOAD-5B2
+
+%struct.A = type { i32 }
+
+@_ZL1i = internal global %struct.A zeroinitializer
[e-mail]_ctors = appending global [1 x { i32, void ()*, i8* }] [{ i32, void ()*, i8* } { i32 65535, void ()* @_GLOBAL__sub_I_global_local, i8* null }]
+
+;; Example 2: Unnecessary stores and loads.
+;; void ex2() {
+;;   const Type i(one());
+;;   const Type j = i;  // Note: i == j, &i != &j  ==> No store.
+;;   bar(i);            // First load.
+;;   foo(&i);           // Does not change i, nor j.
+;;   bar(j);            // No load; Reuse i location.
+;; }
+define void @_Z3ex2v() {
+; CHECK: @_Z3ex2v(
+entry:
+  %j = alloca %struct.A
+  %agg.tmp = alloca %struct.A
+  %agg.tmp1 = alloca %struct.A
+  %0 = bitcast %struct.A* %j to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %0)
+  %1 = bitcast %struct.A* %j to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %1, i8* bitcast (%struct.A* @_ZL1i to i8*), i64 4, i32 4, i1 false)
+  %2 = bitcast %struct.A* %j to i8*
+  %3 = call {}* @llvm.invariant.start(i64 4, i8* %2)
+  ; CHECK-NOT: call {{.*}}@llvm.invariant.start(i64 {{[0-9]+}}, i8*
+  %4 = bitcast %struct.A* %agg.tmp to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %4, i8* bitcast (%struct.A* @_ZL1i to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive = getelementptr inbounds %struct.A, %struct.A* %agg.tmp, i32 0, i32 0
+  %5 = load i32, i32* %coerce.dive
+  ; CHECK: load i32, i32*
+  call void @_Z3bar1A(i32 %5)
+  call void @_Z3fooPK1A(%struct.A* @_ZL1i)
+  %6 = bitcast %struct.A* %agg.tmp1 to i8*
+  %7 = bitcast %struct.A* %j to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %6, i8* %7, i64 4, i32 4, i1 false)
+  %coerce.dive2 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp1, i32 0, i32 0
+  %8 = load i32, i32* %coerce.dive2
+  ; CHECK-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %8)
+  call void @llvm.invariant.end({}* %3, i64 4, i8* %2)
+  ; CHECK-NOT: call {{.*}}@llvm.invariant.end({{.*}}, i64 {{[0-9]+}}, i8*
+  %9 = bitcast %struct.A* %j to i8*
+  call void @llvm.lifetime.end(i64 4, i8* %9)
+  ret void
+}
+
+;; Example 3: Necessary stores and loads.
+;; void ex3() {
+;;   const Type i(1);
+;;   Type k = i;        // Note: i == k, &i != &k  ==> Keep store.
+;;   bar(i);            // First load.
+;;   foo(&k);           // Does not change i; May change k.
+;;   bar(k);            // Keep load.
+;; }
+define void @_Z3ex3v() {
+; CHECK: @_Z3ex3v(
+entry:
+  %k = alloca %struct.A
+  %agg.tmp = alloca %struct.A
+  %agg.tmp1 = alloca %struct.A
+  %0 = bitcast %struct.A* %k to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %0)
+  %1 = bitcast %struct.A* %k to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %1, i8* bitcast (%struct.A* @_ZL1i to i8*), i64 4, i32 4, i1 false)
+  %2 = bitcast %struct.A* %agg.tmp to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %2, i8* bitcast (%struct.A* @_ZL1i to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive = getelementptr inbounds %struct.A, %struct.A* %agg.tmp, i32 0, i32 0
+  %3 = load i32, i32* %coerce.dive
+  ; CHECK: load i32, i32*
+  call void @_Z3bar1A(i32 %3)
+  call void @_Z3fooPK1A(%struct.A* %k)
+  %4 = bitcast %struct.A* %agg.tmp1 to i8*
+  %5 = bitcast %struct.A* %k to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %4, i8* %5, i64 4, i32 4, i1 false)
+  %coerce.dive2 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp1, i32 0, i32 0
+  %6 = load i32, i32* %coerce.dive2
+  ; CHECK: load i32, i32*
+  call void @_Z3bar1A(i32 %6)
+  %7 = bitcast %struct.A* %k to i8*
+  call void @llvm.lifetime.end(i64 4, i8* %7)
+  ret void
+}
+
+;; Example 4: Smart stores and loads.
+;; void ex4() {
+;;   const Type i(one());
+;;   Type k = i;        // Note: i == k, &i != &k  ==> May keep store.
+;;   bar(i);            // First load.
+;;   foo(&i);           // Does not change i, nor k.
+;;   bar(k);            // No load; Reuse i location.
+;;   foo(&k);           // Does not change i; May change k.
+;;   bar(k);            // Keep load.
+;; }
+define void @_Z3ex4v() {
+; CHECK: @_Z3ex4v(
+entry:
+  %k = alloca %struct.A
+  %agg.tmp = alloca %struct.A
+  %agg.tmp1 = alloca %struct.A
+  %agg.tmp3 = alloca %struct.A
+  %0 = bitcast %struct.A* %k to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %0)
+  %1 = bitcast %struct.A* %k to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %1, i8* bitcast (%struct.A* @_ZL1i to i8*), i64 4, i32 4, i1 false)
+  %2 = bitcast %struct.A* %agg.tmp to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %2, i8* bitcast (%struct.A* @_ZL1i to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive = getelementptr inbounds %struct.A, %struct.A* %agg.tmp, i32 0, i32 0
+  %3 = load i32, i32* %coerce.dive
+  ; CHECK: load i32, i32*
+  call void @_Z3bar1A(i32 %3)
+  call void @_Z3fooPK1A(%struct.A* @_ZL1i)
+  %4 = bitcast %struct.A* %agg.tmp1 to i8*
+  %5 = bitcast %struct.A* %k to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %4, i8* %5, i64 4, i32 4, i1 false)
+  %coerce.dive2 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp1, i32 0, i32 0
+  %6 = load i32, i32* %coerce.dive2
+  ; CHECKLOAD-4-5A1: load i32, i32*
+  ; CHECKLOAD-4-5A: load i32, i32*
+  ; CHECK-4-5A1-5B-NOT: load i32, i32*
+  ; CHECK-4-5A-5B1-NOT: load i32, i32*
+  ; CHECK-ALL-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %6)
+  call void @_Z3fooPK1A(%struct.A* %k)
+  %7 = bitcast %struct.A* %agg.tmp3 to i8*
+  %8 = bitcast %struct.A* %k to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %7, i8* %8, i64 4, i32 4, i1 false)
+  %coerce.dive4 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp3, i32 0, i32 0
+  %9 = load i32, i32* %coerce.dive4
+  ; CHECK: load i32, i32*
+  call void @_Z3bar1A(i32 %9)
+  %10 = bitcast %struct.A* %k to i8*
+  call void @llvm.lifetime.end(i64 4, i8* %10)
+  ret void
+}
+
+;; Example 5: Duplicate and smart loads (and stores).
+;; void ex5a() {
+;;   const Type i(one());
+;;   Type k = i;        // Note: i == k, &i != &k  ==> May keep store.
+;;   bar(i);            // First load.
+;;   bar(k);            // No load; Reuse i location.
+;;   foo2(&k, &i);      // Does not change i; May change k.
+;;   bar(i);            // No load.
+;;   bar(k);            // Keep load.
+;; }
+define void @_Z4ex5av() {
+; CHECK: @_Z4ex5av(
+entry:
+  %k = alloca %struct.A
+  %agg.tmp = alloca %struct.A
+  %agg.tmp1 = alloca %struct.A
+  %agg.tmp3 = alloca %struct.A
+  %agg.tmp5 = alloca %struct.A
+  %0 = bitcast %struct.A* %k to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %0)
+  %1 = bitcast %struct.A* %k to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %1, i8* bitcast (%struct.A* @_ZL1i to i8*), i64 4, i32 4, i1 false)
+  %2 = bitcast %struct.A* %agg.tmp to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %2, i8* bitcast (%struct.A* @_ZL1i to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive = getelementptr inbounds %struct.A, %struct.A* %agg.tmp, i32 0, i32 0
+  %3 = load i32, i32* %coerce.dive
+  ; CHECK: load i32, i32*
+  call void @_Z3bar1A(i32 %3)
+  %4 = bitcast %struct.A* %agg.tmp1 to i8*
+  %5 = bitcast %struct.A* %k to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %4, i8* %5, i64 4, i32 4, i1 false)
+  %coerce.dive2 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp1, i32 0, i32 0
+  %6 = load i32, i32* %coerce.dive2
+  ; CHECKLOAD-4-5A1: load i32, i32*
+  ; CHECKLOAD-4-5A: load i32, i32*
+  ; CHECK-4-5A-5B1-NOT: load i32, i32*
+  ; CHECK-ALL-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %6)
+  call void @_Z4foo2PK1AS1_(%struct.A* %k, %struct.A* @_ZL1i)
+  %7 = bitcast %struct.A* %agg.tmp3 to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %7, i8* bitcast (%struct.A* @_ZL1i to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive4 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp3, i32 0, i32 0
+  %8 = load i32, i32* %coerce.dive4
+  ; CHECKLOAD-4-5A: load i32, i32*
+  ; CHECK-4-5A-5B1-NOT: load i32, i32*
+  ; CHECK-5A2-5B-NOT: load i32, i32*
+  ; CHECK-ALL-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %8)
+  %9 = bitcast %struct.A* %agg.tmp5 to i8*
+  %10 = bitcast %struct.A* %k to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %9, i8* %10, i64 4, i32 4, i1 false)
+  %coerce.dive6 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp5, i32 0, i32 0
+  %11 = load i32, i32* %coerce.dive6
+  ; CHECK: load i32, i32*
+  call void @_Z3bar1A(i32 %11)
+  %12 = bitcast %struct.A* %k to i8*
+  call void @llvm.lifetime.end(i64 4, i8* %12)
+  ret void
+}
+
+;; Example 5: Duplicate and smart loads (and stores).
+;; void ex5b() {
+;;   const Type i(one());
+;;   const Type j = i;  // Note: i == j, &i != &j  ==> No store.
+;;   bar(i);            // First load.
+;;   bar(j);            // No load; Reuse i location.
+;;   foo2(&j, &i);      // Does not change i, nor j.
+;;   bar(i);            // No load.
+;;   bar(j);            // No load; Reuse i location.
+;; }
+define void @_Z4ex5bv() {
+; CHECK: @_Z4ex5bv(
+entry:
+  %j = alloca %struct.A
+  %agg.tmp = alloca %struct.A
+  %agg.tmp1 = alloca %struct.A
+  %agg.tmp3 = alloca %struct.A
+  %agg.tmp5 = alloca %struct.A
+  %0 = bitcast %struct.A* %j to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %0)
+  %1 = bitcast %struct.A* %j to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %1, i8* bitcast (%struct.A* @_ZL1i to i8*), i64 4, i32 4, i1 false)
+  %2 = bitcast %struct.A* %j to i8*
+  ; CHECK-4-5A1-5B: load i32, i32*
+  ; CHECK-5A2-5B: load i32, i32*
+  ; CHECK-ALL: load i32, i32*
+  %3 = call {}* @llvm.invariant.start(i64 4, i8* %2)
+  ; CHECK: call {{.*}}@llvm.invariant.start(i64 {{[0-9]+}}, i8*
+  %4 = bitcast %struct.A* %agg.tmp to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %4, i8* bitcast (%struct.A* @_ZL1i to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive = getelementptr inbounds %struct.A, %struct.A* %agg.tmp, i32 0, i32 0
+  %5 = load i32, i32* %coerce.dive
+  ; CHECK-5B: load i32, i32*
+  call void @_Z3bar1A(i32 %5)
+  %6 = bitcast %struct.A* %agg.tmp1 to i8*
+  %7 = bitcast %struct.A* %j to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %6, i8* %7, i64 4, i32 4, i1 false)
+  %coerce.dive2 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp1, i32 0, i32 0
+  %8 = load i32, i32* %coerce.dive2
+  ; CHECK-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %8)
+  call void @_Z4foo2PK1AS1_(%struct.A* %j, %struct.A* @_ZL1i)
+  %9 = bitcast %struct.A* %agg.tmp3 to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %9, i8* bitcast (%struct.A* @_ZL1i to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive4 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp3, i32 0, i32 0
+  %10 = load i32, i32* %coerce.dive4
+  ; CHECK-4-5A1-5B-NOT: load i32, i32*
+  ; CHECK-4-5A-5B1-NOT: load i32, i32*
+  ; CHECK-5A2-5B-NOT: load i32, i32*
+  ; CHECK-5B-NOT: load i32, i32*
+  ; CHECK-ALL-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %10)
+  %11 = bitcast %struct.A* %agg.tmp5 to i8*
+  %12 = bitcast %struct.A* %j to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %11, i8* %12, i64 4, i32 4, i1 false)
+  %coerce.dive6 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp5, i32 0, i32 0
+  %13 = load i32, i32* %coerce.dive6
+  ; CHECKLOAD-5B2: load i32, i32*
+  ; CHECK-4-5A1-5B-NOT: load i32, i32*
+  ; CHECK-5A2-5B-NOT: load i32, i32*
+  ; CHECK-5B-NOT: load i32, i32*
+  ; CHECK-ALL-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %13)
+  call void @llvm.invariant.end({}* %3, i64 4, i8* %2)
+  ; CHECK: call {{.*}}@llvm.invariant.end({{.*}}, i64 {{[0-9]+}}, i8*
+  %14 = bitcast %struct.A* %j to i8*
+  call void @llvm.lifetime.end(i64 4, i8* %14)
+  ret void
+}
+
+define internal void @__cxx_global_var_init() {
+entry:
+  %call = call i32 @_Z3onev()
+  call void @_ZN1AC1Ei(%struct.A* @_ZL1i, i32 %call)
+  ; CHECKINL: store i32 {{.*}}, i32*
+  %0 = call {}* @llvm.invariant.start(i64 4, i8* bitcast (%struct.A* @_ZL1i to i8*))
+  ; CHECK: call {{.*}}@llvm.invariant.start(i64 {{[0-9]+}}, i8*
+  ret void
+}
+
+declare i32 @_Z3onev()
+declare void @_Z3bar1A(i32)
+declare void @_Z3fooPK1A(%struct.A*)
+declare void @_Z4foo2PK1AS1_(%struct.A*, %struct.A*)
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture readonly, i64, i32, i1)
+declare {}* @llvm.invariant.start(i64, i8* nocapture)
+declare void @llvm.invariant.end({}*, i64, i8* nocapture)
+declare void @llvm.lifetime.start(i64, i8* nocapture)
+declare void @llvm.lifetime.end(i64, i8* nocapture)
+
+define internal void @_GLOBAL__sub_I_global_local() {
+entry:
+  call void @__cxx_global_var_init()
+  ret void
+}
+
+define linkonce_odr void @_ZN1AC1Ei(%struct.A* %this, i32 %a) {
+entry:
+  %this.addr = alloca %struct.A*
+  %a.addr = alloca i32
+  store %struct.A* %this, %struct.A** %this.addr
+  store i32 %a, i32* %a.addr
+  %this1 = load %struct.A*, %struct.A** %this.addr
+  %0 = load i32, i32* %a.addr
+  call void @_ZN1AC2Ei(%struct.A* %this1, i32 %0)
+  ret void
+}
+
+define linkonce_odr void @_ZN1AC2Ei(%struct.A* %this, i32 %a) {
+entry:
+  %this.addr = alloca %struct.A*
+  %a.addr = alloca i32
+  store %struct.A* %this, %struct.A** %this.addr
+  store i32 %a, i32* %a.addr
+  %this1 = load %struct.A*, %struct.A** %this.addr
+  %a2 = getelementptr inbounds %struct.A, %struct.A* %this1, i32 0, i32 0
+  %0 = load i32, i32* %a.addr
+  store i32 %0, i32* %a2
+  ret void
+}

test/Transforms/LoadElim/global-vars.ll

+
+;; NOTE: The CHECKLOAD-* prefixes indicate occurences of redundant loads in the output,
+;;                   expected when the loads are not from global variables.
+;;       The CHECK-* prefixes indicate removal of redundant loads in the output,
+;;                   expected when the loads are not from global variables. 
+;;       (ALL == 4-5A1-5A2-5B)
+
+;; * When the available load scan limit is 6, -instcombine does not 
+;;   eliminate some redundant loads that either it would eliminate
+;;   with a load scan limit of 8, or -gvn would eliminate.
+; RUN: opt < %s -globalopt -available-load-scan-limit=6 -instcombine -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-5A2-5B --check-prefix=CHECKLOAD-4-5A1
+; RUN: opt < %s -globalopt -available-load-scan-limit=6 -instcombine -gvn -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-ALL
+; RUN: opt < %s -globalopt -available-load-scan-limit=8 -instcombine -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-5A2-5B --check-prefix=CHECKLOAD-4-5A1
+; RUN: opt < %s -globalopt -available-load-scan-limit=8 -instcombine -gvn -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-ALL
+
+;; * Adding '-inline -early-cse' enables a few more load eliminations,
+;;   but does not merge the same loads into the store as per local vars.
+; RUN: opt < %s -globalopt -available-load-scan-limit=6 -instcombine -inline -early-cse -instcombine -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECKINL --check-prefix=CHECK-5A2-5B --check-prefix=CHECKLOAD-4-5A1
+; RUN: opt < %s -globalopt -available-load-scan-limit=6 -instcombine -inline -early-cse -gvn -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECKINL --check-prefix=CHECK-ALL
+; RUN: opt < %s -globalopt -available-load-scan-limit=8 -instcombine -inline -early-cse -instcombine -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECKINL --check-prefix=CHECK-5A2-5B --check-prefix=CHECKLOAD-4-5A1
+; RUN: opt < %s -globalopt -available-load-scan-limit=8 -instcombine -inline -early-cse -gvn -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECKINL --check-prefix=CHECK-ALL
+
+;; * When the load scan limit is 8,
+;;   '-functionattrs -tailcallelim -instcombine' may be as good as '-gvn'.
+;;   But the same can't be said when the limit is 6.
+; RUN: opt < %s -globalopt -available-load-scan-limit=8 -instcombine -functionattrs -tailcallelim -instcombine -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-ALL
+; RUN: opt < %s -globalopt -available-load-scan-limit=6 -instcombine -functionattrs -tailcallelim -instcombine -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-4-5A-5B1 --check-prefix=CHECKLOAD-5B2
+
+%struct.A = type { i32 }
+
+@_ZL1i = internal global %struct.A zeroinitializer
+@k = global %struct.A zeroinitializer
+@_ZL1j = internal global %struct.A zeroinitializer
[e-mail]_ctors = appending global [1 x { i32, void ()*, i8* }] [{ i32, void ()*, i8* } { i32 65535, void ()* @_GLOBAL__sub_I_global, i8* null }]
+
+;; Example 1: Duplicate loads.
+;; void ex1() {
+;;   const Type i(one());
+;;   bar(i);            // First load.
+;;   foo(&i);           // Does not change i.
+;;   bar(i);            // No load.
+;; }
+define void @_Z3ex1v() {
+; CHECK: @_Z3ex1v(
+entry:
+  %agg.tmp = alloca %struct.A
+  %agg.tmp1 = alloca %struct.A
+  %0 = bitcast %struct.A* %agg.tmp to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* bitcast (%struct.A* @_ZL1i to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive = getelementptr inbounds %struct.A, %struct.A* %agg.tmp, i32 0, i32 0
+  %1 = load i32, i32* %coerce.dive
+  ; CHECK: load i32, i32*
+  call void @_Z3bar1A(i32 %1)
+  call void @_Z3fooPK1A(%struct.A* @_ZL1i)
+  %2 = bitcast %struct.A* %agg.tmp1 to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %2, i8* bitcast (%struct.A* @_ZL1i to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive2 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp1, i32 0, i32 0
+  %3 = load i32, i32* %coerce.dive2
+  ; CHECK-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %3)
+  ret void
+}
+
+;; Example 2: Unnecessary stores and loads.
+;; void ex2() {
+;;   const Type i(one());
+;;   const Type j = i;  // Note: i == j, &i != &j  ==> No store.
+;;   bar(i);            // First load.
+;;   foo(&i);           // Does not change i, nor j.
+;;   bar(j);            // No load; Reuse i location.
+;; }
+define void @_Z3ex2v() {
+; CHECK: @_Z3ex2v(
+entry:
+  %agg.tmp = alloca %struct.A
+  %agg.tmp1 = alloca %struct.A
+  %0 = bitcast %struct.A* %agg.tmp to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* bitcast (%struct.A* @_ZL1i to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive = getelementptr inbounds %struct.A, %struct.A* %agg.tmp, i32 0, i32 0
+  %1 = load i32, i32* %coerce.dive
+  ; CHECK: load i32, i32*
+  call void @_Z3bar1A(i32 %1)
+  call void @_Z3fooPK1A(%struct.A* @_ZL1i)
+  %2 = bitcast %struct.A* %agg.tmp1 to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %2, i8* bitcast (%struct.A* @_ZL1j to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive2 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp1, i32 0, i32 0
+  %3 = load i32, i32* %coerce.dive2
+  ; CHECK: load i32, i32*
+  call void @_Z3bar1A(i32 %3)
+  ret void
+}
+
+;; Example 3: Necessary stores and loads.
+;; void ex3() {
+;;   const Type i(1);
+;;   Type k = i;        // Note: i == k, &i != &k  ==> Keep store.
+;;   bar(i);            // First load.
+;;   foo(&k);           // Does not change i; May change k.
+;;   bar(k);            // Keep load.
+;; }
+define void @_Z3ex3v() {
+; CHECK: @_Z3ex3v(
+entry:
+  %agg.tmp = alloca %struct.A
+  %agg.tmp1 = alloca %struct.A
+  %0 = bitcast %struct.A* %agg.tmp to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* bitcast (%struct.A* @_ZL1i to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive = getelementptr inbounds %struct.A, %struct.A* %agg.tmp, i32 0, i32 0
+  %1 = load i32, i32* %coerce.dive
+  ; CHECK: load i32, i32*
+  call void @_Z3bar1A(i32 %1)
+  call void @_Z3fooPK1A(%struct.A* @k)
+  %2 = bitcast %struct.A* %agg.tmp1 to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %2, i8* bitcast (%struct.A* @k to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive2 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp1, i32 0, i32 0
+  %3 = load i32, i32* %coerce.dive2
+  ; CHECK: load i32, i32*
+  call void @_Z3bar1A(i32 %3)
+  ret void
+}
+
+;; Example 4: Smart stores and loads.
+;; void ex4() {
+;;   const Type i(one());
+;;   Type k = i;        // Note: i == k, &i != &k  ==> May keep store.
+;;   bar(i);            // First load.
+;;   foo(&i);           // Does not change i, nor k.
+;;   bar(k);            // No load; Reuse i location.
+;;   foo(&k);           // Does not change i; May change k.
+;;   bar(k);            // Keep load.
+;; }
+define void @_Z3ex4v() {
+; CHECK: @_Z3ex4v(
+entry:
+  %agg.tmp = alloca %struct.A
+  %agg.tmp1 = alloca %struct.A
+  %agg.tmp3 = alloca %struct.A
+  %0 = bitcast %struct.A* %agg.tmp to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* bitcast (%struct.A* @_ZL1i to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive = getelementptr inbounds %struct.A, %struct.A* %agg.tmp, i32 0, i32 0
+  %1 = load i32, i32* %coerce.dive
+  ; CHECK: load i32, i32*
+  call void @_Z3bar1A(i32 %1)
+  call void @_Z3fooPK1A(%struct.A* @_ZL1i)
+  %2 = bitcast %struct.A* %agg.tmp1 to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %2, i8* bitcast (%struct.A* @k to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive2 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp1, i32 0, i32 0
+  %3 = load i32, i32* %coerce.dive2
+  ; CHECKLOAD-4-5A1: load i32, i32*
+  ; CHECK-4-5A-5B1: load i32, i32*
+  ; CHECK-ALL: load i32, i32*
+  call void @_Z3bar1A(i32 %3)
+  call void @_Z3fooPK1A(%struct.A* @k)
+  %4 = bitcast %struct.A* %agg.tmp3 to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %4, i8* bitcast (%struct.A* @k to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive4 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp3, i32 0, i32 0
+  %5 = load i32, i32* %coerce.dive4
+  ; CHECK: load i32, i32*
+  call void @_Z3bar1A(i32 %5)
+  ret void
+}
+
+;; Example 5: Duplicate and smart loads (and stores).
+;; void ex5a() {
+;;   const Type i(one());
+;;   Type k = i;        // Note: i == k, &i != &k  ==> May keep store.
+;;   bar(i);            // First load.
+;;   bar(k);            // No load; Reuse i location.
+;;   foo2(&k, &i);      // Does not change i; May change k.
+;;   bar(i);            // No load.
+;;   bar(k);            // Keep load.
+;; }
+define void @_Z4ex5av() {
+; CHECK: @_Z4ex5av(
+entry:
+  %agg.tmp = alloca %struct.A
+  %agg.tmp1 = alloca %struct.A
+  %agg.tmp3 = alloca %struct.A
+  %agg.tmp5 = alloca %struct.A
+  %0 = bitcast %struct.A* %agg.tmp to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* bitcast (%struct.A* @_ZL1i to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive = getelementptr inbounds %struct.A, %struct.A* %agg.tmp, i32 0, i32 0
+  %1 = load i32, i32* %coerce.dive
+  ; CHECK: load i32, i32*
+  call void @_Z3bar1A(i32 %1)
+  %2 = bitcast %struct.A* %agg.tmp1 to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %2, i8* bitcast (%struct.A* @k to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive2 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp1, i32 0, i32 0
+  %3 = load i32, i32* %coerce.dive2
+  ; CHECKLOAD-4-5A1: load i32, i32*
+  ; CHECK-4-5A-5B1: load i32, i32*
+  ; CHECK-ALL: load i32, i32*
+  call void @_Z3bar1A(i32 %3)
+  call void @_Z4foo2PK1AS1_(%struct.A* @k, %struct.A* @_ZL1i)
+  %4 = bitcast %struct.A* %agg.tmp3 to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %4, i8* bitcast (%struct.A* @_ZL1i to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive4 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp3, i32 0, i32 0
+  %5 = load i32, i32* %coerce.dive4
+  ; CHECK-4-5A-5B1-NOT: load i32, i32*
+  ; CHECK-5A2-5B-NOT: load i32, i32*
+  ; CHECK-ALL-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %5)
+  %6 = bitcast %struct.A* %agg.tmp5 to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %6, i8* bitcast (%struct.A* @k to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive6 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp5, i32 0, i32 0
+  %7 = load i32, i32* %coerce.dive6
+  ; CHECK: load i32, i32*
+  call void @_Z3bar1A(i32 %7)
+  ret void
+}
+
+;; Example 5: Duplicate and smart loads (and stores).
+;; void ex5b() {
+;;   const Type i(one());
+;;   const Type j = i;  // Note: i == j, &i != &j  ==> No store.
+;;   bar(i);            // First load.
+;;   bar(j);            // No load; Reuse i location.
+;;   foo2(&j, &i);      // Does not change i, nor j.
+;;   bar(i);            // No load.
+;;   bar(j);            // No load; Reuse i location.
+;; }
+define void @_Z4ex5bv() {
+; CHECK: @_Z4ex5bv(
+entry:
+  %agg.tmp = alloca %struct.A
+  %agg.tmp1 = alloca %struct.A
+  %agg.tmp3 = alloca %struct.A
+  %agg.tmp5 = alloca %struct.A
+  %0 = bitcast %struct.A* %agg.tmp to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* bitcast (%struct.A* @_ZL1i to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive = getelementptr inbounds %struct.A, %struct.A* %agg.tmp, i32 0, i32 0
+  %1 = load i32, i32* %coerce.dive
+  ; CHECK-5A2-5B: load i32, i32*
+  ; CHECK-ALL: load i32, i32*
+  call void @_Z3bar1A(i32 %1)
+  %2 = bitcast %struct.A* %agg.tmp1 to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %2, i8* bitcast (%struct.A* @_ZL1j to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive2 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp1, i32 0, i32 0
+  %3 = load i32, i32* %coerce.dive2
+  ; CHECK: load i32, i32*
+  call void @_Z3bar1A(i32 %3)
+  call void @_Z4foo2PK1AS1_(%struct.A* @_ZL1j, %struct.A* @_ZL1i)
+  %4 = bitcast %struct.A* %agg.tmp3 to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %4, i8* bitcast (%struct.A* @_ZL1i to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive4 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp3, i32 0, i32 0
+  %5 = load i32, i32* %coerce.dive4
+  ; CHECK-4-5A-5B1-NOT: load i32, i32*
+  ; CHECK-5A2-5B-NOT: load i32, i32*
+  ; CHECK-ALL-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %5)
+  %6 = bitcast %struct.A* %agg.tmp5 to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %6, i8* bitcast (%struct.A* @_ZL1j to i8*), i64 4, i32 4, i1 false)
+  %coerce.dive6 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp5, i32 0, i32 0
+  %7 = load i32, i32* %coerce.dive6
+  ; CHECKLOAD-5B2: load i32, i32*
+  ; CHECK-5A2-5B-NOT: load i32, i32*
+  ; CHECK-ALL-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %7)
+  ret void
+}
+
+define internal void @__cxx_global_var_init() {
+entry:
+  %call = call i32 @_Z3onev()
+  call void @_ZN1AC1Ei(%struct.A* @_ZL1i, i32 %call)
+  ; CHECKINL: store i32 {{.*}}, i32*
+  %0 = call {}* @llvm.invariant.start(i64 4, i8* bitcast (%struct.A* @_ZL1i to i8*))
+  ; CHECK: call {{.*}}@llvm.invariant.start(i64 {{[0-9]+}}, i8*
+  ret void
+}
+
+define internal void @__cxx_global_var_init.2() {
+entry:
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* bitcast (%struct.A* @_ZL1j to i8*), i8* bitcast (%struct.A* @_ZL1i to i8*), i64 4, i32 4, i1 false)
+  %0 = call {}* @llvm.invariant.start(i64 4, i8* bitcast (%struct.A* @_ZL1j to i8*))
+  ; CHECK: call {{.*}}@llvm.invariant.start(i64 {{[0-9]+}}, i8*
+  ret void
+}
+
+declare i32 @_Z3onev()
+declare void @_Z3bar1A(i32)
+declare void @_Z3fooPK1A(%struct.A*)
+declare void @_Z4foo2PK1AS1_(%struct.A*, %struct.A*)
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture readonly, i64, i32, i1)
+declare {}* @llvm.invariant.start(i64, i8* nocapture)
+declare void @llvm.invariant.end({}*, i64, i8* nocapture)
+declare void @llvm.lifetime.start(i64, i8* nocapture)
+declare void @llvm.lifetime.end(i64, i8* nocapture)
+
+define internal void @_GLOBAL__sub_I_global() {
+entry:
+  call void @__cxx_global_var_init()
+  call void @__cxx_global_var_init.2()
+  call void @__cxx_global_var_init.1()
+  ret void
+}
+
+define internal void @__cxx_global_var_init.1() {
+entry:
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* bitcast (%struct.A* @k to i8*), i8* bitcast (%struct.A* @_ZL1i to i8*), i64 4, i32 4, i1 false)
+  ret void
+}
+
+define linkonce_odr void @_ZN1AC1Ei(%struct.A* %this, i32 %a) {
+entry:
+  %this.addr = alloca %struct.A*
+  %a.addr = alloca i32
+  store %struct.A* %this, %struct.A** %this.addr
+  store i32 %a, i32* %a.addr
+  %this1 = load %struct.A*, %struct.A** %this.addr
+  %0 = load i32, i32* %a.addr
+  call void @_ZN1AC2Ei(%struct.A* %this1, i32 %0)
+  ret void
+}
+
+define linkonce_odr void @_ZN1AC2Ei(%struct.A* %this, i32 %a) {
+entry:
+  %this.addr = alloca %struct.A*
+  %a.addr = alloca i32
+  store %struct.A* %this, %struct.A** %this.addr
+  store i32 %a, i32* %a.addr
+  %this1 = load %struct.A*, %struct.A** %this.addr
+  %a2 = getelementptr inbounds %struct.A, %struct.A* %this1, i32 0, i32 0
+  %0 = load i32, i32* %a.addr
+  store i32 %0, i32* %a2
+  ret void
+}

test/Transforms/LoadElim/local-vars.ll

+
+;; NOTE: The CHECKLOAD-* prefixes indicate occurences of redundant loads in the output.
+;;       The CHECK-* prefixes indicate removal of redundant loads in the output. (ALL == 4-5A1-5A2-5B)
+
+;; * When the available load scan limit is 6, -instcombine does not 
+;;   eliminate some redundant loads that either it would eliminate
+;;   with a load scan limit of 8, or -gvn would eliminate.
+; RUN: opt < %s -available-load-scan-limit=6 -instcombine -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECKNOINL --check-prefix=CHECKLOAD-ALL
+; RUN: opt < %s -available-load-scan-limit=6 -instcombine -gvn -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECKNOINL --check-prefix=CHECK-ALL
+; RUN: opt < %s -available-load-scan-limit=8 -instcombine -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECKNOINL --check-prefix=CHECK-5A2-5B --check-prefix=CHECKLOAD-4-5A1
+; RUN: opt < %s -available-load-scan-limit=8 -instcombine -gvn -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECKNOINL --check-prefix=CHECK-ALL
+
+;; * Adding '-inline -early-cse' enables a few more load eliminations.
+; RUN: opt < %s -available-load-scan-limit=6 -instcombine -inline -early-cse -instcombine -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECKINL --check-prefix=CHECKINV --check-prefix=CHECK-5B1 --check-prefix=CHECKLOAD-4-5A-5B2
+; RUN: opt < %s -available-load-scan-limit=6 -instcombine -inline -early-cse -gvn -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECKINL --check-prefix=CHECKINV3 --check-prefix=CHECK-ALL
+; RUN: opt < %s -available-load-scan-limit=8 -instcombine -inline -early-cse -instcombine -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECKINL --check-prefix=CHECKINV --check-prefix=CHECK-5A2-5B --check-prefix=CHECKLOAD-4-5A1
+; RUN: opt < %s -available-load-scan-limit=8 -instcombine -inline -early-cse -gvn -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECKINL --check-prefix=CHECKINV3 --check-prefix=CHECK-ALL
+
+;; * When the load scan limit is 8,
+;;   '-functionattrs -tailcallelim -instcombine' may be as good as '-gvn'.
+;;   But the same can't be said when the limit is 6.
+; RUN: opt < %s -available-load-scan-limit=8 -instcombine -functionattrs -tailcallelim -instcombine -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECKNOINL --check-prefix=CHECK-ALL
+; RUN: opt < %s -available-load-scan-limit=6 -instcombine -functionattrs -tailcallelim -instcombine -S | FileCheck %s --check-prefix=CHECK --check-prefix=CHECKNOINL --check-prefix=CHECK-5A-5B1 --check-prefix=CHECKLOAD-4-5B2
+
+
+%struct.A = type { i32 }
+
+;; Example 1: Duplicate loads.
+;; void ex1() {
+;;   const Type i(one());
+;;   bar(i);            // First load.
+;;   foo(&i);           // Does not change i.
+;;   bar(i);            // No load.
+;; }
+define void @_Z3ex1v() {
+entry:
+  %i = alloca %struct.A
+  %agg.tmp = alloca %struct.A
+  %agg.tmp1 = alloca %struct.A
+  %0 = bitcast %struct.A* %i to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %0) 
+  %call = call i32 @_Z3onev()
+  call void @_ZN1AC2Ei(%struct.A* %i, i32 %call)
+  ; CHECKINL: store i32 {{.*}}, i32*
+  %1 = bitcast %struct.A* %i to i8*
+  %2 = call {}* @llvm.invariant.start(i64 4, i8* %1)
+  ; CHECK: call {{.*}}@llvm.invariant.start(i64 {{[0-9]+}}, i8*
+  %3 = bitcast %struct.A* %agg.tmp to i8*
+  %4 = bitcast %struct.A* %i to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %3, i8* %4, i64 4, i32 4, i1 false)
+  %coerce.dive = getelementptr inbounds %struct.A, %struct.A* %agg.tmp, i32 0, i32 0
+  %5 = load i32, i32* %coerce.dive
+  ; CHECKNOINL: load i32, i32*
+  ; CHECKINL-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %5)
+  call void @_Z3fooPK1A(%struct.A* %i)
+  %6 = bitcast %struct.A* %agg.tmp1 to i8*
+  %7 = bitcast %struct.A* %i to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %6, i8* %7, i64 4, i32 4, i1 false)
+  %coerce.dive2 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp1, i32 0, i32 0
+  %8 = load i32, i32* %coerce.dive2
+  ; CHECK-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %8)
+  call void @llvm.invariant.end({}* %2, i64 4, i8* %1)
+  ; CHECK: call {{.*}}@llvm.invariant.end({{.*}}, i64 {{[0-9]+}}, i8*
+  %9 = bitcast %struct.A* %i to i8*
+  call void @llvm.lifetime.end(i64 4, i8* %9) 
+  ret void
+}
+
+;; Example 2: Unnecessary stores and loads.
+;; void ex2() {
+;;   const Type i(one());
+;;   const Type j = i;  // Note: i == j, &i != &j  ==> No store.
+;;   bar(i);            // First load.
+;;   foo(&i);           // Does not change i, nor j.
+;;   bar(j);            // No load; Reuse i location.
+;; }
+define void @_Z3ex2v() {
+entry:
+  %i = alloca %struct.A
+  %j = alloca %struct.A
+  %agg.tmp = alloca %struct.A
+  %agg.tmp1 = alloca %struct.A
+  %0 = bitcast %struct.A* %i to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %0) 
+  %call = call i32 @_Z3onev()
+  call void @_ZN1AC2Ei(%struct.A* %i, i32 %call)
+  ; CHECKINL: store i32 {{.*}}, i32*
+  %1 = bitcast %struct.A* %i to i8*
+  %2 = call {}* @llvm.invariant.start(i64 4, i8* %1)
+  ; CHECK: call {{.*}}@llvm.invariant.start(i64 {{[0-9]+}}, i8*
+  %3 = bitcast %struct.A* %j to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %3) 
+  %4 = bitcast %struct.A* %j to i8*
+  %5 = bitcast %struct.A* %i to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %4, i8* %5, i64 4, i32 4, i1 false)
+  %6 = bitcast %struct.A* %j to i8*
+  %7 = call {}* @llvm.invariant.start(i64 4, i8* %6)
+  ; CHECK-NOT: call {{.*}}@llvm.invariant.start(i64 {{[0-9]+}}, i8*
+  %8 = bitcast %struct.A* %agg.tmp to i8*
+  %9 = bitcast %struct.A* %i to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %8, i8* %9, i64 4, i32 4, i1 false)
+  %coerce.dive = getelementptr inbounds %struct.A, %struct.A* %agg.tmp, i32 0, i32 0
+  %10 = load i32, i32* %coerce.dive
+  ; CHECKNOINL: load i32, i32*
+  ; CHECKINL-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %10)
+  call void @_Z3fooPK1A(%struct.A* %i)
+  %11 = bitcast %struct.A* %agg.tmp1 to i8*
+  %12 = bitcast %struct.A* %j to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %11, i8* %12, i64 4, i32 4, i1 false)
+  %coerce.dive2 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp1, i32 0, i32 0
+  %13 = load i32, i32* %coerce.dive2
+  ; CHECK-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %13)
+  call void @llvm.invariant.end({}* %7, i64 4, i8* %6)
+  ; CHECK-NOT: call {{.*}}@llvm.invariant.end({{.*}}, i64 {{[0-9]+}}, i8*
+  %14 = bitcast %struct.A* %j to i8*
+  call void @llvm.lifetime.end(i64 4, i8* %14) 
+  call void @llvm.invariant.end({}* %2, i64 4, i8* %1)
+  ; CHECK: call {{.*}}@llvm.invariant.end({{.*}}, i64 {{[0-9]+}}, i8*
+  %15 = bitcast %struct.A* %i to i8*
+  call void @llvm.lifetime.end(i64 4, i8* %15) 
+  ret void
+}
+
+;; Example 3: Necessary stores and loads.
+;; void ex3() {
+;;   const Type i(1);
+;;   Type k = i;        // Note: i == k, &i != &k  ==> Keep store.
+;;   bar(i);            // First load.
+;;   foo(&k);           // Does not change i; May change k.
+;;   bar(k);            // Keep load.
+;; }
+define void @_Z3ex3v() {
+entry:
+  %i = alloca %struct.A
+  %k = alloca %struct.A
+  %agg.tmp = alloca %struct.A
+  %agg.tmp1 = alloca %struct.A
+  %0 = bitcast %struct.A* %i to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %0) 
+  %call = call i32 @_Z3onev()
+  call void @_ZN1AC2Ei(%struct.A* %i, i32 %call)
+  ; CHECKINL: store i32 {{.*}}, i32*
+  %1 = bitcast %struct.A* %i to i8*
+  %2 = call {}* @llvm.invariant.start(i64 4, i8* %1)
+  ; CHECKNOINL: call {{.*}}@llvm.invariant.start(i64 {{[0-9]+}}, i8*
+  ; CHECKINV3: call {{.*}}@llvm.invariant.start(i64 {{[0-9]+}}, i8*
+  ; CHECKINV-NOT: call {{.*}}@llvm.invariant.start(i64 {{[0-9]+}}, i8*
+  %3 = bitcast %struct.A* %k to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %3) 
+  %4 = bitcast %struct.A* %k to i8*
+  %5 = bitcast %struct.A* %i to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %4, i8* %5, i64 4, i32 4, i1 false)
+  %6 = bitcast %struct.A* %agg.tmp to i8*
+  %7 = bitcast %struct.A* %i to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %6, i8* %7, i64 4, i32 4, i1 false)
+  %coerce.dive = getelementptr inbounds %struct.A, %struct.A* %agg.tmp, i32 0, i32 0
+  %8 = load i32, i32* %coerce.dive
+  ; CHECKNOINL: load i32, i32*
+  ; CHECKINL-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %8)
+  call void @_Z3fooPK1A(%struct.A* %k)
+  %9 = bitcast %struct.A* %agg.tmp1 to i8*
+  %10 = bitcast %struct.A* %k to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %9, i8* %10, i64 4, i32 4, i1 false)
+  %coerce.dive2 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp1, i32 0, i32 0
+  %11 = load i32, i32* %coerce.dive2
+  ; CHECK: load i32, i32*
+  call void @_Z3bar1A(i32 %11)
+  %12 = bitcast %struct.A* %k to i8*
+  call void @llvm.lifetime.end(i64 4, i8* %12) 
+  call void @llvm.invariant.end({}* %2, i64 4, i8* %1)
+  ; CHEC K-ALL: call {{.*}}@llvm.invariant.end({{.*}}, i64 {{[0-9]+}}, i8*  ; FIXME:
+  ; CHECKNOINL: call {{.*}}@llvm.invariant.end({{.*}}, i64 {{[0-9]+}}, i8*
+  ; CHECKINV3: call {{.*}}@llvm.invariant.end({{.*}}, i64 {{[0-9]+}}, i8*
+  ; CHECKINV-NOT: call {{.*}}@llvm.invariant.end({{.*}}, i64 {{[0-9]+}}, i8*
+  %13 = bitcast %struct.A* %i to i8*
+  call void @llvm.lifetime.end(i64 4, i8* %13) 
+  ret void
+}
+
+;; Example 4: Smart stores and loads.
+;; void ex4() {
+;;   const Type i(one());
+;;   Type k = i;        // Note: i == k, &i != &k  ==> May keep store.
+;;   bar(i);            // First load.
+;;   foo(&i);           // Does not change i, nor k.
+;;   bar(k);            // No load; Reuse i location.
+;;   foo(&k);           // Does not change i; May change k.
+;;   bar(k);            // Keep load.
+;; }
+define void @_Z3ex4v() {
+entry:
+  %i = alloca %struct.A
+  %k = alloca %struct.A
+  %agg.tmp = alloca %struct.A
+  %agg.tmp1 = alloca %struct.A
+  %agg.tmp3 = alloca %struct.A
+  %0 = bitcast %struct.A* %i to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %0) 
+  %call = call i32 @_Z3onev()
+  call void @_ZN1AC2Ei(%struct.A* %i, i32 %call)
+  ; CHECKINL: store i32 {{.*}}, i32*
+  %1 = bitcast %struct.A* %i to i8*
+  %2 = call {}* @llvm.invariant.start(i64 4, i8* %1)
+  ; CHECK: call {{.*}}@llvm.invariant.start(i64 {{[0-9]+}}, i8*
+  %3 = bitcast %struct.A* %k to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %3) 
+  %4 = bitcast %struct.A* %k to i8*
+  %5 = bitcast %struct.A* %i to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %4, i8* %5, i64 4, i32 4, i1 false)
+  %6 = bitcast %struct.A* %agg.tmp to i8*
+  %7 = bitcast %struct.A* %i to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %6, i8* %7, i64 4, i32 4, i1 false)
+  %coerce.dive = getelementptr inbounds %struct.A, %struct.A* %agg.tmp, i32 0, i32 0
+  %8 = load i32, i32* %coerce.dive
+  ; CHECKNOINL: load i32, i32*
+  ; CHECKINL-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %8)
+  call void @_Z3fooPK1A(%struct.A* %i)
+  %9 = bitcast %struct.A* %agg.tmp1 to i8*
+  %10 = bitcast %struct.A* %k to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %9, i8* %10, i64 4, i32 4, i1 false)
+  %coerce.dive2 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp1, i32 0, i32 0
+  %11 = load i32, i32* %coerce.dive2
+  ; CHECKLOAD-4-5A1: load i32, i32*
+  ; CHECKLOAD-4-5B2: load i32, i32*
+  ; CHECKLOAD-4-5A-5B2: load i32, i32*
+  ; CHECKLOAD-ALL: load i32, i32*
+  ; CHECK-ALL-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %11)
+  call void @_Z3fooPK1A(%struct.A* %k)
+  %12 = bitcast %struct.A* %agg.tmp3 to i8*
+  %13 = bitcast %struct.A* %k to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %12, i8* %13, i64 4, i32 4, i1 false)
+  %coerce.dive4 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp3, i32 0, i32 0
+  %14 = load i32, i32* %coerce.dive4
+  ; CHECK: load i32, i32*
+  call void @_Z3bar1A(i32 %14)
+  %15 = bitcast %struct.A* %k to i8*
+  call void @llvm.lifetime.end(i64 4, i8* %15) 
+  call void @llvm.invariant.end({}* %2, i64 4, i8* %1)
+  ; CHECK: call {{.*}}@llvm.invariant.end({{.*}}, i64 {{[0-9]+}}, i8*
+  %16 = bitcast %struct.A* %i to i8*
+  call void @llvm.lifetime.end(i64 4, i8* %16) 
+  ret void
+}
+
+;; Example 5: Duplicate and smart loads (and stores).
+;; void ex5a() {
+;;   const Type i(one());
+;;   Type k = i;        // Note: i == k, &i != &k  ==> May keep store.
+;;   bar(i);            // First load.
+;;   bar(k);            // No load; Reuse i location.
+;;   foo2(&k, &i);      // Does not change i; May change k.
+;;   bar(i);            // No load.
+;;   bar(k);            // Keep load.
+;; }
+define void @_Z4ex5av() {
+entry:
+  %i = alloca %struct.A
+  %k = alloca %struct.A
+  %agg.tmp = alloca %struct.A
+  %agg.tmp1 = alloca %struct.A
+  %agg.tmp3 = alloca %struct.A
+  %agg.tmp5 = alloca %struct.A
+  %0 = bitcast %struct.A* %i to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %0) 
+  %call = call i32 @_Z3onev()
+  call void @_ZN1AC2Ei(%struct.A* %i, i32 %call)
+  ; CHECKINL: store i32 {{.*}}, i32*
+  %1 = bitcast %struct.A* %i to i8*
+  %2 = call {}* @llvm.invariant.start(i64 4, i8* %1)
+  ; CHECK: call {{.*}}@llvm.invariant.start(i64 {{[0-9]+}}, i8*
+  %3 = bitcast %struct.A* %k to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %3) 
+  %4 = bitcast %struct.A* %k to i8*
+  %5 = bitcast %struct.A* %i to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %4, i8* %5, i64 4, i32 4, i1 false)
+  %6 = bitcast %struct.A* %agg.tmp to i8*
+  %7 = bitcast %struct.A* %i to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %6, i8* %7, i64 4, i32 4, i1 false)
+  %coerce.dive = getelementptr inbounds %struct.A, %struct.A* %agg.tmp, i32 0, i32 0
+  %8 = load i32, i32* %coerce.dive
+  ; CHECKNOINL: load i32, i32*
+  ; CHECKINL-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %8)
+  %9 = bitcast %struct.A* %agg.tmp1 to i8*
+  %10 = bitcast %struct.A* %k to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %9, i8* %10, i64 4, i32 4, i1 false)
+  %coerce.dive2 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp1, i32 0, i32 0
+  %11 = load i32, i32* %coerce.dive2
+  ; CHECKLOAD-4-5A1: load i32, i32*
+  ; CHECKLOAD-4-5A-5B2: load i32, i32*
+  ; CHECK-5A-5B1-NOT: load i32, i32*
+  ; CHECK-ALL-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %11)
+  call void @_Z4foo2PK1AS1_(%struct.A* %k, %struct.A* %i)
+  %12 = bitcast %struct.A* %agg.tmp3 to i8*
+  %13 = bitcast %struct.A* %i to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %12, i8* %13, i64 4, i32 4, i1 false)
+  %coerce.dive4 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp3, i32 0, i32 0
+  %14 = load i32, i32* %coerce.dive4
+  ; CHECKLOAD-4-5A-5B2: load i32, i32*
+  ; CHECKLOAD-ALL: load i32, i32*
+  ; CHECK-5A-5B1-NOT: load i32, i32*
+  ; CHECK-5A2-NOT: load i32, i32*
+  ; CHECK-5A2-5B-NOT: load i32, i32*
+  ; CHECK-ALL-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %14)
+  %15 = bitcast %struct.A* %agg.tmp5 to i8*
+  %16 = bitcast %struct.A* %k to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %15, i8* %16, i64 4, i32 4, i1 false)
+  %coerce.dive6 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp5, i32 0, i32 0
+  %17 = load i32, i32* %coerce.dive6
+  ; CHECK: load i32, i32*
+  call void @_Z3bar1A(i32 %17)
+  %18 = bitcast %struct.A* %k to i8*
+  call void @llvm.lifetime.end(i64 4, i8* %18) 
+  call void @llvm.invariant.end({}* %2, i64 4, i8* %1)
+  ; CHECK: call {{.*}}@llvm.invariant.end({{.*}}, i64 {{[0-9]+}}, i8*
+  %19 = bitcast %struct.A* %i to i8*
+  call void @llvm.lifetime.end(i64 4, i8* %19) 
+  ret void
+}
+
+;; Example 5: Duplicate and smart loads (and stores).
+;; void ex5b() {
+;;   const Type i(one());
+;;   const Type j = i;  // Note: i == j, &i != &j  ==> No store.
+;;   bar(i);            // First load.
+;;   bar(j);            // No load; Reuse i location.
+;;   foo2(&j, &i);      // Does not change i, nor j.
+;;   bar(i);            // No load.
+;;   bar(j);            // No load; Reuse i location.
+;; }
+define void @_Z4ex5bv() {
+entry:
+  %i = alloca %struct.A
+  %j = alloca %struct.A
+  %agg.tmp = alloca %struct.A
+  %agg.tmp1 = alloca %struct.A
+  %agg.tmp3 = alloca %struct.A
+  %agg.tmp5 = alloca %struct.A
+  %0 = bitcast %struct.A* %i to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %0) 
+  %call = call i32 @_Z3onev()
+  call void @_ZN1AC2Ei(%struct.A* %i, i32 %call)
+  ; CHECKINL: store i32 {{.*}}, i32*
+  %1 = bitcast %struct.A* %i to i8*
+  %2 = call {}* @llvm.invariant.start(i64 4, i8* %1)
+  ; CHECK: call {{.*}}@llvm.invariant.start(i64 {{[0-9]+}}, i8*
+  %3 = bitcast %struct.A* %j to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %3) 
+  %4 = bitcast %struct.A* %j to i8*
+  %5 = bitcast %struct.A* %i to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %4, i8* %5, i64 4, i32 4, i1 false)
+  %6 = bitcast %struct.A* %j to i8*
+  %7 = call {}* @llvm.invariant.start(i64 4, i8* %6)
+  ; CHECK: call {{.*}}@llvm.invariant.start(i64 {{[0-9]+}}, i8*
+  %8 = bitcast %struct.A* %agg.tmp to i8*
+  %9 = bitcast %struct.A* %i to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %8, i8* %9, i64 4, i32 4, i1 false)
+  %coerce.dive = getelementptr inbounds %struct.A, %struct.A* %agg.tmp, i32 0, i32 0
+  %10 = load i32, i32* %coerce.dive
+  ; CHECKNOINL-ALL: load i32, i32*
+  ; CHECKINL-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %10)
+  %11 = bitcast %struct.A* %agg.tmp1 to i8*
+  %12 = bitcast %struct.A* %j to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %11, i8* %12, i64 4, i32 4, i1 false)
+  %coerce.dive2 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp1, i32 0, i32 0
+  %13 = load i32, i32* %coerce.dive2
+  ; CHECK-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %13)
+  call void @_Z4foo2PK1AS1_(%struct.A* %j, %struct.A* %i)
+  %14 = bitcast %struct.A* %agg.tmp3 to i8*
+  %15 = bitcast %struct.A* %i to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %14, i8* %15, i64 4, i32 4, i1 false)
+  %coerce.dive4 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp3, i32 0, i32 0
+  %16 = load i32, i32* %coerce.dive4
+  ; CHECKLOAD-ALL: load i32, i32*
+  ; CHECK-5A2-5B-NOT: load i32, i32*
+  ; CHECK-5A-5B1-NOT: load i32, i32*
+  ; CHECK-ALL-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %16)
+  %17 = bitcast %struct.A* %agg.tmp5 to i8*
+  %18 = bitcast %struct.A* %j to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %17, i8* %18, i64 4, i32 4, i1 false)
+  %coerce.dive6 = getelementptr inbounds %struct.A, %struct.A* %agg.tmp5, i32 0, i32 0
+  %19 = load i32, i32* %coerce.dive6
+  ; CHECKLOAD-4-5B2: load i32, i32*
+  ; CHECKLOAD-4-5A-5B2: load i32, i32*
+  ; CHECKLOAD-ALL: load i32, i32*
+  ; CHECK-5A2-5B-NOT: load i32, i32*
+  ; CHECK-ALL-NOT: load i32, i32*
+  call void @_Z3bar1A(i32 %19)
+  call void @llvm.invariant.end({}* %7, i64 4, i8* %6)
+  ; CHECK: call {{.*}}@llvm.invariant.end({{.*}}, i64 {{[0-9]+}}, i8*
+  %20 = bitcast %struct.A* %j to i8*
+  call void @llvm.lifetime.end(i64 4, i8* %20) 
+  call void @llvm.invariant.end({}* %2, i64 4, i8* %1)
+  ; CHECK: call {{.*}}@llvm.invariant.end({{.*}}, i64 {{[0-9]+}}, i8*
+  %21 = bitcast %struct.A* %i to i8*
+  call void @llvm.lifetime.end(i64 4, i8* %21) 
+  ret void
+}
+
+declare i32 @_Z3onev()
+declare void @_Z3bar1A(i32)
+declare void @_Z3fooPK1A(%struct.A*)
+declare void @_Z4foo2PK1AS1_(%struct.A*, %struct.A*)
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture readonly, i64, i32, i1)
+declare {}* @llvm.invariant.start(i64, i8* nocapture)
+declare void @llvm.invariant.end({}*, i64, i8* nocapture)
+declare void @llvm.lifetime.start(i64, i8* nocapture)
+declare void @llvm.lifetime.end(i64, i8* nocapture)
+
+define linkonce_odr void @_ZN1AC2Ei(%struct.A* %this, i32 %a) unnamed_addr {
+entry:
+  %this.addr = alloca %struct.A*
+  %a.addr = alloca i32
+  store %struct.A* %this, %struct.A** %this.addr
+  store i32 %a, i32* %a.addr
+  %this1 = load %struct.A*, %struct.A** %this.addr
+  %a2 = getelementptr inbounds %struct.A, %struct.A* %this1, i32 0, i32 0
+  %0 = load i32, i32* %a.addr
+  store i32 %0, i32* %a2
+  ret void
+}