================
@@ -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]);
}
----------------
NagyDonat wrote:
This loop (which was also present in the old code) appears to be a quadratic
algorithm, as it (if I understand correctly) removes elements from a
functional-style immutable container one by one.
I'm not familiar with the toolset provided by this factory and datatype, but if
there are good tools, then consider reimplementing this with linear runtime.
(However, don't bother this with if you would need a significant effort or 10+
lines of additional code – simplicity is more important than ad hoc performance
improvements in code that is probably irrelevant.)
https://github.com/llvm/llvm-project/pull/215240
_______________________________________________
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
