vendor/llvm/llvm-trunk-r338150

22 files changed, 443 insertions, 267 deletions

diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h
index 74f75509f550..3dfc73b64842 100644
--- a/include/llvm/Transforms/Utils/BasicBlockUtils.h
+++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h
@@ -27,6 +27,7 @@ namespace llvm {
 
 class BlockFrequencyInfo;
 class BranchProbabilityInfo;
+class DeferredDominance;
 class DominatorTree;
 class Function;
 class Instruction;
@@ -38,7 +39,7 @@ class TargetLibraryInfo;
 class Value;
 
 /// Delete the specified block, which must have no predecessors.
-void DeleteDeadBlock(BasicBlock *BB);
+void DeleteDeadBlock(BasicBlock *BB, DeferredDominance *DDT = nullptr);
 
 /// We know that BB has one predecessor. If there are any single-entry PHI nodes
 /// in it, fold them away. This handles the case when all entries to the PHI
@@ -57,7 +58,8 @@ bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr);
 /// value indicates success or failure.
 bool MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT = nullptr,
                                LoopInfo *LI = nullptr,
-                               MemoryDependenceResults *MemDep = nullptr);
+                               MemoryDependenceResults *MemDep = nullptr,
+                               DeferredDominance *DDT = nullptr);
 
 /// Replace all uses of an instruction (specified by BI) with a value, then
 /// remove and delete the original instruction.
diff --git a/include/llvm/Transforms/Utils/BuildLibCalls.h b/include/llvm/Transforms/Utils/BuildLibCalls.h
index a067a685b837..bdcdf6f361f2 100644
--- a/include/llvm/Transforms/Utils/BuildLibCalls.h
+++ b/include/llvm/Transforms/Utils/BuildLibCalls.h
@@ -15,6 +15,7 @@
 #ifndef LLVM_TRANSFORMS_UTILS_BUILDLIBCALLS_H
 #define LLVM_TRANSFORMS_UTILS_BUILDLIBCALLS_H
 
+#include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/IRBuilder.h"
 
 namespace llvm {
@@ -29,6 +30,12 @@ namespace llvm {
   /// Returns true if any attributes were set and false otherwise.
   bool inferLibFuncAttributes(Function &F, const TargetLibraryInfo &TLI);
 
+  /// Check whether the overloaded unary floating point function
+  /// corresponding to \a Ty is available.
+  bool hasUnaryFloatFn(const TargetLibraryInfo *TLI, Type *Ty,
+                       LibFunc DoubleFn, LibFunc FloatFn,
+                       LibFunc LongDoubleFn);
+
   /// Return V if it is an i8*, otherwise cast it to i8*.
   Value *castToCStr(Value *V, IRBuilder<> &B);
 
@@ -104,15 +111,54 @@ namespace llvm {
   Value *emitFPutC(Value *Char, Value *File, IRBuilder<> &B,
                    const TargetLibraryInfo *TLI);
 
-  /// Emit a call to the puts function. Str is required to be a pointer and
+  /// Emit a call to the fputc_unlocked function. This assumes that Char is an
+  /// i32, and File is a pointer to FILE.
+  Value *emitFPutCUnlocked(Value *Char, Value *File, IRBuilder<> &B,
+                           const TargetLibraryInfo *TLI);
+
+  /// Emit a call to the fputs function. Str is required to be a pointer and
   /// File is a pointer to FILE.
   Value *emitFPutS(Value *Str, Value *File, IRBuilder<> &B,
                    const TargetLibraryInfo *TLI);
 
+  /// Emit a call to the fputs_unlocked function. Str is required to be a
+  /// pointer and File is a pointer to FILE.
+  Value *emitFPutSUnlocked(Value *Str, Value *File, IRBuilder<> &B,
+                           const TargetLibraryInfo *TLI);
+
   /// Emit a call to the fwrite function. This assumes that Ptr is a pointer,
   /// Size is an 'intptr_t', and File is a pointer to FILE.
   Value *emitFWrite(Value *Ptr, Value *Size, Value *File, IRBuilder<> &B,
                     const DataLayout &DL, const TargetLibraryInfo *TLI);
+
+  /// Emit a call to the malloc function.
+  Value *emitMalloc(Value *Num, IRBuilder<> &B, const DataLayout &DL,
+                    const TargetLibraryInfo *TLI);
+
+  /// Emit a call to the calloc function.
+  Value *emitCalloc(Value *Num, Value *Size, const AttributeList &Attrs,
+                    IRBuilder<> &B, const TargetLibraryInfo &TLI);
+
+  /// Emit a call to the fwrite_unlocked function. This assumes that Ptr is a
+  /// pointer, Size is an 'intptr_t', N is nmemb and File is a pointer to FILE.
+  Value *emitFWriteUnlocked(Value *Ptr, Value *Size, Value *N, Value *File,
+                            IRBuilder<> &B, const DataLayout &DL,
+                            const TargetLibraryInfo *TLI);
+
+  /// Emit a call to the fgetc_unlocked function. File is a pointer to FILE.
+  Value *emitFGetCUnlocked(Value *File, IRBuilder<> &B,
+                           const TargetLibraryInfo *TLI);
+
+  /// Emit a call to the fgets_unlocked function. Str is required to be a
+  /// pointer, Size is an i32 and File is a pointer to FILE.
+  Value *emitFGetSUnlocked(Value *Str, Value *Size, Value *File, IRBuilder<> &B,
+                           const TargetLibraryInfo *TLI);
+
+  /// Emit a call to the fread_unlocked function. This assumes that Ptr is a
+  /// pointer, Size is an 'intptr_t', N is nmemb and File is a pointer to FILE.
+  Value *emitFReadUnlocked(Value *Ptr, Value *Size, Value *N, Value *File,
+                           IRBuilder<> &B, const DataLayout &DL,
+                           const TargetLibraryInfo *TLI);
 }
 
 #endif
diff --git a/include/llvm/Transforms/Utils/Cloning.h b/include/llvm/Transforms/Utils/Cloning.h
index 178bae76cef6..7531fb2d69b3 100644
--- a/include/llvm/Transforms/Utils/Cloning.h
+++ b/include/llvm/Transforms/Utils/Cloning.h
@@ -49,15 +49,15 @@ class ReturnInst;
 
 /// Return an exact copy of the specified module
 ///
-std::unique_ptr<Module> CloneModule(const Module *M);
-std::unique_ptr<Module> CloneModule(const Module *M, ValueToValueMapTy &VMap);
+std::unique_ptr<Module> CloneModule(const Module &M);
+std::unique_ptr<Module> CloneModule(const Module &M, ValueToValueMapTy &VMap);
 
 /// Return a copy of the specified module. The ShouldCloneDefinition function
 /// controls whether a specific GlobalValue's definition is cloned. If the
 /// function returns false, the module copy will contain an external reference
 /// in place of the global definition.
 std::unique_ptr<Module>
-CloneModule(const Module *M, ValueToValueMapTy &VMap,
+CloneModule(const Module &M, ValueToValueMapTy &VMap,
             function_ref<bool(const GlobalValue *)> ShouldCloneDefinition);
 
 /// ClonedCodeInfo - This struct can be used to capture information about code
@@ -240,7 +240,7 @@ bool InlineFunction(CallSite CS, InlineFunctionInfo &IFI,
                     AAResults *CalleeAAR = nullptr, bool InsertLifetime = true,
                     Function *ForwardVarArgsTo = nullptr);
 
-/// \brief Clones a loop \p OrigLoop.  Returns the loop and the blocks in \p
+/// Clones a loop \p OrigLoop.  Returns the loop and the blocks in \p
 /// Blocks.
 ///
 /// Updates LoopInfo and DominatorTree assuming the loop is dominated by block
@@ -252,7 +252,7 @@ Loop *cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB,
                              DominatorTree *DT,
                              SmallVectorImpl<BasicBlock *> &Blocks);
 
-/// \brief Remaps instructions in \p Blocks using the mapping in \p VMap.
+/// Remaps instructions in \p Blocks using the mapping in \p VMap.
 void remapInstructionsInBlocks(const SmallVectorImpl<BasicBlock *> &Blocks,
                                ValueToValueMapTy &VMap);
 
@@ -265,7 +265,8 @@ void remapInstructionsInBlocks(const SmallVectorImpl<BasicBlock *> &Blocks,
 BasicBlock *
 DuplicateInstructionsInSplitBetween(BasicBlock *BB, BasicBlock *PredBB,
                                     Instruction *StopAt,
-                                    ValueToValueMapTy &ValueMapping);
+                                    ValueToValueMapTy &ValueMapping,
+                                    DominatorTree *DT = nullptr);
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_CLONING_H
diff --git a/include/llvm/Transforms/Utils/CodeExtractor.h b/include/llvm/Transforms/Utils/CodeExtractor.h
index 63d34511102d..fab8334d4c66 100644
--- a/include/llvm/Transforms/Utils/CodeExtractor.h
+++ b/include/llvm/Transforms/Utils/CodeExtractor.h
@@ -34,7 +34,7 @@ class Module;
 class Type;
 class Value;
 
-  /// \brief Utility class for extracting code into a new function.
+  /// Utility class for extracting code into a new function.
   ///
   /// This utility provides a simple interface for extracting some sequence of
   /// code into its own function, replacing it with a call to that function. It
@@ -65,20 +65,22 @@ class Value;
     Type *RetTy;
 
   public:
-    /// \brief Create a code extractor for a sequence of blocks.
+    /// Create a code extractor for a sequence of blocks.
     ///
     /// Given a sequence of basic blocks where the first block in the sequence
     /// dominates the rest, prepare a code extractor object for pulling this
     /// sequence out into its new function. When a DominatorTree is also given,
     /// extra checking and transformations are enabled. If AllowVarArgs is true,
     /// vararg functions can be extracted. This is safe, if all vararg handling
-    /// code is extracted, including vastart.
+    /// code is extracted, including vastart. If AllowAlloca is true, then
+    /// extraction of blocks containing alloca instructions would be possible,
+    /// however code extractor won't validate whether extraction is legal. 
     CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT = nullptr,
                   bool AggregateArgs = false, BlockFrequencyInfo *BFI = nullptr,
                   BranchProbabilityInfo *BPI = nullptr,
-                  bool AllowVarArgs = false);
+                  bool AllowVarArgs = false, bool AllowAlloca = false);
 
-    /// \brief Create a code extractor for a loop body.
+    /// Create a code extractor for a loop body.
     ///
     /// Behaves just like the generic code sequence constructor, but uses the
     /// block sequence of the loop.
@@ -86,27 +88,19 @@ class Value;
                   BlockFrequencyInfo *BFI = nullptr,
                   BranchProbabilityInfo *BPI = nullptr);
 
-    /// \brief Check to see if a block is valid for extraction.
-    ///
-    /// Blocks containing EHPads, allocas and invokes are not valid. If
-    /// AllowVarArgs is true, blocks with vastart can be extracted. This is
-    /// safe, if all vararg handling code is extracted, including vastart.
-    static bool isBlockValidForExtraction(const BasicBlock &BB,
-                                          bool AllowVarArgs);
-
-    /// \brief Perform the extraction, returning the new function.
+    /// Perform the extraction, returning the new function.
     ///
     /// Returns zero when called on a CodeExtractor instance where isEligible
     /// returns false.
     Function *extractCodeRegion();
 
-    /// \brief Test whether this code extractor is eligible.
+    /// Test whether this code extractor is eligible.
     ///
     /// Based on the blocks used when constructing the code extractor,
     /// determine whether it is eligible for extraction.
     bool isEligible() const { return !Blocks.empty(); }
 
-    /// \brief Compute the set of input values and output values for the code.
+    /// Compute the set of input values and output values for the code.
     ///
     /// These can be used either when performing the extraction or to evaluate
     /// the expected size of a call to the extracted function. Note that this
diff --git a/include/llvm/Transforms/Utils/Evaluator.h b/include/llvm/Transforms/Utils/Evaluator.h
index 0e987b93177a..9908ae6fd393 100644
--- a/include/llvm/Transforms/Utils/Evaluator.h
+++ b/include/llvm/Transforms/Utils/Evaluator.h
@@ -18,6 +18,7 @@
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/CallSite.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Support/Casting.h"
@@ -73,6 +74,18 @@ public:
     ValueStack.back()[V] = C;
   }
 
+  /// Given call site return callee and list of its formal arguments
+  Function *getCalleeWithFormalArgs(CallSite &CS,
+                                    SmallVector<Constant *, 8> &Formals);
+
+  /// Given call site and callee returns list of callee formal argument
+  /// values converting them when necessary
+  bool getFormalParams(CallSite &CS, Function *F,
+                       SmallVector<Constant *, 8> &Formals);
+
+  /// Casts call result to a type of bitcast call expression
+  Constant *castCallResultIfNeeded(Value *CallExpr, Constant *RV);
+
   const DenseMap<Constant*, Constant*> &getMutatedMemory() const {
     return MutatedMemory;
   }
diff --git a/include/llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h b/include/llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h
index b7a3d130aa11..b55a9893bcf7 100644
--- a/include/llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h
+++ b/include/llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h
@@ -22,7 +22,7 @@
 namespace llvm {
 class Module;
 class Function;
-/// \brief Calculate and dump ThinLTO specific inliner stats.
+/// Calculate and dump ThinLTO specific inliner stats.
 /// The main statistics are:
 /// (1) Number of inlined imported functions,
 /// (2) Number of imported functions inlined into importing module (indirect),
diff --git a/include/llvm/Transforms/Utils/IntegerDivision.h b/include/llvm/Transforms/Utils/IntegerDivision.h
index 0ec3321b9cf8..5d9927eb51b2 100644
--- a/include/llvm/Transforms/Utils/IntegerDivision.h
+++ b/include/llvm/Transforms/Utils/IntegerDivision.h
@@ -29,7 +29,7 @@ namespace llvm {
   /// e.g. when more information about the operands are known. Implements both
   /// 32bit and 64bit scalar division.
   ///
-  /// @brief Replace Rem with generated code.
+  /// Replace Rem with generated code.
   bool expandRemainder(BinaryOperator *Rem);
 
   /// Generate code to divide two integers, replacing Div with the generated
@@ -38,7 +38,7 @@ namespace llvm {
   /// when more information about the operands are known. Implements both
   /// 32bit and 64bit scalar division.
   ///
-  /// @brief Replace Div with generated code.
+  /// Replace Div with generated code.
   bool expandDivision(BinaryOperator* Div);
 
   /// Generate code to calculate the remainder of two integers, replacing Rem
@@ -46,26 +46,26 @@ namespace llvm {
   /// makes it useful for targets with little or no support for less than
   /// 32 bit arithmetic.
   ///
-  /// @brief Replace Rem with generated code.
+  /// Replace Rem with generated code.
   bool expandRemainderUpTo32Bits(BinaryOperator *Rem);
 
   /// Generate code to calculate the remainder of two integers, replacing Rem
   /// with the generated code. Uses ExpandReminder with a 64bit Rem.
   ///
-  /// @brief Replace Rem with generated code.
+  /// Replace Rem with generated code.
   bool expandRemainderUpTo64Bits(BinaryOperator *Rem);
 
   /// Generate code to divide two integers, replacing Div with the generated
   /// code. Uses ExpandDivision with a 32bit Div which makes it useful for
   /// targets with little or no support for less than 32 bit arithmetic.
   ///
-  /// @brief Replace Rem with generated code.
+  /// Replace Rem with generated code.
   bool expandDivisionUpTo32Bits(BinaryOperator *Div);
 
   /// Generate code to divide two integers, replacing Div with the generated
   /// code. Uses ExpandDivision with a 64bit Div.
   ///
-  /// @brief Replace Rem with generated code.
+  /// Replace Rem with generated code.
   bool expandDivisionUpTo64Bits(BinaryOperator *Div);
 
 } // End llvm namespace
diff --git a/include/llvm/Transforms/Utils/Local.h b/include/llvm/Transforms/Utils/Local.h
index 01db88bc15c2..b8df32565723 100644
--- a/include/llvm/Transforms/Utils/Local.h
+++ b/include/llvm/Transforms/Utils/Local.h
@@ -16,10 +16,12 @@
 #define LLVM_TRANSFORMS_UTILS_LOCAL_H
 
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/Utils/Local.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
@@ -117,7 +119,8 @@ struct SimplifyCFGOptions {
 /// conditions and indirectbr addresses this might make dead if
 /// DeleteDeadConditions is true.
 bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false,
-                            const TargetLibraryInfo *TLI = nullptr);
+                            const TargetLibraryInfo *TLI = nullptr,
+                            DeferredDominance *DDT = nullptr);
 
 //===----------------------------------------------------------------------===//
 //  Local dead code elimination.
@@ -140,6 +143,18 @@ bool wouldInstructionBeTriviallyDead(Instruction *I,
 bool RecursivelyDeleteTriviallyDeadInstructions(Value *V,
                                         const TargetLibraryInfo *TLI = nullptr);
 
+/// Delete all of the instructions in `DeadInsts`, and all other instructions
+/// that deleting these in turn causes to be trivially dead.
+///
+/// The initial instructions in the provided vector must all have empty use
+/// lists and satisfy `isInstructionTriviallyDead`.
+///
+/// `DeadInsts` will be used as scratch storage for this routine and will be
+/// empty afterward.
+void RecursivelyDeleteTriviallyDeadInstructions(
+    SmallVectorImpl<Instruction *> &DeadInsts,
+    const TargetLibraryInfo *TLI = nullptr);
+
 /// If the specified value is an effectively dead PHI node, due to being a
 /// def-use chain of single-use nodes that either forms a cycle or is terminated
 /// by a trivially dead instruction, delete it. If that makes any of its
@@ -171,18 +186,21 @@ bool SimplifyInstructionsInBlock(BasicBlock *BB,
 ///
 /// .. and delete the predecessor corresponding to the '1', this will attempt to
 /// recursively fold the 'and' to 0.
-void RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred);
+void RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred,
+                                  DeferredDominance *DDT = nullptr);
 
 /// BB is a block with one predecessor and its predecessor is known to have one
 /// successor (BB!). Eliminate the edge between them, moving the instructions in
 /// the predecessor into BB. This deletes the predecessor block.
-void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DominatorTree *DT = nullptr);
+void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DominatorTree *DT = nullptr,
+                                 DeferredDominance *DDT = nullptr);
 
 /// BB is known to contain an unconditional branch, and contains no instructions
 /// other than PHI nodes, potential debug intrinsics and the branch. If
 /// possible, eliminate BB by rewriting all the predecessors to branch to the
 /// successor block and return true. If we can't transform, return false.
-bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB);
+bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
+                                             DeferredDominance *DDT = nullptr);
 
 /// Check for and eliminate duplicate PHI nodes in this block. This doesn't try
 /// to be clever about PHI nodes which differ only in the order of the incoming
@@ -246,72 +264,6 @@ inline unsigned getKnownAlignment(Value *V, const DataLayout &DL,
   return getOrEnforceKnownAlignment(V, 0, DL, CxtI, AC, DT);
 }
 
-/// Given a getelementptr instruction/constantexpr, emit the code necessary to
-/// compute the offset from the base pointer (without adding in the base
-/// pointer). Return the result as a signed integer of intptr size.
-/// When NoAssumptions is true, no assumptions about index computation not
-/// overflowing is made.
-template <typename IRBuilderTy>
-Value *EmitGEPOffset(IRBuilderTy *Builder, const DataLayout &DL, User *GEP,
-                     bool NoAssumptions = false) {
-  GEPOperator *GEPOp = cast<GEPOperator>(GEP);
-  Type *IntPtrTy = DL.getIntPtrType(GEP->getType());
-  Value *Result = Constant::getNullValue(IntPtrTy);
-
-  // If the GEP is inbounds, we know that none of the addressing operations will
-  // overflow in an unsigned sense.
-  bool isInBounds = GEPOp->isInBounds() && !NoAssumptions;
-
-  // Build a mask for high order bits.
-  unsigned IntPtrWidth = IntPtrTy->getScalarType()->getIntegerBitWidth();
-  uint64_t PtrSizeMask =
-      std::numeric_limits<uint64_t>::max() >> (64 - IntPtrWidth);
-
-  gep_type_iterator GTI = gep_type_begin(GEP);
-  for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end(); i != e;
-       ++i, ++GTI) {
-    Value *Op = *i;
-    uint64_t Size = DL.getTypeAllocSize(GTI.getIndexedType()) & PtrSizeMask;
-    if (Constant *OpC = dyn_cast<Constant>(Op)) {
-      if (OpC->isZeroValue())
-        continue;
-
-      // Handle a struct index, which adds its field offset to the pointer.
-      if (StructType *STy = GTI.getStructTypeOrNull()) {
-        if (OpC->getType()->isVectorTy())
-          OpC = OpC->getSplatValue();
-
-        uint64_t OpValue = cast<ConstantInt>(OpC)->getZExtValue();
-        Size = DL.getStructLayout(STy)->getElementOffset(OpValue);
-
-        if (Size)
-          Result = Builder->CreateAdd(Result, ConstantInt::get(IntPtrTy, Size),
-                                      GEP->getName()+".offs");
-        continue;
-      }
-
-      Constant *Scale = ConstantInt::get(IntPtrTy, Size);
-      Constant *OC = ConstantExpr::getIntegerCast(OpC, IntPtrTy, true /*SExt*/);
-      Scale = ConstantExpr::getMul(OC, Scale, isInBounds/*NUW*/);
-      // Emit an add instruction.
-      Result = Builder->CreateAdd(Result, Scale, GEP->getName()+".offs");
-      continue;
-    }
-    // Convert to correct type.
-    if (Op->getType() != IntPtrTy)
-      Op = Builder->CreateIntCast(Op, IntPtrTy, true, Op->getName()+".c");
-    if (Size != 1) {
-      // We'll let instcombine(mul) convert this to a shl if possible.
-      Op = Builder->CreateMul(Op, ConstantInt::get(IntPtrTy, Size),
-                              GEP->getName()+".idx", isInBounds /*NUW*/);
-    }
-
-    // Emit an add instruction.
-    Result = Builder->CreateAdd(Op, Result, GEP->getName()+".offs");
-  }
-  return Result;
-}
-
 ///===---------------------------------------------------------------------===//
 ///  Dbg Intrinsic utilities
 ///
@@ -335,6 +287,10 @@ void ConvertDebugDeclareToDebugValue(DbgInfoIntrinsic *DII,
 /// llvm.dbg.value intrinsics.
 bool LowerDbgDeclare(Function &F);
 
+/// Propagate dbg.value intrinsics through the newly inserted PHIs.
+void insertDebugValuesForPHIs(BasicBlock *BB,
+                              SmallVectorImpl<PHINode *> &InsertedPHIs);
+
 /// Finds all intrinsics declaring local variables as living in the memory that
 /// 'V' points to. This may include a mix of dbg.declare and
 /// dbg.addr intrinsics.
@@ -343,6 +299,9 @@ TinyPtrVector<DbgInfoIntrinsic *> FindDbgAddrUses(Value *V);
 /// Finds the llvm.dbg.value intrinsics describing a value.
 void findDbgValues(SmallVectorImpl<DbgValueInst *> &DbgValues, Value *V);
 
+/// Finds the debug info intrinsics describing a value.
+void findDbgUsers(SmallVectorImpl<DbgInfoIntrinsic *> &DbgInsts, Value *V);
+
 /// Replaces llvm.dbg.declare instruction when the address it
 /// describes is replaced with a new value. If Deref is true, an
 /// additional DW_OP_deref is prepended to the expression. If Offset
@@ -357,7 +316,7 @@ bool replaceDbgDeclare(Value *Address, Value *NewAddress,
 /// DW_OP_deref is prepended to the expression. If Offset is non-zero,
 /// a constant displacement is added to the expression (between the
 /// optional Deref operations). Offset can be negative. The new
-/// llvm.dbg.declare is inserted immediately before AI.
+/// llvm.dbg.declare is inserted immediately after AI.
 bool replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
                                 DIBuilder &Builder, bool DerefBefore,
                                 int Offset, bool DerefAfter);
@@ -370,10 +329,27 @@ bool replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
 void replaceDbgValueForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
                               DIBuilder &Builder, int Offset = 0);
 
-/// Assuming the instruction \p I is going to be deleted, attempt to salvage any
-/// dbg.value intrinsics referring to \p I by rewriting its effect into a
-/// DIExpression.
-void salvageDebugInfo(Instruction &I);
+/// Assuming the instruction \p I is going to be deleted, attempt to salvage
+/// debug users of \p I by writing the effect of \p I in a DIExpression.
+/// Returns true if any debug users were updated.
+bool salvageDebugInfo(Instruction &I);
+
+/// Point debug users of \p From to \p To or salvage them. Use this function
+/// only when replacing all uses of \p From with \p To, with a guarantee that
+/// \p From is going to be deleted.
+///
+/// Follow these rules to prevent use-before-def of \p To:
+///   . If \p To is a linked Instruction, set \p DomPoint to \p To.
+///   . If \p To is an unlinked Instruction, set \p DomPoint to the Instruction
+///     \p To will be inserted after.
+///   . If \p To is not an Instruction (e.g a Constant), the choice of
+///     \p DomPoint is arbitrary. Pick \p From for simplicity.
+///
+/// If a debug user cannot be preserved without reordering variable updates or
+/// introducing a use-before-def, it is either salvaged (\ref salvageDebugInfo)
+/// or deleted. Returns true if any debug users were updated.
+bool replaceAllDbgUsesWith(Instruction &From, Value &To, Instruction &DomPoint,
+                           DominatorTree &DT);
 
 /// Remove all instructions from a basic block other than it's terminator
 /// and any present EH pad instructions.
@@ -382,7 +358,8 @@ unsigned removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB);
 /// Insert an unreachable instruction before the specified
 /// instruction, making it and the rest of the code in the block dead.
 unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap,
-                             bool PreserveLCSSA = false);
+                             bool PreserveLCSSA = false,
+                             DeferredDominance *DDT = nullptr);
 
 /// Convert the CallInst to InvokeInst with the specified unwind edge basic
 /// block.  This also splits the basic block where CI is located, because
@@ -397,12 +374,13 @@ BasicBlock *changeToInvokeAndSplitBasicBlock(CallInst *CI,
 ///
 /// \param BB  Block whose terminator will be replaced.  Its terminator must
 ///            have an unwind successor.
-void removeUnwindEdge(BasicBlock *BB);
+void removeUnwindEdge(BasicBlock *BB, DeferredDominance *DDT = nullptr);
 
 /// Remove all blocks that can not be reached from the function's entry.
 ///
 /// Returns true if any basic block was removed.
-bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI = nullptr);
+bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI = nullptr,
+                             DeferredDominance *DDT = nullptr);
 
 /// Combine the metadata of two instructions so that K can replace J
 ///
diff --git a/include/llvm/Transforms/Utils/LoopRotationUtils.h b/include/llvm/Transforms/Utils/LoopRotationUtils.h
new file mode 100644
index 000000000000..231e5bbb6dee
--- /dev/null
+++ b/include/llvm/Transforms/Utils/LoopRotationUtils.h
@@ -0,0 +1,40 @@
+//===- LoopRotationUtils.h - Utilities to perform loop rotation -*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file provides utilities to convert a loop into a loop with bottom test.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_LOOPROTATIONUTILS_H
+#define LLVM_TRANSFORMS_UTILS_LOOPROTATIONUTILS_H
+
+namespace llvm {
+
+class AssumptionCache;
+class DominatorTree;
+class Loop;
+class LoopInfo;
+class ScalarEvolution;
+struct SimplifyQuery;
+class TargetTransformInfo;
+
+/// Convert a loop into a loop with bottom test. It may
+/// perform loop latch simplication as well if the flag RotationOnly
+/// is false. The flag Threshold represents the size threshold of the loop
+/// header. If the loop header's size exceeds the threshold, the loop rotation
+/// will give up. The flag IsUtilMode controls the heuristic used in the
+/// LoopRotation. If it is true, the profitability heuristic will be ignored.
+bool LoopRotation(Loop *L, LoopInfo *LI, const TargetTransformInfo *TTI,
+                  AssumptionCache *AC, DominatorTree *DT, ScalarEvolution *SE,
+                  const SimplifyQuery &SQ, bool RotationOnly,
+                  unsigned Threshold, bool IsUtilMode);
+
+} // namespace llvm
+
+#endif
diff --git a/include/llvm/Transforms/Utils/LoopSimplify.h b/include/llvm/Transforms/Utils/LoopSimplify.h
index f3828bc16e2f..166da2738ffd 100644
--- a/include/llvm/Transforms/Utils/LoopSimplify.h
+++ b/include/llvm/Transforms/Utils/LoopSimplify.h
@@ -52,7 +52,7 @@ public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
 
-/// \brief Simplify each loop in a loop nest recursively.
+/// Simplify each loop in a loop nest recursively.
 ///
 /// This takes a potentially un-simplified loop L (and its children) and turns
 /// it into a simplified loop nest with preheaders and single backedges. It will
diff --git a/include/llvm/Transforms/Utils/LoopUtils.h b/include/llvm/Transforms/Utils/LoopUtils.h
index 750666136507..eb4c99102a63 100644
--- a/include/llvm/Transforms/Utils/LoopUtils.h
+++ b/include/llvm/Transforms/Utils/LoopUtils.h
@@ -21,7 +21,9 @@
 #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"
@@ -46,17 +48,6 @@ class SCEV;
 class TargetLibraryInfo;
 class TargetTransformInfo;
 
-/// \brief Captures loop safety information.
-/// It keep information for loop & its header may throw exception.
-struct LoopSafetyInfo {
-  bool MayThrow = false;       // The current loop contains an instruction which
-                               // may throw.
-  bool HeaderMayThrow = false; // Same as previous, but specific to loop header
-  // Used to update funclet bundle operands.
-  DenseMap<BasicBlock *, ColorVector> BlockColors;
-
-  LoopSafetyInfo() = default;
-};
 
 /// The RecurrenceDescriptor is used to identify recurrences variables in a
 /// loop. Reduction is a special case of recurrence that has uses of the
@@ -172,15 +163,25 @@ public:
                                Value *Left, Value *Right);
 
   /// Returns true if Phi is a reduction of type Kind and adds it to the
-  /// RecurrenceDescriptor.
+  /// 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);
-
-  /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor is
-  /// returned in RedDes.
+                              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);
+                             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
@@ -218,24 +219,6 @@ public:
   /// Returns true if the recurrence kind is an arithmetic kind.
   static bool isArithmeticRecurrenceKind(RecurrenceKind Kind);
 
-  /// Determines if Phi may have been type-promoted. If Phi has a single user
-  /// that ANDs the Phi with a type mask, return the user. RT is updated to
-  /// account for the narrower bit width represented by the mask, and the AND
-  /// instruction is added to CI.
-  static Instruction *lookThroughAnd(PHINode *Phi, Type *&RT,
-                                     SmallPtrSetImpl<Instruction *> &Visited,
-                                     SmallPtrSetImpl<Instruction *> &CI);
-
-  /// Returns true if all the source operands of a recurrence are either
-  /// SExtInsts or ZExtInsts. This function is intended to be used with
-  /// lookThroughAnd to determine if the recurrence has been type-promoted. The
-  /// source operands are added to CI, and IsSigned is updated to indicate if
-  /// all source operands are SExtInsts.
-  static bool getSourceExtensionKind(Instruction *Start, Instruction *Exit,
-                                     Type *RT, bool &IsSigned,
-                                     SmallPtrSetImpl<Instruction *> &Visited,
-                                     SmallPtrSetImpl<Instruction *> &CI);
-
   /// 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; }
@@ -306,16 +289,16 @@ public:
   /// 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 
+  /// 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 
+  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 
+  /// 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);
@@ -351,11 +334,11 @@ public:
       Instruction::BinaryOpsEnd;
   }
 
-  /// Returns a reference to the type cast instructions in the induction 
+  /// 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; 
+  const SmallVectorImpl<Instruction *> &getCastInsts() const {
+    return RedundantCasts;
   }
 
 private:
@@ -402,7 +385,7 @@ bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
 bool formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
                               DominatorTree &DT, LoopInfo &LI);
 
-/// \brief Put loop into LCSSA form.
+/// Put loop into LCSSA form.
 ///
 /// Looks at all instructions in the loop which have uses outside of the
 /// current loop. For each, an LCSSA PHI node is inserted and the uses outside
@@ -415,7 +398,7 @@ bool formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
 /// Returns true if any modifications are made to the loop.
 bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE);
 
-/// \brief Put a loop nest into LCSSA form.
+/// Put a loop nest into LCSSA form.
 ///
 /// This recursively forms LCSSA for a loop nest.
 ///
@@ -427,7 +410,7 @@ bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution *SE);
 bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
                           ScalarEvolution *SE);
 
-/// \brief Walk the specified region of the CFG (defined by all blocks
+/// Walk the specified region of the CFG (defined by all blocks
 /// dominated by the specified block, and that are in the current loop) in
 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit
 /// uses before definitions, allowing us to sink a loop body in one pass without
@@ -440,7 +423,7 @@ bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
                 AliasSetTracker *, LoopSafetyInfo *,
                 OptimizationRemarkEmitter *ORE);
 
-/// \brief Walk the specified region of the CFG (defined by all blocks
+/// Walk the specified region of the CFG (defined by all blocks
 /// dominated by the specified block, and that are in the current loop) in depth
 /// first order w.r.t the DominatorTree.  This allows us to visit definitions
 /// before uses, allowing us to hoist a loop body in one pass without iteration.
@@ -466,7 +449,7 @@ bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
 void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE,
                     LoopInfo *LI);
 
-/// \brief Try to promote memory values to scalars by sinking stores out of
+/// Try to promote memory values to scalars by sinking stores out of
 /// the loop and moving loads to before the loop.  We do this by looping over
 /// the stores in the loop, looking for stores to Must pointers which are
 /// loop invariant. It takes a set of must-alias values, Loop exit blocks
@@ -487,22 +470,10 @@ bool promoteLoopAccessesToScalars(const SmallSetVector<Value *, 8> &,
 SmallVector<DomTreeNode *, 16> collectChildrenInLoop(DomTreeNode *N,
                                                      const Loop *CurLoop);
 
-/// \brief 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.
-void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *);
-
-/// Returns true if the instruction in a loop is guaranteed to execute at least
-/// once.
-bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT,
-                           const Loop *CurLoop,
-                           const LoopSafetyInfo *SafetyInfo);
-
-/// \brief Returns the instructions that use values defined in the loop.
+/// Returns the instructions that use values defined in the loop.
 SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L);
 
-/// \brief Find string metadata for loop
+/// Find string metadata for loop
 ///
 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
 /// operand or null otherwise.  If the string metadata is not found return
@@ -510,11 +481,11 @@ SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L);
 Optional<const MDOperand *> findStringMetadataForLoop(Loop *TheLoop,
                                                       StringRef Name);
 
-/// \brief Set input string into loop metadata by keeping other values intact.
+/// Set input string into loop metadata by keeping other values intact.
 void addStringMetadataToLoop(Loop *TheLoop, const char *MDString,
                              unsigned V = 0);
 
-/// \brief Get a loop's estimated trip count based on branch weight metadata.
+/// Get a loop's estimated trip count based on branch weight metadata.
 /// Returns 0 when the count is estimated to be 0, or None when a meaningful
 /// estimate can not be made.
 Optional<unsigned> getLoopEstimatedTripCount(Loop *L);
@@ -538,11 +509,18 @@ bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
                         LoopSafetyInfo *SafetyInfo,
                         OptimizationRemarkEmitter *ORE = nullptr);
 
+/// Generates an ordered vector reduction using extracts to reduce the value.
+Value *
+getOrderedReduction(IRBuilder<> &Builder, Value *Acc, Value *Src, unsigned Op,
+                    RecurrenceDescriptor::MinMaxRecurrenceKind MinMaxKind =
+                        RecurrenceDescriptor::MRK_Invalid,
+                    ArrayRef<Value *> RedOps = None);
+
 /// Generates a vector reduction using shufflevectors to reduce the value.
 Value *getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op,
                            RecurrenceDescriptor::MinMaxRecurrenceKind
                                MinMaxKind = RecurrenceDescriptor::MRK_Invalid,
-                           ArrayRef<Value *> RedOps = ArrayRef<Value *>());
+                           ArrayRef<Value *> RedOps = None);
 
 /// Create a target reduction of the given vector. The reduction operation
 /// is described by the \p Opcode parameter. min/max reductions require
@@ -554,7 +532,7 @@ createSimpleTargetReduction(IRBuilder<> &B, const TargetTransformInfo *TTI,
                             unsigned Opcode, Value *Src,
                             TargetTransformInfo::ReductionFlags Flags =
                                 TargetTransformInfo::ReductionFlags(),
-                            ArrayRef<Value *> RedOps = ArrayRef<Value *>());
+                            ArrayRef<Value *> RedOps = None);
 
 /// Create a generic target reduction using a recurrence descriptor \p Desc
 /// The target is queried to determine if intrinsics or shuffle sequences are
diff --git a/include/llvm/Transforms/Utils/LoopVersioning.h b/include/llvm/Transforms/Utils/LoopVersioning.h
index fa5d7845d080..fcd734b37a1f 100644
--- a/include/llvm/Transforms/Utils/LoopVersioning.h
+++ b/include/llvm/Transforms/Utils/LoopVersioning.h
@@ -28,14 +28,14 @@ class LoopAccessInfo;
 class LoopInfo;
 class ScalarEvolution;
 
-/// \brief This class emits a version of the loop where run-time checks ensure
+/// This class emits a version of the loop where run-time checks ensure
 /// that may-alias pointers can't overlap.
 ///
 /// It currently only supports single-exit loops and assumes that the loop
 /// already has a preheader.
 class LoopVersioning {
 public:
-  /// \brief Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input.
+  /// Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input.
   /// It uses runtime check provided by the user. If \p UseLAIChecks is true,
   /// we will retain the default checks made by LAI. Otherwise, construct an
   /// object having no checks and we expect the user to add them.
@@ -43,7 +43,7 @@ public:
                  DominatorTree *DT, ScalarEvolution *SE,
                  bool UseLAIChecks = true);
 
-  /// \brief Performs the CFG manipulation part of versioning the loop including
+  /// Performs the CFG manipulation part of versioning the loop including
   /// the DominatorTree and LoopInfo updates.
   ///
   /// The loop that was used to construct the class will be the "versioned" loop
@@ -58,38 +58,38 @@ public:
   ///        transform L
   void versionLoop() { versionLoop(findDefsUsedOutsideOfLoop(VersionedLoop)); }
 
-  /// \brief Same but if the client has already precomputed the set of values
+  /// Same but if the client has already precomputed the set of values
   /// used outside the loop, this API will allows passing that.
   void versionLoop(const SmallVectorImpl<Instruction *> &DefsUsedOutside);
 
-  /// \brief Returns the versioned loop.  Control flows here if pointers in the
+  /// Returns the versioned loop.  Control flows here if pointers in the
   /// loop don't alias (i.e. all memchecks passed).  (This loop is actually the
   /// same as the original loop that we got constructed with.)
   Loop *getVersionedLoop() { return VersionedLoop; }
 
-  /// \brief Returns the fall-back loop.  Control flows here if pointers in the
+  /// Returns the fall-back loop.  Control flows here if pointers in the
   /// loop may alias (i.e. one of the memchecks failed).
   Loop *getNonVersionedLoop() { return NonVersionedLoop; }
 
-  /// \brief Sets the runtime alias checks for versioning the loop.
+  /// Sets the runtime alias checks for versioning the loop.
   void setAliasChecks(
       SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks);
 
-  /// \brief Sets the runtime SCEV checks for versioning the loop.
+  /// Sets the runtime SCEV checks for versioning the loop.
   void setSCEVChecks(SCEVUnionPredicate Check);
 
-  /// \brief Annotate memory instructions in the versioned loop with no-alias
+  /// Annotate memory instructions in the versioned loop with no-alias
   /// metadata based on the memchecks issued.
   ///
   /// This is just wrapper that calls prepareNoAliasMetadata and
   /// annotateInstWithNoAlias on the instructions of the versioned loop.
   void annotateLoopWithNoAlias();
 
-  /// \brief Set up the aliasing scopes based on the memchecks.  This needs to
+  /// Set up the aliasing scopes based on the memchecks.  This needs to
   /// be called before the first call to annotateInstWithNoAlias.
   void prepareNoAliasMetadata();
 
-  /// \brief Add the noalias annotations to \p VersionedInst.
+  /// Add the noalias annotations to \p VersionedInst.
   ///
   /// \p OrigInst is the instruction corresponding to \p VersionedInst in the
   /// original loop.  Initialize the aliasing scopes with
@@ -98,50 +98,50 @@ public:
                                const Instruction *OrigInst);
 
 private:
-  /// \brief Adds the necessary PHI nodes for the versioned loops based on the
+  /// Adds the necessary PHI nodes for the versioned loops based on the
   /// loop-defined values used outside of the loop.
   ///
   /// This needs to be called after versionLoop if there are defs in the loop
   /// that are used outside the loop.
   void addPHINodes(const SmallVectorImpl<Instruction *> &DefsUsedOutside);
 
-  /// \brief Add the noalias annotations to \p I.  Initialize the aliasing
+  /// Add the noalias annotations to \p I.  Initialize the aliasing
   /// scopes with prepareNoAliasMetadata once before this can be called.
   void annotateInstWithNoAlias(Instruction *I) {
     annotateInstWithNoAlias(I, I);
   }
 
-  /// \brief The original loop.  This becomes the "versioned" one.  I.e.,
+  /// The original loop.  This becomes the "versioned" one.  I.e.,
   /// control flows here if pointers in the loop don't alias.
   Loop *VersionedLoop;
-  /// \brief The fall-back loop.  I.e. control flows here if pointers in the
+  /// The fall-back loop.  I.e. control flows here if pointers in the
   /// loop may alias (memchecks failed).
   Loop *NonVersionedLoop;
 
-  /// \brief This maps the instructions from VersionedLoop to their counterpart
+  /// This maps the instructions from VersionedLoop to their counterpart
   /// in NonVersionedLoop.
   ValueToValueMapTy VMap;
 
-  /// \brief The set of alias checks that we are versioning for.
+  /// The set of alias checks that we are versioning for.
   SmallVector<RuntimePointerChecking::PointerCheck, 4> AliasChecks;
 
-  /// \brief The set of SCEV checks that we are versioning for.
+  /// The set of SCEV checks that we are versioning for.
   SCEVUnionPredicate Preds;
 
-  /// \brief Maps a pointer to the pointer checking group that the pointer
+  /// Maps a pointer to the pointer checking group that the pointer
   /// belongs to.
   DenseMap<const Value *, const RuntimePointerChecking::CheckingPtrGroup *>
       PtrToGroup;
 
-  /// \brief The alias scope corresponding to a pointer checking group.
+  /// The alias scope corresponding to a pointer checking group.
   DenseMap<const RuntimePointerChecking::CheckingPtrGroup *, MDNode *>
       GroupToScope;
 
-  /// \brief The list of alias scopes that a pointer checking group can't alias.
+  /// The list of alias scopes that a pointer checking group can't alias.
   DenseMap<const RuntimePointerChecking::CheckingPtrGroup *, MDNode *>
       GroupToNonAliasingScopeList;
 
-  /// \brief Analyses used.
+  /// Analyses used.
   const LoopAccessInfo &LAI;
   LoopInfo *LI;
   DominatorTree *DT;
diff --git a/include/llvm/Transforms/Utils/ModuleUtils.h b/include/llvm/Transforms/Utils/ModuleUtils.h
index 4b9bc8293810..14615c25d093 100644
--- a/include/llvm/Transforms/Utils/ModuleUtils.h
+++ b/include/llvm/Transforms/Utils/ModuleUtils.h
@@ -49,7 +49,7 @@ Function *checkSanitizerInterfaceFunction(Constant *FuncOrBitcast);
 Function *declareSanitizerInitFunction(Module &M, StringRef InitName,
                                        ArrayRef<Type *> InitArgTypes);
 
-/// \brief Creates sanitizer constructor function, and calls sanitizer's init
+/// Creates sanitizer constructor function, and calls sanitizer's init
 /// function from it.
 /// \return Returns pair of pointers to constructor, and init functions
 /// respectively.
@@ -62,10 +62,10 @@ std::pair<Function *, Function *> createSanitizerCtorAndInitFunctions(
 /// the list of public globals in the module.
 bool nameUnamedGlobals(Module &M);
 
-/// \brief Adds global values to the llvm.used list.
+/// Adds global values to the llvm.used list.
 void appendToUsed(Module &M, ArrayRef<GlobalValue *> Values);
 
-/// \brief Adds global values to the llvm.compiler.used list.
+/// Adds global values to the llvm.compiler.used list.
 void appendToCompilerUsed(Module &M, ArrayRef<GlobalValue *> Values);
 
 /// Filter out potentially dead comdat functions where other entries keep the
@@ -84,7 +84,7 @@ void appendToCompilerUsed(Module &M, ArrayRef<GlobalValue *> Values);
 void filterDeadComdatFunctions(
     Module &M, SmallVectorImpl<Function *> &DeadComdatFunctions);
 
-/// \brief Produce a unique identifier for this module by taking the MD5 sum of
+/// 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
 /// members.
 ///
diff --git a/include/llvm/Transforms/Utils/OrderedInstructions.h b/include/llvm/Transforms/Utils/OrderedInstructions.h
index 165d4bdaa6d4..7f57fde638b8 100644
--- a/include/llvm/Transforms/Utils/OrderedInstructions.h
+++ b/include/llvm/Transforms/Utils/OrderedInstructions.h
@@ -35,6 +35,11 @@ class OrderedInstructions {
   /// 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) {}
@@ -42,6 +47,12 @@ public:
   /// 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
diff --git a/include/llvm/Transforms/Utils/PredicateInfo.h b/include/llvm/Transforms/Utils/PredicateInfo.h
index 8150f1528397..b53eda7e5a42 100644
--- a/include/llvm/Transforms/Utils/PredicateInfo.h
+++ b/include/llvm/Transforms/Utils/PredicateInfo.h
@@ -8,7 +8,7 @@
 //===----------------------------------------------------------------------===//
 ///
 /// \file
-/// \brief  This file implements the PredicateInfo analysis, which creates an Extended
+///  This file implements the PredicateInfo analysis, which creates an Extended
 /// SSA form for operations used in branch comparisons and llvm.assume
 /// comparisons.
 ///
@@ -31,7 +31,7 @@
 /// %cmp = icmp eq i32, %x, 50
 /// br i1 %cmp, label %true, label %false
 /// true:
-/// %x.0 = call @llvm.ssa_copy.i32(i32 %x)
+/// %x.0 = call \@llvm.ssa_copy.i32(i32 %x)
 /// ret i32 %x.0
 /// false:
 /// ret i32 1
@@ -54,6 +54,7 @@
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/ilist.h"
 #include "llvm/ADT/ilist_node.h"
@@ -69,6 +70,7 @@
 #include "llvm/IR/Use.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
+#include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 #include "llvm/PassAnalysisSupport.h"
 #include "llvm/Support/Casting.h"
@@ -193,7 +195,7 @@ namespace PredicateInfoClasses {
 struct ValueDFS;
 }
 
-/// \brief Encapsulates PredicateInfo, including all data associated with memory
+/// Encapsulates PredicateInfo, including all data associated with memory
 /// accesses.
 class PredicateInfo {
 private:
@@ -261,6 +263,8 @@ private:
   // The set of edges along which we can only handle phi uses, due to critical
   // edges.
   DenseSet<std::pair<BasicBlock *, BasicBlock *>> EdgeUsesOnly;
+  // The set of ssa_copy declarations we created with our custom mangling.
+  SmallSet<AssertingVH<Function>, 20> CreatedDeclarations;
 };
 
 // This pass does eager building and then printing of PredicateInfo. It is used
@@ -275,7 +279,7 @@ public:
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 };
 
-/// \brief Printer pass for \c PredicateInfo.
+/// Printer pass for \c PredicateInfo.
 class PredicateInfoPrinterPass
     : public PassInfoMixin<PredicateInfoPrinterPass> {
   raw_ostream &OS;
@@ -285,7 +289,7 @@ public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
 
-/// \brief Verifier pass for \c PredicateInfo.
+/// Verifier pass for \c PredicateInfo.
 struct PredicateInfoVerifierPass : PassInfoMixin<PredicateInfoVerifierPass> {
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
diff --git a/include/llvm/Transforms/Utils/PromoteMemToReg.h b/include/llvm/Transforms/Utils/PromoteMemToReg.h
index bb8a61a474f2..5ddfbe2bf058 100644
--- a/include/llvm/Transforms/Utils/PromoteMemToReg.h
+++ b/include/llvm/Transforms/Utils/PromoteMemToReg.h
@@ -23,7 +23,7 @@ class DominatorTree;
 class AliasSetTracker;
 class AssumptionCache;
 
-/// \brief Return true if this alloca is legal for promotion.
+/// Return true if this alloca is legal for promotion.
 ///
 /// This is true if there are only loads, stores, and lifetime markers
 /// (transitively) using this alloca. This also enforces that there is only
@@ -31,7 +31,7 @@ class AssumptionCache;
 /// markers.
 bool isAllocaPromotable(const AllocaInst *AI);
 
-/// \brief Promote the specified list of alloca instructions into scalar
+/// Promote the specified list of alloca instructions into scalar
 /// registers, inserting PHI nodes as appropriate.
 ///
 /// This function makes use of DominanceFrontier information.  This function
diff --git a/include/llvm/Transforms/Utils/SSAUpdater.h b/include/llvm/Transforms/Utils/SSAUpdater.h
index 6cd9f1539b0b..4a7911662990 100644
--- a/include/llvm/Transforms/Utils/SSAUpdater.h
+++ b/include/llvm/Transforms/Utils/SSAUpdater.h
@@ -30,7 +30,7 @@ class Type;
 class Use;
 class Value;
 
-/// \brief Helper class for SSA formation on a set of values defined in
+/// Helper class for SSA formation on a set of values defined in
 /// multiple blocks.
 ///
 /// This is used when code duplication or another unstructured
@@ -62,25 +62,25 @@ public:
   SSAUpdater &operator=(const SSAUpdater &) = delete;
   ~SSAUpdater();
 
-  /// \brief Reset this object to get ready for a new set of SSA updates with
+  /// Reset this object to get ready for a new set of SSA updates with
   /// type 'Ty'.
   ///
   /// PHI nodes get a name based on 'Name'.
   void Initialize(Type *Ty, StringRef Name);
 
-  /// \brief Indicate that a rewritten value is available in the specified block
+  /// Indicate that a rewritten value is available in the specified block
   /// with the specified value.
   void AddAvailableValue(BasicBlock *BB, Value *V);
 
-  /// \brief Return true if the SSAUpdater already has a value for the specified
+  /// Return true if the SSAUpdater already has a value for the specified
   /// block.
   bool HasValueForBlock(BasicBlock *BB) const;
 
-  /// \brief Construct SSA form, materializing a value that is live at the end
+  /// Construct SSA form, materializing a value that is live at the end
   /// of the specified block.
   Value *GetValueAtEndOfBlock(BasicBlock *BB);
 
-  /// \brief Construct SSA form, materializing a value that is live in the
+  /// Construct SSA form, materializing a value that is live in the
   /// middle of the specified block.
   ///
   /// \c GetValueInMiddleOfBlock is the same as \c GetValueAtEndOfBlock except
@@ -102,7 +102,7 @@ public:
   /// merge the appropriate values, and this value isn't live out of the block.
   Value *GetValueInMiddleOfBlock(BasicBlock *BB);
 
-  /// \brief Rewrite a use of the symbolic value.
+  /// Rewrite a use of the symbolic value.
   ///
   /// This handles PHI nodes, which use their value in the corresponding
   /// predecessor. Note that this will not work if the use is supposed to be
@@ -111,7 +111,7 @@ public:
   /// be below it.
   void RewriteUse(Use &U);
 
-  /// \brief Rewrite a use like \c RewriteUse but handling in-block definitions.
+  /// Rewrite a use like \c RewriteUse but handling in-block definitions.
   ///
   /// This version of the method can rewrite uses in the same block as
   /// a definition, because it assumes that all uses of a value are below any
@@ -122,7 +122,7 @@ private:
   Value *GetValueAtEndOfBlockInternal(BasicBlock *BB);
 };
 
-/// \brief Helper class for promoting a collection of loads and stores into SSA
+/// Helper class for promoting a collection of loads and stores into SSA
 /// Form using the SSAUpdater.
 ///
 /// This handles complexities that SSAUpdater doesn't, such as multiple loads
@@ -139,32 +139,32 @@ public:
                        SSAUpdater &S, StringRef Name = StringRef());
   virtual ~LoadAndStorePromoter() = default;
 
-  /// \brief This does the promotion.
+  /// This does the promotion.
   ///
   /// Insts is a list of loads and stores to promote, and Name is the basename
   /// for the PHIs to insert. After this is complete, the loads and stores are
   /// removed from the code.
   void run(const SmallVectorImpl<Instruction *> &Insts) const;
 
-  /// \brief Return true if the specified instruction is in the Inst list.
+  /// Return true if the specified instruction is in the Inst list.
   ///
   /// The Insts list is the one passed into the constructor. Clients should
   /// implement this with a more efficient version if possible.
   virtual bool isInstInList(Instruction *I,
                             const SmallVectorImpl<Instruction *> &Insts) const;
 
-  /// \brief This hook is invoked after all the stores are found and inserted as
+  /// This hook is invoked after all the stores are found and inserted as
   /// available values.
   virtual void doExtraRewritesBeforeFinalDeletion() const {}
 
-  /// \brief Clients can choose to implement this to get notified right before
+  /// Clients can choose to implement this to get notified right before
   /// a load is RAUW'd another value.
   virtual void replaceLoadWithValue(LoadInst *LI, Value *V) const {}
 
-  /// \brief Called before each instruction is deleted.
+  /// Called before each instruction is deleted.
   virtual void instructionDeleted(Instruction *I) const {}
 
-  /// \brief Called to update debug info associated with the instruction.
+  /// Called to update debug info associated with the instruction.
   virtual void updateDebugInfo(Instruction *I) const {}
 };
 
diff --git a/include/llvm/Transforms/Utils/SSAUpdaterBulk.h b/include/llvm/Transforms/Utils/SSAUpdaterBulk.h
new file mode 100644
index 000000000000..53a608f01804
--- /dev/null
+++ b/include/llvm/Transforms/Utils/SSAUpdaterBulk.h
@@ -0,0 +1,92 @@
+//===- SSAUpdaterBulk.h - Unstructured SSA Update Tool ----------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file declares the SSAUpdaterBulk class.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATERBULK_H
+#define LLVM_TRANSFORMS_UTILS_SSAUPDATERBULK_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/IR/PredIteratorCache.h"
+
+namespace llvm {
+
+class BasicBlock;
+class PHINode;
+template <typename T> class SmallVectorImpl;
+class Type;
+class Use;
+class Value;
+class DominatorTree;
+
+/// Helper class for SSA formation on a set of values defined in multiple
+/// blocks.
+///
+/// This is used when code duplication or another unstructured transformation
+/// wants to rewrite a set of uses of one value with uses of a set of values.
+/// The update is done only when RewriteAllUses is called, all other methods are
+/// used for book-keeping. That helps to share some common computations between
+/// updates of different uses (which is not the case when traditional SSAUpdater
+/// is used).
+class SSAUpdaterBulk {
+  struct RewriteInfo {
+    DenseMap<BasicBlock *, Value *> Defines;
+    SmallVector<Use *, 4> Uses;
+    StringRef Name;
+    Type *Ty;
+    RewriteInfo(){};
+    RewriteInfo(StringRef &N, Type *T) : Name(N), Ty(T){};
+  };
+  SmallVector<RewriteInfo, 4> Rewrites;
+
+  PredIteratorCache PredCache;
+
+  Value *computeValueAt(BasicBlock *BB, RewriteInfo &R, DominatorTree *DT);
+
+public:
+  explicit SSAUpdaterBulk(){};
+  SSAUpdaterBulk(const SSAUpdaterBulk &) = delete;
+  SSAUpdaterBulk &operator=(const SSAUpdaterBulk &) = delete;
+  ~SSAUpdaterBulk(){};
+
+  /// Add a new variable to the SSA rewriter. This needs to be called before
+  /// AddAvailableValue or AddUse calls. The return value is the variable ID,
+  /// which needs to be passed to AddAvailableValue and AddUse.
+  unsigned AddVariable(StringRef Name, Type *Ty);
+
+  /// Indicate that a rewritten value is available in the specified block with
+  /// the specified value.
+  void AddAvailableValue(unsigned Var, BasicBlock *BB, Value *V);
+
+  /// Record a use of the symbolic value. This use will be updated with a
+  /// rewritten value when RewriteAllUses is called.
+  void AddUse(unsigned Var, Use *U);
+
+  /// Return true if the SSAUpdater already has a value for the specified
+  /// variable in the specified block.
+  bool HasValueForBlock(unsigned Var, BasicBlock *BB);
+
+  /// Perform all the necessary updates, including new PHI-nodes insertion and
+  /// the requested uses update.
+  ///
+  /// The function requires dominator tree DT, which is used for computing
+  /// locations for new phi-nodes insertions. If a nonnull pointer to a vector
+  /// InsertedPHIs is passed, all the new phi-nodes will be added to this
+  /// vector.
+  void RewriteAllUses(DominatorTree *DT,
+                      SmallVectorImpl<PHINode *> *InsertedPHIs = nullptr);
+};
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_UTILS_SSAUPDATERBULK_H
diff --git a/include/llvm/Transforms/Utils/SSAUpdaterImpl.h b/include/llvm/Transforms/Utils/SSAUpdaterImpl.h
index b1611d49a456..b7649ba88334 100644
--- a/include/llvm/Transforms/Utils/SSAUpdaterImpl.h
+++ b/include/llvm/Transforms/Utils/SSAUpdaterImpl.h
@@ -379,7 +379,7 @@ public:
         Traits::AddPHIOperand(PHI, PredInfo->AvailableVal, Pred);
       }
 
-      DEBUG(dbgs() << "  Inserted PHI: " << *PHI << "\n");
+      LLVM_DEBUG(dbgs() << "  Inserted PHI: " << *PHI << "\n");
 
       // If the client wants to know about all new instructions, tell it.
       if (InsertedPHIs) InsertedPHIs->push_back(PHI);
@@ -389,12 +389,8 @@ public:
   /// FindExistingPHI - Look through the PHI nodes in a block to see if any of
   /// them match what is needed.
   void FindExistingPHI(BlkT *BB, BlockListTy *BlockList) {
-    for (typename BlkT::iterator BBI = BB->begin(), BBE = BB->end();
-         BBI != BBE; ++BBI) {
-      PhiT *SomePHI = Traits::InstrIsPHI(&*BBI);
-      if (!SomePHI)
-        break;
-      if (CheckIfPHIMatches(SomePHI)) {
+    for (auto &SomePHI : BB->phis()) {
+      if (CheckIfPHIMatches(&SomePHI)) {
         RecordMatchingPHIs(BlockList);
         break;
       }
diff --git a/include/llvm/Transforms/Utils/SimplifyInstructions.h b/include/llvm/Transforms/Utils/SimplifyInstructions.h
deleted file mode 100644
index 3f838611626f..000000000000
--- a/include/llvm/Transforms/Utils/SimplifyInstructions.h
+++ /dev/null
@@ -1,31 +0,0 @@
-//===- SimplifyInstructions.h - Remove redundant instructions ---*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This is a utility pass used for testing the InstructionSimplify analysis.
-// The analysis is applied to every instruction, and if it simplifies then the
-// instruction is replaced by the simplification.  If you are looking for a pass
-// that performs serious instruction folding, use the instcombine pass instead.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_TRANSFORMS_UTILS_SIMPLIFYINSTRUCTIONS_H
-#define LLVM_TRANSFORMS_UTILS_SIMPLIFYINSTRUCTIONS_H
-
-#include "llvm/IR/PassManager.h"
-
-namespace llvm {
-
-/// This pass removes redundant instructions.
-class InstSimplifierPass : public PassInfoMixin<InstSimplifierPass> {
-public:
-  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
-};
-} // end namespace llvm
-
-#endif // LLVM_TRANSFORMS_UTILS_SIMPLIFYINSTRUCTIONS_H
diff --git a/include/llvm/Transforms/Utils/SimplifyLibCalls.h b/include/llvm/Transforms/Utils/SimplifyLibCalls.h
index 73a62f59203b..d007f909c6a4 100644
--- a/include/llvm/Transforms/Utils/SimplifyLibCalls.h
+++ b/include/llvm/Transforms/Utils/SimplifyLibCalls.h
@@ -30,7 +30,7 @@ class BasicBlock;
 class Function;
 class OptimizationRemarkEmitter;
 
-/// \brief This class implements simplifications for calls to fortified library
+/// This class implements simplifications for calls to fortified library
 /// functions (__st*cpy_chk, __memcpy_chk, __memmove_chk, __memset_chk), to,
 /// when possible, replace them with their non-checking counterparts.
 /// Other optimizations can also be done, but it's possible to disable them and
@@ -45,7 +45,7 @@ public:
   FortifiedLibCallSimplifier(const TargetLibraryInfo *TLI,
                              bool OnlyLowerUnknownSize = false);
 
-  /// \brief Take the given call instruction and return a more
+  /// Take the given call instruction and return a more
   /// optimal value to replace the instruction with or 0 if a more
   /// optimal form can't be found.
   /// The call must not be an indirect call.
@@ -60,7 +60,7 @@ private:
   Value *optimizeStrpCpyChk(CallInst *CI, IRBuilder<> &B, LibFunc Func);
   Value *optimizeStrpNCpyChk(CallInst *CI, IRBuilder<> &B, LibFunc Func);
 
-  /// \brief Checks whether the call \p CI to a fortified libcall is foldable
+  /// Checks whether the call \p CI to a fortified libcall is foldable
   /// to the non-fortified version.
   bool isFortifiedCallFoldable(CallInst *CI, unsigned ObjSizeOp,
                                unsigned SizeOp, bool isString);
@@ -78,13 +78,13 @@ private:
   bool UnsafeFPShrink;
   function_ref<void(Instruction *, Value *)> Replacer;
 
-  /// \brief Internal wrapper for RAUW that is the default implementation.
+  /// Internal wrapper for RAUW that is the default implementation.
   ///
   /// Other users may provide an alternate function with this signature instead
   /// of this one.
   static void replaceAllUsesWithDefault(Instruction *I, Value *With);
 
-  /// \brief Replace an instruction's uses with a value using our replacer.
+  /// Replace an instruction's uses with a value using our replacer.
   void replaceAllUsesWith(Instruction *I, Value *With);
 
 public:
@@ -124,6 +124,7 @@ private:
   Value *optimizeMemCpy(CallInst *CI, IRBuilder<> &B);
   Value *optimizeMemMove(CallInst *CI, IRBuilder<> &B);
   Value *optimizeMemSet(CallInst *CI, IRBuilder<> &B);
+  Value *optimizeRealloc(CallInst *CI, IRBuilder<> &B);
   Value *optimizeWcslen(CallInst *CI, IRBuilder<> &B);
   // Wrapper for all String/Memory Library Call Optimizations
   Value *optimizeStringMemoryLibCall(CallInst *CI, IRBuilder<> &B);
@@ -150,15 +151,22 @@ private:
   Value *optimizeIsDigit(CallInst *CI, IRBuilder<> &B);
   Value *optimizeIsAscii(CallInst *CI, IRBuilder<> &B);
   Value *optimizeToAscii(CallInst *CI, IRBuilder<> &B);
+  Value *optimizeAtoi(CallInst *CI, IRBuilder<> &B);
+  Value *optimizeStrtol(CallInst *CI, IRBuilder<> &B);
 
   // Formatting and IO Library Call Optimizations
   Value *optimizeErrorReporting(CallInst *CI, IRBuilder<> &B,
                                 int StreamArg = -1);
   Value *optimizePrintF(CallInst *CI, IRBuilder<> &B);
   Value *optimizeSPrintF(CallInst *CI, IRBuilder<> &B);
+  Value *optimizeSnPrintF(CallInst *CI, IRBuilder<> &B);
   Value *optimizeFPrintF(CallInst *CI, IRBuilder<> &B);
   Value *optimizeFWrite(CallInst *CI, IRBuilder<> &B);
+  Value *optimizeFRead(CallInst *CI, IRBuilder<> &B);
   Value *optimizeFPuts(CallInst *CI, IRBuilder<> &B);
+  Value *optimizeFGets(CallInst *CI, IRBuilder<> &B);
+  Value *optimizeFPutc(CallInst *CI, IRBuilder<> &B);
+  Value *optimizeFGetc(CallInst *CI, IRBuilder<> &B);
   Value *optimizePuts(CallInst *CI, IRBuilder<> &B);
 
   // Helper methods
@@ -169,6 +177,7 @@ private:
                       SmallVectorImpl<CallInst *> &SinCosCalls);
   Value *optimizePrintFString(CallInst *CI, IRBuilder<> &B);
   Value *optimizeSPrintFString(CallInst *CI, IRBuilder<> &B);
+  Value *optimizeSnPrintFString(CallInst *CI, IRBuilder<> &B);
   Value *optimizeFPrintFString(CallInst *CI, IRBuilder<> &B);
 
   /// hasFloatVersion - Checks if there is a float version of the specified
diff --git a/include/llvm/Transforms/Utils/UnrollLoop.h b/include/llvm/Transforms/Utils/UnrollLoop.h
index 12aa3bc6e770..a6b84af068a5 100644
--- a/include/llvm/Transforms/Utils/UnrollLoop.h
+++ b/include/llvm/Transforms/Utils/UnrollLoop.h
@@ -19,11 +19,13 @@
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/Transforms/Utils/ValueMapper.h"
 
 namespace llvm {
 
 class AssumptionCache;
 class BasicBlock;
+class DependenceInfo;
 class DominatorTree;
 class Loop;
 class LoopInfo;
@@ -71,13 +73,54 @@ bool UnrollRuntimeLoopRemainder(Loop *L, unsigned Count,
 
 void computePeelCount(Loop *L, unsigned LoopSize,
                       TargetTransformInfo::UnrollingPreferences &UP,
-                      unsigned &TripCount);
+                      unsigned &TripCount, ScalarEvolution &SE);
+
+bool canPeel(Loop *L);
 
 bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE,
               DominatorTree *DT, AssumptionCache *AC, bool PreserveLCSSA);
 
+LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount,
+                                  unsigned TripMultiple, bool UnrollRemainder,
+                                  LoopInfo *LI, ScalarEvolution *SE,
+                                  DominatorTree *DT, AssumptionCache *AC,
+                                  OptimizationRemarkEmitter *ORE);
+
+bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT,
+                          DependenceInfo &DI);
+
+bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI,
+                        DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE,
+                        const SmallPtrSetImpl<const Value *> &EphValues,
+                        OptimizationRemarkEmitter *ORE, unsigned &TripCount,
+                        unsigned MaxTripCount, unsigned &TripMultiple,
+                        unsigned LoopSize,
+                        TargetTransformInfo::UnrollingPreferences &UP,
+                        bool &UseUpperBound);
+
+BasicBlock *foldBlockIntoPredecessor(BasicBlock *BB, LoopInfo *LI,
+                                     ScalarEvolution *SE, DominatorTree *DT);
+
+void remapInstruction(Instruction *I, ValueToValueMapTy &VMap);
+
+void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI,
+                             ScalarEvolution *SE, DominatorTree *DT,
+                             AssumptionCache *AC);
+
 MDNode *GetUnrollMetadata(MDNode *LoopID, StringRef Name);
 
+TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences(
+    Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, int OptLevel,
+    Optional<unsigned> UserThreshold, Optional<unsigned> UserCount,
+    Optional<bool> UserAllowPartial, Optional<bool> UserRuntime,
+    Optional<bool> UserUpperBound, Optional<bool> UserAllowPeeling);
+
+unsigned ApproximateLoopSize(const Loop *L, unsigned &NumCalls,
+                             bool &NotDuplicatable, bool &Convergent,
+                             const TargetTransformInfo &TTI,
+                             const SmallPtrSetImpl<const Value *> &EphValues,
+                             unsigned BEInsns);
+
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H