On 8/10/20 2:46 PM, Martin Sebor wrote:
On 8/10/20 11:50 AM, Andrew MacLeod wrote:
On 8/10/20 12:35 PM, Martin Sebor via Gcc-patches wrote:
On 8/10/20 5:47 AM, Aldy Hernandez wrote:
On 8/6/20 9:30 PM, Martin Sebor wrote:
On 8/6/20 8:53 AM, Aldy Hernandez via Gcc-patches wrote:
+ // Remove the unknown parts of a multi-range.
+ // This will transform [5,10][20,MAX] into [5,10].
Is this comment correct? Wouldn't this result in returning smaller
sizes than the actual value allows? If so, I'd expect that to cause
false positives (and in that case, if none of our tests fail we need
to add some that would).
By my reading of the code below it seems to return the upper range
(i.e., [20, MAX]) but I'm not fully acquainted with the new ranger
APIs yet.
I believe the comment is correct. What I'm trying to do is remove
[X,TYPE_MAX_VALUE] from the range
+ int pairs = positives.num_pairs ();
+ if (pairs > 1
+ && positives.upper_bound () == wi::to_wide (TYPE_MAX_VALUE
(exptype)))
{
- if (integral)
- {
- /* Use the full range of the type of the expression when
- no value range information is available. */
- range[0] = TYPE_MIN_VALUE (exptype);
- range[1] = TYPE_MAX_VALUE (exptype);
- return true;
- }
-
- range[0] = NULL_TREE;
- range[1] = NULL_TREE;
- return false;
+ value_range last_range (exptype,
+ positives.lower_bound (pairs - 1),
+ positives.upper_bound (pairs - 1),
VR_ANTI_RANGE);
+ positives.intersect (last_range);
}
Notice that we start with positives == vr (where vr is the range
returned by determine_value_range).
Then we build last_range which is the *opposite* of
[X,TYPE_MAX_VALUE]. Notice the VR_ANTI_RANGE in the constructor.
(Note that the nomenclature VR_ANTI_RANGE is being used in the
constructor to keep with the original API. It means "create the
inverse of this range". Ideally, when the m_kind field disappears
along with VR_ANTI_RANGEs, the enum could become RANGE_INVERSE or
something less confusing.)
Finally, last_range is intersected with positives, which will
become whatever VR had, minus the last sub-range.
Those that make sense, or did I miss something?
If you have a testcase that yields a false positive in my proposed
patch, but not in the original code, please let me know so I can
adjust the patch.
Sorry, I misremembered what get_size_range was used for. It's used
to constrain the maximum size of memory accesses by functions like
memcpy (the third argument). The use case I was thinking of was
to determine the bounds of the size of variably modified objects
(like VLAs). It doesn't look like it's used for that.
With the current use taking the lower bound is the conservative
thing to do and using the upper bound would cause false positives.
With the latter it would be the other way around. So the comment
makes sense to me now.
As an aside, here's a test case I played with. I'd expect it to
trigger a warning because the upper bound of the range of array's
size is less than the lower bound of the range of the number of
bytes being written to it.
void f (void*);
void g (unsigned n1, unsigned n2)
{
if (!(n1 >= 2 && n1 <= 3)) // n1 = [2, 3]
return;
char a[n1];
if (!((n2 >= 5 && n2 <= 10)
|| (n2 >= 20))) // n2 = [5, 10] U [20, UINT_MAX]
return;
__builtin_memset (a, 0, n2);
f (a);
}
But I couldn't get it to either produce a multipart range, or
a union of the two parts (i.e., [5, UINT_MAX]). It makes me
wonder what I'm missing about how such ranges are supposed to
come into existence.
Martin
There mare a couple of things..
My guess is you are using a value_range? value_ranges are an
int_range<1> under the covers, so will never have more than a single
range, or anti range.
I see. Yes, get_size_range calls determine_value_range which uses
a value_range.
int_range<X> is the type which allows for up to X subranges.
calculations will be merged to fit within X subranges
widest_irange is the type which allows for "unlimited" subranges...
which currently happens to be capped at 255.. . (its typedef'd as
int_range<255>).
widest_irange is the type used within the range-ops machinery and
such, and then whatever result is calculated is "toned down" to
whatever to user provides.
so if union results in [5,10] and [20, MAX] and you provide a
value_range for the result (, or int_range<1>), the result you get
back will be [5, MAX].. so won't look like there are any multi-ranges
going on.
This is one part of the puzzle (for me). I don't get [5, MAX] but
[0, MAX], on trunk as well as in GCC 10:
void f (unsigned n)
{
if (!((n >= 5 && n <= 10)
|| (n >= 20))) // n2 = [5, 10] U [20, UINT_MAX]
return;
if (n == 3) // not folded
__builtin_abort ();
}
I'd expect this to get optimized regardless of Ranger (Clang folds
the whole function body into a return statement).
well, on our branch, with multirange, the rvrp pass does rewrite the
condition:
=========== BB 4 ============
n_5(D) unsigned int [5, 10][20, +INF]
<bb 4> :
if (0 != 0)
goto <bb 5>; [INV]
else
goto <bb 6>; [INV]
=========== BB 5 ============
<bb 5> :
__builtin_abort ();
=========== BB 6 ============
<bb 6> :
return;
EVRP doesn't get it because the code has been contorted into:
<bb 2> :
_1 = n_5(D) + 4294967291;
_2 = _1 > 5;
_3 = n_5(D) <= 19;
_4 = _2 & _3;
if (_4 != 0)
goto <bb 3>; [INV]
else
goto <bb 4>; [INV]
so without the multirange support, it sees:
Intersecting
unsigned int ~[5, 10]
and
unsigned int [0, 19]
to
unsigned int [0, 19]
so it cant tell that 3 isn't part of it any more since it has to be
pessimistic. I always find things like anti range and regular range
interactions "difficult".. I like multi range way better, and it sees
through those contortions just fine :-).
and don't forget, EVRP only works with value_range, or int_range<1>.
You cant currently get these ranges without the Ranger either...
which is still on our branch. We're hoping to get moving into trunk
in the next couple of weeks.
I think Aldy is just trying to get the code functioning the same with
the new API, even if we cant get the more precise ranges yet. Then
when the ranger is added in, we switch you over and voila...
multi-ranges.
Ah, this is the other part of what I was missing. I thought it
was already (or mostly) on trunk. It'll be fun (in a good way)
to start wiring the new muli-range classes into all these places.
I look forward to fixing the problems you will inevitably find :-P
Thanks
Martin
