vsavchenko added inline comments.
================
Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:114-115
+ return RHS;
+ for (const Range &R : RHS)
+ LHS = add(LHS, R);
+ return LHS;
----------------
This is REAL bad. The main benefit of the new `RangeSet` over the old one is
the fact that common operations that consist of many basic operations are done
on mutable containers, i.e. when `RHS` has 10 elements this code will create
and copy a new array 10 times discarding 9 of them.
That's why every implementation method here operates on mutable `ContainerType`
and then makes is persistent.
Additionally, merging add can be done with one iteration over two containers,
but instead we do `O(N)` operation here `M` times, so it is not `O(N + M)`, but
`O(N * M)`.
================
Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:142
+ ContainerType::size_type InsertIdx = 0;
+ for (auto it = Original.begin(), e = Original.end(); it != e; ++it) {
+ const llvm::APSInt &RFrom = it->From();
----------------
Is there a reason not to use range-based loop in this case?
================
Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:150
+ if (!IsIntersected) {
+ auto One = APSIntType(From).getValue(1);
+ const bool isCurrentRangeOnTheLeft = RTo < From;
----------------
This should be done outside of the loop, we assume that all the ranges are of
the same type.
================
Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:172
+ Range NewRange{ValueFactory.getValue(From), ValueFactory.getValue(To)};
+ Result.insert(Result.begin() + InsertIdx, NewRange);
+
----------------
This is a problem here. This essentially doubles the work you did before.
What can be done in one `O(N)` loop is done with two.
However, I don't really see a point in fixing this algorithm because the more
generic `RangeSet` + `RangeSet` should be optimal `O(N + M)` and this one can
be implemented as a special case.
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D99797/new/
https://reviews.llvm.org/D99797
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
