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_STRCPY));
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);
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 (lhs != NULL_TREE || !builtin_decl_implicit_p (BUILT_IN_STPCPY))
1076 case BUILT_IN_STPCPY:
1077 case BUILT_IN_STPCPY_CHK:
1078 if (lhs == NULL_TREE)
1082 tree lhsuint = fold_convert_loc (loc, size_type_node, lhs);
1083 srclen = fold_convert_loc (loc, size_type_node, dst);
1084 srclen = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
1094 didx = new_stridx (dst);
1100 oldlen = olddsi->length;
1101 dsi = unshare_strinfo (olddsi);
1102 dsi->length = srclen;
1103 /* Break the chain, so adjust_related_strinfo on later pointers in
1104 the chain won't adjust this one anymore. */
1107 dsi->endptr = NULL_TREE;
1111 dsi = new_strinfo (dst, didx, srclen);
1112 set_strinfo (didx, dsi);
1113 find_equal_ptrs (dst, didx);
1115 dsi->writable = true;
1116 dsi->dont_invalidate = true;
1118 if (dsi->length == NULL_TREE)
1120 /* If string length of src is unknown, use delayed length
1121 computation. If string lenth of dst will be needed, it
1122 can be computed by transforming this strcpy call into
1123 stpcpy and subtracting dst from the return value. */
1130 tree adj = NULL_TREE;
1131 if (oldlen == NULL_TREE)
1133 else if (integer_zerop (oldlen))
1135 else if (TREE_CODE (oldlen) == INTEGER_CST
1136 || TREE_CODE (srclen) == INTEGER_CST)
1137 adj = fold_build2_loc (loc, MINUS_EXPR,
1138 TREE_TYPE (srclen), srclen,
1139 fold_convert_loc (loc, TREE_TYPE (srclen),
1141 if (adj != NULL_TREE)
1142 adjust_related_strinfos (loc, dsi, adj);
1146 /* strcpy src may not overlap dst, so src doesn't need to be
1147 invalidated either. */
1149 si->dont_invalidate = true;
1155 case BUILT_IN_STRCPY:
1156 fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
1158 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs), didx);
1160 case BUILT_IN_STRCPY_CHK:
1161 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK);
1163 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs), didx);
1165 case BUILT_IN_STPCPY:
1166 /* This would need adjustment of the lhs (subtract one),
1167 or detection that the trailing '\0' doesn't need to be
1168 written, if it will be immediately overwritten.
1169 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1173 zsi = zero_length_string (lhs, dsi);
1176 case BUILT_IN_STPCPY_CHK:
1177 /* This would need adjustment of the lhs (subtract one),
1178 or detection that the trailing '\0' doesn't need to be
1179 written, if it will be immediately overwritten.
1180 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1184 zsi = zero_length_string (lhs, dsi);
1191 zsi->dont_invalidate = true;
1193 if (fn == NULL_TREE)
1196 args = TYPE_ARG_TYPES (TREE_TYPE (fn));
1197 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
1199 len = fold_convert_loc (loc, type, unshare_expr (srclen));
1200 len = fold_build2_loc (loc, PLUS_EXPR, type, len, build_int_cst (type, 1));
1201 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
1203 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1205 fprintf (dump_file, "Optimizing: ");
1206 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1208 if (gimple_call_num_args (stmt) == 2)
1209 success = update_gimple_call (gsi, fn, 3, dst, src, len);
1211 success = update_gimple_call (gsi, fn, 4, dst, src, len,
1212 gimple_call_arg (stmt, 2));
1215 stmt = gsi_stmt (*gsi);
1217 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1219 fprintf (dump_file, "into: ");
1220 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1222 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1223 laststmt.stmt = stmt;
1224 laststmt.len = srclen;
1225 laststmt.stridx = dsi->idx;
1227 else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1228 fprintf (dump_file, "not possible.\n");
1231 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
1232 If strlen of the second argument is known and length of the third argument
1233 is that plus one, strlen of the first argument is the same after this
1237 handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1240 tree src, dst, len, lhs, oldlen, newlen;
1241 gimple stmt = gsi_stmt (*gsi);
1242 strinfo si, dsi, olddsi;
1244 len = gimple_call_arg (stmt, 2);
1245 src = gimple_call_arg (stmt, 1);
1246 dst = gimple_call_arg (stmt, 0);
1247 idx = get_stridx (src);
1251 didx = get_stridx (dst);
1254 olddsi = get_strinfo (didx);
1259 && host_integerp (len, 1)
1260 && !integer_zerop (len))
1261 adjust_last_stmt (olddsi, stmt, false);
1267 /* Handle memcpy (x, y, l) where l is strlen (y) + 1. */
1268 si = get_strinfo (idx);
1269 if (si == NULL || si->length == NULL_TREE)
1271 if (TREE_CODE (len) != SSA_NAME)
1273 def_stmt = SSA_NAME_DEF_STMT (len);
1274 if (!is_gimple_assign (def_stmt)
1275 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
1276 || gimple_assign_rhs1 (def_stmt) != si->length
1277 || !integer_onep (gimple_assign_rhs2 (def_stmt)))
1283 /* Handle memcpy (x, "abcd", 5) or
1284 memcpy (x, "abc\0uvw", 7). */
1285 if (!host_integerp (len, 1)
1286 || (unsigned HOST_WIDE_INT) tree_low_cst (len, 1)
1287 <= (unsigned HOST_WIDE_INT) ~idx)
1291 if (olddsi != NULL && TREE_CODE (len) == SSA_NAME)
1292 adjust_last_stmt (olddsi, stmt, false);
1296 didx = new_stridx (dst);
1301 newlen = si->length;
1303 newlen = build_int_cst (size_type_node, ~idx);
1307 dsi = unshare_strinfo (olddsi);
1308 oldlen = olddsi->length;
1309 dsi->length = newlen;
1310 /* Break the chain, so adjust_related_strinfo on later pointers in
1311 the chain won't adjust this one anymore. */
1314 dsi->endptr = NULL_TREE;
1318 dsi = new_strinfo (dst, didx, newlen);
1319 set_strinfo (didx, dsi);
1320 find_equal_ptrs (dst, didx);
1322 dsi->writable = true;
1323 dsi->dont_invalidate = true;
1326 tree adj = NULL_TREE;
1327 location_t loc = gimple_location (stmt);
1328 if (oldlen == NULL_TREE)
1330 else if (integer_zerop (oldlen))
1332 else if (TREE_CODE (oldlen) == INTEGER_CST
1333 || TREE_CODE (dsi->length) == INTEGER_CST)
1334 adj = fold_build2_loc (loc, MINUS_EXPR,
1335 TREE_TYPE (dsi->length), dsi->length,
1336 fold_convert_loc (loc, TREE_TYPE (dsi->length),
1338 if (adj != NULL_TREE)
1339 adjust_related_strinfos (loc, dsi, adj);
1343 /* memcpy src may not overlap dst, so src doesn't need to be
1344 invalidated either. */
1346 si->dont_invalidate = true;
1348 lhs = gimple_call_lhs (stmt);
1351 case BUILT_IN_MEMCPY:
1352 case BUILT_IN_MEMCPY_CHK:
1353 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1354 laststmt.stmt = stmt;
1355 laststmt.len = dsi->length;
1356 laststmt.stridx = dsi->idx;
1358 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs), didx);
1360 case BUILT_IN_MEMPCPY:
1361 case BUILT_IN_MEMPCPY_CHK:
1368 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
1369 If strlen of the second argument is known, strlen of the first argument
1370 is increased by the length of the second argument. Furthermore, attempt
1371 to convert it to memcpy/strcpy if the length of the first argument
1375 handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1378 tree src, dst, srclen, dstlen, len, lhs, args, type, fn, objsz, endptr;
1380 gimple stmt = gsi_stmt (*gsi);
1384 src = gimple_call_arg (stmt, 1);
1385 dst = gimple_call_arg (stmt, 0);
1386 lhs = gimple_call_lhs (stmt);
1388 didx = get_stridx (dst);
1394 dsi = get_strinfo (didx);
1395 if (dsi == NULL || get_string_length (dsi) == NULL_TREE)
1397 /* strcat (p, q) can be transformed into
1398 tmp = p + strlen (p); endptr = strpcpy (tmp, q);
1399 with length endptr - p if we need to compute the length
1400 later on. Don't do this transformation if we don't need
1402 if (builtin_decl_implicit_p (BUILT_IN_STPCPY) && lhs == NULL_TREE)
1406 didx = new_stridx (dst);
1412 dsi = new_strinfo (dst, didx, NULL_TREE);
1413 set_strinfo (didx, dsi);
1414 find_equal_ptrs (dst, didx);
1418 dsi = unshare_strinfo (dsi);
1419 dsi->length = NULL_TREE;
1421 dsi->endptr = NULL_TREE;
1423 dsi->writable = true;
1425 dsi->dont_invalidate = true;
1432 idx = get_stridx (src);
1434 srclen = build_int_cst (size_type_node, ~idx);
1437 si = get_strinfo (idx);
1439 srclen = get_string_length (si);
1442 loc = gimple_location (stmt);
1443 dstlen = dsi->length;
1444 endptr = dsi->endptr;
1446 dsi = unshare_strinfo (dsi);
1447 dsi->endptr = NULL_TREE;
1449 dsi->writable = true;
1451 if (srclen != NULL_TREE)
1453 dsi->length = fold_build2_loc (loc, PLUS_EXPR, TREE_TYPE (dsi->length),
1454 dsi->length, srclen);
1455 adjust_related_strinfos (loc, dsi, srclen);
1456 dsi->dont_invalidate = true;
1461 if (lhs == NULL_TREE && builtin_decl_implicit_p (BUILT_IN_STPCPY))
1462 dsi->dont_invalidate = true;
1466 /* strcat src may not overlap dst, so src doesn't need to be
1467 invalidated either. */
1468 si->dont_invalidate = true;
1470 /* For now. Could remove the lhs from the call and add
1471 lhs = dst; afterwards. */
1479 case BUILT_IN_STRCAT:
1480 if (srclen != NULL_TREE)
1481 fn = builtin_decl_implicit (BUILT_IN_MEMCPY);
1483 fn = builtin_decl_implicit (BUILT_IN_STRCPY);
1485 case BUILT_IN_STRCAT_CHK:
1486 if (srclen != NULL_TREE)
1487 fn = builtin_decl_explicit (BUILT_IN_MEMCPY_CHK);
1489 fn = builtin_decl_explicit (BUILT_IN_STRCPY_CHK);
1490 objsz = gimple_call_arg (stmt, 2);
1496 if (fn == NULL_TREE)
1500 if (srclen != NULL_TREE)
1502 args = TYPE_ARG_TYPES (TREE_TYPE (fn));
1503 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
1505 len = fold_convert_loc (loc, type, unshare_expr (srclen));
1506 len = fold_build2_loc (loc, PLUS_EXPR, type, len,
1507 build_int_cst (type, 1));
1508 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
1512 dst = fold_convert_loc (loc, TREE_TYPE (dst), unshare_expr (endptr));
1514 dst = fold_build2_loc (loc, POINTER_PLUS_EXPR,
1515 TREE_TYPE (dst), unshare_expr (dst),
1516 fold_convert_loc (loc, sizetype,
1517 unshare_expr (dstlen)));
1518 dst = force_gimple_operand_gsi (gsi, dst, true, NULL_TREE, true,
1520 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1522 fprintf (dump_file, "Optimizing: ");
1523 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1525 if (srclen != NULL_TREE)
1526 success = update_gimple_call (gsi, fn, 3 + (objsz != NULL_TREE),
1527 dst, src, len, objsz);
1529 success = update_gimple_call (gsi, fn, 2 + (objsz != NULL_TREE),
1533 stmt = gsi_stmt (*gsi);
1535 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1537 fprintf (dump_file, "into: ");
1538 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1540 /* If srclen == NULL, note that current string length can be
1541 computed by transforming this strcpy into stpcpy. */
1542 if (srclen == NULL_TREE && dsi->dont_invalidate)
1544 adjust_last_stmt (dsi, stmt, true);
1545 if (srclen != NULL_TREE)
1547 laststmt.stmt = stmt;
1548 laststmt.len = srclen;
1549 laststmt.stridx = dsi->idx;
1552 else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1553 fprintf (dump_file, "not possible.\n");
1556 /* Handle a POINTER_PLUS_EXPR statement.
1557 For p = "abcd" + 2; compute associated length, or if
1558 p = q + off is pointing to a '\0' character of a string, call
1559 zero_length_string on it. */
1562 handle_pointer_plus (gimple_stmt_iterator *gsi)
1564 gimple stmt = gsi_stmt (*gsi);
1565 tree lhs = gimple_assign_lhs (stmt), off;
1566 int idx = get_stridx (gimple_assign_rhs1 (stmt));
1574 tree off = gimple_assign_rhs2 (stmt);
1575 if (host_integerp (off, 1)
1576 && (unsigned HOST_WIDE_INT) tree_low_cst (off, 1)
1577 <= (unsigned HOST_WIDE_INT) ~idx)
1578 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs),
1579 ~(~idx - (int) tree_low_cst (off, 1)));
1583 si = get_strinfo (idx);
1584 if (si == NULL || si->length == NULL_TREE)
1587 off = gimple_assign_rhs2 (stmt);
1589 if (operand_equal_p (si->length, off, 0))
1590 zsi = zero_length_string (lhs, si);
1591 else if (TREE_CODE (off) == SSA_NAME)
1593 gimple def_stmt = SSA_NAME_DEF_STMT (off);
1594 if (gimple_assign_single_p (def_stmt)
1595 && operand_equal_p (si->length, gimple_assign_rhs1 (def_stmt), 0))
1596 zsi = zero_length_string (lhs, si);
1599 && si->endptr != NULL_TREE
1600 && si->endptr != lhs
1601 && TREE_CODE (si->endptr) == SSA_NAME)
1603 enum tree_code rhs_code
1604 = useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (si->endptr))
1605 ? SSA_NAME : NOP_EXPR;
1606 gimple_assign_set_rhs_with_ops (gsi, rhs_code, si->endptr, NULL_TREE);
1607 gcc_assert (gsi_stmt (*gsi) == stmt);
1612 /* Handle a single character store. */
1615 handle_char_store (gimple_stmt_iterator *gsi)
1619 gimple stmt = gsi_stmt (*gsi);
1620 tree ssaname = NULL_TREE, lhs = gimple_assign_lhs (stmt);
1622 if (TREE_CODE (lhs) == MEM_REF
1623 && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME)
1625 if (integer_zerop (TREE_OPERAND (lhs, 1)))
1627 ssaname = TREE_OPERAND (lhs, 0);
1628 idx = get_stridx (ssaname);
1632 idx = get_addr_stridx (lhs);
1636 si = get_strinfo (idx);
1637 if (si != NULL && si->length != NULL_TREE && integer_zerop (si->length))
1639 if (initializer_zerop (gimple_assign_rhs1 (stmt)))
1641 /* When storing '\0', the store can be removed
1642 if we know it has been stored in the current function. */
1643 if (!stmt_could_throw_p (stmt) && si->writable)
1645 unlink_stmt_vdef (stmt);
1646 release_defs (stmt);
1647 gsi_remove (gsi, true);
1652 si->writable = true;
1653 si->dont_invalidate = true;
1657 /* Otherwise this statement overwrites the '\0' with
1658 something, if the previous stmt was a memcpy,
1659 its length may be decreased. */
1660 adjust_last_stmt (si, stmt, false);
1662 else if (si != NULL)
1664 si = unshare_strinfo (si);
1665 si->length = build_int_cst (size_type_node, 0);
1671 si->writable = true;
1672 if (ssaname && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname))
1673 si->endptr = ssaname;
1674 si->dont_invalidate = true;
1677 else if (idx == 0 && initializer_zerop (gimple_assign_rhs1 (stmt)))
1681 si = zero_length_string (ssaname, NULL);
1683 si->dont_invalidate = true;
1687 int idx = new_addr_stridx (lhs);
1690 si = new_strinfo (build_fold_addr_expr (lhs), idx,
1691 build_int_cst (size_type_node, 0));
1692 set_strinfo (idx, si);
1693 si->dont_invalidate = true;
1697 si->writable = true;
1700 if (si != NULL && initializer_zerop (gimple_assign_rhs1 (stmt)))
1702 /* Allow adjust_last_stmt to remove it if the stored '\0'
1703 is immediately overwritten. */
1704 laststmt.stmt = stmt;
1705 laststmt.len = build_int_cst (size_type_node, 1);
1706 laststmt.stridx = si->idx;
1711 /* Attempt to optimize a single statement at *GSI using string length
1715 strlen_optimize_stmt (gimple_stmt_iterator *gsi)
1717 gimple stmt = gsi_stmt (*gsi);
1719 if (is_gimple_call (stmt))
1721 tree callee = gimple_call_fndecl (stmt);
1722 if (callee && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
1723 switch (DECL_FUNCTION_CODE (callee))
1725 case BUILT_IN_STRLEN:
1726 handle_builtin_strlen (gsi);
1728 case BUILT_IN_STRCHR:
1729 handle_builtin_strchr (gsi);
1731 case BUILT_IN_STRCPY:
1732 case BUILT_IN_STRCPY_CHK:
1733 case BUILT_IN_STPCPY:
1734 case BUILT_IN_STPCPY_CHK:
1735 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee), gsi);
1737 case BUILT_IN_MEMCPY:
1738 case BUILT_IN_MEMCPY_CHK:
1739 case BUILT_IN_MEMPCPY:
1740 case BUILT_IN_MEMPCPY_CHK:
1741 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee), gsi);
1743 case BUILT_IN_STRCAT:
1744 case BUILT_IN_STRCAT_CHK:
1745 handle_builtin_strcat (DECL_FUNCTION_CODE (callee), gsi);
1751 else if (is_gimple_assign (stmt))
1753 tree lhs = gimple_assign_lhs (stmt);
1755 if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (lhs)))
1757 if (gimple_assign_single_p (stmt)
1758 || (gimple_assign_cast_p (stmt)
1759 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt)))))
1761 int idx = get_stridx (gimple_assign_rhs1 (stmt));
1762 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs),
1765 else if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
1766 handle_pointer_plus (gsi);
1768 else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs))
1770 tree type = TREE_TYPE (lhs);
1771 if (TREE_CODE (type) == ARRAY_TYPE)
1772 type = TREE_TYPE (type);
1773 if (TREE_CODE (type) == INTEGER_TYPE
1774 && TYPE_MODE (type) == TYPE_MODE (char_type_node)
1775 && TYPE_PRECISION (type) == TYPE_PRECISION (char_type_node))
1777 if (! handle_char_store (gsi))
1783 if (gimple_vdef (stmt))
1784 maybe_invalidate (stmt);
1788 /* Recursively call maybe_invalidate on stmts that might be executed
1789 in between dombb and current bb and that contain a vdef. Stop when
1790 *count stmts are inspected, or if the whole strinfo vector has
1791 been invalidated. */
1794 do_invalidate (basic_block dombb, gimple phi, bitmap visited, int *count)
1796 unsigned int i, n = gimple_phi_num_args (phi);
1798 for (i = 0; i < n; i++)
1800 tree vuse = gimple_phi_arg_def (phi, i);
1801 gimple stmt = SSA_NAME_DEF_STMT (vuse);
1802 basic_block bb = gimple_bb (stmt);
1805 || !bitmap_set_bit (visited, bb->index)
1806 || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
1810 if (gimple_code (stmt) == GIMPLE_PHI)
1812 do_invalidate (dombb, stmt, visited, count);
1819 if (!maybe_invalidate (stmt))
1824 vuse = gimple_vuse (stmt);
1825 stmt = SSA_NAME_DEF_STMT (vuse);
1826 if (gimple_bb (stmt) != bb)
1828 bb = gimple_bb (stmt);
1831 || !bitmap_set_bit (visited, bb->index)
1832 || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
1839 /* Callback for walk_dominator_tree. Attempt to optimize various
1840 string ops by remembering string lenths pointed by pointer SSA_NAMEs. */
1843 strlen_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1846 gimple_stmt_iterator gsi;
1847 basic_block dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
1850 stridx_to_strinfo = NULL;
1853 stridx_to_strinfo = (VEC(strinfo, heap) *) dombb->aux;
1854 if (stridx_to_strinfo)
1856 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1858 gimple phi = gsi_stmt (gsi);
1859 if (!is_gimple_reg (gimple_phi_result (phi)))
1861 bitmap visited = BITMAP_ALLOC (NULL);
1862 int count_vdef = 100;
1863 do_invalidate (dombb, phi, visited, &count_vdef);
1864 BITMAP_FREE (visited);
1871 /* If all PHI arguments have the same string index, the PHI result
1873 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1875 gimple phi = gsi_stmt (gsi);
1876 tree result = gimple_phi_result (phi);
1877 if (is_gimple_reg (result) && POINTER_TYPE_P (TREE_TYPE (result)))
1879 int idx = get_stridx (gimple_phi_arg_def (phi, 0));
1882 unsigned int i, n = gimple_phi_num_args (phi);
1883 for (i = 1; i < n; i++)
1884 if (idx != get_stridx (gimple_phi_arg_def (phi, i)))
1887 VEC_replace (int, ssa_ver_to_stridx,
1888 SSA_NAME_VERSION (result), idx);
1893 /* Attempt to optimize individual statements. */
1894 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
1895 if (strlen_optimize_stmt (&gsi))
1898 bb->aux = stridx_to_strinfo;
1899 if (VEC_length (strinfo, stridx_to_strinfo) && !strinfo_shared ())
1900 VEC_replace (strinfo, stridx_to_strinfo, 0, (strinfo) bb);
1903 /* Callback for walk_dominator_tree. Free strinfo vector if it is
1904 owned by the current bb, clear bb->aux. */
1907 strlen_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1912 stridx_to_strinfo = (VEC(strinfo, heap) *) bb->aux;
1913 if (VEC_length (strinfo, stridx_to_strinfo)
1914 && VEC_index (strinfo, stridx_to_strinfo, 0) == (strinfo) bb)
1919 for (i = 1; VEC_iterate (strinfo, stridx_to_strinfo, i, si); ++i)
1921 VEC_free (strinfo, heap, stridx_to_strinfo);
1927 /* Main entry point. */
1930 tree_ssa_strlen (void)
1932 struct dom_walk_data walk_data;
1934 VEC_safe_grow_cleared (int, heap, ssa_ver_to_stridx, num_ssa_names);
1936 strinfo_pool = create_alloc_pool ("strinfo_struct pool",
1937 sizeof (struct strinfo_struct), 64);
1939 calculate_dominance_info (CDI_DOMINATORS);
1941 /* String length optimization is implemented as a walk of the dominator
1942 tree and a forward walk of statements within each block. */
1943 walk_data.dom_direction = CDI_DOMINATORS;
1944 walk_data.initialize_block_local_data = NULL;
1945 walk_data.before_dom_children = strlen_enter_block;
1946 walk_data.after_dom_children = strlen_leave_block;
1947 walk_data.block_local_data_size = 0;
1948 walk_data.global_data = NULL;
1950 /* Initialize the dominator walker. */
1951 init_walk_dominator_tree (&walk_data);
1953 /* Recursively walk the dominator tree. */
1954 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1956 /* Finalize the dominator walker. */
1957 fini_walk_dominator_tree (&walk_data);
1959 VEC_free (int, heap, ssa_ver_to_stridx);
1960 free_alloc_pool (strinfo_pool);
1961 if (decl_to_stridxlist_htab)
1963 obstack_free (&stridx_obstack, NULL);
1964 htab_delete (decl_to_stridxlist_htab);
1965 decl_to_stridxlist_htab = NULL;
1967 laststmt.stmt = NULL;
1968 laststmt.len = NULL_TREE;
1969 laststmt.stridx = 0;
1977 return flag_optimize_strlen != 0;
1980 struct gimple_opt_pass pass_strlen =
1984 "strlen", /* name */
1985 gate_strlen, /* gate */
1986 tree_ssa_strlen, /* execute */
1989 0, /* static_pass_number */
1990 TV_TREE_STRLEN, /* tv_id */
1991 PROP_cfg | PROP_ssa, /* properties_required */
1992 0, /* properties_provided */
1993 0, /* properties_destroyed */
1994 0, /* todo_flags_start */
1996 | TODO_verify_ssa /* todo_flags_finish */