diff mbox series

cache compute_objsize results in strlen/sprintf (PR 97373)

Message ID 34f3587a-7c93-804e-639a-da37a1ef50ab@gmail.com
State New
Headers show
Series cache compute_objsize results in strlen/sprintf (PR 97373) | expand

Commit Message

Martin Sebor Nov. 5, 2020, 12:58 a.m. UTC 
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.

Comments

Richard Biener Nov. 5, 2020, 7:31 a.m. UTC | #1 
On Thu, Nov 5, 2020 at 1:59 AM Martin Sebor via Gcc-patches
<gcc-patches@gcc.gnu.org> 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.

I'm quite sure the objsz pass already has a cache, why not
re-use it instead of piggy-backing another one onto its machinery?

Richard.

> 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.
Martin Sebor Nov. 5, 2020, 3:20 p.m. UTC | #2 
On 11/5/20 12:31 AM, Richard Biener wrote:
> On Thu, Nov 5, 2020 at 1:59 AM Martin Sebor via Gcc-patches
> <gcc-patches@gcc.gnu.org> 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.
> 
> I'm quite sure the objsz pass already has a cache, why not
> re-use it instead of piggy-backing another one onto its machinery?

compute_objsize() and the objsz pass are completely independent.
The pass is also quite limited in that it doesn't make use of
ranges.  That limitation was also the main reason for introducing
the compute_objsize() function.

I'd love to see the objsize pass and compute_objsize() integrated
and exposed under an interface similar to range_query, with
the information available anywhere, and on demand.  I might tackle
it some day, but I expect it will be a nontrivial project, much
bigger than letting compute_objsize() do this simple caching for
the time being.

Martin

> 
> Richard.
> 
>> 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.
Jakub Jelinek Nov. 5, 2020, 3:29 p.m. UTC | #3 
On Thu, Nov 05, 2020 at 08:20:20AM -0700, Martin Sebor via Gcc-patches wrote:
> compute_objsize() and the objsz pass are completely independent.
> The pass is also quite limited in that it doesn't make use of
> ranges.  That limitation was also the main reason for introducing
> the compute_objsize() function.
> 
> I'd love to see the objsize pass and compute_objsize() integrated
> and exposed under an interface similar to range_query, with
> the information available anywhere, and on demand.  I might tackle

As I said multiple times, that would be a serious security hazard.
_FORTIFY_SOURCE protects against some UBs in the programs, and ranges
are computed on the assumption that UB doesn't happen in the program,
so relying on the ranges etc. in there is highly undesirable.

	Jakub
Martin Sebor Nov. 5, 2020, 4:23 p.m. UTC | #4 
On 11/5/20 8:29 AM, Jakub Jelinek wrote:
> On Thu, Nov 05, 2020 at 08:20:20AM -0700, Martin Sebor via Gcc-patches wrote:
>> compute_objsize() and the objsz pass are completely independent.
>> The pass is also quite limited in that it doesn't make use of
>> ranges.  That limitation was also the main reason for introducing
>> the compute_objsize() function.
>>
>> I'd love to see the objsize pass and compute_objsize() integrated
>> and exposed under an interface similar to range_query, with
>> the information available anywhere, and on demand.  I might tackle
> 
> As I said multiple times, that would be a serious security hazard.
> _FORTIFY_SOURCE protects against some UBs in the programs, and ranges
> are computed on the assumption that UB doesn't happen in the program,
> so relying on the ranges etc. in there is highly undesirable.

As I think has been pointed out as many times in response, failing
to handle ranges in _FORTIFY_SOURCE, or any expressions that can't
be evaluated at compile time for that matter, is the security gap.
It means that the vast majority of allocated objects (by malloc,
alloca, or VLAs) are unprotected, as are accesses into fixed-size
objects involving nonconstant offsets.

It's only thanks to compute_objsize() GCC diagnoses (but doesn't
prevent) a small subset of buffer overflows involving such accesses
but only those where the lower bound of the access exceeds the upper
bound of the size.  It's powerless against those where the overflow
is due to the size of the access exceeding just the lower bound of
the object size but not the upper bound.

This serious _FORTIFY_SOURCE shortcoming was recognized by the Clang
developers and rectified by introducing __builtin_dynamic_object_size.

Martin
Jeff Law Nov. 23, 2020, 9:04 p.m. UTC | #5 
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. 

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.

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.

So expect pushback if further cache implementations are introduced.

Jeff
Martin Sebor Dec. 1, 2020, 8:57 p.m. UTC | #6 
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.
> 
> 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.
> 
> So expect pushback if further cache implementations are introduced.
> 
> Jeff
>
Martin Sebor Dec. 1, 2020, 9:21 p.m. UTC | #7 
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
>>
>
Jeff Law Dec. 1, 2020, 11:38 p.m. UTC | #8 
On 12/1/20 2:21 PM, Martin Sebor wrote:
> 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.
Understood.  What I'm trying to avoid is having a variety of bespoke
caching implementations for on-demand optimization/analysis phases.  I
can easily see that scenario creeping up on us.

>
>>>
>>> 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.
Understood.

Jeff
diff mbox series

Patch

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.

diff --git a/gcc/builtins.c b/gcc/builtins.c
index 1b8a5b82dac..d79dab05671 100644
--- a/gcc/builtins.c
+++ b/gcc/builtins.c
@@ -185,7 +185,7 @@  static void maybe_emit_chk_warning (tree, enum built_in_function);
 static void maybe_emit_sprintf_chk_warning (tree, enum built_in_function);
 static tree fold_builtin_object_size (tree, tree);
 static bool check_read_access (tree, tree, tree = NULL_TREE, int = 1);
-static bool compute_objsize (tree, int, access_ref *, bitmap *, range_query *);
+static bool compute_objsize_r (tree, access_ref *, pointer_query *, bitmap *);
 
 unsigned HOST_WIDE_INT target_newline;
 unsigned HOST_WIDE_INT target_percent;
@@ -241,15 +241,14 @@  access_ref::phi () const
 
 /* Determine and return the largest object to which REF refers.  If REF
    refers to a PHI and PREF is nonnull, fill *PREF with the details of
-   the object determined by compute_objsize(ARG, OSTYPE) for each PHI
-   argument ARG.  */
+   the object determined by compute_objsize(ARG, ...) for each PHI argument
+   ARG.  */
 
 tree
 access_ref::get_ref (vec<access_ref> *all_refs,
 		     access_ref *pref /* = NULL */,
-		     int ostype /* = 1 */,
-		     bitmap *visited /* = NULL */,
-		     range_query *rvals /* = NULL */) const
+		     pointer_query *qry /* = NULL */,
+		     bitmap *visited /* = NULL */) const
 {
   gphi *phi_stmt = this->phi ();
   if (!phi_stmt)
@@ -266,6 +265,10 @@  access_ref::get_ref (vec<access_ref> *all_refs,
     /* Have compute_objsize() fail and propagate the failure below.  */
     return NULL_TREE;
 
+  pointer_query empty_qry;
+  if (!qry)
+    qry = &empty_qry;
+
   access_ref phi_ref;
   if (pref)
     phi_ref = *pref;
@@ -283,15 +286,17 @@  access_ref::get_ref (vec<access_ref> *all_refs,
     {
       access_ref phi_arg_ref;
       tree arg = gimple_phi_arg_def (phi_stmt, i);
-      if (!compute_objsize (arg, ostype, &phi_arg_ref, visited, rvals))
+      if (!compute_objsize_r (arg, &phi_arg_ref, qry, visited))
 	return NULL_TREE;
 
-      /* The call to compute_objsize() above will fail when the ARG has
-	 already been VISITED.  */
+      /* The call to compute_objsize_r() above will fail when the ARG
+	 has already been VISITED.  */
       gcc_checking_assert (phi_arg_ref.sizrng[0] >= 0);
 
       /* Add PREF's offset to that of the argument.  */
       phi_arg_ref.add_offset (orng[0], orng[1]);
+      if (TREE_CODE (arg) == SSA_NAME)
+	qry->put_ref (arg, phi_arg_ref);
 
       if (all_refs)
 	all_refs->safe_push (phi_arg_ref);
@@ -479,6 +484,103 @@  void access_ref::add_offset (const offset_int &min, const offset_int &max)
     }
 }
 
+/* Default ctor.  Initialize object with pointers to the range_query
+   and cache_type instances to use or null.  */
+
+pointer_query::pointer_query (range_query *qry /* = NULL */,
+			      cache_type *cache /* = NULL */)
+: rvals (qry), var_cache (cache), ostype (1), hits (), misses (),
+  failures (), depth (), max_depth ()
+{
+  /* No op.  */
+}
+
+/* Return a pointer to the cached access_ref instance for the SSA_NAME
+   PTR if it's there or null otherwise.  */
+
+const access_ref *
+pointer_query::get_ref (tree ptr) const
+{
+  if (!var_cache)
+    return NULL;
+
+  unsigned version = SSA_NAME_VERSION (ptr);
+  if (var_cache->length () <= version)
+    return NULL;
+
+  access_ref &cache_ref = (*var_cache)[version];
+  if (cache_ref.ref)
+    {
+      ++hits;
+      return &cache_ref;
+    }
+
+  ++misses;
+  return NULL;
+}
+
+/* Retrieve the access_ref instance for a variable from the cache if it's
+   there or compute it and insert it into the cache if it's nonnonull.  */
+
+bool
+pointer_query::get_ref (tree ptr, access_ref *pref)
+{
+  const unsigned version
+    = TREE_CODE (ptr) == SSA_NAME ? SSA_NAME_VERSION (ptr) : 0;
+
+  access_ref *cache_ref = NULL;
+  if (var_cache && version)
+    {
+      if (version < var_cache->length ())
+	{
+	  if ((*var_cache)[version].ref)
+	    {
+	      ++hits;
+	      *pref = (*var_cache)[version];
+	      return true;
+	    }
+	}
+      else
+	var_cache->safe_grow_cleared (version + 1);
+
+      ++misses;
+      cache_ref = &(*var_cache)[version];
+    }
+
+  if (!compute_objsize (ptr, pref, this))
+    {
+      ++failures;
+      return false;
+    }
+
+  if (cache_ref)
+    *cache_ref = *pref;
+
+  return true;
+}
+
+/* Add a copy of the access_ref REF for the SSA_NAME to the cache if it's
+   nonnull.  */
+
+void
+pointer_query::put_ref (tree ptr, const access_ref &ref)
+{
+  /* Only add populated/valid entries.  */
+  if (!var_cache || !ref.ref || ref.sizrng[0] < 0)
+    return;
+
+  unsigned version = SSA_NAME_VERSION (ptr);
+  if (var_cache->length () <= version)
+    var_cache->safe_grow_cleared (version + 1);
+  else if ((*var_cache)[version].ref)
+    {
+      gcc_checking_assert ((*var_cache)[version].ref == ref.ref);
+      return;
+    }
+
+  (*var_cache)[version] = ref;
+}
+
 /* Return true if NAME starts with __builtin_ or __sync_.  */
 
 static bool
@@ -4956,8 +5058,8 @@  gimple_call_return_array (gimple *stmt, offset_int offrng[2],
    statement STMT with the RHS of either MIN_EXPR or MAX_EXPR.  */
 
 static bool
-handle_min_max_size (gimple *stmt, int ostype, access_ref *pref,
-		     bitmap *visited, range_query *rvals)
+handle_min_max_size (gimple *stmt, access_ref *pref, pointer_query *qry,
+		     bitmap *visited)
 {
   tree_code code = gimple_assign_rhs_code (stmt);
 
@@ -4969,7 +5071,7 @@  handle_min_max_size (gimple *stmt, int ostype, access_ref *pref,
      determined from the other instead, adjusted up or down as appropriate
      for the expression.  */
   access_ref aref[2] = { *pref, *pref };
-  if (!compute_objsize (ptr, ostype, &aref[0], visited, rvals))
+  if (!compute_objsize_r (ptr, &aref[0], qry, visited))
     {
       aref[0].base0 = false;
       aref[0].offrng[0] = aref[0].offrng[1] = 0;
@@ -4978,7 +5080,7 @@  handle_min_max_size (gimple *stmt, int ostype, access_ref *pref,
     }
 
   ptr = gimple_assign_rhs2 (stmt);
-  if (!compute_objsize (ptr, ostype, &aref[1], visited, rvals))
+  if (!compute_objsize_r (ptr, &aref[1], qry, visited))
     {
       aref[1].base0 = false;
       aref[1].offrng[0] = aref[1].offrng[1] = 0;
@@ -5038,7 +5140,8 @@  handle_min_max_size (gimple *stmt, int ostype, access_ref *pref,
    offsets into it, and PREF->SIZRNG to the range of sizes of
    the object(s).
    VISITED is used to avoid visiting the same PHI operand multiple
-   times, and, when nonnull, RVALS to determine range information.
+   times, and, when nonnull, QRY to use to query and/or update
+   the pointer cache and to determine range information.
    Returns true on success, false when a meaningful size (or range)
    cannot be determined.
 
@@ -5046,8 +5149,8 @@  handle_min_max_size (gimple *stmt, int ostype, access_ref *pref,
    to influence code generation or optimization.  */
 
 static bool
-compute_objsize (tree ptr, int ostype, access_ref *pref, bitmap *visited,
-		 range_query *rvals)
+compute_objsize_r (tree ptr, access_ref *pref, pointer_query *qry,
+		   bitmap *visited)
 {
   STRIP_NOPS (ptr);
 
@@ -5082,11 +5185,12 @@  compute_objsize (tree ptr, int ostype, access_ref *pref, bitmap *visited,
     }
 
   const tree_code code = TREE_CODE (ptr);
+  range_query *const rvals = qry ? qry->rvals : NULL;
 
   if (code == BIT_FIELD_REF)
     {
       tree ref = TREE_OPERAND (ptr, 0);
-      if (!compute_objsize (ref, ostype, pref, visited, rvals))
+      if (!compute_objsize_r (ref, pref, qry, visited))
 	return false;
 
       offset_int off = wi::to_offset (pref->eval (TREE_OPERAND (ptr, 2)));
@@ -5097,18 +5201,21 @@  compute_objsize (tree ptr, int ostype, access_ref *pref, bitmap *visited,
   if (code == COMPONENT_REF)
     {
       tree ref = TREE_OPERAND (ptr, 0);
+      const int save_ostype = qry->ostype;
       if (TREE_CODE (TREE_TYPE (ref)) == UNION_TYPE)
 	/* In accesses through union types consider the entire unions
 	   rather than just their members.  */
-	ostype = 0;
+	qry->ostype = 0;
       tree field = TREE_OPERAND (ptr, 1);
 
-      if (ostype == 0)
+      if (qry->ostype == 0)
 	{
 	  /* In OSTYPE zero (for raw memory functions like memcpy), use
 	     the maximum size instead if the identity of the enclosing
 	     object cannot be determined.  */
-	  if (!compute_objsize (ref, ostype, pref, visited, rvals))
+	  bool success = compute_objsize_r (ref, pref, qry, visited);
+	  qry->ostype = save_ostype;
+	  if (!success)
 	    return false;
 
 	  /* Otherwise, use the size of the enclosing object and add
@@ -5179,7 +5286,7 @@  compute_objsize (tree ptr, int ostype, access_ref *pref, bitmap *visited,
 	    return false;
 	}
 
-      if (!compute_objsize (ref, ostype, pref, visited, rvals))
+      if (!compute_objsize_r (ref, pref, qry, visited))
 	return false;
 
       offset_int orng[2];
@@ -5217,7 +5324,7 @@  compute_objsize (tree ptr, int ostype, access_ref *pref, bitmap *visited,
 	  orng[0] *= sz;
 	  orng[1] *= sz;
 
-	  if (ostype && TREE_CODE (eltype) == ARRAY_TYPE)
+	  if (qry->ostype && TREE_CODE (eltype) == ARRAY_TYPE)
 	    {
 	      /* Except for the permissive raw memory functions which use
 		 the size of the whole object determined above, use the size
@@ -5245,7 +5352,7 @@  compute_objsize (tree ptr, int ostype, access_ref *pref, bitmap *visited,
   if (code == TARGET_MEM_REF)
     {
       tree ref = TREE_OPERAND (ptr, 0);
-      if (!compute_objsize (ref, ostype, pref, visited, rvals))
+      if (!compute_objsize_r (ref, pref, qry, visited))
 	return false;
 
       /* TODO: Handle remaining operands.  Until then, add maximum offset.  */
@@ -5279,7 +5386,7 @@  compute_objsize (tree ptr, int ostype, access_ref *pref, bitmap *visited,
   if (code == POINTER_PLUS_EXPR)
     {
       tree ref = TREE_OPERAND (ptr, 0);
-      if (!compute_objsize (ref, ostype, pref, visited, rvals))
+      if (!compute_objsize_r (ref, pref, qry, visited))
 	return false;
 
       /* Clear DEREF since the offset is being applied to the target
@@ -5298,11 +5405,24 @@  compute_objsize (tree ptr, int ostype, access_ref *pref, bitmap *visited,
   if (code == VIEW_CONVERT_EXPR)
     {
       ptr = TREE_OPERAND (ptr, 0);
-      return compute_objsize (ptr, ostype, pref, visited, rvals);
+      return compute_objsize_r (ptr, pref, qry, visited);
     }
 
   if (TREE_CODE (ptr) == SSA_NAME)
     {
+      if (qry)
+	{
+	  if (++qry->depth)
+	    qry->max_depth = qry->depth;
+	  if (const access_ref *cache_ref = qry->get_ref (ptr))
+	    {
+	      /* If the pointer is in the cache set *PREF to what it refers
+		 to and return success.  */
+	      *pref = *cache_ref;
+	      return true;
+	    }
+	}
+
       gimple *stmt = SSA_NAME_DEF_STMT (ptr);
       if (is_gimple_call (stmt))
 	{
@@ -5331,7 +5451,7 @@  compute_objsize (tree ptr, int ostype, access_ref *pref, bitmap *visited,
 	      offset_int offrng[2];
 	      if (tree ret = gimple_call_return_array (stmt, offrng, rvals))
 		{
-		  if (!compute_objsize (ret, ostype, pref, visited, rvals))
+		  if (!compute_objsize_r (ret, pref, qry, visited))
 		    return false;
 
 		  /* Cap OFFRNG[1] to at most the remaining size of
@@ -5353,6 +5473,7 @@  compute_objsize (tree ptr, int ostype, access_ref *pref, bitmap *visited,
 		  pref->ref = ptr;
 		}
 	    }
+	  qry->put_ref (ptr, *pref);
 	  return true;
 	}
 
@@ -5369,12 +5490,14 @@  compute_objsize (tree ptr, int ostype, access_ref *pref, bitmap *visited,
 	      pref->sizrng[0] = offset_int::from (wr[0], UNSIGNED);
 	      pref->sizrng[1] = offset_int::from (wr[1], UNSIGNED);
 	      pref->ref = ref;
+	      qry->put_ref (ptr, *pref);
 	      return true;
 	    }
 
 	  pref->set_max_size_range ();
 	  pref->base0 = false;
 	  pref->ref = ptr;
+	  qry->put_ref (ptr, *pref);
 	  return true;
 	}
 
@@ -5382,10 +5505,11 @@  compute_objsize (tree ptr, int ostype, access_ref *pref, bitmap *visited,
 	{
 	  pref->ref = ptr;
 	  access_ref phi_ref = *pref;
-	  if (!pref->get_ref (NULL, &phi_ref, ostype, visited, rvals))
+	  if (!pref->get_ref (NULL, &phi_ref, qry, visited))
 	    return false;
 	  *pref = phi_ref;
 	  pref->ref = ptr;
+	  qry->put_ref (ptr, *pref);
 	  return true;
 	}
 
@@ -5397,21 +5521,27 @@  compute_objsize (tree ptr, int ostype, access_ref *pref, bitmap *visited,
 	     PREF->REF to it.  */
 	  pref->base0 = false;
 	  pref->set_max_size_range ();
+	  qry->put_ref (ptr, *pref);
 	  return true;
 	}
 
       tree_code code = gimple_assign_rhs_code (stmt);
 
       if (code == MAX_EXPR || code == MIN_EXPR)
-	return handle_min_max_size (stmt, ostype, pref, visited, rvals);
+	{
+	  if (!handle_min_max_size (stmt, pref, qry, visited))
+	    return false;
+	  qry->put_ref (ptr, *pref);
+	  return true;
+	}
 
-      ptr = gimple_assign_rhs1 (stmt);
+      tree rhs = gimple_assign_rhs1 (stmt);
 
       if (code == POINTER_PLUS_EXPR
-	  && TREE_CODE (TREE_TYPE (ptr)) == POINTER_TYPE)
+	  && TREE_CODE (TREE_TYPE (rhs)) == POINTER_TYPE)
 	{
 	  /* Compute the size of the object first. */
-	  if (!compute_objsize (ptr, ostype, pref, visited, rvals))
+	  if (!compute_objsize_r (rhs, pref, qry, visited))
 	    return false;
 
 	  offset_int orng[2];
@@ -5420,22 +5550,25 @@  compute_objsize (tree ptr, int ostype, access_ref *pref, bitmap *visited,
 	    pref->add_offset (orng[0], orng[1]);
 	  else
 	    pref->add_max_offset ();
+	  qry->put_ref (ptr, *pref);
 	  return true;
 	}
 
       if (code == ADDR_EXPR || code == SSA_NAME)
-	return compute_objsize (ptr, ostype, pref, visited, rvals);
+	return compute_objsize_r (rhs, pref, qry, visited);
 	
       /* This could be an assignment from a nonlocal pointer.  Save PTR
 	 to mention in diagnostics but otherwise treat it as a pointer
 	 to an unknown object.  */
-      pref->ref = ptr;
+      pref->ref = rhs;
     }
 
   /* Assume all other expressions point into an unknown object
      of the maximum valid size.  */
   pref->base0 = false;
   pref->set_max_size_range ();
+  if (TREE_CODE (ptr) == SSA_NAME)
+    qry->put_ref (ptr, *pref);
   return true;
 }
 
@@ -5446,10 +5579,44 @@  tree
 compute_objsize (tree ptr, int ostype, access_ref *pref,
 		 range_query *rvals /* = NULL */)
 {
+  pointer_query qry;
+  qry.rvals = rvals;
+  qry.ostype = ostype;
+
+  bitmap visited = NULL;
+
+  bool success = compute_objsize_r (ptr, pref, &qry, &visited);
+
+  if (visited)
+    BITMAP_FREE (visited);
+
+  if (!success)
+    return NULL_TREE;
+
+  offset_int maxsize = pref->size_remaining ();
+  if (pref->base0 && pref->offrng[0] < 0 && pref->offrng[1] >= 0)
+    pref->offrng[0] = 0;
+  return wide_int_to_tree (sizetype, maxsize);
+}
+
+/* Transitional wrapper.  The function should be removed once callers
+   transition to the pointer_query API.  */
+
+tree
+compute_objsize (tree ptr, access_ref *pref, pointer_query *ptr_qry)
+{
+  pointer_query qry;
+  if (ptr_qry)
+    ptr_qry->depth = 0;
+  else
+    {
+      qry.ostype = 1;
+      ptr_qry = &qry;
+    }
+
   bitmap visited = NULL;
 
-  bool success
-    = compute_objsize (ptr, ostype, pref, &visited, rvals);
+  bool success = compute_objsize_r (ptr, pref, ptr_qry, &visited);
 
   if (visited)
     BITMAP_FREE (visited);
@@ -5463,7 +5630,7 @@  compute_objsize (tree ptr, int ostype, access_ref *pref,
   return wide_int_to_tree (sizetype, maxsize);
 }
 
-/* Transitional wrapper around the above.  The function should be removed
+/* Legacy wrapper around the above.  The function should be removed
    once callers transition to one of the two above.  */
 
 tree
@@ -12822,7 +12989,7 @@  maybe_emit_free_warning (tree exp)
     return;
 
   access_ref aref;
-  if (!compute_objsize (ptr, 0, &aref))
+  if (!compute_objsize (ptr, 0, &aref) || !aref.ref)
     return;
 
   tree ref = aref.ref;
diff --git a/gcc/builtins.h b/gcc/builtins.h
index 11f2c1e3eb5..3a5762bbade 100644
--- a/gcc/builtins.h
+++ b/gcc/builtins.h
@@ -153,6 +153,7 @@  extern void warn_string_no_nul (location_t, tree, const char *, tree,
 extern tree unterminated_array (tree, tree * = NULL, bool * = NULL);
 extern bool builtin_with_linkage_p (tree);
 
+class pointer_query;
 class range_query;
 
 /* Describes a reference to an object used in an access.  */
@@ -168,8 +169,8 @@  struct access_ref
   gphi *phi () const;
 
   /* Return the object to which REF refers.  */
-  tree get_ref (vec<access_ref> *, access_ref * = NULL, int = 1,
-		bitmap * = NULL, range_query * = NULL) const;
+  tree get_ref (vec<access_ref> *, access_ref * = NULL,
+		pointer_query * = NULL, bitmap * = NULL) const;
 
   /* Return true if OFFRNG is the constant zero.  */
   bool offset_zero () const
@@ -246,6 +247,41 @@  struct access_ref
   bool parmarray;
 };
 
+/* Queries and caches compute_objsize results.  */
+class pointer_query
+{
+  DISABLE_COPY_AND_ASSIGN (pointer_query);
+
+public:
+  typedef vec<access_ref> cache_type;
+
+  /* Construct an object with the given Ranger instance and cache.  */
+  explicit pointer_query (range_query * = NULL, cache_type * = NULL);
+
+  /* Retrieve the access_ref for a variable from cache if it's there.  */
+  const access_ref* get_ref (tree) const;
+
+  /* Retrieve the access_ref for a variable from cache or compute it.  */
+  bool get_ref (tree, access_ref*);
+
+  /* Add an access_ref for the SSA_NAME to the cache.  */
+  void put_ref (tree, const access_ref&);
+
+  /* A Ranger instance.  May be null to use global ranges.  */
+  range_query *rvals;
+  /* Cache of SSA_NAMEs.  May be null to disable caching.  */
+  cache_type *var_cache;
+  /* The Object Size Type used for size computation.  */
+  int ostype;
+
+  /* Performance counters.  */
+  mutable unsigned hits;
+  mutable unsigned misses;
+  mutable unsigned failures;
+  mutable unsigned depth;
+  mutable unsigned max_depth;
+};
+
 /* Describes a pair of references used in an access by built-in
    functions like memcpy.  */
 struct access_data
@@ -270,7 +306,11 @@  struct access_data
 extern tree gimple_call_alloc_size (gimple *, wide_int[2] = NULL,
 				    range_query * = NULL);
 extern tree gimple_parm_array_size (tree, wide_int[2], bool * = NULL);
-extern tree compute_objsize (tree, int, access_ref *, range_query * = NULL);
+
+extern tree compute_objsize (tree, int, access_ref *,
+			     range_query *rvals = NULL);
+/* Legacy/transitional API.  Should not be used in new code.  */
+extern tree compute_objsize (tree, access_ref *, pointer_query *);
 extern tree compute_objsize (tree, int, tree * = NULL, tree * = NULL,
 			     range_query * = NULL);
 extern bool check_access (tree, tree, tree, tree, tree,
diff --git a/gcc/gimple-ssa-sprintf.c b/gcc/gimple-ssa-sprintf.c
index fff034fac4d..ca0572f53d3 100644
--- a/gcc/gimple-ssa-sprintf.c
+++ b/gcc/gimple-ssa-sprintf.c
@@ -4032,26 +4032,22 @@  compute_format_length (call_info &info, format_result *res, range_query *query)
    available, or the maximum possible size otherwise.  */
 
 static unsigned HOST_WIDE_INT
-get_destination_size (tree dest)
+get_destination_size (tree dest, pointer_query &ptr_qry)
 {
   /* When there is no destination return the maximum.  */
   if (!dest)
     return HOST_WIDE_INT_MAX;
 
-  /* Initialize object size info before trying to compute it.  */
-  init_object_sizes ();
+  /* Use compute_objsize to determine the size of the destination object.  */
+  access_ref aref;
+  if (!ptr_qry.get_ref (dest, &aref))
+    return HOST_WIDE_INT_MAX;
 
-  /* Use __builtin_object_size to determine the size of the destination
-     object.  When optimizing, determine the smallest object (such as
-     a member array as opposed to the whole enclosing object), otherwise
-     use type-zero object size to determine the size of the enclosing
-     object (the function fails without optimization in this type).  */
-  int ost = optimize > 0;
-  unsigned HOST_WIDE_INT size;
-  if (compute_builtin_object_size (dest, ost, &size))
-    return size;
+  offset_int remsize = aref.size_remaining ();
+  if (!wi::fits_uhwi_p (remsize))
+    return HOST_WIDE_INT_MAX;
 
-  return HOST_WIDE_INT_MAX;
+  return remsize.to_uhwi ();
 }
 
 /* Return true if the call described by INFO with result RES safe to
@@ -4296,7 +4292,7 @@  get_user_idx_format (tree fndecl, unsigned *idx_args)
    gsi_next should not be performed in the caller.  */
 
 bool
-handle_printf_call (gimple_stmt_iterator *gsi, range_query *query)
+handle_printf_call (gimple_stmt_iterator *gsi, pointer_query &ptr_qry)
 {
   init_target_to_host_charmap ();
 
@@ -4519,7 +4515,7 @@  handle_printf_call (gimple_stmt_iterator *gsi, range_query *query)
       /* For non-bounded functions like sprintf, determine the size
 	 of the destination from the object or pointer passed to it
 	 as the first argument.  */
-      dstsize = get_destination_size (dstptr);
+      dstsize = get_destination_size (dstptr, ptr_qry);
     }
   else if (tree size = gimple_call_arg (info.callstmt, idx_dstsize))
     {
@@ -4566,7 +4562,7 @@  handle_printf_call (gimple_stmt_iterator *gsi, range_query *query)
 	     and use the greater of the two at level 1 and the smaller
 	     of them at level 2.  */
 	  value_range vr;
-	  query->range_of_expr (vr, size, info.callstmt);
+	  ptr_qry.rvals->range_of_expr (vr, size, info.callstmt);
 
 	  if (!vr.undefined_p ())
 	    {
@@ -4683,7 +4679,7 @@  handle_printf_call (gimple_stmt_iterator *gsi, range_query *query)
      never set to true again).  */
   res.posunder4k = posunder4k && dstptr;
 
-  bool success = compute_format_length (info, &res, query);
+  bool success = compute_format_length (info, &res, ptr_qry.rvals);
   if (res.warned)
     gimple_set_no_warning (info.callstmt, true);
 
diff --git a/gcc/testsuite/g++.dg/warn/Wmismatched-new-delete-2.C b/gcc/testsuite/g++.dg/warn/Wmismatched-new-delete-2.C
new file mode 100644
index 00000000000..ae6cdb56570
--- /dev/null
+++ b/gcc/testsuite/g++.dg/warn/Wmismatched-new-delete-2.C
@@ -0,0 +1,67 @@ 
+typedef __SIZE_TYPE__ size_t;
+
+extern "C" {
+  void free (void*);
+  void* malloc (size_t);
+}
+
+struct HasNew
+{
+  void* operator new (size_t);
+};
+
+struct HasDelete
+{
+  void operator delete (void*);
+};
+
+struct HasNewDelete
+{
+  void* operator new (size_t);
+  void operator delete (void*);
+};
+
+void sink (void*);
+
+void nowarn_new_delete ()
+{
+  {
+    HasNew *p = new HasNew;
+    sink (p);
+    delete p;
+  }
+
+  {
+    HasNewDelete *p = new HasNewDelete;
+    sink (p);
+    delete p;
+  }
+
+  {
+    HasDelete *p = new HasDelete;
+    sink (p);
+    delete p;
+  }
+}
+
+
+void nowarn_new_free ()
+{
+  {
+    HasNew *p = new HasNew;
+    sink (p);
+    free (p);
+  }
+
+  {
+    HasNewDelete *p = new HasNewDelete;
+    sink (p);
+    delete p;
+  }
+
+  {
+    HasDelete *p = new HasDelete;
+    sink (p);
+    delete p;
+  }
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/builtin-sprintf-warn-25.c b/gcc/testsuite/gcc.dg/tree-ssa/builtin-sprintf-warn-25.c
new file mode 100644
index 00000000000..df46023d8c5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/builtin-sprintf-warn-25.c
@@ -0,0 +1,76 @@ 
+/* PR middle-end/97373 - missing warning on sprintf into allocated destination
+   { dg-do compile }
+   { dg-options "-O2 -Wall -ftrack-macro-expansion=0" } */
+
+#include "../range.h"
+
+extern void* alloca (size_t);
+extern void* malloc (size_t);
+
+extern int sprintf (char*, const char*, ...);
+#define sprintf(d, ...) (sprintf (d, __VA_ARGS__), sink (d))
+
+void sink (void*, ...);
+
+void test_alloca_range (void)
+{
+  int n1_2 = UR (1, 2);
+  int n5_9 = UR (5, 9);
+
+  char *d = (char*)alloca (n5_9);
+
+  sprintf (d, "%i", 12345);
+
+  d += n1_2;
+  sprintf (d, "%i", 12345);
+
+  d += n1_2;
+  sprintf (d, "%i", 12345);
+
+  d += n1_2;
+  sprintf (d, "%i", 12345);
+
+  d += n1_2;
+  sprintf (d, "%i", 12345);         // { dg-warning "writing a terminating nul past the end of the destination" }
+
+  d += n1_2;
+  sprintf (d, "%i", 12345);         // { dg-warning "'%i' directive writing 5 bytes into a region of size 4" }
+}
+
+
+void test_malloc_range (void)
+{
+  int n2_3 = UR (2, 3);
+  int n5_9 = UR (5, 9);
+
+  char *d = (char*)malloc (n5_9);
+
+  sprintf (d, "%i", 12345);
+
+  d += n2_3;
+  sprintf (d, "%i", 12345);
+
+  d += n2_3;
+  sprintf (d, "%i", 12345);         // { dg-warning "writing a terminating nul past the end of the destination" }
+
+  d += n2_3;
+  sprintf (d, "%i", 12345);         // { dg-warning "'%i' directive writing 5 bytes into a region of size 3" }
+}
+
+
+void test_vla_range (void)
+{
+  int n3_4 = UR (3, 4);
+  int n5_9 = UR (5, 9);
+
+  char vla[n5_9];
+  char *d = vla;
+
+  sprintf (d, "%i", 12345);
+
+  d += n3_4;
+  sprintf (d, "%i", 12345);
+
+  d += n3_4;
+  sprintf (d, "%i", 12345);         // { dg-warning "'%i' directive writing 5 bytes into a region of size 3" }
+}
diff --git a/gcc/testsuite/gcc.dg/warn-strnlen-no-nul.c b/gcc/testsuite/gcc.dg/warn-strnlen-no-nul.c
index 82555b0fbcc..5968e87da44 100644
--- a/gcc/testsuite/gcc.dg/warn-strnlen-no-nul.c
+++ b/gcc/testsuite/gcc.dg/warn-strnlen-no-nul.c
@@ -180,7 +180,7 @@  T (v0 ? b[0] : b[2], bsz);
 T (v0 ? b[2] : b[3], bsz);
 T (v0 ? b[3] : b[2], bsz);
 
-T (v0 ? "1234" : b[3], bsz + 1);  /* { dg-warning "unterminated" "pr86937" { xfail *-*-* } } */
+T (v0 ? "1234" : b[3], bsz + 1);  /* { dg-warning "bound 6 may exceed source size 5" "pr86937" } */
 T (v0 ? "1234" : b[i3], bsz + 1); /* { dg-warning "unterminated" "pr86937" { xfail *-*-* } } */
 T (v0 ? b[3] : "1234", bsz + 1);  /* { dg-warning "unterminated" "pr86937" { xfail *-*-* } } */
 T (v0 ? b[i3] : "1234", bsz + 1); /* { dg-warning "unterminated" "pr86937" { xfail *-*-* } } */
diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c
index 7de2daa2b54..855a02de607 100644
--- a/gcc/tree-ssa-strlen.c
+++ b/gcc/tree-ssa-strlen.c
@@ -46,7 +46,6 @@  along with GCC; see the file COPYING3.  If not see
 #include "tree-ssa-propagate.h"
 #include "tree-ssa-strlen.h"
 #include "tree-hash-traits.h"
-#include "tree-object-size.h"
 #include "builtins.h"
 #include "target.h"
 #include "diagnostic-core.h"
@@ -1667,7 +1666,8 @@  valid_builtin_call (gimple *stmt)
    strinfo.  */
 
 static void
-adjust_last_stmt (strinfo *si, gimple *stmt, bool is_strcat)
+adjust_last_stmt (strinfo *si, gimple *stmt, bool is_strcat,
+		  pointer_query &ptr_qry)
 {
   tree vuse, callee, len;
   struct laststmt_struct last = laststmt;
@@ -1754,7 +1754,9 @@  adjust_last_stmt (strinfo *si, gimple *stmt, bool is_strcat)
       /* Don't fold away an out of bounds access, as this defeats proper
 	 warnings.  */
       tree dst = gimple_call_arg (last.stmt, 0);
-      tree size = compute_objsize (dst, 0);
+
+      access_ref aref;
+      tree size = compute_objsize (dst, &aref, &ptr_qry);
       if (size && tree_int_cst_lt (size, len))
 	return;
     }
@@ -1912,8 +1914,7 @@  maybe_set_strlen_range (tree lhs, tree src, tree bound)
    to allow accesses across subobject boundaries.  */
 
 static void
-maybe_warn_overflow (gimple *stmt, tree len,
-		     range_query *rvals = NULL,
+maybe_warn_overflow (gimple *stmt, tree len, pointer_query &ptr_qry,
 		     strinfo *si = NULL, bool plus_one = false,
 		     bool rawmem = false)
 {
@@ -1939,6 +1940,12 @@  maybe_warn_overflow (gimple *stmt, tree len,
   if (TREE_NO_WARNING (dest))
     return;
 
+  /* Hack: temporarily replace PTR_QRY.OSTYPE.  OSTYPE should disappear
+     as soon as compute_objsize() computes sizes for both the subobject
+     (type 1) and the enclosing object (type 0).  */
+  const int save_ostype = ptr_qry.ostype;
+  ptr_qry.ostype = rawmem ? 0 : 1;
+
   /* Use maximum precision to avoid overflow in the addition below.
      Make sure all operands have the same precision to keep wide_int
      from ICE'ing.  */
@@ -1946,7 +1953,11 @@  maybe_warn_overflow (gimple *stmt, tree len,
   access_ref aref;
   /* The size of the destination region (which is smaller than
      the destination object for stores at a non-zero offset).  */
-  tree destsize = compute_objsize (dest, rawmem ? 0 : 1, &aref, rvals);
+  tree destsize = compute_objsize (dest, &aref, &ptr_qry);
+
+  /* Restore PTR_QRY.OSTYPE.  */
+  ptr_qry.ostype = save_ostype;
+
   if (!destsize)
     {
       aref.sizrng[0] = 0;
@@ -1962,7 +1973,7 @@  maybe_warn_overflow (gimple *stmt, tree len,
     return;
 
   wide_int rng[2];
-  if (!get_range (len, stmt, rng, rvals))
+  if (!get_range (len, stmt, rng, ptr_qry.rvals))
     return;
 
   widest_int lenrng[2] =
@@ -2091,10 +2102,10 @@  maybe_warn_overflow (gimple *stmt, tree len,
 
 static inline void
 maybe_warn_overflow (gimple *stmt, unsigned HOST_WIDE_INT len,
-		     range_query *rvals = NULL, strinfo *si = NULL,
+		     pointer_query &ptr_qry, strinfo *si = NULL,
 		     bool plus_one = false, bool rawmem = false)
 {
-  maybe_warn_overflow (stmt, build_int_cst (size_type_node, len), rvals,
+  maybe_warn_overflow (stmt, build_int_cst (size_type_node, len), ptr_qry,
 		       si, plus_one, rawmem);
 }
 
@@ -2394,7 +2405,7 @@  handle_builtin_strchr (gimple_stmt_iterator *gsi)
 
 static void
 handle_builtin_strcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi,
-		       range_query *rvals)
+		       pointer_query &ptr_qry)
 {
   int idx, didx;
   tree src, dst, srclen, len, lhs, type, fn, oldlen;
@@ -2420,7 +2431,7 @@  handle_builtin_strcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi,
     return;
 
   if (olddsi != NULL)
-    adjust_last_stmt (olddsi, stmt, false);
+    adjust_last_stmt (olddsi, stmt, false, ptr_qry);
 
   srclen = NULL_TREE;
   if (si != NULL)
@@ -2428,10 +2439,10 @@  handle_builtin_strcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi,
   else if (idx < 0)
     srclen = build_int_cst (size_type_node, ~idx);
 
-  maybe_warn_overflow (stmt, srclen, rvals, olddsi, true);
+  maybe_warn_overflow (stmt, srclen, ptr_qry, olddsi, true);
 
   if (olddsi != NULL)
-    adjust_last_stmt (olddsi, stmt, false);
+    adjust_last_stmt (olddsi, stmt, false, ptr_qry);
 
   loc = gimple_location (stmt);
   if (srclen == NULL_TREE)
@@ -2776,7 +2787,8 @@  is_strlen_related_p (tree src, tree len)
 */
 
 bool
-maybe_diag_stxncpy_trunc (gimple_stmt_iterator gsi, tree src, tree cnt)
+maybe_diag_stxncpy_trunc (gimple_stmt_iterator gsi, tree src, tree cnt,
+			  pointer_query *ptr_qry /* = NULL */)
 {
   gimple *stmt = gsi_stmt (gsi);
   if (gimple_no_warning_p (stmt))
@@ -3039,7 +3051,8 @@  maybe_diag_stxncpy_trunc (gimple_stmt_iterator gsi, tree src, tree cnt)
 	}
     }
 
-  if (tree dstsize = compute_objsize (dst, 1))
+  access_ref aref;
+  if (tree dstsize = compute_objsize (dst, &aref, ptr_qry))
     {
       /* The source length is unknown.  Try to determine the destination
 	 size and see if it matches the specified bound.  If not, bail.
@@ -3054,7 +3067,7 @@  maybe_diag_stxncpy_trunc (gimple_stmt_iterator gsi, tree src, tree cnt)
       /* Avoid warning for strncpy(a, b, N) calls where the following
 	 equalities hold:
 	   N == sizeof a && N == sizeof b */
-      if (tree srcsize = compute_objsize (src, 1))
+      if (tree srcsize = compute_objsize (src, &aref, ptr_qry))
 	if (wi::to_wide (srcsize) == cntrange[1])
 	  return false;
 
@@ -3197,7 +3210,7 @@  handle_builtin_stxncpy_strncat (bool append_p, gimple_stmt_iterator *gsi)
 
 static void
 handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi,
-		       range_query *rvals)
+		       pointer_query &ptr_qry)
 {
   tree lhs, oldlen, newlen;
   gimple *stmt = gsi_stmt (*gsi);
@@ -3217,8 +3230,8 @@  handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi,
   if (olddsi != NULL
       && !integer_zerop (len))
     {
-      maybe_warn_overflow (stmt, len, rvals, olddsi, false, false);
-      adjust_last_stmt (olddsi, stmt, false);
+      maybe_warn_overflow (stmt, len, ptr_qry, olddsi, false, false);
+      adjust_last_stmt (olddsi, stmt, false, ptr_qry);
     }
 
   int idx = get_stridx (src);
@@ -3295,7 +3308,7 @@  handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi,
     }
 
   if (olddsi != NULL && TREE_CODE (len) == SSA_NAME)
-    adjust_last_stmt (olddsi, stmt, false);
+    adjust_last_stmt (olddsi, stmt, false, ptr_qry);
 
   if (didx == 0)
     {
@@ -3377,7 +3390,8 @@  handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi,
    is known.  */
 
 static void
-handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi)
+handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi,
+		       pointer_query &ptr_qry)
 {
   int idx, didx;
   tree srclen, args, type, fn, objsz, endptr;
@@ -3605,7 +3619,7 @@  handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi)
 	 computed by transforming this strcpy into stpcpy.  */
       if (srclen == NULL_TREE && dsi->dont_invalidate)
 	dsi->stmt = stmt;
-      adjust_last_stmt (dsi, stmt, true);
+      adjust_last_stmt (dsi, stmt, true, ptr_qry);
       if (srclen != NULL_TREE)
 	{
 	  laststmt.stmt = stmt;
@@ -3662,13 +3676,13 @@  handle_alloc_call (enum built_in_function bcode, gimple_stmt_iterator *gsi)
 
 static bool
 handle_builtin_memset (gimple_stmt_iterator *gsi, bool *zero_write,
-		       range_query *rvals)
+		       pointer_query &ptr_qry)
 {
   gimple *memset_stmt = gsi_stmt (*gsi);
   tree ptr = gimple_call_arg (memset_stmt, 0);
   /* Set to the non-constant offset added to PTR.  */
   wide_int offrng[2];
-  int idx1 = get_stridx (ptr, offrng, rvals);
+  int idx1 = get_stridx (ptr, offrng, ptr_qry.rvals);
   if (idx1 <= 0)
     return false;
   strinfo *si1 = get_strinfo (idx1);
@@ -3684,7 +3698,7 @@  handle_builtin_memset (gimple_stmt_iterator *gsi, bool *zero_write,
   tree memset_size = gimple_call_arg (memset_stmt, 2);
 
   /* Check for overflow.  */
-  maybe_warn_overflow (memset_stmt, memset_size, rvals, NULL, false, false);
+  maybe_warn_overflow (memset_stmt, memset_size, ptr_qry, NULL, false, false);
 
   /* Bail when there is no statement associated with the destination
      (the statement may be null even when SI1->ALLOC is not).  */
@@ -4728,7 +4742,7 @@  count_nonzero_bytes (tree exp, unsigned lenrange[3], bool *nulterm,
 
 static bool
 handle_store (gimple_stmt_iterator *gsi, bool *zero_write,
-	      range_query *rvals)
+	      pointer_query &ptr_qry)
 {
   int idx = -1;
   strinfo *si = NULL;
@@ -4736,6 +4750,8 @@  handle_store (gimple_stmt_iterator *gsi, bool *zero_write,
   tree ssaname = NULL_TREE, lhs = gimple_assign_lhs (stmt);
   tree rhs = gimple_assign_rhs1 (stmt);
 
+  range_query *const rvals = ptr_qry.rvals;
+
   /* The offset of the first byte in LHS modified by the store.  */
   unsigned HOST_WIDE_INT offset = 0;
 
@@ -4762,7 +4778,7 @@  handle_store (gimple_stmt_iterator *gsi, bool *zero_write,
 	      unsigned lenrange[] = { UINT_MAX, 0, 0 };
 	      if (count_nonzero_bytes (rhs, lenrange, &dummy, &dummy, &dummy,
 				       rvals))
-		maybe_warn_overflow (stmt, lenrange[2], rvals);
+		maybe_warn_overflow (stmt, lenrange[2], ptr_qry);
 
 	      return true;
 	    }
@@ -4802,7 +4818,7 @@  handle_store (gimple_stmt_iterator *gsi, bool *zero_write,
       storing_nonzero_p = lenrange[1] > 0;
       *zero_write = storing_all_zeros_p;
 
-      maybe_warn_overflow (stmt, lenrange[2], rvals);
+      maybe_warn_overflow (stmt, lenrange[2], ptr_qry);
     }
   else
     {
@@ -4920,7 +4936,7 @@  handle_store (gimple_stmt_iterator *gsi, bool *zero_write,
 	    /* We're overwriting the nul terminator with a nonzero or
 	       unknown character.  If the previous stmt was a memcpy,
 	       its length may be decreased.  */
-	    adjust_last_stmt (si, stmt, false);
+	    adjust_last_stmt (si, stmt, false, ptr_qry);
 	  si = unshare_strinfo (si);
 	  if (storing_nonzero_p)
 	    {
@@ -5138,7 +5154,7 @@  is_char_type (tree type)
 
 static bool
 strlen_check_and_optimize_call (gimple_stmt_iterator *gsi, bool *zero_write,
-				range_query *rvals)
+				pointer_query &ptr_qry)
 {
   gimple *stmt = gsi_stmt (*gsi);
 
@@ -5155,7 +5171,7 @@  strlen_check_and_optimize_call (gimple_stmt_iterator *gsi, bool *zero_write,
   if (!flag_optimize_strlen
       || !strlen_optimize
       || !valid_builtin_call (stmt))
-    return !handle_printf_call (gsi, rvals);
+    return !handle_printf_call (gsi, ptr_qry);
 
   tree callee = gimple_call_fndecl (stmt);
   switch (DECL_FUNCTION_CODE (callee))
@@ -5171,7 +5187,7 @@  strlen_check_and_optimize_call (gimple_stmt_iterator *gsi, bool *zero_write,
     case BUILT_IN_STRCPY_CHK:
     case BUILT_IN_STPCPY:
     case BUILT_IN_STPCPY_CHK:
-      handle_builtin_strcpy (DECL_FUNCTION_CODE (callee), gsi, rvals);
+      handle_builtin_strcpy (DECL_FUNCTION_CODE (callee), gsi, ptr_qry);
       break;
 
     case BUILT_IN_STRNCAT:
@@ -5190,11 +5206,11 @@  strlen_check_and_optimize_call (gimple_stmt_iterator *gsi, bool *zero_write,
     case BUILT_IN_MEMCPY_CHK:
     case BUILT_IN_MEMPCPY:
     case BUILT_IN_MEMPCPY_CHK:
-      handle_builtin_memcpy (DECL_FUNCTION_CODE (callee), gsi, rvals);
+      handle_builtin_memcpy (DECL_FUNCTION_CODE (callee), gsi, ptr_qry);
       break;
     case BUILT_IN_STRCAT:
     case BUILT_IN_STRCAT_CHK:
-      handle_builtin_strcat (DECL_FUNCTION_CODE (callee), gsi);
+      handle_builtin_strcat (DECL_FUNCTION_CODE (callee), gsi, ptr_qry);
       break;
     case BUILT_IN_ALLOCA:
     case BUILT_IN_ALLOCA_WITH_ALIGN:
@@ -5203,7 +5219,7 @@  strlen_check_and_optimize_call (gimple_stmt_iterator *gsi, bool *zero_write,
       handle_alloc_call (DECL_FUNCTION_CODE (callee), gsi);
       break;
     case BUILT_IN_MEMSET:
-      if (handle_builtin_memset (gsi, zero_write, rvals))
+      if (handle_builtin_memset (gsi, zero_write, ptr_qry))
 	return false;
       break;
     case BUILT_IN_MEMCMP:
@@ -5212,11 +5228,11 @@  strlen_check_and_optimize_call (gimple_stmt_iterator *gsi, bool *zero_write,
       break;
     case BUILT_IN_STRCMP:
     case BUILT_IN_STRNCMP:
-      if (handle_builtin_string_cmp (gsi, rvals))
+      if (handle_builtin_string_cmp (gsi, ptr_qry.rvals))
 	return false;
       break;
     default:
-      if (handle_printf_call (gsi, rvals))
+      if (handle_printf_call (gsi, ptr_qry))
 	return false;
       break;
     }
@@ -5374,7 +5390,7 @@  handle_integral_assign (gimple_stmt_iterator *gsi, bool *cleanup_eh,
 
 static bool
 check_and_optimize_stmt (gimple_stmt_iterator *gsi, bool *cleanup_eh,
-			 range_query *rvals)
+			 pointer_query &ptr_qry)
 {
   gimple *stmt = gsi_stmt (*gsi);
 
@@ -5384,7 +5400,7 @@  check_and_optimize_stmt (gimple_stmt_iterator *gsi, bool *cleanup_eh,
 
   if (is_gimple_call (stmt))
     {
-      if (!strlen_check_and_optimize_call (gsi, &zero_write, rvals))
+      if (!strlen_check_and_optimize_call (gsi, &zero_write, ptr_qry))
 	return false;
     }
   else if (!flag_optimize_strlen || !strlen_optimize)
@@ -5409,7 +5425,7 @@  check_and_optimize_stmt (gimple_stmt_iterator *gsi, bool *cleanup_eh,
 	}
       else if (TREE_CODE (lhs) == SSA_NAME && INTEGRAL_TYPE_P (lhs_type))
 	/* Handle assignment to a character.  */
-	handle_integral_assign (gsi, cleanup_eh, rvals);
+	handle_integral_assign (gsi, cleanup_eh, ptr_qry.rvals);
       else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs))
 	{
 	  tree type = TREE_TYPE (lhs);
@@ -5440,7 +5456,7 @@  check_and_optimize_stmt (gimple_stmt_iterator *gsi, bool *cleanup_eh,
 	  }
 
 	  /* Handle a single or multibyte assignment.  */
-	  if (is_char_store && !handle_store (gsi, &zero_write, rvals))
+	  if (is_char_store && !handle_store (gsi, &zero_write, ptr_qry))
 	    return false;
 	}
     }
@@ -5514,8 +5530,9 @@  public:
   strlen_dom_walker (cdi_direction direction)
     : dom_walker (direction),
     evrp (false),
+    ptr_qry (&evrp, &var_cache),
     m_cleanup_cfg (false)
-  {}
+  { }
 
   virtual edge before_dom_children (basic_block);
   virtual void after_dom_children (basic_block);
@@ -5524,6 +5541,11 @@  public:
      to track strlen results across integer variable assignments.  */
   evrp_range_analyzer evrp;
 
+  /* A pointer_query object and its cache to store information about
+     pointers and their targets in.  */
+  pointer_query ptr_qry;
+  auto_vec<access_ref> var_cache;
+
   /* Flag that will trigger TODO_cleanup_cfg to be returned in strlen
      execute function.  */
   bool m_cleanup_cfg;
@@ -5617,7 +5639,10 @@  strlen_dom_walker::before_dom_children (basic_block bb)
 	 can be used by printf argument processing.  */
       evrp.record_ranges_from_stmt (stmt, false);
 
-      if (check_and_optimize_stmt (&gsi, &cleanup_eh, &evrp))
+      /* Reset search depth preformance counter.  */
+      ptr_qry.depth = 0;
+
+      if (check_and_optimize_stmt (&gsi, &cleanup_eh, ptr_qry))
 	gsi_next (&gsi);
     }
 
@@ -5685,6 +5710,17 @@  printf_strlen_execute (function *fun, bool warn_only)
   strlen_dom_walker walker (CDI_DOMINATORS);
   walker.walk (ENTRY_BLOCK_PTR_FOR_FN (fun));
 
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "pointer_query counters\n"
+	     "  cache size: %u\n"
+	     "  hits:       %u\n"
+	     "  misses:     %u\n"
+	     "  failures:   %u\n"
+	     "  max_depth:  %u\n",
+	     walker.ptr_qry.var_cache->length (),
+	     walker.ptr_qry.hits, walker.ptr_qry.misses,
+	     walker.ptr_qry.failures, walker.ptr_qry.max_depth);
+
   ssa_ver_to_stridx.release ();
   strinfo_pool.release ();
   if (decl_to_stridxlist_htab)
@@ -5710,9 +5746,6 @@  printf_strlen_execute (function *fun, bool warn_only)
       loop_optimizer_finalize ();
     }
 
-  /* Clean up object size info.  */
-  fini_object_sizes ();
-
   return walker.m_cleanup_cfg ? TODO_cleanup_cfg : 0;
 }
 
diff --git a/gcc/tree-ssa-strlen.h b/gcc/tree-ssa-strlen.h
index 225f64b1630..e3435c187bf 100644
--- a/gcc/tree-ssa-strlen.h
+++ b/gcc/tree-ssa-strlen.h
@@ -21,8 +21,11 @@ 
 #ifndef GCC_TREE_SSA_STRLEN_H
 #define GCC_TREE_SSA_STRLEN_H
 
+class pointer_query;
+
 extern bool is_strlen_related_p (tree, tree);
-extern bool maybe_diag_stxncpy_trunc (gimple_stmt_iterator, tree, tree);
+extern bool maybe_diag_stxncpy_trunc (gimple_stmt_iterator, tree, tree,
+				      pointer_query * = NULL);
 extern tree set_strlen_range (tree, wide_int, wide_int, tree = NULL_TREE);
 
 extern tree get_range (tree, gimple *, wide_int[2],
@@ -33,6 +36,6 @@  extern void get_range_strlen_dynamic (tree, gimple *, c_strlen_data *,
 				      class range_query *);
 
 /* APIs internal to strlen pass.  Defined in gimple-ssa-sprintf.c.  */
-extern bool handle_printf_call (gimple_stmt_iterator *,  class range_query *);
+extern bool handle_printf_call (gimple_stmt_iterator *, pointer_query &);
 
 #endif   // GCC_TREE_SSA_STRLEN_H