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 (implicit_built_in_decls[BUILT_IN_STRCPY] != NULL_TREE);
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 = implicit_built_in_decls[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 = implicit_built_in_decls[BUILT_IN_STPCPY];
439 fn = built_in_decls[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);
592 if (chainsi->endptr == NULL_TREE)
594 chainsi = unshare_strinfo (chainsi);
595 chainsi->endptr = ptr;
597 if (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 si->prev = chainsi->idx;
630 si->first = chainsi->first;
631 si->writable = chainsi->writable;
636 /* For strinfo ORIGSI whose length has been just updated
637 update also related strinfo lengths (add ADJ to each,
638 but don't adjust ORIGSI). */
641 adjust_related_strinfos (location_t loc, strinfo origsi, tree adj)
643 strinfo si = verify_related_strinfos (origsi);
656 si = unshare_strinfo (si);
657 gcc_assert (si->length);
658 tem = fold_convert_loc (loc, TREE_TYPE (si->length), adj);
659 si->length = fold_build2_loc (loc, PLUS_EXPR,
660 TREE_TYPE (si->length), si->length,
662 si->endptr = NULL_TREE;
663 si->dont_invalidate = true;
667 nsi = get_strinfo (si->next);
669 || nsi->first != si->first
670 || nsi->prev != si->idx)
676 /* Find if there are other SSA_NAME pointers equal to PTR
677 for which we don't track their string lengths yet. If so, use
681 find_equal_ptrs (tree ptr, int idx)
683 if (TREE_CODE (ptr) != SSA_NAME)
687 gimple stmt = SSA_NAME_DEF_STMT (ptr);
688 if (!is_gimple_assign (stmt))
690 ptr = gimple_assign_rhs1 (stmt);
691 switch (gimple_assign_rhs_code (stmt))
696 if (!POINTER_TYPE_P (TREE_TYPE (ptr)))
698 if (TREE_CODE (ptr) == SSA_NAME)
700 if (TREE_CODE (ptr) != ADDR_EXPR)
705 int *pidx = addr_stridxptr (TREE_OPERAND (ptr, 0));
706 if (pidx != NULL && *pidx == 0)
714 /* We might find an endptr created in this pass. Grow the
715 vector in that case. */
716 if (VEC_length (int, ssa_ver_to_stridx) <= SSA_NAME_VERSION (ptr))
717 VEC_safe_grow_cleared (int, heap, ssa_ver_to_stridx, num_ssa_names);
719 if (VEC_index (int, ssa_ver_to_stridx, SSA_NAME_VERSION (ptr)) != 0)
721 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (ptr), idx);
725 /* If the last .MEM setter statement before STMT is
726 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
727 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
728 just memcpy (x, y, strlen (y)). SI must be the zero length
732 adjust_last_stmt (strinfo si, gimple stmt, bool is_strcat)
734 tree vuse, callee, len;
735 struct laststmt_struct last = laststmt;
736 strinfo lastsi, firstsi;
738 laststmt.stmt = NULL;
739 laststmt.len = NULL_TREE;
742 if (last.stmt == NULL)
745 vuse = gimple_vuse (stmt);
746 if (vuse == NULL_TREE
747 || SSA_NAME_DEF_STMT (vuse) != last.stmt
748 || !has_single_use (vuse))
751 gcc_assert (last.stridx > 0);
752 lastsi = get_strinfo (last.stridx);
758 if (lastsi->first == 0 || lastsi->first != si->first)
761 firstsi = verify_related_strinfos (si);
764 while (firstsi != lastsi)
767 if (firstsi->next == 0)
769 nextsi = get_strinfo (firstsi->next);
771 || nextsi->prev != firstsi->idx
772 || nextsi->first != si->first)
780 if (si->length == NULL_TREE || !integer_zerop (si->length))
784 if (is_gimple_assign (last.stmt))
786 gimple_stmt_iterator gsi;
788 if (!integer_zerop (gimple_assign_rhs1 (last.stmt)))
790 if (stmt_could_throw_p (last.stmt))
792 gsi = gsi_for_stmt (last.stmt);
793 unlink_stmt_vdef (last.stmt);
794 release_defs (last.stmt);
795 gsi_remove (&gsi, true);
799 if (!is_gimple_call (last.stmt))
801 callee = gimple_call_fndecl (last.stmt);
802 if (callee == NULL_TREE || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL)
805 switch (DECL_FUNCTION_CODE (callee))
807 case BUILT_IN_MEMCPY:
808 case BUILT_IN_MEMCPY_CHK:
814 len = gimple_call_arg (last.stmt, 2);
815 if (host_integerp (len, 1))
817 if (!host_integerp (last.len, 1)
818 || integer_zerop (len)
819 || (unsigned HOST_WIDE_INT) tree_low_cst (len, 1)
820 != (unsigned HOST_WIDE_INT) tree_low_cst (last.len, 1) + 1)
822 /* Don't adjust the length if it is divisible by 4, it is more efficient
823 to store the extra '\0' in that case. */
824 if ((((unsigned HOST_WIDE_INT) tree_low_cst (len, 1)) & 3) == 0)
827 else if (TREE_CODE (len) == SSA_NAME)
829 gimple def_stmt = SSA_NAME_DEF_STMT (len);
830 if (!is_gimple_assign (def_stmt)
831 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
832 || gimple_assign_rhs1 (def_stmt) != last.len
833 || !integer_onep (gimple_assign_rhs2 (def_stmt)))
839 gimple_call_set_arg (last.stmt, 2, last.len);
840 update_stmt (last.stmt);
843 /* Handle a strlen call. If strlen of the argument is known, replace
844 the strlen call with the known value, otherwise remember that strlen
845 of the argument is stored in the lhs SSA_NAME. */
848 handle_builtin_strlen (gimple_stmt_iterator *gsi)
852 gimple stmt = gsi_stmt (*gsi);
853 tree lhs = gimple_call_lhs (stmt);
855 if (lhs == NULL_TREE)
858 src = gimple_call_arg (stmt, 0);
859 idx = get_stridx (src);
866 rhs = build_int_cst (TREE_TYPE (lhs), ~idx);
870 si = get_strinfo (idx);
872 rhs = get_string_length (si);
874 if (rhs != NULL_TREE)
876 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
878 fprintf (dump_file, "Optimizing: ");
879 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
881 rhs = unshare_expr (rhs);
882 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
883 rhs = fold_convert_loc (gimple_location (stmt),
884 TREE_TYPE (lhs), rhs);
885 if (!update_call_from_tree (gsi, rhs))
886 gimplify_and_update_call_from_tree (gsi, rhs);
887 stmt = gsi_stmt (*gsi);
889 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
891 fprintf (dump_file, "into: ");
892 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
895 && TREE_CODE (si->length) != SSA_NAME
896 && TREE_CODE (si->length) != INTEGER_CST
897 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
899 si = unshare_strinfo (si);
905 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
908 idx = new_stridx (src);
909 else if (get_strinfo (idx) != NULL)
913 strinfo si = new_strinfo (src, idx, lhs);
914 set_strinfo (idx, si);
915 find_equal_ptrs (src, idx);
919 /* Handle a strchr call. If strlen of the first argument is known, replace
920 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
921 that lhs of the call is endptr and strlen of the argument is endptr - x. */
924 handle_builtin_strchr (gimple_stmt_iterator *gsi)
928 gimple stmt = gsi_stmt (*gsi);
929 tree lhs = gimple_call_lhs (stmt);
931 if (lhs == NULL_TREE)
934 if (!integer_zerop (gimple_call_arg (stmt, 1)))
937 src = gimple_call_arg (stmt, 0);
938 idx = get_stridx (src);
945 rhs = build_int_cst (size_type_node, ~idx);
949 si = get_strinfo (idx);
951 rhs = get_string_length (si);
953 if (rhs != NULL_TREE)
955 location_t loc = gimple_location (stmt);
957 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
959 fprintf (dump_file, "Optimizing: ");
960 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
962 if (si != NULL && si->endptr != NULL_TREE)
964 rhs = unshare_expr (si->endptr);
965 if (!useless_type_conversion_p (TREE_TYPE (lhs),
967 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
971 rhs = fold_convert_loc (loc, sizetype, unshare_expr (rhs));
972 rhs = fold_build2_loc (loc, POINTER_PLUS_EXPR,
973 TREE_TYPE (src), src, rhs);
974 if (!useless_type_conversion_p (TREE_TYPE (lhs),
976 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
978 if (!update_call_from_tree (gsi, rhs))
979 gimplify_and_update_call_from_tree (gsi, rhs);
980 stmt = gsi_stmt (*gsi);
982 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
984 fprintf (dump_file, "into: ");
985 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
988 && si->endptr == NULL_TREE
989 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
991 si = unshare_strinfo (si);
994 zero_length_string (lhs, si);
998 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
1000 if (TREE_CODE (src) != SSA_NAME || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src))
1003 idx = new_stridx (src);
1004 else if (get_strinfo (idx) != NULL)
1006 zero_length_string (lhs, NULL);
1011 location_t loc = gimple_location (stmt);
1012 tree lhsu = fold_convert_loc (loc, size_type_node, lhs);
1013 tree srcu = fold_convert_loc (loc, size_type_node, src);
1014 tree length = fold_build2_loc (loc, MINUS_EXPR,
1015 size_type_node, lhsu, srcu);
1016 strinfo si = new_strinfo (src, idx, length);
1018 set_strinfo (idx, si);
1019 find_equal_ptrs (src, idx);
1020 zero_length_string (lhs, si);
1024 zero_length_string (lhs, NULL);
1027 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1028 If strlen of the second argument is known, strlen of the first argument
1029 is the same after this call. Furthermore, attempt to convert it to
1033 handle_builtin_strcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1036 tree src, dst, srclen, len, lhs, args, type, fn, oldlen;
1038 gimple stmt = gsi_stmt (*gsi);
1039 strinfo si, dsi, olddsi, zsi;
1042 src = gimple_call_arg (stmt, 1);
1043 dst = gimple_call_arg (stmt, 0);
1044 lhs = gimple_call_lhs (stmt);
1045 idx = get_stridx (src);
1048 si = get_strinfo (idx);
1050 didx = get_stridx (dst);
1054 olddsi = get_strinfo (didx);
1059 adjust_last_stmt (olddsi, stmt, false);
1063 srclen = get_string_length (si);
1065 srclen = build_int_cst (size_type_node, ~idx);
1067 loc = gimple_location (stmt);
1068 if (srclen == NULL_TREE)
1071 case BUILT_IN_STRCPY:
1072 case BUILT_IN_STRCPY_CHK:
1073 if (implicit_built_in_decls[BUILT_IN_STPCPY] == NULL_TREE
1074 || lhs != NULL_TREE)
1077 case BUILT_IN_STPCPY:
1078 case BUILT_IN_STPCPY_CHK:
1079 if (lhs == NULL_TREE)
1083 tree lhsuint = fold_convert_loc (loc, size_type_node, lhs);
1084 srclen = fold_convert_loc (loc, size_type_node, dst);
1085 srclen = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
1095 didx = new_stridx (dst);
1101 oldlen = olddsi->length;
1102 dsi = unshare_strinfo (olddsi);
1103 dsi->length = srclen;
1104 /* Break the chain, so adjust_related_strinfo on later pointers in
1105 the chain won't adjust this one anymore. */
1108 dsi->endptr = NULL_TREE;
1112 dsi = new_strinfo (dst, didx, srclen);
1113 set_strinfo (didx, dsi);
1114 find_equal_ptrs (dst, didx);
1116 dsi->writable = true;
1117 dsi->dont_invalidate = true;
1119 if (dsi->length == NULL_TREE)
1121 /* If string length of src is unknown, use delayed length
1122 computation. If string lenth of dst will be needed, it
1123 can be computed by transforming this strcpy call into
1124 stpcpy and subtracting dst from the return value. */
1131 tree adj = NULL_TREE;
1132 if (oldlen == NULL_TREE)
1134 else if (integer_zerop (oldlen))
1136 else if (TREE_CODE (oldlen) == INTEGER_CST
1137 || TREE_CODE (srclen) == INTEGER_CST)
1138 adj = fold_build2_loc (loc, MINUS_EXPR,
1139 TREE_TYPE (srclen), srclen,
1140 fold_convert_loc (loc, TREE_TYPE (srclen),
1142 if (adj != NULL_TREE)
1143 adjust_related_strinfos (loc, dsi, adj);
1147 /* strcpy src may not overlap dst, so src doesn't need to be
1148 invalidated either. */
1150 si->dont_invalidate = true;
1156 case BUILT_IN_STRCPY:
1157 fn = implicit_built_in_decls[BUILT_IN_MEMCPY];
1159 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs), didx);
1161 case BUILT_IN_STRCPY_CHK:
1162 fn = built_in_decls[BUILT_IN_MEMCPY_CHK];
1164 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs), didx);
1166 case BUILT_IN_STPCPY:
1167 /* This would need adjustment of the lhs (subtract one),
1168 or detection that the trailing '\0' doesn't need to be
1169 written, if it will be immediately overwritten.
1170 fn = built_in_decls[BUILT_IN_MEMPCPY]; */
1174 zsi = zero_length_string (lhs, dsi);
1177 case BUILT_IN_STPCPY_CHK:
1178 /* This would need adjustment of the lhs (subtract one),
1179 or detection that the trailing '\0' doesn't need to be
1180 written, if it will be immediately overwritten.
1181 fn = built_in_decls[BUILT_IN_MEMPCPY_CHK]; */
1185 zsi = zero_length_string (lhs, dsi);
1192 zsi->dont_invalidate = true;
1194 if (fn == NULL_TREE)
1197 args = TYPE_ARG_TYPES (TREE_TYPE (fn));
1198 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
1200 len = fold_convert_loc (loc, type, unshare_expr (srclen));
1201 len = fold_build2_loc (loc, PLUS_EXPR, type, len, build_int_cst (type, 1));
1202 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
1204 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1206 fprintf (dump_file, "Optimizing: ");
1207 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1209 if (gimple_call_num_args (stmt) == 2)
1210 success = update_gimple_call (gsi, fn, 3, dst, src, len);
1212 success = update_gimple_call (gsi, fn, 4, dst, src, len,
1213 gimple_call_arg (stmt, 2));
1216 stmt = gsi_stmt (*gsi);
1218 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1220 fprintf (dump_file, "into: ");
1221 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1223 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1224 laststmt.stmt = stmt;
1225 laststmt.len = srclen;
1226 laststmt.stridx = dsi->idx;
1228 else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1229 fprintf (dump_file, "not possible.\n");
1232 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
1233 If strlen of the second argument is known and length of the third argument
1234 is that plus one, strlen of the first argument is the same after this
1238 handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1241 tree src, dst, len, lhs, oldlen, newlen;
1242 gimple stmt = gsi_stmt (*gsi);
1243 strinfo si, dsi, olddsi;
1245 len = gimple_call_arg (stmt, 2);
1246 src = gimple_call_arg (stmt, 1);
1247 dst = gimple_call_arg (stmt, 0);
1248 idx = get_stridx (src);
1252 didx = get_stridx (dst);
1255 olddsi = get_strinfo (didx);
1260 && host_integerp (len, 1)
1261 && !integer_zerop (len))
1262 adjust_last_stmt (olddsi, stmt, false);
1268 /* Handle memcpy (x, y, l) where l is strlen (y) + 1. */
1269 si = get_strinfo (idx);
1270 if (si == NULL || si->length == NULL_TREE)
1272 if (TREE_CODE (len) != SSA_NAME)
1274 def_stmt = SSA_NAME_DEF_STMT (len);
1275 if (!is_gimple_assign (def_stmt)
1276 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
1277 || gimple_assign_rhs1 (def_stmt) != si->length
1278 || !integer_onep (gimple_assign_rhs2 (def_stmt)))
1284 /* Handle memcpy (x, "abcd", 5) or
1285 memcpy (x, "abc\0uvw", 7). */
1286 if (!host_integerp (len, 1)
1287 || (unsigned HOST_WIDE_INT) tree_low_cst (len, 1)
1288 <= (unsigned HOST_WIDE_INT) ~idx)
1292 if (olddsi != NULL && TREE_CODE (len) == SSA_NAME)
1293 adjust_last_stmt (olddsi, stmt, false);
1297 didx = new_stridx (dst);
1302 newlen = si->length;
1304 newlen = build_int_cst (size_type_node, ~idx);
1308 dsi = unshare_strinfo (olddsi);
1309 oldlen = olddsi->length;
1310 dsi->length = newlen;
1311 /* Break the chain, so adjust_related_strinfo on later pointers in
1312 the chain won't adjust this one anymore. */
1315 dsi->endptr = NULL_TREE;
1319 dsi = new_strinfo (dst, didx, newlen);
1320 set_strinfo (didx, dsi);
1321 find_equal_ptrs (dst, didx);
1323 dsi->writable = true;
1324 dsi->dont_invalidate = true;
1327 tree adj = NULL_TREE;
1328 location_t loc = gimple_location (stmt);
1329 if (oldlen == NULL_TREE)
1331 else if (integer_zerop (oldlen))
1333 else if (TREE_CODE (oldlen) == INTEGER_CST
1334 || TREE_CODE (dsi->length) == INTEGER_CST)
1335 adj = fold_build2_loc (loc, MINUS_EXPR,
1336 TREE_TYPE (dsi->length), dsi->length,
1337 fold_convert_loc (loc, TREE_TYPE (dsi->length),
1339 if (adj != NULL_TREE)
1340 adjust_related_strinfos (loc, dsi, adj);
1344 /* memcpy src may not overlap dst, so src doesn't need to be
1345 invalidated either. */
1347 si->dont_invalidate = true;
1349 lhs = gimple_call_lhs (stmt);
1352 case BUILT_IN_MEMCPY:
1353 case BUILT_IN_MEMCPY_CHK:
1354 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1355 laststmt.stmt = stmt;
1356 laststmt.len = dsi->length;
1357 laststmt.stridx = dsi->idx;
1359 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs), didx);
1361 case BUILT_IN_MEMPCPY:
1362 case BUILT_IN_MEMPCPY_CHK:
1369 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
1370 If strlen of the second argument is known, strlen of the first argument
1371 is increased by the length of the second argument. Furthermore, attempt
1372 to convert it to memcpy/strcpy if the length of the first argument
1376 handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1379 tree src, dst, srclen, dstlen, len, lhs, args, type, fn, objsz, endptr;
1381 gimple stmt = gsi_stmt (*gsi);
1385 src = gimple_call_arg (stmt, 1);
1386 dst = gimple_call_arg (stmt, 0);
1387 lhs = gimple_call_lhs (stmt);
1389 didx = get_stridx (dst);
1395 dsi = get_strinfo (didx);
1396 if (dsi == NULL || get_string_length (dsi) == NULL_TREE)
1398 /* strcat (p, q) can be transformed into
1399 tmp = p + strlen (p); endptr = strpcpy (tmp, q);
1400 with length endptr - p if we need to compute the length
1401 later on. Don't do this transformation if we don't need
1403 if (implicit_built_in_decls[BUILT_IN_STPCPY] != NULL_TREE
1404 && lhs == NULL_TREE)
1408 didx = new_stridx (dst);
1414 dsi = new_strinfo (dst, didx, NULL_TREE);
1415 set_strinfo (didx, dsi);
1416 find_equal_ptrs (dst, didx);
1420 dsi = unshare_strinfo (dsi);
1421 dsi->length = NULL_TREE;
1423 dsi->endptr = NULL_TREE;
1425 dsi->writable = true;
1427 dsi->dont_invalidate = true;
1434 idx = get_stridx (src);
1436 srclen = build_int_cst (size_type_node, ~idx);
1439 si = get_strinfo (idx);
1441 srclen = get_string_length (si);
1444 loc = gimple_location (stmt);
1445 dstlen = dsi->length;
1446 endptr = dsi->endptr;
1448 dsi = unshare_strinfo (dsi);
1449 dsi->endptr = NULL_TREE;
1451 dsi->writable = true;
1453 if (srclen != NULL_TREE)
1455 dsi->length = fold_build2_loc (loc, PLUS_EXPR, TREE_TYPE (dsi->length),
1456 dsi->length, srclen);
1457 adjust_related_strinfos (loc, dsi, srclen);
1458 dsi->dont_invalidate = true;
1463 if (implicit_built_in_decls[BUILT_IN_STPCPY] != NULL_TREE
1464 && lhs == NULL_TREE)
1465 dsi->dont_invalidate = true;
1469 /* strcat src may not overlap dst, so src doesn't need to be
1470 invalidated either. */
1471 si->dont_invalidate = true;
1473 /* For now. Could remove the lhs from the call and add
1474 lhs = dst; afterwards. */
1482 case BUILT_IN_STRCAT:
1483 if (srclen != NULL_TREE)
1484 fn = implicit_built_in_decls[BUILT_IN_MEMCPY];
1486 fn = implicit_built_in_decls[BUILT_IN_STRCPY];
1488 case BUILT_IN_STRCAT_CHK:
1489 if (srclen != NULL_TREE)
1490 fn = built_in_decls[BUILT_IN_MEMCPY_CHK];
1492 fn = built_in_decls[BUILT_IN_STRCPY_CHK];
1493 objsz = gimple_call_arg (stmt, 2);
1499 if (fn == NULL_TREE)
1503 if (srclen != NULL_TREE)
1505 args = TYPE_ARG_TYPES (TREE_TYPE (fn));
1506 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
1508 len = fold_convert_loc (loc, type, unshare_expr (srclen));
1509 len = fold_build2_loc (loc, PLUS_EXPR, type, len,
1510 build_int_cst (type, 1));
1511 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
1515 dst = fold_convert_loc (loc, TREE_TYPE (dst), unshare_expr (endptr));
1517 dst = fold_build2_loc (loc, POINTER_PLUS_EXPR,
1518 TREE_TYPE (dst), unshare_expr (dst),
1519 fold_convert_loc (loc, sizetype,
1520 unshare_expr (dstlen)));
1521 dst = force_gimple_operand_gsi (gsi, dst, true, NULL_TREE, true,
1523 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1525 fprintf (dump_file, "Optimizing: ");
1526 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1528 if (srclen != NULL_TREE)
1529 success = update_gimple_call (gsi, fn, 3 + (objsz != NULL_TREE),
1530 dst, src, len, objsz);
1532 success = update_gimple_call (gsi, fn, 2 + (objsz != NULL_TREE),
1536 stmt = gsi_stmt (*gsi);
1538 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1540 fprintf (dump_file, "into: ");
1541 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1543 /* If srclen == NULL, note that current string length can be
1544 computed by transforming this strcpy into stpcpy. */
1545 if (srclen == NULL_TREE && dsi->dont_invalidate)
1547 adjust_last_stmt (dsi, stmt, true);
1548 if (srclen != NULL_TREE)
1550 laststmt.stmt = stmt;
1551 laststmt.len = srclen;
1552 laststmt.stridx = dsi->idx;
1555 else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1556 fprintf (dump_file, "not possible.\n");
1559 /* Handle a POINTER_PLUS_EXPR statement.
1560 For p = "abcd" + 2; compute associated length, or if
1561 p = q + off is pointing to a '\0' character of a string, call
1562 zero_length_string on it. */
1565 handle_pointer_plus (gimple_stmt_iterator *gsi)
1567 gimple stmt = gsi_stmt (*gsi);
1568 tree lhs = gimple_assign_lhs (stmt), off;
1569 int idx = get_stridx (gimple_assign_rhs1 (stmt));
1577 tree off = gimple_assign_rhs2 (stmt);
1578 if (host_integerp (off, 1)
1579 && (unsigned HOST_WIDE_INT) tree_low_cst (off, 1)
1580 <= (unsigned HOST_WIDE_INT) ~idx)
1581 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs),
1582 ~(~idx - (int) tree_low_cst (off, 1)));
1586 si = get_strinfo (idx);
1587 if (si == NULL || si->length == NULL_TREE)
1590 off = gimple_assign_rhs2 (stmt);
1592 if (operand_equal_p (si->length, off, 0))
1593 zsi = zero_length_string (lhs, si);
1594 else if (TREE_CODE (off) == SSA_NAME)
1596 gimple def_stmt = SSA_NAME_DEF_STMT (off);
1597 if (gimple_assign_single_p (def_stmt)
1598 && operand_equal_p (si->length, gimple_assign_rhs1 (def_stmt), 0))
1599 zsi = zero_length_string (lhs, si);
1602 && si->endptr != NULL_TREE
1603 && si->endptr != lhs
1604 && TREE_CODE (si->endptr) == SSA_NAME)
1606 enum tree_code rhs_code
1607 = useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (si->endptr))
1608 ? SSA_NAME : NOP_EXPR;
1609 gimple_assign_set_rhs_with_ops (gsi, rhs_code, si->endptr, NULL_TREE);
1610 gcc_assert (gsi_stmt (*gsi) == stmt);
1615 /* Handle a single character store. */
1618 handle_char_store (gimple_stmt_iterator *gsi)
1622 gimple stmt = gsi_stmt (*gsi);
1623 tree ssaname = NULL_TREE, lhs = gimple_assign_lhs (stmt);
1625 if (TREE_CODE (lhs) == MEM_REF
1626 && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME)
1628 if (integer_zerop (TREE_OPERAND (lhs, 1)))
1630 ssaname = TREE_OPERAND (lhs, 0);
1631 idx = get_stridx (ssaname);
1635 idx = get_addr_stridx (lhs);
1639 si = get_strinfo (idx);
1640 if (si != NULL && si->length != NULL_TREE && integer_zerop (si->length))
1642 if (initializer_zerop (gimple_assign_rhs1 (stmt)))
1644 /* When storing '\0', the store can be removed
1645 if we know it has been stored in the current function. */
1646 if (!stmt_could_throw_p (stmt) && si->writable)
1648 unlink_stmt_vdef (stmt);
1649 release_defs (stmt);
1650 gsi_remove (gsi, true);
1655 si->writable = true;
1656 si->dont_invalidate = true;
1660 /* Otherwise this statement overwrites the '\0' with
1661 something, if the previous stmt was a memcpy,
1662 its length may be decreased. */
1663 adjust_last_stmt (si, stmt, false);
1665 else if (si != NULL)
1667 si = unshare_strinfo (si);
1668 si->length = build_int_cst (size_type_node, 0);
1674 si->writable = true;
1675 if (ssaname && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname))
1676 si->endptr = ssaname;
1677 si->dont_invalidate = true;
1680 else if (idx == 0 && initializer_zerop (gimple_assign_rhs1 (stmt)))
1684 si = zero_length_string (ssaname, NULL);
1686 si->dont_invalidate = true;
1690 int idx = new_addr_stridx (lhs);
1693 si = new_strinfo (build_fold_addr_expr (lhs), idx,
1694 build_int_cst (size_type_node, 0));
1695 set_strinfo (idx, si);
1696 si->dont_invalidate = true;
1700 si->writable = true;
1703 if (si != NULL && initializer_zerop (gimple_assign_rhs1 (stmt)))
1705 /* Allow adjust_last_stmt to remove it if the stored '\0'
1706 is immediately overwritten. */
1707 laststmt.stmt = stmt;
1708 laststmt.len = build_int_cst (size_type_node, 1);
1709 laststmt.stridx = si->idx;
1714 /* Attempt to optimize a single statement at *GSI using string length
1718 strlen_optimize_stmt (gimple_stmt_iterator *gsi)
1720 gimple stmt = gsi_stmt (*gsi);
1722 if (is_gimple_call (stmt))
1724 tree callee = gimple_call_fndecl (stmt);
1725 if (callee && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
1726 switch (DECL_FUNCTION_CODE (callee))
1728 case BUILT_IN_STRLEN:
1729 handle_builtin_strlen (gsi);
1731 case BUILT_IN_STRCHR:
1732 handle_builtin_strchr (gsi);
1734 case BUILT_IN_STRCPY:
1735 case BUILT_IN_STRCPY_CHK:
1736 case BUILT_IN_STPCPY:
1737 case BUILT_IN_STPCPY_CHK:
1738 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee), gsi);
1740 case BUILT_IN_MEMCPY:
1741 case BUILT_IN_MEMCPY_CHK:
1742 case BUILT_IN_MEMPCPY:
1743 case BUILT_IN_MEMPCPY_CHK:
1744 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee), gsi);
1746 case BUILT_IN_STRCAT:
1747 case BUILT_IN_STRCAT_CHK:
1748 handle_builtin_strcat (DECL_FUNCTION_CODE (callee), gsi);
1754 else if (is_gimple_assign (stmt))
1756 tree lhs = gimple_assign_lhs (stmt);
1758 if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (lhs)))
1760 if (gimple_assign_single_p (stmt)
1761 || (gimple_assign_cast_p (stmt)
1762 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt)))))
1764 int idx = get_stridx (gimple_assign_rhs1 (stmt));
1765 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs),
1768 else if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
1769 handle_pointer_plus (gsi);
1771 else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs))
1773 tree type = TREE_TYPE (lhs);
1774 if (TREE_CODE (type) == ARRAY_TYPE)
1775 type = TREE_TYPE (type);
1776 if (TREE_CODE (type) == INTEGER_TYPE
1777 && TYPE_MODE (type) == TYPE_MODE (char_type_node)
1778 && TYPE_PRECISION (type) == TYPE_PRECISION (char_type_node))
1780 if (! handle_char_store (gsi))
1786 if (gimple_vdef (stmt))
1787 maybe_invalidate (stmt);
1791 /* Recursively call maybe_invalidate on stmts that might be executed
1792 in between dombb and current bb and that contain a vdef. Stop when
1793 *count stmts are inspected, or if the whole strinfo vector has
1794 been invalidated. */
1797 do_invalidate (basic_block dombb, gimple phi, bitmap visited, int *count)
1799 unsigned int i, n = gimple_phi_num_args (phi);
1801 for (i = 0; i < n; i++)
1803 tree vuse = gimple_phi_arg_def (phi, i);
1804 gimple stmt = SSA_NAME_DEF_STMT (vuse);
1805 basic_block bb = gimple_bb (stmt);
1808 || !bitmap_set_bit (visited, bb->index)
1809 || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
1813 if (gimple_code (stmt) == GIMPLE_PHI)
1815 do_invalidate (dombb, stmt, visited, count);
1822 if (!maybe_invalidate (stmt))
1827 vuse = gimple_vuse (stmt);
1828 stmt = SSA_NAME_DEF_STMT (vuse);
1829 if (gimple_bb (stmt) != bb)
1831 bb = gimple_bb (stmt);
1834 || !bitmap_set_bit (visited, bb->index)
1835 || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
1842 /* Callback for walk_dominator_tree. Attempt to optimize various
1843 string ops by remembering string lenths pointed by pointer SSA_NAMEs. */
1846 strlen_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1849 gimple_stmt_iterator gsi;
1850 basic_block dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
1853 stridx_to_strinfo = NULL;
1856 stridx_to_strinfo = (VEC(strinfo, heap) *) dombb->aux;
1857 if (stridx_to_strinfo)
1859 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1861 gimple phi = gsi_stmt (gsi);
1862 if (!is_gimple_reg (gimple_phi_result (phi)))
1864 bitmap visited = BITMAP_ALLOC (NULL);
1865 int count_vdef = 100;
1866 do_invalidate (dombb, phi, visited, &count_vdef);
1867 BITMAP_FREE (visited);
1874 /* If all PHI arguments have the same string index, the PHI result
1876 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1878 gimple phi = gsi_stmt (gsi);
1879 tree result = gimple_phi_result (phi);
1880 if (is_gimple_reg (result) && POINTER_TYPE_P (TREE_TYPE (result)))
1882 int idx = get_stridx (gimple_phi_arg_def (phi, 0));
1885 unsigned int i, n = gimple_phi_num_args (phi);
1886 for (i = 1; i < n; i++)
1887 if (idx != get_stridx (gimple_phi_arg_def (phi, i)))
1890 VEC_replace (int, ssa_ver_to_stridx,
1891 SSA_NAME_VERSION (result), idx);
1896 /* Attempt to optimize individual statements. */
1897 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
1898 if (strlen_optimize_stmt (&gsi))
1901 bb->aux = stridx_to_strinfo;
1902 if (VEC_length (strinfo, stridx_to_strinfo) && !strinfo_shared ())
1903 VEC_replace (strinfo, stridx_to_strinfo, 0, (strinfo) bb);
1906 /* Callback for walk_dominator_tree. Free strinfo vector if it is
1907 owned by the current bb, clear bb->aux. */
1910 strlen_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1915 stridx_to_strinfo = (VEC(strinfo, heap) *) bb->aux;
1916 if (VEC_length (strinfo, stridx_to_strinfo)
1917 && VEC_index (strinfo, stridx_to_strinfo, 0) == (strinfo) bb)
1922 for (i = 1; VEC_iterate (strinfo, stridx_to_strinfo, i, si); ++i)
1924 VEC_free (strinfo, heap, stridx_to_strinfo);
1930 /* Main entry point. */
1933 tree_ssa_strlen (void)
1935 struct dom_walk_data walk_data;
1937 VEC_safe_grow_cleared (int, heap, ssa_ver_to_stridx, num_ssa_names);
1939 strinfo_pool = create_alloc_pool ("strinfo_struct pool",
1940 sizeof (struct strinfo_struct), 64);
1942 calculate_dominance_info (CDI_DOMINATORS);
1944 /* String length optimization is implemented as a walk of the dominator
1945 tree and a forward walk of statements within each block. */
1946 walk_data.dom_direction = CDI_DOMINATORS;
1947 walk_data.initialize_block_local_data = NULL;
1948 walk_data.before_dom_children = strlen_enter_block;
1949 walk_data.after_dom_children = strlen_leave_block;
1950 walk_data.block_local_data_size = 0;
1951 walk_data.global_data = NULL;
1953 /* Initialize the dominator walker. */
1954 init_walk_dominator_tree (&walk_data);
1956 /* Recursively walk the dominator tree. */
1957 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1959 /* Finalize the dominator walker. */
1960 fini_walk_dominator_tree (&walk_data);
1962 VEC_free (int, heap, ssa_ver_to_stridx);
1963 free_alloc_pool (strinfo_pool);
1964 if (decl_to_stridxlist_htab)
1966 obstack_free (&stridx_obstack, NULL);
1967 htab_delete (decl_to_stridxlist_htab);
1968 decl_to_stridxlist_htab = NULL;
1970 laststmt.stmt = NULL;
1971 laststmt.len = NULL_TREE;
1972 laststmt.stridx = 0;
1980 return flag_optimize_strlen != 0;
1983 struct gimple_opt_pass pass_strlen =
1987 "strlen", /* name */
1988 gate_strlen, /* gate */
1989 tree_ssa_strlen, /* execute */
1992 0, /* static_pass_number */
1993 TV_TREE_STRLEN, /* tv_id */
1994 PROP_cfg | PROP_ssa, /* properties_required */
1995 0, /* properties_provided */
1996 0, /* properties_destroyed */
1997 0, /* todo_flags_start */
1999 | TODO_verify_ssa /* todo_flags_finish */