================
@@ -224,10 +228,39 @@ class SMTConstraintManager : public
clang::ento::SimpleConstraintManager {
SymbolReaper &SymReaper) override {
auto CZ = State->get<ConstraintSMT>();
auto &CZFactory = State->get_context<ConstraintSMT>();
+ llvm::SmallVector<ConstraintEntry> Constraints(CZ.begin(), CZ.end());
+ llvm::DenseMap<SymbolRef, SmallVector<size_t>> ConstraintsBySym;
+ llvm::DenseSet<SymbolRef> TraversedSymbols;
+ llvm::SmallVector<SymbolRef> WorkList;
+ llvm::BitVector RetainedConstraints(Constraints.size());
+
+ for (size_t Idx = 0; Idx < Constraints.size(); ++Idx) {
+ for (auto Symbol : Constraints[Idx].first->symbols()) {
+ if (SymReaper.isLive(Symbol) && TraversedSymbols.insert(Symbol).second)
+ WorkList.push_back(Symbol);
+ ConstraintsBySym[Symbol].push_back(Idx);
+ }
+ }
+
+ while (WorkList.size()) {
+ SymbolRef Item = WorkList.pop_back_val();
+ auto &SymConstraints = ConstraintsBySym[Item];
+ for (auto Idx : SymConstraints) {
+ if (RetainedConstraints.test(Idx))
+ continue;
+
+ RetainedConstraints.set(Idx);
+
+ for (auto Symbol : Constraints[Idx].first->symbols()) {
+ if (TraversedSymbols.insert(Symbol).second)
+ WorkList.push_back(Symbol);
+ }
+ }
+ }
- for (const auto &Entry : CZ) {
- if (SymReaper.isDead(Entry.first))
- CZ = CZFactory.remove(CZ, Entry);
+ for (size_t Idx = 0; Idx < Constraints.size(); ++Idx) {
+ if (!RetainedConstraints.test(Idx))
+ CZ = CZFactory.remove(CZ, Constraints[Idx]);
}
----------------
rdevshp wrote:
The comments in ImmutableSet.h (llvm/include/llvm/ADT/ImmutableSet.h) say that
the time/space complexity of the remove operation is logarithmic in the size of
the original set, so this loop should be `O(M + R*log(M))` where `M` is the
total number of constraints, and `R` is the number of constraints that are
removed.
https://github.com/llvm/llvm-project/pull/215240
_______________________________________________
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
