[analyzer] Performance optimizations for the CloneChecker

[teemperor]

Summary

This patch aims at optimizing the CloneChecker for larger programs. Before this patch we took around 102 seconds to analyze sqlite3 with a complexity value of 50. After this patch we now take 2.1 seconds to analyze sqlite3.

The biggest performance optimization is that we now put the constraint for group size before the constraint for the complexity. The group size constraint is much faster in comparison to the complexity constraint as it only does a simple integer comparison. The complexity constraint on the other hand actually traverses each Stmt and even checks the macro stack, so it is obviously not able to handle larger amounts of incoming clones. The new order filters out all the single-clone groups that the type II constraint generates in a faster way before passing the fewer remaining clones to the complexity constraint. This reduced runtime by around 95%.

The other change is that we also delay the verification part of the type II clones back in the chain of constraints. This required to split up the constraint into two parts - a verification and a hash constraint (which is also making it more similar to the original design of the clone detection algorithm). The reasoning for this is the same as before: The verification constraint has to traverse many statements and shouldn't be at the start of the constraint chain. However, as the type II hashing has to be the first step in our algorithm, we have no other choice but split this constrain into two different ones. Now our group size and complexity constrains filter out a chunk of the clones before they reach the slow verification step, which reduces the runtime by around 8%.

I also kept the full type II constraint around - that now just calls it's two sub-constraints - in case someone doesn't care about the performance benefits of doing this.

[v.g.vassilev]

include/clang/Analysis/CloneDetection.h

263 ↗

(On Diff #102442)

Could we typedef std::vector<CloneDetector::CloneGroup> into CloneDetector::CloneGroups?

[teemperor]

include/clang/Analysis/CloneDetection.h

263 ↗

(On Diff #102442)

Yes, I'll do this in another patch for the whole CloneDetector code base.

[teemperor]

• made saveHash static.

[NoQ]

Totally makes sense :)

include/clang/Analysis/CloneDetection.h

258–260 ↗

(On Diff #102700)

Since this constraint is a trivial composition of the other two now, is it useful at all as a separate class? Maybe just remove it?

266–273 ↗

(On Diff #102700)

As a personal preference, i'd probably like to see a more straightforward answer to "what exactly does this do?", rather than "what is this part of?" and "how fast this is?".

Eg., "RecursiveCloneTypeIIHashConstraint computes a hash of each statement sequence; sequences with different hash values are moved into separate clone groups. Collisions are possible, and this constraint does nothing to address this them. Add the slower RecursiveCloneTypeIIVerifyConstraint later in the constraint chain, not necessarily immediately, to eliminate hash collisions through a more detailed analysis."

[teemperor]

• Updated according to Artem's comments.

[teemperor]

(Fixed diff)

cfe/trunk/include/clang/Analysis/CloneDetection.h

public:
   /// \param Compare The comparison function that all clones are supposed to
   ///                pass. Should return true if and only if two clones belong
   ///                to the same CloneGroup.
   static void splitCloneGroups(
       std::vector<CloneDetector::CloneGroup> &CloneGroups,
       std::function<bool(const StmtSequence &, const StmtSequence &)> Compare);
 };
 
-/// Searches all children of the given clones for type II clones (i.e. they are
-/// identical in every aspect beside the used variable names).
-class RecursiveCloneTypeIIConstraint {
-
-  /// Generates and saves a hash code for the given Stmt.
-  /// \param S The given Stmt.
-  /// \param D The Decl containing S.
-  /// \param StmtsByHash Output parameter that will contain the hash codes for
-  ///                    each StmtSequence in the given Stmt.
-  /// \return The hash code of the given Stmt.
-  ///
-  /// If the given Stmt is a CompoundStmt, this method will also generate
-  /// hashes for all possible StmtSequences in the children of this Stmt.
-  size_t saveHash(const Stmt *S, const Decl *D,
-                  std::vector<std::pair<size_t, StmtSequence>> &StmtsByHash);
+/// This constraint moves clones into clone groups of type II via hashing.
+///
+/// Clones with different hash values are moved into separate clone groups.
+/// Collisions are possible, and this constraint does nothing to address this
+/// them. Add the slower RecursiveCloneTypeIIVerifyConstraint later in the
+/// constraint chain, not necessarily immediately, to eliminate hash collisions
+/// through a more detailed analysis.
+class RecursiveCloneTypeIIHashConstraint {
+public:
+  void constrain(std::vector<CloneDetector::CloneGroup> &Sequences);
+};
 
+/// This constraint moves clones into clone groups of type II by comparing them.
+///
+/// Clones that aren't type II clones are moved into separate clone groups.
+/// In contrast to the RecursiveCloneTypeIIHashConstraint, all clones in a clone
+/// group are guaranteed to be be type II clones of each other, but it is too
+/// slow to efficiently handle large amounts of clones.
+class RecursiveCloneTypeIIVerifyConstraint {
 public:
   void constrain(std::vector<CloneDetector::CloneGroup> &Sequences);
 };
 
 /// Ensures that every clone has at least the given complexity.
 ///
 /// Complexity is here defined as the total amount of children of a statement.
 /// This constraint assumes the first statement in the group is representative

cfe/trunk/lib/Analysis/CloneDetection.cpp

static size_t createHash(llvm::MD5 &Hash) {
   // 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)));
 
   return HashCode;
 }
 
-size_t RecursiveCloneTypeIIConstraint::saveHash(
-    const Stmt *S, const Decl *D,
+/// Generates and saves a hash code for the given Stmt.
+/// \param S The given Stmt.
+/// \param D The Decl containing S.
+/// \param StmtsByHash Output parameter that will contain the hash codes for
+///                    each StmtSequence in the given Stmt.
+/// \return The hash code of the given Stmt.
+///
+/// If the given Stmt is a CompoundStmt, this method will also generate
+/// hashes for all possible StmtSequences in the children of this Stmt.
+static size_t
+saveHash(const Stmt *S, const Decl *D,
          std::vector<std::pair<size_t, StmtSequence>> &StmtsByHash) {
   llvm::MD5 Hash;
   ASTContext &Context = D->getASTContext();
 
   CloneTypeIIStmtDataCollector<llvm::MD5>(S, Context, Hash);
 
   auto CS = dyn_cast<CompoundStmt>(S);
   SmallVector<size_t, 8> ChildHashes;
 
static bool areSequencesClones(const StmtSequence &LHS,
   FoldingSetNodeIDWrapper RHSWrapper(DataRHS);
 
   CollectStmtSequenceData(LHS, LHSWrapper);
   CollectStmtSequenceData(RHS, RHSWrapper);
 
   return DataLHS == DataRHS;
 }
 
-void RecursiveCloneTypeIIConstraint::constrain(
+void RecursiveCloneTypeIIHashConstraint::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;
 
   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())
for (unsigned i = 0; i < StmtsByHash.size() - 1; ++i) {
       // 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)) {
+        if (PrototypeHash != StmtsByHash[i].first) {
           // 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);
       }
 
       // 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 RecursiveCloneTypeIIVerifyConstraint::constrain(
+    std::vector<CloneDetector::CloneGroup> &Sequences) {
+  CloneConstraint::splitCloneGroups(
+      Sequences, [](const StmtSequence &A, const StmtSequence &B) {
+        return areSequencesClones(A, B);
+      });
+}
+
 size_t MinComplexityConstraint::calculateStmtComplexity(
     const StmtSequence &Seq, const std::string &ParentMacroStack) {
   if (Seq.empty())
     return 0;
 
   size_t Complexity = 1;
 
   ASTContext &Context = Seq.getASTContext();

cfe/trunk/lib/StaticAnalyzer/Checkers/CloneChecker.cpp

void CloneChecker::checkEndOfTranslationUnit(const TranslationUnitDecl *TU,
   StringRef IgnoredFilesPattern = Mgr.getAnalyzerOptions().getOptionAsString(
       "IgnoredFilesPattern", "", this);
 
   // Let the CloneDetector create a list of clones from all the analyzed
   // statements. We don't filter for matching variable patterns at this point
   // because reportSuspiciousClones() wants to search them for errors.
   std::vector<CloneDetector::CloneGroup> AllCloneGroups;
 
-  Detector.findClones(AllCloneGroups,
-                      FilenamePatternConstraint(IgnoredFilesPattern),
-                      RecursiveCloneTypeIIConstraint(),
-                      MinComplexityConstraint(MinComplexity),
-                      MinGroupSizeConstraint(2), OnlyLargestCloneConstraint());
+  Detector.findClones(
+      AllCloneGroups, FilenamePatternConstraint(IgnoredFilesPattern),
+      RecursiveCloneTypeIIHashConstraint(), MinGroupSizeConstraint(2),
+      RecursiveCloneTypeIIVerifyConstraint(), OnlyLargestCloneConstraint());
 
   if (ReportSuspiciousClones)
     reportSuspiciousClones(BR, Mgr, AllCloneGroups);
 
   // We are done for this translation unit unless we also need to report normal
   // clones.
   if (!ReportNormalClones)
     return;

cfe/trunk/unittests/Analysis/CloneDetectionTest.cpp

TEST(CloneDetector, FilterFunctionsByName) {
   // Push all the function bodies into the detector.
   CloneDetectionVisitor Visitor(Detector);
   Visitor.TraverseTranslationUnitDecl(TU);
 
   // Find clones with the usual settings, but but we want to filter out
   // all statements from functions which names start with "bar".
   std::vector<CloneDetector::CloneGroup> CloneGroups;
   Detector.findClones(CloneGroups, NoBarFunctionConstraint(),
-                      RecursiveCloneTypeIIConstraint(),
+                      RecursiveCloneTypeIIHashConstraint(),
                       MinComplexityConstraint(2), MinGroupSizeConstraint(2),
+                      RecursiveCloneTypeIIVerifyConstraint(),
                       OnlyLargestCloneConstraint());
 
   ASSERT_EQ(CloneGroups.size(), 1u);
   ASSERT_EQ(CloneGroups.front().size(), 2u);
 
   for (auto &Clone : CloneGroups.front()) {
     const auto ND = dyn_cast<const FunctionDecl>(Clone.getContainingDecl());
     ASSERT_TRUE(ND != nullptr);
     // Check that no function name starting with "bar" is in the results...
     ASSERT_TRUE(ND->getNameAsString().find("bar") != 0);
   }
 
   // Retry above's example without the filter...
   CloneGroups.clear();
 
-  Detector.findClones(CloneGroups, RecursiveCloneTypeIIConstraint(),
+  Detector.findClones(CloneGroups, RecursiveCloneTypeIIHashConstraint(),
                       MinComplexityConstraint(2), MinGroupSizeConstraint(2),
+                      RecursiveCloneTypeIIVerifyConstraint(),
                       OnlyLargestCloneConstraint());
   ASSERT_EQ(CloneGroups.size(), 1u);
   ASSERT_EQ(CloneGroups.front().size(), 4u);
 
   // Count how many functions with the bar prefix we have in the results.
   int FoundFunctionsWithBarPrefix = 0;
   for (auto &Clone : CloneGroups.front()) {
     const auto ND = dyn_cast<const FunctionDecl>(Clone.getContainingDecl());