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


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

[2/2] tree-ssa-strlen optimization pass


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?

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


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