1 /* String length optimization
2 Copyright (C) 2011-2019 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"
28 #include "alloc-pool.h"
29 #include "tree-pass.h"
32 #include "gimple-pretty-print.h"
33 #include "gimple-ssa-warn-restrict.h"
34 #include "fold-const.h"
35 #include "stor-layout.h"
36 #include "gimple-fold.h"
39 #include "gimple-iterator.h"
40 #include "gimplify-me.h"
45 #include "tree-ssa-alias.h"
46 #include "tree-ssa-propagate.h"
47 #include "tree-ssa-strlen.h"
49 #include "tree-hash-traits.h"
50 #include "tree-object-size.h"
53 #include "diagnostic-core.h"
54 #include "diagnostic.h"
59 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
60 is an index into strinfo vector, negative value stands for
61 string length of a string literal (~strlen). */
62 static vec
<int> ssa_ver_to_stridx
;
64 /* Number of currently active string indexes plus one. */
65 static int max_stridx
;
67 /* String information record. */
70 /* Number of leading characters that are known to be nonzero. This is
71 also the length of the string if FULL_STRING_P.
73 The values in a list of related string pointers must be consistent;
74 that is, if strinfo B comes X bytes after strinfo A, it must be
75 the case that A->nonzero_chars == X + B->nonzero_chars. */
77 /* Any of the corresponding pointers for querying alias oracle. */
79 /* This is used for two things:
81 - To record the statement that should be used for delayed length
82 computations. We maintain the invariant that all related strinfos
83 have delayed lengths or none do.
85 - To record the malloc or calloc call that produced this result. */
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
;
123 /* True if the string is known to be nul-terminated after NONZERO_CHARS
124 characters. False is useful when detecting strings that are built
125 up via successive memcpys. */
129 /* Pool for allocating strinfo_struct entries. */
130 static object_allocator
<strinfo
> strinfo_pool ("strinfo pool");
132 /* Vector mapping positive string indexes to strinfo, for the
133 current basic block. The first pointer in the vector is special,
134 it is either NULL, meaning the vector isn't shared, or it is
135 a basic block pointer to the owner basic_block if shared.
136 If some other bb wants to modify the vector, the vector needs
137 to be unshared first, and only the owner bb is supposed to free it. */
138 static vec
<strinfo
*, va_heap
, vl_embed
> *stridx_to_strinfo
;
140 /* One OFFSET->IDX mapping. */
143 struct stridxlist
*next
;
144 HOST_WIDE_INT offset
;
148 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
149 struct decl_stridxlist_map
151 struct tree_map_base base
;
152 struct stridxlist list
;
155 /* Hash table for mapping decls to a chained list of offset -> idx
157 static hash_map
<tree_decl_hash
, stridxlist
> *decl_to_stridxlist_htab
;
159 /* Hash table mapping strlen (or strnlen with constant bound and return
160 smaller than bound) calls to stridx instances describing
161 the calls' arguments. Non-null only when warn_stringop_truncation
163 typedef std::pair
<int, location_t
> stridx_strlenloc
;
164 static hash_map
<tree
, stridx_strlenloc
> *strlen_to_stridx
;
166 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
167 static struct obstack stridx_obstack
;
169 /* Last memcpy statement if it could be adjusted if the trailing
170 '\0' written is immediately overwritten, or
171 *x = '\0' store that could be removed if it is immediately overwritten. */
172 struct laststmt_struct
179 static int get_stridx_plus_constant (strinfo
*, unsigned HOST_WIDE_INT
, tree
);
180 static void handle_builtin_stxncpy (built_in_function
, gimple_stmt_iterator
*);
184 - 1 if SI is known to start with more than OFF nonzero characters.
186 - 0 if SI is known to start with OFF nonzero characters,
187 but is not known to start with more.
189 - -1 if SI might not start with OFF nonzero characters. */
192 compare_nonzero_chars (strinfo
*si
, unsigned HOST_WIDE_INT off
)
194 if (si
->nonzero_chars
195 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
196 return compare_tree_int (si
->nonzero_chars
, off
);
201 /* Return true if SI is known to be a zero-length string. */
204 zero_length_string_p (strinfo
*si
)
206 return si
->full_string_p
&& integer_zerop (si
->nonzero_chars
);
209 /* Return strinfo vector entry IDX. */
211 static inline strinfo
*
212 get_strinfo (int idx
)
214 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
216 return (*stridx_to_strinfo
)[idx
];
219 /* Get the next strinfo in the chain after SI, or null if none. */
221 static inline strinfo
*
222 get_next_strinfo (strinfo
*si
)
226 strinfo
*nextsi
= get_strinfo (si
->next
);
227 if (nextsi
== NULL
|| nextsi
->first
!= si
->first
|| nextsi
->prev
!= si
->idx
)
232 /* Helper function for get_stridx. Return the strinfo index of the address
233 of EXP, which is available in PTR if nonnull. If OFFSET_OUT, it is
234 OK to return the index for some X <= &EXP and store &EXP - X in
238 get_addr_stridx (tree exp
, tree ptr
, unsigned HOST_WIDE_INT
*offset_out
)
241 struct stridxlist
*list
, *last
= NULL
;
244 if (!decl_to_stridxlist_htab
)
248 base
= get_addr_base_and_unit_offset (exp
, &poff
);
249 if (base
== NULL
|| !DECL_P (base
) || !poff
.is_constant (&off
))
252 list
= decl_to_stridxlist_htab
->get (base
);
258 if (list
->offset
== off
)
264 if (list
->offset
> off
)
271 if ((offset_out
|| ptr
) && last
&& last
->idx
> 0)
273 unsigned HOST_WIDE_INT rel_off
274 = (unsigned HOST_WIDE_INT
) off
- last
->offset
;
275 strinfo
*si
= get_strinfo (last
->idx
);
276 if (si
&& compare_nonzero_chars (si
, rel_off
) >= 0)
280 *offset_out
= rel_off
;
284 return get_stridx_plus_constant (si
, rel_off
, ptr
);
290 /* Return string index for EXP. */
293 get_stridx (tree exp
)
295 if (TREE_CODE (exp
) == SSA_NAME
)
297 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)])
298 return ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)];
301 HOST_WIDE_INT off
= 0;
302 for (i
= 0; i
< 5; i
++)
304 gimple
*def_stmt
= SSA_NAME_DEF_STMT (e
);
305 if (!is_gimple_assign (def_stmt
)
306 || gimple_assign_rhs_code (def_stmt
) != POINTER_PLUS_EXPR
)
308 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
309 tree rhs2
= gimple_assign_rhs2 (def_stmt
);
310 if (TREE_CODE (rhs1
) != SSA_NAME
311 || !tree_fits_shwi_p (rhs2
))
313 HOST_WIDE_INT this_off
= tree_to_shwi (rhs2
);
316 off
= (unsigned HOST_WIDE_INT
) off
+ this_off
;
319 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)])
322 = get_strinfo (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)]);
323 if (si
&& compare_nonzero_chars (si
, off
) >= 0)
324 return get_stridx_plus_constant (si
, off
, exp
);
331 if (TREE_CODE (exp
) == ADDR_EXPR
)
333 int idx
= get_addr_stridx (TREE_OPERAND (exp
, 0), exp
, NULL
);
338 const char *p
= c_getstr (exp
);
340 return ~(int) strlen (p
);
345 /* Return true if strinfo vector is shared with the immediate dominator. */
348 strinfo_shared (void)
350 return vec_safe_length (stridx_to_strinfo
)
351 && (*stridx_to_strinfo
)[0] != NULL
;
354 /* Unshare strinfo vector that is shared with the immediate dominator. */
357 unshare_strinfo_vec (void)
362 gcc_assert (strinfo_shared ());
363 stridx_to_strinfo
= vec_safe_copy (stridx_to_strinfo
);
364 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
367 (*stridx_to_strinfo
)[0] = NULL
;
370 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
371 Return a pointer to the location where the string index can
372 be stored (if 0) or is stored, or NULL if this can't be tracked. */
375 addr_stridxptr (tree exp
)
380 tree base
= get_addr_base_and_unit_offset (exp
, &poff
);
381 if (base
== NULL_TREE
|| !DECL_P (base
) || !poff
.is_constant (&off
))
384 if (!decl_to_stridxlist_htab
)
386 decl_to_stridxlist_htab
387 = new hash_map
<tree_decl_hash
, stridxlist
> (64);
388 gcc_obstack_init (&stridx_obstack
);
392 stridxlist
*list
= &decl_to_stridxlist_htab
->get_or_insert (base
, &existed
);
396 stridxlist
*before
= NULL
;
397 for (i
= 0; i
< 32; i
++)
399 if (list
->offset
== off
)
401 if (list
->offset
> off
&& before
== NULL
)
403 if (list
->next
== NULL
)
412 before
= XOBNEW (&stridx_obstack
, struct stridxlist
);
419 list
->next
= XOBNEW (&stridx_obstack
, struct stridxlist
);
429 /* Create a new string index, or return 0 if reached limit. */
432 new_stridx (tree exp
)
435 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
437 if (TREE_CODE (exp
) == SSA_NAME
)
439 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
))
442 ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)] = idx
;
445 if (TREE_CODE (exp
) == ADDR_EXPR
)
447 int *pidx
= addr_stridxptr (TREE_OPERAND (exp
, 0));
450 gcc_assert (*pidx
== 0);
451 *pidx
= max_stridx
++;
458 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
461 new_addr_stridx (tree exp
)
464 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
466 pidx
= addr_stridxptr (exp
);
469 gcc_assert (*pidx
== 0);
470 *pidx
= max_stridx
++;
476 /* Create a new strinfo. */
479 new_strinfo (tree ptr
, int idx
, tree nonzero_chars
, bool full_string_p
)
481 strinfo
*si
= strinfo_pool
.allocate ();
482 si
->nonzero_chars
= nonzero_chars
;
485 si
->endptr
= NULL_TREE
;
491 si
->writable
= false;
492 si
->dont_invalidate
= false;
493 si
->full_string_p
= full_string_p
;
497 /* Decrease strinfo refcount and free it if not referenced anymore. */
500 free_strinfo (strinfo
*si
)
502 if (si
&& --si
->refcount
== 0)
503 strinfo_pool
.remove (si
);
506 /* Set strinfo in the vector entry IDX to SI. */
509 set_strinfo (int idx
, strinfo
*si
)
511 if (vec_safe_length (stridx_to_strinfo
) && (*stridx_to_strinfo
)[0])
512 unshare_strinfo_vec ();
513 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
514 vec_safe_grow_cleared (stridx_to_strinfo
, idx
+ 1);
515 (*stridx_to_strinfo
)[idx
] = si
;
518 /* Return the first strinfo in the related strinfo chain
519 if all strinfos in between belong to the chain, otherwise NULL. */
522 verify_related_strinfos (strinfo
*origsi
)
524 strinfo
*si
= origsi
, *psi
;
526 if (origsi
->first
== 0)
528 for (; si
->prev
; si
= psi
)
530 if (si
->first
!= origsi
->first
)
532 psi
= get_strinfo (si
->prev
);
535 if (psi
->next
!= si
->idx
)
538 if (si
->idx
!= si
->first
)
543 /* Set SI's endptr to ENDPTR and compute its length based on SI->ptr.
544 Use LOC for folding. */
547 set_endptr_and_length (location_t loc
, strinfo
*si
, tree endptr
)
551 tree start_as_size
= fold_convert_loc (loc
, size_type_node
, si
->ptr
);
552 tree end_as_size
= fold_convert_loc (loc
, size_type_node
, endptr
);
553 si
->nonzero_chars
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
554 end_as_size
, start_as_size
);
555 si
->full_string_p
= true;
558 /* Return string length, or NULL if it can't be computed. */
561 get_string_length (strinfo
*si
)
563 if (si
->nonzero_chars
)
564 return si
->full_string_p
? si
->nonzero_chars
: NULL
;
568 gimple
*stmt
= si
->stmt
, *lenstmt
;
569 tree callee
, lhs
, fn
, tem
;
571 gimple_stmt_iterator gsi
;
573 gcc_assert (is_gimple_call (stmt
));
574 callee
= gimple_call_fndecl (stmt
);
575 gcc_assert (callee
&& fndecl_built_in_p (callee
, BUILT_IN_NORMAL
));
576 lhs
= gimple_call_lhs (stmt
);
577 /* unshare_strinfo is intentionally not called here. The (delayed)
578 transformation of strcpy or strcat into stpcpy is done at the place
579 of the former strcpy/strcat call and so can affect all the strinfos
580 with the same stmt. If they were unshared before and transformation
581 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
582 just compute the right length. */
583 switch (DECL_FUNCTION_CODE (callee
))
585 case BUILT_IN_STRCAT
:
586 case BUILT_IN_STRCAT_CHK
:
587 gsi
= gsi_for_stmt (stmt
);
588 fn
= builtin_decl_implicit (BUILT_IN_STRLEN
);
589 gcc_assert (lhs
== NULL_TREE
);
590 tem
= unshare_expr (gimple_call_arg (stmt
, 0));
591 lenstmt
= gimple_build_call (fn
, 1, tem
);
592 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), lenstmt
);
593 gimple_call_set_lhs (lenstmt
, lhs
);
594 gimple_set_vuse (lenstmt
, gimple_vuse (stmt
));
595 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
596 tem
= gimple_call_arg (stmt
, 0);
597 if (!ptrofftype_p (TREE_TYPE (lhs
)))
599 lhs
= convert_to_ptrofftype (lhs
);
600 lhs
= force_gimple_operand_gsi (&gsi
, lhs
, true, NULL_TREE
,
601 true, GSI_SAME_STMT
);
603 lenstmt
= gimple_build_assign
604 (make_ssa_name (TREE_TYPE (gimple_call_arg (stmt
, 0))),
605 POINTER_PLUS_EXPR
,tem
, lhs
);
606 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
607 gimple_call_set_arg (stmt
, 0, gimple_assign_lhs (lenstmt
));
610 case BUILT_IN_STRCPY
:
611 case BUILT_IN_STRCPY_CHK
:
612 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY
));
613 if (gimple_call_num_args (stmt
) == 2)
614 fn
= builtin_decl_implicit (BUILT_IN_STPCPY
);
616 fn
= builtin_decl_explicit (BUILT_IN_STPCPY_CHK
);
617 gcc_assert (lhs
== NULL_TREE
);
618 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
620 fprintf (dump_file
, "Optimizing: ");
621 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
623 gimple_call_set_fndecl (stmt
, fn
);
624 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), stmt
);
625 gimple_call_set_lhs (stmt
, lhs
);
627 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
629 fprintf (dump_file
, "into: ");
630 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
633 case BUILT_IN_STPCPY
:
634 case BUILT_IN_STPCPY_CHK
:
635 gcc_assert (lhs
!= NULL_TREE
);
636 loc
= gimple_location (stmt
);
637 set_endptr_and_length (loc
, si
, lhs
);
638 for (strinfo
*chainsi
= verify_related_strinfos (si
);
640 chainsi
= get_next_strinfo (chainsi
))
641 if (chainsi
->nonzero_chars
== NULL
)
642 set_endptr_and_length (loc
, chainsi
, lhs
);
644 case BUILT_IN_MALLOC
:
646 /* BUILT_IN_CALLOC always has si->nonzero_chars set. */
653 return si
->nonzero_chars
;
656 /* Invalidate string length information for strings whose length
657 might change due to stores in stmt. */
660 maybe_invalidate (gimple
*stmt
)
664 bool nonempty
= false;
666 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
669 if (!si
->dont_invalidate
)
672 /* Do not use si->nonzero_chars. */
673 ao_ref_init_from_ptr_and_size (&r
, si
->ptr
, NULL_TREE
);
674 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
676 set_strinfo (i
, NULL
);
681 si
->dont_invalidate
= false;
687 /* Unshare strinfo record SI, if it has refcount > 1 or
688 if stridx_to_strinfo vector is shared with some other
692 unshare_strinfo (strinfo
*si
)
696 if (si
->refcount
== 1 && !strinfo_shared ())
699 nsi
= new_strinfo (si
->ptr
, si
->idx
, si
->nonzero_chars
, si
->full_string_p
);
700 nsi
->stmt
= si
->stmt
;
701 nsi
->endptr
= si
->endptr
;
702 nsi
->first
= si
->first
;
703 nsi
->prev
= si
->prev
;
704 nsi
->next
= si
->next
;
705 nsi
->writable
= si
->writable
;
706 set_strinfo (si
->idx
, nsi
);
711 /* Attempt to create a new strinfo for BASESI + OFF, or find existing
712 strinfo if there is any. Return it's idx, or 0 if no strinfo has
716 get_stridx_plus_constant (strinfo
*basesi
, unsigned HOST_WIDE_INT off
,
719 if (TREE_CODE (ptr
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
722 if (compare_nonzero_chars (basesi
, off
) < 0
723 || !tree_fits_uhwi_p (basesi
->nonzero_chars
))
726 unsigned HOST_WIDE_INT nonzero_chars
727 = tree_to_uhwi (basesi
->nonzero_chars
) - off
;
728 strinfo
*si
= basesi
, *chainsi
;
729 if (si
->first
|| si
->prev
|| si
->next
)
730 si
= verify_related_strinfos (basesi
);
732 || si
->nonzero_chars
== NULL_TREE
733 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
736 if (TREE_CODE (ptr
) == SSA_NAME
737 && ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
738 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
740 gcc_checking_assert (compare_tree_int (si
->nonzero_chars
, off
) != -1);
741 for (chainsi
= si
; chainsi
->next
; chainsi
= si
)
743 si
= get_next_strinfo (chainsi
);
745 || si
->nonzero_chars
== NULL_TREE
746 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
748 int r
= compare_tree_int (si
->nonzero_chars
, nonzero_chars
);
753 if (TREE_CODE (ptr
) == SSA_NAME
)
754 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = si
->idx
;
757 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
758 if (pidx
!= NULL
&& *pidx
== 0)
767 int idx
= new_stridx (ptr
);
770 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, nonzero_chars
),
771 basesi
->full_string_p
);
772 set_strinfo (idx
, si
);
773 if (strinfo
*nextsi
= get_strinfo (chainsi
->next
))
775 nextsi
= unshare_strinfo (nextsi
);
776 si
->next
= nextsi
->idx
;
779 chainsi
= unshare_strinfo (chainsi
);
780 if (chainsi
->first
== 0)
781 chainsi
->first
= chainsi
->idx
;
783 if (chainsi
->endptr
== NULL_TREE
&& zero_length_string_p (si
))
784 chainsi
->endptr
= ptr
;
785 si
->endptr
= chainsi
->endptr
;
786 si
->prev
= chainsi
->idx
;
787 si
->first
= chainsi
->first
;
788 si
->writable
= chainsi
->writable
;
792 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
793 to a zero-length string and if possible chain it to a related strinfo
794 chain whose part is or might be CHAINSI. */
797 zero_length_string (tree ptr
, strinfo
*chainsi
)
801 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
802 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
803 gcc_checking_assert (TREE_CODE (ptr
) == SSA_NAME
804 && ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] == 0);
806 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
810 si
= verify_related_strinfos (chainsi
);
815 /* We shouldn't mix delayed and non-delayed lengths. */
816 gcc_assert (si
->full_string_p
);
817 if (si
->endptr
== NULL_TREE
)
819 si
= unshare_strinfo (si
);
823 si
= get_next_strinfo (si
);
826 if (zero_length_string_p (chainsi
))
830 chainsi
= unshare_strinfo (chainsi
);
833 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = chainsi
->idx
;
839 /* We shouldn't mix delayed and non-delayed lengths. */
840 gcc_assert (chainsi
->full_string_p
);
841 if (chainsi
->first
|| chainsi
->prev
|| chainsi
->next
)
843 chainsi
= unshare_strinfo (chainsi
);
850 idx
= new_stridx (ptr
);
853 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, 0), true);
854 set_strinfo (idx
, si
);
858 chainsi
= unshare_strinfo (chainsi
);
859 if (chainsi
->first
== 0)
860 chainsi
->first
= chainsi
->idx
;
862 if (chainsi
->endptr
== NULL_TREE
)
863 chainsi
->endptr
= ptr
;
864 si
->prev
= chainsi
->idx
;
865 si
->first
= chainsi
->first
;
866 si
->writable
= chainsi
->writable
;
871 /* For strinfo ORIGSI whose length has been just updated, adjust other
872 related strinfos so that they match the new ORIGSI. This involves:
874 - adding ADJ to the nonzero_chars fields
875 - copying full_string_p from the new ORIGSI. */
878 adjust_related_strinfos (location_t loc
, strinfo
*origsi
, tree adj
)
880 strinfo
*si
= verify_related_strinfos (origsi
);
893 si
= unshare_strinfo (si
);
894 /* We shouldn't see delayed lengths here; the caller must have
895 calculated the old length in order to calculate the
897 gcc_assert (si
->nonzero_chars
);
898 tem
= fold_convert_loc (loc
, TREE_TYPE (si
->nonzero_chars
), adj
);
899 si
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
900 TREE_TYPE (si
->nonzero_chars
),
901 si
->nonzero_chars
, tem
);
902 si
->full_string_p
= origsi
->full_string_p
;
904 si
->endptr
= NULL_TREE
;
905 si
->dont_invalidate
= true;
907 nsi
= get_next_strinfo (si
);
914 /* Find if there are other SSA_NAME pointers equal to PTR
915 for which we don't track their string lengths yet. If so, use
919 find_equal_ptrs (tree ptr
, int idx
)
921 if (TREE_CODE (ptr
) != SSA_NAME
)
925 gimple
*stmt
= SSA_NAME_DEF_STMT (ptr
);
926 if (!is_gimple_assign (stmt
))
928 ptr
= gimple_assign_rhs1 (stmt
);
929 switch (gimple_assign_rhs_code (stmt
))
934 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)))
936 if (TREE_CODE (ptr
) == SSA_NAME
)
938 if (TREE_CODE (ptr
) != ADDR_EXPR
)
943 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
944 if (pidx
!= NULL
&& *pidx
== 0)
952 /* We might find an endptr created in this pass. Grow the
953 vector in that case. */
954 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
955 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
957 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] != 0)
959 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = idx
;
963 /* Return true if STMT is a call to a builtin function with the right
964 arguments and attributes that should be considered for optimization
968 valid_builtin_call (gimple
*stmt
)
970 if (!gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
973 tree callee
= gimple_call_fndecl (stmt
);
974 switch (DECL_FUNCTION_CODE (callee
))
976 case BUILT_IN_MEMCMP
:
977 case BUILT_IN_MEMCMP_EQ
:
978 case BUILT_IN_STRCHR
:
979 case BUILT_IN_STRLEN
:
980 /* The above functions should be pure. Punt if they aren't. */
981 if (gimple_vdef (stmt
) || gimple_vuse (stmt
) == NULL_TREE
)
985 case BUILT_IN_CALLOC
:
986 case BUILT_IN_MALLOC
:
987 case BUILT_IN_MEMCPY
:
988 case BUILT_IN_MEMCPY_CHK
:
989 case BUILT_IN_MEMPCPY
:
990 case BUILT_IN_MEMPCPY_CHK
:
991 case BUILT_IN_MEMSET
:
992 case BUILT_IN_STPCPY
:
993 case BUILT_IN_STPCPY_CHK
:
994 case BUILT_IN_STRCAT
:
995 case BUILT_IN_STRCAT_CHK
:
996 case BUILT_IN_STRCPY
:
997 case BUILT_IN_STRCPY_CHK
:
998 /* The above functions should be neither const nor pure. Punt if they
1000 if (gimple_vdef (stmt
) == NULL_TREE
|| gimple_vuse (stmt
) == NULL_TREE
)
1011 /* If the last .MEM setter statement before STMT is
1012 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
1013 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
1014 just memcpy (x, y, strlen (y)). SI must be the zero length
1018 adjust_last_stmt (strinfo
*si
, gimple
*stmt
, bool is_strcat
)
1020 tree vuse
, callee
, len
;
1021 struct laststmt_struct last
= laststmt
;
1022 strinfo
*lastsi
, *firstsi
;
1023 unsigned len_arg_no
= 2;
1025 laststmt
.stmt
= NULL
;
1026 laststmt
.len
= NULL_TREE
;
1027 laststmt
.stridx
= 0;
1029 if (last
.stmt
== NULL
)
1032 vuse
= gimple_vuse (stmt
);
1033 if (vuse
== NULL_TREE
1034 || SSA_NAME_DEF_STMT (vuse
) != last
.stmt
1035 || !has_single_use (vuse
))
1038 gcc_assert (last
.stridx
> 0);
1039 lastsi
= get_strinfo (last
.stridx
);
1045 if (lastsi
->first
== 0 || lastsi
->first
!= si
->first
)
1048 firstsi
= verify_related_strinfos (si
);
1049 if (firstsi
== NULL
)
1051 while (firstsi
!= lastsi
)
1053 firstsi
= get_next_strinfo (firstsi
);
1054 if (firstsi
== NULL
)
1059 if (!is_strcat
&& !zero_length_string_p (si
))
1062 if (is_gimple_assign (last
.stmt
))
1064 gimple_stmt_iterator gsi
;
1066 if (!integer_zerop (gimple_assign_rhs1 (last
.stmt
)))
1068 if (stmt_could_throw_p (cfun
, last
.stmt
))
1070 gsi
= gsi_for_stmt (last
.stmt
);
1071 unlink_stmt_vdef (last
.stmt
);
1072 release_defs (last
.stmt
);
1073 gsi_remove (&gsi
, true);
1077 if (!valid_builtin_call (last
.stmt
))
1080 callee
= gimple_call_fndecl (last
.stmt
);
1081 switch (DECL_FUNCTION_CODE (callee
))
1083 case BUILT_IN_MEMCPY
:
1084 case BUILT_IN_MEMCPY_CHK
:
1090 len
= gimple_call_arg (last
.stmt
, len_arg_no
);
1091 if (tree_fits_uhwi_p (len
))
1093 if (!tree_fits_uhwi_p (last
.len
)
1094 || integer_zerop (len
)
1095 || tree_to_uhwi (len
) != tree_to_uhwi (last
.len
) + 1)
1097 /* Don't adjust the length if it is divisible by 4, it is more efficient
1098 to store the extra '\0' in that case. */
1099 if ((tree_to_uhwi (len
) & 3) == 0)
1102 /* Don't fold away an out of bounds access, as this defeats proper
1104 tree dst
= gimple_call_arg (last
.stmt
, 0);
1105 tree size
= compute_objsize (dst
, 0);
1106 if (size
&& tree_int_cst_lt (size
, len
))
1109 else if (TREE_CODE (len
) == SSA_NAME
)
1111 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1112 if (!is_gimple_assign (def_stmt
)
1113 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1114 || gimple_assign_rhs1 (def_stmt
) != last
.len
1115 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1121 gimple_call_set_arg (last
.stmt
, len_arg_no
, last
.len
);
1122 update_stmt (last
.stmt
);
1125 /* For an LHS that is an SSA_NAME that is the result of a strlen()
1126 call, or when BOUND is non-null, of a strnlen() call, set LHS
1127 range info to [0, min (MAX, BOUND)] when the range includes more
1128 than one value and return LHS. Otherwise, when the range
1129 [MIN, MAX] is such that MIN == MAX, return the tree representation
1130 of (MIN). The latter allows callers to fold suitable strnlen() calls
1134 set_strlen_range (tree lhs
, wide_int max
, tree bound
/* = NULL_TREE */)
1136 if (TREE_CODE (lhs
) != SSA_NAME
1137 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
1140 wide_int min
= wi::zero (max
.get_precision ());
1144 /* For strnlen, adjust MIN and MAX as necessary. If the bound
1145 is less than the size of the array set MAX to it. It it's
1146 greater than MAX and MAX is non-zero bump MAX down to account
1147 for the necessary terminating nul. Otherwise leave it alone. */
1148 if (TREE_CODE (bound
) == INTEGER_CST
)
1150 wide_int wibnd
= wi::to_wide (bound
);
1151 int cmp
= wi::cmpu (wibnd
, max
);
1154 else if (cmp
&& wi::ne_p (max
, min
))
1157 else if (TREE_CODE (bound
) == SSA_NAME
)
1159 wide_int minbound
, maxbound
;
1160 value_range_kind rng
= get_range_info (bound
, &minbound
, &maxbound
);
1161 if (rng
== VR_RANGE
)
1163 /* For a bound in a known range, adjust the range determined
1164 above as necessary. For a bound in some anti-range or
1165 in an unknown range, use the range determined by callers. */
1166 if (wi::ltu_p (minbound
, min
))
1168 if (wi::ltu_p (maxbound
, max
))
1175 return wide_int_to_tree (size_type_node
, min
);
1177 set_range_info (lhs
, VR_RANGE
, min
, max
);
1181 /* For an LHS that is an SSA_NAME and for strlen() or strnlen() argument
1182 SRC, set LHS range info to [0, min (N, BOUND)] if SRC refers to
1183 a character array A[N] with unknown length bounded by N, and for
1184 strnlen(), by min (N, BOUND). */
1187 maybe_set_strlen_range (tree lhs
, tree src
, tree bound
)
1189 if (TREE_CODE (lhs
) != SSA_NAME
1190 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
1193 if (TREE_CODE (src
) == SSA_NAME
)
1195 gimple
*def
= SSA_NAME_DEF_STMT (src
);
1196 if (is_gimple_assign (def
)
1197 && gimple_assign_rhs_code (def
) == ADDR_EXPR
)
1198 src
= gimple_assign_rhs1 (def
);
1201 /* The longest string is PTRDIFF_MAX - 1 bytes including the final
1202 NUL so that the difference between a pointer to just past it and
1203 one to its beginning is positive. */
1204 wide_int max
= wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node
)) - 2;
1206 if (TREE_CODE (src
) == ADDR_EXPR
)
1208 /* The last array member of a struct can be bigger than its size
1209 suggests if it's treated as a poor-man's flexible array member. */
1210 src
= TREE_OPERAND (src
, 0);
1211 if (TREE_CODE (src
) != MEM_REF
1212 && !array_at_struct_end_p (src
))
1214 tree type
= TREE_TYPE (src
);
1215 tree size
= TYPE_SIZE_UNIT (type
);
1217 && TREE_CODE (size
) == INTEGER_CST
1218 && !integer_zerop (size
))
1220 /* Even though such uses of strlen would be undefined,
1221 avoid relying on arrays of arrays in case some genius
1222 decides to call strlen on an unterminated array element
1223 that's followed by a terminated one. Likewise, avoid
1224 assuming that a struct array member is necessarily
1225 nul-terminated (the nul may be in the member that
1226 follows). In those cases, assume that the length
1227 of the string stored in such an array is bounded
1228 by the size of the enclosing object if one can be
1230 tree base
= get_base_address (src
);
1233 if (tree size
= DECL_SIZE_UNIT (base
))
1235 && TREE_CODE (size
) == INTEGER_CST
1236 && TREE_CODE (TREE_TYPE (base
)) != POINTER_TYPE
)
1237 max
= wi::to_wide (size
);
1241 /* For strlen() the upper bound above is equal to
1242 the longest string that can be stored in the array
1243 (i.e., it accounts for the terminating nul. For
1244 strnlen() bump up the maximum by one since the array
1245 need not be nul-terminated. */
1246 if (!bound
&& max
!= 0)
1251 return set_strlen_range (lhs
, max
, bound
);
1254 /* Handle a strlen call. If strlen of the argument is known, replace
1255 the strlen call with the known value, otherwise remember that strlen
1256 of the argument is stored in the lhs SSA_NAME. */
1259 handle_builtin_strlen (gimple_stmt_iterator
*gsi
)
1261 gimple
*stmt
= gsi_stmt (*gsi
);
1262 tree lhs
= gimple_call_lhs (stmt
);
1264 if (lhs
== NULL_TREE
)
1267 location_t loc
= gimple_location (stmt
);
1268 tree callee
= gimple_call_fndecl (stmt
);
1269 tree src
= gimple_call_arg (stmt
, 0);
1270 tree bound
= (DECL_FUNCTION_CODE (callee
) == BUILT_IN_STRNLEN
1271 ? gimple_call_arg (stmt
, 1) : NULL_TREE
);
1272 int idx
= get_stridx (src
);
1273 if (idx
|| (bound
&& integer_zerop (bound
)))
1279 rhs
= build_int_cst (TREE_TYPE (lhs
), ~idx
);
1285 si
= get_strinfo (idx
);
1288 rhs
= get_string_length (si
);
1289 /* For strnlen, if bound is constant, even if si is not known
1290 to be zero terminated, if we know at least bound bytes are
1291 not zero, the return value will be bound. */
1292 if (rhs
== NULL_TREE
1293 && bound
!= NULL_TREE
1294 && TREE_CODE (bound
) == INTEGER_CST
1295 && si
->nonzero_chars
!= NULL_TREE
1296 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
1297 && tree_int_cst_le (bound
, si
->nonzero_chars
))
1301 if (rhs
!= NULL_TREE
)
1303 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1305 fprintf (dump_file
, "Optimizing: ");
1306 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1308 rhs
= unshare_expr (rhs
);
1309 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
1310 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1313 rhs
= fold_build2_loc (loc
, MIN_EXPR
, TREE_TYPE (rhs
), rhs
, bound
);
1315 if (!update_call_from_tree (gsi
, rhs
))
1316 gimplify_and_update_call_from_tree (gsi
, rhs
);
1317 stmt
= gsi_stmt (*gsi
);
1319 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1321 fprintf (dump_file
, "into: ");
1322 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1326 /* Don't update anything for strnlen. */
1327 && bound
== NULL_TREE
1328 && TREE_CODE (si
->nonzero_chars
) != SSA_NAME
1329 && TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
1330 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1332 si
= unshare_strinfo (si
);
1333 si
->nonzero_chars
= lhs
;
1334 gcc_assert (si
->full_string_p
);
1337 if (strlen_to_stridx
1338 && (bound
== NULL_TREE
1339 /* For strnlen record this only if the call is proven
1340 to return the same value as strlen would. */
1341 || (TREE_CODE (bound
) == INTEGER_CST
1342 && TREE_CODE (rhs
) == INTEGER_CST
1343 && tree_int_cst_lt (rhs
, bound
))))
1344 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1349 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1353 idx
= new_stridx (src
);
1356 strinfo
*si
= get_strinfo (idx
);
1359 if (!si
->full_string_p
&& !si
->stmt
)
1361 /* Until now we only had a lower bound on the string length.
1362 Install LHS as the actual length. */
1363 si
= unshare_strinfo (si
);
1364 tree old
= si
->nonzero_chars
;
1365 si
->nonzero_chars
= lhs
;
1366 si
->full_string_p
= true;
1367 if (TREE_CODE (old
) == INTEGER_CST
)
1369 old
= fold_convert_loc (loc
, TREE_TYPE (lhs
), old
);
1370 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1371 TREE_TYPE (lhs
), lhs
, old
);
1372 adjust_related_strinfos (loc
, si
, adj
);
1388 /* Only store the new length information for calls to strlen(),
1389 not for those to strnlen(). */
1390 strinfo
*si
= new_strinfo (src
, idx
, lhs
, true);
1391 set_strinfo (idx
, si
);
1392 find_equal_ptrs (src
, idx
);
1395 /* For SRC that is an array of N elements, set LHS's range
1396 to [0, min (N, BOUND)]. A constant return value means
1397 the range would have consisted of a single value. In
1398 that case, fold the result into the returned constant. */
1399 if (tree ret
= maybe_set_strlen_range (lhs
, src
, bound
))
1400 if (TREE_CODE (ret
) == INTEGER_CST
)
1402 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1404 fprintf (dump_file
, "Optimizing: ");
1405 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1407 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (ret
)))
1408 ret
= fold_convert_loc (loc
, TREE_TYPE (lhs
), ret
);
1409 if (!update_call_from_tree (gsi
, ret
))
1410 gimplify_and_update_call_from_tree (gsi
, ret
);
1411 stmt
= gsi_stmt (*gsi
);
1413 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1415 fprintf (dump_file
, "into: ");
1416 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1420 if (strlen_to_stridx
&& !bound
)
1421 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1425 /* Handle a strchr call. If strlen of the first argument is known, replace
1426 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
1427 that lhs of the call is endptr and strlen of the argument is endptr - x. */
1430 handle_builtin_strchr (gimple_stmt_iterator
*gsi
)
1434 gimple
*stmt
= gsi_stmt (*gsi
);
1435 tree lhs
= gimple_call_lhs (stmt
);
1437 if (lhs
== NULL_TREE
)
1440 if (!integer_zerop (gimple_call_arg (stmt
, 1)))
1443 src
= gimple_call_arg (stmt
, 0);
1444 idx
= get_stridx (src
);
1451 rhs
= build_int_cst (size_type_node
, ~idx
);
1455 si
= get_strinfo (idx
);
1457 rhs
= get_string_length (si
);
1459 if (rhs
!= NULL_TREE
)
1461 location_t loc
= gimple_location (stmt
);
1463 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1465 fprintf (dump_file
, "Optimizing: ");
1466 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1468 if (si
!= NULL
&& si
->endptr
!= NULL_TREE
)
1470 rhs
= unshare_expr (si
->endptr
);
1471 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1473 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1477 rhs
= fold_convert_loc (loc
, sizetype
, unshare_expr (rhs
));
1478 rhs
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1479 TREE_TYPE (src
), src
, rhs
);
1480 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1482 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1484 if (!update_call_from_tree (gsi
, rhs
))
1485 gimplify_and_update_call_from_tree (gsi
, rhs
);
1486 stmt
= gsi_stmt (*gsi
);
1488 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1490 fprintf (dump_file
, "into: ");
1491 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1494 && si
->endptr
== NULL_TREE
1495 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1497 si
= unshare_strinfo (si
);
1500 zero_length_string (lhs
, si
);
1504 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1506 if (TREE_CODE (src
) != SSA_NAME
|| !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src
))
1509 idx
= new_stridx (src
);
1510 else if (get_strinfo (idx
) != NULL
)
1512 zero_length_string (lhs
, NULL
);
1517 location_t loc
= gimple_location (stmt
);
1518 tree lhsu
= fold_convert_loc (loc
, size_type_node
, lhs
);
1519 tree srcu
= fold_convert_loc (loc
, size_type_node
, src
);
1520 tree length
= fold_build2_loc (loc
, MINUS_EXPR
,
1521 size_type_node
, lhsu
, srcu
);
1522 strinfo
*si
= new_strinfo (src
, idx
, length
, true);
1524 set_strinfo (idx
, si
);
1525 find_equal_ptrs (src
, idx
);
1526 zero_length_string (lhs
, si
);
1530 zero_length_string (lhs
, NULL
);
1533 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1534 If strlen of the second argument is known, strlen of the first argument
1535 is the same after this call. Furthermore, attempt to convert it to
1539 handle_builtin_strcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1542 tree src
, dst
, srclen
, len
, lhs
, type
, fn
, oldlen
;
1544 gimple
*stmt
= gsi_stmt (*gsi
);
1545 strinfo
*si
, *dsi
, *olddsi
, *zsi
;
1548 src
= gimple_call_arg (stmt
, 1);
1549 dst
= gimple_call_arg (stmt
, 0);
1550 lhs
= gimple_call_lhs (stmt
);
1551 idx
= get_stridx (src
);
1554 si
= get_strinfo (idx
);
1556 didx
= get_stridx (dst
);
1560 olddsi
= get_strinfo (didx
);
1565 adjust_last_stmt (olddsi
, stmt
, false);
1569 srclen
= get_string_length (si
);
1571 srclen
= build_int_cst (size_type_node
, ~idx
);
1573 loc
= gimple_location (stmt
);
1574 if (srclen
== NULL_TREE
)
1577 case BUILT_IN_STRCPY
:
1578 case BUILT_IN_STRCPY_CHK
:
1579 if (lhs
!= NULL_TREE
|| !builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1582 case BUILT_IN_STPCPY
:
1583 case BUILT_IN_STPCPY_CHK
:
1584 if (lhs
== NULL_TREE
)
1588 tree lhsuint
= fold_convert_loc (loc
, size_type_node
, lhs
);
1589 srclen
= fold_convert_loc (loc
, size_type_node
, dst
);
1590 srclen
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
1600 didx
= new_stridx (dst
);
1606 oldlen
= olddsi
->nonzero_chars
;
1607 dsi
= unshare_strinfo (olddsi
);
1608 dsi
->nonzero_chars
= srclen
;
1609 dsi
->full_string_p
= (srclen
!= NULL_TREE
);
1610 /* Break the chain, so adjust_related_strinfo on later pointers in
1611 the chain won't adjust this one anymore. */
1614 dsi
->endptr
= NULL_TREE
;
1618 dsi
= new_strinfo (dst
, didx
, srclen
, srclen
!= NULL_TREE
);
1619 set_strinfo (didx
, dsi
);
1620 find_equal_ptrs (dst
, didx
);
1622 dsi
->writable
= true;
1623 dsi
->dont_invalidate
= true;
1625 if (dsi
->nonzero_chars
== NULL_TREE
)
1629 /* If string length of src is unknown, use delayed length
1630 computation. If string lenth of dst will be needed, it
1631 can be computed by transforming this strcpy call into
1632 stpcpy and subtracting dst from the return value. */
1634 /* Look for earlier strings whose length could be determined if
1635 this strcpy is turned into an stpcpy. */
1637 if (dsi
->prev
!= 0 && (chainsi
= verify_related_strinfos (dsi
)) != NULL
)
1639 for (; chainsi
&& chainsi
!= dsi
; chainsi
= get_strinfo (chainsi
->next
))
1641 /* When setting a stmt for delayed length computation
1642 prevent all strinfos through dsi from being
1644 chainsi
= unshare_strinfo (chainsi
);
1645 chainsi
->stmt
= stmt
;
1646 chainsi
->nonzero_chars
= NULL_TREE
;
1647 chainsi
->full_string_p
= false;
1648 chainsi
->endptr
= NULL_TREE
;
1649 chainsi
->dont_invalidate
= true;
1654 /* Try to detect overlap before returning. This catches cases
1655 like strcpy (d, d + n) where n is non-constant whose range
1656 is such that (n <= strlen (d) holds).
1658 OLDDSI->NONZERO_chars may have been reset by this point with
1659 oldlen holding it original value. */
1660 if (olddsi
&& oldlen
)
1662 /* Add 1 for the terminating NUL. */
1663 tree type
= TREE_TYPE (oldlen
);
1664 oldlen
= fold_build2 (PLUS_EXPR
, type
, oldlen
,
1665 build_int_cst (type
, 1));
1666 check_bounds_or_overlap (stmt
, olddsi
->ptr
, src
, oldlen
, NULL_TREE
);
1674 tree adj
= NULL_TREE
;
1675 if (oldlen
== NULL_TREE
)
1677 else if (integer_zerop (oldlen
))
1679 else if (TREE_CODE (oldlen
) == INTEGER_CST
1680 || TREE_CODE (srclen
) == INTEGER_CST
)
1681 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1682 TREE_TYPE (srclen
), srclen
,
1683 fold_convert_loc (loc
, TREE_TYPE (srclen
),
1685 if (adj
!= NULL_TREE
)
1686 adjust_related_strinfos (loc
, dsi
, adj
);
1690 /* strcpy src may not overlap dst, so src doesn't need to be
1691 invalidated either. */
1693 si
->dont_invalidate
= true;
1699 case BUILT_IN_STRCPY
:
1700 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1702 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1704 case BUILT_IN_STRCPY_CHK
:
1705 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1707 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1709 case BUILT_IN_STPCPY
:
1710 /* This would need adjustment of the lhs (subtract one),
1711 or detection that the trailing '\0' doesn't need to be
1712 written, if it will be immediately overwritten.
1713 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1717 zsi
= zero_length_string (lhs
, dsi
);
1720 case BUILT_IN_STPCPY_CHK
:
1721 /* This would need adjustment of the lhs (subtract one),
1722 or detection that the trailing '\0' doesn't need to be
1723 written, if it will be immediately overwritten.
1724 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1728 zsi
= zero_length_string (lhs
, dsi
);
1735 zsi
->dont_invalidate
= true;
1739 tree args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1740 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1743 type
= size_type_node
;
1745 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1746 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
, build_int_cst (type
, 1));
1748 /* Set the no-warning bit on the transformed statement? */
1749 bool set_no_warning
= false;
1751 if (const strinfo
*chksi
= olddsi
? olddsi
: dsi
)
1753 && check_bounds_or_overlap (stmt
, chksi
->ptr
, si
->ptr
, NULL_TREE
, len
))
1755 gimple_set_no_warning (stmt
, true);
1756 set_no_warning
= true;
1759 if (fn
== NULL_TREE
)
1762 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1764 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1766 fprintf (dump_file
, "Optimizing: ");
1767 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1769 if (gimple_call_num_args (stmt
) == 2)
1770 success
= update_gimple_call (gsi
, fn
, 3, dst
, src
, len
);
1772 success
= update_gimple_call (gsi
, fn
, 4, dst
, src
, len
,
1773 gimple_call_arg (stmt
, 2));
1776 stmt
= gsi_stmt (*gsi
);
1778 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1780 fprintf (dump_file
, "into: ");
1781 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1783 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1784 laststmt
.stmt
= stmt
;
1785 laststmt
.len
= srclen
;
1786 laststmt
.stridx
= dsi
->idx
;
1788 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1789 fprintf (dump_file
, "not possible.\n");
1792 gimple_set_no_warning (stmt
, true);
1795 /* Check the size argument to the built-in forms of stpncpy and strncpy
1796 for out-of-bounds offsets or overlapping access, and to see if the
1797 size argument is derived from a call to strlen() on the source argument,
1798 and if so, issue an appropriate warning. */
1801 handle_builtin_strncat (built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1803 /* Same as stxncpy(). */
1804 handle_builtin_stxncpy (bcode
, gsi
);
1807 /* Return true if LEN depends on a call to strlen(SRC) in an interesting
1808 way. LEN can either be an integer expression, or a pointer (to char).
1809 When it is the latter (such as in recursive calls to self) is is
1810 assumed to be the argument in some call to strlen() whose relationship
1811 to SRC is being ascertained. */
1814 is_strlen_related_p (tree src
, tree len
)
1816 if (TREE_CODE (TREE_TYPE (len
)) == POINTER_TYPE
1817 && operand_equal_p (src
, len
, 0))
1820 if (TREE_CODE (len
) != SSA_NAME
)
1823 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1827 if (is_gimple_call (def_stmt
))
1829 tree func
= gimple_call_fndecl (def_stmt
);
1830 if (!valid_builtin_call (def_stmt
)
1831 || DECL_FUNCTION_CODE (func
) != BUILT_IN_STRLEN
)
1834 tree arg
= gimple_call_arg (def_stmt
, 0);
1835 return is_strlen_related_p (src
, arg
);
1838 if (!is_gimple_assign (def_stmt
))
1841 tree_code code
= gimple_assign_rhs_code (def_stmt
);
1842 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1843 tree rhstype
= TREE_TYPE (rhs1
);
1845 if ((TREE_CODE (rhstype
) == POINTER_TYPE
&& code
== POINTER_PLUS_EXPR
)
1846 || (INTEGRAL_TYPE_P (rhstype
)
1847 && (code
== BIT_AND_EXPR
1848 || code
== NOP_EXPR
)))
1850 /* Pointer plus (an integer), and truncation are considered among
1851 the (potentially) related expressions to strlen. */
1852 return is_strlen_related_p (src
, rhs1
);
1855 if (tree rhs2
= gimple_assign_rhs2 (def_stmt
))
1857 /* Integer subtraction is considered strlen-related when both
1858 arguments are integers and second one is strlen-related. */
1859 rhstype
= TREE_TYPE (rhs2
);
1860 if (INTEGRAL_TYPE_P (rhstype
) && code
== MINUS_EXPR
)
1861 return is_strlen_related_p (src
, rhs2
);
1867 /* Called by handle_builtin_stxncpy and by gimple_fold_builtin_strncpy
1869 Check to see if the specified bound is a) equal to the size of
1870 the destination DST and if so, b) if it's immediately followed by
1871 DST[CNT - 1] = '\0'. If a) holds and b) does not, warn. Otherwise,
1872 do nothing. Return true if diagnostic has been issued.
1874 The purpose is to diagnose calls to strncpy and stpncpy that do
1875 not nul-terminate the copy while allowing for the idiom where
1876 such a call is immediately followed by setting the last element
1879 strncpy (a, s, sizeof a);
1880 a[sizeof a - 1] = '\0';
1884 maybe_diag_stxncpy_trunc (gimple_stmt_iterator gsi
, tree src
, tree cnt
)
1886 gimple
*stmt
= gsi_stmt (gsi
);
1887 if (gimple_no_warning_p (stmt
))
1890 wide_int cntrange
[2];
1892 if (TREE_CODE (cnt
) == INTEGER_CST
)
1893 cntrange
[0] = cntrange
[1] = wi::to_wide (cnt
);
1894 else if (TREE_CODE (cnt
) == SSA_NAME
)
1896 enum value_range_kind rng
= get_range_info (cnt
, cntrange
, cntrange
+ 1);
1897 if (rng
== VR_RANGE
)
1899 else if (rng
== VR_ANTI_RANGE
)
1901 wide_int maxobjsize
= wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node
));
1903 if (wi::ltu_p (cntrange
[1], maxobjsize
))
1905 cntrange
[0] = cntrange
[1] + 1;
1906 cntrange
[1] = maxobjsize
;
1910 cntrange
[1] = cntrange
[0] - 1;
1911 cntrange
[0] = wi::zero (TYPE_PRECISION (TREE_TYPE (cnt
)));
1920 /* Negative value is the constant string length. If it's less than
1921 the lower bound there is no truncation. Avoid calling get_stridx()
1922 when ssa_ver_to_stridx is empty. That implies the caller isn't
1923 running under the control of this pass and ssa_ver_to_stridx hasn't
1924 been created yet. */
1925 int sidx
= ssa_ver_to_stridx
.length () ? get_stridx (src
) : 0;
1926 if (sidx
< 0 && wi::gtu_p (cntrange
[0], ~sidx
))
1929 tree dst
= gimple_call_arg (stmt
, 0);
1931 if (TREE_CODE (dstdecl
) == ADDR_EXPR
)
1932 dstdecl
= TREE_OPERAND (dstdecl
, 0);
1934 tree ref
= NULL_TREE
;
1938 /* If the source is a non-string return early to avoid warning
1939 for possible truncation (if the truncation is certain SIDX
1941 tree srcdecl
= gimple_call_arg (stmt
, 1);
1942 if (TREE_CODE (srcdecl
) == ADDR_EXPR
)
1943 srcdecl
= TREE_OPERAND (srcdecl
, 0);
1944 if (get_attr_nonstring_decl (srcdecl
, &ref
))
1948 /* Likewise, if the destination refers to a an array/pointer declared
1949 nonstring return early. */
1950 if (get_attr_nonstring_decl (dstdecl
, &ref
))
1953 /* Look for dst[i] = '\0'; after the stxncpy() call and if found
1954 avoid the truncation warning. */
1955 gsi_next_nondebug (&gsi
);
1956 gimple
*next_stmt
= gsi_stmt (gsi
);
1959 /* When there is no statement in the same basic block check
1960 the immediate successor block. */
1961 if (basic_block bb
= gimple_bb (stmt
))
1963 if (single_succ_p (bb
))
1965 /* For simplicity, ignore blocks with multiple outgoing
1966 edges for now and only consider successor blocks along
1968 edge e
= EDGE_SUCC (bb
, 0);
1969 if (!(e
->flags
& EDGE_ABNORMAL
))
1971 gsi
= gsi_start_bb (e
->dest
);
1972 next_stmt
= gsi_stmt (gsi
);
1973 if (next_stmt
&& is_gimple_debug (next_stmt
))
1975 gsi_next_nondebug (&gsi
);
1976 next_stmt
= gsi_stmt (gsi
);
1983 if (next_stmt
&& is_gimple_assign (next_stmt
))
1985 tree lhs
= gimple_assign_lhs (next_stmt
);
1986 tree_code code
= TREE_CODE (lhs
);
1987 if (code
== ARRAY_REF
|| code
== MEM_REF
)
1988 lhs
= TREE_OPERAND (lhs
, 0);
1990 tree func
= gimple_call_fndecl (stmt
);
1991 if (DECL_FUNCTION_CODE (func
) == BUILT_IN_STPNCPY
)
1993 tree ret
= gimple_call_lhs (stmt
);
1994 if (ret
&& operand_equal_p (ret
, lhs
, 0))
1998 /* Determine the base address and offset of the reference,
1999 ignoring the innermost array index. */
2000 if (TREE_CODE (ref
) == ARRAY_REF
)
2001 ref
= TREE_OPERAND (ref
, 0);
2004 tree dstbase
= get_addr_base_and_unit_offset (ref
, &dstoff
);
2007 tree lhsbase
= get_addr_base_and_unit_offset (lhs
, &lhsoff
);
2010 && known_eq (dstoff
, lhsoff
)
2011 && operand_equal_p (dstbase
, lhsbase
, 0))
2015 int prec
= TYPE_PRECISION (TREE_TYPE (cnt
));
2016 wide_int lenrange
[2];
2017 if (strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
)
2019 lenrange
[0] = (sisrc
->nonzero_chars
2020 && TREE_CODE (sisrc
->nonzero_chars
) == INTEGER_CST
2021 ? wi::to_wide (sisrc
->nonzero_chars
)
2023 lenrange
[1] = lenrange
[0];
2026 lenrange
[0] = lenrange
[1] = wi::shwi (~sidx
, prec
);
2029 c_strlen_data lendata
= { };
2030 get_range_strlen (src
, &lendata
, /* eltsize = */1);
2031 if (TREE_CODE (lendata
.minlen
) == INTEGER_CST
2032 && TREE_CODE (lendata
.maxbound
) == INTEGER_CST
)
2034 /* When LENDATA.MAXLEN is unknown, reset LENDATA.MINLEN
2035 which stores the length of the shortest known string. */
2036 if (integer_all_onesp (lendata
.maxlen
))
2037 lenrange
[0] = wi::shwi (0, prec
);
2039 lenrange
[0] = wi::to_wide (lendata
.minlen
, prec
);
2040 lenrange
[1] = wi::to_wide (lendata
.maxbound
, prec
);
2044 lenrange
[0] = wi::shwi (0, prec
);
2045 lenrange
[1] = wi::shwi (-1, prec
);
2049 location_t callloc
= gimple_nonartificial_location (stmt
);
2050 callloc
= expansion_point_location_if_in_system_header (callloc
);
2052 tree func
= gimple_call_fndecl (stmt
);
2054 if (lenrange
[0] != 0 || !wi::neg_p (lenrange
[1]))
2056 /* If the longest source string is shorter than the lower bound
2057 of the specified count the copy is definitely nul-terminated. */
2058 if (wi::ltu_p (lenrange
[1], cntrange
[0]))
2061 if (wi::neg_p (lenrange
[1]))
2063 /* The length of one of the strings is unknown but at least
2064 one has non-zero length and that length is stored in
2065 LENRANGE[1]. Swap the bounds to force a "may be truncated"
2067 lenrange
[1] = lenrange
[0];
2068 lenrange
[0] = wi::shwi (0, prec
);
2071 /* Set to true for strncat whose bound is derived from the length
2072 of the destination (the expected usage pattern). */
2073 bool cat_dstlen_bounded
= false;
2074 if (DECL_FUNCTION_CODE (func
) == BUILT_IN_STRNCAT
)
2075 cat_dstlen_bounded
= is_strlen_related_p (dst
, cnt
);
2077 if (lenrange
[0] == cntrange
[1] && cntrange
[0] == cntrange
[1])
2078 return warning_n (callloc
, OPT_Wstringop_truncation
,
2079 cntrange
[0].to_uhwi (),
2080 "%G%qD output truncated before terminating "
2081 "nul copying %E byte from a string of the "
2083 "%G%qD output truncated before terminating nul "
2084 "copying %E bytes from a string of the same "
2087 else if (!cat_dstlen_bounded
)
2089 if (wi::geu_p (lenrange
[0], cntrange
[1]))
2091 /* The shortest string is longer than the upper bound of
2092 the count so the truncation is certain. */
2093 if (cntrange
[0] == cntrange
[1])
2094 return warning_n (callloc
, OPT_Wstringop_truncation
,
2095 cntrange
[0].to_uhwi (),
2096 "%G%qD output truncated copying %E byte "
2097 "from a string of length %wu",
2098 "%G%qD output truncated copying %E bytes "
2099 "from a string of length %wu",
2100 stmt
, func
, cnt
, lenrange
[0].to_uhwi ());
2102 return warning_at (callloc
, OPT_Wstringop_truncation
,
2103 "%G%qD output truncated copying between %wu "
2104 "and %wu bytes from a string of length %wu",
2105 stmt
, func
, cntrange
[0].to_uhwi (),
2106 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
2108 else if (wi::geu_p (lenrange
[1], cntrange
[1]))
2110 /* The longest string is longer than the upper bound of
2111 the count so the truncation is possible. */
2112 if (cntrange
[0] == cntrange
[1])
2113 return warning_n (callloc
, OPT_Wstringop_truncation
,
2114 cntrange
[0].to_uhwi (),
2115 "%G%qD output may be truncated copying %E "
2116 "byte from a string of length %wu",
2117 "%G%qD output may be truncated copying %E "
2118 "bytes from a string of length %wu",
2119 stmt
, func
, cnt
, lenrange
[1].to_uhwi ());
2121 return warning_at (callloc
, OPT_Wstringop_truncation
,
2122 "%G%qD output may be truncated copying between "
2123 "%wu and %wu bytes from a string of length %wu",
2124 stmt
, func
, cntrange
[0].to_uhwi (),
2125 cntrange
[1].to_uhwi (), lenrange
[1].to_uhwi ());
2129 if (!cat_dstlen_bounded
2130 && cntrange
[0] != cntrange
[1]
2131 && wi::leu_p (cntrange
[0], lenrange
[0])
2132 && wi::leu_p (cntrange
[1], lenrange
[0] + 1))
2134 /* If the source (including the terminating nul) is longer than
2135 the lower bound of the specified count but shorter than the
2136 upper bound the copy may (but need not) be truncated. */
2137 return warning_at (callloc
, OPT_Wstringop_truncation
,
2138 "%G%qD output may be truncated copying between "
2139 "%wu and %wu bytes from a string of length %wu",
2140 stmt
, func
, cntrange
[0].to_uhwi (),
2141 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
2145 if (tree dstsize
= compute_objsize (dst
, 1))
2147 /* The source length is uknown. Try to determine the destination
2148 size and see if it matches the specified bound. If not, bail.
2149 Otherwise go on to see if it should be diagnosed for possible
2154 if (wi::to_wide (dstsize
) != cntrange
[1])
2157 /* Avoid warning for strncpy(a, b, N) calls where the following
2159 N == sizeof a && N == sizeof b */
2160 if (tree srcsize
= compute_objsize (src
, 1))
2161 if (wi::to_wide (srcsize
) == cntrange
[1])
2164 if (cntrange
[0] == cntrange
[1])
2165 return warning_at (callloc
, OPT_Wstringop_truncation
,
2166 "%G%qD specified bound %E equals destination size",
2173 /* Check the arguments to the built-in forms of stpncpy and strncpy for
2174 out-of-bounds offsets or overlapping access, and to see if the size
2175 is derived from calling strlen() on the source argument, and if so,
2176 issue the appropriate warning. */
2179 handle_builtin_stxncpy (built_in_function
, gimple_stmt_iterator
*gsi
)
2181 if (!strlen_to_stridx
)
2184 gimple
*stmt
= gsi_stmt (*gsi
);
2186 tree dst
= gimple_call_arg (stmt
, 0);
2187 tree src
= gimple_call_arg (stmt
, 1);
2188 tree len
= gimple_call_arg (stmt
, 2);
2189 tree dstsize
= NULL_TREE
, srcsize
= NULL_TREE
;
2191 int didx
= get_stridx (dst
);
2192 if (strinfo
*sidst
= didx
> 0 ? get_strinfo (didx
) : NULL
)
2194 /* Compute the size of the destination string including the NUL. */
2195 if (sidst
->nonzero_chars
)
2197 tree type
= TREE_TYPE (sidst
->nonzero_chars
);
2198 dstsize
= fold_build2 (PLUS_EXPR
, type
, sidst
->nonzero_chars
,
2199 build_int_cst (type
, 1));
2204 int sidx
= get_stridx (src
);
2205 strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
;
2208 /* strncat() and strncpy() can modify the source string by writing
2209 over the terminating nul so SISRC->DONT_INVALIDATE must be left
2212 /* Compute the size of the source string including the NUL. */
2213 if (sisrc
->nonzero_chars
)
2215 tree type
= TREE_TYPE (sisrc
->nonzero_chars
);
2216 srcsize
= fold_build2 (PLUS_EXPR
, type
, sisrc
->nonzero_chars
,
2217 build_int_cst (type
, 1));
2223 srcsize
= NULL_TREE
;
2225 if (check_bounds_or_overlap (stmt
, dst
, src
, dstsize
, srcsize
))
2227 gimple_set_no_warning (stmt
, true);
2231 /* If the length argument was computed from strlen(S) for some string
2232 S retrieve the strinfo index for the string (PSS->FIRST) alonng with
2233 the location of the strlen() call (PSS->SECOND). */
2234 stridx_strlenloc
*pss
= strlen_to_stridx
->get (len
);
2235 if (!pss
|| pss
->first
<= 0)
2237 if (maybe_diag_stxncpy_trunc (*gsi
, src
, len
))
2238 gimple_set_no_warning (stmt
, true);
2243 /* Retrieve the strinfo data for the string S that LEN was computed
2244 from as some function F of strlen (S) (i.e., LEN need not be equal
2246 strinfo
*silen
= get_strinfo (pss
->first
);
2248 location_t callloc
= gimple_nonartificial_location (stmt
);
2249 callloc
= expansion_point_location_if_in_system_header (callloc
);
2251 tree func
= gimple_call_fndecl (stmt
);
2253 bool warned
= false;
2255 /* When -Wstringop-truncation is set, try to determine truncation
2256 before diagnosing possible overflow. Truncation is implied by
2257 the LEN argument being equal to strlen(SRC), regardless of
2258 whether its value is known. Otherwise, issue the more generic
2259 -Wstringop-overflow which triggers for LEN arguments that in
2260 any meaningful way depend on strlen(SRC). */
2262 && is_strlen_related_p (src
, len
)
2263 && warning_at (callloc
, OPT_Wstringop_truncation
,
2264 "%G%qD output truncated before terminating nul "
2265 "copying as many bytes from a string as its length",
2268 else if (silen
&& is_strlen_related_p (src
, silen
->ptr
))
2269 warned
= warning_at (callloc
, OPT_Wstringop_overflow_
,
2270 "%G%qD specified bound depends on the length "
2271 "of the source argument",
2275 location_t strlenloc
= pss
->second
;
2276 if (strlenloc
!= UNKNOWN_LOCATION
&& strlenloc
!= callloc
)
2277 inform (strlenloc
, "length computed here");
2281 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
2282 If strlen of the second argument is known and length of the third argument
2283 is that plus one, strlen of the first argument is the same after this
2287 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2290 tree src
, dst
, len
, lhs
, oldlen
, newlen
;
2291 gimple
*stmt
= gsi_stmt (*gsi
);
2292 strinfo
*si
, *dsi
, *olddsi
;
2294 len
= gimple_call_arg (stmt
, 2);
2295 src
= gimple_call_arg (stmt
, 1);
2296 dst
= gimple_call_arg (stmt
, 0);
2297 idx
= get_stridx (src
);
2301 didx
= get_stridx (dst
);
2304 olddsi
= get_strinfo (didx
);
2309 && tree_fits_uhwi_p (len
)
2310 && !integer_zerop (len
))
2311 adjust_last_stmt (olddsi
, stmt
, false);
2318 /* Handle memcpy (x, y, l) where l's relationship with strlen (y)
2320 si
= get_strinfo (idx
);
2321 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
2323 if (TREE_CODE (len
) == INTEGER_CST
2324 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
2326 if (tree_int_cst_le (len
, si
->nonzero_chars
))
2328 /* Copying LEN nonzero characters, where LEN is constant. */
2330 full_string_p
= false;
2334 /* Copying the whole of the analyzed part of SI. */
2335 newlen
= si
->nonzero_chars
;
2336 full_string_p
= si
->full_string_p
;
2341 if (!si
->full_string_p
)
2343 if (TREE_CODE (len
) != SSA_NAME
)
2345 def_stmt
= SSA_NAME_DEF_STMT (len
);
2346 if (!is_gimple_assign (def_stmt
)
2347 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
2348 || gimple_assign_rhs1 (def_stmt
) != si
->nonzero_chars
2349 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
2351 /* Copying variable-length string SI (and no more). */
2352 newlen
= si
->nonzero_chars
;
2353 full_string_p
= true;
2359 /* Handle memcpy (x, "abcd", 5) or
2360 memcpy (x, "abc\0uvw", 7). */
2361 if (!tree_fits_uhwi_p (len
))
2364 unsigned HOST_WIDE_INT clen
= tree_to_uhwi (len
);
2365 unsigned HOST_WIDE_INT nonzero_chars
= ~idx
;
2366 newlen
= build_int_cst (size_type_node
, MIN (nonzero_chars
, clen
));
2367 full_string_p
= clen
> nonzero_chars
;
2372 && olddsi
->nonzero_chars
2373 && TREE_CODE (olddsi
->nonzero_chars
) == INTEGER_CST
2374 && tree_int_cst_le (newlen
, olddsi
->nonzero_chars
))
2376 /* The SRC substring being written strictly overlaps
2377 a subsequence of the existing string OLDDSI. */
2378 newlen
= olddsi
->nonzero_chars
;
2379 full_string_p
= olddsi
->full_string_p
;
2382 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
2383 adjust_last_stmt (olddsi
, stmt
, false);
2387 didx
= new_stridx (dst
);
2394 dsi
= unshare_strinfo (olddsi
);
2395 oldlen
= olddsi
->nonzero_chars
;
2396 dsi
->nonzero_chars
= newlen
;
2397 dsi
->full_string_p
= full_string_p
;
2398 /* Break the chain, so adjust_related_strinfo on later pointers in
2399 the chain won't adjust this one anymore. */
2402 dsi
->endptr
= NULL_TREE
;
2406 dsi
= new_strinfo (dst
, didx
, newlen
, full_string_p
);
2407 set_strinfo (didx
, dsi
);
2408 find_equal_ptrs (dst
, didx
);
2410 dsi
->writable
= true;
2411 dsi
->dont_invalidate
= true;
2414 tree adj
= NULL_TREE
;
2415 location_t loc
= gimple_location (stmt
);
2416 if (oldlen
== NULL_TREE
)
2418 else if (integer_zerop (oldlen
))
2420 else if (TREE_CODE (oldlen
) == INTEGER_CST
2421 || TREE_CODE (newlen
) == INTEGER_CST
)
2422 adj
= fold_build2_loc (loc
, MINUS_EXPR
, TREE_TYPE (newlen
), newlen
,
2423 fold_convert_loc (loc
, TREE_TYPE (newlen
),
2425 if (adj
!= NULL_TREE
)
2426 adjust_related_strinfos (loc
, dsi
, adj
);
2430 /* memcpy src may not overlap dst, so src doesn't need to be
2431 invalidated either. */
2433 si
->dont_invalidate
= true;
2437 lhs
= gimple_call_lhs (stmt
);
2440 case BUILT_IN_MEMCPY
:
2441 case BUILT_IN_MEMCPY_CHK
:
2442 /* Allow adjust_last_stmt to decrease this memcpy's size. */
2443 laststmt
.stmt
= stmt
;
2444 laststmt
.len
= dsi
->nonzero_chars
;
2445 laststmt
.stridx
= dsi
->idx
;
2447 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
2449 case BUILT_IN_MEMPCPY
:
2450 case BUILT_IN_MEMPCPY_CHK
:
2458 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
2459 If strlen of the second argument is known, strlen of the first argument
2460 is increased by the length of the second argument. Furthermore, attempt
2461 to convert it to memcpy/strcpy if the length of the first argument
2465 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2468 tree srclen
, args
, type
, fn
, objsz
, endptr
;
2470 gimple
*stmt
= gsi_stmt (*gsi
);
2472 location_t loc
= gimple_location (stmt
);
2474 tree src
= gimple_call_arg (stmt
, 1);
2475 tree dst
= gimple_call_arg (stmt
, 0);
2477 /* Bail if the source is the same as destination. It will be diagnosed
2479 if (operand_equal_p (src
, dst
, 0))
2482 tree lhs
= gimple_call_lhs (stmt
);
2484 didx
= get_stridx (dst
);
2490 dsi
= get_strinfo (didx
);
2494 idx
= get_stridx (src
);
2496 srclen
= build_int_cst (size_type_node
, ~idx
);
2499 si
= get_strinfo (idx
);
2501 srclen
= get_string_length (si
);
2504 /* Set the no-warning bit on the transformed statement? */
2505 bool set_no_warning
= false;
2507 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
2510 /* The concatenation always involves copying at least one byte
2511 (the terminating nul), even if the source string is empty.
2512 If the source is unknown assume it's one character long and
2513 used that as both sizes. */
2517 tree type
= TREE_TYPE (slen
);
2518 slen
= fold_build2 (PLUS_EXPR
, type
, slen
, build_int_cst (type
, 1));
2521 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2523 if (check_bounds_or_overlap (stmt
, dst
, sptr
, NULL_TREE
, slen
))
2525 gimple_set_no_warning (stmt
, true);
2526 set_no_warning
= true;
2530 /* strcat (p, q) can be transformed into
2531 tmp = p + strlen (p); endptr = stpcpy (tmp, q);
2532 with length endptr - p if we need to compute the length
2533 later on. Don't do this transformation if we don't need
2535 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
2539 didx
= new_stridx (dst
);
2545 dsi
= new_strinfo (dst
, didx
, NULL_TREE
, false);
2546 set_strinfo (didx
, dsi
);
2547 find_equal_ptrs (dst
, didx
);
2551 dsi
= unshare_strinfo (dsi
);
2552 dsi
->nonzero_chars
= NULL_TREE
;
2553 dsi
->full_string_p
= false;
2555 dsi
->endptr
= NULL_TREE
;
2557 dsi
->writable
= true;
2559 dsi
->dont_invalidate
= true;
2564 tree dstlen
= dsi
->nonzero_chars
;
2565 endptr
= dsi
->endptr
;
2567 dsi
= unshare_strinfo (dsi
);
2568 dsi
->endptr
= NULL_TREE
;
2570 dsi
->writable
= true;
2572 if (srclen
!= NULL_TREE
)
2574 dsi
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
2575 TREE_TYPE (dsi
->nonzero_chars
),
2576 dsi
->nonzero_chars
, srclen
);
2577 gcc_assert (dsi
->full_string_p
);
2578 adjust_related_strinfos (loc
, dsi
, srclen
);
2579 dsi
->dont_invalidate
= true;
2583 dsi
->nonzero_chars
= NULL
;
2584 dsi
->full_string_p
= false;
2585 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
2586 dsi
->dont_invalidate
= true;
2590 /* strcat src may not overlap dst, so src doesn't need to be
2591 invalidated either. */
2592 si
->dont_invalidate
= true;
2594 /* For now. Could remove the lhs from the call and add
2595 lhs = dst; afterwards. */
2603 case BUILT_IN_STRCAT
:
2604 if (srclen
!= NULL_TREE
)
2605 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
2607 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
2609 case BUILT_IN_STRCAT_CHK
:
2610 if (srclen
!= NULL_TREE
)
2611 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
2613 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
2614 objsz
= gimple_call_arg (stmt
, 2);
2620 if (fn
== NULL_TREE
)
2625 tree type
= TREE_TYPE (dstlen
);
2627 /* Compute the size of the source sequence, including the nul. */
2628 tree srcsize
= srclen
? srclen
: size_zero_node
;
2629 srcsize
= fold_build2 (PLUS_EXPR
, type
, srcsize
, build_int_cst (type
, 1));
2631 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2633 if (check_bounds_or_overlap (stmt
, dst
, sptr
, dstlen
, srcsize
))
2635 gimple_set_no_warning (stmt
, true);
2636 set_no_warning
= true;
2640 tree len
= NULL_TREE
;
2641 if (srclen
!= NULL_TREE
)
2643 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
2644 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
2646 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
2647 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
2648 build_int_cst (type
, 1));
2649 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
2653 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
2655 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
, TREE_TYPE (dst
), dst
,
2656 fold_convert_loc (loc
, sizetype
,
2657 unshare_expr (dstlen
)));
2658 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
2662 objsz
= fold_build2_loc (loc
, MINUS_EXPR
, TREE_TYPE (objsz
), objsz
,
2663 fold_convert_loc (loc
, TREE_TYPE (objsz
),
2664 unshare_expr (dstlen
)));
2665 objsz
= force_gimple_operand_gsi (gsi
, objsz
, true, NULL_TREE
, true,
2668 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2670 fprintf (dump_file
, "Optimizing: ");
2671 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2673 if (srclen
!= NULL_TREE
)
2674 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
2675 dst
, src
, len
, objsz
);
2677 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
2681 stmt
= gsi_stmt (*gsi
);
2683 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2685 fprintf (dump_file
, "into: ");
2686 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2688 /* If srclen == NULL, note that current string length can be
2689 computed by transforming this strcpy into stpcpy. */
2690 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
2692 adjust_last_stmt (dsi
, stmt
, true);
2693 if (srclen
!= NULL_TREE
)
2695 laststmt
.stmt
= stmt
;
2696 laststmt
.len
= srclen
;
2697 laststmt
.stridx
= dsi
->idx
;
2700 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2701 fprintf (dump_file
, "not possible.\n");
2704 gimple_set_no_warning (stmt
, true);
2707 /* Handle a call to malloc or calloc. */
2710 handle_builtin_malloc (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2712 gimple
*stmt
= gsi_stmt (*gsi
);
2713 tree lhs
= gimple_call_lhs (stmt
);
2714 if (lhs
== NULL_TREE
)
2717 gcc_assert (get_stridx (lhs
) == 0);
2718 int idx
= new_stridx (lhs
);
2719 tree length
= NULL_TREE
;
2720 if (bcode
== BUILT_IN_CALLOC
)
2721 length
= build_int_cst (size_type_node
, 0);
2722 strinfo
*si
= new_strinfo (lhs
, idx
, length
, length
!= NULL_TREE
);
2723 if (bcode
== BUILT_IN_CALLOC
)
2725 set_strinfo (idx
, si
);
2726 si
->writable
= true;
2728 si
->dont_invalidate
= true;
2731 /* Handle a call to memset.
2732 After a call to calloc, memset(,0,) is unnecessary.
2733 memset(malloc(n),0,n) is calloc(n,1).
2734 return true when the call is transfomred, false otherwise. */
2737 handle_builtin_memset (gimple_stmt_iterator
*gsi
)
2739 gimple
*stmt2
= gsi_stmt (*gsi
);
2740 if (!integer_zerop (gimple_call_arg (stmt2
, 1)))
2742 tree ptr
= gimple_call_arg (stmt2
, 0);
2743 int idx1
= get_stridx (ptr
);
2746 strinfo
*si1
= get_strinfo (idx1
);
2749 gimple
*stmt1
= si1
->stmt
;
2750 if (!stmt1
|| !is_gimple_call (stmt1
))
2752 tree callee1
= gimple_call_fndecl (stmt1
);
2753 if (!valid_builtin_call (stmt1
))
2755 enum built_in_function code1
= DECL_FUNCTION_CODE (callee1
);
2756 tree size
= gimple_call_arg (stmt2
, 2);
2757 if (code1
== BUILT_IN_CALLOC
)
2758 /* Not touching stmt1 */ ;
2759 else if (code1
== BUILT_IN_MALLOC
2760 && operand_equal_p (gimple_call_arg (stmt1
, 0), size
, 0))
2762 gimple_stmt_iterator gsi1
= gsi_for_stmt (stmt1
);
2763 update_gimple_call (&gsi1
, builtin_decl_implicit (BUILT_IN_CALLOC
), 2,
2764 size
, build_one_cst (size_type_node
));
2765 si1
->nonzero_chars
= build_int_cst (size_type_node
, 0);
2766 si1
->full_string_p
= true;
2767 si1
->stmt
= gsi_stmt (gsi1
);
2771 tree lhs
= gimple_call_lhs (stmt2
);
2772 unlink_stmt_vdef (stmt2
);
2775 gimple
*assign
= gimple_build_assign (lhs
, ptr
);
2776 gsi_replace (gsi
, assign
, false);
2780 gsi_remove (gsi
, true);
2781 release_defs (stmt2
);
2787 /* Handle a call to memcmp. We try to handle small comparisons by
2788 converting them to load and compare, and replacing the call to memcmp
2789 with a __builtin_memcmp_eq call where possible.
2790 return true when call is transformed, return false otherwise. */
2793 handle_builtin_memcmp (gimple_stmt_iterator
*gsi
)
2795 gcall
*stmt2
= as_a
<gcall
*> (gsi_stmt (*gsi
));
2796 tree res
= gimple_call_lhs (stmt2
);
2797 tree arg1
= gimple_call_arg (stmt2
, 0);
2798 tree arg2
= gimple_call_arg (stmt2
, 1);
2799 tree len
= gimple_call_arg (stmt2
, 2);
2800 unsigned HOST_WIDE_INT leni
;
2801 use_operand_p use_p
;
2802 imm_use_iterator iter
;
2807 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
2809 gimple
*ustmt
= USE_STMT (use_p
);
2811 if (is_gimple_debug (ustmt
))
2813 if (gimple_code (ustmt
) == GIMPLE_ASSIGN
)
2815 gassign
*asgn
= as_a
<gassign
*> (ustmt
);
2816 tree_code code
= gimple_assign_rhs_code (asgn
);
2817 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2818 || !integer_zerop (gimple_assign_rhs2 (asgn
)))
2821 else if (gimple_code (ustmt
) == GIMPLE_COND
)
2823 tree_code code
= gimple_cond_code (ustmt
);
2824 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2825 || !integer_zerop (gimple_cond_rhs (ustmt
)))
2832 if (tree_fits_uhwi_p (len
)
2833 && (leni
= tree_to_uhwi (len
)) <= GET_MODE_SIZE (word_mode
)
2834 && pow2p_hwi (leni
))
2836 leni
*= CHAR_TYPE_SIZE
;
2837 unsigned align1
= get_pointer_alignment (arg1
);
2838 unsigned align2
= get_pointer_alignment (arg2
);
2839 unsigned align
= MIN (align1
, align2
);
2840 scalar_int_mode mode
;
2841 if (int_mode_for_size (leni
, 1).exists (&mode
)
2842 && (align
>= leni
|| !targetm
.slow_unaligned_access (mode
, align
)))
2844 location_t loc
= gimple_location (stmt2
);
2846 type
= build_nonstandard_integer_type (leni
, 1);
2847 gcc_assert (known_eq (GET_MODE_BITSIZE (TYPE_MODE (type
)), leni
));
2848 tree ptrtype
= build_pointer_type_for_mode (char_type_node
,
2850 off
= build_int_cst (ptrtype
, 0);
2851 arg1
= build2_loc (loc
, MEM_REF
, type
, arg1
, off
);
2852 arg2
= build2_loc (loc
, MEM_REF
, type
, arg2
, off
);
2853 tree tem1
= fold_const_aggregate_ref (arg1
);
2856 tree tem2
= fold_const_aggregate_ref (arg2
);
2859 res
= fold_convert_loc (loc
, TREE_TYPE (res
),
2860 fold_build2_loc (loc
, NE_EXPR
,
2863 gimplify_and_update_call_from_tree (gsi
, res
);
2868 gimple_call_set_fndecl (stmt2
, builtin_decl_explicit (BUILT_IN_MEMCMP_EQ
));
2872 /* Given an index to the strinfo vector, compute the string length for the
2873 corresponding string. Return -1 when unknown. */
2875 static HOST_WIDE_INT
2876 compute_string_length (int idx
)
2878 HOST_WIDE_INT string_leni
= -1;
2879 gcc_assert (idx
!= 0);
2884 strinfo
*si
= get_strinfo (idx
);
2887 tree const_string_len
= get_string_length (si
);
2888 if (const_string_len
&& tree_fits_shwi_p (const_string_len
))
2889 string_leni
= tree_to_shwi (const_string_len
);
2892 if (string_leni
< 0)
2898 /* Determine the minimum size of the object referenced by DEST expression which
2899 must have a pointer type.
2900 Return the minimum size of the object if successful or NULL when the size
2901 cannot be determined. */
2903 determine_min_objsize (tree dest
)
2905 unsigned HOST_WIDE_INT size
= 0;
2907 if (compute_builtin_object_size (dest
, 2, &size
))
2908 return build_int_cst (sizetype
, size
);
2910 /* Try to determine the size of the object through the RHS of the
2911 assign statement. */
2912 if (TREE_CODE (dest
) == SSA_NAME
)
2914 gimple
*stmt
= SSA_NAME_DEF_STMT (dest
);
2915 if (!is_gimple_assign (stmt
))
2918 if (!gimple_assign_single_p (stmt
)
2919 && !gimple_assign_unary_nop_p (stmt
))
2922 dest
= gimple_assign_rhs1 (stmt
);
2923 return determine_min_objsize (dest
);
2926 /* Try to determine the size of the object from its type. */
2927 if (TREE_CODE (dest
) != ADDR_EXPR
)
2930 tree type
= TREE_TYPE (dest
);
2931 if (TREE_CODE (type
) == POINTER_TYPE
)
2932 type
= TREE_TYPE (type
);
2934 type
= TYPE_MAIN_VARIANT (type
);
2936 /* We cannot determine the size of the array if it's a flexible array,
2937 which is declared at the end of a structure. */
2938 if (TREE_CODE (type
) == ARRAY_TYPE
2939 && !array_at_struct_end_p (dest
))
2941 tree
size_t = TYPE_SIZE_UNIT (type
);
2942 if (size_t && TREE_CODE (size_t) == INTEGER_CST
2943 && !integer_zerop (size_t))
2950 /* Handle a call to strcmp or strncmp. When the result is ONLY used to do
2951 equality test against zero:
2953 A. When the lengths of both arguments are constant and it's a strcmp:
2954 * if the lengths are NOT equal, we can safely fold the call
2955 to a non-zero value.
2956 * otherwise, do nothing now.
2958 B. When the length of one argument is constant, try to replace the call with
2959 a __builtin_str(n)cmp_eq call where possible, i.e:
2961 strncmp (s, STR, C) (!)= 0 in which, s is a pointer to a string, STR is a
2962 string with constant length , C is a constant.
2963 if (C <= strlen(STR) && sizeof_array(s) > C)
2965 replace this call with
2966 strncmp_eq (s, STR, C) (!)= 0
2970 it can be safely treated as a call to strcmp (s, STR) (!)= 0
2971 can handled by the following strcmp.
2974 strcmp (s, STR) (!)= 0 in which, s is a pointer to a string, STR is a
2975 string with constant length.
2976 if (sizeof_array(s) > strlen(STR))
2978 replace this call with
2979 strcmp_eq (s, STR, strlen(STR)+1) (!)= 0
2982 Return true when the call is transformed, return false otherwise.
2986 handle_builtin_string_cmp (gimple_stmt_iterator
*gsi
)
2988 gcall
*stmt
= as_a
<gcall
*> (gsi_stmt (*gsi
));
2989 tree res
= gimple_call_lhs (stmt
);
2990 use_operand_p use_p
;
2991 imm_use_iterator iter
;
2992 tree arg1
= gimple_call_arg (stmt
, 0);
2993 tree arg2
= gimple_call_arg (stmt
, 1);
2994 int idx1
= get_stridx (arg1
);
2995 int idx2
= get_stridx (arg2
);
2996 HOST_WIDE_INT length
= -1;
2997 bool is_ncmp
= false;
3002 /* When both arguments are unknown, do nothing. */
3003 if (idx1
== 0 && idx2
== 0)
3006 /* Handle strncmp function. */
3007 if (gimple_call_num_args (stmt
) == 3)
3009 tree len
= gimple_call_arg (stmt
, 2);
3010 if (tree_fits_shwi_p (len
))
3011 length
= tree_to_shwi (len
);
3016 /* For strncmp, if the length argument is NOT known, do nothing. */
3017 if (is_ncmp
&& length
< 0)
3020 /* When the result is ONLY used to do equality test against zero. */
3021 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
3023 gimple
*use_stmt
= USE_STMT (use_p
);
3025 if (is_gimple_debug (use_stmt
))
3027 if (gimple_code (use_stmt
) == GIMPLE_ASSIGN
)
3029 tree_code code
= gimple_assign_rhs_code (use_stmt
);
3030 if (code
== COND_EXPR
)
3032 tree cond_expr
= gimple_assign_rhs1 (use_stmt
);
3033 if ((TREE_CODE (cond_expr
) != EQ_EXPR
3034 && (TREE_CODE (cond_expr
) != NE_EXPR
))
3035 || !integer_zerop (TREE_OPERAND (cond_expr
, 1)))
3038 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3040 if (!integer_zerop (gimple_assign_rhs2 (use_stmt
)))
3046 else if (gimple_code (use_stmt
) == GIMPLE_COND
)
3048 tree_code code
= gimple_cond_code (use_stmt
);
3049 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
3050 || !integer_zerop (gimple_cond_rhs (use_stmt
)))
3057 /* When the lengths of both arguments are known, and they are unequal, we can
3058 safely fold the call to a non-zero value for strcmp;
3059 othewise, do nothing now. */
3060 if (idx1
!= 0 && idx2
!= 0)
3062 HOST_WIDE_INT const_string_leni1
= compute_string_length (idx1
);
3063 HOST_WIDE_INT const_string_leni2
= compute_string_length (idx2
);
3066 && const_string_leni1
!= -1
3067 && const_string_leni2
!= -1
3068 && const_string_leni1
!= const_string_leni2
)
3070 replace_call_with_value (gsi
, integer_one_node
);
3076 /* When the length of one argument is constant. */
3077 tree var_string
= NULL_TREE
;
3078 HOST_WIDE_INT const_string_leni
= -1;
3082 const_string_leni
= compute_string_length (idx1
);
3087 gcc_checking_assert (idx2
);
3088 const_string_leni
= compute_string_length (idx2
);
3092 if (const_string_leni
< 0)
3095 unsigned HOST_WIDE_INT var_sizei
= 0;
3096 /* try to determine the minimum size of the object pointed by var_string. */
3097 tree size
= determine_min_objsize (var_string
);
3102 if (tree_fits_uhwi_p (size
))
3103 var_sizei
= tree_to_uhwi (size
);
3108 /* For strncmp, if length > const_string_leni , this call can be safely
3109 transformed to a strcmp. */
3110 if (is_ncmp
&& length
> const_string_leni
)
3113 unsigned HOST_WIDE_INT final_length
3114 = is_ncmp
? length
: const_string_leni
+ 1;
3116 /* Replace strcmp or strncmp with the corresponding str(n)cmp_eq. */
3117 if (var_sizei
> final_length
)
3121 ? builtin_decl_implicit (BUILT_IN_STRNCMP_EQ
)
3122 : builtin_decl_implicit (BUILT_IN_STRCMP_EQ
));
3125 tree const_string_len
= build_int_cst (size_type_node
, final_length
);
3126 update_gimple_call (gsi
, fn
, 3, arg1
, arg2
, const_string_len
);
3134 /* Handle a POINTER_PLUS_EXPR statement.
3135 For p = "abcd" + 2; compute associated length, or if
3136 p = q + off is pointing to a '\0' character of a string, call
3137 zero_length_string on it. */
3140 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
3142 gimple
*stmt
= gsi_stmt (*gsi
);
3143 tree lhs
= gimple_assign_lhs (stmt
), off
;
3144 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
3152 tree off
= gimple_assign_rhs2 (stmt
);
3153 if (tree_fits_uhwi_p (off
)
3154 && tree_to_uhwi (off
) <= (unsigned HOST_WIDE_INT
) ~idx
)
3155 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
3156 = ~(~idx
- (int) tree_to_uhwi (off
));
3160 si
= get_strinfo (idx
);
3161 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
3164 off
= gimple_assign_rhs2 (stmt
);
3166 if (si
->full_string_p
&& operand_equal_p (si
->nonzero_chars
, off
, 0))
3167 zsi
= zero_length_string (lhs
, si
);
3168 else if (TREE_CODE (off
) == SSA_NAME
)
3170 gimple
*def_stmt
= SSA_NAME_DEF_STMT (off
);
3171 if (gimple_assign_single_p (def_stmt
)
3172 && si
->full_string_p
3173 && operand_equal_p (si
->nonzero_chars
,
3174 gimple_assign_rhs1 (def_stmt
), 0))
3175 zsi
= zero_length_string (lhs
, si
);
3178 && si
->endptr
!= NULL_TREE
3179 && si
->endptr
!= lhs
3180 && TREE_CODE (si
->endptr
) == SSA_NAME
)
3182 enum tree_code rhs_code
3183 = useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (si
->endptr
))
3184 ? SSA_NAME
: NOP_EXPR
;
3185 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, si
->endptr
);
3186 gcc_assert (gsi_stmt (*gsi
) == stmt
);
3191 /* If RHS, either directly or indirectly, refers to a string of constant
3192 length, return the length. Otherwise, if it refers to a character
3193 constant, return 1 if the constant is non-zero and 0 if it is nul.
3194 Otherwise, return a negative value. */
3196 static HOST_WIDE_INT
3197 get_min_string_length (tree rhs
, bool *full_string_p
)
3199 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs
)))
3201 if (tree_expr_nonzero_p (rhs
))
3203 *full_string_p
= false;
3207 *full_string_p
= true;
3211 if (TREE_CODE (rhs
) == MEM_REF
3212 && integer_zerop (TREE_OPERAND (rhs
, 1)))
3214 rhs
= TREE_OPERAND (rhs
, 0);
3215 if (TREE_CODE (rhs
) == ADDR_EXPR
)
3217 tree rhs_addr
= rhs
;
3219 rhs
= TREE_OPERAND (rhs
, 0);
3220 if (TREE_CODE (rhs
) != STRING_CST
)
3222 int idx
= get_stridx (rhs_addr
);
3225 strinfo
*si
= get_strinfo (idx
);
3227 && tree_fits_shwi_p (si
->nonzero_chars
))
3229 *full_string_p
= si
->full_string_p
;
3230 return tree_to_shwi (si
->nonzero_chars
);
3237 if (TREE_CODE (rhs
) == VAR_DECL
3238 && TREE_READONLY (rhs
))
3239 rhs
= DECL_INITIAL (rhs
);
3241 if (rhs
&& TREE_CODE (rhs
) == STRING_CST
)
3243 HOST_WIDE_INT len
= strlen (TREE_STRING_POINTER (rhs
));
3244 *full_string_p
= len
< TREE_STRING_LENGTH (rhs
);
3251 /* Handle a single or multiple character store either by single
3252 character assignment or by multi-character assignment from
3256 handle_char_store (gimple_stmt_iterator
*gsi
)
3260 gimple
*stmt
= gsi_stmt (*gsi
);
3261 tree ssaname
= NULL_TREE
, lhs
= gimple_assign_lhs (stmt
);
3262 tree rhs
= gimple_assign_rhs1 (stmt
);
3263 unsigned HOST_WIDE_INT offset
= 0;
3265 if (TREE_CODE (lhs
) == MEM_REF
3266 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
)
3268 tree mem_offset
= TREE_OPERAND (lhs
, 1);
3269 if (tree_fits_uhwi_p (mem_offset
))
3271 /* Get the strinfo for the base, and use it if it starts with at
3272 least OFFSET nonzero characters. This is trivially true if
3274 offset
= tree_to_uhwi (mem_offset
);
3275 idx
= get_stridx (TREE_OPERAND (lhs
, 0));
3277 si
= get_strinfo (idx
);
3279 ssaname
= TREE_OPERAND (lhs
, 0);
3280 else if (si
== NULL
|| compare_nonzero_chars (si
, offset
) < 0)
3286 idx
= get_addr_stridx (lhs
, NULL_TREE
, &offset
);
3288 si
= get_strinfo (idx
);
3291 /* STORING_NONZERO_P is true iff not all stored characters are zero.
3292 STORING_ALL_ZEROS_P is true iff all stored characters are zero.
3293 Both are false when it's impossible to determine which is true. */
3294 bool storing_nonzero_p
;
3295 bool storing_all_zeros_p
= initializer_zerop (rhs
, &storing_nonzero_p
);
3296 if (!storing_nonzero_p
)
3297 storing_nonzero_p
= tree_expr_nonzero_p (rhs
);
3298 bool full_string_p
= storing_all_zeros_p
;
3300 /* Set to the length of the string being assigned if known. */
3301 HOST_WIDE_INT rhslen
;
3305 int cmp
= compare_nonzero_chars (si
, offset
);
3306 gcc_assert (offset
== 0 || cmp
>= 0);
3307 if (storing_all_zeros_p
&& cmp
== 0 && si
->full_string_p
)
3309 /* When overwriting a '\0' with a '\0', the store can be removed
3310 if we know it has been stored in the current function. */
3311 if (!stmt_could_throw_p (cfun
, stmt
) && si
->writable
)
3313 unlink_stmt_vdef (stmt
);
3314 release_defs (stmt
);
3315 gsi_remove (gsi
, true);
3320 si
->writable
= true;
3325 /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0',
3326 and if we aren't storing '\0', we know that the length of the
3327 string and any other zero terminated string in memory remains
3328 the same. In that case we move to the next gimple statement and
3329 return to signal the caller that it shouldn't invalidate anything.
3331 This is benefical for cases like:
3336 strcpy (p, "foobar");
3337 size_t len = strlen (p); // This can be optimized into 6
3338 size_t len2 = strlen (q); // This has to be computed
3340 size_t len3 = strlen (p); // This can be optimized into 6
3341 size_t len4 = strlen (q); // This can be optimized into len2
3342 bar (len, len2, len3, len4);
3345 else if (storing_nonzero_p
&& cmp
> 0)
3350 else if (storing_all_zeros_p
|| storing_nonzero_p
|| (offset
!= 0 && cmp
> 0))
3352 /* When STORING_NONZERO_P, we know that the string will start
3353 with at least OFFSET + 1 nonzero characters. If storing
3354 a single character, set si->NONZERO_CHARS to the result.
3355 If storing multiple characters, try to determine the number
3356 of leading non-zero characters and set si->NONZERO_CHARS to
3359 When STORING_ALL_ZEROS_P, we know that the string is now
3360 OFFSET characters long.
3362 Otherwise, we're storing an unknown value at offset OFFSET,
3363 so need to clip the nonzero_chars to OFFSET. */
3364 bool full_string_p
= storing_all_zeros_p
;
3365 HOST_WIDE_INT len
= 1;
3366 if (storing_nonzero_p
)
3368 /* Try to get the minimum length of the string (or
3369 individual character) being stored. If it fails,
3370 STORING_NONZERO_P guarantees it's at least 1. */
3371 len
= get_min_string_length (rhs
, &full_string_p
);
3376 location_t loc
= gimple_location (stmt
);
3377 tree oldlen
= si
->nonzero_chars
;
3378 if (cmp
== 0 && si
->full_string_p
)
3379 /* We're overwriting the nul terminator with a nonzero or
3380 unknown character. If the previous stmt was a memcpy,
3381 its length may be decreased. */
3382 adjust_last_stmt (si
, stmt
, false);
3383 si
= unshare_strinfo (si
);
3384 if (storing_nonzero_p
)
3386 gcc_assert (len
>= 0);
3387 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
+ len
);
3390 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
);
3391 si
->full_string_p
= full_string_p
;
3392 if (storing_all_zeros_p
3394 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
3395 si
->endptr
= ssaname
;
3400 si
->writable
= true;
3401 si
->dont_invalidate
= true;
3404 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
3405 si
->nonzero_chars
, oldlen
);
3406 adjust_related_strinfos (loc
, si
, adj
);
3412 else if (idx
== 0 && (storing_all_zeros_p
|| storing_nonzero_p
))
3415 idx
= new_stridx (ssaname
);
3417 idx
= new_addr_stridx (lhs
);
3420 tree ptr
= (ssaname
? ssaname
: build_fold_addr_expr (lhs
));
3421 HOST_WIDE_INT slen
= (storing_all_zeros_p
3423 : (storing_nonzero_p
3424 ? get_min_string_length (rhs
, &full_string_p
)
3426 tree len
= (slen
<= 0
3428 : build_int_cst (size_type_node
, slen
));
3429 si
= new_strinfo (ptr
, idx
, len
, slen
>= 0 && full_string_p
);
3430 set_strinfo (idx
, si
);
3431 if (storing_all_zeros_p
3433 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
3434 si
->endptr
= ssaname
;
3435 si
->dont_invalidate
= true;
3436 si
->writable
= true;
3440 && (rhslen
= get_min_string_length (rhs
, &full_string_p
)) >= 0
3441 && ssaname
== NULL_TREE
3442 && TREE_CODE (TREE_TYPE (lhs
)) == ARRAY_TYPE
)
3444 HOST_WIDE_INT a
= int_size_in_bytes (TREE_TYPE (lhs
));
3445 if (a
> 0 && (unsigned HOST_WIDE_INT
) a
> (unsigned HOST_WIDE_INT
) rhslen
)
3447 int idx
= new_addr_stridx (lhs
);
3450 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
3451 build_int_cst (size_type_node
, rhslen
),
3453 set_strinfo (idx
, si
);
3454 si
->dont_invalidate
= true;
3459 if (si
!= NULL
&& offset
== 0 && storing_all_zeros_p
)
3461 /* Allow adjust_last_stmt to remove it if the stored '\0'
3462 is immediately overwritten. */
3463 laststmt
.stmt
= stmt
;
3464 laststmt
.len
= build_int_cst (size_type_node
, 1);
3465 laststmt
.stridx
= si
->idx
;
3470 /* Try to fold strstr (s, t) eq/ne s to strncmp (s, t, strlen (t)) eq/ne 0. */
3473 fold_strstr_to_strncmp (tree rhs1
, tree rhs2
, gimple
*stmt
)
3475 if (TREE_CODE (rhs1
) != SSA_NAME
3476 || TREE_CODE (rhs2
) != SSA_NAME
)
3479 gimple
*call_stmt
= NULL
;
3480 for (int pass
= 0; pass
< 2; pass
++)
3482 gimple
*g
= SSA_NAME_DEF_STMT (rhs1
);
3483 if (gimple_call_builtin_p (g
, BUILT_IN_STRSTR
)
3484 && has_single_use (rhs1
)
3485 && gimple_call_arg (g
, 0) == rhs2
)
3490 std::swap (rhs1
, rhs2
);
3495 tree arg0
= gimple_call_arg (call_stmt
, 0);
3499 tree arg1
= gimple_call_arg (call_stmt
, 1);
3500 tree arg1_len
= NULL_TREE
;
3501 int idx
= get_stridx (arg1
);
3506 arg1_len
= build_int_cst (size_type_node
, ~idx
);
3509 strinfo
*si
= get_strinfo (idx
);
3511 arg1_len
= get_string_length (si
);
3515 if (arg1_len
!= NULL_TREE
)
3517 gimple_stmt_iterator gsi
= gsi_for_stmt (call_stmt
);
3518 tree strncmp_decl
= builtin_decl_explicit (BUILT_IN_STRNCMP
);
3520 if (!is_gimple_val (arg1_len
))
3522 tree arg1_len_tmp
= make_ssa_name (TREE_TYPE (arg1_len
));
3523 gassign
*arg1_stmt
= gimple_build_assign (arg1_len_tmp
,
3525 gsi_insert_before (&gsi
, arg1_stmt
, GSI_SAME_STMT
);
3526 arg1_len
= arg1_len_tmp
;
3529 gcall
*strncmp_call
= gimple_build_call (strncmp_decl
, 3,
3530 arg0
, arg1
, arg1_len
);
3531 tree strncmp_lhs
= make_ssa_name (integer_type_node
);
3532 gimple_set_vuse (strncmp_call
, gimple_vuse (call_stmt
));
3533 gimple_call_set_lhs (strncmp_call
, strncmp_lhs
);
3534 gsi_remove (&gsi
, true);
3535 gsi_insert_before (&gsi
, strncmp_call
, GSI_SAME_STMT
);
3536 tree zero
= build_zero_cst (TREE_TYPE (strncmp_lhs
));
3538 if (is_gimple_assign (stmt
))
3540 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
3542 tree cond
= gimple_assign_rhs1 (stmt
);
3543 TREE_OPERAND (cond
, 0) = strncmp_lhs
;
3544 TREE_OPERAND (cond
, 1) = zero
;
3548 gimple_assign_set_rhs1 (stmt
, strncmp_lhs
);
3549 gimple_assign_set_rhs2 (stmt
, zero
);
3554 gcond
*cond
= as_a
<gcond
*> (stmt
);
3555 gimple_cond_set_lhs (cond
, strncmp_lhs
);
3556 gimple_cond_set_rhs (cond
, zero
);
3564 /* Attempt to check for validity of the performed access a single statement
3565 at *GSI using string length knowledge, and to optimize it.
3566 If the given basic block needs clean-up of EH, CLEANUP_EH is set to
3570 strlen_check_and_optimize_stmt (gimple_stmt_iterator
*gsi
, bool *cleanup_eh
)
3572 gimple
*stmt
= gsi_stmt (*gsi
);
3574 if (is_gimple_call (stmt
))
3576 tree callee
= gimple_call_fndecl (stmt
);
3577 if (valid_builtin_call (stmt
))
3578 switch (DECL_FUNCTION_CODE (callee
))
3580 case BUILT_IN_STRLEN
:
3581 case BUILT_IN_STRNLEN
:
3582 handle_builtin_strlen (gsi
);
3584 case BUILT_IN_STRCHR
:
3585 handle_builtin_strchr (gsi
);
3587 case BUILT_IN_STRCPY
:
3588 case BUILT_IN_STRCPY_CHK
:
3589 case BUILT_IN_STPCPY
:
3590 case BUILT_IN_STPCPY_CHK
:
3591 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3594 case BUILT_IN_STRNCAT
:
3595 case BUILT_IN_STRNCAT_CHK
:
3596 handle_builtin_strncat (DECL_FUNCTION_CODE (callee
), gsi
);
3599 case BUILT_IN_STPNCPY
:
3600 case BUILT_IN_STPNCPY_CHK
:
3601 case BUILT_IN_STRNCPY
:
3602 case BUILT_IN_STRNCPY_CHK
:
3603 handle_builtin_stxncpy (DECL_FUNCTION_CODE (callee
), gsi
);
3606 case BUILT_IN_MEMCPY
:
3607 case BUILT_IN_MEMCPY_CHK
:
3608 case BUILT_IN_MEMPCPY
:
3609 case BUILT_IN_MEMPCPY_CHK
:
3610 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3612 case BUILT_IN_STRCAT
:
3613 case BUILT_IN_STRCAT_CHK
:
3614 handle_builtin_strcat (DECL_FUNCTION_CODE (callee
), gsi
);
3616 case BUILT_IN_MALLOC
:
3617 case BUILT_IN_CALLOC
:
3618 handle_builtin_malloc (DECL_FUNCTION_CODE (callee
), gsi
);
3620 case BUILT_IN_MEMSET
:
3621 if (handle_builtin_memset (gsi
))
3624 case BUILT_IN_MEMCMP
:
3625 if (handle_builtin_memcmp (gsi
))
3628 case BUILT_IN_STRCMP
:
3629 case BUILT_IN_STRNCMP
:
3630 if (handle_builtin_string_cmp (gsi
))
3637 else if (is_gimple_assign (stmt
) && !gimple_clobber_p (stmt
))
3639 tree lhs
= gimple_assign_lhs (stmt
);
3641 if (TREE_CODE (lhs
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (lhs
)))
3643 if (gimple_assign_single_p (stmt
)
3644 || (gimple_assign_cast_p (stmt
)
3645 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
3647 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
3648 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = idx
;
3650 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
3651 handle_pointer_plus (gsi
);
3653 else if (TREE_CODE (lhs
) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
3655 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3656 if (code
== COND_EXPR
)
3658 tree cond
= gimple_assign_rhs1 (stmt
);
3659 enum tree_code cond_code
= TREE_CODE (cond
);
3661 if (cond_code
== EQ_EXPR
|| cond_code
== NE_EXPR
)
3662 fold_strstr_to_strncmp (TREE_OPERAND (cond
, 0),
3663 TREE_OPERAND (cond
, 1), stmt
);
3665 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3666 fold_strstr_to_strncmp (gimple_assign_rhs1 (stmt
),
3667 gimple_assign_rhs2 (stmt
), stmt
);
3668 else if (gimple_assign_load_p (stmt
)
3669 && TREE_CODE (TREE_TYPE (lhs
)) == INTEGER_TYPE
3670 && TYPE_MODE (TREE_TYPE (lhs
)) == TYPE_MODE (char_type_node
)
3671 && (TYPE_PRECISION (TREE_TYPE (lhs
))
3672 == TYPE_PRECISION (char_type_node
))
3673 && !gimple_has_volatile_ops (stmt
))
3675 tree off
= integer_zero_node
;
3676 unsigned HOST_WIDE_INT coff
= 0;
3678 tree rhs1
= gimple_assign_rhs1 (stmt
);
3679 if (code
== MEM_REF
)
3681 idx
= get_stridx (TREE_OPERAND (rhs1
, 0));
3684 strinfo
*si
= get_strinfo (idx
);
3686 && si
->nonzero_chars
3687 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
3688 && (wi::to_widest (si
->nonzero_chars
)
3689 >= wi::to_widest (off
)))
3690 off
= TREE_OPERAND (rhs1
, 1);
3692 /* This case is not useful. See if get_addr_stridx
3693 returns something usable. */
3698 idx
= get_addr_stridx (rhs1
, NULL_TREE
, &coff
);
3701 strinfo
*si
= get_strinfo (idx
);
3703 && si
->nonzero_chars
3704 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
3706 widest_int w1
= wi::to_widest (si
->nonzero_chars
);
3707 widest_int w2
= wi::to_widest (off
) + coff
;
3709 && si
->full_string_p
)
3711 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3713 fprintf (dump_file
, "Optimizing: ");
3714 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3717 /* Reading the final '\0' character. */
3718 tree zero
= build_int_cst (TREE_TYPE (lhs
), 0);
3719 gimple_set_vuse (stmt
, NULL_TREE
);
3720 gimple_assign_set_rhs_from_tree (gsi
, zero
);
3722 |= maybe_clean_or_replace_eh_stmt (stmt
,
3724 stmt
= gsi_stmt (*gsi
);
3727 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3729 fprintf (dump_file
, "into: ");
3730 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3735 /* Reading a character before the final '\0'
3736 character. Just set the value range to ~[0, 0]
3737 if we don't have anything better. */
3739 tree type
= TREE_TYPE (lhs
);
3740 enum value_range_kind vr
3741 = get_range_info (lhs
, &min
, &max
);
3742 if (vr
== VR_VARYING
3744 && min
== wi::min_value (TYPE_PRECISION (type
),
3746 && max
== wi::max_value (TYPE_PRECISION (type
),
3748 set_range_info (lhs
, VR_ANTI_RANGE
,
3749 wi::zero (TYPE_PRECISION (type
)),
3750 wi::zero (TYPE_PRECISION (type
)));
3756 if (strlen_to_stridx
)
3758 tree rhs1
= gimple_assign_rhs1 (stmt
);
3759 if (stridx_strlenloc
*ps
= strlen_to_stridx
->get (rhs1
))
3760 strlen_to_stridx
->put (lhs
, stridx_strlenloc (*ps
));
3763 else if (TREE_CODE (lhs
) != SSA_NAME
&& !TREE_SIDE_EFFECTS (lhs
))
3765 tree type
= TREE_TYPE (lhs
);
3766 if (TREE_CODE (type
) == ARRAY_TYPE
)
3767 type
= TREE_TYPE (type
);
3768 if (TREE_CODE (type
) == INTEGER_TYPE
3769 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
3770 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
))
3772 if (! handle_char_store (gsi
))
3777 else if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
3779 enum tree_code code
= gimple_cond_code (cond
);
3780 if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3781 fold_strstr_to_strncmp (gimple_cond_lhs (stmt
),
3782 gimple_cond_rhs (stmt
), stmt
);
3785 if (gimple_vdef (stmt
))
3786 maybe_invalidate (stmt
);
3790 /* Recursively call maybe_invalidate on stmts that might be executed
3791 in between dombb and current bb and that contain a vdef. Stop when
3792 *count stmts are inspected, or if the whole strinfo vector has
3793 been invalidated. */
3796 do_invalidate (basic_block dombb
, gimple
*phi
, bitmap visited
, int *count
)
3798 unsigned int i
, n
= gimple_phi_num_args (phi
);
3800 for (i
= 0; i
< n
; i
++)
3802 tree vuse
= gimple_phi_arg_def (phi
, i
);
3803 gimple
*stmt
= SSA_NAME_DEF_STMT (vuse
);
3804 basic_block bb
= gimple_bb (stmt
);
3807 || !bitmap_set_bit (visited
, bb
->index
)
3808 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3812 if (gimple_code (stmt
) == GIMPLE_PHI
)
3814 do_invalidate (dombb
, stmt
, visited
, count
);
3821 if (!maybe_invalidate (stmt
))
3826 vuse
= gimple_vuse (stmt
);
3827 stmt
= SSA_NAME_DEF_STMT (vuse
);
3828 if (gimple_bb (stmt
) != bb
)
3830 bb
= gimple_bb (stmt
);
3833 || !bitmap_set_bit (visited
, bb
->index
)
3834 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3841 class strlen_dom_walker
: public dom_walker
3844 strlen_dom_walker (cdi_direction direction
)
3845 : dom_walker (direction
), m_cleanup_cfg (false)
3848 virtual edge
before_dom_children (basic_block
);
3849 virtual void after_dom_children (basic_block
);
3851 /* Flag that will trigger TODO_cleanup_cfg to be returned in strlen
3852 execute function. */
3856 /* Callback for walk_dominator_tree. Attempt to optimize various
3857 string ops by remembering string lengths pointed by pointer SSA_NAMEs. */
3860 strlen_dom_walker::before_dom_children (basic_block bb
)
3862 basic_block dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
3865 stridx_to_strinfo
= NULL
;
3868 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) dombb
->aux
);
3869 if (stridx_to_strinfo
)
3871 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3874 gphi
*phi
= gsi
.phi ();
3875 if (virtual_operand_p (gimple_phi_result (phi
)))
3877 bitmap visited
= BITMAP_ALLOC (NULL
);
3878 int count_vdef
= 100;
3879 do_invalidate (dombb
, phi
, visited
, &count_vdef
);
3880 BITMAP_FREE (visited
);
3881 if (count_vdef
== 0)
3883 /* If there were too many vdefs in between immediate
3884 dominator and current bb, invalidate everything.
3885 If stridx_to_strinfo has been unshared, we need
3886 to free it, otherwise just set it to NULL. */
3887 if (!strinfo_shared ())
3893 vec_safe_iterate (stridx_to_strinfo
, i
, &si
);
3897 (*stridx_to_strinfo
)[i
] = NULL
;
3901 stridx_to_strinfo
= NULL
;
3909 /* If all PHI arguments have the same string index, the PHI result
3911 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3914 gphi
*phi
= gsi
.phi ();
3915 tree result
= gimple_phi_result (phi
);
3916 if (!virtual_operand_p (result
) && POINTER_TYPE_P (TREE_TYPE (result
)))
3918 int idx
= get_stridx (gimple_phi_arg_def (phi
, 0));
3921 unsigned int i
, n
= gimple_phi_num_args (phi
);
3922 for (i
= 1; i
< n
; i
++)
3923 if (idx
!= get_stridx (gimple_phi_arg_def (phi
, i
)))
3926 ssa_ver_to_stridx
[SSA_NAME_VERSION (result
)] = idx
;
3931 bool cleanup_eh
= false;
3933 /* Attempt to optimize individual statements. */
3934 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
3935 if (strlen_check_and_optimize_stmt (&gsi
, &cleanup_eh
))
3938 if (cleanup_eh
&& gimple_purge_dead_eh_edges (bb
))
3939 m_cleanup_cfg
= true;
3941 bb
->aux
= stridx_to_strinfo
;
3942 if (vec_safe_length (stridx_to_strinfo
) && !strinfo_shared ())
3943 (*stridx_to_strinfo
)[0] = (strinfo
*) bb
;
3947 /* Callback for walk_dominator_tree. Free strinfo vector if it is
3948 owned by the current bb, clear bb->aux. */
3951 strlen_dom_walker::after_dom_children (basic_block bb
)
3955 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) bb
->aux
);
3956 if (vec_safe_length (stridx_to_strinfo
)
3957 && (*stridx_to_strinfo
)[0] == (strinfo
*) bb
)
3962 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
3964 vec_free (stridx_to_strinfo
);
3970 /* Main entry point. */
3974 const pass_data pass_data_strlen
=
3976 GIMPLE_PASS
, /* type */
3977 "strlen", /* name */
3978 OPTGROUP_NONE
, /* optinfo_flags */
3979 TV_TREE_STRLEN
, /* tv_id */
3980 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3981 0, /* properties_provided */
3982 0, /* properties_destroyed */
3983 0, /* todo_flags_start */
3984 0, /* todo_flags_finish */
3987 class pass_strlen
: public gimple_opt_pass
3990 pass_strlen (gcc::context
*ctxt
)
3991 : gimple_opt_pass (pass_data_strlen
, ctxt
)
3994 /* opt_pass methods: */
3995 virtual bool gate (function
*) { return flag_optimize_strlen
!= 0; }
3996 virtual unsigned int execute (function
*);
3998 }; // class pass_strlen
4001 pass_strlen::execute (function
*fun
)
4003 gcc_assert (!strlen_to_stridx
);
4004 if (warn_stringop_overflow
|| warn_stringop_truncation
)
4005 strlen_to_stridx
= new hash_map
<tree
, stridx_strlenloc
> ();
4007 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
4010 calculate_dominance_info (CDI_DOMINATORS
);
4012 /* String length optimization is implemented as a walk of the dominator
4013 tree and a forward walk of statements within each block. */
4014 strlen_dom_walker
walker (CDI_DOMINATORS
);
4015 walker
.walk (fun
->cfg
->x_entry_block_ptr
);
4017 ssa_ver_to_stridx
.release ();
4018 strinfo_pool
.release ();
4019 if (decl_to_stridxlist_htab
)
4021 obstack_free (&stridx_obstack
, NULL
);
4022 delete decl_to_stridxlist_htab
;
4023 decl_to_stridxlist_htab
= NULL
;
4025 laststmt
.stmt
= NULL
;
4026 laststmt
.len
= NULL_TREE
;
4027 laststmt
.stridx
= 0;
4029 if (strlen_to_stridx
)
4031 strlen_to_stridx
->empty ();
4032 delete strlen_to_stridx
;
4033 strlen_to_stridx
= NULL
;
4036 return walker
.m_cleanup_cfg
? TODO_cleanup_cfg
: 0;
4042 make_pass_strlen (gcc::context
*ctxt
)
4044 return new pass_strlen (ctxt
);