Re: [PATCH] improve caching and enhance array bounds checking
On 12/15/20 10:29 PM, Jeff Law wrote: On 11/11/20 6:09 PM, Martin Sebor via Gcc-patches wrote: The attached patch builds on top of the series I posted last week(*) to improve the detection of out of bounds pointers and C++ references, as well as a subset of invalid pointer relational and subtraction expressions. First, as I mentioned last week, the simple compute_objsize cache I implemented then is space inefficient. The changes in this update enhance the cache to reduce the space overhead and improve compile-time efficiency. The cache now consists of two arrays, one storing the indices to the other. The former is indexed by SSA_NAME version. The latter also contains separate entries for sizes of enclosing objects and their members (missing from the first attempt, leading to inefficient hacks to overcome the limitation). These improvements let clients look up the provenance of any pointer in O(1) time and avoid the hacks. Second, with the necessary cache improvements above, the gimple-array-bounds changes enhance array bounds checking in two ways: 1) pointers passed to functions or used to initialize C++ references are checked to see if they're valid and in bounds and diagnosed if not (a subset of instances of passing valid just-past-past-the-end and so non-dereferenceable pointers to functions are also diagnosed) 2) relational or difference expressions involving pointers are checked to make sure they point to the same object and diagnosed if not. Besides bootstrapping and regtesting I have also tested the full patch series with a few packages, including Binutils/GDB, Glibc and Valgrind, and verified that it doesn't cause any false positives. The new -Wpointer-compare warning does trigger in two or three places in each, for subtracting pointers to distinct objects. Those are true positives, but the code I checked looks benign. In such cases the warning can be suppressed by converting the pointers to intptr_t before the subtraction. Martin [*] Prerequisite patches: https://gcc.gnu.org/pipermail/gcc-patches/2020-November/558127.html https://gcc.gnu.org/pipermail/gcc-patches/2020-November/557807.html https://gcc.gnu.org/pipermail/gcc-patches/2020-November/557987.html gcc-wpointer-compare.diff Improve detection of invalid pointer operations. gcc/ChangeLog: PR middle-end/93848 * builtins.c (compute_objsize_r): Add argument. (access_ref::parm): New function. (access_ref::get_ref): Add argument. Avoid null pointers. Treat multiple PHIs with all arguments referencing the same object the same as references to that object with a range of offsets. Clear BASE0 for PHIs with arguments referencing distinct objects and different offsets. (access_ref::get_ref_type): New function. (access_ref::size_remaining): Make sure low bound of size is nonnegative. (pointer_query::pointer_query): Adjust ctor. (pointer_query::get_ref): Handle separate index and var caches. (pointer_query::put_ref): Same. (pointer_query::flush_cache): New function. (access_ref::inform_access): Differentiate pointers to allocated objects from those returned by non-allocation functions. (get_offset_range): Make extern. (handle_min_max_size): Add argument. Pass it to compute_objsize. (compute_objsize_r, compute_objsize): Same. (gimple_call_alloc_p): Make extern. (maybe_emit_free_warning): Adjust and simplify test for built-in functions. * builtins.h (struct access_ref): Add new members, adjust existing. (get_offset_range): Declare. (gimple_call_alloc_p): Same. (compute_objsize): Add argument. * common.opt (-Wpointer-compare): Move option here from gcc/c.opt. * doc/invoke.texi (-Wpointer-compare): Update. * gimple-array-bounds.cc (ptrrefs): New variable. (format_offset_range): New function. (format_subscript_range): New function. (array_bounds_checker::check_array_ref): Remove argument. (array_bounds_checker::check_mem_ref): Remove argument. Check no-warning bit on the current statement. Use format_subscript_range. Simplify informational messages. (array_bounds_checker::check_addr_expr): Remove redundant argument from calls. (array_bounds_checker::ptrs_to_distinct): New function. (array_bounds_checker::check_pointer_op): Same. (array_bounds_checker::handle_assign): Same. (array_bounds_checker::handle_call): Same. (array_bounds_checker::check_array_bounds): Set new array_bounds_checker members. Adjust calls. (check_array_bounds_dom_walker::before_dom_children): Call new array_bounds_checker members. Set statement visited bit. (array_bounds_checker::check): Create and a pointer_query instance and flush its cache. * gimple-array-bounds.h (class
Re: [PATCH] improve caching and enhance array bounds checking
On 11/11/20 6:09 PM, Martin Sebor via Gcc-patches wrote: > The attached patch builds on top of the series I posted last > week(*) to improve the detection of out of bounds pointers > and C++ references, as well as a subset of invalid pointer > relational and subtraction expressions. > > First, as I mentioned last week, the simple compute_objsize > cache I implemented then is space inefficient. The changes > in this update enhance the cache to reduce the space overhead > and improve compile-time efficiency. The cache now consists > of two arrays, one storing the indices to the other. > The former is indexed by SSA_NAME version. The latter also > contains separate entries for sizes of enclosing objects and > their members (missing from the first attempt, leading to > inefficient hacks to overcome the limitation). These > improvements let clients look up the provenance of any pointer > in O(1) time and avoid the hacks. > > Second, with the necessary cache improvements above, > the gimple-array-bounds changes enhance array bounds checking > in two ways: > 1) pointers passed to functions or used to initialize C++ > references are checked to see if they're valid and in bounds > and diagnosed if not (a subset of instances of passing valid > just-past-past-the-end and so non-dereferenceable pointers to > functions are also diagnosed) > 2) relational or difference expressions involving pointers are > checked to make sure they point to the same object and diagnosed > if not. > > Besides bootstrapping and regtesting I have also tested the full > patch series with a few packages, including Binutils/GDB, Glibc > and Valgrind, and verified that it doesn't cause any false > positives. The new -Wpointer-compare warning does trigger in > two or three places in each, for subtracting pointers to distinct > objects. Those are true positives, but the code I checked looks > benign. In such cases the warning can be suppressed by converting > the pointers to intptr_t before the subtraction. > > Martin > > [*] Prerequisite patches: > https://gcc.gnu.org/pipermail/gcc-patches/2020-November/558127.html > https://gcc.gnu.org/pipermail/gcc-patches/2020-November/557807.html > https://gcc.gnu.org/pipermail/gcc-patches/2020-November/557987.html > > gcc-wpointer-compare.diff > > Improve detection of invalid pointer operations. > > gcc/ChangeLog: > > PR middle-end/93848 > * builtins.c (compute_objsize_r): Add argument. > (access_ref::parm): New function. > (access_ref::get_ref): Add argument. Avoid null pointers. Treat > multiple PHIs with all arguments referencing the same object the same > as references to that object with a range of offsets. Clear BASE0 > for PHIs with arguments referencing distinct objects and different > offsets. > (access_ref::get_ref_type): New function. > (access_ref::size_remaining): Make sure low bound of size is > nonnegative. > (pointer_query::pointer_query): Adjust ctor. > (pointer_query::get_ref): Handle separate index and var caches. > (pointer_query::put_ref): Same. > (pointer_query::flush_cache): New function. > (access_ref::inform_access): Differentiate pointers to allocated > objects from those returned by non-allocation functions. > (get_offset_range): Make extern. > (handle_min_max_size): Add argument. Pass it to compute_objsize. > (compute_objsize_r, compute_objsize): Same. > (gimple_call_alloc_p): Make extern. > (maybe_emit_free_warning): Adjust and simplify test for built-in > functions. > * builtins.h (struct access_ref): Add new members, adjust existing. > (get_offset_range): Declare. > (gimple_call_alloc_p): Same. > (compute_objsize): Add argument. > * common.opt (-Wpointer-compare): Move option here from gcc/c.opt. > * doc/invoke.texi (-Wpointer-compare): Update. > * gimple-array-bounds.cc (ptrrefs): New variable. > (format_offset_range): New function. > (format_subscript_range): New function. > (array_bounds_checker::check_array_ref): Remove argument. > (array_bounds_checker::check_mem_ref): Remove argument. Check > no-warning bit on the current statement. Use format_subscript_range. > Simplify informational messages. > (array_bounds_checker::check_addr_expr): Remove redundant argument > from calls. > (array_bounds_checker::ptrs_to_distinct): New function. > (array_bounds_checker::check_pointer_op): Same. > (array_bounds_checker::handle_assign): Same. > (array_bounds_checker::handle_call): Same. > (array_bounds_checker::check_array_bounds): Set new > array_bounds_checker members. Adjust calls. > (check_array_bounds_dom_walker::before_dom_children): Call new > array_bounds_checker members. Set statement visited bit. > (array_bounds_checker::check): Create and a pointer_query instance > and flu