1 /* String length optimization
2 Copyright (C) 2011 Free Software Foundation, Inc.
3 Contributed by Jakub Jelinek <jakub@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
24 #include "tree-flow.h"
25 #include "tree-pass.h"
27 #include "alloc-pool.h"
28 #include "tree-ssa-propagate.h"
29 #include "gimple-pretty-print.h"
32 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
33 is an index into strinfo vector, negative value stands for
34 string length of a string literal (~strlen). */
35 static VEC (int, heap) *ssa_ver_to_stridx;
37 /* Number of currently active string indexes plus one. */
38 static int max_stridx;
40 /* String information record. */
41 typedef struct strinfo_struct
43 /* String length of this string. */
45 /* Any of the corresponding pointers for querying alias oracle. */
47 /* Statement for delayed length computation. */
49 /* Pointer to '\0' if known, if NULL, it can be computed as
52 /* Reference count. Any changes to strinfo entry possibly shared
53 with dominating basic blocks need unshare_strinfo first, except
54 for dont_invalidate which affects only the immediately next
57 /* Copy of index. get_strinfo (si->idx) should return si; */
59 /* These 3 fields are for chaining related string pointers together.
61 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
62 strcpy (c, d); e = c + dl;
63 strinfo(a) -> strinfo(c) -> strinfo(e)
64 All have ->first field equal to strinfo(a)->idx and are doubly
65 chained through prev/next fields. The later strinfos are required
66 to point into the same string with zero or more bytes after
67 the previous pointer and all bytes in between the two pointers
68 must be non-zero. Functions like strcpy or memcpy are supposed
69 to adjust all previous strinfo lengths, but not following strinfo
70 lengths (those are uncertain, usually invalidated during
71 maybe_invalidate, except when the alias oracle knows better).
72 Functions like strcat on the other side adjust the whole
73 related strinfo chain.
74 They are updated lazily, so to use the chain the same first fields
75 and si->prev->next == si->idx needs to be verified. */
79 /* A flag whether the string is known to be written in the current
82 /* A flag for the next maybe_invalidate that this strinfo shouldn't
83 be invalidated. Always cleared by maybe_invalidate. */
87 DEF_VEC_ALLOC_P(strinfo,heap);
89 /* Pool for allocating strinfo_struct entries. */
90 static alloc_pool strinfo_pool;
92 /* Vector mapping positive string indexes to strinfo, for the
93 current basic block. The first pointer in the vector is special,
94 it is either NULL, meaning the vector isn't shared, or it is
95 a basic block pointer to the owner basic_block if shared.
96 If some other bb wants to modify the vector, the vector needs
97 to be unshared first, and only the owner bb is supposed to free it. */
98 static VEC(strinfo, heap) *stridx_to_strinfo;
100 /* One OFFSET->IDX mapping. */
103 struct stridxlist *next;
104 HOST_WIDE_INT offset;
108 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
109 struct decl_stridxlist_map
111 struct tree_map_base base;
112 struct stridxlist list;
115 /* Hash table for mapping decls to a chained list of offset -> idx
117 static htab_t decl_to_stridxlist_htab;
119 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
120 static struct obstack stridx_obstack;
122 /* Last memcpy statement if it could be adjusted if the trailing
123 '\0' written is immediately overwritten, or
124 *x = '\0' store that could be removed if it is immediately overwritten. */
125 struct laststmt_struct
132 /* Hash a from tree in a decl_stridxlist_map. */
135 decl_to_stridxlist_hash (const void *item)
137 return DECL_UID (((const struct decl_stridxlist_map *) item)->base.from);
140 /* Helper function for get_stridx. */
143 get_addr_stridx (tree exp)
146 struct decl_stridxlist_map ent, *e;
147 struct stridxlist *list;
150 if (decl_to_stridxlist_htab == NULL)
153 base = get_addr_base_and_unit_offset (exp, &off);
154 if (base == NULL || !DECL_P (base))
157 ent.base.from = base;
158 e = (struct decl_stridxlist_map *)
159 htab_find_with_hash (decl_to_stridxlist_htab, &ent, DECL_UID (base));
166 if (list->offset == off)
174 /* Return string index for EXP. */
177 get_stridx (tree exp)
181 if (TREE_CODE (exp) == SSA_NAME)
182 return VEC_index (int, ssa_ver_to_stridx, SSA_NAME_VERSION (exp));
184 if (TREE_CODE (exp) == ADDR_EXPR)
186 int idx = get_addr_stridx (TREE_OPERAND (exp, 0));
191 l = c_strlen (exp, 0);
193 && host_integerp (l, 1))
195 unsigned HOST_WIDE_INT len = tree_low_cst (l, 1);
196 if (len == (unsigned int) len
203 /* Return true if strinfo vector is shared with the immediate dominator. */
206 strinfo_shared (void)
208 return VEC_length (strinfo, stridx_to_strinfo)
209 && VEC_index (strinfo, stridx_to_strinfo, 0) != NULL;
212 /* Unshare strinfo vector that is shared with the immediate dominator. */
215 unshare_strinfo_vec (void)
220 gcc_assert (strinfo_shared ());
221 stridx_to_strinfo = VEC_copy (strinfo, heap, stridx_to_strinfo);
222 for (i = 1; VEC_iterate (strinfo, stridx_to_strinfo, i, si); ++i)
225 VEC_replace (strinfo, stridx_to_strinfo, 0, NULL);
228 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
229 Return a pointer to the location where the string index can
230 be stored (if 0) or is stored, or NULL if this can't be tracked. */
233 addr_stridxptr (tree exp)
236 struct decl_stridxlist_map ent;
237 struct stridxlist *list;
240 tree base = get_addr_base_and_unit_offset (exp, &off);
241 if (base == NULL_TREE || !DECL_P (base))
244 if (decl_to_stridxlist_htab == NULL)
246 decl_to_stridxlist_htab
247 = htab_create (64, decl_to_stridxlist_hash, tree_map_base_eq, NULL);
248 gcc_obstack_init (&stridx_obstack);
250 ent.base.from = base;
251 slot = htab_find_slot_with_hash (decl_to_stridxlist_htab, &ent,
252 DECL_UID (base), INSERT);
256 list = &((struct decl_stridxlist_map *)*slot)->list;
257 for (i = 0; i < 16; i++)
259 if (list->offset == off)
261 if (list->next == NULL)
266 list->next = XOBNEW (&stridx_obstack, struct stridxlist);
271 struct decl_stridxlist_map *e
272 = XOBNEW (&stridx_obstack, struct decl_stridxlist_map);
283 /* Create a new string index, or return 0 if reached limit. */
286 new_stridx (tree exp)
289 if (max_stridx >= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS))
291 if (TREE_CODE (exp) == SSA_NAME)
293 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp))
296 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (exp), idx);
299 if (TREE_CODE (exp) == ADDR_EXPR)
301 int *pidx = addr_stridxptr (TREE_OPERAND (exp, 0));
304 gcc_assert (*pidx == 0);
305 *pidx = max_stridx++;
312 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
315 new_addr_stridx (tree exp)
318 if (max_stridx >= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS))
320 pidx = addr_stridxptr (exp);
323 gcc_assert (*pidx == 0);
324 *pidx = max_stridx++;
330 /* Create a new strinfo. */
333 new_strinfo (tree ptr, int idx, tree length)
335 strinfo si = (strinfo) pool_alloc (strinfo_pool);
339 si->endptr = NULL_TREE;
345 si->writable = false;
346 si->dont_invalidate = false;
350 /* Decrease strinfo refcount and free it if not referenced anymore. */
353 free_strinfo (strinfo si)
355 if (si && --si->refcount == 0)
356 pool_free (strinfo_pool, si);
359 /* Return strinfo vector entry IDX. */
361 static inline strinfo
362 get_strinfo (int idx)
364 if (VEC_length (strinfo, stridx_to_strinfo) <= (unsigned int) idx)
366 return VEC_index (strinfo, stridx_to_strinfo, idx);
369 /* Set strinfo in the vector entry IDX to SI. */
372 set_strinfo (int idx, strinfo si)
374 if (VEC_length (strinfo, stridx_to_strinfo) && VEC_index (strinfo, stridx_to_strinfo, 0))
375 unshare_strinfo_vec ();
376 if (VEC_length (strinfo, stridx_to_strinfo) <= (unsigned int) idx)
377 VEC_safe_grow_cleared (strinfo, heap, stridx_to_strinfo, idx + 1);
378 VEC_replace (strinfo, stridx_to_strinfo, idx, si);
381 /* Return string length, or NULL if it can't be computed. */
384 get_string_length (strinfo si)
391 gimple stmt = si->stmt, lenstmt;
392 tree callee, lhs, lhs_var, fn, tem;
394 gimple_stmt_iterator gsi;
396 gcc_assert (is_gimple_call (stmt));
397 callee = gimple_call_fndecl (stmt);
398 gcc_assert (callee && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL);
399 lhs = gimple_call_lhs (stmt);
400 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY));
401 /* unshare_strinfo is intentionally not called here. The (delayed)
402 transformation of strcpy or strcat into stpcpy is done at the place
403 of the former strcpy/strcat call and so can affect all the strinfos
404 with the same stmt. If they were unshared before and transformation
405 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
406 just compute the right length. */
407 switch (DECL_FUNCTION_CODE (callee))
409 case BUILT_IN_STRCAT:
410 case BUILT_IN_STRCAT_CHK:
411 gsi = gsi_for_stmt (stmt);
412 fn = builtin_decl_implicit (BUILT_IN_STRLEN);
413 gcc_assert (lhs == NULL_TREE);
414 lhs_var = create_tmp_var (TREE_TYPE (TREE_TYPE (fn)), NULL);
415 add_referenced_var (lhs_var);
416 tem = unshare_expr (gimple_call_arg (stmt, 0));
417 lenstmt = gimple_build_call (fn, 1, tem);
418 lhs = make_ssa_name (lhs_var, lenstmt);
419 gimple_call_set_lhs (lenstmt, lhs);
420 gimple_set_vuse (lenstmt, gimple_vuse (stmt));
421 gsi_insert_before (&gsi, lenstmt, GSI_SAME_STMT);
422 lhs_var = create_tmp_var (TREE_TYPE (gimple_call_arg (stmt, 0)),
424 add_referenced_var (lhs_var);
425 tem = gimple_call_arg (stmt, 0);
427 = gimple_build_assign_with_ops (POINTER_PLUS_EXPR,
428 make_ssa_name (lhs_var, NULL),
430 gsi_insert_before (&gsi, lenstmt, GSI_SAME_STMT);
431 gimple_call_set_arg (stmt, 0, gimple_assign_lhs (lenstmt));
434 case BUILT_IN_STRCPY:
435 case BUILT_IN_STRCPY_CHK:
436 if (gimple_call_num_args (stmt) == 2)
437 fn = builtin_decl_implicit (BUILT_IN_STPCPY);
439 fn = builtin_decl_explicit (BUILT_IN_STPCPY_CHK);
440 gcc_assert (lhs == NULL_TREE);
441 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
443 fprintf (dump_file, "Optimizing: ");
444 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
446 gimple_call_set_fndecl (stmt, fn);
447 lhs_var = create_tmp_var (TREE_TYPE (TREE_TYPE (fn)), NULL);
448 add_referenced_var (lhs_var);
449 lhs = make_ssa_name (lhs_var, stmt);
450 gimple_call_set_lhs (stmt, lhs);
452 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
454 fprintf (dump_file, "into: ");
455 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
458 case BUILT_IN_STPCPY:
459 case BUILT_IN_STPCPY_CHK:
460 gcc_assert (lhs != NULL_TREE);
461 loc = gimple_location (stmt);
464 lhs = fold_convert_loc (loc, size_type_node, lhs);
465 si->length = fold_convert_loc (loc, size_type_node, si->ptr);
466 si->length = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
478 /* Invalidate string length information for strings whose length
479 might change due to stores in stmt. */
482 maybe_invalidate (gimple stmt)
486 bool nonempty = false;
488 for (i = 1; VEC_iterate (strinfo, stridx_to_strinfo, i, si); ++i)
491 if (!si->dont_invalidate)
494 ao_ref_init_from_ptr_and_size (&r, si->ptr, NULL_TREE);
495 if (stmt_may_clobber_ref_p_1 (stmt, &r))
497 set_strinfo (i, NULL);
502 si->dont_invalidate = false;
508 /* Unshare strinfo record SI, if it has recount > 1 or
509 if stridx_to_strinfo vector is shared with some other
513 unshare_strinfo (strinfo si)
517 if (si->refcount == 1 && !strinfo_shared ())
520 nsi = new_strinfo (si->ptr, si->idx, si->length);
521 nsi->stmt = si->stmt;
522 nsi->endptr = si->endptr;
523 nsi->first = si->first;
524 nsi->prev = si->prev;
525 nsi->next = si->next;
526 nsi->writable = si->writable;
527 set_strinfo (si->idx, nsi);
532 /* Return first strinfo in the related strinfo chain
533 if all strinfos in between belong to the chain, otherwise
537 verify_related_strinfos (strinfo origsi)
539 strinfo si = origsi, psi;
541 if (origsi->first == 0)
543 for (; si->prev; si = psi)
545 if (si->first != origsi->first)
547 psi = get_strinfo (si->prev);
550 if (psi->next != si->idx)
553 if (si->idx != si->first)
558 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
559 to a zero-length string and if possible chain it to a related strinfo
560 chain whose part is or might be CHAINSI. */
563 zero_length_string (tree ptr, strinfo chainsi)
567 gcc_checking_assert (TREE_CODE (ptr) == SSA_NAME
568 && get_stridx (ptr) == 0);
570 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr))
574 si = verify_related_strinfos (chainsi);
578 for (; chainsi->next; chainsi = si)
580 if (chainsi->endptr == NULL_TREE)
582 chainsi = unshare_strinfo (chainsi);
583 chainsi->endptr = ptr;
585 si = get_strinfo (chainsi->next);
587 || si->first != chainsi->first
588 || si->prev != chainsi->idx)
591 gcc_assert (chainsi->length || chainsi->stmt);
592 if (chainsi->endptr == NULL_TREE)
594 chainsi = unshare_strinfo (chainsi);
595 chainsi->endptr = ptr;
597 if (chainsi->length && integer_zerop (chainsi->length))
601 chainsi = unshare_strinfo (chainsi);
604 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (ptr),
609 else if (chainsi->first || chainsi->prev || chainsi->next)
611 chainsi = unshare_strinfo (chainsi);
617 idx = new_stridx (ptr);
620 si = new_strinfo (ptr, idx, build_int_cst (size_type_node, 0));
621 set_strinfo (idx, si);
625 chainsi = unshare_strinfo (chainsi);
626 if (chainsi->first == 0)
627 chainsi->first = chainsi->idx;
629 if (chainsi->endptr == NULL_TREE)
630 chainsi->endptr = ptr;
631 si->prev = chainsi->idx;
632 si->first = chainsi->first;
633 si->writable = chainsi->writable;
638 /* For strinfo ORIGSI whose length has been just updated
639 update also related strinfo lengths (add ADJ to each,
640 but don't adjust ORIGSI). */
643 adjust_related_strinfos (location_t loc, strinfo origsi, tree adj)
645 strinfo si = verify_related_strinfos (origsi);
658 si = unshare_strinfo (si);
661 tem = fold_convert_loc (loc, TREE_TYPE (si->length), adj);
662 si->length = fold_build2_loc (loc, PLUS_EXPR,
663 TREE_TYPE (si->length), si->length,
666 else if (si->stmt != NULL)
667 /* Delayed length computation is unaffected. */
672 si->endptr = NULL_TREE;
673 si->dont_invalidate = true;
677 nsi = get_strinfo (si->next);
679 || nsi->first != si->first
680 || nsi->prev != si->idx)
686 /* Find if there are other SSA_NAME pointers equal to PTR
687 for which we don't track their string lengths yet. If so, use
691 find_equal_ptrs (tree ptr, int idx)
693 if (TREE_CODE (ptr) != SSA_NAME)
697 gimple stmt = SSA_NAME_DEF_STMT (ptr);
698 if (!is_gimple_assign (stmt))
700 ptr = gimple_assign_rhs1 (stmt);
701 switch (gimple_assign_rhs_code (stmt))
706 if (!POINTER_TYPE_P (TREE_TYPE (ptr)))
708 if (TREE_CODE (ptr) == SSA_NAME)
710 if (TREE_CODE (ptr) != ADDR_EXPR)
715 int *pidx = addr_stridxptr (TREE_OPERAND (ptr, 0));
716 if (pidx != NULL && *pidx == 0)
724 /* We might find an endptr created in this pass. Grow the
725 vector in that case. */
726 if (VEC_length (int, ssa_ver_to_stridx) <= SSA_NAME_VERSION (ptr))
727 VEC_safe_grow_cleared (int, heap, ssa_ver_to_stridx, num_ssa_names);
729 if (VEC_index (int, ssa_ver_to_stridx, SSA_NAME_VERSION (ptr)) != 0)
731 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (ptr), idx);
735 /* If the last .MEM setter statement before STMT is
736 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
737 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
738 just memcpy (x, y, strlen (y)). SI must be the zero length
742 adjust_last_stmt (strinfo si, gimple stmt, bool is_strcat)
744 tree vuse, callee, len;
745 struct laststmt_struct last = laststmt;
746 strinfo lastsi, firstsi;
748 laststmt.stmt = NULL;
749 laststmt.len = NULL_TREE;
752 if (last.stmt == NULL)
755 vuse = gimple_vuse (stmt);
756 if (vuse == NULL_TREE
757 || SSA_NAME_DEF_STMT (vuse) != last.stmt
758 || !has_single_use (vuse))
761 gcc_assert (last.stridx > 0);
762 lastsi = get_strinfo (last.stridx);
768 if (lastsi->first == 0 || lastsi->first != si->first)
771 firstsi = verify_related_strinfos (si);
774 while (firstsi != lastsi)
777 if (firstsi->next == 0)
779 nextsi = get_strinfo (firstsi->next);
781 || nextsi->prev != firstsi->idx
782 || nextsi->first != si->first)
790 if (si->length == NULL_TREE || !integer_zerop (si->length))
794 if (is_gimple_assign (last.stmt))
796 gimple_stmt_iterator gsi;
798 if (!integer_zerop (gimple_assign_rhs1 (last.stmt)))
800 if (stmt_could_throw_p (last.stmt))
802 gsi = gsi_for_stmt (last.stmt);
803 unlink_stmt_vdef (last.stmt);
804 release_defs (last.stmt);
805 gsi_remove (&gsi, true);
809 if (!is_gimple_call (last.stmt))
811 callee = gimple_call_fndecl (last.stmt);
812 if (callee == NULL_TREE || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL)
815 switch (DECL_FUNCTION_CODE (callee))
817 case BUILT_IN_MEMCPY:
818 case BUILT_IN_MEMCPY_CHK:
824 len = gimple_call_arg (last.stmt, 2);
825 if (host_integerp (len, 1))
827 if (!host_integerp (last.len, 1)
828 || integer_zerop (len)
829 || (unsigned HOST_WIDE_INT) tree_low_cst (len, 1)
830 != (unsigned HOST_WIDE_INT) tree_low_cst (last.len, 1) + 1)
832 /* Don't adjust the length if it is divisible by 4, it is more efficient
833 to store the extra '\0' in that case. */
834 if ((((unsigned HOST_WIDE_INT) tree_low_cst (len, 1)) & 3) == 0)
837 else if (TREE_CODE (len) == SSA_NAME)
839 gimple def_stmt = SSA_NAME_DEF_STMT (len);
840 if (!is_gimple_assign (def_stmt)
841 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
842 || gimple_assign_rhs1 (def_stmt) != last.len
843 || !integer_onep (gimple_assign_rhs2 (def_stmt)))
849 gimple_call_set_arg (last.stmt, 2, last.len);
850 update_stmt (last.stmt);
853 /* Handle a strlen call. If strlen of the argument is known, replace
854 the strlen call with the known value, otherwise remember that strlen
855 of the argument is stored in the lhs SSA_NAME. */
858 handle_builtin_strlen (gimple_stmt_iterator *gsi)
862 gimple stmt = gsi_stmt (*gsi);
863 tree lhs = gimple_call_lhs (stmt);
865 if (lhs == NULL_TREE)
868 src = gimple_call_arg (stmt, 0);
869 idx = get_stridx (src);
876 rhs = build_int_cst (TREE_TYPE (lhs), ~idx);
880 si = get_strinfo (idx);
882 rhs = get_string_length (si);
884 if (rhs != NULL_TREE)
886 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
888 fprintf (dump_file, "Optimizing: ");
889 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
891 rhs = unshare_expr (rhs);
892 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
893 rhs = fold_convert_loc (gimple_location (stmt),
894 TREE_TYPE (lhs), rhs);
895 if (!update_call_from_tree (gsi, rhs))
896 gimplify_and_update_call_from_tree (gsi, rhs);
897 stmt = gsi_stmt (*gsi);
899 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
901 fprintf (dump_file, "into: ");
902 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
905 && TREE_CODE (si->length) != SSA_NAME
906 && TREE_CODE (si->length) != INTEGER_CST
907 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
909 si = unshare_strinfo (si);
915 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
918 idx = new_stridx (src);
919 else if (get_strinfo (idx) != NULL)
923 strinfo si = new_strinfo (src, idx, lhs);
924 set_strinfo (idx, si);
925 find_equal_ptrs (src, idx);
929 /* Handle a strchr call. If strlen of the first argument is known, replace
930 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
931 that lhs of the call is endptr and strlen of the argument is endptr - x. */
934 handle_builtin_strchr (gimple_stmt_iterator *gsi)
938 gimple stmt = gsi_stmt (*gsi);
939 tree lhs = gimple_call_lhs (stmt);
941 if (lhs == NULL_TREE)
944 if (!integer_zerop (gimple_call_arg (stmt, 1)))
947 src = gimple_call_arg (stmt, 0);
948 idx = get_stridx (src);
955 rhs = build_int_cst (size_type_node, ~idx);
959 si = get_strinfo (idx);
961 rhs = get_string_length (si);
963 if (rhs != NULL_TREE)
965 location_t loc = gimple_location (stmt);
967 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
969 fprintf (dump_file, "Optimizing: ");
970 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
972 if (si != NULL && si->endptr != NULL_TREE)
974 rhs = unshare_expr (si->endptr);
975 if (!useless_type_conversion_p (TREE_TYPE (lhs),
977 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
981 rhs = fold_convert_loc (loc, sizetype, unshare_expr (rhs));
982 rhs = fold_build2_loc (loc, POINTER_PLUS_EXPR,
983 TREE_TYPE (src), src, rhs);
984 if (!useless_type_conversion_p (TREE_TYPE (lhs),
986 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
988 if (!update_call_from_tree (gsi, rhs))
989 gimplify_and_update_call_from_tree (gsi, rhs);
990 stmt = gsi_stmt (*gsi);
992 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
994 fprintf (dump_file, "into: ");
995 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
998 && si->endptr == NULL_TREE
999 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1001 si = unshare_strinfo (si);
1004 zero_length_string (lhs, si);
1008 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1010 if (TREE_CODE (src) != SSA_NAME || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src))
1013 idx = new_stridx (src);
1014 else if (get_strinfo (idx) != NULL)
1016 zero_length_string (lhs, NULL);
1021 location_t loc = gimple_location (stmt);
1022 tree lhsu = fold_convert_loc (loc, size_type_node, lhs);
1023 tree srcu = fold_convert_loc (loc, size_type_node, src);
1024 tree length = fold_build2_loc (loc, MINUS_EXPR,
1025 size_type_node, lhsu, srcu);
1026 strinfo si = new_strinfo (src, idx, length);
1028 set_strinfo (idx, si);
1029 find_equal_ptrs (src, idx);
1030 zero_length_string (lhs, si);
1034 zero_length_string (lhs, NULL);
1037 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1038 If strlen of the second argument is known, strlen of the first argument
1039 is the same after this call. Furthermore, attempt to convert it to
1043 handle_builtin_strcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1046 tree src, dst, srclen, len, lhs, args, type, fn, oldlen;
1048 gimple stmt = gsi_stmt (*gsi);
1049 strinfo si, dsi, olddsi, zsi;
1052 src = gimple_call_arg (stmt, 1);
1053 dst = gimple_call_arg (stmt, 0);
1054 lhs = gimple_call_lhs (stmt);
1055 idx = get_stridx (src);
1058 si = get_strinfo (idx);
1060 didx = get_stridx (dst);
1064 olddsi = get_strinfo (didx);
1069 adjust_last_stmt (olddsi, stmt, false);
1073 srclen = get_string_length (si);
1075 srclen = build_int_cst (size_type_node, ~idx);
1077 loc = gimple_location (stmt);
1078 if (srclen == NULL_TREE)
1081 case BUILT_IN_STRCPY:
1082 case BUILT_IN_STRCPY_CHK:
1083 if (lhs != NULL_TREE || !builtin_decl_implicit_p (BUILT_IN_STPCPY))
1086 case BUILT_IN_STPCPY:
1087 case BUILT_IN_STPCPY_CHK:
1088 if (lhs == NULL_TREE)
1092 tree lhsuint = fold_convert_loc (loc, size_type_node, lhs);
1093 srclen = fold_convert_loc (loc, size_type_node, dst);
1094 srclen = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
1104 didx = new_stridx (dst);
1110 oldlen = olddsi->length;
1111 dsi = unshare_strinfo (olddsi);
1112 dsi->length = srclen;
1113 /* Break the chain, so adjust_related_strinfo on later pointers in
1114 the chain won't adjust this one anymore. */
1117 dsi->endptr = NULL_TREE;
1121 dsi = new_strinfo (dst, didx, srclen);
1122 set_strinfo (didx, dsi);
1123 find_equal_ptrs (dst, didx);
1125 dsi->writable = true;
1126 dsi->dont_invalidate = true;
1128 if (dsi->length == NULL_TREE)
1132 /* If string length of src is unknown, use delayed length
1133 computation. If string lenth of dst will be needed, it
1134 can be computed by transforming this strcpy call into
1135 stpcpy and subtracting dst from the return value. */
1137 /* Look for earlier strings whose length could be determined if
1138 this strcpy is turned into an stpcpy. */
1140 if (dsi->prev != 0 && (chainsi = verify_related_strinfos (dsi)) != NULL)
1142 for (; chainsi && chainsi != dsi; chainsi = get_strinfo (chainsi->next))
1144 /* When setting a stmt for delayed length computation
1145 prevent all strinfos through dsi from being
1147 chainsi = unshare_strinfo (chainsi);
1148 chainsi->stmt = stmt;
1149 chainsi->length = NULL_TREE;
1150 chainsi->endptr = NULL_TREE;
1151 chainsi->dont_invalidate = true;
1160 tree adj = NULL_TREE;
1161 if (oldlen == NULL_TREE)
1163 else if (integer_zerop (oldlen))
1165 else if (TREE_CODE (oldlen) == INTEGER_CST
1166 || TREE_CODE (srclen) == INTEGER_CST)
1167 adj = fold_build2_loc (loc, MINUS_EXPR,
1168 TREE_TYPE (srclen), srclen,
1169 fold_convert_loc (loc, TREE_TYPE (srclen),
1171 if (adj != NULL_TREE)
1172 adjust_related_strinfos (loc, dsi, adj);
1176 /* strcpy src may not overlap dst, so src doesn't need to be
1177 invalidated either. */
1179 si->dont_invalidate = true;
1185 case BUILT_IN_STRCPY:
1186 fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
1188 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs), didx);
1190 case BUILT_IN_STRCPY_CHK:
1191 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK);
1193 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs), didx);
1195 case BUILT_IN_STPCPY:
1196 /* This would need adjustment of the lhs (subtract one),
1197 or detection that the trailing '\0' doesn't need to be
1198 written, if it will be immediately overwritten.
1199 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1203 zsi = zero_length_string (lhs, dsi);
1206 case BUILT_IN_STPCPY_CHK:
1207 /* This would need adjustment of the lhs (subtract one),
1208 or detection that the trailing '\0' doesn't need to be
1209 written, if it will be immediately overwritten.
1210 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1214 zsi = zero_length_string (lhs, dsi);
1221 zsi->dont_invalidate = true;
1223 if (fn == NULL_TREE)
1226 args = TYPE_ARG_TYPES (TREE_TYPE (fn));
1227 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
1229 len = fold_convert_loc (loc, type, unshare_expr (srclen));
1230 len = fold_build2_loc (loc, PLUS_EXPR, type, len, build_int_cst (type, 1));
1231 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
1233 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1235 fprintf (dump_file, "Optimizing: ");
1236 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1238 if (gimple_call_num_args (stmt) == 2)
1239 success = update_gimple_call (gsi, fn, 3, dst, src, len);
1241 success = update_gimple_call (gsi, fn, 4, dst, src, len,
1242 gimple_call_arg (stmt, 2));
1245 stmt = gsi_stmt (*gsi);
1247 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1249 fprintf (dump_file, "into: ");
1250 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1252 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1253 laststmt.stmt = stmt;
1254 laststmt.len = srclen;
1255 laststmt.stridx = dsi->idx;
1257 else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1258 fprintf (dump_file, "not possible.\n");
1261 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
1262 If strlen of the second argument is known and length of the third argument
1263 is that plus one, strlen of the first argument is the same after this
1267 handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1270 tree src, dst, len, lhs, oldlen, newlen;
1271 gimple stmt = gsi_stmt (*gsi);
1272 strinfo si, dsi, olddsi;
1274 len = gimple_call_arg (stmt, 2);
1275 src = gimple_call_arg (stmt, 1);
1276 dst = gimple_call_arg (stmt, 0);
1277 idx = get_stridx (src);
1281 didx = get_stridx (dst);
1284 olddsi = get_strinfo (didx);
1289 && host_integerp (len, 1)
1290 && !integer_zerop (len))
1291 adjust_last_stmt (olddsi, stmt, false);
1297 /* Handle memcpy (x, y, l) where l is strlen (y) + 1. */
1298 si = get_strinfo (idx);
1299 if (si == NULL || si->length == NULL_TREE)
1301 if (TREE_CODE (len) != SSA_NAME)
1303 def_stmt = SSA_NAME_DEF_STMT (len);
1304 if (!is_gimple_assign (def_stmt)
1305 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
1306 || gimple_assign_rhs1 (def_stmt) != si->length
1307 || !integer_onep (gimple_assign_rhs2 (def_stmt)))
1313 /* Handle memcpy (x, "abcd", 5) or
1314 memcpy (x, "abc\0uvw", 7). */
1315 if (!host_integerp (len, 1)
1316 || (unsigned HOST_WIDE_INT) tree_low_cst (len, 1)
1317 <= (unsigned HOST_WIDE_INT) ~idx)
1321 if (olddsi != NULL && TREE_CODE (len) == SSA_NAME)
1322 adjust_last_stmt (olddsi, stmt, false);
1326 didx = new_stridx (dst);
1331 newlen = si->length;
1333 newlen = build_int_cst (size_type_node, ~idx);
1337 dsi = unshare_strinfo (olddsi);
1338 oldlen = olddsi->length;
1339 dsi->length = newlen;
1340 /* Break the chain, so adjust_related_strinfo on later pointers in
1341 the chain won't adjust this one anymore. */
1344 dsi->endptr = NULL_TREE;
1348 dsi = new_strinfo (dst, didx, newlen);
1349 set_strinfo (didx, dsi);
1350 find_equal_ptrs (dst, didx);
1352 dsi->writable = true;
1353 dsi->dont_invalidate = true;
1356 tree adj = NULL_TREE;
1357 location_t loc = gimple_location (stmt);
1358 if (oldlen == NULL_TREE)
1360 else if (integer_zerop (oldlen))
1362 else if (TREE_CODE (oldlen) == INTEGER_CST
1363 || TREE_CODE (dsi->length) == INTEGER_CST)
1364 adj = fold_build2_loc (loc, MINUS_EXPR,
1365 TREE_TYPE (dsi->length), dsi->length,
1366 fold_convert_loc (loc, TREE_TYPE (dsi->length),
1368 if (adj != NULL_TREE)
1369 adjust_related_strinfos (loc, dsi, adj);
1373 /* memcpy src may not overlap dst, so src doesn't need to be
1374 invalidated either. */
1376 si->dont_invalidate = true;
1378 lhs = gimple_call_lhs (stmt);
1381 case BUILT_IN_MEMCPY:
1382 case BUILT_IN_MEMCPY_CHK:
1383 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1384 laststmt.stmt = stmt;
1385 laststmt.len = dsi->length;
1386 laststmt.stridx = dsi->idx;
1388 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs), didx);
1390 case BUILT_IN_MEMPCPY:
1391 case BUILT_IN_MEMPCPY_CHK:
1398 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
1399 If strlen of the second argument is known, strlen of the first argument
1400 is increased by the length of the second argument. Furthermore, attempt
1401 to convert it to memcpy/strcpy if the length of the first argument
1405 handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1408 tree src, dst, srclen, dstlen, len, lhs, args, type, fn, objsz, endptr;
1410 gimple stmt = gsi_stmt (*gsi);
1414 src = gimple_call_arg (stmt, 1);
1415 dst = gimple_call_arg (stmt, 0);
1416 lhs = gimple_call_lhs (stmt);
1418 didx = get_stridx (dst);
1424 dsi = get_strinfo (didx);
1425 if (dsi == NULL || get_string_length (dsi) == NULL_TREE)
1427 /* strcat (p, q) can be transformed into
1428 tmp = p + strlen (p); endptr = strpcpy (tmp, q);
1429 with length endptr - p if we need to compute the length
1430 later on. Don't do this transformation if we don't need
1432 if (builtin_decl_implicit_p (BUILT_IN_STPCPY) && lhs == NULL_TREE)
1436 didx = new_stridx (dst);
1442 dsi = new_strinfo (dst, didx, NULL_TREE);
1443 set_strinfo (didx, dsi);
1444 find_equal_ptrs (dst, didx);
1448 dsi = unshare_strinfo (dsi);
1449 dsi->length = NULL_TREE;
1451 dsi->endptr = NULL_TREE;
1453 dsi->writable = true;
1455 dsi->dont_invalidate = true;
1462 idx = get_stridx (src);
1464 srclen = build_int_cst (size_type_node, ~idx);
1467 si = get_strinfo (idx);
1469 srclen = get_string_length (si);
1472 loc = gimple_location (stmt);
1473 dstlen = dsi->length;
1474 endptr = dsi->endptr;
1476 dsi = unshare_strinfo (dsi);
1477 dsi->endptr = NULL_TREE;
1479 dsi->writable = true;
1481 if (srclen != NULL_TREE)
1483 dsi->length = fold_build2_loc (loc, PLUS_EXPR, TREE_TYPE (dsi->length),
1484 dsi->length, srclen);
1485 adjust_related_strinfos (loc, dsi, srclen);
1486 dsi->dont_invalidate = true;
1491 if (lhs == NULL_TREE && builtin_decl_implicit_p (BUILT_IN_STPCPY))
1492 dsi->dont_invalidate = true;
1496 /* strcat src may not overlap dst, so src doesn't need to be
1497 invalidated either. */
1498 si->dont_invalidate = true;
1500 /* For now. Could remove the lhs from the call and add
1501 lhs = dst; afterwards. */
1509 case BUILT_IN_STRCAT:
1510 if (srclen != NULL_TREE)
1511 fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
1513 fn = builtin_decl_implicit (BUILT_IN_STRCPY);
1515 case BUILT_IN_STRCAT_CHK:
1516 if (srclen != NULL_TREE)
1517 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK);
1519 fn = builtin_decl_explicit (BUILT_IN_STRCPY_CHK);
1520 objsz = gimple_call_arg (stmt, 2);
1526 if (fn == NULL_TREE)
1530 if (srclen != NULL_TREE)
1532 args = TYPE_ARG_TYPES (TREE_TYPE (fn));
1533 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
1535 len = fold_convert_loc (loc, type, unshare_expr (srclen));
1536 len = fold_build2_loc (loc, PLUS_EXPR, type, len,
1537 build_int_cst (type, 1));
1538 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
1542 dst = fold_convert_loc (loc, TREE_TYPE (dst), unshare_expr (endptr));
1544 dst = fold_build2_loc (loc, POINTER_PLUS_EXPR,
1545 TREE_TYPE (dst), unshare_expr (dst),
1546 fold_convert_loc (loc, sizetype,
1547 unshare_expr (dstlen)));
1548 dst = force_gimple_operand_gsi (gsi, dst, true, NULL_TREE, true,
1550 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1552 fprintf (dump_file, "Optimizing: ");
1553 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1555 if (srclen != NULL_TREE)
1556 success = update_gimple_call (gsi, fn, 3 + (objsz != NULL_TREE),
1557 dst, src, len, objsz);
1559 success = update_gimple_call (gsi, fn, 2 + (objsz != NULL_TREE),
1563 stmt = gsi_stmt (*gsi);
1565 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1567 fprintf (dump_file, "into: ");
1568 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1570 /* If srclen == NULL, note that current string length can be
1571 computed by transforming this strcpy into stpcpy. */
1572 if (srclen == NULL_TREE && dsi->dont_invalidate)
1574 adjust_last_stmt (dsi, stmt, true);
1575 if (srclen != NULL_TREE)
1577 laststmt.stmt = stmt;
1578 laststmt.len = srclen;
1579 laststmt.stridx = dsi->idx;
1582 else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1583 fprintf (dump_file, "not possible.\n");
1586 /* Handle a POINTER_PLUS_EXPR statement.
1587 For p = "abcd" + 2; compute associated length, or if
1588 p = q + off is pointing to a '\0' character of a string, call
1589 zero_length_string on it. */
1592 handle_pointer_plus (gimple_stmt_iterator *gsi)
1594 gimple stmt = gsi_stmt (*gsi);
1595 tree lhs = gimple_assign_lhs (stmt), off;
1596 int idx = get_stridx (gimple_assign_rhs1 (stmt));
1604 tree off = gimple_assign_rhs2 (stmt);
1605 if (host_integerp (off, 1)
1606 && (unsigned HOST_WIDE_INT) tree_low_cst (off, 1)
1607 <= (unsigned HOST_WIDE_INT) ~idx)
1608 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs),
1609 ~(~idx - (int) tree_low_cst (off, 1)));
1613 si = get_strinfo (idx);
1614 if (si == NULL || si->length == NULL_TREE)
1617 off = gimple_assign_rhs2 (stmt);
1619 if (operand_equal_p (si->length, off, 0))
1620 zsi = zero_length_string (lhs, si);
1621 else if (TREE_CODE (off) == SSA_NAME)
1623 gimple def_stmt = SSA_NAME_DEF_STMT (off);
1624 if (gimple_assign_single_p (def_stmt)
1625 && operand_equal_p (si->length, gimple_assign_rhs1 (def_stmt), 0))
1626 zsi = zero_length_string (lhs, si);
1629 && si->endptr != NULL_TREE
1630 && si->endptr != lhs
1631 && TREE_CODE (si->endptr) == SSA_NAME)
1633 enum tree_code rhs_code
1634 = useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (si->endptr))
1635 ? SSA_NAME : NOP_EXPR;
1636 gimple_assign_set_rhs_with_ops (gsi, rhs_code, si->endptr, NULL_TREE);
1637 gcc_assert (gsi_stmt (*gsi) == stmt);
1642 /* Handle a single character store. */
1645 handle_char_store (gimple_stmt_iterator *gsi)
1649 gimple stmt = gsi_stmt (*gsi);
1650 tree ssaname = NULL_TREE, lhs = gimple_assign_lhs (stmt);
1652 if (TREE_CODE (lhs) == MEM_REF
1653 && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME)
1655 if (integer_zerop (TREE_OPERAND (lhs, 1)))
1657 ssaname = TREE_OPERAND (lhs, 0);
1658 idx = get_stridx (ssaname);
1662 idx = get_addr_stridx (lhs);
1666 si = get_strinfo (idx);
1667 if (si != NULL && si->length != NULL_TREE && integer_zerop (si->length))
1669 if (initializer_zerop (gimple_assign_rhs1 (stmt)))
1671 /* When storing '\0', the store can be removed
1672 if we know it has been stored in the current function. */
1673 if (!stmt_could_throw_p (stmt) && si->writable)
1675 unlink_stmt_vdef (stmt);
1676 release_defs (stmt);
1677 gsi_remove (gsi, true);
1682 si->writable = true;
1683 si->dont_invalidate = true;
1687 /* Otherwise this statement overwrites the '\0' with
1688 something, if the previous stmt was a memcpy,
1689 its length may be decreased. */
1690 adjust_last_stmt (si, stmt, false);
1692 else if (si != NULL)
1694 si = unshare_strinfo (si);
1695 si->length = build_int_cst (size_type_node, 0);
1701 si->writable = true;
1702 if (ssaname && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname))
1703 si->endptr = ssaname;
1704 si->dont_invalidate = true;
1707 else if (idx == 0 && initializer_zerop (gimple_assign_rhs1 (stmt)))
1711 si = zero_length_string (ssaname, NULL);
1713 si->dont_invalidate = true;
1717 int idx = new_addr_stridx (lhs);
1720 si = new_strinfo (build_fold_addr_expr (lhs), idx,
1721 build_int_cst (size_type_node, 0));
1722 set_strinfo (idx, si);
1723 si->dont_invalidate = true;
1727 si->writable = true;
1730 if (si != NULL && initializer_zerop (gimple_assign_rhs1 (stmt)))
1732 /* Allow adjust_last_stmt to remove it if the stored '\0'
1733 is immediately overwritten. */
1734 laststmt.stmt = stmt;
1735 laststmt.len = build_int_cst (size_type_node, 1);
1736 laststmt.stridx = si->idx;
1741 /* Attempt to optimize a single statement at *GSI using string length
1745 strlen_optimize_stmt (gimple_stmt_iterator *gsi)
1747 gimple stmt = gsi_stmt (*gsi);
1749 if (is_gimple_call (stmt))
1751 tree callee = gimple_call_fndecl (stmt);
1752 if (callee && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
1753 switch (DECL_FUNCTION_CODE (callee))
1755 case BUILT_IN_STRLEN:
1756 handle_builtin_strlen (gsi);
1758 case BUILT_IN_STRCHR:
1759 handle_builtin_strchr (gsi);
1761 case BUILT_IN_STRCPY:
1762 case BUILT_IN_STRCPY_CHK:
1763 case BUILT_IN_STPCPY:
1764 case BUILT_IN_STPCPY_CHK:
1765 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee), gsi);
1767 case BUILT_IN_MEMCPY:
1768 case BUILT_IN_MEMCPY_CHK:
1769 case BUILT_IN_MEMPCPY:
1770 case BUILT_IN_MEMPCPY_CHK:
1771 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee), gsi);
1773 case BUILT_IN_STRCAT:
1774 case BUILT_IN_STRCAT_CHK:
1775 handle_builtin_strcat (DECL_FUNCTION_CODE (callee), gsi);
1781 else if (is_gimple_assign (stmt))
1783 tree lhs = gimple_assign_lhs (stmt);
1785 if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (lhs)))
1787 if (gimple_assign_single_p (stmt)
1788 || (gimple_assign_cast_p (stmt)
1789 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt)))))
1791 int idx = get_stridx (gimple_assign_rhs1 (stmt));
1792 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs),
1795 else if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
1796 handle_pointer_plus (gsi);
1798 else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs))
1800 tree type = TREE_TYPE (lhs);
1801 if (TREE_CODE (type) == ARRAY_TYPE)
1802 type = TREE_TYPE (type);
1803 if (TREE_CODE (type) == INTEGER_TYPE
1804 && TYPE_MODE (type) == TYPE_MODE (char_type_node)
1805 && TYPE_PRECISION (type) == TYPE_PRECISION (char_type_node))
1807 if (! handle_char_store (gsi))
1813 if (gimple_vdef (stmt))
1814 maybe_invalidate (stmt);
1818 /* Recursively call maybe_invalidate on stmts that might be executed
1819 in between dombb and current bb and that contain a vdef. Stop when
1820 *count stmts are inspected, or if the whole strinfo vector has
1821 been invalidated. */
1824 do_invalidate (basic_block dombb, gimple phi, bitmap visited, int *count)
1826 unsigned int i, n = gimple_phi_num_args (phi);
1828 for (i = 0; i < n; i++)
1830 tree vuse = gimple_phi_arg_def (phi, i);
1831 gimple stmt = SSA_NAME_DEF_STMT (vuse);
1832 basic_block bb = gimple_bb (stmt);
1835 || !bitmap_set_bit (visited, bb->index)
1836 || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
1840 if (gimple_code (stmt) == GIMPLE_PHI)
1842 do_invalidate (dombb, stmt, visited, count);
1849 if (!maybe_invalidate (stmt))
1854 vuse = gimple_vuse (stmt);
1855 stmt = SSA_NAME_DEF_STMT (vuse);
1856 if (gimple_bb (stmt) != bb)
1858 bb = gimple_bb (stmt);
1861 || !bitmap_set_bit (visited, bb->index)
1862 || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
1869 /* Callback for walk_dominator_tree. Attempt to optimize various
1870 string ops by remembering string lenths pointed by pointer SSA_NAMEs. */
1873 strlen_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1876 gimple_stmt_iterator gsi;
1877 basic_block dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
1880 stridx_to_strinfo = NULL;
1883 stridx_to_strinfo = (VEC(strinfo, heap) *) dombb->aux;
1884 if (stridx_to_strinfo)
1886 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1888 gimple phi = gsi_stmt (gsi);
1889 if (!is_gimple_reg (gimple_phi_result (phi)))
1891 bitmap visited = BITMAP_ALLOC (NULL);
1892 int count_vdef = 100;
1893 do_invalidate (dombb, phi, visited, &count_vdef);
1894 BITMAP_FREE (visited);
1901 /* If all PHI arguments have the same string index, the PHI result
1903 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1905 gimple phi = gsi_stmt (gsi);
1906 tree result = gimple_phi_result (phi);
1907 if (is_gimple_reg (result) && POINTER_TYPE_P (TREE_TYPE (result)))
1909 int idx = get_stridx (gimple_phi_arg_def (phi, 0));
1912 unsigned int i, n = gimple_phi_num_args (phi);
1913 for (i = 1; i < n; i++)
1914 if (idx != get_stridx (gimple_phi_arg_def (phi, i)))
1917 VEC_replace (int, ssa_ver_to_stridx,
1918 SSA_NAME_VERSION (result), idx);
1923 /* Attempt to optimize individual statements. */
1924 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
1925 if (strlen_optimize_stmt (&gsi))
1928 bb->aux = stridx_to_strinfo;
1929 if (VEC_length (strinfo, stridx_to_strinfo) && !strinfo_shared ())
1930 VEC_replace (strinfo, stridx_to_strinfo, 0, (strinfo) bb);
1933 /* Callback for walk_dominator_tree. Free strinfo vector if it is
1934 owned by the current bb, clear bb->aux. */
1937 strlen_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1942 stridx_to_strinfo = (VEC(strinfo, heap) *) bb->aux;
1943 if (VEC_length (strinfo, stridx_to_strinfo)
1944 && VEC_index (strinfo, stridx_to_strinfo, 0) == (strinfo) bb)
1949 for (i = 1; VEC_iterate (strinfo, stridx_to_strinfo, i, si); ++i)
1951 VEC_free (strinfo, heap, stridx_to_strinfo);
1957 /* Main entry point. */
1960 tree_ssa_strlen (void)
1962 struct dom_walk_data walk_data;
1964 VEC_safe_grow_cleared (int, heap, ssa_ver_to_stridx, num_ssa_names);
1966 strinfo_pool = create_alloc_pool ("strinfo_struct pool",
1967 sizeof (struct strinfo_struct), 64);
1969 calculate_dominance_info (CDI_DOMINATORS);
1971 /* String length optimization is implemented as a walk of the dominator
1972 tree and a forward walk of statements within each block. */
1973 walk_data.dom_direction = CDI_DOMINATORS;
1974 walk_data.initialize_block_local_data = NULL;
1975 walk_data.before_dom_children = strlen_enter_block;
1976 walk_data.after_dom_children = strlen_leave_block;
1977 walk_data.block_local_data_size = 0;
1978 walk_data.global_data = NULL;
1980 /* Initialize the dominator walker. */
1981 init_walk_dominator_tree (&walk_data);
1983 /* Recursively walk the dominator tree. */
1984 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1986 /* Finalize the dominator walker. */
1987 fini_walk_dominator_tree (&walk_data);
1989 VEC_free (int, heap, ssa_ver_to_stridx);
1990 free_alloc_pool (strinfo_pool);
1991 if (decl_to_stridxlist_htab)
1993 obstack_free (&stridx_obstack, NULL);
1994 htab_delete (decl_to_stridxlist_htab);
1995 decl_to_stridxlist_htab = NULL;
1997 laststmt.stmt = NULL;
1998 laststmt.len = NULL_TREE;
1999 laststmt.stridx = 0;
2007 return flag_optimize_strlen != 0;
2010 struct gimple_opt_pass pass_strlen =
2014 "strlen", /* name */
2015 gate_strlen, /* gate */
2016 tree_ssa_strlen, /* execute */
2019 0, /* static_pass_number */
2020 TV_TREE_STRLEN, /* tv_id */
2021 PROP_cfg | PROP_ssa, /* properties_required */
2022 0, /* properties_provided */
2023 0, /* properties_destroyed */
2024 0, /* todo_flags_start */
2026 | TODO_verify_ssa /* todo_flags_finish */