Message ID | 20110915170922.GR2687@tyan-ft48-01.lab.bos.redhat.com |
---|---|
State | New |
Headers | show |
On Thu, Sep 15, 2011 at 7:09 PM, Jakub Jelinek <jakub@redhat.com> wrote: > Hi! > > Here is an updated tree-ssa-strlen.c optimization pass, which includes > all the optimizations I've initially wanted and adds a lot of testcases > for it (I've been using -ftest-coverage to verify the pass is thoroughly > tested). > > Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? Ok if there are no objections form the C/C++ maintainers in 24h. Btw, can you add a changes.html entry for this? Thanks, Richard. > There is still room for further improvements, e.g. currently if a strcpy > call is transformed into stpcpy to determine destination length (if that is > needed), we could use the same to determine source length as well - but we'd > need to add another field in addition to ptr, so that get_string_length > knows what to subtract. Example strcpy (p, q); return strlen (q); > (currently we optimize strcpy (p, q); return strlen (q); into > tmp = stpcpy (p, q); return tmp - p; if runtime has stpcpy). > Another possible optimization could be to merge adjacent memcpy calls > from string literals into one, provided the string literals aren't very > large. Say strcat (p, "abcd"); strcat (p, "efgh"); strcat (p, "ijkl"); > could be tmp = p + strlen (p); memcpy (tmp, "abcdefghijkl", 13); instead of > 3 separate memcpy calls. > > 2011-09-15 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]. > cp/ > * decl.c (duplicate_decls): If compatible stpcpy prototype > is seen, set implicit_built_in_decls[BUILT_IN_STPCPY]. > testsuite/ > * 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-19.c: New test. > * gcc.dg/strlenopt-20.c: New test. > * gcc.dg/strlenopt.h: New file. > > --- gcc/common.opt.jj 2011-09-15 12:18:37.000000000 +0200 > +++ gcc/common.opt 2011-09-15 12:24:09.000000000 +0200 > @@ -1953,6 +1953,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 > --- gcc/Makefile.in.jj 2011-09-15 12:18:37.000000000 +0200 > +++ gcc/Makefile.in 2011-09-15 12:24:09.000000000 +0200 > @@ -1472,6 +1472,7 @@ OBJS = \ > tree-ssa-reassoc.o \ > tree-ssa-sccvn.o \ > tree-ssa-sink.o \ > + tree-ssa-strlen.o \ > tree-ssa-structalias.o \ > tree-ssa-ter.o \ > tree-ssa-threadedge.o \ > @@ -3157,6 +3158,9 @@ tree-ssa-ccp.o : tree-ssa-ccp.c $(TREE_F > $(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) \ > --- gcc/opts.c.jj 2011-09-15 12:18:37.000000000 +0200 > +++ gcc/opts.c 2011-09-15 12:24:09.000000000 +0200 > @@ -484,6 +484,7 @@ static const struct default_options defa > { OPT_LEVELS_2_PLUS, OPT_falign_jumps, NULL, 1 }, > { OPT_LEVELS_2_PLUS, OPT_falign_labels, NULL, 1 }, > { OPT_LEVELS_2_PLUS, OPT_falign_functions, NULL, 1 }, > + { OPT_LEVELS_2_PLUS_SPEED_ONLY, OPT_foptimize_strlen, NULL, 1 }, > > /* -O3 optimizations. */ > { OPT_LEVELS_3_PLUS, OPT_ftree_loop_distribute_patterns, NULL, 1 }, > --- gcc/params.def.jj 2011-09-15 12:18:37.000000000 +0200 > +++ gcc/params.def 2011-09-15 12:24:09.000000000 +0200 > @@ -921,6 +921,14 @@ DEFPARAM (PARAM_TREE_REASSOC_WIDTH, > "reassociated tree. If 0, use the target dependent heuristic.", > 0, 0, 0) > > +/* Maximum number of strings for which strlen optimization pass will > + track string lenths. */ > +DEFPARAM (PARAM_MAX_TRACKED_STRLENS, > + "max-tracked-strlens", > + "Maximum number of strings for which strlen optimization pass will " > + "track string lengths", > + 1000, 0, 0) > + > > /* > Local variables: > --- gcc/passes.c.jj 2011-09-15 12:18:37.000000000 +0200 > +++ gcc/passes.c 2011-09-15 12:24:09.000000000 +0200 > @@ -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); > --- gcc/timevar.def.jj 2011-09-15 12:18:37.000000000 +0200 > +++ gcc/timevar.def 2011-09-15 12:24:09.000000000 +0200 > @@ -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> > > @@ -183,6 +183,7 @@ DEFTIMEVAR (TV_TREE_COPY_RENAME , " > 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") > --- gcc/tree-pass.h.jj 2011-09-15 12:18:37.000000000 +0200 > +++ gcc/tree-pass.h 2011-09-15 12:24:09.000000000 +0200 > @@ -412,6 +412,7 @@ extern struct gimple_opt_pass pass_diagn > 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; > --- gcc/tree-ssa-strlen.c.jj 2011-09-15 12:24:09.000000000 +0200 > +++ gcc/tree-ssa-strlen.c 2011-09-15 14:39:14.000000000 +0200 > @@ -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 */ > + } > +}; > --- gcc/c-decl.c.jj 2011-09-15 12:18:54.000000000 +0200 > +++ gcc/c-decl.c 2011-09-15 12:24:09.000000000 +0200 > @@ -2369,7 +2369,21 @@ merge_decls (tree newdecl, tree olddecl, > 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); > --- gcc/cp/decl.c.jj 2011-09-15 12:18:45.000000000 +0200 > +++ gcc/cp/decl.c 2011-09-15 12:24:09.000000000 +0200 > @@ -2135,6 +2135,18 @@ duplicate_decls (tree newdecl, tree oldd > /* 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); > --- gcc/testsuite/gcc.dg/strlenopt-1.c.jj 2011-09-15 12:24:09.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-1.c 2011-09-15 12:24:09.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt-1f.c.jj 2011-09-15 12:24:09.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-1f.c 2011-09-15 12:24:09.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt-2.c.jj 2011-09-15 12:24:09.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-2.c 2011-09-15 12:24:09.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt-2f.c.jj 2011-09-15 12:24:09.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-2f.c 2011-09-15 12:24:09.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt-3.c.jj 2011-09-15 12:24:09.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-3.c 2011-09-15 12:24:09.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt-4.c.jj 2011-09-15 12:24:09.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-4.c 2011-09-15 12:24:09.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt-4g.c.jj 2011-09-15 12:24:09.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-4g.c 2011-09-15 12:24:09.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt-4gf.c.jj 2011-09-15 12:24:09.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-4gf.c 2011-09-15 12:24:09.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt-5.c.jj 2011-09-15 12:24:09.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-5.c 2011-09-15 12:24:09.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt-6.c.jj 2011-09-15 12:24:09.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-6.c 2011-09-15 12:24:09.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt-7.c.jj 2011-09-15 12:24:10.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-7.c 2011-09-15 12:24:10.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt-8.c.jj 2011-09-15 12:24:10.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-8.c 2011-09-15 12:24:10.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt-9.c.jj 2011-09-15 12:24:10.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-9.c 2011-09-15 12:24:10.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt-10.c.jj 2011-09-15 12:24:10.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-10.c 2011-09-15 12:24:10.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt-11.c.jj 2011-09-15 12:24:10.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-11.c 2011-09-15 12:24:10.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt-12.c.jj 2011-09-15 12:24:10.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-12.c 2011-09-15 12:24:10.000000000 +0200 > @@ -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; > +} > --- gcc/testsuite/gcc.dg/strlenopt-12g.c.jj 2011-09-15 12:24:10.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-12g.c 2011-09-15 12:24:10.000000000 +0200 > @@ -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" > --- gcc/testsuite/gcc.dg/strlenopt-13.c.jj 2011-09-15 12:24:10.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-13.c 2011-09-15 12:24:10.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt-14g.c.jj 2011-09-15 12:24:10.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-14g.c 2011-09-15 12:24:10.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt-14gf.c.jj 2011-09-15 12:24:10.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-14gf.c 2011-09-15 12:24:10.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt-15.c.jj 2011-09-15 12:24:10.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-15.c 2011-09-15 12:24:10.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt-16g.c.jj 2011-09-15 12:24:10.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-16g.c 2011-09-15 12:24:10.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt-17g.c.jj 2011-09-15 12:24:10.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-17g.c 2011-09-15 12:24:10.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt-18g.c.jj 2011-09-15 12:24:10.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-18g.c 2011-09-15 12:24:10.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt-19.c.jj 2011-09-15 14:08:48.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-19.c 2011-09-15 14:05:11.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt-20.c.jj 2011-09-15 14:47:56.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt-20.c 2011-09-15 14:47:34.000000000 +0200 > @@ -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" } } */ > --- gcc/testsuite/gcc.dg/strlenopt.h.jj 2011-09-15 12:24:10.000000000 +0200 > +++ gcc/testsuite/gcc.dg/strlenopt.h 2011-09-15 12:24:10.000000000 +0200 > @@ -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 > > Jakub >
--- gcc/common.opt.jj 2011-09-15 12:18:37.000000000 +0200 +++ gcc/common.opt 2011-09-15 12:24:09.000000000 +0200 @@ -1953,6 +1953,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 --- gcc/Makefile.in.jj 2011-09-15 12:18:37.000000000 +0200 +++ gcc/Makefile.in 2011-09-15 12:24:09.000000000 +0200 @@ -1472,6 +1472,7 @@ OBJS = \ tree-ssa-reassoc.o \ tree-ssa-sccvn.o \ tree-ssa-sink.o \ + tree-ssa-strlen.o \ tree-ssa-structalias.o \ tree-ssa-ter.o \ tree-ssa-threadedge.o \ @@ -3157,6 +3158,9 @@ tree-ssa-ccp.o : tree-ssa-ccp.c $(TREE_F $(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) \ --- gcc/opts.c.jj 2011-09-15 12:18:37.000000000 +0200 +++ gcc/opts.c 2011-09-15 12:24:09.000000000 +0200 @@ -484,6 +484,7 @@ static const struct default_options defa { OPT_LEVELS_2_PLUS, OPT_falign_jumps, NULL, 1 }, { OPT_LEVELS_2_PLUS, OPT_falign_labels, NULL, 1 }, { OPT_LEVELS_2_PLUS, OPT_falign_functions, NULL, 1 }, + { OPT_LEVELS_2_PLUS_SPEED_ONLY, OPT_foptimize_strlen, NULL, 1 }, /* -O3 optimizations. */ { OPT_LEVELS_3_PLUS, OPT_ftree_loop_distribute_patterns, NULL, 1 }, --- gcc/params.def.jj 2011-09-15 12:18:37.000000000 +0200 +++ gcc/params.def 2011-09-15 12:24:09.000000000 +0200 @@ -921,6 +921,14 @@ DEFPARAM (PARAM_TREE_REASSOC_WIDTH, "reassociated tree. If 0, use the target dependent heuristic.", 0, 0, 0) +/* Maximum number of strings for which strlen optimization pass will + track string lenths. */ +DEFPARAM (PARAM_MAX_TRACKED_STRLENS, + "max-tracked-strlens", + "Maximum number of strings for which strlen optimization pass will " + "track string lengths", + 1000, 0, 0) + /* Local variables: --- gcc/passes.c.jj 2011-09-15 12:18:37.000000000 +0200 +++ gcc/passes.c 2011-09-15 12:24:09.000000000 +0200 @@ -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); --- gcc/timevar.def.jj 2011-09-15 12:18:37.000000000 +0200 +++ gcc/timevar.def 2011-09-15 12:24:09.000000000 +0200 @@ -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> @@ -183,6 +183,7 @@ DEFTIMEVAR (TV_TREE_COPY_RENAME , " 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") --- gcc/tree-pass.h.jj 2011-09-15 12:18:37.000000000 +0200 +++ gcc/tree-pass.h 2011-09-15 12:24:09.000000000 +0200 @@ -412,6 +412,7 @@ extern struct gimple_opt_pass pass_diagn 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; --- gcc/tree-ssa-strlen.c.jj 2011-09-15 12:24:09.000000000 +0200 +++ gcc/tree-ssa-strlen.c 2011-09-15 14:39:14.000000000 +0200 @@ -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 */ + } +}; --- gcc/c-decl.c.jj 2011-09-15 12:18:54.000000000 +0200 +++ gcc/c-decl.c 2011-09-15 12:24:09.000000000 +0200 @@ -2369,7 +2369,21 @@ merge_decls (tree newdecl, tree olddecl, 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); --- gcc/cp/decl.c.jj 2011-09-15 12:18:45.000000000 +0200 +++ gcc/cp/decl.c 2011-09-15 12:24:09.000000000 +0200 @@ -2135,6 +2135,18 @@ duplicate_decls (tree newdecl, tree oldd /* 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); --- gcc/testsuite/gcc.dg/strlenopt-1.c.jj 2011-09-15 12:24:09.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-1.c 2011-09-15 12:24:09.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt-1f.c.jj 2011-09-15 12:24:09.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-1f.c 2011-09-15 12:24:09.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt-2.c.jj 2011-09-15 12:24:09.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-2.c 2011-09-15 12:24:09.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt-2f.c.jj 2011-09-15 12:24:09.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-2f.c 2011-09-15 12:24:09.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt-3.c.jj 2011-09-15 12:24:09.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-3.c 2011-09-15 12:24:09.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt-4.c.jj 2011-09-15 12:24:09.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-4.c 2011-09-15 12:24:09.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt-4g.c.jj 2011-09-15 12:24:09.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-4g.c 2011-09-15 12:24:09.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt-4gf.c.jj 2011-09-15 12:24:09.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-4gf.c 2011-09-15 12:24:09.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt-5.c.jj 2011-09-15 12:24:09.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-5.c 2011-09-15 12:24:09.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt-6.c.jj 2011-09-15 12:24:09.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-6.c 2011-09-15 12:24:09.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt-7.c.jj 2011-09-15 12:24:10.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-7.c 2011-09-15 12:24:10.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt-8.c.jj 2011-09-15 12:24:10.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-8.c 2011-09-15 12:24:10.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt-9.c.jj 2011-09-15 12:24:10.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-9.c 2011-09-15 12:24:10.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt-10.c.jj 2011-09-15 12:24:10.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-10.c 2011-09-15 12:24:10.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt-11.c.jj 2011-09-15 12:24:10.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-11.c 2011-09-15 12:24:10.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt-12.c.jj 2011-09-15 12:24:10.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-12.c 2011-09-15 12:24:10.000000000 +0200 @@ -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; +} --- gcc/testsuite/gcc.dg/strlenopt-12g.c.jj 2011-09-15 12:24:10.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-12g.c 2011-09-15 12:24:10.000000000 +0200 @@ -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" --- gcc/testsuite/gcc.dg/strlenopt-13.c.jj 2011-09-15 12:24:10.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-13.c 2011-09-15 12:24:10.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt-14g.c.jj 2011-09-15 12:24:10.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-14g.c 2011-09-15 12:24:10.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt-14gf.c.jj 2011-09-15 12:24:10.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-14gf.c 2011-09-15 12:24:10.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt-15.c.jj 2011-09-15 12:24:10.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-15.c 2011-09-15 12:24:10.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt-16g.c.jj 2011-09-15 12:24:10.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-16g.c 2011-09-15 12:24:10.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt-17g.c.jj 2011-09-15 12:24:10.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-17g.c 2011-09-15 12:24:10.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt-18g.c.jj 2011-09-15 12:24:10.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-18g.c 2011-09-15 12:24:10.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt-19.c.jj 2011-09-15 14:08:48.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-19.c 2011-09-15 14:05:11.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt-20.c.jj 2011-09-15 14:47:56.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt-20.c 2011-09-15 14:47:34.000000000 +0200 @@ -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" } } */ --- gcc/testsuite/gcc.dg/strlenopt.h.jj 2011-09-15 12:24:10.000000000 +0200 +++ gcc/testsuite/gcc.dg/strlenopt.h 2011-09-15 12:24:10.000000000 +0200 @@ -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