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 offset
= 0;
302 /* Follow a chain of at most 5 assignments. */
303 for (int i
= 0; i
< 5; i
++)
305 gimple
*def_stmt
= SSA_NAME_DEF_STMT (e
);
306 if (!is_gimple_assign (def_stmt
))
309 tree_code rhs_code
= gimple_assign_rhs_code (def_stmt
);
312 if (rhs_code
== ADDR_EXPR
)
314 /* Handle indices/offsets into VLAs which are implemented
315 as pointers to arrays. */
316 ptr
= gimple_assign_rhs1 (def_stmt
);
317 ptr
= TREE_OPERAND (ptr
, 0);
319 /* Handle also VLAs of types larger than char. */
320 if (tree eltsize
= TYPE_SIZE_UNIT (TREE_TYPE (ptr
)))
322 if (TREE_CODE (ptr
) == ARRAY_REF
)
324 off
= TREE_OPERAND (ptr
, 1);
325 /* Scale the array index by the size of the element
326 type (normally 1 for char). */
327 off
= fold_build2 (MULT_EXPR
, TREE_TYPE (off
), off
,
329 ptr
= TREE_OPERAND (ptr
, 0);
332 off
= integer_zero_node
;
337 if (TREE_CODE (ptr
) != MEM_REF
)
340 /* Add the MEM_REF byte offset. */
341 tree mem_off
= TREE_OPERAND (ptr
, 1);
342 off
= fold_build2 (PLUS_EXPR
, TREE_TYPE (off
), off
, mem_off
);
343 ptr
= TREE_OPERAND (ptr
, 0);
345 else if (rhs_code
== POINTER_PLUS_EXPR
)
347 ptr
= gimple_assign_rhs1 (def_stmt
);
348 off
= gimple_assign_rhs2 (def_stmt
);
353 if (TREE_CODE (ptr
) != SSA_NAME
354 || !tree_fits_shwi_p (off
))
356 HOST_WIDE_INT this_off
= tree_to_shwi (off
);
359 offset
= (unsigned HOST_WIDE_INT
) offset
+ this_off
;
362 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)])
365 = get_strinfo (ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)]);
366 if (si
&& compare_nonzero_chars (si
, offset
) >= 0)
367 return get_stridx_plus_constant (si
, offset
, exp
);
374 if (TREE_CODE (exp
) == ADDR_EXPR
)
376 int idx
= get_addr_stridx (TREE_OPERAND (exp
, 0), exp
, NULL
);
381 const char *p
= c_getstr (exp
);
383 return ~(int) strlen (p
);
388 /* Return true if strinfo vector is shared with the immediate dominator. */
391 strinfo_shared (void)
393 return vec_safe_length (stridx_to_strinfo
)
394 && (*stridx_to_strinfo
)[0] != NULL
;
397 /* Unshare strinfo vector that is shared with the immediate dominator. */
400 unshare_strinfo_vec (void)
405 gcc_assert (strinfo_shared ());
406 stridx_to_strinfo
= vec_safe_copy (stridx_to_strinfo
);
407 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
410 (*stridx_to_strinfo
)[0] = NULL
;
413 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
414 Return a pointer to the location where the string index can
415 be stored (if 0) or is stored, or NULL if this can't be tracked. */
418 addr_stridxptr (tree exp
)
423 tree base
= get_addr_base_and_unit_offset (exp
, &poff
);
424 if (base
== NULL_TREE
|| !DECL_P (base
) || !poff
.is_constant (&off
))
427 if (!decl_to_stridxlist_htab
)
429 decl_to_stridxlist_htab
430 = new hash_map
<tree_decl_hash
, stridxlist
> (64);
431 gcc_obstack_init (&stridx_obstack
);
435 stridxlist
*list
= &decl_to_stridxlist_htab
->get_or_insert (base
, &existed
);
439 stridxlist
*before
= NULL
;
440 for (i
= 0; i
< 32; i
++)
442 if (list
->offset
== off
)
444 if (list
->offset
> off
&& before
== NULL
)
446 if (list
->next
== NULL
)
455 before
= XOBNEW (&stridx_obstack
, struct stridxlist
);
462 list
->next
= XOBNEW (&stridx_obstack
, struct stridxlist
);
472 /* Create a new string index, or return 0 if reached limit. */
475 new_stridx (tree exp
)
478 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
480 if (TREE_CODE (exp
) == SSA_NAME
)
482 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
))
485 ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)] = idx
;
488 if (TREE_CODE (exp
) == ADDR_EXPR
)
490 int *pidx
= addr_stridxptr (TREE_OPERAND (exp
, 0));
493 gcc_assert (*pidx
== 0);
494 *pidx
= max_stridx
++;
501 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
504 new_addr_stridx (tree exp
)
507 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
509 pidx
= addr_stridxptr (exp
);
512 gcc_assert (*pidx
== 0);
513 *pidx
= max_stridx
++;
519 /* Create a new strinfo. */
522 new_strinfo (tree ptr
, int idx
, tree nonzero_chars
, bool full_string_p
)
524 strinfo
*si
= strinfo_pool
.allocate ();
525 si
->nonzero_chars
= nonzero_chars
;
528 si
->endptr
= NULL_TREE
;
534 si
->writable
= false;
535 si
->dont_invalidate
= false;
536 si
->full_string_p
= full_string_p
;
540 /* Decrease strinfo refcount and free it if not referenced anymore. */
543 free_strinfo (strinfo
*si
)
545 if (si
&& --si
->refcount
== 0)
546 strinfo_pool
.remove (si
);
549 /* Set strinfo in the vector entry IDX to SI. */
552 set_strinfo (int idx
, strinfo
*si
)
554 if (vec_safe_length (stridx_to_strinfo
) && (*stridx_to_strinfo
)[0])
555 unshare_strinfo_vec ();
556 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
557 vec_safe_grow_cleared (stridx_to_strinfo
, idx
+ 1);
558 (*stridx_to_strinfo
)[idx
] = si
;
561 /* Return the first strinfo in the related strinfo chain
562 if all strinfos in between belong to the chain, otherwise NULL. */
565 verify_related_strinfos (strinfo
*origsi
)
567 strinfo
*si
= origsi
, *psi
;
569 if (origsi
->first
== 0)
571 for (; si
->prev
; si
= psi
)
573 if (si
->first
!= origsi
->first
)
575 psi
= get_strinfo (si
->prev
);
578 if (psi
->next
!= si
->idx
)
581 if (si
->idx
!= si
->first
)
586 /* Set SI's endptr to ENDPTR and compute its length based on SI->ptr.
587 Use LOC for folding. */
590 set_endptr_and_length (location_t loc
, strinfo
*si
, tree endptr
)
594 tree start_as_size
= fold_convert_loc (loc
, size_type_node
, si
->ptr
);
595 tree end_as_size
= fold_convert_loc (loc
, size_type_node
, endptr
);
596 si
->nonzero_chars
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
597 end_as_size
, start_as_size
);
598 si
->full_string_p
= true;
601 /* Return string length, or NULL if it can't be computed. */
604 get_string_length (strinfo
*si
)
606 if (si
->nonzero_chars
)
607 return si
->full_string_p
? si
->nonzero_chars
: NULL
;
611 gimple
*stmt
= si
->stmt
, *lenstmt
;
612 tree callee
, lhs
, fn
, tem
;
614 gimple_stmt_iterator gsi
;
616 gcc_assert (is_gimple_call (stmt
));
617 callee
= gimple_call_fndecl (stmt
);
618 gcc_assert (callee
&& fndecl_built_in_p (callee
, BUILT_IN_NORMAL
));
619 lhs
= gimple_call_lhs (stmt
);
620 /* unshare_strinfo is intentionally not called here. The (delayed)
621 transformation of strcpy or strcat into stpcpy is done at the place
622 of the former strcpy/strcat call and so can affect all the strinfos
623 with the same stmt. If they were unshared before and transformation
624 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
625 just compute the right length. */
626 switch (DECL_FUNCTION_CODE (callee
))
628 case BUILT_IN_STRCAT
:
629 case BUILT_IN_STRCAT_CHK
:
630 gsi
= gsi_for_stmt (stmt
);
631 fn
= builtin_decl_implicit (BUILT_IN_STRLEN
);
632 gcc_assert (lhs
== NULL_TREE
);
633 tem
= unshare_expr (gimple_call_arg (stmt
, 0));
634 lenstmt
= gimple_build_call (fn
, 1, tem
);
635 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), lenstmt
);
636 gimple_call_set_lhs (lenstmt
, lhs
);
637 gimple_set_vuse (lenstmt
, gimple_vuse (stmt
));
638 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
639 tem
= gimple_call_arg (stmt
, 0);
640 if (!ptrofftype_p (TREE_TYPE (lhs
)))
642 lhs
= convert_to_ptrofftype (lhs
);
643 lhs
= force_gimple_operand_gsi (&gsi
, lhs
, true, NULL_TREE
,
644 true, GSI_SAME_STMT
);
646 lenstmt
= gimple_build_assign
647 (make_ssa_name (TREE_TYPE (gimple_call_arg (stmt
, 0))),
648 POINTER_PLUS_EXPR
,tem
, lhs
);
649 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
650 gimple_call_set_arg (stmt
, 0, gimple_assign_lhs (lenstmt
));
653 case BUILT_IN_STRCPY
:
654 case BUILT_IN_STRCPY_CHK
:
655 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY
));
656 if (gimple_call_num_args (stmt
) == 2)
657 fn
= builtin_decl_implicit (BUILT_IN_STPCPY
);
659 fn
= builtin_decl_explicit (BUILT_IN_STPCPY_CHK
);
660 gcc_assert (lhs
== NULL_TREE
);
661 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
663 fprintf (dump_file
, "Optimizing: ");
664 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
666 gimple_call_set_fndecl (stmt
, fn
);
667 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), stmt
);
668 gimple_call_set_lhs (stmt
, lhs
);
670 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
672 fprintf (dump_file
, "into: ");
673 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
676 case BUILT_IN_STPCPY
:
677 case BUILT_IN_STPCPY_CHK
:
678 gcc_assert (lhs
!= NULL_TREE
);
679 loc
= gimple_location (stmt
);
680 set_endptr_and_length (loc
, si
, lhs
);
681 for (strinfo
*chainsi
= verify_related_strinfos (si
);
683 chainsi
= get_next_strinfo (chainsi
))
684 if (chainsi
->nonzero_chars
== NULL
)
685 set_endptr_and_length (loc
, chainsi
, lhs
);
687 case BUILT_IN_MALLOC
:
689 /* BUILT_IN_CALLOC always has si->nonzero_chars set. */
696 return si
->nonzero_chars
;
699 /* Invalidate string length information for strings whose length
700 might change due to stores in stmt. */
703 maybe_invalidate (gimple
*stmt
)
707 bool nonempty
= false;
709 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
712 if (!si
->dont_invalidate
)
715 /* Do not use si->nonzero_chars. */
716 ao_ref_init_from_ptr_and_size (&r
, si
->ptr
, NULL_TREE
);
717 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
719 set_strinfo (i
, NULL
);
724 si
->dont_invalidate
= false;
730 /* Unshare strinfo record SI, if it has refcount > 1 or
731 if stridx_to_strinfo vector is shared with some other
735 unshare_strinfo (strinfo
*si
)
739 if (si
->refcount
== 1 && !strinfo_shared ())
742 nsi
= new_strinfo (si
->ptr
, si
->idx
, si
->nonzero_chars
, si
->full_string_p
);
743 nsi
->stmt
= si
->stmt
;
744 nsi
->endptr
= si
->endptr
;
745 nsi
->first
= si
->first
;
746 nsi
->prev
= si
->prev
;
747 nsi
->next
= si
->next
;
748 nsi
->writable
= si
->writable
;
749 set_strinfo (si
->idx
, nsi
);
754 /* Attempt to create a new strinfo for BASESI + OFF, or find existing
755 strinfo if there is any. Return it's idx, or 0 if no strinfo has
759 get_stridx_plus_constant (strinfo
*basesi
, unsigned HOST_WIDE_INT off
,
762 if (TREE_CODE (ptr
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
765 if (compare_nonzero_chars (basesi
, off
) < 0
766 || !tree_fits_uhwi_p (basesi
->nonzero_chars
))
769 unsigned HOST_WIDE_INT nonzero_chars
770 = tree_to_uhwi (basesi
->nonzero_chars
) - off
;
771 strinfo
*si
= basesi
, *chainsi
;
772 if (si
->first
|| si
->prev
|| si
->next
)
773 si
= verify_related_strinfos (basesi
);
775 || si
->nonzero_chars
== NULL_TREE
776 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
779 if (TREE_CODE (ptr
) == SSA_NAME
780 && ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
781 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
783 gcc_checking_assert (compare_tree_int (si
->nonzero_chars
, off
) != -1);
784 for (chainsi
= si
; chainsi
->next
; chainsi
= si
)
786 si
= get_next_strinfo (chainsi
);
788 || si
->nonzero_chars
== NULL_TREE
789 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
791 int r
= compare_tree_int (si
->nonzero_chars
, nonzero_chars
);
796 if (TREE_CODE (ptr
) == SSA_NAME
)
797 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = si
->idx
;
800 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
801 if (pidx
!= NULL
&& *pidx
== 0)
810 int idx
= new_stridx (ptr
);
813 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, nonzero_chars
),
814 basesi
->full_string_p
);
815 set_strinfo (idx
, si
);
816 if (strinfo
*nextsi
= get_strinfo (chainsi
->next
))
818 nextsi
= unshare_strinfo (nextsi
);
819 si
->next
= nextsi
->idx
;
822 chainsi
= unshare_strinfo (chainsi
);
823 if (chainsi
->first
== 0)
824 chainsi
->first
= chainsi
->idx
;
826 if (chainsi
->endptr
== NULL_TREE
&& zero_length_string_p (si
))
827 chainsi
->endptr
= ptr
;
828 si
->endptr
= chainsi
->endptr
;
829 si
->prev
= chainsi
->idx
;
830 si
->first
= chainsi
->first
;
831 si
->writable
= chainsi
->writable
;
835 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
836 to a zero-length string and if possible chain it to a related strinfo
837 chain whose part is or might be CHAINSI. */
840 zero_length_string (tree ptr
, strinfo
*chainsi
)
844 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
845 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
846 gcc_checking_assert (TREE_CODE (ptr
) == SSA_NAME
847 && ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] == 0);
849 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
853 si
= verify_related_strinfos (chainsi
);
858 /* We shouldn't mix delayed and non-delayed lengths. */
859 gcc_assert (si
->full_string_p
);
860 if (si
->endptr
== NULL_TREE
)
862 si
= unshare_strinfo (si
);
866 si
= get_next_strinfo (si
);
869 if (zero_length_string_p (chainsi
))
873 chainsi
= unshare_strinfo (chainsi
);
876 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = chainsi
->idx
;
882 /* We shouldn't mix delayed and non-delayed lengths. */
883 gcc_assert (chainsi
->full_string_p
);
884 if (chainsi
->first
|| chainsi
->prev
|| chainsi
->next
)
886 chainsi
= unshare_strinfo (chainsi
);
893 idx
= new_stridx (ptr
);
896 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, 0), true);
897 set_strinfo (idx
, si
);
901 chainsi
= unshare_strinfo (chainsi
);
902 if (chainsi
->first
== 0)
903 chainsi
->first
= chainsi
->idx
;
905 if (chainsi
->endptr
== NULL_TREE
)
906 chainsi
->endptr
= ptr
;
907 si
->prev
= chainsi
->idx
;
908 si
->first
= chainsi
->first
;
909 si
->writable
= chainsi
->writable
;
914 /* For strinfo ORIGSI whose length has been just updated, adjust other
915 related strinfos so that they match the new ORIGSI. This involves:
917 - adding ADJ to the nonzero_chars fields
918 - copying full_string_p from the new ORIGSI. */
921 adjust_related_strinfos (location_t loc
, strinfo
*origsi
, tree adj
)
923 strinfo
*si
= verify_related_strinfos (origsi
);
936 si
= unshare_strinfo (si
);
937 /* We shouldn't see delayed lengths here; the caller must
938 have calculated the old length in order to calculate
940 gcc_assert (si
->nonzero_chars
);
941 tem
= fold_convert_loc (loc
, TREE_TYPE (si
->nonzero_chars
), adj
);
942 si
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
943 TREE_TYPE (si
->nonzero_chars
),
944 si
->nonzero_chars
, tem
);
945 si
->full_string_p
= origsi
->full_string_p
;
947 si
->endptr
= NULL_TREE
;
948 si
->dont_invalidate
= true;
950 nsi
= get_next_strinfo (si
);
957 /* Find if there are other SSA_NAME pointers equal to PTR
958 for which we don't track their string lengths yet. If so, use
962 find_equal_ptrs (tree ptr
, int idx
)
964 if (TREE_CODE (ptr
) != SSA_NAME
)
968 gimple
*stmt
= SSA_NAME_DEF_STMT (ptr
);
969 if (!is_gimple_assign (stmt
))
971 ptr
= gimple_assign_rhs1 (stmt
);
972 switch (gimple_assign_rhs_code (stmt
))
977 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)))
979 if (TREE_CODE (ptr
) == SSA_NAME
)
981 if (TREE_CODE (ptr
) != ADDR_EXPR
)
986 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
987 if (pidx
!= NULL
&& *pidx
== 0)
995 /* We might find an endptr created in this pass. Grow the
996 vector in that case. */
997 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
998 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
1000 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] != 0)
1002 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = idx
;
1006 /* Return true if STMT is a call to a builtin function with the right
1007 arguments and attributes that should be considered for optimization
1011 valid_builtin_call (gimple
*stmt
)
1013 if (!gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
1016 tree callee
= gimple_call_fndecl (stmt
);
1017 tree decl
= builtin_decl_explicit (DECL_FUNCTION_CODE (callee
));
1020 && !gimple_builtin_call_types_compatible_p (stmt
, decl
))
1023 switch (DECL_FUNCTION_CODE (callee
))
1025 case BUILT_IN_MEMCMP
:
1026 case BUILT_IN_MEMCMP_EQ
:
1027 case BUILT_IN_STRCMP
:
1028 case BUILT_IN_STRNCMP
:
1029 case BUILT_IN_STRCHR
:
1030 case BUILT_IN_STRLEN
:
1031 case BUILT_IN_STRNLEN
:
1032 /* The above functions should be pure. Punt if they aren't. */
1033 if (gimple_vdef (stmt
) || gimple_vuse (stmt
) == NULL_TREE
)
1037 case BUILT_IN_CALLOC
:
1038 case BUILT_IN_MALLOC
:
1039 case BUILT_IN_MEMCPY
:
1040 case BUILT_IN_MEMCPY_CHK
:
1041 case BUILT_IN_MEMPCPY
:
1042 case BUILT_IN_MEMPCPY_CHK
:
1043 case BUILT_IN_MEMSET
:
1044 case BUILT_IN_STPCPY
:
1045 case BUILT_IN_STPCPY_CHK
:
1046 case BUILT_IN_STPNCPY
:
1047 case BUILT_IN_STPNCPY_CHK
:
1048 case BUILT_IN_STRCAT
:
1049 case BUILT_IN_STRCAT_CHK
:
1050 case BUILT_IN_STRCPY
:
1051 case BUILT_IN_STRCPY_CHK
:
1052 case BUILT_IN_STRNCAT
:
1053 case BUILT_IN_STRNCAT_CHK
:
1054 case BUILT_IN_STRNCPY
:
1055 case BUILT_IN_STRNCPY_CHK
:
1056 /* The above functions should be neither const nor pure. Punt if they
1058 if (gimple_vdef (stmt
) == NULL_TREE
|| gimple_vuse (stmt
) == NULL_TREE
)
1069 /* If the last .MEM setter statement before STMT is
1070 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
1071 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
1072 just memcpy (x, y, strlen (y)). SI must be the zero length
1076 adjust_last_stmt (strinfo
*si
, gimple
*stmt
, bool is_strcat
)
1078 tree vuse
, callee
, len
;
1079 struct laststmt_struct last
= laststmt
;
1080 strinfo
*lastsi
, *firstsi
;
1081 unsigned len_arg_no
= 2;
1083 laststmt
.stmt
= NULL
;
1084 laststmt
.len
= NULL_TREE
;
1085 laststmt
.stridx
= 0;
1087 if (last
.stmt
== NULL
)
1090 vuse
= gimple_vuse (stmt
);
1091 if (vuse
== NULL_TREE
1092 || SSA_NAME_DEF_STMT (vuse
) != last
.stmt
1093 || !has_single_use (vuse
))
1096 gcc_assert (last
.stridx
> 0);
1097 lastsi
= get_strinfo (last
.stridx
);
1103 if (lastsi
->first
== 0 || lastsi
->first
!= si
->first
)
1106 firstsi
= verify_related_strinfos (si
);
1107 if (firstsi
== NULL
)
1109 while (firstsi
!= lastsi
)
1111 firstsi
= get_next_strinfo (firstsi
);
1112 if (firstsi
== NULL
)
1117 if (!is_strcat
&& !zero_length_string_p (si
))
1120 if (is_gimple_assign (last
.stmt
))
1122 gimple_stmt_iterator gsi
;
1124 if (!integer_zerop (gimple_assign_rhs1 (last
.stmt
)))
1126 if (stmt_could_throw_p (cfun
, last
.stmt
))
1128 gsi
= gsi_for_stmt (last
.stmt
);
1129 unlink_stmt_vdef (last
.stmt
);
1130 release_defs (last
.stmt
);
1131 gsi_remove (&gsi
, true);
1135 if (!valid_builtin_call (last
.stmt
))
1138 callee
= gimple_call_fndecl (last
.stmt
);
1139 switch (DECL_FUNCTION_CODE (callee
))
1141 case BUILT_IN_MEMCPY
:
1142 case BUILT_IN_MEMCPY_CHK
:
1148 len
= gimple_call_arg (last
.stmt
, len_arg_no
);
1149 if (tree_fits_uhwi_p (len
))
1151 if (!tree_fits_uhwi_p (last
.len
)
1152 || integer_zerop (len
)
1153 || tree_to_uhwi (len
) != tree_to_uhwi (last
.len
) + 1)
1155 /* Don't adjust the length if it is divisible by 4, it is more efficient
1156 to store the extra '\0' in that case. */
1157 if ((tree_to_uhwi (len
) & 3) == 0)
1160 /* Don't fold away an out of bounds access, as this defeats proper
1162 tree dst
= gimple_call_arg (last
.stmt
, 0);
1163 tree size
= compute_objsize (dst
, 0);
1164 if (size
&& tree_int_cst_lt (size
, len
))
1167 else if (TREE_CODE (len
) == SSA_NAME
)
1169 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1170 if (!is_gimple_assign (def_stmt
)
1171 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1172 || gimple_assign_rhs1 (def_stmt
) != last
.len
1173 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1179 gimple_call_set_arg (last
.stmt
, len_arg_no
, last
.len
);
1180 update_stmt (last
.stmt
);
1183 /* For an LHS that is an SSA_NAME that is the result of a strlen()
1184 call, or when BOUND is non-null, of a strnlen() call, set LHS
1185 range info to [0, min (MAX, BOUND)] when the range includes more
1186 than one value and return LHS. Otherwise, when the range
1187 [MIN, MAX] is such that MIN == MAX, return the tree representation
1188 of (MIN). The latter allows callers to fold suitable strnlen() calls
1192 set_strlen_range (tree lhs
, wide_int max
, tree bound
/* = NULL_TREE */)
1194 if (TREE_CODE (lhs
) != SSA_NAME
1195 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
1198 wide_int min
= wi::zero (max
.get_precision ());
1202 /* For strnlen, adjust MIN and MAX as necessary. If the bound
1203 is less than the size of the array set MAX to it. It it's
1204 greater than MAX and MAX is non-zero bump MAX down to account
1205 for the necessary terminating nul. Otherwise leave it alone. */
1206 if (TREE_CODE (bound
) == INTEGER_CST
)
1208 wide_int wibnd
= wi::to_wide (bound
);
1209 int cmp
= wi::cmpu (wibnd
, max
);
1212 else if (cmp
&& wi::ne_p (max
, min
))
1215 else if (TREE_CODE (bound
) == SSA_NAME
)
1217 wide_int minbound
, maxbound
;
1218 value_range_kind rng
= get_range_info (bound
, &minbound
, &maxbound
);
1219 if (rng
== VR_RANGE
)
1221 /* For a bound in a known range, adjust the range determined
1222 above as necessary. For a bound in some anti-range or
1223 in an unknown range, use the range determined by callers. */
1224 if (wi::ltu_p (minbound
, min
))
1226 if (wi::ltu_p (maxbound
, max
))
1233 return wide_int_to_tree (size_type_node
, min
);
1235 set_range_info (lhs
, VR_RANGE
, min
, max
);
1239 /* For an LHS that is an SSA_NAME and for strlen() or strnlen() argument
1240 SRC, set LHS range info to [0, min (N, BOUND)] if SRC refers to
1241 a character array A[N] with unknown length bounded by N, and for
1242 strnlen(), by min (N, BOUND). */
1245 maybe_set_strlen_range (tree lhs
, tree src
, tree bound
)
1247 if (TREE_CODE (lhs
) != SSA_NAME
1248 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
1251 if (TREE_CODE (src
) == SSA_NAME
)
1253 gimple
*def
= SSA_NAME_DEF_STMT (src
);
1254 if (is_gimple_assign (def
)
1255 && gimple_assign_rhs_code (def
) == ADDR_EXPR
)
1256 src
= gimple_assign_rhs1 (def
);
1259 /* The longest string is PTRDIFF_MAX - 1 bytes including the final
1260 NUL so that the difference between a pointer to just past it and
1261 one to its beginning is positive. */
1262 wide_int max
= wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node
)) - 2;
1264 if (TREE_CODE (src
) == ADDR_EXPR
)
1266 /* The last array member of a struct can be bigger than its size
1267 suggests if it's treated as a poor-man's flexible array member. */
1268 src
= TREE_OPERAND (src
, 0);
1269 if (TREE_CODE (src
) != MEM_REF
1270 && !array_at_struct_end_p (src
))
1272 tree type
= TREE_TYPE (src
);
1273 tree size
= TYPE_SIZE_UNIT (type
);
1275 && TREE_CODE (size
) == INTEGER_CST
1276 && !integer_zerop (size
))
1278 /* Even though such uses of strlen would be undefined,
1279 avoid relying on arrays of arrays in case some genius
1280 decides to call strlen on an unterminated array element
1281 that's followed by a terminated one. Likewise, avoid
1282 assuming that a struct array member is necessarily
1283 nul-terminated (the nul may be in the member that
1284 follows). In those cases, assume that the length
1285 of the string stored in such an array is bounded
1286 by the size of the enclosing object if one can be
1288 tree base
= get_base_address (src
);
1291 if (tree size
= DECL_SIZE_UNIT (base
))
1293 && TREE_CODE (size
) == INTEGER_CST
1294 && TREE_CODE (TREE_TYPE (base
)) != POINTER_TYPE
)
1295 max
= wi::to_wide (size
);
1299 /* For strlen() the upper bound above is equal to
1300 the longest string that can be stored in the array
1301 (i.e., it accounts for the terminating nul. For
1302 strnlen() bump up the maximum by one since the array
1303 need not be nul-terminated. */
1304 if (!bound
&& max
!= 0)
1309 return set_strlen_range (lhs
, max
, bound
);
1312 /* Handle a strlen call. If strlen of the argument is known, replace
1313 the strlen call with the known value, otherwise remember that strlen
1314 of the argument is stored in the lhs SSA_NAME. */
1317 handle_builtin_strlen (gimple_stmt_iterator
*gsi
)
1319 gimple
*stmt
= gsi_stmt (*gsi
);
1320 tree lhs
= gimple_call_lhs (stmt
);
1322 if (lhs
== NULL_TREE
)
1325 location_t loc
= gimple_location (stmt
);
1326 tree callee
= gimple_call_fndecl (stmt
);
1327 tree src
= gimple_call_arg (stmt
, 0);
1328 tree bound
= (DECL_FUNCTION_CODE (callee
) == BUILT_IN_STRNLEN
1329 ? gimple_call_arg (stmt
, 1) : NULL_TREE
);
1330 int idx
= get_stridx (src
);
1331 if (idx
|| (bound
&& integer_zerop (bound
)))
1337 rhs
= build_int_cst (TREE_TYPE (lhs
), ~idx
);
1343 si
= get_strinfo (idx
);
1346 rhs
= get_string_length (si
);
1347 /* For strnlen, if bound is constant, even if si is not known
1348 to be zero terminated, if we know at least bound bytes are
1349 not zero, the return value will be bound. */
1350 if (rhs
== NULL_TREE
1351 && bound
!= NULL_TREE
1352 && TREE_CODE (bound
) == INTEGER_CST
1353 && si
->nonzero_chars
!= NULL_TREE
1354 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
1355 && tree_int_cst_le (bound
, si
->nonzero_chars
))
1359 if (rhs
!= NULL_TREE
)
1361 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1363 fprintf (dump_file
, "Optimizing: ");
1364 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1366 rhs
= unshare_expr (rhs
);
1367 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
1368 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1371 rhs
= fold_build2_loc (loc
, MIN_EXPR
, TREE_TYPE (rhs
), rhs
, bound
);
1373 if (!update_call_from_tree (gsi
, rhs
))
1374 gimplify_and_update_call_from_tree (gsi
, rhs
);
1375 stmt
= gsi_stmt (*gsi
);
1377 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1379 fprintf (dump_file
, "into: ");
1380 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1384 /* Don't update anything for strnlen. */
1385 && bound
== NULL_TREE
1386 && TREE_CODE (si
->nonzero_chars
) != SSA_NAME
1387 && TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
1388 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1390 si
= unshare_strinfo (si
);
1391 si
->nonzero_chars
= lhs
;
1392 gcc_assert (si
->full_string_p
);
1395 if (strlen_to_stridx
1396 && (bound
== NULL_TREE
1397 /* For strnlen record this only if the call is proven
1398 to return the same value as strlen would. */
1399 || (TREE_CODE (bound
) == INTEGER_CST
1400 && TREE_CODE (rhs
) == INTEGER_CST
1401 && tree_int_cst_lt (rhs
, bound
))))
1402 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1407 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1411 idx
= new_stridx (src
);
1414 strinfo
*si
= get_strinfo (idx
);
1417 if (!si
->full_string_p
&& !si
->stmt
)
1419 /* Until now we only had a lower bound on the string length.
1420 Install LHS as the actual length. */
1421 si
= unshare_strinfo (si
);
1422 tree old
= si
->nonzero_chars
;
1423 si
->nonzero_chars
= lhs
;
1424 si
->full_string_p
= true;
1425 if (TREE_CODE (old
) == INTEGER_CST
)
1427 old
= fold_convert_loc (loc
, TREE_TYPE (lhs
), old
);
1428 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1429 TREE_TYPE (lhs
), lhs
, old
);
1430 adjust_related_strinfos (loc
, si
, adj
);
1446 /* Only store the new length information for calls to strlen(),
1447 not for those to strnlen(). */
1448 strinfo
*si
= new_strinfo (src
, idx
, lhs
, true);
1449 set_strinfo (idx
, si
);
1450 find_equal_ptrs (src
, idx
);
1453 /* For SRC that is an array of N elements, set LHS's range
1454 to [0, min (N, BOUND)]. A constant return value means
1455 the range would have consisted of a single value. In
1456 that case, fold the result into the returned constant. */
1457 if (tree ret
= maybe_set_strlen_range (lhs
, src
, bound
))
1458 if (TREE_CODE (ret
) == INTEGER_CST
)
1460 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1462 fprintf (dump_file
, "Optimizing: ");
1463 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1465 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (ret
)))
1466 ret
= fold_convert_loc (loc
, TREE_TYPE (lhs
), ret
);
1467 if (!update_call_from_tree (gsi
, ret
))
1468 gimplify_and_update_call_from_tree (gsi
, ret
);
1469 stmt
= gsi_stmt (*gsi
);
1471 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1473 fprintf (dump_file
, "into: ");
1474 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1478 if (strlen_to_stridx
&& !bound
)
1479 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1483 /* Handle a strchr call. If strlen of the first argument is known, replace
1484 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
1485 that lhs of the call is endptr and strlen of the argument is endptr - x. */
1488 handle_builtin_strchr (gimple_stmt_iterator
*gsi
)
1492 gimple
*stmt
= gsi_stmt (*gsi
);
1493 tree lhs
= gimple_call_lhs (stmt
);
1495 if (lhs
== NULL_TREE
)
1498 if (!integer_zerop (gimple_call_arg (stmt
, 1)))
1501 src
= gimple_call_arg (stmt
, 0);
1502 idx
= get_stridx (src
);
1509 rhs
= build_int_cst (size_type_node
, ~idx
);
1513 si
= get_strinfo (idx
);
1515 rhs
= get_string_length (si
);
1517 if (rhs
!= NULL_TREE
)
1519 location_t loc
= gimple_location (stmt
);
1521 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1523 fprintf (dump_file
, "Optimizing: ");
1524 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1526 if (si
!= NULL
&& si
->endptr
!= NULL_TREE
)
1528 rhs
= unshare_expr (si
->endptr
);
1529 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1531 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1535 rhs
= fold_convert_loc (loc
, sizetype
, unshare_expr (rhs
));
1536 rhs
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1537 TREE_TYPE (src
), src
, rhs
);
1538 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1540 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1542 if (!update_call_from_tree (gsi
, rhs
))
1543 gimplify_and_update_call_from_tree (gsi
, rhs
);
1544 stmt
= gsi_stmt (*gsi
);
1546 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1548 fprintf (dump_file
, "into: ");
1549 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1552 && si
->endptr
== NULL_TREE
1553 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1555 si
= unshare_strinfo (si
);
1558 zero_length_string (lhs
, si
);
1562 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1564 if (TREE_CODE (src
) != SSA_NAME
|| !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src
))
1567 idx
= new_stridx (src
);
1568 else if (get_strinfo (idx
) != NULL
)
1570 zero_length_string (lhs
, NULL
);
1575 location_t loc
= gimple_location (stmt
);
1576 tree lhsu
= fold_convert_loc (loc
, size_type_node
, lhs
);
1577 tree srcu
= fold_convert_loc (loc
, size_type_node
, src
);
1578 tree length
= fold_build2_loc (loc
, MINUS_EXPR
,
1579 size_type_node
, lhsu
, srcu
);
1580 strinfo
*si
= new_strinfo (src
, idx
, length
, true);
1582 set_strinfo (idx
, si
);
1583 find_equal_ptrs (src
, idx
);
1584 zero_length_string (lhs
, si
);
1588 zero_length_string (lhs
, NULL
);
1591 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1592 If strlen of the second argument is known, strlen of the first argument
1593 is the same after this call. Furthermore, attempt to convert it to
1597 handle_builtin_strcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1600 tree src
, dst
, srclen
, len
, lhs
, type
, fn
, oldlen
;
1602 gimple
*stmt
= gsi_stmt (*gsi
);
1603 strinfo
*si
, *dsi
, *olddsi
, *zsi
;
1606 src
= gimple_call_arg (stmt
, 1);
1607 dst
= gimple_call_arg (stmt
, 0);
1608 lhs
= gimple_call_lhs (stmt
);
1609 idx
= get_stridx (src
);
1612 si
= get_strinfo (idx
);
1614 didx
= get_stridx (dst
);
1618 olddsi
= get_strinfo (didx
);
1623 adjust_last_stmt (olddsi
, stmt
, false);
1627 srclen
= get_string_length (si
);
1629 srclen
= build_int_cst (size_type_node
, ~idx
);
1631 loc
= gimple_location (stmt
);
1632 if (srclen
== NULL_TREE
)
1635 case BUILT_IN_STRCPY
:
1636 case BUILT_IN_STRCPY_CHK
:
1637 if (lhs
!= NULL_TREE
|| !builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1640 case BUILT_IN_STPCPY
:
1641 case BUILT_IN_STPCPY_CHK
:
1642 if (lhs
== NULL_TREE
)
1646 tree lhsuint
= fold_convert_loc (loc
, size_type_node
, lhs
);
1647 srclen
= fold_convert_loc (loc
, size_type_node
, dst
);
1648 srclen
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
1658 didx
= new_stridx (dst
);
1664 oldlen
= olddsi
->nonzero_chars
;
1665 dsi
= unshare_strinfo (olddsi
);
1666 dsi
->nonzero_chars
= srclen
;
1667 dsi
->full_string_p
= (srclen
!= NULL_TREE
);
1668 /* Break the chain, so adjust_related_strinfo on later pointers in
1669 the chain won't adjust this one anymore. */
1672 dsi
->endptr
= NULL_TREE
;
1676 dsi
= new_strinfo (dst
, didx
, srclen
, srclen
!= NULL_TREE
);
1677 set_strinfo (didx
, dsi
);
1678 find_equal_ptrs (dst
, didx
);
1680 dsi
->writable
= true;
1681 dsi
->dont_invalidate
= true;
1683 if (dsi
->nonzero_chars
== NULL_TREE
)
1687 /* If string length of src is unknown, use delayed length
1688 computation. If string lenth of dst will be needed, it
1689 can be computed by transforming this strcpy call into
1690 stpcpy and subtracting dst from the return value. */
1692 /* Look for earlier strings whose length could be determined if
1693 this strcpy is turned into an stpcpy. */
1695 if (dsi
->prev
!= 0 && (chainsi
= verify_related_strinfos (dsi
)) != NULL
)
1697 for (; chainsi
&& chainsi
!= dsi
; chainsi
= get_strinfo (chainsi
->next
))
1699 /* When setting a stmt for delayed length computation
1700 prevent all strinfos through dsi from being
1702 chainsi
= unshare_strinfo (chainsi
);
1703 chainsi
->stmt
= stmt
;
1704 chainsi
->nonzero_chars
= NULL_TREE
;
1705 chainsi
->full_string_p
= false;
1706 chainsi
->endptr
= NULL_TREE
;
1707 chainsi
->dont_invalidate
= true;
1712 /* Try to detect overlap before returning. This catches cases
1713 like strcpy (d, d + n) where n is non-constant whose range
1714 is such that (n <= strlen (d) holds).
1716 OLDDSI->NONZERO_chars may have been reset by this point with
1717 oldlen holding it original value. */
1718 if (olddsi
&& oldlen
)
1720 /* Add 1 for the terminating NUL. */
1721 tree type
= TREE_TYPE (oldlen
);
1722 oldlen
= fold_build2 (PLUS_EXPR
, type
, oldlen
,
1723 build_int_cst (type
, 1));
1724 check_bounds_or_overlap (stmt
, olddsi
->ptr
, src
, oldlen
, NULL_TREE
);
1732 tree adj
= NULL_TREE
;
1733 if (oldlen
== NULL_TREE
)
1735 else if (integer_zerop (oldlen
))
1737 else if (TREE_CODE (oldlen
) == INTEGER_CST
1738 || TREE_CODE (srclen
) == INTEGER_CST
)
1739 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1740 TREE_TYPE (srclen
), srclen
,
1741 fold_convert_loc (loc
, TREE_TYPE (srclen
),
1743 if (adj
!= NULL_TREE
)
1744 adjust_related_strinfos (loc
, dsi
, adj
);
1748 /* strcpy src may not overlap dst, so src doesn't need to be
1749 invalidated either. */
1751 si
->dont_invalidate
= true;
1757 case BUILT_IN_STRCPY
:
1758 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1760 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1762 case BUILT_IN_STRCPY_CHK
:
1763 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1765 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1767 case BUILT_IN_STPCPY
:
1768 /* This would need adjustment of the lhs (subtract one),
1769 or detection that the trailing '\0' doesn't need to be
1770 written, if it will be immediately overwritten.
1771 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1775 zsi
= zero_length_string (lhs
, dsi
);
1778 case BUILT_IN_STPCPY_CHK
:
1779 /* This would need adjustment of the lhs (subtract one),
1780 or detection that the trailing '\0' doesn't need to be
1781 written, if it will be immediately overwritten.
1782 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1786 zsi
= zero_length_string (lhs
, dsi
);
1793 zsi
->dont_invalidate
= true;
1797 tree args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1798 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1801 type
= size_type_node
;
1803 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1804 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
, build_int_cst (type
, 1));
1806 /* Set the no-warning bit on the transformed statement? */
1807 bool set_no_warning
= false;
1809 if (const strinfo
*chksi
= olddsi
? olddsi
: dsi
)
1811 && check_bounds_or_overlap (stmt
, chksi
->ptr
, si
->ptr
, NULL_TREE
, len
))
1813 gimple_set_no_warning (stmt
, true);
1814 set_no_warning
= true;
1817 if (fn
== NULL_TREE
)
1820 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1822 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1824 fprintf (dump_file
, "Optimizing: ");
1825 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1827 if (gimple_call_num_args (stmt
) == 2)
1828 success
= update_gimple_call (gsi
, fn
, 3, dst
, src
, len
);
1830 success
= update_gimple_call (gsi
, fn
, 4, dst
, src
, len
,
1831 gimple_call_arg (stmt
, 2));
1834 stmt
= gsi_stmt (*gsi
);
1836 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1838 fprintf (dump_file
, "into: ");
1839 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1841 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1842 laststmt
.stmt
= stmt
;
1843 laststmt
.len
= srclen
;
1844 laststmt
.stridx
= dsi
->idx
;
1846 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1847 fprintf (dump_file
, "not possible.\n");
1850 gimple_set_no_warning (stmt
, true);
1853 /* Check the size argument to the built-in forms of stpncpy and strncpy
1854 for out-of-bounds offsets or overlapping access, and to see if the
1855 size argument is derived from a call to strlen() on the source argument,
1856 and if so, issue an appropriate warning. */
1859 handle_builtin_strncat (built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1861 /* Same as stxncpy(). */
1862 handle_builtin_stxncpy (bcode
, gsi
);
1865 /* Return true if LEN depends on a call to strlen(SRC) in an interesting
1866 way. LEN can either be an integer expression, or a pointer (to char).
1867 When it is the latter (such as in recursive calls to self) is is
1868 assumed to be the argument in some call to strlen() whose relationship
1869 to SRC is being ascertained. */
1872 is_strlen_related_p (tree src
, tree len
)
1874 if (TREE_CODE (TREE_TYPE (len
)) == POINTER_TYPE
1875 && operand_equal_p (src
, len
, 0))
1878 if (TREE_CODE (len
) != SSA_NAME
)
1881 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1885 if (is_gimple_call (def_stmt
))
1887 tree func
= gimple_call_fndecl (def_stmt
);
1888 if (!valid_builtin_call (def_stmt
)
1889 || DECL_FUNCTION_CODE (func
) != BUILT_IN_STRLEN
)
1892 tree arg
= gimple_call_arg (def_stmt
, 0);
1893 return is_strlen_related_p (src
, arg
);
1896 if (!is_gimple_assign (def_stmt
))
1899 tree_code code
= gimple_assign_rhs_code (def_stmt
);
1900 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1901 tree rhstype
= TREE_TYPE (rhs1
);
1903 if ((TREE_CODE (rhstype
) == POINTER_TYPE
&& code
== POINTER_PLUS_EXPR
)
1904 || (INTEGRAL_TYPE_P (rhstype
)
1905 && (code
== BIT_AND_EXPR
1906 || code
== NOP_EXPR
)))
1908 /* Pointer plus (an integer), and truncation are considered among
1909 the (potentially) related expressions to strlen. */
1910 return is_strlen_related_p (src
, rhs1
);
1913 if (tree rhs2
= gimple_assign_rhs2 (def_stmt
))
1915 /* Integer subtraction is considered strlen-related when both
1916 arguments are integers and second one is strlen-related. */
1917 rhstype
= TREE_TYPE (rhs2
);
1918 if (INTEGRAL_TYPE_P (rhstype
) && code
== MINUS_EXPR
)
1919 return is_strlen_related_p (src
, rhs2
);
1925 /* Called by handle_builtin_stxncpy and by gimple_fold_builtin_strncpy
1927 Check to see if the specified bound is a) equal to the size of
1928 the destination DST and if so, b) if it's immediately followed by
1929 DST[CNT - 1] = '\0'. If a) holds and b) does not, warn. Otherwise,
1930 do nothing. Return true if diagnostic has been issued.
1932 The purpose is to diagnose calls to strncpy and stpncpy that do
1933 not nul-terminate the copy while allowing for the idiom where
1934 such a call is immediately followed by setting the last element
1937 strncpy (a, s, sizeof a);
1938 a[sizeof a - 1] = '\0';
1942 maybe_diag_stxncpy_trunc (gimple_stmt_iterator gsi
, tree src
, tree cnt
)
1944 gimple
*stmt
= gsi_stmt (gsi
);
1945 if (gimple_no_warning_p (stmt
))
1948 wide_int cntrange
[2];
1950 if (TREE_CODE (cnt
) == INTEGER_CST
)
1951 cntrange
[0] = cntrange
[1] = wi::to_wide (cnt
);
1952 else if (TREE_CODE (cnt
) == SSA_NAME
)
1954 enum value_range_kind rng
= get_range_info (cnt
, cntrange
, cntrange
+ 1);
1955 if (rng
== VR_RANGE
)
1957 else if (rng
== VR_ANTI_RANGE
)
1959 wide_int maxobjsize
= wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node
));
1961 if (wi::ltu_p (cntrange
[1], maxobjsize
))
1963 cntrange
[0] = cntrange
[1] + 1;
1964 cntrange
[1] = maxobjsize
;
1968 cntrange
[1] = cntrange
[0] - 1;
1969 cntrange
[0] = wi::zero (TYPE_PRECISION (TREE_TYPE (cnt
)));
1978 /* Negative value is the constant string length. If it's less than
1979 the lower bound there is no truncation. Avoid calling get_stridx()
1980 when ssa_ver_to_stridx is empty. That implies the caller isn't
1981 running under the control of this pass and ssa_ver_to_stridx hasn't
1982 been created yet. */
1983 int sidx
= ssa_ver_to_stridx
.length () ? get_stridx (src
) : 0;
1984 if (sidx
< 0 && wi::gtu_p (cntrange
[0], ~sidx
))
1987 tree dst
= gimple_call_arg (stmt
, 0);
1989 if (TREE_CODE (dstdecl
) == ADDR_EXPR
)
1990 dstdecl
= TREE_OPERAND (dstdecl
, 0);
1992 tree ref
= NULL_TREE
;
1996 /* If the source is a non-string return early to avoid warning
1997 for possible truncation (if the truncation is certain SIDX
1999 tree srcdecl
= gimple_call_arg (stmt
, 1);
2000 if (TREE_CODE (srcdecl
) == ADDR_EXPR
)
2001 srcdecl
= TREE_OPERAND (srcdecl
, 0);
2002 if (get_attr_nonstring_decl (srcdecl
, &ref
))
2006 /* Likewise, if the destination refers to a an array/pointer declared
2007 nonstring return early. */
2008 if (get_attr_nonstring_decl (dstdecl
, &ref
))
2011 /* Look for dst[i] = '\0'; after the stxncpy() call and if found
2012 avoid the truncation warning. */
2013 gsi_next_nondebug (&gsi
);
2014 gimple
*next_stmt
= gsi_stmt (gsi
);
2017 /* When there is no statement in the same basic block check
2018 the immediate successor block. */
2019 if (basic_block bb
= gimple_bb (stmt
))
2021 if (single_succ_p (bb
))
2023 /* For simplicity, ignore blocks with multiple outgoing
2024 edges for now and only consider successor blocks along
2026 edge e
= EDGE_SUCC (bb
, 0);
2027 if (!(e
->flags
& EDGE_ABNORMAL
))
2029 gsi
= gsi_start_bb (e
->dest
);
2030 next_stmt
= gsi_stmt (gsi
);
2031 if (next_stmt
&& is_gimple_debug (next_stmt
))
2033 gsi_next_nondebug (&gsi
);
2034 next_stmt
= gsi_stmt (gsi
);
2041 if (next_stmt
&& is_gimple_assign (next_stmt
))
2043 tree lhs
= gimple_assign_lhs (next_stmt
);
2044 tree_code code
= TREE_CODE (lhs
);
2045 if (code
== ARRAY_REF
|| code
== MEM_REF
)
2046 lhs
= TREE_OPERAND (lhs
, 0);
2048 tree func
= gimple_call_fndecl (stmt
);
2049 if (DECL_FUNCTION_CODE (func
) == BUILT_IN_STPNCPY
)
2051 tree ret
= gimple_call_lhs (stmt
);
2052 if (ret
&& operand_equal_p (ret
, lhs
, 0))
2056 /* Determine the base address and offset of the reference,
2057 ignoring the innermost array index. */
2058 if (TREE_CODE (ref
) == ARRAY_REF
)
2059 ref
= TREE_OPERAND (ref
, 0);
2062 tree dstbase
= get_addr_base_and_unit_offset (ref
, &dstoff
);
2065 tree lhsbase
= get_addr_base_and_unit_offset (lhs
, &lhsoff
);
2068 && known_eq (dstoff
, lhsoff
)
2069 && operand_equal_p (dstbase
, lhsbase
, 0))
2073 int prec
= TYPE_PRECISION (TREE_TYPE (cnt
));
2074 wide_int lenrange
[2];
2075 if (strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
)
2077 lenrange
[0] = (sisrc
->nonzero_chars
2078 && TREE_CODE (sisrc
->nonzero_chars
) == INTEGER_CST
2079 ? wi::to_wide (sisrc
->nonzero_chars
)
2081 lenrange
[1] = lenrange
[0];
2084 lenrange
[0] = lenrange
[1] = wi::shwi (~sidx
, prec
);
2087 c_strlen_data lendata
= { };
2088 get_range_strlen (src
, &lendata
, /* eltsize = */1);
2089 if (TREE_CODE (lendata
.minlen
) == INTEGER_CST
2090 && TREE_CODE (lendata
.maxbound
) == INTEGER_CST
)
2092 /* When LENDATA.MAXLEN is unknown, reset LENDATA.MINLEN
2093 which stores the length of the shortest known string. */
2094 if (integer_all_onesp (lendata
.maxlen
))
2095 lenrange
[0] = wi::shwi (0, prec
);
2097 lenrange
[0] = wi::to_wide (lendata
.minlen
, prec
);
2098 lenrange
[1] = wi::to_wide (lendata
.maxbound
, prec
);
2102 lenrange
[0] = wi::shwi (0, prec
);
2103 lenrange
[1] = wi::shwi (-1, prec
);
2107 location_t callloc
= gimple_nonartificial_location (stmt
);
2108 callloc
= expansion_point_location_if_in_system_header (callloc
);
2110 tree func
= gimple_call_fndecl (stmt
);
2112 if (lenrange
[0] != 0 || !wi::neg_p (lenrange
[1]))
2114 /* If the longest source string is shorter than the lower bound
2115 of the specified count the copy is definitely nul-terminated. */
2116 if (wi::ltu_p (lenrange
[1], cntrange
[0]))
2119 if (wi::neg_p (lenrange
[1]))
2121 /* The length of one of the strings is unknown but at least
2122 one has non-zero length and that length is stored in
2123 LENRANGE[1]. Swap the bounds to force a "may be truncated"
2125 lenrange
[1] = lenrange
[0];
2126 lenrange
[0] = wi::shwi (0, prec
);
2129 /* Set to true for strncat whose bound is derived from the length
2130 of the destination (the expected usage pattern). */
2131 bool cat_dstlen_bounded
= false;
2132 if (DECL_FUNCTION_CODE (func
) == BUILT_IN_STRNCAT
)
2133 cat_dstlen_bounded
= is_strlen_related_p (dst
, cnt
);
2135 if (lenrange
[0] == cntrange
[1] && cntrange
[0] == cntrange
[1])
2136 return warning_n (callloc
, OPT_Wstringop_truncation
,
2137 cntrange
[0].to_uhwi (),
2138 "%G%qD output truncated before terminating "
2139 "nul copying %E byte from a string of the "
2141 "%G%qD output truncated before terminating nul "
2142 "copying %E bytes from a string of the same "
2145 else if (!cat_dstlen_bounded
)
2147 if (wi::geu_p (lenrange
[0], cntrange
[1]))
2149 /* The shortest string is longer than the upper bound of
2150 the count so the truncation is certain. */
2151 if (cntrange
[0] == cntrange
[1])
2152 return warning_n (callloc
, OPT_Wstringop_truncation
,
2153 cntrange
[0].to_uhwi (),
2154 "%G%qD output truncated copying %E byte "
2155 "from a string of length %wu",
2156 "%G%qD output truncated copying %E bytes "
2157 "from a string of length %wu",
2158 stmt
, func
, cnt
, lenrange
[0].to_uhwi ());
2160 return warning_at (callloc
, OPT_Wstringop_truncation
,
2161 "%G%qD output truncated copying between %wu "
2162 "and %wu bytes from a string of length %wu",
2163 stmt
, func
, cntrange
[0].to_uhwi (),
2164 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
2166 else if (wi::geu_p (lenrange
[1], cntrange
[1]))
2168 /* The longest string is longer than the upper bound of
2169 the count so the truncation is possible. */
2170 if (cntrange
[0] == cntrange
[1])
2171 return warning_n (callloc
, OPT_Wstringop_truncation
,
2172 cntrange
[0].to_uhwi (),
2173 "%G%qD output may be truncated copying %E "
2174 "byte from a string of length %wu",
2175 "%G%qD output may be truncated copying %E "
2176 "bytes from a string of length %wu",
2177 stmt
, func
, cnt
, lenrange
[1].to_uhwi ());
2179 return warning_at (callloc
, OPT_Wstringop_truncation
,
2180 "%G%qD output may be truncated copying between "
2181 "%wu and %wu bytes from a string of length %wu",
2182 stmt
, func
, cntrange
[0].to_uhwi (),
2183 cntrange
[1].to_uhwi (), lenrange
[1].to_uhwi ());
2187 if (!cat_dstlen_bounded
2188 && cntrange
[0] != cntrange
[1]
2189 && wi::leu_p (cntrange
[0], lenrange
[0])
2190 && wi::leu_p (cntrange
[1], lenrange
[0] + 1))
2192 /* If the source (including the terminating nul) is longer than
2193 the lower bound of the specified count but shorter than the
2194 upper bound the copy may (but need not) be truncated. */
2195 return warning_at (callloc
, OPT_Wstringop_truncation
,
2196 "%G%qD output may be truncated copying between "
2197 "%wu and %wu bytes from a string of length %wu",
2198 stmt
, func
, cntrange
[0].to_uhwi (),
2199 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
2203 if (tree dstsize
= compute_objsize (dst
, 1))
2205 /* The source length is uknown. Try to determine the destination
2206 size and see if it matches the specified bound. If not, bail.
2207 Otherwise go on to see if it should be diagnosed for possible
2212 if (wi::to_wide (dstsize
) != cntrange
[1])
2215 /* Avoid warning for strncpy(a, b, N) calls where the following
2217 N == sizeof a && N == sizeof b */
2218 if (tree srcsize
= compute_objsize (src
, 1))
2219 if (wi::to_wide (srcsize
) == cntrange
[1])
2222 if (cntrange
[0] == cntrange
[1])
2223 return warning_at (callloc
, OPT_Wstringop_truncation
,
2224 "%G%qD specified bound %E equals destination size",
2231 /* Check the arguments to the built-in forms of stpncpy and strncpy for
2232 out-of-bounds offsets or overlapping access, and to see if the size
2233 is derived from calling strlen() on the source argument, and if so,
2234 issue the appropriate warning. */
2237 handle_builtin_stxncpy (built_in_function
, gimple_stmt_iterator
*gsi
)
2239 if (!strlen_to_stridx
)
2242 gimple
*stmt
= gsi_stmt (*gsi
);
2244 tree dst
= gimple_call_arg (stmt
, 0);
2245 tree src
= gimple_call_arg (stmt
, 1);
2246 tree len
= gimple_call_arg (stmt
, 2);
2247 tree dstsize
= NULL_TREE
, srcsize
= NULL_TREE
;
2249 int didx
= get_stridx (dst
);
2250 if (strinfo
*sidst
= didx
> 0 ? get_strinfo (didx
) : NULL
)
2252 /* Compute the size of the destination string including the nul
2253 if it is known to be nul-terminated. */
2254 if (sidst
->nonzero_chars
)
2256 if (sidst
->full_string_p
)
2258 /* String is known to be nul-terminated. */
2259 tree type
= TREE_TYPE (sidst
->nonzero_chars
);
2260 dstsize
= fold_build2 (PLUS_EXPR
, type
, sidst
->nonzero_chars
,
2261 build_int_cst (type
, 1));
2264 dstsize
= sidst
->nonzero_chars
;
2270 int sidx
= get_stridx (src
);
2271 strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
;
2274 /* strncat() and strncpy() can modify the source string by writing
2275 over the terminating nul so SISRC->DONT_INVALIDATE must be left
2278 /* Compute the size of the source string including the terminating
2279 nul if its known to be nul-terminated. */
2280 if (sisrc
->nonzero_chars
)
2282 if (sisrc
->full_string_p
)
2284 tree type
= TREE_TYPE (sisrc
->nonzero_chars
);
2285 srcsize
= fold_build2 (PLUS_EXPR
, type
, sisrc
->nonzero_chars
,
2286 build_int_cst (type
, 1));
2289 srcsize
= sisrc
->nonzero_chars
;
2295 srcsize
= NULL_TREE
;
2297 if (check_bounds_or_overlap (stmt
, dst
, src
, dstsize
, srcsize
))
2299 gimple_set_no_warning (stmt
, true);
2303 /* If the length argument was computed from strlen(S) for some string
2304 S retrieve the strinfo index for the string (PSS->FIRST) alonng with
2305 the location of the strlen() call (PSS->SECOND). */
2306 stridx_strlenloc
*pss
= strlen_to_stridx
->get (len
);
2307 if (!pss
|| pss
->first
<= 0)
2309 if (maybe_diag_stxncpy_trunc (*gsi
, src
, len
))
2310 gimple_set_no_warning (stmt
, true);
2315 /* Retrieve the strinfo data for the string S that LEN was computed
2316 from as some function F of strlen (S) (i.e., LEN need not be equal
2318 strinfo
*silen
= get_strinfo (pss
->first
);
2320 location_t callloc
= gimple_nonartificial_location (stmt
);
2321 callloc
= expansion_point_location_if_in_system_header (callloc
);
2323 tree func
= gimple_call_fndecl (stmt
);
2325 bool warned
= false;
2327 /* When -Wstringop-truncation is set, try to determine truncation
2328 before diagnosing possible overflow. Truncation is implied by
2329 the LEN argument being equal to strlen(SRC), regardless of
2330 whether its value is known. Otherwise, issue the more generic
2331 -Wstringop-overflow which triggers for LEN arguments that in
2332 any meaningful way depend on strlen(SRC). */
2334 && is_strlen_related_p (src
, len
)
2335 && warning_at (callloc
, OPT_Wstringop_truncation
,
2336 "%G%qD output truncated before terminating nul "
2337 "copying as many bytes from a string as its length",
2340 else if (silen
&& is_strlen_related_p (src
, silen
->ptr
))
2341 warned
= warning_at (callloc
, OPT_Wstringop_overflow_
,
2342 "%G%qD specified bound depends on the length "
2343 "of the source argument",
2347 location_t strlenloc
= pss
->second
;
2348 if (strlenloc
!= UNKNOWN_LOCATION
&& strlenloc
!= callloc
)
2349 inform (strlenloc
, "length computed here");
2353 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
2354 If strlen of the second argument is known and length of the third argument
2355 is that plus one, strlen of the first argument is the same after this
2359 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2362 tree src
, dst
, len
, lhs
, oldlen
, newlen
;
2363 gimple
*stmt
= gsi_stmt (*gsi
);
2364 strinfo
*si
, *dsi
, *olddsi
;
2366 len
= gimple_call_arg (stmt
, 2);
2367 src
= gimple_call_arg (stmt
, 1);
2368 dst
= gimple_call_arg (stmt
, 0);
2369 idx
= get_stridx (src
);
2373 didx
= get_stridx (dst
);
2376 olddsi
= get_strinfo (didx
);
2381 && tree_fits_uhwi_p (len
)
2382 && !integer_zerop (len
))
2383 adjust_last_stmt (olddsi
, stmt
, false);
2390 /* Handle memcpy (x, y, l) where l's relationship with strlen (y)
2392 si
= get_strinfo (idx
);
2393 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
2395 if (TREE_CODE (len
) == INTEGER_CST
2396 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
2398 if (tree_int_cst_le (len
, si
->nonzero_chars
))
2400 /* Copying LEN nonzero characters, where LEN is constant. */
2402 full_string_p
= false;
2406 /* Copying the whole of the analyzed part of SI. */
2407 newlen
= si
->nonzero_chars
;
2408 full_string_p
= si
->full_string_p
;
2413 if (!si
->full_string_p
)
2415 if (TREE_CODE (len
) != SSA_NAME
)
2417 def_stmt
= SSA_NAME_DEF_STMT (len
);
2418 if (!is_gimple_assign (def_stmt
)
2419 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
2420 || gimple_assign_rhs1 (def_stmt
) != si
->nonzero_chars
2421 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
2423 /* Copying variable-length string SI (and no more). */
2424 newlen
= si
->nonzero_chars
;
2425 full_string_p
= true;
2431 /* Handle memcpy (x, "abcd", 5) or
2432 memcpy (x, "abc\0uvw", 7). */
2433 if (!tree_fits_uhwi_p (len
))
2436 unsigned HOST_WIDE_INT clen
= tree_to_uhwi (len
);
2437 unsigned HOST_WIDE_INT nonzero_chars
= ~idx
;
2438 newlen
= build_int_cst (size_type_node
, MIN (nonzero_chars
, clen
));
2439 full_string_p
= clen
> nonzero_chars
;
2444 && olddsi
->nonzero_chars
2445 && TREE_CODE (olddsi
->nonzero_chars
) == INTEGER_CST
2446 && tree_int_cst_le (newlen
, olddsi
->nonzero_chars
))
2448 /* The SRC substring being written strictly overlaps
2449 a subsequence of the existing string OLDDSI. */
2450 newlen
= olddsi
->nonzero_chars
;
2451 full_string_p
= olddsi
->full_string_p
;
2454 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
2455 adjust_last_stmt (olddsi
, stmt
, false);
2459 didx
= new_stridx (dst
);
2466 dsi
= unshare_strinfo (olddsi
);
2467 oldlen
= olddsi
->nonzero_chars
;
2468 dsi
->nonzero_chars
= newlen
;
2469 dsi
->full_string_p
= full_string_p
;
2470 /* Break the chain, so adjust_related_strinfo on later pointers in
2471 the chain won't adjust this one anymore. */
2474 dsi
->endptr
= NULL_TREE
;
2478 dsi
= new_strinfo (dst
, didx
, newlen
, full_string_p
);
2479 set_strinfo (didx
, dsi
);
2480 find_equal_ptrs (dst
, didx
);
2482 dsi
->writable
= true;
2483 dsi
->dont_invalidate
= true;
2486 tree adj
= NULL_TREE
;
2487 location_t loc
= gimple_location (stmt
);
2488 if (oldlen
== NULL_TREE
)
2490 else if (integer_zerop (oldlen
))
2492 else if (TREE_CODE (oldlen
) == INTEGER_CST
2493 || TREE_CODE (newlen
) == INTEGER_CST
)
2494 adj
= fold_build2_loc (loc
, MINUS_EXPR
, TREE_TYPE (newlen
), newlen
,
2495 fold_convert_loc (loc
, TREE_TYPE (newlen
),
2497 if (adj
!= NULL_TREE
)
2498 adjust_related_strinfos (loc
, dsi
, adj
);
2502 /* memcpy src may not overlap dst, so src doesn't need to be
2503 invalidated either. */
2505 si
->dont_invalidate
= true;
2509 lhs
= gimple_call_lhs (stmt
);
2512 case BUILT_IN_MEMCPY
:
2513 case BUILT_IN_MEMCPY_CHK
:
2514 /* Allow adjust_last_stmt to decrease this memcpy's size. */
2515 laststmt
.stmt
= stmt
;
2516 laststmt
.len
= dsi
->nonzero_chars
;
2517 laststmt
.stridx
= dsi
->idx
;
2519 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
2521 case BUILT_IN_MEMPCPY
:
2522 case BUILT_IN_MEMPCPY_CHK
:
2530 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
2531 If strlen of the second argument is known, strlen of the first argument
2532 is increased by the length of the second argument. Furthermore, attempt
2533 to convert it to memcpy/strcpy if the length of the first argument
2537 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2540 tree srclen
, args
, type
, fn
, objsz
, endptr
;
2542 gimple
*stmt
= gsi_stmt (*gsi
);
2544 location_t loc
= gimple_location (stmt
);
2546 tree src
= gimple_call_arg (stmt
, 1);
2547 tree dst
= gimple_call_arg (stmt
, 0);
2549 /* Bail if the source is the same as destination. It will be diagnosed
2551 if (operand_equal_p (src
, dst
, 0))
2554 tree lhs
= gimple_call_lhs (stmt
);
2556 didx
= get_stridx (dst
);
2562 dsi
= get_strinfo (didx
);
2566 idx
= get_stridx (src
);
2568 srclen
= build_int_cst (size_type_node
, ~idx
);
2571 si
= get_strinfo (idx
);
2573 srclen
= get_string_length (si
);
2576 /* Set the no-warning bit on the transformed statement? */
2577 bool set_no_warning
= false;
2579 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
2582 /* The concatenation always involves copying at least one byte
2583 (the terminating nul), even if the source string is empty.
2584 If the source is unknown assume it's one character long and
2585 used that as both sizes. */
2589 tree type
= TREE_TYPE (slen
);
2590 slen
= fold_build2 (PLUS_EXPR
, type
, slen
, build_int_cst (type
, 1));
2593 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2595 if (check_bounds_or_overlap (stmt
, dst
, sptr
, NULL_TREE
, slen
))
2597 gimple_set_no_warning (stmt
, true);
2598 set_no_warning
= true;
2602 /* strcat (p, q) can be transformed into
2603 tmp = p + strlen (p); endptr = stpcpy (tmp, q);
2604 with length endptr - p if we need to compute the length
2605 later on. Don't do this transformation if we don't need
2607 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
2611 didx
= new_stridx (dst
);
2617 dsi
= new_strinfo (dst
, didx
, NULL_TREE
, false);
2618 set_strinfo (didx
, dsi
);
2619 find_equal_ptrs (dst
, didx
);
2623 dsi
= unshare_strinfo (dsi
);
2624 dsi
->nonzero_chars
= NULL_TREE
;
2625 dsi
->full_string_p
= false;
2627 dsi
->endptr
= NULL_TREE
;
2629 dsi
->writable
= true;
2631 dsi
->dont_invalidate
= true;
2636 tree dstlen
= dsi
->nonzero_chars
;
2637 endptr
= dsi
->endptr
;
2639 dsi
= unshare_strinfo (dsi
);
2640 dsi
->endptr
= NULL_TREE
;
2642 dsi
->writable
= true;
2644 if (srclen
!= NULL_TREE
)
2646 dsi
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
2647 TREE_TYPE (dsi
->nonzero_chars
),
2648 dsi
->nonzero_chars
, srclen
);
2649 gcc_assert (dsi
->full_string_p
);
2650 adjust_related_strinfos (loc
, dsi
, srclen
);
2651 dsi
->dont_invalidate
= true;
2655 dsi
->nonzero_chars
= NULL
;
2656 dsi
->full_string_p
= false;
2657 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
2658 dsi
->dont_invalidate
= true;
2662 /* strcat src may not overlap dst, so src doesn't need to be
2663 invalidated either. */
2664 si
->dont_invalidate
= true;
2666 /* For now. Could remove the lhs from the call and add
2667 lhs = dst; afterwards. */
2675 case BUILT_IN_STRCAT
:
2676 if (srclen
!= NULL_TREE
)
2677 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
2679 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
2681 case BUILT_IN_STRCAT_CHK
:
2682 if (srclen
!= NULL_TREE
)
2683 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
2685 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
2686 objsz
= gimple_call_arg (stmt
, 2);
2692 if (fn
== NULL_TREE
)
2697 tree type
= TREE_TYPE (dstlen
);
2699 /* Compute the size of the source sequence, including the nul. */
2700 tree srcsize
= srclen
? srclen
: size_zero_node
;
2701 srcsize
= fold_build2 (PLUS_EXPR
, type
, srcsize
, build_int_cst (type
, 1));
2703 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2705 if (check_bounds_or_overlap (stmt
, dst
, sptr
, dstlen
, srcsize
))
2707 gimple_set_no_warning (stmt
, true);
2708 set_no_warning
= true;
2712 tree len
= NULL_TREE
;
2713 if (srclen
!= NULL_TREE
)
2715 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
2716 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
2718 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
2719 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
2720 build_int_cst (type
, 1));
2721 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
2725 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
2727 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
, TREE_TYPE (dst
), dst
,
2728 fold_convert_loc (loc
, sizetype
,
2729 unshare_expr (dstlen
)));
2730 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
2734 objsz
= fold_build2_loc (loc
, MINUS_EXPR
, TREE_TYPE (objsz
), objsz
,
2735 fold_convert_loc (loc
, TREE_TYPE (objsz
),
2736 unshare_expr (dstlen
)));
2737 objsz
= force_gimple_operand_gsi (gsi
, objsz
, true, NULL_TREE
, true,
2740 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2742 fprintf (dump_file
, "Optimizing: ");
2743 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2745 if (srclen
!= NULL_TREE
)
2746 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
2747 dst
, src
, len
, objsz
);
2749 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
2753 stmt
= gsi_stmt (*gsi
);
2755 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2757 fprintf (dump_file
, "into: ");
2758 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2760 /* If srclen == NULL, note that current string length can be
2761 computed by transforming this strcpy into stpcpy. */
2762 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
2764 adjust_last_stmt (dsi
, stmt
, true);
2765 if (srclen
!= NULL_TREE
)
2767 laststmt
.stmt
= stmt
;
2768 laststmt
.len
= srclen
;
2769 laststmt
.stridx
= dsi
->idx
;
2772 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2773 fprintf (dump_file
, "not possible.\n");
2776 gimple_set_no_warning (stmt
, true);
2779 /* Handle a call to malloc or calloc. */
2782 handle_builtin_malloc (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2784 gimple
*stmt
= gsi_stmt (*gsi
);
2785 tree lhs
= gimple_call_lhs (stmt
);
2786 if (lhs
== NULL_TREE
)
2789 gcc_assert (get_stridx (lhs
) == 0);
2790 int idx
= new_stridx (lhs
);
2791 tree length
= NULL_TREE
;
2792 if (bcode
== BUILT_IN_CALLOC
)
2793 length
= build_int_cst (size_type_node
, 0);
2794 strinfo
*si
= new_strinfo (lhs
, idx
, length
, length
!= NULL_TREE
);
2795 if (bcode
== BUILT_IN_CALLOC
)
2797 set_strinfo (idx
, si
);
2798 si
->writable
= true;
2800 si
->dont_invalidate
= true;
2803 /* Handle a call to memset.
2804 After a call to calloc, memset(,0,) is unnecessary.
2805 memset(malloc(n),0,n) is calloc(n,1).
2806 return true when the call is transfomred, false otherwise. */
2809 handle_builtin_memset (gimple_stmt_iterator
*gsi
)
2811 gimple
*stmt2
= gsi_stmt (*gsi
);
2812 if (!integer_zerop (gimple_call_arg (stmt2
, 1)))
2814 tree ptr
= gimple_call_arg (stmt2
, 0);
2815 int idx1
= get_stridx (ptr
);
2818 strinfo
*si1
= get_strinfo (idx1
);
2821 gimple
*stmt1
= si1
->stmt
;
2822 if (!stmt1
|| !is_gimple_call (stmt1
))
2824 tree callee1
= gimple_call_fndecl (stmt1
);
2825 if (!valid_builtin_call (stmt1
))
2827 enum built_in_function code1
= DECL_FUNCTION_CODE (callee1
);
2828 tree size
= gimple_call_arg (stmt2
, 2);
2829 if (code1
== BUILT_IN_CALLOC
)
2830 /* Not touching stmt1 */ ;
2831 else if (code1
== BUILT_IN_MALLOC
2832 && operand_equal_p (gimple_call_arg (stmt1
, 0), size
, 0))
2834 gimple_stmt_iterator gsi1
= gsi_for_stmt (stmt1
);
2835 update_gimple_call (&gsi1
, builtin_decl_implicit (BUILT_IN_CALLOC
), 2,
2836 size
, build_one_cst (size_type_node
));
2837 si1
->nonzero_chars
= build_int_cst (size_type_node
, 0);
2838 si1
->full_string_p
= true;
2839 si1
->stmt
= gsi_stmt (gsi1
);
2843 tree lhs
= gimple_call_lhs (stmt2
);
2844 unlink_stmt_vdef (stmt2
);
2847 gimple
*assign
= gimple_build_assign (lhs
, ptr
);
2848 gsi_replace (gsi
, assign
, false);
2852 gsi_remove (gsi
, true);
2853 release_defs (stmt2
);
2859 /* Handle a call to memcmp. We try to handle small comparisons by
2860 converting them to load and compare, and replacing the call to memcmp
2861 with a __builtin_memcmp_eq call where possible.
2862 return true when call is transformed, return false otherwise. */
2865 handle_builtin_memcmp (gimple_stmt_iterator
*gsi
)
2867 gcall
*stmt2
= as_a
<gcall
*> (gsi_stmt (*gsi
));
2868 tree res
= gimple_call_lhs (stmt2
);
2869 tree arg1
= gimple_call_arg (stmt2
, 0);
2870 tree arg2
= gimple_call_arg (stmt2
, 1);
2871 tree len
= gimple_call_arg (stmt2
, 2);
2872 unsigned HOST_WIDE_INT leni
;
2873 use_operand_p use_p
;
2874 imm_use_iterator iter
;
2879 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
2881 gimple
*ustmt
= USE_STMT (use_p
);
2883 if (is_gimple_debug (ustmt
))
2885 if (gimple_code (ustmt
) == GIMPLE_ASSIGN
)
2887 gassign
*asgn
= as_a
<gassign
*> (ustmt
);
2888 tree_code code
= gimple_assign_rhs_code (asgn
);
2889 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2890 || !integer_zerop (gimple_assign_rhs2 (asgn
)))
2893 else if (gimple_code (ustmt
) == GIMPLE_COND
)
2895 tree_code code
= gimple_cond_code (ustmt
);
2896 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2897 || !integer_zerop (gimple_cond_rhs (ustmt
)))
2904 if (tree_fits_uhwi_p (len
)
2905 && (leni
= tree_to_uhwi (len
)) <= GET_MODE_SIZE (word_mode
)
2906 && pow2p_hwi (leni
))
2908 leni
*= CHAR_TYPE_SIZE
;
2909 unsigned align1
= get_pointer_alignment (arg1
);
2910 unsigned align2
= get_pointer_alignment (arg2
);
2911 unsigned align
= MIN (align1
, align2
);
2912 scalar_int_mode mode
;
2913 if (int_mode_for_size (leni
, 1).exists (&mode
)
2914 && (align
>= leni
|| !targetm
.slow_unaligned_access (mode
, align
)))
2916 location_t loc
= gimple_location (stmt2
);
2918 type
= build_nonstandard_integer_type (leni
, 1);
2919 gcc_assert (known_eq (GET_MODE_BITSIZE (TYPE_MODE (type
)), leni
));
2920 tree ptrtype
= build_pointer_type_for_mode (char_type_node
,
2922 off
= build_int_cst (ptrtype
, 0);
2923 arg1
= build2_loc (loc
, MEM_REF
, type
, arg1
, off
);
2924 arg2
= build2_loc (loc
, MEM_REF
, type
, arg2
, off
);
2925 tree tem1
= fold_const_aggregate_ref (arg1
);
2928 tree tem2
= fold_const_aggregate_ref (arg2
);
2931 res
= fold_convert_loc (loc
, TREE_TYPE (res
),
2932 fold_build2_loc (loc
, NE_EXPR
,
2935 gimplify_and_update_call_from_tree (gsi
, res
);
2940 gimple_call_set_fndecl (stmt2
, builtin_decl_explicit (BUILT_IN_MEMCMP_EQ
));
2944 /* Given an index to the strinfo vector, compute the string length
2945 for the corresponding string. Return -1 when unknown. */
2947 static HOST_WIDE_INT
2948 compute_string_length (int idx
)
2950 HOST_WIDE_INT string_leni
= -1;
2951 gcc_assert (idx
!= 0);
2956 strinfo
*si
= get_strinfo (idx
);
2959 tree const_string_len
= get_string_length (si
);
2960 if (const_string_len
&& tree_fits_shwi_p (const_string_len
))
2961 string_leni
= tree_to_shwi (const_string_len
);
2964 if (string_leni
< 0)
2970 /* Determine the minimum size of the object referenced by DEST expression
2971 which must have a pointer type.
2972 Return the minimum size of the object if successful or NULL when the size
2973 cannot be determined. */
2975 determine_min_objsize (tree dest
)
2977 unsigned HOST_WIDE_INT size
= 0;
2979 if (compute_builtin_object_size (dest
, 2, &size
))
2980 return build_int_cst (sizetype
, size
);
2982 /* Try to determine the size of the object through the RHS
2983 of the assign statement. */
2984 if (TREE_CODE (dest
) == SSA_NAME
)
2986 gimple
*stmt
= SSA_NAME_DEF_STMT (dest
);
2987 if (!is_gimple_assign (stmt
))
2990 if (!gimple_assign_single_p (stmt
)
2991 && !gimple_assign_unary_nop_p (stmt
))
2994 dest
= gimple_assign_rhs1 (stmt
);
2995 return determine_min_objsize (dest
);
2998 /* Try to determine the size of the object from its type. */
2999 if (TREE_CODE (dest
) != ADDR_EXPR
)
3002 tree type
= TREE_TYPE (dest
);
3003 if (TREE_CODE (type
) == POINTER_TYPE
)
3004 type
= TREE_TYPE (type
);
3006 type
= TYPE_MAIN_VARIANT (type
);
3008 /* We cannot determine the size of the array if it's a flexible array,
3009 which is declared at the end of a structure. */
3010 if (TREE_CODE (type
) == ARRAY_TYPE
3011 && !array_at_struct_end_p (dest
))
3013 tree
size_t = TYPE_SIZE_UNIT (type
);
3014 if (size_t && TREE_CODE (size_t) == INTEGER_CST
3015 && !integer_zerop (size_t))
3022 /* Handle a call to strcmp or strncmp. When the result is ONLY used to do
3023 equality test against zero:
3025 A. When the lengths of both arguments are constant and it's a strcmp:
3026 * if the lengths are NOT equal, we can safely fold the call
3027 to a non-zero value.
3028 * otherwise, do nothing now.
3030 B. When the length of one argument is constant, try to replace the call
3031 with a __builtin_str(n)cmp_eq call where possible, i.e:
3033 strncmp (s, STR, C) (!)= 0 in which, s is a pointer to a string, STR
3034 is a string with constant length , C is a constant.
3035 if (C <= strlen(STR) && sizeof_array(s) > C)
3037 replace this call with
3038 strncmp_eq (s, STR, C) (!)= 0
3042 it can be safely treated as a call to strcmp (s, STR) (!)= 0
3043 can handled by the following strcmp.
3046 strcmp (s, STR) (!)= 0 in which, s is a pointer to a string, STR
3047 is a string with constant length.
3048 if (sizeof_array(s) > strlen(STR))
3050 replace this call with
3051 strcmp_eq (s, STR, strlen(STR)+1) (!)= 0
3054 Return true when the call is transformed, return false otherwise.
3058 handle_builtin_string_cmp (gimple_stmt_iterator
*gsi
)
3060 gcall
*stmt
= as_a
<gcall
*> (gsi_stmt (*gsi
));
3061 tree res
= gimple_call_lhs (stmt
);
3062 use_operand_p use_p
;
3063 imm_use_iterator iter
;
3064 tree arg1
= gimple_call_arg (stmt
, 0);
3065 tree arg2
= gimple_call_arg (stmt
, 1);
3066 int idx1
= get_stridx (arg1
);
3067 int idx2
= get_stridx (arg2
);
3068 HOST_WIDE_INT length
= -1;
3069 bool is_ncmp
= false;
3074 /* When both arguments are unknown, do nothing. */
3075 if (idx1
== 0 && idx2
== 0)
3078 /* Handle strncmp function. */
3079 if (gimple_call_num_args (stmt
) == 3)
3081 tree len
= gimple_call_arg (stmt
, 2);
3082 if (tree_fits_shwi_p (len
))
3083 length
= tree_to_shwi (len
);
3088 /* For strncmp, if the length argument is NOT known, do nothing. */
3089 if (is_ncmp
&& length
< 0)
3092 /* When the result is ONLY used to do equality test against zero. */
3093 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
3095 gimple
*use_stmt
= USE_STMT (use_p
);
3097 if (is_gimple_debug (use_stmt
))
3099 if (gimple_code (use_stmt
) == GIMPLE_ASSIGN
)
3101 tree_code code
= gimple_assign_rhs_code (use_stmt
);
3102 if (code
== COND_EXPR
)
3104 tree cond_expr
= gimple_assign_rhs1 (use_stmt
);
3105 if ((TREE_CODE (cond_expr
) != EQ_EXPR
3106 && (TREE_CODE (cond_expr
) != NE_EXPR
))
3107 || !integer_zerop (TREE_OPERAND (cond_expr
, 1)))
3110 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3112 if (!integer_zerop (gimple_assign_rhs2 (use_stmt
)))
3118 else if (gimple_code (use_stmt
) == GIMPLE_COND
)
3120 tree_code code
= gimple_cond_code (use_stmt
);
3121 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
3122 || !integer_zerop (gimple_cond_rhs (use_stmt
)))
3129 /* When the lengths of both arguments are known, and they are unequal,
3130 we can safely fold the call to a non-zero value for strcmp;
3131 othewise, do nothing now. */
3132 if (idx1
!= 0 && idx2
!= 0)
3134 HOST_WIDE_INT const_string_leni1
= compute_string_length (idx1
);
3135 HOST_WIDE_INT const_string_leni2
= compute_string_length (idx2
);
3138 && const_string_leni1
!= -1
3139 && const_string_leni2
!= -1
3140 && const_string_leni1
!= const_string_leni2
)
3142 replace_call_with_value (gsi
, integer_one_node
);
3148 /* When the length of one argument is constant. */
3149 tree var_string
= NULL_TREE
;
3150 HOST_WIDE_INT const_string_leni
= -1;
3154 const_string_leni
= compute_string_length (idx1
);
3159 gcc_checking_assert (idx2
);
3160 const_string_leni
= compute_string_length (idx2
);
3164 if (const_string_leni
< 0)
3167 unsigned HOST_WIDE_INT var_sizei
= 0;
3168 /* try to determine the minimum size of the object pointed by var_string. */
3169 tree size
= determine_min_objsize (var_string
);
3174 if (tree_fits_uhwi_p (size
))
3175 var_sizei
= tree_to_uhwi (size
);
3180 /* For strncmp, if length > const_string_leni , this call can be safely
3181 transformed to a strcmp. */
3182 if (is_ncmp
&& length
> const_string_leni
)
3185 unsigned HOST_WIDE_INT final_length
3186 = is_ncmp
? length
: const_string_leni
+ 1;
3188 /* Replace strcmp or strncmp with the corresponding str(n)cmp_eq. */
3189 if (var_sizei
> final_length
)
3193 ? builtin_decl_implicit (BUILT_IN_STRNCMP_EQ
)
3194 : builtin_decl_implicit (BUILT_IN_STRCMP_EQ
));
3197 tree const_string_len
= build_int_cst (size_type_node
, final_length
);
3198 update_gimple_call (gsi
, fn
, 3, arg1
, arg2
, const_string_len
);
3206 /* Handle a POINTER_PLUS_EXPR statement.
3207 For p = "abcd" + 2; compute associated length, or if
3208 p = q + off is pointing to a '\0' character of a string, call
3209 zero_length_string on it. */
3212 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
3214 gimple
*stmt
= gsi_stmt (*gsi
);
3215 tree lhs
= gimple_assign_lhs (stmt
), off
;
3216 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
3224 tree off
= gimple_assign_rhs2 (stmt
);
3225 if (tree_fits_uhwi_p (off
)
3226 && tree_to_uhwi (off
) <= (unsigned HOST_WIDE_INT
) ~idx
)
3227 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
3228 = ~(~idx
- (int) tree_to_uhwi (off
));
3232 si
= get_strinfo (idx
);
3233 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
3236 off
= gimple_assign_rhs2 (stmt
);
3238 if (si
->full_string_p
&& operand_equal_p (si
->nonzero_chars
, off
, 0))
3239 zsi
= zero_length_string (lhs
, si
);
3240 else if (TREE_CODE (off
) == SSA_NAME
)
3242 gimple
*def_stmt
= SSA_NAME_DEF_STMT (off
);
3243 if (gimple_assign_single_p (def_stmt
)
3244 && si
->full_string_p
3245 && operand_equal_p (si
->nonzero_chars
,
3246 gimple_assign_rhs1 (def_stmt
), 0))
3247 zsi
= zero_length_string (lhs
, si
);
3250 && si
->endptr
!= NULL_TREE
3251 && si
->endptr
!= lhs
3252 && TREE_CODE (si
->endptr
) == SSA_NAME
)
3254 enum tree_code rhs_code
3255 = useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (si
->endptr
))
3256 ? SSA_NAME
: NOP_EXPR
;
3257 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, si
->endptr
);
3258 gcc_assert (gsi_stmt (*gsi
) == stmt
);
3263 /* If RHS, either directly or indirectly, refers to a string of constant
3264 length, return the length. Otherwise, if it refers to a character
3265 constant, return 1 if the constant is non-zero and 0 if it is nul.
3266 Otherwise, return a negative value. */
3268 static HOST_WIDE_INT
3269 get_min_string_length (tree rhs
, bool *full_string_p
)
3271 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs
)))
3273 if (tree_expr_nonzero_p (rhs
))
3275 *full_string_p
= false;
3279 *full_string_p
= true;
3283 if (TREE_CODE (rhs
) == MEM_REF
3284 && integer_zerop (TREE_OPERAND (rhs
, 1)))
3286 rhs
= TREE_OPERAND (rhs
, 0);
3287 if (TREE_CODE (rhs
) == ADDR_EXPR
)
3289 tree rhs_addr
= rhs
;
3291 rhs
= TREE_OPERAND (rhs
, 0);
3292 if (TREE_CODE (rhs
) != STRING_CST
)
3294 int idx
= get_stridx (rhs_addr
);
3297 strinfo
*si
= get_strinfo (idx
);
3299 && tree_fits_shwi_p (si
->nonzero_chars
))
3301 *full_string_p
= si
->full_string_p
;
3302 return tree_to_shwi (si
->nonzero_chars
);
3309 if (TREE_CODE (rhs
) == VAR_DECL
3310 && TREE_READONLY (rhs
))
3311 rhs
= DECL_INITIAL (rhs
);
3313 if (rhs
&& TREE_CODE (rhs
) == STRING_CST
)
3315 HOST_WIDE_INT len
= strlen (TREE_STRING_POINTER (rhs
));
3316 *full_string_p
= len
< TREE_STRING_LENGTH (rhs
);
3323 /* Handle a single or multiple character store either by single
3324 character assignment or by multi-character assignment from
3328 handle_char_store (gimple_stmt_iterator
*gsi
)
3332 gimple
*stmt
= gsi_stmt (*gsi
);
3333 tree ssaname
= NULL_TREE
, lhs
= gimple_assign_lhs (stmt
);
3334 tree rhs
= gimple_assign_rhs1 (stmt
);
3335 unsigned HOST_WIDE_INT offset
= 0;
3337 if (TREE_CODE (lhs
) == MEM_REF
3338 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
)
3340 tree mem_offset
= TREE_OPERAND (lhs
, 1);
3341 if (tree_fits_uhwi_p (mem_offset
))
3343 /* Get the strinfo for the base, and use it if it starts with at
3344 least OFFSET nonzero characters. This is trivially true if
3346 offset
= tree_to_uhwi (mem_offset
);
3347 idx
= get_stridx (TREE_OPERAND (lhs
, 0));
3349 si
= get_strinfo (idx
);
3351 ssaname
= TREE_OPERAND (lhs
, 0);
3352 else if (si
== NULL
|| compare_nonzero_chars (si
, offset
) < 0)
3358 idx
= get_addr_stridx (lhs
, NULL_TREE
, &offset
);
3360 si
= get_strinfo (idx
);
3363 /* STORING_NONZERO_P is true iff not all stored characters are zero.
3364 STORING_ALL_ZEROS_P is true iff all stored characters are zero.
3365 Both are false when it's impossible to determine which is true. */
3366 bool storing_nonzero_p
;
3367 bool storing_all_zeros_p
= initializer_zerop (rhs
, &storing_nonzero_p
);
3368 if (!storing_nonzero_p
)
3369 storing_nonzero_p
= tree_expr_nonzero_p (rhs
);
3370 bool full_string_p
= storing_all_zeros_p
;
3372 /* Set to the length of the string being assigned if known. */
3373 HOST_WIDE_INT rhslen
;
3377 int cmp
= compare_nonzero_chars (si
, offset
);
3378 gcc_assert (offset
== 0 || cmp
>= 0);
3379 if (storing_all_zeros_p
&& cmp
== 0 && si
->full_string_p
)
3381 /* When overwriting a '\0' with a '\0', the store can be removed
3382 if we know it has been stored in the current function. */
3383 if (!stmt_could_throw_p (cfun
, stmt
) && si
->writable
)
3385 unlink_stmt_vdef (stmt
);
3386 release_defs (stmt
);
3387 gsi_remove (gsi
, true);
3392 si
->writable
= true;
3397 /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0',
3398 and if we aren't storing '\0', we know that the length of the
3399 string and any other zero terminated string in memory remains
3400 the same. In that case we move to the next gimple statement and
3401 return to signal the caller that it shouldn't invalidate anything.
3403 This is benefical for cases like:
3408 strcpy (p, "foobar");
3409 size_t len = strlen (p); // This can be optimized into 6
3410 size_t len2 = strlen (q); // This has to be computed
3412 size_t len3 = strlen (p); // This can be optimized into 6
3413 size_t len4 = strlen (q); // This can be optimized into len2
3414 bar (len, len2, len3, len4);
3417 else if (storing_nonzero_p
&& cmp
> 0)
3422 else if (storing_all_zeros_p
3423 || storing_nonzero_p
3424 || (offset
!= 0 && cmp
> 0))
3426 /* When STORING_NONZERO_P, we know that the string will start
3427 with at least OFFSET + 1 nonzero characters. If storing
3428 a single character, set si->NONZERO_CHARS to the result.
3429 If storing multiple characters, try to determine the number
3430 of leading non-zero characters and set si->NONZERO_CHARS to
3433 When STORING_ALL_ZEROS_P, we know that the string is now
3434 OFFSET characters long.
3436 Otherwise, we're storing an unknown value at offset OFFSET,
3437 so need to clip the nonzero_chars to OFFSET. */
3438 bool full_string_p
= storing_all_zeros_p
;
3439 HOST_WIDE_INT len
= 1;
3440 if (storing_nonzero_p
)
3442 /* Try to get the minimum length of the string (or
3443 individual character) being stored. If it fails,
3444 STORING_NONZERO_P guarantees it's at least 1. */
3445 len
= get_min_string_length (rhs
, &full_string_p
);
3450 location_t loc
= gimple_location (stmt
);
3451 tree oldlen
= si
->nonzero_chars
;
3452 if (cmp
== 0 && si
->full_string_p
)
3453 /* We're overwriting the nul terminator with a nonzero or
3454 unknown character. If the previous stmt was a memcpy,
3455 its length may be decreased. */
3456 adjust_last_stmt (si
, stmt
, false);
3457 si
= unshare_strinfo (si
);
3458 if (storing_nonzero_p
)
3460 gcc_assert (len
>= 0);
3461 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
+ len
);
3464 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
);
3465 si
->full_string_p
= full_string_p
;
3466 if (storing_all_zeros_p
3468 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
3469 si
->endptr
= ssaname
;
3474 si
->writable
= true;
3475 si
->dont_invalidate
= true;
3478 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
3479 si
->nonzero_chars
, oldlen
);
3480 adjust_related_strinfos (loc
, si
, adj
);
3486 else if (idx
== 0 && (storing_all_zeros_p
|| storing_nonzero_p
))
3489 idx
= new_stridx (ssaname
);
3491 idx
= new_addr_stridx (lhs
);
3494 tree ptr
= (ssaname
? ssaname
: build_fold_addr_expr (lhs
));
3495 HOST_WIDE_INT slen
= (storing_all_zeros_p
3497 : (storing_nonzero_p
3498 ? get_min_string_length (rhs
, &full_string_p
)
3500 tree len
= (slen
<= 0
3502 : build_int_cst (size_type_node
, slen
));
3503 si
= new_strinfo (ptr
, idx
, len
, slen
>= 0 && full_string_p
);
3504 set_strinfo (idx
, si
);
3505 if (storing_all_zeros_p
3507 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
3508 si
->endptr
= ssaname
;
3509 si
->dont_invalidate
= true;
3510 si
->writable
= true;
3514 && (rhslen
= get_min_string_length (rhs
, &full_string_p
)) >= 0
3515 && ssaname
== NULL_TREE
3516 && TREE_CODE (TREE_TYPE (lhs
)) == ARRAY_TYPE
)
3518 HOST_WIDE_INT a
= int_size_in_bytes (TREE_TYPE (lhs
));
3519 if (a
> 0 && (unsigned HOST_WIDE_INT
) a
> (unsigned HOST_WIDE_INT
) rhslen
)
3521 int idx
= new_addr_stridx (lhs
);
3524 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
3525 build_int_cst (size_type_node
, rhslen
),
3527 set_strinfo (idx
, si
);
3528 si
->dont_invalidate
= true;
3533 if (si
!= NULL
&& offset
== 0 && storing_all_zeros_p
)
3535 /* Allow adjust_last_stmt to remove it if the stored '\0'
3536 is immediately overwritten. */
3537 laststmt
.stmt
= stmt
;
3538 laststmt
.len
= build_int_cst (size_type_node
, 1);
3539 laststmt
.stridx
= si
->idx
;
3544 /* Try to fold strstr (s, t) eq/ne s to strncmp (s, t, strlen (t)) eq/ne 0. */
3547 fold_strstr_to_strncmp (tree rhs1
, tree rhs2
, gimple
*stmt
)
3549 if (TREE_CODE (rhs1
) != SSA_NAME
3550 || TREE_CODE (rhs2
) != SSA_NAME
)
3553 gimple
*call_stmt
= NULL
;
3554 for (int pass
= 0; pass
< 2; pass
++)
3556 gimple
*g
= SSA_NAME_DEF_STMT (rhs1
);
3557 if (gimple_call_builtin_p (g
, BUILT_IN_STRSTR
)
3558 && has_single_use (rhs1
)
3559 && gimple_call_arg (g
, 0) == rhs2
)
3564 std::swap (rhs1
, rhs2
);
3569 tree arg0
= gimple_call_arg (call_stmt
, 0);
3573 tree arg1
= gimple_call_arg (call_stmt
, 1);
3574 tree arg1_len
= NULL_TREE
;
3575 int idx
= get_stridx (arg1
);
3580 arg1_len
= build_int_cst (size_type_node
, ~idx
);
3583 strinfo
*si
= get_strinfo (idx
);
3585 arg1_len
= get_string_length (si
);
3589 if (arg1_len
!= NULL_TREE
)
3591 gimple_stmt_iterator gsi
= gsi_for_stmt (call_stmt
);
3592 tree strncmp_decl
= builtin_decl_explicit (BUILT_IN_STRNCMP
);
3594 if (!is_gimple_val (arg1_len
))
3596 tree arg1_len_tmp
= make_ssa_name (TREE_TYPE (arg1_len
));
3597 gassign
*arg1_stmt
= gimple_build_assign (arg1_len_tmp
,
3599 gsi_insert_before (&gsi
, arg1_stmt
, GSI_SAME_STMT
);
3600 arg1_len
= arg1_len_tmp
;
3603 gcall
*strncmp_call
= gimple_build_call (strncmp_decl
, 3,
3604 arg0
, arg1
, arg1_len
);
3605 tree strncmp_lhs
= make_ssa_name (integer_type_node
);
3606 gimple_set_vuse (strncmp_call
, gimple_vuse (call_stmt
));
3607 gimple_call_set_lhs (strncmp_call
, strncmp_lhs
);
3608 gsi_remove (&gsi
, true);
3609 gsi_insert_before (&gsi
, strncmp_call
, GSI_SAME_STMT
);
3610 tree zero
= build_zero_cst (TREE_TYPE (strncmp_lhs
));
3612 if (is_gimple_assign (stmt
))
3614 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
3616 tree cond
= gimple_assign_rhs1 (stmt
);
3617 TREE_OPERAND (cond
, 0) = strncmp_lhs
;
3618 TREE_OPERAND (cond
, 1) = zero
;
3622 gimple_assign_set_rhs1 (stmt
, strncmp_lhs
);
3623 gimple_assign_set_rhs2 (stmt
, zero
);
3628 gcond
*cond
= as_a
<gcond
*> (stmt
);
3629 gimple_cond_set_lhs (cond
, strncmp_lhs
);
3630 gimple_cond_set_rhs (cond
, zero
);
3638 /* Attempt to check for validity of the performed access a single statement
3639 at *GSI using string length knowledge, and to optimize it.
3640 If the given basic block needs clean-up of EH, CLEANUP_EH is set to
3644 strlen_check_and_optimize_stmt (gimple_stmt_iterator
*gsi
, bool *cleanup_eh
)
3646 gimple
*stmt
= gsi_stmt (*gsi
);
3648 if (is_gimple_call (stmt
))
3650 tree callee
= gimple_call_fndecl (stmt
);
3651 if (valid_builtin_call (stmt
))
3652 switch (DECL_FUNCTION_CODE (callee
))
3654 case BUILT_IN_STRLEN
:
3655 case BUILT_IN_STRNLEN
:
3656 handle_builtin_strlen (gsi
);
3658 case BUILT_IN_STRCHR
:
3659 handle_builtin_strchr (gsi
);
3661 case BUILT_IN_STRCPY
:
3662 case BUILT_IN_STRCPY_CHK
:
3663 case BUILT_IN_STPCPY
:
3664 case BUILT_IN_STPCPY_CHK
:
3665 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3668 case BUILT_IN_STRNCAT
:
3669 case BUILT_IN_STRNCAT_CHK
:
3670 handle_builtin_strncat (DECL_FUNCTION_CODE (callee
), gsi
);
3673 case BUILT_IN_STPNCPY
:
3674 case BUILT_IN_STPNCPY_CHK
:
3675 case BUILT_IN_STRNCPY
:
3676 case BUILT_IN_STRNCPY_CHK
:
3677 handle_builtin_stxncpy (DECL_FUNCTION_CODE (callee
), gsi
);
3680 case BUILT_IN_MEMCPY
:
3681 case BUILT_IN_MEMCPY_CHK
:
3682 case BUILT_IN_MEMPCPY
:
3683 case BUILT_IN_MEMPCPY_CHK
:
3684 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3686 case BUILT_IN_STRCAT
:
3687 case BUILT_IN_STRCAT_CHK
:
3688 handle_builtin_strcat (DECL_FUNCTION_CODE (callee
), gsi
);
3690 case BUILT_IN_MALLOC
:
3691 case BUILT_IN_CALLOC
:
3692 handle_builtin_malloc (DECL_FUNCTION_CODE (callee
), gsi
);
3694 case BUILT_IN_MEMSET
:
3695 if (handle_builtin_memset (gsi
))
3698 case BUILT_IN_MEMCMP
:
3699 if (handle_builtin_memcmp (gsi
))
3702 case BUILT_IN_STRCMP
:
3703 case BUILT_IN_STRNCMP
:
3704 if (handle_builtin_string_cmp (gsi
))
3711 else if (is_gimple_assign (stmt
) && !gimple_clobber_p (stmt
))
3713 tree lhs
= gimple_assign_lhs (stmt
);
3715 if (TREE_CODE (lhs
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (lhs
)))
3717 if (gimple_assign_single_p (stmt
)
3718 || (gimple_assign_cast_p (stmt
)
3719 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
3721 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
3722 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = idx
;
3724 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
3725 handle_pointer_plus (gsi
);
3727 else if (TREE_CODE (lhs
) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
3729 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3730 if (code
== COND_EXPR
)
3732 tree cond
= gimple_assign_rhs1 (stmt
);
3733 enum tree_code cond_code
= TREE_CODE (cond
);
3735 if (cond_code
== EQ_EXPR
|| cond_code
== NE_EXPR
)
3736 fold_strstr_to_strncmp (TREE_OPERAND (cond
, 0),
3737 TREE_OPERAND (cond
, 1), stmt
);
3739 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3740 fold_strstr_to_strncmp (gimple_assign_rhs1 (stmt
),
3741 gimple_assign_rhs2 (stmt
), stmt
);
3742 else if (gimple_assign_load_p (stmt
)
3743 && TREE_CODE (TREE_TYPE (lhs
)) == INTEGER_TYPE
3744 && TYPE_MODE (TREE_TYPE (lhs
)) == TYPE_MODE (char_type_node
)
3745 && (TYPE_PRECISION (TREE_TYPE (lhs
))
3746 == TYPE_PRECISION (char_type_node
))
3747 && !gimple_has_volatile_ops (stmt
))
3749 tree off
= integer_zero_node
;
3750 unsigned HOST_WIDE_INT coff
= 0;
3752 tree rhs1
= gimple_assign_rhs1 (stmt
);
3753 if (code
== MEM_REF
)
3755 idx
= get_stridx (TREE_OPERAND (rhs1
, 0));
3758 strinfo
*si
= get_strinfo (idx
);
3760 && si
->nonzero_chars
3761 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
3762 && (wi::to_widest (si
->nonzero_chars
)
3763 >= wi::to_widest (off
)))
3764 off
= TREE_OPERAND (rhs1
, 1);
3766 /* This case is not useful. See if get_addr_stridx
3767 returns something usable. */
3772 idx
= get_addr_stridx (rhs1
, NULL_TREE
, &coff
);
3775 strinfo
*si
= get_strinfo (idx
);
3777 && si
->nonzero_chars
3778 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
3780 widest_int w1
= wi::to_widest (si
->nonzero_chars
);
3781 widest_int w2
= wi::to_widest (off
) + coff
;
3783 && si
->full_string_p
)
3785 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3787 fprintf (dump_file
, "Optimizing: ");
3788 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3791 /* Reading the final '\0' character. */
3792 tree zero
= build_int_cst (TREE_TYPE (lhs
), 0);
3793 gimple_set_vuse (stmt
, NULL_TREE
);
3794 gimple_assign_set_rhs_from_tree (gsi
, zero
);
3796 |= maybe_clean_or_replace_eh_stmt (stmt
,
3798 stmt
= gsi_stmt (*gsi
);
3801 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3803 fprintf (dump_file
, "into: ");
3804 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3809 /* Reading a character before the final '\0'
3810 character. Just set the value range to ~[0, 0]
3811 if we don't have anything better. */
3813 tree type
= TREE_TYPE (lhs
);
3814 enum value_range_kind vr
3815 = get_range_info (lhs
, &min
, &max
);
3816 if (vr
== VR_VARYING
3818 && min
== wi::min_value (TYPE_PRECISION (type
),
3820 && max
== wi::max_value (TYPE_PRECISION (type
),
3822 set_range_info (lhs
, VR_ANTI_RANGE
,
3823 wi::zero (TYPE_PRECISION (type
)),
3824 wi::zero (TYPE_PRECISION (type
)));
3830 if (strlen_to_stridx
)
3832 tree rhs1
= gimple_assign_rhs1 (stmt
);
3833 if (stridx_strlenloc
*ps
= strlen_to_stridx
->get (rhs1
))
3834 strlen_to_stridx
->put (lhs
, stridx_strlenloc (*ps
));
3837 else if (TREE_CODE (lhs
) != SSA_NAME
&& !TREE_SIDE_EFFECTS (lhs
))
3839 tree type
= TREE_TYPE (lhs
);
3840 if (TREE_CODE (type
) == ARRAY_TYPE
)
3841 type
= TREE_TYPE (type
);
3842 if (TREE_CODE (type
) == INTEGER_TYPE
3843 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
3844 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
))
3846 if (! handle_char_store (gsi
))
3851 else if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
3853 enum tree_code code
= gimple_cond_code (cond
);
3854 if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3855 fold_strstr_to_strncmp (gimple_cond_lhs (stmt
),
3856 gimple_cond_rhs (stmt
), stmt
);
3859 if (gimple_vdef (stmt
))
3860 maybe_invalidate (stmt
);
3864 /* Recursively call maybe_invalidate on stmts that might be executed
3865 in between dombb and current bb and that contain a vdef. Stop when
3866 *count stmts are inspected, or if the whole strinfo vector has
3867 been invalidated. */
3870 do_invalidate (basic_block dombb
, gimple
*phi
, bitmap visited
, int *count
)
3872 unsigned int i
, n
= gimple_phi_num_args (phi
);
3874 for (i
= 0; i
< n
; i
++)
3876 tree vuse
= gimple_phi_arg_def (phi
, i
);
3877 gimple
*stmt
= SSA_NAME_DEF_STMT (vuse
);
3878 basic_block bb
= gimple_bb (stmt
);
3881 || !bitmap_set_bit (visited
, bb
->index
)
3882 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3886 if (gimple_code (stmt
) == GIMPLE_PHI
)
3888 do_invalidate (dombb
, stmt
, visited
, count
);
3895 if (!maybe_invalidate (stmt
))
3900 vuse
= gimple_vuse (stmt
);
3901 stmt
= SSA_NAME_DEF_STMT (vuse
);
3902 if (gimple_bb (stmt
) != bb
)
3904 bb
= gimple_bb (stmt
);
3907 || !bitmap_set_bit (visited
, bb
->index
)
3908 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3915 class strlen_dom_walker
: public dom_walker
3918 strlen_dom_walker (cdi_direction direction
)
3919 : dom_walker (direction
), m_cleanup_cfg (false)
3922 virtual edge
before_dom_children (basic_block
);
3923 virtual void after_dom_children (basic_block
);
3925 /* Flag that will trigger TODO_cleanup_cfg to be returned in strlen
3926 execute function. */
3930 /* Callback for walk_dominator_tree. Attempt to optimize various
3931 string ops by remembering string lengths pointed by pointer SSA_NAMEs. */
3934 strlen_dom_walker::before_dom_children (basic_block bb
)
3936 basic_block dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
3939 stridx_to_strinfo
= NULL
;
3942 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) dombb
->aux
);
3943 if (stridx_to_strinfo
)
3945 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3948 gphi
*phi
= gsi
.phi ();
3949 if (virtual_operand_p (gimple_phi_result (phi
)))
3951 bitmap visited
= BITMAP_ALLOC (NULL
);
3952 int count_vdef
= 100;
3953 do_invalidate (dombb
, phi
, visited
, &count_vdef
);
3954 BITMAP_FREE (visited
);
3955 if (count_vdef
== 0)
3957 /* If there were too many vdefs in between immediate
3958 dominator and current bb, invalidate everything.
3959 If stridx_to_strinfo has been unshared, we need
3960 to free it, otherwise just set it to NULL. */
3961 if (!strinfo_shared ())
3967 vec_safe_iterate (stridx_to_strinfo
, i
, &si
);
3971 (*stridx_to_strinfo
)[i
] = NULL
;
3975 stridx_to_strinfo
= NULL
;
3983 /* If all PHI arguments have the same string index, the PHI result
3985 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3988 gphi
*phi
= gsi
.phi ();
3989 tree result
= gimple_phi_result (phi
);
3990 if (!virtual_operand_p (result
) && POINTER_TYPE_P (TREE_TYPE (result
)))
3992 int idx
= get_stridx (gimple_phi_arg_def (phi
, 0));
3995 unsigned int i
, n
= gimple_phi_num_args (phi
);
3996 for (i
= 1; i
< n
; i
++)
3997 if (idx
!= get_stridx (gimple_phi_arg_def (phi
, i
)))
4000 ssa_ver_to_stridx
[SSA_NAME_VERSION (result
)] = idx
;
4005 bool cleanup_eh
= false;
4007 /* Attempt to optimize individual statements. */
4008 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
4009 if (strlen_check_and_optimize_stmt (&gsi
, &cleanup_eh
))
4012 if (cleanup_eh
&& gimple_purge_dead_eh_edges (bb
))
4013 m_cleanup_cfg
= true;
4015 bb
->aux
= stridx_to_strinfo
;
4016 if (vec_safe_length (stridx_to_strinfo
) && !strinfo_shared ())
4017 (*stridx_to_strinfo
)[0] = (strinfo
*) bb
;
4021 /* Callback for walk_dominator_tree. Free strinfo vector if it is
4022 owned by the current bb, clear bb->aux. */
4025 strlen_dom_walker::after_dom_children (basic_block bb
)
4029 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) bb
->aux
);
4030 if (vec_safe_length (stridx_to_strinfo
)
4031 && (*stridx_to_strinfo
)[0] == (strinfo
*) bb
)
4036 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
4038 vec_free (stridx_to_strinfo
);
4044 /* Main entry point. */
4048 const pass_data pass_data_strlen
=
4050 GIMPLE_PASS
, /* type */
4051 "strlen", /* name */
4052 OPTGROUP_NONE
, /* optinfo_flags */
4053 TV_TREE_STRLEN
, /* tv_id */
4054 ( PROP_cfg
| PROP_ssa
), /* properties_required */
4055 0, /* properties_provided */
4056 0, /* properties_destroyed */
4057 0, /* todo_flags_start */
4058 0, /* todo_flags_finish */
4061 class pass_strlen
: public gimple_opt_pass
4064 pass_strlen (gcc::context
*ctxt
)
4065 : gimple_opt_pass (pass_data_strlen
, ctxt
)
4068 /* opt_pass methods: */
4069 virtual bool gate (function
*) { return flag_optimize_strlen
!= 0; }
4070 virtual unsigned int execute (function
*);
4072 }; // class pass_strlen
4075 pass_strlen::execute (function
*fun
)
4077 gcc_assert (!strlen_to_stridx
);
4078 if (warn_stringop_overflow
|| warn_stringop_truncation
)
4079 strlen_to_stridx
= new hash_map
<tree
, stridx_strlenloc
> ();
4081 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
4084 calculate_dominance_info (CDI_DOMINATORS
);
4086 /* String length optimization is implemented as a walk of the dominator
4087 tree and a forward walk of statements within each block. */
4088 strlen_dom_walker
walker (CDI_DOMINATORS
);
4089 walker
.walk (fun
->cfg
->x_entry_block_ptr
);
4091 ssa_ver_to_stridx
.release ();
4092 strinfo_pool
.release ();
4093 if (decl_to_stridxlist_htab
)
4095 obstack_free (&stridx_obstack
, NULL
);
4096 delete decl_to_stridxlist_htab
;
4097 decl_to_stridxlist_htab
= NULL
;
4099 laststmt
.stmt
= NULL
;
4100 laststmt
.len
= NULL_TREE
;
4101 laststmt
.stridx
= 0;
4103 if (strlen_to_stridx
)
4105 strlen_to_stridx
->empty ();
4106 delete strlen_to_stridx
;
4107 strlen_to_stridx
= NULL
;
4110 return walker
.m_cleanup_cfg
? TODO_cleanup_cfg
: 0;
4116 make_pass_strlen (gcc::context
*ctxt
)
4118 return new pass_strlen (ctxt
);