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_low_cst (o
, 0) : 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 (host_integerp (len
, 1))
851 if (!host_integerp (last
.len
, 1)
852 || integer_zerop (len
)
853 || (unsigned HOST_WIDE_INT
) tree_low_cst (len
, 1)
854 != (unsigned HOST_WIDE_INT
) tree_low_cst (last
.len
, 1) + 1)
856 /* Don't adjust the length if it is divisible by 4, it is more efficient
857 to store the extra '\0' in that case. */
858 if ((((unsigned HOST_WIDE_INT
) tree_low_cst (len
, 1)) & 3) == 0)
861 else if (TREE_CODE (len
) == SSA_NAME
)
863 gimple def_stmt
= SSA_NAME_DEF_STMT (len
);
864 if (!is_gimple_assign (def_stmt
)
865 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
866 || gimple_assign_rhs1 (def_stmt
) != last
.len
867 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
873 gimple_call_set_arg (last
.stmt
, 2, last
.len
);
874 update_stmt (last
.stmt
);
877 /* Handle a strlen call. If strlen of the argument is known, replace
878 the strlen call with the known value, otherwise remember that strlen
879 of the argument is stored in the lhs SSA_NAME. */
882 handle_builtin_strlen (gimple_stmt_iterator
*gsi
)
886 gimple stmt
= gsi_stmt (*gsi
);
887 tree lhs
= gimple_call_lhs (stmt
);
889 if (lhs
== NULL_TREE
)
892 src
= gimple_call_arg (stmt
, 0);
893 idx
= get_stridx (src
);
900 rhs
= build_int_cst (TREE_TYPE (lhs
), ~idx
);
904 si
= get_strinfo (idx
);
906 rhs
= get_string_length (si
);
908 if (rhs
!= NULL_TREE
)
910 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
912 fprintf (dump_file
, "Optimizing: ");
913 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
915 rhs
= unshare_expr (rhs
);
916 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
917 rhs
= fold_convert_loc (gimple_location (stmt
),
918 TREE_TYPE (lhs
), rhs
);
919 if (!update_call_from_tree (gsi
, rhs
))
920 gimplify_and_update_call_from_tree (gsi
, rhs
);
921 stmt
= gsi_stmt (*gsi
);
923 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
925 fprintf (dump_file
, "into: ");
926 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
929 && TREE_CODE (si
->length
) != SSA_NAME
930 && TREE_CODE (si
->length
) != INTEGER_CST
931 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
933 si
= unshare_strinfo (si
);
939 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
942 idx
= new_stridx (src
);
943 else if (get_strinfo (idx
) != NULL
)
947 strinfo si
= new_strinfo (src
, idx
, lhs
);
948 set_strinfo (idx
, si
);
949 find_equal_ptrs (src
, idx
);
953 /* Handle a strchr call. If strlen of the first argument is known, replace
954 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
955 that lhs of the call is endptr and strlen of the argument is endptr - x. */
958 handle_builtin_strchr (gimple_stmt_iterator
*gsi
)
962 gimple stmt
= gsi_stmt (*gsi
);
963 tree lhs
= gimple_call_lhs (stmt
);
965 if (lhs
== NULL_TREE
)
968 if (!integer_zerop (gimple_call_arg (stmt
, 1)))
971 src
= gimple_call_arg (stmt
, 0);
972 idx
= get_stridx (src
);
979 rhs
= build_int_cst (size_type_node
, ~idx
);
983 si
= get_strinfo (idx
);
985 rhs
= get_string_length (si
);
987 if (rhs
!= NULL_TREE
)
989 location_t loc
= gimple_location (stmt
);
991 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
993 fprintf (dump_file
, "Optimizing: ");
994 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
996 if (si
!= NULL
&& si
->endptr
!= NULL_TREE
)
998 rhs
= unshare_expr (si
->endptr
);
999 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1001 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1005 rhs
= fold_convert_loc (loc
, sizetype
, unshare_expr (rhs
));
1006 rhs
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1007 TREE_TYPE (src
), src
, rhs
);
1008 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1010 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1012 if (!update_call_from_tree (gsi
, rhs
))
1013 gimplify_and_update_call_from_tree (gsi
, rhs
);
1014 stmt
= gsi_stmt (*gsi
);
1016 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1018 fprintf (dump_file
, "into: ");
1019 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1022 && si
->endptr
== NULL_TREE
1023 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1025 si
= unshare_strinfo (si
);
1028 zero_length_string (lhs
, si
);
1032 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1034 if (TREE_CODE (src
) != SSA_NAME
|| !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src
))
1037 idx
= new_stridx (src
);
1038 else if (get_strinfo (idx
) != NULL
)
1040 zero_length_string (lhs
, NULL
);
1045 location_t loc
= gimple_location (stmt
);
1046 tree lhsu
= fold_convert_loc (loc
, size_type_node
, lhs
);
1047 tree srcu
= fold_convert_loc (loc
, size_type_node
, src
);
1048 tree length
= fold_build2_loc (loc
, MINUS_EXPR
,
1049 size_type_node
, lhsu
, srcu
);
1050 strinfo si
= new_strinfo (src
, idx
, length
);
1052 set_strinfo (idx
, si
);
1053 find_equal_ptrs (src
, idx
);
1054 zero_length_string (lhs
, si
);
1058 zero_length_string (lhs
, NULL
);
1061 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1062 If strlen of the second argument is known, strlen of the first argument
1063 is the same after this call. Furthermore, attempt to convert it to
1067 handle_builtin_strcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1070 tree src
, dst
, srclen
, len
, lhs
, args
, type
, fn
, oldlen
;
1072 gimple stmt
= gsi_stmt (*gsi
);
1073 strinfo si
, dsi
, olddsi
, zsi
;
1076 src
= gimple_call_arg (stmt
, 1);
1077 dst
= gimple_call_arg (stmt
, 0);
1078 lhs
= gimple_call_lhs (stmt
);
1079 idx
= get_stridx (src
);
1082 si
= get_strinfo (idx
);
1084 didx
= get_stridx (dst
);
1088 olddsi
= get_strinfo (didx
);
1093 adjust_last_stmt (olddsi
, stmt
, false);
1097 srclen
= get_string_length (si
);
1099 srclen
= build_int_cst (size_type_node
, ~idx
);
1101 loc
= gimple_location (stmt
);
1102 if (srclen
== NULL_TREE
)
1105 case BUILT_IN_STRCPY
:
1106 case BUILT_IN_STRCPY_CHK
:
1107 if (lhs
!= NULL_TREE
|| !builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1110 case BUILT_IN_STPCPY
:
1111 case BUILT_IN_STPCPY_CHK
:
1112 if (lhs
== NULL_TREE
)
1116 tree lhsuint
= fold_convert_loc (loc
, size_type_node
, lhs
);
1117 srclen
= fold_convert_loc (loc
, size_type_node
, dst
);
1118 srclen
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
1128 didx
= new_stridx (dst
);
1134 oldlen
= olddsi
->length
;
1135 dsi
= unshare_strinfo (olddsi
);
1136 dsi
->length
= srclen
;
1137 /* Break the chain, so adjust_related_strinfo on later pointers in
1138 the chain won't adjust this one anymore. */
1141 dsi
->endptr
= NULL_TREE
;
1145 dsi
= new_strinfo (dst
, didx
, srclen
);
1146 set_strinfo (didx
, dsi
);
1147 find_equal_ptrs (dst
, didx
);
1149 dsi
->writable
= true;
1150 dsi
->dont_invalidate
= true;
1152 if (dsi
->length
== NULL_TREE
)
1156 /* If string length of src is unknown, use delayed length
1157 computation. If string lenth of dst will be needed, it
1158 can be computed by transforming this strcpy call into
1159 stpcpy and subtracting dst from the return value. */
1161 /* Look for earlier strings whose length could be determined if
1162 this strcpy is turned into an stpcpy. */
1164 if (dsi
->prev
!= 0 && (chainsi
= verify_related_strinfos (dsi
)) != NULL
)
1166 for (; chainsi
&& chainsi
!= dsi
; chainsi
= get_strinfo (chainsi
->next
))
1168 /* When setting a stmt for delayed length computation
1169 prevent all strinfos through dsi from being
1171 chainsi
= unshare_strinfo (chainsi
);
1172 chainsi
->stmt
= stmt
;
1173 chainsi
->length
= NULL_TREE
;
1174 chainsi
->endptr
= NULL_TREE
;
1175 chainsi
->dont_invalidate
= true;
1184 tree adj
= NULL_TREE
;
1185 if (oldlen
== NULL_TREE
)
1187 else if (integer_zerop (oldlen
))
1189 else if (TREE_CODE (oldlen
) == INTEGER_CST
1190 || TREE_CODE (srclen
) == INTEGER_CST
)
1191 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1192 TREE_TYPE (srclen
), srclen
,
1193 fold_convert_loc (loc
, TREE_TYPE (srclen
),
1195 if (adj
!= NULL_TREE
)
1196 adjust_related_strinfos (loc
, dsi
, adj
);
1200 /* strcpy src may not overlap dst, so src doesn't need to be
1201 invalidated either. */
1203 si
->dont_invalidate
= true;
1209 case BUILT_IN_STRCPY
:
1210 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1212 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1214 case BUILT_IN_STRCPY_CHK
:
1215 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1217 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1219 case BUILT_IN_STPCPY
:
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); */
1227 zsi
= zero_length_string (lhs
, dsi
);
1230 case BUILT_IN_STPCPY_CHK
:
1231 /* This would need adjustment of the lhs (subtract one),
1232 or detection that the trailing '\0' doesn't need to be
1233 written, if it will be immediately overwritten.
1234 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1238 zsi
= zero_length_string (lhs
, dsi
);
1245 zsi
->dont_invalidate
= true;
1247 if (fn
== NULL_TREE
)
1250 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1251 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1253 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1254 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
, build_int_cst (type
, 1));
1255 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1257 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1259 fprintf (dump_file
, "Optimizing: ");
1260 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1262 if (gimple_call_num_args (stmt
) == 2)
1263 success
= update_gimple_call (gsi
, fn
, 3, dst
, src
, len
);
1265 success
= update_gimple_call (gsi
, fn
, 4, dst
, src
, len
,
1266 gimple_call_arg (stmt
, 2));
1269 stmt
= gsi_stmt (*gsi
);
1271 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1273 fprintf (dump_file
, "into: ");
1274 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1276 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1277 laststmt
.stmt
= stmt
;
1278 laststmt
.len
= srclen
;
1279 laststmt
.stridx
= dsi
->idx
;
1281 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1282 fprintf (dump_file
, "not possible.\n");
1285 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
1286 If strlen of the second argument is known and length of the third argument
1287 is that plus one, strlen of the first argument is the same after this
1291 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1294 tree src
, dst
, len
, lhs
, oldlen
, newlen
;
1295 gimple stmt
= gsi_stmt (*gsi
);
1296 strinfo si
, dsi
, olddsi
;
1298 len
= gimple_call_arg (stmt
, 2);
1299 src
= gimple_call_arg (stmt
, 1);
1300 dst
= gimple_call_arg (stmt
, 0);
1301 idx
= get_stridx (src
);
1305 didx
= get_stridx (dst
);
1308 olddsi
= get_strinfo (didx
);
1313 && host_integerp (len
, 1)
1314 && !integer_zerop (len
))
1315 adjust_last_stmt (olddsi
, stmt
, false);
1321 /* Handle memcpy (x, y, l) where l is strlen (y) + 1. */
1322 si
= get_strinfo (idx
);
1323 if (si
== NULL
|| si
->length
== NULL_TREE
)
1325 if (TREE_CODE (len
) != SSA_NAME
)
1327 def_stmt
= SSA_NAME_DEF_STMT (len
);
1328 if (!is_gimple_assign (def_stmt
)
1329 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1330 || gimple_assign_rhs1 (def_stmt
) != si
->length
1331 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1337 /* Handle memcpy (x, "abcd", 5) or
1338 memcpy (x, "abc\0uvw", 7). */
1339 if (!host_integerp (len
, 1)
1340 || (unsigned HOST_WIDE_INT
) tree_low_cst (len
, 1)
1341 <= (unsigned HOST_WIDE_INT
) ~idx
)
1345 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
1346 adjust_last_stmt (olddsi
, stmt
, false);
1350 didx
= new_stridx (dst
);
1355 newlen
= si
->length
;
1357 newlen
= build_int_cst (size_type_node
, ~idx
);
1361 dsi
= unshare_strinfo (olddsi
);
1362 oldlen
= olddsi
->length
;
1363 dsi
->length
= newlen
;
1364 /* Break the chain, so adjust_related_strinfo on later pointers in
1365 the chain won't adjust this one anymore. */
1368 dsi
->endptr
= NULL_TREE
;
1372 dsi
= new_strinfo (dst
, didx
, newlen
);
1373 set_strinfo (didx
, dsi
);
1374 find_equal_ptrs (dst
, didx
);
1376 dsi
->writable
= true;
1377 dsi
->dont_invalidate
= true;
1380 tree adj
= NULL_TREE
;
1381 location_t loc
= gimple_location (stmt
);
1382 if (oldlen
== NULL_TREE
)
1384 else if (integer_zerop (oldlen
))
1386 else if (TREE_CODE (oldlen
) == INTEGER_CST
1387 || TREE_CODE (dsi
->length
) == INTEGER_CST
)
1388 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1389 TREE_TYPE (dsi
->length
), dsi
->length
,
1390 fold_convert_loc (loc
, TREE_TYPE (dsi
->length
),
1392 if (adj
!= NULL_TREE
)
1393 adjust_related_strinfos (loc
, dsi
, adj
);
1397 /* memcpy src may not overlap dst, so src doesn't need to be
1398 invalidated either. */
1400 si
->dont_invalidate
= true;
1402 lhs
= gimple_call_lhs (stmt
);
1405 case BUILT_IN_MEMCPY
:
1406 case BUILT_IN_MEMCPY_CHK
:
1407 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1408 laststmt
.stmt
= stmt
;
1409 laststmt
.len
= dsi
->length
;
1410 laststmt
.stridx
= dsi
->idx
;
1412 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1414 case BUILT_IN_MEMPCPY
:
1415 case BUILT_IN_MEMPCPY_CHK
:
1422 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
1423 If strlen of the second argument is known, strlen of the first argument
1424 is increased by the length of the second argument. Furthermore, attempt
1425 to convert it to memcpy/strcpy if the length of the first argument
1429 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1432 tree src
, dst
, srclen
, dstlen
, len
, lhs
, args
, type
, fn
, objsz
, endptr
;
1434 gimple stmt
= gsi_stmt (*gsi
);
1438 src
= gimple_call_arg (stmt
, 1);
1439 dst
= gimple_call_arg (stmt
, 0);
1440 lhs
= gimple_call_lhs (stmt
);
1442 didx
= get_stridx (dst
);
1448 dsi
= get_strinfo (didx
);
1449 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
1451 /* strcat (p, q) can be transformed into
1452 tmp = p + strlen (p); endptr = strpcpy (tmp, q);
1453 with length endptr - p if we need to compute the length
1454 later on. Don't do this transformation if we don't need
1456 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
1460 didx
= new_stridx (dst
);
1466 dsi
= new_strinfo (dst
, didx
, NULL_TREE
);
1467 set_strinfo (didx
, dsi
);
1468 find_equal_ptrs (dst
, didx
);
1472 dsi
= unshare_strinfo (dsi
);
1473 dsi
->length
= NULL_TREE
;
1475 dsi
->endptr
= NULL_TREE
;
1477 dsi
->writable
= true;
1479 dsi
->dont_invalidate
= true;
1486 idx
= get_stridx (src
);
1488 srclen
= build_int_cst (size_type_node
, ~idx
);
1491 si
= get_strinfo (idx
);
1493 srclen
= get_string_length (si
);
1496 loc
= gimple_location (stmt
);
1497 dstlen
= dsi
->length
;
1498 endptr
= dsi
->endptr
;
1500 dsi
= unshare_strinfo (dsi
);
1501 dsi
->endptr
= NULL_TREE
;
1503 dsi
->writable
= true;
1505 if (srclen
!= NULL_TREE
)
1507 dsi
->length
= fold_build2_loc (loc
, PLUS_EXPR
, TREE_TYPE (dsi
->length
),
1508 dsi
->length
, srclen
);
1509 adjust_related_strinfos (loc
, dsi
, srclen
);
1510 dsi
->dont_invalidate
= true;
1515 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1516 dsi
->dont_invalidate
= true;
1520 /* strcat src may not overlap dst, so src doesn't need to be
1521 invalidated either. */
1522 si
->dont_invalidate
= true;
1524 /* For now. Could remove the lhs from the call and add
1525 lhs = dst; afterwards. */
1533 case BUILT_IN_STRCAT
:
1534 if (srclen
!= NULL_TREE
)
1535 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1537 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
1539 case BUILT_IN_STRCAT_CHK
:
1540 if (srclen
!= NULL_TREE
)
1541 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1543 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
1544 objsz
= gimple_call_arg (stmt
, 2);
1550 if (fn
== NULL_TREE
)
1554 if (srclen
!= NULL_TREE
)
1556 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1557 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1559 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1560 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
1561 build_int_cst (type
, 1));
1562 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1566 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
1568 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1569 TREE_TYPE (dst
), unshare_expr (dst
),
1570 fold_convert_loc (loc
, sizetype
,
1571 unshare_expr (dstlen
)));
1572 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
1574 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1576 fprintf (dump_file
, "Optimizing: ");
1577 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1579 if (srclen
!= NULL_TREE
)
1580 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
1581 dst
, src
, len
, objsz
);
1583 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
1587 stmt
= gsi_stmt (*gsi
);
1589 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1591 fprintf (dump_file
, "into: ");
1592 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1594 /* If srclen == NULL, note that current string length can be
1595 computed by transforming this strcpy into stpcpy. */
1596 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
1598 adjust_last_stmt (dsi
, stmt
, true);
1599 if (srclen
!= NULL_TREE
)
1601 laststmt
.stmt
= stmt
;
1602 laststmt
.len
= srclen
;
1603 laststmt
.stridx
= dsi
->idx
;
1606 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1607 fprintf (dump_file
, "not possible.\n");
1610 /* Handle a POINTER_PLUS_EXPR statement.
1611 For p = "abcd" + 2; compute associated length, or if
1612 p = q + off is pointing to a '\0' character of a string, call
1613 zero_length_string on it. */
1616 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
1618 gimple stmt
= gsi_stmt (*gsi
);
1619 tree lhs
= gimple_assign_lhs (stmt
), off
;
1620 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
1628 tree off
= gimple_assign_rhs2 (stmt
);
1629 if (host_integerp (off
, 1)
1630 && (unsigned HOST_WIDE_INT
) tree_low_cst (off
, 1)
1631 <= (unsigned HOST_WIDE_INT
) ~idx
)
1632 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
1633 = ~(~idx
- (int) tree_low_cst (off
, 1));
1637 si
= get_strinfo (idx
);
1638 if (si
== NULL
|| si
->length
== NULL_TREE
)
1641 off
= gimple_assign_rhs2 (stmt
);
1643 if (operand_equal_p (si
->length
, off
, 0))
1644 zsi
= zero_length_string (lhs
, si
);
1645 else if (TREE_CODE (off
) == SSA_NAME
)
1647 gimple def_stmt
= SSA_NAME_DEF_STMT (off
);
1648 if (gimple_assign_single_p (def_stmt
)
1649 && operand_equal_p (si
->length
, gimple_assign_rhs1 (def_stmt
), 0))
1650 zsi
= zero_length_string (lhs
, si
);
1653 && si
->endptr
!= NULL_TREE
1654 && si
->endptr
!= lhs
1655 && TREE_CODE (si
->endptr
) == SSA_NAME
)
1657 enum tree_code rhs_code
1658 = useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (si
->endptr
))
1659 ? SSA_NAME
: NOP_EXPR
;
1660 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, si
->endptr
, NULL_TREE
);
1661 gcc_assert (gsi_stmt (*gsi
) == stmt
);
1666 /* Handle a single character store. */
1669 handle_char_store (gimple_stmt_iterator
*gsi
)
1673 gimple stmt
= gsi_stmt (*gsi
);
1674 tree ssaname
= NULL_TREE
, lhs
= gimple_assign_lhs (stmt
);
1676 if (TREE_CODE (lhs
) == MEM_REF
1677 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
)
1679 if (integer_zerop (TREE_OPERAND (lhs
, 1)))
1681 ssaname
= TREE_OPERAND (lhs
, 0);
1682 idx
= get_stridx (ssaname
);
1686 idx
= get_addr_stridx (lhs
);
1690 si
= get_strinfo (idx
);
1691 if (si
!= NULL
&& si
->length
!= NULL_TREE
&& integer_zerop (si
->length
))
1693 if (initializer_zerop (gimple_assign_rhs1 (stmt
)))
1695 /* When storing '\0', the store can be removed
1696 if we know it has been stored in the current function. */
1697 if (!stmt_could_throw_p (stmt
) && si
->writable
)
1699 unlink_stmt_vdef (stmt
);
1700 release_defs (stmt
);
1701 gsi_remove (gsi
, true);
1706 si
->writable
= true;
1712 /* Otherwise this statement overwrites the '\0' with
1713 something, if the previous stmt was a memcpy,
1714 its length may be decreased. */
1715 adjust_last_stmt (si
, stmt
, false);
1717 else if (si
!= NULL
&& integer_zerop (gimple_assign_rhs1 (stmt
)))
1719 si
= unshare_strinfo (si
);
1720 si
->length
= build_int_cst (size_type_node
, 0);
1726 si
->writable
= true;
1727 if (ssaname
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
1728 si
->endptr
= ssaname
;
1729 si
->dont_invalidate
= true;
1731 /* If si->length is non-zero constant, we aren't overwriting '\0',
1732 and if we aren't storing '\0', we know that the length of the
1733 string and any other zero terminated string in memory remains
1734 the same. In that case we move to the next gimple statement and
1735 return to signal the caller that it shouldn't invalidate anything.
1737 This is benefical for cases like:
1742 strcpy (p, "foobar");
1743 size_t len = strlen (p); // This can be optimized into 6
1744 size_t len2 = strlen (q); // This has to be computed
1746 size_t len3 = strlen (p); // This can be optimized into 6
1747 size_t len4 = strlen (q); // This can be optimized into len2
1748 bar (len, len2, len3, len4);
1751 else if (si
!= NULL
&& si
->length
!= NULL_TREE
1752 && TREE_CODE (si
->length
) == INTEGER_CST
1753 && integer_nonzerop (gimple_assign_rhs1 (stmt
)))
1759 else if (idx
== 0 && initializer_zerop (gimple_assign_rhs1 (stmt
)))
1763 si
= zero_length_string (ssaname
, NULL
);
1765 si
->dont_invalidate
= true;
1769 int idx
= new_addr_stridx (lhs
);
1772 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
1773 build_int_cst (size_type_node
, 0));
1774 set_strinfo (idx
, si
);
1775 si
->dont_invalidate
= true;
1779 si
->writable
= true;
1782 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == STRING_CST
1783 && ssaname
== NULL_TREE
1784 && TREE_CODE (TREE_TYPE (lhs
)) == ARRAY_TYPE
)
1786 size_t l
= strlen (TREE_STRING_POINTER (gimple_assign_rhs1 (stmt
)));
1787 HOST_WIDE_INT a
= int_size_in_bytes (TREE_TYPE (lhs
));
1788 if (a
> 0 && (unsigned HOST_WIDE_INT
) a
> l
)
1790 int idx
= new_addr_stridx (lhs
);
1793 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
1794 build_int_cst (size_type_node
, l
));
1795 set_strinfo (idx
, si
);
1796 si
->dont_invalidate
= true;
1801 if (si
!= NULL
&& initializer_zerop (gimple_assign_rhs1 (stmt
)))
1803 /* Allow adjust_last_stmt to remove it if the stored '\0'
1804 is immediately overwritten. */
1805 laststmt
.stmt
= stmt
;
1806 laststmt
.len
= build_int_cst (size_type_node
, 1);
1807 laststmt
.stridx
= si
->idx
;
1812 /* Attempt to optimize a single statement at *GSI using string length
1816 strlen_optimize_stmt (gimple_stmt_iterator
*gsi
)
1818 gimple stmt
= gsi_stmt (*gsi
);
1820 if (is_gimple_call (stmt
))
1822 tree callee
= gimple_call_fndecl (stmt
);
1823 if (gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
1824 switch (DECL_FUNCTION_CODE (callee
))
1826 case BUILT_IN_STRLEN
:
1827 handle_builtin_strlen (gsi
);
1829 case BUILT_IN_STRCHR
:
1830 handle_builtin_strchr (gsi
);
1832 case BUILT_IN_STRCPY
:
1833 case BUILT_IN_STRCPY_CHK
:
1834 case BUILT_IN_STPCPY
:
1835 case BUILT_IN_STPCPY_CHK
:
1836 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee
), gsi
);
1838 case BUILT_IN_MEMCPY
:
1839 case BUILT_IN_MEMCPY_CHK
:
1840 case BUILT_IN_MEMPCPY
:
1841 case BUILT_IN_MEMPCPY_CHK
:
1842 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee
), gsi
);
1844 case BUILT_IN_STRCAT
:
1845 case BUILT_IN_STRCAT_CHK
:
1846 handle_builtin_strcat (DECL_FUNCTION_CODE (callee
), gsi
);
1852 else if (is_gimple_assign (stmt
))
1854 tree lhs
= gimple_assign_lhs (stmt
);
1856 if (TREE_CODE (lhs
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (lhs
)))
1858 if (gimple_assign_single_p (stmt
)
1859 || (gimple_assign_cast_p (stmt
)
1860 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
1862 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
1863 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = idx
;
1865 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
1866 handle_pointer_plus (gsi
);
1868 else if (TREE_CODE (lhs
) != SSA_NAME
&& !TREE_SIDE_EFFECTS (lhs
))
1870 tree type
= TREE_TYPE (lhs
);
1871 if (TREE_CODE (type
) == ARRAY_TYPE
)
1872 type
= TREE_TYPE (type
);
1873 if (TREE_CODE (type
) == INTEGER_TYPE
1874 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
1875 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
))
1877 if (! handle_char_store (gsi
))
1883 if (gimple_vdef (stmt
))
1884 maybe_invalidate (stmt
);
1888 /* Recursively call maybe_invalidate on stmts that might be executed
1889 in between dombb and current bb and that contain a vdef. Stop when
1890 *count stmts are inspected, or if the whole strinfo vector has
1891 been invalidated. */
1894 do_invalidate (basic_block dombb
, gimple phi
, bitmap visited
, int *count
)
1896 unsigned int i
, n
= gimple_phi_num_args (phi
);
1898 for (i
= 0; i
< n
; i
++)
1900 tree vuse
= gimple_phi_arg_def (phi
, i
);
1901 gimple stmt
= SSA_NAME_DEF_STMT (vuse
);
1902 basic_block bb
= gimple_bb (stmt
);
1905 || !bitmap_set_bit (visited
, bb
->index
)
1906 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
1910 if (gimple_code (stmt
) == GIMPLE_PHI
)
1912 do_invalidate (dombb
, stmt
, visited
, count
);
1919 if (!maybe_invalidate (stmt
))
1924 vuse
= gimple_vuse (stmt
);
1925 stmt
= SSA_NAME_DEF_STMT (vuse
);
1926 if (gimple_bb (stmt
) != bb
)
1928 bb
= gimple_bb (stmt
);
1931 || !bitmap_set_bit (visited
, bb
->index
)
1932 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
1939 class strlen_dom_walker
: public dom_walker
1942 strlen_dom_walker (cdi_direction direction
) : dom_walker (direction
) {}
1944 virtual void before_dom_children (basic_block
);
1945 virtual void after_dom_children (basic_block
);
1948 /* Callback for walk_dominator_tree. Attempt to optimize various
1949 string ops by remembering string lenths pointed by pointer SSA_NAMEs. */
1952 strlen_dom_walker::before_dom_children (basic_block bb
)
1954 gimple_stmt_iterator gsi
;
1955 basic_block dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1958 stridx_to_strinfo
= NULL
;
1961 stridx_to_strinfo
= ((vec
<strinfo
, va_heap
, vl_embed
> *) dombb
->aux
);
1962 if (stridx_to_strinfo
)
1964 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1966 gimple phi
= gsi_stmt (gsi
);
1967 if (virtual_operand_p (gimple_phi_result (phi
)))
1969 bitmap visited
= BITMAP_ALLOC (NULL
);
1970 int count_vdef
= 100;
1971 do_invalidate (dombb
, phi
, visited
, &count_vdef
);
1972 BITMAP_FREE (visited
);
1973 if (count_vdef
== 0)
1975 /* If there were too many vdefs in between immediate
1976 dominator and current bb, invalidate everything.
1977 If stridx_to_strinfo has been unshared, we need
1978 to free it, otherwise just set it to NULL. */
1979 if (!strinfo_shared ())
1985 vec_safe_iterate (stridx_to_strinfo
, i
, &si
);
1989 (*stridx_to_strinfo
)[i
] = NULL
;
1993 stridx_to_strinfo
= NULL
;
2001 /* If all PHI arguments have the same string index, the PHI result
2003 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2005 gimple phi
= gsi_stmt (gsi
);
2006 tree result
= gimple_phi_result (phi
);
2007 if (!virtual_operand_p (result
) && POINTER_TYPE_P (TREE_TYPE (result
)))
2009 int idx
= get_stridx (gimple_phi_arg_def (phi
, 0));
2012 unsigned int i
, n
= gimple_phi_num_args (phi
);
2013 for (i
= 1; i
< n
; i
++)
2014 if (idx
!= get_stridx (gimple_phi_arg_def (phi
, i
)))
2017 ssa_ver_to_stridx
[SSA_NAME_VERSION (result
)] = idx
;
2022 /* Attempt to optimize individual statements. */
2023 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2024 if (strlen_optimize_stmt (&gsi
))
2027 bb
->aux
= stridx_to_strinfo
;
2028 if (vec_safe_length (stridx_to_strinfo
) && !strinfo_shared ())
2029 (*stridx_to_strinfo
)[0] = (strinfo
) bb
;
2032 /* Callback for walk_dominator_tree. Free strinfo vector if it is
2033 owned by the current bb, clear bb->aux. */
2036 strlen_dom_walker::after_dom_children (basic_block bb
)
2040 stridx_to_strinfo
= ((vec
<strinfo
, va_heap
, vl_embed
> *) bb
->aux
);
2041 if (vec_safe_length (stridx_to_strinfo
)
2042 && (*stridx_to_strinfo
)[0] == (strinfo
) bb
)
2047 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
2049 vec_free (stridx_to_strinfo
);
2055 /* Main entry point. */
2058 tree_ssa_strlen (void)
2060 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
2062 strinfo_pool
= create_alloc_pool ("strinfo_struct pool",
2063 sizeof (struct strinfo_struct
), 64);
2065 calculate_dominance_info (CDI_DOMINATORS
);
2067 /* String length optimization is implemented as a walk of the dominator
2068 tree and a forward walk of statements within each block. */
2069 strlen_dom_walker (CDI_DOMINATORS
).walk (cfun
->cfg
->x_entry_block_ptr
);
2071 ssa_ver_to_stridx
.release ();
2072 free_alloc_pool (strinfo_pool
);
2073 if (decl_to_stridxlist_htab
.is_created ())
2075 obstack_free (&stridx_obstack
, NULL
);
2076 decl_to_stridxlist_htab
.dispose ();
2078 laststmt
.stmt
= NULL
;
2079 laststmt
.len
= NULL_TREE
;
2080 laststmt
.stridx
= 0;
2088 return flag_optimize_strlen
!= 0;
2093 const pass_data pass_data_strlen
=
2095 GIMPLE_PASS
, /* type */
2096 "strlen", /* name */
2097 OPTGROUP_NONE
, /* optinfo_flags */
2098 true, /* has_gate */
2099 true, /* has_execute */
2100 TV_TREE_STRLEN
, /* tv_id */
2101 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2102 0, /* properties_provided */
2103 0, /* properties_destroyed */
2104 0, /* todo_flags_start */
2105 TODO_verify_ssa
, /* todo_flags_finish */
2108 class pass_strlen
: public gimple_opt_pass
2111 pass_strlen (gcc::context
*ctxt
)
2112 : gimple_opt_pass (pass_data_strlen
, ctxt
)
2115 /* opt_pass methods: */
2116 bool gate () { return gate_strlen (); }
2117 unsigned int execute () { return tree_ssa_strlen (); }
2119 }; // class pass_strlen
2124 make_pass_strlen (gcc::context
*ctxt
)
2126 return new pass_strlen (ctxt
);