On 12/1/20 1:57 PM, Martin Sebor wrote:
On 11/23/20 2:04 PM, Jeff Law wrote:
On 11/4/20 5:58 PM, Martin Sebor via Gcc-patches wrote:
To determine the target of a pointer expression and the offset into
it, the increasingly widely used compute_objsize function traverses
the IL following the DEF statements of pointer variables, aggregating
offsets from POINTER_PLUS assignments along the way. It does that
for many statements that involve pointers, including calls to
built-in functions and (so far only) accesses to char arrays. When
a function has many such statements with pointers to the same objects
but with different offsets, the traversal ends up visiting the same
pointer assignments repeatedly and unnecessarily.
To avoid this repeated traversal, the attached patch adds the ability
to cache results obtained in prior calls to the function. The cache
is optional and only used when enabled.
To exercise the cache I have enabled it for the strlen pass (which
is probably the heaviest compute_objsize user). That happens to
resolve PR 97373 which tracks the pass' failure to detect sprintf
overflowing allocated buffers at a non-constant offset. I thought
about making this a separate patch but the sprintf/strlen changes
are completely mechanical so it didn't seem worth the effort.
In the benchmarking I've done the cache isn't a huge win there but
it does have a measurable difference in the project I'm wrapping up
where most pointer assignments need to be examined. The space used
for the cache is negligible on average: fewer than 20 entries per
Glibc function and about 6 for GCC. The worst case in Glibc is
6 thousand entries and 10k in GCC. Since the entries are sizable
(216 bytes each) the worst case memory consumption can be reduced
by adding a level of indirection. A further savings can be obtained
by replacing some of the offset_int members of the entries with
HOST_WIDE_INT.
The efficiency benefits of the cache should increase further as more
of the access checking code is integrated into the same pass. This
should eventually include the checking currently done in the built-in
expanders.
Tested on x86_64-linux, along with Glibc and Binutils/GDB.
Martin
PS The patch add the new pointer_query class (loosely modeled on
range_query) to builtins.{h,c}. This should be only temporary,
until the access checking code is moved into a file (and ultimately
a pass) of its own.
gcc-97373.diff
PR middle-end/97373 - missing warning on sprintf into allocated
destination
gcc/ChangeLog:
PR middle-end/97373
* builtins.c (compute_objsize): Rename...
(compute_objsize_r): to this. Change order and types of arguments.
Use new argument. Adjust calls to self.
(access_ref::get_ref): New member function.
(pointer_query::pointer_query): New member function.
(pointer_query::get_ref): Same.
(pointer_query::put_ref): Same.
(handle_min_max_size): Change order and types of arguments.
(maybe_emit_free_warning): Add a test.
* builtins.h (class pointer_query): New class.
(compute_objsize): Declare an overload.
* gimple-ssa-sprintf.c (get_destination_size):
(handle_printf_call):
* tree-ssa-strlen.c (adjust_last_stmt): Add an argument and use it.
(maybe_warn_overflow): Same.
(handle_builtin_strcpy): Same.
(maybe_diag_stxncpy_trunc): Same.
(handle_builtin_memcpy): Change argument type. Adjust calls.
(handle_builtin_strcat): Same.
(handle_builtin_memset): Same.
(handle_store): Same.
(strlen_check_and_optimize_call): Same.
(check_and_optimize_stmt): Same.
(strlen_dom_walker): Add new data members.
(strlen_dom_walker::before_dom_children): Use new member.
(printf_strlen_execute): Dump cache performance counters.
* tree-ssa-strlen.h (maybe_diag_stxncpy_trunc): Add argument.
(handle_printf_call): Change argument type.
gcc/testsuite/ChangeLog:
PR middle-end/97373
* gcc.dg/warn-strnlen-no-nul.c:
* g++.dg/warn/Wmismatched-new-delete-2.C: New test.
* gcc.dg/tree-ssa/builtin-sprintf-warn-25.c: New test.
I'm going to hesitatingly ACK this.
Besides rebasing the changes on top the latest trunk I've also
adjusted them to avoid the "inefficient hacks" I mentioned in
the subsequent patch(*). They were not only inefficient but
also would have caused the function to return incorrect results
in some cases. After retesting with Binutils/GDB and Glibc
I committed the attached patch in r11-5622.
Martin
[*] https://gcc.gnu.org/pipermail/gcc-patches/2020-November/558775.html
The reason I saw hesitatingly is because I suspect that we're going to
see more cases where caching would be useful and I'd like to have a
general way to do that. We've already got a ton of caching code in
Ranger and I fully expect more as we continue to write analysis code
that wants to walk backwards. I don't want to see multiple
implementations of simple caching code.
I neglected to respond to this: if/when a general caching mechanism
becomes available I'll be happy to switch over to it. This is just
a couple of vectors to avoid the repetitive traversal of the use-def
chains that you have been objecting to, and make constant time
retrieval of the object sizes possible.
Additionally, if you're doing so many queries in a subsequent patch that
caching is needed, then that may be an indication that you're doing too
much work. I can't really evaluate that yet as I haven't looked at the
subsequent patch where this becomes a significant issue.
I also feel like I should address this comment, although I'd prefer
to have the discussion in a review of that patch.
The work that the subsequent patch does (and this one makes possible
to do more efficiently) is to determine the identities of objects
pointed to by pointers at the time of their assignment, as opposed
to the time of their use in expressions like ARRAY_REF, MEM_REF,
COMPONENT_REF, POINTER_PLUS, etc. The current approach on trunk
is inefficient when the same object is referenced many times by
distinct pointers (the common case), because each such reference
involves the traversal of the pointer's use-def chain to discover
what it points to.
Martin
So expect pushback if further cache implementations are introduced.
Jeff
