diff --git a/linux-x64/clang/include/llvm/Analysis/AliasSetTracker.h b/linux-x64/clang/include/llvm/Analysis/AliasSetTracker.h
index 0e6d229..cf4981d 100644
--- a/linux-x64/clang/include/llvm/Analysis/AliasSetTracker.h
+++ b/linux-x64/clang/include/llvm/Analysis/AliasSetTracker.h
@@ -52,9 +52,13 @@
     PointerRec **PrevInList = nullptr;
     PointerRec *NextInList = nullptr;
     AliasSet *AS = nullptr;
-    LocationSize Size = 0;
+    LocationSize Size = LocationSize::mapEmpty();
     AAMDNodes AAInfo;
 
+    // Whether the size for this record has been set at all. This makes no
+    // guarantees about the size being known.
+    bool isSizeSet() const { return Size != LocationSize::mapEmpty(); }
+
   public:
     PointerRec(Value *V)
       : Val(V), AAInfo(DenseMapInfo<AAMDNodes>::getEmptyKey()) {}
@@ -71,9 +75,10 @@
 
     bool updateSizeAndAAInfo(LocationSize NewSize, const AAMDNodes &NewAAInfo) {
       bool SizeChanged = false;
-      if (NewSize > Size) {
-        Size = NewSize;
-        SizeChanged = true;
+      if (NewSize != Size) {
+        LocationSize OldSize = Size;
+        Size = isSizeSet() ? Size.unionWith(NewSize) : NewSize;
+        SizeChanged = OldSize != Size;
       }
 
       if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey())
@@ -91,7 +96,10 @@
       return SizeChanged;
     }
 
-    LocationSize getSize() const { return Size; }
+    LocationSize getSize() const {
+      assert(isSizeSet() && "Getting an unset size!");
+      return Size;
+    }
 
     /// Return the AAInfo, or null if there is no information or conflicting
     /// information.
@@ -175,9 +183,6 @@
   };
   unsigned Alias : 1;
 
-  /// True if this alias set contains volatile loads or stores.
-  unsigned Volatile : 1;
-
   unsigned SetSize = 0;
 
   void addRef() { ++RefCount; }
@@ -203,9 +208,6 @@
   bool isMustAlias() const { return Alias == SetMustAlias; }
   bool isMayAlias()  const { return Alias == SetMayAlias; }
 
-  /// Return true if this alias set contains volatile loads or stores.
-  bool isVolatile() const { return Volatile; }
-
   /// Return true if this alias set should be ignored as part of the
   /// AliasSetTracker object.
   bool isForwardingAliasSet() const { return Forward; }
@@ -226,17 +228,7 @@
 
   /// If this alias set is known to contain a single instruction and *only* a
   /// single unique instruction, return it.  Otherwise, return nullptr.
-  Instruction* getUniqueInstruction() {
-    if (size() != 0)
-      // Can't track source of pointer, might be many instruction
-      return nullptr;
-    if (AliasAny)
-      // May have collapses alias set
-      return nullptr;
-    if (1 != UnknownInsts.size())
-      return nullptr;
-    return cast<Instruction>(UnknownInsts[0]);
-  }
+  Instruction* getUniqueInstruction();
 
   void print(raw_ostream &OS) const;
   void dump() const;
@@ -278,7 +270,7 @@
   // Can only be created by AliasSetTracker.
   AliasSet()
       : PtrListEnd(&PtrList), RefCount(0),  AliasAny(false), Access(NoAccess),
-        Alias(SetMustAlias), Volatile(false) {}
+        Alias(SetMustAlias) {}
 
   PointerRec *getSomePointer() const {
     return PtrList;
@@ -317,8 +309,6 @@
       dropRef(AST);
   }
 
-  void setVolatile() { Volatile = true; }
-
 public:
   /// Return true if the specified pointer "may" (or must) alias one of the
   /// members in the set.
@@ -393,19 +383,11 @@
   /// Return the alias sets that are active.
   const ilist<AliasSet> &getAliasSets() const { return AliasSets; }
 
-  /// Return the alias set that the specified pointer lives in. If the New
-  /// argument is non-null, this method sets the value to true if a new alias
-  /// set is created to contain the pointer (because the pointer didn't alias
-  /// anything).
-  AliasSet &getAliasSetForPointer(Value *P, LocationSize Size,
-                                  const AAMDNodes &AAInfo);
-
-  /// Return the alias set containing the location specified if one exists,
-  /// otherwise return null.
-  AliasSet *getAliasSetForPointerIfExists(const Value *P, LocationSize Size,
-                                          const AAMDNodes &AAInfo) {
-    return mergeAliasSetsForPointer(P, Size, AAInfo);
-  }
+  /// Return the alias set which contains the specified memory location.  If
+  /// the memory location aliases two or more existing alias sets, will have
+  /// the effect of merging those alias sets before the single resulting alias
+  /// set is returned.
+  AliasSet &getAliasSetFor(const MemoryLocation &MemLoc);
 
   /// Return true if the specified instruction "may" (or must) alias one of the
   /// members in any of the sets.
@@ -461,6 +443,10 @@
 
   AliasSet &addPointer(Value *P, LocationSize Size, const AAMDNodes &AAInfo,
                        AliasSet::AccessLattice E);
+  AliasSet &addPointer(MemoryLocation Loc,
+                       AliasSet::AccessLattice E) {
+    return addPointer(const_cast<Value*>(Loc.Ptr), Loc.Size, Loc.AATags, E);
+  }
   AliasSet *mergeAliasSetsForPointer(const Value *Ptr, LocationSize Size,
                                      const AAMDNodes &AAInfo);
 
diff --git a/linux-x64/clang/include/llvm/Analysis/CFGPrinter.h b/linux-x64/clang/include/llvm/Analysis/CFGPrinter.h
index 5786769..a4b642b 100644
--- a/linux-x64/clang/include/llvm/Analysis/CFGPrinter.h
+++ b/linux-x64/clang/include/llvm/Analysis/CFGPrinter.h
@@ -172,8 +172,7 @@
 
     // Prepend a 'W' to indicate that this is a weight rather than the actual
     // profile count (due to scaling).
-    Twine Attrs = "label=\"W:" + Twine(Weight->getZExtValue()) + "\"";
-    return Attrs.str();
+    return ("label=\"W:" + Twine(Weight->getZExtValue()) + "\"").str();
   }
 };
 } // End llvm namespace
diff --git a/linux-x64/clang/include/llvm/Analysis/CGSCCPassManager.h b/linux-x64/clang/include/llvm/Analysis/CGSCCPassManager.h
index 5e83ea2..f150064 100644
--- a/linux-x64/clang/include/llvm/Analysis/CGSCCPassManager.h
+++ b/linux-x64/clang/include/llvm/Analysis/CGSCCPassManager.h
@@ -364,6 +364,10 @@
                             InvalidSCCSet,       nullptr,   nullptr,
                             InlinedInternalEdges};
 
+    // Request PassInstrumentation from analysis manager, will use it to run
+    // instrumenting callbacks for the passes later.
+    PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);
+
     PreservedAnalyses PA = PreservedAnalyses::all();
     CG.buildRefSCCs();
     for (auto RCI = CG.postorder_ref_scc_begin(),
@@ -428,8 +432,17 @@
 
             UR.UpdatedRC = nullptr;
             UR.UpdatedC = nullptr;
+
+            // Check the PassInstrumentation's BeforePass callbacks before
+            // running the pass, skip its execution completely if asked to
+            // (callback returns false).
+            if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
+              continue;
+
             PreservedAnalyses PassPA = Pass.run(*C, CGAM, CG, UR);
 
+            PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);
+
             // Update the SCC and RefSCC if necessary.
             C = UR.UpdatedC ? UR.UpdatedC : C;
             RC = UR.UpdatedRC ? UR.UpdatedRC : RC;
@@ -615,12 +628,20 @@
       if (CG.lookupSCC(*N) != CurrentC)
         continue;
 
-      PreservedAnalyses PassPA = Pass.run(N->getFunction(), FAM);
+      Function &F = N->getFunction();
+
+      PassInstrumentation PI = FAM.getResult<PassInstrumentationAnalysis>(F);
+      if (!PI.runBeforePass<Function>(Pass, F))
+        continue;
+
+      PreservedAnalyses PassPA = Pass.run(F, FAM);
+
+      PI.runAfterPass<Function>(Pass, F);
 
       // We know that the function pass couldn't have invalidated any other
       // function's analyses (that's the contract of a function pass), so
       // directly handle the function analysis manager's invalidation here.
-      FAM.invalidate(N->getFunction(), PassPA);
+      FAM.invalidate(F, PassPA);
 
       // Then intersect the preserved set so that invalidation of module
       // analyses will eventually occur when the module pass completes.
@@ -690,6 +711,8 @@
   PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM,
                         LazyCallGraph &CG, CGSCCUpdateResult &UR) {
     PreservedAnalyses PA = PreservedAnalyses::all();
+    PassInstrumentation PI =
+        AM.getResult<PassInstrumentationAnalysis>(InitialC, CG);
 
     // The SCC may be refined while we are running passes over it, so set up
     // a pointer that we can update.
@@ -733,8 +756,14 @@
     auto CallCounts = ScanSCC(*C, CallHandles);
 
     for (int Iteration = 0;; ++Iteration) {
+
+      if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
+        continue;
+
       PreservedAnalyses PassPA = Pass.run(*C, AM, CG, UR);
 
+      PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);
+
       // If the SCC structure has changed, bail immediately and let the outer
       // CGSCC layer handle any iteration to reflect the refined structure.
       if (UR.UpdatedC && UR.UpdatedC != C) {
diff --git a/linux-x64/clang/include/llvm/Analysis/GuardUtils.h b/linux-x64/clang/include/llvm/Analysis/GuardUtils.h
new file mode 100644
index 0000000..3b151ee
--- /dev/null
+++ b/linux-x64/clang/include/llvm/Analysis/GuardUtils.h
@@ -0,0 +1,26 @@
+//===-- GuardUtils.h - Utils for work with guards ---------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// Utils that are used to perform analyzes related to guards and their
+// conditions.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_GUARDUTILS_H
+#define LLVM_ANALYSIS_GUARDUTILS_H
+
+namespace llvm {
+
+class User;
+
+/// Returns true iff \p U has semantics of a guard.
+bool isGuard(const User *U);
+
+} // llvm
+
+#endif // LLVM_ANALYSIS_GUARDUTILS_H
+
diff --git a/linux-x64/clang/include/llvm/Analysis/IVDescriptors.h b/linux-x64/clang/include/llvm/Analysis/IVDescriptors.h
new file mode 100644
index 0000000..d1d7e5e
--- /dev/null
+++ b/linux-x64/clang/include/llvm/Analysis/IVDescriptors.h
@@ -0,0 +1,352 @@
+//===- llvm/Analysis/IVDescriptors.h - IndVar Descriptors -------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file "describes" induction and recurrence variables.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_IVDESCRIPTORS_H
+#define LLVM_ANALYSIS_IVDESCRIPTORS_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/DemandedBits.h"
+#include "llvm/Analysis/EHPersonalities.h"
+#include "llvm/Analysis/MustExecute.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/InstrTypes.h"
+#include "llvm/IR/Operator.h"
+#include "llvm/IR/ValueHandle.h"
+#include "llvm/Support/Casting.h"
+
+namespace llvm {
+
+class AliasSet;
+class AliasSetTracker;
+class BasicBlock;
+class DataLayout;
+class Loop;
+class LoopInfo;
+class OptimizationRemarkEmitter;
+class PredicatedScalarEvolution;
+class PredIteratorCache;
+class ScalarEvolution;
+class SCEV;
+class TargetLibraryInfo;
+class TargetTransformInfo;
+
+/// The RecurrenceDescriptor is used to identify recurrences variables in a
+/// loop. Reduction is a special case of recurrence that has uses of the
+/// recurrence variable outside the loop. The method isReductionPHI identifies
+/// reductions that are basic recurrences.
+///
+/// Basic recurrences are defined as the summation, product, OR, AND, XOR, min,
+/// or max of a set of terms. For example: for(i=0; i<n; i++) { total +=
+/// array[i]; } is a summation of array elements. Basic recurrences are a
+/// special case of chains of recurrences (CR). See ScalarEvolution for CR
+/// references.
+
+/// This struct holds information about recurrence variables.
+class RecurrenceDescriptor {
+public:
+  /// This enum represents the kinds of recurrences that we support.
+  enum RecurrenceKind {
+    RK_NoRecurrence,  ///< Not a recurrence.
+    RK_IntegerAdd,    ///< Sum of integers.
+    RK_IntegerMult,   ///< Product of integers.
+    RK_IntegerOr,     ///< Bitwise or logical OR of numbers.
+    RK_IntegerAnd,    ///< Bitwise or logical AND of numbers.
+    RK_IntegerXor,    ///< Bitwise or logical XOR of numbers.
+    RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()).
+    RK_FloatAdd,      ///< Sum of floats.
+    RK_FloatMult,     ///< Product of floats.
+    RK_FloatMinMax    ///< Min/max implemented in terms of select(cmp()).
+  };
+
+  // This enum represents the kind of minmax recurrence.
+  enum MinMaxRecurrenceKind {
+    MRK_Invalid,
+    MRK_UIntMin,
+    MRK_UIntMax,
+    MRK_SIntMin,
+    MRK_SIntMax,
+    MRK_FloatMin,
+    MRK_FloatMax
+  };
+
+  RecurrenceDescriptor() = default;
+
+  RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K,
+                       MinMaxRecurrenceKind MK, Instruction *UAI, Type *RT,
+                       bool Signed, SmallPtrSetImpl<Instruction *> &CI)
+      : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK),
+        UnsafeAlgebraInst(UAI), RecurrenceType(RT), IsSigned(Signed) {
+    CastInsts.insert(CI.begin(), CI.end());
+  }
+
+  /// This POD struct holds information about a potential recurrence operation.
+  class InstDesc {
+  public:
+    InstDesc(bool IsRecur, Instruction *I, Instruction *UAI = nullptr)
+        : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid),
+          UnsafeAlgebraInst(UAI) {}
+
+    InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI = nullptr)
+        : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K),
+          UnsafeAlgebraInst(UAI) {}
+
+    bool isRecurrence() { return IsRecurrence; }
+
+    bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
+
+    Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
+
+    MinMaxRecurrenceKind getMinMaxKind() { return MinMaxKind; }
+
+    Instruction *getPatternInst() { return PatternLastInst; }
+
+  private:
+    // Is this instruction a recurrence candidate.
+    bool IsRecurrence;
+    // The last instruction in a min/max pattern (select of the select(icmp())
+    // pattern), or the current recurrence instruction otherwise.
+    Instruction *PatternLastInst;
+    // If this is a min/max pattern the comparison predicate.
+    MinMaxRecurrenceKind MinMaxKind;
+    // Recurrence has unsafe algebra.
+    Instruction *UnsafeAlgebraInst;
+  };
+
+  /// Returns a struct describing if the instruction 'I' can be a recurrence
+  /// variable of type 'Kind'. If the recurrence is a min/max pattern of
+  /// select(icmp()) this function advances the instruction pointer 'I' from the
+  /// compare instruction to the select instruction and stores this pointer in
+  /// 'PatternLastInst' member of the returned struct.
+  static InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
+                                    InstDesc &Prev, bool HasFunNoNaNAttr);
+
+  /// Returns true if instruction I has multiple uses in Insts
+  static bool hasMultipleUsesOf(Instruction *I,
+                                SmallPtrSetImpl<Instruction *> &Insts);
+
+  /// Returns true if all uses of the instruction I is within the Set.
+  static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set);
+
+  /// Returns a struct describing if the instruction if the instruction is a
+  /// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y)
+  /// or max(X, Y).
+  static InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev);
+
+  /// Returns identity corresponding to the RecurrenceKind.
+  static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp);
+
+  /// Returns the opcode of binary operation corresponding to the
+  /// RecurrenceKind.
+  static unsigned getRecurrenceBinOp(RecurrenceKind Kind);
+
+  /// Returns true if Phi is a reduction of type Kind and adds it to the
+  /// RecurrenceDescriptor. If either \p DB is non-null or \p AC and \p DT are
+  /// non-null, the minimal bit width needed to compute the reduction will be
+  /// computed.
+  static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop,
+                              bool HasFunNoNaNAttr,
+                              RecurrenceDescriptor &RedDes,
+                              DemandedBits *DB = nullptr,
+                              AssumptionCache *AC = nullptr,
+                              DominatorTree *DT = nullptr);
+
+  /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor
+  /// is returned in RedDes. If either \p DB is non-null or \p AC and \p DT are
+  /// non-null, the minimal bit width needed to compute the reduction will be
+  /// computed.
+  static bool isReductionPHI(PHINode *Phi, Loop *TheLoop,
+                             RecurrenceDescriptor &RedDes,
+                             DemandedBits *DB = nullptr,
+                             AssumptionCache *AC = nullptr,
+                             DominatorTree *DT = nullptr);
+
+  /// Returns true if Phi is a first-order recurrence. A first-order recurrence
+  /// is a non-reduction recurrence relation in which the value of the
+  /// recurrence in the current loop iteration equals a value defined in the
+  /// previous iteration. \p SinkAfter includes pairs of instructions where the
+  /// first will be rescheduled to appear after the second if/when the loop is
+  /// vectorized. It may be augmented with additional pairs if needed in order
+  /// to handle Phi as a first-order recurrence.
+  static bool
+  isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop,
+                         DenseMap<Instruction *, Instruction *> &SinkAfter,
+                         DominatorTree *DT);
+
+  RecurrenceKind getRecurrenceKind() { return Kind; }
+
+  MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; }
+
+  TrackingVH<Value> getRecurrenceStartValue() { return StartValue; }
+
+  Instruction *getLoopExitInstr() { return LoopExitInstr; }
+
+  /// Returns true if the recurrence has unsafe algebra which requires a relaxed
+  /// floating-point model.
+  bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
+
+  /// Returns first unsafe algebra instruction in the PHI node's use-chain.
+  Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
+
+  /// Returns true if the recurrence kind is an integer kind.
+  static bool isIntegerRecurrenceKind(RecurrenceKind Kind);
+
+  /// Returns true if the recurrence kind is a floating point kind.
+  static bool isFloatingPointRecurrenceKind(RecurrenceKind Kind);
+
+  /// Returns true if the recurrence kind is an arithmetic kind.
+  static bool isArithmeticRecurrenceKind(RecurrenceKind Kind);
+
+  /// Returns the type of the recurrence. This type can be narrower than the
+  /// actual type of the Phi if the recurrence has been type-promoted.
+  Type *getRecurrenceType() { return RecurrenceType; }
+
+  /// Returns a reference to the instructions used for type-promoting the
+  /// recurrence.
+  SmallPtrSet<Instruction *, 8> &getCastInsts() { return CastInsts; }
+
+  /// Returns true if all source operands of the recurrence are SExtInsts.
+  bool isSigned() { return IsSigned; }
+
+private:
+  // The starting value of the recurrence.
+  // It does not have to be zero!
+  TrackingVH<Value> StartValue;
+  // The instruction who's value is used outside the loop.
+  Instruction *LoopExitInstr = nullptr;
+  // The kind of the recurrence.
+  RecurrenceKind Kind = RK_NoRecurrence;
+  // If this a min/max recurrence the kind of recurrence.
+  MinMaxRecurrenceKind MinMaxKind = MRK_Invalid;
+  // First occurrence of unasfe algebra in the PHI's use-chain.
+  Instruction *UnsafeAlgebraInst = nullptr;
+  // The type of the recurrence.
+  Type *RecurrenceType = nullptr;
+  // True if all source operands of the recurrence are SExtInsts.
+  bool IsSigned = false;
+  // Instructions used for type-promoting the recurrence.
+  SmallPtrSet<Instruction *, 8> CastInsts;
+};
+
+/// A struct for saving information about induction variables.
+class InductionDescriptor {
+public:
+  /// This enum represents the kinds of inductions that we support.
+  enum InductionKind {
+    IK_NoInduction,  ///< Not an induction variable.
+    IK_IntInduction, ///< Integer induction variable. Step = C.
+    IK_PtrInduction, ///< Pointer induction var. Step = C / sizeof(elem).
+    IK_FpInduction   ///< Floating point induction variable.
+  };
+
+public:
+  /// Default constructor - creates an invalid induction.
+  InductionDescriptor() = default;
+
+  /// Get the consecutive direction. Returns:
+  ///   0 - unknown or non-consecutive.
+  ///   1 - consecutive and increasing.
+  ///  -1 - consecutive and decreasing.
+  int getConsecutiveDirection() const;
+
+  Value *getStartValue() const { return StartValue; }
+  InductionKind getKind() const { return IK; }
+  const SCEV *getStep() const { return Step; }
+  BinaryOperator *getInductionBinOp() const { return InductionBinOp; }
+  ConstantInt *getConstIntStepValue() const;
+
+  /// Returns true if \p Phi is an induction in the loop \p L. If \p Phi is an
+  /// induction, the induction descriptor \p D will contain the data describing
+  /// this induction. If by some other means the caller has a better SCEV
+  /// expression for \p Phi than the one returned by the ScalarEvolution
+  /// analysis, it can be passed through \p Expr. If the def-use chain
+  /// associated with the phi includes casts (that we know we can ignore
+  /// under proper runtime checks), they are passed through \p CastsToIgnore.
+  static bool
+  isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE,
+                 InductionDescriptor &D, const SCEV *Expr = nullptr,
+                 SmallVectorImpl<Instruction *> *CastsToIgnore = nullptr);
+
+  /// Returns true if \p Phi is a floating point induction in the loop \p L.
+  /// If \p Phi is an induction, the induction descriptor \p D will contain
+  /// the data describing this induction.
+  static bool isFPInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE,
+                               InductionDescriptor &D);
+
+  /// Returns true if \p Phi is a loop \p L induction, in the context associated
+  /// with the run-time predicate of PSE. If \p Assume is true, this can add
+  /// further SCEV predicates to \p PSE in order to prove that \p Phi is an
+  /// induction.
+  /// If \p Phi is an induction, \p D will contain the data describing this
+  /// induction.
+  static bool isInductionPHI(PHINode *Phi, const Loop *L,
+                             PredicatedScalarEvolution &PSE,
+                             InductionDescriptor &D, bool Assume = false);
+
+  /// Returns true if the induction type is FP and the binary operator does
+  /// not have the "fast-math" property. Such operation requires a relaxed FP
+  /// mode.
+  bool hasUnsafeAlgebra() {
+    return InductionBinOp && !cast<FPMathOperator>(InductionBinOp)->isFast();
+  }
+
+  /// Returns induction operator that does not have "fast-math" property
+  /// and requires FP unsafe mode.
+  Instruction *getUnsafeAlgebraInst() {
+    if (!InductionBinOp || cast<FPMathOperator>(InductionBinOp)->isFast())
+      return nullptr;
+    return InductionBinOp;
+  }
+
+  /// Returns binary opcode of the induction operator.
+  Instruction::BinaryOps getInductionOpcode() const {
+    return InductionBinOp ? InductionBinOp->getOpcode()
+                          : Instruction::BinaryOpsEnd;
+  }
+
+  /// Returns a reference to the type cast instructions in the induction
+  /// update chain, that are redundant when guarded with a runtime
+  /// SCEV overflow check.
+  const SmallVectorImpl<Instruction *> &getCastInsts() const {
+    return RedundantCasts;
+  }
+
+private:
+  /// Private constructor - used by \c isInductionPHI.
+  InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step,
+                      BinaryOperator *InductionBinOp = nullptr,
+                      SmallVectorImpl<Instruction *> *Casts = nullptr);
+
+  /// Start value.
+  TrackingVH<Value> StartValue;
+  /// Induction kind.
+  InductionKind IK = IK_NoInduction;
+  /// Step value.
+  const SCEV *Step = nullptr;
+  // Instruction that advances induction variable.
+  BinaryOperator *InductionBinOp = nullptr;
+  // Instructions used for type-casts of the induction variable,
+  // that are redundant when guarded with a runtime SCEV overflow check.
+  SmallVector<Instruction *, 2> RedundantCasts;
+};
+
+} // end namespace llvm
+
+#endif // LLVM_ANALYSIS_IVDESCRIPTORS_H
diff --git a/linux-x64/clang/include/llvm/Analysis/IndirectCallSiteVisitor.h b/linux-x64/clang/include/llvm/Analysis/IndirectCallSiteVisitor.h
index dde56a1..a30b59f 100644
--- a/linux-x64/clang/include/llvm/Analysis/IndirectCallSiteVisitor.h
+++ b/linux-x64/clang/include/llvm/Analysis/IndirectCallSiteVisitor.h
@@ -10,6 +10,9 @@
 // This file implements defines a visitor class and a helper function that find
 // all indirect call-sites in a function.
 
+#ifndef LLVM_ANALYSIS_INDIRECTCALLSITEVISITOR_H
+#define LLVM_ANALYSIS_INDIRECTCALLSITEVISITOR_H
+
 #include "llvm/IR/InstVisitor.h"
 #include <vector>
 
@@ -33,3 +36,5 @@
   return ICV.IndirectCallInsts;
 }
 }
+
+#endif
diff --git a/linux-x64/clang/include/llvm/Analysis/InstructionPrecedenceTracking.h b/linux-x64/clang/include/llvm/Analysis/InstructionPrecedenceTracking.h
new file mode 100644
index 0000000..5178a33
--- /dev/null
+++ b/linux-x64/clang/include/llvm/Analysis/InstructionPrecedenceTracking.h
@@ -0,0 +1,119 @@
+//===-- InstructionPrecedenceTracking.h -------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// Implements a class that is able to define some instructions as "special"
+// (e.g. as having implicit control flow, or writing memory, or having another
+// interesting property) and then efficiently answers queries of the types:
+// 1. Are there any special instructions in the block of interest?
+// 2. Return first of the special instructions in the given block;
+// 3. Check if the given instruction is preceeded by the first special
+//    instruction in the same block.
+// The class provides caching that allows to answer these queries quickly. The
+// user must make sure that the cached data is invalidated properly whenever
+// a content of some tracked block is changed.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H
+#define LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H
+
+#include "llvm/IR/Dominators.h"
+#include "llvm/Analysis/OrderedInstructions.h"
+
+namespace llvm {
+
+class InstructionPrecedenceTracking {
+  // Maps a block to the topmost special instruction in it. If the value is
+  // nullptr, it means that it is known that this block does not contain any
+  // special instructions.
+  DenseMap<const BasicBlock *, const Instruction *> FirstSpecialInsts;
+  // Allows to answer queries about precedence of instructions within one block.
+  OrderedInstructions OI;
+
+  // Fills information about the given block's special instructions.
+  void fill(const BasicBlock *BB);
+
+#ifndef NDEBUG
+  /// Asserts that the cached info for \p BB is up-to-date. This helps to catch
+  /// the usage error of accessing a block without properly invalidating after a
+  /// previous transform.
+  void validate(const BasicBlock *BB) const;
+
+  /// Asserts whether or not the contents of this tracking is up-to-date. This
+  /// helps to catch the usage error of accessing a block without properly
+  /// invalidating after a previous transform.
+  void validateAll() const;
+#endif
+
+protected:
+  InstructionPrecedenceTracking(DominatorTree *DT)
+      : OI(OrderedInstructions(DT)) {}
+
+  /// Returns the topmost special instruction from the block \p BB. Returns
+  /// nullptr if there is no special instructions in the block.
+  const Instruction *getFirstSpecialInstruction(const BasicBlock *BB);
+
+  /// Returns true iff at least one instruction from the basic block \p BB is
+  /// special.
+  bool hasSpecialInstructions(const BasicBlock *BB);
+
+  /// Returns true iff the first special instruction of \p Insn's block exists
+  /// and dominates \p Insn.
+  bool isPreceededBySpecialInstruction(const Instruction *Insn);
+
+  /// A predicate that defines whether or not the instruction \p Insn is
+  /// considered special and needs to be tracked. Implementing this method in
+  /// children classes allows to implement tracking of implicit control flow,
+  /// memory writing instructions or any other kinds of instructions we might
+  /// be interested in.
+  virtual bool isSpecialInstruction(const Instruction *Insn) const = 0;
+
+  virtual ~InstructionPrecedenceTracking() = default;
+
+public:
+  /// Clears cached information about this particular block.
+  void invalidateBlock(const BasicBlock *BB);
+
+  /// Invalidates all information from this tracking.
+  void clear();
+};
+
+/// This class allows to keep track on instructions with implicit control flow.
+/// These are instructions that may not pass execution to their successors. For
+/// example, throwing calls and guards do not always do this. If we need to know
+/// for sure that some instruction is guaranteed to execute if the given block
+/// is reached, then we need to make sure that there is no implicit control flow
+/// instruction (ICFI) preceeding it. For example, this check is required if we
+/// perform PRE moving non-speculable instruction to other place.
+class ImplicitControlFlowTracking : public InstructionPrecedenceTracking {
+public:
+  ImplicitControlFlowTracking(DominatorTree *DT)
+      : InstructionPrecedenceTracking(DT) {}
+
+  /// Returns the topmost instruction with implicit control flow from the given
+  /// basic block. Returns nullptr if there is no such instructions in the block.
+  const Instruction *getFirstICFI(const BasicBlock *BB) {
+    return getFirstSpecialInstruction(BB);
+  }
+
+  /// Returns true if at least one instruction from the given basic block has
+  /// implicit control flow.
+  bool hasICF(const BasicBlock *BB) {
+    return hasSpecialInstructions(BB);
+  }
+
+  /// Returns true if the first ICFI of Insn's block exists and dominates Insn.
+  bool isDominatedByICFIFromSameBlock(const Instruction *Insn) {
+    return isPreceededBySpecialInstruction(Insn);
+  }
+
+  virtual bool isSpecialInstruction(const Instruction *Insn) const;
+};
+
+} // llvm
+
+#endif // LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H
diff --git a/linux-x64/clang/include/llvm/Analysis/InstructionSimplify.h b/linux-x64/clang/include/llvm/Analysis/InstructionSimplify.h
index 4f896bd..6662e91 100644
--- a/linux-x64/clang/include/llvm/Analysis/InstructionSimplify.h
+++ b/linux-x64/clang/include/llvm/Analysis/InstructionSimplify.h
@@ -32,6 +32,8 @@
 #ifndef LLVM_ANALYSIS_INSTRUCTIONSIMPLIFY_H
 #define LLVM_ANALYSIS_INSTRUCTIONSIMPLIFY_H
 
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Operator.h"
 #include "llvm/IR/User.h"
 
 namespace llvm {
@@ -40,7 +42,6 @@
 template <class T> class ArrayRef;
 class AssumptionCache;
 class DominatorTree;
-class Instruction;
 class ImmutableCallSite;
 class DataLayout;
 class FastMathFlags;
@@ -50,6 +51,41 @@
 class TargetLibraryInfo;
 class Type;
 class Value;
+class MDNode;
+class BinaryOperator;
+
+/// InstrInfoQuery provides an interface to query additional information for
+/// instructions like metadata or keywords like nsw, which provides conservative
+/// results if the users specified it is safe to use.
+struct InstrInfoQuery {
+  InstrInfoQuery(bool UMD) : UseInstrInfo(UMD) {}
+  InstrInfoQuery() : UseInstrInfo(true) {}
+  bool UseInstrInfo = true;
+
+  MDNode *getMetadata(const Instruction *I, unsigned KindID) const {
+    if (UseInstrInfo)
+      return I->getMetadata(KindID);
+    return nullptr;
+  }
+
+  template <class InstT> bool hasNoUnsignedWrap(const InstT *Op) const {
+    if (UseInstrInfo)
+      return Op->hasNoUnsignedWrap();
+    return false;
+  }
+
+  template <class InstT> bool hasNoSignedWrap(const InstT *Op) const {
+    if (UseInstrInfo)
+      return Op->hasNoSignedWrap();
+    return false;
+  }
+
+  bool isExact(const BinaryOperator *Op) const {
+    if (UseInstrInfo && isa<PossiblyExactOperator>(Op))
+      return cast<PossiblyExactOperator>(Op)->isExact();
+    return false;
+  }
+};
 
 struct SimplifyQuery {
   const DataLayout &DL;
@@ -58,14 +94,19 @@
   AssumptionCache *AC = nullptr;
   const Instruction *CxtI = nullptr;
 
+  // Wrapper to query additional information for instructions like metadata or
+  // keywords like nsw, which provides conservative results if those cannot
+  // be safely used.
+  const InstrInfoQuery IIQ;
+
   SimplifyQuery(const DataLayout &DL, const Instruction *CXTI = nullptr)
       : DL(DL), CxtI(CXTI) {}
 
   SimplifyQuery(const DataLayout &DL, const TargetLibraryInfo *TLI,
                 const DominatorTree *DT = nullptr,
                 AssumptionCache *AC = nullptr,
-                const Instruction *CXTI = nullptr)
-      : DL(DL), TLI(TLI), DT(DT), AC(AC), CxtI(CXTI) {}
+                const Instruction *CXTI = nullptr, bool UseInstrInfo = true)
+      : DL(DL), TLI(TLI), DT(DT), AC(AC), CxtI(CXTI), IIQ(UseInstrInfo) {}
   SimplifyQuery getWithInstruction(Instruction *I) const {
     SimplifyQuery Copy(*this);
     Copy.CxtI = I;
diff --git a/linux-x64/clang/include/llvm/Analysis/IteratedDominanceFrontier.h b/linux-x64/clang/include/llvm/Analysis/IteratedDominanceFrontier.h
index 6b19507..fdebb1b 100644
--- a/linux-x64/clang/include/llvm/Analysis/IteratedDominanceFrontier.h
+++ b/linux-x64/clang/include/llvm/Analysis/IteratedDominanceFrontier.h
@@ -28,6 +28,7 @@
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/CFGDiff.h"
 #include "llvm/IR/Dominators.h"
 
 namespace llvm {
@@ -45,17 +46,21 @@
 template <class NodeTy, bool IsPostDom>
 class IDFCalculator {
  public:
-  IDFCalculator(DominatorTreeBase<BasicBlock, IsPostDom> &DT)
-      : DT(DT), useLiveIn(false) {}
+   IDFCalculator(DominatorTreeBase<BasicBlock, IsPostDom> &DT)
+       : DT(DT), GD(nullptr), useLiveIn(false) {}
 
-  /// Give the IDF calculator the set of blocks in which the value is
-  /// defined.  This is equivalent to the set of starting blocks it should be
-  /// calculating the IDF for (though later gets pruned based on liveness).
-  ///
-  /// Note: This set *must* live for the entire lifetime of the IDF calculator.
-  void setDefiningBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) {
-    DefBlocks = &Blocks;
-  }
+   IDFCalculator(DominatorTreeBase<BasicBlock, IsPostDom> &DT,
+                 const GraphDiff<BasicBlock *, IsPostDom> *GD)
+       : DT(DT), GD(GD), useLiveIn(false) {}
+
+   /// Give the IDF calculator the set of blocks in which the value is
+   /// defined.  This is equivalent to the set of starting blocks it should be
+   /// calculating the IDF for (though later gets pruned based on liveness).
+   ///
+   /// Note: This set *must* live for the entire lifetime of the IDF calculator.
+   void setDefiningBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) {
+     DefBlocks = &Blocks;
+   }
 
   /// Give the IDF calculator the set of blocks in which the value is
   /// live on entry to the block.   This is used to prune the IDF calculation to
@@ -85,6 +90,7 @@
 
 private:
  DominatorTreeBase<BasicBlock, IsPostDom> &DT;
+ const GraphDiff<BasicBlock *, IsPostDom> *GD;
  bool useLiveIn;
  const SmallPtrSetImpl<BasicBlock *> *LiveInBlocks;
  const SmallPtrSetImpl<BasicBlock *> *DefBlocks;
diff --git a/linux-x64/clang/include/llvm/Analysis/DivergenceAnalysis.h b/linux-x64/clang/include/llvm/Analysis/LegacyDivergenceAnalysis.h
similarity index 72%
rename from linux-x64/clang/include/llvm/Analysis/DivergenceAnalysis.h
rename to linux-x64/clang/include/llvm/Analysis/LegacyDivergenceAnalysis.h
index 328c864..173ca28 100644
--- a/linux-x64/clang/include/llvm/Analysis/DivergenceAnalysis.h
+++ b/linux-x64/clang/include/llvm/Analysis/LegacyDivergenceAnalysis.h
@@ -1,4 +1,4 @@
-//===- llvm/Analysis/DivergenceAnalysis.h - Divergence Analysis -*- C++ -*-===//
+//===- llvm/Analysis/LegacyDivergenceAnalysis.h - KernelDivergence Analysis -*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -7,14 +7,14 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// The divergence analysis is an LLVM pass which can be used to find out
-// if a branch instruction in a GPU program is divergent or not. It can help
+// The kernel divergence analysis is an LLVM pass which can be used to find out
+// if a branch instruction in a GPU program (kernel) is divergent or not. It can help
 // branch optimizations such as jump threading and loop unswitching to make
 // better decisions.
 //
 //===----------------------------------------------------------------------===//
-#ifndef LLVM_ANALYSIS_DIVERGENCE_ANALYSIS_H
-#define LLVM_ANALYSIS_DIVERGENCE_ANALYSIS_H
+#ifndef LLVM_ANALYSIS_LEGACY_DIVERGENCE_ANALYSIS_H
+#define LLVM_ANALYSIS_LEGACY_DIVERGENCE_ANALYSIS_H
 
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/IR/Function.h"
@@ -22,12 +22,12 @@
 
 namespace llvm {
 class Value;
-class DivergenceAnalysis : public FunctionPass {
+class LegacyDivergenceAnalysis : public FunctionPass {
 public:
   static char ID;
 
-  DivergenceAnalysis() : FunctionPass(ID) {
-    initializeDivergenceAnalysisPass(*PassRegistry::getPassRegistry());
+  LegacyDivergenceAnalysis() : FunctionPass(ID) {
+    initializeLegacyDivergenceAnalysisPass(*PassRegistry::getPassRegistry());
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
@@ -58,4 +58,4 @@
 };
 } // End llvm namespace
 
-#endif //LLVM_ANALYSIS_DIVERGENCE_ANALYSIS_H
\ No newline at end of file
+#endif //LLVM_ANALYSIS_LEGACY_DIVERGENCE_ANALYSIS_H
diff --git a/linux-x64/clang/include/llvm/Analysis/LoopAccessAnalysis.h b/linux-x64/clang/include/llvm/Analysis/LoopAccessAnalysis.h
index d27b3e4..86b402b 100644
--- a/linux-x64/clang/include/llvm/Analysis/LoopAccessAnalysis.h
+++ b/linux-x64/clang/include/llvm/Analysis/LoopAccessAnalysis.h
@@ -564,11 +564,10 @@
   /// Print the information about the memory accesses in the loop.
   void print(raw_ostream &OS, unsigned Depth = 0) const;
 
-  /// Checks existence of store to invariant address inside loop.
-  /// If the loop has any store to invariant address, then it returns true,
-  /// else returns false.
-  bool hasStoreToLoopInvariantAddress() const {
-    return StoreToLoopInvariantAddress;
+  /// If the loop has any store of a variant value to an invariant address, then
+  /// return true, else return false.
+  bool hasVariantStoreToLoopInvariantAddress() const {
+    return HasVariantStoreToLoopInvariantAddress;
   }
 
   /// Used to add runtime SCEV checks. Simplifies SCEV expressions and converts
@@ -621,9 +620,8 @@
   /// Cache the result of analyzeLoop.
   bool CanVecMem;
 
-  /// Indicator for storing to uniform addresses.
-  /// If a loop has write to a loop invariant address then it should be true.
-  bool StoreToLoopInvariantAddress;
+  /// Indicator that there is a store of a variant value to a uniform address.
+  bool HasVariantStoreToLoopInvariantAddress;
 
   /// The diagnostics report generated for the analysis.  E.g. why we
   /// couldn't analyze the loop.
diff --git a/linux-x64/clang/include/llvm/Analysis/LoopInfoImpl.h b/linux-x64/clang/include/llvm/Analysis/LoopInfoImpl.h
index 9413898..d3054b7 100644
--- a/linux-x64/clang/include/llvm/Analysis/LoopInfoImpl.h
+++ b/linux-x64/clang/include/llvm/Analysis/LoopInfoImpl.h
@@ -640,8 +640,8 @@
 
 template <typename T>
 bool compareVectors(std::vector<T> &BB1, std::vector<T> &BB2) {
-  llvm::sort(BB1.begin(), BB1.end());
-  llvm::sort(BB2.begin(), BB2.end());
+  llvm::sort(BB1);
+  llvm::sort(BB2);
   return BB1 == BB2;
 }
 
diff --git a/linux-x64/clang/include/llvm/Analysis/MemoryLocation.h b/linux-x64/clang/include/llvm/Analysis/MemoryLocation.h
index 6b68000..509efa2 100644
--- a/linux-x64/clang/include/llvm/Analysis/MemoryLocation.h
+++ b/linux-x64/clang/include/llvm/Analysis/MemoryLocation.h
@@ -34,8 +34,131 @@
 class TargetLibraryInfo;
 
 // Represents the size of a MemoryLocation. Logically, it's an
-// Optional<uint64_t>, with a special UnknownSize value from `MemoryLocation`.
-using LocationSize = uint64_t;
+// Optional<uint63_t> that also carries a bit to represent whether the integer
+// it contains, N, is 'precise'. Precise, in this context, means that we know
+// that the area of storage referenced by the given MemoryLocation must be
+// precisely N bytes. An imprecise value is formed as the union of two or more
+// precise values, and can conservatively represent all of the values unioned
+// into it. Importantly, imprecise values are an *upper-bound* on the size of a
+// MemoryLocation.
+//
+// Concretely, a precise MemoryLocation is (%p, 4) in
+// store i32 0, i32* %p
+//
+// Since we know that %p must be at least 4 bytes large at this point.
+// Otherwise, we have UB. An example of an imprecise MemoryLocation is (%p, 4)
+// at the memcpy in
+//
+//   %n = select i1 %foo, i64 1, i64 4
+//   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %p, i8* %baz, i64 %n, i32 1,
+//                                        i1 false)
+//
+// ...Since we'll copy *up to* 4 bytes into %p, but we can't guarantee that
+// we'll ever actually do so.
+//
+// If asked to represent a pathologically large value, this will degrade to
+// None.
+class LocationSize {
+  enum : uint64_t {
+    Unknown = ~uint64_t(0),
+    ImpreciseBit = uint64_t(1) << 63,
+    MapEmpty = Unknown - 1,
+    MapTombstone = Unknown - 2,
+
+    // The maximum value we can represent without falling back to 'unknown'.
+    MaxValue = (MapTombstone - 1) & ~ImpreciseBit,
+  };
+
+  uint64_t Value;
+
+  // Hack to support implicit construction. This should disappear when the
+  // public LocationSize ctor goes away.
+  enum DirectConstruction { Direct };
+
+  constexpr LocationSize(uint64_t Raw, DirectConstruction): Value(Raw) {}
+
+  static_assert(Unknown & ImpreciseBit, "Unknown is imprecise by definition.");
+public:
+  // FIXME: Migrate all users to construct via either `precise` or `upperBound`,
+  // to make it more obvious at the callsite the kind of size that they're
+  // providing.
+  //
+  // Since the overwhelming majority of users of this provide precise values,
+  // this assumes the provided value is precise.
+  constexpr LocationSize(uint64_t Raw)
+      : Value(Raw > MaxValue ? Unknown : Raw) {}
+
+  static LocationSize precise(uint64_t Value) { return LocationSize(Value); }
+
+  static LocationSize upperBound(uint64_t Value) {
+    // You can't go lower than 0, so give a precise result.
+    if (LLVM_UNLIKELY(Value == 0))
+      return precise(0);
+    if (LLVM_UNLIKELY(Value > MaxValue))
+      return unknown();
+    return LocationSize(Value | ImpreciseBit, Direct);
+  }
+
+  constexpr static LocationSize unknown() {
+    return LocationSize(Unknown, Direct);
+  }
+
+  // Sentinel values, generally used for maps.
+  constexpr static LocationSize mapTombstone() {
+    return LocationSize(MapTombstone, Direct);
+  }
+  constexpr static LocationSize mapEmpty() {
+    return LocationSize(MapEmpty, Direct);
+  }
+
+  // Returns a LocationSize that can correctly represent either `*this` or
+  // `Other`.
+  LocationSize unionWith(LocationSize Other) const {
+    if (Other == *this)
+      return *this;
+
+    if (!hasValue() || !Other.hasValue())
+      return unknown();
+
+    return upperBound(std::max(getValue(), Other.getValue()));
+  }
+
+  bool hasValue() const { return Value != Unknown; }
+  uint64_t getValue() const {
+    assert(hasValue() && "Getting value from an unknown LocationSize!");
+    return Value & ~ImpreciseBit;
+  }
+
+  // Returns whether or not this value is precise. Note that if a value is
+  // precise, it's guaranteed to not be `unknown()`.
+  bool isPrecise() const {
+    return (Value & ImpreciseBit) == 0;
+  }
+
+  bool operator==(const LocationSize &Other) const {
+    return Value == Other.Value;
+  }
+
+  bool operator!=(const LocationSize &Other) const {
+    return !(*this == Other);
+  }
+
+  // Ordering operators are not provided, since it's unclear if there's only one
+  // reasonable way to compare:
+  // - values that don't exist against values that do, and
+  // - precise values to imprecise values
+
+  void print(raw_ostream &OS) const;
+
+  // Returns an opaque value that represents this LocationSize. Cannot be
+  // reliably converted back into a LocationSize.
+  uint64_t toRaw() const { return Value; }
+};
+
+inline raw_ostream &operator<<(raw_ostream &OS, LocationSize Size) {
+  Size.print(OS);
+  return OS;
+}
 
 /// Representation for a specific memory location.
 ///
@@ -109,7 +232,11 @@
 
   /// Return a location representing a particular argument of a call.
   static MemoryLocation getForArgument(ImmutableCallSite CS, unsigned ArgIdx,
-                                       const TargetLibraryInfo &TLI);
+                                       const TargetLibraryInfo *TLI);
+  static MemoryLocation getForArgument(ImmutableCallSite CS, unsigned ArgIdx,
+                                       const TargetLibraryInfo &TLI) {
+    return getForArgument(CS, ArgIdx, &TLI);
+  }
 
   explicit MemoryLocation(const Value *Ptr = nullptr,
                           LocationSize Size = UnknownSize,
@@ -139,13 +266,30 @@
   }
 };
 
-// Specialize DenseMapInfo for MemoryLocation.
+// Specialize DenseMapInfo.
+template <> struct DenseMapInfo<LocationSize> {
+  static inline LocationSize getEmptyKey() {
+    return LocationSize::mapEmpty();
+  }
+  static inline LocationSize getTombstoneKey() {
+    return LocationSize::mapTombstone();
+  }
+  static unsigned getHashValue(const LocationSize &Val) {
+    return DenseMapInfo<uint64_t>::getHashValue(Val.toRaw());
+  }
+  static bool isEqual(const LocationSize &LHS, const LocationSize &RHS) {
+    return LHS == RHS;
+  }
+};
+
 template <> struct DenseMapInfo<MemoryLocation> {
   static inline MemoryLocation getEmptyKey() {
-    return MemoryLocation(DenseMapInfo<const Value *>::getEmptyKey(), 0);
+    return MemoryLocation(DenseMapInfo<const Value *>::getEmptyKey(),
+                          DenseMapInfo<LocationSize>::getEmptyKey());
   }
   static inline MemoryLocation getTombstoneKey() {
-    return MemoryLocation(DenseMapInfo<const Value *>::getTombstoneKey(), 0);
+    return MemoryLocation(DenseMapInfo<const Value *>::getTombstoneKey(),
+                          DenseMapInfo<LocationSize>::getTombstoneKey());
   }
   static unsigned getHashValue(const MemoryLocation &Val) {
     return DenseMapInfo<const Value *>::getHashValue(Val.Ptr) ^
diff --git a/linux-x64/clang/include/llvm/Analysis/MemorySSA.h b/linux-x64/clang/include/llvm/Analysis/MemorySSA.h
index d445e44..6200837 100644
--- a/linux-x64/clang/include/llvm/Analysis/MemorySSA.h
+++ b/linux-x64/clang/include/llvm/Analysis/MemorySSA.h
@@ -280,9 +280,10 @@
   friend class MemorySSAUpdater;
 
   MemoryUseOrDef(LLVMContext &C, MemoryAccess *DMA, unsigned Vty,
-                 DeleteValueTy DeleteValue, Instruction *MI, BasicBlock *BB)
-      : MemoryAccess(C, Vty, DeleteValue, BB, 1), MemoryInstruction(MI),
-        OptimizedAccessAlias(MayAlias) {
+                 DeleteValueTy DeleteValue, Instruction *MI, BasicBlock *BB,
+                 unsigned NumOperands)
+      : MemoryAccess(C, Vty, DeleteValue, BB, NumOperands),
+        MemoryInstruction(MI), OptimizedAccessAlias(MayAlias) {
     setDefiningAccess(DMA);
   }
 
@@ -308,11 +309,6 @@
   Optional<AliasResult> OptimizedAccessAlias;
 };
 
-template <>
-struct OperandTraits<MemoryUseOrDef>
-    : public FixedNumOperandTraits<MemoryUseOrDef, 1> {};
-DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUseOrDef, MemoryAccess)
-
 /// Represents read-only accesses to memory
 ///
 /// In particular, the set of Instructions that will be represented by
@@ -323,7 +319,8 @@
   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess);
 
   MemoryUse(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB)
-      : MemoryUseOrDef(C, DMA, MemoryUseVal, deleteMe, MI, BB) {}
+      : MemoryUseOrDef(C, DMA, MemoryUseVal, deleteMe, MI, BB,
+                       /*NumOperands=*/1) {}
 
   // allocate space for exactly one operand
   void *operator new(size_t s) { return User::operator new(s, 1); }
@@ -381,27 +378,28 @@
 
   MemoryDef(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB,
             unsigned Ver)
-      : MemoryUseOrDef(C, DMA, MemoryDefVal, deleteMe, MI, BB), ID(Ver) {}
+      : MemoryUseOrDef(C, DMA, MemoryDefVal, deleteMe, MI, BB,
+                       /*NumOperands=*/2),
+        ID(Ver) {}
 
-  // allocate space for exactly one operand
-  void *operator new(size_t s) { return User::operator new(s, 1); }
+  // allocate space for exactly two operands
+  void *operator new(size_t s) { return User::operator new(s, 2); }
 
   static bool classof(const Value *MA) {
     return MA->getValueID() == MemoryDefVal;
   }
 
   void setOptimized(MemoryAccess *MA) {
-    Optimized = MA;
-    OptimizedID = getDefiningAccess()->getID();
+    setOperand(1, MA);
+    OptimizedID = MA->getID();
   }
 
   MemoryAccess *getOptimized() const {
-    return cast_or_null<MemoryAccess>(Optimized);
+    return cast_or_null<MemoryAccess>(getOperand(1));
   }
 
   bool isOptimized() const {
-    return getOptimized() && getDefiningAccess() &&
-           OptimizedID == getDefiningAccess()->getID();
+    return getOptimized() && OptimizedID == getOptimized()->getID();
   }
 
   void resetOptimized() {
@@ -417,13 +415,34 @@
 
   const unsigned ID;
   unsigned OptimizedID = INVALID_MEMORYACCESS_ID;
-  WeakVH Optimized;
 };
 
 template <>
-struct OperandTraits<MemoryDef> : public FixedNumOperandTraits<MemoryDef, 1> {};
+struct OperandTraits<MemoryDef> : public FixedNumOperandTraits<MemoryDef, 2> {};
 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryDef, MemoryAccess)
 
+template <>
+struct OperandTraits<MemoryUseOrDef> {
+  static Use *op_begin(MemoryUseOrDef *MUD) {
+    if (auto *MU = dyn_cast<MemoryUse>(MUD))
+      return OperandTraits<MemoryUse>::op_begin(MU);
+    return OperandTraits<MemoryDef>::op_begin(cast<MemoryDef>(MUD));
+  }
+
+  static Use *op_end(MemoryUseOrDef *MUD) {
+    if (auto *MU = dyn_cast<MemoryUse>(MUD))
+      return OperandTraits<MemoryUse>::op_end(MU);
+    return OperandTraits<MemoryDef>::op_end(cast<MemoryDef>(MUD));
+  }
+
+  static unsigned operands(const MemoryUseOrDef *MUD) {
+    if (const auto *MU = dyn_cast<MemoryUse>(MUD))
+      return OperandTraits<MemoryUse>::operands(MU);
+    return OperandTraits<MemoryDef>::operands(cast<MemoryDef>(MUD));
+  }
+};
+DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUseOrDef, MemoryAccess)
+
 /// Represents phi nodes for memory accesses.
 ///
 /// These have the same semantic as regular phi nodes, with the exception that
@@ -689,8 +708,13 @@
   /// access associated with it. If passed a basic block gets the memory phi
   /// node that exists for that block, if there is one. Otherwise, this will get
   /// a MemoryUseOrDef.
-  MemoryUseOrDef *getMemoryAccess(const Instruction *) const;
-  MemoryPhi *getMemoryAccess(const BasicBlock *BB) const;
+  MemoryUseOrDef *getMemoryAccess(const Instruction *I) const {
+    return cast_or_null<MemoryUseOrDef>(ValueToMemoryAccess.lookup(I));
+  }
+
+  MemoryPhi *getMemoryAccess(const BasicBlock *BB) const {
+    return cast_or_null<MemoryPhi>(ValueToMemoryAccess.lookup(cast<Value>(BB)));
+  }
 
   void dump() const;
   void print(raw_ostream &) const;
@@ -750,6 +774,9 @@
   /// all uses, uses appear in the right places).  This is used by unit tests.
   void verifyMemorySSA() const;
 
+  /// Check clobber sanity for an access.
+  void checkClobberSanityAccess(const MemoryAccess *MA) const;
+
   /// Used in various insertion functions to specify whether we are talking
   /// about the beginning or end of a block.
   enum InsertionPlace { Beginning, End };
@@ -764,6 +791,7 @@
   void verifyDomination(Function &F) const;
   void verifyOrdering(Function &F) const;
   void verifyDominationNumbers(const Function &F) const;
+  void verifyClobberSanity(const Function &F) const;
 
   // This is used by the use optimizer and updater.
   AccessList *getWritableBlockAccesses(const BasicBlock *BB) const {
@@ -796,7 +824,8 @@
                                InsertionPlace);
   void insertIntoListsBefore(MemoryAccess *, const BasicBlock *,
                              AccessList::iterator);
-  MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *);
+  MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *,
+                                      const MemoryUseOrDef *Template = nullptr);
 
 private:
   class CachingWalker;
@@ -806,6 +835,7 @@
   void buildMemorySSA();
   void optimizeUses();
 
+  void prepareForMoveTo(MemoryAccess *, BasicBlock *);
   void verifyUseInDefs(MemoryAccess *, MemoryAccess *) const;
 
   using AccessMap = DenseMap<const BasicBlock *, std::unique_ptr<AccessList>>;
@@ -816,7 +846,8 @@
   void markUnreachableAsLiveOnEntry(BasicBlock *BB);
   bool dominatesUse(const MemoryAccess *, const MemoryAccess *) const;
   MemoryPhi *createMemoryPhi(BasicBlock *BB);
-  MemoryUseOrDef *createNewAccess(Instruction *);
+  MemoryUseOrDef *createNewAccess(Instruction *,
+                                  const MemoryUseOrDef *Template = nullptr);
   MemoryAccess *findDominatingDef(BasicBlock *, enum InsertionPlace);
   void placePHINodes(const SmallPtrSetImpl<BasicBlock *> &);
   MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *, bool);
diff --git a/linux-x64/clang/include/llvm/Analysis/MemorySSAUpdater.h b/linux-x64/clang/include/llvm/Analysis/MemorySSAUpdater.h
index 38f08c1..098876e 100644
--- a/linux-x64/clang/include/llvm/Analysis/MemorySSAUpdater.h
+++ b/linux-x64/clang/include/llvm/Analysis/MemorySSAUpdater.h
@@ -35,8 +35,10 @@
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/CFGDiff.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/OperandTraits.h"
@@ -45,6 +47,7 @@
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/IR/ValueHandle.h"
+#include "llvm/IR/ValueMap.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/ErrorHandling.h"
@@ -57,6 +60,12 @@
 class LLVMContext;
 class raw_ostream;
 
+using ValueToValueMapTy = ValueMap<const Value *, WeakTrackingVH>;
+using PhiToDefMap = SmallDenseMap<MemoryPhi *, MemoryAccess *>;
+using CFGUpdate = cfg::Update<BasicBlock *>;
+using GraphDiffInvBBPair =
+    std::pair<const GraphDiff<BasicBlock *> *, Inverse<BasicBlock *>>;
+
 class MemorySSAUpdater {
 private:
   MemorySSA *MSSA;
@@ -70,6 +79,7 @@
 
 public:
   MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {}
+
   /// Insert a definition into the MemorySSA IR.  RenameUses will rename any use
   /// below the new def block (and any inserted phis).  RenameUses should be set
   /// to true if the definition may cause new aliases for loads below it.  This
@@ -89,15 +99,48 @@
   /// Where a mayalias b, *does* require RenameUses be set to true.
   void insertDef(MemoryDef *Def, bool RenameUses = false);
   void insertUse(MemoryUse *Use);
+  /// Update the MemoryPhi in `To` following an edge deletion between `From` and
+  /// `To`. If `To` becomes unreachable, a call to removeBlocks should be made.
+  void removeEdge(BasicBlock *From, BasicBlock *To);
+  /// Update the MemoryPhi in `To` to have a single incoming edge from `From`,
+  /// following a CFG change that replaced multiple edges (switch) with a direct
+  /// branch.
+  void removeDuplicatePhiEdgesBetween(BasicBlock *From, BasicBlock *To);
+  /// Update MemorySSA after a loop was cloned, given the blocks in RPO order,
+  /// the exit blocks and a 1:1 mapping of all blocks and instructions
+  /// cloned. This involves duplicating all defs and uses in the cloned blocks
+  /// Updating phi nodes in exit block successors is done separately.
+  void updateForClonedLoop(const LoopBlocksRPO &LoopBlocks,
+                           ArrayRef<BasicBlock *> ExitBlocks,
+                           const ValueToValueMapTy &VM,
+                           bool IgnoreIncomingWithNoClones = false);
+  // Block BB was fully or partially cloned into its predecessor P1. Map
+  // contains the 1:1 mapping of instructions cloned and VM[BB]=P1.
+  void updateForClonedBlockIntoPred(BasicBlock *BB, BasicBlock *P1,
+                                    const ValueToValueMapTy &VM);
+  /// Update phi nodes in exit block successors following cloning. Exit blocks
+  /// that were not cloned don't have additional predecessors added.
+  void updateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks,
+                                     const ValueToValueMapTy &VMap,
+                                     DominatorTree &DT);
+  void updateExitBlocksForClonedLoop(
+      ArrayRef<BasicBlock *> ExitBlocks,
+      ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT);
+
+  /// Apply CFG updates, analogous with the DT edge updates.
+  void applyUpdates(ArrayRef<CFGUpdate> Updates, DominatorTree &DT);
+  /// Apply CFG insert updates, analogous with the DT edge updates.
+  void applyInsertUpdates(ArrayRef<CFGUpdate> Updates, DominatorTree &DT);
+
   void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where);
   void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where);
   void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
                    MemorySSA::InsertionPlace Where);
-  /// `From` block was spliced into `From` and `To`.
-  /// Move all accesses from `From` to `To` starting at instruction `Start`.
-  /// `To` is newly created BB, so empty of MemorySSA::MemoryAccesses.
-  /// Edges are already updated, so successors of `To` with MPhi nodes need to
-  /// update incoming block.
+  /// `From` block was spliced into `From` and `To`. There is a CFG edge from
+  /// `From` to `To`. Move all accesses from `From` to `To` starting at
+  /// instruction `Start`. `To` is newly created BB, so empty of
+  /// MemorySSA::MemoryAccesses. Edges are already updated, so successors of
+  /// `To` with MPhi nodes need to update incoming block.
   /// |------|        |------|
   /// | From |        | From |
   /// |      |        |------|
@@ -108,12 +151,12 @@
   /// |------|        |------|
   void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To,
                                 Instruction *Start);
-  /// `From` block was merged into `To`. All instructions were moved and
-  /// `From` is an empty block with successor edges; `From` is about to be
-  /// deleted. Move all accesses from `From` to `To` starting at instruction
-  /// `Start`. `To` may have multiple successors, `From` has a single
-  /// predecessor. `From` may have successors with MPhi nodes, replace their
-  /// incoming block with `To`.
+  /// `From` block was merged into `To`. There is a CFG edge from `To` to
+  /// `From`.`To` still branches to `From`, but all instructions were moved and
+  /// `From` is now an empty block; `From` is about to be deleted. Move all
+  /// accesses from `From` to `To` starting at instruction `Start`. `To` may
+  /// have multiple successors, `From` has a single predecessor. `From` may have
+  /// successors with MPhi nodes, replace their incoming block with `To`.
   /// |------|        |------|
   /// |  To  |        |  To  |
   /// |------|        |      |
@@ -124,15 +167,14 @@
   /// |------|        |------|
   void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To,
                                Instruction *Start);
-  /// BasicBlock Old had New, an empty BasicBlock, added directly before it,
-  /// and the predecessors in Preds that used to point to Old, now point to
-  /// New. If New is the only predecessor, move Old's Phi, if present, to New.
+  /// A new empty BasicBlock (New) now branches directly to Old. Some of
+  /// Old's predecessors (Preds) are now branching to New instead of Old.
+  /// If New is the only predecessor, move Old's Phi, if present, to New.
   /// Otherwise, add a new Phi in New with appropriate incoming values, and
   /// update the incoming values in Old's Phi node too, if present.
-  void
-  wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New,
-                                               ArrayRef<BasicBlock *> Preds);
-
+  void wireOldPredecessorsToNewImmediatePredecessor(
+      BasicBlock *Old, BasicBlock *New, ArrayRef<BasicBlock *> Preds,
+      bool IdenticalEdgesWereMerged = true);
   // The below are utility functions. Other than creation of accesses to pass
   // to insertDef, and removeAccess to remove accesses, you should generally
   // not attempt to update memoryssa yourself. It is very non-trivial to get
@@ -220,6 +262,23 @@
   template <class RangeType>
   MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands);
   void fixupDefs(const SmallVectorImpl<WeakVH> &);
+  // Clone all uses and defs from BB to NewBB given a 1:1 map of all
+  // instructions and blocks cloned, and a map of MemoryPhi : Definition
+  // (MemoryAccess Phi or Def). VMap maps old instructions to cloned
+  // instructions and old blocks to cloned blocks. MPhiMap, is created in the
+  // caller of this private method, and maps existing MemoryPhis to new
+  // definitions that new MemoryAccesses must point to. These definitions may
+  // not necessarily be MemoryPhis themselves, they may be MemoryDefs. As such,
+  // the map is between MemoryPhis and MemoryAccesses, where the MemoryAccesses
+  // may be MemoryPhis or MemoryDefs and not MemoryUses.
+  void cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB,
+                        const ValueToValueMapTy &VMap, PhiToDefMap &MPhiMap);
+  template <typename Iter>
+  void privateUpdateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks,
+                                            Iter ValuesBegin, Iter ValuesEnd,
+                                            DominatorTree &DT);
+  void applyInsertUpdates(ArrayRef<CFGUpdate>, DominatorTree &DT,
+                          const GraphDiff<BasicBlock *> *GD);
 };
 } // end namespace llvm
 
diff --git a/linux-x64/clang/include/llvm/Analysis/MustExecute.h b/linux-x64/clang/include/llvm/Analysis/MustExecute.h
index 97ad76d..40a0273 100644
--- a/linux-x64/clang/include/llvm/Analysis/MustExecute.h
+++ b/linux-x64/clang/include/llvm/Analysis/MustExecute.h
@@ -31,28 +31,60 @@
 class Loop;
 
 /// Captures loop safety information.
-/// It keep information for loop & its header may throw exception or otherwise
+/// It keep information for loop blocks may throw exception or otherwise
 /// exit abnormaly on any iteration of the loop which might actually execute
 /// at runtime.  The primary way to consume this infromation is via
 /// isGuaranteedToExecute below, but some callers bailout or fallback to
 /// alternate reasoning if a loop contains any implicit control flow.
-struct LoopSafetyInfo {
+/// NOTE: LoopSafetyInfo contains cached information regarding loops and their
+/// particular blocks. This information is only dropped on invocation of
+/// computeLoopSafetyInfo. If the loop or any of its block is deleted, or if
+/// any thrower instructions have been added or removed from them, or if the
+/// control flow has changed, or in case of other meaningful modifications, the
+/// LoopSafetyInfo needs to be recomputed. If a meaningful modifications to the
+/// loop were made and the info wasn't recomputed properly, the behavior of all
+/// methods except for computeLoopSafetyInfo is undefined.
+class LoopSafetyInfo {
   bool MayThrow = false;       // The current loop contains an instruction which
                                // may throw.
   bool HeaderMayThrow = false; // Same as previous, but specific to loop header
+
+  /// Collect all blocks from \p CurLoop which lie on all possible paths from
+  /// the header of \p CurLoop (inclusive) to BB (exclusive) into the set
+  /// \p Predecessors. If \p BB is the header, \p Predecessors will be empty.
+  void collectTransitivePredecessors(
+      const Loop *CurLoop, const BasicBlock *BB,
+      SmallPtrSetImpl<const BasicBlock *> &Predecessors) const;
+
+public:
   // Used to update funclet bundle operands.
   DenseMap<BasicBlock *, ColorVector> BlockColors;
 
+  /// Returns true iff the header block of the loop for which this info is
+  /// calculated contains an instruction that may throw or otherwise exit
+  /// abnormally.
+  bool headerMayThrow() const;
+
+  /// Returns true iff any block of the loop for which this info is contains an
+  /// instruction that may throw or otherwise exit abnormally.
+  bool anyBlockMayThrow() const;
+
+  /// Return true if we must reach the block \p BB under assumption that the
+  /// loop \p CurLoop is entered and no instruction throws or otherwise exits
+  /// abnormally.
+  bool allLoopPathsLeadToBlock(const Loop *CurLoop, const BasicBlock *BB,
+                               const DominatorTree *DT) const;
+
+  /// Computes safety information for a loop checks loop body & header for
+  /// the possibility of may throw exception, it takes LoopSafetyInfo and loop
+  /// as argument. Updates safety information in LoopSafetyInfo argument.
+  /// Note: This is defined to clear and reinitialize an already initialized
+  /// LoopSafetyInfo.  Some callers rely on this fact.
+  void computeLoopSafetyInfo(Loop *);
+
   LoopSafetyInfo() = default;
 };
 
-/// Computes safety information for a loop checks loop body & header for
-/// the possibility of may throw exception, it takes LoopSafetyInfo and loop as
-/// argument. Updates safety information in LoopSafetyInfo argument.
-/// Note: This is defined to clear and reinitialize an already initialized
-/// LoopSafetyInfo.  Some callers rely on this fact.
-void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *);
-
 /// Returns true if the instruction in a loop is guaranteed to execute at least
 /// once (under the assumption that the loop is entered).
 bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT,
diff --git a/linux-x64/clang/include/llvm/Analysis/OrderedInstructions.h b/linux-x64/clang/include/llvm/Analysis/OrderedInstructions.h
new file mode 100644
index 0000000..7e3850b
--- /dev/null
+++ b/linux-x64/clang/include/llvm/Analysis/OrderedInstructions.h
@@ -0,0 +1,65 @@
+//===- llvm/Transforms/Utils/OrderedInstructions.h -------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines an efficient way to check for dominance relation between 2
+// instructions.
+//
+// This interface dispatches to appropriate dominance check given 2
+// instructions, i.e. in case the instructions are in the same basic block,
+// OrderedBasicBlock (with instruction numbering and caching) are used.
+// Otherwise, dominator tree is used.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H
+#define LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Analysis/OrderedBasicBlock.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Operator.h"
+
+namespace llvm {
+
+class OrderedInstructions {
+  /// Used to check dominance for instructions in same basic block.
+  mutable DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>>
+      OBBMap;
+
+  /// The dominator tree of the parent function.
+  DominatorTree *DT;
+
+  /// Return true if the first instruction comes before the second in the
+  /// same basic block. It will create an ordered basic block, if it does
+  /// not yet exist in OBBMap.
+  bool localDominates(const Instruction *, const Instruction *) const;
+
+public:
+  /// Constructor.
+  OrderedInstructions(DominatorTree *DT) : DT(DT) {}
+
+  /// Return true if first instruction dominates the second.
+  bool dominates(const Instruction *, const Instruction *) const;
+
+  /// Return true if the first instruction comes before the second in the
+  /// dominator tree DFS traversal if they are in different basic blocks,
+  /// or if the first instruction comes before the second in the same basic
+  /// block.
+  bool dfsBefore(const Instruction *, const Instruction *) const;
+
+  /// Invalidate the OrderedBasicBlock cache when its basic block changes.
+  /// i.e. If an instruction is deleted or added to the basic block, the user
+  /// should call this function to invalidate the OrderedBasicBlock cache for
+  /// this basic block.
+  void invalidateBlock(const BasicBlock *BB) { OBBMap.erase(BB); }
+};
+
+} // end namespace llvm
+
+#endif // LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H
diff --git a/linux-x64/clang/include/llvm/Analysis/Passes.h b/linux-x64/clang/include/llvm/Analysis/Passes.h
index 09b28a0..081dd50 100644
--- a/linux-x64/clang/include/llvm/Analysis/Passes.h
+++ b/linux-x64/clang/include/llvm/Analysis/Passes.h
@@ -61,10 +61,10 @@
 
   //===--------------------------------------------------------------------===//
   //
-  // createDivergenceAnalysisPass - This pass determines which branches in a GPU
+  // createLegacyDivergenceAnalysisPass - This pass determines which branches in a GPU
   // program are divergent.
   //
-  FunctionPass *createDivergenceAnalysisPass();
+  FunctionPass *createLegacyDivergenceAnalysisPass();
 
   //===--------------------------------------------------------------------===//
   //
diff --git a/linux-x64/clang/include/llvm/Analysis/PhiValues.h b/linux-x64/clang/include/llvm/Analysis/PhiValues.h
index 6607b32..76204ac 100644
--- a/linux-x64/clang/include/llvm/Analysis/PhiValues.h
+++ b/linux-x64/clang/include/llvm/Analysis/PhiValues.h
@@ -88,6 +88,22 @@
   /// All values reachable from each component.
   DenseMap<unsigned int, ConstValueSet> ReachableMap;
 
+  /// A CallbackVH to notify PhiValues when a value is deleted or replaced, so
+  /// that the cached information for that value can be cleared to avoid
+  /// dangling pointers to invalid values.
+  class PhiValuesCallbackVH final : public CallbackVH {
+    PhiValues *PV;
+    void deleted() override;
+    void allUsesReplacedWith(Value *New) override;
+
+  public:
+    PhiValuesCallbackVH(Value *V, PhiValues *PV = nullptr)
+        : CallbackVH(V), PV(PV) {}
+  };
+
+  /// A set of callbacks to the values that processPhi has seen.
+  DenseSet<PhiValuesCallbackVH, DenseMapInfo<Value *>> TrackedValues;
+
   /// The function that the PhiValues is for.
   const Function &F;
 
diff --git a/linux-x64/clang/include/llvm/Analysis/SparsePropagation.h b/linux-x64/clang/include/llvm/Analysis/SparsePropagation.h
index defcf96..04e94f7 100644
--- a/linux-x64/clang/include/llvm/Analysis/SparsePropagation.h
+++ b/linux-x64/clang/include/llvm/Analysis/SparsePropagation.h
@@ -330,7 +330,7 @@
     return;
   }
 
-  if (TI.isExceptional()) {
+  if (TI.isExceptionalTerminator()) {
     Succs.assign(Succs.size(), true);
     return;
   }
diff --git a/linux-x64/clang/include/llvm/Analysis/TargetTransformInfo.h b/linux-x64/clang/include/llvm/Analysis/TargetTransformInfo.h
index 59657cc..18b5a5c 100644
--- a/linux-x64/clang/include/llvm/Analysis/TargetTransformInfo.h
+++ b/linux-x64/clang/include/llvm/Analysis/TargetTransformInfo.h
@@ -289,7 +289,7 @@
   /// Returns whether V is a source of divergence.
   ///
   /// This function provides the target-dependent information for
-  /// the target-independent DivergenceAnalysis. DivergenceAnalysis first
+  /// the target-independent LegacyDivergenceAnalysis. LegacyDivergenceAnalysis first
   /// builds the dependency graph, and then runs the reachability algorithm
   /// starting with the sources of divergence.
   bool isSourceOfDivergence(const Value *V) const;
@@ -739,6 +739,10 @@
   /// and the number of execution units in the CPU.
   unsigned getMaxInterleaveFactor(unsigned VF) const;
 
+  /// Collect properties of V used in cost analyzis, e.g. OP_PowerOf2.
+  OperandValueKind getOperandInfo(Value *V,
+                                  OperandValueProperties &OpProps) const;
+
   /// This is an approximation of reciprocal throughput of a math/logic op.
   /// A higher cost indicates less expected throughput.
   /// From Agner Fog's guides, reciprocal throughput is "the average number of
diff --git a/linux-x64/clang/include/llvm/Analysis/TargetTransformInfoImpl.h b/linux-x64/clang/include/llvm/Analysis/TargetTransformInfoImpl.h
index d80ae1d..e39fe66 100644
--- a/linux-x64/clang/include/llvm/Analysis/TargetTransformInfoImpl.h
+++ b/linux-x64/clang/include/llvm/Analysis/TargetTransformInfoImpl.h
@@ -158,6 +158,8 @@
     case Intrinsic::dbg_label:
     case Intrinsic::invariant_start:
     case Intrinsic::invariant_end:
+    case Intrinsic::launder_invariant_group:
+    case Intrinsic::strip_invariant_group:
     case Intrinsic::lifetime_start:
     case Intrinsic::lifetime_end:
     case Intrinsic::objectsize:
diff --git a/linux-x64/clang/include/llvm/Analysis/TypeMetadataUtils.h b/linux-x64/clang/include/llvm/Analysis/TypeMetadataUtils.h
index 6764563..3bf9c5d 100644
--- a/linux-x64/clang/include/llvm/Analysis/TypeMetadataUtils.h
+++ b/linux-x64/clang/include/llvm/Analysis/TypeMetadataUtils.h
@@ -20,6 +20,8 @@
 
 namespace llvm {
 
+class DominatorTree;
+
 /// The type of CFI jumptable needed for a function.
 enum CfiFunctionLinkage {
   CFL_Definition = 0,
@@ -39,7 +41,8 @@
 /// call sites based on the call and return them in DevirtCalls.
 void findDevirtualizableCallsForTypeTest(
     SmallVectorImpl<DevirtCallSite> &DevirtCalls,
-    SmallVectorImpl<CallInst *> &Assumes, const CallInst *CI);
+    SmallVectorImpl<CallInst *> &Assumes, const CallInst *CI,
+    DominatorTree &DT);
 
 /// Given a call to the intrinsic \@llvm.type.checked.load, find all
 /// devirtualizable call sites based on the call and return them in DevirtCalls.
@@ -47,7 +50,7 @@
     SmallVectorImpl<DevirtCallSite> &DevirtCalls,
     SmallVectorImpl<Instruction *> &LoadedPtrs,
     SmallVectorImpl<Instruction *> &Preds, bool &HasNonCallUses,
-    const CallInst *CI);
+    const CallInst *CI, DominatorTree &DT);
 }
 
 #endif
diff --git a/linux-x64/clang/include/llvm/Analysis/ValueTracking.h b/linux-x64/clang/include/llvm/Analysis/ValueTracking.h
index 99b47fb..a92ba8e 100644
--- a/linux-x64/clang/include/llvm/Analysis/ValueTracking.h
+++ b/linux-x64/clang/include/llvm/Analysis/ValueTracking.h
@@ -55,14 +55,16 @@
                         AssumptionCache *AC = nullptr,
                         const Instruction *CxtI = nullptr,
                         const DominatorTree *DT = nullptr,
-                        OptimizationRemarkEmitter *ORE = nullptr);
+                        OptimizationRemarkEmitter *ORE = nullptr,
+                        bool UseInstrInfo = true);
 
   /// Returns the known bits rather than passing by reference.
   KnownBits computeKnownBits(const Value *V, const DataLayout &DL,
                              unsigned Depth = 0, AssumptionCache *AC = nullptr,
                              const Instruction *CxtI = nullptr,
                              const DominatorTree *DT = nullptr,
-                             OptimizationRemarkEmitter *ORE = nullptr);
+                             OptimizationRemarkEmitter *ORE = nullptr,
+                             bool UseInstrInfo = true);
 
   /// Compute known bits from the range metadata.
   /// \p KnownZero the set of bits that are known to be zero
@@ -75,7 +77,8 @@
                            const DataLayout &DL,
                            AssumptionCache *AC = nullptr,
                            const Instruction *CxtI = nullptr,
-                           const DominatorTree *DT = nullptr);
+                           const DominatorTree *DT = nullptr,
+                           bool UseInstrInfo = true);
 
   /// Return true if the given value is known to have exactly one bit set when
   /// defined. For vectors return true if every element is known to be a power
@@ -86,7 +89,8 @@
                               bool OrZero = false, unsigned Depth = 0,
                               AssumptionCache *AC = nullptr,
                               const Instruction *CxtI = nullptr,
-                              const DominatorTree *DT = nullptr);
+                              const DominatorTree *DT = nullptr,
+                              bool UseInstrInfo = true);
 
   bool isOnlyUsedInZeroEqualityComparison(const Instruction *CxtI);
 
@@ -99,7 +103,8 @@
   bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth = 0,
                       AssumptionCache *AC = nullptr,
                       const Instruction *CxtI = nullptr,
-                      const DominatorTree *DT = nullptr);
+                      const DominatorTree *DT = nullptr,
+                      bool UseInstrInfo = true);
 
   /// Return true if the two given values are negation.
   /// Currently can recoginze Value pair:
@@ -112,28 +117,32 @@
                           unsigned Depth = 0,
                           AssumptionCache *AC = nullptr,
                           const Instruction *CxtI = nullptr,
-                          const DominatorTree *DT = nullptr);
+                          const DominatorTree *DT = nullptr,
+                          bool UseInstrInfo = true);
 
   /// Returns true if the given value is known be positive (i.e. non-negative
   /// and non-zero).
   bool isKnownPositive(const Value *V, const DataLayout &DL, unsigned Depth = 0,
                        AssumptionCache *AC = nullptr,
                        const Instruction *CxtI = nullptr,
-                       const DominatorTree *DT = nullptr);
+                       const DominatorTree *DT = nullptr,
+                       bool UseInstrInfo = true);
 
   /// Returns true if the given value is known be negative (i.e. non-positive
   /// and non-zero).
   bool isKnownNegative(const Value *V, const DataLayout &DL, unsigned Depth = 0,
                        AssumptionCache *AC = nullptr,
                        const Instruction *CxtI = nullptr,
-                       const DominatorTree *DT = nullptr);
+                       const DominatorTree *DT = nullptr,
+                       bool UseInstrInfo = true);
 
   /// Return true if the given values are known to be non-equal when defined.
   /// Supports scalar integer types only.
   bool isKnownNonEqual(const Value *V1, const Value *V2, const DataLayout &DL,
-                      AssumptionCache *AC = nullptr,
-                      const Instruction *CxtI = nullptr,
-                      const DominatorTree *DT = nullptr);
+                       AssumptionCache *AC = nullptr,
+                       const Instruction *CxtI = nullptr,
+                       const DominatorTree *DT = nullptr,
+                       bool UseInstrInfo = true);
 
   /// Return true if 'V & Mask' is known to be zero. We use this predicate to
   /// simplify operations downstream. Mask is known to be zero for bits that V
@@ -148,7 +157,8 @@
                          const DataLayout &DL,
                          unsigned Depth = 0, AssumptionCache *AC = nullptr,
                          const Instruction *CxtI = nullptr,
-                         const DominatorTree *DT = nullptr);
+                         const DominatorTree *DT = nullptr,
+                         bool UseInstrInfo = true);
 
   /// Return the number of times the sign bit of the register is replicated into
   /// the other bits. We know that at least 1 bit is always equal to the sign
@@ -160,7 +170,8 @@
   unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL,
                               unsigned Depth = 0, AssumptionCache *AC = nullptr,
                               const Instruction *CxtI = nullptr,
-                              const DominatorTree *DT = nullptr);
+                              const DominatorTree *DT = nullptr,
+                              bool UseInstrInfo = true);
 
   /// This function computes the integer multiple of Base that equals V. If
   /// successful, it returns true and returns the multiple in Multiple. If
@@ -210,7 +221,8 @@
   /// return the i8 value that it is represented with. This is true for all i8
   /// values obviously, but is also true for i32 0, i32 -1, i16 0xF0F0, double
   /// 0.0 etc. If the value can't be handled with a repeated byte store (e.g.
-  /// i16 0x1234), return null.
+  /// i16 0x1234), return null. If the value is entirely undef and padding,
+  /// return undef.
   Value *isBytewiseValue(Value *V);
 
   /// Given an aggregrate and an sequence of indices, see if the scalar value
@@ -406,18 +418,21 @@
                                                const DataLayout &DL,
                                                AssumptionCache *AC,
                                                const Instruction *CxtI,
-                                               const DominatorTree *DT);
+                                               const DominatorTree *DT,
+                                               bool UseInstrInfo = true);
   OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS,
                                              const DataLayout &DL,
                                              AssumptionCache *AC,
                                              const Instruction *CxtI,
-                                             const DominatorTree *DT);
+                                             const DominatorTree *DT,
+                                             bool UseInstrInfo = true);
   OverflowResult computeOverflowForUnsignedAdd(const Value *LHS,
                                                const Value *RHS,
                                                const DataLayout &DL,
                                                AssumptionCache *AC,
                                                const Instruction *CxtI,
-                                               const DominatorTree *DT);
+                                               const DominatorTree *DT,
+                                               bool UseInstrInfo = true);
   OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS,
                                              const DataLayout &DL,
                                              AssumptionCache *AC = nullptr,
diff --git a/linux-x64/clang/include/llvm/Analysis/VectorUtils.h b/linux-x64/clang/include/llvm/Analysis/VectorUtils.h
index 9fde36d..622d932 100644
--- a/linux-x64/clang/include/llvm/Analysis/VectorUtils.h
+++ b/linux-x64/clang/include/llvm/Analysis/VectorUtils.h
@@ -15,6 +15,7 @@
 #define LLVM_ANALYSIS_VECTORUTILS_H
 
 #include "llvm/ADT/MapVector.h"
+#include "llvm/Analysis/LoopAccessAnalysis.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/IRBuilder.h"
 
@@ -176,6 +177,338 @@
 /// elements, it will be padded with undefs.
 Value *concatenateVectors(IRBuilder<> &Builder, ArrayRef<Value *> Vecs);
 
+/// The group of interleaved loads/stores sharing the same stride and
+/// close to each other.
+///
+/// Each member in this group has an index starting from 0, and the largest
+/// index should be less than interleaved factor, which is equal to the absolute
+/// value of the access's stride.
+///
+/// E.g. An interleaved load group of factor 4:
+///        for (unsigned i = 0; i < 1024; i+=4) {
+///          a = A[i];                           // Member of index 0
+///          b = A[i+1];                         // Member of index 1
+///          d = A[i+3];                         // Member of index 3
+///          ...
+///        }
+///
+///      An interleaved store group of factor 4:
+///        for (unsigned i = 0; i < 1024; i+=4) {
+///          ...
+///          A[i]   = a;                         // Member of index 0
+///          A[i+1] = b;                         // Member of index 1
+///          A[i+2] = c;                         // Member of index 2
+///          A[i+3] = d;                         // Member of index 3
+///        }
+///
+/// Note: the interleaved load group could have gaps (missing members), but
+/// the interleaved store group doesn't allow gaps.
+class InterleaveGroup {
+public:
+  InterleaveGroup(Instruction *Instr, int Stride, unsigned Align)
+      : Align(Align), InsertPos(Instr) {
+    assert(Align && "The alignment should be non-zero");
+
+    Factor = std::abs(Stride);
+    assert(Factor > 1 && "Invalid interleave factor");
+
+    Reverse = Stride < 0;
+    Members[0] = Instr;
+  }
+
+  bool isReverse() const { return Reverse; }
+  unsigned getFactor() const { return Factor; }
+  unsigned getAlignment() const { return Align; }
+  unsigned getNumMembers() const { return Members.size(); }
+
+  /// Try to insert a new member \p Instr with index \p Index and
+  /// alignment \p NewAlign. The index is related to the leader and it could be
+  /// negative if it is the new leader.
+  ///
+  /// \returns false if the instruction doesn't belong to the group.
+  bool insertMember(Instruction *Instr, int Index, unsigned NewAlign) {
+    assert(NewAlign && "The new member's alignment should be non-zero");
+
+    int Key = Index + SmallestKey;
+
+    // Skip if there is already a member with the same index.
+    if (Members.find(Key) != Members.end())
+      return false;
+
+    if (Key > LargestKey) {
+      // The largest index is always less than the interleave factor.
+      if (Index >= static_cast<int>(Factor))
+        return false;
+
+      LargestKey = Key;
+    } else if (Key < SmallestKey) {
+      // The largest index is always less than the interleave factor.
+      if (LargestKey - Key >= static_cast<int>(Factor))
+        return false;
+
+      SmallestKey = Key;
+    }
+
+    // It's always safe to select the minimum alignment.
+    Align = std::min(Align, NewAlign);
+    Members[Key] = Instr;
+    return true;
+  }
+
+  /// Get the member with the given index \p Index
+  ///
+  /// \returns nullptr if contains no such member.
+  Instruction *getMember(unsigned Index) const {
+    int Key = SmallestKey + Index;
+    auto Member = Members.find(Key);
+    if (Member == Members.end())
+      return nullptr;
+
+    return Member->second;
+  }
+
+  /// Get the index for the given member. Unlike the key in the member
+  /// map, the index starts from 0.
+  unsigned getIndex(Instruction *Instr) const {
+    for (auto I : Members)
+      if (I.second == Instr)
+        return I.first - SmallestKey;
+
+    llvm_unreachable("InterleaveGroup contains no such member");
+  }
+
+  Instruction *getInsertPos() const { return InsertPos; }
+  void setInsertPos(Instruction *Inst) { InsertPos = Inst; }
+
+  /// Add metadata (e.g. alias info) from the instructions in this group to \p
+  /// NewInst.
+  ///
+  /// FIXME: this function currently does not add noalias metadata a'la
+  /// addNewMedata.  To do that we need to compute the intersection of the
+  /// noalias info from all members.
+  void addMetadata(Instruction *NewInst) const {
+    SmallVector<Value *, 4> VL;
+    std::transform(Members.begin(), Members.end(), std::back_inserter(VL),
+                   [](std::pair<int, Instruction *> p) { return p.second; });
+    propagateMetadata(NewInst, VL);
+  }
+
+private:
+  unsigned Factor; // Interleave Factor.
+  bool Reverse;
+  unsigned Align;
+  DenseMap<int, Instruction *> Members;
+  int SmallestKey = 0;
+  int LargestKey = 0;
+
+  // To avoid breaking dependences, vectorized instructions of an interleave
+  // group should be inserted at either the first load or the last store in
+  // program order.
+  //
+  // E.g. %even = load i32             // Insert Position
+  //      %add = add i32 %even         // Use of %even
+  //      %odd = load i32
+  //
+  //      store i32 %even
+  //      %odd = add i32               // Def of %odd
+  //      store i32 %odd               // Insert Position
+  Instruction *InsertPos;
+};
+
+/// Drive the analysis of interleaved memory accesses in the loop.
+///
+/// Use this class to analyze interleaved accesses only when we can vectorize
+/// a loop. Otherwise it's meaningless to do analysis as the vectorization
+/// on interleaved accesses is unsafe.
+///
+/// The analysis collects interleave groups and records the relationships
+/// between the member and the group in a map.
+class InterleavedAccessInfo {
+public:
+  InterleavedAccessInfo(PredicatedScalarEvolution &PSE, Loop *L,
+                        DominatorTree *DT, LoopInfo *LI,
+                        const LoopAccessInfo *LAI)
+    : PSE(PSE), TheLoop(L), DT(DT), LI(LI), LAI(LAI) {}
+
+  ~InterleavedAccessInfo() {
+    SmallPtrSet<InterleaveGroup *, 4> DelSet;
+    // Avoid releasing a pointer twice.
+    for (auto &I : InterleaveGroupMap)
+      DelSet.insert(I.second);
+    for (auto *Ptr : DelSet)
+      delete Ptr;
+  }
+
+  /// Analyze the interleaved accesses and collect them in interleave
+  /// groups. Substitute symbolic strides using \p Strides.
+  void analyzeInterleaving();
+
+  /// Check if \p Instr belongs to any interleave group.
+  bool isInterleaved(Instruction *Instr) const {
+    return InterleaveGroupMap.find(Instr) != InterleaveGroupMap.end();
+  }
+
+  /// Get the interleave group that \p Instr belongs to.
+  ///
+  /// \returns nullptr if doesn't have such group.
+  InterleaveGroup *getInterleaveGroup(Instruction *Instr) const {
+    auto Group = InterleaveGroupMap.find(Instr);
+    if (Group == InterleaveGroupMap.end())
+      return nullptr;
+    return Group->second;
+  }
+
+  /// Returns true if an interleaved group that may access memory
+  /// out-of-bounds requires a scalar epilogue iteration for correctness.
+  bool requiresScalarEpilogue() const { return RequiresScalarEpilogue; }
+
+private:
+  /// A wrapper around ScalarEvolution, used to add runtime SCEV checks.
+  /// Simplifies SCEV expressions in the context of existing SCEV assumptions.
+  /// The interleaved access analysis can also add new predicates (for example
+  /// by versioning strides of pointers).
+  PredicatedScalarEvolution &PSE;
+
+  Loop *TheLoop;
+  DominatorTree *DT;
+  LoopInfo *LI;
+  const LoopAccessInfo *LAI;
+
+  /// True if the loop may contain non-reversed interleaved groups with
+  /// out-of-bounds accesses. We ensure we don't speculatively access memory
+  /// out-of-bounds by executing at least one scalar epilogue iteration.
+  bool RequiresScalarEpilogue = false;
+
+  /// Holds the relationships between the members and the interleave group.
+  DenseMap<Instruction *, InterleaveGroup *> InterleaveGroupMap;
+
+  /// Holds dependences among the memory accesses in the loop. It maps a source
+  /// access to a set of dependent sink accesses.
+  DenseMap<Instruction *, SmallPtrSet<Instruction *, 2>> Dependences;
+
+  /// The descriptor for a strided memory access.
+  struct StrideDescriptor {
+    StrideDescriptor() = default;
+    StrideDescriptor(int64_t Stride, const SCEV *Scev, uint64_t Size,
+                     unsigned Align)
+        : Stride(Stride), Scev(Scev), Size(Size), Align(Align) {}
+
+    // The access's stride. It is negative for a reverse access.
+    int64_t Stride = 0;
+
+    // The scalar expression of this access.
+    const SCEV *Scev = nullptr;
+
+    // The size of the memory object.
+    uint64_t Size = 0;
+
+    // The alignment of this access.
+    unsigned Align = 0;
+  };
+
+  /// A type for holding instructions and their stride descriptors.
+  using StrideEntry = std::pair<Instruction *, StrideDescriptor>;
+
+  /// Create a new interleave group with the given instruction \p Instr,
+  /// stride \p Stride and alignment \p Align.
+  ///
+  /// \returns the newly created interleave group.
+  InterleaveGroup *createInterleaveGroup(Instruction *Instr, int Stride,
+                                         unsigned Align) {
+    assert(!isInterleaved(Instr) && "Already in an interleaved access group");
+    InterleaveGroupMap[Instr] = new InterleaveGroup(Instr, Stride, Align);
+    return InterleaveGroupMap[Instr];
+  }
+
+  /// Release the group and remove all the relationships.
+  void releaseGroup(InterleaveGroup *Group) {
+    for (unsigned i = 0; i < Group->getFactor(); i++)
+      if (Instruction *Member = Group->getMember(i))
+        InterleaveGroupMap.erase(Member);
+
+    delete Group;
+  }
+
+  /// Collect all the accesses with a constant stride in program order.
+  void collectConstStrideAccesses(
+      MapVector<Instruction *, StrideDescriptor> &AccessStrideInfo,
+      const ValueToValueMap &Strides);
+
+  /// Returns true if \p Stride is allowed in an interleaved group.
+  static bool isStrided(int Stride);
+
+  /// Returns true if \p BB is a predicated block.
+  bool isPredicated(BasicBlock *BB) const {
+    return LoopAccessInfo::blockNeedsPredication(BB, TheLoop, DT);
+  }
+
+  /// Returns true if LoopAccessInfo can be used for dependence queries.
+  bool areDependencesValid() const {
+    return LAI && LAI->getDepChecker().getDependences();
+  }
+
+  /// Returns true if memory accesses \p A and \p B can be reordered, if
+  /// necessary, when constructing interleaved groups.
+  ///
+  /// \p A must precede \p B in program order. We return false if reordering is
+  /// not necessary or is prevented because \p A and \p B may be dependent.
+  bool canReorderMemAccessesForInterleavedGroups(StrideEntry *A,
+                                                 StrideEntry *B) const {
+    // Code motion for interleaved accesses can potentially hoist strided loads
+    // and sink strided stores. The code below checks the legality of the
+    // following two conditions:
+    //
+    // 1. Potentially moving a strided load (B) before any store (A) that
+    //    precedes B, or
+    //
+    // 2. Potentially moving a strided store (A) after any load or store (B)
+    //    that A precedes.
+    //
+    // It's legal to reorder A and B if we know there isn't a dependence from A
+    // to B. Note that this determination is conservative since some
+    // dependences could potentially be reordered safely.
+
+    // A is potentially the source of a dependence.
+    auto *Src = A->first;
+    auto SrcDes = A->second;
+
+    // B is potentially the sink of a dependence.
+    auto *Sink = B->first;
+    auto SinkDes = B->second;
+
+    // Code motion for interleaved accesses can't violate WAR dependences.
+    // Thus, reordering is legal if the source isn't a write.
+    if (!Src->mayWriteToMemory())
+      return true;
+
+    // At least one of the accesses must be strided.
+    if (!isStrided(SrcDes.Stride) && !isStrided(SinkDes.Stride))
+      return true;
+
+    // If dependence information is not available from LoopAccessInfo,
+    // conservatively assume the instructions can't be reordered.
+    if (!areDependencesValid())
+      return false;
+
+    // If we know there is a dependence from source to sink, assume the
+    // instructions can't be reordered. Otherwise, reordering is legal.
+    return Dependences.find(Src) == Dependences.end() ||
+           !Dependences.lookup(Src).count(Sink);
+  }
+
+  /// Collect the dependences from LoopAccessInfo.
+  ///
+  /// We process the dependences once during the interleaved access analysis to
+  /// enable constant-time dependence queries.
+  void collectDependences() {
+    if (!areDependencesValid())
+      return;
+    auto *Deps = LAI->getDepChecker().getDependences();
+    for (auto Dep : *Deps)
+      Dependences[Dep.getSource(*LAI)].insert(Dep.getDestination(*LAI));
+  }
+};
+
 } // llvm namespace
 
 #endif