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"
28 #include "gimple-ssa.h"
29 #include "tree-phinodes.h"
30 #include "ssa-iterators.h"
31 #include "tree-ssanames.h"
33 #include "tree-pass.h"
35 #include "alloc-pool.h"
36 #include "tree-ssa-propagate.h"
37 #include "gimple-pretty-print.h"
41 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
42 is an index into strinfo vector, negative value stands for
43 string length of a string literal (~strlen). */
44 static vec
<int> ssa_ver_to_stridx
;
46 /* Number of currently active string indexes plus one. */
47 static int max_stridx
;
49 /* String information record. */
50 typedef struct strinfo_struct
52 /* String length of this string. */
54 /* Any of the corresponding pointers for querying alias oracle. */
56 /* Statement for delayed length computation. */
58 /* Pointer to '\0' if known, if NULL, it can be computed as
61 /* Reference count. Any changes to strinfo entry possibly shared
62 with dominating basic blocks need unshare_strinfo first, except
63 for dont_invalidate which affects only the immediately next
66 /* Copy of index. get_strinfo (si->idx) should return si; */
68 /* These 3 fields are for chaining related string pointers together.
70 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
71 strcpy (c, d); e = c + dl;
72 strinfo(a) -> strinfo(c) -> strinfo(e)
73 All have ->first field equal to strinfo(a)->idx and are doubly
74 chained through prev/next fields. The later strinfos are required
75 to point into the same string with zero or more bytes after
76 the previous pointer and all bytes in between the two pointers
77 must be non-zero. Functions like strcpy or memcpy are supposed
78 to adjust all previous strinfo lengths, but not following strinfo
79 lengths (those are uncertain, usually invalidated during
80 maybe_invalidate, except when the alias oracle knows better).
81 Functions like strcat on the other side adjust the whole
82 related strinfo chain.
83 They are updated lazily, so to use the chain the same first fields
84 and si->prev->next == si->idx needs to be verified. */
88 /* A flag whether the string is known to be written in the current
91 /* A flag for the next maybe_invalidate that this strinfo shouldn't
92 be invalidated. Always cleared by maybe_invalidate. */
96 /* Pool for allocating strinfo_struct entries. */
97 static alloc_pool strinfo_pool
;
99 /* Vector mapping positive string indexes to strinfo, for the
100 current basic block. The first pointer in the vector is special,
101 it is either NULL, meaning the vector isn't shared, or it is
102 a basic block pointer to the owner basic_block if shared.
103 If some other bb wants to modify the vector, the vector needs
104 to be unshared first, and only the owner bb is supposed to free it. */
105 static vec
<strinfo
, va_heap
, vl_embed
> *stridx_to_strinfo
;
107 /* One OFFSET->IDX mapping. */
110 struct stridxlist
*next
;
111 HOST_WIDE_INT offset
;
115 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
116 struct decl_stridxlist_map
118 struct tree_map_base base
;
119 struct stridxlist list
;
122 /* stridxlist hashtable helpers. */
124 struct stridxlist_hasher
: typed_noop_remove
<decl_stridxlist_map
>
126 typedef decl_stridxlist_map value_type
;
127 typedef decl_stridxlist_map compare_type
;
128 static inline hashval_t
hash (const value_type
*);
129 static inline bool equal (const value_type
*, const compare_type
*);
132 /* Hash a from tree in a decl_stridxlist_map. */
135 stridxlist_hasher::hash (const value_type
*item
)
137 return DECL_UID (item
->base
.from
);
141 stridxlist_hasher::equal (const value_type
*v
, const compare_type
*c
)
143 return tree_map_base_eq (&v
->base
, &c
->base
);
146 /* Hash table for mapping decls to a chained list of offset -> idx
148 static hash_table
<stridxlist_hasher
> decl_to_stridxlist_htab
;
150 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
151 static struct obstack stridx_obstack
;
153 /* Last memcpy statement if it could be adjusted if the trailing
154 '\0' written is immediately overwritten, or
155 *x = '\0' store that could be removed if it is immediately overwritten. */
156 struct laststmt_struct
163 /* Helper function for get_stridx. */
166 get_addr_stridx (tree exp
)
169 struct decl_stridxlist_map ent
, *e
;
170 struct stridxlist
*list
;
173 if (!decl_to_stridxlist_htab
.is_created ())
176 base
= get_addr_base_and_unit_offset (exp
, &off
);
177 if (base
== NULL
|| !DECL_P (base
))
180 ent
.base
.from
= base
;
181 e
= decl_to_stridxlist_htab
.find_with_hash (&ent
, DECL_UID (base
));
188 if (list
->offset
== off
)
196 /* Return string index for EXP. */
199 get_stridx (tree exp
)
203 if (TREE_CODE (exp
) == SSA_NAME
)
204 return ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)];
206 if (TREE_CODE (exp
) == ADDR_EXPR
)
208 int idx
= get_addr_stridx (TREE_OPERAND (exp
, 0));
213 s
= string_constant (exp
, &o
);
215 && (o
== NULL_TREE
|| host_integerp (o
, 0))
216 && TREE_STRING_LENGTH (s
) > 0)
218 HOST_WIDE_INT offset
= o
? tree_low_cst (o
, 0) : 0;
219 const char *p
= TREE_STRING_POINTER (s
);
220 int max
= TREE_STRING_LENGTH (s
) - 1;
222 if (p
[max
] == '\0' && offset
>= 0 && offset
<= max
)
223 return ~(int) strlen (p
+ offset
);
228 /* Return true if strinfo vector is shared with the immediate dominator. */
231 strinfo_shared (void)
233 return vec_safe_length (stridx_to_strinfo
)
234 && (*stridx_to_strinfo
)[0] != NULL
;
237 /* Unshare strinfo vector that is shared with the immediate dominator. */
240 unshare_strinfo_vec (void)
245 gcc_assert (strinfo_shared ());
246 stridx_to_strinfo
= vec_safe_copy (stridx_to_strinfo
);
247 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
250 (*stridx_to_strinfo
)[0] = NULL
;
253 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
254 Return a pointer to the location where the string index can
255 be stored (if 0) or is stored, or NULL if this can't be tracked. */
258 addr_stridxptr (tree exp
)
260 decl_stridxlist_map
**slot
;
261 struct decl_stridxlist_map ent
;
262 struct stridxlist
*list
;
265 tree base
= get_addr_base_and_unit_offset (exp
, &off
);
266 if (base
== NULL_TREE
|| !DECL_P (base
))
269 if (!decl_to_stridxlist_htab
.is_created ())
271 decl_to_stridxlist_htab
.create (64);
272 gcc_obstack_init (&stridx_obstack
);
274 ent
.base
.from
= base
;
275 slot
= decl_to_stridxlist_htab
.find_slot_with_hash (&ent
, DECL_UID (base
),
280 list
= &(*slot
)->list
;
281 for (i
= 0; i
< 16; i
++)
283 if (list
->offset
== off
)
285 if (list
->next
== NULL
)
290 list
->next
= XOBNEW (&stridx_obstack
, struct stridxlist
);
295 struct decl_stridxlist_map
*e
296 = XOBNEW (&stridx_obstack
, struct decl_stridxlist_map
);
307 /* Create a new string index, or return 0 if reached limit. */
310 new_stridx (tree exp
)
313 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
315 if (TREE_CODE (exp
) == SSA_NAME
)
317 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
))
320 ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)] = idx
;
323 if (TREE_CODE (exp
) == ADDR_EXPR
)
325 int *pidx
= addr_stridxptr (TREE_OPERAND (exp
, 0));
328 gcc_assert (*pidx
== 0);
329 *pidx
= max_stridx
++;
336 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
339 new_addr_stridx (tree exp
)
342 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
344 pidx
= addr_stridxptr (exp
);
347 gcc_assert (*pidx
== 0);
348 *pidx
= max_stridx
++;
354 /* Create a new strinfo. */
357 new_strinfo (tree ptr
, int idx
, tree length
)
359 strinfo si
= (strinfo
) pool_alloc (strinfo_pool
);
363 si
->endptr
= NULL_TREE
;
369 si
->writable
= false;
370 si
->dont_invalidate
= false;
374 /* Decrease strinfo refcount and free it if not referenced anymore. */
377 free_strinfo (strinfo si
)
379 if (si
&& --si
->refcount
== 0)
380 pool_free (strinfo_pool
, si
);
383 /* Return strinfo vector entry IDX. */
385 static inline strinfo
386 get_strinfo (int idx
)
388 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
390 return (*stridx_to_strinfo
)[idx
];
393 /* Set strinfo in the vector entry IDX to SI. */
396 set_strinfo (int idx
, strinfo si
)
398 if (vec_safe_length (stridx_to_strinfo
) && (*stridx_to_strinfo
)[0])
399 unshare_strinfo_vec ();
400 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
401 vec_safe_grow_cleared (stridx_to_strinfo
, idx
+ 1);
402 (*stridx_to_strinfo
)[idx
] = si
;
405 /* Return string length, or NULL if it can't be computed. */
408 get_string_length (strinfo si
)
415 gimple stmt
= si
->stmt
, lenstmt
;
416 tree callee
, lhs
, fn
, tem
;
418 gimple_stmt_iterator gsi
;
420 gcc_assert (is_gimple_call (stmt
));
421 callee
= gimple_call_fndecl (stmt
);
422 gcc_assert (callee
&& DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
);
423 lhs
= gimple_call_lhs (stmt
);
424 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY
));
425 /* unshare_strinfo is intentionally not called here. The (delayed)
426 transformation of strcpy or strcat into stpcpy is done at the place
427 of the former strcpy/strcat call and so can affect all the strinfos
428 with the same stmt. If they were unshared before and transformation
429 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
430 just compute the right length. */
431 switch (DECL_FUNCTION_CODE (callee
))
433 case BUILT_IN_STRCAT
:
434 case BUILT_IN_STRCAT_CHK
:
435 gsi
= gsi_for_stmt (stmt
);
436 fn
= builtin_decl_implicit (BUILT_IN_STRLEN
);
437 gcc_assert (lhs
== NULL_TREE
);
438 tem
= unshare_expr (gimple_call_arg (stmt
, 0));
439 lenstmt
= gimple_build_call (fn
, 1, tem
);
440 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), lenstmt
);
441 gimple_call_set_lhs (lenstmt
, lhs
);
442 gimple_set_vuse (lenstmt
, gimple_vuse (stmt
));
443 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
444 tem
= gimple_call_arg (stmt
, 0);
445 if (!ptrofftype_p (TREE_TYPE (lhs
)))
447 lhs
= convert_to_ptrofftype (lhs
);
448 lhs
= force_gimple_operand_gsi (&gsi
, lhs
, true, NULL_TREE
,
449 true, GSI_SAME_STMT
);
452 = gimple_build_assign_with_ops
454 make_ssa_name (TREE_TYPE (gimple_call_arg (stmt
, 0)), NULL
),
456 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
457 gimple_call_set_arg (stmt
, 0, gimple_assign_lhs (lenstmt
));
460 case BUILT_IN_STRCPY
:
461 case BUILT_IN_STRCPY_CHK
:
462 if (gimple_call_num_args (stmt
) == 2)
463 fn
= builtin_decl_implicit (BUILT_IN_STPCPY
);
465 fn
= builtin_decl_explicit (BUILT_IN_STPCPY_CHK
);
466 gcc_assert (lhs
== NULL_TREE
);
467 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
469 fprintf (dump_file
, "Optimizing: ");
470 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
472 gimple_call_set_fndecl (stmt
, fn
);
473 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), stmt
);
474 gimple_call_set_lhs (stmt
, lhs
);
476 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
478 fprintf (dump_file
, "into: ");
479 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
482 case BUILT_IN_STPCPY
:
483 case BUILT_IN_STPCPY_CHK
:
484 gcc_assert (lhs
!= NULL_TREE
);
485 loc
= gimple_location (stmt
);
488 lhs
= fold_convert_loc (loc
, size_type_node
, lhs
);
489 si
->length
= fold_convert_loc (loc
, size_type_node
, si
->ptr
);
490 si
->length
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
502 /* Invalidate string length information for strings whose length
503 might change due to stores in stmt. */
506 maybe_invalidate (gimple stmt
)
510 bool nonempty
= false;
512 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
515 if (!si
->dont_invalidate
)
518 ao_ref_init_from_ptr_and_size (&r
, si
->ptr
, NULL_TREE
);
519 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
521 set_strinfo (i
, NULL
);
526 si
->dont_invalidate
= false;
532 /* Unshare strinfo record SI, if it has recount > 1 or
533 if stridx_to_strinfo vector is shared with some other
537 unshare_strinfo (strinfo si
)
541 if (si
->refcount
== 1 && !strinfo_shared ())
544 nsi
= new_strinfo (si
->ptr
, si
->idx
, si
->length
);
545 nsi
->stmt
= si
->stmt
;
546 nsi
->endptr
= si
->endptr
;
547 nsi
->first
= si
->first
;
548 nsi
->prev
= si
->prev
;
549 nsi
->next
= si
->next
;
550 nsi
->writable
= si
->writable
;
551 set_strinfo (si
->idx
, nsi
);
556 /* Return first strinfo in the related strinfo chain
557 if all strinfos in between belong to the chain, otherwise
561 verify_related_strinfos (strinfo origsi
)
563 strinfo si
= origsi
, psi
;
565 if (origsi
->first
== 0)
567 for (; si
->prev
; si
= psi
)
569 if (si
->first
!= origsi
->first
)
571 psi
= get_strinfo (si
->prev
);
574 if (psi
->next
!= si
->idx
)
577 if (si
->idx
!= si
->first
)
582 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
583 to a zero-length string and if possible chain it to a related strinfo
584 chain whose part is or might be CHAINSI. */
587 zero_length_string (tree ptr
, strinfo chainsi
)
591 gcc_checking_assert (TREE_CODE (ptr
) == SSA_NAME
592 && get_stridx (ptr
) == 0);
594 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
598 si
= verify_related_strinfos (chainsi
);
602 for (; chainsi
->next
; chainsi
= si
)
604 if (chainsi
->endptr
== NULL_TREE
)
606 chainsi
= unshare_strinfo (chainsi
);
607 chainsi
->endptr
= ptr
;
609 si
= get_strinfo (chainsi
->next
);
611 || si
->first
!= chainsi
->first
612 || si
->prev
!= chainsi
->idx
)
615 gcc_assert (chainsi
->length
|| chainsi
->stmt
);
616 if (chainsi
->endptr
== NULL_TREE
)
618 chainsi
= unshare_strinfo (chainsi
);
619 chainsi
->endptr
= ptr
;
621 if (chainsi
->length
&& integer_zerop (chainsi
->length
))
625 chainsi
= unshare_strinfo (chainsi
);
628 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = chainsi
->idx
;
632 else if (chainsi
->first
|| chainsi
->prev
|| chainsi
->next
)
634 chainsi
= unshare_strinfo (chainsi
);
640 idx
= new_stridx (ptr
);
643 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, 0));
644 set_strinfo (idx
, si
);
648 chainsi
= unshare_strinfo (chainsi
);
649 if (chainsi
->first
== 0)
650 chainsi
->first
= chainsi
->idx
;
652 if (chainsi
->endptr
== NULL_TREE
)
653 chainsi
->endptr
= ptr
;
654 si
->prev
= chainsi
->idx
;
655 si
->first
= chainsi
->first
;
656 si
->writable
= chainsi
->writable
;
661 /* For strinfo ORIGSI whose length has been just updated
662 update also related strinfo lengths (add ADJ to each,
663 but don't adjust ORIGSI). */
666 adjust_related_strinfos (location_t loc
, strinfo origsi
, tree adj
)
668 strinfo si
= verify_related_strinfos (origsi
);
681 si
= unshare_strinfo (si
);
684 tem
= fold_convert_loc (loc
, TREE_TYPE (si
->length
), adj
);
685 si
->length
= fold_build2_loc (loc
, PLUS_EXPR
,
686 TREE_TYPE (si
->length
), si
->length
,
689 else if (si
->stmt
!= NULL
)
690 /* Delayed length computation is unaffected. */
695 si
->endptr
= NULL_TREE
;
696 si
->dont_invalidate
= true;
700 nsi
= get_strinfo (si
->next
);
702 || nsi
->first
!= si
->first
703 || nsi
->prev
!= si
->idx
)
709 /* Find if there are other SSA_NAME pointers equal to PTR
710 for which we don't track their string lengths yet. If so, use
714 find_equal_ptrs (tree ptr
, int idx
)
716 if (TREE_CODE (ptr
) != SSA_NAME
)
720 gimple stmt
= SSA_NAME_DEF_STMT (ptr
);
721 if (!is_gimple_assign (stmt
))
723 ptr
= gimple_assign_rhs1 (stmt
);
724 switch (gimple_assign_rhs_code (stmt
))
729 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)))
731 if (TREE_CODE (ptr
) == SSA_NAME
)
733 if (TREE_CODE (ptr
) != ADDR_EXPR
)
738 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
739 if (pidx
!= NULL
&& *pidx
== 0)
747 /* We might find an endptr created in this pass. Grow the
748 vector in that case. */
749 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
750 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
752 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] != 0)
754 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = idx
;
758 /* If the last .MEM setter statement before STMT is
759 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
760 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
761 just memcpy (x, y, strlen (y)). SI must be the zero length
765 adjust_last_stmt (strinfo si
, gimple stmt
, bool is_strcat
)
767 tree vuse
, callee
, len
;
768 struct laststmt_struct last
= laststmt
;
769 strinfo lastsi
, firstsi
;
771 laststmt
.stmt
= NULL
;
772 laststmt
.len
= NULL_TREE
;
775 if (last
.stmt
== NULL
)
778 vuse
= gimple_vuse (stmt
);
779 if (vuse
== NULL_TREE
780 || SSA_NAME_DEF_STMT (vuse
) != last
.stmt
781 || !has_single_use (vuse
))
784 gcc_assert (last
.stridx
> 0);
785 lastsi
= get_strinfo (last
.stridx
);
791 if (lastsi
->first
== 0 || lastsi
->first
!= si
->first
)
794 firstsi
= verify_related_strinfos (si
);
797 while (firstsi
!= lastsi
)
800 if (firstsi
->next
== 0)
802 nextsi
= get_strinfo (firstsi
->next
);
804 || nextsi
->prev
!= firstsi
->idx
805 || nextsi
->first
!= si
->first
)
813 if (si
->length
== NULL_TREE
|| !integer_zerop (si
->length
))
817 if (is_gimple_assign (last
.stmt
))
819 gimple_stmt_iterator gsi
;
821 if (!integer_zerop (gimple_assign_rhs1 (last
.stmt
)))
823 if (stmt_could_throw_p (last
.stmt
))
825 gsi
= gsi_for_stmt (last
.stmt
);
826 unlink_stmt_vdef (last
.stmt
);
827 release_defs (last
.stmt
);
828 gsi_remove (&gsi
, true);
832 if (!gimple_call_builtin_p (last
.stmt
, BUILT_IN_NORMAL
))
835 callee
= gimple_call_fndecl (last
.stmt
);
836 switch (DECL_FUNCTION_CODE (callee
))
838 case BUILT_IN_MEMCPY
:
839 case BUILT_IN_MEMCPY_CHK
:
845 len
= gimple_call_arg (last
.stmt
, 2);
846 if (host_integerp (len
, 1))
848 if (!host_integerp (last
.len
, 1)
849 || integer_zerop (len
)
850 || (unsigned HOST_WIDE_INT
) tree_low_cst (len
, 1)
851 != (unsigned HOST_WIDE_INT
) tree_low_cst (last
.len
, 1) + 1)
853 /* Don't adjust the length if it is divisible by 4, it is more efficient
854 to store the extra '\0' in that case. */
855 if ((((unsigned HOST_WIDE_INT
) tree_low_cst (len
, 1)) & 3) == 0)
858 else if (TREE_CODE (len
) == SSA_NAME
)
860 gimple def_stmt
= SSA_NAME_DEF_STMT (len
);
861 if (!is_gimple_assign (def_stmt
)
862 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
863 || gimple_assign_rhs1 (def_stmt
) != last
.len
864 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
870 gimple_call_set_arg (last
.stmt
, 2, last
.len
);
871 update_stmt (last
.stmt
);
874 /* Handle a strlen call. If strlen of the argument is known, replace
875 the strlen call with the known value, otherwise remember that strlen
876 of the argument is stored in the lhs SSA_NAME. */
879 handle_builtin_strlen (gimple_stmt_iterator
*gsi
)
883 gimple stmt
= gsi_stmt (*gsi
);
884 tree lhs
= gimple_call_lhs (stmt
);
886 if (lhs
== NULL_TREE
)
889 src
= gimple_call_arg (stmt
, 0);
890 idx
= get_stridx (src
);
897 rhs
= build_int_cst (TREE_TYPE (lhs
), ~idx
);
901 si
= get_strinfo (idx
);
903 rhs
= get_string_length (si
);
905 if (rhs
!= NULL_TREE
)
907 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
909 fprintf (dump_file
, "Optimizing: ");
910 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
912 rhs
= unshare_expr (rhs
);
913 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
914 rhs
= fold_convert_loc (gimple_location (stmt
),
915 TREE_TYPE (lhs
), rhs
);
916 if (!update_call_from_tree (gsi
, rhs
))
917 gimplify_and_update_call_from_tree (gsi
, rhs
);
918 stmt
= gsi_stmt (*gsi
);
920 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
922 fprintf (dump_file
, "into: ");
923 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
926 && TREE_CODE (si
->length
) != SSA_NAME
927 && TREE_CODE (si
->length
) != INTEGER_CST
928 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
930 si
= unshare_strinfo (si
);
936 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
939 idx
= new_stridx (src
);
940 else if (get_strinfo (idx
) != NULL
)
944 strinfo si
= new_strinfo (src
, idx
, lhs
);
945 set_strinfo (idx
, si
);
946 find_equal_ptrs (src
, idx
);
950 /* Handle a strchr call. If strlen of the first argument is known, replace
951 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
952 that lhs of the call is endptr and strlen of the argument is endptr - x. */
955 handle_builtin_strchr (gimple_stmt_iterator
*gsi
)
959 gimple stmt
= gsi_stmt (*gsi
);
960 tree lhs
= gimple_call_lhs (stmt
);
962 if (lhs
== NULL_TREE
)
965 if (!integer_zerop (gimple_call_arg (stmt
, 1)))
968 src
= gimple_call_arg (stmt
, 0);
969 idx
= get_stridx (src
);
976 rhs
= build_int_cst (size_type_node
, ~idx
);
980 si
= get_strinfo (idx
);
982 rhs
= get_string_length (si
);
984 if (rhs
!= NULL_TREE
)
986 location_t loc
= gimple_location (stmt
);
988 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
990 fprintf (dump_file
, "Optimizing: ");
991 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
993 if (si
!= NULL
&& si
->endptr
!= NULL_TREE
)
995 rhs
= unshare_expr (si
->endptr
);
996 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
998 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1002 rhs
= fold_convert_loc (loc
, sizetype
, unshare_expr (rhs
));
1003 rhs
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1004 TREE_TYPE (src
), src
, rhs
);
1005 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1007 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1009 if (!update_call_from_tree (gsi
, rhs
))
1010 gimplify_and_update_call_from_tree (gsi
, rhs
);
1011 stmt
= gsi_stmt (*gsi
);
1013 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1015 fprintf (dump_file
, "into: ");
1016 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1019 && si
->endptr
== NULL_TREE
1020 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1022 si
= unshare_strinfo (si
);
1025 zero_length_string (lhs
, si
);
1029 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1031 if (TREE_CODE (src
) != SSA_NAME
|| !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src
))
1034 idx
= new_stridx (src
);
1035 else if (get_strinfo (idx
) != NULL
)
1037 zero_length_string (lhs
, NULL
);
1042 location_t loc
= gimple_location (stmt
);
1043 tree lhsu
= fold_convert_loc (loc
, size_type_node
, lhs
);
1044 tree srcu
= fold_convert_loc (loc
, size_type_node
, src
);
1045 tree length
= fold_build2_loc (loc
, MINUS_EXPR
,
1046 size_type_node
, lhsu
, srcu
);
1047 strinfo si
= new_strinfo (src
, idx
, length
);
1049 set_strinfo (idx
, si
);
1050 find_equal_ptrs (src
, idx
);
1051 zero_length_string (lhs
, si
);
1055 zero_length_string (lhs
, NULL
);
1058 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1059 If strlen of the second argument is known, strlen of the first argument
1060 is the same after this call. Furthermore, attempt to convert it to
1064 handle_builtin_strcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1067 tree src
, dst
, srclen
, len
, lhs
, args
, type
, fn
, oldlen
;
1069 gimple stmt
= gsi_stmt (*gsi
);
1070 strinfo si
, dsi
, olddsi
, zsi
;
1073 src
= gimple_call_arg (stmt
, 1);
1074 dst
= gimple_call_arg (stmt
, 0);
1075 lhs
= gimple_call_lhs (stmt
);
1076 idx
= get_stridx (src
);
1079 si
= get_strinfo (idx
);
1081 didx
= get_stridx (dst
);
1085 olddsi
= get_strinfo (didx
);
1090 adjust_last_stmt (olddsi
, stmt
, false);
1094 srclen
= get_string_length (si
);
1096 srclen
= build_int_cst (size_type_node
, ~idx
);
1098 loc
= gimple_location (stmt
);
1099 if (srclen
== NULL_TREE
)
1102 case BUILT_IN_STRCPY
:
1103 case BUILT_IN_STRCPY_CHK
:
1104 if (lhs
!= NULL_TREE
|| !builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1107 case BUILT_IN_STPCPY
:
1108 case BUILT_IN_STPCPY_CHK
:
1109 if (lhs
== NULL_TREE
)
1113 tree lhsuint
= fold_convert_loc (loc
, size_type_node
, lhs
);
1114 srclen
= fold_convert_loc (loc
, size_type_node
, dst
);
1115 srclen
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
1125 didx
= new_stridx (dst
);
1131 oldlen
= olddsi
->length
;
1132 dsi
= unshare_strinfo (olddsi
);
1133 dsi
->length
= srclen
;
1134 /* Break the chain, so adjust_related_strinfo on later pointers in
1135 the chain won't adjust this one anymore. */
1138 dsi
->endptr
= NULL_TREE
;
1142 dsi
= new_strinfo (dst
, didx
, srclen
);
1143 set_strinfo (didx
, dsi
);
1144 find_equal_ptrs (dst
, didx
);
1146 dsi
->writable
= true;
1147 dsi
->dont_invalidate
= true;
1149 if (dsi
->length
== NULL_TREE
)
1153 /* If string length of src is unknown, use delayed length
1154 computation. If string lenth of dst will be needed, it
1155 can be computed by transforming this strcpy call into
1156 stpcpy and subtracting dst from the return value. */
1158 /* Look for earlier strings whose length could be determined if
1159 this strcpy is turned into an stpcpy. */
1161 if (dsi
->prev
!= 0 && (chainsi
= verify_related_strinfos (dsi
)) != NULL
)
1163 for (; chainsi
&& chainsi
!= dsi
; chainsi
= get_strinfo (chainsi
->next
))
1165 /* When setting a stmt for delayed length computation
1166 prevent all strinfos through dsi from being
1168 chainsi
= unshare_strinfo (chainsi
);
1169 chainsi
->stmt
= stmt
;
1170 chainsi
->length
= NULL_TREE
;
1171 chainsi
->endptr
= NULL_TREE
;
1172 chainsi
->dont_invalidate
= true;
1181 tree adj
= NULL_TREE
;
1182 if (oldlen
== NULL_TREE
)
1184 else if (integer_zerop (oldlen
))
1186 else if (TREE_CODE (oldlen
) == INTEGER_CST
1187 || TREE_CODE (srclen
) == INTEGER_CST
)
1188 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1189 TREE_TYPE (srclen
), srclen
,
1190 fold_convert_loc (loc
, TREE_TYPE (srclen
),
1192 if (adj
!= NULL_TREE
)
1193 adjust_related_strinfos (loc
, dsi
, adj
);
1197 /* strcpy src may not overlap dst, so src doesn't need to be
1198 invalidated either. */
1200 si
->dont_invalidate
= true;
1206 case BUILT_IN_STRCPY
:
1207 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1209 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1211 case BUILT_IN_STRCPY_CHK
:
1212 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1214 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1216 case BUILT_IN_STPCPY
:
1217 /* This would need adjustment of the lhs (subtract one),
1218 or detection that the trailing '\0' doesn't need to be
1219 written, if it will be immediately overwritten.
1220 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1224 zsi
= zero_length_string (lhs
, dsi
);
1227 case BUILT_IN_STPCPY_CHK
:
1228 /* This would need adjustment of the lhs (subtract one),
1229 or detection that the trailing '\0' doesn't need to be
1230 written, if it will be immediately overwritten.
1231 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1235 zsi
= zero_length_string (lhs
, dsi
);
1242 zsi
->dont_invalidate
= true;
1244 if (fn
== NULL_TREE
)
1247 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1248 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1250 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1251 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
, build_int_cst (type
, 1));
1252 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1254 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1256 fprintf (dump_file
, "Optimizing: ");
1257 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1259 if (gimple_call_num_args (stmt
) == 2)
1260 success
= update_gimple_call (gsi
, fn
, 3, dst
, src
, len
);
1262 success
= update_gimple_call (gsi
, fn
, 4, dst
, src
, len
,
1263 gimple_call_arg (stmt
, 2));
1266 stmt
= gsi_stmt (*gsi
);
1268 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1270 fprintf (dump_file
, "into: ");
1271 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1273 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1274 laststmt
.stmt
= stmt
;
1275 laststmt
.len
= srclen
;
1276 laststmt
.stridx
= dsi
->idx
;
1278 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1279 fprintf (dump_file
, "not possible.\n");
1282 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
1283 If strlen of the second argument is known and length of the third argument
1284 is that plus one, strlen of the first argument is the same after this
1288 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1291 tree src
, dst
, len
, lhs
, oldlen
, newlen
;
1292 gimple stmt
= gsi_stmt (*gsi
);
1293 strinfo si
, dsi
, olddsi
;
1295 len
= gimple_call_arg (stmt
, 2);
1296 src
= gimple_call_arg (stmt
, 1);
1297 dst
= gimple_call_arg (stmt
, 0);
1298 idx
= get_stridx (src
);
1302 didx
= get_stridx (dst
);
1305 olddsi
= get_strinfo (didx
);
1310 && host_integerp (len
, 1)
1311 && !integer_zerop (len
))
1312 adjust_last_stmt (olddsi
, stmt
, false);
1318 /* Handle memcpy (x, y, l) where l is strlen (y) + 1. */
1319 si
= get_strinfo (idx
);
1320 if (si
== NULL
|| si
->length
== NULL_TREE
)
1322 if (TREE_CODE (len
) != SSA_NAME
)
1324 def_stmt
= SSA_NAME_DEF_STMT (len
);
1325 if (!is_gimple_assign (def_stmt
)
1326 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1327 || gimple_assign_rhs1 (def_stmt
) != si
->length
1328 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1334 /* Handle memcpy (x, "abcd", 5) or
1335 memcpy (x, "abc\0uvw", 7). */
1336 if (!host_integerp (len
, 1)
1337 || (unsigned HOST_WIDE_INT
) tree_low_cst (len
, 1)
1338 <= (unsigned HOST_WIDE_INT
) ~idx
)
1342 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
1343 adjust_last_stmt (olddsi
, stmt
, false);
1347 didx
= new_stridx (dst
);
1352 newlen
= si
->length
;
1354 newlen
= build_int_cst (size_type_node
, ~idx
);
1358 dsi
= unshare_strinfo (olddsi
);
1359 oldlen
= olddsi
->length
;
1360 dsi
->length
= newlen
;
1361 /* Break the chain, so adjust_related_strinfo on later pointers in
1362 the chain won't adjust this one anymore. */
1365 dsi
->endptr
= NULL_TREE
;
1369 dsi
= new_strinfo (dst
, didx
, newlen
);
1370 set_strinfo (didx
, dsi
);
1371 find_equal_ptrs (dst
, didx
);
1373 dsi
->writable
= true;
1374 dsi
->dont_invalidate
= true;
1377 tree adj
= NULL_TREE
;
1378 location_t loc
= gimple_location (stmt
);
1379 if (oldlen
== NULL_TREE
)
1381 else if (integer_zerop (oldlen
))
1383 else if (TREE_CODE (oldlen
) == INTEGER_CST
1384 || TREE_CODE (dsi
->length
) == INTEGER_CST
)
1385 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1386 TREE_TYPE (dsi
->length
), dsi
->length
,
1387 fold_convert_loc (loc
, TREE_TYPE (dsi
->length
),
1389 if (adj
!= NULL_TREE
)
1390 adjust_related_strinfos (loc
, dsi
, adj
);
1394 /* memcpy src may not overlap dst, so src doesn't need to be
1395 invalidated either. */
1397 si
->dont_invalidate
= true;
1399 lhs
= gimple_call_lhs (stmt
);
1402 case BUILT_IN_MEMCPY
:
1403 case BUILT_IN_MEMCPY_CHK
:
1404 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1405 laststmt
.stmt
= stmt
;
1406 laststmt
.len
= dsi
->length
;
1407 laststmt
.stridx
= dsi
->idx
;
1409 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1411 case BUILT_IN_MEMPCPY
:
1412 case BUILT_IN_MEMPCPY_CHK
:
1419 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
1420 If strlen of the second argument is known, strlen of the first argument
1421 is increased by the length of the second argument. Furthermore, attempt
1422 to convert it to memcpy/strcpy if the length of the first argument
1426 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1429 tree src
, dst
, srclen
, dstlen
, len
, lhs
, args
, type
, fn
, objsz
, endptr
;
1431 gimple stmt
= gsi_stmt (*gsi
);
1435 src
= gimple_call_arg (stmt
, 1);
1436 dst
= gimple_call_arg (stmt
, 0);
1437 lhs
= gimple_call_lhs (stmt
);
1439 didx
= get_stridx (dst
);
1445 dsi
= get_strinfo (didx
);
1446 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
1448 /* strcat (p, q) can be transformed into
1449 tmp = p + strlen (p); endptr = strpcpy (tmp, q);
1450 with length endptr - p if we need to compute the length
1451 later on. Don't do this transformation if we don't need
1453 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
1457 didx
= new_stridx (dst
);
1463 dsi
= new_strinfo (dst
, didx
, NULL_TREE
);
1464 set_strinfo (didx
, dsi
);
1465 find_equal_ptrs (dst
, didx
);
1469 dsi
= unshare_strinfo (dsi
);
1470 dsi
->length
= NULL_TREE
;
1472 dsi
->endptr
= NULL_TREE
;
1474 dsi
->writable
= true;
1476 dsi
->dont_invalidate
= true;
1483 idx
= get_stridx (src
);
1485 srclen
= build_int_cst (size_type_node
, ~idx
);
1488 si
= get_strinfo (idx
);
1490 srclen
= get_string_length (si
);
1493 loc
= gimple_location (stmt
);
1494 dstlen
= dsi
->length
;
1495 endptr
= dsi
->endptr
;
1497 dsi
= unshare_strinfo (dsi
);
1498 dsi
->endptr
= NULL_TREE
;
1500 dsi
->writable
= true;
1502 if (srclen
!= NULL_TREE
)
1504 dsi
->length
= fold_build2_loc (loc
, PLUS_EXPR
, TREE_TYPE (dsi
->length
),
1505 dsi
->length
, srclen
);
1506 adjust_related_strinfos (loc
, dsi
, srclen
);
1507 dsi
->dont_invalidate
= true;
1512 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1513 dsi
->dont_invalidate
= true;
1517 /* strcat src may not overlap dst, so src doesn't need to be
1518 invalidated either. */
1519 si
->dont_invalidate
= true;
1521 /* For now. Could remove the lhs from the call and add
1522 lhs = dst; afterwards. */
1530 case BUILT_IN_STRCAT
:
1531 if (srclen
!= NULL_TREE
)
1532 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1534 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
1536 case BUILT_IN_STRCAT_CHK
:
1537 if (srclen
!= NULL_TREE
)
1538 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1540 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
1541 objsz
= gimple_call_arg (stmt
, 2);
1547 if (fn
== NULL_TREE
)
1551 if (srclen
!= NULL_TREE
)
1553 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1554 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1556 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1557 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
1558 build_int_cst (type
, 1));
1559 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1563 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
1565 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1566 TREE_TYPE (dst
), unshare_expr (dst
),
1567 fold_convert_loc (loc
, sizetype
,
1568 unshare_expr (dstlen
)));
1569 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
1571 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1573 fprintf (dump_file
, "Optimizing: ");
1574 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1576 if (srclen
!= NULL_TREE
)
1577 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
1578 dst
, src
, len
, objsz
);
1580 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
1584 stmt
= gsi_stmt (*gsi
);
1586 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1588 fprintf (dump_file
, "into: ");
1589 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1591 /* If srclen == NULL, note that current string length can be
1592 computed by transforming this strcpy into stpcpy. */
1593 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
1595 adjust_last_stmt (dsi
, stmt
, true);
1596 if (srclen
!= NULL_TREE
)
1598 laststmt
.stmt
= stmt
;
1599 laststmt
.len
= srclen
;
1600 laststmt
.stridx
= dsi
->idx
;
1603 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1604 fprintf (dump_file
, "not possible.\n");
1607 /* Handle a POINTER_PLUS_EXPR statement.
1608 For p = "abcd" + 2; compute associated length, or if
1609 p = q + off is pointing to a '\0' character of a string, call
1610 zero_length_string on it. */
1613 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
1615 gimple stmt
= gsi_stmt (*gsi
);
1616 tree lhs
= gimple_assign_lhs (stmt
), off
;
1617 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
1625 tree off
= gimple_assign_rhs2 (stmt
);
1626 if (host_integerp (off
, 1)
1627 && (unsigned HOST_WIDE_INT
) tree_low_cst (off
, 1)
1628 <= (unsigned HOST_WIDE_INT
) ~idx
)
1629 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
1630 = ~(~idx
- (int) tree_low_cst (off
, 1));
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
);