Merge clang, llvm, lld, lldb, compiler-rt and libc++ 5.0.0 release.

MFC r309126 (by emaste):

  Correct lld llvm-tblgen dependency file name

MFC r309169:

  Get rid of separate Subversion mergeinfo properties for llvm-dwarfdump
  and llvm-lto.  The mergeinfo confuses Subversion enormously, and these
  directories will just use the mergeinfo for llvm itself.

MFC r312765:

  Pull in r276136 from upstream llvm trunk (by Wei Mi):

    Use ValueOffsetPair to enhance value reuse during SCEV expansion.

    In D12090, the ExprValueMap was added to reuse existing value during
    SCEV expansion. However, const folding and sext/zext distribution can
    make the reuse still difficult.

    A simplified case is: suppose we know S1 expands to V1 in
    ExprValueMap, and
      S1 = S2 + C_a
      S3 = S2 + C_b
    where C_a and C_b are different SCEVConstants. Then we'd like to
    expand S3 as V1 - C_a + C_b instead of expanding S2 literally. It is
    helpful when S2 is a complex SCEV expr and S2 has no entry in
    ExprValueMap, which is usually caused by the fact that S3 is
    generated from S1 after const folding.

    In order to do that, we represent ExprValueMap as a mapping from SCEV
    to ValueOffsetPair. We will save both S1->{V1, 0} and S2->{V1, C_a}
    into the ExprValueMap when we create SCEV for V1. When S3 is
    expanded, it will first expand S2 to V1 - C_a because of S2->{V1,
    C_a} in the map, then expand S3 to V1 - C_a + C_b.

    Differential Revision: https://reviews.llvm.org/D21313

  This should fix assertion failures when building OpenCV >= 3.1.

  PR:		215649

MFC r312831:

  Revert r312765 for now, since it causes assertions when building
  lang/spidermonkey24.

  Reported by:	antoine
  PR:		215649

MFC r316511 (by jhb):

  Add an implementation of __ffssi2() derived from __ffsdi2().

  Newer versions of GCC include an __ffssi2() symbol in libgcc and the
  compiler can emit calls to it in generated code.  This is true for at
  least GCC 6.2 when compiling world for mips and mips64.

  Reviewed by:	jmallett, dim
  Sponsored by:	DARPA / AFRL
  Differential Revision:	https://reviews.freebsd.org/D10086

MFC r318601 (by adrian):

  [libcompiler-rt] add bswapdi2/bswapsi2

  This is required for mips gcc 6.3 userland to build/run.

  Reviewed by:	emaste, dim
  Approved by:	emaste
  Differential Revision:	https://reviews.freebsd.org/D10838

MFC r318884 (by emaste):

  lldb: map TRAP_CAP to a trace trap

  In the absense of a more specific handler for TRAP_CAP (generated by
  ENOTCAPABLE or ECAPMODE while in capability mode) treat it as a trace
  trap.

  Example usage (testing the bug in PR219173):

  % proccontrol -m trapcap lldb usr.bin/hexdump/obj/hexdump -- -Cv -s 1 /bin/ls
  ...
  (lldb) run
  Process 12980 launching
  Process 12980 launched: '.../usr.bin/hexdump/obj/hexdump' (x86_64)
  Process 12980 stopped
  * thread #1, stop reason = trace
      frame #0: 0x0000004b80c65f1a libc.so.7`__sys_lseek + 10
  ...

  In the future we should have LLDB control the trapcap procctl itself
  (as it does with ASLR), as well as report a specific stop reason.
  This change eliminates an assertion failure from LLDB for now.

MFC r319796:

  Remove a few unneeded files from libllvm, libclang and liblldb.

MFC r319885 (by emaste):

  lld: ELF: Fix ICF crash on absolute symbol relocations.

  If two sections contained relocations to absolute symbols with the same
  value we would crash when trying to access their sections. Add a check that
  both symbols point to sections before accessing their sections, and treat
  absolute symbols as equal if their values are equal.

  Obtained from:	LLD commit r292578

MFC r319918:

  Revert r319796 for now, it can cause undefined references when linking
  in some circumstances.

  Reported by:	Shawn Webb <shawn.webb@hardenedbsd.org>

MFC r319957 (by emaste):

  lld: Add armelf emulation mode

  Obtained from:	LLD r305375

MFC r321369:

  Upgrade our copies of clang, llvm, lld, lldb, compiler-rt and libc++ to
  5.0.0 (trunk r308421).  Upstream has branched for the 5.0.0 release,
  which should be in about a month.  Please report bugs and regressions,
  so we can get them into the release.

  Please note that from 3.5.0 onwards, clang, llvm and lldb require C++11
  support to build; see UPDATING for more information.

MFC r321420:

  Add a few more object files to liblldb, which should solve errors when
  linking the lldb executable in some cases.  In particular, when the
  -ffunction-sections -fdata-sections options are turned off, or
  ineffective.

  Reported by:	Shawn Webb, Mark Millard

MFC r321433:

  Cleanup stale Options.inc files from the previous libllvm build for
  clang 4.0.0.  Otherwise, these can get included before the two newly
  generated ones (which are different) for clang 5.0.0.

  Reported by:	Mark Millard

MFC r321439 (by bdrewery):

  Move llvm Options.inc hack from r321433 for NO_CLEAN to lib/clang/libllvm.

  The files are only ever generated to .OBJDIR, not to WORLDTMP (as a
  sysroot) and are only ever included from a compilation.  So using
  a beforebuild target here removes the file before the compilation
  tries to include it.

MFC r321664:

  Pull in r308891 from upstream llvm trunk (by Benjamin Kramer):

    [CodeGenPrepare] Cut off FindAllMemoryUses if there are too many uses.

    This avoids excessive compile time. The case I'm looking at is
    Function.cpp from an old version of LLVM that still had the giant
    memcmp string matcher in it. Before r308322 this compiled in about 2
    minutes, after it, clang takes infinite* time to compile it. With
    this patch we're at 5 min, which is still bad but this is a
    pathological case.

    The cut off at 20 uses was chosen by looking at other cut-offs in LLVM
    for user scanning. It's probably too high, but does the job and is
    very unlikely to regress anything.

    Fixes PR33900.

    * I'm impatient and aborted after 15 minutes, on the bug report it was
      killed after 2h.

  Pull in r308986 from upstream llvm trunk (by Simon Pilgrim):

    [X86][CGP] Reduce memcmp() expansion to 2 load pairs (PR33914)

    D35067/rL308322 attempted to support up to 4 load pairs for memcmp
    inlining which resulted in regressions for some optimized libc memcmp
    implementations (PR33914).

    Until we can match these more optimal cases, this patch reduces the
    memcmp expansion to a maximum of 2 load pairs (which matches what we
    do for -Os).

    This patch should be considered for the 5.0.0 release branch as well

    Differential Revision: https://reviews.llvm.org/D35830

  These fix a hang (or extremely long compile time) when building older
  LLVM ports.

  Reported by:    antoine
  PR:             219139

MFC r321719:

  Pull in r309503 from upstream clang trunk (by Richard Smith):

    PR33902: Invalidate line number cache when adding more text to
    existing buffer.

    This led to crashes as the line number cache would report a bogus
    line number for a line of code, and we'd try to find a nonexistent
    column within the line when printing diagnostics.

  This fixes an assertion when building the graphics/champlain port.

  Reported by:	antoine, kwm
  PR:		219139

MFC r321723:

  Upgrade our copies of clang, llvm, lld and lldb to r309439 from the
  upstream release_50 branch.  This is just after upstream's 5.0.0-rc1.

MFC r322320:

  Upgrade our copies of clang, llvm and libc++ to r310316 from the
  upstream release_50 branch.

MFC r322326 (by emaste):

  lldb: Make i386-*-freebsd expression work on JIT path

  * Enable i386 ABI creation for freebsd
  * Added an extra argument in ABISysV_i386::PrepareTrivialCall for mmap
    syscall
  * Unlike linux, the last argument of mmap is actually 64-bit(off_t).
    This requires us to push an additional word for the higher order bits.
  * Prior to this change, ktrace dump will show mmap failures due to
    invalid argument coming from the 6th mmap argument.

  Submitted by:	Karnajit Wangkhem
  Differential Revision:	https://reviews.llvm.org/D34776

MFC r322360 (by emaste):

  lldb: Report inferior signals as signals, not exceptions, on FreeBSD

  This is the FreeBSD equivalent of LLVM r238549.

  This serves 2 purposes:

  * LLDB should handle inferior process signals SIGSEGV/SIGILL/SIGBUS/
    SIGFPE the way it is suppose to be handled. Prior to this fix these
    signals will neither create a coredump, nor exit from the debugger
    or work for signal handling scenario.
  * eInvalidCrashReason need not report "unknown crash reason" if we have
    a valid si_signo

  llvm.org/pr23699

  Patch by Karnajit Wangkhem

  Differential Revision:  https://reviews.llvm.org/D35223

  Submitted by:	Karnajit Wangkhem
  Obtained from:	LLVM r310591

MFC r322474 (by emaste):

  lld: Add `-z muldefs` option.

  Obtained from:	LLVM r310757

MFC r322740:

  Upgrade our copies of clang, llvm, lld and libc++ to r311219 from the
  upstream release_50 branch.

MFC r322855:

  Upgrade our copies of clang, llvm, lldb and compiler-rt to r311606 from
  the upstream release_50 branch.

  As of this version, lib/msun's trig test should also work correctly
  again (see bug 220989 for more information).

  PR:		220989

MFC r323112:

  Upgrade our copies of clang, llvm, lldb and compiler-rt to r312293 from
  the upstream release_50 branch.  This corresponds to 5.0.0 rc4.

  As of this version, the cad/stepcode port should now compile in a more
  reasonable time on i386 (see bug 221836 for more information).

  PR:		221836

MFC r323245:

  Upgrade our copies of clang, llvm, lld, lldb, compiler-rt and libc++ to
  5.0.0 release (upstream r312559).

  Release notes for llvm, clang and lld will be available here soon:
  <http://releases.llvm.org/5.0.0/docs/ReleaseNotes.html>
  <http://releases.llvm.org/5.0.0/tools/clang/docs/ReleaseNotes.html>
  <http://releases.llvm.org/5.0.0/tools/lld/docs/ReleaseNotes.html>

  Relnotes:	yes

(cherry picked from commit 12cd91cf4c6b96a24427c0de5374916f2808d263)

1 files changed, 386 insertions, 692 deletions

diff --git a/contrib/llvm/tools/clang/lib/Analysis/CloneDetection.cpp b/contrib/llvm/tools/clang/lib/Analysis/CloneDetection.cpp
index e761738..5ea7498 100644
--- a/contrib/llvm/tools/clang/lib/Analysis/CloneDetection.cpp
+++ b/contrib/llvm/tools/clang/lib/Analysis/CloneDetection.cpp
@@ -16,35 +16,35 @@
 #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"
+#include "llvm/Support/Path.h"
 
 using namespace clang;
+using namespace clang::clone_detection;
 
-StmtSequence::StmtSequence(const CompoundStmt *Stmt, ASTContext &Context,
+StmtSequence::StmtSequence(const CompoundStmt *Stmt, const Decl *D,
                            unsigned StartIndex, unsigned EndIndex)
-    : S(Stmt), Context(&Context), StartIndex(StartIndex), EndIndex(EndIndex) {
+    : S(Stmt), D(D), 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(const Stmt *Stmt, const Decl *D)
+    : S(Stmt), D(D), StartIndex(0), EndIndex(0) {}
 
 StmtSequence::StmtSequence()
-    : S(nullptr), Context(nullptr), StartIndex(0), EndIndex(0) {}
+    : S(nullptr), D(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)
+  // If both sequences reside in different declarations, they can never contain
+  // each other.
+  if (D != Other.D)
     return false;
 
-  const SourceManager &SM = Context->getSourceManager();
+  const SourceManager &SM = getASTContext().getSourceManager();
 
   // Otherwise check if the start and end locations of the current sequence
   // surround the other sequence.
@@ -76,6 +76,11 @@ StmtSequence::iterator StmtSequence::end() const {
   return CS->body_begin() + EndIndex;
 }
 
+ASTContext &StmtSequence::getASTContext() const {
+  assert(D);
+  return D->getASTContext();
+}
+
 SourceLocation StmtSequence::getStartLoc() const {
   return front()->getLocStart();
 }
@@ -86,168 +91,8 @@ 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.
+/// 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(),
@@ -258,12 +103,8 @@ static void printMacroName(llvm::raw_string_ostream &MacroStack,
   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 clone_detection::getMacroStack(SourceLocation Loc,
+                                           ASTContext &Context) {
   std::string MacroStack;
   llvm::raw_string_ostream MacroStackStream(MacroStack);
   SourceManager &SM = Context.getSourceManager();
@@ -278,375 +119,159 @@ static std::string getMacroStack(SourceLocation Loc, ASTContext &Context) {
   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>> {
+void CloneDetector::analyzeCodeBody(const Decl *D) {
+  assert(D);
+  assert(D->hasBody());
 
-  ASTContext &Context;
-  /// \brief The data sink to which all data is forwarded.
-  T &DataConsumer;
+  Sequences.push_back(StmtSequence(D->getBody(), D));
+}
 
-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);
+/// Returns true if and only if \p Stmt contains at least one other
+/// sequence in the \p Group.
+static bool containsAnyInGroup(StmtSequence &Seq,
+                               CloneDetector::CloneGroup &Group) {
+  for (StmtSequence &GroupSeq : Group) {
+    if (Seq.contains(GroupSeq))
+      return true;
   }
+  return false;
+}
 
-  // Below are utility methods for appending different data to the vector.
+/// Returns true if and only if all sequences in \p OtherGroup are
+/// contained by a sequence in \p Group.
+static 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.size() < OtherGroup.size())
+    return false;
 
-  void addData(CloneDetector::DataPiece Integer) {
-    DataConsumer.update(
-        StringRef(reinterpret_cast<char *>(&Integer), sizeof(Integer)));
+  for (StmtSequence &Stmt : Group) {
+    if (!containsAnyInGroup(Stmt, OtherGroup))
+      return false;
   }
+  return true;
+}
 
-  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);                      \
-  }
+void OnlyLargestCloneConstraint::constrain(
+    std::vector<CloneDetector::CloneGroup> &Result) {
+  std::vector<unsigned> IndexesToRemove;
 
-  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();
+  // 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;
 
-        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());
+      if (containsGroup(Result[j], Result[i])) {
+        IndexesToRemove.push_back(i);
+        break;
       }
     }
-  })
-  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;
-    }
+  // 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);
+  }
+}
 
-    // 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);
+bool FilenamePatternConstraint::isAutoGenerated(const CloneDetector::CloneGroup &Group) {
+  std::string Error;
+  if (IgnoredFilesPattern.empty() || Group.empty() || 
+      !IgnoredFilesRegex->isValid(Error))
+    return false;
 
-    // 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;
+  for (const StmtSequence &S : Group) {
+    const SourceManager &SM = S.getASTContext().getSourceManager();
+    StringRef Filename = llvm::sys::path::filename(SM.getFilename(
+        S.getContainingDecl()->getLocation()));
+    if (IgnoredFilesRegex->match(Filename))
+      return true;
+  }
 
-      // 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);
+  return false;
+}
 
-      // 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)));
+static size_t createHash(llvm::MD5 &Hash) {
+  size_t HashCode;
 
-      // 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);
-    }
+  // Create the final hash code for the current Stmt.
+  llvm::MD5::MD5Result HashResult;
+  Hash.final(HashResult);
 
-    // 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);
+  // Copy as much as possible of the generated hash code to the Stmt's hash
+  // code.
+  std::memcpy(&HashCode, &HashResult,
+              std::min(sizeof(HashCode), sizeof(HashResult)));
 
-    // Create the final hash code for the current signature.
-    llvm::MD5::MD5Result HashResult;
-    Hash.final(HashResult);
+  return HashCode;
+}
+
+size_t RecursiveCloneTypeIIConstraint::saveHash(
+    const Stmt *S, const Decl *D,
+    std::vector<std::pair<size_t, StmtSequence>> &StmtsByHash) {
+  llvm::MD5 Hash;
+  ASTContext &Context = D->getASTContext();
 
-    // 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)));
+  StmtDataCollector<llvm::MD5>(S, Context, Hash);
 
-    // Save the signature for the current statement in the CloneDetector object.
-    CD.add(StmtSequence(S, Context), Signature);
+  auto CS = dyn_cast<CompoundStmt>(S);
+  SmallVector<size_t, 8> ChildHashes;
 
-    return Signature;
+  for (const Stmt *Child : S->children()) {
+    if (Child == nullptr) {
+      ChildHashes.push_back(0);
+      continue;
+    }
+    size_t ChildHash = saveHash(Child, D, StmtsByHash);
+    Hash.update(
+        StringRef(reinterpret_cast<char *>(&ChildHash), sizeof(ChildHash)));
+    ChildHashes.push_back(ChildHash);
   }
 
-  /// \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)));
+  if (CS) {
+    // If we're in a CompoundStmt, we hash all possible combinations of child
+    // statements to find clones in those subsequences.
+    // We first go through every possible starting position of a subsequence.
+    for (unsigned Pos = 0; Pos < CS->size(); ++Pos) {
+      // Then we try all possible lengths this subsequence could have and
+      // reuse the same hash object to make sure we only hash every child
+      // hash exactly once.
+      llvm::MD5 Hash;
+      for (unsigned Length = 1; Length <= CS->size() - Pos; ++Length) {
+        // Grab the current child hash and put it into our hash. We do
+        // -1 on the index because we start counting the length at 1.
+        size_t ChildHash = ChildHashes[Pos + Length - 1];
+        Hash.update(
+            StringRef(reinterpret_cast<char *>(&ChildHash), sizeof(ChildHash)));
+        // If we have at least two elements in our subsequence, we can start
+        // saving it.
+        if (Length > 1) {
+          llvm::MD5 SubHash = Hash;
+          StmtsByHash.push_back(std::make_pair(
+              createHash(SubHash), StmtSequence(CS, D, Pos, Pos + Length)));
         }
-
-        // 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));
+  size_t HashCode = createHash(Hash);
+  StmtsByHash.push_back(std::make_pair(HashCode, StmtSequence(S, D)));
+  return HashCode;
 }
 
 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.
+/// Wrapper around FoldingSetNodeID that it can be used as the template
+/// argument of the StmtDataCollector.
 class FoldingSetNodeIDWrapper {
 
   llvm::FoldingSetNodeID &FS;
@@ -658,8 +283,8 @@ public:
 };
 } // end anonymous namespace
 
-/// \brief Writes the relevant data from all statements and child statements
-///        in the given StmtSequence into the given FoldingSetNodeID.
+/// 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) {
@@ -670,13 +295,13 @@ static void CollectStmtSequenceData(const StmtSequence &Sequence,
       if (!Child)
         continue;
 
-      CollectStmtSequenceData(StmtSequence(Child, Sequence.getASTContext()),
+      CollectStmtSequenceData(StmtSequence(Child, Sequence.getContainingDecl()),
                               OutputData);
     }
   }
 }
 
-/// \brief Returns true if both sequences are clones of each other.
+/// 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
@@ -693,202 +318,271 @@ static bool areSequencesClones(const StmtSequence &LHS,
   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;
-      }
+void RecursiveCloneTypeIIConstraint::constrain(
+    std::vector<CloneDetector::CloneGroup> &Sequences) {
+  // FIXME: Maybe we can do this in-place and don't need this additional vector.
+  std::vector<CloneDetector::CloneGroup> Result;
 
-      // 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;
-      }
+  for (CloneDetector::CloneGroup &Group : Sequences) {
+    // We assume in the following code that the Group is non-empty, so we
+    // skip all empty groups.
+    if (Group.empty())
+      continue;
+
+    std::vector<std::pair<size_t, StmtSequence>> StmtsByHash;
 
-      // We didn't found a matching variable pattern, so we continue with the
-      // next sequence.
-      ++I;
+    // Generate hash codes for all children of S and save them in StmtsByHash.
+    for (const StmtSequence &S : Group) {
+      saveHash(S.front(), S.getContainingDecl(), StmtsByHash);
     }
 
-    // Add a valid clone group to the list of found clone groups.
-    if (!FilteredGroup.isValid())
-      continue;
+    // Sort hash_codes in StmtsByHash.
+    std::stable_sort(StmtsByHash.begin(), StmtsByHash.end(),
+                     [](std::pair<size_t, StmtSequence> LHS,
+                            std::pair<size_t, StmtSequence> RHS) {
+                       return LHS.first < RHS.first;
+                     });
+
+    // Check for each StmtSequence if its successor has the same hash value.
+    // We don't check the last StmtSequence as it has no successor.
+    // Note: The 'size - 1 ' in the condition is safe because we check for an
+    // empty Group vector at the beginning of this function.
+    for (unsigned i = 0; i < StmtsByHash.size() - 1; ++i) {
+      const auto Current = StmtsByHash[i];
+
+      // It's likely that we just found an sequence of StmtSequences that
+      // represent a CloneGroup, so we create a new group and start checking and
+      // adding the StmtSequences in this sequence.
+      CloneDetector::CloneGroup NewGroup;
+
+      size_t PrototypeHash = Current.first;
+
+      for (; i < StmtsByHash.size(); ++i) {
+        // A different hash value means we have reached the end of the sequence.
+        if (PrototypeHash != StmtsByHash[i].first ||
+            !areSequencesClones(StmtsByHash[i].second, Current.second)) {
+          // The current sequence 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 StmtSequence with itself in the 'if' above.
+          assert(i != 0);
+          --i;
+          break;
+        }
+        // Same hash value means we should add the StmtSequence to the current
+        // group.
+        NewGroup.push_back(StmtsByHash[i].second);
+      }
 
-    Result.push_back(FilteredGroup);
+      // We created a new clone group with matching hash codes and move it to
+      // the result vector.
+      Result.push_back(NewGroup);
+    }
   }
+  // Sequences is the output parameter, so we copy our result into it.
+  Sequences = Result;
 }
 
-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;
+size_t MinComplexityConstraint::calculateStmtComplexity(
+    const StmtSequence &Seq, const std::string &ParentMacroStack) {
+  if (Seq.empty())
+    return 0;
+
+  size_t Complexity = 1;
+
+  ASTContext &Context = Seq.getASTContext();
+
+  // Look up what macros expanded into the current statement.
+  std::string StartMacroStack = getMacroStack(Seq.getStartLoc(), Context);
+  std::string EndMacroStack = getMacroStack(Seq.getEndLoc(), 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)) {
+    Complexity = 0;
+  }
 
-  // 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;
+  // Iterate over the Stmts in the StmtSequence and add their complexity values
+  // to the current complexity value.
+  if (Seq.holdsSequence()) {
+    for (const Stmt *S : Seq) {
+      Complexity += calculateStmtComplexity(
+          StmtSequence(S, Seq.getContainingDecl()), StartMacroStack);
+    }
+  } else {
+    for (const Stmt *S : Seq.front()->children()) {
+      Complexity += calculateStmtComplexity(
+          StmtSequence(S, Seq.getContainingDecl()), StartMacroStack);
+    }
+  }
+  return Complexity;
+}
 
-    // 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;
-      }
+void MatchingVariablePatternConstraint::constrain(
+    std::vector<CloneDetector::CloneGroup> &CloneGroups) {
+  CloneConstraint::splitCloneGroups(
+      CloneGroups, [](const StmtSequence &A, const StmtSequence &B) {
+        VariablePattern PatternA(A);
+        VariablePattern PatternB(B);
+        return PatternA.countPatternDifferences(PatternB) == 0;
+      });
+}
 
-      // Skip CloneSignatures that won't pass the complexity requirement.
-      if (Signature.first.Complexity < MinGroupComplexity)
+void CloneConstraint::splitCloneGroups(
+    std::vector<CloneDetector::CloneGroup> &CloneGroups,
+    std::function<bool(const StmtSequence &, const StmtSequence &)> Compare) {
+  std::vector<CloneDetector::CloneGroup> Result;
+  for (auto &HashGroup : CloneGroups) {
+    // Contains all indexes in HashGroup that were already added to a
+    // CloneGroup.
+    std::vector<char> Indexes;
+    Indexes.resize(HashGroup.size());
+
+    for (unsigned i = 0; i < HashGroup.size(); ++i) {
+      // Skip indexes that are already part of a CloneGroup.
+      if (Indexes[i])
         continue;
 
-      Group.Sequences.push_back(Signature.second);
-    }
+      // Pick the first unhandled StmtSequence and consider it as the
+      // beginning
+      // of a new CloneGroup for now.
+      // We don't add i to Indexes because we never iterate back.
+      StmtSequence Prototype = HashGroup[i];
+      CloneDetector::CloneGroup PotentialGroup = {Prototype};
+      ++Indexes[i];
+
+      // Check all following StmtSequences for clones.
+      for (unsigned j = i + 1; j < HashGroup.size(); ++j) {
+        // Skip indexes that are already part of a CloneGroup.
+        if (Indexes[j])
+          continue;
+
+        // If a following StmtSequence belongs to our CloneGroup, we add it.
+        const StmtSequence &Candidate = HashGroup[j];
+
+        if (!Compare(Prototype, Candidate))
+          continue;
+
+        PotentialGroup.push_back(Candidate);
+        // Make sure we never visit this StmtSequence again.
+        ++Indexes[j];
+      }
 
-    // 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;
+      // Otherwise, add it to the result and continue searching for more
+      // groups.
+      Result.push_back(PotentialGroup);
+    }
 
-    CloneGroups.push_back(Group);
+    assert(std::all_of(Indexes.begin(), Indexes.end(),
+                       [](char c) { return c == 1; }));
   }
+  CloneGroups = Result;
+}
 
-  // Add every valid clone group that fulfills the complexity requirement.
-  for (const CloneGroup &Group : CloneGroups) {
-    createCloneGroups(Result, Group, CheckPatterns);
+void VariablePattern::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);
+}
 
-  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;
+void VariablePattern::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;
 
-      if (containsGroup(Result[j], Result[i])) {
-        IndexesToRemove.push_back(i);
-        break;
-      }
-    }
+  // 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);
   }
 
-  // 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);
+  // Recursively check all children of the given statement.
+  for (const Stmt *Child : S->children()) {
+    addVariables(Child);
   }
 }
 
-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;
-        }
-      }
-    }
+unsigned VariablePattern::countPatternDifferences(
+    const VariablePattern &Other,
+    VariablePattern::SuspiciousClonePair *FirstMismatch) {
+  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 =
+        VariablePattern::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 =
+        VariablePattern::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;
 }