1 /* String length optimization
2 Copyright (C) 2011-2018 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"
50 #include "tree-hash-traits.h"
53 #include "diagnostic-core.h"
54 #include "diagnostic.h"
59 /* A vector indexed by SSA_NAME_VERSION. 0 means unknown, positive value
60 is an index into strinfo vector, negative value stands for
61 string length of a string literal (~strlen). */
62 static vec
<int> ssa_ver_to_stridx
;
64 /* Number of currently active string indexes plus one. */
65 static int max_stridx
;
67 /* String information record. */
70 /* Number of leading characters that are known to be nonzero. This is
71 also the length of the string if FULL_STRING_P.
73 The values in a list of related string pointers must be consistent;
74 that is, if strinfo B comes X bytes after strinfo A, it must be
75 the case that A->nonzero_chars == X + B->nonzero_chars. */
77 /* Any of the corresponding pointers for querying alias oracle. */
79 /* This is used for two things:
81 - To record the statement that should be used for delayed length
82 computations. We maintain the invariant that all related strinfos
83 have delayed lengths or none do.
85 - To record the malloc or calloc call that produced this result. */
87 /* Pointer to '\0' if known, if NULL, it can be computed as
90 /* Reference count. Any changes to strinfo entry possibly shared
91 with dominating basic blocks need unshare_strinfo first, except
92 for dont_invalidate which affects only the immediately next
95 /* Copy of index. get_strinfo (si->idx) should return si; */
97 /* These 3 fields are for chaining related string pointers together.
99 bl = strlen (b); dl = strlen (d); strcpy (a, b); c = a + bl;
100 strcpy (c, d); e = c + dl;
101 strinfo(a) -> strinfo(c) -> strinfo(e)
102 All have ->first field equal to strinfo(a)->idx and are doubly
103 chained through prev/next fields. The later strinfos are required
104 to point into the same string with zero or more bytes after
105 the previous pointer and all bytes in between the two pointers
106 must be non-zero. Functions like strcpy or memcpy are supposed
107 to adjust all previous strinfo lengths, but not following strinfo
108 lengths (those are uncertain, usually invalidated during
109 maybe_invalidate, except when the alias oracle knows better).
110 Functions like strcat on the other side adjust the whole
111 related strinfo chain.
112 They are updated lazily, so to use the chain the same first fields
113 and si->prev->next == si->idx needs to be verified. */
117 /* A flag whether the string is known to be written in the current
120 /* A flag for the next maybe_invalidate that this strinfo shouldn't
121 be invalidated. Always cleared by maybe_invalidate. */
122 bool dont_invalidate
;
123 /* True if the string is known to be nul-terminated after NONZERO_CHARS
124 characters. False is useful when detecting strings that are built
125 up via successive memcpys. */
129 /* Pool for allocating strinfo_struct entries. */
130 static object_allocator
<strinfo
> strinfo_pool ("strinfo pool");
132 /* Vector mapping positive string indexes to strinfo, for the
133 current basic block. The first pointer in the vector is special,
134 it is either NULL, meaning the vector isn't shared, or it is
135 a basic block pointer to the owner basic_block if shared.
136 If some other bb wants to modify the vector, the vector needs
137 to be unshared first, and only the owner bb is supposed to free it. */
138 static vec
<strinfo
*, va_heap
, vl_embed
> *stridx_to_strinfo
;
140 /* One OFFSET->IDX mapping. */
143 struct stridxlist
*next
;
144 HOST_WIDE_INT offset
;
148 /* Hash table entry, mapping a DECL to a chain of OFFSET->IDX mappings. */
149 struct decl_stridxlist_map
151 struct tree_map_base base
;
152 struct stridxlist list
;
155 /* Hash table for mapping decls to a chained list of offset -> idx
157 static hash_map
<tree_decl_hash
, stridxlist
> *decl_to_stridxlist_htab
;
159 /* Hash table mapping strlen calls to stridx instances describing
160 the calls' arguments. Non-null only when warn_stringop_truncation
162 typedef std::pair
<int, location_t
> stridx_strlenloc
;
163 static hash_map
<tree
, stridx_strlenloc
> *strlen_to_stridx
;
165 /* Obstack for struct stridxlist and struct decl_stridxlist_map. */
166 static struct obstack stridx_obstack
;
168 /* Last memcpy statement if it could be adjusted if the trailing
169 '\0' written is immediately overwritten, or
170 *x = '\0' store that could be removed if it is immediately overwritten. */
171 struct laststmt_struct
178 static int get_stridx_plus_constant (strinfo
*, unsigned HOST_WIDE_INT
, tree
);
179 static void handle_builtin_stxncpy (built_in_function
, gimple_stmt_iterator
*);
183 - 1 if SI is known to start with more than OFF nonzero characters.
185 - 0 if SI is known to start with OFF nonzero characters,
186 but is not known to start with more.
188 - -1 if SI might not start with OFF nonzero characters. */
191 compare_nonzero_chars (strinfo
*si
, unsigned HOST_WIDE_INT off
)
193 if (si
->nonzero_chars
194 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
195 return compare_tree_int (si
->nonzero_chars
, off
);
200 /* Return true if SI is known to be a zero-length string. */
203 zero_length_string_p (strinfo
*si
)
205 return si
->full_string_p
&& integer_zerop (si
->nonzero_chars
);
208 /* Return strinfo vector entry IDX. */
210 static inline strinfo
*
211 get_strinfo (int idx
)
213 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
215 return (*stridx_to_strinfo
)[idx
];
218 /* Get the next strinfo in the chain after SI, or null if none. */
220 static inline strinfo
*
221 get_next_strinfo (strinfo
*si
)
225 strinfo
*nextsi
= get_strinfo (si
->next
);
226 if (nextsi
== NULL
|| nextsi
->first
!= si
->first
|| nextsi
->prev
!= si
->idx
)
231 /* Helper function for get_stridx. Return the strinfo index of the address
232 of EXP, which is available in PTR if nonnull. If OFFSET_OUT, it is
233 OK to return the index for some X <= &EXP and store &EXP - X in
237 get_addr_stridx (tree exp
, tree ptr
, unsigned HOST_WIDE_INT
*offset_out
)
240 struct stridxlist
*list
, *last
= NULL
;
243 if (!decl_to_stridxlist_htab
)
247 base
= get_addr_base_and_unit_offset (exp
, &poff
);
248 if (base
== NULL
|| !DECL_P (base
) || !poff
.is_constant (&off
))
251 list
= decl_to_stridxlist_htab
->get (base
);
257 if (list
->offset
== off
)
263 if (list
->offset
> off
)
270 if ((offset_out
|| ptr
) && last
&& last
->idx
> 0)
272 unsigned HOST_WIDE_INT rel_off
273 = (unsigned HOST_WIDE_INT
) off
- last
->offset
;
274 strinfo
*si
= get_strinfo (last
->idx
);
275 if (si
&& compare_nonzero_chars (si
, rel_off
) >= 0)
279 *offset_out
= rel_off
;
283 return get_stridx_plus_constant (si
, rel_off
, ptr
);
289 /* Return string index for EXP. */
292 get_stridx (tree exp
)
296 if (TREE_CODE (exp
) == SSA_NAME
)
298 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)])
299 return ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)];
302 HOST_WIDE_INT off
= 0;
303 for (i
= 0; i
< 5; i
++)
305 gimple
*def_stmt
= SSA_NAME_DEF_STMT (e
);
306 if (!is_gimple_assign (def_stmt
)
307 || gimple_assign_rhs_code (def_stmt
) != POINTER_PLUS_EXPR
)
309 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
310 tree rhs2
= gimple_assign_rhs2 (def_stmt
);
311 if (TREE_CODE (rhs1
) != SSA_NAME
312 || !tree_fits_shwi_p (rhs2
))
314 HOST_WIDE_INT this_off
= tree_to_shwi (rhs2
);
317 off
= (unsigned HOST_WIDE_INT
) off
+ this_off
;
320 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)])
323 = get_strinfo (ssa_ver_to_stridx
[SSA_NAME_VERSION (rhs1
)]);
324 if (si
&& compare_nonzero_chars (si
, off
) >= 0)
325 return get_stridx_plus_constant (si
, off
, exp
);
332 if (TREE_CODE (exp
) == ADDR_EXPR
)
334 int idx
= get_addr_stridx (TREE_OPERAND (exp
, 0), exp
, NULL
);
339 s
= string_constant (exp
, &o
);
341 && (o
== NULL_TREE
|| tree_fits_shwi_p (o
))
342 && TREE_STRING_LENGTH (s
) > 0)
344 HOST_WIDE_INT offset
= o
? tree_to_shwi (o
) : 0;
345 const char *p
= TREE_STRING_POINTER (s
);
346 int max
= TREE_STRING_LENGTH (s
) - 1;
348 if (p
[max
] == '\0' && offset
>= 0 && offset
<= max
)
349 return ~(int) strlen (p
+ offset
);
354 /* Return true if strinfo vector is shared with the immediate dominator. */
357 strinfo_shared (void)
359 return vec_safe_length (stridx_to_strinfo
)
360 && (*stridx_to_strinfo
)[0] != NULL
;
363 /* Unshare strinfo vector that is shared with the immediate dominator. */
366 unshare_strinfo_vec (void)
371 gcc_assert (strinfo_shared ());
372 stridx_to_strinfo
= vec_safe_copy (stridx_to_strinfo
);
373 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
376 (*stridx_to_strinfo
)[0] = NULL
;
379 /* Attempt to create a string index for exp, ADDR_EXPR's operand.
380 Return a pointer to the location where the string index can
381 be stored (if 0) or is stored, or NULL if this can't be tracked. */
384 addr_stridxptr (tree exp
)
389 tree base
= get_addr_base_and_unit_offset (exp
, &poff
);
390 if (base
== NULL_TREE
|| !DECL_P (base
) || !poff
.is_constant (&off
))
393 if (!decl_to_stridxlist_htab
)
395 decl_to_stridxlist_htab
396 = new hash_map
<tree_decl_hash
, stridxlist
> (64);
397 gcc_obstack_init (&stridx_obstack
);
401 stridxlist
*list
= &decl_to_stridxlist_htab
->get_or_insert (base
, &existed
);
405 stridxlist
*before
= NULL
;
406 for (i
= 0; i
< 32; i
++)
408 if (list
->offset
== off
)
410 if (list
->offset
> off
&& before
== NULL
)
412 if (list
->next
== NULL
)
421 before
= XOBNEW (&stridx_obstack
, struct stridxlist
);
428 list
->next
= XOBNEW (&stridx_obstack
, struct stridxlist
);
438 /* Create a new string index, or return 0 if reached limit. */
441 new_stridx (tree exp
)
444 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
446 if (TREE_CODE (exp
) == SSA_NAME
)
448 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp
))
451 ssa_ver_to_stridx
[SSA_NAME_VERSION (exp
)] = idx
;
454 if (TREE_CODE (exp
) == ADDR_EXPR
)
456 int *pidx
= addr_stridxptr (TREE_OPERAND (exp
, 0));
459 gcc_assert (*pidx
== 0);
460 *pidx
= max_stridx
++;
467 /* Like new_stridx, but for ADDR_EXPR's operand instead. */
470 new_addr_stridx (tree exp
)
473 if (max_stridx
>= PARAM_VALUE (PARAM_MAX_TRACKED_STRLENS
))
475 pidx
= addr_stridxptr (exp
);
478 gcc_assert (*pidx
== 0);
479 *pidx
= max_stridx
++;
485 /* Create a new strinfo. */
488 new_strinfo (tree ptr
, int idx
, tree nonzero_chars
, bool full_string_p
)
490 strinfo
*si
= strinfo_pool
.allocate ();
491 si
->nonzero_chars
= nonzero_chars
;
494 si
->endptr
= NULL_TREE
;
500 si
->writable
= false;
501 si
->dont_invalidate
= false;
502 si
->full_string_p
= full_string_p
;
506 /* Decrease strinfo refcount and free it if not referenced anymore. */
509 free_strinfo (strinfo
*si
)
511 if (si
&& --si
->refcount
== 0)
512 strinfo_pool
.remove (si
);
515 /* Set strinfo in the vector entry IDX to SI. */
518 set_strinfo (int idx
, strinfo
*si
)
520 if (vec_safe_length (stridx_to_strinfo
) && (*stridx_to_strinfo
)[0])
521 unshare_strinfo_vec ();
522 if (vec_safe_length (stridx_to_strinfo
) <= (unsigned int) idx
)
523 vec_safe_grow_cleared (stridx_to_strinfo
, idx
+ 1);
524 (*stridx_to_strinfo
)[idx
] = si
;
527 /* Return the first strinfo in the related strinfo chain
528 if all strinfos in between belong to the chain, otherwise NULL. */
531 verify_related_strinfos (strinfo
*origsi
)
533 strinfo
*si
= origsi
, *psi
;
535 if (origsi
->first
== 0)
537 for (; si
->prev
; si
= psi
)
539 if (si
->first
!= origsi
->first
)
541 psi
= get_strinfo (si
->prev
);
544 if (psi
->next
!= si
->idx
)
547 if (si
->idx
!= si
->first
)
552 /* Set SI's endptr to ENDPTR and compute its length based on SI->ptr.
553 Use LOC for folding. */
556 set_endptr_and_length (location_t loc
, strinfo
*si
, tree endptr
)
560 tree start_as_size
= fold_convert_loc (loc
, size_type_node
, si
->ptr
);
561 tree end_as_size
= fold_convert_loc (loc
, size_type_node
, endptr
);
562 si
->nonzero_chars
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
563 end_as_size
, start_as_size
);
564 si
->full_string_p
= true;
567 /* Return string length, or NULL if it can't be computed. */
570 get_string_length (strinfo
*si
)
572 if (si
->nonzero_chars
)
573 return si
->full_string_p
? si
->nonzero_chars
: NULL
;
577 gimple
*stmt
= si
->stmt
, *lenstmt
;
578 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
579 tree callee
, lhs
, fn
, tem
;
581 gimple_stmt_iterator gsi
;
583 gcc_assert (is_gimple_call (stmt
));
584 callee
= gimple_call_fndecl (stmt
);
585 gcc_assert (callee
&& DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
);
586 lhs
= gimple_call_lhs (stmt
);
587 /* unshare_strinfo is intentionally not called here. The (delayed)
588 transformation of strcpy or strcat into stpcpy is done at the place
589 of the former strcpy/strcat call and so can affect all the strinfos
590 with the same stmt. If they were unshared before and transformation
591 has been already done, the handling of BUILT_IN_STPCPY{,_CHK} should
592 just compute the right length. */
593 switch (DECL_FUNCTION_CODE (callee
))
595 case BUILT_IN_STRCAT
:
596 case BUILT_IN_STRCAT_CHK
:
597 case BUILT_IN_STRCAT_CHKP
:
598 case BUILT_IN_STRCAT_CHK_CHKP
:
599 gsi
= gsi_for_stmt (stmt
);
600 fn
= builtin_decl_implicit (BUILT_IN_STRLEN
);
601 gcc_assert (lhs
== NULL_TREE
);
602 tem
= unshare_expr (gimple_call_arg (stmt
, 0));
605 lenstmt
= gimple_build_call (chkp_maybe_create_clone (fn
)->decl
,
606 2, tem
, gimple_call_arg (stmt
, 1));
607 gimple_call_set_with_bounds (lenstmt
, true);
610 lenstmt
= gimple_build_call (fn
, 1, tem
);
611 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), lenstmt
);
612 gimple_call_set_lhs (lenstmt
, lhs
);
613 gimple_set_vuse (lenstmt
, gimple_vuse (stmt
));
614 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
615 tem
= gimple_call_arg (stmt
, 0);
616 if (!ptrofftype_p (TREE_TYPE (lhs
)))
618 lhs
= convert_to_ptrofftype (lhs
);
619 lhs
= force_gimple_operand_gsi (&gsi
, lhs
, true, NULL_TREE
,
620 true, GSI_SAME_STMT
);
622 lenstmt
= gimple_build_assign
623 (make_ssa_name (TREE_TYPE (gimple_call_arg (stmt
, 0))),
624 POINTER_PLUS_EXPR
,tem
, lhs
);
625 gsi_insert_before (&gsi
, lenstmt
, GSI_SAME_STMT
);
626 gimple_call_set_arg (stmt
, 0, gimple_assign_lhs (lenstmt
));
629 case BUILT_IN_STRCPY
:
630 case BUILT_IN_STRCPY_CHK
:
631 case BUILT_IN_STRCPY_CHKP
:
632 case BUILT_IN_STRCPY_CHK_CHKP
:
633 gcc_assert (builtin_decl_implicit_p (BUILT_IN_STPCPY
));
634 if (gimple_call_num_args (stmt
) == (with_bounds
? 4 : 2))
635 fn
= builtin_decl_implicit (BUILT_IN_STPCPY
);
637 fn
= builtin_decl_explicit (BUILT_IN_STPCPY_CHK
);
639 fn
= chkp_maybe_create_clone (fn
)->decl
;
640 gcc_assert (lhs
== NULL_TREE
);
641 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
643 fprintf (dump_file
, "Optimizing: ");
644 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
646 gimple_call_set_fndecl (stmt
, fn
);
647 lhs
= make_ssa_name (TREE_TYPE (TREE_TYPE (fn
)), stmt
);
648 gimple_call_set_lhs (stmt
, lhs
);
650 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
652 fprintf (dump_file
, "into: ");
653 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
656 case BUILT_IN_STPCPY
:
657 case BUILT_IN_STPCPY_CHK
:
658 case BUILT_IN_STPCPY_CHKP
:
659 case BUILT_IN_STPCPY_CHK_CHKP
:
660 gcc_assert (lhs
!= NULL_TREE
);
661 loc
= gimple_location (stmt
);
662 set_endptr_and_length (loc
, si
, lhs
);
663 for (strinfo
*chainsi
= verify_related_strinfos (si
);
665 chainsi
= get_next_strinfo (chainsi
))
666 if (chainsi
->nonzero_chars
== NULL
)
667 set_endptr_and_length (loc
, chainsi
, lhs
);
669 case BUILT_IN_MALLOC
:
671 /* BUILT_IN_CALLOC always has si->nonzero_chars set. */
678 return si
->nonzero_chars
;
681 /* Invalidate string length information for strings whose length
682 might change due to stores in stmt. */
685 maybe_invalidate (gimple
*stmt
)
689 bool nonempty
= false;
691 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
694 if (!si
->dont_invalidate
)
697 /* Do not use si->nonzero_chars. */
698 ao_ref_init_from_ptr_and_size (&r
, si
->ptr
, NULL_TREE
);
699 if (stmt_may_clobber_ref_p_1 (stmt
, &r
))
701 set_strinfo (i
, NULL
);
706 si
->dont_invalidate
= false;
712 /* Unshare strinfo record SI, if it has refcount > 1 or
713 if stridx_to_strinfo vector is shared with some other
717 unshare_strinfo (strinfo
*si
)
721 if (si
->refcount
== 1 && !strinfo_shared ())
724 nsi
= new_strinfo (si
->ptr
, si
->idx
, si
->nonzero_chars
, si
->full_string_p
);
725 nsi
->stmt
= si
->stmt
;
726 nsi
->endptr
= si
->endptr
;
727 nsi
->first
= si
->first
;
728 nsi
->prev
= si
->prev
;
729 nsi
->next
= si
->next
;
730 nsi
->writable
= si
->writable
;
731 set_strinfo (si
->idx
, nsi
);
736 /* Attempt to create a new strinfo for BASESI + OFF, or find existing
737 strinfo if there is any. Return it's idx, or 0 if no strinfo has
741 get_stridx_plus_constant (strinfo
*basesi
, unsigned HOST_WIDE_INT off
,
744 if (TREE_CODE (ptr
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
747 if (compare_nonzero_chars (basesi
, off
) < 0
748 || !tree_fits_uhwi_p (basesi
->nonzero_chars
))
751 unsigned HOST_WIDE_INT nonzero_chars
752 = tree_to_uhwi (basesi
->nonzero_chars
) - off
;
753 strinfo
*si
= basesi
, *chainsi
;
754 if (si
->first
|| si
->prev
|| si
->next
)
755 si
= verify_related_strinfos (basesi
);
757 || si
->nonzero_chars
== NULL_TREE
758 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
761 if (TREE_CODE (ptr
) == SSA_NAME
762 && ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
763 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
765 gcc_checking_assert (compare_tree_int (si
->nonzero_chars
, off
) != -1);
766 for (chainsi
= si
; chainsi
->next
; chainsi
= si
)
768 si
= get_next_strinfo (chainsi
);
770 || si
->nonzero_chars
== NULL_TREE
771 || TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
)
773 int r
= compare_tree_int (si
->nonzero_chars
, nonzero_chars
);
778 if (TREE_CODE (ptr
) == SSA_NAME
)
779 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = si
->idx
;
782 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
783 if (pidx
!= NULL
&& *pidx
== 0)
792 int idx
= new_stridx (ptr
);
795 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, nonzero_chars
),
796 basesi
->full_string_p
);
797 set_strinfo (idx
, si
);
800 strinfo
*nextsi
= unshare_strinfo (get_strinfo (chainsi
->next
));
801 si
->next
= nextsi
->idx
;
804 chainsi
= unshare_strinfo (chainsi
);
805 if (chainsi
->first
== 0)
806 chainsi
->first
= chainsi
->idx
;
808 if (chainsi
->endptr
== NULL_TREE
&& zero_length_string_p (si
))
809 chainsi
->endptr
= ptr
;
810 si
->endptr
= chainsi
->endptr
;
811 si
->prev
= chainsi
->idx
;
812 si
->first
= chainsi
->first
;
813 si
->writable
= chainsi
->writable
;
817 /* Note that PTR, a pointer SSA_NAME initialized in the current stmt, points
818 to a zero-length string and if possible chain it to a related strinfo
819 chain whose part is or might be CHAINSI. */
822 zero_length_string (tree ptr
, strinfo
*chainsi
)
826 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
827 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
828 gcc_checking_assert (TREE_CODE (ptr
) == SSA_NAME
829 && ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] == 0);
831 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr
))
835 si
= verify_related_strinfos (chainsi
);
840 /* We shouldn't mix delayed and non-delayed lengths. */
841 gcc_assert (si
->full_string_p
);
842 if (si
->endptr
== NULL_TREE
)
844 si
= unshare_strinfo (si
);
848 si
= get_next_strinfo (si
);
851 if (zero_length_string_p (chainsi
))
855 chainsi
= unshare_strinfo (chainsi
);
858 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = chainsi
->idx
;
864 /* We shouldn't mix delayed and non-delayed lengths. */
865 gcc_assert (chainsi
->full_string_p
);
866 if (chainsi
->first
|| chainsi
->prev
|| chainsi
->next
)
868 chainsi
= unshare_strinfo (chainsi
);
875 idx
= new_stridx (ptr
);
878 si
= new_strinfo (ptr
, idx
, build_int_cst (size_type_node
, 0), true);
879 set_strinfo (idx
, si
);
883 chainsi
= unshare_strinfo (chainsi
);
884 if (chainsi
->first
== 0)
885 chainsi
->first
= chainsi
->idx
;
887 if (chainsi
->endptr
== NULL_TREE
)
888 chainsi
->endptr
= ptr
;
889 si
->prev
= chainsi
->idx
;
890 si
->first
= chainsi
->first
;
891 si
->writable
= chainsi
->writable
;
896 /* For strinfo ORIGSI whose length has been just updated, adjust other
897 related strinfos so that they match the new ORIGSI. This involves:
899 - adding ADJ to the nonzero_chars fields
900 - copying full_string_p from the new ORIGSI. */
903 adjust_related_strinfos (location_t loc
, strinfo
*origsi
, tree adj
)
905 strinfo
*si
= verify_related_strinfos (origsi
);
918 si
= unshare_strinfo (si
);
919 /* We shouldn't see delayed lengths here; the caller must have
920 calculated the old length in order to calculate the
922 gcc_assert (si
->nonzero_chars
);
923 tem
= fold_convert_loc (loc
, TREE_TYPE (si
->nonzero_chars
), adj
);
924 si
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
925 TREE_TYPE (si
->nonzero_chars
),
926 si
->nonzero_chars
, tem
);
927 si
->full_string_p
= origsi
->full_string_p
;
929 si
->endptr
= NULL_TREE
;
930 si
->dont_invalidate
= true;
932 nsi
= get_next_strinfo (si
);
939 /* Find if there are other SSA_NAME pointers equal to PTR
940 for which we don't track their string lengths yet. If so, use
944 find_equal_ptrs (tree ptr
, int idx
)
946 if (TREE_CODE (ptr
) != SSA_NAME
)
950 gimple
*stmt
= SSA_NAME_DEF_STMT (ptr
);
951 if (!is_gimple_assign (stmt
))
953 ptr
= gimple_assign_rhs1 (stmt
);
954 switch (gimple_assign_rhs_code (stmt
))
959 if (!POINTER_TYPE_P (TREE_TYPE (ptr
)))
961 if (TREE_CODE (ptr
) == SSA_NAME
)
963 if (TREE_CODE (ptr
) != ADDR_EXPR
)
968 int *pidx
= addr_stridxptr (TREE_OPERAND (ptr
, 0));
969 if (pidx
!= NULL
&& *pidx
== 0)
977 /* We might find an endptr created in this pass. Grow the
978 vector in that case. */
979 if (ssa_ver_to_stridx
.length () <= SSA_NAME_VERSION (ptr
))
980 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
982 if (ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] != 0)
984 ssa_ver_to_stridx
[SSA_NAME_VERSION (ptr
)] = idx
;
988 /* Return true if STMT is a call to a builtin function with the right
989 arguments and attributes that should be considered for optimization
993 valid_builtin_call (gimple
*stmt
)
995 if (!gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
))
998 tree callee
= gimple_call_fndecl (stmt
);
999 switch (DECL_FUNCTION_CODE (callee
))
1001 case BUILT_IN_MEMCMP
:
1002 case BUILT_IN_MEMCMP_EQ
:
1003 case BUILT_IN_STRCHR
:
1004 case BUILT_IN_STRCHR_CHKP
:
1005 case BUILT_IN_STRLEN
:
1006 case BUILT_IN_STRLEN_CHKP
:
1007 /* The above functions should be pure. Punt if they aren't. */
1008 if (gimple_vdef (stmt
) || gimple_vuse (stmt
) == NULL_TREE
)
1012 case BUILT_IN_CALLOC
:
1013 case BUILT_IN_MALLOC
:
1014 case BUILT_IN_MEMCPY
:
1015 case BUILT_IN_MEMCPY_CHK
:
1016 case BUILT_IN_MEMCPY_CHKP
:
1017 case BUILT_IN_MEMCPY_CHK_CHKP
:
1018 case BUILT_IN_MEMPCPY
:
1019 case BUILT_IN_MEMPCPY_CHK
:
1020 case BUILT_IN_MEMPCPY_CHKP
:
1021 case BUILT_IN_MEMPCPY_CHK_CHKP
:
1022 case BUILT_IN_MEMSET
:
1023 case BUILT_IN_STPCPY
:
1024 case BUILT_IN_STPCPY_CHK
:
1025 case BUILT_IN_STPCPY_CHKP
:
1026 case BUILT_IN_STPCPY_CHK_CHKP
:
1027 case BUILT_IN_STRCAT
:
1028 case BUILT_IN_STRCAT_CHK
:
1029 case BUILT_IN_STRCAT_CHKP
:
1030 case BUILT_IN_STRCAT_CHK_CHKP
:
1031 case BUILT_IN_STRCPY
:
1032 case BUILT_IN_STRCPY_CHK
:
1033 case BUILT_IN_STRCPY_CHKP
:
1034 case BUILT_IN_STRCPY_CHK_CHKP
:
1035 /* The above functions should be neither const nor pure. Punt if they
1037 if (gimple_vdef (stmt
) == NULL_TREE
|| gimple_vuse (stmt
) == NULL_TREE
)
1048 /* If the last .MEM setter statement before STMT is
1049 memcpy (x, y, strlen (y) + 1), the only .MEM use of it is STMT
1050 and STMT is known to overwrite x[strlen (x)], adjust the last memcpy to
1051 just memcpy (x, y, strlen (y)). SI must be the zero length
1055 adjust_last_stmt (strinfo
*si
, gimple
*stmt
, bool is_strcat
)
1057 tree vuse
, callee
, len
;
1058 struct laststmt_struct last
= laststmt
;
1059 strinfo
*lastsi
, *firstsi
;
1060 unsigned len_arg_no
= 2;
1062 laststmt
.stmt
= NULL
;
1063 laststmt
.len
= NULL_TREE
;
1064 laststmt
.stridx
= 0;
1066 if (last
.stmt
== NULL
)
1069 vuse
= gimple_vuse (stmt
);
1070 if (vuse
== NULL_TREE
1071 || SSA_NAME_DEF_STMT (vuse
) != last
.stmt
1072 || !has_single_use (vuse
))
1075 gcc_assert (last
.stridx
> 0);
1076 lastsi
= get_strinfo (last
.stridx
);
1082 if (lastsi
->first
== 0 || lastsi
->first
!= si
->first
)
1085 firstsi
= verify_related_strinfos (si
);
1086 if (firstsi
== NULL
)
1088 while (firstsi
!= lastsi
)
1090 firstsi
= get_next_strinfo (firstsi
);
1091 if (firstsi
== NULL
)
1096 if (!is_strcat
&& !zero_length_string_p (si
))
1099 if (is_gimple_assign (last
.stmt
))
1101 gimple_stmt_iterator gsi
;
1103 if (!integer_zerop (gimple_assign_rhs1 (last
.stmt
)))
1105 if (stmt_could_throw_p (last
.stmt
))
1107 gsi
= gsi_for_stmt (last
.stmt
);
1108 unlink_stmt_vdef (last
.stmt
);
1109 release_defs (last
.stmt
);
1110 gsi_remove (&gsi
, true);
1114 if (!valid_builtin_call (last
.stmt
))
1117 callee
= gimple_call_fndecl (last
.stmt
);
1118 switch (DECL_FUNCTION_CODE (callee
))
1120 case BUILT_IN_MEMCPY
:
1121 case BUILT_IN_MEMCPY_CHK
:
1123 case BUILT_IN_MEMCPY_CHKP
:
1124 case BUILT_IN_MEMCPY_CHK_CHKP
:
1131 len
= gimple_call_arg (last
.stmt
, len_arg_no
);
1132 if (tree_fits_uhwi_p (len
))
1134 if (!tree_fits_uhwi_p (last
.len
)
1135 || integer_zerop (len
)
1136 || tree_to_uhwi (len
) != tree_to_uhwi (last
.len
) + 1)
1138 /* Don't adjust the length if it is divisible by 4, it is more efficient
1139 to store the extra '\0' in that case. */
1140 if ((tree_to_uhwi (len
) & 3) == 0)
1143 else if (TREE_CODE (len
) == SSA_NAME
)
1145 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1146 if (!is_gimple_assign (def_stmt
)
1147 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
1148 || gimple_assign_rhs1 (def_stmt
) != last
.len
1149 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
1155 gimple_call_set_arg (last
.stmt
, len_arg_no
, last
.len
);
1156 update_stmt (last
.stmt
);
1159 /* For an LHS that is an SSA_NAME and for strlen() argument SRC, set
1160 LHS range info to [0, N] if SRC refers to a character array A[N]
1161 with unknown length bounded by N. */
1164 maybe_set_strlen_range (tree lhs
, tree src
)
1166 if (TREE_CODE (lhs
) != SSA_NAME
)
1169 if (TREE_CODE (src
) == SSA_NAME
)
1171 gimple
*def
= SSA_NAME_DEF_STMT (src
);
1172 if (is_gimple_assign (def
)
1173 && gimple_assign_rhs_code (def
) == ADDR_EXPR
)
1174 src
= gimple_assign_rhs1 (def
);
1177 if (TREE_CODE (src
) != ADDR_EXPR
)
1180 /* The last array member of a struct can be bigger than its size
1181 suggests if it's treated as a poor-man's flexible array member. */
1182 src
= TREE_OPERAND (src
, 0);
1183 if (TREE_CODE (TREE_TYPE (src
)) != ARRAY_TYPE
1184 || array_at_struct_end_p (src
))
1187 tree type
= TREE_TYPE (src
);
1188 if (tree dom
= TYPE_DOMAIN (type
))
1189 if (tree maxval
= TYPE_MAX_VALUE (dom
))
1191 wide_int max
= wi::to_wide (maxval
);
1192 wide_int min
= wi::zero (max
.get_precision ());
1193 set_range_info (lhs
, VR_RANGE
, min
, max
);
1197 /* Handle a strlen call. If strlen of the argument is known, replace
1198 the strlen call with the known value, otherwise remember that strlen
1199 of the argument is stored in the lhs SSA_NAME. */
1202 handle_builtin_strlen (gimple_stmt_iterator
*gsi
)
1206 gimple
*stmt
= gsi_stmt (*gsi
);
1207 tree lhs
= gimple_call_lhs (stmt
);
1209 if (lhs
== NULL_TREE
)
1212 src
= gimple_call_arg (stmt
, 0);
1213 idx
= get_stridx (src
);
1220 rhs
= build_int_cst (TREE_TYPE (lhs
), ~idx
);
1224 si
= get_strinfo (idx
);
1226 rhs
= get_string_length (si
);
1228 if (rhs
!= NULL_TREE
)
1230 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1232 fprintf (dump_file
, "Optimizing: ");
1233 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1235 rhs
= unshare_expr (rhs
);
1236 if (!useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (rhs
)))
1237 rhs
= fold_convert_loc (gimple_location (stmt
),
1238 TREE_TYPE (lhs
), rhs
);
1239 if (!update_call_from_tree (gsi
, rhs
))
1240 gimplify_and_update_call_from_tree (gsi
, rhs
);
1241 stmt
= gsi_stmt (*gsi
);
1243 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1245 fprintf (dump_file
, "into: ");
1246 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1249 && TREE_CODE (si
->nonzero_chars
) != SSA_NAME
1250 && TREE_CODE (si
->nonzero_chars
) != INTEGER_CST
1251 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1253 si
= unshare_strinfo (si
);
1254 si
->nonzero_chars
= lhs
;
1255 gcc_assert (si
->full_string_p
);
1258 if (strlen_to_stridx
)
1260 location_t loc
= gimple_location (stmt
);
1261 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1266 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1269 idx
= new_stridx (src
);
1272 strinfo
*si
= get_strinfo (idx
);
1275 if (!si
->full_string_p
&& !si
->stmt
)
1277 /* Until now we only had a lower bound on the string length.
1278 Install LHS as the actual length. */
1279 si
= unshare_strinfo (si
);
1280 tree old
= si
->nonzero_chars
;
1281 si
->nonzero_chars
= lhs
;
1282 si
->full_string_p
= true;
1283 if (TREE_CODE (old
) == INTEGER_CST
)
1285 location_t loc
= gimple_location (stmt
);
1286 old
= fold_convert_loc (loc
, TREE_TYPE (lhs
), old
);
1287 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1288 TREE_TYPE (lhs
), lhs
, old
);
1289 adjust_related_strinfos (loc
, si
, adj
);
1303 strinfo
*si
= new_strinfo (src
, idx
, lhs
, true);
1304 set_strinfo (idx
, si
);
1305 find_equal_ptrs (src
, idx
);
1307 /* For SRC that is an array of N elements, set LHS's range
1309 maybe_set_strlen_range (lhs
, src
);
1311 if (strlen_to_stridx
)
1313 location_t loc
= gimple_location (stmt
);
1314 strlen_to_stridx
->put (lhs
, stridx_strlenloc (idx
, loc
));
1319 /* Handle a strchr call. If strlen of the first argument is known, replace
1320 the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
1321 that lhs of the call is endptr and strlen of the argument is endptr - x. */
1324 handle_builtin_strchr (gimple_stmt_iterator
*gsi
)
1328 gimple
*stmt
= gsi_stmt (*gsi
);
1329 tree lhs
= gimple_call_lhs (stmt
);
1330 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1332 if (lhs
== NULL_TREE
)
1335 if (!integer_zerop (gimple_call_arg (stmt
, with_bounds
? 2 : 1)))
1338 src
= gimple_call_arg (stmt
, 0);
1339 idx
= get_stridx (src
);
1346 rhs
= build_int_cst (size_type_node
, ~idx
);
1350 si
= get_strinfo (idx
);
1352 rhs
= get_string_length (si
);
1354 if (rhs
!= NULL_TREE
)
1356 location_t loc
= gimple_location (stmt
);
1358 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1360 fprintf (dump_file
, "Optimizing: ");
1361 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1363 if (si
!= NULL
&& si
->endptr
!= NULL_TREE
)
1365 rhs
= unshare_expr (si
->endptr
);
1366 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1368 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1372 rhs
= fold_convert_loc (loc
, sizetype
, unshare_expr (rhs
));
1373 rhs
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
1374 TREE_TYPE (src
), src
, rhs
);
1375 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
1377 rhs
= fold_convert_loc (loc
, TREE_TYPE (lhs
), rhs
);
1379 if (!update_call_from_tree (gsi
, rhs
))
1380 gimplify_and_update_call_from_tree (gsi
, rhs
);
1381 stmt
= gsi_stmt (*gsi
);
1383 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1385 fprintf (dump_file
, "into: ");
1386 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1389 && si
->endptr
== NULL_TREE
1390 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1392 si
= unshare_strinfo (si
);
1395 zero_length_string (lhs
, si
);
1399 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
1401 if (TREE_CODE (src
) != SSA_NAME
|| !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src
))
1404 idx
= new_stridx (src
);
1405 else if (get_strinfo (idx
) != NULL
)
1407 zero_length_string (lhs
, NULL
);
1412 location_t loc
= gimple_location (stmt
);
1413 tree lhsu
= fold_convert_loc (loc
, size_type_node
, lhs
);
1414 tree srcu
= fold_convert_loc (loc
, size_type_node
, src
);
1415 tree length
= fold_build2_loc (loc
, MINUS_EXPR
,
1416 size_type_node
, lhsu
, srcu
);
1417 strinfo
*si
= new_strinfo (src
, idx
, length
, true);
1419 set_strinfo (idx
, si
);
1420 find_equal_ptrs (src
, idx
);
1421 zero_length_string (lhs
, si
);
1425 zero_length_string (lhs
, NULL
);
1428 /* Handle a strcpy-like ({st{r,p}cpy,__st{r,p}cpy_chk}) call.
1429 If strlen of the second argument is known, strlen of the first argument
1430 is the same after this call. Furthermore, attempt to convert it to
1434 handle_builtin_strcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1437 tree src
, dst
, srclen
, len
, lhs
, type
, fn
, oldlen
;
1439 gimple
*stmt
= gsi_stmt (*gsi
);
1440 strinfo
*si
, *dsi
, *olddsi
, *zsi
;
1442 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
1444 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
1445 dst
= gimple_call_arg (stmt
, 0);
1446 lhs
= gimple_call_lhs (stmt
);
1447 idx
= get_stridx (src
);
1450 si
= get_strinfo (idx
);
1452 didx
= get_stridx (dst
);
1456 olddsi
= get_strinfo (didx
);
1461 adjust_last_stmt (olddsi
, stmt
, false);
1465 srclen
= get_string_length (si
);
1467 srclen
= build_int_cst (size_type_node
, ~idx
);
1469 loc
= gimple_location (stmt
);
1470 if (srclen
== NULL_TREE
)
1473 case BUILT_IN_STRCPY
:
1474 case BUILT_IN_STRCPY_CHK
:
1475 case BUILT_IN_STRCPY_CHKP
:
1476 case BUILT_IN_STRCPY_CHK_CHKP
:
1477 if (lhs
!= NULL_TREE
|| !builtin_decl_implicit_p (BUILT_IN_STPCPY
))
1480 case BUILT_IN_STPCPY
:
1481 case BUILT_IN_STPCPY_CHK
:
1482 case BUILT_IN_STPCPY_CHKP
:
1483 case BUILT_IN_STPCPY_CHK_CHKP
:
1484 if (lhs
== NULL_TREE
)
1488 tree lhsuint
= fold_convert_loc (loc
, size_type_node
, lhs
);
1489 srclen
= fold_convert_loc (loc
, size_type_node
, dst
);
1490 srclen
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
1500 didx
= new_stridx (dst
);
1506 oldlen
= olddsi
->nonzero_chars
;
1507 dsi
= unshare_strinfo (olddsi
);
1508 dsi
->nonzero_chars
= srclen
;
1509 dsi
->full_string_p
= (srclen
!= NULL_TREE
);
1510 /* Break the chain, so adjust_related_strinfo on later pointers in
1511 the chain won't adjust this one anymore. */
1514 dsi
->endptr
= NULL_TREE
;
1518 dsi
= new_strinfo (dst
, didx
, srclen
, srclen
!= NULL_TREE
);
1519 set_strinfo (didx
, dsi
);
1520 find_equal_ptrs (dst
, didx
);
1522 dsi
->writable
= true;
1523 dsi
->dont_invalidate
= true;
1525 if (dsi
->nonzero_chars
== NULL_TREE
)
1529 /* If string length of src is unknown, use delayed length
1530 computation. If string lenth of dst will be needed, it
1531 can be computed by transforming this strcpy call into
1532 stpcpy and subtracting dst from the return value. */
1534 /* Look for earlier strings whose length could be determined if
1535 this strcpy is turned into an stpcpy. */
1537 if (dsi
->prev
!= 0 && (chainsi
= verify_related_strinfos (dsi
)) != NULL
)
1539 for (; chainsi
&& chainsi
!= dsi
; chainsi
= get_strinfo (chainsi
->next
))
1541 /* When setting a stmt for delayed length computation
1542 prevent all strinfos through dsi from being
1544 chainsi
= unshare_strinfo (chainsi
);
1545 chainsi
->stmt
= stmt
;
1546 chainsi
->nonzero_chars
= NULL_TREE
;
1547 chainsi
->full_string_p
= false;
1548 chainsi
->endptr
= NULL_TREE
;
1549 chainsi
->dont_invalidate
= true;
1554 /* Try to detect overlap before returning. This catches cases
1555 like strcpy (d, d + n) where n is non-constant whose range
1556 is such that (n <= strlen (d) holds).
1558 OLDDSI->NONZERO_chars may have been reset by this point with
1559 oldlen holding it original value. */
1560 if (olddsi
&& oldlen
)
1562 /* Add 1 for the terminating NUL. */
1563 tree type
= TREE_TYPE (oldlen
);
1564 oldlen
= fold_build2 (PLUS_EXPR
, type
, oldlen
,
1565 build_int_cst (type
, 1));
1566 check_bounds_or_overlap (as_a
<gcall
*>(stmt
), olddsi
->ptr
, src
,
1575 tree adj
= NULL_TREE
;
1576 if (oldlen
== NULL_TREE
)
1578 else if (integer_zerop (oldlen
))
1580 else if (TREE_CODE (oldlen
) == INTEGER_CST
1581 || TREE_CODE (srclen
) == INTEGER_CST
)
1582 adj
= fold_build2_loc (loc
, MINUS_EXPR
,
1583 TREE_TYPE (srclen
), srclen
,
1584 fold_convert_loc (loc
, TREE_TYPE (srclen
),
1586 if (adj
!= NULL_TREE
)
1587 adjust_related_strinfos (loc
, dsi
, adj
);
1591 /* strcpy src may not overlap dst, so src doesn't need to be
1592 invalidated either. */
1594 si
->dont_invalidate
= true;
1600 case BUILT_IN_STRCPY
:
1601 case BUILT_IN_STRCPY_CHKP
:
1602 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
1604 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1606 case BUILT_IN_STRCPY_CHK
:
1607 case BUILT_IN_STRCPY_CHK_CHKP
:
1608 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
1610 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
1612 case BUILT_IN_STPCPY
:
1613 case BUILT_IN_STPCPY_CHKP
:
1614 /* This would need adjustment of the lhs (subtract one),
1615 or detection that the trailing '\0' doesn't need to be
1616 written, if it will be immediately overwritten.
1617 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY); */
1621 zsi
= zero_length_string (lhs
, dsi
);
1624 case BUILT_IN_STPCPY_CHK
:
1625 case BUILT_IN_STPCPY_CHK_CHKP
:
1626 /* This would need adjustment of the lhs (subtract one),
1627 or detection that the trailing '\0' doesn't need to be
1628 written, if it will be immediately overwritten.
1629 fn = builtin_decl_explicit (BUILT_IN_MEMPCPY_CHK); */
1633 zsi
= zero_length_string (lhs
, dsi
);
1640 zsi
->dont_invalidate
= true;
1644 tree args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
1645 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
1648 type
= size_type_node
;
1650 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
1651 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
, build_int_cst (type
, 1));
1653 /* Set the no-warning bit on the transformed statement? */
1654 bool set_no_warning
= false;
1656 if (const strinfo
*chksi
= olddsi
? olddsi
: dsi
)
1658 && !check_bounds_or_overlap (as_a
<gcall
*>(stmt
), chksi
->ptr
, si
->ptr
,
1661 gimple_set_no_warning (stmt
, true);
1662 set_no_warning
= true;
1665 if (fn
== NULL_TREE
)
1668 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
1670 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1672 fprintf (dump_file
, "Optimizing: ");
1673 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1677 fn
= chkp_maybe_create_clone (fn
)->decl
;
1678 if (gimple_call_num_args (stmt
) == 4)
1679 success
= update_gimple_call (gsi
, fn
, 5, dst
,
1680 gimple_call_arg (stmt
, 1),
1682 gimple_call_arg (stmt
, 3),
1685 success
= update_gimple_call (gsi
, fn
, 6, dst
,
1686 gimple_call_arg (stmt
, 1),
1688 gimple_call_arg (stmt
, 3),
1690 gimple_call_arg (stmt
, 4));
1693 if (gimple_call_num_args (stmt
) == 2)
1694 success
= update_gimple_call (gsi
, fn
, 3, dst
, src
, len
);
1696 success
= update_gimple_call (gsi
, fn
, 4, dst
, src
, len
,
1697 gimple_call_arg (stmt
, 2));
1700 stmt
= gsi_stmt (*gsi
);
1701 gimple_call_set_with_bounds (stmt
, with_bounds
);
1703 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1705 fprintf (dump_file
, "into: ");
1706 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1708 /* Allow adjust_last_stmt to decrease this memcpy's size. */
1709 laststmt
.stmt
= stmt
;
1710 laststmt
.len
= srclen
;
1711 laststmt
.stridx
= dsi
->idx
;
1713 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
1714 fprintf (dump_file
, "not possible.\n");
1717 gimple_set_no_warning (stmt
, true);
1720 /* Check the size argument to the built-in forms of stpncpy and strncpy
1721 for out-of-bounds offsets or overlapping access, and to see if the
1722 size argument is derived from a call to strlen() on the source argument,
1723 and if so, issue an appropriate warning. */
1726 handle_builtin_strncat (built_in_function bcode
, gimple_stmt_iterator
*gsi
)
1728 /* Same as stxncpy(). */
1729 handle_builtin_stxncpy (bcode
, gsi
);
1732 /* Return true if LEN depends on a call to strlen(SRC) in an interesting
1733 way. LEN can either be an integer expression, or a pointer (to char).
1734 When it is the latter (such as in recursive calls to self) is is
1735 assumed to be the argument in some call to strlen() whose relationship
1736 to SRC is being ascertained. */
1739 is_strlen_related_p (tree src
, tree len
)
1741 if (TREE_CODE (TREE_TYPE (len
)) == POINTER_TYPE
1742 && operand_equal_p (src
, len
, 0))
1745 if (TREE_CODE (len
) != SSA_NAME
)
1748 gimple
*def_stmt
= SSA_NAME_DEF_STMT (len
);
1752 if (is_gimple_call (def_stmt
))
1754 tree func
= gimple_call_fndecl (def_stmt
);
1755 if (!valid_builtin_call (def_stmt
)
1756 || DECL_FUNCTION_CODE (func
) != BUILT_IN_STRLEN
)
1759 tree arg
= gimple_call_arg (def_stmt
, 0);
1760 return is_strlen_related_p (src
, arg
);
1763 if (!is_gimple_assign (def_stmt
))
1766 tree_code code
= gimple_assign_rhs_code (def_stmt
);
1767 tree rhs1
= gimple_assign_rhs1 (def_stmt
);
1768 tree rhstype
= TREE_TYPE (rhs1
);
1770 if ((TREE_CODE (rhstype
) == POINTER_TYPE
&& code
== POINTER_PLUS_EXPR
)
1771 || (INTEGRAL_TYPE_P (rhstype
)
1772 && (code
== BIT_AND_EXPR
1773 || code
== NOP_EXPR
)))
1775 /* Pointer plus (an integer) and integer cast or truncation are
1776 considered among the (potentially) related expressions to strlen.
1778 return is_strlen_related_p (src
, rhs1
);
1784 /* Called by handle_builtin_stxncpy and by gimple_fold_builtin_strncpy
1786 Check to see if the specified bound is a) equal to the size of
1787 the destination DST and if so, b) if it's immediately followed by
1788 DST[CNT - 1] = '\0'. If a) holds and b) does not, warn. Otherwise,
1789 do nothing. Return true if diagnostic has been issued.
1791 The purpose is to diagnose calls to strncpy and stpncpy that do
1792 not nul-terminate the copy while allowing for the idiom where
1793 such a call is immediately followed by setting the last element
1796 strncpy (a, s, sizeof a);
1797 a[sizeof a - 1] = '\0';
1801 maybe_diag_stxncpy_trunc (gimple_stmt_iterator gsi
, tree src
, tree cnt
)
1803 gimple
*stmt
= gsi_stmt (gsi
);
1805 wide_int cntrange
[2];
1807 if (TREE_CODE (cnt
) == INTEGER_CST
)
1808 cntrange
[0] = cntrange
[1] = wi::to_wide (cnt
);
1809 else if (TREE_CODE (cnt
) == SSA_NAME
)
1811 enum value_range_type rng
= get_range_info (cnt
, cntrange
, cntrange
+ 1);
1812 if (rng
== VR_RANGE
)
1814 else if (rng
== VR_ANTI_RANGE
)
1816 wide_int maxobjsize
= wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node
));
1818 if (wi::ltu_p (cntrange
[1], maxobjsize
))
1820 cntrange
[0] = cntrange
[1] + 1;
1821 cntrange
[1] = maxobjsize
;
1825 cntrange
[1] = cntrange
[0] - 1;
1826 cntrange
[0] = wi::zero (TYPE_PRECISION (TREE_TYPE (cnt
)));
1835 /* Negative value is the constant string length. If it's less than
1836 the lower bound there is no truncation. Avoid calling get_stridx()
1837 when ssa_ver_to_stridx is empty. That implies the caller isn't
1838 running under the control of this pass and ssa_ver_to_stridx hasn't
1839 been created yet. */
1840 int sidx
= ssa_ver_to_stridx
.length () ? get_stridx (src
) : 0;
1841 if (sidx
< 0 && wi::gtu_p (cntrange
[0], ~sidx
))
1844 tree dst
= gimple_call_arg (stmt
, 0);
1846 if (TREE_CODE (dstdecl
) == ADDR_EXPR
)
1847 dstdecl
= TREE_OPERAND (dstdecl
, 0);
1849 /* If the destination refers to a an array/pointer declared nonstring
1851 tree ref
= NULL_TREE
;
1852 if (get_attr_nonstring_decl (dstdecl
, &ref
))
1855 /* Look for dst[i] = '\0'; after the stxncpy() call and if found
1856 avoid the truncation warning. */
1857 gsi_next_nondebug (&gsi
);
1858 gimple
*next_stmt
= gsi_stmt (gsi
);
1860 if (!gsi_end_p (gsi
) && is_gimple_assign (next_stmt
))
1862 tree lhs
= gimple_assign_lhs (next_stmt
);
1863 tree_code code
= TREE_CODE (lhs
);
1864 if (code
== ARRAY_REF
|| code
== MEM_REF
)
1865 lhs
= TREE_OPERAND (lhs
, 0);
1867 tree func
= gimple_call_fndecl (stmt
);
1868 if (DECL_FUNCTION_CODE (func
) == BUILT_IN_STPNCPY
)
1870 tree ret
= gimple_call_lhs (stmt
);
1871 if (ret
&& operand_equal_p (ret
, lhs
, 0))
1875 /* Determine the base address and offset of the reference,
1876 ignoring the innermost array index. */
1877 if (TREE_CODE (ref
) == ARRAY_REF
)
1878 ref
= TREE_OPERAND (ref
, 0);
1881 tree dstbase
= get_addr_base_and_unit_offset (ref
, &dstoff
);
1884 tree lhsbase
= get_addr_base_and_unit_offset (lhs
, &lhsoff
);
1887 && known_eq (dstoff
, lhsoff
)
1888 && operand_equal_p (dstbase
, lhsbase
, 0))
1892 int prec
= TYPE_PRECISION (TREE_TYPE (cnt
));
1893 wide_int lenrange
[2];
1894 if (strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
)
1896 lenrange
[0] = (sisrc
->nonzero_chars
1897 && TREE_CODE (sisrc
->nonzero_chars
) == INTEGER_CST
1898 ? wi::to_wide (sisrc
->nonzero_chars
)
1900 lenrange
[1] = lenrange
[0];
1903 lenrange
[0] = lenrange
[1] = wi::shwi (~sidx
, prec
);
1907 get_range_strlen (src
, range
);
1908 if (range
[0] != NULL_TREE
1909 && TREE_CODE (range
[0]) == INTEGER_CST
1910 && range
[1] != NULL_TREE
1911 && TREE_CODE (range
[1]) == INTEGER_CST
)
1913 lenrange
[0] = wi::to_wide (range
[0], prec
);
1914 lenrange
[1] = wi::to_wide (range
[1], prec
);
1918 lenrange
[0] = wi::shwi (0, prec
);
1919 lenrange
[1] = wi::shwi (-1, prec
);
1923 location_t callloc
= gimple_location (stmt
);
1924 tree func
= gimple_call_fndecl (stmt
);
1926 if (lenrange
[0] != 0 || !wi::neg_p (lenrange
[1]))
1928 /* If the longest source string is shorter than the lower bound
1929 of the specified count the copy is definitely nul-terminated. */
1930 if (wi::ltu_p (lenrange
[1], cntrange
[0]))
1933 if (wi::neg_p (lenrange
[1]))
1935 /* The length of one of the strings is unknown but at least
1936 one has non-zero length and that length is stored in
1937 LENRANGE[1]. Swap the bounds to force a "may be truncated"
1939 lenrange
[1] = lenrange
[0];
1940 lenrange
[0] = wi::shwi (0, prec
);
1943 gcall
*call
= as_a
<gcall
*> (stmt
);
1945 if (lenrange
[0] == cntrange
[1] && cntrange
[0] == cntrange
[1])
1946 return warning_n (callloc
, OPT_Wstringop_truncation
,
1947 cntrange
[0].to_uhwi (),
1948 "%G%qD output truncated before terminating "
1949 "nul copying %E byte from a string of the "
1951 "%G%qD output truncated before terminating nul "
1952 "copying %E bytes from a string of the same "
1955 else if (wi::geu_p (lenrange
[0], cntrange
[1]))
1957 /* The shortest string is longer than the upper bound of
1958 the count so the truncation is certain. */
1959 if (cntrange
[0] == cntrange
[1])
1960 return warning_n (callloc
, OPT_Wstringop_truncation
,
1961 cntrange
[0].to_uhwi (),
1962 "%G%qD output truncated copying %E byte "
1963 "from a string of length %wu",
1964 "%G%qD output truncated copying %E bytes "
1965 "from a string of length %wu",
1966 call
, func
, cnt
, lenrange
[0].to_uhwi ());
1968 return warning_at (callloc
, OPT_Wstringop_truncation
,
1969 "%G%qD output truncated copying between %wu "
1970 "and %wu bytes from a string of length %wu",
1971 call
, func
, cntrange
[0].to_uhwi (),
1972 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
1974 else if (wi::geu_p (lenrange
[1], cntrange
[1]))
1976 /* The longest string is longer than the upper bound of
1977 the count so the truncation is possible. */
1978 if (cntrange
[0] == cntrange
[1])
1979 return warning_n (callloc
, OPT_Wstringop_truncation
,
1980 cntrange
[0].to_uhwi (),
1981 "%G%qD output may be truncated copying %E "
1982 "byte from a string of length %wu",
1983 "%G%qD output may be truncated copying %E "
1984 "bytes from a string of length %wu",
1985 call
, func
, cnt
, lenrange
[1].to_uhwi ());
1987 return warning_at (callloc
, OPT_Wstringop_truncation
,
1988 "%G%qD output may be truncated copying between %wu "
1989 "and %wu bytes from a string of length %wu",
1990 call
, func
, cntrange
[0].to_uhwi (),
1991 cntrange
[1].to_uhwi (), lenrange
[1].to_uhwi ());
1994 if (cntrange
[0] != cntrange
[1]
1995 && wi::leu_p (cntrange
[0], lenrange
[0])
1996 && wi::leu_p (cntrange
[1], lenrange
[0] + 1))
1998 /* If the source (including the terminating nul) is longer than
1999 the lower bound of the specified count but shorter than the
2000 upper bound the copy may (but need not) be truncated. */
2001 return warning_at (callloc
, OPT_Wstringop_truncation
,
2002 "%G%qD output may be truncated copying between "
2003 "%wu and %wu bytes from a string of length %wu",
2004 call
, func
, cntrange
[0].to_uhwi (),
2005 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
2009 if (tree dstsize
= compute_objsize (dst
, 1))
2011 /* The source length is uknown. Try to determine the destination
2012 size and see if it matches the specified bound. If not, bail.
2013 Otherwise go on to see if it should be diagnosed for possible
2018 if (wi::to_wide (dstsize
) != cntrange
[1])
2021 if (cntrange
[0] == cntrange
[1])
2022 return warning_at (callloc
, OPT_Wstringop_truncation
,
2023 "%G%qD specified bound %E equals destination size",
2024 as_a
<gcall
*> (stmt
), func
, cnt
);
2030 /* Check the arguments to the built-in forms of stpncpy and strncpy for
2031 out-of-bounds offsets or overlapping access, and to see if the size
2032 is derived from calling strlen() on the source argument, and if so,
2033 issue the appropriate warning. */
2036 handle_builtin_stxncpy (built_in_function
, gimple_stmt_iterator
*gsi
)
2038 if (!strlen_to_stridx
)
2041 gimple
*stmt
= gsi_stmt (*gsi
);
2043 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
2045 tree dst
= gimple_call_arg (stmt
, with_bounds
? 1 : 0);
2046 tree src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
2047 tree len
= gimple_call_arg (stmt
, with_bounds
? 3 : 2);
2048 tree dstsize
= NULL_TREE
, srcsize
= NULL_TREE
;
2050 int didx
= get_stridx (dst
);
2051 if (strinfo
*sidst
= didx
> 0 ? get_strinfo (didx
) : NULL
)
2053 /* Compute the size of the destination string including the NUL. */
2054 if (sidst
->nonzero_chars
)
2056 tree type
= TREE_TYPE (sidst
->nonzero_chars
);
2057 dstsize
= fold_build2 (PLUS_EXPR
, type
, sidst
->nonzero_chars
,
2058 build_int_cst (type
, 1));
2063 int sidx
= get_stridx (src
);
2064 strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
;
2067 /* strncat() and strncpy() can modify the source string by writing
2068 over the terminating nul so SISRC->DONT_INVALIDATE must be left
2071 /* Compute the size of the source string including the NUL. */
2072 if (sisrc
->nonzero_chars
)
2074 tree type
= TREE_TYPE (sisrc
->nonzero_chars
);
2075 srcsize
= fold_build2 (PLUS_EXPR
, type
, sisrc
->nonzero_chars
,
2076 build_int_cst (type
, 1));
2082 srcsize
= NULL_TREE
;
2084 if (!check_bounds_or_overlap (as_a
<gcall
*>(stmt
), dst
, src
,
2087 gimple_set_no_warning (stmt
, true);
2091 /* If the length argument was computed from strlen(S) for some string
2092 S retrieve the strinfo index for the string (PSS->FIRST) alonng with
2093 the location of the strlen() call (PSS->SECOND). */
2094 stridx_strlenloc
*pss
= strlen_to_stridx
->get (len
);
2095 if (!pss
|| pss
->first
<= 0)
2097 if (maybe_diag_stxncpy_trunc (*gsi
, src
, len
))
2098 gimple_set_no_warning (stmt
, true);
2103 /* Retrieve the strinfo data for the string S that LEN was computed
2104 from as some function F of strlen (S) (i.e., LEN need not be equal
2106 strinfo
*silen
= get_strinfo (pss
->first
);
2108 location_t callloc
= gimple_location (stmt
);
2110 tree func
= gimple_call_fndecl (stmt
);
2112 bool warned
= false;
2114 /* When -Wstringop-truncation is set, try to determine truncation
2115 before diagnosing possible overflow. Truncation is implied by
2116 the LEN argument being equal to strlen(SRC), regardless of
2117 whether its value is known. Otherwise, issue the more generic
2118 -Wstringop-overflow which triggers for LEN arguments that in
2119 any meaningful way depend on strlen(SRC). */
2121 && is_strlen_related_p (src
, len
)
2122 && warning_at (callloc
, OPT_Wstringop_truncation
,
2123 "%G%qD output truncated before terminating nul "
2124 "copying as many bytes from a string as its length",
2125 as_a
<gcall
*>(stmt
), func
))
2127 else if (silen
&& is_strlen_related_p (src
, silen
->ptr
))
2128 warned
= warning_at (callloc
, OPT_Wstringop_overflow_
,
2129 "%G%qD specified bound depends on the length "
2130 "of the source argument",
2131 as_a
<gcall
*>(stmt
), func
);
2134 location_t strlenloc
= pss
->second
;
2135 if (strlenloc
!= UNKNOWN_LOCATION
&& strlenloc
!= callloc
)
2136 inform (strlenloc
, "length computed here");
2140 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
2141 If strlen of the second argument is known and length of the third argument
2142 is that plus one, strlen of the first argument is the same after this
2146 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2149 tree src
, dst
, len
, lhs
, oldlen
, newlen
;
2150 gimple
*stmt
= gsi_stmt (*gsi
);
2151 strinfo
*si
, *dsi
, *olddsi
;
2152 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
2154 len
= gimple_call_arg (stmt
, with_bounds
? 4 : 2);
2155 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
2156 dst
= gimple_call_arg (stmt
, 0);
2157 idx
= get_stridx (src
);
2161 didx
= get_stridx (dst
);
2164 olddsi
= get_strinfo (didx
);
2169 && tree_fits_uhwi_p (len
)
2170 && !integer_zerop (len
))
2171 adjust_last_stmt (olddsi
, stmt
, false);
2178 /* Handle memcpy (x, y, l) where l's relationship with strlen (y)
2180 si
= get_strinfo (idx
);
2181 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
2183 if (TREE_CODE (len
) == INTEGER_CST
2184 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
2186 if (tree_int_cst_le (len
, si
->nonzero_chars
))
2188 /* Copying LEN nonzero characters, where LEN is constant. */
2190 full_string_p
= false;
2194 /* Copying the whole of the analyzed part of SI. */
2195 newlen
= si
->nonzero_chars
;
2196 full_string_p
= si
->full_string_p
;
2201 if (!si
->full_string_p
)
2203 if (TREE_CODE (len
) != SSA_NAME
)
2205 def_stmt
= SSA_NAME_DEF_STMT (len
);
2206 if (!is_gimple_assign (def_stmt
)
2207 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
2208 || gimple_assign_rhs1 (def_stmt
) != si
->nonzero_chars
2209 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
2211 /* Copying variable-length string SI (and no more). */
2212 newlen
= si
->nonzero_chars
;
2213 full_string_p
= true;
2219 /* Handle memcpy (x, "abcd", 5) or
2220 memcpy (x, "abc\0uvw", 7). */
2221 if (!tree_fits_uhwi_p (len
))
2224 unsigned HOST_WIDE_INT clen
= tree_to_uhwi (len
);
2225 unsigned HOST_WIDE_INT nonzero_chars
= ~idx
;
2226 newlen
= build_int_cst (size_type_node
, MIN (nonzero_chars
, clen
));
2227 full_string_p
= clen
> nonzero_chars
;
2230 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
2231 adjust_last_stmt (olddsi
, stmt
, false);
2235 didx
= new_stridx (dst
);
2242 dsi
= unshare_strinfo (olddsi
);
2243 oldlen
= olddsi
->nonzero_chars
;
2244 dsi
->nonzero_chars
= newlen
;
2245 dsi
->full_string_p
= full_string_p
;
2246 /* Break the chain, so adjust_related_strinfo on later pointers in
2247 the chain won't adjust this one anymore. */
2250 dsi
->endptr
= NULL_TREE
;
2254 dsi
= new_strinfo (dst
, didx
, newlen
, full_string_p
);
2255 set_strinfo (didx
, dsi
);
2256 find_equal_ptrs (dst
, didx
);
2258 dsi
->writable
= true;
2259 dsi
->dont_invalidate
= true;
2262 tree adj
= NULL_TREE
;
2263 location_t loc
= gimple_location (stmt
);
2264 if (oldlen
== NULL_TREE
)
2266 else if (integer_zerop (oldlen
))
2268 else if (TREE_CODE (oldlen
) == INTEGER_CST
2269 || TREE_CODE (newlen
) == INTEGER_CST
)
2270 adj
= fold_build2_loc (loc
, MINUS_EXPR
, TREE_TYPE (newlen
), newlen
,
2271 fold_convert_loc (loc
, TREE_TYPE (newlen
),
2273 if (adj
!= NULL_TREE
)
2274 adjust_related_strinfos (loc
, dsi
, adj
);
2278 /* memcpy src may not overlap dst, so src doesn't need to be
2279 invalidated either. */
2281 si
->dont_invalidate
= true;
2285 lhs
= gimple_call_lhs (stmt
);
2288 case BUILT_IN_MEMCPY
:
2289 case BUILT_IN_MEMCPY_CHK
:
2290 case BUILT_IN_MEMCPY_CHKP
:
2291 case BUILT_IN_MEMCPY_CHK_CHKP
:
2292 /* Allow adjust_last_stmt to decrease this memcpy's size. */
2293 laststmt
.stmt
= stmt
;
2294 laststmt
.len
= dsi
->nonzero_chars
;
2295 laststmt
.stridx
= dsi
->idx
;
2297 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
2299 case BUILT_IN_MEMPCPY
:
2300 case BUILT_IN_MEMPCPY_CHK
:
2301 case BUILT_IN_MEMPCPY_CHKP
:
2302 case BUILT_IN_MEMPCPY_CHK_CHKP
:
2310 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
2311 If strlen of the second argument is known, strlen of the first argument
2312 is increased by the length of the second argument. Furthermore, attempt
2313 to convert it to memcpy/strcpy if the length of the first argument
2317 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2320 tree srclen
, args
, type
, fn
, objsz
, endptr
;
2322 gimple
*stmt
= gsi_stmt (*gsi
);
2324 location_t loc
= gimple_location (stmt
);
2325 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
2327 tree src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
2328 tree dst
= gimple_call_arg (stmt
, 0);
2330 /* Bail if the source is the same as destination. It will be diagnosed
2332 if (operand_equal_p (src
, dst
, 0))
2335 tree lhs
= gimple_call_lhs (stmt
);
2337 didx
= get_stridx (dst
);
2343 dsi
= get_strinfo (didx
);
2347 idx
= get_stridx (src
);
2349 srclen
= build_int_cst (size_type_node
, ~idx
);
2352 si
= get_strinfo (idx
);
2354 srclen
= get_string_length (si
);
2357 /* Set the no-warning bit on the transformed statement? */
2358 bool set_no_warning
= false;
2360 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
2363 /* The concatenation always involves copying at least one byte
2364 (the terminating nul), even if the source string is empty.
2365 If the source is unknown assume it's one character long and
2366 used that as both sizes. */
2370 tree type
= TREE_TYPE (slen
);
2371 slen
= fold_build2 (PLUS_EXPR
, type
, slen
, build_int_cst (type
, 1));
2374 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2376 if (!check_bounds_or_overlap (as_a
<gcall
*>(stmt
), dst
, sptr
,
2379 gimple_set_no_warning (stmt
, true);
2380 set_no_warning
= true;
2384 /* strcat (p, q) can be transformed into
2385 tmp = p + strlen (p); endptr = stpcpy (tmp, q);
2386 with length endptr - p if we need to compute the length
2387 later on. Don't do this transformation if we don't need
2389 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
2393 didx
= new_stridx (dst
);
2399 dsi
= new_strinfo (dst
, didx
, NULL_TREE
, false);
2400 set_strinfo (didx
, dsi
);
2401 find_equal_ptrs (dst
, didx
);
2405 dsi
= unshare_strinfo (dsi
);
2406 dsi
->nonzero_chars
= NULL_TREE
;
2407 dsi
->full_string_p
= false;
2409 dsi
->endptr
= NULL_TREE
;
2411 dsi
->writable
= true;
2413 dsi
->dont_invalidate
= true;
2418 tree dstlen
= dsi
->nonzero_chars
;
2419 endptr
= dsi
->endptr
;
2421 dsi
= unshare_strinfo (dsi
);
2422 dsi
->endptr
= NULL_TREE
;
2424 dsi
->writable
= true;
2426 if (srclen
!= NULL_TREE
)
2428 dsi
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
2429 TREE_TYPE (dsi
->nonzero_chars
),
2430 dsi
->nonzero_chars
, srclen
);
2431 gcc_assert (dsi
->full_string_p
);
2432 adjust_related_strinfos (loc
, dsi
, srclen
);
2433 dsi
->dont_invalidate
= true;
2437 dsi
->nonzero_chars
= NULL
;
2438 dsi
->full_string_p
= false;
2439 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
2440 dsi
->dont_invalidate
= true;
2444 /* strcat src may not overlap dst, so src doesn't need to be
2445 invalidated either. */
2446 si
->dont_invalidate
= true;
2448 /* For now. Could remove the lhs from the call and add
2449 lhs = dst; afterwards. */
2457 case BUILT_IN_STRCAT
:
2458 case BUILT_IN_STRCAT_CHKP
:
2459 if (srclen
!= NULL_TREE
)
2460 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
2462 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
2464 case BUILT_IN_STRCAT_CHK
:
2465 case BUILT_IN_STRCAT_CHK_CHKP
:
2466 if (srclen
!= NULL_TREE
)
2467 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
2469 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
2470 objsz
= gimple_call_arg (stmt
, with_bounds
? 4 : 2);
2476 if (fn
== NULL_TREE
)
2481 tree type
= TREE_TYPE (dstlen
);
2483 /* Compute the size of the source sequence, including the nul. */
2484 tree srcsize
= srclen
? srclen
: size_zero_node
;
2485 srcsize
= fold_build2 (PLUS_EXPR
, type
, srcsize
, build_int_cst (type
, 1));
2487 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2489 if (!check_bounds_or_overlap (as_a
<gcall
*>(stmt
), dst
, sptr
,
2492 gimple_set_no_warning (stmt
, true);
2493 set_no_warning
= true;
2497 tree len
= NULL_TREE
;
2498 if (srclen
!= NULL_TREE
)
2500 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
2501 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
2503 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
2504 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
2505 build_int_cst (type
, 1));
2506 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
2510 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
2512 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
2513 TREE_TYPE (dst
), unshare_expr (dst
),
2514 fold_convert_loc (loc
, sizetype
,
2515 unshare_expr (dstlen
)));
2516 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
2518 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2520 fprintf (dump_file
, "Optimizing: ");
2521 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2525 fn
= chkp_maybe_create_clone (fn
)->decl
;
2526 if (srclen
!= NULL_TREE
)
2527 success
= update_gimple_call (gsi
, fn
, 5 + (objsz
!= NULL_TREE
),
2529 gimple_call_arg (stmt
, 1),
2531 gimple_call_arg (stmt
, 3),
2534 success
= update_gimple_call (gsi
, fn
, 4 + (objsz
!= NULL_TREE
),
2536 gimple_call_arg (stmt
, 1),
2538 gimple_call_arg (stmt
, 3),
2542 if (srclen
!= NULL_TREE
)
2543 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
2544 dst
, src
, len
, objsz
);
2546 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
2550 stmt
= gsi_stmt (*gsi
);
2551 gimple_call_set_with_bounds (stmt
, with_bounds
);
2553 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2555 fprintf (dump_file
, "into: ");
2556 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2558 /* If srclen == NULL, note that current string length can be
2559 computed by transforming this strcpy into stpcpy. */
2560 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
2562 adjust_last_stmt (dsi
, stmt
, true);
2563 if (srclen
!= NULL_TREE
)
2565 laststmt
.stmt
= stmt
;
2566 laststmt
.len
= srclen
;
2567 laststmt
.stridx
= dsi
->idx
;
2570 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2571 fprintf (dump_file
, "not possible.\n");
2574 gimple_set_no_warning (stmt
, true);
2577 /* Handle a call to malloc or calloc. */
2580 handle_builtin_malloc (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2582 gimple
*stmt
= gsi_stmt (*gsi
);
2583 tree lhs
= gimple_call_lhs (stmt
);
2584 if (lhs
== NULL_TREE
)
2587 gcc_assert (get_stridx (lhs
) == 0);
2588 int idx
= new_stridx (lhs
);
2589 tree length
= NULL_TREE
;
2590 if (bcode
== BUILT_IN_CALLOC
)
2591 length
= build_int_cst (size_type_node
, 0);
2592 strinfo
*si
= new_strinfo (lhs
, idx
, length
, length
!= NULL_TREE
);
2593 if (bcode
== BUILT_IN_CALLOC
)
2595 set_strinfo (idx
, si
);
2596 si
->writable
= true;
2598 si
->dont_invalidate
= true;
2601 /* Handle a call to memset.
2602 After a call to calloc, memset(,0,) is unnecessary.
2603 memset(malloc(n),0,n) is calloc(n,1). */
2606 handle_builtin_memset (gimple_stmt_iterator
*gsi
)
2608 gimple
*stmt2
= gsi_stmt (*gsi
);
2609 if (!integer_zerop (gimple_call_arg (stmt2
, 1)))
2611 tree ptr
= gimple_call_arg (stmt2
, 0);
2612 int idx1
= get_stridx (ptr
);
2615 strinfo
*si1
= get_strinfo (idx1
);
2618 gimple
*stmt1
= si1
->stmt
;
2619 if (!stmt1
|| !is_gimple_call (stmt1
))
2621 tree callee1
= gimple_call_fndecl (stmt1
);
2622 if (!valid_builtin_call (stmt1
))
2624 enum built_in_function code1
= DECL_FUNCTION_CODE (callee1
);
2625 tree size
= gimple_call_arg (stmt2
, 2);
2626 if (code1
== BUILT_IN_CALLOC
)
2627 /* Not touching stmt1 */ ;
2628 else if (code1
== BUILT_IN_MALLOC
2629 && operand_equal_p (gimple_call_arg (stmt1
, 0), size
, 0))
2631 gimple_stmt_iterator gsi1
= gsi_for_stmt (stmt1
);
2632 update_gimple_call (&gsi1
, builtin_decl_implicit (BUILT_IN_CALLOC
), 2,
2633 size
, build_one_cst (size_type_node
));
2634 si1
->nonzero_chars
= build_int_cst (size_type_node
, 0);
2635 si1
->full_string_p
= true;
2636 si1
->stmt
= gsi_stmt (gsi1
);
2640 tree lhs
= gimple_call_lhs (stmt2
);
2641 unlink_stmt_vdef (stmt2
);
2644 gimple
*assign
= gimple_build_assign (lhs
, ptr
);
2645 gsi_replace (gsi
, assign
, false);
2649 gsi_remove (gsi
, true);
2650 release_defs (stmt2
);
2656 /* Handle a call to memcmp. We try to handle small comparisons by
2657 converting them to load and compare, and replacing the call to memcmp
2658 with a __builtin_memcmp_eq call where possible. */
2661 handle_builtin_memcmp (gimple_stmt_iterator
*gsi
)
2663 gcall
*stmt2
= as_a
<gcall
*> (gsi_stmt (*gsi
));
2664 tree res
= gimple_call_lhs (stmt2
);
2665 tree arg1
= gimple_call_arg (stmt2
, 0);
2666 tree arg2
= gimple_call_arg (stmt2
, 1);
2667 tree len
= gimple_call_arg (stmt2
, 2);
2668 unsigned HOST_WIDE_INT leni
;
2669 use_operand_p use_p
;
2670 imm_use_iterator iter
;
2675 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
2677 gimple
*ustmt
= USE_STMT (use_p
);
2679 if (is_gimple_debug (ustmt
))
2681 if (gimple_code (ustmt
) == GIMPLE_ASSIGN
)
2683 gassign
*asgn
= as_a
<gassign
*> (ustmt
);
2684 tree_code code
= gimple_assign_rhs_code (asgn
);
2685 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2686 || !integer_zerop (gimple_assign_rhs2 (asgn
)))
2689 else if (gimple_code (ustmt
) == GIMPLE_COND
)
2691 tree_code code
= gimple_cond_code (ustmt
);
2692 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2693 || !integer_zerop (gimple_cond_rhs (ustmt
)))
2700 if (tree_fits_uhwi_p (len
)
2701 && (leni
= tree_to_uhwi (len
)) <= GET_MODE_SIZE (word_mode
)
2702 && pow2p_hwi (leni
))
2704 leni
*= CHAR_TYPE_SIZE
;
2705 unsigned align1
= get_pointer_alignment (arg1
);
2706 unsigned align2
= get_pointer_alignment (arg2
);
2707 unsigned align
= MIN (align1
, align2
);
2708 scalar_int_mode mode
;
2709 if (int_mode_for_size (leni
, 1).exists (&mode
)
2710 && (align
>= leni
|| !targetm
.slow_unaligned_access (mode
, align
)))
2712 location_t loc
= gimple_location (stmt2
);
2714 type
= build_nonstandard_integer_type (leni
, 1);
2715 gcc_assert (known_eq (GET_MODE_BITSIZE (TYPE_MODE (type
)), leni
));
2716 tree ptrtype
= build_pointer_type_for_mode (char_type_node
,
2718 off
= build_int_cst (ptrtype
, 0);
2719 arg1
= build2_loc (loc
, MEM_REF
, type
, arg1
, off
);
2720 arg2
= build2_loc (loc
, MEM_REF
, type
, arg2
, off
);
2721 tree tem1
= fold_const_aggregate_ref (arg1
);
2724 tree tem2
= fold_const_aggregate_ref (arg2
);
2727 res
= fold_convert_loc (loc
, TREE_TYPE (res
),
2728 fold_build2_loc (loc
, NE_EXPR
,
2731 gimplify_and_update_call_from_tree (gsi
, res
);
2736 gimple_call_set_fndecl (stmt2
, builtin_decl_explicit (BUILT_IN_MEMCMP_EQ
));
2740 /* Handle a POINTER_PLUS_EXPR statement.
2741 For p = "abcd" + 2; compute associated length, or if
2742 p = q + off is pointing to a '\0' character of a string, call
2743 zero_length_string on it. */
2746 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
2748 gimple
*stmt
= gsi_stmt (*gsi
);
2749 tree lhs
= gimple_assign_lhs (stmt
), off
;
2750 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
2758 tree off
= gimple_assign_rhs2 (stmt
);
2759 if (tree_fits_uhwi_p (off
)
2760 && tree_to_uhwi (off
) <= (unsigned HOST_WIDE_INT
) ~idx
)
2761 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
2762 = ~(~idx
- (int) tree_to_uhwi (off
));
2766 si
= get_strinfo (idx
);
2767 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
2770 off
= gimple_assign_rhs2 (stmt
);
2772 if (si
->full_string_p
&& operand_equal_p (si
->nonzero_chars
, off
, 0))
2773 zsi
= zero_length_string (lhs
, si
);
2774 else if (TREE_CODE (off
) == SSA_NAME
)
2776 gimple
*def_stmt
= SSA_NAME_DEF_STMT (off
);
2777 if (gimple_assign_single_p (def_stmt
)
2778 && si
->full_string_p
2779 && operand_equal_p (si
->nonzero_chars
,
2780 gimple_assign_rhs1 (def_stmt
), 0))
2781 zsi
= zero_length_string (lhs
, si
);
2784 && si
->endptr
!= NULL_TREE
2785 && si
->endptr
!= lhs
2786 && TREE_CODE (si
->endptr
) == SSA_NAME
)
2788 enum tree_code rhs_code
2789 = useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (si
->endptr
))
2790 ? SSA_NAME
: NOP_EXPR
;
2791 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, si
->endptr
);
2792 gcc_assert (gsi_stmt (*gsi
) == stmt
);
2797 /* If RHS, either directly or indirectly, refers to a string of constant
2798 length, return it. Otherwise return a negative value. */
2800 static HOST_WIDE_INT
2801 get_string_cst_length (tree rhs
)
2803 if (TREE_CODE (rhs
) == MEM_REF
2804 && integer_zerop (TREE_OPERAND (rhs
, 1)))
2806 rhs
= TREE_OPERAND (rhs
, 0);
2807 if (TREE_CODE (rhs
) == ADDR_EXPR
)
2809 tree rhs_addr
= rhs
;
2811 rhs
= TREE_OPERAND (rhs
, 0);
2812 if (TREE_CODE (rhs
) != STRING_CST
)
2814 int idx
= get_stridx (rhs_addr
);
2817 strinfo
*si
= get_strinfo (idx
);
2819 && si
->full_string_p
2820 && tree_fits_shwi_p (si
->nonzero_chars
))
2821 return tree_to_shwi (si
->nonzero_chars
);
2827 if (TREE_CODE (rhs
) == VAR_DECL
2828 && TREE_READONLY (rhs
))
2829 rhs
= DECL_INITIAL (rhs
);
2831 if (rhs
&& TREE_CODE (rhs
) == STRING_CST
)
2832 return strlen (TREE_STRING_POINTER (rhs
));
2837 /* Handle a single character store. */
2840 handle_char_store (gimple_stmt_iterator
*gsi
)
2844 gimple
*stmt
= gsi_stmt (*gsi
);
2845 tree ssaname
= NULL_TREE
, lhs
= gimple_assign_lhs (stmt
);
2846 tree rhs
= gimple_assign_rhs1 (stmt
);
2847 unsigned HOST_WIDE_INT offset
= 0;
2849 if (TREE_CODE (lhs
) == MEM_REF
2850 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
)
2852 tree mem_offset
= TREE_OPERAND (lhs
, 1);
2853 if (tree_fits_uhwi_p (mem_offset
))
2855 /* Get the strinfo for the base, and use it if it starts with at
2856 least OFFSET nonzero characters. This is trivially true if
2858 offset
= tree_to_uhwi (mem_offset
);
2859 idx
= get_stridx (TREE_OPERAND (lhs
, 0));
2861 si
= get_strinfo (idx
);
2863 ssaname
= TREE_OPERAND (lhs
, 0);
2864 else if (si
== NULL
|| compare_nonzero_chars (si
, offset
) < 0)
2870 idx
= get_addr_stridx (lhs
, NULL_TREE
, &offset
);
2872 si
= get_strinfo (idx
);
2875 bool storing_zero_p
= initializer_zerop (rhs
);
2876 bool storing_nonzero_p
= (!storing_zero_p
2877 && TREE_CODE (rhs
) == INTEGER_CST
2878 && integer_nonzerop (rhs
));
2879 /* Set to the length of the string being assigned if known. */
2880 HOST_WIDE_INT rhslen
;
2884 int cmp
= compare_nonzero_chars (si
, offset
);
2885 gcc_assert (offset
== 0 || cmp
>= 0);
2886 if (storing_zero_p
&& cmp
== 0 && si
->full_string_p
)
2888 /* When overwriting a '\0' with a '\0', the store can be removed
2889 if we know it has been stored in the current function. */
2890 if (!stmt_could_throw_p (stmt
) && si
->writable
)
2892 unlink_stmt_vdef (stmt
);
2893 release_defs (stmt
);
2894 gsi_remove (gsi
, true);
2899 si
->writable
= true;
2904 /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0',
2905 and if we aren't storing '\0', we know that the length of the
2906 string and any other zero terminated string in memory remains
2907 the same. In that case we move to the next gimple statement and
2908 return to signal the caller that it shouldn't invalidate anything.
2910 This is benefical for cases like:
2915 strcpy (p, "foobar");
2916 size_t len = strlen (p); // This can be optimized into 6
2917 size_t len2 = strlen (q); // This has to be computed
2919 size_t len3 = strlen (p); // This can be optimized into 6
2920 size_t len4 = strlen (q); // This can be optimized into len2
2921 bar (len, len2, len3, len4);
2924 else if (storing_nonzero_p
&& cmp
> 0)
2929 else if (storing_zero_p
|| storing_nonzero_p
|| (offset
!= 0 && cmp
> 0))
2931 /* When storing_nonzero_p, we know that the string now starts
2932 with OFFSET + 1 nonzero characters, but don't know whether
2933 there's a following nul terminator.
2935 When storing_zero_p, we know that the string is now OFFSET
2938 Otherwise, we're storing an unknown value at offset OFFSET,
2939 so need to clip the nonzero_chars to OFFSET. */
2940 location_t loc
= gimple_location (stmt
);
2941 tree oldlen
= si
->nonzero_chars
;
2942 if (cmp
== 0 && si
->full_string_p
)
2943 /* We're overwriting the nul terminator with a nonzero or
2944 unknown character. If the previous stmt was a memcpy,
2945 its length may be decreased. */
2946 adjust_last_stmt (si
, stmt
, false);
2947 si
= unshare_strinfo (si
);
2948 if (storing_nonzero_p
)
2949 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
+ 1);
2951 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
);
2952 si
->full_string_p
= storing_zero_p
;
2955 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
2956 si
->endptr
= ssaname
;
2961 si
->writable
= true;
2962 si
->dont_invalidate
= true;
2965 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
2966 si
->nonzero_chars
, oldlen
);
2967 adjust_related_strinfos (loc
, si
, adj
);
2973 else if (idx
== 0 && (storing_zero_p
|| storing_nonzero_p
))
2976 idx
= new_stridx (ssaname
);
2978 idx
= new_addr_stridx (lhs
);
2981 tree ptr
= (ssaname
? ssaname
: build_fold_addr_expr (lhs
));
2982 tree len
= storing_nonzero_p
? size_one_node
: size_zero_node
;
2983 si
= new_strinfo (ptr
, idx
, len
, storing_zero_p
);
2984 set_strinfo (idx
, si
);
2987 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
2988 si
->endptr
= ssaname
;
2989 si
->dont_invalidate
= true;
2990 si
->writable
= true;
2994 && (rhslen
= get_string_cst_length (gimple_assign_rhs1 (stmt
))) >= 0
2995 && ssaname
== NULL_TREE
2996 && TREE_CODE (TREE_TYPE (lhs
)) == ARRAY_TYPE
)
2998 HOST_WIDE_INT a
= int_size_in_bytes (TREE_TYPE (lhs
));
2999 if (a
> 0 && (unsigned HOST_WIDE_INT
) a
> (unsigned HOST_WIDE_INT
) rhslen
)
3001 int idx
= new_addr_stridx (lhs
);
3004 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
3005 build_int_cst (size_type_node
, rhslen
), true);
3006 set_strinfo (idx
, si
);
3007 si
->dont_invalidate
= true;
3012 if (si
!= NULL
&& offset
== 0 && storing_zero_p
)
3014 /* Allow adjust_last_stmt to remove it if the stored '\0'
3015 is immediately overwritten. */
3016 laststmt
.stmt
= stmt
;
3017 laststmt
.len
= build_int_cst (size_type_node
, 1);
3018 laststmt
.stridx
= si
->idx
;
3023 /* Try to fold strstr (s, t) eq/ne s to strncmp (s, t, strlen (t)) eq/ne 0. */
3026 fold_strstr_to_strncmp (tree rhs1
, tree rhs2
, gimple
*stmt
)
3028 if (TREE_CODE (rhs1
) != SSA_NAME
3029 || TREE_CODE (rhs2
) != SSA_NAME
)
3032 gimple
*call_stmt
= NULL
;
3033 for (int pass
= 0; pass
< 2; pass
++)
3035 gimple
*g
= SSA_NAME_DEF_STMT (rhs1
);
3036 if (gimple_call_builtin_p (g
, BUILT_IN_STRSTR
)
3037 && has_single_use (rhs1
)
3038 && gimple_call_arg (g
, 0) == rhs2
)
3043 std::swap (rhs1
, rhs2
);
3048 tree arg0
= gimple_call_arg (call_stmt
, 0);
3052 tree arg1
= gimple_call_arg (call_stmt
, 1);
3053 tree arg1_len
= NULL_TREE
;
3054 int idx
= get_stridx (arg1
);
3059 arg1_len
= build_int_cst (size_type_node
, ~idx
);
3062 strinfo
*si
= get_strinfo (idx
);
3064 arg1_len
= get_string_length (si
);
3068 if (arg1_len
!= NULL_TREE
)
3070 gimple_stmt_iterator gsi
= gsi_for_stmt (call_stmt
);
3071 tree strncmp_decl
= builtin_decl_explicit (BUILT_IN_STRNCMP
);
3073 if (!is_gimple_val (arg1_len
))
3075 tree arg1_len_tmp
= make_ssa_name (TREE_TYPE (arg1_len
));
3076 gassign
*arg1_stmt
= gimple_build_assign (arg1_len_tmp
,
3078 gsi_insert_before (&gsi
, arg1_stmt
, GSI_SAME_STMT
);
3079 arg1_len
= arg1_len_tmp
;
3082 gcall
*strncmp_call
= gimple_build_call (strncmp_decl
, 3,
3083 arg0
, arg1
, arg1_len
);
3084 tree strncmp_lhs
= make_ssa_name (integer_type_node
);
3085 gimple_set_vuse (strncmp_call
, gimple_vuse (call_stmt
));
3086 gimple_call_set_lhs (strncmp_call
, strncmp_lhs
);
3087 gsi_remove (&gsi
, true);
3088 gsi_insert_before (&gsi
, strncmp_call
, GSI_SAME_STMT
);
3089 tree zero
= build_zero_cst (TREE_TYPE (strncmp_lhs
));
3091 if (is_gimple_assign (stmt
))
3093 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
3095 tree cond
= gimple_assign_rhs1 (stmt
);
3096 TREE_OPERAND (cond
, 0) = strncmp_lhs
;
3097 TREE_OPERAND (cond
, 1) = zero
;
3101 gimple_assign_set_rhs1 (stmt
, strncmp_lhs
);
3102 gimple_assign_set_rhs2 (stmt
, zero
);
3107 gcond
*cond
= as_a
<gcond
*> (stmt
);
3108 gimple_cond_set_lhs (cond
, strncmp_lhs
);
3109 gimple_cond_set_rhs (cond
, zero
);
3117 /* Attempt to check for validity of the performed access a single statement
3118 at *GSI using string length knowledge, and to optimize it.
3119 If the given basic block needs clean-up of EH, CLEANUP_EH is set to
3123 strlen_check_and_optimize_stmt (gimple_stmt_iterator
*gsi
, bool *cleanup_eh
)
3125 gimple
*stmt
= gsi_stmt (*gsi
);
3127 if (is_gimple_call (stmt
))
3129 tree callee
= gimple_call_fndecl (stmt
);
3130 if (valid_builtin_call (stmt
))
3131 switch (DECL_FUNCTION_CODE (callee
))
3133 case BUILT_IN_STRLEN
:
3134 case BUILT_IN_STRLEN_CHKP
:
3135 handle_builtin_strlen (gsi
);
3137 case BUILT_IN_STRCHR
:
3138 case BUILT_IN_STRCHR_CHKP
:
3139 handle_builtin_strchr (gsi
);
3141 case BUILT_IN_STRCPY
:
3142 case BUILT_IN_STRCPY_CHK
:
3143 case BUILT_IN_STPCPY
:
3144 case BUILT_IN_STPCPY_CHK
:
3145 case BUILT_IN_STRCPY_CHKP
:
3146 case BUILT_IN_STRCPY_CHK_CHKP
:
3147 case BUILT_IN_STPCPY_CHKP
:
3148 case BUILT_IN_STPCPY_CHK_CHKP
:
3149 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3152 case BUILT_IN_STRNCAT
:
3153 case BUILT_IN_STRNCAT_CHK
:
3154 handle_builtin_strncat (DECL_FUNCTION_CODE (callee
), gsi
);
3157 case BUILT_IN_STPNCPY
:
3158 case BUILT_IN_STPNCPY_CHK
:
3159 case BUILT_IN_STRNCPY
:
3160 case BUILT_IN_STRNCPY_CHK
:
3161 handle_builtin_stxncpy (DECL_FUNCTION_CODE (callee
), gsi
);
3164 case BUILT_IN_MEMCPY
:
3165 case BUILT_IN_MEMCPY_CHK
:
3166 case BUILT_IN_MEMPCPY
:
3167 case BUILT_IN_MEMPCPY_CHK
:
3168 case BUILT_IN_MEMCPY_CHKP
:
3169 case BUILT_IN_MEMCPY_CHK_CHKP
:
3170 case BUILT_IN_MEMPCPY_CHKP
:
3171 case BUILT_IN_MEMPCPY_CHK_CHKP
:
3172 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3174 case BUILT_IN_STRCAT
:
3175 case BUILT_IN_STRCAT_CHK
:
3176 case BUILT_IN_STRCAT_CHKP
:
3177 case BUILT_IN_STRCAT_CHK_CHKP
:
3178 handle_builtin_strcat (DECL_FUNCTION_CODE (callee
), gsi
);
3180 case BUILT_IN_MALLOC
:
3181 case BUILT_IN_CALLOC
:
3182 handle_builtin_malloc (DECL_FUNCTION_CODE (callee
), gsi
);
3184 case BUILT_IN_MEMSET
:
3185 if (!handle_builtin_memset (gsi
))
3188 case BUILT_IN_MEMCMP
:
3189 if (!handle_builtin_memcmp (gsi
))
3196 else if (is_gimple_assign (stmt
) && !gimple_clobber_p (stmt
))
3198 tree lhs
= gimple_assign_lhs (stmt
);
3200 if (TREE_CODE (lhs
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (lhs
)))
3202 if (gimple_assign_single_p (stmt
)
3203 || (gimple_assign_cast_p (stmt
)
3204 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
3206 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
3207 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = idx
;
3209 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
3210 handle_pointer_plus (gsi
);
3212 else if (TREE_CODE (lhs
) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
3214 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3215 if (code
== COND_EXPR
)
3217 tree cond
= gimple_assign_rhs1 (stmt
);
3218 enum tree_code cond_code
= TREE_CODE (cond
);
3220 if (cond_code
== EQ_EXPR
|| cond_code
== NE_EXPR
)
3221 fold_strstr_to_strncmp (TREE_OPERAND (cond
, 0),
3222 TREE_OPERAND (cond
, 1), stmt
);
3224 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3225 fold_strstr_to_strncmp (gimple_assign_rhs1 (stmt
),
3226 gimple_assign_rhs2 (stmt
), stmt
);
3227 else if (gimple_assign_load_p (stmt
)
3228 && TREE_CODE (TREE_TYPE (lhs
)) == INTEGER_TYPE
3229 && TYPE_MODE (TREE_TYPE (lhs
)) == TYPE_MODE (char_type_node
)
3230 && (TYPE_PRECISION (TREE_TYPE (lhs
))
3231 == TYPE_PRECISION (char_type_node
))
3232 && !gimple_has_volatile_ops (stmt
))
3234 tree off
= integer_zero_node
;
3235 unsigned HOST_WIDE_INT coff
= 0;
3237 tree rhs1
= gimple_assign_rhs1 (stmt
);
3238 if (code
== MEM_REF
)
3240 idx
= get_stridx (TREE_OPERAND (rhs1
, 0));
3243 strinfo
*si
= get_strinfo (idx
);
3245 && si
->nonzero_chars
3246 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
3247 && (wi::to_widest (si
->nonzero_chars
)
3248 >= wi::to_widest (off
)))
3249 off
= TREE_OPERAND (rhs1
, 1);
3251 /* This case is not useful. See if get_addr_stridx
3252 returns something usable. */
3257 idx
= get_addr_stridx (rhs1
, NULL_TREE
, &coff
);
3260 strinfo
*si
= get_strinfo (idx
);
3262 && si
->nonzero_chars
3263 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
3265 widest_int w1
= wi::to_widest (si
->nonzero_chars
);
3266 widest_int w2
= wi::to_widest (off
) + coff
;
3268 && si
->full_string_p
)
3270 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3272 fprintf (dump_file
, "Optimizing: ");
3273 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3276 /* Reading the final '\0' character. */
3277 tree zero
= build_int_cst (TREE_TYPE (lhs
), 0);
3278 gimple_set_vuse (stmt
, NULL_TREE
);
3279 gimple_assign_set_rhs_from_tree (gsi
, zero
);
3281 |= maybe_clean_or_replace_eh_stmt (stmt
,
3283 stmt
= gsi_stmt (*gsi
);
3286 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3288 fprintf (dump_file
, "into: ");
3289 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3294 /* Reading a character before the final '\0'
3295 character. Just set the value range to ~[0, 0]
3296 if we don't have anything better. */
3298 tree type
= TREE_TYPE (lhs
);
3299 enum value_range_type vr
3300 = get_range_info (lhs
, &min
, &max
);
3301 if (vr
== VR_VARYING
3303 && min
== wi::min_value (TYPE_PRECISION (type
),
3305 && max
== wi::max_value (TYPE_PRECISION (type
),
3307 set_range_info (lhs
, VR_ANTI_RANGE
,
3308 wi::zero (TYPE_PRECISION (type
)),
3309 wi::zero (TYPE_PRECISION (type
)));
3315 if (strlen_to_stridx
)
3317 tree rhs1
= gimple_assign_rhs1 (stmt
);
3318 if (stridx_strlenloc
*ps
= strlen_to_stridx
->get (rhs1
))
3319 strlen_to_stridx
->put (lhs
, stridx_strlenloc (*ps
));
3322 else if (TREE_CODE (lhs
) != SSA_NAME
&& !TREE_SIDE_EFFECTS (lhs
))
3324 tree type
= TREE_TYPE (lhs
);
3325 if (TREE_CODE (type
) == ARRAY_TYPE
)
3326 type
= TREE_TYPE (type
);
3327 if (TREE_CODE (type
) == INTEGER_TYPE
3328 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
3329 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
))
3331 if (! handle_char_store (gsi
))
3336 else if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
3338 enum tree_code code
= gimple_cond_code (cond
);
3339 if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3340 fold_strstr_to_strncmp (gimple_cond_lhs (stmt
),
3341 gimple_cond_rhs (stmt
), stmt
);
3344 if (gimple_vdef (stmt
))
3345 maybe_invalidate (stmt
);
3349 /* Recursively call maybe_invalidate on stmts that might be executed
3350 in between dombb and current bb and that contain a vdef. Stop when
3351 *count stmts are inspected, or if the whole strinfo vector has
3352 been invalidated. */
3355 do_invalidate (basic_block dombb
, gimple
*phi
, bitmap visited
, int *count
)
3357 unsigned int i
, n
= gimple_phi_num_args (phi
);
3359 for (i
= 0; i
< n
; i
++)
3361 tree vuse
= gimple_phi_arg_def (phi
, i
);
3362 gimple
*stmt
= SSA_NAME_DEF_STMT (vuse
);
3363 basic_block bb
= gimple_bb (stmt
);
3366 || !bitmap_set_bit (visited
, bb
->index
)
3367 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3371 if (gimple_code (stmt
) == GIMPLE_PHI
)
3373 do_invalidate (dombb
, stmt
, visited
, count
);
3380 if (!maybe_invalidate (stmt
))
3385 vuse
= gimple_vuse (stmt
);
3386 stmt
= SSA_NAME_DEF_STMT (vuse
);
3387 if (gimple_bb (stmt
) != bb
)
3389 bb
= gimple_bb (stmt
);
3392 || !bitmap_set_bit (visited
, bb
->index
)
3393 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3400 class strlen_dom_walker
: public dom_walker
3403 strlen_dom_walker (cdi_direction direction
)
3404 : dom_walker (direction
), m_cleanup_cfg (false)
3407 virtual edge
before_dom_children (basic_block
);
3408 virtual void after_dom_children (basic_block
);
3410 /* Flag that will trigger TODO_cleanup_cfg to be returned in strlen
3411 execute function. */
3415 /* Callback for walk_dominator_tree. Attempt to optimize various
3416 string ops by remembering string lengths pointed by pointer SSA_NAMEs. */
3419 strlen_dom_walker::before_dom_children (basic_block bb
)
3421 basic_block dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
3424 stridx_to_strinfo
= NULL
;
3427 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) dombb
->aux
);
3428 if (stridx_to_strinfo
)
3430 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3433 gphi
*phi
= gsi
.phi ();
3434 if (virtual_operand_p (gimple_phi_result (phi
)))
3436 bitmap visited
= BITMAP_ALLOC (NULL
);
3437 int count_vdef
= 100;
3438 do_invalidate (dombb
, phi
, visited
, &count_vdef
);
3439 BITMAP_FREE (visited
);
3440 if (count_vdef
== 0)
3442 /* If there were too many vdefs in between immediate
3443 dominator and current bb, invalidate everything.
3444 If stridx_to_strinfo has been unshared, we need
3445 to free it, otherwise just set it to NULL. */
3446 if (!strinfo_shared ())
3452 vec_safe_iterate (stridx_to_strinfo
, i
, &si
);
3456 (*stridx_to_strinfo
)[i
] = NULL
;
3460 stridx_to_strinfo
= NULL
;
3468 /* If all PHI arguments have the same string index, the PHI result
3470 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3473 gphi
*phi
= gsi
.phi ();
3474 tree result
= gimple_phi_result (phi
);
3475 if (!virtual_operand_p (result
) && POINTER_TYPE_P (TREE_TYPE (result
)))
3477 int idx
= get_stridx (gimple_phi_arg_def (phi
, 0));
3480 unsigned int i
, n
= gimple_phi_num_args (phi
);
3481 for (i
= 1; i
< n
; i
++)
3482 if (idx
!= get_stridx (gimple_phi_arg_def (phi
, i
)))
3485 ssa_ver_to_stridx
[SSA_NAME_VERSION (result
)] = idx
;
3490 bool cleanup_eh
= false;
3492 /* Attempt to optimize individual statements. */
3493 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
3494 if (strlen_check_and_optimize_stmt (&gsi
, &cleanup_eh
))
3497 if (cleanup_eh
&& gimple_purge_dead_eh_edges (bb
))
3498 m_cleanup_cfg
= true;
3500 bb
->aux
= stridx_to_strinfo
;
3501 if (vec_safe_length (stridx_to_strinfo
) && !strinfo_shared ())
3502 (*stridx_to_strinfo
)[0] = (strinfo
*) bb
;
3506 /* Callback for walk_dominator_tree. Free strinfo vector if it is
3507 owned by the current bb, clear bb->aux. */
3510 strlen_dom_walker::after_dom_children (basic_block bb
)
3514 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) bb
->aux
);
3515 if (vec_safe_length (stridx_to_strinfo
)
3516 && (*stridx_to_strinfo
)[0] == (strinfo
*) bb
)
3521 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
3523 vec_free (stridx_to_strinfo
);
3529 /* Main entry point. */
3533 const pass_data pass_data_strlen
=
3535 GIMPLE_PASS
, /* type */
3536 "strlen", /* name */
3537 OPTGROUP_NONE
, /* optinfo_flags */
3538 TV_TREE_STRLEN
, /* tv_id */
3539 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3540 0, /* properties_provided */
3541 0, /* properties_destroyed */
3542 0, /* todo_flags_start */
3543 0, /* todo_flags_finish */
3546 class pass_strlen
: public gimple_opt_pass
3549 pass_strlen (gcc::context
*ctxt
)
3550 : gimple_opt_pass (pass_data_strlen
, ctxt
)
3553 /* opt_pass methods: */
3554 virtual bool gate (function
*) { return flag_optimize_strlen
!= 0; }
3555 virtual unsigned int execute (function
*);
3557 }; // class pass_strlen
3560 pass_strlen::execute (function
*fun
)
3562 gcc_assert (!strlen_to_stridx
);
3563 if (warn_stringop_overflow
|| warn_stringop_truncation
)
3564 strlen_to_stridx
= new hash_map
<tree
, stridx_strlenloc
> ();
3566 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
3569 calculate_dominance_info (CDI_DOMINATORS
);
3571 /* String length optimization is implemented as a walk of the dominator
3572 tree and a forward walk of statements within each block. */
3573 strlen_dom_walker
walker (CDI_DOMINATORS
);
3574 walker
.walk (fun
->cfg
->x_entry_block_ptr
);
3576 ssa_ver_to_stridx
.release ();
3577 strinfo_pool
.release ();
3578 if (decl_to_stridxlist_htab
)
3580 obstack_free (&stridx_obstack
, NULL
);
3581 delete decl_to_stridxlist_htab
;
3582 decl_to_stridxlist_htab
= NULL
;
3584 laststmt
.stmt
= NULL
;
3585 laststmt
.len
= NULL_TREE
;
3586 laststmt
.stridx
= 0;
3588 if (strlen_to_stridx
)
3590 strlen_to_stridx
->empty ();
3591 delete strlen_to_stridx
;
3592 strlen_to_stridx
= NULL
;
3595 return walker
.m_cleanup_cfg
? TODO_cleanup_cfg
: 0;
3601 make_pass_strlen (gcc::context
*ctxt
)
3603 return new pass_strlen (ctxt
);