diff options
38 files changed, 3671 insertions, 4 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 19a0a28..8cbbe02 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,19 @@ +2011-09-27 Jakub Jelinek <jakub@redhat.com> + + * common.opt: Add -foptimize-strlen option. + * Makefile.in (OBJS): Add tree-ssa-strlen.o. + (tree-sssa-strlen.o): Add dependencies. + * opts.c (default_options_table): Enable -foptimize-strlen + by default at -O2 if not -Os. + * passes.c (init_optimization_passes): Add pass_strlen + after pass_object_sizes. + * timevar.def (TV_TREE_STRLEN): New timevar. + * params.def (PARAM_MAX_TRACKED_STRLENS): New parameter. + * tree-pass.h (pass_strlen): Declare. + * tree-ssa-strlen.c: New file. + * c-decl.c (merge_decls): If compatible stpcpy prototype + is seen, set implicit_built_in_decls[BUILT_IN_STPCPY]. + 2011-09-27 Tom de Vries <tom@codesourcery.com> PR middle-end/43864 diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 9827d21..2f320a9 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1475,6 +1475,7 @@ OBJS = \ tree-ssa-reassoc.o \ tree-ssa-sccvn.o \ tree-ssa-sink.o \ + tree-ssa-strlen.o \ tree-ssa-structalias.o \ tree-ssa-tail-merge.o \ tree-ssa-ter.o \ @@ -3168,6 +3169,9 @@ tree-ssa-ccp.o : tree-ssa-ccp.c $(TREE_FLOW_H) $(CONFIG_H) \ $(TREE_DUMP_H) $(BASIC_BLOCK_H) $(TREE_PASS_H) langhooks.h $(PARAMS_H) \ tree-ssa-propagate.h value-prof.h $(FLAGS_H) $(TARGET_H) $(DIAGNOSTIC_CORE_H) \ $(DBGCNT_H) tree-pretty-print.h gimple-pretty-print.h gimple-fold.h +tree-ssa-strlen.o : tree-ssa-strlen.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \ + $(TREE_FLOW_H) $(TREE_PASS_H) domwalk.h alloc-pool.h tree-ssa-propagate.h \ + gimple-pretty-print.h $(PARAMS_H) tree-sra.o : tree-sra.c $(CONFIG_H) $(SYSTEM_H) coretypes.h alloc-pool.h \ $(TM_H) $(TREE_H) $(GIMPLE_H) $(CGRAPH_H) $(TREE_FLOW_H) \ $(IPA_PROP_H) $(DIAGNOSTIC_H) statistics.h $(TREE_DUMP_H) $(TIMEVAR_H) \ diff --git a/gcc/c-decl.c b/gcc/c-decl.c index 5d4564a..cb58d32 100644 --- a/gcc/c-decl.c +++ b/gcc/c-decl.c @@ -2369,7 +2369,21 @@ merge_decls (tree newdecl, tree olddecl, tree newtype, tree oldtype) DECL_FUNCTION_CODE (newdecl) = DECL_FUNCTION_CODE (olddecl); C_DECL_DECLARED_BUILTIN (newdecl) = 1; if (new_is_prototype) - C_DECL_BUILTIN_PROTOTYPE (newdecl) = 0; + { + C_DECL_BUILTIN_PROTOTYPE (newdecl) = 0; + if (DECL_BUILT_IN_CLASS (newdecl) == BUILT_IN_NORMAL) + switch (DECL_FUNCTION_CODE (newdecl)) + { + /* If a compatible prototype of these builtin functions + is seen, assume the runtime implements it with the + expected semantics. */ + case BUILT_IN_STPCPY: + implicit_built_in_decls[DECL_FUNCTION_CODE (newdecl)] + = built_in_decls[DECL_FUNCTION_CODE (newdecl)]; + default: + break; + } + } else C_DECL_BUILTIN_PROTOTYPE (newdecl) = C_DECL_BUILTIN_PROTOTYPE (olddecl); diff --git a/gcc/common.opt b/gcc/common.opt index 50d7904..c7c523c 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -1961,6 +1961,10 @@ ftree-fre Common Report Var(flag_tree_fre) Optimization Enable Full Redundancy Elimination (FRE) on trees +foptimize-strlen +Common Report Var(flag_optimize_strlen) Optimization +Enable string length optimizations on trees + ftree-loop-distribution Common Report Var(flag_tree_loop_distribution) Optimization Enable loop distribution on trees diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog index c8dc519..24068c8 100644 --- a/gcc/cp/ChangeLog +++ b/gcc/cp/ChangeLog @@ -1,3 +1,8 @@ +2011-09-27 Jakub Jelinek <jakub@redhat.com> + + * decl.c (duplicate_decls): If compatible stpcpy prototype + is seen, set implicit_built_in_decls[BUILT_IN_STPCPY]. + 2011-09-26 Jason Merrill <jason@redhat.com> PR c++/45012 diff --git a/gcc/cp/decl.c b/gcc/cp/decl.c index 45bf6a1..30f92da 100644 --- a/gcc/cp/decl.c +++ b/gcc/cp/decl.c @@ -2135,6 +2135,18 @@ duplicate_decls (tree newdecl, tree olddecl, bool newdecl_is_friend) /* If we're keeping the built-in definition, keep the rtl, regardless of declaration matches. */ COPY_DECL_RTL (olddecl, newdecl); + if (DECL_BUILT_IN_CLASS (newdecl) == BUILT_IN_NORMAL) + switch (DECL_FUNCTION_CODE (newdecl)) + { + /* If a compatible prototype of these builtin functions + is seen, assume the runtime implements it with the + expected semantics. */ + case BUILT_IN_STPCPY: + implicit_built_in_decls[DECL_FUNCTION_CODE (newdecl)] + = built_in_decls[DECL_FUNCTION_CODE (newdecl)]; + default: + break; + } } DECL_RESULT (newdecl) = DECL_RESULT (olddecl); diff --git a/gcc/passes.c b/gcc/passes.c index 88b7147..4d8ca6e 100644 --- a/gcc/passes.c +++ b/gcc/passes.c @@ -1,7 +1,7 @@ /* Top level of GCC compilers (cc1, cc1plus, etc.) Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998, - 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 - Free Software Foundation, Inc. + 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, + 2011 Free Software Foundation, Inc. This file is part of GCC. @@ -1321,6 +1321,7 @@ init_optimization_passes (void) NEXT_PASS (pass_forwprop); NEXT_PASS (pass_phiopt); NEXT_PASS (pass_object_sizes); + NEXT_PASS (pass_strlen); NEXT_PASS (pass_ccp); NEXT_PASS (pass_copy_prop); NEXT_PASS (pass_cse_sincos); diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index c237ebb..68c5d28 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,31 @@ +2011-09-27 Jakub Jelinek <jakub@redhat.com> + + * gcc.dg/strlenopt-1.c: New test. + * gcc.dg/strlenopt-1f.c: New test. + * gcc.dg/strlenopt-2.c: New test. + * gcc.dg/strlenopt-2f.c: New test. + * gcc.dg/strlenopt-3.c: New test. + * gcc.dg/strlenopt-4.c: New test. + * gcc.dg/strlenopt-4g.c: New test. + * gcc.dg/strlenopt-4gf.c: New test. + * gcc.dg/strlenopt-5.c: New test. + * gcc.dg/strlenopt-6.c: New test. + * gcc.dg/strlenopt-7.c: New test. + * gcc.dg/strlenopt-8.c: New test. + * gcc.dg/strlenopt-9.c: New test. + * gcc.dg/strlenopt-10.c: New test. + * gcc.dg/strlenopt-11.c: New test. + * gcc.dg/strlenopt-12.c: New test. + * gcc.dg/strlenopt-12g.c: New test. + * gcc.dg/strlenopt-13.c: New test. + * gcc.dg/strlenopt-14g.c: New test. + * gcc.dg/strlenopt-14gf.c: New test. + * gcc.dg/strlenopt-15.c: New test. + * gcc.dg/strlenopt-16g.c: New test. + * gcc.dg/strlenopt-17g.c: New test. + * gcc.dg/strlenopt-18g.c: New test. + * gcc.dg/strlenopt.h: New file. + 2011-09-27 Tom de Vries <tom@codesourcery.com> PR middle-end/43864 diff --git a/gcc/testsuite/gcc.dg/strlenopt-1.c b/gcc/testsuite/gcc.dg/strlenopt-1.c new file mode 100644 index 0000000..5bc4f0c --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-1.c @@ -0,0 +1,47 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#include "strlenopt.h" + +__attribute__((noinline, noclone)) char * +foo (char *p, char *r) +{ + char *q = malloc (strlen (p) + strlen (r) + 64); + if (q == NULL) return NULL; + /* This strcpy can be optimized into memcpy, using the remembered + strlen (p). */ + strcpy (q, p); + /* These two strcat can be optimized into memcpy. The first one + could be even optimized into a *ptr = '/'; store as the '\0' + is immediately overwritten. */ + strcat (q, "/"); + strcat (q, "abcde"); + /* Due to inefficient PTA (PR50262) the above calls invalidate + string length of r, so it is optimized just into strcpy instead + of memcpy. */ + strcat (q, r); + return q; +} + +int +main () +{ + char *volatile p = "string1"; + char *volatile r = "string2"; + char *q = foo (p, r); + if (q != NULL) + { + if (strcmp (q, "string1/abcdestring2")) + abort (); + free (q); + } + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 2 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 3 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-10.c b/gcc/testsuite/gcc.dg/strlenopt-10.c new file mode 100644 index 0000000..a18c06a --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-10.c @@ -0,0 +1,80 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#include "strlenopt.h" + +__attribute__((noinline, noclone)) size_t +fn1 (char *p) +{ + char *q; + /* This can be optimized into memcpy and the size can be decreased to one, + as it is immediately overwritten. */ + strcpy (p, "z"); + q = strchr (p, '\0'); + *q = 32; + /* This strlen can't be optimized away, string length is unknown here. */ + return strlen (p); +} + +__attribute__((noinline, noclone)) void +fn2 (char *p, const char *z, size_t *lp) +{ + char *q, *r; + char buf[64]; + size_t l[10]; + /* The first strlen stays, all the strcpy calls can be optimized + into memcpy and all other strlen calls and all strchr calls + optimized away. */ + l[0] = strlen (z); + strcpy (buf, z); + strcpy (p, "abcde"); + q = strchr (p, '\0'); + strcpy (q, "efghi"); + r = strchr (q, '\0'); + strcpy (r, "jkl"); + l[1] = strlen (p); + l[2] = strlen (q); + l[3] = strlen (r); + strcpy (r, buf); + l[4] = strlen (p); + l[5] = strlen (q); + l[6] = strlen (r); + strcpy (r, "mnopqr"); + l[7] = strlen (p); + l[8] = strlen (q); + l[9] = strlen (r); + memcpy (lp, l, sizeof l); +} + +int +main () +{ + char buf[64]; + size_t l[10]; + const char *volatile z = "ABCDEFG"; + memset (buf, '\0', sizeof buf); + if (fn1 (buf) != 2 || buf[0] != 'z' || buf[1] != 32 || buf[2] != '\0') + abort (); + fn2 (buf, z, l); + if (memcmp (buf, "abcdeefghimnopqr", 17) != 0) + abort (); + if (l[0] != 7) + abort (); + if (l[1] != 13 || l[2] != 8 || l[3] != 3) + abort (); + if (l[4] != 17 || l[5] != 12 || l[6] != 7) + abort (); + if (l[7] != 16 || l[8] != 11 || l[9] != 6) + abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 2 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 8 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "\\*q_\[0-9\]* = 32;" 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(\[^\n\r\]*, 1\\)" 1 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-11.c b/gcc/testsuite/gcc.dg/strlenopt-11.c new file mode 100644 index 0000000..03f8790 --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-11.c @@ -0,0 +1,70 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#include "strlenopt.h" + +__attribute__((noinline, noclone)) void +fn1 (char *p, const char *z, size_t *lp) +{ + char *q, *r, *s; + char buf[64]; + size_t l[11]; + /* The first strlen stays, all the strcpy calls can be optimized + into memcpy and most other strlen calls and all strchr calls + optimized away. l[6] = strlen (r); and l[9] = strlen (r); need + to stay, because we need to invalidate the knowledge about + r strlen after strcpy (q, "jklmnopqrst"). */ + l[0] = strlen (z); + strcpy (buf, z); + strcpy (p, "abcde"); + q = strchr (p, '\0'); + strcpy (q, "efghi"); + r = strchr (q, '\0'); + strcpy (r, buf); + l[1] = strlen (p); + l[2] = strlen (q); + l[3] = strlen (r); + strcpy (q, "jklmnopqrst"); + l[4] = strlen (p); + l[5] = strlen (q); + l[6] = strlen (r); + s = strchr (q, '\0'); + strcpy (s, buf); + l[7] = strlen (p); + l[8] = strlen (q); + l[9] = strlen (r); + l[10] = strlen (s); + memcpy (lp, l, sizeof l); +} + +int +main () +{ + char buf[64]; + size_t l[11]; + const char *volatile z = "ABCDEFG"; + memset (buf, '\0', sizeof buf); + fn1 (buf, z, l); + if (memcmp (buf, "abcdejklmnopqrstABCDEFG", 24) != 0) + abort (); + if (l[0] != 7) + abort (); + if (l[1] != 17 || l[2] != 12 || l[3] != 7) + abort (); + if (l[4] != 16 || l[5] != 11 || l[6] != 6) + abort (); + if (l[7] != 23 || l[8] != 18 || l[9] != 13 || l[10] != 7) + abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 3 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 7 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times " D\.\[0-9_\]* = strlen \\(\[^\n\r\]*;\[\n\r\]* l.0. = " 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times " D\.\[0-9_\]* = strlen \\(\[^\n\r\]*;\[\n\r\]* l.6. = " 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times " D\.\[0-9_\]* = strlen \\(\[^\n\r\]*;\[\n\r\]* l.9. = " 1 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-12.c b/gcc/testsuite/gcc.dg/strlenopt-12.c new file mode 100644 index 0000000..1005fc6 --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-12.c @@ -0,0 +1,90 @@ +/* { dg-do run } */ +/* { dg-options "-O2" } */ + +#include "strlenopt.h" + +__attribute__((noinline, noclone)) char * +fn1 (char *p, size_t *l) +{ + char *q = strcat (p, "abcde"); + *l = strlen (p); + return q; +} + +__attribute__((noinline, noclone)) char * +fn2 (char *p, const char *q, size_t *l1, size_t *l2) +{ + size_t l = strlen (q); + char *r = strcat (p, q); + *l1 = l; + *l2 = strlen (p); + return r; +} + +__attribute__((noinline, noclone)) char * +fn3 (char *p, const char *q, size_t *l) +{ + char *r = strcpy (p, q); + *l = strlen (p); + return r; +} + +__attribute__((noinline, noclone)) char * +fn4 (char *p, const char *q, size_t *l) +{ + char *r = strcat (p, q); + *l = strlen (p); + return r; +} + +__attribute__((noinline, noclone)) char * +fn5 (char *p, const char *q, size_t *l1, size_t *l2, size_t *l3) +{ + size_t l = strlen (q); + size_t ll = strlen (p); + char *r = strcat (p, q); + *l1 = l; + *l2 = strlen (p); + *l3 = ll; + return r; +} + +__attribute__((noinline, noclone)) char * +fn6 (char *p, const char *q, size_t *l1, size_t *l2) +{ + size_t l = strlen (p); + char *r = strcat (p, q); + *l1 = strlen (p); + *l2 = l; + return r; +} + +int +main () +{ + char buf[64]; + const char *volatile q = "fgh"; + size_t l, l1, l2, l3; + memset (buf, '\0', sizeof buf); + memset (buf, 'a', 3); + if (fn1 (buf, &l) != buf || l != 8 || memcmp (buf, "aaaabcde", 9) != 0) + abort (); + if (fn2 (buf, q, &l1, &l2) != buf || l1 != 3 || l2 != 11 + || memcmp (buf, "aaaabcdefgh", 12) != 0) + abort (); + if (fn3 (buf, q, &l) != buf || l != 3 + || memcmp (buf, "fgh\0bcdefgh", 12) != 0) + abort (); + if (fn4 (buf, q, &l) != buf || l != 6 + || memcmp (buf, "fghfgh\0efgh", 12) != 0) + abort (); + l1 = 0; + l2 = 0; + if (fn5 (buf, q, &l1, &l2, &l3) != buf || l1 != 3 || l2 != 9 || l3 != 6 + || memcmp (buf, "fghfghfgh\0h", 12) != 0) + abort (); + if (fn6 (buf, q, &l1, &l2) != buf || l1 != 12 || l2 != 9 + || memcmp (buf, "fghfghfghfgh", 13) != 0) + abort (); + return 0; +} diff --git a/gcc/testsuite/gcc.dg/strlenopt-12g.c b/gcc/testsuite/gcc.dg/strlenopt-12g.c new file mode 100644 index 0000000..2b6508f --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-12g.c @@ -0,0 +1,6 @@ +/* This test needs runtime that provides stpcpy function. */ +/* { dg-do run { target *-*-linux* } } */ +/* { dg-options "-O2" } */ + +#define USE_GNU +#include "strlenopt-12.c" diff --git a/gcc/testsuite/gcc.dg/strlenopt-13.c b/gcc/testsuite/gcc.dg/strlenopt-13.c new file mode 100644 index 0000000..62effcd --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-13.c @@ -0,0 +1,68 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#include "strlenopt.h" + +__attribute__((noinline, noclone)) void +fn1 (char *p, const char *y, const char *z, size_t *lp) +{ + char *q, *r, *s; + char buf1[64], buf2[64]; + size_t l[8]; + /* These two strlen calls stay, all strcpy calls are optimized into + memcpy, all strchr calls optimized away, and most other strlen + calls too. */ + l[0] = strlen (y); + l[1] = strlen (z); + strcpy (buf1, y); + strcpy (buf2, z); + strcpy (p, "abcde"); + q = strchr (p, '\0'); + strcpy (q, "efghi"); + r = strchr (q, '\0'); + strcpy (r, buf1); + l[2] = strlen (p); + l[3] = strlen (q); + l[4] = strlen (r); + strcpy (r, buf2); + /* Except for these two calls, strlen (r) before and after the above + is non-constant, so adding l[4] - l[1] to all previous strlens + might make the expressions already too complex. */ + l[5] = strlen (p); + l[6] = strlen (q); + /* This one is of course optimized, it is l[1]. */ + l[7] = strlen (r); + memcpy (lp, l, sizeof l); +} + +int +main () +{ + char buf[64]; + size_t l[8]; + const char *volatile y = "ABCDEFG"; + const char *volatile z = "HIJK"; + memset (buf, '\0', sizeof buf); + fn1 (buf, y, z, l); + if (memcmp (buf, "abcdeefghiHIJK", 15) != 0) + abort (); + if (l[0] != 7 || l[1] != 4) + abort (); + if (l[2] != 17 || l[3] != 12 || l[4] != 7) + abort (); + if (l[5] != 14 || l[6] != 9 || l[7] != 4) + abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 4 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 7 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times " D\.\[0-9_\]* = strlen \\(\[^\n\r\]*;\[\n\r\]* l.0. = " 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times " D\.\[0-9_\]* = strlen \\(\[^\n\r\]*;\[\n\r\]* l.1. = " 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times " D\.\[0-9_\]* = strlen \\(\[^\n\r\]*;\[\n\r\]* l.5. = " 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times " D\.\[0-9_\]* = strlen \\(\[^\n\r\]*;\[\n\r\]* l.6. = " 1 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-14g.c b/gcc/testsuite/gcc.dg/strlenopt-14g.c new file mode 100644 index 0000000..62a120d --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-14g.c @@ -0,0 +1,115 @@ +/* This test needs runtime that provides stpcpy and mempcpy functions. */ +/* { dg-do run { target *-*-linux* } } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#define USE_GNU +#include "strlenopt.h" + +__attribute__((noinline, noclone)) char * +fn1 (char *p, size_t *l1, size_t *l2) +{ + char *a = mempcpy (p, "abcde", 6); + /* This strlen needs to stay. */ + size_t la = strlen (a); + /* This strlen can be optimized into 5. */ + size_t lp = strlen (p); + *l1 = la; + *l2 = lp; + return a; +} + +__attribute__((noinline, noclone)) char * +fn2 (char *p, const char *q, size_t *l1, size_t *l2, size_t *l3) +{ + /* This strlen needs to stay. */ + size_t lq = strlen (q); + char *a = mempcpy (p, q, lq + 1); + /* This strlen needs to stay. */ + size_t la = strlen (a); + /* This strlen can be optimized into lq. */ + size_t lp = strlen (p); + *l1 = lq; + *l2 = la; + *l3 = lp; + return a; +} + +__attribute__((noinline, noclone)) char * +fn3 (char *p, size_t *l1, size_t *l2) +{ + char *a = stpcpy (p, "abcde"); + /* This strlen can be optimized into 0. */ + size_t la = strlen (a); + /* This strlen can be optimized into 5. */ + size_t lp = strlen (p); + *l1 = la; + *l2 = lp; + return a; +} + +__attribute__((noinline, noclone)) char * +fn4 (char *p, const char *q, size_t *l1, size_t *l2, size_t *l3) +{ + /* This strlen needs to stay. */ + size_t lq = strlen (q); + char *a = stpcpy (p, q); + /* This strlen can be optimized into 0. */ + size_t la = strlen (a); + /* This strlen can be optimized into lq. */ + size_t lp = strlen (p); + *l1 = lq; + *l2 = la; + *l3 = lp; + return a; +} + +__attribute__((noinline, noclone)) char * +fn5 (char *p, const char *q, size_t *l1, size_t *l2) +{ + char *a = stpcpy (p, q); + /* This strlen can be optimized into 0. */ + size_t la = strlen (a); + /* This strlen can be optimized into a - p. */ + size_t lp = strlen (p); + *l1 = la; + *l2 = lp; + return a; +} + +int +main () +{ + char buf[64]; + const char *volatile q = "ABCDEFGH"; + size_t l1, l2, l3; + memset (buf, '\0', sizeof buf); + memset (buf + 6, 'z', 7); + if (fn1 (buf, &l1, &l2) != buf + 6 || l1 != 7 || l2 != 5 + || memcmp (buf, "abcde\0zzzzzzz", 14) != 0) + abort (); + if (fn2 (buf, q, &l1, &l2, &l3) != buf + 9 || l1 != 8 || l2 != 4 || l3 != 8 + || memcmp (buf, "ABCDEFGH\0zzzz", 14) != 0) + abort (); + if (fn3 (buf, &l1, &l2) != buf + 5 || l1 != 0 || l2 != 5 + || memcmp (buf, "abcde\0GH\0zzzz", 14) != 0) + abort (); + l3 = 0; + memset (buf, 'n', 9); + if (fn4 (buf, q, &l1, &l2, &l3) != buf + 8 || l1 != 8 || l2 != 0 || l3 != 8 + || memcmp (buf, "ABCDEFGH\0zzzz", 14) != 0) + abort (); + memset (buf, 'm', 9); + if (fn5 (buf, q, &l1, &l2) != buf + 8 || l1 != 0 || l2 != 8 + || memcmp (buf, "ABCDEFGH\0zzzz", 14) != 0) + abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 4 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "mempcpy \\(" 2 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 2 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-14gf.c b/gcc/testsuite/gcc.dg/strlenopt-14gf.c new file mode 100644 index 0000000..999759e --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-14gf.c @@ -0,0 +1,24 @@ +/* This test needs runtime that provides stpcpy, mempcpy and __*_chk + functions. */ +/* { dg-do run { target *-*-linux* } } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#define FORTIFY_SOURCE 2 +#include "strlenopt-14g.c" + +/* Compared to strlenopt-14gf.c, strcpy_chk with string literal as + second argument isn't being optimized by builtins.c into + memcpy. */ +/* { dg-final { scan-tree-dump-times "strlen \\(" 4 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "__memcpy_chk \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "__mempcpy_chk \\(" 2 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "__strcpy_chk \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "__strcat_chk \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "__stpcpy_chk \\(" 3 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "mempcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-15.c b/gcc/testsuite/gcc.dg/strlenopt-15.c new file mode 100644 index 0000000..495166d --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-15.c @@ -0,0 +1,60 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#include "strlenopt.h" + +__attribute__((noinline, noclone)) size_t +fn1 (char *p, size_t l) +{ + memcpy (p, "abcdef", l); + /* This strlen can't be optimized, as l is unknown. */ + return strlen (p); +} + +__attribute__((noinline, noclone)) size_t +fn2 (char *p, const char *q, size_t *lp) +{ + size_t l = strlen (q), l2; + memcpy (p, q, 7); + /* This strlen can't be optimized, as l might be bigger than 7. */ + l2 = strlen (p); + *lp = l; + return l2; +} + +__attribute__((noinline, noclone)) char * +fn3 (char *p) +{ + *p = 0; + return p + 1; +} + +int +main () +{ + char buf[64]; + const char *volatile q = "ABCDEFGH"; + const char *volatile q2 = "IJ\0KLMNOPQRS"; + size_t l; + memset (buf, '\0', sizeof buf); + memset (buf + 2, 'a', 7); + if (fn1 (buf, 3) != 9 || memcmp (buf, "abcaaaaaa", 10) != 0) + abort (); + if (fn1 (buf, 7) != 6 || memcmp (buf, "abcdef\0aa", 10) != 0) + abort (); + if (fn2 (buf, q, &l) != 9 || l != 8 || memcmp (buf, "ABCDEFGaa", 10) != 0) + abort (); + if (fn2 (buf, q2, &l) != 2 || l != 2 || memcmp (buf, "IJ\0KLMNaa", 10) != 0) + abort (); + if (fn3 (buf) != buf + 1 || memcmp (buf, "\0J\0KLMNaa", 10) != 0) + abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 3 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 2 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-16g.c b/gcc/testsuite/gcc.dg/strlenopt-16g.c new file mode 100644 index 0000000..11e4d31 --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-16g.c @@ -0,0 +1,34 @@ +/* This test needs runtime that provides stpcpy function. */ +/* { dg-do run { target *-*-linux* } } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#define USE_GNU +#include "strlenopt.h" + +__attribute__((noinline, noclone)) char * +fn1 (char *p, const char *q) +{ + /* This strcpy can be optimized into stpcpy. */ + strcpy (p, q); + /* And this strchr into the return value from it. */ + return strchr (p, '\0'); +} + +int +main () +{ + char buf[64]; + const char *volatile q = "ABCDEFGH"; + if (fn1 (buf, q) != buf + 8 || memcmp (buf, "ABCDEFGH", 9) != 0) + abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "mempcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 1 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-17g.c b/gcc/testsuite/gcc.dg/strlenopt-17g.c new file mode 100644 index 0000000..b61bf74 --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-17g.c @@ -0,0 +1,57 @@ +/* This test needs runtime that provides stpcpy function. */ +/* { dg-do run { target *-*-linux* } } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#define USE_GNU +#include "strlenopt.h" + +__attribute__((noinline, noclone)) int +foo (const char *p) +{ + static int c; + const char *q[] = { "123498765abcde", "123498765..", "129abcde", "129abcde" }; + if (strcmp (p, q[c]) != 0) + abort (); + return c++; +} + +__attribute__((noinline, noclone)) void +bar (const char *p, const char *q) +{ + size_t l; + /* This strlen stays. */ + char *a = __builtin_alloca (strlen (p) + 50); + /* strcpy can be optimized into memcpy. */ + strcpy (a, p); + /* strcat into stpcpy. */ + strcat (a, q); + /* This strlen can be optimized away. */ + l = strlen (a); + /* This becomes memcpy. */ + strcat (a, "abcde"); + if (!foo (a)) + /* And this one too. */ + strcpy (a + l, ".."); + foo (a); +} + +int +main () +{ + const char *volatile s1 = "1234"; + const char *volatile s2 = "98765"; + const char *volatile s3 = "12"; + const char *volatile s4 = "9"; + bar (s1, s2); + bar (s3, s4); + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 3 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "mempcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 1 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-18g.c b/gcc/testsuite/gcc.dg/strlenopt-18g.c new file mode 100644 index 0000000..c70daea --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-18g.c @@ -0,0 +1,82 @@ +/* This test needs runtime that provides stpcpy function. */ +/* { dg-do run { target *-*-linux* } } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#define USE_GNU +#include "strlenopt.h" + +__attribute__((noinline, noclone)) char * +fn1 (int x, int y, int z) +{ + static char buf[40]; + const char *p; + switch (x) + { + case 0: + p = "abcd"; + break; + case 1: + p = "efgh"; + break; + case 2: + p = "ijkl"; + break; + default: + p = "mnopq"; + break; + } + if (y) + { + strcpy (buf, p); + if (z) + strcat (buf, "ABCDEFG"); + else + strcat (buf, "HIJKLMN"); + } + else + { + strcpy (buf, p + 1); + if (z) + strcat (buf, "OPQ"); + else + strcat (buf, "RST"); + } + return buf; +} + +int +main () +{ + int i; + for (i = 0; i < 5; i++) + { + const char *p = "abcdefghijklmnopq" + (i < 3 ? i : 3) * 4; + const char *q; + int j = i >= 3; + fn1 (i ? 0 : 1, 1, 1); + q = fn1 (i, 0, 0); + if (memcmp (q, p + 1, 3 + j) != 0 || memcmp (q + 3 + j, "RST", 4) != 0) + abort (); + fn1 (i ? 0 : 1, 0, 1); + q = fn1 (i, 1, 0); + if (memcmp (q, p, 4 + j) != 0 || memcmp (q + 4 + j, "HIJKLMN", 8) != 0) + abort (); + fn1 (i ? 0 : 1, 1, 0); + q = fn1 (i, 0, 1); + if (memcmp (q, p + 1, 3 + j) != 0 || memcmp (q + 3 + j, "OPQ", 4) != 0) + abort (); + fn1 (i ? 0 : 1, 0, 0); + q = fn1 (i, 1, 1); + if (memcmp (q, p, 4 + j) != 0 || memcmp (q + 4 + j, "ABCDEFG", 8) != 0) + abort (); + } + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 4 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 2 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-19.c b/gcc/testsuite/gcc.dg/strlenopt-19.c new file mode 100644 index 0000000..042fd77 --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-19.c @@ -0,0 +1,81 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#include "strlenopt.h" + +__attribute__((noinline, noclone)) char * +fn1 (int x, int y, int z) +{ + static char buf[40]; + const char *p; + switch (x) + { + case 0: + p = "abcd"; + /* Prevent cswitch optimization. */ + asm volatile ("" : : : "memory"); + break; + case 1: + p = "efgh"; + break; + case 2: + p = "ijkl"; + break; + default: + p = "mnop"; + break; + } + if (y) + { + strcpy (buf, p); + if (z) + strcat (buf, "ABCDEFG"); + else + strcat (buf, "HIJKLMN"); + } + else + { + strcpy (buf, p + 1); + if (z) + strcat (buf, "OPQ"); + else + strcat (buf, "RST"); + } + return buf; +} + +int +main () +{ + int i; + for (i = 0; i < 5; i++) + { + const char *p = "abcdefghijklmnop" + (i < 3 ? i : 3) * 4; + const char *q; + fn1 (i ? 0 : 1, 1, 1); + q = fn1 (i, 0, 0); + if (memcmp (q, p + 1, 3) != 0 || memcmp (q + 3, "RST", 4) != 0) + abort (); + fn1 (i ? 0 : 1, 0, 1); + q = fn1 (i, 1, 0); + if (memcmp (q, p, 4) != 0 || memcmp (q + 4, "HIJKLMN", 8) != 0) + abort (); + fn1 (i ? 0 : 1, 1, 0); + q = fn1 (i, 0, 1); + if (memcmp (q, p + 1, 3) != 0 || memcmp (q + 3, "OPQ", 4) != 0) + abort (); + fn1 (i ? 0 : 1, 0, 0); + q = fn1 (i, 1, 1); + if (memcmp (q, p, 4) != 0 || memcmp (q + 4, "ABCDEFG", 8) != 0) + abort (); + } + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 6 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-1f.c b/gcc/testsuite/gcc.dg/strlenopt-1f.c new file mode 100644 index 0000000..4b0207f --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-1f.c @@ -0,0 +1,18 @@ +/* This test needs runtime that provides __*_chk functions. */ +/* { dg-do run { target *-*-linux* } } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#define FORTIFY_SOURCE 2 +#include "strlenopt-1.c" + +/* { dg-final { scan-tree-dump-times "strlen \\(" 2 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "__memcpy_chk \\(" 3 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "__strcpy_chk \\(" 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "__strcat_chk \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "__stpcpy_chk \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-2.c b/gcc/testsuite/gcc.dg/strlenopt-2.c new file mode 100644 index 0000000..5e6557b --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-2.c @@ -0,0 +1,49 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#include "strlenopt.h" + +__attribute__((noinline, noclone)) char * +foo (char *p, char *r) +{ + char buf[26]; + if (strlen (p) + strlen (r) + 9 > 26) + return NULL; + /* This strcpy can be optimized into memcpy, using the remembered + strlen (p). */ + strcpy (buf, p); + /* These two strcat can be optimized into memcpy. The first one + could be even optimized into a *ptr = '/'; store as the '\0' + is immediately overwritten. */ + strcat (buf, "/"); + strcat (buf, "abcde"); + /* This strcpy can be optimized into memcpy, using the remembered + strlen (r). */ + strcat (buf, r); + /* And this can be optimized into memcpy too. */ + strcat (buf, "fg"); + return strdup (buf); +} + +int +main () +{ + char *volatile p = "string1"; + char *volatile r = "string2"; + char *q = foo (p, r); + if (q != NULL) + { + if (strcmp (q, "string1/abcdestring2fg")) + abort (); + free (q); + } + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 2 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 5 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-20.c b/gcc/testsuite/gcc.dg/strlenopt-20.c new file mode 100644 index 0000000..6fe99a4 --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-20.c @@ -0,0 +1,95 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#include "strlenopt.h" + +__attribute__((noinline, noclone)) const char * +fn1 (int x, int y) +{ + const char *p; + switch (x) + { + case 0: + p = "abcd"; + /* Prevent cswitch optimization. */ + asm volatile ("" : : : "memory"); + break; + case 1: + p = "efgh"; + break; + case 2: + p = "ijkl"; + break; + default: + p = "mnop"; + break; + } + if (y) + /* strchr should be optimized into p + 4 here. */ + return strchr (p, '\0'); + else + /* and strlen into 3. */ + return p + strlen (p + 1); +} + +__attribute__((noinline, noclone)) size_t +fn2 (char *p, char *q) +{ + size_t l; + /* Both strcpy calls can be optimized into memcpy, strlen needs to stay. */ + strcpy (p, "abc"); + p[3] = 'd'; + l = strlen (p); + strcpy (q, p); + return l; +} + +__attribute__((noinline, noclone)) char * +fn3 (char *p) +{ + char *c; + /* The strcpy call can be optimized into memcpy, strchr needs to stay, + strcat is optimized into memcpy. */ + strcpy (p, "abc"); + p[3] = 'd'; + c = strchr (p, '\0'); + strcat (p, "efgh"); + return c; +} + +int +main () +{ + int i; + char buf[64], buf2[64]; + for (i = 0; i < 5; i++) + { + const char *p = "abcdefghijklmnop" + (i < 3 ? i : 3) * 4; + const char *q; + q = fn1 (i, 1); + if (memcmp (q - 4, p, 4) != 0 || q[0] != '\0') + abort (); + q = fn1 (i, 0); + if (memcmp (q - 3, p, 4) != 0 || q[1] != '\0') + abort (); + } + memset (buf, '\0', sizeof buf); + memset (buf + 4, 'z', 2); + if (fn2 (buf, buf2) != 6 + || memcmp (buf, "abcdzz", 7) != 0 + || memcmp (buf2, "abcdzz", 7) != 0) + abort (); + memset (buf, '\0', sizeof buf); + memset (buf + 4, 'z', 2); + if (fn3 (buf) != buf + 6 || memcmp (buf, "abcdzzefgh", 11) != 0) + abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 4 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-2f.c b/gcc/testsuite/gcc.dg/strlenopt-2f.c new file mode 100644 index 0000000..7996e67 --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-2f.c @@ -0,0 +1,18 @@ +/* This test needs runtime that provides __*_chk functions. */ +/* { dg-do run { target *-*-linux* } } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#define FORTIFY_SOURCE 2 +#include "strlenopt-2.c" + +/* { dg-final { scan-tree-dump-times "strlen \\(" 2 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "__memcpy_chk \\(" 5 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "__strcpy_chk \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "__strcat_chk \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "__stpcpy_chk \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-3.c b/gcc/testsuite/gcc.dg/strlenopt-3.c new file mode 100644 index 0000000..1bab8f3 --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-3.c @@ -0,0 +1,66 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-strlen -fdump-tree-optimized" } */ + +#include "strlenopt.h" + +__attribute__((noinline, noclone)) size_t +fn1 (char *p, char *q) +{ + size_t s = strlen (q); + strcpy (p, q); + return s - strlen (p); +} + +__attribute__((noinline, noclone)) size_t +fn2 (char *p, char *q) +{ + size_t s = strlen (q); + memcpy (p, q, s + 1); + return s - strlen (p); +} + +__attribute__((noinline, noclone)) size_t +fn3 (char *p) +{ + memcpy (p, "abcd", 5); + return strlen (p); +} + +__attribute__((noinline, noclone)) size_t +fn4 (char *p) +{ + memcpy (p, "efg\0hij", 6); + return strlen (p); +} + +int +main () +{ + char buf[64]; + char *volatile p = buf; + char *volatile q = "ABCDEF"; + buf[7] = 'G'; + if (fn1 (p, q) != 0 || memcmp (buf, "ABCDEF\0G", 8)) + abort (); + q = "HIJ"; + if (fn2 (p + 1, q) != 0 || memcmp (buf, "AHIJ\0F\0G", 8)) + abort (); + buf[6] = 'K'; + if (fn3 (p + 1) != 4 || memcmp (buf, "Aabcd\0KG", 8)) + abort (); + if (fn4 (p) != 3 || memcmp (buf, "efg\0hiKG", 8)) + abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 2 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 4 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ +/* { dg-final { scan-tree-dump-times "return 0" 3 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "return 4" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "return 3" 1 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-4.c b/gcc/testsuite/gcc.dg/strlenopt-4.c new file mode 100644 index 0000000..beea495 --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-4.c @@ -0,0 +1,75 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#include "strlenopt.h" + +/* If stpcpy can't be used, this is optimized into + strcpy (p, q); strcat (p, r); memcpy (p + strlen (p), "abcd", 5); + If stpcpy can be used (see strlenopt-4g.c test), + this is optimized into + memcpy (stpcpy (stpcpy (p, q), r), "abcd", 5); */ +__attribute__((noinline, noclone)) void +foo (char *p, const char *q, const char *r) +{ + strcpy (p, q); + strcat (p, r); + strcat (p, "abcd"); +} + +/* If stpcpy can't be used, this is optimized into + memcpy (p, "abcd", 4); strcpy (p + 4, q); strcat (p, r); + If stpcpy can be used, this is optimized into + memcpy (p, "abcd", 4); strcpy (stpcpy (p + 4, q), r); */ +__attribute__((noinline, noclone)) void +bar (char *p, const char *q, const char *r) +{ + strcpy (p, "abcd"); + strcat (p, q); + strcat (p, r); +} + +/* If stpcpy can't be used, this is optimized into + strcat (p, q); memcpy (t1 = p + strlen (p), "abcd", 4); + strcpy (t1 + 4, r); memcpy (p + strlen (p), "efgh", 5); + If stpcpy can be used, this is optimized into + t1 = stpcpy (p + strlen (p), q); memcpy (t1, "abcd", 4); + memcpy (stpcpy (t1 + 4, r), "efgh", 5); */ +__attribute__((noinline, noclone)) void +baz (char *p, const char *q, const char *r) +{ + strcat (p, q); + strcat (p, "abcd"); + strcat (p, r); + strcat (p, "efgh"); +} + +char buf[64]; + +int +main () +{ + char *volatile p = buf; + const char *volatile q = "ij"; + const char *volatile r = "klmno"; + foo (p, q, r); + if (memcmp (buf, "ijklmnoabcd\0\0\0\0\0\0\0\0", 20) != 0) + abort (); + memset (buf, '\0', sizeof buf); + bar (p, q, r); + if (memcmp (buf, "abcdijklmno\0\0\0\0\0\0\0\0", 20) != 0) + abort (); + memset (buf, 'v', 3); + memset (buf + 3, '\0', -3 + sizeof buf); + baz (p, q, r); + if (memcmp (buf, "vvvijabcdklmnoefgh\0", 20) != 0) + abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 3 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 4 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 3 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 3 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-4g.c b/gcc/testsuite/gcc.dg/strlenopt-4g.c new file mode 100644 index 0000000..7b39736 --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-4g.c @@ -0,0 +1,14 @@ +/* This test needs runtime that provides stpcpy function. */ +/* { dg-do run { target *-*-linux* } } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#define USE_GNU +#include "strlenopt-4.c" + +/* { dg-final { scan-tree-dump-times "strlen \\(" 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 4 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 5 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-4gf.c b/gcc/testsuite/gcc.dg/strlenopt-4gf.c new file mode 100644 index 0000000..cf99212 --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-4gf.c @@ -0,0 +1,19 @@ +/* This test needs runtime that provides stpcpy and __*_chk functions. */ +/* { dg-do run { target *-*-linux* } } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#define USE_GNU +#define FORTIFY_SOURCE 2 +#include "strlenopt-4.c" + +/* { dg-final { scan-tree-dump-times "strlen \\(" 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "__memcpy_chk \\(" 4 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "__strcpy_chk \\(" 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "__strcat_chk \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "__stpcpy_chk \\(" 5 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-5.c b/gcc/testsuite/gcc.dg/strlenopt-5.c new file mode 100644 index 0000000..131494a --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-5.c @@ -0,0 +1,57 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#include "strlenopt.h" + +__attribute__((noinline, noclone)) char * +foo (char *p, const char *q) +{ + char *e = strchr (p, '\0'); + strcat (p, q); + return e; +} + +__attribute__((noinline, noclone)) char * +bar (char *p) +{ + memcpy (p, "abcd", 5); + return strchr (p, '\0'); +} + +__attribute__((noinline, noclone)) void +baz (char *p) +{ + char *e = strchr (p, '\0'); + strcat (e, "abcd"); +} + +char buf[64]; + +int +main () +{ + char *volatile p = buf; + const char *volatile q = "ij"; + memset (buf, 'v', 3); + if (foo (p, q) != buf + 3 + || memcmp (buf, "vvvij\0\0\0\0", 10) != 0) + abort (); + memset (buf, '\0', sizeof buf); + if (bar (p) != buf + 4 + || memcmp (buf, "abcd\0\0\0\0\0", 10) != 0) + abort (); + memset (buf, 'v', 2); + memset (buf + 2, '\0', -2 + sizeof buf); + baz (p); + if (memcmp (buf, "vvabcd\0\0\0", 10) != 0) + abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 2 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 2 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-6.c b/gcc/testsuite/gcc.dg/strlenopt-6.c new file mode 100644 index 0000000..d9b7187 --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-6.c @@ -0,0 +1,86 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#include "strlenopt.h" + +__attribute__((noinline, noclone)) char * +foo (char *x) +{ +#ifdef PR50262_FIXED + /* Once PTA is fixed, we'll need just one strlen here, + without the memcpy. */ + char *p = x; + char *q = malloc (strlen (p) + 64); +#else + /* This is here just because PTA can't figure that + *q = '\0' store below can't change p's length. + In this case we have one strlen and one memcpy here. */ + char b[64]; + char *q = malloc (strlen (x) + 64); + char *p = strcpy (b, x); +#endif + char *r; + if (q == NULL) return NULL; + /* This store can be optimized away once strcat is + replaced with memcpy. */ + *q = '\0'; + /* These two strcat calls can be optimized into memcpy calls. */ + strcat (q, p); + strcat (q, "/"); + /* The strchr can be optimized away, as we know the current + string length as well as end pointer. */ + r = strchr (q, '\0'); + /* This store can go, as it is overwriting '\0' with the same + character. */ + *r = '\0'; + /* And this strcat can be again optimized into memcpy call. */ + strcat (q, "abcde"); + return q; +} + +__attribute__((noinline, noclone)) char * +bar (char *p) +{ + char buf[26]; + char *r; + if (strlen (p) + 9 > 26) + return NULL; + *buf = '\0'; + strcat (buf, p); + strcat (buf, "/"); + r = strchr (buf, '\0'); + *r = '\0'; + strcat (buf, "abcde"); + return strdup (buf); +} + +int +main () +{ + char *volatile p = "string1"; + char *volatile r = "string2"; + char *q = foo (p); + if (q != NULL) + { + if (strcmp (q, "string1/abcde")) + abort (); + memset (q, '\0', 14); + free (q); + } + q = bar (p); + if (q != NULL) + { + if (strcmp (q, "string1/abcde")) + abort (); + free (q); + } + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 2 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 7 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-7.c b/gcc/testsuite/gcc.dg/strlenopt-7.c new file mode 100644 index 0000000..6fd940d --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-7.c @@ -0,0 +1,53 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-strlen -fdump-tree-optimized" } */ + +#include "strlenopt.h" + +char buf[64]; + +__attribute__((noinline, noclone)) size_t +foo (void) +{ + char *p = memcpy (buf, "abcdefgh", 9); + /* This store can be optimized away as... */ + *p = '\0'; + /* ... the following strcat can be optimized into memcpy, + which overwrites that '\0'. */ + strcat (p, "ijk"); + /* This should be optimized into return 3. */ + return strlen (p); +} + +__attribute__((noinline, noclone)) size_t +bar (char *p) +{ + char *r = strchr (p, '\0'); + /* This store shouldn't be optimized away, because we + want to crash if p is e.g. a string literal. */ + *r = '\0'; + /* This strlen can be optimized into 0. */ + return strlen (r); +} + +int +main () +{ + char *volatile p = buf; + if (foo () != 3 || memcmp (buf, "ijk\0efgh\0", 10) != 0) + abort (); + if (bar (p) != 0 || memcmp (buf, "ijk\0efgh\0", 10) != 0) + abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 2 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "\\*r_\[0-9\]* = 0;" 1 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ +/* { dg-final { scan-tree-dump-times "return 3;" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "return 0;" 2 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-8.c b/gcc/testsuite/gcc.dg/strlenopt-8.c new file mode 100644 index 0000000..3aaf660 --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-8.c @@ -0,0 +1,52 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#include "strlenopt.h" + +/* Yes, there are people who write code like this. */ + +__attribute__((noinline, noclone)) char * +foo (int r) +{ + char buf[10] = ""; + strcat (buf, r ? "r" : "w"); + strcat (buf, "b"); + return strdup (buf); +} + +__attribute__((noinline, noclone)) char * +bar (int r) +{ + char buf[10] = {}; + strcat (buf, r ? "r" : "w"); + strcat (buf, "b"); + return strdup (buf); +} + +int +main () +{ + char *q = foo (1); + if (q != NULL) + { + if (strcmp (q, "rb")) + abort (); + free (q); + } + q = bar (0); + if (q != NULL) + { + if (strcmp (q, "wb")) + abort (); + free (q); + } + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 4 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-9.c b/gcc/testsuite/gcc.dg/strlenopt-9.c new file mode 100644 index 0000000..6590d70 --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-9.c @@ -0,0 +1,109 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-strlen -fdump-tree-optimized" } */ + +#include "strlenopt.h" + +__attribute__((noinline, noclone)) char * +fn1 (int r) +{ + char *p = r ? "a" : "bc"; + /* String length for p varies, therefore strchr below isn't + optimized away. */ + return strchr (p, '\0'); +} + +__attribute__((noinline, noclone)) size_t +fn2 (int r) +{ + char *p, q[10]; + strcpy (q, "abc"); + p = r ? "a" : q; + /* String length for p varies, therefore strlen below isn't + optimized away. */ + return strlen (p); +} + +__attribute__((noinline, noclone)) size_t +fn3 (char *p, int n) +{ + int i; + p = strchr (p, '\0'); + /* strcat here can be optimized into memcpy. */ + strcat (p, "abcd"); + for (i = 0; i < n; i++) + if ((i % 123) == 53) + /* strcat here is optimized into strlen and memcpy. */ + strcat (p, "efg"); + /* The strlen here can't be optimized away, as in the loop string + length of p might change. */ + return strlen (p); +} + +char buf[64]; + +__attribute__((noinline, noclone)) size_t +fn4 (char *x, int n) +{ + int i; + size_t l; + char a[64]; + char *p = strchr (x, '\0'); + /* strcpy here is optimized into memcpy, length computed as p - x + 1. */ + strcpy (a, x); + /* strcat here is optimized into memcpy. */ + strcat (p, "abcd"); + for (i = 0; i < n; i++) + if ((i % 123) == 53) + /* strcat here is optimized into strlen and memcpy. */ + strcat (a, "efg"); + /* The strlen should be optimized here into 4. */ + l = strlen (p); + /* This stays strcpy. */ + strcpy (buf, a); + return l; +} + +int +main () +{ + volatile int l = 1; + char b[64]; + + if (memcmp (fn1 (l) - 1, "a", 2) != 0) + abort (); + if (memcmp (fn1 (!l) - 2, "bc", 3) != 0) + abort (); + if (fn2 (l) != 1 || fn2 (!l) != 3) + abort (); + memset (b, '\0', sizeof b); + memset (b, 'a', 3); + if (fn3 (b, 10) != 4 || memcmp (b, "aaaabcd", 8) != 0) + abort (); + if (fn3 (b, 128) != 7 || memcmp (b, "aaaabcdabcdefg", 15) != 0) + abort (); + if (fn3 (b, 256) != 10 || memcmp (b, "aaaabcdabcdefgabcdefgefg", 25) != 0) + abort (); + if (fn4 (b, 10) != 4 + || memcmp (b, "aaaabcdabcdefgabcdefgefgabcd", 29) != 0 + || memcmp (buf, "aaaabcdabcdefgabcdefgefg", 25) != 0) + abort (); + if (fn4 (b, 128) != 4 + || memcmp (b, "aaaabcdabcdefgabcdefgefgabcdabcd", 33) != 0 + || memcmp (buf, "aaaabcdabcdefgabcdefgefgabcdefg", 32) != 0) + abort (); + if (fn4 (b, 256) != 4 + || memcmp (b, "aaaabcdabcdefgabcdefgefgabcdabcdabcd", 37) != 0 + || memcmp (buf, "aaaabcdabcdefgabcdefgefgabcdabcdefgefg", 39) != 0) + abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "strlen \\(" 4 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 6 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcpy \\(" 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strcat \\(" 0 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "strchr \\(" 3 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 0 "strlen" } } */ +/* { dg-final { cleanup-tree-dump "strlen" } } */ +/* { dg-final { scan-tree-dump-times "return 4;" 1 "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt.h b/gcc/testsuite/gcc.dg/strlenopt.h new file mode 100644 index 0000000..ef47e5a --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt.h @@ -0,0 +1,59 @@ +/* This is a replacement of needed parts from stdlib.h and string.h + for -foptimize-strlen testing, to ensure we are testing the builtins + rather than whatever the OS has in its headers. */ + +#define NULL ((void *) 0) +typedef __SIZE_TYPE__ size_t; +extern void abort (void); +void *malloc (size_t); +void free (void *); +char *strdup (const char *); +size_t strlen (const char *); +void *memcpy (void *__restrict, const void *__restrict, size_t); +char *strcpy (char *__restrict, const char *__restrict); +char *strcat (char *__restrict, const char *__restrict); +char *strchr (const char *, int); +void *memset (void *, int, size_t); +int memcmp (const void *, const void *, size_t); +int strcmp (const char *, const char *); +#ifdef USE_GNU +void *mempcpy (void *__restrict, const void *__restrict, size_t); +char *stpcpy (char *__restrict, const char *__restrict); +#endif + +#if defined(FORTIFY_SOURCE) && FORTIFY_SOURCE > 0 && __OPTIMIZE__ +# define bos(ptr) __builtin_object_size (ptr, FORTIFY_SOURCE > 0) +# define bos0(ptr) __builtin_object_size (ptr, 0) + +extern inline __attribute__((gnu_inline, always_inline, artificial)) void * +memcpy (void *__restrict dest, const void *__restrict src, size_t len) +{ + return __builtin___memcpy_chk (dest, src, len, bos0 (dest)); +} + +extern inline __attribute__((gnu_inline, always_inline, artificial)) char * +strcpy (char *__restrict dest, const char *__restrict src) +{ + return __builtin___strcpy_chk (dest, src, bos (dest)); +} + +extern inline __attribute__((gnu_inline, always_inline, artificial)) char * +strcat (char *__restrict dest, const char *__restrict src) +{ + return __builtin___strcat_chk (dest, src, bos (dest)); +} + +# ifdef USE_GNU +extern inline __attribute__((gnu_inline, always_inline, artificial)) void * +mempcpy (void *__restrict dest, const void *__restrict src, size_t len) +{ + return __builtin___mempcpy_chk (dest, src, len, bos0 (dest)); +} + +extern inline __attribute__((gnu_inline, always_inline, artificial)) char * +stpcpy (char *__restrict dest, const char *__restrict src) +{ + return __builtin___stpcpy_chk (dest, src, bos (dest)); +} +# endif +#endif diff --git a/gcc/timevar.def b/gcc/timevar.def index 373bae6..5ad0f9d 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -1,7 +1,7 @@ /* This file contains the definitions for timing variables used to measure run-time performance of the compiler. Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, - 2009, 2010 + 2009, 2010, 2011 Free Software Foundation, Inc. Contributed by Alex Samuel <samuel@codesourcery.com> @@ -184,6 +184,7 @@ DEFTIMEVAR (TV_TREE_COPY_RENAME , "tree rename SSA copies") DEFTIMEVAR (TV_TREE_SSA_VERIFY , "tree SSA verifier") DEFTIMEVAR (TV_TREE_STMT_VERIFY , "tree STMT verifier") DEFTIMEVAR (TV_TREE_SWITCH_CONVERSION, "tree switch initialization conversion") +DEFTIMEVAR (TV_TREE_STRLEN , "tree strlen optimization") DEFTIMEVAR (TV_CGRAPH_VERIFY , "callgraph verifier") DEFTIMEVAR (TV_DOM_FRONTIERS , "dominance frontiers") DEFTIMEVAR (TV_DOMINANCE , "dominance computation") diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index ee442a5..df1e24c 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -413,6 +413,7 @@ extern struct gimple_opt_pass pass_diagnose_omp_blocks; extern struct gimple_opt_pass pass_expand_omp; extern struct gimple_opt_pass pass_expand_omp_ssa; extern struct gimple_opt_pass pass_object_sizes; +extern struct gimple_opt_pass pass_strlen; extern struct gimple_opt_pass pass_fold_builtins; extern struct gimple_opt_pass pass_stdarg; extern struct gimple_opt_pass pass_early_warn_uninitialized; diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c new file mode 100644 index 0000000..71cefaa --- /dev/null +++ b/gcc/tree-ssa-strlen.c @@ -0,0 +1,1997 @@ +/* String length optimization + Copyright (C) 2011 Free Software Foundation, Inc. + Contributed by Jakub Jelinek <jakub@redhat.com> + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tree-flow.h" +#include "tree-pass.h" +#include "domwalk.h" +#include "alloc-pool.h" +#include "tree-ssa-propagate.h" +#include "gimple-pretty-print.h" +#include "params.h" + +/* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value + is an index into strinfo vector, negative value stands for + string length of a string literal (~strlen). */ +static VEC (int, heap) *ssa_ver_to_stridx; + +/* Number of currently active string indexes plus one. */ +static int max_stridx; + +/* String information record. */ +typedef struct strinfo_struct +{ + /* String length of this string. */ + tree length; + /* Any of the corresponding pointers for querying alias oracle. */ + tree ptr; + /* Statement for delayed length computation. */ + gimple stmt; + /* Pointer to '\0' if known, if NULL, it can be computed as + ptr + length. */ + tree endptr; + /* Reference count. Any changes to strinfo entry possibly shared + with dominating basic blocks need unshare_strinfo first, except + for dont_invalidate which affects only the immediately next + maybe_invalidate. */ + int refcount; + /* Copy of index. get_strinfo (si->idx) should return si; */ + int idx; + /* These 3 fields are for chaining related string pointers together. + E.g. for + bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl; + strcpy (c, d); e = c + dl; + strinfo(a) -> strinfo(c) -> strinfo(e) + All have ->first field equal to strinfo(a)->idx and are doubly + chained through prev/next fields. The later strinfos are required + to point into the same string with zero or more bytes after + the previous pointer and all bytes in between the two pointers + must be non-zero. Functions like strcpy or memcpy are supposed + to adjust all previous strinfo lengths, but not following strinfo + lengths (those are uncertain, usually invalidated during + maybe_invalidate, except when the alias oracle knows better). + Functions like strcat on the other side adjust the whole + related strinfo chain. + They are updated lazily, so to use the chain the same first fields + and si->prev->next == si->idx needs to be verified. */ + int first; + int next; + int prev; + /* A flag whether the string is known to be written in the current + function. */ + bool writable; + /* A flag for the next maybe_invalidate that this strinfo shouldn't + be invalidated. Always cleared by maybe_invalidate. */ + bool dont_invalidate; +} *strinfo; +DEF_VEC_P(strinfo); +DEF_VEC_ALLOC_P(strinfo,heap); + +/* Pool for allocating strinfo_struct entries. */ +static alloc_pool strinfo_pool; + +/* Vector mapping positive string indexes to strinfo, for the + current basic block. The first pointer in the vector is special, + it is either NULL, meaning the vector isn't shared, or it is + a basic block pointer to the owner basic_block if shared. + If some other bb wants to modify the vector, the vector needs + to be unshared first, and only the owner bb is supposed to free it. */ +static VEC(strinfo, heap) *stridx_to_strinfo; + +/* One OFFSET->IDX mapping. */ +struct stridxlist +{ + struct stridxlist *next; + HOST_WIDE_INT offset; + int idx; +}; + +/* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */ +struct decl_stridxlist_map +{ + struct tree_map_base base; + struct stridxlist list; +}; + +/* Hash table for mapping decls to a chained list of offset -> idx + mappings. */ +static htab_t decl_to_stridxlist_htab; + +/* Obstack for struct stridxlist and struct decl_stridxlist_map. */ +static struct obstack stridx_obstack; + +/* Last memcpy statement if it could be adjusted if the trailing + '\0' written is immediately overwritten, or + *x = '\0' store that could be removed if it is immediately overwritten. */ +struct laststmt_struct +{ + gimple stmt; + tree len; + int stridx; +} laststmt; + +/* Hash a from tree in a decl_stridxlist_map. */ + +static unsigned int +decl_to_stridxlist_hash (const void *item) +{ + return DECL_UID (((const struct decl_stridxlist_map *) item)->base.from); +} + +/* Helper function for get_stridx. */ + +static int +get_addr_stridx (tree exp) +{ + HOST_WIDE_INT off; + struct decl_stridxlist_map ent, *e; + struct stridxlist *list; + tree base; + + if (decl_to_stridxlist_htab == NULL) + return 0; + + base = get_addr_base_and_unit_offset (exp, &off); + if (base == NULL || !DECL_P (base)) + return 0; + + ent.base.from = base; + e = (struct decl_stridxlist_map *) + htab_find_with_hash (decl_to_stridxlist_htab, &ent, DECL_UID (base)); + if (e == NULL) + return 0; + + list = &e->list; + do + { + if (list->offset == off) + return list->idx; + list = list->next; + } + while (list); + return 0; +} + +/* Return string index for EXP. */ + +static int +get_stridx (tree exp) +{ + tree l; + + if (TREE_CODE (exp) == SSA_NAME) + return VEC_index (int, ssa_ver_to_stridx, SSA_NAME_VERSION (exp)); + + if (TREE_CODE (exp) == ADDR_EXPR) + { + int idx = get_addr_stridx (TREE_OPERAND (exp, 0)); + if (idx != 0) + return idx; + } + + l = c_strlen (exp, 0); + if (l != NULL_TREE + && host_integerp (l, 1)) + { + unsigned HOST_WIDE_INT len = tree_low_cst (l, 1); + if (len == (unsigned int) len + && (int) len >= 0) + return ~(int) len; + } + return 0; +} + +/* Return true if strinfo vector is shared with the immediate dominator. */ + +static inline bool +strinfo_shared (void) +{ + return VEC_length (strinfo, stridx_to_strinfo) + && VEC_index (strinfo, stridx_to_strinfo, 0) != NULL; +} + +/* Unshare strinfo vector that is shared with the immediate dominator. */ + +static void +unshare_strinfo_vec (void) +{ + strinfo si; + unsigned int i = 0; + + gcc_assert (strinfo_shared ()); + stridx_to_strinfo = VEC_copy (strinfo, heap, stridx_to_strinfo); + for (i = 1; VEC_iterate (strinfo, stridx_to_strinfo, i, si); ++i) + if (si != NULL) + si->refcount++; + VEC_replace (strinfo, stridx_to_strinfo, 0, NULL); +} + +/* Attempt to create a string index for exp, ADDR_EXPR's operand. + Return a pointer to the location where the string index can + be stored (if 0) or is stored, or NULL if this can't be tracked. */ + +static int * +addr_stridxptr (tree exp) +{ + void **slot; + struct decl_stridxlist_map ent; + struct stridxlist *list; + HOST_WIDE_INT off; + + tree base = get_addr_base_and_unit_offset (exp, &off); + if (base == NULL_TREE || !DECL_P (base)) + return NULL; + + if (decl_to_stridxlist_htab == NULL) + { + decl_to_stridxlist_htab + = htab_create (64, decl_to_stridxlist_hash, tree_map_base_eq, NULL); + gcc_obstack_init (&stridx_obstack); + } + ent.base.from = base; + slot = htab_find_slot_with_hash (decl_to_stridxlist_htab, &ent, + DECL_UID (base), INSERT); + if (*slot) + { + int i; + list = &((struct decl_stridxlist_map *)*slot)->list; + for (i = 0; i < 16; i++) + { + if (list->offset == off) + return &list->idx; + if (list->next == NULL) + break; + } + if (i == 16) + return NULL; + list->next = XOBNEW (&stridx_obstack, struct stridxlist); + list = list->next; + } + else + { + struct decl_stridxlist_map *e + = XOBNEW (&stridx_obstack, struct decl_stridxlist_map); + e->base.from = base; + *slot = (void *) e; + list = &e->list; + } + list->next = NULL; + list->offset = off; + list->idx = 0; + return &list->idx; +} + +/* Create a new string index, or return 0 if reached limit. */ + +static int +new_stridx (tree exp) +{ + int idx; + if (max_stridx >= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS)) + return 0; + if (TREE_CODE (exp) == SSA_NAME) + { + if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp)) + return 0; + idx = max_stridx++; + VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (exp), idx); + return idx; + } + if (TREE_CODE (exp) == ADDR_EXPR) + { + int *pidx = addr_stridxptr (TREE_OPERAND (exp, 0)); + if (pidx != NULL) + { + gcc_assert (*pidx == 0); + *pidx = max_stridx++; + return *pidx; + } + } + return 0; +} + +/* Like new_stridx, but for ADDR_EXPR's operand instead. */ + +static int +new_addr_stridx (tree exp) +{ + int *pidx; + if (max_stridx >= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS)) + return 0; + pidx = addr_stridxptr (exp); + if (pidx != NULL) + { + gcc_assert (*pidx == 0); + *pidx = max_stridx++; + return *pidx; + } + return 0; +} + +/* Create a new strinfo. */ + +static strinfo +new_strinfo (tree ptr, int idx, tree length) +{ + strinfo si = (strinfo) pool_alloc (strinfo_pool); + si->length = length; + si->ptr = ptr; + si->stmt = NULL; + si->endptr = NULL_TREE; + si->refcount = 1; + si->idx = idx; + si->first = 0; + si->prev = 0; + si->next = 0; + si->writable = false; + si->dont_invalidate = false; + return si; +} + +/* Decrease strinfo refcount and free it if not referenced anymore. */ + +static inline void +free_strinfo (strinfo si) +{ + if (si && --si->refcount == 0) + pool_free (strinfo_pool, si); +} + +/* Return strinfo vector entry IDX. */ + +static inline strinfo +get_strinfo (int idx) +{ + if (VEC_length (strinfo, stridx_to_strinfo) <= (unsigned int) idx) + return NULL; + return VEC_index (strinfo, stridx_to_strinfo, idx); +} + +/* Set strinfo in the vector entry IDX to SI. */ + +static inline void +set_strinfo (int idx, strinfo si) +{ + if (VEC_length (strinfo, stridx_to_strinfo) && VEC_index (strinfo, stridx_to_strinfo, 0)) + unshare_strinfo_vec (); + if (VEC_length (strinfo, stridx_to_strinfo) <= (unsigned int) idx) + VEC_safe_grow_cleared (strinfo, heap, stridx_to_strinfo, idx + 1); + VEC_replace (strinfo, stridx_to_strinfo, idx, si); +} + +/* Return string length, or NULL if it can't be computed. */ + +static tree +get_string_length (strinfo si) +{ + if (si->length) + return si->length; + + if (si->stmt) + { + gimple stmt = si->stmt, lenstmt; + tree callee, lhs, lhs_var, fn, tem; + location_t loc; + gimple_stmt_iterator gsi; + + gcc_assert (is_gimple_call (stmt)); + callee = gimple_call_fndecl (stmt); + gcc_assert (callee && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL); + lhs = gimple_call_lhs (stmt); + gcc_assert (implicit_built_in_decls[BUILT_IN_STRCPY] != NULL_TREE); + /* unshare_strinfo is intentionally not called here. The (delayed) + transformation of strcpy or strcat into stpcpy is done at the place + of the former strcpy/strcat call and so can affect all the strinfos + with the same stmt. If they were unshared before and transformation + has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should + just compute the right length. */ + switch (DECL_FUNCTION_CODE (callee)) + { + case BUILT_IN_STRCAT: + case BUILT_IN_STRCAT_CHK: + gsi = gsi_for_stmt (stmt); + fn = implicit_built_in_decls[BUILT_IN_STRLEN]; + gcc_assert (lhs == NULL_TREE); + lhs_var = create_tmp_var (TREE_TYPE (TREE_TYPE (fn)), NULL); + add_referenced_var (lhs_var); + tem = unshare_expr (gimple_call_arg (stmt, 0)); + lenstmt = gimple_build_call (fn, 1, tem); + lhs = make_ssa_name (lhs_var, lenstmt); + gimple_call_set_lhs (lenstmt, lhs); + gimple_set_vuse (lenstmt, gimple_vuse (stmt)); + gsi_insert_before (&gsi, lenstmt, GSI_SAME_STMT); + lhs_var = create_tmp_var (TREE_TYPE (gimple_call_arg (stmt, 0)), + NULL); + add_referenced_var (lhs_var); + tem = gimple_call_arg (stmt, 0); + lenstmt + = gimple_build_assign_with_ops (POINTER_PLUS_EXPR, + make_ssa_name (lhs_var, NULL), + tem, lhs); + gsi_insert_before (&gsi, lenstmt, GSI_SAME_STMT); + gimple_call_set_arg (stmt, 0, gimple_assign_lhs (lenstmt)); + lhs = NULL_TREE; + /* FALLTHRU */ + case BUILT_IN_STRCPY: + case BUILT_IN_STRCPY_CHK: + if (gimple_call_num_args (stmt) == 2) + fn = implicit_built_in_decls[BUILT_IN_STPCPY]; + else + fn = built_in_decls[BUILT_IN_STPCPY_CHK]; + gcc_assert (lhs == NULL_TREE); + if (dump_file && (dump_flags & TDF_DETAILS) != 0) + { + fprintf (dump_file, "Optimizing: "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + } + gimple_call_set_fndecl (stmt, fn); + lhs_var = create_tmp_var (TREE_TYPE (TREE_TYPE (fn)), NULL); + add_referenced_var (lhs_var); + lhs = make_ssa_name (lhs_var, stmt); + gimple_call_set_lhs (stmt, lhs); + update_stmt (stmt); + if (dump_file && (dump_flags & TDF_DETAILS) != 0) + { + fprintf (dump_file, "into: "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + } + /* FALLTHRU */ + case BUILT_IN_STPCPY: + case BUILT_IN_STPCPY_CHK: + gcc_assert (lhs != NULL_TREE); + loc = gimple_location (stmt); + si->endptr = lhs; + si->stmt = NULL; + lhs = fold_convert_loc (loc, size_type_node, lhs); + si->length = fold_convert_loc (loc, size_type_node, si->ptr); + si->length = fold_build2_loc (loc, MINUS_EXPR, size_type_node, + lhs, si->length); + break; + default: + gcc_unreachable (); + break; + } + } + + return si->length; +} + +/* Invalidate string length information for strings whose length + might change due to stores in stmt. */ + +static bool +maybe_invalidate (gimple stmt) +{ + strinfo si; + unsigned int i; + bool nonempty = false; + + for (i = 1; VEC_iterate (strinfo, stridx_to_strinfo, i, si); ++i) + if (si != NULL) + { + if (!si->dont_invalidate) + { + ao_ref r; + ao_ref_init_from_ptr_and_size (&r, si->ptr, NULL_TREE); + if (stmt_may_clobber_ref_p_1 (stmt, &r)) + { + set_strinfo (i, NULL); + free_strinfo (si); + continue; + } + } + si->dont_invalidate = false; + nonempty = true; + } + return nonempty; +} + +/* Unshare strinfo record SI, if it has recount > 1 or + if stridx_to_strinfo vector is shared with some other + bbs. */ + +static strinfo +unshare_strinfo (strinfo si) +{ + strinfo nsi; + + if (si->refcount == 1 && !strinfo_shared ()) + return si; + + nsi = new_strinfo (si->ptr, si->idx, si->length); + nsi->stmt = si->stmt; + nsi->endptr = si->endptr; + nsi->first = si->first; + nsi->prev = si->prev; + nsi->next = si->next; + nsi->writable = si->writable; + set_strinfo (si->idx, nsi); + free_strinfo (si); + return nsi; +} + +/* Return first strinfo in the related strinfo chain + if all strinfos in between belong to the chain, otherwise + NULL. */ + +static strinfo +verify_related_strinfos (strinfo origsi) +{ + strinfo si = origsi, psi; + + if (origsi->first == 0) + return NULL; + for (; si->prev; si = psi) + { + if (si->first != origsi->first) + return NULL; + psi = get_strinfo (si->prev); + if (psi == NULL) + return NULL; + if (psi->next != si->idx) + return NULL; + } + if (si->idx != si->first) + return NULL; + return si; +} + +/* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points + to a zero-length string and if possible chain it to a related strinfo + chain whose part is or might be CHAINSI. */ + +static strinfo +zero_length_string (tree ptr, strinfo chainsi) +{ + strinfo si; + int idx; + gcc_checking_assert (TREE_CODE (ptr) == SSA_NAME + && get_stridx (ptr) == 0); + + if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr)) + return NULL; + if (chainsi != NULL) + { + si = verify_related_strinfos (chainsi); + if (si) + { + chainsi = si; + for (; chainsi->next; chainsi = si) + { + if (chainsi->endptr == NULL_TREE) + { + chainsi = unshare_strinfo (chainsi); + chainsi->endptr = ptr; + } + si = get_strinfo (chainsi->next); + if (si == NULL + || si->first != chainsi->first + || si->prev != chainsi->idx) + break; + } + gcc_assert (chainsi->length); + if (chainsi->endptr == NULL_TREE) + { + chainsi = unshare_strinfo (chainsi); + chainsi->endptr = ptr; + } + if (integer_zerop (chainsi->length)) + { + if (chainsi->next) + { + chainsi = unshare_strinfo (chainsi); + chainsi->next = 0; + } + VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (ptr), + chainsi->idx); + return chainsi; + } + } + else if (chainsi->first || chainsi->prev || chainsi->next) + { + chainsi = unshare_strinfo (chainsi); + chainsi->first = 0; + chainsi->prev = 0; + chainsi->next = 0; + } + } + idx = new_stridx (ptr); + if (idx == 0) + return NULL; + si = new_strinfo (ptr, idx, build_int_cst (size_type_node, 0)); + set_strinfo (idx, si); + si->endptr = ptr; + if (chainsi != NULL) + { + chainsi = unshare_strinfo (chainsi); + if (chainsi->first == 0) + chainsi->first = chainsi->idx; + chainsi->next = idx; + si->prev = chainsi->idx; + si->first = chainsi->first; + si->writable = chainsi->writable; + } + return si; +} + +/* For strinfo ORIGSI whose length has been just updated + update also related strinfo lengths (add ADJ to each, + but don't adjust ORIGSI). */ + +static void +adjust_related_strinfos (location_t loc, strinfo origsi, tree adj) +{ + strinfo si = verify_related_strinfos (origsi); + + if (si == NULL) + return; + + while (1) + { + strinfo nsi; + + if (si != origsi) + { + tree tem; + + si = unshare_strinfo (si); + gcc_assert (si->length); + tem = fold_convert_loc (loc, TREE_TYPE (si->length), adj); + si->length = fold_build2_loc (loc, PLUS_EXPR, + TREE_TYPE (si->length), si->length, + tem); + si->endptr = NULL_TREE; + si->dont_invalidate = true; + } + if (si->next == 0) + return; + nsi = get_strinfo (si->next); + if (nsi == NULL + || nsi->first != si->first + || nsi->prev != si->idx) + return; + si = nsi; + } +} + +/* Find if there are other SSA_NAME pointers equal to PTR + for which we don't track their string lengths yet. If so, use + IDX for them. */ + +static void +find_equal_ptrs (tree ptr, int idx) +{ + if (TREE_CODE (ptr) != SSA_NAME) + return; + while (1) + { + gimple stmt = SSA_NAME_DEF_STMT (ptr); + if (!is_gimple_assign (stmt)) + return; + ptr = gimple_assign_rhs1 (stmt); + switch (gimple_assign_rhs_code (stmt)) + { + case SSA_NAME: + break; + case ADDR_EXPR: + { + int *pidx = addr_stridxptr (TREE_OPERAND (ptr, 0)); + if (pidx != NULL && *pidx == 0) + *pidx = idx; + return; + } + CASE_CONVERT: + if (POINTER_TYPE_P (TREE_TYPE (ptr))) + break; + return; + default: + return; + } + + /* We might find an endptr created in this pass. Grow the + vector in that case. */ + if (VEC_length (int, ssa_ver_to_stridx) <= SSA_NAME_VERSION (ptr)) + VEC_safe_grow_cleared (int, heap, ssa_ver_to_stridx, num_ssa_names); + + if (VEC_index (int, ssa_ver_to_stridx, SSA_NAME_VERSION (ptr)) != 0) + return; + VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (ptr), idx); + } +} + +/* If the last .MEM setter statement before STMT is + memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT + and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to + just memcpy (x, y, strlen (y)). SI must be the zero length + strinfo. */ + +static void +adjust_last_stmt (strinfo si, gimple stmt, bool is_strcat) +{ + tree vuse, callee, len; + struct laststmt_struct last = laststmt; + strinfo lastsi, firstsi; + + laststmt.stmt = NULL; + laststmt.len = NULL_TREE; + laststmt.stridx = 0; + + if (last.stmt == NULL) + return; + + vuse = gimple_vuse (stmt); + if (vuse == NULL_TREE + || SSA_NAME_DEF_STMT (vuse) != last.stmt + || !has_single_use (vuse)) + return; + + gcc_assert (last.stridx > 0); + lastsi = get_strinfo (last.stridx); + if (lastsi == NULL) + return; + + if (lastsi != si) + { + if (lastsi->first == 0 || lastsi->first != si->first) + return; + + firstsi = verify_related_strinfos (si); + if (firstsi == NULL) + return; + while (firstsi != lastsi) + { + strinfo nextsi; + if (firstsi->next == 0) + return; + nextsi = get_strinfo (firstsi->next); + if (nextsi == NULL + || nextsi->prev != firstsi->idx + || nextsi->first != si->first) + return; + firstsi = nextsi; + } + } + + if (!is_strcat) + { + if (si->length == NULL_TREE || !integer_zerop (si->length)) + return; + } + + if (is_gimple_assign (last.stmt)) + { + gimple_stmt_iterator gsi; + + if (!integer_zerop (gimple_assign_rhs1 (last.stmt))) + return; + if (stmt_could_throw_p (last.stmt)) + return; + gsi = gsi_for_stmt (last.stmt); + unlink_stmt_vdef (last.stmt); + release_defs (last.stmt); + gsi_remove (&gsi, true); + return; + } + + if (!is_gimple_call (last.stmt)) + return; + callee = gimple_call_fndecl (last.stmt); + if (callee == NULL_TREE || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL) + return; + + switch (DECL_FUNCTION_CODE (callee)) + { + case BUILT_IN_MEMCPY: + case BUILT_IN_MEMCPY_CHK: + break; + default: + return; + } + + len = gimple_call_arg (last.stmt, 2); + if (host_integerp (len, 1)) + { + if (!host_integerp (last.len, 1) + || integer_zerop (len) + || (unsigned HOST_WIDE_INT) tree_low_cst (len, 1) + != (unsigned HOST_WIDE_INT) tree_low_cst (last.len, 1) + 1) + return; + /* Don't adjust the length if it is divisible by 4, it is more efficient + to store the extra '\0' in that case. */ + if ((((unsigned HOST_WIDE_INT) tree_low_cst (len, 1)) & 3) == 0) + return; + } + else if (TREE_CODE (len) == SSA_NAME) + { + gimple def_stmt = SSA_NAME_DEF_STMT (len); + if (!is_gimple_assign (def_stmt) + || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR + || gimple_assign_rhs1 (def_stmt) != last.len + || !integer_onep (gimple_assign_rhs2 (def_stmt))) + return; + } + else + return; + + gimple_call_set_arg (last.stmt, 2, last.len); + update_stmt (last.stmt); +} + +/* Handle a strlen call. If strlen of the argument is known, replace + the strlen call with the known value, otherwise remember that strlen + of the argument is stored in the lhs SSA_NAME. */ + +static void +handle_builtin_strlen (gimple_stmt_iterator *gsi) +{ + int idx; + tree src; + gimple stmt = gsi_stmt (*gsi); + tree lhs = gimple_call_lhs (stmt); + + if (lhs == NULL_TREE) + return; + + src = gimple_call_arg (stmt, 0); + idx = get_stridx (src); + if (idx) + { + strinfo si = NULL; + tree rhs; + + if (idx < 0) + rhs = build_int_cst (TREE_TYPE (lhs), ~idx); + else + { + rhs = NULL_TREE; + si = get_strinfo (idx); + if (si != NULL) + rhs = get_string_length (si); + } + if (rhs != NULL_TREE) + { + if (dump_file && (dump_flags & TDF_DETAILS) != 0) + { + fprintf (dump_file, "Optimizing: "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + } + rhs = unshare_expr (rhs); + if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs))) + rhs = fold_convert_loc (gimple_location (stmt), + TREE_TYPE (lhs), rhs); + if (!update_call_from_tree (gsi, rhs)) + gimplify_and_update_call_from_tree (gsi, rhs); + stmt = gsi_stmt (*gsi); + update_stmt (stmt); + if (dump_file && (dump_flags & TDF_DETAILS) != 0) + { + fprintf (dump_file, "into: "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + } + if (si != NULL + && TREE_CODE (si->length) != SSA_NAME + && TREE_CODE (si->length) != INTEGER_CST + && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) + { + si = unshare_strinfo (si); + si->length = lhs; + } + return; + } + } + if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) + return; + if (idx == 0) + idx = new_stridx (src); + else if (get_strinfo (idx) != NULL) + return; + if (idx) + { + strinfo si = new_strinfo (src, idx, lhs); + set_strinfo (idx, si); + find_equal_ptrs (src, idx); + } +} + +/* Handle a strchr call. If strlen of the first argument is known, replace + the strchr (x, 0) call with the endptr or x + strlen, otherwise remember + that lhs of the call is endptr and strlen of the argument is endptr - x. */ + +static void +handle_builtin_strchr (gimple_stmt_iterator *gsi) +{ + int idx; + tree src; + gimple stmt = gsi_stmt (*gsi); + tree lhs = gimple_call_lhs (stmt); + + if (lhs == NULL_TREE) + return; + + if (!integer_zerop (gimple_call_arg (stmt, 1))) + return; + + src = gimple_call_arg (stmt, 0); + idx = get_stridx (src); + if (idx) + { + strinfo si = NULL; + tree rhs; + + if (idx < 0) + rhs = build_int_cst (size_type_node, ~idx); + else + { + rhs = NULL_TREE; + si = get_strinfo (idx); + if (si != NULL) + rhs = get_string_length (si); + } + if (rhs != NULL_TREE) + { + location_t loc = gimple_location (stmt); + + if (dump_file && (dump_flags & TDF_DETAILS) != 0) + { + fprintf (dump_file, "Optimizing: "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + } + if (si != NULL && si->endptr != NULL_TREE) + { + rhs = unshare_expr (si->endptr); + if (!useless_type_conversion_p (TREE_TYPE (lhs), + TREE_TYPE (rhs))) + rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs); + } + else + { + rhs = fold_convert_loc (loc, sizetype, unshare_expr (rhs)); + rhs = fold_build2_loc (loc, POINTER_PLUS_EXPR, + TREE_TYPE (src), src, rhs); + if (!useless_type_conversion_p (TREE_TYPE (lhs), + TREE_TYPE (rhs))) + rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs); + } + if (!update_call_from_tree (gsi, rhs)) + gimplify_and_update_call_from_tree (gsi, rhs); + stmt = gsi_stmt (*gsi); + update_stmt (stmt); + if (dump_file && (dump_flags & TDF_DETAILS) != 0) + { + fprintf (dump_file, "into: "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + } + if (si != NULL + && si->endptr == NULL_TREE + && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) + { + si = unshare_strinfo (si); + si->endptr = lhs; + } + zero_length_string (lhs, si); + return; + } + } + if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) + return; + if (TREE_CODE (src) != SSA_NAME || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src)) + { + if (idx == 0) + idx = new_stridx (src); + else if (get_strinfo (idx) != NULL) + { + zero_length_string (lhs, NULL); + return; + } + if (idx) + { + location_t loc = gimple_location (stmt); + tree lhsu = fold_convert_loc (loc, size_type_node, lhs); + tree srcu = fold_convert_loc (loc, size_type_node, src); + tree length = fold_build2_loc (loc, MINUS_EXPR, + size_type_node, lhsu, srcu); + strinfo si = new_strinfo (src, idx, length); + si->endptr = lhs; + set_strinfo (idx, si); + find_equal_ptrs (src, idx); + zero_length_string (lhs, si); + } + } + else + zero_length_string (lhs, NULL); +} + +/* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call. + If strlen of the second argument is known, strlen of the first argument + is the same after this call. Furthermore, attempt to convert it to + memcpy. */ + +static void +handle_builtin_strcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi) +{ + int idx, didx; + tree src, dst, srclen, len, lhs, args, type, fn, oldlen; + bool success; + gimple stmt = gsi_stmt (*gsi); + strinfo si, dsi, olddsi, zsi; + location_t loc; + + src = gimple_call_arg (stmt, 1); + dst = gimple_call_arg (stmt, 0); + lhs = gimple_call_lhs (stmt); + idx = get_stridx (src); + si = NULL; + if (idx > 0) + si = get_strinfo (idx); + + didx = get_stridx (dst); + olddsi = NULL; + oldlen = NULL_TREE; + if (didx > 0) + olddsi = get_strinfo (didx); + else if (didx < 0) + return; + + if (olddsi != NULL) + adjust_last_stmt (olddsi, stmt, false); + + srclen = NULL_TREE; + if (si != NULL) + srclen = get_string_length (si); + else if (idx < 0) + srclen = build_int_cst (size_type_node, ~idx); + + loc = gimple_location (stmt); + if (srclen == NULL_TREE) + switch (bcode) + { + case BUILT_IN_STRCPY: + case BUILT_IN_STRCPY_CHK: + if (implicit_built_in_decls[BUILT_IN_STPCPY] == NULL_TREE + || lhs != NULL_TREE) + return; + break; + case BUILT_IN_STPCPY: + case BUILT_IN_STPCPY_CHK: + if (lhs == NULL_TREE) + return; + else + { + tree lhsuint = fold_convert_loc (loc, size_type_node, lhs); + srclen = fold_convert_loc (loc, size_type_node, dst); + srclen = fold_build2_loc (loc, MINUS_EXPR, size_type_node, + lhsuint, srclen); + } + break; + default: + gcc_unreachable (); + } + + if (didx == 0) + { + didx = new_stridx (dst); + if (didx == 0) + return; + } + if (olddsi != NULL) + { + oldlen = olddsi->length; + dsi = unshare_strinfo (olddsi); + dsi->length = srclen; + /* Break the chain, so adjust_related_strinfo on later pointers in + the chain won't adjust this one anymore. */ + dsi->next = 0; + dsi->stmt = NULL; + dsi->endptr = NULL_TREE; + } + else + { + dsi = new_strinfo (dst, didx, srclen); + set_strinfo (didx, dsi); + find_equal_ptrs (dst, didx); + } + dsi->writable = true; + dsi->dont_invalidate = true; + + if (dsi->length == NULL_TREE) + { + /* If string length of src is unknown, use delayed length + computation. If string lenth of dst will be needed, it + can be computed by transforming this strcpy call into + stpcpy and subtracting dst from the return value. */ + dsi->stmt = stmt; + return; + } + + if (olddsi != NULL) + { + tree adj = NULL_TREE; + if (oldlen == NULL_TREE) + ; + else if (integer_zerop (oldlen)) + adj = srclen; + else if (TREE_CODE (oldlen) == INTEGER_CST + || TREE_CODE (srclen) == INTEGER_CST) + adj = fold_build2_loc (loc, MINUS_EXPR, + TREE_TYPE (srclen), srclen, + fold_convert_loc (loc, TREE_TYPE (srclen), + oldlen)); + if (adj != NULL_TREE) + adjust_related_strinfos (loc, dsi, adj); + else + dsi->prev = 0; + } + /* strcpy src may not overlap dst, so src doesn't need to be + invalidated either. */ + if (si != NULL) + si->dont_invalidate = true; + + fn = NULL_TREE; + zsi = NULL; + switch (bcode) + { + case BUILT_IN_STRCPY: + fn = implicit_built_in_decls[BUILT_IN_MEMCPY]; + if (lhs) + VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs), didx); + break; + case BUILT_IN_STRCPY_CHK: + fn = built_in_decls[BUILT_IN_MEMCPY_CHK]; + if (lhs) + VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs), didx); + break; + case BUILT_IN_STPCPY: + /* This would need adjustment of the lhs (subtract one), + or detection that the trailing '\0' doesn't need to be + written, if it will be immediately overwritten. + fn = built_in_decls[BUILT_IN_MEMPCPY]; */ + if (lhs) + { + dsi->endptr = lhs; + zsi = zero_length_string (lhs, dsi); + } + break; + case BUILT_IN_STPCPY_CHK: + /* This would need adjustment of the lhs (subtract one), + or detection that the trailing '\0' doesn't need to be + written, if it will be immediately overwritten. + fn = built_in_decls[BUILT_IN_MEMPCPY_CHK]; */ + if (lhs) + { + dsi->endptr = lhs; + zsi = zero_length_string (lhs, dsi); + } + break; + default: + gcc_unreachable (); + } + if (zsi != NULL) + zsi->dont_invalidate = true; + + if (fn == NULL_TREE) + return; + + args = TYPE_ARG_TYPES (TREE_TYPE (fn)); + type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args))); + + len = fold_convert_loc (loc, type, unshare_expr (srclen)); + len = fold_build2_loc (loc, PLUS_EXPR, type, len, build_int_cst (type, 1)); + len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true, + GSI_SAME_STMT); + if (dump_file && (dump_flags & TDF_DETAILS) != 0) + { + fprintf (dump_file, "Optimizing: "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + } + if (gimple_call_num_args (stmt) == 2) + success = update_gimple_call (gsi, fn, 3, dst, src, len); + else + success = update_gimple_call (gsi, fn, 4, dst, src, len, + gimple_call_arg (stmt, 2)); + if (success) + { + stmt = gsi_stmt (*gsi); + update_stmt (stmt); + if (dump_file && (dump_flags & TDF_DETAILS) != 0) + { + fprintf (dump_file, "into: "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + } + /* Allow adjust_last_stmt to decrease this memcpy's size. */ + laststmt.stmt = stmt; + laststmt.len = srclen; + laststmt.stridx = dsi->idx; + } + else if (dump_file && (dump_flags & TDF_DETAILS) != 0) + fprintf (dump_file, "not possible.\n"); +} + +/* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call. + If strlen of the second argument is known and length of the third argument + is that plus one, strlen of the first argument is the same after this + call. */ + +static void +handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi) +{ + int idx, didx; + tree src, dst, len, lhs, oldlen, newlen; + gimple stmt = gsi_stmt (*gsi); + strinfo si, dsi, olddsi; + + len = gimple_call_arg (stmt, 2); + src = gimple_call_arg (stmt, 1); + dst = gimple_call_arg (stmt, 0); + idx = get_stridx (src); + if (idx == 0) + return; + + didx = get_stridx (dst); + olddsi = NULL; + if (didx > 0) + olddsi = get_strinfo (didx); + else if (didx < 0) + return; + + if (olddsi != NULL + && host_integerp (len, 1) + && !integer_zerop (len)) + adjust_last_stmt (olddsi, stmt, false); + + if (idx > 0) + { + gimple def_stmt; + + /* Handle memcpy (x, y, l) where l is strlen (y) + 1. */ + si = get_strinfo (idx); + if (si == NULL || si->length == NULL_TREE) + return; + if (TREE_CODE (len) != SSA_NAME) + return; + def_stmt = SSA_NAME_DEF_STMT (len); + if (!is_gimple_assign (def_stmt) + || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR + || gimple_assign_rhs1 (def_stmt) != si->length + || !integer_onep (gimple_assign_rhs2 (def_stmt))) + return; + } + else + { + si = NULL; + /* Handle memcpy (x, "abcd", 5) or + memcpy (x, "abc\0uvw", 7). */ + if (!host_integerp (len, 1) + || (unsigned HOST_WIDE_INT) tree_low_cst (len, 1) + <= (unsigned HOST_WIDE_INT) ~idx) + return; + } + + if (olddsi != NULL && TREE_CODE (len) == SSA_NAME) + adjust_last_stmt (olddsi, stmt, false); + + if (didx == 0) + { + didx = new_stridx (dst); + if (didx == 0) + return; + } + if (si != NULL) + newlen = si->length; + else + newlen = build_int_cst (TREE_TYPE (len), ~idx); + oldlen = NULL_TREE; + if (olddsi != NULL) + { + dsi = unshare_strinfo (olddsi); + oldlen = olddsi->length; + dsi->length = newlen; + /* Break the chain, so adjust_related_strinfo on later pointers in + the chain won't adjust this one anymore. */ + dsi->next = 0; + dsi->stmt = NULL; + dsi->endptr = NULL_TREE; + } + else + { + dsi = new_strinfo (dst, didx, newlen); + set_strinfo (didx, dsi); + find_equal_ptrs (dst, didx); + } + dsi->writable = true; + dsi->dont_invalidate = true; + if (olddsi != NULL) + { + tree adj = NULL_TREE; + location_t loc = gimple_location (stmt); + if (oldlen == NULL_TREE) + ; + else if (integer_zerop (oldlen)) + adj = dsi->length; + else if (TREE_CODE (oldlen) == INTEGER_CST + || TREE_CODE (dsi->length) == INTEGER_CST) + adj = fold_build2_loc (loc, MINUS_EXPR, + TREE_TYPE (dsi->length), dsi->length, + fold_convert_loc (loc, TREE_TYPE (dsi->length), + oldlen)); + if (adj != NULL_TREE) + adjust_related_strinfos (loc, dsi, adj); + else + dsi->prev = 0; + } + /* memcpy src may not overlap dst, so src doesn't need to be + invalidated either. */ + if (si != NULL) + si->dont_invalidate = true; + + lhs = gimple_call_lhs (stmt); + switch (bcode) + { + case BUILT_IN_MEMCPY: + case BUILT_IN_MEMCPY_CHK: + /* Allow adjust_last_stmt to decrease this memcpy's size. */ + laststmt.stmt = stmt; + laststmt.len = dsi->length; + laststmt.stridx = dsi->idx; + if (lhs) + VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs), didx); + break; + case BUILT_IN_MEMPCPY: + case BUILT_IN_MEMPCPY_CHK: + break; + default: + gcc_unreachable (); + } +} + +/* Handle a strcat-like ({strcat,__strcat_chk}) call. + If strlen of the second argument is known, strlen of the first argument + is increased by the length of the second argument. Furthermore, attempt + to convert it to memcpy/strcpy if the length of the first argument + is known. */ + +static void +handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi) +{ + int idx, didx; + tree src, dst, srclen, dstlen, len, lhs, args, type, fn, objsz, endptr; + bool success; + gimple stmt = gsi_stmt (*gsi); + strinfo si, dsi; + location_t loc; + + src = gimple_call_arg (stmt, 1); + dst = gimple_call_arg (stmt, 0); + lhs = gimple_call_lhs (stmt); + + didx = get_stridx (dst); + if (didx < 0) + return; + + dsi = NULL; + if (didx > 0) + dsi = get_strinfo (didx); + if (dsi == NULL || get_string_length (dsi) == NULL_TREE) + { + /* strcat (p, q) can be transformed into + tmp = p + strlen (p); endptr = strpcpy (tmp, q); + with length endptr - p if we need to compute the length + later on. Don't do this transformation if we don't need + it. */ + if (implicit_built_in_decls[BUILT_IN_STPCPY] != NULL_TREE + && lhs == NULL_TREE) + { + if (didx == 0) + { + didx = new_stridx (dst); + if (didx == 0) + return; + } + if (dsi == NULL) + { + dsi = new_strinfo (dst, didx, NULL_TREE); + set_strinfo (didx, dsi); + find_equal_ptrs (dst, didx); + } + else + { + dsi = unshare_strinfo (dsi); + dsi->length = NULL_TREE; + dsi->next = 0; + dsi->endptr = NULL_TREE; + } + dsi->writable = true; + dsi->stmt = stmt; + dsi->dont_invalidate = true; + } + return; + } + + srclen = NULL_TREE; + si = NULL; + idx = get_stridx (src); + if (idx < 0) + srclen = build_int_cst (size_type_node, ~idx); + else if (idx > 0) + { + si = get_strinfo (idx); + if (si != NULL) + srclen = get_string_length (si); + } + + loc = gimple_location (stmt); + dstlen = dsi->length; + endptr = dsi->endptr; + + dsi = unshare_strinfo (dsi); + dsi->endptr = NULL_TREE; + dsi->stmt = NULL; + dsi->writable = true; + + if (srclen != NULL_TREE) + { + dsi->length = fold_build2_loc (loc, PLUS_EXPR, TREE_TYPE (dsi->length), + dsi->length, srclen); + adjust_related_strinfos (loc, dsi, srclen); + dsi->dont_invalidate = true; + } + else + { + dsi->length = NULL; + if (implicit_built_in_decls[BUILT_IN_STPCPY] != NULL_TREE + && lhs == NULL_TREE) + dsi->dont_invalidate = true; + } + + if (si != NULL) + /* strcat src may not overlap dst, so src doesn't need to be + invalidated either. */ + si->dont_invalidate = true; + + /* For now. Could remove the lhs from the call and add + lhs = dst; afterwards. */ + if (lhs) + return; + + fn = NULL_TREE; + objsz = NULL_TREE; + switch (bcode) + { + case BUILT_IN_STRCAT: + if (srclen != NULL_TREE) + fn = implicit_built_in_decls[BUILT_IN_MEMCPY]; + else + fn = implicit_built_in_decls[BUILT_IN_STRCPY]; + break; + case BUILT_IN_STRCAT_CHK: + if (srclen != NULL_TREE) + fn = built_in_decls[BUILT_IN_MEMCPY_CHK]; + else + fn = built_in_decls[BUILT_IN_STRCPY_CHK]; + objsz = gimple_call_arg (stmt, 2); + break; + default: + gcc_unreachable (); + } + + if (fn == NULL_TREE) + return; + + len = NULL_TREE; + if (srclen != NULL_TREE) + { + args = TYPE_ARG_TYPES (TREE_TYPE (fn)); + type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args))); + + len = fold_convert_loc (loc, type, unshare_expr (srclen)); + len = fold_build2_loc (loc, PLUS_EXPR, type, len, + build_int_cst (type, 1)); + len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true, + GSI_SAME_STMT); + } + if (endptr) + dst = fold_convert_loc (loc, TREE_TYPE (dst), unshare_expr (endptr)); + else + dst = fold_build2_loc (loc, POINTER_PLUS_EXPR, + TREE_TYPE (dst), unshare_expr (dst), + fold_convert_loc (loc, sizetype, + unshare_expr (dstlen))); + dst = force_gimple_operand_gsi (gsi, dst, true, NULL_TREE, true, + GSI_SAME_STMT); + if (dump_file && (dump_flags & TDF_DETAILS) != 0) + { + fprintf (dump_file, "Optimizing: "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + } + if (srclen != NULL_TREE) + success = update_gimple_call (gsi, fn, 3 + (objsz != NULL_TREE), + dst, src, len, objsz); + else + success = update_gimple_call (gsi, fn, 2 + (objsz != NULL_TREE), + dst, src, objsz); + if (success) + { + stmt = gsi_stmt (*gsi); + update_stmt (stmt); + if (dump_file && (dump_flags & TDF_DETAILS) != 0) + { + fprintf (dump_file, "into: "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + } + /* If srclen == NULL, note that current string length can be + computed by transforming this strcpy into stpcpy. */ + if (srclen == NULL_TREE && dsi->dont_invalidate) + dsi->stmt = stmt; + adjust_last_stmt (dsi, stmt, true); + if (srclen != NULL_TREE) + { + laststmt.stmt = stmt; + laststmt.len = srclen; + laststmt.stridx = dsi->idx; + } + } + else if (dump_file && (dump_flags & TDF_DETAILS) != 0) + fprintf (dump_file, "not possible.\n"); +} + +/* Handle a POINTER_PLUS_EXPR statement. + For p = "abcd" + 2; compute associated length, or if + p = q + off is pointing to a '\0' character of a string, call + zero_length_string on it. */ + +static void +handle_pointer_plus (gimple_stmt_iterator *gsi) +{ + gimple stmt = gsi_stmt (*gsi); + tree lhs = gimple_assign_lhs (stmt), off; + int idx = get_stridx (gimple_assign_rhs1 (stmt)); + strinfo si, zsi; + + if (idx == 0) + return; + + if (idx < 0) + { + tree off = gimple_assign_rhs2 (stmt); + if (host_integerp (off, 1) + && (unsigned HOST_WIDE_INT) tree_low_cst (off, 1) + <= (unsigned HOST_WIDE_INT) ~idx) + VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs), + ~(~idx - (int) tree_low_cst (off, 1))); + return; + } + + si = get_strinfo (idx); + if (si == NULL || si->length == NULL_TREE) + return; + + off = gimple_assign_rhs2 (stmt); + zsi = NULL; + if (operand_equal_p (si->length, off, 0)) + zsi = zero_length_string (lhs, si); + else if (TREE_CODE (off) == SSA_NAME) + { + gimple def_stmt = SSA_NAME_DEF_STMT (off); + if (gimple_assign_single_p (def_stmt) + && operand_equal_p (si->length, gimple_assign_rhs1 (def_stmt), 0)) + zsi = zero_length_string (lhs, si); + } + if (zsi != NULL + && si->endptr != NULL_TREE + && si->endptr != lhs + && TREE_CODE (si->endptr) == SSA_NAME) + { + enum tree_code rhs_code + = useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (si->endptr)) + ? SSA_NAME : NOP_EXPR; + gimple_assign_set_rhs_with_ops (gsi, rhs_code, si->endptr, NULL_TREE); + gcc_assert (gsi_stmt (*gsi) == stmt); + update_stmt (stmt); + } +} + +/* Handle a single character store. */ + +static bool +handle_char_store (gimple_stmt_iterator *gsi) +{ + int idx = -1; + strinfo si = NULL; + gimple stmt = gsi_stmt (*gsi); + tree ssaname = NULL_TREE, lhs = gimple_assign_lhs (stmt); + + if (TREE_CODE (lhs) == MEM_REF + && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME) + { + if (integer_zerop (TREE_OPERAND (lhs, 1))) + { + ssaname = TREE_OPERAND (lhs, 0); + idx = get_stridx (ssaname); + } + } + else + idx = get_addr_stridx (lhs); + + if (idx > 0) + { + si = get_strinfo (idx); + if (si != NULL && si->length != NULL_TREE && integer_zerop (si->length)) + { + if (initializer_zerop (gimple_assign_rhs1 (stmt))) + { + /* When storing '\0', the store can be removed + if we know it has been stored in the current function. */ + if (!stmt_could_throw_p (stmt) && si->writable) + { + unlink_stmt_vdef (stmt); + release_defs (stmt); + gsi_remove (gsi, true); + return false; + } + else + { + si->writable = true; + si->dont_invalidate = true; + } + } + else + /* Otherwise this statement overwrites the '\0' with + something, if the previous stmt was a memcpy, + its length may be decreased. */ + adjust_last_stmt (si, stmt, false); + } + else if (si != NULL) + { + si = unshare_strinfo (si); + si->length = build_int_cst (size_type_node, 0); + si->endptr = NULL; + si->prev = 0; + si->next = 0; + si->stmt = NULL; + si->first = 0; + si->writable = true; + if (ssaname && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname)) + si->endptr = ssaname; + si->dont_invalidate = true; + } + } + else if (idx == 0 && initializer_zerop (gimple_assign_rhs1 (stmt))) + { + if (ssaname) + { + si = zero_length_string (ssaname, NULL); + if (si != NULL) + si->dont_invalidate = true; + } + else + { + int idx = new_addr_stridx (lhs); + if (idx != 0) + { + si = new_strinfo (build_fold_addr_expr (lhs), idx, + build_int_cst (size_type_node, 0)); + set_strinfo (idx, si); + si->dont_invalidate = true; + } + } + if (si != NULL) + si->writable = true; + } + + if (si != NULL && initializer_zerop (gimple_assign_rhs1 (stmt))) + { + /* Allow adjust_last_stmt to remove it if the stored '\0' + is immediately overwritten. */ + laststmt.stmt = stmt; + laststmt.len = build_int_cst (size_type_node, 1); + laststmt.stridx = si->idx; + } + return true; +} + +/* Attempt to optimize a single statement at *GSI using string length + knowledge. */ + +static bool +strlen_optimize_stmt (gimple_stmt_iterator *gsi) +{ + gimple stmt = gsi_stmt (*gsi); + + if (is_gimple_call (stmt)) + { + tree callee = gimple_call_fndecl (stmt); + if (callee && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL) + switch (DECL_FUNCTION_CODE (callee)) + { + case BUILT_IN_STRLEN: + handle_builtin_strlen (gsi); + break; + case BUILT_IN_STRCHR: + handle_builtin_strchr (gsi); + break; + case BUILT_IN_STRCPY: + case BUILT_IN_STRCPY_CHK: + case BUILT_IN_STPCPY: + case BUILT_IN_STPCPY_CHK: + handle_builtin_strcpy (DECL_FUNCTION_CODE (callee), gsi); + break; + case BUILT_IN_MEMCPY: + case BUILT_IN_MEMCPY_CHK: + case BUILT_IN_MEMPCPY: + case BUILT_IN_MEMPCPY_CHK: + handle_builtin_memcpy (DECL_FUNCTION_CODE (callee), gsi); + break; + case BUILT_IN_STRCAT: + case BUILT_IN_STRCAT_CHK: + handle_builtin_strcat (DECL_FUNCTION_CODE (callee), gsi); + break; + default: + break; + } + } + else if (is_gimple_assign (stmt)) + { + tree lhs = gimple_assign_lhs (stmt); + + if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (lhs))) + { + if (gimple_assign_single_p (stmt) + || (gimple_assign_cast_p (stmt) + && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt))))) + { + int idx = get_stridx (gimple_assign_rhs1 (stmt)); + VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs), + idx); + } + else if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR) + handle_pointer_plus (gsi); + } + else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs)) + { + tree type = TREE_TYPE (lhs); + if (TREE_CODE (type) == ARRAY_TYPE) + type = TREE_TYPE (type); + if (TREE_CODE (type) == INTEGER_TYPE + && TYPE_MODE (type) == TYPE_MODE (char_type_node) + && TYPE_PRECISION (type) == TYPE_PRECISION (char_type_node)) + { + if (! handle_char_store (gsi)) + return false; + } + } + } + + if (gimple_vdef (stmt)) + maybe_invalidate (stmt); + return true; +} + +/* Recursively call maybe_invalidate on stmts that might be executed + in between dombb and current bb and that contain a vdef. Stop when + *count stmts are inspected, or if the whole strinfo vector has + been invalidated. */ + +static void +do_invalidate (basic_block dombb, gimple phi, bitmap visited, int *count) +{ + unsigned int i, n = gimple_phi_num_args (phi); + + for (i = 0; i < n; i++) + { + tree vuse = gimple_phi_arg_def (phi, i); + gimple stmt = SSA_NAME_DEF_STMT (vuse); + basic_block bb = gimple_bb (stmt); + if (bb == NULL + || bb == dombb + || !bitmap_set_bit (visited, bb->index) + || !dominated_by_p (CDI_DOMINATORS, bb, dombb)) + continue; + while (1) + { + if (gimple_code (stmt) == GIMPLE_PHI) + { + do_invalidate (dombb, stmt, visited, count); + if (*count == 0) + return; + break; + } + if (--*count == 0) + return; + if (!maybe_invalidate (stmt)) + { + *count = 0; + return; + } + vuse = gimple_vuse (stmt); + stmt = SSA_NAME_DEF_STMT (vuse); + if (gimple_bb (stmt) != bb) + { + bb = gimple_bb (stmt); + if (bb == NULL + || bb == dombb + || !bitmap_set_bit (visited, bb->index) + || !dominated_by_p (CDI_DOMINATORS, bb, dombb)) + break; + } + } + } +} + +/* Callback for walk_dominator_tree. Attempt to optimize various + string ops by remembering string lenths pointed by pointer SSA_NAMEs. */ + +static void +strlen_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, + basic_block bb) +{ + gimple_stmt_iterator gsi; + basic_block dombb = get_immediate_dominator (CDI_DOMINATORS, bb); + + if (dombb == NULL) + stridx_to_strinfo = NULL; + else + { + stridx_to_strinfo = (VEC(strinfo, heap) *) dombb->aux; + if (stridx_to_strinfo) + { + for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple phi = gsi_stmt (gsi); + if (!is_gimple_reg (gimple_phi_result (phi))) + { + bitmap visited = BITMAP_ALLOC (NULL); + int count_vdef = 100; + do_invalidate (dombb, phi, visited, &count_vdef); + BITMAP_FREE (visited); + break; + } + } + } + } + + /* If all PHI arguments have the same string index, the PHI result + has it as well. */ + for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple phi = gsi_stmt (gsi); + tree result = gimple_phi_result (phi); + if (is_gimple_reg (result) && POINTER_TYPE_P (TREE_TYPE (result))) + { + int idx = get_stridx (gimple_phi_arg_def (phi, 0)); + if (idx != 0) + { + unsigned int i, n = gimple_phi_num_args (phi); + for (i = 1; i < n; i++) + if (idx != get_stridx (gimple_phi_arg_def (phi, i))) + break; + if (i == n) + VEC_replace (int, ssa_ver_to_stridx, + SSA_NAME_VERSION (result), idx); + } + } + } + + /* Attempt to optimize individual statements. */ + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); ) + if (strlen_optimize_stmt (&gsi)) + gsi_next (&gsi); + + bb->aux = stridx_to_strinfo; + if (VEC_length (strinfo, stridx_to_strinfo) && !strinfo_shared ()) + VEC_replace (strinfo, stridx_to_strinfo, 0, (strinfo) bb); +} + +/* Callback for walk_dominator_tree. Free strinfo vector if it is + owned by the current bb, clear bb->aux. */ + +static void +strlen_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, + basic_block bb) +{ + if (bb->aux) + { + stridx_to_strinfo = (VEC(strinfo, heap) *) bb->aux; + if (VEC_length (strinfo, stridx_to_strinfo) + && VEC_index (strinfo, stridx_to_strinfo, 0) == (strinfo) bb) + { + unsigned int i; + strinfo si; + + for (i = 1; VEC_iterate (strinfo, stridx_to_strinfo, i, si); ++i) + free_strinfo (si); + VEC_free (strinfo, heap, stridx_to_strinfo); + } + bb->aux = NULL; + } +} + +/* Main entry point. */ + +static unsigned int +tree_ssa_strlen (void) +{ + struct dom_walk_data walk_data; + + VEC_safe_grow_cleared (int, heap, ssa_ver_to_stridx, num_ssa_names); + max_stridx = 1; + strinfo_pool = create_alloc_pool ("strinfo_struct pool", + sizeof (struct strinfo_struct), 64); + + calculate_dominance_info (CDI_DOMINATORS); + + /* String length optimization is implemented as a walk of the dominator + tree and a forward walk of statements within each block. */ + walk_data.dom_direction = CDI_DOMINATORS; + walk_data.initialize_block_local_data = NULL; + walk_data.before_dom_children = strlen_enter_block; + walk_data.after_dom_children = strlen_leave_block; + walk_data.block_local_data_size = 0; + walk_data.global_data = NULL; + + /* Initialize the dominator walker. */ + init_walk_dominator_tree (&walk_data); + + /* Recursively walk the dominator tree. */ + walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR); + + /* Finalize the dominator walker. */ + fini_walk_dominator_tree (&walk_data); + + VEC_free (int, heap, ssa_ver_to_stridx); + free_alloc_pool (strinfo_pool); + if (decl_to_stridxlist_htab) + { + obstack_free (&stridx_obstack, NULL); + htab_delete (decl_to_stridxlist_htab); + decl_to_stridxlist_htab = NULL; + } + laststmt.stmt = NULL; + laststmt.len = NULL_TREE; + laststmt.stridx = 0; + + return 0; +} + +static bool +gate_strlen (void) +{ + return flag_optimize_strlen != 0; +} + +struct gimple_opt_pass pass_strlen = +{ + { + GIMPLE_PASS, + "strlen", /* name */ + gate_strlen, /* gate */ + tree_ssa_strlen, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_TREE_STRLEN, /* tv_id */ + PROP_cfg | PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_ggc_collect + | TODO_verify_ssa /* todo_flags_finish */ + } +}; |