This is an archive of the discontinued LLVM Phabricator instance.

[analyzer][solver] Redesign constraint ranges data structure
ClosedPublic

Authored by vsavchenko on Aug 24 2020, 8:30 AM.

Details

Summary

ImmutableSet doesn't seem like the perfect fit for the RangeSet
data structure. It is good for saving memory in a persistent
setting, but not for the case when the population of the container
is tiny. This commit replaces RangeSet implementation and
redesigns the most common operations to be more efficient.

Diff Detail

Event Timeline

vsavchenko created this revision.Aug 24 2020, 8:30 AM
Herald added a project: Restricted Project. ยท View Herald TranscriptAug 24 2020, 8:30 AM
vsavchenko requested review of this revision.Aug 24 2020, 8:30 AM
grandinj added inline comments.
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
88

Just curious - if they mostly contain 1 or 2 elements, why is N == 4 here?

vsavchenko added inline comments.Aug 24 2020, 9:52 AM
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
88

Essentially, the main factor is intuition ๐Ÿ˜†
The main idea here is that allocations are the single most expensive thing about ranges, so I want to avoid extra allocations not for 60% of range sets, but for 90%. I still should definitely measure performance difference for different values of N and gather some stats about the lengths.

NoQ added a comment.Aug 24 2020, 11:48 PM

If the numbers are confirmed to be as good as what i've sneak-peeked so far, that should be pretty amazing. Also whoa, test coverage!~

WDYT about moving introducing a generic "SmallImmutableSet" in llvm/ADT to back your implementation?

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

Given that you pass those by pointers, i suspect you don't need to fix the size at all. In fact the small-size of the small vector is, by design, a runtime value and you can use llvm::SmallVectorImpl * instead, which can point to SmallVector of any small-size. This would allow you to allocate small vectors of variable length which you can take advantage of whenever you know the length in advance.

135

"But what about setGet()???" - some user, probably :)

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

Given that we're certain from the start that the container will be persistent, can we save a copy by directly asking the factory to allocate a fresh container?

Also this seems to be one of the cases where variable-sized small vectors would make sense.

281

Thanks a lot for adding those comments. These methods were confusing as heck.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp
206

Why is it necessary to specify this-> here?

In D86465#2235289, @NoQ wrote:

If the numbers are confirmed to be as good as what i've sneak-peeked so far, that should be pretty amazing. Also whoa, test coverage!~

I'll add the charts with performance in the next couple of days

WDYT about moving introducing a generic "SmallImmutableSet" in llvm/ADT to back your implementation?

Oof, it is not really possible. First of all, existing RangeSet didn't really ensure that ranges do not intersect (add is/was not checking for that), and this is left for the user. Additionally, it is designed and optimized specifically for RangeSet queries and operations. Like intersect and contains in a more generic Set sense mean entirely different things.

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

Sounds reasonable, I'll give it a shot!

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

๐Ÿ˜Š

clang/unittests/StaticAnalyzer/RangeSetTest.cpp
206

It is due to shenanigans in test fixtures implementation. I didn't find a better workaround and other tests for other components also use this-> as far as I checked :-(

vsavchenko added inline comments.Aug 25 2020, 1:10 AM
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
119

Surprisingly this is not the case, it is cheaper to do whatever you want on small vectors on the stack and check if we already allocated it.
So, it is a deliberate choice to do it this way (you can see it in the comment inside of the makePersistent function.

vsavchenko added inline comments.Aug 25 2020, 2:18 AM
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
88

On the second thought, it's not going to be pretty. I still will need to allocate SmallVector<..., N>, where N is a compile-time constant, so it would be a big old switch where I "convert" run-time values into compile-time values so-to-speak.

Additionally, the involvement of SmallVector doesn't seem to be necessary at all because in this setting we don't use the main feature of it that it can grow larger than this size onto the heap. So, we can simply do the same trick with ArrayRef and std::array, but with less ambiguity.

However, one of the benefits of the current approach is "let's allocate as little as possible". It does the operation, checks if we allocated space for a container with these contents, and allocates it only if not. It is MUCH cheaper to do the operation and find out that we already have one like this or copy it to the newly allocated place than allocating it every time.

This is a huge change, I've got pretty tired at the end of the review.
I haven't checked the test-cases too deeply.

I've found only minor typos, clarity enhancement opportunities etc. nothing serious.
It was awesome to see how this code can be improved, even becoming comprehensible.

Sorry for my nit spam if it needs further discussion - but it looks good to me.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
35โ€“36

I don't think we should inherit from standard type. It should be a private member instead.
https://quuxplusone.github.io/blog/2018/12/11/dont-inherit-from-std-types/#never-ever-inherit-from-any-std

51

We have dump methods all over the place. Except this.
I propose to rename this to dump.

53โ€“55

It's a good practice to define comparison operators as friend functions inline.
Even if we don't rely on implicit conversions.

110

I think it should be std::size_t.

118โ€“123

What about merge or combine? I know that union is a keyword thus we can not use.

135

Why don't we call this createSetOf?
And createEmptySet.
I know that we don't create the empty set, but then what does a factory if not create stuff?

149โ€“160

I think an example would be awesome here.

170โ€“174

Why does this operation take O(N) time? Shouldn't be O(logN) instead?

190โ€“193
195โ€“196
203

As commented later, this function worth to be documented.

207โ€“208

Why do we need to explicitly spell the RangeSet here?

210โ€“211
213โ€“215
222

class Factory is a nested class of RangeSet, so it can already access all private parts.

225โ€“228

If this is the Rule of 5, where is the defaulted destructor?

252โ€“259

Finally, we got this, awesome!

261
269

If we implement equality, we should also support inequality.

272โ€“273

Missing explicit.

275โ€“276

TBH, I don't even know what the pin function does.
Should we consider a more descriptive name instead?
Maybe some docs would come handy too.

277

If it's a read-only operation why don't we take by value? Just like contains does.
If it has side-effects which modify the Point, why is that not documented here?

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
146โ€“149

Off-topic: Why do the Allocate and the similar allocator functions return T* if there is NO living object there (yet).
There will be, only if the placement constructor called...
I highly agree with you using void * there.

177โ€“178
181โ€“188

Previously we had an early empty check here.
Why don't we have that now?
Same question for the other overload.

281

I agree. These are black magic. xD

322โ€“325

It could definitely bear a longer name.

367โ€“370
375

It's unfortunate to refer to the next subrange by the ++Second.
Since operator++ has a side-effect I would recommend the Second+1 instead.

384

It's probably a personal taste though.
I think better to use the more verbose way incrementing an iterator if you are in the body of the loop.
It catches more attention.

412โ€“417

What.size() seems not justified here.
As you described previously, there is a case when the resulting range will have one more range then the previous one had.
negate([MIN, X] => [MIN,MIN] U [-X,MAX]

431
498

Can we use range-based for loops?

vsavchenko added inline comments.Aug 26 2020, 1:47 AM
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
110

Yeah, I didn't see a unified stand of the community on this matter. It looks like both options are pretty widespread. I mimicked SmallVector.h, but I can easily change it.

118โ€“123

Maybe, but the real union function is not present. And I think that in the original code it is add to hint that it's not really a union and nothing complex is done here. Maybe something like mergeUnchecked would work.

vsavchenko added inline comments.Aug 26 2020, 1:47 AM
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
149โ€“160

Agree, I simply copy-pasted the comment, but it would be better to expand it a bit because it might be confusing.

170โ€“174

We still create a copy of an old vector to maintain persistence, that's why it's O(N).

190โ€“193

The same thing with this comment, I think I'll rework it even more

195โ€“196

+1

203

I didn't think that it's necessary because of the fact that it's private, but it's pretty important, so I'll do it.

207โ€“208

Good point!

210โ€“211

+1

213โ€“215

+1

225โ€“228

It is, and it is forgotten, good catch!

269

Sure!

272โ€“273

More like missing /* implicit */ because it is intentional

277

Good point. Essentially it modifies the argument the same way pin functions do - by changing its type. I'll add the comments

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
146โ€“149

100% agree. It might be a source of mistakes where the type system doesn't help.

177โ€“178

I don't really see the benefits of one way over another and as I said in another comment, I don't really like to pay for an extra copy with iterators as just a rule of thumb.

181โ€“188

I'll add assertions checking for non-emptiness.
Essentially, it is a private function and the callers ensure this precondition.

322โ€“325

I think that there is nothing wrong in spelling out std::swap twice.
And do we have a naming convention for lambdas, is it a variable or a function from a naming perspective?

367โ€“370

OK

375

NP

384

It basically makes it Second++, and even though for these iterators it doesn't really matter I prefer not to pay extra copy when I don't need it.

498

We sure can, I wanted to change it but forgot

Here are some benchmarking results.
In docker:



Natively on my Mac (no memory measurements due to this issue during psutil installation):

Here are some benchmarking results.
In docker:



Natively on my Mac (no memory measurements due to this issue during psutil installation):

These are really promising figures, nice work! (And the measurement stuff itself is also a great addition, thanks for that!)
Not that it would matter much, but I was just wondering why there is a slightly bigger memory usage in some of the docker/small projects? The most conspicuous is oatpp.

steakhal added inline comments.Aug 26 2020, 5:49 AM
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
118โ€“123

Now I get it. Let's keep it as-is.
Might worth highlighting the **with all ranges from both** part though.

170โ€“174

Thanks. BTW I just forgot about this comment :D

272โ€“273

It doesn't have a too long identifier.
The users can always refer to it auto R = RangeSet(...), so we still don't repeat ourselves.
Do you have any particular counterexample?
Probably the tests will become slightly more bloated but eh. whatever.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
177โ€“178

Iterators supposed to be cheap to copy. That is why we take them by value all over the place.
IMO it should boil down to the very same codegen in both cases. https://godbolt.org/z/8x1zMh

To prove it, I disassembled the following functions in release clang build:

// _Z21raw_rangeset_iteratorN5clang4ento8RangeSetE
const llvm::APSInt &raw_rangeset_iterator(RangeSet What) {
  RangeSet::iterator It = What.begin();
  --It;
  return It->To();
}
// _Z26std_prev_rangeset_iteratorN5clang4ento8RangeSetE
const llvm::APSInt &std_prev_rangeset_iterator(RangeSet What) {
  RangeSet::iterator It = What.begin();
  return std::prev(It)->To();
}
(gdb) disassemble _Z21raw_rangeset_iteratorN5clang4ento8RangeSetE
Dump of assembler code for function raw_rangeset_iterator(clang::ento::RangeSet):
   0x0000000006102b10 <+0>:	mov    (%rdi),%rax
   0x0000000006102b13 <+3>:	mov    -0x8(%rax),%rax
   0x0000000006102b17 <+7>:	retq   
End of assembler dump.
(gdb) disassemble _Z26std_prev_rangeset_iteratorN5clang4ento8RangeSetE
Dump of assembler code for function _Z26std_prev_rangeset_iteratorN5clang4ento8RangeSetE:
   0x00000000061040d0 <+0>:	mov    (%rdi),%rax
   0x00000000061040d3 <+3>:	mov    -0x8(%rax),%rax
   0x00000000061040d7 <+7>:	retq   
End of assembler dump.
322โ€“325

That's a good question :)
I would say that its a variable, since you can mark it const, otherwise you could overwrite it. xD But that's a different story I think.
About the swap thingie, its a good practice to respect ADL for functions which know to be used via ADL.
Even if we don't depend on ADL in this particular case.

vsavchenko marked 21 inline comments as done.

Fix review remarks

These are really promising figures, nice work! (And the measurement stuff itself is also a great addition, thanks for that!)

Thanks ๐Ÿ˜Š

Not that it would matter much, but I was just wondering why there is a slightly bigger memory usage in some of the docker/small projects? The most conspicuous is oatpp.

The measurements fluctuate quite significantly and as you can see the means for both old and new experiments for oatpp are pretty close. So, I would say that the memory differences are not conclusive.
This being said, the performance measurements should also be taken with a grain of salt. We can't really say that we get 5-10% performance improvement for sure, but that analysis tends to be faster instead.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
53โ€“55

It doesn't seem like there is a single opinion on this in the codebase.

135

The naming is this way to be consistent with ImmutableSet::Factory

272โ€“273

These constructors are private and used in Factory methods. IMO they make those methods less cluttered.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
322โ€“325

I'm sorry but I still don't get the importance of dropping std:: here.

Previously, I liked this. Now I love it!
The benchmarks look promising as well.

I think I can not convince you about not modifying iterators using ++,--, etc. outside of loop-expressions. So be it :D

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

How about marking this LLVM_DUMP_METHOD?
Also, defining the operator<< would come handly later.

53โ€“55

Okay.

106

Shouldn't we call this const_iterator?

135

Makes sense.

205
207
268

Btw in C++20 we will have a way expressing this: explicit(false)

271โ€“280

Aww, excellent. Thanks.

272โ€“273

Okay.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
322โ€“325

Since we don't rely on Argument Dependent Lookup in this particular case, both versions do the same.
So it's perfectly fine as-is.
You should interpret my previous comment in a broader sense, like a guideline.
Which is meaningful mostly in generic programming.

414
462โ€“470

It might be overkill, but we can do this using transform.

495โ€“507

Hmm, we could simplify this further, assuming Range::operator<< is defined.

Here is my five cents. I haven't done with the review yet. I'm gonna return to it a bit later.

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

I'm not sure about optimizations but it seems like it could have less commands by omiting this.

135

IMO function's name should match to what it does. If it creates smth, so its name should starts with create. Even if all other functions have misleading names it doesn't mean we are delegated to ignore this fact.
My another suggestion is that Set is a common term to RangeSet. So I'd prefer to use getRangeSet instead.

I didn't check correctness of each Factory function but if it passes all tests and improves performance, I think it's enough.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
73โ€“74

That's very usefull description for reviewers, but I think is redundant for newcomers, when you're reading this you can't understand why it compares to ImmutableSet at all. I think this preamble only relates to the Summary of this patch as the core reason of this change.
You can just mention the fact that formerly it was an ImmutableSet. See http for details.

129

We can add one more instance of add (and maybe others): RangeSet add(RangeSet original, llvm::APSInt &point);.
Since we have RangeSet(Factory &F, const llvm::APSInt &Point) ctor, why wouldn't we have similar functionality in the Factory?

It could simplify function RangeSetTest::from in tests and be useful across the code on the whole.

174

IMHO you should change params with each other:
deletePoint(const llvm::APSInt &Point, RangeSet From) -> deletePoint(RangeSet Original, const llvm::APSInt &Point)
This will look more consistent with other interfaces like in add or intersect functions.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp
105

Explain, please, what's the matter to use wrap everywhere, not just call checkNegateImpl explicitly?
Won't the call works and looks the same? Like:

this->checkNegateImpl({{MIN, A}}, {{MIN, MIN}, {D, MAX}});
185

Thank you for making it in a proper way, instead of a list with different type instantiations.

My propositions for the function negate.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
433โ€“434

Here you can just move What. And after that you can do Result.reserve.

509

Here you can reuse SampleValue and simplify a bit this snippet.

@vsavchenko
Hi, I actually want this patch goes developing and be loaded. It's really the worth one. Is it abandoned?

@vsavchenko
Hi, I actually want this patch goes developing and be loaded. It's really the worth one. Is it abandoned?

Hi, nope. Just got postponed, I'll address the review comments soon!

vsavchenko added inline comments.Feb 19 2021, 5:24 AM
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
433โ€“434

What is a persistent range set, so moving it or making it persistent won't do, but we indeed can simply return What.

vsavchenko marked 16 inline comments as done.

Rebase and address review comments

Oof, it took me quite some time to come back to this.
I don't think that I'll be able to gather more performance-related data than I already did, so if it's OK with y'all, we can land it.
@NoQ @steakhal @ASDenysPetrov ?

clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
73โ€“74

I don't want to fully remove this comment because this is a comment explaining implementation detail, which I believe newcomers can skip altogether.
However, I will change it to say that it was formerly an immutable set.

205

That's a bit too verbose for the header IMO.

207

The same as above. I don't want to mention caches or arenas for the sake of hiding those as implementation detail. One might rightfully argue that having these methods here also leaks implementation detail into the header file, but without a pImpl, which I believe is not very widespread in the LLVM codebase, it's not possible to hide these.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
462โ€“470

Yeah, I'd say that it is wordier.

495โ€“507

I think it looks a bit clearer with llvm::interleaveComma

clang/unittests/StaticAnalyzer/RangeSetTest.cpp
105

Sure, we want to use a "raw" version of ranges and range sets everywhere in the tests for the simplicity of the test. Here I got bored writing from(Arg0), from(Arg1), ... and went with this.

185

Oh yes, it would've been a true nightmare repeating every test for every type

Add minor fix in tests

Ah, I wanted to give it a go, but the bots caught an assertion failure for the parent revision of this. See the details at the Bugzilla ticket.

What is more concerning is that this patch resolves that assertion failure. I guess it implies it can not be NFC?
Regardless, I'm gonna wait to get that issue fixed before I have a deeper look.

clang/unittests/StaticAnalyzer/RangeSetTest.cpp
186

You should probably test _ExtInts as well.

steakhal accepted this revision.Mar 22 2021, 1:11 AM

Given that it did not change any reports in our testbench it seems to be safe to land it.

It clearly improves the API significantly, so I'm not opposing.
Really good work @vsavchenko.

PS: If should support _ExtInts as well, even if they are not too common.
Please try to fill this gap, before you push your changes.

clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
495โ€“507

Awesome!

This revision is now accepted and ready to land.Mar 22 2021, 1:11 AM

Ah, I wanted to give it a go, but the bots caught an assertion failure for the parent revision of this. See the details at the Bugzilla ticket.

What is more concerning is that this patch resolves that assertion failure. I guess it implies it can not be NFC?
Regardless, I'm gonna wait to get that issue fixed before I have a deeper look.

Hmm, I tried it on that test without the fix, and the assertion failure is there.

vsavchenko added a comment.EditedMar 22 2021, 1:57 AM

Given that it did not change any reports in our testbench it seems to be safe to land it.

It clearly improves the API significantly, so I'm not opposing.
Really good work @vsavchenko.

Thanks ๐Ÿ˜Š

PS: If should support _ExtInts as well, even if they are not too common.
Please try to fill this gap, before you push your changes.

I do have a bit of a struggle here. This is a unit-test and thus should be compiled for all of the supported architectures by all of the supported compilers.
Is there a __has_feature or something for me to check if _ExtInt can be used?

I do have a bit of a struggle here. This is a unit-test and thus should be compiled for all of the supported architectures by all of the supported compilers.
Is there a __has_feature or something for me to check if _ExtInt can be used?

Aa, I get it. It is actually a clang specific extension. By checking git blame, it seems to be a quite new feature, clang-11+.
What about something like this?

using IntTypes = ::Types<int8_t, uint8_t, int16_t, uint16_t, int32_t,
                         uint32_t, int64_t, uint64_t
#if defined(__clang__) && __clang_major__ >= 11
                         , __int128_t, __uint128_t
                         , signed _ExtInt(200)
                         , unsigned _ExtInt(200)
#endif
>;

https://godbolt.org/z/GfMfWEz88 Seems to work for a number of compilers.

vsavchenko added a comment.EditedMar 22 2021, 3:14 AM

I do have a bit of a struggle here. This is a unit-test and thus should be compiled for all of the supported architectures by all of the supported compilers.
Is there a __has_feature or something for me to check if _ExtInt can be used?

Aa, I get it. It is actually a clang specific extension. By checking git blame, it seems to be a quite new feature, clang-11+.
What about something like this?

using IntTypes = ::Types<int8_t, uint8_t, int16_t, uint16_t, int32_t,
                         uint32_t, int64_t, uint64_t
#if defined(__clang__) && __clang_major__ >= 11
                         , __int128_t, __uint128_t
                         , signed _ExtInt(200)
                         , unsigned _ExtInt(200)
#endif
>;

https://godbolt.org/z/GfMfWEz88 Seems to work for a number of compilers.

This is not only a compiler feature, it also should be supported by the target architecture:
https://godbolt.org/z/ddjYYx9x6

This is not only a compiler feature, it also should be supported by the target architecture:
https://godbolt.org/z/ddjYYx9x6

It's getting complicated then xD. I guess we should complement unittests with LIT tests?
You can know there that clang is recent enough and pinning the target triple would also solve this.

This is not only a compiler feature, it also should be supported by the target architecture:
https://godbolt.org/z/ddjYYx9x6

It's getting complicated then xD. I guess we should complement unittests with LIT tests?
You can know there that clang is recent enough and pinning the target triple would also solve this.

My suggestion would be to check these separately with a possible fix.

It's getting complicated then xD. I guess we should complement unittests with LIT tests?
You can know there that clang is recent enough and pinning the target triple would also solve this.

My suggestion would be to check these separately with a possible fix.

Feel free to push this as-is. But try to cover these cases later if you can.

This revision was landed with ongoing or failed builds.Mar 22 2021, 3:53 AM
This revision was automatically updated to reflect the committed changes.