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"
66 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
67 is an index into strinfo vector, negative value stands for
68 string length of a string literal (~strlen). */
69 static vec
<int> ssa_ver_to_stridx
;
71 /* Number of currently active string indexes plus one. */
72 static int max_stridx
;
74 /* String information record. */
75 typedef struct strinfo_struct
77 /* String length of this string. */
79 /* Any of the corresponding pointers for querying alias oracle. */
81 /* Statement for delayed length computation. */
83 /* Pointer to '\0' if known, if NULL, it can be computed as
86 /* Reference count. Any changes to strinfo entry possibly shared
87 with dominating basic blocks need unshare_strinfo first, except
88 for dont_invalidate which affects only the immediately next
91 /* Copy of index. get_strinfo (si->idx) should return si; */
93 /* These 3 fields are for chaining related string pointers together.
95 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
96 strcpy (c, d); e = c + dl;
97 strinfo(a) -> strinfo(c) -> strinfo(e)
98 All have ->first field equal to strinfo(a)->idx and are doubly
99 chained through prev/next fields. The later strinfos are required
100 to point into the same string with zero or more bytes after
101 the previous pointer and all bytes in between the two pointers
102 must be non-zero. Functions like strcpy or memcpy are supposed
103 to adjust all previous strinfo lengths, but not following strinfo
104 lengths (those are uncertain, usually invalidated during
105 maybe_invalidate, except when the alias oracle knows better).
106 Functions like strcat on the other side adjust the whole
107 related strinfo chain.
108 They are updated lazily, so to use the chain the same first fields
109 and si->prev->next == si->idx needs to be verified. */
113 /* A flag whether the string is known to be written in the current
116 /* A flag for the next maybe_invalidate that this strinfo shouldn't
117 be invalidated. Always cleared by maybe_invalidate. */
118 bool dont_invalidate
;
121 /* Pool for allocating strinfo_struct entries. */
122 static alloc_pool strinfo_pool
;
124 /* Vector mapping positive string indexes to strinfo, for the
125 current basic block. The first pointer in the vector is special,
126 it is either NULL, meaning the vector isn't shared, or it is
127 a basic block pointer to the owner basic_block if shared.
128 If some other bb wants to modify the vector, the vector needs
129 to be unshared first, and only the owner bb is supposed to free it. */
130 static vec
<strinfo
, va_heap
, vl_embed
> *stridx_to_strinfo
;
132 /* One OFFSET->IDX mapping. */
135 struct stridxlist
*next
;
136 HOST_WIDE_INT offset
;
140 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
141 struct decl_stridxlist_map
143 struct tree_map_base base
;
144 struct stridxlist list
;
147 /* stridxlist hashtable helpers. */
149 struct stridxlist_hash_traits
: default_hashmap_traits
151 static inline hashval_t
hash (tree
);
154 /* Hash a from tree in a decl_stridxlist_map. */
157 stridxlist_hash_traits::hash (tree item
)
159 return DECL_UID (item
);
162 /* Hash table for mapping decls to a chained list of offset -> idx
164 static hash_map
<tree
, stridxlist
, stridxlist_hash_traits
>
165 *decl_to_stridxlist_htab
;
167 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
168 static struct obstack stridx_obstack
;
170 /* Last memcpy statement if it could be adjusted if the trailing
171 '\0' written is immediately overwritten, or
172 *x = '\0' store that could be removed if it is immediately overwritten. */
173 struct laststmt_struct
180 /* Helper function for get_stridx. */
183 get_addr_stridx (tree exp
)
186 struct stridxlist
*list
;
189 if (!decl_to_stridxlist_htab
)
192 base
= get_addr_base_and_unit_offset (exp
, &off
);
193 if (base
== NULL
|| !DECL_P (base
))
196 list
= decl_to_stridxlist_htab
->get (base
);
202 if (list
->offset
== off
)
210 /* Return string index for EXP. */
213 get_stridx (tree exp
)
217 if (TREE_CODE (exp
) == SSA_NAME
)
218 return ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)];
220 if (TREE_CODE (exp
) == ADDR_EXPR
)
222 int idx
= get_addr_stridx (TREE_OPERAND (exp
, 0));
227 s
= string_constant (exp
, &o
);
229 && (o
== NULL_TREE
|| tree_fits_shwi_p (o
))
230 && TREE_STRING_LENGTH (s
) > 0)
232 HOST_WIDE_INT offset
= o
? tree_to_shwi (o
) : 0;
233 const char *p
= TREE_STRING_POINTER (s
);
234 int max
= TREE_STRING_LENGTH (s
) - 1;
236 if (p
[max
] == '\0' && offset
>= 0 && offset
<= max
)
237 return ~(int) strlen (p
+ offset
);
242 /* Return true if strinfo vector is shared with the immediate dominator. */
245 strinfo_shared (void)
247 return vec_safe_length (stridx_to_strinfo
)
248 && (*stridx_to_strinfo
)[0] != NULL
;
251 /* Unshare strinfo vector that is shared with the immediate dominator. */
254 unshare_strinfo_vec (void)
259 gcc_assert (strinfo_shared ());
260 stridx_to_strinfo
= vec_safe_copy (stridx_to_strinfo
);
261 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
264 (*stridx_to_strinfo
)[0] = NULL
;
267 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
268 Return a pointer to the location where the string index can
269 be stored (if 0) or is stored, or NULL if this can't be tracked. */
272 addr_stridxptr (tree exp
)
276 tree base
= get_addr_base_and_unit_offset (exp
, &off
);
277 if (base
== NULL_TREE
|| !DECL_P (base
))
280 if (!decl_to_stridxlist_htab
)
282 decl_to_stridxlist_htab
283 = new hash_map
<tree
, stridxlist
, stridxlist_hash_traits
> (64);
284 gcc_obstack_init (&stridx_obstack
);
288 stridxlist
*list
= &decl_to_stridxlist_htab
->get_or_insert (base
, &existed
);
292 for (i
= 0; i
< 16; i
++)
294 if (list
->offset
== off
)
296 if (list
->next
== NULL
)
301 list
->next
= XOBNEW (&stridx_obstack
, struct stridxlist
);
311 /* Create a new string index, or return 0 if reached limit. */
314 new_stridx (tree exp
)
317 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
319 if (TREE_CODE (exp
) == SSA_NAME
)
321 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
))
324 ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)] = idx
;
327 if (TREE_CODE (exp
) == ADDR_EXPR
)
329 int *pidx
= addr_stridxptr (TREE_OPERAND (exp
, 0));
332 gcc_assert (*pidx
== 0);
333 *pidx
= max_stridx
++;
340 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
343 new_addr_stridx (tree exp
)
346 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
348 pidx
= addr_stridxptr (exp
);
351 gcc_assert (*pidx
== 0);
352 *pidx
= max_stridx
++;
358 /* Create a new strinfo. */
361 new_strinfo (tree ptr
, int idx
, tree length
)
363 strinfo si
= (strinfo
) pool_alloc (strinfo_pool
);
367 si
->endptr
= NULL_TREE
;
373 si
->writable
= false;
374 si
->dont_invalidate
= false;
378 /* Decrease strinfo refcount and free it if not referenced anymore. */
381 free_strinfo (strinfo si
)
383 if (si
&& --si
->refcount
== 0)
384 pool_free (strinfo_pool
, si
);
387 /* Return strinfo vector entry IDX. */
389 static inline strinfo
390 get_strinfo (int idx
)
392 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
394 return (*stridx_to_strinfo
)[idx
];
397 /* Set strinfo in the vector entry IDX to SI. */
400 set_strinfo (int idx
, strinfo si
)
402 if (vec_safe_length (stridx_to_strinfo
) && (*stridx_to_strinfo
)[0])
403 unshare_strinfo_vec ();
404 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
405 vec_safe_grow_cleared (stridx_to_strinfo
, idx
+ 1);
406 (*stridx_to_strinfo
)[idx
] = si
;
409 /* Return string length, or NULL if it can't be computed. */
412 get_string_length (strinfo si
)
419 gimple stmt
= si
->stmt
, lenstmt
;
420 tree callee
, lhs
, fn
, tem
;
422 gimple_stmt_iterator gsi
;
424 gcc_assert (is_gimple_call (stmt
));
425 callee
= gimple_call_fndecl (stmt
);
426 gcc_assert (callee
&& DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
);
427 lhs
= gimple_call_lhs (stmt
);
428 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY
));
429 /* unshare_strinfo is intentionally not called here. The (delayed)
430 transformation of strcpy or strcat into stpcpy is done at the place
431 of the former strcpy/strcat call and so can affect all the strinfos
432 with the same stmt. If they were unshared before and transformation
433 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
434 just compute the right length. */
435 switch (DECL_FUNCTION_CODE (callee
))
437 case BUILT_IN_STRCAT
:
438 case BUILT_IN_STRCAT_CHK
:
439 gsi
= gsi_for_stmt (stmt
);
440 fn
= builtin_decl_implicit (BUILT_IN_STRLEN
);
441 gcc_assert (lhs
== NULL_TREE
);
442 tem
= unshare_expr (gimple_call_arg (stmt
, 0));
443 lenstmt
= gimple_build_call (fn
, 1, tem
);
444 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), lenstmt
);
445 gimple_call_set_lhs (lenstmt
, lhs
);
446 gimple_set_vuse (lenstmt
, gimple_vuse (stmt
));
447 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
448 tem
= gimple_call_arg (stmt
, 0);
449 if (!ptrofftype_p (TREE_TYPE (lhs
)))
451 lhs
= convert_to_ptrofftype (lhs
);
452 lhs
= force_gimple_operand_gsi (&gsi
, lhs
, true, NULL_TREE
,
453 true, GSI_SAME_STMT
);
456 = gimple_build_assign_with_ops
458 make_ssa_name (TREE_TYPE (gimple_call_arg (stmt
, 0)), NULL
),
460 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
461 gimple_call_set_arg (stmt
, 0, gimple_assign_lhs (lenstmt
));
464 case BUILT_IN_STRCPY
:
465 case BUILT_IN_STRCPY_CHK
:
466 if (gimple_call_num_args (stmt
) == 2)
467 fn
= builtin_decl_implicit (BUILT_IN_STPCPY
);
469 fn
= builtin_decl_explicit (BUILT_IN_STPCPY_CHK
);
470 gcc_assert (lhs
== NULL_TREE
);
471 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
473 fprintf (dump_file
, "Optimizing: ");
474 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
476 gimple_call_set_fndecl (stmt
, fn
);
477 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), stmt
);
478 gimple_call_set_lhs (stmt
, lhs
);
480 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
482 fprintf (dump_file
, "into: ");
483 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
486 case BUILT_IN_STPCPY
:
487 case BUILT_IN_STPCPY_CHK
:
488 gcc_assert (lhs
!= NULL_TREE
);
489 loc
= gimple_location (stmt
);
492 lhs
= fold_convert_loc (loc
, size_type_node
, lhs
);
493 si
->length
= fold_convert_loc (loc
, size_type_node
, si
->ptr
);
494 si
->length
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
497 case BUILT_IN_MALLOC
:
499 /* BUILT_IN_CALLOC always has si->length set. */
509 /* Invalidate string length information for strings whose length
510 might change due to stores in stmt. */
513 maybe_invalidate (gimple stmt
)
517 bool nonempty
= false;
519 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
522 if (!si
->dont_invalidate
)
525 /* Do not use si->length. */
526 ao_ref_init_from_ptr_and_size (&r
, si
->ptr
, NULL_TREE
);
527 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
529 set_strinfo (i
, NULL
);
534 si
->dont_invalidate
= false;
540 /* Unshare strinfo record SI, if it has recount > 1 or
541 if stridx_to_strinfo vector is shared with some other
545 unshare_strinfo (strinfo si
)
549 if (si
->refcount
== 1 && !strinfo_shared ())
552 nsi
= new_strinfo (si
->ptr
, si
->idx
, si
->length
);
553 nsi
->stmt
= si
->stmt
;
554 nsi
->endptr
= si
->endptr
;
555 nsi
->first
= si
->first
;
556 nsi
->prev
= si
->prev
;
557 nsi
->next
= si
->next
;
558 nsi
->writable
= si
->writable
;
559 set_strinfo (si
->idx
, nsi
);
564 /* Return first strinfo in the related strinfo chain
565 if all strinfos in between belong to the chain, otherwise
569 verify_related_strinfos (strinfo origsi
)
571 strinfo si
= origsi
, psi
;
573 if (origsi
->first
== 0)
575 for (; si
->prev
; si
= psi
)
577 if (si
->first
!= origsi
->first
)
579 psi
= get_strinfo (si
->prev
);
582 if (psi
->next
!= si
->idx
)
585 if (si
->idx
!= si
->first
)
590 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
591 to a zero-length string and if possible chain it to a related strinfo
592 chain whose part is or might be CHAINSI. */
595 zero_length_string (tree ptr
, strinfo chainsi
)
599 gcc_checking_assert (TREE_CODE (ptr
) == SSA_NAME
600 && get_stridx (ptr
) == 0);
602 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
606 si
= verify_related_strinfos (chainsi
);
610 for (; chainsi
->next
; chainsi
= si
)
612 if (chainsi
->endptr
== NULL_TREE
)
614 chainsi
= unshare_strinfo (chainsi
);
615 chainsi
->endptr
= ptr
;
617 si
= get_strinfo (chainsi
->next
);
619 || si
->first
!= chainsi
->first
620 || si
->prev
!= chainsi
->idx
)
623 gcc_assert (chainsi
->length
|| chainsi
->stmt
);
624 if (chainsi
->endptr
== NULL_TREE
)
626 chainsi
= unshare_strinfo (chainsi
);
627 chainsi
->endptr
= ptr
;
629 if (chainsi
->length
&& integer_zerop (chainsi
->length
))
633 chainsi
= unshare_strinfo (chainsi
);
636 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = chainsi
->idx
;
640 else if (chainsi
->first
|| chainsi
->prev
|| chainsi
->next
)
642 chainsi
= unshare_strinfo (chainsi
);
648 idx
= new_stridx (ptr
);
651 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, 0));
652 set_strinfo (idx
, si
);
656 chainsi
= unshare_strinfo (chainsi
);
657 if (chainsi
->first
== 0)
658 chainsi
->first
= chainsi
->idx
;
660 if (chainsi
->endptr
== NULL_TREE
)
661 chainsi
->endptr
= ptr
;
662 si
->prev
= chainsi
->idx
;
663 si
->first
= chainsi
->first
;
664 si
->writable
= chainsi
->writable
;
669 /* For strinfo ORIGSI whose length has been just updated
670 update also related strinfo lengths (add ADJ to each,
671 but don't adjust ORIGSI). */
674 adjust_related_strinfos (location_t loc
, strinfo origsi
, tree adj
)
676 strinfo si
= verify_related_strinfos (origsi
);
689 si
= unshare_strinfo (si
);
692 tem
= fold_convert_loc (loc
, TREE_TYPE (si
->length
), adj
);
693 si
->length
= fold_build2_loc (loc
, PLUS_EXPR
,
694 TREE_TYPE (si
->length
), si
->length
,
697 else if (si
->stmt
!= NULL
)
698 /* Delayed length computation is unaffected. */
703 si
->endptr
= NULL_TREE
;
704 si
->dont_invalidate
= true;
708 nsi
= get_strinfo (si
->next
);
710 || nsi
->first
!= si
->first
711 || nsi
->prev
!= si
->idx
)
717 /* Find if there are other SSA_NAME pointers equal to PTR
718 for which we don't track their string lengths yet. If so, use
722 find_equal_ptrs (tree ptr
, int idx
)
724 if (TREE_CODE (ptr
) != SSA_NAME
)
728 gimple stmt
= SSA_NAME_DEF_STMT (ptr
);
729 if (!is_gimple_assign (stmt
))
731 ptr
= gimple_assign_rhs1 (stmt
);
732 switch (gimple_assign_rhs_code (stmt
))
737 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)))
739 if (TREE_CODE (ptr
) == SSA_NAME
)
741 if (TREE_CODE (ptr
) != ADDR_EXPR
)
746 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
747 if (pidx
!= NULL
&& *pidx
== 0)
755 /* We might find an endptr created in this pass. Grow the
756 vector in that case. */
757 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
758 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
760 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] != 0)
762 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = idx
;
766 /* If the last .MEM setter statement before STMT is
767 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
768 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
769 just memcpy (x, y, strlen (y)). SI must be the zero length
773 adjust_last_stmt (strinfo si
, gimple stmt
, bool is_strcat
)
775 tree vuse
, callee
, len
;
776 struct laststmt_struct last
= laststmt
;
777 strinfo lastsi
, firstsi
;
779 laststmt
.stmt
= NULL
;
780 laststmt
.len
= NULL_TREE
;
783 if (last
.stmt
== NULL
)
786 vuse
= gimple_vuse (stmt
);
787 if (vuse
== NULL_TREE
788 || SSA_NAME_DEF_STMT (vuse
) != last
.stmt
789 || !has_single_use (vuse
))
792 gcc_assert (last
.stridx
> 0);
793 lastsi
= get_strinfo (last
.stridx
);
799 if (lastsi
->first
== 0 || lastsi
->first
!= si
->first
)
802 firstsi
= verify_related_strinfos (si
);
805 while (firstsi
!= lastsi
)
808 if (firstsi
->next
== 0)
810 nextsi
= get_strinfo (firstsi
->next
);
812 || nextsi
->prev
!= firstsi
->idx
813 || nextsi
->first
!= si
->first
)
821 if (si
->length
== NULL_TREE
|| !integer_zerop (si
->length
))
825 if (is_gimple_assign (last
.stmt
))
827 gimple_stmt_iterator gsi
;
829 if (!integer_zerop (gimple_assign_rhs1 (last
.stmt
)))
831 if (stmt_could_throw_p (last
.stmt
))
833 gsi
= gsi_for_stmt (last
.stmt
);
834 unlink_stmt_vdef (last
.stmt
);
835 release_defs (last
.stmt
);
836 gsi_remove (&gsi
, true);
840 if (!gimple_call_builtin_p (last
.stmt
, BUILT_IN_NORMAL
))
843 callee
= gimple_call_fndecl (last
.stmt
);
844 switch (DECL_FUNCTION_CODE (callee
))
846 case BUILT_IN_MEMCPY
:
847 case BUILT_IN_MEMCPY_CHK
:
853 len
= gimple_call_arg (last
.stmt
, 2);
854 if (tree_fits_uhwi_p (len
))
856 if (!tree_fits_uhwi_p (last
.len
)
857 || integer_zerop (len
)
858 || tree_to_uhwi (len
) != tree_to_uhwi (last
.len
) + 1)
860 /* Don't adjust the length if it is divisible by 4, it is more efficient
861 to store the extra '\0' in that case. */
862 if ((tree_to_uhwi (len
) & 3) == 0)
865 else if (TREE_CODE (len
) == SSA_NAME
)
867 gimple def_stmt
= SSA_NAME_DEF_STMT (len
);
868 if (!is_gimple_assign (def_stmt
)
869 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
870 || gimple_assign_rhs1 (def_stmt
) != last
.len
871 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
877 gimple_call_set_arg (last
.stmt
, 2, last
.len
);
878 update_stmt (last
.stmt
);
881 /* Handle a strlen call. If strlen of the argument is known, replace
882 the strlen call with the known value, otherwise remember that strlen
883 of the argument is stored in the lhs SSA_NAME. */
886 handle_builtin_strlen (gimple_stmt_iterator
*gsi
)
890 gimple stmt
= gsi_stmt (*gsi
);
891 tree lhs
= gimple_call_lhs (stmt
);
893 if (lhs
== NULL_TREE
)
896 src
= gimple_call_arg (stmt
, 0);
897 idx
= get_stridx (src
);
904 rhs
= build_int_cst (TREE_TYPE (lhs
), ~idx
);
908 si
= get_strinfo (idx
);
910 rhs
= get_string_length (si
);
912 if (rhs
!= NULL_TREE
)
914 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
916 fprintf (dump_file
, "Optimizing: ");
917 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
919 rhs
= unshare_expr (rhs
);
920 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
921 rhs
= fold_convert_loc (gimple_location (stmt
),
922 TREE_TYPE (lhs
), rhs
);
923 if (!update_call_from_tree (gsi
, rhs
))
924 gimplify_and_update_call_from_tree (gsi
, rhs
);
925 stmt
= gsi_stmt (*gsi
);
927 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
929 fprintf (dump_file
, "into: ");
930 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
933 && TREE_CODE (si
->length
) != SSA_NAME
934 && TREE_CODE (si
->length
) != INTEGER_CST
935 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
937 si
= unshare_strinfo (si
);
943 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
946 idx
= new_stridx (src
);
947 else if (get_strinfo (idx
) != NULL
)
951 strinfo si
= new_strinfo (src
, idx
, lhs
);
952 set_strinfo (idx
, si
);
953 find_equal_ptrs (src
, idx
);
957 /* Handle a strchr call. If strlen of the first argument is known, replace
958 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
959 that lhs of the call is endptr and strlen of the argument is endptr - x. */
962 handle_builtin_strchr (gimple_stmt_iterator
*gsi
)
966 gimple stmt
= gsi_stmt (*gsi
);
967 tree lhs
= gimple_call_lhs (stmt
);
969 if (lhs
== NULL_TREE
)
972 if (!integer_zerop (gimple_call_arg (stmt
, 1)))
975 src
= gimple_call_arg (stmt
, 0);
976 idx
= get_stridx (src
);
983 rhs
= build_int_cst (size_type_node
, ~idx
);
987 si
= get_strinfo (idx
);
989 rhs
= get_string_length (si
);
991 if (rhs
!= NULL_TREE
)
993 location_t loc
= gimple_location (stmt
);
995 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
997 fprintf (dump_file
, "Optimizing: ");
998 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1000 if (si
!= NULL
&& si
->endptr
!= NULL_TREE
)
1002 rhs
= unshare_expr (si
->endptr
);
1003 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1005 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1009 rhs
= fold_convert_loc (loc
, sizetype
, unshare_expr (rhs
));
1010 rhs
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1011 TREE_TYPE (src
), src
, rhs
);
1012 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1014 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1016 if (!update_call_from_tree (gsi
, rhs
))
1017 gimplify_and_update_call_from_tree (gsi
, rhs
);
1018 stmt
= gsi_stmt (*gsi
);
1020 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1022 fprintf (dump_file
, "into: ");
1023 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1026 && si
->endptr
== NULL_TREE
1027 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1029 si
= unshare_strinfo (si
);
1032 zero_length_string (lhs
, si
);
1036 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1038 if (TREE_CODE (src
) != SSA_NAME
|| !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src
))
1041 idx
= new_stridx (src
);
1042 else if (get_strinfo (idx
) != NULL
)
1044 zero_length_string (lhs
, NULL
);
1049 location_t loc
= gimple_location (stmt
);
1050 tree lhsu
= fold_convert_loc (loc
, size_type_node
, lhs
);
1051 tree srcu
= fold_convert_loc (loc
, size_type_node
, src
);
1052 tree length
= fold_build2_loc (loc
, MINUS_EXPR
,
1053 size_type_node
, lhsu
, srcu
);
1054 strinfo si
= new_strinfo (src
, idx
, length
);
1056 set_strinfo (idx
, si
);
1057 find_equal_ptrs (src
, idx
);
1058 zero_length_string (lhs
, si
);
1062 zero_length_string (lhs
, NULL
);
1065 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1066 If strlen of the second argument is known, strlen of the first argument
1067 is the same after this call. Furthermore, attempt to convert it to
1071 handle_builtin_strcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1074 tree src
, dst
, srclen
, len
, lhs
, args
, type
, fn
, oldlen
;
1076 gimple stmt
= gsi_stmt (*gsi
);
1077 strinfo si
, dsi
, olddsi
, zsi
;
1080 src
= gimple_call_arg (stmt
, 1);
1081 dst
= gimple_call_arg (stmt
, 0);
1082 lhs
= gimple_call_lhs (stmt
);
1083 idx
= get_stridx (src
);
1086 si
= get_strinfo (idx
);
1088 didx
= get_stridx (dst
);
1092 olddsi
= get_strinfo (didx
);
1097 adjust_last_stmt (olddsi
, stmt
, false);
1101 srclen
= get_string_length (si
);
1103 srclen
= build_int_cst (size_type_node
, ~idx
);
1105 loc
= gimple_location (stmt
);
1106 if (srclen
== NULL_TREE
)
1109 case BUILT_IN_STRCPY
:
1110 case BUILT_IN_STRCPY_CHK
:
1111 if (lhs
!= NULL_TREE
|| !builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1114 case BUILT_IN_STPCPY
:
1115 case BUILT_IN_STPCPY_CHK
:
1116 if (lhs
== NULL_TREE
)
1120 tree lhsuint
= fold_convert_loc (loc
, size_type_node
, lhs
);
1121 srclen
= fold_convert_loc (loc
, size_type_node
, dst
);
1122 srclen
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
1132 didx
= new_stridx (dst
);
1138 oldlen
= olddsi
->length
;
1139 dsi
= unshare_strinfo (olddsi
);
1140 dsi
->length
= srclen
;
1141 /* Break the chain, so adjust_related_strinfo on later pointers in
1142 the chain won't adjust this one anymore. */
1145 dsi
->endptr
= NULL_TREE
;
1149 dsi
= new_strinfo (dst
, didx
, srclen
);
1150 set_strinfo (didx
, dsi
);
1151 find_equal_ptrs (dst
, didx
);
1153 dsi
->writable
= true;
1154 dsi
->dont_invalidate
= true;
1156 if (dsi
->length
== NULL_TREE
)
1160 /* If string length of src is unknown, use delayed length
1161 computation. If string lenth of dst will be needed, it
1162 can be computed by transforming this strcpy call into
1163 stpcpy and subtracting dst from the return value. */
1165 /* Look for earlier strings whose length could be determined if
1166 this strcpy is turned into an stpcpy. */
1168 if (dsi
->prev
!= 0 && (chainsi
= verify_related_strinfos (dsi
)) != NULL
)
1170 for (; chainsi
&& chainsi
!= dsi
; chainsi
= get_strinfo (chainsi
->next
))
1172 /* When setting a stmt for delayed length computation
1173 prevent all strinfos through dsi from being
1175 chainsi
= unshare_strinfo (chainsi
);
1176 chainsi
->stmt
= stmt
;
1177 chainsi
->length
= NULL_TREE
;
1178 chainsi
->endptr
= NULL_TREE
;
1179 chainsi
->dont_invalidate
= true;
1188 tree adj
= NULL_TREE
;
1189 if (oldlen
== NULL_TREE
)
1191 else if (integer_zerop (oldlen
))
1193 else if (TREE_CODE (oldlen
) == INTEGER_CST
1194 || TREE_CODE (srclen
) == INTEGER_CST
)
1195 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1196 TREE_TYPE (srclen
), srclen
,
1197 fold_convert_loc (loc
, TREE_TYPE (srclen
),
1199 if (adj
!= NULL_TREE
)
1200 adjust_related_strinfos (loc
, dsi
, adj
);
1204 /* strcpy src may not overlap dst, so src doesn't need to be
1205 invalidated either. */
1207 si
->dont_invalidate
= true;
1213 case BUILT_IN_STRCPY
:
1214 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1216 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1218 case BUILT_IN_STRCPY_CHK
:
1219 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1221 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1223 case BUILT_IN_STPCPY
:
1224 /* This would need adjustment of the lhs (subtract one),
1225 or detection that the trailing '\0' doesn't need to be
1226 written, if it will be immediately overwritten.
1227 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1231 zsi
= zero_length_string (lhs
, dsi
);
1234 case BUILT_IN_STPCPY_CHK
:
1235 /* This would need adjustment of the lhs (subtract one),
1236 or detection that the trailing '\0' doesn't need to be
1237 written, if it will be immediately overwritten.
1238 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1242 zsi
= zero_length_string (lhs
, dsi
);
1249 zsi
->dont_invalidate
= true;
1251 if (fn
== NULL_TREE
)
1254 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1255 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1257 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1258 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
, build_int_cst (type
, 1));
1259 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1261 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1263 fprintf (dump_file
, "Optimizing: ");
1264 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1266 if (gimple_call_num_args (stmt
) == 2)
1267 success
= update_gimple_call (gsi
, fn
, 3, dst
, src
, len
);
1269 success
= update_gimple_call (gsi
, fn
, 4, dst
, src
, len
,
1270 gimple_call_arg (stmt
, 2));
1273 stmt
= gsi_stmt (*gsi
);
1275 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1277 fprintf (dump_file
, "into: ");
1278 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1280 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1281 laststmt
.stmt
= stmt
;
1282 laststmt
.len
= srclen
;
1283 laststmt
.stridx
= dsi
->idx
;
1285 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1286 fprintf (dump_file
, "not possible.\n");
1289 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
1290 If strlen of the second argument is known and length of the third argument
1291 is that plus one, strlen of the first argument is the same after this
1295 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1298 tree src
, dst
, len
, lhs
, oldlen
, newlen
;
1299 gimple stmt
= gsi_stmt (*gsi
);
1300 strinfo si
, dsi
, olddsi
;
1302 len
= gimple_call_arg (stmt
, 2);
1303 src
= gimple_call_arg (stmt
, 1);
1304 dst
= gimple_call_arg (stmt
, 0);
1305 idx
= get_stridx (src
);
1309 didx
= get_stridx (dst
);
1312 olddsi
= get_strinfo (didx
);
1317 && tree_fits_uhwi_p (len
)
1318 && !integer_zerop (len
))
1319 adjust_last_stmt (olddsi
, stmt
, false);
1325 /* Handle memcpy (x, y, l) where l is strlen (y) + 1. */
1326 si
= get_strinfo (idx
);
1327 if (si
== NULL
|| si
->length
== NULL_TREE
)
1329 if (TREE_CODE (len
) != SSA_NAME
)
1331 def_stmt
= SSA_NAME_DEF_STMT (len
);
1332 if (!is_gimple_assign (def_stmt
)
1333 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1334 || gimple_assign_rhs1 (def_stmt
) != si
->length
1335 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1341 /* Handle memcpy (x, "abcd", 5) or
1342 memcpy (x, "abc\0uvw", 7). */
1343 if (!tree_fits_uhwi_p (len
)
1344 || tree_to_uhwi (len
) <= (unsigned HOST_WIDE_INT
) ~idx
)
1348 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
1349 adjust_last_stmt (olddsi
, stmt
, false);
1353 didx
= new_stridx (dst
);
1358 newlen
= si
->length
;
1360 newlen
= build_int_cst (size_type_node
, ~idx
);
1364 dsi
= unshare_strinfo (olddsi
);
1365 oldlen
= olddsi
->length
;
1366 dsi
->length
= newlen
;
1367 /* Break the chain, so adjust_related_strinfo on later pointers in
1368 the chain won't adjust this one anymore. */
1371 dsi
->endptr
= NULL_TREE
;
1375 dsi
= new_strinfo (dst
, didx
, newlen
);
1376 set_strinfo (didx
, dsi
);
1377 find_equal_ptrs (dst
, didx
);
1379 dsi
->writable
= true;
1380 dsi
->dont_invalidate
= true;
1383 tree adj
= NULL_TREE
;
1384 location_t loc
= gimple_location (stmt
);
1385 if (oldlen
== NULL_TREE
)
1387 else if (integer_zerop (oldlen
))
1389 else if (TREE_CODE (oldlen
) == INTEGER_CST
1390 || TREE_CODE (dsi
->length
) == INTEGER_CST
)
1391 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1392 TREE_TYPE (dsi
->length
), dsi
->length
,
1393 fold_convert_loc (loc
, TREE_TYPE (dsi
->length
),
1395 if (adj
!= NULL_TREE
)
1396 adjust_related_strinfos (loc
, dsi
, adj
);
1400 /* memcpy src may not overlap dst, so src doesn't need to be
1401 invalidated either. */
1403 si
->dont_invalidate
= true;
1405 lhs
= gimple_call_lhs (stmt
);
1408 case BUILT_IN_MEMCPY
:
1409 case BUILT_IN_MEMCPY_CHK
:
1410 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1411 laststmt
.stmt
= stmt
;
1412 laststmt
.len
= dsi
->length
;
1413 laststmt
.stridx
= dsi
->idx
;
1415 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1417 case BUILT_IN_MEMPCPY
:
1418 case BUILT_IN_MEMPCPY_CHK
:
1425 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
1426 If strlen of the second argument is known, strlen of the first argument
1427 is increased by the length of the second argument. Furthermore, attempt
1428 to convert it to memcpy/strcpy if the length of the first argument
1432 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1435 tree src
, dst
, srclen
, dstlen
, len
, lhs
, args
, type
, fn
, objsz
, endptr
;
1437 gimple stmt
= gsi_stmt (*gsi
);
1441 src
= gimple_call_arg (stmt
, 1);
1442 dst
= gimple_call_arg (stmt
, 0);
1443 lhs
= gimple_call_lhs (stmt
);
1445 didx
= get_stridx (dst
);
1451 dsi
= get_strinfo (didx
);
1452 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
1454 /* strcat (p, q) can be transformed into
1455 tmp = p + strlen (p); endptr = strpcpy (tmp, q);
1456 with length endptr - p if we need to compute the length
1457 later on. Don't do this transformation if we don't need
1459 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
1463 didx
= new_stridx (dst
);
1469 dsi
= new_strinfo (dst
, didx
, NULL_TREE
);
1470 set_strinfo (didx
, dsi
);
1471 find_equal_ptrs (dst
, didx
);
1475 dsi
= unshare_strinfo (dsi
);
1476 dsi
->length
= NULL_TREE
;
1478 dsi
->endptr
= NULL_TREE
;
1480 dsi
->writable
= true;
1482 dsi
->dont_invalidate
= true;
1489 idx
= get_stridx (src
);
1491 srclen
= build_int_cst (size_type_node
, ~idx
);
1494 si
= get_strinfo (idx
);
1496 srclen
= get_string_length (si
);
1499 loc
= gimple_location (stmt
);
1500 dstlen
= dsi
->length
;
1501 endptr
= dsi
->endptr
;
1503 dsi
= unshare_strinfo (dsi
);
1504 dsi
->endptr
= NULL_TREE
;
1506 dsi
->writable
= true;
1508 if (srclen
!= NULL_TREE
)
1510 dsi
->length
= fold_build2_loc (loc
, PLUS_EXPR
, TREE_TYPE (dsi
->length
),
1511 dsi
->length
, srclen
);
1512 adjust_related_strinfos (loc
, dsi
, srclen
);
1513 dsi
->dont_invalidate
= true;
1518 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1519 dsi
->dont_invalidate
= true;
1523 /* strcat src may not overlap dst, so src doesn't need to be
1524 invalidated either. */
1525 si
->dont_invalidate
= true;
1527 /* For now. Could remove the lhs from the call and add
1528 lhs = dst; afterwards. */
1536 case BUILT_IN_STRCAT
:
1537 if (srclen
!= NULL_TREE
)
1538 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1540 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
1542 case BUILT_IN_STRCAT_CHK
:
1543 if (srclen
!= NULL_TREE
)
1544 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1546 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
1547 objsz
= gimple_call_arg (stmt
, 2);
1553 if (fn
== NULL_TREE
)
1557 if (srclen
!= NULL_TREE
)
1559 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1560 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1562 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1563 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
1564 build_int_cst (type
, 1));
1565 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1569 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
1571 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1572 TREE_TYPE (dst
), unshare_expr (dst
),
1573 fold_convert_loc (loc
, sizetype
,
1574 unshare_expr (dstlen
)));
1575 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
1577 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1579 fprintf (dump_file
, "Optimizing: ");
1580 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1582 if (srclen
!= NULL_TREE
)
1583 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
1584 dst
, src
, len
, objsz
);
1586 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
1590 stmt
= gsi_stmt (*gsi
);
1592 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1594 fprintf (dump_file
, "into: ");
1595 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1597 /* If srclen == NULL, note that current string length can be
1598 computed by transforming this strcpy into stpcpy. */
1599 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
1601 adjust_last_stmt (dsi
, stmt
, true);
1602 if (srclen
!= NULL_TREE
)
1604 laststmt
.stmt
= stmt
;
1605 laststmt
.len
= srclen
;
1606 laststmt
.stridx
= dsi
->idx
;
1609 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1610 fprintf (dump_file
, "not possible.\n");
1613 /* Handle a call to malloc or calloc. */
1616 handle_builtin_malloc (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1618 gimple stmt
= gsi_stmt (*gsi
);
1619 tree lhs
= gimple_call_lhs (stmt
);
1620 gcc_assert (get_stridx (lhs
) == 0);
1621 int idx
= new_stridx (lhs
);
1622 tree length
= NULL_TREE
;
1623 if (bcode
== BUILT_IN_CALLOC
)
1624 length
= build_int_cst (size_type_node
, 0);
1625 strinfo si
= new_strinfo (lhs
, idx
, length
);
1626 if (bcode
== BUILT_IN_CALLOC
)
1628 set_strinfo (idx
, si
);
1629 si
->writable
= true;
1631 si
->dont_invalidate
= true;
1634 /* Handle a call to memset.
1635 After a call to calloc, memset(,0,) is unnecessary.
1636 memset(malloc(n),0,n) is calloc(n,1). */
1639 handle_builtin_memset (gimple_stmt_iterator
*gsi
)
1641 gimple stmt2
= gsi_stmt (*gsi
);
1642 if (!integer_zerop (gimple_call_arg (stmt2
, 1)))
1644 tree ptr
= gimple_call_arg (stmt2
, 0);
1645 int idx1
= get_stridx (ptr
);
1648 strinfo si1
= get_strinfo (idx1
);
1651 gimple stmt1
= si1
->stmt
;
1652 if (!stmt1
|| !is_gimple_call (stmt1
))
1654 tree callee1
= gimple_call_fndecl (stmt1
);
1655 if (!gimple_call_builtin_p (stmt1
, BUILT_IN_NORMAL
))
1657 enum built_in_function code1
= DECL_FUNCTION_CODE (callee1
);
1658 tree size
= gimple_call_arg (stmt2
, 2);
1659 if (code1
== BUILT_IN_CALLOC
)
1660 /* Not touching stmt1 */ ;
1661 else if (code1
== BUILT_IN_MALLOC
1662 && operand_equal_p (gimple_call_arg (stmt1
, 0), size
, 0))
1664 gimple_stmt_iterator gsi1
= gsi_for_stmt (stmt1
);
1665 update_gimple_call (&gsi1
, builtin_decl_implicit (BUILT_IN_CALLOC
), 2,
1666 size
, build_one_cst (size_type_node
));
1667 si1
->length
= build_int_cst (size_type_node
, 0);
1668 si1
->stmt
= gsi_stmt (gsi1
);
1672 tree lhs
= gimple_call_lhs (stmt2
);
1673 unlink_stmt_vdef (stmt2
);
1676 gimple assign
= gimple_build_assign (lhs
, ptr
);
1677 gsi_replace (gsi
, assign
, false);
1681 gsi_remove (gsi
, true);
1682 release_defs (stmt2
);
1688 /* Handle a POINTER_PLUS_EXPR statement.
1689 For p = "abcd" + 2; compute associated length, or if
1690 p = q + off is pointing to a '\0' character of a string, call
1691 zero_length_string on it. */
1694 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
1696 gimple stmt
= gsi_stmt (*gsi
);
1697 tree lhs
= gimple_assign_lhs (stmt
), off
;
1698 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
1706 tree off
= gimple_assign_rhs2 (stmt
);
1707 if (tree_fits_uhwi_p (off
)
1708 && tree_to_uhwi (off
) <= (unsigned HOST_WIDE_INT
) ~idx
)
1709 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
1710 = ~(~idx
- (int) tree_to_uhwi (off
));
1714 si
= get_strinfo (idx
);
1715 if (si
== NULL
|| si
->length
== NULL_TREE
)
1718 off
= gimple_assign_rhs2 (stmt
);
1720 if (operand_equal_p (si
->length
, off
, 0))
1721 zsi
= zero_length_string (lhs
, si
);
1722 else if (TREE_CODE (off
) == SSA_NAME
)
1724 gimple def_stmt
= SSA_NAME_DEF_STMT (off
);
1725 if (gimple_assign_single_p (def_stmt
)
1726 && operand_equal_p (si
->length
, gimple_assign_rhs1 (def_stmt
), 0))
1727 zsi
= zero_length_string (lhs
, si
);
1730 && si
->endptr
!= NULL_TREE
1731 && si
->endptr
!= lhs
1732 && TREE_CODE (si
->endptr
) == SSA_NAME
)
1734 enum tree_code rhs_code
1735 = useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (si
->endptr
))
1736 ? SSA_NAME
: NOP_EXPR
;
1737 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, si
->endptr
, NULL_TREE
);
1738 gcc_assert (gsi_stmt (*gsi
) == stmt
);
1743 /* Handle a single character store. */
1746 handle_char_store (gimple_stmt_iterator
*gsi
)
1750 gimple stmt
= gsi_stmt (*gsi
);
1751 tree ssaname
= NULL_TREE
, lhs
= gimple_assign_lhs (stmt
);
1753 if (TREE_CODE (lhs
) == MEM_REF
1754 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
)
1756 if (integer_zerop (TREE_OPERAND (lhs
, 1)))
1758 ssaname
= TREE_OPERAND (lhs
, 0);
1759 idx
= get_stridx (ssaname
);
1763 idx
= get_addr_stridx (lhs
);
1767 si
= get_strinfo (idx
);
1768 if (si
!= NULL
&& si
->length
!= NULL_TREE
&& integer_zerop (si
->length
))
1770 if (initializer_zerop (gimple_assign_rhs1 (stmt
)))
1772 /* When storing '\0', the store can be removed
1773 if we know it has been stored in the current function. */
1774 if (!stmt_could_throw_p (stmt
) && si
->writable
)
1776 unlink_stmt_vdef (stmt
);
1777 release_defs (stmt
);
1778 gsi_remove (gsi
, true);
1783 si
->writable
= true;
1789 /* Otherwise this statement overwrites the '\0' with
1790 something, if the previous stmt was a memcpy,
1791 its length may be decreased. */
1792 adjust_last_stmt (si
, stmt
, false);
1794 else if (si
!= NULL
&& integer_zerop (gimple_assign_rhs1 (stmt
)))
1796 si
= unshare_strinfo (si
);
1797 si
->length
= build_int_cst (size_type_node
, 0);
1803 si
->writable
= true;
1804 if (ssaname
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
1805 si
->endptr
= ssaname
;
1806 si
->dont_invalidate
= true;
1808 /* If si->length is non-zero constant, we aren't overwriting '\0',
1809 and if we aren't storing '\0', we know that the length of the
1810 string and any other zero terminated string in memory remains
1811 the same. In that case we move to the next gimple statement and
1812 return to signal the caller that it shouldn't invalidate anything.
1814 This is benefical for cases like:
1819 strcpy (p, "foobar");
1820 size_t len = strlen (p); // This can be optimized into 6
1821 size_t len2 = strlen (q); // This has to be computed
1823 size_t len3 = strlen (p); // This can be optimized into 6
1824 size_t len4 = strlen (q); // This can be optimized into len2
1825 bar (len, len2, len3, len4);
1828 else if (si
!= NULL
&& si
->length
!= NULL_TREE
1829 && TREE_CODE (si
->length
) == INTEGER_CST
1830 && integer_nonzerop (gimple_assign_rhs1 (stmt
)))
1836 else if (idx
== 0 && initializer_zerop (gimple_assign_rhs1 (stmt
)))
1840 si
= zero_length_string (ssaname
, NULL
);
1842 si
->dont_invalidate
= true;
1846 int idx
= new_addr_stridx (lhs
);
1849 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
1850 build_int_cst (size_type_node
, 0));
1851 set_strinfo (idx
, si
);
1852 si
->dont_invalidate
= true;
1856 si
->writable
= true;
1859 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == STRING_CST
1860 && ssaname
== NULL_TREE
1861 && TREE_CODE (TREE_TYPE (lhs
)) == ARRAY_TYPE
)
1863 size_t l
= strlen (TREE_STRING_POINTER (gimple_assign_rhs1 (stmt
)));
1864 HOST_WIDE_INT a
= int_size_in_bytes (TREE_TYPE (lhs
));
1865 if (a
> 0 && (unsigned HOST_WIDE_INT
) a
> l
)
1867 int idx
= new_addr_stridx (lhs
);
1870 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
1871 build_int_cst (size_type_node
, l
));
1872 set_strinfo (idx
, si
);
1873 si
->dont_invalidate
= true;
1878 if (si
!= NULL
&& initializer_zerop (gimple_assign_rhs1 (stmt
)))
1880 /* Allow adjust_last_stmt to remove it if the stored '\0'
1881 is immediately overwritten. */
1882 laststmt
.stmt
= stmt
;
1883 laststmt
.len
= build_int_cst (size_type_node
, 1);
1884 laststmt
.stridx
= si
->idx
;
1889 /* Attempt to optimize a single statement at *GSI using string length
1893 strlen_optimize_stmt (gimple_stmt_iterator
*gsi
)
1895 gimple stmt
= gsi_stmt (*gsi
);
1897 if (is_gimple_call (stmt
))
1899 tree callee
= gimple_call_fndecl (stmt
);
1900 if (gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
1901 switch (DECL_FUNCTION_CODE (callee
))
1903 case BUILT_IN_STRLEN
:
1904 handle_builtin_strlen (gsi
);
1906 case BUILT_IN_STRCHR
:
1907 handle_builtin_strchr (gsi
);
1909 case BUILT_IN_STRCPY
:
1910 case BUILT_IN_STRCPY_CHK
:
1911 case BUILT_IN_STPCPY
:
1912 case BUILT_IN_STPCPY_CHK
:
1913 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee
), gsi
);
1915 case BUILT_IN_MEMCPY
:
1916 case BUILT_IN_MEMCPY_CHK
:
1917 case BUILT_IN_MEMPCPY
:
1918 case BUILT_IN_MEMPCPY_CHK
:
1919 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee
), gsi
);
1921 case BUILT_IN_STRCAT
:
1922 case BUILT_IN_STRCAT_CHK
:
1923 handle_builtin_strcat (DECL_FUNCTION_CODE (callee
), gsi
);
1925 case BUILT_IN_MALLOC
:
1926 case BUILT_IN_CALLOC
:
1927 handle_builtin_malloc (DECL_FUNCTION_CODE (callee
), gsi
);
1929 case BUILT_IN_MEMSET
:
1930 if (!handle_builtin_memset (gsi
))
1937 else if (is_gimple_assign (stmt
))
1939 tree lhs
= gimple_assign_lhs (stmt
);
1941 if (TREE_CODE (lhs
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (lhs
)))
1943 if (gimple_assign_single_p (stmt
)
1944 || (gimple_assign_cast_p (stmt
)
1945 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
1947 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
1948 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = idx
;
1950 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
1951 handle_pointer_plus (gsi
);
1953 else if (TREE_CODE (lhs
) != SSA_NAME
&& !TREE_SIDE_EFFECTS (lhs
))
1955 tree type
= TREE_TYPE (lhs
);
1956 if (TREE_CODE (type
) == ARRAY_TYPE
)
1957 type
= TREE_TYPE (type
);
1958 if (TREE_CODE (type
) == INTEGER_TYPE
1959 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
1960 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
))
1962 if (! handle_char_store (gsi
))
1968 if (gimple_vdef (stmt
))
1969 maybe_invalidate (stmt
);
1973 /* Recursively call maybe_invalidate on stmts that might be executed
1974 in between dombb and current bb and that contain a vdef. Stop when
1975 *count stmts are inspected, or if the whole strinfo vector has
1976 been invalidated. */
1979 do_invalidate (basic_block dombb
, gimple phi
, bitmap visited
, int *count
)
1981 unsigned int i
, n
= gimple_phi_num_args (phi
);
1983 for (i
= 0; i
< n
; i
++)
1985 tree vuse
= gimple_phi_arg_def (phi
, i
);
1986 gimple stmt
= SSA_NAME_DEF_STMT (vuse
);
1987 basic_block bb
= gimple_bb (stmt
);
1990 || !bitmap_set_bit (visited
, bb
->index
)
1991 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
1995 if (gimple_code (stmt
) == GIMPLE_PHI
)
1997 do_invalidate (dombb
, stmt
, visited
, count
);
2004 if (!maybe_invalidate (stmt
))
2009 vuse
= gimple_vuse (stmt
);
2010 stmt
= SSA_NAME_DEF_STMT (vuse
);
2011 if (gimple_bb (stmt
) != bb
)
2013 bb
= gimple_bb (stmt
);
2016 || !bitmap_set_bit (visited
, bb
->index
)
2017 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
2024 class strlen_dom_walker
: public dom_walker
2027 strlen_dom_walker (cdi_direction direction
) : dom_walker (direction
) {}
2029 virtual void before_dom_children (basic_block
);
2030 virtual void after_dom_children (basic_block
);
2033 /* Callback for walk_dominator_tree. Attempt to optimize various
2034 string ops by remembering string lenths pointed by pointer SSA_NAMEs. */
2037 strlen_dom_walker::before_dom_children (basic_block bb
)
2039 gimple_stmt_iterator gsi
;
2040 basic_block dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
2043 stridx_to_strinfo
= NULL
;
2046 stridx_to_strinfo
= ((vec
<strinfo
, va_heap
, vl_embed
> *) dombb
->aux
);
2047 if (stridx_to_strinfo
)
2049 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2051 gimple phi
= gsi_stmt (gsi
);
2052 if (virtual_operand_p (gimple_phi_result (phi
)))
2054 bitmap visited
= BITMAP_ALLOC (NULL
);
2055 int count_vdef
= 100;
2056 do_invalidate (dombb
, phi
, visited
, &count_vdef
);
2057 BITMAP_FREE (visited
);
2058 if (count_vdef
== 0)
2060 /* If there were too many vdefs in between immediate
2061 dominator and current bb, invalidate everything.
2062 If stridx_to_strinfo has been unshared, we need
2063 to free it, otherwise just set it to NULL. */
2064 if (!strinfo_shared ())
2070 vec_safe_iterate (stridx_to_strinfo
, i
, &si
);
2074 (*stridx_to_strinfo
)[i
] = NULL
;
2078 stridx_to_strinfo
= NULL
;
2086 /* If all PHI arguments have the same string index, the PHI result
2088 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2090 gimple phi
= gsi_stmt (gsi
);
2091 tree result
= gimple_phi_result (phi
);
2092 if (!virtual_operand_p (result
) && POINTER_TYPE_P (TREE_TYPE (result
)))
2094 int idx
= get_stridx (gimple_phi_arg_def (phi
, 0));
2097 unsigned int i
, n
= gimple_phi_num_args (phi
);
2098 for (i
= 1; i
< n
; i
++)
2099 if (idx
!= get_stridx (gimple_phi_arg_def (phi
, i
)))
2102 ssa_ver_to_stridx
[SSA_NAME_VERSION (result
)] = idx
;
2107 /* Attempt to optimize individual statements. */
2108 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2109 if (strlen_optimize_stmt (&gsi
))
2112 bb
->aux
= stridx_to_strinfo
;
2113 if (vec_safe_length (stridx_to_strinfo
) && !strinfo_shared ())
2114 (*stridx_to_strinfo
)[0] = (strinfo
) bb
;
2117 /* Callback for walk_dominator_tree. Free strinfo vector if it is
2118 owned by the current bb, clear bb->aux. */
2121 strlen_dom_walker::after_dom_children (basic_block bb
)
2125 stridx_to_strinfo
= ((vec
<strinfo
, va_heap
, vl_embed
> *) bb
->aux
);
2126 if (vec_safe_length (stridx_to_strinfo
)
2127 && (*stridx_to_strinfo
)[0] == (strinfo
) bb
)
2132 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
2134 vec_free (stridx_to_strinfo
);
2140 /* Main entry point. */
2144 const pass_data pass_data_strlen
=
2146 GIMPLE_PASS
, /* type */
2147 "strlen", /* name */
2148 OPTGROUP_NONE
, /* optinfo_flags */
2149 TV_TREE_STRLEN
, /* tv_id */
2150 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2151 0, /* properties_provided */
2152 0, /* properties_destroyed */
2153 0, /* todo_flags_start */
2154 0, /* todo_flags_finish */
2157 class pass_strlen
: public gimple_opt_pass
2160 pass_strlen (gcc::context
*ctxt
)
2161 : gimple_opt_pass (pass_data_strlen
, ctxt
)
2164 /* opt_pass methods: */
2165 virtual bool gate (function
*) { return flag_optimize_strlen
!= 0; }
2166 virtual unsigned int execute (function
*);
2168 }; // class pass_strlen
2171 pass_strlen::execute (function
*fun
)
2173 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
2175 strinfo_pool
= create_alloc_pool ("strinfo_struct pool",
2176 sizeof (struct strinfo_struct
), 64);
2178 calculate_dominance_info (CDI_DOMINATORS
);
2180 /* String length optimization is implemented as a walk of the dominator
2181 tree and a forward walk of statements within each block. */
2182 strlen_dom_walker (CDI_DOMINATORS
).walk (fun
->cfg
->x_entry_block_ptr
);
2184 ssa_ver_to_stridx
.release ();
2185 free_alloc_pool (strinfo_pool
);
2186 if (decl_to_stridxlist_htab
)
2188 obstack_free (&stridx_obstack
, NULL
);
2189 delete decl_to_stridxlist_htab
;
2190 decl_to_stridxlist_htab
= NULL
;
2192 laststmt
.stmt
= NULL
;
2193 laststmt
.len
= NULL_TREE
;
2194 laststmt
.stridx
= 0;
2202 make_pass_strlen (gcc::context
*ctxt
)
2204 return new pass_strlen (ctxt
);