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))
697 int *pidx = addr_stridxptr (TREE_OPERAND (ptr, 0));
698 if (pidx != NULL && *pidx == 0)
703 if (POINTER_TYPE_P (TREE_TYPE (ptr)))
710 /* We might find an endptr created in this pass. Grow the
711 vector in that case. */
712 if (VEC_length (int, ssa_ver_to_stridx) <= SSA_NAME_VERSION (ptr))
713 VEC_safe_grow_cleared (int, heap, ssa_ver_to_stridx, num_ssa_names);
715 if (VEC_index (int, ssa_ver_to_stridx, SSA_NAME_VERSION (ptr)) != 0)
717 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (ptr), idx);
721 /* If the last .MEM setter statement before STMT is
722 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
723 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
724 just memcpy (x, y, strlen (y)). SI must be the zero length
728 adjust_last_stmt (strinfo si, gimple stmt, bool is_strcat)
730 tree vuse, callee, len;
731 struct laststmt_struct last = laststmt;
732 strinfo lastsi, firstsi;
734 laststmt.stmt = NULL;
735 laststmt.len = NULL_TREE;
738 if (last.stmt == NULL)
741 vuse = gimple_vuse (stmt);
742 if (vuse == NULL_TREE
743 || SSA_NAME_DEF_STMT (vuse) != last.stmt
744 || !has_single_use (vuse))
747 gcc_assert (last.stridx > 0);
748 lastsi = get_strinfo (last.stridx);
754 if (lastsi->first == 0 || lastsi->first != si->first)
757 firstsi = verify_related_strinfos (si);
760 while (firstsi != lastsi)
763 if (firstsi->next == 0)
765 nextsi = get_strinfo (firstsi->next);
767 || nextsi->prev != firstsi->idx
768 || nextsi->first != si->first)
776 if (si->length == NULL_TREE || !integer_zerop (si->length))
780 if (is_gimple_assign (last.stmt))
782 gimple_stmt_iterator gsi;
784 if (!integer_zerop (gimple_assign_rhs1 (last.stmt)))
786 if (stmt_could_throw_p (last.stmt))
788 gsi = gsi_for_stmt (last.stmt);
789 unlink_stmt_vdef (last.stmt);
790 release_defs (last.stmt);
791 gsi_remove (&gsi, true);
795 if (!is_gimple_call (last.stmt))
797 callee = gimple_call_fndecl (last.stmt);
798 if (callee == NULL_TREE || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL)
801 switch (DECL_FUNCTION_CODE (callee))
803 case BUILT_IN_MEMCPY:
804 case BUILT_IN_MEMCPY_CHK:
810 len = gimple_call_arg (last.stmt, 2);
811 if (host_integerp (len, 1))
813 if (!host_integerp (last.len, 1)
814 || integer_zerop (len)
815 || (unsigned HOST_WIDE_INT) tree_low_cst (len, 1)
816 != (unsigned HOST_WIDE_INT) tree_low_cst (last.len, 1) + 1)
818 /* Don't adjust the length if it is divisible by 4, it is more efficient
819 to store the extra '\0' in that case. */
820 if ((((unsigned HOST_WIDE_INT) tree_low_cst (len, 1)) & 3) == 0)
823 else if (TREE_CODE (len) == SSA_NAME)
825 gimple def_stmt = SSA_NAME_DEF_STMT (len);
826 if (!is_gimple_assign (def_stmt)
827 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
828 || gimple_assign_rhs1 (def_stmt) != last.len
829 || !integer_onep (gimple_assign_rhs2 (def_stmt)))
835 gimple_call_set_arg (last.stmt, 2, last.len);
836 update_stmt (last.stmt);
839 /* Handle a strlen call. If strlen of the argument is known, replace
840 the strlen call with the known value, otherwise remember that strlen
841 of the argument is stored in the lhs SSA_NAME. */
844 handle_builtin_strlen (gimple_stmt_iterator *gsi)
848 gimple stmt = gsi_stmt (*gsi);
849 tree lhs = gimple_call_lhs (stmt);
851 if (lhs == NULL_TREE)
854 src = gimple_call_arg (stmt, 0);
855 idx = get_stridx (src);
862 rhs = build_int_cst (TREE_TYPE (lhs), ~idx);
866 si = get_strinfo (idx);
868 rhs = get_string_length (si);
870 if (rhs != NULL_TREE)
872 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
874 fprintf (dump_file, "Optimizing: ");
875 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
877 rhs = unshare_expr (rhs);
878 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
879 rhs = fold_convert_loc (gimple_location (stmt),
880 TREE_TYPE (lhs), rhs);
881 if (!update_call_from_tree (gsi, rhs))
882 gimplify_and_update_call_from_tree (gsi, rhs);
883 stmt = gsi_stmt (*gsi);
885 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
887 fprintf (dump_file, "into: ");
888 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
891 && TREE_CODE (si->length) != SSA_NAME
892 && TREE_CODE (si->length) != INTEGER_CST
893 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
895 si = unshare_strinfo (si);
901 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
904 idx = new_stridx (src);
905 else if (get_strinfo (idx) != NULL)
909 strinfo si = new_strinfo (src, idx, lhs);
910 set_strinfo (idx, si);
911 find_equal_ptrs (src, idx);
915 /* Handle a strchr call. If strlen of the first argument is known, replace
916 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
917 that lhs of the call is endptr and strlen of the argument is endptr - x. */
920 handle_builtin_strchr (gimple_stmt_iterator *gsi)
924 gimple stmt = gsi_stmt (*gsi);
925 tree lhs = gimple_call_lhs (stmt);
927 if (lhs == NULL_TREE)
930 if (!integer_zerop (gimple_call_arg (stmt, 1)))
933 src = gimple_call_arg (stmt, 0);
934 idx = get_stridx (src);
941 rhs = build_int_cst (size_type_node, ~idx);
945 si = get_strinfo (idx);
947 rhs = get_string_length (si);
949 if (rhs != NULL_TREE)
951 location_t loc = gimple_location (stmt);
953 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
955 fprintf (dump_file, "Optimizing: ");
956 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
958 if (si != NULL && si->endptr != NULL_TREE)
960 rhs = unshare_expr (si->endptr);
961 if (!useless_type_conversion_p (TREE_TYPE (lhs),
963 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
967 rhs = fold_convert_loc (loc, sizetype, unshare_expr (rhs));
968 rhs = fold_build2_loc (loc, POINTER_PLUS_EXPR,
969 TREE_TYPE (src), src, rhs);
970 if (!useless_type_conversion_p (TREE_TYPE (lhs),
972 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
974 if (!update_call_from_tree (gsi, rhs))
975 gimplify_and_update_call_from_tree (gsi, rhs);
976 stmt = gsi_stmt (*gsi);
978 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
980 fprintf (dump_file, "into: ");
981 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
984 && si->endptr == NULL_TREE
985 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
987 si = unshare_strinfo (si);
990 zero_length_string (lhs, si);
994 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
996 if (TREE_CODE (src) != SSA_NAME || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src))
999 idx = new_stridx (src);
1000 else if (get_strinfo (idx) != NULL)
1002 zero_length_string (lhs, NULL);
1007 location_t loc = gimple_location (stmt);
1008 tree lhsu = fold_convert_loc (loc, size_type_node, lhs);
1009 tree srcu = fold_convert_loc (loc, size_type_node, src);
1010 tree length = fold_build2_loc (loc, MINUS_EXPR,
1011 size_type_node, lhsu, srcu);
1012 strinfo si = new_strinfo (src, idx, length);
1014 set_strinfo (idx, si);
1015 find_equal_ptrs (src, idx);
1016 zero_length_string (lhs, si);
1020 zero_length_string (lhs, NULL);
1023 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1024 If strlen of the second argument is known, strlen of the first argument
1025 is the same after this call. Furthermore, attempt to convert it to
1029 handle_builtin_strcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1032 tree src, dst, srclen, len, lhs, args, type, fn, oldlen;
1034 gimple stmt = gsi_stmt (*gsi);
1035 strinfo si, dsi, olddsi, zsi;
1038 src = gimple_call_arg (stmt, 1);
1039 dst = gimple_call_arg (stmt, 0);
1040 lhs = gimple_call_lhs (stmt);
1041 idx = get_stridx (src);
1044 si = get_strinfo (idx);
1046 didx = get_stridx (dst);
1050 olddsi = get_strinfo (didx);
1055 adjust_last_stmt (olddsi, stmt, false);
1059 srclen = get_string_length (si);
1061 srclen = build_int_cst (size_type_node, ~idx);
1063 loc = gimple_location (stmt);
1064 if (srclen == NULL_TREE)
1067 case BUILT_IN_STRCPY:
1068 case BUILT_IN_STRCPY_CHK:
1069 if (implicit_built_in_decls[BUILT_IN_STPCPY] == NULL_TREE
1070 || lhs != NULL_TREE)
1073 case BUILT_IN_STPCPY:
1074 case BUILT_IN_STPCPY_CHK:
1075 if (lhs == NULL_TREE)
1079 tree lhsuint = fold_convert_loc (loc, size_type_node, lhs);
1080 srclen = fold_convert_loc (loc, size_type_node, dst);
1081 srclen = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
1091 didx = new_stridx (dst);
1097 oldlen = olddsi->length;
1098 dsi = unshare_strinfo (olddsi);
1099 dsi->length = srclen;
1100 /* Break the chain, so adjust_related_strinfo on later pointers in
1101 the chain won't adjust this one anymore. */
1104 dsi->endptr = NULL_TREE;
1108 dsi = new_strinfo (dst, didx, srclen);
1109 set_strinfo (didx, dsi);
1110 find_equal_ptrs (dst, didx);
1112 dsi->writable = true;
1113 dsi->dont_invalidate = true;
1115 if (dsi->length == NULL_TREE)
1117 /* If string length of src is unknown, use delayed length
1118 computation. If string lenth of dst will be needed, it
1119 can be computed by transforming this strcpy call into
1120 stpcpy and subtracting dst from the return value. */
1127 tree adj = NULL_TREE;
1128 if (oldlen == NULL_TREE)
1130 else if (integer_zerop (oldlen))
1132 else if (TREE_CODE (oldlen) == INTEGER_CST
1133 || TREE_CODE (srclen) == INTEGER_CST)
1134 adj = fold_build2_loc (loc, MINUS_EXPR,
1135 TREE_TYPE (srclen), srclen,
1136 fold_convert_loc (loc, TREE_TYPE (srclen),
1138 if (adj != NULL_TREE)
1139 adjust_related_strinfos (loc, dsi, adj);
1143 /* strcpy src may not overlap dst, so src doesn't need to be
1144 invalidated either. */
1146 si->dont_invalidate = true;
1152 case BUILT_IN_STRCPY:
1153 fn = implicit_built_in_decls[BUILT_IN_MEMCPY];
1155 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs), didx);
1157 case BUILT_IN_STRCPY_CHK:
1158 fn = built_in_decls[BUILT_IN_MEMCPY_CHK];
1160 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs), didx);
1162 case BUILT_IN_STPCPY:
1163 /* This would need adjustment of the lhs (subtract one),
1164 or detection that the trailing '\0' doesn't need to be
1165 written, if it will be immediately overwritten.
1166 fn = built_in_decls[BUILT_IN_MEMPCPY]; */
1170 zsi = zero_length_string (lhs, dsi);
1173 case BUILT_IN_STPCPY_CHK:
1174 /* This would need adjustment of the lhs (subtract one),
1175 or detection that the trailing '\0' doesn't need to be
1176 written, if it will be immediately overwritten.
1177 fn = built_in_decls[BUILT_IN_MEMPCPY_CHK]; */
1181 zsi = zero_length_string (lhs, dsi);
1188 zsi->dont_invalidate = true;
1190 if (fn == NULL_TREE)
1193 args = TYPE_ARG_TYPES (TREE_TYPE (fn));
1194 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
1196 len = fold_convert_loc (loc, type, unshare_expr (srclen));
1197 len = fold_build2_loc (loc, PLUS_EXPR, type, len, build_int_cst (type, 1));
1198 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
1200 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1202 fprintf (dump_file, "Optimizing: ");
1203 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1205 if (gimple_call_num_args (stmt) == 2)
1206 success = update_gimple_call (gsi, fn, 3, dst, src, len);
1208 success = update_gimple_call (gsi, fn, 4, dst, src, len,
1209 gimple_call_arg (stmt, 2));
1212 stmt = gsi_stmt (*gsi);
1214 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1216 fprintf (dump_file, "into: ");
1217 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1219 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1220 laststmt.stmt = stmt;
1221 laststmt.len = srclen;
1222 laststmt.stridx = dsi->idx;
1224 else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1225 fprintf (dump_file, "not possible.\n");
1228 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
1229 If strlen of the second argument is known and length of the third argument
1230 is that plus one, strlen of the first argument is the same after this
1234 handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1237 tree src, dst, len, lhs, oldlen, newlen;
1238 gimple stmt = gsi_stmt (*gsi);
1239 strinfo si, dsi, olddsi;
1241 len = gimple_call_arg (stmt, 2);
1242 src = gimple_call_arg (stmt, 1);
1243 dst = gimple_call_arg (stmt, 0);
1244 idx = get_stridx (src);
1248 didx = get_stridx (dst);
1251 olddsi = get_strinfo (didx);
1256 && host_integerp (len, 1)
1257 && !integer_zerop (len))
1258 adjust_last_stmt (olddsi, stmt, false);
1264 /* Handle memcpy (x, y, l) where l is strlen (y) + 1. */
1265 si = get_strinfo (idx);
1266 if (si == NULL || si->length == NULL_TREE)
1268 if (TREE_CODE (len) != SSA_NAME)
1270 def_stmt = SSA_NAME_DEF_STMT (len);
1271 if (!is_gimple_assign (def_stmt)
1272 || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR
1273 || gimple_assign_rhs1 (def_stmt) != si->length
1274 || !integer_onep (gimple_assign_rhs2 (def_stmt)))
1280 /* Handle memcpy (x, "abcd", 5) or
1281 memcpy (x, "abc\0uvw", 7). */
1282 if (!host_integerp (len, 1)
1283 || (unsigned HOST_WIDE_INT) tree_low_cst (len, 1)
1284 <= (unsigned HOST_WIDE_INT) ~idx)
1288 if (olddsi != NULL && TREE_CODE (len) == SSA_NAME)
1289 adjust_last_stmt (olddsi, stmt, false);
1293 didx = new_stridx (dst);
1298 newlen = si->length;
1300 newlen = build_int_cst (TREE_TYPE (len), ~idx);
1304 dsi = unshare_strinfo (olddsi);
1305 oldlen = olddsi->length;
1306 dsi->length = newlen;
1307 /* Break the chain, so adjust_related_strinfo on later pointers in
1308 the chain won't adjust this one anymore. */
1311 dsi->endptr = NULL_TREE;
1315 dsi = new_strinfo (dst, didx, newlen);
1316 set_strinfo (didx, dsi);
1317 find_equal_ptrs (dst, didx);
1319 dsi->writable = true;
1320 dsi->dont_invalidate = true;
1323 tree adj = NULL_TREE;
1324 location_t loc = gimple_location (stmt);
1325 if (oldlen == NULL_TREE)
1327 else if (integer_zerop (oldlen))
1329 else if (TREE_CODE (oldlen) == INTEGER_CST
1330 || TREE_CODE (dsi->length) == INTEGER_CST)
1331 adj = fold_build2_loc (loc, MINUS_EXPR,
1332 TREE_TYPE (dsi->length), dsi->length,
1333 fold_convert_loc (loc, TREE_TYPE (dsi->length),
1335 if (adj != NULL_TREE)
1336 adjust_related_strinfos (loc, dsi, adj);
1340 /* memcpy src may not overlap dst, so src doesn't need to be
1341 invalidated either. */
1343 si->dont_invalidate = true;
1345 lhs = gimple_call_lhs (stmt);
1348 case BUILT_IN_MEMCPY:
1349 case BUILT_IN_MEMCPY_CHK:
1350 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1351 laststmt.stmt = stmt;
1352 laststmt.len = dsi->length;
1353 laststmt.stridx = dsi->idx;
1355 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs), didx);
1357 case BUILT_IN_MEMPCPY:
1358 case BUILT_IN_MEMPCPY_CHK:
1365 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
1366 If strlen of the second argument is known, strlen of the first argument
1367 is increased by the length of the second argument. Furthermore, attempt
1368 to convert it to memcpy/strcpy if the length of the first argument
1372 handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi)
1375 tree src, dst, srclen, dstlen, len, lhs, args, type, fn, objsz, endptr;
1377 gimple stmt = gsi_stmt (*gsi);
1381 src = gimple_call_arg (stmt, 1);
1382 dst = gimple_call_arg (stmt, 0);
1383 lhs = gimple_call_lhs (stmt);
1385 didx = get_stridx (dst);
1391 dsi = get_strinfo (didx);
1392 if (dsi == NULL || get_string_length (dsi) == NULL_TREE)
1394 /* strcat (p, q) can be transformed into
1395 tmp = p + strlen (p); endptr = strpcpy (tmp, q);
1396 with length endptr - p if we need to compute the length
1397 later on. Don't do this transformation if we don't need
1399 if (implicit_built_in_decls[BUILT_IN_STPCPY] != NULL_TREE
1400 && lhs == NULL_TREE)
1404 didx = new_stridx (dst);
1410 dsi = new_strinfo (dst, didx, NULL_TREE);
1411 set_strinfo (didx, dsi);
1412 find_equal_ptrs (dst, didx);
1416 dsi = unshare_strinfo (dsi);
1417 dsi->length = NULL_TREE;
1419 dsi->endptr = NULL_TREE;
1421 dsi->writable = true;
1423 dsi->dont_invalidate = true;
1430 idx = get_stridx (src);
1432 srclen = build_int_cst (size_type_node, ~idx);
1435 si = get_strinfo (idx);
1437 srclen = get_string_length (si);
1440 loc = gimple_location (stmt);
1441 dstlen = dsi->length;
1442 endptr = dsi->endptr;
1444 dsi = unshare_strinfo (dsi);
1445 dsi->endptr = NULL_TREE;
1447 dsi->writable = true;
1449 if (srclen != NULL_TREE)
1451 dsi->length = fold_build2_loc (loc, PLUS_EXPR, TREE_TYPE (dsi->length),
1452 dsi->length, srclen);
1453 adjust_related_strinfos (loc, dsi, srclen);
1454 dsi->dont_invalidate = true;
1459 if (implicit_built_in_decls[BUILT_IN_STPCPY] != NULL_TREE
1460 && lhs == NULL_TREE)
1461 dsi->dont_invalidate = true;
1465 /* strcat src may not overlap dst, so src doesn't need to be
1466 invalidated either. */
1467 si->dont_invalidate = true;
1469 /* For now. Could remove the lhs from the call and add
1470 lhs = dst; afterwards. */
1478 case BUILT_IN_STRCAT:
1479 if (srclen != NULL_TREE)
1480 fn = implicit_built_in_decls[BUILT_IN_MEMCPY];
1482 fn = implicit_built_in_decls[BUILT_IN_STRCPY];
1484 case BUILT_IN_STRCAT_CHK:
1485 if (srclen != NULL_TREE)
1486 fn = built_in_decls[BUILT_IN_MEMCPY_CHK];
1488 fn = built_in_decls[BUILT_IN_STRCPY_CHK];
1489 objsz = gimple_call_arg (stmt, 2);
1495 if (fn == NULL_TREE)
1499 if (srclen != NULL_TREE)
1501 args = TYPE_ARG_TYPES (TREE_TYPE (fn));
1502 type = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args)));
1504 len = fold_convert_loc (loc, type, unshare_expr (srclen));
1505 len = fold_build2_loc (loc, PLUS_EXPR, type, len,
1506 build_int_cst (type, 1));
1507 len = force_gimple_operand_gsi (gsi, len, true, NULL_TREE, true,
1511 dst = fold_convert_loc (loc, TREE_TYPE (dst), unshare_expr (endptr));
1513 dst = fold_build2_loc (loc, POINTER_PLUS_EXPR,
1514 TREE_TYPE (dst), unshare_expr (dst),
1515 fold_convert_loc (loc, sizetype,
1516 unshare_expr (dstlen)));
1517 dst = force_gimple_operand_gsi (gsi, dst, true, NULL_TREE, true,
1519 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1521 fprintf (dump_file, "Optimizing: ");
1522 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1524 if (srclen != NULL_TREE)
1525 success = update_gimple_call (gsi, fn, 3 + (objsz != NULL_TREE),
1526 dst, src, len, objsz);
1528 success = update_gimple_call (gsi, fn, 2 + (objsz != NULL_TREE),
1532 stmt = gsi_stmt (*gsi);
1534 if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1536 fprintf (dump_file, "into: ");
1537 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1539 /* If srclen == NULL, note that current string length can be
1540 computed by transforming this strcpy into stpcpy. */
1541 if (srclen == NULL_TREE && dsi->dont_invalidate)
1543 adjust_last_stmt (dsi, stmt, true);
1544 if (srclen != NULL_TREE)
1546 laststmt.stmt = stmt;
1547 laststmt.len = srclen;
1548 laststmt.stridx = dsi->idx;
1551 else if (dump_file && (dump_flags & TDF_DETAILS) != 0)
1552 fprintf (dump_file, "not possible.\n");
1555 /* Handle a POINTER_PLUS_EXPR statement.
1556 For p = "abcd" + 2; compute associated length, or if
1557 p = q + off is pointing to a '\0' character of a string, call
1558 zero_length_string on it. */
1561 handle_pointer_plus (gimple_stmt_iterator *gsi)
1563 gimple stmt = gsi_stmt (*gsi);
1564 tree lhs = gimple_assign_lhs (stmt), off;
1565 int idx = get_stridx (gimple_assign_rhs1 (stmt));
1573 tree off = gimple_assign_rhs2 (stmt);
1574 if (host_integerp (off, 1)
1575 && (unsigned HOST_WIDE_INT) tree_low_cst (off, 1)
1576 <= (unsigned HOST_WIDE_INT) ~idx)
1577 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs),
1578 ~(~idx - (int) tree_low_cst (off, 1)));
1582 si = get_strinfo (idx);
1583 if (si == NULL || si->length == NULL_TREE)
1586 off = gimple_assign_rhs2 (stmt);
1588 if (operand_equal_p (si->length, off, 0))
1589 zsi = zero_length_string (lhs, si);
1590 else if (TREE_CODE (off) == SSA_NAME)
1592 gimple def_stmt = SSA_NAME_DEF_STMT (off);
1593 if (gimple_assign_single_p (def_stmt)
1594 && operand_equal_p (si->length, gimple_assign_rhs1 (def_stmt), 0))
1595 zsi = zero_length_string (lhs, si);
1598 && si->endptr != NULL_TREE
1599 && si->endptr != lhs
1600 && TREE_CODE (si->endptr) == SSA_NAME)
1602 enum tree_code rhs_code
1603 = useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (si->endptr))
1604 ? SSA_NAME : NOP_EXPR;
1605 gimple_assign_set_rhs_with_ops (gsi, rhs_code, si->endptr, NULL_TREE);
1606 gcc_assert (gsi_stmt (*gsi) == stmt);
1611 /* Handle a single character store. */
1614 handle_char_store (gimple_stmt_iterator *gsi)
1618 gimple stmt = gsi_stmt (*gsi);
1619 tree ssaname = NULL_TREE, lhs = gimple_assign_lhs (stmt);
1621 if (TREE_CODE (lhs) == MEM_REF
1622 && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME)
1624 if (integer_zerop (TREE_OPERAND (lhs, 1)))
1626 ssaname = TREE_OPERAND (lhs, 0);
1627 idx = get_stridx (ssaname);
1631 idx = get_addr_stridx (lhs);
1635 si = get_strinfo (idx);
1636 if (si != NULL && si->length != NULL_TREE && integer_zerop (si->length))
1638 if (initializer_zerop (gimple_assign_rhs1 (stmt)))
1640 /* When storing '\0', the store can be removed
1641 if we know it has been stored in the current function. */
1642 if (!stmt_could_throw_p (stmt) && si->writable)
1644 unlink_stmt_vdef (stmt);
1645 release_defs (stmt);
1646 gsi_remove (gsi, true);
1651 si->writable = true;
1652 si->dont_invalidate = true;
1656 /* Otherwise this statement overwrites the '\0' with
1657 something, if the previous stmt was a memcpy,
1658 its length may be decreased. */
1659 adjust_last_stmt (si, stmt, false);
1661 else if (si != NULL)
1663 si = unshare_strinfo (si);
1664 si->length = build_int_cst (size_type_node, 0);
1670 si->writable = true;
1671 if (ssaname && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname))
1672 si->endptr = ssaname;
1673 si->dont_invalidate = true;
1676 else if (idx == 0 && initializer_zerop (gimple_assign_rhs1 (stmt)))
1680 si = zero_length_string (ssaname, NULL);
1682 si->dont_invalidate = true;
1686 int idx = new_addr_stridx (lhs);
1689 si = new_strinfo (build_fold_addr_expr (lhs), idx,
1690 build_int_cst (size_type_node, 0));
1691 set_strinfo (idx, si);
1692 si->dont_invalidate = true;
1696 si->writable = true;
1699 if (si != NULL && initializer_zerop (gimple_assign_rhs1 (stmt)))
1701 /* Allow adjust_last_stmt to remove it if the stored '\0'
1702 is immediately overwritten. */
1703 laststmt.stmt = stmt;
1704 laststmt.len = build_int_cst (size_type_node, 1);
1705 laststmt.stridx = si->idx;
1710 /* Attempt to optimize a single statement at *GSI using string length
1714 strlen_optimize_stmt (gimple_stmt_iterator *gsi)
1716 gimple stmt = gsi_stmt (*gsi);
1718 if (is_gimple_call (stmt))
1720 tree callee = gimple_call_fndecl (stmt);
1721 if (callee && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
1722 switch (DECL_FUNCTION_CODE (callee))
1724 case BUILT_IN_STRLEN:
1725 handle_builtin_strlen (gsi);
1727 case BUILT_IN_STRCHR:
1728 handle_builtin_strchr (gsi);
1730 case BUILT_IN_STRCPY:
1731 case BUILT_IN_STRCPY_CHK:
1732 case BUILT_IN_STPCPY:
1733 case BUILT_IN_STPCPY_CHK:
1734 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee), gsi);
1736 case BUILT_IN_MEMCPY:
1737 case BUILT_IN_MEMCPY_CHK:
1738 case BUILT_IN_MEMPCPY:
1739 case BUILT_IN_MEMPCPY_CHK:
1740 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee), gsi);
1742 case BUILT_IN_STRCAT:
1743 case BUILT_IN_STRCAT_CHK:
1744 handle_builtin_strcat (DECL_FUNCTION_CODE (callee), gsi);
1750 else if (is_gimple_assign (stmt))
1752 tree lhs = gimple_assign_lhs (stmt);
1754 if (TREE_CODE (lhs) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (lhs)))
1756 if (gimple_assign_single_p (stmt)
1757 || (gimple_assign_cast_p (stmt)
1758 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt)))))
1760 int idx = get_stridx (gimple_assign_rhs1 (stmt));
1761 VEC_replace (int, ssa_ver_to_stridx, SSA_NAME_VERSION (lhs),
1764 else if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
1765 handle_pointer_plus (gsi);
1767 else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs))
1769 tree type = TREE_TYPE (lhs);
1770 if (TREE_CODE (type) == ARRAY_TYPE)
1771 type = TREE_TYPE (type);
1772 if (TREE_CODE (type) == INTEGER_TYPE
1773 && TYPE_MODE (type) == TYPE_MODE (char_type_node)
1774 && TYPE_PRECISION (type) == TYPE_PRECISION (char_type_node))
1776 if (! handle_char_store (gsi))
1782 if (gimple_vdef (stmt))
1783 maybe_invalidate (stmt);
1787 /* Recursively call maybe_invalidate on stmts that might be executed
1788 in between dombb and current bb and that contain a vdef. Stop when
1789 *count stmts are inspected, or if the whole strinfo vector has
1790 been invalidated. */
1793 do_invalidate (basic_block dombb, gimple phi, bitmap visited, int *count)
1795 unsigned int i, n = gimple_phi_num_args (phi);
1797 for (i = 0; i < n; i++)
1799 tree vuse = gimple_phi_arg_def (phi, i);
1800 gimple stmt = SSA_NAME_DEF_STMT (vuse);
1801 basic_block bb = gimple_bb (stmt);
1804 || !bitmap_set_bit (visited, bb->index)
1805 || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
1809 if (gimple_code (stmt) == GIMPLE_PHI)
1811 do_invalidate (dombb, stmt, visited, count);
1818 if (!maybe_invalidate (stmt))
1823 vuse = gimple_vuse (stmt);
1824 stmt = SSA_NAME_DEF_STMT (vuse);
1825 if (gimple_bb (stmt) != bb)
1827 bb = gimple_bb (stmt);
1830 || !bitmap_set_bit (visited, bb->index)
1831 || !dominated_by_p (CDI_DOMINATORS, bb, dombb))
1838 /* Callback for walk_dominator_tree. Attempt to optimize various
1839 string ops by remembering string lenths pointed by pointer SSA_NAMEs. */
1842 strlen_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1845 gimple_stmt_iterator gsi;
1846 basic_block dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
1849 stridx_to_strinfo = NULL;
1852 stridx_to_strinfo = (VEC(strinfo, heap) *) dombb->aux;
1853 if (stridx_to_strinfo)
1855 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1857 gimple phi = gsi_stmt (gsi);
1858 if (!is_gimple_reg (gimple_phi_result (phi)))
1860 bitmap visited = BITMAP_ALLOC (NULL);
1861 int count_vdef = 100;
1862 do_invalidate (dombb, phi, visited, &count_vdef);
1863 BITMAP_FREE (visited);
1870 /* If all PHI arguments have the same string index, the PHI result
1872 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1874 gimple phi = gsi_stmt (gsi);
1875 tree result = gimple_phi_result (phi);
1876 if (is_gimple_reg (result) && POINTER_TYPE_P (TREE_TYPE (result)))
1878 int idx = get_stridx (gimple_phi_arg_def (phi, 0));
1881 unsigned int i, n = gimple_phi_num_args (phi);
1882 for (i = 1; i < n; i++)
1883 if (idx != get_stridx (gimple_phi_arg_def (phi, i)))
1886 VEC_replace (int, ssa_ver_to_stridx,
1887 SSA_NAME_VERSION (result), idx);
1892 /* Attempt to optimize individual statements. */
1893 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
1894 if (strlen_optimize_stmt (&gsi))
1897 bb->aux = stridx_to_strinfo;
1898 if (VEC_length (strinfo, stridx_to_strinfo) && !strinfo_shared ())
1899 VEC_replace (strinfo, stridx_to_strinfo, 0, (strinfo) bb);
1902 /* Callback for walk_dominator_tree. Free strinfo vector if it is
1903 owned by the current bb, clear bb->aux. */
1906 strlen_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1911 stridx_to_strinfo = (VEC(strinfo, heap) *) bb->aux;
1912 if (VEC_length (strinfo, stridx_to_strinfo)
1913 && VEC_index (strinfo, stridx_to_strinfo, 0) == (strinfo) bb)
1918 for (i = 1; VEC_iterate (strinfo, stridx_to_strinfo, i, si); ++i)
1920 VEC_free (strinfo, heap, stridx_to_strinfo);
1926 /* Main entry point. */
1929 tree_ssa_strlen (void)
1931 struct dom_walk_data walk_data;
1933 VEC_safe_grow_cleared (int, heap, ssa_ver_to_stridx, num_ssa_names);
1935 strinfo_pool = create_alloc_pool ("strinfo_struct pool",
1936 sizeof (struct strinfo_struct), 64);
1938 calculate_dominance_info (CDI_DOMINATORS);
1940 /* String length optimization is implemented as a walk of the dominator
1941 tree and a forward walk of statements within each block. */
1942 walk_data.dom_direction = CDI_DOMINATORS;
1943 walk_data.initialize_block_local_data = NULL;
1944 walk_data.before_dom_children = strlen_enter_block;
1945 walk_data.after_dom_children = strlen_leave_block;
1946 walk_data.block_local_data_size = 0;
1947 walk_data.global_data = NULL;
1949 /* Initialize the dominator walker. */
1950 init_walk_dominator_tree (&walk_data);
1952 /* Recursively walk the dominator tree. */
1953 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
1955 /* Finalize the dominator walker. */
1956 fini_walk_dominator_tree (&walk_data);
1958 VEC_free (int, heap, ssa_ver_to_stridx);
1959 free_alloc_pool (strinfo_pool);
1960 if (decl_to_stridxlist_htab)
1962 obstack_free (&stridx_obstack, NULL);
1963 htab_delete (decl_to_stridxlist_htab);
1964 decl_to_stridxlist_htab = NULL;
1966 laststmt.stmt = NULL;
1967 laststmt.len = NULL_TREE;
1968 laststmt.stridx = 0;
1976 return flag_optimize_strlen != 0;
1979 struct gimple_opt_pass pass_strlen =
1983 "strlen", /* name */
1984 gate_strlen, /* gate */
1985 tree_ssa_strlen, /* execute */
1988 0, /* static_pass_number */
1989 TV_TREE_STRLEN, /* tv_id */
1990 PROP_cfg | PROP_ssa, /* properties_required */
1991 0, /* properties_provided */
1992 0, /* properties_destroyed */
1993 0, /* todo_flags_start */
1995 | TODO_verify_ssa /* todo_flags_finish */