diff mbox

tree-ssa-strlen improvements (PR tree-optimization/71625)

Message ID 20160628142341.GD7387@tucnak.redhat.com
State New
Headers show

Commit Message

Jakub Jelinek June 28, 2016, 2:23 p.m. UTC 
Hi!

This is just first small step towards this PR.
It brings the ADDR_EXPR of DECL_P bases roughly on the same level as
SSA_NAMEs pointers - so get_stridx_plus_constant works for them, and
more importantly, before this patch there was a very severe bug in
addr_stridxptr (missing list = list->next; in the loop), which meant that
inside of a single decl we were tracking at most one string length, rather
than the former 16 (or now 32) limit.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

As a follow-up, I'd like to introduce string length at least N, where we
don't know the exact string length, but we know there are no '\0' chars
within N bytes.

2016-06-28  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/71625
	* tree-ssa-strlen.c (get_addr_stridx): Add PTR argument.  Assume list
	is sorted by ascending list->offset.  If PTR is non-NULL and there is
	previous strinfo, call get_stridx_plus_constant.
	(get_stridx): Pass exp as second argument to get_addr_stridx.
	(addr_stridxptr): Add missing list = list->next, so that there can be
	more than one entries in the list.  Bump limit from 16 to 32.  Ensure
	the list is sorted by ascending list->offset.
	(get_stridx_plus_constant): Adjust so that it can be also called with
	ADDR_EXPR instead of SSA_NAME as PTR.
	(handle_char_store): Pass NULL_TREE as second argument to
	get_addr_stridx.

	* gcc.dg/strlenopt-28.c: New test.


	Jakub

Comments

Richard Biener June 29, 2016, 8:16 a.m. UTC | #1 
On Tue, 28 Jun 2016, Jakub Jelinek wrote:

> Hi!
> 
> This is just first small step towards this PR.
> It brings the ADDR_EXPR of DECL_P bases roughly on the same level as
> SSA_NAMEs pointers - so get_stridx_plus_constant works for them, and
> more importantly, before this patch there was a very severe bug in
> addr_stridxptr (missing list = list->next; in the loop), which meant that
> inside of a single decl we were tracking at most one string length, rather
> than the former 16 (or now 32) limit.
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

Ok.

Thanks,
Richard.

> As a follow-up, I'd like to introduce string length at least N, where we
> don't know the exact string length, but we know there are no '\0' chars
> within N bytes.
> 
> 2016-06-28  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR tree-optimization/71625
> 	* tree-ssa-strlen.c (get_addr_stridx): Add PTR argument.  Assume list
> 	is sorted by ascending list->offset.  If PTR is non-NULL and there is
> 	previous strinfo, call get_stridx_plus_constant.
> 	(get_stridx): Pass exp as second argument to get_addr_stridx.
> 	(addr_stridxptr): Add missing list = list->next, so that there can be
> 	more than one entries in the list.  Bump limit from 16 to 32.  Ensure
> 	the list is sorted by ascending list->offset.
> 	(get_stridx_plus_constant): Adjust so that it can be also called with
> 	ADDR_EXPR instead of SSA_NAME as PTR.
> 	(handle_char_store): Pass NULL_TREE as second argument to
> 	get_addr_stridx.
> 
> 	* gcc.dg/strlenopt-28.c: New test.
> 
> --- gcc/tree-ssa-strlen.c.jj	2016-06-28 10:21:22.103693623 +0200
> +++ gcc/tree-ssa-strlen.c	2016-06-28 13:41:56.797718522 +0200
> @@ -159,10 +159,10 @@ get_strinfo (int idx)
>  /* Helper function for get_stridx.  */
>  
>  static int
> -get_addr_stridx (tree exp)
> +get_addr_stridx (tree exp, tree ptr)
>  {
>    HOST_WIDE_INT off;
> -  struct stridxlist *list;
> +  struct stridxlist *list, *last = NULL;
>    tree base;
>  
>    if (!decl_to_stridxlist_htab)
> @@ -180,9 +180,22 @@ get_addr_stridx (tree exp)
>      {
>        if (list->offset == off)
>  	return list->idx;
> +      if (list->offset > off)
> +	return 0;
> +      last = list;
>        list = list->next;
>      }
>    while (list);
> +
> +  if (ptr && last && last->idx > 0)
> +    {
> +      strinfo *si = get_strinfo (last->idx);
> +      if (si
> +	  && si->length
> +	  && TREE_CODE (si->length) == INTEGER_CST
> +	  && compare_tree_int (si->length, off - last->offset) != -1)
> +	return get_stridx_plus_constant (si, off - last->offset, ptr);
> +    }
>    return 0;
>  }
>  
> @@ -234,7 +247,7 @@ get_stridx (tree exp)
>  
>    if (TREE_CODE (exp) == ADDR_EXPR)
>      {
> -      int idx = get_addr_stridx (TREE_OPERAND (exp, 0));
> +      int idx = get_addr_stridx (TREE_OPERAND (exp, 0), exp);
>        if (idx != 0)
>  	return idx;
>      }
> @@ -304,15 +317,29 @@ addr_stridxptr (tree exp)
>    if (existed)
>      {
>        int i;
> -      for (i = 0; i < 16; i++)
> +      stridxlist *before = NULL;
> +      for (i = 0; i < 32; i++)
>  	{
>  	  if (list->offset == off)
>  	    return &list->idx;
> +	  if (list->offset > off && before == NULL)
> +	    before = list;
>  	  if (list->next == NULL)
>  	    break;
> +	  list = list->next;
>  	}
> -      if (i == 16)
> +      if (i == 32)
>  	return NULL;
> +      if (before)
> +	{
> +	  list = before;
> +	  before = XOBNEW (&stridx_obstack, struct stridxlist);
> +	  *before = *list;
> +	  list->next = before;
> +	  list->offset = off;
> +	  list->idx = 0;
> +	  return &list->idx;
> +	}
>        list->next = XOBNEW (&stridx_obstack, struct stridxlist);
>        list = list->next;
>      }
> @@ -613,9 +640,7 @@ verify_related_strinfos (strinfo *origsi
>  static int
>  get_stridx_plus_constant (strinfo *basesi, HOST_WIDE_INT off, tree ptr)
>  {
> -  gcc_checking_assert (TREE_CODE (ptr) == SSA_NAME);
> -
> -  if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr))
> +  if (TREE_CODE (ptr) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr))
>      return 0;
>  
>    if (basesi->length == NULL_TREE
> @@ -633,7 +658,8 @@ get_stridx_plus_constant (strinfo *bases
>        || TREE_CODE (si->length) != INTEGER_CST)
>      return 0;
>  
> -  if (ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
> +  if (TREE_CODE (ptr) == SSA_NAME
> +      && ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
>      ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
>  
>    gcc_checking_assert (compare_tree_int (si->length, off) != -1);
> @@ -651,6 +677,7 @@ get_stridx_plus_constant (strinfo *bases
>  	{
>  	  if (r == 0)
>  	    {
> +	      gcc_assert (TREE_CODE (ptr) == SSA_NAME);
>  	      ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = si->idx;
>  	      return si->idx;
>  	    }
> @@ -2063,7 +2090,7 @@ handle_char_store (gimple_stmt_iterator
>  	}
>      }
>    else
> -    idx = get_addr_stridx (lhs);
> +    idx = get_addr_stridx (lhs, NULL_TREE);
>  
>    if (idx > 0)
>      {
> --- gcc/testsuite/gcc.dg/strlenopt-28.c.jj	2016-06-28 13:57:06.768016510 +0200
> +++ gcc/testsuite/gcc.dg/strlenopt-28.c	2016-06-28 13:55:01.000000000 +0200
> @@ -0,0 +1,59 @@
> +/* { dg-do run } */
> +/* { dg-options "-O2 -fdump-tree-strlen" } */
> +
> +#include "strlenopt.h"
> +
> +volatile int v;
> +
> +size_t
> +f1 (void)
> +{
> +  char a[30];
> +  v += 1;
> +  memcpy (a, "1234567", 8);
> +  memcpy (a + 7, "89abcdefg", 10);
> +  memcpy (a + 16, "h", 2);
> +  return strlen (a);	// This strlen should be optimized into 17.
> +}
> +
> +size_t
> +f2 (void)
> +{
> +  char a[30];
> +  v += 2;
> +  strcpy (a, "1234567");
> +  strcpy (a + 7, "89abcdefg");
> +  strcpy (a + 16, "h");
> +  return strlen (a);	// This strlen should be optimized into 17.
> +}
> +
> +size_t
> +f3 (char *a)
> +{
> +  v += 3;
> +  memcpy (a, "1234567", 8);
> +  memcpy (a + 7, "89abcdefg", 10);
> +  memcpy (a + 16, "h", 2);
> +  return strlen (a);	// This strlen should be optimized into 17.
> +}
> +
> +size_t
> +f4 (char *a)
> +{
> +  v += 4;
> +  strcpy (a, "1234567");
> +  strcpy (a + 7, "89abcdefg");
> +  strcpy (a + 16, "h");
> +  return strlen (a);	// This strlen should be optimized into 17.
> +}
> +
> +int
> +main ()
> +{
> +  char a[30];
> +  if (f1 () != 17 || f2 () != 17 || f3 (a) != 17 || f4 (a) != 17)
> +    abort ();
> +  return 0;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "strlen \\(" 0 "strlen" } } */
> 
> 	Jakub
> 
>
Christophe Lyon June 29, 2016, 1:11 p.m. UTC | #2 
On 28 June 2016 at 16:23, Jakub Jelinek <jakub@redhat.com> wrote:
> Hi!
>
> This is just first small step towards this PR.
> It brings the ADDR_EXPR of DECL_P bases roughly on the same level as
> SSA_NAMEs pointers - so get_stridx_plus_constant works for them, and
> more importantly, before this patch there was a very severe bug in
> addr_stridxptr (missing list = list->next; in the loop), which meant that
> inside of a single decl we were tracking at most one string length, rather
> than the former 16 (or now 32) limit.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
>
> As a follow-up, I'd like to introduce string length at least N, where we
> don't know the exact string length, but we know there are no '\0' chars
> within N bytes.
>
> 2016-06-28  Jakub Jelinek  <jakub@redhat.com>
>
>         PR tree-optimization/71625
>         * tree-ssa-strlen.c (get_addr_stridx): Add PTR argument.  Assume list
>         is sorted by ascending list->offset.  If PTR is non-NULL and there is
>         previous strinfo, call get_stridx_plus_constant.
>         (get_stridx): Pass exp as second argument to get_addr_stridx.
>         (addr_stridxptr): Add missing list = list->next, so that there can be
>         more than one entries in the list.  Bump limit from 16 to 32.  Ensure
>         the list is sorted by ascending list->offset.
>         (get_stridx_plus_constant): Adjust so that it can be also called with
>         ADDR_EXPR instead of SSA_NAME as PTR.
>         (handle_char_store): Pass NULL_TREE as second argument to
>         get_addr_stridx.
>
>         * gcc.dg/strlenopt-28.c: New test.
>

Hi,

This causes GCC builds failures on arm-linux* targets, while building glibc:

/tmp/1440207_1.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/bin/arm-none-linux-gnueabi-gcc
ns_print.c -c -std=gnu99 -fgnu89-inline  -O2 -Wall -Winline -Wundef
-Wwrite-strings -fmerge-
all-constants -frounding-math -g -Wno-strict-prototypes
-Wno-write-strings -Wstrict-prototypes   -fPIC   -fstack-protector
-I../include -I/tmp/1440207_1.tmpdir/aci-gcc-fsf/builds/gc
c-fsf-gccsrc/obj-arm-none-linux-gnueabi/glibc-1/resolv
-I/tmp/1440207_1.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-arm-none-linux-gnueabi/glibc-1
 -I../sysdeps/unix/sysv/linux/arm  -
I../nptl/sysdeps/unix/sysv/linux  -I../nptl/sysdeps/pthread
-I../sysdeps/pthread  -I../sysdeps/unix/sysv/linux  -I../sysdeps/gnu
-I../sysdeps/unix/inet  -I../nptl/sysdeps/unix/sysv  -
I../sysdeps/unix/sysv  -I../sysdeps/unix/arm  -I../nptl/sysdeps/unix
-I../sysdeps/unix  -I../sysdeps/posix
-I../sysdeps/arm/armv7/multiarch  -I../sysdeps/arm/armv7
-I../sysdeps/arm/a
rmv6t2  -I../sysdeps/arm/armv6  -I../sysdeps/arm/nptl
-I../sysdeps/arm/include -I../sysdeps/arm  -I../sysdeps/arm/soft-fp
-I../sysdeps/wordsize-32  -I../sysdeps/ieee754/flt-32  -I../s
ysdeps/ieee754/dbl-64  -I../sysdeps/ieee754  -I../sysdeps/generic
-I../nptl  -I.. -I../libio -I. -nostdinc -isystem
/tmp/1440207_1.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/lib/gc
c/arm-none-linux-gnueabi/7.0.0/include -isystem
/tmp/1440207_1.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/lib/gcc/arm-none-linux-gnueabi/7.0.0/include-fixed
-isystem /tmp/1440207_1.
tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/sysroot-arm-none-linux-gnueabi/usr/include
 -D_LIBC_REENTRANT -include ../include/libc-symbols.h  -DPIC -DSHARED
-DNOT_IN_libc=1 -DIS_IN_libreso
lv=1 -DIN_LIB=libresolv    -Dgethostbyname=res_gethostbyname
-Dgethostbyname2=res_gethostbyname2 -Dgethostbyaddr=res_gethostbyaddr
-Dgetnetbyname=res_getnetbyname -Dgetnetbyaddr=res_get
netbyaddr -o /tmp/1440207_1.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-arm-none-linux-gnueabi/glibc-1/resolv/ns_print.os
-MD -MP -MF /tmp/1440207_1.tmpdir/aci-gcc-fsf/builds/gcc-fsf-g
ccsrc/obj-arm-none-linux-gnueabi/glibc-1/resolv/ns_print.os.dt -MT
/tmp/1440207_1.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-arm-none-linux-gnueabi/glibc-1/resolv/ns_print.os

ns_print.c: In function 'ns_sprintrrf':
ns_print.c:94:1: internal compiler error: in get_stridx_plus_constant,
at tree-ssa-strlen.c:680
 ns_sprintrrf(const u_char *msg, size_t msglen,
 ^~~~~~~~~~~~
0xcf1387 get_stridx_plus_constant
        /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-strlen.c:680
0xcf15ba get_addr_stridx
        /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-strlen.c:197
0xcf1776 get_stridx
        /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-strlen.c:250
0xcf6448 handle_pointer_plus
        /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-strlen.c:2028
0xcf6448 strlen_optimize_stmt
        /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-strlen.c:2297
0xcf6fd9 strlen_dom_walker::before_dom_children(basic_block_def*)
        /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-strlen.c:2456
0x115c27c dom_walker::walk(basic_block_def*)
        /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/domwalk.c:265
0xcef80a execute
        /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-strlen.c:2528


I do not have a preprocessed file yet, I'll prepare one if you need.

Christophe.

> --- gcc/tree-ssa-strlen.c.jj    2016-06-28 10:21:22.103693623 +0200
> +++ gcc/tree-ssa-strlen.c       2016-06-28 13:41:56.797718522 +0200
> @@ -159,10 +159,10 @@ get_strinfo (int idx)
>  /* Helper function for get_stridx.  */
>
>  static int
> -get_addr_stridx (tree exp)
> +get_addr_stridx (tree exp, tree ptr)
>  {
>    HOST_WIDE_INT off;
> -  struct stridxlist *list;
> +  struct stridxlist *list, *last = NULL;
>    tree base;
>
>    if (!decl_to_stridxlist_htab)
> @@ -180,9 +180,22 @@ get_addr_stridx (tree exp)
>      {
>        if (list->offset == off)
>         return list->idx;
> +      if (list->offset > off)
> +       return 0;
> +      last = list;
>        list = list->next;
>      }
>    while (list);
> +
> +  if (ptr && last && last->idx > 0)
> +    {
> +      strinfo *si = get_strinfo (last->idx);
> +      if (si
> +         && si->length
> +         && TREE_CODE (si->length) == INTEGER_CST
> +         && compare_tree_int (si->length, off - last->offset) != -1)
> +       return get_stridx_plus_constant (si, off - last->offset, ptr);
> +    }
>    return 0;
>  }
>
> @@ -234,7 +247,7 @@ get_stridx (tree exp)
>
>    if (TREE_CODE (exp) == ADDR_EXPR)
>      {
> -      int idx = get_addr_stridx (TREE_OPERAND (exp, 0));
> +      int idx = get_addr_stridx (TREE_OPERAND (exp, 0), exp);
>        if (idx != 0)
>         return idx;
>      }
> @@ -304,15 +317,29 @@ addr_stridxptr (tree exp)
>    if (existed)
>      {
>        int i;
> -      for (i = 0; i < 16; i++)
> +      stridxlist *before = NULL;
> +      for (i = 0; i < 32; i++)
>         {
>           if (list->offset == off)
>             return &list->idx;
> +         if (list->offset > off && before == NULL)
> +           before = list;
>           if (list->next == NULL)
>             break;
> +         list = list->next;
>         }
> -      if (i == 16)
> +      if (i == 32)
>         return NULL;
> +      if (before)
> +       {
> +         list = before;
> +         before = XOBNEW (&stridx_obstack, struct stridxlist);
> +         *before = *list;
> +         list->next = before;
> +         list->offset = off;
> +         list->idx = 0;
> +         return &list->idx;
> +       }
>        list->next = XOBNEW (&stridx_obstack, struct stridxlist);
>        list = list->next;
>      }
> @@ -613,9 +640,7 @@ verify_related_strinfos (strinfo *origsi
>  static int
>  get_stridx_plus_constant (strinfo *basesi, HOST_WIDE_INT off, tree ptr)
>  {
> -  gcc_checking_assert (TREE_CODE (ptr) == SSA_NAME);
> -
> -  if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr))
> +  if (TREE_CODE (ptr) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr))
>      return 0;
>
>    if (basesi->length == NULL_TREE
> @@ -633,7 +658,8 @@ get_stridx_plus_constant (strinfo *bases
>        || TREE_CODE (si->length) != INTEGER_CST)
>      return 0;
>
> -  if (ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
> +  if (TREE_CODE (ptr) == SSA_NAME
> +      && ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
>      ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
>
>    gcc_checking_assert (compare_tree_int (si->length, off) != -1);
> @@ -651,6 +677,7 @@ get_stridx_plus_constant (strinfo *bases
>         {
>           if (r == 0)
>             {
> +             gcc_assert (TREE_CODE (ptr) == SSA_NAME);
>               ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = si->idx;
>               return si->idx;
>             }
> @@ -2063,7 +2090,7 @@ handle_char_store (gimple_stmt_iterator
>         }
>      }
>    else
> -    idx = get_addr_stridx (lhs);
> +    idx = get_addr_stridx (lhs, NULL_TREE);
>
>    if (idx > 0)
>      {
> --- gcc/testsuite/gcc.dg/strlenopt-28.c.jj      2016-06-28 13:57:06.768016510 +0200
> +++ gcc/testsuite/gcc.dg/strlenopt-28.c 2016-06-28 13:55:01.000000000 +0200
> @@ -0,0 +1,59 @@
> +/* { dg-do run } */
> +/* { dg-options "-O2 -fdump-tree-strlen" } */
> +
> +#include "strlenopt.h"
> +
> +volatile int v;
> +
> +size_t
> +f1 (void)
> +{
> +  char a[30];
> +  v += 1;
> +  memcpy (a, "1234567", 8);
> +  memcpy (a + 7, "89abcdefg", 10);
> +  memcpy (a + 16, "h", 2);
> +  return strlen (a);   // This strlen should be optimized into 17.
> +}
> +
> +size_t
> +f2 (void)
> +{
> +  char a[30];
> +  v += 2;
> +  strcpy (a, "1234567");
> +  strcpy (a + 7, "89abcdefg");
> +  strcpy (a + 16, "h");
> +  return strlen (a);   // This strlen should be optimized into 17.
> +}
> +
> +size_t
> +f3 (char *a)
> +{
> +  v += 3;
> +  memcpy (a, "1234567", 8);
> +  memcpy (a + 7, "89abcdefg", 10);
> +  memcpy (a + 16, "h", 2);
> +  return strlen (a);   // This strlen should be optimized into 17.
> +}
> +
> +size_t
> +f4 (char *a)
> +{
> +  v += 4;
> +  strcpy (a, "1234567");
> +  strcpy (a + 7, "89abcdefg");
> +  strcpy (a + 16, "h");
> +  return strlen (a);   // This strlen should be optimized into 17.
> +}
> +
> +int
> +main ()
> +{
> +  char a[30];
> +  if (f1 () != 17 || f2 () != 17 || f3 (a) != 17 || f4 (a) != 17)
> +    abort ();
> +  return 0;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "strlen \\(" 0 "strlen" } } */
>
>         Jakub
Jakub Jelinek June 29, 2016, 1:20 p.m. UTC | #3 
On Wed, Jun 29, 2016 at 03:11:07PM +0200, Christophe Lyon wrote:
> This causes GCC builds failures on arm-linux* targets, while building glibc:
> 
> ns_print.c: In function 'ns_sprintrrf':
> ns_print.c:94:1: internal compiler error: in get_stridx_plus_constant,
> at tree-ssa-strlen.c:680
>  ns_sprintrrf(const u_char *msg, size_t msglen,
>  ^~~~~~~~~~~~
> 0xcf1387 get_stridx_plus_constant
>         /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-strlen.c:680
> 0xcf15ba get_addr_stridx
>         /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-strlen.c:197
> 0xcf1776 get_stridx
>         /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-strlen.c:250
> 0xcf6448 handle_pointer_plus
>         /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-strlen.c:2028
> 0xcf6448 strlen_optimize_stmt
>         /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-strlen.c:2297
> 0xcf6fd9 strlen_dom_walker::before_dom_children(basic_block_def*)
>         /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-strlen.c:2456
> 0x115c27c dom_walker::walk(basic_block_def*)
>         /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/domwalk.c:265
> 0xcef80a execute
>         /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-strlen.c:2528
> 
> 
> I do not have a preprocessed file yet, I'll prepare one if you need.

That would be greatly appreciated (plus command line options).
Please file a PR and I'll handle it.  Thanks.

	Jakub
Christophe Lyon June 29, 2016, 9:07 p.m. UTC | #4 
On 29 June 2016 at 15:20, Jakub Jelinek <jakub@redhat.com> wrote:
> On Wed, Jun 29, 2016 at 03:11:07PM +0200, Christophe Lyon wrote:
>> This causes GCC builds failures on arm-linux* targets, while building glibc:
>>
>> ns_print.c: In function 'ns_sprintrrf':
>> ns_print.c:94:1: internal compiler error: in get_stridx_plus_constant,
>> at tree-ssa-strlen.c:680
>>  ns_sprintrrf(const u_char *msg, size_t msglen,
>>  ^~~~~~~~~~~~
>> 0xcf1387 get_stridx_plus_constant
>>         /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-strlen.c:680
>> 0xcf15ba get_addr_stridx
>>         /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-strlen.c:197
>> 0xcf1776 get_stridx
>>         /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-strlen.c:250
>> 0xcf6448 handle_pointer_plus
>>         /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-strlen.c:2028
>> 0xcf6448 strlen_optimize_stmt
>>         /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-strlen.c:2297
>> 0xcf6fd9 strlen_dom_walker::before_dom_children(basic_block_def*)
>>         /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-strlen.c:2456
>> 0x115c27c dom_walker::walk(basic_block_def*)
>>         /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/domwalk.c:265
>> 0xcef80a execute
>>         /tmp/1440207_1.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/tree-ssa-strlen.c:2528
>>
>>
>> I do not have a preprocessed file yet, I'll prepare one if you need.
>
> That would be greatly appreciated (plus command line options).
> Please file a PR and I'll handle it.  Thanks.
>

This is PR 71707.
Sorry for the delay.

Thanks,

Christophe


>         Jakub
diff mbox

Patch

--- gcc/tree-ssa-strlen.c.jj	2016-06-28 10:21:22.103693623 +0200
+++ gcc/tree-ssa-strlen.c	2016-06-28 13:41:56.797718522 +0200
@@ -159,10 +159,10 @@  get_strinfo (int idx)
 /* Helper function for get_stridx.  */
 
 static int
-get_addr_stridx (tree exp)
+get_addr_stridx (tree exp, tree ptr)
 {
   HOST_WIDE_INT off;
-  struct stridxlist *list;
+  struct stridxlist *list, *last = NULL;
   tree base;
 
   if (!decl_to_stridxlist_htab)
@@ -180,9 +180,22 @@  get_addr_stridx (tree exp)
     {
       if (list->offset == off)
 	return list->idx;
+      if (list->offset > off)
+	return 0;
+      last = list;
       list = list->next;
     }
   while (list);
+
+  if (ptr && last && last->idx > 0)
+    {
+      strinfo *si = get_strinfo (last->idx);
+      if (si
+	  && si->length
+	  && TREE_CODE (si->length) == INTEGER_CST
+	  && compare_tree_int (si->length, off - last->offset) != -1)
+	return get_stridx_plus_constant (si, off - last->offset, ptr);
+    }
   return 0;
 }
 
@@ -234,7 +247,7 @@  get_stridx (tree exp)
 
   if (TREE_CODE (exp) == ADDR_EXPR)
     {
-      int idx = get_addr_stridx (TREE_OPERAND (exp, 0));
+      int idx = get_addr_stridx (TREE_OPERAND (exp, 0), exp);
       if (idx != 0)
 	return idx;
     }
@@ -304,15 +317,29 @@  addr_stridxptr (tree exp)
   if (existed)
     {
       int i;
-      for (i = 0; i < 16; i++)
+      stridxlist *before = NULL;
+      for (i = 0; i < 32; i++)
 	{
 	  if (list->offset == off)
 	    return &list->idx;
+	  if (list->offset > off && before == NULL)
+	    before = list;
 	  if (list->next == NULL)
 	    break;
+	  list = list->next;
 	}
-      if (i == 16)
+      if (i == 32)
 	return NULL;
+      if (before)
+	{
+	  list = before;
+	  before = XOBNEW (&stridx_obstack, struct stridxlist);
+	  *before = *list;
+	  list->next = before;
+	  list->offset = off;
+	  list->idx = 0;
+	  return &list->idx;
+	}
       list->next = XOBNEW (&stridx_obstack, struct stridxlist);
       list = list->next;
     }
@@ -613,9 +640,7 @@  verify_related_strinfos (strinfo *origsi
 static int
 get_stridx_plus_constant (strinfo *basesi, HOST_WIDE_INT off, tree ptr)
 {
-  gcc_checking_assert (TREE_CODE (ptr) == SSA_NAME);
-
-  if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr))
+  if (TREE_CODE (ptr) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr))
     return 0;
 
   if (basesi->length == NULL_TREE
@@ -633,7 +658,8 @@  get_stridx_plus_constant (strinfo *bases
       || TREE_CODE (si->length) != INTEGER_CST)
     return 0;
 
-  if (ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
+  if (TREE_CODE (ptr) == SSA_NAME
+      && ssa_ver_to_stridx.length () <= SSA_NAME_VERSION (ptr))
     ssa_ver_to_stridx.safe_grow_cleared (num_ssa_names);
 
   gcc_checking_assert (compare_tree_int (si->length, off) != -1);
@@ -651,6 +677,7 @@  get_stridx_plus_constant (strinfo *bases
 	{
 	  if (r == 0)
 	    {
+	      gcc_assert (TREE_CODE (ptr) == SSA_NAME);
 	      ssa_ver_to_stridx[SSA_NAME_VERSION (ptr)] = si->idx;
 	      return si->idx;
 	    }
@@ -2063,7 +2090,7 @@  handle_char_store (gimple_stmt_iterator
 	}
     }
   else
-    idx = get_addr_stridx (lhs);
+    idx = get_addr_stridx (lhs, NULL_TREE);
 
   if (idx > 0)
     {
--- gcc/testsuite/gcc.dg/strlenopt-28.c.jj	2016-06-28 13:57:06.768016510 +0200
+++ gcc/testsuite/gcc.dg/strlenopt-28.c	2016-06-28 13:55:01.000000000 +0200
@@ -0,0 +1,59 @@ 
+/* { dg-do run } */
+/* { dg-options "-O2 -fdump-tree-strlen" } */
+
+#include "strlenopt.h"
+
+volatile int v;
+
+size_t
+f1 (void)
+{
+  char a[30];
+  v += 1;
+  memcpy (a, "1234567", 8);
+  memcpy (a + 7, "89abcdefg", 10);
+  memcpy (a + 16, "h", 2);
+  return strlen (a);	// This strlen should be optimized into 17.
+}
+
+size_t
+f2 (void)
+{
+  char a[30];
+  v += 2;
+  strcpy (a, "1234567");
+  strcpy (a + 7, "89abcdefg");
+  strcpy (a + 16, "h");
+  return strlen (a);	// This strlen should be optimized into 17.
+}
+
+size_t
+f3 (char *a)
+{
+  v += 3;
+  memcpy (a, "1234567", 8);
+  memcpy (a + 7, "89abcdefg", 10);
+  memcpy (a + 16, "h", 2);
+  return strlen (a);	// This strlen should be optimized into 17.
+}
+
+size_t
+f4 (char *a)
+{
+  v += 4;
+  strcpy (a, "1234567");
+  strcpy (a + 7, "89abcdefg");
+  strcpy (a + 16, "h");
+  return strlen (a);	// This strlen should be optimized into 17.
+}
+
+int
+main ()
+{
+  char a[30];
+  if (f1 () != 17 || f2 () != 17 || f3 (a) != 17 || f4 (a) != 17)
+    abort ();
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "strlen \\(" 0 "strlen" } } */