1 /* String length optimization
2 Copyright (C) 2011-2013 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 "hash-table.h"
29 #include "gimple-iterator.h"
30 #include "gimplify-me.h"
31 #include "gimple-ssa.h"
32 #include "tree-phinodes.h"
33 #include "ssa-iterators.h"
34 #include "tree-ssanames.h"
36 #include "tree-pass.h"
38 #include "alloc-pool.h"
39 #include "tree-ssa-propagate.h"
40 #include "gimple-pretty-print.h"
44 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
45 is an index into strinfo vector, negative value stands for
46 string length of a string literal (~strlen). */
47 static vec
<int> ssa_ver_to_stridx
;
49 /* Number of currently active string indexes plus one. */
50 static int max_stridx
;
52 /* String information record. */
53 typedef struct strinfo_struct
55 /* String length of this string. */
57 /* Any of the corresponding pointers for querying alias oracle. */
59 /* Statement for delayed length computation. */
61 /* Pointer to '\0' if known, if NULL, it can be computed as
64 /* Reference count. Any changes to strinfo entry possibly shared
65 with dominating basic blocks need unshare_strinfo first, except
66 for dont_invalidate which affects only the immediately next
69 /* Copy of index. get_strinfo (si->idx) should return si; */
71 /* These 3 fields are for chaining related string pointers together.
73 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
74 strcpy (c, d); e = c + dl;
75 strinfo(a) -> strinfo(c) -> strinfo(e)
76 All have ->first field equal to strinfo(a)->idx and are doubly
77 chained through prev/next fields. The later strinfos are required
78 to point into the same string with zero or more bytes after
79 the previous pointer and all bytes in between the two pointers
80 must be non-zero. Functions like strcpy or memcpy are supposed
81 to adjust all previous strinfo lengths, but not following strinfo
82 lengths (those are uncertain, usually invalidated during
83 maybe_invalidate, except when the alias oracle knows better).
84 Functions like strcat on the other side adjust the whole
85 related strinfo chain.
86 They are updated lazily, so to use the chain the same first fields
87 and si->prev->next == si->idx needs to be verified. */
91 /* A flag whether the string is known to be written in the current
94 /* A flag for the next maybe_invalidate that this strinfo shouldn't
95 be invalidated. Always cleared by maybe_invalidate. */
99 /* Pool for allocating strinfo_struct entries. */
100 static alloc_pool strinfo_pool
;
102 /* Vector mapping positive string indexes to strinfo, for the
103 current basic block. The first pointer in the vector is special,
104 it is either NULL, meaning the vector isn't shared, or it is
105 a basic block pointer to the owner basic_block if shared.
106 If some other bb wants to modify the vector, the vector needs
107 to be unshared first, and only the owner bb is supposed to free it. */
108 static vec
<strinfo
, va_heap
, vl_embed
> *stridx_to_strinfo
;
110 /* One OFFSET->IDX mapping. */
113 struct stridxlist
*next
;
114 HOST_WIDE_INT offset
;
118 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
119 struct decl_stridxlist_map
121 struct tree_map_base base
;
122 struct stridxlist list
;
125 /* stridxlist hashtable helpers. */
127 struct stridxlist_hasher
: typed_noop_remove
<decl_stridxlist_map
>
129 typedef decl_stridxlist_map value_type
;
130 typedef decl_stridxlist_map compare_type
;
131 static inline hashval_t
hash (const value_type
*);
132 static inline bool equal (const value_type
*, const compare_type
*);
135 /* Hash a from tree in a decl_stridxlist_map. */
138 stridxlist_hasher::hash (const value_type
*item
)
140 return DECL_UID (item
->base
.from
);
144 stridxlist_hasher::equal (const value_type
*v
, const compare_type
*c
)
146 return tree_map_base_eq (&v
->base
, &c
->base
);
149 /* Hash table for mapping decls to a chained list of offset -> idx
151 static hash_table
<stridxlist_hasher
> decl_to_stridxlist_htab
;
153 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
154 static struct obstack stridx_obstack
;
156 /* Last memcpy statement if it could be adjusted if the trailing
157 '\0' written is immediately overwritten, or
158 *x = '\0' store that could be removed if it is immediately overwritten. */
159 struct laststmt_struct
166 /* Helper function for get_stridx. */
169 get_addr_stridx (tree exp
)
172 struct decl_stridxlist_map ent
, *e
;
173 struct stridxlist
*list
;
176 if (!decl_to_stridxlist_htab
.is_created ())
179 base
= get_addr_base_and_unit_offset (exp
, &off
);
180 if (base
== NULL
|| !DECL_P (base
))
183 ent
.base
.from
= base
;
184 e
= decl_to_stridxlist_htab
.find_with_hash (&ent
, DECL_UID (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
)
263 decl_stridxlist_map
**slot
;
264 struct decl_stridxlist_map ent
;
265 struct stridxlist
*list
;
268 tree base
= get_addr_base_and_unit_offset (exp
, &off
);
269 if (base
== NULL_TREE
|| !DECL_P (base
))
272 if (!decl_to_stridxlist_htab
.is_created ())
274 decl_to_stridxlist_htab
.create (64);
275 gcc_obstack_init (&stridx_obstack
);
277 ent
.base
.from
= base
;
278 slot
= decl_to_stridxlist_htab
.find_slot_with_hash (&ent
, DECL_UID (base
),
283 list
= &(*slot
)->list
;
284 for (i
= 0; i
< 16; i
++)
286 if (list
->offset
== off
)
288 if (list
->next
== NULL
)
293 list
->next
= XOBNEW (&stridx_obstack
, struct stridxlist
);
298 struct decl_stridxlist_map
*e
299 = XOBNEW (&stridx_obstack
, struct decl_stridxlist_map
);
310 /* Create a new string index, or return 0 if reached limit. */
313 new_stridx (tree exp
)
316 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
318 if (TREE_CODE (exp
) == SSA_NAME
)
320 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
))
323 ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)] = idx
;
326 if (TREE_CODE (exp
) == ADDR_EXPR
)
328 int *pidx
= addr_stridxptr (TREE_OPERAND (exp
, 0));
331 gcc_assert (*pidx
== 0);
332 *pidx
= max_stridx
++;
339 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
342 new_addr_stridx (tree exp
)
345 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
347 pidx
= addr_stridxptr (exp
);
350 gcc_assert (*pidx
== 0);
351 *pidx
= max_stridx
++;
357 /* Create a new strinfo. */
360 new_strinfo (tree ptr
, int idx
, tree length
)
362 strinfo si
= (strinfo
) pool_alloc (strinfo_pool
);
366 si
->endptr
= NULL_TREE
;
372 si
->writable
= false;
373 si
->dont_invalidate
= false;
377 /* Decrease strinfo refcount and free it if not referenced anymore. */
380 free_strinfo (strinfo si
)
382 if (si
&& --si
->refcount
== 0)
383 pool_free (strinfo_pool
, si
);
386 /* Return strinfo vector entry IDX. */
388 static inline strinfo
389 get_strinfo (int idx
)
391 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
393 return (*stridx_to_strinfo
)[idx
];
396 /* Set strinfo in the vector entry IDX to SI. */
399 set_strinfo (int idx
, strinfo si
)
401 if (vec_safe_length (stridx_to_strinfo
) && (*stridx_to_strinfo
)[0])
402 unshare_strinfo_vec ();
403 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
404 vec_safe_grow_cleared (stridx_to_strinfo
, idx
+ 1);
405 (*stridx_to_strinfo
)[idx
] = si
;
408 /* Return string length, or NULL if it can't be computed. */
411 get_string_length (strinfo si
)
418 gimple stmt
= si
->stmt
, lenstmt
;
419 tree callee
, lhs
, fn
, tem
;
421 gimple_stmt_iterator gsi
;
423 gcc_assert (is_gimple_call (stmt
));
424 callee
= gimple_call_fndecl (stmt
);
425 gcc_assert (callee
&& DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
);
426 lhs
= gimple_call_lhs (stmt
);
427 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY
));
428 /* unshare_strinfo is intentionally not called here. The (delayed)
429 transformation of strcpy or strcat into stpcpy is done at the place
430 of the former strcpy/strcat call and so can affect all the strinfos
431 with the same stmt. If they were unshared before and transformation
432 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
433 just compute the right length. */
434 switch (DECL_FUNCTION_CODE (callee
))
436 case BUILT_IN_STRCAT
:
437 case BUILT_IN_STRCAT_CHK
:
438 gsi
= gsi_for_stmt (stmt
);
439 fn
= builtin_decl_implicit (BUILT_IN_STRLEN
);
440 gcc_assert (lhs
== NULL_TREE
);
441 tem
= unshare_expr (gimple_call_arg (stmt
, 0));
442 lenstmt
= gimple_build_call (fn
, 1, tem
);
443 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), lenstmt
);
444 gimple_call_set_lhs (lenstmt
, lhs
);
445 gimple_set_vuse (lenstmt
, gimple_vuse (stmt
));
446 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
447 tem
= gimple_call_arg (stmt
, 0);
448 if (!ptrofftype_p (TREE_TYPE (lhs
)))
450 lhs
= convert_to_ptrofftype (lhs
);
451 lhs
= force_gimple_operand_gsi (&gsi
, lhs
, true, NULL_TREE
,
452 true, GSI_SAME_STMT
);
455 = gimple_build_assign_with_ops
457 make_ssa_name (TREE_TYPE (gimple_call_arg (stmt
, 0)), NULL
),
459 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
460 gimple_call_set_arg (stmt
, 0, gimple_assign_lhs (lenstmt
));
463 case BUILT_IN_STRCPY
:
464 case BUILT_IN_STRCPY_CHK
:
465 if (gimple_call_num_args (stmt
) == 2)
466 fn
= builtin_decl_implicit (BUILT_IN_STPCPY
);
468 fn
= builtin_decl_explicit (BUILT_IN_STPCPY_CHK
);
469 gcc_assert (lhs
== NULL_TREE
);
470 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
472 fprintf (dump_file
, "Optimizing: ");
473 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
475 gimple_call_set_fndecl (stmt
, fn
);
476 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), stmt
);
477 gimple_call_set_lhs (stmt
, lhs
);
479 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
481 fprintf (dump_file
, "into: ");
482 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
485 case BUILT_IN_STPCPY
:
486 case BUILT_IN_STPCPY_CHK
:
487 gcc_assert (lhs
!= NULL_TREE
);
488 loc
= gimple_location (stmt
);
491 lhs
= fold_convert_loc (loc
, size_type_node
, lhs
);
492 si
->length
= fold_convert_loc (loc
, size_type_node
, si
->ptr
);
493 si
->length
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
505 /* Invalidate string length information for strings whose length
506 might change due to stores in stmt. */
509 maybe_invalidate (gimple stmt
)
513 bool nonempty
= false;
515 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
518 if (!si
->dont_invalidate
)
521 ao_ref_init_from_ptr_and_size (&r
, si
->ptr
, NULL_TREE
);
522 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
524 set_strinfo (i
, NULL
);
529 si
->dont_invalidate
= false;
535 /* Unshare strinfo record SI, if it has recount > 1 or
536 if stridx_to_strinfo vector is shared with some other
540 unshare_strinfo (strinfo si
)
544 if (si
->refcount
== 1 && !strinfo_shared ())
547 nsi
= new_strinfo (si
->ptr
, si
->idx
, si
->length
);
548 nsi
->stmt
= si
->stmt
;
549 nsi
->endptr
= si
->endptr
;
550 nsi
->first
= si
->first
;
551 nsi
->prev
= si
->prev
;
552 nsi
->next
= si
->next
;
553 nsi
->writable
= si
->writable
;
554 set_strinfo (si
->idx
, nsi
);
559 /* Return first strinfo in the related strinfo chain
560 if all strinfos in between belong to the chain, otherwise
564 verify_related_strinfos (strinfo origsi
)
566 strinfo si
= origsi
, psi
;
568 if (origsi
->first
== 0)
570 for (; si
->prev
; si
= psi
)
572 if (si
->first
!= origsi
->first
)
574 psi
= get_strinfo (si
->prev
);
577 if (psi
->next
!= si
->idx
)
580 if (si
->idx
!= si
->first
)
585 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
586 to a zero-length string and if possible chain it to a related strinfo
587 chain whose part is or might be CHAINSI. */
590 zero_length_string (tree ptr
, strinfo chainsi
)
594 gcc_checking_assert (TREE_CODE (ptr
) == SSA_NAME
595 && get_stridx (ptr
) == 0);
597 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
601 si
= verify_related_strinfos (chainsi
);
605 for (; chainsi
->next
; chainsi
= si
)
607 if (chainsi
->endptr
== NULL_TREE
)
609 chainsi
= unshare_strinfo (chainsi
);
610 chainsi
->endptr
= ptr
;
612 si
= get_strinfo (chainsi
->next
);
614 || si
->first
!= chainsi
->first
615 || si
->prev
!= chainsi
->idx
)
618 gcc_assert (chainsi
->length
|| chainsi
->stmt
);
619 if (chainsi
->endptr
== NULL_TREE
)
621 chainsi
= unshare_strinfo (chainsi
);
622 chainsi
->endptr
= ptr
;
624 if (chainsi
->length
&& integer_zerop (chainsi
->length
))
628 chainsi
= unshare_strinfo (chainsi
);
631 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = chainsi
->idx
;
635 else if (chainsi
->first
|| chainsi
->prev
|| chainsi
->next
)
637 chainsi
= unshare_strinfo (chainsi
);
643 idx
= new_stridx (ptr
);
646 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, 0));
647 set_strinfo (idx
, si
);
651 chainsi
= unshare_strinfo (chainsi
);
652 if (chainsi
->first
== 0)
653 chainsi
->first
= chainsi
->idx
;
655 if (chainsi
->endptr
== NULL_TREE
)
656 chainsi
->endptr
= ptr
;
657 si
->prev
= chainsi
->idx
;
658 si
->first
= chainsi
->first
;
659 si
->writable
= chainsi
->writable
;
664 /* For strinfo ORIGSI whose length has been just updated
665 update also related strinfo lengths (add ADJ to each,
666 but don't adjust ORIGSI). */
669 adjust_related_strinfos (location_t loc
, strinfo origsi
, tree adj
)
671 strinfo si
= verify_related_strinfos (origsi
);
684 si
= unshare_strinfo (si
);
687 tem
= fold_convert_loc (loc
, TREE_TYPE (si
->length
), adj
);
688 si
->length
= fold_build2_loc (loc
, PLUS_EXPR
,
689 TREE_TYPE (si
->length
), si
->length
,
692 else if (si
->stmt
!= NULL
)
693 /* Delayed length computation is unaffected. */
698 si
->endptr
= NULL_TREE
;
699 si
->dont_invalidate
= true;
703 nsi
= get_strinfo (si
->next
);
705 || nsi
->first
!= si
->first
706 || nsi
->prev
!= si
->idx
)
712 /* Find if there are other SSA_NAME pointers equal to PTR
713 for which we don't track their string lengths yet. If so, use
717 find_equal_ptrs (tree ptr
, int idx
)
719 if (TREE_CODE (ptr
) != SSA_NAME
)
723 gimple stmt
= SSA_NAME_DEF_STMT (ptr
);
724 if (!is_gimple_assign (stmt
))
726 ptr
= gimple_assign_rhs1 (stmt
);
727 switch (gimple_assign_rhs_code (stmt
))
732 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)))
734 if (TREE_CODE (ptr
) == SSA_NAME
)
736 if (TREE_CODE (ptr
) != ADDR_EXPR
)
741 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
742 if (pidx
!= NULL
&& *pidx
== 0)
750 /* We might find an endptr created in this pass. Grow the
751 vector in that case. */
752 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
753 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
755 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] != 0)
757 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = idx
;
761 /* If the last .MEM setter statement before STMT is
762 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
763 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
764 just memcpy (x, y, strlen (y)). SI must be the zero length
768 adjust_last_stmt (strinfo si
, gimple stmt
, bool is_strcat
)
770 tree vuse
, callee
, len
;
771 struct laststmt_struct last
= laststmt
;
772 strinfo lastsi
, firstsi
;
774 laststmt
.stmt
= NULL
;
775 laststmt
.len
= NULL_TREE
;
778 if (last
.stmt
== NULL
)
781 vuse
= gimple_vuse (stmt
);
782 if (vuse
== NULL_TREE
783 || SSA_NAME_DEF_STMT (vuse
) != last
.stmt
784 || !has_single_use (vuse
))
787 gcc_assert (last
.stridx
> 0);
788 lastsi
= get_strinfo (last
.stridx
);
794 if (lastsi
->first
== 0 || lastsi
->first
!= si
->first
)
797 firstsi
= verify_related_strinfos (si
);
800 while (firstsi
!= lastsi
)
803 if (firstsi
->next
== 0)
805 nextsi
= get_strinfo (firstsi
->next
);
807 || nextsi
->prev
!= firstsi
->idx
808 || nextsi
->first
!= si
->first
)
816 if (si
->length
== NULL_TREE
|| !integer_zerop (si
->length
))
820 if (is_gimple_assign (last
.stmt
))
822 gimple_stmt_iterator gsi
;
824 if (!integer_zerop (gimple_assign_rhs1 (last
.stmt
)))
826 if (stmt_could_throw_p (last
.stmt
))
828 gsi
= gsi_for_stmt (last
.stmt
);
829 unlink_stmt_vdef (last
.stmt
);
830 release_defs (last
.stmt
);
831 gsi_remove (&gsi
, true);
835 if (!gimple_call_builtin_p (last
.stmt
, BUILT_IN_NORMAL
))
838 callee
= gimple_call_fndecl (last
.stmt
);
839 switch (DECL_FUNCTION_CODE (callee
))
841 case BUILT_IN_MEMCPY
:
842 case BUILT_IN_MEMCPY_CHK
:
848 len
= gimple_call_arg (last
.stmt
, 2);
849 if (tree_fits_uhwi_p (len
))
851 if (!tree_fits_uhwi_p (last
.len
)
852 || integer_zerop (len
)
853 || tree_to_uhwi (len
) != tree_to_uhwi (last
.len
) + 1)
855 /* Don't adjust the length if it is divisible by 4, it is more efficient
856 to store the extra '\0' in that case. */
857 if ((tree_to_uhwi (len
) & 3) == 0)
860 else if (TREE_CODE (len
) == SSA_NAME
)
862 gimple def_stmt
= SSA_NAME_DEF_STMT (len
);
863 if (!is_gimple_assign (def_stmt
)
864 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
865 || gimple_assign_rhs1 (def_stmt
) != last
.len
866 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
872 gimple_call_set_arg (last
.stmt
, 2, last
.len
);
873 update_stmt (last
.stmt
);
876 /* Handle a strlen call. If strlen of the argument is known, replace
877 the strlen call with the known value, otherwise remember that strlen
878 of the argument is stored in the lhs SSA_NAME. */
881 handle_builtin_strlen (gimple_stmt_iterator
*gsi
)
885 gimple stmt
= gsi_stmt (*gsi
);
886 tree lhs
= gimple_call_lhs (stmt
);
888 if (lhs
== NULL_TREE
)
891 src
= gimple_call_arg (stmt
, 0);
892 idx
= get_stridx (src
);
899 rhs
= build_int_cst (TREE_TYPE (lhs
), ~idx
);
903 si
= get_strinfo (idx
);
905 rhs
= get_string_length (si
);
907 if (rhs
!= NULL_TREE
)
909 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
911 fprintf (dump_file
, "Optimizing: ");
912 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
914 rhs
= unshare_expr (rhs
);
915 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
916 rhs
= fold_convert_loc (gimple_location (stmt
),
917 TREE_TYPE (lhs
), rhs
);
918 if (!update_call_from_tree (gsi
, rhs
))
919 gimplify_and_update_call_from_tree (gsi
, rhs
);
920 stmt
= gsi_stmt (*gsi
);
922 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
924 fprintf (dump_file
, "into: ");
925 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
928 && TREE_CODE (si
->length
) != SSA_NAME
929 && TREE_CODE (si
->length
) != INTEGER_CST
930 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
932 si
= unshare_strinfo (si
);
938 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
941 idx
= new_stridx (src
);
942 else if (get_strinfo (idx
) != NULL
)
946 strinfo si
= new_strinfo (src
, idx
, lhs
);
947 set_strinfo (idx
, si
);
948 find_equal_ptrs (src
, idx
);
952 /* Handle a strchr call. If strlen of the first argument is known, replace
953 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
954 that lhs of the call is endptr and strlen of the argument is endptr - x. */
957 handle_builtin_strchr (gimple_stmt_iterator
*gsi
)
961 gimple stmt
= gsi_stmt (*gsi
);
962 tree lhs
= gimple_call_lhs (stmt
);
964 if (lhs
== NULL_TREE
)
967 if (!integer_zerop (gimple_call_arg (stmt
, 1)))
970 src
= gimple_call_arg (stmt
, 0);
971 idx
= get_stridx (src
);
978 rhs
= build_int_cst (size_type_node
, ~idx
);
982 si
= get_strinfo (idx
);
984 rhs
= get_string_length (si
);
986 if (rhs
!= NULL_TREE
)
988 location_t loc
= gimple_location (stmt
);
990 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
992 fprintf (dump_file
, "Optimizing: ");
993 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
995 if (si
!= NULL
&& si
->endptr
!= NULL_TREE
)
997 rhs
= unshare_expr (si
->endptr
);
998 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1000 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1004 rhs
= fold_convert_loc (loc
, sizetype
, unshare_expr (rhs
));
1005 rhs
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1006 TREE_TYPE (src
), src
, rhs
);
1007 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1009 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1011 if (!update_call_from_tree (gsi
, rhs
))
1012 gimplify_and_update_call_from_tree (gsi
, rhs
);
1013 stmt
= gsi_stmt (*gsi
);
1015 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1017 fprintf (dump_file
, "into: ");
1018 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1021 && si
->endptr
== NULL_TREE
1022 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1024 si
= unshare_strinfo (si
);
1027 zero_length_string (lhs
, si
);
1031 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1033 if (TREE_CODE (src
) != SSA_NAME
|| !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src
))
1036 idx
= new_stridx (src
);
1037 else if (get_strinfo (idx
) != NULL
)
1039 zero_length_string (lhs
, NULL
);
1044 location_t loc
= gimple_location (stmt
);
1045 tree lhsu
= fold_convert_loc (loc
, size_type_node
, lhs
);
1046 tree srcu
= fold_convert_loc (loc
, size_type_node
, src
);
1047 tree length
= fold_build2_loc (loc
, MINUS_EXPR
,
1048 size_type_node
, lhsu
, srcu
);
1049 strinfo si
= new_strinfo (src
, idx
, length
);
1051 set_strinfo (idx
, si
);
1052 find_equal_ptrs (src
, idx
);
1053 zero_length_string (lhs
, si
);
1057 zero_length_string (lhs
, NULL
);
1060 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1061 If strlen of the second argument is known, strlen of the first argument
1062 is the same after this call. Furthermore, attempt to convert it to
1066 handle_builtin_strcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1069 tree src
, dst
, srclen
, len
, lhs
, args
, type
, fn
, oldlen
;
1071 gimple stmt
= gsi_stmt (*gsi
);
1072 strinfo si
, dsi
, olddsi
, zsi
;
1075 src
= gimple_call_arg (stmt
, 1);
1076 dst
= gimple_call_arg (stmt
, 0);
1077 lhs
= gimple_call_lhs (stmt
);
1078 idx
= get_stridx (src
);
1081 si
= get_strinfo (idx
);
1083 didx
= get_stridx (dst
);
1087 olddsi
= get_strinfo (didx
);
1092 adjust_last_stmt (olddsi
, stmt
, false);
1096 srclen
= get_string_length (si
);
1098 srclen
= build_int_cst (size_type_node
, ~idx
);
1100 loc
= gimple_location (stmt
);
1101 if (srclen
== NULL_TREE
)
1104 case BUILT_IN_STRCPY
:
1105 case BUILT_IN_STRCPY_CHK
:
1106 if (lhs
!= NULL_TREE
|| !builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1109 case BUILT_IN_STPCPY
:
1110 case BUILT_IN_STPCPY_CHK
:
1111 if (lhs
== NULL_TREE
)
1115 tree lhsuint
= fold_convert_loc (loc
, size_type_node
, lhs
);
1116 srclen
= fold_convert_loc (loc
, size_type_node
, dst
);
1117 srclen
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
1127 didx
= new_stridx (dst
);
1133 oldlen
= olddsi
->length
;
1134 dsi
= unshare_strinfo (olddsi
);
1135 dsi
->length
= srclen
;
1136 /* Break the chain, so adjust_related_strinfo on later pointers in
1137 the chain won't adjust this one anymore. */
1140 dsi
->endptr
= NULL_TREE
;
1144 dsi
= new_strinfo (dst
, didx
, srclen
);
1145 set_strinfo (didx
, dsi
);
1146 find_equal_ptrs (dst
, didx
);
1148 dsi
->writable
= true;
1149 dsi
->dont_invalidate
= true;
1151 if (dsi
->length
== NULL_TREE
)
1155 /* If string length of src is unknown, use delayed length
1156 computation. If string lenth of dst will be needed, it
1157 can be computed by transforming this strcpy call into
1158 stpcpy and subtracting dst from the return value. */
1160 /* Look for earlier strings whose length could be determined if
1161 this strcpy is turned into an stpcpy. */
1163 if (dsi
->prev
!= 0 && (chainsi
= verify_related_strinfos (dsi
)) != NULL
)
1165 for (; chainsi
&& chainsi
!= dsi
; chainsi
= get_strinfo (chainsi
->next
))
1167 /* When setting a stmt for delayed length computation
1168 prevent all strinfos through dsi from being
1170 chainsi
= unshare_strinfo (chainsi
);
1171 chainsi
->stmt
= stmt
;
1172 chainsi
->length
= NULL_TREE
;
1173 chainsi
->endptr
= NULL_TREE
;
1174 chainsi
->dont_invalidate
= true;
1183 tree adj
= NULL_TREE
;
1184 if (oldlen
== NULL_TREE
)
1186 else if (integer_zerop (oldlen
))
1188 else if (TREE_CODE (oldlen
) == INTEGER_CST
1189 || TREE_CODE (srclen
) == INTEGER_CST
)
1190 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1191 TREE_TYPE (srclen
), srclen
,
1192 fold_convert_loc (loc
, TREE_TYPE (srclen
),
1194 if (adj
!= NULL_TREE
)
1195 adjust_related_strinfos (loc
, dsi
, adj
);
1199 /* strcpy src may not overlap dst, so src doesn't need to be
1200 invalidated either. */
1202 si
->dont_invalidate
= true;
1208 case BUILT_IN_STRCPY
:
1209 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1211 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1213 case BUILT_IN_STRCPY_CHK
:
1214 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1216 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1218 case BUILT_IN_STPCPY
:
1219 /* This would need adjustment of the lhs (subtract one),
1220 or detection that the trailing '\0' doesn't need to be
1221 written, if it will be immediately overwritten.
1222 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1226 zsi
= zero_length_string (lhs
, dsi
);
1229 case BUILT_IN_STPCPY_CHK
:
1230 /* This would need adjustment of the lhs (subtract one),
1231 or detection that the trailing '\0' doesn't need to be
1232 written, if it will be immediately overwritten.
1233 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1237 zsi
= zero_length_string (lhs
, dsi
);
1244 zsi
->dont_invalidate
= true;
1246 if (fn
== NULL_TREE
)
1249 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1250 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1252 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1253 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
, build_int_cst (type
, 1));
1254 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1256 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1258 fprintf (dump_file
, "Optimizing: ");
1259 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1261 if (gimple_call_num_args (stmt
) == 2)
1262 success
= update_gimple_call (gsi
, fn
, 3, dst
, src
, len
);
1264 success
= update_gimple_call (gsi
, fn
, 4, dst
, src
, len
,
1265 gimple_call_arg (stmt
, 2));
1268 stmt
= gsi_stmt (*gsi
);
1270 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1272 fprintf (dump_file
, "into: ");
1273 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1275 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1276 laststmt
.stmt
= stmt
;
1277 laststmt
.len
= srclen
;
1278 laststmt
.stridx
= dsi
->idx
;
1280 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1281 fprintf (dump_file
, "not possible.\n");
1284 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
1285 If strlen of the second argument is known and length of the third argument
1286 is that plus one, strlen of the first argument is the same after this
1290 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1293 tree src
, dst
, len
, lhs
, oldlen
, newlen
;
1294 gimple stmt
= gsi_stmt (*gsi
);
1295 strinfo si
, dsi
, olddsi
;
1297 len
= gimple_call_arg (stmt
, 2);
1298 src
= gimple_call_arg (stmt
, 1);
1299 dst
= gimple_call_arg (stmt
, 0);
1300 idx
= get_stridx (src
);
1304 didx
= get_stridx (dst
);
1307 olddsi
= get_strinfo (didx
);
1312 && tree_fits_uhwi_p (len
)
1313 && !integer_zerop (len
))
1314 adjust_last_stmt (olddsi
, stmt
, false);
1320 /* Handle memcpy (x, y, l) where l is strlen (y) + 1. */
1321 si
= get_strinfo (idx
);
1322 if (si
== NULL
|| si
->length
== NULL_TREE
)
1324 if (TREE_CODE (len
) != SSA_NAME
)
1326 def_stmt
= SSA_NAME_DEF_STMT (len
);
1327 if (!is_gimple_assign (def_stmt
)
1328 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1329 || gimple_assign_rhs1 (def_stmt
) != si
->length
1330 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1336 /* Handle memcpy (x, "abcd", 5) or
1337 memcpy (x, "abc\0uvw", 7). */
1338 if (!tree_fits_uhwi_p (len
)
1339 || tree_to_uhwi (len
) <= (unsigned HOST_WIDE_INT
) ~idx
)
1343 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
1344 adjust_last_stmt (olddsi
, stmt
, false);
1348 didx
= new_stridx (dst
);
1353 newlen
= si
->length
;
1355 newlen
= build_int_cst (size_type_node
, ~idx
);
1359 dsi
= unshare_strinfo (olddsi
);
1360 oldlen
= olddsi
->length
;
1361 dsi
->length
= newlen
;
1362 /* Break the chain, so adjust_related_strinfo on later pointers in
1363 the chain won't adjust this one anymore. */
1366 dsi
->endptr
= NULL_TREE
;
1370 dsi
= new_strinfo (dst
, didx
, newlen
);
1371 set_strinfo (didx
, dsi
);
1372 find_equal_ptrs (dst
, didx
);
1374 dsi
->writable
= true;
1375 dsi
->dont_invalidate
= true;
1378 tree adj
= NULL_TREE
;
1379 location_t loc
= gimple_location (stmt
);
1380 if (oldlen
== NULL_TREE
)
1382 else if (integer_zerop (oldlen
))
1384 else if (TREE_CODE (oldlen
) == INTEGER_CST
1385 || TREE_CODE (dsi
->length
) == INTEGER_CST
)
1386 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1387 TREE_TYPE (dsi
->length
), dsi
->length
,
1388 fold_convert_loc (loc
, TREE_TYPE (dsi
->length
),
1390 if (adj
!= NULL_TREE
)
1391 adjust_related_strinfos (loc
, dsi
, adj
);
1395 /* memcpy src may not overlap dst, so src doesn't need to be
1396 invalidated either. */
1398 si
->dont_invalidate
= true;
1400 lhs
= gimple_call_lhs (stmt
);
1403 case BUILT_IN_MEMCPY
:
1404 case BUILT_IN_MEMCPY_CHK
:
1405 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1406 laststmt
.stmt
= stmt
;
1407 laststmt
.len
= dsi
->length
;
1408 laststmt
.stridx
= dsi
->idx
;
1410 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1412 case BUILT_IN_MEMPCPY
:
1413 case BUILT_IN_MEMPCPY_CHK
:
1420 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
1421 If strlen of the second argument is known, strlen of the first argument
1422 is increased by the length of the second argument. Furthermore, attempt
1423 to convert it to memcpy/strcpy if the length of the first argument
1427 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1430 tree src
, dst
, srclen
, dstlen
, len
, lhs
, args
, type
, fn
, objsz
, endptr
;
1432 gimple stmt
= gsi_stmt (*gsi
);
1436 src
= gimple_call_arg (stmt
, 1);
1437 dst
= gimple_call_arg (stmt
, 0);
1438 lhs
= gimple_call_lhs (stmt
);
1440 didx
= get_stridx (dst
);
1446 dsi
= get_strinfo (didx
);
1447 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
1449 /* strcat (p, q) can be transformed into
1450 tmp = p + strlen (p); endptr = strpcpy (tmp, q);
1451 with length endptr - p if we need to compute the length
1452 later on. Don't do this transformation if we don't need
1454 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
1458 didx
= new_stridx (dst
);
1464 dsi
= new_strinfo (dst
, didx
, NULL_TREE
);
1465 set_strinfo (didx
, dsi
);
1466 find_equal_ptrs (dst
, didx
);
1470 dsi
= unshare_strinfo (dsi
);
1471 dsi
->length
= NULL_TREE
;
1473 dsi
->endptr
= NULL_TREE
;
1475 dsi
->writable
= true;
1477 dsi
->dont_invalidate
= true;
1484 idx
= get_stridx (src
);
1486 srclen
= build_int_cst (size_type_node
, ~idx
);
1489 si
= get_strinfo (idx
);
1491 srclen
= get_string_length (si
);
1494 loc
= gimple_location (stmt
);
1495 dstlen
= dsi
->length
;
1496 endptr
= dsi
->endptr
;
1498 dsi
= unshare_strinfo (dsi
);
1499 dsi
->endptr
= NULL_TREE
;
1501 dsi
->writable
= true;
1503 if (srclen
!= NULL_TREE
)
1505 dsi
->length
= fold_build2_loc (loc
, PLUS_EXPR
, TREE_TYPE (dsi
->length
),
1506 dsi
->length
, srclen
);
1507 adjust_related_strinfos (loc
, dsi
, srclen
);
1508 dsi
->dont_invalidate
= true;
1513 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1514 dsi
->dont_invalidate
= true;
1518 /* strcat src may not overlap dst, so src doesn't need to be
1519 invalidated either. */
1520 si
->dont_invalidate
= true;
1522 /* For now. Could remove the lhs from the call and add
1523 lhs = dst; afterwards. */
1531 case BUILT_IN_STRCAT
:
1532 if (srclen
!= NULL_TREE
)
1533 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1535 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
1537 case BUILT_IN_STRCAT_CHK
:
1538 if (srclen
!= NULL_TREE
)
1539 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1541 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
1542 objsz
= gimple_call_arg (stmt
, 2);
1548 if (fn
== NULL_TREE
)
1552 if (srclen
!= NULL_TREE
)
1554 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1555 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1557 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1558 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
1559 build_int_cst (type
, 1));
1560 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1564 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
1566 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1567 TREE_TYPE (dst
), unshare_expr (dst
),
1568 fold_convert_loc (loc
, sizetype
,
1569 unshare_expr (dstlen
)));
1570 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
1572 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1574 fprintf (dump_file
, "Optimizing: ");
1575 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1577 if (srclen
!= NULL_TREE
)
1578 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
1579 dst
, src
, len
, objsz
);
1581 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
1585 stmt
= gsi_stmt (*gsi
);
1587 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1589 fprintf (dump_file
, "into: ");
1590 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1592 /* If srclen == NULL, note that current string length can be
1593 computed by transforming this strcpy into stpcpy. */
1594 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
1596 adjust_last_stmt (dsi
, stmt
, true);
1597 if (srclen
!= NULL_TREE
)
1599 laststmt
.stmt
= stmt
;
1600 laststmt
.len
= srclen
;
1601 laststmt
.stridx
= dsi
->idx
;
1604 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1605 fprintf (dump_file
, "not possible.\n");
1608 /* Handle a POINTER_PLUS_EXPR statement.
1609 For p = "abcd" + 2; compute associated length, or if
1610 p = q + off is pointing to a '\0' character of a string, call
1611 zero_length_string on it. */
1614 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
1616 gimple stmt
= gsi_stmt (*gsi
);
1617 tree lhs
= gimple_assign_lhs (stmt
), off
;
1618 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
1626 tree off
= gimple_assign_rhs2 (stmt
);
1627 if (tree_fits_uhwi_p (off
)
1628 && tree_to_uhwi (off
) <= (unsigned HOST_WIDE_INT
) ~idx
)
1629 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
1630 = ~(~idx
- (int) tree_to_uhwi (off
));
1634 si
= get_strinfo (idx
);
1635 if (si
== NULL
|| si
->length
== NULL_TREE
)
1638 off
= gimple_assign_rhs2 (stmt
);
1640 if (operand_equal_p (si
->length
, off
, 0))
1641 zsi
= zero_length_string (lhs
, si
);
1642 else if (TREE_CODE (off
) == SSA_NAME
)
1644 gimple def_stmt
= SSA_NAME_DEF_STMT (off
);
1645 if (gimple_assign_single_p (def_stmt
)
1646 && operand_equal_p (si
->length
, gimple_assign_rhs1 (def_stmt
), 0))
1647 zsi
= zero_length_string (lhs
, si
);
1650 && si
->endptr
!= NULL_TREE
1651 && si
->endptr
!= lhs
1652 && TREE_CODE (si
->endptr
) == SSA_NAME
)
1654 enum tree_code rhs_code
1655 = useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (si
->endptr
))
1656 ? SSA_NAME
: NOP_EXPR
;
1657 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, si
->endptr
, NULL_TREE
);
1658 gcc_assert (gsi_stmt (*gsi
) == stmt
);
1663 /* Handle a single character store. */
1666 handle_char_store (gimple_stmt_iterator
*gsi
)
1670 gimple stmt
= gsi_stmt (*gsi
);
1671 tree ssaname
= NULL_TREE
, lhs
= gimple_assign_lhs (stmt
);
1673 if (TREE_CODE (lhs
) == MEM_REF
1674 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
)
1676 if (integer_zerop (TREE_OPERAND (lhs
, 1)))
1678 ssaname
= TREE_OPERAND (lhs
, 0);
1679 idx
= get_stridx (ssaname
);
1683 idx
= get_addr_stridx (lhs
);
1687 si
= get_strinfo (idx
);
1688 if (si
!= NULL
&& si
->length
!= NULL_TREE
&& integer_zerop (si
->length
))
1690 if (initializer_zerop (gimple_assign_rhs1 (stmt
)))
1692 /* When storing '\0', the store can be removed
1693 if we know it has been stored in the current function. */
1694 if (!stmt_could_throw_p (stmt
) && si
->writable
)
1696 unlink_stmt_vdef (stmt
);
1697 release_defs (stmt
);
1698 gsi_remove (gsi
, true);
1703 si
->writable
= true;
1709 /* Otherwise this statement overwrites the '\0' with
1710 something, if the previous stmt was a memcpy,
1711 its length may be decreased. */
1712 adjust_last_stmt (si
, stmt
, false);
1714 else if (si
!= NULL
&& integer_zerop (gimple_assign_rhs1 (stmt
)))
1716 si
= unshare_strinfo (si
);
1717 si
->length
= build_int_cst (size_type_node
, 0);
1723 si
->writable
= true;
1724 if (ssaname
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
1725 si
->endptr
= ssaname
;
1726 si
->dont_invalidate
= true;
1728 /* If si->length is non-zero constant, we aren't overwriting '\0',
1729 and if we aren't storing '\0', we know that the length of the
1730 string and any other zero terminated string in memory remains
1731 the same. In that case we move to the next gimple statement and
1732 return to signal the caller that it shouldn't invalidate anything.
1734 This is benefical for cases like:
1739 strcpy (p, "foobar");
1740 size_t len = strlen (p); // This can be optimized into 6
1741 size_t len2 = strlen (q); // This has to be computed
1743 size_t len3 = strlen (p); // This can be optimized into 6
1744 size_t len4 = strlen (q); // This can be optimized into len2
1745 bar (len, len2, len3, len4);
1748 else if (si
!= NULL
&& si
->length
!= NULL_TREE
1749 && TREE_CODE (si
->length
) == INTEGER_CST
1750 && integer_nonzerop (gimple_assign_rhs1 (stmt
)))
1756 else if (idx
== 0 && initializer_zerop (gimple_assign_rhs1 (stmt
)))
1760 si
= zero_length_string (ssaname
, NULL
);
1762 si
->dont_invalidate
= true;
1766 int idx
= new_addr_stridx (lhs
);
1769 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
1770 build_int_cst (size_type_node
, 0));
1771 set_strinfo (idx
, si
);
1772 si
->dont_invalidate
= true;
1776 si
->writable
= true;
1779 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == STRING_CST
1780 && ssaname
== NULL_TREE
1781 && TREE_CODE (TREE_TYPE (lhs
)) == ARRAY_TYPE
)
1783 size_t l
= strlen (TREE_STRING_POINTER (gimple_assign_rhs1 (stmt
)));
1784 HOST_WIDE_INT a
= int_size_in_bytes (TREE_TYPE (lhs
));
1785 if (a
> 0 && (unsigned HOST_WIDE_INT
) a
> l
)
1787 int idx
= new_addr_stridx (lhs
);
1790 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
1791 build_int_cst (size_type_node
, l
));
1792 set_strinfo (idx
, si
);
1793 si
->dont_invalidate
= true;
1798 if (si
!= NULL
&& initializer_zerop (gimple_assign_rhs1 (stmt
)))
1800 /* Allow adjust_last_stmt to remove it if the stored '\0'
1801 is immediately overwritten. */
1802 laststmt
.stmt
= stmt
;
1803 laststmt
.len
= build_int_cst (size_type_node
, 1);
1804 laststmt
.stridx
= si
->idx
;
1809 /* Attempt to optimize a single statement at *GSI using string length
1813 strlen_optimize_stmt (gimple_stmt_iterator
*gsi
)
1815 gimple stmt
= gsi_stmt (*gsi
);
1817 if (is_gimple_call (stmt
))
1819 tree callee
= gimple_call_fndecl (stmt
);
1820 if (gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
1821 switch (DECL_FUNCTION_CODE (callee
))
1823 case BUILT_IN_STRLEN
:
1824 handle_builtin_strlen (gsi
);
1826 case BUILT_IN_STRCHR
:
1827 handle_builtin_strchr (gsi
);
1829 case BUILT_IN_STRCPY
:
1830 case BUILT_IN_STRCPY_CHK
:
1831 case BUILT_IN_STPCPY
:
1832 case BUILT_IN_STPCPY_CHK
:
1833 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee
), gsi
);
1835 case BUILT_IN_MEMCPY
:
1836 case BUILT_IN_MEMCPY_CHK
:
1837 case BUILT_IN_MEMPCPY
:
1838 case BUILT_IN_MEMPCPY_CHK
:
1839 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee
), gsi
);
1841 case BUILT_IN_STRCAT
:
1842 case BUILT_IN_STRCAT_CHK
:
1843 handle_builtin_strcat (DECL_FUNCTION_CODE (callee
), gsi
);
1849 else if (is_gimple_assign (stmt
))
1851 tree lhs
= gimple_assign_lhs (stmt
);
1853 if (TREE_CODE (lhs
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (lhs
)))
1855 if (gimple_assign_single_p (stmt
)
1856 || (gimple_assign_cast_p (stmt
)
1857 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
1859 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
1860 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = idx
;
1862 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
1863 handle_pointer_plus (gsi
);
1865 else if (TREE_CODE (lhs
) != SSA_NAME
&& !TREE_SIDE_EFFECTS (lhs
))
1867 tree type
= TREE_TYPE (lhs
);
1868 if (TREE_CODE (type
) == ARRAY_TYPE
)
1869 type
= TREE_TYPE (type
);
1870 if (TREE_CODE (type
) == INTEGER_TYPE
1871 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
1872 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
))
1874 if (! handle_char_store (gsi
))
1880 if (gimple_vdef (stmt
))
1881 maybe_invalidate (stmt
);
1885 /* Recursively call maybe_invalidate on stmts that might be executed
1886 in between dombb and current bb and that contain a vdef. Stop when
1887 *count stmts are inspected, or if the whole strinfo vector has
1888 been invalidated. */
1891 do_invalidate (basic_block dombb
, gimple phi
, bitmap visited
, int *count
)
1893 unsigned int i
, n
= gimple_phi_num_args (phi
);
1895 for (i
= 0; i
< n
; i
++)
1897 tree vuse
= gimple_phi_arg_def (phi
, i
);
1898 gimple stmt
= SSA_NAME_DEF_STMT (vuse
);
1899 basic_block bb
= gimple_bb (stmt
);
1902 || !bitmap_set_bit (visited
, bb
->index
)
1903 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
1907 if (gimple_code (stmt
) == GIMPLE_PHI
)
1909 do_invalidate (dombb
, stmt
, visited
, count
);
1916 if (!maybe_invalidate (stmt
))
1921 vuse
= gimple_vuse (stmt
);
1922 stmt
= SSA_NAME_DEF_STMT (vuse
);
1923 if (gimple_bb (stmt
) != bb
)
1925 bb
= gimple_bb (stmt
);
1928 || !bitmap_set_bit (visited
, bb
->index
)
1929 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
1936 class strlen_dom_walker
: public dom_walker
1939 strlen_dom_walker (cdi_direction direction
) : dom_walker (direction
) {}
1941 virtual void before_dom_children (basic_block
);
1942 virtual void after_dom_children (basic_block
);
1945 /* Callback for walk_dominator_tree. Attempt to optimize various
1946 string ops by remembering string lenths pointed by pointer SSA_NAMEs. */
1949 strlen_dom_walker::before_dom_children (basic_block bb
)
1951 gimple_stmt_iterator gsi
;
1952 basic_block dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1955 stridx_to_strinfo
= NULL
;
1958 stridx_to_strinfo
= ((vec
<strinfo
, va_heap
, vl_embed
> *) dombb
->aux
);
1959 if (stridx_to_strinfo
)
1961 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1963 gimple phi
= gsi_stmt (gsi
);
1964 if (virtual_operand_p (gimple_phi_result (phi
)))
1966 bitmap visited
= BITMAP_ALLOC (NULL
);
1967 int count_vdef
= 100;
1968 do_invalidate (dombb
, phi
, visited
, &count_vdef
);
1969 BITMAP_FREE (visited
);
1970 if (count_vdef
== 0)
1972 /* If there were too many vdefs in between immediate
1973 dominator and current bb, invalidate everything.
1974 If stridx_to_strinfo has been unshared, we need
1975 to free it, otherwise just set it to NULL. */
1976 if (!strinfo_shared ())
1982 vec_safe_iterate (stridx_to_strinfo
, i
, &si
);
1986 (*stridx_to_strinfo
)[i
] = NULL
;
1990 stridx_to_strinfo
= NULL
;
1998 /* If all PHI arguments have the same string index, the PHI result
2000 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2002 gimple phi
= gsi_stmt (gsi
);
2003 tree result
= gimple_phi_result (phi
);
2004 if (!virtual_operand_p (result
) && POINTER_TYPE_P (TREE_TYPE (result
)))
2006 int idx
= get_stridx (gimple_phi_arg_def (phi
, 0));
2009 unsigned int i
, n
= gimple_phi_num_args (phi
);
2010 for (i
= 1; i
< n
; i
++)
2011 if (idx
!= get_stridx (gimple_phi_arg_def (phi
, i
)))
2014 ssa_ver_to_stridx
[SSA_NAME_VERSION (result
)] = idx
;
2019 /* Attempt to optimize individual statements. */
2020 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2021 if (strlen_optimize_stmt (&gsi
))
2024 bb
->aux
= stridx_to_strinfo
;
2025 if (vec_safe_length (stridx_to_strinfo
) && !strinfo_shared ())
2026 (*stridx_to_strinfo
)[0] = (strinfo
) bb
;
2029 /* Callback for walk_dominator_tree. Free strinfo vector if it is
2030 owned by the current bb, clear bb->aux. */
2033 strlen_dom_walker::after_dom_children (basic_block bb
)
2037 stridx_to_strinfo
= ((vec
<strinfo
, va_heap
, vl_embed
> *) bb
->aux
);
2038 if (vec_safe_length (stridx_to_strinfo
)
2039 && (*stridx_to_strinfo
)[0] == (strinfo
) bb
)
2044 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
2046 vec_free (stridx_to_strinfo
);
2052 /* Main entry point. */
2055 tree_ssa_strlen (void)
2057 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
2059 strinfo_pool
= create_alloc_pool ("strinfo_struct pool",
2060 sizeof (struct strinfo_struct
), 64);
2062 calculate_dominance_info (CDI_DOMINATORS
);
2064 /* String length optimization is implemented as a walk of the dominator
2065 tree and a forward walk of statements within each block. */
2066 strlen_dom_walker (CDI_DOMINATORS
).walk (cfun
->cfg
->x_entry_block_ptr
);
2068 ssa_ver_to_stridx
.release ();
2069 free_alloc_pool (strinfo_pool
);
2070 if (decl_to_stridxlist_htab
.is_created ())
2072 obstack_free (&stridx_obstack
, NULL
);
2073 decl_to_stridxlist_htab
.dispose ();
2075 laststmt
.stmt
= NULL
;
2076 laststmt
.len
= NULL_TREE
;
2077 laststmt
.stridx
= 0;
2085 return flag_optimize_strlen
!= 0;
2090 const pass_data pass_data_strlen
=
2092 GIMPLE_PASS
, /* type */
2093 "strlen", /* name */
2094 OPTGROUP_NONE
, /* optinfo_flags */
2095 true, /* has_gate */
2096 true, /* has_execute */
2097 TV_TREE_STRLEN
, /* tv_id */
2098 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2099 0, /* properties_provided */
2100 0, /* properties_destroyed */
2101 0, /* todo_flags_start */
2102 TODO_verify_ssa
, /* todo_flags_finish */
2105 class pass_strlen
: public gimple_opt_pass
2108 pass_strlen (gcc::context
*ctxt
)
2109 : gimple_opt_pass (pass_data_strlen
, ctxt
)
2112 /* opt_pass methods: */
2113 bool gate () { return gate_strlen (); }
2114 unsigned int execute () { return tree_ssa_strlen (); }
2116 }; // class pass_strlen
2121 make_pass_strlen (gcc::context
*ctxt
)
2123 return new pass_strlen (ctxt
);