1 /* String length optimization
2 Copyright (C) 2011-2014 Free Software Foundation, Inc.
3 Contributed by Jakub Jelinek <jakub@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
25 #include "stor-layout.h"
26 #include "hash-table.h"
35 #include "hard-reg-set.h"
38 #include "dominance.h"
40 #include "basic-block.h"
41 #include "tree-ssa-alias.h"
42 #include "internal-fn.h"
43 #include "gimple-fold.h"
45 #include "gimple-expr.h"
49 #include "gimple-iterator.h"
50 #include "gimplify-me.h"
51 #include "gimple-ssa.h"
52 #include "tree-phinodes.h"
53 #include "ssa-iterators.h"
54 #include "stringpool.h"
55 #include "tree-ssanames.h"
58 #include "tree-pass.h"
60 #include "alloc-pool.h"
61 #include "tree-ssa-propagate.h"
62 #include "gimple-pretty-print.h"
65 #include "plugin-api.h"
70 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
71 is an index into strinfo vector, negative value stands for
72 string length of a string literal (~strlen). */
73 static vec
<int> ssa_ver_to_stridx
;
75 /* Number of currently active string indexes plus one. */
76 static int max_stridx
;
78 /* String information record. */
79 typedef struct strinfo_struct
81 /* String length of this string. */
83 /* Any of the corresponding pointers for querying alias oracle. */
85 /* Statement for delayed length computation. */
87 /* Pointer to '\0' if known, if NULL, it can be computed as
90 /* Reference count. Any changes to strinfo entry possibly shared
91 with dominating basic blocks need unshare_strinfo first, except
92 for dont_invalidate which affects only the immediately next
95 /* Copy of index. get_strinfo (si->idx) should return si; */
97 /* These 3 fields are for chaining related string pointers together.
99 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
100 strcpy (c, d); e = c + dl;
101 strinfo(a) -> strinfo(c) -> strinfo(e)
102 All have ->first field equal to strinfo(a)->idx and are doubly
103 chained through prev/next fields. The later strinfos are required
104 to point into the same string with zero or more bytes after
105 the previous pointer and all bytes in between the two pointers
106 must be non-zero. Functions like strcpy or memcpy are supposed
107 to adjust all previous strinfo lengths, but not following strinfo
108 lengths (those are uncertain, usually invalidated during
109 maybe_invalidate, except when the alias oracle knows better).
110 Functions like strcat on the other side adjust the whole
111 related strinfo chain.
112 They are updated lazily, so to use the chain the same first fields
113 and si->prev->next == si->idx needs to be verified. */
117 /* A flag whether the string is known to be written in the current
120 /* A flag for the next maybe_invalidate that this strinfo shouldn't
121 be invalidated. Always cleared by maybe_invalidate. */
122 bool dont_invalidate
;
125 /* Pool for allocating strinfo_struct entries. */
126 static alloc_pool strinfo_pool
;
128 /* Vector mapping positive string indexes to strinfo, for the
129 current basic block. The first pointer in the vector is special,
130 it is either NULL, meaning the vector isn't shared, or it is
131 a basic block pointer to the owner basic_block if shared.
132 If some other bb wants to modify the vector, the vector needs
133 to be unshared first, and only the owner bb is supposed to free it. */
134 static vec
<strinfo
, va_heap
, vl_embed
> *stridx_to_strinfo
;
136 /* One OFFSET->IDX mapping. */
139 struct stridxlist
*next
;
140 HOST_WIDE_INT offset
;
144 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
145 struct decl_stridxlist_map
147 struct tree_map_base base
;
148 struct stridxlist list
;
151 /* stridxlist hashtable helpers. */
153 struct stridxlist_hash_traits
: default_hashmap_traits
155 static inline hashval_t
hash (tree
);
158 /* Hash a from tree in a decl_stridxlist_map. */
161 stridxlist_hash_traits::hash (tree item
)
163 return DECL_UID (item
);
166 /* Hash table for mapping decls to a chained list of offset -> idx
168 static hash_map
<tree
, stridxlist
, stridxlist_hash_traits
>
169 *decl_to_stridxlist_htab
;
171 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
172 static struct obstack stridx_obstack
;
174 /* Last memcpy statement if it could be adjusted if the trailing
175 '\0' written is immediately overwritten, or
176 *x = '\0' store that could be removed if it is immediately overwritten. */
177 struct laststmt_struct
184 /* Helper function for get_stridx. */
187 get_addr_stridx (tree exp
)
190 struct stridxlist
*list
;
193 if (!decl_to_stridxlist_htab
)
196 base
= get_addr_base_and_unit_offset (exp
, &off
);
197 if (base
== NULL
|| !DECL_P (base
))
200 list
= decl_to_stridxlist_htab
->get (base
);
206 if (list
->offset
== off
)
214 /* Return string index for EXP. */
217 get_stridx (tree exp
)
221 if (TREE_CODE (exp
) == SSA_NAME
)
222 return ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)];
224 if (TREE_CODE (exp
) == ADDR_EXPR
)
226 int idx
= get_addr_stridx (TREE_OPERAND (exp
, 0));
231 s
= string_constant (exp
, &o
);
233 && (o
== NULL_TREE
|| tree_fits_shwi_p (o
))
234 && TREE_STRING_LENGTH (s
) > 0)
236 HOST_WIDE_INT offset
= o
? tree_to_shwi (o
) : 0;
237 const char *p
= TREE_STRING_POINTER (s
);
238 int max
= TREE_STRING_LENGTH (s
) - 1;
240 if (p
[max
] == '\0' && offset
>= 0 && offset
<= max
)
241 return ~(int) strlen (p
+ offset
);
246 /* Return true if strinfo vector is shared with the immediate dominator. */
249 strinfo_shared (void)
251 return vec_safe_length (stridx_to_strinfo
)
252 && (*stridx_to_strinfo
)[0] != NULL
;
255 /* Unshare strinfo vector that is shared with the immediate dominator. */
258 unshare_strinfo_vec (void)
263 gcc_assert (strinfo_shared ());
264 stridx_to_strinfo
= vec_safe_copy (stridx_to_strinfo
);
265 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
268 (*stridx_to_strinfo
)[0] = NULL
;
271 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
272 Return a pointer to the location where the string index can
273 be stored (if 0) or is stored, or NULL if this can't be tracked. */
276 addr_stridxptr (tree exp
)
280 tree base
= get_addr_base_and_unit_offset (exp
, &off
);
281 if (base
== NULL_TREE
|| !DECL_P (base
))
284 if (!decl_to_stridxlist_htab
)
286 decl_to_stridxlist_htab
287 = new hash_map
<tree
, stridxlist
, stridxlist_hash_traits
> (64);
288 gcc_obstack_init (&stridx_obstack
);
292 stridxlist
*list
= &decl_to_stridxlist_htab
->get_or_insert (base
, &existed
);
296 for (i
= 0; i
< 16; i
++)
298 if (list
->offset
== off
)
300 if (list
->next
== NULL
)
305 list
->next
= XOBNEW (&stridx_obstack
, struct stridxlist
);
315 /* Create a new string index, or return 0 if reached limit. */
318 new_stridx (tree exp
)
321 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
323 if (TREE_CODE (exp
) == SSA_NAME
)
325 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
))
328 ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)] = idx
;
331 if (TREE_CODE (exp
) == ADDR_EXPR
)
333 int *pidx
= addr_stridxptr (TREE_OPERAND (exp
, 0));
336 gcc_assert (*pidx
== 0);
337 *pidx
= max_stridx
++;
344 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
347 new_addr_stridx (tree exp
)
350 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
352 pidx
= addr_stridxptr (exp
);
355 gcc_assert (*pidx
== 0);
356 *pidx
= max_stridx
++;
362 /* Create a new strinfo. */
365 new_strinfo (tree ptr
, int idx
, tree length
)
367 strinfo si
= (strinfo
) pool_alloc (strinfo_pool
);
371 si
->endptr
= NULL_TREE
;
377 si
->writable
= false;
378 si
->dont_invalidate
= false;
382 /* Decrease strinfo refcount and free it if not referenced anymore. */
385 free_strinfo (strinfo si
)
387 if (si
&& --si
->refcount
== 0)
388 pool_free (strinfo_pool
, si
);
391 /* Return strinfo vector entry IDX. */
393 static inline strinfo
394 get_strinfo (int idx
)
396 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
398 return (*stridx_to_strinfo
)[idx
];
401 /* Set strinfo in the vector entry IDX to SI. */
404 set_strinfo (int idx
, strinfo si
)
406 if (vec_safe_length (stridx_to_strinfo
) && (*stridx_to_strinfo
)[0])
407 unshare_strinfo_vec ();
408 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
409 vec_safe_grow_cleared (stridx_to_strinfo
, idx
+ 1);
410 (*stridx_to_strinfo
)[idx
] = si
;
413 /* Return string length, or NULL if it can't be computed. */
416 get_string_length (strinfo si
)
423 gimple stmt
= si
->stmt
, lenstmt
;
424 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
425 tree callee
, lhs
, fn
, tem
;
427 gimple_stmt_iterator gsi
;
429 gcc_assert (is_gimple_call (stmt
));
430 callee
= gimple_call_fndecl (stmt
);
431 gcc_assert (callee
&& DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
);
432 lhs
= gimple_call_lhs (stmt
);
433 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY
));
434 /* unshare_strinfo is intentionally not called here. The (delayed)
435 transformation of strcpy or strcat into stpcpy is done at the place
436 of the former strcpy/strcat call and so can affect all the strinfos
437 with the same stmt. If they were unshared before and transformation
438 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
439 just compute the right length. */
440 switch (DECL_FUNCTION_CODE (callee
))
442 case BUILT_IN_STRCAT
:
443 case BUILT_IN_STRCAT_CHK
:
444 case BUILT_IN_STRCAT_CHKP
:
445 case BUILT_IN_STRCAT_CHK_CHKP
:
446 gsi
= gsi_for_stmt (stmt
);
447 fn
= builtin_decl_implicit (BUILT_IN_STRLEN
);
448 gcc_assert (lhs
== NULL_TREE
);
449 tem
= unshare_expr (gimple_call_arg (stmt
, 0));
452 lenstmt
= gimple_build_call (chkp_maybe_create_clone (fn
)->decl
,
453 2, tem
, gimple_call_arg (stmt
, 1));
454 gimple_call_set_with_bounds (lenstmt
, true);
457 lenstmt
= gimple_build_call (fn
, 1, tem
);
458 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), lenstmt
);
459 gimple_call_set_lhs (lenstmt
, lhs
);
460 gimple_set_vuse (lenstmt
, gimple_vuse (stmt
));
461 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
462 tem
= gimple_call_arg (stmt
, 0);
463 if (!ptrofftype_p (TREE_TYPE (lhs
)))
465 lhs
= convert_to_ptrofftype (lhs
);
466 lhs
= force_gimple_operand_gsi (&gsi
, lhs
, true, NULL_TREE
,
467 true, GSI_SAME_STMT
);
470 = gimple_build_assign_with_ops
472 make_ssa_name (TREE_TYPE (gimple_call_arg (stmt
, 0)), NULL
),
474 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
475 gimple_call_set_arg (stmt
, 0, gimple_assign_lhs (lenstmt
));
478 case BUILT_IN_STRCPY
:
479 case BUILT_IN_STRCPY_CHK
:
480 case BUILT_IN_STRCPY_CHKP
:
481 case BUILT_IN_STRCPY_CHK_CHKP
:
482 if (gimple_call_num_args (stmt
) == (with_bounds
? 4 : 2))
483 fn
= builtin_decl_implicit (BUILT_IN_STPCPY
);
485 fn
= builtin_decl_explicit (BUILT_IN_STPCPY_CHK
);
487 fn
= chkp_maybe_create_clone (fn
)->decl
;
488 gcc_assert (lhs
== NULL_TREE
);
489 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
491 fprintf (dump_file
, "Optimizing: ");
492 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
494 gimple_call_set_fndecl (stmt
, fn
);
495 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), stmt
);
496 gimple_call_set_lhs (stmt
, lhs
);
498 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
500 fprintf (dump_file
, "into: ");
501 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
504 case BUILT_IN_STPCPY
:
505 case BUILT_IN_STPCPY_CHK
:
506 case BUILT_IN_STPCPY_CHKP
:
507 case BUILT_IN_STPCPY_CHK_CHKP
:
508 gcc_assert (lhs
!= NULL_TREE
);
509 loc
= gimple_location (stmt
);
512 lhs
= fold_convert_loc (loc
, size_type_node
, lhs
);
513 si
->length
= fold_convert_loc (loc
, size_type_node
, si
->ptr
);
514 si
->length
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
517 case BUILT_IN_MALLOC
:
519 /* BUILT_IN_CALLOC always has si->length set. */
529 /* Invalidate string length information for strings whose length
530 might change due to stores in stmt. */
533 maybe_invalidate (gimple stmt
)
537 bool nonempty
= false;
539 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
542 if (!si
->dont_invalidate
)
545 /* Do not use si->length. */
546 ao_ref_init_from_ptr_and_size (&r
, si
->ptr
, NULL_TREE
);
547 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
549 set_strinfo (i
, NULL
);
554 si
->dont_invalidate
= false;
560 /* Unshare strinfo record SI, if it has recount > 1 or
561 if stridx_to_strinfo vector is shared with some other
565 unshare_strinfo (strinfo si
)
569 if (si
->refcount
== 1 && !strinfo_shared ())
572 nsi
= new_strinfo (si
->ptr
, si
->idx
, si
->length
);
573 nsi
->stmt
= si
->stmt
;
574 nsi
->endptr
= si
->endptr
;
575 nsi
->first
= si
->first
;
576 nsi
->prev
= si
->prev
;
577 nsi
->next
= si
->next
;
578 nsi
->writable
= si
->writable
;
579 set_strinfo (si
->idx
, nsi
);
584 /* Return first strinfo in the related strinfo chain
585 if all strinfos in between belong to the chain, otherwise
589 verify_related_strinfos (strinfo origsi
)
591 strinfo si
= origsi
, psi
;
593 if (origsi
->first
== 0)
595 for (; si
->prev
; si
= psi
)
597 if (si
->first
!= origsi
->first
)
599 psi
= get_strinfo (si
->prev
);
602 if (psi
->next
!= si
->idx
)
605 if (si
->idx
!= si
->first
)
610 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
611 to a zero-length string and if possible chain it to a related strinfo
612 chain whose part is or might be CHAINSI. */
615 zero_length_string (tree ptr
, strinfo chainsi
)
619 gcc_checking_assert (TREE_CODE (ptr
) == SSA_NAME
620 && get_stridx (ptr
) == 0);
622 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
626 si
= verify_related_strinfos (chainsi
);
630 for (; chainsi
->next
; chainsi
= si
)
632 if (chainsi
->endptr
== NULL_TREE
)
634 chainsi
= unshare_strinfo (chainsi
);
635 chainsi
->endptr
= ptr
;
637 si
= get_strinfo (chainsi
->next
);
639 || si
->first
!= chainsi
->first
640 || si
->prev
!= chainsi
->idx
)
643 gcc_assert (chainsi
->length
|| chainsi
->stmt
);
644 if (chainsi
->endptr
== NULL_TREE
)
646 chainsi
= unshare_strinfo (chainsi
);
647 chainsi
->endptr
= ptr
;
649 if (chainsi
->length
&& integer_zerop (chainsi
->length
))
653 chainsi
= unshare_strinfo (chainsi
);
656 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = chainsi
->idx
;
660 else if (chainsi
->first
|| chainsi
->prev
|| chainsi
->next
)
662 chainsi
= unshare_strinfo (chainsi
);
668 idx
= new_stridx (ptr
);
671 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, 0));
672 set_strinfo (idx
, si
);
676 chainsi
= unshare_strinfo (chainsi
);
677 if (chainsi
->first
== 0)
678 chainsi
->first
= chainsi
->idx
;
680 if (chainsi
->endptr
== NULL_TREE
)
681 chainsi
->endptr
= ptr
;
682 si
->prev
= chainsi
->idx
;
683 si
->first
= chainsi
->first
;
684 si
->writable
= chainsi
->writable
;
689 /* For strinfo ORIGSI whose length has been just updated
690 update also related strinfo lengths (add ADJ to each,
691 but don't adjust ORIGSI). */
694 adjust_related_strinfos (location_t loc
, strinfo origsi
, tree adj
)
696 strinfo si
= verify_related_strinfos (origsi
);
709 si
= unshare_strinfo (si
);
712 tem
= fold_convert_loc (loc
, TREE_TYPE (si
->length
), adj
);
713 si
->length
= fold_build2_loc (loc
, PLUS_EXPR
,
714 TREE_TYPE (si
->length
), si
->length
,
717 else if (si
->stmt
!= NULL
)
718 /* Delayed length computation is unaffected. */
723 si
->endptr
= NULL_TREE
;
724 si
->dont_invalidate
= true;
728 nsi
= get_strinfo (si
->next
);
730 || nsi
->first
!= si
->first
731 || nsi
->prev
!= si
->idx
)
737 /* Find if there are other SSA_NAME pointers equal to PTR
738 for which we don't track their string lengths yet. If so, use
742 find_equal_ptrs (tree ptr
, int idx
)
744 if (TREE_CODE (ptr
) != SSA_NAME
)
748 gimple stmt
= SSA_NAME_DEF_STMT (ptr
);
749 if (!is_gimple_assign (stmt
))
751 ptr
= gimple_assign_rhs1 (stmt
);
752 switch (gimple_assign_rhs_code (stmt
))
757 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)))
759 if (TREE_CODE (ptr
) == SSA_NAME
)
761 if (TREE_CODE (ptr
) != ADDR_EXPR
)
766 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
767 if (pidx
!= NULL
&& *pidx
== 0)
775 /* We might find an endptr created in this pass. Grow the
776 vector in that case. */
777 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
778 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
780 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] != 0)
782 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = idx
;
786 /* If the last .MEM setter statement before STMT is
787 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
788 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
789 just memcpy (x, y, strlen (y)). SI must be the zero length
793 adjust_last_stmt (strinfo si
, gimple stmt
, bool is_strcat
)
795 tree vuse
, callee
, len
;
796 struct laststmt_struct last
= laststmt
;
797 strinfo lastsi
, firstsi
;
798 unsigned len_arg_no
= 2;
800 laststmt
.stmt
= NULL
;
801 laststmt
.len
= NULL_TREE
;
804 if (last
.stmt
== NULL
)
807 vuse
= gimple_vuse (stmt
);
808 if (vuse
== NULL_TREE
809 || SSA_NAME_DEF_STMT (vuse
) != last
.stmt
810 || !has_single_use (vuse
))
813 gcc_assert (last
.stridx
> 0);
814 lastsi
= get_strinfo (last
.stridx
);
820 if (lastsi
->first
== 0 || lastsi
->first
!= si
->first
)
823 firstsi
= verify_related_strinfos (si
);
826 while (firstsi
!= lastsi
)
829 if (firstsi
->next
== 0)
831 nextsi
= get_strinfo (firstsi
->next
);
833 || nextsi
->prev
!= firstsi
->idx
834 || nextsi
->first
!= si
->first
)
842 if (si
->length
== NULL_TREE
|| !integer_zerop (si
->length
))
846 if (is_gimple_assign (last
.stmt
))
848 gimple_stmt_iterator gsi
;
850 if (!integer_zerop (gimple_assign_rhs1 (last
.stmt
)))
852 if (stmt_could_throw_p (last
.stmt
))
854 gsi
= gsi_for_stmt (last
.stmt
);
855 unlink_stmt_vdef (last
.stmt
);
856 release_defs (last
.stmt
);
857 gsi_remove (&gsi
, true);
861 if (!gimple_call_builtin_p (last
.stmt
, BUILT_IN_NORMAL
))
864 callee
= gimple_call_fndecl (last
.stmt
);
865 switch (DECL_FUNCTION_CODE (callee
))
867 case BUILT_IN_MEMCPY
:
868 case BUILT_IN_MEMCPY_CHK
:
870 case BUILT_IN_MEMCPY_CHKP
:
871 case BUILT_IN_MEMCPY_CHK_CHKP
:
878 len
= gimple_call_arg (last
.stmt
, len_arg_no
);
879 if (tree_fits_uhwi_p (len
))
881 if (!tree_fits_uhwi_p (last
.len
)
882 || integer_zerop (len
)
883 || tree_to_uhwi (len
) != tree_to_uhwi (last
.len
) + 1)
885 /* Don't adjust the length if it is divisible by 4, it is more efficient
886 to store the extra '\0' in that case. */
887 if ((tree_to_uhwi (len
) & 3) == 0)
890 else if (TREE_CODE (len
) == SSA_NAME
)
892 gimple def_stmt
= SSA_NAME_DEF_STMT (len
);
893 if (!is_gimple_assign (def_stmt
)
894 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
895 || gimple_assign_rhs1 (def_stmt
) != last
.len
896 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
902 gimple_call_set_arg (last
.stmt
, len_arg_no
, last
.len
);
903 update_stmt (last
.stmt
);
906 /* Handle a strlen call. If strlen of the argument is known, replace
907 the strlen call with the known value, otherwise remember that strlen
908 of the argument is stored in the lhs SSA_NAME. */
911 handle_builtin_strlen (gimple_stmt_iterator
*gsi
)
915 gimple stmt
= gsi_stmt (*gsi
);
916 tree lhs
= gimple_call_lhs (stmt
);
918 if (lhs
== NULL_TREE
)
921 src
= gimple_call_arg (stmt
, 0);
922 idx
= get_stridx (src
);
929 rhs
= build_int_cst (TREE_TYPE (lhs
), ~idx
);
933 si
= get_strinfo (idx
);
935 rhs
= get_string_length (si
);
937 if (rhs
!= NULL_TREE
)
939 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
941 fprintf (dump_file
, "Optimizing: ");
942 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
944 rhs
= unshare_expr (rhs
);
945 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
946 rhs
= fold_convert_loc (gimple_location (stmt
),
947 TREE_TYPE (lhs
), rhs
);
948 if (!update_call_from_tree (gsi
, rhs
))
949 gimplify_and_update_call_from_tree (gsi
, rhs
);
950 stmt
= gsi_stmt (*gsi
);
952 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
954 fprintf (dump_file
, "into: ");
955 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
958 && TREE_CODE (si
->length
) != SSA_NAME
959 && TREE_CODE (si
->length
) != INTEGER_CST
960 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
962 si
= unshare_strinfo (si
);
968 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
971 idx
= new_stridx (src
);
972 else if (get_strinfo (idx
) != NULL
)
976 strinfo si
= new_strinfo (src
, idx
, lhs
);
977 set_strinfo (idx
, si
);
978 find_equal_ptrs (src
, idx
);
982 /* Handle a strchr call. If strlen of the first argument is known, replace
983 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
984 that lhs of the call is endptr and strlen of the argument is endptr - x. */
987 handle_builtin_strchr (gimple_stmt_iterator
*gsi
)
991 gimple stmt
= gsi_stmt (*gsi
);
992 tree lhs
= gimple_call_lhs (stmt
);
993 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
995 if (lhs
== NULL_TREE
)
998 if (!integer_zerop (gimple_call_arg (stmt
, with_bounds
? 2 : 1)))
1001 src
= gimple_call_arg (stmt
, 0);
1002 idx
= get_stridx (src
);
1009 rhs
= build_int_cst (size_type_node
, ~idx
);
1013 si
= get_strinfo (idx
);
1015 rhs
= get_string_length (si
);
1017 if (rhs
!= NULL_TREE
)
1019 location_t loc
= gimple_location (stmt
);
1021 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1023 fprintf (dump_file
, "Optimizing: ");
1024 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1026 if (si
!= NULL
&& si
->endptr
!= NULL_TREE
)
1028 rhs
= unshare_expr (si
->endptr
);
1029 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1031 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1035 rhs
= fold_convert_loc (loc
, sizetype
, unshare_expr (rhs
));
1036 rhs
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1037 TREE_TYPE (src
), src
, rhs
);
1038 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1040 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1042 if (!update_call_from_tree (gsi
, rhs
))
1043 gimplify_and_update_call_from_tree (gsi
, rhs
);
1044 stmt
= gsi_stmt (*gsi
);
1046 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1048 fprintf (dump_file
, "into: ");
1049 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1052 && si
->endptr
== NULL_TREE
1053 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1055 si
= unshare_strinfo (si
);
1058 zero_length_string (lhs
, si
);
1062 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1064 if (TREE_CODE (src
) != SSA_NAME
|| !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src
))
1067 idx
= new_stridx (src
);
1068 else if (get_strinfo (idx
) != NULL
)
1070 zero_length_string (lhs
, NULL
);
1075 location_t loc
= gimple_location (stmt
);
1076 tree lhsu
= fold_convert_loc (loc
, size_type_node
, lhs
);
1077 tree srcu
= fold_convert_loc (loc
, size_type_node
, src
);
1078 tree length
= fold_build2_loc (loc
, MINUS_EXPR
,
1079 size_type_node
, lhsu
, srcu
);
1080 strinfo si
= new_strinfo (src
, idx
, length
);
1082 set_strinfo (idx
, si
);
1083 find_equal_ptrs (src
, idx
);
1084 zero_length_string (lhs
, si
);
1088 zero_length_string (lhs
, NULL
);
1091 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1092 If strlen of the second argument is known, strlen of the first argument
1093 is the same after this call. Furthermore, attempt to convert it to
1097 handle_builtin_strcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1100 tree src
, dst
, srclen
, len
, lhs
, args
, type
, fn
, oldlen
;
1102 gimple stmt
= gsi_stmt (*gsi
);
1103 strinfo si
, dsi
, olddsi
, zsi
;
1105 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1107 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
1108 dst
= gimple_call_arg (stmt
, 0);
1109 lhs
= gimple_call_lhs (stmt
);
1110 idx
= get_stridx (src
);
1113 si
= get_strinfo (idx
);
1115 didx
= get_stridx (dst
);
1119 olddsi
= get_strinfo (didx
);
1124 adjust_last_stmt (olddsi
, stmt
, false);
1128 srclen
= get_string_length (si
);
1130 srclen
= build_int_cst (size_type_node
, ~idx
);
1132 loc
= gimple_location (stmt
);
1133 if (srclen
== NULL_TREE
)
1136 case BUILT_IN_STRCPY
:
1137 case BUILT_IN_STRCPY_CHK
:
1138 case BUILT_IN_STRCPY_CHKP
:
1139 case BUILT_IN_STRCPY_CHK_CHKP
:
1140 if (lhs
!= NULL_TREE
|| !builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1143 case BUILT_IN_STPCPY
:
1144 case BUILT_IN_STPCPY_CHK
:
1145 case BUILT_IN_STPCPY_CHKP
:
1146 case BUILT_IN_STPCPY_CHK_CHKP
:
1147 if (lhs
== NULL_TREE
)
1151 tree lhsuint
= fold_convert_loc (loc
, size_type_node
, lhs
);
1152 srclen
= fold_convert_loc (loc
, size_type_node
, dst
);
1153 srclen
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
1163 didx
= new_stridx (dst
);
1169 oldlen
= olddsi
->length
;
1170 dsi
= unshare_strinfo (olddsi
);
1171 dsi
->length
= srclen
;
1172 /* Break the chain, so adjust_related_strinfo on later pointers in
1173 the chain won't adjust this one anymore. */
1176 dsi
->endptr
= NULL_TREE
;
1180 dsi
= new_strinfo (dst
, didx
, srclen
);
1181 set_strinfo (didx
, dsi
);
1182 find_equal_ptrs (dst
, didx
);
1184 dsi
->writable
= true;
1185 dsi
->dont_invalidate
= true;
1187 if (dsi
->length
== NULL_TREE
)
1191 /* If string length of src is unknown, use delayed length
1192 computation. If string lenth of dst will be needed, it
1193 can be computed by transforming this strcpy call into
1194 stpcpy and subtracting dst from the return value. */
1196 /* Look for earlier strings whose length could be determined if
1197 this strcpy is turned into an stpcpy. */
1199 if (dsi
->prev
!= 0 && (chainsi
= verify_related_strinfos (dsi
)) != NULL
)
1201 for (; chainsi
&& chainsi
!= dsi
; chainsi
= get_strinfo (chainsi
->next
))
1203 /* When setting a stmt for delayed length computation
1204 prevent all strinfos through dsi from being
1206 chainsi
= unshare_strinfo (chainsi
);
1207 chainsi
->stmt
= stmt
;
1208 chainsi
->length
= NULL_TREE
;
1209 chainsi
->endptr
= NULL_TREE
;
1210 chainsi
->dont_invalidate
= true;
1219 tree adj
= NULL_TREE
;
1220 if (oldlen
== NULL_TREE
)
1222 else if (integer_zerop (oldlen
))
1224 else if (TREE_CODE (oldlen
) == INTEGER_CST
1225 || TREE_CODE (srclen
) == INTEGER_CST
)
1226 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1227 TREE_TYPE (srclen
), srclen
,
1228 fold_convert_loc (loc
, TREE_TYPE (srclen
),
1230 if (adj
!= NULL_TREE
)
1231 adjust_related_strinfos (loc
, dsi
, adj
);
1235 /* strcpy src may not overlap dst, so src doesn't need to be
1236 invalidated either. */
1238 si
->dont_invalidate
= true;
1244 case BUILT_IN_STRCPY
:
1245 case BUILT_IN_STRCPY_CHKP
:
1246 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1248 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1250 case BUILT_IN_STRCPY_CHK
:
1251 case BUILT_IN_STRCPY_CHK_CHKP
:
1252 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1254 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1256 case BUILT_IN_STPCPY
:
1257 case BUILT_IN_STPCPY_CHKP
:
1258 /* This would need adjustment of the lhs (subtract one),
1259 or detection that the trailing '\0' doesn't need to be
1260 written, if it will be immediately overwritten.
1261 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1265 zsi
= zero_length_string (lhs
, dsi
);
1268 case BUILT_IN_STPCPY_CHK
:
1269 case BUILT_IN_STPCPY_CHK_CHKP
:
1270 /* This would need adjustment of the lhs (subtract one),
1271 or detection that the trailing '\0' doesn't need to be
1272 written, if it will be immediately overwritten.
1273 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1277 zsi
= zero_length_string (lhs
, dsi
);
1284 zsi
->dont_invalidate
= true;
1286 if (fn
== NULL_TREE
)
1289 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1290 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1292 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1293 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
, build_int_cst (type
, 1));
1294 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1296 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1298 fprintf (dump_file
, "Optimizing: ");
1299 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1303 fn
= chkp_maybe_create_clone (fn
)->decl
;
1304 if (gimple_call_num_args (stmt
) == 4)
1305 success
= update_gimple_call (gsi
, fn
, 5, dst
,
1306 gimple_call_arg (stmt
, 1),
1308 gimple_call_arg (stmt
, 3),
1311 success
= update_gimple_call (gsi
, fn
, 6, dst
,
1312 gimple_call_arg (stmt
, 1),
1314 gimple_call_arg (stmt
, 3),
1316 gimple_call_arg (stmt
, 4));
1319 if (gimple_call_num_args (stmt
) == 2)
1320 success
= update_gimple_call (gsi
, fn
, 3, dst
, src
, len
);
1322 success
= update_gimple_call (gsi
, fn
, 4, dst
, src
, len
,
1323 gimple_call_arg (stmt
, 2));
1326 stmt
= gsi_stmt (*gsi
);
1327 gimple_call_set_with_bounds (stmt
, with_bounds
);
1329 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1331 fprintf (dump_file
, "into: ");
1332 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1334 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1335 laststmt
.stmt
= stmt
;
1336 laststmt
.len
= srclen
;
1337 laststmt
.stridx
= dsi
->idx
;
1339 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1340 fprintf (dump_file
, "not possible.\n");
1343 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
1344 If strlen of the second argument is known and length of the third argument
1345 is that plus one, strlen of the first argument is the same after this
1349 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1352 tree src
, dst
, len
, lhs
, oldlen
, newlen
;
1353 gimple stmt
= gsi_stmt (*gsi
);
1354 strinfo si
, dsi
, olddsi
;
1355 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1357 len
= gimple_call_arg (stmt
, with_bounds
? 4 : 2);
1358 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
1359 dst
= gimple_call_arg (stmt
, 0);
1360 idx
= get_stridx (src
);
1364 didx
= get_stridx (dst
);
1367 olddsi
= get_strinfo (didx
);
1372 && tree_fits_uhwi_p (len
)
1373 && !integer_zerop (len
))
1374 adjust_last_stmt (olddsi
, stmt
, false);
1380 /* Handle memcpy (x, y, l) where l is strlen (y) + 1. */
1381 si
= get_strinfo (idx
);
1382 if (si
== NULL
|| si
->length
== NULL_TREE
)
1384 if (TREE_CODE (len
) != SSA_NAME
)
1386 def_stmt
= SSA_NAME_DEF_STMT (len
);
1387 if (!is_gimple_assign (def_stmt
)
1388 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1389 || gimple_assign_rhs1 (def_stmt
) != si
->length
1390 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1396 /* Handle memcpy (x, "abcd", 5) or
1397 memcpy (x, "abc\0uvw", 7). */
1398 if (!tree_fits_uhwi_p (len
)
1399 || tree_to_uhwi (len
) <= (unsigned HOST_WIDE_INT
) ~idx
)
1403 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
1404 adjust_last_stmt (olddsi
, stmt
, false);
1408 didx
= new_stridx (dst
);
1413 newlen
= si
->length
;
1415 newlen
= build_int_cst (size_type_node
, ~idx
);
1419 dsi
= unshare_strinfo (olddsi
);
1420 oldlen
= olddsi
->length
;
1421 dsi
->length
= newlen
;
1422 /* Break the chain, so adjust_related_strinfo on later pointers in
1423 the chain won't adjust this one anymore. */
1426 dsi
->endptr
= NULL_TREE
;
1430 dsi
= new_strinfo (dst
, didx
, newlen
);
1431 set_strinfo (didx
, dsi
);
1432 find_equal_ptrs (dst
, didx
);
1434 dsi
->writable
= true;
1435 dsi
->dont_invalidate
= true;
1438 tree adj
= NULL_TREE
;
1439 location_t loc
= gimple_location (stmt
);
1440 if (oldlen
== NULL_TREE
)
1442 else if (integer_zerop (oldlen
))
1444 else if (TREE_CODE (oldlen
) == INTEGER_CST
1445 || TREE_CODE (dsi
->length
) == INTEGER_CST
)
1446 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1447 TREE_TYPE (dsi
->length
), dsi
->length
,
1448 fold_convert_loc (loc
, TREE_TYPE (dsi
->length
),
1450 if (adj
!= NULL_TREE
)
1451 adjust_related_strinfos (loc
, dsi
, adj
);
1455 /* memcpy src may not overlap dst, so src doesn't need to be
1456 invalidated either. */
1458 si
->dont_invalidate
= true;
1460 lhs
= gimple_call_lhs (stmt
);
1463 case BUILT_IN_MEMCPY
:
1464 case BUILT_IN_MEMCPY_CHK
:
1465 case BUILT_IN_MEMCPY_CHKP
:
1466 case BUILT_IN_MEMCPY_CHK_CHKP
:
1467 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1468 laststmt
.stmt
= stmt
;
1469 laststmt
.len
= dsi
->length
;
1470 laststmt
.stridx
= dsi
->idx
;
1472 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1474 case BUILT_IN_MEMPCPY
:
1475 case BUILT_IN_MEMPCPY_CHK
:
1476 case BUILT_IN_MEMPCPY_CHKP
:
1477 case BUILT_IN_MEMPCPY_CHK_CHKP
:
1484 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
1485 If strlen of the second argument is known, strlen of the first argument
1486 is increased by the length of the second argument. Furthermore, attempt
1487 to convert it to memcpy/strcpy if the length of the first argument
1491 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1494 tree src
, dst
, srclen
, dstlen
, len
, lhs
, args
, type
, fn
, objsz
, endptr
;
1496 gimple stmt
= gsi_stmt (*gsi
);
1499 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1501 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
1502 dst
= gimple_call_arg (stmt
, 0);
1503 lhs
= gimple_call_lhs (stmt
);
1505 didx
= get_stridx (dst
);
1511 dsi
= get_strinfo (didx
);
1512 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
1514 /* strcat (p, q) can be transformed into
1515 tmp = p + strlen (p); endptr = strpcpy (tmp, q);
1516 with length endptr - p if we need to compute the length
1517 later on. Don't do this transformation if we don't need
1519 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
1523 didx
= new_stridx (dst
);
1529 dsi
= new_strinfo (dst
, didx
, NULL_TREE
);
1530 set_strinfo (didx
, dsi
);
1531 find_equal_ptrs (dst
, didx
);
1535 dsi
= unshare_strinfo (dsi
);
1536 dsi
->length
= NULL_TREE
;
1538 dsi
->endptr
= NULL_TREE
;
1540 dsi
->writable
= true;
1542 dsi
->dont_invalidate
= true;
1549 idx
= get_stridx (src
);
1551 srclen
= build_int_cst (size_type_node
, ~idx
);
1554 si
= get_strinfo (idx
);
1556 srclen
= get_string_length (si
);
1559 loc
= gimple_location (stmt
);
1560 dstlen
= dsi
->length
;
1561 endptr
= dsi
->endptr
;
1563 dsi
= unshare_strinfo (dsi
);
1564 dsi
->endptr
= NULL_TREE
;
1566 dsi
->writable
= true;
1568 if (srclen
!= NULL_TREE
)
1570 dsi
->length
= fold_build2_loc (loc
, PLUS_EXPR
, TREE_TYPE (dsi
->length
),
1571 dsi
->length
, srclen
);
1572 adjust_related_strinfos (loc
, dsi
, srclen
);
1573 dsi
->dont_invalidate
= true;
1578 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1579 dsi
->dont_invalidate
= true;
1583 /* strcat src may not overlap dst, so src doesn't need to be
1584 invalidated either. */
1585 si
->dont_invalidate
= true;
1587 /* For now. Could remove the lhs from the call and add
1588 lhs = dst; afterwards. */
1596 case BUILT_IN_STRCAT
:
1597 case BUILT_IN_STRCAT_CHKP
:
1598 if (srclen
!= NULL_TREE
)
1599 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1601 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
1603 case BUILT_IN_STRCAT_CHK
:
1604 case BUILT_IN_STRCAT_CHK_CHKP
:
1605 if (srclen
!= NULL_TREE
)
1606 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1608 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
1609 objsz
= gimple_call_arg (stmt
, with_bounds
? 4 : 2);
1615 if (fn
== NULL_TREE
)
1619 if (srclen
!= NULL_TREE
)
1621 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1622 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1624 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1625 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
1626 build_int_cst (type
, 1));
1627 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1631 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
1633 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1634 TREE_TYPE (dst
), unshare_expr (dst
),
1635 fold_convert_loc (loc
, sizetype
,
1636 unshare_expr (dstlen
)));
1637 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
1639 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1641 fprintf (dump_file
, "Optimizing: ");
1642 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1646 fn
= chkp_maybe_create_clone (fn
)->decl
;
1647 if (srclen
!= NULL_TREE
)
1648 success
= update_gimple_call (gsi
, fn
, 5 + (objsz
!= NULL_TREE
),
1650 gimple_call_arg (stmt
, 1),
1652 gimple_call_arg (stmt
, 3),
1655 success
= update_gimple_call (gsi
, fn
, 4 + (objsz
!= NULL_TREE
),
1657 gimple_call_arg (stmt
, 1),
1659 gimple_call_arg (stmt
, 3),
1663 if (srclen
!= NULL_TREE
)
1664 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
1665 dst
, src
, len
, objsz
);
1667 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
1671 stmt
= gsi_stmt (*gsi
);
1672 gimple_call_set_with_bounds (stmt
, with_bounds
);
1674 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1676 fprintf (dump_file
, "into: ");
1677 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1679 /* If srclen == NULL, note that current string length can be
1680 computed by transforming this strcpy into stpcpy. */
1681 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
1683 adjust_last_stmt (dsi
, stmt
, true);
1684 if (srclen
!= NULL_TREE
)
1686 laststmt
.stmt
= stmt
;
1687 laststmt
.len
= srclen
;
1688 laststmt
.stridx
= dsi
->idx
;
1691 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1692 fprintf (dump_file
, "not possible.\n");
1695 /* Handle a call to malloc or calloc. */
1698 handle_builtin_malloc (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1700 gimple stmt
= gsi_stmt (*gsi
);
1701 tree lhs
= gimple_call_lhs (stmt
);
1702 gcc_assert (get_stridx (lhs
) == 0);
1703 int idx
= new_stridx (lhs
);
1704 tree length
= NULL_TREE
;
1705 if (bcode
== BUILT_IN_CALLOC
)
1706 length
= build_int_cst (size_type_node
, 0);
1707 strinfo si
= new_strinfo (lhs
, idx
, length
);
1708 if (bcode
== BUILT_IN_CALLOC
)
1710 set_strinfo (idx
, si
);
1711 si
->writable
= true;
1713 si
->dont_invalidate
= true;
1716 /* Handle a call to memset.
1717 After a call to calloc, memset(,0,) is unnecessary.
1718 memset(malloc(n),0,n) is calloc(n,1). */
1721 handle_builtin_memset (gimple_stmt_iterator
*gsi
)
1723 gimple stmt2
= gsi_stmt (*gsi
);
1724 if (!integer_zerop (gimple_call_arg (stmt2
, 1)))
1726 tree ptr
= gimple_call_arg (stmt2
, 0);
1727 int idx1
= get_stridx (ptr
);
1730 strinfo si1
= get_strinfo (idx1
);
1733 gimple stmt1
= si1
->stmt
;
1734 if (!stmt1
|| !is_gimple_call (stmt1
))
1736 tree callee1
= gimple_call_fndecl (stmt1
);
1737 if (!gimple_call_builtin_p (stmt1
, BUILT_IN_NORMAL
))
1739 enum built_in_function code1
= DECL_FUNCTION_CODE (callee1
);
1740 tree size
= gimple_call_arg (stmt2
, 2);
1741 if (code1
== BUILT_IN_CALLOC
)
1742 /* Not touching stmt1 */ ;
1743 else if (code1
== BUILT_IN_MALLOC
1744 && operand_equal_p (gimple_call_arg (stmt1
, 0), size
, 0))
1746 gimple_stmt_iterator gsi1
= gsi_for_stmt (stmt1
);
1747 update_gimple_call (&gsi1
, builtin_decl_implicit (BUILT_IN_CALLOC
), 2,
1748 size
, build_one_cst (size_type_node
));
1749 si1
->length
= build_int_cst (size_type_node
, 0);
1750 si1
->stmt
= gsi_stmt (gsi1
);
1754 tree lhs
= gimple_call_lhs (stmt2
);
1755 unlink_stmt_vdef (stmt2
);
1758 gimple assign
= gimple_build_assign (lhs
, ptr
);
1759 gsi_replace (gsi
, assign
, false);
1763 gsi_remove (gsi
, true);
1764 release_defs (stmt2
);
1770 /* Handle a POINTER_PLUS_EXPR statement.
1771 For p = "abcd" + 2; compute associated length, or if
1772 p = q + off is pointing to a '\0' character of a string, call
1773 zero_length_string on it. */
1776 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
1778 gimple stmt
= gsi_stmt (*gsi
);
1779 tree lhs
= gimple_assign_lhs (stmt
), off
;
1780 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
1788 tree off
= gimple_assign_rhs2 (stmt
);
1789 if (tree_fits_uhwi_p (off
)
1790 && tree_to_uhwi (off
) <= (unsigned HOST_WIDE_INT
) ~idx
)
1791 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
1792 = ~(~idx
- (int) tree_to_uhwi (off
));
1796 si
= get_strinfo (idx
);
1797 if (si
== NULL
|| si
->length
== NULL_TREE
)
1800 off
= gimple_assign_rhs2 (stmt
);
1802 if (operand_equal_p (si
->length
, off
, 0))
1803 zsi
= zero_length_string (lhs
, si
);
1804 else if (TREE_CODE (off
) == SSA_NAME
)
1806 gimple def_stmt
= SSA_NAME_DEF_STMT (off
);
1807 if (gimple_assign_single_p (def_stmt
)
1808 && operand_equal_p (si
->length
, gimple_assign_rhs1 (def_stmt
), 0))
1809 zsi
= zero_length_string (lhs
, si
);
1812 && si
->endptr
!= NULL_TREE
1813 && si
->endptr
!= lhs
1814 && TREE_CODE (si
->endptr
) == SSA_NAME
)
1816 enum tree_code rhs_code
1817 = useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (si
->endptr
))
1818 ? SSA_NAME
: NOP_EXPR
;
1819 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, si
->endptr
, NULL_TREE
);
1820 gcc_assert (gsi_stmt (*gsi
) == stmt
);
1825 /* Handle a single character store. */
1828 handle_char_store (gimple_stmt_iterator
*gsi
)
1832 gimple stmt
= gsi_stmt (*gsi
);
1833 tree ssaname
= NULL_TREE
, lhs
= gimple_assign_lhs (stmt
);
1835 if (TREE_CODE (lhs
) == MEM_REF
1836 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
)
1838 if (integer_zerop (TREE_OPERAND (lhs
, 1)))
1840 ssaname
= TREE_OPERAND (lhs
, 0);
1841 idx
= get_stridx (ssaname
);
1845 idx
= get_addr_stridx (lhs
);
1849 si
= get_strinfo (idx
);
1850 if (si
!= NULL
&& si
->length
!= NULL_TREE
&& integer_zerop (si
->length
))
1852 if (initializer_zerop (gimple_assign_rhs1 (stmt
)))
1854 /* When storing '\0', the store can be removed
1855 if we know it has been stored in the current function. */
1856 if (!stmt_could_throw_p (stmt
) && si
->writable
)
1858 unlink_stmt_vdef (stmt
);
1859 release_defs (stmt
);
1860 gsi_remove (gsi
, true);
1865 si
->writable
= true;
1871 /* Otherwise this statement overwrites the '\0' with
1872 something, if the previous stmt was a memcpy,
1873 its length may be decreased. */
1874 adjust_last_stmt (si
, stmt
, false);
1876 else if (si
!= NULL
&& integer_zerop (gimple_assign_rhs1 (stmt
)))
1878 si
= unshare_strinfo (si
);
1879 si
->length
= build_int_cst (size_type_node
, 0);
1885 si
->writable
= true;
1886 if (ssaname
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
1887 si
->endptr
= ssaname
;
1888 si
->dont_invalidate
= true;
1890 /* If si->length is non-zero constant, we aren't overwriting '\0',
1891 and if we aren't storing '\0', we know that the length of the
1892 string and any other zero terminated string in memory remains
1893 the same. In that case we move to the next gimple statement and
1894 return to signal the caller that it shouldn't invalidate anything.
1896 This is benefical for cases like:
1901 strcpy (p, "foobar");
1902 size_t len = strlen (p); // This can be optimized into 6
1903 size_t len2 = strlen (q); // This has to be computed
1905 size_t len3 = strlen (p); // This can be optimized into 6
1906 size_t len4 = strlen (q); // This can be optimized into len2
1907 bar (len, len2, len3, len4);
1910 else if (si
!= NULL
&& si
->length
!= NULL_TREE
1911 && TREE_CODE (si
->length
) == INTEGER_CST
1912 && integer_nonzerop (gimple_assign_rhs1 (stmt
)))
1918 else if (idx
== 0 && initializer_zerop (gimple_assign_rhs1 (stmt
)))
1922 si
= zero_length_string (ssaname
, NULL
);
1924 si
->dont_invalidate
= true;
1928 int idx
= new_addr_stridx (lhs
);
1931 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
1932 build_int_cst (size_type_node
, 0));
1933 set_strinfo (idx
, si
);
1934 si
->dont_invalidate
= true;
1938 si
->writable
= true;
1941 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == STRING_CST
1942 && ssaname
== NULL_TREE
1943 && TREE_CODE (TREE_TYPE (lhs
)) == ARRAY_TYPE
)
1945 size_t l
= strlen (TREE_STRING_POINTER (gimple_assign_rhs1 (stmt
)));
1946 HOST_WIDE_INT a
= int_size_in_bytes (TREE_TYPE (lhs
));
1947 if (a
> 0 && (unsigned HOST_WIDE_INT
) a
> l
)
1949 int idx
= new_addr_stridx (lhs
);
1952 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
1953 build_int_cst (size_type_node
, l
));
1954 set_strinfo (idx
, si
);
1955 si
->dont_invalidate
= true;
1960 if (si
!= NULL
&& initializer_zerop (gimple_assign_rhs1 (stmt
)))
1962 /* Allow adjust_last_stmt to remove it if the stored '\0'
1963 is immediately overwritten. */
1964 laststmt
.stmt
= stmt
;
1965 laststmt
.len
= build_int_cst (size_type_node
, 1);
1966 laststmt
.stridx
= si
->idx
;
1971 /* Attempt to optimize a single statement at *GSI using string length
1975 strlen_optimize_stmt (gimple_stmt_iterator
*gsi
)
1977 gimple stmt
= gsi_stmt (*gsi
);
1979 if (is_gimple_call (stmt
))
1981 tree callee
= gimple_call_fndecl (stmt
);
1982 if (gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
1983 switch (DECL_FUNCTION_CODE (callee
))
1985 case BUILT_IN_STRLEN
:
1986 case BUILT_IN_STRLEN_CHKP
:
1987 handle_builtin_strlen (gsi
);
1989 case BUILT_IN_STRCHR
:
1990 case BUILT_IN_STRCHR_CHKP
:
1991 handle_builtin_strchr (gsi
);
1993 case BUILT_IN_STRCPY
:
1994 case BUILT_IN_STRCPY_CHK
:
1995 case BUILT_IN_STPCPY
:
1996 case BUILT_IN_STPCPY_CHK
:
1997 case BUILT_IN_STRCPY_CHKP
:
1998 case BUILT_IN_STRCPY_CHK_CHKP
:
1999 case BUILT_IN_STPCPY_CHKP
:
2000 case BUILT_IN_STPCPY_CHK_CHKP
:
2001 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee
), gsi
);
2003 case BUILT_IN_MEMCPY
:
2004 case BUILT_IN_MEMCPY_CHK
:
2005 case BUILT_IN_MEMPCPY
:
2006 case BUILT_IN_MEMPCPY_CHK
:
2007 case BUILT_IN_MEMCPY_CHKP
:
2008 case BUILT_IN_MEMCPY_CHK_CHKP
:
2009 case BUILT_IN_MEMPCPY_CHKP
:
2010 case BUILT_IN_MEMPCPY_CHK_CHKP
:
2011 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee
), gsi
);
2013 case BUILT_IN_STRCAT
:
2014 case BUILT_IN_STRCAT_CHK
:
2015 case BUILT_IN_STRCAT_CHKP
:
2016 case BUILT_IN_STRCAT_CHK_CHKP
:
2017 handle_builtin_strcat (DECL_FUNCTION_CODE (callee
), gsi
);
2019 case BUILT_IN_MALLOC
:
2020 case BUILT_IN_CALLOC
:
2021 handle_builtin_malloc (DECL_FUNCTION_CODE (callee
), gsi
);
2023 case BUILT_IN_MEMSET
:
2024 if (!handle_builtin_memset (gsi
))
2031 else if (is_gimple_assign (stmt
) && !gimple_clobber_p (stmt
))
2033 tree lhs
= gimple_assign_lhs (stmt
);
2035 if (TREE_CODE (lhs
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (lhs
)))
2037 if (gimple_assign_single_p (stmt
)
2038 || (gimple_assign_cast_p (stmt
)
2039 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
2041 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
2042 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = idx
;
2044 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
2045 handle_pointer_plus (gsi
);
2047 else if (TREE_CODE (lhs
) != SSA_NAME
&& !TREE_SIDE_EFFECTS (lhs
))
2049 tree type
= TREE_TYPE (lhs
);
2050 if (TREE_CODE (type
) == ARRAY_TYPE
)
2051 type
= TREE_TYPE (type
);
2052 if (TREE_CODE (type
) == INTEGER_TYPE
2053 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
2054 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
))
2056 if (! handle_char_store (gsi
))
2062 if (gimple_vdef (stmt
))
2063 maybe_invalidate (stmt
);
2067 /* Recursively call maybe_invalidate on stmts that might be executed
2068 in between dombb and current bb and that contain a vdef. Stop when
2069 *count stmts are inspected, or if the whole strinfo vector has
2070 been invalidated. */
2073 do_invalidate (basic_block dombb
, gimple phi
, bitmap visited
, int *count
)
2075 unsigned int i
, n
= gimple_phi_num_args (phi
);
2077 for (i
= 0; i
< n
; i
++)
2079 tree vuse
= gimple_phi_arg_def (phi
, i
);
2080 gimple stmt
= SSA_NAME_DEF_STMT (vuse
);
2081 basic_block bb
= gimple_bb (stmt
);
2084 || !bitmap_set_bit (visited
, bb
->index
)
2085 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
2089 if (gimple_code (stmt
) == GIMPLE_PHI
)
2091 do_invalidate (dombb
, stmt
, visited
, count
);
2098 if (!maybe_invalidate (stmt
))
2103 vuse
= gimple_vuse (stmt
);
2104 stmt
= SSA_NAME_DEF_STMT (vuse
);
2105 if (gimple_bb (stmt
) != bb
)
2107 bb
= gimple_bb (stmt
);
2110 || !bitmap_set_bit (visited
, bb
->index
)
2111 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
2118 class strlen_dom_walker
: public dom_walker
2121 strlen_dom_walker (cdi_direction direction
) : dom_walker (direction
) {}
2123 virtual void before_dom_children (basic_block
);
2124 virtual void after_dom_children (basic_block
);
2127 /* Callback for walk_dominator_tree. Attempt to optimize various
2128 string ops by remembering string lenths pointed by pointer SSA_NAMEs. */
2131 strlen_dom_walker::before_dom_children (basic_block bb
)
2133 basic_block dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
2136 stridx_to_strinfo
= NULL
;
2139 stridx_to_strinfo
= ((vec
<strinfo
, va_heap
, vl_embed
> *) dombb
->aux
);
2140 if (stridx_to_strinfo
)
2142 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
2145 gphi
*phi
= gsi
.phi ();
2146 if (virtual_operand_p (gimple_phi_result (phi
)))
2148 bitmap visited
= BITMAP_ALLOC (NULL
);
2149 int count_vdef
= 100;
2150 do_invalidate (dombb
, phi
, visited
, &count_vdef
);
2151 BITMAP_FREE (visited
);
2152 if (count_vdef
== 0)
2154 /* If there were too many vdefs in between immediate
2155 dominator and current bb, invalidate everything.
2156 If stridx_to_strinfo has been unshared, we need
2157 to free it, otherwise just set it to NULL. */
2158 if (!strinfo_shared ())
2164 vec_safe_iterate (stridx_to_strinfo
, i
, &si
);
2168 (*stridx_to_strinfo
)[i
] = NULL
;
2172 stridx_to_strinfo
= NULL
;
2180 /* If all PHI arguments have the same string index, the PHI result
2182 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
2185 gphi
*phi
= gsi
.phi ();
2186 tree result
= gimple_phi_result (phi
);
2187 if (!virtual_operand_p (result
) && POINTER_TYPE_P (TREE_TYPE (result
)))
2189 int idx
= get_stridx (gimple_phi_arg_def (phi
, 0));
2192 unsigned int i
, n
= gimple_phi_num_args (phi
);
2193 for (i
= 1; i
< n
; i
++)
2194 if (idx
!= get_stridx (gimple_phi_arg_def (phi
, i
)))
2197 ssa_ver_to_stridx
[SSA_NAME_VERSION (result
)] = idx
;
2202 /* Attempt to optimize individual statements. */
2203 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2204 if (strlen_optimize_stmt (&gsi
))
2207 bb
->aux
= stridx_to_strinfo
;
2208 if (vec_safe_length (stridx_to_strinfo
) && !strinfo_shared ())
2209 (*stridx_to_strinfo
)[0] = (strinfo
) bb
;
2212 /* Callback for walk_dominator_tree. Free strinfo vector if it is
2213 owned by the current bb, clear bb->aux. */
2216 strlen_dom_walker::after_dom_children (basic_block bb
)
2220 stridx_to_strinfo
= ((vec
<strinfo
, va_heap
, vl_embed
> *) bb
->aux
);
2221 if (vec_safe_length (stridx_to_strinfo
)
2222 && (*stridx_to_strinfo
)[0] == (strinfo
) bb
)
2227 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
2229 vec_free (stridx_to_strinfo
);
2235 /* Main entry point. */
2239 const pass_data pass_data_strlen
=
2241 GIMPLE_PASS
, /* type */
2242 "strlen", /* name */
2243 OPTGROUP_NONE
, /* optinfo_flags */
2244 TV_TREE_STRLEN
, /* tv_id */
2245 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2246 0, /* properties_provided */
2247 0, /* properties_destroyed */
2248 0, /* todo_flags_start */
2249 0, /* todo_flags_finish */
2252 class pass_strlen
: public gimple_opt_pass
2255 pass_strlen (gcc::context
*ctxt
)
2256 : gimple_opt_pass (pass_data_strlen
, ctxt
)
2259 /* opt_pass methods: */
2260 virtual bool gate (function
*) { return flag_optimize_strlen
!= 0; }
2261 virtual unsigned int execute (function
*);
2263 }; // class pass_strlen
2266 pass_strlen::execute (function
*fun
)
2268 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
2270 strinfo_pool
= create_alloc_pool ("strinfo_struct pool",
2271 sizeof (struct strinfo_struct
), 64);
2273 calculate_dominance_info (CDI_DOMINATORS
);
2275 /* String length optimization is implemented as a walk of the dominator
2276 tree and a forward walk of statements within each block. */
2277 strlen_dom_walker (CDI_DOMINATORS
).walk (fun
->cfg
->x_entry_block_ptr
);
2279 ssa_ver_to_stridx
.release ();
2280 free_alloc_pool (strinfo_pool
);
2281 if (decl_to_stridxlist_htab
)
2283 obstack_free (&stridx_obstack
, NULL
);
2284 delete decl_to_stridxlist_htab
;
2285 decl_to_stridxlist_htab
= NULL
;
2287 laststmt
.stmt
= NULL
;
2288 laststmt
.len
= NULL_TREE
;
2289 laststmt
.stridx
= 0;
2297 make_pass_strlen (gcc::context
*ctxt
)
2299 return new pass_strlen (ctxt
);