[PATCH] D82381: [analyzer] Introduce small improvements to the solver infra
This revision was automatically updated to reflect the committed changes.
Closed by commit rGf531c1c7c0d5: [analyzer] Introduce small improvements to the
solver infra (authored by vsavchenko).
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D82381/new/
https://reviews.llvm.org/D82381
Files:
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===
--- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -89,7 +89,7 @@
}
TriStateKind getCmpOpState(BinaryOperatorKind CurrentOP,
- BinaryOperatorKind QueriedOP) const {
+ BinaryOperatorKind QueriedOP) const {
return CmpOpTable[getIndexFromOp(CurrentOP)][getIndexFromOp(QueriedOP)];
}
@@ -364,6 +364,18 @@
return newRanges;
}
+RangeSet RangeSet::Delete(BasicValueFactory , Factory ,
+ const llvm::APSInt ) const {
+ llvm::APSInt Upper = Point;
+ llvm::APSInt Lower = Point;
+
+ ++Upper;
+ --Lower;
+
+ // Notice that the lower bound is greater than the upper bound.
+ return Intersect(BV, F, Upper, Lower);
+}
+
void RangeSet::print(raw_ostream ) const {
bool isFirst = true;
os << "{ ";
@@ -381,6 +393,107 @@
namespace {
+//===--===//
+//Intersection functions
+//===--===//
+
+template
+LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory ,
+ RangeSet::Factory , RangeSet Head,
+ SecondTy Second, RestTy... Tail);
+
+template struct IntersectionTraits;
+
+template struct IntersectionTraits {
+ // Found RangeSet, no need to check any further
+ using Type = RangeSet;
+};
+
+template <> struct IntersectionTraits<> {
+ // We ran out of types, and we didn't find any RangeSet, so the result should
+ // be optional.
+ using Type = Optional;
+};
+
+template
+struct IntersectionTraits {
+ // If current type is Optional or a raw pointer, we should keep looking.
+ using Type = typename IntersectionTraits::Type;
+};
+
+template
+LLVM_NODISCARD inline EndTy intersect(BasicValueFactory ,
+ RangeSet::Factory , EndTy End) {
+ // If the list contains only RangeSet or Optional, simply return
+ // that range set.
+ return End;
+}
+
+LLVM_NODISCARD LLVM_ATTRIBUTE_UNUSED inline Optional
+intersect(BasicValueFactory , RangeSet::Factory , const RangeSet *End) {
+ // This is an extraneous conversion from a raw pointer into Optional
+ if (End) {
+return *End;
+ }
+ return llvm::None;
+}
+
+template
+LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory ,
+ RangeSet::Factory , RangeSet Head,
+ RangeSet Second, RestTy... Tail) {
+ // Here we call either the or version
+ // of the function and can be sure that the result is RangeSet.
+ return intersect(BV, F, Head.Intersect(BV, F, Second), Tail...);
+}
+
+template
+LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory ,
+ RangeSet::Factory , RangeSet Head,
+ SecondTy Second, RestTy... Tail) {
+ if (Second) {
+// Here we call the version of the function...
+return intersect(BV, F, Head, *Second, Tail...);
+ }
+ // ...and here it is either or , which
+ // means that the result is definitely RangeSet.
+ return intersect(BV, F, Head, Tail...);
+}
+
+/// Main generic intersect function.
+/// It intersects all of the given range sets. If some of the given arguments
+/// don't hold a range set (nullptr or llvm::None), the function will skip them.
+///
+/// Available representations for the arguments are:
+/// * RangeSet
+/// * Optional
+/// * RangeSet *
+/// Pointer to a RangeSet is automatically assumed to be nullable and will get
+/// checked as well as the optional version. If this behaviour is undesired,
+/// please dereference the pointer in the call.
+///
+/// Return type depends on the arguments' types. If we can be sure in compile
+/// time that there will be a range set as a result, the returning type is
+/// simply RangeSet, in other cases we have to back off to Optional.
+///
+/// Please, prefer optional range sets to raw pointers. If the last argument is
+/// a raw pointer and all previous arguments are None, it will cost one
+/// additional check to convert RangeSet * into Optional.
+template
+LLVM_NODISCARD inline
+typename IntersectionTraits::Type
+intersect(BasicValueFactory ,
[PATCH] D82381: [analyzer] Introduce small improvements to the solver infra
vsavchenko updated this revision to Diff 278454.
vsavchenko added a comment.
Rename function
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D82381/new/
https://reviews.llvm.org/D82381
Files:
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===
--- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -89,7 +89,7 @@
}
TriStateKind getCmpOpState(BinaryOperatorKind CurrentOP,
- BinaryOperatorKind QueriedOP) const {
+ BinaryOperatorKind QueriedOP) const {
return CmpOpTable[getIndexFromOp(CurrentOP)][getIndexFromOp(QueriedOP)];
}
@@ -364,6 +364,18 @@
return newRanges;
}
+RangeSet RangeSet::Delete(BasicValueFactory , Factory ,
+ const llvm::APSInt ) const {
+ llvm::APSInt Upper = Point;
+ llvm::APSInt Lower = Point;
+
+ ++Upper;
+ --Lower;
+
+ // Notice that the lower bound is greater than the upper bound.
+ return Intersect(BV, F, Upper, Lower);
+}
+
void RangeSet::print(raw_ostream ) const {
bool isFirst = true;
os << "{ ";
@@ -381,6 +393,107 @@
namespace {
+//===--===//
+//Intersection functions
+//===--===//
+
+template
+LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory ,
+ RangeSet::Factory , RangeSet Head,
+ SecondTy Second, RestTy... Tail);
+
+template struct IntersectionTraits;
+
+template struct IntersectionTraits {
+ // Found RangeSet, no need to check any further
+ using Type = RangeSet;
+};
+
+template <> struct IntersectionTraits<> {
+ // We ran out of types, and we didn't find any RangeSet, so the result should
+ // be optional.
+ using Type = Optional;
+};
+
+template
+struct IntersectionTraits {
+ // If current type is Optional or a raw pointer, we should keep looking.
+ using Type = typename IntersectionTraits::Type;
+};
+
+template
+LLVM_NODISCARD inline EndTy intersect(BasicValueFactory ,
+ RangeSet::Factory , EndTy End) {
+ // If the list contains only RangeSet or Optional, simply return
+ // that range set.
+ return End;
+}
+
+LLVM_NODISCARD LLVM_ATTRIBUTE_UNUSED inline Optional
+intersect(BasicValueFactory , RangeSet::Factory , const RangeSet *End) {
+ // This is an extraneous conversion from a raw pointer into Optional
+ if (End) {
+return *End;
+ }
+ return llvm::None;
+}
+
+template
+LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory ,
+ RangeSet::Factory , RangeSet Head,
+ RangeSet Second, RestTy... Tail) {
+ // Here we call either the or version
+ // of the function and can be sure that the result is RangeSet.
+ return intersect(BV, F, Head.Intersect(BV, F, Second), Tail...);
+}
+
+template
+LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory ,
+ RangeSet::Factory , RangeSet Head,
+ SecondTy Second, RestTy... Tail) {
+ if (Second) {
+// Here we call the version of the function...
+return intersect(BV, F, Head, *Second, Tail...);
+ }
+ // ...and here it is either or , which
+ // means that the result is definitely RangeSet.
+ return intersect(BV, F, Head, Tail...);
+}
+
+/// Main generic intersect function.
+/// It intersects all of the given range sets. If some of the given arguments
+/// don't hold a range set (nullptr or llvm::None), the function will skip them.
+///
+/// Available representations for the arguments are:
+/// * RangeSet
+/// * Optional
+/// * RangeSet *
+/// Pointer to a RangeSet is automatically assumed to be nullable and will get
+/// checked as well as the optional version. If this behaviour is undesired,
+/// please dereference the pointer in the call.
+///
+/// Return type depends on the arguments' types. If we can be sure in compile
+/// time that there will be a range set as a result, the returning type is
+/// simply RangeSet, in other cases we have to back off to Optional.
+///
+/// Please, prefer optional range sets to raw pointers. If the last argument is
+/// a raw pointer and all previous arguments are None, it will cost one
+/// additional check to convert RangeSet * into Optional.
+template
+LLVM_NODISCARD inline
+typename IntersectionTraits::Type
+intersect(BasicValueFactory , RangeSet::Factory , HeadTy Head,
+ SecondTy Second, RestTy... Tail) {
+ if (Head) {
+
[PATCH] D82381: [analyzer] Introduce small improvements to the solver infra
ASDenysPetrov added inline comments.
Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:734
//expressions which we currently do not know how to negate.
- const RangeSet *getRangeForMinusSymbol(ProgramStateRef State, SymbolRef Sym)
{
+ Optional getRangeForInvertedSub(SymbolRef Sym) {
if (const SymSymExpr *SSE = dyn_cast(Sym)) {
NoQ wrote:
> vsavchenko wrote:
> > ASDenysPetrov wrote:
> > > vsavchenko wrote:
> > > > ASDenysPetrov wrote:
> > > > > As for me, I'd call this like `getRangeForNegatedSymSymExpr`, since
> > > > > you do Negate operation inside.
> > > > I'm not super happy about my name either, but I feel like it describes
> > > > it better than the previous name and your version. That function
> > > > doesn't work for any `SymSymExpr` and it doesn't simply negate whatever
> > > > we gave it. It works specifically for symbolic subtractions and this
> > > > is the information I want to be reflected in the name.
> > > Oh, I just assumed //...Sub// at the end as a //subexpression// but you
> > > mean //subtraction//. What I'm trying to say is that we can rename it
> > > like `getRangeFor...`//the expression which this function can handle//.
> > > E.g. `getRangeForNegatedSubtractionSymSymExpr`. My point is in a speaking
> > > name.
> > >
> > > I think //invertion// is not something appropriate in terms of applying
> > > minus operator. I think invertion of zero should be something opposite
> > > but not a zero. Because when you would like to implement the function
> > > which turns [A, B] into [MIN, A)U(B, MAX], what would be the name of it?
> > > I think this is an //invertion//.
> > >
> > > But this is not a big deal, it's just my thoughts.
> > My thought process here was that we are trying to get range for `A - B` and
> > there is also information on `B - A`, so we can get something for `A - B`
> > based on that. So, it doesn't really matter what it does under the hood
> > with ranges, it matters what its semantics are. Here I called `B - A` //an
> > inverted subtraction//.
> > I don't really know what would be the best name, but I thought that this
> > one makes more sense.
> > Because when you would like to implement the function which turns [A, B]
> > into [MIN, A)U(B, MAX], what would be the name of it? I think this is an
> > //invertion//.
>
> https://en.wikipedia.org/wiki/Complement_(set_theory)
> https://en.wikipedia.org/wiki/Inverse_function
>
> "Negated subtraction" is definitely my favorite so far. "Mirrored" might be a
> good layman term as well.
>https://en.wikipedia.org/wiki/Complement_(set_theory)
>https://en.wikipedia.org/wiki/Inverse_function
Thanks for the links, @NoQ. That's much definite now.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D82381/new/
https://reviews.llvm.org/D82381
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D82381: [analyzer] Introduce small improvements to the solver infra
NoQ accepted this revision.
NoQ added inline comments.
Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:734
//expressions which we currently do not know how to negate.
- const RangeSet *getRangeForMinusSymbol(ProgramStateRef State, SymbolRef Sym)
{
+ Optional getRangeForInvertedSub(SymbolRef Sym) {
if (const SymSymExpr *SSE = dyn_cast(Sym)) {
vsavchenko wrote:
> ASDenysPetrov wrote:
> > vsavchenko wrote:
> > > ASDenysPetrov wrote:
> > > > As for me, I'd call this like `getRangeForNegatedSymSymExpr`, since you
> > > > do Negate operation inside.
> > > I'm not super happy about my name either, but I feel like it describes it
> > > better than the previous name and your version. That function doesn't
> > > work for any `SymSymExpr` and it doesn't simply negate whatever we gave
> > > it. It works specifically for symbolic subtractions and this is the
> > > information I want to be reflected in the name.
> > Oh, I just assumed //...Sub// at the end as a //subexpression// but you
> > mean //subtraction//. What I'm trying to say is that we can rename it like
> > `getRangeFor...`//the expression which this function can handle//. E.g.
> > `getRangeForNegatedSubtractionSymSymExpr`. My point is in a speaking name.
> >
> > I think //invertion// is not something appropriate in terms of applying
> > minus operator. I think invertion of zero should be something opposite but
> > not a zero. Because when you would like to implement the function which
> > turns [A, B] into [MIN, A)U(B, MAX], what would be the name of it? I think
> > this is an //invertion//.
> >
> > But this is not a big deal, it's just my thoughts.
> My thought process here was that we are trying to get range for `A - B` and
> there is also information on `B - A`, so we can get something for `A - B`
> based on that. So, it doesn't really matter what it does under the hood with
> ranges, it matters what its semantics are. Here I called `B - A` //an
> inverted subtraction//.
> I don't really know what would be the best name, but I thought that this one
> makes more sense.
> Because when you would like to implement the function which turns [A, B] into
> [MIN, A)U(B, MAX], what would be the name of it? I think this is an
> //invertion//.
https://en.wikipedia.org/wiki/Complement_(set_theory)
https://en.wikipedia.org/wiki/Inverse_function
"Negated subtraction" is definitely my favorite so far. "Mirrored" might be a
good layman term as well.
Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:467-470
+/// Available representations for the arguments are:
+/// * RangeSet
+/// * Optional
+/// * RangeSet *
vsavchenko wrote:
> xazax.hun wrote:
> > NoQ wrote:
> > > Why do we have these representations in the first place?
> > >
> > > It sounds like you're treating null pointers / empty optionals
> > > equivalently to full ranges (i.e., intersecting with them has no effect).
> > > How hard would it be to simply construct an actual full range in all the
> > > places in which we currently have empty optionals?
> > +1
> >
> > I also find this confusing. Should I interpret a None as a full or empty
> > range? Does this depend on the context or a general rule? Is there any
> > reason we need to handle nullable pointers or could we actually make call
> > sites more uniform to get rid of some of the complexity here?
> > It sounds like you're treating null pointers / empty optionals equivalently
> > to full ranges (i.e., intersecting with them has no effect)
> It is not actually true. Empty optionals is the information that "this range
> information is not available for this symbol". It is true that intersecting
> with them has no effect, but they are semantically different in other
> aspects.
>
> Currently solver RELIES on the information that whether the range is
> available or not (see my previous comment), and we simply couldn't get rid of
> this behavior as part of NFC.
>
> > How hard would it be to simply construct an actual full range in all the
> > places in which we currently have empty optionals?
> It is not hard architecturally, but it WILL make the change functional and
> possibly impact the performance.
>
> > Should I interpret a None as a full or empty range?
> Neither of those. That is the problem right now, that we rely on different
> sources of information for the ranges and behave differently depending on
> whether one piece of information is available or not.
>
> > Does this depend on the context or a general rule?
> Semantics are always the same - this info is not available.
>
> > Is there any reason we need to handle nullable pointers?
> `State->get(abc)` returns a nullable pointer meaning optional object, it
> is hard to avoid it especially because we currently behave very differently
> when this information is not available.
>
> > ...could we actually make call
[PATCH] D82381: [analyzer] Introduce small improvements to the solver infra
ASDenysPetrov added a comment. @vsavchenko OK, let it be. ) Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D82381/new/ https://reviews.llvm.org/D82381 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D82381: [analyzer] Introduce small improvements to the solver infra
vsavchenko marked 2 inline comments as done.
vsavchenko added inline comments.
Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:734
//expressions which we currently do not know how to negate.
- const RangeSet *getRangeForMinusSymbol(ProgramStateRef State, SymbolRef Sym)
{
+ Optional getRangeForInvertedSub(SymbolRef Sym) {
if (const SymSymExpr *SSE = dyn_cast(Sym)) {
ASDenysPetrov wrote:
> vsavchenko wrote:
> > ASDenysPetrov wrote:
> > > As for me, I'd call this like `getRangeForNegatedSymSymExpr`, since you
> > > do Negate operation inside.
> > I'm not super happy about my name either, but I feel like it describes it
> > better than the previous name and your version. That function doesn't work
> > for any `SymSymExpr` and it doesn't simply negate whatever we gave it. It
> > works specifically for symbolic subtractions and this is the information I
> > want to be reflected in the name.
> Oh, I just assumed //...Sub// at the end as a //subexpression// but you mean
> //subtraction//. What I'm trying to say is that we can rename it like
> `getRangeFor...`//the expression which this function can handle//. E.g.
> `getRangeForNegatedSubtractionSymSymExpr`. My point is in a speaking name.
>
> I think //invertion// is not something appropriate in terms of applying minus
> operator. I think invertion of zero should be something opposite but not a
> zero. Because when you would like to implement the function which turns [A,
> B] into [MIN, A)U(B, MAX], what would be the name of it? I think this is an
> //invertion//.
>
> But this is not a big deal, it's just my thoughts.
My thought process here was that we are trying to get range for `A - B` and
there is also information on `B - A`, so we can get something for `A - B` based
on that. So, it doesn't really matter what it does under the hood with ranges,
it matters what its semantics are. Here I called `B - A` //an inverted
subtraction//.
I don't really know what would be the best name, but I thought that this one
makes more sense.
Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:841-844
+ RangeSet getTrueRange(QualType T) {
+RangeSet TypeRange = infer(T);
+return assumeNonZero(TypeRange, T);
+ }
ASDenysPetrov wrote:
> vsavchenko wrote:
> > ASDenysPetrov wrote:
> > > Don't you think this is too complicated for such a simple getter?
> > > Maybe we can just construct the range using smth about
> > > `RangeSet(RangeFactory, ++Zero, --Zero);` ?
> > It is more complex than a false range but there is a reason for it.
> >
> > First of all, `RangeSet` can't have ranges where the end is greater than
> > its start. Only `Intersect` can handle such ranges correctly. Another
> > thing is that ranges like that mean `[MIN, --Zero], [++Zero, MAX]` and
> > without a type we can't really say what `MIN` and `MAX` are, so such
> > constructor for `RangeSet` simply cannot exist.
> >
> > Another point is that we do need to have `[MIN, -1], [+1, MAX]` as opposed
> > to `[-1, -1], [+1, +1]` because of C language (it doesn't have boolean
> > type), and because of the cases like `a - b` where we know that `a != b`.
> >
> > I hope that answers the question.
> I just want this function has low complexity and be more lightweight as
> `getFalseRange`. And if we have any chance to simplify it (and you have all
> the data to get MIN and MAX), it'd be cool.
`infer(QualType T)` does just that ☺️ So it is a pretty low complexity.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D82381/new/
https://reviews.llvm.org/D82381
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D82381: [analyzer] Introduce small improvements to the solver infra
ASDenysPetrov added a comment.
@vsavchenko
Thank you.
Despite of all of my nits, LGTM!
Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:367-378
+RangeSet RangeSet::Delete(BasicValueFactory , Factory ,
+ const llvm::APSInt ) const {
+ llvm::APSInt Upper = Point;
+ llvm::APSInt Lower = Point;
+
+ ++Upper;
+ --Lower;
vsavchenko wrote:
> ASDenysPetrov wrote:
> > Useful function. But I'd better rename it to `subtract` as we are working
> > with sets (as a mathimatical collection). We should have a such one for the
> > Ranges not only for Points.
> > We have `intersect`, `delete` aka `subtract`. And we also need to have
> > functions `union` and `symmetricDifference` to cover full palette of common
> > operations on sets.
> I agree that we should have a full set of functions. I don't agree however,
> that this function is a `subtract`. Subtract is an operation on two sets and
> here we have a set and a point. One might argue that a point is just a very
> simple set, that's true, but real `subtract` would be more complex in its
> implementation.
>
> Naming it `delete`, on the other hand, I was coming from a notion of deleting
> points or neighbourhoods
> (https://en.wikipedia.org/wiki/Neighbourhood_(mathematics)#Deleted_neighbourhood).
>One might argue that a point is just a very simple set
That's actually what I mean :) and for this particular case you may leave the
implementation as is. And for me it still does what `subtract` does. But I'm
OK, I don't insist.
Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:734
//expressions which we currently do not know how to negate.
- const RangeSet *getRangeForMinusSymbol(ProgramStateRef State, SymbolRef Sym)
{
+ Optional getRangeForInvertedSub(SymbolRef Sym) {
if (const SymSymExpr *SSE = dyn_cast(Sym)) {
vsavchenko wrote:
> ASDenysPetrov wrote:
> > As for me, I'd call this like `getRangeForNegatedSymSymExpr`, since you do
> > Negate operation inside.
> I'm not super happy about my name either, but I feel like it describes it
> better than the previous name and your version. That function doesn't work
> for any `SymSymExpr` and it doesn't simply negate whatever we gave it. It
> works specifically for symbolic subtractions and this is the information I
> want to be reflected in the name.
Oh, I just assumed //...Sub// at the end as a //subexpression// but you mean
//subtraction//. What I'm trying to say is that we can rename it like
`getRangeFor...`//the expression which this function can handle//. E.g.
`getRangeForNegatedSubtractionSymSymExpr`. My point is in a speaking name.
I think //invertion// is not something appropriate in terms of applying minus
operator. I think invertion of zero should be something opposite but not a
zero. Because when you would like to implement the function which turns [A, B]
into [MIN, A)U(B, MAX], what would be the name of it? I think this is an
//invertion//.
But this is not a big deal, it's just my thoughts.
Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:841-844
+ RangeSet getTrueRange(QualType T) {
+RangeSet TypeRange = infer(T);
+return assumeNonZero(TypeRange, T);
+ }
vsavchenko wrote:
> ASDenysPetrov wrote:
> > Don't you think this is too complicated for such a simple getter?
> > Maybe we can just construct the range using smth about
> > `RangeSet(RangeFactory, ++Zero, --Zero);` ?
> It is more complex than a false range but there is a reason for it.
>
> First of all, `RangeSet` can't have ranges where the end is greater than its
> start. Only `Intersect` can handle such ranges correctly. Another thing is
> that ranges like that mean `[MIN, --Zero], [++Zero, MAX]` and without a type
> we can't really say what `MIN` and `MAX` are, so such constructor for
> `RangeSet` simply cannot exist.
>
> Another point is that we do need to have `[MIN, -1], [+1, MAX]` as opposed to
> `[-1, -1], [+1, +1]` because of C language (it doesn't have boolean type),
> and because of the cases like `a - b` where we know that `a != b`.
>
> I hope that answers the question.
I just want this function has low complexity and be more lightweight as
`getFalseRange`. And if we have any chance to simplify it (and you have all the
data to get MIN and MAX), it'd be cool.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D82381/new/
https://reviews.llvm.org/D82381
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D82381: [analyzer] Introduce small improvements to the solver infra
vsavchenko marked 3 inline comments as done.
vsavchenko added a comment.
Hi @ASDenysPetrov no problem at all! Thanks for taking your time and checking
it.
Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:367-378
+RangeSet RangeSet::Delete(BasicValueFactory , Factory ,
+ const llvm::APSInt ) const {
+ llvm::APSInt Upper = Point;
+ llvm::APSInt Lower = Point;
+
+ ++Upper;
+ --Lower;
ASDenysPetrov wrote:
> Useful function. But I'd better rename it to `subtract` as we are working
> with sets (as a mathimatical collection). We should have a such one for the
> Ranges not only for Points.
> We have `intersect`, `delete` aka `subtract`. And we also need to have
> functions `union` and `symmetricDifference` to cover full palette of common
> operations on sets.
I agree that we should have a full set of functions. I don't agree however,
that this function is a `subtract`. Subtract is an operation on two sets and
here we have a set and a point. One might argue that a point is just a very
simple set, that's true, but real `subtract` would be more complex in its
implementation.
Naming it `delete`, on the other hand, I was coming from a notion of deleting
points or neighbourhoods
(https://en.wikipedia.org/wiki/Neighbourhood_(mathematics)#Deleted_neighbourhood).
Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:734
//expressions which we currently do not know how to negate.
- const RangeSet *getRangeForMinusSymbol(ProgramStateRef State, SymbolRef Sym)
{
+ Optional getRangeForInvertedSub(SymbolRef Sym) {
if (const SymSymExpr *SSE = dyn_cast(Sym)) {
ASDenysPetrov wrote:
> As for me, I'd call this like `getRangeForNegatedSymSymExpr`, since you do
> Negate operation inside.
I'm not super happy about my name either, but I feel like it describes it
better than the previous name and your version. That function doesn't work for
any `SymSymExpr` and it doesn't simply negate whatever we gave it. It works
specifically for symbolic subtractions and this is the information I want to be
reflected in the name.
Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:841-844
+ RangeSet getTrueRange(QualType T) {
+RangeSet TypeRange = infer(T);
+return assumeNonZero(TypeRange, T);
+ }
ASDenysPetrov wrote:
> Don't you think this is too complicated for such a simple getter?
> Maybe we can just construct the range using smth about
> `RangeSet(RangeFactory, ++Zero, --Zero);` ?
It is more complex than a false range but there is a reason for it.
First of all, `RangeSet` can't have ranges where the end is greater than its
start. Only `Intersect` can handle such ranges correctly. Another thing is
that ranges like that mean `[MIN, --Zero], [++Zero, MAX]` and without a type we
can't really say what `MIN` and `MAX` are, so such constructor for `RangeSet`
simply cannot exist.
Another point is that we do need to have `[MIN, -1], [+1, MAX]` as opposed to
`[-1, -1], [+1, +1]` because of C language (it doesn't have boolean type), and
because of the cases like `a - b` where we know that `a != b`.
I hope that answers the question.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D82381/new/
https://reviews.llvm.org/D82381
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D82381: [analyzer] Introduce small improvements to the solver infra
ASDenysPetrov added a comment.
Hi @vsavchenko , sorry for the late review.
Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:367-378
+RangeSet RangeSet::Delete(BasicValueFactory , Factory ,
+ const llvm::APSInt ) const {
+ llvm::APSInt Upper = Point;
+ llvm::APSInt Lower = Point;
+
+ ++Upper;
+ --Lower;
Useful function. But I'd better rename it to `subtract` as we are working with
sets (as a mathimatical collection). We should have a such one for the Ranges
not only for Points.
We have `intersect`, `delete` aka `subtract`. And we also need to have
functions `union` and `symmetricDifference` to cover full palette of common
operations on sets.
Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:734
//expressions which we currently do not know how to negate.
- const RangeSet *getRangeForMinusSymbol(ProgramStateRef State, SymbolRef Sym)
{
+ Optional getRangeForInvertedSub(SymbolRef Sym) {
if (const SymSymExpr *SSE = dyn_cast(Sym)) {
As for me, I'd call this like `getRangeForNegatedSymSymExpr`, since you do
Negate operation inside.
Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:841-844
+ RangeSet getTrueRange(QualType T) {
+RangeSet TypeRange = infer(T);
+return assumeNonZero(TypeRange, T);
+ }
Don't you think this is too complicated for such a simple getter?
Maybe we can just construct the range using smth about `RangeSet(RangeFactory,
++Zero, --Zero);` ?
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D82381/new/
https://reviews.llvm.org/D82381
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D82381: [analyzer] Introduce small improvements to the solver infra
vsavchenko updated this revision to Diff 275955.
vsavchenko added a comment.
Rebase
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D82381/new/
https://reviews.llvm.org/D82381
Files:
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===
--- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -89,7 +89,7 @@
}
TriStateKind getCmpOpState(BinaryOperatorKind CurrentOP,
- BinaryOperatorKind QueriedOP) const {
+ BinaryOperatorKind QueriedOP) const {
return CmpOpTable[getIndexFromOp(CurrentOP)][getIndexFromOp(QueriedOP)];
}
@@ -364,6 +364,18 @@
return newRanges;
}
+RangeSet RangeSet::Delete(BasicValueFactory , Factory ,
+ const llvm::APSInt ) const {
+ llvm::APSInt Upper = Point;
+ llvm::APSInt Lower = Point;
+
+ ++Upper;
+ --Lower;
+
+ // Notice that the lower bound is greater than the upper bound.
+ return Intersect(BV, F, Upper, Lower);
+}
+
void RangeSet::print(raw_ostream ) const {
bool isFirst = true;
os << "{ ";
@@ -381,6 +393,107 @@
namespace {
+//===--===//
+//Intersection functions
+//===--===//
+
+template
+LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory ,
+ RangeSet::Factory , RangeSet Head,
+ SecondTy Second, RestTy... Tail);
+
+template struct IntersectionTraits;
+
+template struct IntersectionTraits {
+ // Found RangeSet, no need to check any further
+ using Type = RangeSet;
+};
+
+template <> struct IntersectionTraits<> {
+ // We ran out of types, and we didn't find any RangeSet, so the result should
+ // be optional.
+ using Type = Optional;
+};
+
+template
+struct IntersectionTraits {
+ // If current type is Optional or a raw pointer, we should keep looking.
+ using Type = typename IntersectionTraits::Type;
+};
+
+template
+LLVM_NODISCARD inline EndTy intersect(BasicValueFactory ,
+ RangeSet::Factory , EndTy End) {
+ // If the list contains only RangeSet or Optional, simply return
+ // that range set.
+ return End;
+}
+
+LLVM_NODISCARD LLVM_ATTRIBUTE_UNUSED inline Optional
+intersect(BasicValueFactory , RangeSet::Factory , const RangeSet *End) {
+ // This is an extraneous conversion from a raw pointer into Optional
+ if (End) {
+return *End;
+ }
+ return llvm::None;
+}
+
+template
+LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory ,
+ RangeSet::Factory , RangeSet Head,
+ RangeSet Second, RestTy... Tail) {
+ // Here we call either the or version
+ // of the function and can be sure that the result is RangeSet.
+ return intersect(BV, F, Head.Intersect(BV, F, Second), Tail...);
+}
+
+template
+LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory ,
+ RangeSet::Factory , RangeSet Head,
+ SecondTy Second, RestTy... Tail) {
+ if (Second) {
+// Here we call the version of the function...
+return intersect(BV, F, Head, *Second, Tail...);
+ }
+ // ...and here it is either or , which
+ // means that the result is definitely RangeSet.
+ return intersect(BV, F, Head, Tail...);
+}
+
+/// Main generic intersect function.
+/// It intersects all of the given range sets. If some of the given arguments
+/// don't hold a range set (nullptr or llvm::None), the function will skip them.
+///
+/// Available representations for the arguments are:
+/// * RangeSet
+/// * Optional
+/// * RangeSet *
+/// Pointer to a RangeSet is automatically assumed to be nullable and will get
+/// checked as well as the optional version. If this behaviour is undesired,
+/// please dereference the pointer in the call.
+///
+/// Return type depends on the arguments' types. If we can be sure in compile
+/// time that there will be a range set as a result, the returning type is
+/// simply RangeSet, in other cases we have to back off to Optional.
+///
+/// Please, prefer optional range sets to raw pointers. If the last argument is
+/// a raw pointer and all previous arguments are None, it will cost one
+/// additional check to convert RangeSet * into Optional.
+template
+LLVM_NODISCARD inline
+typename IntersectionTraits::Type
+intersect(BasicValueFactory , RangeSet::Factory , HeadTy Head,
+ SecondTy Second, RestTy... Tail) {
+ if (Head) {
+return
[PATCH] D82381: [analyzer] Introduce small improvements to the solver infra
vsavchenko marked an inline comment as done. vsavchenko added inline comments. Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:373 + ++Upper; + --Lower; + xazax.hun wrote: > Sorry if my question is dumb, but I do not really have a mental model at this > point about where do we actually handle types and overflows. Will this method > work when we delete the last or the first element of the full range of a type? > > I think having unit tests would be a great way to make this clear. I always > felt that the solver is actually something that should be really easy to test > separately and those tests would also help a lot to understand how the solver > is actually working. > Sorry if my question is dumb... No problem at all, I also had this question when I looked at that. > where do we actually handle types and overflows `APInt` class basically does it all for us in terms of overflows, number of bits, and signedness. > I think having unit tests would be a great way to make this clear I am onboard! I will add a framework for testing the solver in later patches. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D82381/new/ https://reviews.llvm.org/D82381 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D82381: [analyzer] Introduce small improvements to the solver infra
vsavchenko marked an inline comment as done. vsavchenko added inline comments. Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:467-470 +/// Available representations for the arguments are: +/// * RangeSet +/// * Optional +/// * RangeSet * xazax.hun wrote: > NoQ wrote: > > Why do we have these representations in the first place? > > > > It sounds like you're treating null pointers / empty optionals equivalently > > to full ranges (i.e., intersecting with them has no effect). How hard would > > it be to simply construct an actual full range in all the places in which > > we currently have empty optionals? > +1 > > I also find this confusing. Should I interpret a None as a full or empty > range? Does this depend on the context or a general rule? Is there any reason > we need to handle nullable pointers or could we actually make call sites more > uniform to get rid of some of the complexity here? > It sounds like you're treating null pointers / empty optionals equivalently > to full ranges (i.e., intersecting with them has no effect) It is not actually true. Empty optionals is the information that "this range information is not available for this symbol". It is true that intersecting with them has no effect, but they are semantically different in other aspects. Currently solver RELIES on the information that whether the range is available or not (see my previous comment), and we simply couldn't get rid of this behavior as part of NFC. > How hard would it be to simply construct an actual full range in all the > places in which we currently have empty optionals? It is not hard architecturally, but it WILL make the change functional and possibly impact the performance. > Should I interpret a None as a full or empty range? Neither of those. That is the problem right now, that we rely on different sources of information for the ranges and behave differently depending on whether one piece of information is available or not. > Does this depend on the context or a general rule? Semantics are always the same - this info is not available. > Is there any reason we need to handle nullable pointers? `State->get(abc)` returns a nullable pointer meaning optional object, it is hard to avoid it especially because we currently behave very differently when this information is not available. > ...could we actually make call sites more uniform to get rid of some of the > complexity here? Yes we can, but later on. See the explanations above and in my other comment. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D82381/new/ https://reviews.llvm.org/D82381 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D82381: [analyzer] Introduce small improvements to the solver infra
xazax.hun added inline comments. Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:373 + ++Upper; + --Lower; + Sorry if my question is dumb, but I do not really have a mental model at this point about where do we actually handle types and overflows. Will this method work when we delete the last or the first element of the full range of a type? I think having unit tests would be a great way to make this clear. I always felt that the solver is actually something that should be really easy to test separately and those tests would also help a lot to understand how the solver is actually working. Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:467-470 +/// Available representations for the arguments are: +/// * RangeSet +/// * Optional +/// * RangeSet * NoQ wrote: > Why do we have these representations in the first place? > > It sounds like you're treating null pointers / empty optionals equivalently > to full ranges (i.e., intersecting with them has no effect). How hard would > it be to simply construct an actual full range in all the places in which we > currently have empty optionals? +1 I also find this confusing. Should I interpret a None as a full or empty range? Does this depend on the context or a general rule? Is there any reason we need to handle nullable pointers or could we actually make call sites more uniform to get rid of some of the complexity here? Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D82381/new/ https://reviews.llvm.org/D82381 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D82381: [analyzer] Introduce small improvements to the solver infra
NoQ added inline comments. Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:467-470 +/// Available representations for the arguments are: +/// * RangeSet +/// * Optional +/// * RangeSet * Why do we have these representations in the first place? It sounds like you're treating null pointers / empty optionals equivalently to full ranges (i.e., intersecting with them has no effect). How hard would it be to simply construct an actual full range in all the places in which we currently have empty optionals? Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D82381/new/ https://reviews.llvm.org/D82381 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D82381: [analyzer] Introduce small improvements to the solver infra
vsavchenko marked an inline comment as done.
vsavchenko added inline comments.
Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:556
RangeSet infer(SymbolRef Sym) {
-const RangeSet *AssociatedRange = State->get(Sym);
-
-// If Sym is a difference of symbols A - B, then maybe we have range set
-// stored for B - A.
-const RangeSet *RangeAssociatedWithNegatedSym =
-getRangeForMinusSymbol(State, Sym);
-
-// If we have range set stored for both A - B and B - A then calculate the
-// effective range set by intersecting the range set for A - B and the
-// negated range set of B - A.
-if (AssociatedRange && RangeAssociatedWithNegatedSym)
- return AssociatedRange->Intersect(
- ValueFactory, RangeFactory,
- RangeAssociatedWithNegatedSym->Negate(ValueFactory, RangeFactory));
-
-if (AssociatedRange)
- return *AssociatedRange;
-
-if (RangeAssociatedWithNegatedSym)
- return RangeAssociatedWithNegatedSym->Negate(ValueFactory, RangeFactory);
+if (Optional ConstraintBasedRange = intersect(
+ValueFactory, RangeFactory, State->get(Sym),
NoQ wrote:
> I'm a bit confused, why aren't these invocations of
> `getRangeForInvertedSub()` and `getRangeForComparisonSymbol()` implemented
> simply as steps in `Visit()`? What's so different about them, other then our
> desire not to go into infinite recursion (which should probably be addressed
> via memoization)?
I even had a patch that moves these two functions inside of the `Visit`, but
then I reverted that change.
Right now the logic for each symbol is like this: let's try to find anything on
this symbol in the existing constraints and if we did find something - return
it. And only if that didn't work, we try to figure out something from the
sub-tree on its own.
So what does that mean in here: that we will need to make a performance
impacting [probably nothing serious, but still a functional] change - to
intersect the range assigned to the symbol and whatever we can infer from its
subtrees. It would be good to have when we support binary operators
`+/-/==/<=/etc.` because it can help narrowing it down.
As of now, it will give no information, only possible overhead of traversing a
tree. For this reason, I suggest to move those separately and AFTER we support
more operators, because that will also have a couple of good motivation
examples.
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D82381/new/
https://reviews.llvm.org/D82381
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D82381: [analyzer] Introduce small improvements to the solver infra
NoQ added inline comments.
Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:556
RangeSet infer(SymbolRef Sym) {
-const RangeSet *AssociatedRange = State->get(Sym);
-
-// If Sym is a difference of symbols A - B, then maybe we have range set
-// stored for B - A.
-const RangeSet *RangeAssociatedWithNegatedSym =
-getRangeForMinusSymbol(State, Sym);
-
-// If we have range set stored for both A - B and B - A then calculate the
-// effective range set by intersecting the range set for A - B and the
-// negated range set of B - A.
-if (AssociatedRange && RangeAssociatedWithNegatedSym)
- return AssociatedRange->Intersect(
- ValueFactory, RangeFactory,
- RangeAssociatedWithNegatedSym->Negate(ValueFactory, RangeFactory));
-
-if (AssociatedRange)
- return *AssociatedRange;
-
-if (RangeAssociatedWithNegatedSym)
- return RangeAssociatedWithNegatedSym->Negate(ValueFactory, RangeFactory);
+if (Optional ConstraintBasedRange = intersect(
+ValueFactory, RangeFactory, State->get(Sym),
I'm a bit confused, why aren't these invocations of `getRangeForInvertedSub()`
and `getRangeForComparisonSymbol()` implemented simply as steps in `Visit()`?
What's so different about them, other then our desire not to go into infinite
recursion (which should probably be addressed via memoization)?
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D82381/new/
https://reviews.llvm.org/D82381
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D82381: [analyzer] Introduce small improvements to the solver infra
vsavchenko updated this revision to Diff 272729.
vsavchenko added a comment.
Add forgotten nodiscards
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D82381/new/
https://reviews.llvm.org/D82381
Files:
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===
--- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -89,7 +89,7 @@
}
TriStateKind getCmpOpState(BinaryOperatorKind CurrentOP,
- BinaryOperatorKind QueriedOP) const {
+ BinaryOperatorKind QueriedOP) const {
return CmpOpTable[getIndexFromOp(CurrentOP)][getIndexFromOp(QueriedOP)];
}
@@ -364,6 +364,18 @@
return newRanges;
}
+RangeSet RangeSet::Delete(BasicValueFactory , Factory ,
+ const llvm::APSInt ) const {
+ llvm::APSInt Upper = Point;
+ llvm::APSInt Lower = Point;
+
+ ++Upper;
+ --Lower;
+
+ // Notice that the lower bound is greater than the upper bound.
+ return Intersect(BV, F, Upper, Lower);
+}
+
void RangeSet::print(raw_ostream ) const {
bool isFirst = true;
os << "{ ";
@@ -381,6 +393,107 @@
namespace {
+//===--===//
+//Intersection functions
+//===--===//
+
+template
+LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory ,
+ RangeSet::Factory , RangeSet Head,
+ SecondTy Second, RestTy... Tail);
+
+template struct IntersectionTraits;
+
+template struct IntersectionTraits {
+ // Found RangeSet, no need to check any further
+ using Type = RangeSet;
+};
+
+template <> struct IntersectionTraits<> {
+ // We ran out of types, and we didn't find any RangeSet, so the result should
+ // be optional.
+ using Type = Optional;
+};
+
+template
+struct IntersectionTraits {
+ // If current type is Optional or a raw pointer, we should keep looking.
+ using Type = typename IntersectionTraits::Type;
+};
+
+template
+LLVM_NODISCARD inline EndTy intersect(BasicValueFactory ,
+ RangeSet::Factory , EndTy End) {
+ // If the list contains only RangeSet or Optional, simply return
+ // that range set.
+ return End;
+}
+
+LLVM_NODISCARD LLVM_ATTRIBUTE_UNUSED inline Optional
+intersect(BasicValueFactory , RangeSet::Factory , const RangeSet *End) {
+ // This is an extraneous conversion from a raw pointer into Optional
+ if (End) {
+return *End;
+ }
+ return llvm::None;
+}
+
+template
+LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory ,
+ RangeSet::Factory , RangeSet Head,
+ RangeSet Second, RestTy... Tail) {
+ // Here we call either the or version
+ // of the function and can be sure that the result is RangeSet.
+ return intersect(BV, F, Head.Intersect(BV, F, Second), Tail...);
+}
+
+template
+LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory ,
+ RangeSet::Factory , RangeSet Head,
+ SecondTy Second, RestTy... Tail) {
+ if (Second) {
+// Here we call the version of the function...
+return intersect(BV, F, Head, *Second, Tail...);
+ }
+ // ...and here it is either or , which
+ // means that the result is definitely RangeSet.
+ return intersect(BV, F, Head, Tail...);
+}
+
+/// Main generic intersect function.
+/// It intersects all of the given range sets. If some of the given arguments
+/// don't hold a range set (nullptr or llvm::None), the function will skip them.
+///
+/// Available representations for the arguments are:
+/// * RangeSet
+/// * Optional
+/// * RangeSet *
+/// Pointer to a RangeSet is automatically assumed to be nullable and will get
+/// checked as well as the optional version. If this behaviour is undesired,
+/// please dereference the pointer in the call.
+///
+/// Return type depends on the arguments' types. If we can be sure in compile
+/// time that there will be a range set as a result, the returning type is
+/// simply RangeSet, in other cases we have to back off to Optional.
+///
+/// Please, prefer optional range sets to raw pointers. If the last argument is
+/// a raw pointer and all previous arguments are None, it will cost one
+/// additional check to convert RangeSet * into Optional.
+template
+LLVM_NODISCARD inline
+typename IntersectionTraits::Type
+intersect(BasicValueFactory , RangeSet::Factory , HeadTy Head,
+ SecondTy Second, RestTy... Tail) {
+ if (Head) {
+
[PATCH] D82381: [analyzer] Introduce small improvements to the solver infra
vsavchenko updated this revision to Diff 272724.
vsavchenko added a comment.
Fix comment
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D82381/new/
https://reviews.llvm.org/D82381
Files:
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===
--- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -89,7 +89,7 @@
}
TriStateKind getCmpOpState(BinaryOperatorKind CurrentOP,
- BinaryOperatorKind QueriedOP) const {
+ BinaryOperatorKind QueriedOP) const {
return CmpOpTable[getIndexFromOp(CurrentOP)][getIndexFromOp(QueriedOP)];
}
@@ -364,6 +364,18 @@
return newRanges;
}
+RangeSet RangeSet::Delete(BasicValueFactory , Factory ,
+ const llvm::APSInt ) const {
+ llvm::APSInt Upper = Point;
+ llvm::APSInt Lower = Point;
+
+ ++Upper;
+ --Lower;
+
+ // Notice that the lower bound is greater than the upper bound.
+ return Intersect(BV, F, Upper, Lower);
+}
+
void RangeSet::print(raw_ostream ) const {
bool isFirst = true;
os << "{ ";
@@ -381,6 +393,105 @@
namespace {
+//===--===//
+//Intersection functions
+//===--===//
+
+template
+LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory ,
+ RangeSet::Factory , RangeSet Head,
+ SecondTy Second, RestTy... Tail);
+
+template struct IntersectionTraits;
+
+template struct IntersectionTraits {
+ // Found RangeSet, no need to check any further
+ using Type = RangeSet;
+};
+
+template <> struct IntersectionTraits<> {
+ // We ran out of types, and we didn't find any RangeSet, so the result should
+ // be optional.
+ using Type = Optional;
+};
+
+template
+struct IntersectionTraits {
+ // If current type is Optional or a raw pointer, we should keep looking.
+ using Type = typename IntersectionTraits::Type;
+};
+
+template
+inline EndTy intersect(BasicValueFactory , RangeSet::Factory , EndTy End) {
+ // If the list contains only RangeSet or Optional, simply return
+ // that range set.
+ return End;
+}
+
+LLVM_NODISCARD LLVM_ATTRIBUTE_UNUSED inline Optional
+intersect(BasicValueFactory , RangeSet::Factory , const RangeSet *End) {
+ // This is an extraneous conversion from a raw pointer into Optional
+ if (End) {
+return *End;
+ }
+ return llvm::None;
+}
+
+template
+LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory ,
+ RangeSet::Factory , RangeSet Head,
+ RangeSet Second, RestTy... Tail) {
+ // Here we call either the or version
+ // of the function and can be sure that the result is RangeSet.
+ return intersect(BV, F, Head.Intersect(BV, F, Second), Tail...);
+}
+
+template
+LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory ,
+ RangeSet::Factory , RangeSet Head,
+ SecondTy Second, RestTy... Tail) {
+ if (Second) {
+// Here we call the version of the function...
+return intersect(BV, F, Head, *Second, Tail...);
+ }
+ // ...and here it is either or , which
+ // means that the result is definitely RangeSet.
+ return intersect(BV, F, Head, Tail...);
+}
+
+/// Main generic intersect function.
+/// It intersects all of the given range sets. If some of the given arguments
+/// don't hold a range set (nullptr or llvm::None), the function will skip them.
+///
+/// Available representations for the arguments are:
+/// * RangeSet
+/// * Optional
+/// * RangeSet *
+/// Pointer to a RangeSet is automatically assumed to be nullable and will get
+/// checked as well as the optional version. If this behaviour is undesired,
+/// please dereference the pointer in the call.
+///
+/// Return type depends on the arguments' types. If we can be sure in compile
+/// time that there will be a range set as a result, the returning type is
+/// simply RangeSet, in other cases we have to back off to Optional.
+///
+/// Please, prefer optional range sets to raw pointers. If the last argument is
+/// a raw pointer and all previous arguments are None, it will cost one
+/// additional check to convert RangeSet * into Optional.
+template
+inline typename IntersectionTraits::Type
+intersect(BasicValueFactory , RangeSet::Factory , HeadTy Head,
+ SecondTy Second, RestTy... Tail) {
+ if (Head) {
+return intersect(BV, F, *Head, Second, Tail...);
+ }
+ return intersect(BV, F, Second,
[PATCH] D82381: [analyzer] Introduce small improvements to the solver infra
vsavchenko updated this revision to Diff 272722.
vsavchenko added a comment.
Remove hunk that is meant for the next commmit
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D82381/new/
https://reviews.llvm.org/D82381
Files:
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===
--- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -89,7 +89,7 @@
}
TriStateKind getCmpOpState(BinaryOperatorKind CurrentOP,
- BinaryOperatorKind QueriedOP) const {
+ BinaryOperatorKind QueriedOP) const {
return CmpOpTable[getIndexFromOp(CurrentOP)][getIndexFromOp(QueriedOP)];
}
@@ -364,6 +364,18 @@
return newRanges;
}
+RangeSet RangeSet::Delete(BasicValueFactory , Factory ,
+ const llvm::APSInt ) const {
+ llvm::APSInt Upper = Point;
+ llvm::APSInt Lower = Point;
+
+ ++Upper;
+ --Lower;
+
+ // Notice that the lower bound is greater than the upper bound.
+ return Intersect(BV, F, Upper, Lower);
+}
+
void RangeSet::print(raw_ostream ) const {
bool isFirst = true;
os << "{ ";
@@ -381,6 +393,105 @@
namespace {
+//===--===//
+//Intersection functions
+//===--===//
+
+template
+LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory ,
+ RangeSet::Factory , RangeSet Head,
+ SecondTy Second, RestTy... Tail);
+
+template struct IntersectionTraits;
+
+template struct IntersectionTraits {
+ // Found RangeSet, no need to check any further
+ using Type = RangeSet;
+};
+
+template <> struct IntersectionTraits<> {
+ // We ran out of types, and we didn't find any RangeSet, so the result should
+ // be optional.
+ using Type = Optional;
+};
+
+template
+struct IntersectionTraits {
+ // If current type is Optional or a raw pointer, we should keep looking.
+ using Type = typename IntersectionTraits::Type;
+};
+
+template
+inline EndTy intersect(BasicValueFactory , RangeSet::Factory , EndTy End) {
+ // If the list contains only RangeSet or Optional, simply return
+ // that range set.
+ return End;
+}
+
+LLVM_NODISCARD LLVM_ATTRIBUTE_UNUSED inline Optional
+intersect(BasicValueFactory , RangeSet::Factory , const RangeSet *End) {
+ // This is an extraneous conversion from a raw pointer into Optional
+ if (End) {
+return *End;
+ }
+ return llvm::None;
+}
+
+template
+LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory ,
+ RangeSet::Factory , RangeSet Head,
+ RangeSet Second, RestTy... Tail) {
+ // Here we call either the or version
+ // of the function and can be sure that the result is RangeSet.
+ return intersect(BV, F, Head.Intersect(BV, F, Second), Tail...);
+}
+
+template
+LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory ,
+ RangeSet::Factory , RangeSet Head,
+ SecondTy Second, RestTy... Tail) {
+ if (Second) {
+// Here we call the version of the function...
+return intersect(BV, F, Head, *Second, Tail...);
+ }
+ // ...and here it is either or , which
+ // means that the result is definitely RangeSet.
+ return intersect(BV, F, Head, Tail...);
+}
+
+/// Main generic intersect function.
+/// It intersects all of the given range sets. If some of the given arguments
+/// don't hold a range set (nullptr or llvm::None), the function will skip them.
+///
+/// Available representations for the arguments are:
+/// * RangeSet
+/// * Optional
+/// * RangeSet *
+/// Pointer to a RangeSet is automatically assumed to be nullable and will get
+/// checked as well as the optional version. If this behaviour is undesired,
+/// please dereference the pointer in the call.
+///
+/// Return type depends on the arguments' types. If we can be sure in compile
+/// time that there will be a range set as a result, the returning type is
+/// simply RangeSet, in other cases we have to back off to Optional.
+///
+/// Please, prefer optional range sets to raw pointers. If the last argument is
+/// a raw pointer and all previous arguments are None, it will cost one
+/// additional check to convert RangeSet * into Optional.
+template
+inline typename IntersectionTraits::Type
+intersect(BasicValueFactory , RangeSet::Factory , HeadTy Head,
+ SecondTy Second, RestTy... Tail) {
+ if (Head) {
+return intersect(BV, F, *Head, Second, Tail...);
+ }
+
[PATCH] D82381: [analyzer] Introduce small improvements to the solver infra
vsavchenko created this revision.
vsavchenko added reviewers: NoQ, dcoughlin, ASDenysPetrov, xazax.hun, Szelethus.
Herald added subscribers: cfe-commits, martong, Charusso, dkrupp, donat.nagy,
mikhail.ramalho, a.sidorin, rnkovacs, szepet, baloghadamsoftware.
Herald added a project: clang.
- Add a new function to delete points from range sets.
- Introduce an internal generic interface for range set intersections.
- Remove unnecessary bits from a couple of solver functions.
- Add in-code sections.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D82381
Files:
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===
--- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -89,7 +89,7 @@
}
TriStateKind getCmpOpState(BinaryOperatorKind CurrentOP,
- BinaryOperatorKind QueriedOP) const {
+ BinaryOperatorKind QueriedOP) const {
return CmpOpTable[getIndexFromOp(CurrentOP)][getIndexFromOp(QueriedOP)];
}
@@ -364,6 +364,18 @@
return newRanges;
}
+RangeSet RangeSet::Delete(BasicValueFactory , Factory ,
+ const llvm::APSInt ) const {
+ llvm::APSInt Upper = Point;
+ llvm::APSInt Lower = Point;
+
+ ++Upper;
+ --Lower;
+
+ // Notice that the lower bound is greater than the upper bound.
+ return Intersect(BV, F, Upper, Lower);
+}
+
void RangeSet::print(raw_ostream ) const {
bool isFirst = true;
os << "{ ";
@@ -381,6 +393,105 @@
namespace {
+//===--===//
+//Intersection functions
+//===--===//
+
+template
+LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory ,
+ RangeSet::Factory , RangeSet Head,
+ SecondTy Second, RestTy... Tail);
+
+template struct IntersectionTraits;
+
+template struct IntersectionTraits {
+ // Found RangeSet, no need to check any further
+ using Type = RangeSet;
+};
+
+template <> struct IntersectionTraits<> {
+ // We ran out of types, and we didn't find any RangeSet, so the result should
+ // be optional.
+ using Type = Optional;
+};
+
+template
+struct IntersectionTraits {
+ // If current type is Optional or a raw pointer, we should keep looking.
+ using Type = typename IntersectionTraits::Type;
+};
+
+template
+inline EndTy intersect(BasicValueFactory , RangeSet::Factory , EndTy End) {
+ // If the list contains only RangeSet or Optional, simply return
+ // that range set.
+ return End;
+}
+
+LLVM_NODISCARD LLVM_ATTRIBUTE_UNUSED inline Optional
+intersect(BasicValueFactory , RangeSet::Factory , const RangeSet *End) {
+ // This is an extraneous conversion from a raw pointer into Optional
+ if (End) {
+return *End;
+ }
+ return llvm::None;
+}
+
+template
+LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory ,
+ RangeSet::Factory , RangeSet Head,
+ RangeSet Second, RestTy... Tail) {
+ // Here we call either the or version
+ // of the function and can be sure that the result is RangeSet.
+ return intersect(BV, F, Head.Intersect(BV, F, Second), Tail...);
+}
+
+template
+LLVM_NODISCARD inline RangeSet intersect(BasicValueFactory ,
+ RangeSet::Factory , RangeSet Head,
+ SecondTy Second, RestTy... Tail) {
+ if (Second) {
+// Here we call the version of the function...
+return intersect(BV, F, Head, *Second, Tail...);
+ }
+ // ...and here it is either or , which
+ // means that the result is definitely RangeSet.
+ return intersect(BV, F, Head, Tail...);
+}
+
+/// Main generic intersect function.
+/// It intersects all of the given range sets. If some of the given arguments
+/// don't hold a range set (nullptr or llvm::None), the function will skip them.
+///
+/// Available representations for the arguments are:
+/// * RangeSet
+/// * Optional
+/// * RangeSet *
+/// Pointer to a RangeSet is automatically assumed to be nullable and will get
+/// checked as well as the optional version. If this behaviour is undesired,
+/// please dereference the pointer in the call.
+///
+/// Return type depends on the arguments' types. If we can be sure in compile
+/// time that there will be a range set as a result, the returning type is
+/// simply RangeSet, in other cases we have to back off to Optional.
+///
+/// Please, prefer optional range sets to raw pointers. If the last argument is
+/// a raw pointer and all previous arguments are None, it
