On 7/2/19 3:59 AM, Richard Biener wrote:
> On Tue, Jul 2, 2019 at 3:48 AM Martin Sebor <mse...@gmail.com> wrote:
>>
>> Attached is a more complete solution that fully resolves the bug
>> report by avoiding a warning in cases like:
>>
>> char a[32], b[8];
>>
>> void f (void)
>> {
>> if (strlen (a) < sizeof b - 2)
>> snprintf (b, sizeof b, "b=%s", a); // no -Wformat-truncation
>> }
>>
>> It does that by having get_range_strlen_dynamic use the EVRP
>> information for non-constant strlen calls: EVRP has recorded
>> that the result is less sizeof b - 2 and so the function
>> returns this limited range of lengths to snprintf which can
>> then avoid warning. It also improves the checking and can
>> find latent bugs it missed before (like the off-by-one in
>> print-rtl.c).
>>
>> Besides improving the accuracy of the -Wformat-overflow and
>> truncation warnings this can also result in better code.
>> So far this only benefits snprintf but there may be other
>> opportunities to string functions as well (e.g., strcmp or
>> memcmp).
>>
>> Jeff, I looked into your question/suggestion for me last week
>> when we spoke, to introduce some sort of a recursion limit for
>> get_range_strlen_dynamic. It's easily doable but before we go
>> down that path I did some testing to see how bad it can get and
>> to compare it with get_range_strlen. Here are the results for
>> a few packages. The dept is the maximum recursion depth, success
>> and fail are the numbers of successful and failed calls to
>> the function:
>>
>> binutils-gdb:
>> depth success fail
>> get_range_strlen: 319 8302 21621
>> get_range_strlen_dynamic: 41 1503 161
>> gcc:
>> get_range_strlen: 46 7211 11365
>> get_range_strlen_dynamic: 23 10272 12
>> glibc:
>> get_range_strlen: 76 2840 11422
>> get_range_strlen_dynamic: 51 1186 46
>> elfutils:
>> get_range_strlen: 33 1198 2516
>> get_range_strlen_dynamic: 31 685 36
>> kernel:
>> get_range_strlen: 25 5299 11698
>> get_range_strlen_dynamic: 31 9911 122
>>
>> Except the first case of get_range_strlen (I haven't looked into
>> it yet), it doesn't seem too bad, and with just one exception it's
>> better than get_range_strlen. Let me know if you think it's worth
>> adding a parameter (I assume we'd use it for both functions) and
>> what to set it to.
>
> I think we want to avoid adding code to GCC that might turn out
> quadratic for artificial testcases. History tells us that eventually
> somebody will find a real-world testcase that hits it. I would
> suggest to not place a limit on the depth but on the number
> of SSA_NAME_DEF_STMTs visited. Not sure to what this
> would turn out but I guess using a limit around 500 would work?
> For the data above what's the biggest depth / highest number
> of stmts we visit when we are able to compute a useful limit
> and what is it when including failure? The individual number
> of successes/fails are not too interesting. Maybe even provide
> a histogram for the successful cases depth/stmt count?
Martin and I were kicking this around last week based on some feedback
from Jakub. I agree that we want to avoid quadratic, even for
artificial testcases. Whatever the solution finally is, we probably
want to do something very similar if not the same in the patch to detect
returning addresses in the local stack.
In an ideal world we'd have some kind of generic walker with the
limiter; I suspect there's more instances of this backwards walk lurking.
>
> Since we have a parallelization GSoC project running not
> adding more global state to passes would be nice as well,
> strlen has a lot of it that could be in a per invocation state
> class. Not a requirement for this patch though.
I have an independent patch which does some of this. It's from about
this time last year and had to be put on the back burner. It pulls
ssa_ver_to_stridx, max_stridx, strinfo_pool, stridx_to_strinfo,
strlenloc, strlen_to_stridx and stridx_obstack into the class along with
a lot of the support routines.
I guess it's time to resurrect that work :-)
jeff
