1 /* String length optimization
2 Copyright (C) 2011-2014 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"
25 #include "stor-layout.h"
26 #include "hash-table.h"
29 #include "basic-block.h"
30 #include "tree-ssa-alias.h"
31 #include "internal-fn.h"
32 #include "gimple-fold.h"
34 #include "gimple-expr.h"
38 #include "gimple-iterator.h"
39 #include "gimplify-me.h"
40 #include "gimple-ssa.h"
41 #include "tree-phinodes.h"
42 #include "ssa-iterators.h"
43 #include "stringpool.h"
44 #include "tree-ssanames.h"
47 #include "tree-pass.h"
49 #include "alloc-pool.h"
50 #include "tree-ssa-propagate.h"
51 #include "gimple-pretty-print.h"
55 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
56 is an index into strinfo vector, negative value stands for
57 string length of a string literal (~strlen). */
58 static vec
<int> ssa_ver_to_stridx
;
60 /* Number of currently active string indexes plus one. */
61 static int max_stridx
;
63 /* String information record. */
64 typedef struct strinfo_struct
66 /* String length of this string. */
68 /* Any of the corresponding pointers for querying alias oracle. */
70 /* Statement for delayed length computation. */
72 /* Pointer to '\0' if known, if NULL, it can be computed as
75 /* Reference count. Any changes to strinfo entry possibly shared
76 with dominating basic blocks need unshare_strinfo first, except
77 for dont_invalidate which affects only the immediately next
80 /* Copy of index. get_strinfo (si->idx) should return si; */
82 /* These 3 fields are for chaining related string pointers together.
84 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
85 strcpy (c, d); e = c + dl;
86 strinfo(a) -> strinfo(c) -> strinfo(e)
87 All have ->first field equal to strinfo(a)->idx and are doubly
88 chained through prev/next fields. The later strinfos are required
89 to point into the same string with zero or more bytes after
90 the previous pointer and all bytes in between the two pointers
91 must be non-zero. Functions like strcpy or memcpy are supposed
92 to adjust all previous strinfo lengths, but not following strinfo
93 lengths (those are uncertain, usually invalidated during
94 maybe_invalidate, except when the alias oracle knows better).
95 Functions like strcat on the other side adjust the whole
96 related strinfo chain.
97 They are updated lazily, so to use the chain the same first fields
98 and si->prev->next == si->idx needs to be verified. */
102 /* A flag whether the string is known to be written in the current
105 /* A flag for the next maybe_invalidate that this strinfo shouldn't
106 be invalidated. Always cleared by maybe_invalidate. */
107 bool dont_invalidate
;
110 /* Pool for allocating strinfo_struct entries. */
111 static alloc_pool strinfo_pool
;
113 /* Vector mapping positive string indexes to strinfo, for the
114 current basic block. The first pointer in the vector is special,
115 it is either NULL, meaning the vector isn't shared, or it is
116 a basic block pointer to the owner basic_block if shared.
117 If some other bb wants to modify the vector, the vector needs
118 to be unshared first, and only the owner bb is supposed to free it. */
119 static vec
<strinfo
, va_heap
, vl_embed
> *stridx_to_strinfo
;
121 /* One OFFSET->IDX mapping. */
124 struct stridxlist
*next
;
125 HOST_WIDE_INT offset
;
129 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
130 struct decl_stridxlist_map
132 struct tree_map_base base
;
133 struct stridxlist list
;
136 /* stridxlist hashtable helpers. */
138 struct stridxlist_hash_traits
: default_hashmap_traits
140 static inline hashval_t
hash (tree
);
143 /* Hash a from tree in a decl_stridxlist_map. */
146 stridxlist_hash_traits::hash (tree item
)
148 return DECL_UID (item
);
151 /* Hash table for mapping decls to a chained list of offset -> idx
153 static hash_map
<tree
, stridxlist
, stridxlist_hash_traits
>
154 *decl_to_stridxlist_htab
;
156 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
157 static struct obstack stridx_obstack
;
159 /* Last memcpy statement if it could be adjusted if the trailing
160 '\0' written is immediately overwritten, or
161 *x = '\0' store that could be removed if it is immediately overwritten. */
162 struct laststmt_struct
169 /* Helper function for get_stridx. */
172 get_addr_stridx (tree exp
)
175 struct stridxlist
*list
;
178 if (!decl_to_stridxlist_htab
)
181 base
= get_addr_base_and_unit_offset (exp
, &off
);
182 if (base
== NULL
|| !DECL_P (base
))
185 list
= decl_to_stridxlist_htab
->get (base
);
191 if (list
->offset
== off
)
199 /* Return string index for EXP. */
202 get_stridx (tree exp
)
206 if (TREE_CODE (exp
) == SSA_NAME
)
207 return ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)];
209 if (TREE_CODE (exp
) == ADDR_EXPR
)
211 int idx
= get_addr_stridx (TREE_OPERAND (exp
, 0));
216 s
= string_constant (exp
, &o
);
218 && (o
== NULL_TREE
|| tree_fits_shwi_p (o
))
219 && TREE_STRING_LENGTH (s
) > 0)
221 HOST_WIDE_INT offset
= o
? tree_to_shwi (o
) : 0;
222 const char *p
= TREE_STRING_POINTER (s
);
223 int max
= TREE_STRING_LENGTH (s
) - 1;
225 if (p
[max
] == '\0' && offset
>= 0 && offset
<= max
)
226 return ~(int) strlen (p
+ offset
);
231 /* Return true if strinfo vector is shared with the immediate dominator. */
234 strinfo_shared (void)
236 return vec_safe_length (stridx_to_strinfo
)
237 && (*stridx_to_strinfo
)[0] != NULL
;
240 /* Unshare strinfo vector that is shared with the immediate dominator. */
243 unshare_strinfo_vec (void)
248 gcc_assert (strinfo_shared ());
249 stridx_to_strinfo
= vec_safe_copy (stridx_to_strinfo
);
250 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
253 (*stridx_to_strinfo
)[0] = NULL
;
256 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
257 Return a pointer to the location where the string index can
258 be stored (if 0) or is stored, or NULL if this can't be tracked. */
261 addr_stridxptr (tree exp
)
265 tree base
= get_addr_base_and_unit_offset (exp
, &off
);
266 if (base
== NULL_TREE
|| !DECL_P (base
))
269 if (!decl_to_stridxlist_htab
)
271 decl_to_stridxlist_htab
272 = new hash_map
<tree
, stridxlist
, stridxlist_hash_traits
> (64);
273 gcc_obstack_init (&stridx_obstack
);
277 stridxlist
*list
= &decl_to_stridxlist_htab
->get_or_insert (base
, &existed
);
281 for (i
= 0; i
< 16; i
++)
283 if (list
->offset
== off
)
285 if (list
->next
== NULL
)
290 list
->next
= XOBNEW (&stridx_obstack
, struct stridxlist
);
300 /* Create a new string index, or return 0 if reached limit. */
303 new_stridx (tree exp
)
306 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
308 if (TREE_CODE (exp
) == SSA_NAME
)
310 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
))
313 ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)] = idx
;
316 if (TREE_CODE (exp
) == ADDR_EXPR
)
318 int *pidx
= addr_stridxptr (TREE_OPERAND (exp
, 0));
321 gcc_assert (*pidx
== 0);
322 *pidx
= max_stridx
++;
329 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
332 new_addr_stridx (tree exp
)
335 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
337 pidx
= addr_stridxptr (exp
);
340 gcc_assert (*pidx
== 0);
341 *pidx
= max_stridx
++;
347 /* Create a new strinfo. */
350 new_strinfo (tree ptr
, int idx
, tree length
)
352 strinfo si
= (strinfo
) pool_alloc (strinfo_pool
);
356 si
->endptr
= NULL_TREE
;
362 si
->writable
= false;
363 si
->dont_invalidate
= false;
367 /* Decrease strinfo refcount and free it if not referenced anymore. */
370 free_strinfo (strinfo si
)
372 if (si
&& --si
->refcount
== 0)
373 pool_free (strinfo_pool
, si
);
376 /* Return strinfo vector entry IDX. */
378 static inline strinfo
379 get_strinfo (int idx
)
381 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
383 return (*stridx_to_strinfo
)[idx
];
386 /* Set strinfo in the vector entry IDX to SI. */
389 set_strinfo (int idx
, strinfo si
)
391 if (vec_safe_length (stridx_to_strinfo
) && (*stridx_to_strinfo
)[0])
392 unshare_strinfo_vec ();
393 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
394 vec_safe_grow_cleared (stridx_to_strinfo
, idx
+ 1);
395 (*stridx_to_strinfo
)[idx
] = si
;
398 /* Return string length, or NULL if it can't be computed. */
401 get_string_length (strinfo si
)
408 gimple stmt
= si
->stmt
, lenstmt
;
409 tree callee
, lhs
, fn
, tem
;
411 gimple_stmt_iterator gsi
;
413 gcc_assert (is_gimple_call (stmt
));
414 callee
= gimple_call_fndecl (stmt
);
415 gcc_assert (callee
&& DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
);
416 lhs
= gimple_call_lhs (stmt
);
417 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY
));
418 /* unshare_strinfo is intentionally not called here. The (delayed)
419 transformation of strcpy or strcat into stpcpy is done at the place
420 of the former strcpy/strcat call and so can affect all the strinfos
421 with the same stmt. If they were unshared before and transformation
422 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
423 just compute the right length. */
424 switch (DECL_FUNCTION_CODE (callee
))
426 case BUILT_IN_STRCAT
:
427 case BUILT_IN_STRCAT_CHK
:
428 gsi
= gsi_for_stmt (stmt
);
429 fn
= builtin_decl_implicit (BUILT_IN_STRLEN
);
430 gcc_assert (lhs
== NULL_TREE
);
431 tem
= unshare_expr (gimple_call_arg (stmt
, 0));
432 lenstmt
= gimple_build_call (fn
, 1, tem
);
433 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), lenstmt
);
434 gimple_call_set_lhs (lenstmt
, lhs
);
435 gimple_set_vuse (lenstmt
, gimple_vuse (stmt
));
436 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
437 tem
= gimple_call_arg (stmt
, 0);
438 if (!ptrofftype_p (TREE_TYPE (lhs
)))
440 lhs
= convert_to_ptrofftype (lhs
);
441 lhs
= force_gimple_operand_gsi (&gsi
, lhs
, true, NULL_TREE
,
442 true, GSI_SAME_STMT
);
445 = gimple_build_assign_with_ops
447 make_ssa_name (TREE_TYPE (gimple_call_arg (stmt
, 0)), NULL
),
449 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
450 gimple_call_set_arg (stmt
, 0, gimple_assign_lhs (lenstmt
));
453 case BUILT_IN_STRCPY
:
454 case BUILT_IN_STRCPY_CHK
:
455 if (gimple_call_num_args (stmt
) == 2)
456 fn
= builtin_decl_implicit (BUILT_IN_STPCPY
);
458 fn
= builtin_decl_explicit (BUILT_IN_STPCPY_CHK
);
459 gcc_assert (lhs
== NULL_TREE
);
460 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
462 fprintf (dump_file
, "Optimizing: ");
463 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
465 gimple_call_set_fndecl (stmt
, fn
);
466 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), stmt
);
467 gimple_call_set_lhs (stmt
, lhs
);
469 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
471 fprintf (dump_file
, "into: ");
472 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
475 case BUILT_IN_STPCPY
:
476 case BUILT_IN_STPCPY_CHK
:
477 gcc_assert (lhs
!= NULL_TREE
);
478 loc
= gimple_location (stmt
);
481 lhs
= fold_convert_loc (loc
, size_type_node
, lhs
);
482 si
->length
= fold_convert_loc (loc
, size_type_node
, si
->ptr
);
483 si
->length
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
495 /* Invalidate string length information for strings whose length
496 might change due to stores in stmt. */
499 maybe_invalidate (gimple stmt
)
503 bool nonempty
= false;
505 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
508 if (!si
->dont_invalidate
)
511 ao_ref_init_from_ptr_and_size (&r
, si
->ptr
, NULL_TREE
);
512 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
514 set_strinfo (i
, NULL
);
519 si
->dont_invalidate
= false;
525 /* Unshare strinfo record SI, if it has recount > 1 or
526 if stridx_to_strinfo vector is shared with some other
530 unshare_strinfo (strinfo si
)
534 if (si
->refcount
== 1 && !strinfo_shared ())
537 nsi
= new_strinfo (si
->ptr
, si
->idx
, si
->length
);
538 nsi
->stmt
= si
->stmt
;
539 nsi
->endptr
= si
->endptr
;
540 nsi
->first
= si
->first
;
541 nsi
->prev
= si
->prev
;
542 nsi
->next
= si
->next
;
543 nsi
->writable
= si
->writable
;
544 set_strinfo (si
->idx
, nsi
);
549 /* Return first strinfo in the related strinfo chain
550 if all strinfos in between belong to the chain, otherwise
554 verify_related_strinfos (strinfo origsi
)
556 strinfo si
= origsi
, psi
;
558 if (origsi
->first
== 0)
560 for (; si
->prev
; si
= psi
)
562 if (si
->first
!= origsi
->first
)
564 psi
= get_strinfo (si
->prev
);
567 if (psi
->next
!= si
->idx
)
570 if (si
->idx
!= si
->first
)
575 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
576 to a zero-length string and if possible chain it to a related strinfo
577 chain whose part is or might be CHAINSI. */
580 zero_length_string (tree ptr
, strinfo chainsi
)
584 gcc_checking_assert (TREE_CODE (ptr
) == SSA_NAME
585 && get_stridx (ptr
) == 0);
587 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
591 si
= verify_related_strinfos (chainsi
);
595 for (; chainsi
->next
; chainsi
= si
)
597 if (chainsi
->endptr
== NULL_TREE
)
599 chainsi
= unshare_strinfo (chainsi
);
600 chainsi
->endptr
= ptr
;
602 si
= get_strinfo (chainsi
->next
);
604 || si
->first
!= chainsi
->first
605 || si
->prev
!= chainsi
->idx
)
608 gcc_assert (chainsi
->length
|| chainsi
->stmt
);
609 if (chainsi
->endptr
== NULL_TREE
)
611 chainsi
= unshare_strinfo (chainsi
);
612 chainsi
->endptr
= ptr
;
614 if (chainsi
->length
&& integer_zerop (chainsi
->length
))
618 chainsi
= unshare_strinfo (chainsi
);
621 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = chainsi
->idx
;
625 else if (chainsi
->first
|| chainsi
->prev
|| chainsi
->next
)
627 chainsi
= unshare_strinfo (chainsi
);
633 idx
= new_stridx (ptr
);
636 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, 0));
637 set_strinfo (idx
, si
);
641 chainsi
= unshare_strinfo (chainsi
);
642 if (chainsi
->first
== 0)
643 chainsi
->first
= chainsi
->idx
;
645 if (chainsi
->endptr
== NULL_TREE
)
646 chainsi
->endptr
= ptr
;
647 si
->prev
= chainsi
->idx
;
648 si
->first
= chainsi
->first
;
649 si
->writable
= chainsi
->writable
;
654 /* For strinfo ORIGSI whose length has been just updated
655 update also related strinfo lengths (add ADJ to each,
656 but don't adjust ORIGSI). */
659 adjust_related_strinfos (location_t loc
, strinfo origsi
, tree adj
)
661 strinfo si
= verify_related_strinfos (origsi
);
674 si
= unshare_strinfo (si
);
677 tem
= fold_convert_loc (loc
, TREE_TYPE (si
->length
), adj
);
678 si
->length
= fold_build2_loc (loc
, PLUS_EXPR
,
679 TREE_TYPE (si
->length
), si
->length
,
682 else if (si
->stmt
!= NULL
)
683 /* Delayed length computation is unaffected. */
688 si
->endptr
= NULL_TREE
;
689 si
->dont_invalidate
= true;
693 nsi
= get_strinfo (si
->next
);
695 || nsi
->first
!= si
->first
696 || nsi
->prev
!= si
->idx
)
702 /* Find if there are other SSA_NAME pointers equal to PTR
703 for which we don't track their string lengths yet. If so, use
707 find_equal_ptrs (tree ptr
, int idx
)
709 if (TREE_CODE (ptr
) != SSA_NAME
)
713 gimple stmt
= SSA_NAME_DEF_STMT (ptr
);
714 if (!is_gimple_assign (stmt
))
716 ptr
= gimple_assign_rhs1 (stmt
);
717 switch (gimple_assign_rhs_code (stmt
))
722 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)))
724 if (TREE_CODE (ptr
) == SSA_NAME
)
726 if (TREE_CODE (ptr
) != ADDR_EXPR
)
731 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
732 if (pidx
!= NULL
&& *pidx
== 0)
740 /* We might find an endptr created in this pass. Grow the
741 vector in that case. */
742 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
743 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
745 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] != 0)
747 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = idx
;
751 /* If the last .MEM setter statement before STMT is
752 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
753 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
754 just memcpy (x, y, strlen (y)). SI must be the zero length
758 adjust_last_stmt (strinfo si
, gimple stmt
, bool is_strcat
)
760 tree vuse
, callee
, len
;
761 struct laststmt_struct last
= laststmt
;
762 strinfo lastsi
, firstsi
;
764 laststmt
.stmt
= NULL
;
765 laststmt
.len
= NULL_TREE
;
768 if (last
.stmt
== NULL
)
771 vuse
= gimple_vuse (stmt
);
772 if (vuse
== NULL_TREE
773 || SSA_NAME_DEF_STMT (vuse
) != last
.stmt
774 || !has_single_use (vuse
))
777 gcc_assert (last
.stridx
> 0);
778 lastsi
= get_strinfo (last
.stridx
);
784 if (lastsi
->first
== 0 || lastsi
->first
!= si
->first
)
787 firstsi
= verify_related_strinfos (si
);
790 while (firstsi
!= lastsi
)
793 if (firstsi
->next
== 0)
795 nextsi
= get_strinfo (firstsi
->next
);
797 || nextsi
->prev
!= firstsi
->idx
798 || nextsi
->first
!= si
->first
)
806 if (si
->length
== NULL_TREE
|| !integer_zerop (si
->length
))
810 if (is_gimple_assign (last
.stmt
))
812 gimple_stmt_iterator gsi
;
814 if (!integer_zerop (gimple_assign_rhs1 (last
.stmt
)))
816 if (stmt_could_throw_p (last
.stmt
))
818 gsi
= gsi_for_stmt (last
.stmt
);
819 unlink_stmt_vdef (last
.stmt
);
820 release_defs (last
.stmt
);
821 gsi_remove (&gsi
, true);
825 if (!gimple_call_builtin_p (last
.stmt
, BUILT_IN_NORMAL
))
828 callee
= gimple_call_fndecl (last
.stmt
);
829 switch (DECL_FUNCTION_CODE (callee
))
831 case BUILT_IN_MEMCPY
:
832 case BUILT_IN_MEMCPY_CHK
:
838 len
= gimple_call_arg (last
.stmt
, 2);
839 if (tree_fits_uhwi_p (len
))
841 if (!tree_fits_uhwi_p (last
.len
)
842 || integer_zerop (len
)
843 || tree_to_uhwi (len
) != tree_to_uhwi (last
.len
) + 1)
845 /* Don't adjust the length if it is divisible by 4, it is more efficient
846 to store the extra '\0' in that case. */
847 if ((tree_to_uhwi (len
) & 3) == 0)
850 else if (TREE_CODE (len
) == SSA_NAME
)
852 gimple def_stmt
= SSA_NAME_DEF_STMT (len
);
853 if (!is_gimple_assign (def_stmt
)
854 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
855 || gimple_assign_rhs1 (def_stmt
) != last
.len
856 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
862 gimple_call_set_arg (last
.stmt
, 2, last
.len
);
863 update_stmt (last
.stmt
);
866 /* Handle a strlen call. If strlen of the argument is known, replace
867 the strlen call with the known value, otherwise remember that strlen
868 of the argument is stored in the lhs SSA_NAME. */
871 handle_builtin_strlen (gimple_stmt_iterator
*gsi
)
875 gimple stmt
= gsi_stmt (*gsi
);
876 tree lhs
= gimple_call_lhs (stmt
);
878 if (lhs
== NULL_TREE
)
881 src
= gimple_call_arg (stmt
, 0);
882 idx
= get_stridx (src
);
889 rhs
= build_int_cst (TREE_TYPE (lhs
), ~idx
);
893 si
= get_strinfo (idx
);
895 rhs
= get_string_length (si
);
897 if (rhs
!= NULL_TREE
)
899 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
901 fprintf (dump_file
, "Optimizing: ");
902 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
904 rhs
= unshare_expr (rhs
);
905 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
906 rhs
= fold_convert_loc (gimple_location (stmt
),
907 TREE_TYPE (lhs
), rhs
);
908 if (!update_call_from_tree (gsi
, rhs
))
909 gimplify_and_update_call_from_tree (gsi
, rhs
);
910 stmt
= gsi_stmt (*gsi
);
912 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
914 fprintf (dump_file
, "into: ");
915 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
918 && TREE_CODE (si
->length
) != SSA_NAME
919 && TREE_CODE (si
->length
) != INTEGER_CST
920 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
922 si
= unshare_strinfo (si
);
928 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
931 idx
= new_stridx (src
);
932 else if (get_strinfo (idx
) != NULL
)
936 strinfo si
= new_strinfo (src
, idx
, lhs
);
937 set_strinfo (idx
, si
);
938 find_equal_ptrs (src
, idx
);
942 /* Handle a strchr call. If strlen of the first argument is known, replace
943 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
944 that lhs of the call is endptr and strlen of the argument is endptr - x. */
947 handle_builtin_strchr (gimple_stmt_iterator
*gsi
)
951 gimple stmt
= gsi_stmt (*gsi
);
952 tree lhs
= gimple_call_lhs (stmt
);
954 if (lhs
== NULL_TREE
)
957 if (!integer_zerop (gimple_call_arg (stmt
, 1)))
960 src
= gimple_call_arg (stmt
, 0);
961 idx
= get_stridx (src
);
968 rhs
= build_int_cst (size_type_node
, ~idx
);
972 si
= get_strinfo (idx
);
974 rhs
= get_string_length (si
);
976 if (rhs
!= NULL_TREE
)
978 location_t loc
= gimple_location (stmt
);
980 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
982 fprintf (dump_file
, "Optimizing: ");
983 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
985 if (si
!= NULL
&& si
->endptr
!= NULL_TREE
)
987 rhs
= unshare_expr (si
->endptr
);
988 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
990 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
994 rhs
= fold_convert_loc (loc
, sizetype
, unshare_expr (rhs
));
995 rhs
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
996 TREE_TYPE (src
), src
, rhs
);
997 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
999 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1001 if (!update_call_from_tree (gsi
, rhs
))
1002 gimplify_and_update_call_from_tree (gsi
, rhs
);
1003 stmt
= gsi_stmt (*gsi
);
1005 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1007 fprintf (dump_file
, "into: ");
1008 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1011 && si
->endptr
== NULL_TREE
1012 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1014 si
= unshare_strinfo (si
);
1017 zero_length_string (lhs
, si
);
1021 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1023 if (TREE_CODE (src
) != SSA_NAME
|| !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src
))
1026 idx
= new_stridx (src
);
1027 else if (get_strinfo (idx
) != NULL
)
1029 zero_length_string (lhs
, NULL
);
1034 location_t loc
= gimple_location (stmt
);
1035 tree lhsu
= fold_convert_loc (loc
, size_type_node
, lhs
);
1036 tree srcu
= fold_convert_loc (loc
, size_type_node
, src
);
1037 tree length
= fold_build2_loc (loc
, MINUS_EXPR
,
1038 size_type_node
, lhsu
, srcu
);
1039 strinfo si
= new_strinfo (src
, idx
, length
);
1041 set_strinfo (idx
, si
);
1042 find_equal_ptrs (src
, idx
);
1043 zero_length_string (lhs
, si
);
1047 zero_length_string (lhs
, NULL
);
1050 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1051 If strlen of the second argument is known, strlen of the first argument
1052 is the same after this call. Furthermore, attempt to convert it to
1056 handle_builtin_strcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1059 tree src
, dst
, srclen
, len
, lhs
, args
, type
, fn
, oldlen
;
1061 gimple stmt
= gsi_stmt (*gsi
);
1062 strinfo si
, dsi
, olddsi
, zsi
;
1065 src
= gimple_call_arg (stmt
, 1);
1066 dst
= gimple_call_arg (stmt
, 0);
1067 lhs
= gimple_call_lhs (stmt
);
1068 idx
= get_stridx (src
);
1071 si
= get_strinfo (idx
);
1073 didx
= get_stridx (dst
);
1077 olddsi
= get_strinfo (didx
);
1082 adjust_last_stmt (olddsi
, stmt
, false);
1086 srclen
= get_string_length (si
);
1088 srclen
= build_int_cst (size_type_node
, ~idx
);
1090 loc
= gimple_location (stmt
);
1091 if (srclen
== NULL_TREE
)
1094 case BUILT_IN_STRCPY
:
1095 case BUILT_IN_STRCPY_CHK
:
1096 if (lhs
!= NULL_TREE
|| !builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1099 case BUILT_IN_STPCPY
:
1100 case BUILT_IN_STPCPY_CHK
:
1101 if (lhs
== NULL_TREE
)
1105 tree lhsuint
= fold_convert_loc (loc
, size_type_node
, lhs
);
1106 srclen
= fold_convert_loc (loc
, size_type_node
, dst
);
1107 srclen
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
1117 didx
= new_stridx (dst
);
1123 oldlen
= olddsi
->length
;
1124 dsi
= unshare_strinfo (olddsi
);
1125 dsi
->length
= srclen
;
1126 /* Break the chain, so adjust_related_strinfo on later pointers in
1127 the chain won't adjust this one anymore. */
1130 dsi
->endptr
= NULL_TREE
;
1134 dsi
= new_strinfo (dst
, didx
, srclen
);
1135 set_strinfo (didx
, dsi
);
1136 find_equal_ptrs (dst
, didx
);
1138 dsi
->writable
= true;
1139 dsi
->dont_invalidate
= true;
1141 if (dsi
->length
== NULL_TREE
)
1145 /* If string length of src is unknown, use delayed length
1146 computation. If string lenth of dst will be needed, it
1147 can be computed by transforming this strcpy call into
1148 stpcpy and subtracting dst from the return value. */
1150 /* Look for earlier strings whose length could be determined if
1151 this strcpy is turned into an stpcpy. */
1153 if (dsi
->prev
!= 0 && (chainsi
= verify_related_strinfos (dsi
)) != NULL
)
1155 for (; chainsi
&& chainsi
!= dsi
; chainsi
= get_strinfo (chainsi
->next
))
1157 /* When setting a stmt for delayed length computation
1158 prevent all strinfos through dsi from being
1160 chainsi
= unshare_strinfo (chainsi
);
1161 chainsi
->stmt
= stmt
;
1162 chainsi
->length
= NULL_TREE
;
1163 chainsi
->endptr
= NULL_TREE
;
1164 chainsi
->dont_invalidate
= true;
1173 tree adj
= NULL_TREE
;
1174 if (oldlen
== NULL_TREE
)
1176 else if (integer_zerop (oldlen
))
1178 else if (TREE_CODE (oldlen
) == INTEGER_CST
1179 || TREE_CODE (srclen
) == INTEGER_CST
)
1180 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1181 TREE_TYPE (srclen
), srclen
,
1182 fold_convert_loc (loc
, TREE_TYPE (srclen
),
1184 if (adj
!= NULL_TREE
)
1185 adjust_related_strinfos (loc
, dsi
, adj
);
1189 /* strcpy src may not overlap dst, so src doesn't need to be
1190 invalidated either. */
1192 si
->dont_invalidate
= true;
1198 case BUILT_IN_STRCPY
:
1199 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1201 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1203 case BUILT_IN_STRCPY_CHK
:
1204 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1206 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1208 case BUILT_IN_STPCPY
:
1209 /* This would need adjustment of the lhs (subtract one),
1210 or detection that the trailing '\0' doesn't need to be
1211 written, if it will be immediately overwritten.
1212 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1216 zsi
= zero_length_string (lhs
, dsi
);
1219 case BUILT_IN_STPCPY_CHK
:
1220 /* This would need adjustment of the lhs (subtract one),
1221 or detection that the trailing '\0' doesn't need to be
1222 written, if it will be immediately overwritten.
1223 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1227 zsi
= zero_length_string (lhs
, dsi
);
1234 zsi
->dont_invalidate
= true;
1236 if (fn
== NULL_TREE
)
1239 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1240 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1242 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1243 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
, build_int_cst (type
, 1));
1244 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1246 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1248 fprintf (dump_file
, "Optimizing: ");
1249 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1251 if (gimple_call_num_args (stmt
) == 2)
1252 success
= update_gimple_call (gsi
, fn
, 3, dst
, src
, len
);
1254 success
= update_gimple_call (gsi
, fn
, 4, dst
, src
, len
,
1255 gimple_call_arg (stmt
, 2));
1258 stmt
= gsi_stmt (*gsi
);
1260 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1262 fprintf (dump_file
, "into: ");
1263 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1265 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1266 laststmt
.stmt
= stmt
;
1267 laststmt
.len
= srclen
;
1268 laststmt
.stridx
= dsi
->idx
;
1270 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1271 fprintf (dump_file
, "not possible.\n");
1274 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
1275 If strlen of the second argument is known and length of the third argument
1276 is that plus one, strlen of the first argument is the same after this
1280 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1283 tree src
, dst
, len
, lhs
, oldlen
, newlen
;
1284 gimple stmt
= gsi_stmt (*gsi
);
1285 strinfo si
, dsi
, olddsi
;
1287 len
= gimple_call_arg (stmt
, 2);
1288 src
= gimple_call_arg (stmt
, 1);
1289 dst
= gimple_call_arg (stmt
, 0);
1290 idx
= get_stridx (src
);
1294 didx
= get_stridx (dst
);
1297 olddsi
= get_strinfo (didx
);
1302 && tree_fits_uhwi_p (len
)
1303 && !integer_zerop (len
))
1304 adjust_last_stmt (olddsi
, stmt
, false);
1310 /* Handle memcpy (x, y, l) where l is strlen (y) + 1. */
1311 si
= get_strinfo (idx
);
1312 if (si
== NULL
|| si
->length
== NULL_TREE
)
1314 if (TREE_CODE (len
) != SSA_NAME
)
1316 def_stmt
= SSA_NAME_DEF_STMT (len
);
1317 if (!is_gimple_assign (def_stmt
)
1318 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1319 || gimple_assign_rhs1 (def_stmt
) != si
->length
1320 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1326 /* Handle memcpy (x, "abcd", 5) or
1327 memcpy (x, "abc\0uvw", 7). */
1328 if (!tree_fits_uhwi_p (len
)
1329 || tree_to_uhwi (len
) <= (unsigned HOST_WIDE_INT
) ~idx
)
1333 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
1334 adjust_last_stmt (olddsi
, stmt
, false);
1338 didx
= new_stridx (dst
);
1343 newlen
= si
->length
;
1345 newlen
= build_int_cst (size_type_node
, ~idx
);
1349 dsi
= unshare_strinfo (olddsi
);
1350 oldlen
= olddsi
->length
;
1351 dsi
->length
= newlen
;
1352 /* Break the chain, so adjust_related_strinfo on later pointers in
1353 the chain won't adjust this one anymore. */
1356 dsi
->endptr
= NULL_TREE
;
1360 dsi
= new_strinfo (dst
, didx
, newlen
);
1361 set_strinfo (didx
, dsi
);
1362 find_equal_ptrs (dst
, didx
);
1364 dsi
->writable
= true;
1365 dsi
->dont_invalidate
= true;
1368 tree adj
= NULL_TREE
;
1369 location_t loc
= gimple_location (stmt
);
1370 if (oldlen
== NULL_TREE
)
1372 else if (integer_zerop (oldlen
))
1374 else if (TREE_CODE (oldlen
) == INTEGER_CST
1375 || TREE_CODE (dsi
->length
) == INTEGER_CST
)
1376 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1377 TREE_TYPE (dsi
->length
), dsi
->length
,
1378 fold_convert_loc (loc
, TREE_TYPE (dsi
->length
),
1380 if (adj
!= NULL_TREE
)
1381 adjust_related_strinfos (loc
, dsi
, adj
);
1385 /* memcpy src may not overlap dst, so src doesn't need to be
1386 invalidated either. */
1388 si
->dont_invalidate
= true;
1390 lhs
= gimple_call_lhs (stmt
);
1393 case BUILT_IN_MEMCPY
:
1394 case BUILT_IN_MEMCPY_CHK
:
1395 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1396 laststmt
.stmt
= stmt
;
1397 laststmt
.len
= dsi
->length
;
1398 laststmt
.stridx
= dsi
->idx
;
1400 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1402 case BUILT_IN_MEMPCPY
:
1403 case BUILT_IN_MEMPCPY_CHK
:
1410 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
1411 If strlen of the second argument is known, strlen of the first argument
1412 is increased by the length of the second argument. Furthermore, attempt
1413 to convert it to memcpy/strcpy if the length of the first argument
1417 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1420 tree src
, dst
, srclen
, dstlen
, len
, lhs
, args
, type
, fn
, objsz
, endptr
;
1422 gimple stmt
= gsi_stmt (*gsi
);
1426 src
= gimple_call_arg (stmt
, 1);
1427 dst
= gimple_call_arg (stmt
, 0);
1428 lhs
= gimple_call_lhs (stmt
);
1430 didx
= get_stridx (dst
);
1436 dsi
= get_strinfo (didx
);
1437 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
1439 /* strcat (p, q) can be transformed into
1440 tmp = p + strlen (p); endptr = strpcpy (tmp, q);
1441 with length endptr - p if we need to compute the length
1442 later on. Don't do this transformation if we don't need
1444 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
1448 didx
= new_stridx (dst
);
1454 dsi
= new_strinfo (dst
, didx
, NULL_TREE
);
1455 set_strinfo (didx
, dsi
);
1456 find_equal_ptrs (dst
, didx
);
1460 dsi
= unshare_strinfo (dsi
);
1461 dsi
->length
= NULL_TREE
;
1463 dsi
->endptr
= NULL_TREE
;
1465 dsi
->writable
= true;
1467 dsi
->dont_invalidate
= true;
1474 idx
= get_stridx (src
);
1476 srclen
= build_int_cst (size_type_node
, ~idx
);
1479 si
= get_strinfo (idx
);
1481 srclen
= get_string_length (si
);
1484 loc
= gimple_location (stmt
);
1485 dstlen
= dsi
->length
;
1486 endptr
= dsi
->endptr
;
1488 dsi
= unshare_strinfo (dsi
);
1489 dsi
->endptr
= NULL_TREE
;
1491 dsi
->writable
= true;
1493 if (srclen
!= NULL_TREE
)
1495 dsi
->length
= fold_build2_loc (loc
, PLUS_EXPR
, TREE_TYPE (dsi
->length
),
1496 dsi
->length
, srclen
);
1497 adjust_related_strinfos (loc
, dsi
, srclen
);
1498 dsi
->dont_invalidate
= true;
1503 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1504 dsi
->dont_invalidate
= true;
1508 /* strcat src may not overlap dst, so src doesn't need to be
1509 invalidated either. */
1510 si
->dont_invalidate
= true;
1512 /* For now. Could remove the lhs from the call and add
1513 lhs = dst; afterwards. */
1521 case BUILT_IN_STRCAT
:
1522 if (srclen
!= NULL_TREE
)
1523 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1525 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
1527 case BUILT_IN_STRCAT_CHK
:
1528 if (srclen
!= NULL_TREE
)
1529 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1531 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
1532 objsz
= gimple_call_arg (stmt
, 2);
1538 if (fn
== NULL_TREE
)
1542 if (srclen
!= NULL_TREE
)
1544 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1545 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1547 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1548 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
1549 build_int_cst (type
, 1));
1550 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1554 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
1556 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1557 TREE_TYPE (dst
), unshare_expr (dst
),
1558 fold_convert_loc (loc
, sizetype
,
1559 unshare_expr (dstlen
)));
1560 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
1562 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1564 fprintf (dump_file
, "Optimizing: ");
1565 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1567 if (srclen
!= NULL_TREE
)
1568 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
1569 dst
, src
, len
, objsz
);
1571 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
1575 stmt
= gsi_stmt (*gsi
);
1577 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1579 fprintf (dump_file
, "into: ");
1580 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1582 /* If srclen == NULL, note that current string length can be
1583 computed by transforming this strcpy into stpcpy. */
1584 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
1586 adjust_last_stmt (dsi
, stmt
, true);
1587 if (srclen
!= NULL_TREE
)
1589 laststmt
.stmt
= stmt
;
1590 laststmt
.len
= srclen
;
1591 laststmt
.stridx
= dsi
->idx
;
1594 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1595 fprintf (dump_file
, "not possible.\n");
1598 /* Handle a POINTER_PLUS_EXPR statement.
1599 For p = "abcd" + 2; compute associated length, or if
1600 p = q + off is pointing to a '\0' character of a string, call
1601 zero_length_string on it. */
1604 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
1606 gimple stmt
= gsi_stmt (*gsi
);
1607 tree lhs
= gimple_assign_lhs (stmt
), off
;
1608 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
1616 tree off
= gimple_assign_rhs2 (stmt
);
1617 if (tree_fits_uhwi_p (off
)
1618 && tree_to_uhwi (off
) <= (unsigned HOST_WIDE_INT
) ~idx
)
1619 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
1620 = ~(~idx
- (int) tree_to_uhwi (off
));
1624 si
= get_strinfo (idx
);
1625 if (si
== NULL
|| si
->length
== NULL_TREE
)
1628 off
= gimple_assign_rhs2 (stmt
);
1630 if (operand_equal_p (si
->length
, off
, 0))
1631 zsi
= zero_length_string (lhs
, si
);
1632 else if (TREE_CODE (off
) == SSA_NAME
)
1634 gimple def_stmt
= SSA_NAME_DEF_STMT (off
);
1635 if (gimple_assign_single_p (def_stmt
)
1636 && operand_equal_p (si
->length
, gimple_assign_rhs1 (def_stmt
), 0))
1637 zsi
= zero_length_string (lhs
, si
);
1640 && si
->endptr
!= NULL_TREE
1641 && si
->endptr
!= lhs
1642 && TREE_CODE (si
->endptr
) == SSA_NAME
)
1644 enum tree_code rhs_code
1645 = useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (si
->endptr
))
1646 ? SSA_NAME
: NOP_EXPR
;
1647 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, si
->endptr
, NULL_TREE
);
1648 gcc_assert (gsi_stmt (*gsi
) == stmt
);
1653 /* Handle a single character store. */
1656 handle_char_store (gimple_stmt_iterator
*gsi
)
1660 gimple stmt
= gsi_stmt (*gsi
);
1661 tree ssaname
= NULL_TREE
, lhs
= gimple_assign_lhs (stmt
);
1663 if (TREE_CODE (lhs
) == MEM_REF
1664 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
)
1666 if (integer_zerop (TREE_OPERAND (lhs
, 1)))
1668 ssaname
= TREE_OPERAND (lhs
, 0);
1669 idx
= get_stridx (ssaname
);
1673 idx
= get_addr_stridx (lhs
);
1677 si
= get_strinfo (idx
);
1678 if (si
!= NULL
&& si
->length
!= NULL_TREE
&& integer_zerop (si
->length
))
1680 if (initializer_zerop (gimple_assign_rhs1 (stmt
)))
1682 /* When storing '\0', the store can be removed
1683 if we know it has been stored in the current function. */
1684 if (!stmt_could_throw_p (stmt
) && si
->writable
)
1686 unlink_stmt_vdef (stmt
);
1687 release_defs (stmt
);
1688 gsi_remove (gsi
, true);
1693 si
->writable
= true;
1699 /* Otherwise this statement overwrites the '\0' with
1700 something, if the previous stmt was a memcpy,
1701 its length may be decreased. */
1702 adjust_last_stmt (si
, stmt
, false);
1704 else if (si
!= NULL
&& integer_zerop (gimple_assign_rhs1 (stmt
)))
1706 si
= unshare_strinfo (si
);
1707 si
->length
= build_int_cst (size_type_node
, 0);
1713 si
->writable
= true;
1714 if (ssaname
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
1715 si
->endptr
= ssaname
;
1716 si
->dont_invalidate
= true;
1718 /* If si->length is non-zero constant, we aren't overwriting '\0',
1719 and if we aren't storing '\0', we know that the length of the
1720 string and any other zero terminated string in memory remains
1721 the same. In that case we move to the next gimple statement and
1722 return to signal the caller that it shouldn't invalidate anything.
1724 This is benefical for cases like:
1729 strcpy (p, "foobar");
1730 size_t len = strlen (p); // This can be optimized into 6
1731 size_t len2 = strlen (q); // This has to be computed
1733 size_t len3 = strlen (p); // This can be optimized into 6
1734 size_t len4 = strlen (q); // This can be optimized into len2
1735 bar (len, len2, len3, len4);
1738 else if (si
!= NULL
&& si
->length
!= NULL_TREE
1739 && TREE_CODE (si
->length
) == INTEGER_CST
1740 && integer_nonzerop (gimple_assign_rhs1 (stmt
)))
1746 else if (idx
== 0 && initializer_zerop (gimple_assign_rhs1 (stmt
)))
1750 si
= zero_length_string (ssaname
, NULL
);
1752 si
->dont_invalidate
= true;
1756 int idx
= new_addr_stridx (lhs
);
1759 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
1760 build_int_cst (size_type_node
, 0));
1761 set_strinfo (idx
, si
);
1762 si
->dont_invalidate
= true;
1766 si
->writable
= true;
1769 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == STRING_CST
1770 && ssaname
== NULL_TREE
1771 && TREE_CODE (TREE_TYPE (lhs
)) == ARRAY_TYPE
)
1773 size_t l
= strlen (TREE_STRING_POINTER (gimple_assign_rhs1 (stmt
)));
1774 HOST_WIDE_INT a
= int_size_in_bytes (TREE_TYPE (lhs
));
1775 if (a
> 0 && (unsigned HOST_WIDE_INT
) a
> l
)
1777 int idx
= new_addr_stridx (lhs
);
1780 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
1781 build_int_cst (size_type_node
, l
));
1782 set_strinfo (idx
, si
);
1783 si
->dont_invalidate
= true;
1788 if (si
!= NULL
&& initializer_zerop (gimple_assign_rhs1 (stmt
)))
1790 /* Allow adjust_last_stmt to remove it if the stored '\0'
1791 is immediately overwritten. */
1792 laststmt
.stmt
= stmt
;
1793 laststmt
.len
= build_int_cst (size_type_node
, 1);
1794 laststmt
.stridx
= si
->idx
;
1799 /* Attempt to optimize a single statement at *GSI using string length
1803 strlen_optimize_stmt (gimple_stmt_iterator
*gsi
)
1805 gimple stmt
= gsi_stmt (*gsi
);
1807 if (is_gimple_call (stmt
))
1809 tree callee
= gimple_call_fndecl (stmt
);
1810 if (gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
1811 switch (DECL_FUNCTION_CODE (callee
))
1813 case BUILT_IN_STRLEN
:
1814 handle_builtin_strlen (gsi
);
1816 case BUILT_IN_STRCHR
:
1817 handle_builtin_strchr (gsi
);
1819 case BUILT_IN_STRCPY
:
1820 case BUILT_IN_STRCPY_CHK
:
1821 case BUILT_IN_STPCPY
:
1822 case BUILT_IN_STPCPY_CHK
:
1823 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee
), gsi
);
1825 case BUILT_IN_MEMCPY
:
1826 case BUILT_IN_MEMCPY_CHK
:
1827 case BUILT_IN_MEMPCPY
:
1828 case BUILT_IN_MEMPCPY_CHK
:
1829 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee
), gsi
);
1831 case BUILT_IN_STRCAT
:
1832 case BUILT_IN_STRCAT_CHK
:
1833 handle_builtin_strcat (DECL_FUNCTION_CODE (callee
), gsi
);
1839 else if (is_gimple_assign (stmt
))
1841 tree lhs
= gimple_assign_lhs (stmt
);
1843 if (TREE_CODE (lhs
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (lhs
)))
1845 if (gimple_assign_single_p (stmt
)
1846 || (gimple_assign_cast_p (stmt
)
1847 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
1849 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
1850 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = idx
;
1852 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
1853 handle_pointer_plus (gsi
);
1855 else if (TREE_CODE (lhs
) != SSA_NAME
&& !TREE_SIDE_EFFECTS (lhs
))
1857 tree type
= TREE_TYPE (lhs
);
1858 if (TREE_CODE (type
) == ARRAY_TYPE
)
1859 type
= TREE_TYPE (type
);
1860 if (TREE_CODE (type
) == INTEGER_TYPE
1861 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
1862 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
))
1864 if (! handle_char_store (gsi
))
1870 if (gimple_vdef (stmt
))
1871 maybe_invalidate (stmt
);
1875 /* Recursively call maybe_invalidate on stmts that might be executed
1876 in between dombb and current bb and that contain a vdef. Stop when
1877 *count stmts are inspected, or if the whole strinfo vector has
1878 been invalidated. */
1881 do_invalidate (basic_block dombb
, gimple phi
, bitmap visited
, int *count
)
1883 unsigned int i
, n
= gimple_phi_num_args (phi
);
1885 for (i
= 0; i
< n
; i
++)
1887 tree vuse
= gimple_phi_arg_def (phi
, i
);
1888 gimple stmt
= SSA_NAME_DEF_STMT (vuse
);
1889 basic_block bb
= gimple_bb (stmt
);
1892 || !bitmap_set_bit (visited
, bb
->index
)
1893 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
1897 if (gimple_code (stmt
) == GIMPLE_PHI
)
1899 do_invalidate (dombb
, stmt
, visited
, count
);
1906 if (!maybe_invalidate (stmt
))
1911 vuse
= gimple_vuse (stmt
);
1912 stmt
= SSA_NAME_DEF_STMT (vuse
);
1913 if (gimple_bb (stmt
) != bb
)
1915 bb
= gimple_bb (stmt
);
1918 || !bitmap_set_bit (visited
, bb
->index
)
1919 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
1926 class strlen_dom_walker
: public dom_walker
1929 strlen_dom_walker (cdi_direction direction
) : dom_walker (direction
) {}
1931 virtual void before_dom_children (basic_block
);
1932 virtual void after_dom_children (basic_block
);
1935 /* Callback for walk_dominator_tree. Attempt to optimize various
1936 string ops by remembering string lenths pointed by pointer SSA_NAMEs. */
1939 strlen_dom_walker::before_dom_children (basic_block bb
)
1941 gimple_stmt_iterator gsi
;
1942 basic_block dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1945 stridx_to_strinfo
= NULL
;
1948 stridx_to_strinfo
= ((vec
<strinfo
, va_heap
, vl_embed
> *) dombb
->aux
);
1949 if (stridx_to_strinfo
)
1951 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1953 gimple phi
= gsi_stmt (gsi
);
1954 if (virtual_operand_p (gimple_phi_result (phi
)))
1956 bitmap visited
= BITMAP_ALLOC (NULL
);
1957 int count_vdef
= 100;
1958 do_invalidate (dombb
, phi
, visited
, &count_vdef
);
1959 BITMAP_FREE (visited
);
1960 if (count_vdef
== 0)
1962 /* If there were too many vdefs in between immediate
1963 dominator and current bb, invalidate everything.
1964 If stridx_to_strinfo has been unshared, we need
1965 to free it, otherwise just set it to NULL. */
1966 if (!strinfo_shared ())
1972 vec_safe_iterate (stridx_to_strinfo
, i
, &si
);
1976 (*stridx_to_strinfo
)[i
] = NULL
;
1980 stridx_to_strinfo
= NULL
;
1988 /* If all PHI arguments have the same string index, the PHI result
1990 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1992 gimple phi
= gsi_stmt (gsi
);
1993 tree result
= gimple_phi_result (phi
);
1994 if (!virtual_operand_p (result
) && POINTER_TYPE_P (TREE_TYPE (result
)))
1996 int idx
= get_stridx (gimple_phi_arg_def (phi
, 0));
1999 unsigned int i
, n
= gimple_phi_num_args (phi
);
2000 for (i
= 1; i
< n
; i
++)
2001 if (idx
!= get_stridx (gimple_phi_arg_def (phi
, i
)))
2004 ssa_ver_to_stridx
[SSA_NAME_VERSION (result
)] = idx
;
2009 /* Attempt to optimize individual statements. */
2010 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2011 if (strlen_optimize_stmt (&gsi
))
2014 bb
->aux
= stridx_to_strinfo
;
2015 if (vec_safe_length (stridx_to_strinfo
) && !strinfo_shared ())
2016 (*stridx_to_strinfo
)[0] = (strinfo
) bb
;
2019 /* Callback for walk_dominator_tree. Free strinfo vector if it is
2020 owned by the current bb, clear bb->aux. */
2023 strlen_dom_walker::after_dom_children (basic_block bb
)
2027 stridx_to_strinfo
= ((vec
<strinfo
, va_heap
, vl_embed
> *) bb
->aux
);
2028 if (vec_safe_length (stridx_to_strinfo
)
2029 && (*stridx_to_strinfo
)[0] == (strinfo
) bb
)
2034 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
2036 vec_free (stridx_to_strinfo
);
2042 /* Main entry point. */
2046 const pass_data pass_data_strlen
=
2048 GIMPLE_PASS
, /* type */
2049 "strlen", /* name */
2050 OPTGROUP_NONE
, /* optinfo_flags */
2051 true, /* has_execute */
2052 TV_TREE_STRLEN
, /* tv_id */
2053 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2054 0, /* properties_provided */
2055 0, /* properties_destroyed */
2056 0, /* todo_flags_start */
2057 0, /* todo_flags_finish */
2060 class pass_strlen
: public gimple_opt_pass
2063 pass_strlen (gcc::context
*ctxt
)
2064 : gimple_opt_pass (pass_data_strlen
, ctxt
)
2067 /* opt_pass methods: */
2068 virtual bool gate (function
*) { return flag_optimize_strlen
!= 0; }
2069 virtual unsigned int execute (function
*);
2071 }; // class pass_strlen
2074 pass_strlen::execute (function
*fun
)
2076 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
2078 strinfo_pool
= create_alloc_pool ("strinfo_struct pool",
2079 sizeof (struct strinfo_struct
), 64);
2081 calculate_dominance_info (CDI_DOMINATORS
);
2083 /* String length optimization is implemented as a walk of the dominator
2084 tree and a forward walk of statements within each block. */
2085 strlen_dom_walker (CDI_DOMINATORS
).walk (fun
->cfg
->x_entry_block_ptr
);
2087 ssa_ver_to_stridx
.release ();
2088 free_alloc_pool (strinfo_pool
);
2089 if (decl_to_stridxlist_htab
)
2091 obstack_free (&stridx_obstack
, NULL
);
2092 delete decl_to_stridxlist_htab
;
2093 decl_to_stridxlist_htab
= NULL
;
2095 laststmt
.stmt
= NULL
;
2096 laststmt
.len
= NULL_TREE
;
2097 laststmt
.stridx
= 0;
2105 make_pass_strlen (gcc::context
*ctxt
)
2107 return new pass_strlen (ctxt
);