[Proof of concept] Clang lowering: Add 'writeonce' annotations on constant objects.

[lvoufo]

Summary

[No formal review needed at this time.]

[lvoufo]

Generalized generation of 'writeonce' annotations.

[lvoufo]

Bug Fix:

• the inliner and -gvn were removing or ignoring calls to constructors that were prematurely treated as readonly when their arguments were writeonce.
• As result, calls like call void @_Z3bar1A(i32 %agg.tmp.sroa.0.0.copyload) were eventually replaced with call void @_Z3bar1A(i32 undef).
• This is not the case anymore.

This patch uses the @llvm.invariant.start/end intrinsics to either

• mark that writeonce memory locations have been written into and thus can now be treated as readonly, or
• mark that it's okay to write into a writeonce memory location again.

The intrinsics are generated immediately after writing into a given address location, and, when applicable, at the end of a variable's lifetime.

[lvoufo]

Remove duplicate generation of invariant.start intrisic call for writeonce addresses.

[lvoufo]

Bug Fix: Global const object cases work again.

Solution: Teach BasicAA to not treat @llvm.invariant.start/end() intrinsic calls as potentially writing to memory.

[lvoufo]

Remove explicit 'writeonce' annotations; not worth the overhead of keeping them around (e.g. propagation through new AllocaInst's).

[lvoufo]

POC done (based on the sample programs in the design doc).

Moving towards initial patch submission for review:

• Fix unexpected failures in regression tests: 8
• generalize and add new test cases.

[chandlerc]

FYI, if this is something you'd like to start more active code review on, I
would recommend closing this particular entry on Phabricator and creating a
new one with llvm-commits subscribed from the start. Adding a mailing list
doesn't work well with Phabricator sadly. =/ It will also give a good
chance to update the description because I know you've made a lot of
progress based on the design review, etc.

[lvoufo]

Update diff with more visible context (-U999999).

[ * This was submitted in error -- Please ignore this diff *]

include/llvm/IR/GlobalVariable.h

 #include "llvm/IR/OperandTraits.h"
 
 namespace llvm {
 
 class Module;
 class Constant;
 template<typename ValueSubClass, typename ItemParentClass>
   class SymbolTableListTraits;
+class IntrinsicInst;
 
 class GlobalVariable : public GlobalObject, public ilist_node<GlobalVariable> {
   friend class SymbolTableListTraits<GlobalVariable, Module>;
   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

 
 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,

 //===----------------------------------------------------------------------===//
 //                                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);
+
+struct PreservedInvariantInfo {
+  IntrinsicInst *II;
+  Value *Load;
+  PreservedInvariantInfo(): II(nullptr), Load(nullptr) { }
+};
+
+class PreserveInvariantInfo {
+  IntrinsicInst *PreservedII;
+  Value *LoadI;
+  void CheckPreservedInfo();
+public:
+  PreserveInvariantInfo(IntrinsicInst *II, Value *LI)
+  : PreservedII(II), LoadI(LI) {
+    if (PreservedII)
+      CheckPreservedInfo();
+  }
+  ~PreserveInvariantInfo() {
+    if (PreservedII)
+      setInvariantStartInstruction(LoadI, PreservedII);
+  }
+};
+
+void setPreservedInvariantInfo(PreservedInvariantInfo &Preserved,
+                               BasicBlock::iterator &ScanBackwardFrom,
+                               Value *Query, BasicBlock *BB,
+                               bool SkipToInvariantStart = false);
+
 } // End llvm namespace
 
 #endif

lib/Analysis/AliasAnalysis.cpp

ModRefInfo AAResults::getModRefInfo(const StoreInst *S,
   if (Loc.Ptr) {
     // If the store address cannot alias the pointer in question, then the
     // specified memory cannot be modified by the store.
     if (!alias(MemoryLocation::get(S), Loc))
       return MRI_NoModRef;
 
     // If the pointer is a pointer to constant memory, then it could not have
     // been modified by this store.
+    // NOTE: We do not store into written 'writeonce' memory, which means that
+    // the store to a given address always precedes an invariant_start on it.
+    // So, if the address here is written to, then assume that it is not.
+    // FIXME: Handle this better, in combination with
+    // processInvariantIntrisics(), for GVN to skip straight to the store
+    // during memory dependence analysis.
     if (pointsToConstantMemory(Loc))
       return MRI_NoModRef;
   }
 
   // Otherwise, a store just writes.
   return MRI_Mod;
 }
 

lib/Analysis/BasicAliasAnalysis.cpp

/*static*/ const Value *BasicAAResult::DecomposeGEPExpression(
   // If the chain of expressions is too deep, just return early.
   MaxLookupReached = true;
   SearchLimitReached++;
   return V;
 }
 
 /// Returns whether the given pointer value points to memory that is local to
 /// the function, with global constants being considered local to all
-/// functions.
+/// functions. Initialized global writeonces are also considered local to
+/// all functions.
 bool BasicAAResult::pointsToConstantMemory(const MemoryLocation &Loc,
                                            bool OrLocal) {
   assert(Visited.empty() && "Visited must be cleared after use!");
 
   unsigned MaxLookup = 8;
   SmallVector<const Value *, 16> Worklist;
   Worklist.push_back(Loc.Ptr);
   do {
     const Value *V = GetUnderlyingObject(Worklist.pop_back_val(), DL);
     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)) {

 static bool isAssumeIntrinsic(ImmutableCallSite CS) {
   const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction());
   if (II && II->getIntrinsicID() == Intrinsic::assume)
     return true;
 
   return false;
 }
 
+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.
+/// 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(6), cl::Hidden,
+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
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;
+  setPreservedInvariantInfo(Preserved, ScanFrom, StrippedPtr, ScanBB);
+  PreserveInvariantInfo PIO(Preserved.II, Preserved.Load);
+
   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.Load, 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::getPointerDependencyFrom(
   // forwarding, but any mayalias write can be assumed to be noalias.
   // Arguably, this logic should be pushed inside AliasAnalysis itself.
   if (isLoad && QueryInst) {
     LoadInst *LI = dyn_cast<LoadInst>(QueryInst);
     if (LI && LI->getMetadata(LLVMContext::MD_invariant_load) != nullptr)
       isInvariantLoad = true;
   }
 
+  // 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)
+    setPreservedInvariantInfo(Preserved, ScanIt, QueryInst, BB,
+                              /*SkipToInvariantStart =*/ true);
+  PreserveInvariantInfo PIO(Preserved.II, Preserved.Load);
+
   const DataLayout &DL = BB->getModule()->getDataLayout();
 
   // 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);
 

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

 #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(PreservedII->getIntrinsicID() == Intrinsic::invariant_start &&
+         "Preserved instruction must be an invariant_start intrinsic");
+  assert(LoadI && "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, BasicBlock *BB,
+                                     bool SkipToInvariantStart) {
+  if (LoadInst *LI = dyn_cast<LoadInst>(Query)) {
+    Value *I = LI->getPointerOperand()->stripPointerCasts();
+    if (IntrinsicInst *II = llvm::getInvariantStartInstruction(I)) {
+      // NOTE: II's parent block can only either be the same as or contain
+      //       ScanIt's parent block (i.e. BB). When not the same, set
+      //       ScanIt to the begin of BB to skip the backward traversal.
+      if (II->getParent() == ScanBackwardFrom->getParent()) {
+        // If there is anything to scan backward at all, then we must still
+        // be processing BB, and this load no longer points to constant
+        // memory. Record info to preserve before reseting it.
+        Preserved.II = II;
+        Preserved.Load = I;
+        if (SkipToInvariantStart) {
+          ScanBackwardFrom = II;
+          llvm::setInvariantStartInstruction(I, nullptr);
+        }
+      }
+      else if (SkipToInvariantStart)
+        ScanBackwardFrom = BB->begin();
+    }
+  }
+}
+
+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);
+}
+
+// Process @llvm.invariant.start/end intrinsics.
+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;
+}

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);
+
+    // 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
+              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)->getName().compare((*B)->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))
+        // never be inlined. *.invariant.* intrinsics are excepted because
+        // they should processed when inlining other calls.
+        //if (!CS || isa<IntrinsicInst>(I))
+        if (!CS)
+          continue;
+        if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I))
+          if (II->getIntrinsicID() != Intrinsic::invariant_start &&
+              II->getIntrinsicID() != Intrinsic::invariant_end)
             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())
+          if (Callee->isDeclaration() && !isa<IntrinsicInst>(I))
             continue;
         
         CallSites.push_back(std::make_pair(CS, -1));
       }
   }
 
   DEBUG(dbgs() << ": " << CallSites.size() << " call sites.\n");
 
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;
-      
+      if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
+        if (processInvariantIntrinsics(II))
+          continue;
+      }
+
       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/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 it's *.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/EarlyCSE.cpp

for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
     // they're marked as such to ensure preservation of control dependencies),
     // and this pass will not disturb any of the assumption's control
     // dependencies.
     if (match(Inst, m_Intrinsic<Intrinsic::assume>())) {
       DEBUG(dbgs() << "EarlyCSE skipping assumption: " << *Inst << '\n');
       continue;
     }
 
+    // TODO: Not needed?
+    if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
+      if (processInvariantIntrinsics(II))
+        continue;
+    }
+
     // If the instruction can be simplified (e.g. X+0 = X) then replace it with
     // its simpler value.
     if (Value *V = SimplifyInstruction(Inst, DL, &TLI, &DT, &AC)) {
       DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << "  to: " << *V << '\n');
       Inst->replaceAllUsesWith(V);
       Inst->eraseFromParent();
       Changed = true;
       ++NumSimplify;

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())