1 /* String length optimization
2 Copyright (C) 2011-2021 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"
48 #include "tree-hash-traits.h"
51 #include "diagnostic-core.h"
52 #include "diagnostic.h"
57 #include "tree-ssa-loop.h"
58 #include "tree-scalar-evolution.h"
59 #include "vr-values.h"
60 #include "gimple-ssa-evrp-analyze.h"
63 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
64 is an index into strinfo vector, negative value stands for
65 string length of a string literal (~strlen). */
66 static vec
<int> ssa_ver_to_stridx
;
68 /* Number of currently active string indexes plus one. */
69 static int max_stridx
;
71 /* Set to true to optimize, false when just checking. */
72 static bool strlen_optimize
;
74 /* String information record. */
77 /* Number of leading characters that are known to be nonzero. This is
78 also the length of the string if FULL_STRING_P.
80 The values in a list of related string pointers must be consistent;
81 that is, if strinfo B comes X bytes after strinfo A, it must be
82 the case that A->nonzero_chars == X + B->nonzero_chars. */
84 /* Any of the corresponding pointers for querying alias oracle. */
86 /* STMT is used for two things:
88 - To record the statement that should be used for delayed length
89 computations. We maintain the invariant that all related strinfos
90 have delayed lengths or none do.
92 - To record the malloc or calloc call that produced this result
93 to optimize away malloc/memset sequences. STMT is reset after
94 a calloc-allocated object has been stored a non-zero value into. */
96 /* Set to the dynamic allocation statement for the object (alloca,
97 calloc, malloc, or VLA). Unlike STMT, once set for a strinfo
98 object, ALLOC doesn't change. */
100 /* Pointer to '\0' if known, if NULL, it can be computed as
103 /* Reference count. Any changes to strinfo entry possibly shared
104 with dominating basic blocks need unshare_strinfo first, except
105 for dont_invalidate which affects only the immediately next
108 /* Copy of index. get_strinfo (si->idx) should return si; */
110 /* These 3 fields are for chaining related string pointers together.
112 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
113 strcpy (c, d); e = c + dl;
114 strinfo(a) -> strinfo(c) -> strinfo(e)
115 All have ->first field equal to strinfo(a)->idx and are doubly
116 chained through prev/next fields. The later strinfos are required
117 to point into the same string with zero or more bytes after
118 the previous pointer and all bytes in between the two pointers
119 must be non-zero. Functions like strcpy or memcpy are supposed
120 to adjust all previous strinfo lengths, but not following strinfo
121 lengths (those are uncertain, usually invalidated during
122 maybe_invalidate, except when the alias oracle knows better).
123 Functions like strcat on the other side adjust the whole
124 related strinfo chain.
125 They are updated lazily, so to use the chain the same first fields
126 and si->prev->next == si->idx needs to be verified. */
130 /* A flag whether the string is known to be written in the current
133 /* A flag for the next maybe_invalidate that this strinfo shouldn't
134 be invalidated. Always cleared by maybe_invalidate. */
135 bool dont_invalidate
;
136 /* True if the string is known to be nul-terminated after NONZERO_CHARS
137 characters. False is useful when detecting strings that are built
138 up via successive memcpys. */
142 /* Pool for allocating strinfo_struct entries. */
143 static object_allocator
<strinfo
> strinfo_pool ("strinfo pool");
145 /* Vector mapping positive string indexes to strinfo, for the
146 current basic block. The first pointer in the vector is special,
147 it is either NULL, meaning the vector isn't shared, or it is
148 a basic block pointer to the owner basic_block if shared.
149 If some other bb wants to modify the vector, the vector needs
150 to be unshared first, and only the owner bb is supposed to free it. */
151 static vec
<strinfo
*, va_heap
, vl_embed
> *stridx_to_strinfo
;
153 /* One OFFSET->IDX mapping. */
156 struct stridxlist
*next
;
157 HOST_WIDE_INT offset
;
161 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
162 struct decl_stridxlist_map
164 struct tree_map_base base
;
165 struct stridxlist list
;
168 /* Hash table for mapping decls to a chained list of offset -> idx
170 typedef hash_map
<tree_decl_hash
, stridxlist
> decl_to_stridxlist_htab_t
;
171 static decl_to_stridxlist_htab_t
*decl_to_stridxlist_htab
;
173 /* Hash table mapping strlen (or strnlen with constant bound and return
174 smaller than bound) calls to stridx instances describing
175 the calls' arguments. Non-null only when warn_stringop_truncation
177 typedef std::pair
<int, location_t
> stridx_strlenloc
;
178 static hash_map
<tree
, stridx_strlenloc
> *strlen_to_stridx
;
180 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
181 static struct obstack stridx_obstack
;
183 /* Last memcpy statement if it could be adjusted if the trailing
184 '\0' written is immediately overwritten, or
185 *x = '\0' store that could be removed if it is immediately overwritten. */
186 struct laststmt_struct
193 static int get_stridx_plus_constant (strinfo
*, unsigned HOST_WIDE_INT
, tree
);
194 static void handle_builtin_stxncpy_strncat (bool, gimple_stmt_iterator
*);
196 /* Sets MINMAX to either the constant value or the range VAL is in
197 and returns either the constant value or VAL on success or null
198 when the range couldn't be determined. Uses RVALS when nonnull
199 to determine the range, otherwise get_range_info. */
202 get_range (tree val
, gimple
*stmt
, wide_int minmax
[2],
203 range_query
*rvals
/* = NULL */)
205 if (TREE_CODE (val
) == INTEGER_CST
)
207 minmax
[0] = minmax
[1] = wi::to_wide (val
);
211 if (TREE_CODE (val
) != SSA_NAME
)
217 if (!rvals
->range_of_expr (vr
, val
, stmt
))
219 value_range_kind rng
= vr
.kind ();
223 minmax
[0] = wi::to_wide (vr
.min ());
224 minmax
[1] = wi::to_wide (vr
.max ());
228 value_range_kind rng
= get_range_info (val
, minmax
, minmax
+ 1);
230 /* This may be an inverted range whose MINMAX[1] < MINMAX[0]. */
233 if (rng
== VR_ANTI_RANGE
)
235 /* An anti-range is the same as an ordinary range with inverted
236 bounds (where MINMAX[1] < MINMAX[0] is true) that may result
237 from the conversion of a signed anti-range to unsigned. */
238 wide_int tmp
= minmax
[0];
239 minmax
[0] = minmax
[1] + 1;
240 minmax
[1] = wi::sub (tmp
, 1);
244 /* Do not handle anti-ranges and instead make use of the on-demand
245 VRP if/when it becomes available (hopefully in GCC 11). */
251 * +1 if SI is known to start with more than OFF nonzero characters.
253 * 0 if SI is known to start with exactly OFF nonzero characters.
255 * -1 if SI either does not start with OFF nonzero characters
256 or the relationship between the number of leading nonzero
257 characters in SI and OFF is unknown. */
260 compare_nonzero_chars (strinfo
*si
, unsigned HOST_WIDE_INT off
)
262 if (si
->nonzero_chars
263 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
264 return compare_tree_int (si
->nonzero_chars
, off
);
269 /* Same as above but suitable also for strings with non-constant lengths.
270 Uses RVALS to determine length range. */
273 compare_nonzero_chars (strinfo
*si
, unsigned HOST_WIDE_INT off
,
276 if (!si
->nonzero_chars
)
279 if (TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
280 return compare_tree_int (si
->nonzero_chars
, off
);
282 if (!rvals
|| TREE_CODE (si
->nonzero_chars
) != SSA_NAME
)
286 if (!rvals
->range_of_expr (vr
, si
->nonzero_chars
, si
->stmt
))
288 value_range_kind rng
= vr
.kind ();
292 /* If the offset is less than the minimum length or if the bounds
293 of the length range are equal return the result of the comparison
294 same as in the constant case. Otherwise return a conservative
296 int cmpmin
= compare_tree_int (vr
.min (), off
);
297 if (cmpmin
> 0 || tree_int_cst_equal (vr
.min (), vr
.max ()))
303 /* Return true if SI is known to be a zero-length string. */
306 zero_length_string_p (strinfo
*si
)
308 return si
->full_string_p
&& integer_zerop (si
->nonzero_chars
);
311 /* Return strinfo vector entry IDX. */
313 static inline strinfo
*
314 get_strinfo (int idx
)
316 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
318 return (*stridx_to_strinfo
)[idx
];
321 /* Get the next strinfo in the chain after SI, or null if none. */
323 static inline strinfo
*
324 get_next_strinfo (strinfo
*si
)
328 strinfo
*nextsi
= get_strinfo (si
->next
);
329 if (nextsi
== NULL
|| nextsi
->first
!= si
->first
|| nextsi
->prev
!= si
->idx
)
334 /* Helper function for get_stridx. Return the strinfo index of the address
335 of EXP, which is available in PTR if nonnull. If OFFSET_OUT, it is
336 OK to return the index for some X <= &EXP and store &EXP - X in
337 *OFFSET_OUT. When RVALS is nonnull uses it to determine range
341 get_addr_stridx (tree exp
, tree ptr
, unsigned HOST_WIDE_INT
*offset_out
,
342 range_query
*rvals
= NULL
)
345 struct stridxlist
*list
, *last
= NULL
;
348 if (!decl_to_stridxlist_htab
)
352 base
= get_addr_base_and_unit_offset (exp
, &poff
);
353 if (base
== NULL
|| !DECL_P (base
) || !poff
.is_constant (&off
))
356 list
= decl_to_stridxlist_htab
->get (base
);
362 if (list
->offset
== off
)
368 if (list
->offset
> off
)
375 if ((offset_out
|| ptr
) && last
&& last
->idx
> 0)
377 unsigned HOST_WIDE_INT rel_off
378 = (unsigned HOST_WIDE_INT
) off
- last
->offset
;
379 strinfo
*si
= get_strinfo (last
->idx
);
380 if (si
&& compare_nonzero_chars (si
, rel_off
, rvals
) >= 0)
384 *offset_out
= rel_off
;
388 return get_stridx_plus_constant (si
, rel_off
, ptr
);
394 /* Returns string index for EXP. When EXP is an SSA_NAME that refers
395 to a known strinfo with an offset and OFFRNG is non-null, sets
396 both elements of the OFFRNG array to the range of the offset and
397 returns the index of the known strinfo. In this case the result
398 must not be used in for functions that modify the string.
399 When nonnull, uses RVALS to determine range information. */
402 get_stridx (tree exp
, wide_int offrng
[2] = NULL
, range_query
*rvals
= NULL
)
405 offrng
[0] = offrng
[1] = wi::zero (TYPE_PRECISION (ptrdiff_type_node
));
407 if (TREE_CODE (exp
) == SSA_NAME
)
409 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)])
410 return ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)];
414 HOST_WIDE_INT offset
= 0;
415 /* Follow a chain of at most 5 assignments. */
416 for (int i
= 0; i
< 5; i
++)
418 gimple
*def_stmt
= SSA_NAME_DEF_STMT (e
);
419 if (!is_gimple_assign (def_stmt
))
422 tree_code rhs_code
= gimple_assign_rhs_code (def_stmt
);
425 if (rhs_code
== ADDR_EXPR
)
427 /* Handle indices/offsets into VLAs which are implemented
428 as pointers to arrays. */
429 ptr
= gimple_assign_rhs1 (def_stmt
);
430 ptr
= TREE_OPERAND (ptr
, 0);
432 /* Handle also VLAs of types larger than char. */
433 if (tree eltsize
= TYPE_SIZE_UNIT (TREE_TYPE (ptr
)))
435 if (TREE_CODE (ptr
) == ARRAY_REF
)
437 off
= TREE_OPERAND (ptr
, 1);
438 ptr
= TREE_OPERAND (ptr
, 0);
439 if (!integer_onep (eltsize
))
441 /* Scale the array index by the size of the element
442 type in the rare case that it's greater than
443 the typical 1 for char, making sure both operands
444 have the same type. */
445 eltsize
= fold_convert (ssizetype
, eltsize
);
446 off
= fold_convert (ssizetype
, off
);
447 off
= fold_build2 (MULT_EXPR
, ssizetype
, off
, eltsize
);
451 off
= integer_zero_node
;
456 if (TREE_CODE (ptr
) != MEM_REF
)
459 /* Add the MEM_REF byte offset. */
460 tree mem_off
= TREE_OPERAND (ptr
, 1);
461 off
= fold_build2 (PLUS_EXPR
, TREE_TYPE (off
), off
, mem_off
);
462 ptr
= TREE_OPERAND (ptr
, 0);
464 else if (rhs_code
== POINTER_PLUS_EXPR
)
466 ptr
= gimple_assign_rhs1 (def_stmt
);
467 off
= gimple_assign_rhs2 (def_stmt
);
472 if (TREE_CODE (ptr
) != SSA_NAME
)
475 if (!tree_fits_shwi_p (off
))
477 if (int idx
= ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)])
480 /* Only when requested by setting OFFRNG to non-null,
481 return the index corresponding to the SSA_NAME.
482 Do this irrespective of the whether the offset
484 if (get_range (off
, def_stmt
, offrng
, rvals
))
486 /* When the offset range is known, increment it
487 it by the constant offset computed in prior
488 iterations and store it in the OFFRNG array. */
494 /* When the offset range cannot be determined
495 store [0, SIZE_MAX] and let the caller decide
496 if the offset matters. */
497 offrng
[1] = wi::to_wide (TYPE_MAX_VALUE (sizetype
));
498 offrng
[0] = wi::zero (offrng
[1].get_precision ());
505 HOST_WIDE_INT this_off
= tree_to_shwi (off
);
508 offrng
[0] += wi::shwi (this_off
, offrng
->get_precision ());
509 offrng
[1] += offrng
[0];
515 offset
= (unsigned HOST_WIDE_INT
) offset
+ this_off
;
519 if (int idx
= ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)])
521 strinfo
*si
= get_strinfo (idx
);
524 if (compare_nonzero_chars (si
, offset
) >= 0)
525 return get_stridx_plus_constant (si
, offset
, exp
);
537 if (TREE_CODE (exp
) == ADDR_EXPR
)
539 int idx
= get_addr_stridx (TREE_OPERAND (exp
, 0), exp
, NULL
);
544 const char *p
= c_getstr (exp
);
546 return ~(int) strlen (p
);
551 /* Return true if strinfo vector is shared with the immediate dominator. */
554 strinfo_shared (void)
556 return vec_safe_length (stridx_to_strinfo
)
557 && (*stridx_to_strinfo
)[0] != NULL
;
560 /* Unshare strinfo vector that is shared with the immediate dominator. */
563 unshare_strinfo_vec (void)
568 gcc_assert (strinfo_shared ());
569 stridx_to_strinfo
= vec_safe_copy (stridx_to_strinfo
);
570 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
573 (*stridx_to_strinfo
)[0] = NULL
;
576 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
577 Return a pointer to the location where the string index can
578 be stored (if 0) or is stored, or NULL if this can't be tracked. */
581 addr_stridxptr (tree exp
)
586 tree base
= get_addr_base_and_unit_offset (exp
, &poff
);
587 if (base
== NULL_TREE
|| !DECL_P (base
) || !poff
.is_constant (&off
))
590 if (!decl_to_stridxlist_htab
)
592 decl_to_stridxlist_htab
593 = new hash_map
<tree_decl_hash
, stridxlist
> (64);
594 gcc_obstack_init (&stridx_obstack
);
598 stridxlist
*list
= &decl_to_stridxlist_htab
->get_or_insert (base
, &existed
);
602 stridxlist
*before
= NULL
;
603 for (i
= 0; i
< 32; i
++)
605 if (list
->offset
== off
)
607 if (list
->offset
> off
&& before
== NULL
)
609 if (list
->next
== NULL
)
618 before
= XOBNEW (&stridx_obstack
, struct stridxlist
);
625 list
->next
= XOBNEW (&stridx_obstack
, struct stridxlist
);
635 /* Create a new string index, or return 0 if reached limit. */
638 new_stridx (tree exp
)
641 if (max_stridx
>= param_max_tracked_strlens
)
643 if (TREE_CODE (exp
) == SSA_NAME
)
645 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
))
648 ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)] = idx
;
651 if (TREE_CODE (exp
) == ADDR_EXPR
)
653 int *pidx
= addr_stridxptr (TREE_OPERAND (exp
, 0));
656 gcc_assert (*pidx
== 0);
657 *pidx
= max_stridx
++;
664 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
667 new_addr_stridx (tree exp
)
670 if (max_stridx
>= param_max_tracked_strlens
)
672 pidx
= addr_stridxptr (exp
);
675 gcc_assert (*pidx
== 0);
676 *pidx
= max_stridx
++;
682 /* Create a new strinfo. */
685 new_strinfo (tree ptr
, int idx
, tree nonzero_chars
, bool full_string_p
)
687 strinfo
*si
= strinfo_pool
.allocate ();
688 si
->nonzero_chars
= nonzero_chars
;
689 STRIP_USELESS_TYPE_CONVERSION (ptr
);
693 si
->endptr
= NULL_TREE
;
699 si
->writable
= false;
700 si
->dont_invalidate
= false;
701 si
->full_string_p
= full_string_p
;
705 /* Decrease strinfo refcount and free it if not referenced anymore. */
708 free_strinfo (strinfo
*si
)
710 if (si
&& --si
->refcount
== 0)
711 strinfo_pool
.remove (si
);
714 /* Set strinfo in the vector entry IDX to SI. */
717 set_strinfo (int idx
, strinfo
*si
)
719 if (vec_safe_length (stridx_to_strinfo
) && (*stridx_to_strinfo
)[0])
720 unshare_strinfo_vec ();
721 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
722 vec_safe_grow_cleared (stridx_to_strinfo
, idx
+ 1, true);
723 (*stridx_to_strinfo
)[idx
] = si
;
726 /* Return the first strinfo in the related strinfo chain
727 if all strinfos in between belong to the chain, otherwise NULL. */
730 verify_related_strinfos (strinfo
*origsi
)
732 strinfo
*si
= origsi
, *psi
;
734 if (origsi
->first
== 0)
736 for (; si
->prev
; si
= psi
)
738 if (si
->first
!= origsi
->first
)
740 psi
= get_strinfo (si
->prev
);
743 if (psi
->next
!= si
->idx
)
746 if (si
->idx
!= si
->first
)
751 /* Set SI's endptr to ENDPTR and compute its length based on SI->ptr.
752 Use LOC for folding. */
755 set_endptr_and_length (location_t loc
, strinfo
*si
, tree endptr
)
759 tree start_as_size
= fold_convert_loc (loc
, size_type_node
, si
->ptr
);
760 tree end_as_size
= fold_convert_loc (loc
, size_type_node
, endptr
);
761 si
->nonzero_chars
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
762 end_as_size
, start_as_size
);
763 si
->full_string_p
= true;
766 /* Return the string length, or NULL if it can't be computed.
767 The length may but need not be constant. Instead, it might be
768 the result of a strlen() call. */
771 get_string_length (strinfo
*si
)
773 /* If the length has already been computed return it if it's exact
774 (i.e., the string is nul-terminated at NONZERO_CHARS), or return
776 if (si
->nonzero_chars
)
777 return si
->full_string_p
? si
->nonzero_chars
: NULL
;
779 /* If the string is the result of one of the built-in calls below
780 attempt to compute the length from the call statement. */
783 gimple
*stmt
= si
->stmt
, *lenstmt
;
784 tree callee
, lhs
, fn
, tem
;
786 gimple_stmt_iterator gsi
;
788 gcc_assert (is_gimple_call (stmt
));
789 callee
= gimple_call_fndecl (stmt
);
790 gcc_assert (callee
&& fndecl_built_in_p (callee
, BUILT_IN_NORMAL
));
791 lhs
= gimple_call_lhs (stmt
);
792 /* unshare_strinfo is intentionally not called here. The (delayed)
793 transformation of strcpy or strcat into stpcpy is done at the place
794 of the former strcpy/strcat call and so can affect all the strinfos
795 with the same stmt. If they were unshared before and transformation
796 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
797 just compute the right length. */
798 switch (DECL_FUNCTION_CODE (callee
))
800 case BUILT_IN_STRCAT
:
801 case BUILT_IN_STRCAT_CHK
:
802 gsi
= gsi_for_stmt (stmt
);
803 fn
= builtin_decl_implicit (BUILT_IN_STRLEN
);
804 gcc_assert (lhs
== NULL_TREE
);
805 tem
= unshare_expr (gimple_call_arg (stmt
, 0));
806 lenstmt
= gimple_build_call (fn
, 1, tem
);
807 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), lenstmt
);
808 gimple_call_set_lhs (lenstmt
, lhs
);
809 gimple_set_vuse (lenstmt
, gimple_vuse (stmt
));
810 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
811 tem
= gimple_call_arg (stmt
, 0);
812 if (!ptrofftype_p (TREE_TYPE (lhs
)))
814 lhs
= convert_to_ptrofftype (lhs
);
815 lhs
= force_gimple_operand_gsi (&gsi
, lhs
, true, NULL_TREE
,
816 true, GSI_SAME_STMT
);
818 lenstmt
= gimple_build_assign
819 (make_ssa_name (TREE_TYPE (gimple_call_arg (stmt
, 0))),
820 POINTER_PLUS_EXPR
,tem
, lhs
);
821 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
822 gimple_call_set_arg (stmt
, 0, gimple_assign_lhs (lenstmt
));
825 case BUILT_IN_STRCPY
:
826 case BUILT_IN_STRCPY_CHK
:
827 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY
));
828 if (gimple_call_num_args (stmt
) == 2)
829 fn
= builtin_decl_implicit (BUILT_IN_STPCPY
);
831 fn
= builtin_decl_explicit (BUILT_IN_STPCPY_CHK
);
832 gcc_assert (lhs
== NULL_TREE
);
833 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
835 fprintf (dump_file
, "Optimizing: ");
836 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
838 gimple_call_set_fndecl (stmt
, fn
);
839 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), stmt
);
840 gimple_call_set_lhs (stmt
, lhs
);
842 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
844 fprintf (dump_file
, "into: ");
845 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
848 case BUILT_IN_STPCPY
:
849 case BUILT_IN_STPCPY_CHK
:
850 gcc_assert (lhs
!= NULL_TREE
);
851 loc
= gimple_location (stmt
);
852 set_endptr_and_length (loc
, si
, lhs
);
853 for (strinfo
*chainsi
= verify_related_strinfos (si
);
855 chainsi
= get_next_strinfo (chainsi
))
856 if (chainsi
->nonzero_chars
== NULL
)
857 set_endptr_and_length (loc
, chainsi
, lhs
);
859 case BUILT_IN_ALLOCA
:
860 case BUILT_IN_ALLOCA_WITH_ALIGN
:
861 case BUILT_IN_MALLOC
:
863 /* BUILT_IN_CALLOC always has si->nonzero_chars set. */
870 return si
->nonzero_chars
;
873 /* Dump strlen data to FP for statement STMT. When non-null, RVALS
874 points to the valuation engine used to calculate ranges, and is
875 used to dump strlen range for non-constant results. */
878 dump_strlen_info (FILE *fp
, gimple
*stmt
, range_query
*rvals
)
882 fprintf (fp
, "\nDumping strlen pass data after ");
883 print_gimple_expr (fp
, stmt
, TDF_LINENO
);
887 fprintf (fp
, "\nDumping strlen pass data\n");
889 fprintf (fp
, "max_stridx = %i\n", max_stridx
);
890 fprintf (fp
, "ssa_ver_to_stridx has %u elements\n",
891 ssa_ver_to_stridx
.length ());
892 fprintf (fp
, "stridx_to_strinfo");
893 if (stridx_to_strinfo
)
895 fprintf (fp
, " has %u elements\n", stridx_to_strinfo
->length ());
896 for (unsigned i
= 0; i
!= stridx_to_strinfo
->length (); ++i
)
898 if (strinfo
*si
= (*stridx_to_strinfo
)[i
])
902 fprintf (fp
, " idx = %i", si
->idx
);
905 fprintf (fp
, ", ptr = ");
906 print_generic_expr (fp
, si
->ptr
);
909 if (si
->nonzero_chars
)
911 fprintf (fp
, ", nonzero_chars = ");
912 print_generic_expr (fp
, si
->nonzero_chars
);
913 if (TREE_CODE (si
->nonzero_chars
) == SSA_NAME
)
915 value_range_kind rng
= VR_UNDEFINED
;
920 rvals
->range_of_expr (vr
, si
->nonzero_chars
,
923 if (range_int_cst_p (&vr
))
925 min
= wi::to_wide (vr
.min ());
926 max
= wi::to_wide (vr
.max ());
932 rng
= get_range_info (si
->nonzero_chars
, &min
, &max
);
934 if (rng
== VR_RANGE
|| rng
== VR_ANTI_RANGE
)
936 fprintf (fp
, " %s[%llu, %llu]",
937 rng
== VR_RANGE
? "" : "~",
938 (long long) min
.to_uhwi (),
939 (long long) max
.to_uhwi ());
944 fprintf (fp
, ", refcount = %i", si
->refcount
);
947 fprintf (fp
, ", stmt = ");
948 print_gimple_expr (fp
, si
->stmt
, 0);
952 fprintf (fp
, ", alloc = ");
953 print_gimple_expr (fp
, si
->alloc
, 0);
956 fprintf (fp
, ", writable");
957 if (si
->dont_invalidate
)
958 fprintf (fp
, ", dont_invalidate");
959 if (si
->full_string_p
)
960 fprintf (fp
, ", full_string_p");
961 if (strinfo
*next
= get_next_strinfo (si
))
965 fprintf (fp
, "%i%s", next
->idx
, next
->first
? ", " : "");
966 while ((next
= get_next_strinfo (next
)));
974 fprintf (fp
, " = null\n");
976 fprintf (fp
, "decl_to_stridxlist_htab");
977 if (decl_to_stridxlist_htab
)
980 typedef decl_to_stridxlist_htab_t::iterator iter_t
;
981 for (iter_t it
= decl_to_stridxlist_htab
->begin ();
982 it
!= decl_to_stridxlist_htab
->end (); ++it
)
984 tree decl
= (*it
).first
;
985 stridxlist
*list
= &(*it
).second
;
986 fprintf (fp
, " decl = ");
987 print_generic_expr (fp
, decl
);
990 fprintf (fp
, ", offsets = {");
991 for (; list
; list
= list
->next
)
992 fprintf (fp
, "%lli%s", (long long) list
->offset
,
993 list
->next
? ", " : "");
1000 fprintf (fp
, " = null\n");
1004 fprintf (fp
, "laststmt = ");
1005 print_gimple_expr (fp
, laststmt
.stmt
, 0);
1006 fprintf (fp
, ", len = ");
1007 print_generic_expr (fp
, laststmt
.len
);
1008 fprintf (fp
, ", stridx = %i\n", laststmt
.stridx
);
1012 /* Attempt to determine the length of the string SRC. On success, store
1013 the length in *PDATA and return true. Otherwise, return false.
1014 VISITED is a bitmap of visited PHI nodes. RVALS points to the valuation
1015 engine used to calculate ranges. PSSA_DEF_MAX to an SSA_NAME
1016 assignment limit used to prevent runaway recursion. */
1019 get_range_strlen_dynamic (tree src
, gimple
*stmt
,
1020 c_strlen_data
*pdata
, bitmap
*visited
,
1021 range_query
*rvals
, unsigned *pssa_def_max
)
1023 int idx
= get_stridx (src
);
1026 if (TREE_CODE (src
) == SSA_NAME
)
1028 gimple
*def_stmt
= SSA_NAME_DEF_STMT (src
);
1029 if (gimple_code (def_stmt
) == GIMPLE_PHI
)
1032 *visited
= BITMAP_ALLOC (NULL
);
1034 if (!bitmap_set_bit (*visited
, SSA_NAME_VERSION (src
)))
1037 if (*pssa_def_max
== 0)
1042 /* Iterate over the PHI arguments and determine the minimum
1043 and maximum length/size of each and incorporate them into
1044 the overall result. */
1045 gphi
*phi
= as_a
<gphi
*> (def_stmt
);
1046 for (unsigned i
= 0; i
!= gimple_phi_num_args (phi
); ++i
)
1048 tree arg
= gimple_phi_arg_def (phi
, i
);
1049 if (arg
== gimple_phi_result (def_stmt
))
1052 c_strlen_data argdata
= { };
1053 if (get_range_strlen_dynamic (arg
, phi
, &argdata
, visited
,
1054 rvals
, pssa_def_max
))
1056 /* Set the DECL of an unterminated array this argument
1057 refers to if one hasn't been found yet. */
1058 if (!pdata
->decl
&& argdata
.decl
)
1059 pdata
->decl
= argdata
.decl
;
1062 || (integer_zerop (argdata
.minlen
)
1063 && (!argdata
.maxbound
1064 || integer_all_onesp (argdata
.maxbound
))
1065 && integer_all_onesp (argdata
.maxlen
)))
1067 /* Set the upper bound of the length to unbounded. */
1068 pdata
->maxlen
= build_all_ones_cst (size_type_node
);
1072 /* Adjust the minimum and maximum length determined
1073 so far and the upper bound on the array size. */
1075 || tree_int_cst_lt (argdata
.minlen
, pdata
->minlen
))
1076 pdata
->minlen
= argdata
.minlen
;
1079 && tree_int_cst_lt (pdata
->maxlen
, argdata
.maxlen
)))
1080 pdata
->maxlen
= argdata
.maxlen
;
1081 if (!pdata
->maxbound
1082 || TREE_CODE (pdata
->maxbound
) != INTEGER_CST
1083 || (argdata
.maxbound
1084 && tree_int_cst_lt (pdata
->maxbound
,
1086 && !integer_all_onesp (argdata
.maxbound
)))
1087 pdata
->maxbound
= argdata
.maxbound
;
1090 pdata
->maxlen
= build_all_ones_cst (size_type_node
);
1097 /* Return success regardless of the result and handle *PDATA
1099 get_range_strlen (src
, pdata
, 1);
1105 /* SRC is a string of constant length. */
1106 pdata
->minlen
= build_int_cst (size_type_node
, ~idx
);
1107 pdata
->maxlen
= pdata
->minlen
;
1108 pdata
->maxbound
= pdata
->maxlen
;
1112 if (strinfo
*si
= get_strinfo (idx
))
1114 pdata
->minlen
= get_string_length (si
);
1115 if (!pdata
->minlen
&& si
->nonzero_chars
)
1117 if (TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
1118 pdata
->minlen
= si
->nonzero_chars
;
1119 else if (TREE_CODE (si
->nonzero_chars
) == SSA_NAME
)
1122 rvals
->range_of_expr (vr
, si
->nonzero_chars
, si
->stmt
);
1123 if (range_int_cst_p (&vr
))
1125 pdata
->minlen
= vr
.min ();
1126 pdata
->maxlen
= vr
.max ();
1129 pdata
->minlen
= build_zero_cst (size_type_node
);
1132 pdata
->minlen
= build_zero_cst (size_type_node
);
1134 tree base
= si
->ptr
;
1135 if (TREE_CODE (base
) == ADDR_EXPR
)
1136 base
= TREE_OPERAND (base
, 0);
1140 base
= get_addr_base_and_unit_offset (base
, &poff
);
1143 && TREE_CODE (TREE_TYPE (base
)) == ARRAY_TYPE
1144 && TYPE_SIZE_UNIT (TREE_TYPE (base
))
1145 && poff
.is_constant (&off
))
1147 tree basetype
= TREE_TYPE (base
);
1148 tree size
= TYPE_SIZE_UNIT (basetype
);
1149 if (TREE_CODE (size
) == INTEGER_CST
)
1151 ++off
; /* Increment for the terminating nul. */
1152 tree toffset
= build_int_cst (size_type_node
, off
);
1153 pdata
->maxlen
= fold_build2 (MINUS_EXPR
, size_type_node
, size
,
1155 pdata
->maxbound
= pdata
->maxlen
;
1158 pdata
->maxlen
= build_all_ones_cst (size_type_node
);
1161 pdata
->maxlen
= build_all_ones_cst (size_type_node
);
1163 else if (pdata
->minlen
&& TREE_CODE (pdata
->minlen
) == SSA_NAME
)
1166 rvals
->range_of_expr (vr
, si
->nonzero_chars
, stmt
);
1167 if (range_int_cst_p (&vr
))
1169 pdata
->minlen
= vr
.min ();
1170 pdata
->maxlen
= vr
.max ();
1171 pdata
->maxbound
= pdata
->maxlen
;
1175 pdata
->minlen
= build_zero_cst (size_type_node
);
1176 pdata
->maxlen
= build_all_ones_cst (size_type_node
);
1179 else if (pdata
->minlen
&& TREE_CODE (pdata
->minlen
) == INTEGER_CST
)
1181 pdata
->maxlen
= pdata
->minlen
;
1182 pdata
->maxbound
= pdata
->minlen
;
1186 /* For PDATA->MINLEN that's a non-constant expression such
1187 as PLUS_EXPR whose value range is unknown, set the bounds
1188 to zero and SIZE_MAX. */
1189 pdata
->minlen
= build_zero_cst (size_type_node
);
1190 pdata
->maxlen
= build_all_ones_cst (size_type_node
);
1199 /* Analogous to get_range_strlen but for dynamically created strings,
1200 i.e., those created by calls to strcpy as opposed to just string
1202 Try to obtain the range of the lengths of the string(s) referenced
1203 by SRC, or the size of the largest array SRC refers to if the range
1204 of lengths cannot be determined, and store all in *PDATA. RVALS
1205 points to the valuation engine used to calculate ranges. */
1208 get_range_strlen_dynamic (tree src
, gimple
*stmt
, c_strlen_data
*pdata
,
1211 bitmap visited
= NULL
;
1212 tree maxbound
= pdata
->maxbound
;
1214 unsigned limit
= param_ssa_name_def_chain_limit
;
1215 if (!get_range_strlen_dynamic (src
, stmt
, pdata
, &visited
, rvals
, &limit
))
1217 /* On failure extend the length range to an impossible maximum
1218 (a valid MAXLEN must be less than PTRDIFF_MAX - 1). Other
1219 members can stay unchanged regardless. */
1220 pdata
->minlen
= ssize_int (0);
1221 pdata
->maxlen
= build_all_ones_cst (size_type_node
);
1223 else if (!pdata
->minlen
)
1224 pdata
->minlen
= ssize_int (0);
1226 /* If it's unchanged from it initial non-null value, set the conservative
1227 MAXBOUND to SIZE_MAX. Otherwise leave it null (if it is null). */
1228 if (maxbound
&& pdata
->maxbound
== maxbound
)
1229 pdata
->maxbound
= build_all_ones_cst (size_type_node
);
1232 BITMAP_FREE (visited
);
1235 /* Invalidate string length information for strings whose length might
1236 change due to stores in STMT, except those marked DONT_INVALIDATE.
1237 For string-modifying statements, ZERO_WRITE is set when the statement
1239 Returns true if any STRIDX_TO_STRINFO entries were considered
1240 for invalidation. */
1243 maybe_invalidate (gimple
*stmt
, bool zero_write
= false)
1245 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1247 fprintf (dump_file
, "%s called for ", __func__
);
1248 print_gimple_stmt (dump_file
, stmt
, TDF_LINENO
);
1252 bool nonempty
= false;
1254 for (unsigned i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
1256 if (si
== NULL
|| !POINTER_TYPE_P (TREE_TYPE (si
->ptr
)))
1261 /* Unconditionally reset DONT_INVALIDATE. */
1262 bool dont_invalidate
= si
->dont_invalidate
;
1263 si
->dont_invalidate
= false;
1265 if (dont_invalidate
)
1269 tree size
= NULL_TREE
;
1270 if (si
->nonzero_chars
)
1272 /* Include the terminating nul in the size of the string
1273 to consider when determining possible clobber. */
1274 tree type
= TREE_TYPE (si
->nonzero_chars
);
1275 size
= fold_build2 (PLUS_EXPR
, type
, si
->nonzero_chars
,
1276 build_int_cst (type
, 1));
1278 ao_ref_init_from_ptr_and_size (&r
, si
->ptr
, size
);
1279 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
1281 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1283 fputs (" statement may clobber object ", dump_file
);
1284 print_generic_expr (dump_file
, si
->ptr
);
1285 if (size
&& tree_fits_uhwi_p (size
))
1286 fprintf (dump_file
, " " HOST_WIDE_INT_PRINT_UNSIGNED
1287 " bytes in size", tree_to_uhwi (size
));
1288 fputc ('\n', dump_file
);
1291 set_strinfo (i
, NULL
);
1299 && is_gimple_call (si
->stmt
)
1300 && (DECL_FUNCTION_CODE (gimple_call_fndecl (si
->stmt
))
1301 == BUILT_IN_CALLOC
))
1303 /* If the clobber test above considered the length of
1304 the string (including the nul), then for (potentially)
1305 non-zero writes that might modify storage allocated by
1306 calloc consider the whole object and if it might be
1307 clobbered by the statement reset the statement. */
1308 ao_ref_init_from_ptr_and_size (&r
, si
->ptr
, NULL_TREE
);
1309 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
1314 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1315 fprintf (dump_file
, "%s returns %i\n", __func__
, nonempty
);
1320 /* Unshare strinfo record SI, if it has refcount > 1 or
1321 if stridx_to_strinfo vector is shared with some other
1325 unshare_strinfo (strinfo
*si
)
1329 if (si
->refcount
== 1 && !strinfo_shared ())
1332 nsi
= new_strinfo (si
->ptr
, si
->idx
, si
->nonzero_chars
, si
->full_string_p
);
1333 nsi
->stmt
= si
->stmt
;
1334 nsi
->alloc
= si
->alloc
;
1335 nsi
->endptr
= si
->endptr
;
1336 nsi
->first
= si
->first
;
1337 nsi
->prev
= si
->prev
;
1338 nsi
->next
= si
->next
;
1339 nsi
->writable
= si
->writable
;
1340 set_strinfo (si
->idx
, nsi
);
1345 /* Attempt to create a new strinfo for BASESI + OFF, or find existing
1346 strinfo if there is any. Return it's idx, or 0 if no strinfo has
1350 get_stridx_plus_constant (strinfo
*basesi
, unsigned HOST_WIDE_INT off
,
1353 if (TREE_CODE (ptr
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
1356 if (compare_nonzero_chars (basesi
, off
) < 0
1357 || !tree_fits_uhwi_p (basesi
->nonzero_chars
))
1360 unsigned HOST_WIDE_INT nonzero_chars
1361 = tree_to_uhwi (basesi
->nonzero_chars
) - off
;
1362 strinfo
*si
= basesi
, *chainsi
;
1363 if (si
->first
|| si
->prev
|| si
->next
)
1364 si
= verify_related_strinfos (basesi
);
1366 || si
->nonzero_chars
== NULL_TREE
1367 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
1370 if (TREE_CODE (ptr
) == SSA_NAME
1371 && ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
1372 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
, true);
1374 gcc_checking_assert (compare_tree_int (si
->nonzero_chars
, off
) != -1);
1375 for (chainsi
= si
; chainsi
->next
; chainsi
= si
)
1377 si
= get_next_strinfo (chainsi
);
1379 || si
->nonzero_chars
== NULL_TREE
1380 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
1382 int r
= compare_tree_int (si
->nonzero_chars
, nonzero_chars
);
1387 if (TREE_CODE (ptr
) == SSA_NAME
)
1388 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = si
->idx
;
1391 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
1392 if (pidx
!= NULL
&& *pidx
== 0)
1401 int idx
= new_stridx (ptr
);
1404 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, nonzero_chars
),
1405 basesi
->full_string_p
);
1406 set_strinfo (idx
, si
);
1407 if (strinfo
*nextsi
= get_strinfo (chainsi
->next
))
1409 nextsi
= unshare_strinfo (nextsi
);
1410 si
->next
= nextsi
->idx
;
1413 chainsi
= unshare_strinfo (chainsi
);
1414 if (chainsi
->first
== 0)
1415 chainsi
->first
= chainsi
->idx
;
1416 chainsi
->next
= idx
;
1417 if (chainsi
->endptr
== NULL_TREE
&& zero_length_string_p (si
))
1418 chainsi
->endptr
= ptr
;
1419 si
->endptr
= chainsi
->endptr
;
1420 si
->prev
= chainsi
->idx
;
1421 si
->first
= chainsi
->first
;
1422 si
->writable
= chainsi
->writable
;
1426 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
1427 to a zero-length string and if possible chain it to a related strinfo
1428 chain whose part is or might be CHAINSI. */
1431 zero_length_string (tree ptr
, strinfo
*chainsi
)
1435 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
1436 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
, true);
1437 gcc_checking_assert (TREE_CODE (ptr
) == SSA_NAME
1438 && ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] == 0);
1440 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
1442 if (chainsi
!= NULL
)
1444 si
= verify_related_strinfos (chainsi
);
1449 /* We shouldn't mix delayed and non-delayed lengths. */
1450 gcc_assert (si
->full_string_p
);
1451 if (si
->endptr
== NULL_TREE
)
1453 si
= unshare_strinfo (si
);
1457 si
= get_next_strinfo (si
);
1460 if (zero_length_string_p (chainsi
))
1464 chainsi
= unshare_strinfo (chainsi
);
1467 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = chainsi
->idx
;
1473 /* We shouldn't mix delayed and non-delayed lengths. */
1474 gcc_assert (chainsi
->full_string_p
);
1475 if (chainsi
->first
|| chainsi
->prev
|| chainsi
->next
)
1477 chainsi
= unshare_strinfo (chainsi
);
1484 idx
= new_stridx (ptr
);
1487 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, 0), true);
1488 set_strinfo (idx
, si
);
1490 if (chainsi
!= NULL
)
1492 chainsi
= unshare_strinfo (chainsi
);
1493 if (chainsi
->first
== 0)
1494 chainsi
->first
= chainsi
->idx
;
1495 chainsi
->next
= idx
;
1496 if (chainsi
->endptr
== NULL_TREE
)
1497 chainsi
->endptr
= ptr
;
1498 si
->prev
= chainsi
->idx
;
1499 si
->first
= chainsi
->first
;
1500 si
->writable
= chainsi
->writable
;
1505 /* For strinfo ORIGSI whose length has been just updated, adjust other
1506 related strinfos so that they match the new ORIGSI. This involves:
1508 - adding ADJ to the nonzero_chars fields
1509 - copying full_string_p from the new ORIGSI. */
1512 adjust_related_strinfos (location_t loc
, strinfo
*origsi
, tree adj
)
1514 strinfo
*si
= verify_related_strinfos (origsi
);
1527 si
= unshare_strinfo (si
);
1528 /* We shouldn't see delayed lengths here; the caller must
1529 have calculated the old length in order to calculate
1531 gcc_assert (si
->nonzero_chars
);
1532 tem
= fold_convert_loc (loc
, TREE_TYPE (si
->nonzero_chars
), adj
);
1533 si
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
1534 TREE_TYPE (si
->nonzero_chars
),
1535 si
->nonzero_chars
, tem
);
1536 si
->full_string_p
= origsi
->full_string_p
;
1538 si
->endptr
= NULL_TREE
;
1539 si
->dont_invalidate
= true;
1541 nsi
= get_next_strinfo (si
);
1548 /* Find if there are other SSA_NAME pointers equal to PTR
1549 for which we don't track their string lengths yet. If so, use
1553 find_equal_ptrs (tree ptr
, int idx
)
1555 if (TREE_CODE (ptr
) != SSA_NAME
)
1559 gimple
*stmt
= SSA_NAME_DEF_STMT (ptr
);
1560 if (!is_gimple_assign (stmt
))
1562 ptr
= gimple_assign_rhs1 (stmt
);
1563 switch (gimple_assign_rhs_code (stmt
))
1568 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)))
1570 if (TREE_CODE (ptr
) == SSA_NAME
)
1572 if (TREE_CODE (ptr
) != ADDR_EXPR
)
1577 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
1578 if (pidx
!= NULL
&& *pidx
== 0)
1586 /* We might find an endptr created in this pass. Grow the
1587 vector in that case. */
1588 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
1589 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
, true);
1591 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] != 0)
1593 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = idx
;
1597 /* Return true if STMT is a call to a builtin function with the right
1598 arguments and attributes that should be considered for optimization
1602 valid_builtin_call (gimple
*stmt
)
1604 if (!gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
1607 tree callee
= gimple_call_fndecl (stmt
);
1608 tree decl
= builtin_decl_explicit (DECL_FUNCTION_CODE (callee
));
1611 && !gimple_builtin_call_types_compatible_p (stmt
, decl
))
1614 switch (DECL_FUNCTION_CODE (callee
))
1616 case BUILT_IN_MEMCMP
:
1617 case BUILT_IN_MEMCMP_EQ
:
1618 case BUILT_IN_STRCMP
:
1619 case BUILT_IN_STRNCMP
:
1620 case BUILT_IN_STRCHR
:
1621 case BUILT_IN_STRLEN
:
1622 case BUILT_IN_STRNLEN
:
1623 /* The above functions should be pure. Punt if they aren't. */
1624 if (gimple_vdef (stmt
) || gimple_vuse (stmt
) == NULL_TREE
)
1628 case BUILT_IN_ALLOCA
:
1629 case BUILT_IN_ALLOCA_WITH_ALIGN
:
1630 case BUILT_IN_CALLOC
:
1631 case BUILT_IN_MALLOC
:
1632 case BUILT_IN_MEMCPY
:
1633 case BUILT_IN_MEMCPY_CHK
:
1634 case BUILT_IN_MEMPCPY
:
1635 case BUILT_IN_MEMPCPY_CHK
:
1636 case BUILT_IN_MEMSET
:
1637 case BUILT_IN_STPCPY
:
1638 case BUILT_IN_STPCPY_CHK
:
1639 case BUILT_IN_STPNCPY
:
1640 case BUILT_IN_STPNCPY_CHK
:
1641 case BUILT_IN_STRCAT
:
1642 case BUILT_IN_STRCAT_CHK
:
1643 case BUILT_IN_STRCPY
:
1644 case BUILT_IN_STRCPY_CHK
:
1645 case BUILT_IN_STRNCAT
:
1646 case BUILT_IN_STRNCAT_CHK
:
1647 case BUILT_IN_STRNCPY
:
1648 case BUILT_IN_STRNCPY_CHK
:
1649 /* The above functions should be neither const nor pure. Punt if they
1651 if (gimple_vdef (stmt
) == NULL_TREE
|| gimple_vuse (stmt
) == NULL_TREE
)
1662 /* If the last .MEM setter statement before STMT is
1663 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
1664 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
1665 just memcpy (x, y, strlen (y)). SI must be the zero length
1669 adjust_last_stmt (strinfo
*si
, gimple
*stmt
, bool is_strcat
,
1670 pointer_query
&ptr_qry
)
1672 tree vuse
, callee
, len
;
1673 struct laststmt_struct last
= laststmt
;
1674 strinfo
*lastsi
, *firstsi
;
1675 unsigned len_arg_no
= 2;
1677 laststmt
.stmt
= NULL
;
1678 laststmt
.len
= NULL_TREE
;
1679 laststmt
.stridx
= 0;
1681 if (last
.stmt
== NULL
)
1684 vuse
= gimple_vuse (stmt
);
1685 if (vuse
== NULL_TREE
1686 || SSA_NAME_DEF_STMT (vuse
) != last
.stmt
1687 || !has_single_use (vuse
))
1690 gcc_assert (last
.stridx
> 0);
1691 lastsi
= get_strinfo (last
.stridx
);
1697 if (lastsi
->first
== 0 || lastsi
->first
!= si
->first
)
1700 firstsi
= verify_related_strinfos (si
);
1701 if (firstsi
== NULL
)
1703 while (firstsi
!= lastsi
)
1705 firstsi
= get_next_strinfo (firstsi
);
1706 if (firstsi
== NULL
)
1711 if (!is_strcat
&& !zero_length_string_p (si
))
1714 if (is_gimple_assign (last
.stmt
))
1716 gimple_stmt_iterator gsi
;
1718 if (!integer_zerop (gimple_assign_rhs1 (last
.stmt
)))
1720 if (stmt_could_throw_p (cfun
, last
.stmt
))
1722 gsi
= gsi_for_stmt (last
.stmt
);
1723 unlink_stmt_vdef (last
.stmt
);
1724 release_defs (last
.stmt
);
1725 gsi_remove (&gsi
, true);
1729 if (!valid_builtin_call (last
.stmt
))
1732 callee
= gimple_call_fndecl (last
.stmt
);
1733 switch (DECL_FUNCTION_CODE (callee
))
1735 case BUILT_IN_MEMCPY
:
1736 case BUILT_IN_MEMCPY_CHK
:
1742 len
= gimple_call_arg (last
.stmt
, len_arg_no
);
1743 if (tree_fits_uhwi_p (len
))
1745 if (!tree_fits_uhwi_p (last
.len
)
1746 || integer_zerop (len
)
1747 || tree_to_uhwi (len
) != tree_to_uhwi (last
.len
) + 1)
1749 /* Don't adjust the length if it is divisible by 4, it is more efficient
1750 to store the extra '\0' in that case. */
1751 if ((tree_to_uhwi (len
) & 3) == 0)
1754 /* Don't fold away an out of bounds access, as this defeats proper
1756 tree dst
= gimple_call_arg (last
.stmt
, 0);
1759 tree size
= compute_objsize (dst
, 1, &aref
, &ptr_qry
);
1760 if (size
&& tree_int_cst_lt (size
, len
))
1763 else if (TREE_CODE (len
) == SSA_NAME
)
1765 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1766 if (!is_gimple_assign (def_stmt
)
1767 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1768 || gimple_assign_rhs1 (def_stmt
) != last
.len
1769 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1775 gimple_call_set_arg (last
.stmt
, len_arg_no
, last
.len
);
1776 update_stmt (last
.stmt
);
1779 /* For an LHS that is an SSA_NAME that is the result of a strlen()
1780 call, or when BOUND is non-null, of a strnlen() call, set LHS
1781 range info to [0, min (MAX, BOUND)] when the range includes more
1782 than one value and return LHS. Otherwise, when the range
1783 [MIN, MAX] is such that MIN == MAX, return the tree representation
1784 of (MIN). The latter allows callers to fold suitable strnlen() calls
1788 set_strlen_range (tree lhs
, wide_int min
, wide_int max
,
1789 tree bound
/* = NULL_TREE */)
1791 if (TREE_CODE (lhs
) != SSA_NAME
1792 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
1797 /* For strnlen, adjust MIN and MAX as necessary. If the bound
1798 is less than the size of the array set MAX to it. It it's
1799 greater than MAX and MAX is non-zero bump MAX down to account
1800 for the necessary terminating nul. Otherwise leave it alone. */
1801 if (TREE_CODE (bound
) == INTEGER_CST
)
1803 wide_int wibnd
= wi::to_wide (bound
);
1804 int cmp
= wi::cmpu (wibnd
, max
);
1807 else if (cmp
&& wi::ne_p (max
, min
))
1810 else if (TREE_CODE (bound
) == SSA_NAME
)
1812 wide_int minbound
, maxbound
;
1813 // FIXME: Use range_query instead of global ranges.
1814 value_range_kind rng
= get_range_info (bound
, &minbound
, &maxbound
);
1815 if (rng
== VR_RANGE
)
1817 /* For a bound in a known range, adjust the range determined
1818 above as necessary. For a bound in some anti-range or
1819 in an unknown range, use the range determined by callers. */
1820 if (wi::ltu_p (minbound
, min
))
1822 if (wi::ltu_p (maxbound
, max
))
1829 return wide_int_to_tree (size_type_node
, min
);
1831 set_range_info (lhs
, VR_RANGE
, min
, max
);
1835 /* For an LHS that is an SSA_NAME and for strlen() or strnlen() argument
1836 SRC, set LHS range info to [0, min (N, BOUND)] if SRC refers to
1837 a character array A[N] with unknown length bounded by N, and for
1838 strnlen(), by min (N, BOUND). */
1841 maybe_set_strlen_range (tree lhs
, tree src
, tree bound
)
1843 if (TREE_CODE (lhs
) != SSA_NAME
1844 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
1847 if (TREE_CODE (src
) == SSA_NAME
)
1849 gimple
*def
= SSA_NAME_DEF_STMT (src
);
1850 if (is_gimple_assign (def
)
1851 && gimple_assign_rhs_code (def
) == ADDR_EXPR
)
1852 src
= gimple_assign_rhs1 (def
);
1855 /* The longest string is PTRDIFF_MAX - 1 bytes including the final
1856 NUL so that the difference between a pointer to just past it and
1857 one to its beginning is positive. */
1858 wide_int max
= wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node
)) - 2;
1860 if (TREE_CODE (src
) == ADDR_EXPR
)
1862 /* The last array member of a struct can be bigger than its size
1863 suggests if it's treated as a poor-man's flexible array member. */
1864 src
= TREE_OPERAND (src
, 0);
1865 if (TREE_CODE (src
) != MEM_REF
1866 && !array_at_struct_end_p (src
))
1868 tree type
= TREE_TYPE (src
);
1869 tree size
= TYPE_SIZE_UNIT (type
);
1871 && TREE_CODE (size
) == INTEGER_CST
1872 && !integer_zerop (size
))
1874 /* Even though such uses of strlen would be undefined,
1875 avoid relying on arrays of arrays in case some genius
1876 decides to call strlen on an unterminated array element
1877 that's followed by a terminated one. Likewise, avoid
1878 assuming that a struct array member is necessarily
1879 nul-terminated (the nul may be in the member that
1880 follows). In those cases, assume that the length
1881 of the string stored in such an array is bounded
1882 by the size of the enclosing object if one can be
1884 tree base
= get_base_address (src
);
1887 if (tree size
= DECL_SIZE_UNIT (base
))
1889 && TREE_CODE (size
) == INTEGER_CST
1890 && TREE_CODE (TREE_TYPE (base
)) != POINTER_TYPE
)
1891 max
= wi::to_wide (size
);
1895 /* For strlen() the upper bound above is equal to
1896 the longest string that can be stored in the array
1897 (i.e., it accounts for the terminating nul. For
1898 strnlen() bump up the maximum by one since the array
1899 need not be nul-terminated. */
1900 if (!bound
&& max
!= 0)
1905 wide_int min
= wi::zero (max
.get_precision ());
1906 return set_strlen_range (lhs
, min
, max
, bound
);
1909 /* Diagnose buffer overflow by a STMT writing LEN + PLUS_ONE bytes,
1910 either into a region allocated for the object SI when non-null,
1911 or into an object designated by the LHS of STMT otherwise.
1912 When nonnull uses RVALS to determine range information.
1913 RAWMEM may be set by memcpy and other raw memory functions
1914 to allow accesses across subobject boundaries. */
1917 maybe_warn_overflow (gimple
*stmt
, tree len
, pointer_query
&ptr_qry
,
1918 strinfo
*si
= NULL
, bool plus_one
= false,
1919 bool rawmem
= false)
1921 if (!len
|| gimple_no_warning_p (stmt
))
1924 /* The DECL of the function performing the write if it is done
1926 tree writefn
= NULL_TREE
;
1927 /* The destination expression involved in the store STMT. */
1928 tree dest
= NULL_TREE
;
1930 if (is_gimple_assign (stmt
))
1931 dest
= gimple_assign_lhs (stmt
);
1932 else if (is_gimple_call (stmt
))
1934 dest
= gimple_call_arg (stmt
, 0);
1935 writefn
= gimple_call_fndecl (stmt
);
1940 if (TREE_NO_WARNING (dest
))
1943 const int ostype
= rawmem
? 0 : 1;
1945 /* Use maximum precision to avoid overflow in the addition below.
1946 Make sure all operands have the same precision to keep wide_int
1950 /* The size of the destination region (which is smaller than
1951 the destination object for stores at a non-zero offset). */
1952 tree destsize
= compute_objsize (dest
, ostype
, &aref
, &ptr_qry
);
1957 aref
.sizrng
[1] = wi::to_offset (max_object_size ());
1960 /* Return early if the DESTSIZE size expression is the same as LEN
1961 and the offset into the destination is zero. This might happen
1962 in the case of a pair of malloc and memset calls to allocate
1963 an object and clear it as if by calloc. */
1964 if (destsize
== len
&& !plus_one
1965 && aref
.offrng
[0] == 0 && aref
.offrng
[0] == aref
.offrng
[1])
1969 if (!get_range (len
, stmt
, rng
, ptr_qry
.rvals
))
1972 widest_int lenrng
[2] =
1973 { widest_int::from (rng
[0], SIGNED
), widest_int::from (rng
[1], SIGNED
) };
1981 /* The size of the remaining space in the destination computed
1982 as the size of the latter minus the offset into it. */
1983 widest_int spcrng
[2];
1985 offset_int remrng
[2];
1986 remrng
[1] = aref
.size_remaining (remrng
);
1987 spcrng
[0] = remrng
[0] == -1 ? 0 : widest_int::from (remrng
[0], UNSIGNED
);
1988 spcrng
[1] = widest_int::from (remrng
[1], UNSIGNED
);
1991 if (wi::leu_p (lenrng
[0], spcrng
[0])
1992 && wi::leu_p (lenrng
[1], spcrng
[1]))
1995 if (lenrng
[0] == spcrng
[1]
1997 || !si
|| !is_strlen_related_p (si
->ptr
, len
)))
2000 location_t loc
= gimple_or_expr_nonartificial_location (stmt
, dest
);
2001 bool warned
= false;
2002 if (wi::leu_p (lenrng
[0], spcrng
[1]))
2005 && (!si
|| !is_strlen_related_p (si
->ptr
, len
)))
2009 ? warning_at (loc
, OPT_Wstringop_overflow_
,
2010 "%G%qD writing one too many bytes into a region "
2011 "of a size that depends on %<strlen%>",
2013 : warning_at (loc
, OPT_Wstringop_overflow_
,
2014 "%Gwriting one too many bytes into a region "
2015 "of a size that depends on %<strlen%>",
2018 else if (lenrng
[0] == lenrng
[1])
2020 if (spcrng
[0] == spcrng
[1])
2022 ? warning_n (loc
, OPT_Wstringop_overflow_
,
2023 lenrng
[0].to_uhwi (),
2024 "%G%qD writing %wu byte into a region "
2026 "%G%qD writing %wu bytes into a region "
2028 stmt
, writefn
, lenrng
[0].to_uhwi (),
2029 spcrng
[0].to_uhwi ())
2030 : warning_n (loc
, OPT_Wstringop_overflow_
,
2031 lenrng
[0].to_uhwi (),
2032 "%Gwriting %wu byte into a region "
2034 "%Gwriting %wu bytes into a region "
2036 stmt
, lenrng
[0].to_uhwi (),
2037 spcrng
[0].to_uhwi ()));
2040 ? warning_n (loc
, OPT_Wstringop_overflow_
,
2041 lenrng
[0].to_uhwi (),
2042 "%G%qD writing %wu byte into a region "
2043 "of size between %wu and %wu",
2044 "%G%qD writing %wu bytes into a region "
2045 "of size between %wu and %wu",
2046 stmt
, writefn
, lenrng
[0].to_uhwi (),
2047 spcrng
[0].to_uhwi (), spcrng
[1].to_uhwi ())
2048 : warning_n (loc
, OPT_Wstringop_overflow_
,
2049 lenrng
[0].to_uhwi (),
2050 "%Gwriting %wu byte into a region "
2051 "of size between %wu and %wu",
2052 "%Gwriting %wu bytes into a region "
2053 "of size between %wu and %wu",
2054 stmt
, lenrng
[0].to_uhwi (),
2055 spcrng
[0].to_uhwi (), spcrng
[1].to_uhwi ()));
2057 else if (spcrng
[0] == spcrng
[1])
2059 ? warning_at (loc
, OPT_Wstringop_overflow_
,
2060 "%G%qD writing between %wu and %wu bytes "
2061 "into a region of size %wu",
2062 stmt
, writefn
, lenrng
[0].to_uhwi (),
2063 lenrng
[1].to_uhwi (),
2064 spcrng
[0].to_uhwi ())
2065 : warning_at (loc
, OPT_Wstringop_overflow_
,
2066 "%Gwriting between %wu and %wu bytes "
2067 "into a region of size %wu",
2068 stmt
, lenrng
[0].to_uhwi (),
2069 lenrng
[1].to_uhwi (),
2070 spcrng
[0].to_uhwi ()));
2073 ? warning_at (loc
, OPT_Wstringop_overflow_
,
2074 "%G%qD writing between %wu and %wu bytes "
2075 "into a region of size between %wu and %wu",
2076 stmt
, writefn
, lenrng
[0].to_uhwi (),
2077 lenrng
[1].to_uhwi (),
2078 spcrng
[0].to_uhwi (), spcrng
[1].to_uhwi ())
2079 : warning_at (loc
, OPT_Wstringop_overflow_
,
2080 "%Gwriting between %wu and %wu bytes "
2081 "into a region of size between %wu and %wu",
2082 stmt
, lenrng
[0].to_uhwi (),
2083 lenrng
[1].to_uhwi (),
2084 spcrng
[0].to_uhwi (), spcrng
[1].to_uhwi ()));
2089 gimple_set_no_warning (stmt
, true);
2091 aref
.inform_access (access_write_only
);
2094 /* Convenience wrapper for the above. */
2097 maybe_warn_overflow (gimple
*stmt
, unsigned HOST_WIDE_INT len
,
2098 pointer_query
&ptr_qry
, strinfo
*si
= NULL
,
2099 bool plus_one
= false, bool rawmem
= false)
2101 maybe_warn_overflow (stmt
, build_int_cst (size_type_node
, len
), ptr_qry
,
2102 si
, plus_one
, rawmem
);
2105 /* Handle a strlen call. If strlen of the argument is known, replace
2106 the strlen call with the known value, otherwise remember that strlen
2107 of the argument is stored in the lhs SSA_NAME. */
2110 handle_builtin_strlen (gimple_stmt_iterator
*gsi
)
2112 gimple
*stmt
= gsi_stmt (*gsi
);
2113 tree lhs
= gimple_call_lhs (stmt
);
2115 if (lhs
== NULL_TREE
)
2118 location_t loc
= gimple_location (stmt
);
2119 tree callee
= gimple_call_fndecl (stmt
);
2120 tree src
= gimple_call_arg (stmt
, 0);
2121 tree bound
= (DECL_FUNCTION_CODE (callee
) == BUILT_IN_STRNLEN
2122 ? gimple_call_arg (stmt
, 1) : NULL_TREE
);
2123 int idx
= get_stridx (src
);
2124 if (idx
|| (bound
&& integer_zerop (bound
)))
2130 rhs
= build_int_cst (TREE_TYPE (lhs
), ~idx
);
2136 si
= get_strinfo (idx
);
2139 rhs
= get_string_length (si
);
2140 /* For strnlen, if bound is constant, even if si is not known
2141 to be zero terminated, if we know at least bound bytes are
2142 not zero, the return value will be bound. */
2143 if (rhs
== NULL_TREE
2144 && bound
!= NULL_TREE
2145 && TREE_CODE (bound
) == INTEGER_CST
2146 && si
->nonzero_chars
!= NULL_TREE
2147 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
2148 && tree_int_cst_le (bound
, si
->nonzero_chars
))
2152 if (rhs
!= NULL_TREE
)
2154 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2156 fprintf (dump_file
, "Optimizing: ");
2157 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2159 rhs
= unshare_expr (rhs
);
2160 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
2161 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
2164 rhs
= fold_build2_loc (loc
, MIN_EXPR
, TREE_TYPE (rhs
), rhs
, bound
);
2166 if (!update_call_from_tree (gsi
, rhs
))
2167 gimplify_and_update_call_from_tree (gsi
, rhs
);
2168 stmt
= gsi_stmt (*gsi
);
2170 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2172 fprintf (dump_file
, "into: ");
2173 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2177 /* Don't update anything for strnlen. */
2178 && bound
== NULL_TREE
2179 && TREE_CODE (si
->nonzero_chars
) != SSA_NAME
2180 && TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
2181 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
2183 si
= unshare_strinfo (si
);
2184 si
->nonzero_chars
= lhs
;
2185 gcc_assert (si
->full_string_p
);
2188 if (strlen_to_stridx
2189 && (bound
== NULL_TREE
2190 /* For strnlen record this only if the call is proven
2191 to return the same value as strlen would. */
2192 || (TREE_CODE (bound
) == INTEGER_CST
2193 && TREE_CODE (rhs
) == INTEGER_CST
2194 && tree_int_cst_lt (rhs
, bound
))))
2195 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
2200 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
2204 idx
= new_stridx (src
);
2207 strinfo
*si
= get_strinfo (idx
);
2210 if (!si
->full_string_p
&& !si
->stmt
)
2212 /* Until now we only had a lower bound on the string length.
2213 Install LHS as the actual length. */
2214 si
= unshare_strinfo (si
);
2215 tree old
= si
->nonzero_chars
;
2216 si
->nonzero_chars
= lhs
;
2217 si
->full_string_p
= true;
2218 if (old
&& TREE_CODE (old
) == INTEGER_CST
)
2220 old
= fold_convert_loc (loc
, TREE_TYPE (lhs
), old
);
2221 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
,
2222 TREE_TYPE (lhs
), lhs
, old
);
2223 adjust_related_strinfos (loc
, si
, adj
);
2224 /* Use the constant minimum length as the lower bound
2225 of the non-constant length. */
2226 wide_int min
= wi::to_wide (old
);
2228 = wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node
)) - 2;
2229 set_strlen_range (lhs
, min
, max
);
2245 /* Only store the new length information for calls to strlen(),
2246 not for those to strnlen(). */
2247 strinfo
*si
= new_strinfo (src
, idx
, lhs
, true);
2248 set_strinfo (idx
, si
);
2249 find_equal_ptrs (src
, idx
);
2252 /* For SRC that is an array of N elements, set LHS's range
2253 to [0, min (N, BOUND)]. A constant return value means
2254 the range would have consisted of a single value. In
2255 that case, fold the result into the returned constant. */
2256 if (tree ret
= maybe_set_strlen_range (lhs
, src
, bound
))
2257 if (TREE_CODE (ret
) == INTEGER_CST
)
2259 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2261 fprintf (dump_file
, "Optimizing: ");
2262 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2264 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (ret
)))
2265 ret
= fold_convert_loc (loc
, TREE_TYPE (lhs
), ret
);
2266 if (!update_call_from_tree (gsi
, ret
))
2267 gimplify_and_update_call_from_tree (gsi
, ret
);
2268 stmt
= gsi_stmt (*gsi
);
2270 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2272 fprintf (dump_file
, "into: ");
2273 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2277 if (strlen_to_stridx
&& !bound
)
2278 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
2282 /* Handle a strchr call. If strlen of the first argument is known, replace
2283 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
2284 that lhs of the call is endptr and strlen of the argument is endptr - x. */
2287 handle_builtin_strchr (gimple_stmt_iterator
*gsi
)
2289 gimple
*stmt
= gsi_stmt (*gsi
);
2290 tree lhs
= gimple_call_lhs (stmt
);
2292 if (lhs
== NULL_TREE
)
2295 if (!integer_zerop (gimple_call_arg (stmt
, 1)))
2298 tree src
= gimple_call_arg (stmt
, 0);
2300 /* Avoid folding if the first argument is not a nul-terminated array.
2301 Defer warning until later. */
2302 if (!check_nul_terminated_array (NULL_TREE
, src
))
2305 int idx
= get_stridx (src
);
2312 rhs
= build_int_cst (size_type_node
, ~idx
);
2316 si
= get_strinfo (idx
);
2318 rhs
= get_string_length (si
);
2320 if (rhs
!= NULL_TREE
)
2322 location_t loc
= gimple_location (stmt
);
2324 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2326 fprintf (dump_file
, "Optimizing: ");
2327 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2329 if (si
!= NULL
&& si
->endptr
!= NULL_TREE
)
2331 rhs
= unshare_expr (si
->endptr
);
2332 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
2334 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
2338 rhs
= fold_convert_loc (loc
, sizetype
, unshare_expr (rhs
));
2339 rhs
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
2340 TREE_TYPE (src
), src
, rhs
);
2341 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
2343 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
2345 if (!update_call_from_tree (gsi
, rhs
))
2346 gimplify_and_update_call_from_tree (gsi
, rhs
);
2347 stmt
= gsi_stmt (*gsi
);
2349 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2351 fprintf (dump_file
, "into: ");
2352 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2355 && si
->endptr
== NULL_TREE
2356 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
2358 si
= unshare_strinfo (si
);
2361 zero_length_string (lhs
, si
);
2365 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
2367 if (TREE_CODE (src
) != SSA_NAME
|| !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src
))
2370 idx
= new_stridx (src
);
2371 else if (get_strinfo (idx
) != NULL
)
2373 zero_length_string (lhs
, NULL
);
2378 location_t loc
= gimple_location (stmt
);
2379 tree lhsu
= fold_convert_loc (loc
, size_type_node
, lhs
);
2380 tree srcu
= fold_convert_loc (loc
, size_type_node
, src
);
2381 tree length
= fold_build2_loc (loc
, MINUS_EXPR
,
2382 size_type_node
, lhsu
, srcu
);
2383 strinfo
*si
= new_strinfo (src
, idx
, length
, true);
2385 set_strinfo (idx
, si
);
2386 find_equal_ptrs (src
, idx
);
2387 zero_length_string (lhs
, si
);
2391 zero_length_string (lhs
, NULL
);
2394 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
2395 If strlen of the second argument is known, strlen of the first argument
2396 is the same after this call. Furthermore, attempt to convert it to
2397 memcpy. Uses RVALS to determine range information. */
2400 handle_builtin_strcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
,
2401 pointer_query
&ptr_qry
)
2404 tree src
, dst
, srclen
, len
, lhs
, type
, fn
, oldlen
;
2406 gimple
*stmt
= gsi_stmt (*gsi
);
2407 strinfo
*si
, *dsi
, *olddsi
, *zsi
;
2410 src
= gimple_call_arg (stmt
, 1);
2411 dst
= gimple_call_arg (stmt
, 0);
2412 lhs
= gimple_call_lhs (stmt
);
2413 idx
= get_stridx (src
);
2416 si
= get_strinfo (idx
);
2418 didx
= get_stridx (dst
);
2422 olddsi
= get_strinfo (didx
);
2427 adjust_last_stmt (olddsi
, stmt
, false, ptr_qry
);
2431 srclen
= get_string_length (si
);
2433 srclen
= build_int_cst (size_type_node
, ~idx
);
2435 maybe_warn_overflow (stmt
, srclen
, ptr_qry
, olddsi
, true);
2438 adjust_last_stmt (olddsi
, stmt
, false, ptr_qry
);
2440 loc
= gimple_location (stmt
);
2441 if (srclen
== NULL_TREE
)
2444 case BUILT_IN_STRCPY
:
2445 case BUILT_IN_STRCPY_CHK
:
2446 if (lhs
!= NULL_TREE
|| !builtin_decl_implicit_p (BUILT_IN_STPCPY
))
2449 case BUILT_IN_STPCPY
:
2450 case BUILT_IN_STPCPY_CHK
:
2451 if (lhs
== NULL_TREE
)
2455 tree lhsuint
= fold_convert_loc (loc
, size_type_node
, lhs
);
2456 srclen
= fold_convert_loc (loc
, size_type_node
, dst
);
2457 srclen
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
2467 didx
= new_stridx (dst
);
2473 oldlen
= olddsi
->nonzero_chars
;
2474 dsi
= unshare_strinfo (olddsi
);
2475 dsi
->nonzero_chars
= srclen
;
2476 dsi
->full_string_p
= (srclen
!= NULL_TREE
);
2477 /* Break the chain, so adjust_related_strinfo on later pointers in
2478 the chain won't adjust this one anymore. */
2481 dsi
->endptr
= NULL_TREE
;
2485 dsi
= new_strinfo (dst
, didx
, srclen
, srclen
!= NULL_TREE
);
2486 set_strinfo (didx
, dsi
);
2487 find_equal_ptrs (dst
, didx
);
2489 dsi
->writable
= true;
2490 dsi
->dont_invalidate
= true;
2492 if (dsi
->nonzero_chars
== NULL_TREE
)
2496 /* If string length of src is unknown, use delayed length
2497 computation. If string length of dst will be needed, it
2498 can be computed by transforming this strcpy call into
2499 stpcpy and subtracting dst from the return value. */
2501 /* Look for earlier strings whose length could be determined if
2502 this strcpy is turned into an stpcpy. */
2504 if (dsi
->prev
!= 0 && (chainsi
= verify_related_strinfos (dsi
)) != NULL
)
2506 for (; chainsi
&& chainsi
!= dsi
; chainsi
= get_strinfo (chainsi
->next
))
2508 /* When setting a stmt for delayed length computation
2509 prevent all strinfos through dsi from being
2511 chainsi
= unshare_strinfo (chainsi
);
2512 chainsi
->stmt
= stmt
;
2513 chainsi
->nonzero_chars
= NULL_TREE
;
2514 chainsi
->full_string_p
= false;
2515 chainsi
->endptr
= NULL_TREE
;
2516 chainsi
->dont_invalidate
= true;
2521 /* Try to detect overlap before returning. This catches cases
2522 like strcpy (d, d + n) where n is non-constant whose range
2523 is such that (n <= strlen (d) holds).
2525 OLDDSI->NONZERO_chars may have been reset by this point with
2526 oldlen holding it original value. */
2527 if (olddsi
&& oldlen
)
2529 /* Add 1 for the terminating NUL. */
2530 tree type
= TREE_TYPE (oldlen
);
2531 oldlen
= fold_build2 (PLUS_EXPR
, type
, oldlen
,
2532 build_int_cst (type
, 1));
2533 check_bounds_or_overlap (stmt
, olddsi
->ptr
, src
, oldlen
, NULL_TREE
);
2541 tree adj
= NULL_TREE
;
2542 if (oldlen
== NULL_TREE
)
2544 else if (integer_zerop (oldlen
))
2546 else if (TREE_CODE (oldlen
) == INTEGER_CST
2547 || TREE_CODE (srclen
) == INTEGER_CST
)
2548 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
2549 TREE_TYPE (srclen
), srclen
,
2550 fold_convert_loc (loc
, TREE_TYPE (srclen
),
2552 if (adj
!= NULL_TREE
)
2553 adjust_related_strinfos (loc
, dsi
, adj
);
2557 /* strcpy src may not overlap dst, so src doesn't need to be
2558 invalidated either. */
2560 si
->dont_invalidate
= true;
2566 case BUILT_IN_STRCPY
:
2567 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
2569 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
2571 case BUILT_IN_STRCPY_CHK
:
2572 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
2574 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
2576 case BUILT_IN_STPCPY
:
2577 /* This would need adjustment of the lhs (subtract one),
2578 or detection that the trailing '\0' doesn't need to be
2579 written, if it will be immediately overwritten.
2580 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
2584 zsi
= zero_length_string (lhs
, dsi
);
2587 case BUILT_IN_STPCPY_CHK
:
2588 /* This would need adjustment of the lhs (subtract one),
2589 or detection that the trailing '\0' doesn't need to be
2590 written, if it will be immediately overwritten.
2591 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
2595 zsi
= zero_length_string (lhs
, dsi
);
2602 zsi
->dont_invalidate
= true;
2606 tree args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
2607 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
2610 type
= size_type_node
;
2612 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
2613 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
, build_int_cst (type
, 1));
2615 /* Set the no-warning bit on the transformed statement? */
2616 bool set_no_warning
= false;
2618 if (const strinfo
*chksi
= olddsi
? olddsi
: dsi
)
2620 && check_bounds_or_overlap (stmt
, chksi
->ptr
, si
->ptr
, NULL_TREE
, len
))
2622 gimple_set_no_warning (stmt
, true);
2623 set_no_warning
= true;
2626 if (fn
== NULL_TREE
)
2629 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
2631 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2633 fprintf (dump_file
, "Optimizing: ");
2634 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2636 if (gimple_call_num_args (stmt
) == 2)
2637 success
= update_gimple_call (gsi
, fn
, 3, dst
, src
, len
);
2639 success
= update_gimple_call (gsi
, fn
, 4, dst
, src
, len
,
2640 gimple_call_arg (stmt
, 2));
2643 stmt
= gsi_stmt (*gsi
);
2645 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2647 fprintf (dump_file
, "into: ");
2648 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2650 /* Allow adjust_last_stmt to decrease this memcpy's size. */
2651 laststmt
.stmt
= stmt
;
2652 laststmt
.len
= srclen
;
2653 laststmt
.stridx
= dsi
->idx
;
2655 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2656 fprintf (dump_file
, "not possible.\n");
2659 gimple_set_no_warning (stmt
, true);
2662 /* Check the size argument to the built-in forms of stpncpy and strncpy
2663 for out-of-bounds offsets or overlapping access, and to see if the
2664 size argument is derived from a call to strlen() on the source argument,
2665 and if so, issue an appropriate warning. */
2668 handle_builtin_strncat (built_in_function
, gimple_stmt_iterator
*gsi
)
2670 /* Same as stxncpy(). */
2671 handle_builtin_stxncpy_strncat (true, gsi
);
2674 /* Return true if LEN depends on a call to strlen(SRC) in an interesting
2675 way. LEN can either be an integer expression, or a pointer (to char).
2676 When it is the latter (such as in recursive calls to self) it is
2677 assumed to be the argument in some call to strlen() whose relationship
2678 to SRC is being ascertained. */
2681 is_strlen_related_p (tree src
, tree len
)
2683 if (TREE_CODE (TREE_TYPE (len
)) == POINTER_TYPE
2684 && operand_equal_p (src
, len
, 0))
2687 if (TREE_CODE (len
) != SSA_NAME
)
2690 if (TREE_CODE (src
) == SSA_NAME
)
2692 gimple
*srcdef
= SSA_NAME_DEF_STMT (src
);
2693 if (is_gimple_assign (srcdef
))
2695 /* Handle bitwise AND used in conversions from wider size_t
2696 to narrower unsigned types. */
2697 tree_code code
= gimple_assign_rhs_code (srcdef
);
2698 if (code
== BIT_AND_EXPR
2699 || code
== NOP_EXPR
)
2700 return is_strlen_related_p (gimple_assign_rhs1 (srcdef
), len
);
2705 if (gimple_call_builtin_p (srcdef
, BUILT_IN_NORMAL
))
2707 /* If SRC is the result of a call to an allocation function
2708 or strlen, use the function's argument instead. */
2709 tree func
= gimple_call_fndecl (srcdef
);
2710 built_in_function code
= DECL_FUNCTION_CODE (func
);
2711 if (code
== BUILT_IN_ALLOCA
2712 || code
== BUILT_IN_ALLOCA_WITH_ALIGN
2713 || code
== BUILT_IN_MALLOC
2714 || code
== BUILT_IN_STRLEN
)
2715 return is_strlen_related_p (gimple_call_arg (srcdef
, 0), len
);
2717 /* FIXME: Handle other functions with attribute alloc_size. */
2722 gimple
*lendef
= SSA_NAME_DEF_STMT (len
);
2726 if (is_gimple_call (lendef
))
2728 tree func
= gimple_call_fndecl (lendef
);
2729 if (!valid_builtin_call (lendef
)
2730 || DECL_FUNCTION_CODE (func
) != BUILT_IN_STRLEN
)
2733 tree arg
= gimple_call_arg (lendef
, 0);
2734 return is_strlen_related_p (src
, arg
);
2737 if (!is_gimple_assign (lendef
))
2740 tree_code code
= gimple_assign_rhs_code (lendef
);
2741 tree rhs1
= gimple_assign_rhs1 (lendef
);
2742 tree rhstype
= TREE_TYPE (rhs1
);
2744 if ((TREE_CODE (rhstype
) == POINTER_TYPE
&& code
== POINTER_PLUS_EXPR
)
2745 || (INTEGRAL_TYPE_P (rhstype
)
2746 && (code
== BIT_AND_EXPR
2747 || code
== NOP_EXPR
)))
2749 /* Pointer plus (an integer), and truncation are considered among
2750 the (potentially) related expressions to strlen. */
2751 return is_strlen_related_p (src
, rhs1
);
2754 if (tree rhs2
= gimple_assign_rhs2 (lendef
))
2756 /* Integer subtraction is considered strlen-related when both
2757 arguments are integers and second one is strlen-related. */
2758 rhstype
= TREE_TYPE (rhs2
);
2759 if (INTEGRAL_TYPE_P (rhstype
) && code
== MINUS_EXPR
)
2760 return is_strlen_related_p (src
, rhs2
);
2766 /* Called by handle_builtin_stxncpy_strncat and by
2767 gimple_fold_builtin_strncpy in gimple-fold.c.
2768 Check to see if the specified bound is a) equal to the size of
2769 the destination DST and if so, b) if it's immediately followed by
2770 DST[CNT - 1] = '\0'. If a) holds and b) does not, warn. Otherwise,
2771 do nothing. Return true if diagnostic has been issued.
2773 The purpose is to diagnose calls to strncpy and stpncpy that do
2774 not nul-terminate the copy while allowing for the idiom where
2775 such a call is immediately followed by setting the last element
2778 strncpy (a, s, sizeof a);
2779 a[sizeof a - 1] = '\0';
2783 maybe_diag_stxncpy_trunc (gimple_stmt_iterator gsi
, tree src
, tree cnt
,
2784 pointer_query
*ptr_qry
/* = NULL */)
2786 gimple
*stmt
= gsi_stmt (gsi
);
2787 if (gimple_no_warning_p (stmt
))
2790 wide_int cntrange
[2];
2792 // FIXME: Use range_query instead of global ranges.
2793 enum value_range_kind rng
= get_range_info (cnt
, cntrange
, cntrange
+ 1);
2794 if (rng
== VR_RANGE
)
2796 else if (rng
== VR_ANTI_RANGE
)
2798 wide_int maxobjsize
= wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node
));
2800 if (wi::ltu_p (cntrange
[1], maxobjsize
))
2802 cntrange
[0] = cntrange
[1] + 1;
2803 cntrange
[1] = maxobjsize
;
2807 cntrange
[1] = cntrange
[0] - 1;
2808 cntrange
[0] = wi::zero (TYPE_PRECISION (TREE_TYPE (cnt
)));
2814 /* Negative value is the constant string length. If it's less than
2815 the lower bound there is no truncation. Avoid calling get_stridx()
2816 when ssa_ver_to_stridx is empty. That implies the caller isn't
2817 running under the control of this pass and ssa_ver_to_stridx hasn't
2818 been created yet. */
2819 int sidx
= ssa_ver_to_stridx
.length () ? get_stridx (src
) : 0;
2820 if (sidx
< 0 && wi::gtu_p (cntrange
[0], ~sidx
))
2823 tree dst
= gimple_call_arg (stmt
, 0);
2825 if (TREE_CODE (dstdecl
) == ADDR_EXPR
)
2826 dstdecl
= TREE_OPERAND (dstdecl
, 0);
2828 tree ref
= NULL_TREE
;
2832 /* If the source is a non-string return early to avoid warning
2833 for possible truncation (if the truncation is certain SIDX
2835 tree srcdecl
= gimple_call_arg (stmt
, 1);
2836 if (TREE_CODE (srcdecl
) == ADDR_EXPR
)
2837 srcdecl
= TREE_OPERAND (srcdecl
, 0);
2838 if (get_attr_nonstring_decl (srcdecl
, &ref
))
2842 /* Likewise, if the destination refers to an array/pointer declared
2843 nonstring return early. */
2844 if (get_attr_nonstring_decl (dstdecl
, &ref
))
2847 /* Look for dst[i] = '\0'; after the stxncpy() call and if found
2848 avoid the truncation warning. */
2849 gsi_next_nondebug (&gsi
);
2850 gimple
*next_stmt
= gsi_stmt (gsi
);
2853 /* When there is no statement in the same basic block check
2854 the immediate successor block. */
2855 if (basic_block bb
= gimple_bb (stmt
))
2857 if (single_succ_p (bb
))
2859 /* For simplicity, ignore blocks with multiple outgoing
2860 edges for now and only consider successor blocks along
2862 edge e
= EDGE_SUCC (bb
, 0);
2863 if (!(e
->flags
& EDGE_ABNORMAL
))
2865 gsi
= gsi_start_bb (e
->dest
);
2866 next_stmt
= gsi_stmt (gsi
);
2867 if (next_stmt
&& is_gimple_debug (next_stmt
))
2869 gsi_next_nondebug (&gsi
);
2870 next_stmt
= gsi_stmt (gsi
);
2877 if (next_stmt
&& is_gimple_assign (next_stmt
))
2879 tree lhs
= gimple_assign_lhs (next_stmt
);
2880 tree_code code
= TREE_CODE (lhs
);
2881 if (code
== ARRAY_REF
|| code
== MEM_REF
)
2882 lhs
= TREE_OPERAND (lhs
, 0);
2884 tree func
= gimple_call_fndecl (stmt
);
2885 if (DECL_FUNCTION_CODE (func
) == BUILT_IN_STPNCPY
)
2887 tree ret
= gimple_call_lhs (stmt
);
2888 if (ret
&& operand_equal_p (ret
, lhs
, 0))
2892 /* Determine the base address and offset of the reference,
2893 ignoring the innermost array index. */
2894 if (TREE_CODE (ref
) == ARRAY_REF
)
2895 ref
= TREE_OPERAND (ref
, 0);
2898 tree dstbase
= get_addr_base_and_unit_offset (ref
, &dstoff
);
2901 tree lhsbase
= get_addr_base_and_unit_offset (lhs
, &lhsoff
);
2904 && known_eq (dstoff
, lhsoff
)
2905 && operand_equal_p (dstbase
, lhsbase
, 0))
2909 int prec
= TYPE_PRECISION (TREE_TYPE (cnt
));
2910 wide_int lenrange
[2];
2911 if (strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
)
2913 lenrange
[0] = (sisrc
->nonzero_chars
2914 && TREE_CODE (sisrc
->nonzero_chars
) == INTEGER_CST
2915 ? wi::to_wide (sisrc
->nonzero_chars
)
2917 lenrange
[1] = lenrange
[0];
2920 lenrange
[0] = lenrange
[1] = wi::shwi (~sidx
, prec
);
2923 c_strlen_data lendata
= { };
2924 /* Set MAXBOUND to an arbitrary non-null non-integer node as a request
2925 to have it set to the length of the longest string in a PHI. */
2926 lendata
.maxbound
= src
;
2927 get_range_strlen (src
, &lendata
, /* eltsize = */1);
2928 if (TREE_CODE (lendata
.minlen
) == INTEGER_CST
2929 && TREE_CODE (lendata
.maxbound
) == INTEGER_CST
)
2931 /* When LENDATA.MAXLEN is unknown, reset LENDATA.MINLEN
2932 which stores the length of the shortest known string. */
2933 if (integer_all_onesp (lendata
.maxlen
))
2934 lenrange
[0] = wi::shwi (0, prec
);
2936 lenrange
[0] = wi::to_wide (lendata
.minlen
, prec
);
2937 lenrange
[1] = wi::to_wide (lendata
.maxbound
, prec
);
2941 lenrange
[0] = wi::shwi (0, prec
);
2942 lenrange
[1] = wi::shwi (-1, prec
);
2946 location_t callloc
= gimple_or_expr_nonartificial_location (stmt
, dst
);
2947 tree func
= gimple_call_fndecl (stmt
);
2949 if (lenrange
[0] != 0 || !wi::neg_p (lenrange
[1]))
2951 /* If the longest source string is shorter than the lower bound
2952 of the specified count the copy is definitely nul-terminated. */
2953 if (wi::ltu_p (lenrange
[1], cntrange
[0]))
2956 if (wi::neg_p (lenrange
[1]))
2958 /* The length of one of the strings is unknown but at least
2959 one has non-zero length and that length is stored in
2960 LENRANGE[1]. Swap the bounds to force a "may be truncated"
2962 lenrange
[1] = lenrange
[0];
2963 lenrange
[0] = wi::shwi (0, prec
);
2966 /* Set to true for strncat whose bound is derived from the length
2967 of the destination (the expected usage pattern). */
2968 bool cat_dstlen_bounded
= false;
2969 if (DECL_FUNCTION_CODE (func
) == BUILT_IN_STRNCAT
)
2970 cat_dstlen_bounded
= is_strlen_related_p (dst
, cnt
);
2972 if (lenrange
[0] == cntrange
[1] && cntrange
[0] == cntrange
[1])
2973 return warning_n (callloc
, OPT_Wstringop_truncation
,
2974 cntrange
[0].to_uhwi (),
2975 "%G%qD output truncated before terminating "
2976 "nul copying %E byte from a string of the "
2978 "%G%qD output truncated before terminating nul "
2979 "copying %E bytes from a string of the same "
2982 else if (!cat_dstlen_bounded
)
2984 if (wi::geu_p (lenrange
[0], cntrange
[1]))
2986 /* The shortest string is longer than the upper bound of
2987 the count so the truncation is certain. */
2988 if (cntrange
[0] == cntrange
[1])
2989 return warning_n (callloc
, OPT_Wstringop_truncation
,
2990 cntrange
[0].to_uhwi (),
2991 "%G%qD output truncated copying %E byte "
2992 "from a string of length %wu",
2993 "%G%qD output truncated copying %E bytes "
2994 "from a string of length %wu",
2995 stmt
, func
, cnt
, lenrange
[0].to_uhwi ());
2997 return warning_at (callloc
, OPT_Wstringop_truncation
,
2998 "%G%qD output truncated copying between %wu "
2999 "and %wu bytes from a string of length %wu",
3000 stmt
, func
, cntrange
[0].to_uhwi (),
3001 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
3003 else if (wi::geu_p (lenrange
[1], cntrange
[1]))
3005 /* The longest string is longer than the upper bound of
3006 the count so the truncation is possible. */
3007 if (cntrange
[0] == cntrange
[1])
3008 return warning_n (callloc
, OPT_Wstringop_truncation
,
3009 cntrange
[0].to_uhwi (),
3010 "%G%qD output may be truncated copying %E "
3011 "byte from a string of length %wu",
3012 "%G%qD output may be truncated copying %E "
3013 "bytes from a string of length %wu",
3014 stmt
, func
, cnt
, lenrange
[1].to_uhwi ());
3016 return warning_at (callloc
, OPT_Wstringop_truncation
,
3017 "%G%qD output may be truncated copying between "
3018 "%wu and %wu bytes from a string of length %wu",
3019 stmt
, func
, cntrange
[0].to_uhwi (),
3020 cntrange
[1].to_uhwi (), lenrange
[1].to_uhwi ());
3024 if (!cat_dstlen_bounded
3025 && cntrange
[0] != cntrange
[1]
3026 && wi::leu_p (cntrange
[0], lenrange
[0])
3027 && wi::leu_p (cntrange
[1], lenrange
[0] + 1))
3029 /* If the source (including the terminating nul) is longer than
3030 the lower bound of the specified count but shorter than the
3031 upper bound the copy may (but need not) be truncated. */
3032 return warning_at (callloc
, OPT_Wstringop_truncation
,
3033 "%G%qD output may be truncated copying between "
3034 "%wu and %wu bytes from a string of length %wu",
3035 stmt
, func
, cntrange
[0].to_uhwi (),
3036 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
3041 if (tree dstsize
= compute_objsize (dst
, 1, &aref
, ptr_qry
))
3043 /* The source length is unknown. Try to determine the destination
3044 size and see if it matches the specified bound. If not, bail.
3045 Otherwise go on to see if it should be diagnosed for possible
3050 if (wi::to_wide (dstsize
) != cntrange
[1])
3053 /* Avoid warning for strncpy(a, b, N) calls where the following
3055 N == sizeof a && N == sizeof b */
3056 if (tree srcsize
= compute_objsize (src
, 1, &aref
, ptr_qry
))
3057 if (wi::to_wide (srcsize
) == cntrange
[1])
3060 if (cntrange
[0] == cntrange
[1])
3061 return warning_at (callloc
, OPT_Wstringop_truncation
,
3062 "%G%qD specified bound %E equals destination size",
3069 /* Check the arguments to the built-in forms of stpncpy, strncpy, and
3070 strncat, for out-of-bounds offsets or overlapping access, and to see
3071 if the size is derived from calling strlen() on the source argument,
3072 and if so, issue the appropriate warning.
3073 APPEND_P is true for strncat. */
3076 handle_builtin_stxncpy_strncat (bool append_p
, gimple_stmt_iterator
*gsi
)
3078 if (!strlen_to_stridx
)
3081 gimple
*stmt
= gsi_stmt (*gsi
);
3083 tree dst
= gimple_call_arg (stmt
, 0);
3084 tree src
= gimple_call_arg (stmt
, 1);
3085 tree len
= gimple_call_arg (stmt
, 2);
3086 tree dstsize
= NULL_TREE
, srcsize
= NULL_TREE
;
3088 int didx
= get_stridx (dst
);
3089 if (strinfo
*sidst
= didx
> 0 ? get_strinfo (didx
) : NULL
)
3091 /* Compute the size of the destination string including the nul
3092 if it is known to be nul-terminated. */
3093 if (sidst
->nonzero_chars
)
3095 if (sidst
->full_string_p
)
3097 /* String is known to be nul-terminated. */
3098 tree type
= TREE_TYPE (sidst
->nonzero_chars
);
3099 dstsize
= fold_build2 (PLUS_EXPR
, type
, sidst
->nonzero_chars
,
3100 build_int_cst (type
, 1));
3103 dstsize
= sidst
->nonzero_chars
;
3109 int sidx
= get_stridx (src
);
3110 strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
;
3113 /* strncat() and strncpy() can modify the source string by writing
3114 over the terminating nul so SISRC->DONT_INVALIDATE must be left
3117 /* Compute the size of the source string including the terminating
3118 nul if its known to be nul-terminated. */
3119 if (sisrc
->nonzero_chars
)
3121 if (sisrc
->full_string_p
)
3123 tree type
= TREE_TYPE (sisrc
->nonzero_chars
);
3124 srcsize
= fold_build2 (PLUS_EXPR
, type
, sisrc
->nonzero_chars
,
3125 build_int_cst (type
, 1));
3128 srcsize
= sisrc
->nonzero_chars
;
3134 srcsize
= NULL_TREE
;
3136 if (check_bounds_or_overlap (stmt
, dst
, src
, dstsize
, srcsize
))
3138 gimple_set_no_warning (stmt
, true);
3142 /* If the length argument was computed from strlen(S) for some string
3143 S retrieve the strinfo index for the string (PSS->FIRST) along with
3144 the location of the strlen() call (PSS->SECOND). */
3145 stridx_strlenloc
*pss
= strlen_to_stridx
->get (len
);
3146 if (!pss
|| pss
->first
<= 0)
3148 if (maybe_diag_stxncpy_trunc (*gsi
, src
, len
))
3149 gimple_set_no_warning (stmt
, true);
3154 /* Retrieve the strinfo data for the string S that LEN was computed
3155 from as some function F of strlen (S) (i.e., LEN need not be equal
3157 strinfo
*silen
= get_strinfo (pss
->first
);
3159 location_t callloc
= gimple_or_expr_nonartificial_location (stmt
, dst
);
3161 tree func
= gimple_call_fndecl (stmt
);
3163 bool warned
= false;
3165 /* When -Wstringop-truncation is set, try to determine truncation
3166 before diagnosing possible overflow. Truncation is implied by
3167 the LEN argument being equal to strlen(SRC), regardless of
3168 whether its value is known. Otherwise, issue the more generic
3169 -Wstringop-overflow which triggers for LEN arguments that in
3170 any meaningful way depend on strlen(SRC). */
3173 && is_strlen_related_p (src
, len
)
3174 && warning_at (callloc
, OPT_Wstringop_truncation
,
3175 "%G%qD output truncated before terminating nul "
3176 "copying as many bytes from a string as its length",
3179 else if (silen
&& is_strlen_related_p (src
, silen
->ptr
))
3180 warned
= warning_at (callloc
, OPT_Wstringop_overflow_
,
3181 "%G%qD specified bound depends on the length "
3182 "of the source argument",
3186 location_t strlenloc
= pss
->second
;
3187 if (strlenloc
!= UNKNOWN_LOCATION
&& strlenloc
!= callloc
)
3188 inform (strlenloc
, "length computed here");
3192 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
3193 If strlen of the second argument is known and length of the third argument
3194 is that plus one, strlen of the first argument is the same after this
3195 call. Uses RVALS to determine range information. */
3198 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
,
3199 pointer_query
&ptr_qry
)
3201 tree lhs
, oldlen
, newlen
;
3202 gimple
*stmt
= gsi_stmt (*gsi
);
3205 tree len
= gimple_call_arg (stmt
, 2);
3206 tree src
= gimple_call_arg (stmt
, 1);
3207 tree dst
= gimple_call_arg (stmt
, 0);
3209 int didx
= get_stridx (dst
);
3210 strinfo
*olddsi
= NULL
;
3212 olddsi
= get_strinfo (didx
);
3217 && !integer_zerop (len
))
3219 maybe_warn_overflow (stmt
, len
, ptr_qry
, olddsi
, false, false);
3220 adjust_last_stmt (olddsi
, stmt
, false, ptr_qry
);
3223 int idx
= get_stridx (src
);
3232 /* Handle memcpy (x, y, l) where l's relationship with strlen (y)
3234 si
= get_strinfo (idx
);
3235 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
3237 if (TREE_CODE (len
) == INTEGER_CST
3238 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
3240 if (tree_int_cst_le (len
, si
->nonzero_chars
))
3242 /* Copying LEN nonzero characters, where LEN is constant. */
3244 full_string_p
= false;
3248 /* Copying the whole of the analyzed part of SI. */
3249 newlen
= si
->nonzero_chars
;
3250 full_string_p
= si
->full_string_p
;
3255 if (!si
->full_string_p
)
3257 if (TREE_CODE (len
) != SSA_NAME
)
3259 def_stmt
= SSA_NAME_DEF_STMT (len
);
3260 if (!is_gimple_assign (def_stmt
)
3261 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
3262 || gimple_assign_rhs1 (def_stmt
) != si
->nonzero_chars
3263 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
3265 /* Copying variable-length string SI (and no more). */
3266 newlen
= si
->nonzero_chars
;
3267 full_string_p
= true;
3273 /* Handle memcpy (x, "abcd", 5) or
3274 memcpy (x, "abc\0uvw", 7). */
3275 if (!tree_fits_uhwi_p (len
))
3278 unsigned HOST_WIDE_INT clen
= tree_to_uhwi (len
);
3279 unsigned HOST_WIDE_INT nonzero_chars
= ~idx
;
3280 newlen
= build_int_cst (size_type_node
, MIN (nonzero_chars
, clen
));
3281 full_string_p
= clen
> nonzero_chars
;
3286 && olddsi
->nonzero_chars
3287 && TREE_CODE (olddsi
->nonzero_chars
) == INTEGER_CST
3288 && tree_int_cst_le (newlen
, olddsi
->nonzero_chars
))
3290 /* The SRC substring being written strictly overlaps
3291 a subsequence of the existing string OLDDSI. */
3292 newlen
= olddsi
->nonzero_chars
;
3293 full_string_p
= olddsi
->full_string_p
;
3296 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
3297 adjust_last_stmt (olddsi
, stmt
, false, ptr_qry
);
3301 didx
= new_stridx (dst
);
3308 dsi
= unshare_strinfo (olddsi
);
3309 oldlen
= olddsi
->nonzero_chars
;
3310 dsi
->nonzero_chars
= newlen
;
3311 dsi
->full_string_p
= full_string_p
;
3312 /* Break the chain, so adjust_related_strinfo on later pointers in
3313 the chain won't adjust this one anymore. */
3316 dsi
->endptr
= NULL_TREE
;
3320 dsi
= new_strinfo (dst
, didx
, newlen
, full_string_p
);
3321 set_strinfo (didx
, dsi
);
3322 find_equal_ptrs (dst
, didx
);
3324 dsi
->writable
= true;
3325 dsi
->dont_invalidate
= true;
3328 tree adj
= NULL_TREE
;
3329 location_t loc
= gimple_location (stmt
);
3330 if (oldlen
== NULL_TREE
)
3332 else if (integer_zerop (oldlen
))
3334 else if (TREE_CODE (oldlen
) == INTEGER_CST
3335 || TREE_CODE (newlen
) == INTEGER_CST
)
3336 adj
= fold_build2_loc (loc
, MINUS_EXPR
, TREE_TYPE (newlen
), newlen
,
3337 fold_convert_loc (loc
, TREE_TYPE (newlen
),
3339 if (adj
!= NULL_TREE
)
3340 adjust_related_strinfos (loc
, dsi
, adj
);
3344 /* memcpy src may not overlap dst, so src doesn't need to be
3345 invalidated either. */
3347 si
->dont_invalidate
= true;
3351 lhs
= gimple_call_lhs (stmt
);
3354 case BUILT_IN_MEMCPY
:
3355 case BUILT_IN_MEMCPY_CHK
:
3356 /* Allow adjust_last_stmt to decrease this memcpy's size. */
3357 laststmt
.stmt
= stmt
;
3358 laststmt
.len
= dsi
->nonzero_chars
;
3359 laststmt
.stridx
= dsi
->idx
;
3361 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
3363 case BUILT_IN_MEMPCPY
:
3364 case BUILT_IN_MEMPCPY_CHK
:
3372 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
3373 If strlen of the second argument is known, strlen of the first argument
3374 is increased by the length of the second argument. Furthermore, attempt
3375 to convert it to memcpy/strcpy if the length of the first argument
3379 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
,
3380 pointer_query
&ptr_qry
)
3383 tree srclen
, args
, type
, fn
, objsz
, endptr
;
3385 gimple
*stmt
= gsi_stmt (*gsi
);
3387 location_t loc
= gimple_location (stmt
);
3389 tree src
= gimple_call_arg (stmt
, 1);
3390 tree dst
= gimple_call_arg (stmt
, 0);
3392 /* Bail if the source is the same as destination. It will be diagnosed
3394 if (operand_equal_p (src
, dst
, 0))
3397 tree lhs
= gimple_call_lhs (stmt
);
3399 didx
= get_stridx (dst
);
3405 dsi
= get_strinfo (didx
);
3409 idx
= get_stridx (src
);
3411 srclen
= build_int_cst (size_type_node
, ~idx
);
3414 si
= get_strinfo (idx
);
3416 srclen
= get_string_length (si
);
3419 /* Set the no-warning bit on the transformed statement? */
3420 bool set_no_warning
= false;
3422 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
3425 /* The concatenation always involves copying at least one byte
3426 (the terminating nul), even if the source string is empty.
3427 If the source is unknown assume it's one character long and
3428 used that as both sizes. */
3432 tree type
= TREE_TYPE (slen
);
3433 slen
= fold_build2 (PLUS_EXPR
, type
, slen
, build_int_cst (type
, 1));
3436 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
3438 if (check_bounds_or_overlap (stmt
, dst
, sptr
, NULL_TREE
, slen
))
3440 gimple_set_no_warning (stmt
, true);
3441 set_no_warning
= true;
3445 /* strcat (p, q) can be transformed into
3446 tmp = p + strlen (p); endptr = stpcpy (tmp, q);
3447 with length endptr - p if we need to compute the length
3448 later on. Don't do this transformation if we don't need
3450 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
3454 didx
= new_stridx (dst
);
3460 dsi
= new_strinfo (dst
, didx
, NULL_TREE
, false);
3461 set_strinfo (didx
, dsi
);
3462 find_equal_ptrs (dst
, didx
);
3466 dsi
= unshare_strinfo (dsi
);
3467 dsi
->nonzero_chars
= NULL_TREE
;
3468 dsi
->full_string_p
= false;
3470 dsi
->endptr
= NULL_TREE
;
3472 dsi
->writable
= true;
3474 dsi
->dont_invalidate
= true;
3479 tree dstlen
= dsi
->nonzero_chars
;
3480 endptr
= dsi
->endptr
;
3482 dsi
= unshare_strinfo (dsi
);
3483 dsi
->endptr
= NULL_TREE
;
3485 dsi
->writable
= true;
3487 if (srclen
!= NULL_TREE
)
3489 dsi
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
3490 TREE_TYPE (dsi
->nonzero_chars
),
3491 dsi
->nonzero_chars
, srclen
);
3492 gcc_assert (dsi
->full_string_p
);
3493 adjust_related_strinfos (loc
, dsi
, srclen
);
3494 dsi
->dont_invalidate
= true;
3498 dsi
->nonzero_chars
= NULL
;
3499 dsi
->full_string_p
= false;
3500 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
3501 dsi
->dont_invalidate
= true;
3505 /* strcat src may not overlap dst, so src doesn't need to be
3506 invalidated either. */
3507 si
->dont_invalidate
= true;
3509 /* For now. Could remove the lhs from the call and add
3510 lhs = dst; afterwards. */
3518 case BUILT_IN_STRCAT
:
3519 if (srclen
!= NULL_TREE
)
3520 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
3522 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
3524 case BUILT_IN_STRCAT_CHK
:
3525 if (srclen
!= NULL_TREE
)
3526 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
3528 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
3529 objsz
= gimple_call_arg (stmt
, 2);
3535 if (fn
== NULL_TREE
)
3540 tree type
= TREE_TYPE (dstlen
);
3542 /* Compute the size of the source sequence, including the nul. */
3543 tree srcsize
= srclen
? srclen
: size_zero_node
;
3544 tree one
= build_int_cst (type
, 1);
3545 srcsize
= fold_build2 (PLUS_EXPR
, type
, srcsize
, one
);
3546 tree dstsize
= fold_build2 (PLUS_EXPR
, type
, dstlen
, one
);
3547 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
3549 if (check_bounds_or_overlap (stmt
, dst
, sptr
, dstsize
, srcsize
))
3551 gimple_set_no_warning (stmt
, true);
3552 set_no_warning
= true;
3556 tree len
= NULL_TREE
;
3557 if (srclen
!= NULL_TREE
)
3559 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
3560 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
3562 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
3563 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
3564 build_int_cst (type
, 1));
3565 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
3569 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
3571 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
, TREE_TYPE (dst
), dst
,
3572 fold_convert_loc (loc
, sizetype
,
3573 unshare_expr (dstlen
)));
3574 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
3578 objsz
= fold_build2_loc (loc
, MINUS_EXPR
, TREE_TYPE (objsz
), objsz
,
3579 fold_convert_loc (loc
, TREE_TYPE (objsz
),
3580 unshare_expr (dstlen
)));
3581 objsz
= force_gimple_operand_gsi (gsi
, objsz
, true, NULL_TREE
, true,
3584 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3586 fprintf (dump_file
, "Optimizing: ");
3587 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3589 if (srclen
!= NULL_TREE
)
3590 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
3591 dst
, src
, len
, objsz
);
3593 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
3597 stmt
= gsi_stmt (*gsi
);
3599 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3601 fprintf (dump_file
, "into: ");
3602 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3604 /* If srclen == NULL, note that current string length can be
3605 computed by transforming this strcpy into stpcpy. */
3606 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
3608 adjust_last_stmt (dsi
, stmt
, true, ptr_qry
);
3609 if (srclen
!= NULL_TREE
)
3611 laststmt
.stmt
= stmt
;
3612 laststmt
.len
= srclen
;
3613 laststmt
.stridx
= dsi
->idx
;
3616 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3617 fprintf (dump_file
, "not possible.\n");
3620 gimple_set_no_warning (stmt
, true);
3623 /* Handle a call to an allocation function like alloca, malloc or calloc,
3624 or an ordinary allocation function declared with attribute alloc_size. */
3627 handle_alloc_call (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
3629 gimple
*stmt
= gsi_stmt (*gsi
);
3630 tree lhs
= gimple_call_lhs (stmt
);
3631 if (lhs
== NULL_TREE
)
3634 gcc_assert (get_stridx (lhs
) == 0);
3635 int idx
= new_stridx (lhs
);
3636 tree length
= NULL_TREE
;
3637 if (bcode
== BUILT_IN_CALLOC
)
3638 length
= build_int_cst (size_type_node
, 0);
3639 strinfo
*si
= new_strinfo (lhs
, idx
, length
, length
!= NULL_TREE
);
3640 if (bcode
== BUILT_IN_CALLOC
)
3642 /* Only set STMT for calloc and malloc. */
3644 /* Only set ENDPTR for calloc. */
3647 else if (bcode
== BUILT_IN_MALLOC
)
3650 /* Set ALLOC is set for all allocation functions. */
3652 set_strinfo (idx
, si
);
3653 si
->writable
= true;
3654 si
->dont_invalidate
= true;
3657 /* Handle a call to memset.
3658 After a call to calloc, memset(,0,) is unnecessary.
3659 memset(malloc(n),0,n) is calloc(n,1).
3660 return true when the call is transformed, false otherwise.
3661 When nonnull uses RVALS to determine range information. */
3664 handle_builtin_memset (gimple_stmt_iterator
*gsi
, bool *zero_write
,
3665 pointer_query
&ptr_qry
)
3667 gimple
*memset_stmt
= gsi_stmt (*gsi
);
3668 tree ptr
= gimple_call_arg (memset_stmt
, 0);
3669 /* Set to the non-constant offset added to PTR. */
3671 int idx1
= get_stridx (ptr
, offrng
, ptr_qry
.rvals
);
3674 strinfo
*si1
= get_strinfo (idx1
);
3677 gimple
*alloc_stmt
= si1
->alloc
;
3678 if (!alloc_stmt
|| !is_gimple_call (alloc_stmt
))
3680 tree callee1
= gimple_call_fndecl (alloc_stmt
);
3681 if (!valid_builtin_call (alloc_stmt
))
3683 tree alloc_size
= gimple_call_arg (alloc_stmt
, 0);
3684 tree memset_size
= gimple_call_arg (memset_stmt
, 2);
3686 /* Check for overflow. */
3687 maybe_warn_overflow (memset_stmt
, memset_size
, ptr_qry
, NULL
, false, false);
3689 /* Bail when there is no statement associated with the destination
3690 (the statement may be null even when SI1->ALLOC is not). */
3694 /* Avoid optimizing if store is at a variable offset from the beginning
3695 of the allocated object. */
3696 if (offrng
[0] != 0 || offrng
[0] != offrng
[1])
3699 /* Bail when the call writes a non-zero value. */
3700 if (!integer_zerop (gimple_call_arg (memset_stmt
, 1)))
3703 /* Let the caller know the memset call cleared the destination. */
3706 enum built_in_function code1
= DECL_FUNCTION_CODE (callee1
);
3707 if (code1
== BUILT_IN_CALLOC
)
3708 /* Not touching alloc_stmt */ ;
3709 else if (code1
== BUILT_IN_MALLOC
3710 && operand_equal_p (memset_size
, alloc_size
, 0))
3712 /* Replace the malloc + memset calls with calloc. */
3713 gimple_stmt_iterator gsi1
= gsi_for_stmt (si1
->stmt
);
3714 update_gimple_call (&gsi1
, builtin_decl_implicit (BUILT_IN_CALLOC
), 2,
3715 alloc_size
, build_one_cst (size_type_node
));
3716 si1
->nonzero_chars
= build_int_cst (size_type_node
, 0);
3717 si1
->full_string_p
= true;
3718 si1
->stmt
= gsi_stmt (gsi1
);
3722 tree lhs
= gimple_call_lhs (memset_stmt
);
3723 unlink_stmt_vdef (memset_stmt
);
3726 gimple
*assign
= gimple_build_assign (lhs
, ptr
);
3727 gsi_replace (gsi
, assign
, false);
3731 gsi_remove (gsi
, true);
3732 release_defs (memset_stmt
);
3738 /* Return first such statement if RES is used in statements testing its
3739 equality to zero, and null otherwise. If EXCLUSIVE is true, return
3740 nonnull if and only RES is used in such expressions exclusively and
3744 use_in_zero_equality (tree res
, bool exclusive
= true)
3746 gimple
*first_use
= NULL
;
3748 use_operand_p use_p
;
3749 imm_use_iterator iter
;
3751 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
3753 gimple
*use_stmt
= USE_STMT (use_p
);
3755 if (is_gimple_debug (use_stmt
))
3758 if (gimple_code (use_stmt
) == GIMPLE_ASSIGN
)
3760 tree_code code
= gimple_assign_rhs_code (use_stmt
);
3761 if (code
== COND_EXPR
)
3763 tree cond_expr
= gimple_assign_rhs1 (use_stmt
);
3764 if ((TREE_CODE (cond_expr
) != EQ_EXPR
3765 && (TREE_CODE (cond_expr
) != NE_EXPR
))
3766 || !integer_zerop (TREE_OPERAND (cond_expr
, 1)))
3773 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3775 if (!integer_zerop (gimple_assign_rhs2 (use_stmt
)))
3787 else if (gimple_code (use_stmt
) == GIMPLE_COND
)
3789 tree_code code
= gimple_cond_code (use_stmt
);
3790 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
3791 || !integer_zerop (gimple_cond_rhs (use_stmt
)))
3804 first_use
= use_stmt
;
3810 /* Handle a call to memcmp. We try to handle small comparisons by
3811 converting them to load and compare, and replacing the call to memcmp
3812 with a __builtin_memcmp_eq call where possible.
3813 return true when call is transformed, return false otherwise. */
3816 handle_builtin_memcmp (gimple_stmt_iterator
*gsi
)
3818 gcall
*stmt
= as_a
<gcall
*> (gsi_stmt (*gsi
));
3819 tree res
= gimple_call_lhs (stmt
);
3821 if (!res
|| !use_in_zero_equality (res
))
3824 tree arg1
= gimple_call_arg (stmt
, 0);
3825 tree arg2
= gimple_call_arg (stmt
, 1);
3826 tree len
= gimple_call_arg (stmt
, 2);
3827 unsigned HOST_WIDE_INT leni
;
3829 if (tree_fits_uhwi_p (len
)
3830 && (leni
= tree_to_uhwi (len
)) <= GET_MODE_SIZE (word_mode
)
3831 && pow2p_hwi (leni
))
3833 leni
*= CHAR_TYPE_SIZE
;
3834 unsigned align1
= get_pointer_alignment (arg1
);
3835 unsigned align2
= get_pointer_alignment (arg2
);
3836 unsigned align
= MIN (align1
, align2
);
3837 scalar_int_mode mode
;
3838 if (int_mode_for_size (leni
, 1).exists (&mode
)
3839 && (align
>= leni
|| !targetm
.slow_unaligned_access (mode
, align
)))
3841 location_t loc
= gimple_location (stmt
);
3843 type
= build_nonstandard_integer_type (leni
, 1);
3844 gcc_assert (known_eq (GET_MODE_BITSIZE (TYPE_MODE (type
)), leni
));
3845 tree ptrtype
= build_pointer_type_for_mode (char_type_node
,
3847 off
= build_int_cst (ptrtype
, 0);
3848 arg1
= build2_loc (loc
, MEM_REF
, type
, arg1
, off
);
3849 arg2
= build2_loc (loc
, MEM_REF
, type
, arg2
, off
);
3850 tree tem1
= fold_const_aggregate_ref (arg1
);
3853 tree tem2
= fold_const_aggregate_ref (arg2
);
3856 res
= fold_convert_loc (loc
, TREE_TYPE (res
),
3857 fold_build2_loc (loc
, NE_EXPR
,
3860 gimplify_and_update_call_from_tree (gsi
, res
);
3865 gimple_call_set_fndecl (stmt
, builtin_decl_explicit (BUILT_IN_MEMCMP_EQ
));
3869 /* Given strinfo IDX for ARG, sets LENRNG[] to the range of lengths
3870 of the string(s) referenced by ARG if it can be determined.
3871 If the length cannot be determined, sets *SIZE to the size of
3872 the array the string is stored in, if any. If no such array is
3873 known, sets *SIZE to -1. When the strings are nul-terminated sets
3874 *NULTERM to true, otherwise to false. When nonnull uses RVALS to
3875 determine range information. Returns true on success. */
3878 get_len_or_size (gimple
*stmt
, tree arg
, int idx
,
3879 unsigned HOST_WIDE_INT lenrng
[2],
3880 unsigned HOST_WIDE_INT
*size
, bool *nulterm
,
3884 *size
= HOST_WIDE_INT_M1U
;
3888 /* IDX is the inverted constant string length. */
3890 lenrng
[1] = lenrng
[0];
3895 /* Set so that both LEN and ~LEN are invalid lengths, i.e., maximum
3896 possible length + 1. */
3897 lenrng
[0] = lenrng
[1] = HOST_WIDE_INT_MAX
;
3899 if (strinfo
*si
= idx
? get_strinfo (idx
) : NULL
)
3901 /* FIXME: Handle all this in_range_strlen_dynamic. */
3902 if (!si
->nonzero_chars
)
3904 else if (tree_fits_uhwi_p (si
->nonzero_chars
))
3906 lenrng
[0] = tree_to_uhwi (si
->nonzero_chars
);
3907 *nulterm
= si
->full_string_p
;
3908 /* Set the upper bound only if the string is known to be
3909 nul-terminated, otherwise leave it at maximum + 1. */
3911 lenrng
[1] = lenrng
[0];
3913 else if (TREE_CODE (si
->nonzero_chars
) == SSA_NAME
)
3916 // FIXME: Use range_query instead of global ranges.
3917 value_range_kind rng
= get_range_info (si
->nonzero_chars
, &min
, &max
);
3918 if (rng
== VR_RANGE
)
3920 lenrng
[0] = min
.to_uhwi ();
3921 lenrng
[1] = max
.to_uhwi ();
3922 *nulterm
= si
->full_string_p
;
3927 if (lenrng
[0] != HOST_WIDE_INT_MAX
)
3930 /* Compute the minimum and maximum real or possible lengths. */
3931 c_strlen_data lendata
= { };
3932 /* Set MAXBOUND to an arbitrary non-null non-integer node as a request
3933 to have it set to the length of the longest string in a PHI. */
3934 lendata
.maxbound
= arg
;
3935 get_range_strlen_dynamic (arg
, stmt
, &lendata
, rvals
);
3937 unsigned HOST_WIDE_INT maxbound
= HOST_WIDE_INT_M1U
;
3938 if (tree_fits_uhwi_p (lendata
.maxbound
)
3939 && !integer_all_onesp (lendata
.maxbound
))
3940 maxbound
= tree_to_uhwi (lendata
.maxbound
);
3942 if (tree_fits_uhwi_p (lendata
.minlen
) && tree_fits_uhwi_p (lendata
.maxlen
))
3944 unsigned HOST_WIDE_INT minlen
= tree_to_uhwi (lendata
.minlen
);
3945 unsigned HOST_WIDE_INT maxlen
= tree_to_uhwi (lendata
.maxlen
);
3947 /* The longest string in this data model. */
3948 const unsigned HOST_WIDE_INT lenmax
3949 = tree_to_uhwi (max_object_size ()) - 2;
3951 if (maxbound
== HOST_WIDE_INT_M1U
)
3955 *nulterm
= minlen
== maxlen
;
3957 else if (maxlen
< lenmax
)
3959 *size
= maxbound
+ 1;
3968 if (maxbound
!= HOST_WIDE_INT_M1U
3970 && !integer_all_onesp (lendata
.maxlen
))
3972 /* Set *SIZE to LENDATA.MAXBOUND which is a conservative estimate
3973 of the longest string based on the sizes of the arrays referenced
3975 *size
= maxbound
+ 1;
3983 /* If IDX1 and IDX2 refer to strings A and B of unequal lengths, return
3984 the result of 0 == strncmp (A, B, BOUND) (which is the same as strcmp
3985 for a sufficiently large BOUND). If the result is based on the length
3986 of one string being greater than the longest string that would fit in
3987 the array pointer to by the argument, set *PLEN and *PSIZE to
3988 the corresponding length (or its complement when the string is known
3989 to be at least as long and need not be nul-terminated) and size.
3990 Otherwise return null. */
3993 strxcmp_eqz_result (gimple
*stmt
, tree arg1
, int idx1
, tree arg2
, int idx2
,
3994 unsigned HOST_WIDE_INT bound
, unsigned HOST_WIDE_INT len
[2],
3995 unsigned HOST_WIDE_INT
*psize
, range_query
*rvals
)
3997 /* Determine the range the length of each string is in and whether it's
3998 known to be nul-terminated, or the size of the array it's stored in. */
4000 unsigned HOST_WIDE_INT siz1
, siz2
;
4001 unsigned HOST_WIDE_INT len1rng
[2], len2rng
[2];
4002 if (!get_len_or_size (stmt
, arg1
, idx1
, len1rng
, &siz1
, &nul1
, rvals
)
4003 || !get_len_or_size (stmt
, arg2
, idx2
, len2rng
, &siz2
, &nul2
, rvals
))
4006 /* BOUND is set to HWI_M1U for strcmp and less to strncmp, and LENiRNG
4007 to HWI_MAX when invalid. Adjust the length of each string to consider
4008 to be no more than BOUND. */
4009 if (len1rng
[0] < HOST_WIDE_INT_MAX
&& len1rng
[0] > bound
)
4011 if (len1rng
[1] < HOST_WIDE_INT_MAX
&& len1rng
[1] > bound
)
4013 if (len2rng
[0] < HOST_WIDE_INT_MAX
&& len2rng
[0] > bound
)
4015 if (len2rng
[1] < HOST_WIDE_INT_MAX
&& len2rng
[1] > bound
)
4018 /* Two empty strings are equal. */
4019 if (len1rng
[1] == 0 && len2rng
[1] == 0)
4020 return integer_one_node
;
4022 /* The strings are definitely unequal when the lower bound of the length
4023 of one of them is greater than the length of the longest string that
4024 would fit into the other array. */
4025 if (len1rng
[0] == HOST_WIDE_INT_MAX
4026 && len2rng
[0] != HOST_WIDE_INT_MAX
4027 && ((len2rng
[0] < bound
&& len2rng
[0] >= siz1
)
4028 || len2rng
[0] > siz1
))
4031 len
[0] = len1rng
[0];
4032 /* Set LEN[0] to the lower bound of ARG1's length when it's
4033 nul-terminated or to the complement of its minimum length
4035 len
[1] = nul2
? len2rng
[0] : ~len2rng
[0];
4036 return integer_zero_node
;
4039 if (len2rng
[0] == HOST_WIDE_INT_MAX
4040 && len1rng
[0] != HOST_WIDE_INT_MAX
4041 && ((len1rng
[0] < bound
&& len1rng
[0] >= siz2
)
4042 || len1rng
[0] > siz2
))
4045 len
[0] = nul1
? len1rng
[0] : ~len1rng
[0];
4046 len
[1] = len2rng
[0];
4047 return integer_zero_node
;
4050 /* The strings are also definitely unequal when their lengths are unequal
4051 and at least one is nul-terminated. */
4052 if (len1rng
[0] != HOST_WIDE_INT_MAX
4053 && len2rng
[0] != HOST_WIDE_INT_MAX
4054 && ((len1rng
[1] < len2rng
[0] && nul1
)
4055 || (len2rng
[1] < len1rng
[0] && nul2
)))
4057 if (bound
<= len1rng
[0] || bound
<= len2rng
[0])
4060 *psize
= HOST_WIDE_INT_M1U
;
4062 len
[0] = len1rng
[0];
4063 len
[1] = len2rng
[0];
4064 return integer_zero_node
;
4067 /* The string lengths may be equal or unequal. Even when equal and
4068 both strings nul-terminated, without the string contents there's
4069 no way to determine whether they are equal. */
4073 /* Diagnose pointless calls to strcmp or strncmp STMT with string
4074 arguments of lengths LEN or size SIZ and (for strncmp) BOUND,
4075 whose result is used in equality expressions that evaluate to
4076 a constant due to one argument being longer than the size of
4080 maybe_warn_pointless_strcmp (gimple
*stmt
, HOST_WIDE_INT bound
,
4081 unsigned HOST_WIDE_INT len
[2],
4082 unsigned HOST_WIDE_INT siz
)
4084 tree lhs
= gimple_call_lhs (stmt
);
4085 gimple
*use
= use_in_zero_equality (lhs
, /* exclusive = */ false);
4089 bool at_least
= false;
4091 /* Excessive LEN[i] indicates a lower bound. */
4092 if (len
[0] > HOST_WIDE_INT_MAX
)
4098 if (len
[1] > HOST_WIDE_INT_MAX
)
4104 unsigned HOST_WIDE_INT minlen
= MIN (len
[0], len
[1]);
4106 /* FIXME: Include a note pointing to the declaration of the smaller
4108 location_t stmt_loc
= gimple_or_expr_nonartificial_location (stmt
, lhs
);
4110 tree callee
= gimple_call_fndecl (stmt
);
4111 bool warned
= false;
4112 if (siz
<= minlen
&& bound
== -1)
4113 warned
= warning_at (stmt_loc
, OPT_Wstring_compare
,
4115 ? G_("%G%qD of a string of length %wu or more and "
4116 "an array of size %wu evaluates to nonzero")
4117 : G_("%G%qD of a string of length %wu and an array "
4118 "of size %wu evaluates to nonzero")),
4119 stmt
, callee
, minlen
, siz
);
4120 else if (!at_least
&& siz
<= HOST_WIDE_INT_MAX
)
4122 if (len
[0] != HOST_WIDE_INT_MAX
&& len
[1] != HOST_WIDE_INT_MAX
)
4123 warned
= warning_at (stmt_loc
, OPT_Wstring_compare
,
4124 "%G%qD of strings of length %wu and %wu "
4125 "and bound of %wu evaluates to nonzero",
4126 stmt
, callee
, len
[0], len
[1], bound
);
4128 warned
= warning_at (stmt_loc
, OPT_Wstring_compare
,
4129 "%G%qD of a string of length %wu, an array "
4130 "of size %wu and bound of %wu evaluates to "
4132 stmt
, callee
, minlen
, siz
, bound
);
4138 location_t use_loc
= gimple_location (use
);
4139 if (LOCATION_LINE (stmt_loc
) != LOCATION_LINE (use_loc
))
4140 inform (use_loc
, "in this expression");
4144 /* Optimize a call to strcmp or strncmp either by folding it to a constant
4145 when possible or by transforming the latter to the former. Warn about
4146 calls where the length of one argument is greater than the size of
4147 the array to which the other argument points if the latter's length
4148 is not known. Return true when the call has been transformed into
4149 another and false otherwise. */
4152 handle_builtin_string_cmp (gimple_stmt_iterator
*gsi
, range_query
*rvals
)
4154 gcall
*stmt
= as_a
<gcall
*> (gsi_stmt (*gsi
));
4155 tree lhs
= gimple_call_lhs (stmt
);
4160 tree arg1
= gimple_call_arg (stmt
, 0);
4161 tree arg2
= gimple_call_arg (stmt
, 1);
4162 int idx1
= get_stridx (arg1
);
4163 int idx2
= get_stridx (arg2
);
4165 /* For strncmp set to the value of the third argument if known. */
4166 HOST_WIDE_INT bound
= -1;
4167 tree len
= NULL_TREE
;
4168 /* Extract the strncmp bound. */
4169 if (gimple_call_num_args (stmt
) == 3)
4171 len
= gimple_call_arg (stmt
, 2);
4172 if (tree_fits_shwi_p (len
))
4173 bound
= tree_to_shwi (len
);
4175 /* If the bound argument is NOT known, do nothing. */
4180 /* Avoid folding if either argument is not a nul-terminated array.
4181 Defer warning until later. */
4182 if (!check_nul_terminated_array (NULL_TREE
, arg1
, len
)
4183 || !check_nul_terminated_array (NULL_TREE
, arg2
, len
))
4187 /* Set to the length of one argument (or its complement if it's
4188 the lower bound of a range) and the size of the array storing
4189 the other if the result is based on the former being equal to
4190 or greater than the latter. */
4191 unsigned HOST_WIDE_INT len
[2] = { HOST_WIDE_INT_MAX
, HOST_WIDE_INT_MAX
};
4192 unsigned HOST_WIDE_INT siz
= HOST_WIDE_INT_M1U
;
4194 /* Try to determine if the two strings are either definitely equal
4195 or definitely unequal and if so, either fold the result to zero
4196 (when equal) or set the range of the result to ~[0, 0] otherwise. */
4197 if (tree eqz
= strxcmp_eqz_result (stmt
, arg1
, idx1
, arg2
, idx2
, bound
,
4200 if (integer_zerop (eqz
))
4202 maybe_warn_pointless_strcmp (stmt
, bound
, len
, siz
);
4204 /* When the lengths of the first two string arguments are
4205 known to be unequal set the range of the result to non-zero.
4206 This allows the call to be eliminated if its result is only
4207 used in tests for equality to zero. */
4208 wide_int zero
= wi::zero (TYPE_PRECISION (TREE_TYPE (lhs
)));
4209 set_range_info (lhs
, VR_ANTI_RANGE
, zero
, zero
);
4212 /* When the two strings are definitely equal (such as when they
4213 are both empty) fold the call to the constant result. */
4214 replace_call_with_value (gsi
, integer_zero_node
);
4219 /* Return if nothing is known about the strings pointed to by ARG1
4221 if (idx1
== 0 && idx2
== 0)
4224 /* Determine either the length or the size of each of the strings,
4225 whichever is available. */
4226 HOST_WIDE_INT cstlen1
= -1, cstlen2
= -1;
4227 HOST_WIDE_INT arysiz1
= -1, arysiz2
= -1;
4230 unsigned HOST_WIDE_INT len1rng
[2], len2rng
[2];
4231 unsigned HOST_WIDE_INT arsz1
, arsz2
;
4234 if (!get_len_or_size (stmt
, arg1
, idx1
, len1rng
, &arsz1
, nulterm
, rvals
)
4235 || !get_len_or_size (stmt
, arg2
, idx2
, len2rng
, &arsz2
, nulterm
+ 1,
4239 if (len1rng
[0] == len1rng
[1] && len1rng
[0] < HOST_WIDE_INT_MAX
)
4240 cstlen1
= len1rng
[0];
4241 else if (arsz1
< HOST_WIDE_INT_M1U
)
4244 if (len2rng
[0] == len2rng
[1] && len2rng
[0] < HOST_WIDE_INT_MAX
)
4245 cstlen2
= len2rng
[0];
4246 else if (arsz2
< HOST_WIDE_INT_M1U
)
4250 /* Bail if neither the string length nor the size of the array
4251 it is stored in can be determined. */
4252 if ((cstlen1
< 0 && arysiz1
< 0)
4253 || (cstlen2
< 0 && arysiz2
< 0)
4254 || (cstlen1
< 0 && cstlen2
< 0))
4262 /* The exact number of characters to compare. */
4263 HOST_WIDE_INT cmpsiz
;
4264 if (cstlen1
>= 0 && cstlen2
>= 0)
4265 cmpsiz
= MIN (cstlen1
, cstlen2
);
4266 else if (cstlen1
>= 0)
4271 cmpsiz
= MIN (cmpsiz
, bound
);
4272 /* The size of the array in which the unknown string is stored. */
4273 HOST_WIDE_INT varsiz
= arysiz1
< 0 ? arysiz2
: arysiz1
;
4275 if ((varsiz
< 0 || cmpsiz
< varsiz
) && use_in_zero_equality (lhs
))
4277 /* If the known length is less than the size of the other array
4278 and the strcmp result is only used to test equality to zero,
4279 transform the call to the equivalent _eq call. */
4280 if (tree fn
= builtin_decl_implicit (bound
< 0 ? BUILT_IN_STRCMP_EQ
4281 : BUILT_IN_STRNCMP_EQ
))
4283 tree n
= build_int_cst (size_type_node
, cmpsiz
);
4284 update_gimple_call (gsi
, fn
, 3, arg1
, arg2
, n
);
4292 /* Handle a POINTER_PLUS_EXPR statement.
4293 For p = "abcd" + 2; compute associated length, or if
4294 p = q + off is pointing to a '\0' character of a string, call
4295 zero_length_string on it. */
4298 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
4300 gimple
*stmt
= gsi_stmt (*gsi
);
4301 tree lhs
= gimple_assign_lhs (stmt
), off
;
4302 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
4310 tree off
= gimple_assign_rhs2 (stmt
);
4311 if (tree_fits_uhwi_p (off
)
4312 && tree_to_uhwi (off
) <= (unsigned HOST_WIDE_INT
) ~idx
)
4313 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
4314 = ~(~idx
- (int) tree_to_uhwi (off
));
4318 si
= get_strinfo (idx
);
4319 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
4322 off
= gimple_assign_rhs2 (stmt
);
4324 if (si
->full_string_p
&& operand_equal_p (si
->nonzero_chars
, off
, 0))
4325 zsi
= zero_length_string (lhs
, si
);
4326 else if (TREE_CODE (off
) == SSA_NAME
)
4328 gimple
*def_stmt
= SSA_NAME_DEF_STMT (off
);
4329 if (gimple_assign_single_p (def_stmt
)
4330 && si
->full_string_p
4331 && operand_equal_p (si
->nonzero_chars
,
4332 gimple_assign_rhs1 (def_stmt
), 0))
4333 zsi
= zero_length_string (lhs
, si
);
4336 && si
->endptr
!= NULL_TREE
4337 && si
->endptr
!= lhs
4338 && TREE_CODE (si
->endptr
) == SSA_NAME
)
4340 enum tree_code rhs_code
4341 = useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (si
->endptr
))
4342 ? SSA_NAME
: NOP_EXPR
;
4343 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, si
->endptr
);
4344 gcc_assert (gsi_stmt (*gsi
) == stmt
);
4350 count_nonzero_bytes_addr (tree
, unsigned HOST_WIDE_INT
, unsigned HOST_WIDE_INT
,
4351 unsigned [3], bool *, bool *, bool *,
4352 range_query
*, ssa_name_limit_t
&);
4354 /* Determines the minimum and maximum number of leading non-zero bytes
4355 in the representation of EXP and set LENRANGE[0] and LENRANGE[1]
4357 Sets LENRANGE[2] to the total size of the access (which may be less
4358 than LENRANGE[1] when what's being referenced by EXP is a pointer
4359 rather than an array).
4360 Sets *NULTERM if the representation contains a zero byte, and sets
4361 *ALLNUL if all the bytes are zero.
4362 OFFSET and NBYTES are the offset into the representation and
4363 the size of the access to it determined from an ADDR_EXPR (i.e.,
4364 a pointer) or MEM_REF or zero for other expressions.
4365 Uses RVALS to determine range information.
4366 Avoids recursing deeper than the limits in SNLIM allow.
4367 Returns true on success and false otherwise. */
4370 count_nonzero_bytes (tree exp
, unsigned HOST_WIDE_INT offset
,
4371 unsigned HOST_WIDE_INT nbytes
,
4372 unsigned lenrange
[3], bool *nulterm
,
4373 bool *allnul
, bool *allnonnul
, range_query
*rvals
,
4374 ssa_name_limit_t
&snlim
)
4376 if (TREE_CODE (exp
) == SSA_NAME
)
4378 /* Handle non-zero single-character stores specially. */
4379 tree type
= TREE_TYPE (exp
);
4380 if (TREE_CODE (type
) == INTEGER_TYPE
4381 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
4382 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
)
4383 && tree_expr_nonzero_p (exp
))
4385 /* If the character EXP is known to be non-zero (even if its
4386 exact value is not known) recurse once to set the range
4387 for an arbitrary constant. */
4388 exp
= build_int_cst (type
, 1);
4389 return count_nonzero_bytes (exp
, offset
, 1, lenrange
,
4390 nulterm
, allnul
, allnonnul
, rvals
, snlim
);
4393 gimple
*stmt
= SSA_NAME_DEF_STMT (exp
);
4394 if (gimple_assign_single_p (stmt
))
4396 exp
= gimple_assign_rhs1 (stmt
);
4397 if (TREE_CODE (exp
) != MEM_REF
)
4399 /* Handle MEM_REF below. */
4401 else if (gimple_code (stmt
) == GIMPLE_PHI
)
4403 /* Avoid processing an SSA_NAME that has already been visited
4404 or if an SSA_NAME limit has been reached. Indicate success
4405 if the former and failure if the latter. */
4406 if (int res
= snlim
.next_phi (exp
))
4409 /* Determine the minimum and maximum from the PHI arguments. */
4410 unsigned int n
= gimple_phi_num_args (stmt
);
4411 for (unsigned i
= 0; i
!= n
; i
++)
4413 tree def
= gimple_phi_arg_def (stmt
, i
);
4414 if (!count_nonzero_bytes (def
, offset
, nbytes
, lenrange
, nulterm
,
4415 allnul
, allnonnul
, rvals
, snlim
))
4423 if (TREE_CODE (exp
) == MEM_REF
)
4428 tree arg
= TREE_OPERAND (exp
, 0);
4429 tree off
= TREE_OPERAND (exp
, 1);
4431 if (TREE_CODE (off
) != INTEGER_CST
|| !tree_fits_uhwi_p (off
))
4434 unsigned HOST_WIDE_INT wioff
= tree_to_uhwi (off
);
4435 if (INT_MAX
< wioff
)
4439 if (INT_MAX
< offset
)
4442 /* The size of the MEM_REF access determines the number of bytes. */
4443 tree type
= TREE_TYPE (exp
);
4444 tree typesize
= TYPE_SIZE_UNIT (type
);
4445 if (!typesize
|| !tree_fits_uhwi_p (typesize
))
4447 nbytes
= tree_to_uhwi (typesize
);
4451 /* Handle MEM_REF = SSA_NAME types of assignments. */
4452 return count_nonzero_bytes_addr (arg
, offset
, nbytes
, lenrange
, nulterm
,
4453 allnul
, allnonnul
, rvals
, snlim
);
4456 if (VAR_P (exp
) || TREE_CODE (exp
) == CONST_DECL
)
4458 exp
= ctor_for_folding (exp
);
4463 const char *prep
= NULL
;
4464 if (TREE_CODE (exp
) == STRING_CST
)
4466 unsigned nchars
= TREE_STRING_LENGTH (exp
);
4467 if (nchars
< offset
)
4471 /* If NBYTES hasn't been determined earlier, either from ADDR_EXPR
4472 (i.e., it's the size of a pointer), or from MEM_REF (as the size
4473 of the access), set it here to the size of the string, including
4474 all internal and trailing nuls if the string has any. */
4475 nbytes
= nchars
- offset
;
4476 else if (nchars
- offset
< nbytes
)
4479 prep
= TREE_STRING_POINTER (exp
) + offset
;
4482 unsigned char buf
[256];
4485 if (CHAR_BIT
!= 8 || BITS_PER_UNIT
!= 8)
4487 /* If the pointer to representation hasn't been set above
4488 for STRING_CST point it at the buffer. */
4489 prep
= reinterpret_cast <char *>(buf
);
4490 /* Try to extract the representation of the constant object
4491 or expression starting from the offset. */
4492 unsigned repsize
= native_encode_expr (exp
, buf
, sizeof buf
, offset
);
4493 if (repsize
< nbytes
)
4495 /* This should only happen when REPSIZE is zero because EXP
4496 doesn't denote an object with a known initializer, except
4497 perhaps when the reference reads past its end. */
4503 else if (nbytes
< repsize
)
4510 /* Compute the number of leading nonzero bytes in the representation
4511 and update the minimum and maximum. */
4512 unsigned n
= prep
? strnlen (prep
, nbytes
) : nbytes
;
4514 if (n
< lenrange
[0])
4516 if (lenrange
[1] < n
)
4519 /* Set the size of the representation. */
4520 if (lenrange
[2] < nbytes
)
4521 lenrange
[2] = nbytes
;
4523 /* Clear NULTERM if none of the bytes is zero. */
4529 /* When the initial number of non-zero bytes N is non-zero, reset
4530 *ALLNUL; if N is less than that the size of the representation
4531 also clear *ALLNONNUL. */
4536 else if (*allnul
|| *allnonnul
)
4542 /* When either ALLNUL is set and N is zero, also determine
4543 whether all subsequent bytes after the first one (which
4544 is nul) are zero or nonzero and clear ALLNUL if not. */
4545 for (const char *p
= prep
; p
!= prep
+ nbytes
; ++p
)
4557 /* Like count_nonzero_bytes, but instead of counting bytes in EXP, count
4558 bytes that are pointed to by EXP, which should be a pointer. */
4561 count_nonzero_bytes_addr (tree exp
, unsigned HOST_WIDE_INT offset
,
4562 unsigned HOST_WIDE_INT nbytes
,
4563 unsigned lenrange
[3], bool *nulterm
,
4564 bool *allnul
, bool *allnonnul
,
4565 range_query
*rvals
, ssa_name_limit_t
&snlim
)
4567 int idx
= get_stridx (exp
);
4570 strinfo
*si
= get_strinfo (idx
);
4574 /* Handle both constant lengths as well non-constant lengths
4576 unsigned HOST_WIDE_INT minlen
, maxlen
;
4577 if (tree_fits_shwi_p (si
->nonzero_chars
))
4578 minlen
= maxlen
= tree_to_shwi (si
->nonzero_chars
);
4579 else if (si
->nonzero_chars
4580 && TREE_CODE (si
->nonzero_chars
) == SSA_NAME
)
4583 rvals
->range_of_expr (vr
, si
->nonzero_chars
, si
->stmt
);
4584 if (vr
.kind () != VR_RANGE
)
4587 minlen
= tree_to_uhwi (vr
.min ());
4588 maxlen
= tree_to_uhwi (vr
.max ());
4593 if (maxlen
< offset
)
4596 minlen
= minlen
< offset
? 0 : minlen
- offset
;
4598 if (maxlen
+ 1 < nbytes
)
4601 if (nbytes
<= minlen
)
4604 if (nbytes
< minlen
)
4607 if (nbytes
< maxlen
)
4611 if (minlen
< lenrange
[0])
4612 lenrange
[0] = minlen
;
4613 if (lenrange
[1] < maxlen
)
4614 lenrange
[1] = maxlen
;
4616 if (lenrange
[2] < nbytes
)
4617 lenrange
[2] = nbytes
;
4619 /* Since only the length of the string are known and not its contents,
4620 clear ALLNUL and ALLNONNUL purely on the basis of the length. */
4622 if (minlen
< nbytes
)
4628 if (TREE_CODE (exp
) == ADDR_EXPR
)
4629 return count_nonzero_bytes (TREE_OPERAND (exp
, 0), offset
, nbytes
,
4630 lenrange
, nulterm
, allnul
, allnonnul
, rvals
,
4633 if (TREE_CODE (exp
) == SSA_NAME
)
4635 gimple
*stmt
= SSA_NAME_DEF_STMT (exp
);
4636 if (gimple_code (stmt
) == GIMPLE_PHI
)
4638 /* Avoid processing an SSA_NAME that has already been visited
4639 or if an SSA_NAME limit has been reached. Indicate success
4640 if the former and failure if the latter. */
4641 if (int res
= snlim
.next_phi (exp
))
4644 /* Determine the minimum and maximum from the PHI arguments. */
4645 unsigned int n
= gimple_phi_num_args (stmt
);
4646 for (unsigned i
= 0; i
!= n
; i
++)
4648 tree def
= gimple_phi_arg_def (stmt
, i
);
4649 if (!count_nonzero_bytes_addr (def
, offset
, nbytes
, lenrange
,
4650 nulterm
, allnul
, allnonnul
, rvals
,
4659 /* Otherwise we don't know anything. */
4661 if (lenrange
[1] < nbytes
)
4662 lenrange
[1] = nbytes
;
4663 if (lenrange
[2] < nbytes
)
4664 lenrange
[2] = nbytes
;
4671 /* Same as above except with an implicit SSA_NAME limit. RVALS is used
4672 to determine ranges of dynamically computed string lengths (the results
4676 count_nonzero_bytes (tree exp
, unsigned lenrange
[3], bool *nulterm
,
4677 bool *allnul
, bool *allnonnul
, range_query
*rvals
)
4679 /* Set to optimistic values so the caller doesn't have to worry about
4680 initializing these and to what. On success, the function will clear
4681 these if it determines their values are different but being recursive
4682 it never sets either to true. On failure, their values are
4688 ssa_name_limit_t snlim
;
4689 return count_nonzero_bytes (exp
, 0, 0, lenrange
, nulterm
, allnul
, allnonnul
,
4693 /* Handle a single or multibyte store other than by a built-in function,
4694 either via a single character assignment or by multi-byte assignment
4695 either via MEM_REF or via a type other than char (such as in
4696 '*(int*)a = 12345'). Return true to let the caller advance *GSI to
4697 the next statement in the basic block and false otherwise. */
4700 handle_store (gimple_stmt_iterator
*gsi
, bool *zero_write
,
4701 pointer_query
&ptr_qry
)
4705 gimple
*stmt
= gsi_stmt (*gsi
);
4706 tree ssaname
= NULL_TREE
, lhs
= gimple_assign_lhs (stmt
);
4707 tree rhs
= gimple_assign_rhs1 (stmt
);
4709 range_query
*const rvals
= ptr_qry
.rvals
;
4711 /* The offset of the first byte in LHS modified by the store. */
4712 unsigned HOST_WIDE_INT offset
= 0;
4714 if (TREE_CODE (lhs
) == MEM_REF
4715 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
)
4717 tree mem_offset
= TREE_OPERAND (lhs
, 1);
4718 if (tree_fits_uhwi_p (mem_offset
))
4720 /* Get the strinfo for the base, and use it if it starts with at
4721 least OFFSET nonzero characters. This is trivially true if
4723 offset
= tree_to_uhwi (mem_offset
);
4724 idx
= get_stridx (TREE_OPERAND (lhs
, 0));
4726 si
= get_strinfo (idx
);
4728 ssaname
= TREE_OPERAND (lhs
, 0);
4729 else if (si
== NULL
|| compare_nonzero_chars (si
, offset
, rvals
) < 0)
4731 *zero_write
= initializer_zerop (rhs
);
4734 unsigned lenrange
[] = { UINT_MAX
, 0, 0 };
4735 if (count_nonzero_bytes (rhs
, lenrange
, &dummy
, &dummy
, &dummy
,
4737 maybe_warn_overflow (stmt
, lenrange
[2], ptr_qry
);
4745 idx
= get_addr_stridx (lhs
, NULL_TREE
, &offset
, rvals
);
4747 si
= get_strinfo (idx
);
4750 /* Minimum and maximum leading non-zero bytes and the size of the store. */
4751 unsigned lenrange
[] = { UINT_MAX
, 0, 0 };
4753 /* Set to the minimum length of the string being assigned if known. */
4754 unsigned HOST_WIDE_INT rhs_minlen
;
4756 /* STORING_NONZERO_P is true iff not all stored characters are zero.
4757 STORING_ALL_NONZERO_P is true if all stored characters are zero.
4758 STORING_ALL_ZEROS_P is true iff all stored characters are zero.
4759 Both are false when it's impossible to determine which is true. */
4760 bool storing_nonzero_p
;
4761 bool storing_all_nonzero_p
;
4762 bool storing_all_zeros_p
;
4763 /* FULL_STRING_P is set when the stored sequence of characters form
4764 a nul-terminated string. */
4767 const bool ranges_valid
4768 = count_nonzero_bytes (rhs
, lenrange
, &full_string_p
,
4769 &storing_all_zeros_p
, &storing_all_nonzero_p
,
4773 rhs_minlen
= lenrange
[0];
4774 storing_nonzero_p
= lenrange
[1] > 0;
4775 *zero_write
= storing_all_zeros_p
;
4777 maybe_warn_overflow (stmt
, lenrange
[2], ptr_qry
);
4781 rhs_minlen
= HOST_WIDE_INT_M1U
;
4782 full_string_p
= false;
4783 storing_nonzero_p
= false;
4784 storing_all_zeros_p
= false;
4785 storing_all_nonzero_p
= false;
4790 /* The corresponding element is set to 1 if the first and last
4791 element, respectively, of the sequence of characters being
4792 written over the string described by SI ends before
4793 the terminating nul (if it has one), to zero if the nul is
4794 being overwritten but not beyond, or negative otherwise. */
4795 int store_before_nul
[2];
4798 /* The offset of the last stored byte. */
4799 unsigned HOST_WIDE_INT endoff
= offset
+ lenrange
[2] - 1;
4800 store_before_nul
[0] = compare_nonzero_chars (si
, offset
, rvals
);
4801 if (endoff
== offset
)
4802 store_before_nul
[1] = store_before_nul
[0];
4804 store_before_nul
[1] = compare_nonzero_chars (si
, endoff
, rvals
);
4808 store_before_nul
[0] = compare_nonzero_chars (si
, offset
, rvals
);
4809 store_before_nul
[1] = store_before_nul
[0];
4810 gcc_assert (offset
== 0 || store_before_nul
[0] >= 0);
4813 if (storing_all_zeros_p
4814 && store_before_nul
[0] == 0
4815 && store_before_nul
[1] == 0
4816 && si
->full_string_p
)
4818 /* When overwriting a '\0' with a '\0', the store can be removed
4819 if we know it has been stored in the current function. */
4820 if (!stmt_could_throw_p (cfun
, stmt
) && si
->writable
)
4822 unlink_stmt_vdef (stmt
);
4823 release_defs (stmt
);
4824 gsi_remove (gsi
, true);
4829 si
->writable
= true;
4835 if (store_before_nul
[1] > 0
4836 && storing_nonzero_p
4837 && lenrange
[0] == lenrange
[1]
4838 && lenrange
[0] == lenrange
[2]
4839 && TREE_CODE (TREE_TYPE (rhs
)) == INTEGER_TYPE
)
4841 /* Handle a store of one or more non-nul characters that ends
4842 before the terminating nul of the destination and so does
4843 not affect its length
4844 If si->nonzero_chars > OFFSET, we aren't overwriting '\0',
4845 and if we aren't storing '\0', we know that the length of
4846 the string and any other zero terminated string in memory
4847 remains the same. In that case we move to the next gimple
4848 statement and return to signal the caller that it shouldn't
4849 invalidate anything.
4851 This is beneficial for cases like:
4856 strcpy (p, "foobar");
4857 size_t len = strlen (p); // can be folded to 6
4858 size_t len2 = strlen (q); // has to be computed
4860 size_t len3 = strlen (p); // can be folded to 6
4861 size_t len4 = strlen (q); // can be folded to len2
4862 bar (len, len2, len3, len4);
4868 if (storing_all_zeros_p
4869 || storing_nonzero_p
4870 || (offset
!= 0 && store_before_nul
[1] > 0))
4872 /* When STORING_NONZERO_P, we know that the string will start
4873 with at least OFFSET + 1 nonzero characters. If storing
4874 a single character, set si->NONZERO_CHARS to the result.
4875 If storing multiple characters, try to determine the number
4876 of leading non-zero characters and set si->NONZERO_CHARS to
4879 When STORING_ALL_ZEROS_P, we know that the string is now
4880 OFFSET characters long.
4882 Otherwise, we're storing an unknown value at offset OFFSET,
4883 so need to clip the nonzero_chars to OFFSET.
4884 Use the minimum length of the string (or individual character)
4885 being stored if it's known. Otherwise, STORING_NONZERO_P
4886 guarantees it's at least 1. */
4888 = storing_nonzero_p
&& ranges_valid
? lenrange
[0] : 1;
4889 location_t loc
= gimple_location (stmt
);
4890 tree oldlen
= si
->nonzero_chars
;
4891 if (store_before_nul
[1] == 0 && si
->full_string_p
)
4892 /* We're overwriting the nul terminator with a nonzero or
4893 unknown character. If the previous stmt was a memcpy,
4894 its length may be decreased. */
4895 adjust_last_stmt (si
, stmt
, false, ptr_qry
);
4896 si
= unshare_strinfo (si
);
4897 if (storing_nonzero_p
)
4899 gcc_assert (len
>= 0);
4900 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
+ len
);
4903 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
);
4905 /* Set FULL_STRING_P only if the length of the strings being
4906 written is the same, and clear it if the strings have
4907 different lengths. In the latter case the length stored
4908 in si->NONZERO_CHARS becomes the lower bound.
4909 FIXME: Handle the upper bound of the length if possible. */
4910 si
->full_string_p
= full_string_p
&& lenrange
[0] == lenrange
[1];
4912 if (storing_all_zeros_p
4914 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
4915 si
->endptr
= ssaname
;
4920 si
->writable
= true;
4921 si
->dont_invalidate
= true;
4924 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
4925 si
->nonzero_chars
, oldlen
);
4926 adjust_related_strinfos (loc
, si
, adj
);
4932 else if (idx
== 0 && (storing_all_zeros_p
|| storing_nonzero_p
))
4935 idx
= new_stridx (ssaname
);
4937 idx
= new_addr_stridx (lhs
);
4940 tree ptr
= (ssaname
? ssaname
: build_fold_addr_expr (lhs
));
4943 if (storing_all_zeros_p
)
4945 else if (storing_nonzero_p
&& ranges_valid
)
4947 /* FIXME: Handle the upper bound of the length when
4948 LENRANGE[0] != LENRANGE[1]. */
4950 if (lenrange
[0] != lenrange
[1])
4951 /* Set the minimum length but ignore the maximum
4953 full_string_p
= false;
4958 tree len
= (slen
<= 0
4960 : build_int_cst (size_type_node
, slen
));
4961 si
= new_strinfo (ptr
, idx
, len
, slen
>= 0 && full_string_p
);
4962 set_strinfo (idx
, si
);
4963 if (storing_all_zeros_p
4965 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
4966 si
->endptr
= ssaname
;
4967 si
->dont_invalidate
= true;
4968 si
->writable
= true;
4972 && rhs_minlen
< HOST_WIDE_INT_M1U
4973 && ssaname
== NULL_TREE
4974 && TREE_CODE (TREE_TYPE (lhs
)) == ARRAY_TYPE
)
4976 HOST_WIDE_INT a
= int_size_in_bytes (TREE_TYPE (lhs
));
4977 if (a
> 0 && (unsigned HOST_WIDE_INT
) a
> rhs_minlen
)
4979 int idx
= new_addr_stridx (lhs
);
4982 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
4983 build_int_cst (size_type_node
, rhs_minlen
),
4985 set_strinfo (idx
, si
);
4986 si
->dont_invalidate
= true;
4991 if (si
!= NULL
&& offset
== 0 && storing_all_zeros_p
&& lenrange
[2] == 1)
4993 /* For single-byte stores only, allow adjust_last_stmt to remove
4994 the statement if the stored '\0' is immediately overwritten. */
4995 laststmt
.stmt
= stmt
;
4996 laststmt
.len
= build_int_cst (size_type_node
, 1);
4997 laststmt
.stridx
= si
->idx
;
5002 /* Try to fold strstr (s, t) eq/ne s to strncmp (s, t, strlen (t)) eq/ne 0. */
5005 fold_strstr_to_strncmp (tree rhs1
, tree rhs2
, gimple
*stmt
)
5007 if (TREE_CODE (rhs1
) != SSA_NAME
5008 || TREE_CODE (rhs2
) != SSA_NAME
)
5011 gimple
*call_stmt
= NULL
;
5012 for (int pass
= 0; pass
< 2; pass
++)
5014 gimple
*g
= SSA_NAME_DEF_STMT (rhs1
);
5015 if (gimple_call_builtin_p (g
, BUILT_IN_STRSTR
)
5016 && has_single_use (rhs1
)
5017 && gimple_call_arg (g
, 0) == rhs2
)
5022 std::swap (rhs1
, rhs2
);
5027 tree arg0
= gimple_call_arg (call_stmt
, 0);
5031 tree arg1
= gimple_call_arg (call_stmt
, 1);
5032 tree arg1_len
= NULL_TREE
;
5033 int idx
= get_stridx (arg1
);
5038 arg1_len
= build_int_cst (size_type_node
, ~idx
);
5041 strinfo
*si
= get_strinfo (idx
);
5043 arg1_len
= get_string_length (si
);
5047 if (arg1_len
!= NULL_TREE
)
5049 gimple_stmt_iterator gsi
= gsi_for_stmt (call_stmt
);
5050 tree strncmp_decl
= builtin_decl_explicit (BUILT_IN_STRNCMP
);
5052 if (!is_gimple_val (arg1_len
))
5054 tree arg1_len_tmp
= make_ssa_name (TREE_TYPE (arg1_len
));
5055 gassign
*arg1_stmt
= gimple_build_assign (arg1_len_tmp
,
5057 gsi_insert_before (&gsi
, arg1_stmt
, GSI_SAME_STMT
);
5058 arg1_len
= arg1_len_tmp
;
5061 gcall
*strncmp_call
= gimple_build_call (strncmp_decl
, 3,
5062 arg0
, arg1
, arg1_len
);
5063 tree strncmp_lhs
= make_ssa_name (integer_type_node
);
5064 gimple_set_vuse (strncmp_call
, gimple_vuse (call_stmt
));
5065 gimple_call_set_lhs (strncmp_call
, strncmp_lhs
);
5066 gsi_remove (&gsi
, true);
5067 gsi_insert_before (&gsi
, strncmp_call
, GSI_SAME_STMT
);
5068 tree zero
= build_zero_cst (TREE_TYPE (strncmp_lhs
));
5070 if (is_gimple_assign (stmt
))
5072 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
5074 tree cond
= gimple_assign_rhs1 (stmt
);
5075 TREE_OPERAND (cond
, 0) = strncmp_lhs
;
5076 TREE_OPERAND (cond
, 1) = zero
;
5080 gimple_assign_set_rhs1 (stmt
, strncmp_lhs
);
5081 gimple_assign_set_rhs2 (stmt
, zero
);
5086 gcond
*cond
= as_a
<gcond
*> (stmt
);
5087 gimple_cond_set_lhs (cond
, strncmp_lhs
);
5088 gimple_cond_set_rhs (cond
, zero
);
5096 /* Return true if TYPE corresponds to a narrow character type. */
5099 is_char_type (tree type
)
5101 return (TREE_CODE (type
) == INTEGER_TYPE
5102 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
5103 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
));
5106 /* Check the built-in call at GSI for validity and optimize it.
5107 Uses RVALS to determine range information.
5108 Return true to let the caller advance *GSI to the next statement
5109 in the basic block and false otherwise. */
5112 strlen_check_and_optimize_call (gimple_stmt_iterator
*gsi
, bool *zero_write
,
5113 pointer_query
&ptr_qry
)
5115 gimple
*stmt
= gsi_stmt (*gsi
);
5117 if (!gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
5119 tree fntype
= gimple_call_fntype (stmt
);
5120 if (fntype
&& lookup_attribute ("alloc_size", TYPE_ATTRIBUTES (fntype
)))
5121 handle_alloc_call (BUILT_IN_NONE
, gsi
);
5124 /* When not optimizing we must be checking printf calls which
5125 we do even for user-defined functions when they are declared
5126 with attribute format. */
5127 if (!flag_optimize_strlen
5129 || !valid_builtin_call (stmt
))
5130 return !handle_printf_call (gsi
, ptr_qry
);
5132 tree callee
= gimple_call_fndecl (stmt
);
5133 switch (DECL_FUNCTION_CODE (callee
))
5135 case BUILT_IN_STRLEN
:
5136 case BUILT_IN_STRNLEN
:
5137 handle_builtin_strlen (gsi
);
5139 case BUILT_IN_STRCHR
:
5140 handle_builtin_strchr (gsi
);
5142 case BUILT_IN_STRCPY
:
5143 case BUILT_IN_STRCPY_CHK
:
5144 case BUILT_IN_STPCPY
:
5145 case BUILT_IN_STPCPY_CHK
:
5146 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee
), gsi
, ptr_qry
);
5149 case BUILT_IN_STRNCAT
:
5150 case BUILT_IN_STRNCAT_CHK
:
5151 handle_builtin_strncat (DECL_FUNCTION_CODE (callee
), gsi
);
5154 case BUILT_IN_STPNCPY
:
5155 case BUILT_IN_STPNCPY_CHK
:
5156 case BUILT_IN_STRNCPY
:
5157 case BUILT_IN_STRNCPY_CHK
:
5158 handle_builtin_stxncpy_strncat (false, gsi
);
5161 case BUILT_IN_MEMCPY
:
5162 case BUILT_IN_MEMCPY_CHK
:
5163 case BUILT_IN_MEMPCPY
:
5164 case BUILT_IN_MEMPCPY_CHK
:
5165 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee
), gsi
, ptr_qry
);
5167 case BUILT_IN_STRCAT
:
5168 case BUILT_IN_STRCAT_CHK
:
5169 handle_builtin_strcat (DECL_FUNCTION_CODE (callee
), gsi
, ptr_qry
);
5171 case BUILT_IN_ALLOCA
:
5172 case BUILT_IN_ALLOCA_WITH_ALIGN
:
5173 case BUILT_IN_MALLOC
:
5174 case BUILT_IN_CALLOC
:
5175 handle_alloc_call (DECL_FUNCTION_CODE (callee
), gsi
);
5177 case BUILT_IN_MEMSET
:
5178 if (handle_builtin_memset (gsi
, zero_write
, ptr_qry
))
5181 case BUILT_IN_MEMCMP
:
5182 if (handle_builtin_memcmp (gsi
))
5185 case BUILT_IN_STRCMP
:
5186 case BUILT_IN_STRNCMP
:
5187 if (handle_builtin_string_cmp (gsi
, ptr_qry
.rvals
))
5191 if (handle_printf_call (gsi
, ptr_qry
))
5199 /* Handle an assignment statement at *GSI to a LHS of integral type.
5200 If GSI's basic block needs clean-up of EH, set *CLEANUP_EH to true. */
5203 handle_integral_assign (gimple_stmt_iterator
*gsi
, bool *cleanup_eh
,
5206 gimple
*stmt
= gsi_stmt (*gsi
);
5207 tree lhs
= gimple_assign_lhs (stmt
);
5208 tree lhs_type
= TREE_TYPE (lhs
);
5210 enum tree_code code
= gimple_assign_rhs_code (stmt
);
5211 if (code
== COND_EXPR
)
5213 tree cond
= gimple_assign_rhs1 (stmt
);
5214 enum tree_code cond_code
= TREE_CODE (cond
);
5216 if (cond_code
== EQ_EXPR
|| cond_code
== NE_EXPR
)
5217 fold_strstr_to_strncmp (TREE_OPERAND (cond
, 0),
5218 TREE_OPERAND (cond
, 1), stmt
);
5220 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
5221 fold_strstr_to_strncmp (gimple_assign_rhs1 (stmt
),
5222 gimple_assign_rhs2 (stmt
), stmt
);
5223 else if (gimple_assign_load_p (stmt
)
5224 && TREE_CODE (lhs_type
) == INTEGER_TYPE
5225 && TYPE_MODE (lhs_type
) == TYPE_MODE (char_type_node
)
5226 && (TYPE_PRECISION (lhs_type
)
5227 == TYPE_PRECISION (char_type_node
))
5228 && !gimple_has_volatile_ops (stmt
))
5230 tree off
= integer_zero_node
;
5231 unsigned HOST_WIDE_INT coff
= 0;
5233 tree rhs1
= gimple_assign_rhs1 (stmt
);
5234 if (code
== MEM_REF
)
5236 idx
= get_stridx (TREE_OPERAND (rhs1
, 0));
5239 strinfo
*si
= get_strinfo (idx
);
5241 && si
->nonzero_chars
5242 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
5243 && (wi::to_widest (si
->nonzero_chars
)
5244 >= wi::to_widest (off
)))
5245 off
= TREE_OPERAND (rhs1
, 1);
5247 /* This case is not useful. See if get_addr_stridx
5248 returns something usable. */
5253 idx
= get_addr_stridx (rhs1
, NULL_TREE
, &coff
);
5256 strinfo
*si
= get_strinfo (idx
);
5258 && si
->nonzero_chars
5259 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
5261 widest_int w1
= wi::to_widest (si
->nonzero_chars
);
5262 widest_int w2
= wi::to_widest (off
) + coff
;
5264 && si
->full_string_p
)
5266 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
5268 fprintf (dump_file
, "Optimizing: ");
5269 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
5272 /* Reading the final '\0' character. */
5273 tree zero
= build_int_cst (lhs_type
, 0);
5274 gimple_set_vuse (stmt
, NULL_TREE
);
5275 gimple_assign_set_rhs_from_tree (gsi
, zero
);
5277 |= maybe_clean_or_replace_eh_stmt (stmt
,
5279 stmt
= gsi_stmt (*gsi
);
5282 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
5284 fprintf (dump_file
, "into: ");
5285 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
5290 /* Reading a character before the final '\0'
5291 character. Just set the value range to ~[0, 0]
5292 if we don't have anything better. */
5294 signop sign
= TYPE_SIGN (lhs_type
);
5295 int prec
= TYPE_PRECISION (lhs_type
);
5296 // FIXME: Use range_query instead of global ranges.
5297 value_range_kind vr
= get_range_info (lhs
, &min
, &max
);
5298 if (vr
== VR_VARYING
5300 && min
== wi::min_value (prec
, sign
)
5301 && max
== wi::max_value (prec
, sign
)))
5302 set_range_info (lhs
, VR_ANTI_RANGE
,
5303 wi::zero (prec
), wi::zero (prec
));
5308 else if (code
== MEM_REF
&& TREE_CODE (lhs
) == SSA_NAME
)
5310 if (int idx
= new_stridx (lhs
))
5312 /* Record multi-byte assignments from MEM_REFs. */
5313 bool storing_all_nonzero_p
;
5314 bool storing_all_zeros_p
;
5316 unsigned lenrange
[] = { UINT_MAX
, 0, 0 };
5317 tree rhs
= gimple_assign_rhs1 (stmt
);
5318 const bool ranges_valid
5319 = count_nonzero_bytes (rhs
, lenrange
, &full_string_p
,
5320 &storing_all_zeros_p
, &storing_all_nonzero_p
,
5324 tree length
= build_int_cst (sizetype
, lenrange
[0]);
5325 strinfo
*si
= new_strinfo (lhs
, idx
, length
, full_string_p
);
5326 set_strinfo (idx
, si
);
5327 si
->writable
= true;
5328 si
->dont_invalidate
= true;
5333 if (strlen_to_stridx
)
5335 tree rhs1
= gimple_assign_rhs1 (stmt
);
5336 if (stridx_strlenloc
*ps
= strlen_to_stridx
->get (rhs1
))
5337 strlen_to_stridx
->put (lhs
, stridx_strlenloc (*ps
));
5341 /* Attempt to check for validity of the performed access a single statement
5342 at *GSI using string length knowledge, and to optimize it.
5343 If the given basic block needs clean-up of EH, CLEANUP_EH is set to
5344 true. Return true to let the caller advance *GSI to the next statement
5345 in the basic block and false otherwise. */
5348 check_and_optimize_stmt (gimple_stmt_iterator
*gsi
, bool *cleanup_eh
,
5349 pointer_query
&ptr_qry
)
5351 gimple
*stmt
= gsi_stmt (*gsi
);
5353 /* For statements that modify a string, set to true if the write
5355 bool zero_write
= false;
5357 if (is_gimple_call (stmt
))
5359 if (!strlen_check_and_optimize_call (gsi
, &zero_write
, ptr_qry
))
5362 else if (!flag_optimize_strlen
|| !strlen_optimize
)
5364 else if (is_gimple_assign (stmt
) && !gimple_clobber_p (stmt
))
5366 /* Handle non-clobbering assignment. */
5367 tree lhs
= gimple_assign_lhs (stmt
);
5368 tree lhs_type
= TREE_TYPE (lhs
);
5370 if (TREE_CODE (lhs
) == SSA_NAME
&& POINTER_TYPE_P (lhs_type
))
5372 if (gimple_assign_single_p (stmt
)
5373 || (gimple_assign_cast_p (stmt
)
5374 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
5376 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
5377 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = idx
;
5379 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
5380 handle_pointer_plus (gsi
);
5382 else if (TREE_CODE (lhs
) == SSA_NAME
&& INTEGRAL_TYPE_P (lhs_type
))
5383 /* Handle assignment to a character. */
5384 handle_integral_assign (gsi
, cleanup_eh
, ptr_qry
.rvals
);
5385 else if (TREE_CODE (lhs
) != SSA_NAME
&& !TREE_SIDE_EFFECTS (lhs
))
5387 tree type
= TREE_TYPE (lhs
);
5388 if (TREE_CODE (type
) == ARRAY_TYPE
)
5389 type
= TREE_TYPE (type
);
5391 bool is_char_store
= is_char_type (type
);
5392 if (!is_char_store
&& TREE_CODE (lhs
) == MEM_REF
)
5394 /* To consider stores into char objects via integer types
5395 other than char but not those to non-character objects,
5396 determine the type of the destination rather than just
5397 the type of the access. */
5398 for (int i
= 0; i
!= 2; ++i
)
5400 tree ref
= TREE_OPERAND (lhs
, i
);
5401 type
= TREE_TYPE (ref
);
5402 if (TREE_CODE (type
) == POINTER_TYPE
)
5403 type
= TREE_TYPE (type
);
5404 if (TREE_CODE (type
) == ARRAY_TYPE
)
5405 type
= TREE_TYPE (type
);
5406 if (is_char_type (type
))
5408 is_char_store
= true;
5414 /* Handle a single or multibyte assignment. */
5415 if (is_char_store
&& !handle_store (gsi
, &zero_write
, ptr_qry
))
5419 else if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
5421 enum tree_code code
= gimple_cond_code (cond
);
5422 if (code
== EQ_EXPR
|| code
== NE_EXPR
)
5423 fold_strstr_to_strncmp (gimple_cond_lhs (stmt
),
5424 gimple_cond_rhs (stmt
), stmt
);
5427 if (gimple_vdef (stmt
))
5428 maybe_invalidate (stmt
, zero_write
);
5432 /* Recursively call maybe_invalidate on stmts that might be executed
5433 in between dombb and current bb and that contain a vdef. Stop when
5434 *count stmts are inspected, or if the whole strinfo vector has
5435 been invalidated. */
5438 do_invalidate (basic_block dombb
, gimple
*phi
, bitmap visited
, int *count
)
5440 unsigned int i
, n
= gimple_phi_num_args (phi
);
5442 for (i
= 0; i
< n
; i
++)
5444 tree vuse
= gimple_phi_arg_def (phi
, i
);
5445 gimple
*stmt
= SSA_NAME_DEF_STMT (vuse
);
5446 basic_block bb
= gimple_bb (stmt
);
5449 || !bitmap_set_bit (visited
, bb
->index
)
5450 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
5454 if (gimple_code (stmt
) == GIMPLE_PHI
)
5456 do_invalidate (dombb
, stmt
, visited
, count
);
5463 if (!maybe_invalidate (stmt
))
5468 vuse
= gimple_vuse (stmt
);
5469 stmt
= SSA_NAME_DEF_STMT (vuse
);
5470 if (gimple_bb (stmt
) != bb
)
5472 bb
= gimple_bb (stmt
);
5475 || !bitmap_set_bit (visited
, bb
->index
)
5476 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
5483 class strlen_dom_walker
: public dom_walker
5486 strlen_dom_walker (cdi_direction direction
)
5487 : dom_walker (direction
),
5489 ptr_qry (&evrp
, &var_cache
),
5491 m_cleanup_cfg (false)
5494 virtual edge
before_dom_children (basic_block
);
5495 virtual void after_dom_children (basic_block
);
5497 /* EVRP analyzer used for printf argument range processing, and
5498 to track strlen results across integer variable assignments. */
5499 evrp_range_analyzer evrp
;
5501 /* A pointer_query object and its cache to store information about
5502 pointers and their targets in. */
5503 pointer_query ptr_qry
;
5504 pointer_query::cache_type var_cache
;
5506 /* Flag that will trigger TODO_cleanup_cfg to be returned in strlen
5507 execute function. */
5511 /* Callback for walk_dominator_tree. Attempt to optimize various
5512 string ops by remembering string lengths pointed by pointer SSA_NAMEs. */
5515 strlen_dom_walker::before_dom_children (basic_block bb
)
5519 basic_block dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
5522 stridx_to_strinfo
= NULL
;
5525 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) dombb
->aux
);
5526 if (stridx_to_strinfo
)
5528 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
5531 gphi
*phi
= gsi
.phi ();
5532 if (virtual_operand_p (gimple_phi_result (phi
)))
5534 bitmap visited
= BITMAP_ALLOC (NULL
);
5535 int count_vdef
= 100;
5536 do_invalidate (dombb
, phi
, visited
, &count_vdef
);
5537 BITMAP_FREE (visited
);
5538 if (count_vdef
== 0)
5540 /* If there were too many vdefs in between immediate
5541 dominator and current bb, invalidate everything.
5542 If stridx_to_strinfo has been unshared, we need
5543 to free it, otherwise just set it to NULL. */
5544 if (!strinfo_shared ())
5550 vec_safe_iterate (stridx_to_strinfo
, i
, &si
);
5554 (*stridx_to_strinfo
)[i
] = NULL
;
5558 stridx_to_strinfo
= NULL
;
5566 /* If all PHI arguments have the same string index, the PHI result
5568 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
5571 gphi
*phi
= gsi
.phi ();
5572 tree result
= gimple_phi_result (phi
);
5573 if (!virtual_operand_p (result
) && POINTER_TYPE_P (TREE_TYPE (result
)))
5575 int idx
= get_stridx (gimple_phi_arg_def (phi
, 0));
5578 unsigned int i
, n
= gimple_phi_num_args (phi
);
5579 for (i
= 1; i
< n
; i
++)
5580 if (idx
!= get_stridx (gimple_phi_arg_def (phi
, i
)))
5583 ssa_ver_to_stridx
[SSA_NAME_VERSION (result
)] = idx
;
5588 bool cleanup_eh
= false;
5590 /* Attempt to optimize individual statements. */
5591 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
5593 gimple
*stmt
= gsi_stmt (gsi
);
5595 /* First record ranges generated by this statement so they
5596 can be used by printf argument processing. */
5597 evrp
.record_ranges_from_stmt (stmt
, false);
5599 /* Reset search depth preformance counter. */
5602 if (check_and_optimize_stmt (&gsi
, &cleanup_eh
, ptr_qry
))
5606 if (cleanup_eh
&& gimple_purge_dead_eh_edges (bb
))
5607 m_cleanup_cfg
= true;
5609 bb
->aux
= stridx_to_strinfo
;
5610 if (vec_safe_length (stridx_to_strinfo
) && !strinfo_shared ())
5611 (*stridx_to_strinfo
)[0] = (strinfo
*) bb
;
5615 /* Callback for walk_dominator_tree. Free strinfo vector if it is
5616 owned by the current bb, clear bb->aux. */
5619 strlen_dom_walker::after_dom_children (basic_block bb
)
5625 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) bb
->aux
);
5626 if (vec_safe_length (stridx_to_strinfo
)
5627 && (*stridx_to_strinfo
)[0] == (strinfo
*) bb
)
5632 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
5634 vec_free (stridx_to_strinfo
);
5643 printf_strlen_execute (function
*fun
, bool warn_only
)
5645 strlen_optimize
= !warn_only
;
5647 calculate_dominance_info (CDI_DOMINATORS
);
5649 bool use_scev
= optimize
> 0 && flag_printf_return_value
;
5652 loop_optimizer_init (LOOPS_NORMAL
);
5656 gcc_assert (!strlen_to_stridx
);
5657 if (warn_stringop_overflow
|| warn_stringop_truncation
)
5658 strlen_to_stridx
= new hash_map
<tree
, stridx_strlenloc
> ();
5660 /* This has to happen after initializing the loop optimizer
5661 and initializing SCEV as they create new SSA_NAMEs. */
5662 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
, true);
5665 /* String length optimization is implemented as a walk of the dominator
5666 tree and a forward walk of statements within each block. */
5667 strlen_dom_walker
walker (CDI_DOMINATORS
);
5668 walker
.walk (ENTRY_BLOCK_PTR_FOR_FN (fun
));
5670 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
5673 unsigned nidxs
= walker
.ptr_qry
.var_cache
->indices
.length ();
5674 for (unsigned i
= 0; i
!= nidxs
; ++i
)
5675 if (walker
.ptr_qry
.var_cache
->indices
[i
])
5678 fprintf (dump_file
, "pointer_query counters\n"
5679 " index cache size: %u\n"
5680 " utilization: %u%%\n"
5681 " access cache size: %u\n"
5687 nidxs
== 0 ? 0 : (nused
* 100) / nidxs
,
5688 walker
.ptr_qry
.var_cache
->access_refs
.length (),
5689 walker
.ptr_qry
.hits
, walker
.ptr_qry
.misses
,
5690 walker
.ptr_qry
.failures
, walker
.ptr_qry
.max_depth
);
5693 ssa_ver_to_stridx
.release ();
5694 strinfo_pool
.release ();
5695 if (decl_to_stridxlist_htab
)
5697 obstack_free (&stridx_obstack
, NULL
);
5698 delete decl_to_stridxlist_htab
;
5699 decl_to_stridxlist_htab
= NULL
;
5701 laststmt
.stmt
= NULL
;
5702 laststmt
.len
= NULL_TREE
;
5703 laststmt
.stridx
= 0;
5705 if (strlen_to_stridx
)
5707 strlen_to_stridx
->empty ();
5708 delete strlen_to_stridx
;
5709 strlen_to_stridx
= NULL
;
5715 loop_optimizer_finalize ();
5718 return walker
.m_cleanup_cfg
? TODO_cleanup_cfg
: 0;
5721 /* This file defines two passes: one for warnings that runs only when
5722 optimization is disabled, and another that implements optimizations
5723 and also issues warnings. */
5725 const pass_data pass_data_warn_printf
=
5727 GIMPLE_PASS
, /* type */
5728 "warn-printf", /* name */
5729 OPTGROUP_NONE
, /* optinfo_flags */
5730 TV_NONE
, /* tv_id */
5731 /* Normally an optimization pass would require PROP_ssa but because
5732 this pass runs early, with no optimization, to do sprintf format
5733 checking, it only requires PROP_cfg. */
5734 PROP_cfg
, /* properties_required */
5735 0, /* properties_provided */
5736 0, /* properties_destroyed */
5737 0, /* todo_flags_start */
5738 0, /* todo_flags_finish */
5741 class pass_warn_printf
: public gimple_opt_pass
5744 pass_warn_printf (gcc::context
*ctxt
)
5745 : gimple_opt_pass (pass_data_warn_printf
, ctxt
)
5748 virtual bool gate (function
*);
5749 virtual unsigned int execute (function
*fun
)
5751 return printf_strlen_execute (fun
, true);
5756 /* Return true to run the warning pass only when not optimizing and
5757 iff either -Wformat-overflow or -Wformat-truncation is specified. */
5760 pass_warn_printf::gate (function
*)
5762 return !optimize
&& (warn_format_overflow
> 0 || warn_format_trunc
> 0);
5765 const pass_data pass_data_strlen
=
5767 GIMPLE_PASS
, /* type */
5768 "strlen", /* name */
5769 OPTGROUP_NONE
, /* optinfo_flags */
5770 TV_TREE_STRLEN
, /* tv_id */
5771 PROP_cfg
| PROP_ssa
, /* properties_required */
5772 0, /* properties_provided */
5773 0, /* properties_destroyed */
5774 0, /* todo_flags_start */
5775 0, /* todo_flags_finish */
5778 class pass_strlen
: public gimple_opt_pass
5781 pass_strlen (gcc::context
*ctxt
)
5782 : gimple_opt_pass (pass_data_strlen
, ctxt
)
5785 opt_pass
* clone () { return new pass_strlen (m_ctxt
); }
5787 virtual bool gate (function
*);
5788 virtual unsigned int execute (function
*fun
)
5790 return printf_strlen_execute (fun
, false);
5794 /* Return true to run the pass only when the sprintf and/or strlen
5795 optimizations are enabled and -Wformat-overflow or -Wformat-truncation
5799 pass_strlen::gate (function
*)
5801 return ((warn_format_overflow
> 0
5802 || warn_format_trunc
> 0
5803 || warn_restrict
> 0
5804 || flag_optimize_strlen
> 0
5805 || flag_printf_return_value
)
5812 make_pass_warn_printf (gcc::context
*ctxt
)
5814 return new pass_warn_printf (ctxt
);
5818 make_pass_strlen (gcc::context
*ctxt
)
5820 return new pass_strlen (ctxt
);