vendor/clang/clang-trunk-r290819

16 files changed, 1224 insertions, 87 deletions

diff --git a/lib/Analysis/AnalysisDeclContext.cpp b/lib/Analysis/AnalysisDeclContext.cpp
index 6bbe8f86d48ea..6b58916162f63 100644
--- a/lib/Analysis/AnalysisDeclContext.cpp
+++ b/lib/Analysis/AnalysisDeclContext.cpp
@@ -81,9 +81,7 @@ AnalysisDeclContextManager::AnalysisDeclContextManager(bool useUnoptimizedCFG,
   cfgBuildOptions.AddCXXNewAllocator = addCXXNewAllocator;
 }
 
-void AnalysisDeclContextManager::clear() {
-  llvm::DeleteContainerSeconds(Contexts);
-}
+void AnalysisDeclContextManager::clear() { Contexts.clear(); }
 
 static BodyFarm &getBodyFarm(ASTContext &C, CodeInjector *injector = nullptr) {
   static BodyFarm *BF = new BodyFarm(C, injector);
@@ -307,10 +305,10 @@ AnalysisDeclContext *AnalysisDeclContextManager::getContext(const Decl *D) {
     D = FD;
   }
 
-  AnalysisDeclContext *&AC = Contexts[D];
+  std::unique_ptr<AnalysisDeclContext> &AC = Contexts[D];
   if (!AC)
-    AC = new AnalysisDeclContext(this, D, cfgBuildOptions);
-  return AC;
+    AC = llvm::make_unique<AnalysisDeclContext>(this, D, cfgBuildOptions);
+  return AC.get();
 }
 
 const StackFrameContext *
@@ -606,9 +604,7 @@ AnalysisDeclContext::~AnalysisDeclContext() {
   }
 }
 
-AnalysisDeclContextManager::~AnalysisDeclContextManager() {
-  llvm::DeleteContainerSeconds(Contexts);
-}
+AnalysisDeclContextManager::~AnalysisDeclContextManager() {}
 
 LocationContext::~LocationContext() {}
 
diff --git a/lib/Analysis/CFG.cpp b/lib/Analysis/CFG.cpp
index a67f0910e15a7..bf3cc05cdb6e8 100644
--- a/lib/Analysis/CFG.cpp
+++ b/lib/Analysis/CFG.cpp
@@ -1164,7 +1164,8 @@ CFGBlock *CFGBuilder::addInitializer(CXXCtorInitializer *I) {
 /// \brief Retrieve the type of the temporary object whose lifetime was 
 /// extended by a local reference with the given initializer.
 static QualType getReferenceInitTemporaryType(ASTContext &Context,
-                                              const Expr *Init) {
+                                              const Expr *Init,
+                                              bool *FoundMTE = nullptr) {
   while (true) {
     // Skip parentheses.
     Init = Init->IgnoreParens();
@@ -1179,6 +1180,8 @@ static QualType getReferenceInitTemporaryType(ASTContext &Context,
     if (const MaterializeTemporaryExpr *MTE
           = dyn_cast<MaterializeTemporaryExpr>(Init)) {
       Init = MTE->GetTemporaryExpr();
+      if (FoundMTE)
+        *FoundMTE = true;
       continue;
     }
     
@@ -1370,13 +1373,12 @@ LocalScope* CFGBuilder::addLocalScopeForVarDecl(VarDecl *VD,
     const Expr *Init = VD->getInit();
     if (!Init)
       return Scope;
-    if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Init))
-      Init = EWC->getSubExpr();
-    if (!isa<MaterializeTemporaryExpr>(Init))
-      return Scope;
 
     // Lifetime-extending a temporary.
-    QT = getReferenceInitTemporaryType(*Context, Init);
+    bool FoundMTE = false;
+    QT = getReferenceInitTemporaryType(*Context, Init, &FoundMTE);
+    if (!FoundMTE)
+      return Scope;
   }
 
   // Check for constant size array. Set type to array element type.
@@ -2050,8 +2052,7 @@ CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) {
                                        E = DS->decl_rend();
        I != E; ++I) {
     // Get the alignment of the new DeclStmt, padding out to >=8 bytes.
-    unsigned A = llvm::AlignOf<DeclStmt>::Alignment < 8
-               ? 8 : llvm::AlignOf<DeclStmt>::Alignment;
+    unsigned A = alignof(DeclStmt) < 8 ? 8 : alignof(DeclStmt);
 
     // Allocate the DeclStmt using the BumpPtrAllocator.  It will get
     // automatically freed with the CFG.
@@ -2983,20 +2984,19 @@ CFGBlock *CFGBuilder::VisitDoStmt(DoStmt *D) {
         return nullptr;
     }
 
-    if (!KnownVal.isFalse()) {
-      // Add an intermediate block between the BodyBlock and the
-      // ExitConditionBlock to represent the "loop back" transition.  Create an
-      // empty block to represent the transition block for looping back to the
-      // head of the loop.
-      // FIXME: Can we do this more efficiently without adding another block?
-      Block = nullptr;
-      Succ = BodyBlock;
-      CFGBlock *LoopBackBlock = createBlock();
-      LoopBackBlock->setLoopTarget(D);
+    // Add an intermediate block between the BodyBlock and the
+    // ExitConditionBlock to represent the "loop back" transition.  Create an
+    // empty block to represent the transition block for looping back to the
+    // head of the loop.
+    // FIXME: Can we do this more efficiently without adding another block?
+    Block = nullptr;
+    Succ = BodyBlock;
+    CFGBlock *LoopBackBlock = createBlock();
+    LoopBackBlock->setLoopTarget(D);
 
+    if (!KnownVal.isFalse())
       // Add the loop body entry as a successor to the condition.
       addSuccessor(ExitConditionBlock, LoopBackBlock);
-    }
     else
       addSuccessor(ExitConditionBlock, nullptr);
   }
@@ -3583,11 +3583,13 @@ CFGBlock *CFGBuilder::VisitCXXDeleteExpr(CXXDeleteExpr *DE,
   autoCreateBlock();
   appendStmt(Block, DE);
   QualType DTy = DE->getDestroyedType();
-  DTy = DTy.getNonReferenceType();
-  CXXRecordDecl *RD = Context->getBaseElementType(DTy)->getAsCXXRecordDecl();
-  if (RD) {
-    if (RD->isCompleteDefinition() && !RD->hasTrivialDestructor())
-      appendDeleteDtor(Block, RD, DE);
+  if (!DTy.isNull()) {
+    DTy = DTy.getNonReferenceType();
+    CXXRecordDecl *RD = Context->getBaseElementType(DTy)->getAsCXXRecordDecl();
+    if (RD) {
+      if (RD->isCompleteDefinition() && !RD->hasTrivialDestructor())
+        appendDeleteDtor(Block, RD, DE);
+    }
   }
 
   return VisitChildren(DE);
diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt
index 1df093d850983..fdc9e6cee8e16 100644
--- a/lib/Analysis/CMakeLists.txt
+++ b/lib/Analysis/CMakeLists.txt
@@ -9,12 +9,14 @@ add_clang_library(clangAnalysis
   CFGReachabilityAnalysis.cpp
   CFGStmtMap.cpp
   CallGraph.cpp
+  CloneDetection.cpp
   CocoaConventions.cpp
   Consumed.cpp
   CodeInjector.cpp
   Dominators.cpp
   FormatString.cpp
   LiveVariables.cpp
+  OSLog.cpp
   ObjCNoReturn.cpp
   PostOrderCFGView.cpp
   PrintfFormatString.cpp
diff --git a/lib/Analysis/CallGraph.cpp b/lib/Analysis/CallGraph.cpp
index 9d522fe7c6c51..8c126b09d0575 100644
--- a/lib/Analysis/CallGraph.cpp
+++ b/lib/Analysis/CallGraph.cpp
@@ -55,7 +55,7 @@ public:
   void addCalledDecl(Decl *D) {
     if (G->includeInGraph(D)) {
       CallGraphNode *CalleeNode = G->getOrInsertNode(D);
-      CallerNode->addCallee(CalleeNode, G);
+      CallerNode->addCallee(CalleeNode);
     }
   }
 
@@ -104,9 +104,7 @@ CallGraph::CallGraph() {
   Root = getOrInsertNode(nullptr);
 }
 
-CallGraph::~CallGraph() {
-  llvm::DeleteContainerSeconds(FunctionMap);
-}
+CallGraph::~CallGraph() {}
 
 bool CallGraph::includeInGraph(const Decl *D) {
   assert(D);
@@ -142,22 +140,22 @@ void CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) {
 CallGraphNode *CallGraph::getNode(const Decl *F) const {
   FunctionMapTy::const_iterator I = FunctionMap.find(F);
   if (I == FunctionMap.end()) return nullptr;
-  return I->second;
+  return I->second.get();
 }
 
 CallGraphNode *CallGraph::getOrInsertNode(Decl *F) {
   if (F && !isa<ObjCMethodDecl>(F))
     F = F->getCanonicalDecl();
 
-  CallGraphNode *&Node = FunctionMap[F];
+  std::unique_ptr<CallGraphNode> &Node = FunctionMap[F];
   if (Node)
-    return Node;
+    return Node.get();
 
-  Node = new CallGraphNode(F);
+  Node = llvm::make_unique<CallGraphNode>(F);
   // Make Root node a parent of all functions to make sure all are reachable.
   if (F)
-    Root->addCallee(Node, this);
-  return Node;
+    Root->addCallee(Node.get());
+  return Node.get();
 }
 
 void CallGraph::print(raw_ostream &OS) const {
diff --git a/lib/Analysis/CloneDetection.cpp b/lib/Analysis/CloneDetection.cpp
new file mode 100644
index 0000000000000..e761738214c6e
--- /dev/null
+++ b/lib/Analysis/CloneDetection.cpp
@@ -0,0 +1,894 @@
+//===--- CloneDetection.cpp - Finds code clones in an AST -------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+///  This file implements classes for searching and anlyzing source code clones.
+///
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/CloneDetection.h"
+
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/AST/Stmt.h"
+#include "clang/AST/StmtVisitor.h"
+#include "clang/Lex/Lexer.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/MD5.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace clang;
+
+StmtSequence::StmtSequence(const CompoundStmt *Stmt, ASTContext &Context,
+                           unsigned StartIndex, unsigned EndIndex)
+    : S(Stmt), Context(&Context), StartIndex(StartIndex), EndIndex(EndIndex) {
+  assert(Stmt && "Stmt must not be a nullptr");
+  assert(StartIndex < EndIndex && "Given array should not be empty");
+  assert(EndIndex <= Stmt->size() && "Given array too big for this Stmt");
+}
+
+StmtSequence::StmtSequence(const Stmt *Stmt, ASTContext &Context)
+    : S(Stmt), Context(&Context), StartIndex(0), EndIndex(0) {}
+
+StmtSequence::StmtSequence()
+    : S(nullptr), Context(nullptr), StartIndex(0), EndIndex(0) {}
+
+bool StmtSequence::contains(const StmtSequence &Other) const {
+  // If both sequences reside in different translation units, they can never
+  // contain each other.
+  if (Context != Other.Context)
+    return false;
+
+  const SourceManager &SM = Context->getSourceManager();
+
+  // Otherwise check if the start and end locations of the current sequence
+  // surround the other sequence.
+  bool StartIsInBounds =
+      SM.isBeforeInTranslationUnit(getStartLoc(), Other.getStartLoc()) ||
+      getStartLoc() == Other.getStartLoc();
+  if (!StartIsInBounds)
+    return false;
+
+  bool EndIsInBounds =
+      SM.isBeforeInTranslationUnit(Other.getEndLoc(), getEndLoc()) ||
+      Other.getEndLoc() == getEndLoc();
+  return EndIsInBounds;
+}
+
+StmtSequence::iterator StmtSequence::begin() const {
+  if (!holdsSequence()) {
+    return &S;
+  }
+  auto CS = cast<CompoundStmt>(S);
+  return CS->body_begin() + StartIndex;
+}
+
+StmtSequence::iterator StmtSequence::end() const {
+  if (!holdsSequence()) {
+    return reinterpret_cast<StmtSequence::iterator>(&S) + 1;
+  }
+  auto CS = cast<CompoundStmt>(S);
+  return CS->body_begin() + EndIndex;
+}
+
+SourceLocation StmtSequence::getStartLoc() const {
+  return front()->getLocStart();
+}
+
+SourceLocation StmtSequence::getEndLoc() const { return back()->getLocEnd(); }
+
+SourceRange StmtSequence::getSourceRange() const {
+  return SourceRange(getStartLoc(), getEndLoc());
+}
+
+namespace {
+
+/// \brief Analyzes the pattern of the referenced variables in a statement.
+class VariablePattern {
+
+  /// \brief Describes an occurence of a variable reference in a statement.
+  struct VariableOccurence {
+    /// The index of the associated VarDecl in the Variables vector.
+    size_t KindID;
+    /// The statement in the code where the variable was referenced.
+    const Stmt *Mention;
+
+    VariableOccurence(size_t KindID, const Stmt *Mention)
+        : KindID(KindID), Mention(Mention) {}
+  };
+
+  /// All occurences of referenced variables in the order of appearance.
+  std::vector<VariableOccurence> Occurences;
+  /// List of referenced variables in the order of appearance.
+  /// Every item in this list is unique.
+  std::vector<const VarDecl *> Variables;
+
+  /// \brief Adds a new variable referenced to this pattern.
+  /// \param VarDecl The declaration of the variable that is referenced.
+  /// \param Mention The SourceRange where this variable is referenced.
+  void addVariableOccurence(const VarDecl *VarDecl, const Stmt *Mention) {
+    // First check if we already reference this variable
+    for (size_t KindIndex = 0; KindIndex < Variables.size(); ++KindIndex) {
+      if (Variables[KindIndex] == VarDecl) {
+        // If yes, add a new occurence that points to the existing entry in
+        // the Variables vector.
+        Occurences.emplace_back(KindIndex, Mention);
+        return;
+      }
+    }
+    // If this variable wasn't already referenced, add it to the list of
+    // referenced variables and add a occurence that points to this new entry.
+    Occurences.emplace_back(Variables.size(), Mention);
+    Variables.push_back(VarDecl);
+  }
+
+  /// \brief Adds each referenced variable from the given statement.
+  void addVariables(const Stmt *S) {
+    // Sometimes we get a nullptr (such as from IfStmts which often have nullptr
+    // children). We skip such statements as they don't reference any
+    // variables.
+    if (!S)
+      return;
+
+    // Check if S is a reference to a variable. If yes, add it to the pattern.
+    if (auto D = dyn_cast<DeclRefExpr>(S)) {
+      if (auto VD = dyn_cast<VarDecl>(D->getDecl()->getCanonicalDecl()))
+        addVariableOccurence(VD, D);
+    }
+
+    // Recursively check all children of the given statement.
+    for (const Stmt *Child : S->children()) {
+      addVariables(Child);
+    }
+  }
+
+public:
+  /// \brief Creates an VariablePattern object with information about the given
+  ///        StmtSequence.
+  VariablePattern(const StmtSequence &Sequence) {
+    for (const Stmt *S : Sequence)
+      addVariables(S);
+  }
+
+  /// \brief Counts the differences between this pattern and the given one.
+  /// \param Other The given VariablePattern to compare with.
+  /// \param FirstMismatch Output parameter that will be filled with information
+  ///        about the first difference between the two patterns. This parameter
+  ///        can be a nullptr, in which case it will be ignored.
+  /// \return Returns the number of differences between the pattern this object
+  ///         is following and the given VariablePattern.
+  ///
+  /// For example, the following statements all have the same pattern and this
+  /// function would return zero:
+  ///
+  ///   if (a < b) return a; return b;
+  ///   if (x < y) return x; return y;
+  ///   if (u2 < u1) return u2; return u1;
+  ///
+  /// But the following statement has a different pattern (note the changed
+  /// variables in the return statements) and would have two differences when
+  /// compared with one of the statements above.
+  ///
+  ///   if (a < b) return b; return a;
+  ///
+  /// This function should only be called if the related statements of the given
+  /// pattern and the statements of this objects are clones of each other.
+  unsigned countPatternDifferences(
+      const VariablePattern &Other,
+      CloneDetector::SuspiciousClonePair *FirstMismatch = nullptr) {
+    unsigned NumberOfDifferences = 0;
+
+    assert(Other.Occurences.size() == Occurences.size());
+    for (unsigned i = 0; i < Occurences.size(); ++i) {
+      auto ThisOccurence = Occurences[i];
+      auto OtherOccurence = Other.Occurences[i];
+      if (ThisOccurence.KindID == OtherOccurence.KindID)
+        continue;
+
+      ++NumberOfDifferences;
+
+      // If FirstMismatch is not a nullptr, we need to store information about
+      // the first difference between the two patterns.
+      if (FirstMismatch == nullptr)
+        continue;
+
+      // Only proceed if we just found the first difference as we only store
+      // information about the first difference.
+      if (NumberOfDifferences != 1)
+        continue;
+
+      const VarDecl *FirstSuggestion = nullptr;
+      // If there is a variable available in the list of referenced variables
+      // which wouldn't break the pattern if it is used in place of the
+      // current variable, we provide this variable as the suggested fix.
+      if (OtherOccurence.KindID < Variables.size())
+        FirstSuggestion = Variables[OtherOccurence.KindID];
+
+      // Store information about the first clone.
+      FirstMismatch->FirstCloneInfo =
+          CloneDetector::SuspiciousClonePair::SuspiciousCloneInfo(
+              Variables[ThisOccurence.KindID], ThisOccurence.Mention,
+              FirstSuggestion);
+
+      // Same as above but with the other clone. We do this for both clones as
+      // we don't know which clone is the one containing the unintended
+      // pattern error.
+      const VarDecl *SecondSuggestion = nullptr;
+      if (ThisOccurence.KindID < Other.Variables.size())
+        SecondSuggestion = Other.Variables[ThisOccurence.KindID];
+
+      // Store information about the second clone.
+      FirstMismatch->SecondCloneInfo =
+          CloneDetector::SuspiciousClonePair::SuspiciousCloneInfo(
+              Other.Variables[OtherOccurence.KindID], OtherOccurence.Mention,
+              SecondSuggestion);
+
+      // SuspiciousClonePair guarantees that the first clone always has a
+      // suggested variable associated with it. As we know that one of the two
+      // clones in the pair always has suggestion, we swap the two clones
+      // in case the first clone has no suggested variable which means that
+      // the second clone has a suggested variable and should be first.
+      if (!FirstMismatch->FirstCloneInfo.Suggestion)
+        std::swap(FirstMismatch->FirstCloneInfo,
+                  FirstMismatch->SecondCloneInfo);
+
+      // This ensures that we always have at least one suggestion in a pair.
+      assert(FirstMismatch->FirstCloneInfo.Suggestion);
+    }
+
+    return NumberOfDifferences;
+  }
+};
+}
+
+/// \brief Prints the macro name that contains the given SourceLocation into
+///        the given raw_string_ostream.
+static void printMacroName(llvm::raw_string_ostream &MacroStack,
+                           ASTContext &Context, SourceLocation Loc) {
+  MacroStack << Lexer::getImmediateMacroName(Loc, Context.getSourceManager(),
+                                             Context.getLangOpts());
+
+  // Add an empty space at the end as a padding to prevent
+  // that macro names concatenate to the names of other macros.
+  MacroStack << " ";
+}
+
+/// \brief Returns a string that represents all macro expansions that
+///        expanded into the given SourceLocation.
+///
+/// If 'getMacroStack(A) == getMacroStack(B)' is true, then the SourceLocations
+/// A and B are expanded from the same macros in the same order.
+static std::string getMacroStack(SourceLocation Loc, ASTContext &Context) {
+  std::string MacroStack;
+  llvm::raw_string_ostream MacroStackStream(MacroStack);
+  SourceManager &SM = Context.getSourceManager();
+
+  // Iterate over all macros that expanded into the given SourceLocation.
+  while (Loc.isMacroID()) {
+    // Add the macro name to the stream.
+    printMacroName(MacroStackStream, Context, Loc);
+    Loc = SM.getImmediateMacroCallerLoc(Loc);
+  }
+  MacroStackStream.flush();
+  return MacroStack;
+}
+
+namespace {
+/// \brief Collects the data of a single Stmt.
+///
+/// This class defines what a code clone is: If it collects for two statements
+/// the same data, then those two statements are considered to be clones of each
+/// other.
+///
+/// All collected data is forwarded to the given data consumer of the type T.
+/// The data consumer class needs to provide a member method with the signature:
+///   update(StringRef Str)
+template <typename T>
+class StmtDataCollector : public ConstStmtVisitor<StmtDataCollector<T>> {
+
+  ASTContext &Context;
+  /// \brief The data sink to which all data is forwarded.
+  T &DataConsumer;
+
+public:
+  /// \brief Collects data of the given Stmt.
+  /// \param S The given statement.
+  /// \param Context The ASTContext of S.
+  /// \param DataConsumer The data sink to which all data is forwarded.
+  StmtDataCollector(const Stmt *S, ASTContext &Context, T &DataConsumer)
+      : Context(Context), DataConsumer(DataConsumer) {
+    this->Visit(S);
+  }
+
+  // Below are utility methods for appending different data to the vector.
+
+  void addData(CloneDetector::DataPiece Integer) {
+    DataConsumer.update(
+        StringRef(reinterpret_cast<char *>(&Integer), sizeof(Integer)));
+  }
+
+  void addData(llvm::StringRef Str) { DataConsumer.update(Str); }
+
+  void addData(const QualType &QT) { addData(QT.getAsString()); }
+
+// The functions below collect the class specific data of each Stmt subclass.
+
+// Utility macro for defining a visit method for a given class. This method
+// calls back to the ConstStmtVisitor to visit all parent classes.
+#define DEF_ADD_DATA(CLASS, CODE)                                              \
+  void Visit##CLASS(const CLASS *S) {                                          \
+    CODE;                                                                      \
+    ConstStmtVisitor<StmtDataCollector>::Visit##CLASS(S);                      \
+  }
+
+  DEF_ADD_DATA(Stmt, {
+    addData(S->getStmtClass());
+    // This ensures that macro generated code isn't identical to macro-generated
+    // code.
+    addData(getMacroStack(S->getLocStart(), Context));
+    addData(getMacroStack(S->getLocEnd(), Context));
+  })
+  DEF_ADD_DATA(Expr, { addData(S->getType()); })
+
+  //--- Builtin functionality ----------------------------------------------//
+  DEF_ADD_DATA(ArrayTypeTraitExpr, { addData(S->getTrait()); })
+  DEF_ADD_DATA(ExpressionTraitExpr, { addData(S->getTrait()); })
+  DEF_ADD_DATA(PredefinedExpr, { addData(S->getIdentType()); })
+  DEF_ADD_DATA(TypeTraitExpr, {
+    addData(S->getTrait());
+    for (unsigned i = 0; i < S->getNumArgs(); ++i)
+      addData(S->getArg(i)->getType());
+  })
+
+  //--- Calls --------------------------------------------------------------//
+  DEF_ADD_DATA(CallExpr, {
+    // Function pointers don't have a callee and we just skip hashing it.
+    if (const FunctionDecl *D = S->getDirectCallee()) {
+      // If the function is a template specialization, we also need to handle
+      // the template arguments as they are not included in the qualified name.
+      if (auto Args = D->getTemplateSpecializationArgs()) {
+        std::string ArgString;
+
+        // Print all template arguments into ArgString
+        llvm::raw_string_ostream OS(ArgString);
+        for (unsigned i = 0; i < Args->size(); ++i) {
+          Args->get(i).print(Context.getLangOpts(), OS);
+          // Add a padding character so that 'foo<X, XX>()' != 'foo<XX, X>()'.
+          OS << '\n';
+        }
+        OS.flush();
+
+        addData(ArgString);
+      }
+      addData(D->getQualifiedNameAsString());
+    }
+  })
+
+  //--- Exceptions ---------------------------------------------------------//
+  DEF_ADD_DATA(CXXCatchStmt, { addData(S->getCaughtType()); })
+
+  //--- C++ OOP Stmts ------------------------------------------------------//
+  DEF_ADD_DATA(CXXDeleteExpr, {
+    addData(S->isArrayFormAsWritten());
+    addData(S->isGlobalDelete());
+  })
+
+  //--- Casts --------------------------------------------------------------//
+  DEF_ADD_DATA(ObjCBridgedCastExpr, { addData(S->getBridgeKind()); })
+
+  //--- Miscellaneous Exprs ------------------------------------------------//
+  DEF_ADD_DATA(BinaryOperator, { addData(S->getOpcode()); })
+  DEF_ADD_DATA(UnaryOperator, { addData(S->getOpcode()); })
+
+  //--- Control flow -------------------------------------------------------//
+  DEF_ADD_DATA(GotoStmt, { addData(S->getLabel()->getName()); })
+  DEF_ADD_DATA(IndirectGotoStmt, {
+    if (S->getConstantTarget())
+      addData(S->getConstantTarget()->getName());
+  })
+  DEF_ADD_DATA(LabelStmt, { addData(S->getDecl()->getName()); })
+  DEF_ADD_DATA(MSDependentExistsStmt, { addData(S->isIfExists()); })
+  DEF_ADD_DATA(AddrLabelExpr, { addData(S->getLabel()->getName()); })
+
+  //--- Objective-C --------------------------------------------------------//
+  DEF_ADD_DATA(ObjCIndirectCopyRestoreExpr, { addData(S->shouldCopy()); })
+  DEF_ADD_DATA(ObjCPropertyRefExpr, {
+    addData(S->isSuperReceiver());
+    addData(S->isImplicitProperty());
+  })
+  DEF_ADD_DATA(ObjCAtCatchStmt, { addData(S->hasEllipsis()); })
+
+  //--- Miscellaneous Stmts ------------------------------------------------//
+  DEF_ADD_DATA(CXXFoldExpr, {
+    addData(S->isRightFold());
+    addData(S->getOperator());
+  })
+  DEF_ADD_DATA(GenericSelectionExpr, {
+    for (unsigned i = 0; i < S->getNumAssocs(); ++i) {
+      addData(S->getAssocType(i));
+    }
+  })
+  DEF_ADD_DATA(LambdaExpr, {
+    for (const LambdaCapture &C : S->captures()) {
+      addData(C.isPackExpansion());
+      addData(C.getCaptureKind());
+      if (C.capturesVariable())
+        addData(C.getCapturedVar()->getType());
+    }
+    addData(S->isGenericLambda());
+    addData(S->isMutable());
+  })
+  DEF_ADD_DATA(DeclStmt, {
+    auto numDecls = std::distance(S->decl_begin(), S->decl_end());
+    addData(static_cast<CloneDetector::DataPiece>(numDecls));
+    for (const Decl *D : S->decls()) {
+      if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
+        addData(VD->getType());
+      }
+    }
+  })
+  DEF_ADD_DATA(AsmStmt, {
+    addData(S->isSimple());
+    addData(S->isVolatile());
+    addData(S->generateAsmString(Context));
+    for (unsigned i = 0; i < S->getNumInputs(); ++i) {
+      addData(S->getInputConstraint(i));
+    }
+    for (unsigned i = 0; i < S->getNumOutputs(); ++i) {
+      addData(S->getOutputConstraint(i));
+    }
+    for (unsigned i = 0; i < S->getNumClobbers(); ++i) {
+      addData(S->getClobber(i));
+    }
+  })
+  DEF_ADD_DATA(AttributedStmt, {
+    for (const Attr *A : S->getAttrs()) {
+      addData(std::string(A->getSpelling()));
+    }
+  })
+};
+} // end anonymous namespace
+
+namespace {
+/// Generates CloneSignatures for a set of statements and stores the results in
+/// a CloneDetector object.
+class CloneSignatureGenerator {
+
+  CloneDetector &CD;
+  ASTContext &Context;
+
+  /// \brief Generates CloneSignatures for all statements in the given statement
+  /// tree and stores them in the CloneDetector.
+  ///
+  /// \param S The root of the given statement tree.
+  /// \param ParentMacroStack A string representing the macros that generated
+  ///                         the parent statement or an empty string if no
+  ///                         macros generated the parent statement.
+  ///                         See getMacroStack() for generating such a string.
+  /// \return The CloneSignature of the root statement.
+  CloneDetector::CloneSignature
+  generateSignatures(const Stmt *S, const std::string &ParentMacroStack) {
+    // Create an empty signature that will be filled in this method.
+    CloneDetector::CloneSignature Signature;
+
+    llvm::MD5 Hash;
+
+    // Collect all relevant data from S and hash it.
+    StmtDataCollector<llvm::MD5>(S, Context, Hash);
+
+    // Look up what macros expanded into the current statement.
+    std::string StartMacroStack = getMacroStack(S->getLocStart(), Context);
+    std::string EndMacroStack = getMacroStack(S->getLocEnd(), Context);
+
+    // First, check if ParentMacroStack is not empty which means we are currently
+    // dealing with a parent statement which was expanded from a macro.
+    // If this parent statement was expanded from the same macros as this
+    // statement, we reduce the initial complexity of this statement to zero.
+    // This causes that a group of statements that were generated by a single
+    // macro expansion will only increase the total complexity by one.
+    // Note: This is not the final complexity of this statement as we still
+    // add the complexity of the child statements to the complexity value.
+    if (!ParentMacroStack.empty() && (StartMacroStack == ParentMacroStack &&
+                                      EndMacroStack == ParentMacroStack)) {
+      Signature.Complexity = 0;
+    }
+
+    // Storage for the signatures of the direct child statements. This is only
+    // needed if the current statement is a CompoundStmt.
+    std::vector<CloneDetector::CloneSignature> ChildSignatures;
+    const CompoundStmt *CS = dyn_cast<const CompoundStmt>(S);
+
+    // The signature of a statement includes the signatures of its children.
+    // Therefore we create the signatures for every child and add them to the
+    // current signature.
+    for (const Stmt *Child : S->children()) {
+      // Some statements like 'if' can have nullptr children that we will skip.
+      if (!Child)
+        continue;
+
+      // Recursive call to create the signature of the child statement. This
+      // will also create and store all clone groups in this child statement.
+      // We pass only the StartMacroStack along to keep things simple.
+      auto ChildSignature = generateSignatures(Child, StartMacroStack);
+
+      // Add the collected data to the signature of the current statement.
+      Signature.Complexity += ChildSignature.Complexity;
+      Hash.update(StringRef(reinterpret_cast<char *>(&ChildSignature.Hash),
+                            sizeof(ChildSignature.Hash)));
+
+      // If the current statement is a CompoundStatement, we need to store the
+      // signature for the generation of the sub-sequences.
+      if (CS)
+        ChildSignatures.push_back(ChildSignature);
+    }
+
+    // If the current statement is a CompoundStmt, we also need to create the
+    // clone groups from the sub-sequences inside the children.
+    if (CS)
+      handleSubSequences(CS, ChildSignatures);
+
+    // Create the final hash code for the current signature.
+    llvm::MD5::MD5Result HashResult;
+    Hash.final(HashResult);
+
+    // Copy as much of the generated hash code to the signature's hash code.
+    std::memcpy(&Signature.Hash, &HashResult,
+                std::min(sizeof(Signature.Hash), sizeof(HashResult)));
+
+    // Save the signature for the current statement in the CloneDetector object.
+    CD.add(StmtSequence(S, Context), Signature);
+
+    return Signature;
+  }
+
+  /// \brief Adds all possible sub-sequences in the child array of the given
+  ///        CompoundStmt to the CloneDetector.
+  /// \param CS The given CompoundStmt.
+  /// \param ChildSignatures A list of calculated signatures for each child in
+  ///                        the given CompoundStmt.
+  void handleSubSequences(
+      const CompoundStmt *CS,
+      const std::vector<CloneDetector::CloneSignature> &ChildSignatures) {
+
+    // FIXME: This function has quadratic runtime right now. Check if skipping
+    // this function for too long CompoundStmts is an option.
+
+    // The length of the sub-sequence. We don't need to handle sequences with
+    // the length 1 as they are already handled in CollectData().
+    for (unsigned Length = 2; Length <= CS->size(); ++Length) {
+      // The start index in the body of the CompoundStmt. We increase the
+      // position until the end of the sub-sequence reaches the end of the
+      // CompoundStmt body.
+      for (unsigned Pos = 0; Pos <= CS->size() - Length; ++Pos) {
+        // Create an empty signature and add the signatures of all selected
+        // child statements to it.
+        CloneDetector::CloneSignature SubSignature;
+        llvm::MD5 SubHash;
+
+        for (unsigned i = Pos; i < Pos + Length; ++i) {
+          SubSignature.Complexity += ChildSignatures[i].Complexity;
+          size_t ChildHash = ChildSignatures[i].Hash;
+
+          SubHash.update(StringRef(reinterpret_cast<char *>(&ChildHash),
+                                sizeof(ChildHash)));
+        }
+
+        // Create the final hash code for the current signature.
+        llvm::MD5::MD5Result HashResult;
+        SubHash.final(HashResult);
+
+        // Copy as much of the generated hash code to the signature's hash code.
+        std::memcpy(&SubSignature.Hash, &HashResult,
+                    std::min(sizeof(SubSignature.Hash), sizeof(HashResult)));
+
+        // Save the signature together with the information about what children
+        // sequence we selected.
+        CD.add(StmtSequence(CS, Context, Pos, Pos + Length), SubSignature);
+      }
+    }
+  }
+
+public:
+  explicit CloneSignatureGenerator(CloneDetector &CD, ASTContext &Context)
+      : CD(CD), Context(Context) {}
+
+  /// \brief Generates signatures for all statements in the given function body.
+  void consumeCodeBody(const Stmt *S) { generateSignatures(S, ""); }
+};
+} // end anonymous namespace
+
+void CloneDetector::analyzeCodeBody(const Decl *D) {
+  assert(D);
+  assert(D->hasBody());
+  CloneSignatureGenerator Generator(*this, D->getASTContext());
+  Generator.consumeCodeBody(D->getBody());
+}
+
+void CloneDetector::add(const StmtSequence &S,
+                        const CloneSignature &Signature) {
+  Sequences.push_back(std::make_pair(Signature, S));
+}
+
+namespace {
+/// \brief Returns true if and only if \p Stmt contains at least one other
+/// sequence in the \p Group.
+bool containsAnyInGroup(StmtSequence &Stmt, CloneDetector::CloneGroup &Group) {
+  for (StmtSequence &GroupStmt : Group.Sequences) {
+    if (Stmt.contains(GroupStmt))
+      return true;
+  }
+  return false;
+}
+
+/// \brief Returns true if and only if all sequences in \p OtherGroup are
+/// contained by a sequence in \p Group.
+bool containsGroup(CloneDetector::CloneGroup &Group,
+                   CloneDetector::CloneGroup &OtherGroup) {
+  // We have less sequences in the current group than we have in the other,
+  // so we will never fulfill the requirement for returning true. This is only
+  // possible because we know that a sequence in Group can contain at most
+  // one sequence in OtherGroup.
+  if (Group.Sequences.size() < OtherGroup.Sequences.size())
+    return false;
+
+  for (StmtSequence &Stmt : Group.Sequences) {
+    if (!containsAnyInGroup(Stmt, OtherGroup))
+      return false;
+  }
+  return true;
+}
+} // end anonymous namespace
+
+namespace {
+/// \brief Wrapper around FoldingSetNodeID that it can be used as the template
+///        argument of the StmtDataCollector.
+class FoldingSetNodeIDWrapper {
+
+  llvm::FoldingSetNodeID &FS;
+
+public:
+  FoldingSetNodeIDWrapper(llvm::FoldingSetNodeID &FS) : FS(FS) {}
+
+  void update(StringRef Str) { FS.AddString(Str); }
+};
+} // end anonymous namespace
+
+/// \brief Writes the relevant data from all statements and child statements
+///        in the given StmtSequence into the given FoldingSetNodeID.
+static void CollectStmtSequenceData(const StmtSequence &Sequence,
+                                    FoldingSetNodeIDWrapper &OutputData) {
+  for (const Stmt *S : Sequence) {
+    StmtDataCollector<FoldingSetNodeIDWrapper>(S, Sequence.getASTContext(),
+                                               OutputData);
+
+    for (const Stmt *Child : S->children()) {
+      if (!Child)
+        continue;
+
+      CollectStmtSequenceData(StmtSequence(Child, Sequence.getASTContext()),
+                              OutputData);
+    }
+  }
+}
+
+/// \brief Returns true if both sequences are clones of each other.
+static bool areSequencesClones(const StmtSequence &LHS,
+                               const StmtSequence &RHS) {
+  // We collect the data from all statements in the sequence as we did before
+  // when generating a hash value for each sequence. But this time we don't
+  // hash the collected data and compare the whole data set instead. This
+  // prevents any false-positives due to hash code collisions.
+  llvm::FoldingSetNodeID DataLHS, DataRHS;
+  FoldingSetNodeIDWrapper LHSWrapper(DataLHS);
+  FoldingSetNodeIDWrapper RHSWrapper(DataRHS);
+
+  CollectStmtSequenceData(LHS, LHSWrapper);
+  CollectStmtSequenceData(RHS, RHSWrapper);
+
+  return DataLHS == DataRHS;
+}
+
+/// \brief Finds all actual clone groups in a single group of presumed clones.
+/// \param Result Output parameter to which all found groups are added.
+/// \param Group A group of presumed clones. The clones are allowed to have a
+///              different variable pattern and may not be actual clones of each
+///              other.
+/// \param CheckVariablePattern If true, every clone in a group that was added
+///              to the output follows the same variable pattern as the other
+///              clones in its group.
+static void createCloneGroups(std::vector<CloneDetector::CloneGroup> &Result,
+                              const CloneDetector::CloneGroup &Group,
+                              bool CheckVariablePattern) {
+  // We remove the Sequences one by one, so a list is more appropriate.
+  std::list<StmtSequence> UnassignedSequences(Group.Sequences.begin(),
+                                              Group.Sequences.end());
+
+  // Search for clones as long as there could be clones in UnassignedSequences.
+  while (UnassignedSequences.size() > 1) {
+
+    // Pick the first Sequence as a protoype for a new clone group.
+    StmtSequence Prototype = UnassignedSequences.front();
+    UnassignedSequences.pop_front();
+
+    CloneDetector::CloneGroup FilteredGroup(Prototype, Group.Signature);
+
+    // Analyze the variable pattern of the prototype. Every other StmtSequence
+    // needs to have the same pattern to get into the new clone group.
+    VariablePattern PrototypeFeatures(Prototype);
+
+    // Search all remaining StmtSequences for an identical variable pattern
+    // and assign them to our new clone group.
+    auto I = UnassignedSequences.begin(), E = UnassignedSequences.end();
+    while (I != E) {
+      // If the sequence doesn't fit to the prototype, we have encountered
+      // an unintended hash code collision and we skip it.
+      if (!areSequencesClones(Prototype, *I)) {
+        ++I;
+        continue;
+      }
+
+      // If we weren't asked to check for a matching variable pattern in clone
+      // groups we can add the sequence now to the new clone group.
+      // If we were asked to check for matching variable pattern, we first have
+      // to check that there are no differences between the two patterns and
+      // only proceed if they match.
+      if (!CheckVariablePattern ||
+          VariablePattern(*I).countPatternDifferences(PrototypeFeatures) == 0) {
+        FilteredGroup.Sequences.push_back(*I);
+        I = UnassignedSequences.erase(I);
+        continue;
+      }
+
+      // We didn't found a matching variable pattern, so we continue with the
+      // next sequence.
+      ++I;
+    }
+
+    // Add a valid clone group to the list of found clone groups.
+    if (!FilteredGroup.isValid())
+      continue;
+
+    Result.push_back(FilteredGroup);
+  }
+}
+
+void CloneDetector::findClones(std::vector<CloneGroup> &Result,
+                               unsigned MinGroupComplexity,
+                               bool CheckPatterns) {
+  // A shortcut (and necessary for the for-loop later in this function).
+  if (Sequences.empty())
+    return;
+
+  // We need to search for groups of StmtSequences with the same hash code to
+  // create our initial clone groups. By sorting all known StmtSequences by
+  // their hash value we make sure that StmtSequences with the same hash code
+  // are grouped together in the Sequences vector.
+  // Note: We stable sort here because the StmtSequences are added in the order
+  // in which they appear in the source file. We want to preserve that order
+  // because we also want to report them in that order in the CloneChecker.
+  std::stable_sort(Sequences.begin(), Sequences.end(),
+                   [](std::pair<CloneSignature, StmtSequence> LHS,
+                      std::pair<CloneSignature, StmtSequence> RHS) {
+                     return LHS.first.Hash < RHS.first.Hash;
+                   });
+
+  std::vector<CloneGroup> CloneGroups;
+
+  // Check for each CloneSignature if its successor has the same hash value.
+  // We don't check the last CloneSignature as it has no successor.
+  // Note: The 'size - 1' in the condition is safe because we check for an empty
+  // Sequences vector at the beginning of this function.
+  for (unsigned i = 0; i < Sequences.size() - 1; ++i) {
+    const auto Current = Sequences[i];
+    const auto Next = Sequences[i + 1];
+
+    if (Current.first.Hash != Next.first.Hash)
+      continue;
+
+    // It's likely that we just found an sequence of CloneSignatures that
+    // represent a CloneGroup, so we create a new group and start checking and
+    // adding the CloneSignatures in this sequence.
+    CloneGroup Group;
+    Group.Signature = Current.first;
+
+    for (; i < Sequences.size(); ++i) {
+      const auto &Signature = Sequences[i];
+
+      // A different hash value means we have reached the end of the sequence.
+      if (Current.first.Hash != Signature.first.Hash) {
+        // The current Signature could be the start of a new CloneGroup. So we
+        // decrement i so that we visit it again in the outer loop.
+        // Note: i can never be 0 at this point because we are just comparing
+        // the hash of the Current CloneSignature with itself in the 'if' above.
+        assert(i != 0);
+        --i;
+        break;
+      }
+
+      // Skip CloneSignatures that won't pass the complexity requirement.
+      if (Signature.first.Complexity < MinGroupComplexity)
+        continue;
+
+      Group.Sequences.push_back(Signature.second);
+    }
+
+    // There is a chance that we haven't found more than two fitting
+    // CloneSignature because not enough CloneSignatures passed the complexity
+    // requirement. As a CloneGroup with less than two members makes no sense,
+    // we ignore this CloneGroup and won't add it to the result.
+    if (!Group.isValid())
+      continue;
+
+    CloneGroups.push_back(Group);
+  }
+
+  // Add every valid clone group that fulfills the complexity requirement.
+  for (const CloneGroup &Group : CloneGroups) {
+    createCloneGroups(Result, Group, CheckPatterns);
+  }
+
+  std::vector<unsigned> IndexesToRemove;
+
+  // Compare every group in the result with the rest. If one groups contains
+  // another group, we only need to return the bigger group.
+  // Note: This doesn't scale well, so if possible avoid calling any heavy
+  // function from this loop to minimize the performance impact.
+  for (unsigned i = 0; i < Result.size(); ++i) {
+    for (unsigned j = 0; j < Result.size(); ++j) {
+      // Don't compare a group with itself.
+      if (i == j)
+        continue;
+
+      if (containsGroup(Result[j], Result[i])) {
+        IndexesToRemove.push_back(i);
+        break;
+      }
+    }
+  }
+
+  // Erasing a list of indexes from the vector should be done with decreasing
+  // indexes. As IndexesToRemove is constructed with increasing values, we just
+  // reverse iterate over it to get the desired order.
+  for (auto I = IndexesToRemove.rbegin(); I != IndexesToRemove.rend(); ++I) {
+    Result.erase(Result.begin() + *I);
+  }
+}
+
+void CloneDetector::findSuspiciousClones(
+    std::vector<CloneDetector::SuspiciousClonePair> &Result,
+    unsigned MinGroupComplexity) {
+  std::vector<CloneGroup> Clones;
+  // Reuse the normal search for clones but specify that the clone groups don't
+  // need to have a common referenced variable pattern so that we can manually
+  // search for the kind of pattern errors this function is supposed to find.
+  findClones(Clones, MinGroupComplexity, false);
+
+  for (const CloneGroup &Group : Clones) {
+    for (unsigned i = 0; i < Group.Sequences.size(); ++i) {
+      VariablePattern PatternA(Group.Sequences[i]);
+
+      for (unsigned j = i + 1; j < Group.Sequences.size(); ++j) {
+        VariablePattern PatternB(Group.Sequences[j]);
+
+        CloneDetector::SuspiciousClonePair ClonePair;
+        // For now, we only report clones which break the variable pattern just
+        // once because multiple differences in a pattern are an indicator that
+        // those differences are maybe intended (e.g. because it's actually
+        // a different algorithm).
+        // TODO: In very big clones even multiple variables can be unintended,
+        // so replacing this number with a percentage could better handle such
+        // cases. On the other hand it could increase the false-positive rate
+        // for all clones if the percentage is too high.
+        if (PatternA.countPatternDifferences(PatternB, &ClonePair) == 1) {
+          Result.push_back(ClonePair);
+          break;
+        }
+      }
+    }
+  }
+}
diff --git a/lib/Analysis/Consumed.cpp b/lib/Analysis/Consumed.cpp
index 47bef1b927c9e..f6fe78ac4619c 100644
--- a/lib/Analysis/Consumed.cpp
+++ b/lib/Analysis/Consumed.cpp
@@ -12,6 +12,7 @@
 //
 //===----------------------------------------------------------------------===//
 
+#include "clang/Analysis/Analyses/Consumed.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Attr.h"
 #include "clang/AST/DeclCXX.h"
@@ -20,16 +21,12 @@
 #include "clang/AST/StmtCXX.h"
 #include "clang/AST/StmtVisitor.h"
 #include "clang/AST/Type.h"
-#include "clang/Analysis/Analyses/Consumed.h"
 #include "clang/Analysis/Analyses/PostOrderCFGView.h"
 #include "clang/Analysis/AnalysisContext.h"
 #include "clang/Analysis/CFG.h"
 #include "clang/Basic/OperatorKinds.h"
 #include "clang/Basic/SourceLocation.h"
 #include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/SmallVector.h"
-#include "llvm/Support/Compiler.h"
-#include "llvm/Support/raw_ostream.h"
 #include <memory>
 
 // TODO: Adjust states of args to constructors in the same way that arguments to
diff --git a/lib/Analysis/FormatString.cpp b/lib/Analysis/FormatString.cpp
index 83d08b55427fd..c62e537e92dd9 100644
--- a/lib/Analysis/FormatString.cpp
+++ b/lib/Analysis/FormatString.cpp
@@ -266,14 +266,15 @@ bool clang::analyze_format_string::ParseUTF8InvalidSpecifier(
   if (SpecifierBegin + 1 >= FmtStrEnd)
     return false;
 
-  const UTF8 *SB = reinterpret_cast<const UTF8 *>(SpecifierBegin + 1);
-  const UTF8 *SE = reinterpret_cast<const UTF8 *>(FmtStrEnd);
+  const llvm::UTF8 *SB =
+      reinterpret_cast<const llvm::UTF8 *>(SpecifierBegin + 1);
+  const llvm::UTF8 *SE = reinterpret_cast<const llvm::UTF8 *>(FmtStrEnd);
   const char FirstByte = *SB;
 
   // If the invalid specifier is a multibyte UTF-8 string, return the
   // total length accordingly so that the conversion specifier can be
   // properly updated to reflect a complete UTF-8 specifier.
-  unsigned NumBytes = getNumBytesForUTF8(FirstByte);
+  unsigned NumBytes = llvm::getNumBytesForUTF8(FirstByte);
   if (NumBytes == 1)
     return false;
   if (SB + NumBytes > SE)
@@ -310,8 +311,13 @@ ArgType::matchesType(ASTContext &C, QualType argTy) const {
       return Match;
 
     case AnyCharTy: {
-      if (const EnumType *ETy = argTy->getAs<EnumType>())
+      if (const EnumType *ETy = argTy->getAs<EnumType>()) {
+        // If the enum is incomplete we know nothing about the underlying type.
+        // Assume that it's 'int'.
+        if (!ETy->getDecl()->isComplete())
+          return NoMatch;
         argTy = ETy->getDecl()->getIntegerType();
+      }
 
       if (const BuiltinType *BT = argTy->getAs<BuiltinType>())
         switch (BT->getKind()) {
@@ -327,8 +333,14 @@ ArgType::matchesType(ASTContext &C, QualType argTy) const {
     }
 
     case SpecificTy: {
-      if (const EnumType *ETy = argTy->getAs<EnumType>())
-        argTy = ETy->getDecl()->getIntegerType();
+      if (const EnumType *ETy = argTy->getAs<EnumType>()) {
+        // If the enum is incomplete we know nothing about the underlying type.
+        // Assume that it's 'int'.
+        if (!ETy->getDecl()->isComplete())
+          argTy = C.IntTy;
+        else
+          argTy = ETy->getDecl()->getIntegerType();
+      }
       argTy = C.getCanonicalType(argTy).getUnqualifiedType();
 
       if (T == argTy)
@@ -579,6 +591,8 @@ const char *ConversionSpecifier::toString() const {
   case cArg: return "c";
   case sArg: return "s";
   case pArg: return "p";
+  case PArg:
+    return "P";
   case nArg: return "n";
   case PercentArg:  return "%";
   case ScanListArg: return "[";
@@ -854,6 +868,7 @@ bool FormatSpecifier::hasStandardConversionSpecifier(
     case ConversionSpecifier::ObjCObjArg:
     case ConversionSpecifier::ScanListArg:
     case ConversionSpecifier::PercentArg:
+    case ConversionSpecifier::PArg:
       return true;
     case ConversionSpecifier::CArg:
     case ConversionSpecifier::SArg:
diff --git a/lib/Analysis/FormatStringParsing.h b/lib/Analysis/FormatStringParsing.h
index 8463fcec5bf49..17fd2f6aefb8a 100644
--- a/lib/Analysis/FormatStringParsing.h
+++ b/lib/Analysis/FormatStringParsing.h
@@ -4,7 +4,6 @@
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Type.h"
 #include "clang/Analysis/Analyses/FormatString.h"
-#include "llvm/Support/raw_ostream.h"
 
 namespace clang {
 
diff --git a/lib/Analysis/LiveVariables.cpp b/lib/Analysis/LiveVariables.cpp
index 5e0a9a0d73c8f..cd73a62e6918c 100644
--- a/lib/Analysis/LiveVariables.cpp
+++ b/lib/Analysis/LiveVariables.cpp
@@ -19,6 +19,7 @@
 #include "clang/Analysis/CFG.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/PriorityQueue.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <vector>
@@ -28,20 +29,21 @@ using namespace clang;
 namespace {
 
 class DataflowWorklist {
-  SmallVector<const CFGBlock *, 20> worklist;
   llvm::BitVector enqueuedBlocks;
   PostOrderCFGView *POV;
+  llvm::PriorityQueue<const CFGBlock *, SmallVector<const CFGBlock *, 20>,
+                      PostOrderCFGView::BlockOrderCompare> worklist;
+
 public:
   DataflowWorklist(const CFG &cfg, AnalysisDeclContext &Ctx)
     : enqueuedBlocks(cfg.getNumBlockIDs()),
-      POV(Ctx.getAnalysis<PostOrderCFGView>()) {}
+      POV(Ctx.getAnalysis<PostOrderCFGView>()),
+      worklist(POV->getComparator()) {}
   
   void enqueueBlock(const CFGBlock *block);
   void enqueuePredecessors(const CFGBlock *block);
 
   const CFGBlock *dequeue();
-
-  void sortWorklist();
 };
 
 }
@@ -49,31 +51,22 @@ public:
 void DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) {
   if (block && !enqueuedBlocks[block->getBlockID()]) {
     enqueuedBlocks[block->getBlockID()] = true;
-    worklist.push_back(block);
+    worklist.push(block);
   }
 }
 
 void DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) {
-  const unsigned OldWorklistSize = worklist.size();
   for (CFGBlock::const_pred_iterator I = block->pred_begin(),
        E = block->pred_end(); I != E; ++I) {
     enqueueBlock(*I);
   }
-  
-  if (OldWorklistSize == 0 || OldWorklistSize == worklist.size())
-    return;
-
-  sortWorklist();
-}
-
-void DataflowWorklist::sortWorklist() {
-  std::sort(worklist.begin(), worklist.end(), POV->getComparator());
 }
 
 const CFGBlock *DataflowWorklist::dequeue() {
   if (worklist.empty())
     return nullptr;
-  const CFGBlock *b = worklist.pop_back_val();
+  const CFGBlock *b = worklist.top();
+  worklist.pop();
   enqueuedBlocks[b->getBlockID()] = false;
   return b;
 }
@@ -528,8 +521,6 @@ LiveVariables::computeLiveness(AnalysisDeclContext &AC,
       }
   }
   
-  worklist.sortWorklist();
-  
   while (const CFGBlock *block = worklist.dequeue()) {
     // Determine if the block's end value has changed.  If not, we
     // have nothing left to do for this block.
diff --git a/lib/Analysis/OSLog.cpp b/lib/Analysis/OSLog.cpp
new file mode 100644
index 0000000000000..3e13a153c65fa
--- /dev/null
+++ b/lib/Analysis/OSLog.cpp
@@ -0,0 +1,202 @@
+// TODO: header template
+
+#include "clang/Analysis/Analyses/OSLog.h"
+#include "clang/AST/Attr.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/DeclCXX.h"
+#include "clang/AST/ExprObjC.h"
+#include "clang/Analysis/Analyses/FormatString.h"
+#include "clang/Basic/Builtins.h"
+#include "llvm/ADT/SmallBitVector.h"
+
+using namespace clang;
+using llvm::APInt;
+
+using clang::analyze_os_log::OSLogBufferItem;
+using clang::analyze_os_log::OSLogBufferLayout;
+
+class OSLogFormatStringHandler
+    : public analyze_format_string::FormatStringHandler {
+private:
+  struct ArgData {
+    const Expr *E = nullptr;
+    Optional<OSLogBufferItem::Kind> Kind;
+    Optional<unsigned> Size;
+    Optional<const Expr *> Count;
+    Optional<const Expr *> Precision;
+    Optional<const Expr *> FieldWidth;
+    unsigned char Flags = 0;
+  };
+  SmallVector<ArgData, 4> ArgsData;
+  ArrayRef<const Expr *> Args;
+
+  OSLogBufferItem::Kind
+  getKind(analyze_format_string::ConversionSpecifier::Kind K) {
+    switch (K) {
+    case clang::analyze_format_string::ConversionSpecifier::sArg: // "%s"
+      return OSLogBufferItem::StringKind;
+    case clang::analyze_format_string::ConversionSpecifier::SArg: // "%S"
+      return OSLogBufferItem::WideStringKind;
+    case clang::analyze_format_string::ConversionSpecifier::PArg: { // "%P"
+      return OSLogBufferItem::PointerKind;
+    case clang::analyze_format_string::ConversionSpecifier::ObjCObjArg: // "%@"
+      return OSLogBufferItem::ObjCObjKind;
+    case clang::analyze_format_string::ConversionSpecifier::PrintErrno: // "%m"
+      return OSLogBufferItem::ErrnoKind;
+    default:
+      return OSLogBufferItem::ScalarKind;
+    }
+    }
+  }
+
+public:
+  OSLogFormatStringHandler(ArrayRef<const Expr *> Args) : Args(Args) {
+    ArgsData.reserve(Args.size());
+  }
+
+  virtual bool HandlePrintfSpecifier(const analyze_printf::PrintfSpecifier &FS,
+                                     const char *StartSpecifier,
+                                     unsigned SpecifierLen) {
+    if (!FS.consumesDataArgument() &&
+        FS.getConversionSpecifier().getKind() !=
+            clang::analyze_format_string::ConversionSpecifier::PrintErrno)
+      return true;
+
+    ArgsData.emplace_back();
+    unsigned ArgIndex = FS.getArgIndex();
+    if (ArgIndex < Args.size())
+      ArgsData.back().E = Args[ArgIndex];
+
+    // First get the Kind
+    ArgsData.back().Kind = getKind(FS.getConversionSpecifier().getKind());
+    if (ArgsData.back().Kind != OSLogBufferItem::ErrnoKind &&
+        !ArgsData.back().E) {
+      // missing argument
+      ArgsData.pop_back();
+      return false;
+    }
+
+    switch (FS.getConversionSpecifier().getKind()) {
+    case clang::analyze_format_string::ConversionSpecifier::sArg:   // "%s"
+    case clang::analyze_format_string::ConversionSpecifier::SArg: { // "%S"
+      auto &precision = FS.getPrecision();
+      switch (precision.getHowSpecified()) {
+      case clang::analyze_format_string::OptionalAmount::NotSpecified: // "%s"
+        break;
+      case clang::analyze_format_string::OptionalAmount::Constant: // "%.16s"
+        ArgsData.back().Size = precision.getConstantAmount();
+        break;
+      case clang::analyze_format_string::OptionalAmount::Arg: // "%.*s"
+        ArgsData.back().Count = Args[precision.getArgIndex()];
+        break;
+      case clang::analyze_format_string::OptionalAmount::Invalid:
+        return false;
+      }
+      break;
+    }
+    case clang::analyze_format_string::ConversionSpecifier::PArg: { // "%P"
+      auto &precision = FS.getPrecision();
+      switch (precision.getHowSpecified()) {
+      case clang::analyze_format_string::OptionalAmount::NotSpecified: // "%P"
+        return false; // length must be supplied with pointer format specifier
+      case clang::analyze_format_string::OptionalAmount::Constant: // "%.16P"
+        ArgsData.back().Size = precision.getConstantAmount();
+        break;
+      case clang::analyze_format_string::OptionalAmount::Arg: // "%.*P"
+        ArgsData.back().Count = Args[precision.getArgIndex()];
+        break;
+      case clang::analyze_format_string::OptionalAmount::Invalid:
+        return false;
+      }
+      break;
+    }
+    default:
+      if (FS.getPrecision().hasDataArgument()) {
+        ArgsData.back().Precision = Args[FS.getPrecision().getArgIndex()];
+      }
+      break;
+    }
+    if (FS.getFieldWidth().hasDataArgument()) {
+      ArgsData.back().FieldWidth = Args[FS.getFieldWidth().getArgIndex()];
+    }
+
+    if (FS.isPrivate()) {
+      ArgsData.back().Flags |= OSLogBufferItem::IsPrivate;
+    }
+    if (FS.isPublic()) {
+      ArgsData.back().Flags |= OSLogBufferItem::IsPublic;
+    }
+    return true;
+  }
+
+  void computeLayout(ASTContext &Ctx, OSLogBufferLayout &Layout) const {
+    Layout.Items.clear();
+    for (auto &Data : ArgsData) {
+      if (Data.FieldWidth) {
+        CharUnits Size = Ctx.getTypeSizeInChars((*Data.FieldWidth)->getType());
+        Layout.Items.emplace_back(OSLogBufferItem::ScalarKind, *Data.FieldWidth,
+                                  Size, 0);
+      }
+      if (Data.Precision) {
+        CharUnits Size = Ctx.getTypeSizeInChars((*Data.Precision)->getType());
+        Layout.Items.emplace_back(OSLogBufferItem::ScalarKind, *Data.Precision,
+                                  Size, 0);
+      }
+      if (Data.Count) {
+        // "%.*P" has an extra "count" that we insert before the argument.
+        CharUnits Size = Ctx.getTypeSizeInChars((*Data.Count)->getType());
+        Layout.Items.emplace_back(OSLogBufferItem::CountKind, *Data.Count, Size,
+                                  0);
+      }
+      if (Data.Size)
+        Layout.Items.emplace_back(Ctx, CharUnits::fromQuantity(*Data.Size),
+                                  Data.Flags);
+      if (Data.Kind) {
+        CharUnits Size;
+        if (*Data.Kind == OSLogBufferItem::ErrnoKind)
+          Size = CharUnits::Zero();
+        else
+          Size = Ctx.getTypeSizeInChars(Data.E->getType());
+        Layout.Items.emplace_back(*Data.Kind, Data.E, Size, Data.Flags);
+      } else {
+        auto Size = Ctx.getTypeSizeInChars(Data.E->getType());
+        Layout.Items.emplace_back(OSLogBufferItem::ScalarKind, Data.E, Size,
+                                  Data.Flags);
+      }
+    }
+  }
+};
+
+bool clang::analyze_os_log::computeOSLogBufferLayout(
+    ASTContext &Ctx, const CallExpr *E, OSLogBufferLayout &Layout) {
+  ArrayRef<const Expr *> Args(E->getArgs(), E->getArgs() + E->getNumArgs());
+
+  const Expr *StringArg;
+  ArrayRef<const Expr *> VarArgs;
+  switch (E->getBuiltinCallee()) {
+  case Builtin::BI__builtin_os_log_format_buffer_size:
+    assert(E->getNumArgs() >= 1 &&
+           "__builtin_os_log_format_buffer_size takes at least 1 argument");
+    StringArg = E->getArg(0);
+    VarArgs = Args.slice(1);
+    break;
+  case Builtin::BI__builtin_os_log_format:
+    assert(E->getNumArgs() >= 2 &&
+           "__builtin_os_log_format takes at least 2 arguments");
+    StringArg = E->getArg(1);
+    VarArgs = Args.slice(2);
+    break;
+  default:
+    llvm_unreachable("non-os_log builtin passed to computeOSLogBufferLayout");
+  }
+
+  const StringLiteral *Lit = cast<StringLiteral>(StringArg->IgnoreParenCasts());
+  assert(Lit && (Lit->isAscii() || Lit->isUTF8()));
+  StringRef Data = Lit->getString();
+  OSLogFormatStringHandler H(VarArgs);
+  ParsePrintfString(H, Data.begin(), Data.end(), Ctx.getLangOpts(),
+                    Ctx.getTargetInfo(), /*isFreeBSDKPrintf*/ false);
+
+  H.computeLayout(Ctx, Layout);
+  return true;
+}
diff --git a/lib/Analysis/PrintfFormatString.cpp b/lib/Analysis/PrintfFormatString.cpp
index ac6cef9d08420..ed7193ecb4379 100644
--- a/lib/Analysis/PrintfFormatString.cpp
+++ b/lib/Analysis/PrintfFormatString.cpp
@@ -119,6 +119,39 @@ static PrintfSpecifierResult ParsePrintfSpecifier(FormatStringHandler &H,
     return true;
   }
 
+  const char *OSLogVisibilityFlagsStart = nullptr,
+             *OSLogVisibilityFlagsEnd = nullptr;
+  if (*I == '{') {
+    OSLogVisibilityFlagsStart = I++;
+    // Find the end of the modifier.
+    while (I != E && *I != '}') {
+      I++;
+    }
+    if (I == E) {
+      if (Warn)
+        H.HandleIncompleteSpecifier(Start, E - Start);
+      return true;
+    }
+    assert(*I == '}');
+    OSLogVisibilityFlagsEnd = I++;
+
+    // Just see if 'private' or 'public' is the first word. os_log itself will
+    // do any further parsing.
+    const char *P = OSLogVisibilityFlagsStart + 1;
+    while (P < OSLogVisibilityFlagsEnd && isspace(*P))
+      P++;
+    const char *WordStart = P;
+    while (P < OSLogVisibilityFlagsEnd && (isalnum(*P) || *P == '_'))
+      P++;
+    const char *WordEnd = P;
+    StringRef Word(WordStart, WordEnd - WordStart);
+    if (Word == "private") {
+      FS.setIsPrivate(WordStart);
+    } else if (Word == "public") {
+      FS.setIsPublic(WordStart);
+    }
+  }
+
   // Look for flags (if any).
   bool hasMore = true;
   for ( ; I != E; ++I) {
@@ -253,6 +286,10 @@ static PrintfSpecifierResult ParsePrintfSpecifier(FormatStringHandler &H,
     // POSIX specific.
     case 'C': k = ConversionSpecifier::CArg; break;
     case 'S': k = ConversionSpecifier::SArg; break;
+    // Apple extension for os_log
+    case 'P':
+      k = ConversionSpecifier::PArg;
+      break;
     // Objective-C.
     case '@': k = ConversionSpecifier::ObjCObjArg; break;
     // Glibc specific.
@@ -301,7 +338,7 @@ static PrintfSpecifierResult ParsePrintfSpecifier(FormatStringHandler &H,
                                            conversionPosition);
     return true;
   }
-  
+
   PrintfConversionSpecifier CS(conversionPosition, k);
   FS.setConversionSpecifier(CS);
   if (CS.consumesDataArgument() && !FS.usesPositionalArg())
@@ -541,6 +578,7 @@ ArgType PrintfSpecifier::getArgType(ASTContext &Ctx,
         return Ctx.IntTy;
       return ArgType(Ctx.WideCharTy, "wchar_t");
     case ConversionSpecifier::pArg:
+    case ConversionSpecifier::PArg:
       return ArgType::CPointerTy;
     case ConversionSpecifier::ObjCObjArg:
       return ArgType::ObjCPointerTy;
@@ -900,7 +938,7 @@ bool PrintfSpecifier::hasValidPrecision() const {
   if (Precision.getHowSpecified() == OptionalAmount::NotSpecified)
     return true;
 
-  // Precision is only valid with the diouxXaAeEfFgGs conversions
+  // Precision is only valid with the diouxXaAeEfFgGsP conversions
   switch (CS.getKind()) {
   case ConversionSpecifier::dArg:
   case ConversionSpecifier::DArg:
@@ -922,6 +960,7 @@ bool PrintfSpecifier::hasValidPrecision() const {
   case ConversionSpecifier::sArg:
   case ConversionSpecifier::FreeBSDrArg:
   case ConversionSpecifier::FreeBSDyArg:
+  case ConversionSpecifier::PArg:
     return true;
 
   default:
diff --git a/lib/Analysis/ReachableCode.cpp b/lib/Analysis/ReachableCode.cpp
index 8165b09f40800..69d000c03bac1 100644
--- a/lib/Analysis/ReachableCode.cpp
+++ b/lib/Analysis/ReachableCode.cpp
@@ -164,6 +164,8 @@ static bool isConfigurationValue(const Stmt *S,
   if (!S)
     return false;
 
+  S = S->IgnoreImplicit();
+
   if (const Expr *Ex = dyn_cast<Expr>(S))
     S = Ex->IgnoreCasts();
 
diff --git a/lib/Analysis/ScanfFormatString.cpp b/lib/Analysis/ScanfFormatString.cpp
index 82b038864c23f..3b93f1a57f1ff 100644
--- a/lib/Analysis/ScanfFormatString.cpp
+++ b/lib/Analysis/ScanfFormatString.cpp
@@ -418,8 +418,12 @@ bool ScanfSpecifier::fixType(QualType QT, QualType RawQT,
   QualType PT = QT->getPointeeType();
 
   // If it's an enum, get its underlying type.
-  if (const EnumType *ETy = PT->getAs<EnumType>())
+  if (const EnumType *ETy = PT->getAs<EnumType>()) {
+    // Don't try to fix incomplete enums.
+    if (!ETy->getDecl()->isComplete())
+      return false;
     PT = ETy->getDecl()->getIntegerType();
+  }
 
   const BuiltinType *BT = PT->getAs<BuiltinType>();
   if (!BT)
diff --git a/lib/Analysis/ThreadSafety.cpp b/lib/Analysis/ThreadSafety.cpp
index b282a5bbd8d8c..879a15c9c2a8e 100644
--- a/lib/Analysis/ThreadSafety.cpp
+++ b/lib/Analysis/ThreadSafety.cpp
@@ -15,13 +15,13 @@
 //
 //===----------------------------------------------------------------------===//
 
+#include "clang/Analysis/Analyses/ThreadSafety.h"
 #include "clang/AST/Attr.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/StmtCXX.h"
 #include "clang/AST/StmtVisitor.h"
 #include "clang/Analysis/Analyses/PostOrderCFGView.h"
-#include "clang/Analysis/Analyses/ThreadSafety.h"
 #include "clang/Analysis/Analyses/ThreadSafetyCommon.h"
 #include "clang/Analysis/Analyses/ThreadSafetyLogical.h"
 #include "clang/Analysis/Analyses/ThreadSafetyTIL.h"
@@ -32,8 +32,6 @@
 #include "clang/Basic/OperatorKinds.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
-#include "llvm/ADT/BitVector.h"
-#include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/ImmutableMap.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SmallVector.h"
@@ -259,7 +257,7 @@ private:
 
   struct BeforeInfo {
     BeforeInfo() : Visited(0) {}
-    BeforeInfo(BeforeInfo &&O) : Vect(std::move(O.Vect)), Visited(O.Visited) {}
+    BeforeInfo(BeforeInfo &&) = default;
 
     BeforeVect Vect;
     int Visited;
@@ -1585,7 +1583,7 @@ void BuildLockset::warnIfMutexHeld(const NamedDecl *D, const Expr *Exp,
 /// a pointer marked with pt_guarded_by.
 void BuildLockset::checkAccess(const Expr *Exp, AccessKind AK,
                                ProtectedOperationKind POK) {
-  Exp = Exp->IgnoreParenCasts();
+  Exp = Exp->IgnoreImplicit()->IgnoreParenCasts();
 
   SourceLocation Loc = Exp->getExprLoc();
 
diff --git a/lib/Analysis/ThreadSafetyCommon.cpp b/lib/Analysis/ThreadSafetyCommon.cpp
index ffe95ea22a425..cbd5464c34d7c 100644
--- a/lib/Analysis/ThreadSafetyCommon.cpp
+++ b/lib/Analysis/ThreadSafetyCommon.cpp
@@ -17,20 +17,14 @@
 #include "clang/AST/DeclObjC.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/StmtCXX.h"
-#include "clang/Analysis/Analyses/PostOrderCFGView.h"
 #include "clang/Analysis/Analyses/ThreadSafetyTIL.h"
 #include "clang/Analysis/Analyses/ThreadSafetyTraverse.h"
 #include "clang/Analysis/AnalysisContext.h"
 #include "clang/Analysis/CFG.h"
 #include "clang/Basic/OperatorKinds.h"
 #include "clang/Basic/SourceLocation.h"
-#include "clang/Basic/SourceManager.h"
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include <algorithm>
-#include <climits>
-#include <vector>
 
 using namespace clang;
 using namespace threadSafety;
@@ -239,6 +233,9 @@ til::SExpr *SExprBuilder::translate(const Stmt *S, CallingContext *Ctx) {
     return translate(cast<ExprWithCleanups>(S)->getSubExpr(), Ctx);
   case Stmt::CXXBindTemporaryExprClass:
     return translate(cast<CXXBindTemporaryExpr>(S)->getSubExpr(), Ctx);
+  case Stmt::MaterializeTemporaryExprClass:
+    return translate(cast<MaterializeTemporaryExpr>(S)->GetTemporaryExpr(),
+                     Ctx);
 
   // Collect all literals
   case Stmt::CharacterLiteralClass:
diff --git a/lib/Analysis/UninitializedValues.cpp b/lib/Analysis/UninitializedValues.cpp
index f2f791957aa32..d5289fb9d4271 100644
--- a/lib/Analysis/UninitializedValues.cpp
+++ b/lib/Analysis/UninitializedValues.cpp
@@ -348,7 +348,8 @@ public:
 }
 
 static const DeclRefExpr *getSelfInitExpr(VarDecl *VD) {
-  if (VD->getType()->isRecordType()) return nullptr;
+  if (VD->getType()->isRecordType())
+    return nullptr;
   if (Expr *Init = VD->getInit()) {
     const DeclRefExpr *DRE
       = dyn_cast<DeclRefExpr>(stripCasts(VD->getASTContext(), Init));