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
);
1804 if (gimple_no_warning_p (stmt
))
1807 wide_int cntrange
[2];
1809 if (TREE_CODE (cnt
) == INTEGER_CST
)
1810 cntrange
[0] = cntrange
[1] = wi::to_wide (cnt
);
1811 else if (TREE_CODE (cnt
) == SSA_NAME
)
1813 enum value_range_type rng
= get_range_info (cnt
, cntrange
, cntrange
+ 1);
1814 if (rng
== VR_RANGE
)
1816 else if (rng
== VR_ANTI_RANGE
)
1818 wide_int maxobjsize
= wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node
));
1820 if (wi::ltu_p (cntrange
[1], maxobjsize
))
1822 cntrange
[0] = cntrange
[1] + 1;
1823 cntrange
[1] = maxobjsize
;
1827 cntrange
[1] = cntrange
[0] - 1;
1828 cntrange
[0] = wi::zero (TYPE_PRECISION (TREE_TYPE (cnt
)));
1837 /* Negative value is the constant string length. If it's less than
1838 the lower bound there is no truncation. Avoid calling get_stridx()
1839 when ssa_ver_to_stridx is empty. That implies the caller isn't
1840 running under the control of this pass and ssa_ver_to_stridx hasn't
1841 been created yet. */
1842 int sidx
= ssa_ver_to_stridx
.length () ? get_stridx (src
) : 0;
1843 if (sidx
< 0 && wi::gtu_p (cntrange
[0], ~sidx
))
1846 tree dst
= gimple_call_arg (stmt
, 0);
1848 if (TREE_CODE (dstdecl
) == ADDR_EXPR
)
1849 dstdecl
= TREE_OPERAND (dstdecl
, 0);
1851 /* If the destination refers to a an array/pointer declared nonstring
1853 tree ref
= NULL_TREE
;
1854 if (get_attr_nonstring_decl (dstdecl
, &ref
))
1857 /* Look for dst[i] = '\0'; after the stxncpy() call and if found
1858 avoid the truncation warning. */
1859 gsi_next_nondebug (&gsi
);
1860 gimple
*next_stmt
= gsi_stmt (gsi
);
1863 /* When there is no statement in the same basic block check
1864 the immediate successor block. */
1865 if (basic_block bb
= gimple_bb (stmt
))
1867 if (single_succ_p (bb
))
1869 /* For simplicity, ignore blocks with multiple outgoing
1870 edges for now and only consider successor blocks along
1872 edge e
= EDGE_SUCC (bb
, 0);
1873 if (!(e
->flags
& EDGE_ABNORMAL
))
1875 gsi
= gsi_start_bb (e
->dest
);
1876 next_stmt
= gsi_stmt (gsi
);
1877 if (next_stmt
&& is_gimple_debug (next_stmt
))
1879 gsi_next_nondebug (&gsi
);
1880 next_stmt
= gsi_stmt (gsi
);
1887 if (next_stmt
&& is_gimple_assign (next_stmt
))
1889 tree lhs
= gimple_assign_lhs (next_stmt
);
1890 tree_code code
= TREE_CODE (lhs
);
1891 if (code
== ARRAY_REF
|| code
== MEM_REF
)
1892 lhs
= TREE_OPERAND (lhs
, 0);
1894 tree func
= gimple_call_fndecl (stmt
);
1895 if (DECL_FUNCTION_CODE (func
) == BUILT_IN_STPNCPY
)
1897 tree ret
= gimple_call_lhs (stmt
);
1898 if (ret
&& operand_equal_p (ret
, lhs
, 0))
1902 /* Determine the base address and offset of the reference,
1903 ignoring the innermost array index. */
1904 if (TREE_CODE (ref
) == ARRAY_REF
)
1905 ref
= TREE_OPERAND (ref
, 0);
1908 tree dstbase
= get_addr_base_and_unit_offset (ref
, &dstoff
);
1911 tree lhsbase
= get_addr_base_and_unit_offset (lhs
, &lhsoff
);
1914 && known_eq (dstoff
, lhsoff
)
1915 && operand_equal_p (dstbase
, lhsbase
, 0))
1919 int prec
= TYPE_PRECISION (TREE_TYPE (cnt
));
1920 wide_int lenrange
[2];
1921 if (strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
)
1923 lenrange
[0] = (sisrc
->nonzero_chars
1924 && TREE_CODE (sisrc
->nonzero_chars
) == INTEGER_CST
1925 ? wi::to_wide (sisrc
->nonzero_chars
)
1927 lenrange
[1] = lenrange
[0];
1930 lenrange
[0] = lenrange
[1] = wi::shwi (~sidx
, prec
);
1934 get_range_strlen (src
, range
);
1935 if (range
[0] != NULL_TREE
1936 && TREE_CODE (range
[0]) == INTEGER_CST
1937 && range
[1] != NULL_TREE
1938 && TREE_CODE (range
[1]) == INTEGER_CST
)
1940 lenrange
[0] = wi::to_wide (range
[0], prec
);
1941 lenrange
[1] = wi::to_wide (range
[1], prec
);
1945 lenrange
[0] = wi::shwi (0, prec
);
1946 lenrange
[1] = wi::shwi (-1, prec
);
1950 location_t callloc
= gimple_location (stmt
);
1951 tree func
= gimple_call_fndecl (stmt
);
1953 if (lenrange
[0] != 0 || !wi::neg_p (lenrange
[1]))
1955 /* If the longest source string is shorter than the lower bound
1956 of the specified count the copy is definitely nul-terminated. */
1957 if (wi::ltu_p (lenrange
[1], cntrange
[0]))
1960 if (wi::neg_p (lenrange
[1]))
1962 /* The length of one of the strings is unknown but at least
1963 one has non-zero length and that length is stored in
1964 LENRANGE[1]. Swap the bounds to force a "may be truncated"
1966 lenrange
[1] = lenrange
[0];
1967 lenrange
[0] = wi::shwi (0, prec
);
1970 gcall
*call
= as_a
<gcall
*> (stmt
);
1972 if (lenrange
[0] == cntrange
[1] && cntrange
[0] == cntrange
[1])
1973 return warning_n (callloc
, OPT_Wstringop_truncation
,
1974 cntrange
[0].to_uhwi (),
1975 "%G%qD output truncated before terminating "
1976 "nul copying %E byte from a string of the "
1978 "%G%qD output truncated before terminating nul "
1979 "copying %E bytes from a string of the same "
1982 else if (wi::geu_p (lenrange
[0], cntrange
[1]))
1984 /* The shortest string is longer than the upper bound of
1985 the count so the truncation is certain. */
1986 if (cntrange
[0] == cntrange
[1])
1987 return warning_n (callloc
, OPT_Wstringop_truncation
,
1988 cntrange
[0].to_uhwi (),
1989 "%G%qD output truncated copying %E byte "
1990 "from a string of length %wu",
1991 "%G%qD output truncated copying %E bytes "
1992 "from a string of length %wu",
1993 call
, func
, cnt
, lenrange
[0].to_uhwi ());
1995 return warning_at (callloc
, OPT_Wstringop_truncation
,
1996 "%G%qD output truncated copying between %wu "
1997 "and %wu bytes from a string of length %wu",
1998 call
, func
, cntrange
[0].to_uhwi (),
1999 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
2001 else if (wi::geu_p (lenrange
[1], cntrange
[1]))
2003 /* The longest string is longer than the upper bound of
2004 the count so the truncation is possible. */
2005 if (cntrange
[0] == cntrange
[1])
2006 return warning_n (callloc
, OPT_Wstringop_truncation
,
2007 cntrange
[0].to_uhwi (),
2008 "%G%qD output may be truncated copying %E "
2009 "byte from a string of length %wu",
2010 "%G%qD output may be truncated copying %E "
2011 "bytes from a string of length %wu",
2012 call
, func
, cnt
, lenrange
[1].to_uhwi ());
2014 return warning_at (callloc
, OPT_Wstringop_truncation
,
2015 "%G%qD output may be truncated copying between %wu "
2016 "and %wu bytes from a string of length %wu",
2017 call
, func
, cntrange
[0].to_uhwi (),
2018 cntrange
[1].to_uhwi (), lenrange
[1].to_uhwi ());
2021 if (cntrange
[0] != cntrange
[1]
2022 && wi::leu_p (cntrange
[0], lenrange
[0])
2023 && wi::leu_p (cntrange
[1], lenrange
[0] + 1))
2025 /* If the source (including the terminating nul) is longer than
2026 the lower bound of the specified count but shorter than the
2027 upper bound the copy may (but need not) be truncated. */
2028 return warning_at (callloc
, OPT_Wstringop_truncation
,
2029 "%G%qD output may be truncated copying between "
2030 "%wu and %wu bytes from a string of length %wu",
2031 call
, func
, cntrange
[0].to_uhwi (),
2032 cntrange
[1].to_uhwi (), lenrange
[0].to_uhwi ());
2036 if (tree dstsize
= compute_objsize (dst
, 1))
2038 /* The source length is uknown. Try to determine the destination
2039 size and see if it matches the specified bound. If not, bail.
2040 Otherwise go on to see if it should be diagnosed for possible
2045 if (wi::to_wide (dstsize
) != cntrange
[1])
2048 if (cntrange
[0] == cntrange
[1])
2049 return warning_at (callloc
, OPT_Wstringop_truncation
,
2050 "%G%qD specified bound %E equals destination size",
2051 as_a
<gcall
*> (stmt
), func
, cnt
);
2057 /* Check the arguments to the built-in forms of stpncpy and strncpy for
2058 out-of-bounds offsets or overlapping access, and to see if the size
2059 is derived from calling strlen() on the source argument, and if so,
2060 issue the appropriate warning. */
2063 handle_builtin_stxncpy (built_in_function
, gimple_stmt_iterator
*gsi
)
2065 if (!strlen_to_stridx
)
2068 gimple
*stmt
= gsi_stmt (*gsi
);
2070 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
2072 tree dst
= gimple_call_arg (stmt
, with_bounds
? 1 : 0);
2073 tree src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
2074 tree len
= gimple_call_arg (stmt
, with_bounds
? 3 : 2);
2075 tree dstsize
= NULL_TREE
, srcsize
= NULL_TREE
;
2077 int didx
= get_stridx (dst
);
2078 if (strinfo
*sidst
= didx
> 0 ? get_strinfo (didx
) : NULL
)
2080 /* Compute the size of the destination string including the NUL. */
2081 if (sidst
->nonzero_chars
)
2083 tree type
= TREE_TYPE (sidst
->nonzero_chars
);
2084 dstsize
= fold_build2 (PLUS_EXPR
, type
, sidst
->nonzero_chars
,
2085 build_int_cst (type
, 1));
2090 int sidx
= get_stridx (src
);
2091 strinfo
*sisrc
= sidx
> 0 ? get_strinfo (sidx
) : NULL
;
2094 /* strncat() and strncpy() can modify the source string by writing
2095 over the terminating nul so SISRC->DONT_INVALIDATE must be left
2098 /* Compute the size of the source string including the NUL. */
2099 if (sisrc
->nonzero_chars
)
2101 tree type
= TREE_TYPE (sisrc
->nonzero_chars
);
2102 srcsize
= fold_build2 (PLUS_EXPR
, type
, sisrc
->nonzero_chars
,
2103 build_int_cst (type
, 1));
2109 srcsize
= NULL_TREE
;
2111 if (!check_bounds_or_overlap (as_a
<gcall
*>(stmt
), dst
, src
,
2114 gimple_set_no_warning (stmt
, true);
2118 /* If the length argument was computed from strlen(S) for some string
2119 S retrieve the strinfo index for the string (PSS->FIRST) alonng with
2120 the location of the strlen() call (PSS->SECOND). */
2121 stridx_strlenloc
*pss
= strlen_to_stridx
->get (len
);
2122 if (!pss
|| pss
->first
<= 0)
2124 if (maybe_diag_stxncpy_trunc (*gsi
, src
, len
))
2125 gimple_set_no_warning (stmt
, true);
2130 /* Retrieve the strinfo data for the string S that LEN was computed
2131 from as some function F of strlen (S) (i.e., LEN need not be equal
2133 strinfo
*silen
= get_strinfo (pss
->first
);
2135 location_t callloc
= gimple_location (stmt
);
2137 tree func
= gimple_call_fndecl (stmt
);
2139 bool warned
= false;
2141 /* When -Wstringop-truncation is set, try to determine truncation
2142 before diagnosing possible overflow. Truncation is implied by
2143 the LEN argument being equal to strlen(SRC), regardless of
2144 whether its value is known. Otherwise, issue the more generic
2145 -Wstringop-overflow which triggers for LEN arguments that in
2146 any meaningful way depend on strlen(SRC). */
2148 && is_strlen_related_p (src
, len
)
2149 && warning_at (callloc
, OPT_Wstringop_truncation
,
2150 "%G%qD output truncated before terminating nul "
2151 "copying as many bytes from a string as its length",
2152 as_a
<gcall
*>(stmt
), func
))
2154 else if (silen
&& is_strlen_related_p (src
, silen
->ptr
))
2155 warned
= warning_at (callloc
, OPT_Wstringop_overflow_
,
2156 "%G%qD specified bound depends on the length "
2157 "of the source argument",
2158 as_a
<gcall
*>(stmt
), func
);
2161 location_t strlenloc
= pss
->second
;
2162 if (strlenloc
!= UNKNOWN_LOCATION
&& strlenloc
!= callloc
)
2163 inform (strlenloc
, "length computed here");
2167 /* Handle a memcpy-like ({mem{,p}cpy,__mem{,p}cpy_chk}) call.
2168 If strlen of the second argument is known and length of the third argument
2169 is that plus one, strlen of the first argument is the same after this
2173 handle_builtin_memcpy (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2176 tree src
, dst
, len
, lhs
, oldlen
, newlen
;
2177 gimple
*stmt
= gsi_stmt (*gsi
);
2178 strinfo
*si
, *dsi
, *olddsi
;
2179 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
2181 len
= gimple_call_arg (stmt
, with_bounds
? 4 : 2);
2182 src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
2183 dst
= gimple_call_arg (stmt
, 0);
2184 idx
= get_stridx (src
);
2188 didx
= get_stridx (dst
);
2191 olddsi
= get_strinfo (didx
);
2196 && tree_fits_uhwi_p (len
)
2197 && !integer_zerop (len
))
2198 adjust_last_stmt (olddsi
, stmt
, false);
2205 /* Handle memcpy (x, y, l) where l's relationship with strlen (y)
2207 si
= get_strinfo (idx
);
2208 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
2210 if (TREE_CODE (len
) == INTEGER_CST
2211 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
2213 if (tree_int_cst_le (len
, si
->nonzero_chars
))
2215 /* Copying LEN nonzero characters, where LEN is constant. */
2217 full_string_p
= false;
2221 /* Copying the whole of the analyzed part of SI. */
2222 newlen
= si
->nonzero_chars
;
2223 full_string_p
= si
->full_string_p
;
2228 if (!si
->full_string_p
)
2230 if (TREE_CODE (len
) != SSA_NAME
)
2232 def_stmt
= SSA_NAME_DEF_STMT (len
);
2233 if (!is_gimple_assign (def_stmt
)
2234 || gimple_assign_rhs_code (def_stmt
) != PLUS_EXPR
2235 || gimple_assign_rhs1 (def_stmt
) != si
->nonzero_chars
2236 || !integer_onep (gimple_assign_rhs2 (def_stmt
)))
2238 /* Copying variable-length string SI (and no more). */
2239 newlen
= si
->nonzero_chars
;
2240 full_string_p
= true;
2246 /* Handle memcpy (x, "abcd", 5) or
2247 memcpy (x, "abc\0uvw", 7). */
2248 if (!tree_fits_uhwi_p (len
))
2251 unsigned HOST_WIDE_INT clen
= tree_to_uhwi (len
);
2252 unsigned HOST_WIDE_INT nonzero_chars
= ~idx
;
2253 newlen
= build_int_cst (size_type_node
, MIN (nonzero_chars
, clen
));
2254 full_string_p
= clen
> nonzero_chars
;
2257 if (olddsi
!= NULL
&& TREE_CODE (len
) == SSA_NAME
)
2258 adjust_last_stmt (olddsi
, stmt
, false);
2262 didx
= new_stridx (dst
);
2269 dsi
= unshare_strinfo (olddsi
);
2270 oldlen
= olddsi
->nonzero_chars
;
2271 dsi
->nonzero_chars
= newlen
;
2272 dsi
->full_string_p
= full_string_p
;
2273 /* Break the chain, so adjust_related_strinfo on later pointers in
2274 the chain won't adjust this one anymore. */
2277 dsi
->endptr
= NULL_TREE
;
2281 dsi
= new_strinfo (dst
, didx
, newlen
, full_string_p
);
2282 set_strinfo (didx
, dsi
);
2283 find_equal_ptrs (dst
, didx
);
2285 dsi
->writable
= true;
2286 dsi
->dont_invalidate
= true;
2289 tree adj
= NULL_TREE
;
2290 location_t loc
= gimple_location (stmt
);
2291 if (oldlen
== NULL_TREE
)
2293 else if (integer_zerop (oldlen
))
2295 else if (TREE_CODE (oldlen
) == INTEGER_CST
2296 || TREE_CODE (newlen
) == INTEGER_CST
)
2297 adj
= fold_build2_loc (loc
, MINUS_EXPR
, TREE_TYPE (newlen
), newlen
,
2298 fold_convert_loc (loc
, TREE_TYPE (newlen
),
2300 if (adj
!= NULL_TREE
)
2301 adjust_related_strinfos (loc
, dsi
, adj
);
2305 /* memcpy src may not overlap dst, so src doesn't need to be
2306 invalidated either. */
2308 si
->dont_invalidate
= true;
2312 lhs
= gimple_call_lhs (stmt
);
2315 case BUILT_IN_MEMCPY
:
2316 case BUILT_IN_MEMCPY_CHK
:
2317 case BUILT_IN_MEMCPY_CHKP
:
2318 case BUILT_IN_MEMCPY_CHK_CHKP
:
2319 /* Allow adjust_last_stmt to decrease this memcpy's size. */
2320 laststmt
.stmt
= stmt
;
2321 laststmt
.len
= dsi
->nonzero_chars
;
2322 laststmt
.stridx
= dsi
->idx
;
2324 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = didx
;
2326 case BUILT_IN_MEMPCPY
:
2327 case BUILT_IN_MEMPCPY_CHK
:
2328 case BUILT_IN_MEMPCPY_CHKP
:
2329 case BUILT_IN_MEMPCPY_CHK_CHKP
:
2337 /* Handle a strcat-like ({strcat,__strcat_chk}) call.
2338 If strlen of the second argument is known, strlen of the first argument
2339 is increased by the length of the second argument. Furthermore, attempt
2340 to convert it to memcpy/strcpy if the length of the first argument
2344 handle_builtin_strcat (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2347 tree srclen
, args
, type
, fn
, objsz
, endptr
;
2349 gimple
*stmt
= gsi_stmt (*gsi
);
2351 location_t loc
= gimple_location (stmt
);
2352 bool with_bounds
= gimple_call_with_bounds_p (stmt
);
2354 tree src
= gimple_call_arg (stmt
, with_bounds
? 2 : 1);
2355 tree dst
= gimple_call_arg (stmt
, 0);
2357 /* Bail if the source is the same as destination. It will be diagnosed
2359 if (operand_equal_p (src
, dst
, 0))
2362 tree lhs
= gimple_call_lhs (stmt
);
2364 didx
= get_stridx (dst
);
2370 dsi
= get_strinfo (didx
);
2374 idx
= get_stridx (src
);
2376 srclen
= build_int_cst (size_type_node
, ~idx
);
2379 si
= get_strinfo (idx
);
2381 srclen
= get_string_length (si
);
2384 /* Set the no-warning bit on the transformed statement? */
2385 bool set_no_warning
= false;
2387 if (dsi
== NULL
|| get_string_length (dsi
) == NULL_TREE
)
2390 /* The concatenation always involves copying at least one byte
2391 (the terminating nul), even if the source string is empty.
2392 If the source is unknown assume it's one character long and
2393 used that as both sizes. */
2397 tree type
= TREE_TYPE (slen
);
2398 slen
= fold_build2 (PLUS_EXPR
, type
, slen
, build_int_cst (type
, 1));
2401 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2403 if (!check_bounds_or_overlap (as_a
<gcall
*>(stmt
), dst
, sptr
,
2406 gimple_set_no_warning (stmt
, true);
2407 set_no_warning
= true;
2411 /* strcat (p, q) can be transformed into
2412 tmp = p + strlen (p); endptr = stpcpy (tmp, q);
2413 with length endptr - p if we need to compute the length
2414 later on. Don't do this transformation if we don't need
2416 if (builtin_decl_implicit_p (BUILT_IN_STPCPY
) && lhs
== NULL_TREE
)
2420 didx
= new_stridx (dst
);
2426 dsi
= new_strinfo (dst
, didx
, NULL_TREE
, false);
2427 set_strinfo (didx
, dsi
);
2428 find_equal_ptrs (dst
, didx
);
2432 dsi
= unshare_strinfo (dsi
);
2433 dsi
->nonzero_chars
= NULL_TREE
;
2434 dsi
->full_string_p
= false;
2436 dsi
->endptr
= NULL_TREE
;
2438 dsi
->writable
= true;
2440 dsi
->dont_invalidate
= true;
2445 tree dstlen
= dsi
->nonzero_chars
;
2446 endptr
= dsi
->endptr
;
2448 dsi
= unshare_strinfo (dsi
);
2449 dsi
->endptr
= NULL_TREE
;
2451 dsi
->writable
= true;
2453 if (srclen
!= NULL_TREE
)
2455 dsi
->nonzero_chars
= fold_build2_loc (loc
, PLUS_EXPR
,
2456 TREE_TYPE (dsi
->nonzero_chars
),
2457 dsi
->nonzero_chars
, srclen
);
2458 gcc_assert (dsi
->full_string_p
);
2459 adjust_related_strinfos (loc
, dsi
, srclen
);
2460 dsi
->dont_invalidate
= true;
2464 dsi
->nonzero_chars
= NULL
;
2465 dsi
->full_string_p
= false;
2466 if (lhs
== NULL_TREE
&& builtin_decl_implicit_p (BUILT_IN_STPCPY
))
2467 dsi
->dont_invalidate
= true;
2471 /* strcat src may not overlap dst, so src doesn't need to be
2472 invalidated either. */
2473 si
->dont_invalidate
= true;
2475 /* For now. Could remove the lhs from the call and add
2476 lhs = dst; afterwards. */
2484 case BUILT_IN_STRCAT
:
2485 case BUILT_IN_STRCAT_CHKP
:
2486 if (srclen
!= NULL_TREE
)
2487 fn
= builtin_decl_implicit (BUILT_IN_MEMCPY
);
2489 fn
= builtin_decl_implicit (BUILT_IN_STRCPY
);
2491 case BUILT_IN_STRCAT_CHK
:
2492 case BUILT_IN_STRCAT_CHK_CHKP
:
2493 if (srclen
!= NULL_TREE
)
2494 fn
= builtin_decl_explicit (BUILT_IN_MEMCPY_CHK
);
2496 fn
= builtin_decl_explicit (BUILT_IN_STRCPY_CHK
);
2497 objsz
= gimple_call_arg (stmt
, with_bounds
? 4 : 2);
2503 if (fn
== NULL_TREE
)
2508 tree type
= TREE_TYPE (dstlen
);
2510 /* Compute the size of the source sequence, including the nul. */
2511 tree srcsize
= srclen
? srclen
: size_zero_node
;
2512 srcsize
= fold_build2 (PLUS_EXPR
, type
, srcsize
, build_int_cst (type
, 1));
2514 tree sptr
= si
&& si
->ptr
? si
->ptr
: src
;
2516 if (!check_bounds_or_overlap (as_a
<gcall
*>(stmt
), dst
, sptr
,
2519 gimple_set_no_warning (stmt
, true);
2520 set_no_warning
= true;
2524 tree len
= NULL_TREE
;
2525 if (srclen
!= NULL_TREE
)
2527 args
= TYPE_ARG_TYPES (TREE_TYPE (fn
));
2528 type
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (args
)));
2530 len
= fold_convert_loc (loc
, type
, unshare_expr (srclen
));
2531 len
= fold_build2_loc (loc
, PLUS_EXPR
, type
, len
,
2532 build_int_cst (type
, 1));
2533 len
= force_gimple_operand_gsi (gsi
, len
, true, NULL_TREE
, true,
2537 dst
= fold_convert_loc (loc
, TREE_TYPE (dst
), unshare_expr (endptr
));
2539 dst
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
2540 TREE_TYPE (dst
), unshare_expr (dst
),
2541 fold_convert_loc (loc
, sizetype
,
2542 unshare_expr (dstlen
)));
2543 dst
= force_gimple_operand_gsi (gsi
, dst
, true, NULL_TREE
, true,
2545 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2547 fprintf (dump_file
, "Optimizing: ");
2548 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2552 fn
= chkp_maybe_create_clone (fn
)->decl
;
2553 if (srclen
!= NULL_TREE
)
2554 success
= update_gimple_call (gsi
, fn
, 5 + (objsz
!= NULL_TREE
),
2556 gimple_call_arg (stmt
, 1),
2558 gimple_call_arg (stmt
, 3),
2561 success
= update_gimple_call (gsi
, fn
, 4 + (objsz
!= NULL_TREE
),
2563 gimple_call_arg (stmt
, 1),
2565 gimple_call_arg (stmt
, 3),
2569 if (srclen
!= NULL_TREE
)
2570 success
= update_gimple_call (gsi
, fn
, 3 + (objsz
!= NULL_TREE
),
2571 dst
, src
, len
, objsz
);
2573 success
= update_gimple_call (gsi
, fn
, 2 + (objsz
!= NULL_TREE
),
2577 stmt
= gsi_stmt (*gsi
);
2578 gimple_call_set_with_bounds (stmt
, with_bounds
);
2580 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2582 fprintf (dump_file
, "into: ");
2583 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2585 /* If srclen == NULL, note that current string length can be
2586 computed by transforming this strcpy into stpcpy. */
2587 if (srclen
== NULL_TREE
&& dsi
->dont_invalidate
)
2589 adjust_last_stmt (dsi
, stmt
, true);
2590 if (srclen
!= NULL_TREE
)
2592 laststmt
.stmt
= stmt
;
2593 laststmt
.len
= srclen
;
2594 laststmt
.stridx
= dsi
->idx
;
2597 else if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
2598 fprintf (dump_file
, "not possible.\n");
2601 gimple_set_no_warning (stmt
, true);
2604 /* Handle a call to malloc or calloc. */
2607 handle_builtin_malloc (enum built_in_function bcode
, gimple_stmt_iterator
*gsi
)
2609 gimple
*stmt
= gsi_stmt (*gsi
);
2610 tree lhs
= gimple_call_lhs (stmt
);
2611 if (lhs
== NULL_TREE
)
2614 gcc_assert (get_stridx (lhs
) == 0);
2615 int idx
= new_stridx (lhs
);
2616 tree length
= NULL_TREE
;
2617 if (bcode
== BUILT_IN_CALLOC
)
2618 length
= build_int_cst (size_type_node
, 0);
2619 strinfo
*si
= new_strinfo (lhs
, idx
, length
, length
!= NULL_TREE
);
2620 if (bcode
== BUILT_IN_CALLOC
)
2622 set_strinfo (idx
, si
);
2623 si
->writable
= true;
2625 si
->dont_invalidate
= true;
2628 /* Handle a call to memset.
2629 After a call to calloc, memset(,0,) is unnecessary.
2630 memset(malloc(n),0,n) is calloc(n,1). */
2633 handle_builtin_memset (gimple_stmt_iterator
*gsi
)
2635 gimple
*stmt2
= gsi_stmt (*gsi
);
2636 if (!integer_zerop (gimple_call_arg (stmt2
, 1)))
2638 tree ptr
= gimple_call_arg (stmt2
, 0);
2639 int idx1
= get_stridx (ptr
);
2642 strinfo
*si1
= get_strinfo (idx1
);
2645 gimple
*stmt1
= si1
->stmt
;
2646 if (!stmt1
|| !is_gimple_call (stmt1
))
2648 tree callee1
= gimple_call_fndecl (stmt1
);
2649 if (!valid_builtin_call (stmt1
))
2651 enum built_in_function code1
= DECL_FUNCTION_CODE (callee1
);
2652 tree size
= gimple_call_arg (stmt2
, 2);
2653 if (code1
== BUILT_IN_CALLOC
)
2654 /* Not touching stmt1 */ ;
2655 else if (code1
== BUILT_IN_MALLOC
2656 && operand_equal_p (gimple_call_arg (stmt1
, 0), size
, 0))
2658 gimple_stmt_iterator gsi1
= gsi_for_stmt (stmt1
);
2659 update_gimple_call (&gsi1
, builtin_decl_implicit (BUILT_IN_CALLOC
), 2,
2660 size
, build_one_cst (size_type_node
));
2661 si1
->nonzero_chars
= build_int_cst (size_type_node
, 0);
2662 si1
->full_string_p
= true;
2663 si1
->stmt
= gsi_stmt (gsi1
);
2667 tree lhs
= gimple_call_lhs (stmt2
);
2668 unlink_stmt_vdef (stmt2
);
2671 gimple
*assign
= gimple_build_assign (lhs
, ptr
);
2672 gsi_replace (gsi
, assign
, false);
2676 gsi_remove (gsi
, true);
2677 release_defs (stmt2
);
2683 /* Handle a call to memcmp. We try to handle small comparisons by
2684 converting them to load and compare, and replacing the call to memcmp
2685 with a __builtin_memcmp_eq call where possible. */
2688 handle_builtin_memcmp (gimple_stmt_iterator
*gsi
)
2690 gcall
*stmt2
= as_a
<gcall
*> (gsi_stmt (*gsi
));
2691 tree res
= gimple_call_lhs (stmt2
);
2692 tree arg1
= gimple_call_arg (stmt2
, 0);
2693 tree arg2
= gimple_call_arg (stmt2
, 1);
2694 tree len
= gimple_call_arg (stmt2
, 2);
2695 unsigned HOST_WIDE_INT leni
;
2696 use_operand_p use_p
;
2697 imm_use_iterator iter
;
2702 FOR_EACH_IMM_USE_FAST (use_p
, iter
, res
)
2704 gimple
*ustmt
= USE_STMT (use_p
);
2706 if (is_gimple_debug (ustmt
))
2708 if (gimple_code (ustmt
) == GIMPLE_ASSIGN
)
2710 gassign
*asgn
= as_a
<gassign
*> (ustmt
);
2711 tree_code code
= gimple_assign_rhs_code (asgn
);
2712 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2713 || !integer_zerop (gimple_assign_rhs2 (asgn
)))
2716 else if (gimple_code (ustmt
) == GIMPLE_COND
)
2718 tree_code code
= gimple_cond_code (ustmt
);
2719 if ((code
!= EQ_EXPR
&& code
!= NE_EXPR
)
2720 || !integer_zerop (gimple_cond_rhs (ustmt
)))
2727 if (tree_fits_uhwi_p (len
)
2728 && (leni
= tree_to_uhwi (len
)) <= GET_MODE_SIZE (word_mode
)
2729 && pow2p_hwi (leni
))
2731 leni
*= CHAR_TYPE_SIZE
;
2732 unsigned align1
= get_pointer_alignment (arg1
);
2733 unsigned align2
= get_pointer_alignment (arg2
);
2734 unsigned align
= MIN (align1
, align2
);
2735 scalar_int_mode mode
;
2736 if (int_mode_for_size (leni
, 1).exists (&mode
)
2737 && (align
>= leni
|| !targetm
.slow_unaligned_access (mode
, align
)))
2739 location_t loc
= gimple_location (stmt2
);
2741 type
= build_nonstandard_integer_type (leni
, 1);
2742 gcc_assert (known_eq (GET_MODE_BITSIZE (TYPE_MODE (type
)), leni
));
2743 tree ptrtype
= build_pointer_type_for_mode (char_type_node
,
2745 off
= build_int_cst (ptrtype
, 0);
2746 arg1
= build2_loc (loc
, MEM_REF
, type
, arg1
, off
);
2747 arg2
= build2_loc (loc
, MEM_REF
, type
, arg2
, off
);
2748 tree tem1
= fold_const_aggregate_ref (arg1
);
2751 tree tem2
= fold_const_aggregate_ref (arg2
);
2754 res
= fold_convert_loc (loc
, TREE_TYPE (res
),
2755 fold_build2_loc (loc
, NE_EXPR
,
2758 gimplify_and_update_call_from_tree (gsi
, res
);
2763 gimple_call_set_fndecl (stmt2
, builtin_decl_explicit (BUILT_IN_MEMCMP_EQ
));
2767 /* Handle a POINTER_PLUS_EXPR statement.
2768 For p = "abcd" + 2; compute associated length, or if
2769 p = q + off is pointing to a '\0' character of a string, call
2770 zero_length_string on it. */
2773 handle_pointer_plus (gimple_stmt_iterator
*gsi
)
2775 gimple
*stmt
= gsi_stmt (*gsi
);
2776 tree lhs
= gimple_assign_lhs (stmt
), off
;
2777 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
2785 tree off
= gimple_assign_rhs2 (stmt
);
2786 if (tree_fits_uhwi_p (off
)
2787 && tree_to_uhwi (off
) <= (unsigned HOST_WIDE_INT
) ~idx
)
2788 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)]
2789 = ~(~idx
- (int) tree_to_uhwi (off
));
2793 si
= get_strinfo (idx
);
2794 if (si
== NULL
|| si
->nonzero_chars
== NULL_TREE
)
2797 off
= gimple_assign_rhs2 (stmt
);
2799 if (si
->full_string_p
&& operand_equal_p (si
->nonzero_chars
, off
, 0))
2800 zsi
= zero_length_string (lhs
, si
);
2801 else if (TREE_CODE (off
) == SSA_NAME
)
2803 gimple
*def_stmt
= SSA_NAME_DEF_STMT (off
);
2804 if (gimple_assign_single_p (def_stmt
)
2805 && si
->full_string_p
2806 && operand_equal_p (si
->nonzero_chars
,
2807 gimple_assign_rhs1 (def_stmt
), 0))
2808 zsi
= zero_length_string (lhs
, si
);
2811 && si
->endptr
!= NULL_TREE
2812 && si
->endptr
!= lhs
2813 && TREE_CODE (si
->endptr
) == SSA_NAME
)
2815 enum tree_code rhs_code
2816 = useless_type_conversion_p (TREE_TYPE (lhs
), TREE_TYPE (si
->endptr
))
2817 ? SSA_NAME
: NOP_EXPR
;
2818 gimple_assign_set_rhs_with_ops (gsi
, rhs_code
, si
->endptr
);
2819 gcc_assert (gsi_stmt (*gsi
) == stmt
);
2824 /* If RHS, either directly or indirectly, refers to a string of constant
2825 length, return it. Otherwise return a negative value. */
2827 static HOST_WIDE_INT
2828 get_string_cst_length (tree rhs
)
2830 if (TREE_CODE (rhs
) == MEM_REF
2831 && integer_zerop (TREE_OPERAND (rhs
, 1)))
2833 rhs
= TREE_OPERAND (rhs
, 0);
2834 if (TREE_CODE (rhs
) == ADDR_EXPR
)
2836 tree rhs_addr
= rhs
;
2838 rhs
= TREE_OPERAND (rhs
, 0);
2839 if (TREE_CODE (rhs
) != STRING_CST
)
2841 int idx
= get_stridx (rhs_addr
);
2844 strinfo
*si
= get_strinfo (idx
);
2846 && si
->full_string_p
2847 && tree_fits_shwi_p (si
->nonzero_chars
))
2848 return tree_to_shwi (si
->nonzero_chars
);
2854 if (TREE_CODE (rhs
) == VAR_DECL
2855 && TREE_READONLY (rhs
))
2856 rhs
= DECL_INITIAL (rhs
);
2858 if (rhs
&& TREE_CODE (rhs
) == STRING_CST
)
2859 return strlen (TREE_STRING_POINTER (rhs
));
2864 /* Handle a single character store. */
2867 handle_char_store (gimple_stmt_iterator
*gsi
)
2871 gimple
*stmt
= gsi_stmt (*gsi
);
2872 tree ssaname
= NULL_TREE
, lhs
= gimple_assign_lhs (stmt
);
2873 tree rhs
= gimple_assign_rhs1 (stmt
);
2874 unsigned HOST_WIDE_INT offset
= 0;
2876 if (TREE_CODE (lhs
) == MEM_REF
2877 && TREE_CODE (TREE_OPERAND (lhs
, 0)) == SSA_NAME
)
2879 tree mem_offset
= TREE_OPERAND (lhs
, 1);
2880 if (tree_fits_uhwi_p (mem_offset
))
2882 /* Get the strinfo for the base, and use it if it starts with at
2883 least OFFSET nonzero characters. This is trivially true if
2885 offset
= tree_to_uhwi (mem_offset
);
2886 idx
= get_stridx (TREE_OPERAND (lhs
, 0));
2888 si
= get_strinfo (idx
);
2890 ssaname
= TREE_OPERAND (lhs
, 0);
2891 else if (si
== NULL
|| compare_nonzero_chars (si
, offset
) < 0)
2897 idx
= get_addr_stridx (lhs
, NULL_TREE
, &offset
);
2899 si
= get_strinfo (idx
);
2902 bool storing_zero_p
= initializer_zerop (rhs
);
2903 bool storing_nonzero_p
= (!storing_zero_p
2904 && TREE_CODE (rhs
) == INTEGER_CST
2905 && integer_nonzerop (rhs
));
2906 /* Set to the length of the string being assigned if known. */
2907 HOST_WIDE_INT rhslen
;
2911 int cmp
= compare_nonzero_chars (si
, offset
);
2912 gcc_assert (offset
== 0 || cmp
>= 0);
2913 if (storing_zero_p
&& cmp
== 0 && si
->full_string_p
)
2915 /* When overwriting a '\0' with a '\0', the store can be removed
2916 if we know it has been stored in the current function. */
2917 if (!stmt_could_throw_p (stmt
) && si
->writable
)
2919 unlink_stmt_vdef (stmt
);
2920 release_defs (stmt
);
2921 gsi_remove (gsi
, true);
2926 si
->writable
= true;
2931 /* If si->nonzero_chars > OFFSET, we aren't overwriting '\0',
2932 and if we aren't storing '\0', we know that the length of the
2933 string and any other zero terminated string in memory remains
2934 the same. In that case we move to the next gimple statement and
2935 return to signal the caller that it shouldn't invalidate anything.
2937 This is benefical for cases like:
2942 strcpy (p, "foobar");
2943 size_t len = strlen (p); // This can be optimized into 6
2944 size_t len2 = strlen (q); // This has to be computed
2946 size_t len3 = strlen (p); // This can be optimized into 6
2947 size_t len4 = strlen (q); // This can be optimized into len2
2948 bar (len, len2, len3, len4);
2951 else if (storing_nonzero_p
&& cmp
> 0)
2956 else if (storing_zero_p
|| storing_nonzero_p
|| (offset
!= 0 && cmp
> 0))
2958 /* When storing_nonzero_p, we know that the string now starts
2959 with OFFSET + 1 nonzero characters, but don't know whether
2960 there's a following nul terminator.
2962 When storing_zero_p, we know that the string is now OFFSET
2965 Otherwise, we're storing an unknown value at offset OFFSET,
2966 so need to clip the nonzero_chars to OFFSET. */
2967 location_t loc
= gimple_location (stmt
);
2968 tree oldlen
= si
->nonzero_chars
;
2969 if (cmp
== 0 && si
->full_string_p
)
2970 /* We're overwriting the nul terminator with a nonzero or
2971 unknown character. If the previous stmt was a memcpy,
2972 its length may be decreased. */
2973 adjust_last_stmt (si
, stmt
, false);
2974 si
= unshare_strinfo (si
);
2975 if (storing_nonzero_p
)
2976 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
+ 1);
2978 si
->nonzero_chars
= build_int_cst (size_type_node
, offset
);
2979 si
->full_string_p
= storing_zero_p
;
2982 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
2983 si
->endptr
= ssaname
;
2988 si
->writable
= true;
2989 si
->dont_invalidate
= true;
2992 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
, size_type_node
,
2993 si
->nonzero_chars
, oldlen
);
2994 adjust_related_strinfos (loc
, si
, adj
);
3000 else if (idx
== 0 && (storing_zero_p
|| storing_nonzero_p
))
3003 idx
= new_stridx (ssaname
);
3005 idx
= new_addr_stridx (lhs
);
3008 tree ptr
= (ssaname
? ssaname
: build_fold_addr_expr (lhs
));
3009 tree len
= storing_nonzero_p
? size_one_node
: size_zero_node
;
3010 si
= new_strinfo (ptr
, idx
, len
, storing_zero_p
);
3011 set_strinfo (idx
, si
);
3014 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname
))
3015 si
->endptr
= ssaname
;
3016 si
->dont_invalidate
= true;
3017 si
->writable
= true;
3021 && (rhslen
= get_string_cst_length (gimple_assign_rhs1 (stmt
))) >= 0
3022 && ssaname
== NULL_TREE
3023 && TREE_CODE (TREE_TYPE (lhs
)) == ARRAY_TYPE
)
3025 HOST_WIDE_INT a
= int_size_in_bytes (TREE_TYPE (lhs
));
3026 if (a
> 0 && (unsigned HOST_WIDE_INT
) a
> (unsigned HOST_WIDE_INT
) rhslen
)
3028 int idx
= new_addr_stridx (lhs
);
3031 si
= new_strinfo (build_fold_addr_expr (lhs
), idx
,
3032 build_int_cst (size_type_node
, rhslen
), true);
3033 set_strinfo (idx
, si
);
3034 si
->dont_invalidate
= true;
3039 if (si
!= NULL
&& offset
== 0 && storing_zero_p
)
3041 /* Allow adjust_last_stmt to remove it if the stored '\0'
3042 is immediately overwritten. */
3043 laststmt
.stmt
= stmt
;
3044 laststmt
.len
= build_int_cst (size_type_node
, 1);
3045 laststmt
.stridx
= si
->idx
;
3050 /* Try to fold strstr (s, t) eq/ne s to strncmp (s, t, strlen (t)) eq/ne 0. */
3053 fold_strstr_to_strncmp (tree rhs1
, tree rhs2
, gimple
*stmt
)
3055 if (TREE_CODE (rhs1
) != SSA_NAME
3056 || TREE_CODE (rhs2
) != SSA_NAME
)
3059 gimple
*call_stmt
= NULL
;
3060 for (int pass
= 0; pass
< 2; pass
++)
3062 gimple
*g
= SSA_NAME_DEF_STMT (rhs1
);
3063 if (gimple_call_builtin_p (g
, BUILT_IN_STRSTR
)
3064 && has_single_use (rhs1
)
3065 && gimple_call_arg (g
, 0) == rhs2
)
3070 std::swap (rhs1
, rhs2
);
3075 tree arg0
= gimple_call_arg (call_stmt
, 0);
3079 tree arg1
= gimple_call_arg (call_stmt
, 1);
3080 tree arg1_len
= NULL_TREE
;
3081 int idx
= get_stridx (arg1
);
3086 arg1_len
= build_int_cst (size_type_node
, ~idx
);
3089 strinfo
*si
= get_strinfo (idx
);
3091 arg1_len
= get_string_length (si
);
3095 if (arg1_len
!= NULL_TREE
)
3097 gimple_stmt_iterator gsi
= gsi_for_stmt (call_stmt
);
3098 tree strncmp_decl
= builtin_decl_explicit (BUILT_IN_STRNCMP
);
3100 if (!is_gimple_val (arg1_len
))
3102 tree arg1_len_tmp
= make_ssa_name (TREE_TYPE (arg1_len
));
3103 gassign
*arg1_stmt
= gimple_build_assign (arg1_len_tmp
,
3105 gsi_insert_before (&gsi
, arg1_stmt
, GSI_SAME_STMT
);
3106 arg1_len
= arg1_len_tmp
;
3109 gcall
*strncmp_call
= gimple_build_call (strncmp_decl
, 3,
3110 arg0
, arg1
, arg1_len
);
3111 tree strncmp_lhs
= make_ssa_name (integer_type_node
);
3112 gimple_set_vuse (strncmp_call
, gimple_vuse (call_stmt
));
3113 gimple_call_set_lhs (strncmp_call
, strncmp_lhs
);
3114 gsi_remove (&gsi
, true);
3115 gsi_insert_before (&gsi
, strncmp_call
, GSI_SAME_STMT
);
3116 tree zero
= build_zero_cst (TREE_TYPE (strncmp_lhs
));
3118 if (is_gimple_assign (stmt
))
3120 if (gimple_assign_rhs_code (stmt
) == COND_EXPR
)
3122 tree cond
= gimple_assign_rhs1 (stmt
);
3123 TREE_OPERAND (cond
, 0) = strncmp_lhs
;
3124 TREE_OPERAND (cond
, 1) = zero
;
3128 gimple_assign_set_rhs1 (stmt
, strncmp_lhs
);
3129 gimple_assign_set_rhs2 (stmt
, zero
);
3134 gcond
*cond
= as_a
<gcond
*> (stmt
);
3135 gimple_cond_set_lhs (cond
, strncmp_lhs
);
3136 gimple_cond_set_rhs (cond
, zero
);
3144 /* Attempt to check for validity of the performed access a single statement
3145 at *GSI using string length knowledge, and to optimize it.
3146 If the given basic block needs clean-up of EH, CLEANUP_EH is set to
3150 strlen_check_and_optimize_stmt (gimple_stmt_iterator
*gsi
, bool *cleanup_eh
)
3152 gimple
*stmt
= gsi_stmt (*gsi
);
3154 if (is_gimple_call (stmt
))
3156 tree callee
= gimple_call_fndecl (stmt
);
3157 if (valid_builtin_call (stmt
))
3158 switch (DECL_FUNCTION_CODE (callee
))
3160 case BUILT_IN_STRLEN
:
3161 case BUILT_IN_STRLEN_CHKP
:
3162 handle_builtin_strlen (gsi
);
3164 case BUILT_IN_STRCHR
:
3165 case BUILT_IN_STRCHR_CHKP
:
3166 handle_builtin_strchr (gsi
);
3168 case BUILT_IN_STRCPY
:
3169 case BUILT_IN_STRCPY_CHK
:
3170 case BUILT_IN_STPCPY
:
3171 case BUILT_IN_STPCPY_CHK
:
3172 case BUILT_IN_STRCPY_CHKP
:
3173 case BUILT_IN_STRCPY_CHK_CHKP
:
3174 case BUILT_IN_STPCPY_CHKP
:
3175 case BUILT_IN_STPCPY_CHK_CHKP
:
3176 handle_builtin_strcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3179 case BUILT_IN_STRNCAT
:
3180 case BUILT_IN_STRNCAT_CHK
:
3181 handle_builtin_strncat (DECL_FUNCTION_CODE (callee
), gsi
);
3184 case BUILT_IN_STPNCPY
:
3185 case BUILT_IN_STPNCPY_CHK
:
3186 case BUILT_IN_STRNCPY
:
3187 case BUILT_IN_STRNCPY_CHK
:
3188 handle_builtin_stxncpy (DECL_FUNCTION_CODE (callee
), gsi
);
3191 case BUILT_IN_MEMCPY
:
3192 case BUILT_IN_MEMCPY_CHK
:
3193 case BUILT_IN_MEMPCPY
:
3194 case BUILT_IN_MEMPCPY_CHK
:
3195 case BUILT_IN_MEMCPY_CHKP
:
3196 case BUILT_IN_MEMCPY_CHK_CHKP
:
3197 case BUILT_IN_MEMPCPY_CHKP
:
3198 case BUILT_IN_MEMPCPY_CHK_CHKP
:
3199 handle_builtin_memcpy (DECL_FUNCTION_CODE (callee
), gsi
);
3201 case BUILT_IN_STRCAT
:
3202 case BUILT_IN_STRCAT_CHK
:
3203 case BUILT_IN_STRCAT_CHKP
:
3204 case BUILT_IN_STRCAT_CHK_CHKP
:
3205 handle_builtin_strcat (DECL_FUNCTION_CODE (callee
), gsi
);
3207 case BUILT_IN_MALLOC
:
3208 case BUILT_IN_CALLOC
:
3209 handle_builtin_malloc (DECL_FUNCTION_CODE (callee
), gsi
);
3211 case BUILT_IN_MEMSET
:
3212 if (!handle_builtin_memset (gsi
))
3215 case BUILT_IN_MEMCMP
:
3216 if (!handle_builtin_memcmp (gsi
))
3223 else if (is_gimple_assign (stmt
) && !gimple_clobber_p (stmt
))
3225 tree lhs
= gimple_assign_lhs (stmt
);
3227 if (TREE_CODE (lhs
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (lhs
)))
3229 if (gimple_assign_single_p (stmt
)
3230 || (gimple_assign_cast_p (stmt
)
3231 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt
)))))
3233 int idx
= get_stridx (gimple_assign_rhs1 (stmt
));
3234 ssa_ver_to_stridx
[SSA_NAME_VERSION (lhs
)] = idx
;
3236 else if (gimple_assign_rhs_code (stmt
) == POINTER_PLUS_EXPR
)
3237 handle_pointer_plus (gsi
);
3239 else if (TREE_CODE (lhs
) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (lhs
)))
3241 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3242 if (code
== COND_EXPR
)
3244 tree cond
= gimple_assign_rhs1 (stmt
);
3245 enum tree_code cond_code
= TREE_CODE (cond
);
3247 if (cond_code
== EQ_EXPR
|| cond_code
== NE_EXPR
)
3248 fold_strstr_to_strncmp (TREE_OPERAND (cond
, 0),
3249 TREE_OPERAND (cond
, 1), stmt
);
3251 else if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3252 fold_strstr_to_strncmp (gimple_assign_rhs1 (stmt
),
3253 gimple_assign_rhs2 (stmt
), stmt
);
3254 else if (gimple_assign_load_p (stmt
)
3255 && TREE_CODE (TREE_TYPE (lhs
)) == INTEGER_TYPE
3256 && TYPE_MODE (TREE_TYPE (lhs
)) == TYPE_MODE (char_type_node
)
3257 && (TYPE_PRECISION (TREE_TYPE (lhs
))
3258 == TYPE_PRECISION (char_type_node
))
3259 && !gimple_has_volatile_ops (stmt
))
3261 tree off
= integer_zero_node
;
3262 unsigned HOST_WIDE_INT coff
= 0;
3264 tree rhs1
= gimple_assign_rhs1 (stmt
);
3265 if (code
== MEM_REF
)
3267 idx
= get_stridx (TREE_OPERAND (rhs1
, 0));
3270 strinfo
*si
= get_strinfo (idx
);
3272 && si
->nonzero_chars
3273 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
3274 && (wi::to_widest (si
->nonzero_chars
)
3275 >= wi::to_widest (off
)))
3276 off
= TREE_OPERAND (rhs1
, 1);
3278 /* This case is not useful. See if get_addr_stridx
3279 returns something usable. */
3284 idx
= get_addr_stridx (rhs1
, NULL_TREE
, &coff
);
3287 strinfo
*si
= get_strinfo (idx
);
3289 && si
->nonzero_chars
3290 && TREE_CODE (si
->nonzero_chars
) == INTEGER_CST
)
3292 widest_int w1
= wi::to_widest (si
->nonzero_chars
);
3293 widest_int w2
= wi::to_widest (off
) + coff
;
3295 && si
->full_string_p
)
3297 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3299 fprintf (dump_file
, "Optimizing: ");
3300 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3303 /* Reading the final '\0' character. */
3304 tree zero
= build_int_cst (TREE_TYPE (lhs
), 0);
3305 gimple_set_vuse (stmt
, NULL_TREE
);
3306 gimple_assign_set_rhs_from_tree (gsi
, zero
);
3308 |= maybe_clean_or_replace_eh_stmt (stmt
,
3310 stmt
= gsi_stmt (*gsi
);
3313 if (dump_file
&& (dump_flags
& TDF_DETAILS
) != 0)
3315 fprintf (dump_file
, "into: ");
3316 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3321 /* Reading a character before the final '\0'
3322 character. Just set the value range to ~[0, 0]
3323 if we don't have anything better. */
3325 tree type
= TREE_TYPE (lhs
);
3326 enum value_range_type vr
3327 = get_range_info (lhs
, &min
, &max
);
3328 if (vr
== VR_VARYING
3330 && min
== wi::min_value (TYPE_PRECISION (type
),
3332 && max
== wi::max_value (TYPE_PRECISION (type
),
3334 set_range_info (lhs
, VR_ANTI_RANGE
,
3335 wi::zero (TYPE_PRECISION (type
)),
3336 wi::zero (TYPE_PRECISION (type
)));
3342 if (strlen_to_stridx
)
3344 tree rhs1
= gimple_assign_rhs1 (stmt
);
3345 if (stridx_strlenloc
*ps
= strlen_to_stridx
->get (rhs1
))
3346 strlen_to_stridx
->put (lhs
, stridx_strlenloc (*ps
));
3349 else if (TREE_CODE (lhs
) != SSA_NAME
&& !TREE_SIDE_EFFECTS (lhs
))
3351 tree type
= TREE_TYPE (lhs
);
3352 if (TREE_CODE (type
) == ARRAY_TYPE
)
3353 type
= TREE_TYPE (type
);
3354 if (TREE_CODE (type
) == INTEGER_TYPE
3355 && TYPE_MODE (type
) == TYPE_MODE (char_type_node
)
3356 && TYPE_PRECISION (type
) == TYPE_PRECISION (char_type_node
))
3358 if (! handle_char_store (gsi
))
3363 else if (gcond
*cond
= dyn_cast
<gcond
*> (stmt
))
3365 enum tree_code code
= gimple_cond_code (cond
);
3366 if (code
== EQ_EXPR
|| code
== NE_EXPR
)
3367 fold_strstr_to_strncmp (gimple_cond_lhs (stmt
),
3368 gimple_cond_rhs (stmt
), stmt
);
3371 if (gimple_vdef (stmt
))
3372 maybe_invalidate (stmt
);
3376 /* Recursively call maybe_invalidate on stmts that might be executed
3377 in between dombb and current bb and that contain a vdef. Stop when
3378 *count stmts are inspected, or if the whole strinfo vector has
3379 been invalidated. */
3382 do_invalidate (basic_block dombb
, gimple
*phi
, bitmap visited
, int *count
)
3384 unsigned int i
, n
= gimple_phi_num_args (phi
);
3386 for (i
= 0; i
< n
; i
++)
3388 tree vuse
= gimple_phi_arg_def (phi
, i
);
3389 gimple
*stmt
= SSA_NAME_DEF_STMT (vuse
);
3390 basic_block bb
= gimple_bb (stmt
);
3393 || !bitmap_set_bit (visited
, bb
->index
)
3394 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3398 if (gimple_code (stmt
) == GIMPLE_PHI
)
3400 do_invalidate (dombb
, stmt
, visited
, count
);
3407 if (!maybe_invalidate (stmt
))
3412 vuse
= gimple_vuse (stmt
);
3413 stmt
= SSA_NAME_DEF_STMT (vuse
);
3414 if (gimple_bb (stmt
) != bb
)
3416 bb
= gimple_bb (stmt
);
3419 || !bitmap_set_bit (visited
, bb
->index
)
3420 || !dominated_by_p (CDI_DOMINATORS
, bb
, dombb
))
3427 class strlen_dom_walker
: public dom_walker
3430 strlen_dom_walker (cdi_direction direction
)
3431 : dom_walker (direction
), m_cleanup_cfg (false)
3434 virtual edge
before_dom_children (basic_block
);
3435 virtual void after_dom_children (basic_block
);
3437 /* Flag that will trigger TODO_cleanup_cfg to be returned in strlen
3438 execute function. */
3442 /* Callback for walk_dominator_tree. Attempt to optimize various
3443 string ops by remembering string lengths pointed by pointer SSA_NAMEs. */
3446 strlen_dom_walker::before_dom_children (basic_block bb
)
3448 basic_block dombb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
3451 stridx_to_strinfo
= NULL
;
3454 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) dombb
->aux
);
3455 if (stridx_to_strinfo
)
3457 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3460 gphi
*phi
= gsi
.phi ();
3461 if (virtual_operand_p (gimple_phi_result (phi
)))
3463 bitmap visited
= BITMAP_ALLOC (NULL
);
3464 int count_vdef
= 100;
3465 do_invalidate (dombb
, phi
, visited
, &count_vdef
);
3466 BITMAP_FREE (visited
);
3467 if (count_vdef
== 0)
3469 /* If there were too many vdefs in between immediate
3470 dominator and current bb, invalidate everything.
3471 If stridx_to_strinfo has been unshared, we need
3472 to free it, otherwise just set it to NULL. */
3473 if (!strinfo_shared ())
3479 vec_safe_iterate (stridx_to_strinfo
, i
, &si
);
3483 (*stridx_to_strinfo
)[i
] = NULL
;
3487 stridx_to_strinfo
= NULL
;
3495 /* If all PHI arguments have the same string index, the PHI result
3497 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
3500 gphi
*phi
= gsi
.phi ();
3501 tree result
= gimple_phi_result (phi
);
3502 if (!virtual_operand_p (result
) && POINTER_TYPE_P (TREE_TYPE (result
)))
3504 int idx
= get_stridx (gimple_phi_arg_def (phi
, 0));
3507 unsigned int i
, n
= gimple_phi_num_args (phi
);
3508 for (i
= 1; i
< n
; i
++)
3509 if (idx
!= get_stridx (gimple_phi_arg_def (phi
, i
)))
3512 ssa_ver_to_stridx
[SSA_NAME_VERSION (result
)] = idx
;
3517 bool cleanup_eh
= false;
3519 /* Attempt to optimize individual statements. */
3520 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
3521 if (strlen_check_and_optimize_stmt (&gsi
, &cleanup_eh
))
3524 if (cleanup_eh
&& gimple_purge_dead_eh_edges (bb
))
3525 m_cleanup_cfg
= true;
3527 bb
->aux
= stridx_to_strinfo
;
3528 if (vec_safe_length (stridx_to_strinfo
) && !strinfo_shared ())
3529 (*stridx_to_strinfo
)[0] = (strinfo
*) bb
;
3533 /* Callback for walk_dominator_tree. Free strinfo vector if it is
3534 owned by the current bb, clear bb->aux. */
3537 strlen_dom_walker::after_dom_children (basic_block bb
)
3541 stridx_to_strinfo
= ((vec
<strinfo
*, va_heap
, vl_embed
> *) bb
->aux
);
3542 if (vec_safe_length (stridx_to_strinfo
)
3543 && (*stridx_to_strinfo
)[0] == (strinfo
*) bb
)
3548 for (i
= 1; vec_safe_iterate (stridx_to_strinfo
, i
, &si
); ++i
)
3550 vec_free (stridx_to_strinfo
);
3556 /* Main entry point. */
3560 const pass_data pass_data_strlen
=
3562 GIMPLE_PASS
, /* type */
3563 "strlen", /* name */
3564 OPTGROUP_NONE
, /* optinfo_flags */
3565 TV_TREE_STRLEN
, /* tv_id */
3566 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3567 0, /* properties_provided */
3568 0, /* properties_destroyed */
3569 0, /* todo_flags_start */
3570 0, /* todo_flags_finish */
3573 class pass_strlen
: public gimple_opt_pass
3576 pass_strlen (gcc::context
*ctxt
)
3577 : gimple_opt_pass (pass_data_strlen
, ctxt
)
3580 /* opt_pass methods: */
3581 virtual bool gate (function
*) { return flag_optimize_strlen
!= 0; }
3582 virtual unsigned int execute (function
*);
3584 }; // class pass_strlen
3587 pass_strlen::execute (function
*fun
)
3589 gcc_assert (!strlen_to_stridx
);
3590 if (warn_stringop_overflow
|| warn_stringop_truncation
)
3591 strlen_to_stridx
= new hash_map
<tree
, stridx_strlenloc
> ();
3593 ssa_ver_to_stridx
.safe_grow_cleared (num_ssa_names
);
3596 calculate_dominance_info (CDI_DOMINATORS
);
3598 /* String length optimization is implemented as a walk of the dominator
3599 tree and a forward walk of statements within each block. */
3600 strlen_dom_walker
walker (CDI_DOMINATORS
);
3601 walker
.walk (fun
->cfg
->x_entry_block_ptr
);
3603 ssa_ver_to_stridx
.release ();
3604 strinfo_pool
.release ();
3605 if (decl_to_stridxlist_htab
)
3607 obstack_free (&stridx_obstack
, NULL
);
3608 delete decl_to_stridxlist_htab
;
3609 decl_to_stridxlist_htab
= NULL
;
3611 laststmt
.stmt
= NULL
;
3612 laststmt
.len
= NULL_TREE
;
3613 laststmt
.stridx
= 0;
3615 if (strlen_to_stridx
)
3617 strlen_to_stridx
->empty ();
3618 delete strlen_to_stridx
;
3619 strlen_to_stridx
= NULL
;
3622 return walker
.m_cleanup_cfg
? TODO_cleanup_cfg
: 0;
3628 make_pass_strlen (gcc::context
*ctxt
)
3630 return new pass_strlen (ctxt
);