Vendor import of llvm-project main llvmorg-14-init-17616-g024a1fab5c35.vendor/llvm-project/llvmorg-14-init-17616-g024a1fab5c35

32 files changed, 131 insertions, 69 deletions

diff --git a/llvm/include/llvm/Transforms/Coroutines/CoroSplit.h b/llvm/include/llvm/Transforms/Coroutines/CoroSplit.h
index ffca51578551..7623c9c0eb68 100644
--- a/llvm/include/llvm/Transforms/Coroutines/CoroSplit.h
+++ b/llvm/include/llvm/Transforms/Coroutines/CoroSplit.h
@@ -22,14 +22,14 @@
 namespace llvm {
 
 struct CoroSplitPass : PassInfoMixin<CoroSplitPass> {
-  CoroSplitPass(bool ReuseFrameSlot = false) : ReuseFrameSlot(ReuseFrameSlot) {}
+  CoroSplitPass(bool OptimizeFrame = false) : OptimizeFrame(OptimizeFrame) {}
 
   PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
                         LazyCallGraph &CG, CGSCCUpdateResult &UR);
   static bool isRequired() { return true; }
 
   // Would be true if the Optimization level isn't O0.
-  bool ReuseFrameSlot;
+  bool OptimizeFrame;
 };
 } // end namespace llvm
 
diff --git a/llvm/include/llvm/Transforms/IPO/Attributor.h b/llvm/include/llvm/Transforms/IPO/Attributor.h
index d4cbc9bd20b7..d56a43ec7961 100644
--- a/llvm/include/llvm/Transforms/IPO/Attributor.h
+++ b/llvm/include/llvm/Transforms/IPO/Attributor.h
@@ -133,7 +133,6 @@ struct InformationCache;
 struct AAIsDead;
 struct AttributorCallGraph;
 
-class AAManager;
 class AAResults;
 class Function;
 
@@ -173,7 +172,8 @@ combineOptionalValuesInAAValueLatice(const Optional<Value *> &A,
                                      const Optional<Value *> &B, Type *Ty);
 
 /// Return the initial value of \p Obj with type \p Ty if that is a constant.
-Constant *getInitialValueForObj(Value &Obj, Type &Ty);
+Constant *getInitialValueForObj(Value &Obj, Type &Ty,
+                                const TargetLibraryInfo *TLI);
 
 /// Collect all potential underlying objects of \p Ptr at position \p CtxI in
 /// \p Objects. Assumed information is used and dependences onto \p QueryingAA
@@ -1623,10 +1623,17 @@ public:
   ///
   /// This method will evaluate \p Pred on all (transitive) uses of the
   /// associated value and return true if \p Pred holds every time.
+  /// If uses are skipped in favor of equivalent ones, e.g., if we look through
+  /// memory, the \p EquivalentUseCB will be used to give the caller an idea
+  /// what original used was replaced by a new one (or new ones). The visit is
+  /// cut short if \p EquivalentUseCB returns false and the function will return
+  /// false as well.
   bool checkForAllUses(function_ref<bool(const Use &, bool &)> Pred,
                        const AbstractAttribute &QueryingAA, const Value &V,
                        bool CheckBBLivenessOnly = false,
-                       DepClassTy LivenessDepClass = DepClassTy::OPTIONAL);
+                       DepClassTy LivenessDepClass = DepClassTy::OPTIONAL,
+                       function_ref<bool(const Use &OldU, const Use &NewU)>
+                           EquivalentUseCB = nullptr);
 
   /// Emit a remark generically.
   ///
@@ -2354,11 +2361,11 @@ private:
 };
 
 /// Simple wrapper for a single bit (boolean) state.
-struct BooleanState : public IntegerStateBase<bool, 1, 0> {
-  using super = IntegerStateBase<bool, 1, 0>;
+struct BooleanState : public IntegerStateBase<bool, true, false> {
+  using super = IntegerStateBase<bool, true, false>;
   using base_t = IntegerStateBase::base_t;
 
-  BooleanState() : super() {}
+  BooleanState() {}
   BooleanState(base_t Assumed) : super(Assumed) {}
 
   /// Set the assumed value to \p Value but never below the known one.
diff --git a/llvm/include/llvm/Transforms/IPO/IROutliner.h b/llvm/include/llvm/Transforms/IPO/IROutliner.h
index 110c0b4dcf16..ed74c8ed0e96 100644
--- a/llvm/include/llvm/Transforms/IPO/IROutliner.h
+++ b/llvm/include/llvm/Transforms/IPO/IROutliner.h
@@ -95,6 +95,10 @@ struct OutlinableRegion {
   /// required for the following basic blocks in this case.
   bool EndsInBranch = false;
 
+  /// The PHIBlocks with their corresponding return block based on the return
+  /// value as the key.
+  DenseMap<Value *, BasicBlock *> PHIBlocks;
+
   /// Mapping of the argument number in the deduplicated function
   /// to a given constant, which is used when creating the arguments to the call
   /// to the newly created deduplicated function.  This is handled separately
@@ -182,7 +186,14 @@ public:
   IROutliner(function_ref<TargetTransformInfo &(Function &)> GTTI,
              function_ref<IRSimilarityIdentifier &(Module &)> GIRSI,
              function_ref<OptimizationRemarkEmitter &(Function &)> GORE)
-      : getTTI(GTTI), getIRSI(GIRSI), getORE(GORE) {}
+      : getTTI(GTTI), getIRSI(GIRSI), getORE(GORE) {
+    
+    // Check that the DenseMap implementation has not changed.
+    assert(DenseMapInfo<unsigned>::getEmptyKey() == (unsigned)-1 &&
+           "DenseMapInfo<unsigned>'s empty key isn't -1!");
+    assert(DenseMapInfo<unsigned>::getTombstoneKey() == (unsigned)-2 &&
+           "DenseMapInfo<unsigned>'s tombstone key isn't -2!");
+  }
   bool run(Module &M);
 
 private:
@@ -331,8 +342,7 @@ private:
     bool visitBranchInst(BranchInst &BI) { 
       return EnableBranches;
     }
-    // TODO: Determine a scheme to resolve when the labels are similar enough.
-    bool visitPHINode(PHINode &PN) { return false; }
+    bool visitPHINode(PHINode &PN) { return EnableBranches; }
     // TODO: Handle allocas.
     bool visitAllocaInst(AllocaInst &AI) { return false; }
     // VAArg instructions are not allowed since this could cause difficulty when
@@ -354,7 +364,15 @@ private:
     // that they have a name in these cases.
     bool visitCallInst(CallInst &CI) {
       Function *F = CI.getCalledFunction();
-      if (!F || CI.isIndirectCall() || !F->hasName())
+      bool IsIndirectCall = CI.isIndirectCall();
+      if (IsIndirectCall && !EnableIndirectCalls)
+        return false;
+      if (!F && !IsIndirectCall)
+        return false;
+      // Returning twice can cause issues with the state of the function call
+      // that were not expected when the function was used, so we do not include
+      // the call in outlined functions.
+      if (CI.canReturnTwice())
         return false;
       return true;
     }
@@ -373,6 +391,10 @@ private:
     // The flag variable that marks whether we should allow branch instructions
     // to be outlined.
     bool EnableBranches = false;
+
+    // The flag variable that marks whether we should allow indirect calls
+    // to be outlined.
+    bool EnableIndirectCalls = true;
   };
 
   /// A InstVisitor used to exclude certain instructions from being outlined.
diff --git a/llvm/include/llvm/Transforms/IPO/ModuleInliner.h b/llvm/include/llvm/Transforms/IPO/ModuleInliner.h
index 963d74d71003..7474e48aafaf 100644
--- a/llvm/include/llvm/Transforms/IPO/ModuleInliner.h
+++ b/llvm/include/llvm/Transforms/IPO/ModuleInliner.h
@@ -18,9 +18,6 @@
 
 namespace llvm {
 
-class AssumptionCacheTracker;
-class ProfileSummaryInfo;
-
 /// The module inliner pass for the new pass manager.
 ///
 /// This pass wires together the inlining utilities and the inline cost
diff --git a/llvm/include/llvm/Transforms/IPO/OpenMPOpt.h b/llvm/include/llvm/Transforms/IPO/OpenMPOpt.h
index c6ac5bd46f57..bf08336663b6 100644
--- a/llvm/include/llvm/Transforms/IPO/OpenMPOpt.h
+++ b/llvm/include/llvm/Transforms/IPO/OpenMPOpt.h
@@ -21,7 +21,7 @@ namespace omp {
 using Kernel = Function *;
 
 /// Set of kernels in the module
-using KernelSet = SmallPtrSet<Kernel, 4>;
+using KernelSet = SetVector<Kernel>;
 
 /// Helper to determine if \p M contains OpenMP.
 bool containsOpenMP(Module &M);
diff --git a/llvm/include/llvm/Transforms/IPO/PassManagerBuilder.h b/llvm/include/llvm/Transforms/IPO/PassManagerBuilder.h
index 7f321a688aff..3b944878a810 100644
--- a/llvm/include/llvm/Transforms/IPO/PassManagerBuilder.h
+++ b/llvm/include/llvm/Transforms/IPO/PassManagerBuilder.h
@@ -24,7 +24,6 @@ namespace llvm {
 class ModuleSummaryIndex;
 class Pass;
 class TargetLibraryInfoImpl;
-class TargetMachine;
 
 // The old pass manager infrastructure is hidden in a legacy namespace now.
 namespace legacy {
diff --git a/llvm/include/llvm/Transforms/InstCombine/InstCombiner.h b/llvm/include/llvm/Transforms/InstCombine/InstCombiner.h
index c6aee439b5a0..f8cb6dc73a6f 100644
--- a/llvm/include/llvm/Transforms/InstCombine/InstCombiner.h
+++ b/llvm/include/llvm/Transforms/InstCombine/InstCombiner.h
@@ -480,9 +480,9 @@ public:
     return llvm::ComputeNumSignBits(Op, DL, Depth, &AC, CxtI, &DT);
   }
 
-  unsigned ComputeMinSignedBits(const Value *Op, unsigned Depth = 0,
-                                const Instruction *CxtI = nullptr) const {
-    return llvm::ComputeMinSignedBits(Op, DL, Depth, &AC, CxtI, &DT);
+  unsigned ComputeMaxSignificantBits(const Value *Op, unsigned Depth = 0,
+                                     const Instruction *CxtI = nullptr) const {
+    return llvm::ComputeMaxSignificantBits(Op, DL, Depth, &AC, CxtI, &DT);
   }
 
   OverflowResult computeOverflowForUnsignedMul(const Value *LHS,
diff --git a/llvm/include/llvm/Transforms/Instrumentation/AddressSanitizerCommon.h b/llvm/include/llvm/Transforms/Instrumentation/AddressSanitizerCommon.h
index 6c351e3f8e1f..5a0fb835606a 100644
--- a/llvm/include/llvm/Transforms/Instrumentation/AddressSanitizerCommon.h
+++ b/llvm/include/llvm/Transforms/Instrumentation/AddressSanitizerCommon.h
@@ -26,6 +26,7 @@ class InterestingMemoryOperand {
 public:
   Use *PtrUse;
   bool IsWrite;
+  Type *OpType;
   uint64_t TypeSize;
   MaybeAlign Alignment;
   // The mask Value, if we're looking at a masked load/store.
@@ -34,7 +35,8 @@ public:
   InterestingMemoryOperand(Instruction *I, unsigned OperandNo, bool IsWrite,
                            class Type *OpType, MaybeAlign Alignment,
                            Value *MaybeMask = nullptr)
-      : IsWrite(IsWrite), Alignment(Alignment), MaybeMask(MaybeMask) {
+      : IsWrite(IsWrite), OpType(OpType), Alignment(Alignment),
+        MaybeMask(MaybeMask) {
     const DataLayout &DL = I->getModule()->getDataLayout();
     TypeSize = DL.getTypeStoreSizeInBits(OpType);
     PtrUse = &I->getOperandUse(OperandNo);
diff --git a/llvm/include/llvm/Transforms/Instrumentation/InstrProfiling.h b/llvm/include/llvm/Transforms/Instrumentation/InstrProfiling.h
index 94b156f3b137..64523d7d073c 100644
--- a/llvm/include/llvm/Transforms/Instrumentation/InstrProfiling.h
+++ b/llvm/include/llvm/Transforms/Instrumentation/InstrProfiling.h
@@ -100,7 +100,7 @@ private:
   ///
   /// If the counter array doesn't yet exist, the profile data variables
   /// referring to them will also be created.
-  GlobalVariable *getOrCreateRegionCounters(InstrProfIncrementInst *Inc);
+  GlobalVariable *getOrCreateRegionCounters(InstrProfInstBase *Inc);
 
   /// Emit the section with compressed function names.
   void emitNameData();
diff --git a/llvm/include/llvm/Transforms/Instrumentation/MemorySanitizer.h b/llvm/include/llvm/Transforms/Instrumentation/MemorySanitizer.h
index d47beb93397e..e5779dc775ba 100644
--- a/llvm/include/llvm/Transforms/Instrumentation/MemorySanitizer.h
+++ b/llvm/include/llvm/Transforms/Instrumentation/MemorySanitizer.h
@@ -19,11 +19,15 @@
 namespace llvm {
 
 struct MemorySanitizerOptions {
-  MemorySanitizerOptions() : MemorySanitizerOptions(0, false, false){};
-  MemorySanitizerOptions(int TrackOrigins, bool Recover, bool Kernel);
+  MemorySanitizerOptions() : MemorySanitizerOptions(0, false, false, false){};
+  MemorySanitizerOptions(int TrackOrigins, bool Recover, bool Kernel)
+      : MemorySanitizerOptions(TrackOrigins, Recover, Kernel, false) {}
+  MemorySanitizerOptions(int TrackOrigins, bool Recover, bool Kernel,
+                         bool EagerChecks);
   bool Kernel;
   int TrackOrigins;
   bool Recover;
+  bool EagerChecks;
 };
 
 // Insert MemorySanitizer instrumentation (detection of uninitialized reads)
diff --git a/llvm/include/llvm/Transforms/Scalar/GVN.h b/llvm/include/llvm/Transforms/Scalar/GVN.h
index cbe5057b9cde..9e660c92124e 100644
--- a/llvm/include/llvm/Transforms/Scalar/GVN.h
+++ b/llvm/include/llvm/Transforms/Scalar/GVN.h
@@ -39,11 +39,9 @@ class AssumptionCache;
 class BasicBlock;
 class BranchInst;
 class CallInst;
-class Constant;
 class ExtractValueInst;
 class Function;
 class FunctionPass;
-class IntrinsicInst;
 class LoadInst;
 class LoopInfo;
 class MemDepResult;
diff --git a/llvm/include/llvm/Transforms/Scalar/InstSimplifyPass.h b/llvm/include/llvm/Transforms/Scalar/InstSimplifyPass.h
index f5781e085f7b..09a4a95401d8 100644
--- a/llvm/include/llvm/Transforms/Scalar/InstSimplifyPass.h
+++ b/llvm/include/llvm/Transforms/Scalar/InstSimplifyPass.h
@@ -18,8 +18,6 @@
 
 namespace llvm {
 
-class FunctionPass;
-
 /// Run instruction simplification across each instruction in the function.
 ///
 /// Instruction simplification has useful constraints in some contexts:
diff --git a/llvm/include/llvm/Transforms/Scalar/LoopPassManager.h b/llvm/include/llvm/Transforms/Scalar/LoopPassManager.h
index 419729271a23..7ba9d65cae55 100644
--- a/llvm/include/llvm/Transforms/Scalar/LoopPassManager.h
+++ b/llvm/include/llvm/Transforms/Scalar/LoopPassManager.h
@@ -435,8 +435,7 @@ public:
                                      bool UseBlockFrequencyInfo = false,
                                      bool UseBranchProbabilityInfo = false,
                                      bool LoopNestMode = false)
-      : Pass(std::move(Pass)), LoopCanonicalizationFPM(),
-        UseMemorySSA(UseMemorySSA),
+      : Pass(std::move(Pass)), UseMemorySSA(UseMemorySSA),
         UseBlockFrequencyInfo(UseBlockFrequencyInfo),
         UseBranchProbabilityInfo(UseBranchProbabilityInfo),
         LoopNestMode(LoopNestMode) {
diff --git a/llvm/include/llvm/Transforms/Scalar/LoopReroll.h b/llvm/include/llvm/Transforms/Scalar/LoopReroll.h
index 6ae309e48a28..496e8df85ea0 100644
--- a/llvm/include/llvm/Transforms/Scalar/LoopReroll.h
+++ b/llvm/include/llvm/Transforms/Scalar/LoopReroll.h
@@ -14,8 +14,6 @@
 
 namespace llvm {
 
-class Function;
-
 class LoopRerollPass : public PassInfoMixin<LoopRerollPass> {
 public:
   PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
diff --git a/llvm/include/llvm/Transforms/Scalar/LoopUnrollAndJamPass.h b/llvm/include/llvm/Transforms/Scalar/LoopUnrollAndJamPass.h
index 6125fc7636a0..72663d3d62a8 100644
--- a/llvm/include/llvm/Transforms/Scalar/LoopUnrollAndJamPass.h
+++ b/llvm/include/llvm/Transforms/Scalar/LoopUnrollAndJamPass.h
@@ -13,7 +13,6 @@
 #include "llvm/Transforms/Scalar/LoopPassManager.h"
 
 namespace llvm {
-class Function;
 
 /// A simple loop rotation transformation.
 class LoopUnrollAndJamPass : public PassInfoMixin<LoopUnrollAndJamPass> {
diff --git a/llvm/include/llvm/Transforms/Scalar/SCCP.h b/llvm/include/llvm/Transforms/Scalar/SCCP.h
index 2d7c94918699..cd4100447880 100644
--- a/llvm/include/llvm/Transforms/Scalar/SCCP.h
+++ b/llvm/include/llvm/Transforms/Scalar/SCCP.h
@@ -32,8 +32,6 @@
 
 namespace llvm {
 
-class PostDominatorTree;
-
 /// This pass performs function-level constant propagation and merging.
 class SCCPPass : public PassInfoMixin<SCCPPass> {
 public:
diff --git a/llvm/include/llvm/Transforms/Scalar/SROA.h b/llvm/include/llvm/Transforms/Scalar/SROA.h
index f1a43435d89a..b74c45e71d95 100644
--- a/llvm/include/llvm/Transforms/Scalar/SROA.h
+++ b/llvm/include/llvm/Transforms/Scalar/SROA.h
@@ -27,7 +27,6 @@ class AllocaInst;
 class AssumptionCache;
 class DominatorTree;
 class Function;
-class Instruction;
 class LLVMContext;
 class PHINode;
 class SelectInst;
diff --git a/llvm/include/llvm/Transforms/Scalar/WarnMissedTransforms.h b/llvm/include/llvm/Transforms/Scalar/WarnMissedTransforms.h
index 2d5942a3f569..04a5f7e6ff38 100644
--- a/llvm/include/llvm/Transforms/Scalar/WarnMissedTransforms.h
+++ b/llvm/include/llvm/Transforms/Scalar/WarnMissedTransforms.h
@@ -17,8 +17,6 @@
 
 namespace llvm {
 class Function;
-class Loop;
-class LPMUpdater;
 
 // New pass manager boilerplate.
 class WarnMissedTransformationsPass
diff --git a/llvm/include/llvm/Transforms/Utils/AssumeBundleBuilder.h b/llvm/include/llvm/Transforms/Utils/AssumeBundleBuilder.h
index 5c06af9bc84c..a497722eece6 100644
--- a/llvm/include/llvm/Transforms/Utils/AssumeBundleBuilder.h
+++ b/llvm/include/llvm/Transforms/Utils/AssumeBundleBuilder.h
@@ -22,7 +22,6 @@
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
-class IntrinsicInst;
 class AssumptionCache;
 class DominatorTree;
 
diff --git a/llvm/include/llvm/Transforms/Utils/Cloning.h b/llvm/include/llvm/Transforms/Utils/Cloning.h
index 5a1f322b2054..fdc55bea99e7 100644
--- a/llvm/include/llvm/Transforms/Utils/Cloning.h
+++ b/llvm/include/llvm/Transforms/Utils/Cloning.h
@@ -33,13 +33,11 @@ class AAResults;
 class AllocaInst;
 class BasicBlock;
 class BlockFrequencyInfo;
-class CallInst;
 class CallGraph;
 class DebugInfoFinder;
 class DominatorTree;
 class Function;
 class Instruction;
-class InvokeInst;
 class Loop;
 class LoopInfo;
 class Module;
diff --git a/llvm/include/llvm/Transforms/Utils/CodeExtractor.h b/llvm/include/llvm/Transforms/Utils/CodeExtractor.h
index f08173e45a5b..8aed3d0e40d9 100644
--- a/llvm/include/llvm/Transforms/Utils/CodeExtractor.h
+++ b/llvm/include/llvm/Transforms/Utils/CodeExtractor.h
@@ -168,7 +168,7 @@ public:
     ///
     /// Based on the blocks used when constructing the code extractor,
     /// determine whether it is eligible for extraction.
-    /// 
+    ///
     /// Checks that varargs handling (with vastart and vaend) is only done in
     /// the outlined blocks.
     bool isEligible() const;
@@ -214,6 +214,10 @@ public:
     /// original block will be added to the outline region.
     BasicBlock *findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock);
 
+    /// Exclude a value from aggregate argument passing when extracting a code
+    /// region, passing it instead as a scalar.
+    void excludeArgFromAggregate(Value *Arg);
+
   private:
     struct LifetimeMarkerInfo {
       bool SinkLifeStart = false;
@@ -222,6 +226,8 @@ public:
       Instruction *LifeEnd = nullptr;
     };
 
+    ValueSet ExcludeArgsFromAggregate;
+
     LifetimeMarkerInfo
     getLifetimeMarkers(const CodeExtractorAnalysisCache &CEAC,
                        Instruction *Addr, BasicBlock *ExitBlock) const;
diff --git a/llvm/include/llvm/Transforms/Utils/CodeLayout.h b/llvm/include/llvm/Transforms/Utils/CodeLayout.h
index 987a5651a8b6..a0e5f8c7d014 100644
--- a/llvm/include/llvm/Transforms/Utils/CodeLayout.h
+++ b/llvm/include/llvm/Transforms/Utils/CodeLayout.h
@@ -20,8 +20,6 @@
 
 namespace llvm {
 
-class MachineBasicBlock;
-
 /// Find a layout of nodes (basic blocks) of a given CFG optimizing jump
 /// locality and thus processor I-cache utilization. This is achieved via
 /// increasing the number of fall-through jumps and co-locating frequently
diff --git a/llvm/include/llvm/Transforms/Utils/CtorUtils.h b/llvm/include/llvm/Transforms/Utils/CtorUtils.h
index 3625ee662b1c..3ef3ba244b43 100644
--- a/llvm/include/llvm/Transforms/Utils/CtorUtils.h
+++ b/llvm/include/llvm/Transforms/Utils/CtorUtils.h
@@ -17,7 +17,6 @@
 
 namespace llvm {
 
-class GlobalVariable;
 class Function;
 class Module;
 
diff --git a/llvm/include/llvm/Transforms/Utils/Evaluator.h b/llvm/include/llvm/Transforms/Utils/Evaluator.h
index 1b93b0af86e2..99e826bf855f 100644
--- a/llvm/include/llvm/Transforms/Utils/Evaluator.h
+++ b/llvm/include/llvm/Transforms/Utils/Evaluator.h
@@ -36,6 +36,49 @@ class TargetLibraryInfo;
 /// be iterated over after the evaluation is complete.  Once an evaluation call
 /// fails, the evaluation object should not be reused.
 class Evaluator {
+  struct MutableAggregate;
+
+  /// The evaluator represents values either as a Constant*, or as a
+  /// MutableAggregate, which allows changing individual aggregate elements
+  /// without creating a new interned Constant.
+  class MutableValue {
+    PointerUnion<Constant *, MutableAggregate *> Val;
+    void clear();
+    bool makeMutable();
+
+  public:
+    MutableValue(Constant *C) { Val = C; }
+    MutableValue(const MutableValue &) = delete;
+    MutableValue(MutableValue &&Other) {
+      Val = Other.Val;
+      Other.Val = nullptr;
+    }
+    ~MutableValue() { clear(); }
+
+    Type *getType() const {
+      if (auto *C = Val.dyn_cast<Constant *>())
+        return C->getType();
+      return Val.get<MutableAggregate *>()->Ty;
+    }
+
+    Constant *toConstant() const {
+      if (auto *C = Val.dyn_cast<Constant *>())
+        return C;
+      return Val.get<MutableAggregate *>()->toConstant();
+    }
+
+    Constant *read(Type *Ty, APInt Offset, const DataLayout &DL) const;
+    bool write(Constant *V, APInt Offset, const DataLayout &DL);
+  };
+
+  struct MutableAggregate {
+    Type *Ty;
+    SmallVector<MutableValue> Elements;
+
+    MutableAggregate(Type *Ty) : Ty(Ty) {}
+    Constant *toConstant() const;
+  };
+
 public:
   Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI)
       : DL(DL), TLI(TLI) {
@@ -57,8 +100,11 @@ public:
   bool EvaluateFunction(Function *F, Constant *&RetVal,
                         const SmallVectorImpl<Constant*> &ActualArgs);
 
-  const DenseMap<Constant *, Constant *> &getMutatedMemory() const {
-    return MutatedMemory;
+  DenseMap<GlobalVariable *, Constant *> getMutatedInitializers() const {
+    DenseMap<GlobalVariable *, Constant *> Result;
+    for (auto &Pair : MutatedMemory)
+      Result[Pair.first] = Pair.second.toConstant();
+    return Result;
   }
 
   const SmallPtrSetImpl<GlobalVariable *> &getInvariants() const {
@@ -81,7 +127,7 @@ private:
   }
 
   /// Casts call result to a type of bitcast call expression
-  Constant *castCallResultIfNeeded(Value *CallExpr, Constant *RV);
+  Constant *castCallResultIfNeeded(Type *ReturnType, Constant *RV);
 
   /// Given call site return callee and list of its formal arguments
   Function *getCalleeWithFormalArgs(CallBase &CB,
@@ -106,7 +152,7 @@ private:
   /// For each store we execute, we update this map.  Loads check this to get
   /// the most up-to-date value.  If evaluation is successful, this state is
   /// committed to the process.
-  DenseMap<Constant*, Constant*> MutatedMemory;
+  DenseMap<GlobalVariable *, MutableValue> MutatedMemory;
 
   /// To 'execute' an alloca, we create a temporary global variable to represent
   /// its body.  This vector is needed so we can delete the temporary globals
diff --git a/llvm/include/llvm/Transforms/Utils/GlobalStatus.h b/llvm/include/llvm/Transforms/Utils/GlobalStatus.h
index 78d7845c4353..775dd23d8f23 100644
--- a/llvm/include/llvm/Transforms/Utils/GlobalStatus.h
+++ b/llvm/include/llvm/Transforms/Utils/GlobalStatus.h
@@ -73,10 +73,6 @@ struct GlobalStatus {
   const Function *AccessingFunction = nullptr;
   bool HasMultipleAccessingFunctions = false;
 
-  /// Set to true if this global has a user that is not an instruction (e.g. a
-  /// constant expr or GV initializer).
-  bool HasNonInstructionUser = false;
-
   /// Set to the strongest atomic ordering requirement.
   AtomicOrdering Ordering = AtomicOrdering::NotAtomic;
 
diff --git a/llvm/include/llvm/Transforms/Utils/Local.h b/llvm/include/llvm/Transforms/Utils/Local.h
index a914c6e0925f..873127554b47 100644
--- a/llvm/include/llvm/Transforms/Utils/Local.h
+++ b/llvm/include/llvm/Transforms/Utils/Local.h
@@ -42,9 +42,7 @@ class BasicBlock;
 class BranchInst;
 class CallBase;
 class CallInst;
-class DbgDeclareInst;
 class DbgVariableIntrinsic;
-class DbgValueInst;
 class DIBuilder;
 class DomTreeUpdater;
 class Function;
@@ -243,7 +241,7 @@ inline Align getKnownAlignment(Value *V, const DataLayout &DL,
 CallInst *createCallMatchingInvoke(InvokeInst *II);
 
 /// This function converts the specified invoek into a normall call.
-void changeToCall(InvokeInst *II, DomTreeUpdater *DTU = nullptr);
+CallInst *changeToCall(InvokeInst *II, DomTreeUpdater *DTU = nullptr);
 
 ///===---------------------------------------------------------------------===//
 ///  Dbg Intrinsic utilities
diff --git a/llvm/include/llvm/Transforms/Utils/LoopPeel.h b/llvm/include/llvm/Transforms/Utils/LoopPeel.h
index 6f1b4a880457..7b6595c192de 100644
--- a/llvm/include/llvm/Transforms/Utils/LoopPeel.h
+++ b/llvm/include/llvm/Transforms/Utils/LoopPeel.h
@@ -32,7 +32,7 @@ gatherPeelingPreferences(Loop *L, ScalarEvolution &SE,
 
 void computePeelCount(Loop *L, unsigned LoopSize,
                       TargetTransformInfo::PeelingPreferences &PP,
-                      unsigned &TripCount, DominatorTree &DT,
+                      unsigned TripCount, DominatorTree &DT,
                       ScalarEvolution &SE, unsigned Threshold = UINT_MAX);
 
 } // end namespace llvm
diff --git a/llvm/include/llvm/Transforms/Utils/LoopUtils.h b/llvm/include/llvm/Transforms/Utils/LoopUtils.h
index e0a9115f61b0..3a712d78df67 100644
--- a/llvm/include/llvm/Transforms/Utils/LoopUtils.h
+++ b/llvm/include/llvm/Transforms/Utils/LoopUtils.h
@@ -37,7 +37,6 @@ class MemorySSAUpdater;
 class OptimizationRemarkEmitter;
 class PredIteratorCache;
 class ScalarEvolution;
-class ScalarEvolutionExpander;
 class SCEV;
 class SCEVExpander;
 class TargetLibraryInfo;
diff --git a/llvm/include/llvm/Transforms/Utils/MemoryOpRemark.h b/llvm/include/llvm/Transforms/Utils/MemoryOpRemark.h
index e5f8a46eaf23..8dc0f1e26a92 100644
--- a/llvm/include/llvm/Transforms/Utils/MemoryOpRemark.h
+++ b/llvm/include/llvm/Transforms/Utils/MemoryOpRemark.h
@@ -27,8 +27,6 @@ class Instruction;
 class IntrinsicInst;
 class Value;
 class OptimizationRemarkEmitter;
-class OptimizationRemarkMissed;
-class OptimizationRemarkAnalysis;
 class StoreInst;
 
 // FIXME: Once we get to more remarks like this one, we need to re-evaluate how
diff --git a/llvm/include/llvm/Transforms/Utils/ModuleUtils.h b/llvm/include/llvm/Transforms/Utils/ModuleUtils.h
index f53ba546dc5c..9bbe8ea7e1e8 100644
--- a/llvm/include/llvm/Transforms/Utils/ModuleUtils.h
+++ b/llvm/include/llvm/Transforms/Utils/ModuleUtils.h
@@ -92,7 +92,7 @@ void appendToCompilerUsed(Module &M, ArrayRef<GlobalValue *> Values);
 /// DeadComdatFunctions are those where every member of the comdat is listed
 /// and thus removing them is safe (provided *all* are removed).
 void filterDeadComdatFunctions(
-    Module &M, SmallVectorImpl<Function *> &DeadComdatFunctions);
+    SmallVectorImpl<Function *> &DeadComdatFunctions);
 
 /// Produce a unique identifier for this module by taking the MD5 sum of
 /// the names of the module's strong external symbols that are not comdat
diff --git a/llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h b/llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h
index efc3cc775e11..277eb7acf238 100644
--- a/llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h
+++ b/llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h
@@ -18,6 +18,7 @@
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/Analysis/InstSimplifyFolder.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/ScalarEvolutionNormalization.h"
 #include "llvm/Analysis/TargetFolder.h"
@@ -122,7 +123,7 @@ class SCEVExpander : public SCEVVisitor<SCEVExpander, Value *> {
   /// "expanded" form.
   bool LSRMode;
 
-  typedef IRBuilder<TargetFolder, IRBuilderCallbackInserter> BuilderType;
+  typedef IRBuilder<InstSimplifyFolder, IRBuilderCallbackInserter> BuilderType;
   BuilderType Builder;
 
   // RAII object that stores the current insertion point and restores it when
@@ -178,7 +179,7 @@ public:
       : SE(se), DL(DL), IVName(name), PreserveLCSSA(PreserveLCSSA),
         IVIncInsertLoop(nullptr), IVIncInsertPos(nullptr), CanonicalMode(true),
         LSRMode(false),
-        Builder(se.getContext(), TargetFolder(DL),
+        Builder(se.getContext(), InstSimplifyFolder(DL),
                 IRBuilderCallbackInserter(
                     [this](Instruction *I) { rememberInstruction(I); })) {
 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
@@ -450,6 +451,14 @@ private:
   /// Determine the most "relevant" loop for the given SCEV.
   const Loop *getRelevantLoop(const SCEV *);
 
+  Value *expandSMaxExpr(const SCEVNAryExpr *S);
+
+  Value *expandUMaxExpr(const SCEVNAryExpr *S);
+
+  Value *expandSMinExpr(const SCEVNAryExpr *S);
+
+  Value *expandUMinExpr(const SCEVNAryExpr *S);
+
   Value *visitConstant(const SCEVConstant *S) { return S->getValue(); }
 
   Value *visitPtrToIntExpr(const SCEVPtrToIntExpr *S);
@@ -476,6 +485,8 @@ private:
 
   Value *visitUMinExpr(const SCEVUMinExpr *S);
 
+  Value *visitSequentialUMinExpr(const SCEVSequentialUMinExpr *S);
+
   Value *visitUnknown(const SCEVUnknown *S) { return S->getValue(); }
 
   void rememberInstruction(Value *I);
@@ -504,15 +515,13 @@ private:
 class SCEVExpanderCleaner {
   SCEVExpander &Expander;
 
-  DominatorTree &DT;
-
   /// Indicates whether the result of the expansion is used. If false, the
   /// instructions added during expansion are removed.
   bool ResultUsed;
 
 public:
-  SCEVExpanderCleaner(SCEVExpander &Expander, DominatorTree &DT)
-      : Expander(Expander), DT(DT), ResultUsed(false) {}
+  SCEVExpanderCleaner(SCEVExpander &Expander)
+      : Expander(Expander), ResultUsed(false) {}
 
   ~SCEVExpanderCleaner() { cleanup(); }
 
diff --git a/llvm/include/llvm/Transforms/Utils/UnifyFunctionExitNodes.h b/llvm/include/llvm/Transforms/Utils/UnifyFunctionExitNodes.h
index 20b360212506..461669d6a217 100644
--- a/llvm/include/llvm/Transforms/Utils/UnifyFunctionExitNodes.h
+++ b/llvm/include/llvm/Transforms/Utils/UnifyFunctionExitNodes.h
@@ -19,8 +19,6 @@
 
 namespace llvm {
 
-class BasicBlock;
-
 class UnifyFunctionExitNodesLegacyPass : public FunctionPass {
 public:
   static char ID; // Pass identification, replacement for typeid