[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

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

[teemperor]

include/clang/Analysis/CloneDetection.h

263

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

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

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)

include/clang/Analysis/CloneDetection.h

   ///                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).
+///
+/// This constraint is also available to be executed in two phases, see
+/// RecursiveCloneTypeIIHashConstraint and RecursiveCloneTypeIIVerifyConstraint
+/// for more.
 class RecursiveCloneTypeIIConstraint {
+public:
+  void constrain(std::vector<CloneDetector::CloneGroup> &Sequences);
+};
 
-  /// 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 performs only the hashing part of the
+/// RecursiveCloneTypeIIConstraint.
+///
+/// It is supposed to be fast and can be used at the front of the constraint
+/// chain. However, it has a tiny chance to generate false-positives where the
+/// clones in a clone group are not actually type II clones of each other.
+/// This happens only due to hash collisions and they can be removed by the
+/// RecursiveCloneTypeIIVerifyConstraint.
+class RecursiveCloneTypeIIHashConstraint {
+public:
+  void constrain(std::vector<CloneDetector::CloneGroup> &Sequences);
+};
 
+/// This constraint performs only the verification part of the
+/// RecursiveCloneTypeIIConstraint.
+///
+/// It is supposed to be used behind the RecursiveCloneTypeIIHashConstraint
+/// and verifies that all clones in a group are actually type II clones of
+/// each other. However, this constraint is quite slow, so if you have faster
+/// constraints that can handle false-positives generated by hash collisions,
+/// then prepend those constraints to this one for optimal performance.
+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

lib/Analysis/CloneDetection.cpp

   // 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,
-    std::vector<std::pair<size_t, StmtSequence>> &StmtsByHash) {
+/// 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();
 
   StmtDataCollector<llvm::MD5>(S, Context, Hash);
 
   auto CS = dyn_cast<CompoundStmt>(S);
   SmallVector<size_t, 8> ChildHashes;
 

   CollectStmtSequenceData(LHS, LHSWrapper);
   CollectStmtSequenceData(RHS, RHSWrapper);
 
   return DataLHS == DataRHS;
 }
 
 void RecursiveCloneTypeIIConstraint::constrain(
     std::vector<CloneDetector::CloneGroup> &Sequences) {
+  RecursiveCloneTypeIIHashConstraint Hash;
+  Hash.constrain(Sequences);
+  RecursiveCloneTypeIIVerifyConstraint Verify;
+  Verify.constrain(Sequences);
+}
+
+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())
       continue;

       // 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();

lib/StaticAnalyzer/Checkers/CloneChecker.cpp

void CloneChecker::checkEndOfTranslationUnit(const TranslationUnitDecl *TU,
   bool ReportNormalClones = Mgr.getAnalyzerOptions().getBooleanOption(
       "ReportNormalClones", true, 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, RecursiveCloneTypeIIConstraint(),
-                      MinComplexityConstraint(MinComplexity),
-                      MinGroupSizeConstraint(2), OnlyLargestCloneConstraint());
+  Detector.findClones(
+      AllCloneGroups, RecursiveCloneTypeIIHashConstraint(),
+      MinGroupSizeConstraint(2), MinComplexityConstraint(MinComplexity),
+      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;