Author: teemperor Date: Sun Jul 9 14:14:36 2017 New Revision: 307509 URL: http://llvm.org/viewvc/llvm-project?rev=307509&view=rev Log: [analyzer] Faster hashing of subsequences in CompoundStmts.
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%). Reviewers: NoQ Reviewed By: NoQ Subscribers: cfe-commits, xazax.hun, v.g.vassilev Differential Revision: https://reviews.llvm.org/D34364 Modified: cfe/trunk/lib/Analysis/CloneDetection.cpp Modified: cfe/trunk/lib/Analysis/CloneDetection.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/Analysis/CloneDetection.cpp?rev=307509&r1=307508&r2=307509&view=diff ============================================================================== --- cfe/trunk/lib/Analysis/CloneDetection.cpp (original) +++ cfe/trunk/lib/Analysis/CloneDetection.cpp Sun Jul 9 14:14:36 2017 @@ -239,16 +239,27 @@ size_t RecursiveCloneTypeIIConstraint::s } 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))); } } } _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits