This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] tree-ssa-strlen improvements (PR tree-optimization/71625)
- From: Jakub Jelinek <jakub at redhat dot com>
- To: Richard Biener <rguenther at suse dot de>
- Cc: gcc-patches at gcc dot gnu dot org
- Date: Tue, 28 Jun 2016 16:23:41 +0200
- Subject: [PATCH] tree-ssa-strlen improvements (PR tree-optimization/71625)
- Authentication-results: sourceware.org; auth=none
- Reply-to: Jakub Jelinek <jakub at redhat dot com>
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.
--- 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