* 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.h: New file.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@179277 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 1997 insertions, 0 deletions

diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c
new file mode 100644
index 00000000000..71cefaaabc8
--- /dev/null
+++ b/gcc/tree-ssa-strlen.c
@@ -0,0 +1,1997 @@
+/* String length optimization
+   Copyright (C) 2011 Free Software Foundation, Inc.
+   Contributed by Jakub Jelinek <jakub@redhat.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tree-flow.h"
+#include "tree-pass.h"
+#include "domwalk.h"
+#include "alloc-pool.h"
+#include "tree-ssa-propagate.h"
+#include "gimple-pretty-print.h"
+#include "params.h"
+
+/* A vector indexed by SSA_NAME_VERSION.  0 means unknown, positive value
+   is an index into strinfo vector, negative value stands for
+   string length of a string literal (~strlen).  */
+static VEC (int, heap) *ssa_ver_to_stridx;
+
+/* Number of currently active string indexes plus one.  */
+static int max_stridx;
+
+/* String information record.  */
+typedef struct strinfo_struct
+{
+  /* String length of this string.  */
+  tree length;
+  /* Any of the corresponding pointers for querying alias oracle.  */
+  tree ptr;
+  /* Statement for delayed length computation.  */
+  gimple stmt;
+  /* Pointer to '\0' if known, if NULL, it can be computed as
+     ptr + length.  */
+  tree endptr;
+  /* Reference count.  Any changes to strinfo entry possibly shared
+     with dominating basic blocks need unshare_strinfo first, except
+     for dont_invalidate which affects only the immediately next
+     maybe_invalidate.  */
+  int refcount;
+  /* Copy of index.  get_strinfo (si->idx) should return si;  */
+  int idx;
+  /* These 3 fields are for chaining related string pointers together.
+     E.g. for
+     bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
+     strcpy (c, d); e = c + dl;
+     strinfo(a) -> strinfo(c) -> strinfo(e)
+     All have ->first field equal to strinfo(a)->idx and are doubly
+     chained through prev/next fields.  The later strinfos are required
+     to point into the same string with zero or more bytes after
+     the previous pointer and all bytes in between the two pointers
+     must be non-zero.  Functions like strcpy or memcpy are supposed
+     to adjust all previous strinfo lengths, but not following strinfo
+     lengths (those are uncertain, usually invalidated during
+     maybe_invalidate, except when the alias oracle knows better).
+     Functions like strcat on the other side adjust the whole
+     related strinfo chain.
+     They are updated lazily, so to use the chain the same first fields
+     and si->prev->next == si->idx needs to be verified.  */
+  int first;
+  int next;
+  int prev;
+  /* A flag whether the string is known to be written in the current
+     function.  */
+  bool writable;
+  /* A flag for the next maybe_invalidate that this strinfo shouldn't
+     be invalidated.  Always cleared by maybe_invalidate.  */
+  bool dont_invalidate;
+} *strinfo;
+DEF_VEC_P(strinfo);
+DEF_VEC_ALLOC_P(strinfo,heap);
+
+/* Pool for allocating strinfo_struct entries.  */
+static alloc_pool strinfo_pool;
+
+/* Vector mapping positive string indexes to strinfo, for the
+   current basic block.  The first pointer in the vector is special,
+   it is either NULL, meaning the vector isn't shared, or it is
+   a basic block pointer to the owner basic_block if shared.
+   If some other bb wants to modify the vector, the vector needs
+   to be unshared first, and only the owner bb is supposed to free it.  */
+static VEC(strinfo, heap) *stridx_to_strinfo;
+
+/* One OFFSET->IDX mapping.  */
+struct stridxlist
+{
+  struct stridxlist *next;
+  HOST_WIDE_INT offset;
+  int idx;
+};
+
+/* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings.  */
+struct decl_stridxlist_map
+{
+  struct tree_map_base base;
+  struct stridxlist list;
+};
+
+/* Hash table for mapping decls to a chained list of offset -> idx
+   mappings.  */
+static htab_t decl_to_stridxlist_htab;
+
+/* Obstack for struct stridxlist and struct decl_stridxlist_map.  */
+static struct obstack stridx_obstack;
+
+/* Last memcpy statement if it could be adjusted if the trailing
+   '\0' written is immediately overwritten, or
+   *x = '\0' store that could be removed if it is immediately overwritten.  */
+struct laststmt_struct
+{
+  gimple stmt;
+  tree len;
+  int stridx;
+} laststmt;
+
+/* Hash a from tree in a decl_stridxlist_map.  */
+
+static unsigned int
+decl_to_stridxlist_hash (const void *item)
+{
+  return DECL_UID (((const struct decl_stridxlist_map *) item)->base.from);
+}
+
+/* Helper function for get_stridx.  */
+
+static int
+get_addr_stridx (tree exp)
+{
+  HOST_WIDE_INT off;
+  struct decl_stridxlist_map ent, *e;
+  struct stridxlist *list;
+  tree base;
+
+  if (decl_to_stridxlist_htab == NULL)
+    return 0;
+
+  base = get_addr_base_and_unit_offset (exp, &off);
+  if (base == NULL || !DECL_P (base))
+    return 0;
+
+  ent.base.from = base;
+  e = (struct decl_stridxlist_map *)
+      htab_find_with_hash (decl_to_stridxlist_htab, &ent, DECL_UID (base));
+  if (e == NULL)
+    return 0;
+
+  list = &e->list;
+  do
+    {
+      if (list->offset == off)
+	return list->idx;
+      list = list->next;
+    }
+  while (list);
+  return 0;
+}
+
+/* Return string index for EXP.  */
+
+static int
+get_stridx (tree exp)
+{
+  tree l;
+
+  if (TREE_CODE (exp) == SSA_NAME)
+    return VEC_index (int, ssa_ver_to_stridx, SSA_NAME_VERSION (exp));
+
+  if (TREE_CODE (exp) == ADDR_EXPR)
+    {
+      int idx = get_addr_stridx (TREE_OPERAND (exp, 0));
+      if (idx != 0)
+	return idx;
+    }
+
+  l = c_strlen (exp, 0);
+  if (l != NULL_TREE
+      && host_integerp (l, 1))
+    {
+      unsigned HOST_WIDE_INT len = tree_low_cst (l, 1);
+      if (len == (unsigned int) len
+	  && (int) len >= 0)
+	return ~(int) len;
+    }
+  return 0;
+}
+
+/* Return true if strinfo vector is shared with the immediate dominator.  */
+
+static inline bool
+strinfo_shared (void)
+{
+  return VEC_length (strinfo, stridx_to_strinfo)
+	 && VEC_index (strinfo, stridx_to_strinfo, 0) != NULL;
+}
+
+/* Unshare strinfo vector that is shared with the immediate dominator.  */
+
+static void
+unshare_strinfo_vec (void)
+{
+  strinfo si;
+  unsigned int i = 0;
+
+  gcc_assert (strinfo_shared ());
+  stridx_to_strinfo = VEC_copy (strinfo, heap, stridx_to_strinfo);
+  for (i = 1; VEC_iterate (strinfo, stridx_to_strinfo, i, si); ++i)
+    if (si != NULL)
+      si->refcount++;
+  VEC_replace (strinfo, stridx_to_strinfo, 0, NULL);
+}
+
+/* Attempt to create a string index for exp, ADDR_EXPR's operand.
+   Return a pointer to the location where the string index can
+   be stored (if 0) or is stored, or NULL if this can't be tracked.  */
+
+static int *
+addr_stridxptr (tree exp)
+{
+  void **slot;
+  struct decl_stridxlist_map ent;
+  struct stridxlist *list;
+  HOST_WIDE_INT off;
+
+  tree base = get_addr_base_and_unit_offset (exp, &off);
+  if (base == NULL_TREE || !DECL_P (base))
+    return NULL;
+
+  if (decl_to_stridxlist_htab == NULL)
+    {
+      decl_to_stridxlist_htab
+	= htab_create (64, decl_to_stridxlist_hash, tree_map_base_eq, NULL);
+      gcc_obstack_init (&stridx_obstack);
+    }
+  ent.base.from = base;
+  slot = htab_find_slot_with_hash (decl_to_stridxlist_htab, &ent,
+				   DECL_UID (base), INSERT);
+  if (*slot)
+    {
+      int i;
+      list = &((struct decl_stridxlist_map *)*slot)->list;
+      for (i = 0; i < 16; i++)
+	{
+	  if (list->offset == off)
+	    return &list->idx;
+	  if (list->next == NULL)
+	    break;
+	}
+      if (i == 16)
+	return NULL;
+      list->next = XOBNEW (&stridx_obstack, struct stridxlist);
+      list = list->next;
+    }
+  else
+    {
+      struct decl_stridxlist_map *e
+	= XOBNEW (&stridx_obstack, struct decl_stridxlist_map);
+      e->base.from = base;
+      *slot = (void *) e;
+      list = &e->list;
+    }
+  list->next = NULL;
+  list->offset = off;
+  list->idx = 0;
+  return &list->idx;
+}
+
+/* Create a new string index, or return 0 if reached limit.  */
+
+static int
+new_stridx (tree exp)
+{
+  int idx;
+  if (max_stridx >= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS))
+    return 0;
+  if (TREE_CODE (exp) == SSA_NAME)
+    {
+      if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp))
+	return 0;
+      idx = max_stridx++;
+      VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (exp), idx);
+      return idx;
+    }
+  if (TREE_CODE (exp) == ADDR_EXPR)
+    {
+      int *pidx = addr_stridxptr (TREE_OPERAND (exp, 0));
+      if (pidx != NULL)
+	{
+	  gcc_assert (*pidx == 0);
+	  *pidx = max_stridx++;
+	  return *pidx;
+	}
+    }
+  return 0;
+}
+
+/* Like new_stridx, but for ADDR_EXPR's operand instead.  */
+
+static int
+new_addr_stridx (tree exp)
+{
+  int *pidx;
+  if (max_stridx >= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS))
+    return 0;
+  pidx = addr_stridxptr (exp);
+  if (pidx != NULL)
+    {
+      gcc_assert (*pidx == 0);
+      *pidx = max_stridx++;
+      return *pidx;
+    }
+  return 0;
+}
+
+/* Create a new strinfo.  */
+
+static strinfo
+new_strinfo (tree ptr, int idx, tree length)
+{
+  strinfo si = (strinfo) pool_alloc (strinfo_pool);
+  si->length = length;
+  si->ptr = ptr;
+  si->stmt = NULL;
+  si->endptr = NULL_TREE;
+  si->refcount = 1;
+  si->idx = idx;
+  si->first = 0;
+  si->prev = 0;
+  si->next = 0;
+  si->writable = false;
+  si->dont_invalidate = false;
+  return si;
+}
+
+/* Decrease strinfo refcount and free it if not referenced anymore.  */
+
+static inline void
+free_strinfo (strinfo si)
+{
+  if (si && --si->refcount == 0)
+    pool_free (strinfo_pool, si);
+}
+
+/* Return strinfo vector entry IDX.  */
+
+static inline strinfo
+get_strinfo (int idx)
+{
+  if (VEC_length (strinfo, stridx_to_strinfo) <= (unsigned int) idx)
+    return NULL;
+  return VEC_index (strinfo, stridx_to_strinfo, idx);
+}
+
+/* Set strinfo in the vector entry IDX to SI.  */
+
+static inline void
+set_strinfo (int idx, strinfo si)
+{
+  if (VEC_length (strinfo, stridx_to_strinfo) && VEC_index (strinfo, stridx_to_strinfo, 0))
+    unshare_strinfo_vec ();
+  if (VEC_length (strinfo, stridx_to_strinfo) <= (unsigned int) idx)
+    VEC_safe_grow_cleared (strinfo, heap, stridx_to_strinfo, idx + 1);
+  VEC_replace (strinfo, stridx_to_strinfo, idx, si);
+}
+
+/* Return string length, or NULL if it can't be computed.  */
+
+static tree
+get_string_length (strinfo si)
+{
+  if (si->length)
+    return si->length;
+
+  if (si->stmt)
+    {
+      gimple stmt = si->stmt, lenstmt;
+      tree callee, lhs, lhs_var, fn, tem;
+      location_t loc;
+      gimple_stmt_iterator gsi;
+
+      gcc_assert (is_gimple_call (stmt));
+      callee = gimple_call_fndecl (stmt);
+      gcc_assert (callee && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL);
+      lhs = gimple_call_lhs (stmt);
+      gcc_assert (implicit_built_in_decls[BUILT_IN_STRCPY] != NULL_TREE);
+      /* unshare_strinfo is intentionally not called here.  The (delayed)
+	 transformation of strcpy or strcat into stpcpy is done at the place
+	 of the former strcpy/strcat call and so can affect all the strinfos
+	 with the same stmt.  If they were unshared before and transformation
+	 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
+	 just compute the right length.  */
+      switch (DECL_FUNCTION_CODE (callee))
+	{
+	case BUILT_IN_STRCAT:
+	case BUILT_IN_STRCAT_CHK:
+	  gsi = gsi_for_stmt (stmt);
+	  fn = implicit_built_in_decls[BUILT_IN_STRLEN];
+	  gcc_assert (lhs == NULL_TREE);
+	  lhs_var = create_tmp_var (TREE_TYPE (TREE_TYPE (fn)), NULL);
+	  add_referenced_var (lhs_var);
+	  tem = unshare_expr (gimple_call_arg (stmt, 0));
+	  lenstmt = gimple_build_call (fn, 1, tem);
+	  lhs = make_ssa_name (lhs_var, lenstmt);
+	  gimple_call_set_lhs (lenstmt, lhs);
+	  gimple_set_vuse (lenstmt, gimple_vuse (stmt));
+	  gsi_insert_before (&gsi, lenstmt, GSI_SAME_STMT);
+	  lhs_var = create_tmp_var (TREE_TYPE (gimple_call_arg (stmt, 0)),
+				    NULL);
+	  add_referenced_var (lhs_var);
+	  tem = gimple_call_arg (stmt, 0);
+	  lenstmt
+	    = gimple_build_assign_with_ops (POINTER_PLUS_EXPR,
+					    make_ssa_name (lhs_var, NULL),
+					    tem, lhs);
+	  gsi_insert_before (&gsi, lenstmt, GSI_SAME_STMT);
+	  gimple_call_set_arg (stmt, 0, gimple_assign_lhs (lenstmt));
+	  lhs = NULL_TREE;
+	  /* FALLTHRU */
+	case BUILT_IN_STRCPY:
+	case BUILT_IN_STRCPY_CHK:
+	  if (gimple_call_num_args (stmt) == 2)
+	    fn = implicit_built_in_decls[BUILT_IN_STPCPY];
+	  else
+	    fn = built_in_decls[BUILT_IN_STPCPY_CHK];
+	  gcc_assert (lhs == NULL_TREE);
+	  if (dump_file && (dump_flags & TDF_DETAILS) != 0)
+	    {
+	      fprintf (dump_file, "Optimizing: ");
+	      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+	    }
+	  gimple_call_set_fndecl (stmt, fn);
+	  lhs_var = create_tmp_var (TREE_TYPE (TREE_TYPE (fn)), NULL);
+	  add_referenced_var (lhs_var);
+	  lhs = make_ssa_name (lhs_var, stmt);
+	  gimple_call_set_lhs (stmt, lhs);
+	  update_stmt (stmt);
+	  if (dump_file && (dump_flags & TDF_DETAILS) != 0)
+	    {
+	      fprintf (dump_file, "into: ");
+	      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+	    }
+	  /* FALLTHRU */
+	case BUILT_IN_STPCPY:
+	case BUILT_IN_STPCPY_CHK:
+	  gcc_assert (lhs != NULL_TREE);
+	  loc = gimple_location (stmt);
+	  si->endptr = lhs;
+	  si->stmt = NULL;
+	  lhs = fold_convert_loc (loc, size_type_node, lhs);
+	  si->length = fold_convert_loc (loc, size_type_node, si->ptr);
+	  si->length = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
+					lhs, si->length);
+	  break;
+	default:
+	  gcc_unreachable ();
+	  break;
+	}
+    }
+
+  return si->length;
+}
+
+/* Invalidate string length information for strings whose length
+   might change due to stores in stmt.  */
+
+static bool
+maybe_invalidate (gimple stmt)
+{
+  strinfo si;
+  unsigned int i;
+  bool nonempty = false;
+
+  for (i = 1; VEC_iterate (strinfo, stridx_to_strinfo, i, si); ++i)
+    if (si != NULL)
+      {
+	if (!si->dont_invalidate)
+	  {
+	    ao_ref r;
+	    ao_ref_init_from_ptr_and_size (&r, si->ptr, NULL_TREE);
+	    if (stmt_may_clobber_ref_p_1 (stmt, &r))
+	      {
+		set_strinfo (i, NULL);
+		free_strinfo (si);
+		continue;
+	      }
+	  }
+	si->dont_invalidate = false;
+	nonempty = true;
+      }
+  return nonempty;
+}
+
+/* Unshare strinfo record SI, if it has recount > 1 or
+   if stridx_to_strinfo vector is shared with some other
+   bbs.  */
+
+static strinfo
+unshare_strinfo (strinfo si)
+{
+  strinfo nsi;
+
+  if (si->refcount == 1 && !strinfo_shared ())
+    return si;
+
+  nsi = new_strinfo (si->ptr, si->idx, si->length);
+  nsi->stmt = si->stmt;
+  nsi->endptr = si->endptr;
+  nsi->first = si->first;
+  nsi->prev = si->prev;
+  nsi->next = si->next;
+  nsi->writable = si->writable;
+  set_strinfo (si->idx, nsi);
+  free_strinfo (si);
+  return nsi;
+}
+
+/* Return first strinfo in the related strinfo chain
+   if all strinfos in between belong to the chain, otherwise
+   NULL.  */
+
+static strinfo
+verify_related_strinfos (strinfo origsi)
+{
+  strinfo si = origsi, psi;
+
+  if (origsi->first == 0)
+    return NULL;
+  for (; si->prev; si = psi)
+    {
+      if (si->first != origsi->first)
+	return NULL;
+      psi = get_strinfo (si->prev);
+      if (psi == NULL)
+	return NULL;
+      if (psi->next != si->idx)
+	return NULL;
+    }
+  if (si->idx != si->first)
+    return NULL;
+  return si;
+}
+
+/* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
+   to a zero-length string and if possible chain it to a related strinfo
+   chain whose part is or might be CHAINSI.  */
+
+static strinfo
+zero_length_string (tree ptr, strinfo chainsi)
+{
+  strinfo si;
+  int idx;
+  gcc_checking_assert (TREE_CODE (ptr) == SSA_NAME
+		       && get_stridx (ptr) == 0);
+
+  if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr))
+    return NULL;
+  if (chainsi != NULL)
+    {
+      si = verify_related_strinfos (chainsi);
+      if (si)
+	{
+	  chainsi = si;
+	  for (; chainsi->next; chainsi = si)
+	    {
+	      if (chainsi->endptr == NULL_TREE)
+		{
+		  chainsi = unshare_strinfo (chainsi);
+		  chainsi->endptr = ptr;
+		}
+	      si = get_strinfo (chainsi->next);
+	      if (si == NULL
+		  || si->first != chainsi->first
+		  || si->prev != chainsi->idx)
+		break;
+	    }
+	  gcc_assert (chainsi->length);
+	  if (chainsi->endptr == NULL_TREE)
+	    {
+	      chainsi = unshare_strinfo (chainsi);
+	      chainsi->endptr = ptr;
+	    }
+	  if (integer_zerop (chainsi->length))
+	    {
+	      if (chainsi->next)
+		{
+		  chainsi = unshare_strinfo (chainsi);
+		  chainsi->next = 0;
+		}
+	      VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (ptr),
+			   chainsi->idx);
+	      return chainsi;
+	    }
+	}
+      else if (chainsi->first || chainsi->prev || chainsi->next)
+	{
+	  chainsi = unshare_strinfo (chainsi);
+	  chainsi->first = 0;
+	  chainsi->prev = 0;
+	  chainsi->next = 0;
+	}
+    }
+  idx = new_stridx (ptr);
+  if (idx == 0)
+    return NULL;
+  si = new_strinfo (ptr, idx, build_int_cst (size_type_node, 0));
+  set_strinfo (idx, si);
+  si->endptr = ptr;
+  if (chainsi != NULL)
+    {
+      chainsi = unshare_strinfo (chainsi);
+      if (chainsi->first == 0)
+	chainsi->first = chainsi->idx;
+      chainsi->next = idx;
+      si->prev = chainsi->idx;
+      si->first = chainsi->first;
+      si->writable = chainsi->writable;
+    }
+  return si;
+}
+
+/* For strinfo ORIGSI whose length has been just updated
+   update also related strinfo lengths (add ADJ to each,
+   but don't adjust ORIGSI).  */
+
+static void
+adjust_related_strinfos (location_t loc, strinfo origsi, tree adj)
+{
+  strinfo si = verify_related_strinfos (origsi);
+
+  if (si == NULL)
+    return;
+
+  while (1)
+    {
+      strinfo nsi;
+
+      if (si != origsi)
+	{
+	  tree tem;
+
+	  si = unshare_strinfo (si);
+	  gcc_assert (si->length);
+	  tem = fold_convert_loc (loc, TREE_TYPE (si->length), adj);
+	  si->length = fold_build2_loc (loc, PLUS_EXPR,
+					TREE_TYPE (si->length), si->length,
+					tem);
+	  si->endptr = NULL_TREE;
+	  si->dont_invalidate = true;
+	}
+      if (si->next == 0)
+	return;
+      nsi = get_strinfo (si->next);
+      if (nsi == NULL
+	  || nsi->first != si->first
+	  || nsi->prev != si->idx)
+	return;
+      si = nsi;
+    }
+}
+
+/* Find if there are other SSA_NAME pointers equal to PTR
+   for which we don't track their string lengths yet.  If so, use
+   IDX for them.  */
+
+static void
+find_equal_ptrs (tree ptr, int idx)
+{
+  if (TREE_CODE (ptr) != SSA_NAME)
+    return;
+  while (1)
+    {
+      gimple stmt = SSA_NAME_DEF_STMT (ptr);
+      if (!is_gimple_assign (stmt))
+	return;
+      ptr = gimple_assign_rhs1 (stmt);
+      switch (gimple_assign_rhs_code (stmt))
+	{
+	case SSA_NAME:
+	  break;
+	case ADDR_EXPR:
+	  {
+	    int *pidx = addr_stridxptr (TREE_OPERAND (ptr, 0));
+	    if (pidx != NULL && *pidx == 0)
+	      *pidx = idx;
+	    return;
+	  }
+	CASE_CONVERT:
+	  if (POINTER_TYPE_P (TREE_TYPE (ptr)))
+	    break;
+	  return;
+	default:
+	  return;
+	}
+
+      /* We might find an endptr created in this pass.  Grow the
+	 vector in that case.  */
+      if (VEC_length (int, ssa_ver_to_stridx) <= SSA_NAME_VERSION (ptr))
+	VEC_safe_grow_cleared (int, heap, ssa_ver_to_stridx, num_ssa_names);
+
+      if (VEC_index (int, ssa_ver_to_stridx, SSA_NAME_VERSION (ptr)) != 0)
+	return;
+      VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (ptr), idx);
+    }
+}
+
+/* If the last .MEM setter statement before STMT is
+   memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
+   and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
+   just memcpy (x, y, strlen (y)).  SI must be the zero length
+   strinfo.  */
+
+static void
+adjust_last_stmt (strinfo si, gimple stmt, bool is_strcat)
+{
+  tree vuse, callee, len;
+  struct laststmt_struct last = laststmt;
+  strinfo lastsi, firstsi;
+
+  laststmt.stmt = NULL;
+  laststmt.len = NULL_TREE;
+  laststmt.stridx = 0;
+
+  if (last.stmt == NULL)
+    return;
+
+  vuse = gimple_vuse (stmt);
+  if (vuse == NULL_TREE
+      || SSA_NAME_DEF_STMT (vuse) != last.stmt
+      || !has_single_use (vuse))
+    return;
+
+  gcc_assert (last.stridx > 0);
+  lastsi = get_strinfo (last.stridx);
+  if (lastsi == NULL)
+    return;
+
+  if (lastsi != si)
+    {
+      if (lastsi->first == 0 || lastsi->first != si->first)
+	return;
+
+      firstsi = verify_related_strinfos (si);
+      if (firstsi == NULL)
+	return;
+      while (firstsi != lastsi)
+	{
+	  strinfo nextsi;
+	  if (firstsi->next == 0)
+	    return;
+	  nextsi = get_strinfo (firstsi->next);
+	  if (nextsi == NULL
+	      || nextsi->prev != firstsi->idx
+	      || nextsi->first != si->first)
+	    return;
+	  firstsi = nextsi;
+	}
+    }
+
+  if (!is_strcat)
+    {
+      if (si->length == NULL_TREE || !integer_zerop (si->length))
+	return;
+    }
+
+  if (is_gimple_assign (last.stmt))
+    {
+      gimple_stmt_iterator gsi;
+
+      if (!integer_zerop (gimple_assign_rhs1 (last.stmt)))
+	return;
+      if (stmt_could_throw_p (last.stmt))
+	return;
+      gsi = gsi_for_stmt (last.stmt);
+      unlink_stmt_vdef (last.stmt);
+      release_defs (last.stmt);
+      gsi_remove (&gsi, true);
+      return;
+    }
+
+  if (!is_gimple_call (last.stmt))
+    return;
+  callee = gimple_call_fndecl (last.stmt);
+  if (callee == NULL_TREE || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL)
+    return;
+
+  switch (DECL_FUNCTION_CODE (callee))
+    {
+    case BUILT_IN_MEMCPY:
+    case BUILT_IN_MEMCPY_CHK:
+      break;
+    default:
+      return;
+    }
+
+  len = gimple_call_arg (last.stmt, 2);
+  if (host_integerp (len, 1))
+    {
+      if (!host_integerp (last.len, 1)
+	  || integer_zerop (len)
+	  || (unsigned HOST_WIDE_INT) tree_low_cst (len, 1)
+	     != (unsigned HOST_WIDE_INT) tree_low_cst (last.len, 1) + 1)
+	return;
+      /* Don't adjust the length if it is divisible by 4, it is more efficient
+	 to store the extra '\0' in that case.  */
+      if ((((unsigned HOST_WIDE_INT) tree_low_cst (len, 1)) & 3) == 0)
+	return;
+    }
+  else if (TREE_CODE (len) == SSA_NAME)
+    {
+      gimple def_stmt = SSA_NAME_DEF_STMT (len);
+      if (!is_gimple_assign (def_stmt)
+	  || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
+	  || gimple_assign_rhs1 (def_stmt) != last.len
+	  || !integer_onep (gimple_assign_rhs2 (def_stmt)))
+	return;
+    }
+  else
+    return;
+
+  gimple_call_set_arg (last.stmt, 2, last.len);
+  update_stmt (last.stmt);
+}
+
+/* Handle a strlen call.  If strlen of the argument is known, replace
+   the strlen call with the known value, otherwise remember that strlen
+   of the argument is stored in the lhs SSA_NAME.  */
+
+static void
+handle_builtin_strlen (gimple_stmt_iterator *gsi)
+{
+  int idx;
+  tree src;
+  gimple stmt = gsi_stmt (*gsi);
+  tree lhs = gimple_call_lhs (stmt);
+
+  if (lhs == NULL_TREE)
+    return;
+
+  src = gimple_call_arg (stmt, 0);
+  idx = get_stridx (src);
+  if (idx)
+    {
+      strinfo si = NULL;
+      tree rhs;
+
+      if (idx < 0)
+	rhs = build_int_cst (TREE_TYPE (lhs), ~idx);
+      else
+	{
+	  rhs = NULL_TREE;
+	  si = get_strinfo (idx);
+	  if (si != NULL)
+	    rhs = get_string_length (si);
+	}
+      if (rhs != NULL_TREE)
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS) != 0)
+	    {
+	      fprintf (dump_file, "Optimizing: ");
+	      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+	    }
+	  rhs = unshare_expr (rhs);
+	  if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
+	    rhs = fold_convert_loc (gimple_location (stmt),
+				    TREE_TYPE (lhs), rhs);
+	  if (!update_call_from_tree (gsi, rhs))
+	    gimplify_and_update_call_from_tree (gsi, rhs);
+	  stmt = gsi_stmt (*gsi);
+	  update_stmt (stmt);
+	  if (dump_file && (dump_flags & TDF_DETAILS) != 0)
+	    {
+	      fprintf (dump_file, "into: ");
+	      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+	    }
+	  if (si != NULL
+	      && TREE_CODE (si->length) != SSA_NAME
+	      && TREE_CODE (si->length) != INTEGER_CST
+	      && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
+	    {
+	      si = unshare_strinfo (si);
+	      si->length = lhs;
+	    }
+	  return;
+	}
+    }
+  if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
+    return;
+  if (idx == 0)
+    idx = new_stridx (src);
+  else if (get_strinfo (idx) != NULL)
+    return;
+  if (idx)
+    {
+      strinfo si = new_strinfo (src, idx, lhs);
+      set_strinfo (idx, si);
+      find_equal_ptrs (src, idx);
+    }
+}
+
+/* Handle a strchr call.  If strlen of the first argument is known, replace
+   the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
+   that lhs of the call is endptr and strlen of the argument is endptr - x.  */
+
+static void
+handle_builtin_strchr (gimple_stmt_iterator *gsi)
+{
+  int idx;
+  tree src;
+  gimple stmt = gsi_stmt (*gsi);
+  tree lhs = gimple_call_lhs (stmt);
+
+  if (lhs == NULL_TREE)
+    return;
+
+  if (!integer_zerop (gimple_call_arg (stmt, 1)))
+    return;
+
+  src = gimple_call_arg (stmt, 0);
+  idx = get_stridx (src);
+  if (idx)
+    {
+      strinfo si = NULL;
+      tree rhs;
+
+      if (idx < 0)
+	rhs = build_int_cst (size_type_node, ~idx);
+      else
+	{
+	  rhs = NULL_TREE;
+	  si = get_strinfo (idx);
+	  if (si != NULL)
+	    rhs = get_string_length (si);
+	}
+      if (rhs != NULL_TREE)
+	{
+	  location_t loc = gimple_location (stmt);
+
+	  if (dump_file && (dump_flags & TDF_DETAILS) != 0)
+	    {
+	      fprintf (dump_file, "Optimizing: ");
+	      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+	    }
+	  if (si != NULL && si->endptr != NULL_TREE)
+	    {
+	      rhs = unshare_expr (si->endptr);
+	      if (!useless_type_conversion_p (TREE_TYPE (lhs),
+					      TREE_TYPE (rhs)))
+		rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
+	    }
+	  else
+	    {
+	      rhs = fold_convert_loc (loc, sizetype, unshare_expr (rhs));
+	      rhs = fold_build2_loc (loc, POINTER_PLUS_EXPR,
+				     TREE_TYPE (src), src, rhs);
+	      if (!useless_type_conversion_p (TREE_TYPE (lhs),
+					      TREE_TYPE (rhs)))
+		rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
+	    }
+	  if (!update_call_from_tree (gsi, rhs))
+	    gimplify_and_update_call_from_tree (gsi, rhs);
+	  stmt = gsi_stmt (*gsi);
+	  update_stmt (stmt);
+	  if (dump_file && (dump_flags & TDF_DETAILS) != 0)
+	    {
+	      fprintf (dump_file, "into: ");
+	      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+	    }
+	  if (si != NULL
+	      && si->endptr == NULL_TREE
+	      && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
+	    {
+	      si = unshare_strinfo (si);
+	      si->endptr = lhs;
+	    }
+	  zero_length_string (lhs, si);
+	  return;
+	}
+    }
+  if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
+    return;
+  if (TREE_CODE (src) != SSA_NAME || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src))
+    {
+      if (idx == 0)
+	idx = new_stridx (src);
+      else if (get_strinfo (idx) != NULL)
+	{
+	  zero_length_string (lhs, NULL);
+	  return;
+	}
+      if (idx)
+	{
+	  location_t loc = gimple_location (stmt);
+	  tree lhsu = fold_convert_loc (loc, size_type_node, lhs);
+	  tree srcu = fold_convert_loc (loc, size_type_node, src);
+	  tree length = fold_build2_loc (loc, MINUS_EXPR,
+					 size_type_node, lhsu, srcu);
+	  strinfo si = new_strinfo (src, idx, length);
+	  si->endptr = lhs;
+	  set_strinfo (idx, si);
+	  find_equal_ptrs (src, idx);
+	  zero_length_string (lhs, si);
+	}
+    }
+  else
+    zero_length_string (lhs, NULL);
+}
+
+/* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
+   If strlen of the second argument is known, strlen of the first argument
+   is the same after this call.  Furthermore, attempt to convert it to
+   memcpy.  */
+
+static void
+handle_builtin_strcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi)
+{
+  int idx, didx;
+  tree src, dst, srclen, len, lhs, args, type, fn, oldlen;
+  bool success;
+  gimple stmt = gsi_stmt (*gsi);
+  strinfo si, dsi, olddsi, zsi;
+  location_t loc;
+
+  src = gimple_call_arg (stmt, 1);
+  dst = gimple_call_arg (stmt, 0);
+  lhs = gimple_call_lhs (stmt);
+  idx = get_stridx (src);
+  si = NULL;
+  if (idx > 0)
+    si = get_strinfo (idx);
+
+  didx = get_stridx (dst);
+  olddsi = NULL;
+  oldlen = NULL_TREE;
+  if (didx > 0)
+    olddsi = get_strinfo (didx);
+  else if (didx < 0)
+    return;
+
+  if (olddsi != NULL)
+    adjust_last_stmt (olddsi, stmt, false);
+
+  srclen = NULL_TREE;
+  if (si != NULL)
+    srclen = get_string_length (si);
+  else if (idx < 0)
+    srclen = build_int_cst (size_type_node, ~idx);
+
+  loc = gimple_location (stmt);
+  if (srclen == NULL_TREE)
+    switch (bcode)
+      {
+      case BUILT_IN_STRCPY:
+      case BUILT_IN_STRCPY_CHK:
+	if (implicit_built_in_decls[BUILT_IN_STPCPY] == NULL_TREE
+	    || lhs != NULL_TREE)
+	  return;
+	break;
+      case BUILT_IN_STPCPY:
+      case BUILT_IN_STPCPY_CHK:
+	if (lhs == NULL_TREE)
+	  return;
+	else
+	  {
+	    tree lhsuint = fold_convert_loc (loc, size_type_node, lhs);
+	    srclen = fold_convert_loc (loc, size_type_node, dst);
+	    srclen = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
+				      lhsuint, srclen);
+	  }
+	break;
+      default:
+	gcc_unreachable ();
+      }
+
+  if (didx == 0)
+    {
+      didx = new_stridx (dst);
+      if (didx == 0)
+	return;
+    }
+  if (olddsi != NULL)
+    {
+      oldlen = olddsi->length;
+      dsi = unshare_strinfo (olddsi);
+      dsi->length = srclen;
+      /* Break the chain, so adjust_related_strinfo on later pointers in
+	 the chain won't adjust this one anymore.  */
+      dsi->next = 0;
+      dsi->stmt = NULL;
+      dsi->endptr = NULL_TREE;
+    }
+  else
+    {
+      dsi = new_strinfo (dst, didx, srclen);
+      set_strinfo (didx, dsi);
+      find_equal_ptrs (dst, didx);
+    }
+  dsi->writable = true;
+  dsi->dont_invalidate = true;
+
+  if (dsi->length == NULL_TREE)
+    {
+      /* If string length of src is unknown, use delayed length
+	 computation.  If string lenth of dst will be needed, it
+	 can be computed by transforming this strcpy call into
+	 stpcpy and subtracting dst from the return value.  */
+      dsi->stmt = stmt;
+      return;
+    }
+
+  if (olddsi != NULL)
+    {
+      tree adj = NULL_TREE;
+      if (oldlen == NULL_TREE)
+	;
+      else if (integer_zerop (oldlen))
+	adj = srclen;
+      else if (TREE_CODE (oldlen) == INTEGER_CST
+	       || TREE_CODE (srclen) == INTEGER_CST)
+	adj = fold_build2_loc (loc, MINUS_EXPR,
+			       TREE_TYPE (srclen), srclen,
+			       fold_convert_loc (loc, TREE_TYPE (srclen),
+						 oldlen));
+      if (adj != NULL_TREE)
+	adjust_related_strinfos (loc, dsi, adj);
+      else
+	dsi->prev = 0;
+    }
+  /* strcpy src may not overlap dst, so src doesn't need to be
+     invalidated either.  */
+  if (si != NULL)
+    si->dont_invalidate = true;
+
+  fn = NULL_TREE;
+  zsi = NULL;
+  switch (bcode)
+    {
+    case BUILT_IN_STRCPY:
+      fn = implicit_built_in_decls[BUILT_IN_MEMCPY];
+      if (lhs)
+	VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs), didx);
+      break;
+    case BUILT_IN_STRCPY_CHK:
+      fn = built_in_decls[BUILT_IN_MEMCPY_CHK];
+      if (lhs)
+	VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs), didx);
+      break;
+    case BUILT_IN_STPCPY:
+      /* This would need adjustment of the lhs (subtract one),
+	 or detection that the trailing '\0' doesn't need to be
+	 written, if it will be immediately overwritten.
+      fn = built_in_decls[BUILT_IN_MEMPCPY];  */
+      if (lhs)
+	{
+	  dsi->endptr = lhs;
+	  zsi = zero_length_string (lhs, dsi);
+	}
+      break;
+    case BUILT_IN_STPCPY_CHK:
+      /* This would need adjustment of the lhs (subtract one),
+	 or detection that the trailing '\0' doesn't need to be
+	 written, if it will be immediately overwritten.
+      fn = built_in_decls[BUILT_IN_MEMPCPY_CHK];  */
+      if (lhs)
+	{
+	  dsi->endptr = lhs;
+	  zsi = zero_length_string (lhs, dsi);
+	}
+      break;
+    default:
+      gcc_unreachable ();
+    }
+  if (zsi != NULL)
+    zsi->dont_invalidate = true;
+
+  if (fn == NULL_TREE)
+    return;
+
+  args = TYPE_ARG_TYPES (TREE_TYPE (fn));
+  type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
+
+  len = fold_convert_loc (loc, type, unshare_expr (srclen));
+  len = fold_build2_loc (loc, PLUS_EXPR, type, len, build_int_cst (type, 1));
+  len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
+				  GSI_SAME_STMT);
+  if (dump_file && (dump_flags & TDF_DETAILS) != 0)
+    {
+      fprintf (dump_file, "Optimizing: ");
+      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+    }
+  if (gimple_call_num_args (stmt) == 2)
+    success = update_gimple_call (gsi, fn, 3, dst, src, len);
+  else
+    success = update_gimple_call (gsi, fn, 4, dst, src, len,
+				  gimple_call_arg (stmt, 2));
+  if (success)
+    {
+      stmt = gsi_stmt (*gsi);
+      update_stmt (stmt);
+      if (dump_file && (dump_flags & TDF_DETAILS) != 0)
+	{
+	  fprintf (dump_file, "into: ");
+	  print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+	}
+      /* Allow adjust_last_stmt to decrease this memcpy's size.  */
+      laststmt.stmt = stmt;
+      laststmt.len = srclen;
+      laststmt.stridx = dsi->idx;
+    }
+  else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
+    fprintf (dump_file, "not possible.\n");
+}
+
+/* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
+   If strlen of the second argument is known and length of the third argument
+   is that plus one, strlen of the first argument is the same after this
+   call.  */
+
+static void
+handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi)
+{
+  int idx, didx;
+  tree src, dst, len, lhs, oldlen, newlen;
+  gimple stmt = gsi_stmt (*gsi);
+  strinfo si, dsi, olddsi;
+
+  len = gimple_call_arg (stmt, 2);
+  src = gimple_call_arg (stmt, 1);
+  dst = gimple_call_arg (stmt, 0);
+  idx = get_stridx (src);
+  if (idx == 0)
+    return;
+
+  didx = get_stridx (dst);
+  olddsi = NULL;
+  if (didx > 0)
+    olddsi = get_strinfo (didx);
+  else if (didx < 0)
+    return;
+
+  if (olddsi != NULL
+      && host_integerp (len, 1)
+      && !integer_zerop (len))
+    adjust_last_stmt (olddsi, stmt, false);
+
+  if (idx > 0)
+    {
+      gimple def_stmt;
+
+      /* Handle memcpy (x, y, l) where l is strlen (y) + 1.  */
+      si = get_strinfo (idx);
+      if (si == NULL || si->length == NULL_TREE)
+	return;
+      if (TREE_CODE (len) != SSA_NAME)
+	return;
+      def_stmt = SSA_NAME_DEF_STMT (len);
+      if (!is_gimple_assign (def_stmt)
+	  || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
+	  || gimple_assign_rhs1 (def_stmt) != si->length
+	  || !integer_onep (gimple_assign_rhs2 (def_stmt)))
+	return;
+    }
+  else
+    {
+      si = NULL;
+      /* Handle memcpy (x, "abcd", 5) or
+	 memcpy (x, "abc\0uvw", 7).  */
+      if (!host_integerp (len, 1)
+	  || (unsigned HOST_WIDE_INT) tree_low_cst (len, 1)
+	     <= (unsigned HOST_WIDE_INT) ~idx)
+	return;
+    }
+
+  if (olddsi != NULL && TREE_CODE (len) == SSA_NAME)
+    adjust_last_stmt (olddsi, stmt, false);
+
+  if (didx == 0)
+    {
+      didx = new_stridx (dst);
+      if (didx == 0)
+	return;
+    }
+  if (si != NULL)
+    newlen = si->length;
+  else
+    newlen = build_int_cst (TREE_TYPE (len), ~idx);
+  oldlen = NULL_TREE;
+  if (olddsi != NULL)
+    {
+      dsi = unshare_strinfo (olddsi);
+      oldlen = olddsi->length;
+      dsi->length = newlen;
+      /* Break the chain, so adjust_related_strinfo on later pointers in
+	 the chain won't adjust this one anymore.  */
+      dsi->next = 0;
+      dsi->stmt = NULL;
+      dsi->endptr = NULL_TREE;
+    }
+  else
+    {
+      dsi = new_strinfo (dst, didx, newlen);
+      set_strinfo (didx, dsi);
+      find_equal_ptrs (dst, didx);
+    }
+  dsi->writable = true;
+  dsi->dont_invalidate = true;
+  if (olddsi != NULL)
+    {
+      tree adj = NULL_TREE;
+      location_t loc = gimple_location (stmt);
+      if (oldlen == NULL_TREE)
+	;
+      else if (integer_zerop (oldlen))
+	adj = dsi->length;
+      else if (TREE_CODE (oldlen) == INTEGER_CST
+	       || TREE_CODE (dsi->length) == INTEGER_CST)
+	adj = fold_build2_loc (loc, MINUS_EXPR,
+			       TREE_TYPE (dsi->length), dsi->length,
+			       fold_convert_loc (loc, TREE_TYPE (dsi->length),
+						 oldlen));
+      if (adj != NULL_TREE)
+	adjust_related_strinfos (loc, dsi, adj);
+      else
+	dsi->prev = 0;
+    }
+  /* memcpy src may not overlap dst, so src doesn't need to be
+     invalidated either.  */
+  if (si != NULL)
+    si->dont_invalidate = true;
+
+  lhs = gimple_call_lhs (stmt);
+  switch (bcode)
+    {
+    case BUILT_IN_MEMCPY:
+    case BUILT_IN_MEMCPY_CHK:
+      /* Allow adjust_last_stmt to decrease this memcpy's size.  */
+      laststmt.stmt = stmt;
+      laststmt.len = dsi->length;
+      laststmt.stridx = dsi->idx;
+      if (lhs)
+	VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs), didx);
+      break;
+    case BUILT_IN_MEMPCPY:
+    case BUILT_IN_MEMPCPY_CHK:
+      break;
+    default:
+      gcc_unreachable ();
+    }
+}
+
+/* Handle a strcat-like ({strcat,__strcat_chk}) call.
+   If strlen of the second argument is known, strlen of the first argument
+   is increased by the length of the second argument.  Furthermore, attempt
+   to convert it to memcpy/strcpy if the length of the first argument
+   is known.  */
+
+static void
+handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi)
+{
+  int idx, didx;
+  tree src, dst, srclen, dstlen, len, lhs, args, type, fn, objsz, endptr;
+  bool success;
+  gimple stmt = gsi_stmt (*gsi);
+  strinfo si, dsi;
+  location_t loc;
+
+  src = gimple_call_arg (stmt, 1);
+  dst = gimple_call_arg (stmt, 0);
+  lhs = gimple_call_lhs (stmt);
+
+  didx = get_stridx (dst);
+  if (didx < 0)
+    return;
+
+  dsi = NULL;
+  if (didx > 0)
+    dsi = get_strinfo (didx);
+  if (dsi == NULL || get_string_length (dsi) == NULL_TREE)
+    {
+      /* strcat (p, q) can be transformed into
+	 tmp = p + strlen (p); endptr = strpcpy (tmp, q);
+	 with length endptr - p if we need to compute the length
+	 later on.  Don't do this transformation if we don't need
+	 it.  */
+      if (implicit_built_in_decls[BUILT_IN_STPCPY] != NULL_TREE
+	  && lhs == NULL_TREE)
+	{
+	  if (didx == 0)
+	    {
+	      didx = new_stridx (dst);
+	      if (didx == 0)
+		return;
+	    }
+	  if (dsi == NULL)
+	    {
+	      dsi = new_strinfo (dst, didx, NULL_TREE);
+	      set_strinfo (didx, dsi);
+	      find_equal_ptrs (dst, didx);
+	    }
+	  else
+	    {
+	      dsi = unshare_strinfo (dsi);
+	      dsi->length = NULL_TREE;
+	      dsi->next = 0;
+	      dsi->endptr = NULL_TREE;
+	    }
+	  dsi->writable = true;
+	  dsi->stmt = stmt;
+	  dsi->dont_invalidate = true;
+	}
+      return;
+    }
+
+  srclen = NULL_TREE;
+  si = NULL;
+  idx = get_stridx (src);
+  if (idx < 0)
+    srclen = build_int_cst (size_type_node, ~idx);
+  else if (idx > 0)
+    {
+      si = get_strinfo (idx);
+      if (si != NULL)
+	srclen = get_string_length (si);
+    }
+
+  loc = gimple_location (stmt);
+  dstlen = dsi->length;
+  endptr = dsi->endptr;
+
+  dsi = unshare_strinfo (dsi);
+  dsi->endptr = NULL_TREE;
+  dsi->stmt = NULL;
+  dsi->writable = true;
+
+  if (srclen != NULL_TREE)
+    {
+      dsi->length = fold_build2_loc (loc, PLUS_EXPR, TREE_TYPE (dsi->length),
+				     dsi->length, srclen);
+      adjust_related_strinfos (loc, dsi, srclen);
+      dsi->dont_invalidate = true;
+    }
+  else
+    {
+      dsi->length = NULL;
+      if (implicit_built_in_decls[BUILT_IN_STPCPY] != NULL_TREE
+	  && lhs == NULL_TREE)
+	dsi->dont_invalidate = true;
+    }
+
+  if (si != NULL)
+    /* strcat src may not overlap dst, so src doesn't need to be
+       invalidated either.  */
+    si->dont_invalidate = true;
+
+  /* For now.  Could remove the lhs from the call and add
+     lhs = dst; afterwards.  */
+  if (lhs)
+    return;
+
+  fn = NULL_TREE;
+  objsz = NULL_TREE;
+  switch (bcode)
+    {
+    case BUILT_IN_STRCAT:
+      if (srclen != NULL_TREE)
+	fn = implicit_built_in_decls[BUILT_IN_MEMCPY];
+      else
+	fn = implicit_built_in_decls[BUILT_IN_STRCPY];
+      break;
+    case BUILT_IN_STRCAT_CHK:
+      if (srclen != NULL_TREE)
+	fn = built_in_decls[BUILT_IN_MEMCPY_CHK];
+      else
+	fn = built_in_decls[BUILT_IN_STRCPY_CHK];
+      objsz = gimple_call_arg (stmt, 2);
+      break;
+    default:
+      gcc_unreachable ();
+    }
+
+  if (fn == NULL_TREE)
+    return;
+
+  len = NULL_TREE;
+  if (srclen != NULL_TREE)
+    {
+      args = TYPE_ARG_TYPES (TREE_TYPE (fn));
+      type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
+
+      len = fold_convert_loc (loc, type, unshare_expr (srclen));
+      len = fold_build2_loc (loc, PLUS_EXPR, type, len,
+			     build_int_cst (type, 1));
+      len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
+				      GSI_SAME_STMT);
+    }
+  if (endptr)
+    dst = fold_convert_loc (loc, TREE_TYPE (dst), unshare_expr (endptr));
+  else
+    dst = fold_build2_loc (loc, POINTER_PLUS_EXPR,
+			   TREE_TYPE (dst), unshare_expr (dst),
+			   fold_convert_loc (loc, sizetype,
+					     unshare_expr (dstlen)));
+  dst = force_gimple_operand_gsi (gsi, dst, true, NULL_TREE, true,
+				  GSI_SAME_STMT);
+  if (dump_file && (dump_flags & TDF_DETAILS) != 0)
+    {
+      fprintf (dump_file, "Optimizing: ");
+      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+    }
+  if (srclen != NULL_TREE)
+    success = update_gimple_call (gsi, fn, 3 + (objsz != NULL_TREE),
+				  dst, src, len, objsz);
+  else
+    success = update_gimple_call (gsi, fn, 2 + (objsz != NULL_TREE),
+				  dst, src, objsz);
+  if (success)
+    {
+      stmt = gsi_stmt (*gsi);
+      update_stmt (stmt);
+      if (dump_file && (dump_flags & TDF_DETAILS) != 0)
+	{
+	  fprintf (dump_file, "into: ");
+	  print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+	}
+      /* If srclen == NULL, note that current string length can be
+	 computed by transforming this strcpy into stpcpy.  */
+      if (srclen == NULL_TREE && dsi->dont_invalidate)
+	dsi->stmt = stmt;
+      adjust_last_stmt (dsi, stmt, true);
+      if (srclen != NULL_TREE)
+	{
+	  laststmt.stmt = stmt;
+	  laststmt.len = srclen;
+	  laststmt.stridx = dsi->idx;
+	}
+    }
+  else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
+    fprintf (dump_file, "not possible.\n");
+}
+
+/* Handle a POINTER_PLUS_EXPR statement.
+   For p = "abcd" + 2; compute associated length, or if
+   p = q + off is pointing to a '\0' character of a string, call
+   zero_length_string on it.  */
+
+static void
+handle_pointer_plus (gimple_stmt_iterator *gsi)
+{
+  gimple stmt = gsi_stmt (*gsi);
+  tree lhs = gimple_assign_lhs (stmt), off;
+  int idx = get_stridx (gimple_assign_rhs1 (stmt));
+  strinfo si, zsi;
+
+  if (idx == 0)
+    return;
+
+  if (idx < 0)
+    {
+      tree off = gimple_assign_rhs2 (stmt);
+      if (host_integerp (off, 1)
+	  && (unsigned HOST_WIDE_INT) tree_low_cst (off, 1)
+	     <= (unsigned HOST_WIDE_INT) ~idx)
+	VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs),
+		     ~(~idx - (int) tree_low_cst (off, 1)));
+      return;
+    }
+
+  si = get_strinfo (idx);
+  if (si == NULL || si->length == NULL_TREE)
+    return;
+
+  off = gimple_assign_rhs2 (stmt);
+  zsi = NULL;
+  if (operand_equal_p (si->length, off, 0))
+    zsi = zero_length_string (lhs, si);
+  else if (TREE_CODE (off) == SSA_NAME)
+    {
+      gimple def_stmt = SSA_NAME_DEF_STMT (off);
+      if (gimple_assign_single_p (def_stmt)
+	  && operand_equal_p (si->length, gimple_assign_rhs1 (def_stmt), 0))
+	zsi = zero_length_string (lhs, si);
+    }
+  if (zsi != NULL
+      && si->endptr != NULL_TREE
+      && si->endptr != lhs
+      && TREE_CODE (si->endptr) == SSA_NAME)
+    {
+      enum tree_code rhs_code
+	= useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (si->endptr))
+	  ? SSA_NAME : NOP_EXPR;
+      gimple_assign_set_rhs_with_ops (gsi, rhs_code, si->endptr, NULL_TREE);
+      gcc_assert (gsi_stmt (*gsi) == stmt);
+      update_stmt (stmt);
+    }
+}
+
+/* Handle a single character store.  */
+
+static bool
+handle_char_store (gimple_stmt_iterator *gsi)
+{
+  int idx = -1;
+  strinfo si = NULL;
+  gimple stmt = gsi_stmt (*gsi);
+  tree ssaname = NULL_TREE, lhs = gimple_assign_lhs (stmt);
+
+  if (TREE_CODE (lhs) == MEM_REF
+      && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME)
+    {
+      if (integer_zerop (TREE_OPERAND (lhs, 1)))
+	{
+	  ssaname = TREE_OPERAND (lhs, 0);
+	  idx = get_stridx (ssaname);
+	}
+    }
+  else
+    idx = get_addr_stridx (lhs);
+
+  if (idx > 0)
+    {
+      si = get_strinfo (idx);
+      if (si != NULL && si->length != NULL_TREE && integer_zerop (si->length))
+	{
+	  if (initializer_zerop (gimple_assign_rhs1 (stmt)))
+	    {
+	      /* When storing '\0', the store can be removed
+		 if we know it has been stored in the current function.  */
+	      if (!stmt_could_throw_p (stmt) && si->writable)
+		{
+		  unlink_stmt_vdef (stmt);
+		  release_defs (stmt);
+		  gsi_remove (gsi, true);
+		  return false;
+		}
+	      else
+		{
+		  si->writable = true;
+		  si->dont_invalidate = true;
+		}
+	    }
+	  else
+	    /* Otherwise this statement overwrites the '\0' with
+	       something, if the previous stmt was a memcpy,
+	       its length may be decreased.  */
+	    adjust_last_stmt (si, stmt, false);
+	}
+      else if (si != NULL)
+	{
+	  si = unshare_strinfo (si);
+	  si->length = build_int_cst (size_type_node, 0);
+	  si->endptr = NULL;
+	  si->prev = 0;
+	  si->next = 0;
+	  si->stmt = NULL;
+	  si->first = 0;
+	  si->writable = true;
+	  if (ssaname && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname))
+	    si->endptr = ssaname;
+	  si->dont_invalidate = true;
+	}
+    }
+  else if (idx == 0 && initializer_zerop (gimple_assign_rhs1 (stmt)))
+    {
+      if (ssaname)
+	{
+	  si = zero_length_string (ssaname, NULL);
+	  if (si != NULL)
+	    si->dont_invalidate = true;
+	}
+      else
+	{
+	  int idx = new_addr_stridx (lhs);
+	  if (idx != 0)
+	    {
+	      si = new_strinfo (build_fold_addr_expr (lhs), idx,
+				build_int_cst (size_type_node, 0));
+	      set_strinfo (idx, si);
+	      si->dont_invalidate = true;
+	    }
+	}
+      if (si != NULL)
+	si->writable = true;
+    }
+
+  if (si != NULL && initializer_zerop (gimple_assign_rhs1 (stmt)))
+    {
+      /* Allow adjust_last_stmt to remove it if the stored '\0'
+	 is immediately overwritten.  */
+      laststmt.stmt = stmt;
+      laststmt.len = build_int_cst (size_type_node, 1);
+      laststmt.stridx = si->idx;
+    }
+  return true;
+}
+
+/* Attempt to optimize a single statement at *GSI using string length
+   knowledge.  */
+
+static bool
+strlen_optimize_stmt (gimple_stmt_iterator *gsi)
+{
+  gimple stmt = gsi_stmt (*gsi);
+
+  if (is_gimple_call (stmt))
+    {
+      tree callee = gimple_call_fndecl (stmt);
+      if (callee && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
+	switch (DECL_FUNCTION_CODE (callee))
+	  {
+	  case BUILT_IN_STRLEN:
+	    handle_builtin_strlen (gsi);
+	    break;
+	  case BUILT_IN_STRCHR:
+	    handle_builtin_strchr (gsi);
+	    break;
+	  case BUILT_IN_STRCPY:
+	  case BUILT_IN_STRCPY_CHK:
+	  case BUILT_IN_STPCPY:
+	  case BUILT_IN_STPCPY_CHK:
+	    handle_builtin_strcpy (DECL_FUNCTION_CODE (callee), gsi);
+	    break;
+	  case BUILT_IN_MEMCPY:
+	  case BUILT_IN_MEMCPY_CHK:
+	  case BUILT_IN_MEMPCPY:
+	  case BUILT_IN_MEMPCPY_CHK:
+	    handle_builtin_memcpy (DECL_FUNCTION_CODE (callee), gsi);
+	    break;
+	  case BUILT_IN_STRCAT:
+	  case BUILT_IN_STRCAT_CHK:
+	    handle_builtin_strcat (DECL_FUNCTION_CODE (callee), gsi);
+	    break;
+	  default:
+	    break;
+	  }
+    }
+  else if (is_gimple_assign (stmt))
+    {
+      tree lhs = gimple_assign_lhs (stmt);
+
+      if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (lhs)))
+	{
+	  if (gimple_assign_single_p (stmt)
+	      || (gimple_assign_cast_p (stmt)
+		  && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt)))))
+	    {
+	      int idx = get_stridx (gimple_assign_rhs1 (stmt));
+	      VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs),
+			   idx);
+	    }
+	  else if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
+	    handle_pointer_plus (gsi);
+	}
+      else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs))
+	{
+	  tree type = TREE_TYPE (lhs);
+	  if (TREE_CODE (type) == ARRAY_TYPE)
+	    type = TREE_TYPE (type);
+	  if (TREE_CODE (type) == INTEGER_TYPE
+	      && TYPE_MODE (type) == TYPE_MODE (char_type_node)
+	      && TYPE_PRECISION (type) == TYPE_PRECISION (char_type_node))
+	    {
+	      if (! handle_char_store (gsi))
+		return false;
+	    }
+	}
+    }
+
+  if (gimple_vdef (stmt))
+    maybe_invalidate (stmt);
+  return true;
+}
+
+/* Recursively call maybe_invalidate on stmts that might be executed
+   in between dombb and current bb and that contain a vdef.  Stop when
+   *count stmts are inspected, or if the whole strinfo vector has
+   been invalidated.  */
+
+static void
+do_invalidate (basic_block dombb, gimple phi, bitmap visited, int *count)
+{
+  unsigned int i, n = gimple_phi_num_args (phi);
+
+  for (i = 0; i < n; i++)
+    {
+      tree vuse = gimple_phi_arg_def (phi, i);
+      gimple stmt = SSA_NAME_DEF_STMT (vuse);
+      basic_block bb = gimple_bb (stmt);
+      if (bb == NULL
+	  || bb == dombb
+	  || !bitmap_set_bit (visited, bb->index)
+	  || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
+	continue;
+      while (1)
+	{
+	  if (gimple_code (stmt) == GIMPLE_PHI)
+	    {
+	      do_invalidate (dombb, stmt, visited, count);
+	      if (*count == 0)
+		return;
+	      break;
+	    }
+	  if (--*count == 0)
+	    return;
+	  if (!maybe_invalidate (stmt))
+	    {
+	      *count = 0;
+	      return;
+	    }
+	  vuse = gimple_vuse (stmt);
+	  stmt = SSA_NAME_DEF_STMT (vuse);
+	  if (gimple_bb (stmt) != bb)
+	    {
+	      bb = gimple_bb (stmt);
+	      if (bb == NULL
+		  || bb == dombb
+		  || !bitmap_set_bit (visited, bb->index)
+		  || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
+		break;
+	    }
+	}
+    }
+}
+
+/* Callback for walk_dominator_tree.  Attempt to optimize various
+   string ops by remembering string lenths pointed by pointer SSA_NAMEs.  */
+
+static void
+strlen_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+		    basic_block bb)
+{
+  gimple_stmt_iterator gsi;
+  basic_block dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
+
+  if (dombb == NULL)
+    stridx_to_strinfo = NULL;
+  else
+    {
+      stridx_to_strinfo = (VEC(strinfo, heap) *) dombb->aux;
+      if (stridx_to_strinfo)
+	{
+	  for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+	    {
+	      gimple phi = gsi_stmt (gsi);
+	      if (!is_gimple_reg (gimple_phi_result (phi)))
+		{
+		  bitmap visited = BITMAP_ALLOC (NULL);
+		  int count_vdef = 100;
+		  do_invalidate (dombb, phi, visited, &count_vdef);
+		  BITMAP_FREE (visited);
+		  break;
+		}
+	    }
+	}
+    }
+
+  /* If all PHI arguments have the same string index, the PHI result
+     has it as well.  */
+  for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      gimple phi = gsi_stmt (gsi);
+      tree result = gimple_phi_result (phi);
+      if (is_gimple_reg (result) && POINTER_TYPE_P (TREE_TYPE (result)))
+	{
+	  int idx = get_stridx (gimple_phi_arg_def (phi, 0));
+	  if (idx != 0)
+	    {
+	      unsigned int i, n = gimple_phi_num_args (phi);
+	      for (i = 1; i < n; i++)
+		if (idx != get_stridx (gimple_phi_arg_def (phi, i)))
+		  break;
+	      if (i == n)
+		VEC_replace (int, ssa_ver_to_stridx,
+			     SSA_NAME_VERSION (result), idx);
+	    }
+	}
+    }
+
+  /* Attempt to optimize individual statements.  */
+  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
+    if (strlen_optimize_stmt (&gsi))
+      gsi_next (&gsi);
+
+  bb->aux = stridx_to_strinfo;
+  if (VEC_length (strinfo, stridx_to_strinfo) && !strinfo_shared ())
+    VEC_replace (strinfo, stridx_to_strinfo, 0, (strinfo) bb);
+}
+
+/* Callback for walk_dominator_tree.  Free strinfo vector if it is
+   owned by the current bb, clear bb->aux.  */
+
+static void
+strlen_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+		    basic_block bb)
+{
+  if (bb->aux)
+    {
+      stridx_to_strinfo = (VEC(strinfo, heap) *) bb->aux;
+      if (VEC_length (strinfo, stridx_to_strinfo)
+	  && VEC_index (strinfo, stridx_to_strinfo, 0) == (strinfo) bb)
+	{
+	  unsigned int i;
+	  strinfo si;
+
+	  for (i = 1; VEC_iterate (strinfo, stridx_to_strinfo, i, si); ++i)
+	    free_strinfo (si);
+	  VEC_free (strinfo, heap, stridx_to_strinfo);
+	}
+      bb->aux = NULL;
+    }
+}
+
+/* Main entry point.  */
+
+static unsigned int
+tree_ssa_strlen (void)
+{
+  struct dom_walk_data walk_data;
+
+  VEC_safe_grow_cleared (int, heap, ssa_ver_to_stridx, num_ssa_names);
+  max_stridx = 1;
+  strinfo_pool = create_alloc_pool ("strinfo_struct pool",
+				    sizeof (struct strinfo_struct), 64);
+
+  calculate_dominance_info (CDI_DOMINATORS);
+
+  /* String length optimization is implemented as a walk of the dominator
+     tree and a forward walk of statements within each block.  */
+  walk_data.dom_direction = CDI_DOMINATORS;
+  walk_data.initialize_block_local_data = NULL;
+  walk_data.before_dom_children = strlen_enter_block;
+  walk_data.after_dom_children = strlen_leave_block;
+  walk_data.block_local_data_size = 0;
+  walk_data.global_data = NULL;
+
+  /* Initialize the dominator walker.  */
+  init_walk_dominator_tree (&walk_data);
+
+  /* Recursively walk the dominator tree.  */
+  walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
+
+  /* Finalize the dominator walker.  */
+  fini_walk_dominator_tree (&walk_data);
+
+  VEC_free (int, heap, ssa_ver_to_stridx);
+  free_alloc_pool (strinfo_pool);
+  if (decl_to_stridxlist_htab)
+    {
+      obstack_free (&stridx_obstack, NULL);
+      htab_delete (decl_to_stridxlist_htab);
+      decl_to_stridxlist_htab = NULL;
+    }
+  laststmt.stmt = NULL;
+  laststmt.len = NULL_TREE;
+  laststmt.stridx = 0;
+
+  return 0;
+}
+
+static bool
+gate_strlen (void)
+{
+  return flag_optimize_strlen != 0;
+}
+
+struct gimple_opt_pass pass_strlen =
+{
+ {
+  GIMPLE_PASS,
+  "strlen",			/* name */
+  gate_strlen,			/* gate */
+  tree_ssa_strlen,		/* execute */
+  NULL,				/* sub */
+  NULL,				/* next */
+  0,				/* static_pass_number */
+  TV_TREE_STRLEN,		/* tv_id */
+  PROP_cfg | PROP_ssa,		/* properties_required */
+  0,				/* properties_provided */
+  0,				/* properties_destroyed */
+  0,				/* todo_flags_start */
+  TODO_ggc_collect
+    | TODO_verify_ssa		/* todo_flags_finish */
+ }
+};