This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH] fold more string comparison with known result (PR 90879)


On 8/9/19 10:17 AM, Martin Sebor wrote:
> GCC 9 optimizes a subset of expression of the form
> (0 == strcmp(a, b)) based on the length and/or size of
> the arguments but it doesn't take advantage of all
> the opportunities there.  For example in the following,
> although it folds the first test to false it doesn't fold
> the second one:
> 
>   char a[4];
> 
>   void f (void)
>   {
>     if (strlen (a) > 3)   // folded to false by GCC 8+
>       abort ();
> 
>     if (strcmp (a, "1234") == 0)   // folded by patched GCC
>       abort ();
> }
> 
> The attached patch extends the strcmp optimization added in
> GCC 9 to also handle the latter cases (among others).  Testing
> the enhancement with several other sizable code bases besides
> GCC (Binutils/GDB, the Linux kernel, and LLVM) shows that code
> like this is rare.  After thinking about it I decided it's more
> likely a bug than a significant optimization opportunity, so
> I introduced a new warning to point it out: -Wstring-compare
> (enabled in -Wextra).
> 
> Besides this enhancement, the patch also improves the current
> optimization to fold strcmp calls with conditional arguments
> such as in:
> 
>   void f (char *s, int i)
>   {
>     strcpy (s, "12");
>     if (strcmp (s, i ? "123" : "1234") == 0)   // folded
>       abort ();
>   }
> 
> Martin
> 
> PS The diff looks like the changes are more extensive than they
> actually are.
> 
> gcc-90879.diff
> 
> PR tree-optimization/90879 - fold zero-equality of strcmp between a longer string and a smaller array
> 
> gcc/c-family/ChangeLog:
> 
> 	PR tree-optimization/90879
> 	* c.opt (-Wstring-compare): New option.
> 
> gcc/testsuite/ChangeLog:
> 
> 	PR tree-optimization/90879
> 	* gcc.dg/Wstring-compare-2.c: New test.
> 	* gcc.dg/Wstring-compare.c: New test.
> 	* gcc.dg/strcmpopt_3.c: Scan the optmized dump instead of strlen.
> 	* gcc.dg/strcmpopt_6.c: New test.
> 	* gcc.dg/strlenopt-65.c: Remove uinnecessary declarations, add
> 	test cases.
> 	* gcc.dg/strlenopt-66.c: Run it.
> 	* gcc.dg/strlenopt-67.c: New test.
> 	* gcc.dg/strlenopt-68.c: New test.
> 
> gcc/ChangeLog:
> 
> 	PR tree-optimization/90879
> 	* builtins.c (check_access): Avoid using maxbound when null.
> 	* calls.c (maybe_warn_nonstring_arg): Adjust to get_range_strlen change.
> 	* doc/invoke.texi (-Wstring-compare): Document new warning option.
> 	* gengtype-state.c (state_ident_st): Use a zero-length array instead.
> 	(state_token_st): Same.  Make last.
> 	(state_ident_by_name): Allocate enough space for terminating nul.
> 	* gimple-fold.c (get_range_strlen_tree): Make setting maxbound
> 	conditional.
> 	(get_range_strlen): Overwrite initial maxbound when non-null.
> 	* gimple-ssa-sprintf.c (get_string_length): Adjust to get_range_strlen
> 	change.
> 	* tree-ssa-strlen.c (maybe_diag_stxncpy_trunc): Same.
> 	(used_only_for_zero_equality): New function.
> 	(handle_builtin_memcmp): Call it.
> 	(determine_min_objsize): Return an integer instead of tree.
> 	(get_len_or_size, strxcmp_eqz_result): New functions.
> 	(maybe_warn_pointless_strcmp): New function.
> 	(handle_builtin_string_cmp): Call it.  Fold zero-equality of strcmp
> 	between a longer string and a smaller array.
> 
> diff --git a/gcc/gengtype-state.c b/gcc/gengtype-state.c
> index 03f40694ec6..80a8b57e9a2 100644
> --- a/gcc/gengtype-state.c
> +++ b/gcc/gengtype-state.c
> @@ -79,6 +79,14 @@ enum state_token_en
>    STOK_NAME                     /* hash-consed name or identifier.  */
>  };
>  
> +/* Suppress warning: ISO C forbids zero-size array for stok_string
> +   below.  The arrays are treated as flexible array members but in
> +   otherwise an empty struct or as a member of a union cannot be
> +   declared as such.  They must have zero size to keep GCC from
> +   assuming their bound reflect their size.  */
> +#pragma GCC diagnostic push
> +#pragma GCC diagnostic ignored "-Wpedantic"
> +
>  
>  /* Structure and hash-table used to share identifiers or names.  */
>  struct state_ident_st
> @@ -86,11 +94,10 @@ struct state_ident_st
>    /* TODO: We could improve the parser by reserving identifiers for
>       state keywords and adding a keyword number for them.  That would
>       mean adding another field in this state_ident_st struct.  */
> -  char stid_name[1];		/* actually bigger & null terminated */
> +  char stid_name[0];		/* actually bigger & null terminated */
>  };
>  static htab_t state_ident_tab;
>  
> -
>  /* The state_token_st structure is for lexical tokens in the read
>     state file.  The stok_kind field discriminates the union.  Tokens
>     are allocated by peek_state_token which calls read_a_state_token
> @@ -110,14 +117,15 @@ struct state_token_st
>    union		                        /* discriminated by stok_kind! */
>    {
>      int stok_num;			/* when STOK_INTEGER */
> -    char stok_string[1];		/* when STOK_STRING, actual size is
> -					   bigger and null terminated */
>      struct state_ident_st *stok_ident;	/* when STOK_IDENT */
>      void *stok_ptr;		        /* null otherwise */
> +    char stok_string[0];		/* when STOK_STRING, actual size is
> +					   bigger and null terminated */
>    }
>    stok_un;
>  };
>  
> +#pragma GCC diagnostic pop
I think these three hunks should be a separate discussion about the code
construct we use for represent a trailing array and should be left out
of this patch.


>  
>  
>  
> @@ -325,7 +333,7 @@ state_ident_by_name (const char *name, enum insert_option optins)
>    namlen = strlen (name);
>    stid =
>      (struct state_ident_st *) xmalloc (sizeof (struct state_ident_st) +
> -				       namlen);
> +				       namlen + 1);
>    memset (stid, 0, sizeof (struct state_ident_st) + namlen);
>    strcpy (stid->stid_name, name);
>    *slot = stid;
How did you find this goof?



> diff --git a/gcc/gimple-fold.c b/gcc/gimple-fold.c
> index fc57fb45e3a..582768090ae 100644
> --- a/gcc/gimple-fold.c
> +++ b/gcc/gimple-fold.c
> @@ -1346,6 +1346,10 @@ get_range_strlen_tree (tree arg, bitmap *visited, strlen_range_kind rkind,
>  	}
>      }
>  
> +  /* Set if VAL represents the maximum length based on array size (set
> +     when exact length cannot be determined).  */
> +  bool maxbound = false;
> +
>    if (!val && rkind == SRK_LENRANGE)
>      {
>        if (TREE_CODE (arg) == ADDR_EXPR)
> @@ -1441,6 +1445,7 @@ get_range_strlen_tree (tree arg, bitmap *visited, strlen_range_kind rkind,
>  	      pdata->minlen = ssize_int (0);
>  	    }
>  	}
> +      maxbound = true;
>      }
>  
>    if (!val)
> @@ -1454,7 +1459,7 @@ get_range_strlen_tree (tree arg, bitmap *visited, strlen_range_kind rkind,
>  	  && tree_int_cst_lt (val, pdata->minlen)))
>      pdata->minlen = val;
>  
> -  if (pdata->maxbound)
> +  if (pdata->maxbound && TREE_CODE (pdata->maxbound) == INTEGER_CST)
>      {
>        /* Adjust the tighter (more optimistic) string length bound
>  	 if necessary and proceed to adjust the more conservative
So inside the conditional guarded by the test you're changing above we have:

     if (TREE_CODE (val) == INTEGER_CST)
        {
          if (TREE_CODE (pdata->maxbound) == INTEGER_CST)
            {
              if (tree_int_cst_lt (pdata->maxbound, val))
                pdata->maxbound = val;
            }
          else
            pdata->maxbound = build_all_ones_cst (size_type_node);
        }

Isn't the inner test that pdata->maxbound == INTEGER_CST always true and
we should remove the test and the else clause?  Does the else clause
need to be handled elsewhere (I don't see that it would be handled after
your changes).  Or perhaps it just doesn't matter...




> @@ -1653,8 +1661,11 @@ get_range_strlen (tree arg, bitmap *visited,
>  
>  /* 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.  ELTSIZE
> -   is the expected size of the string element in bytes: 1 for char and
> +   of lengths cannot be determined, and store all in *PDATA which must
> +   be zero-initialized on input except PDATA->MAXBOUND may be set to
> +   a non-null tree node other than INTEGER_CST to request to have it
> +   set to the length of the longest string in a PHI.  ELTSIZE is
> +   the expected size of the string element in bytes: 1 for char and
Is there any reason we can't just make a clean distinction between input
and output objects in this routine?  As an API this seems awkward at best.



> @@ -2862,51 +2865,78 @@ handle_builtin_memset (gimple_stmt_iterator *gsi)
>    return true;
>  }
>  
> -/* Handle a call to memcmp.  We try to handle small comparisons by
> -   converting them to load and compare, and replacing the call to memcmp
> -   with a __builtin_memcmp_eq call where possible.
> -   return true when call is transformed, return false otherwise.  */
> +/* Return a pointer to the first such equality expression if RES is used
> +   only in experessions testing its equality to zero, and null otherwise.  */
s/experessions/expressions/


>  
> -static bool
> -handle_builtin_memcmp (gimple_stmt_iterator *gsi)
> +static gimple*
> +used_only_for_zero_equality (tree res)
Nit.  A space between "gimple" and "*".




> +
> +/* If IDX1 and IDX2 refer to strings A and B of unequal lengths, return
> +   the result of 0 == strncmp (A, B, BOUND) (which is the same as strcmp
> +   for s sufficiently large BOUND).  If the result is based on the length
> +   of one string being greater than the longest string that would fit in
> +   the array pointer to by the argument, set *PLEN and *PSIZE to
> +   the corresponding length (or its complement when the string is known
> +   to be at least as long and need not be nul-terminated) and size.
> +   Otherwise return null.  */
s/null/NULL/


> +/* Diagnose pointless calls to strcmp whose result is used in equality
> +   epxpressions that evaluate to a constant due to one argument being
> +   longer than the size of the other.  */
s/epxressions/expressions/



> +/* Optimize a call to strcmp or strncmp either by folding it to a constant
> +   when possible or by transforming the latter to the former.  Warn about
> +   calls where the length of one argument is greater than the size of
> +   the array to which the other aargument points if the latter's length
> +   is not known.  Return true when the call has been transformed into
> +   another and false otherwise.  */
s/aargument/argument/


>  
> -  unsigned HOST_WIDE_INT var_sizei = 0;
> -  /* try to determine the minimum size of the object pointed by var_string.  */
> -  tree size = determine_min_objsize (var_string);
> +  /* Determine either the length or the size of each of the string
> +     orguments, whichever is available.  */
s/orguments/arguments/


Generally looks reasonable.  Just a couple things.  One, whether or not
we can clean up the API changes to get_range_strlen, cleanups to
get_range_strlen_tree and whether or not the dropped case from
get_range_strlen_tree needs to be handled, and if so where should it go.

jeff


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]