[PATCH] integrate sprintf pass into strlen (PR 83431)

Martin Sebor msebor@gmail.com
Fri Jul 12 22:04:00 GMT 2019 

...
>> 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?
> 
> Yes.  strlen just calls into sprintf to handle the calls.
> 
>>> 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.
> 
> I think you did the best you could given the APIs you had to work
> with There's still plenty of room to improve const-correctness but
> it involves changing other APIs outsid strlen/sprintf.
> 
>>> 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.
> 
> The strlen optimization machinery only runs once.  The code avoids
> running it when the pass is invoked early and only calls into sprintf
> to do format checking.
> 
>>
>> 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?
> 
> We decided to run it early when optimization is disabled because
> there's a good amount of code that can be checked even without
> ranges and string lengths (especially at the conservative level
> 2 setting when we consider the largest integers and array sizes
> instead of values or string lengths).
> 
> For example, this is diagnosed for the potential buffer overflow
> at -Wformat-overflow=2 even without optimization:
> 
>    char a[8], s[4];
> 
>    void f (int i)
>    {
>      __builtin_sprintf (a, "%s = %i", s, i);
>    }
> 
>    warning: ‘%i’ directive writing between 1 and 11 bytes into a region 
> of size between 2 and 5 [-Wformat-overflow=]
> 
> 
>>> 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.
> 
> Yes, good catch, thanks!
> 
>> 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.
> The term is a "null pointer."  NULL is a C macro that has in C++ 11
> been superseded by nullptr.  I don't mind using NUL character but
> I also don't think it matters.  No one will be confused about what
> either means.
> 
>>> +/* 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.
> 
> It's easy enough to add here.  But I know I've introduced other
> algorithms that recurse on SSA_NAME_DEF_STMT, and I'm quite sure
> others predate those.  To make a difference I think we need to
> review at least the one most likely to be exposed to this problem
> and introduce the same limit there.  I could probably fix the ones
> I wrote reasonably quickly, but making the change to the others
> would be much more of a project.  I looked to see how pervasive
> this might be and here is just a small sampling of things that
> jumped out at me in a quick grep search:
> 
>   *  compute_builtin_object_size (for _FORTIFY_SOURCE)
>   *  compute_objsize (for -Wstringop-overflow)
>   *  get_range_strlen
>   *  maybe_fold_{and,or}_comparisons in gimple-fold.c
>   *  -Warray-bounds (computing an offset into an object)
>   *  -Wrestrict (computing an offset into an object)
>   *  -Wreturn-local-addr (is_addr_local)
>   *  -Wuninitialized (collect_phi_def_edges)
> 
> Given how wide-spread this technique seems to be, if the recursion
> is in fact a problem it's just as likely (if not more) to come up
> in the folder or in BOS or some other place as it is here.  So if
> it needs fixing it seems it should be done as its own project and
> everywhere (or as close as we can get), and not as part of this
> integration.
> 
>>   +  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.
> 
> Yes, thanks.
> 
>>
>>> @@ -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.
> 
> Well, sure.  The whole pass can be a class (or a set of classes).
> It began as C code and then C++ started to slowly and organically
> creep in.  There are many other nice improvements we could make
> by putting C++ to better use.  One very simple one I'd like is
> moving local variable declarations to the point of their
> initialization.  Making the APIs const-correct would also improve
> readability.  But I've resisted making these changes because I
> know people are sensitive to too much churn.  If you think it's
> a good idea for me to make these changes let me know.  I'd be
> happy to do it, just separately from this integration.
> 
>>> +{
>>> +  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);
>>> -}
> 
> This test is now integrated into pass_strlen::gate so the guard
> above is only entered when the pass is running early (i.e., at
> -O0) or when the strlen optimization is disabled.  Otherwise
> there's another call to handle_printf_call in the big switch
> statement in check_and_optimize_call.
> 
>>> @@ -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.
> 
> Please see my answer + example above.
> 
>>>     /* 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?
> 
> Yes, thanks.
> 
>>
>>
>>> +     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.
> 
> It was introduced by Aldy to fix PR 85598.
> 
>>
>> My brain is turning to mush, so I think I'm going to need to do another
>> iteration over this patch.
> 
> I want to respond because it's been a while but I'll post an updated
> patch later this week.  In the meantime, if you have more comments
> on the rest of it please send them my way.

Attached is the updated patch.  I added the recursion limit to
get_range_strlen_dynamic (and tests for it) but not to
get_range_strlen in gimple-fold.c or any of the other functions
outside tree-ssa-strlen.c.  I will do that separately, once this
work has been committed.

Rested on x86_64-linux.

Martin
-------------- next part --------------
A non-text attachment was scrubbed...
Name: gcc-83431.diff
Type: text/x-patch
Size: 141709 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20190712/2604ae8e/attachment.bin>

More information about the Gcc-patches mailing list