[analyzer] Faster hashing of subsequences in CompoundStmts.

[teemperor]

Summary

This patches improves the hashing subsequences in CompoundStmts by incrementally hashing all subsequences with the same starting position. This results in a reduction of the time for this constraint while running over SQLite from 1.10 seconds to 0.55 seconds (-50%).

[NoQ]

This looks negligible compared to compilation time.
I wonder if we're now scalable enough to try finding whole-translation-unit clones.

lib/Analysis/CloneDetection.cpp

402

Hmm, is 8 enough here? People often write large functions. Maybe bump to 32 or 64?

lib/Analysis/CloneDetection.cpp

 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;
 
   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);
   }
 
   if (CS) {
-    for (unsigned Length = 2; Length <= CS->size(); ++Length) {
-      for (unsigned Pos = 0; Pos <= CS->size() - Length; ++Pos) {
-        llvm::MD5 Hash;
-        for (unsigned i = Pos; i < Pos + Length; ++i) {
-          size_t ChildHash = ChildHashes[i];
-          Hash.update(StringRef(reinterpret_cast<char *>(&ChildHash),
-                                sizeof(ChildHash)));
+    // 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)));
         }
-        StmtsByHash.push_back(std::make_pair(
-            createHash(Hash), StmtSequence(CS, D, Pos, Pos + Length)));
       }
     }
   }
 
   size_t HashCode = createHash(Hash);
   StmtsByHash.push_back(std::make_pair(HashCode, StmtSequence(S, D)));
   return HashCode;
 }