On 7/1/19 7:47 PM, Martin Sebor 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.
>
> On 6/11/19 5:26 PM, Martin Sebor wrote:
>> The sprintf and strlen passes both work with strings but
>> run independently of one another and don't share state. As
>> a result, lengths of strings dynamically created by functions
>> that are available to the strlen pass are not available to
>> sprintf. Conversely, lengths of strings formatted by
>> the sprintf functions are not made available to the strlen
>> pass. The result is less efficient code, poor diagnostics,
>> and ultimately less than optimal user experience.
>>
>> The attached patch is the first step toward rectifying this
>> design problem. It integrates the two passes into one and
>> exposes the string length data managed by the strlen pass to
>> the sprintf "module." (It does not expose any sprintf data
>> to the strlen pass yet.)
>>
>> The sprintf pass invocations in passes.def have been replaced
>> with those of strlen. The first "early" invocation is only
>> effective for the sprintf module to enable warnings without
>> optimization. The second invocation is "late" and enables
>> both warnings and the sprintf and strlen optimizations unless
>> explicitly disabled via -fno-optimize-strlen.
>>
>> Since the strlen optimization is the second invocation of
>> the pass tests that scan the strlen dump have been adjusted
>> to look for the "strlen2" dump file.
>>
>> The changes in the patch are mostly mechanical. The one new
>> "feature" worth calling out is the get_range_strlen_dynamic
>> function. It's analogous to get_range_strlen in gimple-fold.c
>> except that it makes use of the strlen "dynamically" obtained
>> string length info. In cases when the info is not available
>> the former calls the latter.
>>
>> The other new functions in tree-ssa-strlen.c are
>> check_and_optimize_call and handle_integral_assign: I added
>> them only to keep the check_and_optimize_stmt function from
>> getting excessively long and hard to follow. Otherwise,
>> the code in the functions is unchanged.
>>
>> There are a number of further enhancements to consider as
>> the next steps:
>> * enhance the strlen module to determine string length range
>> information from integer variable to which it was previously
>> assigned (necessary to fully resolve pr83431 and pr90625),
>> * make the sprintf/snprintf string length results directly
>> available to the strlen module,
>> * enhance the sprintf module to optimize snprintf(0, 0, fmt)
>> calls with fmt strings consisting solely of plain characters
>> and %s directives to series of strlen calls on the arguments,
>> * and more.
>>
>> Martin
>
>
> gcc-83431.diff
>
> PR tree-optimization/83431 - -Wformat-truncation may incorrectly report
> truncation
>
> gcc/ChangeLog:
>
> PR c++/83431
> * gimple-ssa-sprintf.c (pass_data_sprintf_length): Remove object.
> (sprintf_dom_walker): Remove class.
> (get_int_range): Make argument const.
> (directive::fmtfunc, directive::set_precision): Same.
> (format_none): Same.
> (build_intmax_type_nodes): Same.
> (adjust_range_for_overflow): Same.
> (format_floating): Same.
> (format_character): Same.
> (format_string): Same.
> (format_plain): Same.
> (get_int_range): Cast away constness.
> (format_integer): Same.
> (get_string_length): Call get_range_strlen_dynamic. Handle
> null lendata.maxbound.
> (should_warn_p): Adjust argument scope qualifier.
> (maybe_warn): Same.
> (format_directive): Same.
> (parse_directive): Same.
> (is_call_safe): Same.
> (try_substitute_return_value): Same.
> (sprintf_dom_walker::handle_printf_call): Rename...
> (handle_printf_call): ...to this. Initialize target to host charmap
> here instead of in pass_sprintf_length::execute.
> (struct call_info): Make global.
> (sprintf_dom_walker::compute_format_length): Make global.
> (sprintf_dom_walker::handle_gimple_call): Same.
> * passes.def (pass_sprintf_length): Replace with pass_strlen.
> * print-rtl.c (print_pattern): Reduce the number of spaces to
> avoid -Wformat-truncation.
> * tree-ssa-strlen.c (strlen_optimize): New variable.
> (get_string_length): Add comments.
> (get_range_strlen_dynamic): New functions.
> (check_and_optimize_call): New function.
> (handle_integral_assign): New function.
> (strlen_check_and_optimize_stmt): Rename...
> (check_and_optimize_stmt): ...to this. Factor code out into
> check_and_optimize_call and handle_integral_assign.
> (strlen_dom_walker::evrp): New member.
> (strlen_dom_walker::before_dom_children): Use evrp member.
> (strlen_dom_walker::after_dom_children): Use evrp member.
> (pass_data_strlen): Remove property not satisfied during an early run.
> (pass_strlen::do_optimize): New data member.
> (pass_strlen::set_pass_param): New member function.
> (pass_strlen::gate): Update to handle printf calls.
> (pass_strlen::execute): Initialize loop and scev optimizers.
> (dump_strlen_info): New function.
> * tree-ssa-strlen.h (get_range_strlen_dynamic): Declare.
> (handle_printf_call): Same.
>
> gcc/testsuite/ChangeLog:
>
> PR c++/83431
> * gcc.dg/strlenopt-63.c: New test.
> * gcc.dg/pr81292-1.c: Adjust pass name.
> * gcc.dg/pr81292-2.c: Same.
> * gcc.dg/pr81703.c: Same.
> * gcc.dg/strcmpopt_2.c: Same.
> * gcc.dg/strcmpopt_3.c: Same.
> * gcc.dg/strcmpopt_4.c: Same.
> * gcc.dg/strlenopt-1.c: Same.
> * gcc.dg/strlenopt-10.c: Same.
> * gcc.dg/strlenopt-11.c: Same.
> * gcc.dg/strlenopt-13.c: Same.
> * gcc.dg/strlenopt-14g.c: Same.
> * gcc.dg/strlenopt-14gf.c: Same.
> * gcc.dg/strlenopt-15.c: Same.
> * gcc.dg/strlenopt-16g.c: Same.
> * gcc.dg/strlenopt-17g.c: Same.
> * gcc.dg/strlenopt-18g.c: Same.
> * gcc.dg/strlenopt-19.c: Same.
> * gcc.dg/strlenopt-1f.c: Same.
> * gcc.dg/strlenopt-2.c: Same.
> * gcc.dg/strlenopt-20.c: Same.
> * gcc.dg/strlenopt-21.c: Same.
> * gcc.dg/strlenopt-22.c: Same.
> * gcc.dg/strlenopt-22g.c: Same.
> * gcc.dg/strlenopt-24.c: Same.
> * gcc.dg/strlenopt-25.c: Same.
> * gcc.dg/strlenopt-26.c: Same.
> * gcc.dg/strlenopt-27.c: Same.
> * gcc.dg/strlenopt-28.c: Same.
> * gcc.dg/strlenopt-29.c: Same.
> * gcc.dg/strlenopt-2f.c: Same.
> * gcc.dg/strlenopt-3.c: Same.
> * gcc.dg/strlenopt-30.c: Same.
> * gcc.dg/strlenopt-31g.c: Same.
> * gcc.dg/strlenopt-32.c: Same.
> * gcc.dg/strlenopt-33.c: Same.
> * gcc.dg/strlenopt-33g.c: Same.
> * gcc.dg/strlenopt-34.c: Same.
> * gcc.dg/strlenopt-35.c: Same.
> * gcc.dg/strlenopt-4.c: Same.
> * gcc.dg/strlenopt-48.c: Same.
> * gcc.dg/strlenopt-49.c: Same.
> * gcc.dg/strlenopt-4g.c: Same.
> * gcc.dg/strlenopt-4gf.c: Same.
> * gcc.dg/strlenopt-5.c: Same.
> * gcc.dg/strlenopt-50.c: Same.
> * gcc.dg/strlenopt-51.c: Same.
> * gcc.dg/strlenopt-52.c: Same.
> * gcc.dg/strlenopt-53.c: Same.
> * gcc.dg/strlenopt-54.c: Same.
> * gcc.dg/strlenopt-55.c: Same.
> * gcc.dg/strlenopt-56.c: Same.
> * gcc.dg/strlenopt-6.c: Same.
> * gcc.dg/strlenopt-61.c: Same.
> * gcc.dg/strlenopt-7.c: Same.
> * gcc.dg/strlenopt-8.c: Same.
> * gcc.dg/strlenopt-9.c: Same.
> * gcc.dg/strlenopt.h (snprintf, snprintf): Declare.
> * gcc.dg/tree-ssa/builtin-snprintf-6.c: New test.
> * gcc.dg/tree-ssa/builtin-snprintf-7.c: New test.
> * gcc.dg/tree-ssa/builtin-sprintf-warn-21.c: New test.
> * gcc.dg/tree-ssa/dump-4.c: New test.
> * gcc.dg/tree-ssa/pr83501.c: Adjust pass name.
So if I'm reading things correctly, it appears gimple-ssa-sprintf.c is
no longer a distinct pass. Instead it co-exists with the strlen pass.
Right?
>
> diff --git a/gcc/gimple-ssa-sprintf.c b/gcc/gimple-ssa-sprintf.c
> index a0934bcaf87..b05e4050f1d 100644
> --- a/gcc/gimple-ssa-sprintf.c
> +++ b/gcc/gimple-ssa-sprintf.c
> @@ -683,7 +618,7 @@ fmtresult::type_max_digits (tree type, int base)
>
> static bool
> get_int_range (tree, HOST_WIDE_INT *, HOST_WIDE_INT *, bool, HOST_WIDE_INT,
> - class vr_values *vr_values);
> + const class vr_values *vr_values);
FWIW, I think this is something *I* could do a lot better at.
Specifically I think we're not supposed to be writing the "class" here
and I'm not as good as I should be with marking things const. Thanks
for cleaning up my lack of consts.
> diff --git a/gcc/passes.def b/gcc/passes.def
> index 9a5b0cd554a..637e228f988 100644
> --- a/gcc/passes.def
> +++ b/gcc/passes.def
> @@ -42,7 +42,7 @@ along with GCC; see the file COPYING3. If not see
> NEXT_PASS (pass_build_cfg);
> NEXT_PASS (pass_warn_function_return);
> NEXT_PASS (pass_expand_omp);
> - NEXT_PASS (pass_sprintf_length, false);
> + NEXT_PASS (pass_strlen, false);
So this is something we discussed a bit on the phone. This is very
early in the pipeline -- before we've gone into SSA form.
I'm a bit concerned that we're running strlen that early without some
kind of auditing of whether or not the strlen pass can safely run that
early. Similarly have we done any review for issues that might arise
from running strlen more than once? I guess in some small way
encapsulating the state into a class like my unsubmitted patch does
would help there.
More generally I think we concluded that the placement of sprintf this
early was driven by the early placement of walloca. I don't want to
open a huge can of worms here, but do we really need to run this early
in the pipeline?
> diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c
> index 74cd6c44874..89932713476 100644
> --- a/gcc/tree-ssa-strlen.c
> +++ b/gcc/tree-ssa-strlen.c
> @@ -55,6 +55,12 @@ along with GCC; see the file COPYING3. If not see
> #include "intl.h"
> #include "attribs.h"
> #include "calls.h"
> +#include "cfgloop.h"
> +#include "tree-ssa-loop.h"
> +#include "tree-scalar-evolution.h"
> +
> +#include "vr-values.h"
> +#include "gimple-ssa-evrp-analyze.h"
Nit: Drop the extra newline.
> @@ -604,14 +614,19 @@ set_endptr_and_length (location_t loc, strinfo *si,
> tree endptr)
> si->full_string_p = true;
> }
>
> -/* Return string length, or NULL if it can't be computed. */
> +/* Return the constant string length, or NULL if it can't be computed. */>
> static tree
> get_string_length (strinfo *si)
> {
> + /* If the length has already been computed return it if it's exact
> + (i.e., the string is nul-terminated at NONZERO_CHARS), or return
> + null if it isn't. */
> if (si->nonzero_chars)
> return si->full_string_p ? si->nonzero_chars : NULL;
>
> + /* If the string is the result of one of the built-in calls below
> + attempt to compute the length from the call statement. */
> if (si->stmt)
> {
> gimple *stmt = si->stmt, *lenstmt;
IIUC get_string_length could return a non-constant expression that gives
the runtime length of a string. So I think the comment change is a bit
misleading.
Nit: Use NULL rather than null. I think this happens in more than one
place in your patch. Similarly I think we generally use NUL rather than
nul when referring to a single character.
+
> +/* Attempt to determine the length of the string SRC. On success, store
> + the length in *PDATA and return true. Otherwise, return false.
> + VISITED is a bitmap of visited PHI nodes. RVALS points to EVRP info. */
> +
> +static bool
> +get_range_strlen_dynamic (tree src, c_strlen_data *pdata, bitmap *visited,
> + const vr_values *rvals)
[ ... ]
We've already touched on the need to limit the backwards walk out of
this code. Limiting based on the product of # phi args * number of phis
visited, recursion depth, or number of SSA_NAME_DEF_STMTs visited all
seem reasonable to me.
I do think Richi's suggestion for figuring out a suitable inflection
point is reasonable.
+ if (strinfo *si = get_strinfo (idx))
> + {
> + pdata->minlen = get_string_length (si);
> + if (!pdata->minlen
> + && si->nonzero_chars)
Nit: No need for a line break in that conditional.
> +
> +/* Analogous to get_range_strlen but for dynamically created strings,
> + i.e., those created by calls to strcpy as opposed to just string
> + constants.
> + Try to obtain the range of the lengths of the string(s) referenced
> + by ARG, or the size of the largest array ARG refers to if the range
> + of lengths cannot be determined, and store all in *PDATA. RVALS
> + points to EVRP info. */
> +
> +void
> +get_range_strlen_dynamic (tree src, c_strlen_data *pdata,
> + const vr_values *rvals)
I think you need to s/ARG/SRC/ in the function comment since SRC is the
name of the parameter.
> @@ -3703,84 +4031,231 @@ fold_strstr_to_strncmp (tree rhs1, tree rhs2, gimple
> *stmt)
> }
> }
>
> +/* Check the built-in call at GSI for validity and optimize it.
> + Return true to let the caller advance *GSI to the statement
> + in the CFG and false otherwise. */
> +
> +static bool
> +check_and_optimize_call (gimple_stmt_iterator *gsi, const vr_values *rvals)
It was suggested that perhaps we should prefix this call name, but I
think the better solution might be to classify the pass and make this a
member function. That would seem to naturally fall to me since I've got
a classification patch for this code from last year that I could easily
update after your patch.
> +{
> + gimple *stmt = gsi_stmt (*gsi);
> +
> + if (!flag_optimize_strlen
> + || !strlen_optimize
> + || !valid_builtin_call (stmt))
> + {
> + /* When not optimizing we must be checking printf calls which
> + we do even for user-defined functions when they are declared
> + with attribute format. */
> + handle_printf_call (gsi, rvals);
> + return true;
> + }
Shouldn't the guard here be similar, if not the same as the gate for the
old sprintf pass? Which was:
> bool
> -pass_sprintf_length::gate (function *)
> -{
> - /* Run the pass iff -Warn-format-overflow or -Warn-format-truncation
> - is specified and either not optimizing and the pass is being invoked
> - early, or when optimizing and the pass is being invoked during
> - optimization (i.e., "late"). */
> - return ((warn_format_overflow > 0
> - || warn_format_trunc > 0
> - || flag_printf_return_value)
> - && (optimize > 0) == fold_return_value);
> -}
> @@ -4119,7 +4504,10 @@ const pass_data pass_data_strlen =
> "strlen", /* name */
> OPTGROUP_NONE, /* optinfo_flags */
> TV_TREE_STRLEN, /* tv_id */
> - ( PROP_cfg | PROP_ssa ), /* properties_required */
> + /* Normally the pass would require PROP_ssa but because it also
> + runs early, with no optimization, to do sprintf format checking,
> + it only requires PROP_cfg. */
> + PROP_cfg, /* properties_required */
> 0, /* properties_provided */
> 0, /* properties_destroyed */
> 0, /* todo_flags_start */
> @@ -4128,20 +4516,50 @@ const pass_data pass_data_strlen =
So the question I'd come back to is what are we capturing with the
instance that runs before we're in SSA form and can we reasonably catch
that stuff after going into SSA form?
It may be that we went through this at the initial submission of the
sprintf patches. I simply can't remember.
>
> /* opt_pass methods: */
> - virtual bool gate (function *) { return flag_optimize_strlen != 0; }
> +
> + opt_pass * clone () {
> + return new pass_strlen (m_ctxt);
> + }
Nit. I think this is trivial enough to just have on a single line and
is generally consistent with other passes.
> +
> + virtual bool gate (function *);
> virtual unsigned int execute (function *);
>
> + void set_pass_param (unsigned int n, bool param)
> + {
> + gcc_assert (n == 0);
> + do_optimize = param;
> + }
> }; // class pass_strlen
>
> +
> +bool
> +pass_strlen::gate (function *)
> +{
> + /* Run the pass iff -Warn-format-overflow or -Warn-format-truncation
Aren't these Wformat-overflow and Wformat-trunction?
> + is specified and either not optimizing and the pass is being
> + invoked early, or when optimizing and the pass is being invoked
> + during optimization (i.e., "late"). */
> + return ((warn_format_overflow > 0
> + || warn_format_trunc > 0
> + || flag_optimize_strlen > 0
> + || flag_printf_return_value)
> + && (optimize > 0) == do_optimize);
> +}
Ah, this is where the sprintf gateing clause went.
> +
> unsigned int
> pass_strlen::execute (function *fun)
> {
> + strlen_optimize = do_optimize;
> +
> gcc_assert (!strlen_to_stridx);
> if (warn_stringop_overflow || warn_stringop_truncation)
> strlen_to_stridx = new hash_map<tree, stridx_strlenloc> ();
> @@ -4151,10 +4569,17 @@ pass_strlen::execute (function *fun)
>
> calculate_dominance_info (CDI_DOMINATORS);
>
> + bool use_scev = optimize > 0 && flag_printf_return_value;
> + if (use_scev)
> + {
> + loop_optimizer_init (LOOPS_NORMAL);
> + scev_initialize ();
> + }
> +
> /* String length optimization is implemented as a walk of the dominator
> tree and a forward walk of statements within each block. */
> strlen_dom_walker walker (CDI_DOMINATORS);
> - walker.walk (fun->cfg->x_entry_block_ptr);
> + walker.walk (ENTRY_BLOCK_PTR_FOR_FN (fun));
>
> ssa_ver_to_stridx.release ();
> strinfo_pool.release ();
> @@ -4175,6 +4600,15 @@ pass_strlen::execute (function *fun)
> strlen_to_stridx = NULL;
> }
>
> + if (use_scev)
> + {
> + scev_finalize ();
> + loop_optimizer_finalize ();
> + }
> +
> + /* Clean up object size info. */
> + fini_object_sizes ();
> +
> return walker.m_cleanup_cfg ? TODO_cleanup_cfg : 0;
> }
Is scev really that useful here? If it is, fine, if not I'd rather not
pay the price to set it up.
My brain is turning to mush, so I think I'm going to need to do another
iteration over this patch.
Jeff
