This is an archive of the discontinued LLVM Phabricator instance.

[analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency
ClosedPublic

Authored by ASDenysPetrov on Apr 2 2021, 9:06 AM.

Details

Summary

Handle intersected and adjacent ranges uniting them into a single one.
Example:
intersection [0, 10] U [5, 20] = [0, 20]
adjacency [0, 10] U [11, 20] = [0, 20]

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
ASDenysPetrov requested review of this revision.Apr 2 2021, 9:06 AM

Thanks for working on improvements of the solver and constraints! However, I have some tough questions about this patch.

What I really want to understand here is motivation. Why do we need to have add operation semantics like this in the first place? My guess is that "the user" will be in the following patch.
Additionally, I don't really like the idea of replacing something simple and fast (old add methods`) with something more complex unconditionally. Old users still don't need this additional logic. C++ has always been the language where we "pay for what we use".
So, with good motivation, I'd still prefer methods like add and addUnchecked or smith similar.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
127

This most certainly can be done in O(N + M) the same way the intersection is done.

vsavchenko requested changes to this revision.Apr 2 2021, 9:15 AM
This revision now requires changes to proceed.Apr 2 2021, 9:15 AM
ASDenysPetrov added a comment.EditedApr 2 2021, 9:54 AM

Thanks for working on improvements of the solver and constraints! However, I have some tough questions about this patch.

What I really want to understand here is motivation. Why do we need to have add operation semantics like this in the first place? My guess is that "the user" will be in the following patch.
Additionally, I don't really like the idea of replacing something simple and fast (old add methods`) with something more complex unconditionally. Old users still don't need this additional logic. C++ has always been the language where we "pay for what we use".
So, with good motivation, I'd still prefer methods like add and addUnchecked or smith similar.

My motivation is that I'm currently working on some bigger improvement (symbolic integral cast) and stucked here of the lack of handling intersections. Would you mind of accepting this revision in case if I restore complexity to O(N+M)?

Or. We always can have both methods. The quick add and caring add. Actually you've said that :)

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
127

Actually yes, it can. And it was, when I played with different solutions. But the code was poor readable. So I decided make it easier to understand to bring to review. Of couse I can move further to improve it and retain readability. I'll do.

@vsavchenko
OK, what do you think of *adjacency* feature? I mean it simplifies such ranges [1,2][3,4][5,6] to [1,6]. Is it worth for implementation?

Updated. Restored complexity to O(N).

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
112–113

Also optimized this particular case.

129–130

This allows to add a RangeSet of any type. E.g. RangeSet(uchar) + RangeSet(int) = valid, because of pin

I'm wondering whether we really need it here in practice?

clang/unittests/StaticAnalyzer/RangeSetTest.cpp
176

Fixed the misprint.

@vsavchenko
OK, what do you think of *adjacency* feature? I mean it simplifies such ranges [1,2][3,4][5,6] to [1,6]. Is it worth for implementation?

I want to clarify my position here. It's not that I am opposed to this change in principle, but I want to understand the motivation (a small example will be sufficient) and I don't want to sacrifice a single bit of performance efficiency of this part of code.
Even for the O(N + M) solution, I'd still be standing strong on keeping the old functions as is (except for maybe renaming them). Range sets are small and asymptotics don't work that well when reasoning about the expected performance benefits and gains.
For this reason, whenever we can, we should have the simplest operation possible in terms of the number of instructions, ie the constant factor is very strong here.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
127

Bring it here and we'll see what can be done on that front. *makeover time!*

145

nit: O(N + log(N)) == O(N)

vsavchenko added inline comments.Apr 3 2021, 3:28 AM
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
129–130

We mix ranges of different types way more than one would expect.

vsavchenko added inline comments.Apr 3 2021, 3:52 AM
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
114–115

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).

133

Is there a reason not to use range-based loop in this case?

141

This should be done outside of the loop, we assume that all the ranges are of the same type.

163

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.

ASDenysPetrov added a comment.EditedApr 3 2021, 7:25 AM

@vsavchenko Many thanks for your feedback!
I will make a new separate function for checking intersections considering all your suggestions along with the old quick add versions. It'll be more optimized.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
133

You are right. Working on restoring O(N) I been played with iterators, then found another solution, but forgot to return range-based loop back. Thnx.

141

+1 I'll move it outside the loop.

ASDenysPetrov updated this revision to Diff 335768.EditedApr 7 2021, 3:03 AM
ASDenysPetrov retitled this revision from [analyzer] Handle intersections and adjacency in RangeSet::Factory::add function to [analyzer] Implemented RangeSet::Factory::unite function to handle intersections and adjacency.

Updated. Implemented four separate functions RangeSet::Factory::unite. Each function has the most optimized approach to handle intersections for the particular case.

@vsavchenko You are welcome to evaluate this changes.

I want to understand the motivation (a small example will be sufficient)

I'm afraid a snippet out of context wouldn't make much sense for you. Let me present you the next patch soon.

Well, that is a nice exercise for "two pointer" problems, but can we please talk about the actual use case for it?

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
137

I'd prefer merge

218

This algorithm is indeed O(N +M), good job!
But let me get picky again 😅

It looks like we do too many comparisons in this loop. As I said earlier, constant factor is the key here and while this iterator idea is good it is a tradeoff. There is a piece of knowledge that would've been obvious with regular iterators, now is a run-time unknown that we constantly need to check (isTo and isFrom).

What we are trying to achieve here is not harder than what we do in intersect and there it is way less comparisons. While iterating through sets we can keep a set of invariants, so we don't need to re-check something that we already know.

Here is a sketch for the algorithm:

{
  assert(First != FirstEnd && Second != SecondEnd);
  // We have && here because one of them reaches its end,
  // we should not check for it again and simply add the rest
  // of the other set.
  while (true) {
    // We need to find the beginning of the next range to add
    // First should be the iterator which To is a candidate to be
    // an and for the merged range.
    if (First.From() > Second.From()) {
      swap();
    }

    auto From = First.From();

    // That's it, we found our start, and we need to go through
    // other ranges and look for the end.
    // After this point, First.From() shouldn'y be accessed.

    while (true) {
      // We can compress all the checks into just one.
      // This essentially means that Second should not get merged with First.
      if (Second.From() > First.To() + 1) {
        break;
      }

      if (Second.From() > First.From()) {
        // First is maintained as a candidate for the end.
        swap();
      }

      // At this point we know that Second lives fully inside
      // of the new range and we can skip it.
      ++Second;

      // If we have nothing else in the second set...
      if (Second == SecondEnd) {
        // ...let's finish the current range first...
        Result.emplace_back(From, First.To());
        while (++First != FirstEnd) {
          // ...and copy the rest of the ranges
          Result.push_back(*First);
        }
        // The range is ready.
        return makePersistent(Result);
      }
    };

    // Second is outside of the range, and we can
    // safely add a new range.
    Result.emplace_back(From, First.To());
    ++First;

    // First set can be over at this point and we should...
    if (First == FirstEnd) {
      // ...copy the rest if the second set's ranges.
      while (Second != SecondEnd) {
        Result.push_back(*(Second++));
      }
      // Nothing left to do.
      return makePersistent(Result);
    }
  };

  // No way for us to get here!
  llvm_unreachable("...");
}

It's trickier in the way we end things than the intersection because we still need to add the rest of the other set.

280–294

I don't see any practical reasons to keep this version over the more generic RangeSet + RangeSet

322–336

Same here, it is just way more code to maintain.

vsavchenko added inline comments.Apr 8 2021, 5:20 AM
clang/unittests/StaticAnalyzer/RangeSetTest.cpp
481

I guess I also want to have more cases where ranges from RHS are in between ranges from LHS, also it should be a case with LHS being a set of ranges.

507

Also I'd like to see cases when there are ranges to merge from two sets but then one set has a bunch of other ranges that should be added as is. We can automatically think of two possibilities here: when these additional ranges are before and after the common part.
And I guess I want at least one check with two sets with a good amount of ranges in both covering all possible situations and overlappings.

ASDenysPetrov added a comment.EditedApr 9 2021, 10:43 AM

@vsavchenko
Thank you for the proposed solution. It looks much easier to understand and maintain. Great! I will take it into account.

Well, that is a nice exercise for "two pointer" problems, but can we please talk about the actual use case for it?

I'm currently working on integral cast between ranges. Consider the range of int which is casted to char. You've got some ranges of int which obviously should be corespondently represented as some other ranges of char.
Some examples:

int [257, 259]  -> char [1, 3]
int [510, 513]  -> char [-2, 1]
int [42, 1000]  -> char [-128, 127]
int [257, 259] U [2049, 2051]  -> char [1,3] // Here we need `unite` logic to get the casted range because both original ranges lay on the same area after trancation.

Updated the patch due to comments. Added more tests. Simplified and improved solution.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
137

There are common namings of operations with sets and union is one of them. IMO this is most appropriate one.

Minor comment fix.

Minor performance improvement. Add more comments.

vsavchenko added inline comments.May 12 2021, 4:21 AM
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
147

LHS

247

nit: "...on the fact that..."

250

ContainerType is basically a mutable version of RangeSet, so there is only one reason to return it - you believe that the users might want to modify it after they called this unite. But as long as this unite is just a generalized version of user-facing unites, it can totally return RangeSet`.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
112

Let's reserve some place here. Because LHS and RHS don't have intersections, the result always has size(LHS) + size(RHS) elements

222

Oof, I don't know about this algorithm. I mean it does its job. But IMO it lacks a good description of what are the invariants and what are the different situations we are looking for.
Aaaand you kind of re-check certain conditions multiple times. One example here is the check for Min and Max. Those situations are super rare, but we check for them on every single iteration. std::min and std::max are additional comparisons. As I mentioned before, constant factor is the key here and less comparisons we do is way more important than doing binary search at some point.
Just make a benchmark if you don't believe me (with google-benchmark, for example). The version with less comparisons will dominate one with more on RangeSet under 20 (and they'll be even smaller in practice).

@vsavchenko Thanka for the suggestions! I'll take them into account and update the patch.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
250

I'm going to use raw ContainerType in further patches. So this is exactly what I want.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
222

I'll investigate the whole algorithm once more and reduce comparisons.

vsavchenko added inline comments.May 12 2021, 5:27 AM
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
250

Oh, I see. OK then :)

Reworked the solution. Returned to Implemented two versions of the same algorithm. Most optimized (but more verbose) and generalized one (but less optimized).
Added a bit more tests. @vsavchenko , please, look.

Minor improvements in unit tests.

More minor improvements in unit tests.

To be honest, I don't think that it solves the problem I mentioned before. The fact that conditions and branching are part of operator++ now, doesn't cancel them. I noticed that you made the first loop, so we don't need to check for Min in the main loop, and this is the right direction. But this approach has the same problem as one of the previous methods - you check isFrom, this is the price of abstraction. This is something that we won't be doing when working outside of such abstractions. Also, when one of the range sets is shorter, you will keep checking if the other iterator is end on every iteration when you run out of the ranges in shorter set.

I'm sorry for being so hard on you about this patch. 😔

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
257

nit: it has different ticks than you use in all other places

ASDenysPetrov added a comment.EditedMay 26 2021, 5:48 AM

@vsavchenko
Thanks for your suggestions! I really appreciate it! I'll do my best on this algorithm.
BTW, I've just presented the motivation you looked D103094 and D103096.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
257

I'm sorry. I didn't get it. What do you mean?

vsavchenko added inline comments.May 26 2021, 6:58 AM
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
257

This is a super duper tiny thing: you usually write ) or (, but here wrote '('.

ASDenysPetrov added inline comments.May 26 2021, 8:20 AM
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
257

Oh! :-) Sharp eye!

ASDenysPetrov updated this revision to Diff 348284.EditedMay 27 2021, 8:41 AM

@vsavchenko
Reworked the algorithm.

I hope this is a final version. Honestly, I also have the most optimized version but it has twice more similar(but different) code and gotos. I decided not to present it. Let it be less micro-optimized but much readable version.

Fixed the issue. Added more unit tests.

I think this iteration is much better, it requires way more description as it has now. You didn't actually describe anywhere how this algorithm actually works.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
210

nit: "is adjacent"

vsavchenko added inline comments.Jun 17 2021, 3:39 AM
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
200–201

At this point, we know for a fact that the next range we are going to add to our result set starts with I1->From(). No need to check F for null or anything

212

Why break? At this point we know that what we peaked into is actually a part of another range (in terms of the end result).
And this range is over, you just need to add it to the final result!

214–218

You actually don't need it, the moment you swap two iterators and find out that I1->From() <= I2->From(), that's it I1->From() is the beginning of the new range. No need to carry extra flag here.

227

nit
Additionally, you didn't tell your readers WHY you are even swapping iterators in the first place and what relationship they have. You need to communicate in terms of invariants.

244

This goto is always finishing with a return, so we can refactor goto end1 into something like return copyIntoResult(I1, E1); and goto end2 into return copyIntoResult(I2, E2);.
As I mentioned before, optional F should be removed. On every path we should know deterministically what is the beginning and what is the end of the range that we are trying to add.

Updated. Removed F as flag. Replaced goto with closure. Detailed comments and fixed typos.

@vsavchenko made changes according your suggestions.

How about this patch and the entire stack?

Rebased. Review, please.

@ASDenysPetrov Nice work! I really appreciate the hard work you guys (with @vsavchenko) had done here. I really like that you have created visible test cases (though the last ones are a bit cryptic for me). It is going to take some more time to finish my review.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
177

This is called

I still need to chew through the code but on a high level, I think it looks correct.
PS: the test coverage is outstanding!

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
147

Why do you take APSInts by value? Generally, we take them by reference.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp
88

Shouldn't you use sizeof(BaseType) * CHAR_BIT instead?

PS: the test coverage is outstanding!

Thank you for this analysis.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
147

I want to send a message to the caller that he can pass an arbitrary APSInt without warrying about making it permanent (aka stored by the Factory). But we can revise this contract and carry this responsibility to a caller.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp
88

Agree. It's better to avoid magic numbers. I'll fix.

martong added inline comments.Oct 20 2021, 2:41 AM
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
147

Why do you take APSInts by value? Generally, we take them by reference.

Actually, it is specific to BasicValueFactory to cache the APSInts, however, it might not be the best practice. I doubt that somebody has ever measured the performance of passing APSInts by value, so my guess is the caching of APSInts might be an early optimization that might be more harmful than advantageous. On top of all this, we do the caching inconsistently, just consider the member functions of APSIntType, they all return by value.

Perhaps (totally independently from this patch of course), it might be worth to have a measurement/comparison with removed cache and pass by value.

steakhal added inline comments.Oct 20 2021, 8:53 AM
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
147

Okay, then we shall leave this as-is now.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp
88

It's not only that but just imagine testing a clang on a special hardware where they have let's say 9 bit bytes, for parity or something similar stuff.
The test would suddenly break.
Although I suspect there would be many more things to break TBH xD

I think, the visual comments that we have in intersect makes the code of intersect a lot easier to follow. Could you please add similar visual comments here? Also, I find First and Second in intersect way more better naming than I1 and I2, could you please update?

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
167

I think, the naming conventions we have in intersect are easier to follow. Could we call I1 as First and I2 as Second?

179
186

It is not clear what is the complicated condition that you'd like to avoid. Could you please elaborate?

187–199

I'd like to see similar visual comments that we have in intersect.

202–203

Let's reuse as much as possible from intersect, both code and comments.

205–206

We could reuse SwapIterators from intersect. Of course for that we need to make a real function out of the lambda.

209
210

Let's be consistent with intersect. Also, you could introduce the variable here, and it is not needed to declare that at L176.

212
240

@martong
Thanks for your inlines. I'll update the patch.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp
88

I am always skeptical about using`CHAR_BIT`, beacuse it represents bit number in char. And what if it would be 16 for instance (aka 2 bytes). But my intention is to get an amount of bits for a particular type. And I want something to represent a number of bits in a byte as a fundamental unit, but not something that depends on a char size on a particular platform.
I would better introduce something like constexpr size_t BITS_IN_BYTE = 8;.

@martong @steakhal
Updated according to your comments. Thank you!

steakhal added inline comments.Oct 27 2021, 9:14 AM
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
198–202

Might be First->To() == Second->To(). In this case the comment is not completely accurate.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp
88

basic.memobj 6.7.1/22:

The number of bits in a byte is reported by the macro CHAR_­BIT in the header <climits>.

ASDenysPetrov added inline comments.Oct 28 2021, 9:10 AM
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
198–202

I'll update.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp
88

These legacy names... :) I'll update.

ASDenysPetrov added inline comments.Oct 28 2021, 10:00 AM
clang/unittests/StaticAnalyzer/RangeSetTest.cpp
88

BTW, the first time this definition appeared only in C++17 in a footnote. The committee is not yet confident enough about CHAR_BIT that it still resides there :)

Thanks Denys for the update! Very good! However, I think maybe we could make the code a bit more simpler.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
227–231

I am not sure about this, but perhaps we could put this swapIterators call right at the beginning of the nested while loop (L243). That would eliminate the need to call it again at the end of the second while loop.

241

So, this loop is about to merge conjunct Ranges. The first time when we find disjoint Ranges then we break out. (Or we return once we reach the end of any of the RangeSets.)
This makes we wonder, if it would be possible to split this while loop into a lambda named mergeConjunctRanges ?

288–290

Should this be like in the code suggestion? You incremented First at L276.

291

?

Gentle ping.

ASDenysPetrov added inline comments.Nov 18 2021, 8:40 AM
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
227–231

I'm afraid, it is not the case. Every loop needs its own swapIterators. As you can see, swapIterators in the nested loop invokes not always because of break; in the middle. Otherwise, it would invokes each time. But I checked your suggestion. It doesn't work.

241

I'm not in favor of introducing another level of abstraction. It would divide the flow/comments and could reduce readability and performance which is crucial here.

Fixed comments.

Thanks for the update, I am okay with the .cpp file, now I continue the review with the tests.

martong accepted this revision.Dec 2 2021, 12:11 PM

Nice, assiduous work! The tests are awesome!
LGTM, with minor revisions. Please check out my suggestions about the tests' formatting and there are those disturbing (LHS, RHS) swaps in the comments.

I am going to continue with the next patch in the stack. I recognize that the handling of casts is very important and problems related to not handling them occurs even more frequently as other parts of the engine evolve (e.g. https://reviews.llvm.org/D113753#3167134)

clang/unittests/StaticAnalyzer/RangeSetTest.cpp
448
456

I think, either we should use {{X, X}} or X everywhere, but not mixed.

532–533

LHS and RHS is swapped here?

535–536

I think we could better format these more complex cases.

540–541

LHS and RHS is swapped?

543–544
548–549

LHS and RHS is swapped?

565–566

LHS and RHS is swapped here as well.

589
597–599
597–599

What do you think about this format? The result can be easily verified this way I think, but a bit ugly ...

@martong

Nice, assiduous work!

Many thanks for your time! Your work is not less assiduous!

(LHS, RHS) swaps

it doesn't really matter, as the operation is comutative, but, yes, it does matter to depict the particular test case. I'll revise twise LHS-RHS's.

I am going to continue with the next patch in the stack. I recognize that the handling of casts is very important and problems related to not handling them occurs even more frequently as other parts of the engine evolve (e.g. https://reviews.llvm.org/D113753#3167134)

Aha. I saw you patch. I'll join to review it.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp
448

There are three overloads of checkUnite which correspond to three overloads of RangeSet::unite. I made it consistent to other check-functions (add e.g.).

456

This tests different oveloaded versions of RangeSet::unite.

535–536

clang-fromat acts on its own. But I agree, it looks the way better. I'll consider wrapping it into // clang-format on/off directives.

597–599

I think ASCII art does this job. Let code look as code :)

Fixed code formatting in the unit test file according to remarks. Ready to load.

This revision was not accepted when it landed; it landed in state Needs Review.Dec 10 2021, 8:48 AM
This revision was landed with ongoing or failed builds.
This revision was automatically updated to reflect the committed changes.