On 10/9/20 9:13 AM, Jason Merrill wrote:
On 10/9/20 10:51 AM, Martin Sebor wrote:
On 10/8/20 1:40 PM, Jason Merrill wrote:
On 10/8/20 3:18 PM, Martin Sebor wrote:
On 10/7/20 3:01 PM, Jason Merrill wrote:
On 10/7/20 4:11 PM, Martin Sebor wrote:
...
For the various member functions, please include the
comments with the definition as well as the in-class
declaration.
Only one access_ref member function is defined out-of-line:
offset_bounded(). I've adjusted the comment and copied it
above
the function definition.
And size_remaining, as quoted above?
I have this in my tree:
/* Return the maximum amount of space remaining and if non-null, set
argument to the minimum. */
I'll add it when I commit the patch.
I also don't see a comment above the definition of offset_bounded
in the new patch?
There is a comment in the latest patch.
...
The goal of conditionals is to avoid overwhelming the user with
excessive numbers that may not be meaningful or even relevant
to the warning. I've corrected the function body, tweaked and
renamed the get_range function to get_offset_range to do a
better
job of extracting ranges from the types of some nonconstant
expressions the front end passes it, and added a new test for
all this. Attached is the new revision.
offset_bounded looks unchanged in the new patch. It still returns
true iff either the range is a single value or one of the bounds
are unrepresentable in ptrdiff_t. I'm still unclear how this
corresponds to "Return true if OFFRNG is bounded to a subrange of
possible offset values."
I don't think you're looking at the latest patch. It has this:
+/* Return true if OFFRNG is bounded to a subrange of offset values
+ valid for the largest possible object. */
+
bool
access_ref::offset_bounded () const
{
- if (offrng[0] == offrng[1])
- return false;
-
tree min = TYPE_MIN_VALUE (ptrdiff_type_node);
tree max = TYPE_MAX_VALUE (ptrdiff_type_node);
- return offrng[0] <= wi::to_offset (min) || offrng[1] >=
wi::to_offset (max);
+ return wi::to_offset (min) <= offrng[0] && offrng[1] <=
wi::to_offset (max);
}
Here's a link to it in the archive:
https://gcc.gnu.org/pipermail/gcc-patches/2020-September/555019.html
https://gcc.gnu.org/pipermail/gcc-patches/attachments/20200928/9026783a/attachment-0003.bin
Ah, yes, there are two patches in that email; the first introduces
the broken offset_bounded, and the second one fixes it without
mentioning that in the ChangeLog. How about moving the fix to the
first patch?
Sure, I can do that. Anything else or is the final version okay
to commit with this adjustment?
OK with that adjustment.
I've done more testing and found a bug in the second patch: adding
an offset in an inverted range to an existing offset range isn't as
simple as adding up the bounds because they mean different things:
like an anti-range, an inverted range is a union of two subranges.
Instead, the upper bound needs to be extended to PTRDIFF_MAX because
that is the maximum being added, and the lower bound either reset to
zero if the absolute value of the maximum being added is less than
it, or incremented by the absolute value otherwise.
For example, given:
char a[8];
char *pa = a;
char *p1 = pa + i; // i's range is [3, 5]
char *p2 = p1 + j; // j's range is [1, -4]
the range of p2's offset isn't [4, 1] but [4, PTRDIFF_MAX] (or more
precisely [4, 8] if we assume it's valid). But the range of p3's
valid offset in this last pointer
char *p3 = p2 + k; // k's range is [5, -4]
is all of [0, PTRDIFF_MAX] (or, more accurately, [0, 8]).
This may seem obvious but it took me a while at first to wrap my head
around.
I've tweaked access_ref::add_offset in the patch to handle this
correctly. The function now ensures that every offset is in
a regular range (and not an inverted one). That in turn simplifies
access_ref::size_remaining. Since an inverted range is the same as
an anti-range, there's no reason to exclude the latter anymore(*).
The diff on top of the approved patch is attached.
I've retested this new revision of the patch with Glibc and GDB/
Binutils, (the latter fails due to PR 97360), and the Linux kernel.
Please let me know if you have any questions or concerns with
this change. If not, I'd like to commit it sometime tomorrow.
Martin
[*] I was curious how often these inverted ranges/anti-ranges come
up in pointer arithmetic to see if handling them is worthwhile. I
instrumented GCC to print them in get_range() on master where they
are only looked at in calls to built-in functions, and in another
patch I'm working on where they are looked at for every pointer
addition. They account for 16% to 23% (GCC and Glibc, respectively)
and 22% to 32% (Glibc and GCC). The detailed results are below.
GCC
Builtin pointer arithmetic:
kind ordinary inverted
RANGE 636 (38%) 150 ( 9%)
ANTI_RANGE 28 ( 1%) 99 ( 6%)
VARYING 733 (44%)
total 1397 (84%) 249 (15%)
All pointer arithmetic:
kind ordinary inverted
RANGE 4663 (45%) 2945 (28%)
ANTI_RANGE 134 ( 1%) 119 ( 1%)
VARYING 2344 (22%)
total 7141 (69%) 3064 (30%)
Glibc
Builtin pointer arithmetic:
kind ordinary inverted
RANGE 488 (37%) 191 (14%)
ANTI_RANGE 18 ( 1%) 112 ( 8%)
VARYING 509 (38%)
total 1015 (77%) 303 (22%)
All pointer arithmetic:
kind ordinary inverted
RANGE 1941 (51%) 636 (16%)
ANTI_RANGE 41 ( 1%) 202 ( 5%)
VARYING 952 (25%)
total 2934 (77%) 838 (22%)
diff --git a/gcc/builtins.c b/gcc/builtins.c
index 5c8cdc3add7..e6649ddc76f 100644
--- a/gcc/builtins.c
+++ b/gcc/builtins.c
@@ -231,20 +231,11 @@ access_ref::size_remaining (offset_int *pmin /* = NULL */) const
if (!pmin)
pmin = &minbuf;
+ /* add_offset() ensures the offset range isn't inverted. */
+ gcc_checking_assert (offrng[0] <= offrng[1]);
+
if (base0)
{
- if (offrng[1] < offrng[0])
- {
- if (offrng[1] < 0)
- {
- *pmin = 0;
- return offrng[0] < sizrng[1] ? sizrng[1] - offrng[0] : 0;
- }
-
- *pmin = offrng[0] < sizrng[1] ? sizrng[1] - offrng[0] : 0;
- return sizrng[1];
- }
-
/* The offset into referenced object is zero-based (i.e., it's
not referenced by a pointer into middle of some unknown object). */
if (offrng[0] < 0 && offrng[1] < 0)
@@ -256,9 +247,11 @@ access_ref::size_remaining (offset_int *pmin /* = NULL */) const
if (sizrng[1] <= offrng[0])
{
- /* If the starting offset is greater than the upper bound on
- the size of the object the space remaining is zero. */
- *pmin = 0;
+ /* If the starting offset is greater than or equal to the upper
+ bound on the size of the object, the space remaining is zero.
+ As a special case, if it's equal, set *PMIN to -1 to let
+ the caller know the offset is valid and just past the end. */
+ *pmin = sizrng[1] == offrng[0] ? -1 : 0;
return 0;
}
@@ -273,22 +266,6 @@ access_ref::size_remaining (offset_int *pmin /* = NULL */) const
refer to a byte other than the first. The size of such an object
is constrained only by the size of the address space (the result
of max_object_size()). */
- if (offrng[1] < offrng[0])
- {
- if (offrng[1] < 0)
- {
- *pmin = sizrng[0];
- return sizrng[1];
- }
-
- if (offrng[0] < sizrng[1])
- *pmin = offrng[0] < 0 ? sizrng[1] : sizrng[1] - offrng[0];
- else
- *pmin = 0;
-
- return sizrng[1];
- }
-
if (sizrng[1] <= offrng[0])
{
*pmin = 0;
@@ -301,6 +278,71 @@ access_ref::size_remaining (offset_int *pmin /* = NULL */) const
return sizrng[1] - or0;
}
+/* Add the range [MIN, MAX] to the offset range. For known objects (with
+ zero-based offsets) at least one of whose offset's bounds is in range,
+ constrain the other (or both) to the bounds of the object (i.e., zero
+ and the upper bound of its size). This improves the quality of
+ diagnostics. */
+
+void access_ref::add_offset (const offset_int &min, const offset_int &max)
+{
+ if (min <= max)
+ {
+ /* To add an ordinary range just add it to the bounds. */
+ offrng[0] += min;
+ offrng[1] += max;
+ }
+ else if (!base0)
+ {
+ /* To add an inverted range to an offset to an unknown object
+ expand it to the maximum. */
+ add_max_offset ();
+ return;
+ }
+ else
+ {
+ /* To add an inverted range to an offset to an known object set
+ the upper bound to the maximum representable offset value
+ (which may be greater than MAX_OBJECT_SIZE).
+ The lower bound is either the sum of the current offset and
+ MIN when abs(MAX) is greater than the former, or zero otherwise.
+ Zero because then then inverted range includes the negative of
+ the lower bound. */
+ offset_int maxoff = wi::to_offset (TYPE_MAX_VALUE (ptrdiff_type_node));
+ offrng[1] = maxoff;
+
+ if (max >= 0)
+ {
+ offrng[0] = 0;
+ return;
+ }
+
+ offrng[1] = maxoff;
+ offset_int absmax = wi::abs (max);
+ if (offrng[0] < absmax)
+ offrng[0] += min;
+ else
+ offrng[0] = 0;
+ }
+
+ if (!base0)
+ return;
+
+ /* When referencing a known object check to see if the offset computed
+ so far is in bounds... */
+ offset_int remrng[2];
+ remrng[1] = size_remaining (remrng);
+ if (remrng[1] > 0 || remrng[0] < 0)
+ {
+ /* ...if so, constrain it so that neither bound exceeds the size of
+ the object. */
+ if (offrng[0] < 0)
+ offrng[0] = 0;
+ if (offrng[1] > sizrng[1])
+ offrng[1] = sizrng[1];
+ }
+}
+
/* Return true if NAME starts with __builtin_ or __sync_. */
static bool
@@ -4728,7 +4785,8 @@ compute_objsize (tree ptr, int ostype, access_ref *pref, bitmap *visited,
tree off = pref->eval (TREE_OPERAND (ptr, 1));
if (!get_offset_range (off, NULL, orng, rvals))
{
- orng[1] = wi::to_offset (max_object_size ());
+ /* Set ORNG to the maximum offset representable in ptrdiff_t. */
+ orng[1] = wi::to_offset (TYPE_MAX_VALUE (ptrdiff_type_node));
orng[0] = -orng[1] - 1;
}
@@ -4779,9 +4837,7 @@ compute_objsize (tree ptr, int ostype, access_ref *pref, bitmap *visited,
}
}
- pref->offrng[0] += orng[0];
- pref->offrng[1] += orng[1];
-
+ pref->add_offset (orng[0], orng[1]);
return true;
}
@@ -4941,19 +4997,17 @@ compute_objsize (tree ptr, int ostype, access_ref *pref, bitmap *visited,
if (code == POINTER_PLUS_EXPR
&& TREE_CODE (TREE_TYPE (ptr)) == POINTER_TYPE)
{
- /* If the the offset in the expression can be determined use
- it to adjust the overall offset. Otherwise, set the overall
- offset to the maximum. */
+ /* Compute the size of the object first. */
+ if (!compute_objsize (ptr, ostype, pref, visited, rvals))
+ return false;
+
offset_int orng[2];
tree off = gimple_assign_rhs2 (stmt);
- if (!get_offset_range (off, stmt, orng, rvals))
- {
- orng[0] = -wi::to_offset (max_object_size ()) - 1;
- orng[1] = wi::to_offset (max_object_size ());
- }
-
- pref->add_offset (orng[0], orng[1]);
- return compute_objsize (ptr, ostype, pref, visited, rvals);
+ if (get_offset_range (off, stmt, orng, rvals))
+ pref->add_offset (orng[0], orng[1]);
+ else
+ pref->add_max_offset ();
+ return true;
}
if (code == ADDR_EXPR)
diff --git a/gcc/builtins.h b/gcc/builtins.h
index d07d79ebd1a..c09f36da02b 100644
--- a/gcc/builtins.h
+++ b/gcc/builtins.h
@@ -198,22 +198,17 @@ struct access_ref
/* Add OFF to the offset range. */
void add_offset (const offset_int &off)
{
- offrng[0] += off;
- offrng[1] += off;
+ add_offset (off, off);
}
/* Add the range [MIN, MAX] to the offset range. */
- void add_offset (const offset_int &min, const offset_int &max)
- {
- offrng[0] += min;
- offrng[1] += max;
- }
+ void add_offset (const offset_int &, const offset_int &);
- /* Add the maximum valid offset to the offset range. */
+ /* Add the maximum representable offset to the offset range. */
void add_max_offset ()
{
- offrng[0] -= wi::to_offset (max_object_size ()) + 1;
- offrng[1] += wi::to_offset (max_object_size ());
+ offset_int maxoff = wi::to_offset (TYPE_MAX_VALUE (ptrdiff_type_node));
+ add_offset (-maxoff - 1, maxoff);
}
/* Used to fold integer expressions when called from front ends. */
@@ -249,9 +244,8 @@ struct access_data
class range_query;
extern tree gimple_call_alloc_size (gimple *, wide_int[2] = NULL,
- range_query * = NULL);
-extern tree gimple_parm_array_size (tree, wide_int[2],
range_query * = NULL);
+extern tree gimple_parm_array_size (tree, wide_int[2], range_query * = NULL);
extern tree compute_objsize (tree, int, access_ref *, range_query * = NULL);
extern tree compute_objsize (tree, int, tree * = NULL, tree * = NULL,
range_query * = NULL);
diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c
index f4d1c5ca256..ebb17cd852c 100644
--- a/gcc/tree-ssa-strlen.c
+++ b/gcc/tree-ssa-strlen.c
@@ -228,8 +228,20 @@ get_range (tree val, gimple *stmt, wide_int minmax[2],
value_range_kind rng = get_range_info (val, minmax, minmax + 1);
if (rng == VR_RANGE)
+ /* This may be an inverted range whose MINMAX[1] < MINMAX[0]. */
return val;
+ if (rng == VR_ANTI_RANGE)
+ {
+ /* An anti-range is the same as an ordinary range with inverted
+ bounds (where MINMAX[1] < MINMAX[0] is true) that may result
+ from the conversion of a signed anti-range to unsigned. */
+ wide_int tmp = minmax[0];
+ minmax[0] = minmax[1] + 1;
+ minmax[1] = wi::sub (tmp, 1);
+ return val;
+ }
+
/* Do not handle anti-ranges and instead make use of the on-demand
VRP if/when it becomes available (hopefully in GCC 11). */
return NULL_TREE;
