What is RangeSet::Negate idea

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

What is RangeSet::Negate idea

Fangrui Song via cfe-dev

Hi, community.


Who can explain the main idea of RangeSet::Negate? And how does RangeSet ​work?


As I understand RangeSet may hold several constraint ranges (e.g. [MIN,10] U [20,30] U [40,MAX]) or may be empty (no constraints, in other words, holds everything [MIN, MAX]),

when MIN and MAX are kinda numeric_limits<type which corresponds to particular SymExpr>::min/max().

Am I correct? If I am not, please explain.



Denys Petrov
Senior С++ Developer | Kharkiv, Ukraine


_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

[analyzer] What is RangeSet::Negate idea

Fangrui Song via cfe-dev

Hi, community.


Who can explain the main idea of RangeSet::Negate? And how does RangeSet ​work?


As I understand RangeSet may hold several constraint ranges (e.g. [MIN,10] U [20,30] U [40,MAX]) or may be empty (no constraints, in other words, holds everything [MIN, MAX]),

when MIN and MAX are kinda numeric_limits<type which corresponds to particular SymExpr>::min/max().

Am I correct? If I am not, please explain.


P.S. fixed wrong subject format.



Denys Petrov
Senior С++ Developer | Kharkiv, Ukraine


_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] What is RangeSet::Negate idea

Fangrui Song via cfe-dev
Yup, and Negate() flips this sequence of segments around zero, i.e.
[/a/, /b]/ U [/c/, /d/] => [-/d/, -/c/] U [-/b/, -/a/]. In other words,
if R is the range for $x, then R.Negate() is the range for -x.

Negate() also handles MIN differently because -MIN is unrepresentable
for most integer types.

On 4/6/20 6:22 PM, Denis Petrov via cfe-dev wrote:

>
> Hi, community.
>
>
> Who can explain the main idea of *RangeSet::Negate*? And how does
> *RangeSet*​work?
>
>
> As I understand *RangeSet* may hold several constraint ranges
> /(e.g. [MIN,10] U [20,30] U [40,MAX])/ or may be empty /(no
> constraints, in other words, holds everything [MIN, MAX])/,
>
> when MIN and MAX are kinda *numeric**_limits<*/type //which
> corresponds to particular SymExpr​/*>::min/max()*.
>
> Am I correct? If I am not, please explain.
>
>
> P.S. fixed wrong subject format.
>
>
> ------------------------------------------------------------------------
> *Denys Petrov*
> Senior С++ Developer | Kharkiv, Ukraine
>
>
> _______________________________________________
> cfe-dev mailing list
> [hidden email]
> https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev

_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] What is RangeSet::Negate idea

Fangrui Song via cfe-dev
*re-adds cfe-dev*

Mmm, dunno what you mean. Like, it's the range for the negated symbol.
It should be applied by the constraint manager (our wannabe SAT solver)
when it wants to obtain the range for the negated symbol when it already
has the range for the original symbol.

Would it help you if you see how it's used on tests? Eg., you can inject
a crash in this function and see which tests fail; this will help you
gather some examples of how the function is used. Then you can look
under the debugger to see how exactly does it get used.

On 4/7/20 2:08 AM, Denis Petrov wrote:
> OK, thanks, I think I got it.
>
> Digging a bit more I came up with a special case of -MIN and handling of unsigned ranges. For me it's just a simple classic C unary minus operation. (And actually there is no special case for-MIN, it's just how native unary minus works)
>
> But what is a physical sense of Negate? When it should be applied and what for?
>
> ________________________________
> Denys Petrov
> Senior С++ Developer | Kharkiv, Ukraine

_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev